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"
19 * An entry on the bitmap index, representing the bitmap for a given
22 struct stored_bitmap
{
24 struct ewah_bitmap
*root
;
25 struct stored_bitmap
*xor;
30 * The active bitmap index for a repository. By design, repositories only have
31 * a single bitmap index available (the index for the biggest packfile in
32 * the repository), since bitmap indexes need full closure.
34 * If there is more than one bitmap index available (e.g. because of alternates),
35 * the active bitmap index is the largest one.
38 /* Packfile to which this bitmap index belongs to */
39 struct packed_git
*pack
;
42 * Mark the first `reuse_objects` in the packfile as reused:
43 * they will be sent as-is without using them for repacking
46 uint32_t reuse_objects
;
48 /* mmapped buffer of the whole bitmap index */
50 size_t map_size
; /* size of the mmaped buffer */
51 size_t map_pos
; /* current position when loading the index */
56 * Each bitmap marks which objects in the packfile are of the given
57 * type. This provides type information when yielding the objects from
58 * the packfile during a walk, which allows for better delta bases.
60 struct ewah_bitmap
*commits
;
61 struct ewah_bitmap
*trees
;
62 struct ewah_bitmap
*blobs
;
63 struct ewah_bitmap
*tags
;
65 /* Map from object ID -> `stored_bitmap` for all the bitmapped commits */
66 kh_oid_map_t
*bitmaps
;
68 /* Number of bitmapped commits */
71 /* If not NULL, this is a name-hash cache pointing into map. */
77 * When trying to perform bitmap operations with objects that are not
78 * packed in `pack`, these objects are added to this "fake index" and
79 * are assumed to appear at the end of the packfile for all operations
82 struct object
**objects
;
84 uint32_t count
, alloc
;
85 kh_oid_pos_t
*positions
;
88 /* Bitmap result of the last performed walk */
89 struct bitmap
*result
;
91 /* "have" bitmap from the last performed walk */
94 /* 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 uint32_t bitmap_num_objects(struct bitmap_index
*index
)
141 return index
->pack
->num_objects
;
144 static int load_bitmap_header(struct bitmap_index
*index
)
146 struct bitmap_disk_header
*header
= (void *)index
->map
;
147 size_t header_size
= sizeof(*header
) - GIT_MAX_RAWSZ
+ the_hash_algo
->rawsz
;
149 if (index
->map_size
< header_size
+ the_hash_algo
->rawsz
)
150 return error("Corrupted bitmap index (too small)");
152 if (memcmp(header
->magic
, BITMAP_IDX_SIGNATURE
, sizeof(BITMAP_IDX_SIGNATURE
)) != 0)
153 return error("Corrupted bitmap index file (wrong header)");
155 index
->version
= ntohs(header
->version
);
156 if (index
->version
!= 1)
157 return error("Unsupported version for bitmap index file (%d)", index
->version
);
159 /* Parse known bitmap format options */
161 uint32_t flags
= ntohs(header
->options
);
162 size_t cache_size
= st_mult(bitmap_num_objects(index
), sizeof(uint32_t));
163 unsigned char *index_end
= index
->map
+ index
->map_size
- the_hash_algo
->rawsz
;
165 if ((flags
& BITMAP_OPT_FULL_DAG
) == 0)
166 return error("Unsupported options for bitmap index file "
167 "(Git requires BITMAP_OPT_FULL_DAG)");
169 if (flags
& BITMAP_OPT_HASH_CACHE
) {
170 if (cache_size
> index_end
- index
->map
- header_size
)
171 return error("corrupted bitmap index file (too short to fit hash cache)");
172 index
->hashes
= (void *)(index_end
- cache_size
);
173 index_end
-= cache_size
;
177 index
->entry_count
= ntohl(header
->entry_count
);
178 index
->map_pos
+= header_size
;
182 static struct stored_bitmap
*store_bitmap(struct bitmap_index
*index
,
183 struct ewah_bitmap
*root
,
184 const struct object_id
*oid
,
185 struct stored_bitmap
*xor_with
,
188 struct stored_bitmap
*stored
;
192 stored
= xmalloc(sizeof(struct stored_bitmap
));
194 stored
->xor = xor_with
;
195 stored
->flags
= flags
;
196 oidcpy(&stored
->oid
, oid
);
198 hash_pos
= kh_put_oid_map(index
->bitmaps
, stored
->oid
, &ret
);
200 /* a 0 return code means the insertion succeeded with no changes,
201 * because the SHA1 already existed on the map. this is bad, there
202 * shouldn't be duplicated commits in the index */
204 error("Duplicate entry in bitmap index: %s", oid_to_hex(oid
));
208 kh_value(index
->bitmaps
, hash_pos
) = stored
;
212 static inline uint32_t read_be32(const unsigned char *buffer
, size_t *pos
)
214 uint32_t result
= get_be32(buffer
+ *pos
);
215 (*pos
) += sizeof(result
);
219 static inline uint8_t read_u8(const unsigned char *buffer
, size_t *pos
)
221 return buffer
[(*pos
)++];
224 #define MAX_XOR_OFFSET 160
226 static int nth_bitmap_object_oid(struct bitmap_index
*index
,
227 struct object_id
*oid
,
230 return nth_packed_object_id(oid
, index
->pack
, n
);
233 static int load_bitmap_entries_v1(struct bitmap_index
*index
)
236 struct stored_bitmap
*recent_bitmaps
[MAX_XOR_OFFSET
] = { NULL
};
238 for (i
= 0; i
< index
->entry_count
; ++i
) {
239 int xor_offset
, flags
;
240 struct ewah_bitmap
*bitmap
= NULL
;
241 struct stored_bitmap
*xor_bitmap
= NULL
;
242 uint32_t commit_idx_pos
;
243 struct object_id oid
;
245 if (index
->map_size
- index
->map_pos
< 6)
246 return error("corrupt ewah bitmap: truncated header for entry %d", i
);
248 commit_idx_pos
= read_be32(index
->map
, &index
->map_pos
);
249 xor_offset
= read_u8(index
->map
, &index
->map_pos
);
250 flags
= read_u8(index
->map
, &index
->map_pos
);
252 if (nth_bitmap_object_oid(index
, &oid
, commit_idx_pos
) < 0)
253 return error("corrupt ewah bitmap: commit index %u out of range",
254 (unsigned)commit_idx_pos
);
256 bitmap
= read_bitmap_1(index
);
260 if (xor_offset
> MAX_XOR_OFFSET
|| xor_offset
> i
)
261 return error("Corrupted bitmap pack index");
263 if (xor_offset
> 0) {
264 xor_bitmap
= recent_bitmaps
[(i
- xor_offset
) % MAX_XOR_OFFSET
];
266 if (xor_bitmap
== NULL
)
267 return error("Invalid XOR offset in bitmap pack index");
270 recent_bitmaps
[i
% MAX_XOR_OFFSET
] = store_bitmap(
271 index
, bitmap
, &oid
, xor_bitmap
, flags
);
277 static char *pack_bitmap_filename(struct packed_git
*p
)
281 if (!strip_suffix(p
->pack_name
, ".pack", &len
))
282 BUG("pack_name does not end in .pack");
283 return xstrfmt("%.*s.bitmap", (int)len
, p
->pack_name
);
286 static int open_pack_bitmap_1(struct bitmap_index
*bitmap_git
, struct packed_git
*packfile
)
292 if (open_pack_index(packfile
))
295 idx_name
= pack_bitmap_filename(packfile
);
296 fd
= git_open(idx_name
);
302 if (fstat(fd
, &st
)) {
307 if (bitmap_git
->pack
) {
308 warning("ignoring extra bitmap file: %s", packfile
->pack_name
);
313 if (!is_pack_valid(packfile
)) {
318 bitmap_git
->pack
= packfile
;
319 bitmap_git
->map_size
= xsize_t(st
.st_size
);
320 bitmap_git
->map
= xmmap(NULL
, bitmap_git
->map_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
321 bitmap_git
->map_pos
= 0;
324 if (load_bitmap_header(bitmap_git
) < 0) {
325 munmap(bitmap_git
->map
, bitmap_git
->map_size
);
326 bitmap_git
->map
= NULL
;
327 bitmap_git
->map_size
= 0;
334 static int load_pack_bitmap(struct bitmap_index
*bitmap_git
)
336 assert(bitmap_git
->map
);
338 bitmap_git
->bitmaps
= kh_init_oid_map();
339 bitmap_git
->ext_index
.positions
= kh_init_oid_pos();
340 if (load_pack_revindex(bitmap_git
->pack
))
343 if (!(bitmap_git
->commits
= read_bitmap_1(bitmap_git
)) ||
344 !(bitmap_git
->trees
= read_bitmap_1(bitmap_git
)) ||
345 !(bitmap_git
->blobs
= read_bitmap_1(bitmap_git
)) ||
346 !(bitmap_git
->tags
= read_bitmap_1(bitmap_git
)))
349 if (load_bitmap_entries_v1(bitmap_git
) < 0)
355 munmap(bitmap_git
->map
, bitmap_git
->map_size
);
356 bitmap_git
->map
= NULL
;
357 bitmap_git
->map_size
= 0;
359 kh_destroy_oid_map(bitmap_git
->bitmaps
);
360 bitmap_git
->bitmaps
= NULL
;
362 kh_destroy_oid_pos(bitmap_git
->ext_index
.positions
);
363 bitmap_git
->ext_index
.positions
= NULL
;
368 static int open_pack_bitmap(struct repository
*r
,
369 struct bitmap_index
*bitmap_git
)
371 struct packed_git
*p
;
374 assert(!bitmap_git
->map
);
376 for (p
= get_all_packs(r
); p
; p
= p
->next
) {
377 if (open_pack_bitmap_1(bitmap_git
, p
) == 0)
384 struct bitmap_index
*prepare_bitmap_git(struct repository
*r
)
386 struct bitmap_index
*bitmap_git
= xcalloc(1, sizeof(*bitmap_git
));
388 if (!open_pack_bitmap(r
, bitmap_git
) && !load_pack_bitmap(bitmap_git
))
391 free_bitmap_index(bitmap_git
);
395 struct include_data
{
396 struct bitmap_index
*bitmap_git
;
401 struct ewah_bitmap
*bitmap_for_commit(struct bitmap_index
*bitmap_git
,
402 struct commit
*commit
)
404 khiter_t hash_pos
= kh_get_oid_map(bitmap_git
->bitmaps
,
406 if (hash_pos
>= kh_end(bitmap_git
->bitmaps
))
408 return lookup_stored_bitmap(kh_value(bitmap_git
->bitmaps
, hash_pos
));
411 static inline int bitmap_position_extended(struct bitmap_index
*bitmap_git
,
412 const struct object_id
*oid
)
414 kh_oid_pos_t
*positions
= bitmap_git
->ext_index
.positions
;
415 khiter_t pos
= kh_get_oid_pos(positions
, *oid
);
417 if (pos
< kh_end(positions
)) {
418 int bitmap_pos
= kh_value(positions
, pos
);
419 return bitmap_pos
+ bitmap_num_objects(bitmap_git
);
425 static inline int bitmap_position_packfile(struct bitmap_index
*bitmap_git
,
426 const struct object_id
*oid
)
429 off_t offset
= find_pack_entry_one(oid
->hash
, bitmap_git
->pack
);
433 if (offset_to_pack_pos(bitmap_git
->pack
, offset
, &pos
) < 0)
438 static int bitmap_position(struct bitmap_index
*bitmap_git
,
439 const struct object_id
*oid
)
441 int pos
= bitmap_position_packfile(bitmap_git
, oid
);
442 return (pos
>= 0) ? pos
: bitmap_position_extended(bitmap_git
, oid
);
445 static int ext_index_add_object(struct bitmap_index
*bitmap_git
,
446 struct object
*object
, const char *name
)
448 struct eindex
*eindex
= &bitmap_git
->ext_index
;
454 hash_pos
= kh_put_oid_pos(eindex
->positions
, object
->oid
, &hash_ret
);
456 if (eindex
->count
>= eindex
->alloc
) {
457 eindex
->alloc
= (eindex
->alloc
+ 16) * 3 / 2;
458 REALLOC_ARRAY(eindex
->objects
, eindex
->alloc
);
459 REALLOC_ARRAY(eindex
->hashes
, eindex
->alloc
);
462 bitmap_pos
= eindex
->count
;
463 eindex
->objects
[eindex
->count
] = object
;
464 eindex
->hashes
[eindex
->count
] = pack_name_hash(name
);
465 kh_value(eindex
->positions
, hash_pos
) = bitmap_pos
;
468 bitmap_pos
= kh_value(eindex
->positions
, hash_pos
);
471 return bitmap_pos
+ bitmap_num_objects(bitmap_git
);
474 struct bitmap_show_data
{
475 struct bitmap_index
*bitmap_git
;
479 static void show_object(struct object
*object
, const char *name
, void *data_
)
481 struct bitmap_show_data
*data
= data_
;
484 bitmap_pos
= bitmap_position(data
->bitmap_git
, &object
->oid
);
487 bitmap_pos
= ext_index_add_object(data
->bitmap_git
, object
,
490 bitmap_set(data
->base
, bitmap_pos
);
493 static void show_commit(struct commit
*commit
, void *data
)
497 static int add_to_include_set(struct bitmap_index
*bitmap_git
,
498 struct include_data
*data
,
499 struct commit
*commit
,
502 struct ewah_bitmap
*partial
;
504 if (data
->seen
&& bitmap_get(data
->seen
, bitmap_pos
))
507 if (bitmap_get(data
->base
, bitmap_pos
))
510 partial
= bitmap_for_commit(bitmap_git
, commit
);
512 bitmap_or_ewah(data
->base
, partial
);
516 bitmap_set(data
->base
, bitmap_pos
);
520 static int should_include(struct commit
*commit
, void *_data
)
522 struct include_data
*data
= _data
;
525 bitmap_pos
= bitmap_position(data
->bitmap_git
, &commit
->object
.oid
);
527 bitmap_pos
= ext_index_add_object(data
->bitmap_git
,
528 (struct object
*)commit
,
531 if (!add_to_include_set(data
->bitmap_git
, data
, commit
, bitmap_pos
)) {
532 struct commit_list
*parent
= commit
->parents
;
535 parent
->item
->object
.flags
|= SEEN
;
536 parent
= parent
->next
;
545 static int should_include_obj(struct object
*obj
, void *_data
)
547 struct include_data
*data
= _data
;
550 bitmap_pos
= bitmap_position(data
->bitmap_git
, &obj
->oid
);
553 if ((data
->seen
&& bitmap_get(data
->seen
, bitmap_pos
)) ||
554 bitmap_get(data
->base
, bitmap_pos
)) {
561 static int add_commit_to_bitmap(struct bitmap_index
*bitmap_git
,
562 struct bitmap
**base
,
563 struct commit
*commit
)
565 struct ewah_bitmap
*or_with
= bitmap_for_commit(bitmap_git
, commit
);
571 *base
= ewah_to_bitmap(or_with
);
573 bitmap_or_ewah(*base
, or_with
);
578 static struct bitmap
*find_objects(struct bitmap_index
*bitmap_git
,
579 struct rev_info
*revs
,
580 struct object_list
*roots
,
582 struct list_objects_filter_options
*filter
)
584 struct bitmap
*base
= NULL
;
587 struct object_list
*not_mapped
= NULL
;
590 * Go through all the roots for the walk. The ones that have bitmaps
591 * on the bitmap index will be `or`ed together to form an initial
592 * global reachability analysis.
594 * The ones without bitmaps in the index will be stored in the
595 * `not_mapped_list` for further processing.
598 struct object
*object
= roots
->item
;
601 if (object
->type
== OBJ_COMMIT
&&
602 add_commit_to_bitmap(bitmap_git
, &base
, (struct commit
*)object
)) {
603 object
->flags
|= SEEN
;
607 object_list_insert(object
, ¬_mapped
);
611 * Best case scenario: We found bitmaps for all the roots,
612 * so the resulting `or` bitmap has the full reachability analysis
614 if (not_mapped
== NULL
)
620 * Let's iterate through all the roots that don't have bitmaps to
621 * check if we can determine them to be reachable from the existing
624 * If we cannot find them in the existing global bitmap, we'll need
625 * to push them to an actual walk and run it until we can confirm
629 struct object
*object
= roots
->item
;
633 pos
= bitmap_position(bitmap_git
, &object
->oid
);
635 if (pos
< 0 || base
== NULL
|| !bitmap_get(base
, pos
)) {
636 object
->flags
&= ~UNINTERESTING
;
637 add_pending_object(revs
, object
, "");
640 object
->flags
|= SEEN
;
645 struct include_data incdata
;
646 struct bitmap_show_data show_data
;
651 incdata
.bitmap_git
= bitmap_git
;
655 revs
->include_check
= should_include
;
656 revs
->include_check_obj
= should_include_obj
;
657 revs
->include_check_data
= &incdata
;
659 if (prepare_revision_walk(revs
))
660 die("revision walk setup failed");
662 show_data
.bitmap_git
= bitmap_git
;
663 show_data
.base
= base
;
665 traverse_commit_list_filtered(filter
, revs
,
666 show_commit
, show_object
,
669 revs
->include_check
= NULL
;
670 revs
->include_check_obj
= NULL
;
671 revs
->include_check_data
= NULL
;
677 static void show_extended_objects(struct bitmap_index
*bitmap_git
,
678 struct rev_info
*revs
,
679 show_reachable_fn show_reach
)
681 struct bitmap
*objects
= bitmap_git
->result
;
682 struct eindex
*eindex
= &bitmap_git
->ext_index
;
685 for (i
= 0; i
< eindex
->count
; ++i
) {
688 if (!bitmap_get(objects
, bitmap_num_objects(bitmap_git
) + i
))
691 obj
= eindex
->objects
[i
];
692 if ((obj
->type
== OBJ_BLOB
&& !revs
->blob_objects
) ||
693 (obj
->type
== OBJ_TREE
&& !revs
->tree_objects
) ||
694 (obj
->type
== OBJ_TAG
&& !revs
->tag_objects
))
697 show_reach(&obj
->oid
, obj
->type
, 0, eindex
->hashes
[i
], NULL
, 0);
701 static void init_type_iterator(struct ewah_iterator
*it
,
702 struct bitmap_index
*bitmap_git
,
703 enum object_type type
)
707 ewah_iterator_init(it
, bitmap_git
->commits
);
711 ewah_iterator_init(it
, bitmap_git
->trees
);
715 ewah_iterator_init(it
, bitmap_git
->blobs
);
719 ewah_iterator_init(it
, bitmap_git
->tags
);
723 BUG("object type %d not stored by bitmap type index", type
);
728 static void show_objects_for_type(
729 struct bitmap_index
*bitmap_git
,
730 enum object_type object_type
,
731 show_reachable_fn show_reach
)
736 struct ewah_iterator it
;
739 struct bitmap
*objects
= bitmap_git
->result
;
741 init_type_iterator(&it
, bitmap_git
, object_type
);
743 for (i
= 0; i
< objects
->word_alloc
&&
744 ewah_iterator_next(&filter
, &it
); i
++) {
745 eword_t word
= objects
->words
[i
] & filter
;
746 size_t pos
= (i
* BITS_IN_EWORD
);
751 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
752 struct object_id oid
;
753 uint32_t hash
= 0, index_pos
;
756 if ((word
>> offset
) == 0)
759 offset
+= ewah_bit_ctz64(word
>> offset
);
761 index_pos
= pack_pos_to_index(bitmap_git
->pack
, pos
+ offset
);
762 ofs
= pack_pos_to_offset(bitmap_git
->pack
, pos
+ offset
);
763 nth_packed_object_id(&oid
, bitmap_git
->pack
, index_pos
);
765 if (bitmap_git
->hashes
)
766 hash
= get_be32(bitmap_git
->hashes
+ index_pos
);
768 show_reach(&oid
, object_type
, 0, hash
, bitmap_git
->pack
, ofs
);
773 static int in_bitmapped_pack(struct bitmap_index
*bitmap_git
,
774 struct object_list
*roots
)
777 struct object
*object
= roots
->item
;
780 if (find_pack_entry_one(object
->oid
.hash
, bitmap_git
->pack
) > 0)
787 static struct bitmap
*find_tip_objects(struct bitmap_index
*bitmap_git
,
788 struct object_list
*tip_objects
,
789 enum object_type type
)
791 struct bitmap
*result
= bitmap_new();
792 struct object_list
*p
;
794 for (p
= tip_objects
; p
; p
= p
->next
) {
797 if (p
->item
->type
!= type
)
800 pos
= bitmap_position(bitmap_git
, &p
->item
->oid
);
804 bitmap_set(result
, pos
);
810 static void filter_bitmap_exclude_type(struct bitmap_index
*bitmap_git
,
811 struct object_list
*tip_objects
,
812 struct bitmap
*to_filter
,
813 enum object_type type
)
815 struct eindex
*eindex
= &bitmap_git
->ext_index
;
817 struct ewah_iterator it
;
822 * The non-bitmap version of this filter never removes
823 * objects which the other side specifically asked for,
824 * so we must match that behavior.
826 tips
= find_tip_objects(bitmap_git
, tip_objects
, type
);
829 * We can use the type-level bitmap for 'type' to work in whole
830 * words for the objects that are actually in the bitmapped
833 for (i
= 0, init_type_iterator(&it
, bitmap_git
, type
);
834 i
< to_filter
->word_alloc
&& ewah_iterator_next(&mask
, &it
);
836 if (i
< tips
->word_alloc
)
837 mask
&= ~tips
->words
[i
];
838 to_filter
->words
[i
] &= ~mask
;
842 * Clear any objects that weren't in the packfile (and so would
843 * not have been caught by the loop above. We'll have to check
846 for (i
= 0; i
< eindex
->count
; i
++) {
847 uint32_t pos
= i
+ bitmap_num_objects(bitmap_git
);
848 if (eindex
->objects
[i
]->type
== type
&&
849 bitmap_get(to_filter
, pos
) &&
850 !bitmap_get(tips
, pos
))
851 bitmap_unset(to_filter
, pos
);
857 static void filter_bitmap_blob_none(struct bitmap_index
*bitmap_git
,
858 struct object_list
*tip_objects
,
859 struct bitmap
*to_filter
)
861 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
,
865 static unsigned long get_size_by_pos(struct bitmap_index
*bitmap_git
,
868 struct packed_git
*pack
= bitmap_git
->pack
;
870 struct object_info oi
= OBJECT_INFO_INIT
;
874 if (pos
< bitmap_num_objects(bitmap_git
)) {
875 off_t ofs
= pack_pos_to_offset(pack
, pos
);
876 if (packed_object_info(the_repository
, pack
, ofs
, &oi
) < 0) {
877 struct object_id oid
;
878 nth_bitmap_object_oid(bitmap_git
, &oid
,
879 pack_pos_to_index(pack
, pos
));
880 die(_("unable to get size of %s"), oid_to_hex(&oid
));
883 struct eindex
*eindex
= &bitmap_git
->ext_index
;
884 struct object
*obj
= eindex
->objects
[pos
- bitmap_num_objects(bitmap_git
)];
885 if (oid_object_info_extended(the_repository
, &obj
->oid
, &oi
, 0) < 0)
886 die(_("unable to get size of %s"), oid_to_hex(&obj
->oid
));
892 static void filter_bitmap_blob_limit(struct bitmap_index
*bitmap_git
,
893 struct object_list
*tip_objects
,
894 struct bitmap
*to_filter
,
897 struct eindex
*eindex
= &bitmap_git
->ext_index
;
899 struct ewah_iterator it
;
903 tips
= find_tip_objects(bitmap_git
, tip_objects
, OBJ_BLOB
);
905 for (i
= 0, init_type_iterator(&it
, bitmap_git
, OBJ_BLOB
);
906 i
< to_filter
->word_alloc
&& ewah_iterator_next(&mask
, &it
);
908 eword_t word
= to_filter
->words
[i
] & mask
;
911 for (offset
= 0; offset
< BITS_IN_EWORD
; offset
++) {
914 if ((word
>> offset
) == 0)
916 offset
+= ewah_bit_ctz64(word
>> offset
);
917 pos
= i
* BITS_IN_EWORD
+ offset
;
919 if (!bitmap_get(tips
, pos
) &&
920 get_size_by_pos(bitmap_git
, pos
) >= limit
)
921 bitmap_unset(to_filter
, pos
);
925 for (i
= 0; i
< eindex
->count
; i
++) {
926 uint32_t pos
= i
+ bitmap_num_objects(bitmap_git
);
927 if (eindex
->objects
[i
]->type
== OBJ_BLOB
&&
928 bitmap_get(to_filter
, pos
) &&
929 !bitmap_get(tips
, pos
) &&
930 get_size_by_pos(bitmap_git
, pos
) >= limit
)
931 bitmap_unset(to_filter
, pos
);
937 static void filter_bitmap_tree_depth(struct bitmap_index
*bitmap_git
,
938 struct object_list
*tip_objects
,
939 struct bitmap
*to_filter
,
943 BUG("filter_bitmap_tree_depth given non-zero limit");
945 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
,
947 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
,
951 static void filter_bitmap_object_type(struct bitmap_index
*bitmap_git
,
952 struct object_list
*tip_objects
,
953 struct bitmap
*to_filter
,
954 enum object_type object_type
)
956 if (object_type
< OBJ_COMMIT
|| object_type
> OBJ_TAG
)
957 BUG("filter_bitmap_object_type given invalid object");
959 if (object_type
!= OBJ_TAG
)
960 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_TAG
);
961 if (object_type
!= OBJ_COMMIT
)
962 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_COMMIT
);
963 if (object_type
!= OBJ_TREE
)
964 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_TREE
);
965 if (object_type
!= OBJ_BLOB
)
966 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_BLOB
);
969 static int filter_bitmap(struct bitmap_index
*bitmap_git
,
970 struct object_list
*tip_objects
,
971 struct bitmap
*to_filter
,
972 struct list_objects_filter_options
*filter
)
974 if (!filter
|| filter
->choice
== LOFC_DISABLED
)
977 if (filter
->choice
== LOFC_BLOB_NONE
) {
979 filter_bitmap_blob_none(bitmap_git
, tip_objects
,
984 if (filter
->choice
== LOFC_BLOB_LIMIT
) {
986 filter_bitmap_blob_limit(bitmap_git
, tip_objects
,
988 filter
->blob_limit_value
);
992 if (filter
->choice
== LOFC_TREE_DEPTH
&&
993 filter
->tree_exclude_depth
== 0) {
995 filter_bitmap_tree_depth(bitmap_git
, tip_objects
,
997 filter
->tree_exclude_depth
);
1001 if (filter
->choice
== LOFC_OBJECT_TYPE
) {
1003 filter_bitmap_object_type(bitmap_git
, tip_objects
,
1005 filter
->object_type
);
1009 if (filter
->choice
== LOFC_COMBINE
) {
1011 for (i
= 0; i
< filter
->sub_nr
; i
++) {
1012 if (filter_bitmap(bitmap_git
, tip_objects
, to_filter
,
1013 &filter
->sub
[i
]) < 0)
1019 /* filter choice not handled */
1023 static int can_filter_bitmap(struct list_objects_filter_options
*filter
)
1025 return !filter_bitmap(NULL
, NULL
, NULL
, filter
);
1028 struct bitmap_index
*prepare_bitmap_walk(struct rev_info
*revs
,
1029 struct list_objects_filter_options
*filter
,
1030 int filter_provided_objects
)
1034 struct object_list
*wants
= NULL
;
1035 struct object_list
*haves
= NULL
;
1037 struct bitmap
*wants_bitmap
= NULL
;
1038 struct bitmap
*haves_bitmap
= NULL
;
1040 struct bitmap_index
*bitmap_git
;
1043 * We can't do pathspec limiting with bitmaps, because we don't know
1044 * which commits are associated with which object changes (let alone
1045 * even which objects are associated with which paths).
1050 if (!can_filter_bitmap(filter
))
1053 /* try to open a bitmapped pack, but don't parse it yet
1054 * because we may not need to use it */
1055 CALLOC_ARRAY(bitmap_git
, 1);
1056 if (open_pack_bitmap(revs
->repo
, bitmap_git
) < 0)
1059 for (i
= 0; i
< revs
->pending
.nr
; ++i
) {
1060 struct object
*object
= revs
->pending
.objects
[i
].item
;
1062 if (object
->type
== OBJ_NONE
)
1063 parse_object_or_die(&object
->oid
, NULL
);
1065 while (object
->type
== OBJ_TAG
) {
1066 struct tag
*tag
= (struct tag
*) object
;
1068 if (object
->flags
& UNINTERESTING
)
1069 object_list_insert(object
, &haves
);
1071 object_list_insert(object
, &wants
);
1073 object
= parse_object_or_die(get_tagged_oid(tag
), NULL
);
1074 object
->flags
|= (tag
->object
.flags
& UNINTERESTING
);
1077 if (object
->flags
& UNINTERESTING
)
1078 object_list_insert(object
, &haves
);
1080 object_list_insert(object
, &wants
);
1084 * if we have a HAVES list, but none of those haves is contained
1085 * in the packfile that has a bitmap, we don't have anything to
1088 if (haves
&& !in_bitmapped_pack(bitmap_git
, haves
))
1091 /* if we don't want anything, we're done here */
1096 * now we're going to use bitmaps, so load the actual bitmap entries
1097 * from disk. this is the point of no return; after this the rev_list
1098 * becomes invalidated and we must perform the revwalk through bitmaps
1100 if (load_pack_bitmap(bitmap_git
) < 0)
1103 object_array_clear(&revs
->pending
);
1106 revs
->ignore_missing_links
= 1;
1107 haves_bitmap
= find_objects(bitmap_git
, revs
, haves
, NULL
,
1109 reset_revision_walk();
1110 revs
->ignore_missing_links
= 0;
1112 if (haves_bitmap
== NULL
)
1113 BUG("failed to perform bitmap walk");
1116 wants_bitmap
= find_objects(bitmap_git
, revs
, wants
, haves_bitmap
,
1120 BUG("failed to perform bitmap walk");
1123 bitmap_and_not(wants_bitmap
, haves_bitmap
);
1125 filter_bitmap(bitmap_git
, (filter
&& filter_provided_objects
) ? NULL
: wants
,
1126 wants_bitmap
, filter
);
1128 bitmap_git
->result
= wants_bitmap
;
1129 bitmap_git
->haves
= haves_bitmap
;
1131 object_list_free(&wants
);
1132 object_list_free(&haves
);
1137 free_bitmap_index(bitmap_git
);
1138 object_list_free(&wants
);
1139 object_list_free(&haves
);
1143 static void try_partial_reuse(struct bitmap_index
*bitmap_git
,
1145 struct bitmap
*reuse
,
1146 struct pack_window
**w_curs
)
1148 off_t offset
, header
;
1149 enum object_type type
;
1152 if (pos
>= bitmap_num_objects(bitmap_git
))
1153 return; /* not actually in the pack or MIDX */
1155 offset
= header
= pack_pos_to_offset(bitmap_git
->pack
, pos
);
1156 type
= unpack_object_header(bitmap_git
->pack
, w_curs
, &offset
, &size
);
1158 return; /* broken packfile, punt */
1160 if (type
== OBJ_REF_DELTA
|| type
== OBJ_OFS_DELTA
) {
1165 * Find the position of the base object so we can look it up
1166 * in our bitmaps. If we can't come up with an offset, or if
1167 * that offset is not in the revidx, the pack is corrupt.
1168 * There's nothing we can do, so just punt on this object,
1169 * and the normal slow path will complain about it in
1172 base_offset
= get_delta_base(bitmap_git
->pack
, w_curs
,
1173 &offset
, type
, header
);
1176 if (offset_to_pack_pos(bitmap_git
->pack
, base_offset
, &base_pos
) < 0)
1180 * We assume delta dependencies always point backwards. This
1181 * lets us do a single pass, and is basically always true
1182 * due to the way OFS_DELTAs work. You would not typically
1183 * find REF_DELTA in a bitmapped pack, since we only bitmap
1184 * packs we write fresh, and OFS_DELTA is the default). But
1185 * let's double check to make sure the pack wasn't written with
1188 if (base_pos
>= pos
)
1192 * And finally, if we're not sending the base as part of our
1193 * reuse chunk, then don't send this object either. The base
1194 * would come after us, along with other objects not
1195 * necessarily in the pack, which means we'd need to convert
1196 * to REF_DELTA on the fly. Better to just let the normal
1197 * object_entry code path handle it.
1199 if (!bitmap_get(reuse
, base_pos
))
1204 * If we got here, then the object is OK to reuse. Mark it.
1206 bitmap_set(reuse
, pos
);
1209 int reuse_partial_packfile_from_bitmap(struct bitmap_index
*bitmap_git
,
1210 struct packed_git
**packfile_out
,
1212 struct bitmap
**reuse_out
)
1214 struct bitmap
*result
= bitmap_git
->result
;
1215 struct bitmap
*reuse
;
1216 struct pack_window
*w_curs
= NULL
;
1219 uint32_t objects_nr
= bitmap_num_objects(bitmap_git
);
1223 while (i
< result
->word_alloc
&& result
->words
[i
] == (eword_t
)~0)
1226 /* Don't mark objects not in the packfile */
1227 if (i
> objects_nr
/ BITS_IN_EWORD
)
1228 i
= objects_nr
/ BITS_IN_EWORD
;
1230 reuse
= bitmap_word_alloc(i
);
1231 memset(reuse
->words
, 0xFF, i
* sizeof(eword_t
));
1233 for (; i
< result
->word_alloc
; ++i
) {
1234 eword_t word
= result
->words
[i
];
1235 size_t pos
= (i
* BITS_IN_EWORD
);
1237 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
1238 if ((word
>> offset
) == 0)
1241 offset
+= ewah_bit_ctz64(word
>> offset
);
1242 try_partial_reuse(bitmap_git
, pos
+ offset
, reuse
, &w_curs
);
1246 unuse_pack(&w_curs
);
1248 *entries
= bitmap_popcount(reuse
);
1255 * Drop any reused objects from the result, since they will not
1256 * need to be handled separately.
1258 bitmap_and_not(result
, reuse
);
1259 *packfile_out
= bitmap_git
->pack
;
1264 int bitmap_walk_contains(struct bitmap_index
*bitmap_git
,
1265 struct bitmap
*bitmap
, const struct object_id
*oid
)
1272 idx
= bitmap_position(bitmap_git
, oid
);
1273 return idx
>= 0 && bitmap_get(bitmap
, idx
);
1276 void traverse_bitmap_commit_list(struct bitmap_index
*bitmap_git
,
1277 struct rev_info
*revs
,
1278 show_reachable_fn show_reachable
)
1280 assert(bitmap_git
->result
);
1282 show_objects_for_type(bitmap_git
, OBJ_COMMIT
, show_reachable
);
1283 if (revs
->tree_objects
)
1284 show_objects_for_type(bitmap_git
, OBJ_TREE
, show_reachable
);
1285 if (revs
->blob_objects
)
1286 show_objects_for_type(bitmap_git
, OBJ_BLOB
, show_reachable
);
1287 if (revs
->tag_objects
)
1288 show_objects_for_type(bitmap_git
, OBJ_TAG
, show_reachable
);
1290 show_extended_objects(bitmap_git
, revs
, show_reachable
);
1293 static uint32_t count_object_type(struct bitmap_index
*bitmap_git
,
1294 enum object_type type
)
1296 struct bitmap
*objects
= bitmap_git
->result
;
1297 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1299 uint32_t i
= 0, count
= 0;
1300 struct ewah_iterator it
;
1303 init_type_iterator(&it
, bitmap_git
, type
);
1305 while (i
< objects
->word_alloc
&& ewah_iterator_next(&filter
, &it
)) {
1306 eword_t word
= objects
->words
[i
++] & filter
;
1307 count
+= ewah_bit_popcount64(word
);
1310 for (i
= 0; i
< eindex
->count
; ++i
) {
1311 if (eindex
->objects
[i
]->type
== type
&&
1312 bitmap_get(objects
, bitmap_num_objects(bitmap_git
) + i
))
1319 void count_bitmap_commit_list(struct bitmap_index
*bitmap_git
,
1320 uint32_t *commits
, uint32_t *trees
,
1321 uint32_t *blobs
, uint32_t *tags
)
1323 assert(bitmap_git
->result
);
1326 *commits
= count_object_type(bitmap_git
, OBJ_COMMIT
);
1329 *trees
= count_object_type(bitmap_git
, OBJ_TREE
);
1332 *blobs
= count_object_type(bitmap_git
, OBJ_BLOB
);
1335 *tags
= count_object_type(bitmap_git
, OBJ_TAG
);
1338 struct bitmap_test_data
{
1339 struct bitmap_index
*bitmap_git
;
1340 struct bitmap
*base
;
1341 struct bitmap
*commits
;
1342 struct bitmap
*trees
;
1343 struct bitmap
*blobs
;
1344 struct bitmap
*tags
;
1345 struct progress
*prg
;
1349 static void test_bitmap_type(struct bitmap_test_data
*tdata
,
1350 struct object
*obj
, int pos
)
1352 enum object_type bitmap_type
= OBJ_NONE
;
1355 if (bitmap_get(tdata
->commits
, pos
)) {
1356 bitmap_type
= OBJ_COMMIT
;
1359 if (bitmap_get(tdata
->trees
, pos
)) {
1360 bitmap_type
= OBJ_TREE
;
1363 if (bitmap_get(tdata
->blobs
, pos
)) {
1364 bitmap_type
= OBJ_BLOB
;
1367 if (bitmap_get(tdata
->tags
, pos
)) {
1368 bitmap_type
= OBJ_TAG
;
1372 if (bitmap_type
== OBJ_NONE
)
1373 die("object %s not found in type bitmaps",
1374 oid_to_hex(&obj
->oid
));
1377 die("object %s does not have a unique type",
1378 oid_to_hex(&obj
->oid
));
1380 if (bitmap_type
!= obj
->type
)
1381 die("object %s: real type %s, expected: %s",
1382 oid_to_hex(&obj
->oid
),
1383 type_name(obj
->type
),
1384 type_name(bitmap_type
));
1387 static void test_show_object(struct object
*object
, const char *name
,
1390 struct bitmap_test_data
*tdata
= data
;
1393 bitmap_pos
= bitmap_position(tdata
->bitmap_git
, &object
->oid
);
1395 die("Object not in bitmap: %s\n", oid_to_hex(&object
->oid
));
1396 test_bitmap_type(tdata
, object
, bitmap_pos
);
1398 bitmap_set(tdata
->base
, bitmap_pos
);
1399 display_progress(tdata
->prg
, ++tdata
->seen
);
1402 static void test_show_commit(struct commit
*commit
, void *data
)
1404 struct bitmap_test_data
*tdata
= data
;
1407 bitmap_pos
= bitmap_position(tdata
->bitmap_git
,
1408 &commit
->object
.oid
);
1410 die("Object not in bitmap: %s\n", oid_to_hex(&commit
->object
.oid
));
1411 test_bitmap_type(tdata
, &commit
->object
, bitmap_pos
);
1413 bitmap_set(tdata
->base
, bitmap_pos
);
1414 display_progress(tdata
->prg
, ++tdata
->seen
);
1417 void test_bitmap_walk(struct rev_info
*revs
)
1419 struct object
*root
;
1420 struct bitmap
*result
= NULL
;
1421 size_t result_popcnt
;
1422 struct bitmap_test_data tdata
;
1423 struct bitmap_index
*bitmap_git
;
1424 struct ewah_bitmap
*bm
;
1426 if (!(bitmap_git
= prepare_bitmap_git(revs
->repo
)))
1427 die("failed to load bitmap indexes");
1429 if (revs
->pending
.nr
!= 1)
1430 die("you must specify exactly one commit to test");
1432 fprintf(stderr
, "Bitmap v%d test (%d entries loaded)\n",
1433 bitmap_git
->version
, bitmap_git
->entry_count
);
1435 root
= revs
->pending
.objects
[0].item
;
1436 bm
= bitmap_for_commit(bitmap_git
, (struct commit
*)root
);
1439 fprintf(stderr
, "Found bitmap for %s. %d bits / %08x checksum\n",
1440 oid_to_hex(&root
->oid
), (int)bm
->bit_size
, ewah_checksum(bm
));
1442 result
= ewah_to_bitmap(bm
);
1446 die("Commit %s doesn't have an indexed bitmap", oid_to_hex(&root
->oid
));
1448 revs
->tag_objects
= 1;
1449 revs
->tree_objects
= 1;
1450 revs
->blob_objects
= 1;
1452 result_popcnt
= bitmap_popcount(result
);
1454 if (prepare_revision_walk(revs
))
1455 die("revision walk setup failed");
1457 tdata
.bitmap_git
= bitmap_git
;
1458 tdata
.base
= bitmap_new();
1459 tdata
.commits
= ewah_to_bitmap(bitmap_git
->commits
);
1460 tdata
.trees
= ewah_to_bitmap(bitmap_git
->trees
);
1461 tdata
.blobs
= ewah_to_bitmap(bitmap_git
->blobs
);
1462 tdata
.tags
= ewah_to_bitmap(bitmap_git
->tags
);
1463 tdata
.prg
= start_progress("Verifying bitmap entries", result_popcnt
);
1466 traverse_commit_list(revs
, &test_show_commit
, &test_show_object
, &tdata
);
1468 stop_progress(&tdata
.prg
);
1470 if (bitmap_equals(result
, tdata
.base
))
1471 fprintf(stderr
, "OK!\n");
1473 die("mismatch in bitmap results");
1475 free_bitmap_index(bitmap_git
);
1478 int test_bitmap_commits(struct repository
*r
)
1480 struct bitmap_index
*bitmap_git
= prepare_bitmap_git(r
);
1481 struct object_id oid
;
1482 MAYBE_UNUSED
void *value
;
1485 die("failed to load bitmap indexes");
1487 kh_foreach(bitmap_git
->bitmaps
, oid
, value
, {
1488 printf("%s\n", oid_to_hex(&oid
));
1491 free_bitmap_index(bitmap_git
);
1496 int rebuild_bitmap(const uint32_t *reposition
,
1497 struct ewah_bitmap
*source
,
1498 struct bitmap
*dest
)
1501 struct ewah_iterator it
;
1504 ewah_iterator_init(&it
, source
);
1506 while (ewah_iterator_next(&word
, &it
)) {
1507 uint32_t offset
, bit_pos
;
1509 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
1510 if ((word
>> offset
) == 0)
1513 offset
+= ewah_bit_ctz64(word
>> offset
);
1515 bit_pos
= reposition
[pos
+ offset
];
1517 bitmap_set(dest
, bit_pos
- 1);
1518 else /* can't reuse, we don't have the object */
1522 pos
+= BITS_IN_EWORD
;
1527 uint32_t *create_bitmap_mapping(struct bitmap_index
*bitmap_git
,
1528 struct packing_data
*mapping
)
1530 uint32_t i
, num_objects
;
1531 uint32_t *reposition
;
1533 num_objects
= bitmap_num_objects(bitmap_git
);
1534 CALLOC_ARRAY(reposition
, num_objects
);
1536 for (i
= 0; i
< num_objects
; ++i
) {
1537 struct object_id oid
;
1538 struct object_entry
*oe
;
1540 nth_packed_object_id(&oid
, bitmap_git
->pack
,
1541 pack_pos_to_index(bitmap_git
->pack
, i
));
1542 oe
= packlist_find(mapping
, &oid
);
1545 reposition
[i
] = oe_in_pack_pos(mapping
, oe
) + 1;
1551 void free_bitmap_index(struct bitmap_index
*b
)
1557 munmap(b
->map
, b
->map_size
);
1558 ewah_pool_free(b
->commits
);
1559 ewah_pool_free(b
->trees
);
1560 ewah_pool_free(b
->blobs
);
1561 ewah_pool_free(b
->tags
);
1562 kh_destroy_oid_map(b
->bitmaps
);
1563 free(b
->ext_index
.objects
);
1564 free(b
->ext_index
.hashes
);
1565 bitmap_free(b
->result
);
1566 bitmap_free(b
->haves
);
1570 int bitmap_has_oid_in_uninteresting(struct bitmap_index
*bitmap_git
,
1571 const struct object_id
*oid
)
1573 return bitmap_git
&&
1574 bitmap_walk_contains(bitmap_git
, bitmap_git
->haves
, oid
);
1577 static off_t
get_disk_usage_for_type(struct bitmap_index
*bitmap_git
,
1578 enum object_type object_type
)
1580 struct bitmap
*result
= bitmap_git
->result
;
1581 struct packed_git
*pack
= bitmap_git
->pack
;
1583 struct ewah_iterator it
;
1587 init_type_iterator(&it
, bitmap_git
, object_type
);
1588 for (i
= 0; i
< result
->word_alloc
&&
1589 ewah_iterator_next(&filter
, &it
); i
++) {
1590 eword_t word
= result
->words
[i
] & filter
;
1591 size_t base
= (i
* BITS_IN_EWORD
);
1597 for (offset
= 0; offset
< BITS_IN_EWORD
; offset
++) {
1600 if ((word
>> offset
) == 0)
1603 offset
+= ewah_bit_ctz64(word
>> offset
);
1604 pos
= base
+ offset
;
1605 total
+= pack_pos_to_offset(pack
, pos
+ 1) -
1606 pack_pos_to_offset(pack
, pos
);
1613 static off_t
get_disk_usage_for_extended(struct bitmap_index
*bitmap_git
)
1615 struct bitmap
*result
= bitmap_git
->result
;
1616 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1618 struct object_info oi
= OBJECT_INFO_INIT
;
1622 oi
.disk_sizep
= &object_size
;
1624 for (i
= 0; i
< eindex
->count
; i
++) {
1625 struct object
*obj
= eindex
->objects
[i
];
1627 if (!bitmap_get(result
, bitmap_num_objects(bitmap_git
) + i
))
1630 if (oid_object_info_extended(the_repository
, &obj
->oid
, &oi
, 0) < 0)
1631 die(_("unable to get disk usage of %s"),
1632 oid_to_hex(&obj
->oid
));
1634 total
+= object_size
;
1639 off_t
get_disk_usage_from_bitmap(struct bitmap_index
*bitmap_git
,
1640 struct rev_info
*revs
)
1644 total
+= get_disk_usage_for_type(bitmap_git
, OBJ_COMMIT
);
1645 if (revs
->tree_objects
)
1646 total
+= get_disk_usage_for_type(bitmap_git
, OBJ_TREE
);
1647 if (revs
->blob_objects
)
1648 total
+= get_disk_usage_for_type(bitmap_git
, OBJ_BLOB
);
1649 if (revs
->tag_objects
)
1650 total
+= get_disk_usage_for_type(bitmap_git
, OBJ_TAG
);
1652 total
+= get_disk_usage_for_extended(bitmap_git
);
1657 const struct string_list
*bitmap_preferred_tips(struct repository
*r
)
1659 return repo_config_get_value_multi(r
, "pack.preferbitmaptips");