7 #include "list-objects.h"
9 #include "pack-bitmap.h"
10 #include "pack-revindex.h"
11 #include "pack-objects.h"
13 #include "repository.h"
14 #include "object-store.h"
17 * An entry on the bitmap index, representing the bitmap for a given
20 struct stored_bitmap {
22 struct ewah_bitmap *root;
23 struct stored_bitmap *xor;
28 * The active bitmap index for a repository. By design, repositories only have
29 * a single bitmap index available (the index for the biggest packfile in
30 * the repository), since bitmap indexes need full closure.
32 * If there is more than one bitmap index available (e.g. because of alternates),
33 * the active bitmap index is the largest one.
36 /* Packfile to which this bitmap index belongs to */
37 struct packed_git *pack;
40 * Mark the first `reuse_objects` in the packfile as reused:
41 * they will be sent as-is without using them for repacking
44 uint32_t reuse_objects;
46 /* mmapped buffer of the whole bitmap index */
48 size_t map_size; /* size of the mmaped buffer */
49 size_t map_pos; /* current position when loading the index */
54 * Each bitmap marks which objects in the packfile are of the given
55 * type. This provides type information when yielding the objects from
56 * the packfile during a walk, which allows for better delta bases.
58 struct ewah_bitmap *commits;
59 struct ewah_bitmap *trees;
60 struct ewah_bitmap *blobs;
61 struct ewah_bitmap *tags;
63 /* Map from object ID -> `stored_bitmap` for all the bitmapped commits */
64 kh_oid_map_t *bitmaps;
66 /* Number of bitmapped commits */
69 /* If not NULL, this is a name-hash cache pointing into map. */
75 * When trying to perform bitmap operations with objects that are not
76 * packed in `pack`, these objects are added to this "fake index" and
77 * are assumed to appear at the end of the packfile for all operations
80 struct object **objects;
82 uint32_t count, alloc;
83 kh_oid_pos_t *positions;
86 /* Bitmap result of the last performed walk */
87 struct bitmap *result;
89 /* "have" bitmap from the last performed walk */
92 /* Version of the bitmap index */
96 static struct ewah_bitmap *lookup_stored_bitmap(struct stored_bitmap *st)
98 struct ewah_bitmap *parent;
99 struct ewah_bitmap *composed;
104 composed = ewah_pool_new();
105 parent = lookup_stored_bitmap(st->xor);
106 ewah_xor(st->root, parent, composed);
108 ewah_pool_free(st->root);
116 * Read a bitmap from the current read position on the mmaped
117 * index, and increase the read position accordingly
119 static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *index)
121 struct ewah_bitmap *b = ewah_pool_new();
123 ssize_t bitmap_size = ewah_read_mmap(b,
124 index->map + index->map_pos,
125 index->map_size - index->map_pos);
127 if (bitmap_size < 0) {
128 error("Failed to load bitmap index (corrupted?)");
133 index->map_pos += bitmap_size;
137 static int load_bitmap_header(struct bitmap_index *index)
139 struct bitmap_disk_header *header = (void *)index->map;
141 if (index->map_size < sizeof(*header) + the_hash_algo->rawsz)
142 return error("Corrupted bitmap index (missing header data)");
144 if (memcmp(header->magic, BITMAP_IDX_SIGNATURE, sizeof(BITMAP_IDX_SIGNATURE)) != 0)
145 return error("Corrupted bitmap index file (wrong header)");
147 index->version = ntohs(header->version);
148 if (index->version != 1)
149 return error("Unsupported version for bitmap index file (%d)", index->version);
151 /* Parse known bitmap format options */
153 uint32_t flags = ntohs(header->options);
155 if ((flags & BITMAP_OPT_FULL_DAG) == 0)
156 return error("Unsupported options for bitmap index file "
157 "(Git requires BITMAP_OPT_FULL_DAG)");
159 if (flags & BITMAP_OPT_HASH_CACHE) {
160 unsigned char *end = index->map + index->map_size - the_hash_algo->rawsz;
161 index->hashes = ((uint32_t *)end) - index->pack->num_objects;
165 index->entry_count = ntohl(header->entry_count);
166 index->map_pos += sizeof(*header) - GIT_MAX_RAWSZ + the_hash_algo->rawsz;
170 static struct stored_bitmap *store_bitmap(struct bitmap_index *index,
171 struct ewah_bitmap *root,
172 const unsigned char *hash,
173 struct stored_bitmap *xor_with,
176 struct stored_bitmap *stored;
180 stored = xmalloc(sizeof(struct stored_bitmap));
182 stored->xor = xor_with;
183 stored->flags = flags;
184 oidread(&stored->oid, hash);
186 hash_pos = kh_put_oid_map(index->bitmaps, stored->oid, &ret);
188 /* a 0 return code means the insertion succeeded with no changes,
189 * because the SHA1 already existed on the map. this is bad, there
190 * shouldn't be duplicated commits in the index */
192 error("Duplicate entry in bitmap index: %s", hash_to_hex(hash));
196 kh_value(index->bitmaps, hash_pos) = stored;
200 static inline uint32_t read_be32(const unsigned char *buffer, size_t *pos)
202 uint32_t result = get_be32(buffer + *pos);
203 (*pos) += sizeof(result);
207 static inline uint8_t read_u8(const unsigned char *buffer, size_t *pos)
209 return buffer[(*pos)++];
212 #define MAX_XOR_OFFSET 160
214 static int load_bitmap_entries_v1(struct bitmap_index *index)
217 struct stored_bitmap *recent_bitmaps[MAX_XOR_OFFSET] = { NULL };
219 for (i = 0; i < index->entry_count; ++i) {
220 int xor_offset, flags;
221 struct ewah_bitmap *bitmap = NULL;
222 struct stored_bitmap *xor_bitmap = NULL;
223 uint32_t commit_idx_pos;
224 const unsigned char *sha1;
226 commit_idx_pos = read_be32(index->map, &index->map_pos);
227 xor_offset = read_u8(index->map, &index->map_pos);
228 flags = read_u8(index->map, &index->map_pos);
230 sha1 = nth_packed_object_sha1(index->pack, commit_idx_pos);
232 bitmap = read_bitmap_1(index);
236 if (xor_offset > MAX_XOR_OFFSET || xor_offset > i)
237 return error("Corrupted bitmap pack index");
239 if (xor_offset > 0) {
240 xor_bitmap = recent_bitmaps[(i - xor_offset) % MAX_XOR_OFFSET];
242 if (xor_bitmap == NULL)
243 return error("Invalid XOR offset in bitmap pack index");
246 recent_bitmaps[i % MAX_XOR_OFFSET] = store_bitmap(
247 index, bitmap, sha1, xor_bitmap, flags);
253 static char *pack_bitmap_filename(struct packed_git *p)
257 if (!strip_suffix(p->pack_name, ".pack", &len))
258 BUG("pack_name does not end in .pack");
259 return xstrfmt("%.*s.bitmap", (int)len, p->pack_name);
262 static int open_pack_bitmap_1(struct bitmap_index *bitmap_git, struct packed_git *packfile)
268 if (open_pack_index(packfile))
271 idx_name = pack_bitmap_filename(packfile);
272 fd = git_open(idx_name);
278 if (fstat(fd, &st)) {
283 if (bitmap_git->pack) {
284 warning("ignoring extra bitmap file: %s", packfile->pack_name);
289 bitmap_git->pack = packfile;
290 bitmap_git->map_size = xsize_t(st.st_size);
291 bitmap_git->map = xmmap(NULL, bitmap_git->map_size, PROT_READ, MAP_PRIVATE, fd, 0);
292 bitmap_git->map_pos = 0;
295 if (load_bitmap_header(bitmap_git) < 0) {
296 munmap(bitmap_git->map, bitmap_git->map_size);
297 bitmap_git->map = NULL;
298 bitmap_git->map_size = 0;
305 static int load_pack_bitmap(struct bitmap_index *bitmap_git)
307 assert(bitmap_git->map);
309 bitmap_git->bitmaps = kh_init_oid_map();
310 bitmap_git->ext_index.positions = kh_init_oid_pos();
311 if (load_pack_revindex(bitmap_git->pack))
314 if (!(bitmap_git->commits = read_bitmap_1(bitmap_git)) ||
315 !(bitmap_git->trees = read_bitmap_1(bitmap_git)) ||
316 !(bitmap_git->blobs = read_bitmap_1(bitmap_git)) ||
317 !(bitmap_git->tags = read_bitmap_1(bitmap_git)))
320 if (load_bitmap_entries_v1(bitmap_git) < 0)
326 munmap(bitmap_git->map, bitmap_git->map_size);
327 bitmap_git->map = NULL;
328 bitmap_git->map_size = 0;
330 kh_destroy_oid_map(bitmap_git->bitmaps);
331 bitmap_git->bitmaps = NULL;
333 kh_destroy_oid_pos(bitmap_git->ext_index.positions);
334 bitmap_git->ext_index.positions = NULL;
339 static int open_pack_bitmap(struct repository *r,
340 struct bitmap_index *bitmap_git)
342 struct packed_git *p;
345 assert(!bitmap_git->map);
347 for (p = get_all_packs(r); p; p = p->next) {
348 if (open_pack_bitmap_1(bitmap_git, p) == 0)
355 struct bitmap_index *prepare_bitmap_git(struct repository *r)
357 struct bitmap_index *bitmap_git = xcalloc(1, sizeof(*bitmap_git));
359 if (!open_pack_bitmap(r, bitmap_git) && !load_pack_bitmap(bitmap_git))
362 free_bitmap_index(bitmap_git);
366 struct include_data {
367 struct bitmap_index *bitmap_git;
372 static inline int bitmap_position_extended(struct bitmap_index *bitmap_git,
373 const struct object_id *oid)
375 kh_oid_pos_t *positions = bitmap_git->ext_index.positions;
376 khiter_t pos = kh_get_oid_pos(positions, *oid);
378 if (pos < kh_end(positions)) {
379 int bitmap_pos = kh_value(positions, pos);
380 return bitmap_pos + bitmap_git->pack->num_objects;
386 static inline int bitmap_position_packfile(struct bitmap_index *bitmap_git,
387 const struct object_id *oid)
389 off_t offset = find_pack_entry_one(oid->hash, bitmap_git->pack);
393 return find_revindex_position(bitmap_git->pack, offset);
396 static int bitmap_position(struct bitmap_index *bitmap_git,
397 const struct object_id *oid)
399 int pos = bitmap_position_packfile(bitmap_git, oid);
400 return (pos >= 0) ? pos : bitmap_position_extended(bitmap_git, oid);
403 static int ext_index_add_object(struct bitmap_index *bitmap_git,
404 struct object *object, const char *name)
406 struct eindex *eindex = &bitmap_git->ext_index;
412 hash_pos = kh_put_oid_pos(eindex->positions, object->oid, &hash_ret);
414 if (eindex->count >= eindex->alloc) {
415 eindex->alloc = (eindex->alloc + 16) * 3 / 2;
416 REALLOC_ARRAY(eindex->objects, eindex->alloc);
417 REALLOC_ARRAY(eindex->hashes, eindex->alloc);
420 bitmap_pos = eindex->count;
421 eindex->objects[eindex->count] = object;
422 eindex->hashes[eindex->count] = pack_name_hash(name);
423 kh_value(eindex->positions, hash_pos) = bitmap_pos;
426 bitmap_pos = kh_value(eindex->positions, hash_pos);
429 return bitmap_pos + bitmap_git->pack->num_objects;
432 struct bitmap_show_data {
433 struct bitmap_index *bitmap_git;
437 static void show_object(struct object *object, const char *name, void *data_)
439 struct bitmap_show_data *data = data_;
442 bitmap_pos = bitmap_position(data->bitmap_git, &object->oid);
445 bitmap_pos = ext_index_add_object(data->bitmap_git, object,
448 bitmap_set(data->base, bitmap_pos);
451 static void show_commit(struct commit *commit, void *data)
455 static int add_to_include_set(struct bitmap_index *bitmap_git,
456 struct include_data *data,
457 const struct object_id *oid,
462 if (data->seen && bitmap_get(data->seen, bitmap_pos))
465 if (bitmap_get(data->base, bitmap_pos))
468 hash_pos = kh_get_oid_map(bitmap_git->bitmaps, *oid);
469 if (hash_pos < kh_end(bitmap_git->bitmaps)) {
470 struct stored_bitmap *st = kh_value(bitmap_git->bitmaps, hash_pos);
471 bitmap_or_ewah(data->base, lookup_stored_bitmap(st));
475 bitmap_set(data->base, bitmap_pos);
479 static int should_include(struct commit *commit, void *_data)
481 struct include_data *data = _data;
484 bitmap_pos = bitmap_position(data->bitmap_git, &commit->object.oid);
486 bitmap_pos = ext_index_add_object(data->bitmap_git,
487 (struct object *)commit,
490 if (!add_to_include_set(data->bitmap_git, data, &commit->object.oid,
492 struct commit_list *parent = commit->parents;
495 parent->item->object.flags |= SEEN;
496 parent = parent->next;
505 static struct bitmap *find_objects(struct bitmap_index *bitmap_git,
506 struct rev_info *revs,
507 struct object_list *roots,
510 struct bitmap *base = NULL;
513 struct object_list *not_mapped = NULL;
516 * Go through all the roots for the walk. The ones that have bitmaps
517 * on the bitmap index will be `or`ed together to form an initial
518 * global reachability analysis.
520 * The ones without bitmaps in the index will be stored in the
521 * `not_mapped_list` for further processing.
524 struct object *object = roots->item;
527 if (object->type == OBJ_COMMIT) {
528 khiter_t pos = kh_get_oid_map(bitmap_git->bitmaps, object->oid);
530 if (pos < kh_end(bitmap_git->bitmaps)) {
531 struct stored_bitmap *st = kh_value(bitmap_git->bitmaps, pos);
532 struct ewah_bitmap *or_with = lookup_stored_bitmap(st);
535 base = ewah_to_bitmap(or_with);
537 bitmap_or_ewah(base, or_with);
539 object->flags |= SEEN;
544 object_list_insert(object, ¬_mapped);
548 * Best case scenario: We found bitmaps for all the roots,
549 * so the resulting `or` bitmap has the full reachability analysis
551 if (not_mapped == NULL)
557 * Let's iterate through all the roots that don't have bitmaps to
558 * check if we can determine them to be reachable from the existing
561 * If we cannot find them in the existing global bitmap, we'll need
562 * to push them to an actual walk and run it until we can confirm
566 struct object *object = roots->item;
570 pos = bitmap_position(bitmap_git, &object->oid);
572 if (pos < 0 || base == NULL || !bitmap_get(base, pos)) {
573 object->flags &= ~UNINTERESTING;
574 add_pending_object(revs, object, "");
577 object->flags |= SEEN;
582 struct include_data incdata;
583 struct bitmap_show_data show_data;
588 incdata.bitmap_git = bitmap_git;
592 revs->include_check = should_include;
593 revs->include_check_data = &incdata;
595 if (prepare_revision_walk(revs))
596 die("revision walk setup failed");
598 show_data.bitmap_git = bitmap_git;
599 show_data.base = base;
601 traverse_commit_list(revs, show_commit, show_object,
608 static void show_extended_objects(struct bitmap_index *bitmap_git,
609 show_reachable_fn show_reach)
611 struct bitmap *objects = bitmap_git->result;
612 struct eindex *eindex = &bitmap_git->ext_index;
615 for (i = 0; i < eindex->count; ++i) {
618 if (!bitmap_get(objects, bitmap_git->pack->num_objects + i))
621 obj = eindex->objects[i];
622 show_reach(&obj->oid, obj->type, 0, eindex->hashes[i], NULL, 0);
626 static void show_objects_for_type(
627 struct bitmap_index *bitmap_git,
628 struct ewah_bitmap *type_filter,
629 enum object_type object_type,
630 show_reachable_fn show_reach)
632 size_t pos = 0, i = 0;
635 struct ewah_iterator it;
638 struct bitmap *objects = bitmap_git->result;
640 if (bitmap_git->reuse_objects == bitmap_git->pack->num_objects)
643 ewah_iterator_init(&it, type_filter);
645 while (i < objects->word_alloc && ewah_iterator_next(&filter, &it)) {
646 eword_t word = objects->words[i] & filter;
648 for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
649 struct object_id oid;
650 struct revindex_entry *entry;
653 if ((word >> offset) == 0)
656 offset += ewah_bit_ctz64(word >> offset);
658 if (pos + offset < bitmap_git->reuse_objects)
661 entry = &bitmap_git->pack->revindex[pos + offset];
662 nth_packed_object_oid(&oid, bitmap_git->pack, entry->nr);
664 if (bitmap_git->hashes)
665 hash = get_be32(bitmap_git->hashes + entry->nr);
667 show_reach(&oid, object_type, 0, hash, bitmap_git->pack, entry->offset);
670 pos += BITS_IN_EWORD;
675 static int in_bitmapped_pack(struct bitmap_index *bitmap_git,
676 struct object_list *roots)
679 struct object *object = roots->item;
682 if (find_pack_entry_one(object->oid.hash, bitmap_git->pack) > 0)
689 struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)
693 struct object_list *wants = NULL;
694 struct object_list *haves = NULL;
696 struct bitmap *wants_bitmap = NULL;
697 struct bitmap *haves_bitmap = NULL;
699 struct bitmap_index *bitmap_git = xcalloc(1, sizeof(*bitmap_git));
700 /* try to open a bitmapped pack, but don't parse it yet
701 * because we may not need to use it */
702 if (open_pack_bitmap(revs->repo, bitmap_git) < 0)
705 for (i = 0; i < revs->pending.nr; ++i) {
706 struct object *object = revs->pending.objects[i].item;
708 if (object->type == OBJ_NONE)
709 parse_object_or_die(&object->oid, NULL);
711 while (object->type == OBJ_TAG) {
712 struct tag *tag = (struct tag *) object;
714 if (object->flags & UNINTERESTING)
715 object_list_insert(object, &haves);
717 object_list_insert(object, &wants);
721 object = parse_object_or_die(&tag->tagged->oid, NULL);
724 if (object->flags & UNINTERESTING)
725 object_list_insert(object, &haves);
727 object_list_insert(object, &wants);
731 * if we have a HAVES list, but none of those haves is contained
732 * in the packfile that has a bitmap, we don't have anything to
735 if (haves && !in_bitmapped_pack(bitmap_git, haves))
738 /* if we don't want anything, we're done here */
743 * now we're going to use bitmaps, so load the actual bitmap entries
744 * from disk. this is the point of no return; after this the rev_list
745 * becomes invalidated and we must perform the revwalk through bitmaps
747 if (load_pack_bitmap(bitmap_git) < 0)
750 object_array_clear(&revs->pending);
753 revs->ignore_missing_links = 1;
754 haves_bitmap = find_objects(bitmap_git, revs, haves, NULL);
755 reset_revision_walk();
756 revs->ignore_missing_links = 0;
758 if (haves_bitmap == NULL)
759 BUG("failed to perform bitmap walk");
762 wants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap);
765 BUG("failed to perform bitmap walk");
768 bitmap_and_not(wants_bitmap, haves_bitmap);
770 bitmap_git->result = wants_bitmap;
771 bitmap_git->haves = haves_bitmap;
776 free_bitmap_index(bitmap_git);
780 static void try_partial_reuse(struct bitmap_index *bitmap_git,
782 struct bitmap *reuse,
783 struct pack_window **w_curs)
785 struct revindex_entry *revidx;
787 enum object_type type;
790 if (pos >= bitmap_git->pack->num_objects)
791 return; /* not actually in the pack */
793 revidx = &bitmap_git->pack->revindex[pos];
794 offset = revidx->offset;
795 type = unpack_object_header(bitmap_git->pack, w_curs, &offset, &size);
797 return; /* broken packfile, punt */
799 if (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA) {
804 * Find the position of the base object so we can look it up
805 * in our bitmaps. If we can't come up with an offset, or if
806 * that offset is not in the revidx, the pack is corrupt.
807 * There's nothing we can do, so just punt on this object,
808 * and the normal slow path will complain about it in
811 base_offset = get_delta_base(bitmap_git->pack, w_curs,
812 &offset, type, revidx->offset);
815 base_pos = find_revindex_position(bitmap_git->pack, base_offset);
820 * We assume delta dependencies always point backwards. This
821 * lets us do a single pass, and is basically always true
822 * due to the way OFS_DELTAs work. You would not typically
823 * find REF_DELTA in a bitmapped pack, since we only bitmap
824 * packs we write fresh, and OFS_DELTA is the default). But
825 * let's double check to make sure the pack wasn't written with
832 * And finally, if we're not sending the base as part of our
833 * reuse chunk, then don't send this object either. The base
834 * would come after us, along with other objects not
835 * necessarily in the pack, which means we'd need to convert
836 * to REF_DELTA on the fly. Better to just let the normal
837 * object_entry code path handle it.
839 if (!bitmap_get(reuse, base_pos))
844 * If we got here, then the object is OK to reuse. Mark it.
846 bitmap_set(reuse, pos);
849 int reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,
850 struct packed_git **packfile_out,
852 struct bitmap **reuse_out)
854 struct bitmap *result = bitmap_git->result;
855 struct bitmap *reuse;
856 struct pack_window *w_curs = NULL;
862 while (i < result->word_alloc && result->words[i] == (eword_t)~0)
865 /* Don't mark objects not in the packfile */
866 if (i > bitmap_git->pack->num_objects / BITS_IN_EWORD)
867 i = bitmap_git->pack->num_objects / BITS_IN_EWORD;
869 reuse = bitmap_word_alloc(i);
870 memset(reuse->words, 0xFF, i * sizeof(eword_t));
872 for (; i < result->word_alloc; ++i) {
873 eword_t word = result->words[i];
874 size_t pos = (i * BITS_IN_EWORD);
876 for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
877 if ((word >> offset) == 0)
880 offset += ewah_bit_ctz64(word >> offset);
881 try_partial_reuse(bitmap_git, pos + offset, reuse, &w_curs);
887 *entries = bitmap_popcount(reuse);
894 * Drop any reused objects from the result, since they will not
895 * need to be handled separately.
897 bitmap_and_not(result, reuse);
898 *packfile_out = bitmap_git->pack;
903 int bitmap_walk_contains(struct bitmap_index *bitmap_git,
904 struct bitmap *bitmap, const struct object_id *oid)
911 idx = bitmap_position(bitmap_git, oid);
912 return idx >= 0 && bitmap_get(bitmap, idx);
915 void traverse_bitmap_commit_list(struct bitmap_index *bitmap_git,
916 show_reachable_fn show_reachable)
918 assert(bitmap_git->result);
920 show_objects_for_type(bitmap_git, bitmap_git->commits,
921 OBJ_COMMIT, show_reachable);
922 show_objects_for_type(bitmap_git, bitmap_git->trees,
923 OBJ_TREE, show_reachable);
924 show_objects_for_type(bitmap_git, bitmap_git->blobs,
925 OBJ_BLOB, show_reachable);
926 show_objects_for_type(bitmap_git, bitmap_git->tags,
927 OBJ_TAG, show_reachable);
929 show_extended_objects(bitmap_git, show_reachable);
932 static uint32_t count_object_type(struct bitmap_index *bitmap_git,
933 enum object_type type)
935 struct bitmap *objects = bitmap_git->result;
936 struct eindex *eindex = &bitmap_git->ext_index;
938 uint32_t i = 0, count = 0;
939 struct ewah_iterator it;
944 ewah_iterator_init(&it, bitmap_git->commits);
948 ewah_iterator_init(&it, bitmap_git->trees);
952 ewah_iterator_init(&it, bitmap_git->blobs);
956 ewah_iterator_init(&it, bitmap_git->tags);
963 while (i < objects->word_alloc && ewah_iterator_next(&filter, &it)) {
964 eword_t word = objects->words[i++] & filter;
965 count += ewah_bit_popcount64(word);
968 for (i = 0; i < eindex->count; ++i) {
969 if (eindex->objects[i]->type == type &&
970 bitmap_get(objects, bitmap_git->pack->num_objects + i))
977 void count_bitmap_commit_list(struct bitmap_index *bitmap_git,
978 uint32_t *commits, uint32_t *trees,
979 uint32_t *blobs, uint32_t *tags)
981 assert(bitmap_git->result);
984 *commits = count_object_type(bitmap_git, OBJ_COMMIT);
987 *trees = count_object_type(bitmap_git, OBJ_TREE);
990 *blobs = count_object_type(bitmap_git, OBJ_BLOB);
993 *tags = count_object_type(bitmap_git, OBJ_TAG);
996 struct bitmap_test_data {
997 struct bitmap_index *bitmap_git;
999 struct progress *prg;
1003 static void test_show_object(struct object *object, const char *name,
1006 struct bitmap_test_data *tdata = data;
1009 bitmap_pos = bitmap_position(tdata->bitmap_git, &object->oid);
1011 die("Object not in bitmap: %s\n", oid_to_hex(&object->oid));
1013 bitmap_set(tdata->base, bitmap_pos);
1014 display_progress(tdata->prg, ++tdata->seen);
1017 static void test_show_commit(struct commit *commit, void *data)
1019 struct bitmap_test_data *tdata = data;
1022 bitmap_pos = bitmap_position(tdata->bitmap_git,
1023 &commit->object.oid);
1025 die("Object not in bitmap: %s\n", oid_to_hex(&commit->object.oid));
1027 bitmap_set(tdata->base, bitmap_pos);
1028 display_progress(tdata->prg, ++tdata->seen);
1031 void test_bitmap_walk(struct rev_info *revs)
1033 struct object *root;
1034 struct bitmap *result = NULL;
1036 size_t result_popcnt;
1037 struct bitmap_test_data tdata;
1038 struct bitmap_index *bitmap_git;
1040 if (!(bitmap_git = prepare_bitmap_git(revs->repo)))
1041 die("failed to load bitmap indexes");
1043 if (revs->pending.nr != 1)
1044 die("you must specify exactly one commit to test");
1046 fprintf(stderr, "Bitmap v%d test (%d entries loaded)\n",
1047 bitmap_git->version, bitmap_git->entry_count);
1049 root = revs->pending.objects[0].item;
1050 pos = kh_get_oid_map(bitmap_git->bitmaps, root->oid);
1052 if (pos < kh_end(bitmap_git->bitmaps)) {
1053 struct stored_bitmap *st = kh_value(bitmap_git->bitmaps, pos);
1054 struct ewah_bitmap *bm = lookup_stored_bitmap(st);
1056 fprintf(stderr, "Found bitmap for %s. %d bits / %08x checksum\n",
1057 oid_to_hex(&root->oid), (int)bm->bit_size, ewah_checksum(bm));
1059 result = ewah_to_bitmap(bm);
1063 die("Commit %s doesn't have an indexed bitmap", oid_to_hex(&root->oid));
1065 revs->tag_objects = 1;
1066 revs->tree_objects = 1;
1067 revs->blob_objects = 1;
1069 result_popcnt = bitmap_popcount(result);
1071 if (prepare_revision_walk(revs))
1072 die("revision walk setup failed");
1074 tdata.bitmap_git = bitmap_git;
1075 tdata.base = bitmap_new();
1076 tdata.prg = start_progress("Verifying bitmap entries", result_popcnt);
1079 traverse_commit_list(revs, &test_show_commit, &test_show_object, &tdata);
1081 stop_progress(&tdata.prg);
1083 if (bitmap_equals(result, tdata.base))
1084 fprintf(stderr, "OK!\n");
1086 fprintf(stderr, "Mismatch!\n");
1088 free_bitmap_index(bitmap_git);
1091 static int rebuild_bitmap(uint32_t *reposition,
1092 struct ewah_bitmap *source,
1093 struct bitmap *dest)
1096 struct ewah_iterator it;
1099 ewah_iterator_init(&it, source);
1101 while (ewah_iterator_next(&word, &it)) {
1102 uint32_t offset, bit_pos;
1104 for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
1105 if ((word >> offset) == 0)
1108 offset += ewah_bit_ctz64(word >> offset);
1110 bit_pos = reposition[pos + offset];
1112 bitmap_set(dest, bit_pos - 1);
1113 else /* can't reuse, we don't have the object */
1117 pos += BITS_IN_EWORD;
1122 int rebuild_existing_bitmaps(struct bitmap_index *bitmap_git,
1123 struct packing_data *mapping,
1124 kh_oid_map_t *reused_bitmaps,
1127 uint32_t i, num_objects;
1128 uint32_t *reposition;
1129 struct bitmap *rebuild;
1130 struct stored_bitmap *stored;
1131 struct progress *progress = NULL;
1136 num_objects = bitmap_git->pack->num_objects;
1137 reposition = xcalloc(num_objects, sizeof(uint32_t));
1139 for (i = 0; i < num_objects; ++i) {
1140 struct object_id oid;
1141 struct revindex_entry *entry;
1142 struct object_entry *oe;
1144 entry = &bitmap_git->pack->revindex[i];
1145 nth_packed_object_oid(&oid, bitmap_git->pack, entry->nr);
1146 oe = packlist_find(mapping, &oid, NULL);
1149 reposition[i] = oe_in_pack_pos(mapping, oe) + 1;
1152 rebuild = bitmap_new();
1156 progress = start_progress("Reusing bitmaps", 0);
1158 kh_foreach_value(bitmap_git->bitmaps, stored, {
1159 if (stored->flags & BITMAP_FLAG_REUSE) {
1160 if (!rebuild_bitmap(reposition,
1161 lookup_stored_bitmap(stored),
1163 hash_pos = kh_put_oid_map(reused_bitmaps,
1166 kh_value(reused_bitmaps, hash_pos) =
1167 bitmap_to_ewah(rebuild);
1169 bitmap_reset(rebuild);
1170 display_progress(progress, ++i);
1174 stop_progress(&progress);
1177 bitmap_free(rebuild);
1181 void free_bitmap_index(struct bitmap_index *b)
1187 munmap(b->map, b->map_size);
1188 ewah_pool_free(b->commits);
1189 ewah_pool_free(b->trees);
1190 ewah_pool_free(b->blobs);
1191 ewah_pool_free(b->tags);
1192 kh_destroy_oid_map(b->bitmaps);
1193 free(b->ext_index.objects);
1194 free(b->ext_index.hashes);
1195 bitmap_free(b->result);
1196 bitmap_free(b->haves);
1200 int bitmap_has_oid_in_uninteresting(struct bitmap_index *bitmap_git,
1201 const struct object_id *oid)
1203 return bitmap_git &&
1204 bitmap_walk_contains(bitmap_git, bitmap_git->haves, oid);