7 #include "list-objects.h"
9 #include "pack-bitmap.h"
10 #include "pack-revindex.h"
11 #include "pack-objects.h"
14 * An entry on the bitmap index, representing the bitmap for a given
17 struct stored_bitmap
{
18 unsigned char sha1
[20];
19 struct ewah_bitmap
*root
;
20 struct stored_bitmap
*xor;
25 * The currently active bitmap index. By design, repositories only have
26 * a single bitmap index available (the index for the biggest packfile in
27 * the repository), since bitmap indexes need full closure.
29 * If there is more than one bitmap index available (e.g. because of alternates),
30 * the active bitmap index is the largest one.
32 static struct bitmap_index
{
33 /* Packfile to which this bitmap index belongs to */
34 struct packed_git
*pack
;
37 * Mark the first `reuse_objects` in the packfile as reused:
38 * they will be sent as-is without using them for repacking
41 uint32_t reuse_objects
;
43 /* mmapped buffer of the whole bitmap index */
45 size_t map_size
; /* size of the mmaped buffer */
46 size_t map_pos
; /* current position when loading the index */
51 * Each bitmap marks which objects in the packfile are of the given
52 * type. This provides type information when yielding the objects from
53 * the packfile during a walk, which allows for better delta bases.
55 struct ewah_bitmap
*commits
;
56 struct ewah_bitmap
*trees
;
57 struct ewah_bitmap
*blobs
;
58 struct ewah_bitmap
*tags
;
60 /* Map from SHA1 -> `stored_bitmap` for all the bitmapped commits */
63 /* Number of bitmapped commits */
66 /* Name-hash cache (or NULL if not present). */
72 * When trying to perform bitmap operations with objects that are not
73 * packed in `pack`, these objects are added to this "fake index" and
74 * are assumed to appear at the end of the packfile for all operations
77 struct object
**objects
;
79 uint32_t count
, alloc
;
80 khash_sha1_pos
*positions
;
83 /* Bitmap result of the last performed walk */
84 struct bitmap
*result
;
86 /* Version of the bitmap index */
93 static struct ewah_bitmap
*lookup_stored_bitmap(struct stored_bitmap
*st
)
95 struct ewah_bitmap
*parent
;
96 struct ewah_bitmap
*composed
;
101 composed
= ewah_pool_new();
102 parent
= lookup_stored_bitmap(st
->xor);
103 ewah_xor(st
->root
, parent
, composed
);
105 ewah_pool_free(st
->root
);
113 * Read a bitmap from the current read position on the mmaped
114 * index, and increase the read position accordingly
116 static struct ewah_bitmap
*read_bitmap_1(struct bitmap_index
*index
)
118 struct ewah_bitmap
*b
= ewah_pool_new();
120 int bitmap_size
= ewah_read_mmap(b
,
121 index
->map
+ index
->map_pos
,
122 index
->map_size
- index
->map_pos
);
124 if (bitmap_size
< 0) {
125 error("Failed to load bitmap index (corrupted?)");
130 index
->map_pos
+= bitmap_size
;
134 static int load_bitmap_header(struct bitmap_index
*index
)
136 struct bitmap_disk_header
*header
= (void *)index
->map
;
138 if (index
->map_size
< sizeof(*header
) + 20)
139 return error("Corrupted bitmap index (missing header data)");
141 if (memcmp(header
->magic
, BITMAP_IDX_SIGNATURE
, sizeof(BITMAP_IDX_SIGNATURE
)) != 0)
142 return error("Corrupted bitmap index file (wrong header)");
144 index
->version
= ntohs(header
->version
);
145 if (index
->version
!= 1)
146 return error("Unsupported version for bitmap index file (%d)", index
->version
);
148 /* Parse known bitmap format options */
150 uint32_t flags
= ntohs(header
->options
);
152 if ((flags
& BITMAP_OPT_FULL_DAG
) == 0)
153 return error("Unsupported options for bitmap index file "
154 "(Git requires BITMAP_OPT_FULL_DAG)");
156 if (flags
& BITMAP_OPT_HASH_CACHE
) {
157 unsigned char *end
= index
->map
+ index
->map_size
- 20;
158 index
->hashes
= ((uint32_t *)end
) - index
->pack
->num_objects
;
162 index
->entry_count
= ntohl(header
->entry_count
);
163 index
->map_pos
+= sizeof(*header
);
167 static struct stored_bitmap
*store_bitmap(struct bitmap_index
*index
,
168 struct ewah_bitmap
*root
,
169 const unsigned char *sha1
,
170 struct stored_bitmap
*xor_with
,
173 struct stored_bitmap
*stored
;
177 stored
= xmalloc(sizeof(struct stored_bitmap
));
179 stored
->xor = xor_with
;
180 stored
->flags
= flags
;
181 hashcpy(stored
->sha1
, sha1
);
183 hash_pos
= kh_put_sha1(index
->bitmaps
, stored
->sha1
, &ret
);
185 /* a 0 return code means the insertion succeeded with no changes,
186 * because the SHA1 already existed on the map. this is bad, there
187 * shouldn't be duplicated commits in the index */
189 error("Duplicate entry in bitmap index: %s", sha1_to_hex(sha1
));
193 kh_value(index
->bitmaps
, hash_pos
) = stored
;
197 static inline uint32_t read_be32(const unsigned char *buffer
, size_t *pos
)
199 uint32_t result
= get_be32(buffer
+ *pos
);
200 (*pos
) += sizeof(result
);
204 static inline uint8_t read_u8(const unsigned char *buffer
, size_t *pos
)
206 return buffer
[(*pos
)++];
209 #define MAX_XOR_OFFSET 160
211 static int load_bitmap_entries_v1(struct bitmap_index
*index
)
214 struct stored_bitmap
*recent_bitmaps
[MAX_XOR_OFFSET
] = { NULL
};
216 for (i
= 0; i
< index
->entry_count
; ++i
) {
217 int xor_offset
, flags
;
218 struct ewah_bitmap
*bitmap
= NULL
;
219 struct stored_bitmap
*xor_bitmap
= NULL
;
220 uint32_t commit_idx_pos
;
221 const unsigned char *sha1
;
223 commit_idx_pos
= read_be32(index
->map
, &index
->map_pos
);
224 xor_offset
= read_u8(index
->map
, &index
->map_pos
);
225 flags
= read_u8(index
->map
, &index
->map_pos
);
227 sha1
= nth_packed_object_sha1(index
->pack
, commit_idx_pos
);
229 bitmap
= read_bitmap_1(index
);
233 if (xor_offset
> MAX_XOR_OFFSET
|| xor_offset
> i
)
234 return error("Corrupted bitmap pack index");
236 if (xor_offset
> 0) {
237 xor_bitmap
= recent_bitmaps
[(i
- xor_offset
) % MAX_XOR_OFFSET
];
239 if (xor_bitmap
== NULL
)
240 return error("Invalid XOR offset in bitmap pack index");
243 recent_bitmaps
[i
% MAX_XOR_OFFSET
] = store_bitmap(
244 index
, bitmap
, sha1
, xor_bitmap
, flags
);
250 static char *pack_bitmap_filename(struct packed_git
*p
)
254 if (!strip_suffix(p
->pack_name
, ".pack", &len
))
255 die("BUG: pack_name does not end in .pack");
256 return xstrfmt("%.*s.bitmap", (int)len
, p
->pack_name
);
259 static int open_pack_bitmap_1(struct packed_git
*packfile
)
265 if (open_pack_index(packfile
))
268 idx_name
= pack_bitmap_filename(packfile
);
269 fd
= git_open(idx_name
);
275 if (fstat(fd
, &st
)) {
280 if (bitmap_git
.pack
) {
281 warning("ignoring extra bitmap file: %s", packfile
->pack_name
);
286 bitmap_git
.pack
= packfile
;
287 bitmap_git
.map_size
= xsize_t(st
.st_size
);
288 bitmap_git
.map
= xmmap(NULL
, bitmap_git
.map_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
289 bitmap_git
.map_pos
= 0;
292 if (load_bitmap_header(&bitmap_git
) < 0) {
293 munmap(bitmap_git
.map
, bitmap_git
.map_size
);
294 bitmap_git
.map
= NULL
;
295 bitmap_git
.map_size
= 0;
302 static int load_pack_bitmap(void)
304 assert(bitmap_git
.map
&& !bitmap_git
.loaded
);
306 bitmap_git
.bitmaps
= kh_init_sha1();
307 bitmap_git
.ext_index
.positions
= kh_init_sha1_pos();
308 load_pack_revindex(bitmap_git
.pack
);
310 if (!(bitmap_git
.commits
= read_bitmap_1(&bitmap_git
)) ||
311 !(bitmap_git
.trees
= read_bitmap_1(&bitmap_git
)) ||
312 !(bitmap_git
.blobs
= read_bitmap_1(&bitmap_git
)) ||
313 !(bitmap_git
.tags
= read_bitmap_1(&bitmap_git
)))
316 if (load_bitmap_entries_v1(&bitmap_git
) < 0)
319 bitmap_git
.loaded
= 1;
323 munmap(bitmap_git
.map
, bitmap_git
.map_size
);
324 bitmap_git
.map
= NULL
;
325 bitmap_git
.map_size
= 0;
329 static int open_pack_bitmap(void)
331 struct packed_git
*p
;
334 assert(!bitmap_git
.map
&& !bitmap_git
.loaded
);
336 prepare_packed_git();
337 for (p
= packed_git
; p
; p
= p
->next
) {
338 if (open_pack_bitmap_1(p
) == 0)
345 int prepare_bitmap_git(void)
347 if (bitmap_git
.loaded
)
350 if (!open_pack_bitmap())
351 return load_pack_bitmap();
356 struct include_data
{
361 static inline int bitmap_position_extended(const unsigned char *sha1
)
363 khash_sha1_pos
*positions
= bitmap_git
.ext_index
.positions
;
364 khiter_t pos
= kh_get_sha1_pos(positions
, sha1
);
366 if (pos
< kh_end(positions
)) {
367 int bitmap_pos
= kh_value(positions
, pos
);
368 return bitmap_pos
+ bitmap_git
.pack
->num_objects
;
374 static inline int bitmap_position_packfile(const unsigned char *sha1
)
376 off_t offset
= find_pack_entry_one(sha1
, bitmap_git
.pack
);
380 return find_revindex_position(bitmap_git
.pack
, offset
);
383 static int bitmap_position(const unsigned char *sha1
)
385 int pos
= bitmap_position_packfile(sha1
);
386 return (pos
>= 0) ? pos
: bitmap_position_extended(sha1
);
389 static int ext_index_add_object(struct object
*object
, const char *name
)
391 struct eindex
*eindex
= &bitmap_git
.ext_index
;
397 hash_pos
= kh_put_sha1_pos(eindex
->positions
, object
->oid
.hash
, &hash_ret
);
399 if (eindex
->count
>= eindex
->alloc
) {
400 eindex
->alloc
= (eindex
->alloc
+ 16) * 3 / 2;
401 REALLOC_ARRAY(eindex
->objects
, eindex
->alloc
);
402 REALLOC_ARRAY(eindex
->hashes
, eindex
->alloc
);
405 bitmap_pos
= eindex
->count
;
406 eindex
->objects
[eindex
->count
] = object
;
407 eindex
->hashes
[eindex
->count
] = pack_name_hash(name
);
408 kh_value(eindex
->positions
, hash_pos
) = bitmap_pos
;
411 bitmap_pos
= kh_value(eindex
->positions
, hash_pos
);
414 return bitmap_pos
+ bitmap_git
.pack
->num_objects
;
417 static void show_object(struct object
*object
, const char *name
, void *data
)
419 struct bitmap
*base
= data
;
422 bitmap_pos
= bitmap_position(object
->oid
.hash
);
425 bitmap_pos
= ext_index_add_object(object
, name
);
427 bitmap_set(base
, bitmap_pos
);
430 static void show_commit(struct commit
*commit
, void *data
)
434 static int add_to_include_set(struct include_data
*data
,
435 const unsigned char *sha1
,
440 if (data
->seen
&& bitmap_get(data
->seen
, bitmap_pos
))
443 if (bitmap_get(data
->base
, bitmap_pos
))
446 hash_pos
= kh_get_sha1(bitmap_git
.bitmaps
, sha1
);
447 if (hash_pos
< kh_end(bitmap_git
.bitmaps
)) {
448 struct stored_bitmap
*st
= kh_value(bitmap_git
.bitmaps
, hash_pos
);
449 bitmap_or_ewah(data
->base
, lookup_stored_bitmap(st
));
453 bitmap_set(data
->base
, bitmap_pos
);
457 static int should_include(struct commit
*commit
, void *_data
)
459 struct include_data
*data
= _data
;
462 bitmap_pos
= bitmap_position(commit
->object
.oid
.hash
);
464 bitmap_pos
= ext_index_add_object((struct object
*)commit
, NULL
);
466 if (!add_to_include_set(data
, commit
->object
.oid
.hash
, bitmap_pos
)) {
467 struct commit_list
*parent
= commit
->parents
;
470 parent
->item
->object
.flags
|= SEEN
;
471 parent
= parent
->next
;
480 static struct bitmap
*find_objects(struct rev_info
*revs
,
481 struct object_list
*roots
,
484 struct bitmap
*base
= NULL
;
487 struct object_list
*not_mapped
= NULL
;
490 * Go through all the roots for the walk. The ones that have bitmaps
491 * on the bitmap index will be `or`ed together to form an initial
492 * global reachability analysis.
494 * The ones without bitmaps in the index will be stored in the
495 * `not_mapped_list` for further processing.
498 struct object
*object
= roots
->item
;
501 if (object
->type
== OBJ_COMMIT
) {
502 khiter_t pos
= kh_get_sha1(bitmap_git
.bitmaps
, object
->oid
.hash
);
504 if (pos
< kh_end(bitmap_git
.bitmaps
)) {
505 struct stored_bitmap
*st
= kh_value(bitmap_git
.bitmaps
, pos
);
506 struct ewah_bitmap
*or_with
= lookup_stored_bitmap(st
);
509 base
= ewah_to_bitmap(or_with
);
511 bitmap_or_ewah(base
, or_with
);
513 object
->flags
|= SEEN
;
518 object_list_insert(object
, ¬_mapped
);
522 * Best case scenario: We found bitmaps for all the roots,
523 * so the resulting `or` bitmap has the full reachability analysis
525 if (not_mapped
== NULL
)
531 * Let's iterate through all the roots that don't have bitmaps to
532 * check if we can determine them to be reachable from the existing
535 * If we cannot find them in the existing global bitmap, we'll need
536 * to push them to an actual walk and run it until we can confirm
540 struct object
*object
= roots
->item
;
544 pos
= bitmap_position(object
->oid
.hash
);
546 if (pos
< 0 || base
== NULL
|| !bitmap_get(base
, pos
)) {
547 object
->flags
&= ~UNINTERESTING
;
548 add_pending_object(revs
, object
, "");
551 object
->flags
|= SEEN
;
556 struct include_data incdata
;
564 revs
->include_check
= should_include
;
565 revs
->include_check_data
= &incdata
;
567 if (prepare_revision_walk(revs
))
568 die("revision walk setup failed");
570 traverse_commit_list(revs
, show_commit
, show_object
, base
);
576 static void show_extended_objects(struct bitmap
*objects
,
577 show_reachable_fn show_reach
)
579 struct eindex
*eindex
= &bitmap_git
.ext_index
;
582 for (i
= 0; i
< eindex
->count
; ++i
) {
585 if (!bitmap_get(objects
, bitmap_git
.pack
->num_objects
+ i
))
588 obj
= eindex
->objects
[i
];
589 show_reach(obj
->oid
.hash
, obj
->type
, 0, eindex
->hashes
[i
], NULL
, 0);
593 static void show_objects_for_type(
594 struct bitmap
*objects
,
595 struct ewah_bitmap
*type_filter
,
596 enum object_type object_type
,
597 show_reachable_fn show_reach
)
599 size_t pos
= 0, i
= 0;
602 struct ewah_iterator it
;
605 if (bitmap_git
.reuse_objects
== bitmap_git
.pack
->num_objects
)
608 ewah_iterator_init(&it
, type_filter
);
610 while (i
< objects
->word_alloc
&& ewah_iterator_next(&filter
, &it
)) {
611 eword_t word
= objects
->words
[i
] & filter
;
613 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
614 const unsigned char *sha1
;
615 struct revindex_entry
*entry
;
618 if ((word
>> offset
) == 0)
621 offset
+= ewah_bit_ctz64(word
>> offset
);
623 if (pos
+ offset
< bitmap_git
.reuse_objects
)
626 entry
= &bitmap_git
.pack
->revindex
[pos
+ offset
];
627 sha1
= nth_packed_object_sha1(bitmap_git
.pack
, entry
->nr
);
629 if (bitmap_git
.hashes
)
630 hash
= get_be32(bitmap_git
.hashes
+ entry
->nr
);
632 show_reach(sha1
, object_type
, 0, hash
, bitmap_git
.pack
, entry
->offset
);
635 pos
+= BITS_IN_EWORD
;
640 static int in_bitmapped_pack(struct object_list
*roots
)
643 struct object
*object
= roots
->item
;
646 if (find_pack_entry_one(object
->oid
.hash
, bitmap_git
.pack
) > 0)
653 int prepare_bitmap_walk(struct rev_info
*revs
)
656 unsigned int pending_nr
= revs
->pending
.nr
;
657 struct object_array_entry
*pending_e
= revs
->pending
.objects
;
659 struct object_list
*wants
= NULL
;
660 struct object_list
*haves
= NULL
;
662 struct bitmap
*wants_bitmap
= NULL
;
663 struct bitmap
*haves_bitmap
= NULL
;
665 if (!bitmap_git
.loaded
) {
666 /* try to open a bitmapped pack, but don't parse it yet
667 * because we may not need to use it */
668 if (open_pack_bitmap() < 0)
672 for (i
= 0; i
< pending_nr
; ++i
) {
673 struct object
*object
= pending_e
[i
].item
;
675 if (object
->type
== OBJ_NONE
)
676 parse_object_or_die(&object
->oid
, NULL
);
678 while (object
->type
== OBJ_TAG
) {
679 struct tag
*tag
= (struct tag
*) object
;
681 if (object
->flags
& UNINTERESTING
)
682 object_list_insert(object
, &haves
);
684 object_list_insert(object
, &wants
);
688 object
= parse_object_or_die(&tag
->tagged
->oid
, NULL
);
691 if (object
->flags
& UNINTERESTING
)
692 object_list_insert(object
, &haves
);
694 object_list_insert(object
, &wants
);
698 * if we have a HAVES list, but none of those haves is contained
699 * in the packfile that has a bitmap, we don't have anything to
702 if (haves
&& !in_bitmapped_pack(haves
))
705 /* if we don't want anything, we're done here */
710 * now we're going to use bitmaps, so load the actual bitmap entries
711 * from disk. this is the point of no return; after this the rev_list
712 * becomes invalidated and we must perform the revwalk through bitmaps
714 if (!bitmap_git
.loaded
&& load_pack_bitmap() < 0)
717 revs
->pending
.nr
= 0;
718 revs
->pending
.alloc
= 0;
719 revs
->pending
.objects
= NULL
;
722 revs
->ignore_missing_links
= 1;
723 haves_bitmap
= find_objects(revs
, haves
, NULL
);
724 reset_revision_walk();
725 revs
->ignore_missing_links
= 0;
727 if (haves_bitmap
== NULL
)
728 die("BUG: failed to perform bitmap walk");
731 wants_bitmap
= find_objects(revs
, wants
, haves_bitmap
);
734 die("BUG: failed to perform bitmap walk");
737 bitmap_and_not(wants_bitmap
, haves_bitmap
);
739 bitmap_git
.result
= wants_bitmap
;
741 bitmap_free(haves_bitmap
);
745 int reuse_partial_packfile_from_bitmap(struct packed_git
**packfile
,
750 * Reuse the packfile content if we need more than
753 static const double REUSE_PERCENT
= 0.9;
755 struct bitmap
*result
= bitmap_git
.result
;
756 uint32_t reuse_threshold
;
757 uint32_t i
, reuse_objects
= 0;
761 for (i
= 0; i
< result
->word_alloc
; ++i
) {
762 if (result
->words
[i
] != (eword_t
)~0) {
763 reuse_objects
+= ewah_bit_ctz64(~result
->words
[i
]);
767 reuse_objects
+= BITS_IN_EWORD
;
770 #ifdef GIT_BITMAP_DEBUG
772 const unsigned char *sha1
;
773 struct revindex_entry
*entry
;
775 entry
= &bitmap_git
.reverse_index
->revindex
[reuse_objects
];
776 sha1
= nth_packed_object_sha1(bitmap_git
.pack
, entry
->nr
);
778 fprintf(stderr
, "Failed to reuse at %d (%016llx)\n",
779 reuse_objects
, result
->words
[i
]);
780 fprintf(stderr
, " %s\n", sha1_to_hex(sha1
));
787 if (reuse_objects
>= bitmap_git
.pack
->num_objects
) {
788 bitmap_git
.reuse_objects
= *entries
= bitmap_git
.pack
->num_objects
;
789 *up_to
= -1; /* reuse the full pack */
790 *packfile
= bitmap_git
.pack
;
794 reuse_threshold
= bitmap_popcount(bitmap_git
.result
) * REUSE_PERCENT
;
796 if (reuse_objects
< reuse_threshold
)
799 bitmap_git
.reuse_objects
= *entries
= reuse_objects
;
800 *up_to
= bitmap_git
.pack
->revindex
[reuse_objects
].offset
;
801 *packfile
= bitmap_git
.pack
;
806 void traverse_bitmap_commit_list(show_reachable_fn show_reachable
)
808 assert(bitmap_git
.result
);
810 show_objects_for_type(bitmap_git
.result
, bitmap_git
.commits
,
811 OBJ_COMMIT
, show_reachable
);
812 show_objects_for_type(bitmap_git
.result
, bitmap_git
.trees
,
813 OBJ_TREE
, show_reachable
);
814 show_objects_for_type(bitmap_git
.result
, bitmap_git
.blobs
,
815 OBJ_BLOB
, show_reachable
);
816 show_objects_for_type(bitmap_git
.result
, bitmap_git
.tags
,
817 OBJ_TAG
, show_reachable
);
819 show_extended_objects(bitmap_git
.result
, show_reachable
);
821 bitmap_free(bitmap_git
.result
);
822 bitmap_git
.result
= NULL
;
825 static uint32_t count_object_type(struct bitmap
*objects
,
826 enum object_type type
)
828 struct eindex
*eindex
= &bitmap_git
.ext_index
;
830 uint32_t i
= 0, count
= 0;
831 struct ewah_iterator it
;
836 ewah_iterator_init(&it
, bitmap_git
.commits
);
840 ewah_iterator_init(&it
, bitmap_git
.trees
);
844 ewah_iterator_init(&it
, bitmap_git
.blobs
);
848 ewah_iterator_init(&it
, bitmap_git
.tags
);
855 while (i
< objects
->word_alloc
&& ewah_iterator_next(&filter
, &it
)) {
856 eword_t word
= objects
->words
[i
++] & filter
;
857 count
+= ewah_bit_popcount64(word
);
860 for (i
= 0; i
< eindex
->count
; ++i
) {
861 if (eindex
->objects
[i
]->type
== type
&&
862 bitmap_get(objects
, bitmap_git
.pack
->num_objects
+ i
))
869 void count_bitmap_commit_list(uint32_t *commits
, uint32_t *trees
,
870 uint32_t *blobs
, uint32_t *tags
)
872 assert(bitmap_git
.result
);
875 *commits
= count_object_type(bitmap_git
.result
, OBJ_COMMIT
);
878 *trees
= count_object_type(bitmap_git
.result
, OBJ_TREE
);
881 *blobs
= count_object_type(bitmap_git
.result
, OBJ_BLOB
);
884 *tags
= count_object_type(bitmap_git
.result
, OBJ_TAG
);
887 struct bitmap_test_data
{
889 struct progress
*prg
;
893 static void test_show_object(struct object
*object
, const char *name
,
896 struct bitmap_test_data
*tdata
= data
;
899 bitmap_pos
= bitmap_position(object
->oid
.hash
);
901 die("Object not in bitmap: %s\n", oid_to_hex(&object
->oid
));
903 bitmap_set(tdata
->base
, bitmap_pos
);
904 display_progress(tdata
->prg
, ++tdata
->seen
);
907 static void test_show_commit(struct commit
*commit
, void *data
)
909 struct bitmap_test_data
*tdata
= data
;
912 bitmap_pos
= bitmap_position(commit
->object
.oid
.hash
);
914 die("Object not in bitmap: %s\n", oid_to_hex(&commit
->object
.oid
));
916 bitmap_set(tdata
->base
, bitmap_pos
);
917 display_progress(tdata
->prg
, ++tdata
->seen
);
920 void test_bitmap_walk(struct rev_info
*revs
)
923 struct bitmap
*result
= NULL
;
925 size_t result_popcnt
;
926 struct bitmap_test_data tdata
;
928 if (prepare_bitmap_git())
929 die("failed to load bitmap indexes");
931 if (revs
->pending
.nr
!= 1)
932 die("you must specify exactly one commit to test");
934 fprintf(stderr
, "Bitmap v%d test (%d entries loaded)\n",
935 bitmap_git
.version
, bitmap_git
.entry_count
);
937 root
= revs
->pending
.objects
[0].item
;
938 pos
= kh_get_sha1(bitmap_git
.bitmaps
, root
->oid
.hash
);
940 if (pos
< kh_end(bitmap_git
.bitmaps
)) {
941 struct stored_bitmap
*st
= kh_value(bitmap_git
.bitmaps
, pos
);
942 struct ewah_bitmap
*bm
= lookup_stored_bitmap(st
);
944 fprintf(stderr
, "Found bitmap for %s. %d bits / %08x checksum\n",
945 oid_to_hex(&root
->oid
), (int)bm
->bit_size
, ewah_checksum(bm
));
947 result
= ewah_to_bitmap(bm
);
951 die("Commit %s doesn't have an indexed bitmap", oid_to_hex(&root
->oid
));
953 revs
->tag_objects
= 1;
954 revs
->tree_objects
= 1;
955 revs
->blob_objects
= 1;
957 result_popcnt
= bitmap_popcount(result
);
959 if (prepare_revision_walk(revs
))
960 die("revision walk setup failed");
962 tdata
.base
= bitmap_new();
963 tdata
.prg
= start_progress("Verifying bitmap entries", result_popcnt
);
966 traverse_commit_list(revs
, &test_show_commit
, &test_show_object
, &tdata
);
968 stop_progress(&tdata
.prg
);
970 if (bitmap_equals(result
, tdata
.base
))
971 fprintf(stderr
, "OK!\n");
973 fprintf(stderr
, "Mismatch!\n");
978 static int rebuild_bitmap(uint32_t *reposition
,
979 struct ewah_bitmap
*source
,
983 struct ewah_iterator it
;
986 ewah_iterator_init(&it
, source
);
988 while (ewah_iterator_next(&word
, &it
)) {
989 uint32_t offset
, bit_pos
;
991 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
992 if ((word
>> offset
) == 0)
995 offset
+= ewah_bit_ctz64(word
>> offset
);
997 bit_pos
= reposition
[pos
+ offset
];
999 bitmap_set(dest
, bit_pos
- 1);
1000 else /* can't reuse, we don't have the object */
1004 pos
+= BITS_IN_EWORD
;
1009 int rebuild_existing_bitmaps(struct packing_data
*mapping
,
1010 khash_sha1
*reused_bitmaps
,
1013 uint32_t i
, num_objects
;
1014 uint32_t *reposition
;
1015 struct bitmap
*rebuild
;
1016 struct stored_bitmap
*stored
;
1017 struct progress
*progress
= NULL
;
1022 if (prepare_bitmap_git() < 0)
1025 num_objects
= bitmap_git
.pack
->num_objects
;
1026 reposition
= xcalloc(num_objects
, sizeof(uint32_t));
1028 for (i
= 0; i
< num_objects
; ++i
) {
1029 const unsigned char *sha1
;
1030 struct revindex_entry
*entry
;
1031 struct object_entry
*oe
;
1033 entry
= &bitmap_git
.pack
->revindex
[i
];
1034 sha1
= nth_packed_object_sha1(bitmap_git
.pack
, entry
->nr
);
1035 oe
= packlist_find(mapping
, sha1
, NULL
);
1038 reposition
[i
] = oe
->in_pack_pos
+ 1;
1041 rebuild
= bitmap_new();
1045 progress
= start_progress("Reusing bitmaps", 0);
1047 kh_foreach_value(bitmap_git
.bitmaps
, stored
, {
1048 if (stored
->flags
& BITMAP_FLAG_REUSE
) {
1049 if (!rebuild_bitmap(reposition
,
1050 lookup_stored_bitmap(stored
),
1052 hash_pos
= kh_put_sha1(reused_bitmaps
,
1055 kh_value(reused_bitmaps
, hash_pos
) =
1056 bitmap_to_ewah(rebuild
);
1058 bitmap_reset(rebuild
);
1059 display_progress(progress
, ++i
);
1063 stop_progress(&progress
);
1066 bitmap_free(rebuild
);