pack-objects.c · matheusbsbs/matheus-bagliano

jch

bisect jch maint master next seen test todo

c 5,537 lines 150 KB

Raw

1	#define USE_THE_REPOSITORY_VARIABLE
2	#define DISABLE_SIGN_COMPARE_WARNINGS
3
4	#include "builtin.h"
5	#include "environment.h"
6	#include "gettext.h"
7	#include "hex.h"
8	#include "config.h"
9	#include "attr.h"
10	#include "object.h"
11	#include "commit.h"
12	#include "tag.h"
13	#include "delta.h"
14	#include "pack.h"
15	#include "pack-revindex.h"
16	#include "csum-file.h"
17	#include "tree-walk.h"
18	#include "diff.h"
19	#include "revision.h"
20	#include "list-objects.h"
21	#include "list-objects-filter-options.h"
22	#include "pack-objects.h"
23	#include "progress.h"
24	#include "refs.h"
25	#include "thread-utils.h"
26	#include "pack-bitmap.h"
27	#include "delta-islands.h"
28	#include "reachable.h"
29	#include "oid-array.h"
30	#include "strvec.h"
31	#include "strmap.h"
32	#include "list.h"
33	#include "packfile.h"
34	#include "object-file.h"
35	#include "object-file-convert.h"
36	#include "odb.h"
37	#include "odb/streaming.h"
38	#include "replace-object.h"
39	#include "dir.h"
40	#include "midx.h"
41	#include "trace2.h"
42	#include "shallow.h"
43	#include "promisor-remote.h"
44	#include "pack-mtimes.h"
45	#include "parse-options.h"
46	#include "pkt-line.h"
47	#include "blob.h"
48	#include "tree.h"
49	#include "path-walk.h"
50
51	/*
52	* Objects we are going to pack are collected in the `to_pack` structure.
53	* It contains an array (dynamically expanded) of the object data, and a map
54	* that can resolve SHA1s to their position in the array.
55	*/
56	static struct packing_data to_pack;
57
58	static inline struct object_entry *oe_delta(
59	const struct packing_data *pack,
60	const struct object_entry *e)
61	{
62	if (!e->delta_idx)
63	return NULL;
64	if (e->ext_base)
65	return &pack->ext_bases[e->delta_idx - 1];
66	else
67	return &pack->objects[e->delta_idx - 1];
68	}
69
70	static inline size_t oe_delta_size(struct packing_data *pack,
71	const struct object_entry *e)
72	{
73	if (e->delta_size_valid)
74	return e->delta_size_;
75
76	/*
77	* pack->delta_size[] can't be NULL because oe_set_delta_size()
78	* must have been called when a new delta is saved with
79	* oe_set_delta().
80	* If oe_delta() returns NULL (i.e. default state, which means
81	* delta_size_valid is also false), then the caller must never
82	* call oe_delta_size().
83	*/
84	return pack->delta_size[e - pack->objects];
85	}
86
87	size_t oe_get_size_slow(struct packing_data *pack,
88	const struct object_entry *e);
89
90	static inline size_t oe_size(struct packing_data *pack,
91	const struct object_entry *e)
92	{
93	if (e->size_valid)
94	return e->size_;
95
96	return oe_get_size_slow(pack, e);
97	}
98
99	static inline void oe_set_delta(struct packing_data *pack,
100	struct object_entry *e,
101	struct object_entry *delta)
102	{
103	if (delta)
104	e->delta_idx = (delta - pack->objects) + 1;
105	else
106	e->delta_idx = 0;
107	}
108
109	static inline struct object_entry *oe_delta_sibling(
110	const struct packing_data *pack,
111	const struct object_entry *e)
112	{
113	if (e->delta_sibling_idx)
114	return &pack->objects[e->delta_sibling_idx - 1];
115	return NULL;
116	}
117
118	static inline struct object_entry *oe_delta_child(
119	const struct packing_data *pack,
120	const struct object_entry *e)
121	{
122	if (e->delta_child_idx)
123	return &pack->objects[e->delta_child_idx - 1];
124	return NULL;
125	}
126
127	static inline void oe_set_delta_child(struct packing_data *pack,
128	struct object_entry *e,
129	struct object_entry *delta)
130	{
131	if (delta)
132	e->delta_child_idx = (delta - pack->objects) + 1;
133	else
134	e->delta_child_idx = 0;
135	}
136
137	static inline void oe_set_delta_sibling(struct packing_data *pack,
138	struct object_entry *e,
139	struct object_entry *delta)
140	{
141	if (delta)
142	e->delta_sibling_idx = (delta - pack->objects) + 1;
143	else
144	e->delta_sibling_idx = 0;
145	}
146
147	static inline void oe_set_size(struct packing_data *pack,
148	struct object_entry *e,
149	size_t size)
150	{
151	if (size < pack->oe_size_limit) {
152	e->size_ = size;
153	e->size_valid = 1;
154	} else {
155	e->size_valid = 0;
156	if (oe_get_size_slow(pack, e) != size)
157	BUG("'size' is supposed to be the object size!");
158	}
159	}
160
161	static inline void oe_set_delta_size(struct packing_data *pack,
162	struct object_entry *e,
163	size_t size)
164	{
165	if (size < pack->oe_delta_size_limit) {
166	e->delta_size_ = size;
167	e->delta_size_valid = 1;
168	} else {
169	packing_data_lock(pack);
170	if (!pack->delta_size)
171	ALLOC_ARRAY(pack->delta_size, pack->nr_alloc);
172	packing_data_unlock(pack);
173
174	pack->delta_size[e - pack->objects] = size;
175	e->delta_size_valid = 0;
176	}
177	}
178
179	#define IN_PACK(obj) oe_in_pack(&to_pack, obj)
180	#define SIZE(obj) oe_size(&to_pack, obj)
181	#define SET_SIZE(obj,size) oe_set_size(&to_pack, obj, size)
182	#define DELTA_SIZE(obj) oe_delta_size(&to_pack, obj)
183	#define DELTA(obj) oe_delta(&to_pack, obj)
184	#define DELTA_CHILD(obj) oe_delta_child(&to_pack, obj)
185	#define DELTA_SIBLING(obj) oe_delta_sibling(&to_pack, obj)
186	#define SET_DELTA(obj, val) oe_set_delta(&to_pack, obj, val)
187	#define SET_DELTA_EXT(obj, oid) oe_set_delta_ext(&to_pack, obj, oid)
188	#define SET_DELTA_SIZE(obj, val) oe_set_delta_size(&to_pack, obj, val)
189	#define SET_DELTA_CHILD(obj, val) oe_set_delta_child(&to_pack, obj, val)
190	#define SET_DELTA_SIBLING(obj, val) oe_set_delta_sibling(&to_pack, obj, val)
191
192	static const char *const pack_usage[] = {
193	N_("git pack-objects [-q \| --progress \| --all-progress] [--all-progress-implied]\n"
194	" [--no-reuse-delta] [--delta-base-offset] [--non-empty]\n"
195	" [--local] [--incremental] [--window=<n>] [--depth=<n>]\n"
196	" [--revs [--unpacked \| --all]] [--keep-pack=<pack-name>]\n"
197	" [--cruft] [--cruft-expiration=<time>]\n"
198	" [--stdout [--filter=<filter-spec>] \| <base-name>]\n"
199	" [--shallow] [--keep-true-parents] [--[no-]sparse]\n"
200	" [--name-hash-version=<n>] [--path-walk] < <object-list>"),
201	NULL
202	};
203
204	static struct pack_idx_entry **written_list;
205	static uint32_t nr_result, nr_written, nr_seen;
206	static struct bitmap_index *bitmap_git;
207	static uint32_t write_layer;
208
209	static int non_empty;
210	static int reuse_delta = 1, reuse_object = 1;
211	static int keep_unreachable, unpack_unreachable, include_tag;
212	static timestamp_t unpack_unreachable_expiration;
213	static int pack_loose_unreachable;
214	static int cruft;
215	static int shallow = 0;
216	static timestamp_t cruft_expiration;
217	static int local;
218	static int have_non_local_packs;
219	static int incremental;
220	static int ignore_packed_keep_on_disk;
221	static int ignore_packed_keep_in_core;
222	static int ignore_packed_keep_in_core_open;
223	static int ignore_packed_keep_in_core_has_cruft;
224	static int allow_ofs_delta;
225	static struct pack_idx_option pack_idx_opts;
226	static const char *base_name;
227	static int progress = 1;
228	static int window = 10;
229	static unsigned long pack_size_limit;
230	static int depth = 50;
231	static int delta_search_threads;
232	static int pack_to_stdout;
233	static int sparse;
234	static int thin;
235	static int path_walk = -1;
236	static int num_preferred_base;
237	static struct progress *progress_state;
238
239	static struct bitmapped_pack *reuse_packfiles;
240	static size_t reuse_packfiles_nr;
241	static size_t reuse_packfiles_used_nr;
242	static uint32_t reuse_packfile_objects;
243	static struct bitmap *reuse_packfile_bitmap;
244
245	static int use_bitmap_index_default = 1;
246	static int use_bitmap_index = -1;
247	static enum {
248	NO_PACK_REUSE = 0,
249	SINGLE_PACK_REUSE,
250	MULTI_PACK_REUSE,
251	} allow_pack_reuse = SINGLE_PACK_REUSE;
252	static enum {
253	WRITE_BITMAP_FALSE = 0,
254	WRITE_BITMAP_QUIET,
255	WRITE_BITMAP_TRUE,
256	} write_bitmap_index;
257	static uint16_t write_bitmap_options = BITMAP_OPT_HASH_CACHE;
258
259	static int exclude_promisor_objects;
260	static int exclude_promisor_objects_best_effort;
261
262	static int use_delta_islands;
263
264	static unsigned long delta_cache_size = 0;
265	static unsigned long max_delta_cache_size = DEFAULT_DELTA_CACHE_SIZE;
266	static unsigned long cache_max_small_delta_size = 1000;
267
268	static unsigned long window_memory_limit = 0;
269
270	static struct string_list uri_protocols = STRING_LIST_INIT_NODUP;
271
272	enum missing_action {
273	MA_ERROR = 0, /* fail if any missing objects are encountered */
274	MA_ALLOW_ANY, /* silently allow ALL missing objects */
275	MA_ALLOW_PROMISOR, /* silently allow all missing PROMISOR objects */
276	};
277	static enum missing_action arg_missing_action;
278	static show_object_fn fn_show_object;
279
280	struct configured_exclusion {
281	struct oidmap_entry e;
282	char *pack_hash_hex;
283	char *uri;
284	};
285	static struct oidmap configured_exclusions;
286
287	static struct oidset excluded_by_config;
288	static int name_hash_version = -1;
289
290	enum stdin_packs_mode {
291	STDIN_PACKS_MODE_NONE,
292	STDIN_PACKS_MODE_STANDARD,
293	STDIN_PACKS_MODE_FOLLOW,
294	};
295
296	/**
297	* Check whether the name_hash_version chosen by user input is appropriate,
298	* and also validate whether it is compatible with other features.
299	*/
300	static void validate_name_hash_version(void)
301	{
302	if (name_hash_version < 1 \|\| name_hash_version > 2)
303	die(_("invalid --name-hash-version option: %d"), name_hash_version);
304	if (write_bitmap_index && name_hash_version != 1) {
305	warning(_("currently, --write-bitmap-index requires --name-hash-version=1"));
306	name_hash_version = 1;
307	}
308	}
309
310	static inline uint32_t pack_name_hash_fn(const char *name)
311	{
312	static int seen_version = -1;
313
314	if (seen_version < 0)
315	seen_version = name_hash_version;
316	else if (seen_version != name_hash_version)
317	BUG("name hash version changed from %d to %d mid-process",
318	seen_version, name_hash_version);
319
320	switch (name_hash_version) {
321	case 1:
322	return pack_name_hash(name);
323
324	case 2:
325	return pack_name_hash_v2((const unsigned char *)name);
326
327	default:
328	BUG("invalid name-hash version: %d", name_hash_version);
329	}
330	}
331
332	/*
333	* stats
334	*/
335	static uint32_t written, written_delta;
336	static uint32_t reused, reused_delta;
337
338	/*
339	* Indexed commits
340	*/
341	static struct commit **indexed_commits;
342	static unsigned int indexed_commits_nr;
343	static unsigned int indexed_commits_alloc;
344
345	static void index_commit_for_bitmap(struct commit *commit)
346	{
347	if (indexed_commits_nr >= indexed_commits_alloc) {
348	indexed_commits_alloc = (indexed_commits_alloc + 32) * 2;
349	REALLOC_ARRAY(indexed_commits, indexed_commits_alloc);
350	}
351
352	indexed_commits[indexed_commits_nr++] = commit;
353	}
354
355	static void get_delta(struct object_entry entry)
356	{
357	unsigned long size, base_size, delta_size;
358	void buf, base_buf, *delta_buf;
359	enum object_type type;
360	size_t size_st = 0, base_size_st = 0;
361
362	buf = odb_read_object(the_repository->objects, &entry->idx.oid,
363	&type, &size_st);
364	size = cast_size_t_to_ulong(size_st);
365	if (!buf)
366	die(_("unable to read %s"), oid_to_hex(&entry->idx.oid));
367	base_buf = odb_read_object(the_repository->objects,
368	&DELTA(entry)->idx.oid, &type,
369	&base_size_st);
370	base_size = cast_size_t_to_ulong(base_size_st);
371	if (!base_buf)
372	die("unable to read %s",
373	oid_to_hex(&DELTA(entry)->idx.oid));
374	delta_buf = diff_delta(base_buf, base_size,
375	buf, size, &delta_size, 0);
376	/*
377	* We successfully computed this delta once but dropped it for
378	* memory reasons. Something is very wrong if this time we
379	* recompute and create a different delta.
380	*/
381	if (!delta_buf \|\| delta_size != DELTA_SIZE(entry))
382	BUG("delta size changed");
383	free(buf);
384	free(base_buf);
385	return delta_buf;
386	}
387
388	static unsigned long do_compress(void **pptr, unsigned long size)
389	{
390	git_zstream stream;
391	void in, out;
392	unsigned long maxsize;
393	struct repo_config_values *cfg = repo_config_values(the_repository);
394
395	git_deflate_init(&stream, cfg->pack_compression_level);
396	maxsize = git_deflate_bound(&stream, size);
397
398	in = *pptr;
399	out = xmalloc(maxsize);
400	*pptr = out;
401
402	stream.next_in = in;
403	stream.avail_in = size;
404	stream.next_out = out;
405	stream.avail_out = maxsize;
406	while (git_deflate(&stream, Z_FINISH) == Z_OK)
407	; /* nothing */
408	git_deflate_end(&stream);
409
410	free(in);
411	return stream.total_out;
412	}
413
414	static unsigned long write_large_blob_data(struct odb_read_stream st, struct hashfile f,
415	const struct object_id *oid)
416	{
417	git_zstream stream;
418	unsigned char ibuf[1024 * 16];
419	unsigned char obuf[1024 * 16];
420	unsigned long olen = 0;
421	struct repo_config_values *cfg = repo_config_values(the_repository);
422
423	git_deflate_init(&stream, cfg->pack_compression_level);
424
425	for (;;) {
426	ssize_t readlen;
427	int zret = Z_OK;
428	readlen = odb_read_stream_read(st, ibuf, sizeof(ibuf));
429	if (readlen == -1)
430	die(_("unable to read %s"), oid_to_hex(oid));
431
432	stream.next_in = ibuf;
433	stream.avail_in = readlen;
434	while ((stream.avail_in \|\| readlen == 0) &&
435	(zret == Z_OK \|\| zret == Z_BUF_ERROR)) {
436	stream.next_out = obuf;
437	stream.avail_out = sizeof(obuf);
438	zret = git_deflate(&stream, readlen ? 0 : Z_FINISH);
439	hashwrite(f, obuf, stream.next_out - obuf);
440	olen += stream.next_out - obuf;
441	}
442	if (stream.avail_in)
443	die(_("deflate error (%d)"), zret);
444	if (readlen == 0) {
445	if (zret != Z_STREAM_END)
446	die(_("deflate error (%d)"), zret);
447	break;
448	}
449	}
450	git_deflate_end(&stream);
451	return olen;
452	}
453
454	/*
455	* we are going to reuse the existing object data as is. make
456	* sure it is not corrupt.
457	*/
458	static int check_pack_inflate(struct packed_git *p,
459	struct pack_window **w_curs,
460	off_t offset,
461	off_t len,
462	size_t expect)
463	{
464	git_zstream stream;
465	unsigned char fakebuf[4096], *in;
466	int st;
467
468	memset(&stream, 0, sizeof(stream));
469	git_inflate_init(&stream);
470	do {
471	in = use_pack(p, w_curs, offset, &stream.avail_in);
472	stream.next_in = in;
473	stream.next_out = fakebuf;
474	stream.avail_out = sizeof(fakebuf);
475	st = git_inflate(&stream, Z_FINISH);
476	offset += stream.next_in - in;
477	} while (st == Z_OK \|\| st == Z_BUF_ERROR);
478	git_inflate_end(&stream);
479	return (st == Z_STREAM_END &&
480	stream.total_out == expect &&
481	stream.total_in == len) ? 0 : -1;
482	}
483
484	static void copy_pack_data(struct hashfile *f,
485	struct packed_git *p,
486	struct pack_window **w_curs,
487	off_t offset,
488	off_t len)
489	{
490	unsigned char *in;
491	unsigned long avail;
492
493	while (len) {
494	in = use_pack(p, w_curs, offset, &avail);
495	if (avail > len)
496	avail = (unsigned long)len;
497	hashwrite(f, in, avail);
498	offset += avail;
499	len -= avail;
500	}
501	}
502
503	static inline int oe_size_greater_than(struct packing_data *pack,
504	const struct object_entry *lhs,
505	size_t rhs)
506	{
507	if (lhs->size_valid)
508	return lhs->size_ > rhs;
509	if (rhs < pack->oe_size_limit) /* rhs < 2^x <= lhs ? */
510	return 1;
511	return oe_get_size_slow(pack, lhs) > rhs;
512	}
513
514	/* Return 0 if we will bust the pack-size limit */
515	static unsigned long write_no_reuse_object(struct hashfile f, struct object_entry entry,
516	unsigned long limit, int usable_delta)
517	{
518	unsigned long size, datalen;
519	unsigned char header[MAX_PACK_OBJECT_HEADER],
520	dheader[MAX_PACK_OBJECT_HEADER];
521	unsigned hdrlen;
522	enum object_type type;
523	void *buf;
524	struct odb_read_stream *st = NULL;
525	const unsigned hashsz = the_hash_algo->rawsz;
526
527	if (!usable_delta) {
528	if (oe_type(entry) == OBJ_BLOB &&
529	oe_size_greater_than(&to_pack, entry,
530	repo_settings_get_big_file_threshold(the_repository)) &&
531	(st = odb_read_stream_open(the_repository->objects, &entry->idx.oid,
532	NULL)) != NULL) {
533	buf = NULL;
534	type = st->type;
535	size = st->size;
536	} else {
537	size_t size_st = 0;
538	buf = odb_read_object(the_repository->objects,
539	&entry->idx.oid, &type,
540	&size_st);
541	size = cast_size_t_to_ulong(size_st);
542	if (!buf)
543	die(_("unable to read %s"),
544	oid_to_hex(&entry->idx.oid));
545	}
546	/*
547	* make sure no cached delta data remains from a
548	* previous attempt before a pack split occurred.
549	*/
550	FREE_AND_NULL(entry->delta_data);
551	entry->z_delta_size = 0;
552	} else if (entry->delta_data) {
553	size = DELTA_SIZE(entry);
554	buf = entry->delta_data;
555	entry->delta_data = NULL;
556	type = (allow_ofs_delta && DELTA(entry)->idx.offset) ?
557	OBJ_OFS_DELTA : OBJ_REF_DELTA;
558	} else {
559	buf = get_delta(entry);
560	size = DELTA_SIZE(entry);
561	type = (allow_ofs_delta && DELTA(entry)->idx.offset) ?
562	OBJ_OFS_DELTA : OBJ_REF_DELTA;
563	}
564
565	if (st) /* large blob case, just assume we don't compress well */
566	datalen = size;
567	else if (entry->z_delta_size)
568	datalen = entry->z_delta_size;
569	else
570	datalen = do_compress(&buf, size);
571
572	/*
573	* The object header is a byte of 'type' followed by zero or
574	* more bytes of length.
575	*/
576	hdrlen = encode_in_pack_object_header(header, sizeof(header),
577	type, size);
578
579	if (type == OBJ_OFS_DELTA) {
580	/*
581	* Deltas with relative base contain an additional
582	* encoding of the relative offset for the delta
583	* base from this object's position in the pack.
584	*/
585	off_t ofs = entry->idx.offset - DELTA(entry)->idx.offset;
586	unsigned pos = sizeof(dheader) - 1;
587	dheader[pos] = ofs & 127;
588	while (ofs >>= 7)
589	dheader[--pos] = 128 \| (--ofs & 127);
590	if (limit && hdrlen + sizeof(dheader) - pos + datalen + hashsz >= limit) {
591	if (st)
592	odb_read_stream_close(st);
593	free(buf);
594	return 0;
595	}
596	hashwrite(f, header, hdrlen);
597	hashwrite(f, dheader + pos, sizeof(dheader) - pos);
598	hdrlen += sizeof(dheader) - pos;
599	} else if (type == OBJ_REF_DELTA) {
600	/*
601	* Deltas with a base reference contain
602	* additional bytes for the base object ID.
603	*/
604	if (limit && hdrlen + hashsz + datalen + hashsz >= limit) {
605	if (st)
606	odb_read_stream_close(st);
607	free(buf);
608	return 0;
609	}
610	hashwrite(f, header, hdrlen);
611	hashwrite(f, DELTA(entry)->idx.oid.hash, hashsz);
612	hdrlen += hashsz;
613	} else {
614	if (limit && hdrlen + datalen + hashsz >= limit) {
615	if (st)
616	odb_read_stream_close(st);
617	free(buf);
618	return 0;
619	}
620	hashwrite(f, header, hdrlen);
621	}
622	if (st) {
623	datalen = write_large_blob_data(st, f, &entry->idx.oid);
624	odb_read_stream_close(st);
625	} else {
626	hashwrite(f, buf, datalen);
627	free(buf);
628	}
629
630	return hdrlen + datalen;
631	}
632
633	/* Return 0 if we will bust the pack-size limit */
634	static off_t write_reuse_object(struct hashfile f, struct object_entry entry,
635	unsigned long limit, int usable_delta)
636	{
637	struct packed_git *p = IN_PACK(entry);
638	struct pack_window *w_curs = NULL;
639	uint32_t pos;
640	off_t offset, cur;
641	enum object_type type = oe_type(entry);
642	enum object_type in_pack_type;
643	off_t datalen;
644	unsigned char header[MAX_PACK_OBJECT_HEADER],
645	dheader[MAX_PACK_OBJECT_HEADER];
646	unsigned hdrlen;
647	const unsigned hashsz = the_hash_algo->rawsz;
648	size_t entry_size;
649
650	cur = entry->in_pack_offset;
651	in_pack_type = unpack_object_header(p, &w_curs, &cur, &entry_size);
652	if (in_pack_type < 0)
653	die(_("write_reuse_object: unable to parse object header of %s"),
654	oid_to_hex(&entry->idx.oid));
655
656	if (DELTA(entry))
657	type = (allow_ofs_delta && DELTA(entry)->idx.offset) ?
658	OBJ_OFS_DELTA : OBJ_REF_DELTA;
659	hdrlen = encode_in_pack_object_header(header, sizeof(header),
660	type, entry_size);
661
662	offset = entry->in_pack_offset;
663	if (offset_to_pack_pos(p, offset, &pos) < 0)
664	die(_("write_reuse_object: could not locate %s, expected at "
665	"offset %"PRIuMAX" in pack %s"),
666	oid_to_hex(&entry->idx.oid), (uintmax_t)offset,
667	p->pack_name);
668	datalen = pack_pos_to_offset(p, pos + 1) - offset;
669	if (!pack_to_stdout && p->index_version > 1 &&
670	check_pack_crc(p, &w_curs, offset, datalen,
671	pack_pos_to_index(p, pos))) {
672	error(_("bad packed object CRC for %s"),
673	oid_to_hex(&entry->idx.oid));
674	unuse_pack(&w_curs);
675	return write_no_reuse_object(f, entry, limit, usable_delta);
676	}
677
678	offset += entry->in_pack_header_size;
679	datalen -= entry->in_pack_header_size;
680
681	if (!pack_to_stdout && p->index_version == 1 &&
682	check_pack_inflate(p, &w_curs, offset, datalen, entry_size)) {
683	error(_("corrupt packed object for %s"),
684	oid_to_hex(&entry->idx.oid));
685	unuse_pack(&w_curs);
686	return write_no_reuse_object(f, entry, limit, usable_delta);
687	}
688
689	if (type == OBJ_OFS_DELTA) {
690	off_t ofs = entry->idx.offset - DELTA(entry)->idx.offset;
691	unsigned pos = sizeof(dheader) - 1;
692	dheader[pos] = ofs & 127;
693	while (ofs >>= 7)
694	dheader[--pos] = 128 \| (--ofs & 127);
695	if (limit && hdrlen + sizeof(dheader) - pos + datalen + hashsz >= limit) {
696	unuse_pack(&w_curs);
697	return 0;
698	}
699	hashwrite(f, header, hdrlen);
700	hashwrite(f, dheader + pos, sizeof(dheader) - pos);
701	hdrlen += sizeof(dheader) - pos;
702	reused_delta++;
703	} else if (type == OBJ_REF_DELTA) {
704	if (limit && hdrlen + hashsz + datalen + hashsz >= limit) {
705	unuse_pack(&w_curs);
706	return 0;
707	}
708	hashwrite(f, header, hdrlen);
709	hashwrite(f, DELTA(entry)->idx.oid.hash, hashsz);
710	hdrlen += hashsz;
711	reused_delta++;
712	} else {
713	if (limit && hdrlen + datalen + hashsz >= limit) {
714	unuse_pack(&w_curs);
715	return 0;
716	}
717	hashwrite(f, header, hdrlen);
718	}
719	copy_pack_data(f, p, &w_curs, offset, datalen);
720	unuse_pack(&w_curs);
721	reused++;
722	return hdrlen + datalen;
723	}
724
725	/* Return 0 if we will bust the pack-size limit */
726	static off_t write_object(struct hashfile *f,
727	struct object_entry *entry,
728	off_t write_offset)
729	{
730	unsigned long limit;
731	off_t len;
732	int usable_delta, to_reuse;
733
734	if (!pack_to_stdout)
735	crc32_begin(f);
736
737	/* apply size limit if limited packsize and not first object */
738	if (!pack_size_limit \|\| !nr_written)
739	limit = 0;
740	else if (pack_size_limit <= write_offset)
741	/*
742	* the earlier object did not fit the limit; avoid
743	* mistaking this with unlimited (i.e. limit = 0).
744	*/
745	limit = 1;
746	else
747	limit = pack_size_limit - write_offset;
748
749	if (!DELTA(entry))
750	usable_delta = 0; /* no delta */
751	else if (!pack_size_limit)
752	usable_delta = 1; /* unlimited packfile */
753	else if (DELTA(entry)->idx.offset == (off_t)-1)
754	usable_delta = 0; /* base was written to another pack */
755	else if (DELTA(entry)->idx.offset)
756	usable_delta = 1; /* base already exists in this pack */
757	else
758	usable_delta = 0; /* base could end up in another pack */
759
760	if (!reuse_object)
761	to_reuse = 0; /* explicit */
762	else if (!IN_PACK(entry))
763	to_reuse = 0; /* can't reuse what we don't have */
764	else if (oe_type(entry) == OBJ_REF_DELTA \|\|
765	oe_type(entry) == OBJ_OFS_DELTA)
766	/* check_object() decided it for us ... */
767	to_reuse = usable_delta;
768	/* ... but pack split may override that */
769	else if (oe_type(entry) != entry->in_pack_type)
770	to_reuse = 0; /* pack has delta which is unusable */
771	else if (DELTA(entry))
772	to_reuse = 0; /* we want to pack afresh */
773	else
774	to_reuse = 1; /* we have it in-pack undeltified,
775	* and we do not need to deltify it.
776	*/
777
778	if (!to_reuse)
779	len = write_no_reuse_object(f, entry, limit, usable_delta);
780	else
781	len = write_reuse_object(f, entry, limit, usable_delta);
782	if (!len)
783	return 0;
784
785	if (usable_delta)
786	written_delta++;
787	written++;
788	if (!pack_to_stdout)
789	entry->idx.crc32 = crc32_end(f);
790	return len;
791	}
792
793	enum write_one_status {
794	WRITE_ONE_SKIP = -1, /* already written */
795	WRITE_ONE_BREAK = 0, /* writing this will bust the limit; not written */
796	WRITE_ONE_WRITTEN = 1, /* normal */
797	WRITE_ONE_RECURSIVE = 2 /* already scheduled to be written */
798	};
799
800	static enum write_one_status write_one(struct hashfile *f,
801	struct object_entry *e,
802	off_t *offset)
803	{
804	off_t size;
805	int recursing;
806
807	/*
808	* we set offset to 1 (which is an impossible value) to mark
809	* the fact that this object is involved in "write its base
810	* first before writing a deltified object" recursion.
811	*/
812	recursing = (e->idx.offset == 1);
813	if (recursing) {
814	warning(_("recursive delta detected for object %s"),
815	oid_to_hex(&e->idx.oid));
816	return WRITE_ONE_RECURSIVE;
817	} else if (e->idx.offset \|\| e->preferred_base) {
818	/* offset is non zero if object is written already. */
819	return WRITE_ONE_SKIP;
820	}
821
822	/* if we are deltified, write out base object first. */
823	if (DELTA(e)) {
824	e->idx.offset = 1; /* now recurse */
825	switch (write_one(f, DELTA(e), offset)) {
826	case WRITE_ONE_RECURSIVE:
827	/* we cannot depend on this one */
828	SET_DELTA(e, NULL);
829	break;
830	default:
831	break;
832	case WRITE_ONE_BREAK:
833	e->idx.offset = recursing;
834	return WRITE_ONE_BREAK;
835	}
836	}
837
838	e->idx.offset = *offset;
839	size = write_object(f, e, *offset);
840	if (!size) {
841	e->idx.offset = recursing;
842	return WRITE_ONE_BREAK;
843	}
844	written_list[nr_written++] = &e->idx;
845
846	/* make sure off_t is sufficiently large not to wrap */
847	if (signed_add_overflows(*offset, size))
848	die(_("pack too large for current definition of off_t"));
849	*offset += size;
850	return WRITE_ONE_WRITTEN;
851	}
852
853	static int mark_tagged(const struct reference ref, void cb_data UNUSED)
854	{
855	struct object_id peeled;
856	struct object_entry *entry = packlist_find(&to_pack, ref->oid);
857
858	if (entry)
859	entry->tagged = 1;
860	if (!reference_get_peeled_oid(the_repository, ref, &peeled)) {
861	entry = packlist_find(&to_pack, &peeled);
862	if (entry)
863	entry->tagged = 1;
864	}
865	return 0;
866	}
867
868	static inline unsigned char oe_layer(struct packing_data *pack,
869	struct object_entry *e)
870	{
871	if (!pack->layer)
872	return 0;
873	return pack->layer[e - pack->objects];
874	}
875
876	static inline void add_to_write_order(struct object_entry **wo,
877	unsigned int *endp,
878	struct object_entry *e)
879	{
880	if (e->filled \|\| oe_layer(&to_pack, e) != write_layer)
881	return;
882	wo[(*endp)++] = e;
883	e->filled = 1;
884	}
885
886	static void add_descendants_to_write_order(struct object_entry **wo,
887	unsigned int *endp,
888	struct object_entry *e)
889	{
890	int add_to_order = 1;
891	while (e) {
892	if (add_to_order) {
893	struct object_entry *s;
894	/* add this node... */
895	add_to_write_order(wo, endp, e);
896	/* all its siblings... */
897	for (s = DELTA_SIBLING(e); s; s = DELTA_SIBLING(s)) {
898	add_to_write_order(wo, endp, s);
899	}
900	}
901	/* drop down a level to add left subtree nodes if possible */
902	if (DELTA_CHILD(e)) {
903	add_to_order = 1;
904	e = DELTA_CHILD(e);
905	} else {
906	add_to_order = 0;
907	/* our sibling might have some children, it is next */
908	if (DELTA_SIBLING(e)) {
909	e = DELTA_SIBLING(e);
910	continue;
911	}
912	/* go back to our parent node */
913	e = DELTA(e);
914	while (e && !DELTA_SIBLING(e)) {
915	/* we're on the right side of a subtree, keep
916	* going up until we can go right again */
917	e = DELTA(e);
918	}
919	if (!e) {
920	/* done- we hit our original root node */
921	return;
922	}
923	/* pass it off to sibling at this level */
924	e = DELTA_SIBLING(e);
925	}
926	};
927	}
928
929	static void add_family_to_write_order(struct object_entry **wo,
930	unsigned int *endp,
931	struct object_entry *e)
932	{
933	struct object_entry *root;
934
935	for (root = e; DELTA(root); root = DELTA(root))
936	; /* nothing */
937	add_descendants_to_write_order(wo, endp, root);
938	}
939
940	static void compute_layer_order(struct object_entry *wo, unsigned int wo_end)
941	{
942	unsigned int i, last_untagged;
943	struct object_entry *objects = to_pack.objects;
944
945	for (i = 0; i < to_pack.nr_objects; i++) {
946	if (objects[i].tagged)
947	break;
948	add_to_write_order(wo, wo_end, &objects[i]);
949	}
950	last_untagged = i;
951
952	/*
953	* Then fill all the tagged tips.
954	*/
955	for (; i < to_pack.nr_objects; i++) {
956	if (objects[i].tagged)
957	add_to_write_order(wo, wo_end, &objects[i]);
958	}
959
960	/*
961	* And then all remaining commits and tags.
962	*/
963	for (i = last_untagged; i < to_pack.nr_objects; i++) {
964	if (oe_type(&objects[i]) != OBJ_COMMIT &&
965	oe_type(&objects[i]) != OBJ_TAG)
966	continue;
967	add_to_write_order(wo, wo_end, &objects[i]);
968	}
969
970	/*
971	* And then all the trees.
972	*/
973	for (i = last_untagged; i < to_pack.nr_objects; i++) {
974	if (oe_type(&objects[i]) != OBJ_TREE)
975	continue;
976	add_to_write_order(wo, wo_end, &objects[i]);
977	}
978
979	/*
980	* Finally all the rest in really tight order
981	*/
982	for (i = last_untagged; i < to_pack.nr_objects; i++) {
983	if (!objects[i].filled && oe_layer(&to_pack, &objects[i]) == write_layer)
984	add_family_to_write_order(wo, wo_end, &objects[i]);
985	}
986	}
987
988	static struct object_entry **compute_write_order(void)
989	{
990	uint32_t max_layers = 1;
991	unsigned int i, wo_end;
992
993	struct object_entry **wo;
994	struct object_entry *objects = to_pack.objects;
995
996	for (i = 0; i < to_pack.nr_objects; i++) {
997	objects[i].tagged = 0;
998	objects[i].filled = 0;
999	SET_DELTA_CHILD(&objects[i], NULL);
1000	SET_DELTA_SIBLING(&objects[i], NULL);
1001	}
1002
1003	/*
1004	* Fully connect delta_child/delta_sibling network.
1005	* Make sure delta_sibling is sorted in the original
1006	* recency order.
1007	*/
1008	for (i = to_pack.nr_objects; i > 0;) {
1009	struct object_entry *e = &objects[--i];
1010	if (!DELTA(e))
1011	continue;
1012	/* Mark me as the first child */
1013	e->delta_sibling_idx = DELTA(e)->delta_child_idx;
1014	SET_DELTA_CHILD(DELTA(e), e);
1015	}
1016
1017	/*
1018	* Mark objects that are at the tip of tags.
1019	*/
1020	refs_for_each_tag_ref(get_main_ref_store(the_repository), mark_tagged,
1021	NULL);
1022
1023	if (use_delta_islands) {
1024	max_layers = compute_pack_layers(&to_pack);
1025	free_island_marks();
1026	}
1027
1028	ALLOC_ARRAY(wo, to_pack.nr_objects);
1029	wo_end = 0;
1030
1031	for (; write_layer < max_layers; ++write_layer)
1032	compute_layer_order(wo, &wo_end);
1033
1034	if (wo_end != to_pack.nr_objects)
1035	die(_("ordered %u objects, expected %"PRIu32),
1036	wo_end, to_pack.nr_objects);
1037
1038	return wo;
1039	}
1040
1041
1042	/*
1043	* A reused set of objects. All objects in a chunk have the same
1044	* relative position in the original packfile and the generated
1045	* packfile.
1046	*/
1047
1048	static struct reused_chunk {
1049	/* The offset of the first object of this chunk in the original
1050	* packfile. */
1051	off_t original;
1052	/* The difference for "original" minus the offset of the first object of
1053	* this chunk in the generated packfile. */
1054	off_t difference;
1055	} *reused_chunks;
1056	static int reused_chunks_nr;
1057	static int reused_chunks_alloc;
1058
1059	static void record_reused_object(off_t where, off_t offset)
1060	{
1061	if (reused_chunks_nr && reused_chunks[reused_chunks_nr-1].difference == offset)
1062	return;
1063
1064	ALLOC_GROW(reused_chunks, reused_chunks_nr + 1,
1065	reused_chunks_alloc);
1066	reused_chunks[reused_chunks_nr].original = where;
1067	reused_chunks[reused_chunks_nr].difference = offset;
1068	reused_chunks_nr++;
1069	}
1070
1071	/*
1072	* Binary search to find the chunk that "where" is in. Note
1073	* that we're not looking for an exact match, just the first
1074	* chunk that contains it (which implicitly ends at the start
1075	* of the next chunk.
1076	*/
1077	static off_t find_reused_offset(off_t where)
1078	{
1079	int lo = 0, hi = reused_chunks_nr;
1080	while (lo < hi) {
1081	int mi = lo + ((hi - lo) / 2);
1082	if (where == reused_chunks[mi].original)
1083	return reused_chunks[mi].difference;
1084	if (where < reused_chunks[mi].original)
1085	hi = mi;
1086	else
1087	lo = mi + 1;
1088	}
1089
1090	/*
1091	* The first chunk starts at zero, so we can't have gone below
1092	* there.
1093	*/
1094	assert(lo);
1095	return reused_chunks[lo-1].difference;
1096	}
1097
1098	static void write_reused_pack_one(struct packed_git *reuse_packfile,
1099	size_t pos, struct hashfile *out,
1100	off_t pack_start,
1101	struct pack_window **w_curs)
1102	{
1103	off_t offset, next, cur;
1104	enum object_type type;
1105	size_t size;
1106
1107	offset = pack_pos_to_offset(reuse_packfile, pos);
1108	next = pack_pos_to_offset(reuse_packfile, pos + 1);
1109
1110	record_reused_object(offset,
1111	offset - (hashfile_total(out) - pack_start));
1112
1113	cur = offset;
1114	type = unpack_object_header(reuse_packfile, w_curs, &cur, &size);
1115	assert(type >= 0);
1116
1117	if (type == OBJ_OFS_DELTA) {
1118	off_t base_offset;
1119	off_t fixup;
1120
1121	unsigned char header[MAX_PACK_OBJECT_HEADER];
1122	unsigned len;
1123
1124	base_offset = get_delta_base(reuse_packfile, w_curs, &cur, type, offset);
1125	assert(base_offset != 0);
1126
1127	/* Convert to REF_DELTA if we must... */
1128	if (!allow_ofs_delta) {
1129	uint32_t base_pos;
1130	struct object_id base_oid;
1131
1132	if (offset_to_pack_pos(reuse_packfile, base_offset, &base_pos) < 0)
1133	die(_("expected object at offset %"PRIuMAX" "
1134	"in pack %s"),
1135	(uintmax_t)base_offset,
1136	reuse_packfile->pack_name);
1137
1138	nth_packed_object_id(&base_oid, reuse_packfile,
1139	pack_pos_to_index(reuse_packfile, base_pos));
1140
1141	len = encode_in_pack_object_header(header, sizeof(header),
1142	OBJ_REF_DELTA, size);
1143	hashwrite(out, header, len);
1144	hashwrite(out, base_oid.hash, the_hash_algo->rawsz);
1145	copy_pack_data(out, reuse_packfile, w_curs, cur, next - cur);
1146	return;
1147	}
1148
1149	/* Otherwise see if we need to rewrite the offset... */
1150	fixup = find_reused_offset(offset) -
1151	find_reused_offset(base_offset);
1152	if (fixup) {
1153	unsigned char ofs_header[MAX_PACK_OBJECT_HEADER];
1154	unsigned i, ofs_len;
1155	off_t ofs = offset - base_offset - fixup;
1156
1157	len = encode_in_pack_object_header(header, sizeof(header),
1158	OBJ_OFS_DELTA, size);
1159
1160	i = sizeof(ofs_header) - 1;
1161	ofs_header[i] = ofs & 127;
1162	while (ofs >>= 7)
1163	ofs_header[--i] = 128 \| (--ofs & 127);
1164
1165	ofs_len = sizeof(ofs_header) - i;
1166
1167	hashwrite(out, header, len);
1168	hashwrite(out, ofs_header + sizeof(ofs_header) - ofs_len, ofs_len);
1169	copy_pack_data(out, reuse_packfile, w_curs, cur, next - cur);
1170	return;
1171	}
1172
1173	/* ...otherwise we have no fixup, and can write it verbatim */
1174	}
1175
1176	copy_pack_data(out, reuse_packfile, w_curs, offset, next - offset);
1177	}
1178
1179	static size_t write_reused_pack_verbatim(struct bitmapped_pack *reuse_packfile,
1180	struct hashfile *out,
1181	struct pack_window **w_curs)
1182	{
1183	size_t pos = 0;
1184	size_t end;
1185
1186	if (reuse_packfile->bitmap_pos) {
1187	/*
1188	* We can't reuse whole chunks verbatim out of
1189	* non-preferred packs since we can't guarantee that
1190	* all duplicate objects were resolved in favor of
1191	* that pack.
1192	*
1193	* Even if we have a whole eword_t worth of bits that
1194	* could be reused, there may be objects between the
1195	* objects corresponding to the first and last bit of
1196	* that word which were selected from a different
1197	* pack, causing us to send duplicate or unwanted
1198	* objects.
1199	*
1200	* Handle non-preferred packs from within
1201	* write_reused_pack(), which inspects and reuses
1202	* individual bits.
1203	*/
1204	return reuse_packfile->bitmap_pos / BITS_IN_EWORD;
1205	}
1206
1207	/*
1208	* Only read through the last word whose bits all correspond
1209	* to objects in the given packfile, since we must stop at a
1210	* word boundary.
1211	*
1212	* If there is no whole word to read (i.e. the packfile
1213	* contains fewer than BITS_IN_EWORD objects), then we'll
1214	* inspect bits one-by-one in write_reused_pack().
1215	*/
1216	end = reuse_packfile->bitmap_nr / BITS_IN_EWORD;
1217	if (reuse_packfile_bitmap->word_alloc < end)
1218	BUG("fewer words than expected in reuse_packfile_bitmap");
1219
1220	while (pos < end && reuse_packfile_bitmap->words[pos] == (eword_t)~0)
1221	pos++;
1222
1223	if (pos) {
1224	off_t to_write;
1225
1226	written = (pos * BITS_IN_EWORD);
1227	to_write = pack_pos_to_offset(reuse_packfile->p, written)
1228	- sizeof(struct pack_header);
1229
1230	/* We're recording one chunk, not one object. */
1231	record_reused_object(sizeof(struct pack_header), 0);
1232	hashflush(out);
1233	copy_pack_data(out, reuse_packfile->p, w_curs,
1234	sizeof(struct pack_header), to_write);
1235
1236	display_progress(progress_state, written);
1237	}
1238	return pos;
1239	}
1240
1241	static void write_reused_pack(struct bitmapped_pack *reuse_packfile,
1242	struct hashfile *f)
1243	{
1244	size_t i = reuse_packfile->bitmap_pos / BITS_IN_EWORD;
1245	uint32_t offset;
1246	off_t pack_start = hashfile_total(f) - sizeof(struct pack_header);
1247	struct pack_window *w_curs = NULL;
1248
1249	if (allow_ofs_delta)
1250	i = write_reused_pack_verbatim(reuse_packfile, f, &w_curs);
1251
1252	for (; i < reuse_packfile_bitmap->word_alloc; ++i) {
1253	eword_t word = reuse_packfile_bitmap->words[i];
1254	size_t pos = (i * BITS_IN_EWORD);
1255
1256	for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
1257	uint32_t pack_pos;
1258	if ((word >> offset) == 0)
1259	break;
1260
1261	offset += ewah_bit_ctz64(word >> offset);
1262	if (pos + offset < reuse_packfile->bitmap_pos)
1263	continue;
1264	if (pos + offset >= reuse_packfile->bitmap_pos + reuse_packfile->bitmap_nr)
1265	goto done;
1266
1267	if (reuse_packfile->bitmap_pos) {
1268	/*
1269	* When doing multi-pack reuse on a
1270	* non-preferred pack, translate bit positions
1271	* from the MIDX pseudo-pack order back to their
1272	* pack-relative positions before attempting
1273	* reuse.
1274	*/
1275	struct multi_pack_index *m = reuse_packfile->from_midx;
1276	uint32_t midx_pos;
1277	off_t pack_ofs;
1278
1279	if (!m)
1280	BUG("non-zero bitmap position without MIDX");
1281
1282	midx_pos = pack_pos_to_midx(m, pos + offset);
1283	pack_ofs = nth_midxed_offset(m, midx_pos);
1284
1285	if (offset_to_pack_pos(reuse_packfile->p,
1286	pack_ofs, &pack_pos) < 0)
1287	BUG("could not find expected object at offset %"PRIuMAX" in pack %s",
1288	(uintmax_t)pack_ofs,
1289	pack_basename(reuse_packfile->p));
1290	} else {
1291	/*
1292	* Can use bit positions directly, even for MIDX
1293	* bitmaps. See comment in try_partial_reuse()
1294	* for why.
1295	*/
1296	pack_pos = pos + offset;
1297	}
1298
1299	write_reused_pack_one(reuse_packfile->p, pack_pos, f,
1300	pack_start, &w_curs);
1301	display_progress(progress_state, ++written);
1302	}
1303	}
1304
1305	done:
1306	unuse_pack(&w_curs);
1307	}
1308
1309	static void write_excluded_by_configs(void)
1310	{
1311	struct oidset_iter iter;
1312	const struct object_id *oid;
1313
1314	oidset_iter_init(&excluded_by_config, &iter);
1315	while ((oid = oidset_iter_next(&iter))) {
1316	struct configured_exclusion *ex =
1317	oidmap_get(&configured_exclusions, oid);
1318
1319	if (!ex)
1320	BUG("configured exclusion wasn't configured");
1321	write_in_full(1, ex->pack_hash_hex, strlen(ex->pack_hash_hex));
1322	write_in_full(1, " ", 1);
1323	write_in_full(1, ex->uri, strlen(ex->uri));
1324	write_in_full(1, "\n", 1);
1325	}
1326	}
1327
1328	static const char no_split_warning[] = N_(
1329	"disabling bitmap writing, packs are split due to pack.packSizeLimit"
1330	);
1331
1332	static void write_pack_file(void)
1333	{
1334	uint32_t i = 0, j;
1335	struct hashfile *f;
1336	off_t offset;
1337	uint32_t nr_remaining = nr_result;
1338	time_t last_mtime = 0;
1339	struct object_entry **write_order;
1340
1341	if (progress > pack_to_stdout)
1342	progress_state = start_progress(the_repository,
1343	_("Writing objects"), nr_result);
1344	ALLOC_ARRAY(written_list, to_pack.nr_objects);
1345	write_order = compute_write_order();
1346
1347	do {
1348	unsigned char hash[GIT_MAX_RAWSZ];
1349	char *pack_tmp_name = NULL;
1350
1351	if (pack_to_stdout) {
1352	/*
1353	* This command is most often invoked via
1354	* git-upload-pack(1), which will typically chunk data
1355	* into pktlines. As such, we use the maximum data
1356	* length of them as buffer length.
1357	*
1358	* Note that we need to subtract one though to
1359	* accommodate for the sideband byte.
1360	*/
1361	struct hashfd_options opts = {
1362	.progress = progress_state,
1363	.buffer_len = LARGE_PACKET_DATA_MAX - 1,
1364	};
1365	f = hashfd_ext(the_repository->hash_algo, 1,
1366	"<stdout>", &opts);
1367	} else {
1368	f = create_tmp_packfile(the_repository, &pack_tmp_name);
1369	}
1370
1371	offset = write_pack_header(f, nr_remaining);
1372
1373	if (reuse_packfiles_nr) {
1374	assert(pack_to_stdout);
1375	for (j = 0; j < reuse_packfiles_nr; j++) {
1376	reused_chunks_nr = 0;
1377	write_reused_pack(&reuse_packfiles[j], f);
1378	if (reused_chunks_nr)
1379	reuse_packfiles_used_nr++;
1380	}
1381	offset = hashfile_total(f);
1382	}
1383
1384	nr_written = 0;
1385	for (; i < to_pack.nr_objects; i++) {
1386	struct object_entry *e = write_order[i];
1387	if (write_one(f, e, &offset) == WRITE_ONE_BREAK)
1388	break;
1389	display_progress(progress_state, written);
1390	}
1391
1392	if (pack_to_stdout) {
1393	/*
1394	* We never fsync when writing to stdout since we may
1395	* not be writing to an actual pack file. For instance,
1396	* the upload-pack code passes a pipe here. Calling
1397	* fsync on a pipe results in unnecessary
1398	* synchronization with the reader on some platforms.
1399	*/
1400	finalize_hashfile(f, hash, FSYNC_COMPONENT_NONE,
1401	CSUM_HASH_IN_STREAM \| CSUM_CLOSE);
1402	} else if (nr_written == nr_remaining) {
1403	finalize_hashfile(f, hash, FSYNC_COMPONENT_PACK,
1404	CSUM_HASH_IN_STREAM \| CSUM_FSYNC \| CSUM_CLOSE);
1405	} else {
1406	/*
1407	* If we wrote the wrong number of entries in the
1408	* header, rewrite it like in fast-import.
1409	*/
1410
1411	int fd = finalize_hashfile(f, hash, FSYNC_COMPONENT_PACK, 0);
1412	fixup_pack_header_footer(the_hash_algo, fd, hash,
1413	pack_tmp_name, nr_written,
1414	hash, offset);
1415	close(fd);
1416	if (write_bitmap_index) {
1417	if (write_bitmap_index != WRITE_BITMAP_QUIET)
1418	warning(_(no_split_warning));
1419	write_bitmap_index = 0;
1420	}
1421	}
1422
1423	if (!pack_to_stdout) {
1424	struct stat st;
1425	struct strbuf tmpname = STRBUF_INIT;
1426	struct bitmap_writer bitmap_writer;
1427	char *idx_tmp_name = NULL;
1428
1429	/*
1430	* Packs are runtime accessed in their mtime
1431	* order since newer packs are more likely to contain
1432	* younger objects. So if we are creating multiple
1433	* packs then we should modify the mtime of later ones
1434	* to preserve this property.
1435	*/
1436	if (stat(pack_tmp_name, &st) < 0) {
1437	warning_errno(_("failed to stat %s"), pack_tmp_name);
1438	} else if (!last_mtime) {
1439	last_mtime = st.st_mtime;
1440	} else {
1441	struct utimbuf utb;
1442	utb.actime = st.st_atime;
1443	utb.modtime = --last_mtime;
1444	if (utime(pack_tmp_name, &utb) < 0)
1445	warning_errno(_("failed utime() on %s"), pack_tmp_name);
1446	}
1447
1448	strbuf_addf(&tmpname, "%s-%s.", base_name,
1449	hash_to_hex(hash));
1450
1451	if (write_bitmap_index) {
1452	bitmap_writer_init(&bitmap_writer,
1453	the_repository, &to_pack,
1454	NULL);
1455	bitmap_writer_set_checksum(&bitmap_writer, hash);
1456	bitmap_writer_build_type_index(&bitmap_writer,
1457	written_list);
1458	}
1459
1460	if (cruft)
1461	pack_idx_opts.flags \|= WRITE_MTIMES;
1462
1463	stage_tmp_packfiles(the_repository, &tmpname,
1464	pack_tmp_name, written_list,
1465	nr_written, &to_pack,
1466	&pack_idx_opts, hash,
1467	&idx_tmp_name);
1468
1469	if (write_bitmap_index) {
1470	size_t tmpname_len = tmpname.len;
1471
1472	strbuf_addstr(&tmpname, "bitmap");
1473	stop_progress(&progress_state);
1474
1475	bitmap_writer_show_progress(&bitmap_writer,
1476	progress);
1477	bitmap_writer_select_commits(&bitmap_writer,
1478	indexed_commits,
1479	indexed_commits_nr);
1480	if (bitmap_writer_build(&bitmap_writer) < 0)
1481	die(_("failed to write bitmap index"));
1482	bitmap_writer_finish(&bitmap_writer,
1483	written_list,
1484	tmpname.buf, write_bitmap_options);
1485	bitmap_writer_free(&bitmap_writer);
1486	write_bitmap_index = 0;
1487	strbuf_setlen(&tmpname, tmpname_len);
1488	}
1489
1490	rename_tmp_packfile_idx(the_repository, &tmpname, &idx_tmp_name);
1491
1492	free(idx_tmp_name);
1493	strbuf_release(&tmpname);
1494	free(pack_tmp_name);
1495	puts(hash_to_hex(hash));
1496	}
1497
1498	/* mark written objects as written to previous pack */
1499	for (j = 0; j < nr_written; j++) {
1500	written_list[j]->offset = (off_t)-1;
1501	}
1502	nr_remaining -= nr_written;
1503	} while (nr_remaining && i < to_pack.nr_objects);
1504
1505	free(written_list);
1506	free(write_order);
1507	stop_progress(&progress_state);
1508	if (written != nr_result)
1509	die(_("wrote %"PRIu32" objects while expecting %"PRIu32),
1510	written, nr_result);
1511	trace2_data_intmax("pack-objects", the_repository,
1512	"write_pack_file/wrote", nr_result);
1513	}
1514
1515	static int no_try_delta(const char *path)
1516	{
1517	static struct attr_check *check;
1518
1519	if (!check)
1520	check = attr_check_initl("delta", NULL);
1521	git_check_attr(the_repository->index, path, check);
1522	if (ATTR_FALSE(check->items[0].value))
1523	return 1;
1524	return 0;
1525	}
1526
1527	/*
1528	* When adding an object, check whether we have already added it
1529	* to our packing list. If so, we can skip. However, if we are
1530	* being asked to excludei t, but the previous mention was to include
1531	* it, make sure to adjust its flags and tweak our numbers accordingly.
1532	*
1533	* As an optimization, we pass out the index position where we would have
1534	* found the item, since that saves us from having to look it up again a
1535	* few lines later when we want to add the new entry.
1536	*/
1537	static int have_duplicate_entry(const struct object_id *oid,
1538	int exclude)
1539	{
1540	struct object_entry *entry;
1541
1542	if (reuse_packfile_bitmap &&
1543	bitmap_walk_contains(bitmap_git, reuse_packfile_bitmap, oid))
1544	return 1;
1545
1546	entry = packlist_find(&to_pack, oid);
1547	if (!entry)
1548	return 0;
1549
1550	if (exclude) {
1551	if (!entry->preferred_base)
1552	nr_result--;
1553	entry->preferred_base = 1;
1554	}
1555
1556	return 1;
1557	}
1558
1559	static int want_cruft_object_mtime(struct repository *r,
1560	const struct object_id *oid,
1561	unsigned flags, uint32_t mtime)
1562	{
1563	struct odb_source *source;
1564
1565	for (source = r->objects->sources; source; source = source->next) {
1566	struct odb_source_files *files = odb_source_files_downcast(source);
1567	struct packed_git **cache = packfile_store_get_kept_pack_cache(files->packed, flags);
1568
1569	for (; *cache; cache++) {
1570	struct packed_git p = cache;
1571	off_t ofs;
1572	uint32_t candidate_mtime;
1573
1574	ofs = find_pack_entry_one(oid, p);
1575	if (!ofs)
1576	continue;
1577
1578	/*
1579	* We have a copy of the object 'oid' in a non-cruft
1580	* pack. We can avoid packing an additional copy
1581	* regardless of what the existing copy's mtime is since
1582	* it is outside of a cruft pack.
1583	*/
1584	if (!p->is_cruft)
1585	return 0;
1586
1587	/*
1588	* If we have a copy of the object 'oid' in a cruft
1589	* pack, then either read the cruft pack's mtime for
1590	* that object, or, if that can't be loaded, assume the
1591	* pack's mtime itself.
1592	*/
1593	if (!load_pack_mtimes(p)) {
1594	uint32_t pos;
1595	if (offset_to_pack_pos(p, ofs, &pos) < 0)
1596	continue;
1597	candidate_mtime = nth_packed_mtime(p, pos);
1598	} else {
1599	candidate_mtime = p->mtime;
1600	}
1601
1602	/*
1603	* We have a surviving copy of the object in a cruft
1604	* pack whose mtime is greater than or equal to the one
1605	* we are considering. We can thus avoid packing an
1606	* additional copy of that object.
1607	*/
1608	if (mtime <= candidate_mtime)
1609	return 0;
1610	}
1611	}
1612
1613	return -1;
1614	}
1615
1616	static int want_found_object(const struct object_id *oid, int exclude,
1617	struct packed_git *p, uint32_t mtime)
1618	{
1619	if (exclude)
1620	return 1;
1621	if (incremental)
1622	return 0;
1623
1624	if (!is_pack_valid(p))
1625	return -1;
1626
1627	/*
1628	* When asked to do --local (do not include an object that appears in a
1629	* pack we borrow from elsewhere) or --honor-pack-keep (do not include
1630	* an object that appears in a pack marked with .keep), finding a pack
1631	* that matches the criteria is sufficient for us to decide to omit it.
1632	* However, even if this pack does not satisfy the criteria, we need to
1633	* make sure no copy of this object appears in _any_ pack that makes us
1634	* to omit the object, so we need to check all the packs.
1635	*
1636	* We can however first check whether these options can possibly matter;
1637	* if they do not matter we know we want the object in generated pack.
1638	* Otherwise, we signal "-1" at the end to tell the caller that we do
1639	* not know either way, and it needs to check more packs.
1640	*/
1641
1642	/*
1643	* Objects in packs borrowed from elsewhere are discarded regardless of
1644	* if they appear in other packs that weren't borrowed.
1645	*/
1646	if (local && !p->pack_local)
1647	return 0;
1648
1649	/*
1650	* Then handle .keep first, as we have a fast(er) path there.
1651	*/
1652	if (ignore_packed_keep_on_disk \|\| ignore_packed_keep_in_core \|\|
1653	ignore_packed_keep_in_core_open) {
1654	/*
1655	* Set the flags for the kept-pack cache to be the ones we want
1656	* to ignore.
1657	*
1658	* That is, if we are ignoring objects in on-disk keep packs,
1659	* then we want to search through the on-disk keep and ignore
1660	* the in-core ones.
1661	*/
1662	unsigned flags = 0;
1663	if (ignore_packed_keep_on_disk)
1664	flags \|= KEPT_PACK_ON_DISK;
1665	if (ignore_packed_keep_in_core)
1666	flags \|= KEPT_PACK_IN_CORE;
1667	if (ignore_packed_keep_in_core_open)
1668	flags \|= KEPT_PACK_IN_CORE_OPEN;
1669
1670	/*
1671	* If the object is in a pack that we want to ignore, and we
1672	* don't have any cruft packs that are being retained, we can
1673	* abort quickly.
1674	*/
1675	if (!ignore_packed_keep_in_core_has_cruft) {
1676	if (ignore_packed_keep_on_disk && p->pack_keep)
1677	return 0;
1678	if (ignore_packed_keep_in_core && p->pack_keep_in_core)
1679	return 0;
1680	if (ignore_packed_keep_in_core_open && p->pack_keep_in_core_open)
1681	return 0;
1682	if (has_object_kept_pack(p->repo, oid, flags))
1683	return 0;
1684	} else {
1685	/*
1686	* But if there is at least one cruft pack which
1687	* is being kept, we only want to include the
1688	* provided object if it has a strictly greater
1689	* mtime than any existing cruft copy.
1690	*/
1691	if (!want_cruft_object_mtime(p->repo, oid, flags,
1692	mtime))
1693	return 0;
1694	}
1695	}
1696
1697	/*
1698	* At this point we know definitively that either we don't care about
1699	* keep-packs, or the object is not in one. Keep checking other
1700	* conditions...
1701	*/
1702	if (!local \|\| !have_non_local_packs)
1703	return 1;
1704
1705	/* we don't know yet; keep looking for more packs */
1706	return -1;
1707	}
1708
1709	static int want_object_in_pack_one(struct packed_git *p,
1710	const struct object_id *oid,
1711	int exclude,
1712	struct packed_git **found_pack,
1713	off_t *found_offset,
1714	uint32_t found_mtime)
1715	{
1716	off_t offset;
1717
1718	if (p == *found_pack)
1719	offset = *found_offset;
1720	else
1721	offset = find_pack_entry_one(oid, p);
1722
1723	if (offset) {
1724	if (!*found_pack) {
1725	if (!is_pack_valid(p))
1726	return -1;
1727	*found_offset = offset;
1728	*found_pack = p;
1729	}
1730	return want_found_object(oid, exclude, p, found_mtime);
1731	}
1732	return -1;
1733	}
1734
1735	/*
1736	* Check whether we want the object in the pack (e.g., we do not want
1737	* objects found in non-local stores if the "--local" option was used).
1738	*
1739	* If the caller already knows an existing pack it wants to take the object
1740	* from, that is passed in found_pack and found_offset; otherwise this
1741	* function finds if there is any pack that has the object and returns the pack
1742	* and its offset in these variables.
1743	*/
1744	static int want_object_in_pack_mtime(const struct object_id *oid,
1745	int exclude,
1746	struct packed_git **found_pack,
1747	off_t *found_offset,
1748	uint32_t found_mtime)
1749	{
1750	int want;
1751	struct packfile_list_entry *e;
1752	struct odb_source *source;
1753
1754	if (!exclude && local) {
1755	/*
1756	* Note that we start iterating at `sources->next` so that we
1757	* skip the local object source.
1758	*/
1759	struct odb_source *source = the_repository->objects->sources->next;
1760	for (; source; source = source->next) {
1761	struct odb_source_files *files = odb_source_files_downcast(source);
1762	if (!odb_source_read_object_info(&files->loose->base, oid, NULL, 0))
1763	return 0;
1764	}
1765	}
1766
1767	/*
1768	* If we already know the pack object lives in, start checks from that
1769	* pack - in the usual case when neither --local was given nor .keep files
1770	* are present we will determine the answer right now.
1771	*/
1772	if (*found_pack) {
1773	want = want_found_object(oid, exclude, *found_pack,
1774	found_mtime);
1775	if (want != -1)
1776	return want;
1777
1778	*found_pack = NULL;
1779	*found_offset = 0;
1780	}
1781
1782	odb_prepare_alternates(the_repository->objects);
1783
1784	for (source = the_repository->objects->sources; source; source = source->next) {
1785	struct odb_source_files *files = odb_source_files_downcast(source);
1786	struct multi_pack_index *m = get_multi_pack_index(files->packed);
1787	struct pack_entry e;
1788
1789	if (m && fill_midx_entry(m, oid, &e)) {
1790	want = want_object_in_pack_one(e.p, oid, exclude, found_pack, found_offset, found_mtime);
1791	if (want != -1)
1792	return want;
1793	}
1794	}
1795
1796	for (source = the_repository->objects->sources; source; source = source->next) {
1797	struct odb_source_files *files = odb_source_files_downcast(source);
1798
1799	for (e = files->packed->packs.head; e; e = e->next) {
1800	struct packed_git *p = e->pack;
1801	want = want_object_in_pack_one(p, oid, exclude, found_pack, found_offset, found_mtime);
1802	if (!exclude && want > 0)
1803	packfile_list_prepend(&files->packed->packs, p);
1804	if (want != -1)
1805	return want;
1806	}
1807	}
1808
1809	if (uri_protocols.nr) {
1810	struct configured_exclusion *ex =
1811	oidmap_get(&configured_exclusions, oid);
1812	int i;
1813	const char *p;
1814
1815	if (ex) {
1816	for (i = 0; i < uri_protocols.nr; i++) {
1817	if (skip_prefix(ex->uri,
1818	uri_protocols.items[i].string,
1819	&p) &&
1820	*p == ':') {
1821	oidset_insert(&excluded_by_config, oid);
1822	return 0;
1823	}
1824	}
1825	}
1826	}
1827
1828	return 1;
1829	}
1830
1831	static inline int want_object_in_pack(const struct object_id *oid,
1832	int exclude,
1833	struct packed_git **found_pack,
1834	off_t *found_offset)
1835	{
1836	return want_object_in_pack_mtime(oid, exclude, found_pack, found_offset,
1837	0);
1838	}
1839
1840	static struct object_entry create_object_entry(const struct object_id oid,
1841	enum object_type type,
1842	uint32_t hash,
1843	int exclude,
1844	int no_try_delta,
1845	struct packed_git *found_pack,
1846	off_t found_offset)
1847	{
1848	struct object_entry *entry;
1849
1850	entry = packlist_alloc(&to_pack, oid);
1851	entry->hash = hash;
1852	oe_set_type(entry, type);
1853	if (exclude)
1854	entry->preferred_base = 1;
1855	else
1856	nr_result++;
1857	if (found_pack) {
1858	oe_set_in_pack(&to_pack, entry, found_pack);
1859	entry->in_pack_offset = found_offset;
1860	}
1861
1862	entry->no_try_delta = no_try_delta;
1863
1864	return entry;
1865	}
1866
1867	static const char no_closure_warning[] = N_(
1868	"disabling bitmap writing, as some objects are not being packed"
1869	);
1870
1871	static void add_object_entry(const struct object_id *oid, enum object_type type,
1872	const char *name, int exclude)
1873	{
1874	struct packed_git *found_pack = NULL;
1875	off_t found_offset = 0;
1876
1877	display_progress(progress_state, ++nr_seen);
1878
1879	if (have_duplicate_entry(oid, exclude))
1880	return;
1881
1882	if (!want_object_in_pack(oid, exclude, &found_pack, &found_offset)) {
1883	/* The pack is missing an object, so it will not have closure */
1884	if (write_bitmap_index) {
1885	if (write_bitmap_index != WRITE_BITMAP_QUIET)
1886	warning(_(no_closure_warning));
1887	write_bitmap_index = 0;
1888	}
1889	return;
1890	}
1891
1892	create_object_entry(oid, type, pack_name_hash_fn(name),
1893	exclude, name && no_try_delta(name),
1894	found_pack, found_offset);
1895	}
1896
1897	static int add_object_entry_from_bitmap(const struct object_id *oid,
1898	enum object_type type,
1899	int flags UNUSED, uint32_t name_hash,
1900	struct packed_git *pack, off_t offset,
1901	void *payload UNUSED)
1902	{
1903	display_progress(progress_state, ++nr_seen);
1904
1905	if (have_duplicate_entry(oid, 0))
1906	return 0;
1907
1908	if (!want_object_in_pack(oid, 0, &pack, &offset))
1909	return 0;
1910
1911	create_object_entry(oid, type, name_hash, 0, 0, pack, offset);
1912	return 0;
1913	}
1914
1915	struct pbase_tree_cache {
1916	struct object_id oid;
1917	int ref;
1918	int temporary;
1919	void *tree_data;
1920	unsigned long tree_size;
1921	};
1922
1923	static struct pbase_tree_cache *(pbase_tree_cache[256]);
1924	static int pbase_tree_cache_ix(const struct object_id *oid)
1925	{
1926	return oid->hash[0] % ARRAY_SIZE(pbase_tree_cache);
1927	}
1928	static int pbase_tree_cache_ix_incr(int ix)
1929	{
1930	return (ix+1) % ARRAY_SIZE(pbase_tree_cache);
1931	}
1932
1933	static struct pbase_tree {
1934	struct pbase_tree *next;
1935	/* This is a phony "cache" entry; we are not
1936	* going to evict it or find it through _get()
1937	* mechanism -- this is for the toplevel node that
1938	* would almost always change with any commit.
1939	*/
1940	struct pbase_tree_cache pcache;
1941	} *pbase_tree;
1942
1943	static struct pbase_tree_cache pbase_tree_get(const struct object_id oid)
1944	{
1945	struct pbase_tree_cache ent, nent;
1946	void *data;
1947	unsigned long size;
1948	size_t size_st = 0;
1949	enum object_type type;
1950	int neigh;
1951	int my_ix = pbase_tree_cache_ix(oid);
1952	int available_ix = -1;
1953
1954	/* pbase-tree-cache acts as a limited hashtable.
1955	* your object will be found at your index or within a few
1956	* slots after that slot if it is cached.
1957	*/
1958	for (neigh = 0; neigh < 8; neigh++) {
1959	ent = pbase_tree_cache[my_ix];
1960	if (ent && oideq(&ent->oid, oid)) {
1961	ent->ref++;
1962	return ent;
1963	}
1964	else if (((available_ix < 0) && (!ent \|\| !ent->ref)) \|\|
1965	((0 <= available_ix) &&
1966	(!ent && pbase_tree_cache[available_ix])))
1967	available_ix = my_ix;
1968	if (!ent)
1969	break;
1970	my_ix = pbase_tree_cache_ix_incr(my_ix);
1971	}
1972
1973	/* Did not find one. Either we got a bogus request or
1974	* we need to read and perhaps cache.
1975	*/
1976	data = odb_read_object(the_repository->objects, oid, &type, &size_st);
1977	size = cast_size_t_to_ulong(size_st);
1978	if (!data)
1979	return NULL;
1980	if (type != OBJ_TREE) {
1981	free(data);
1982	return NULL;
1983	}
1984
1985	/* We need to either cache or return a throwaway copy */
1986
1987	if (available_ix < 0)
1988	ent = NULL;
1989	else {
1990	ent = pbase_tree_cache[available_ix];
1991	my_ix = available_ix;
1992	}
1993
1994	if (!ent) {
1995	nent = xmalloc(sizeof(*nent));
1996	nent->temporary = (available_ix < 0);
1997	}
1998	else {
1999	/* evict and reuse */
2000	free(ent->tree_data);
2001	nent = ent;
2002	}
2003	oidcpy(&nent->oid, oid);
2004	nent->tree_data = data;
2005	nent->tree_size = size;
2006	nent->ref = 1;
2007	if (!nent->temporary)
2008	pbase_tree_cache[my_ix] = nent;
2009	return nent;
2010	}
2011
2012	static void pbase_tree_put(struct pbase_tree_cache *cache)
2013	{
2014	if (!cache->temporary) {
2015	cache->ref--;
2016	return;
2017	}
2018	free(cache->tree_data);
2019	free(cache);
2020	}
2021
2022	static size_t name_cmp_len(const char *name)
2023	{
2024	return strcspn(name, "\n/");
2025	}
2026
2027	static void add_pbase_object(struct tree_desc *tree,
2028	const char *name,
2029	size_t cmplen,
2030	const char *fullname)
2031	{
2032	struct name_entry entry;
2033	int cmp;
2034
2035	while (tree_entry(tree,&entry)) {
2036	if (S_ISGITLINK(entry.mode))
2037	continue;
2038	cmp = tree_entry_len(&entry) != cmplen ? 1 :
2039	memcmp(name, entry.path, cmplen);
2040	if (cmp > 0)
2041	continue;
2042	if (cmp < 0)
2043	return;
2044	if (name[cmplen] != '/') {
2045	add_object_entry(&entry.oid,
2046	object_type(entry.mode),
2047	fullname, 1);
2048	return;
2049	}
2050	if (S_ISDIR(entry.mode)) {
2051	struct tree_desc sub;
2052	struct pbase_tree_cache *tree;
2053	const char *down = name+cmplen+1;
2054	size_t downlen = name_cmp_len(down);
2055
2056	tree = pbase_tree_get(&entry.oid);
2057	if (!tree)
2058	return;
2059	init_tree_desc(&sub, &tree->oid,
2060	tree->tree_data, tree->tree_size);
2061
2062	add_pbase_object(&sub, down, downlen, fullname);
2063	pbase_tree_put(tree);
2064	}
2065	}
2066	}
2067
2068	static unsigned *done_pbase_paths;
2069	static int done_pbase_paths_num;
2070	static int done_pbase_paths_alloc;
2071	static int done_pbase_path_pos(unsigned hash)
2072	{
2073	int lo = 0;
2074	int hi = done_pbase_paths_num;
2075	while (lo < hi) {
2076	int mi = lo + (hi - lo) / 2;
2077	if (done_pbase_paths[mi] == hash)
2078	return mi;
2079	if (done_pbase_paths[mi] < hash)
2080	hi = mi;
2081	else
2082	lo = mi + 1;
2083	}
2084	return -lo-1;
2085	}
2086
2087	static int check_pbase_path(unsigned hash)
2088	{
2089	int pos = done_pbase_path_pos(hash);
2090	if (0 <= pos)
2091	return 1;
2092	pos = -pos - 1;
2093	ALLOC_GROW(done_pbase_paths,
2094	done_pbase_paths_num + 1,
2095	done_pbase_paths_alloc);
2096	done_pbase_paths_num++;
2097	if (pos < done_pbase_paths_num)
2098	MOVE_ARRAY(done_pbase_paths + pos + 1, done_pbase_paths + pos,
2099	done_pbase_paths_num - pos - 1);
2100	done_pbase_paths[pos] = hash;
2101	return 0;
2102	}
2103
2104	static void add_preferred_base_object(const char *name)
2105	{
2106	struct pbase_tree *it;
2107	size_t cmplen;
2108	unsigned hash = pack_name_hash_fn(name);
2109
2110	if (!num_preferred_base \|\| check_pbase_path(hash))
2111	return;
2112
2113	cmplen = name_cmp_len(name);
2114	for (it = pbase_tree; it; it = it->next) {
2115	if (cmplen == 0) {
2116	add_object_entry(&it->pcache.oid, OBJ_TREE, NULL, 1);
2117	}
2118	else {
2119	struct tree_desc tree;
2120	init_tree_desc(&tree, &it->pcache.oid,
2121	it->pcache.tree_data, it->pcache.tree_size);
2122	add_pbase_object(&tree, name, cmplen, name);
2123	}
2124	}
2125	}
2126
2127	static void add_preferred_base(struct object_id *oid)
2128	{
2129	struct pbase_tree *it;
2130	void *data;
2131	unsigned long size;
2132	size_t size_st = 0;
2133	struct object_id tree_oid;
2134
2135	if (window <= num_preferred_base++)
2136	return;
2137
2138	data = odb_read_object_peeled(the_repository->objects, oid,
2139	OBJ_TREE, &size_st, &tree_oid);
2140	size = cast_size_t_to_ulong(size_st);
2141	if (!data)
2142	return;
2143
2144	for (it = pbase_tree; it; it = it->next) {
2145	if (oideq(&it->pcache.oid, &tree_oid)) {
2146	free(data);
2147	return;
2148	}
2149	}
2150
2151	CALLOC_ARRAY(it, 1);
2152	it->next = pbase_tree;
2153	pbase_tree = it;
2154
2155	oidcpy(&it->pcache.oid, &tree_oid);
2156	it->pcache.tree_data = data;
2157	it->pcache.tree_size = size;
2158	}
2159
2160	static void cleanup_preferred_base(void)
2161	{
2162	struct pbase_tree *it;
2163	unsigned i;
2164
2165	it = pbase_tree;
2166	pbase_tree = NULL;
2167	while (it) {
2168	struct pbase_tree *tmp = it;
2169	it = tmp->next;
2170	free(tmp->pcache.tree_data);
2171	free(tmp);
2172	}
2173
2174	for (i = 0; i < ARRAY_SIZE(pbase_tree_cache); i++) {
2175	if (!pbase_tree_cache[i])
2176	continue;
2177	free(pbase_tree_cache[i]->tree_data);
2178	FREE_AND_NULL(pbase_tree_cache[i]);
2179	}
2180
2181	FREE_AND_NULL(done_pbase_paths);
2182	done_pbase_paths_num = done_pbase_paths_alloc = 0;
2183	}
2184
2185	/*
2186	* Return 1 iff the object specified by "delta" can be sent
2187	* literally as a delta against the base in "base_sha1". If
2188	* so, then *base_out will point to the entry in our packing
2189	* list, or NULL if we must use the external-base list.
2190	*
2191	* Depth value does not matter - find_deltas() will
2192	* never consider reused delta as the base object to
2193	* deltify other objects against, in order to avoid
2194	* circular deltas.
2195	*/
2196	static int can_reuse_delta(const struct object_id *base_oid,
2197	struct object_entry *delta,
2198	struct object_entry **base_out)
2199	{
2200	struct object_entry *base;
2201
2202	/*
2203	* First see if we're already sending the base (or it's explicitly in
2204	* our "excluded" list).
2205	*/
2206	base = packlist_find(&to_pack, base_oid);
2207	if (base) {
2208	if (!in_same_island(&delta->idx.oid, &base->idx.oid))
2209	return 0;
2210	*base_out = base;
2211	return 1;
2212	}
2213
2214	/*
2215	* Otherwise, reachability bitmaps may tell us if the receiver has it,
2216	* even if it was buried too deep in history to make it into the
2217	* packing list.
2218	*/
2219	if (thin && bitmap_has_oid_in_uninteresting(bitmap_git, base_oid)) {
2220	if (use_delta_islands) {
2221	if (!in_same_island(&delta->idx.oid, base_oid))
2222	return 0;
2223	}
2224	*base_out = NULL;
2225	return 1;
2226	}
2227
2228	return 0;
2229	}
2230
2231	static void prefetch_to_pack(uint32_t object_index_start) {
2232	struct oid_array to_fetch = OID_ARRAY_INIT;
2233	uint32_t i;
2234
2235	for (i = object_index_start; i < to_pack.nr_objects; i++) {
2236	struct object_entry *entry = to_pack.objects + i;
2237
2238	if (!odb_read_object_info_extended(the_repository->objects,
2239	&entry->idx.oid,
2240	NULL,
2241	OBJECT_INFO_FOR_PREFETCH))
2242	continue;
2243	oid_array_append(&to_fetch, &entry->idx.oid);
2244	}
2245	promisor_remote_get_direct(the_repository,
2246	to_fetch.oid, to_fetch.nr);
2247	oid_array_clear(&to_fetch);
2248	}
2249
2250	static void check_object(struct object_entry *entry, uint32_t object_index)
2251	{
2252	size_t canonical_size;
2253	enum object_type type;
2254	struct object_info oi = {.typep = &type, .sizep = &canonical_size};
2255
2256	if (IN_PACK(entry)) {
2257	struct packed_git *p = IN_PACK(entry);
2258	struct pack_window *w_curs = NULL;
2259	int have_base = 0;
2260	struct object_id base_ref;
2261	struct object_entry *base_entry;
2262	unsigned long used, used_0;
2263	unsigned long avail;
2264	off_t ofs;
2265	unsigned char *buf, c;
2266	enum object_type type;
2267	size_t in_pack_size;
2268
2269	buf = use_pack(p, &w_curs, entry->in_pack_offset, &avail);
2270
2271	/*
2272	* We want in_pack_type even if we do not reuse delta
2273	* since non-delta representations could still be reused.
2274	*/
2275	used = unpack_object_header_buffer(buf, avail,
2276	&type,
2277	&in_pack_size);
2278	if (used == 0)
2279	goto give_up;
2280
2281	if (type < 0)
2282	BUG("invalid type %d", type);
2283	entry->in_pack_type = type;
2284
2285	/*
2286	* Determine if this is a delta and if so whether we can
2287	* reuse it or not. Otherwise let's find out as cheaply as
2288	* possible what the actual type and size for this object is.
2289	*/
2290	switch (entry->in_pack_type) {
2291	default:
2292	/* Not a delta hence we've already got all we need. */
2293	oe_set_type(entry, entry->in_pack_type);
2294	SET_SIZE(entry, in_pack_size);
2295	entry->in_pack_header_size = used;
2296	if (oe_type(entry) < OBJ_COMMIT \|\| oe_type(entry) > OBJ_BLOB)
2297	goto give_up;
2298	unuse_pack(&w_curs);
2299	return;
2300	case OBJ_REF_DELTA:
2301	if (reuse_delta && !entry->preferred_base) {
2302	oidread(&base_ref,
2303	use_pack(p, &w_curs,
2304	entry->in_pack_offset + used,
2305	NULL),
2306	the_repository->hash_algo);
2307	have_base = 1;
2308	}
2309	entry->in_pack_header_size = used + the_hash_algo->rawsz;
2310	break;
2311	case OBJ_OFS_DELTA:
2312	buf = use_pack(p, &w_curs,
2313	entry->in_pack_offset + used, NULL);
2314	used_0 = 0;
2315	c = buf[used_0++];
2316	ofs = c & 127;
2317	while (c & 128) {
2318	ofs += 1;
2319	if (!ofs \|\| MSB(ofs, 7)) {
2320	error(_("delta base offset overflow in pack for %s"),
2321	oid_to_hex(&entry->idx.oid));
2322	goto give_up;
2323	}
2324	c = buf[used_0++];
2325	ofs = (ofs << 7) + (c & 127);
2326	}
2327	ofs = entry->in_pack_offset - ofs;
2328	if (ofs <= 0 \|\| ofs >= entry->in_pack_offset) {
2329	error(_("delta base offset out of bound for %s"),
2330	oid_to_hex(&entry->idx.oid));
2331	goto give_up;
2332	}
2333	if (reuse_delta && !entry->preferred_base) {
2334	uint32_t pos;
2335	if (offset_to_pack_pos(p, ofs, &pos) < 0)
2336	goto give_up;
2337	if (!nth_packed_object_id(&base_ref, p,
2338	pack_pos_to_index(p, pos)))
2339	have_base = 1;
2340	}
2341	entry->in_pack_header_size = used + used_0;
2342	break;
2343	}
2344
2345	if (have_base &&
2346	can_reuse_delta(&base_ref, entry, &base_entry)) {
2347	oe_set_type(entry, entry->in_pack_type);
2348	SET_SIZE(entry, in_pack_size); /* delta size */
2349	SET_DELTA_SIZE(entry, in_pack_size);
2350
2351	if (base_entry) {
2352	SET_DELTA(entry, base_entry);
2353	entry->delta_sibling_idx = base_entry->delta_child_idx;
2354	SET_DELTA_CHILD(base_entry, entry);
2355	} else {
2356	SET_DELTA_EXT(entry, &base_ref);
2357	}
2358
2359	unuse_pack(&w_curs);
2360	return;
2361	}
2362
2363	if (oe_type(entry)) {
2364	off_t delta_pos;
2365
2366	/*
2367	* This must be a delta and we already know what the
2368	* final object type is. Let's extract the actual
2369	* object size from the delta header.
2370	*/
2371	delta_pos = entry->in_pack_offset + entry->in_pack_header_size;
2372	canonical_size = get_size_from_delta(p, &w_curs,
2373	delta_pos);
2374	if (canonical_size == 0)
2375	goto give_up;
2376	SET_SIZE(entry, canonical_size);
2377	unuse_pack(&w_curs);
2378	return;
2379	}
2380
2381	/*
2382	* No choice but to fall back to the recursive delta walk
2383	* with odb_read_object_info() to find about the object type
2384	* at this point...
2385	*/
2386	give_up:
2387	unuse_pack(&w_curs);
2388	}
2389
2390	if (odb_read_object_info_extended(the_repository->objects, &entry->idx.oid, &oi,
2391	OBJECT_INFO_SKIP_FETCH_OBJECT \| OBJECT_INFO_LOOKUP_REPLACE) < 0) {
2392	if (repo_has_promisor_remote(the_repository)) {
2393	prefetch_to_pack(object_index);
2394	if (odb_read_object_info_extended(the_repository->objects, &entry->idx.oid, &oi,
2395	OBJECT_INFO_SKIP_FETCH_OBJECT \| OBJECT_INFO_LOOKUP_REPLACE) < 0)
2396	type = -1;
2397	} else {
2398	type = -1;
2399	}
2400	}
2401	oe_set_type(entry, type);
2402	if (entry->type_valid) {
2403	SET_SIZE(entry, canonical_size);
2404	} else {
2405	/*
2406	* Bad object type is checked in prepare_pack(). This is
2407	* to permit a missing preferred base object to be ignored
2408	* as a preferred base. Doing so can result in a larger
2409	* pack file, but the transfer will still take place.
2410	*/
2411	}
2412	}
2413
2414	static int pack_offset_sort(const void _a, const void _b)
2415	{
2416	const struct object_entry a = (struct object_entry **)_a;
2417	const struct object_entry b = (struct object_entry **)_b;
2418	const struct packed_git *a_in_pack = IN_PACK(a);
2419	const struct packed_git *b_in_pack = IN_PACK(b);
2420
2421	/* avoid filesystem trashing with loose objects */
2422	if (!a_in_pack && !b_in_pack)
2423	return oidcmp(&a->idx.oid, &b->idx.oid);
2424
2425	if (a_in_pack < b_in_pack)
2426	return -1;
2427	if (a_in_pack > b_in_pack)
2428	return 1;
2429	return a->in_pack_offset < b->in_pack_offset ? -1 :
2430	(a->in_pack_offset > b->in_pack_offset);
2431	}
2432
2433	/*
2434	* Drop an on-disk delta we were planning to reuse. Naively, this would
2435	* just involve blanking out the "delta" field, but we have to deal
2436	* with some extra book-keeping:
2437	*
2438	* 1. Removing ourselves from the delta_sibling linked list.
2439	*
2440	* 2. Updating our size/type to the non-delta representation. These were
2441	* either not recorded initially (size) or overwritten with the delta type
2442	* (type) when check_object() decided to reuse the delta.
2443	*
2444	* 3. Resetting our delta depth, as we are now a base object.
2445	*/
2446	static void drop_reused_delta(struct object_entry *entry)
2447	{
2448	unsigned *idx = &to_pack.objects[entry->delta_idx - 1].delta_child_idx;
2449	struct object_info oi = OBJECT_INFO_INIT;
2450	enum object_type type;
2451	size_t size;
2452
2453	while (*idx) {
2454	struct object_entry oe = &to_pack.objects[idx - 1];
2455
2456	if (oe == entry)
2457	*idx = oe->delta_sibling_idx;
2458	else
2459	idx = &oe->delta_sibling_idx;
2460	}
2461	SET_DELTA(entry, NULL);
2462	entry->depth = 0;
2463
2464	oi.sizep = &size;
2465	oi.typep = &type;
2466	if (packed_object_info(NULL, IN_PACK(entry), entry->in_pack_offset, &oi) < 0) {
2467	/*
2468	* We failed to get the info from this pack for some reason;
2469	* fall back to odb_read_object_info, which may find another copy.
2470	* And if that fails, the error will be recorded in oe_type(entry)
2471	* and dealt with in prepare_pack().
2472	*/
2473	oe_set_type(entry,
2474	odb_read_object_info(the_repository->objects,
2475	&entry->idx.oid, &size));
2476	} else {
2477	oe_set_type(entry, type);
2478	}
2479	SET_SIZE(entry, size);
2480	}
2481
2482	/*
2483	* Follow the chain of deltas from this entry onward, throwing away any links
2484	* that cause us to hit a cycle (as determined by the DFS state flags in
2485	* the entries).
2486	*
2487	* We also detect too-long reused chains that would violate our --depth
2488	* limit.
2489	*/
2490	static void break_delta_chains(struct object_entry *entry)
2491	{
2492	/*
2493	* The actual depth of each object we will write is stored as an int,
2494	* as it cannot exceed our int "depth" limit. But before we break
2495	* changes based no that limit, we may potentially go as deep as the
2496	* number of objects, which is elsewhere bounded to a uint32_t.
2497	*/
2498	uint32_t total_depth;
2499	struct object_entry cur, next;
2500
2501	for (cur = entry, total_depth = 0;
2502	cur;
2503	cur = DELTA(cur), total_depth++) {
2504	if (cur->dfs_state == DFS_DONE) {
2505	/*
2506	* We've already seen this object and know it isn't
2507	* part of a cycle. We do need to append its depth
2508	* to our count.
2509	*/
2510	total_depth += cur->depth;
2511	break;
2512	}
2513
2514	/*
2515	* We break cycles before looping, so an ACTIVE state (or any
2516	* other cruft which made its way into the state variable)
2517	* is a bug.
2518	*/
2519	if (cur->dfs_state != DFS_NONE)
2520	BUG("confusing delta dfs state in first pass: %d",
2521	cur->dfs_state);
2522
2523	/*
2524	* Now we know this is the first time we've seen the object. If
2525	* it's not a delta, we're done traversing, but we'll mark it
2526	* done to save time on future traversals.
2527	*/
2528	if (!DELTA(cur)) {
2529	cur->dfs_state = DFS_DONE;
2530	break;
2531	}
2532
2533	/*
2534	* Mark ourselves as active and see if the next step causes
2535	* us to cycle to another active object. It's important to do
2536	* this _before_ we loop, because it impacts where we make the
2537	* cut, and thus how our total_depth counter works.
2538	* E.g., We may see a partial loop like:
2539	*
2540	* A -> B -> C -> D -> B
2541	*
2542	* Cutting B->C breaks the cycle. But now the depth of A is
2543	* only 1, and our total_depth counter is at 3. The size of the
2544	* error is always one less than the size of the cycle we
2545	* broke. Commits C and D were "lost" from A's chain.
2546	*
2547	* If we instead cut D->B, then the depth of A is correct at 3.
2548	* We keep all commits in the chain that we examined.
2549	*/
2550	cur->dfs_state = DFS_ACTIVE;
2551	if (DELTA(cur)->dfs_state == DFS_ACTIVE) {
2552	drop_reused_delta(cur);
2553	cur->dfs_state = DFS_DONE;
2554	break;
2555	}
2556	}
2557
2558	/*
2559	* And now that we've gone all the way to the bottom of the chain, we
2560	* need to clear the active flags and set the depth fields as
2561	* appropriate. Unlike the loop above, which can quit when it drops a
2562	* delta, we need to keep going to look for more depth cuts. So we need
2563	* an extra "next" pointer to keep going after we reset cur->delta.
2564	*/
2565	for (cur = entry; cur; cur = next) {
2566	next = DELTA(cur);
2567
2568	/*
2569	* We should have a chain of zero or more ACTIVE states down to
2570	* a final DONE. We can quit after the DONE, because either it
2571	* has no bases, or we've already handled them in a previous
2572	* call.
2573	*/
2574	if (cur->dfs_state == DFS_DONE)
2575	break;
2576	else if (cur->dfs_state != DFS_ACTIVE)
2577	BUG("confusing delta dfs state in second pass: %d",
2578	cur->dfs_state);
2579
2580	/*
2581	* If the total_depth is more than depth, then we need to snip
2582	* the chain into two or more smaller chains that don't exceed
2583	* the maximum depth. Most of the resulting chains will contain
2584	* (depth + 1) entries (i.e., depth deltas plus one base), and
2585	* the last chain (i.e., the one containing entry) will contain
2586	* whatever entries are left over, namely
2587	* (total_depth % (depth + 1)) of them.
2588	*
2589	* Since we are iterating towards decreasing depth, we need to
2590	* decrement total_depth as we go, and we need to write to the
2591	* entry what its final depth will be after all of the
2592	* snipping. Since we're snipping into chains of length (depth
2593	* + 1) entries, the final depth of an entry will be its
2594	* original depth modulo (depth + 1). Any time we encounter an
2595	* entry whose final depth is supposed to be zero, we snip it
2596	* from its delta base, thereby making it so.
2597	*/
2598	cur->depth = (total_depth--) % (depth + 1);
2599	if (!cur->depth)
2600	drop_reused_delta(cur);
2601
2602	cur->dfs_state = DFS_DONE;
2603	}
2604	}
2605
2606	static void get_object_details(void)
2607	{
2608	uint32_t i;
2609	struct object_entry **sorted_by_offset;
2610
2611	if (progress)
2612	progress_state = start_progress(the_repository,
2613	_("Counting objects"),
2614	to_pack.nr_objects);
2615
2616	CALLOC_ARRAY(sorted_by_offset, to_pack.nr_objects);
2617	for (i = 0; i < to_pack.nr_objects; i++)
2618	sorted_by_offset[i] = to_pack.objects + i;
2619	QSORT(sorted_by_offset, to_pack.nr_objects, pack_offset_sort);
2620
2621	for (i = 0; i < to_pack.nr_objects; i++) {
2622	struct object_entry *entry = sorted_by_offset[i];
2623	check_object(entry, i);
2624	if (entry->type_valid &&
2625	oe_size_greater_than(&to_pack, entry,
2626	repo_settings_get_big_file_threshold(the_repository)))
2627	entry->no_try_delta = 1;
2628	display_progress(progress_state, i + 1);
2629	}
2630	stop_progress(&progress_state);
2631
2632	/*
2633	* This must happen in a second pass, since we rely on the delta
2634	* information for the whole list being completed.
2635	*/
2636	for (i = 0; i < to_pack.nr_objects; i++)
2637	break_delta_chains(&to_pack.objects[i]);
2638
2639	free(sorted_by_offset);
2640	}
2641
2642	/*
2643	* We search for deltas in a list sorted by type, by filename hash, and then
2644	* by size, so that we see progressively smaller and smaller files.
2645	* That's because we prefer deltas to be from the bigger file
2646	* to the smaller -- deletes are potentially cheaper, but perhaps
2647	* more importantly, the bigger file is likely the more recent
2648	* one. The deepest deltas are therefore the oldest objects which are
2649	* less susceptible to be accessed often.
2650	*/
2651	static int type_size_sort(const void _a, const void _b)
2652	{
2653	const struct object_entry a = (struct object_entry **)_a;
2654	const struct object_entry b = (struct object_entry **)_b;
2655	const enum object_type a_type = oe_type(a);
2656	const enum object_type b_type = oe_type(b);
2657	const unsigned long a_size = SIZE(a);
2658	const unsigned long b_size = SIZE(b);
2659
2660	if (a_type > b_type)
2661	return -1;
2662	if (a_type < b_type)
2663	return 1;
2664	if (a->hash > b->hash)
2665	return -1;
2666	if (a->hash < b->hash)
2667	return 1;
2668	if (a->preferred_base > b->preferred_base)
2669	return -1;
2670	if (a->preferred_base < b->preferred_base)
2671	return 1;
2672	if (use_delta_islands) {
2673	const int island_cmp = island_delta_cmp(&a->idx.oid, &b->idx.oid);
2674	if (island_cmp)
2675	return island_cmp;
2676	}
2677	if (a_size > b_size)
2678	return -1;
2679	if (a_size < b_size)
2680	return 1;
2681	return a < b ? -1 : (a > b); /* newest first */
2682	}
2683
2684	struct unpacked {
2685	struct object_entry *entry;
2686	void *data;
2687	struct delta_index *index;
2688	unsigned depth;
2689	};
2690
2691	static int delta_cacheable(unsigned long src_size, unsigned long trg_size,
2692	unsigned long delta_size)
2693	{
2694	if (max_delta_cache_size && delta_cache_size + delta_size > max_delta_cache_size)
2695	return 0;
2696
2697	if (delta_size < cache_max_small_delta_size)
2698	return 1;
2699
2700	/* cache delta, if objects are large enough compared to delta size */
2701	if ((src_size >> 20) + (trg_size >> 21) > (delta_size >> 10))
2702	return 1;
2703
2704	return 0;
2705	}
2706
2707	/* Protect delta_cache_size */
2708	static pthread_mutex_t cache_mutex;
2709	#define cache_lock() pthread_mutex_lock(&cache_mutex)
2710	#define cache_unlock() pthread_mutex_unlock(&cache_mutex)
2711
2712	/*
2713	* Protect object list partitioning (e.g. struct thread_param) and
2714	* progress_state
2715	*/
2716	static pthread_mutex_t progress_mutex;
2717	#define progress_lock() pthread_mutex_lock(&progress_mutex)
2718	#define progress_unlock() pthread_mutex_unlock(&progress_mutex)
2719
2720	/*
2721	* Access to struct object_entry is unprotected since each thread owns
2722	* a portion of the main object list. Just don't access object entries
2723	* ahead in the list because they can be stolen and would need
2724	* progress_mutex for protection.
2725	*/
2726
2727	static inline int oe_size_less_than(struct packing_data *pack,
2728	const struct object_entry *lhs,
2729	size_t rhs)
2730	{
2731	if (lhs->size_valid)
2732	return lhs->size_ < rhs;
2733	if (rhs < pack->oe_size_limit) /* rhs < 2^x <= lhs ? */
2734	return 0;
2735	return oe_get_size_slow(pack, lhs) < rhs;
2736	}
2737
2738	static inline void oe_set_tree_depth(struct packing_data *pack,
2739	struct object_entry *e,
2740	unsigned int tree_depth)
2741	{
2742	if (!pack->tree_depth)
2743	CALLOC_ARRAY(pack->tree_depth, pack->nr_alloc);
2744	pack->tree_depth[e - pack->objects] = tree_depth;
2745	}
2746
2747	static void record_tree_depth(const struct object_id oid, const char name)
2748	{
2749	const char *p;
2750	unsigned depth;
2751	struct object_entry *ent;
2752
2753	/* the empty string is a root tree, which is depth 0 */
2754	depth = *name ? 1 : 0;
2755	for (p = strchr(name, '/'); p; p = strchr(p + 1, '/'))
2756	depth++;
2757
2758	ent = packlist_find(&to_pack, oid);
2759	if (ent && depth > oe_tree_depth(&to_pack, ent))
2760	oe_set_tree_depth(&to_pack, ent, depth);
2761	}
2762
2763	/*
2764	* Return the size of the object without doing any delta
2765	* reconstruction (so non-deltas are true object sizes, but deltas
2766	* return the size of the delta data).
2767	*/
2768	size_t oe_get_size_slow(struct packing_data *pack,
2769	const struct object_entry *e)
2770	{
2771	struct packed_git *p;
2772	struct pack_window *w_curs;
2773	unsigned char *buf;
2774	enum object_type type;
2775	unsigned long used, avail;
2776	size_t size;
2777
2778	if (e->type_ != OBJ_OFS_DELTA && e->type_ != OBJ_REF_DELTA) {
2779	size_t sz;
2780	packing_data_lock(&to_pack);
2781	if (odb_read_object_info(the_repository->objects,
2782	&e->idx.oid, &sz) < 0)
2783	die(_("unable to get size of %s"),
2784	oid_to_hex(&e->idx.oid));
2785	packing_data_unlock(&to_pack);
2786	return sz;
2787	}
2788
2789	p = oe_in_pack(pack, e);
2790	if (!p)
2791	BUG("when e->type is a delta, it must belong to a pack");
2792
2793	packing_data_lock(&to_pack);
2794	w_curs = NULL;
2795	buf = use_pack(p, &w_curs, e->in_pack_offset, &avail);
2796	used = unpack_object_header_buffer(buf, avail, &type, &size);
2797	if (used == 0)
2798	die(_("unable to parse object header of %s"),
2799	oid_to_hex(&e->idx.oid));
2800
2801	unuse_pack(&w_curs);
2802	packing_data_unlock(&to_pack);
2803	return size;
2804	}
2805
2806	static int try_delta(struct unpacked trg, struct unpacked src,
2807	unsigned max_depth, unsigned long *mem_usage)
2808	{
2809	struct object_entry *trg_entry = trg->entry;
2810	struct object_entry *src_entry = src->entry;
2811	unsigned long trg_size, src_size, delta_size, sizediff, max_size, sz;
2812	unsigned ref_depth;
2813	enum object_type type;
2814	void *delta_buf;
2815
2816	/* Don't bother doing diffs between different types */
2817	if (oe_type(trg_entry) != oe_type(src_entry))
2818	return -1;
2819
2820	/*
2821	* We do not bother to try a delta that we discarded on an
2822	* earlier try, but only when reusing delta data. Note that
2823	* src_entry that is marked as the preferred_base should always
2824	* be considered, as even if we produce a suboptimal delta against
2825	* it, we will still save the transfer cost, as we already know
2826	* the other side has it and we won't send src_entry at all.
2827	*/
2828	if (reuse_delta && IN_PACK(trg_entry) &&
2829	IN_PACK(trg_entry) == IN_PACK(src_entry) &&
2830	!src_entry->preferred_base &&
2831	trg_entry->in_pack_type != OBJ_REF_DELTA &&
2832	trg_entry->in_pack_type != OBJ_OFS_DELTA)
2833	return 0;
2834
2835	/* Let's not bust the allowed depth. */
2836	if (src->depth >= max_depth)
2837	return 0;
2838
2839	/* Now some size filtering heuristics. */
2840	trg_size = SIZE(trg_entry);
2841	if (!DELTA(trg_entry)) {
2842	max_size = trg_size/2 - the_hash_algo->rawsz;
2843	ref_depth = 1;
2844	} else {
2845	max_size = DELTA_SIZE(trg_entry);
2846	ref_depth = trg->depth;
2847	}
2848	max_size = (uint64_t)max_size * (max_depth - src->depth) /
2849	(max_depth - ref_depth + 1);
2850	if (max_size == 0)
2851	return 0;
2852	src_size = SIZE(src_entry);
2853	sizediff = src_size < trg_size ? trg_size - src_size : 0;
2854	if (sizediff >= max_size)
2855	return 0;
2856	if (trg_size < src_size / 32)
2857	return 0;
2858
2859	if (!in_same_island(&trg->entry->idx.oid, &src->entry->idx.oid))
2860	return 0;
2861
2862	/* Load data if not already done */
2863	if (!trg->data) {
2864	size_t sz_st = 0;
2865	packing_data_lock(&to_pack);
2866	trg->data = odb_read_object(the_repository->objects,
2867	&trg_entry->idx.oid, &type,
2868	&sz_st);
2869	sz = cast_size_t_to_ulong(sz_st);
2870	packing_data_unlock(&to_pack);
2871	if (!trg->data)
2872	die(_("object %s cannot be read"),
2873	oid_to_hex(&trg_entry->idx.oid));
2874	if (sz != trg_size)
2875	die(_("object %s inconsistent object length (%"PRIuMAX" vs %"PRIuMAX")"),
2876	oid_to_hex(&trg_entry->idx.oid), (uintmax_t)sz,
2877	(uintmax_t)trg_size);
2878	*mem_usage += sz;
2879	}
2880	if (!src->data) {
2881	size_t sz_st = 0;
2882	packing_data_lock(&to_pack);
2883	src->data = odb_read_object(the_repository->objects,
2884	&src_entry->idx.oid, &type,
2885	&sz_st);
2886	sz = cast_size_t_to_ulong(sz_st);
2887	packing_data_unlock(&to_pack);
2888	if (!src->data) {
2889	if (src_entry->preferred_base) {
2890	static int warned = 0;
2891	if (!warned++)
2892	warning(_("object %s cannot be read"),
2893	oid_to_hex(&src_entry->idx.oid));
2894	/*
2895	* Those objects are not included in the
2896	* resulting pack. Be resilient and ignore
2897	* them if they can't be read, in case the
2898	* pack could be created nevertheless.
2899	*/
2900	return 0;
2901	}
2902	die(_("object %s cannot be read"),
2903	oid_to_hex(&src_entry->idx.oid));
2904	}
2905	if (sz != src_size)
2906	die(_("object %s inconsistent object length (%"PRIuMAX" vs %"PRIuMAX")"),
2907	oid_to_hex(&src_entry->idx.oid), (uintmax_t)sz,
2908	(uintmax_t)src_size);
2909	*mem_usage += sz;
2910	}
2911	if (!src->index) {
2912	src->index = create_delta_index(src->data, src_size);
2913	if (!src->index) {
2914	static int warned = 0;
2915	if (!warned++)
2916	warning(_("suboptimal pack - out of memory"));
2917	return 0;
2918	}
2919	*mem_usage += sizeof_delta_index(src->index);
2920	}
2921
2922	delta_buf = create_delta(src->index, trg->data, trg_size, &delta_size, max_size);
2923	if (!delta_buf)
2924	return 0;
2925
2926	if (DELTA(trg_entry)) {
2927	/* Prefer only shallower same-sized deltas. */
2928	if (delta_size == DELTA_SIZE(trg_entry) &&
2929	src->depth + 1 >= trg->depth) {
2930	free(delta_buf);
2931	return 0;
2932	}
2933	}
2934
2935	/*
2936	* Handle memory allocation outside of the cache
2937	* accounting lock. Compiler will optimize the strangeness
2938	* away when NO_PTHREADS is defined.
2939	*/
2940	free(trg_entry->delta_data);
2941	cache_lock();
2942	if (trg_entry->delta_data) {
2943	delta_cache_size -= DELTA_SIZE(trg_entry);
2944	trg_entry->delta_data = NULL;
2945	}
2946	if (delta_cacheable(src_size, trg_size, delta_size)) {
2947	delta_cache_size += delta_size;
2948	cache_unlock();
2949	trg_entry->delta_data = xrealloc(delta_buf, delta_size);
2950	} else {
2951	cache_unlock();
2952	free(delta_buf);
2953	}
2954
2955	SET_DELTA(trg_entry, src_entry);
2956	SET_DELTA_SIZE(trg_entry, delta_size);
2957	trg->depth = src->depth + 1;
2958
2959	return 1;
2960	}
2961
2962	static unsigned int check_delta_limit(struct object_entry *me, unsigned int n)
2963	{
2964	struct object_entry *child = DELTA_CHILD(me);
2965	unsigned int m = n;
2966	while (child) {
2967	const unsigned int c = check_delta_limit(child, n + 1);
2968	if (m < c)
2969	m = c;
2970	child = DELTA_SIBLING(child);
2971	}
2972	return m;
2973	}
2974
2975	static unsigned long free_unpacked(struct unpacked *n)
2976	{
2977	unsigned long freed_mem = sizeof_delta_index(n->index);
2978	free_delta_index(n->index);
2979	n->index = NULL;
2980	if (n->data) {
2981	freed_mem += SIZE(n->entry);
2982	FREE_AND_NULL(n->data);
2983	}
2984	n->entry = NULL;
2985	n->depth = 0;
2986	return freed_mem;
2987	}
2988
2989	static void find_deltas(struct object_entry *list, unsigned list_size,
2990	int window, int depth, unsigned *processed)
2991	{
2992	uint32_t i, idx = 0, count = 0;
2993	struct unpacked *array;
2994	unsigned long mem_usage = 0;
2995
2996	CALLOC_ARRAY(array, window);
2997
2998	for (;;) {
2999	struct object_entry *entry;
3000	struct unpacked *n = array + idx;
3001	int j, max_depth, best_base = -1;
3002
3003	progress_lock();
3004	if (!*list_size) {
3005	progress_unlock();
3006	break;
3007	}
3008	entry = *list++;
3009	(*list_size)--;
3010	if (!entry->preferred_base) {
3011	(*processed)++;
3012	display_progress(progress_state, *processed);
3013	}
3014	progress_unlock();
3015
3016	mem_usage -= free_unpacked(n);
3017	n->entry = entry;
3018
3019	while (window_memory_limit &&
3020	mem_usage > window_memory_limit &&
3021	count > 1) {
3022	const uint32_t tail = (idx + window - count) % window;
3023	mem_usage -= free_unpacked(array + tail);
3024	count--;
3025	}
3026
3027	/* We do not compute delta to create objects we are not
3028	* going to pack.
3029	*/
3030	if (entry->preferred_base)
3031	goto next;
3032
3033	/*
3034	* If the current object is at pack edge, take the depth the
3035	* objects that depend on the current object into account
3036	* otherwise they would become too deep.
3037	*/
3038	max_depth = depth;
3039	if (DELTA_CHILD(entry)) {
3040	max_depth -= check_delta_limit(entry, 0);
3041	if (max_depth <= 0)
3042	goto next;
3043	}
3044
3045	j = window;
3046	while (--j > 0) {
3047	int ret;
3048	uint32_t other_idx = idx + j;
3049	struct unpacked *m;
3050	if (other_idx >= window)
3051	other_idx -= window;
3052	m = array + other_idx;
3053	if (!m->entry)
3054	break;
3055	ret = try_delta(n, m, max_depth, &mem_usage);
3056	if (ret < 0)
3057	break;
3058	else if (ret > 0)
3059	best_base = other_idx;
3060	}
3061
3062	/*
3063	* If we decided to cache the delta data, then it is best
3064	* to compress it right away. First because we have to do
3065	* it anyway, and doing it here while we're threaded will
3066	* save a lot of time in the non threaded write phase,
3067	* as well as allow for caching more deltas within
3068	* the same cache size limit.
3069	* ...
3070	* But only if not writing to stdout, since in that case
3071	* the network is most likely throttling writes anyway,
3072	* and therefore it is best to go to the write phase ASAP
3073	* instead, as we can afford spending more time compressing
3074	* between writes at that moment.
3075	*/
3076	if (entry->delta_data && !pack_to_stdout) {
3077	unsigned long size;
3078
3079	size = do_compress(&entry->delta_data, DELTA_SIZE(entry));
3080	if (size < (1U << OE_Z_DELTA_BITS)) {
3081	entry->z_delta_size = size;
3082	cache_lock();
3083	delta_cache_size -= DELTA_SIZE(entry);
3084	delta_cache_size += entry->z_delta_size;
3085	cache_unlock();
3086	} else {
3087	FREE_AND_NULL(entry->delta_data);
3088	entry->z_delta_size = 0;
3089	}
3090	}
3091
3092	/* if we made n a delta, and if n is already at max
3093	* depth, leaving it in the window is pointless. we
3094	* should evict it first.
3095	*/
3096	if (DELTA(entry) && max_depth <= n->depth)
3097	continue;
3098
3099	/*
3100	* Move the best delta base up in the window, after the
3101	* currently deltified object, to keep it longer. It will
3102	* be the first base object to be attempted next.
3103	*/
3104	if (DELTA(entry)) {
3105	struct unpacked swap = array[best_base];
3106	int dist = (window + idx - best_base) % window;
3107	int dst = best_base;
3108	while (dist--) {
3109	int src = (dst + 1) % window;
3110	array[dst] = array[src];
3111	dst = src;
3112	}
3113	array[dst] = swap;
3114	}
3115
3116	next:
3117	idx++;
3118	if (count + 1 < window)
3119	count++;
3120	if (idx >= window)
3121	idx = 0;
3122	}
3123
3124	for (i = 0; i < window; ++i) {
3125	free_delta_index(array[i].index);
3126	free(array[i].data);
3127	}
3128	free(array);
3129	}
3130
3131	/*
3132	* The main object list is split into smaller lists, each is handed to
3133	* one worker.
3134	*
3135	* The main thread waits on the condition that (at least) one of the workers
3136	* has stopped working (which is indicated in the .working member of
3137	* struct thread_params).
3138	*
3139	* When a work thread has completed its work, it sets .working to 0 and
3140	* signals the main thread and waits on the condition that .data_ready
3141	* becomes 1.
3142	*
3143	* The main thread steals half of the work from the worker that has
3144	* most work left to hand it to the idle worker.
3145	*/
3146
3147	struct thread_params {
3148	pthread_t thread;
3149	struct object_entry **list;
3150	struct packing_region *regions;
3151	unsigned list_size;
3152	unsigned remaining;
3153	int window;
3154	int depth;
3155	int working;
3156	int data_ready;
3157	pthread_mutex_t mutex;
3158	pthread_cond_t cond;
3159	unsigned *processed;
3160	};
3161
3162	static pthread_cond_t progress_cond;
3163
3164	/*
3165	* Mutex and conditional variable can't be statically-initialized on Windows.
3166	*/
3167	static void init_threaded_search(void)
3168	{
3169	pthread_mutex_init(&cache_mutex, NULL);
3170	pthread_mutex_init(&progress_mutex, NULL);
3171	pthread_cond_init(&progress_cond, NULL);
3172	}
3173
3174	static void cleanup_threaded_search(void)
3175	{
3176	pthread_cond_destroy(&progress_cond);
3177	pthread_mutex_destroy(&cache_mutex);
3178	pthread_mutex_destroy(&progress_mutex);
3179	}
3180
3181	static void threaded_find_deltas(void arg)
3182	{
3183	struct thread_params *me = arg;
3184
3185	progress_lock();
3186	while (me->remaining) {
3187	progress_unlock();
3188
3189	find_deltas(me->list, &me->remaining,
3190	me->window, me->depth, me->processed);
3191
3192	progress_lock();
3193	me->working = 0;
3194	pthread_cond_signal(&progress_cond);
3195	progress_unlock();
3196
3197	/*
3198	* We must not set ->data_ready before we wait on the
3199	* condition because the main thread may have set it to 1
3200	* before we get here. In order to be sure that new
3201	* work is available if we see 1 in ->data_ready, it
3202	* was initialized to 0 before this thread was spawned
3203	* and we reset it to 0 right away.
3204	*/
3205	pthread_mutex_lock(&me->mutex);
3206	while (!me->data_ready)
3207	pthread_cond_wait(&me->cond, &me->mutex);
3208	me->data_ready = 0;
3209	pthread_mutex_unlock(&me->mutex);
3210
3211	progress_lock();
3212	}
3213	progress_unlock();
3214	/* leave ->working 1 so that this doesn't get more work assigned */
3215	return NULL;
3216	}
3217
3218	static void ll_find_deltas(struct object_entry **list, unsigned list_size,
3219	int window, int depth, unsigned *processed)
3220	{
3221	struct thread_params *p;
3222	int i, ret, active_threads = 0;
3223
3224	init_threaded_search();
3225
3226	if (delta_search_threads <= 1) {
3227	find_deltas(list, &list_size, window, depth, processed);
3228	cleanup_threaded_search();
3229	return;
3230	}
3231	if (progress > pack_to_stdout)
3232	fprintf_ln(stderr, _("Delta compression using up to %d threads"),
3233	delta_search_threads);
3234	CALLOC_ARRAY(p, delta_search_threads);
3235
3236	/* Partition the work amongst work threads. */
3237	for (i = 0; i < delta_search_threads; i++) {
3238	unsigned sub_size = list_size / (delta_search_threads - i);
3239
3240	/* don't use too small segments or no deltas will be found */
3241	if (sub_size < 2*window && i+1 < delta_search_threads)
3242	sub_size = 0;
3243
3244	p[i].window = window;
3245	p[i].depth = depth;
3246	p[i].processed = processed;
3247	p[i].working = 1;
3248	p[i].data_ready = 0;
3249
3250	/* try to split chunks on "path" boundaries */
3251	while (sub_size && sub_size < list_size &&
3252	list[sub_size]->hash &&
3253	list[sub_size]->hash == list[sub_size-1]->hash)
3254	sub_size++;
3255
3256	p[i].list = list;
3257	p[i].list_size = sub_size;
3258	p[i].remaining = sub_size;
3259
3260	list += sub_size;
3261	list_size -= sub_size;
3262	}
3263
3264	/* Start work threads. */
3265	for (i = 0; i < delta_search_threads; i++) {
3266	if (!p[i].list_size)
3267	continue;
3268	pthread_mutex_init(&p[i].mutex, NULL);
3269	pthread_cond_init(&p[i].cond, NULL);
3270	ret = pthread_create(&p[i].thread, NULL,
3271	threaded_find_deltas, &p[i]);
3272	if (ret)
3273	die(_("unable to create thread: %s"), strerror(ret));
3274	active_threads++;
3275	}
3276
3277	/*
3278	* Now let's wait for work completion. Each time a thread is done
3279	* with its work, we steal half of the remaining work from the
3280	* thread with the largest number of unprocessed objects and give
3281	* it to that newly idle thread. This ensure good load balancing
3282	* until the remaining object list segments are simply too short
3283	* to be worth splitting anymore.
3284	*/
3285	while (active_threads) {
3286	struct thread_params *target = NULL;
3287	struct thread_params *victim = NULL;
3288	unsigned sub_size = 0;
3289
3290	progress_lock();
3291	for (;;) {
3292	for (i = 0; !target && i < delta_search_threads; i++)
3293	if (!p[i].working)
3294	target = &p[i];
3295	if (target)
3296	break;
3297	pthread_cond_wait(&progress_cond, &progress_mutex);
3298	}
3299
3300	for (i = 0; i < delta_search_threads; i++)
3301	if (p[i].remaining > 2*window &&
3302	(!victim \|\| victim->remaining < p[i].remaining))
3303	victim = &p[i];
3304	if (victim) {
3305	sub_size = victim->remaining / 2;
3306	list = victim->list + victim->list_size - sub_size;
3307	while (sub_size && list[0]->hash &&
3308	list[0]->hash == list[-1]->hash) {
3309	list++;
3310	sub_size--;
3311	}
3312	if (!sub_size) {
3313	/*
3314	* It is possible for some "paths" to have
3315	* so many objects that no hash boundary
3316	* might be found. Let's just steal the
3317	* exact half in that case.
3318	*/
3319	sub_size = victim->remaining / 2;
3320	list -= sub_size;
3321	}
3322	target->list = list;
3323	victim->list_size -= sub_size;
3324	victim->remaining -= sub_size;
3325	}
3326	target->list_size = sub_size;
3327	target->remaining = sub_size;
3328	target->working = 1;
3329	progress_unlock();
3330
3331	pthread_mutex_lock(&target->mutex);
3332	target->data_ready = 1;
3333	pthread_cond_signal(&target->cond);
3334	pthread_mutex_unlock(&target->mutex);
3335
3336	if (!sub_size) {
3337	pthread_join(target->thread, NULL);
3338	pthread_cond_destroy(&target->cond);
3339	pthread_mutex_destroy(&target->mutex);
3340	active_threads--;
3341	}
3342	}
3343	cleanup_threaded_search();
3344	free(p);
3345	}
3346
3347	static int obj_is_packed(const struct object_id *oid)
3348	{
3349	return packlist_find(&to_pack, oid) \|\|
3350	(reuse_packfile_bitmap &&
3351	bitmap_walk_contains(bitmap_git, reuse_packfile_bitmap, oid));
3352	}
3353
3354	static void add_tag_chain(const struct object_id *oid)
3355	{
3356	struct tag *tag;
3357
3358	/*
3359	* We catch duplicates already in add_object_entry(), but we'd
3360	* prefer to do this extra check to avoid having to parse the
3361	* tag at all if we already know that it's being packed (e.g., if
3362	* it was included via bitmaps, we would not have parsed it
3363	* previously).
3364	*/
3365	if (obj_is_packed(oid))
3366	return;
3367
3368	tag = lookup_tag(the_repository, oid);
3369	while (1) {
3370	if (!tag \|\| parse_tag(the_repository, tag) \|\| !tag->tagged)
3371	die(_("unable to pack objects reachable from tag %s"),
3372	oid_to_hex(oid));
3373
3374	add_object_entry(&tag->object.oid, OBJ_TAG, NULL, 0);
3375
3376	if (tag->tagged->type != OBJ_TAG)
3377	return;
3378
3379	tag = (struct tag *)tag->tagged;
3380	}
3381	}
3382
3383	static int add_ref_tag(const struct reference ref, void cb_data UNUSED)
3384	{
3385	struct object_id peeled;
3386
3387	if (!reference_get_peeled_oid(the_repository, ref, &peeled) &&
3388	obj_is_packed(&peeled))
3389	add_tag_chain(ref->oid);
3390	return 0;
3391	}
3392
3393	static int should_attempt_deltas(struct object_entry *entry)
3394	{
3395	if (DELTA(entry))
3396	/* This happens if we decided to reuse existing
3397	* delta from a pack. "reuse_delta &&" is implied.
3398	*/
3399	return 0;
3400
3401	if (!entry->type_valid \|\|
3402	oe_size_less_than(&to_pack, entry, 50))
3403	return 0;
3404
3405	if (entry->no_try_delta)
3406	return 0;
3407
3408	if (!entry->preferred_base) {
3409	if (oe_type(entry) < 0)
3410	die(_("unable to get type of object %s"),
3411	oid_to_hex(&entry->idx.oid));
3412	} else if (oe_type(entry) < 0) {
3413	/*
3414	* This object is not found, but we
3415	* don't have to include it anyway.
3416	*/
3417	return 0;
3418	}
3419
3420	return 1;
3421	}
3422
3423	static void find_deltas_for_region(struct object_entry *list,
3424	struct packing_region *region,
3425	unsigned int *processed)
3426	{
3427	struct object_entry **delta_list;
3428	unsigned int delta_list_nr = 0;
3429
3430	ALLOC_ARRAY(delta_list, region->nr);
3431	for (size_t i = 0; i < region->nr; i++) {
3432	struct object_entry *entry = list + region->start + i;
3433	if (should_attempt_deltas(entry))
3434	delta_list[delta_list_nr++] = entry;
3435	}
3436
3437	QSORT(delta_list, delta_list_nr, type_size_sort);
3438	find_deltas(delta_list, &delta_list_nr, window, depth, processed);
3439	free(delta_list);
3440	}
3441
3442	static void find_deltas_by_region(struct object_entry *list,
3443	struct packing_region *regions,
3444	size_t start, size_t nr)
3445	{
3446	unsigned int processed = 0;
3447	size_t progress_nr;
3448
3449	if (!nr)
3450	return;
3451
3452	progress_nr = regions[nr - 1].start + regions[nr - 1].nr;
3453
3454	if (progress)
3455	progress_state = start_progress(the_repository,
3456	_("Compressing objects by path"),
3457	progress_nr);
3458
3459	while (nr--)
3460	find_deltas_for_region(list,
3461	&regions[start++],
3462	&processed);
3463
3464	display_progress(progress_state, progress_nr);
3465	stop_progress(&progress_state);
3466	}
3467
3468	static void threaded_find_deltas_by_path(void arg)
3469	{
3470	struct thread_params *me = arg;
3471
3472	progress_lock();
3473	while (me->remaining) {
3474	while (me->remaining) {
3475	progress_unlock();
3476	find_deltas_for_region(to_pack.objects,
3477	me->regions,
3478	me->processed);
3479	progress_lock();
3480	me->remaining--;
3481	me->regions++;
3482	}
3483
3484	me->working = 0;
3485	pthread_cond_signal(&progress_cond);
3486	progress_unlock();
3487
3488	/*
3489	* We must not set ->data_ready before we wait on the
3490	* condition because the main thread may have set it to 1
3491	* before we get here. In order to be sure that new
3492	* work is available if we see 1 in ->data_ready, it
3493	* was initialized to 0 before this thread was spawned
3494	* and we reset it to 0 right away.
3495	*/
3496	pthread_mutex_lock(&me->mutex);
3497	while (!me->data_ready)
3498	pthread_cond_wait(&me->cond, &me->mutex);
3499	me->data_ready = 0;
3500	pthread_mutex_unlock(&me->mutex);
3501
3502	progress_lock();
3503	}
3504	progress_unlock();
3505	/* leave ->working 1 so that this doesn't get more work assigned */
3506	return NULL;
3507	}
3508
3509	static void ll_find_deltas_by_region(struct object_entry *list,
3510	struct packing_region *regions,
3511	uint32_t start, uint32_t nr)
3512	{
3513	struct thread_params *p;
3514	int i, ret, active_threads = 0;
3515	unsigned int processed = 0;
3516	uint32_t progress_nr;
3517	init_threaded_search();
3518
3519	if (!nr)
3520	return;
3521
3522	progress_nr = regions[nr - 1].start + regions[nr - 1].nr;
3523	if (delta_search_threads <= 1) {
3524	find_deltas_by_region(list, regions, start, nr);
3525	cleanup_threaded_search();
3526	return;
3527	}
3528
3529	if (progress > pack_to_stdout)
3530	fprintf_ln(stderr,
3531	Q_("Path-based delta compression using up to %d thread",
3532	"Path-based delta compression using up to %d threads",
3533	delta_search_threads),
3534	delta_search_threads);
3535	CALLOC_ARRAY(p, delta_search_threads);
3536
3537	if (progress)
3538	progress_state = start_progress(the_repository,
3539	_("Compressing objects by path"),
3540	progress_nr);
3541	/* Partition the work amongst work threads. */
3542	for (i = 0; i < delta_search_threads; i++) {
3543	unsigned sub_size = nr / (delta_search_threads - i);
3544
3545	p[i].window = window;
3546	p[i].depth = depth;
3547	p[i].processed = &processed;
3548	p[i].working = 1;
3549	p[i].data_ready = 0;
3550
3551	p[i].regions = regions;
3552	p[i].list_size = sub_size;
3553	p[i].remaining = sub_size;
3554
3555	regions += sub_size;
3556	nr -= sub_size;
3557	}
3558
3559	/* Start work threads. */
3560	for (i = 0; i < delta_search_threads; i++) {
3561	if (!p[i].list_size)
3562	continue;
3563	pthread_mutex_init(&p[i].mutex, NULL);
3564	pthread_cond_init(&p[i].cond, NULL);
3565	ret = pthread_create(&p[i].thread, NULL,
3566	threaded_find_deltas_by_path, &p[i]);
3567	if (ret)
3568	die(_("unable to create thread: %s"), strerror(ret));
3569	active_threads++;
3570	}
3571
3572	/*
3573	* Now let's wait for work completion. Each time a thread is done
3574	* with its work, we steal half of the remaining work from the
3575	* thread with the largest number of unprocessed objects and give
3576	* it to that newly idle thread. This ensure good load balancing
3577	* until the remaining object list segments are simply too short
3578	* to be worth splitting anymore.
3579	*/
3580	while (active_threads) {
3581	struct thread_params *target = NULL;
3582	struct thread_params *victim = NULL;
3583	unsigned sub_size = 0;
3584
3585	progress_lock();
3586	for (;;) {
3587	for (i = 0; !target && i < delta_search_threads; i++)
3588	if (!p[i].working)
3589	target = &p[i];
3590	if (target)
3591	break;
3592	pthread_cond_wait(&progress_cond, &progress_mutex);
3593	}
3594
3595	for (i = 0; i < delta_search_threads; i++)
3596	if (p[i].remaining > 2*window &&
3597	(!victim \|\| victim->remaining < p[i].remaining))
3598	victim = &p[i];
3599	if (victim) {
3600	sub_size = victim->remaining / 2;
3601	target->regions = victim->regions + victim->remaining - sub_size;
3602	victim->list_size -= sub_size;
3603	victim->remaining -= sub_size;
3604	}
3605	target->list_size = sub_size;
3606	target->remaining = sub_size;
3607	target->working = 1;
3608	progress_unlock();
3609
3610	pthread_mutex_lock(&target->mutex);
3611	target->data_ready = 1;
3612	pthread_cond_signal(&target->cond);
3613	pthread_mutex_unlock(&target->mutex);
3614
3615	if (!sub_size) {
3616	pthread_join(target->thread, NULL);
3617	pthread_cond_destroy(&target->cond);
3618	pthread_mutex_destroy(&target->mutex);
3619	active_threads--;
3620	}
3621	}
3622	cleanup_threaded_search();
3623	free(p);
3624
3625	display_progress(progress_state, progress_nr);
3626	stop_progress(&progress_state);
3627	}
3628
3629	static void prepare_pack(int window, int depth)
3630	{
3631	struct object_entry **delta_list;
3632	uint32_t i, nr_deltas;
3633	unsigned n;
3634
3635	if (use_delta_islands)
3636	resolve_tree_islands(the_repository, progress, &to_pack);
3637
3638	get_object_details();
3639
3640	/*
3641	* If we're locally repacking then we need to be doubly careful
3642	* from now on in order to make sure no stealth corruption gets
3643	* propagated to the new pack. Clients receiving streamed packs
3644	* should validate everything they get anyway so no need to incur
3645	* the additional cost here in that case.
3646	*/
3647	if (!pack_to_stdout)
3648	do_check_packed_object_crc = 1;
3649
3650	if (!to_pack.nr_objects \|\| !window \|\| !depth)
3651	return;
3652
3653	if (path_walk)
3654	ll_find_deltas_by_region(to_pack.objects, to_pack.regions,
3655	0, to_pack.nr_regions);
3656
3657	ALLOC_ARRAY(delta_list, to_pack.nr_objects);
3658	nr_deltas = n = 0;
3659
3660	for (i = 0; i < to_pack.nr_objects; i++) {
3661	struct object_entry *entry = to_pack.objects + i;
3662
3663	if (!should_attempt_deltas(entry))
3664	continue;
3665
3666	if (!entry->preferred_base)
3667	nr_deltas++;
3668
3669	delta_list[n++] = entry;
3670	}
3671
3672	if (nr_deltas && n > 1) {
3673	unsigned nr_done = 0;
3674
3675	if (progress)
3676	progress_state = start_progress(the_repository,
3677	_("Compressing objects"),
3678	nr_deltas);
3679	QSORT(delta_list, n, type_size_sort);
3680	ll_find_deltas(delta_list, n, window+1, depth, &nr_done);
3681	stop_progress(&progress_state);
3682	if (nr_done != nr_deltas)
3683	die(_("inconsistency with delta count"));
3684	}
3685	free(delta_list);
3686	}
3687
3688	static int git_pack_config(const char k, const char v,
3689	const struct config_context ctx, void cb)
3690	{
3691	if (!strcmp(k, "pack.window")) {
3692	window = git_config_int(k, v, ctx->kvi);
3693	return 0;
3694	}
3695	if (!strcmp(k, "pack.windowmemory")) {
3696	window_memory_limit = git_config_ulong(k, v, ctx->kvi);
3697	return 0;
3698	}
3699	if (!strcmp(k, "pack.depth")) {
3700	depth = git_config_int(k, v, ctx->kvi);
3701	return 0;
3702	}
3703	if (!strcmp(k, "pack.deltacachesize")) {
3704	max_delta_cache_size = git_config_int(k, v, ctx->kvi);
3705	return 0;
3706	}
3707	if (!strcmp(k, "pack.deltacachelimit")) {
3708	cache_max_small_delta_size = git_config_int(k, v, ctx->kvi);
3709	return 0;
3710	}
3711	if (!strcmp(k, "pack.writebitmaphashcache")) {
3712	if (git_config_bool(k, v))
3713	write_bitmap_options \|= BITMAP_OPT_HASH_CACHE;
3714	else
3715	write_bitmap_options &= ~BITMAP_OPT_HASH_CACHE;
3716	}
3717
3718	if (!strcmp(k, "pack.writebitmaplookuptable")) {
3719	if (git_config_bool(k, v))
3720	write_bitmap_options \|= BITMAP_OPT_LOOKUP_TABLE;
3721	else
3722	write_bitmap_options &= ~BITMAP_OPT_LOOKUP_TABLE;
3723	}
3724
3725	if (!strcmp(k, "pack.usebitmaps")) {
3726	use_bitmap_index_default = git_config_bool(k, v);
3727	return 0;
3728	}
3729	if (!strcmp(k, "pack.allowpackreuse")) {
3730	int res = git_parse_maybe_bool_text(v);
3731	if (res < 0) {
3732	if (!strcasecmp(v, "single"))
3733	allow_pack_reuse = SINGLE_PACK_REUSE;
3734	else if (!strcasecmp(v, "multi"))
3735	allow_pack_reuse = MULTI_PACK_REUSE;
3736	else
3737	die(_("invalid pack.allowPackReuse value: '%s'"), v);
3738	} else if (res) {
3739	allow_pack_reuse = SINGLE_PACK_REUSE;
3740	} else {
3741	allow_pack_reuse = NO_PACK_REUSE;
3742	}
3743	return 0;
3744	}
3745	if (!strcmp(k, "pack.threads")) {
3746	delta_search_threads = git_config_int(k, v, ctx->kvi);
3747	if (delta_search_threads < 0)
3748	die(_("invalid number of threads specified (%d)"),
3749	delta_search_threads);
3750	if (!HAVE_THREADS && delta_search_threads != 1) {
3751	warning(_("no threads support, ignoring %s"), k);
3752	delta_search_threads = 0;
3753	}
3754	return 0;
3755	}
3756	if (!strcmp(k, "pack.indexversion")) {
3757	pack_idx_opts.version = git_config_int(k, v, ctx->kvi);
3758	if (pack_idx_opts.version > 2)
3759	die(_("bad pack.indexVersion=%"PRIu32),
3760	pack_idx_opts.version);
3761	return 0;
3762	}
3763	if (!strcmp(k, "pack.writereverseindex")) {
3764	if (git_config_bool(k, v))
3765	pack_idx_opts.flags \|= WRITE_REV;
3766	else
3767	pack_idx_opts.flags &= ~WRITE_REV;
3768	return 0;
3769	}
3770	if (!strcmp(k, "uploadpack.blobpackfileuri")) {
3771	struct configured_exclusion *ex;
3772	const char oid_end, pack_end;
3773	/*
3774	* Stores the pack hash. This is not a true object ID, but is
3775	* of the same form.
3776	*/
3777	struct object_id pack_hash;
3778
3779	if (!v)
3780	return config_error_nonbool(k);
3781
3782	ex = xmalloc(sizeof(*ex));
3783	if (parse_oid_hex(v, &ex->e.oid, &oid_end) \|\|
3784	*oid_end != ' ' \|\|
3785	parse_oid_hex(oid_end + 1, &pack_hash, &pack_end) \|\|
3786	*pack_end != ' ')
3787	die(_("value of uploadpack.blobpackfileuri must be "
3788	"of the form '<object-hash> <pack-hash> <uri>' (got '%s')"), v);
3789	if (oidmap_get(&configured_exclusions, &ex->e.oid))
3790	die(_("object already configured in another "
3791	"uploadpack.blobpackfileuri (got '%s')"), v);
3792	ex->pack_hash_hex = xcalloc(1, pack_end - oid_end);
3793	memcpy(ex->pack_hash_hex, oid_end + 1, pack_end - oid_end - 1);
3794	ex->uri = xstrdup(pack_end + 1);
3795	oidmap_put(&configured_exclusions, ex);
3796	}
3797	return git_default_config(k, v, ctx, cb);
3798	}
3799
3800	/* Counters for trace2 output when in --stdin-packs mode. */
3801	static int stdin_packs_found_nr;
3802	static int stdin_packs_hints_nr;
3803
3804	static int add_object_entry_from_pack(const struct object_id *oid,
3805	struct packed_git *p,
3806	uint32_t pos,
3807	void *_data)
3808	{
3809	off_t ofs;
3810	struct object_info oi = OBJECT_INFO_INIT;
3811	enum object_type type = OBJ_NONE;
3812
3813	display_progress(progress_state, ++nr_seen);
3814
3815	if (have_duplicate_entry(oid, 0))
3816	return 0;
3817
3818	stdin_packs_found_nr++;
3819
3820	ofs = nth_packed_object_offset(p, pos);
3821
3822	oi.typep = &type;
3823	if (packed_object_info(NULL, p, ofs, &oi) < 0) {
3824	die(_("could not get type of object %s in pack %s"),
3825	oid_to_hex(oid), p->pack_name);
3826	} else if (type == OBJ_COMMIT) {
3827	struct rev_info *revs = _data;
3828	/*
3829	* commits in included packs are used as starting points
3830	* for the subsequent revision walk
3831	*
3832	* Note that we do want to walk through commits that are
3833	* present in excluded-open ('!') packs to pick up any
3834	* objects reachable from them not present in the
3835	* excluded-closed ('^') packs.
3836	*
3837	* However, we'll only add those objects to the packing
3838	* list after checking `want_object_in_pack()` below.
3839	*/
3840	add_pending_oid(revs, NULL, oid, 0);
3841	}
3842
3843	if (!want_object_in_pack(oid, 0, &p, &ofs))
3844	return 0;
3845
3846	create_object_entry(oid, type, 0, 0, 0, p, ofs);
3847
3848	return 0;
3849	}
3850
3851	static void show_object_pack_hint(struct object object, const char name,
3852	void *data)
3853	{
3854	enum stdin_packs_mode mode = (enum stdin_packs_mode )data;
3855	if (mode == STDIN_PACKS_MODE_FOLLOW) {
3856	if (object->type == OBJ_BLOB &&
3857	!odb_has_object(the_repository->objects, &object->oid, 0))
3858	return;
3859	add_object_entry(&object->oid, object->type, name, 0);
3860	} else {
3861	struct object_entry *oe = packlist_find(&to_pack, &object->oid);
3862	if (!oe)
3863	return;
3864
3865	/*
3866	* Our 'to_pack' list was constructed by iterating all
3867	* objects packed in included packs, and so doesn't have
3868	* a non-zero hash field that you would typically pick
3869	* up during a reachability traversal.
3870	*
3871	* Make a best-effort attempt to fill in the ->hash and
3872	* ->no_try_delta fields here in order to perhaps
3873	* improve the delta selection process.
3874	*/
3875	oe->hash = pack_name_hash_fn(name);
3876	oe->no_try_delta = name && no_try_delta(name);
3877
3878	stdin_packs_hints_nr++;
3879	}
3880	}
3881
3882	static void show_commit_pack_hint(struct commit commit, void data)
3883	{
3884	enum stdin_packs_mode mode = (enum stdin_packs_mode )data;
3885
3886	if (mode == STDIN_PACKS_MODE_FOLLOW) {
3887	show_object_pack_hint((struct object *)commit, "", data);
3888	return;
3889	}
3890
3891	/* nothing to do; commits don't have a namehash */
3892
3893	}
3894
3895	/*
3896	* stdin_pack_info_kind specifies how a pack specified over stdin
3897	* should be treated when pack-objects is invoked with --stdin-packs.
3898	*
3899	* - STDIN_PACK_INCLUDE: objects in any packs with this flag bit set
3900	* should be included in the output pack, unless they appear in an
3901	* excluded pack.
3902	*
3903	* - STDIN_PACK_EXCLUDE_CLOSED: objects in any packs with this flag
3904	* bit set should be excluded from the output pack.
3905	*
3906	* - STDIN_PACK_EXCLUDE_OPEN: objects in any packs with this flag
3907	* bit set should be excluded from the output pack, but are not
3908	* guaranteed to be closed under reachability.
3909	*
3910	* Objects in packs whose 'kind' bits include STDIN_PACK_INCLUDE or
3911	* STDIN_PACK_EXCLUDE_OPEN are used as traversal tips when invoked
3912	* with --stdin-packs=follow.
3913	*/
3914	enum stdin_pack_info_kind {
3915	STDIN_PACK_INCLUDE = (1<<0),
3916	STDIN_PACK_EXCLUDE_CLOSED = (1<<1),
3917	STDIN_PACK_EXCLUDE_OPEN = (1<<2),
3918	};
3919
3920	struct stdin_pack_info {
3921	struct packed_git *p;
3922	enum stdin_pack_info_kind kind;
3923	};
3924
3925	static int pack_mtime_cmp(const void _a, const void _b)
3926	{
3927	struct stdin_pack_info a = ((const struct string_list_item)_a)->util;
3928	struct stdin_pack_info b = ((const struct string_list_item)_b)->util;
3929
3930	/*
3931	* order packs by descending mtime so that objects are laid out
3932	* roughly as newest-to-oldest
3933	*/
3934	if (a->p->mtime < b->p->mtime)
3935	return 1;
3936	else if (b->p->mtime < a->p->mtime)
3937	return -1;
3938	else
3939	return 0;
3940	}
3941
3942	static int stdin_packs_include_check_obj(struct object obj, void data UNUSED)
3943	{
3944	return !has_object_kept_pack(to_pack.repo, &obj->oid,
3945	KEPT_PACK_IN_CORE);
3946	}
3947
3948	static int stdin_packs_include_check(struct commit commit, void data)
3949	{
3950	return stdin_packs_include_check_obj((struct object *)commit, data);
3951	}
3952
3953	static void stdin_packs_add_pack_entries(struct strmap *packs,
3954	struct rev_info *revs)
3955	{
3956	struct string_list keys = STRING_LIST_INIT_NODUP;
3957	struct string_list_item *item;
3958	struct hashmap_iter iter;
3959	struct strmap_entry *entry;
3960
3961	strmap_for_each_entry(packs, &iter, entry) {
3962	struct stdin_pack_info *info = entry->value;
3963	if (!info->p)
3964	die(_("could not find pack '%s'"), entry->key);
3965
3966	string_list_append(&keys, entry->key)->util = info;
3967	}
3968
3969	/*
3970	* Order packs by ascending mtime; use QSORT directly to access the
3971	* string_list_item's ->util pointer, which string_list_sort() does not
3972	* provide.
3973	*/
3974	QSORT(keys.items, keys.nr, pack_mtime_cmp);
3975
3976	for_each_string_list_item(item, &keys) {
3977	struct stdin_pack_info *info = item->util;
3978
3979	if (info->kind & STDIN_PACK_EXCLUDE_OPEN) {
3980	/*
3981	* When open-excluded packs ("!") are present, stop
3982	* the parent walk at closed-excluded ("^") packs.
3983	* Objects behind a "^" boundary are guaranteed to
3984	* have closure and should not be rescued.
3985	*/
3986	revs->include_check = stdin_packs_include_check;
3987	revs->include_check_obj = stdin_packs_include_check_obj;
3988	}
3989
3990	if ((info->kind & STDIN_PACK_INCLUDE) \|\|
3991	(info->kind & STDIN_PACK_EXCLUDE_OPEN))
3992	for_each_object_in_pack(info->p,
3993	add_object_entry_from_pack,
3994	revs,
3995	ODB_FOR_EACH_OBJECT_PACK_ORDER);
3996	}
3997
3998	string_list_clear(&keys, 0);
3999	}
4000
4001	static void stdin_packs_read_input(struct rev_info *revs,
4002	enum stdin_packs_mode mode)
4003	{
4004	struct strbuf buf = STRBUF_INIT;
4005	struct strmap packs = STRMAP_INIT;
4006	struct packed_git *p;
4007
4008	while (strbuf_getline(&buf, stdin) != EOF) {
4009	struct stdin_pack_info *info;
4010	enum stdin_pack_info_kind kind = STDIN_PACK_INCLUDE;
4011	const char *key = buf.buf;
4012
4013	if (!*key)
4014	continue;
4015	else if (*key == '^')
4016	kind = STDIN_PACK_EXCLUDE_CLOSED;
4017	else if (*key == '!' && mode == STDIN_PACKS_MODE_FOLLOW)
4018	kind = STDIN_PACK_EXCLUDE_OPEN;
4019
4020	if (kind != STDIN_PACK_INCLUDE)
4021	key++;
4022
4023	info = strmap_get(&packs, key);
4024	if (!info) {
4025	CALLOC_ARRAY(info, 1);
4026	strmap_put(&packs, key, info);
4027	}
4028
4029	info->kind \|= kind;
4030
4031	strbuf_reset(&buf);
4032	}
4033
4034	repo_for_each_pack(the_repository, p) {
4035	struct stdin_pack_info *info;
4036
4037	info = strmap_get(&packs, pack_basename(p));
4038	if (!info)
4039	continue;
4040
4041	if (info->kind & STDIN_PACK_INCLUDE) {
4042	if (exclude_promisor_objects && p->pack_promisor)
4043	die(_("packfile %s is a promisor but --exclude-promisor-objects was given"), p->pack_name);
4044
4045	/*
4046	* Arguments we got on stdin may not even be
4047	* packs. First check that to avoid segfaulting
4048	* later on in e.g. pack_mtime_cmp(), excluded
4049	* packs are handled below.
4050	*/
4051	if (!is_pack_valid(p))
4052	die(_("packfile %s cannot be accessed"), p->pack_name);
4053	}
4054
4055	if (info->kind & STDIN_PACK_EXCLUDE_CLOSED) {
4056	/*
4057	* Marking excluded packs as kept in-core so
4058	* that later calls to add_object_entry()
4059	* discards any objects that are also found in
4060	* excluded packs.
4061	*/
4062	p->pack_keep_in_core = 1;
4063	}
4064
4065	if (info->kind & STDIN_PACK_EXCLUDE_OPEN) {
4066	/*
4067	* Marking excluded open packs as kept in-core
4068	* (open) for the same reason as we marked
4069	* exclude closed packs as kept in-core.
4070	*
4071	* Use a separate flag here to ensure we don't
4072	* halt our traversal at these packs, since they
4073	* are not guaranteed to have closure.
4074	*
4075	*/
4076	p->pack_keep_in_core_open = 1;
4077	}
4078
4079	info->p = p;
4080	}
4081
4082	stdin_packs_add_pack_entries(&packs, revs);
4083
4084	strbuf_release(&buf);
4085	strmap_clear(&packs, 1);
4086	}
4087
4088	static void add_unreachable_loose_objects(struct rev_info *revs);
4089
4090	static void read_stdin_packs(enum stdin_packs_mode mode, int rev_list_unpacked)
4091	{
4092	int prev_fetch_if_missing = fetch_if_missing;
4093	struct rev_info revs;
4094
4095	/*
4096	* The revision walk may hit objects that are promised, only. As the
4097	* walk is best-effort though we don't want to perform backfill fetches
4098	* for them.
4099	*/
4100	fetch_if_missing = 0;
4101
4102	repo_init_revisions(the_repository, &revs, NULL);
4103	/*
4104	* Use a revision walk to fill in the namehash of objects in the include
4105	* packs. To save time, we'll avoid traversing through objects that are
4106	* in excluded packs.
4107	*
4108	* That may cause us to avoid populating all of the namehash fields of
4109	* all included objects, but our goal is best-effort, since this is only
4110	* an optimization during delta selection.
4111	*/
4112	revs.no_kept_objects = 1;
4113	revs.keep_pack_cache_flags \|= KEPT_PACK_IN_CORE;
4114	revs.blob_objects = 1;
4115	revs.tree_objects = 1;
4116	revs.tag_objects = 1;
4117	revs.ignore_missing_links = 1;
4118	revs.exclude_promisor_objects = exclude_promisor_objects;
4119
4120	/* avoids adding objects in excluded packs */
4121	ignore_packed_keep_in_core = 1;
4122	if (mode == STDIN_PACKS_MODE_FOLLOW) {
4123	/*
4124	* In '--stdin-packs=follow' mode, additionally ignore
4125	* objects in excluded-open packs to prevent them from
4126	* appearing in the resulting pack.
4127	*/
4128	ignore_packed_keep_in_core_open = 1;
4129	}
4130	stdin_packs_read_input(&revs, mode);
4131	if (rev_list_unpacked)
4132	add_unreachable_loose_objects(&revs);
4133
4134	if (prepare_revision_walk(&revs))
4135	die(_("revision walk setup failed"));
4136	traverse_commit_list(&revs,
4137	show_commit_pack_hint,
4138	show_object_pack_hint,
4139	&mode);
4140
4141	release_revisions(&revs);
4142
4143	trace2_data_intmax("pack-objects", the_repository, "stdin_packs_found",
4144	stdin_packs_found_nr);
4145	trace2_data_intmax("pack-objects", the_repository, "stdin_packs_hints",
4146	stdin_packs_hints_nr);
4147
4148	fetch_if_missing = prev_fetch_if_missing;
4149	}
4150
4151	static void add_cruft_object_entry(const struct object_id *oid, enum object_type type,
4152	struct packed_git *pack, off_t offset,
4153	const char *name, uint32_t mtime)
4154	{
4155	struct object_entry *entry;
4156
4157	display_progress(progress_state, ++nr_seen);
4158
4159	entry = packlist_find(&to_pack, oid);
4160	if (entry) {
4161	if (name) {
4162	entry->hash = pack_name_hash_fn(name);
4163	entry->no_try_delta = no_try_delta(name);
4164	}
4165	} else {
4166	if (!want_object_in_pack_mtime(oid, 0, &pack, &offset, mtime))
4167	return;
4168	if (!pack && type == OBJ_BLOB) {
4169	struct odb_source *source = the_repository->objects->sources;
4170	int found = 0;
4171
4172	for (; !found && source; source = source->next) {
4173	struct odb_source_files *files = odb_source_files_downcast(source);
4174	if (!odb_source_read_object_info(&files->loose->base, oid, NULL, 0))
4175	found = 1;
4176	}
4177
4178	/*
4179	* If a traversed tree has a missing blob then we want
4180	* to avoid adding that missing object to our pack.
4181	*
4182	* This only applies to missing blobs, not trees,
4183	* because the traversal needs to parse sub-trees but
4184	* not blobs.
4185	*
4186	* Note we only perform this check when we couldn't
4187	* already find the object in a pack, so we're really
4188	* limited to "ensure non-tip blobs which don't exist in
4189	* packs do exist via loose objects". Confused?
4190	*/
4191	if (!found)
4192	return;
4193	}
4194
4195	entry = create_object_entry(oid, type, pack_name_hash_fn(name),
4196	0, name && no_try_delta(name),
4197	pack, offset);
4198	}
4199
4200	if (mtime > oe_cruft_mtime(&to_pack, entry))
4201	oe_set_cruft_mtime(&to_pack, entry, mtime);
4202	return;
4203	}
4204
4205	static void show_cruft_object(struct object obj, const char name, void *data UNUSED)
4206	{
4207	/*
4208	* if we did not record it earlier, it's at least as old as our
4209	* expiration value. Rather than find it exactly, just use that
4210	* value. This may bump it forward from its real mtime, but it
4211	* will still be "too old" next time we run with the same
4212	* expiration.
4213	*
4214	* if obj does appear in the packing list, this call is a noop (or may
4215	* set the namehash).
4216	*/
4217	add_cruft_object_entry(&obj->oid, obj->type, NULL, 0, name, cruft_expiration);
4218	}
4219
4220	static void show_cruft_commit(struct commit commit, void data)
4221	{
4222	show_cruft_object((struct object*)commit, NULL, data);
4223	}
4224
4225	static int cruft_include_check_obj(struct object obj, void data UNUSED)
4226	{
4227	return !has_object_kept_pack(to_pack.repo, &obj->oid, KEPT_PACK_IN_CORE);
4228	}
4229
4230	static int cruft_include_check(struct commit commit, void data)
4231	{
4232	return cruft_include_check_obj((struct object*)commit, data);
4233	}
4234
4235	static void set_cruft_mtime(const struct object *object,
4236	struct packed_git *pack,
4237	off_t offset, time_t mtime)
4238	{
4239	add_cruft_object_entry(&object->oid, object->type, pack, offset, NULL,
4240	mtime);
4241	}
4242
4243	static void mark_pack_kept_in_core(struct string_list *packs, unsigned keep)
4244	{
4245	struct string_list_item *item = NULL;
4246	for_each_string_list_item(item, packs) {
4247	struct packed_git *p = item->util;
4248	if (!p)
4249	die(_("could not find pack '%s'"), item->string);
4250	if (p->is_cruft && keep)
4251	ignore_packed_keep_in_core_has_cruft = 1;
4252	p->pack_keep_in_core = keep;
4253	}
4254	}
4255
4256	static void add_objects_in_unpacked_packs(void);
4257
4258	static void enumerate_cruft_objects(void)
4259	{
4260	if (progress)
4261	progress_state = start_progress(the_repository,
4262	_("Enumerating cruft objects"), 0);
4263
4264	add_objects_in_unpacked_packs();
4265	add_unreachable_loose_objects(NULL);
4266
4267	stop_progress(&progress_state);
4268	}
4269
4270	static void enumerate_and_traverse_cruft_objects(struct string_list *fresh_packs)
4271	{
4272	struct packed_git *p;
4273	struct rev_info revs;
4274	int ret;
4275
4276	repo_init_revisions(the_repository, &revs, NULL);
4277
4278	revs.tag_objects = 1;
4279	revs.tree_objects = 1;
4280	revs.blob_objects = 1;
4281
4282	revs.include_check = cruft_include_check;
4283	revs.include_check_obj = cruft_include_check_obj;
4284
4285	revs.ignore_missing_links = 1;
4286
4287	if (progress)
4288	progress_state = start_progress(the_repository,
4289	_("Enumerating cruft objects"), 0);
4290	ret = add_unseen_recent_objects_to_traversal(&revs, cruft_expiration,
4291	set_cruft_mtime, 1);
4292	stop_progress(&progress_state);
4293
4294	if (ret)
4295	die(_("unable to add cruft objects"));
4296
4297	/*
4298	* Re-mark only the fresh packs as kept so that objects in
4299	* unknown packs do not halt the reachability traversal early.
4300	*/
4301	repo_for_each_pack(the_repository, p)
4302	p->pack_keep_in_core = 0;
4303	mark_pack_kept_in_core(fresh_packs, 1);
4304
4305	if (prepare_revision_walk(&revs))
4306	die(_("revision walk setup failed"));
4307	if (progress)
4308	progress_state = start_progress(the_repository,
4309	_("Traversing cruft objects"), 0);
4310	nr_seen = 0;
4311	traverse_commit_list(&revs, show_cruft_commit, show_cruft_object, NULL);
4312
4313	stop_progress(&progress_state);
4314	release_revisions(&revs);
4315	}
4316
4317	static void read_cruft_objects(void)
4318	{
4319	struct strbuf buf = STRBUF_INIT;
4320	struct string_list discard_packs = STRING_LIST_INIT_DUP;
4321	struct string_list fresh_packs = STRING_LIST_INIT_DUP;
4322	struct packed_git *p;
4323
4324	ignore_packed_keep_in_core = 1;
4325
4326	while (strbuf_getline(&buf, stdin) != EOF) {
4327	if (!buf.len)
4328	continue;
4329
4330	if (*buf.buf == '-')
4331	string_list_append(&discard_packs, buf.buf + 1);
4332	else
4333	string_list_append(&fresh_packs, buf.buf);
4334	}
4335
4336	string_list_sort(&discard_packs);
4337	string_list_sort(&fresh_packs);
4338
4339	repo_for_each_pack(the_repository, p) {
4340	const char *pack_name = pack_basename(p);
4341	struct string_list_item *item;
4342
4343	item = string_list_lookup(&fresh_packs, pack_name);
4344	if (!item)
4345	item = string_list_lookup(&discard_packs, pack_name);
4346
4347	if (item) {
4348	item->util = p;
4349	} else {
4350	/*
4351	* This pack wasn't mentioned in either the "fresh" or
4352	* "discard" list, so the caller didn't know about it.
4353	*
4354	* Mark it as kept so that its objects are ignored by
4355	* add_unseen_recent_objects_to_traversal(). We'll
4356	* unmark it before starting the traversal so it doesn't
4357	* halt the traversal early.
4358	*/
4359	p->pack_keep_in_core = 1;
4360	}
4361	}
4362
4363	mark_pack_kept_in_core(&fresh_packs, 1);
4364	mark_pack_kept_in_core(&discard_packs, 0);
4365
4366	if (cruft_expiration)
4367	enumerate_and_traverse_cruft_objects(&fresh_packs);
4368	else
4369	enumerate_cruft_objects();
4370
4371	strbuf_release(&buf);
4372	string_list_clear(&discard_packs, 0);
4373	string_list_clear(&fresh_packs, 0);
4374	}
4375
4376	static void read_object_list_from_stdin(void)
4377	{
4378	char line[GIT_MAX_HEXSZ + 1 + PATH_MAX + 2];
4379	struct object_id oid;
4380	const char *p;
4381
4382	for (;;) {
4383	if (!fgets(line, sizeof(line), stdin)) {
4384	if (feof(stdin))
4385	break;
4386	if (!ferror(stdin))
4387	BUG("fgets returned NULL, not EOF, not error!");
4388	if (errno != EINTR)
4389	die_errno("fgets");
4390	clearerr(stdin);
4391	continue;
4392	}
4393	if (line[0] == '-') {
4394	if (get_oid_hex(line+1, &oid))
4395	die(_("expected edge object ID, got garbage:\n %s"),
4396	line);
4397	add_preferred_base(&oid);
4398	continue;
4399	}
4400	if (parse_oid_hex(line, &oid, &p))
4401	die(_("expected object ID, got garbage:\n %s"), line);
4402
4403	add_preferred_base_object(p + 1);
4404	add_object_entry(&oid, OBJ_NONE, p + 1, 0);
4405	}
4406	}
4407
4408	static void show_commit(struct commit commit, void data UNUSED)
4409	{
4410	add_object_entry(&commit->object.oid, OBJ_COMMIT, NULL, 0);
4411
4412	if (write_bitmap_index)
4413	index_commit_for_bitmap(commit);
4414
4415	if (use_delta_islands)
4416	propagate_island_marks(the_repository, commit);
4417	}
4418
4419	static void show_object(struct object obj, const char name,
4420	void *data UNUSED)
4421	{
4422	add_preferred_base_object(name);
4423	add_object_entry(&obj->oid, obj->type, name, 0);
4424
4425	if (use_delta_islands)
4426	record_tree_depth(&obj->oid, name);
4427	}
4428
4429	static void show_object__ma_allow_any(struct object obj, const char name, void *data)
4430	{
4431	assert(arg_missing_action == MA_ALLOW_ANY);
4432
4433	/*
4434	* Quietly ignore ALL missing objects. This avoids problems with
4435	* staging them now and getting an odd error later.
4436	*/
4437	if (!odb_has_object(the_repository->objects, &obj->oid, 0))
4438	return;
4439
4440	show_object(obj, name, data);
4441	}
4442
4443	static void show_object__ma_allow_promisor(struct object obj, const char name, void *data)
4444	{
4445	assert(arg_missing_action == MA_ALLOW_PROMISOR);
4446
4447	/*
4448	* Quietly ignore EXPECTED missing objects. This avoids problems with
4449	* staging them now and getting an odd error later.
4450	*/
4451	if (!odb_has_object(the_repository->objects, &obj->oid, 0) &&
4452	is_promisor_object(to_pack.repo, &obj->oid))
4453	return;
4454
4455	show_object(obj, name, data);
4456	}
4457
4458	static int option_parse_missing_action(const struct option *opt UNUSED,
4459	const char *arg, int unset)
4460	{
4461	assert(arg);
4462	assert(!unset);
4463
4464	if (!strcmp(arg, "error")) {
4465	arg_missing_action = MA_ERROR;
4466	fn_show_object = show_object;
4467	return 0;
4468	}
4469
4470	if (!strcmp(arg, "allow-any")) {
4471	arg_missing_action = MA_ALLOW_ANY;
4472	fetch_if_missing = 0;
4473	fn_show_object = show_object__ma_allow_any;
4474	return 0;
4475	}
4476
4477	if (!strcmp(arg, "allow-promisor")) {
4478	arg_missing_action = MA_ALLOW_PROMISOR;
4479	fetch_if_missing = 0;
4480	fn_show_object = show_object__ma_allow_promisor;
4481	return 0;
4482	}
4483
4484	die(_("invalid value for '%s': '%s'"), "--missing", arg);
4485	return 0;
4486	}
4487
4488	static void show_edge(struct commit *commit)
4489	{
4490	add_preferred_base(&commit->object.oid);
4491	}
4492
4493	static int add_object_in_unpacked_pack(const struct object_id *oid,
4494	struct object_info *oi,
4495	void *data UNUSED)
4496	{
4497	if (cruft) {
4498	add_cruft_object_entry(oid, OBJ_NONE, oi->source_infop->u.packed.pack,
4499	oi->source_infop->u.packed.offset, NULL,
4500	*oi->mtimep);
4501	} else {
4502	add_object_entry(oid, OBJ_NONE, "", 0);
4503	}
4504	return 0;
4505	}
4506
4507	static void add_objects_in_unpacked_packs(void)
4508	{
4509	struct odb_source *source;
4510	time_t mtime;
4511	struct odb_for_each_object_options opts = {
4512	.flags = ODB_FOR_EACH_OBJECT_PACK_ORDER \|
4513	ODB_FOR_EACH_OBJECT_LOCAL_ONLY \|
4514	ODB_FOR_EACH_OBJECT_SKIP_IN_CORE_KEPT_PACKS \|
4515	ODB_FOR_EACH_OBJECT_SKIP_ON_DISK_KEPT_PACKS,
4516	};
4517	struct odb_source_info source_info;
4518	struct object_info oi = {
4519	.mtimep = &mtime,
4520	.source_infop = &source_info,
4521	};
4522
4523	odb_prepare_alternates(to_pack.repo->objects);
4524	for (source = to_pack.repo->objects->sources; source; source = source->next) {
4525	struct odb_source_files *files = odb_source_files_downcast(source);
4526
4527	if (!source->local)
4528	continue;
4529
4530	if (odb_source_for_each_object(&files->packed->base, &oi,
4531	add_object_in_unpacked_pack, NULL, &opts))
4532	die(_("cannot open pack index"));
4533	}
4534	}
4535
4536	static int add_loose_object(const struct object_id oid, const char path,
4537	void *data)
4538	{
4539	struct rev_info *revs = data;
4540	enum object_type type = odb_read_object_info(the_repository->objects, oid, NULL);
4541
4542	if (type < 0) {
4543	warning(_("loose object at %s could not be examined"), path);
4544	return 0;
4545	}
4546
4547	if (cruft) {
4548	struct stat st;
4549	if (stat(path, &st) < 0) {
4550	if (errno == ENOENT)
4551	return 0;
4552	return error_errno("unable to stat %s", oid_to_hex(oid));
4553	}
4554
4555	add_cruft_object_entry(oid, type, NULL, 0, NULL,
4556	st.st_mtime);
4557	} else {
4558	add_object_entry(oid, type, "", 0);
4559	}
4560
4561	if (revs && type == OBJ_COMMIT)
4562	add_pending_oid(revs, NULL, oid, 0);
4563
4564	return 0;
4565	}
4566
4567	/*
4568	* We actually don't even have to worry about reachability here.
4569	* add_object_entry will weed out duplicates, so we just add every
4570	* loose object we find.
4571	*/
4572	static void add_unreachable_loose_objects(struct rev_info *revs)
4573	{
4574	for_each_loose_file_in_source(the_repository->objects->sources,
4575	add_loose_object, NULL, NULL, revs);
4576	}
4577
4578	static int has_sha1_pack_kept_or_nonlocal(const struct object_id *oid)
4579	{
4580	static struct packed_git *last_found = NULL;
4581	struct packed_git *p;
4582
4583	if (last_found && find_pack_entry_one(oid, last_found))
4584	return 1;
4585
4586	repo_for_each_pack(the_repository, p) {
4587	/*
4588	* We have already checked `last_found`, so there is no need to
4589	* re-check here.
4590	*/
4591	if (p == last_found)
4592	continue;
4593
4594	if ((!p->pack_local \|\| p->pack_keep \|\| p->pack_keep_in_core) &&
4595	find_pack_entry_one(oid, p)) {
4596	last_found = p;
4597	return 1;
4598	}
4599	}
4600
4601	return 0;
4602	}
4603
4604	/*
4605	* Store a list of sha1s that are should not be discarded
4606	* because they are either written too recently, or are
4607	* reachable from another object that was.
4608	*
4609	* This is filled by get_object_list.
4610	*/
4611	static struct oid_array recent_objects;
4612
4613	static int loosened_object_can_be_discarded(const struct object_id *oid,
4614	timestamp_t mtime)
4615	{
4616	if (!unpack_unreachable_expiration)
4617	return 0;
4618	if (mtime > unpack_unreachable_expiration)
4619	return 0;
4620	if (oid_array_lookup(&recent_objects, oid) >= 0)
4621	return 0;
4622	return 1;
4623	}
4624
4625	static int force_object_loose(struct odb_source *source,
4626	const struct object_id *oid,
4627	const time_t *mtime)
4628	{
4629	struct odb_source_files *files = odb_source_files_downcast(source);
4630	const struct git_hash_algo *compat = source->odb->repo->compat_hash_algo;
4631	struct object_info oi = OBJECT_INFO_INIT;
4632	struct object_id compat_oid, *compat_oid_p = NULL;
4633	enum object_type type;
4634	void *buf = NULL;
4635	size_t len;
4636	int ret;
4637
4638	for (struct odb_source *s = source->odb->sources; s; s = s->next) {
4639	struct odb_source_files *files = odb_source_files_downcast(s);
4640	if (!odb_source_read_object_info(&files->loose->base, oid, NULL, 0))
4641	return 0;
4642	}
4643
4644	oi.typep = &type;
4645	oi.sizep = &len;
4646	oi.contentp = &buf;
4647	if (odb_read_object_info_extended(source->odb, oid, &oi, 0)) {
4648	ret = error(_("cannot read object for %s"), oid_to_hex(oid));
4649	goto out;
4650	}
4651
4652	if (compat) {
4653	if (repo_oid_to_algop(source->odb->repo, oid, compat, &compat_oid)) {
4654	ret = error(_("cannot map object %s to %s"),
4655	oid_to_hex(oid), compat->name);
4656	goto out;
4657	}
4658
4659	compat_oid_p = &compat_oid;
4660	}
4661
4662	ret = odb_source_write_object(&files->loose->base, buf, len, type, oid,
4663	compat_oid_p, mtime, 0);
4664
4665	out:
4666	free(buf);
4667	return ret;
4668	}
4669
4670	static void loosen_unused_packed_objects(void)
4671	{
4672	struct packed_git *p;
4673	uint32_t i;
4674	uint32_t loosened_objects_nr = 0;
4675	struct object_id oid;
4676
4677	repo_for_each_pack(the_repository, p) {
4678	if (!p->pack_local \|\| p->pack_keep \|\| p->pack_keep_in_core)
4679	continue;
4680
4681	if (open_pack_index(p))
4682	die(_("cannot open pack index"));
4683
4684	for (i = 0; i < p->num_objects; i++) {
4685	nth_packed_object_id(&oid, p, i);
4686	if (!packlist_find(&to_pack, &oid) &&
4687	!has_sha1_pack_kept_or_nonlocal(&oid) &&
4688	!loosened_object_can_be_discarded(&oid, p->mtime)) {
4689	if (force_object_loose(the_repository->objects->sources,
4690	&oid, &p->mtime))
4691	die(_("unable to force loose object"));
4692	loosened_objects_nr++;
4693	}
4694	}
4695	}
4696
4697	trace2_data_intmax("pack-objects", the_repository,
4698	"loosen_unused_packed_objects/loosened", loosened_objects_nr);
4699	}
4700
4701	/*
4702	* This tracks any options which pack-reuse code expects to be on, or which a
4703	* reader of the pack might not understand, and which would therefore prevent
4704	* blind reuse of what we have on disk.
4705	*/
4706	static int pack_options_allow_reuse(void)
4707	{
4708	return allow_pack_reuse != NO_PACK_REUSE &&
4709	pack_to_stdout &&
4710	!ignore_packed_keep_on_disk &&
4711	!ignore_packed_keep_in_core &&
4712	(!local \|\| !have_non_local_packs) &&
4713	!incremental;
4714	}
4715
4716	static int get_object_list_from_bitmap(struct rev_info *revs)
4717	{
4718	if (!(bitmap_git = prepare_bitmap_walk(revs, 0)))
4719	return -1;
4720
4721	/*
4722	* For now, force the name-hash version to be 1 since that
4723	* is the version implied by the bitmap format. Later, the
4724	* format can include this version explicitly in its format,
4725	* allowing readers to know the version that was used during
4726	* the bitmap write.
4727	*/
4728	name_hash_version = 1;
4729
4730	if (pack_options_allow_reuse())
4731	reuse_partial_packfile_from_bitmap(bitmap_git,
4732	&reuse_packfiles,
4733	&reuse_packfiles_nr,
4734	&reuse_packfile_bitmap,
4735	allow_pack_reuse == MULTI_PACK_REUSE);
4736
4737	if (reuse_packfiles) {
4738	reuse_packfile_objects = bitmap_popcount(reuse_packfile_bitmap);
4739	if (!reuse_packfile_objects)
4740	BUG("expected non-empty reuse bitmap");
4741
4742	nr_result += reuse_packfile_objects;
4743	nr_seen += reuse_packfile_objects;
4744	display_progress(progress_state, nr_seen);
4745	}
4746
4747	traverse_bitmap_commit_list(bitmap_git, revs,
4748	&add_object_entry_from_bitmap);
4749	return 0;
4750	}
4751
4752	static void record_recent_object(struct object *obj,
4753	const char *name UNUSED,
4754	void *data UNUSED)
4755	{
4756	oid_array_append(&recent_objects, &obj->oid);
4757	}
4758
4759	static void record_recent_commit(struct commit commit, void data UNUSED)
4760	{
4761	oid_array_append(&recent_objects, &commit->object.oid);
4762	}
4763
4764	static int mark_bitmap_preferred_tip(const struct reference ref, void data UNUSED)
4765	{
4766	const struct object_id *maybe_peeled = ref->oid;
4767	struct object_id peeled;
4768	struct object *object;
4769
4770	if (!reference_get_peeled_oid(the_repository, ref, &peeled))
4771	maybe_peeled = &peeled;
4772
4773	object = parse_object_or_die(the_repository, maybe_peeled, ref->name);
4774	if (object->type == OBJ_COMMIT)
4775	object->flags \|= NEEDS_BITMAP;
4776
4777	return 0;
4778	}
4779
4780	static inline int is_oid_uninteresting(struct repository *repo,
4781	struct object_id *oid)
4782	{
4783	struct object *o = lookup_object(repo, oid);
4784	return !o \|\| (o->flags & UNINTERESTING);
4785	}
4786
4787	static int add_objects_by_path(const char *path,
4788	struct oid_array *oids,
4789	enum object_type type,
4790	void *data)
4791	{
4792	size_t oe_start = to_pack.nr_objects;
4793	size_t oe_end;
4794	unsigned int *processed = data;
4795
4796	/*
4797	* First, add all objects to the packing data, including the ones
4798	* marked UNINTERESTING (translated to 'exclude') as they can be
4799	* used as delta bases.
4800	*/
4801	for (size_t i = 0; i < oids->nr; i++) {
4802	int exclude;
4803	struct object_info oi = OBJECT_INFO_INIT;
4804	struct object_id *oid = &oids->oid[i];
4805
4806	/* Skip objects that do not exist locally. */
4807	if ((exclude_promisor_objects \|\| arg_missing_action != MA_ERROR) &&
4808	odb_read_object_info_extended(the_repository->objects, oid, &oi,
4809	OBJECT_INFO_FOR_PREFETCH) < 0)
4810	continue;
4811
4812	exclude = is_oid_uninteresting(the_repository, oid);
4813
4814	if (exclude && !thin)
4815	continue;
4816
4817	add_object_entry(oid, type, path, exclude);
4818
4819	if (type == OBJ_COMMIT) {
4820	struct commit *commit;
4821
4822	if (!write_bitmap_index && !use_delta_islands)
4823	continue;
4824
4825	commit = lookup_commit(the_repository, oid);
4826	if (!commit)
4827	die(_("could not find commit %s"), oid_to_hex(oid));
4828	if (write_bitmap_index)
4829	index_commit_for_bitmap(commit);
4830	/*
4831	* Skip island propagation for boundary commits.
4832	* The regular traversal's show_commit() is only
4833	* called for interesting commits; matching that
4834	* here keeps path-walk from doing extra work that
4835	* would only be a no-op anyway (boundary commits
4836	* are not in island_marks).
4837	*/
4838	if (use_delta_islands && !exclude)
4839	propagate_island_marks(the_repository, commit);
4840	} else if (type == OBJ_TREE && use_delta_islands) {
4841	record_tree_depth(oid, path);
4842	}
4843	}
4844
4845	oe_end = to_pack.nr_objects;
4846
4847	/* We can skip delta calculations if it is a no-op. */
4848	if (oe_end == oe_start \|\| !window)
4849	return 0;
4850
4851	ALLOC_GROW(to_pack.regions,
4852	to_pack.nr_regions + 1,
4853	to_pack.nr_regions_alloc);
4854
4855	to_pack.regions[to_pack.nr_regions].start = oe_start;
4856	to_pack.regions[to_pack.nr_regions].nr = oe_end - oe_start;
4857	to_pack.nr_regions++;
4858
4859	*processed += oids->nr;
4860	display_progress(progress_state, *processed);
4861
4862	return 0;
4863	}
4864
4865	static int get_object_list_path_walk(struct rev_info *revs)
4866	{
4867	struct path_walk_info info = PATH_WALK_INFO_INIT;
4868	unsigned int processed = 0;
4869	int result;
4870
4871	info.revs = revs;
4872	info.path_fn = add_objects_by_path;
4873	info.path_fn_data = &processed;
4874
4875	/*
4876	* Path-walk needs boundary commits to discover thin-pack bases, but
4877	* bitmap traversal does not understand the boundary state. Set it
4878	* here so any prior bitmap attempt sees the usual non-boundary walk.
4879	*/
4880	revs->boundary = 1;
4881
4882	/*
4883	* Allow the --[no-]sparse option to be interesting here, if only
4884	* for testing purposes. Paths with no interesting objects will not
4885	* contribute to the resulting pack, but only create noisy preferred
4886	* base objects.
4887	*/
4888	info.prune_all_uninteresting = sparse;
4889	info.edge_aggressive = shallow;
4890
4891	trace2_region_enter("pack-objects", "path-walk", revs->repo);
4892	result = walk_objects_by_path(&info);
4893	trace2_region_leave("pack-objects", "path-walk", revs->repo);
4894
4895	path_walk_info_clear(&info);
4896
4897	return result;
4898	}
4899
4900	static void get_object_list(struct rev_info revs, struct strvec argv)
4901	{
4902	struct setup_revision_opt s_r_opt = {
4903	.allow_exclude_promisor_objects = 1,
4904	};
4905	struct repo_config_values *cfg = repo_config_values(the_repository);
4906	char line[1000];
4907	int flags = 0;
4908	int save_warning;
4909
4910	save_commit_buffer = 0;
4911	setup_revisions_from_strvec(argv, revs, &s_r_opt);
4912
4913	/* make sure shallows are read */
4914	is_repository_shallow(the_repository);
4915
4916	save_warning = cfg->warn_on_object_refname_ambiguity;
4917	cfg->warn_on_object_refname_ambiguity = 0;
4918
4919	while (fgets(line, sizeof(line), stdin) != NULL) {
4920	int len = strlen(line);
4921	if (len && line[len - 1] == '\n')
4922	line[--len] = 0;
4923	if (!len)
4924	break;
4925	if (*line == '-') {
4926	if (!strcmp(line, "--not")) {
4927	flags ^= UNINTERESTING;
4928	write_bitmap_index = 0;
4929	continue;
4930	}
4931	if (starts_with(line, "--shallow ")) {
4932	struct object_id oid;
4933	if (get_oid_hex(line + 10, &oid))
4934	die("not an object name '%s'", line + 10);
4935	register_shallow(the_repository, &oid);
4936	use_bitmap_index = 0;
4937	continue;
4938	}
4939	die(_("not a rev '%s'"), line);
4940	}
4941	if (handle_revision_arg(line, revs, flags, REVARG_CANNOT_BE_FILENAME))
4942	die(_("bad revision '%s'"), line);
4943	}
4944
4945	cfg->warn_on_object_refname_ambiguity = save_warning;
4946
4947	if (use_bitmap_index && !get_object_list_from_bitmap(revs))
4948	return;
4949
4950	if (use_delta_islands)
4951	load_delta_islands(the_repository, progress);
4952
4953	if (write_bitmap_index)
4954	for_each_preferred_bitmap_tip(the_repository, mark_bitmap_preferred_tip,
4955	NULL);
4956
4957	if (!fn_show_object)
4958	fn_show_object = show_object;
4959
4960	if (path_walk) {
4961	if (get_object_list_path_walk(revs)) {
4962	warning(_("failed to pack objects via path-walk"));
4963	path_walk = 0;
4964	}
4965	}
4966
4967	if (!path_walk) {
4968	if (prepare_revision_walk(revs))
4969	die(_("revision walk setup failed"));
4970	mark_edges_uninteresting(revs, show_edge, sparse);
4971	traverse_commit_list(revs,
4972	show_commit, fn_show_object,
4973	NULL);
4974	}
4975
4976	if (unpack_unreachable_expiration) {
4977	revs->ignore_missing_links = 1;
4978	if (add_unseen_recent_objects_to_traversal(revs,
4979	unpack_unreachable_expiration, NULL, 0))
4980	die(_("unable to add recent objects"));
4981	if (prepare_revision_walk(revs))
4982	die(_("revision walk setup failed"));
4983	traverse_commit_list(revs, record_recent_commit,
4984	record_recent_object, NULL);
4985	}
4986
4987	if (keep_unreachable)
4988	add_objects_in_unpacked_packs();
4989	if (pack_loose_unreachable)
4990	add_unreachable_loose_objects(NULL);
4991	if (unpack_unreachable)
4992	loosen_unused_packed_objects();
4993
4994	oid_array_clear(&recent_objects);
4995	}
4996
4997	static void add_extra_kept_packs(const struct string_list *names)
4998	{
4999	struct packed_git *p;
5000

Showing first 5,000 of 5,537 lines. View raw