7 #include "list-objects.h"
9 #include "pack-bitmap.h"
10 #include "pack-revindex.h"
11 #include "pack-objects.h"
13 #include "repository.h"
14 #include "object-store.h"
15 #include "list-objects-filter-options.h"
18 * An entry on the bitmap index, representing the bitmap for a given
21 struct stored_bitmap
{
23 struct ewah_bitmap
*root
;
24 struct stored_bitmap
*xor;
29 * The active bitmap index for a repository. By design, repositories only have
30 * a single bitmap index available (the index for the biggest packfile in
31 * the repository), since bitmap indexes need full closure.
33 * If there is more than one bitmap index available (e.g. because of alternates),
34 * the active bitmap index is the largest one.
37 /* Packfile to which this bitmap index belongs to */
38 struct packed_git
*pack
;
41 * Mark the first `reuse_objects` in the packfile as reused:
42 * they will be sent as-is without using them for repacking
45 uint32_t reuse_objects
;
47 /* mmapped buffer of the whole bitmap index */
49 size_t map_size
; /* size of the mmaped buffer */
50 size_t map_pos
; /* current position when loading the index */
55 * Each bitmap marks which objects in the packfile are of the given
56 * type. This provides type information when yielding the objects from
57 * the packfile during a walk, which allows for better delta bases.
59 struct ewah_bitmap
*commits
;
60 struct ewah_bitmap
*trees
;
61 struct ewah_bitmap
*blobs
;
62 struct ewah_bitmap
*tags
;
64 /* Map from object ID -> `stored_bitmap` for all the bitmapped commits */
65 kh_oid_map_t
*bitmaps
;
67 /* Number of bitmapped commits */
70 /* If not NULL, this is a name-hash cache pointing into map. */
76 * When trying to perform bitmap operations with objects that are not
77 * packed in `pack`, these objects are added to this "fake index" and
78 * are assumed to appear at the end of the packfile for all operations
81 struct object
**objects
;
83 uint32_t count
, alloc
;
84 kh_oid_pos_t
*positions
;
87 /* Bitmap result of the last performed walk */
88 struct bitmap
*result
;
90 /* "have" bitmap from the last performed walk */
93 /* Version of the bitmap index */
97 static struct ewah_bitmap
*lookup_stored_bitmap(struct stored_bitmap
*st
)
99 struct ewah_bitmap
*parent
;
100 struct ewah_bitmap
*composed
;
105 composed
= ewah_pool_new();
106 parent
= lookup_stored_bitmap(st
->xor);
107 ewah_xor(st
->root
, parent
, composed
);
109 ewah_pool_free(st
->root
);
117 * Read a bitmap from the current read position on the mmaped
118 * index, and increase the read position accordingly
120 static struct ewah_bitmap
*read_bitmap_1(struct bitmap_index
*index
)
122 struct ewah_bitmap
*b
= ewah_pool_new();
124 ssize_t bitmap_size
= ewah_read_mmap(b
,
125 index
->map
+ index
->map_pos
,
126 index
->map_size
- index
->map_pos
);
128 if (bitmap_size
< 0) {
129 error("Failed to load bitmap index (corrupted?)");
134 index
->map_pos
+= bitmap_size
;
138 static int load_bitmap_header(struct bitmap_index
*index
)
140 struct bitmap_disk_header
*header
= (void *)index
->map
;
141 size_t header_size
= sizeof(*header
) - GIT_MAX_RAWSZ
+ the_hash_algo
->rawsz
;
143 if (index
->map_size
< header_size
+ the_hash_algo
->rawsz
)
144 return error("Corrupted bitmap index (too small)");
146 if (memcmp(header
->magic
, BITMAP_IDX_SIGNATURE
, sizeof(BITMAP_IDX_SIGNATURE
)) != 0)
147 return error("Corrupted bitmap index file (wrong header)");
149 index
->version
= ntohs(header
->version
);
150 if (index
->version
!= 1)
151 return error("Unsupported version for bitmap index file (%d)", index
->version
);
153 /* Parse known bitmap format options */
155 uint32_t flags
= ntohs(header
->options
);
156 size_t cache_size
= st_mult(index
->pack
->num_objects
, sizeof(uint32_t));
157 unsigned char *index_end
= index
->map
+ index
->map_size
- the_hash_algo
->rawsz
;
159 if ((flags
& BITMAP_OPT_FULL_DAG
) == 0)
160 return error("Unsupported options for bitmap index file "
161 "(Git requires BITMAP_OPT_FULL_DAG)");
163 if (flags
& BITMAP_OPT_HASH_CACHE
) {
164 if (cache_size
> index_end
- index
->map
- header_size
)
165 return error("corrupted bitmap index file (too short to fit hash cache)");
166 index
->hashes
= (void *)(index_end
- cache_size
);
167 index_end
-= cache_size
;
171 index
->entry_count
= ntohl(header
->entry_count
);
172 index
->map_pos
+= header_size
;
176 static struct stored_bitmap
*store_bitmap(struct bitmap_index
*index
,
177 struct ewah_bitmap
*root
,
178 const struct object_id
*oid
,
179 struct stored_bitmap
*xor_with
,
182 struct stored_bitmap
*stored
;
186 stored
= xmalloc(sizeof(struct stored_bitmap
));
188 stored
->xor = xor_with
;
189 stored
->flags
= flags
;
190 oidcpy(&stored
->oid
, oid
);
192 hash_pos
= kh_put_oid_map(index
->bitmaps
, stored
->oid
, &ret
);
194 /* a 0 return code means the insertion succeeded with no changes,
195 * because the SHA1 already existed on the map. this is bad, there
196 * shouldn't be duplicated commits in the index */
198 error("Duplicate entry in bitmap index: %s", oid_to_hex(oid
));
202 kh_value(index
->bitmaps
, hash_pos
) = stored
;
206 static inline uint32_t read_be32(const unsigned char *buffer
, size_t *pos
)
208 uint32_t result
= get_be32(buffer
+ *pos
);
209 (*pos
) += sizeof(result
);
213 static inline uint8_t read_u8(const unsigned char *buffer
, size_t *pos
)
215 return buffer
[(*pos
)++];
218 #define MAX_XOR_OFFSET 160
220 static int load_bitmap_entries_v1(struct bitmap_index
*index
)
223 struct stored_bitmap
*recent_bitmaps
[MAX_XOR_OFFSET
] = { NULL
};
225 for (i
= 0; i
< index
->entry_count
; ++i
) {
226 int xor_offset
, flags
;
227 struct ewah_bitmap
*bitmap
= NULL
;
228 struct stored_bitmap
*xor_bitmap
= NULL
;
229 uint32_t commit_idx_pos
;
230 struct object_id oid
;
232 commit_idx_pos
= read_be32(index
->map
, &index
->map_pos
);
233 xor_offset
= read_u8(index
->map
, &index
->map_pos
);
234 flags
= read_u8(index
->map
, &index
->map_pos
);
236 nth_packed_object_id(&oid
, index
->pack
, commit_idx_pos
);
238 bitmap
= read_bitmap_1(index
);
242 if (xor_offset
> MAX_XOR_OFFSET
|| xor_offset
> i
)
243 return error("Corrupted bitmap pack index");
245 if (xor_offset
> 0) {
246 xor_bitmap
= recent_bitmaps
[(i
- xor_offset
) % MAX_XOR_OFFSET
];
248 if (xor_bitmap
== NULL
)
249 return error("Invalid XOR offset in bitmap pack index");
252 recent_bitmaps
[i
% MAX_XOR_OFFSET
] = store_bitmap(
253 index
, bitmap
, &oid
, xor_bitmap
, flags
);
259 static char *pack_bitmap_filename(struct packed_git
*p
)
263 if (!strip_suffix(p
->pack_name
, ".pack", &len
))
264 BUG("pack_name does not end in .pack");
265 return xstrfmt("%.*s.bitmap", (int)len
, p
->pack_name
);
268 static int open_pack_bitmap_1(struct bitmap_index
*bitmap_git
, struct packed_git
*packfile
)
274 if (open_pack_index(packfile
))
277 idx_name
= pack_bitmap_filename(packfile
);
278 fd
= git_open(idx_name
);
284 if (fstat(fd
, &st
)) {
289 if (bitmap_git
->pack
) {
290 warning("ignoring extra bitmap file: %s", packfile
->pack_name
);
295 bitmap_git
->pack
= packfile
;
296 bitmap_git
->map_size
= xsize_t(st
.st_size
);
297 bitmap_git
->map
= xmmap(NULL
, bitmap_git
->map_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
298 bitmap_git
->map_pos
= 0;
301 if (load_bitmap_header(bitmap_git
) < 0) {
302 munmap(bitmap_git
->map
, bitmap_git
->map_size
);
303 bitmap_git
->map
= NULL
;
304 bitmap_git
->map_size
= 0;
311 static int load_pack_bitmap(struct bitmap_index
*bitmap_git
)
313 assert(bitmap_git
->map
);
315 bitmap_git
->bitmaps
= kh_init_oid_map();
316 bitmap_git
->ext_index
.positions
= kh_init_oid_pos();
317 if (load_pack_revindex(bitmap_git
->pack
))
320 if (!(bitmap_git
->commits
= read_bitmap_1(bitmap_git
)) ||
321 !(bitmap_git
->trees
= read_bitmap_1(bitmap_git
)) ||
322 !(bitmap_git
->blobs
= read_bitmap_1(bitmap_git
)) ||
323 !(bitmap_git
->tags
= read_bitmap_1(bitmap_git
)))
326 if (load_bitmap_entries_v1(bitmap_git
) < 0)
332 munmap(bitmap_git
->map
, bitmap_git
->map_size
);
333 bitmap_git
->map
= NULL
;
334 bitmap_git
->map_size
= 0;
336 kh_destroy_oid_map(bitmap_git
->bitmaps
);
337 bitmap_git
->bitmaps
= NULL
;
339 kh_destroy_oid_pos(bitmap_git
->ext_index
.positions
);
340 bitmap_git
->ext_index
.positions
= NULL
;
345 static int open_pack_bitmap(struct repository
*r
,
346 struct bitmap_index
*bitmap_git
)
348 struct packed_git
*p
;
351 assert(!bitmap_git
->map
);
353 for (p
= get_all_packs(r
); p
; p
= p
->next
) {
354 if (open_pack_bitmap_1(bitmap_git
, p
) == 0)
361 struct bitmap_index
*prepare_bitmap_git(struct repository
*r
)
363 struct bitmap_index
*bitmap_git
= xcalloc(1, sizeof(*bitmap_git
));
365 if (!open_pack_bitmap(r
, bitmap_git
) && !load_pack_bitmap(bitmap_git
))
368 free_bitmap_index(bitmap_git
);
372 struct include_data
{
373 struct bitmap_index
*bitmap_git
;
378 static inline int bitmap_position_extended(struct bitmap_index
*bitmap_git
,
379 const struct object_id
*oid
)
381 kh_oid_pos_t
*positions
= bitmap_git
->ext_index
.positions
;
382 khiter_t pos
= kh_get_oid_pos(positions
, *oid
);
384 if (pos
< kh_end(positions
)) {
385 int bitmap_pos
= kh_value(positions
, pos
);
386 return bitmap_pos
+ bitmap_git
->pack
->num_objects
;
392 static inline int bitmap_position_packfile(struct bitmap_index
*bitmap_git
,
393 const struct object_id
*oid
)
395 off_t offset
= find_pack_entry_one(oid
->hash
, bitmap_git
->pack
);
399 return find_revindex_position(bitmap_git
->pack
, offset
);
402 static int bitmap_position(struct bitmap_index
*bitmap_git
,
403 const struct object_id
*oid
)
405 int pos
= bitmap_position_packfile(bitmap_git
, oid
);
406 return (pos
>= 0) ? pos
: bitmap_position_extended(bitmap_git
, oid
);
409 static int ext_index_add_object(struct bitmap_index
*bitmap_git
,
410 struct object
*object
, const char *name
)
412 struct eindex
*eindex
= &bitmap_git
->ext_index
;
418 hash_pos
= kh_put_oid_pos(eindex
->positions
, object
->oid
, &hash_ret
);
420 if (eindex
->count
>= eindex
->alloc
) {
421 eindex
->alloc
= (eindex
->alloc
+ 16) * 3 / 2;
422 REALLOC_ARRAY(eindex
->objects
, eindex
->alloc
);
423 REALLOC_ARRAY(eindex
->hashes
, eindex
->alloc
);
426 bitmap_pos
= eindex
->count
;
427 eindex
->objects
[eindex
->count
] = object
;
428 eindex
->hashes
[eindex
->count
] = pack_name_hash(name
);
429 kh_value(eindex
->positions
, hash_pos
) = bitmap_pos
;
432 bitmap_pos
= kh_value(eindex
->positions
, hash_pos
);
435 return bitmap_pos
+ bitmap_git
->pack
->num_objects
;
438 struct bitmap_show_data
{
439 struct bitmap_index
*bitmap_git
;
443 static void show_object(struct object
*object
, const char *name
, void *data_
)
445 struct bitmap_show_data
*data
= data_
;
448 bitmap_pos
= bitmap_position(data
->bitmap_git
, &object
->oid
);
451 bitmap_pos
= ext_index_add_object(data
->bitmap_git
, object
,
454 bitmap_set(data
->base
, bitmap_pos
);
457 static void show_commit(struct commit
*commit
, void *data
)
461 static int add_to_include_set(struct bitmap_index
*bitmap_git
,
462 struct include_data
*data
,
463 const struct object_id
*oid
,
468 if (data
->seen
&& bitmap_get(data
->seen
, bitmap_pos
))
471 if (bitmap_get(data
->base
, bitmap_pos
))
474 hash_pos
= kh_get_oid_map(bitmap_git
->bitmaps
, *oid
);
475 if (hash_pos
< kh_end(bitmap_git
->bitmaps
)) {
476 struct stored_bitmap
*st
= kh_value(bitmap_git
->bitmaps
, hash_pos
);
477 bitmap_or_ewah(data
->base
, lookup_stored_bitmap(st
));
481 bitmap_set(data
->base
, bitmap_pos
);
485 static int should_include(struct commit
*commit
, void *_data
)
487 struct include_data
*data
= _data
;
490 bitmap_pos
= bitmap_position(data
->bitmap_git
, &commit
->object
.oid
);
492 bitmap_pos
= ext_index_add_object(data
->bitmap_git
,
493 (struct object
*)commit
,
496 if (!add_to_include_set(data
->bitmap_git
, data
, &commit
->object
.oid
,
498 struct commit_list
*parent
= commit
->parents
;
501 parent
->item
->object
.flags
|= SEEN
;
502 parent
= parent
->next
;
511 static struct bitmap
*find_objects(struct bitmap_index
*bitmap_git
,
512 struct rev_info
*revs
,
513 struct object_list
*roots
,
515 struct list_objects_filter_options
*filter
)
517 struct bitmap
*base
= NULL
;
520 struct object_list
*not_mapped
= NULL
;
523 * Go through all the roots for the walk. The ones that have bitmaps
524 * on the bitmap index will be `or`ed together to form an initial
525 * global reachability analysis.
527 * The ones without bitmaps in the index will be stored in the
528 * `not_mapped_list` for further processing.
531 struct object
*object
= roots
->item
;
534 if (object
->type
== OBJ_COMMIT
) {
535 khiter_t pos
= kh_get_oid_map(bitmap_git
->bitmaps
, object
->oid
);
537 if (pos
< kh_end(bitmap_git
->bitmaps
)) {
538 struct stored_bitmap
*st
= kh_value(bitmap_git
->bitmaps
, pos
);
539 struct ewah_bitmap
*or_with
= lookup_stored_bitmap(st
);
542 base
= ewah_to_bitmap(or_with
);
544 bitmap_or_ewah(base
, or_with
);
546 object
->flags
|= SEEN
;
551 object_list_insert(object
, ¬_mapped
);
555 * Best case scenario: We found bitmaps for all the roots,
556 * so the resulting `or` bitmap has the full reachability analysis
558 if (not_mapped
== NULL
)
564 * Let's iterate through all the roots that don't have bitmaps to
565 * check if we can determine them to be reachable from the existing
568 * If we cannot find them in the existing global bitmap, we'll need
569 * to push them to an actual walk and run it until we can confirm
573 struct object
*object
= roots
->item
;
577 pos
= bitmap_position(bitmap_git
, &object
->oid
);
579 if (pos
< 0 || base
== NULL
|| !bitmap_get(base
, pos
)) {
580 object
->flags
&= ~UNINTERESTING
;
581 add_pending_object(revs
, object
, "");
584 object
->flags
|= SEEN
;
589 struct include_data incdata
;
590 struct bitmap_show_data show_data
;
595 incdata
.bitmap_git
= bitmap_git
;
599 revs
->include_check
= should_include
;
600 revs
->include_check_data
= &incdata
;
602 if (prepare_revision_walk(revs
))
603 die("revision walk setup failed");
605 show_data
.bitmap_git
= bitmap_git
;
606 show_data
.base
= base
;
608 traverse_commit_list_filtered(filter
, revs
,
609 show_commit
, show_object
,
616 static void show_extended_objects(struct bitmap_index
*bitmap_git
,
617 struct rev_info
*revs
,
618 show_reachable_fn show_reach
)
620 struct bitmap
*objects
= bitmap_git
->result
;
621 struct eindex
*eindex
= &bitmap_git
->ext_index
;
624 for (i
= 0; i
< eindex
->count
; ++i
) {
627 if (!bitmap_get(objects
, bitmap_git
->pack
->num_objects
+ i
))
630 obj
= eindex
->objects
[i
];
631 if ((obj
->type
== OBJ_BLOB
&& !revs
->blob_objects
) ||
632 (obj
->type
== OBJ_TREE
&& !revs
->tree_objects
) ||
633 (obj
->type
== OBJ_TAG
&& !revs
->tag_objects
))
636 show_reach(&obj
->oid
, obj
->type
, 0, eindex
->hashes
[i
], NULL
, 0);
640 static void init_type_iterator(struct ewah_iterator
*it
,
641 struct bitmap_index
*bitmap_git
,
642 enum object_type type
)
646 ewah_iterator_init(it
, bitmap_git
->commits
);
650 ewah_iterator_init(it
, bitmap_git
->trees
);
654 ewah_iterator_init(it
, bitmap_git
->blobs
);
658 ewah_iterator_init(it
, bitmap_git
->tags
);
662 BUG("object type %d not stored by bitmap type index", type
);
667 static void show_objects_for_type(
668 struct bitmap_index
*bitmap_git
,
669 enum object_type object_type
,
670 show_reachable_fn show_reach
)
675 struct ewah_iterator it
;
678 struct bitmap
*objects
= bitmap_git
->result
;
680 init_type_iterator(&it
, bitmap_git
, object_type
);
682 for (i
= 0; i
< objects
->word_alloc
&&
683 ewah_iterator_next(&filter
, &it
); i
++) {
684 eword_t word
= objects
->words
[i
] & filter
;
685 size_t pos
= (i
* BITS_IN_EWORD
);
690 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
691 struct object_id oid
;
692 struct revindex_entry
*entry
;
695 if ((word
>> offset
) == 0)
698 offset
+= ewah_bit_ctz64(word
>> offset
);
700 entry
= &bitmap_git
->pack
->revindex
[pos
+ offset
];
701 nth_packed_object_id(&oid
, bitmap_git
->pack
, entry
->nr
);
703 if (bitmap_git
->hashes
)
704 hash
= get_be32(bitmap_git
->hashes
+ entry
->nr
);
706 show_reach(&oid
, object_type
, 0, hash
, bitmap_git
->pack
, entry
->offset
);
711 static int in_bitmapped_pack(struct bitmap_index
*bitmap_git
,
712 struct object_list
*roots
)
715 struct object
*object
= roots
->item
;
718 if (find_pack_entry_one(object
->oid
.hash
, bitmap_git
->pack
) > 0)
725 static struct bitmap
*find_tip_objects(struct bitmap_index
*bitmap_git
,
726 struct object_list
*tip_objects
,
727 enum object_type type
)
729 struct bitmap
*result
= bitmap_new();
730 struct object_list
*p
;
732 for (p
= tip_objects
; p
; p
= p
->next
) {
735 if (p
->item
->type
!= type
)
738 pos
= bitmap_position(bitmap_git
, &p
->item
->oid
);
742 bitmap_set(result
, pos
);
748 static void filter_bitmap_exclude_type(struct bitmap_index
*bitmap_git
,
749 struct object_list
*tip_objects
,
750 struct bitmap
*to_filter
,
751 enum object_type type
)
753 struct eindex
*eindex
= &bitmap_git
->ext_index
;
755 struct ewah_iterator it
;
759 if (type
!= OBJ_BLOB
&& type
!= OBJ_TREE
)
760 BUG("filter_bitmap_exclude_type: unsupported type '%d'", type
);
763 * The non-bitmap version of this filter never removes
764 * objects which the other side specifically asked for,
765 * so we must match that behavior.
767 tips
= find_tip_objects(bitmap_git
, tip_objects
, type
);
770 * We can use the blob type-bitmap to work in whole words
771 * for the objects that are actually in the bitmapped packfile.
773 for (i
= 0, init_type_iterator(&it
, bitmap_git
, type
);
774 i
< to_filter
->word_alloc
&& ewah_iterator_next(&mask
, &it
);
776 if (i
< tips
->word_alloc
)
777 mask
&= ~tips
->words
[i
];
778 to_filter
->words
[i
] &= ~mask
;
782 * Clear any blobs that weren't in the packfile (and so would not have
783 * been caught by the loop above. We'll have to check them
786 for (i
= 0; i
< eindex
->count
; i
++) {
787 uint32_t pos
= i
+ bitmap_git
->pack
->num_objects
;
788 if (eindex
->objects
[i
]->type
== type
&&
789 bitmap_get(to_filter
, pos
) &&
790 !bitmap_get(tips
, pos
))
791 bitmap_unset(to_filter
, pos
);
797 static void filter_bitmap_blob_none(struct bitmap_index
*bitmap_git
,
798 struct object_list
*tip_objects
,
799 struct bitmap
*to_filter
)
801 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
,
805 static unsigned long get_size_by_pos(struct bitmap_index
*bitmap_git
,
808 struct packed_git
*pack
= bitmap_git
->pack
;
810 struct object_info oi
= OBJECT_INFO_INIT
;
814 if (pos
< pack
->num_objects
) {
815 struct revindex_entry
*entry
= &pack
->revindex
[pos
];
816 if (packed_object_info(the_repository
, pack
,
817 entry
->offset
, &oi
) < 0) {
818 struct object_id oid
;
819 nth_packed_object_id(&oid
, pack
, entry
->nr
);
820 die(_("unable to get size of %s"), oid_to_hex(&oid
));
823 struct eindex
*eindex
= &bitmap_git
->ext_index
;
824 struct object
*obj
= eindex
->objects
[pos
- pack
->num_objects
];
825 if (oid_object_info_extended(the_repository
, &obj
->oid
, &oi
, 0) < 0)
826 die(_("unable to get size of %s"), oid_to_hex(&obj
->oid
));
832 static void filter_bitmap_blob_limit(struct bitmap_index
*bitmap_git
,
833 struct object_list
*tip_objects
,
834 struct bitmap
*to_filter
,
837 struct eindex
*eindex
= &bitmap_git
->ext_index
;
839 struct ewah_iterator it
;
843 tips
= find_tip_objects(bitmap_git
, tip_objects
, OBJ_BLOB
);
845 for (i
= 0, init_type_iterator(&it
, bitmap_git
, OBJ_BLOB
);
846 i
< to_filter
->word_alloc
&& ewah_iterator_next(&mask
, &it
);
848 eword_t word
= to_filter
->words
[i
] & mask
;
851 for (offset
= 0; offset
< BITS_IN_EWORD
; offset
++) {
854 if ((word
>> offset
) == 0)
856 offset
+= ewah_bit_ctz64(word
>> offset
);
857 pos
= i
* BITS_IN_EWORD
+ offset
;
859 if (!bitmap_get(tips
, pos
) &&
860 get_size_by_pos(bitmap_git
, pos
) >= limit
)
861 bitmap_unset(to_filter
, pos
);
865 for (i
= 0; i
< eindex
->count
; i
++) {
866 uint32_t pos
= i
+ bitmap_git
->pack
->num_objects
;
867 if (eindex
->objects
[i
]->type
== OBJ_BLOB
&&
868 bitmap_get(to_filter
, pos
) &&
869 !bitmap_get(tips
, pos
) &&
870 get_size_by_pos(bitmap_git
, pos
) >= limit
)
871 bitmap_unset(to_filter
, pos
);
877 static void filter_bitmap_tree_depth(struct bitmap_index
*bitmap_git
,
878 struct object_list
*tip_objects
,
879 struct bitmap
*to_filter
,
883 BUG("filter_bitmap_tree_depth given non-zero limit");
885 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
,
887 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
,
891 static int filter_bitmap(struct bitmap_index
*bitmap_git
,
892 struct object_list
*tip_objects
,
893 struct bitmap
*to_filter
,
894 struct list_objects_filter_options
*filter
)
896 if (!filter
|| filter
->choice
== LOFC_DISABLED
)
899 if (filter
->choice
== LOFC_BLOB_NONE
) {
901 filter_bitmap_blob_none(bitmap_git
, tip_objects
,
906 if (filter
->choice
== LOFC_BLOB_LIMIT
) {
908 filter_bitmap_blob_limit(bitmap_git
, tip_objects
,
910 filter
->blob_limit_value
);
914 if (filter
->choice
== LOFC_TREE_DEPTH
&&
915 filter
->tree_exclude_depth
== 0) {
917 filter_bitmap_tree_depth(bitmap_git
, tip_objects
,
919 filter
->tree_exclude_depth
);
923 /* filter choice not handled */
927 static int can_filter_bitmap(struct list_objects_filter_options
*filter
)
929 return !filter_bitmap(NULL
, NULL
, NULL
, filter
);
932 struct bitmap_index
*prepare_bitmap_walk(struct rev_info
*revs
,
933 struct list_objects_filter_options
*filter
)
937 struct object_list
*wants
= NULL
;
938 struct object_list
*haves
= NULL
;
940 struct bitmap
*wants_bitmap
= NULL
;
941 struct bitmap
*haves_bitmap
= NULL
;
943 struct bitmap_index
*bitmap_git
;
946 * We can't do pathspec limiting with bitmaps, because we don't know
947 * which commits are associated with which object changes (let alone
948 * even which objects are associated with which paths).
953 if (!can_filter_bitmap(filter
))
956 /* try to open a bitmapped pack, but don't parse it yet
957 * because we may not need to use it */
958 bitmap_git
= xcalloc(1, sizeof(*bitmap_git
));
959 if (open_pack_bitmap(revs
->repo
, bitmap_git
) < 0)
962 for (i
= 0; i
< revs
->pending
.nr
; ++i
) {
963 struct object
*object
= revs
->pending
.objects
[i
].item
;
965 if (object
->type
== OBJ_NONE
)
966 parse_object_or_die(&object
->oid
, NULL
);
968 while (object
->type
== OBJ_TAG
) {
969 struct tag
*tag
= (struct tag
*) object
;
971 if (object
->flags
& UNINTERESTING
)
972 object_list_insert(object
, &haves
);
974 object_list_insert(object
, &wants
);
976 object
= parse_object_or_die(get_tagged_oid(tag
), NULL
);
979 if (object
->flags
& UNINTERESTING
)
980 object_list_insert(object
, &haves
);
982 object_list_insert(object
, &wants
);
986 * if we have a HAVES list, but none of those haves is contained
987 * in the packfile that has a bitmap, we don't have anything to
990 if (haves
&& !in_bitmapped_pack(bitmap_git
, haves
))
993 /* if we don't want anything, we're done here */
998 * now we're going to use bitmaps, so load the actual bitmap entries
999 * from disk. this is the point of no return; after this the rev_list
1000 * becomes invalidated and we must perform the revwalk through bitmaps
1002 if (load_pack_bitmap(bitmap_git
) < 0)
1005 object_array_clear(&revs
->pending
);
1008 revs
->ignore_missing_links
= 1;
1009 haves_bitmap
= find_objects(bitmap_git
, revs
, haves
, NULL
,
1011 reset_revision_walk();
1012 revs
->ignore_missing_links
= 0;
1014 if (haves_bitmap
== NULL
)
1015 BUG("failed to perform bitmap walk");
1018 wants_bitmap
= find_objects(bitmap_git
, revs
, wants
, haves_bitmap
,
1022 BUG("failed to perform bitmap walk");
1025 bitmap_and_not(wants_bitmap
, haves_bitmap
);
1027 filter_bitmap(bitmap_git
, wants
, wants_bitmap
, filter
);
1029 bitmap_git
->result
= wants_bitmap
;
1030 bitmap_git
->haves
= haves_bitmap
;
1032 object_list_free(&wants
);
1033 object_list_free(&haves
);
1038 free_bitmap_index(bitmap_git
);
1039 object_list_free(&wants
);
1040 object_list_free(&haves
);
1044 static void try_partial_reuse(struct bitmap_index
*bitmap_git
,
1046 struct bitmap
*reuse
,
1047 struct pack_window
**w_curs
)
1049 struct revindex_entry
*revidx
;
1051 enum object_type type
;
1054 if (pos
>= bitmap_git
->pack
->num_objects
)
1055 return; /* not actually in the pack */
1057 revidx
= &bitmap_git
->pack
->revindex
[pos
];
1058 offset
= revidx
->offset
;
1059 type
= unpack_object_header(bitmap_git
->pack
, w_curs
, &offset
, &size
);
1061 return; /* broken packfile, punt */
1063 if (type
== OBJ_REF_DELTA
|| type
== OBJ_OFS_DELTA
) {
1068 * Find the position of the base object so we can look it up
1069 * in our bitmaps. If we can't come up with an offset, or if
1070 * that offset is not in the revidx, the pack is corrupt.
1071 * There's nothing we can do, so just punt on this object,
1072 * and the normal slow path will complain about it in
1075 base_offset
= get_delta_base(bitmap_git
->pack
, w_curs
,
1076 &offset
, type
, revidx
->offset
);
1079 base_pos
= find_revindex_position(bitmap_git
->pack
, base_offset
);
1084 * We assume delta dependencies always point backwards. This
1085 * lets us do a single pass, and is basically always true
1086 * due to the way OFS_DELTAs work. You would not typically
1087 * find REF_DELTA in a bitmapped pack, since we only bitmap
1088 * packs we write fresh, and OFS_DELTA is the default). But
1089 * let's double check to make sure the pack wasn't written with
1092 if (base_pos
>= pos
)
1096 * And finally, if we're not sending the base as part of our
1097 * reuse chunk, then don't send this object either. The base
1098 * would come after us, along with other objects not
1099 * necessarily in the pack, which means we'd need to convert
1100 * to REF_DELTA on the fly. Better to just let the normal
1101 * object_entry code path handle it.
1103 if (!bitmap_get(reuse
, base_pos
))
1108 * If we got here, then the object is OK to reuse. Mark it.
1110 bitmap_set(reuse
, pos
);
1113 int reuse_partial_packfile_from_bitmap(struct bitmap_index
*bitmap_git
,
1114 struct packed_git
**packfile_out
,
1116 struct bitmap
**reuse_out
)
1118 struct bitmap
*result
= bitmap_git
->result
;
1119 struct bitmap
*reuse
;
1120 struct pack_window
*w_curs
= NULL
;
1126 while (i
< result
->word_alloc
&& result
->words
[i
] == (eword_t
)~0)
1129 /* Don't mark objects not in the packfile */
1130 if (i
> bitmap_git
->pack
->num_objects
/ BITS_IN_EWORD
)
1131 i
= bitmap_git
->pack
->num_objects
/ BITS_IN_EWORD
;
1133 reuse
= bitmap_word_alloc(i
);
1134 memset(reuse
->words
, 0xFF, i
* sizeof(eword_t
));
1136 for (; i
< result
->word_alloc
; ++i
) {
1137 eword_t word
= result
->words
[i
];
1138 size_t pos
= (i
* BITS_IN_EWORD
);
1140 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
1141 if ((word
>> offset
) == 0)
1144 offset
+= ewah_bit_ctz64(word
>> offset
);
1145 try_partial_reuse(bitmap_git
, pos
+ offset
, reuse
, &w_curs
);
1149 unuse_pack(&w_curs
);
1151 *entries
= bitmap_popcount(reuse
);
1158 * Drop any reused objects from the result, since they will not
1159 * need to be handled separately.
1161 bitmap_and_not(result
, reuse
);
1162 *packfile_out
= bitmap_git
->pack
;
1167 int bitmap_walk_contains(struct bitmap_index
*bitmap_git
,
1168 struct bitmap
*bitmap
, const struct object_id
*oid
)
1175 idx
= bitmap_position(bitmap_git
, oid
);
1176 return idx
>= 0 && bitmap_get(bitmap
, idx
);
1179 void traverse_bitmap_commit_list(struct bitmap_index
*bitmap_git
,
1180 struct rev_info
*revs
,
1181 show_reachable_fn show_reachable
)
1183 assert(bitmap_git
->result
);
1185 show_objects_for_type(bitmap_git
, OBJ_COMMIT
, show_reachable
);
1186 if (revs
->tree_objects
)
1187 show_objects_for_type(bitmap_git
, OBJ_TREE
, show_reachable
);
1188 if (revs
->blob_objects
)
1189 show_objects_for_type(bitmap_git
, OBJ_BLOB
, show_reachable
);
1190 if (revs
->tag_objects
)
1191 show_objects_for_type(bitmap_git
, OBJ_TAG
, show_reachable
);
1193 show_extended_objects(bitmap_git
, revs
, show_reachable
);
1196 static uint32_t count_object_type(struct bitmap_index
*bitmap_git
,
1197 enum object_type type
)
1199 struct bitmap
*objects
= bitmap_git
->result
;
1200 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1202 uint32_t i
= 0, count
= 0;
1203 struct ewah_iterator it
;
1206 init_type_iterator(&it
, bitmap_git
, type
);
1208 while (i
< objects
->word_alloc
&& ewah_iterator_next(&filter
, &it
)) {
1209 eword_t word
= objects
->words
[i
++] & filter
;
1210 count
+= ewah_bit_popcount64(word
);
1213 for (i
= 0; i
< eindex
->count
; ++i
) {
1214 if (eindex
->objects
[i
]->type
== type
&&
1215 bitmap_get(objects
, bitmap_git
->pack
->num_objects
+ i
))
1222 void count_bitmap_commit_list(struct bitmap_index
*bitmap_git
,
1223 uint32_t *commits
, uint32_t *trees
,
1224 uint32_t *blobs
, uint32_t *tags
)
1226 assert(bitmap_git
->result
);
1229 *commits
= count_object_type(bitmap_git
, OBJ_COMMIT
);
1232 *trees
= count_object_type(bitmap_git
, OBJ_TREE
);
1235 *blobs
= count_object_type(bitmap_git
, OBJ_BLOB
);
1238 *tags
= count_object_type(bitmap_git
, OBJ_TAG
);
1241 struct bitmap_test_data
{
1242 struct bitmap_index
*bitmap_git
;
1243 struct bitmap
*base
;
1244 struct progress
*prg
;
1248 static void test_show_object(struct object
*object
, const char *name
,
1251 struct bitmap_test_data
*tdata
= data
;
1254 bitmap_pos
= bitmap_position(tdata
->bitmap_git
, &object
->oid
);
1256 die("Object not in bitmap: %s\n", oid_to_hex(&object
->oid
));
1258 bitmap_set(tdata
->base
, bitmap_pos
);
1259 display_progress(tdata
->prg
, ++tdata
->seen
);
1262 static void test_show_commit(struct commit
*commit
, void *data
)
1264 struct bitmap_test_data
*tdata
= data
;
1267 bitmap_pos
= bitmap_position(tdata
->bitmap_git
,
1268 &commit
->object
.oid
);
1270 die("Object not in bitmap: %s\n", oid_to_hex(&commit
->object
.oid
));
1272 bitmap_set(tdata
->base
, bitmap_pos
);
1273 display_progress(tdata
->prg
, ++tdata
->seen
);
1276 void test_bitmap_walk(struct rev_info
*revs
)
1278 struct object
*root
;
1279 struct bitmap
*result
= NULL
;
1281 size_t result_popcnt
;
1282 struct bitmap_test_data tdata
;
1283 struct bitmap_index
*bitmap_git
;
1285 if (!(bitmap_git
= prepare_bitmap_git(revs
->repo
)))
1286 die("failed to load bitmap indexes");
1288 if (revs
->pending
.nr
!= 1)
1289 die("you must specify exactly one commit to test");
1291 fprintf(stderr
, "Bitmap v%d test (%d entries loaded)\n",
1292 bitmap_git
->version
, bitmap_git
->entry_count
);
1294 root
= revs
->pending
.objects
[0].item
;
1295 pos
= kh_get_oid_map(bitmap_git
->bitmaps
, root
->oid
);
1297 if (pos
< kh_end(bitmap_git
->bitmaps
)) {
1298 struct stored_bitmap
*st
= kh_value(bitmap_git
->bitmaps
, pos
);
1299 struct ewah_bitmap
*bm
= lookup_stored_bitmap(st
);
1301 fprintf(stderr
, "Found bitmap for %s. %d bits / %08x checksum\n",
1302 oid_to_hex(&root
->oid
), (int)bm
->bit_size
, ewah_checksum(bm
));
1304 result
= ewah_to_bitmap(bm
);
1308 die("Commit %s doesn't have an indexed bitmap", oid_to_hex(&root
->oid
));
1310 revs
->tag_objects
= 1;
1311 revs
->tree_objects
= 1;
1312 revs
->blob_objects
= 1;
1314 result_popcnt
= bitmap_popcount(result
);
1316 if (prepare_revision_walk(revs
))
1317 die("revision walk setup failed");
1319 tdata
.bitmap_git
= bitmap_git
;
1320 tdata
.base
= bitmap_new();
1321 tdata
.prg
= start_progress("Verifying bitmap entries", result_popcnt
);
1324 traverse_commit_list(revs
, &test_show_commit
, &test_show_object
, &tdata
);
1326 stop_progress(&tdata
.prg
);
1328 if (bitmap_equals(result
, tdata
.base
))
1329 fprintf(stderr
, "OK!\n");
1331 fprintf(stderr
, "Mismatch!\n");
1333 free_bitmap_index(bitmap_git
);
1336 static int rebuild_bitmap(uint32_t *reposition
,
1337 struct ewah_bitmap
*source
,
1338 struct bitmap
*dest
)
1341 struct ewah_iterator it
;
1344 ewah_iterator_init(&it
, source
);
1346 while (ewah_iterator_next(&word
, &it
)) {
1347 uint32_t offset
, bit_pos
;
1349 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
1350 if ((word
>> offset
) == 0)
1353 offset
+= ewah_bit_ctz64(word
>> offset
);
1355 bit_pos
= reposition
[pos
+ offset
];
1357 bitmap_set(dest
, bit_pos
- 1);
1358 else /* can't reuse, we don't have the object */
1362 pos
+= BITS_IN_EWORD
;
1367 int rebuild_existing_bitmaps(struct bitmap_index
*bitmap_git
,
1368 struct packing_data
*mapping
,
1369 kh_oid_map_t
*reused_bitmaps
,
1372 uint32_t i
, num_objects
;
1373 uint32_t *reposition
;
1374 struct bitmap
*rebuild
;
1375 struct stored_bitmap
*stored
;
1376 struct progress
*progress
= NULL
;
1381 num_objects
= bitmap_git
->pack
->num_objects
;
1382 reposition
= xcalloc(num_objects
, sizeof(uint32_t));
1384 for (i
= 0; i
< num_objects
; ++i
) {
1385 struct object_id oid
;
1386 struct revindex_entry
*entry
;
1387 struct object_entry
*oe
;
1389 entry
= &bitmap_git
->pack
->revindex
[i
];
1390 nth_packed_object_id(&oid
, bitmap_git
->pack
, entry
->nr
);
1391 oe
= packlist_find(mapping
, &oid
);
1394 reposition
[i
] = oe_in_pack_pos(mapping
, oe
) + 1;
1397 rebuild
= bitmap_new();
1401 progress
= start_progress("Reusing bitmaps", 0);
1403 kh_foreach_value(bitmap_git
->bitmaps
, stored
, {
1404 if (stored
->flags
& BITMAP_FLAG_REUSE
) {
1405 if (!rebuild_bitmap(reposition
,
1406 lookup_stored_bitmap(stored
),
1408 hash_pos
= kh_put_oid_map(reused_bitmaps
,
1411 kh_value(reused_bitmaps
, hash_pos
) =
1412 bitmap_to_ewah(rebuild
);
1414 bitmap_reset(rebuild
);
1415 display_progress(progress
, ++i
);
1419 stop_progress(&progress
);
1422 bitmap_free(rebuild
);
1426 void free_bitmap_index(struct bitmap_index
*b
)
1432 munmap(b
->map
, b
->map_size
);
1433 ewah_pool_free(b
->commits
);
1434 ewah_pool_free(b
->trees
);
1435 ewah_pool_free(b
->blobs
);
1436 ewah_pool_free(b
->tags
);
1437 kh_destroy_oid_map(b
->bitmaps
);
1438 free(b
->ext_index
.objects
);
1439 free(b
->ext_index
.hashes
);
1440 bitmap_free(b
->result
);
1441 bitmap_free(b
->haves
);
1445 int bitmap_has_oid_in_uninteresting(struct bitmap_index
*bitmap_git
,
1446 const struct object_id
*oid
)
1448 return bitmap_git
&&
1449 bitmap_walk_contains(bitmap_git
, bitmap_git
->haves
, oid
);