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
)
657 struct object_list
*wants
= NULL
;
658 struct object_list
*haves
= NULL
;
660 struct bitmap
*wants_bitmap
= NULL
;
661 struct bitmap
*haves_bitmap
= NULL
;
663 if (!bitmap_git
.loaded
) {
664 /* try to open a bitmapped pack, but don't parse it yet
665 * because we may not need to use it */
666 if (open_pack_bitmap() < 0)
670 for (i
= 0; i
< revs
->pending
.nr
; ++i
) {
671 struct object
*object
= revs
->pending
.objects
[i
].item
;
673 if (object
->type
== OBJ_NONE
)
674 parse_object_or_die(&object
->oid
, NULL
);
676 while (object
->type
== OBJ_TAG
) {
677 struct tag
*tag
= (struct tag
*) object
;
679 if (object
->flags
& UNINTERESTING
)
680 object_list_insert(object
, &haves
);
682 object_list_insert(object
, &wants
);
686 object
= parse_object_or_die(&tag
->tagged
->oid
, NULL
);
689 if (object
->flags
& UNINTERESTING
)
690 object_list_insert(object
, &haves
);
692 object_list_insert(object
, &wants
);
696 * if we have a HAVES list, but none of those haves is contained
697 * in the packfile that has a bitmap, we don't have anything to
700 if (haves
&& !in_bitmapped_pack(haves
))
703 /* if we don't want anything, we're done here */
708 * now we're going to use bitmaps, so load the actual bitmap entries
709 * from disk. this is the point of no return; after this the rev_list
710 * becomes invalidated and we must perform the revwalk through bitmaps
712 if (!bitmap_git
.loaded
&& load_pack_bitmap() < 0)
715 object_array_clear(&revs
->pending
);
718 revs
->ignore_missing_links
= 1;
719 haves_bitmap
= find_objects(revs
, haves
, NULL
);
720 reset_revision_walk();
721 revs
->ignore_missing_links
= 0;
723 if (haves_bitmap
== NULL
)
724 die("BUG: failed to perform bitmap walk");
727 wants_bitmap
= find_objects(revs
, wants
, haves_bitmap
);
730 die("BUG: failed to perform bitmap walk");
733 bitmap_and_not(wants_bitmap
, haves_bitmap
);
735 bitmap_git
.result
= wants_bitmap
;
737 bitmap_free(haves_bitmap
);
741 int reuse_partial_packfile_from_bitmap(struct packed_git
**packfile
,
746 * Reuse the packfile content if we need more than
749 static const double REUSE_PERCENT
= 0.9;
751 struct bitmap
*result
= bitmap_git
.result
;
752 uint32_t reuse_threshold
;
753 uint32_t i
, reuse_objects
= 0;
757 for (i
= 0; i
< result
->word_alloc
; ++i
) {
758 if (result
->words
[i
] != (eword_t
)~0) {
759 reuse_objects
+= ewah_bit_ctz64(~result
->words
[i
]);
763 reuse_objects
+= BITS_IN_EWORD
;
766 #ifdef GIT_BITMAP_DEBUG
768 const unsigned char *sha1
;
769 struct revindex_entry
*entry
;
771 entry
= &bitmap_git
.reverse_index
->revindex
[reuse_objects
];
772 sha1
= nth_packed_object_sha1(bitmap_git
.pack
, entry
->nr
);
774 fprintf(stderr
, "Failed to reuse at %d (%016llx)\n",
775 reuse_objects
, result
->words
[i
]);
776 fprintf(stderr
, " %s\n", sha1_to_hex(sha1
));
783 if (reuse_objects
>= bitmap_git
.pack
->num_objects
) {
784 bitmap_git
.reuse_objects
= *entries
= bitmap_git
.pack
->num_objects
;
785 *up_to
= -1; /* reuse the full pack */
786 *packfile
= bitmap_git
.pack
;
790 reuse_threshold
= bitmap_popcount(bitmap_git
.result
) * REUSE_PERCENT
;
792 if (reuse_objects
< reuse_threshold
)
795 bitmap_git
.reuse_objects
= *entries
= reuse_objects
;
796 *up_to
= bitmap_git
.pack
->revindex
[reuse_objects
].offset
;
797 *packfile
= bitmap_git
.pack
;
802 void traverse_bitmap_commit_list(show_reachable_fn show_reachable
)
804 assert(bitmap_git
.result
);
806 show_objects_for_type(bitmap_git
.result
, bitmap_git
.commits
,
807 OBJ_COMMIT
, show_reachable
);
808 show_objects_for_type(bitmap_git
.result
, bitmap_git
.trees
,
809 OBJ_TREE
, show_reachable
);
810 show_objects_for_type(bitmap_git
.result
, bitmap_git
.blobs
,
811 OBJ_BLOB
, show_reachable
);
812 show_objects_for_type(bitmap_git
.result
, bitmap_git
.tags
,
813 OBJ_TAG
, show_reachable
);
815 show_extended_objects(bitmap_git
.result
, show_reachable
);
817 bitmap_free(bitmap_git
.result
);
818 bitmap_git
.result
= NULL
;
821 static uint32_t count_object_type(struct bitmap
*objects
,
822 enum object_type type
)
824 struct eindex
*eindex
= &bitmap_git
.ext_index
;
826 uint32_t i
= 0, count
= 0;
827 struct ewah_iterator it
;
832 ewah_iterator_init(&it
, bitmap_git
.commits
);
836 ewah_iterator_init(&it
, bitmap_git
.trees
);
840 ewah_iterator_init(&it
, bitmap_git
.blobs
);
844 ewah_iterator_init(&it
, bitmap_git
.tags
);
851 while (i
< objects
->word_alloc
&& ewah_iterator_next(&filter
, &it
)) {
852 eword_t word
= objects
->words
[i
++] & filter
;
853 count
+= ewah_bit_popcount64(word
);
856 for (i
= 0; i
< eindex
->count
; ++i
) {
857 if (eindex
->objects
[i
]->type
== type
&&
858 bitmap_get(objects
, bitmap_git
.pack
->num_objects
+ i
))
865 void count_bitmap_commit_list(uint32_t *commits
, uint32_t *trees
,
866 uint32_t *blobs
, uint32_t *tags
)
868 assert(bitmap_git
.result
);
871 *commits
= count_object_type(bitmap_git
.result
, OBJ_COMMIT
);
874 *trees
= count_object_type(bitmap_git
.result
, OBJ_TREE
);
877 *blobs
= count_object_type(bitmap_git
.result
, OBJ_BLOB
);
880 *tags
= count_object_type(bitmap_git
.result
, OBJ_TAG
);
883 struct bitmap_test_data
{
885 struct progress
*prg
;
889 static void test_show_object(struct object
*object
, const char *name
,
892 struct bitmap_test_data
*tdata
= data
;
895 bitmap_pos
= bitmap_position(object
->oid
.hash
);
897 die("Object not in bitmap: %s\n", oid_to_hex(&object
->oid
));
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
.oid
.hash
);
910 die("Object not in bitmap: %s\n", oid_to_hex(&commit
->object
.oid
));
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
->oid
.hash
);
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 oid_to_hex(&root
->oid
), (int)bm
->bit_size
, ewah_checksum(bm
));
943 result
= ewah_to_bitmap(bm
);
947 die("Commit %s doesn't have an indexed bitmap", oid_to_hex(&root
->oid
));
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");
974 static int rebuild_bitmap(uint32_t *reposition
,
975 struct ewah_bitmap
*source
,
979 struct ewah_iterator it
;
982 ewah_iterator_init(&it
, source
);
984 while (ewah_iterator_next(&word
, &it
)) {
985 uint32_t offset
, bit_pos
;
987 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
988 if ((word
>> offset
) == 0)
991 offset
+= ewah_bit_ctz64(word
>> offset
);
993 bit_pos
= reposition
[pos
+ offset
];
995 bitmap_set(dest
, bit_pos
- 1);
996 else /* can't reuse, we don't have the object */
1000 pos
+= BITS_IN_EWORD
;
1005 int rebuild_existing_bitmaps(struct packing_data
*mapping
,
1006 khash_sha1
*reused_bitmaps
,
1009 uint32_t i
, num_objects
;
1010 uint32_t *reposition
;
1011 struct bitmap
*rebuild
;
1012 struct stored_bitmap
*stored
;
1013 struct progress
*progress
= NULL
;
1018 if (prepare_bitmap_git() < 0)
1021 num_objects
= bitmap_git
.pack
->num_objects
;
1022 reposition
= xcalloc(num_objects
, sizeof(uint32_t));
1024 for (i
= 0; i
< num_objects
; ++i
) {
1025 const unsigned char *sha1
;
1026 struct revindex_entry
*entry
;
1027 struct object_entry
*oe
;
1029 entry
= &bitmap_git
.pack
->revindex
[i
];
1030 sha1
= nth_packed_object_sha1(bitmap_git
.pack
, entry
->nr
);
1031 oe
= packlist_find(mapping
, sha1
, NULL
);
1034 reposition
[i
] = oe
->in_pack_pos
+ 1;
1037 rebuild
= bitmap_new();
1041 progress
= start_progress("Reusing bitmaps", 0);
1043 kh_foreach_value(bitmap_git
.bitmaps
, stored
, {
1044 if (stored
->flags
& BITMAP_FLAG_REUSE
) {
1045 if (!rebuild_bitmap(reposition
,
1046 lookup_stored_bitmap(stored
),
1048 hash_pos
= kh_put_sha1(reused_bitmaps
,
1051 kh_value(reused_bitmaps
, hash_pos
) =
1052 bitmap_to_ewah(rebuild
);
1054 bitmap_reset(rebuild
);
1055 display_progress(progress
, ++i
);
1059 stop_progress(&progress
);
1062 bitmap_free(rebuild
);