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"
15 #include "list-objects-filter-options.h"
18 * An entry on the bitmap index, representing the bitmap for a given
21 struct stored_bitmap {
23 struct ewah_bitmap *root;
24 struct stored_bitmap *xor;
29 * The active bitmap index for a repository. By design, repositories only have
30 * a single bitmap index available (the index for the biggest packfile in
31 * the repository), since bitmap indexes need full closure.
33 * If there is more than one bitmap index available (e.g. because of alternates),
34 * the active bitmap index is the largest one.
37 /* Packfile to which this bitmap index belongs to */
38 struct packed_git *pack;
41 * Mark the first `reuse_objects` in the packfile as reused:
42 * they will be sent as-is without using them for repacking
45 uint32_t reuse_objects;
47 /* mmapped buffer of the whole bitmap index */
49 size_t map_size; /* size of the mmaped buffer */
50 size_t map_pos; /* current position when loading the index */
55 * Each bitmap marks which objects in the packfile are of the given
56 * type. This provides type information when yielding the objects from
57 * the packfile during a walk, which allows for better delta bases.
59 struct ewah_bitmap *commits;
60 struct ewah_bitmap *trees;
61 struct ewah_bitmap *blobs;
62 struct ewah_bitmap *tags;
64 /* Map from object ID -> `stored_bitmap` for all the bitmapped commits */
65 kh_oid_map_t *bitmaps;
67 /* Number of bitmapped commits */
70 /* If not NULL, this is a name-hash cache pointing into map. */
76 * When trying to perform bitmap operations with objects that are not
77 * packed in `pack`, these objects are added to this "fake index" and
78 * are assumed to appear at the end of the packfile for all operations
81 struct object **objects;
83 uint32_t count, alloc;
84 kh_oid_pos_t *positions;
87 /* Bitmap result of the last performed walk */
88 struct bitmap *result;
90 /* "have" bitmap from the last performed walk */
93 /* Version of the bitmap index */
97 static struct ewah_bitmap *lookup_stored_bitmap(struct stored_bitmap *st)
99 struct ewah_bitmap *parent;
100 struct ewah_bitmap *composed;
105 composed = ewah_pool_new();
106 parent = lookup_stored_bitmap(st->xor);
107 ewah_xor(st->root, parent, composed);
109 ewah_pool_free(st->root);
117 * Read a bitmap from the current read position on the mmaped
118 * index, and increase the read position accordingly
120 static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *index)
122 struct ewah_bitmap *b = ewah_pool_new();
124 ssize_t bitmap_size = ewah_read_mmap(b,
125 index->map + index->map_pos,
126 index->map_size - index->map_pos);
128 if (bitmap_size < 0) {
129 error("Failed to load bitmap index (corrupted?)");
134 index->map_pos += bitmap_size;
138 static int load_bitmap_header(struct bitmap_index *index)
140 struct bitmap_disk_header *header = (void *)index->map;
141 size_t header_size = sizeof(*header) - GIT_MAX_RAWSZ + the_hash_algo->rawsz;
143 if (index->map_size < header_size + the_hash_algo->rawsz)
144 return error("Corrupted bitmap index (too small)");
146 if (memcmp(header->magic, BITMAP_IDX_SIGNATURE, sizeof(BITMAP_IDX_SIGNATURE)) != 0)
147 return error("Corrupted bitmap index file (wrong header)");
149 index->version = ntohs(header->version);
150 if (index->version != 1)
151 return error("Unsupported version for bitmap index file (%d)", index->version);
153 /* Parse known bitmap format options */
155 uint32_t flags = ntohs(header->options);
156 size_t cache_size = st_mult(index->pack->num_objects, sizeof(uint32_t));
157 unsigned char *index_end = index->map + index->map_size - the_hash_algo->rawsz;
159 if ((flags & BITMAP_OPT_FULL_DAG) == 0)
160 return error("Unsupported options for bitmap index file "
161 "(Git requires BITMAP_OPT_FULL_DAG)");
163 if (flags & BITMAP_OPT_HASH_CACHE) {
164 if (cache_size > index_end - index->map - header_size)
165 return error("corrupted bitmap index file (too short to fit hash cache)");
166 index->hashes = (void *)(index_end - cache_size);
167 index_end -= cache_size;
171 index->entry_count = ntohl(header->entry_count);
172 index->map_pos += header_size;
176 static struct stored_bitmap *store_bitmap(struct bitmap_index *index,
177 struct ewah_bitmap *root,
178 const struct object_id *oid,
179 struct stored_bitmap *xor_with,
182 struct stored_bitmap *stored;
186 stored = xmalloc(sizeof(struct stored_bitmap));
188 stored->xor = xor_with;
189 stored->flags = flags;
190 oidcpy(&stored->oid, oid);
192 hash_pos = kh_put_oid_map(index->bitmaps, stored->oid, &ret);
194 /* a 0 return code means the insertion succeeded with no changes,
195 * because the SHA1 already existed on the map. this is bad, there
196 * shouldn't be duplicated commits in the index */
198 error("Duplicate entry in bitmap index: %s", oid_to_hex(oid));
202 kh_value(index->bitmaps, hash_pos) = stored;
206 static inline uint32_t read_be32(const unsigned char *buffer, size_t *pos)
208 uint32_t result = get_be32(buffer + *pos);
209 (*pos) += sizeof(result);
213 static inline uint8_t read_u8(const unsigned char *buffer, size_t *pos)
215 return buffer[(*pos)++];
218 #define MAX_XOR_OFFSET 160
220 static int load_bitmap_entries_v1(struct bitmap_index *index)
223 struct stored_bitmap *recent_bitmaps[MAX_XOR_OFFSET] = { NULL };
225 for (i = 0; i < index->entry_count; ++i) {
226 int xor_offset, flags;
227 struct ewah_bitmap *bitmap = NULL;
228 struct stored_bitmap *xor_bitmap = NULL;
229 uint32_t commit_idx_pos;
230 struct object_id oid;
232 if (index->map_size - index->map_pos < 6)
233 return error("corrupt ewah bitmap: truncated header for entry %d", i);
235 commit_idx_pos = read_be32(index->map, &index->map_pos);
236 xor_offset = read_u8(index->map, &index->map_pos);
237 flags = read_u8(index->map, &index->map_pos);
239 if (nth_packed_object_id(&oid, index->pack, commit_idx_pos) < 0)
240 return error("corrupt ewah bitmap: commit index %u out of range",
241 (unsigned)commit_idx_pos);
243 bitmap = read_bitmap_1(index);
247 if (xor_offset > MAX_XOR_OFFSET || xor_offset > i)
248 return error("Corrupted bitmap pack index");
250 if (xor_offset > 0) {
251 xor_bitmap = recent_bitmaps[(i - xor_offset) % MAX_XOR_OFFSET];
253 if (xor_bitmap == NULL)
254 return error("Invalid XOR offset in bitmap pack index");
257 recent_bitmaps[i % MAX_XOR_OFFSET] = store_bitmap(
258 index, bitmap, &oid, xor_bitmap, flags);
264 static char *pack_bitmap_filename(struct packed_git *p)
268 if (!strip_suffix(p->pack_name, ".pack", &len))
269 BUG("pack_name does not end in .pack");
270 return xstrfmt("%.*s.bitmap", (int)len, p->pack_name);
273 static int open_pack_bitmap_1(struct bitmap_index *bitmap_git, struct packed_git *packfile)
279 if (open_pack_index(packfile))
282 idx_name = pack_bitmap_filename(packfile);
283 fd = git_open(idx_name);
289 if (fstat(fd, &st)) {
294 if (bitmap_git->pack) {
295 warning("ignoring extra bitmap file: %s", packfile->pack_name);
300 bitmap_git->pack = packfile;
301 bitmap_git->map_size = xsize_t(st.st_size);
302 bitmap_git->map = xmmap(NULL, bitmap_git->map_size, PROT_READ, MAP_PRIVATE, fd, 0);
303 bitmap_git->map_pos = 0;
306 if (load_bitmap_header(bitmap_git) < 0) {
307 munmap(bitmap_git->map, bitmap_git->map_size);
308 bitmap_git->map = NULL;
309 bitmap_git->map_size = 0;
316 static int load_pack_bitmap(struct bitmap_index *bitmap_git)
318 assert(bitmap_git->map);
320 bitmap_git->bitmaps = kh_init_oid_map();
321 bitmap_git->ext_index.positions = kh_init_oid_pos();
322 if (load_pack_revindex(bitmap_git->pack))
325 if (!(bitmap_git->commits = read_bitmap_1(bitmap_git)) ||
326 !(bitmap_git->trees = read_bitmap_1(bitmap_git)) ||
327 !(bitmap_git->blobs = read_bitmap_1(bitmap_git)) ||
328 !(bitmap_git->tags = read_bitmap_1(bitmap_git)))
331 if (load_bitmap_entries_v1(bitmap_git) < 0)
337 munmap(bitmap_git->map, bitmap_git->map_size);
338 bitmap_git->map = NULL;
339 bitmap_git->map_size = 0;
341 kh_destroy_oid_map(bitmap_git->bitmaps);
342 bitmap_git->bitmaps = NULL;
344 kh_destroy_oid_pos(bitmap_git->ext_index.positions);
345 bitmap_git->ext_index.positions = NULL;
350 static int open_pack_bitmap(struct repository *r,
351 struct bitmap_index *bitmap_git)
353 struct packed_git *p;
356 assert(!bitmap_git->map);
358 for (p = get_all_packs(r); p; p = p->next) {
359 if (open_pack_bitmap_1(bitmap_git, p) == 0)
366 struct bitmap_index *prepare_bitmap_git(struct repository *r)
368 struct bitmap_index *bitmap_git = xcalloc(1, sizeof(*bitmap_git));
370 if (!open_pack_bitmap(r, bitmap_git) && !load_pack_bitmap(bitmap_git))
373 free_bitmap_index(bitmap_git);
377 struct include_data {
378 struct bitmap_index *bitmap_git;
383 struct ewah_bitmap *bitmap_for_commit(struct bitmap_index *bitmap_git,
384 struct commit *commit)
386 khiter_t hash_pos = kh_get_oid_map(bitmap_git->bitmaps,
388 if (hash_pos >= kh_end(bitmap_git->bitmaps))
390 return lookup_stored_bitmap(kh_value(bitmap_git->bitmaps, hash_pos));
393 static inline int bitmap_position_extended(struct bitmap_index *bitmap_git,
394 const struct object_id *oid)
396 kh_oid_pos_t *positions = bitmap_git->ext_index.positions;
397 khiter_t pos = kh_get_oid_pos(positions, *oid);
399 if (pos < kh_end(positions)) {
400 int bitmap_pos = kh_value(positions, pos);
401 return bitmap_pos + bitmap_git->pack->num_objects;
407 static inline int bitmap_position_packfile(struct bitmap_index *bitmap_git,
408 const struct object_id *oid)
411 off_t offset = find_pack_entry_one(oid->hash, bitmap_git->pack);
415 if (offset_to_pack_pos(bitmap_git->pack, offset, &pos) < 0)
420 static int bitmap_position(struct bitmap_index *bitmap_git,
421 const struct object_id *oid)
423 int pos = bitmap_position_packfile(bitmap_git, oid);
424 return (pos >= 0) ? pos : bitmap_position_extended(bitmap_git, oid);
427 static int ext_index_add_object(struct bitmap_index *bitmap_git,
428 struct object *object, const char *name)
430 struct eindex *eindex = &bitmap_git->ext_index;
436 hash_pos = kh_put_oid_pos(eindex->positions, object->oid, &hash_ret);
438 if (eindex->count >= eindex->alloc) {
439 eindex->alloc = (eindex->alloc + 16) * 3 / 2;
440 REALLOC_ARRAY(eindex->objects, eindex->alloc);
441 REALLOC_ARRAY(eindex->hashes, eindex->alloc);
444 bitmap_pos = eindex->count;
445 eindex->objects[eindex->count] = object;
446 eindex->hashes[eindex->count] = pack_name_hash(name);
447 kh_value(eindex->positions, hash_pos) = bitmap_pos;
450 bitmap_pos = kh_value(eindex->positions, hash_pos);
453 return bitmap_pos + bitmap_git->pack->num_objects;
456 struct bitmap_show_data {
457 struct bitmap_index *bitmap_git;
461 static void show_object(struct object *object, const char *name, void *data_)
463 struct bitmap_show_data *data = data_;
466 bitmap_pos = bitmap_position(data->bitmap_git, &object->oid);
469 bitmap_pos = ext_index_add_object(data->bitmap_git, object,
472 bitmap_set(data->base, bitmap_pos);
475 static void show_commit(struct commit *commit, void *data)
479 static int add_to_include_set(struct bitmap_index *bitmap_git,
480 struct include_data *data,
481 struct commit *commit,
484 struct ewah_bitmap *partial;
486 if (data->seen && bitmap_get(data->seen, bitmap_pos))
489 if (bitmap_get(data->base, bitmap_pos))
492 partial = bitmap_for_commit(bitmap_git, commit);
494 bitmap_or_ewah(data->base, partial);
498 bitmap_set(data->base, bitmap_pos);
502 static int should_include(struct commit *commit, void *_data)
504 struct include_data *data = _data;
507 bitmap_pos = bitmap_position(data->bitmap_git, &commit->object.oid);
509 bitmap_pos = ext_index_add_object(data->bitmap_git,
510 (struct object *)commit,
513 if (!add_to_include_set(data->bitmap_git, data, commit, bitmap_pos)) {
514 struct commit_list *parent = commit->parents;
517 parent->item->object.flags |= SEEN;
518 parent = parent->next;
527 static int add_commit_to_bitmap(struct bitmap_index *bitmap_git,
528 struct bitmap **base,
529 struct commit *commit)
531 struct ewah_bitmap *or_with = bitmap_for_commit(bitmap_git, commit);
537 *base = ewah_to_bitmap(or_with);
539 bitmap_or_ewah(*base, or_with);
544 static struct bitmap *find_objects(struct bitmap_index *bitmap_git,
545 struct rev_info *revs,
546 struct object_list *roots,
548 struct list_objects_filter_options *filter)
550 struct bitmap *base = NULL;
553 struct object_list *not_mapped = NULL;
556 * Go through all the roots for the walk. The ones that have bitmaps
557 * on the bitmap index will be `or`ed together to form an initial
558 * global reachability analysis.
560 * The ones without bitmaps in the index will be stored in the
561 * `not_mapped_list` for further processing.
564 struct object *object = roots->item;
567 if (object->type == OBJ_COMMIT &&
568 add_commit_to_bitmap(bitmap_git, &base, (struct commit *)object)) {
569 object->flags |= SEEN;
573 object_list_insert(object, ¬_mapped);
577 * Best case scenario: We found bitmaps for all the roots,
578 * so the resulting `or` bitmap has the full reachability analysis
580 if (not_mapped == NULL)
586 * Let's iterate through all the roots that don't have bitmaps to
587 * check if we can determine them to be reachable from the existing
590 * If we cannot find them in the existing global bitmap, we'll need
591 * to push them to an actual walk and run it until we can confirm
595 struct object *object = roots->item;
599 pos = bitmap_position(bitmap_git, &object->oid);
601 if (pos < 0 || base == NULL || !bitmap_get(base, pos)) {
602 object->flags &= ~UNINTERESTING;
603 add_pending_object(revs, object, "");
606 object->flags |= SEEN;
611 struct include_data incdata;
612 struct bitmap_show_data show_data;
617 incdata.bitmap_git = bitmap_git;
621 revs->include_check = should_include;
622 revs->include_check_data = &incdata;
624 if (prepare_revision_walk(revs))
625 die("revision walk setup failed");
627 show_data.bitmap_git = bitmap_git;
628 show_data.base = base;
630 traverse_commit_list_filtered(filter, revs,
631 show_commit, show_object,
634 revs->include_check = NULL;
635 revs->include_check_data = NULL;
641 static void show_extended_objects(struct bitmap_index *bitmap_git,
642 struct rev_info *revs,
643 show_reachable_fn show_reach)
645 struct bitmap *objects = bitmap_git->result;
646 struct eindex *eindex = &bitmap_git->ext_index;
649 for (i = 0; i < eindex->count; ++i) {
652 if (!bitmap_get(objects, bitmap_git->pack->num_objects + i))
655 obj = eindex->objects[i];
656 if ((obj->type == OBJ_BLOB && !revs->blob_objects) ||
657 (obj->type == OBJ_TREE && !revs->tree_objects) ||
658 (obj->type == OBJ_TAG && !revs->tag_objects))
661 show_reach(&obj->oid, obj->type, 0, eindex->hashes[i], NULL, 0);
665 static void init_type_iterator(struct ewah_iterator *it,
666 struct bitmap_index *bitmap_git,
667 enum object_type type)
671 ewah_iterator_init(it, bitmap_git->commits);
675 ewah_iterator_init(it, bitmap_git->trees);
679 ewah_iterator_init(it, bitmap_git->blobs);
683 ewah_iterator_init(it, bitmap_git->tags);
687 BUG("object type %d not stored by bitmap type index", type);
692 static void show_objects_for_type(
693 struct bitmap_index *bitmap_git,
694 enum object_type object_type,
695 show_reachable_fn show_reach)
700 struct ewah_iterator it;
703 struct bitmap *objects = bitmap_git->result;
705 init_type_iterator(&it, bitmap_git, object_type);
707 for (i = 0; i < objects->word_alloc &&
708 ewah_iterator_next(&filter, &it); i++) {
709 eword_t word = objects->words[i] & filter;
710 size_t pos = (i * BITS_IN_EWORD);
715 for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
716 struct object_id oid;
717 uint32_t hash = 0, index_pos;
720 if ((word >> offset) == 0)
723 offset += ewah_bit_ctz64(word >> offset);
725 index_pos = pack_pos_to_index(bitmap_git->pack, pos + offset);
726 ofs = pack_pos_to_offset(bitmap_git->pack, pos + offset);
727 nth_packed_object_id(&oid, bitmap_git->pack, index_pos);
729 if (bitmap_git->hashes)
730 hash = get_be32(bitmap_git->hashes + index_pos);
732 show_reach(&oid, object_type, 0, hash, bitmap_git->pack, ofs);
737 static int in_bitmapped_pack(struct bitmap_index *bitmap_git,
738 struct object_list *roots)
741 struct object *object = roots->item;
744 if (find_pack_entry_one(object->oid.hash, bitmap_git->pack) > 0)
751 static struct bitmap *find_tip_objects(struct bitmap_index *bitmap_git,
752 struct object_list *tip_objects,
753 enum object_type type)
755 struct bitmap *result = bitmap_new();
756 struct object_list *p;
758 for (p = tip_objects; p; p = p->next) {
761 if (p->item->type != type)
764 pos = bitmap_position(bitmap_git, &p->item->oid);
768 bitmap_set(result, pos);
774 static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git,
775 struct object_list *tip_objects,
776 struct bitmap *to_filter,
777 enum object_type type)
779 struct eindex *eindex = &bitmap_git->ext_index;
781 struct ewah_iterator it;
785 if (type != OBJ_BLOB && type != OBJ_TREE)
786 BUG("filter_bitmap_exclude_type: unsupported type '%d'", type);
789 * The non-bitmap version of this filter never removes
790 * objects which the other side specifically asked for,
791 * so we must match that behavior.
793 tips = find_tip_objects(bitmap_git, tip_objects, type);
796 * We can use the blob type-bitmap to work in whole words
797 * for the objects that are actually in the bitmapped packfile.
799 for (i = 0, init_type_iterator(&it, bitmap_git, type);
800 i < to_filter->word_alloc && ewah_iterator_next(&mask, &it);
802 if (i < tips->word_alloc)
803 mask &= ~tips->words[i];
804 to_filter->words[i] &= ~mask;
808 * Clear any blobs that weren't in the packfile (and so would not have
809 * been caught by the loop above. We'll have to check them
812 for (i = 0; i < eindex->count; i++) {
813 uint32_t pos = i + bitmap_git->pack->num_objects;
814 if (eindex->objects[i]->type == type &&
815 bitmap_get(to_filter, pos) &&
816 !bitmap_get(tips, pos))
817 bitmap_unset(to_filter, pos);
823 static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git,
824 struct object_list *tip_objects,
825 struct bitmap *to_filter)
827 filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter,
831 static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git,
834 struct packed_git *pack = bitmap_git->pack;
836 struct object_info oi = OBJECT_INFO_INIT;
840 if (pos < pack->num_objects) {
841 off_t ofs = pack_pos_to_offset(pack, pos);
842 if (packed_object_info(the_repository, pack, ofs, &oi) < 0) {
843 struct object_id oid;
844 nth_packed_object_id(&oid, pack,
845 pack_pos_to_index(pack, pos));
846 die(_("unable to get size of %s"), oid_to_hex(&oid));
849 struct eindex *eindex = &bitmap_git->ext_index;
850 struct object *obj = eindex->objects[pos - pack->num_objects];
851 if (oid_object_info_extended(the_repository, &obj->oid, &oi, 0) < 0)
852 die(_("unable to get size of %s"), oid_to_hex(&obj->oid));
858 static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git,
859 struct object_list *tip_objects,
860 struct bitmap *to_filter,
863 struct eindex *eindex = &bitmap_git->ext_index;
865 struct ewah_iterator it;
869 tips = find_tip_objects(bitmap_git, tip_objects, OBJ_BLOB);
871 for (i = 0, init_type_iterator(&it, bitmap_git, OBJ_BLOB);
872 i < to_filter->word_alloc && ewah_iterator_next(&mask, &it);
874 eword_t word = to_filter->words[i] & mask;
877 for (offset = 0; offset < BITS_IN_EWORD; offset++) {
880 if ((word >> offset) == 0)
882 offset += ewah_bit_ctz64(word >> offset);
883 pos = i * BITS_IN_EWORD + offset;
885 if (!bitmap_get(tips, pos) &&
886 get_size_by_pos(bitmap_git, pos) >= limit)
887 bitmap_unset(to_filter, pos);
891 for (i = 0; i < eindex->count; i++) {
892 uint32_t pos = i + bitmap_git->pack->num_objects;
893 if (eindex->objects[i]->type == OBJ_BLOB &&
894 bitmap_get(to_filter, pos) &&
895 !bitmap_get(tips, pos) &&
896 get_size_by_pos(bitmap_git, pos) >= limit)
897 bitmap_unset(to_filter, pos);
903 static void filter_bitmap_tree_depth(struct bitmap_index *bitmap_git,
904 struct object_list *tip_objects,
905 struct bitmap *to_filter,
909 BUG("filter_bitmap_tree_depth given non-zero limit");
911 filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter,
913 filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter,
917 static int filter_bitmap(struct bitmap_index *bitmap_git,
918 struct object_list *tip_objects,
919 struct bitmap *to_filter,
920 struct list_objects_filter_options *filter)
922 if (!filter || filter->choice == LOFC_DISABLED)
925 if (filter->choice == LOFC_BLOB_NONE) {
927 filter_bitmap_blob_none(bitmap_git, tip_objects,
932 if (filter->choice == LOFC_BLOB_LIMIT) {
934 filter_bitmap_blob_limit(bitmap_git, tip_objects,
936 filter->blob_limit_value);
940 if (filter->choice == LOFC_TREE_DEPTH &&
941 filter->tree_exclude_depth == 0) {
943 filter_bitmap_tree_depth(bitmap_git, tip_objects,
945 filter->tree_exclude_depth);
949 /* filter choice not handled */
953 static int can_filter_bitmap(struct list_objects_filter_options *filter)
955 return !filter_bitmap(NULL, NULL, NULL, filter);
958 struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,
959 struct list_objects_filter_options *filter)
963 struct object_list *wants = NULL;
964 struct object_list *haves = NULL;
966 struct bitmap *wants_bitmap = NULL;
967 struct bitmap *haves_bitmap = NULL;
969 struct bitmap_index *bitmap_git;
972 * We can't do pathspec limiting with bitmaps, because we don't know
973 * which commits are associated with which object changes (let alone
974 * even which objects are associated with which paths).
979 if (!can_filter_bitmap(filter))
982 /* try to open a bitmapped pack, but don't parse it yet
983 * because we may not need to use it */
984 CALLOC_ARRAY(bitmap_git, 1);
985 if (open_pack_bitmap(revs->repo, bitmap_git) < 0)
988 for (i = 0; i < revs->pending.nr; ++i) {
989 struct object *object = revs->pending.objects[i].item;
991 if (object->type == OBJ_NONE)
992 parse_object_or_die(&object->oid, NULL);
994 while (object->type == OBJ_TAG) {
995 struct tag *tag = (struct tag *) object;
997 if (object->flags & UNINTERESTING)
998 object_list_insert(object, &haves);
1000 object_list_insert(object, &wants);
1002 object = parse_object_or_die(get_tagged_oid(tag), NULL);
1005 if (object->flags & UNINTERESTING)
1006 object_list_insert(object, &haves);
1008 object_list_insert(object, &wants);
1012 * if we have a HAVES list, but none of those haves is contained
1013 * in the packfile that has a bitmap, we don't have anything to
1016 if (haves && !in_bitmapped_pack(bitmap_git, haves))
1019 /* if we don't want anything, we're done here */
1024 * now we're going to use bitmaps, so load the actual bitmap entries
1025 * from disk. this is the point of no return; after this the rev_list
1026 * becomes invalidated and we must perform the revwalk through bitmaps
1028 if (load_pack_bitmap(bitmap_git) < 0)
1031 object_array_clear(&revs->pending);
1034 revs->ignore_missing_links = 1;
1035 haves_bitmap = find_objects(bitmap_git, revs, haves, NULL,
1037 reset_revision_walk();
1038 revs->ignore_missing_links = 0;
1040 if (haves_bitmap == NULL)
1041 BUG("failed to perform bitmap walk");
1044 wants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap,
1048 BUG("failed to perform bitmap walk");
1051 bitmap_and_not(wants_bitmap, haves_bitmap);
1053 filter_bitmap(bitmap_git, wants, wants_bitmap, filter);
1055 bitmap_git->result = wants_bitmap;
1056 bitmap_git->haves = haves_bitmap;
1058 object_list_free(&wants);
1059 object_list_free(&haves);
1064 free_bitmap_index(bitmap_git);
1065 object_list_free(&wants);
1066 object_list_free(&haves);
1070 static void try_partial_reuse(struct bitmap_index *bitmap_git,
1072 struct bitmap *reuse,
1073 struct pack_window **w_curs)
1075 off_t offset, header;
1076 enum object_type type;
1079 if (pos >= bitmap_git->pack->num_objects)
1080 return; /* not actually in the pack */
1082 offset = header = pack_pos_to_offset(bitmap_git->pack, pos);
1083 type = unpack_object_header(bitmap_git->pack, w_curs, &offset, &size);
1085 return; /* broken packfile, punt */
1087 if (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA) {
1092 * Find the position of the base object so we can look it up
1093 * in our bitmaps. If we can't come up with an offset, or if
1094 * that offset is not in the revidx, the pack is corrupt.
1095 * There's nothing we can do, so just punt on this object,
1096 * and the normal slow path will complain about it in
1099 base_offset = get_delta_base(bitmap_git->pack, w_curs,
1100 &offset, type, header);
1103 if (offset_to_pack_pos(bitmap_git->pack, base_offset, &base_pos) < 0)
1107 * We assume delta dependencies always point backwards. This
1108 * lets us do a single pass, and is basically always true
1109 * due to the way OFS_DELTAs work. You would not typically
1110 * find REF_DELTA in a bitmapped pack, since we only bitmap
1111 * packs we write fresh, and OFS_DELTA is the default). But
1112 * let's double check to make sure the pack wasn't written with
1115 if (base_pos >= pos)
1119 * And finally, if we're not sending the base as part of our
1120 * reuse chunk, then don't send this object either. The base
1121 * would come after us, along with other objects not
1122 * necessarily in the pack, which means we'd need to convert
1123 * to REF_DELTA on the fly. Better to just let the normal
1124 * object_entry code path handle it.
1126 if (!bitmap_get(reuse, base_pos))
1131 * If we got here, then the object is OK to reuse. Mark it.
1133 bitmap_set(reuse, pos);
1136 int reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,
1137 struct packed_git **packfile_out,
1139 struct bitmap **reuse_out)
1141 struct bitmap *result = bitmap_git->result;
1142 struct bitmap *reuse;
1143 struct pack_window *w_curs = NULL;
1149 while (i < result->word_alloc && result->words[i] == (eword_t)~0)
1152 /* Don't mark objects not in the packfile */
1153 if (i > bitmap_git->pack->num_objects / BITS_IN_EWORD)
1154 i = bitmap_git->pack->num_objects / BITS_IN_EWORD;
1156 reuse = bitmap_word_alloc(i);
1157 memset(reuse->words, 0xFF, i * sizeof(eword_t));
1159 for (; i < result->word_alloc; ++i) {
1160 eword_t word = result->words[i];
1161 size_t pos = (i * BITS_IN_EWORD);
1163 for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
1164 if ((word >> offset) == 0)
1167 offset += ewah_bit_ctz64(word >> offset);
1168 try_partial_reuse(bitmap_git, pos + offset, reuse, &w_curs);
1172 unuse_pack(&w_curs);
1174 *entries = bitmap_popcount(reuse);
1181 * Drop any reused objects from the result, since they will not
1182 * need to be handled separately.
1184 bitmap_and_not(result, reuse);
1185 *packfile_out = bitmap_git->pack;
1190 int bitmap_walk_contains(struct bitmap_index *bitmap_git,
1191 struct bitmap *bitmap, const struct object_id *oid)
1198 idx = bitmap_position(bitmap_git, oid);
1199 return idx >= 0 && bitmap_get(bitmap, idx);
1202 void traverse_bitmap_commit_list(struct bitmap_index *bitmap_git,
1203 struct rev_info *revs,
1204 show_reachable_fn show_reachable)
1206 assert(bitmap_git->result);
1208 show_objects_for_type(bitmap_git, OBJ_COMMIT, show_reachable);
1209 if (revs->tree_objects)
1210 show_objects_for_type(bitmap_git, OBJ_TREE, show_reachable);
1211 if (revs->blob_objects)
1212 show_objects_for_type(bitmap_git, OBJ_BLOB, show_reachable);
1213 if (revs->tag_objects)
1214 show_objects_for_type(bitmap_git, OBJ_TAG, show_reachable);
1216 show_extended_objects(bitmap_git, revs, show_reachable);
1219 static uint32_t count_object_type(struct bitmap_index *bitmap_git,
1220 enum object_type type)
1222 struct bitmap *objects = bitmap_git->result;
1223 struct eindex *eindex = &bitmap_git->ext_index;
1225 uint32_t i = 0, count = 0;
1226 struct ewah_iterator it;
1229 init_type_iterator(&it, bitmap_git, type);
1231 while (i < objects->word_alloc && ewah_iterator_next(&filter, &it)) {
1232 eword_t word = objects->words[i++] & filter;
1233 count += ewah_bit_popcount64(word);
1236 for (i = 0; i < eindex->count; ++i) {
1237 if (eindex->objects[i]->type == type &&
1238 bitmap_get(objects, bitmap_git->pack->num_objects + i))
1245 void count_bitmap_commit_list(struct bitmap_index *bitmap_git,
1246 uint32_t *commits, uint32_t *trees,
1247 uint32_t *blobs, uint32_t *tags)
1249 assert(bitmap_git->result);
1252 *commits = count_object_type(bitmap_git, OBJ_COMMIT);
1255 *trees = count_object_type(bitmap_git, OBJ_TREE);
1258 *blobs = count_object_type(bitmap_git, OBJ_BLOB);
1261 *tags = count_object_type(bitmap_git, OBJ_TAG);
1264 struct bitmap_test_data {
1265 struct bitmap_index *bitmap_git;
1266 struct bitmap *base;
1267 struct progress *prg;
1271 static void test_show_object(struct object *object, const char *name,
1274 struct bitmap_test_data *tdata = data;
1277 bitmap_pos = bitmap_position(tdata->bitmap_git, &object->oid);
1279 die("Object not in bitmap: %s\n", oid_to_hex(&object->oid));
1281 bitmap_set(tdata->base, bitmap_pos);
1282 display_progress(tdata->prg, ++tdata->seen);
1285 static void test_show_commit(struct commit *commit, void *data)
1287 struct bitmap_test_data *tdata = data;
1290 bitmap_pos = bitmap_position(tdata->bitmap_git,
1291 &commit->object.oid);
1293 die("Object not in bitmap: %s\n", oid_to_hex(&commit->object.oid));
1295 bitmap_set(tdata->base, bitmap_pos);
1296 display_progress(tdata->prg, ++tdata->seen);
1299 void test_bitmap_walk(struct rev_info *revs)
1301 struct object *root;
1302 struct bitmap *result = NULL;
1303 size_t result_popcnt;
1304 struct bitmap_test_data tdata;
1305 struct bitmap_index *bitmap_git;
1306 struct ewah_bitmap *bm;
1308 if (!(bitmap_git = prepare_bitmap_git(revs->repo)))
1309 die("failed to load bitmap indexes");
1311 if (revs->pending.nr != 1)
1312 die("you must specify exactly one commit to test");
1314 fprintf(stderr, "Bitmap v%d test (%d entries loaded)\n",
1315 bitmap_git->version, bitmap_git->entry_count);
1317 root = revs->pending.objects[0].item;
1318 bm = bitmap_for_commit(bitmap_git, (struct commit *)root);
1321 fprintf(stderr, "Found bitmap for %s. %d bits / %08x checksum\n",
1322 oid_to_hex(&root->oid), (int)bm->bit_size, ewah_checksum(bm));
1324 result = ewah_to_bitmap(bm);
1328 die("Commit %s doesn't have an indexed bitmap", oid_to_hex(&root->oid));
1330 revs->tag_objects = 1;
1331 revs->tree_objects = 1;
1332 revs->blob_objects = 1;
1334 result_popcnt = bitmap_popcount(result);
1336 if (prepare_revision_walk(revs))
1337 die("revision walk setup failed");
1339 tdata.bitmap_git = bitmap_git;
1340 tdata.base = bitmap_new();
1341 tdata.prg = start_progress("Verifying bitmap entries", result_popcnt);
1344 traverse_commit_list(revs, &test_show_commit, &test_show_object, &tdata);
1346 stop_progress(&tdata.prg);
1348 if (bitmap_equals(result, tdata.base))
1349 fprintf(stderr, "OK!\n");
1351 die("mismatch in bitmap results");
1353 free_bitmap_index(bitmap_git);
1356 int rebuild_bitmap(const uint32_t *reposition,
1357 struct ewah_bitmap *source,
1358 struct bitmap *dest)
1361 struct ewah_iterator it;
1364 ewah_iterator_init(&it, source);
1366 while (ewah_iterator_next(&word, &it)) {
1367 uint32_t offset, bit_pos;
1369 for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
1370 if ((word >> offset) == 0)
1373 offset += ewah_bit_ctz64(word >> offset);
1375 bit_pos = reposition[pos + offset];
1377 bitmap_set(dest, bit_pos - 1);
1378 else /* can't reuse, we don't have the object */
1382 pos += BITS_IN_EWORD;
1387 uint32_t *create_bitmap_mapping(struct bitmap_index *bitmap_git,
1388 struct packing_data *mapping)
1390 uint32_t i, num_objects;
1391 uint32_t *reposition;
1393 num_objects = bitmap_git->pack->num_objects;
1394 CALLOC_ARRAY(reposition, num_objects);
1396 for (i = 0; i < num_objects; ++i) {
1397 struct object_id oid;
1398 struct object_entry *oe;
1400 nth_packed_object_id(&oid, bitmap_git->pack,
1401 pack_pos_to_index(bitmap_git->pack, i));
1402 oe = packlist_find(mapping, &oid);
1405 reposition[i] = oe_in_pack_pos(mapping, oe) + 1;
1411 void free_bitmap_index(struct bitmap_index *b)
1417 munmap(b->map, b->map_size);
1418 ewah_pool_free(b->commits);
1419 ewah_pool_free(b->trees);
1420 ewah_pool_free(b->blobs);
1421 ewah_pool_free(b->tags);
1422 kh_destroy_oid_map(b->bitmaps);
1423 free(b->ext_index.objects);
1424 free(b->ext_index.hashes);
1425 bitmap_free(b->result);
1426 bitmap_free(b->haves);
1430 int bitmap_has_oid_in_uninteresting(struct bitmap_index *bitmap_git,
1431 const struct object_id *oid)
1433 return bitmap_git &&
1434 bitmap_walk_contains(bitmap_git, bitmap_git->haves, oid);
1437 static off_t get_disk_usage_for_type(struct bitmap_index *bitmap_git,
1438 enum object_type object_type)
1440 struct bitmap *result = bitmap_git->result;
1441 struct packed_git *pack = bitmap_git->pack;
1443 struct ewah_iterator it;
1447 init_type_iterator(&it, bitmap_git, object_type);
1448 for (i = 0; i < result->word_alloc &&
1449 ewah_iterator_next(&filter, &it); i++) {
1450 eword_t word = result->words[i] & filter;
1451 size_t base = (i * BITS_IN_EWORD);
1457 for (offset = 0; offset < BITS_IN_EWORD; offset++) {
1460 if ((word >> offset) == 0)
1463 offset += ewah_bit_ctz64(word >> offset);
1464 pos = base + offset;
1465 total += pack_pos_to_offset(pack, pos + 1) -
1466 pack_pos_to_offset(pack, pos);
1473 static off_t get_disk_usage_for_extended(struct bitmap_index *bitmap_git)
1475 struct bitmap *result = bitmap_git->result;
1476 struct packed_git *pack = bitmap_git->pack;
1477 struct eindex *eindex = &bitmap_git->ext_index;
1479 struct object_info oi = OBJECT_INFO_INIT;
1483 oi.disk_sizep = &object_size;
1485 for (i = 0; i < eindex->count; i++) {
1486 struct object *obj = eindex->objects[i];
1488 if (!bitmap_get(result, pack->num_objects + i))
1491 if (oid_object_info_extended(the_repository, &obj->oid, &oi, 0) < 0)
1492 die(_("unable to get disk usage of %s"),
1493 oid_to_hex(&obj->oid));
1495 total += object_size;
1500 off_t get_disk_usage_from_bitmap(struct bitmap_index *bitmap_git,
1501 struct rev_info *revs)
1505 total += get_disk_usage_for_type(bitmap_git, OBJ_COMMIT);
1506 if (revs->tree_objects)
1507 total += get_disk_usage_for_type(bitmap_git, OBJ_TREE);
1508 if (revs->blob_objects)
1509 total += get_disk_usage_for_type(bitmap_git, OBJ_BLOB);
1510 if (revs->tag_objects)
1511 total += get_disk_usage_for_type(bitmap_git, OBJ_TAG);
1513 total += get_disk_usage_for_extended(bitmap_git);