diff options
Diffstat (limited to 'pack-bitmap.c')
| -rw-r--r-- | pack-bitmap.c | 844 |
1 files changed, 678 insertions, 166 deletions
diff --git a/pack-bitmap.c b/pack-bitmap.c index 7367f62bb6..6406953d32 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -1,5 +1,6 @@ +#define DISABLE_SIGN_COMPARE_WARNINGS + #include "git-compat-util.h" -#include "alloc.h" #include "commit.h" #include "gettext.h" #include "hex.h" @@ -21,6 +22,7 @@ #include "list-objects-filter-options.h" #include "midx.h" #include "config.h" +#include "pseudo-merge.h" /* * An entry on the bitmap index, representing the bitmap for a given @@ -52,13 +54,6 @@ struct bitmap_index { struct packed_git *pack; struct multi_pack_index *midx; - /* - * Mark the first `reuse_objects` in the packfile as reused: - * they will be sent as-is without using them for repacking - * calculations - */ - uint32_t reuse_objects; - /* mmapped buffer of the whole bitmap index */ unsigned char *map; size_t map_size; /* size of the mmaped buffer */ @@ -94,6 +89,9 @@ struct bitmap_index { */ unsigned char *table_lookup; + /* This contains the pseudo-merge cache within 'map' (if found). */ + struct pseudo_merge_map pseudo_merges; + /* * Extended index. * @@ -118,6 +116,13 @@ struct bitmap_index { unsigned int version; }; +static int pseudo_merges_satisfied_nr; +static int pseudo_merges_cascades_nr; +static int existing_bitmaps_hits_nr; +static int existing_bitmaps_misses_nr; +static int roots_with_bitmaps_nr; +static int roots_without_bitmaps_nr; + static struct ewah_bitmap *lookup_stored_bitmap(struct stored_bitmap *st) { struct ewah_bitmap *parent; @@ -137,17 +142,13 @@ static struct ewah_bitmap *lookup_stored_bitmap(struct stored_bitmap *st) return composed; } -/* - * Read a bitmap from the current read position on the mmaped - * index, and increase the read position accordingly - */ -static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *index) +struct ewah_bitmap *read_bitmap(const unsigned char *map, + size_t map_size, size_t *map_pos) { struct ewah_bitmap *b = ewah_pool_new(); - ssize_t bitmap_size = ewah_read_mmap(b, - index->map + index->map_pos, - index->map_size - index->map_pos); + ssize_t bitmap_size = ewah_read_mmap(b, map + *map_pos, + map_size - *map_pos); if (bitmap_size < 0) { error(_("failed to load bitmap index (corrupted?)")); @@ -155,10 +156,20 @@ static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *index) return NULL; } - index->map_pos += bitmap_size; + *map_pos += bitmap_size; + return b; } +/* + * Read a bitmap from the current read position on the mmaped + * index, and increase the read position accordingly + */ +static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *index) +{ + return read_bitmap(index->map, index->map_size, &index->map_pos); +} + static uint32_t bitmap_num_objects(struct bitmap_index *index) { if (index->midx) @@ -166,12 +177,21 @@ static uint32_t bitmap_num_objects(struct bitmap_index *index) return index->pack->num_objects; } +static struct repository *bitmap_repo(struct bitmap_index *bitmap_git) +{ + if (bitmap_is_midx(bitmap_git)) + return bitmap_git->midx->repo; + return bitmap_git->pack->repo; +} + static int load_bitmap_header(struct bitmap_index *index) { struct bitmap_disk_header *header = (void *)index->map; - size_t header_size = sizeof(*header) - GIT_MAX_RAWSZ + the_hash_algo->rawsz; + const struct git_hash_algo *hash_algo = bitmap_repo(index)->hash_algo; - if (index->map_size < header_size + the_hash_algo->rawsz) + size_t header_size = sizeof(*header) - GIT_MAX_RAWSZ + hash_algo->rawsz; + + if (index->map_size < header_size + hash_algo->rawsz) return error(_("corrupted bitmap index (too small)")); if (memcmp(header->magic, BITMAP_IDX_SIGNATURE, sizeof(BITMAP_IDX_SIGNATURE)) != 0) @@ -185,7 +205,7 @@ static int load_bitmap_header(struct bitmap_index *index) { uint32_t flags = ntohs(header->options); size_t cache_size = st_mult(bitmap_num_objects(index), sizeof(uint32_t)); - unsigned char *index_end = index->map + index->map_size - the_hash_algo->rawsz; + unsigned char *index_end = index->map + index->map_size - hash_algo->rawsz; if ((flags & BITMAP_OPT_FULL_DAG) == 0) BUG("unsupported options for bitmap index file " @@ -207,6 +227,46 @@ static int load_bitmap_header(struct bitmap_index *index) index->table_lookup = (void *)(index_end - table_size); index_end -= table_size; } + + if (flags & BITMAP_OPT_PSEUDO_MERGES) { + unsigned char *pseudo_merge_ofs; + size_t table_size; + uint32_t i; + + if (sizeof(table_size) > index_end - index->map - header_size) + return error(_("corrupted bitmap index file (too short to fit pseudo-merge table header)")); + + table_size = get_be64(index_end - 8); + if (table_size > index_end - index->map - header_size) + return error(_("corrupted bitmap index file (too short to fit pseudo-merge table)")); + + if (git_env_bool("GIT_TEST_USE_PSEUDO_MERGES", 1)) { + const unsigned char *ext = (index_end - table_size); + + index->pseudo_merges.map = index->map; + index->pseudo_merges.map_size = index->map_size; + index->pseudo_merges.commits = ext + get_be64(index_end - 16); + index->pseudo_merges.commits_nr = get_be32(index_end - 20); + index->pseudo_merges.nr = get_be32(index_end - 24); + + if (st_add(st_mult(index->pseudo_merges.nr, + sizeof(uint64_t)), + 24) > table_size) + return error(_("corrupted bitmap index file, pseudo-merge table too short")); + + CALLOC_ARRAY(index->pseudo_merges.v, + index->pseudo_merges.nr); + + pseudo_merge_ofs = index_end - 24 - + (index->pseudo_merges.nr * sizeof(uint64_t)); + for (i = 0; i < index->pseudo_merges.nr; i++) { + index->pseudo_merges.v[i].at = get_be64(pseudo_merge_ofs); + pseudo_merge_ofs += sizeof(uint64_t); + } + } + + index_end -= table_size; + } } index->entry_count = ntohl(header->entry_count); @@ -317,9 +377,8 @@ static int load_bitmap_entries_v1(struct bitmap_index *index) char *midx_bitmap_filename(struct multi_pack_index *midx) { struct strbuf buf = STRBUF_INIT; - - get_midx_filename(&buf, midx->object_dir); - strbuf_addf(&buf, "-%s.bitmap", hash_to_hex(get_midx_checksum(midx))); + get_midx_filename_ext(midx->repo->hash_algo, &buf, midx->object_dir, + get_midx_checksum(midx), MIDX_EXT_BITMAP); return strbuf_detach(&buf, NULL); } @@ -340,7 +399,6 @@ static int open_midx_bitmap_1(struct bitmap_index *bitmap_git, char *bitmap_name = midx_bitmap_filename(midx); int fd = git_open(bitmap_name); uint32_t i; - struct packed_git *preferred; if (fd < 0) { if (errno != ENOENT) @@ -358,8 +416,8 @@ static int open_midx_bitmap_1(struct bitmap_index *bitmap_git, if (bitmap_git->pack || bitmap_git->midx) { struct strbuf buf = STRBUF_INIT; - get_midx_filename(&buf, midx->object_dir); - trace2_data_string("bitmap", the_repository, + get_midx_filename(midx->repo->hash_algo, &buf, midx->object_dir); + trace2_data_string("bitmap", bitmap_repo(bitmap_git), "ignoring extra midx bitmap file", buf.buf); close(fd); strbuf_release(&buf); @@ -376,7 +434,8 @@ static int open_midx_bitmap_1(struct bitmap_index *bitmap_git, if (load_bitmap_header(bitmap_git) < 0) goto cleanup; - if (!hasheq(get_midx_checksum(bitmap_git->midx), bitmap_git->checksum)) { + if (!hasheq(get_midx_checksum(bitmap_git->midx), bitmap_git->checksum, + bitmap_repo(bitmap_git)->hash_algo)) { error(_("checksum doesn't match in MIDX and bitmap")); goto cleanup; } @@ -387,20 +446,15 @@ static int open_midx_bitmap_1(struct bitmap_index *bitmap_git, } for (i = 0; i < bitmap_git->midx->num_packs; i++) { - if (prepare_midx_pack(the_repository, bitmap_git->midx, i)) { + if (prepare_midx_pack(bitmap_repo(bitmap_git), + bitmap_git->midx, + i)) { warning(_("could not open pack %s"), bitmap_git->midx->pack_names[i]); goto cleanup; } } - preferred = bitmap_git->midx->packs[midx_preferred_pack(bitmap_git)]; - if (!is_pack_valid(preferred)) { - warning(_("preferred pack (%s) is invalid"), - preferred->pack_name); - goto cleanup; - } - return 0; cleanup: @@ -436,8 +490,9 @@ static int open_pack_bitmap_1(struct bitmap_index *bitmap_git, struct packed_git } if (bitmap_git->pack || bitmap_git->midx) { - trace2_data_string("bitmap", the_repository, - "ignoring extra bitmap file", packfile->pack_name); + trace2_data_string("bitmap", bitmap_repo(bitmap_git), + "ignoring extra bitmap file", + packfile->pack_name); close(fd); return -1; } @@ -462,8 +517,8 @@ static int open_pack_bitmap_1(struct bitmap_index *bitmap_git, struct packed_git return -1; } - trace2_data_string("bitmap", the_repository, "opened bitmap file", - packfile->pack_name); + trace2_data_string("bitmap", bitmap_repo(bitmap_git), + "opened bitmap file", packfile->pack_name); return 0; } @@ -593,7 +648,7 @@ struct bitmap_index *prepare_bitmap_git(struct repository *r) struct bitmap_index *prepare_midx_bitmap_git(struct multi_pack_index *midx) { - struct repository *r = the_repository; + struct repository *r = midx->repo; struct bitmap_index *bitmap_git = xcalloc(1, sizeof(*bitmap_git)); if (!open_midx_bitmap_1(bitmap_git, midx) && !load_bitmap(r, bitmap_git)) @@ -879,7 +934,7 @@ static inline int bitmap_position_packfile(struct bitmap_index *bitmap_git, const struct object_id *oid) { uint32_t pos; - off_t offset = find_pack_entry_one(oid->hash, bitmap_git->pack); + off_t offset = find_pack_entry_one(oid, bitmap_git->pack); if (!offset) return -1; @@ -964,6 +1019,22 @@ static void show_commit(struct commit *commit UNUSED, { } +static unsigned apply_pseudo_merges_for_commit_1(struct bitmap_index *bitmap_git, + struct bitmap *result, + struct commit *commit, + uint32_t commit_pos) +{ + int ret; + + ret = apply_pseudo_merges_for_commit(&bitmap_git->pseudo_merges, + result, commit, commit_pos); + + if (ret) + pseudo_merges_satisfied_nr += ret; + + return ret; +} + static int add_to_include_set(struct bitmap_index *bitmap_git, struct include_data *data, struct commit *commit, @@ -979,11 +1050,19 @@ static int add_to_include_set(struct bitmap_index *bitmap_git, partial = bitmap_for_commit(bitmap_git, commit); if (partial) { + existing_bitmaps_hits_nr++; + bitmap_or_ewah(data->base, partial); return 0; } + existing_bitmaps_misses_nr++; + bitmap_set(data->base, bitmap_pos); + if (apply_pseudo_merges_for_commit_1(bitmap_git, data->base, commit, + bitmap_pos)) + return 0; + return 1; } @@ -1034,8 +1113,12 @@ static int add_commit_to_bitmap(struct bitmap_index *bitmap_git, { struct ewah_bitmap *or_with = bitmap_for_commit(bitmap_git, commit); - if (!or_with) + if (!or_with) { + existing_bitmaps_misses_nr++; return 0; + } + + existing_bitmaps_hits_nr++; if (!*base) *base = ewah_to_bitmap(or_with); @@ -1102,28 +1185,66 @@ static void show_boundary_commit(struct commit *commit, void *_data) } } -static void show_boundary_object(struct object *object, - const char *name, void *data) +static void show_boundary_object(struct object *object UNUSED, + const char *name UNUSED, + void *data UNUSED) { BUG("should not be called"); } +static unsigned cascade_pseudo_merges_1(struct bitmap_index *bitmap_git, + struct bitmap *result, + struct bitmap *roots) +{ + int ret = cascade_pseudo_merges(&bitmap_git->pseudo_merges, + result, roots); + if (ret) { + pseudo_merges_cascades_nr++; + pseudo_merges_satisfied_nr += ret; + } + + return ret; +} + static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git, struct rev_info *revs, struct object_list *roots) { struct bitmap_boundary_cb cb; struct object_list *root; + struct repository *repo; unsigned int i; unsigned int tmp_blobs, tmp_trees, tmp_tags; int any_missing = 0; + int existing_bitmaps = 0; cb.bitmap_git = bitmap_git; cb.base = bitmap_new(); object_array_init(&cb.boundary); + repo = bitmap_repo(bitmap_git); + revs->ignore_missing_links = 1; + if (bitmap_git->pseudo_merges.nr) { + struct bitmap *roots_bitmap = bitmap_new(); + struct object_list *objects = NULL; + + for (objects = roots; objects; objects = objects->next) { + struct object *object = objects->item; + int pos; + + pos = bitmap_position(bitmap_git, &object->oid); + if (pos < 0) + continue; + + bitmap_set(roots_bitmap, pos); + } + + if (!cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap)) + bitmap_free(roots_bitmap); + } + /* * OR in any existing reachability bitmaps among `roots` into * `cb.base`. @@ -1135,8 +1256,10 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git, continue; if (add_commit_to_bitmap(bitmap_git, &cb.base, - (struct commit *)object)) + (struct commit *)object)) { + existing_bitmaps = 1; continue; + } any_missing = 1; } @@ -1144,9 +1267,12 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git, if (!any_missing) goto cleanup; + if (existing_bitmaps) + cascade_pseudo_merges_1(bitmap_git, cb.base, NULL); + tmp_blobs = revs->blob_objects; tmp_trees = revs->tree_objects; - tmp_tags = revs->blob_objects; + tmp_tags = revs->tag_objects; revs->blob_objects = 0; revs->tree_objects = 0; revs->tag_objects = 0; @@ -1156,19 +1282,19 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git, * revision walk to (a) OR in any bitmaps that are UNINTERESTING * between the tips and boundary, and (b) record the boundary. */ - trace2_region_enter("pack-bitmap", "boundary-prepare", the_repository); + trace2_region_enter("pack-bitmap", "boundary-prepare", repo); if (prepare_revision_walk(revs)) die("revision walk setup failed"); - trace2_region_leave("pack-bitmap", "boundary-prepare", the_repository); + trace2_region_leave("pack-bitmap", "boundary-prepare", repo); - trace2_region_enter("pack-bitmap", "boundary-traverse", the_repository); + trace2_region_enter("pack-bitmap", "boundary-traverse", repo); revs->boundary = 1; traverse_commit_list_filtered(revs, show_boundary_commit, show_boundary_object, &cb, NULL); revs->boundary = 0; - trace2_region_leave("pack-bitmap", "boundary-traverse", the_repository); + trace2_region_leave("pack-bitmap", "boundary-traverse", repo); revs->blob_objects = tmp_blobs; revs->tree_objects = tmp_trees; @@ -1180,7 +1306,7 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git, /* * Then add the boundary commit(s) as fill-in traversal tips. */ - trace2_region_enter("pack-bitmap", "boundary-fill-in", the_repository); + trace2_region_enter("pack-bitmap", "boundary-fill-in", repo); for (i = 0; i < cb.boundary.nr; i++) { struct object *obj = cb.boundary.objects[i].item; if (bitmap_walk_contains(bitmap_git, cb.base, &obj->oid)) @@ -1190,7 +1316,7 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git, } if (revs->pending.nr) cb.base = fill_in_bitmap(bitmap_git, revs, cb.base, NULL); - trace2_region_leave("pack-bitmap", "boundary-fill-in", the_repository); + trace2_region_leave("pack-bitmap", "boundary-fill-in", repo); cleanup: object_array_clear(&cb.boundary); @@ -1199,6 +1325,44 @@ cleanup: return cb.base; } +struct ewah_bitmap *pseudo_merge_bitmap_for_commit(struct bitmap_index *bitmap_git, + struct commit *commit) +{ + struct commit_list *p; + struct bitmap *parents; + struct pseudo_merge *match = NULL; + + if (!bitmap_git->pseudo_merges.nr) + return NULL; + + parents = bitmap_new(); + + for (p = commit->parents; p; p = p->next) { + int pos = bitmap_position(bitmap_git, &p->item->object.oid); + if (pos < 0 || pos >= bitmap_num_objects(bitmap_git)) + goto done; + + bitmap_set(parents, pos); + } + + match = pseudo_merge_for_parents(&bitmap_git->pseudo_merges, + parents); + +done: + bitmap_free(parents); + if (match) + return pseudo_merge_bitmap(&bitmap_git->pseudo_merges, match); + + return NULL; +} + +static void unsatisfy_all_pseudo_merges(struct bitmap_index *bitmap_git) +{ + uint32_t i; + for (i = 0; i < bitmap_git->pseudo_merges.nr; i++) + bitmap_git->pseudo_merges.v[i].satisfied = 0; +} + static struct bitmap *find_objects(struct bitmap_index *bitmap_git, struct rev_info *revs, struct object_list *roots, @@ -1206,9 +1370,32 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git, { struct bitmap *base = NULL; int needs_walk = 0; + unsigned existing_bitmaps = 0; struct object_list *not_mapped = NULL; + unsatisfy_all_pseudo_merges(bitmap_git); + + if (bitmap_git->pseudo_merges.nr) { + struct bitmap *roots_bitmap = bitmap_new(); + struct object_list *objects = NULL; + + for (objects = roots; objects; objects = objects->next) { + struct object *object = objects->item; + int pos; + + pos = bitmap_position(bitmap_git, &object->oid); + if (pos < 0) + continue; + + bitmap_set(roots_bitmap, pos); + } + + base = bitmap_new(); + cascade_pseudo_merges_1(bitmap_git, base, roots_bitmap); + bitmap_free(roots_bitmap); + } + /* * Go through all the roots for the walk. The ones that have bitmaps * on the bitmap index will be `or`ed together to form an initial @@ -1219,11 +1406,21 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git, */ while (roots) { struct object *object = roots->item; + roots = roots->next; + if (base) { + int pos = bitmap_position(bitmap_git, &object->oid); + if (pos > 0 && bitmap_get(base, pos)) { + object->flags |= SEEN; + continue; + } + } + if (object->type == OBJ_COMMIT && add_commit_to_bitmap(bitmap_git, &base, (struct commit *)object)) { object->flags |= SEEN; + existing_bitmaps = 1; continue; } @@ -1239,6 +1436,9 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git, roots = not_mapped; + if (existing_bitmaps) + cascade_pseudo_merges_1(bitmap_git, base, NULL); + /* * Let's iterate through all the roots that don't have bitmaps to * check if we can determine them to be reachable from the existing @@ -1259,8 +1459,12 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git, object->flags &= ~UNINTERESTING; add_pending_object(revs, object, ""); needs_walk = 1; + + roots_without_bitmaps_nr++; } else { object->flags |= SEEN; + + roots_with_bitmaps_nr++; } } @@ -1280,6 +1484,8 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git, base = fill_in_bitmap(bitmap_git, revs, base, seen); } + object_list_free(¬_mapped); + return base; } @@ -1294,7 +1500,7 @@ static void show_extended_objects(struct bitmap_index *bitmap_git, for (i = 0; i < eindex->count; ++i) { struct object *obj; - if (!bitmap_get(objects, bitmap_num_objects(bitmap_git) + i)) + if (!bitmap_get(objects, st_add(bitmap_num_objects(bitmap_git), i))) continue; obj = eindex->objects[i]; @@ -1405,7 +1611,7 @@ static int in_bitmapped_pack(struct bitmap_index *bitmap_git, if (bsearch_midx(&object->oid, bitmap_git->midx, NULL)) return 1; } else { - if (find_pack_entry_one(object->oid.hash, bitmap_git->pack) > 0) + if (find_pack_entry_one(&object->oid, bitmap_git->pack) > 0) return 1; } } @@ -1473,7 +1679,7 @@ static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git, * them individually. */ for (i = 0; i < eindex->count; i++) { - uint32_t pos = i + bitmap_num_objects(bitmap_git); + size_t pos = st_add(i, bitmap_num_objects(bitmap_git)); if (eindex->objects[i]->type == type && bitmap_get(to_filter, pos) && !bitmap_get(tips, pos)) @@ -1514,7 +1720,8 @@ static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git, ofs = pack_pos_to_offset(pack, pos); } - if (packed_object_info(the_repository, pack, ofs, &oi) < 0) { + if (packed_object_info(bitmap_repo(bitmap_git), pack, ofs, + &oi) < 0) { struct object_id oid; nth_bitmap_object_oid(bitmap_git, &oid, pack_pos_to_index(pack, pos)); @@ -1523,7 +1730,8 @@ static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git, } else { struct eindex *eindex = &bitmap_git->ext_index; struct object *obj = eindex->objects[pos - bitmap_num_objects(bitmap_git)]; - if (oid_object_info_extended(the_repository, &obj->oid, &oi, 0) < 0) + if (oid_object_info_extended(bitmap_repo(bitmap_git), &obj->oid, + &oi, 0) < 0) die(_("unable to get size of %s"), oid_to_hex(&obj->oid)); } @@ -1564,7 +1772,7 @@ static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git, } for (i = 0; i < eindex->count; i++) { - uint32_t pos = i + bitmap_num_objects(bitmap_git); + size_t pos = st_add(i, bitmap_num_objects(bitmap_git)); if (eindex->objects[i]->type == OBJ_BLOB && bitmap_get(to_filter, pos) && !bitmap_get(tips, pos) && @@ -1666,6 +1874,31 @@ static int can_filter_bitmap(struct list_objects_filter_options *filter) return !filter_bitmap(NULL, NULL, NULL, filter); } + +static void filter_packed_objects_from_bitmap(struct bitmap_index *bitmap_git, + struct bitmap *result) +{ + struct eindex *eindex = &bitmap_git->ext_index; + uint32_t objects_nr; + size_t i, pos; + + objects_nr = bitmap_num_objects(bitmap_git); + pos = objects_nr / BITS_IN_EWORD; + + if (pos > result->word_alloc) + pos = result->word_alloc; + + memset(result->words, 0x00, sizeof(eword_t) * pos); + for (i = pos * BITS_IN_EWORD; i < objects_nr; i++) + bitmap_unset(result, i); + + for (i = 0; i < eindex->count; ++i) { + if (has_object_pack(bitmap_repo(bitmap_git), + &eindex->objects[i]->oid)) + bitmap_unset(result, objects_nr + i); + } +} + struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs, int filter_provided_objects) { @@ -1679,6 +1912,7 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs, struct bitmap *haves_bitmap = NULL; struct bitmap_index *bitmap_git; + struct repository *repo; /* * We can't do pathspec limiting with bitmaps, because we don't know @@ -1752,18 +1986,20 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs, if (!use_boundary_traversal) object_array_clear(&revs->pending); + repo = bitmap_repo(bitmap_git); + if (haves) { if (use_boundary_traversal) { - trace2_region_enter("pack-bitmap", "haves/boundary", the_repository); + trace2_region_enter("pack-bitmap", "haves/boundary", repo); haves_bitmap = find_boundary_objects(bitmap_git, revs, haves); - trace2_region_leave("pack-bitmap", "haves/boundary", the_repository); + trace2_region_leave("pack-bitmap", "haves/boundary", repo); } else { - trace2_region_enter("pack-bitmap", "haves/classic", the_repository); + trace2_region_enter("pack-bitmap", "haves/classic", repo); revs->ignore_missing_links = 1; haves_bitmap = find_objects(bitmap_git, revs, haves, NULL); reset_revision_walk(); revs->ignore_missing_links = 0; - trace2_region_leave("pack-bitmap", "haves/classic", the_repository); + trace2_region_leave("pack-bitmap", "haves/classic", repo); } if (!haves_bitmap) @@ -1788,12 +2024,28 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs, wants_bitmap, &revs->filter); + if (revs->unpacked) + filter_packed_objects_from_bitmap(bitmap_git, wants_bitmap); + bitmap_git->result = wants_bitmap; bitmap_git->haves = haves_bitmap; object_list_free(&wants); object_list_free(&haves); + trace2_data_intmax("bitmap", repo, "pseudo_merges_satisfied", + pseudo_merges_satisfied_nr); + trace2_data_intmax("bitmap", repo, "pseudo_merges_cascades", + pseudo_merges_cascades_nr); + trace2_data_intmax("bitmap", repo, "bitmap/hits", + existing_bitmaps_hits_nr); + trace2_data_intmax("bitmap", repo, "bitmap/misses", + existing_bitmaps_misses_nr); + trace2_data_intmax("bitmap", repo, "bitmap/roots_with_bitmap", + roots_with_bitmaps_nr); + trace2_data_intmax("bitmap", repo, "bitmap/roots_without_bitmap", + roots_without_bitmaps_nr); + return bitmap_git; cleanup: @@ -1807,49 +2059,30 @@ cleanup: * -1 means "stop trying further objects"; 0 means we may or may not have * reused, but you can keep feeding bits. */ -static int try_partial_reuse(struct packed_git *pack, - size_t pos, +static int try_partial_reuse(struct bitmap_index *bitmap_git, + struct bitmapped_pack *pack, + size_t bitmap_pos, + uint32_t pack_pos, + off_t offset, struct bitmap *reuse, struct pack_window **w_curs) { - off_t offset, delta_obj_offset; + off_t delta_obj_offset; enum object_type type; unsigned long size; - /* - * try_partial_reuse() is called either on (a) objects in the - * bitmapped pack (in the case of a single-pack bitmap) or (b) - * objects in the preferred pack of a multi-pack bitmap. - * Importantly, the latter can pretend as if only a single pack - * exists because: - * - * - The first pack->num_objects bits of a MIDX bitmap are - * reserved for the preferred pack, and - * - * - Ties due to duplicate objects are always resolved in - * favor of the preferred pack. - * - * Therefore we do not need to ever ask the MIDX for its copy of - * an object by OID, since it will always select it from the - * preferred pack. Likewise, the selected copy of the base - * object for any deltas will reside in the same pack. - * - * This means that we can reuse pos when looking up the bit in - * the reuse bitmap, too, since bits corresponding to the - * preferred pack precede all bits from other packs. - */ - - if (pos >= pack->num_objects) - return -1; /* not actually in the pack or MIDX preferred pack */ + if (pack_pos >= pack->p->num_objects) + return -1; /* not actually in the pack */ - offset = delta_obj_offset = pack_pos_to_offset(pack, pos); - type = unpack_object_header(pack, w_curs, &offset, &size); + delta_obj_offset = offset; + type = unpack_object_header(pack->p, w_curs, &offset, &size); if (type < 0) return -1; /* broken packfile, punt */ if (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA) { off_t base_offset; uint32_t base_pos; + uint32_t base_bitmap_pos; /* * Find the position of the base object so we can look it up @@ -1859,24 +2092,48 @@ static int try_partial_reuse(struct packed_git *pack, * and the normal slow path will complain about it in * more detail. */ - base_offset = get_delta_base(pack, w_curs, &offset, type, + base_offset = get_delta_base(pack->p, w_curs, &offset, type, delta_obj_offset); if (!base_offset) return 0; - if (offset_to_pack_pos(pack, base_offset, &base_pos) < 0) - return 0; - /* - * We assume delta dependencies always point backwards. This - * lets us do a single pass, and is basically always true - * due to the way OFS_DELTAs work. You would not typically - * find REF_DELTA in a bitmapped pack, since we only bitmap - * packs we write fresh, and OFS_DELTA is the default). But - * let's double check to make sure the pack wasn't written with - * odd parameters. - */ - if (base_pos >= pos) - return 0; + offset_to_pack_pos(pack->p, base_offset, &base_pos); + + if (bitmap_is_midx(bitmap_git)) { + /* + * Cross-pack deltas are rejected for now, but could + * theoretically be supported in the future. + * + * We would need to ensure that we're sending both + * halves of the delta/base pair, regardless of whether + * or not the two cross a pack boundary. If they do, + * then we must convert the delta to an REF_DELTA to + * refer back to the base in the other pack. + * */ + if (midx_pair_to_pack_pos(bitmap_git->midx, + pack->pack_int_id, + base_offset, + &base_bitmap_pos) < 0) { + return 0; + } + } else { + if (offset_to_pack_pos(pack->p, base_offset, + &base_pos) < 0) + return 0; + /* + * We assume delta dependencies always point backwards. + * This lets us do a single pass, and is basically + * always true due to the way OFS_DELTAs work. You would + * not typically find REF_DELTA in a bitmapped pack, + * since we only bitmap packs we write fresh, and + * OFS_DELTA is the default). But let's double check to + * make sure the pack wasn't written with odd + * parameters. + */ + if (base_pos >= pack_pos) + return 0; + base_bitmap_pos = pack->bitmap_pos + base_pos; + } /* * And finally, if we're not sending the base as part of our @@ -1886,77 +2143,91 @@ static int try_partial_reuse(struct packed_git *pack, * to REF_DELTA on the fly. Better to just let the normal * object_entry code path handle it. */ - if (!bitmap_get(reuse, base_pos)) + if (!bitmap_get(reuse, base_bitmap_pos)) return 0; } /* * If we got here, then the object is OK to reuse. Mark it. */ - bitmap_set(reuse, pos); + bitmap_set(reuse, bitmap_pos); return 0; } -uint32_t midx_preferred_pack(struct bitmap_index *bitmap_git) -{ - struct multi_pack_index *m = bitmap_git->midx; - if (!m) - BUG("midx_preferred_pack: requires non-empty MIDX"); - return nth_midxed_pack_int_id(m, pack_pos_to_midx(bitmap_git->midx, 0)); -} - -int reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git, - struct packed_git **packfile_out, - uint32_t *entries, - struct bitmap **reuse_out) +static void reuse_partial_packfile_from_bitmap_1(struct bitmap_index *bitmap_git, + struct bitmapped_pack *pack, + struct bitmap *reuse) { - struct repository *r = the_repository; - struct packed_git *pack; struct bitmap *result = bitmap_git->result; - struct bitmap *reuse; struct pack_window *w_curs = NULL; - size_t i = 0; - uint32_t offset; - uint32_t objects_nr; + size_t pos = pack->bitmap_pos / BITS_IN_EWORD; - assert(result); + if (!pack->bitmap_pos) { + /* + * If we're processing the first (in the case of a MIDX, the + * preferred pack) or the only (in the case of single-pack + * bitmaps) pack, then we can reuse whole words at a time. + * + * This is because we know that any deltas in this range *must* + * have their bases chosen from the same pack, since: + * + * - In the single pack case, there is no other pack to choose + * them from. + * + * - In the MIDX case, the first pack is the preferred pack, so + * all ties are broken in favor of that pack (i.e. the one + * we're currently processing). So any duplicate bases will be + * resolved in favor of the pack we're processing. + */ + while (pos < result->word_alloc && + pos < pack->bitmap_nr / BITS_IN_EWORD && + result->words[pos] == (eword_t)~0) + pos++; + memset(reuse->words, 0xFF, pos * sizeof(eword_t)); + } - load_reverse_index(r, bitmap_git); + for (; pos < result->word_alloc; pos++) { + eword_t word = result->words[pos]; + size_t offset; - if (bitmap_is_midx(bitmap_git)) - pack = bitmap_git->midx->packs[midx_preferred_pack(bitmap_git)]; - else - pack = bitmap_git->pack; - objects_nr = pack->num_objects; + for (offset = 0; offset < BITS_IN_EWORD; offset++) { + size_t bit_pos; + uint32_t pack_pos; + off_t ofs; - while (i < result->word_alloc && result->words[i] == (eword_t)~0) - i++; + if (word >> offset == 0) + break; - /* - * Don't mark objects not in the packfile or preferred pack. This bitmap - * marks objects eligible for reuse, but the pack-reuse code only - * understands how to reuse a single pack. Since the preferred pack is - * guaranteed to have all bases for its deltas (in a multi-pack bitmap), - * we use it instead of another pack. In single-pack bitmaps, the choice - * is made for us. - */ - if (i > objects_nr / BITS_IN_EWORD) - i = objects_nr / BITS_IN_EWORD; + offset += ewah_bit_ctz64(word >> offset); - reuse = bitmap_word_alloc(i); - memset(reuse->words, 0xFF, i * sizeof(eword_t)); + bit_pos = pos * BITS_IN_EWORD + offset; + if (bit_pos < pack->bitmap_pos) + continue; + if (bit_pos >= pack->bitmap_pos + pack->bitmap_nr) + goto done; - for (; i < result->word_alloc; ++i) { - eword_t word = result->words[i]; - size_t pos = (i * BITS_IN_EWORD); + if (bitmap_is_midx(bitmap_git)) { + uint32_t midx_pos; - for (offset = 0; offset < BITS_IN_EWORD; ++offset) { - if ((word >> offset) == 0) - break; + midx_pos = pack_pos_to_midx(bitmap_git->midx, bit_pos); + ofs = nth_midxed_offset(bitmap_git->midx, midx_pos); - offset += ewah_bit_ctz64(word >> offset); - if (try_partial_reuse(pack, pos + offset, - reuse, &w_curs) < 0) { + if (offset_to_pack_pos(pack->p, ofs, &pack_pos) < 0) + BUG("could not find object in pack %s " + "at offset %"PRIuMAX" in MIDX", + pack_basename(pack->p), (uintmax_t)ofs); + } else { + pack_pos = cast_size_t_to_uint32_t(st_sub(bit_pos, pack->bitmap_pos)); + if (pack_pos >= pack->p->num_objects) + BUG("advanced beyond the end of pack %s (%"PRIuMAX" > %"PRIu32")", + pack_basename(pack->p), (uintmax_t)pack_pos, + pack->p->num_objects); + + ofs = pack_pos_to_offset(pack->p, pack_pos); + } + + if (try_partial_reuse(bitmap_git, pack, bit_pos, + pack_pos, ofs, reuse, &w_curs) < 0) { /* * try_partial_reuse indicated we couldn't reuse * any bits, so there is no point in trying more @@ -1973,11 +2244,120 @@ int reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git, done: unuse_pack(&w_curs); +} - *entries = bitmap_popcount(reuse); - if (!*entries) { - bitmap_free(reuse); +static int bitmapped_pack_cmp(const void *va, const void *vb) +{ + const struct bitmapped_pack *a = va; + const struct bitmapped_pack *b = vb; + + if (a->bitmap_pos < b->bitmap_pos) return -1; + if (a->bitmap_pos > b->bitmap_pos) + return 1; + return 0; +} + +void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git, + struct bitmapped_pack **packs_out, + size_t *packs_nr_out, + struct bitmap **reuse_out, + int multi_pack_reuse) +{ + struct repository *r = bitmap_repo(bitmap_git); + struct bitmapped_pack *packs = NULL; + struct bitmap *result = bitmap_git->result; + struct bitmap *reuse; + size_t i; + size_t packs_nr = 0, packs_alloc = 0; + size_t word_alloc; + uint32_t objects_nr = 0; + + assert(result); + + load_reverse_index(r, bitmap_git); + + if (!bitmap_is_midx(bitmap_git) || !bitmap_git->midx->chunk_bitmapped_packs) + multi_pack_reuse = 0; + + if (multi_pack_reuse) { + for (i = 0; i < bitmap_git->midx->num_packs; i++) { + struct bitmapped_pack pack; + if (nth_bitmapped_pack(r, bitmap_git->midx, &pack, i) < 0) { + warning(_("unable to load pack: '%s', disabling pack-reuse"), + bitmap_git->midx->pack_names[i]); + free(packs); + return; + } + + if (!pack.bitmap_nr) + continue; + + if (is_pack_valid(pack.p)) { + ALLOC_GROW(packs, packs_nr + 1, packs_alloc); + memcpy(&packs[packs_nr++], &pack, sizeof(pack)); + } + + objects_nr += pack.p->num_objects; + } + + QSORT(packs, packs_nr, bitmapped_pack_cmp); + } else { + struct packed_git *pack; + uint32_t pack_int_id; + + if (bitmap_is_midx(bitmap_git)) { + uint32_t preferred_pack_pos; + + if (midx_preferred_pack(bitmap_git->midx, &preferred_pack_pos) < 0) { + warning(_("unable to compute preferred pack, disabling pack-reuse")); + return; + } + + pack = bitmap_git->midx->packs[preferred_pack_pos]; + pack_int_id = preferred_pack_pos; + } else { + pack = bitmap_git->pack; + /* + * Any value for 'pack_int_id' will do here. When we + * process the pack via try_partial_reuse(), we won't + * use the `pack_int_id` field since we have a non-MIDX + * bitmap. + * + * Use '-1' as a sentinel value to make it clear + * that we do not expect to read this field. + */ + pack_int_id = -1; + } + + if (is_pack_valid(pack)) { + ALLOC_GROW(packs, packs_nr + 1, packs_alloc); + packs[packs_nr].p = pack; + packs[packs_nr].pack_int_id = pack_int_id; + packs[packs_nr].bitmap_nr = pack->num_objects; + packs[packs_nr].bitmap_pos = 0; + packs[packs_nr].from_midx = bitmap_git->midx; + packs_nr++; + } + + objects_nr = pack->num_objects; + } + + if (!packs_nr) + return; + + word_alloc = objects_nr / BITS_IN_EWORD; + if (objects_nr % BITS_IN_EWORD) + word_alloc++; + reuse = bitmap_word_alloc(word_alloc); + + for (i = 0; i < packs_nr; i++) + reuse_partial_packfile_from_bitmap_1(bitmap_git, &packs[i], reuse); + + if (bitmap_is_empty(reuse)) { + free(packs); + bitmap_free(reuse); + return; } /* @@ -1985,9 +2365,9 @@ done: * need to be handled separately. */ bitmap_and_not(result, reuse); - *packfile_out = pack; + *packs_out = packs; + *packs_nr_out = packs_nr; *reuse_out = reuse; - return 0; } int bitmap_walk_contains(struct bitmap_index *bitmap_git, @@ -2038,7 +2418,8 @@ static uint32_t count_object_type(struct bitmap_index *bitmap_git, for (i = 0; i < eindex->count; ++i) { if (eindex->objects[i]->type == type && - bitmap_get(objects, bitmap_num_objects(bitmap_git) + i)) + bitmap_get(objects, + st_add(bitmap_num_objects(bitmap_git), i))) count++; } @@ -2192,7 +2573,9 @@ void test_bitmap_walk(struct rev_info *revs) tdata.trees = ewah_to_bitmap(bitmap_git->trees); tdata.blobs = ewah_to_bitmap(bitmap_git->blobs); tdata.tags = ewah_to_bitmap(bitmap_git->tags); - tdata.prg = start_progress("Verifying bitmap entries", result_popcnt); + tdata.prg = start_progress(revs->repo, + "Verifying bitmap entries", + result_popcnt); tdata.seen = 0; traverse_commit_list(revs, &test_show_commit, &test_show_object, &tdata); @@ -2267,6 +2650,132 @@ cleanup: return 0; } +static void bit_pos_to_object_id(struct bitmap_index *bitmap_git, + uint32_t bit_pos, + struct object_id *oid) +{ + uint32_t index_pos; + + if (bitmap_is_midx(bitmap_git)) + index_pos = pack_pos_to_midx(bitmap_git->midx, bit_pos); + else + index_pos = pack_pos_to_index(bitmap_git->pack, bit_pos); + + nth_bitmap_object_oid(bitmap_git, oid, index_pos); +} + +int test_bitmap_pseudo_merges(struct repository *r) +{ + struct bitmap_index *bitmap_git; + uint32_t i; + + bitmap_git = prepare_bitmap_git(r); + if (!bitmap_git || !bitmap_git->pseudo_merges.nr) + goto cleanup; + + for (i = 0; i < bitmap_git->pseudo_merges.nr; i++) { + struct pseudo_merge *merge; + struct ewah_bitmap *commits_bitmap, *merge_bitmap; + + merge = use_pseudo_merge(&bitmap_git->pseudo_merges, + &bitmap_git->pseudo_merges.v[i]); + commits_bitmap = merge->commits; + merge_bitmap = pseudo_merge_bitmap(&bitmap_git->pseudo_merges, + merge); + + printf("at=%"PRIuMAX", commits=%"PRIuMAX", objects=%"PRIuMAX"\n", + (uintmax_t)merge->at, + (uintmax_t)ewah_bitmap_popcount(commits_bitmap), + (uintmax_t)ewah_bitmap_popcount(merge_bitmap)); + } + +cleanup: + free_bitmap_index(bitmap_git); + return 0; +} + +static void dump_ewah_object_ids(struct bitmap_index *bitmap_git, + struct ewah_bitmap *bitmap) + +{ + struct ewah_iterator it; + eword_t word; + uint32_t pos = 0; + + ewah_iterator_init(&it, bitmap); + + while (ewah_iterator_next(&word, &it)) { + struct object_id oid; + uint32_t offset; + + for (offset = 0; offset < BITS_IN_EWORD; offset++) { + if (!(word >> offset)) + break; + + offset += ewah_bit_ctz64(word >> offset); + + bit_pos_to_object_id(bitmap_git, pos + offset, &oid); + printf("%s\n", oid_to_hex(&oid)); + } + pos += BITS_IN_EWORD; + } +} + +int test_bitmap_pseudo_merge_commits(struct repository *r, uint32_t n) +{ + struct bitmap_index *bitmap_git; + struct pseudo_merge *merge; + int ret = 0; + + bitmap_git = prepare_bitmap_git(r); + if (!bitmap_git || !bitmap_git->pseudo_merges.nr) + goto cleanup; + + if (n >= bitmap_git->pseudo_merges.nr) { + ret = error(_("pseudo-merge index out of range " + "(%"PRIu32" >= %"PRIuMAX")"), + n, (uintmax_t)bitmap_git->pseudo_merges.nr); + goto cleanup; + } + + merge = use_pseudo_merge(&bitmap_git->pseudo_merges, + &bitmap_git->pseudo_merges.v[n]); + dump_ewah_object_ids(bitmap_git, merge->commits); + +cleanup: + free_bitmap_index(bitmap_git); + return ret; +} + +int test_bitmap_pseudo_merge_objects(struct repository *r, uint32_t n) +{ + struct bitmap_index *bitmap_git; + struct pseudo_merge *merge; + int ret = 0; + + bitmap_git = prepare_bitmap_git(r); + if (!bitmap_git || !bitmap_git->pseudo_merges.nr) + goto cleanup; + + if (n >= bitmap_git->pseudo_merges.nr) { + ret = error(_("pseudo-merge index out of range " + "(%"PRIu32" >= %"PRIuMAX")"), + n, (uintmax_t)bitmap_git->pseudo_merges.nr); + goto cleanup; + } + + merge = use_pseudo_merge(&bitmap_git->pseudo_merges, + &bitmap_git->pseudo_merges.v[n]); + + dump_ewah_object_ids(bitmap_git, + pseudo_merge_bitmap(&bitmap_git->pseudo_merges, + merge)); + +cleanup: + free_bitmap_index(bitmap_git); + return ret; +} + int rebuild_bitmap(const uint32_t *reposition, struct ewah_bitmap *source, struct bitmap *dest) @@ -2301,7 +2810,7 @@ int rebuild_bitmap(const uint32_t *reposition, uint32_t *create_bitmap_mapping(struct bitmap_index *bitmap_git, struct packing_data *mapping) { - struct repository *r = the_repository; + struct repository *r = bitmap_repo(bitmap_git); uint32_t i, num_objects; uint32_t *reposition; @@ -2373,6 +2882,7 @@ void free_bitmap_index(struct bitmap_index *b) */ close_midx_revindex(b->midx); } + free_pseudo_merge_map(&b->pseudo_merges); free(b); } @@ -2452,10 +2962,12 @@ static off_t get_disk_usage_for_extended(struct bitmap_index *bitmap_git) for (i = 0; i < eindex->count; i++) { struct object *obj = eindex->objects[i]; - if (!bitmap_get(result, bitmap_num_objects(bitmap_git) + i)) + if (!bitmap_get(result, + st_add(bitmap_num_objects(bitmap_git), i))) continue; - if (oid_object_info_extended(the_repository, &obj->oid, &oi, 0) < 0) + if (oid_object_info_extended(bitmap_repo(bitmap_git), &obj->oid, + &oi, 0) < 0) die(_("unable to get disk usage of '%s'"), oid_to_hex(&obj->oid)); |