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"
23 #include "pseudo-merge.h"
26 * An entry on the bitmap index, representing the bitmap for a given
29 struct stored_bitmap
{
31 struct ewah_bitmap
*root
;
32 struct stored_bitmap
*xor;
37 * The active bitmap index for a repository. By design, repositories only have
38 * a single bitmap index available (the index for the biggest packfile in
39 * the repository), since bitmap indexes need full closure.
41 * If there is more than one bitmap index available (e.g. because of alternates),
42 * the active bitmap index is the largest one.
46 * The pack or multi-pack index (MIDX) that this bitmap index belongs
49 * Exactly one of these must be non-NULL; this specifies the object
50 * order used to interpret this bitmap.
52 struct packed_git
*pack
;
53 struct multi_pack_index
*midx
;
55 /* mmapped buffer of the whole bitmap index */
57 size_t map_size
; /* size of the mmaped buffer */
58 size_t map_pos
; /* current position when loading the index */
63 * Each bitmap marks which objects in the packfile are of the given
64 * type. This provides type information when yielding the objects from
65 * the packfile during a walk, which allows for better delta bases.
67 struct ewah_bitmap
*commits
;
68 struct ewah_bitmap
*trees
;
69 struct ewah_bitmap
*blobs
;
70 struct ewah_bitmap
*tags
;
72 /* Map from object ID -> `stored_bitmap` for all the bitmapped commits */
73 kh_oid_map_t
*bitmaps
;
75 /* Number of bitmapped commits */
78 /* If not NULL, this is a name-hash cache pointing into map. */
81 /* The checksum of the packfile or MIDX; points into map. */
82 const unsigned char *checksum
;
85 * If not NULL, this point into the commit table extension
86 * (within the memory mapped region `map`).
88 unsigned char *table_lookup
;
90 /* This contains the pseudo-merge cache within 'map' (if found). */
91 struct pseudo_merge_map pseudo_merges
;
96 * When trying to perform bitmap operations with objects that are not
97 * packed in `pack`, these objects are added to this "fake index" and
98 * are assumed to appear at the end of the packfile for all operations
101 struct object
**objects
;
103 uint32_t count
, alloc
;
104 kh_oid_pos_t
*positions
;
107 /* Bitmap result of the last performed walk */
108 struct bitmap
*result
;
110 /* "have" bitmap from the last performed walk */
111 struct bitmap
*haves
;
113 /* Version of the bitmap index */
114 unsigned int version
;
117 static int pseudo_merges_satisfied_nr
;
118 static int pseudo_merges_cascades_nr
;
119 static int existing_bitmaps_hits_nr
;
120 static int existing_bitmaps_misses_nr
;
121 static int roots_with_bitmaps_nr
;
122 static int roots_without_bitmaps_nr
;
124 static struct ewah_bitmap
*lookup_stored_bitmap(struct stored_bitmap
*st
)
126 struct ewah_bitmap
*parent
;
127 struct ewah_bitmap
*composed
;
132 composed
= ewah_pool_new();
133 parent
= lookup_stored_bitmap(st
->xor);
134 ewah_xor(st
->root
, parent
, composed
);
136 ewah_pool_free(st
->root
);
143 struct ewah_bitmap
*read_bitmap(const unsigned char *map
,
144 size_t map_size
, size_t *map_pos
)
146 struct ewah_bitmap
*b
= ewah_pool_new();
148 ssize_t bitmap_size
= ewah_read_mmap(b
, map
+ *map_pos
,
149 map_size
- *map_pos
);
151 if (bitmap_size
< 0) {
152 error(_("failed to load bitmap index (corrupted?)"));
157 *map_pos
+= bitmap_size
;
163 * Read a bitmap from the current read position on the mmaped
164 * index, and increase the read position accordingly
166 static struct ewah_bitmap
*read_bitmap_1(struct bitmap_index
*index
)
168 return read_bitmap(index
->map
, index
->map_size
, &index
->map_pos
);
171 static uint32_t bitmap_num_objects(struct bitmap_index
*index
)
174 return index
->midx
->num_objects
;
175 return index
->pack
->num_objects
;
178 static int load_bitmap_header(struct bitmap_index
*index
)
180 struct bitmap_disk_header
*header
= (void *)index
->map
;
181 size_t header_size
= sizeof(*header
) - GIT_MAX_RAWSZ
+ the_hash_algo
->rawsz
;
183 if (index
->map_size
< header_size
+ the_hash_algo
->rawsz
)
184 return error(_("corrupted bitmap index (too small)"));
186 if (memcmp(header
->magic
, BITMAP_IDX_SIGNATURE
, sizeof(BITMAP_IDX_SIGNATURE
)) != 0)
187 return error(_("corrupted bitmap index file (wrong header)"));
189 index
->version
= ntohs(header
->version
);
190 if (index
->version
!= 1)
191 return error(_("unsupported version '%d' for bitmap index file"), index
->version
);
193 /* Parse known bitmap format options */
195 uint32_t flags
= ntohs(header
->options
);
196 size_t cache_size
= st_mult(bitmap_num_objects(index
), sizeof(uint32_t));
197 unsigned char *index_end
= index
->map
+ index
->map_size
- the_hash_algo
->rawsz
;
199 if ((flags
& BITMAP_OPT_FULL_DAG
) == 0)
200 BUG("unsupported options for bitmap index file "
201 "(Git requires BITMAP_OPT_FULL_DAG)");
203 if (flags
& BITMAP_OPT_HASH_CACHE
) {
204 if (cache_size
> index_end
- index
->map
- header_size
)
205 return error(_("corrupted bitmap index file (too short to fit hash cache)"));
206 index
->hashes
= (void *)(index_end
- cache_size
);
207 index_end
-= cache_size
;
210 if (flags
& BITMAP_OPT_LOOKUP_TABLE
) {
211 size_t table_size
= st_mult(ntohl(header
->entry_count
),
212 BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH
);
213 if (table_size
> index_end
- index
->map
- header_size
)
214 return error(_("corrupted bitmap index file (too short to fit lookup table)"));
215 if (git_env_bool("GIT_TEST_READ_COMMIT_TABLE", 1))
216 index
->table_lookup
= (void *)(index_end
- table_size
);
217 index_end
-= table_size
;
220 if (flags
& BITMAP_OPT_PSEUDO_MERGES
) {
221 unsigned char *pseudo_merge_ofs
;
225 if (sizeof(table_size
) > index_end
- index
->map
- header_size
)
226 return error(_("corrupted bitmap index file (too short to fit pseudo-merge table header)"));
228 table_size
= get_be64(index_end
- 8);
229 if (table_size
> index_end
- index
->map
- header_size
)
230 return error(_("corrupted bitmap index file (too short to fit pseudo-merge table)"));
232 if (git_env_bool("GIT_TEST_USE_PSEUDO_MERGES", 1)) {
233 const unsigned char *ext
= (index_end
- table_size
);
235 index
->pseudo_merges
.map
= index
->map
;
236 index
->pseudo_merges
.map_size
= index
->map_size
;
237 index
->pseudo_merges
.commits
= ext
+ get_be64(index_end
- 16);
238 index
->pseudo_merges
.commits_nr
= get_be32(index_end
- 20);
239 index
->pseudo_merges
.nr
= get_be32(index_end
- 24);
241 CALLOC_ARRAY(index
->pseudo_merges
.v
,
242 index
->pseudo_merges
.nr
);
244 pseudo_merge_ofs
= index_end
- 24 -
245 (index
->pseudo_merges
.nr
* sizeof(uint64_t));
246 for (i
= 0; i
< index
->pseudo_merges
.nr
; i
++) {
247 index
->pseudo_merges
.v
[i
].at
= get_be64(pseudo_merge_ofs
);
248 pseudo_merge_ofs
+= sizeof(uint64_t);
252 index_end
-= table_size
;
256 index
->entry_count
= ntohl(header
->entry_count
);
257 index
->checksum
= header
->checksum
;
258 index
->map_pos
+= header_size
;
262 static struct stored_bitmap
*store_bitmap(struct bitmap_index
*index
,
263 struct ewah_bitmap
*root
,
264 const struct object_id
*oid
,
265 struct stored_bitmap
*xor_with
,
268 struct stored_bitmap
*stored
;
272 stored
= xmalloc(sizeof(struct stored_bitmap
));
274 stored
->xor = xor_with
;
275 stored
->flags
= flags
;
276 oidcpy(&stored
->oid
, oid
);
278 hash_pos
= kh_put_oid_map(index
->bitmaps
, stored
->oid
, &ret
);
281 * A 0 return code means the insertion succeeded with no changes,
282 * because the SHA1 already existed on the map. This is bad, there
283 * shouldn't be duplicated commits in the index.
286 error(_("duplicate entry in bitmap index: '%s'"), oid_to_hex(oid
));
290 kh_value(index
->bitmaps
, hash_pos
) = stored
;
294 static inline uint32_t read_be32(const unsigned char *buffer
, size_t *pos
)
296 uint32_t result
= get_be32(buffer
+ *pos
);
297 (*pos
) += sizeof(result
);
301 static inline uint8_t read_u8(const unsigned char *buffer
, size_t *pos
)
303 return buffer
[(*pos
)++];
306 #define MAX_XOR_OFFSET 160
308 static int nth_bitmap_object_oid(struct bitmap_index
*index
,
309 struct object_id
*oid
,
313 return nth_midxed_object_oid(oid
, index
->midx
, n
) ? 0 : -1;
314 return nth_packed_object_id(oid
, index
->pack
, n
);
317 static int load_bitmap_entries_v1(struct bitmap_index
*index
)
320 struct stored_bitmap
*recent_bitmaps
[MAX_XOR_OFFSET
] = { NULL
};
322 for (i
= 0; i
< index
->entry_count
; ++i
) {
323 int xor_offset
, flags
;
324 struct ewah_bitmap
*bitmap
= NULL
;
325 struct stored_bitmap
*xor_bitmap
= NULL
;
326 uint32_t commit_idx_pos
;
327 struct object_id oid
;
329 if (index
->map_size
- index
->map_pos
< 6)
330 return error(_("corrupt ewah bitmap: truncated header for entry %d"), i
);
332 commit_idx_pos
= read_be32(index
->map
, &index
->map_pos
);
333 xor_offset
= read_u8(index
->map
, &index
->map_pos
);
334 flags
= read_u8(index
->map
, &index
->map_pos
);
336 if (nth_bitmap_object_oid(index
, &oid
, commit_idx_pos
) < 0)
337 return error(_("corrupt ewah bitmap: commit index %u out of range"),
338 (unsigned)commit_idx_pos
);
340 bitmap
= read_bitmap_1(index
);
344 if (xor_offset
> MAX_XOR_OFFSET
|| xor_offset
> i
)
345 return error(_("corrupted bitmap pack index"));
347 if (xor_offset
> 0) {
348 xor_bitmap
= recent_bitmaps
[(i
- xor_offset
) % MAX_XOR_OFFSET
];
351 return error(_("invalid XOR offset in bitmap pack index"));
354 recent_bitmaps
[i
% MAX_XOR_OFFSET
] = store_bitmap(
355 index
, bitmap
, &oid
, xor_bitmap
, flags
);
361 char *midx_bitmap_filename(struct multi_pack_index
*midx
)
363 struct strbuf buf
= STRBUF_INIT
;
364 get_midx_filename_ext(&buf
, midx
->object_dir
, get_midx_checksum(midx
),
367 return strbuf_detach(&buf
, NULL
);
370 char *pack_bitmap_filename(struct packed_git
*p
)
374 if (!strip_suffix(p
->pack_name
, ".pack", &len
))
375 BUG("pack_name does not end in .pack");
376 return xstrfmt("%.*s.bitmap", (int)len
, p
->pack_name
);
379 static int open_midx_bitmap_1(struct bitmap_index
*bitmap_git
,
380 struct multi_pack_index
*midx
)
383 char *bitmap_name
= midx_bitmap_filename(midx
);
384 int fd
= git_open(bitmap_name
);
385 uint32_t i
, preferred_pack
;
386 struct packed_git
*preferred
;
390 warning_errno("cannot open '%s'", bitmap_name
);
396 if (fstat(fd
, &st
)) {
397 error_errno(_("cannot fstat bitmap file"));
402 if (bitmap_git
->pack
|| bitmap_git
->midx
) {
403 struct strbuf buf
= STRBUF_INIT
;
404 get_midx_filename(&buf
, midx
->object_dir
);
405 trace2_data_string("bitmap", the_repository
,
406 "ignoring extra midx bitmap file", buf
.buf
);
408 strbuf_release(&buf
);
412 bitmap_git
->midx
= midx
;
413 bitmap_git
->map_size
= xsize_t(st
.st_size
);
414 bitmap_git
->map_pos
= 0;
415 bitmap_git
->map
= xmmap(NULL
, bitmap_git
->map_size
, PROT_READ
,
419 if (load_bitmap_header(bitmap_git
) < 0)
422 if (!hasheq(get_midx_checksum(bitmap_git
->midx
), bitmap_git
->checksum
)) {
423 error(_("checksum doesn't match in MIDX and bitmap"));
427 if (load_midx_revindex(bitmap_git
->midx
)) {
428 warning(_("multi-pack bitmap is missing required reverse index"));
432 for (i
= 0; i
< bitmap_git
->midx
->num_packs
; i
++) {
433 if (prepare_midx_pack(the_repository
, bitmap_git
->midx
, i
)) {
434 warning(_("could not open pack %s"),
435 bitmap_git
->midx
->pack_names
[i
]);
440 if (midx_preferred_pack(bitmap_git
->midx
, &preferred_pack
) < 0) {
441 warning(_("could not determine MIDX preferred pack"));
445 preferred
= bitmap_git
->midx
->packs
[preferred_pack
];
446 if (!is_pack_valid(preferred
)) {
447 warning(_("preferred pack (%s) is invalid"),
448 preferred
->pack_name
);
455 munmap(bitmap_git
->map
, bitmap_git
->map_size
);
456 bitmap_git
->map_size
= 0;
457 bitmap_git
->map_pos
= 0;
458 bitmap_git
->map
= NULL
;
459 bitmap_git
->midx
= NULL
;
463 static int open_pack_bitmap_1(struct bitmap_index
*bitmap_git
, struct packed_git
*packfile
)
469 bitmap_name
= pack_bitmap_filename(packfile
);
470 fd
= git_open(bitmap_name
);
474 warning_errno("cannot open '%s'", bitmap_name
);
480 if (fstat(fd
, &st
)) {
481 error_errno(_("cannot fstat bitmap file"));
486 if (bitmap_git
->pack
|| bitmap_git
->midx
) {
487 trace2_data_string("bitmap", the_repository
,
488 "ignoring extra bitmap file", packfile
->pack_name
);
493 if (!is_pack_valid(packfile
)) {
498 bitmap_git
->pack
= packfile
;
499 bitmap_git
->map_size
= xsize_t(st
.st_size
);
500 bitmap_git
->map
= xmmap(NULL
, bitmap_git
->map_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
501 bitmap_git
->map_pos
= 0;
504 if (load_bitmap_header(bitmap_git
) < 0) {
505 munmap(bitmap_git
->map
, bitmap_git
->map_size
);
506 bitmap_git
->map
= NULL
;
507 bitmap_git
->map_size
= 0;
508 bitmap_git
->map_pos
= 0;
509 bitmap_git
->pack
= NULL
;
513 trace2_data_string("bitmap", the_repository
, "opened bitmap file",
514 packfile
->pack_name
);
518 static int load_reverse_index(struct repository
*r
, struct bitmap_index
*bitmap_git
)
520 if (bitmap_is_midx(bitmap_git
)) {
525 * The multi-pack-index's .rev file is already loaded via
526 * open_pack_bitmap_1().
528 * But we still need to open the individual pack .rev files,
529 * since we will need to make use of them in pack-objects.
531 for (i
= 0; i
< bitmap_git
->midx
->num_packs
; i
++) {
532 ret
= load_pack_revindex(r
, bitmap_git
->midx
->packs
[i
]);
538 return load_pack_revindex(r
, bitmap_git
->pack
);
541 static int load_bitmap(struct repository
*r
, struct bitmap_index
*bitmap_git
)
543 assert(bitmap_git
->map
);
545 bitmap_git
->bitmaps
= kh_init_oid_map();
546 bitmap_git
->ext_index
.positions
= kh_init_oid_pos();
548 if (load_reverse_index(r
, bitmap_git
))
551 if (!(bitmap_git
->commits
= read_bitmap_1(bitmap_git
)) ||
552 !(bitmap_git
->trees
= read_bitmap_1(bitmap_git
)) ||
553 !(bitmap_git
->blobs
= read_bitmap_1(bitmap_git
)) ||
554 !(bitmap_git
->tags
= read_bitmap_1(bitmap_git
)))
557 if (!bitmap_git
->table_lookup
&& load_bitmap_entries_v1(bitmap_git
) < 0)
563 munmap(bitmap_git
->map
, bitmap_git
->map_size
);
564 bitmap_git
->map
= NULL
;
565 bitmap_git
->map_size
= 0;
567 kh_destroy_oid_map(bitmap_git
->bitmaps
);
568 bitmap_git
->bitmaps
= NULL
;
570 kh_destroy_oid_pos(bitmap_git
->ext_index
.positions
);
571 bitmap_git
->ext_index
.positions
= NULL
;
576 static int open_pack_bitmap(struct repository
*r
,
577 struct bitmap_index
*bitmap_git
)
579 struct packed_git
*p
;
582 for (p
= get_all_packs(r
); p
; p
= p
->next
) {
583 if (open_pack_bitmap_1(bitmap_git
, p
) == 0) {
586 * The only reason to keep looking is to report
589 if (!trace2_is_enabled())
597 static int open_midx_bitmap(struct repository
*r
,
598 struct bitmap_index
*bitmap_git
)
601 struct multi_pack_index
*midx
;
603 assert(!bitmap_git
->map
);
605 for (midx
= get_multi_pack_index(r
); midx
; midx
= midx
->next
) {
606 if (!open_midx_bitmap_1(bitmap_git
, midx
))
612 static int open_bitmap(struct repository
*r
,
613 struct bitmap_index
*bitmap_git
)
617 assert(!bitmap_git
->map
);
619 found
= !open_midx_bitmap(r
, bitmap_git
);
622 * these will all be skipped if we opened a midx bitmap; but run it
623 * anyway if tracing is enabled to report the duplicates
625 if (!found
|| trace2_is_enabled())
626 found
|= !open_pack_bitmap(r
, bitmap_git
);
628 return found
? 0 : -1;
631 struct bitmap_index
*prepare_bitmap_git(struct repository
*r
)
633 struct bitmap_index
*bitmap_git
= xcalloc(1, sizeof(*bitmap_git
));
635 if (!open_bitmap(r
, bitmap_git
) && !load_bitmap(r
, bitmap_git
))
638 free_bitmap_index(bitmap_git
);
642 struct bitmap_index
*prepare_midx_bitmap_git(struct multi_pack_index
*midx
)
644 struct repository
*r
= the_repository
;
645 struct bitmap_index
*bitmap_git
= xcalloc(1, sizeof(*bitmap_git
));
647 if (!open_midx_bitmap_1(bitmap_git
, midx
) && !load_bitmap(r
, bitmap_git
))
650 free_bitmap_index(bitmap_git
);
654 struct include_data
{
655 struct bitmap_index
*bitmap_git
;
660 struct bitmap_lookup_table_triplet
{
666 struct bitmap_lookup_table_xor_item
{
667 struct object_id oid
;
672 * Given a `triplet` struct pointer and pointer `p`, this
673 * function reads the triplet beginning at `p` into the struct.
674 * Note that this function assumes that there is enough memory
675 * left for filling the `triplet` struct from `p`.
677 static int bitmap_lookup_table_get_triplet_by_pointer(struct bitmap_lookup_table_triplet
*triplet
,
678 const unsigned char *p
)
683 triplet
->commit_pos
= get_be32(p
);
684 p
+= sizeof(uint32_t);
685 triplet
->offset
= get_be64(p
);
686 p
+= sizeof(uint64_t);
687 triplet
->xor_row
= get_be32(p
);
692 * This function gets the raw triplet from `row`'th row in the
693 * lookup table and fills that data to the `triplet`.
695 static int bitmap_lookup_table_get_triplet(struct bitmap_index
*bitmap_git
,
697 struct bitmap_lookup_table_triplet
*triplet
)
699 unsigned char *p
= NULL
;
700 if (pos
>= bitmap_git
->entry_count
)
701 return error(_("corrupt bitmap lookup table: triplet position out of index"));
703 p
= bitmap_git
->table_lookup
+ st_mult(pos
, BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH
);
705 return bitmap_lookup_table_get_triplet_by_pointer(triplet
, p
);
709 * Searches for a matching triplet. `commit_pos` is a pointer
710 * to the wanted commit position value. `table_entry` points to
711 * a triplet in lookup table. The first 4 bytes of each
712 * triplet (pointed by `table_entry`) are compared with `*commit_pos`.
714 static int triplet_cmp(const void *commit_pos
, const void *table_entry
)
717 uint32_t a
= *(uint32_t *)commit_pos
;
718 uint32_t b
= get_be32(table_entry
);
727 static uint32_t bitmap_bsearch_pos(struct bitmap_index
*bitmap_git
,
728 struct object_id
*oid
,
733 if (bitmap_is_midx(bitmap_git
))
734 found
= bsearch_midx(oid
, bitmap_git
->midx
, result
);
736 found
= bsearch_pack(oid
, bitmap_git
->pack
, result
);
742 * `bsearch_triplet_by_pos` function searches for the raw triplet
743 * having commit position same as `commit_pos` and fills `triplet`
744 * object from the raw triplet. Returns 1 on success and 0 on
747 static int bitmap_bsearch_triplet_by_pos(uint32_t commit_pos
,
748 struct bitmap_index
*bitmap_git
,
749 struct bitmap_lookup_table_triplet
*triplet
)
751 unsigned char *p
= bsearch(&commit_pos
, bitmap_git
->table_lookup
, bitmap_git
->entry_count
,
752 BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH
, triplet_cmp
);
757 return bitmap_lookup_table_get_triplet_by_pointer(triplet
, p
);
760 static struct stored_bitmap
*lazy_bitmap_for_commit(struct bitmap_index
*bitmap_git
,
761 struct commit
*commit
)
763 uint32_t commit_pos
, xor_row
;
766 struct bitmap_lookup_table_triplet triplet
;
767 struct object_id
*oid
= &commit
->object
.oid
;
768 struct ewah_bitmap
*bitmap
;
769 struct stored_bitmap
*xor_bitmap
= NULL
;
770 const int bitmap_header_size
= 6;
771 static struct bitmap_lookup_table_xor_item
*xor_items
= NULL
;
772 static size_t xor_items_nr
= 0, xor_items_alloc
= 0;
773 static int is_corrupt
= 0;
776 struct bitmap_lookup_table_xor_item
*xor_item
;
781 if (!bitmap_bsearch_pos(bitmap_git
, oid
, &commit_pos
))
784 if (bitmap_bsearch_triplet_by_pos(commit_pos
, bitmap_git
, &triplet
) < 0)
788 offset
= triplet
.offset
;
789 xor_row
= triplet
.xor_row
;
791 while (xor_row
!= 0xffffffff) {
792 ALLOC_GROW(xor_items
, xor_items_nr
+ 1, xor_items_alloc
);
794 if (xor_items_nr
+ 1 >= bitmap_git
->entry_count
) {
795 error(_("corrupt bitmap lookup table: xor chain exceeds entry count"));
799 if (bitmap_lookup_table_get_triplet(bitmap_git
, xor_row
, &triplet
) < 0)
802 xor_item
= &xor_items
[xor_items_nr
];
803 xor_item
->offset
= triplet
.offset
;
805 if (nth_bitmap_object_oid(bitmap_git
, &xor_item
->oid
, triplet
.commit_pos
) < 0) {
806 error(_("corrupt bitmap lookup table: commit index %u out of range"),
811 hash_pos
= kh_get_oid_map(bitmap_git
->bitmaps
, xor_item
->oid
);
814 * If desired bitmap is already stored, we don't need
815 * to iterate further. Because we know that bitmaps
816 * that are needed to be parsed to parse this bitmap
817 * has already been stored. So, assign this stored bitmap
820 if (hash_pos
< kh_end(bitmap_git
->bitmaps
) &&
821 (xor_bitmap
= kh_value(bitmap_git
->bitmaps
, hash_pos
)))
824 xor_row
= triplet
.xor_row
;
827 while (xor_items_nr
) {
828 xor_item
= &xor_items
[xor_items_nr
- 1];
829 bitmap_git
->map_pos
= xor_item
->offset
;
830 if (bitmap_git
->map_size
- bitmap_git
->map_pos
< bitmap_header_size
) {
831 error(_("corrupt ewah bitmap: truncated header for bitmap of commit \"%s\""),
832 oid_to_hex(&xor_item
->oid
));
836 bitmap_git
->map_pos
+= sizeof(uint32_t) + sizeof(uint8_t);
837 xor_flags
= read_u8(bitmap_git
->map
, &bitmap_git
->map_pos
);
838 bitmap
= read_bitmap_1(bitmap_git
);
843 xor_bitmap
= store_bitmap(bitmap_git
, bitmap
, &xor_item
->oid
, xor_bitmap
, xor_flags
);
847 bitmap_git
->map_pos
= offset
;
848 if (bitmap_git
->map_size
- bitmap_git
->map_pos
< bitmap_header_size
) {
849 error(_("corrupt ewah bitmap: truncated header for bitmap of commit \"%s\""),
855 * Don't bother reading the commit's index position or its xor
858 * - The commit's index position is irrelevant to us, since
859 * load_bitmap_entries_v1 only uses it to learn the object
860 * id which is used to compute the hashmap's key. We already
861 * have an object id, so no need to look it up again.
863 * - The xor_offset is unusable for us, since it specifies how
864 * many entries previous to ours we should look at. This
865 * makes sense when reading the bitmaps sequentially (as in
866 * load_bitmap_entries_v1()), since we can keep track of
867 * each bitmap as we read them.
869 * But it can't work for us, since the bitmap's don't have a
870 * fixed size. So we learn the position of the xor'd bitmap
871 * from the commit table (and resolve it to a bitmap in the
872 * above if-statement).
874 * Instead, we can skip ahead and immediately read the flags and
877 bitmap_git
->map_pos
+= sizeof(uint32_t) + sizeof(uint8_t);
878 flags
= read_u8(bitmap_git
->map
, &bitmap_git
->map_pos
);
879 bitmap
= read_bitmap_1(bitmap_git
);
884 return store_bitmap(bitmap_git
, bitmap
, oid
, xor_bitmap
, flags
);
892 struct ewah_bitmap
*bitmap_for_commit(struct bitmap_index
*bitmap_git
,
893 struct commit
*commit
)
895 khiter_t hash_pos
= kh_get_oid_map(bitmap_git
->bitmaps
,
897 if (hash_pos
>= kh_end(bitmap_git
->bitmaps
)) {
898 struct stored_bitmap
*bitmap
= NULL
;
899 if (!bitmap_git
->table_lookup
)
902 /* this is a fairly hot codepath - no trace2_region please */
903 /* NEEDSWORK: cache misses aren't recorded */
904 bitmap
= lazy_bitmap_for_commit(bitmap_git
, commit
);
907 return lookup_stored_bitmap(bitmap
);
909 return lookup_stored_bitmap(kh_value(bitmap_git
->bitmaps
, hash_pos
));
912 static inline int bitmap_position_extended(struct bitmap_index
*bitmap_git
,
913 const struct object_id
*oid
)
915 kh_oid_pos_t
*positions
= bitmap_git
->ext_index
.positions
;
916 khiter_t pos
= kh_get_oid_pos(positions
, *oid
);
918 if (pos
< kh_end(positions
)) {
919 int bitmap_pos
= kh_value(positions
, pos
);
920 return bitmap_pos
+ bitmap_num_objects(bitmap_git
);
926 static inline int bitmap_position_packfile(struct bitmap_index
*bitmap_git
,
927 const struct object_id
*oid
)
930 off_t offset
= find_pack_entry_one(oid
->hash
, bitmap_git
->pack
);
934 if (offset_to_pack_pos(bitmap_git
->pack
, offset
, &pos
) < 0)
939 static int bitmap_position_midx(struct bitmap_index
*bitmap_git
,
940 const struct object_id
*oid
)
943 if (!bsearch_midx(oid
, bitmap_git
->midx
, &want
))
946 if (midx_to_pack_pos(bitmap_git
->midx
, want
, &got
) < 0)
951 static int bitmap_position(struct bitmap_index
*bitmap_git
,
952 const struct object_id
*oid
)
955 if (bitmap_is_midx(bitmap_git
))
956 pos
= bitmap_position_midx(bitmap_git
, oid
);
958 pos
= bitmap_position_packfile(bitmap_git
, oid
);
959 return (pos
>= 0) ? pos
: bitmap_position_extended(bitmap_git
, oid
);
962 static int ext_index_add_object(struct bitmap_index
*bitmap_git
,
963 struct object
*object
, const char *name
)
965 struct eindex
*eindex
= &bitmap_git
->ext_index
;
971 hash_pos
= kh_put_oid_pos(eindex
->positions
, object
->oid
, &hash_ret
);
973 if (eindex
->count
>= eindex
->alloc
) {
974 eindex
->alloc
= (eindex
->alloc
+ 16) * 3 / 2;
975 REALLOC_ARRAY(eindex
->objects
, eindex
->alloc
);
976 REALLOC_ARRAY(eindex
->hashes
, eindex
->alloc
);
979 bitmap_pos
= eindex
->count
;
980 eindex
->objects
[eindex
->count
] = object
;
981 eindex
->hashes
[eindex
->count
] = pack_name_hash(name
);
982 kh_value(eindex
->positions
, hash_pos
) = bitmap_pos
;
985 bitmap_pos
= kh_value(eindex
->positions
, hash_pos
);
988 return bitmap_pos
+ bitmap_num_objects(bitmap_git
);
991 struct bitmap_show_data
{
992 struct bitmap_index
*bitmap_git
;
996 static void show_object(struct object
*object
, const char *name
, void *data_
)
998 struct bitmap_show_data
*data
= data_
;
1001 bitmap_pos
= bitmap_position(data
->bitmap_git
, &object
->oid
);
1004 bitmap_pos
= ext_index_add_object(data
->bitmap_git
, object
,
1007 bitmap_set(data
->base
, bitmap_pos
);
1010 static void show_commit(struct commit
*commit UNUSED
,
1015 static unsigned apply_pseudo_merges_for_commit_1(struct bitmap_index
*bitmap_git
,
1016 struct bitmap
*result
,
1017 struct commit
*commit
,
1018 uint32_t commit_pos
)
1022 ret
= apply_pseudo_merges_for_commit(&bitmap_git
->pseudo_merges
,
1023 result
, commit
, commit_pos
);
1026 pseudo_merges_satisfied_nr
+= ret
;
1031 static int add_to_include_set(struct bitmap_index
*bitmap_git
,
1032 struct include_data
*data
,
1033 struct commit
*commit
,
1036 struct ewah_bitmap
*partial
;
1038 if (data
->seen
&& bitmap_get(data
->seen
, bitmap_pos
))
1041 if (bitmap_get(data
->base
, bitmap_pos
))
1044 partial
= bitmap_for_commit(bitmap_git
, commit
);
1046 existing_bitmaps_hits_nr
++;
1048 bitmap_or_ewah(data
->base
, partial
);
1052 existing_bitmaps_misses_nr
++;
1054 bitmap_set(data
->base
, bitmap_pos
);
1055 if (apply_pseudo_merges_for_commit_1(bitmap_git
, data
->base
, commit
,
1062 static int should_include(struct commit
*commit
, void *_data
)
1064 struct include_data
*data
= _data
;
1067 bitmap_pos
= bitmap_position(data
->bitmap_git
, &commit
->object
.oid
);
1069 bitmap_pos
= ext_index_add_object(data
->bitmap_git
,
1070 (struct object
*)commit
,
1073 if (!add_to_include_set(data
->bitmap_git
, data
, commit
, bitmap_pos
)) {
1074 struct commit_list
*parent
= commit
->parents
;
1077 parent
->item
->object
.flags
|= SEEN
;
1078 parent
= parent
->next
;
1087 static int should_include_obj(struct object
*obj
, void *_data
)
1089 struct include_data
*data
= _data
;
1092 bitmap_pos
= bitmap_position(data
->bitmap_git
, &obj
->oid
);
1095 if ((data
->seen
&& bitmap_get(data
->seen
, bitmap_pos
)) ||
1096 bitmap_get(data
->base
, bitmap_pos
)) {
1103 static int add_commit_to_bitmap(struct bitmap_index
*bitmap_git
,
1104 struct bitmap
**base
,
1105 struct commit
*commit
)
1107 struct ewah_bitmap
*or_with
= bitmap_for_commit(bitmap_git
, commit
);
1110 existing_bitmaps_misses_nr
++;
1114 existing_bitmaps_hits_nr
++;
1117 *base
= ewah_to_bitmap(or_with
);
1119 bitmap_or_ewah(*base
, or_with
);
1124 static struct bitmap
*fill_in_bitmap(struct bitmap_index
*bitmap_git
,
1125 struct rev_info
*revs
,
1126 struct bitmap
*base
,
1127 struct bitmap
*seen
)
1129 struct include_data incdata
;
1130 struct bitmap_show_data show_data
;
1133 base
= bitmap_new();
1135 incdata
.bitmap_git
= bitmap_git
;
1136 incdata
.base
= base
;
1137 incdata
.seen
= seen
;
1139 revs
->include_check
= should_include
;
1140 revs
->include_check_obj
= should_include_obj
;
1141 revs
->include_check_data
= &incdata
;
1143 if (prepare_revision_walk(revs
))
1144 die(_("revision walk setup failed"));
1146 show_data
.bitmap_git
= bitmap_git
;
1147 show_data
.base
= base
;
1149 traverse_commit_list(revs
, show_commit
, show_object
, &show_data
);
1151 revs
->include_check
= NULL
;
1152 revs
->include_check_obj
= NULL
;
1153 revs
->include_check_data
= NULL
;
1158 struct bitmap_boundary_cb
{
1159 struct bitmap_index
*bitmap_git
;
1160 struct bitmap
*base
;
1162 struct object_array boundary
;
1165 static void show_boundary_commit(struct commit
*commit
, void *_data
)
1167 struct bitmap_boundary_cb
*data
= _data
;
1169 if (commit
->object
.flags
& BOUNDARY
)
1170 add_object_array(&commit
->object
, "", &data
->boundary
);
1172 if (commit
->object
.flags
& UNINTERESTING
) {
1173 if (bitmap_walk_contains(data
->bitmap_git
, data
->base
,
1174 &commit
->object
.oid
))
1177 add_commit_to_bitmap(data
->bitmap_git
, &data
->base
, commit
);
1181 static void show_boundary_object(struct object
*object UNUSED
,
1182 const char *name UNUSED
,
1185 BUG("should not be called");
1188 static unsigned cascade_pseudo_merges_1(struct bitmap_index
*bitmap_git
,
1189 struct bitmap
*result
,
1190 struct bitmap
*roots
)
1192 int ret
= cascade_pseudo_merges(&bitmap_git
->pseudo_merges
,
1195 pseudo_merges_cascades_nr
++;
1196 pseudo_merges_satisfied_nr
+= ret
;
1202 static struct bitmap
*find_boundary_objects(struct bitmap_index
*bitmap_git
,
1203 struct rev_info
*revs
,
1204 struct object_list
*roots
)
1206 struct bitmap_boundary_cb cb
;
1207 struct object_list
*root
;
1209 unsigned int tmp_blobs
, tmp_trees
, tmp_tags
;
1210 int any_missing
= 0;
1211 int existing_bitmaps
= 0;
1213 cb
.bitmap_git
= bitmap_git
;
1214 cb
.base
= bitmap_new();
1215 object_array_init(&cb
.boundary
);
1217 revs
->ignore_missing_links
= 1;
1219 if (bitmap_git
->pseudo_merges
.nr
) {
1220 struct bitmap
*roots_bitmap
= bitmap_new();
1221 struct object_list
*objects
= NULL
;
1223 for (objects
= roots
; objects
; objects
= objects
->next
) {
1224 struct object
*object
= objects
->item
;
1227 pos
= bitmap_position(bitmap_git
, &object
->oid
);
1231 bitmap_set(roots_bitmap
, pos
);
1234 if (!cascade_pseudo_merges_1(bitmap_git
, cb
.base
, roots_bitmap
))
1235 bitmap_free(roots_bitmap
);
1239 * OR in any existing reachability bitmaps among `roots` into
1242 for (root
= roots
; root
; root
= root
->next
) {
1243 struct object
*object
= root
->item
;
1244 if (object
->type
!= OBJ_COMMIT
||
1245 bitmap_walk_contains(bitmap_git
, cb
.base
, &object
->oid
))
1248 if (add_commit_to_bitmap(bitmap_git
, &cb
.base
,
1249 (struct commit
*)object
)) {
1250 existing_bitmaps
= 1;
1260 if (existing_bitmaps
)
1261 cascade_pseudo_merges_1(bitmap_git
, cb
.base
, NULL
);
1263 tmp_blobs
= revs
->blob_objects
;
1264 tmp_trees
= revs
->tree_objects
;
1265 tmp_tags
= revs
->blob_objects
;
1266 revs
->blob_objects
= 0;
1267 revs
->tree_objects
= 0;
1268 revs
->tag_objects
= 0;
1271 * We didn't have complete coverage of the roots. First setup a
1272 * revision walk to (a) OR in any bitmaps that are UNINTERESTING
1273 * between the tips and boundary, and (b) record the boundary.
1275 trace2_region_enter("pack-bitmap", "boundary-prepare", the_repository
);
1276 if (prepare_revision_walk(revs
))
1277 die("revision walk setup failed");
1278 trace2_region_leave("pack-bitmap", "boundary-prepare", the_repository
);
1280 trace2_region_enter("pack-bitmap", "boundary-traverse", the_repository
);
1282 traverse_commit_list_filtered(revs
,
1283 show_boundary_commit
,
1284 show_boundary_object
,
1287 trace2_region_leave("pack-bitmap", "boundary-traverse", the_repository
);
1289 revs
->blob_objects
= tmp_blobs
;
1290 revs
->tree_objects
= tmp_trees
;
1291 revs
->tag_objects
= tmp_tags
;
1293 reset_revision_walk();
1294 clear_object_flags(UNINTERESTING
);
1297 * Then add the boundary commit(s) as fill-in traversal tips.
1299 trace2_region_enter("pack-bitmap", "boundary-fill-in", the_repository
);
1300 for (i
= 0; i
< cb
.boundary
.nr
; i
++) {
1301 struct object
*obj
= cb
.boundary
.objects
[i
].item
;
1302 if (bitmap_walk_contains(bitmap_git
, cb
.base
, &obj
->oid
))
1305 add_pending_object(revs
, obj
, "");
1307 if (revs
->pending
.nr
)
1308 cb
.base
= fill_in_bitmap(bitmap_git
, revs
, cb
.base
, NULL
);
1309 trace2_region_leave("pack-bitmap", "boundary-fill-in", the_repository
);
1312 object_array_clear(&cb
.boundary
);
1313 revs
->ignore_missing_links
= 0;
1318 struct ewah_bitmap
*pseudo_merge_bitmap_for_commit(struct bitmap_index
*bitmap_git
,
1319 struct commit
*commit
)
1321 struct commit_list
*p
;
1322 struct bitmap
*parents
;
1323 struct pseudo_merge
*match
= NULL
;
1325 if (!bitmap_git
->pseudo_merges
.nr
)
1328 parents
= bitmap_new();
1330 for (p
= commit
->parents
; p
; p
= p
->next
) {
1331 int pos
= bitmap_position(bitmap_git
, &p
->item
->object
.oid
);
1332 if (pos
< 0 || pos
>= bitmap_num_objects(bitmap_git
))
1335 bitmap_set(parents
, pos
);
1338 match
= pseudo_merge_for_parents(&bitmap_git
->pseudo_merges
,
1342 bitmap_free(parents
);
1344 return pseudo_merge_bitmap(&bitmap_git
->pseudo_merges
, match
);
1349 static void unsatisfy_all_pseudo_merges(struct bitmap_index
*bitmap_git
)
1352 for (i
= 0; i
< bitmap_git
->pseudo_merges
.nr
; i
++)
1353 bitmap_git
->pseudo_merges
.v
[i
].satisfied
= 0;
1356 static struct bitmap
*find_objects(struct bitmap_index
*bitmap_git
,
1357 struct rev_info
*revs
,
1358 struct object_list
*roots
,
1359 struct bitmap
*seen
)
1361 struct bitmap
*base
= NULL
;
1363 unsigned existing_bitmaps
= 0;
1365 struct object_list
*not_mapped
= NULL
;
1367 unsatisfy_all_pseudo_merges(bitmap_git
);
1369 if (bitmap_git
->pseudo_merges
.nr
) {
1370 struct bitmap
*roots_bitmap
= bitmap_new();
1371 struct object_list
*objects
= NULL
;
1373 for (objects
= roots
; objects
; objects
= objects
->next
) {
1374 struct object
*object
= objects
->item
;
1377 pos
= bitmap_position(bitmap_git
, &object
->oid
);
1381 bitmap_set(roots_bitmap
, pos
);
1384 base
= bitmap_new();
1385 if (!cascade_pseudo_merges_1(bitmap_git
, base
, roots_bitmap
))
1386 bitmap_free(roots_bitmap
);
1390 * Go through all the roots for the walk. The ones that have bitmaps
1391 * on the bitmap index will be `or`ed together to form an initial
1392 * global reachability analysis.
1394 * The ones without bitmaps in the index will be stored in the
1395 * `not_mapped_list` for further processing.
1398 struct object
*object
= roots
->item
;
1400 roots
= roots
->next
;
1403 int pos
= bitmap_position(bitmap_git
, &object
->oid
);
1404 if (pos
> 0 && bitmap_get(base
, pos
)) {
1405 object
->flags
|= SEEN
;
1410 if (object
->type
== OBJ_COMMIT
&&
1411 add_commit_to_bitmap(bitmap_git
, &base
, (struct commit
*)object
)) {
1412 object
->flags
|= SEEN
;
1413 existing_bitmaps
= 1;
1417 object_list_insert(object
, ¬_mapped
);
1421 * Best case scenario: We found bitmaps for all the roots,
1422 * so the resulting `or` bitmap has the full reachability analysis
1429 if (existing_bitmaps
)
1430 cascade_pseudo_merges_1(bitmap_git
, base
, NULL
);
1433 * Let's iterate through all the roots that don't have bitmaps to
1434 * check if we can determine them to be reachable from the existing
1437 * If we cannot find them in the existing global bitmap, we'll need
1438 * to push them to an actual walk and run it until we can confirm
1439 * they are reachable
1442 struct object
*object
= roots
->item
;
1445 roots
= roots
->next
;
1446 pos
= bitmap_position(bitmap_git
, &object
->oid
);
1448 if (pos
< 0 || base
== NULL
|| !bitmap_get(base
, pos
)) {
1449 object
->flags
&= ~UNINTERESTING
;
1450 add_pending_object(revs
, object
, "");
1453 roots_without_bitmaps_nr
++;
1455 object
->flags
|= SEEN
;
1457 roots_with_bitmaps_nr
++;
1463 * This fill-in traversal may walk over some objects
1464 * again, since we have already traversed in order to
1465 * find the boundary.
1467 * But this extra walk should be extremely cheap, since
1468 * all commit objects are loaded into memory, and
1469 * because we skip walking to parents that are
1470 * UNINTERESTING, since it will be marked in the haves
1471 * bitmap already (or it has an on-disk bitmap, since
1472 * OR-ing it in covers all of its ancestors).
1474 base
= fill_in_bitmap(bitmap_git
, revs
, base
, seen
);
1477 object_list_free(¬_mapped
);
1482 static void show_extended_objects(struct bitmap_index
*bitmap_git
,
1483 struct rev_info
*revs
,
1484 show_reachable_fn show_reach
)
1486 struct bitmap
*objects
= bitmap_git
->result
;
1487 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1490 for (i
= 0; i
< eindex
->count
; ++i
) {
1493 if (!bitmap_get(objects
, st_add(bitmap_num_objects(bitmap_git
), i
)))
1496 obj
= eindex
->objects
[i
];
1497 if ((obj
->type
== OBJ_BLOB
&& !revs
->blob_objects
) ||
1498 (obj
->type
== OBJ_TREE
&& !revs
->tree_objects
) ||
1499 (obj
->type
== OBJ_TAG
&& !revs
->tag_objects
))
1502 show_reach(&obj
->oid
, obj
->type
, 0, eindex
->hashes
[i
], NULL
, 0);
1506 static void init_type_iterator(struct ewah_iterator
*it
,
1507 struct bitmap_index
*bitmap_git
,
1508 enum object_type type
)
1512 ewah_iterator_init(it
, bitmap_git
->commits
);
1516 ewah_iterator_init(it
, bitmap_git
->trees
);
1520 ewah_iterator_init(it
, bitmap_git
->blobs
);
1524 ewah_iterator_init(it
, bitmap_git
->tags
);
1528 BUG("object type %d not stored by bitmap type index", type
);
1533 static void show_objects_for_type(
1534 struct bitmap_index
*bitmap_git
,
1535 enum object_type object_type
,
1536 show_reachable_fn show_reach
)
1541 struct ewah_iterator it
;
1544 struct bitmap
*objects
= bitmap_git
->result
;
1546 init_type_iterator(&it
, bitmap_git
, object_type
);
1548 for (i
= 0; i
< objects
->word_alloc
&&
1549 ewah_iterator_next(&filter
, &it
); i
++) {
1550 eword_t word
= objects
->words
[i
] & filter
;
1551 size_t pos
= (i
* BITS_IN_EWORD
);
1556 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
1557 struct packed_git
*pack
;
1558 struct object_id oid
;
1559 uint32_t hash
= 0, index_pos
;
1562 if ((word
>> offset
) == 0)
1565 offset
+= ewah_bit_ctz64(word
>> offset
);
1567 if (bitmap_is_midx(bitmap_git
)) {
1568 struct multi_pack_index
*m
= bitmap_git
->midx
;
1571 index_pos
= pack_pos_to_midx(m
, pos
+ offset
);
1572 ofs
= nth_midxed_offset(m
, index_pos
);
1573 nth_midxed_object_oid(&oid
, m
, index_pos
);
1575 pack_id
= nth_midxed_pack_int_id(m
, index_pos
);
1576 pack
= bitmap_git
->midx
->packs
[pack_id
];
1578 index_pos
= pack_pos_to_index(bitmap_git
->pack
, pos
+ offset
);
1579 ofs
= pack_pos_to_offset(bitmap_git
->pack
, pos
+ offset
);
1580 nth_bitmap_object_oid(bitmap_git
, &oid
, index_pos
);
1582 pack
= bitmap_git
->pack
;
1585 if (bitmap_git
->hashes
)
1586 hash
= get_be32(bitmap_git
->hashes
+ index_pos
);
1588 show_reach(&oid
, object_type
, 0, hash
, pack
, ofs
);
1593 static int in_bitmapped_pack(struct bitmap_index
*bitmap_git
,
1594 struct object_list
*roots
)
1597 struct object
*object
= roots
->item
;
1598 roots
= roots
->next
;
1600 if (bitmap_is_midx(bitmap_git
)) {
1601 if (bsearch_midx(&object
->oid
, bitmap_git
->midx
, NULL
))
1604 if (find_pack_entry_one(object
->oid
.hash
, bitmap_git
->pack
) > 0)
1612 static struct bitmap
*find_tip_objects(struct bitmap_index
*bitmap_git
,
1613 struct object_list
*tip_objects
,
1614 enum object_type type
)
1616 struct bitmap
*result
= bitmap_new();
1617 struct object_list
*p
;
1619 for (p
= tip_objects
; p
; p
= p
->next
) {
1622 if (p
->item
->type
!= type
)
1625 pos
= bitmap_position(bitmap_git
, &p
->item
->oid
);
1629 bitmap_set(result
, pos
);
1635 static void filter_bitmap_exclude_type(struct bitmap_index
*bitmap_git
,
1636 struct object_list
*tip_objects
,
1637 struct bitmap
*to_filter
,
1638 enum object_type type
)
1640 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1641 struct bitmap
*tips
;
1642 struct ewah_iterator it
;
1647 * The non-bitmap version of this filter never removes
1648 * objects which the other side specifically asked for,
1649 * so we must match that behavior.
1651 tips
= find_tip_objects(bitmap_git
, tip_objects
, type
);
1654 * We can use the type-level bitmap for 'type' to work in whole
1655 * words for the objects that are actually in the bitmapped
1658 for (i
= 0, init_type_iterator(&it
, bitmap_git
, type
);
1659 i
< to_filter
->word_alloc
&& ewah_iterator_next(&mask
, &it
);
1661 if (i
< tips
->word_alloc
)
1662 mask
&= ~tips
->words
[i
];
1663 to_filter
->words
[i
] &= ~mask
;
1667 * Clear any objects that weren't in the packfile (and so would
1668 * not have been caught by the loop above. We'll have to check
1669 * them individually.
1671 for (i
= 0; i
< eindex
->count
; i
++) {
1672 size_t pos
= st_add(i
, bitmap_num_objects(bitmap_git
));
1673 if (eindex
->objects
[i
]->type
== type
&&
1674 bitmap_get(to_filter
, pos
) &&
1675 !bitmap_get(tips
, pos
))
1676 bitmap_unset(to_filter
, pos
);
1682 static void filter_bitmap_blob_none(struct bitmap_index
*bitmap_git
,
1683 struct object_list
*tip_objects
,
1684 struct bitmap
*to_filter
)
1686 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
,
1690 static unsigned long get_size_by_pos(struct bitmap_index
*bitmap_git
,
1694 struct object_info oi
= OBJECT_INFO_INIT
;
1698 if (pos
< bitmap_num_objects(bitmap_git
)) {
1699 struct packed_git
*pack
;
1702 if (bitmap_is_midx(bitmap_git
)) {
1703 uint32_t midx_pos
= pack_pos_to_midx(bitmap_git
->midx
, pos
);
1704 uint32_t pack_id
= nth_midxed_pack_int_id(bitmap_git
->midx
, midx_pos
);
1706 pack
= bitmap_git
->midx
->packs
[pack_id
];
1707 ofs
= nth_midxed_offset(bitmap_git
->midx
, midx_pos
);
1709 pack
= bitmap_git
->pack
;
1710 ofs
= pack_pos_to_offset(pack
, pos
);
1713 if (packed_object_info(the_repository
, pack
, ofs
, &oi
) < 0) {
1714 struct object_id oid
;
1715 nth_bitmap_object_oid(bitmap_git
, &oid
,
1716 pack_pos_to_index(pack
, pos
));
1717 die(_("unable to get size of %s"), oid_to_hex(&oid
));
1720 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1721 struct object
*obj
= eindex
->objects
[pos
- bitmap_num_objects(bitmap_git
)];
1722 if (oid_object_info_extended(the_repository
, &obj
->oid
, &oi
, 0) < 0)
1723 die(_("unable to get size of %s"), oid_to_hex(&obj
->oid
));
1729 static void filter_bitmap_blob_limit(struct bitmap_index
*bitmap_git
,
1730 struct object_list
*tip_objects
,
1731 struct bitmap
*to_filter
,
1732 unsigned long limit
)
1734 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1735 struct bitmap
*tips
;
1736 struct ewah_iterator it
;
1740 tips
= find_tip_objects(bitmap_git
, tip_objects
, OBJ_BLOB
);
1742 for (i
= 0, init_type_iterator(&it
, bitmap_git
, OBJ_BLOB
);
1743 i
< to_filter
->word_alloc
&& ewah_iterator_next(&mask
, &it
);
1745 eword_t word
= to_filter
->words
[i
] & mask
;
1748 for (offset
= 0; offset
< BITS_IN_EWORD
; offset
++) {
1751 if ((word
>> offset
) == 0)
1753 offset
+= ewah_bit_ctz64(word
>> offset
);
1754 pos
= i
* BITS_IN_EWORD
+ offset
;
1756 if (!bitmap_get(tips
, pos
) &&
1757 get_size_by_pos(bitmap_git
, pos
) >= limit
)
1758 bitmap_unset(to_filter
, pos
);
1762 for (i
= 0; i
< eindex
->count
; i
++) {
1763 size_t pos
= st_add(i
, bitmap_num_objects(bitmap_git
));
1764 if (eindex
->objects
[i
]->type
== OBJ_BLOB
&&
1765 bitmap_get(to_filter
, pos
) &&
1766 !bitmap_get(tips
, pos
) &&
1767 get_size_by_pos(bitmap_git
, pos
) >= limit
)
1768 bitmap_unset(to_filter
, pos
);
1774 static void filter_bitmap_tree_depth(struct bitmap_index
*bitmap_git
,
1775 struct object_list
*tip_objects
,
1776 struct bitmap
*to_filter
,
1777 unsigned long limit
)
1780 BUG("filter_bitmap_tree_depth given non-zero limit");
1782 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
,
1784 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
,
1788 static void filter_bitmap_object_type(struct bitmap_index
*bitmap_git
,
1789 struct object_list
*tip_objects
,
1790 struct bitmap
*to_filter
,
1791 enum object_type object_type
)
1793 if (object_type
< OBJ_COMMIT
|| object_type
> OBJ_TAG
)
1794 BUG("filter_bitmap_object_type given invalid object");
1796 if (object_type
!= OBJ_TAG
)
1797 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_TAG
);
1798 if (object_type
!= OBJ_COMMIT
)
1799 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_COMMIT
);
1800 if (object_type
!= OBJ_TREE
)
1801 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_TREE
);
1802 if (object_type
!= OBJ_BLOB
)
1803 filter_bitmap_exclude_type(bitmap_git
, tip_objects
, to_filter
, OBJ_BLOB
);
1806 static int filter_bitmap(struct bitmap_index
*bitmap_git
,
1807 struct object_list
*tip_objects
,
1808 struct bitmap
*to_filter
,
1809 struct list_objects_filter_options
*filter
)
1811 if (!filter
|| filter
->choice
== LOFC_DISABLED
)
1814 if (filter
->choice
== LOFC_BLOB_NONE
) {
1816 filter_bitmap_blob_none(bitmap_git
, tip_objects
,
1821 if (filter
->choice
== LOFC_BLOB_LIMIT
) {
1823 filter_bitmap_blob_limit(bitmap_git
, tip_objects
,
1825 filter
->blob_limit_value
);
1829 if (filter
->choice
== LOFC_TREE_DEPTH
&&
1830 filter
->tree_exclude_depth
== 0) {
1832 filter_bitmap_tree_depth(bitmap_git
, tip_objects
,
1834 filter
->tree_exclude_depth
);
1838 if (filter
->choice
== LOFC_OBJECT_TYPE
) {
1840 filter_bitmap_object_type(bitmap_git
, tip_objects
,
1842 filter
->object_type
);
1846 if (filter
->choice
== LOFC_COMBINE
) {
1848 for (i
= 0; i
< filter
->sub_nr
; i
++) {
1849 if (filter_bitmap(bitmap_git
, tip_objects
, to_filter
,
1850 &filter
->sub
[i
]) < 0)
1856 /* filter choice not handled */
1860 static int can_filter_bitmap(struct list_objects_filter_options
*filter
)
1862 return !filter_bitmap(NULL
, NULL
, NULL
, filter
);
1866 static void filter_packed_objects_from_bitmap(struct bitmap_index
*bitmap_git
,
1867 struct bitmap
*result
)
1869 struct eindex
*eindex
= &bitmap_git
->ext_index
;
1870 uint32_t objects_nr
;
1873 objects_nr
= bitmap_num_objects(bitmap_git
);
1874 pos
= objects_nr
/ BITS_IN_EWORD
;
1876 if (pos
> result
->word_alloc
)
1877 pos
= result
->word_alloc
;
1879 memset(result
->words
, 0x00, sizeof(eword_t
) * pos
);
1880 for (i
= pos
* BITS_IN_EWORD
; i
< objects_nr
; i
++)
1881 bitmap_unset(result
, i
);
1883 for (i
= 0; i
< eindex
->count
; ++i
) {
1884 if (has_object_pack(&eindex
->objects
[i
]->oid
))
1885 bitmap_unset(result
, objects_nr
+ i
);
1889 struct bitmap_index
*prepare_bitmap_walk(struct rev_info
*revs
,
1890 int filter_provided_objects
)
1893 int use_boundary_traversal
;
1895 struct object_list
*wants
= NULL
;
1896 struct object_list
*haves
= NULL
;
1898 struct bitmap
*wants_bitmap
= NULL
;
1899 struct bitmap
*haves_bitmap
= NULL
;
1901 struct bitmap_index
*bitmap_git
;
1904 * We can't do pathspec limiting with bitmaps, because we don't know
1905 * which commits are associated with which object changes (let alone
1906 * even which objects are associated with which paths).
1911 if (!can_filter_bitmap(&revs
->filter
))
1914 /* try to open a bitmapped pack, but don't parse it yet
1915 * because we may not need to use it */
1916 CALLOC_ARRAY(bitmap_git
, 1);
1917 if (open_bitmap(revs
->repo
, bitmap_git
) < 0)
1920 for (i
= 0; i
< revs
->pending
.nr
; ++i
) {
1921 struct object
*object
= revs
->pending
.objects
[i
].item
;
1923 if (object
->type
== OBJ_NONE
)
1924 parse_object_or_die(&object
->oid
, NULL
);
1926 while (object
->type
== OBJ_TAG
) {
1927 struct tag
*tag
= (struct tag
*) object
;
1929 if (object
->flags
& UNINTERESTING
)
1930 object_list_insert(object
, &haves
);
1932 object_list_insert(object
, &wants
);
1934 object
= parse_object_or_die(get_tagged_oid(tag
), NULL
);
1935 object
->flags
|= (tag
->object
.flags
& UNINTERESTING
);
1938 if (object
->flags
& UNINTERESTING
)
1939 object_list_insert(object
, &haves
);
1941 object_list_insert(object
, &wants
);
1944 use_boundary_traversal
= git_env_bool(GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL
, -1);
1945 if (use_boundary_traversal
< 0) {
1946 prepare_repo_settings(revs
->repo
);
1947 use_boundary_traversal
= revs
->repo
->settings
.pack_use_bitmap_boundary_traversal
;
1950 if (!use_boundary_traversal
) {
1952 * if we have a HAVES list, but none of those haves is contained
1953 * in the packfile that has a bitmap, we don't have anything to
1956 if (haves
&& !in_bitmapped_pack(bitmap_git
, haves
))
1960 /* if we don't want anything, we're done here */
1965 * now we're going to use bitmaps, so load the actual bitmap entries
1966 * from disk. this is the point of no return; after this the rev_list
1967 * becomes invalidated and we must perform the revwalk through bitmaps
1969 if (load_bitmap(revs
->repo
, bitmap_git
) < 0)
1972 if (!use_boundary_traversal
)
1973 object_array_clear(&revs
->pending
);
1976 if (use_boundary_traversal
) {
1977 trace2_region_enter("pack-bitmap", "haves/boundary", the_repository
);
1978 haves_bitmap
= find_boundary_objects(bitmap_git
, revs
, haves
);
1979 trace2_region_leave("pack-bitmap", "haves/boundary", the_repository
);
1981 trace2_region_enter("pack-bitmap", "haves/classic", the_repository
);
1982 revs
->ignore_missing_links
= 1;
1983 haves_bitmap
= find_objects(bitmap_git
, revs
, haves
, NULL
);
1984 reset_revision_walk();
1985 revs
->ignore_missing_links
= 0;
1986 trace2_region_leave("pack-bitmap", "haves/classic", the_repository
);
1990 BUG("failed to perform bitmap walk");
1993 if (use_boundary_traversal
) {
1994 object_array_clear(&revs
->pending
);
1995 reset_revision_walk();
1998 wants_bitmap
= find_objects(bitmap_git
, revs
, wants
, haves_bitmap
);
2001 BUG("failed to perform bitmap walk");
2004 bitmap_and_not(wants_bitmap
, haves_bitmap
);
2006 filter_bitmap(bitmap_git
,
2007 (revs
->filter
.choice
&& filter_provided_objects
) ? NULL
: wants
,
2012 filter_packed_objects_from_bitmap(bitmap_git
, wants_bitmap
);
2014 bitmap_git
->result
= wants_bitmap
;
2015 bitmap_git
->haves
= haves_bitmap
;
2017 object_list_free(&wants
);
2018 object_list_free(&haves
);
2020 trace2_data_intmax("bitmap", the_repository
, "pseudo_merges_satisfied",
2021 pseudo_merges_satisfied_nr
);
2022 trace2_data_intmax("bitmap", the_repository
, "pseudo_merges_cascades",
2023 pseudo_merges_cascades_nr
);
2024 trace2_data_intmax("bitmap", the_repository
, "bitmap/hits",
2025 existing_bitmaps_hits_nr
);
2026 trace2_data_intmax("bitmap", the_repository
, "bitmap/misses",
2027 existing_bitmaps_misses_nr
);
2028 trace2_data_intmax("bitmap", the_repository
, "bitmap/roots_with_bitmap",
2029 roots_with_bitmaps_nr
);
2030 trace2_data_intmax("bitmap", the_repository
, "bitmap/roots_without_bitmap",
2031 roots_without_bitmaps_nr
);
2036 free_bitmap_index(bitmap_git
);
2037 object_list_free(&wants
);
2038 object_list_free(&haves
);
2043 * -1 means "stop trying further objects"; 0 means we may or may not have
2044 * reused, but you can keep feeding bits.
2046 static int try_partial_reuse(struct bitmap_index
*bitmap_git
,
2047 struct bitmapped_pack
*pack
,
2050 struct bitmap
*reuse
,
2051 struct pack_window
**w_curs
)
2053 off_t offset
, delta_obj_offset
;
2054 enum object_type type
;
2057 if (pack_pos
>= pack
->p
->num_objects
)
2058 return -1; /* not actually in the pack */
2060 offset
= delta_obj_offset
= pack_pos_to_offset(pack
->p
, pack_pos
);
2061 type
= unpack_object_header(pack
->p
, w_curs
, &offset
, &size
);
2063 return -1; /* broken packfile, punt */
2065 if (type
== OBJ_REF_DELTA
|| type
== OBJ_OFS_DELTA
) {
2068 uint32_t base_bitmap_pos
;
2071 * Find the position of the base object so we can look it up
2072 * in our bitmaps. If we can't come up with an offset, or if
2073 * that offset is not in the revidx, the pack is corrupt.
2074 * There's nothing we can do, so just punt on this object,
2075 * and the normal slow path will complain about it in
2078 base_offset
= get_delta_base(pack
->p
, w_curs
, &offset
, type
,
2083 offset_to_pack_pos(pack
->p
, base_offset
, &base_pos
);
2085 if (bitmap_is_midx(bitmap_git
)) {
2087 * Cross-pack deltas are rejected for now, but could
2088 * theoretically be supported in the future.
2090 * We would need to ensure that we're sending both
2091 * halves of the delta/base pair, regardless of whether
2092 * or not the two cross a pack boundary. If they do,
2093 * then we must convert the delta to an REF_DELTA to
2094 * refer back to the base in the other pack.
2096 if (midx_pair_to_pack_pos(bitmap_git
->midx
,
2099 &base_bitmap_pos
) < 0) {
2103 if (offset_to_pack_pos(pack
->p
, base_offset
,
2107 * We assume delta dependencies always point backwards.
2108 * This lets us do a single pass, and is basically
2109 * always true due to the way OFS_DELTAs work. You would
2110 * not typically find REF_DELTA in a bitmapped pack,
2111 * since we only bitmap packs we write fresh, and
2112 * OFS_DELTA is the default). But let's double check to
2113 * make sure the pack wasn't written with odd
2116 if (base_pos
>= pack_pos
)
2118 base_bitmap_pos
= pack
->bitmap_pos
+ base_pos
;
2122 * And finally, if we're not sending the base as part of our
2123 * reuse chunk, then don't send this object either. The base
2124 * would come after us, along with other objects not
2125 * necessarily in the pack, which means we'd need to convert
2126 * to REF_DELTA on the fly. Better to just let the normal
2127 * object_entry code path handle it.
2129 if (!bitmap_get(reuse
, base_bitmap_pos
))
2134 * If we got here, then the object is OK to reuse. Mark it.
2136 bitmap_set(reuse
, bitmap_pos
);
2140 static void reuse_partial_packfile_from_bitmap_1(struct bitmap_index
*bitmap_git
,
2141 struct bitmapped_pack
*pack
,
2142 struct bitmap
*reuse
)
2144 struct bitmap
*result
= bitmap_git
->result
;
2145 struct pack_window
*w_curs
= NULL
;
2146 size_t pos
= pack
->bitmap_pos
/ BITS_IN_EWORD
;
2148 if (!pack
->bitmap_pos
) {
2150 * If we're processing the first (in the case of a MIDX, the
2151 * preferred pack) or the only (in the case of single-pack
2152 * bitmaps) pack, then we can reuse whole words at a time.
2154 * This is because we know that any deltas in this range *must*
2155 * have their bases chosen from the same pack, since:
2157 * - In the single pack case, there is no other pack to choose
2160 * - In the MIDX case, the first pack is the preferred pack, so
2161 * all ties are broken in favor of that pack (i.e. the one
2162 * we're currently processing). So any duplicate bases will be
2163 * resolved in favor of the pack we're processing.
2165 while (pos
< result
->word_alloc
&&
2166 pos
< pack
->bitmap_nr
/ BITS_IN_EWORD
&&
2167 result
->words
[pos
] == (eword_t
)~0)
2169 memset(reuse
->words
, 0xFF, pos
* sizeof(eword_t
));
2172 for (; pos
< result
->word_alloc
; pos
++) {
2173 eword_t word
= result
->words
[pos
];
2176 for (offset
= 0; offset
< BITS_IN_EWORD
; offset
++) {
2180 if (word
>> offset
== 0)
2183 offset
+= ewah_bit_ctz64(word
>> offset
);
2185 bit_pos
= pos
* BITS_IN_EWORD
+ offset
;
2186 if (bit_pos
< pack
->bitmap_pos
)
2188 if (bit_pos
>= pack
->bitmap_pos
+ pack
->bitmap_nr
)
2191 if (bitmap_is_midx(bitmap_git
)) {
2195 midx_pos
= pack_pos_to_midx(bitmap_git
->midx
, bit_pos
);
2196 ofs
= nth_midxed_offset(bitmap_git
->midx
, midx_pos
);
2198 if (offset_to_pack_pos(pack
->p
, ofs
, &pack_pos
) < 0)
2199 BUG("could not find object in pack %s "
2200 "at offset %"PRIuMAX
" in MIDX",
2201 pack_basename(pack
->p
), (uintmax_t)ofs
);
2203 pack_pos
= cast_size_t_to_uint32_t(st_sub(bit_pos
, pack
->bitmap_pos
));
2204 if (pack_pos
>= pack
->p
->num_objects
)
2205 BUG("advanced beyond the end of pack %s (%"PRIuMAX
" > %"PRIu32
")",
2206 pack_basename(pack
->p
), (uintmax_t)pack_pos
,
2207 pack
->p
->num_objects
);
2210 if (try_partial_reuse(bitmap_git
, pack
, bit_pos
,
2211 pack_pos
, reuse
, &w_curs
) < 0) {
2213 * try_partial_reuse indicated we couldn't reuse
2214 * any bits, so there is no point in trying more
2215 * bits in the current word, or any other words
2218 * Jump out of both loops to avoid future
2219 * unnecessary calls to try_partial_reuse.
2227 unuse_pack(&w_curs
);
2230 static int bitmapped_pack_cmp(const void *va
, const void *vb
)
2232 const struct bitmapped_pack
*a
= va
;
2233 const struct bitmapped_pack
*b
= vb
;
2235 if (a
->bitmap_pos
< b
->bitmap_pos
)
2237 if (a
->bitmap_pos
> b
->bitmap_pos
)
2242 void reuse_partial_packfile_from_bitmap(struct bitmap_index
*bitmap_git
,
2243 struct bitmapped_pack
**packs_out
,
2244 size_t *packs_nr_out
,
2245 struct bitmap
**reuse_out
,
2246 int multi_pack_reuse
)
2248 struct repository
*r
= the_repository
;
2249 struct bitmapped_pack
*packs
= NULL
;
2250 struct bitmap
*result
= bitmap_git
->result
;
2251 struct bitmap
*reuse
;
2253 size_t packs_nr
= 0, packs_alloc
= 0;
2255 uint32_t objects_nr
= 0;
2259 load_reverse_index(r
, bitmap_git
);
2261 if (!bitmap_is_midx(bitmap_git
) || !bitmap_git
->midx
->chunk_bitmapped_packs
)
2262 multi_pack_reuse
= 0;
2264 if (multi_pack_reuse
) {
2265 for (i
= 0; i
< bitmap_git
->midx
->num_packs
; i
++) {
2266 struct bitmapped_pack pack
;
2267 if (nth_bitmapped_pack(r
, bitmap_git
->midx
, &pack
, i
) < 0) {
2268 warning(_("unable to load pack: '%s', disabling pack-reuse"),
2269 bitmap_git
->midx
->pack_names
[i
]);
2274 if (!pack
.bitmap_nr
)
2277 ALLOC_GROW(packs
, packs_nr
+ 1, packs_alloc
);
2278 memcpy(&packs
[packs_nr
++], &pack
, sizeof(pack
));
2280 objects_nr
+= pack
.p
->num_objects
;
2283 QSORT(packs
, packs_nr
, bitmapped_pack_cmp
);
2285 struct packed_git
*pack
;
2286 uint32_t pack_int_id
;
2288 if (bitmap_is_midx(bitmap_git
)) {
2289 uint32_t preferred_pack_pos
;
2291 if (midx_preferred_pack(bitmap_git
->midx
, &preferred_pack_pos
) < 0) {
2292 warning(_("unable to compute preferred pack, disabling pack-reuse"));
2296 pack
= bitmap_git
->midx
->packs
[preferred_pack_pos
];
2297 pack_int_id
= preferred_pack_pos
;
2299 pack
= bitmap_git
->pack
;
2301 * Any value for 'pack_int_id' will do here. When we
2302 * process the pack via try_partial_reuse(), we won't
2303 * use the `pack_int_id` field since we have a non-MIDX
2306 * Use '-1' as a sentinel value to make it clear
2307 * that we do not expect to read this field.
2312 ALLOC_GROW(packs
, packs_nr
+ 1, packs_alloc
);
2313 packs
[packs_nr
].p
= pack
;
2314 packs
[packs_nr
].pack_int_id
= pack_int_id
;
2315 packs
[packs_nr
].bitmap_nr
= pack
->num_objects
;
2316 packs
[packs_nr
].bitmap_pos
= 0;
2318 objects_nr
= packs
[packs_nr
++].bitmap_nr
;
2321 word_alloc
= objects_nr
/ BITS_IN_EWORD
;
2322 if (objects_nr
% BITS_IN_EWORD
)
2324 reuse
= bitmap_word_alloc(word_alloc
);
2326 for (i
= 0; i
< packs_nr
; i
++)
2327 reuse_partial_packfile_from_bitmap_1(bitmap_git
, &packs
[i
], reuse
);
2329 if (bitmap_is_empty(reuse
)) {
2336 * Drop any reused objects from the result, since they will not
2337 * need to be handled separately.
2339 bitmap_and_not(result
, reuse
);
2341 *packs_nr_out
= packs_nr
;
2345 int bitmap_walk_contains(struct bitmap_index
*bitmap_git
,
2346 struct bitmap
*bitmap
, const struct object_id
*oid
)
2353 idx
= bitmap_position(bitmap_git
, oid
);
2354 return idx
>= 0 && bitmap_get(bitmap
, idx
);
2357 void traverse_bitmap_commit_list(struct bitmap_index
*bitmap_git
,
2358 struct rev_info
*revs
,
2359 show_reachable_fn show_reachable
)
2361 assert(bitmap_git
->result
);
2363 show_objects_for_type(bitmap_git
, OBJ_COMMIT
, show_reachable
);
2364 if (revs
->tree_objects
)
2365 show_objects_for_type(bitmap_git
, OBJ_TREE
, show_reachable
);
2366 if (revs
->blob_objects
)
2367 show_objects_for_type(bitmap_git
, OBJ_BLOB
, show_reachable
);
2368 if (revs
->tag_objects
)
2369 show_objects_for_type(bitmap_git
, OBJ_TAG
, show_reachable
);
2371 show_extended_objects(bitmap_git
, revs
, show_reachable
);
2374 static uint32_t count_object_type(struct bitmap_index
*bitmap_git
,
2375 enum object_type type
)
2377 struct bitmap
*objects
= bitmap_git
->result
;
2378 struct eindex
*eindex
= &bitmap_git
->ext_index
;
2380 uint32_t i
= 0, count
= 0;
2381 struct ewah_iterator it
;
2384 init_type_iterator(&it
, bitmap_git
, type
);
2386 while (i
< objects
->word_alloc
&& ewah_iterator_next(&filter
, &it
)) {
2387 eword_t word
= objects
->words
[i
++] & filter
;
2388 count
+= ewah_bit_popcount64(word
);
2391 for (i
= 0; i
< eindex
->count
; ++i
) {
2392 if (eindex
->objects
[i
]->type
== type
&&
2394 st_add(bitmap_num_objects(bitmap_git
), i
)))
2401 void count_bitmap_commit_list(struct bitmap_index
*bitmap_git
,
2402 uint32_t *commits
, uint32_t *trees
,
2403 uint32_t *blobs
, uint32_t *tags
)
2405 assert(bitmap_git
->result
);
2408 *commits
= count_object_type(bitmap_git
, OBJ_COMMIT
);
2411 *trees
= count_object_type(bitmap_git
, OBJ_TREE
);
2414 *blobs
= count_object_type(bitmap_git
, OBJ_BLOB
);
2417 *tags
= count_object_type(bitmap_git
, OBJ_TAG
);
2420 struct bitmap_test_data
{
2421 struct bitmap_index
*bitmap_git
;
2422 struct bitmap
*base
;
2423 struct bitmap
*commits
;
2424 struct bitmap
*trees
;
2425 struct bitmap
*blobs
;
2426 struct bitmap
*tags
;
2427 struct progress
*prg
;
2431 static void test_bitmap_type(struct bitmap_test_data
*tdata
,
2432 struct object
*obj
, int pos
)
2434 enum object_type bitmap_type
= OBJ_NONE
;
2437 if (bitmap_get(tdata
->commits
, pos
)) {
2438 bitmap_type
= OBJ_COMMIT
;
2441 if (bitmap_get(tdata
->trees
, pos
)) {
2442 bitmap_type
= OBJ_TREE
;
2445 if (bitmap_get(tdata
->blobs
, pos
)) {
2446 bitmap_type
= OBJ_BLOB
;
2449 if (bitmap_get(tdata
->tags
, pos
)) {
2450 bitmap_type
= OBJ_TAG
;
2454 if (bitmap_type
== OBJ_NONE
)
2455 die(_("object '%s' not found in type bitmaps"),
2456 oid_to_hex(&obj
->oid
));
2459 die(_("object '%s' does not have a unique type"),
2460 oid_to_hex(&obj
->oid
));
2462 if (bitmap_type
!= obj
->type
)
2463 die(_("object '%s': real type '%s', expected: '%s'"),
2464 oid_to_hex(&obj
->oid
),
2465 type_name(obj
->type
),
2466 type_name(bitmap_type
));
2469 static void test_show_object(struct object
*object
,
2470 const char *name UNUSED
,
2473 struct bitmap_test_data
*tdata
= data
;
2476 bitmap_pos
= bitmap_position(tdata
->bitmap_git
, &object
->oid
);
2478 die(_("object not in bitmap: '%s'"), oid_to_hex(&object
->oid
));
2479 test_bitmap_type(tdata
, object
, bitmap_pos
);
2481 bitmap_set(tdata
->base
, bitmap_pos
);
2482 display_progress(tdata
->prg
, ++tdata
->seen
);
2485 static void test_show_commit(struct commit
*commit
, void *data
)
2487 struct bitmap_test_data
*tdata
= data
;
2490 bitmap_pos
= bitmap_position(tdata
->bitmap_git
,
2491 &commit
->object
.oid
);
2493 die(_("object not in bitmap: '%s'"), oid_to_hex(&commit
->object
.oid
));
2494 test_bitmap_type(tdata
, &commit
->object
, bitmap_pos
);
2496 bitmap_set(tdata
->base
, bitmap_pos
);
2497 display_progress(tdata
->prg
, ++tdata
->seen
);
2500 void test_bitmap_walk(struct rev_info
*revs
)
2502 struct object
*root
;
2503 struct bitmap
*result
= NULL
;
2504 size_t result_popcnt
;
2505 struct bitmap_test_data tdata
;
2506 struct bitmap_index
*bitmap_git
;
2507 struct ewah_bitmap
*bm
;
2509 if (!(bitmap_git
= prepare_bitmap_git(revs
->repo
)))
2510 die(_("failed to load bitmap indexes"));
2512 if (revs
->pending
.nr
!= 1)
2513 die(_("you must specify exactly one commit to test"));
2515 fprintf_ln(stderr
, "Bitmap v%d test (%d entries%s)",
2516 bitmap_git
->version
,
2517 bitmap_git
->entry_count
,
2518 bitmap_git
->table_lookup
? "" : " loaded");
2520 root
= revs
->pending
.objects
[0].item
;
2521 bm
= bitmap_for_commit(bitmap_git
, (struct commit
*)root
);
2524 fprintf_ln(stderr
, "Found bitmap for '%s'. %d bits / %08x checksum",
2525 oid_to_hex(&root
->oid
), (int)bm
->bit_size
, ewah_checksum(bm
));
2527 result
= ewah_to_bitmap(bm
);
2531 die(_("commit '%s' doesn't have an indexed bitmap"), oid_to_hex(&root
->oid
));
2533 revs
->tag_objects
= 1;
2534 revs
->tree_objects
= 1;
2535 revs
->blob_objects
= 1;
2537 result_popcnt
= bitmap_popcount(result
);
2539 if (prepare_revision_walk(revs
))
2540 die(_("revision walk setup failed"));
2542 tdata
.bitmap_git
= bitmap_git
;
2543 tdata
.base
= bitmap_new();
2544 tdata
.commits
= ewah_to_bitmap(bitmap_git
->commits
);
2545 tdata
.trees
= ewah_to_bitmap(bitmap_git
->trees
);
2546 tdata
.blobs
= ewah_to_bitmap(bitmap_git
->blobs
);
2547 tdata
.tags
= ewah_to_bitmap(bitmap_git
->tags
);
2548 tdata
.prg
= start_progress("Verifying bitmap entries", result_popcnt
);
2551 traverse_commit_list(revs
, &test_show_commit
, &test_show_object
, &tdata
);
2553 stop_progress(&tdata
.prg
);
2555 if (bitmap_equals(result
, tdata
.base
))
2556 fprintf_ln(stderr
, "OK!");
2558 die(_("mismatch in bitmap results"));
2560 bitmap_free(result
);
2561 bitmap_free(tdata
.base
);
2562 bitmap_free(tdata
.commits
);
2563 bitmap_free(tdata
.trees
);
2564 bitmap_free(tdata
.blobs
);
2565 bitmap_free(tdata
.tags
);
2566 free_bitmap_index(bitmap_git
);
2569 int test_bitmap_commits(struct repository
*r
)
2571 struct object_id oid
;
2572 MAYBE_UNUSED
void *value
;
2573 struct bitmap_index
*bitmap_git
= prepare_bitmap_git(r
);
2576 die(_("failed to load bitmap indexes"));
2579 * As this function is only used to print bitmap selected
2580 * commits, we don't have to read the commit table.
2582 if (bitmap_git
->table_lookup
) {
2583 if (load_bitmap_entries_v1(bitmap_git
) < 0)
2584 die(_("failed to load bitmap indexes"));
2587 kh_foreach(bitmap_git
->bitmaps
, oid
, value
, {
2588 printf_ln("%s", oid_to_hex(&oid
));
2591 free_bitmap_index(bitmap_git
);
2596 int test_bitmap_hashes(struct repository
*r
)
2598 struct bitmap_index
*bitmap_git
= prepare_bitmap_git(r
);
2599 struct object_id oid
;
2600 uint32_t i
, index_pos
;
2602 if (!bitmap_git
|| !bitmap_git
->hashes
)
2605 for (i
= 0; i
< bitmap_num_objects(bitmap_git
); i
++) {
2606 if (bitmap_is_midx(bitmap_git
))
2607 index_pos
= pack_pos_to_midx(bitmap_git
->midx
, i
);
2609 index_pos
= pack_pos_to_index(bitmap_git
->pack
, i
);
2611 nth_bitmap_object_oid(bitmap_git
, &oid
, index_pos
);
2613 printf_ln("%s %"PRIu32
"",
2614 oid_to_hex(&oid
), get_be32(bitmap_git
->hashes
+ index_pos
));
2618 free_bitmap_index(bitmap_git
);
2623 static void bit_pos_to_object_id(struct bitmap_index
*bitmap_git
,
2625 struct object_id
*oid
)
2629 if (bitmap_is_midx(bitmap_git
))
2630 index_pos
= pack_pos_to_midx(bitmap_git
->midx
, bit_pos
);
2632 index_pos
= pack_pos_to_index(bitmap_git
->pack
, bit_pos
);
2634 nth_bitmap_object_oid(bitmap_git
, oid
, index_pos
);
2637 int test_bitmap_pseudo_merges(struct repository
*r
)
2639 struct bitmap_index
*bitmap_git
;
2642 bitmap_git
= prepare_bitmap_git(r
);
2643 if (!bitmap_git
|| !bitmap_git
->pseudo_merges
.nr
)
2646 for (i
= 0; i
< bitmap_git
->pseudo_merges
.nr
; i
++) {
2647 struct pseudo_merge
*merge
;
2648 struct ewah_bitmap
*commits_bitmap
, *merge_bitmap
;
2650 merge
= use_pseudo_merge(&bitmap_git
->pseudo_merges
,
2651 &bitmap_git
->pseudo_merges
.v
[i
]);
2652 commits_bitmap
= merge
->commits
;
2653 merge_bitmap
= pseudo_merge_bitmap(&bitmap_git
->pseudo_merges
,
2656 printf("at=%"PRIuMAX
", commits=%"PRIuMAX
", objects=%"PRIuMAX
"\n",
2657 (uintmax_t)merge
->at
,
2658 (uintmax_t)ewah_bitmap_popcount(commits_bitmap
),
2659 (uintmax_t)ewah_bitmap_popcount(merge_bitmap
));
2663 free_bitmap_index(bitmap_git
);
2667 static void dump_ewah_object_ids(struct bitmap_index
*bitmap_git
,
2668 struct ewah_bitmap
*bitmap
)
2671 struct ewah_iterator it
;
2675 ewah_iterator_init(&it
, bitmap
);
2677 while (ewah_iterator_next(&word
, &it
)) {
2678 struct object_id oid
;
2681 for (offset
= 0; offset
< BITS_IN_EWORD
; offset
++) {
2682 if (!(word
>> offset
))
2685 offset
+= ewah_bit_ctz64(word
>> offset
);
2687 bit_pos_to_object_id(bitmap_git
, pos
+ offset
, &oid
);
2688 printf("%s\n", oid_to_hex(&oid
));
2690 pos
+= BITS_IN_EWORD
;
2694 int test_bitmap_pseudo_merge_commits(struct repository
*r
, uint32_t n
)
2696 struct bitmap_index
*bitmap_git
;
2697 struct pseudo_merge
*merge
;
2700 bitmap_git
= prepare_bitmap_git(r
);
2701 if (!bitmap_git
|| !bitmap_git
->pseudo_merges
.nr
)
2704 if (n
>= bitmap_git
->pseudo_merges
.nr
) {
2705 ret
= error(_("pseudo-merge index out of range "
2706 "(%"PRIu32
" >= %"PRIuMAX
")"),
2707 n
, (uintmax_t)bitmap_git
->pseudo_merges
.nr
);
2711 merge
= use_pseudo_merge(&bitmap_git
->pseudo_merges
,
2712 &bitmap_git
->pseudo_merges
.v
[n
]);
2713 dump_ewah_object_ids(bitmap_git
, merge
->commits
);
2716 free_bitmap_index(bitmap_git
);
2720 int test_bitmap_pseudo_merge_objects(struct repository
*r
, uint32_t n
)
2722 struct bitmap_index
*bitmap_git
;
2723 struct pseudo_merge
*merge
;
2726 bitmap_git
= prepare_bitmap_git(r
);
2727 if (!bitmap_git
|| !bitmap_git
->pseudo_merges
.nr
)
2730 if (n
>= bitmap_git
->pseudo_merges
.nr
) {
2731 ret
= error(_("pseudo-merge index out of range "
2732 "(%"PRIu32
" >= %"PRIuMAX
")"),
2733 n
, (uintmax_t)bitmap_git
->pseudo_merges
.nr
);
2737 merge
= use_pseudo_merge(&bitmap_git
->pseudo_merges
,
2738 &bitmap_git
->pseudo_merges
.v
[n
]);
2740 dump_ewah_object_ids(bitmap_git
,
2741 pseudo_merge_bitmap(&bitmap_git
->pseudo_merges
,
2745 free_bitmap_index(bitmap_git
);
2749 int rebuild_bitmap(const uint32_t *reposition
,
2750 struct ewah_bitmap
*source
,
2751 struct bitmap
*dest
)
2754 struct ewah_iterator it
;
2757 ewah_iterator_init(&it
, source
);
2759 while (ewah_iterator_next(&word
, &it
)) {
2760 uint32_t offset
, bit_pos
;
2762 for (offset
= 0; offset
< BITS_IN_EWORD
; ++offset
) {
2763 if ((word
>> offset
) == 0)
2766 offset
+= ewah_bit_ctz64(word
>> offset
);
2768 bit_pos
= reposition
[pos
+ offset
];
2770 bitmap_set(dest
, bit_pos
- 1);
2771 else /* can't reuse, we don't have the object */
2775 pos
+= BITS_IN_EWORD
;
2780 uint32_t *create_bitmap_mapping(struct bitmap_index
*bitmap_git
,
2781 struct packing_data
*mapping
)
2783 struct repository
*r
= the_repository
;
2784 uint32_t i
, num_objects
;
2785 uint32_t *reposition
;
2787 if (!bitmap_is_midx(bitmap_git
))
2788 load_reverse_index(r
, bitmap_git
);
2789 else if (load_midx_revindex(bitmap_git
->midx
))
2790 BUG("rebuild_existing_bitmaps: missing required rev-cache "
2793 num_objects
= bitmap_num_objects(bitmap_git
);
2794 CALLOC_ARRAY(reposition
, num_objects
);
2796 for (i
= 0; i
< num_objects
; ++i
) {
2797 struct object_id oid
;
2798 struct object_entry
*oe
;
2801 if (bitmap_is_midx(bitmap_git
))
2802 index_pos
= pack_pos_to_midx(bitmap_git
->midx
, i
);
2804 index_pos
= pack_pos_to_index(bitmap_git
->pack
, i
);
2805 nth_bitmap_object_oid(bitmap_git
, &oid
, index_pos
);
2806 oe
= packlist_find(mapping
, &oid
);
2809 reposition
[i
] = oe_in_pack_pos(mapping
, oe
) + 1;
2810 if (bitmap_git
->hashes
&& !oe
->hash
)
2811 oe
->hash
= get_be32(bitmap_git
->hashes
+ index_pos
);
2818 void free_bitmap_index(struct bitmap_index
*b
)
2824 munmap(b
->map
, b
->map_size
);
2825 ewah_pool_free(b
->commits
);
2826 ewah_pool_free(b
->trees
);
2827 ewah_pool_free(b
->blobs
);
2828 ewah_pool_free(b
->tags
);
2830 struct stored_bitmap
*sb
;
2831 kh_foreach_value(b
->bitmaps
, sb
, {
2832 ewah_pool_free(sb
->root
);
2836 kh_destroy_oid_map(b
->bitmaps
);
2837 free(b
->ext_index
.objects
);
2838 free(b
->ext_index
.hashes
);
2839 kh_destroy_oid_pos(b
->ext_index
.positions
);
2840 bitmap_free(b
->result
);
2841 bitmap_free(b
->haves
);
2842 if (bitmap_is_midx(b
)) {
2844 * Multi-pack bitmaps need to have resources associated with
2845 * their on-disk reverse indexes unmapped so that stale .rev and
2846 * .bitmap files can be removed.
2848 * Unlike pack-based bitmaps, multi-pack bitmaps can be read and
2849 * written in the same 'git multi-pack-index write --bitmap'
2850 * process. Close resources so they can be removed safely on
2851 * platforms like Windows.
2853 close_midx_revindex(b
->midx
);
2855 free_pseudo_merge_map(&b
->pseudo_merges
);
2859 int bitmap_has_oid_in_uninteresting(struct bitmap_index
*bitmap_git
,
2860 const struct object_id
*oid
)
2862 return bitmap_git
&&
2863 bitmap_walk_contains(bitmap_git
, bitmap_git
->haves
, oid
);
2866 static off_t
get_disk_usage_for_type(struct bitmap_index
*bitmap_git
,
2867 enum object_type object_type
)
2869 struct bitmap
*result
= bitmap_git
->result
;
2871 struct ewah_iterator it
;
2875 init_type_iterator(&it
, bitmap_git
, object_type
);
2876 for (i
= 0; i
< result
->word_alloc
&&
2877 ewah_iterator_next(&filter
, &it
); i
++) {
2878 eword_t word
= result
->words
[i
] & filter
;
2879 size_t base
= (i
* BITS_IN_EWORD
);
2885 for (offset
= 0; offset
< BITS_IN_EWORD
; offset
++) {
2886 if ((word
>> offset
) == 0)
2889 offset
+= ewah_bit_ctz64(word
>> offset
);
2891 if (bitmap_is_midx(bitmap_git
)) {
2893 uint32_t midx_pos
= pack_pos_to_midx(bitmap_git
->midx
, base
+ offset
);
2894 off_t offset
= nth_midxed_offset(bitmap_git
->midx
, midx_pos
);
2896 uint32_t pack_id
= nth_midxed_pack_int_id(bitmap_git
->midx
, midx_pos
);
2897 struct packed_git
*pack
= bitmap_git
->midx
->packs
[pack_id
];
2899 if (offset_to_pack_pos(pack
, offset
, &pack_pos
) < 0) {
2900 struct object_id oid
;
2901 nth_midxed_object_oid(&oid
, bitmap_git
->midx
, midx_pos
);
2903 die(_("could not find '%s' in pack '%s' at offset %"PRIuMAX
),
2909 total
+= pack_pos_to_offset(pack
, pack_pos
+ 1) - offset
;
2911 size_t pos
= base
+ offset
;
2912 total
+= pack_pos_to_offset(bitmap_git
->pack
, pos
+ 1) -
2913 pack_pos_to_offset(bitmap_git
->pack
, pos
);
2921 static off_t
get_disk_usage_for_extended(struct bitmap_index
*bitmap_git
)
2923 struct bitmap
*result
= bitmap_git
->result
;
2924 struct eindex
*eindex
= &bitmap_git
->ext_index
;
2926 struct object_info oi
= OBJECT_INFO_INIT
;
2930 oi
.disk_sizep
= &object_size
;
2932 for (i
= 0; i
< eindex
->count
; i
++) {
2933 struct object
*obj
= eindex
->objects
[i
];
2935 if (!bitmap_get(result
,
2936 st_add(bitmap_num_objects(bitmap_git
), i
)))
2939 if (oid_object_info_extended(the_repository
, &obj
->oid
, &oi
, 0) < 0)
2940 die(_("unable to get disk usage of '%s'"),
2941 oid_to_hex(&obj
->oid
));
2943 total
+= object_size
;
2948 off_t
get_disk_usage_from_bitmap(struct bitmap_index
*bitmap_git
,
2949 struct rev_info
*revs
)
2953 total
+= get_disk_usage_for_type(bitmap_git
, OBJ_COMMIT
);
2954 if (revs
->tree_objects
)
2955 total
+= get_disk_usage_for_type(bitmap_git
, OBJ_TREE
);
2956 if (revs
->blob_objects
)
2957 total
+= get_disk_usage_for_type(bitmap_git
, OBJ_BLOB
);
2958 if (revs
->tag_objects
)
2959 total
+= get_disk_usage_for_type(bitmap_git
, OBJ_TAG
);
2961 total
+= get_disk_usage_for_extended(bitmap_git
);
2966 int bitmap_is_midx(struct bitmap_index
*bitmap_git
)
2968 return !!bitmap_git
->midx
;
2971 const struct string_list
*bitmap_preferred_tips(struct repository
*r
)
2973 const struct string_list
*dest
;
2975 if (!repo_config_get_string_multi(r
, "pack.preferbitmaptips", &dest
))
2980 int bitmap_is_preferred_refname(struct repository
*r
, const char *refname
)
2982 const struct string_list
*preferred_tips
= bitmap_preferred_tips(r
);
2983 struct string_list_item
*item
;
2985 if (!preferred_tips
)
2988 for_each_string_list_item(item
, preferred_tips
) {
2989 if (starts_with(refname
, item
->string
))
2996 static int verify_bitmap_file(const char *name
)
2999 unsigned char *data
;
3000 int fd
= git_open(name
);
3003 /* It is OK to not have the file. */
3004 if (fd
< 0 || fstat(fd
, &st
)) {
3010 data
= xmmap(NULL
, st
.st_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0);
3012 if (!hashfile_checksum_valid(data
, st
.st_size
))
3013 res
= error(_("bitmap file '%s' has invalid checksum"),
3016 munmap(data
, st
.st_size
);
3020 int verify_bitmap_files(struct repository
*r
)
3024 for (struct multi_pack_index
*m
= get_multi_pack_index(r
);
3026 char *midx_bitmap_name
= midx_bitmap_filename(m
);
3027 res
|= verify_bitmap_file(midx_bitmap_name
);
3028 free(midx_bitmap_name
);
3031 for (struct packed_git
*p
= get_all_packs(r
);
3033 char *pack_bitmap_name
= pack_bitmap_filename(p
);
3034 res
|= verify_bitmap_file(pack_bitmap_name
);
3035 free(pack_bitmap_name
);