git

1
#define USE_THE_REPOSITORY_VARIABLE
2

3
#include "git-compat-util.h"
4
#include "commit.h"
5
#include "gettext.h"
6
#include "hex.h"
7
#include "strbuf.h"
8
#include "tag.h"
9
#include "diff.h"
10
#include "revision.h"
11
#include "progress.h"
12
#include "list-objects.h"
13
#include "pack.h"
14
#include "pack-bitmap.h"
15
#include "pack-revindex.h"
16
#include "pack-objects.h"
17
#include "packfile.h"
18
#include "repository.h"
19
#include "trace2.h"
20
#include "object-file.h"
21
#include "object-store-ll.h"
22
#include "list-objects-filter-options.h"
23
#include "midx.h"
24
#include "config.h"
25
#include "pseudo-merge.h"
26

27
/*
28
 * An entry on the bitmap index, representing the bitmap for a given
29
 * commit.
30
 */
31
struct stored_bitmap {
32
	struct object_id oid;
33
	struct ewah_bitmap *root;
34
	struct stored_bitmap *xor;
35
	int flags;
36
};
37

38
/*
39
 * The active bitmap index for a repository. By design, repositories only have
40
 * a single bitmap index available (the index for the biggest packfile in
41
 * the repository), since bitmap indexes need full closure.
42
 *
43
 * If there is more than one bitmap index available (e.g. because of alternates),
44
 * the active bitmap index is the largest one.
45
 */
46
struct bitmap_index {
47
	/*
48
	 * The pack or multi-pack index (MIDX) that this bitmap index belongs
49
	 * to.
50
	 *
51
	 * Exactly one of these must be non-NULL; this specifies the object
52
	 * order used to interpret this bitmap.
53
	 */
54
	struct packed_git *pack;
55
	struct multi_pack_index *midx;
56

57
	/* mmapped buffer of the whole bitmap index */
58
	unsigned char *map;
59
	size_t map_size; /* size of the mmaped buffer */
60
	size_t map_pos; /* current position when loading the index */
61

62
	/*
63
	 * Type indexes.
64
	 *
65
	 * Each bitmap marks which objects in the packfile  are of the given
66
	 * type. This provides type information when yielding the objects from
67
	 * the packfile during a walk, which allows for better delta bases.
68
	 */
69
	struct ewah_bitmap *commits;
70
	struct ewah_bitmap *trees;
71
	struct ewah_bitmap *blobs;
72
	struct ewah_bitmap *tags;
73

74
	/* Map from object ID -> `stored_bitmap` for all the bitmapped commits */
75
	kh_oid_map_t *bitmaps;
76

77
	/* Number of bitmapped commits */
78
	uint32_t entry_count;
79

80
	/* If not NULL, this is a name-hash cache pointing into map. */
81
	uint32_t *hashes;
82

83
	/* The checksum of the packfile or MIDX; points into map. */
84
	const unsigned char *checksum;
85

86
	/*
87
	 * If not NULL, this point into the commit table extension
88
	 * (within the memory mapped region `map`).
89
	 */
90
	unsigned char *table_lookup;
91

92
	/* This contains the pseudo-merge cache within 'map' (if found). */
93
	struct pseudo_merge_map pseudo_merges;
94

95
	/*
96
	 * Extended index.
97
	 *
98
	 * When trying to perform bitmap operations with objects that are not
99
	 * packed in `pack`, these objects are added to this "fake index" and
100
	 * are assumed to appear at the end of the packfile for all operations
101
	 */
102
	struct eindex {
103
		struct object **objects;
104
		uint32_t *hashes;
105
		uint32_t count, alloc;
106
		kh_oid_pos_t *positions;
107
	} ext_index;
108

109
	/* Bitmap result of the last performed walk */
110
	struct bitmap *result;
111

112
	/* "have" bitmap from the last performed walk */
113
	struct bitmap *haves;
114

115
	/* Version of the bitmap index */
116
	unsigned int version;
117
};
118

119
static int pseudo_merges_satisfied_nr;
120
static int pseudo_merges_cascades_nr;
121
static int existing_bitmaps_hits_nr;
122
static int existing_bitmaps_misses_nr;
123
static int roots_with_bitmaps_nr;
124
static int roots_without_bitmaps_nr;
125

126
static struct ewah_bitmap *lookup_stored_bitmap(struct stored_bitmap *st)
127
{
128
	struct ewah_bitmap *parent;
129
	struct ewah_bitmap *composed;
130

131
	if (!st->xor)
132
		return st->root;
133

134
	composed = ewah_pool_new();
135
	parent = lookup_stored_bitmap(st->xor);
136
	ewah_xor(st->root, parent, composed);
137

138
	ewah_pool_free(st->root);
139
	st->root = composed;
140
	st->xor = NULL;
141

142
	return composed;
143
}
144

145
struct ewah_bitmap *read_bitmap(const unsigned char *map,
146
				size_t map_size, size_t *map_pos)
147
{
148
	struct ewah_bitmap *b = ewah_pool_new();
149

150
	ssize_t bitmap_size = ewah_read_mmap(b, map + *map_pos,
151
					     map_size - *map_pos);
152

153
	if (bitmap_size < 0) {
154
		error(_("failed to load bitmap index (corrupted?)"));
155
		ewah_pool_free(b);
156
		return NULL;
157
	}
158

159
	*map_pos += bitmap_size;
160

161
	return b;
162
}
163

164
/*
165
 * Read a bitmap from the current read position on the mmaped
166
 * index, and increase the read position accordingly
167
 */
168
static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *index)
169
{
170
	return read_bitmap(index->map, index->map_size, &index->map_pos);
171
}
172

173
static uint32_t bitmap_num_objects(struct bitmap_index *index)
174
{
175
	if (index->midx)
176
		return index->midx->num_objects;
177
	return index->pack->num_objects;
178
}
179

180
static int load_bitmap_header(struct bitmap_index *index)
181
{
182
	struct bitmap_disk_header *header = (void *)index->map;
183
	size_t header_size = sizeof(*header) - GIT_MAX_RAWSZ + the_hash_algo->rawsz;
184

185
	if (index->map_size < header_size + the_hash_algo->rawsz)
186
		return error(_("corrupted bitmap index (too small)"));
187

188
	if (memcmp(header->magic, BITMAP_IDX_SIGNATURE, sizeof(BITMAP_IDX_SIGNATURE)) != 0)
189
		return error(_("corrupted bitmap index file (wrong header)"));
190

191
	index->version = ntohs(header->version);
192
	if (index->version != 1)
193
		return error(_("unsupported version '%d' for bitmap index file"), index->version);
194

195
	/* Parse known bitmap format options */
196
	{
197
		uint32_t flags = ntohs(header->options);
198
		size_t cache_size = st_mult(bitmap_num_objects(index), sizeof(uint32_t));
199
		unsigned char *index_end = index->map + index->map_size - the_hash_algo->rawsz;
200

201
		if ((flags & BITMAP_OPT_FULL_DAG) == 0)
202
			BUG("unsupported options for bitmap index file "
203
				"(Git requires BITMAP_OPT_FULL_DAG)");
204

205
		if (flags & BITMAP_OPT_HASH_CACHE) {
206
			if (cache_size > index_end - index->map - header_size)
207
				return error(_("corrupted bitmap index file (too short to fit hash cache)"));
208
			index->hashes = (void *)(index_end - cache_size);
209
			index_end -= cache_size;
210
		}
211

212
		if (flags & BITMAP_OPT_LOOKUP_TABLE) {
213
			size_t table_size = st_mult(ntohl(header->entry_count),
214
						    BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH);
215
			if (table_size > index_end - index->map - header_size)
216
				return error(_("corrupted bitmap index file (too short to fit lookup table)"));
217
			if (git_env_bool("GIT_TEST_READ_COMMIT_TABLE", 1))
218
				index->table_lookup = (void *)(index_end - table_size);
219
			index_end -= table_size;
220
		}
221

222
		if (flags & BITMAP_OPT_PSEUDO_MERGES) {
223
			unsigned char *pseudo_merge_ofs;
224
			size_t table_size;
225
			uint32_t i;
226

227
			if (sizeof(table_size) > index_end - index->map - header_size)
228
				return error(_("corrupted bitmap index file (too short to fit pseudo-merge table header)"));
229

230
			table_size = get_be64(index_end - 8);
231
			if (table_size > index_end - index->map - header_size)
232
				return error(_("corrupted bitmap index file (too short to fit pseudo-merge table)"));
233

234
			if (git_env_bool("GIT_TEST_USE_PSEUDO_MERGES", 1)) {
235
				const unsigned char *ext = (index_end - table_size);
236

237
				index->pseudo_merges.map = index->map;
238
				index->pseudo_merges.map_size = index->map_size;
239
				index->pseudo_merges.commits = ext + get_be64(index_end - 16);
240
				index->pseudo_merges.commits_nr = get_be32(index_end - 20);
241
				index->pseudo_merges.nr = get_be32(index_end - 24);
242

243
				if (st_add(st_mult(index->pseudo_merges.nr,
244
						   sizeof(uint64_t)),
245
					   24) > table_size)
246
					return error(_("corrupted bitmap index file, pseudo-merge table too short"));
247

248
				CALLOC_ARRAY(index->pseudo_merges.v,
249
					     index->pseudo_merges.nr);
250

251
				pseudo_merge_ofs = index_end - 24 -
252
					(index->pseudo_merges.nr * sizeof(uint64_t));
253
				for (i = 0; i < index->pseudo_merges.nr; i++) {
254
					index->pseudo_merges.v[i].at = get_be64(pseudo_merge_ofs);
255
					pseudo_merge_ofs += sizeof(uint64_t);
256
				}
257
			}
258

259
			index_end -= table_size;
260
		}
261
	}
262

263
	index->entry_count = ntohl(header->entry_count);
264
	index->checksum = header->checksum;
265
	index->map_pos += header_size;
266
	return 0;
267
}
268

269
static struct stored_bitmap *store_bitmap(struct bitmap_index *index,
270
					  struct ewah_bitmap *root,
271
					  const struct object_id *oid,
272
					  struct stored_bitmap *xor_with,
273
					  int flags)
274
{
275
	struct stored_bitmap *stored;
276
	khiter_t hash_pos;
277
	int ret;
278

279
	stored = xmalloc(sizeof(struct stored_bitmap));
280
	stored->root = root;
281
	stored->xor = xor_with;
282
	stored->flags = flags;
283
	oidcpy(&stored->oid, oid);
284

285
	hash_pos = kh_put_oid_map(index->bitmaps, stored->oid, &ret);
286

287
	/*
288
	 * A 0 return code means the insertion succeeded with no changes,
289
	 * because the SHA1 already existed on the map. This is bad, there
290
	 * shouldn't be duplicated commits in the index.
291
	 */
292
	if (ret == 0) {
293
		error(_("duplicate entry in bitmap index: '%s'"), oid_to_hex(oid));
294
		return NULL;
295
	}
296

297
	kh_value(index->bitmaps, hash_pos) = stored;
298
	return stored;
299
}
300

301
static inline uint32_t read_be32(const unsigned char *buffer, size_t *pos)
302
{
303
	uint32_t result = get_be32(buffer + *pos);
304
	(*pos) += sizeof(result);
305
	return result;
306
}
307

308
static inline uint8_t read_u8(const unsigned char *buffer, size_t *pos)
309
{
310
	return buffer[(*pos)++];
311
}
312

313
#define MAX_XOR_OFFSET 160
314

315
static int nth_bitmap_object_oid(struct bitmap_index *index,
316
				 struct object_id *oid,
317
				 uint32_t n)
318
{
319
	if (index->midx)
320
		return nth_midxed_object_oid(oid, index->midx, n) ? 0 : -1;
321
	return nth_packed_object_id(oid, index->pack, n);
322
}
323

324
static int load_bitmap_entries_v1(struct bitmap_index *index)
325
{
326
	uint32_t i;
327
	struct stored_bitmap *recent_bitmaps[MAX_XOR_OFFSET] = { NULL };
328

329
	for (i = 0; i < index->entry_count; ++i) {
330
		int xor_offset, flags;
331
		struct ewah_bitmap *bitmap = NULL;
332
		struct stored_bitmap *xor_bitmap = NULL;
333
		uint32_t commit_idx_pos;
334
		struct object_id oid;
335

336
		if (index->map_size - index->map_pos < 6)
337
			return error(_("corrupt ewah bitmap: truncated header for entry %d"), i);
338

339
		commit_idx_pos = read_be32(index->map, &index->map_pos);
340
		xor_offset = read_u8(index->map, &index->map_pos);
341
		flags = read_u8(index->map, &index->map_pos);
342

343
		if (nth_bitmap_object_oid(index, &oid, commit_idx_pos) < 0)
344
			return error(_("corrupt ewah bitmap: commit index %u out of range"),
345
				     (unsigned)commit_idx_pos);
346

347
		bitmap = read_bitmap_1(index);
348
		if (!bitmap)
349
			return -1;
350

351
		if (xor_offset > MAX_XOR_OFFSET || xor_offset > i)
352
			return error(_("corrupted bitmap pack index"));
353

354
		if (xor_offset > 0) {
355
			xor_bitmap = recent_bitmaps[(i - xor_offset) % MAX_XOR_OFFSET];
356

357
			if (!xor_bitmap)
358
				return error(_("invalid XOR offset in bitmap pack index"));
359
		}
360

361
		recent_bitmaps[i % MAX_XOR_OFFSET] = store_bitmap(
362
			index, bitmap, &oid, xor_bitmap, flags);
363
	}
364

365
	return 0;
366
}
367

368
char *midx_bitmap_filename(struct multi_pack_index *midx)
369
{
370
	struct strbuf buf = STRBUF_INIT;
371
	get_midx_filename_ext(&buf, midx->object_dir, get_midx_checksum(midx),
372
			      MIDX_EXT_BITMAP);
373

374
	return strbuf_detach(&buf, NULL);
375
}
376

377
char *pack_bitmap_filename(struct packed_git *p)
378
{
379
	size_t len;
380

381
	if (!strip_suffix(p->pack_name, ".pack", &len))
382
		BUG("pack_name does not end in .pack");
383
	return xstrfmt("%.*s.bitmap", (int)len, p->pack_name);
384
}
385

386
static int open_midx_bitmap_1(struct bitmap_index *bitmap_git,
387
			      struct multi_pack_index *midx)
388
{
389
	struct stat st;
390
	char *bitmap_name = midx_bitmap_filename(midx);
391
	int fd = git_open(bitmap_name);
392
	uint32_t i, preferred_pack;
393
	struct packed_git *preferred;
394

395
	if (fd < 0) {
396
		if (errno != ENOENT)
397
			warning_errno("cannot open '%s'", bitmap_name);
398
		free(bitmap_name);
399
		return -1;
400
	}
401
	free(bitmap_name);
402

403
	if (fstat(fd, &st)) {
404
		error_errno(_("cannot fstat bitmap file"));
405
		close(fd);
406
		return -1;
407
	}
408

409
	if (bitmap_git->pack || bitmap_git->midx) {
410
		struct strbuf buf = STRBUF_INIT;
411
		get_midx_filename(&buf, midx->object_dir);
412
		trace2_data_string("bitmap", the_repository,
413
				   "ignoring extra midx bitmap file", buf.buf);
414
		close(fd);
415
		strbuf_release(&buf);
416
		return -1;
417
	}
418

419
	bitmap_git->midx = midx;
420
	bitmap_git->map_size = xsize_t(st.st_size);
421
	bitmap_git->map_pos = 0;
422
	bitmap_git->map = xmmap(NULL, bitmap_git->map_size, PROT_READ,
423
				MAP_PRIVATE, fd, 0);
424
	close(fd);
425

426
	if (load_bitmap_header(bitmap_git) < 0)
427
		goto cleanup;
428

429
	if (!hasheq(get_midx_checksum(bitmap_git->midx), bitmap_git->checksum,
430
		    the_repository->hash_algo)) {
431
		error(_("checksum doesn't match in MIDX and bitmap"));
432
		goto cleanup;
433
	}
434

435
	if (load_midx_revindex(bitmap_git->midx)) {
436
		warning(_("multi-pack bitmap is missing required reverse index"));
437
		goto cleanup;
438
	}
439

440
	for (i = 0; i < bitmap_git->midx->num_packs; i++) {
441
		if (prepare_midx_pack(the_repository, bitmap_git->midx, i)) {
442
			warning(_("could not open pack %s"),
443
				bitmap_git->midx->pack_names[i]);
444
			goto cleanup;
445
		}
446
	}
447

448
	if (midx_preferred_pack(bitmap_git->midx, &preferred_pack) < 0) {
449
		warning(_("could not determine MIDX preferred pack"));
450
		goto cleanup;
451
	}
452

453
	preferred = bitmap_git->midx->packs[preferred_pack];
454
	if (!is_pack_valid(preferred)) {
455
		warning(_("preferred pack (%s) is invalid"),
456
			preferred->pack_name);
457
		goto cleanup;
458
	}
459

460
	return 0;
461

462
cleanup:
463
	munmap(bitmap_git->map, bitmap_git->map_size);
464
	bitmap_git->map_size = 0;
465
	bitmap_git->map_pos = 0;
466
	bitmap_git->map = NULL;
467
	bitmap_git->midx = NULL;
468
	return -1;
469
}
470

471
static int open_pack_bitmap_1(struct bitmap_index *bitmap_git, struct packed_git *packfile)
472
{
473
	int fd;
474
	struct stat st;
475
	char *bitmap_name;
476

477
	bitmap_name = pack_bitmap_filename(packfile);
478
	fd = git_open(bitmap_name);
479

480
	if (fd < 0) {
481
		if (errno != ENOENT)
482
			warning_errno("cannot open '%s'", bitmap_name);
483
		free(bitmap_name);
484
		return -1;
485
	}
486
	free(bitmap_name);
487

488
	if (fstat(fd, &st)) {
489
		error_errno(_("cannot fstat bitmap file"));
490
		close(fd);
491
		return -1;
492
	}
493

494
	if (bitmap_git->pack || bitmap_git->midx) {
495
		trace2_data_string("bitmap", the_repository,
496
				   "ignoring extra bitmap file", packfile->pack_name);
497
		close(fd);
498
		return -1;
499
	}
500

501
	if (!is_pack_valid(packfile)) {
502
		close(fd);
503
		return -1;
504
	}
505

506
	bitmap_git->pack = packfile;
507
	bitmap_git->map_size = xsize_t(st.st_size);
508
	bitmap_git->map = xmmap(NULL, bitmap_git->map_size, PROT_READ, MAP_PRIVATE, fd, 0);
509
	bitmap_git->map_pos = 0;
510
	close(fd);
511

512
	if (load_bitmap_header(bitmap_git) < 0) {
513
		munmap(bitmap_git->map, bitmap_git->map_size);
514
		bitmap_git->map = NULL;
515
		bitmap_git->map_size = 0;
516
		bitmap_git->map_pos = 0;
517
		bitmap_git->pack = NULL;
518
		return -1;
519
	}
520

521
	trace2_data_string("bitmap", the_repository, "opened bitmap file",
522
			   packfile->pack_name);
523
	return 0;
524
}
525

526
static int load_reverse_index(struct repository *r, struct bitmap_index *bitmap_git)
527
{
528
	if (bitmap_is_midx(bitmap_git)) {
529
		uint32_t i;
530
		int ret;
531

532
		/*
533
		 * The multi-pack-index's .rev file is already loaded via
534
		 * open_pack_bitmap_1().
535
		 *
536
		 * But we still need to open the individual pack .rev files,
537
		 * since we will need to make use of them in pack-objects.
538
		 */
539
		for (i = 0; i < bitmap_git->midx->num_packs; i++) {
540
			ret = load_pack_revindex(r, bitmap_git->midx->packs[i]);
541
			if (ret)
542
				return ret;
543
		}
544
		return 0;
545
	}
546
	return load_pack_revindex(r, bitmap_git->pack);
547
}
548

549
static int load_bitmap(struct repository *r, struct bitmap_index *bitmap_git)
550
{
551
	assert(bitmap_git->map);
552

553
	bitmap_git->bitmaps = kh_init_oid_map();
554
	bitmap_git->ext_index.positions = kh_init_oid_pos();
555

556
	if (load_reverse_index(r, bitmap_git))
557
		goto failed;
558

559
	if (!(bitmap_git->commits = read_bitmap_1(bitmap_git)) ||
560
		!(bitmap_git->trees = read_bitmap_1(bitmap_git)) ||
561
		!(bitmap_git->blobs = read_bitmap_1(bitmap_git)) ||
562
		!(bitmap_git->tags = read_bitmap_1(bitmap_git)))
563
		goto failed;
564

565
	if (!bitmap_git->table_lookup && load_bitmap_entries_v1(bitmap_git) < 0)
566
		goto failed;
567

568
	return 0;
569

570
failed:
571
	munmap(bitmap_git->map, bitmap_git->map_size);
572
	bitmap_git->map = NULL;
573
	bitmap_git->map_size = 0;
574

575
	kh_destroy_oid_map(bitmap_git->bitmaps);
576
	bitmap_git->bitmaps = NULL;
577

578
	kh_destroy_oid_pos(bitmap_git->ext_index.positions);
579
	bitmap_git->ext_index.positions = NULL;
580

581
	return -1;
582
}
583

584
static int open_pack_bitmap(struct repository *r,
585
			    struct bitmap_index *bitmap_git)
586
{
587
	struct packed_git *p;
588
	int ret = -1;
589

590
	for (p = get_all_packs(r); p; p = p->next) {
591
		if (open_pack_bitmap_1(bitmap_git, p) == 0) {
592
			ret = 0;
593
			/*
594
			 * The only reason to keep looking is to report
595
			 * duplicates.
596
			 */
597
			if (!trace2_is_enabled())
598
				break;
599
		}
600
	}
601

602
	return ret;
603
}
604

605
static int open_midx_bitmap(struct repository *r,
606
			    struct bitmap_index *bitmap_git)
607
{
608
	int ret = -1;
609
	struct multi_pack_index *midx;
610

611
	assert(!bitmap_git->map);
612

613
	for (midx = get_multi_pack_index(r); midx; midx = midx->next) {
614
		if (!open_midx_bitmap_1(bitmap_git, midx))
615
			ret = 0;
616
	}
617
	return ret;
618
}
619

620
static int open_bitmap(struct repository *r,
621
		       struct bitmap_index *bitmap_git)
622
{
623
	int found;
624

625
	assert(!bitmap_git->map);
626

627
	found = !open_midx_bitmap(r, bitmap_git);
628

629
	/*
630
	 * these will all be skipped if we opened a midx bitmap; but run it
631
	 * anyway if tracing is enabled to report the duplicates
632
	 */
633
	if (!found || trace2_is_enabled())
634
		found |= !open_pack_bitmap(r, bitmap_git);
635

636
	return found ? 0 : -1;
637
}
638

639
struct bitmap_index *prepare_bitmap_git(struct repository *r)
640
{
641
	struct bitmap_index *bitmap_git = xcalloc(1, sizeof(*bitmap_git));
642

643
	if (!open_bitmap(r, bitmap_git) && !load_bitmap(r, bitmap_git))
644
		return bitmap_git;
645

646
	free_bitmap_index(bitmap_git);
647
	return NULL;
648
}
649

650
struct bitmap_index *prepare_midx_bitmap_git(struct multi_pack_index *midx)
651
{
652
	struct repository *r = the_repository;
653
	struct bitmap_index *bitmap_git = xcalloc(1, sizeof(*bitmap_git));
654

655
	if (!open_midx_bitmap_1(bitmap_git, midx) && !load_bitmap(r, bitmap_git))
656
		return bitmap_git;
657

658
	free_bitmap_index(bitmap_git);
659
	return NULL;
660
}
661

662
struct include_data {
663
	struct bitmap_index *bitmap_git;
664
	struct bitmap *base;
665
	struct bitmap *seen;
666
};
667

668
struct bitmap_lookup_table_triplet {
669
	uint32_t commit_pos;
670
	uint64_t offset;
671
	uint32_t xor_row;
672
};
673

674
struct bitmap_lookup_table_xor_item {
675
	struct object_id oid;
676
	uint64_t offset;
677
};
678

679
/*
680
 * Given a `triplet` struct pointer and pointer `p`, this
681
 * function reads the triplet beginning at `p` into the struct.
682
 * Note that this function assumes that there is enough memory
683
 * left for filling the `triplet` struct from `p`.
684
 */
685
static int bitmap_lookup_table_get_triplet_by_pointer(struct bitmap_lookup_table_triplet *triplet,
686
						      const unsigned char *p)
687
{
688
	if (!triplet)
689
		return -1;
690

691
	triplet->commit_pos = get_be32(p);
692
	p += sizeof(uint32_t);
693
	triplet->offset = get_be64(p);
694
	p += sizeof(uint64_t);
695
	triplet->xor_row = get_be32(p);
696
	return 0;
697
}
698

699
/*
700
 * This function gets the raw triplet from `row`'th row in the
701
 * lookup table and fills that data to the `triplet`.
702
 */
703
static int bitmap_lookup_table_get_triplet(struct bitmap_index *bitmap_git,
704
					   uint32_t pos,
705
					   struct bitmap_lookup_table_triplet *triplet)
706
{
707
	unsigned char *p = NULL;
708
	if (pos >= bitmap_git->entry_count)
709
		return error(_("corrupt bitmap lookup table: triplet position out of index"));
710

711
	p = bitmap_git->table_lookup + st_mult(pos, BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH);
712

713
	return bitmap_lookup_table_get_triplet_by_pointer(triplet, p);
714
}
715

716
/*
717
 * Searches for a matching triplet. `commit_pos` is a pointer
718
 * to the wanted commit position value. `table_entry` points to
719
 * a triplet in lookup table. The first 4 bytes of each
720
 * triplet (pointed by `table_entry`) are compared with `*commit_pos`.
721
 */
722
static int triplet_cmp(const void *commit_pos, const void *table_entry)
723
{
724

725
	uint32_t a = *(uint32_t *)commit_pos;
726
	uint32_t b = get_be32(table_entry);
727
	if (a > b)
728
		return 1;
729
	else if (a < b)
730
		return -1;
731

732
	return 0;
733
}
734

735
static uint32_t bitmap_bsearch_pos(struct bitmap_index *bitmap_git,
736
			    struct object_id *oid,
737
			    uint32_t *result)
738
{
739
	int found;
740

741
	if (bitmap_is_midx(bitmap_git))
742
		found = bsearch_midx(oid, bitmap_git->midx, result);
743
	else
744
		found = bsearch_pack(oid, bitmap_git->pack, result);
745

746
	return found;
747
}
748

749
/*
750
 * `bsearch_triplet_by_pos` function searches for the raw triplet
751
 * having commit position same as `commit_pos` and fills `triplet`
752
 * object from the raw triplet. Returns 1 on success and 0 on
753
 * failure.
754
 */
755
static int bitmap_bsearch_triplet_by_pos(uint32_t commit_pos,
756
				  struct bitmap_index *bitmap_git,
757
				  struct bitmap_lookup_table_triplet *triplet)
758
{
759
	unsigned char *p = bsearch(&commit_pos, bitmap_git->table_lookup, bitmap_git->entry_count,
760
				   BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH, triplet_cmp);
761

762
	if (!p)
763
		return -1;
764

765
	return bitmap_lookup_table_get_triplet_by_pointer(triplet, p);
766
}
767

768
static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_git,
769
						    struct commit *commit)
770
{
771
	uint32_t commit_pos, xor_row;
772
	uint64_t offset;
773
	int flags;
774
	struct bitmap_lookup_table_triplet triplet;
775
	struct object_id *oid = &commit->object.oid;
776
	struct ewah_bitmap *bitmap;
777
	struct stored_bitmap *xor_bitmap = NULL;
778
	const int bitmap_header_size = 6;
779
	static struct bitmap_lookup_table_xor_item *xor_items = NULL;
780
	static size_t xor_items_nr = 0, xor_items_alloc = 0;
781
	static int is_corrupt = 0;
782
	int xor_flags;
783
	khiter_t hash_pos;
784
	struct bitmap_lookup_table_xor_item *xor_item;
785

786
	if (is_corrupt)
787
		return NULL;
788

789
	if (!bitmap_bsearch_pos(bitmap_git, oid, &commit_pos))
790
		return NULL;
791

792
	if (bitmap_bsearch_triplet_by_pos(commit_pos, bitmap_git, &triplet) < 0)
793
		return NULL;
794

795
	xor_items_nr = 0;
796
	offset = triplet.offset;
797
	xor_row = triplet.xor_row;
798

799
	while (xor_row != 0xffffffff) {
800
		ALLOC_GROW(xor_items, xor_items_nr + 1, xor_items_alloc);
801

802
		if (xor_items_nr + 1 >= bitmap_git->entry_count) {
803
			error(_("corrupt bitmap lookup table: xor chain exceeds entry count"));
804
			goto corrupt;
805
		}
806

807
		if (bitmap_lookup_table_get_triplet(bitmap_git, xor_row, &triplet) < 0)
808
			goto corrupt;
809

810
		xor_item = &xor_items[xor_items_nr];
811
		xor_item->offset = triplet.offset;
812

813
		if (nth_bitmap_object_oid(bitmap_git, &xor_item->oid, triplet.commit_pos) < 0) {
814
			error(_("corrupt bitmap lookup table: commit index %u out of range"),
815
				triplet.commit_pos);
816
			goto corrupt;
817
		}
818

819
		hash_pos = kh_get_oid_map(bitmap_git->bitmaps, xor_item->oid);
820

821
		/*
822
		 * If desired bitmap is already stored, we don't need
823
		 * to iterate further. Because we know that bitmaps
824
		 * that are needed to be parsed to parse this bitmap
825
		 * has already been stored. So, assign this stored bitmap
826
		 * to the xor_bitmap.
827
		 */
828
		if (hash_pos < kh_end(bitmap_git->bitmaps) &&
829
			(xor_bitmap = kh_value(bitmap_git->bitmaps, hash_pos)))
830
			break;
831
		xor_items_nr++;
832
		xor_row = triplet.xor_row;
833
	}
834

835
	while (xor_items_nr) {
836
		xor_item = &xor_items[xor_items_nr - 1];
837
		bitmap_git->map_pos = xor_item->offset;
838
		if (bitmap_git->map_size - bitmap_git->map_pos < bitmap_header_size) {
839
			error(_("corrupt ewah bitmap: truncated header for bitmap of commit \"%s\""),
840
				oid_to_hex(&xor_item->oid));
841
			goto corrupt;
842
		}
843

844
		bitmap_git->map_pos += sizeof(uint32_t) + sizeof(uint8_t);
845
		xor_flags = read_u8(bitmap_git->map, &bitmap_git->map_pos);
846
		bitmap = read_bitmap_1(bitmap_git);
847

848
		if (!bitmap)
849
			goto corrupt;
850

851
		xor_bitmap = store_bitmap(bitmap_git, bitmap, &xor_item->oid, xor_bitmap, xor_flags);
852
		xor_items_nr--;
853
	}
854

855
	bitmap_git->map_pos = offset;
856
	if (bitmap_git->map_size - bitmap_git->map_pos < bitmap_header_size) {
857
		error(_("corrupt ewah bitmap: truncated header for bitmap of commit \"%s\""),
858
			oid_to_hex(oid));
859
		goto corrupt;
860
	}
861

862
	/*
863
	 * Don't bother reading the commit's index position or its xor
864
	 * offset:
865
	 *
866
	 *   - The commit's index position is irrelevant to us, since
867
	 *     load_bitmap_entries_v1 only uses it to learn the object
868
	 *     id which is used to compute the hashmap's key. We already
869
	 *     have an object id, so no need to look it up again.
870
	 *
871
	 *   - The xor_offset is unusable for us, since it specifies how
872
	 *     many entries previous to ours we should look at. This
873
	 *     makes sense when reading the bitmaps sequentially (as in
874
	 *     load_bitmap_entries_v1()), since we can keep track of
875
	 *     each bitmap as we read them.
876
	 *
877
	 *     But it can't work for us, since the bitmap's don't have a
878
	 *     fixed size. So we learn the position of the xor'd bitmap
879
	 *     from the commit table (and resolve it to a bitmap in the
880
	 *     above if-statement).
881
	 *
882
	 * Instead, we can skip ahead and immediately read the flags and
883
	 * ewah bitmap.
884
	 */
885
	bitmap_git->map_pos += sizeof(uint32_t) + sizeof(uint8_t);
886
	flags = read_u8(bitmap_git->map, &bitmap_git->map_pos);
887
	bitmap = read_bitmap_1(bitmap_git);
888

889
	if (!bitmap)
890
		goto corrupt;
891

892
	return store_bitmap(bitmap_git, bitmap, oid, xor_bitmap, flags);
893

894
corrupt:
895
	free(xor_items);
896
	is_corrupt = 1;
897
	return NULL;
898
}
899

900
struct ewah_bitmap *bitmap_for_commit(struct bitmap_index *bitmap_git,
901
				      struct commit *commit)
902
{
903
	khiter_t hash_pos = kh_get_oid_map(bitmap_git->bitmaps,
904
					   commit->object.oid);
905
	if (hash_pos >= kh_end(bitmap_git->bitmaps)) {
906
		struct stored_bitmap *bitmap = NULL;
907
		if (!bitmap_git->table_lookup)
908
			return NULL;
909

910
		/* this is a fairly hot codepath - no trace2_region please */
911
		/* NEEDSWORK: cache misses aren't recorded */
912
		bitmap = lazy_bitmap_for_commit(bitmap_git, commit);
913
		if (!bitmap)
914
			return NULL;
915
		return lookup_stored_bitmap(bitmap);
916
	}
917
	return lookup_stored_bitmap(kh_value(bitmap_git->bitmaps, hash_pos));
918
}
919

920
static inline int bitmap_position_extended(struct bitmap_index *bitmap_git,
921
					   const struct object_id *oid)
922
{
923
	kh_oid_pos_t *positions = bitmap_git->ext_index.positions;
924
	khiter_t pos = kh_get_oid_pos(positions, *oid);
925

926
	if (pos < kh_end(positions)) {
927
		int bitmap_pos = kh_value(positions, pos);
928
		return bitmap_pos + bitmap_num_objects(bitmap_git);
929
	}
930

931
	return -1;
932
}
933

934
static inline int bitmap_position_packfile(struct bitmap_index *bitmap_git,
935
					   const struct object_id *oid)
936
{
937
	uint32_t pos;
938
	off_t offset = find_pack_entry_one(oid->hash, bitmap_git->pack);
939
	if (!offset)
940
		return -1;
941

942
	if (offset_to_pack_pos(bitmap_git->pack, offset, &pos) < 0)
943
		return -1;
944
	return pos;
945
}
946

947
static int bitmap_position_midx(struct bitmap_index *bitmap_git,
948
				const struct object_id *oid)
949
{
950
	uint32_t want, got;
951
	if (!bsearch_midx(oid, bitmap_git->midx, &want))
952
		return -1;
953

954
	if (midx_to_pack_pos(bitmap_git->midx, want, &got) < 0)
955
		return -1;
956
	return got;
957
}
958

959
static int bitmap_position(struct bitmap_index *bitmap_git,
960
			   const struct object_id *oid)
961
{
962
	int pos;
963
	if (bitmap_is_midx(bitmap_git))
964
		pos = bitmap_position_midx(bitmap_git, oid);
965
	else
966
		pos = bitmap_position_packfile(bitmap_git, oid);
967
	return (pos >= 0) ? pos : bitmap_position_extended(bitmap_git, oid);
968
}
969

970
static int ext_index_add_object(struct bitmap_index *bitmap_git,
971
				struct object *object, const char *name)
972
{
973
	struct eindex *eindex = &bitmap_git->ext_index;
974

975
	khiter_t hash_pos;
976
	int hash_ret;
977
	int bitmap_pos;
978

979
	hash_pos = kh_put_oid_pos(eindex->positions, object->oid, &hash_ret);
980
	if (hash_ret > 0) {
981
		if (eindex->count >= eindex->alloc) {
982
			eindex->alloc = (eindex->alloc + 16) * 3 / 2;
983
			REALLOC_ARRAY(eindex->objects, eindex->alloc);
984
			REALLOC_ARRAY(eindex->hashes, eindex->alloc);
985
		}
986

987
		bitmap_pos = eindex->count;
988
		eindex->objects[eindex->count] = object;
989
		eindex->hashes[eindex->count] = pack_name_hash(name);
990
		kh_value(eindex->positions, hash_pos) = bitmap_pos;
991
		eindex->count++;
992
	} else {
993
		bitmap_pos = kh_value(eindex->positions, hash_pos);
994
	}
995

996
	return bitmap_pos + bitmap_num_objects(bitmap_git);
997
}
998

999
struct bitmap_show_data {
1000
	struct bitmap_index *bitmap_git;
1001
	struct bitmap *base;
1002
};
1003

1004
static void show_object(struct object *object, const char *name, void *data_)
1005
{
1006
	struct bitmap_show_data *data = data_;
1007
	int bitmap_pos;
1008

1009
	bitmap_pos = bitmap_position(data->bitmap_git, &object->oid);
1010

1011
	if (bitmap_pos < 0)
1012
		bitmap_pos = ext_index_add_object(data->bitmap_git, object,
1013
						  name);
1014

1015
	bitmap_set(data->base, bitmap_pos);
1016
}
1017

1018
static void show_commit(struct commit *commit UNUSED,
1019
			void *data UNUSED)
1020
{
1021
}
1022

1023
static unsigned apply_pseudo_merges_for_commit_1(struct bitmap_index *bitmap_git,
1024
						 struct bitmap *result,
1025
						 struct commit *commit,
1026
						 uint32_t commit_pos)
1027
{
1028
	int ret;
1029

1030
	ret = apply_pseudo_merges_for_commit(&bitmap_git->pseudo_merges,
1031
					     result, commit, commit_pos);
1032

1033
	if (ret)
1034
		pseudo_merges_satisfied_nr += ret;
1035

1036
	return ret;
1037
}
1038

1039
static int add_to_include_set(struct bitmap_index *bitmap_git,
1040
			      struct include_data *data,
1041
			      struct commit *commit,
1042
			      int bitmap_pos)
1043
{
1044
	struct ewah_bitmap *partial;
1045

1046
	if (data->seen && bitmap_get(data->seen, bitmap_pos))
1047
		return 0;
1048

1049
	if (bitmap_get(data->base, bitmap_pos))
1050
		return 0;
1051

1052
	partial = bitmap_for_commit(bitmap_git, commit);
1053
	if (partial) {
1054
		existing_bitmaps_hits_nr++;
1055

1056
		bitmap_or_ewah(data->base, partial);
1057
		return 0;
1058
	}
1059

1060
	existing_bitmaps_misses_nr++;
1061

1062
	bitmap_set(data->base, bitmap_pos);
1063
	if (apply_pseudo_merges_for_commit_1(bitmap_git, data->base, commit,
1064
					     bitmap_pos))
1065
		return 0;
1066

1067
	return 1;
1068
}
1069

1070
static int should_include(struct commit *commit, void *_data)
1071
{
1072
	struct include_data *data = _data;
1073
	int bitmap_pos;
1074

1075
	bitmap_pos = bitmap_position(data->bitmap_git, &commit->object.oid);
1076
	if (bitmap_pos < 0)
1077
		bitmap_pos = ext_index_add_object(data->bitmap_git,
1078
						  (struct object *)commit,
1079
						  NULL);
1080

1081
	if (!add_to_include_set(data->bitmap_git, data, commit, bitmap_pos)) {
1082
		struct commit_list *parent = commit->parents;
1083

1084
		while (parent) {
1085
			parent->item->object.flags |= SEEN;
1086
			parent = parent->next;
1087
		}
1088

1089
		return 0;
1090
	}
1091

1092
	return 1;
1093
}
1094

1095
static int should_include_obj(struct object *obj, void *_data)
1096
{
1097
	struct include_data *data = _data;
1098
	int bitmap_pos;
1099

1100
	bitmap_pos = bitmap_position(data->bitmap_git, &obj->oid);
1101
	if (bitmap_pos < 0)
1102
		return 1;
1103
	if ((data->seen && bitmap_get(data->seen, bitmap_pos)) ||
1104
	     bitmap_get(data->base, bitmap_pos)) {
1105
		obj->flags |= SEEN;
1106
		return 0;
1107
	}
1108
	return 1;
1109
}
1110

1111
static int add_commit_to_bitmap(struct bitmap_index *bitmap_git,
1112
				struct bitmap **base,
1113
				struct commit *commit)
1114
{
1115
	struct ewah_bitmap *or_with = bitmap_for_commit(bitmap_git, commit);
1116

1117
	if (!or_with) {
1118
		existing_bitmaps_misses_nr++;
1119
		return 0;
1120
	}
1121

1122
	existing_bitmaps_hits_nr++;
1123

1124
	if (!*base)
1125
		*base = ewah_to_bitmap(or_with);
1126
	else
1127
		bitmap_or_ewah(*base, or_with);
1128

1129
	return 1;
1130
}
1131

1132
static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_git,
1133
				     struct rev_info *revs,
1134
				     struct bitmap *base,
1135
				     struct bitmap *seen)
1136
{
1137
	struct include_data incdata;
1138
	struct bitmap_show_data show_data;
1139

1140
	if (!base)
1141
		base = bitmap_new();
1142

1143
	incdata.bitmap_git = bitmap_git;
1144
	incdata.base = base;
1145
	incdata.seen = seen;
1146

1147
	revs->include_check = should_include;
1148
	revs->include_check_obj = should_include_obj;
1149
	revs->include_check_data = &incdata;
1150

1151
	if (prepare_revision_walk(revs))
1152
		die(_("revision walk setup failed"));
1153

1154
	show_data.bitmap_git = bitmap_git;
1155
	show_data.base = base;
1156

1157
	traverse_commit_list(revs, show_commit, show_object, &show_data);
1158

1159
	revs->include_check = NULL;
1160
	revs->include_check_obj = NULL;
1161
	revs->include_check_data = NULL;
1162

1163
	return base;
1164
}
1165

1166
struct bitmap_boundary_cb {
1167
	struct bitmap_index *bitmap_git;
1168
	struct bitmap *base;
1169

1170
	struct object_array boundary;
1171
};
1172

1173
static void show_boundary_commit(struct commit *commit, void *_data)
1174
{
1175
	struct bitmap_boundary_cb *data = _data;
1176

1177
	if (commit->object.flags & BOUNDARY)
1178
		add_object_array(&commit->object, "", &data->boundary);
1179

1180
	if (commit->object.flags & UNINTERESTING) {
1181
		if (bitmap_walk_contains(data->bitmap_git, data->base,
1182
					 &commit->object.oid))
1183
			return;
1184

1185
		add_commit_to_bitmap(data->bitmap_git, &data->base, commit);
1186
	}
1187
}
1188

1189
static void show_boundary_object(struct object *object UNUSED,
1190
				 const char *name UNUSED,
1191
				 void *data UNUSED)
1192
{
1193
	BUG("should not be called");
1194
}
1195

1196
static unsigned cascade_pseudo_merges_1(struct bitmap_index *bitmap_git,
1197
					struct bitmap *result,
1198
					struct bitmap *roots)
1199
{
1200
	int ret = cascade_pseudo_merges(&bitmap_git->pseudo_merges,
1201
					result, roots);
1202
	if (ret) {
1203
		pseudo_merges_cascades_nr++;
1204
		pseudo_merges_satisfied_nr += ret;
1205
	}
1206

1207
	return ret;
1208
}
1209

1210
static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,
1211
					    struct rev_info *revs,
1212
					    struct object_list *roots)
1213
{
1214
	struct bitmap_boundary_cb cb;
1215
	struct object_list *root;
1216
	unsigned int i;
1217
	unsigned int tmp_blobs, tmp_trees, tmp_tags;
1218
	int any_missing = 0;
1219
	int existing_bitmaps = 0;
1220

1221
	cb.bitmap_git = bitmap_git;
1222
	cb.base = bitmap_new();
1223
	object_array_init(&cb.boundary);
1224

1225
	revs->ignore_missing_links = 1;
1226

1227
	if (bitmap_git->pseudo_merges.nr) {
1228
		struct bitmap *roots_bitmap = bitmap_new();
1229
		struct object_list *objects = NULL;
1230

1231
		for (objects = roots; objects; objects = objects->next) {
1232
			struct object *object = objects->item;
1233
			int pos;
1234

1235
			pos = bitmap_position(bitmap_git, &object->oid);
1236
			if (pos < 0)
1237
				continue;
1238

1239
			bitmap_set(roots_bitmap, pos);
1240
		}
1241

1242
		if (!cascade_pseudo_merges_1(bitmap_git, cb.base, roots_bitmap))
1243
			bitmap_free(roots_bitmap);
1244
	}
1245

1246
	/*
1247
	 * OR in any existing reachability bitmaps among `roots` into
1248
	 * `cb.base`.
1249
	 */
1250
	for (root = roots; root; root = root->next) {
1251
		struct object *object = root->item;
1252
		if (object->type != OBJ_COMMIT ||
1253
		    bitmap_walk_contains(bitmap_git, cb.base, &object->oid))
1254
			continue;
1255

1256
		if (add_commit_to_bitmap(bitmap_git, &cb.base,
1257
					 (struct commit *)object)) {
1258
			existing_bitmaps = 1;
1259
			continue;
1260
		}
1261

1262
		any_missing = 1;
1263
	}
1264

1265
	if (!any_missing)
1266
		goto cleanup;
1267

1268
	if (existing_bitmaps)
1269
		cascade_pseudo_merges_1(bitmap_git, cb.base, NULL);
1270

1271
	tmp_blobs = revs->blob_objects;
1272
	tmp_trees = revs->tree_objects;
1273
	tmp_tags = revs->blob_objects;
1274
	revs->blob_objects = 0;
1275
	revs->tree_objects = 0;
1276
	revs->tag_objects = 0;
1277

1278
	/*
1279
	 * We didn't have complete coverage of the roots. First setup a
1280
	 * revision walk to (a) OR in any bitmaps that are UNINTERESTING
1281
	 * between the tips and boundary, and (b) record the boundary.
1282
	 */
1283
	trace2_region_enter("pack-bitmap", "boundary-prepare", the_repository);
1284
	if (prepare_revision_walk(revs))
1285
		die("revision walk setup failed");
1286
	trace2_region_leave("pack-bitmap", "boundary-prepare", the_repository);
1287

1288
	trace2_region_enter("pack-bitmap", "boundary-traverse", the_repository);
1289
	revs->boundary = 1;
1290
	traverse_commit_list_filtered(revs,
1291
				      show_boundary_commit,
1292
				      show_boundary_object,
1293
				      &cb, NULL);
1294
	revs->boundary = 0;
1295
	trace2_region_leave("pack-bitmap", "boundary-traverse", the_repository);
1296

1297
	revs->blob_objects = tmp_blobs;
1298
	revs->tree_objects = tmp_trees;
1299
	revs->tag_objects = tmp_tags;
1300

1301
	reset_revision_walk();
1302
	clear_object_flags(UNINTERESTING);
1303

1304
	/*
1305
	 * Then add the boundary commit(s) as fill-in traversal tips.
1306
	 */
1307
	trace2_region_enter("pack-bitmap", "boundary-fill-in", the_repository);
1308
	for (i = 0; i < cb.boundary.nr; i++) {
1309
		struct object *obj = cb.boundary.objects[i].item;
1310
		if (bitmap_walk_contains(bitmap_git, cb.base, &obj->oid))
1311
			obj->flags |= SEEN;
1312
		else
1313
			add_pending_object(revs, obj, "");
1314
	}
1315
	if (revs->pending.nr)
1316
		cb.base = fill_in_bitmap(bitmap_git, revs, cb.base, NULL);
1317
	trace2_region_leave("pack-bitmap", "boundary-fill-in", the_repository);
1318

1319
cleanup:
1320
	object_array_clear(&cb.boundary);
1321
	revs->ignore_missing_links = 0;
1322

1323
	return cb.base;
1324
}
1325

1326
struct ewah_bitmap *pseudo_merge_bitmap_for_commit(struct bitmap_index *bitmap_git,
1327
						   struct commit *commit)
1328
{
1329
	struct commit_list *p;
1330
	struct bitmap *parents;
1331
	struct pseudo_merge *match = NULL;
1332

1333
	if (!bitmap_git->pseudo_merges.nr)
1334
		return NULL;
1335

1336
	parents = bitmap_new();
1337

1338
	for (p = commit->parents; p; p = p->next) {
1339
		int pos = bitmap_position(bitmap_git, &p->item->object.oid);
1340
		if (pos < 0 || pos >= bitmap_num_objects(bitmap_git))
1341
			goto done;
1342

1343
		bitmap_set(parents, pos);
1344
	}
1345

1346
	match = pseudo_merge_for_parents(&bitmap_git->pseudo_merges,
1347
						parents);
1348

1349
done:
1350
	bitmap_free(parents);
1351
	if (match)
1352
		return pseudo_merge_bitmap(&bitmap_git->pseudo_merges, match);
1353

1354
	return NULL;
1355
}
1356

1357
static void unsatisfy_all_pseudo_merges(struct bitmap_index *bitmap_git)
1358
{
1359
	uint32_t i;
1360
	for (i = 0; i < bitmap_git->pseudo_merges.nr; i++)
1361
		bitmap_git->pseudo_merges.v[i].satisfied = 0;
1362
}
1363

1364
static struct bitmap *find_objects(struct bitmap_index *bitmap_git,
1365
				   struct rev_info *revs,
1366
				   struct object_list *roots,
1367
				   struct bitmap *seen)
1368
{
1369
	struct bitmap *base = NULL;
1370
	int needs_walk = 0;
1371
	unsigned existing_bitmaps = 0;
1372

1373
	struct object_list *not_mapped = NULL;
1374

1375
	unsatisfy_all_pseudo_merges(bitmap_git);
1376

1377
	if (bitmap_git->pseudo_merges.nr) {
1378
		struct bitmap *roots_bitmap = bitmap_new();
1379
		struct object_list *objects = NULL;
1380

1381
		for (objects = roots; objects; objects = objects->next) {
1382
			struct object *object = objects->item;
1383
			int pos;
1384

1385
			pos = bitmap_position(bitmap_git, &object->oid);
1386
			if (pos < 0)
1387
				continue;
1388

1389
			bitmap_set(roots_bitmap, pos);
1390
		}
1391

1392
		base = bitmap_new();
1393
		if (!cascade_pseudo_merges_1(bitmap_git, base, roots_bitmap))
1394
			bitmap_free(roots_bitmap);
1395
	}
1396

1397
	/*
1398
	 * Go through all the roots for the walk. The ones that have bitmaps
1399
	 * on the bitmap index will be `or`ed together to form an initial
1400
	 * global reachability analysis.
1401
	 *
1402
	 * The ones without bitmaps in the index will be stored in the
1403
	 * `not_mapped_list` for further processing.
1404
	 */
1405
	while (roots) {
1406
		struct object *object = roots->item;
1407

1408
		roots = roots->next;
1409

1410
		if (base) {
1411
			int pos = bitmap_position(bitmap_git, &object->oid);
1412
			if (pos > 0 && bitmap_get(base, pos)) {
1413
				object->flags |= SEEN;
1414
				continue;
1415
			}
1416
		}
1417

1418
		if (object->type == OBJ_COMMIT &&
1419
		    add_commit_to_bitmap(bitmap_git, &base, (struct commit *)object)) {
1420
			object->flags |= SEEN;
1421
			existing_bitmaps = 1;
1422
			continue;
1423
		}
1424

1425
		object_list_insert(object, &not_mapped);
1426
	}
1427

1428
	/*
1429
	 * Best case scenario: We found bitmaps for all the roots,
1430
	 * so the resulting `or` bitmap has the full reachability analysis
1431
	 */
1432
	if (!not_mapped)
1433
		return base;
1434

1435
	roots = not_mapped;
1436

1437
	if (existing_bitmaps)
1438
		cascade_pseudo_merges_1(bitmap_git, base, NULL);
1439

1440
	/*
1441
	 * Let's iterate through all the roots that don't have bitmaps to
1442
	 * check if we can determine them to be reachable from the existing
1443
	 * global bitmap.
1444
	 *
1445
	 * If we cannot find them in the existing global bitmap, we'll need
1446
	 * to push them to an actual walk and run it until we can confirm
1447
	 * they are reachable
1448
	 */
1449
	while (roots) {
1450
		struct object *object = roots->item;
1451
		int pos;
1452

1453
		roots = roots->next;
1454
		pos = bitmap_position(bitmap_git, &object->oid);
1455

1456
		if (pos < 0 || base == NULL || !bitmap_get(base, pos)) {
1457
			object->flags &= ~UNINTERESTING;
1458
			add_pending_object(revs, object, "");
1459
			needs_walk = 1;
1460

1461
			roots_without_bitmaps_nr++;
1462
		} else {
1463
			object->flags |= SEEN;
1464

1465
			roots_with_bitmaps_nr++;
1466
		}
1467
	}
1468

1469
	if (needs_walk) {
1470
		/*
1471
		 * This fill-in traversal may walk over some objects
1472
		 * again, since we have already traversed in order to
1473
		 * find the boundary.
1474
		 *
1475
		 * But this extra walk should be extremely cheap, since
1476
		 * all commit objects are loaded into memory, and
1477
		 * because we skip walking to parents that are
1478
		 * UNINTERESTING, since it will be marked in the haves
1479
		 * bitmap already (or it has an on-disk bitmap, since
1480
		 * OR-ing it in covers all of its ancestors).
1481
		 */
1482
		base = fill_in_bitmap(bitmap_git, revs, base, seen);
1483
	}
1484

1485
	object_list_free(&not_mapped);
1486

1487
	return base;
1488
}
1489

1490
static void show_extended_objects(struct bitmap_index *bitmap_git,
1491
				  struct rev_info *revs,
1492
				  show_reachable_fn show_reach)
1493
{
1494
	struct bitmap *objects = bitmap_git->result;
1495
	struct eindex *eindex = &bitmap_git->ext_index;
1496
	uint32_t i;
1497

1498
	for (i = 0; i < eindex->count; ++i) {
1499
		struct object *obj;
1500

1501
		if (!bitmap_get(objects, st_add(bitmap_num_objects(bitmap_git), i)))
1502
			continue;
1503

1504
		obj = eindex->objects[i];
1505
		if ((obj->type == OBJ_BLOB && !revs->blob_objects) ||
1506
		    (obj->type == OBJ_TREE && !revs->tree_objects) ||
1507
		    (obj->type == OBJ_TAG && !revs->tag_objects))
1508
			continue;
1509

1510
		show_reach(&obj->oid, obj->type, 0, eindex->hashes[i], NULL, 0);
1511
	}
1512
}
1513

1514
static void init_type_iterator(struct ewah_iterator *it,
1515
			       struct bitmap_index *bitmap_git,
1516
			       enum object_type type)
1517
{
1518
	switch (type) {
1519
	case OBJ_COMMIT:
1520
		ewah_iterator_init(it, bitmap_git->commits);
1521
		break;
1522

1523
	case OBJ_TREE:
1524
		ewah_iterator_init(it, bitmap_git->trees);
1525
		break;
1526

1527
	case OBJ_BLOB:
1528
		ewah_iterator_init(it, bitmap_git->blobs);
1529
		break;
1530

1531
	case OBJ_TAG:
1532
		ewah_iterator_init(it, bitmap_git->tags);
1533
		break;
1534

1535
	default:
1536
		BUG("object type %d not stored by bitmap type index", type);
1537
		break;
1538
	}
1539
}
1540

1541
static void show_objects_for_type(
1542
	struct bitmap_index *bitmap_git,
1543
	enum object_type object_type,
1544
	show_reachable_fn show_reach)
1545
{
1546
	size_t i = 0;
1547
	uint32_t offset;
1548

1549
	struct ewah_iterator it;
1550
	eword_t filter;
1551

1552
	struct bitmap *objects = bitmap_git->result;
1553

1554
	init_type_iterator(&it, bitmap_git, object_type);
1555

1556
	for (i = 0; i < objects->word_alloc &&
1557
			ewah_iterator_next(&filter, &it); i++) {
1558
		eword_t word = objects->words[i] & filter;
1559
		size_t pos = (i * BITS_IN_EWORD);
1560

1561
		if (!word)
1562
			continue;
1563

1564
		for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
1565
			struct packed_git *pack;
1566
			struct object_id oid;
1567
			uint32_t hash = 0, index_pos;
1568
			off_t ofs;
1569

1570
			if ((word >> offset) == 0)
1571
				break;
1572

1573
			offset += ewah_bit_ctz64(word >> offset);
1574

1575
			if (bitmap_is_midx(bitmap_git)) {
1576
				struct multi_pack_index *m = bitmap_git->midx;
1577
				uint32_t pack_id;
1578

1579
				index_pos = pack_pos_to_midx(m, pos + offset);
1580
				ofs = nth_midxed_offset(m, index_pos);
1581
				nth_midxed_object_oid(&oid, m, index_pos);
1582

1583
				pack_id = nth_midxed_pack_int_id(m, index_pos);
1584
				pack = bitmap_git->midx->packs[pack_id];
1585
			} else {
1586
				index_pos = pack_pos_to_index(bitmap_git->pack, pos + offset);
1587
				ofs = pack_pos_to_offset(bitmap_git->pack, pos + offset);
1588
				nth_bitmap_object_oid(bitmap_git, &oid, index_pos);
1589

1590
				pack = bitmap_git->pack;
1591
			}
1592

1593
			if (bitmap_git->hashes)
1594
				hash = get_be32(bitmap_git->hashes + index_pos);
1595

1596
			show_reach(&oid, object_type, 0, hash, pack, ofs);
1597
		}
1598
	}
1599
}
1600

1601
static int in_bitmapped_pack(struct bitmap_index *bitmap_git,
1602
			     struct object_list *roots)
1603
{
1604
	while (roots) {
1605
		struct object *object = roots->item;
1606
		roots = roots->next;
1607

1608
		if (bitmap_is_midx(bitmap_git)) {
1609
			if (bsearch_midx(&object->oid, bitmap_git->midx, NULL))
1610
				return 1;
1611
		} else {
1612
			if (find_pack_entry_one(object->oid.hash, bitmap_git->pack) > 0)
1613
				return 1;
1614
		}
1615
	}
1616

1617
	return 0;
1618
}
1619

1620
static struct bitmap *find_tip_objects(struct bitmap_index *bitmap_git,
1621
				       struct object_list *tip_objects,
1622
				       enum object_type type)
1623
{
1624
	struct bitmap *result = bitmap_new();
1625
	struct object_list *p;
1626

1627
	for (p = tip_objects; p; p = p->next) {
1628
		int pos;
1629

1630
		if (p->item->type != type)
1631
			continue;
1632

1633
		pos = bitmap_position(bitmap_git, &p->item->oid);
1634
		if (pos < 0)
1635
			continue;
1636

1637
		bitmap_set(result, pos);
1638
	}
1639

1640
	return result;
1641
}
1642

1643
static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git,
1644
				       struct object_list *tip_objects,
1645
				       struct bitmap *to_filter,
1646
				       enum object_type type)
1647
{
1648
	struct eindex *eindex = &bitmap_git->ext_index;
1649
	struct bitmap *tips;
1650
	struct ewah_iterator it;
1651
	eword_t mask;
1652
	uint32_t i;
1653

1654
	/*
1655
	 * The non-bitmap version of this filter never removes
1656
	 * objects which the other side specifically asked for,
1657
	 * so we must match that behavior.
1658
	 */
1659
	tips = find_tip_objects(bitmap_git, tip_objects, type);
1660

1661
	/*
1662
	 * We can use the type-level bitmap for 'type' to work in whole
1663
	 * words for the objects that are actually in the bitmapped
1664
	 * packfile.
1665
	 */
1666
	for (i = 0, init_type_iterator(&it, bitmap_git, type);
1667
	     i < to_filter->word_alloc && ewah_iterator_next(&mask, &it);
1668
	     i++) {
1669
		if (i < tips->word_alloc)
1670
			mask &= ~tips->words[i];
1671
		to_filter->words[i] &= ~mask;
1672
	}
1673

1674
	/*
1675
	 * Clear any objects that weren't in the packfile (and so would
1676
	 * not have been caught by the loop above. We'll have to check
1677
	 * them individually.
1678
	 */
1679
	for (i = 0; i < eindex->count; i++) {
1680
		size_t pos = st_add(i, bitmap_num_objects(bitmap_git));
1681
		if (eindex->objects[i]->type == type &&
1682
		    bitmap_get(to_filter, pos) &&
1683
		    !bitmap_get(tips, pos))
1684
			bitmap_unset(to_filter, pos);
1685
	}
1686

1687
	bitmap_free(tips);
1688
}
1689

1690
static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git,
1691
				    struct object_list *tip_objects,
1692
				    struct bitmap *to_filter)
1693
{
1694
	filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter,
1695
				   OBJ_BLOB);
1696
}
1697

1698
static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git,
1699
				     uint32_t pos)
1700
{
1701
	unsigned long size;
1702
	struct object_info oi = OBJECT_INFO_INIT;
1703

1704
	oi.sizep = &size;
1705

1706
	if (pos < bitmap_num_objects(bitmap_git)) {
1707
		struct packed_git *pack;
1708
		off_t ofs;
1709

1710
		if (bitmap_is_midx(bitmap_git)) {
1711
			uint32_t midx_pos = pack_pos_to_midx(bitmap_git->midx, pos);
1712
			uint32_t pack_id = nth_midxed_pack_int_id(bitmap_git->midx, midx_pos);
1713

1714
			pack = bitmap_git->midx->packs[pack_id];
1715
			ofs = nth_midxed_offset(bitmap_git->midx, midx_pos);
1716
		} else {
1717
			pack = bitmap_git->pack;
1718
			ofs = pack_pos_to_offset(pack, pos);
1719
		}
1720

1721
		if (packed_object_info(the_repository, pack, ofs, &oi) < 0) {
1722
			struct object_id oid;
1723
			nth_bitmap_object_oid(bitmap_git, &oid,
1724
					      pack_pos_to_index(pack, pos));
1725
			die(_("unable to get size of %s"), oid_to_hex(&oid));
1726
		}
1727
	} else {
1728
		struct eindex *eindex = &bitmap_git->ext_index;
1729
		struct object *obj = eindex->objects[pos - bitmap_num_objects(bitmap_git)];
1730
		if (oid_object_info_extended(the_repository, &obj->oid, &oi, 0) < 0)
1731
			die(_("unable to get size of %s"), oid_to_hex(&obj->oid));
1732
	}
1733

1734
	return size;
1735
}
1736

1737
static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git,
1738
				     struct object_list *tip_objects,
1739
				     struct bitmap *to_filter,
1740
				     unsigned long limit)
1741
{
1742
	struct eindex *eindex = &bitmap_git->ext_index;
1743
	struct bitmap *tips;
1744
	struct ewah_iterator it;
1745
	eword_t mask;
1746
	uint32_t i;
1747

1748
	tips = find_tip_objects(bitmap_git, tip_objects, OBJ_BLOB);
1749

1750
	for (i = 0, init_type_iterator(&it, bitmap_git, OBJ_BLOB);
1751
	     i < to_filter->word_alloc && ewah_iterator_next(&mask, &it);
1752
	     i++) {
1753
		eword_t word = to_filter->words[i] & mask;
1754
		unsigned offset;
1755

1756
		for (offset = 0; offset < BITS_IN_EWORD; offset++) {
1757
			uint32_t pos;
1758

1759
			if ((word >> offset) == 0)
1760
				break;
1761
			offset += ewah_bit_ctz64(word >> offset);
1762
			pos = i * BITS_IN_EWORD + offset;
1763

1764
			if (!bitmap_get(tips, pos) &&
1765
			    get_size_by_pos(bitmap_git, pos) >= limit)
1766
				bitmap_unset(to_filter, pos);
1767
		}
1768
	}
1769

1770
	for (i = 0; i < eindex->count; i++) {
1771
		size_t pos = st_add(i, bitmap_num_objects(bitmap_git));
1772
		if (eindex->objects[i]->type == OBJ_BLOB &&
1773
		    bitmap_get(to_filter, pos) &&
1774
		    !bitmap_get(tips, pos) &&
1775
		    get_size_by_pos(bitmap_git, pos) >= limit)
1776
			bitmap_unset(to_filter, pos);
1777
	}
1778

1779
	bitmap_free(tips);
1780
}
1781

1782
static void filter_bitmap_tree_depth(struct bitmap_index *bitmap_git,
1783
				     struct object_list *tip_objects,
1784
				     struct bitmap *to_filter,
1785
				     unsigned long limit)
1786
{
1787
	if (limit)
1788
		BUG("filter_bitmap_tree_depth given non-zero limit");
1789

1790
	filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter,
1791
				   OBJ_TREE);
1792
	filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter,
1793
				   OBJ_BLOB);
1794
}
1795

1796
static void filter_bitmap_object_type(struct bitmap_index *bitmap_git,
1797
				      struct object_list *tip_objects,
1798
				      struct bitmap *to_filter,
1799
				      enum object_type object_type)
1800
{
1801
	if (object_type < OBJ_COMMIT || object_type > OBJ_TAG)
1802
		BUG("filter_bitmap_object_type given invalid object");
1803

1804
	if (object_type != OBJ_TAG)
1805
		filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter, OBJ_TAG);
1806
	if (object_type != OBJ_COMMIT)
1807
		filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter, OBJ_COMMIT);
1808
	if (object_type != OBJ_TREE)
1809
		filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter, OBJ_TREE);
1810
	if (object_type != OBJ_BLOB)
1811
		filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter, OBJ_BLOB);
1812
}
1813

1814
static int filter_bitmap(struct bitmap_index *bitmap_git,
1815
			 struct object_list *tip_objects,
1816
			 struct bitmap *to_filter,
1817
			 struct list_objects_filter_options *filter)
1818
{
1819
	if (!filter || filter->choice == LOFC_DISABLED)
1820
		return 0;
1821

1822
	if (filter->choice == LOFC_BLOB_NONE) {
1823
		if (bitmap_git)
1824
			filter_bitmap_blob_none(bitmap_git, tip_objects,
1825
						to_filter);
1826
		return 0;
1827
	}
1828

1829
	if (filter->choice == LOFC_BLOB_LIMIT) {
1830
		if (bitmap_git)
1831
			filter_bitmap_blob_limit(bitmap_git, tip_objects,
1832
						 to_filter,
1833
						 filter->blob_limit_value);
1834
		return 0;
1835
	}
1836

1837
	if (filter->choice == LOFC_TREE_DEPTH &&
1838
	    filter->tree_exclude_depth == 0) {
1839
		if (bitmap_git)
1840
			filter_bitmap_tree_depth(bitmap_git, tip_objects,
1841
						 to_filter,
1842
						 filter->tree_exclude_depth);
1843
		return 0;
1844
	}
1845

1846
	if (filter->choice == LOFC_OBJECT_TYPE) {
1847
		if (bitmap_git)
1848
			filter_bitmap_object_type(bitmap_git, tip_objects,
1849
						  to_filter,
1850
						  filter->object_type);
1851
		return 0;
1852
	}
1853

1854
	if (filter->choice == LOFC_COMBINE) {
1855
		int i;
1856
		for (i = 0; i < filter->sub_nr; i++) {
1857
			if (filter_bitmap(bitmap_git, tip_objects, to_filter,
1858
					  &filter->sub[i]) < 0)
1859
				return -1;
1860
		}
1861
		return 0;
1862
	}
1863

1864
	/* filter choice not handled */
1865
	return -1;
1866
}
1867

1868
static int can_filter_bitmap(struct list_objects_filter_options *filter)
1869
{
1870
	return !filter_bitmap(NULL, NULL, NULL, filter);
1871
}
1872

1873

1874
static void filter_packed_objects_from_bitmap(struct bitmap_index *bitmap_git,
1875
					      struct bitmap *result)
1876
{
1877
	struct eindex *eindex = &bitmap_git->ext_index;
1878
	uint32_t objects_nr;
1879
	size_t i, pos;
1880

1881
	objects_nr = bitmap_num_objects(bitmap_git);
1882
	pos = objects_nr / BITS_IN_EWORD;
1883

1884
	if (pos > result->word_alloc)
1885
		pos = result->word_alloc;
1886

1887
	memset(result->words, 0x00, sizeof(eword_t) * pos);
1888
	for (i = pos * BITS_IN_EWORD; i < objects_nr; i++)
1889
		bitmap_unset(result, i);
1890

1891
	for (i = 0; i < eindex->count; ++i) {
1892
		if (has_object_pack(&eindex->objects[i]->oid))
1893
			bitmap_unset(result, objects_nr + i);
1894
	}
1895
}
1896

1897
struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,
1898
					 int filter_provided_objects)
1899
{
1900
	unsigned int i;
1901
	int use_boundary_traversal;
1902

1903
	struct object_list *wants = NULL;
1904
	struct object_list *haves = NULL;
1905

1906
	struct bitmap *wants_bitmap = NULL;
1907
	struct bitmap *haves_bitmap = NULL;
1908

1909
	struct bitmap_index *bitmap_git;
1910

1911
	/*
1912
	 * We can't do pathspec limiting with bitmaps, because we don't know
1913
	 * which commits are associated with which object changes (let alone
1914
	 * even which objects are associated with which paths).
1915
	 */
1916
	if (revs->prune)
1917
		return NULL;
1918

1919
	if (!can_filter_bitmap(&revs->filter))
1920
		return NULL;
1921

1922
	/* try to open a bitmapped pack, but don't parse it yet
1923
	 * because we may not need to use it */
1924
	CALLOC_ARRAY(bitmap_git, 1);
1925
	if (open_bitmap(revs->repo, bitmap_git) < 0)
1926
		goto cleanup;
1927

1928
	for (i = 0; i < revs->pending.nr; ++i) {
1929
		struct object *object = revs->pending.objects[i].item;
1930

1931
		if (object->type == OBJ_NONE)
1932
			parse_object_or_die(&object->oid, NULL);
1933

1934
		while (object->type == OBJ_TAG) {
1935
			struct tag *tag = (struct tag *) object;
1936

1937
			if (object->flags & UNINTERESTING)
1938
				object_list_insert(object, &haves);
1939
			else
1940
				object_list_insert(object, &wants);
1941

1942
			object = parse_object_or_die(get_tagged_oid(tag), NULL);
1943
			object->flags |= (tag->object.flags & UNINTERESTING);
1944
		}
1945

1946
		if (object->flags & UNINTERESTING)
1947
			object_list_insert(object, &haves);
1948
		else
1949
			object_list_insert(object, &wants);
1950
	}
1951

1952
	use_boundary_traversal = git_env_bool(GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL, -1);
1953
	if (use_boundary_traversal < 0) {
1954
		prepare_repo_settings(revs->repo);
1955
		use_boundary_traversal = revs->repo->settings.pack_use_bitmap_boundary_traversal;
1956
	}
1957

1958
	if (!use_boundary_traversal) {
1959
		/*
1960
		 * if we have a HAVES list, but none of those haves is contained
1961
		 * in the packfile that has a bitmap, we don't have anything to
1962
		 * optimize here
1963
		 */
1964
		if (haves && !in_bitmapped_pack(bitmap_git, haves))
1965
			goto cleanup;
1966
	}
1967

1968
	/* if we don't want anything, we're done here */
1969
	if (!wants)
1970
		goto cleanup;
1971

1972
	/*
1973
	 * now we're going to use bitmaps, so load the actual bitmap entries
1974
	 * from disk. this is the point of no return; after this the rev_list
1975
	 * becomes invalidated and we must perform the revwalk through bitmaps
1976
	 */
1977
	if (load_bitmap(revs->repo, bitmap_git) < 0)
1978
		goto cleanup;
1979

1980
	if (!use_boundary_traversal)
1981
		object_array_clear(&revs->pending);
1982

1983
	if (haves) {
1984
		if (use_boundary_traversal) {
1985
			trace2_region_enter("pack-bitmap", "haves/boundary", the_repository);
1986
			haves_bitmap = find_boundary_objects(bitmap_git, revs, haves);
1987
			trace2_region_leave("pack-bitmap", "haves/boundary", the_repository);
1988
		} else {
1989
			trace2_region_enter("pack-bitmap", "haves/classic", the_repository);
1990
			revs->ignore_missing_links = 1;
1991
			haves_bitmap = find_objects(bitmap_git, revs, haves, NULL);
1992
			reset_revision_walk();
1993
			revs->ignore_missing_links = 0;
1994
			trace2_region_leave("pack-bitmap", "haves/classic", the_repository);
1995
		}
1996

1997
		if (!haves_bitmap)
1998
			BUG("failed to perform bitmap walk");
1999
	}
2000

2001
	if (use_boundary_traversal) {
2002
		object_array_clear(&revs->pending);
2003
		reset_revision_walk();
2004
	}
2005

2006
	wants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap);
2007

2008
	if (!wants_bitmap)
2009
		BUG("failed to perform bitmap walk");
2010

2011
	if (haves_bitmap)
2012
		bitmap_and_not(wants_bitmap, haves_bitmap);
2013

2014
	filter_bitmap(bitmap_git,
2015
		      (revs->filter.choice && filter_provided_objects) ? NULL : wants,
2016
		      wants_bitmap,
2017
		      &revs->filter);
2018

2019
	if (revs->unpacked)
2020
		filter_packed_objects_from_bitmap(bitmap_git, wants_bitmap);
2021

2022
	bitmap_git->result = wants_bitmap;
2023
	bitmap_git->haves = haves_bitmap;
2024

2025
	object_list_free(&wants);
2026
	object_list_free(&haves);
2027

2028
	trace2_data_intmax("bitmap", the_repository, "pseudo_merges_satisfied",
2029
			   pseudo_merges_satisfied_nr);
2030
	trace2_data_intmax("bitmap", the_repository, "pseudo_merges_cascades",
2031
			   pseudo_merges_cascades_nr);
2032
	trace2_data_intmax("bitmap", the_repository, "bitmap/hits",
2033
			   existing_bitmaps_hits_nr);
2034
	trace2_data_intmax("bitmap", the_repository, "bitmap/misses",
2035
			   existing_bitmaps_misses_nr);
2036
	trace2_data_intmax("bitmap", the_repository, "bitmap/roots_with_bitmap",
2037
			   roots_with_bitmaps_nr);
2038
	trace2_data_intmax("bitmap", the_repository, "bitmap/roots_without_bitmap",
2039
			   roots_without_bitmaps_nr);
2040

2041
	return bitmap_git;
2042

2043
cleanup:
2044
	free_bitmap_index(bitmap_git);
2045
	object_list_free(&wants);
2046
	object_list_free(&haves);
2047
	return NULL;
2048
}
2049

2050
/*
2051
 * -1 means "stop trying further objects"; 0 means we may or may not have
2052
 * reused, but you can keep feeding bits.
2053
 */
2054
static int try_partial_reuse(struct bitmap_index *bitmap_git,
2055
			     struct bitmapped_pack *pack,
2056
			     size_t bitmap_pos,
2057
			     uint32_t pack_pos,
2058
			     struct bitmap *reuse,
2059
			     struct pack_window **w_curs)
2060
{
2061
	off_t offset, delta_obj_offset;
2062
	enum object_type type;
2063
	unsigned long size;
2064

2065
	if (pack_pos >= pack->p->num_objects)
2066
		return -1; /* not actually in the pack */
2067

2068
	offset = delta_obj_offset = pack_pos_to_offset(pack->p, pack_pos);
2069
	type = unpack_object_header(pack->p, w_curs, &offset, &size);
2070
	if (type < 0)
2071
		return -1; /* broken packfile, punt */
2072

2073
	if (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA) {
2074
		off_t base_offset;
2075
		uint32_t base_pos;
2076
		uint32_t base_bitmap_pos;
2077

2078
		/*
2079
		 * Find the position of the base object so we can look it up
2080
		 * in our bitmaps. If we can't come up with an offset, or if
2081
		 * that offset is not in the revidx, the pack is corrupt.
2082
		 * There's nothing we can do, so just punt on this object,
2083
		 * and the normal slow path will complain about it in
2084
		 * more detail.
2085
		 */
2086
		base_offset = get_delta_base(pack->p, w_curs, &offset, type,
2087
					     delta_obj_offset);
2088
		if (!base_offset)
2089
			return 0;
2090

2091
		offset_to_pack_pos(pack->p, base_offset, &base_pos);
2092

2093
		if (bitmap_is_midx(bitmap_git)) {
2094
			/*
2095
			 * Cross-pack deltas are rejected for now, but could
2096
			 * theoretically be supported in the future.
2097
			 *
2098
			 * We would need to ensure that we're sending both
2099
			 * halves of the delta/base pair, regardless of whether
2100
			 * or not the two cross a pack boundary. If they do,
2101
			 * then we must convert the delta to an REF_DELTA to
2102
			 * refer back to the base in the other pack.
2103
			 * */
2104
			if (midx_pair_to_pack_pos(bitmap_git->midx,
2105
						  pack->pack_int_id,
2106
						  base_offset,
2107
						  &base_bitmap_pos) < 0) {
2108
				return 0;
2109
			}
2110
		} else {
2111
			if (offset_to_pack_pos(pack->p, base_offset,
2112
					       &base_pos) < 0)
2113
				return 0;
2114
			/*
2115
			 * We assume delta dependencies always point backwards.
2116
			 * This lets us do a single pass, and is basically
2117
			 * always true due to the way OFS_DELTAs work. You would
2118
			 * not typically find REF_DELTA in a bitmapped pack,
2119
			 * since we only bitmap packs we write fresh, and
2120
			 * OFS_DELTA is the default). But let's double check to
2121
			 * make sure the pack wasn't written with odd
2122
			 * parameters.
2123
			 */
2124
			if (base_pos >= pack_pos)
2125
				return 0;
2126
			base_bitmap_pos = pack->bitmap_pos + base_pos;
2127
		}
2128

2129
		/*
2130
		 * And finally, if we're not sending the base as part of our
2131
		 * reuse chunk, then don't send this object either. The base
2132
		 * would come after us, along with other objects not
2133
		 * necessarily in the pack, which means we'd need to convert
2134
		 * to REF_DELTA on the fly. Better to just let the normal
2135
		 * object_entry code path handle it.
2136
		 */
2137
		if (!bitmap_get(reuse, base_bitmap_pos))
2138
			return 0;
2139
	}
2140

2141
	/*
2142
	 * If we got here, then the object is OK to reuse. Mark it.
2143
	 */
2144
	bitmap_set(reuse, bitmap_pos);
2145
	return 0;
2146
}
2147

2148
static void reuse_partial_packfile_from_bitmap_1(struct bitmap_index *bitmap_git,
2149
						 struct bitmapped_pack *pack,
2150
						 struct bitmap *reuse)
2151
{
2152
	struct bitmap *result = bitmap_git->result;
2153
	struct pack_window *w_curs = NULL;
2154
	size_t pos = pack->bitmap_pos / BITS_IN_EWORD;
2155

2156
	if (!pack->bitmap_pos) {
2157
		/*
2158
		 * If we're processing the first (in the case of a MIDX, the
2159
		 * preferred pack) or the only (in the case of single-pack
2160
		 * bitmaps) pack, then we can reuse whole words at a time.
2161
		 *
2162
		 * This is because we know that any deltas in this range *must*
2163
		 * have their bases chosen from the same pack, since:
2164
		 *
2165
		 * - In the single pack case, there is no other pack to choose
2166
		 *   them from.
2167
		 *
2168
		 * - In the MIDX case, the first pack is the preferred pack, so
2169
		 *   all ties are broken in favor of that pack (i.e. the one
2170
		 *   we're currently processing). So any duplicate bases will be
2171
		 *   resolved in favor of the pack we're processing.
2172
		 */
2173
		while (pos < result->word_alloc &&
2174
		       pos < pack->bitmap_nr / BITS_IN_EWORD &&
2175
		       result->words[pos] == (eword_t)~0)
2176
			pos++;
2177
		memset(reuse->words, 0xFF, pos * sizeof(eword_t));
2178
	}
2179

2180
	for (; pos < result->word_alloc; pos++) {
2181
		eword_t word = result->words[pos];
2182
		size_t offset;
2183

2184
		for (offset = 0; offset < BITS_IN_EWORD; offset++) {
2185
			size_t bit_pos;
2186
			uint32_t pack_pos;
2187

2188
			if (word >> offset == 0)
2189
				break;
2190

2191
			offset += ewah_bit_ctz64(word >> offset);
2192

2193
			bit_pos = pos * BITS_IN_EWORD + offset;
2194
			if (bit_pos < pack->bitmap_pos)
2195
				continue;
2196
			if (bit_pos >= pack->bitmap_pos + pack->bitmap_nr)
2197
				goto done;
2198

2199
			if (bitmap_is_midx(bitmap_git)) {
2200
				uint32_t midx_pos;
2201
				off_t ofs;
2202

2203
				midx_pos = pack_pos_to_midx(bitmap_git->midx, bit_pos);
2204
				ofs = nth_midxed_offset(bitmap_git->midx, midx_pos);
2205

2206
				if (offset_to_pack_pos(pack->p, ofs, &pack_pos) < 0)
2207
					BUG("could not find object in pack %s "
2208
					    "at offset %"PRIuMAX" in MIDX",
2209
					    pack_basename(pack->p), (uintmax_t)ofs);
2210
			} else {
2211
				pack_pos = cast_size_t_to_uint32_t(st_sub(bit_pos, pack->bitmap_pos));
2212
				if (pack_pos >= pack->p->num_objects)
2213
					BUG("advanced beyond the end of pack %s (%"PRIuMAX" > %"PRIu32")",
2214
					    pack_basename(pack->p), (uintmax_t)pack_pos,
2215
					    pack->p->num_objects);
2216
			}
2217

2218
			if (try_partial_reuse(bitmap_git, pack, bit_pos,
2219
					      pack_pos, reuse, &w_curs) < 0) {
2220
				/*
2221
				 * try_partial_reuse indicated we couldn't reuse
2222
				 * any bits, so there is no point in trying more
2223
				 * bits in the current word, or any other words
2224
				 * in result.
2225
				 *
2226
				 * Jump out of both loops to avoid future
2227
				 * unnecessary calls to try_partial_reuse.
2228
				 */
2229
				goto done;
2230
			}
2231
		}
2232
	}
2233

2234
done:
2235
	unuse_pack(&w_curs);
2236
}
2237

2238
static int bitmapped_pack_cmp(const void *va, const void *vb)
2239
{
2240
	const struct bitmapped_pack *a = va;
2241
	const struct bitmapped_pack *b = vb;
2242

2243
	if (a->bitmap_pos < b->bitmap_pos)
2244
		return -1;
2245
	if (a->bitmap_pos > b->bitmap_pos)
2246
		return 1;
2247
	return 0;
2248
}
2249

2250
void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,
2251
					struct bitmapped_pack **packs_out,
2252
					size_t *packs_nr_out,
2253
					struct bitmap **reuse_out,
2254
					int multi_pack_reuse)
2255
{
2256
	struct repository *r = the_repository;
2257
	struct bitmapped_pack *packs = NULL;
2258
	struct bitmap *result = bitmap_git->result;
2259
	struct bitmap *reuse;
2260
	size_t i;
2261
	size_t packs_nr = 0, packs_alloc = 0;
2262
	size_t word_alloc;
2263
	uint32_t objects_nr = 0;
2264

2265
	assert(result);
2266

2267
	load_reverse_index(r, bitmap_git);
2268

2269
	if (!bitmap_is_midx(bitmap_git) || !bitmap_git->midx->chunk_bitmapped_packs)
2270
		multi_pack_reuse = 0;
2271

2272
	if (multi_pack_reuse) {
2273
		for (i = 0; i < bitmap_git->midx->num_packs; i++) {
2274
			struct bitmapped_pack pack;
2275
			if (nth_bitmapped_pack(r, bitmap_git->midx, &pack, i) < 0) {
2276
				warning(_("unable to load pack: '%s', disabling pack-reuse"),
2277
					bitmap_git->midx->pack_names[i]);
2278
				free(packs);
2279
				return;
2280
			}
2281

2282
			if (!pack.bitmap_nr)
2283
				continue;
2284

2285
			ALLOC_GROW(packs, packs_nr + 1, packs_alloc);
2286
			memcpy(&packs[packs_nr++], &pack, sizeof(pack));
2287

2288
			objects_nr += pack.p->num_objects;
2289
		}
2290

2291
		QSORT(packs, packs_nr, bitmapped_pack_cmp);
2292
	} else {
2293
		struct packed_git *pack;
2294
		uint32_t pack_int_id;
2295

2296
		if (bitmap_is_midx(bitmap_git)) {
2297
			uint32_t preferred_pack_pos;
2298

2299
			if (midx_preferred_pack(bitmap_git->midx, &preferred_pack_pos) < 0) {
2300
				warning(_("unable to compute preferred pack, disabling pack-reuse"));
2301
				return;
2302
			}
2303

2304
			pack = bitmap_git->midx->packs[preferred_pack_pos];
2305
			pack_int_id = preferred_pack_pos;
2306
		} else {
2307
			pack = bitmap_git->pack;
2308
			/*
2309
			 * Any value for 'pack_int_id' will do here. When we
2310
			 * process the pack via try_partial_reuse(), we won't
2311
			 * use the `pack_int_id` field since we have a non-MIDX
2312
			 * bitmap.
2313
			 *
2314
			 * Use '-1' as a sentinel value to make it clear
2315
			 * that we do not expect to read this field.
2316
			 */
2317
			pack_int_id = -1;
2318
		}
2319

2320
		ALLOC_GROW(packs, packs_nr + 1, packs_alloc);
2321
		packs[packs_nr].p = pack;
2322
		packs[packs_nr].pack_int_id = pack_int_id;
2323
		packs[packs_nr].bitmap_nr = pack->num_objects;
2324
		packs[packs_nr].bitmap_pos = 0;
2325

2326
		objects_nr = packs[packs_nr++].bitmap_nr;
2327
	}
2328

2329
	word_alloc = objects_nr / BITS_IN_EWORD;
2330
	if (objects_nr % BITS_IN_EWORD)
2331
		word_alloc++;
2332
	reuse = bitmap_word_alloc(word_alloc);
2333

2334
	for (i = 0; i < packs_nr; i++)
2335
		reuse_partial_packfile_from_bitmap_1(bitmap_git, &packs[i], reuse);
2336

2337
	if (bitmap_is_empty(reuse)) {
2338
		free(packs);
2339
		bitmap_free(reuse);
2340
		return;
2341
	}
2342

2343
	/*
2344
	 * Drop any reused objects from the result, since they will not
2345
	 * need to be handled separately.
2346
	 */
2347
	bitmap_and_not(result, reuse);
2348
	*packs_out = packs;
2349
	*packs_nr_out = packs_nr;
2350
	*reuse_out = reuse;
2351
}
2352

2353
int bitmap_walk_contains(struct bitmap_index *bitmap_git,
2354
			 struct bitmap *bitmap, const struct object_id *oid)
2355
{
2356
	int idx;
2357

2358
	if (!bitmap)
2359
		return 0;
2360

2361
	idx = bitmap_position(bitmap_git, oid);
2362
	return idx >= 0 && bitmap_get(bitmap, idx);
2363
}
2364

2365
void traverse_bitmap_commit_list(struct bitmap_index *bitmap_git,
2366
				 struct rev_info *revs,
2367
				 show_reachable_fn show_reachable)
2368
{
2369
	assert(bitmap_git->result);
2370

2371
	show_objects_for_type(bitmap_git, OBJ_COMMIT, show_reachable);
2372
	if (revs->tree_objects)
2373
		show_objects_for_type(bitmap_git, OBJ_TREE, show_reachable);
2374
	if (revs->blob_objects)
2375
		show_objects_for_type(bitmap_git, OBJ_BLOB, show_reachable);
2376
	if (revs->tag_objects)
2377
		show_objects_for_type(bitmap_git, OBJ_TAG, show_reachable);
2378

2379
	show_extended_objects(bitmap_git, revs, show_reachable);
2380
}
2381

2382
static uint32_t count_object_type(struct bitmap_index *bitmap_git,
2383
				  enum object_type type)
2384
{
2385
	struct bitmap *objects = bitmap_git->result;
2386
	struct eindex *eindex = &bitmap_git->ext_index;
2387

2388
	uint32_t i = 0, count = 0;
2389
	struct ewah_iterator it;
2390
	eword_t filter;
2391

2392
	init_type_iterator(&it, bitmap_git, type);
2393

2394
	while (i < objects->word_alloc && ewah_iterator_next(&filter, &it)) {
2395
		eword_t word = objects->words[i++] & filter;
2396
		count += ewah_bit_popcount64(word);
2397
	}
2398

2399
	for (i = 0; i < eindex->count; ++i) {
2400
		if (eindex->objects[i]->type == type &&
2401
		    bitmap_get(objects,
2402
			       st_add(bitmap_num_objects(bitmap_git), i)))
2403
			count++;
2404
	}
2405

2406
	return count;
2407
}
2408

2409
void count_bitmap_commit_list(struct bitmap_index *bitmap_git,
2410
			      uint32_t *commits, uint32_t *trees,
2411
			      uint32_t *blobs, uint32_t *tags)
2412
{
2413
	assert(bitmap_git->result);
2414

2415
	if (commits)
2416
		*commits = count_object_type(bitmap_git, OBJ_COMMIT);
2417

2418
	if (trees)
2419
		*trees = count_object_type(bitmap_git, OBJ_TREE);
2420

2421
	if (blobs)
2422
		*blobs = count_object_type(bitmap_git, OBJ_BLOB);
2423

2424
	if (tags)
2425
		*tags = count_object_type(bitmap_git, OBJ_TAG);
2426
}
2427

2428
struct bitmap_test_data {
2429
	struct bitmap_index *bitmap_git;
2430
	struct bitmap *base;
2431
	struct bitmap *commits;
2432
	struct bitmap *trees;
2433
	struct bitmap *blobs;
2434
	struct bitmap *tags;
2435
	struct progress *prg;
2436
	size_t seen;
2437
};
2438

2439
static void test_bitmap_type(struct bitmap_test_data *tdata,
2440
			     struct object *obj, int pos)
2441
{
2442
	enum object_type bitmap_type = OBJ_NONE;
2443
	int bitmaps_nr = 0;
2444

2445
	if (bitmap_get(tdata->commits, pos)) {
2446
		bitmap_type = OBJ_COMMIT;
2447
		bitmaps_nr++;
2448
	}
2449
	if (bitmap_get(tdata->trees, pos)) {
2450
		bitmap_type = OBJ_TREE;
2451
		bitmaps_nr++;
2452
	}
2453
	if (bitmap_get(tdata->blobs, pos)) {
2454
		bitmap_type = OBJ_BLOB;
2455
		bitmaps_nr++;
2456
	}
2457
	if (bitmap_get(tdata->tags, pos)) {
2458
		bitmap_type = OBJ_TAG;
2459
		bitmaps_nr++;
2460
	}
2461

2462
	if (bitmap_type == OBJ_NONE)
2463
		die(_("object '%s' not found in type bitmaps"),
2464
		    oid_to_hex(&obj->oid));
2465

2466
	if (bitmaps_nr > 1)
2467
		die(_("object '%s' does not have a unique type"),
2468
		    oid_to_hex(&obj->oid));
2469

2470
	if (bitmap_type != obj->type)
2471
		die(_("object '%s': real type '%s', expected: '%s'"),
2472
		    oid_to_hex(&obj->oid),
2473
		    type_name(obj->type),
2474
		    type_name(bitmap_type));
2475
}
2476

2477
static void test_show_object(struct object *object,
2478
			     const char *name UNUSED,
2479
			     void *data)
2480
{
2481
	struct bitmap_test_data *tdata = data;
2482
	int bitmap_pos;
2483

2484
	bitmap_pos = bitmap_position(tdata->bitmap_git, &object->oid);
2485
	if (bitmap_pos < 0)
2486
		die(_("object not in bitmap: '%s'"), oid_to_hex(&object->oid));
2487
	test_bitmap_type(tdata, object, bitmap_pos);
2488

2489
	bitmap_set(tdata->base, bitmap_pos);
2490
	display_progress(tdata->prg, ++tdata->seen);
2491
}
2492

2493
static void test_show_commit(struct commit *commit, void *data)
2494
{
2495
	struct bitmap_test_data *tdata = data;
2496
	int bitmap_pos;
2497

2498
	bitmap_pos = bitmap_position(tdata->bitmap_git,
2499
				     &commit->object.oid);
2500
	if (bitmap_pos < 0)
2501
		die(_("object not in bitmap: '%s'"), oid_to_hex(&commit->object.oid));
2502
	test_bitmap_type(tdata, &commit->object, bitmap_pos);
2503

2504
	bitmap_set(tdata->base, bitmap_pos);
2505
	display_progress(tdata->prg, ++tdata->seen);
2506
}
2507

2508
void test_bitmap_walk(struct rev_info *revs)
2509
{
2510
	struct object *root;
2511
	struct bitmap *result = NULL;
2512
	size_t result_popcnt;
2513
	struct bitmap_test_data tdata;
2514
	struct bitmap_index *bitmap_git;
2515
	struct ewah_bitmap *bm;
2516

2517
	if (!(bitmap_git = prepare_bitmap_git(revs->repo)))
2518
		die(_("failed to load bitmap indexes"));
2519

2520
	if (revs->pending.nr != 1)
2521
		die(_("you must specify exactly one commit to test"));
2522

2523
	fprintf_ln(stderr, "Bitmap v%d test (%d entries%s)",
2524
		bitmap_git->version,
2525
		bitmap_git->entry_count,
2526
		bitmap_git->table_lookup ? "" : " loaded");
2527

2528
	root = revs->pending.objects[0].item;
2529
	bm = bitmap_for_commit(bitmap_git, (struct commit *)root);
2530

2531
	if (bm) {
2532
		fprintf_ln(stderr, "Found bitmap for '%s'. %d bits / %08x checksum",
2533
			oid_to_hex(&root->oid), (int)bm->bit_size, ewah_checksum(bm));
2534

2535
		result = ewah_to_bitmap(bm);
2536
	}
2537

2538
	if (!result)
2539
		die(_("commit '%s' doesn't have an indexed bitmap"), oid_to_hex(&root->oid));
2540

2541
	revs->tag_objects = 1;
2542
	revs->tree_objects = 1;
2543
	revs->blob_objects = 1;
2544

2545
	result_popcnt = bitmap_popcount(result);
2546

2547
	if (prepare_revision_walk(revs))
2548
		die(_("revision walk setup failed"));
2549

2550
	tdata.bitmap_git = bitmap_git;
2551
	tdata.base = bitmap_new();
2552
	tdata.commits = ewah_to_bitmap(bitmap_git->commits);
2553
	tdata.trees = ewah_to_bitmap(bitmap_git->trees);
2554
	tdata.blobs = ewah_to_bitmap(bitmap_git->blobs);
2555
	tdata.tags = ewah_to_bitmap(bitmap_git->tags);
2556
	tdata.prg = start_progress("Verifying bitmap entries", result_popcnt);
2557
	tdata.seen = 0;
2558

2559
	traverse_commit_list(revs, &test_show_commit, &test_show_object, &tdata);
2560

2561
	stop_progress(&tdata.prg);
2562

2563
	if (bitmap_equals(result, tdata.base))
2564
		fprintf_ln(stderr, "OK!");
2565
	else
2566
		die(_("mismatch in bitmap results"));
2567

2568
	bitmap_free(result);
2569
	bitmap_free(tdata.base);
2570
	bitmap_free(tdata.commits);
2571
	bitmap_free(tdata.trees);
2572
	bitmap_free(tdata.blobs);
2573
	bitmap_free(tdata.tags);
2574
	free_bitmap_index(bitmap_git);
2575
}
2576

2577
int test_bitmap_commits(struct repository *r)
2578
{
2579
	struct object_id oid;
2580
	MAYBE_UNUSED void *value;
2581
	struct bitmap_index *bitmap_git = prepare_bitmap_git(r);
2582

2583
	if (!bitmap_git)
2584
		die(_("failed to load bitmap indexes"));
2585

2586
	/*
2587
	 * As this function is only used to print bitmap selected
2588
	 * commits, we don't have to read the commit table.
2589
	 */
2590
	if (bitmap_git->table_lookup) {
2591
		if (load_bitmap_entries_v1(bitmap_git) < 0)
2592
			die(_("failed to load bitmap indexes"));
2593
	}
2594

2595
	kh_foreach(bitmap_git->bitmaps, oid, value, {
2596
		printf_ln("%s", oid_to_hex(&oid));
2597
	});
2598

2599
	free_bitmap_index(bitmap_git);
2600

2601
	return 0;
2602
}
2603

2604
int test_bitmap_hashes(struct repository *r)
2605
{
2606
	struct bitmap_index *bitmap_git = prepare_bitmap_git(r);
2607
	struct object_id oid;
2608
	uint32_t i, index_pos;
2609

2610
	if (!bitmap_git || !bitmap_git->hashes)
2611
		goto cleanup;
2612

2613
	for (i = 0; i < bitmap_num_objects(bitmap_git); i++) {
2614
		if (bitmap_is_midx(bitmap_git))
2615
			index_pos = pack_pos_to_midx(bitmap_git->midx, i);
2616
		else
2617
			index_pos = pack_pos_to_index(bitmap_git->pack, i);
2618

2619
		nth_bitmap_object_oid(bitmap_git, &oid, index_pos);
2620

2621
		printf_ln("%s %"PRIu32"",
2622
		       oid_to_hex(&oid), get_be32(bitmap_git->hashes + index_pos));
2623
	}
2624

2625
cleanup:
2626
	free_bitmap_index(bitmap_git);
2627

2628
	return 0;
2629
}
2630

2631
static void bit_pos_to_object_id(struct bitmap_index *bitmap_git,
2632
				 uint32_t bit_pos,
2633
				 struct object_id *oid)
2634
{
2635
	uint32_t index_pos;
2636

2637
	if (bitmap_is_midx(bitmap_git))
2638
		index_pos = pack_pos_to_midx(bitmap_git->midx, bit_pos);
2639
	else
2640
		index_pos = pack_pos_to_index(bitmap_git->pack, bit_pos);
2641

2642
	nth_bitmap_object_oid(bitmap_git, oid, index_pos);
2643
}
2644

2645
int test_bitmap_pseudo_merges(struct repository *r)
2646
{
2647
	struct bitmap_index *bitmap_git;
2648
	uint32_t i;
2649

2650
	bitmap_git = prepare_bitmap_git(r);
2651
	if (!bitmap_git || !bitmap_git->pseudo_merges.nr)
2652
		goto cleanup;
2653

2654
	for (i = 0; i < bitmap_git->pseudo_merges.nr; i++) {
2655
		struct pseudo_merge *merge;
2656
		struct ewah_bitmap *commits_bitmap, *merge_bitmap;
2657

2658
		merge = use_pseudo_merge(&bitmap_git->pseudo_merges,
2659
					 &bitmap_git->pseudo_merges.v[i]);
2660
		commits_bitmap = merge->commits;
2661
		merge_bitmap = pseudo_merge_bitmap(&bitmap_git->pseudo_merges,
2662
						   merge);
2663

2664
		printf("at=%"PRIuMAX", commits=%"PRIuMAX", objects=%"PRIuMAX"\n",
2665
		       (uintmax_t)merge->at,
2666
		       (uintmax_t)ewah_bitmap_popcount(commits_bitmap),
2667
		       (uintmax_t)ewah_bitmap_popcount(merge_bitmap));
2668
	}
2669

2670
cleanup:
2671
	free_bitmap_index(bitmap_git);
2672
	return 0;
2673
}
2674

2675
static void dump_ewah_object_ids(struct bitmap_index *bitmap_git,
2676
				 struct ewah_bitmap *bitmap)
2677

2678
{
2679
	struct ewah_iterator it;
2680
	eword_t word;
2681
	uint32_t pos = 0;
2682

2683
	ewah_iterator_init(&it, bitmap);
2684

2685
	while (ewah_iterator_next(&word, &it)) {
2686
		struct object_id oid;
2687
		uint32_t offset;
2688

2689
		for (offset = 0; offset < BITS_IN_EWORD; offset++) {
2690
			if (!(word >> offset))
2691
				break;
2692

2693
			offset += ewah_bit_ctz64(word >> offset);
2694

2695
			bit_pos_to_object_id(bitmap_git, pos + offset, &oid);
2696
			printf("%s\n", oid_to_hex(&oid));
2697
		}
2698
		pos += BITS_IN_EWORD;
2699
	}
2700
}
2701

2702
int test_bitmap_pseudo_merge_commits(struct repository *r, uint32_t n)
2703
{
2704
	struct bitmap_index *bitmap_git;
2705
	struct pseudo_merge *merge;
2706
	int ret = 0;
2707

2708
	bitmap_git = prepare_bitmap_git(r);
2709
	if (!bitmap_git || !bitmap_git->pseudo_merges.nr)
2710
		goto cleanup;
2711

2712
	if (n >= bitmap_git->pseudo_merges.nr) {
2713
		ret = error(_("pseudo-merge index out of range "
2714
			      "(%"PRIu32" >= %"PRIuMAX")"),
2715
			    n, (uintmax_t)bitmap_git->pseudo_merges.nr);
2716
		goto cleanup;
2717
	}
2718

2719
	merge = use_pseudo_merge(&bitmap_git->pseudo_merges,
2720
				 &bitmap_git->pseudo_merges.v[n]);
2721
	dump_ewah_object_ids(bitmap_git, merge->commits);
2722

2723
cleanup:
2724
	free_bitmap_index(bitmap_git);
2725
	return ret;
2726
}
2727

2728
int test_bitmap_pseudo_merge_objects(struct repository *r, uint32_t n)
2729
{
2730
	struct bitmap_index *bitmap_git;
2731
	struct pseudo_merge *merge;
2732
	int ret = 0;
2733

2734
	bitmap_git = prepare_bitmap_git(r);
2735
	if (!bitmap_git || !bitmap_git->pseudo_merges.nr)
2736
		goto cleanup;
2737

2738
	if (n >= bitmap_git->pseudo_merges.nr) {
2739
		ret = error(_("pseudo-merge index out of range "
2740
			      "(%"PRIu32" >= %"PRIuMAX")"),
2741
			    n, (uintmax_t)bitmap_git->pseudo_merges.nr);
2742
		goto cleanup;
2743
	}
2744

2745
	merge = use_pseudo_merge(&bitmap_git->pseudo_merges,
2746
				 &bitmap_git->pseudo_merges.v[n]);
2747

2748
	dump_ewah_object_ids(bitmap_git,
2749
			     pseudo_merge_bitmap(&bitmap_git->pseudo_merges,
2750
						 merge));
2751

2752
cleanup:
2753
	free_bitmap_index(bitmap_git);
2754
	return ret;
2755
}
2756

2757
int rebuild_bitmap(const uint32_t *reposition,
2758
		   struct ewah_bitmap *source,
2759
		   struct bitmap *dest)
2760
{
2761
	uint32_t pos = 0;
2762
	struct ewah_iterator it;
2763
	eword_t word;
2764

2765
	ewah_iterator_init(&it, source);
2766

2767
	while (ewah_iterator_next(&word, &it)) {
2768
		uint32_t offset, bit_pos;
2769

2770
		for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
2771
			if ((word >> offset) == 0)
2772
				break;
2773

2774
			offset += ewah_bit_ctz64(word >> offset);
2775

2776
			bit_pos = reposition[pos + offset];
2777
			if (bit_pos > 0)
2778
				bitmap_set(dest, bit_pos - 1);
2779
			else /* can't reuse, we don't have the object */
2780
				return -1;
2781
		}
2782

2783
		pos += BITS_IN_EWORD;
2784
	}
2785
	return 0;
2786
}
2787

2788
uint32_t *create_bitmap_mapping(struct bitmap_index *bitmap_git,
2789
				struct packing_data *mapping)
2790
{
2791
	struct repository *r = the_repository;
2792
	uint32_t i, num_objects;
2793
	uint32_t *reposition;
2794

2795
	if (!bitmap_is_midx(bitmap_git))
2796
		load_reverse_index(r, bitmap_git);
2797
	else if (load_midx_revindex(bitmap_git->midx))
2798
		BUG("rebuild_existing_bitmaps: missing required rev-cache "
2799
		    "extension");
2800

2801
	num_objects = bitmap_num_objects(bitmap_git);
2802
	CALLOC_ARRAY(reposition, num_objects);
2803

2804
	for (i = 0; i < num_objects; ++i) {
2805
		struct object_id oid;
2806
		struct object_entry *oe;
2807
		uint32_t index_pos;
2808

2809
		if (bitmap_is_midx(bitmap_git))
2810
			index_pos = pack_pos_to_midx(bitmap_git->midx, i);
2811
		else
2812
			index_pos = pack_pos_to_index(bitmap_git->pack, i);
2813
		nth_bitmap_object_oid(bitmap_git, &oid, index_pos);
2814
		oe = packlist_find(mapping, &oid);
2815

2816
		if (oe) {
2817
			reposition[i] = oe_in_pack_pos(mapping, oe) + 1;
2818
			if (bitmap_git->hashes && !oe->hash)
2819
				oe->hash = get_be32(bitmap_git->hashes + index_pos);
2820
		}
2821
	}
2822

2823
	return reposition;
2824
}
2825

2826
void free_bitmap_index(struct bitmap_index *b)
2827
{
2828
	if (!b)
2829
		return;
2830

2831
	if (b->map)
2832
		munmap(b->map, b->map_size);
2833
	ewah_pool_free(b->commits);
2834
	ewah_pool_free(b->trees);
2835
	ewah_pool_free(b->blobs);
2836
	ewah_pool_free(b->tags);
2837
	if (b->bitmaps) {
2838
		struct stored_bitmap *sb;
2839
		kh_foreach_value(b->bitmaps, sb, {
2840
			ewah_pool_free(sb->root);
2841
			free(sb);
2842
		});
2843
	}
2844
	kh_destroy_oid_map(b->bitmaps);
2845
	free(b->ext_index.objects);
2846
	free(b->ext_index.hashes);
2847
	kh_destroy_oid_pos(b->ext_index.positions);
2848
	bitmap_free(b->result);
2849
	bitmap_free(b->haves);
2850
	if (bitmap_is_midx(b)) {
2851
		/*
2852
		 * Multi-pack bitmaps need to have resources associated with
2853
		 * their on-disk reverse indexes unmapped so that stale .rev and
2854
		 * .bitmap files can be removed.
2855
		 *
2856
		 * Unlike pack-based bitmaps, multi-pack bitmaps can be read and
2857
		 * written in the same 'git multi-pack-index write --bitmap'
2858
		 * process. Close resources so they can be removed safely on
2859
		 * platforms like Windows.
2860
		 */
2861
		close_midx_revindex(b->midx);
2862
	}
2863
	free_pseudo_merge_map(&b->pseudo_merges);
2864
	free(b);
2865
}
2866

2867
int bitmap_has_oid_in_uninteresting(struct bitmap_index *bitmap_git,
2868
				    const struct object_id *oid)
2869
{
2870
	return bitmap_git &&
2871
		bitmap_walk_contains(bitmap_git, bitmap_git->haves, oid);
2872
}
2873

2874
static off_t get_disk_usage_for_type(struct bitmap_index *bitmap_git,
2875
				     enum object_type object_type)
2876
{
2877
	struct bitmap *result = bitmap_git->result;
2878
	off_t total = 0;
2879
	struct ewah_iterator it;
2880
	eword_t filter;
2881
	size_t i;
2882

2883
	init_type_iterator(&it, bitmap_git, object_type);
2884
	for (i = 0; i < result->word_alloc &&
2885
			ewah_iterator_next(&filter, &it); i++) {
2886
		eword_t word = result->words[i] & filter;
2887
		size_t base = (i * BITS_IN_EWORD);
2888
		unsigned offset;
2889

2890
		if (!word)
2891
			continue;
2892

2893
		for (offset = 0; offset < BITS_IN_EWORD; offset++) {
2894
			if ((word >> offset) == 0)
2895
				break;
2896

2897
			offset += ewah_bit_ctz64(word >> offset);
2898

2899
			if (bitmap_is_midx(bitmap_git)) {
2900
				uint32_t pack_pos;
2901
				uint32_t midx_pos = pack_pos_to_midx(bitmap_git->midx, base + offset);
2902
				off_t offset = nth_midxed_offset(bitmap_git->midx, midx_pos);
2903

2904
				uint32_t pack_id = nth_midxed_pack_int_id(bitmap_git->midx, midx_pos);
2905
				struct packed_git *pack = bitmap_git->midx->packs[pack_id];
2906

2907
				if (offset_to_pack_pos(pack, offset, &pack_pos) < 0) {
2908
					struct object_id oid;
2909
					nth_midxed_object_oid(&oid, bitmap_git->midx, midx_pos);
2910

2911
					die(_("could not find '%s' in pack '%s' at offset %"PRIuMAX),
2912
					    oid_to_hex(&oid),
2913
					    pack->pack_name,
2914
					    (uintmax_t)offset);
2915
				}
2916

2917
				total += pack_pos_to_offset(pack, pack_pos + 1) - offset;
2918
			} else {
2919
				size_t pos = base + offset;
2920
				total += pack_pos_to_offset(bitmap_git->pack, pos + 1) -
2921
					 pack_pos_to_offset(bitmap_git->pack, pos);
2922
			}
2923
		}
2924
	}
2925

2926
	return total;
2927
}
2928

2929
static off_t get_disk_usage_for_extended(struct bitmap_index *bitmap_git)
2930
{
2931
	struct bitmap *result = bitmap_git->result;
2932
	struct eindex *eindex = &bitmap_git->ext_index;
2933
	off_t total = 0;
2934
	struct object_info oi = OBJECT_INFO_INIT;
2935
	off_t object_size;
2936
	size_t i;
2937

2938
	oi.disk_sizep = &object_size;
2939

2940
	for (i = 0; i < eindex->count; i++) {
2941
		struct object *obj = eindex->objects[i];
2942

2943
		if (!bitmap_get(result,
2944
				st_add(bitmap_num_objects(bitmap_git), i)))
2945
			continue;
2946

2947
		if (oid_object_info_extended(the_repository, &obj->oid, &oi, 0) < 0)
2948
			die(_("unable to get disk usage of '%s'"),
2949
			    oid_to_hex(&obj->oid));
2950

2951
		total += object_size;
2952
	}
2953
	return total;
2954
}
2955

2956
off_t get_disk_usage_from_bitmap(struct bitmap_index *bitmap_git,
2957
				 struct rev_info *revs)
2958
{
2959
	off_t total = 0;
2960

2961
	total += get_disk_usage_for_type(bitmap_git, OBJ_COMMIT);
2962
	if (revs->tree_objects)
2963
		total += get_disk_usage_for_type(bitmap_git, OBJ_TREE);
2964
	if (revs->blob_objects)
2965
		total += get_disk_usage_for_type(bitmap_git, OBJ_BLOB);
2966
	if (revs->tag_objects)
2967
		total += get_disk_usage_for_type(bitmap_git, OBJ_TAG);
2968

2969
	total += get_disk_usage_for_extended(bitmap_git);
2970

2971
	return total;
2972
}
2973

2974
int bitmap_is_midx(struct bitmap_index *bitmap_git)
2975
{
2976
	return !!bitmap_git->midx;
2977
}
2978

2979
const struct string_list *bitmap_preferred_tips(struct repository *r)
2980
{
2981
	const struct string_list *dest;
2982

2983
	if (!repo_config_get_string_multi(r, "pack.preferbitmaptips", &dest))
2984
		return dest;
2985
	return NULL;
2986
}
2987

2988
int bitmap_is_preferred_refname(struct repository *r, const char *refname)
2989
{
2990
	const struct string_list *preferred_tips = bitmap_preferred_tips(r);
2991
	struct string_list_item *item;
2992

2993
	if (!preferred_tips)
2994
		return 0;
2995

2996
	for_each_string_list_item(item, preferred_tips) {
2997
		if (starts_with(refname, item->string))
2998
			return 1;
2999
	}
3000

3001
	return 0;
3002
}
3003

3004
static int verify_bitmap_file(const char *name)
3005
{
3006
	struct stat st;
3007
	unsigned char *data;
3008
	int fd = git_open(name);
3009
	int res = 0;
3010

3011
	/* It is OK to not have the file. */
3012
	if (fd < 0 || fstat(fd, &st)) {
3013
		if (fd >= 0)
3014
			close(fd);
3015
		return 0;
3016
	}
3017

3018
	data = xmmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
3019
	close(fd);
3020
	if (!hashfile_checksum_valid(data, st.st_size))
3021
		res = error(_("bitmap file '%s' has invalid checksum"),
3022
			    name);
3023

3024
	munmap(data, st.st_size);
3025
	return res;
3026
}
3027

3028
int verify_bitmap_files(struct repository *r)
3029
{
3030
	int res = 0;
3031

3032
	for (struct multi_pack_index *m = get_multi_pack_index(r);
3033
	     m; m = m->next) {
3034
		char *midx_bitmap_name = midx_bitmap_filename(m);
3035
		res |= verify_bitmap_file(midx_bitmap_name);
3036
		free(midx_bitmap_name);
3037
	}
3038

3039
	for (struct packed_git *p = get_all_packs(r);
3040
	     p; p = p->next) {
3041
		char *pack_bitmap_name = pack_bitmap_filename(p);
3042
		res |= verify_bitmap_file(pack_bitmap_name);
3043
		free(pack_bitmap_name);
3044
	}
3045

3046
	return res;
3047
}
3048