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"
18 #include "object-file.h"
19 #include "object-store-ll.h"
20 #include "list-objects-filter-options.h"
25 * An entry on the bitmap index, representing the bitmap for a given
28 struct stored_bitmap
{
30 struct ewah_bitmap
*root
;
31 struct stored_bitmap
*xor;
36 * The active bitmap index for a repository. By design, repositories only have
37 * a single bitmap index available (the index for the biggest packfile in
38 * the repository), since bitmap indexes need full closure.
40 * If there is more than one bitmap index available (e.g. because of alternates),
41 * the active bitmap index is the largest one.
45 * The pack or multi-pack index (MIDX) that this bitmap index belongs
48 * Exactly one of these must be non-NULL; this specifies the object
49 * order used to interpret this bitmap.
51 struct packed_git
*pack
;
52 struct multi_pack_index
*midx
;
54 /* mmapped buffer of the whole bitmap index */
56 size_t map_size
; /* size of the mmaped buffer */
57 size_t map_pos
; /* current position when loading the index */
62 * Each bitmap marks which objects in the packfile are of the given
63 * type. This provides type information when yielding the objects from
64 * the packfile during a walk, which allows for better delta bases.
66 struct ewah_bitmap
*commits
;
67 struct ewah_bitmap
*trees
;
68 struct ewah_bitmap
*blobs
;
69 struct ewah_bitmap
*tags
;
71 /* Map from object ID -> `stored_bitmap` for all the bitmapped commits */
72 kh_oid_map_t
*bitmaps
;
74 /* Number of bitmapped commits */
77 /* If not NULL, this is a name-hash cache pointing into map. */
80 /* The checksum of the packfile or MIDX; points into map. */
81 const unsigned char *checksum
;
84 * If not NULL, this point into the commit table extension
85 * (within the memory mapped region `map`).
87 unsigned char *table_lookup
;
92 * When trying to perform bitmap operations with objects that are not
93 * packed in `pack`, these objects are added to this "fake index" and
94 * are assumed to appear at the end of the packfile for all operations
97 struct object
**objects
;
99 uint32_t count
, alloc
;
100 kh_oid_pos_t
*positions
;
103 /* Bitmap result of the last performed walk */
104 struct bitmap
*result
;
106 /* "have" bitmap from the last performed walk */
107 struct bitmap
*haves
;
109 /* Version of the bitmap index */
110 unsigned int version
;
113 static struct ewah_bitmap
*lookup_stored_bitmap(struct stored_bitmap
*st
)
115 struct ewah_bitmap
*parent
;
116 struct ewah_bitmap
*composed
;
121 composed
= ewah_pool_new();
122 parent
= lookup_stored_bitmap(st
->xor);
123 ewah_xor(st
->root
, parent
, composed
);
125 ewah_pool_free(st
->root
);
133 * Read a bitmap from the current read position on the mmaped
134 * index, and increase the read position accordingly
136 static struct ewah_bitmap
*read_bitmap_1(struct bitmap_index
*index
)
138 struct ewah_bitmap
*b
= ewah_pool_new();
140 ssize_t bitmap_size
= ewah_read_mmap(b
,
141 index
->map
+ index
->map_pos
,
142 index
->map_size
- index
->map_pos
);
144 if (bitmap_size
< 0) {
145 error(_("failed to load bitmap index (corrupted?)"));
150 index
->map_pos
+= bitmap_size
;
154 static uint32_t bitmap_num_objects(struct bitmap_index
*index
)
157 return index
->midx
->num_objects
;
158 return index
->pack
->num_objects
;
161 static int load_bitmap_header(struct bitmap_index
*index
)
163 struct bitmap_disk_header
*header
= (void *)index
->map
;
164 size_t header_size
= sizeof(*header
) - GIT_MAX_RAWSZ
+ the_hash_algo
->rawsz
;
166 if (index
->map_size
< header_size
+ the_hash_algo
->rawsz
)
167 return error(_("corrupted bitmap index (too small)"));
169 if (memcmp(header
->magic
, BITMAP_IDX_SIGNATURE
, sizeof(BITMAP_IDX_SIGNATURE
)) != 0)
170 return error(_("corrupted bitmap index file (wrong header)"));
172 index
->version
= ntohs(header
->version
);
173 if (index
->version
!= 1)
174 return error(_("unsupported version '%d' for bitmap index file"), index
->version
);
176 /* Parse known bitmap format options */
178 uint32_t flags
= ntohs(header
->options
);
179 size_t cache_size
= st_mult(bitmap_num_objects(index
), sizeof(uint32_t));
180 unsigned char *index_end
= index
->map
+ index
->map_size
- the_hash_algo
->rawsz
;
182 if ((flags
& BITMAP_OPT_FULL_DAG
) == 0)
183 BUG("unsupported options for bitmap index file "
184 "(Git requires BITMAP_OPT_FULL_DAG)");
186 if (flags
& BITMAP_OPT_HASH_CACHE
) {
187 if (cache_size
> index_end
- index
->map
- header_size
)
188 return error(_("corrupted bitmap index file (too short to fit hash cache)"));
189 index
->hashes
= (void *)(index_end
- cache_size
);
190 index_end
-= cache_size
;
193 if (flags
& BITMAP_OPT_LOOKUP_TABLE
) {
194 size_t table_size
= st_mult(ntohl(header
->entry_count
),
195 BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH
);
196 if (table_size
> index_end
- index
->map
- header_size
)
197 return error(_("corrupted bitmap index file (too short to fit lookup table)"));
198 if (git_env_bool("GIT_TEST_READ_COMMIT_TABLE", 1))
199 index
->table_lookup
= (void *)(index_end
- table_size
);
200 index_end
-= table_size
;
204 index
->entry_count
= ntohl(header
->entry_count
);
205 index
->checksum
= header
->checksum
;
206 index
->map_pos
+= header_size
;
210 static struct stored_bitmap
*store_bitmap(struct bitmap_index
*index
,
211 struct ewah_bitmap
*root
,
212 const struct object_id
*oid
,
213 struct stored_bitmap
*xor_with
,
216 struct stored_bitmap
*stored
;
220 stored
= xmalloc(sizeof(struct stored_bitmap
));
222 stored
->xor = xor_with
;
223 stored
->flags
= flags
;
224 oidcpy(&stored
->oid
, oid
);
226 hash_pos
= kh_put_oid_map(index
->bitmaps
, stored
->oid
, &ret
);
229 * A 0 return code means the insertion succeeded with no changes,
230 * because the SHA1 already existed on the map. This is bad, there
231 * shouldn't be duplicated commits in the index.
234 error(_("duplicate entry in bitmap index: '%s'"), oid_to_hex(oid
));
238 kh_value(index
->bitmaps
, hash_pos
) = stored
;
242 static inline uint32_t read_be32(const unsigned char *buffer
, size_t *pos
)
244 uint32_t result
= get_be32(buffer
+ *pos
);
245 (*pos
) += sizeof(result
);
249 static inline uint8_t read_u8(const unsigned char *buffer
, size_t *pos
)
251 return buffer
[(*pos
)++];
254 #define MAX_XOR_OFFSET 160
256 static int nth_bitmap_object_oid(struct bitmap_index
*index
,
257 struct object_id
*oid
,
261 return nth_midxed_object_oid(oid
, index
->midx
, n
) ? 0 : -1;
262 return nth_packed_object_id(oid
, index
->pack
, n
);
265 static int load_bitmap_entries_v1(struct bitmap_index
*index
)
268 struct stored_bitmap
*recent_bitmaps
[MAX_XOR_OFFSET
] = { NULL
};
270 for (i
= 0; i
< index
->entry_count
; ++i
) {
271 int xor_offset
, flags
;
272 struct ewah_bitmap
*bitmap
= NULL
;
273 struct stored_bitmap
*xor_bitmap
= NULL
;
274 uint32_t commit_idx_pos
;
275 struct object_id oid
;
277 if (index
->map_size
- index
->map_pos
< 6)
278 return error(_("corrupt ewah bitmap: truncated header for entry %d"), i
);
280 commit_idx_pos
= read_be32(index
->map
, &index
->map_pos
);
281 xor_offset
= read_u8(index
->map
, &index
->map_pos
);
282 flags
= read_u8(index
->map
, &index
->map_pos
);
284 if (nth_bitmap_object_oid(index
, &oid
, commit_idx_pos
) < 0)
285 return error(_("corrupt ewah bitmap: commit index %u out of range"),
286 (unsigned)commit_idx_pos
);
288 bitmap
= read_bitmap_1(index
);
292 if (xor_offset
> MAX_XOR_OFFSET
|| xor_offset
> i
)
293 return error(_("corrupted bitmap pack index"));
295 if (xor_offset
> 0) {
296 xor_bitmap
= recent_bitmaps
[(i
- xor_offset
) % MAX_XOR_OFFSET
];
299 return error(_("invalid XOR offset in bitmap pack index"));
302 recent_bitmaps
[i
% MAX_XOR_OFFSET
] = store_bitmap(
303 index
, bitmap
, &oid
, xor_bitmap
, flags
);
309 char *midx_bitmap_filename(struct multi_pack_index
*midx
)
311 struct strbuf buf
= STRBUF_INIT
;
312 get_midx_filename_ext(&buf
, midx
->object_dir
, get_midx_checksum(midx
),
315 return strbuf_detach(&buf
, NULL
);
318 char *pack_bitmap_filename(struct packed_git
*p
)
322 if (!strip_suffix(p
->pack_name
, ".pack", &len
))
323 BUG("pack_name does not end in .pack");
324 return xstrfmt("%.*s.bitmap", (int)len
, p
->pack_name
);
327 static int open_midx_bitmap_1(struct bitmap_index
*bitmap_git
,
328 struct multi_pack_index
*midx
)
331 char *bitmap_name
= midx_bitmap_filename(midx
);
332 int fd
= git_open(bitmap_name
);
333 uint32_t i
, preferred_pack
;
334 struct packed_git
*preferred
;
338 warning_errno("cannot open '%s'", bitmap_name
);
344 if (fstat(fd
, &st
)) {
345 error_errno(_("cannot fstat bitmap file"));
350 if (bitmap_git
->pack
|| bitmap_git
->midx
) {
351 struct strbuf buf
= STRBUF_INIT
;
352 get_midx_filename(&buf
, midx
->object_dir
);
353 trace2_data_string("bitmap", the_repository
,
354 "ignoring extra midx bitmap file", buf
.buf
);
356 strbuf_release(&buf
);
360 bitmap_git
->midx
= midx
;
361 bitmap_git
->map_size
= xsize_t(st
.st_size
);
362 bitmap_git
->map_pos
= 0;
363 bitmap_git
->map
= xmmap(NULL
, bitmap_git
->map_size
, PROT_READ
,
367 if (load_bitmap_header(bitmap_git
) < 0)
370 if (!hasheq(get_midx_checksum(bitmap_git
->midx
), bitmap_git
->checksum
)) {
371 error(_("checksum doesn't match in MIDX and bitmap"));
375 if (load_midx_revindex(bitmap_git
->midx
)) {
376 warning(_("multi-pack bitmap is missing required reverse index"));
380 for (i
= 0; i
< bitmap_git
->midx
->num_packs
; i
++) {
381 if (prepare_midx_pack(the_repository
, bitmap_git
->midx
, i
)) {
382 warning(_("could not open pack %s"),
383 bitmap_git
->midx
->pack_names
[i
]);
388 if (midx_preferred_pack(bitmap_git
->midx
, &preferred_pack
) < 0) {
389 warning(_("could not determine MIDX preferred pack"));
393 preferred
= bitmap_git
->midx
->packs
[preferred_pack
];
394 if (!is_pack_valid(preferred
)) {
395 warning(_("preferred pack (%s) is invalid"),
396 preferred
->pack_name
);
403 munmap(bitmap_git
->map
, bitmap_git
->map_size
);
404 bitmap_git
->map_size
= 0;
405 bitmap_git
->map_pos
= 0;
406 bitmap_git
->map
= NULL
;
407 bitmap_git
->midx
= NULL
;
411 static int open_pack_bitmap_1(struct bitmap_index
*bitmap_git
, struct packed_git
*packfile
)
417 bitmap_name
= pack_bitmap_filename(packfile
);
418 fd
= git_open(bitmap_name
);
422 warning_errno("cannot open '%s'", bitmap_name
);
428 if (fstat(fd
, &st
)) {
429 error_errno(_("cannot fstat bitmap file"));
434 if (bitmap_git
->pack
|| bitmap_git
->midx
) {
435 trace2_data_string("bitmap", the_repository
,
436 "ignoring extra bitmap file", packfile
->pack_name
);
441 if (!is_pack_valid(packfile
)) {
446 bitmap_git
->pack
= packfile
;
447 bitmap_git
->map_size
= xsize_t(st
.st_size
);
448 bitmap_git
->map
= xmmap(NULL
, bitmap_git
->map_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
449 bitmap_git
->map_pos
= 0;
452 if (load_bitmap_header(bitmap_git
) < 0) {
453 munmap(bitmap_git
->map
, bitmap_git
->map_size
);
454 bitmap_git
->map
= NULL
;
455 bitmap_git
->map_size
= 0;
456 bitmap_git
->map_pos
= 0;
457 bitmap_git
->pack
= NULL
;
461 trace2_data_string("bitmap", the_repository
, "opened bitmap file",
462 packfile
->pack_name
);
466 static int load_reverse_index(struct repository
*r
, struct bitmap_index
*bitmap_git
)
468 if (bitmap_is_midx(bitmap_git
)) {
473 * The multi-pack-index's .rev file is already loaded via
474 * open_pack_bitmap_1().
476 * But we still need to open the individual pack .rev files,
477 * since we will need to make use of them in pack-objects.
479 for (i
= 0; i
< bitmap_git
->midx
->num_packs
; i
++) {
480 ret
= load_pack_revindex(r
, bitmap_git
->midx
->packs
[i
]);
486 return load_pack_revindex(r
, bitmap_git
->pack
);
489 static int load_bitmap(struct repository
*r
, struct bitmap_index
*bitmap_git
)
491 assert(bitmap_git
->map
);
493 bitmap_git
->bitmaps
= kh_init_oid_map();
494 bitmap_git
->ext_index
.positions
= kh_init_oid_pos();
496 if (load_reverse_index(r
, bitmap_git
))
499 if (!(bitmap_git
->commits
= read_bitmap_1(bitmap_git
)) ||
500 !(bitmap_git
->trees
= read_bitmap_1(bitmap_git
)) ||
501 !(bitmap_git
->blobs
= read_bitmap_1(bitmap_git
)) ||
502 !(bitmap_git
->tags
= read_bitmap_1(bitmap_git
)))
505 if (!bitmap_git
->table_lookup
&& load_bitmap_entries_v1(bitmap_git
) < 0)
511 munmap(bitmap_git
->map
, bitmap_git
->map_size
);
512 bitmap_git
->map
= NULL
;
513 bitmap_git
->map_size
= 0;
515 kh_destroy_oid_map(bitmap_git
->bitmaps
);
516 bitmap_git
->bitmaps
= NULL
;
518 kh_destroy_oid_pos(bitmap_git
->ext_index
.positions
);
519 bitmap_git
->ext_index
.positions
= NULL
;
524 static int open_pack_bitmap(struct repository
*r
,
525 struct bitmap_index
*bitmap_git
)
527 struct packed_git
*p
;
530 for (p
= get_all_packs(r
); p
; p
= p
->next
) {
531 if (open_pack_bitmap_1(bitmap_git
, p
) == 0) {
534 * The only reason to keep looking is to report
537 if (!trace2_is_enabled())
545 static int open_midx_bitmap(struct repository
*r
,
546 struct bitmap_index
*bitmap_git
)
549 struct multi_pack_index
*midx
;
551 assert(!bitmap_git
->map
);
553 for (midx
= get_multi_pack_index(r
); midx
; midx
= midx
->next
) {
554 if (!open_midx_bitmap_1(bitmap_git
, midx
))
560 static int open_bitmap(struct repository
*r
,
561 struct bitmap_index
*bitmap_git
)
565 assert(!bitmap_git
->map
);
567 found
= !open_midx_bitmap(r
, bitmap_git
);
570 * these will all be skipped if we opened a midx bitmap; but run it
571 * anyway if tracing is enabled to report the duplicates
573 if (!found
|| trace2_is_enabled())
574 found
|= !open_pack_bitmap(r
, bitmap_git
);
576 return found
? 0 : -1;
579 struct bitmap_index
*prepare_bitmap_git(struct repository
*r
)
581 struct bitmap_index
*bitmap_git
= xcalloc(1, sizeof(*bitmap_git
));
583 if (!open_bitmap(r
, bitmap_git
) && !load_bitmap(r
, bitmap_git
))
586 free_bitmap_index(bitmap_git
);
590 struct bitmap_index
*prepare_midx_bitmap_git(struct multi_pack_index
*midx
)
592 struct repository
*r
= the_repository
;
593 struct bitmap_index
*bitmap_git
= xcalloc(1, sizeof(*bitmap_git
));
595 if (!open_midx_bitmap_1(bitmap_git
, midx
) && !load_bitmap(r
, bitmap_git
))
598 free_bitmap_index(bitmap_git
);
602 struct include_data
{
603 struct bitmap_index
*bitmap_git
;
608 struct bitmap_lookup_table_triplet
{
614 struct bitmap_lookup_table_xor_item
{
615 struct object_id oid
;
620 * Given a `triplet` struct pointer and pointer `p`, this
621 * function reads the triplet beginning at `p` into the struct.
622 * Note that this function assumes that there is enough memory
623 * left for filling the `triplet` struct from `p`.
625 static int bitmap_lookup_table_get_triplet_by_pointer(struct bitmap_lookup_table_triplet
*triplet
,
626 const unsigned char *p
)
631 triplet
->commit_pos
= get_be32(p
);
632 p
+= sizeof(uint32_t);
633 triplet
->offset
= get_be64(p
);
634 p
+= sizeof(uint64_t);
635 triplet
->xor_row
= get_be32(p
);
640 * This function gets the raw triplet from `row`'th row in the
641 * lookup table and fills that data to the `triplet`.
643 static int bitmap_lookup_table_get_triplet(struct bitmap_index
*bitmap_git
,
645 struct bitmap_lookup_table_triplet
*triplet
)
647 unsigned char *p
= NULL
;
648 if (pos
>= bitmap_git
->entry_count
)
649 return error(_("corrupt bitmap lookup table: triplet position out of index"));
651 p
= bitmap_git
->table_lookup
+ st_mult(pos
, BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH
);
653 return bitmap_lookup_table_get_triplet_by_pointer(triplet
, p
);
657 * Searches for a matching triplet. `commit_pos` is a pointer
658 * to the wanted commit position value. `table_entry` points to
659 * a triplet in lookup table. The first 4 bytes of each
660 * triplet (pointed by `table_entry`) are compared with `*commit_pos`.
662 static int triplet_cmp(const void *commit_pos
, const void *table_entry
)
665 uint32_t a
= *(uint32_t *)commit_pos
;
666 uint32_t b
= get_be32(table_entry
);
675 static uint32_t bitmap_bsearch_pos(struct bitmap_index
*bitmap_git
,
676 struct object_id
*oid
,
681 if (bitmap_is_midx(bitmap_git
))
682 found
= bsearch_midx(oid
, bitmap_git
->midx
, result
);
684 found
= bsearch_pack(oid
, bitmap_git
->pack
, result
);
690 * `bsearch_triplet_by_pos` function searches for the raw triplet
691 * having commit position same as `commit_pos` and fills `triplet`
692 * object from the raw triplet. Returns 1 on success and 0 on
695 static int bitmap_bsearch_triplet_by_pos(uint32_t commit_pos
,
696 struct bitmap_index
*bitmap_git
,
697 struct bitmap_lookup_table_triplet
*triplet
)
699 unsigned char *p
= bsearch(&commit_pos
, bitmap_git
->table_lookup
, bitmap_git
->entry_count
,
700 BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH
, triplet_cmp
);
705 return bitmap_lookup_table_get_triplet_by_pointer(triplet
, p
);
708 static struct stored_bitmap
*lazy_bitmap_for_commit(struct bitmap_index
*bitmap_git
,
709 struct commit
*commit
)
711 uint32_t commit_pos
, xor_row
;
714 struct bitmap_lookup_table_triplet triplet
;
715 struct object_id
*oid
= &commit
->object
.oid
;
716 struct ewah_bitmap
*bitmap
;
717 struct stored_bitmap
*xor_bitmap
= NULL
;
718 const int bitmap_header_size
= 6;
719 static struct bitmap_lookup_table_xor_item
*xor_items
= NULL
;
720 static size_t xor_items_nr
= 0, xor_items_alloc
= 0;
721 static int is_corrupt
= 0;
724 struct bitmap_lookup_table_xor_item
*xor_item
;
729 if (!bitmap_bsearch_pos(bitmap_git
, oid
, &commit_pos
))
732 if (bitmap_bsearch_triplet_by_pos(commit_pos
, bitmap_git
, &triplet
) < 0)
736 offset
= triplet
.offset
;
737 xor_row
= triplet
.xor_row
;
739 while (xor_row
!= 0xffffffff) {
740 ALLOC_GROW(xor_items
, xor_items_nr
+ 1, xor_items_alloc
);
742 if (xor_items_nr
+ 1 >= bitmap_git
->entry_count
) {
743 error(_("corrupt bitmap lookup table: xor chain exceeds entry count"));
747 if (bitmap_lookup_table_get_triplet(bitmap_git
, xor_row
, &triplet
) < 0)
750 xor_item
= &xor_items
[xor_items_nr
];
751 xor_item
->offset
= triplet
.offset
;
753 if (nth_bitmap_object_oid(bitmap_git
, &xor_item
->oid
, triplet
.commit_pos
) < 0) {
754 error(_("corrupt bitmap lookup table: commit index %u out of range"),
759 hash_pos
= kh_get_oid_map(bitmap_git
->bitmaps
, xor_item
->oid
);
762 * If desired bitmap is already stored, we don't need
763 * to iterate further. Because we know that bitmaps
764 * that are needed to be parsed to parse this bitmap
765 * has already been stored. So, assign this stored bitmap
768 if (hash_pos
< kh_end(bitmap_git
->bitmaps
) &&
769 (xor_bitmap
= kh_value(bitmap_git
->bitmaps
, hash_pos
)))
772 xor_row
= triplet
.xor_row
;
775 while (xor_items_nr
) {
776 xor_item
= &xor_items
[xor_items_nr
- 1];
777 bitmap_git
->map_pos
= xor_item
->offset
;
778 if (bitmap_git
->map_size
- bitmap_git
->map_pos
< bitmap_header_size
) {
779 error(_("corrupt ewah bitmap: truncated header for bitmap of commit \"%s\""),
780 oid_to_hex(&xor_item
->oid
));
784 bitmap_git
->map_pos
+= sizeof(uint32_t) + sizeof(uint8_t);
785 xor_flags
= read_u8(bitmap_git
->map
, &bitmap_git
->map_pos
);
786 bitmap
= read_bitmap_1(bitmap_git
);
791 xor_bitmap
= store_bitmap(bitmap_git
, bitmap
, &xor_item
->oid
, xor_bitmap
, xor_flags
);
795 bitmap_git
->map_pos
= offset
;
796 if (bitmap_git
->map_size
- bitmap_git
->map_pos
< bitmap_header_size
) {
797 error(_("corrupt ewah bitmap: truncated header for bitmap of commit \"%s\""),
803 * Don't bother reading the commit's index position or its xor
806 * - The commit's index position is irrelevant to us, since
807 * load_bitmap_entries_v1 only uses it to learn the object
808 * id which is used to compute the hashmap's key. We already
809 * have an object id, so no need to look it up again.
811 * - The xor_offset is unusable for us, since it specifies how
812 * many entries previous to ours we should look at. This
813 * makes sense when reading the bitmaps sequentially (as in
814 * load_bitmap_entries_v1()), since we can keep track of
815 * each bitmap as we read them.
817 * But it can't work for us, since the bitmap's don't have a
818 * fixed size. So we learn the position of the xor'd bitmap
819 * from the commit table (and resolve it to a bitmap in the
820 * above if-statement).
822 * Instead, we can skip ahead and immediately read the flags and
825 bitmap_git
->map_pos
+= sizeof(uint32_t) + sizeof(uint8_t);
826 flags
= read_u8(bitmap_git
->map
, &bitmap_git
->map_pos
);
827 bitmap
= read_bitmap_1(bitmap_git
);
832 return store_bitmap(bitmap_git
, bitmap
, oid
, xor_bitmap
, flags
);
840 struct ewah_bitmap
*bitmap_for_commit(struct bitmap_index
*bitmap_git
,
841 struct commit
*commit
)
843 khiter_t hash_pos
= kh_get_oid_map(bitmap_git
->bitmaps
,
845 if (hash_pos
>= kh_end(bitmap_git
->bitmaps
)) {
846 struct stored_bitmap
*bitmap
= NULL
;
847 if (!bitmap_git
->table_lookup
)
850 /* this is a fairly hot codepath - no trace2_region please */
851 /* NEEDSWORK: cache misses aren't recorded */
852 bitmap
= lazy_bitmap_for_commit(bitmap_git
, commit
);
855 return lookup_stored_bitmap(bitmap
);
857 return lookup_stored_bitmap(kh_value(bitmap_git
->bitmaps
, hash_pos
));
860 static inline int bitmap_position_extended(struct bitmap_index
*bitmap_git
,
861 const struct object_id
*oid
)
863 kh_oid_pos_t
*positions
= bitmap_git
->ext_index
.positions
;
864 khiter_t pos
= kh_get_oid_pos(positions
, *oid
);
866 if (pos
< kh_end(positions
)) {
867 int bitmap_pos
= kh_value(positions
, pos
);
868 return bitmap_pos
+ bitmap_num_objects(bitmap_git
);
874 static inline int bitmap_position_packfile(struct bitmap_index
*bitmap_git
,
875 const struct object_id
*oid
)
878 off_t offset
= find_pack_entry_one(oid
->hash
, bitmap_git
->pack
);
882 if (offset_to_pack_pos(bitmap_git
->pack
, offset
, &pos
) < 0)
887 static int bitmap_position_midx(struct bitmap_index
*bitmap_git
,
888 const struct object_id
*oid
)
891 if (!bsearch_midx(oid
, bitmap_git
->midx
, &want
))
894 if (midx_to_pack_pos(bitmap_git
->midx
, want
, &got
) < 0)
899 static int bitmap_position(struct bitmap_index
*bitmap_git
,
900 const struct object_id
*oid
)
903 if (bitmap_is_midx(bitmap_git
))
904 pos
= bitmap_position_midx(bitmap_git
, oid
);
906 pos
= bitmap_position_packfile(bitmap_git
, oid
);
907 return (pos
>= 0) ? pos
: bitmap_position_extended(bitmap_git
, oid
);
910 static int ext_index_add_object(struct bitmap_index
*bitmap_git
,
911 struct object
*object
, const char *name
)
913 struct eindex
*eindex
= &bitmap_git
->ext_index
;
919 hash_pos
= kh_put_oid_pos(eindex
->positions
, object
->oid
, &hash_ret
);
921 if (eindex
->count
>= eindex
->alloc
) {
922 eindex
->alloc
= (eindex
->alloc
+ 16) * 3 / 2;
923 REALLOC_ARRAY(eindex
->objects
, eindex
->alloc
);
924 REALLOC_ARRAY(eindex
->hashes
, eindex
->alloc
);
927 bitmap_pos
= eindex
->count
;
928 eindex
->objects
[eindex
->count
] = object
;
929 eindex
->hashes
[eindex
->count
] = pack_name_hash(name
);
930 kh_value(eindex
->positions
, hash_pos
) = bitmap_pos
;
933 bitmap_pos
= kh_value(eindex
->positions
, hash_pos
);
936 return bitmap_pos
+ bitmap_num_objects(bitmap_git
);
939 struct bitmap_show_data
{
940 struct bitmap_index
*bitmap_git
;
944 static void show_object(struct object
*object
, const char *name
, void *data_
)
946 struct bitmap_show_data
*data
= data_
;
949 bitmap_pos
= bitmap_position(data
->bitmap_git
, &object
->oid
);
952 bitmap_pos
= ext_index_add_object(data
->bitmap_git
, object
,
955 bitmap_set(data
->base
, bitmap_pos
);
958 static void show_commit(struct commit
*commit UNUSED
,
963 static int add_to_include_set(struct bitmap_index
*bitmap_git
,
964 struct include_data
*data
,
965 struct commit
*commit
,
968 struct ewah_bitmap
*partial
;
970 if (data
->seen
&& bitmap_get(data
->seen
, bitmap_pos
))
973 if (bitmap_get(data
->base
, bitmap_pos
))
976 partial
= bitmap_for_commit(bitmap_git
, commit
);
978 bitmap_or_ewah(data
->base
, partial
);
982 bitmap_set(data
->base
, bitmap_pos
);
986 static int should_include(struct commit
*commit
, void *_data
)
988 struct include_data
*data
= _data
;
991 bitmap_pos
= bitmap_position(data
->bitmap_git
, &commit
->object
.oid
);
993 bitmap_pos
= ext_index_add_object(data
->bitmap_git
,
994 (struct object
*)commit
,
997 if (!add_to_include_set(data
->bitmap_git
, data
, commit
, bitmap_pos
)) {
998 struct commit_list
*parent
= commit
->parents
;
1001 parent
->item
->object
.flags
|= SEEN
;
1002 parent
= parent
->next
;
1011 static int should_include_obj(struct object
*obj
, void *_data
)
1013 struct include_data
*data
= _data
;
1016 bitmap_pos
= bitmap_position(data
->bitmap_git
, &obj
->oid
);
1019 if ((data
->seen
&& bitmap_get(data
->seen
, bitmap_pos
)) ||
1020 bitmap_get(data
->base
, bitmap_pos
)) {
1027 static int add_commit_to_bitmap(struct bitmap_index
*bitmap_git
,
1028 struct bitmap
**base
,
1029 struct commit
*commit
)
1031 struct ewah_bitmap
*or_with
= bitmap_for_commit(bitmap_git
, commit
);
1037 *base
= ewah_to_bitmap(or_with
);
1039 bitmap_or_ewah(*base
, or_with
);
1044 static struct bitmap
*fill_in_bitmap(struct bitmap_index
*bitmap_git
,
1045 struct rev_info
*revs
,
1046 struct bitmap
*base
,
1047 struct bitmap
*seen
)
1049 struct include_data incdata
;
1050 struct bitmap_show_data show_data
;
1053 base
= bitmap_new();
1055 incdata
.bitmap_git
= bitmap_git
;
1056 incdata
.base
= base
;
1057 incdata
.seen
= seen
;
1059 revs
->include_check
= should_include
;
1060 revs
->include_check_obj
= should_include_obj
;
1061 revs
->include_check_data
= &incdata
;
1063 if (prepare_revision_walk(revs
))
1064 die(_("revision walk setup failed"));
1066 show_data
.bitmap_git
= bitmap_git
;
1067 show_data
.base
= base
;
1069 traverse_commit_list(revs
, show_commit
, show_object
, &show_data
);
1071 revs
->include_check
= NULL
;
1072 revs
->include_check_obj
= NULL
;
1073 revs
->include_check_data
= NULL
;
1078 struct bitmap_boundary_cb
{
1079 struct bitmap_index
*bitmap_git
;
1080 struct bitmap
*base
;
1082 struct object_array boundary
;
1085 static void show_boundary_commit(struct commit
*commit
, void *_data
)
1087 struct bitmap_boundary_cb
*data
= _data
;
1089 if (commit
->object
.flags
& BOUNDARY
)
1090 add_object_array(&commit
->object
, "", &data
->boundary
);
1092 if (commit
->object
.flags
& UNINTERESTING
) {
1093 if (bitmap_walk_contains(data
->bitmap_git
, data
->base
,
1094 &commit
->object
.oid
))
1097 add_commit_to_bitmap(data
->bitmap_git
, &data
->base
, commit
);
1101 static void show_boundary_object(struct object
*object UNUSED
,
1102 const char *name UNUSED
,
1105 BUG("should not be called");
1108 static struct bitmap
*find_boundary_objects(struct bitmap_index
*bitmap_git
,
1109 struct rev_info
*revs
,
1110 struct object_list
*roots
)
1112 struct bitmap_boundary_cb cb
;
1113 struct object_list
*root
;
1115 unsigned int tmp_blobs
, tmp_trees
, tmp_tags
;
1116 int any_missing
= 0;
1118 cb
.bitmap_git
= bitmap_git
;
1119 cb
.base
= bitmap_new();
1120 object_array_init(&cb
.boundary
);
1122 revs
->ignore_missing_links
= 1;
1125 * OR in any existing reachability bitmaps among `roots` into
1128 for (root
= roots
; root
; root
= root
->next
) {
1129 struct object
*object
= root
->item
;
1130 if (object
->type
!= OBJ_COMMIT
||
1131 bitmap_walk_contains(bitmap_git
, cb
.base
, &object
->oid
))
1134 if (add_commit_to_bitmap(bitmap_git
, &cb
.base
,
1135 (struct commit
*)object
))
1144 tmp_blobs
= revs
->blob_objects
;
1145 tmp_trees
= revs
->tree_objects
;
1146 tmp_tags
= revs
->blob_objects
;
1147 revs
->blob_objects
= 0;
1148 revs
->tree_objects
= 0;
1149 revs
->tag_objects
= 0;
1152 * We didn't have complete coverage of the roots. First setup a
1153 * revision walk to (a) OR in any bitmaps that are UNINTERESTING
1154 * between the tips and boundary, and (b) record the boundary.
1156 trace2_region_enter("pack-bitmap", "boundary-prepare", the_repository
);
1157 if (prepare_revision_walk(revs
))
1158 die("revision walk setup failed");
1159 trace2_region_leave("pack-bitmap", "boundary-prepare", the_repository
);
1161 trace2_region_enter("pack-bitmap", "boundary-traverse", the_repository
);
1163 traverse_commit_list_filtered(revs
,
1164 show_boundary_commit
,
1165 show_boundary_object
,
1168 trace2_region_leave("pack-bitmap", "boundary-traverse", the_repository
);
1170 revs
->blob_objects
= tmp_blobs
;
1171 revs
->tree_objects
= tmp_trees
;
1172 revs
->tag_objects
= tmp_tags
;
1174 reset_revision_walk();
1175 clear_object_flags(UNINTERESTING
);
1178 * Then add the boundary commit(s) as fill-in traversal tips.
1180 trace2_region_enter("pack-bitmap", "boundary-fill-in", the_repository
);
1181 for (i
= 0; i
< cb
.boundary
.nr
; i
++) {
1182 struct object
*obj
= cb
.boundary
.objects
[i
].item
;
1183 if (bitmap_walk_contains(bitmap_git
, cb
.base
, &obj
->oid
))
1186 add_pending_object(revs
, obj
, "");
1188 if (revs
->pending
.nr
)
1189 cb
.base
= fill_in_bitmap(bitmap_git
, revs
, cb
.base
, NULL
);
1190 trace2_region_leave("pack-bitmap", "boundary-fill-in", the_repository
);
1193 object_array_clear(&cb
.boundary
);
1194 revs
->ignore_missing_links
= 0;
1199 static struct bitmap
*find_objects(struct bitmap_index
*bitmap_git
,
1200 struct rev_info
*revs
,
1201 struct object_list
*roots
,
1202 struct bitmap
*seen
)
1204 struct bitmap
*base
= NULL
;
1207 struct object_list
*not_mapped
= NULL
;
1210 * Go through all the roots for the walk. The ones that have bitmaps
1211 * on the bitmap index will be `or`ed together to form an initial
1212 * global reachability analysis.
1214 * The ones without bitmaps in the index will be stored in the
1215 * `not_mapped_list` for further processing.
1218 struct object
*object
= roots
->item
;
1219 roots
= roots
->next
;
1221 if (object
->type
== OBJ_COMMIT
&&
1222 add_commit_to_bitmap(bitmap_git
, &base
, (struct commit
*)object
)) {
1223 object
->flags
|= SEEN
;
1227 object_list_insert(object
, ¬_mapped
);
1231 * Best case scenario: We found bitmaps for all the roots,
1232 * so the resulting `or` bitmap has the full reachability analysis
1240 * Let's iterate through all the roots that don't have bitmaps to
1241 * check if we can determine them to be reachable from the existing
1244 * If we cannot find them in the existing global bitmap, we'll need
1245 * to push them to an actual walk and run it until we can confirm
1246 * they are reachable
1249 struct object
*object
= roots
->item
;
1252 roots
= roots
->next
;
1253 pos
= bitmap_position(bitmap_git
, &object
->oid
);
1255 if (pos
< 0 || base
== NULL
|| !bitmap_get(base
, pos
)) {
1256 object
->flags
&= ~UNINTERESTING
;
1257 add_pending_object(revs
, object
, "");
1260 object
->flags
|= SEEN
;
1266 * This fill-in traversal may walk over some objects
1267 * again, since we have already traversed in order to
1268 * find the boundary.
1270 * But this extra walk should be extremely cheap, since
1271 * all commit objects are loaded into memory, and
1272 * because we skip walking to parents that are
1273 * UNINTERESTING, since it will be marked in the haves
1274 * bitmap already (or it has an on-disk bitmap, since
1275 * OR-ing it in covers all of its ancestors).
1277 base
= fill_in_bitmap(bitmap_git
, revs
, base
, seen
);
1280 object_list_free(¬_mapped
);
1285 static void show_extended_objects(struct bitmap_index
*bitmap_git
,
1286 struct rev_info
*revs
,
1287 show_reachable_fn show_reach
)
1289 struct bitmap
*objects
= bitmap_git
->result
;
1290 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1293 for (i
= 0; i
< eindex
->count
; ++i
) {
1296 if (!bitmap_get(objects
, st_add(bitmap_num_objects(bitmap_git
), i
)))
1299 obj
= eindex
->objects
[i
];
1300 if ((obj
->type
== OBJ_BLOB
&& !revs
->blob_objects
) ||
1301 (obj
->type
== OBJ_TREE
&& !revs
->tree_objects
) ||
1302 (obj
->type
== OBJ_TAG
&& !revs
->tag_objects
))
1305 show_reach(&obj
->oid
, obj
->type
, 0, eindex
->hashes
[i
], NULL
, 0);
1309 static void init_type_iterator(struct ewah_iterator
*it
,
1310 struct bitmap_index
*bitmap_git
,
1311 enum object_type type
)
1315 ewah_iterator_init(it
, bitmap_git
->commits
);
1319 ewah_iterator_init(it
, bitmap_git
->trees
);
1323 ewah_iterator_init(it
, bitmap_git
->blobs
);
1327 ewah_iterator_init(it
, bitmap_git
->tags
);
1331 BUG("object type %d not stored by bitmap type index", type
);
1336 static void show_objects_for_type(
1337 struct bitmap_index
*bitmap_git
,
1338 enum object_type object_type
,
1339 show_reachable_fn show_reach
)
1344 struct ewah_iterator it
;
1347 struct bitmap
*objects
= bitmap_git
->result
;
1349 init_type_iterator(&it
, bitmap_git
, object_type
);
1351 for (i
= 0; i
< objects
->word_alloc
&&
1352 ewah_iterator_next(&filter
, &it
); i
++) {
1353 eword_t word
= objects
->words
[i
] & filter
;
1354 size_t pos
= (i
* BITS_IN_EWORD
);
1359 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
1360 struct packed_git
*pack
;
1361 struct object_id oid
;
1362 uint32_t hash
= 0, index_pos
;
1365 if ((word
>> offset
) == 0)
1368 offset
+= ewah_bit_ctz64(word
>> offset
);
1370 if (bitmap_is_midx(bitmap_git
)) {
1371 struct multi_pack_index
*m
= bitmap_git
->midx
;
1374 index_pos
= pack_pos_to_midx(m
, pos
+ offset
);
1375 ofs
= nth_midxed_offset(m
, index_pos
);
1376 nth_midxed_object_oid(&oid
, m
, index_pos
);
1378 pack_id
= nth_midxed_pack_int_id(m
, index_pos
);
1379 pack
= bitmap_git
->midx
->packs
[pack_id
];
1381 index_pos
= pack_pos_to_index(bitmap_git
->pack
, pos
+ offset
);
1382 ofs
= pack_pos_to_offset(bitmap_git
->pack
, pos
+ offset
);
1383 nth_bitmap_object_oid(bitmap_git
, &oid
, index_pos
);
1385 pack
= bitmap_git
->pack
;
1388 if (bitmap_git
->hashes
)
1389 hash
= get_be32(bitmap_git
->hashes
+ index_pos
);
1391 show_reach(&oid
, object_type
, 0, hash
, pack
, ofs
);
1396 static int in_bitmapped_pack(struct bitmap_index
*bitmap_git
,
1397 struct object_list
*roots
)
1400 struct object
*object
= roots
->item
;
1401 roots
= roots
->next
;
1403 if (bitmap_is_midx(bitmap_git
)) {
1404 if (bsearch_midx(&object
->oid
, bitmap_git
->midx
, NULL
))
1407 if (find_pack_entry_one(object
->oid
.hash
, bitmap_git
->pack
) > 0)
1415 static struct bitmap
*find_tip_objects(struct bitmap_index
*bitmap_git
,
1416 struct object_list
*tip_objects
,
1417 enum object_type type
)
1419 struct bitmap
*result
= bitmap_new();
1420 struct object_list
*p
;
1422 for (p
= tip_objects
; p
; p
= p
->next
) {
1425 if (p
->item
->type
!= type
)
1428 pos
= bitmap_position(bitmap_git
, &p
->item
->oid
);
1432 bitmap_set(result
, pos
);
1438 static void filter_bitmap_exclude_type(struct bitmap_index
*bitmap_git
,
1439 struct object_list
*tip_objects
,
1440 struct bitmap
*to_filter
,
1441 enum object_type type
)
1443 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1444 struct bitmap
*tips
;
1445 struct ewah_iterator it
;
1450 * The non-bitmap version of this filter never removes
1451 * objects which the other side specifically asked for,
1452 * so we must match that behavior.
1454 tips
= find_tip_objects(bitmap_git
, tip_objects
, type
);
1457 * We can use the type-level bitmap for 'type' to work in whole
1458 * words for the objects that are actually in the bitmapped
1461 for (i
= 0, init_type_iterator(&it
, bitmap_git
, type
);
1462 i
< to_filter
->word_alloc
&& ewah_iterator_next(&mask
, &it
);
1464 if (i
< tips
->word_alloc
)
1465 mask
&= ~tips
->words
[i
];
1466 to_filter
->words
[i
] &= ~mask
;
1470 * Clear any objects that weren't in the packfile (and so would
1471 * not have been caught by the loop above. We'll have to check
1472 * them individually.
1474 for (i
= 0; i
< eindex
->count
; i
++) {
1475 size_t pos
= st_add(i
, bitmap_num_objects(bitmap_git
));
1476 if (eindex
->objects
[i
]->type
== type
&&
1477 bitmap_get(to_filter
, pos
) &&
1478 !bitmap_get(tips
, pos
))
1479 bitmap_unset(to_filter
, pos
);
1485 static void filter_bitmap_blob_none(struct bitmap_index
*bitmap_git
,
1486 struct object_list
*tip_objects
,
1487 struct bitmap
*to_filter
)
1489 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
,
1493 static unsigned long get_size_by_pos(struct bitmap_index
*bitmap_git
,
1497 struct object_info oi
= OBJECT_INFO_INIT
;
1501 if (pos
< bitmap_num_objects(bitmap_git
)) {
1502 struct packed_git
*pack
;
1505 if (bitmap_is_midx(bitmap_git
)) {
1506 uint32_t midx_pos
= pack_pos_to_midx(bitmap_git
->midx
, pos
);
1507 uint32_t pack_id
= nth_midxed_pack_int_id(bitmap_git
->midx
, midx_pos
);
1509 pack
= bitmap_git
->midx
->packs
[pack_id
];
1510 ofs
= nth_midxed_offset(bitmap_git
->midx
, midx_pos
);
1512 pack
= bitmap_git
->pack
;
1513 ofs
= pack_pos_to_offset(pack
, pos
);
1516 if (packed_object_info(the_repository
, pack
, ofs
, &oi
) < 0) {
1517 struct object_id oid
;
1518 nth_bitmap_object_oid(bitmap_git
, &oid
,
1519 pack_pos_to_index(pack
, pos
));
1520 die(_("unable to get size of %s"), oid_to_hex(&oid
));
1523 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1524 struct object
*obj
= eindex
->objects
[pos
- bitmap_num_objects(bitmap_git
)];
1525 if (oid_object_info_extended(the_repository
, &obj
->oid
, &oi
, 0) < 0)
1526 die(_("unable to get size of %s"), oid_to_hex(&obj
->oid
));
1532 static void filter_bitmap_blob_limit(struct bitmap_index
*bitmap_git
,
1533 struct object_list
*tip_objects
,
1534 struct bitmap
*to_filter
,
1535 unsigned long limit
)
1537 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1538 struct bitmap
*tips
;
1539 struct ewah_iterator it
;
1543 tips
= find_tip_objects(bitmap_git
, tip_objects
, OBJ_BLOB
);
1545 for (i
= 0, init_type_iterator(&it
, bitmap_git
, OBJ_BLOB
);
1546 i
< to_filter
->word_alloc
&& ewah_iterator_next(&mask
, &it
);
1548 eword_t word
= to_filter
->words
[i
] & mask
;
1551 for (offset
= 0; offset
< BITS_IN_EWORD
; offset
++) {
1554 if ((word
>> offset
) == 0)
1556 offset
+= ewah_bit_ctz64(word
>> offset
);
1557 pos
= i
* BITS_IN_EWORD
+ offset
;
1559 if (!bitmap_get(tips
, pos
) &&
1560 get_size_by_pos(bitmap_git
, pos
) >= limit
)
1561 bitmap_unset(to_filter
, pos
);
1565 for (i
= 0; i
< eindex
->count
; i
++) {
1566 size_t pos
= st_add(i
, bitmap_num_objects(bitmap_git
));
1567 if (eindex
->objects
[i
]->type
== OBJ_BLOB
&&
1568 bitmap_get(to_filter
, pos
) &&
1569 !bitmap_get(tips
, pos
) &&
1570 get_size_by_pos(bitmap_git
, pos
) >= limit
)
1571 bitmap_unset(to_filter
, pos
);
1577 static void filter_bitmap_tree_depth(struct bitmap_index
*bitmap_git
,
1578 struct object_list
*tip_objects
,
1579 struct bitmap
*to_filter
,
1580 unsigned long limit
)
1583 BUG("filter_bitmap_tree_depth given non-zero limit");
1585 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
,
1587 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
,
1591 static void filter_bitmap_object_type(struct bitmap_index
*bitmap_git
,
1592 struct object_list
*tip_objects
,
1593 struct bitmap
*to_filter
,
1594 enum object_type object_type
)
1596 if (object_type
< OBJ_COMMIT
|| object_type
> OBJ_TAG
)
1597 BUG("filter_bitmap_object_type given invalid object");
1599 if (object_type
!= OBJ_TAG
)
1600 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_TAG
);
1601 if (object_type
!= OBJ_COMMIT
)
1602 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_COMMIT
);
1603 if (object_type
!= OBJ_TREE
)
1604 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_TREE
);
1605 if (object_type
!= OBJ_BLOB
)
1606 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_BLOB
);
1609 static int filter_bitmap(struct bitmap_index
*bitmap_git
,
1610 struct object_list
*tip_objects
,
1611 struct bitmap
*to_filter
,
1612 struct list_objects_filter_options
*filter
)
1614 if (!filter
|| filter
->choice
== LOFC_DISABLED
)
1617 if (filter
->choice
== LOFC_BLOB_NONE
) {
1619 filter_bitmap_blob_none(bitmap_git
, tip_objects
,
1624 if (filter
->choice
== LOFC_BLOB_LIMIT
) {
1626 filter_bitmap_blob_limit(bitmap_git
, tip_objects
,
1628 filter
->blob_limit_value
);
1632 if (filter
->choice
== LOFC_TREE_DEPTH
&&
1633 filter
->tree_exclude_depth
== 0) {
1635 filter_bitmap_tree_depth(bitmap_git
, tip_objects
,
1637 filter
->tree_exclude_depth
);
1641 if (filter
->choice
== LOFC_OBJECT_TYPE
) {
1643 filter_bitmap_object_type(bitmap_git
, tip_objects
,
1645 filter
->object_type
);
1649 if (filter
->choice
== LOFC_COMBINE
) {
1651 for (i
= 0; i
< filter
->sub_nr
; i
++) {
1652 if (filter_bitmap(bitmap_git
, tip_objects
, to_filter
,
1653 &filter
->sub
[i
]) < 0)
1659 /* filter choice not handled */
1663 static int can_filter_bitmap(struct list_objects_filter_options
*filter
)
1665 return !filter_bitmap(NULL
, NULL
, NULL
, filter
);
1669 static void filter_packed_objects_from_bitmap(struct bitmap_index
*bitmap_git
,
1670 struct bitmap
*result
)
1672 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1673 uint32_t objects_nr
;
1676 objects_nr
= bitmap_num_objects(bitmap_git
);
1677 pos
= objects_nr
/ BITS_IN_EWORD
;
1679 if (pos
> result
->word_alloc
)
1680 pos
= result
->word_alloc
;
1682 memset(result
->words
, 0x00, sizeof(eword_t
) * pos
);
1683 for (i
= pos
* BITS_IN_EWORD
; i
< objects_nr
; i
++)
1684 bitmap_unset(result
, i
);
1686 for (i
= 0; i
< eindex
->count
; ++i
) {
1687 if (has_object_pack(&eindex
->objects
[i
]->oid
))
1688 bitmap_unset(result
, objects_nr
+ i
);
1692 struct bitmap_index
*prepare_bitmap_walk(struct rev_info
*revs
,
1693 int filter_provided_objects
)
1696 int use_boundary_traversal
;
1698 struct object_list
*wants
= NULL
;
1699 struct object_list
*haves
= NULL
;
1701 struct bitmap
*wants_bitmap
= NULL
;
1702 struct bitmap
*haves_bitmap
= NULL
;
1704 struct bitmap_index
*bitmap_git
;
1707 * We can't do pathspec limiting with bitmaps, because we don't know
1708 * which commits are associated with which object changes (let alone
1709 * even which objects are associated with which paths).
1714 if (!can_filter_bitmap(&revs
->filter
))
1717 /* try to open a bitmapped pack, but don't parse it yet
1718 * because we may not need to use it */
1719 CALLOC_ARRAY(bitmap_git
, 1);
1720 if (open_bitmap(revs
->repo
, bitmap_git
) < 0)
1723 for (i
= 0; i
< revs
->pending
.nr
; ++i
) {
1724 struct object
*object
= revs
->pending
.objects
[i
].item
;
1726 if (object
->type
== OBJ_NONE
)
1727 parse_object_or_die(&object
->oid
, NULL
);
1729 while (object
->type
== OBJ_TAG
) {
1730 struct tag
*tag
= (struct tag
*) object
;
1732 if (object
->flags
& UNINTERESTING
)
1733 object_list_insert(object
, &haves
);
1735 object_list_insert(object
, &wants
);
1737 object
= parse_object_or_die(get_tagged_oid(tag
), NULL
);
1738 object
->flags
|= (tag
->object
.flags
& UNINTERESTING
);
1741 if (object
->flags
& UNINTERESTING
)
1742 object_list_insert(object
, &haves
);
1744 object_list_insert(object
, &wants
);
1747 use_boundary_traversal
= git_env_bool(GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL
, -1);
1748 if (use_boundary_traversal
< 0) {
1749 prepare_repo_settings(revs
->repo
);
1750 use_boundary_traversal
= revs
->repo
->settings
.pack_use_bitmap_boundary_traversal
;
1753 if (!use_boundary_traversal
) {
1755 * if we have a HAVES list, but none of those haves is contained
1756 * in the packfile that has a bitmap, we don't have anything to
1759 if (haves
&& !in_bitmapped_pack(bitmap_git
, haves
))
1763 /* if we don't want anything, we're done here */
1768 * now we're going to use bitmaps, so load the actual bitmap entries
1769 * from disk. this is the point of no return; after this the rev_list
1770 * becomes invalidated and we must perform the revwalk through bitmaps
1772 if (load_bitmap(revs
->repo
, bitmap_git
) < 0)
1775 if (!use_boundary_traversal
)
1776 object_array_clear(&revs
->pending
);
1779 if (use_boundary_traversal
) {
1780 trace2_region_enter("pack-bitmap", "haves/boundary", the_repository
);
1781 haves_bitmap
= find_boundary_objects(bitmap_git
, revs
, haves
);
1782 trace2_region_leave("pack-bitmap", "haves/boundary", the_repository
);
1784 trace2_region_enter("pack-bitmap", "haves/classic", the_repository
);
1785 revs
->ignore_missing_links
= 1;
1786 haves_bitmap
= find_objects(bitmap_git
, revs
, haves
, NULL
);
1787 reset_revision_walk();
1788 revs
->ignore_missing_links
= 0;
1789 trace2_region_leave("pack-bitmap", "haves/classic", the_repository
);
1793 BUG("failed to perform bitmap walk");
1796 if (use_boundary_traversal
) {
1797 object_array_clear(&revs
->pending
);
1798 reset_revision_walk();
1801 wants_bitmap
= find_objects(bitmap_git
, revs
, wants
, haves_bitmap
);
1804 BUG("failed to perform bitmap walk");
1807 bitmap_and_not(wants_bitmap
, haves_bitmap
);
1809 filter_bitmap(bitmap_git
,
1810 (revs
->filter
.choice
&& filter_provided_objects
) ? NULL
: wants
,
1815 filter_packed_objects_from_bitmap(bitmap_git
, wants_bitmap
);
1817 bitmap_git
->result
= wants_bitmap
;
1818 bitmap_git
->haves
= haves_bitmap
;
1820 object_list_free(&wants
);
1821 object_list_free(&haves
);
1826 free_bitmap_index(bitmap_git
);
1827 object_list_free(&wants
);
1828 object_list_free(&haves
);
1833 * -1 means "stop trying further objects"; 0 means we may or may not have
1834 * reused, but you can keep feeding bits.
1836 static int try_partial_reuse(struct bitmap_index
*bitmap_git
,
1837 struct bitmapped_pack
*pack
,
1840 struct bitmap
*reuse
,
1841 struct pack_window
**w_curs
)
1843 off_t offset
, delta_obj_offset
;
1844 enum object_type type
;
1847 if (pack_pos
>= pack
->p
->num_objects
)
1848 return -1; /* not actually in the pack */
1850 offset
= delta_obj_offset
= pack_pos_to_offset(pack
->p
, pack_pos
);
1851 type
= unpack_object_header(pack
->p
, w_curs
, &offset
, &size
);
1853 return -1; /* broken packfile, punt */
1855 if (type
== OBJ_REF_DELTA
|| type
== OBJ_OFS_DELTA
) {
1858 uint32_t base_bitmap_pos
;
1861 * Find the position of the base object so we can look it up
1862 * in our bitmaps. If we can't come up with an offset, or if
1863 * that offset is not in the revidx, the pack is corrupt.
1864 * There's nothing we can do, so just punt on this object,
1865 * and the normal slow path will complain about it in
1868 base_offset
= get_delta_base(pack
->p
, w_curs
, &offset
, type
,
1873 offset_to_pack_pos(pack
->p
, base_offset
, &base_pos
);
1875 if (bitmap_is_midx(bitmap_git
)) {
1877 * Cross-pack deltas are rejected for now, but could
1878 * theoretically be supported in the future.
1880 * We would need to ensure that we're sending both
1881 * halves of the delta/base pair, regardless of whether
1882 * or not the two cross a pack boundary. If they do,
1883 * then we must convert the delta to an REF_DELTA to
1884 * refer back to the base in the other pack.
1886 if (midx_pair_to_pack_pos(bitmap_git
->midx
,
1889 &base_bitmap_pos
) < 0) {
1893 if (offset_to_pack_pos(pack
->p
, base_offset
,
1897 * We assume delta dependencies always point backwards.
1898 * This lets us do a single pass, and is basically
1899 * always true due to the way OFS_DELTAs work. You would
1900 * not typically find REF_DELTA in a bitmapped pack,
1901 * since we only bitmap packs we write fresh, and
1902 * OFS_DELTA is the default). But let's double check to
1903 * make sure the pack wasn't written with odd
1906 if (base_pos
>= pack_pos
)
1908 base_bitmap_pos
= pack
->bitmap_pos
+ base_pos
;
1912 * And finally, if we're not sending the base as part of our
1913 * reuse chunk, then don't send this object either. The base
1914 * would come after us, along with other objects not
1915 * necessarily in the pack, which means we'd need to convert
1916 * to REF_DELTA on the fly. Better to just let the normal
1917 * object_entry code path handle it.
1919 if (!bitmap_get(reuse
, base_bitmap_pos
))
1924 * If we got here, then the object is OK to reuse. Mark it.
1926 bitmap_set(reuse
, bitmap_pos
);
1930 static void reuse_partial_packfile_from_bitmap_1(struct bitmap_index
*bitmap_git
,
1931 struct bitmapped_pack
*pack
,
1932 struct bitmap
*reuse
)
1934 struct bitmap
*result
= bitmap_git
->result
;
1935 struct pack_window
*w_curs
= NULL
;
1936 size_t pos
= pack
->bitmap_pos
/ BITS_IN_EWORD
;
1938 if (!pack
->bitmap_pos
) {
1940 * If we're processing the first (in the case of a MIDX, the
1941 * preferred pack) or the only (in the case of single-pack
1942 * bitmaps) pack, then we can reuse whole words at a time.
1944 * This is because we know that any deltas in this range *must*
1945 * have their bases chosen from the same pack, since:
1947 * - In the single pack case, there is no other pack to choose
1950 * - In the MIDX case, the first pack is the preferred pack, so
1951 * all ties are broken in favor of that pack (i.e. the one
1952 * we're currently processing). So any duplicate bases will be
1953 * resolved in favor of the pack we're processing.
1955 while (pos
< result
->word_alloc
&&
1956 pos
< pack
->bitmap_nr
/ BITS_IN_EWORD
&&
1957 result
->words
[pos
] == (eword_t
)~0)
1959 memset(reuse
->words
, 0xFF, pos
* sizeof(eword_t
));
1962 for (; pos
< result
->word_alloc
; pos
++) {
1963 eword_t word
= result
->words
[pos
];
1966 for (offset
= 0; offset
< BITS_IN_EWORD
; offset
++) {
1970 if (word
>> offset
== 0)
1973 offset
+= ewah_bit_ctz64(word
>> offset
);
1975 bit_pos
= pos
* BITS_IN_EWORD
+ offset
;
1976 if (bit_pos
< pack
->bitmap_pos
)
1978 if (bit_pos
>= pack
->bitmap_pos
+ pack
->bitmap_nr
)
1981 if (bitmap_is_midx(bitmap_git
)) {
1985 midx_pos
= pack_pos_to_midx(bitmap_git
->midx
, bit_pos
);
1986 ofs
= nth_midxed_offset(bitmap_git
->midx
, midx_pos
);
1988 if (offset_to_pack_pos(pack
->p
, ofs
, &pack_pos
) < 0)
1989 BUG("could not find object in pack %s "
1990 "at offset %"PRIuMAX
" in MIDX",
1991 pack_basename(pack
->p
), (uintmax_t)ofs
);
1993 pack_pos
= cast_size_t_to_uint32_t(st_sub(bit_pos
, pack
->bitmap_pos
));
1994 if (pack_pos
>= pack
->p
->num_objects
)
1995 BUG("advanced beyond the end of pack %s (%"PRIuMAX
" > %"PRIu32
")",
1996 pack_basename(pack
->p
), (uintmax_t)pack_pos
,
1997 pack
->p
->num_objects
);
2000 if (try_partial_reuse(bitmap_git
, pack
, bit_pos
,
2001 pack_pos
, reuse
, &w_curs
) < 0) {
2003 * try_partial_reuse indicated we couldn't reuse
2004 * any bits, so there is no point in trying more
2005 * bits in the current word, or any other words
2008 * Jump out of both loops to avoid future
2009 * unnecessary calls to try_partial_reuse.
2017 unuse_pack(&w_curs
);
2020 static int bitmapped_pack_cmp(const void *va
, const void *vb
)
2022 const struct bitmapped_pack
*a
= va
;
2023 const struct bitmapped_pack
*b
= vb
;
2025 if (a
->bitmap_pos
< b
->bitmap_pos
)
2027 if (a
->bitmap_pos
> b
->bitmap_pos
)
2032 void reuse_partial_packfile_from_bitmap(struct bitmap_index
*bitmap_git
,
2033 struct bitmapped_pack
**packs_out
,
2034 size_t *packs_nr_out
,
2035 struct bitmap
**reuse_out
,
2036 int multi_pack_reuse
)
2038 struct repository
*r
= the_repository
;
2039 struct bitmapped_pack
*packs
= NULL
;
2040 struct bitmap
*result
= bitmap_git
->result
;
2041 struct bitmap
*reuse
;
2043 size_t packs_nr
= 0, packs_alloc
= 0;
2045 uint32_t objects_nr
= 0;
2049 load_reverse_index(r
, bitmap_git
);
2051 if (!bitmap_is_midx(bitmap_git
) || !bitmap_git
->midx
->chunk_bitmapped_packs
)
2052 multi_pack_reuse
= 0;
2054 if (multi_pack_reuse
) {
2055 for (i
= 0; i
< bitmap_git
->midx
->num_packs
; i
++) {
2056 struct bitmapped_pack pack
;
2057 if (nth_bitmapped_pack(r
, bitmap_git
->midx
, &pack
, i
) < 0) {
2058 warning(_("unable to load pack: '%s', disabling pack-reuse"),
2059 bitmap_git
->midx
->pack_names
[i
]);
2064 if (!pack
.bitmap_nr
)
2067 ALLOC_GROW(packs
, packs_nr
+ 1, packs_alloc
);
2068 memcpy(&packs
[packs_nr
++], &pack
, sizeof(pack
));
2070 objects_nr
+= pack
.p
->num_objects
;
2073 QSORT(packs
, packs_nr
, bitmapped_pack_cmp
);
2075 struct packed_git
*pack
;
2076 uint32_t pack_int_id
;
2078 if (bitmap_is_midx(bitmap_git
)) {
2079 uint32_t preferred_pack_pos
;
2081 if (midx_preferred_pack(bitmap_git
->midx
, &preferred_pack_pos
) < 0) {
2082 warning(_("unable to compute preferred pack, disabling pack-reuse"));
2086 pack
= bitmap_git
->midx
->packs
[preferred_pack_pos
];
2087 pack_int_id
= preferred_pack_pos
;
2089 pack
= bitmap_git
->pack
;
2091 * Any value for 'pack_int_id' will do here. When we
2092 * process the pack via try_partial_reuse(), we won't
2093 * use the `pack_int_id` field since we have a non-MIDX
2096 * Use '-1' as a sentinel value to make it clear
2097 * that we do not expect to read this field.
2102 ALLOC_GROW(packs
, packs_nr
+ 1, packs_alloc
);
2103 packs
[packs_nr
].p
= pack
;
2104 packs
[packs_nr
].pack_int_id
= pack_int_id
;
2105 packs
[packs_nr
].bitmap_nr
= pack
->num_objects
;
2106 packs
[packs_nr
].bitmap_pos
= 0;
2108 objects_nr
= packs
[packs_nr
++].bitmap_nr
;
2111 word_alloc
= objects_nr
/ BITS_IN_EWORD
;
2112 if (objects_nr
% BITS_IN_EWORD
)
2114 reuse
= bitmap_word_alloc(word_alloc
);
2116 for (i
= 0; i
< packs_nr
; i
++)
2117 reuse_partial_packfile_from_bitmap_1(bitmap_git
, &packs
[i
], reuse
);
2119 if (bitmap_is_empty(reuse
)) {
2126 * Drop any reused objects from the result, since they will not
2127 * need to be handled separately.
2129 bitmap_and_not(result
, reuse
);
2131 *packs_nr_out
= packs_nr
;
2135 int bitmap_walk_contains(struct bitmap_index
*bitmap_git
,
2136 struct bitmap
*bitmap
, const struct object_id
*oid
)
2143 idx
= bitmap_position(bitmap_git
, oid
);
2144 return idx
>= 0 && bitmap_get(bitmap
, idx
);
2147 void traverse_bitmap_commit_list(struct bitmap_index
*bitmap_git
,
2148 struct rev_info
*revs
,
2149 show_reachable_fn show_reachable
)
2151 assert(bitmap_git
->result
);
2153 show_objects_for_type(bitmap_git
, OBJ_COMMIT
, show_reachable
);
2154 if (revs
->tree_objects
)
2155 show_objects_for_type(bitmap_git
, OBJ_TREE
, show_reachable
);
2156 if (revs
->blob_objects
)
2157 show_objects_for_type(bitmap_git
, OBJ_BLOB
, show_reachable
);
2158 if (revs
->tag_objects
)
2159 show_objects_for_type(bitmap_git
, OBJ_TAG
, show_reachable
);
2161 show_extended_objects(bitmap_git
, revs
, show_reachable
);
2164 static uint32_t count_object_type(struct bitmap_index
*bitmap_git
,
2165 enum object_type type
)
2167 struct bitmap
*objects
= bitmap_git
->result
;
2168 struct eindex
*eindex
= &bitmap_git
->ext_index
;
2170 uint32_t i
= 0, count
= 0;
2171 struct ewah_iterator it
;
2174 init_type_iterator(&it
, bitmap_git
, type
);
2176 while (i
< objects
->word_alloc
&& ewah_iterator_next(&filter
, &it
)) {
2177 eword_t word
= objects
->words
[i
++] & filter
;
2178 count
+= ewah_bit_popcount64(word
);
2181 for (i
= 0; i
< eindex
->count
; ++i
) {
2182 if (eindex
->objects
[i
]->type
== type
&&
2184 st_add(bitmap_num_objects(bitmap_git
), i
)))
2191 void count_bitmap_commit_list(struct bitmap_index
*bitmap_git
,
2192 uint32_t *commits
, uint32_t *trees
,
2193 uint32_t *blobs
, uint32_t *tags
)
2195 assert(bitmap_git
->result
);
2198 *commits
= count_object_type(bitmap_git
, OBJ_COMMIT
);
2201 *trees
= count_object_type(bitmap_git
, OBJ_TREE
);
2204 *blobs
= count_object_type(bitmap_git
, OBJ_BLOB
);
2207 *tags
= count_object_type(bitmap_git
, OBJ_TAG
);
2210 struct bitmap_test_data
{
2211 struct bitmap_index
*bitmap_git
;
2212 struct bitmap
*base
;
2213 struct bitmap
*commits
;
2214 struct bitmap
*trees
;
2215 struct bitmap
*blobs
;
2216 struct bitmap
*tags
;
2217 struct progress
*prg
;
2221 static void test_bitmap_type(struct bitmap_test_data
*tdata
,
2222 struct object
*obj
, int pos
)
2224 enum object_type bitmap_type
= OBJ_NONE
;
2227 if (bitmap_get(tdata
->commits
, pos
)) {
2228 bitmap_type
= OBJ_COMMIT
;
2231 if (bitmap_get(tdata
->trees
, pos
)) {
2232 bitmap_type
= OBJ_TREE
;
2235 if (bitmap_get(tdata
->blobs
, pos
)) {
2236 bitmap_type
= OBJ_BLOB
;
2239 if (bitmap_get(tdata
->tags
, pos
)) {
2240 bitmap_type
= OBJ_TAG
;
2244 if (bitmap_type
== OBJ_NONE
)
2245 die(_("object '%s' not found in type bitmaps"),
2246 oid_to_hex(&obj
->oid
));
2249 die(_("object '%s' does not have a unique type"),
2250 oid_to_hex(&obj
->oid
));
2252 if (bitmap_type
!= obj
->type
)
2253 die(_("object '%s': real type '%s', expected: '%s'"),
2254 oid_to_hex(&obj
->oid
),
2255 type_name(obj
->type
),
2256 type_name(bitmap_type
));
2259 static void test_show_object(struct object
*object
,
2260 const char *name UNUSED
,
2263 struct bitmap_test_data
*tdata
= data
;
2266 bitmap_pos
= bitmap_position(tdata
->bitmap_git
, &object
->oid
);
2268 die(_("object not in bitmap: '%s'"), oid_to_hex(&object
->oid
));
2269 test_bitmap_type(tdata
, object
, bitmap_pos
);
2271 bitmap_set(tdata
->base
, bitmap_pos
);
2272 display_progress(tdata
->prg
, ++tdata
->seen
);
2275 static void test_show_commit(struct commit
*commit
, void *data
)
2277 struct bitmap_test_data
*tdata
= data
;
2280 bitmap_pos
= bitmap_position(tdata
->bitmap_git
,
2281 &commit
->object
.oid
);
2283 die(_("object not in bitmap: '%s'"), oid_to_hex(&commit
->object
.oid
));
2284 test_bitmap_type(tdata
, &commit
->object
, bitmap_pos
);
2286 bitmap_set(tdata
->base
, bitmap_pos
);
2287 display_progress(tdata
->prg
, ++tdata
->seen
);
2290 void test_bitmap_walk(struct rev_info
*revs
)
2292 struct object
*root
;
2293 struct bitmap
*result
= NULL
;
2294 size_t result_popcnt
;
2295 struct bitmap_test_data tdata
;
2296 struct bitmap_index
*bitmap_git
;
2297 struct ewah_bitmap
*bm
;
2299 if (!(bitmap_git
= prepare_bitmap_git(revs
->repo
)))
2300 die(_("failed to load bitmap indexes"));
2302 if (revs
->pending
.nr
!= 1)
2303 die(_("you must specify exactly one commit to test"));
2305 fprintf_ln(stderr
, "Bitmap v%d test (%d entries%s)",
2306 bitmap_git
->version
,
2307 bitmap_git
->entry_count
,
2308 bitmap_git
->table_lookup
? "" : " loaded");
2310 root
= revs
->pending
.objects
[0].item
;
2311 bm
= bitmap_for_commit(bitmap_git
, (struct commit
*)root
);
2314 fprintf_ln(stderr
, "Found bitmap for '%s'. %d bits / %08x checksum",
2315 oid_to_hex(&root
->oid
), (int)bm
->bit_size
, ewah_checksum(bm
));
2317 result
= ewah_to_bitmap(bm
);
2321 die(_("commit '%s' doesn't have an indexed bitmap"), oid_to_hex(&root
->oid
));
2323 revs
->tag_objects
= 1;
2324 revs
->tree_objects
= 1;
2325 revs
->blob_objects
= 1;
2327 result_popcnt
= bitmap_popcount(result
);
2329 if (prepare_revision_walk(revs
))
2330 die(_("revision walk setup failed"));
2332 tdata
.bitmap_git
= bitmap_git
;
2333 tdata
.base
= bitmap_new();
2334 tdata
.commits
= ewah_to_bitmap(bitmap_git
->commits
);
2335 tdata
.trees
= ewah_to_bitmap(bitmap_git
->trees
);
2336 tdata
.blobs
= ewah_to_bitmap(bitmap_git
->blobs
);
2337 tdata
.tags
= ewah_to_bitmap(bitmap_git
->tags
);
2338 tdata
.prg
= start_progress("Verifying bitmap entries", result_popcnt
);
2341 traverse_commit_list(revs
, &test_show_commit
, &test_show_object
, &tdata
);
2343 stop_progress(&tdata
.prg
);
2345 if (bitmap_equals(result
, tdata
.base
))
2346 fprintf_ln(stderr
, "OK!");
2348 die(_("mismatch in bitmap results"));
2350 bitmap_free(result
);
2351 bitmap_free(tdata
.base
);
2352 bitmap_free(tdata
.commits
);
2353 bitmap_free(tdata
.trees
);
2354 bitmap_free(tdata
.blobs
);
2355 bitmap_free(tdata
.tags
);
2356 free_bitmap_index(bitmap_git
);
2359 int test_bitmap_commits(struct repository
*r
)
2361 struct object_id oid
;
2362 MAYBE_UNUSED
void *value
;
2363 struct bitmap_index
*bitmap_git
= prepare_bitmap_git(r
);
2366 die(_("failed to load bitmap indexes"));
2369 * As this function is only used to print bitmap selected
2370 * commits, we don't have to read the commit table.
2372 if (bitmap_git
->table_lookup
) {
2373 if (load_bitmap_entries_v1(bitmap_git
) < 0)
2374 die(_("failed to load bitmap indexes"));
2377 kh_foreach(bitmap_git
->bitmaps
, oid
, value
, {
2378 printf_ln("%s", oid_to_hex(&oid
));
2381 free_bitmap_index(bitmap_git
);
2386 int test_bitmap_hashes(struct repository
*r
)
2388 struct bitmap_index
*bitmap_git
= prepare_bitmap_git(r
);
2389 struct object_id oid
;
2390 uint32_t i
, index_pos
;
2392 if (!bitmap_git
|| !bitmap_git
->hashes
)
2395 for (i
= 0; i
< bitmap_num_objects(bitmap_git
); i
++) {
2396 if (bitmap_is_midx(bitmap_git
))
2397 index_pos
= pack_pos_to_midx(bitmap_git
->midx
, i
);
2399 index_pos
= pack_pos_to_index(bitmap_git
->pack
, i
);
2401 nth_bitmap_object_oid(bitmap_git
, &oid
, index_pos
);
2403 printf_ln("%s %"PRIu32
"",
2404 oid_to_hex(&oid
), get_be32(bitmap_git
->hashes
+ index_pos
));
2408 free_bitmap_index(bitmap_git
);
2413 int rebuild_bitmap(const uint32_t *reposition
,
2414 struct ewah_bitmap
*source
,
2415 struct bitmap
*dest
)
2418 struct ewah_iterator it
;
2421 ewah_iterator_init(&it
, source
);
2423 while (ewah_iterator_next(&word
, &it
)) {
2424 uint32_t offset
, bit_pos
;
2426 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
2427 if ((word
>> offset
) == 0)
2430 offset
+= ewah_bit_ctz64(word
>> offset
);
2432 bit_pos
= reposition
[pos
+ offset
];
2434 bitmap_set(dest
, bit_pos
- 1);
2435 else /* can't reuse, we don't have the object */
2439 pos
+= BITS_IN_EWORD
;
2444 uint32_t *create_bitmap_mapping(struct bitmap_index
*bitmap_git
,
2445 struct packing_data
*mapping
)
2447 struct repository
*r
= the_repository
;
2448 uint32_t i
, num_objects
;
2449 uint32_t *reposition
;
2451 if (!bitmap_is_midx(bitmap_git
))
2452 load_reverse_index(r
, bitmap_git
);
2453 else if (load_midx_revindex(bitmap_git
->midx
))
2454 BUG("rebuild_existing_bitmaps: missing required rev-cache "
2457 num_objects
= bitmap_num_objects(bitmap_git
);
2458 CALLOC_ARRAY(reposition
, num_objects
);
2460 for (i
= 0; i
< num_objects
; ++i
) {
2461 struct object_id oid
;
2462 struct object_entry
*oe
;
2465 if (bitmap_is_midx(bitmap_git
))
2466 index_pos
= pack_pos_to_midx(bitmap_git
->midx
, i
);
2468 index_pos
= pack_pos_to_index(bitmap_git
->pack
, i
);
2469 nth_bitmap_object_oid(bitmap_git
, &oid
, index_pos
);
2470 oe
= packlist_find(mapping
, &oid
);
2473 reposition
[i
] = oe_in_pack_pos(mapping
, oe
) + 1;
2474 if (bitmap_git
->hashes
&& !oe
->hash
)
2475 oe
->hash
= get_be32(bitmap_git
->hashes
+ index_pos
);
2482 void free_bitmap_index(struct bitmap_index
*b
)
2488 munmap(b
->map
, b
->map_size
);
2489 ewah_pool_free(b
->commits
);
2490 ewah_pool_free(b
->trees
);
2491 ewah_pool_free(b
->blobs
);
2492 ewah_pool_free(b
->tags
);
2494 struct stored_bitmap
*sb
;
2495 kh_foreach_value(b
->bitmaps
, sb
, {
2496 ewah_pool_free(sb
->root
);
2500 kh_destroy_oid_map(b
->bitmaps
);
2501 free(b
->ext_index
.objects
);
2502 free(b
->ext_index
.hashes
);
2503 kh_destroy_oid_pos(b
->ext_index
.positions
);
2504 bitmap_free(b
->result
);
2505 bitmap_free(b
->haves
);
2506 if (bitmap_is_midx(b
)) {
2508 * Multi-pack bitmaps need to have resources associated with
2509 * their on-disk reverse indexes unmapped so that stale .rev and
2510 * .bitmap files can be removed.
2512 * Unlike pack-based bitmaps, multi-pack bitmaps can be read and
2513 * written in the same 'git multi-pack-index write --bitmap'
2514 * process. Close resources so they can be removed safely on
2515 * platforms like Windows.
2517 close_midx_revindex(b
->midx
);
2522 int bitmap_has_oid_in_uninteresting(struct bitmap_index
*bitmap_git
,
2523 const struct object_id
*oid
)
2525 return bitmap_git
&&
2526 bitmap_walk_contains(bitmap_git
, bitmap_git
->haves
, oid
);
2529 static off_t
get_disk_usage_for_type(struct bitmap_index
*bitmap_git
,
2530 enum object_type object_type
)
2532 struct bitmap
*result
= bitmap_git
->result
;
2534 struct ewah_iterator it
;
2538 init_type_iterator(&it
, bitmap_git
, object_type
);
2539 for (i
= 0; i
< result
->word_alloc
&&
2540 ewah_iterator_next(&filter
, &it
); i
++) {
2541 eword_t word
= result
->words
[i
] & filter
;
2542 size_t base
= (i
* BITS_IN_EWORD
);
2548 for (offset
= 0; offset
< BITS_IN_EWORD
; offset
++) {
2549 if ((word
>> offset
) == 0)
2552 offset
+= ewah_bit_ctz64(word
>> offset
);
2554 if (bitmap_is_midx(bitmap_git
)) {
2556 uint32_t midx_pos
= pack_pos_to_midx(bitmap_git
->midx
, base
+ offset
);
2557 off_t offset
= nth_midxed_offset(bitmap_git
->midx
, midx_pos
);
2559 uint32_t pack_id
= nth_midxed_pack_int_id(bitmap_git
->midx
, midx_pos
);
2560 struct packed_git
*pack
= bitmap_git
->midx
->packs
[pack_id
];
2562 if (offset_to_pack_pos(pack
, offset
, &pack_pos
) < 0) {
2563 struct object_id oid
;
2564 nth_midxed_object_oid(&oid
, bitmap_git
->midx
, midx_pos
);
2566 die(_("could not find '%s' in pack '%s' at offset %"PRIuMAX
),
2572 total
+= pack_pos_to_offset(pack
, pack_pos
+ 1) - offset
;
2574 size_t pos
= base
+ offset
;
2575 total
+= pack_pos_to_offset(bitmap_git
->pack
, pos
+ 1) -
2576 pack_pos_to_offset(bitmap_git
->pack
, pos
);
2584 static off_t
get_disk_usage_for_extended(struct bitmap_index
*bitmap_git
)
2586 struct bitmap
*result
= bitmap_git
->result
;
2587 struct eindex
*eindex
= &bitmap_git
->ext_index
;
2589 struct object_info oi
= OBJECT_INFO_INIT
;
2593 oi
.disk_sizep
= &object_size
;
2595 for (i
= 0; i
< eindex
->count
; i
++) {
2596 struct object
*obj
= eindex
->objects
[i
];
2598 if (!bitmap_get(result
,
2599 st_add(bitmap_num_objects(bitmap_git
), i
)))
2602 if (oid_object_info_extended(the_repository
, &obj
->oid
, &oi
, 0) < 0)
2603 die(_("unable to get disk usage of '%s'"),
2604 oid_to_hex(&obj
->oid
));
2606 total
+= object_size
;
2611 off_t
get_disk_usage_from_bitmap(struct bitmap_index
*bitmap_git
,
2612 struct rev_info
*revs
)
2616 total
+= get_disk_usage_for_type(bitmap_git
, OBJ_COMMIT
);
2617 if (revs
->tree_objects
)
2618 total
+= get_disk_usage_for_type(bitmap_git
, OBJ_TREE
);
2619 if (revs
->blob_objects
)
2620 total
+= get_disk_usage_for_type(bitmap_git
, OBJ_BLOB
);
2621 if (revs
->tag_objects
)
2622 total
+= get_disk_usage_for_type(bitmap_git
, OBJ_TAG
);
2624 total
+= get_disk_usage_for_extended(bitmap_git
);
2629 int bitmap_is_midx(struct bitmap_index
*bitmap_git
)
2631 return !!bitmap_git
->midx
;
2634 const struct string_list
*bitmap_preferred_tips(struct repository
*r
)
2636 const struct string_list
*dest
;
2638 if (!repo_config_get_string_multi(r
, "pack.preferbitmaptips", &dest
))
2643 int bitmap_is_preferred_refname(struct repository
*r
, const char *refname
)
2645 const struct string_list
*preferred_tips
= bitmap_preferred_tips(r
);
2646 struct string_list_item
*item
;
2648 if (!preferred_tips
)
2651 for_each_string_list_item(item
, preferred_tips
) {
2652 if (starts_with(refname
, item
->string
))
2659 static int verify_bitmap_file(const char *name
)
2662 unsigned char *data
;
2663 int fd
= git_open(name
);
2666 /* It is OK to not have the file. */
2667 if (fd
< 0 || fstat(fd
, &st
)) {
2673 data
= xmmap(NULL
, st
.st_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
2675 if (!hashfile_checksum_valid(data
, st
.st_size
))
2676 res
= error(_("bitmap file '%s' has invalid checksum"),
2679 munmap(data
, st
.st_size
);
2683 int verify_bitmap_files(struct repository
*r
)
2687 for (struct multi_pack_index
*m
= get_multi_pack_index(r
);
2689 char *midx_bitmap_name
= midx_bitmap_filename(m
);
2690 res
|= verify_bitmap_file(midx_bitmap_name
);
2691 free(midx_bitmap_name
);
2694 for (struct packed_git
*p
= get_all_packs(r
);
2696 char *pack_bitmap_name
= pack_bitmap_filename(p
);
2697 res
|= verify_bitmap_file(pack_bitmap_name
);
2698 free(pack_bitmap_name
);