8 #include "list-objects.h"
10 #include "pack-bitmap.h"
11 #include "pack-revindex.h"
12 #include "pack-objects.h"
14 #include "repository.h"
15 #include "object-store.h"
16 #include "list-objects-filter-options.h"
21 * An entry on the bitmap index, representing the bitmap for a given
24 struct stored_bitmap
{
26 struct ewah_bitmap
*root
;
27 struct stored_bitmap
*xor;
32 * The active bitmap index for a repository. By design, repositories only have
33 * a single bitmap index available (the index for the biggest packfile in
34 * the repository), since bitmap indexes need full closure.
36 * If there is more than one bitmap index available (e.g. because of alternates),
37 * the active bitmap index is the largest one.
41 * The pack or multi-pack index (MIDX) that this bitmap index belongs
44 * Exactly one of these must be non-NULL; this specifies the object
45 * order used to interpret this bitmap.
47 struct packed_git
*pack
;
48 struct multi_pack_index
*midx
;
51 * Mark the first `reuse_objects` in the packfile as reused:
52 * they will be sent as-is without using them for repacking
55 uint32_t reuse_objects
;
57 /* mmapped buffer of the whole bitmap index */
59 size_t map_size
; /* size of the mmaped buffer */
60 size_t map_pos
; /* current position when loading the index */
65 * Each bitmap marks which objects in the packfile are of the given
66 * type. This provides type information when yielding the objects from
67 * the packfile during a walk, which allows for better delta bases.
69 struct ewah_bitmap
*commits
;
70 struct ewah_bitmap
*trees
;
71 struct ewah_bitmap
*blobs
;
72 struct ewah_bitmap
*tags
;
74 /* Map from object ID -> `stored_bitmap` for all the bitmapped commits */
75 kh_oid_map_t
*bitmaps
;
77 /* Number of bitmapped commits */
80 /* If not NULL, this is a name-hash cache pointing into map. */
83 /* The checksum of the packfile or MIDX; points into map. */
84 const unsigned char *checksum
;
89 * When trying to perform bitmap operations with objects that are not
90 * packed in `pack`, these objects are added to this "fake index" and
91 * are assumed to appear at the end of the packfile for all operations
94 struct object
**objects
;
96 uint32_t count
, alloc
;
97 kh_oid_pos_t
*positions
;
100 /* Bitmap result of the last performed walk */
101 struct bitmap
*result
;
103 /* "have" bitmap from the last performed walk */
104 struct bitmap
*haves
;
106 /* Version of the bitmap index */
107 unsigned int version
;
110 static struct ewah_bitmap
*lookup_stored_bitmap(struct stored_bitmap
*st
)
112 struct ewah_bitmap
*parent
;
113 struct ewah_bitmap
*composed
;
118 composed
= ewah_pool_new();
119 parent
= lookup_stored_bitmap(st
->xor);
120 ewah_xor(st
->root
, parent
, composed
);
122 ewah_pool_free(st
->root
);
130 * Read a bitmap from the current read position on the mmaped
131 * index, and increase the read position accordingly
133 static struct ewah_bitmap
*read_bitmap_1(struct bitmap_index
*index
)
135 struct ewah_bitmap
*b
= ewah_pool_new();
137 ssize_t bitmap_size
= ewah_read_mmap(b
,
138 index
->map
+ index
->map_pos
,
139 index
->map_size
- index
->map_pos
);
141 if (bitmap_size
< 0) {
142 error(_("failed to load bitmap index (corrupted?)"));
147 index
->map_pos
+= bitmap_size
;
151 static uint32_t bitmap_num_objects(struct bitmap_index
*index
)
154 return index
->midx
->num_objects
;
155 return index
->pack
->num_objects
;
158 static int load_bitmap_header(struct bitmap_index
*index
)
160 struct bitmap_disk_header
*header
= (void *)index
->map
;
161 size_t header_size
= sizeof(*header
) - GIT_MAX_RAWSZ
+ the_hash_algo
->rawsz
;
163 if (index
->map_size
< header_size
+ the_hash_algo
->rawsz
)
164 return error(_("corrupted bitmap index (too small)"));
166 if (memcmp(header
->magic
, BITMAP_IDX_SIGNATURE
, sizeof(BITMAP_IDX_SIGNATURE
)) != 0)
167 return error(_("corrupted bitmap index file (wrong header)"));
169 index
->version
= ntohs(header
->version
);
170 if (index
->version
!= 1)
171 return error(_("unsupported version '%d' for bitmap index file"), index
->version
);
173 /* Parse known bitmap format options */
175 uint32_t flags
= ntohs(header
->options
);
176 size_t cache_size
= st_mult(bitmap_num_objects(index
), sizeof(uint32_t));
177 unsigned char *index_end
= index
->map
+ index
->map_size
- the_hash_algo
->rawsz
;
179 if ((flags
& BITMAP_OPT_FULL_DAG
) == 0)
180 BUG("unsupported options for bitmap index file "
181 "(Git requires BITMAP_OPT_FULL_DAG)");
183 if (flags
& BITMAP_OPT_HASH_CACHE
) {
184 if (cache_size
> index_end
- index
->map
- header_size
)
185 return error(_("corrupted bitmap index file (too short to fit hash cache)"));
186 index
->hashes
= (void *)(index_end
- cache_size
);
187 index_end
-= cache_size
;
191 index
->entry_count
= ntohl(header
->entry_count
);
192 index
->checksum
= header
->checksum
;
193 index
->map_pos
+= header_size
;
197 static struct stored_bitmap
*store_bitmap(struct bitmap_index
*index
,
198 struct ewah_bitmap
*root
,
199 const struct object_id
*oid
,
200 struct stored_bitmap
*xor_with
,
203 struct stored_bitmap
*stored
;
207 stored
= xmalloc(sizeof(struct stored_bitmap
));
209 stored
->xor = xor_with
;
210 stored
->flags
= flags
;
211 oidcpy(&stored
->oid
, oid
);
213 hash_pos
= kh_put_oid_map(index
->bitmaps
, stored
->oid
, &ret
);
215 /* a 0 return code means the insertion succeeded with no changes,
216 * because the SHA1 already existed on the map. this is bad, there
217 * shouldn't be duplicated commits in the index */
219 error(_("duplicate entry in bitmap index: '%s'"), oid_to_hex(oid
));
223 kh_value(index
->bitmaps
, hash_pos
) = stored
;
227 static inline uint32_t read_be32(const unsigned char *buffer
, size_t *pos
)
229 uint32_t result
= get_be32(buffer
+ *pos
);
230 (*pos
) += sizeof(result
);
234 static inline uint8_t read_u8(const unsigned char *buffer
, size_t *pos
)
236 return buffer
[(*pos
)++];
239 #define MAX_XOR_OFFSET 160
241 static int nth_bitmap_object_oid(struct bitmap_index
*index
,
242 struct object_id
*oid
,
246 return nth_midxed_object_oid(oid
, index
->midx
, n
) ? 0 : -1;
247 return nth_packed_object_id(oid
, index
->pack
, n
);
250 static int load_bitmap_entries_v1(struct bitmap_index
*index
)
253 struct stored_bitmap
*recent_bitmaps
[MAX_XOR_OFFSET
] = { NULL
};
255 for (i
= 0; i
< index
->entry_count
; ++i
) {
256 int xor_offset
, flags
;
257 struct ewah_bitmap
*bitmap
= NULL
;
258 struct stored_bitmap
*xor_bitmap
= NULL
;
259 uint32_t commit_idx_pos
;
260 struct object_id oid
;
262 if (index
->map_size
- index
->map_pos
< 6)
263 return error(_("corrupt ewah bitmap: truncated header for entry %d"), i
);
265 commit_idx_pos
= read_be32(index
->map
, &index
->map_pos
);
266 xor_offset
= read_u8(index
->map
, &index
->map_pos
);
267 flags
= read_u8(index
->map
, &index
->map_pos
);
269 if (nth_bitmap_object_oid(index
, &oid
, commit_idx_pos
) < 0)
270 return error(_("corrupt ewah bitmap: commit index %u out of range"),
271 (unsigned)commit_idx_pos
);
273 bitmap
= read_bitmap_1(index
);
277 if (xor_offset
> MAX_XOR_OFFSET
|| xor_offset
> i
)
278 return error(_("corrupted bitmap pack index"));
280 if (xor_offset
> 0) {
281 xor_bitmap
= recent_bitmaps
[(i
- xor_offset
) % MAX_XOR_OFFSET
];
283 if (xor_bitmap
== NULL
)
284 return error(_("invalid XOR offset in bitmap pack index"));
287 recent_bitmaps
[i
% MAX_XOR_OFFSET
] = store_bitmap(
288 index
, bitmap
, &oid
, xor_bitmap
, flags
);
294 char *midx_bitmap_filename(struct multi_pack_index
*midx
)
296 struct strbuf buf
= STRBUF_INIT
;
298 get_midx_filename(&buf
, midx
->object_dir
);
299 strbuf_addf(&buf
, "-%s.bitmap", hash_to_hex(get_midx_checksum(midx
)));
301 return strbuf_detach(&buf
, NULL
);
304 char *pack_bitmap_filename(struct packed_git
*p
)
308 if (!strip_suffix(p
->pack_name
, ".pack", &len
))
309 BUG("pack_name does not end in .pack");
310 return xstrfmt("%.*s.bitmap", (int)len
, p
->pack_name
);
313 static int open_midx_bitmap_1(struct bitmap_index
*bitmap_git
,
314 struct multi_pack_index
*midx
)
317 char *bitmap_name
= midx_bitmap_filename(midx
);
318 int fd
= git_open(bitmap_name
);
325 if (fstat(fd
, &st
)) {
330 if (bitmap_git
->pack
|| bitmap_git
->midx
) {
331 struct strbuf buf
= STRBUF_INIT
;
332 get_midx_filename(&buf
, midx
->object_dir
);
333 /* ignore extra bitmap file; we can only handle one */
334 warning(_("ignoring extra bitmap file: '%s'"), buf
.buf
);
336 strbuf_release(&buf
);
340 bitmap_git
->midx
= midx
;
341 bitmap_git
->map_size
= xsize_t(st
.st_size
);
342 bitmap_git
->map_pos
= 0;
343 bitmap_git
->map
= xmmap(NULL
, bitmap_git
->map_size
, PROT_READ
,
347 if (load_bitmap_header(bitmap_git
) < 0)
350 if (!hasheq(get_midx_checksum(bitmap_git
->midx
), bitmap_git
->checksum
))
353 if (load_midx_revindex(bitmap_git
->midx
) < 0) {
354 warning(_("multi-pack bitmap is missing required reverse index"));
360 munmap(bitmap_git
->map
, bitmap_git
->map_size
);
361 bitmap_git
->map_size
= 0;
362 bitmap_git
->map_pos
= 0;
363 bitmap_git
->map
= NULL
;
364 bitmap_git
->midx
= NULL
;
368 static int open_pack_bitmap_1(struct bitmap_index
*bitmap_git
, struct packed_git
*packfile
)
374 if (open_pack_index(packfile
))
377 bitmap_name
= pack_bitmap_filename(packfile
);
378 fd
= git_open(bitmap_name
);
384 if (fstat(fd
, &st
)) {
389 if (bitmap_git
->pack
|| bitmap_git
->midx
) {
390 /* ignore extra bitmap file; we can only handle one */
391 warning(_("ignoring extra bitmap file: '%s'"), packfile
->pack_name
);
396 if (!is_pack_valid(packfile
)) {
401 bitmap_git
->pack
= packfile
;
402 bitmap_git
->map_size
= xsize_t(st
.st_size
);
403 bitmap_git
->map
= xmmap(NULL
, bitmap_git
->map_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
404 bitmap_git
->map_pos
= 0;
407 if (load_bitmap_header(bitmap_git
) < 0) {
408 munmap(bitmap_git
->map
, bitmap_git
->map_size
);
409 bitmap_git
->map
= NULL
;
410 bitmap_git
->map_size
= 0;
411 bitmap_git
->map_pos
= 0;
412 bitmap_git
->pack
= NULL
;
419 static int load_reverse_index(struct bitmap_index
*bitmap_git
)
421 if (bitmap_is_midx(bitmap_git
)) {
426 * The multi-pack-index's .rev file is already loaded via
427 * open_pack_bitmap_1().
429 * But we still need to open the individual pack .rev files,
430 * since we will need to make use of them in pack-objects.
432 for (i
= 0; i
< bitmap_git
->midx
->num_packs
; i
++) {
433 if (prepare_midx_pack(the_repository
, bitmap_git
->midx
, i
))
434 die(_("load_reverse_index: could not open pack"));
435 ret
= load_pack_revindex(bitmap_git
->midx
->packs
[i
]);
441 return load_pack_revindex(bitmap_git
->pack
);
444 static int load_bitmap(struct bitmap_index
*bitmap_git
)
446 assert(bitmap_git
->map
);
448 bitmap_git
->bitmaps
= kh_init_oid_map();
449 bitmap_git
->ext_index
.positions
= kh_init_oid_pos();
451 if (load_reverse_index(bitmap_git
))
454 if (!(bitmap_git
->commits
= read_bitmap_1(bitmap_git
)) ||
455 !(bitmap_git
->trees
= read_bitmap_1(bitmap_git
)) ||
456 !(bitmap_git
->blobs
= read_bitmap_1(bitmap_git
)) ||
457 !(bitmap_git
->tags
= read_bitmap_1(bitmap_git
)))
460 if (load_bitmap_entries_v1(bitmap_git
) < 0)
466 munmap(bitmap_git
->map
, bitmap_git
->map_size
);
467 bitmap_git
->map
= NULL
;
468 bitmap_git
->map_size
= 0;
470 kh_destroy_oid_map(bitmap_git
->bitmaps
);
471 bitmap_git
->bitmaps
= NULL
;
473 kh_destroy_oid_pos(bitmap_git
->ext_index
.positions
);
474 bitmap_git
->ext_index
.positions
= NULL
;
479 static int open_pack_bitmap(struct repository
*r
,
480 struct bitmap_index
*bitmap_git
)
482 struct packed_git
*p
;
485 assert(!bitmap_git
->map
);
487 for (p
= get_all_packs(r
); p
; p
= p
->next
) {
488 if (open_pack_bitmap_1(bitmap_git
, p
) == 0)
495 static int open_midx_bitmap(struct repository
*r
,
496 struct bitmap_index
*bitmap_git
)
498 struct multi_pack_index
*midx
;
500 assert(!bitmap_git
->map
);
502 for (midx
= get_multi_pack_index(r
); midx
; midx
= midx
->next
) {
503 if (!open_midx_bitmap_1(bitmap_git
, midx
))
509 static int open_bitmap(struct repository
*r
,
510 struct bitmap_index
*bitmap_git
)
512 assert(!bitmap_git
->map
);
514 if (!open_midx_bitmap(r
, bitmap_git
))
516 return open_pack_bitmap(r
, bitmap_git
);
519 struct bitmap_index
*prepare_bitmap_git(struct repository
*r
)
521 struct bitmap_index
*bitmap_git
= xcalloc(1, sizeof(*bitmap_git
));
523 if (!open_bitmap(r
, bitmap_git
) && !load_bitmap(bitmap_git
))
526 free_bitmap_index(bitmap_git
);
530 struct bitmap_index
*prepare_midx_bitmap_git(struct multi_pack_index
*midx
)
532 struct bitmap_index
*bitmap_git
= xcalloc(1, sizeof(*bitmap_git
));
534 if (!open_midx_bitmap_1(bitmap_git
, midx
) && !load_bitmap(bitmap_git
))
537 free_bitmap_index(bitmap_git
);
541 struct include_data
{
542 struct bitmap_index
*bitmap_git
;
547 struct ewah_bitmap
*bitmap_for_commit(struct bitmap_index
*bitmap_git
,
548 struct commit
*commit
)
550 khiter_t hash_pos
= kh_get_oid_map(bitmap_git
->bitmaps
,
552 if (hash_pos
>= kh_end(bitmap_git
->bitmaps
))
554 return lookup_stored_bitmap(kh_value(bitmap_git
->bitmaps
, hash_pos
));
557 static inline int bitmap_position_extended(struct bitmap_index
*bitmap_git
,
558 const struct object_id
*oid
)
560 kh_oid_pos_t
*positions
= bitmap_git
->ext_index
.positions
;
561 khiter_t pos
= kh_get_oid_pos(positions
, *oid
);
563 if (pos
< kh_end(positions
)) {
564 int bitmap_pos
= kh_value(positions
, pos
);
565 return bitmap_pos
+ bitmap_num_objects(bitmap_git
);
571 static inline int bitmap_position_packfile(struct bitmap_index
*bitmap_git
,
572 const struct object_id
*oid
)
575 off_t offset
= find_pack_entry_one(oid
->hash
, bitmap_git
->pack
);
579 if (offset_to_pack_pos(bitmap_git
->pack
, offset
, &pos
) < 0)
584 static int bitmap_position_midx(struct bitmap_index
*bitmap_git
,
585 const struct object_id
*oid
)
588 if (!bsearch_midx(oid
, bitmap_git
->midx
, &want
))
591 if (midx_to_pack_pos(bitmap_git
->midx
, want
, &got
) < 0)
596 static int bitmap_position(struct bitmap_index
*bitmap_git
,
597 const struct object_id
*oid
)
600 if (bitmap_is_midx(bitmap_git
))
601 pos
= bitmap_position_midx(bitmap_git
, oid
);
603 pos
= bitmap_position_packfile(bitmap_git
, oid
);
604 return (pos
>= 0) ? pos
: bitmap_position_extended(bitmap_git
, oid
);
607 static int ext_index_add_object(struct bitmap_index
*bitmap_git
,
608 struct object
*object
, const char *name
)
610 struct eindex
*eindex
= &bitmap_git
->ext_index
;
616 hash_pos
= kh_put_oid_pos(eindex
->positions
, object
->oid
, &hash_ret
);
618 if (eindex
->count
>= eindex
->alloc
) {
619 eindex
->alloc
= (eindex
->alloc
+ 16) * 3 / 2;
620 REALLOC_ARRAY(eindex
->objects
, eindex
->alloc
);
621 REALLOC_ARRAY(eindex
->hashes
, eindex
->alloc
);
624 bitmap_pos
= eindex
->count
;
625 eindex
->objects
[eindex
->count
] = object
;
626 eindex
->hashes
[eindex
->count
] = pack_name_hash(name
);
627 kh_value(eindex
->positions
, hash_pos
) = bitmap_pos
;
630 bitmap_pos
= kh_value(eindex
->positions
, hash_pos
);
633 return bitmap_pos
+ bitmap_num_objects(bitmap_git
);
636 struct bitmap_show_data
{
637 struct bitmap_index
*bitmap_git
;
641 static void show_object(struct object
*object
, const char *name
, void *data_
)
643 struct bitmap_show_data
*data
= data_
;
646 bitmap_pos
= bitmap_position(data
->bitmap_git
, &object
->oid
);
649 bitmap_pos
= ext_index_add_object(data
->bitmap_git
, object
,
652 bitmap_set(data
->base
, bitmap_pos
);
655 static void show_commit(struct commit
*commit
, void *data
)
659 static int add_to_include_set(struct bitmap_index
*bitmap_git
,
660 struct include_data
*data
,
661 struct commit
*commit
,
664 struct ewah_bitmap
*partial
;
666 if (data
->seen
&& bitmap_get(data
->seen
, bitmap_pos
))
669 if (bitmap_get(data
->base
, bitmap_pos
))
672 partial
= bitmap_for_commit(bitmap_git
, commit
);
674 bitmap_or_ewah(data
->base
, partial
);
678 bitmap_set(data
->base
, bitmap_pos
);
682 static int should_include(struct commit
*commit
, void *_data
)
684 struct include_data
*data
= _data
;
687 bitmap_pos
= bitmap_position(data
->bitmap_git
, &commit
->object
.oid
);
689 bitmap_pos
= ext_index_add_object(data
->bitmap_git
,
690 (struct object
*)commit
,
693 if (!add_to_include_set(data
->bitmap_git
, data
, commit
, bitmap_pos
)) {
694 struct commit_list
*parent
= commit
->parents
;
697 parent
->item
->object
.flags
|= SEEN
;
698 parent
= parent
->next
;
707 static int should_include_obj(struct object
*obj
, void *_data
)
709 struct include_data
*data
= _data
;
712 bitmap_pos
= bitmap_position(data
->bitmap_git
, &obj
->oid
);
715 if ((data
->seen
&& bitmap_get(data
->seen
, bitmap_pos
)) ||
716 bitmap_get(data
->base
, bitmap_pos
)) {
723 static int add_commit_to_bitmap(struct bitmap_index
*bitmap_git
,
724 struct bitmap
**base
,
725 struct commit
*commit
)
727 struct ewah_bitmap
*or_with
= bitmap_for_commit(bitmap_git
, commit
);
733 *base
= ewah_to_bitmap(or_with
);
735 bitmap_or_ewah(*base
, or_with
);
740 static struct bitmap
*find_objects(struct bitmap_index
*bitmap_git
,
741 struct rev_info
*revs
,
742 struct object_list
*roots
,
745 struct bitmap
*base
= NULL
;
748 struct object_list
*not_mapped
= NULL
;
751 * Go through all the roots for the walk. The ones that have bitmaps
752 * on the bitmap index will be `or`ed together to form an initial
753 * global reachability analysis.
755 * The ones without bitmaps in the index will be stored in the
756 * `not_mapped_list` for further processing.
759 struct object
*object
= roots
->item
;
762 if (object
->type
== OBJ_COMMIT
&&
763 add_commit_to_bitmap(bitmap_git
, &base
, (struct commit
*)object
)) {
764 object
->flags
|= SEEN
;
768 object_list_insert(object
, ¬_mapped
);
772 * Best case scenario: We found bitmaps for all the roots,
773 * so the resulting `or` bitmap has the full reachability analysis
775 if (not_mapped
== NULL
)
781 * Let's iterate through all the roots that don't have bitmaps to
782 * check if we can determine them to be reachable from the existing
785 * If we cannot find them in the existing global bitmap, we'll need
786 * to push them to an actual walk and run it until we can confirm
790 struct object
*object
= roots
->item
;
794 pos
= bitmap_position(bitmap_git
, &object
->oid
);
796 if (pos
< 0 || base
== NULL
|| !bitmap_get(base
, pos
)) {
797 object
->flags
&= ~UNINTERESTING
;
798 add_pending_object(revs
, object
, "");
801 object
->flags
|= SEEN
;
806 struct include_data incdata
;
807 struct bitmap_show_data show_data
;
812 incdata
.bitmap_git
= bitmap_git
;
816 revs
->include_check
= should_include
;
817 revs
->include_check_obj
= should_include_obj
;
818 revs
->include_check_data
= &incdata
;
820 if (prepare_revision_walk(revs
))
821 die(_("revision walk setup failed"));
823 show_data
.bitmap_git
= bitmap_git
;
824 show_data
.base
= base
;
826 traverse_commit_list(revs
,
827 show_commit
, show_object
,
830 revs
->include_check
= NULL
;
831 revs
->include_check_obj
= NULL
;
832 revs
->include_check_data
= NULL
;
838 static void show_extended_objects(struct bitmap_index
*bitmap_git
,
839 struct rev_info
*revs
,
840 show_reachable_fn show_reach
)
842 struct bitmap
*objects
= bitmap_git
->result
;
843 struct eindex
*eindex
= &bitmap_git
->ext_index
;
846 for (i
= 0; i
< eindex
->count
; ++i
) {
849 if (!bitmap_get(objects
, bitmap_num_objects(bitmap_git
) + i
))
852 obj
= eindex
->objects
[i
];
853 if ((obj
->type
== OBJ_BLOB
&& !revs
->blob_objects
) ||
854 (obj
->type
== OBJ_TREE
&& !revs
->tree_objects
) ||
855 (obj
->type
== OBJ_TAG
&& !revs
->tag_objects
))
858 show_reach(&obj
->oid
, obj
->type
, 0, eindex
->hashes
[i
], NULL
, 0);
862 static void init_type_iterator(struct ewah_iterator
*it
,
863 struct bitmap_index
*bitmap_git
,
864 enum object_type type
)
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
);
884 BUG("object type %d not stored by bitmap type index", type
);
889 static void show_objects_for_type(
890 struct bitmap_index
*bitmap_git
,
891 enum object_type object_type
,
892 show_reachable_fn show_reach
)
897 struct ewah_iterator it
;
900 struct bitmap
*objects
= bitmap_git
->result
;
902 init_type_iterator(&it
, bitmap_git
, object_type
);
904 for (i
= 0; i
< objects
->word_alloc
&&
905 ewah_iterator_next(&filter
, &it
); i
++) {
906 eword_t word
= objects
->words
[i
] & filter
;
907 size_t pos
= (i
* BITS_IN_EWORD
);
912 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
913 struct packed_git
*pack
;
914 struct object_id oid
;
915 uint32_t hash
= 0, index_pos
;
918 if ((word
>> offset
) == 0)
921 offset
+= ewah_bit_ctz64(word
>> offset
);
923 if (bitmap_is_midx(bitmap_git
)) {
924 struct multi_pack_index
*m
= bitmap_git
->midx
;
927 index_pos
= pack_pos_to_midx(m
, pos
+ offset
);
928 ofs
= nth_midxed_offset(m
, index_pos
);
929 nth_midxed_object_oid(&oid
, m
, index_pos
);
931 pack_id
= nth_midxed_pack_int_id(m
, index_pos
);
932 pack
= bitmap_git
->midx
->packs
[pack_id
];
934 index_pos
= pack_pos_to_index(bitmap_git
->pack
, pos
+ offset
);
935 ofs
= pack_pos_to_offset(bitmap_git
->pack
, pos
+ offset
);
936 nth_bitmap_object_oid(bitmap_git
, &oid
, index_pos
);
938 pack
= bitmap_git
->pack
;
941 if (bitmap_git
->hashes
)
942 hash
= get_be32(bitmap_git
->hashes
+ index_pos
);
944 show_reach(&oid
, object_type
, 0, hash
, pack
, ofs
);
949 static int in_bitmapped_pack(struct bitmap_index
*bitmap_git
,
950 struct object_list
*roots
)
953 struct object
*object
= roots
->item
;
956 if (bitmap_is_midx(bitmap_git
)) {
957 if (bsearch_midx(&object
->oid
, bitmap_git
->midx
, NULL
))
960 if (find_pack_entry_one(object
->oid
.hash
, bitmap_git
->pack
) > 0)
968 static struct bitmap
*find_tip_objects(struct bitmap_index
*bitmap_git
,
969 struct object_list
*tip_objects
,
970 enum object_type type
)
972 struct bitmap
*result
= bitmap_new();
973 struct object_list
*p
;
975 for (p
= tip_objects
; p
; p
= p
->next
) {
978 if (p
->item
->type
!= type
)
981 pos
= bitmap_position(bitmap_git
, &p
->item
->oid
);
985 bitmap_set(result
, pos
);
991 static void filter_bitmap_exclude_type(struct bitmap_index
*bitmap_git
,
992 struct object_list
*tip_objects
,
993 struct bitmap
*to_filter
,
994 enum object_type type
)
996 struct eindex
*eindex
= &bitmap_git
->ext_index
;
998 struct ewah_iterator it
;
1003 * The non-bitmap version of this filter never removes
1004 * objects which the other side specifically asked for,
1005 * so we must match that behavior.
1007 tips
= find_tip_objects(bitmap_git
, tip_objects
, type
);
1010 * We can use the type-level bitmap for 'type' to work in whole
1011 * words for the objects that are actually in the bitmapped
1014 for (i
= 0, init_type_iterator(&it
, bitmap_git
, type
);
1015 i
< to_filter
->word_alloc
&& ewah_iterator_next(&mask
, &it
);
1017 if (i
< tips
->word_alloc
)
1018 mask
&= ~tips
->words
[i
];
1019 to_filter
->words
[i
] &= ~mask
;
1023 * Clear any objects that weren't in the packfile (and so would
1024 * not have been caught by the loop above. We'll have to check
1025 * them individually.
1027 for (i
= 0; i
< eindex
->count
; i
++) {
1028 uint32_t pos
= i
+ bitmap_num_objects(bitmap_git
);
1029 if (eindex
->objects
[i
]->type
== type
&&
1030 bitmap_get(to_filter
, pos
) &&
1031 !bitmap_get(tips
, pos
))
1032 bitmap_unset(to_filter
, pos
);
1038 static void filter_bitmap_blob_none(struct bitmap_index
*bitmap_git
,
1039 struct object_list
*tip_objects
,
1040 struct bitmap
*to_filter
)
1042 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
,
1046 static unsigned long get_size_by_pos(struct bitmap_index
*bitmap_git
,
1050 struct object_info oi
= OBJECT_INFO_INIT
;
1054 if (pos
< bitmap_num_objects(bitmap_git
)) {
1055 struct packed_git
*pack
;
1058 if (bitmap_is_midx(bitmap_git
)) {
1059 uint32_t midx_pos
= pack_pos_to_midx(bitmap_git
->midx
, pos
);
1060 uint32_t pack_id
= nth_midxed_pack_int_id(bitmap_git
->midx
, midx_pos
);
1062 pack
= bitmap_git
->midx
->packs
[pack_id
];
1063 ofs
= nth_midxed_offset(bitmap_git
->midx
, midx_pos
);
1065 pack
= bitmap_git
->pack
;
1066 ofs
= pack_pos_to_offset(pack
, pos
);
1069 if (packed_object_info(the_repository
, pack
, ofs
, &oi
) < 0) {
1070 struct object_id oid
;
1071 nth_bitmap_object_oid(bitmap_git
, &oid
,
1072 pack_pos_to_index(pack
, pos
));
1073 die(_("unable to get size of %s"), oid_to_hex(&oid
));
1076 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1077 struct object
*obj
= eindex
->objects
[pos
- bitmap_num_objects(bitmap_git
)];
1078 if (oid_object_info_extended(the_repository
, &obj
->oid
, &oi
, 0) < 0)
1079 die(_("unable to get size of %s"), oid_to_hex(&obj
->oid
));
1085 static void filter_bitmap_blob_limit(struct bitmap_index
*bitmap_git
,
1086 struct object_list
*tip_objects
,
1087 struct bitmap
*to_filter
,
1088 unsigned long limit
)
1090 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1091 struct bitmap
*tips
;
1092 struct ewah_iterator it
;
1096 tips
= find_tip_objects(bitmap_git
, tip_objects
, OBJ_BLOB
);
1098 for (i
= 0, init_type_iterator(&it
, bitmap_git
, OBJ_BLOB
);
1099 i
< to_filter
->word_alloc
&& ewah_iterator_next(&mask
, &it
);
1101 eword_t word
= to_filter
->words
[i
] & mask
;
1104 for (offset
= 0; offset
< BITS_IN_EWORD
; offset
++) {
1107 if ((word
>> offset
) == 0)
1109 offset
+= ewah_bit_ctz64(word
>> offset
);
1110 pos
= i
* BITS_IN_EWORD
+ offset
;
1112 if (!bitmap_get(tips
, pos
) &&
1113 get_size_by_pos(bitmap_git
, pos
) >= limit
)
1114 bitmap_unset(to_filter
, pos
);
1118 for (i
= 0; i
< eindex
->count
; i
++) {
1119 uint32_t pos
= i
+ bitmap_num_objects(bitmap_git
);
1120 if (eindex
->objects
[i
]->type
== OBJ_BLOB
&&
1121 bitmap_get(to_filter
, pos
) &&
1122 !bitmap_get(tips
, pos
) &&
1123 get_size_by_pos(bitmap_git
, pos
) >= limit
)
1124 bitmap_unset(to_filter
, pos
);
1130 static void filter_bitmap_tree_depth(struct bitmap_index
*bitmap_git
,
1131 struct object_list
*tip_objects
,
1132 struct bitmap
*to_filter
,
1133 unsigned long limit
)
1136 BUG("filter_bitmap_tree_depth given non-zero limit");
1138 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
,
1140 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
,
1144 static void filter_bitmap_object_type(struct bitmap_index
*bitmap_git
,
1145 struct object_list
*tip_objects
,
1146 struct bitmap
*to_filter
,
1147 enum object_type object_type
)
1149 if (object_type
< OBJ_COMMIT
|| object_type
> OBJ_TAG
)
1150 BUG("filter_bitmap_object_type given invalid object");
1152 if (object_type
!= OBJ_TAG
)
1153 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_TAG
);
1154 if (object_type
!= OBJ_COMMIT
)
1155 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_COMMIT
);
1156 if (object_type
!= OBJ_TREE
)
1157 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_TREE
);
1158 if (object_type
!= OBJ_BLOB
)
1159 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_BLOB
);
1162 static int filter_bitmap(struct bitmap_index
*bitmap_git
,
1163 struct object_list
*tip_objects
,
1164 struct bitmap
*to_filter
,
1165 struct list_objects_filter_options
*filter
)
1167 if (!filter
|| filter
->choice
== LOFC_DISABLED
)
1170 if (filter
->choice
== LOFC_BLOB_NONE
) {
1172 filter_bitmap_blob_none(bitmap_git
, tip_objects
,
1177 if (filter
->choice
== LOFC_BLOB_LIMIT
) {
1179 filter_bitmap_blob_limit(bitmap_git
, tip_objects
,
1181 filter
->blob_limit_value
);
1185 if (filter
->choice
== LOFC_TREE_DEPTH
&&
1186 filter
->tree_exclude_depth
== 0) {
1188 filter_bitmap_tree_depth(bitmap_git
, tip_objects
,
1190 filter
->tree_exclude_depth
);
1194 if (filter
->choice
== LOFC_OBJECT_TYPE
) {
1196 filter_bitmap_object_type(bitmap_git
, tip_objects
,
1198 filter
->object_type
);
1202 if (filter
->choice
== LOFC_COMBINE
) {
1204 for (i
= 0; i
< filter
->sub_nr
; i
++) {
1205 if (filter_bitmap(bitmap_git
, tip_objects
, to_filter
,
1206 &filter
->sub
[i
]) < 0)
1212 /* filter choice not handled */
1216 static int can_filter_bitmap(struct list_objects_filter_options
*filter
)
1218 return !filter_bitmap(NULL
, NULL
, NULL
, filter
);
1221 struct bitmap_index
*prepare_bitmap_walk(struct rev_info
*revs
,
1222 int filter_provided_objects
)
1226 struct object_list
*wants
= NULL
;
1227 struct object_list
*haves
= NULL
;
1229 struct bitmap
*wants_bitmap
= NULL
;
1230 struct bitmap
*haves_bitmap
= NULL
;
1232 struct bitmap_index
*bitmap_git
;
1235 * We can't do pathspec limiting with bitmaps, because we don't know
1236 * which commits are associated with which object changes (let alone
1237 * even which objects are associated with which paths).
1242 if (!can_filter_bitmap(&revs
->filter
))
1245 /* try to open a bitmapped pack, but don't parse it yet
1246 * because we may not need to use it */
1247 CALLOC_ARRAY(bitmap_git
, 1);
1248 if (open_bitmap(revs
->repo
, bitmap_git
) < 0)
1251 for (i
= 0; i
< revs
->pending
.nr
; ++i
) {
1252 struct object
*object
= revs
->pending
.objects
[i
].item
;
1254 if (object
->type
== OBJ_NONE
)
1255 parse_object_or_die(&object
->oid
, NULL
);
1257 while (object
->type
== OBJ_TAG
) {
1258 struct tag
*tag
= (struct tag
*) object
;
1260 if (object
->flags
& UNINTERESTING
)
1261 object_list_insert(object
, &haves
);
1263 object_list_insert(object
, &wants
);
1265 object
= parse_object_or_die(get_tagged_oid(tag
), NULL
);
1266 object
->flags
|= (tag
->object
.flags
& UNINTERESTING
);
1269 if (object
->flags
& UNINTERESTING
)
1270 object_list_insert(object
, &haves
);
1272 object_list_insert(object
, &wants
);
1276 * if we have a HAVES list, but none of those haves is contained
1277 * in the packfile that has a bitmap, we don't have anything to
1280 if (haves
&& !in_bitmapped_pack(bitmap_git
, haves
))
1283 /* if we don't want anything, we're done here */
1288 * now we're going to use bitmaps, so load the actual bitmap entries
1289 * from disk. this is the point of no return; after this the rev_list
1290 * becomes invalidated and we must perform the revwalk through bitmaps
1292 if (load_bitmap(bitmap_git
) < 0)
1295 object_array_clear(&revs
->pending
);
1298 revs
->ignore_missing_links
= 1;
1299 haves_bitmap
= find_objects(bitmap_git
, revs
, haves
, NULL
);
1300 reset_revision_walk();
1301 revs
->ignore_missing_links
= 0;
1303 if (haves_bitmap
== NULL
)
1304 BUG("failed to perform bitmap walk");
1307 wants_bitmap
= find_objects(bitmap_git
, revs
, wants
, haves_bitmap
);
1310 BUG("failed to perform bitmap walk");
1313 bitmap_and_not(wants_bitmap
, haves_bitmap
);
1315 filter_bitmap(bitmap_git
,
1316 (revs
->filter
.choice
&& filter_provided_objects
) ? NULL
: wants
,
1320 bitmap_git
->result
= wants_bitmap
;
1321 bitmap_git
->haves
= haves_bitmap
;
1323 object_list_free(&wants
);
1324 object_list_free(&haves
);
1329 free_bitmap_index(bitmap_git
);
1330 object_list_free(&wants
);
1331 object_list_free(&haves
);
1336 * -1 means "stop trying further objects"; 0 means we may or may not have
1337 * reused, but you can keep feeding bits.
1339 static int try_partial_reuse(struct packed_git
*pack
,
1341 struct bitmap
*reuse
,
1342 struct pack_window
**w_curs
)
1344 off_t offset
, delta_obj_offset
;
1345 enum object_type type
;
1349 * try_partial_reuse() is called either on (a) objects in the
1350 * bitmapped pack (in the case of a single-pack bitmap) or (b)
1351 * objects in the preferred pack of a multi-pack bitmap.
1352 * Importantly, the latter can pretend as if only a single pack
1355 * - The first pack->num_objects bits of a MIDX bitmap are
1356 * reserved for the preferred pack, and
1358 * - Ties due to duplicate objects are always resolved in
1359 * favor of the preferred pack.
1361 * Therefore we do not need to ever ask the MIDX for its copy of
1362 * an object by OID, since it will always select it from the
1363 * preferred pack. Likewise, the selected copy of the base
1364 * object for any deltas will reside in the same pack.
1366 * This means that we can reuse pos when looking up the bit in
1367 * the reuse bitmap, too, since bits corresponding to the
1368 * preferred pack precede all bits from other packs.
1371 if (pos
>= pack
->num_objects
)
1372 return -1; /* not actually in the pack or MIDX preferred pack */
1374 offset
= delta_obj_offset
= pack_pos_to_offset(pack
, pos
);
1375 type
= unpack_object_header(pack
, w_curs
, &offset
, &size
);
1377 return -1; /* broken packfile, punt */
1379 if (type
== OBJ_REF_DELTA
|| type
== OBJ_OFS_DELTA
) {
1384 * Find the position of the base object so we can look it up
1385 * in our bitmaps. If we can't come up with an offset, or if
1386 * that offset is not in the revidx, the pack is corrupt.
1387 * There's nothing we can do, so just punt on this object,
1388 * and the normal slow path will complain about it in
1391 base_offset
= get_delta_base(pack
, w_curs
, &offset
, type
,
1395 if (offset_to_pack_pos(pack
, base_offset
, &base_pos
) < 0)
1399 * We assume delta dependencies always point backwards. This
1400 * lets us do a single pass, and is basically always true
1401 * due to the way OFS_DELTAs work. You would not typically
1402 * find REF_DELTA in a bitmapped pack, since we only bitmap
1403 * packs we write fresh, and OFS_DELTA is the default). But
1404 * let's double check to make sure the pack wasn't written with
1407 if (base_pos
>= pos
)
1411 * And finally, if we're not sending the base as part of our
1412 * reuse chunk, then don't send this object either. The base
1413 * would come after us, along with other objects not
1414 * necessarily in the pack, which means we'd need to convert
1415 * to REF_DELTA on the fly. Better to just let the normal
1416 * object_entry code path handle it.
1418 if (!bitmap_get(reuse
, base_pos
))
1423 * If we got here, then the object is OK to reuse. Mark it.
1425 bitmap_set(reuse
, pos
);
1429 uint32_t midx_preferred_pack(struct bitmap_index
*bitmap_git
)
1431 struct multi_pack_index
*m
= bitmap_git
->midx
;
1433 BUG("midx_preferred_pack: requires non-empty MIDX");
1434 return nth_midxed_pack_int_id(m
, pack_pos_to_midx(bitmap_git
->midx
, 0));
1437 int reuse_partial_packfile_from_bitmap(struct bitmap_index
*bitmap_git
,
1438 struct packed_git
**packfile_out
,
1440 struct bitmap
**reuse_out
)
1442 struct packed_git
*pack
;
1443 struct bitmap
*result
= bitmap_git
->result
;
1444 struct bitmap
*reuse
;
1445 struct pack_window
*w_curs
= NULL
;
1448 uint32_t objects_nr
;
1452 load_reverse_index(bitmap_git
);
1454 if (bitmap_is_midx(bitmap_git
))
1455 pack
= bitmap_git
->midx
->packs
[midx_preferred_pack(bitmap_git
)];
1457 pack
= bitmap_git
->pack
;
1458 objects_nr
= pack
->num_objects
;
1460 while (i
< result
->word_alloc
&& result
->words
[i
] == (eword_t
)~0)
1464 * Don't mark objects not in the packfile or preferred pack. This bitmap
1465 * marks objects eligible for reuse, but the pack-reuse code only
1466 * understands how to reuse a single pack. Since the preferred pack is
1467 * guaranteed to have all bases for its deltas (in a multi-pack bitmap),
1468 * we use it instead of another pack. In single-pack bitmaps, the choice
1471 if (i
> objects_nr
/ BITS_IN_EWORD
)
1472 i
= objects_nr
/ BITS_IN_EWORD
;
1474 reuse
= bitmap_word_alloc(i
);
1475 memset(reuse
->words
, 0xFF, i
* sizeof(eword_t
));
1477 for (; i
< result
->word_alloc
; ++i
) {
1478 eword_t word
= result
->words
[i
];
1479 size_t pos
= (i
* BITS_IN_EWORD
);
1481 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
1482 if ((word
>> offset
) == 0)
1485 offset
+= ewah_bit_ctz64(word
>> offset
);
1486 if (try_partial_reuse(pack
, pos
+ offset
,
1487 reuse
, &w_curs
) < 0) {
1489 * try_partial_reuse indicated we couldn't reuse
1490 * any bits, so there is no point in trying more
1491 * bits in the current word, or any other words
1494 * Jump out of both loops to avoid future
1495 * unnecessary calls to try_partial_reuse.
1503 unuse_pack(&w_curs
);
1505 *entries
= bitmap_popcount(reuse
);
1512 * Drop any reused objects from the result, since they will not
1513 * need to be handled separately.
1515 bitmap_and_not(result
, reuse
);
1516 *packfile_out
= pack
;
1521 int bitmap_walk_contains(struct bitmap_index
*bitmap_git
,
1522 struct bitmap
*bitmap
, const struct object_id
*oid
)
1529 idx
= bitmap_position(bitmap_git
, oid
);
1530 return idx
>= 0 && bitmap_get(bitmap
, idx
);
1533 void traverse_bitmap_commit_list(struct bitmap_index
*bitmap_git
,
1534 struct rev_info
*revs
,
1535 show_reachable_fn show_reachable
)
1537 assert(bitmap_git
->result
);
1539 show_objects_for_type(bitmap_git
, OBJ_COMMIT
, show_reachable
);
1540 if (revs
->tree_objects
)
1541 show_objects_for_type(bitmap_git
, OBJ_TREE
, show_reachable
);
1542 if (revs
->blob_objects
)
1543 show_objects_for_type(bitmap_git
, OBJ_BLOB
, show_reachable
);
1544 if (revs
->tag_objects
)
1545 show_objects_for_type(bitmap_git
, OBJ_TAG
, show_reachable
);
1547 show_extended_objects(bitmap_git
, revs
, show_reachable
);
1550 static uint32_t count_object_type(struct bitmap_index
*bitmap_git
,
1551 enum object_type type
)
1553 struct bitmap
*objects
= bitmap_git
->result
;
1554 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1556 uint32_t i
= 0, count
= 0;
1557 struct ewah_iterator it
;
1560 init_type_iterator(&it
, bitmap_git
, type
);
1562 while (i
< objects
->word_alloc
&& ewah_iterator_next(&filter
, &it
)) {
1563 eword_t word
= objects
->words
[i
++] & filter
;
1564 count
+= ewah_bit_popcount64(word
);
1567 for (i
= 0; i
< eindex
->count
; ++i
) {
1568 if (eindex
->objects
[i
]->type
== type
&&
1569 bitmap_get(objects
, bitmap_num_objects(bitmap_git
) + i
))
1576 void count_bitmap_commit_list(struct bitmap_index
*bitmap_git
,
1577 uint32_t *commits
, uint32_t *trees
,
1578 uint32_t *blobs
, uint32_t *tags
)
1580 assert(bitmap_git
->result
);
1583 *commits
= count_object_type(bitmap_git
, OBJ_COMMIT
);
1586 *trees
= count_object_type(bitmap_git
, OBJ_TREE
);
1589 *blobs
= count_object_type(bitmap_git
, OBJ_BLOB
);
1592 *tags
= count_object_type(bitmap_git
, OBJ_TAG
);
1595 struct bitmap_test_data
{
1596 struct bitmap_index
*bitmap_git
;
1597 struct bitmap
*base
;
1598 struct bitmap
*commits
;
1599 struct bitmap
*trees
;
1600 struct bitmap
*blobs
;
1601 struct bitmap
*tags
;
1602 struct progress
*prg
;
1606 static void test_bitmap_type(struct bitmap_test_data
*tdata
,
1607 struct object
*obj
, int pos
)
1609 enum object_type bitmap_type
= OBJ_NONE
;
1612 if (bitmap_get(tdata
->commits
, pos
)) {
1613 bitmap_type
= OBJ_COMMIT
;
1616 if (bitmap_get(tdata
->trees
, pos
)) {
1617 bitmap_type
= OBJ_TREE
;
1620 if (bitmap_get(tdata
->blobs
, pos
)) {
1621 bitmap_type
= OBJ_BLOB
;
1624 if (bitmap_get(tdata
->tags
, pos
)) {
1625 bitmap_type
= OBJ_TAG
;
1629 if (bitmap_type
== OBJ_NONE
)
1630 die(_("object '%s' not found in type bitmaps"),
1631 oid_to_hex(&obj
->oid
));
1634 die(_("object '%s' does not have a unique type"),
1635 oid_to_hex(&obj
->oid
));
1637 if (bitmap_type
!= obj
->type
)
1638 die(_("object '%s': real type '%s', expected: '%s'"),
1639 oid_to_hex(&obj
->oid
),
1640 type_name(obj
->type
),
1641 type_name(bitmap_type
));
1644 static void test_show_object(struct object
*object
, const char *name
,
1647 struct bitmap_test_data
*tdata
= data
;
1650 bitmap_pos
= bitmap_position(tdata
->bitmap_git
, &object
->oid
);
1652 die(_("object not in bitmap: '%s'"), oid_to_hex(&object
->oid
));
1653 test_bitmap_type(tdata
, object
, bitmap_pos
);
1655 bitmap_set(tdata
->base
, bitmap_pos
);
1656 display_progress(tdata
->prg
, ++tdata
->seen
);
1659 static void test_show_commit(struct commit
*commit
, void *data
)
1661 struct bitmap_test_data
*tdata
= data
;
1664 bitmap_pos
= bitmap_position(tdata
->bitmap_git
,
1665 &commit
->object
.oid
);
1667 die(_("object not in bitmap: '%s'"), oid_to_hex(&commit
->object
.oid
));
1668 test_bitmap_type(tdata
, &commit
->object
, bitmap_pos
);
1670 bitmap_set(tdata
->base
, bitmap_pos
);
1671 display_progress(tdata
->prg
, ++tdata
->seen
);
1674 void test_bitmap_walk(struct rev_info
*revs
)
1676 struct object
*root
;
1677 struct bitmap
*result
= NULL
;
1678 size_t result_popcnt
;
1679 struct bitmap_test_data tdata
;
1680 struct bitmap_index
*bitmap_git
;
1681 struct ewah_bitmap
*bm
;
1683 if (!(bitmap_git
= prepare_bitmap_git(revs
->repo
)))
1684 die(_("failed to load bitmap indexes"));
1686 if (revs
->pending
.nr
!= 1)
1687 die(_("you must specify exactly one commit to test"));
1689 fprintf_ln(stderr
, "Bitmap v%d test (%d entries loaded)",
1690 bitmap_git
->version
, bitmap_git
->entry_count
);
1692 root
= revs
->pending
.objects
[0].item
;
1693 bm
= bitmap_for_commit(bitmap_git
, (struct commit
*)root
);
1696 fprintf_ln(stderr
, "Found bitmap for '%s'. %d bits / %08x checksum",
1697 oid_to_hex(&root
->oid
), (int)bm
->bit_size
, ewah_checksum(bm
));
1699 result
= ewah_to_bitmap(bm
);
1703 die(_("commit '%s' doesn't have an indexed bitmap"), oid_to_hex(&root
->oid
));
1705 revs
->tag_objects
= 1;
1706 revs
->tree_objects
= 1;
1707 revs
->blob_objects
= 1;
1709 result_popcnt
= bitmap_popcount(result
);
1711 if (prepare_revision_walk(revs
))
1712 die(_("revision walk setup failed"));
1714 tdata
.bitmap_git
= bitmap_git
;
1715 tdata
.base
= bitmap_new();
1716 tdata
.commits
= ewah_to_bitmap(bitmap_git
->commits
);
1717 tdata
.trees
= ewah_to_bitmap(bitmap_git
->trees
);
1718 tdata
.blobs
= ewah_to_bitmap(bitmap_git
->blobs
);
1719 tdata
.tags
= ewah_to_bitmap(bitmap_git
->tags
);
1720 tdata
.prg
= start_progress("Verifying bitmap entries", result_popcnt
);
1723 traverse_commit_list(revs
, &test_show_commit
, &test_show_object
, &tdata
);
1725 stop_progress(&tdata
.prg
);
1727 if (bitmap_equals(result
, tdata
.base
))
1728 fprintf_ln(stderr
, "OK!");
1730 die(_("mismatch in bitmap results"));
1732 bitmap_free(result
);
1733 bitmap_free(tdata
.base
);
1734 bitmap_free(tdata
.commits
);
1735 bitmap_free(tdata
.trees
);
1736 bitmap_free(tdata
.blobs
);
1737 bitmap_free(tdata
.tags
);
1738 free_bitmap_index(bitmap_git
);
1741 int test_bitmap_commits(struct repository
*r
)
1743 struct bitmap_index
*bitmap_git
= prepare_bitmap_git(r
);
1744 struct object_id oid
;
1745 MAYBE_UNUSED
void *value
;
1748 die(_("failed to load bitmap indexes"));
1750 kh_foreach(bitmap_git
->bitmaps
, oid
, value
, {
1751 printf_ln("%s", oid_to_hex(&oid
));
1754 free_bitmap_index(bitmap_git
);
1759 int test_bitmap_hashes(struct repository
*r
)
1761 struct bitmap_index
*bitmap_git
= prepare_bitmap_git(r
);
1762 struct object_id oid
;
1763 uint32_t i
, index_pos
;
1765 if (!bitmap_git
|| !bitmap_git
->hashes
)
1768 for (i
= 0; i
< bitmap_num_objects(bitmap_git
); i
++) {
1769 if (bitmap_is_midx(bitmap_git
))
1770 index_pos
= pack_pos_to_midx(bitmap_git
->midx
, i
);
1772 index_pos
= pack_pos_to_index(bitmap_git
->pack
, i
);
1774 nth_bitmap_object_oid(bitmap_git
, &oid
, index_pos
);
1776 printf_ln("%s %"PRIu32
"",
1777 oid_to_hex(&oid
), get_be32(bitmap_git
->hashes
+ index_pos
));
1781 free_bitmap_index(bitmap_git
);
1786 int rebuild_bitmap(const uint32_t *reposition
,
1787 struct ewah_bitmap
*source
,
1788 struct bitmap
*dest
)
1791 struct ewah_iterator it
;
1794 ewah_iterator_init(&it
, source
);
1796 while (ewah_iterator_next(&word
, &it
)) {
1797 uint32_t offset
, bit_pos
;
1799 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
1800 if ((word
>> offset
) == 0)
1803 offset
+= ewah_bit_ctz64(word
>> offset
);
1805 bit_pos
= reposition
[pos
+ offset
];
1807 bitmap_set(dest
, bit_pos
- 1);
1808 else /* can't reuse, we don't have the object */
1812 pos
+= BITS_IN_EWORD
;
1817 uint32_t *create_bitmap_mapping(struct bitmap_index
*bitmap_git
,
1818 struct packing_data
*mapping
)
1820 uint32_t i
, num_objects
;
1821 uint32_t *reposition
;
1823 if (!bitmap_is_midx(bitmap_git
))
1824 load_reverse_index(bitmap_git
);
1825 else if (load_midx_revindex(bitmap_git
->midx
) < 0)
1826 BUG("rebuild_existing_bitmaps: missing required rev-cache "
1829 num_objects
= bitmap_num_objects(bitmap_git
);
1830 CALLOC_ARRAY(reposition
, num_objects
);
1832 for (i
= 0; i
< num_objects
; ++i
) {
1833 struct object_id oid
;
1834 struct object_entry
*oe
;
1837 if (bitmap_is_midx(bitmap_git
))
1838 index_pos
= pack_pos_to_midx(bitmap_git
->midx
, i
);
1840 index_pos
= pack_pos_to_index(bitmap_git
->pack
, i
);
1841 nth_bitmap_object_oid(bitmap_git
, &oid
, index_pos
);
1842 oe
= packlist_find(mapping
, &oid
);
1845 reposition
[i
] = oe_in_pack_pos(mapping
, oe
) + 1;
1846 if (bitmap_git
->hashes
&& !oe
->hash
)
1847 oe
->hash
= get_be32(bitmap_git
->hashes
+ index_pos
);
1854 void free_bitmap_index(struct bitmap_index
*b
)
1860 munmap(b
->map
, b
->map_size
);
1861 ewah_pool_free(b
->commits
);
1862 ewah_pool_free(b
->trees
);
1863 ewah_pool_free(b
->blobs
);
1864 ewah_pool_free(b
->tags
);
1866 struct stored_bitmap
*sb
;
1867 kh_foreach_value(b
->bitmaps
, sb
, {
1868 ewah_pool_free(sb
->root
);
1872 kh_destroy_oid_map(b
->bitmaps
);
1873 free(b
->ext_index
.objects
);
1874 free(b
->ext_index
.hashes
);
1875 kh_destroy_oid_pos(b
->ext_index
.positions
);
1876 bitmap_free(b
->result
);
1877 bitmap_free(b
->haves
);
1878 if (bitmap_is_midx(b
)) {
1880 * Multi-pack bitmaps need to have resources associated with
1881 * their on-disk reverse indexes unmapped so that stale .rev and
1882 * .bitmap files can be removed.
1884 * Unlike pack-based bitmaps, multi-pack bitmaps can be read and
1885 * written in the same 'git multi-pack-index write --bitmap'
1886 * process. Close resources so they can be removed safely on
1887 * platforms like Windows.
1889 close_midx_revindex(b
->midx
);
1894 int bitmap_has_oid_in_uninteresting(struct bitmap_index
*bitmap_git
,
1895 const struct object_id
*oid
)
1897 return bitmap_git
&&
1898 bitmap_walk_contains(bitmap_git
, bitmap_git
->haves
, oid
);
1901 static off_t
get_disk_usage_for_type(struct bitmap_index
*bitmap_git
,
1902 enum object_type object_type
)
1904 struct bitmap
*result
= bitmap_git
->result
;
1906 struct ewah_iterator it
;
1910 init_type_iterator(&it
, bitmap_git
, object_type
);
1911 for (i
= 0; i
< result
->word_alloc
&&
1912 ewah_iterator_next(&filter
, &it
); i
++) {
1913 eword_t word
= result
->words
[i
] & filter
;
1914 size_t base
= (i
* BITS_IN_EWORD
);
1920 for (offset
= 0; offset
< BITS_IN_EWORD
; offset
++) {
1921 if ((word
>> offset
) == 0)
1924 offset
+= ewah_bit_ctz64(word
>> offset
);
1926 if (bitmap_is_midx(bitmap_git
)) {
1928 uint32_t midx_pos
= pack_pos_to_midx(bitmap_git
->midx
, base
+ offset
);
1929 off_t offset
= nth_midxed_offset(bitmap_git
->midx
, midx_pos
);
1931 uint32_t pack_id
= nth_midxed_pack_int_id(bitmap_git
->midx
, midx_pos
);
1932 struct packed_git
*pack
= bitmap_git
->midx
->packs
[pack_id
];
1934 if (offset_to_pack_pos(pack
, offset
, &pack_pos
) < 0) {
1935 struct object_id oid
;
1936 nth_midxed_object_oid(&oid
, bitmap_git
->midx
, midx_pos
);
1938 die(_("could not find '%s' in pack '%s' at offset %"PRIuMAX
),
1944 total
+= pack_pos_to_offset(pack
, pack_pos
+ 1) - offset
;
1946 size_t pos
= base
+ offset
;
1947 total
+= pack_pos_to_offset(bitmap_git
->pack
, pos
+ 1) -
1948 pack_pos_to_offset(bitmap_git
->pack
, pos
);
1956 static off_t
get_disk_usage_for_extended(struct bitmap_index
*bitmap_git
)
1958 struct bitmap
*result
= bitmap_git
->result
;
1959 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1961 struct object_info oi
= OBJECT_INFO_INIT
;
1965 oi
.disk_sizep
= &object_size
;
1967 for (i
= 0; i
< eindex
->count
; i
++) {
1968 struct object
*obj
= eindex
->objects
[i
];
1970 if (!bitmap_get(result
, bitmap_num_objects(bitmap_git
) + i
))
1973 if (oid_object_info_extended(the_repository
, &obj
->oid
, &oi
, 0) < 0)
1974 die(_("unable to get disk usage of '%s'"),
1975 oid_to_hex(&obj
->oid
));
1977 total
+= object_size
;
1982 off_t
get_disk_usage_from_bitmap(struct bitmap_index
*bitmap_git
,
1983 struct rev_info
*revs
)
1987 total
+= get_disk_usage_for_type(bitmap_git
, OBJ_COMMIT
);
1988 if (revs
->tree_objects
)
1989 total
+= get_disk_usage_for_type(bitmap_git
, OBJ_TREE
);
1990 if (revs
->blob_objects
)
1991 total
+= get_disk_usage_for_type(bitmap_git
, OBJ_BLOB
);
1992 if (revs
->tag_objects
)
1993 total
+= get_disk_usage_for_type(bitmap_git
, OBJ_TAG
);
1995 total
+= get_disk_usage_for_extended(bitmap_git
);
2000 int bitmap_is_midx(struct bitmap_index
*bitmap_git
)
2002 return !!bitmap_git
->midx
;
2005 const struct string_list
*bitmap_preferred_tips(struct repository
*r
)
2007 return repo_config_get_value_multi(r
, "pack.preferbitmaptips");
2010 int bitmap_is_preferred_refname(struct repository
*r
, const char *refname
)
2012 const struct string_list
*preferred_tips
= bitmap_preferred_tips(r
);
2013 struct string_list_item
*item
;
2015 if (!preferred_tips
)
2018 for_each_string_list_item(item
, preferred_tips
) {
2019 if (starts_with(refname
, item
->string
))