git

1
#include "builtin.h"
2
#include "environment.h"
3
#include "gettext.h"
4
#include "hex.h"
5
#include "repository.h"
6
#include "config.h"
7
#include "attr.h"
8
#include "object.h"
9
#include "commit.h"
10
#include "tag.h"
11
#include "delta.h"
12
#include "pack.h"
13
#include "pack-revindex.h"
14
#include "csum-file.h"
15
#include "tree-walk.h"
16
#include "diff.h"
17
#include "revision.h"
18
#include "list-objects.h"
19
#include "list-objects-filter-options.h"
20
#include "pack-objects.h"
21
#include "progress.h"
22
#include "refs.h"
23
#include "streaming.h"
24
#include "thread-utils.h"
25
#include "pack-bitmap.h"
26
#include "delta-islands.h"
27
#include "reachable.h"
28
#include "oid-array.h"
29
#include "strvec.h"
30
#include "list.h"
31
#include "packfile.h"
32
#include "object-file.h"
33
#include "object-store-ll.h"
34
#include "replace-object.h"
35
#include "dir.h"
36
#include "midx.h"
37
#include "trace2.h"
38
#include "shallow.h"
39
#include "promisor-remote.h"
40
#include "pack-mtimes.h"
41
#include "parse-options.h"
42

43
/*
44
 * Objects we are going to pack are collected in the `to_pack` structure.
45
 * It contains an array (dynamically expanded) of the object data, and a map
46
 * that can resolve SHA1s to their position in the array.
47
 */
48
static struct packing_data to_pack;
49

50
static inline struct object_entry *oe_delta(
51
		const struct packing_data *pack,
52
		const struct object_entry *e)
53
{
54
	if (!e->delta_idx)
55
		return NULL;
56
	if (e->ext_base)
57
		return &pack->ext_bases[e->delta_idx - 1];
58
	else
59
		return &pack->objects[e->delta_idx - 1];
60
}
61

62
static inline unsigned long oe_delta_size(struct packing_data *pack,
63
					  const struct object_entry *e)
64
{
65
	if (e->delta_size_valid)
66
		return e->delta_size_;
67

68
	/*
69
	 * pack->delta_size[] can't be NULL because oe_set_delta_size()
70
	 * must have been called when a new delta is saved with
71
	 * oe_set_delta().
72
	 * If oe_delta() returns NULL (i.e. default state, which means
73
	 * delta_size_valid is also false), then the caller must never
74
	 * call oe_delta_size().
75
	 */
76
	return pack->delta_size[e - pack->objects];
77
}
78

79
unsigned long oe_get_size_slow(struct packing_data *pack,
80
			       const struct object_entry *e);
81

82
static inline unsigned long oe_size(struct packing_data *pack,
83
				    const struct object_entry *e)
84
{
85
	if (e->size_valid)
86
		return e->size_;
87

88
	return oe_get_size_slow(pack, e);
89
}
90

91
static inline void oe_set_delta(struct packing_data *pack,
92
				struct object_entry *e,
93
				struct object_entry *delta)
94
{
95
	if (delta)
96
		e->delta_idx = (delta - pack->objects) + 1;
97
	else
98
		e->delta_idx = 0;
99
}
100

101
static inline struct object_entry *oe_delta_sibling(
102
		const struct packing_data *pack,
103
		const struct object_entry *e)
104
{
105
	if (e->delta_sibling_idx)
106
		return &pack->objects[e->delta_sibling_idx - 1];
107
	return NULL;
108
}
109

110
static inline struct object_entry *oe_delta_child(
111
		const struct packing_data *pack,
112
		const struct object_entry *e)
113
{
114
	if (e->delta_child_idx)
115
		return &pack->objects[e->delta_child_idx - 1];
116
	return NULL;
117
}
118

119
static inline void oe_set_delta_child(struct packing_data *pack,
120
				      struct object_entry *e,
121
				      struct object_entry *delta)
122
{
123
	if (delta)
124
		e->delta_child_idx = (delta - pack->objects) + 1;
125
	else
126
		e->delta_child_idx = 0;
127
}
128

129
static inline void oe_set_delta_sibling(struct packing_data *pack,
130
					struct object_entry *e,
131
					struct object_entry *delta)
132
{
133
	if (delta)
134
		e->delta_sibling_idx = (delta - pack->objects) + 1;
135
	else
136
		e->delta_sibling_idx = 0;
137
}
138

139
static inline void oe_set_size(struct packing_data *pack,
140
			       struct object_entry *e,
141
			       unsigned long size)
142
{
143
	if (size < pack->oe_size_limit) {
144
		e->size_ = size;
145
		e->size_valid = 1;
146
	} else {
147
		e->size_valid = 0;
148
		if (oe_get_size_slow(pack, e) != size)
149
			BUG("'size' is supposed to be the object size!");
150
	}
151
}
152

153
static inline void oe_set_delta_size(struct packing_data *pack,
154
				     struct object_entry *e,
155
				     unsigned long size)
156
{
157
	if (size < pack->oe_delta_size_limit) {
158
		e->delta_size_ = size;
159
		e->delta_size_valid = 1;
160
	} else {
161
		packing_data_lock(pack);
162
		if (!pack->delta_size)
163
			ALLOC_ARRAY(pack->delta_size, pack->nr_alloc);
164
		packing_data_unlock(pack);
165

166
		pack->delta_size[e - pack->objects] = size;
167
		e->delta_size_valid = 0;
168
	}
169
}
170

171
#define IN_PACK(obj) oe_in_pack(&to_pack, obj)
172
#define SIZE(obj) oe_size(&to_pack, obj)
173
#define SET_SIZE(obj,size) oe_set_size(&to_pack, obj, size)
174
#define DELTA_SIZE(obj) oe_delta_size(&to_pack, obj)
175
#define DELTA(obj) oe_delta(&to_pack, obj)
176
#define DELTA_CHILD(obj) oe_delta_child(&to_pack, obj)
177
#define DELTA_SIBLING(obj) oe_delta_sibling(&to_pack, obj)
178
#define SET_DELTA(obj, val) oe_set_delta(&to_pack, obj, val)
179
#define SET_DELTA_EXT(obj, oid) oe_set_delta_ext(&to_pack, obj, oid)
180
#define SET_DELTA_SIZE(obj, val) oe_set_delta_size(&to_pack, obj, val)
181
#define SET_DELTA_CHILD(obj, val) oe_set_delta_child(&to_pack, obj, val)
182
#define SET_DELTA_SIBLING(obj, val) oe_set_delta_sibling(&to_pack, obj, val)
183

184
static const char *pack_usage[] = {
185
	N_("git pack-objects --stdout [<options>] [< <ref-list> | < <object-list>]"),
186
	N_("git pack-objects [<options>] <base-name> [< <ref-list> | < <object-list>]"),
187
	NULL
188
};
189

190
static struct pack_idx_entry **written_list;
191
static uint32_t nr_result, nr_written, nr_seen;
192
static struct bitmap_index *bitmap_git;
193
static uint32_t write_layer;
194

195
static int non_empty;
196
static int reuse_delta = 1, reuse_object = 1;
197
static int keep_unreachable, unpack_unreachable, include_tag;
198
static timestamp_t unpack_unreachable_expiration;
199
static int pack_loose_unreachable;
200
static int cruft;
201
static timestamp_t cruft_expiration;
202
static int local;
203
static int have_non_local_packs;
204
static int incremental;
205
static int ignore_packed_keep_on_disk;
206
static int ignore_packed_keep_in_core;
207
static int allow_ofs_delta;
208
static struct pack_idx_option pack_idx_opts;
209
static const char *base_name;
210
static int progress = 1;
211
static int window = 10;
212
static unsigned long pack_size_limit;
213
static int depth = 50;
214
static int delta_search_threads;
215
static int pack_to_stdout;
216
static int sparse;
217
static int thin;
218
static int num_preferred_base;
219
static struct progress *progress_state;
220

221
static struct bitmapped_pack *reuse_packfiles;
222
static size_t reuse_packfiles_nr;
223
static size_t reuse_packfiles_used_nr;
224
static uint32_t reuse_packfile_objects;
225
static struct bitmap *reuse_packfile_bitmap;
226

227
static int use_bitmap_index_default = 1;
228
static int use_bitmap_index = -1;
229
static enum {
230
	NO_PACK_REUSE = 0,
231
	SINGLE_PACK_REUSE,
232
	MULTI_PACK_REUSE,
233
} allow_pack_reuse = SINGLE_PACK_REUSE;
234
static enum {
235
	WRITE_BITMAP_FALSE = 0,
236
	WRITE_BITMAP_QUIET,
237
	WRITE_BITMAP_TRUE,
238
} write_bitmap_index;
239
static uint16_t write_bitmap_options = BITMAP_OPT_HASH_CACHE;
240

241
static int exclude_promisor_objects;
242

243
static int use_delta_islands;
244

245
static unsigned long delta_cache_size = 0;
246
static unsigned long max_delta_cache_size = DEFAULT_DELTA_CACHE_SIZE;
247
static unsigned long cache_max_small_delta_size = 1000;
248

249
static unsigned long window_memory_limit = 0;
250

251
static struct string_list uri_protocols = STRING_LIST_INIT_NODUP;
252

253
enum missing_action {
254
	MA_ERROR = 0,      /* fail if any missing objects are encountered */
255
	MA_ALLOW_ANY,      /* silently allow ALL missing objects */
256
	MA_ALLOW_PROMISOR, /* silently allow all missing PROMISOR objects */
257
};
258
static enum missing_action arg_missing_action;
259
static show_object_fn fn_show_object;
260

261
struct configured_exclusion {
262
	struct oidmap_entry e;
263
	char *pack_hash_hex;
264
	char *uri;
265
};
266
static struct oidmap configured_exclusions;
267

268
static struct oidset excluded_by_config;
269

270
/*
271
 * stats
272
 */
273
static uint32_t written, written_delta;
274
static uint32_t reused, reused_delta;
275

276
/*
277
 * Indexed commits
278
 */
279
static struct commit **indexed_commits;
280
static unsigned int indexed_commits_nr;
281
static unsigned int indexed_commits_alloc;
282

283
static void index_commit_for_bitmap(struct commit *commit)
284
{
285
	if (indexed_commits_nr >= indexed_commits_alloc) {
286
		indexed_commits_alloc = (indexed_commits_alloc + 32) * 2;
287
		REALLOC_ARRAY(indexed_commits, indexed_commits_alloc);
288
	}
289

290
	indexed_commits[indexed_commits_nr++] = commit;
291
}
292

293
static void *get_delta(struct object_entry *entry)
294
{
295
	unsigned long size, base_size, delta_size;
296
	void *buf, *base_buf, *delta_buf;
297
	enum object_type type;
298

299
	buf = repo_read_object_file(the_repository, &entry->idx.oid, &type,
300
				    &size);
301
	if (!buf)
302
		die(_("unable to read %s"), oid_to_hex(&entry->idx.oid));
303
	base_buf = repo_read_object_file(the_repository,
304
					 &DELTA(entry)->idx.oid, &type,
305
					 &base_size);
306
	if (!base_buf)
307
		die("unable to read %s",
308
		    oid_to_hex(&DELTA(entry)->idx.oid));
309
	delta_buf = diff_delta(base_buf, base_size,
310
			       buf, size, &delta_size, 0);
311
	/*
312
	 * We successfully computed this delta once but dropped it for
313
	 * memory reasons. Something is very wrong if this time we
314
	 * recompute and create a different delta.
315
	 */
316
	if (!delta_buf || delta_size != DELTA_SIZE(entry))
317
		BUG("delta size changed");
318
	free(buf);
319
	free(base_buf);
320
	return delta_buf;
321
}
322

323
static unsigned long do_compress(void **pptr, unsigned long size)
324
{
325
	git_zstream stream;
326
	void *in, *out;
327
	unsigned long maxsize;
328

329
	git_deflate_init(&stream, pack_compression_level);
330
	maxsize = git_deflate_bound(&stream, size);
331

332
	in = *pptr;
333
	out = xmalloc(maxsize);
334
	*pptr = out;
335

336
	stream.next_in = in;
337
	stream.avail_in = size;
338
	stream.next_out = out;
339
	stream.avail_out = maxsize;
340
	while (git_deflate(&stream, Z_FINISH) == Z_OK)
341
		; /* nothing */
342
	git_deflate_end(&stream);
343

344
	free(in);
345
	return stream.total_out;
346
}
347

348
static unsigned long write_large_blob_data(struct git_istream *st, struct hashfile *f,
349
					   const struct object_id *oid)
350
{
351
	git_zstream stream;
352
	unsigned char ibuf[1024 * 16];
353
	unsigned char obuf[1024 * 16];
354
	unsigned long olen = 0;
355

356
	git_deflate_init(&stream, pack_compression_level);
357

358
	for (;;) {
359
		ssize_t readlen;
360
		int zret = Z_OK;
361
		readlen = read_istream(st, ibuf, sizeof(ibuf));
362
		if (readlen == -1)
363
			die(_("unable to read %s"), oid_to_hex(oid));
364

365
		stream.next_in = ibuf;
366
		stream.avail_in = readlen;
367
		while ((stream.avail_in || readlen == 0) &&
368
		       (zret == Z_OK || zret == Z_BUF_ERROR)) {
369
			stream.next_out = obuf;
370
			stream.avail_out = sizeof(obuf);
371
			zret = git_deflate(&stream, readlen ? 0 : Z_FINISH);
372
			hashwrite(f, obuf, stream.next_out - obuf);
373
			olen += stream.next_out - obuf;
374
		}
375
		if (stream.avail_in)
376
			die(_("deflate error (%d)"), zret);
377
		if (readlen == 0) {
378
			if (zret != Z_STREAM_END)
379
				die(_("deflate error (%d)"), zret);
380
			break;
381
		}
382
	}
383
	git_deflate_end(&stream);
384
	return olen;
385
}
386

387
/*
388
 * we are going to reuse the existing object data as is.  make
389
 * sure it is not corrupt.
390
 */
391
static int check_pack_inflate(struct packed_git *p,
392
		struct pack_window **w_curs,
393
		off_t offset,
394
		off_t len,
395
		unsigned long expect)
396
{
397
	git_zstream stream;
398
	unsigned char fakebuf[4096], *in;
399
	int st;
400

401
	memset(&stream, 0, sizeof(stream));
402
	git_inflate_init(&stream);
403
	do {
404
		in = use_pack(p, w_curs, offset, &stream.avail_in);
405
		stream.next_in = in;
406
		stream.next_out = fakebuf;
407
		stream.avail_out = sizeof(fakebuf);
408
		st = git_inflate(&stream, Z_FINISH);
409
		offset += stream.next_in - in;
410
	} while (st == Z_OK || st == Z_BUF_ERROR);
411
	git_inflate_end(&stream);
412
	return (st == Z_STREAM_END &&
413
		stream.total_out == expect &&
414
		stream.total_in == len) ? 0 : -1;
415
}
416

417
static void copy_pack_data(struct hashfile *f,
418
		struct packed_git *p,
419
		struct pack_window **w_curs,
420
		off_t offset,
421
		off_t len)
422
{
423
	unsigned char *in;
424
	unsigned long avail;
425

426
	while (len) {
427
		in = use_pack(p, w_curs, offset, &avail);
428
		if (avail > len)
429
			avail = (unsigned long)len;
430
		hashwrite(f, in, avail);
431
		offset += avail;
432
		len -= avail;
433
	}
434
}
435

436
static inline int oe_size_greater_than(struct packing_data *pack,
437
				       const struct object_entry *lhs,
438
				       unsigned long rhs)
439
{
440
	if (lhs->size_valid)
441
		return lhs->size_ > rhs;
442
	if (rhs < pack->oe_size_limit) /* rhs < 2^x <= lhs ? */
443
		return 1;
444
	return oe_get_size_slow(pack, lhs) > rhs;
445
}
446

447
/* Return 0 if we will bust the pack-size limit */
448
static unsigned long write_no_reuse_object(struct hashfile *f, struct object_entry *entry,
449
					   unsigned long limit, int usable_delta)
450
{
451
	unsigned long size, datalen;
452
	unsigned char header[MAX_PACK_OBJECT_HEADER],
453
		      dheader[MAX_PACK_OBJECT_HEADER];
454
	unsigned hdrlen;
455
	enum object_type type;
456
	void *buf;
457
	struct git_istream *st = NULL;
458
	const unsigned hashsz = the_hash_algo->rawsz;
459

460
	if (!usable_delta) {
461
		if (oe_type(entry) == OBJ_BLOB &&
462
		    oe_size_greater_than(&to_pack, entry, big_file_threshold) &&
463
		    (st = open_istream(the_repository, &entry->idx.oid, &type,
464
				       &size, NULL)) != NULL)
465
			buf = NULL;
466
		else {
467
			buf = repo_read_object_file(the_repository,
468
						    &entry->idx.oid, &type,
469
						    &size);
470
			if (!buf)
471
				die(_("unable to read %s"),
472
				    oid_to_hex(&entry->idx.oid));
473
		}
474
		/*
475
		 * make sure no cached delta data remains from a
476
		 * previous attempt before a pack split occurred.
477
		 */
478
		FREE_AND_NULL(entry->delta_data);
479
		entry->z_delta_size = 0;
480
	} else if (entry->delta_data) {
481
		size = DELTA_SIZE(entry);
482
		buf = entry->delta_data;
483
		entry->delta_data = NULL;
484
		type = (allow_ofs_delta && DELTA(entry)->idx.offset) ?
485
			OBJ_OFS_DELTA : OBJ_REF_DELTA;
486
	} else {
487
		buf = get_delta(entry);
488
		size = DELTA_SIZE(entry);
489
		type = (allow_ofs_delta && DELTA(entry)->idx.offset) ?
490
			OBJ_OFS_DELTA : OBJ_REF_DELTA;
491
	}
492

493
	if (st)	/* large blob case, just assume we don't compress well */
494
		datalen = size;
495
	else if (entry->z_delta_size)
496
		datalen = entry->z_delta_size;
497
	else
498
		datalen = do_compress(&buf, size);
499

500
	/*
501
	 * The object header is a byte of 'type' followed by zero or
502
	 * more bytes of length.
503
	 */
504
	hdrlen = encode_in_pack_object_header(header, sizeof(header),
505
					      type, size);
506

507
	if (type == OBJ_OFS_DELTA) {
508
		/*
509
		 * Deltas with relative base contain an additional
510
		 * encoding of the relative offset for the delta
511
		 * base from this object's position in the pack.
512
		 */
513
		off_t ofs = entry->idx.offset - DELTA(entry)->idx.offset;
514
		unsigned pos = sizeof(dheader) - 1;
515
		dheader[pos] = ofs & 127;
516
		while (ofs >>= 7)
517
			dheader[--pos] = 128 | (--ofs & 127);
518
		if (limit && hdrlen + sizeof(dheader) - pos + datalen + hashsz >= limit) {
519
			if (st)
520
				close_istream(st);
521
			free(buf);
522
			return 0;
523
		}
524
		hashwrite(f, header, hdrlen);
525
		hashwrite(f, dheader + pos, sizeof(dheader) - pos);
526
		hdrlen += sizeof(dheader) - pos;
527
	} else if (type == OBJ_REF_DELTA) {
528
		/*
529
		 * Deltas with a base reference contain
530
		 * additional bytes for the base object ID.
531
		 */
532
		if (limit && hdrlen + hashsz + datalen + hashsz >= limit) {
533
			if (st)
534
				close_istream(st);
535
			free(buf);
536
			return 0;
537
		}
538
		hashwrite(f, header, hdrlen);
539
		hashwrite(f, DELTA(entry)->idx.oid.hash, hashsz);
540
		hdrlen += hashsz;
541
	} else {
542
		if (limit && hdrlen + datalen + hashsz >= limit) {
543
			if (st)
544
				close_istream(st);
545
			free(buf);
546
			return 0;
547
		}
548
		hashwrite(f, header, hdrlen);
549
	}
550
	if (st) {
551
		datalen = write_large_blob_data(st, f, &entry->idx.oid);
552
		close_istream(st);
553
	} else {
554
		hashwrite(f, buf, datalen);
555
		free(buf);
556
	}
557

558
	return hdrlen + datalen;
559
}
560

561
/* Return 0 if we will bust the pack-size limit */
562
static off_t write_reuse_object(struct hashfile *f, struct object_entry *entry,
563
				unsigned long limit, int usable_delta)
564
{
565
	struct packed_git *p = IN_PACK(entry);
566
	struct pack_window *w_curs = NULL;
567
	uint32_t pos;
568
	off_t offset;
569
	enum object_type type = oe_type(entry);
570
	off_t datalen;
571
	unsigned char header[MAX_PACK_OBJECT_HEADER],
572
		      dheader[MAX_PACK_OBJECT_HEADER];
573
	unsigned hdrlen;
574
	const unsigned hashsz = the_hash_algo->rawsz;
575
	unsigned long entry_size = SIZE(entry);
576

577
	if (DELTA(entry))
578
		type = (allow_ofs_delta && DELTA(entry)->idx.offset) ?
579
			OBJ_OFS_DELTA : OBJ_REF_DELTA;
580
	hdrlen = encode_in_pack_object_header(header, sizeof(header),
581
					      type, entry_size);
582

583
	offset = entry->in_pack_offset;
584
	if (offset_to_pack_pos(p, offset, &pos) < 0)
585
		die(_("write_reuse_object: could not locate %s, expected at "
586
		      "offset %"PRIuMAX" in pack %s"),
587
		    oid_to_hex(&entry->idx.oid), (uintmax_t)offset,
588
		    p->pack_name);
589
	datalen = pack_pos_to_offset(p, pos + 1) - offset;
590
	if (!pack_to_stdout && p->index_version > 1 &&
591
	    check_pack_crc(p, &w_curs, offset, datalen,
592
			   pack_pos_to_index(p, pos))) {
593
		error(_("bad packed object CRC for %s"),
594
		      oid_to_hex(&entry->idx.oid));
595
		unuse_pack(&w_curs);
596
		return write_no_reuse_object(f, entry, limit, usable_delta);
597
	}
598

599
	offset += entry->in_pack_header_size;
600
	datalen -= entry->in_pack_header_size;
601

602
	if (!pack_to_stdout && p->index_version == 1 &&
603
	    check_pack_inflate(p, &w_curs, offset, datalen, entry_size)) {
604
		error(_("corrupt packed object for %s"),
605
		      oid_to_hex(&entry->idx.oid));
606
		unuse_pack(&w_curs);
607
		return write_no_reuse_object(f, entry, limit, usable_delta);
608
	}
609

610
	if (type == OBJ_OFS_DELTA) {
611
		off_t ofs = entry->idx.offset - DELTA(entry)->idx.offset;
612
		unsigned pos = sizeof(dheader) - 1;
613
		dheader[pos] = ofs & 127;
614
		while (ofs >>= 7)
615
			dheader[--pos] = 128 | (--ofs & 127);
616
		if (limit && hdrlen + sizeof(dheader) - pos + datalen + hashsz >= limit) {
617
			unuse_pack(&w_curs);
618
			return 0;
619
		}
620
		hashwrite(f, header, hdrlen);
621
		hashwrite(f, dheader + pos, sizeof(dheader) - pos);
622
		hdrlen += sizeof(dheader) - pos;
623
		reused_delta++;
624
	} else if (type == OBJ_REF_DELTA) {
625
		if (limit && hdrlen + hashsz + datalen + hashsz >= limit) {
626
			unuse_pack(&w_curs);
627
			return 0;
628
		}
629
		hashwrite(f, header, hdrlen);
630
		hashwrite(f, DELTA(entry)->idx.oid.hash, hashsz);
631
		hdrlen += hashsz;
632
		reused_delta++;
633
	} else {
634
		if (limit && hdrlen + datalen + hashsz >= limit) {
635
			unuse_pack(&w_curs);
636
			return 0;
637
		}
638
		hashwrite(f, header, hdrlen);
639
	}
640
	copy_pack_data(f, p, &w_curs, offset, datalen);
641
	unuse_pack(&w_curs);
642
	reused++;
643
	return hdrlen + datalen;
644
}
645

646
/* Return 0 if we will bust the pack-size limit */
647
static off_t write_object(struct hashfile *f,
648
			  struct object_entry *entry,
649
			  off_t write_offset)
650
{
651
	unsigned long limit;
652
	off_t len;
653
	int usable_delta, to_reuse;
654

655
	if (!pack_to_stdout)
656
		crc32_begin(f);
657

658
	/* apply size limit if limited packsize and not first object */
659
	if (!pack_size_limit || !nr_written)
660
		limit = 0;
661
	else if (pack_size_limit <= write_offset)
662
		/*
663
		 * the earlier object did not fit the limit; avoid
664
		 * mistaking this with unlimited (i.e. limit = 0).
665
		 */
666
		limit = 1;
667
	else
668
		limit = pack_size_limit - write_offset;
669

670
	if (!DELTA(entry))
671
		usable_delta = 0;	/* no delta */
672
	else if (!pack_size_limit)
673
	       usable_delta = 1;	/* unlimited packfile */
674
	else if (DELTA(entry)->idx.offset == (off_t)-1)
675
		usable_delta = 0;	/* base was written to another pack */
676
	else if (DELTA(entry)->idx.offset)
677
		usable_delta = 1;	/* base already exists in this pack */
678
	else
679
		usable_delta = 0;	/* base could end up in another pack */
680

681
	if (!reuse_object)
682
		to_reuse = 0;	/* explicit */
683
	else if (!IN_PACK(entry))
684
		to_reuse = 0;	/* can't reuse what we don't have */
685
	else if (oe_type(entry) == OBJ_REF_DELTA ||
686
		 oe_type(entry) == OBJ_OFS_DELTA)
687
				/* check_object() decided it for us ... */
688
		to_reuse = usable_delta;
689
				/* ... but pack split may override that */
690
	else if (oe_type(entry) != entry->in_pack_type)
691
		to_reuse = 0;	/* pack has delta which is unusable */
692
	else if (DELTA(entry))
693
		to_reuse = 0;	/* we want to pack afresh */
694
	else
695
		to_reuse = 1;	/* we have it in-pack undeltified,
696
				 * and we do not need to deltify it.
697
				 */
698

699
	if (!to_reuse)
700
		len = write_no_reuse_object(f, entry, limit, usable_delta);
701
	else
702
		len = write_reuse_object(f, entry, limit, usable_delta);
703
	if (!len)
704
		return 0;
705

706
	if (usable_delta)
707
		written_delta++;
708
	written++;
709
	if (!pack_to_stdout)
710
		entry->idx.crc32 = crc32_end(f);
711
	return len;
712
}
713

714
enum write_one_status {
715
	WRITE_ONE_SKIP = -1, /* already written */
716
	WRITE_ONE_BREAK = 0, /* writing this will bust the limit; not written */
717
	WRITE_ONE_WRITTEN = 1, /* normal */
718
	WRITE_ONE_RECURSIVE = 2 /* already scheduled to be written */
719
};
720

721
static enum write_one_status write_one(struct hashfile *f,
722
				       struct object_entry *e,
723
				       off_t *offset)
724
{
725
	off_t size;
726
	int recursing;
727

728
	/*
729
	 * we set offset to 1 (which is an impossible value) to mark
730
	 * the fact that this object is involved in "write its base
731
	 * first before writing a deltified object" recursion.
732
	 */
733
	recursing = (e->idx.offset == 1);
734
	if (recursing) {
735
		warning(_("recursive delta detected for object %s"),
736
			oid_to_hex(&e->idx.oid));
737
		return WRITE_ONE_RECURSIVE;
738
	} else if (e->idx.offset || e->preferred_base) {
739
		/* offset is non zero if object is written already. */
740
		return WRITE_ONE_SKIP;
741
	}
742

743
	/* if we are deltified, write out base object first. */
744
	if (DELTA(e)) {
745
		e->idx.offset = 1; /* now recurse */
746
		switch (write_one(f, DELTA(e), offset)) {
747
		case WRITE_ONE_RECURSIVE:
748
			/* we cannot depend on this one */
749
			SET_DELTA(e, NULL);
750
			break;
751
		default:
752
			break;
753
		case WRITE_ONE_BREAK:
754
			e->idx.offset = recursing;
755
			return WRITE_ONE_BREAK;
756
		}
757
	}
758

759
	e->idx.offset = *offset;
760
	size = write_object(f, e, *offset);
761
	if (!size) {
762
		e->idx.offset = recursing;
763
		return WRITE_ONE_BREAK;
764
	}
765
	written_list[nr_written++] = &e->idx;
766

767
	/* make sure off_t is sufficiently large not to wrap */
768
	if (signed_add_overflows(*offset, size))
769
		die(_("pack too large for current definition of off_t"));
770
	*offset += size;
771
	return WRITE_ONE_WRITTEN;
772
}
773

774
static int mark_tagged(const char *path UNUSED, const char *referent UNUSED, const struct object_id *oid,
775
		       int flag UNUSED, void *cb_data UNUSED)
776
{
777
	struct object_id peeled;
778
	struct object_entry *entry = packlist_find(&to_pack, oid);
779

780
	if (entry)
781
		entry->tagged = 1;
782
	if (!peel_iterated_oid(the_repository, oid, &peeled)) {
783
		entry = packlist_find(&to_pack, &peeled);
784
		if (entry)
785
			entry->tagged = 1;
786
	}
787
	return 0;
788
}
789

790
static inline unsigned char oe_layer(struct packing_data *pack,
791
				     struct object_entry *e)
792
{
793
	if (!pack->layer)
794
		return 0;
795
	return pack->layer[e - pack->objects];
796
}
797

798
static inline void add_to_write_order(struct object_entry **wo,
799
			       unsigned int *endp,
800
			       struct object_entry *e)
801
{
802
	if (e->filled || oe_layer(&to_pack, e) != write_layer)
803
		return;
804
	wo[(*endp)++] = e;
805
	e->filled = 1;
806
}
807

808
static void add_descendants_to_write_order(struct object_entry **wo,
809
					   unsigned int *endp,
810
					   struct object_entry *e)
811
{
812
	int add_to_order = 1;
813
	while (e) {
814
		if (add_to_order) {
815
			struct object_entry *s;
816
			/* add this node... */
817
			add_to_write_order(wo, endp, e);
818
			/* all its siblings... */
819
			for (s = DELTA_SIBLING(e); s; s = DELTA_SIBLING(s)) {
820
				add_to_write_order(wo, endp, s);
821
			}
822
		}
823
		/* drop down a level to add left subtree nodes if possible */
824
		if (DELTA_CHILD(e)) {
825
			add_to_order = 1;
826
			e = DELTA_CHILD(e);
827
		} else {
828
			add_to_order = 0;
829
			/* our sibling might have some children, it is next */
830
			if (DELTA_SIBLING(e)) {
831
				e = DELTA_SIBLING(e);
832
				continue;
833
			}
834
			/* go back to our parent node */
835
			e = DELTA(e);
836
			while (e && !DELTA_SIBLING(e)) {
837
				/* we're on the right side of a subtree, keep
838
				 * going up until we can go right again */
839
				e = DELTA(e);
840
			}
841
			if (!e) {
842
				/* done- we hit our original root node */
843
				return;
844
			}
845
			/* pass it off to sibling at this level */
846
			e = DELTA_SIBLING(e);
847
		}
848
	};
849
}
850

851
static void add_family_to_write_order(struct object_entry **wo,
852
				      unsigned int *endp,
853
				      struct object_entry *e)
854
{
855
	struct object_entry *root;
856

857
	for (root = e; DELTA(root); root = DELTA(root))
858
		; /* nothing */
859
	add_descendants_to_write_order(wo, endp, root);
860
}
861

862
static void compute_layer_order(struct object_entry **wo, unsigned int *wo_end)
863
{
864
	unsigned int i, last_untagged;
865
	struct object_entry *objects = to_pack.objects;
866

867
	for (i = 0; i < to_pack.nr_objects; i++) {
868
		if (objects[i].tagged)
869
			break;
870
		add_to_write_order(wo, wo_end, &objects[i]);
871
	}
872
	last_untagged = i;
873

874
	/*
875
	 * Then fill all the tagged tips.
876
	 */
877
	for (; i < to_pack.nr_objects; i++) {
878
		if (objects[i].tagged)
879
			add_to_write_order(wo, wo_end, &objects[i]);
880
	}
881

882
	/*
883
	 * And then all remaining commits and tags.
884
	 */
885
	for (i = last_untagged; i < to_pack.nr_objects; i++) {
886
		if (oe_type(&objects[i]) != OBJ_COMMIT &&
887
		    oe_type(&objects[i]) != OBJ_TAG)
888
			continue;
889
		add_to_write_order(wo, wo_end, &objects[i]);
890
	}
891

892
	/*
893
	 * And then all the trees.
894
	 */
895
	for (i = last_untagged; i < to_pack.nr_objects; i++) {
896
		if (oe_type(&objects[i]) != OBJ_TREE)
897
			continue;
898
		add_to_write_order(wo, wo_end, &objects[i]);
899
	}
900

901
	/*
902
	 * Finally all the rest in really tight order
903
	 */
904
	for (i = last_untagged; i < to_pack.nr_objects; i++) {
905
		if (!objects[i].filled && oe_layer(&to_pack, &objects[i]) == write_layer)
906
			add_family_to_write_order(wo, wo_end, &objects[i]);
907
	}
908
}
909

910
static struct object_entry **compute_write_order(void)
911
{
912
	uint32_t max_layers = 1;
913
	unsigned int i, wo_end;
914

915
	struct object_entry **wo;
916
	struct object_entry *objects = to_pack.objects;
917

918
	for (i = 0; i < to_pack.nr_objects; i++) {
919
		objects[i].tagged = 0;
920
		objects[i].filled = 0;
921
		SET_DELTA_CHILD(&objects[i], NULL);
922
		SET_DELTA_SIBLING(&objects[i], NULL);
923
	}
924

925
	/*
926
	 * Fully connect delta_child/delta_sibling network.
927
	 * Make sure delta_sibling is sorted in the original
928
	 * recency order.
929
	 */
930
	for (i = to_pack.nr_objects; i > 0;) {
931
		struct object_entry *e = &objects[--i];
932
		if (!DELTA(e))
933
			continue;
934
		/* Mark me as the first child */
935
		e->delta_sibling_idx = DELTA(e)->delta_child_idx;
936
		SET_DELTA_CHILD(DELTA(e), e);
937
	}
938

939
	/*
940
	 * Mark objects that are at the tip of tags.
941
	 */
942
	refs_for_each_tag_ref(get_main_ref_store(the_repository), mark_tagged,
943
			      NULL);
944

945
	if (use_delta_islands) {
946
		max_layers = compute_pack_layers(&to_pack);
947
		free_island_marks();
948
	}
949

950
	ALLOC_ARRAY(wo, to_pack.nr_objects);
951
	wo_end = 0;
952

953
	for (; write_layer < max_layers; ++write_layer)
954
		compute_layer_order(wo, &wo_end);
955

956
	if (wo_end != to_pack.nr_objects)
957
		die(_("ordered %u objects, expected %"PRIu32),
958
		    wo_end, to_pack.nr_objects);
959

960
	return wo;
961
}
962

963

964
/*
965
 * A reused set of objects. All objects in a chunk have the same
966
 * relative position in the original packfile and the generated
967
 * packfile.
968
 */
969

970
static struct reused_chunk {
971
	/* The offset of the first object of this chunk in the original
972
	 * packfile. */
973
	off_t original;
974
	/* The difference for "original" minus the offset of the first object of
975
	 * this chunk in the generated packfile. */
976
	off_t difference;
977
} *reused_chunks;
978
static int reused_chunks_nr;
979
static int reused_chunks_alloc;
980

981
static void record_reused_object(off_t where, off_t offset)
982
{
983
	if (reused_chunks_nr && reused_chunks[reused_chunks_nr-1].difference == offset)
984
		return;
985

986
	ALLOC_GROW(reused_chunks, reused_chunks_nr + 1,
987
		   reused_chunks_alloc);
988
	reused_chunks[reused_chunks_nr].original = where;
989
	reused_chunks[reused_chunks_nr].difference = offset;
990
	reused_chunks_nr++;
991
}
992

993
/*
994
 * Binary search to find the chunk that "where" is in. Note
995
 * that we're not looking for an exact match, just the first
996
 * chunk that contains it (which implicitly ends at the start
997
 * of the next chunk.
998
 */
999
static off_t find_reused_offset(off_t where)
1000
{
1001
	int lo = 0, hi = reused_chunks_nr;
1002
	while (lo < hi) {
1003
		int mi = lo + ((hi - lo) / 2);
1004
		if (where == reused_chunks[mi].original)
1005
			return reused_chunks[mi].difference;
1006
		if (where < reused_chunks[mi].original)
1007
			hi = mi;
1008
		else
1009
			lo = mi + 1;
1010
	}
1011

1012
	/*
1013
	 * The first chunk starts at zero, so we can't have gone below
1014
	 * there.
1015
	 */
1016
	assert(lo);
1017
	return reused_chunks[lo-1].difference;
1018
}
1019

1020
static void write_reused_pack_one(struct packed_git *reuse_packfile,
1021
				  size_t pos, struct hashfile *out,
1022
				  off_t pack_start,
1023
				  struct pack_window **w_curs)
1024
{
1025
	off_t offset, next, cur;
1026
	enum object_type type;
1027
	unsigned long size;
1028

1029
	offset = pack_pos_to_offset(reuse_packfile, pos);
1030
	next = pack_pos_to_offset(reuse_packfile, pos + 1);
1031

1032
	record_reused_object(offset,
1033
			     offset - (hashfile_total(out) - pack_start));
1034

1035
	cur = offset;
1036
	type = unpack_object_header(reuse_packfile, w_curs, &cur, &size);
1037
	assert(type >= 0);
1038

1039
	if (type == OBJ_OFS_DELTA) {
1040
		off_t base_offset;
1041
		off_t fixup;
1042

1043
		unsigned char header[MAX_PACK_OBJECT_HEADER];
1044
		unsigned len;
1045

1046
		base_offset = get_delta_base(reuse_packfile, w_curs, &cur, type, offset);
1047
		assert(base_offset != 0);
1048

1049
		/* Convert to REF_DELTA if we must... */
1050
		if (!allow_ofs_delta) {
1051
			uint32_t base_pos;
1052
			struct object_id base_oid;
1053

1054
			if (offset_to_pack_pos(reuse_packfile, base_offset, &base_pos) < 0)
1055
				die(_("expected object at offset %"PRIuMAX" "
1056
				      "in pack %s"),
1057
				    (uintmax_t)base_offset,
1058
				    reuse_packfile->pack_name);
1059

1060
			nth_packed_object_id(&base_oid, reuse_packfile,
1061
					     pack_pos_to_index(reuse_packfile, base_pos));
1062

1063
			len = encode_in_pack_object_header(header, sizeof(header),
1064
							   OBJ_REF_DELTA, size);
1065
			hashwrite(out, header, len);
1066
			hashwrite(out, base_oid.hash, the_hash_algo->rawsz);
1067
			copy_pack_data(out, reuse_packfile, w_curs, cur, next - cur);
1068
			return;
1069
		}
1070

1071
		/* Otherwise see if we need to rewrite the offset... */
1072
		fixup = find_reused_offset(offset) -
1073
			find_reused_offset(base_offset);
1074
		if (fixup) {
1075
			unsigned char ofs_header[10];
1076
			unsigned i, ofs_len;
1077
			off_t ofs = offset - base_offset - fixup;
1078

1079
			len = encode_in_pack_object_header(header, sizeof(header),
1080
							   OBJ_OFS_DELTA, size);
1081

1082
			i = sizeof(ofs_header) - 1;
1083
			ofs_header[i] = ofs & 127;
1084
			while (ofs >>= 7)
1085
				ofs_header[--i] = 128 | (--ofs & 127);
1086

1087
			ofs_len = sizeof(ofs_header) - i;
1088

1089
			hashwrite(out, header, len);
1090
			hashwrite(out, ofs_header + sizeof(ofs_header) - ofs_len, ofs_len);
1091
			copy_pack_data(out, reuse_packfile, w_curs, cur, next - cur);
1092
			return;
1093
		}
1094

1095
		/* ...otherwise we have no fixup, and can write it verbatim */
1096
	}
1097

1098
	copy_pack_data(out, reuse_packfile, w_curs, offset, next - offset);
1099
}
1100

1101
static size_t write_reused_pack_verbatim(struct bitmapped_pack *reuse_packfile,
1102
					 struct hashfile *out,
1103
					 off_t pack_start,
1104
					 struct pack_window **w_curs)
1105
{
1106
	size_t pos = reuse_packfile->bitmap_pos;
1107
	size_t end;
1108

1109
	if (pos % BITS_IN_EWORD) {
1110
		size_t word_pos = (pos / BITS_IN_EWORD);
1111
		size_t offset = pos % BITS_IN_EWORD;
1112
		size_t last;
1113
		eword_t word = reuse_packfile_bitmap->words[word_pos];
1114

1115
		if (offset + reuse_packfile->bitmap_nr < BITS_IN_EWORD)
1116
			last = offset + reuse_packfile->bitmap_nr;
1117
		else
1118
			last = BITS_IN_EWORD;
1119

1120
		for (; offset < last; offset++) {
1121
			if (word >> offset == 0)
1122
				return word_pos;
1123
			if (!bitmap_get(reuse_packfile_bitmap,
1124
					word_pos * BITS_IN_EWORD + offset))
1125
				return word_pos;
1126
		}
1127

1128
		pos += BITS_IN_EWORD - (pos % BITS_IN_EWORD);
1129
	}
1130

1131
	/*
1132
	 * Now we're going to copy as many whole eword_t's as possible.
1133
	 * "end" is the index of the last whole eword_t we copy, but
1134
	 * there may be additional bits to process. Those are handled
1135
	 * individually by write_reused_pack().
1136
	 *
1137
	 * Begin by advancing to the first word boundary in range of the
1138
	 * bit positions occupied by objects in "reuse_packfile". Then
1139
	 * pick the last word boundary in the same range. If we have at
1140
	 * least one word's worth of bits to process, continue on.
1141
	 */
1142
	end = reuse_packfile->bitmap_pos + reuse_packfile->bitmap_nr;
1143
	if (end % BITS_IN_EWORD)
1144
		end -= end % BITS_IN_EWORD;
1145
	if (pos >= end)
1146
		return reuse_packfile->bitmap_pos / BITS_IN_EWORD;
1147

1148
	while (pos < end &&
1149
	       reuse_packfile_bitmap->words[pos / BITS_IN_EWORD] == (eword_t)~0)
1150
		pos += BITS_IN_EWORD;
1151

1152
	if (pos > end)
1153
		pos = end;
1154

1155
	if (reuse_packfile->bitmap_pos < pos) {
1156
		off_t pack_start_off = pack_pos_to_offset(reuse_packfile->p, 0);
1157
		off_t pack_end_off = pack_pos_to_offset(reuse_packfile->p,
1158
							pos - reuse_packfile->bitmap_pos);
1159

1160
		written += pos - reuse_packfile->bitmap_pos;
1161

1162
		/* We're recording one chunk, not one object. */
1163
		record_reused_object(pack_start_off,
1164
				     pack_start_off - (hashfile_total(out) - pack_start));
1165
		hashflush(out);
1166
		copy_pack_data(out, reuse_packfile->p, w_curs,
1167
			pack_start_off, pack_end_off - pack_start_off);
1168

1169
		display_progress(progress_state, written);
1170
	}
1171
	if (pos % BITS_IN_EWORD)
1172
		BUG("attempted to jump past a word boundary to %"PRIuMAX,
1173
		    (uintmax_t)pos);
1174
	return pos / BITS_IN_EWORD;
1175
}
1176

1177
static void write_reused_pack(struct bitmapped_pack *reuse_packfile,
1178
			      struct hashfile *f)
1179
{
1180
	size_t i = reuse_packfile->bitmap_pos / BITS_IN_EWORD;
1181
	uint32_t offset;
1182
	off_t pack_start = hashfile_total(f) - sizeof(struct pack_header);
1183
	struct pack_window *w_curs = NULL;
1184

1185
	if (allow_ofs_delta)
1186
		i = write_reused_pack_verbatim(reuse_packfile, f, pack_start,
1187
					       &w_curs);
1188

1189
	for (; i < reuse_packfile_bitmap->word_alloc; ++i) {
1190
		eword_t word = reuse_packfile_bitmap->words[i];
1191
		size_t pos = (i * BITS_IN_EWORD);
1192

1193
		for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
1194
			if ((word >> offset) == 0)
1195
				break;
1196

1197
			offset += ewah_bit_ctz64(word >> offset);
1198
			if (pos + offset < reuse_packfile->bitmap_pos)
1199
				continue;
1200
			if (pos + offset >= reuse_packfile->bitmap_pos + reuse_packfile->bitmap_nr)
1201
				goto done;
1202
			/*
1203
			 * Can use bit positions directly, even for MIDX
1204
			 * bitmaps. See comment in try_partial_reuse()
1205
			 * for why.
1206
			 */
1207
			write_reused_pack_one(reuse_packfile->p,
1208
					      pos + offset - reuse_packfile->bitmap_pos,
1209
					      f, pack_start, &w_curs);
1210
			display_progress(progress_state, ++written);
1211
		}
1212
	}
1213

1214
done:
1215
	unuse_pack(&w_curs);
1216
}
1217

1218
static void write_excluded_by_configs(void)
1219
{
1220
	struct oidset_iter iter;
1221
	const struct object_id *oid;
1222

1223
	oidset_iter_init(&excluded_by_config, &iter);
1224
	while ((oid = oidset_iter_next(&iter))) {
1225
		struct configured_exclusion *ex =
1226
			oidmap_get(&configured_exclusions, oid);
1227

1228
		if (!ex)
1229
			BUG("configured exclusion wasn't configured");
1230
		write_in_full(1, ex->pack_hash_hex, strlen(ex->pack_hash_hex));
1231
		write_in_full(1, " ", 1);
1232
		write_in_full(1, ex->uri, strlen(ex->uri));
1233
		write_in_full(1, "\n", 1);
1234
	}
1235
}
1236

1237
static const char no_split_warning[] = N_(
1238
"disabling bitmap writing, packs are split due to pack.packSizeLimit"
1239
);
1240

1241
static void write_pack_file(void)
1242
{
1243
	uint32_t i = 0, j;
1244
	struct hashfile *f;
1245
	off_t offset;
1246
	uint32_t nr_remaining = nr_result;
1247
	time_t last_mtime = 0;
1248
	struct object_entry **write_order;
1249

1250
	if (progress > pack_to_stdout)
1251
		progress_state = start_progress(_("Writing objects"), nr_result);
1252
	ALLOC_ARRAY(written_list, to_pack.nr_objects);
1253
	write_order = compute_write_order();
1254

1255
	do {
1256
		unsigned char hash[GIT_MAX_RAWSZ];
1257
		char *pack_tmp_name = NULL;
1258

1259
		if (pack_to_stdout)
1260
			f = hashfd_throughput(1, "<stdout>", progress_state);
1261
		else
1262
			f = create_tmp_packfile(&pack_tmp_name);
1263

1264
		offset = write_pack_header(f, nr_remaining);
1265

1266
		if (reuse_packfiles_nr) {
1267
			assert(pack_to_stdout);
1268
			for (j = 0; j < reuse_packfiles_nr; j++) {
1269
				reused_chunks_nr = 0;
1270
				write_reused_pack(&reuse_packfiles[j], f);
1271
				if (reused_chunks_nr)
1272
					reuse_packfiles_used_nr++;
1273
			}
1274
			offset = hashfile_total(f);
1275
		}
1276

1277
		nr_written = 0;
1278
		for (; i < to_pack.nr_objects; i++) {
1279
			struct object_entry *e = write_order[i];
1280
			if (write_one(f, e, &offset) == WRITE_ONE_BREAK)
1281
				break;
1282
			display_progress(progress_state, written);
1283
		}
1284

1285
		if (pack_to_stdout) {
1286
			/*
1287
			 * We never fsync when writing to stdout since we may
1288
			 * not be writing to an actual pack file. For instance,
1289
			 * the upload-pack code passes a pipe here. Calling
1290
			 * fsync on a pipe results in unnecessary
1291
			 * synchronization with the reader on some platforms.
1292
			 */
1293
			finalize_hashfile(f, hash, FSYNC_COMPONENT_NONE,
1294
					  CSUM_HASH_IN_STREAM | CSUM_CLOSE);
1295
		} else if (nr_written == nr_remaining) {
1296
			finalize_hashfile(f, hash, FSYNC_COMPONENT_PACK,
1297
					  CSUM_HASH_IN_STREAM | CSUM_FSYNC | CSUM_CLOSE);
1298
		} else {
1299
			/*
1300
			 * If we wrote the wrong number of entries in the
1301
			 * header, rewrite it like in fast-import.
1302
			 */
1303

1304
			int fd = finalize_hashfile(f, hash, FSYNC_COMPONENT_PACK, 0);
1305
			fixup_pack_header_footer(fd, hash, pack_tmp_name,
1306
						 nr_written, hash, offset);
1307
			close(fd);
1308
			if (write_bitmap_index) {
1309
				if (write_bitmap_index != WRITE_BITMAP_QUIET)
1310
					warning(_(no_split_warning));
1311
				write_bitmap_index = 0;
1312
			}
1313
		}
1314

1315
		if (!pack_to_stdout) {
1316
			struct stat st;
1317
			struct strbuf tmpname = STRBUF_INIT;
1318
			struct bitmap_writer bitmap_writer;
1319
			char *idx_tmp_name = NULL;
1320

1321
			/*
1322
			 * Packs are runtime accessed in their mtime
1323
			 * order since newer packs are more likely to contain
1324
			 * younger objects.  So if we are creating multiple
1325
			 * packs then we should modify the mtime of later ones
1326
			 * to preserve this property.
1327
			 */
1328
			if (stat(pack_tmp_name, &st) < 0) {
1329
				warning_errno(_("failed to stat %s"), pack_tmp_name);
1330
			} else if (!last_mtime) {
1331
				last_mtime = st.st_mtime;
1332
			} else {
1333
				struct utimbuf utb;
1334
				utb.actime = st.st_atime;
1335
				utb.modtime = --last_mtime;
1336
				if (utime(pack_tmp_name, &utb) < 0)
1337
					warning_errno(_("failed utime() on %s"), pack_tmp_name);
1338
			}
1339

1340
			strbuf_addf(&tmpname, "%s-%s.", base_name,
1341
				    hash_to_hex(hash));
1342

1343
			if (write_bitmap_index) {
1344
				bitmap_writer_init(&bitmap_writer,
1345
						   the_repository, &to_pack);
1346
				bitmap_writer_set_checksum(&bitmap_writer, hash);
1347
				bitmap_writer_build_type_index(&bitmap_writer,
1348
							       written_list);
1349
			}
1350

1351
			if (cruft)
1352
				pack_idx_opts.flags |= WRITE_MTIMES;
1353

1354
			stage_tmp_packfiles(&tmpname, pack_tmp_name,
1355
					    written_list, nr_written,
1356
					    &to_pack, &pack_idx_opts, hash,
1357
					    &idx_tmp_name);
1358

1359
			if (write_bitmap_index) {
1360
				size_t tmpname_len = tmpname.len;
1361

1362
				strbuf_addstr(&tmpname, "bitmap");
1363
				stop_progress(&progress_state);
1364

1365
				bitmap_writer_show_progress(&bitmap_writer,
1366
							    progress);
1367
				bitmap_writer_select_commits(&bitmap_writer,
1368
							     indexed_commits,
1369
							     indexed_commits_nr);
1370
				if (bitmap_writer_build(&bitmap_writer) < 0)
1371
					die(_("failed to write bitmap index"));
1372
				bitmap_writer_finish(&bitmap_writer,
1373
						     written_list,
1374
						     tmpname.buf, write_bitmap_options);
1375
				bitmap_writer_free(&bitmap_writer);
1376
				write_bitmap_index = 0;
1377
				strbuf_setlen(&tmpname, tmpname_len);
1378
			}
1379

1380
			rename_tmp_packfile_idx(&tmpname, &idx_tmp_name);
1381

1382
			free(idx_tmp_name);
1383
			strbuf_release(&tmpname);
1384
			free(pack_tmp_name);
1385
			puts(hash_to_hex(hash));
1386
		}
1387

1388
		/* mark written objects as written to previous pack */
1389
		for (j = 0; j < nr_written; j++) {
1390
			written_list[j]->offset = (off_t)-1;
1391
		}
1392
		nr_remaining -= nr_written;
1393
	} while (nr_remaining && i < to_pack.nr_objects);
1394

1395
	free(written_list);
1396
	free(write_order);
1397
	stop_progress(&progress_state);
1398
	if (written != nr_result)
1399
		die(_("wrote %"PRIu32" objects while expecting %"PRIu32),
1400
		    written, nr_result);
1401
	trace2_data_intmax("pack-objects", the_repository,
1402
			   "write_pack_file/wrote", nr_result);
1403
}
1404

1405
static int no_try_delta(const char *path)
1406
{
1407
	static struct attr_check *check;
1408

1409
	if (!check)
1410
		check = attr_check_initl("delta", NULL);
1411
	git_check_attr(the_repository->index, path, check);
1412
	if (ATTR_FALSE(check->items[0].value))
1413
		return 1;
1414
	return 0;
1415
}
1416

1417
/*
1418
 * When adding an object, check whether we have already added it
1419
 * to our packing list. If so, we can skip. However, if we are
1420
 * being asked to excludei t, but the previous mention was to include
1421
 * it, make sure to adjust its flags and tweak our numbers accordingly.
1422
 *
1423
 * As an optimization, we pass out the index position where we would have
1424
 * found the item, since that saves us from having to look it up again a
1425
 * few lines later when we want to add the new entry.
1426
 */
1427
static int have_duplicate_entry(const struct object_id *oid,
1428
				int exclude)
1429
{
1430
	struct object_entry *entry;
1431

1432
	if (reuse_packfile_bitmap &&
1433
	    bitmap_walk_contains(bitmap_git, reuse_packfile_bitmap, oid))
1434
		return 1;
1435

1436
	entry = packlist_find(&to_pack, oid);
1437
	if (!entry)
1438
		return 0;
1439

1440
	if (exclude) {
1441
		if (!entry->preferred_base)
1442
			nr_result--;
1443
		entry->preferred_base = 1;
1444
	}
1445

1446
	return 1;
1447
}
1448

1449
static int want_found_object(const struct object_id *oid, int exclude,
1450
			     struct packed_git *p)
1451
{
1452
	if (exclude)
1453
		return 1;
1454
	if (incremental)
1455
		return 0;
1456

1457
	if (!is_pack_valid(p))
1458
		return -1;
1459

1460
	/*
1461
	 * When asked to do --local (do not include an object that appears in a
1462
	 * pack we borrow from elsewhere) or --honor-pack-keep (do not include
1463
	 * an object that appears in a pack marked with .keep), finding a pack
1464
	 * that matches the criteria is sufficient for us to decide to omit it.
1465
	 * However, even if this pack does not satisfy the criteria, we need to
1466
	 * make sure no copy of this object appears in _any_ pack that makes us
1467
	 * to omit the object, so we need to check all the packs.
1468
	 *
1469
	 * We can however first check whether these options can possibly matter;
1470
	 * if they do not matter we know we want the object in generated pack.
1471
	 * Otherwise, we signal "-1" at the end to tell the caller that we do
1472
	 * not know either way, and it needs to check more packs.
1473
	 */
1474

1475
	/*
1476
	 * Objects in packs borrowed from elsewhere are discarded regardless of
1477
	 * if they appear in other packs that weren't borrowed.
1478
	 */
1479
	if (local && !p->pack_local)
1480
		return 0;
1481

1482
	/*
1483
	 * Then handle .keep first, as we have a fast(er) path there.
1484
	 */
1485
	if (ignore_packed_keep_on_disk || ignore_packed_keep_in_core) {
1486
		/*
1487
		 * Set the flags for the kept-pack cache to be the ones we want
1488
		 * to ignore.
1489
		 *
1490
		 * That is, if we are ignoring objects in on-disk keep packs,
1491
		 * then we want to search through the on-disk keep and ignore
1492
		 * the in-core ones.
1493
		 */
1494
		unsigned flags = 0;
1495
		if (ignore_packed_keep_on_disk)
1496
			flags |= ON_DISK_KEEP_PACKS;
1497
		if (ignore_packed_keep_in_core)
1498
			flags |= IN_CORE_KEEP_PACKS;
1499

1500
		if (ignore_packed_keep_on_disk && p->pack_keep)
1501
			return 0;
1502
		if (ignore_packed_keep_in_core && p->pack_keep_in_core)
1503
			return 0;
1504
		if (has_object_kept_pack(oid, flags))
1505
			return 0;
1506
	}
1507

1508
	/*
1509
	 * At this point we know definitively that either we don't care about
1510
	 * keep-packs, or the object is not in one. Keep checking other
1511
	 * conditions...
1512
	 */
1513
	if (!local || !have_non_local_packs)
1514
		return 1;
1515

1516
	/* we don't know yet; keep looking for more packs */
1517
	return -1;
1518
}
1519

1520
static int want_object_in_pack_one(struct packed_git *p,
1521
				   const struct object_id *oid,
1522
				   int exclude,
1523
				   struct packed_git **found_pack,
1524
				   off_t *found_offset)
1525
{
1526
	off_t offset;
1527

1528
	if (p == *found_pack)
1529
		offset = *found_offset;
1530
	else
1531
		offset = find_pack_entry_one(oid->hash, p);
1532

1533
	if (offset) {
1534
		if (!*found_pack) {
1535
			if (!is_pack_valid(p))
1536
				return -1;
1537
			*found_offset = offset;
1538
			*found_pack = p;
1539
		}
1540
		return want_found_object(oid, exclude, p);
1541
	}
1542
	return -1;
1543
}
1544

1545
/*
1546
 * Check whether we want the object in the pack (e.g., we do not want
1547
 * objects found in non-local stores if the "--local" option was used).
1548
 *
1549
 * If the caller already knows an existing pack it wants to take the object
1550
 * from, that is passed in *found_pack and *found_offset; otherwise this
1551
 * function finds if there is any pack that has the object and returns the pack
1552
 * and its offset in these variables.
1553
 */
1554
static int want_object_in_pack(const struct object_id *oid,
1555
			       int exclude,
1556
			       struct packed_git **found_pack,
1557
			       off_t *found_offset)
1558
{
1559
	int want;
1560
	struct list_head *pos;
1561
	struct multi_pack_index *m;
1562

1563
	if (!exclude && local && has_loose_object_nonlocal(oid))
1564
		return 0;
1565

1566
	/*
1567
	 * If we already know the pack object lives in, start checks from that
1568
	 * pack - in the usual case when neither --local was given nor .keep files
1569
	 * are present we will determine the answer right now.
1570
	 */
1571
	if (*found_pack) {
1572
		want = want_found_object(oid, exclude, *found_pack);
1573
		if (want != -1)
1574
			return want;
1575

1576
		*found_pack = NULL;
1577
		*found_offset = 0;
1578
	}
1579

1580
	for (m = get_multi_pack_index(the_repository); m; m = m->next) {
1581
		struct pack_entry e;
1582
		if (fill_midx_entry(the_repository, oid, &e, m)) {
1583
			want = want_object_in_pack_one(e.p, oid, exclude, found_pack, found_offset);
1584
			if (want != -1)
1585
				return want;
1586
		}
1587
	}
1588

1589
	list_for_each(pos, get_packed_git_mru(the_repository)) {
1590
		struct packed_git *p = list_entry(pos, struct packed_git, mru);
1591
		want = want_object_in_pack_one(p, oid, exclude, found_pack, found_offset);
1592
		if (!exclude && want > 0)
1593
			list_move(&p->mru,
1594
				  get_packed_git_mru(the_repository));
1595
		if (want != -1)
1596
			return want;
1597
	}
1598

1599
	if (uri_protocols.nr) {
1600
		struct configured_exclusion *ex =
1601
			oidmap_get(&configured_exclusions, oid);
1602
		int i;
1603
		const char *p;
1604

1605
		if (ex) {
1606
			for (i = 0; i < uri_protocols.nr; i++) {
1607
				if (skip_prefix(ex->uri,
1608
						uri_protocols.items[i].string,
1609
						&p) &&
1610
				    *p == ':') {
1611
					oidset_insert(&excluded_by_config, oid);
1612
					return 0;
1613
				}
1614
			}
1615
		}
1616
	}
1617

1618
	return 1;
1619
}
1620

1621
static struct object_entry *create_object_entry(const struct object_id *oid,
1622
						enum object_type type,
1623
						uint32_t hash,
1624
						int exclude,
1625
						int no_try_delta,
1626
						struct packed_git *found_pack,
1627
						off_t found_offset)
1628
{
1629
	struct object_entry *entry;
1630

1631
	entry = packlist_alloc(&to_pack, oid);
1632
	entry->hash = hash;
1633
	oe_set_type(entry, type);
1634
	if (exclude)
1635
		entry->preferred_base = 1;
1636
	else
1637
		nr_result++;
1638
	if (found_pack) {
1639
		oe_set_in_pack(&to_pack, entry, found_pack);
1640
		entry->in_pack_offset = found_offset;
1641
	}
1642

1643
	entry->no_try_delta = no_try_delta;
1644

1645
	return entry;
1646
}
1647

1648
static const char no_closure_warning[] = N_(
1649
"disabling bitmap writing, as some objects are not being packed"
1650
);
1651

1652
static int add_object_entry(const struct object_id *oid, enum object_type type,
1653
			    const char *name, int exclude)
1654
{
1655
	struct packed_git *found_pack = NULL;
1656
	off_t found_offset = 0;
1657

1658
	display_progress(progress_state, ++nr_seen);
1659

1660
	if (have_duplicate_entry(oid, exclude))
1661
		return 0;
1662

1663
	if (!want_object_in_pack(oid, exclude, &found_pack, &found_offset)) {
1664
		/* The pack is missing an object, so it will not have closure */
1665
		if (write_bitmap_index) {
1666
			if (write_bitmap_index != WRITE_BITMAP_QUIET)
1667
				warning(_(no_closure_warning));
1668
			write_bitmap_index = 0;
1669
		}
1670
		return 0;
1671
	}
1672

1673
	create_object_entry(oid, type, pack_name_hash(name),
1674
			    exclude, name && no_try_delta(name),
1675
			    found_pack, found_offset);
1676
	return 1;
1677
}
1678

1679
static int add_object_entry_from_bitmap(const struct object_id *oid,
1680
					enum object_type type,
1681
					int flags UNUSED, uint32_t name_hash,
1682
					struct packed_git *pack, off_t offset)
1683
{
1684
	display_progress(progress_state, ++nr_seen);
1685

1686
	if (have_duplicate_entry(oid, 0))
1687
		return 0;
1688

1689
	if (!want_object_in_pack(oid, 0, &pack, &offset))
1690
		return 0;
1691

1692
	create_object_entry(oid, type, name_hash, 0, 0, pack, offset);
1693
	return 1;
1694
}
1695

1696
struct pbase_tree_cache {
1697
	struct object_id oid;
1698
	int ref;
1699
	int temporary;
1700
	void *tree_data;
1701
	unsigned long tree_size;
1702
};
1703

1704
static struct pbase_tree_cache *(pbase_tree_cache[256]);
1705
static int pbase_tree_cache_ix(const struct object_id *oid)
1706
{
1707
	return oid->hash[0] % ARRAY_SIZE(pbase_tree_cache);
1708
}
1709
static int pbase_tree_cache_ix_incr(int ix)
1710
{
1711
	return (ix+1) % ARRAY_SIZE(pbase_tree_cache);
1712
}
1713

1714
static struct pbase_tree {
1715
	struct pbase_tree *next;
1716
	/* This is a phony "cache" entry; we are not
1717
	 * going to evict it or find it through _get()
1718
	 * mechanism -- this is for the toplevel node that
1719
	 * would almost always change with any commit.
1720
	 */
1721
	struct pbase_tree_cache pcache;
1722
} *pbase_tree;
1723

1724
static struct pbase_tree_cache *pbase_tree_get(const struct object_id *oid)
1725
{
1726
	struct pbase_tree_cache *ent, *nent;
1727
	void *data;
1728
	unsigned long size;
1729
	enum object_type type;
1730
	int neigh;
1731
	int my_ix = pbase_tree_cache_ix(oid);
1732
	int available_ix = -1;
1733

1734
	/* pbase-tree-cache acts as a limited hashtable.
1735
	 * your object will be found at your index or within a few
1736
	 * slots after that slot if it is cached.
1737
	 */
1738
	for (neigh = 0; neigh < 8; neigh++) {
1739
		ent = pbase_tree_cache[my_ix];
1740
		if (ent && oideq(&ent->oid, oid)) {
1741
			ent->ref++;
1742
			return ent;
1743
		}
1744
		else if (((available_ix < 0) && (!ent || !ent->ref)) ||
1745
			 ((0 <= available_ix) &&
1746
			  (!ent && pbase_tree_cache[available_ix])))
1747
			available_ix = my_ix;
1748
		if (!ent)
1749
			break;
1750
		my_ix = pbase_tree_cache_ix_incr(my_ix);
1751
	}
1752

1753
	/* Did not find one.  Either we got a bogus request or
1754
	 * we need to read and perhaps cache.
1755
	 */
1756
	data = repo_read_object_file(the_repository, oid, &type, &size);
1757
	if (!data)
1758
		return NULL;
1759
	if (type != OBJ_TREE) {
1760
		free(data);
1761
		return NULL;
1762
	}
1763

1764
	/* We need to either cache or return a throwaway copy */
1765

1766
	if (available_ix < 0)
1767
		ent = NULL;
1768
	else {
1769
		ent = pbase_tree_cache[available_ix];
1770
		my_ix = available_ix;
1771
	}
1772

1773
	if (!ent) {
1774
		nent = xmalloc(sizeof(*nent));
1775
		nent->temporary = (available_ix < 0);
1776
	}
1777
	else {
1778
		/* evict and reuse */
1779
		free(ent->tree_data);
1780
		nent = ent;
1781
	}
1782
	oidcpy(&nent->oid, oid);
1783
	nent->tree_data = data;
1784
	nent->tree_size = size;
1785
	nent->ref = 1;
1786
	if (!nent->temporary)
1787
		pbase_tree_cache[my_ix] = nent;
1788
	return nent;
1789
}
1790

1791
static void pbase_tree_put(struct pbase_tree_cache *cache)
1792
{
1793
	if (!cache->temporary) {
1794
		cache->ref--;
1795
		return;
1796
	}
1797
	free(cache->tree_data);
1798
	free(cache);
1799
}
1800

1801
static size_t name_cmp_len(const char *name)
1802
{
1803
	return strcspn(name, "\n/");
1804
}
1805

1806
static void add_pbase_object(struct tree_desc *tree,
1807
			     const char *name,
1808
			     size_t cmplen,
1809
			     const char *fullname)
1810
{
1811
	struct name_entry entry;
1812
	int cmp;
1813

1814
	while (tree_entry(tree,&entry)) {
1815
		if (S_ISGITLINK(entry.mode))
1816
			continue;
1817
		cmp = tree_entry_len(&entry) != cmplen ? 1 :
1818
		      memcmp(name, entry.path, cmplen);
1819
		if (cmp > 0)
1820
			continue;
1821
		if (cmp < 0)
1822
			return;
1823
		if (name[cmplen] != '/') {
1824
			add_object_entry(&entry.oid,
1825
					 object_type(entry.mode),
1826
					 fullname, 1);
1827
			return;
1828
		}
1829
		if (S_ISDIR(entry.mode)) {
1830
			struct tree_desc sub;
1831
			struct pbase_tree_cache *tree;
1832
			const char *down = name+cmplen+1;
1833
			size_t downlen = name_cmp_len(down);
1834

1835
			tree = pbase_tree_get(&entry.oid);
1836
			if (!tree)
1837
				return;
1838
			init_tree_desc(&sub, &tree->oid,
1839
				       tree->tree_data, tree->tree_size);
1840

1841
			add_pbase_object(&sub, down, downlen, fullname);
1842
			pbase_tree_put(tree);
1843
		}
1844
	}
1845
}
1846

1847
static unsigned *done_pbase_paths;
1848
static int done_pbase_paths_num;
1849
static int done_pbase_paths_alloc;
1850
static int done_pbase_path_pos(unsigned hash)
1851
{
1852
	int lo = 0;
1853
	int hi = done_pbase_paths_num;
1854
	while (lo < hi) {
1855
		int mi = lo + (hi - lo) / 2;
1856
		if (done_pbase_paths[mi] == hash)
1857
			return mi;
1858
		if (done_pbase_paths[mi] < hash)
1859
			hi = mi;
1860
		else
1861
			lo = mi + 1;
1862
	}
1863
	return -lo-1;
1864
}
1865

1866
static int check_pbase_path(unsigned hash)
1867
{
1868
	int pos = done_pbase_path_pos(hash);
1869
	if (0 <= pos)
1870
		return 1;
1871
	pos = -pos - 1;
1872
	ALLOC_GROW(done_pbase_paths,
1873
		   done_pbase_paths_num + 1,
1874
		   done_pbase_paths_alloc);
1875
	done_pbase_paths_num++;
1876
	if (pos < done_pbase_paths_num)
1877
		MOVE_ARRAY(done_pbase_paths + pos + 1, done_pbase_paths + pos,
1878
			   done_pbase_paths_num - pos - 1);
1879
	done_pbase_paths[pos] = hash;
1880
	return 0;
1881
}
1882

1883
static void add_preferred_base_object(const char *name)
1884
{
1885
	struct pbase_tree *it;
1886
	size_t cmplen;
1887
	unsigned hash = pack_name_hash(name);
1888

1889
	if (!num_preferred_base || check_pbase_path(hash))
1890
		return;
1891

1892
	cmplen = name_cmp_len(name);
1893
	for (it = pbase_tree; it; it = it->next) {
1894
		if (cmplen == 0) {
1895
			add_object_entry(&it->pcache.oid, OBJ_TREE, NULL, 1);
1896
		}
1897
		else {
1898
			struct tree_desc tree;
1899
			init_tree_desc(&tree, &it->pcache.oid,
1900
				       it->pcache.tree_data, it->pcache.tree_size);
1901
			add_pbase_object(&tree, name, cmplen, name);
1902
		}
1903
	}
1904
}
1905

1906
static void add_preferred_base(struct object_id *oid)
1907
{
1908
	struct pbase_tree *it;
1909
	void *data;
1910
	unsigned long size;
1911
	struct object_id tree_oid;
1912

1913
	if (window <= num_preferred_base++)
1914
		return;
1915

1916
	data = read_object_with_reference(the_repository, oid,
1917
					  OBJ_TREE, &size, &tree_oid);
1918
	if (!data)
1919
		return;
1920

1921
	for (it = pbase_tree; it; it = it->next) {
1922
		if (oideq(&it->pcache.oid, &tree_oid)) {
1923
			free(data);
1924
			return;
1925
		}
1926
	}
1927

1928
	CALLOC_ARRAY(it, 1);
1929
	it->next = pbase_tree;
1930
	pbase_tree = it;
1931

1932
	oidcpy(&it->pcache.oid, &tree_oid);
1933
	it->pcache.tree_data = data;
1934
	it->pcache.tree_size = size;
1935
}
1936

1937
static void cleanup_preferred_base(void)
1938
{
1939
	struct pbase_tree *it;
1940
	unsigned i;
1941

1942
	it = pbase_tree;
1943
	pbase_tree = NULL;
1944
	while (it) {
1945
		struct pbase_tree *tmp = it;
1946
		it = tmp->next;
1947
		free(tmp->pcache.tree_data);
1948
		free(tmp);
1949
	}
1950

1951
	for (i = 0; i < ARRAY_SIZE(pbase_tree_cache); i++) {
1952
		if (!pbase_tree_cache[i])
1953
			continue;
1954
		free(pbase_tree_cache[i]->tree_data);
1955
		FREE_AND_NULL(pbase_tree_cache[i]);
1956
	}
1957

1958
	FREE_AND_NULL(done_pbase_paths);
1959
	done_pbase_paths_num = done_pbase_paths_alloc = 0;
1960
}
1961

1962
/*
1963
 * Return 1 iff the object specified by "delta" can be sent
1964
 * literally as a delta against the base in "base_sha1". If
1965
 * so, then *base_out will point to the entry in our packing
1966
 * list, or NULL if we must use the external-base list.
1967
 *
1968
 * Depth value does not matter - find_deltas() will
1969
 * never consider reused delta as the base object to
1970
 * deltify other objects against, in order to avoid
1971
 * circular deltas.
1972
 */
1973
static int can_reuse_delta(const struct object_id *base_oid,
1974
			   struct object_entry *delta,
1975
			   struct object_entry **base_out)
1976
{
1977
	struct object_entry *base;
1978

1979
	/*
1980
	 * First see if we're already sending the base (or it's explicitly in
1981
	 * our "excluded" list).
1982
	 */
1983
	base = packlist_find(&to_pack, base_oid);
1984
	if (base) {
1985
		if (!in_same_island(&delta->idx.oid, &base->idx.oid))
1986
			return 0;
1987
		*base_out = base;
1988
		return 1;
1989
	}
1990

1991
	/*
1992
	 * Otherwise, reachability bitmaps may tell us if the receiver has it,
1993
	 * even if it was buried too deep in history to make it into the
1994
	 * packing list.
1995
	 */
1996
	if (thin && bitmap_has_oid_in_uninteresting(bitmap_git, base_oid)) {
1997
		if (use_delta_islands) {
1998
			if (!in_same_island(&delta->idx.oid, base_oid))
1999
				return 0;
2000
		}
2001
		*base_out = NULL;
2002
		return 1;
2003
	}
2004

2005
	return 0;
2006
}
2007

2008
static void prefetch_to_pack(uint32_t object_index_start) {
2009
	struct oid_array to_fetch = OID_ARRAY_INIT;
2010
	uint32_t i;
2011

2012
	for (i = object_index_start; i < to_pack.nr_objects; i++) {
2013
		struct object_entry *entry = to_pack.objects + i;
2014

2015
		if (!oid_object_info_extended(the_repository,
2016
					      &entry->idx.oid,
2017
					      NULL,
2018
					      OBJECT_INFO_FOR_PREFETCH))
2019
			continue;
2020
		oid_array_append(&to_fetch, &entry->idx.oid);
2021
	}
2022
	promisor_remote_get_direct(the_repository,
2023
				   to_fetch.oid, to_fetch.nr);
2024
	oid_array_clear(&to_fetch);
2025
}
2026

2027
static void check_object(struct object_entry *entry, uint32_t object_index)
2028
{
2029
	unsigned long canonical_size;
2030
	enum object_type type;
2031
	struct object_info oi = {.typep = &type, .sizep = &canonical_size};
2032

2033
	if (IN_PACK(entry)) {
2034
		struct packed_git *p = IN_PACK(entry);
2035
		struct pack_window *w_curs = NULL;
2036
		int have_base = 0;
2037
		struct object_id base_ref;
2038
		struct object_entry *base_entry;
2039
		unsigned long used, used_0;
2040
		unsigned long avail;
2041
		off_t ofs;
2042
		unsigned char *buf, c;
2043
		enum object_type type;
2044
		unsigned long in_pack_size;
2045

2046
		buf = use_pack(p, &w_curs, entry->in_pack_offset, &avail);
2047

2048
		/*
2049
		 * We want in_pack_type even if we do not reuse delta
2050
		 * since non-delta representations could still be reused.
2051
		 */
2052
		used = unpack_object_header_buffer(buf, avail,
2053
						   &type,
2054
						   &in_pack_size);
2055
		if (used == 0)
2056
			goto give_up;
2057

2058
		if (type < 0)
2059
			BUG("invalid type %d", type);
2060
		entry->in_pack_type = type;
2061

2062
		/*
2063
		 * Determine if this is a delta and if so whether we can
2064
		 * reuse it or not.  Otherwise let's find out as cheaply as
2065
		 * possible what the actual type and size for this object is.
2066
		 */
2067
		switch (entry->in_pack_type) {
2068
		default:
2069
			/* Not a delta hence we've already got all we need. */
2070
			oe_set_type(entry, entry->in_pack_type);
2071
			SET_SIZE(entry, in_pack_size);
2072
			entry->in_pack_header_size = used;
2073
			if (oe_type(entry) < OBJ_COMMIT || oe_type(entry) > OBJ_BLOB)
2074
				goto give_up;
2075
			unuse_pack(&w_curs);
2076
			return;
2077
		case OBJ_REF_DELTA:
2078
			if (reuse_delta && !entry->preferred_base) {
2079
				oidread(&base_ref,
2080
					use_pack(p, &w_curs,
2081
						 entry->in_pack_offset + used,
2082
						 NULL),
2083
					the_repository->hash_algo);
2084
				have_base = 1;
2085
			}
2086
			entry->in_pack_header_size = used + the_hash_algo->rawsz;
2087
			break;
2088
		case OBJ_OFS_DELTA:
2089
			buf = use_pack(p, &w_curs,
2090
				       entry->in_pack_offset + used, NULL);
2091
			used_0 = 0;
2092
			c = buf[used_0++];
2093
			ofs = c & 127;
2094
			while (c & 128) {
2095
				ofs += 1;
2096
				if (!ofs || MSB(ofs, 7)) {
2097
					error(_("delta base offset overflow in pack for %s"),
2098
					      oid_to_hex(&entry->idx.oid));
2099
					goto give_up;
2100
				}
2101
				c = buf[used_0++];
2102
				ofs = (ofs << 7) + (c & 127);
2103
			}
2104
			ofs = entry->in_pack_offset - ofs;
2105
			if (ofs <= 0 || ofs >= entry->in_pack_offset) {
2106
				error(_("delta base offset out of bound for %s"),
2107
				      oid_to_hex(&entry->idx.oid));
2108
				goto give_up;
2109
			}
2110
			if (reuse_delta && !entry->preferred_base) {
2111
				uint32_t pos;
2112
				if (offset_to_pack_pos(p, ofs, &pos) < 0)
2113
					goto give_up;
2114
				if (!nth_packed_object_id(&base_ref, p,
2115
							  pack_pos_to_index(p, pos)))
2116
					have_base = 1;
2117
			}
2118
			entry->in_pack_header_size = used + used_0;
2119
			break;
2120
		}
2121

2122
		if (have_base &&
2123
		    can_reuse_delta(&base_ref, entry, &base_entry)) {
2124
			oe_set_type(entry, entry->in_pack_type);
2125
			SET_SIZE(entry, in_pack_size); /* delta size */
2126
			SET_DELTA_SIZE(entry, in_pack_size);
2127

2128
			if (base_entry) {
2129
				SET_DELTA(entry, base_entry);
2130
				entry->delta_sibling_idx = base_entry->delta_child_idx;
2131
				SET_DELTA_CHILD(base_entry, entry);
2132
			} else {
2133
				SET_DELTA_EXT(entry, &base_ref);
2134
			}
2135

2136
			unuse_pack(&w_curs);
2137
			return;
2138
		}
2139

2140
		if (oe_type(entry)) {
2141
			off_t delta_pos;
2142

2143
			/*
2144
			 * This must be a delta and we already know what the
2145
			 * final object type is.  Let's extract the actual
2146
			 * object size from the delta header.
2147
			 */
2148
			delta_pos = entry->in_pack_offset + entry->in_pack_header_size;
2149
			canonical_size = get_size_from_delta(p, &w_curs, delta_pos);
2150
			if (canonical_size == 0)
2151
				goto give_up;
2152
			SET_SIZE(entry, canonical_size);
2153
			unuse_pack(&w_curs);
2154
			return;
2155
		}
2156

2157
		/*
2158
		 * No choice but to fall back to the recursive delta walk
2159
		 * with oid_object_info() to find about the object type
2160
		 * at this point...
2161
		 */
2162
		give_up:
2163
		unuse_pack(&w_curs);
2164
	}
2165

2166
	if (oid_object_info_extended(the_repository, &entry->idx.oid, &oi,
2167
				     OBJECT_INFO_SKIP_FETCH_OBJECT | OBJECT_INFO_LOOKUP_REPLACE) < 0) {
2168
		if (repo_has_promisor_remote(the_repository)) {
2169
			prefetch_to_pack(object_index);
2170
			if (oid_object_info_extended(the_repository, &entry->idx.oid, &oi,
2171
						     OBJECT_INFO_SKIP_FETCH_OBJECT | OBJECT_INFO_LOOKUP_REPLACE) < 0)
2172
				type = -1;
2173
		} else {
2174
			type = -1;
2175
		}
2176
	}
2177
	oe_set_type(entry, type);
2178
	if (entry->type_valid) {
2179
		SET_SIZE(entry, canonical_size);
2180
	} else {
2181
		/*
2182
		 * Bad object type is checked in prepare_pack().  This is
2183
		 * to permit a missing preferred base object to be ignored
2184
		 * as a preferred base.  Doing so can result in a larger
2185
		 * pack file, but the transfer will still take place.
2186
		 */
2187
	}
2188
}
2189

2190
static int pack_offset_sort(const void *_a, const void *_b)
2191
{
2192
	const struct object_entry *a = *(struct object_entry **)_a;
2193
	const struct object_entry *b = *(struct object_entry **)_b;
2194
	const struct packed_git *a_in_pack = IN_PACK(a);
2195
	const struct packed_git *b_in_pack = IN_PACK(b);
2196

2197
	/* avoid filesystem trashing with loose objects */
2198
	if (!a_in_pack && !b_in_pack)
2199
		return oidcmp(&a->idx.oid, &b->idx.oid);
2200

2201
	if (a_in_pack < b_in_pack)
2202
		return -1;
2203
	if (a_in_pack > b_in_pack)
2204
		return 1;
2205
	return a->in_pack_offset < b->in_pack_offset ? -1 :
2206
			(a->in_pack_offset > b->in_pack_offset);
2207
}
2208

2209
/*
2210
 * Drop an on-disk delta we were planning to reuse. Naively, this would
2211
 * just involve blanking out the "delta" field, but we have to deal
2212
 * with some extra book-keeping:
2213
 *
2214
 *   1. Removing ourselves from the delta_sibling linked list.
2215
 *
2216
 *   2. Updating our size/type to the non-delta representation. These were
2217
 *      either not recorded initially (size) or overwritten with the delta type
2218
 *      (type) when check_object() decided to reuse the delta.
2219
 *
2220
 *   3. Resetting our delta depth, as we are now a base object.
2221
 */
2222
static void drop_reused_delta(struct object_entry *entry)
2223
{
2224
	unsigned *idx = &to_pack.objects[entry->delta_idx - 1].delta_child_idx;
2225
	struct object_info oi = OBJECT_INFO_INIT;
2226
	enum object_type type;
2227
	unsigned long size;
2228

2229
	while (*idx) {
2230
		struct object_entry *oe = &to_pack.objects[*idx - 1];
2231

2232
		if (oe == entry)
2233
			*idx = oe->delta_sibling_idx;
2234
		else
2235
			idx = &oe->delta_sibling_idx;
2236
	}
2237
	SET_DELTA(entry, NULL);
2238
	entry->depth = 0;
2239

2240
	oi.sizep = &size;
2241
	oi.typep = &type;
2242
	if (packed_object_info(the_repository, IN_PACK(entry), entry->in_pack_offset, &oi) < 0) {
2243
		/*
2244
		 * We failed to get the info from this pack for some reason;
2245
		 * fall back to oid_object_info, which may find another copy.
2246
		 * And if that fails, the error will be recorded in oe_type(entry)
2247
		 * and dealt with in prepare_pack().
2248
		 */
2249
		oe_set_type(entry,
2250
			    oid_object_info(the_repository, &entry->idx.oid, &size));
2251
	} else {
2252
		oe_set_type(entry, type);
2253
	}
2254
	SET_SIZE(entry, size);
2255
}
2256

2257
/*
2258
 * Follow the chain of deltas from this entry onward, throwing away any links
2259
 * that cause us to hit a cycle (as determined by the DFS state flags in
2260
 * the entries).
2261
 *
2262
 * We also detect too-long reused chains that would violate our --depth
2263
 * limit.
2264
 */
2265
static void break_delta_chains(struct object_entry *entry)
2266
{
2267
	/*
2268
	 * The actual depth of each object we will write is stored as an int,
2269
	 * as it cannot exceed our int "depth" limit. But before we break
2270
	 * changes based no that limit, we may potentially go as deep as the
2271
	 * number of objects, which is elsewhere bounded to a uint32_t.
2272
	 */
2273
	uint32_t total_depth;
2274
	struct object_entry *cur, *next;
2275

2276
	for (cur = entry, total_depth = 0;
2277
	     cur;
2278
	     cur = DELTA(cur), total_depth++) {
2279
		if (cur->dfs_state == DFS_DONE) {
2280
			/*
2281
			 * We've already seen this object and know it isn't
2282
			 * part of a cycle. We do need to append its depth
2283
			 * to our count.
2284
			 */
2285
			total_depth += cur->depth;
2286
			break;
2287
		}
2288

2289
		/*
2290
		 * We break cycles before looping, so an ACTIVE state (or any
2291
		 * other cruft which made its way into the state variable)
2292
		 * is a bug.
2293
		 */
2294
		if (cur->dfs_state != DFS_NONE)
2295
			BUG("confusing delta dfs state in first pass: %d",
2296
			    cur->dfs_state);
2297

2298
		/*
2299
		 * Now we know this is the first time we've seen the object. If
2300
		 * it's not a delta, we're done traversing, but we'll mark it
2301
		 * done to save time on future traversals.
2302
		 */
2303
		if (!DELTA(cur)) {
2304
			cur->dfs_state = DFS_DONE;
2305
			break;
2306
		}
2307

2308
		/*
2309
		 * Mark ourselves as active and see if the next step causes
2310
		 * us to cycle to another active object. It's important to do
2311
		 * this _before_ we loop, because it impacts where we make the
2312
		 * cut, and thus how our total_depth counter works.
2313
		 * E.g., We may see a partial loop like:
2314
		 *
2315
		 *   A -> B -> C -> D -> B
2316
		 *
2317
		 * Cutting B->C breaks the cycle. But now the depth of A is
2318
		 * only 1, and our total_depth counter is at 3. The size of the
2319
		 * error is always one less than the size of the cycle we
2320
		 * broke. Commits C and D were "lost" from A's chain.
2321
		 *
2322
		 * If we instead cut D->B, then the depth of A is correct at 3.
2323
		 * We keep all commits in the chain that we examined.
2324
		 */
2325
		cur->dfs_state = DFS_ACTIVE;
2326
		if (DELTA(cur)->dfs_state == DFS_ACTIVE) {
2327
			drop_reused_delta(cur);
2328
			cur->dfs_state = DFS_DONE;
2329
			break;
2330
		}
2331
	}
2332

2333
	/*
2334
	 * And now that we've gone all the way to the bottom of the chain, we
2335
	 * need to clear the active flags and set the depth fields as
2336
	 * appropriate. Unlike the loop above, which can quit when it drops a
2337
	 * delta, we need to keep going to look for more depth cuts. So we need
2338
	 * an extra "next" pointer to keep going after we reset cur->delta.
2339
	 */
2340
	for (cur = entry; cur; cur = next) {
2341
		next = DELTA(cur);
2342

2343
		/*
2344
		 * We should have a chain of zero or more ACTIVE states down to
2345
		 * a final DONE. We can quit after the DONE, because either it
2346
		 * has no bases, or we've already handled them in a previous
2347
		 * call.
2348
		 */
2349
		if (cur->dfs_state == DFS_DONE)
2350
			break;
2351
		else if (cur->dfs_state != DFS_ACTIVE)
2352
			BUG("confusing delta dfs state in second pass: %d",
2353
			    cur->dfs_state);
2354

2355
		/*
2356
		 * If the total_depth is more than depth, then we need to snip
2357
		 * the chain into two or more smaller chains that don't exceed
2358
		 * the maximum depth. Most of the resulting chains will contain
2359
		 * (depth + 1) entries (i.e., depth deltas plus one base), and
2360
		 * the last chain (i.e., the one containing entry) will contain
2361
		 * whatever entries are left over, namely
2362
		 * (total_depth % (depth + 1)) of them.
2363
		 *
2364
		 * Since we are iterating towards decreasing depth, we need to
2365
		 * decrement total_depth as we go, and we need to write to the
2366
		 * entry what its final depth will be after all of the
2367
		 * snipping. Since we're snipping into chains of length (depth
2368
		 * + 1) entries, the final depth of an entry will be its
2369
		 * original depth modulo (depth + 1). Any time we encounter an
2370
		 * entry whose final depth is supposed to be zero, we snip it
2371
		 * from its delta base, thereby making it so.
2372
		 */
2373
		cur->depth = (total_depth--) % (depth + 1);
2374
		if (!cur->depth)
2375
			drop_reused_delta(cur);
2376

2377
		cur->dfs_state = DFS_DONE;
2378
	}
2379
}
2380

2381
static void get_object_details(void)
2382
{
2383
	uint32_t i;
2384
	struct object_entry **sorted_by_offset;
2385

2386
	if (progress)
2387
		progress_state = start_progress(_("Counting objects"),
2388
						to_pack.nr_objects);
2389

2390
	CALLOC_ARRAY(sorted_by_offset, to_pack.nr_objects);
2391
	for (i = 0; i < to_pack.nr_objects; i++)
2392
		sorted_by_offset[i] = to_pack.objects + i;
2393
	QSORT(sorted_by_offset, to_pack.nr_objects, pack_offset_sort);
2394

2395
	for (i = 0; i < to_pack.nr_objects; i++) {
2396
		struct object_entry *entry = sorted_by_offset[i];
2397
		check_object(entry, i);
2398
		if (entry->type_valid &&
2399
		    oe_size_greater_than(&to_pack, entry, big_file_threshold))
2400
			entry->no_try_delta = 1;
2401
		display_progress(progress_state, i + 1);
2402
	}
2403
	stop_progress(&progress_state);
2404

2405
	/*
2406
	 * This must happen in a second pass, since we rely on the delta
2407
	 * information for the whole list being completed.
2408
	 */
2409
	for (i = 0; i < to_pack.nr_objects; i++)
2410
		break_delta_chains(&to_pack.objects[i]);
2411

2412
	free(sorted_by_offset);
2413
}
2414

2415
/*
2416
 * We search for deltas in a list sorted by type, by filename hash, and then
2417
 * by size, so that we see progressively smaller and smaller files.
2418
 * That's because we prefer deltas to be from the bigger file
2419
 * to the smaller -- deletes are potentially cheaper, but perhaps
2420
 * more importantly, the bigger file is likely the more recent
2421
 * one.  The deepest deltas are therefore the oldest objects which are
2422
 * less susceptible to be accessed often.
2423
 */
2424
static int type_size_sort(const void *_a, const void *_b)
2425
{
2426
	const struct object_entry *a = *(struct object_entry **)_a;
2427
	const struct object_entry *b = *(struct object_entry **)_b;
2428
	const enum object_type a_type = oe_type(a);
2429
	const enum object_type b_type = oe_type(b);
2430
	const unsigned long a_size = SIZE(a);
2431
	const unsigned long b_size = SIZE(b);
2432

2433
	if (a_type > b_type)
2434
		return -1;
2435
	if (a_type < b_type)
2436
		return 1;
2437
	if (a->hash > b->hash)
2438
		return -1;
2439
	if (a->hash < b->hash)
2440
		return 1;
2441
	if (a->preferred_base > b->preferred_base)
2442
		return -1;
2443
	if (a->preferred_base < b->preferred_base)
2444
		return 1;
2445
	if (use_delta_islands) {
2446
		const int island_cmp = island_delta_cmp(&a->idx.oid, &b->idx.oid);
2447
		if (island_cmp)
2448
			return island_cmp;
2449
	}
2450
	if (a_size > b_size)
2451
		return -1;
2452
	if (a_size < b_size)
2453
		return 1;
2454
	return a < b ? -1 : (a > b);  /* newest first */
2455
}
2456

2457
struct unpacked {
2458
	struct object_entry *entry;
2459
	void *data;
2460
	struct delta_index *index;
2461
	unsigned depth;
2462
};
2463

2464
static int delta_cacheable(unsigned long src_size, unsigned long trg_size,
2465
			   unsigned long delta_size)
2466
{
2467
	if (max_delta_cache_size && delta_cache_size + delta_size > max_delta_cache_size)
2468
		return 0;
2469

2470
	if (delta_size < cache_max_small_delta_size)
2471
		return 1;
2472

2473
	/* cache delta, if objects are large enough compared to delta size */
2474
	if ((src_size >> 20) + (trg_size >> 21) > (delta_size >> 10))
2475
		return 1;
2476

2477
	return 0;
2478
}
2479

2480
/* Protect delta_cache_size */
2481
static pthread_mutex_t cache_mutex;
2482
#define cache_lock()		pthread_mutex_lock(&cache_mutex)
2483
#define cache_unlock()		pthread_mutex_unlock(&cache_mutex)
2484

2485
/*
2486
 * Protect object list partitioning (e.g. struct thread_param) and
2487
 * progress_state
2488
 */
2489
static pthread_mutex_t progress_mutex;
2490
#define progress_lock()		pthread_mutex_lock(&progress_mutex)
2491
#define progress_unlock()	pthread_mutex_unlock(&progress_mutex)
2492

2493
/*
2494
 * Access to struct object_entry is unprotected since each thread owns
2495
 * a portion of the main object list. Just don't access object entries
2496
 * ahead in the list because they can be stolen and would need
2497
 * progress_mutex for protection.
2498
 */
2499

2500
static inline int oe_size_less_than(struct packing_data *pack,
2501
				    const struct object_entry *lhs,
2502
				    unsigned long rhs)
2503
{
2504
	if (lhs->size_valid)
2505
		return lhs->size_ < rhs;
2506
	if (rhs < pack->oe_size_limit) /* rhs < 2^x <= lhs ? */
2507
		return 0;
2508
	return oe_get_size_slow(pack, lhs) < rhs;
2509
}
2510

2511
static inline void oe_set_tree_depth(struct packing_data *pack,
2512
				     struct object_entry *e,
2513
				     unsigned int tree_depth)
2514
{
2515
	if (!pack->tree_depth)
2516
		CALLOC_ARRAY(pack->tree_depth, pack->nr_alloc);
2517
	pack->tree_depth[e - pack->objects] = tree_depth;
2518
}
2519

2520
/*
2521
 * Return the size of the object without doing any delta
2522
 * reconstruction (so non-deltas are true object sizes, but deltas
2523
 * return the size of the delta data).
2524
 */
2525
unsigned long oe_get_size_slow(struct packing_data *pack,
2526
			       const struct object_entry *e)
2527
{
2528
	struct packed_git *p;
2529
	struct pack_window *w_curs;
2530
	unsigned char *buf;
2531
	enum object_type type;
2532
	unsigned long used, avail, size;
2533

2534
	if (e->type_ != OBJ_OFS_DELTA && e->type_ != OBJ_REF_DELTA) {
2535
		packing_data_lock(&to_pack);
2536
		if (oid_object_info(the_repository, &e->idx.oid, &size) < 0)
2537
			die(_("unable to get size of %s"),
2538
			    oid_to_hex(&e->idx.oid));
2539
		packing_data_unlock(&to_pack);
2540
		return size;
2541
	}
2542

2543
	p = oe_in_pack(pack, e);
2544
	if (!p)
2545
		BUG("when e->type is a delta, it must belong to a pack");
2546

2547
	packing_data_lock(&to_pack);
2548
	w_curs = NULL;
2549
	buf = use_pack(p, &w_curs, e->in_pack_offset, &avail);
2550
	used = unpack_object_header_buffer(buf, avail, &type, &size);
2551
	if (used == 0)
2552
		die(_("unable to parse object header of %s"),
2553
		    oid_to_hex(&e->idx.oid));
2554

2555
	unuse_pack(&w_curs);
2556
	packing_data_unlock(&to_pack);
2557
	return size;
2558
}
2559

2560
static int try_delta(struct unpacked *trg, struct unpacked *src,
2561
		     unsigned max_depth, unsigned long *mem_usage)
2562
{
2563
	struct object_entry *trg_entry = trg->entry;
2564
	struct object_entry *src_entry = src->entry;
2565
	unsigned long trg_size, src_size, delta_size, sizediff, max_size, sz;
2566
	unsigned ref_depth;
2567
	enum object_type type;
2568
	void *delta_buf;
2569

2570
	/* Don't bother doing diffs between different types */
2571
	if (oe_type(trg_entry) != oe_type(src_entry))
2572
		return -1;
2573

2574
	/*
2575
	 * We do not bother to try a delta that we discarded on an
2576
	 * earlier try, but only when reusing delta data.  Note that
2577
	 * src_entry that is marked as the preferred_base should always
2578
	 * be considered, as even if we produce a suboptimal delta against
2579
	 * it, we will still save the transfer cost, as we already know
2580
	 * the other side has it and we won't send src_entry at all.
2581
	 */
2582
	if (reuse_delta && IN_PACK(trg_entry) &&
2583
	    IN_PACK(trg_entry) == IN_PACK(src_entry) &&
2584
	    !src_entry->preferred_base &&
2585
	    trg_entry->in_pack_type != OBJ_REF_DELTA &&
2586
	    trg_entry->in_pack_type != OBJ_OFS_DELTA)
2587
		return 0;
2588

2589
	/* Let's not bust the allowed depth. */
2590
	if (src->depth >= max_depth)
2591
		return 0;
2592

2593
	/* Now some size filtering heuristics. */
2594
	trg_size = SIZE(trg_entry);
2595
	if (!DELTA(trg_entry)) {
2596
		max_size = trg_size/2 - the_hash_algo->rawsz;
2597
		ref_depth = 1;
2598
	} else {
2599
		max_size = DELTA_SIZE(trg_entry);
2600
		ref_depth = trg->depth;
2601
	}
2602
	max_size = (uint64_t)max_size * (max_depth - src->depth) /
2603
						(max_depth - ref_depth + 1);
2604
	if (max_size == 0)
2605
		return 0;
2606
	src_size = SIZE(src_entry);
2607
	sizediff = src_size < trg_size ? trg_size - src_size : 0;
2608
	if (sizediff >= max_size)
2609
		return 0;
2610
	if (trg_size < src_size / 32)
2611
		return 0;
2612

2613
	if (!in_same_island(&trg->entry->idx.oid, &src->entry->idx.oid))
2614
		return 0;
2615

2616
	/* Load data if not already done */
2617
	if (!trg->data) {
2618
		packing_data_lock(&to_pack);
2619
		trg->data = repo_read_object_file(the_repository,
2620
						  &trg_entry->idx.oid, &type,
2621
						  &sz);
2622
		packing_data_unlock(&to_pack);
2623
		if (!trg->data)
2624
			die(_("object %s cannot be read"),
2625
			    oid_to_hex(&trg_entry->idx.oid));
2626
		if (sz != trg_size)
2627
			die(_("object %s inconsistent object length (%"PRIuMAX" vs %"PRIuMAX")"),
2628
			    oid_to_hex(&trg_entry->idx.oid), (uintmax_t)sz,
2629
			    (uintmax_t)trg_size);
2630
		*mem_usage += sz;
2631
	}
2632
	if (!src->data) {
2633
		packing_data_lock(&to_pack);
2634
		src->data = repo_read_object_file(the_repository,
2635
						  &src_entry->idx.oid, &type,
2636
						  &sz);
2637
		packing_data_unlock(&to_pack);
2638
		if (!src->data) {
2639
			if (src_entry->preferred_base) {
2640
				static int warned = 0;
2641
				if (!warned++)
2642
					warning(_("object %s cannot be read"),
2643
						oid_to_hex(&src_entry->idx.oid));
2644
				/*
2645
				 * Those objects are not included in the
2646
				 * resulting pack.  Be resilient and ignore
2647
				 * them if they can't be read, in case the
2648
				 * pack could be created nevertheless.
2649
				 */
2650
				return 0;
2651
			}
2652
			die(_("object %s cannot be read"),
2653
			    oid_to_hex(&src_entry->idx.oid));
2654
		}
2655
		if (sz != src_size)
2656
			die(_("object %s inconsistent object length (%"PRIuMAX" vs %"PRIuMAX")"),
2657
			    oid_to_hex(&src_entry->idx.oid), (uintmax_t)sz,
2658
			    (uintmax_t)src_size);
2659
		*mem_usage += sz;
2660
	}
2661
	if (!src->index) {
2662
		src->index = create_delta_index(src->data, src_size);
2663
		if (!src->index) {
2664
			static int warned = 0;
2665
			if (!warned++)
2666
				warning(_("suboptimal pack - out of memory"));
2667
			return 0;
2668
		}
2669
		*mem_usage += sizeof_delta_index(src->index);
2670
	}
2671

2672
	delta_buf = create_delta(src->index, trg->data, trg_size, &delta_size, max_size);
2673
	if (!delta_buf)
2674
		return 0;
2675

2676
	if (DELTA(trg_entry)) {
2677
		/* Prefer only shallower same-sized deltas. */
2678
		if (delta_size == DELTA_SIZE(trg_entry) &&
2679
		    src->depth + 1 >= trg->depth) {
2680
			free(delta_buf);
2681
			return 0;
2682
		}
2683
	}
2684

2685
	/*
2686
	 * Handle memory allocation outside of the cache
2687
	 * accounting lock.  Compiler will optimize the strangeness
2688
	 * away when NO_PTHREADS is defined.
2689
	 */
2690
	free(trg_entry->delta_data);
2691
	cache_lock();
2692
	if (trg_entry->delta_data) {
2693
		delta_cache_size -= DELTA_SIZE(trg_entry);
2694
		trg_entry->delta_data = NULL;
2695
	}
2696
	if (delta_cacheable(src_size, trg_size, delta_size)) {
2697
		delta_cache_size += delta_size;
2698
		cache_unlock();
2699
		trg_entry->delta_data = xrealloc(delta_buf, delta_size);
2700
	} else {
2701
		cache_unlock();
2702
		free(delta_buf);
2703
	}
2704

2705
	SET_DELTA(trg_entry, src_entry);
2706
	SET_DELTA_SIZE(trg_entry, delta_size);
2707
	trg->depth = src->depth + 1;
2708

2709
	return 1;
2710
}
2711

2712
static unsigned int check_delta_limit(struct object_entry *me, unsigned int n)
2713
{
2714
	struct object_entry *child = DELTA_CHILD(me);
2715
	unsigned int m = n;
2716
	while (child) {
2717
		const unsigned int c = check_delta_limit(child, n + 1);
2718
		if (m < c)
2719
			m = c;
2720
		child = DELTA_SIBLING(child);
2721
	}
2722
	return m;
2723
}
2724

2725
static unsigned long free_unpacked(struct unpacked *n)
2726
{
2727
	unsigned long freed_mem = sizeof_delta_index(n->index);
2728
	free_delta_index(n->index);
2729
	n->index = NULL;
2730
	if (n->data) {
2731
		freed_mem += SIZE(n->entry);
2732
		FREE_AND_NULL(n->data);
2733
	}
2734
	n->entry = NULL;
2735
	n->depth = 0;
2736
	return freed_mem;
2737
}
2738

2739
static void find_deltas(struct object_entry **list, unsigned *list_size,
2740
			int window, int depth, unsigned *processed)
2741
{
2742
	uint32_t i, idx = 0, count = 0;
2743
	struct unpacked *array;
2744
	unsigned long mem_usage = 0;
2745

2746
	CALLOC_ARRAY(array, window);
2747

2748
	for (;;) {
2749
		struct object_entry *entry;
2750
		struct unpacked *n = array + idx;
2751
		int j, max_depth, best_base = -1;
2752

2753
		progress_lock();
2754
		if (!*list_size) {
2755
			progress_unlock();
2756
			break;
2757
		}
2758
		entry = *list++;
2759
		(*list_size)--;
2760
		if (!entry->preferred_base) {
2761
			(*processed)++;
2762
			display_progress(progress_state, *processed);
2763
		}
2764
		progress_unlock();
2765

2766
		mem_usage -= free_unpacked(n);
2767
		n->entry = entry;
2768

2769
		while (window_memory_limit &&
2770
		       mem_usage > window_memory_limit &&
2771
		       count > 1) {
2772
			const uint32_t tail = (idx + window - count) % window;
2773
			mem_usage -= free_unpacked(array + tail);
2774
			count--;
2775
		}
2776

2777
		/* We do not compute delta to *create* objects we are not
2778
		 * going to pack.
2779
		 */
2780
		if (entry->preferred_base)
2781
			goto next;
2782

2783
		/*
2784
		 * If the current object is at pack edge, take the depth the
2785
		 * objects that depend on the current object into account
2786
		 * otherwise they would become too deep.
2787
		 */
2788
		max_depth = depth;
2789
		if (DELTA_CHILD(entry)) {
2790
			max_depth -= check_delta_limit(entry, 0);
2791
			if (max_depth <= 0)
2792
				goto next;
2793
		}
2794

2795
		j = window;
2796
		while (--j > 0) {
2797
			int ret;
2798
			uint32_t other_idx = idx + j;
2799
			struct unpacked *m;
2800
			if (other_idx >= window)
2801
				other_idx -= window;
2802
			m = array + other_idx;
2803
			if (!m->entry)
2804
				break;
2805
			ret = try_delta(n, m, max_depth, &mem_usage);
2806
			if (ret < 0)
2807
				break;
2808
			else if (ret > 0)
2809
				best_base = other_idx;
2810
		}
2811

2812
		/*
2813
		 * If we decided to cache the delta data, then it is best
2814
		 * to compress it right away.  First because we have to do
2815
		 * it anyway, and doing it here while we're threaded will
2816
		 * save a lot of time in the non threaded write phase,
2817
		 * as well as allow for caching more deltas within
2818
		 * the same cache size limit.
2819
		 * ...
2820
		 * But only if not writing to stdout, since in that case
2821
		 * the network is most likely throttling writes anyway,
2822
		 * and therefore it is best to go to the write phase ASAP
2823
		 * instead, as we can afford spending more time compressing
2824
		 * between writes at that moment.
2825
		 */
2826
		if (entry->delta_data && !pack_to_stdout) {
2827
			unsigned long size;
2828

2829
			size = do_compress(&entry->delta_data, DELTA_SIZE(entry));
2830
			if (size < (1U << OE_Z_DELTA_BITS)) {
2831
				entry->z_delta_size = size;
2832
				cache_lock();
2833
				delta_cache_size -= DELTA_SIZE(entry);
2834
				delta_cache_size += entry->z_delta_size;
2835
				cache_unlock();
2836
			} else {
2837
				FREE_AND_NULL(entry->delta_data);
2838
				entry->z_delta_size = 0;
2839
			}
2840
		}
2841

2842
		/* if we made n a delta, and if n is already at max
2843
		 * depth, leaving it in the window is pointless.  we
2844
		 * should evict it first.
2845
		 */
2846
		if (DELTA(entry) && max_depth <= n->depth)
2847
			continue;
2848

2849
		/*
2850
		 * Move the best delta base up in the window, after the
2851
		 * currently deltified object, to keep it longer.  It will
2852
		 * be the first base object to be attempted next.
2853
		 */
2854
		if (DELTA(entry)) {
2855
			struct unpacked swap = array[best_base];
2856
			int dist = (window + idx - best_base) % window;
2857
			int dst = best_base;
2858
			while (dist--) {
2859
				int src = (dst + 1) % window;
2860
				array[dst] = array[src];
2861
				dst = src;
2862
			}
2863
			array[dst] = swap;
2864
		}
2865

2866
		next:
2867
		idx++;
2868
		if (count + 1 < window)
2869
			count++;
2870
		if (idx >= window)
2871
			idx = 0;
2872
	}
2873

2874
	for (i = 0; i < window; ++i) {
2875
		free_delta_index(array[i].index);
2876
		free(array[i].data);
2877
	}
2878
	free(array);
2879
}
2880

2881
/*
2882
 * The main object list is split into smaller lists, each is handed to
2883
 * one worker.
2884
 *
2885
 * The main thread waits on the condition that (at least) one of the workers
2886
 * has stopped working (which is indicated in the .working member of
2887
 * struct thread_params).
2888
 *
2889
 * When a work thread has completed its work, it sets .working to 0 and
2890
 * signals the main thread and waits on the condition that .data_ready
2891
 * becomes 1.
2892
 *
2893
 * The main thread steals half of the work from the worker that has
2894
 * most work left to hand it to the idle worker.
2895
 */
2896

2897
struct thread_params {
2898
	pthread_t thread;
2899
	struct object_entry **list;
2900
	unsigned list_size;
2901
	unsigned remaining;
2902
	int window;
2903
	int depth;
2904
	int working;
2905
	int data_ready;
2906
	pthread_mutex_t mutex;
2907
	pthread_cond_t cond;
2908
	unsigned *processed;
2909
};
2910

2911
static pthread_cond_t progress_cond;
2912

2913
/*
2914
 * Mutex and conditional variable can't be statically-initialized on Windows.
2915
 */
2916
static void init_threaded_search(void)
2917
{
2918
	pthread_mutex_init(&cache_mutex, NULL);
2919
	pthread_mutex_init(&progress_mutex, NULL);
2920
	pthread_cond_init(&progress_cond, NULL);
2921
}
2922

2923
static void cleanup_threaded_search(void)
2924
{
2925
	pthread_cond_destroy(&progress_cond);
2926
	pthread_mutex_destroy(&cache_mutex);
2927
	pthread_mutex_destroy(&progress_mutex);
2928
}
2929

2930
static void *threaded_find_deltas(void *arg)
2931
{
2932
	struct thread_params *me = arg;
2933

2934
	progress_lock();
2935
	while (me->remaining) {
2936
		progress_unlock();
2937

2938
		find_deltas(me->list, &me->remaining,
2939
			    me->window, me->depth, me->processed);
2940

2941
		progress_lock();
2942
		me->working = 0;
2943
		pthread_cond_signal(&progress_cond);
2944
		progress_unlock();
2945

2946
		/*
2947
		 * We must not set ->data_ready before we wait on the
2948
		 * condition because the main thread may have set it to 1
2949
		 * before we get here. In order to be sure that new
2950
		 * work is available if we see 1 in ->data_ready, it
2951
		 * was initialized to 0 before this thread was spawned
2952
		 * and we reset it to 0 right away.
2953
		 */
2954
		pthread_mutex_lock(&me->mutex);
2955
		while (!me->data_ready)
2956
			pthread_cond_wait(&me->cond, &me->mutex);
2957
		me->data_ready = 0;
2958
		pthread_mutex_unlock(&me->mutex);
2959

2960
		progress_lock();
2961
	}
2962
	progress_unlock();
2963
	/* leave ->working 1 so that this doesn't get more work assigned */
2964
	return NULL;
2965
}
2966

2967
static void ll_find_deltas(struct object_entry **list, unsigned list_size,
2968
			   int window, int depth, unsigned *processed)
2969
{
2970
	struct thread_params *p;
2971
	int i, ret, active_threads = 0;
2972

2973
	init_threaded_search();
2974

2975
	if (delta_search_threads <= 1) {
2976
		find_deltas(list, &list_size, window, depth, processed);
2977
		cleanup_threaded_search();
2978
		return;
2979
	}
2980
	if (progress > pack_to_stdout)
2981
		fprintf_ln(stderr, _("Delta compression using up to %d threads"),
2982
			   delta_search_threads);
2983
	CALLOC_ARRAY(p, delta_search_threads);
2984

2985
	/* Partition the work amongst work threads. */
2986
	for (i = 0; i < delta_search_threads; i++) {
2987
		unsigned sub_size = list_size / (delta_search_threads - i);
2988

2989
		/* don't use too small segments or no deltas will be found */
2990
		if (sub_size < 2*window && i+1 < delta_search_threads)
2991
			sub_size = 0;
2992

2993
		p[i].window = window;
2994
		p[i].depth = depth;
2995
		p[i].processed = processed;
2996
		p[i].working = 1;
2997
		p[i].data_ready = 0;
2998

2999
		/* try to split chunks on "path" boundaries */
3000
		while (sub_size && sub_size < list_size &&
3001
		       list[sub_size]->hash &&
3002
		       list[sub_size]->hash == list[sub_size-1]->hash)
3003
			sub_size++;
3004

3005
		p[i].list = list;
3006
		p[i].list_size = sub_size;
3007
		p[i].remaining = sub_size;
3008

3009
		list += sub_size;
3010
		list_size -= sub_size;
3011
	}
3012

3013
	/* Start work threads. */
3014
	for (i = 0; i < delta_search_threads; i++) {
3015
		if (!p[i].list_size)
3016
			continue;
3017
		pthread_mutex_init(&p[i].mutex, NULL);
3018
		pthread_cond_init(&p[i].cond, NULL);
3019
		ret = pthread_create(&p[i].thread, NULL,
3020
				     threaded_find_deltas, &p[i]);
3021
		if (ret)
3022
			die(_("unable to create thread: %s"), strerror(ret));
3023
		active_threads++;
3024
	}
3025

3026
	/*
3027
	 * Now let's wait for work completion.  Each time a thread is done
3028
	 * with its work, we steal half of the remaining work from the
3029
	 * thread with the largest number of unprocessed objects and give
3030
	 * it to that newly idle thread.  This ensure good load balancing
3031
	 * until the remaining object list segments are simply too short
3032
	 * to be worth splitting anymore.
3033
	 */
3034
	while (active_threads) {
3035
		struct thread_params *target = NULL;
3036
		struct thread_params *victim = NULL;
3037
		unsigned sub_size = 0;
3038

3039
		progress_lock();
3040
		for (;;) {
3041
			for (i = 0; !target && i < delta_search_threads; i++)
3042
				if (!p[i].working)
3043
					target = &p[i];
3044
			if (target)
3045
				break;
3046
			pthread_cond_wait(&progress_cond, &progress_mutex);
3047
		}
3048

3049
		for (i = 0; i < delta_search_threads; i++)
3050
			if (p[i].remaining > 2*window &&
3051
			    (!victim || victim->remaining < p[i].remaining))
3052
				victim = &p[i];
3053
		if (victim) {
3054
			sub_size = victim->remaining / 2;
3055
			list = victim->list + victim->list_size - sub_size;
3056
			while (sub_size && list[0]->hash &&
3057
			       list[0]->hash == list[-1]->hash) {
3058
				list++;
3059
				sub_size--;
3060
			}
3061
			if (!sub_size) {
3062
				/*
3063
				 * It is possible for some "paths" to have
3064
				 * so many objects that no hash boundary
3065
				 * might be found.  Let's just steal the
3066
				 * exact half in that case.
3067
				 */
3068
				sub_size = victim->remaining / 2;
3069
				list -= sub_size;
3070
			}
3071
			target->list = list;
3072
			victim->list_size -= sub_size;
3073
			victim->remaining -= sub_size;
3074
		}
3075
		target->list_size = sub_size;
3076
		target->remaining = sub_size;
3077
		target->working = 1;
3078
		progress_unlock();
3079

3080
		pthread_mutex_lock(&target->mutex);
3081
		target->data_ready = 1;
3082
		pthread_cond_signal(&target->cond);
3083
		pthread_mutex_unlock(&target->mutex);
3084

3085
		if (!sub_size) {
3086
			pthread_join(target->thread, NULL);
3087
			pthread_cond_destroy(&target->cond);
3088
			pthread_mutex_destroy(&target->mutex);
3089
			active_threads--;
3090
		}
3091
	}
3092
	cleanup_threaded_search();
3093
	free(p);
3094
}
3095

3096
static int obj_is_packed(const struct object_id *oid)
3097
{
3098
	return packlist_find(&to_pack, oid) ||
3099
		(reuse_packfile_bitmap &&
3100
		 bitmap_walk_contains(bitmap_git, reuse_packfile_bitmap, oid));
3101
}
3102

3103
static void add_tag_chain(const struct object_id *oid)
3104
{
3105
	struct tag *tag;
3106

3107
	/*
3108
	 * We catch duplicates already in add_object_entry(), but we'd
3109
	 * prefer to do this extra check to avoid having to parse the
3110
	 * tag at all if we already know that it's being packed (e.g., if
3111
	 * it was included via bitmaps, we would not have parsed it
3112
	 * previously).
3113
	 */
3114
	if (obj_is_packed(oid))
3115
		return;
3116

3117
	tag = lookup_tag(the_repository, oid);
3118
	while (1) {
3119
		if (!tag || parse_tag(tag) || !tag->tagged)
3120
			die(_("unable to pack objects reachable from tag %s"),
3121
			    oid_to_hex(oid));
3122

3123
		add_object_entry(&tag->object.oid, OBJ_TAG, NULL, 0);
3124

3125
		if (tag->tagged->type != OBJ_TAG)
3126
			return;
3127

3128
		tag = (struct tag *)tag->tagged;
3129
	}
3130
}
3131

3132
static int add_ref_tag(const char *tag UNUSED, const char *referent UNUSED, const struct object_id *oid,
3133
		       int flag UNUSED, void *cb_data UNUSED)
3134
{
3135
	struct object_id peeled;
3136

3137
	if (!peel_iterated_oid(the_repository, oid, &peeled) && obj_is_packed(&peeled))
3138
		add_tag_chain(oid);
3139
	return 0;
3140
}
3141

3142
static void prepare_pack(int window, int depth)
3143
{
3144
	struct object_entry **delta_list;
3145
	uint32_t i, nr_deltas;
3146
	unsigned n;
3147

3148
	if (use_delta_islands)
3149
		resolve_tree_islands(the_repository, progress, &to_pack);
3150

3151
	get_object_details();
3152

3153
	/*
3154
	 * If we're locally repacking then we need to be doubly careful
3155
	 * from now on in order to make sure no stealth corruption gets
3156
	 * propagated to the new pack.  Clients receiving streamed packs
3157
	 * should validate everything they get anyway so no need to incur
3158
	 * the additional cost here in that case.
3159
	 */
3160
	if (!pack_to_stdout)
3161
		do_check_packed_object_crc = 1;
3162

3163
	if (!to_pack.nr_objects || !window || !depth)
3164
		return;
3165

3166
	ALLOC_ARRAY(delta_list, to_pack.nr_objects);
3167
	nr_deltas = n = 0;
3168

3169
	for (i = 0; i < to_pack.nr_objects; i++) {
3170
		struct object_entry *entry = to_pack.objects + i;
3171

3172
		if (DELTA(entry))
3173
			/* This happens if we decided to reuse existing
3174
			 * delta from a pack.  "reuse_delta &&" is implied.
3175
			 */
3176
			continue;
3177

3178
		if (!entry->type_valid ||
3179
		    oe_size_less_than(&to_pack, entry, 50))
3180
			continue;
3181

3182
		if (entry->no_try_delta)
3183
			continue;
3184

3185
		if (!entry->preferred_base) {
3186
			nr_deltas++;
3187
			if (oe_type(entry) < 0)
3188
				die(_("unable to get type of object %s"),
3189
				    oid_to_hex(&entry->idx.oid));
3190
		} else {
3191
			if (oe_type(entry) < 0) {
3192
				/*
3193
				 * This object is not found, but we
3194
				 * don't have to include it anyway.
3195
				 */
3196
				continue;
3197
			}
3198
		}
3199

3200
		delta_list[n++] = entry;
3201
	}
3202

3203
	if (nr_deltas && n > 1) {
3204
		unsigned nr_done = 0;
3205

3206
		if (progress)
3207
			progress_state = start_progress(_("Compressing objects"),
3208
							nr_deltas);
3209
		QSORT(delta_list, n, type_size_sort);
3210
		ll_find_deltas(delta_list, n, window+1, depth, &nr_done);
3211
		stop_progress(&progress_state);
3212
		if (nr_done != nr_deltas)
3213
			die(_("inconsistency with delta count"));
3214
	}
3215
	free(delta_list);
3216
}
3217

3218
static int git_pack_config(const char *k, const char *v,
3219
			   const struct config_context *ctx, void *cb)
3220
{
3221
	if (!strcmp(k, "pack.window")) {
3222
		window = git_config_int(k, v, ctx->kvi);
3223
		return 0;
3224
	}
3225
	if (!strcmp(k, "pack.windowmemory")) {
3226
		window_memory_limit = git_config_ulong(k, v, ctx->kvi);
3227
		return 0;
3228
	}
3229
	if (!strcmp(k, "pack.depth")) {
3230
		depth = git_config_int(k, v, ctx->kvi);
3231
		return 0;
3232
	}
3233
	if (!strcmp(k, "pack.deltacachesize")) {
3234
		max_delta_cache_size = git_config_int(k, v, ctx->kvi);
3235
		return 0;
3236
	}
3237
	if (!strcmp(k, "pack.deltacachelimit")) {
3238
		cache_max_small_delta_size = git_config_int(k, v, ctx->kvi);
3239
		return 0;
3240
	}
3241
	if (!strcmp(k, "pack.writebitmaphashcache")) {
3242
		if (git_config_bool(k, v))
3243
			write_bitmap_options |= BITMAP_OPT_HASH_CACHE;
3244
		else
3245
			write_bitmap_options &= ~BITMAP_OPT_HASH_CACHE;
3246
	}
3247

3248
	if (!strcmp(k, "pack.writebitmaplookuptable")) {
3249
		if (git_config_bool(k, v))
3250
			write_bitmap_options |= BITMAP_OPT_LOOKUP_TABLE;
3251
		else
3252
			write_bitmap_options &= ~BITMAP_OPT_LOOKUP_TABLE;
3253
	}
3254

3255
	if (!strcmp(k, "pack.usebitmaps")) {
3256
		use_bitmap_index_default = git_config_bool(k, v);
3257
		return 0;
3258
	}
3259
	if (!strcmp(k, "pack.allowpackreuse")) {
3260
		int res = git_parse_maybe_bool_text(v);
3261
		if (res < 0) {
3262
			if (!strcasecmp(v, "single"))
3263
				allow_pack_reuse = SINGLE_PACK_REUSE;
3264
			else if (!strcasecmp(v, "multi"))
3265
				allow_pack_reuse = MULTI_PACK_REUSE;
3266
			else
3267
				die(_("invalid pack.allowPackReuse value: '%s'"), v);
3268
		} else if (res) {
3269
			allow_pack_reuse = SINGLE_PACK_REUSE;
3270
		} else {
3271
			allow_pack_reuse = NO_PACK_REUSE;
3272
		}
3273
		return 0;
3274
	}
3275
	if (!strcmp(k, "pack.threads")) {
3276
		delta_search_threads = git_config_int(k, v, ctx->kvi);
3277
		if (delta_search_threads < 0)
3278
			die(_("invalid number of threads specified (%d)"),
3279
			    delta_search_threads);
3280
		if (!HAVE_THREADS && delta_search_threads != 1) {
3281
			warning(_("no threads support, ignoring %s"), k);
3282
			delta_search_threads = 0;
3283
		}
3284
		return 0;
3285
	}
3286
	if (!strcmp(k, "pack.indexversion")) {
3287
		pack_idx_opts.version = git_config_int(k, v, ctx->kvi);
3288
		if (pack_idx_opts.version > 2)
3289
			die(_("bad pack.indexVersion=%"PRIu32),
3290
			    pack_idx_opts.version);
3291
		return 0;
3292
	}
3293
	if (!strcmp(k, "pack.writereverseindex")) {
3294
		if (git_config_bool(k, v))
3295
			pack_idx_opts.flags |= WRITE_REV;
3296
		else
3297
			pack_idx_opts.flags &= ~WRITE_REV;
3298
		return 0;
3299
	}
3300
	if (!strcmp(k, "uploadpack.blobpackfileuri")) {
3301
		struct configured_exclusion *ex;
3302
		const char *oid_end, *pack_end;
3303
		/*
3304
		 * Stores the pack hash. This is not a true object ID, but is
3305
		 * of the same form.
3306
		 */
3307
		struct object_id pack_hash;
3308

3309
		if (!v)
3310
			return config_error_nonbool(k);
3311

3312
		ex = xmalloc(sizeof(*ex));
3313
		if (parse_oid_hex(v, &ex->e.oid, &oid_end) ||
3314
		    *oid_end != ' ' ||
3315
		    parse_oid_hex(oid_end + 1, &pack_hash, &pack_end) ||
3316
		    *pack_end != ' ')
3317
			die(_("value of uploadpack.blobpackfileuri must be "
3318
			      "of the form '<object-hash> <pack-hash> <uri>' (got '%s')"), v);
3319
		if (oidmap_get(&configured_exclusions, &ex->e.oid))
3320
			die(_("object already configured in another "
3321
			      "uploadpack.blobpackfileuri (got '%s')"), v);
3322
		ex->pack_hash_hex = xcalloc(1, pack_end - oid_end);
3323
		memcpy(ex->pack_hash_hex, oid_end + 1, pack_end - oid_end - 1);
3324
		ex->uri = xstrdup(pack_end + 1);
3325
		oidmap_put(&configured_exclusions, ex);
3326
	}
3327
	return git_default_config(k, v, ctx, cb);
3328
}
3329

3330
/* Counters for trace2 output when in --stdin-packs mode. */
3331
static int stdin_packs_found_nr;
3332
static int stdin_packs_hints_nr;
3333

3334
static int add_object_entry_from_pack(const struct object_id *oid,
3335
				      struct packed_git *p,
3336
				      uint32_t pos,
3337
				      void *_data)
3338
{
3339
	off_t ofs;
3340
	enum object_type type = OBJ_NONE;
3341

3342
	display_progress(progress_state, ++nr_seen);
3343

3344
	if (have_duplicate_entry(oid, 0))
3345
		return 0;
3346

3347
	ofs = nth_packed_object_offset(p, pos);
3348
	if (!want_object_in_pack(oid, 0, &p, &ofs))
3349
		return 0;
3350

3351
	if (p) {
3352
		struct rev_info *revs = _data;
3353
		struct object_info oi = OBJECT_INFO_INIT;
3354

3355
		oi.typep = &type;
3356
		if (packed_object_info(the_repository, p, ofs, &oi) < 0) {
3357
			die(_("could not get type of object %s in pack %s"),
3358
			    oid_to_hex(oid), p->pack_name);
3359
		} else if (type == OBJ_COMMIT) {
3360
			/*
3361
			 * commits in included packs are used as starting points for the
3362
			 * subsequent revision walk
3363
			 */
3364
			add_pending_oid(revs, NULL, oid, 0);
3365
		}
3366

3367
		stdin_packs_found_nr++;
3368
	}
3369

3370
	create_object_entry(oid, type, 0, 0, 0, p, ofs);
3371

3372
	return 0;
3373
}
3374

3375
static void show_commit_pack_hint(struct commit *commit UNUSED,
3376
				  void *data UNUSED)
3377
{
3378
	/* nothing to do; commits don't have a namehash */
3379
}
3380

3381
static void show_object_pack_hint(struct object *object, const char *name,
3382
				  void *data UNUSED)
3383
{
3384
	struct object_entry *oe = packlist_find(&to_pack, &object->oid);
3385
	if (!oe)
3386
		return;
3387

3388
	/*
3389
	 * Our 'to_pack' list was constructed by iterating all objects packed in
3390
	 * included packs, and so doesn't have a non-zero hash field that you
3391
	 * would typically pick up during a reachability traversal.
3392
	 *
3393
	 * Make a best-effort attempt to fill in the ->hash and ->no_try_delta
3394
	 * here using a now in order to perhaps improve the delta selection
3395
	 * process.
3396
	 */
3397
	oe->hash = pack_name_hash(name);
3398
	oe->no_try_delta = name && no_try_delta(name);
3399

3400
	stdin_packs_hints_nr++;
3401
}
3402

3403
static int pack_mtime_cmp(const void *_a, const void *_b)
3404
{
3405
	struct packed_git *a = ((const struct string_list_item*)_a)->util;
3406
	struct packed_git *b = ((const struct string_list_item*)_b)->util;
3407

3408
	/*
3409
	 * order packs by descending mtime so that objects are laid out
3410
	 * roughly as newest-to-oldest
3411
	 */
3412
	if (a->mtime < b->mtime)
3413
		return 1;
3414
	else if (b->mtime < a->mtime)
3415
		return -1;
3416
	else
3417
		return 0;
3418
}
3419

3420
static void read_packs_list_from_stdin(void)
3421
{
3422
	struct strbuf buf = STRBUF_INIT;
3423
	struct string_list include_packs = STRING_LIST_INIT_DUP;
3424
	struct string_list exclude_packs = STRING_LIST_INIT_DUP;
3425
	struct string_list_item *item = NULL;
3426

3427
	struct packed_git *p;
3428
	struct rev_info revs;
3429

3430
	repo_init_revisions(the_repository, &revs, NULL);
3431
	/*
3432
	 * Use a revision walk to fill in the namehash of objects in the include
3433
	 * packs. To save time, we'll avoid traversing through objects that are
3434
	 * in excluded packs.
3435
	 *
3436
	 * That may cause us to avoid populating all of the namehash fields of
3437
	 * all included objects, but our goal is best-effort, since this is only
3438
	 * an optimization during delta selection.
3439
	 */
3440
	revs.no_kept_objects = 1;
3441
	revs.keep_pack_cache_flags |= IN_CORE_KEEP_PACKS;
3442
	revs.blob_objects = 1;
3443
	revs.tree_objects = 1;
3444
	revs.tag_objects = 1;
3445
	revs.ignore_missing_links = 1;
3446

3447
	while (strbuf_getline(&buf, stdin) != EOF) {
3448
		if (!buf.len)
3449
			continue;
3450

3451
		if (*buf.buf == '^')
3452
			string_list_append(&exclude_packs, buf.buf + 1);
3453
		else
3454
			string_list_append(&include_packs, buf.buf);
3455

3456
		strbuf_reset(&buf);
3457
	}
3458

3459
	string_list_sort(&include_packs);
3460
	string_list_remove_duplicates(&include_packs, 0);
3461
	string_list_sort(&exclude_packs);
3462
	string_list_remove_duplicates(&exclude_packs, 0);
3463

3464
	for (p = get_all_packs(the_repository); p; p = p->next) {
3465
		const char *pack_name = pack_basename(p);
3466

3467
		if ((item = string_list_lookup(&include_packs, pack_name)))
3468
			item->util = p;
3469
		if ((item = string_list_lookup(&exclude_packs, pack_name)))
3470
			item->util = p;
3471
	}
3472

3473
	/*
3474
	 * Arguments we got on stdin may not even be packs. First
3475
	 * check that to avoid segfaulting later on in
3476
	 * e.g. pack_mtime_cmp(), excluded packs are handled below.
3477
	 *
3478
	 * Since we first parsed our STDIN and then sorted the input
3479
	 * lines the pack we error on will be whatever line happens to
3480
	 * sort first. This is lazy, it's enough that we report one
3481
	 * bad case here, we don't need to report the first/last one,
3482
	 * or all of them.
3483
	 */
3484
	for_each_string_list_item(item, &include_packs) {
3485
		struct packed_git *p = item->util;
3486
		if (!p)
3487
			die(_("could not find pack '%s'"), item->string);
3488
		if (!is_pack_valid(p))
3489
			die(_("packfile %s cannot be accessed"), p->pack_name);
3490
	}
3491

3492
	/*
3493
	 * Then, handle all of the excluded packs, marking them as
3494
	 * kept in-core so that later calls to add_object_entry()
3495
	 * discards any objects that are also found in excluded packs.
3496
	 */
3497
	for_each_string_list_item(item, &exclude_packs) {
3498
		struct packed_git *p = item->util;
3499
		if (!p)
3500
			die(_("could not find pack '%s'"), item->string);
3501
		p->pack_keep_in_core = 1;
3502
	}
3503

3504
	/*
3505
	 * Order packs by ascending mtime; use QSORT directly to access the
3506
	 * string_list_item's ->util pointer, which string_list_sort() does not
3507
	 * provide.
3508
	 */
3509
	QSORT(include_packs.items, include_packs.nr, pack_mtime_cmp);
3510

3511
	for_each_string_list_item(item, &include_packs) {
3512
		struct packed_git *p = item->util;
3513
		for_each_object_in_pack(p,
3514
					add_object_entry_from_pack,
3515
					&revs,
3516
					FOR_EACH_OBJECT_PACK_ORDER);
3517
	}
3518

3519
	if (prepare_revision_walk(&revs))
3520
		die(_("revision walk setup failed"));
3521
	traverse_commit_list(&revs,
3522
			     show_commit_pack_hint,
3523
			     show_object_pack_hint,
3524
			     NULL);
3525

3526
	trace2_data_intmax("pack-objects", the_repository, "stdin_packs_found",
3527
			   stdin_packs_found_nr);
3528
	trace2_data_intmax("pack-objects", the_repository, "stdin_packs_hints",
3529
			   stdin_packs_hints_nr);
3530

3531
	strbuf_release(&buf);
3532
	string_list_clear(&include_packs, 0);
3533
	string_list_clear(&exclude_packs, 0);
3534
}
3535

3536
static void add_cruft_object_entry(const struct object_id *oid, enum object_type type,
3537
				   struct packed_git *pack, off_t offset,
3538
				   const char *name, uint32_t mtime)
3539
{
3540
	struct object_entry *entry;
3541

3542
	display_progress(progress_state, ++nr_seen);
3543

3544
	entry = packlist_find(&to_pack, oid);
3545
	if (entry) {
3546
		if (name) {
3547
			entry->hash = pack_name_hash(name);
3548
			entry->no_try_delta = no_try_delta(name);
3549
		}
3550
	} else {
3551
		if (!want_object_in_pack(oid, 0, &pack, &offset))
3552
			return;
3553
		if (!pack && type == OBJ_BLOB && !has_loose_object(oid)) {
3554
			/*
3555
			 * If a traversed tree has a missing blob then we want
3556
			 * to avoid adding that missing object to our pack.
3557
			 *
3558
			 * This only applies to missing blobs, not trees,
3559
			 * because the traversal needs to parse sub-trees but
3560
			 * not blobs.
3561
			 *
3562
			 * Note we only perform this check when we couldn't
3563
			 * already find the object in a pack, so we're really
3564
			 * limited to "ensure non-tip blobs which don't exist in
3565
			 * packs do exist via loose objects". Confused?
3566
			 */
3567
			return;
3568
		}
3569

3570
		entry = create_object_entry(oid, type, pack_name_hash(name),
3571
					    0, name && no_try_delta(name),
3572
					    pack, offset);
3573
	}
3574

3575
	if (mtime > oe_cruft_mtime(&to_pack, entry))
3576
		oe_set_cruft_mtime(&to_pack, entry, mtime);
3577
	return;
3578
}
3579

3580
static void show_cruft_object(struct object *obj, const char *name, void *data UNUSED)
3581
{
3582
	/*
3583
	 * if we did not record it earlier, it's at least as old as our
3584
	 * expiration value. Rather than find it exactly, just use that
3585
	 * value.  This may bump it forward from its real mtime, but it
3586
	 * will still be "too old" next time we run with the same
3587
	 * expiration.
3588
	 *
3589
	 * if obj does appear in the packing list, this call is a noop (or may
3590
	 * set the namehash).
3591
	 */
3592
	add_cruft_object_entry(&obj->oid, obj->type, NULL, 0, name, cruft_expiration);
3593
}
3594

3595
static void show_cruft_commit(struct commit *commit, void *data)
3596
{
3597
	show_cruft_object((struct object*)commit, NULL, data);
3598
}
3599

3600
static int cruft_include_check_obj(struct object *obj, void *data UNUSED)
3601
{
3602
	return !has_object_kept_pack(&obj->oid, IN_CORE_KEEP_PACKS);
3603
}
3604

3605
static int cruft_include_check(struct commit *commit, void *data)
3606
{
3607
	return cruft_include_check_obj((struct object*)commit, data);
3608
}
3609

3610
static void set_cruft_mtime(const struct object *object,
3611
			    struct packed_git *pack,
3612
			    off_t offset, time_t mtime)
3613
{
3614
	add_cruft_object_entry(&object->oid, object->type, pack, offset, NULL,
3615
			       mtime);
3616
}
3617

3618
static void mark_pack_kept_in_core(struct string_list *packs, unsigned keep)
3619
{
3620
	struct string_list_item *item = NULL;
3621
	for_each_string_list_item(item, packs) {
3622
		struct packed_git *p = item->util;
3623
		if (!p)
3624
			die(_("could not find pack '%s'"), item->string);
3625
		p->pack_keep_in_core = keep;
3626
	}
3627
}
3628

3629
static void add_unreachable_loose_objects(void);
3630
static void add_objects_in_unpacked_packs(void);
3631

3632
static void enumerate_cruft_objects(void)
3633
{
3634
	if (progress)
3635
		progress_state = start_progress(_("Enumerating cruft objects"), 0);
3636

3637
	add_objects_in_unpacked_packs();
3638
	add_unreachable_loose_objects();
3639

3640
	stop_progress(&progress_state);
3641
}
3642

3643
static void enumerate_and_traverse_cruft_objects(struct string_list *fresh_packs)
3644
{
3645
	struct packed_git *p;
3646
	struct rev_info revs;
3647
	int ret;
3648

3649
	repo_init_revisions(the_repository, &revs, NULL);
3650

3651
	revs.tag_objects = 1;
3652
	revs.tree_objects = 1;
3653
	revs.blob_objects = 1;
3654

3655
	revs.include_check = cruft_include_check;
3656
	revs.include_check_obj = cruft_include_check_obj;
3657

3658
	revs.ignore_missing_links = 1;
3659

3660
	if (progress)
3661
		progress_state = start_progress(_("Enumerating cruft objects"), 0);
3662
	ret = add_unseen_recent_objects_to_traversal(&revs, cruft_expiration,
3663
						     set_cruft_mtime, 1);
3664
	stop_progress(&progress_state);
3665

3666
	if (ret)
3667
		die(_("unable to add cruft objects"));
3668

3669
	/*
3670
	 * Re-mark only the fresh packs as kept so that objects in
3671
	 * unknown packs do not halt the reachability traversal early.
3672
	 */
3673
	for (p = get_all_packs(the_repository); p; p = p->next)
3674
		p->pack_keep_in_core = 0;
3675
	mark_pack_kept_in_core(fresh_packs, 1);
3676

3677
	if (prepare_revision_walk(&revs))
3678
		die(_("revision walk setup failed"));
3679
	if (progress)
3680
		progress_state = start_progress(_("Traversing cruft objects"), 0);
3681
	nr_seen = 0;
3682
	traverse_commit_list(&revs, show_cruft_commit, show_cruft_object, NULL);
3683

3684
	stop_progress(&progress_state);
3685
}
3686

3687
static void read_cruft_objects(void)
3688
{
3689
	struct strbuf buf = STRBUF_INIT;
3690
	struct string_list discard_packs = STRING_LIST_INIT_DUP;
3691
	struct string_list fresh_packs = STRING_LIST_INIT_DUP;
3692
	struct packed_git *p;
3693

3694
	ignore_packed_keep_in_core = 1;
3695

3696
	while (strbuf_getline(&buf, stdin) != EOF) {
3697
		if (!buf.len)
3698
			continue;
3699

3700
		if (*buf.buf == '-')
3701
			string_list_append(&discard_packs, buf.buf + 1);
3702
		else
3703
			string_list_append(&fresh_packs, buf.buf);
3704
	}
3705

3706
	string_list_sort(&discard_packs);
3707
	string_list_sort(&fresh_packs);
3708

3709
	for (p = get_all_packs(the_repository); p; p = p->next) {
3710
		const char *pack_name = pack_basename(p);
3711
		struct string_list_item *item;
3712

3713
		item = string_list_lookup(&fresh_packs, pack_name);
3714
		if (!item)
3715
			item = string_list_lookup(&discard_packs, pack_name);
3716

3717
		if (item) {
3718
			item->util = p;
3719
		} else {
3720
			/*
3721
			 * This pack wasn't mentioned in either the "fresh" or
3722
			 * "discard" list, so the caller didn't know about it.
3723
			 *
3724
			 * Mark it as kept so that its objects are ignored by
3725
			 * add_unseen_recent_objects_to_traversal(). We'll
3726
			 * unmark it before starting the traversal so it doesn't
3727
			 * halt the traversal early.
3728
			 */
3729
			p->pack_keep_in_core = 1;
3730
		}
3731
	}
3732

3733
	mark_pack_kept_in_core(&fresh_packs, 1);
3734
	mark_pack_kept_in_core(&discard_packs, 0);
3735

3736
	if (cruft_expiration)
3737
		enumerate_and_traverse_cruft_objects(&fresh_packs);
3738
	else
3739
		enumerate_cruft_objects();
3740

3741
	strbuf_release(&buf);
3742
	string_list_clear(&discard_packs, 0);
3743
	string_list_clear(&fresh_packs, 0);
3744
}
3745

3746
static void read_object_list_from_stdin(void)
3747
{
3748
	char line[GIT_MAX_HEXSZ + 1 + PATH_MAX + 2];
3749
	struct object_id oid;
3750
	const char *p;
3751

3752
	for (;;) {
3753
		if (!fgets(line, sizeof(line), stdin)) {
3754
			if (feof(stdin))
3755
				break;
3756
			if (!ferror(stdin))
3757
				BUG("fgets returned NULL, not EOF, not error!");
3758
			if (errno != EINTR)
3759
				die_errno("fgets");
3760
			clearerr(stdin);
3761
			continue;
3762
		}
3763
		if (line[0] == '-') {
3764
			if (get_oid_hex(line+1, &oid))
3765
				die(_("expected edge object ID, got garbage:\n %s"),
3766
				    line);
3767
			add_preferred_base(&oid);
3768
			continue;
3769
		}
3770
		if (parse_oid_hex(line, &oid, &p))
3771
			die(_("expected object ID, got garbage:\n %s"), line);
3772

3773
		add_preferred_base_object(p + 1);
3774
		add_object_entry(&oid, OBJ_NONE, p + 1, 0);
3775
	}
3776
}
3777

3778
static void show_commit(struct commit *commit, void *data UNUSED)
3779
{
3780
	add_object_entry(&commit->object.oid, OBJ_COMMIT, NULL, 0);
3781

3782
	if (write_bitmap_index)
3783
		index_commit_for_bitmap(commit);
3784

3785
	if (use_delta_islands)
3786
		propagate_island_marks(commit);
3787
}
3788

3789
static void show_object(struct object *obj, const char *name,
3790
			void *data UNUSED)
3791
{
3792
	add_preferred_base_object(name);
3793
	add_object_entry(&obj->oid, obj->type, name, 0);
3794

3795
	if (use_delta_islands) {
3796
		const char *p;
3797
		unsigned depth;
3798
		struct object_entry *ent;
3799

3800
		/* the empty string is a root tree, which is depth 0 */
3801
		depth = *name ? 1 : 0;
3802
		for (p = strchr(name, '/'); p; p = strchr(p + 1, '/'))
3803
			depth++;
3804

3805
		ent = packlist_find(&to_pack, &obj->oid);
3806
		if (ent && depth > oe_tree_depth(&to_pack, ent))
3807
			oe_set_tree_depth(&to_pack, ent, depth);
3808
	}
3809
}
3810

3811
static void show_object__ma_allow_any(struct object *obj, const char *name, void *data)
3812
{
3813
	assert(arg_missing_action == MA_ALLOW_ANY);
3814

3815
	/*
3816
	 * Quietly ignore ALL missing objects.  This avoids problems with
3817
	 * staging them now and getting an odd error later.
3818
	 */
3819
	if (!has_object(the_repository, &obj->oid, 0))
3820
		return;
3821

3822
	show_object(obj, name, data);
3823
}
3824

3825
static void show_object__ma_allow_promisor(struct object *obj, const char *name, void *data)
3826
{
3827
	assert(arg_missing_action == MA_ALLOW_PROMISOR);
3828

3829
	/*
3830
	 * Quietly ignore EXPECTED missing objects.  This avoids problems with
3831
	 * staging them now and getting an odd error later.
3832
	 */
3833
	if (!has_object(the_repository, &obj->oid, 0) && is_promisor_object(&obj->oid))
3834
		return;
3835

3836
	show_object(obj, name, data);
3837
}
3838

3839
static int option_parse_missing_action(const struct option *opt UNUSED,
3840
				       const char *arg, int unset)
3841
{
3842
	assert(arg);
3843
	assert(!unset);
3844

3845
	if (!strcmp(arg, "error")) {
3846
		arg_missing_action = MA_ERROR;
3847
		fn_show_object = show_object;
3848
		return 0;
3849
	}
3850

3851
	if (!strcmp(arg, "allow-any")) {
3852
		arg_missing_action = MA_ALLOW_ANY;
3853
		fetch_if_missing = 0;
3854
		fn_show_object = show_object__ma_allow_any;
3855
		return 0;
3856
	}
3857

3858
	if (!strcmp(arg, "allow-promisor")) {
3859
		arg_missing_action = MA_ALLOW_PROMISOR;
3860
		fetch_if_missing = 0;
3861
		fn_show_object = show_object__ma_allow_promisor;
3862
		return 0;
3863
	}
3864

3865
	die(_("invalid value for '%s': '%s'"), "--missing", arg);
3866
	return 0;
3867
}
3868

3869
static void show_edge(struct commit *commit)
3870
{
3871
	add_preferred_base(&commit->object.oid);
3872
}
3873

3874
static int add_object_in_unpacked_pack(const struct object_id *oid,
3875
				       struct packed_git *pack,
3876
				       uint32_t pos,
3877
				       void *data UNUSED)
3878
{
3879
	if (cruft) {
3880
		off_t offset;
3881
		time_t mtime;
3882

3883
		if (pack->is_cruft) {
3884
			if (load_pack_mtimes(pack) < 0)
3885
				die(_("could not load cruft pack .mtimes"));
3886
			mtime = nth_packed_mtime(pack, pos);
3887
		} else {
3888
			mtime = pack->mtime;
3889
		}
3890
		offset = nth_packed_object_offset(pack, pos);
3891

3892
		add_cruft_object_entry(oid, OBJ_NONE, pack, offset,
3893
				       NULL, mtime);
3894
	} else {
3895
		add_object_entry(oid, OBJ_NONE, "", 0);
3896
	}
3897
	return 0;
3898
}
3899

3900
static void add_objects_in_unpacked_packs(void)
3901
{
3902
	if (for_each_packed_object(add_object_in_unpacked_pack, NULL,
3903
				   FOR_EACH_OBJECT_PACK_ORDER |
3904
				   FOR_EACH_OBJECT_LOCAL_ONLY |
3905
				   FOR_EACH_OBJECT_SKIP_IN_CORE_KEPT_PACKS |
3906
				   FOR_EACH_OBJECT_SKIP_ON_DISK_KEPT_PACKS))
3907
		die(_("cannot open pack index"));
3908
}
3909

3910
static int add_loose_object(const struct object_id *oid, const char *path,
3911
			    void *data UNUSED)
3912
{
3913
	enum object_type type = oid_object_info(the_repository, oid, NULL);
3914

3915
	if (type < 0) {
3916
		warning(_("loose object at %s could not be examined"), path);
3917
		return 0;
3918
	}
3919

3920
	if (cruft) {
3921
		struct stat st;
3922
		if (stat(path, &st) < 0) {
3923
			if (errno == ENOENT)
3924
				return 0;
3925
			return error_errno("unable to stat %s", oid_to_hex(oid));
3926
		}
3927

3928
		add_cruft_object_entry(oid, type, NULL, 0, NULL,
3929
				       st.st_mtime);
3930
	} else {
3931
		add_object_entry(oid, type, "", 0);
3932
	}
3933
	return 0;
3934
}
3935

3936
/*
3937
 * We actually don't even have to worry about reachability here.
3938
 * add_object_entry will weed out duplicates, so we just add every
3939
 * loose object we find.
3940
 */
3941
static void add_unreachable_loose_objects(void)
3942
{
3943
	for_each_loose_file_in_objdir(get_object_directory(),
3944
				      add_loose_object,
3945
				      NULL, NULL, NULL);
3946
}
3947

3948
static int has_sha1_pack_kept_or_nonlocal(const struct object_id *oid)
3949
{
3950
	static struct packed_git *last_found = (void *)1;
3951
	struct packed_git *p;
3952

3953
	p = (last_found != (void *)1) ? last_found :
3954
					get_all_packs(the_repository);
3955

3956
	while (p) {
3957
		if ((!p->pack_local || p->pack_keep ||
3958
				p->pack_keep_in_core) &&
3959
			find_pack_entry_one(oid->hash, p)) {
3960
			last_found = p;
3961
			return 1;
3962
		}
3963
		if (p == last_found)
3964
			p = get_all_packs(the_repository);
3965
		else
3966
			p = p->next;
3967
		if (p == last_found)
3968
			p = p->next;
3969
	}
3970
	return 0;
3971
}
3972

3973
/*
3974
 * Store a list of sha1s that are should not be discarded
3975
 * because they are either written too recently, or are
3976
 * reachable from another object that was.
3977
 *
3978
 * This is filled by get_object_list.
3979
 */
3980
static struct oid_array recent_objects;
3981

3982
static int loosened_object_can_be_discarded(const struct object_id *oid,
3983
					    timestamp_t mtime)
3984
{
3985
	if (!unpack_unreachable_expiration)
3986
		return 0;
3987
	if (mtime > unpack_unreachable_expiration)
3988
		return 0;
3989
	if (oid_array_lookup(&recent_objects, oid) >= 0)
3990
		return 0;
3991
	return 1;
3992
}
3993

3994
static void loosen_unused_packed_objects(void)
3995
{
3996
	struct packed_git *p;
3997
	uint32_t i;
3998
	uint32_t loosened_objects_nr = 0;
3999
	struct object_id oid;
4000

4001
	for (p = get_all_packs(the_repository); p; p = p->next) {
4002
		if (!p->pack_local || p->pack_keep || p->pack_keep_in_core)
4003
			continue;
4004

4005
		if (open_pack_index(p))
4006
			die(_("cannot open pack index"));
4007

4008
		for (i = 0; i < p->num_objects; i++) {
4009
			nth_packed_object_id(&oid, p, i);
4010
			if (!packlist_find(&to_pack, &oid) &&
4011
			    !has_sha1_pack_kept_or_nonlocal(&oid) &&
4012
			    !loosened_object_can_be_discarded(&oid, p->mtime)) {
4013
				if (force_object_loose(&oid, p->mtime))
4014
					die(_("unable to force loose object"));
4015
				loosened_objects_nr++;
4016
			}
4017
		}
4018
	}
4019

4020
	trace2_data_intmax("pack-objects", the_repository,
4021
			   "loosen_unused_packed_objects/loosened", loosened_objects_nr);
4022
}
4023

4024
/*
4025
 * This tracks any options which pack-reuse code expects to be on, or which a
4026
 * reader of the pack might not understand, and which would therefore prevent
4027
 * blind reuse of what we have on disk.
4028
 */
4029
static int pack_options_allow_reuse(void)
4030
{
4031
	return allow_pack_reuse != NO_PACK_REUSE &&
4032
	       pack_to_stdout &&
4033
	       !ignore_packed_keep_on_disk &&
4034
	       !ignore_packed_keep_in_core &&
4035
	       (!local || !have_non_local_packs) &&
4036
	       !incremental;
4037
}
4038

4039
static int get_object_list_from_bitmap(struct rev_info *revs)
4040
{
4041
	if (!(bitmap_git = prepare_bitmap_walk(revs, 0)))
4042
		return -1;
4043

4044
	if (pack_options_allow_reuse())
4045
		reuse_partial_packfile_from_bitmap(bitmap_git,
4046
						   &reuse_packfiles,
4047
						   &reuse_packfiles_nr,
4048
						   &reuse_packfile_bitmap,
4049
						   allow_pack_reuse == MULTI_PACK_REUSE);
4050

4051
	if (reuse_packfiles) {
4052
		reuse_packfile_objects = bitmap_popcount(reuse_packfile_bitmap);
4053
		if (!reuse_packfile_objects)
4054
			BUG("expected non-empty reuse bitmap");
4055

4056
		nr_result += reuse_packfile_objects;
4057
		nr_seen += reuse_packfile_objects;
4058
		display_progress(progress_state, nr_seen);
4059
	}
4060

4061
	traverse_bitmap_commit_list(bitmap_git, revs,
4062
				    &add_object_entry_from_bitmap);
4063
	return 0;
4064
}
4065

4066
static void record_recent_object(struct object *obj,
4067
				 const char *name UNUSED,
4068
				 void *data UNUSED)
4069
{
4070
	oid_array_append(&recent_objects, &obj->oid);
4071
}
4072

4073
static void record_recent_commit(struct commit *commit, void *data UNUSED)
4074
{
4075
	oid_array_append(&recent_objects, &commit->object.oid);
4076
}
4077

4078
static int mark_bitmap_preferred_tip(const char *refname,
4079
				     const char *referent UNUSED,
4080
				     const struct object_id *oid,
4081
				     int flags UNUSED,
4082
				     void *data UNUSED)
4083
{
4084
	struct object_id peeled;
4085
	struct object *object;
4086

4087
	if (!peel_iterated_oid(the_repository, oid, &peeled))
4088
		oid = &peeled;
4089

4090
	object = parse_object_or_die(oid, refname);
4091
	if (object->type == OBJ_COMMIT)
4092
		object->flags |= NEEDS_BITMAP;
4093

4094
	return 0;
4095
}
4096

4097
static void mark_bitmap_preferred_tips(void)
4098
{
4099
	struct string_list_item *item;
4100
	const struct string_list *preferred_tips;
4101

4102
	preferred_tips = bitmap_preferred_tips(the_repository);
4103
	if (!preferred_tips)
4104
		return;
4105

4106
	for_each_string_list_item(item, preferred_tips) {
4107
		refs_for_each_ref_in(get_main_ref_store(the_repository),
4108
				     item->string, mark_bitmap_preferred_tip,
4109
				     NULL);
4110
	}
4111
}
4112

4113
static void get_object_list(struct rev_info *revs, int ac, const char **av)
4114
{
4115
	struct setup_revision_opt s_r_opt = {
4116
		.allow_exclude_promisor_objects = 1,
4117
	};
4118
	char line[1000];
4119
	int flags = 0;
4120
	int save_warning;
4121

4122
	save_commit_buffer = 0;
4123
	setup_revisions(ac, av, revs, &s_r_opt);
4124

4125
	/* make sure shallows are read */
4126
	is_repository_shallow(the_repository);
4127

4128
	save_warning = warn_on_object_refname_ambiguity;
4129
	warn_on_object_refname_ambiguity = 0;
4130

4131
	while (fgets(line, sizeof(line), stdin) != NULL) {
4132
		int len = strlen(line);
4133
		if (len && line[len - 1] == '\n')
4134
			line[--len] = 0;
4135
		if (!len)
4136
			break;
4137
		if (*line == '-') {
4138
			if (!strcmp(line, "--not")) {
4139
				flags ^= UNINTERESTING;
4140
				write_bitmap_index = 0;
4141
				continue;
4142
			}
4143
			if (starts_with(line, "--shallow ")) {
4144
				struct object_id oid;
4145
				if (get_oid_hex(line + 10, &oid))
4146
					die("not an object name '%s'", line + 10);
4147
				register_shallow(the_repository, &oid);
4148
				use_bitmap_index = 0;
4149
				continue;
4150
			}
4151
			die(_("not a rev '%s'"), line);
4152
		}
4153
		if (handle_revision_arg(line, revs, flags, REVARG_CANNOT_BE_FILENAME))
4154
			die(_("bad revision '%s'"), line);
4155
	}
4156

4157
	warn_on_object_refname_ambiguity = save_warning;
4158

4159
	if (use_bitmap_index && !get_object_list_from_bitmap(revs))
4160
		return;
4161

4162
	if (use_delta_islands)
4163
		load_delta_islands(the_repository, progress);
4164

4165
	if (write_bitmap_index)
4166
		mark_bitmap_preferred_tips();
4167

4168
	if (prepare_revision_walk(revs))
4169
		die(_("revision walk setup failed"));
4170
	mark_edges_uninteresting(revs, show_edge, sparse);
4171

4172
	if (!fn_show_object)
4173
		fn_show_object = show_object;
4174
	traverse_commit_list(revs,
4175
			     show_commit, fn_show_object,
4176
			     NULL);
4177

4178
	if (unpack_unreachable_expiration) {
4179
		revs->ignore_missing_links = 1;
4180
		if (add_unseen_recent_objects_to_traversal(revs,
4181
				unpack_unreachable_expiration, NULL, 0))
4182
			die(_("unable to add recent objects"));
4183
		if (prepare_revision_walk(revs))
4184
			die(_("revision walk setup failed"));
4185
		traverse_commit_list(revs, record_recent_commit,
4186
				     record_recent_object, NULL);
4187
	}
4188

4189
	if (keep_unreachable)
4190
		add_objects_in_unpacked_packs();
4191
	if (pack_loose_unreachable)
4192
		add_unreachable_loose_objects();
4193
	if (unpack_unreachable)
4194
		loosen_unused_packed_objects();
4195

4196
	oid_array_clear(&recent_objects);
4197
}
4198

4199
static void add_extra_kept_packs(const struct string_list *names)
4200
{
4201
	struct packed_git *p;
4202

4203
	if (!names->nr)
4204
		return;
4205

4206
	for (p = get_all_packs(the_repository); p; p = p->next) {
4207
		const char *name = basename(p->pack_name);
4208
		int i;
4209

4210
		if (!p->pack_local)
4211
			continue;
4212

4213
		for (i = 0; i < names->nr; i++)
4214
			if (!fspathcmp(name, names->items[i].string))
4215
				break;
4216

4217
		if (i < names->nr) {
4218
			p->pack_keep_in_core = 1;
4219
			ignore_packed_keep_in_core = 1;
4220
			continue;
4221
		}
4222
	}
4223
}
4224

4225
static int option_parse_quiet(const struct option *opt, const char *arg,
4226
			      int unset)
4227
{
4228
	int *val = opt->value;
4229

4230
	BUG_ON_OPT_ARG(arg);
4231

4232
	if (!unset)
4233
		*val = 0;
4234
	else if (!*val)
4235
		*val = 1;
4236
	return 0;
4237
}
4238

4239
static int option_parse_index_version(const struct option *opt,
4240
				      const char *arg, int unset)
4241
{
4242
	struct pack_idx_option *popts = opt->value;
4243
	char *c;
4244
	const char *val = arg;
4245

4246
	BUG_ON_OPT_NEG(unset);
4247

4248
	popts->version = strtoul(val, &c, 10);
4249
	if (popts->version > 2)
4250
		die(_("unsupported index version %s"), val);
4251
	if (*c == ',' && c[1])
4252
		popts->off32_limit = strtoul(c+1, &c, 0);
4253
	if (*c || popts->off32_limit & 0x80000000)
4254
		die(_("bad index version '%s'"), val);
4255
	return 0;
4256
}
4257

4258
static int option_parse_unpack_unreachable(const struct option *opt UNUSED,
4259
					   const char *arg, int unset)
4260
{
4261
	if (unset) {
4262
		unpack_unreachable = 0;
4263
		unpack_unreachable_expiration = 0;
4264
	}
4265
	else {
4266
		unpack_unreachable = 1;
4267
		if (arg)
4268
			unpack_unreachable_expiration = approxidate(arg);
4269
	}
4270
	return 0;
4271
}
4272

4273
static int option_parse_cruft_expiration(const struct option *opt UNUSED,
4274
					 const char *arg, int unset)
4275
{
4276
	if (unset) {
4277
		cruft = 0;
4278
		cruft_expiration = 0;
4279
	} else {
4280
		cruft = 1;
4281
		if (arg)
4282
			cruft_expiration = approxidate(arg);
4283
	}
4284
	return 0;
4285
}
4286

4287
int cmd_pack_objects(int argc, const char **argv, const char *prefix)
4288
{
4289
	int use_internal_rev_list = 0;
4290
	int shallow = 0;
4291
	int all_progress_implied = 0;
4292
	struct strvec rp = STRVEC_INIT;
4293
	int rev_list_unpacked = 0, rev_list_all = 0, rev_list_reflog = 0;
4294
	int rev_list_index = 0;
4295
	int stdin_packs = 0;
4296
	struct string_list keep_pack_list = STRING_LIST_INIT_NODUP;
4297
	struct list_objects_filter_options filter_options =
4298
		LIST_OBJECTS_FILTER_INIT;
4299

4300
	struct option pack_objects_options[] = {
4301
		OPT_CALLBACK_F('q', "quiet", &progress, NULL,
4302
			       N_("do not show progress meter"),
4303
			       PARSE_OPT_NOARG, option_parse_quiet),
4304
		OPT_SET_INT(0, "progress", &progress,
4305
			    N_("show progress meter"), 1),
4306
		OPT_SET_INT(0, "all-progress", &progress,
4307
			    N_("show progress meter during object writing phase"), 2),
4308
		OPT_BOOL(0, "all-progress-implied",
4309
			 &all_progress_implied,
4310
			 N_("similar to --all-progress when progress meter is shown")),
4311
		OPT_CALLBACK_F(0, "index-version", &pack_idx_opts, N_("<version>[,<offset>]"),
4312
		  N_("write the pack index file in the specified idx format version"),
4313
		  PARSE_OPT_NONEG, option_parse_index_version),
4314
		OPT_MAGNITUDE(0, "max-pack-size", &pack_size_limit,
4315
			      N_("maximum size of each output pack file")),
4316
		OPT_BOOL(0, "local", &local,
4317
			 N_("ignore borrowed objects from alternate object store")),
4318
		OPT_BOOL(0, "incremental", &incremental,
4319
			 N_("ignore packed objects")),
4320
		OPT_INTEGER(0, "window", &window,
4321
			    N_("limit pack window by objects")),
4322
		OPT_MAGNITUDE(0, "window-memory", &window_memory_limit,
4323
			      N_("limit pack window by memory in addition to object limit")),
4324
		OPT_INTEGER(0, "depth", &depth,
4325
			    N_("maximum length of delta chain allowed in the resulting pack")),
4326
		OPT_BOOL(0, "reuse-delta", &reuse_delta,
4327
			 N_("reuse existing deltas")),
4328
		OPT_BOOL(0, "reuse-object", &reuse_object,
4329
			 N_("reuse existing objects")),
4330
		OPT_BOOL(0, "delta-base-offset", &allow_ofs_delta,
4331
			 N_("use OFS_DELTA objects")),
4332
		OPT_INTEGER(0, "threads", &delta_search_threads,
4333
			    N_("use threads when searching for best delta matches")),
4334
		OPT_BOOL(0, "non-empty", &non_empty,
4335
			 N_("do not create an empty pack output")),
4336
		OPT_BOOL(0, "revs", &use_internal_rev_list,
4337
			 N_("read revision arguments from standard input")),
4338
		OPT_SET_INT_F(0, "unpacked", &rev_list_unpacked,
4339
			      N_("limit the objects to those that are not yet packed"),
4340
			      1, PARSE_OPT_NONEG),
4341
		OPT_SET_INT_F(0, "all", &rev_list_all,
4342
			      N_("include objects reachable from any reference"),
4343
			      1, PARSE_OPT_NONEG),
4344
		OPT_SET_INT_F(0, "reflog", &rev_list_reflog,
4345
			      N_("include objects referred by reflog entries"),
4346
			      1, PARSE_OPT_NONEG),
4347
		OPT_SET_INT_F(0, "indexed-objects", &rev_list_index,
4348
			      N_("include objects referred to by the index"),
4349
			      1, PARSE_OPT_NONEG),
4350
		OPT_BOOL(0, "stdin-packs", &stdin_packs,
4351
			 N_("read packs from stdin")),
4352
		OPT_BOOL(0, "stdout", &pack_to_stdout,
4353
			 N_("output pack to stdout")),
4354
		OPT_BOOL(0, "include-tag", &include_tag,
4355
			 N_("include tag objects that refer to objects to be packed")),
4356
		OPT_BOOL(0, "keep-unreachable", &keep_unreachable,
4357
			 N_("keep unreachable objects")),
4358
		OPT_BOOL(0, "pack-loose-unreachable", &pack_loose_unreachable,
4359
			 N_("pack loose unreachable objects")),
4360
		OPT_CALLBACK_F(0, "unpack-unreachable", NULL, N_("time"),
4361
		  N_("unpack unreachable objects newer than <time>"),
4362
		  PARSE_OPT_OPTARG, option_parse_unpack_unreachable),
4363
		OPT_BOOL(0, "cruft", &cruft, N_("create a cruft pack")),
4364
		OPT_CALLBACK_F(0, "cruft-expiration", NULL, N_("time"),
4365
		  N_("expire cruft objects older than <time>"),
4366
		  PARSE_OPT_OPTARG, option_parse_cruft_expiration),
4367
		OPT_BOOL(0, "sparse", &sparse,
4368
			 N_("use the sparse reachability algorithm")),
4369
		OPT_BOOL(0, "thin", &thin,
4370
			 N_("create thin packs")),
4371
		OPT_BOOL(0, "shallow", &shallow,
4372
			 N_("create packs suitable for shallow fetches")),
4373
		OPT_BOOL(0, "honor-pack-keep", &ignore_packed_keep_on_disk,
4374
			 N_("ignore packs that have companion .keep file")),
4375
		OPT_STRING_LIST(0, "keep-pack", &keep_pack_list, N_("name"),
4376
				N_("ignore this pack")),
4377
		OPT_INTEGER(0, "compression", &pack_compression_level,
4378
			    N_("pack compression level")),
4379
		OPT_BOOL(0, "keep-true-parents", &grafts_keep_true_parents,
4380
			 N_("do not hide commits by grafts")),
4381
		OPT_BOOL(0, "use-bitmap-index", &use_bitmap_index,
4382
			 N_("use a bitmap index if available to speed up counting objects")),
4383
		OPT_SET_INT(0, "write-bitmap-index", &write_bitmap_index,
4384
			    N_("write a bitmap index together with the pack index"),
4385
			    WRITE_BITMAP_TRUE),
4386
		OPT_SET_INT_F(0, "write-bitmap-index-quiet",
4387
			      &write_bitmap_index,
4388
			      N_("write a bitmap index if possible"),
4389
			      WRITE_BITMAP_QUIET, PARSE_OPT_HIDDEN),
4390
		OPT_PARSE_LIST_OBJECTS_FILTER(&filter_options),
4391
		OPT_CALLBACK_F(0, "missing", NULL, N_("action"),
4392
		  N_("handling for missing objects"), PARSE_OPT_NONEG,
4393
		  option_parse_missing_action),
4394
		OPT_BOOL(0, "exclude-promisor-objects", &exclude_promisor_objects,
4395
			 N_("do not pack objects in promisor packfiles")),
4396
		OPT_BOOL(0, "delta-islands", &use_delta_islands,
4397
			 N_("respect islands during delta compression")),
4398
		OPT_STRING_LIST(0, "uri-protocol", &uri_protocols,
4399
				N_("protocol"),
4400
				N_("exclude any configured uploadpack.blobpackfileuri with this protocol")),
4401
		OPT_END(),
4402
	};
4403

4404
	if (DFS_NUM_STATES > (1 << OE_DFS_STATE_BITS))
4405
		BUG("too many dfs states, increase OE_DFS_STATE_BITS");
4406

4407
	disable_replace_refs();
4408

4409
	sparse = git_env_bool("GIT_TEST_PACK_SPARSE", -1);
4410
	if (the_repository->gitdir) {
4411
		prepare_repo_settings(the_repository);
4412
		if (sparse < 0)
4413
			sparse = the_repository->settings.pack_use_sparse;
4414
		if (the_repository->settings.pack_use_multi_pack_reuse)
4415
			allow_pack_reuse = MULTI_PACK_REUSE;
4416
	}
4417

4418
	reset_pack_idx_option(&pack_idx_opts);
4419
	pack_idx_opts.flags |= WRITE_REV;
4420
	git_config(git_pack_config, NULL);
4421
	if (git_env_bool(GIT_TEST_NO_WRITE_REV_INDEX, 0))
4422
		pack_idx_opts.flags &= ~WRITE_REV;
4423

4424
	progress = isatty(2);
4425
	argc = parse_options(argc, argv, prefix, pack_objects_options,
4426
			     pack_usage, 0);
4427

4428
	if (argc) {
4429
		base_name = argv[0];
4430
		argc--;
4431
	}
4432
	if (pack_to_stdout != !base_name || argc)
4433
		usage_with_options(pack_usage, pack_objects_options);
4434

4435
	if (depth < 0)
4436
		depth = 0;
4437
	if (depth >= (1 << OE_DEPTH_BITS)) {
4438
		warning(_("delta chain depth %d is too deep, forcing %d"),
4439
			depth, (1 << OE_DEPTH_BITS) - 1);
4440
		depth = (1 << OE_DEPTH_BITS) - 1;
4441
	}
4442
	if (cache_max_small_delta_size >= (1U << OE_Z_DELTA_BITS)) {
4443
		warning(_("pack.deltaCacheLimit is too high, forcing %d"),
4444
			(1U << OE_Z_DELTA_BITS) - 1);
4445
		cache_max_small_delta_size = (1U << OE_Z_DELTA_BITS) - 1;
4446
	}
4447
	if (window < 0)
4448
		window = 0;
4449

4450
	strvec_push(&rp, "pack-objects");
4451
	if (thin) {
4452
		use_internal_rev_list = 1;
4453
		strvec_push(&rp, shallow
4454
				? "--objects-edge-aggressive"
4455
				: "--objects-edge");
4456
	} else
4457
		strvec_push(&rp, "--objects");
4458

4459
	if (rev_list_all) {
4460
		use_internal_rev_list = 1;
4461
		strvec_push(&rp, "--all");
4462
	}
4463
	if (rev_list_reflog) {
4464
		use_internal_rev_list = 1;
4465
		strvec_push(&rp, "--reflog");
4466
	}
4467
	if (rev_list_index) {
4468
		use_internal_rev_list = 1;
4469
		strvec_push(&rp, "--indexed-objects");
4470
	}
4471
	if (rev_list_unpacked && !stdin_packs) {
4472
		use_internal_rev_list = 1;
4473
		strvec_push(&rp, "--unpacked");
4474
	}
4475

4476
	if (exclude_promisor_objects) {
4477
		use_internal_rev_list = 1;
4478
		fetch_if_missing = 0;
4479
		strvec_push(&rp, "--exclude-promisor-objects");
4480
	}
4481
	if (unpack_unreachable || keep_unreachable || pack_loose_unreachable)
4482
		use_internal_rev_list = 1;
4483

4484
	if (!reuse_object)
4485
		reuse_delta = 0;
4486
	if (pack_compression_level == -1)
4487
		pack_compression_level = Z_DEFAULT_COMPRESSION;
4488
	else if (pack_compression_level < 0 || pack_compression_level > Z_BEST_COMPRESSION)
4489
		die(_("bad pack compression level %d"), pack_compression_level);
4490

4491
	if (!delta_search_threads)	/* --threads=0 means autodetect */
4492
		delta_search_threads = online_cpus();
4493

4494
	if (!HAVE_THREADS && delta_search_threads != 1)
4495
		warning(_("no threads support, ignoring --threads"));
4496
	if (!pack_to_stdout && !pack_size_limit)
4497
		pack_size_limit = pack_size_limit_cfg;
4498
	if (pack_to_stdout && pack_size_limit)
4499
		die(_("--max-pack-size cannot be used to build a pack for transfer"));
4500
	if (pack_size_limit && pack_size_limit < 1024*1024) {
4501
		warning(_("minimum pack size limit is 1 MiB"));
4502
		pack_size_limit = 1024*1024;
4503
	}
4504

4505
	if (!pack_to_stdout && thin)
4506
		die(_("--thin cannot be used to build an indexable pack"));
4507

4508
	if (keep_unreachable && unpack_unreachable)
4509
		die(_("options '%s' and '%s' cannot be used together"), "--keep-unreachable", "--unpack-unreachable");
4510
	if (!rev_list_all || !rev_list_reflog || !rev_list_index)
4511
		unpack_unreachable_expiration = 0;
4512

4513
	if (stdin_packs && filter_options.choice)
4514
		die(_("cannot use --filter with --stdin-packs"));
4515

4516
	if (stdin_packs && use_internal_rev_list)
4517
		die(_("cannot use internal rev list with --stdin-packs"));
4518

4519
	if (cruft) {
4520
		if (use_internal_rev_list)
4521
			die(_("cannot use internal rev list with --cruft"));
4522
		if (stdin_packs)
4523
			die(_("cannot use --stdin-packs with --cruft"));
4524
	}
4525

4526
	/*
4527
	 * "soft" reasons not to use bitmaps - for on-disk repack by default we want
4528
	 *
4529
	 * - to produce good pack (with bitmap index not-yet-packed objects are
4530
	 *   packed in suboptimal order).
4531
	 *
4532
	 * - to use more robust pack-generation codepath (avoiding possible
4533
	 *   bugs in bitmap code and possible bitmap index corruption).
4534
	 */
4535
	if (!pack_to_stdout)
4536
		use_bitmap_index_default = 0;
4537

4538
	if (use_bitmap_index < 0)
4539
		use_bitmap_index = use_bitmap_index_default;
4540

4541
	/* "hard" reasons not to use bitmaps; these just won't work at all */
4542
	if (!use_internal_rev_list || (!pack_to_stdout && write_bitmap_index) || is_repository_shallow(the_repository))
4543
		use_bitmap_index = 0;
4544

4545
	if (pack_to_stdout || !rev_list_all)
4546
		write_bitmap_index = 0;
4547

4548
	if (use_delta_islands)
4549
		strvec_push(&rp, "--topo-order");
4550

4551
	if (progress && all_progress_implied)
4552
		progress = 2;
4553

4554
	add_extra_kept_packs(&keep_pack_list);
4555
	if (ignore_packed_keep_on_disk) {
4556
		struct packed_git *p;
4557
		for (p = get_all_packs(the_repository); p; p = p->next)
4558
			if (p->pack_local && p->pack_keep)
4559
				break;
4560
		if (!p) /* no keep-able packs found */
4561
			ignore_packed_keep_on_disk = 0;
4562
	}
4563
	if (local) {
4564
		/*
4565
		 * unlike ignore_packed_keep_on_disk above, we do not
4566
		 * want to unset "local" based on looking at packs, as
4567
		 * it also covers non-local objects
4568
		 */
4569
		struct packed_git *p;
4570
		for (p = get_all_packs(the_repository); p; p = p->next) {
4571
			if (!p->pack_local) {
4572
				have_non_local_packs = 1;
4573
				break;
4574
			}
4575
		}
4576
	}
4577

4578
	trace2_region_enter("pack-objects", "enumerate-objects",
4579
			    the_repository);
4580
	prepare_packing_data(the_repository, &to_pack);
4581

4582
	if (progress && !cruft)
4583
		progress_state = start_progress(_("Enumerating objects"), 0);
4584
	if (stdin_packs) {
4585
		/* avoids adding objects in excluded packs */
4586
		ignore_packed_keep_in_core = 1;
4587
		read_packs_list_from_stdin();
4588
		if (rev_list_unpacked)
4589
			add_unreachable_loose_objects();
4590
	} else if (cruft) {
4591
		read_cruft_objects();
4592
	} else if (!use_internal_rev_list) {
4593
		read_object_list_from_stdin();
4594
	} else {
4595
		struct rev_info revs;
4596

4597
		repo_init_revisions(the_repository, &revs, NULL);
4598
		list_objects_filter_copy(&revs.filter, &filter_options);
4599
		get_object_list(&revs, rp.nr, rp.v);
4600
		release_revisions(&revs);
4601
	}
4602
	cleanup_preferred_base();
4603
	if (include_tag && nr_result)
4604
		refs_for_each_tag_ref(get_main_ref_store(the_repository),
4605
				      add_ref_tag, NULL);
4606
	stop_progress(&progress_state);
4607
	trace2_region_leave("pack-objects", "enumerate-objects",
4608
			    the_repository);
4609

4610
	if (non_empty && !nr_result)
4611
		goto cleanup;
4612
	if (nr_result) {
4613
		trace2_region_enter("pack-objects", "prepare-pack",
4614
				    the_repository);
4615
		prepare_pack(window, depth);
4616
		trace2_region_leave("pack-objects", "prepare-pack",
4617
				    the_repository);
4618
	}
4619

4620
	trace2_region_enter("pack-objects", "write-pack-file", the_repository);
4621
	write_excluded_by_configs();
4622
	write_pack_file();
4623
	trace2_region_leave("pack-objects", "write-pack-file", the_repository);
4624

4625
	if (progress)
4626
		fprintf_ln(stderr,
4627
			   _("Total %"PRIu32" (delta %"PRIu32"),"
4628
			     " reused %"PRIu32" (delta %"PRIu32"),"
4629
			     " pack-reused %"PRIu32" (from %"PRIuMAX")"),
4630
			   written, written_delta, reused, reused_delta,
4631
			   reuse_packfile_objects,
4632
			   (uintmax_t)reuse_packfiles_used_nr);
4633

4634
	trace2_data_intmax("pack-objects", the_repository, "written", written);
4635
	trace2_data_intmax("pack-objects", the_repository, "written/delta", written_delta);
4636
	trace2_data_intmax("pack-objects", the_repository, "reused", reused);
4637
	trace2_data_intmax("pack-objects", the_repository, "reused/delta", reused_delta);
4638
	trace2_data_intmax("pack-objects", the_repository, "pack-reused", reuse_packfile_objects);
4639
	trace2_data_intmax("pack-objects", the_repository, "packs-reused", reuse_packfiles_used_nr);
4640

4641
cleanup:
4642
	clear_packing_data(&to_pack);
4643
	list_objects_filter_release(&filter_options);
4644
	strvec_clear(&rp);
4645

4646
	return 0;
4647
}
4648