pack-objects.c · matheusbsbs/matheus-bagliano

bisect

bisect jch maint master next seen test todo

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

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