pack-objects.c · matheusbsbs/matheus-bagliano

maint

bisect jch maint master next seen test todo

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

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