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
;
87 * If not NULL, this point into the commit table extension
88 * (within the memory mapped region `map`).
90 unsigned char *table_lookup
;
95 * When trying to perform bitmap operations with objects that are not
96 * packed in `pack`, these objects are added to this "fake index" and
97 * are assumed to appear at the end of the packfile for all operations
100 struct object
**objects
;
102 uint32_t count
, alloc
;
103 kh_oid_pos_t
*positions
;
106 /* Bitmap result of the last performed walk */
107 struct bitmap
*result
;
109 /* "have" bitmap from the last performed walk */
110 struct bitmap
*haves
;
112 /* Version of the bitmap index */
113 unsigned int version
;
116 static struct ewah_bitmap
*lookup_stored_bitmap(struct stored_bitmap
*st
)
118 struct ewah_bitmap
*parent
;
119 struct ewah_bitmap
*composed
;
124 composed
= ewah_pool_new();
125 parent
= lookup_stored_bitmap(st
->xor);
126 ewah_xor(st
->root
, parent
, composed
);
128 ewah_pool_free(st
->root
);
136 * Read a bitmap from the current read position on the mmaped
137 * index, and increase the read position accordingly
139 static struct ewah_bitmap
*read_bitmap_1(struct bitmap_index
*index
)
141 struct ewah_bitmap
*b
= ewah_pool_new();
143 ssize_t bitmap_size
= ewah_read_mmap(b
,
144 index
->map
+ index
->map_pos
,
145 index
->map_size
- index
->map_pos
);
147 if (bitmap_size
< 0) {
148 error(_("failed to load bitmap index (corrupted?)"));
153 index
->map_pos
+= bitmap_size
;
157 static uint32_t bitmap_num_objects(struct bitmap_index
*index
)
160 return index
->midx
->num_objects
;
161 return index
->pack
->num_objects
;
164 static int load_bitmap_header(struct bitmap_index
*index
)
166 struct bitmap_disk_header
*header
= (void *)index
->map
;
167 size_t header_size
= sizeof(*header
) - GIT_MAX_RAWSZ
+ the_hash_algo
->rawsz
;
169 if (index
->map_size
< header_size
+ the_hash_algo
->rawsz
)
170 return error(_("corrupted bitmap index (too small)"));
172 if (memcmp(header
->magic
, BITMAP_IDX_SIGNATURE
, sizeof(BITMAP_IDX_SIGNATURE
)) != 0)
173 return error(_("corrupted bitmap index file (wrong header)"));
175 index
->version
= ntohs(header
->version
);
176 if (index
->version
!= 1)
177 return error(_("unsupported version '%d' for bitmap index file"), index
->version
);
179 /* Parse known bitmap format options */
181 uint32_t flags
= ntohs(header
->options
);
182 size_t cache_size
= st_mult(bitmap_num_objects(index
), sizeof(uint32_t));
183 unsigned char *index_end
= index
->map
+ index
->map_size
- the_hash_algo
->rawsz
;
185 if ((flags
& BITMAP_OPT_FULL_DAG
) == 0)
186 BUG("unsupported options for bitmap index file "
187 "(Git requires BITMAP_OPT_FULL_DAG)");
189 if (flags
& BITMAP_OPT_HASH_CACHE
) {
190 if (cache_size
> index_end
- index
->map
- header_size
)
191 return error(_("corrupted bitmap index file (too short to fit hash cache)"));
192 index
->hashes
= (void *)(index_end
- cache_size
);
193 index_end
-= cache_size
;
196 if (flags
& BITMAP_OPT_LOOKUP_TABLE
) {
197 size_t table_size
= st_mult(ntohl(header
->entry_count
),
198 BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH
);
199 if (table_size
> index_end
- index
->map
- header_size
)
200 return error(_("corrupted bitmap index file (too short to fit lookup table)"));
201 if (git_env_bool("GIT_TEST_READ_COMMIT_TABLE", 1))
202 index
->table_lookup
= (void *)(index_end
- table_size
);
203 index_end
-= table_size
;
207 index
->entry_count
= ntohl(header
->entry_count
);
208 index
->checksum
= header
->checksum
;
209 index
->map_pos
+= header_size
;
213 static struct stored_bitmap
*store_bitmap(struct bitmap_index
*index
,
214 struct ewah_bitmap
*root
,
215 const struct object_id
*oid
,
216 struct stored_bitmap
*xor_with
,
219 struct stored_bitmap
*stored
;
223 stored
= xmalloc(sizeof(struct stored_bitmap
));
225 stored
->xor = xor_with
;
226 stored
->flags
= flags
;
227 oidcpy(&stored
->oid
, oid
);
229 hash_pos
= kh_put_oid_map(index
->bitmaps
, stored
->oid
, &ret
);
232 * A 0 return code means the insertion succeeded with no changes,
233 * because the SHA1 already existed on the map. This is bad, there
234 * shouldn't be duplicated commits in the index.
237 error(_("duplicate entry in bitmap index: '%s'"), oid_to_hex(oid
));
241 kh_value(index
->bitmaps
, hash_pos
) = stored
;
245 static inline uint32_t read_be32(const unsigned char *buffer
, size_t *pos
)
247 uint32_t result
= get_be32(buffer
+ *pos
);
248 (*pos
) += sizeof(result
);
252 static inline uint8_t read_u8(const unsigned char *buffer
, size_t *pos
)
254 return buffer
[(*pos
)++];
257 #define MAX_XOR_OFFSET 160
259 static int nth_bitmap_object_oid(struct bitmap_index
*index
,
260 struct object_id
*oid
,
264 return nth_midxed_object_oid(oid
, index
->midx
, n
) ? 0 : -1;
265 return nth_packed_object_id(oid
, index
->pack
, n
);
268 static int load_bitmap_entries_v1(struct bitmap_index
*index
)
271 struct stored_bitmap
*recent_bitmaps
[MAX_XOR_OFFSET
] = { NULL
};
273 for (i
= 0; i
< index
->entry_count
; ++i
) {
274 int xor_offset
, flags
;
275 struct ewah_bitmap
*bitmap
= NULL
;
276 struct stored_bitmap
*xor_bitmap
= NULL
;
277 uint32_t commit_idx_pos
;
278 struct object_id oid
;
280 if (index
->map_size
- index
->map_pos
< 6)
281 return error(_("corrupt ewah bitmap: truncated header for entry %d"), i
);
283 commit_idx_pos
= read_be32(index
->map
, &index
->map_pos
);
284 xor_offset
= read_u8(index
->map
, &index
->map_pos
);
285 flags
= read_u8(index
->map
, &index
->map_pos
);
287 if (nth_bitmap_object_oid(index
, &oid
, commit_idx_pos
) < 0)
288 return error(_("corrupt ewah bitmap: commit index %u out of range"),
289 (unsigned)commit_idx_pos
);
291 bitmap
= read_bitmap_1(index
);
295 if (xor_offset
> MAX_XOR_OFFSET
|| xor_offset
> i
)
296 return error(_("corrupted bitmap pack index"));
298 if (xor_offset
> 0) {
299 xor_bitmap
= recent_bitmaps
[(i
- xor_offset
) % MAX_XOR_OFFSET
];
302 return error(_("invalid XOR offset in bitmap pack index"));
305 recent_bitmaps
[i
% MAX_XOR_OFFSET
] = store_bitmap(
306 index
, bitmap
, &oid
, xor_bitmap
, flags
);
312 char *midx_bitmap_filename(struct multi_pack_index
*midx
)
314 struct strbuf buf
= STRBUF_INIT
;
316 get_midx_filename(&buf
, midx
->object_dir
);
317 strbuf_addf(&buf
, "-%s.bitmap", hash_to_hex(get_midx_checksum(midx
)));
319 return strbuf_detach(&buf
, NULL
);
322 char *pack_bitmap_filename(struct packed_git
*p
)
326 if (!strip_suffix(p
->pack_name
, ".pack", &len
))
327 BUG("pack_name does not end in .pack");
328 return xstrfmt("%.*s.bitmap", (int)len
, p
->pack_name
);
331 static int open_midx_bitmap_1(struct bitmap_index
*bitmap_git
,
332 struct multi_pack_index
*midx
)
335 char *bitmap_name
= midx_bitmap_filename(midx
);
336 int fd
= git_open(bitmap_name
);
338 struct packed_git
*preferred
;
342 warning_errno("cannot open '%s'", bitmap_name
);
348 if (fstat(fd
, &st
)) {
349 error_errno(_("cannot fstat bitmap file"));
354 if (bitmap_git
->pack
|| bitmap_git
->midx
) {
355 struct strbuf buf
= STRBUF_INIT
;
356 get_midx_filename(&buf
, midx
->object_dir
);
357 trace2_data_string("bitmap", the_repository
,
358 "ignoring extra midx bitmap file", buf
.buf
);
360 strbuf_release(&buf
);
364 bitmap_git
->midx
= midx
;
365 bitmap_git
->map_size
= xsize_t(st
.st_size
);
366 bitmap_git
->map_pos
= 0;
367 bitmap_git
->map
= xmmap(NULL
, bitmap_git
->map_size
, PROT_READ
,
371 if (load_bitmap_header(bitmap_git
) < 0)
374 if (!hasheq(get_midx_checksum(bitmap_git
->midx
), bitmap_git
->checksum
)) {
375 error(_("checksum doesn't match in MIDX and bitmap"));
379 if (load_midx_revindex(bitmap_git
->midx
) < 0) {
380 warning(_("multi-pack bitmap is missing required reverse index"));
384 for (i
= 0; i
< bitmap_git
->midx
->num_packs
; i
++) {
385 if (prepare_midx_pack(the_repository
, bitmap_git
->midx
, i
))
386 die(_("could not open pack %s"),
387 bitmap_git
->midx
->pack_names
[i
]);
390 preferred
= bitmap_git
->midx
->packs
[midx_preferred_pack(bitmap_git
)];
391 if (!is_pack_valid(preferred
)) {
392 warning(_("preferred pack (%s) is invalid"),
393 preferred
->pack_name
);
400 munmap(bitmap_git
->map
, bitmap_git
->map_size
);
401 bitmap_git
->map_size
= 0;
402 bitmap_git
->map_pos
= 0;
403 bitmap_git
->map
= NULL
;
404 bitmap_git
->midx
= NULL
;
408 static int open_pack_bitmap_1(struct bitmap_index
*bitmap_git
, struct packed_git
*packfile
)
414 bitmap_name
= pack_bitmap_filename(packfile
);
415 fd
= git_open(bitmap_name
);
419 warning_errno("cannot open '%s'", bitmap_name
);
425 if (fstat(fd
, &st
)) {
426 error_errno(_("cannot fstat bitmap file"));
431 if (bitmap_git
->pack
|| bitmap_git
->midx
) {
432 trace2_data_string("bitmap", the_repository
,
433 "ignoring extra bitmap file", packfile
->pack_name
);
438 if (!is_pack_valid(packfile
)) {
443 bitmap_git
->pack
= packfile
;
444 bitmap_git
->map_size
= xsize_t(st
.st_size
);
445 bitmap_git
->map
= xmmap(NULL
, bitmap_git
->map_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
446 bitmap_git
->map_pos
= 0;
449 if (load_bitmap_header(bitmap_git
) < 0) {
450 munmap(bitmap_git
->map
, bitmap_git
->map_size
);
451 bitmap_git
->map
= NULL
;
452 bitmap_git
->map_size
= 0;
453 bitmap_git
->map_pos
= 0;
454 bitmap_git
->pack
= NULL
;
458 trace2_data_string("bitmap", the_repository
, "opened bitmap file",
459 packfile
->pack_name
);
463 static int load_reverse_index(struct bitmap_index
*bitmap_git
)
465 if (bitmap_is_midx(bitmap_git
)) {
470 * The multi-pack-index's .rev file is already loaded via
471 * open_pack_bitmap_1().
473 * But we still need to open the individual pack .rev files,
474 * since we will need to make use of them in pack-objects.
476 for (i
= 0; i
< bitmap_git
->midx
->num_packs
; i
++) {
477 ret
= load_pack_revindex(bitmap_git
->midx
->packs
[i
]);
483 return load_pack_revindex(bitmap_git
->pack
);
486 static int load_bitmap(struct bitmap_index
*bitmap_git
)
488 assert(bitmap_git
->map
);
490 bitmap_git
->bitmaps
= kh_init_oid_map();
491 bitmap_git
->ext_index
.positions
= kh_init_oid_pos();
493 if (load_reverse_index(bitmap_git
))
496 if (!(bitmap_git
->commits
= read_bitmap_1(bitmap_git
)) ||
497 !(bitmap_git
->trees
= read_bitmap_1(bitmap_git
)) ||
498 !(bitmap_git
->blobs
= read_bitmap_1(bitmap_git
)) ||
499 !(bitmap_git
->tags
= read_bitmap_1(bitmap_git
)))
502 if (!bitmap_git
->table_lookup
&& load_bitmap_entries_v1(bitmap_git
) < 0)
508 munmap(bitmap_git
->map
, bitmap_git
->map_size
);
509 bitmap_git
->map
= NULL
;
510 bitmap_git
->map_size
= 0;
512 kh_destroy_oid_map(bitmap_git
->bitmaps
);
513 bitmap_git
->bitmaps
= NULL
;
515 kh_destroy_oid_pos(bitmap_git
->ext_index
.positions
);
516 bitmap_git
->ext_index
.positions
= NULL
;
521 static int open_pack_bitmap(struct repository
*r
,
522 struct bitmap_index
*bitmap_git
)
524 struct packed_git
*p
;
527 for (p
= get_all_packs(r
); p
; p
= p
->next
) {
528 if (open_pack_bitmap_1(bitmap_git
, p
) == 0) {
531 * The only reason to keep looking is to report
534 if (!trace2_is_enabled())
542 static int open_midx_bitmap(struct repository
*r
,
543 struct bitmap_index
*bitmap_git
)
546 struct multi_pack_index
*midx
;
548 assert(!bitmap_git
->map
);
550 for (midx
= get_multi_pack_index(r
); midx
; midx
= midx
->next
) {
551 if (!open_midx_bitmap_1(bitmap_git
, midx
))
557 static int open_bitmap(struct repository
*r
,
558 struct bitmap_index
*bitmap_git
)
562 assert(!bitmap_git
->map
);
564 found
= !open_midx_bitmap(r
, bitmap_git
);
567 * these will all be skipped if we opened a midx bitmap; but run it
568 * anyway if tracing is enabled to report the duplicates
570 if (!found
|| trace2_is_enabled())
571 found
|= !open_pack_bitmap(r
, bitmap_git
);
573 return found
? 0 : -1;
576 struct bitmap_index
*prepare_bitmap_git(struct repository
*r
)
578 struct bitmap_index
*bitmap_git
= xcalloc(1, sizeof(*bitmap_git
));
580 if (!open_bitmap(r
, bitmap_git
) && !load_bitmap(bitmap_git
))
583 free_bitmap_index(bitmap_git
);
587 struct bitmap_index
*prepare_midx_bitmap_git(struct multi_pack_index
*midx
)
589 struct bitmap_index
*bitmap_git
= xcalloc(1, sizeof(*bitmap_git
));
591 if (!open_midx_bitmap_1(bitmap_git
, midx
) && !load_bitmap(bitmap_git
))
594 free_bitmap_index(bitmap_git
);
598 struct include_data
{
599 struct bitmap_index
*bitmap_git
;
604 struct bitmap_lookup_table_triplet
{
610 struct bitmap_lookup_table_xor_item
{
611 struct object_id oid
;
616 * Given a `triplet` struct pointer and pointer `p`, this
617 * function reads the triplet beginning at `p` into the struct.
618 * Note that this function assumes that there is enough memory
619 * left for filling the `triplet` struct from `p`.
621 static int bitmap_lookup_table_get_triplet_by_pointer(struct bitmap_lookup_table_triplet
*triplet
,
622 const unsigned char *p
)
627 triplet
->commit_pos
= get_be32(p
);
628 p
+= sizeof(uint32_t);
629 triplet
->offset
= get_be64(p
);
630 p
+= sizeof(uint64_t);
631 triplet
->xor_row
= get_be32(p
);
636 * This function gets the raw triplet from `row`'th row in the
637 * lookup table and fills that data to the `triplet`.
639 static int bitmap_lookup_table_get_triplet(struct bitmap_index
*bitmap_git
,
641 struct bitmap_lookup_table_triplet
*triplet
)
643 unsigned char *p
= NULL
;
644 if (pos
>= bitmap_git
->entry_count
)
645 return error(_("corrupt bitmap lookup table: triplet position out of index"));
647 p
= bitmap_git
->table_lookup
+ st_mult(pos
, BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH
);
649 return bitmap_lookup_table_get_triplet_by_pointer(triplet
, p
);
653 * Searches for a matching triplet. `commit_pos` is a pointer
654 * to the wanted commit position value. `table_entry` points to
655 * a triplet in lookup table. The first 4 bytes of each
656 * triplet (pointed by `table_entry`) are compared with `*commit_pos`.
658 static int triplet_cmp(const void *commit_pos
, const void *table_entry
)
661 uint32_t a
= *(uint32_t *)commit_pos
;
662 uint32_t b
= get_be32(table_entry
);
671 static uint32_t bitmap_bsearch_pos(struct bitmap_index
*bitmap_git
,
672 struct object_id
*oid
,
677 if (bitmap_is_midx(bitmap_git
))
678 found
= bsearch_midx(oid
, bitmap_git
->midx
, result
);
680 found
= bsearch_pack(oid
, bitmap_git
->pack
, result
);
686 * `bsearch_triplet_by_pos` function searches for the raw triplet
687 * having commit position same as `commit_pos` and fills `triplet`
688 * object from the raw triplet. Returns 1 on success and 0 on
691 static int bitmap_bsearch_triplet_by_pos(uint32_t commit_pos
,
692 struct bitmap_index
*bitmap_git
,
693 struct bitmap_lookup_table_triplet
*triplet
)
695 unsigned char *p
= bsearch(&commit_pos
, bitmap_git
->table_lookup
, bitmap_git
->entry_count
,
696 BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH
, triplet_cmp
);
701 return bitmap_lookup_table_get_triplet_by_pointer(triplet
, p
);
704 static struct stored_bitmap
*lazy_bitmap_for_commit(struct bitmap_index
*bitmap_git
,
705 struct commit
*commit
)
707 uint32_t commit_pos
, xor_row
;
710 struct bitmap_lookup_table_triplet triplet
;
711 struct object_id
*oid
= &commit
->object
.oid
;
712 struct ewah_bitmap
*bitmap
;
713 struct stored_bitmap
*xor_bitmap
= NULL
;
714 const int bitmap_header_size
= 6;
715 static struct bitmap_lookup_table_xor_item
*xor_items
= NULL
;
716 static size_t xor_items_nr
= 0, xor_items_alloc
= 0;
717 static int is_corrupt
= 0;
720 struct bitmap_lookup_table_xor_item
*xor_item
;
725 if (!bitmap_bsearch_pos(bitmap_git
, oid
, &commit_pos
))
728 if (bitmap_bsearch_triplet_by_pos(commit_pos
, bitmap_git
, &triplet
) < 0)
732 offset
= triplet
.offset
;
733 xor_row
= triplet
.xor_row
;
735 while (xor_row
!= 0xffffffff) {
736 ALLOC_GROW(xor_items
, xor_items_nr
+ 1, xor_items_alloc
);
738 if (xor_items_nr
+ 1 >= bitmap_git
->entry_count
) {
739 error(_("corrupt bitmap lookup table: xor chain exceeds entry count"));
743 if (bitmap_lookup_table_get_triplet(bitmap_git
, xor_row
, &triplet
) < 0)
746 xor_item
= &xor_items
[xor_items_nr
];
747 xor_item
->offset
= triplet
.offset
;
749 if (nth_bitmap_object_oid(bitmap_git
, &xor_item
->oid
, triplet
.commit_pos
) < 0) {
750 error(_("corrupt bitmap lookup table: commit index %u out of range"),
755 hash_pos
= kh_get_oid_map(bitmap_git
->bitmaps
, xor_item
->oid
);
758 * If desired bitmap is already stored, we don't need
759 * to iterate further. Because we know that bitmaps
760 * that are needed to be parsed to parse this bitmap
761 * has already been stored. So, assign this stored bitmap
764 if (hash_pos
< kh_end(bitmap_git
->bitmaps
) &&
765 (xor_bitmap
= kh_value(bitmap_git
->bitmaps
, hash_pos
)))
768 xor_row
= triplet
.xor_row
;
771 while (xor_items_nr
) {
772 xor_item
= &xor_items
[xor_items_nr
- 1];
773 bitmap_git
->map_pos
= xor_item
->offset
;
774 if (bitmap_git
->map_size
- bitmap_git
->map_pos
< bitmap_header_size
) {
775 error(_("corrupt ewah bitmap: truncated header for bitmap of commit \"%s\""),
776 oid_to_hex(&xor_item
->oid
));
780 bitmap_git
->map_pos
+= sizeof(uint32_t) + sizeof(uint8_t);
781 xor_flags
= read_u8(bitmap_git
->map
, &bitmap_git
->map_pos
);
782 bitmap
= read_bitmap_1(bitmap_git
);
787 xor_bitmap
= store_bitmap(bitmap_git
, bitmap
, &xor_item
->oid
, xor_bitmap
, xor_flags
);
791 bitmap_git
->map_pos
= offset
;
792 if (bitmap_git
->map_size
- bitmap_git
->map_pos
< bitmap_header_size
) {
793 error(_("corrupt ewah bitmap: truncated header for bitmap of commit \"%s\""),
799 * Don't bother reading the commit's index position or its xor
802 * - The commit's index position is irrelevant to us, since
803 * load_bitmap_entries_v1 only uses it to learn the object
804 * id which is used to compute the hashmap's key. We already
805 * have an object id, so no need to look it up again.
807 * - The xor_offset is unusable for us, since it specifies how
808 * many entries previous to ours we should look at. This
809 * makes sense when reading the bitmaps sequentially (as in
810 * load_bitmap_entries_v1()), since we can keep track of
811 * each bitmap as we read them.
813 * But it can't work for us, since the bitmap's don't have a
814 * fixed size. So we learn the position of the xor'd bitmap
815 * from the commit table (and resolve it to a bitmap in the
816 * above if-statement).
818 * Instead, we can skip ahead and immediately read the flags and
821 bitmap_git
->map_pos
+= sizeof(uint32_t) + sizeof(uint8_t);
822 flags
= read_u8(bitmap_git
->map
, &bitmap_git
->map_pos
);
823 bitmap
= read_bitmap_1(bitmap_git
);
828 return store_bitmap(bitmap_git
, bitmap
, oid
, xor_bitmap
, flags
);
836 struct ewah_bitmap
*bitmap_for_commit(struct bitmap_index
*bitmap_git
,
837 struct commit
*commit
)
839 khiter_t hash_pos
= kh_get_oid_map(bitmap_git
->bitmaps
,
841 if (hash_pos
>= kh_end(bitmap_git
->bitmaps
)) {
842 struct stored_bitmap
*bitmap
= NULL
;
843 if (!bitmap_git
->table_lookup
)
846 /* this is a fairly hot codepath - no trace2_region please */
847 /* NEEDSWORK: cache misses aren't recorded */
848 bitmap
= lazy_bitmap_for_commit(bitmap_git
, commit
);
851 return lookup_stored_bitmap(bitmap
);
853 return lookup_stored_bitmap(kh_value(bitmap_git
->bitmaps
, hash_pos
));
856 static inline int bitmap_position_extended(struct bitmap_index
*bitmap_git
,
857 const struct object_id
*oid
)
859 kh_oid_pos_t
*positions
= bitmap_git
->ext_index
.positions
;
860 khiter_t pos
= kh_get_oid_pos(positions
, *oid
);
862 if (pos
< kh_end(positions
)) {
863 int bitmap_pos
= kh_value(positions
, pos
);
864 return bitmap_pos
+ bitmap_num_objects(bitmap_git
);
870 static inline int bitmap_position_packfile(struct bitmap_index
*bitmap_git
,
871 const struct object_id
*oid
)
874 off_t offset
= find_pack_entry_one(oid
->hash
, bitmap_git
->pack
);
878 if (offset_to_pack_pos(bitmap_git
->pack
, offset
, &pos
) < 0)
883 static int bitmap_position_midx(struct bitmap_index
*bitmap_git
,
884 const struct object_id
*oid
)
887 if (!bsearch_midx(oid
, bitmap_git
->midx
, &want
))
890 if (midx_to_pack_pos(bitmap_git
->midx
, want
, &got
) < 0)
895 static int bitmap_position(struct bitmap_index
*bitmap_git
,
896 const struct object_id
*oid
)
899 if (bitmap_is_midx(bitmap_git
))
900 pos
= bitmap_position_midx(bitmap_git
, oid
);
902 pos
= bitmap_position_packfile(bitmap_git
, oid
);
903 return (pos
>= 0) ? pos
: bitmap_position_extended(bitmap_git
, oid
);
906 static int ext_index_add_object(struct bitmap_index
*bitmap_git
,
907 struct object
*object
, const char *name
)
909 struct eindex
*eindex
= &bitmap_git
->ext_index
;
915 hash_pos
= kh_put_oid_pos(eindex
->positions
, object
->oid
, &hash_ret
);
917 if (eindex
->count
>= eindex
->alloc
) {
918 eindex
->alloc
= (eindex
->alloc
+ 16) * 3 / 2;
919 REALLOC_ARRAY(eindex
->objects
, eindex
->alloc
);
920 REALLOC_ARRAY(eindex
->hashes
, eindex
->alloc
);
923 bitmap_pos
= eindex
->count
;
924 eindex
->objects
[eindex
->count
] = object
;
925 eindex
->hashes
[eindex
->count
] = pack_name_hash(name
);
926 kh_value(eindex
->positions
, hash_pos
) = bitmap_pos
;
929 bitmap_pos
= kh_value(eindex
->positions
, hash_pos
);
932 return bitmap_pos
+ bitmap_num_objects(bitmap_git
);
935 struct bitmap_show_data
{
936 struct bitmap_index
*bitmap_git
;
940 static void show_object(struct object
*object
, const char *name
, void *data_
)
942 struct bitmap_show_data
*data
= data_
;
945 bitmap_pos
= bitmap_position(data
->bitmap_git
, &object
->oid
);
948 bitmap_pos
= ext_index_add_object(data
->bitmap_git
, object
,
951 bitmap_set(data
->base
, bitmap_pos
);
954 static void show_commit(struct commit
*commit UNUSED
,
959 static int add_to_include_set(struct bitmap_index
*bitmap_git
,
960 struct include_data
*data
,
961 struct commit
*commit
,
964 struct ewah_bitmap
*partial
;
966 if (data
->seen
&& bitmap_get(data
->seen
, bitmap_pos
))
969 if (bitmap_get(data
->base
, bitmap_pos
))
972 partial
= bitmap_for_commit(bitmap_git
, commit
);
974 bitmap_or_ewah(data
->base
, partial
);
978 bitmap_set(data
->base
, bitmap_pos
);
982 static int should_include(struct commit
*commit
, void *_data
)
984 struct include_data
*data
= _data
;
987 bitmap_pos
= bitmap_position(data
->bitmap_git
, &commit
->object
.oid
);
989 bitmap_pos
= ext_index_add_object(data
->bitmap_git
,
990 (struct object
*)commit
,
993 if (!add_to_include_set(data
->bitmap_git
, data
, commit
, bitmap_pos
)) {
994 struct commit_list
*parent
= commit
->parents
;
997 parent
->item
->object
.flags
|= SEEN
;
998 parent
= parent
->next
;
1007 static int should_include_obj(struct object
*obj
, void *_data
)
1009 struct include_data
*data
= _data
;
1012 bitmap_pos
= bitmap_position(data
->bitmap_git
, &obj
->oid
);
1015 if ((data
->seen
&& bitmap_get(data
->seen
, bitmap_pos
)) ||
1016 bitmap_get(data
->base
, bitmap_pos
)) {
1023 static int add_commit_to_bitmap(struct bitmap_index
*bitmap_git
,
1024 struct bitmap
**base
,
1025 struct commit
*commit
)
1027 struct ewah_bitmap
*or_with
= bitmap_for_commit(bitmap_git
, commit
);
1033 *base
= ewah_to_bitmap(or_with
);
1035 bitmap_or_ewah(*base
, or_with
);
1040 static struct bitmap
*find_objects(struct bitmap_index
*bitmap_git
,
1041 struct rev_info
*revs
,
1042 struct object_list
*roots
,
1043 struct bitmap
*seen
)
1045 struct bitmap
*base
= NULL
;
1048 struct object_list
*not_mapped
= NULL
;
1051 * Go through all the roots for the walk. The ones that have bitmaps
1052 * on the bitmap index will be `or`ed together to form an initial
1053 * global reachability analysis.
1055 * The ones without bitmaps in the index will be stored in the
1056 * `not_mapped_list` for further processing.
1059 struct object
*object
= roots
->item
;
1060 roots
= roots
->next
;
1062 if (object
->type
== OBJ_COMMIT
&&
1063 add_commit_to_bitmap(bitmap_git
, &base
, (struct commit
*)object
)) {
1064 object
->flags
|= SEEN
;
1068 object_list_insert(object
, ¬_mapped
);
1072 * Best case scenario: We found bitmaps for all the roots,
1073 * so the resulting `or` bitmap has the full reachability analysis
1081 * Let's iterate through all the roots that don't have bitmaps to
1082 * check if we can determine them to be reachable from the existing
1085 * If we cannot find them in the existing global bitmap, we'll need
1086 * to push them to an actual walk and run it until we can confirm
1087 * they are reachable
1090 struct object
*object
= roots
->item
;
1093 roots
= roots
->next
;
1094 pos
= bitmap_position(bitmap_git
, &object
->oid
);
1096 if (pos
< 0 || base
== NULL
|| !bitmap_get(base
, pos
)) {
1097 object
->flags
&= ~UNINTERESTING
;
1098 add_pending_object(revs
, object
, "");
1101 object
->flags
|= SEEN
;
1106 struct include_data incdata
;
1107 struct bitmap_show_data show_data
;
1110 base
= bitmap_new();
1112 incdata
.bitmap_git
= bitmap_git
;
1113 incdata
.base
= base
;
1114 incdata
.seen
= seen
;
1116 revs
->include_check
= should_include
;
1117 revs
->include_check_obj
= should_include_obj
;
1118 revs
->include_check_data
= &incdata
;
1120 if (prepare_revision_walk(revs
))
1121 die(_("revision walk setup failed"));
1123 show_data
.bitmap_git
= bitmap_git
;
1124 show_data
.base
= base
;
1126 traverse_commit_list(revs
,
1127 show_commit
, show_object
,
1130 revs
->include_check
= NULL
;
1131 revs
->include_check_obj
= NULL
;
1132 revs
->include_check_data
= NULL
;
1138 static void show_extended_objects(struct bitmap_index
*bitmap_git
,
1139 struct rev_info
*revs
,
1140 show_reachable_fn show_reach
)
1142 struct bitmap
*objects
= bitmap_git
->result
;
1143 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1146 for (i
= 0; i
< eindex
->count
; ++i
) {
1149 if (!bitmap_get(objects
, bitmap_num_objects(bitmap_git
) + i
))
1152 obj
= eindex
->objects
[i
];
1153 if ((obj
->type
== OBJ_BLOB
&& !revs
->blob_objects
) ||
1154 (obj
->type
== OBJ_TREE
&& !revs
->tree_objects
) ||
1155 (obj
->type
== OBJ_TAG
&& !revs
->tag_objects
))
1158 show_reach(&obj
->oid
, obj
->type
, 0, eindex
->hashes
[i
], NULL
, 0);
1162 static void init_type_iterator(struct ewah_iterator
*it
,
1163 struct bitmap_index
*bitmap_git
,
1164 enum object_type type
)
1168 ewah_iterator_init(it
, bitmap_git
->commits
);
1172 ewah_iterator_init(it
, bitmap_git
->trees
);
1176 ewah_iterator_init(it
, bitmap_git
->blobs
);
1180 ewah_iterator_init(it
, bitmap_git
->tags
);
1184 BUG("object type %d not stored by bitmap type index", type
);
1189 static void show_objects_for_type(
1190 struct bitmap_index
*bitmap_git
,
1191 enum object_type object_type
,
1192 show_reachable_fn show_reach
)
1197 struct ewah_iterator it
;
1200 struct bitmap
*objects
= bitmap_git
->result
;
1202 init_type_iterator(&it
, bitmap_git
, object_type
);
1204 for (i
= 0; i
< objects
->word_alloc
&&
1205 ewah_iterator_next(&filter
, &it
); i
++) {
1206 eword_t word
= objects
->words
[i
] & filter
;
1207 size_t pos
= (i
* BITS_IN_EWORD
);
1212 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
1213 struct packed_git
*pack
;
1214 struct object_id oid
;
1215 uint32_t hash
= 0, index_pos
;
1218 if ((word
>> offset
) == 0)
1221 offset
+= ewah_bit_ctz64(word
>> offset
);
1223 if (bitmap_is_midx(bitmap_git
)) {
1224 struct multi_pack_index
*m
= bitmap_git
->midx
;
1227 index_pos
= pack_pos_to_midx(m
, pos
+ offset
);
1228 ofs
= nth_midxed_offset(m
, index_pos
);
1229 nth_midxed_object_oid(&oid
, m
, index_pos
);
1231 pack_id
= nth_midxed_pack_int_id(m
, index_pos
);
1232 pack
= bitmap_git
->midx
->packs
[pack_id
];
1234 index_pos
= pack_pos_to_index(bitmap_git
->pack
, pos
+ offset
);
1235 ofs
= pack_pos_to_offset(bitmap_git
->pack
, pos
+ offset
);
1236 nth_bitmap_object_oid(bitmap_git
, &oid
, index_pos
);
1238 pack
= bitmap_git
->pack
;
1241 if (bitmap_git
->hashes
)
1242 hash
= get_be32(bitmap_git
->hashes
+ index_pos
);
1244 show_reach(&oid
, object_type
, 0, hash
, pack
, ofs
);
1249 static int in_bitmapped_pack(struct bitmap_index
*bitmap_git
,
1250 struct object_list
*roots
)
1253 struct object
*object
= roots
->item
;
1254 roots
= roots
->next
;
1256 if (bitmap_is_midx(bitmap_git
)) {
1257 if (bsearch_midx(&object
->oid
, bitmap_git
->midx
, NULL
))
1260 if (find_pack_entry_one(object
->oid
.hash
, bitmap_git
->pack
) > 0)
1268 static struct bitmap
*find_tip_objects(struct bitmap_index
*bitmap_git
,
1269 struct object_list
*tip_objects
,
1270 enum object_type type
)
1272 struct bitmap
*result
= bitmap_new();
1273 struct object_list
*p
;
1275 for (p
= tip_objects
; p
; p
= p
->next
) {
1278 if (p
->item
->type
!= type
)
1281 pos
= bitmap_position(bitmap_git
, &p
->item
->oid
);
1285 bitmap_set(result
, pos
);
1291 static void filter_bitmap_exclude_type(struct bitmap_index
*bitmap_git
,
1292 struct object_list
*tip_objects
,
1293 struct bitmap
*to_filter
,
1294 enum object_type type
)
1296 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1297 struct bitmap
*tips
;
1298 struct ewah_iterator it
;
1303 * The non-bitmap version of this filter never removes
1304 * objects which the other side specifically asked for,
1305 * so we must match that behavior.
1307 tips
= find_tip_objects(bitmap_git
, tip_objects
, type
);
1310 * We can use the type-level bitmap for 'type' to work in whole
1311 * words for the objects that are actually in the bitmapped
1314 for (i
= 0, init_type_iterator(&it
, bitmap_git
, type
);
1315 i
< to_filter
->word_alloc
&& ewah_iterator_next(&mask
, &it
);
1317 if (i
< tips
->word_alloc
)
1318 mask
&= ~tips
->words
[i
];
1319 to_filter
->words
[i
] &= ~mask
;
1323 * Clear any objects that weren't in the packfile (and so would
1324 * not have been caught by the loop above. We'll have to check
1325 * them individually.
1327 for (i
= 0; i
< eindex
->count
; i
++) {
1328 uint32_t pos
= i
+ bitmap_num_objects(bitmap_git
);
1329 if (eindex
->objects
[i
]->type
== type
&&
1330 bitmap_get(to_filter
, pos
) &&
1331 !bitmap_get(tips
, pos
))
1332 bitmap_unset(to_filter
, pos
);
1338 static void filter_bitmap_blob_none(struct bitmap_index
*bitmap_git
,
1339 struct object_list
*tip_objects
,
1340 struct bitmap
*to_filter
)
1342 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
,
1346 static unsigned long get_size_by_pos(struct bitmap_index
*bitmap_git
,
1350 struct object_info oi
= OBJECT_INFO_INIT
;
1354 if (pos
< bitmap_num_objects(bitmap_git
)) {
1355 struct packed_git
*pack
;
1358 if (bitmap_is_midx(bitmap_git
)) {
1359 uint32_t midx_pos
= pack_pos_to_midx(bitmap_git
->midx
, pos
);
1360 uint32_t pack_id
= nth_midxed_pack_int_id(bitmap_git
->midx
, midx_pos
);
1362 pack
= bitmap_git
->midx
->packs
[pack_id
];
1363 ofs
= nth_midxed_offset(bitmap_git
->midx
, midx_pos
);
1365 pack
= bitmap_git
->pack
;
1366 ofs
= pack_pos_to_offset(pack
, pos
);
1369 if (packed_object_info(the_repository
, pack
, ofs
, &oi
) < 0) {
1370 struct object_id oid
;
1371 nth_bitmap_object_oid(bitmap_git
, &oid
,
1372 pack_pos_to_index(pack
, pos
));
1373 die(_("unable to get size of %s"), oid_to_hex(&oid
));
1376 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1377 struct object
*obj
= eindex
->objects
[pos
- bitmap_num_objects(bitmap_git
)];
1378 if (oid_object_info_extended(the_repository
, &obj
->oid
, &oi
, 0) < 0)
1379 die(_("unable to get size of %s"), oid_to_hex(&obj
->oid
));
1385 static void filter_bitmap_blob_limit(struct bitmap_index
*bitmap_git
,
1386 struct object_list
*tip_objects
,
1387 struct bitmap
*to_filter
,
1388 unsigned long limit
)
1390 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1391 struct bitmap
*tips
;
1392 struct ewah_iterator it
;
1396 tips
= find_tip_objects(bitmap_git
, tip_objects
, OBJ_BLOB
);
1398 for (i
= 0, init_type_iterator(&it
, bitmap_git
, OBJ_BLOB
);
1399 i
< to_filter
->word_alloc
&& ewah_iterator_next(&mask
, &it
);
1401 eword_t word
= to_filter
->words
[i
] & mask
;
1404 for (offset
= 0; offset
< BITS_IN_EWORD
; offset
++) {
1407 if ((word
>> offset
) == 0)
1409 offset
+= ewah_bit_ctz64(word
>> offset
);
1410 pos
= i
* BITS_IN_EWORD
+ offset
;
1412 if (!bitmap_get(tips
, pos
) &&
1413 get_size_by_pos(bitmap_git
, pos
) >= limit
)
1414 bitmap_unset(to_filter
, pos
);
1418 for (i
= 0; i
< eindex
->count
; i
++) {
1419 uint32_t pos
= i
+ bitmap_num_objects(bitmap_git
);
1420 if (eindex
->objects
[i
]->type
== OBJ_BLOB
&&
1421 bitmap_get(to_filter
, pos
) &&
1422 !bitmap_get(tips
, pos
) &&
1423 get_size_by_pos(bitmap_git
, pos
) >= limit
)
1424 bitmap_unset(to_filter
, pos
);
1430 static void filter_bitmap_tree_depth(struct bitmap_index
*bitmap_git
,
1431 struct object_list
*tip_objects
,
1432 struct bitmap
*to_filter
,
1433 unsigned long limit
)
1436 BUG("filter_bitmap_tree_depth given non-zero limit");
1438 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
,
1440 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
,
1444 static void filter_bitmap_object_type(struct bitmap_index
*bitmap_git
,
1445 struct object_list
*tip_objects
,
1446 struct bitmap
*to_filter
,
1447 enum object_type object_type
)
1449 if (object_type
< OBJ_COMMIT
|| object_type
> OBJ_TAG
)
1450 BUG("filter_bitmap_object_type given invalid object");
1452 if (object_type
!= OBJ_TAG
)
1453 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_TAG
);
1454 if (object_type
!= OBJ_COMMIT
)
1455 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_COMMIT
);
1456 if (object_type
!= OBJ_TREE
)
1457 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_TREE
);
1458 if (object_type
!= OBJ_BLOB
)
1459 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_BLOB
);
1462 static int filter_bitmap(struct bitmap_index
*bitmap_git
,
1463 struct object_list
*tip_objects
,
1464 struct bitmap
*to_filter
,
1465 struct list_objects_filter_options
*filter
)
1467 if (!filter
|| filter
->choice
== LOFC_DISABLED
)
1470 if (filter
->choice
== LOFC_BLOB_NONE
) {
1472 filter_bitmap_blob_none(bitmap_git
, tip_objects
,
1477 if (filter
->choice
== LOFC_BLOB_LIMIT
) {
1479 filter_bitmap_blob_limit(bitmap_git
, tip_objects
,
1481 filter
->blob_limit_value
);
1485 if (filter
->choice
== LOFC_TREE_DEPTH
&&
1486 filter
->tree_exclude_depth
== 0) {
1488 filter_bitmap_tree_depth(bitmap_git
, tip_objects
,
1490 filter
->tree_exclude_depth
);
1494 if (filter
->choice
== LOFC_OBJECT_TYPE
) {
1496 filter_bitmap_object_type(bitmap_git
, tip_objects
,
1498 filter
->object_type
);
1502 if (filter
->choice
== LOFC_COMBINE
) {
1504 for (i
= 0; i
< filter
->sub_nr
; i
++) {
1505 if (filter_bitmap(bitmap_git
, tip_objects
, to_filter
,
1506 &filter
->sub
[i
]) < 0)
1512 /* filter choice not handled */
1516 static int can_filter_bitmap(struct list_objects_filter_options
*filter
)
1518 return !filter_bitmap(NULL
, NULL
, NULL
, filter
);
1521 struct bitmap_index
*prepare_bitmap_walk(struct rev_info
*revs
,
1522 int filter_provided_objects
)
1526 struct object_list
*wants
= NULL
;
1527 struct object_list
*haves
= NULL
;
1529 struct bitmap
*wants_bitmap
= NULL
;
1530 struct bitmap
*haves_bitmap
= NULL
;
1532 struct bitmap_index
*bitmap_git
;
1535 * We can't do pathspec limiting with bitmaps, because we don't know
1536 * which commits are associated with which object changes (let alone
1537 * even which objects are associated with which paths).
1542 if (!can_filter_bitmap(&revs
->filter
))
1545 /* try to open a bitmapped pack, but don't parse it yet
1546 * because we may not need to use it */
1547 CALLOC_ARRAY(bitmap_git
, 1);
1548 if (open_bitmap(revs
->repo
, bitmap_git
) < 0)
1551 for (i
= 0; i
< revs
->pending
.nr
; ++i
) {
1552 struct object
*object
= revs
->pending
.objects
[i
].item
;
1554 if (object
->type
== OBJ_NONE
)
1555 parse_object_or_die(&object
->oid
, NULL
);
1557 while (object
->type
== OBJ_TAG
) {
1558 struct tag
*tag
= (struct tag
*) object
;
1560 if (object
->flags
& UNINTERESTING
)
1561 object_list_insert(object
, &haves
);
1563 object_list_insert(object
, &wants
);
1565 object
= parse_object_or_die(get_tagged_oid(tag
), NULL
);
1566 object
->flags
|= (tag
->object
.flags
& UNINTERESTING
);
1569 if (object
->flags
& UNINTERESTING
)
1570 object_list_insert(object
, &haves
);
1572 object_list_insert(object
, &wants
);
1576 * if we have a HAVES list, but none of those haves is contained
1577 * in the packfile that has a bitmap, we don't have anything to
1580 if (haves
&& !in_bitmapped_pack(bitmap_git
, haves
))
1583 /* if we don't want anything, we're done here */
1588 * now we're going to use bitmaps, so load the actual bitmap entries
1589 * from disk. this is the point of no return; after this the rev_list
1590 * becomes invalidated and we must perform the revwalk through bitmaps
1592 if (load_bitmap(bitmap_git
) < 0)
1595 object_array_clear(&revs
->pending
);
1598 revs
->ignore_missing_links
= 1;
1599 haves_bitmap
= find_objects(bitmap_git
, revs
, haves
, NULL
);
1600 reset_revision_walk();
1601 revs
->ignore_missing_links
= 0;
1604 BUG("failed to perform bitmap walk");
1607 wants_bitmap
= find_objects(bitmap_git
, revs
, wants
, haves_bitmap
);
1610 BUG("failed to perform bitmap walk");
1613 bitmap_and_not(wants_bitmap
, haves_bitmap
);
1615 filter_bitmap(bitmap_git
,
1616 (revs
->filter
.choice
&& filter_provided_objects
) ? NULL
: wants
,
1620 bitmap_git
->result
= wants_bitmap
;
1621 bitmap_git
->haves
= haves_bitmap
;
1623 object_list_free(&wants
);
1624 object_list_free(&haves
);
1629 free_bitmap_index(bitmap_git
);
1630 object_list_free(&wants
);
1631 object_list_free(&haves
);
1636 * -1 means "stop trying further objects"; 0 means we may or may not have
1637 * reused, but you can keep feeding bits.
1639 static int try_partial_reuse(struct packed_git
*pack
,
1641 struct bitmap
*reuse
,
1642 struct pack_window
**w_curs
)
1644 off_t offset
, delta_obj_offset
;
1645 enum object_type type
;
1649 * try_partial_reuse() is called either on (a) objects in the
1650 * bitmapped pack (in the case of a single-pack bitmap) or (b)
1651 * objects in the preferred pack of a multi-pack bitmap.
1652 * Importantly, the latter can pretend as if only a single pack
1655 * - The first pack->num_objects bits of a MIDX bitmap are
1656 * reserved for the preferred pack, and
1658 * - Ties due to duplicate objects are always resolved in
1659 * favor of the preferred pack.
1661 * Therefore we do not need to ever ask the MIDX for its copy of
1662 * an object by OID, since it will always select it from the
1663 * preferred pack. Likewise, the selected copy of the base
1664 * object for any deltas will reside in the same pack.
1666 * This means that we can reuse pos when looking up the bit in
1667 * the reuse bitmap, too, since bits corresponding to the
1668 * preferred pack precede all bits from other packs.
1671 if (pos
>= pack
->num_objects
)
1672 return -1; /* not actually in the pack or MIDX preferred pack */
1674 offset
= delta_obj_offset
= pack_pos_to_offset(pack
, pos
);
1675 type
= unpack_object_header(pack
, w_curs
, &offset
, &size
);
1677 return -1; /* broken packfile, punt */
1679 if (type
== OBJ_REF_DELTA
|| type
== OBJ_OFS_DELTA
) {
1684 * Find the position of the base object so we can look it up
1685 * in our bitmaps. If we can't come up with an offset, or if
1686 * that offset is not in the revidx, the pack is corrupt.
1687 * There's nothing we can do, so just punt on this object,
1688 * and the normal slow path will complain about it in
1691 base_offset
= get_delta_base(pack
, w_curs
, &offset
, type
,
1695 if (offset_to_pack_pos(pack
, base_offset
, &base_pos
) < 0)
1699 * We assume delta dependencies always point backwards. This
1700 * lets us do a single pass, and is basically always true
1701 * due to the way OFS_DELTAs work. You would not typically
1702 * find REF_DELTA in a bitmapped pack, since we only bitmap
1703 * packs we write fresh, and OFS_DELTA is the default). But
1704 * let's double check to make sure the pack wasn't written with
1707 if (base_pos
>= pos
)
1711 * And finally, if we're not sending the base as part of our
1712 * reuse chunk, then don't send this object either. The base
1713 * would come after us, along with other objects not
1714 * necessarily in the pack, which means we'd need to convert
1715 * to REF_DELTA on the fly. Better to just let the normal
1716 * object_entry code path handle it.
1718 if (!bitmap_get(reuse
, base_pos
))
1723 * If we got here, then the object is OK to reuse. Mark it.
1725 bitmap_set(reuse
, pos
);
1729 uint32_t midx_preferred_pack(struct bitmap_index
*bitmap_git
)
1731 struct multi_pack_index
*m
= bitmap_git
->midx
;
1733 BUG("midx_preferred_pack: requires non-empty MIDX");
1734 return nth_midxed_pack_int_id(m
, pack_pos_to_midx(bitmap_git
->midx
, 0));
1737 int reuse_partial_packfile_from_bitmap(struct bitmap_index
*bitmap_git
,
1738 struct packed_git
**packfile_out
,
1740 struct bitmap
**reuse_out
)
1742 struct packed_git
*pack
;
1743 struct bitmap
*result
= bitmap_git
->result
;
1744 struct bitmap
*reuse
;
1745 struct pack_window
*w_curs
= NULL
;
1748 uint32_t objects_nr
;
1752 load_reverse_index(bitmap_git
);
1754 if (bitmap_is_midx(bitmap_git
))
1755 pack
= bitmap_git
->midx
->packs
[midx_preferred_pack(bitmap_git
)];
1757 pack
= bitmap_git
->pack
;
1758 objects_nr
= pack
->num_objects
;
1760 while (i
< result
->word_alloc
&& result
->words
[i
] == (eword_t
)~0)
1764 * Don't mark objects not in the packfile or preferred pack. This bitmap
1765 * marks objects eligible for reuse, but the pack-reuse code only
1766 * understands how to reuse a single pack. Since the preferred pack is
1767 * guaranteed to have all bases for its deltas (in a multi-pack bitmap),
1768 * we use it instead of another pack. In single-pack bitmaps, the choice
1771 if (i
> objects_nr
/ BITS_IN_EWORD
)
1772 i
= objects_nr
/ BITS_IN_EWORD
;
1774 reuse
= bitmap_word_alloc(i
);
1775 memset(reuse
->words
, 0xFF, i
* sizeof(eword_t
));
1777 for (; i
< result
->word_alloc
; ++i
) {
1778 eword_t word
= result
->words
[i
];
1779 size_t pos
= (i
* BITS_IN_EWORD
);
1781 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
1782 if ((word
>> offset
) == 0)
1785 offset
+= ewah_bit_ctz64(word
>> offset
);
1786 if (try_partial_reuse(pack
, pos
+ offset
,
1787 reuse
, &w_curs
) < 0) {
1789 * try_partial_reuse indicated we couldn't reuse
1790 * any bits, so there is no point in trying more
1791 * bits in the current word, or any other words
1794 * Jump out of both loops to avoid future
1795 * unnecessary calls to try_partial_reuse.
1803 unuse_pack(&w_curs
);
1805 *entries
= bitmap_popcount(reuse
);
1812 * Drop any reused objects from the result, since they will not
1813 * need to be handled separately.
1815 bitmap_and_not(result
, reuse
);
1816 *packfile_out
= pack
;
1821 int bitmap_walk_contains(struct bitmap_index
*bitmap_git
,
1822 struct bitmap
*bitmap
, const struct object_id
*oid
)
1829 idx
= bitmap_position(bitmap_git
, oid
);
1830 return idx
>= 0 && bitmap_get(bitmap
, idx
);
1833 void traverse_bitmap_commit_list(struct bitmap_index
*bitmap_git
,
1834 struct rev_info
*revs
,
1835 show_reachable_fn show_reachable
)
1837 assert(bitmap_git
->result
);
1839 show_objects_for_type(bitmap_git
, OBJ_COMMIT
, show_reachable
);
1840 if (revs
->tree_objects
)
1841 show_objects_for_type(bitmap_git
, OBJ_TREE
, show_reachable
);
1842 if (revs
->blob_objects
)
1843 show_objects_for_type(bitmap_git
, OBJ_BLOB
, show_reachable
);
1844 if (revs
->tag_objects
)
1845 show_objects_for_type(bitmap_git
, OBJ_TAG
, show_reachable
);
1847 show_extended_objects(bitmap_git
, revs
, show_reachable
);
1850 static uint32_t count_object_type(struct bitmap_index
*bitmap_git
,
1851 enum object_type type
)
1853 struct bitmap
*objects
= bitmap_git
->result
;
1854 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1856 uint32_t i
= 0, count
= 0;
1857 struct ewah_iterator it
;
1860 init_type_iterator(&it
, bitmap_git
, type
);
1862 while (i
< objects
->word_alloc
&& ewah_iterator_next(&filter
, &it
)) {
1863 eword_t word
= objects
->words
[i
++] & filter
;
1864 count
+= ewah_bit_popcount64(word
);
1867 for (i
= 0; i
< eindex
->count
; ++i
) {
1868 if (eindex
->objects
[i
]->type
== type
&&
1869 bitmap_get(objects
, bitmap_num_objects(bitmap_git
) + i
))
1876 void count_bitmap_commit_list(struct bitmap_index
*bitmap_git
,
1877 uint32_t *commits
, uint32_t *trees
,
1878 uint32_t *blobs
, uint32_t *tags
)
1880 assert(bitmap_git
->result
);
1883 *commits
= count_object_type(bitmap_git
, OBJ_COMMIT
);
1886 *trees
= count_object_type(bitmap_git
, OBJ_TREE
);
1889 *blobs
= count_object_type(bitmap_git
, OBJ_BLOB
);
1892 *tags
= count_object_type(bitmap_git
, OBJ_TAG
);
1895 struct bitmap_test_data
{
1896 struct bitmap_index
*bitmap_git
;
1897 struct bitmap
*base
;
1898 struct bitmap
*commits
;
1899 struct bitmap
*trees
;
1900 struct bitmap
*blobs
;
1901 struct bitmap
*tags
;
1902 struct progress
*prg
;
1906 static void test_bitmap_type(struct bitmap_test_data
*tdata
,
1907 struct object
*obj
, int pos
)
1909 enum object_type bitmap_type
= OBJ_NONE
;
1912 if (bitmap_get(tdata
->commits
, pos
)) {
1913 bitmap_type
= OBJ_COMMIT
;
1916 if (bitmap_get(tdata
->trees
, pos
)) {
1917 bitmap_type
= OBJ_TREE
;
1920 if (bitmap_get(tdata
->blobs
, pos
)) {
1921 bitmap_type
= OBJ_BLOB
;
1924 if (bitmap_get(tdata
->tags
, pos
)) {
1925 bitmap_type
= OBJ_TAG
;
1929 if (bitmap_type
== OBJ_NONE
)
1930 die(_("object '%s' not found in type bitmaps"),
1931 oid_to_hex(&obj
->oid
));
1934 die(_("object '%s' does not have a unique type"),
1935 oid_to_hex(&obj
->oid
));
1937 if (bitmap_type
!= obj
->type
)
1938 die(_("object '%s': real type '%s', expected: '%s'"),
1939 oid_to_hex(&obj
->oid
),
1940 type_name(obj
->type
),
1941 type_name(bitmap_type
));
1944 static void test_show_object(struct object
*object
,
1945 const char *name UNUSED
,
1948 struct bitmap_test_data
*tdata
= data
;
1951 bitmap_pos
= bitmap_position(tdata
->bitmap_git
, &object
->oid
);
1953 die(_("object not in bitmap: '%s'"), oid_to_hex(&object
->oid
));
1954 test_bitmap_type(tdata
, object
, bitmap_pos
);
1956 bitmap_set(tdata
->base
, bitmap_pos
);
1957 display_progress(tdata
->prg
, ++tdata
->seen
);
1960 static void test_show_commit(struct commit
*commit
, void *data
)
1962 struct bitmap_test_data
*tdata
= data
;
1965 bitmap_pos
= bitmap_position(tdata
->bitmap_git
,
1966 &commit
->object
.oid
);
1968 die(_("object not in bitmap: '%s'"), oid_to_hex(&commit
->object
.oid
));
1969 test_bitmap_type(tdata
, &commit
->object
, bitmap_pos
);
1971 bitmap_set(tdata
->base
, bitmap_pos
);
1972 display_progress(tdata
->prg
, ++tdata
->seen
);
1975 void test_bitmap_walk(struct rev_info
*revs
)
1977 struct object
*root
;
1978 struct bitmap
*result
= NULL
;
1979 size_t result_popcnt
;
1980 struct bitmap_test_data tdata
;
1981 struct bitmap_index
*bitmap_git
;
1982 struct ewah_bitmap
*bm
;
1984 if (!(bitmap_git
= prepare_bitmap_git(revs
->repo
)))
1985 die(_("failed to load bitmap indexes"));
1987 if (revs
->pending
.nr
!= 1)
1988 die(_("you must specify exactly one commit to test"));
1990 fprintf_ln(stderr
, "Bitmap v%d test (%d entries%s)",
1991 bitmap_git
->version
,
1992 bitmap_git
->entry_count
,
1993 bitmap_git
->table_lookup
? "" : " loaded");
1995 root
= revs
->pending
.objects
[0].item
;
1996 bm
= bitmap_for_commit(bitmap_git
, (struct commit
*)root
);
1999 fprintf_ln(stderr
, "Found bitmap for '%s'. %d bits / %08x checksum",
2000 oid_to_hex(&root
->oid
), (int)bm
->bit_size
, ewah_checksum(bm
));
2002 result
= ewah_to_bitmap(bm
);
2006 die(_("commit '%s' doesn't have an indexed bitmap"), oid_to_hex(&root
->oid
));
2008 revs
->tag_objects
= 1;
2009 revs
->tree_objects
= 1;
2010 revs
->blob_objects
= 1;
2012 result_popcnt
= bitmap_popcount(result
);
2014 if (prepare_revision_walk(revs
))
2015 die(_("revision walk setup failed"));
2017 tdata
.bitmap_git
= bitmap_git
;
2018 tdata
.base
= bitmap_new();
2019 tdata
.commits
= ewah_to_bitmap(bitmap_git
->commits
);
2020 tdata
.trees
= ewah_to_bitmap(bitmap_git
->trees
);
2021 tdata
.blobs
= ewah_to_bitmap(bitmap_git
->blobs
);
2022 tdata
.tags
= ewah_to_bitmap(bitmap_git
->tags
);
2023 tdata
.prg
= start_progress("Verifying bitmap entries", result_popcnt
);
2026 traverse_commit_list(revs
, &test_show_commit
, &test_show_object
, &tdata
);
2028 stop_progress(&tdata
.prg
);
2030 if (bitmap_equals(result
, tdata
.base
))
2031 fprintf_ln(stderr
, "OK!");
2033 die(_("mismatch in bitmap results"));
2035 bitmap_free(result
);
2036 bitmap_free(tdata
.base
);
2037 bitmap_free(tdata
.commits
);
2038 bitmap_free(tdata
.trees
);
2039 bitmap_free(tdata
.blobs
);
2040 bitmap_free(tdata
.tags
);
2041 free_bitmap_index(bitmap_git
);
2044 int test_bitmap_commits(struct repository
*r
)
2046 struct object_id oid
;
2047 MAYBE_UNUSED
void *value
;
2048 struct bitmap_index
*bitmap_git
= prepare_bitmap_git(r
);
2051 die(_("failed to load bitmap indexes"));
2054 * As this function is only used to print bitmap selected
2055 * commits, we don't have to read the commit table.
2057 if (bitmap_git
->table_lookup
) {
2058 if (load_bitmap_entries_v1(bitmap_git
) < 0)
2059 die(_("failed to load bitmap indexes"));
2062 kh_foreach(bitmap_git
->bitmaps
, oid
, value
, {
2063 printf_ln("%s", oid_to_hex(&oid
));
2066 free_bitmap_index(bitmap_git
);
2071 int test_bitmap_hashes(struct repository
*r
)
2073 struct bitmap_index
*bitmap_git
= prepare_bitmap_git(r
);
2074 struct object_id oid
;
2075 uint32_t i
, index_pos
;
2077 if (!bitmap_git
|| !bitmap_git
->hashes
)
2080 for (i
= 0; i
< bitmap_num_objects(bitmap_git
); i
++) {
2081 if (bitmap_is_midx(bitmap_git
))
2082 index_pos
= pack_pos_to_midx(bitmap_git
->midx
, i
);
2084 index_pos
= pack_pos_to_index(bitmap_git
->pack
, i
);
2086 nth_bitmap_object_oid(bitmap_git
, &oid
, index_pos
);
2088 printf_ln("%s %"PRIu32
"",
2089 oid_to_hex(&oid
), get_be32(bitmap_git
->hashes
+ index_pos
));
2093 free_bitmap_index(bitmap_git
);
2098 int rebuild_bitmap(const uint32_t *reposition
,
2099 struct ewah_bitmap
*source
,
2100 struct bitmap
*dest
)
2103 struct ewah_iterator it
;
2106 ewah_iterator_init(&it
, source
);
2108 while (ewah_iterator_next(&word
, &it
)) {
2109 uint32_t offset
, bit_pos
;
2111 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
2112 if ((word
>> offset
) == 0)
2115 offset
+= ewah_bit_ctz64(word
>> offset
);
2117 bit_pos
= reposition
[pos
+ offset
];
2119 bitmap_set(dest
, bit_pos
- 1);
2120 else /* can't reuse, we don't have the object */
2124 pos
+= BITS_IN_EWORD
;
2129 uint32_t *create_bitmap_mapping(struct bitmap_index
*bitmap_git
,
2130 struct packing_data
*mapping
)
2132 uint32_t i
, num_objects
;
2133 uint32_t *reposition
;
2135 if (!bitmap_is_midx(bitmap_git
))
2136 load_reverse_index(bitmap_git
);
2137 else if (load_midx_revindex(bitmap_git
->midx
) < 0)
2138 BUG("rebuild_existing_bitmaps: missing required rev-cache "
2141 num_objects
= bitmap_num_objects(bitmap_git
);
2142 CALLOC_ARRAY(reposition
, num_objects
);
2144 for (i
= 0; i
< num_objects
; ++i
) {
2145 struct object_id oid
;
2146 struct object_entry
*oe
;
2149 if (bitmap_is_midx(bitmap_git
))
2150 index_pos
= pack_pos_to_midx(bitmap_git
->midx
, i
);
2152 index_pos
= pack_pos_to_index(bitmap_git
->pack
, i
);
2153 nth_bitmap_object_oid(bitmap_git
, &oid
, index_pos
);
2154 oe
= packlist_find(mapping
, &oid
);
2157 reposition
[i
] = oe_in_pack_pos(mapping
, oe
) + 1;
2158 if (bitmap_git
->hashes
&& !oe
->hash
)
2159 oe
->hash
= get_be32(bitmap_git
->hashes
+ index_pos
);
2166 void free_bitmap_index(struct bitmap_index
*b
)
2172 munmap(b
->map
, b
->map_size
);
2173 ewah_pool_free(b
->commits
);
2174 ewah_pool_free(b
->trees
);
2175 ewah_pool_free(b
->blobs
);
2176 ewah_pool_free(b
->tags
);
2178 struct stored_bitmap
*sb
;
2179 kh_foreach_value(b
->bitmaps
, sb
, {
2180 ewah_pool_free(sb
->root
);
2184 kh_destroy_oid_map(b
->bitmaps
);
2185 free(b
->ext_index
.objects
);
2186 free(b
->ext_index
.hashes
);
2187 kh_destroy_oid_pos(b
->ext_index
.positions
);
2188 bitmap_free(b
->result
);
2189 bitmap_free(b
->haves
);
2190 if (bitmap_is_midx(b
)) {
2192 * Multi-pack bitmaps need to have resources associated with
2193 * their on-disk reverse indexes unmapped so that stale .rev and
2194 * .bitmap files can be removed.
2196 * Unlike pack-based bitmaps, multi-pack bitmaps can be read and
2197 * written in the same 'git multi-pack-index write --bitmap'
2198 * process. Close resources so they can be removed safely on
2199 * platforms like Windows.
2201 close_midx_revindex(b
->midx
);
2206 int bitmap_has_oid_in_uninteresting(struct bitmap_index
*bitmap_git
,
2207 const struct object_id
*oid
)
2209 return bitmap_git
&&
2210 bitmap_walk_contains(bitmap_git
, bitmap_git
->haves
, oid
);
2213 static off_t
get_disk_usage_for_type(struct bitmap_index
*bitmap_git
,
2214 enum object_type object_type
)
2216 struct bitmap
*result
= bitmap_git
->result
;
2218 struct ewah_iterator it
;
2222 init_type_iterator(&it
, bitmap_git
, object_type
);
2223 for (i
= 0; i
< result
->word_alloc
&&
2224 ewah_iterator_next(&filter
, &it
); i
++) {
2225 eword_t word
= result
->words
[i
] & filter
;
2226 size_t base
= (i
* BITS_IN_EWORD
);
2232 for (offset
= 0; offset
< BITS_IN_EWORD
; offset
++) {
2233 if ((word
>> offset
) == 0)
2236 offset
+= ewah_bit_ctz64(word
>> offset
);
2238 if (bitmap_is_midx(bitmap_git
)) {
2240 uint32_t midx_pos
= pack_pos_to_midx(bitmap_git
->midx
, base
+ offset
);
2241 off_t offset
= nth_midxed_offset(bitmap_git
->midx
, midx_pos
);
2243 uint32_t pack_id
= nth_midxed_pack_int_id(bitmap_git
->midx
, midx_pos
);
2244 struct packed_git
*pack
= bitmap_git
->midx
->packs
[pack_id
];
2246 if (offset_to_pack_pos(pack
, offset
, &pack_pos
) < 0) {
2247 struct object_id oid
;
2248 nth_midxed_object_oid(&oid
, bitmap_git
->midx
, midx_pos
);
2250 die(_("could not find '%s' in pack '%s' at offset %"PRIuMAX
),
2256 total
+= pack_pos_to_offset(pack
, pack_pos
+ 1) - offset
;
2258 size_t pos
= base
+ offset
;
2259 total
+= pack_pos_to_offset(bitmap_git
->pack
, pos
+ 1) -
2260 pack_pos_to_offset(bitmap_git
->pack
, pos
);
2268 static off_t
get_disk_usage_for_extended(struct bitmap_index
*bitmap_git
)
2270 struct bitmap
*result
= bitmap_git
->result
;
2271 struct eindex
*eindex
= &bitmap_git
->ext_index
;
2273 struct object_info oi
= OBJECT_INFO_INIT
;
2277 oi
.disk_sizep
= &object_size
;
2279 for (i
= 0; i
< eindex
->count
; i
++) {
2280 struct object
*obj
= eindex
->objects
[i
];
2282 if (!bitmap_get(result
, bitmap_num_objects(bitmap_git
) + i
))
2285 if (oid_object_info_extended(the_repository
, &obj
->oid
, &oi
, 0) < 0)
2286 die(_("unable to get disk usage of '%s'"),
2287 oid_to_hex(&obj
->oid
));
2289 total
+= object_size
;
2294 off_t
get_disk_usage_from_bitmap(struct bitmap_index
*bitmap_git
,
2295 struct rev_info
*revs
)
2299 total
+= get_disk_usage_for_type(bitmap_git
, OBJ_COMMIT
);
2300 if (revs
->tree_objects
)
2301 total
+= get_disk_usage_for_type(bitmap_git
, OBJ_TREE
);
2302 if (revs
->blob_objects
)
2303 total
+= get_disk_usage_for_type(bitmap_git
, OBJ_BLOB
);
2304 if (revs
->tag_objects
)
2305 total
+= get_disk_usage_for_type(bitmap_git
, OBJ_TAG
);
2307 total
+= get_disk_usage_for_extended(bitmap_git
);
2312 int bitmap_is_midx(struct bitmap_index
*bitmap_git
)
2314 return !!bitmap_git
->midx
;
2317 const struct string_list
*bitmap_preferred_tips(struct repository
*r
)
2319 return repo_config_get_value_multi(r
, "pack.preferbitmaptips");
2322 int bitmap_is_preferred_refname(struct repository
*r
, const char *refname
)
2324 const struct string_list
*preferred_tips
= bitmap_preferred_tips(r
);
2325 struct string_list_item
*item
;
2327 if (!preferred_tips
)
2330 for_each_string_list_item(item
, preferred_tips
) {
2331 if (starts_with(refname
, item
->string
))