1 #include "git-compat-util.h"
10 #include "list-objects.h"
12 #include "pack-bitmap.h"
13 #include "pack-revindex.h"
14 #include "pack-objects.h"
16 #include "repository.h"
17 #include "object-store.h"
18 #include "list-objects-filter-options.h"
23 * An entry on the bitmap index, representing the bitmap for a given
26 struct stored_bitmap
{
28 struct ewah_bitmap
*root
;
29 struct stored_bitmap
*xor;
34 * The active bitmap index for a repository. By design, repositories only have
35 * a single bitmap index available (the index for the biggest packfile in
36 * the repository), since bitmap indexes need full closure.
38 * If there is more than one bitmap index available (e.g. because of alternates),
39 * the active bitmap index is the largest one.
43 * The pack or multi-pack index (MIDX) that this bitmap index belongs
46 * Exactly one of these must be non-NULL; this specifies the object
47 * order used to interpret this bitmap.
49 struct packed_git
*pack
;
50 struct multi_pack_index
*midx
;
53 * Mark the first `reuse_objects` in the packfile as reused:
54 * they will be sent as-is without using them for repacking
57 uint32_t reuse_objects
;
59 /* mmapped buffer of the whole bitmap index */
61 size_t map_size
; /* size of the mmaped buffer */
62 size_t map_pos
; /* current position when loading the index */
67 * Each bitmap marks which objects in the packfile are of the given
68 * type. This provides type information when yielding the objects from
69 * the packfile during a walk, which allows for better delta bases.
71 struct ewah_bitmap
*commits
;
72 struct ewah_bitmap
*trees
;
73 struct ewah_bitmap
*blobs
;
74 struct ewah_bitmap
*tags
;
76 /* Map from object ID -> `stored_bitmap` for all the bitmapped commits */
77 kh_oid_map_t
*bitmaps
;
79 /* Number of bitmapped commits */
82 /* If not NULL, this is a name-hash cache pointing into map. */
85 /* The checksum of the packfile or MIDX; points into map. */
86 const unsigned char *checksum
;
89 * If not NULL, this point into the commit table extension
90 * (within the memory mapped region `map`).
92 unsigned char *table_lookup
;
97 * When trying to perform bitmap operations with objects that are not
98 * packed in `pack`, these objects are added to this "fake index" and
99 * are assumed to appear at the end of the packfile for all operations
102 struct object
**objects
;
104 uint32_t count
, alloc
;
105 kh_oid_pos_t
*positions
;
108 /* Bitmap result of the last performed walk */
109 struct bitmap
*result
;
111 /* "have" bitmap from the last performed walk */
112 struct bitmap
*haves
;
114 /* Version of the bitmap index */
115 unsigned int version
;
118 static struct ewah_bitmap
*lookup_stored_bitmap(struct stored_bitmap
*st
)
120 struct ewah_bitmap
*parent
;
121 struct ewah_bitmap
*composed
;
126 composed
= ewah_pool_new();
127 parent
= lookup_stored_bitmap(st
->xor);
128 ewah_xor(st
->root
, parent
, composed
);
130 ewah_pool_free(st
->root
);
138 * Read a bitmap from the current read position on the mmaped
139 * index, and increase the read position accordingly
141 static struct ewah_bitmap
*read_bitmap_1(struct bitmap_index
*index
)
143 struct ewah_bitmap
*b
= ewah_pool_new();
145 ssize_t bitmap_size
= ewah_read_mmap(b
,
146 index
->map
+ index
->map_pos
,
147 index
->map_size
- index
->map_pos
);
149 if (bitmap_size
< 0) {
150 error(_("failed to load bitmap index (corrupted?)"));
155 index
->map_pos
+= bitmap_size
;
159 static uint32_t bitmap_num_objects(struct bitmap_index
*index
)
162 return index
->midx
->num_objects
;
163 return index
->pack
->num_objects
;
166 static int load_bitmap_header(struct bitmap_index
*index
)
168 struct bitmap_disk_header
*header
= (void *)index
->map
;
169 size_t header_size
= sizeof(*header
) - GIT_MAX_RAWSZ
+ the_hash_algo
->rawsz
;
171 if (index
->map_size
< header_size
+ the_hash_algo
->rawsz
)
172 return error(_("corrupted bitmap index (too small)"));
174 if (memcmp(header
->magic
, BITMAP_IDX_SIGNATURE
, sizeof(BITMAP_IDX_SIGNATURE
)) != 0)
175 return error(_("corrupted bitmap index file (wrong header)"));
177 index
->version
= ntohs(header
->version
);
178 if (index
->version
!= 1)
179 return error(_("unsupported version '%d' for bitmap index file"), index
->version
);
181 /* Parse known bitmap format options */
183 uint32_t flags
= ntohs(header
->options
);
184 size_t cache_size
= st_mult(bitmap_num_objects(index
), sizeof(uint32_t));
185 unsigned char *index_end
= index
->map
+ index
->map_size
- the_hash_algo
->rawsz
;
187 if ((flags
& BITMAP_OPT_FULL_DAG
) == 0)
188 BUG("unsupported options for bitmap index file "
189 "(Git requires BITMAP_OPT_FULL_DAG)");
191 if (flags
& BITMAP_OPT_HASH_CACHE
) {
192 if (cache_size
> index_end
- index
->map
- header_size
)
193 return error(_("corrupted bitmap index file (too short to fit hash cache)"));
194 index
->hashes
= (void *)(index_end
- cache_size
);
195 index_end
-= cache_size
;
198 if (flags
& BITMAP_OPT_LOOKUP_TABLE
) {
199 size_t table_size
= st_mult(ntohl(header
->entry_count
),
200 BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH
);
201 if (table_size
> index_end
- index
->map
- header_size
)
202 return error(_("corrupted bitmap index file (too short to fit lookup table)"));
203 if (git_env_bool("GIT_TEST_READ_COMMIT_TABLE", 1))
204 index
->table_lookup
= (void *)(index_end
- table_size
);
205 index_end
-= table_size
;
209 index
->entry_count
= ntohl(header
->entry_count
);
210 index
->checksum
= header
->checksum
;
211 index
->map_pos
+= header_size
;
215 static struct stored_bitmap
*store_bitmap(struct bitmap_index
*index
,
216 struct ewah_bitmap
*root
,
217 const struct object_id
*oid
,
218 struct stored_bitmap
*xor_with
,
221 struct stored_bitmap
*stored
;
225 stored
= xmalloc(sizeof(struct stored_bitmap
));
227 stored
->xor = xor_with
;
228 stored
->flags
= flags
;
229 oidcpy(&stored
->oid
, oid
);
231 hash_pos
= kh_put_oid_map(index
->bitmaps
, stored
->oid
, &ret
);
234 * A 0 return code means the insertion succeeded with no changes,
235 * because the SHA1 already existed on the map. This is bad, there
236 * shouldn't be duplicated commits in the index.
239 error(_("duplicate entry in bitmap index: '%s'"), oid_to_hex(oid
));
243 kh_value(index
->bitmaps
, hash_pos
) = stored
;
247 static inline uint32_t read_be32(const unsigned char *buffer
, size_t *pos
)
249 uint32_t result
= get_be32(buffer
+ *pos
);
250 (*pos
) += sizeof(result
);
254 static inline uint8_t read_u8(const unsigned char *buffer
, size_t *pos
)
256 return buffer
[(*pos
)++];
259 #define MAX_XOR_OFFSET 160
261 static int nth_bitmap_object_oid(struct bitmap_index
*index
,
262 struct object_id
*oid
,
266 return nth_midxed_object_oid(oid
, index
->midx
, n
) ? 0 : -1;
267 return nth_packed_object_id(oid
, index
->pack
, n
);
270 static int load_bitmap_entries_v1(struct bitmap_index
*index
)
273 struct stored_bitmap
*recent_bitmaps
[MAX_XOR_OFFSET
] = { NULL
};
275 for (i
= 0; i
< index
->entry_count
; ++i
) {
276 int xor_offset
, flags
;
277 struct ewah_bitmap
*bitmap
= NULL
;
278 struct stored_bitmap
*xor_bitmap
= NULL
;
279 uint32_t commit_idx_pos
;
280 struct object_id oid
;
282 if (index
->map_size
- index
->map_pos
< 6)
283 return error(_("corrupt ewah bitmap: truncated header for entry %d"), i
);
285 commit_idx_pos
= read_be32(index
->map
, &index
->map_pos
);
286 xor_offset
= read_u8(index
->map
, &index
->map_pos
);
287 flags
= read_u8(index
->map
, &index
->map_pos
);
289 if (nth_bitmap_object_oid(index
, &oid
, commit_idx_pos
) < 0)
290 return error(_("corrupt ewah bitmap: commit index %u out of range"),
291 (unsigned)commit_idx_pos
);
293 bitmap
= read_bitmap_1(index
);
297 if (xor_offset
> MAX_XOR_OFFSET
|| xor_offset
> i
)
298 return error(_("corrupted bitmap pack index"));
300 if (xor_offset
> 0) {
301 xor_bitmap
= recent_bitmaps
[(i
- xor_offset
) % MAX_XOR_OFFSET
];
304 return error(_("invalid XOR offset in bitmap pack index"));
307 recent_bitmaps
[i
% MAX_XOR_OFFSET
] = store_bitmap(
308 index
, bitmap
, &oid
, xor_bitmap
, flags
);
314 char *midx_bitmap_filename(struct multi_pack_index
*midx
)
316 struct strbuf buf
= STRBUF_INIT
;
318 get_midx_filename(&buf
, midx
->object_dir
);
319 strbuf_addf(&buf
, "-%s.bitmap", hash_to_hex(get_midx_checksum(midx
)));
321 return strbuf_detach(&buf
, NULL
);
324 char *pack_bitmap_filename(struct packed_git
*p
)
328 if (!strip_suffix(p
->pack_name
, ".pack", &len
))
329 BUG("pack_name does not end in .pack");
330 return xstrfmt("%.*s.bitmap", (int)len
, p
->pack_name
);
333 static int open_midx_bitmap_1(struct bitmap_index
*bitmap_git
,
334 struct multi_pack_index
*midx
)
337 char *bitmap_name
= midx_bitmap_filename(midx
);
338 int fd
= git_open(bitmap_name
);
340 struct packed_git
*preferred
;
344 warning_errno("cannot open '%s'", bitmap_name
);
350 if (fstat(fd
, &st
)) {
351 error_errno(_("cannot fstat bitmap file"));
356 if (bitmap_git
->pack
|| bitmap_git
->midx
) {
357 struct strbuf buf
= STRBUF_INIT
;
358 get_midx_filename(&buf
, midx
->object_dir
);
359 trace2_data_string("bitmap", the_repository
,
360 "ignoring extra midx bitmap file", buf
.buf
);
362 strbuf_release(&buf
);
366 bitmap_git
->midx
= midx
;
367 bitmap_git
->map_size
= xsize_t(st
.st_size
);
368 bitmap_git
->map_pos
= 0;
369 bitmap_git
->map
= xmmap(NULL
, bitmap_git
->map_size
, PROT_READ
,
373 if (load_bitmap_header(bitmap_git
) < 0)
376 if (!hasheq(get_midx_checksum(bitmap_git
->midx
), bitmap_git
->checksum
)) {
377 error(_("checksum doesn't match in MIDX and bitmap"));
381 if (load_midx_revindex(bitmap_git
->midx
) < 0) {
382 warning(_("multi-pack bitmap is missing required reverse index"));
386 for (i
= 0; i
< bitmap_git
->midx
->num_packs
; i
++) {
387 if (prepare_midx_pack(the_repository
, bitmap_git
->midx
, i
))
388 die(_("could not open pack %s"),
389 bitmap_git
->midx
->pack_names
[i
]);
392 preferred
= bitmap_git
->midx
->packs
[midx_preferred_pack(bitmap_git
)];
393 if (!is_pack_valid(preferred
)) {
394 warning(_("preferred pack (%s) is invalid"),
395 preferred
->pack_name
);
402 munmap(bitmap_git
->map
, bitmap_git
->map_size
);
403 bitmap_git
->map_size
= 0;
404 bitmap_git
->map_pos
= 0;
405 bitmap_git
->map
= NULL
;
406 bitmap_git
->midx
= NULL
;
410 static int open_pack_bitmap_1(struct bitmap_index
*bitmap_git
, struct packed_git
*packfile
)
416 bitmap_name
= pack_bitmap_filename(packfile
);
417 fd
= git_open(bitmap_name
);
421 warning_errno("cannot open '%s'", bitmap_name
);
427 if (fstat(fd
, &st
)) {
428 error_errno(_("cannot fstat bitmap file"));
433 if (bitmap_git
->pack
|| bitmap_git
->midx
) {
434 trace2_data_string("bitmap", the_repository
,
435 "ignoring extra bitmap file", packfile
->pack_name
);
440 if (!is_pack_valid(packfile
)) {
445 bitmap_git
->pack
= packfile
;
446 bitmap_git
->map_size
= xsize_t(st
.st_size
);
447 bitmap_git
->map
= xmmap(NULL
, bitmap_git
->map_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
448 bitmap_git
->map_pos
= 0;
451 if (load_bitmap_header(bitmap_git
) < 0) {
452 munmap(bitmap_git
->map
, bitmap_git
->map_size
);
453 bitmap_git
->map
= NULL
;
454 bitmap_git
->map_size
= 0;
455 bitmap_git
->map_pos
= 0;
456 bitmap_git
->pack
= NULL
;
460 trace2_data_string("bitmap", the_repository
, "opened bitmap file",
461 packfile
->pack_name
);
465 static int load_reverse_index(struct bitmap_index
*bitmap_git
)
467 if (bitmap_is_midx(bitmap_git
)) {
472 * The multi-pack-index's .rev file is already loaded via
473 * open_pack_bitmap_1().
475 * But we still need to open the individual pack .rev files,
476 * since we will need to make use of them in pack-objects.
478 for (i
= 0; i
< bitmap_git
->midx
->num_packs
; i
++) {
479 ret
= load_pack_revindex(bitmap_git
->midx
->packs
[i
]);
485 return load_pack_revindex(bitmap_git
->pack
);
488 static int load_bitmap(struct bitmap_index
*bitmap_git
)
490 assert(bitmap_git
->map
);
492 bitmap_git
->bitmaps
= kh_init_oid_map();
493 bitmap_git
->ext_index
.positions
= kh_init_oid_pos();
495 if (load_reverse_index(bitmap_git
))
498 if (!(bitmap_git
->commits
= read_bitmap_1(bitmap_git
)) ||
499 !(bitmap_git
->trees
= read_bitmap_1(bitmap_git
)) ||
500 !(bitmap_git
->blobs
= read_bitmap_1(bitmap_git
)) ||
501 !(bitmap_git
->tags
= read_bitmap_1(bitmap_git
)))
504 if (!bitmap_git
->table_lookup
&& load_bitmap_entries_v1(bitmap_git
) < 0)
510 munmap(bitmap_git
->map
, bitmap_git
->map_size
);
511 bitmap_git
->map
= NULL
;
512 bitmap_git
->map_size
= 0;
514 kh_destroy_oid_map(bitmap_git
->bitmaps
);
515 bitmap_git
->bitmaps
= NULL
;
517 kh_destroy_oid_pos(bitmap_git
->ext_index
.positions
);
518 bitmap_git
->ext_index
.positions
= NULL
;
523 static int open_pack_bitmap(struct repository
*r
,
524 struct bitmap_index
*bitmap_git
)
526 struct packed_git
*p
;
529 for (p
= get_all_packs(r
); p
; p
= p
->next
) {
530 if (open_pack_bitmap_1(bitmap_git
, p
) == 0) {
533 * The only reason to keep looking is to report
536 if (!trace2_is_enabled())
544 static int open_midx_bitmap(struct repository
*r
,
545 struct bitmap_index
*bitmap_git
)
548 struct multi_pack_index
*midx
;
550 assert(!bitmap_git
->map
);
552 for (midx
= get_multi_pack_index(r
); midx
; midx
= midx
->next
) {
553 if (!open_midx_bitmap_1(bitmap_git
, midx
))
559 static int open_bitmap(struct repository
*r
,
560 struct bitmap_index
*bitmap_git
)
564 assert(!bitmap_git
->map
);
566 found
= !open_midx_bitmap(r
, bitmap_git
);
569 * these will all be skipped if we opened a midx bitmap; but run it
570 * anyway if tracing is enabled to report the duplicates
572 if (!found
|| trace2_is_enabled())
573 found
|= !open_pack_bitmap(r
, bitmap_git
);
575 return found
? 0 : -1;
578 struct bitmap_index
*prepare_bitmap_git(struct repository
*r
)
580 struct bitmap_index
*bitmap_git
= xcalloc(1, sizeof(*bitmap_git
));
582 if (!open_bitmap(r
, bitmap_git
) && !load_bitmap(bitmap_git
))
585 free_bitmap_index(bitmap_git
);
589 struct bitmap_index
*prepare_midx_bitmap_git(struct multi_pack_index
*midx
)
591 struct bitmap_index
*bitmap_git
= xcalloc(1, sizeof(*bitmap_git
));
593 if (!open_midx_bitmap_1(bitmap_git
, midx
) && !load_bitmap(bitmap_git
))
596 free_bitmap_index(bitmap_git
);
600 struct include_data
{
601 struct bitmap_index
*bitmap_git
;
606 struct bitmap_lookup_table_triplet
{
612 struct bitmap_lookup_table_xor_item
{
613 struct object_id oid
;
618 * Given a `triplet` struct pointer and pointer `p`, this
619 * function reads the triplet beginning at `p` into the struct.
620 * Note that this function assumes that there is enough memory
621 * left for filling the `triplet` struct from `p`.
623 static int bitmap_lookup_table_get_triplet_by_pointer(struct bitmap_lookup_table_triplet
*triplet
,
624 const unsigned char *p
)
629 triplet
->commit_pos
= get_be32(p
);
630 p
+= sizeof(uint32_t);
631 triplet
->offset
= get_be64(p
);
632 p
+= sizeof(uint64_t);
633 triplet
->xor_row
= get_be32(p
);
638 * This function gets the raw triplet from `row`'th row in the
639 * lookup table and fills that data to the `triplet`.
641 static int bitmap_lookup_table_get_triplet(struct bitmap_index
*bitmap_git
,
643 struct bitmap_lookup_table_triplet
*triplet
)
645 unsigned char *p
= NULL
;
646 if (pos
>= bitmap_git
->entry_count
)
647 return error(_("corrupt bitmap lookup table: triplet position out of index"));
649 p
= bitmap_git
->table_lookup
+ st_mult(pos
, BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH
);
651 return bitmap_lookup_table_get_triplet_by_pointer(triplet
, p
);
655 * Searches for a matching triplet. `commit_pos` is a pointer
656 * to the wanted commit position value. `table_entry` points to
657 * a triplet in lookup table. The first 4 bytes of each
658 * triplet (pointed by `table_entry`) are compared with `*commit_pos`.
660 static int triplet_cmp(const void *commit_pos
, const void *table_entry
)
663 uint32_t a
= *(uint32_t *)commit_pos
;
664 uint32_t b
= get_be32(table_entry
);
673 static uint32_t bitmap_bsearch_pos(struct bitmap_index
*bitmap_git
,
674 struct object_id
*oid
,
679 if (bitmap_is_midx(bitmap_git
))
680 found
= bsearch_midx(oid
, bitmap_git
->midx
, result
);
682 found
= bsearch_pack(oid
, bitmap_git
->pack
, result
);
688 * `bsearch_triplet_by_pos` function searches for the raw triplet
689 * having commit position same as `commit_pos` and fills `triplet`
690 * object from the raw triplet. Returns 1 on success and 0 on
693 static int bitmap_bsearch_triplet_by_pos(uint32_t commit_pos
,
694 struct bitmap_index
*bitmap_git
,
695 struct bitmap_lookup_table_triplet
*triplet
)
697 unsigned char *p
= bsearch(&commit_pos
, bitmap_git
->table_lookup
, bitmap_git
->entry_count
,
698 BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH
, triplet_cmp
);
703 return bitmap_lookup_table_get_triplet_by_pointer(triplet
, p
);
706 static struct stored_bitmap
*lazy_bitmap_for_commit(struct bitmap_index
*bitmap_git
,
707 struct commit
*commit
)
709 uint32_t commit_pos
, xor_row
;
712 struct bitmap_lookup_table_triplet triplet
;
713 struct object_id
*oid
= &commit
->object
.oid
;
714 struct ewah_bitmap
*bitmap
;
715 struct stored_bitmap
*xor_bitmap
= NULL
;
716 const int bitmap_header_size
= 6;
717 static struct bitmap_lookup_table_xor_item
*xor_items
= NULL
;
718 static size_t xor_items_nr
= 0, xor_items_alloc
= 0;
719 static int is_corrupt
= 0;
722 struct bitmap_lookup_table_xor_item
*xor_item
;
727 if (!bitmap_bsearch_pos(bitmap_git
, oid
, &commit_pos
))
730 if (bitmap_bsearch_triplet_by_pos(commit_pos
, bitmap_git
, &triplet
) < 0)
734 offset
= triplet
.offset
;
735 xor_row
= triplet
.xor_row
;
737 while (xor_row
!= 0xffffffff) {
738 ALLOC_GROW(xor_items
, xor_items_nr
+ 1, xor_items_alloc
);
740 if (xor_items_nr
+ 1 >= bitmap_git
->entry_count
) {
741 error(_("corrupt bitmap lookup table: xor chain exceeds entry count"));
745 if (bitmap_lookup_table_get_triplet(bitmap_git
, xor_row
, &triplet
) < 0)
748 xor_item
= &xor_items
[xor_items_nr
];
749 xor_item
->offset
= triplet
.offset
;
751 if (nth_bitmap_object_oid(bitmap_git
, &xor_item
->oid
, triplet
.commit_pos
) < 0) {
752 error(_("corrupt bitmap lookup table: commit index %u out of range"),
757 hash_pos
= kh_get_oid_map(bitmap_git
->bitmaps
, xor_item
->oid
);
760 * If desired bitmap is already stored, we don't need
761 * to iterate further. Because we know that bitmaps
762 * that are needed to be parsed to parse this bitmap
763 * has already been stored. So, assign this stored bitmap
766 if (hash_pos
< kh_end(bitmap_git
->bitmaps
) &&
767 (xor_bitmap
= kh_value(bitmap_git
->bitmaps
, hash_pos
)))
770 xor_row
= triplet
.xor_row
;
773 while (xor_items_nr
) {
774 xor_item
= &xor_items
[xor_items_nr
- 1];
775 bitmap_git
->map_pos
= xor_item
->offset
;
776 if (bitmap_git
->map_size
- bitmap_git
->map_pos
< bitmap_header_size
) {
777 error(_("corrupt ewah bitmap: truncated header for bitmap of commit \"%s\""),
778 oid_to_hex(&xor_item
->oid
));
782 bitmap_git
->map_pos
+= sizeof(uint32_t) + sizeof(uint8_t);
783 xor_flags
= read_u8(bitmap_git
->map
, &bitmap_git
->map_pos
);
784 bitmap
= read_bitmap_1(bitmap_git
);
789 xor_bitmap
= store_bitmap(bitmap_git
, bitmap
, &xor_item
->oid
, xor_bitmap
, xor_flags
);
793 bitmap_git
->map_pos
= offset
;
794 if (bitmap_git
->map_size
- bitmap_git
->map_pos
< bitmap_header_size
) {
795 error(_("corrupt ewah bitmap: truncated header for bitmap of commit \"%s\""),
801 * Don't bother reading the commit's index position or its xor
804 * - The commit's index position is irrelevant to us, since
805 * load_bitmap_entries_v1 only uses it to learn the object
806 * id which is used to compute the hashmap's key. We already
807 * have an object id, so no need to look it up again.
809 * - The xor_offset is unusable for us, since it specifies how
810 * many entries previous to ours we should look at. This
811 * makes sense when reading the bitmaps sequentially (as in
812 * load_bitmap_entries_v1()), since we can keep track of
813 * each bitmap as we read them.
815 * But it can't work for us, since the bitmap's don't have a
816 * fixed size. So we learn the position of the xor'd bitmap
817 * from the commit table (and resolve it to a bitmap in the
818 * above if-statement).
820 * Instead, we can skip ahead and immediately read the flags and
823 bitmap_git
->map_pos
+= sizeof(uint32_t) + sizeof(uint8_t);
824 flags
= read_u8(bitmap_git
->map
, &bitmap_git
->map_pos
);
825 bitmap
= read_bitmap_1(bitmap_git
);
830 return store_bitmap(bitmap_git
, bitmap
, oid
, xor_bitmap
, flags
);
838 struct ewah_bitmap
*bitmap_for_commit(struct bitmap_index
*bitmap_git
,
839 struct commit
*commit
)
841 khiter_t hash_pos
= kh_get_oid_map(bitmap_git
->bitmaps
,
843 if (hash_pos
>= kh_end(bitmap_git
->bitmaps
)) {
844 struct stored_bitmap
*bitmap
= NULL
;
845 if (!bitmap_git
->table_lookup
)
848 /* this is a fairly hot codepath - no trace2_region please */
849 /* NEEDSWORK: cache misses aren't recorded */
850 bitmap
= lazy_bitmap_for_commit(bitmap_git
, commit
);
853 return lookup_stored_bitmap(bitmap
);
855 return lookup_stored_bitmap(kh_value(bitmap_git
->bitmaps
, hash_pos
));
858 static inline int bitmap_position_extended(struct bitmap_index
*bitmap_git
,
859 const struct object_id
*oid
)
861 kh_oid_pos_t
*positions
= bitmap_git
->ext_index
.positions
;
862 khiter_t pos
= kh_get_oid_pos(positions
, *oid
);
864 if (pos
< kh_end(positions
)) {
865 int bitmap_pos
= kh_value(positions
, pos
);
866 return bitmap_pos
+ bitmap_num_objects(bitmap_git
);
872 static inline int bitmap_position_packfile(struct bitmap_index
*bitmap_git
,
873 const struct object_id
*oid
)
876 off_t offset
= find_pack_entry_one(oid
->hash
, bitmap_git
->pack
);
880 if (offset_to_pack_pos(bitmap_git
->pack
, offset
, &pos
) < 0)
885 static int bitmap_position_midx(struct bitmap_index
*bitmap_git
,
886 const struct object_id
*oid
)
889 if (!bsearch_midx(oid
, bitmap_git
->midx
, &want
))
892 if (midx_to_pack_pos(bitmap_git
->midx
, want
, &got
) < 0)
897 static int bitmap_position(struct bitmap_index
*bitmap_git
,
898 const struct object_id
*oid
)
901 if (bitmap_is_midx(bitmap_git
))
902 pos
= bitmap_position_midx(bitmap_git
, oid
);
904 pos
= bitmap_position_packfile(bitmap_git
, oid
);
905 return (pos
>= 0) ? pos
: bitmap_position_extended(bitmap_git
, oid
);
908 static int ext_index_add_object(struct bitmap_index
*bitmap_git
,
909 struct object
*object
, const char *name
)
911 struct eindex
*eindex
= &bitmap_git
->ext_index
;
917 hash_pos
= kh_put_oid_pos(eindex
->positions
, object
->oid
, &hash_ret
);
919 if (eindex
->count
>= eindex
->alloc
) {
920 eindex
->alloc
= (eindex
->alloc
+ 16) * 3 / 2;
921 REALLOC_ARRAY(eindex
->objects
, eindex
->alloc
);
922 REALLOC_ARRAY(eindex
->hashes
, eindex
->alloc
);
925 bitmap_pos
= eindex
->count
;
926 eindex
->objects
[eindex
->count
] = object
;
927 eindex
->hashes
[eindex
->count
] = pack_name_hash(name
);
928 kh_value(eindex
->positions
, hash_pos
) = bitmap_pos
;
931 bitmap_pos
= kh_value(eindex
->positions
, hash_pos
);
934 return bitmap_pos
+ bitmap_num_objects(bitmap_git
);
937 struct bitmap_show_data
{
938 struct bitmap_index
*bitmap_git
;
942 static void show_object(struct object
*object
, const char *name
, void *data_
)
944 struct bitmap_show_data
*data
= data_
;
947 bitmap_pos
= bitmap_position(data
->bitmap_git
, &object
->oid
);
950 bitmap_pos
= ext_index_add_object(data
->bitmap_git
, object
,
953 bitmap_set(data
->base
, bitmap_pos
);
956 static void show_commit(struct commit
*commit
, void *data
)
960 static int add_to_include_set(struct bitmap_index
*bitmap_git
,
961 struct include_data
*data
,
962 struct commit
*commit
,
965 struct ewah_bitmap
*partial
;
967 if (data
->seen
&& bitmap_get(data
->seen
, bitmap_pos
))
970 if (bitmap_get(data
->base
, bitmap_pos
))
973 partial
= bitmap_for_commit(bitmap_git
, commit
);
975 bitmap_or_ewah(data
->base
, partial
);
979 bitmap_set(data
->base
, bitmap_pos
);
983 static int should_include(struct commit
*commit
, void *_data
)
985 struct include_data
*data
= _data
;
988 bitmap_pos
= bitmap_position(data
->bitmap_git
, &commit
->object
.oid
);
990 bitmap_pos
= ext_index_add_object(data
->bitmap_git
,
991 (struct object
*)commit
,
994 if (!add_to_include_set(data
->bitmap_git
, data
, commit
, bitmap_pos
)) {
995 struct commit_list
*parent
= commit
->parents
;
998 parent
->item
->object
.flags
|= SEEN
;
999 parent
= parent
->next
;
1008 static int should_include_obj(struct object
*obj
, void *_data
)
1010 struct include_data
*data
= _data
;
1013 bitmap_pos
= bitmap_position(data
->bitmap_git
, &obj
->oid
);
1016 if ((data
->seen
&& bitmap_get(data
->seen
, bitmap_pos
)) ||
1017 bitmap_get(data
->base
, bitmap_pos
)) {
1024 static int add_commit_to_bitmap(struct bitmap_index
*bitmap_git
,
1025 struct bitmap
**base
,
1026 struct commit
*commit
)
1028 struct ewah_bitmap
*or_with
= bitmap_for_commit(bitmap_git
, commit
);
1034 *base
= ewah_to_bitmap(or_with
);
1036 bitmap_or_ewah(*base
, or_with
);
1041 static struct bitmap
*find_objects(struct bitmap_index
*bitmap_git
,
1042 struct rev_info
*revs
,
1043 struct object_list
*roots
,
1044 struct bitmap
*seen
)
1046 struct bitmap
*base
= NULL
;
1049 struct object_list
*not_mapped
= NULL
;
1052 * Go through all the roots for the walk. The ones that have bitmaps
1053 * on the bitmap index will be `or`ed together to form an initial
1054 * global reachability analysis.
1056 * The ones without bitmaps in the index will be stored in the
1057 * `not_mapped_list` for further processing.
1060 struct object
*object
= roots
->item
;
1061 roots
= roots
->next
;
1063 if (object
->type
== OBJ_COMMIT
&&
1064 add_commit_to_bitmap(bitmap_git
, &base
, (struct commit
*)object
)) {
1065 object
->flags
|= SEEN
;
1069 object_list_insert(object
, ¬_mapped
);
1073 * Best case scenario: We found bitmaps for all the roots,
1074 * so the resulting `or` bitmap has the full reachability analysis
1082 * Let's iterate through all the roots that don't have bitmaps to
1083 * check if we can determine them to be reachable from the existing
1086 * If we cannot find them in the existing global bitmap, we'll need
1087 * to push them to an actual walk and run it until we can confirm
1088 * they are reachable
1091 struct object
*object
= roots
->item
;
1094 roots
= roots
->next
;
1095 pos
= bitmap_position(bitmap_git
, &object
->oid
);
1097 if (pos
< 0 || base
== NULL
|| !bitmap_get(base
, pos
)) {
1098 object
->flags
&= ~UNINTERESTING
;
1099 add_pending_object(revs
, object
, "");
1102 object
->flags
|= SEEN
;
1107 struct include_data incdata
;
1108 struct bitmap_show_data show_data
;
1111 base
= bitmap_new();
1113 incdata
.bitmap_git
= bitmap_git
;
1114 incdata
.base
= base
;
1115 incdata
.seen
= seen
;
1117 revs
->include_check
= should_include
;
1118 revs
->include_check_obj
= should_include_obj
;
1119 revs
->include_check_data
= &incdata
;
1121 if (prepare_revision_walk(revs
))
1122 die(_("revision walk setup failed"));
1124 show_data
.bitmap_git
= bitmap_git
;
1125 show_data
.base
= base
;
1127 traverse_commit_list(revs
,
1128 show_commit
, show_object
,
1131 revs
->include_check
= NULL
;
1132 revs
->include_check_obj
= NULL
;
1133 revs
->include_check_data
= NULL
;
1139 static void show_extended_objects(struct bitmap_index
*bitmap_git
,
1140 struct rev_info
*revs
,
1141 show_reachable_fn show_reach
)
1143 struct bitmap
*objects
= bitmap_git
->result
;
1144 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1147 for (i
= 0; i
< eindex
->count
; ++i
) {
1150 if (!bitmap_get(objects
, bitmap_num_objects(bitmap_git
) + i
))
1153 obj
= eindex
->objects
[i
];
1154 if ((obj
->type
== OBJ_BLOB
&& !revs
->blob_objects
) ||
1155 (obj
->type
== OBJ_TREE
&& !revs
->tree_objects
) ||
1156 (obj
->type
== OBJ_TAG
&& !revs
->tag_objects
))
1159 show_reach(&obj
->oid
, obj
->type
, 0, eindex
->hashes
[i
], NULL
, 0);
1163 static void init_type_iterator(struct ewah_iterator
*it
,
1164 struct bitmap_index
*bitmap_git
,
1165 enum object_type type
)
1169 ewah_iterator_init(it
, bitmap_git
->commits
);
1173 ewah_iterator_init(it
, bitmap_git
->trees
);
1177 ewah_iterator_init(it
, bitmap_git
->blobs
);
1181 ewah_iterator_init(it
, bitmap_git
->tags
);
1185 BUG("object type %d not stored by bitmap type index", type
);
1190 static void show_objects_for_type(
1191 struct bitmap_index
*bitmap_git
,
1192 enum object_type object_type
,
1193 show_reachable_fn show_reach
)
1198 struct ewah_iterator it
;
1201 struct bitmap
*objects
= bitmap_git
->result
;
1203 init_type_iterator(&it
, bitmap_git
, object_type
);
1205 for (i
= 0; i
< objects
->word_alloc
&&
1206 ewah_iterator_next(&filter
, &it
); i
++) {
1207 eword_t word
= objects
->words
[i
] & filter
;
1208 size_t pos
= (i
* BITS_IN_EWORD
);
1213 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
1214 struct packed_git
*pack
;
1215 struct object_id oid
;
1216 uint32_t hash
= 0, index_pos
;
1219 if ((word
>> offset
) == 0)
1222 offset
+= ewah_bit_ctz64(word
>> offset
);
1224 if (bitmap_is_midx(bitmap_git
)) {
1225 struct multi_pack_index
*m
= bitmap_git
->midx
;
1228 index_pos
= pack_pos_to_midx(m
, pos
+ offset
);
1229 ofs
= nth_midxed_offset(m
, index_pos
);
1230 nth_midxed_object_oid(&oid
, m
, index_pos
);
1232 pack_id
= nth_midxed_pack_int_id(m
, index_pos
);
1233 pack
= bitmap_git
->midx
->packs
[pack_id
];
1235 index_pos
= pack_pos_to_index(bitmap_git
->pack
, pos
+ offset
);
1236 ofs
= pack_pos_to_offset(bitmap_git
->pack
, pos
+ offset
);
1237 nth_bitmap_object_oid(bitmap_git
, &oid
, index_pos
);
1239 pack
= bitmap_git
->pack
;
1242 if (bitmap_git
->hashes
)
1243 hash
= get_be32(bitmap_git
->hashes
+ index_pos
);
1245 show_reach(&oid
, object_type
, 0, hash
, pack
, ofs
);
1250 static int in_bitmapped_pack(struct bitmap_index
*bitmap_git
,
1251 struct object_list
*roots
)
1254 struct object
*object
= roots
->item
;
1255 roots
= roots
->next
;
1257 if (bitmap_is_midx(bitmap_git
)) {
1258 if (bsearch_midx(&object
->oid
, bitmap_git
->midx
, NULL
))
1261 if (find_pack_entry_one(object
->oid
.hash
, bitmap_git
->pack
) > 0)
1269 static struct bitmap
*find_tip_objects(struct bitmap_index
*bitmap_git
,
1270 struct object_list
*tip_objects
,
1271 enum object_type type
)
1273 struct bitmap
*result
= bitmap_new();
1274 struct object_list
*p
;
1276 for (p
= tip_objects
; p
; p
= p
->next
) {
1279 if (p
->item
->type
!= type
)
1282 pos
= bitmap_position(bitmap_git
, &p
->item
->oid
);
1286 bitmap_set(result
, pos
);
1292 static void filter_bitmap_exclude_type(struct bitmap_index
*bitmap_git
,
1293 struct object_list
*tip_objects
,
1294 struct bitmap
*to_filter
,
1295 enum object_type type
)
1297 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1298 struct bitmap
*tips
;
1299 struct ewah_iterator it
;
1304 * The non-bitmap version of this filter never removes
1305 * objects which the other side specifically asked for,
1306 * so we must match that behavior.
1308 tips
= find_tip_objects(bitmap_git
, tip_objects
, type
);
1311 * We can use the type-level bitmap for 'type' to work in whole
1312 * words for the objects that are actually in the bitmapped
1315 for (i
= 0, init_type_iterator(&it
, bitmap_git
, type
);
1316 i
< to_filter
->word_alloc
&& ewah_iterator_next(&mask
, &it
);
1318 if (i
< tips
->word_alloc
)
1319 mask
&= ~tips
->words
[i
];
1320 to_filter
->words
[i
] &= ~mask
;
1324 * Clear any objects that weren't in the packfile (and so would
1325 * not have been caught by the loop above. We'll have to check
1326 * them individually.
1328 for (i
= 0; i
< eindex
->count
; i
++) {
1329 uint32_t pos
= i
+ bitmap_num_objects(bitmap_git
);
1330 if (eindex
->objects
[i
]->type
== type
&&
1331 bitmap_get(to_filter
, pos
) &&
1332 !bitmap_get(tips
, pos
))
1333 bitmap_unset(to_filter
, pos
);
1339 static void filter_bitmap_blob_none(struct bitmap_index
*bitmap_git
,
1340 struct object_list
*tip_objects
,
1341 struct bitmap
*to_filter
)
1343 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
,
1347 static unsigned long get_size_by_pos(struct bitmap_index
*bitmap_git
,
1351 struct object_info oi
= OBJECT_INFO_INIT
;
1355 if (pos
< bitmap_num_objects(bitmap_git
)) {
1356 struct packed_git
*pack
;
1359 if (bitmap_is_midx(bitmap_git
)) {
1360 uint32_t midx_pos
= pack_pos_to_midx(bitmap_git
->midx
, pos
);
1361 uint32_t pack_id
= nth_midxed_pack_int_id(bitmap_git
->midx
, midx_pos
);
1363 pack
= bitmap_git
->midx
->packs
[pack_id
];
1364 ofs
= nth_midxed_offset(bitmap_git
->midx
, midx_pos
);
1366 pack
= bitmap_git
->pack
;
1367 ofs
= pack_pos_to_offset(pack
, pos
);
1370 if (packed_object_info(the_repository
, pack
, ofs
, &oi
) < 0) {
1371 struct object_id oid
;
1372 nth_bitmap_object_oid(bitmap_git
, &oid
,
1373 pack_pos_to_index(pack
, pos
));
1374 die(_("unable to get size of %s"), oid_to_hex(&oid
));
1377 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1378 struct object
*obj
= eindex
->objects
[pos
- bitmap_num_objects(bitmap_git
)];
1379 if (oid_object_info_extended(the_repository
, &obj
->oid
, &oi
, 0) < 0)
1380 die(_("unable to get size of %s"), oid_to_hex(&obj
->oid
));
1386 static void filter_bitmap_blob_limit(struct bitmap_index
*bitmap_git
,
1387 struct object_list
*tip_objects
,
1388 struct bitmap
*to_filter
,
1389 unsigned long limit
)
1391 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1392 struct bitmap
*tips
;
1393 struct ewah_iterator it
;
1397 tips
= find_tip_objects(bitmap_git
, tip_objects
, OBJ_BLOB
);
1399 for (i
= 0, init_type_iterator(&it
, bitmap_git
, OBJ_BLOB
);
1400 i
< to_filter
->word_alloc
&& ewah_iterator_next(&mask
, &it
);
1402 eword_t word
= to_filter
->words
[i
] & mask
;
1405 for (offset
= 0; offset
< BITS_IN_EWORD
; offset
++) {
1408 if ((word
>> offset
) == 0)
1410 offset
+= ewah_bit_ctz64(word
>> offset
);
1411 pos
= i
* BITS_IN_EWORD
+ offset
;
1413 if (!bitmap_get(tips
, pos
) &&
1414 get_size_by_pos(bitmap_git
, pos
) >= limit
)
1415 bitmap_unset(to_filter
, pos
);
1419 for (i
= 0; i
< eindex
->count
; i
++) {
1420 uint32_t pos
= i
+ bitmap_num_objects(bitmap_git
);
1421 if (eindex
->objects
[i
]->type
== OBJ_BLOB
&&
1422 bitmap_get(to_filter
, pos
) &&
1423 !bitmap_get(tips
, pos
) &&
1424 get_size_by_pos(bitmap_git
, pos
) >= limit
)
1425 bitmap_unset(to_filter
, pos
);
1431 static void filter_bitmap_tree_depth(struct bitmap_index
*bitmap_git
,
1432 struct object_list
*tip_objects
,
1433 struct bitmap
*to_filter
,
1434 unsigned long limit
)
1437 BUG("filter_bitmap_tree_depth given non-zero limit");
1439 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
,
1441 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
,
1445 static void filter_bitmap_object_type(struct bitmap_index
*bitmap_git
,
1446 struct object_list
*tip_objects
,
1447 struct bitmap
*to_filter
,
1448 enum object_type object_type
)
1450 if (object_type
< OBJ_COMMIT
|| object_type
> OBJ_TAG
)
1451 BUG("filter_bitmap_object_type given invalid object");
1453 if (object_type
!= OBJ_TAG
)
1454 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_TAG
);
1455 if (object_type
!= OBJ_COMMIT
)
1456 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_COMMIT
);
1457 if (object_type
!= OBJ_TREE
)
1458 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_TREE
);
1459 if (object_type
!= OBJ_BLOB
)
1460 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_BLOB
);
1463 static int filter_bitmap(struct bitmap_index
*bitmap_git
,
1464 struct object_list
*tip_objects
,
1465 struct bitmap
*to_filter
,
1466 struct list_objects_filter_options
*filter
)
1468 if (!filter
|| filter
->choice
== LOFC_DISABLED
)
1471 if (filter
->choice
== LOFC_BLOB_NONE
) {
1473 filter_bitmap_blob_none(bitmap_git
, tip_objects
,
1478 if (filter
->choice
== LOFC_BLOB_LIMIT
) {
1480 filter_bitmap_blob_limit(bitmap_git
, tip_objects
,
1482 filter
->blob_limit_value
);
1486 if (filter
->choice
== LOFC_TREE_DEPTH
&&
1487 filter
->tree_exclude_depth
== 0) {
1489 filter_bitmap_tree_depth(bitmap_git
, tip_objects
,
1491 filter
->tree_exclude_depth
);
1495 if (filter
->choice
== LOFC_OBJECT_TYPE
) {
1497 filter_bitmap_object_type(bitmap_git
, tip_objects
,
1499 filter
->object_type
);
1503 if (filter
->choice
== LOFC_COMBINE
) {
1505 for (i
= 0; i
< filter
->sub_nr
; i
++) {
1506 if (filter_bitmap(bitmap_git
, tip_objects
, to_filter
,
1507 &filter
->sub
[i
]) < 0)
1513 /* filter choice not handled */
1517 static int can_filter_bitmap(struct list_objects_filter_options
*filter
)
1519 return !filter_bitmap(NULL
, NULL
, NULL
, filter
);
1522 struct bitmap_index
*prepare_bitmap_walk(struct rev_info
*revs
,
1523 int filter_provided_objects
)
1527 struct object_list
*wants
= NULL
;
1528 struct object_list
*haves
= NULL
;
1530 struct bitmap
*wants_bitmap
= NULL
;
1531 struct bitmap
*haves_bitmap
= NULL
;
1533 struct bitmap_index
*bitmap_git
;
1536 * We can't do pathspec limiting with bitmaps, because we don't know
1537 * which commits are associated with which object changes (let alone
1538 * even which objects are associated with which paths).
1543 if (!can_filter_bitmap(&revs
->filter
))
1546 /* try to open a bitmapped pack, but don't parse it yet
1547 * because we may not need to use it */
1548 CALLOC_ARRAY(bitmap_git
, 1);
1549 if (open_bitmap(revs
->repo
, bitmap_git
) < 0)
1552 for (i
= 0; i
< revs
->pending
.nr
; ++i
) {
1553 struct object
*object
= revs
->pending
.objects
[i
].item
;
1555 if (object
->type
== OBJ_NONE
)
1556 parse_object_or_die(&object
->oid
, NULL
);
1558 while (object
->type
== OBJ_TAG
) {
1559 struct tag
*tag
= (struct tag
*) object
;
1561 if (object
->flags
& UNINTERESTING
)
1562 object_list_insert(object
, &haves
);
1564 object_list_insert(object
, &wants
);
1566 object
= parse_object_or_die(get_tagged_oid(tag
), NULL
);
1567 object
->flags
|= (tag
->object
.flags
& UNINTERESTING
);
1570 if (object
->flags
& UNINTERESTING
)
1571 object_list_insert(object
, &haves
);
1573 object_list_insert(object
, &wants
);
1577 * if we have a HAVES list, but none of those haves is contained
1578 * in the packfile that has a bitmap, we don't have anything to
1581 if (haves
&& !in_bitmapped_pack(bitmap_git
, haves
))
1584 /* if we don't want anything, we're done here */
1589 * now we're going to use bitmaps, so load the actual bitmap entries
1590 * from disk. this is the point of no return; after this the rev_list
1591 * becomes invalidated and we must perform the revwalk through bitmaps
1593 if (load_bitmap(bitmap_git
) < 0)
1596 object_array_clear(&revs
->pending
);
1599 revs
->ignore_missing_links
= 1;
1600 haves_bitmap
= find_objects(bitmap_git
, revs
, haves
, NULL
);
1601 reset_revision_walk();
1602 revs
->ignore_missing_links
= 0;
1605 BUG("failed to perform bitmap walk");
1608 wants_bitmap
= find_objects(bitmap_git
, revs
, wants
, haves_bitmap
);
1611 BUG("failed to perform bitmap walk");
1614 bitmap_and_not(wants_bitmap
, haves_bitmap
);
1616 filter_bitmap(bitmap_git
,
1617 (revs
->filter
.choice
&& filter_provided_objects
) ? NULL
: wants
,
1621 bitmap_git
->result
= wants_bitmap
;
1622 bitmap_git
->haves
= haves_bitmap
;
1624 object_list_free(&wants
);
1625 object_list_free(&haves
);
1630 free_bitmap_index(bitmap_git
);
1631 object_list_free(&wants
);
1632 object_list_free(&haves
);
1637 * -1 means "stop trying further objects"; 0 means we may or may not have
1638 * reused, but you can keep feeding bits.
1640 static int try_partial_reuse(struct packed_git
*pack
,
1642 struct bitmap
*reuse
,
1643 struct pack_window
**w_curs
)
1645 off_t offset
, delta_obj_offset
;
1646 enum object_type type
;
1650 * try_partial_reuse() is called either on (a) objects in the
1651 * bitmapped pack (in the case of a single-pack bitmap) or (b)
1652 * objects in the preferred pack of a multi-pack bitmap.
1653 * Importantly, the latter can pretend as if only a single pack
1656 * - The first pack->num_objects bits of a MIDX bitmap are
1657 * reserved for the preferred pack, and
1659 * - Ties due to duplicate objects are always resolved in
1660 * favor of the preferred pack.
1662 * Therefore we do not need to ever ask the MIDX for its copy of
1663 * an object by OID, since it will always select it from the
1664 * preferred pack. Likewise, the selected copy of the base
1665 * object for any deltas will reside in the same pack.
1667 * This means that we can reuse pos when looking up the bit in
1668 * the reuse bitmap, too, since bits corresponding to the
1669 * preferred pack precede all bits from other packs.
1672 if (pos
>= pack
->num_objects
)
1673 return -1; /* not actually in the pack or MIDX preferred pack */
1675 offset
= delta_obj_offset
= pack_pos_to_offset(pack
, pos
);
1676 type
= unpack_object_header(pack
, w_curs
, &offset
, &size
);
1678 return -1; /* broken packfile, punt */
1680 if (type
== OBJ_REF_DELTA
|| type
== OBJ_OFS_DELTA
) {
1685 * Find the position of the base object so we can look it up
1686 * in our bitmaps. If we can't come up with an offset, or if
1687 * that offset is not in the revidx, the pack is corrupt.
1688 * There's nothing we can do, so just punt on this object,
1689 * and the normal slow path will complain about it in
1692 base_offset
= get_delta_base(pack
, w_curs
, &offset
, type
,
1696 if (offset_to_pack_pos(pack
, base_offset
, &base_pos
) < 0)
1700 * We assume delta dependencies always point backwards. This
1701 * lets us do a single pass, and is basically always true
1702 * due to the way OFS_DELTAs work. You would not typically
1703 * find REF_DELTA in a bitmapped pack, since we only bitmap
1704 * packs we write fresh, and OFS_DELTA is the default). But
1705 * let's double check to make sure the pack wasn't written with
1708 if (base_pos
>= pos
)
1712 * And finally, if we're not sending the base as part of our
1713 * reuse chunk, then don't send this object either. The base
1714 * would come after us, along with other objects not
1715 * necessarily in the pack, which means we'd need to convert
1716 * to REF_DELTA on the fly. Better to just let the normal
1717 * object_entry code path handle it.
1719 if (!bitmap_get(reuse
, base_pos
))
1724 * If we got here, then the object is OK to reuse. Mark it.
1726 bitmap_set(reuse
, pos
);
1730 uint32_t midx_preferred_pack(struct bitmap_index
*bitmap_git
)
1732 struct multi_pack_index
*m
= bitmap_git
->midx
;
1734 BUG("midx_preferred_pack: requires non-empty MIDX");
1735 return nth_midxed_pack_int_id(m
, pack_pos_to_midx(bitmap_git
->midx
, 0));
1738 int reuse_partial_packfile_from_bitmap(struct bitmap_index
*bitmap_git
,
1739 struct packed_git
**packfile_out
,
1741 struct bitmap
**reuse_out
)
1743 struct packed_git
*pack
;
1744 struct bitmap
*result
= bitmap_git
->result
;
1745 struct bitmap
*reuse
;
1746 struct pack_window
*w_curs
= NULL
;
1749 uint32_t objects_nr
;
1753 load_reverse_index(bitmap_git
);
1755 if (bitmap_is_midx(bitmap_git
))
1756 pack
= bitmap_git
->midx
->packs
[midx_preferred_pack(bitmap_git
)];
1758 pack
= bitmap_git
->pack
;
1759 objects_nr
= pack
->num_objects
;
1761 while (i
< result
->word_alloc
&& result
->words
[i
] == (eword_t
)~0)
1765 * Don't mark objects not in the packfile or preferred pack. This bitmap
1766 * marks objects eligible for reuse, but the pack-reuse code only
1767 * understands how to reuse a single pack. Since the preferred pack is
1768 * guaranteed to have all bases for its deltas (in a multi-pack bitmap),
1769 * we use it instead of another pack. In single-pack bitmaps, the choice
1772 if (i
> objects_nr
/ BITS_IN_EWORD
)
1773 i
= objects_nr
/ BITS_IN_EWORD
;
1775 reuse
= bitmap_word_alloc(i
);
1776 memset(reuse
->words
, 0xFF, i
* sizeof(eword_t
));
1778 for (; i
< result
->word_alloc
; ++i
) {
1779 eword_t word
= result
->words
[i
];
1780 size_t pos
= (i
* BITS_IN_EWORD
);
1782 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
1783 if ((word
>> offset
) == 0)
1786 offset
+= ewah_bit_ctz64(word
>> offset
);
1787 if (try_partial_reuse(pack
, pos
+ offset
,
1788 reuse
, &w_curs
) < 0) {
1790 * try_partial_reuse indicated we couldn't reuse
1791 * any bits, so there is no point in trying more
1792 * bits in the current word, or any other words
1795 * Jump out of both loops to avoid future
1796 * unnecessary calls to try_partial_reuse.
1804 unuse_pack(&w_curs
);
1806 *entries
= bitmap_popcount(reuse
);
1813 * Drop any reused objects from the result, since they will not
1814 * need to be handled separately.
1816 bitmap_and_not(result
, reuse
);
1817 *packfile_out
= pack
;
1822 int bitmap_walk_contains(struct bitmap_index
*bitmap_git
,
1823 struct bitmap
*bitmap
, const struct object_id
*oid
)
1830 idx
= bitmap_position(bitmap_git
, oid
);
1831 return idx
>= 0 && bitmap_get(bitmap
, idx
);
1834 void traverse_bitmap_commit_list(struct bitmap_index
*bitmap_git
,
1835 struct rev_info
*revs
,
1836 show_reachable_fn show_reachable
)
1838 assert(bitmap_git
->result
);
1840 show_objects_for_type(bitmap_git
, OBJ_COMMIT
, show_reachable
);
1841 if (revs
->tree_objects
)
1842 show_objects_for_type(bitmap_git
, OBJ_TREE
, show_reachable
);
1843 if (revs
->blob_objects
)
1844 show_objects_for_type(bitmap_git
, OBJ_BLOB
, show_reachable
);
1845 if (revs
->tag_objects
)
1846 show_objects_for_type(bitmap_git
, OBJ_TAG
, show_reachable
);
1848 show_extended_objects(bitmap_git
, revs
, show_reachable
);
1851 static uint32_t count_object_type(struct bitmap_index
*bitmap_git
,
1852 enum object_type type
)
1854 struct bitmap
*objects
= bitmap_git
->result
;
1855 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1857 uint32_t i
= 0, count
= 0;
1858 struct ewah_iterator it
;
1861 init_type_iterator(&it
, bitmap_git
, type
);
1863 while (i
< objects
->word_alloc
&& ewah_iterator_next(&filter
, &it
)) {
1864 eword_t word
= objects
->words
[i
++] & filter
;
1865 count
+= ewah_bit_popcount64(word
);
1868 for (i
= 0; i
< eindex
->count
; ++i
) {
1869 if (eindex
->objects
[i
]->type
== type
&&
1870 bitmap_get(objects
, bitmap_num_objects(bitmap_git
) + i
))
1877 void count_bitmap_commit_list(struct bitmap_index
*bitmap_git
,
1878 uint32_t *commits
, uint32_t *trees
,
1879 uint32_t *blobs
, uint32_t *tags
)
1881 assert(bitmap_git
->result
);
1884 *commits
= count_object_type(bitmap_git
, OBJ_COMMIT
);
1887 *trees
= count_object_type(bitmap_git
, OBJ_TREE
);
1890 *blobs
= count_object_type(bitmap_git
, OBJ_BLOB
);
1893 *tags
= count_object_type(bitmap_git
, OBJ_TAG
);
1896 struct bitmap_test_data
{
1897 struct bitmap_index
*bitmap_git
;
1898 struct bitmap
*base
;
1899 struct bitmap
*commits
;
1900 struct bitmap
*trees
;
1901 struct bitmap
*blobs
;
1902 struct bitmap
*tags
;
1903 struct progress
*prg
;
1907 static void test_bitmap_type(struct bitmap_test_data
*tdata
,
1908 struct object
*obj
, int pos
)
1910 enum object_type bitmap_type
= OBJ_NONE
;
1913 if (bitmap_get(tdata
->commits
, pos
)) {
1914 bitmap_type
= OBJ_COMMIT
;
1917 if (bitmap_get(tdata
->trees
, pos
)) {
1918 bitmap_type
= OBJ_TREE
;
1921 if (bitmap_get(tdata
->blobs
, pos
)) {
1922 bitmap_type
= OBJ_BLOB
;
1925 if (bitmap_get(tdata
->tags
, pos
)) {
1926 bitmap_type
= OBJ_TAG
;
1930 if (bitmap_type
== OBJ_NONE
)
1931 die(_("object '%s' not found in type bitmaps"),
1932 oid_to_hex(&obj
->oid
));
1935 die(_("object '%s' does not have a unique type"),
1936 oid_to_hex(&obj
->oid
));
1938 if (bitmap_type
!= obj
->type
)
1939 die(_("object '%s': real type '%s', expected: '%s'"),
1940 oid_to_hex(&obj
->oid
),
1941 type_name(obj
->type
),
1942 type_name(bitmap_type
));
1945 static void test_show_object(struct object
*object
, const char *name
,
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
))