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
;
36 /* reverse index for the packfile */
37 struct pack_revindex
*reverse_index
;
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 SHA1 -> `stored_bitmap` for all the bitmapped comits */
66 /* Number of bitmapped commits */
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)");
157 index
->entry_count
= ntohl(header
->entry_count
);
158 index
->map_pos
+= sizeof(*header
);
162 static struct stored_bitmap
*store_bitmap(struct bitmap_index
*index
,
163 struct ewah_bitmap
*root
,
164 const unsigned char *sha1
,
165 struct stored_bitmap
*xor_with
,
168 struct stored_bitmap
*stored
;
172 stored
= xmalloc(sizeof(struct stored_bitmap
));
174 stored
->xor = xor_with
;
175 stored
->flags
= flags
;
176 hashcpy(stored
->sha1
, sha1
);
178 hash_pos
= kh_put_sha1(index
->bitmaps
, stored
->sha1
, &ret
);
180 /* a 0 return code means the insertion succeeded with no changes,
181 * because the SHA1 already existed on the map. this is bad, there
182 * shouldn't be duplicated commits in the index */
184 error("Duplicate entry in bitmap index: %s", sha1_to_hex(sha1
));
188 kh_value(index
->bitmaps
, hash_pos
) = stored
;
192 static int load_bitmap_entries_v1(struct bitmap_index
*index
)
194 static const size_t MAX_XOR_OFFSET
= 160;
197 struct stored_bitmap
**recent_bitmaps
;
198 struct bitmap_disk_entry
*entry
;
200 recent_bitmaps
= xcalloc(MAX_XOR_OFFSET
, sizeof(struct stored_bitmap
));
202 for (i
= 0; i
< index
->entry_count
; ++i
) {
203 int xor_offset
, flags
;
204 struct ewah_bitmap
*bitmap
= NULL
;
205 struct stored_bitmap
*xor_bitmap
= NULL
;
206 uint32_t commit_idx_pos
;
207 const unsigned char *sha1
;
209 entry
= (struct bitmap_disk_entry
*)(index
->map
+ index
->map_pos
);
210 index
->map_pos
+= sizeof(struct bitmap_disk_entry
);
212 commit_idx_pos
= ntohl(entry
->object_pos
);
213 sha1
= nth_packed_object_sha1(index
->pack
, commit_idx_pos
);
215 xor_offset
= (int)entry
->xor_offset
;
216 flags
= (int)entry
->flags
;
218 bitmap
= read_bitmap_1(index
);
222 if (xor_offset
> MAX_XOR_OFFSET
|| xor_offset
> i
)
223 return error("Corrupted bitmap pack index");
225 if (xor_offset
> 0) {
226 xor_bitmap
= recent_bitmaps
[(i
- xor_offset
) % MAX_XOR_OFFSET
];
228 if (xor_bitmap
== NULL
)
229 return error("Invalid XOR offset in bitmap pack index");
232 recent_bitmaps
[i
% MAX_XOR_OFFSET
] = store_bitmap(
233 index
, bitmap
, sha1
, xor_bitmap
, flags
);
239 static int open_pack_bitmap_1(struct packed_git
*packfile
)
245 if (open_pack_index(packfile
))
248 idx_name
= pack_bitmap_filename(packfile
);
249 fd
= git_open_noatime(idx_name
);
255 if (fstat(fd
, &st
)) {
260 if (bitmap_git
.pack
) {
261 warning("ignoring extra bitmap file: %s", packfile
->pack_name
);
266 bitmap_git
.pack
= packfile
;
267 bitmap_git
.map_size
= xsize_t(st
.st_size
);
268 bitmap_git
.map
= xmmap(NULL
, bitmap_git
.map_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
269 bitmap_git
.map_pos
= 0;
272 if (load_bitmap_header(&bitmap_git
) < 0) {
273 munmap(bitmap_git
.map
, bitmap_git
.map_size
);
274 bitmap_git
.map
= NULL
;
275 bitmap_git
.map_size
= 0;
282 static int load_pack_bitmap(void)
284 assert(bitmap_git
.map
&& !bitmap_git
.loaded
);
286 bitmap_git
.bitmaps
= kh_init_sha1();
287 bitmap_git
.ext_index
.positions
= kh_init_sha1_pos();
288 bitmap_git
.reverse_index
= revindex_for_pack(bitmap_git
.pack
);
290 if (!(bitmap_git
.commits
= read_bitmap_1(&bitmap_git
)) ||
291 !(bitmap_git
.trees
= read_bitmap_1(&bitmap_git
)) ||
292 !(bitmap_git
.blobs
= read_bitmap_1(&bitmap_git
)) ||
293 !(bitmap_git
.tags
= read_bitmap_1(&bitmap_git
)))
296 if (load_bitmap_entries_v1(&bitmap_git
) < 0)
299 bitmap_git
.loaded
= 1;
303 munmap(bitmap_git
.map
, bitmap_git
.map_size
);
304 bitmap_git
.map
= NULL
;
305 bitmap_git
.map_size
= 0;
309 char *pack_bitmap_filename(struct packed_git
*p
)
314 len
= strlen(p
->pack_name
) - strlen(".pack");
315 idx_name
= xmalloc(len
+ strlen(".bitmap") + 1);
317 memcpy(idx_name
, p
->pack_name
, len
);
318 memcpy(idx_name
+ len
, ".bitmap", strlen(".bitmap") + 1);
323 static int open_pack_bitmap(void)
325 struct packed_git
*p
;
328 assert(!bitmap_git
.map
&& !bitmap_git
.loaded
);
330 prepare_packed_git();
331 for (p
= packed_git
; p
; p
= p
->next
) {
332 if (open_pack_bitmap_1(p
) == 0)
339 int prepare_bitmap_git(void)
341 if (bitmap_git
.loaded
)
344 if (!open_pack_bitmap())
345 return load_pack_bitmap();
350 struct include_data
{
355 static inline int bitmap_position_extended(const unsigned char *sha1
)
357 khash_sha1_pos
*positions
= bitmap_git
.ext_index
.positions
;
358 khiter_t pos
= kh_get_sha1_pos(positions
, sha1
);
360 if (pos
< kh_end(positions
)) {
361 int bitmap_pos
= kh_value(positions
, pos
);
362 return bitmap_pos
+ bitmap_git
.pack
->num_objects
;
368 static inline int bitmap_position_packfile(const unsigned char *sha1
)
370 off_t offset
= find_pack_entry_one(sha1
, bitmap_git
.pack
);
374 return find_revindex_position(bitmap_git
.reverse_index
, offset
);
377 static int bitmap_position(const unsigned char *sha1
)
379 int pos
= bitmap_position_packfile(sha1
);
380 return (pos
>= 0) ? pos
: bitmap_position_extended(sha1
);
383 static int ext_index_add_object(struct object
*object
, const char *name
)
385 struct eindex
*eindex
= &bitmap_git
.ext_index
;
391 hash_pos
= kh_put_sha1_pos(eindex
->positions
, object
->sha1
, &hash_ret
);
393 if (eindex
->count
>= eindex
->alloc
) {
394 eindex
->alloc
= (eindex
->alloc
+ 16) * 3 / 2;
395 eindex
->objects
= xrealloc(eindex
->objects
,
396 eindex
->alloc
* sizeof(struct object
*));
397 eindex
->hashes
= xrealloc(eindex
->hashes
,
398 eindex
->alloc
* sizeof(uint32_t));
401 bitmap_pos
= eindex
->count
;
402 eindex
->objects
[eindex
->count
] = object
;
403 eindex
->hashes
[eindex
->count
] = pack_name_hash(name
);
404 kh_value(eindex
->positions
, hash_pos
) = bitmap_pos
;
407 bitmap_pos
= kh_value(eindex
->positions
, hash_pos
);
410 return bitmap_pos
+ bitmap_git
.pack
->num_objects
;
413 static void show_object(struct object
*object
, const struct name_path
*path
,
414 const char *last
, void *data
)
416 struct bitmap
*base
= data
;
419 bitmap_pos
= bitmap_position(object
->sha1
);
421 if (bitmap_pos
< 0) {
422 char *name
= path_name(path
, last
);
423 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
.sha1
);
464 bitmap_pos
= ext_index_add_object((struct object
*)commit
, NULL
);
466 if (!add_to_include_set(data
, commit
->object
.sha1
, 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
->sha1
);
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
->sha1
);
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
->sha1
, 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_WORD
; ++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
.reverse_index
->revindex
[pos
+ offset
];
627 sha1
= nth_packed_object_sha1(bitmap_git
.pack
, entry
->nr
);
629 show_reach(sha1
, object_type
, 0, hash
, bitmap_git
.pack
, entry
->offset
);
637 static int in_bitmapped_pack(struct object_list
*roots
)
640 struct object
*object
= roots
->item
;
643 if (find_pack_entry_one(object
->sha1
, bitmap_git
.pack
) > 0)
650 int prepare_bitmap_walk(struct rev_info
*revs
)
653 unsigned int pending_nr
= revs
->pending
.nr
;
654 struct object_array_entry
*pending_e
= revs
->pending
.objects
;
656 struct object_list
*wants
= NULL
;
657 struct object_list
*haves
= NULL
;
659 struct bitmap
*wants_bitmap
= NULL
;
660 struct bitmap
*haves_bitmap
= NULL
;
662 if (!bitmap_git
.loaded
) {
663 /* try to open a bitmapped pack, but don't parse it yet
664 * because we may not need to use it */
665 if (open_pack_bitmap() < 0)
669 for (i
= 0; i
< pending_nr
; ++i
) {
670 struct object
*object
= pending_e
[i
].item
;
672 if (object
->type
== OBJ_NONE
)
673 parse_object_or_die(object
->sha1
, NULL
);
675 while (object
->type
== OBJ_TAG
) {
676 struct tag
*tag
= (struct tag
*) object
;
678 if (object
->flags
& UNINTERESTING
)
679 object_list_insert(object
, &haves
);
681 object_list_insert(object
, &wants
);
685 object
= parse_object_or_die(tag
->tagged
->sha1
, NULL
);
688 if (object
->flags
& UNINTERESTING
)
689 object_list_insert(object
, &haves
);
691 object_list_insert(object
, &wants
);
695 * if we have a HAVES list, but none of those haves is contained
696 * in the packfile that has a bitmap, we don't have anything to
699 if (haves
&& !in_bitmapped_pack(haves
))
702 /* if we don't want anything, we're done here */
707 * now we're going to use bitmaps, so load the actual bitmap entries
708 * from disk. this is the point of no return; after this the rev_list
709 * becomes invalidated and we must perform the revwalk through bitmaps
711 if (!bitmap_git
.loaded
&& load_pack_bitmap() < 0)
714 revs
->pending
.nr
= 0;
715 revs
->pending
.alloc
= 0;
716 revs
->pending
.objects
= NULL
;
719 haves_bitmap
= find_objects(revs
, haves
, NULL
);
720 reset_revision_walk();
722 if (haves_bitmap
== NULL
)
723 die("BUG: failed to perform bitmap walk");
726 wants_bitmap
= find_objects(revs
, wants
, haves_bitmap
);
729 die("BUG: failed to perform bitmap walk");
732 bitmap_and_not(wants_bitmap
, haves_bitmap
);
734 bitmap_git
.result
= wants_bitmap
;
736 bitmap_free(haves_bitmap
);
740 int reuse_partial_packfile_from_bitmap(struct packed_git
**packfile
,
745 * Reuse the packfile content if we need more than
748 static const double REUSE_PERCENT
= 0.9;
750 struct bitmap
*result
= bitmap_git
.result
;
751 uint32_t reuse_threshold
;
752 uint32_t i
, reuse_objects
= 0;
756 for (i
= 0; i
< result
->word_alloc
; ++i
) {
757 if (result
->words
[i
] != (eword_t
)~0) {
758 reuse_objects
+= ewah_bit_ctz64(~result
->words
[i
]);
762 reuse_objects
+= BITS_IN_WORD
;
765 #ifdef GIT_BITMAP_DEBUG
767 const unsigned char *sha1
;
768 struct revindex_entry
*entry
;
770 entry
= &bitmap_git
.reverse_index
->revindex
[reuse_objects
];
771 sha1
= nth_packed_object_sha1(bitmap_git
.pack
, entry
->nr
);
773 fprintf(stderr
, "Failed to reuse at %d (%016llx)\n",
774 reuse_objects
, result
->words
[i
]);
775 fprintf(stderr
, " %s\n", sha1_to_hex(sha1
));
782 if (reuse_objects
>= bitmap_git
.pack
->num_objects
) {
783 bitmap_git
.reuse_objects
= *entries
= bitmap_git
.pack
->num_objects
;
784 *up_to
= -1; /* reuse the full pack */
785 *packfile
= bitmap_git
.pack
;
789 reuse_threshold
= bitmap_popcount(bitmap_git
.result
) * REUSE_PERCENT
;
791 if (reuse_objects
< reuse_threshold
)
794 bitmap_git
.reuse_objects
= *entries
= reuse_objects
;
795 *up_to
= bitmap_git
.reverse_index
->revindex
[reuse_objects
].offset
;
796 *packfile
= bitmap_git
.pack
;
801 void traverse_bitmap_commit_list(show_reachable_fn show_reachable
)
803 assert(bitmap_git
.result
);
805 show_objects_for_type(bitmap_git
.result
, bitmap_git
.commits
,
806 OBJ_COMMIT
, show_reachable
);
807 show_objects_for_type(bitmap_git
.result
, bitmap_git
.trees
,
808 OBJ_TREE
, show_reachable
);
809 show_objects_for_type(bitmap_git
.result
, bitmap_git
.blobs
,
810 OBJ_BLOB
, show_reachable
);
811 show_objects_for_type(bitmap_git
.result
, bitmap_git
.tags
,
812 OBJ_TAG
, show_reachable
);
814 show_extended_objects(bitmap_git
.result
, show_reachable
);
816 bitmap_free(bitmap_git
.result
);
817 bitmap_git
.result
= NULL
;
820 static uint32_t count_object_type(struct bitmap
*objects
,
821 enum object_type type
)
823 struct eindex
*eindex
= &bitmap_git
.ext_index
;
825 uint32_t i
= 0, count
= 0;
826 struct ewah_iterator it
;
831 ewah_iterator_init(&it
, bitmap_git
.commits
);
835 ewah_iterator_init(&it
, bitmap_git
.trees
);
839 ewah_iterator_init(&it
, bitmap_git
.blobs
);
843 ewah_iterator_init(&it
, bitmap_git
.tags
);
850 while (i
< objects
->word_alloc
&& ewah_iterator_next(&filter
, &it
)) {
851 eword_t word
= objects
->words
[i
++] & filter
;
852 count
+= ewah_bit_popcount64(word
);
855 for (i
= 0; i
< eindex
->count
; ++i
) {
856 if (eindex
->objects
[i
]->type
== type
&&
857 bitmap_get(objects
, bitmap_git
.pack
->num_objects
+ i
))
864 void count_bitmap_commit_list(uint32_t *commits
, uint32_t *trees
,
865 uint32_t *blobs
, uint32_t *tags
)
867 assert(bitmap_git
.result
);
870 *commits
= count_object_type(bitmap_git
.result
, OBJ_COMMIT
);
873 *trees
= count_object_type(bitmap_git
.result
, OBJ_TREE
);
876 *blobs
= count_object_type(bitmap_git
.result
, OBJ_BLOB
);
879 *tags
= count_object_type(bitmap_git
.result
, OBJ_TAG
);
882 struct bitmap_test_data
{
884 struct progress
*prg
;
888 static void test_show_object(struct object
*object
,
889 const struct name_path
*path
,
890 const char *last
, void *data
)
892 struct bitmap_test_data
*tdata
= data
;
895 bitmap_pos
= bitmap_position(object
->sha1
);
897 die("Object not in bitmap: %s\n", sha1_to_hex(object
->sha1
));
899 bitmap_set(tdata
->base
, bitmap_pos
);
900 display_progress(tdata
->prg
, ++tdata
->seen
);
903 static void test_show_commit(struct commit
*commit
, void *data
)
905 struct bitmap_test_data
*tdata
= data
;
908 bitmap_pos
= bitmap_position(commit
->object
.sha1
);
910 die("Object not in bitmap: %s\n", sha1_to_hex(commit
->object
.sha1
));
912 bitmap_set(tdata
->base
, bitmap_pos
);
913 display_progress(tdata
->prg
, ++tdata
->seen
);
916 void test_bitmap_walk(struct rev_info
*revs
)
919 struct bitmap
*result
= NULL
;
921 size_t result_popcnt
;
922 struct bitmap_test_data tdata
;
924 if (prepare_bitmap_git())
925 die("failed to load bitmap indexes");
927 if (revs
->pending
.nr
!= 1)
928 die("you must specify exactly one commit to test");
930 fprintf(stderr
, "Bitmap v%d test (%d entries loaded)\n",
931 bitmap_git
.version
, bitmap_git
.entry_count
);
933 root
= revs
->pending
.objects
[0].item
;
934 pos
= kh_get_sha1(bitmap_git
.bitmaps
, root
->sha1
);
936 if (pos
< kh_end(bitmap_git
.bitmaps
)) {
937 struct stored_bitmap
*st
= kh_value(bitmap_git
.bitmaps
, pos
);
938 struct ewah_bitmap
*bm
= lookup_stored_bitmap(st
);
940 fprintf(stderr
, "Found bitmap for %s. %d bits / %08x checksum\n",
941 sha1_to_hex(root
->sha1
), (int)bm
->bit_size
, ewah_checksum(bm
));
943 result
= ewah_to_bitmap(bm
);
947 die("Commit %s doesn't have an indexed bitmap", sha1_to_hex(root
->sha1
));
949 revs
->tag_objects
= 1;
950 revs
->tree_objects
= 1;
951 revs
->blob_objects
= 1;
953 result_popcnt
= bitmap_popcount(result
);
955 if (prepare_revision_walk(revs
))
956 die("revision walk setup failed");
958 tdata
.base
= bitmap_new();
959 tdata
.prg
= start_progress("Verifying bitmap entries", result_popcnt
);
962 traverse_commit_list(revs
, &test_show_commit
, &test_show_object
, &tdata
);
964 stop_progress(&tdata
.prg
);
966 if (bitmap_equals(result
, tdata
.base
))
967 fprintf(stderr
, "OK!\n");
969 fprintf(stderr
, "Mismatch!\n");
972 static int rebuild_bitmap(uint32_t *reposition
,
973 struct ewah_bitmap
*source
,
977 struct ewah_iterator it
;
980 ewah_iterator_init(&it
, source
);
982 while (ewah_iterator_next(&word
, &it
)) {
983 uint32_t offset
, bit_pos
;
985 for (offset
= 0; offset
< BITS_IN_WORD
; ++offset
) {
986 if ((word
>> offset
) == 0)
989 offset
+= ewah_bit_ctz64(word
>> offset
);
991 bit_pos
= reposition
[pos
+ offset
];
993 bitmap_set(dest
, bit_pos
- 1);
994 else /* can't reuse, we don't have the object */
1003 int rebuild_existing_bitmaps(struct packing_data
*mapping
,
1004 khash_sha1
*reused_bitmaps
,
1007 uint32_t i
, num_objects
;
1008 uint32_t *reposition
;
1009 struct bitmap
*rebuild
;
1010 struct stored_bitmap
*stored
;
1011 struct progress
*progress
= NULL
;
1016 if (prepare_bitmap_git() < 0)
1019 num_objects
= bitmap_git
.pack
->num_objects
;
1020 reposition
= xcalloc(num_objects
, sizeof(uint32_t));
1022 for (i
= 0; i
< num_objects
; ++i
) {
1023 const unsigned char *sha1
;
1024 struct revindex_entry
*entry
;
1025 struct object_entry
*oe
;
1027 entry
= &bitmap_git
.reverse_index
->revindex
[i
];
1028 sha1
= nth_packed_object_sha1(bitmap_git
.pack
, entry
->nr
);
1029 oe
= packlist_find(mapping
, sha1
, NULL
);
1032 reposition
[i
] = oe
->in_pack_pos
+ 1;
1035 rebuild
= bitmap_new();
1039 progress
= start_progress("Reusing bitmaps", 0);
1041 kh_foreach_value(bitmap_git
.bitmaps
, stored
, {
1042 if (stored
->flags
& BITMAP_FLAG_REUSE
) {
1043 if (!rebuild_bitmap(reposition
,
1044 lookup_stored_bitmap(stored
),
1046 hash_pos
= kh_put_sha1(reused_bitmaps
,
1049 kh_value(reused_bitmaps
, hash_pos
) =
1050 bitmap_to_ewah(rebuild
);
1052 bitmap_reset(rebuild
);
1053 display_progress(progress
, ++i
);
1057 stop_progress(&progress
);
1060 bitmap_free(rebuild
);