t/gpg: simplify test for unknown key
[git/debian.git] / pack-bitmap.c
blobf47a0a7db4dd30a6450b3e59e0ec463c5578da39
1 #include "cache.h"
2 #include "commit.h"
3 #include "tag.h"
4 #include "diff.h"
5 #include "revision.h"
6 #include "progress.h"
7 #include "list-objects.h"
8 #include "pack.h"
9 #include "pack-bitmap.h"
10 #include "pack-revindex.h"
11 #include "pack-objects.h"
12 #include "packfile.h"
13 #include "repository.h"
14 #include "object-store.h"
15 #include "list-objects-filter-options.h"
16 #include "midx.h"
17 #include "config.h"
20 * An entry on the bitmap index, representing the bitmap for a given
21 * commit.
23 struct stored_bitmap {
24 struct object_id oid;
25 struct ewah_bitmap *root;
26 struct stored_bitmap *xor;
27 int flags;
31 * The active bitmap index for a repository. By design, repositories only have
32 * a single bitmap index available (the index for the biggest packfile in
33 * the repository), since bitmap indexes need full closure.
35 * If there is more than one bitmap index available (e.g. because of alternates),
36 * the active bitmap index is the largest one.
38 struct bitmap_index {
40 * The pack or multi-pack index (MIDX) that this bitmap index belongs
41 * to.
43 * Exactly one of these must be non-NULL; this specifies the object
44 * order used to interpret this bitmap.
46 struct packed_git *pack;
47 struct multi_pack_index *midx;
50 * Mark the first `reuse_objects` in the packfile as reused:
51 * they will be sent as-is without using them for repacking
52 * calculations
54 uint32_t reuse_objects;
56 /* mmapped buffer of the whole bitmap index */
57 unsigned char *map;
58 size_t map_size; /* size of the mmaped buffer */
59 size_t map_pos; /* current position when loading the index */
62 * Type indexes.
64 * Each bitmap marks which objects in the packfile are of the given
65 * type. This provides type information when yielding the objects from
66 * the packfile during a walk, which allows for better delta bases.
68 struct ewah_bitmap *commits;
69 struct ewah_bitmap *trees;
70 struct ewah_bitmap *blobs;
71 struct ewah_bitmap *tags;
73 /* Map from object ID -> `stored_bitmap` for all the bitmapped commits */
74 kh_oid_map_t *bitmaps;
76 /* Number of bitmapped commits */
77 uint32_t entry_count;
79 /* If not NULL, this is a name-hash cache pointing into map. */
80 uint32_t *hashes;
82 /* The checksum of the packfile or MIDX; points into map. */
83 const unsigned char *checksum;
86 * Extended index.
88 * When trying to perform bitmap operations with objects that are not
89 * packed in `pack`, these objects are added to this "fake index" and
90 * are assumed to appear at the end of the packfile for all operations
92 struct eindex {
93 struct object **objects;
94 uint32_t *hashes;
95 uint32_t count, alloc;
96 kh_oid_pos_t *positions;
97 } ext_index;
99 /* Bitmap result of the last performed walk */
100 struct bitmap *result;
102 /* "have" bitmap from the last performed walk */
103 struct bitmap *haves;
105 /* Version of the bitmap index */
106 unsigned int version;
109 static struct ewah_bitmap *lookup_stored_bitmap(struct stored_bitmap *st)
111 struct ewah_bitmap *parent;
112 struct ewah_bitmap *composed;
114 if (st->xor == NULL)
115 return st->root;
117 composed = ewah_pool_new();
118 parent = lookup_stored_bitmap(st->xor);
119 ewah_xor(st->root, parent, composed);
121 ewah_pool_free(st->root);
122 st->root = composed;
123 st->xor = NULL;
125 return composed;
129 * Read a bitmap from the current read position on the mmaped
130 * index, and increase the read position accordingly
132 static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *index)
134 struct ewah_bitmap *b = ewah_pool_new();
136 ssize_t bitmap_size = ewah_read_mmap(b,
137 index->map + index->map_pos,
138 index->map_size - index->map_pos);
140 if (bitmap_size < 0) {
141 error("Failed to load bitmap index (corrupted?)");
142 ewah_pool_free(b);
143 return NULL;
146 index->map_pos += bitmap_size;
147 return b;
150 static uint32_t bitmap_num_objects(struct bitmap_index *index)
152 if (index->midx)
153 return index->midx->num_objects;
154 return index->pack->num_objects;
157 static int load_bitmap_header(struct bitmap_index *index)
159 struct bitmap_disk_header *header = (void *)index->map;
160 size_t header_size = sizeof(*header) - GIT_MAX_RAWSZ + the_hash_algo->rawsz;
162 if (index->map_size < header_size + the_hash_algo->rawsz)
163 return error("Corrupted bitmap index (too small)");
165 if (memcmp(header->magic, BITMAP_IDX_SIGNATURE, sizeof(BITMAP_IDX_SIGNATURE)) != 0)
166 return error("Corrupted bitmap index file (wrong header)");
168 index->version = ntohs(header->version);
169 if (index->version != 1)
170 return error("Unsupported version for bitmap index file (%d)", index->version);
172 /* Parse known bitmap format options */
174 uint32_t flags = ntohs(header->options);
175 size_t cache_size = st_mult(bitmap_num_objects(index), sizeof(uint32_t));
176 unsigned char *index_end = index->map + index->map_size - the_hash_algo->rawsz;
178 if ((flags & BITMAP_OPT_FULL_DAG) == 0)
179 return error("Unsupported options for bitmap index file "
180 "(Git requires BITMAP_OPT_FULL_DAG)");
182 if (flags & BITMAP_OPT_HASH_CACHE) {
183 if (cache_size > index_end - index->map - header_size)
184 return error("corrupted bitmap index file (too short to fit hash cache)");
185 index->hashes = (void *)(index_end - cache_size);
186 index_end -= cache_size;
190 index->entry_count = ntohl(header->entry_count);
191 index->checksum = header->checksum;
192 index->map_pos += header_size;
193 return 0;
196 static struct stored_bitmap *store_bitmap(struct bitmap_index *index,
197 struct ewah_bitmap *root,
198 const struct object_id *oid,
199 struct stored_bitmap *xor_with,
200 int flags)
202 struct stored_bitmap *stored;
203 khiter_t hash_pos;
204 int ret;
206 stored = xmalloc(sizeof(struct stored_bitmap));
207 stored->root = root;
208 stored->xor = xor_with;
209 stored->flags = flags;
210 oidcpy(&stored->oid, oid);
212 hash_pos = kh_put_oid_map(index->bitmaps, stored->oid, &ret);
214 /* a 0 return code means the insertion succeeded with no changes,
215 * because the SHA1 already existed on the map. this is bad, there
216 * shouldn't be duplicated commits in the index */
217 if (ret == 0) {
218 error("Duplicate entry in bitmap index: %s", oid_to_hex(oid));
219 return NULL;
222 kh_value(index->bitmaps, hash_pos) = stored;
223 return stored;
226 static inline uint32_t read_be32(const unsigned char *buffer, size_t *pos)
228 uint32_t result = get_be32(buffer + *pos);
229 (*pos) += sizeof(result);
230 return result;
233 static inline uint8_t read_u8(const unsigned char *buffer, size_t *pos)
235 return buffer[(*pos)++];
238 #define MAX_XOR_OFFSET 160
240 static int nth_bitmap_object_oid(struct bitmap_index *index,
241 struct object_id *oid,
242 uint32_t n)
244 if (index->midx)
245 return nth_midxed_object_oid(oid, index->midx, n) ? 0 : -1;
246 return nth_packed_object_id(oid, index->pack, n);
249 static int load_bitmap_entries_v1(struct bitmap_index *index)
251 uint32_t i;
252 struct stored_bitmap *recent_bitmaps[MAX_XOR_OFFSET] = { NULL };
254 for (i = 0; i < index->entry_count; ++i) {
255 int xor_offset, flags;
256 struct ewah_bitmap *bitmap = NULL;
257 struct stored_bitmap *xor_bitmap = NULL;
258 uint32_t commit_idx_pos;
259 struct object_id oid;
261 if (index->map_size - index->map_pos < 6)
262 return error("corrupt ewah bitmap: truncated header for entry %d", i);
264 commit_idx_pos = read_be32(index->map, &index->map_pos);
265 xor_offset = read_u8(index->map, &index->map_pos);
266 flags = read_u8(index->map, &index->map_pos);
268 if (nth_bitmap_object_oid(index, &oid, commit_idx_pos) < 0)
269 return error("corrupt ewah bitmap: commit index %u out of range",
270 (unsigned)commit_idx_pos);
272 bitmap = read_bitmap_1(index);
273 if (!bitmap)
274 return -1;
276 if (xor_offset > MAX_XOR_OFFSET || xor_offset > i)
277 return error("Corrupted bitmap pack index");
279 if (xor_offset > 0) {
280 xor_bitmap = recent_bitmaps[(i - xor_offset) % MAX_XOR_OFFSET];
282 if (xor_bitmap == NULL)
283 return error("Invalid XOR offset in bitmap pack index");
286 recent_bitmaps[i % MAX_XOR_OFFSET] = store_bitmap(
287 index, bitmap, &oid, xor_bitmap, flags);
290 return 0;
293 char *midx_bitmap_filename(struct multi_pack_index *midx)
295 return xstrfmt("%s-%s.bitmap",
296 get_midx_filename(midx->object_dir),
297 hash_to_hex(get_midx_checksum(midx)));
300 char *pack_bitmap_filename(struct packed_git *p)
302 size_t len;
304 if (!strip_suffix(p->pack_name, ".pack", &len))
305 BUG("pack_name does not end in .pack");
306 return xstrfmt("%.*s.bitmap", (int)len, p->pack_name);
309 static int open_midx_bitmap_1(struct bitmap_index *bitmap_git,
310 struct multi_pack_index *midx)
312 struct stat st;
313 char *idx_name = midx_bitmap_filename(midx);
314 int fd = git_open(idx_name);
316 free(idx_name);
318 if (fd < 0)
319 return -1;
321 if (fstat(fd, &st)) {
322 close(fd);
323 return -1;
326 if (bitmap_git->pack || bitmap_git->midx) {
327 /* ignore extra bitmap file; we can only handle one */
328 warning("ignoring extra bitmap file: %s",
329 get_midx_filename(midx->object_dir));
330 close(fd);
331 return -1;
334 bitmap_git->midx = midx;
335 bitmap_git->map_size = xsize_t(st.st_size);
336 bitmap_git->map_pos = 0;
337 bitmap_git->map = xmmap(NULL, bitmap_git->map_size, PROT_READ,
338 MAP_PRIVATE, fd, 0);
339 close(fd);
341 if (load_bitmap_header(bitmap_git) < 0)
342 goto cleanup;
344 if (!hasheq(get_midx_checksum(bitmap_git->midx), bitmap_git->checksum))
345 goto cleanup;
347 if (load_midx_revindex(bitmap_git->midx) < 0) {
348 warning(_("multi-pack bitmap is missing required reverse index"));
349 goto cleanup;
351 return 0;
353 cleanup:
354 munmap(bitmap_git->map, bitmap_git->map_size);
355 bitmap_git->map_size = 0;
356 bitmap_git->map = NULL;
357 return -1;
360 static int open_pack_bitmap_1(struct bitmap_index *bitmap_git, struct packed_git *packfile)
362 int fd;
363 struct stat st;
364 char *idx_name;
366 if (open_pack_index(packfile))
367 return -1;
369 idx_name = pack_bitmap_filename(packfile);
370 fd = git_open(idx_name);
371 free(idx_name);
373 if (fd < 0)
374 return -1;
376 if (fstat(fd, &st)) {
377 close(fd);
378 return -1;
381 if (bitmap_git->pack || bitmap_git->midx) {
382 /* ignore extra bitmap file; we can only handle one */
383 warning("ignoring extra bitmap file: %s", packfile->pack_name);
384 close(fd);
385 return -1;
388 if (!is_pack_valid(packfile)) {
389 close(fd);
390 return -1;
393 bitmap_git->pack = packfile;
394 bitmap_git->map_size = xsize_t(st.st_size);
395 bitmap_git->map = xmmap(NULL, bitmap_git->map_size, PROT_READ, MAP_PRIVATE, fd, 0);
396 bitmap_git->map_pos = 0;
397 close(fd);
399 if (load_bitmap_header(bitmap_git) < 0) {
400 munmap(bitmap_git->map, bitmap_git->map_size);
401 bitmap_git->map = NULL;
402 bitmap_git->map_size = 0;
403 return -1;
406 return 0;
409 static int load_reverse_index(struct bitmap_index *bitmap_git)
411 if (bitmap_is_midx(bitmap_git)) {
412 uint32_t i;
413 int ret;
416 * The multi-pack-index's .rev file is already loaded via
417 * open_pack_bitmap_1().
419 * But we still need to open the individual pack .rev files,
420 * since we will need to make use of them in pack-objects.
422 for (i = 0; i < bitmap_git->midx->num_packs; i++) {
423 if (prepare_midx_pack(the_repository, bitmap_git->midx, i))
424 die(_("load_reverse_index: could not open pack"));
425 ret = load_pack_revindex(bitmap_git->midx->packs[i]);
426 if (ret)
427 return ret;
429 return 0;
431 return load_pack_revindex(bitmap_git->pack);
434 static int load_bitmap(struct bitmap_index *bitmap_git)
436 assert(bitmap_git->map);
438 bitmap_git->bitmaps = kh_init_oid_map();
439 bitmap_git->ext_index.positions = kh_init_oid_pos();
441 if (load_reverse_index(bitmap_git))
442 goto failed;
444 if (!(bitmap_git->commits = read_bitmap_1(bitmap_git)) ||
445 !(bitmap_git->trees = read_bitmap_1(bitmap_git)) ||
446 !(bitmap_git->blobs = read_bitmap_1(bitmap_git)) ||
447 !(bitmap_git->tags = read_bitmap_1(bitmap_git)))
448 goto failed;
450 if (load_bitmap_entries_v1(bitmap_git) < 0)
451 goto failed;
453 return 0;
455 failed:
456 munmap(bitmap_git->map, bitmap_git->map_size);
457 bitmap_git->map = NULL;
458 bitmap_git->map_size = 0;
460 kh_destroy_oid_map(bitmap_git->bitmaps);
461 bitmap_git->bitmaps = NULL;
463 kh_destroy_oid_pos(bitmap_git->ext_index.positions);
464 bitmap_git->ext_index.positions = NULL;
466 return -1;
469 static int open_pack_bitmap(struct repository *r,
470 struct bitmap_index *bitmap_git)
472 struct packed_git *p;
473 int ret = -1;
475 assert(!bitmap_git->map);
477 for (p = get_all_packs(r); p; p = p->next) {
478 if (open_pack_bitmap_1(bitmap_git, p) == 0)
479 ret = 0;
482 return ret;
485 static int open_midx_bitmap(struct repository *r,
486 struct bitmap_index *bitmap_git)
488 struct multi_pack_index *midx;
490 assert(!bitmap_git->map);
492 for (midx = get_multi_pack_index(r); midx; midx = midx->next) {
493 if (!open_midx_bitmap_1(bitmap_git, midx))
494 return 0;
496 return -1;
499 static int open_bitmap(struct repository *r,
500 struct bitmap_index *bitmap_git)
502 assert(!bitmap_git->map);
504 if (!open_midx_bitmap(r, bitmap_git))
505 return 0;
506 return open_pack_bitmap(r, bitmap_git);
509 struct bitmap_index *prepare_bitmap_git(struct repository *r)
511 struct bitmap_index *bitmap_git = xcalloc(1, sizeof(*bitmap_git));
513 if (!open_bitmap(r, bitmap_git) && !load_bitmap(bitmap_git))
514 return bitmap_git;
516 free_bitmap_index(bitmap_git);
517 return NULL;
520 struct bitmap_index *prepare_midx_bitmap_git(struct multi_pack_index *midx)
522 struct bitmap_index *bitmap_git = xcalloc(1, sizeof(*bitmap_git));
524 if (!open_midx_bitmap_1(bitmap_git, midx) && !load_bitmap(bitmap_git))
525 return bitmap_git;
527 free_bitmap_index(bitmap_git);
528 return NULL;
531 struct include_data {
532 struct bitmap_index *bitmap_git;
533 struct bitmap *base;
534 struct bitmap *seen;
537 struct ewah_bitmap *bitmap_for_commit(struct bitmap_index *bitmap_git,
538 struct commit *commit)
540 khiter_t hash_pos = kh_get_oid_map(bitmap_git->bitmaps,
541 commit->object.oid);
542 if (hash_pos >= kh_end(bitmap_git->bitmaps))
543 return NULL;
544 return lookup_stored_bitmap(kh_value(bitmap_git->bitmaps, hash_pos));
547 static inline int bitmap_position_extended(struct bitmap_index *bitmap_git,
548 const struct object_id *oid)
550 kh_oid_pos_t *positions = bitmap_git->ext_index.positions;
551 khiter_t pos = kh_get_oid_pos(positions, *oid);
553 if (pos < kh_end(positions)) {
554 int bitmap_pos = kh_value(positions, pos);
555 return bitmap_pos + bitmap_num_objects(bitmap_git);
558 return -1;
561 static inline int bitmap_position_packfile(struct bitmap_index *bitmap_git,
562 const struct object_id *oid)
564 uint32_t pos;
565 off_t offset = find_pack_entry_one(oid->hash, bitmap_git->pack);
566 if (!offset)
567 return -1;
569 if (offset_to_pack_pos(bitmap_git->pack, offset, &pos) < 0)
570 return -1;
571 return pos;
574 static int bitmap_position_midx(struct bitmap_index *bitmap_git,
575 const struct object_id *oid)
577 uint32_t want, got;
578 if (!bsearch_midx(oid, bitmap_git->midx, &want))
579 return -1;
581 if (midx_to_pack_pos(bitmap_git->midx, want, &got) < 0)
582 return -1;
583 return got;
586 static int bitmap_position(struct bitmap_index *bitmap_git,
587 const struct object_id *oid)
589 int pos;
590 if (bitmap_is_midx(bitmap_git))
591 pos = bitmap_position_midx(bitmap_git, oid);
592 else
593 pos = bitmap_position_packfile(bitmap_git, oid);
594 return (pos >= 0) ? pos : bitmap_position_extended(bitmap_git, oid);
597 static int ext_index_add_object(struct bitmap_index *bitmap_git,
598 struct object *object, const char *name)
600 struct eindex *eindex = &bitmap_git->ext_index;
602 khiter_t hash_pos;
603 int hash_ret;
604 int bitmap_pos;
606 hash_pos = kh_put_oid_pos(eindex->positions, object->oid, &hash_ret);
607 if (hash_ret > 0) {
608 if (eindex->count >= eindex->alloc) {
609 eindex->alloc = (eindex->alloc + 16) * 3 / 2;
610 REALLOC_ARRAY(eindex->objects, eindex->alloc);
611 REALLOC_ARRAY(eindex->hashes, eindex->alloc);
614 bitmap_pos = eindex->count;
615 eindex->objects[eindex->count] = object;
616 eindex->hashes[eindex->count] = pack_name_hash(name);
617 kh_value(eindex->positions, hash_pos) = bitmap_pos;
618 eindex->count++;
619 } else {
620 bitmap_pos = kh_value(eindex->positions, hash_pos);
623 return bitmap_pos + bitmap_num_objects(bitmap_git);
626 struct bitmap_show_data {
627 struct bitmap_index *bitmap_git;
628 struct bitmap *base;
631 static void show_object(struct object *object, const char *name, void *data_)
633 struct bitmap_show_data *data = data_;
634 int bitmap_pos;
636 bitmap_pos = bitmap_position(data->bitmap_git, &object->oid);
638 if (bitmap_pos < 0)
639 bitmap_pos = ext_index_add_object(data->bitmap_git, object,
640 name);
642 bitmap_set(data->base, bitmap_pos);
645 static void show_commit(struct commit *commit, void *data)
649 static int add_to_include_set(struct bitmap_index *bitmap_git,
650 struct include_data *data,
651 struct commit *commit,
652 int bitmap_pos)
654 struct ewah_bitmap *partial;
656 if (data->seen && bitmap_get(data->seen, bitmap_pos))
657 return 0;
659 if (bitmap_get(data->base, bitmap_pos))
660 return 0;
662 partial = bitmap_for_commit(bitmap_git, commit);
663 if (partial) {
664 bitmap_or_ewah(data->base, partial);
665 return 0;
668 bitmap_set(data->base, bitmap_pos);
669 return 1;
672 static int should_include(struct commit *commit, void *_data)
674 struct include_data *data = _data;
675 int bitmap_pos;
677 bitmap_pos = bitmap_position(data->bitmap_git, &commit->object.oid);
678 if (bitmap_pos < 0)
679 bitmap_pos = ext_index_add_object(data->bitmap_git,
680 (struct object *)commit,
681 NULL);
683 if (!add_to_include_set(data->bitmap_git, data, commit, bitmap_pos)) {
684 struct commit_list *parent = commit->parents;
686 while (parent) {
687 parent->item->object.flags |= SEEN;
688 parent = parent->next;
691 return 0;
694 return 1;
697 static int should_include_obj(struct object *obj, void *_data)
699 struct include_data *data = _data;
700 int bitmap_pos;
702 bitmap_pos = bitmap_position(data->bitmap_git, &obj->oid);
703 if (bitmap_pos < 0)
704 return 1;
705 if ((data->seen && bitmap_get(data->seen, bitmap_pos)) ||
706 bitmap_get(data->base, bitmap_pos)) {
707 obj->flags |= SEEN;
708 return 0;
710 return 1;
713 static int add_commit_to_bitmap(struct bitmap_index *bitmap_git,
714 struct bitmap **base,
715 struct commit *commit)
717 struct ewah_bitmap *or_with = bitmap_for_commit(bitmap_git, commit);
719 if (!or_with)
720 return 0;
722 if (*base == NULL)
723 *base = ewah_to_bitmap(or_with);
724 else
725 bitmap_or_ewah(*base, or_with);
727 return 1;
730 static struct bitmap *find_objects(struct bitmap_index *bitmap_git,
731 struct rev_info *revs,
732 struct object_list *roots,
733 struct bitmap *seen,
734 struct list_objects_filter_options *filter)
736 struct bitmap *base = NULL;
737 int needs_walk = 0;
739 struct object_list *not_mapped = NULL;
742 * Go through all the roots for the walk. The ones that have bitmaps
743 * on the bitmap index will be `or`ed together to form an initial
744 * global reachability analysis.
746 * The ones without bitmaps in the index will be stored in the
747 * `not_mapped_list` for further processing.
749 while (roots) {
750 struct object *object = roots->item;
751 roots = roots->next;
753 if (object->type == OBJ_COMMIT &&
754 add_commit_to_bitmap(bitmap_git, &base, (struct commit *)object)) {
755 object->flags |= SEEN;
756 continue;
759 object_list_insert(object, &not_mapped);
763 * Best case scenario: We found bitmaps for all the roots,
764 * so the resulting `or` bitmap has the full reachability analysis
766 if (not_mapped == NULL)
767 return base;
769 roots = not_mapped;
772 * Let's iterate through all the roots that don't have bitmaps to
773 * check if we can determine them to be reachable from the existing
774 * global bitmap.
776 * If we cannot find them in the existing global bitmap, we'll need
777 * to push them to an actual walk and run it until we can confirm
778 * they are reachable
780 while (roots) {
781 struct object *object = roots->item;
782 int pos;
784 roots = roots->next;
785 pos = bitmap_position(bitmap_git, &object->oid);
787 if (pos < 0 || base == NULL || !bitmap_get(base, pos)) {
788 object->flags &= ~UNINTERESTING;
789 add_pending_object(revs, object, "");
790 needs_walk = 1;
791 } else {
792 object->flags |= SEEN;
796 if (needs_walk) {
797 struct include_data incdata;
798 struct bitmap_show_data show_data;
800 if (base == NULL)
801 base = bitmap_new();
803 incdata.bitmap_git = bitmap_git;
804 incdata.base = base;
805 incdata.seen = seen;
807 revs->include_check = should_include;
808 revs->include_check_obj = should_include_obj;
809 revs->include_check_data = &incdata;
811 if (prepare_revision_walk(revs))
812 die("revision walk setup failed");
814 show_data.bitmap_git = bitmap_git;
815 show_data.base = base;
817 traverse_commit_list_filtered(filter, revs,
818 show_commit, show_object,
819 &show_data, NULL);
821 revs->include_check = NULL;
822 revs->include_check_obj = NULL;
823 revs->include_check_data = NULL;
826 return base;
829 static void show_extended_objects(struct bitmap_index *bitmap_git,
830 struct rev_info *revs,
831 show_reachable_fn show_reach)
833 struct bitmap *objects = bitmap_git->result;
834 struct eindex *eindex = &bitmap_git->ext_index;
835 uint32_t i;
837 for (i = 0; i < eindex->count; ++i) {
838 struct object *obj;
840 if (!bitmap_get(objects, bitmap_num_objects(bitmap_git) + i))
841 continue;
843 obj = eindex->objects[i];
844 if ((obj->type == OBJ_BLOB && !revs->blob_objects) ||
845 (obj->type == OBJ_TREE && !revs->tree_objects) ||
846 (obj->type == OBJ_TAG && !revs->tag_objects))
847 continue;
849 show_reach(&obj->oid, obj->type, 0, eindex->hashes[i], NULL, 0);
853 static void init_type_iterator(struct ewah_iterator *it,
854 struct bitmap_index *bitmap_git,
855 enum object_type type)
857 switch (type) {
858 case OBJ_COMMIT:
859 ewah_iterator_init(it, bitmap_git->commits);
860 break;
862 case OBJ_TREE:
863 ewah_iterator_init(it, bitmap_git->trees);
864 break;
866 case OBJ_BLOB:
867 ewah_iterator_init(it, bitmap_git->blobs);
868 break;
870 case OBJ_TAG:
871 ewah_iterator_init(it, bitmap_git->tags);
872 break;
874 default:
875 BUG("object type %d not stored by bitmap type index", type);
876 break;
880 static void show_objects_for_type(
881 struct bitmap_index *bitmap_git,
882 enum object_type object_type,
883 show_reachable_fn show_reach)
885 size_t i = 0;
886 uint32_t offset;
888 struct ewah_iterator it;
889 eword_t filter;
891 struct bitmap *objects = bitmap_git->result;
893 init_type_iterator(&it, bitmap_git, object_type);
895 for (i = 0; i < objects->word_alloc &&
896 ewah_iterator_next(&filter, &it); i++) {
897 eword_t word = objects->words[i] & filter;
898 size_t pos = (i * BITS_IN_EWORD);
900 if (!word)
901 continue;
903 for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
904 struct packed_git *pack;
905 struct object_id oid;
906 uint32_t hash = 0, index_pos;
907 off_t ofs;
909 if ((word >> offset) == 0)
910 break;
912 offset += ewah_bit_ctz64(word >> offset);
914 if (bitmap_is_midx(bitmap_git)) {
915 struct multi_pack_index *m = bitmap_git->midx;
916 uint32_t pack_id;
918 index_pos = pack_pos_to_midx(m, pos + offset);
919 ofs = nth_midxed_offset(m, index_pos);
920 nth_midxed_object_oid(&oid, m, index_pos);
922 pack_id = nth_midxed_pack_int_id(m, index_pos);
923 pack = bitmap_git->midx->packs[pack_id];
924 } else {
925 index_pos = pack_pos_to_index(bitmap_git->pack, pos + offset);
926 ofs = pack_pos_to_offset(bitmap_git->pack, pos + offset);
927 nth_bitmap_object_oid(bitmap_git, &oid, index_pos);
929 pack = bitmap_git->pack;
932 if (bitmap_git->hashes)
933 hash = get_be32(bitmap_git->hashes + index_pos);
935 show_reach(&oid, object_type, 0, hash, pack, ofs);
940 static int in_bitmapped_pack(struct bitmap_index *bitmap_git,
941 struct object_list *roots)
943 while (roots) {
944 struct object *object = roots->item;
945 roots = roots->next;
947 if (bitmap_is_midx(bitmap_git)) {
948 if (bsearch_midx(&object->oid, bitmap_git->midx, NULL))
949 return 1;
950 } else {
951 if (find_pack_entry_one(object->oid.hash, bitmap_git->pack) > 0)
952 return 1;
956 return 0;
959 static struct bitmap *find_tip_objects(struct bitmap_index *bitmap_git,
960 struct object_list *tip_objects,
961 enum object_type type)
963 struct bitmap *result = bitmap_new();
964 struct object_list *p;
966 for (p = tip_objects; p; p = p->next) {
967 int pos;
969 if (p->item->type != type)
970 continue;
972 pos = bitmap_position(bitmap_git, &p->item->oid);
973 if (pos < 0)
974 continue;
976 bitmap_set(result, pos);
979 return result;
982 static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git,
983 struct object_list *tip_objects,
984 struct bitmap *to_filter,
985 enum object_type type)
987 struct eindex *eindex = &bitmap_git->ext_index;
988 struct bitmap *tips;
989 struct ewah_iterator it;
990 eword_t mask;
991 uint32_t i;
994 * The non-bitmap version of this filter never removes
995 * objects which the other side specifically asked for,
996 * so we must match that behavior.
998 tips = find_tip_objects(bitmap_git, tip_objects, type);
1001 * We can use the type-level bitmap for 'type' to work in whole
1002 * words for the objects that are actually in the bitmapped
1003 * packfile.
1005 for (i = 0, init_type_iterator(&it, bitmap_git, type);
1006 i < to_filter->word_alloc && ewah_iterator_next(&mask, &it);
1007 i++) {
1008 if (i < tips->word_alloc)
1009 mask &= ~tips->words[i];
1010 to_filter->words[i] &= ~mask;
1014 * Clear any objects that weren't in the packfile (and so would
1015 * not have been caught by the loop above. We'll have to check
1016 * them individually.
1018 for (i = 0; i < eindex->count; i++) {
1019 uint32_t pos = i + bitmap_num_objects(bitmap_git);
1020 if (eindex->objects[i]->type == type &&
1021 bitmap_get(to_filter, pos) &&
1022 !bitmap_get(tips, pos))
1023 bitmap_unset(to_filter, pos);
1026 bitmap_free(tips);
1029 static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git,
1030 struct object_list *tip_objects,
1031 struct bitmap *to_filter)
1033 filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter,
1034 OBJ_BLOB);
1037 static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git,
1038 uint32_t pos)
1040 unsigned long size;
1041 struct object_info oi = OBJECT_INFO_INIT;
1043 oi.sizep = &size;
1045 if (pos < bitmap_num_objects(bitmap_git)) {
1046 struct packed_git *pack;
1047 off_t ofs;
1049 if (bitmap_is_midx(bitmap_git)) {
1050 uint32_t midx_pos = pack_pos_to_midx(bitmap_git->midx, pos);
1051 uint32_t pack_id = nth_midxed_pack_int_id(bitmap_git->midx, midx_pos);
1053 pack = bitmap_git->midx->packs[pack_id];
1054 ofs = nth_midxed_offset(bitmap_git->midx, midx_pos);
1055 } else {
1056 pack = bitmap_git->pack;
1057 ofs = pack_pos_to_offset(pack, pos);
1060 if (packed_object_info(the_repository, pack, ofs, &oi) < 0) {
1061 struct object_id oid;
1062 nth_bitmap_object_oid(bitmap_git, &oid,
1063 pack_pos_to_index(pack, pos));
1064 die(_("unable to get size of %s"), oid_to_hex(&oid));
1066 } else {
1067 struct eindex *eindex = &bitmap_git->ext_index;
1068 struct object *obj = eindex->objects[pos - bitmap_num_objects(bitmap_git)];
1069 if (oid_object_info_extended(the_repository, &obj->oid, &oi, 0) < 0)
1070 die(_("unable to get size of %s"), oid_to_hex(&obj->oid));
1073 return size;
1076 static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git,
1077 struct object_list *tip_objects,
1078 struct bitmap *to_filter,
1079 unsigned long limit)
1081 struct eindex *eindex = &bitmap_git->ext_index;
1082 struct bitmap *tips;
1083 struct ewah_iterator it;
1084 eword_t mask;
1085 uint32_t i;
1087 tips = find_tip_objects(bitmap_git, tip_objects, OBJ_BLOB);
1089 for (i = 0, init_type_iterator(&it, bitmap_git, OBJ_BLOB);
1090 i < to_filter->word_alloc && ewah_iterator_next(&mask, &it);
1091 i++) {
1092 eword_t word = to_filter->words[i] & mask;
1093 unsigned offset;
1095 for (offset = 0; offset < BITS_IN_EWORD; offset++) {
1096 uint32_t pos;
1098 if ((word >> offset) == 0)
1099 break;
1100 offset += ewah_bit_ctz64(word >> offset);
1101 pos = i * BITS_IN_EWORD + offset;
1103 if (!bitmap_get(tips, pos) &&
1104 get_size_by_pos(bitmap_git, pos) >= limit)
1105 bitmap_unset(to_filter, pos);
1109 for (i = 0; i < eindex->count; i++) {
1110 uint32_t pos = i + bitmap_num_objects(bitmap_git);
1111 if (eindex->objects[i]->type == OBJ_BLOB &&
1112 bitmap_get(to_filter, pos) &&
1113 !bitmap_get(tips, pos) &&
1114 get_size_by_pos(bitmap_git, pos) >= limit)
1115 bitmap_unset(to_filter, pos);
1118 bitmap_free(tips);
1121 static void filter_bitmap_tree_depth(struct bitmap_index *bitmap_git,
1122 struct object_list *tip_objects,
1123 struct bitmap *to_filter,
1124 unsigned long limit)
1126 if (limit)
1127 BUG("filter_bitmap_tree_depth given non-zero limit");
1129 filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter,
1130 OBJ_TREE);
1131 filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter,
1132 OBJ_BLOB);
1135 static void filter_bitmap_object_type(struct bitmap_index *bitmap_git,
1136 struct object_list *tip_objects,
1137 struct bitmap *to_filter,
1138 enum object_type object_type)
1140 if (object_type < OBJ_COMMIT || object_type > OBJ_TAG)
1141 BUG("filter_bitmap_object_type given invalid object");
1143 if (object_type != OBJ_TAG)
1144 filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter, OBJ_TAG);
1145 if (object_type != OBJ_COMMIT)
1146 filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter, OBJ_COMMIT);
1147 if (object_type != OBJ_TREE)
1148 filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter, OBJ_TREE);
1149 if (object_type != OBJ_BLOB)
1150 filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter, OBJ_BLOB);
1153 static int filter_bitmap(struct bitmap_index *bitmap_git,
1154 struct object_list *tip_objects,
1155 struct bitmap *to_filter,
1156 struct list_objects_filter_options *filter)
1158 if (!filter || filter->choice == LOFC_DISABLED)
1159 return 0;
1161 if (filter->choice == LOFC_BLOB_NONE) {
1162 if (bitmap_git)
1163 filter_bitmap_blob_none(bitmap_git, tip_objects,
1164 to_filter);
1165 return 0;
1168 if (filter->choice == LOFC_BLOB_LIMIT) {
1169 if (bitmap_git)
1170 filter_bitmap_blob_limit(bitmap_git, tip_objects,
1171 to_filter,
1172 filter->blob_limit_value);
1173 return 0;
1176 if (filter->choice == LOFC_TREE_DEPTH &&
1177 filter->tree_exclude_depth == 0) {
1178 if (bitmap_git)
1179 filter_bitmap_tree_depth(bitmap_git, tip_objects,
1180 to_filter,
1181 filter->tree_exclude_depth);
1182 return 0;
1185 if (filter->choice == LOFC_OBJECT_TYPE) {
1186 if (bitmap_git)
1187 filter_bitmap_object_type(bitmap_git, tip_objects,
1188 to_filter,
1189 filter->object_type);
1190 return 0;
1193 if (filter->choice == LOFC_COMBINE) {
1194 int i;
1195 for (i = 0; i < filter->sub_nr; i++) {
1196 if (filter_bitmap(bitmap_git, tip_objects, to_filter,
1197 &filter->sub[i]) < 0)
1198 return -1;
1200 return 0;
1203 /* filter choice not handled */
1204 return -1;
1207 static int can_filter_bitmap(struct list_objects_filter_options *filter)
1209 return !filter_bitmap(NULL, NULL, NULL, filter);
1212 struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,
1213 struct list_objects_filter_options *filter,
1214 int filter_provided_objects)
1216 unsigned int i;
1218 struct object_list *wants = NULL;
1219 struct object_list *haves = NULL;
1221 struct bitmap *wants_bitmap = NULL;
1222 struct bitmap *haves_bitmap = NULL;
1224 struct bitmap_index *bitmap_git;
1227 * We can't do pathspec limiting with bitmaps, because we don't know
1228 * which commits are associated with which object changes (let alone
1229 * even which objects are associated with which paths).
1231 if (revs->prune)
1232 return NULL;
1234 if (!can_filter_bitmap(filter))
1235 return NULL;
1237 /* try to open a bitmapped pack, but don't parse it yet
1238 * because we may not need to use it */
1239 CALLOC_ARRAY(bitmap_git, 1);
1240 if (open_bitmap(revs->repo, bitmap_git) < 0)
1241 goto cleanup;
1243 for (i = 0; i < revs->pending.nr; ++i) {
1244 struct object *object = revs->pending.objects[i].item;
1246 if (object->type == OBJ_NONE)
1247 parse_object_or_die(&object->oid, NULL);
1249 while (object->type == OBJ_TAG) {
1250 struct tag *tag = (struct tag *) object;
1252 if (object->flags & UNINTERESTING)
1253 object_list_insert(object, &haves);
1254 else
1255 object_list_insert(object, &wants);
1257 object = parse_object_or_die(get_tagged_oid(tag), NULL);
1258 object->flags |= (tag->object.flags & UNINTERESTING);
1261 if (object->flags & UNINTERESTING)
1262 object_list_insert(object, &haves);
1263 else
1264 object_list_insert(object, &wants);
1268 * if we have a HAVES list, but none of those haves is contained
1269 * in the packfile that has a bitmap, we don't have anything to
1270 * optimize here
1272 if (haves && !in_bitmapped_pack(bitmap_git, haves))
1273 goto cleanup;
1275 /* if we don't want anything, we're done here */
1276 if (!wants)
1277 goto cleanup;
1280 * now we're going to use bitmaps, so load the actual bitmap entries
1281 * from disk. this is the point of no return; after this the rev_list
1282 * becomes invalidated and we must perform the revwalk through bitmaps
1284 if (load_bitmap(bitmap_git) < 0)
1285 goto cleanup;
1287 object_array_clear(&revs->pending);
1289 if (haves) {
1290 revs->ignore_missing_links = 1;
1291 haves_bitmap = find_objects(bitmap_git, revs, haves, NULL,
1292 filter);
1293 reset_revision_walk();
1294 revs->ignore_missing_links = 0;
1296 if (haves_bitmap == NULL)
1297 BUG("failed to perform bitmap walk");
1300 wants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap,
1301 filter);
1303 if (!wants_bitmap)
1304 BUG("failed to perform bitmap walk");
1306 if (haves_bitmap)
1307 bitmap_and_not(wants_bitmap, haves_bitmap);
1309 filter_bitmap(bitmap_git, (filter && filter_provided_objects) ? NULL : wants,
1310 wants_bitmap, filter);
1312 bitmap_git->result = wants_bitmap;
1313 bitmap_git->haves = haves_bitmap;
1315 object_list_free(&wants);
1316 object_list_free(&haves);
1318 return bitmap_git;
1320 cleanup:
1321 free_bitmap_index(bitmap_git);
1322 object_list_free(&wants);
1323 object_list_free(&haves);
1324 return NULL;
1328 * -1 means "stop trying further objects"; 0 means we may or may not have
1329 * reused, but you can keep feeding bits.
1331 static int try_partial_reuse(struct packed_git *pack,
1332 size_t pos,
1333 struct bitmap *reuse,
1334 struct pack_window **w_curs)
1336 off_t offset, delta_obj_offset;
1337 enum object_type type;
1338 unsigned long size;
1341 * try_partial_reuse() is called either on (a) objects in the
1342 * bitmapped pack (in the case of a single-pack bitmap) or (b)
1343 * objects in the preferred pack of a multi-pack bitmap.
1344 * Importantly, the latter can pretend as if only a single pack
1345 * exists because:
1347 * - The first pack->num_objects bits of a MIDX bitmap are
1348 * reserved for the preferred pack, and
1350 * - Ties due to duplicate objects are always resolved in
1351 * favor of the preferred pack.
1353 * Therefore we do not need to ever ask the MIDX for its copy of
1354 * an object by OID, since it will always select it from the
1355 * preferred pack. Likewise, the selected copy of the base
1356 * object for any deltas will reside in the same pack.
1358 * This means that we can reuse pos when looking up the bit in
1359 * the reuse bitmap, too, since bits corresponding to the
1360 * preferred pack precede all bits from other packs.
1363 if (pos >= pack->num_objects)
1364 return -1; /* not actually in the pack or MIDX preferred pack */
1366 offset = delta_obj_offset = pack_pos_to_offset(pack, pos);
1367 type = unpack_object_header(pack, w_curs, &offset, &size);
1368 if (type < 0)
1369 return -1; /* broken packfile, punt */
1371 if (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA) {
1372 off_t base_offset;
1373 uint32_t base_pos;
1376 * Find the position of the base object so we can look it up
1377 * in our bitmaps. If we can't come up with an offset, or if
1378 * that offset is not in the revidx, the pack is corrupt.
1379 * There's nothing we can do, so just punt on this object,
1380 * and the normal slow path will complain about it in
1381 * more detail.
1383 base_offset = get_delta_base(pack, w_curs, &offset, type,
1384 delta_obj_offset);
1385 if (!base_offset)
1386 return 0;
1387 if (offset_to_pack_pos(pack, base_offset, &base_pos) < 0)
1388 return 0;
1391 * We assume delta dependencies always point backwards. This
1392 * lets us do a single pass, and is basically always true
1393 * due to the way OFS_DELTAs work. You would not typically
1394 * find REF_DELTA in a bitmapped pack, since we only bitmap
1395 * packs we write fresh, and OFS_DELTA is the default). But
1396 * let's double check to make sure the pack wasn't written with
1397 * odd parameters.
1399 if (base_pos >= pos)
1400 return 0;
1403 * And finally, if we're not sending the base as part of our
1404 * reuse chunk, then don't send this object either. The base
1405 * would come after us, along with other objects not
1406 * necessarily in the pack, which means we'd need to convert
1407 * to REF_DELTA on the fly. Better to just let the normal
1408 * object_entry code path handle it.
1410 if (!bitmap_get(reuse, base_pos))
1411 return 0;
1415 * If we got here, then the object is OK to reuse. Mark it.
1417 bitmap_set(reuse, pos);
1418 return 0;
1421 uint32_t midx_preferred_pack(struct bitmap_index *bitmap_git)
1423 struct multi_pack_index *m = bitmap_git->midx;
1424 if (!m)
1425 BUG("midx_preferred_pack: requires non-empty MIDX");
1426 return nth_midxed_pack_int_id(m, pack_pos_to_midx(bitmap_git->midx, 0));
1429 int reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,
1430 struct packed_git **packfile_out,
1431 uint32_t *entries,
1432 struct bitmap **reuse_out)
1434 struct packed_git *pack;
1435 struct bitmap *result = bitmap_git->result;
1436 struct bitmap *reuse;
1437 struct pack_window *w_curs = NULL;
1438 size_t i = 0;
1439 uint32_t offset;
1440 uint32_t objects_nr;
1442 assert(result);
1444 load_reverse_index(bitmap_git);
1446 if (bitmap_is_midx(bitmap_git))
1447 pack = bitmap_git->midx->packs[midx_preferred_pack(bitmap_git)];
1448 else
1449 pack = bitmap_git->pack;
1450 objects_nr = pack->num_objects;
1452 while (i < result->word_alloc && result->words[i] == (eword_t)~0)
1453 i++;
1456 * Don't mark objects not in the packfile or preferred pack. This bitmap
1457 * marks objects eligible for reuse, but the pack-reuse code only
1458 * understands how to reuse a single pack. Since the preferred pack is
1459 * guaranteed to have all bases for its deltas (in a multi-pack bitmap),
1460 * we use it instead of another pack. In single-pack bitmaps, the choice
1461 * is made for us.
1463 if (i > objects_nr / BITS_IN_EWORD)
1464 i = objects_nr / BITS_IN_EWORD;
1466 reuse = bitmap_word_alloc(i);
1467 memset(reuse->words, 0xFF, i * sizeof(eword_t));
1469 for (; i < result->word_alloc; ++i) {
1470 eword_t word = result->words[i];
1471 size_t pos = (i * BITS_IN_EWORD);
1473 for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
1474 if ((word >> offset) == 0)
1475 break;
1477 offset += ewah_bit_ctz64(word >> offset);
1478 if (try_partial_reuse(pack, pos + offset,
1479 reuse, &w_curs) < 0) {
1481 * try_partial_reuse indicated we couldn't reuse
1482 * any bits, so there is no point in trying more
1483 * bits in the current word, or any other words
1484 * in result.
1486 * Jump out of both loops to avoid future
1487 * unnecessary calls to try_partial_reuse.
1489 goto done;
1494 done:
1495 unuse_pack(&w_curs);
1497 *entries = bitmap_popcount(reuse);
1498 if (!*entries) {
1499 bitmap_free(reuse);
1500 return -1;
1504 * Drop any reused objects from the result, since they will not
1505 * need to be handled separately.
1507 bitmap_and_not(result, reuse);
1508 *packfile_out = pack;
1509 *reuse_out = reuse;
1510 return 0;
1513 int bitmap_walk_contains(struct bitmap_index *bitmap_git,
1514 struct bitmap *bitmap, const struct object_id *oid)
1516 int idx;
1518 if (!bitmap)
1519 return 0;
1521 idx = bitmap_position(bitmap_git, oid);
1522 return idx >= 0 && bitmap_get(bitmap, idx);
1525 void traverse_bitmap_commit_list(struct bitmap_index *bitmap_git,
1526 struct rev_info *revs,
1527 show_reachable_fn show_reachable)
1529 assert(bitmap_git->result);
1531 show_objects_for_type(bitmap_git, OBJ_COMMIT, show_reachable);
1532 if (revs->tree_objects)
1533 show_objects_for_type(bitmap_git, OBJ_TREE, show_reachable);
1534 if (revs->blob_objects)
1535 show_objects_for_type(bitmap_git, OBJ_BLOB, show_reachable);
1536 if (revs->tag_objects)
1537 show_objects_for_type(bitmap_git, OBJ_TAG, show_reachable);
1539 show_extended_objects(bitmap_git, revs, show_reachable);
1542 static uint32_t count_object_type(struct bitmap_index *bitmap_git,
1543 enum object_type type)
1545 struct bitmap *objects = bitmap_git->result;
1546 struct eindex *eindex = &bitmap_git->ext_index;
1548 uint32_t i = 0, count = 0;
1549 struct ewah_iterator it;
1550 eword_t filter;
1552 init_type_iterator(&it, bitmap_git, type);
1554 while (i < objects->word_alloc && ewah_iterator_next(&filter, &it)) {
1555 eword_t word = objects->words[i++] & filter;
1556 count += ewah_bit_popcount64(word);
1559 for (i = 0; i < eindex->count; ++i) {
1560 if (eindex->objects[i]->type == type &&
1561 bitmap_get(objects, bitmap_num_objects(bitmap_git) + i))
1562 count++;
1565 return count;
1568 void count_bitmap_commit_list(struct bitmap_index *bitmap_git,
1569 uint32_t *commits, uint32_t *trees,
1570 uint32_t *blobs, uint32_t *tags)
1572 assert(bitmap_git->result);
1574 if (commits)
1575 *commits = count_object_type(bitmap_git, OBJ_COMMIT);
1577 if (trees)
1578 *trees = count_object_type(bitmap_git, OBJ_TREE);
1580 if (blobs)
1581 *blobs = count_object_type(bitmap_git, OBJ_BLOB);
1583 if (tags)
1584 *tags = count_object_type(bitmap_git, OBJ_TAG);
1587 struct bitmap_test_data {
1588 struct bitmap_index *bitmap_git;
1589 struct bitmap *base;
1590 struct bitmap *commits;
1591 struct bitmap *trees;
1592 struct bitmap *blobs;
1593 struct bitmap *tags;
1594 struct progress *prg;
1595 size_t seen;
1598 static void test_bitmap_type(struct bitmap_test_data *tdata,
1599 struct object *obj, int pos)
1601 enum object_type bitmap_type = OBJ_NONE;
1602 int bitmaps_nr = 0;
1604 if (bitmap_get(tdata->commits, pos)) {
1605 bitmap_type = OBJ_COMMIT;
1606 bitmaps_nr++;
1608 if (bitmap_get(tdata->trees, pos)) {
1609 bitmap_type = OBJ_TREE;
1610 bitmaps_nr++;
1612 if (bitmap_get(tdata->blobs, pos)) {
1613 bitmap_type = OBJ_BLOB;
1614 bitmaps_nr++;
1616 if (bitmap_get(tdata->tags, pos)) {
1617 bitmap_type = OBJ_TAG;
1618 bitmaps_nr++;
1621 if (bitmap_type == OBJ_NONE)
1622 die("object %s not found in type bitmaps",
1623 oid_to_hex(&obj->oid));
1625 if (bitmaps_nr > 1)
1626 die("object %s does not have a unique type",
1627 oid_to_hex(&obj->oid));
1629 if (bitmap_type != obj->type)
1630 die("object %s: real type %s, expected: %s",
1631 oid_to_hex(&obj->oid),
1632 type_name(obj->type),
1633 type_name(bitmap_type));
1636 static void test_show_object(struct object *object, const char *name,
1637 void *data)
1639 struct bitmap_test_data *tdata = data;
1640 int bitmap_pos;
1642 bitmap_pos = bitmap_position(tdata->bitmap_git, &object->oid);
1643 if (bitmap_pos < 0)
1644 die("Object not in bitmap: %s\n", oid_to_hex(&object->oid));
1645 test_bitmap_type(tdata, object, bitmap_pos);
1647 bitmap_set(tdata->base, bitmap_pos);
1648 display_progress(tdata->prg, ++tdata->seen);
1651 static void test_show_commit(struct commit *commit, void *data)
1653 struct bitmap_test_data *tdata = data;
1654 int bitmap_pos;
1656 bitmap_pos = bitmap_position(tdata->bitmap_git,
1657 &commit->object.oid);
1658 if (bitmap_pos < 0)
1659 die("Object not in bitmap: %s\n", oid_to_hex(&commit->object.oid));
1660 test_bitmap_type(tdata, &commit->object, bitmap_pos);
1662 bitmap_set(tdata->base, bitmap_pos);
1663 display_progress(tdata->prg, ++tdata->seen);
1666 void test_bitmap_walk(struct rev_info *revs)
1668 struct object *root;
1669 struct bitmap *result = NULL;
1670 size_t result_popcnt;
1671 struct bitmap_test_data tdata;
1672 struct bitmap_index *bitmap_git;
1673 struct ewah_bitmap *bm;
1675 if (!(bitmap_git = prepare_bitmap_git(revs->repo)))
1676 die("failed to load bitmap indexes");
1678 if (revs->pending.nr != 1)
1679 die("you must specify exactly one commit to test");
1681 fprintf(stderr, "Bitmap v%d test (%d entries loaded)\n",
1682 bitmap_git->version, bitmap_git->entry_count);
1684 root = revs->pending.objects[0].item;
1685 bm = bitmap_for_commit(bitmap_git, (struct commit *)root);
1687 if (bm) {
1688 fprintf(stderr, "Found bitmap for %s. %d bits / %08x checksum\n",
1689 oid_to_hex(&root->oid), (int)bm->bit_size, ewah_checksum(bm));
1691 result = ewah_to_bitmap(bm);
1694 if (result == NULL)
1695 die("Commit %s doesn't have an indexed bitmap", oid_to_hex(&root->oid));
1697 revs->tag_objects = 1;
1698 revs->tree_objects = 1;
1699 revs->blob_objects = 1;
1701 result_popcnt = bitmap_popcount(result);
1703 if (prepare_revision_walk(revs))
1704 die("revision walk setup failed");
1706 tdata.bitmap_git = bitmap_git;
1707 tdata.base = bitmap_new();
1708 tdata.commits = ewah_to_bitmap(bitmap_git->commits);
1709 tdata.trees = ewah_to_bitmap(bitmap_git->trees);
1710 tdata.blobs = ewah_to_bitmap(bitmap_git->blobs);
1711 tdata.tags = ewah_to_bitmap(bitmap_git->tags);
1712 tdata.prg = start_progress("Verifying bitmap entries", result_popcnt);
1713 tdata.seen = 0;
1715 traverse_commit_list(revs, &test_show_commit, &test_show_object, &tdata);
1717 stop_progress(&tdata.prg);
1719 if (bitmap_equals(result, tdata.base))
1720 fprintf(stderr, "OK!\n");
1721 else
1722 die("mismatch in bitmap results");
1724 free_bitmap_index(bitmap_git);
1727 int test_bitmap_commits(struct repository *r)
1729 struct bitmap_index *bitmap_git = prepare_bitmap_git(r);
1730 struct object_id oid;
1731 MAYBE_UNUSED void *value;
1733 if (!bitmap_git)
1734 die("failed to load bitmap indexes");
1736 kh_foreach(bitmap_git->bitmaps, oid, value, {
1737 printf("%s\n", oid_to_hex(&oid));
1740 free_bitmap_index(bitmap_git);
1742 return 0;
1745 int test_bitmap_hashes(struct repository *r)
1747 struct bitmap_index *bitmap_git = prepare_bitmap_git(r);
1748 struct object_id oid;
1749 uint32_t i, index_pos;
1751 if (!bitmap_git->hashes)
1752 goto cleanup;
1754 for (i = 0; i < bitmap_num_objects(bitmap_git); i++) {
1755 if (bitmap_is_midx(bitmap_git))
1756 index_pos = pack_pos_to_midx(bitmap_git->midx, i);
1757 else
1758 index_pos = pack_pos_to_index(bitmap_git->pack, i);
1760 nth_bitmap_object_oid(bitmap_git, &oid, index_pos);
1762 printf("%s %"PRIu32"\n",
1763 oid_to_hex(&oid), get_be32(bitmap_git->hashes + index_pos));
1766 cleanup:
1767 free_bitmap_index(bitmap_git);
1769 return 0;
1772 int rebuild_bitmap(const uint32_t *reposition,
1773 struct ewah_bitmap *source,
1774 struct bitmap *dest)
1776 uint32_t pos = 0;
1777 struct ewah_iterator it;
1778 eword_t word;
1780 ewah_iterator_init(&it, source);
1782 while (ewah_iterator_next(&word, &it)) {
1783 uint32_t offset, bit_pos;
1785 for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
1786 if ((word >> offset) == 0)
1787 break;
1789 offset += ewah_bit_ctz64(word >> offset);
1791 bit_pos = reposition[pos + offset];
1792 if (bit_pos > 0)
1793 bitmap_set(dest, bit_pos - 1);
1794 else /* can't reuse, we don't have the object */
1795 return -1;
1798 pos += BITS_IN_EWORD;
1800 return 0;
1803 uint32_t *create_bitmap_mapping(struct bitmap_index *bitmap_git,
1804 struct packing_data *mapping)
1806 uint32_t i, num_objects;
1807 uint32_t *reposition;
1809 if (!bitmap_is_midx(bitmap_git))
1810 load_reverse_index(bitmap_git);
1811 else if (load_midx_revindex(bitmap_git->midx) < 0)
1812 BUG("rebuild_existing_bitmaps: missing required rev-cache "
1813 "extension");
1815 num_objects = bitmap_num_objects(bitmap_git);
1816 CALLOC_ARRAY(reposition, num_objects);
1818 for (i = 0; i < num_objects; ++i) {
1819 struct object_id oid;
1820 struct object_entry *oe;
1821 uint32_t index_pos;
1823 if (bitmap_is_midx(bitmap_git))
1824 index_pos = pack_pos_to_midx(bitmap_git->midx, i);
1825 else
1826 index_pos = pack_pos_to_index(bitmap_git->pack, i);
1827 nth_bitmap_object_oid(bitmap_git, &oid, index_pos);
1828 oe = packlist_find(mapping, &oid);
1830 if (oe) {
1831 reposition[i] = oe_in_pack_pos(mapping, oe) + 1;
1832 if (bitmap_git->hashes && !oe->hash)
1833 oe->hash = get_be32(bitmap_git->hashes + index_pos);
1837 return reposition;
1840 void free_bitmap_index(struct bitmap_index *b)
1842 if (!b)
1843 return;
1845 if (b->map)
1846 munmap(b->map, b->map_size);
1847 ewah_pool_free(b->commits);
1848 ewah_pool_free(b->trees);
1849 ewah_pool_free(b->blobs);
1850 ewah_pool_free(b->tags);
1851 kh_destroy_oid_map(b->bitmaps);
1852 free(b->ext_index.objects);
1853 free(b->ext_index.hashes);
1854 bitmap_free(b->result);
1855 bitmap_free(b->haves);
1856 if (bitmap_is_midx(b)) {
1858 * Multi-pack bitmaps need to have resources associated with
1859 * their on-disk reverse indexes unmapped so that stale .rev and
1860 * .bitmap files can be removed.
1862 * Unlike pack-based bitmaps, multi-pack bitmaps can be read and
1863 * written in the same 'git multi-pack-index write --bitmap'
1864 * process. Close resources so they can be removed safely on
1865 * platforms like Windows.
1867 close_midx_revindex(b->midx);
1869 free(b);
1872 int bitmap_has_oid_in_uninteresting(struct bitmap_index *bitmap_git,
1873 const struct object_id *oid)
1875 return bitmap_git &&
1876 bitmap_walk_contains(bitmap_git, bitmap_git->haves, oid);
1879 static off_t get_disk_usage_for_type(struct bitmap_index *bitmap_git,
1880 enum object_type object_type)
1882 struct bitmap *result = bitmap_git->result;
1883 off_t total = 0;
1884 struct ewah_iterator it;
1885 eword_t filter;
1886 size_t i;
1888 init_type_iterator(&it, bitmap_git, object_type);
1889 for (i = 0; i < result->word_alloc &&
1890 ewah_iterator_next(&filter, &it); i++) {
1891 eword_t word = result->words[i] & filter;
1892 size_t base = (i * BITS_IN_EWORD);
1893 unsigned offset;
1895 if (!word)
1896 continue;
1898 for (offset = 0; offset < BITS_IN_EWORD; offset++) {
1899 if ((word >> offset) == 0)
1900 break;
1902 offset += ewah_bit_ctz64(word >> offset);
1904 if (bitmap_is_midx(bitmap_git)) {
1905 uint32_t pack_pos;
1906 uint32_t midx_pos = pack_pos_to_midx(bitmap_git->midx, base + offset);
1907 off_t offset = nth_midxed_offset(bitmap_git->midx, midx_pos);
1909 uint32_t pack_id = nth_midxed_pack_int_id(bitmap_git->midx, midx_pos);
1910 struct packed_git *pack = bitmap_git->midx->packs[pack_id];
1912 if (offset_to_pack_pos(pack, offset, &pack_pos) < 0) {
1913 struct object_id oid;
1914 nth_midxed_object_oid(&oid, bitmap_git->midx, midx_pos);
1916 die(_("could not find %s in pack %s at offset %"PRIuMAX),
1917 oid_to_hex(&oid),
1918 pack->pack_name,
1919 (uintmax_t)offset);
1922 total += pack_pos_to_offset(pack, pack_pos + 1) - offset;
1923 } else {
1924 size_t pos = base + offset;
1925 total += pack_pos_to_offset(bitmap_git->pack, pos + 1) -
1926 pack_pos_to_offset(bitmap_git->pack, pos);
1931 return total;
1934 static off_t get_disk_usage_for_extended(struct bitmap_index *bitmap_git)
1936 struct bitmap *result = bitmap_git->result;
1937 struct eindex *eindex = &bitmap_git->ext_index;
1938 off_t total = 0;
1939 struct object_info oi = OBJECT_INFO_INIT;
1940 off_t object_size;
1941 size_t i;
1943 oi.disk_sizep = &object_size;
1945 for (i = 0; i < eindex->count; i++) {
1946 struct object *obj = eindex->objects[i];
1948 if (!bitmap_get(result, bitmap_num_objects(bitmap_git) + i))
1949 continue;
1951 if (oid_object_info_extended(the_repository, &obj->oid, &oi, 0) < 0)
1952 die(_("unable to get disk usage of %s"),
1953 oid_to_hex(&obj->oid));
1955 total += object_size;
1957 return total;
1960 off_t get_disk_usage_from_bitmap(struct bitmap_index *bitmap_git,
1961 struct rev_info *revs)
1963 off_t total = 0;
1965 total += get_disk_usage_for_type(bitmap_git, OBJ_COMMIT);
1966 if (revs->tree_objects)
1967 total += get_disk_usage_for_type(bitmap_git, OBJ_TREE);
1968 if (revs->blob_objects)
1969 total += get_disk_usage_for_type(bitmap_git, OBJ_BLOB);
1970 if (revs->tag_objects)
1971 total += get_disk_usage_for_type(bitmap_git, OBJ_TAG);
1973 total += get_disk_usage_for_extended(bitmap_git);
1975 return total;
1978 int bitmap_is_midx(struct bitmap_index *bitmap_git)
1980 return !!bitmap_git->midx;
1983 const struct string_list *bitmap_preferred_tips(struct repository *r)
1985 return repo_config_get_value_multi(r, "pack.preferbitmaptips");
1988 int bitmap_is_preferred_refname(struct repository *r, const char *refname)
1990 const struct string_list *preferred_tips = bitmap_preferred_tips(r);
1991 struct string_list_item *item;
1993 if (!preferred_tips)
1994 return 0;
1996 for_each_string_list_item(item, preferred_tips) {
1997 if (starts_with(refname, item->string))
1998 return 1;
2001 return 0;