7 #include "list-objects.h"
9 #include "pack-bitmap.h"
10 #include "pack-revindex.h"
11 #include "pack-objects.h"
13 #include "repository.h"
14 #include "object-store.h"
17 * An entry on the bitmap index, representing the bitmap for a given
20 struct stored_bitmap
{
21 unsigned char sha1
[20];
22 struct ewah_bitmap
*root
;
23 struct stored_bitmap
*xor;
28 * The active bitmap index for a repository. By design, repositories only have
29 * a single bitmap index available (the index for the biggest packfile in
30 * the repository), since bitmap indexes need full closure.
32 * If there is more than one bitmap index available (e.g. because of alternates),
33 * the active bitmap index is the largest one.
36 /* Packfile to which this bitmap index belongs to */
37 struct packed_git
*pack
;
40 * Mark the first `reuse_objects` in the packfile as reused:
41 * they will be sent as-is without using them for repacking
44 uint32_t reuse_objects
;
46 /* mmapped buffer of the whole bitmap index */
48 size_t map_size
; /* size of the mmaped buffer */
49 size_t map_pos
; /* current position when loading the index */
54 * Each bitmap marks which objects in the packfile are of the given
55 * type. This provides type information when yielding the objects from
56 * the packfile during a walk, which allows for better delta bases.
58 struct ewah_bitmap
*commits
;
59 struct ewah_bitmap
*trees
;
60 struct ewah_bitmap
*blobs
;
61 struct ewah_bitmap
*tags
;
63 /* Map from SHA1 -> `stored_bitmap` for all the bitmapped commits */
66 /* Number of bitmapped commits */
69 /* If not NULL, this is a name-hash cache pointing into map. */
75 * When trying to perform bitmap operations with objects that are not
76 * packed in `pack`, these objects are added to this "fake index" and
77 * are assumed to appear at the end of the packfile for all operations
80 struct object
**objects
;
82 uint32_t count
, alloc
;
83 khash_sha1_pos
*positions
;
86 /* Bitmap result of the last performed walk */
87 struct bitmap
*result
;
89 /* "have" bitmap from the last performed walk */
92 /* Version of the bitmap index */
98 static struct ewah_bitmap
*lookup_stored_bitmap(struct stored_bitmap
*st
)
100 struct ewah_bitmap
*parent
;
101 struct ewah_bitmap
*composed
;
106 composed
= ewah_pool_new();
107 parent
= lookup_stored_bitmap(st
->xor);
108 ewah_xor(st
->root
, parent
, composed
);
110 ewah_pool_free(st
->root
);
118 * Read a bitmap from the current read position on the mmaped
119 * index, and increase the read position accordingly
121 static struct ewah_bitmap
*read_bitmap_1(struct bitmap_index
*index
)
123 struct ewah_bitmap
*b
= ewah_pool_new();
125 ssize_t bitmap_size
= ewah_read_mmap(b
,
126 index
->map
+ index
->map_pos
,
127 index
->map_size
- index
->map_pos
);
129 if (bitmap_size
< 0) {
130 error("Failed to load bitmap index (corrupted?)");
135 index
->map_pos
+= bitmap_size
;
139 static int load_bitmap_header(struct bitmap_index
*index
)
141 struct bitmap_disk_header
*header
= (void *)index
->map
;
143 if (index
->map_size
< sizeof(*header
) + 20)
144 return error("Corrupted bitmap index (missing header data)");
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
);
157 if ((flags
& BITMAP_OPT_FULL_DAG
) == 0)
158 return error("Unsupported options for bitmap index file "
159 "(Git requires BITMAP_OPT_FULL_DAG)");
161 if (flags
& BITMAP_OPT_HASH_CACHE
) {
162 unsigned char *end
= index
->map
+ index
->map_size
- 20;
163 index
->hashes
= ((uint32_t *)end
) - index
->pack
->num_objects
;
167 index
->entry_count
= ntohl(header
->entry_count
);
168 index
->map_pos
+= sizeof(*header
);
172 static struct stored_bitmap
*store_bitmap(struct bitmap_index
*index
,
173 struct ewah_bitmap
*root
,
174 const unsigned char *sha1
,
175 struct stored_bitmap
*xor_with
,
178 struct stored_bitmap
*stored
;
182 stored
= xmalloc(sizeof(struct stored_bitmap
));
184 stored
->xor = xor_with
;
185 stored
->flags
= flags
;
186 hashcpy(stored
->sha1
, sha1
);
188 hash_pos
= kh_put_sha1(index
->bitmaps
, stored
->sha1
, &ret
);
190 /* a 0 return code means the insertion succeeded with no changes,
191 * because the SHA1 already existed on the map. this is bad, there
192 * shouldn't be duplicated commits in the index */
194 error("Duplicate entry in bitmap index: %s", sha1_to_hex(sha1
));
198 kh_value(index
->bitmaps
, hash_pos
) = stored
;
202 static inline uint32_t read_be32(const unsigned char *buffer
, size_t *pos
)
204 uint32_t result
= get_be32(buffer
+ *pos
);
205 (*pos
) += sizeof(result
);
209 static inline uint8_t read_u8(const unsigned char *buffer
, size_t *pos
)
211 return buffer
[(*pos
)++];
214 #define MAX_XOR_OFFSET 160
216 static int load_bitmap_entries_v1(struct bitmap_index
*index
)
219 struct stored_bitmap
*recent_bitmaps
[MAX_XOR_OFFSET
] = { NULL
};
221 for (i
= 0; i
< index
->entry_count
; ++i
) {
222 int xor_offset
, flags
;
223 struct ewah_bitmap
*bitmap
= NULL
;
224 struct stored_bitmap
*xor_bitmap
= NULL
;
225 uint32_t commit_idx_pos
;
226 const unsigned char *sha1
;
228 commit_idx_pos
= read_be32(index
->map
, &index
->map_pos
);
229 xor_offset
= read_u8(index
->map
, &index
->map_pos
);
230 flags
= read_u8(index
->map
, &index
->map_pos
);
232 sha1
= nth_packed_object_sha1(index
->pack
, commit_idx_pos
);
234 bitmap
= read_bitmap_1(index
);
238 if (xor_offset
> MAX_XOR_OFFSET
|| xor_offset
> i
)
239 return error("Corrupted bitmap pack index");
241 if (xor_offset
> 0) {
242 xor_bitmap
= recent_bitmaps
[(i
- xor_offset
) % MAX_XOR_OFFSET
];
244 if (xor_bitmap
== NULL
)
245 return error("Invalid XOR offset in bitmap pack index");
248 recent_bitmaps
[i
% MAX_XOR_OFFSET
] = store_bitmap(
249 index
, bitmap
, sha1
, xor_bitmap
, flags
);
255 static char *pack_bitmap_filename(struct packed_git
*p
)
259 if (!strip_suffix(p
->pack_name
, ".pack", &len
))
260 BUG("pack_name does not end in .pack");
261 return xstrfmt("%.*s.bitmap", (int)len
, p
->pack_name
);
264 static int open_pack_bitmap_1(struct bitmap_index
*bitmap_git
, struct packed_git
*packfile
)
270 if (open_pack_index(packfile
))
273 idx_name
= pack_bitmap_filename(packfile
);
274 fd
= git_open(idx_name
);
280 if (fstat(fd
, &st
)) {
285 if (bitmap_git
->pack
) {
286 warning("ignoring extra bitmap file: %s", packfile
->pack_name
);
291 bitmap_git
->pack
= packfile
;
292 bitmap_git
->map_size
= xsize_t(st
.st_size
);
293 bitmap_git
->map
= xmmap(NULL
, bitmap_git
->map_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
294 bitmap_git
->map_pos
= 0;
297 if (load_bitmap_header(bitmap_git
) < 0) {
298 munmap(bitmap_git
->map
, bitmap_git
->map_size
);
299 bitmap_git
->map
= NULL
;
300 bitmap_git
->map_size
= 0;
307 static int load_pack_bitmap(struct bitmap_index
*bitmap_git
)
309 assert(bitmap_git
->map
&& !bitmap_git
->loaded
);
311 bitmap_git
->bitmaps
= kh_init_sha1();
312 bitmap_git
->ext_index
.positions
= kh_init_sha1_pos();
313 load_pack_revindex(bitmap_git
->pack
);
315 if (!(bitmap_git
->commits
= read_bitmap_1(bitmap_git
)) ||
316 !(bitmap_git
->trees
= read_bitmap_1(bitmap_git
)) ||
317 !(bitmap_git
->blobs
= read_bitmap_1(bitmap_git
)) ||
318 !(bitmap_git
->tags
= read_bitmap_1(bitmap_git
)))
321 if (load_bitmap_entries_v1(bitmap_git
) < 0)
324 bitmap_git
->loaded
= 1;
328 munmap(bitmap_git
->map
, bitmap_git
->map_size
);
329 bitmap_git
->map
= NULL
;
330 bitmap_git
->map_size
= 0;
334 static int open_pack_bitmap(struct bitmap_index
*bitmap_git
)
336 struct packed_git
*p
;
339 assert(!bitmap_git
->map
&& !bitmap_git
->loaded
);
341 for (p
= get_packed_git(the_repository
); p
; p
= p
->next
) {
342 if (open_pack_bitmap_1(bitmap_git
, p
) == 0)
349 struct bitmap_index
*prepare_bitmap_git(void)
351 struct bitmap_index
*bitmap_git
= xcalloc(1, sizeof(*bitmap_git
));
353 if (!open_pack_bitmap(bitmap_git
) && !load_pack_bitmap(bitmap_git
))
356 free_bitmap_index(bitmap_git
);
360 struct include_data
{
361 struct bitmap_index
*bitmap_git
;
366 static inline int bitmap_position_extended(struct bitmap_index
*bitmap_git
,
367 const unsigned char *sha1
)
369 khash_sha1_pos
*positions
= bitmap_git
->ext_index
.positions
;
370 khiter_t pos
= kh_get_sha1_pos(positions
, sha1
);
372 if (pos
< kh_end(positions
)) {
373 int bitmap_pos
= kh_value(positions
, pos
);
374 return bitmap_pos
+ bitmap_git
->pack
->num_objects
;
380 static inline int bitmap_position_packfile(struct bitmap_index
*bitmap_git
,
381 const unsigned char *sha1
)
383 off_t offset
= find_pack_entry_one(sha1
, bitmap_git
->pack
);
387 return find_revindex_position(bitmap_git
->pack
, offset
);
390 static int bitmap_position(struct bitmap_index
*bitmap_git
,
391 const unsigned char *sha1
)
393 int pos
= bitmap_position_packfile(bitmap_git
, sha1
);
394 return (pos
>= 0) ? pos
: bitmap_position_extended(bitmap_git
, sha1
);
397 static int ext_index_add_object(struct bitmap_index
*bitmap_git
,
398 struct object
*object
, const char *name
)
400 struct eindex
*eindex
= &bitmap_git
->ext_index
;
406 hash_pos
= kh_put_sha1_pos(eindex
->positions
, object
->oid
.hash
, &hash_ret
);
408 if (eindex
->count
>= eindex
->alloc
) {
409 eindex
->alloc
= (eindex
->alloc
+ 16) * 3 / 2;
410 REALLOC_ARRAY(eindex
->objects
, eindex
->alloc
);
411 REALLOC_ARRAY(eindex
->hashes
, eindex
->alloc
);
414 bitmap_pos
= eindex
->count
;
415 eindex
->objects
[eindex
->count
] = object
;
416 eindex
->hashes
[eindex
->count
] = pack_name_hash(name
);
417 kh_value(eindex
->positions
, hash_pos
) = bitmap_pos
;
420 bitmap_pos
= kh_value(eindex
->positions
, hash_pos
);
423 return bitmap_pos
+ bitmap_git
->pack
->num_objects
;
426 struct bitmap_show_data
{
427 struct bitmap_index
*bitmap_git
;
431 static void show_object(struct object
*object
, const char *name
, void *data_
)
433 struct bitmap_show_data
*data
= data_
;
436 bitmap_pos
= bitmap_position(data
->bitmap_git
, object
->oid
.hash
);
439 bitmap_pos
= ext_index_add_object(data
->bitmap_git
, object
,
442 bitmap_set(data
->base
, bitmap_pos
);
445 static void show_commit(struct commit
*commit
, void *data
)
449 static int add_to_include_set(struct bitmap_index
*bitmap_git
,
450 struct include_data
*data
,
451 const unsigned char *sha1
,
456 if (data
->seen
&& bitmap_get(data
->seen
, bitmap_pos
))
459 if (bitmap_get(data
->base
, bitmap_pos
))
462 hash_pos
= kh_get_sha1(bitmap_git
->bitmaps
, sha1
);
463 if (hash_pos
< kh_end(bitmap_git
->bitmaps
)) {
464 struct stored_bitmap
*st
= kh_value(bitmap_git
->bitmaps
, hash_pos
);
465 bitmap_or_ewah(data
->base
, lookup_stored_bitmap(st
));
469 bitmap_set(data
->base
, bitmap_pos
);
473 static int should_include(struct commit
*commit
, void *_data
)
475 struct include_data
*data
= _data
;
478 bitmap_pos
= bitmap_position(data
->bitmap_git
, commit
->object
.oid
.hash
);
480 bitmap_pos
= ext_index_add_object(data
->bitmap_git
,
481 (struct object
*)commit
,
484 if (!add_to_include_set(data
->bitmap_git
, data
, commit
->object
.oid
.hash
,
486 struct commit_list
*parent
= commit
->parents
;
489 parent
->item
->object
.flags
|= SEEN
;
490 parent
= parent
->next
;
499 static struct bitmap
*find_objects(struct bitmap_index
*bitmap_git
,
500 struct rev_info
*revs
,
501 struct object_list
*roots
,
504 struct bitmap
*base
= NULL
;
507 struct object_list
*not_mapped
= NULL
;
510 * Go through all the roots for the walk. The ones that have bitmaps
511 * on the bitmap index will be `or`ed together to form an initial
512 * global reachability analysis.
514 * The ones without bitmaps in the index will be stored in the
515 * `not_mapped_list` for further processing.
518 struct object
*object
= roots
->item
;
521 if (object
->type
== OBJ_COMMIT
) {
522 khiter_t pos
= kh_get_sha1(bitmap_git
->bitmaps
, object
->oid
.hash
);
524 if (pos
< kh_end(bitmap_git
->bitmaps
)) {
525 struct stored_bitmap
*st
= kh_value(bitmap_git
->bitmaps
, pos
);
526 struct ewah_bitmap
*or_with
= lookup_stored_bitmap(st
);
529 base
= ewah_to_bitmap(or_with
);
531 bitmap_or_ewah(base
, or_with
);
533 object
->flags
|= SEEN
;
538 object_list_insert(object
, ¬_mapped
);
542 * Best case scenario: We found bitmaps for all the roots,
543 * so the resulting `or` bitmap has the full reachability analysis
545 if (not_mapped
== NULL
)
551 * Let's iterate through all the roots that don't have bitmaps to
552 * check if we can determine them to be reachable from the existing
555 * If we cannot find them in the existing global bitmap, we'll need
556 * to push them to an actual walk and run it until we can confirm
560 struct object
*object
= roots
->item
;
564 pos
= bitmap_position(bitmap_git
, object
->oid
.hash
);
566 if (pos
< 0 || base
== NULL
|| !bitmap_get(base
, pos
)) {
567 object
->flags
&= ~UNINTERESTING
;
568 add_pending_object(revs
, object
, "");
571 object
->flags
|= SEEN
;
576 struct include_data incdata
;
577 struct bitmap_show_data show_data
;
582 incdata
.bitmap_git
= bitmap_git
;
586 revs
->include_check
= should_include
;
587 revs
->include_check_data
= &incdata
;
589 if (prepare_revision_walk(revs
))
590 die("revision walk setup failed");
592 show_data
.bitmap_git
= bitmap_git
;
593 show_data
.base
= base
;
595 traverse_commit_list(revs
, show_commit
, show_object
,
602 static void show_extended_objects(struct bitmap_index
*bitmap_git
,
603 show_reachable_fn show_reach
)
605 struct bitmap
*objects
= bitmap_git
->result
;
606 struct eindex
*eindex
= &bitmap_git
->ext_index
;
609 for (i
= 0; i
< eindex
->count
; ++i
) {
612 if (!bitmap_get(objects
, bitmap_git
->pack
->num_objects
+ i
))
615 obj
= eindex
->objects
[i
];
616 show_reach(&obj
->oid
, obj
->type
, 0, eindex
->hashes
[i
], NULL
, 0);
620 static void show_objects_for_type(
621 struct bitmap_index
*bitmap_git
,
622 struct ewah_bitmap
*type_filter
,
623 enum object_type object_type
,
624 show_reachable_fn show_reach
)
626 size_t pos
= 0, i
= 0;
629 struct ewah_iterator it
;
632 struct bitmap
*objects
= bitmap_git
->result
;
634 if (bitmap_git
->reuse_objects
== bitmap_git
->pack
->num_objects
)
637 ewah_iterator_init(&it
, type_filter
);
639 while (i
< objects
->word_alloc
&& ewah_iterator_next(&filter
, &it
)) {
640 eword_t word
= objects
->words
[i
] & filter
;
642 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
643 struct object_id oid
;
644 struct revindex_entry
*entry
;
647 if ((word
>> offset
) == 0)
650 offset
+= ewah_bit_ctz64(word
>> offset
);
652 if (pos
+ offset
< bitmap_git
->reuse_objects
)
655 entry
= &bitmap_git
->pack
->revindex
[pos
+ offset
];
656 nth_packed_object_oid(&oid
, bitmap_git
->pack
, entry
->nr
);
658 if (bitmap_git
->hashes
)
659 hash
= get_be32(bitmap_git
->hashes
+ entry
->nr
);
661 show_reach(&oid
, object_type
, 0, hash
, bitmap_git
->pack
, entry
->offset
);
664 pos
+= BITS_IN_EWORD
;
669 static int in_bitmapped_pack(struct bitmap_index
*bitmap_git
,
670 struct object_list
*roots
)
673 struct object
*object
= roots
->item
;
676 if (find_pack_entry_one(object
->oid
.hash
, bitmap_git
->pack
) > 0)
683 struct bitmap_index
*prepare_bitmap_walk(struct rev_info
*revs
)
687 struct object_list
*wants
= NULL
;
688 struct object_list
*haves
= NULL
;
690 struct bitmap
*wants_bitmap
= NULL
;
691 struct bitmap
*haves_bitmap
= NULL
;
693 struct bitmap_index
*bitmap_git
= xcalloc(1, sizeof(*bitmap_git
));
694 /* try to open a bitmapped pack, but don't parse it yet
695 * because we may not need to use it */
696 if (open_pack_bitmap(bitmap_git
) < 0)
699 for (i
= 0; i
< revs
->pending
.nr
; ++i
) {
700 struct object
*object
= revs
->pending
.objects
[i
].item
;
702 if (object
->type
== OBJ_NONE
)
703 parse_object_or_die(&object
->oid
, NULL
);
705 while (object
->type
== OBJ_TAG
) {
706 struct tag
*tag
= (struct tag
*) object
;
708 if (object
->flags
& UNINTERESTING
)
709 object_list_insert(object
, &haves
);
711 object_list_insert(object
, &wants
);
715 object
= parse_object_or_die(&tag
->tagged
->oid
, NULL
);
718 if (object
->flags
& UNINTERESTING
)
719 object_list_insert(object
, &haves
);
721 object_list_insert(object
, &wants
);
725 * if we have a HAVES list, but none of those haves is contained
726 * in the packfile that has a bitmap, we don't have anything to
729 if (haves
&& !in_bitmapped_pack(bitmap_git
, haves
))
732 /* if we don't want anything, we're done here */
737 * now we're going to use bitmaps, so load the actual bitmap entries
738 * from disk. this is the point of no return; after this the rev_list
739 * becomes invalidated and we must perform the revwalk through bitmaps
741 if (!bitmap_git
->loaded
&& load_pack_bitmap(bitmap_git
) < 0)
744 object_array_clear(&revs
->pending
);
747 revs
->ignore_missing_links
= 1;
748 haves_bitmap
= find_objects(bitmap_git
, revs
, haves
, NULL
);
749 reset_revision_walk();
750 revs
->ignore_missing_links
= 0;
752 if (haves_bitmap
== NULL
)
753 BUG("failed to perform bitmap walk");
756 wants_bitmap
= find_objects(bitmap_git
, revs
, wants
, haves_bitmap
);
759 BUG("failed to perform bitmap walk");
762 bitmap_and_not(wants_bitmap
, haves_bitmap
);
764 bitmap_git
->result
= wants_bitmap
;
765 bitmap_git
->haves
= haves_bitmap
;
770 free_bitmap_index(bitmap_git
);
774 int reuse_partial_packfile_from_bitmap(struct bitmap_index
*bitmap_git
,
775 struct packed_git
**packfile
,
780 * Reuse the packfile content if we need more than
783 static const double REUSE_PERCENT
= 0.9;
785 struct bitmap
*result
= bitmap_git
->result
;
786 uint32_t reuse_threshold
;
787 uint32_t i
, reuse_objects
= 0;
791 for (i
= 0; i
< result
->word_alloc
; ++i
) {
792 if (result
->words
[i
] != (eword_t
)~0) {
793 reuse_objects
+= ewah_bit_ctz64(~result
->words
[i
]);
797 reuse_objects
+= BITS_IN_EWORD
;
800 #ifdef GIT_BITMAP_DEBUG
802 const unsigned char *sha1
;
803 struct revindex_entry
*entry
;
805 entry
= &bitmap_git
->reverse_index
->revindex
[reuse_objects
];
806 sha1
= nth_packed_object_sha1(bitmap_git
->pack
, entry
->nr
);
808 fprintf(stderr
, "Failed to reuse at %d (%016llx)\n",
809 reuse_objects
, result
->words
[i
]);
810 fprintf(stderr
, " %s\n", sha1_to_hex(sha1
));
817 if (reuse_objects
>= bitmap_git
->pack
->num_objects
) {
818 bitmap_git
->reuse_objects
= *entries
= bitmap_git
->pack
->num_objects
;
819 *up_to
= -1; /* reuse the full pack */
820 *packfile
= bitmap_git
->pack
;
824 reuse_threshold
= bitmap_popcount(bitmap_git
->result
) * REUSE_PERCENT
;
826 if (reuse_objects
< reuse_threshold
)
829 bitmap_git
->reuse_objects
= *entries
= reuse_objects
;
830 *up_to
= bitmap_git
->pack
->revindex
[reuse_objects
].offset
;
831 *packfile
= bitmap_git
->pack
;
836 void traverse_bitmap_commit_list(struct bitmap_index
*bitmap_git
,
837 show_reachable_fn show_reachable
)
839 assert(bitmap_git
->result
);
841 show_objects_for_type(bitmap_git
, bitmap_git
->commits
,
842 OBJ_COMMIT
, show_reachable
);
843 show_objects_for_type(bitmap_git
, bitmap_git
->trees
,
844 OBJ_TREE
, show_reachable
);
845 show_objects_for_type(bitmap_git
, bitmap_git
->blobs
,
846 OBJ_BLOB
, show_reachable
);
847 show_objects_for_type(bitmap_git
, bitmap_git
->tags
,
848 OBJ_TAG
, show_reachable
);
850 show_extended_objects(bitmap_git
, show_reachable
);
852 bitmap_free(bitmap_git
->result
);
853 bitmap_git
->result
= NULL
;
856 static uint32_t count_object_type(struct bitmap_index
*bitmap_git
,
857 enum object_type type
)
859 struct bitmap
*objects
= bitmap_git
->result
;
860 struct eindex
*eindex
= &bitmap_git
->ext_index
;
862 uint32_t i
= 0, count
= 0;
863 struct ewah_iterator it
;
868 ewah_iterator_init(&it
, bitmap_git
->commits
);
872 ewah_iterator_init(&it
, bitmap_git
->trees
);
876 ewah_iterator_init(&it
, bitmap_git
->blobs
);
880 ewah_iterator_init(&it
, bitmap_git
->tags
);
887 while (i
< objects
->word_alloc
&& ewah_iterator_next(&filter
, &it
)) {
888 eword_t word
= objects
->words
[i
++] & filter
;
889 count
+= ewah_bit_popcount64(word
);
892 for (i
= 0; i
< eindex
->count
; ++i
) {
893 if (eindex
->objects
[i
]->type
== type
&&
894 bitmap_get(objects
, bitmap_git
->pack
->num_objects
+ i
))
901 void count_bitmap_commit_list(struct bitmap_index
*bitmap_git
,
902 uint32_t *commits
, uint32_t *trees
,
903 uint32_t *blobs
, uint32_t *tags
)
905 assert(bitmap_git
->result
);
908 *commits
= count_object_type(bitmap_git
, OBJ_COMMIT
);
911 *trees
= count_object_type(bitmap_git
, OBJ_TREE
);
914 *blobs
= count_object_type(bitmap_git
, OBJ_BLOB
);
917 *tags
= count_object_type(bitmap_git
, OBJ_TAG
);
920 struct bitmap_test_data
{
921 struct bitmap_index
*bitmap_git
;
923 struct progress
*prg
;
927 static void test_show_object(struct object
*object
, const char *name
,
930 struct bitmap_test_data
*tdata
= data
;
933 bitmap_pos
= bitmap_position(tdata
->bitmap_git
, object
->oid
.hash
);
935 die("Object not in bitmap: %s\n", oid_to_hex(&object
->oid
));
937 bitmap_set(tdata
->base
, bitmap_pos
);
938 display_progress(tdata
->prg
, ++tdata
->seen
);
941 static void test_show_commit(struct commit
*commit
, void *data
)
943 struct bitmap_test_data
*tdata
= data
;
946 bitmap_pos
= bitmap_position(tdata
->bitmap_git
,
947 commit
->object
.oid
.hash
);
949 die("Object not in bitmap: %s\n", oid_to_hex(&commit
->object
.oid
));
951 bitmap_set(tdata
->base
, bitmap_pos
);
952 display_progress(tdata
->prg
, ++tdata
->seen
);
955 void test_bitmap_walk(struct rev_info
*revs
)
958 struct bitmap
*result
= NULL
;
960 size_t result_popcnt
;
961 struct bitmap_test_data tdata
;
962 struct bitmap_index
*bitmap_git
;
964 if (!(bitmap_git
= prepare_bitmap_git()))
965 die("failed to load bitmap indexes");
967 if (revs
->pending
.nr
!= 1)
968 die("you must specify exactly one commit to test");
970 fprintf(stderr
, "Bitmap v%d test (%d entries loaded)\n",
971 bitmap_git
->version
, bitmap_git
->entry_count
);
973 root
= revs
->pending
.objects
[0].item
;
974 pos
= kh_get_sha1(bitmap_git
->bitmaps
, root
->oid
.hash
);
976 if (pos
< kh_end(bitmap_git
->bitmaps
)) {
977 struct stored_bitmap
*st
= kh_value(bitmap_git
->bitmaps
, pos
);
978 struct ewah_bitmap
*bm
= lookup_stored_bitmap(st
);
980 fprintf(stderr
, "Found bitmap for %s. %d bits / %08x checksum\n",
981 oid_to_hex(&root
->oid
), (int)bm
->bit_size
, ewah_checksum(bm
));
983 result
= ewah_to_bitmap(bm
);
987 die("Commit %s doesn't have an indexed bitmap", oid_to_hex(&root
->oid
));
989 revs
->tag_objects
= 1;
990 revs
->tree_objects
= 1;
991 revs
->blob_objects
= 1;
993 result_popcnt
= bitmap_popcount(result
);
995 if (prepare_revision_walk(revs
))
996 die("revision walk setup failed");
998 tdata
.bitmap_git
= bitmap_git
;
999 tdata
.base
= bitmap_new();
1000 tdata
.prg
= start_progress("Verifying bitmap entries", result_popcnt
);
1003 traverse_commit_list(revs
, &test_show_commit
, &test_show_object
, &tdata
);
1005 stop_progress(&tdata
.prg
);
1007 if (bitmap_equals(result
, tdata
.base
))
1008 fprintf(stderr
, "OK!\n");
1010 fprintf(stderr
, "Mismatch!\n");
1012 free_bitmap_index(bitmap_git
);
1015 static int rebuild_bitmap(uint32_t *reposition
,
1016 struct ewah_bitmap
*source
,
1017 struct bitmap
*dest
)
1020 struct ewah_iterator it
;
1023 ewah_iterator_init(&it
, source
);
1025 while (ewah_iterator_next(&word
, &it
)) {
1026 uint32_t offset
, bit_pos
;
1028 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
1029 if ((word
>> offset
) == 0)
1032 offset
+= ewah_bit_ctz64(word
>> offset
);
1034 bit_pos
= reposition
[pos
+ offset
];
1036 bitmap_set(dest
, bit_pos
- 1);
1037 else /* can't reuse, we don't have the object */
1041 pos
+= BITS_IN_EWORD
;
1046 int rebuild_existing_bitmaps(struct bitmap_index
*bitmap_git
,
1047 struct packing_data
*mapping
,
1048 khash_sha1
*reused_bitmaps
,
1051 uint32_t i
, num_objects
;
1052 uint32_t *reposition
;
1053 struct bitmap
*rebuild
;
1054 struct stored_bitmap
*stored
;
1055 struct progress
*progress
= NULL
;
1060 num_objects
= bitmap_git
->pack
->num_objects
;
1061 reposition
= xcalloc(num_objects
, sizeof(uint32_t));
1063 for (i
= 0; i
< num_objects
; ++i
) {
1064 const unsigned char *sha1
;
1065 struct revindex_entry
*entry
;
1066 struct object_entry
*oe
;
1068 entry
= &bitmap_git
->pack
->revindex
[i
];
1069 sha1
= nth_packed_object_sha1(bitmap_git
->pack
, entry
->nr
);
1070 oe
= packlist_find(mapping
, sha1
, NULL
);
1073 reposition
[i
] = oe_in_pack_pos(mapping
, oe
) + 1;
1076 rebuild
= bitmap_new();
1080 progress
= start_progress("Reusing bitmaps", 0);
1082 kh_foreach_value(bitmap_git
->bitmaps
, stored
, {
1083 if (stored
->flags
& BITMAP_FLAG_REUSE
) {
1084 if (!rebuild_bitmap(reposition
,
1085 lookup_stored_bitmap(stored
),
1087 hash_pos
= kh_put_sha1(reused_bitmaps
,
1090 kh_value(reused_bitmaps
, hash_pos
) =
1091 bitmap_to_ewah(rebuild
);
1093 bitmap_reset(rebuild
);
1094 display_progress(progress
, ++i
);
1098 stop_progress(&progress
);
1101 bitmap_free(rebuild
);
1105 void free_bitmap_index(struct bitmap_index
*b
)
1111 munmap(b
->map
, b
->map_size
);
1112 ewah_pool_free(b
->commits
);
1113 ewah_pool_free(b
->trees
);
1114 ewah_pool_free(b
->blobs
);
1115 ewah_pool_free(b
->tags
);
1116 kh_destroy_sha1(b
->bitmaps
);
1117 free(b
->ext_index
.objects
);
1118 free(b
->ext_index
.hashes
);
1119 bitmap_free(b
->result
);
1120 bitmap_free(b
->haves
);
1124 int bitmap_has_sha1_in_uninteresting(struct bitmap_index
*bitmap_git
,
1125 const unsigned char *sha1
)
1130 return 0; /* no bitmap loaded */
1131 if (!bitmap_git
->result
)
1132 BUG("failed to perform bitmap walk before querying");
1133 if (!bitmap_git
->haves
)
1134 return 0; /* walk had no "haves" */
1136 pos
= bitmap_position_packfile(bitmap_git
, sha1
);
1140 return bitmap_get(bitmap_git
->haves
, pos
);