packed-backend.c · leroysheep/BookAlchemy

maint

bisect jch maint master next seen test todo

c 2,165 lines 57.9 KB

Raw

1	#define USE_THE_REPOSITORY_VARIABLE
2	#define DISABLE_SIGN_COMPARE_WARNINGS
3
4	#include "../git-compat-util.h"
5	#include "../config.h"
6	#include "../dir.h"
7	#include "../fsck.h"
8	#include "../gettext.h"
9	#include "../hash.h"
10	#include "../hex.h"
11	#include "../refs.h"
12	#include "refs-internal.h"
13	#include "packed-backend.h"
14	#include "../iterator.h"
15	#include "../lockfile.h"
16	#include "../chdir-notify.h"
17	#include "../statinfo.h"
18	#include "../worktree.h"
19	#include "../wrapper.h"
20	#include "../write-or-die.h"
21	#include "../trace2.h"
22
23	enum mmap_strategy {
24	/*
25	* Don't use mmap() at all for reading `packed-refs`.
26	*/
27	MMAP_NONE,
28
29	/*
30	* Can use mmap() for reading `packed-refs`, but the file must
31	* not remain mmapped. This is the usual option on Windows,
32	* where you cannot rename a new version of a file onto a file
33	* that is currently mmapped.
34	*/
35	MMAP_TEMPORARY,
36
37	/*
38	* It is OK to leave the `packed-refs` file mmapped while
39	* arbitrary other code is running.
40	*/
41	MMAP_OK
42	};
43
44	#if defined(NO_MMAP)
45	static enum mmap_strategy mmap_strategy = MMAP_NONE;
46	#elif defined(MMAP_PREVENTS_DELETE)
47	static enum mmap_strategy mmap_strategy = MMAP_TEMPORARY;
48	#else
49	static enum mmap_strategy mmap_strategy = MMAP_OK;
50	#endif
51
52	struct packed_ref_store;
53
54	/*
55	* A `snapshot` represents one snapshot of a `packed-refs` file.
56	*
57	* Normally, this will be a mmapped view of the contents of the
58	* `packed-refs` file at the time the snapshot was created. However,
59	* if the `packed-refs` file was not sorted, this might point at heap
60	* memory holding the contents of the `packed-refs` file with its
61	* records sorted by refname.
62	*
63	* `snapshot` instances are reference counted (via
64	* `acquire_snapshot()` and `release_snapshot()`). This is to prevent
65	* an instance from disappearing while an iterator is still iterating
66	* over it. Instances are garbage collected when their `referrers`
67	* count goes to zero.
68	*
69	* The most recent `snapshot`, if available, is referenced by the
70	* `packed_ref_store`. Its freshness is checked whenever
71	* `get_snapshot()` is called; if the existing snapshot is obsolete, a
72	* new snapshot is taken.
73	*/
74	struct snapshot {
75	/*
76	* A back-pointer to the packed_ref_store with which this
77	* snapshot is associated:
78	*/
79	struct packed_ref_store *refs;
80
81	/* Is the `packed-refs` file currently mmapped? */
82	int mmapped;
83
84	/*
85	* The contents of the `packed-refs` file:
86	*
87	* - buf -- a pointer to the start of the memory
88	* - start -- a pointer to the first byte of actual references
89	* (i.e., after the header line, if one is present)
90	* - eof -- a pointer just past the end of the reference
91	* contents
92	*
93	* If the `packed-refs` file was already sorted, `buf` points
94	* at the mmapped contents of the file. If not, it points at
95	* heap-allocated memory containing the contents, sorted. If
96	* there were no contents (e.g., because the file didn't
97	* exist), `buf`, `start`, and `eof` are all NULL.
98	*/
99	char buf, start, *eof;
100
101	/*
102	* What is the peeled state of the `packed-refs` file that
103	* this snapshot represents? (This is usually determined from
104	* the file's header.)
105	*/
106	enum { PEELED_NONE, PEELED_TAGS, PEELED_FULLY } peeled;
107
108	/*
109	* Count of references to this instance, including the pointer
110	* from `packed_ref_store::snapshot`, if any. The instance
111	* will not be freed as long as the reference count is
112	* nonzero.
113	*/
114	unsigned int referrers;
115
116	/*
117	* The metadata of the `packed-refs` file from which this
118	* snapshot was created, used to tell if the file has been
119	* replaced since we read it.
120	*/
121	struct stat_validity validity;
122	};
123
124	/*
125	* A `ref_store` representing references stored in a `packed-refs`
126	* file. It implements the `ref_store` interface, though it has some
127	* limitations:
128	*
129	* - It cannot store symbolic references.
130	*
131	* - It cannot store reflogs.
132	*
133	* - It does not support reference renaming (though it could).
134	*
135	* On the other hand, it can be locked outside of a reference
136	* transaction. In that case, it remains locked even after the
137	* transaction is done and the new `packed-refs` file is activated.
138	*/
139	struct packed_ref_store {
140	struct ref_store base;
141
142	unsigned int store_flags;
143
144	/* The path of the "packed-refs" file: */
145	char *path;
146
147	/*
148	* A snapshot of the values read from the `packed-refs` file,
149	* if it might still be current; otherwise, NULL.
150	*/
151	struct snapshot *snapshot;
152
153	/*
154	* Lock used for the "packed-refs" file. Note that this (and
155	* thus the enclosing `packed_ref_store`) must not be freed.
156	*/
157	struct lock_file lock;
158
159	/*
160	* Temporary file used when rewriting new contents to the
161	* "packed-refs" file. Note that this (and thus the enclosing
162	* `packed_ref_store`) must not be freed.
163	*/
164	struct tempfile *tempfile;
165	};
166
167	/*
168	* Increment the reference count of `*snapshot`.
169	*/
170	static void acquire_snapshot(struct snapshot *snapshot)
171	{
172	snapshot->referrers++;
173	}
174
175	/*
176	* If the buffer in `snapshot` is active, then either munmap the
177	* memory and close the file, or free the memory. Then set the buffer
178	* pointers to NULL.
179	*/
180	static void clear_snapshot_buffer(struct snapshot *snapshot)
181	{
182	if (snapshot->mmapped) {
183	if (munmap(snapshot->buf, snapshot->eof - snapshot->buf))
184	die_errno("error ummapping packed-refs file %s",
185	snapshot->refs->path);
186	snapshot->mmapped = 0;
187	} else {
188	free(snapshot->buf);
189	}
190	snapshot->buf = snapshot->start = snapshot->eof = NULL;
191	}
192
193	/*
194	* Decrease the reference count of `*snapshot`. If it goes to zero,
195	* free `*snapshot` and return true; otherwise return false.
196	*/
197	static int release_snapshot(struct snapshot *snapshot)
198	{
199	if (!--snapshot->referrers) {
200	stat_validity_clear(&snapshot->validity);
201	clear_snapshot_buffer(snapshot);
202	free(snapshot);
203	return 1;
204	} else {
205	return 0;
206	}
207	}
208
209	static size_t snapshot_hexsz(const struct snapshot *snapshot)
210	{
211	return snapshot->refs->base.repo->hash_algo->hexsz;
212	}
213
214	/*
215	* Since packed-refs is only stored in the common dir, don't parse the
216	* payload and rely on the files-backend to set 'gitdir' correctly.
217	*/
218	struct ref_store packed_ref_store_init(struct repository repo,
219	const char *payload UNUSED,
220	const char *gitdir,
221	const struct ref_store_init_options *opts)
222	{
223	struct packed_ref_store refs = xcalloc(1, sizeof(refs));
224	struct ref_store ref_store = (struct ref_store )refs;
225	struct strbuf sb = STRBUF_INIT;
226
227	base_ref_store_init(ref_store, repo, gitdir, &refs_be_packed);
228	refs->store_flags = opts->access_flags;
229
230	strbuf_addf(&sb, "%s/packed-refs", gitdir);
231	refs->path = strbuf_detach(&sb, NULL);
232	chdir_notify_reparent("packed-refs", &refs->path);
233	return ref_store;
234	}
235
236	/*
237	* Downcast `ref_store` to `packed_ref_store`. Die if `ref_store` is
238	* not a `packed_ref_store`. Also die if `packed_ref_store` doesn't
239	* support at least the flags specified in `required_flags`. `caller`
240	* is used in any necessary error messages.
241	*/
242	static struct packed_ref_store packed_downcast(struct ref_store ref_store,
243	unsigned int required_flags,
244	const char *caller)
245	{
246	struct packed_ref_store *refs;
247
248	if (ref_store->be != &refs_be_packed)
249	BUG("ref_store is type \"%s\" not \"packed\" in %s",
250	ref_store->be->name, caller);
251
252	refs = (struct packed_ref_store *)ref_store;
253
254	if ((refs->store_flags & required_flags) != required_flags)
255	BUG("unallowed operation (%s), requires %x, has %x\n",
256	caller, required_flags, refs->store_flags);
257
258	return refs;
259	}
260
261	static void clear_snapshot(struct packed_ref_store *refs)
262	{
263	if (refs->snapshot) {
264	struct snapshot *snapshot = refs->snapshot;
265
266	refs->snapshot = NULL;
267	release_snapshot(snapshot);
268	}
269	}
270
271	static void packed_ref_store_release(struct ref_store *ref_store)
272	{
273	struct packed_ref_store *refs = packed_downcast(ref_store, 0, "release");
274	clear_snapshot(refs);
275	rollback_lock_file(&refs->lock);
276	delete_tempfile(&refs->tempfile);
277	free(refs->path);
278	}
279
280	static NORETURN void die_unterminated_line(const char *path,
281	const char *p, size_t len)
282	{
283	if (len < 80)
284	die("unterminated line in %s: %.*s", path, (int)len, p);
285	else
286	die("unterminated line in %s: %.75s...", path, p);
287	}
288
289	static NORETURN void die_invalid_line(const char *path,
290	const char *p, size_t len)
291	{
292	const char *eol = memchr(p, '\n', len);
293
294	if (!eol)
295	die_unterminated_line(path, p, len);
296	else if (eol - p < 80)
297	die("unexpected line in %s: %.*s", path, (int)(eol - p), p);
298	else
299	die("unexpected line in %s: %.75s...", path, p);
300
301	}
302
303	struct snapshot_record {
304	const char *start;
305	size_t len;
306	};
307
308
309	static int cmp_packed_refname(const char r1, const char r2)
310	{
311	while (1) {
312	if (*r1 == '\n')
313	return *r2 == '\n' ? 0 : -1;
314	if (r1 != r2) {
315	if (*r2 == '\n')
316	return 1;
317	else
318	return (unsigned char)r1 < (unsigned char)r2 ? -1 : +1;
319	}
320	r1++;
321	r2++;
322	}
323	}
324
325	static int cmp_packed_ref_records(const void v1, const void v2,
326	void *cb_data)
327	{
328	const struct snapshot *snapshot = cb_data;
329	const struct snapshot_record e1 = v1, e2 = v2;
330	const char *r1 = e1->start + snapshot_hexsz(snapshot) + 1;
331	const char *r2 = e2->start + snapshot_hexsz(snapshot) + 1;
332
333	return cmp_packed_refname(r1, r2);
334	}
335
336	/*
337	* Compare a snapshot record at `rec` to the specified NUL-terminated
338	* refname.
339	*/
340	static int cmp_record_to_refname(const char rec, const char refname,
341	int start, const struct snapshot *snapshot)
342	{
343	const char *r1 = rec + snapshot_hexsz(snapshot) + 1;
344	const char *r2 = refname;
345
346	while (1) {
347	if (*r1 == '\n')
348	return *r2 ? -1 : 0;
349	if (!*r2)
350	return start ? 1 : -1;
351	if (r1 != r2)
352	return (unsigned char)r1 < (unsigned char)r2 ? -1 : +1;
353	r1++;
354	r2++;
355	}
356	}
357
358	/*
359	* `snapshot->buf` is not known to be sorted. Check whether it is, and
360	* if not, sort it into new memory and munmap/free the old storage.
361	*/
362	static void sort_snapshot(struct snapshot *snapshot)
363	{
364	struct snapshot_record *records = NULL;
365	size_t alloc = 0, nr = 0;
366	int sorted = 1;
367	const char pos, eof, *eol;
368	size_t len, i;
369	char new_buffer, dst;
370
371	pos = snapshot->start;
372	eof = snapshot->eof;
373
374	if (pos == eof)
375	return;
376
377	len = eof - pos;
378
379	/*
380	* Initialize records based on a crude estimate of the number
381	* of references in the file (we'll grow it below if needed):
382	*/
383	ALLOC_GROW(records, len / 80 + 20, alloc);
384
385	while (pos < eof) {
386	eol = memchr(pos, '\n', eof - pos);
387	if (!eol)
388	/* The safety check should prevent this. */
389	BUG("unterminated line found in packed-refs");
390	if (eol - pos < snapshot_hexsz(snapshot) + 2)
391	die_invalid_line(snapshot->refs->path,
392	pos, eof - pos);
393	eol++;
394	if (eol < eof && *eol == '^') {
395	/*
396	* Keep any peeled line together with its
397	* reference:
398	*/
399	const char *peeled_start = eol;
400
401	eol = memchr(peeled_start, '\n', eof - peeled_start);
402	if (!eol)
403	/* The safety check should prevent this. */
404	BUG("unterminated peeled line found in packed-refs");
405	eol++;
406	}
407
408	ALLOC_GROW(records, nr + 1, alloc);
409	records[nr].start = pos;
410	records[nr].len = eol - pos;
411	nr++;
412
413	if (sorted &&
414	nr > 1 &&
415	cmp_packed_ref_records(&records[nr - 2],
416	&records[nr - 1], snapshot) >= 0)
417	sorted = 0;
418
419	pos = eol;
420	}
421
422	if (sorted)
423	goto cleanup;
424
425	/* We need to sort the memory. First we sort the records array: */
426	QSORT_S(records, nr, cmp_packed_ref_records, snapshot);
427
428	/*
429	* Allocate a new chunk of memory, and copy the old memory to
430	* the new in the order indicated by `records` (not bothering
431	* with the header line):
432	*/
433	new_buffer = xmalloc(len);
434	for (dst = new_buffer, i = 0; i < nr; i++) {
435	memcpy(dst, records[i].start, records[i].len);
436	dst += records[i].len;
437	}
438
439	/*
440	* Now munmap the old buffer and use the sorted buffer in its
441	* place:
442	*/
443	clear_snapshot_buffer(snapshot);
444	snapshot->buf = snapshot->start = new_buffer;
445	snapshot->eof = new_buffer + len;
446
447	cleanup:
448	free(records);
449	}
450
451	/*
452	* Return a pointer to the start of the record that contains the
453	* character `*p` (which must be within the buffer). If no other
454	* record start is found, return `buf`.
455	*/
456	static const char find_start_of_record(const char buf, const char *p)
457	{
458	while (p > buf && (p[-1] != '\n' \|\| p[0] == '^'))
459	p--;
460	return p;
461	}
462
463	/*
464	* Return a pointer to the start of the record following the record
465	* that contains `*p`. If none is found before `end`, return `end`.
466	*/
467	static const char find_end_of_record(const char p, const char *end)
468	{
469	while (++p < end && (p[-1] != '\n' \|\| p[0] == '^'))
470	;
471	return p;
472	}
473
474	/*
475	* We want to be able to compare mmapped reference records quickly,
476	* without totally parsing them. We can do so because the records are
477	* LF-terminated, and the refname should start exactly (GIT_SHA1_HEXSZ
478	* + 1) bytes past the beginning of the record.
479	*
480	* But what if the `packed-refs` file contains garbage? We're willing
481	* to tolerate not detecting the problem, as long as we don't produce
482	* totally garbled output (we can't afford to check the integrity of
483	* the whole file during every Git invocation). But we do want to be
484	* sure that we never read past the end of the buffer in memory and
485	* perform an illegal memory access.
486	*
487	* Guarantee that minimum level of safety by verifying that the last
488	* record in the file is LF-terminated, and that it has at least
489	* (GIT_SHA1_HEXSZ + 1) characters before the LF. Die if either of
490	* these checks fails.
491	*/
492	static void verify_buffer_safe(struct snapshot *snapshot)
493	{
494	const char *start = snapshot->start;
495	const char *eof = snapshot->eof;
496	const char *last_line;
497
498	if (start == eof)
499	return;
500
501	last_line = find_start_of_record(start, eof - 1);
502	if (*(eof - 1) != '\n' \|\|
503	eof - last_line < snapshot_hexsz(snapshot) + 2)
504	die_invalid_line(snapshot->refs->path,
505	last_line, eof - last_line);
506	}
507
508	/*
509	* When parsing the "packed-refs" file, we will parse it line by line.
510	* Because we know the start pointer of the refname and the next
511	* newline pointer, we could calculate the length of the refname by
512	* subtracting the two pointers. However, there is a corner case where
513	* the refname contains corrupted embedded NUL characters. And
514	* `check_refname_format()` will not catch this when the truncated
515	* refname is still a valid refname. To prevent this, we need to check
516	* whether the refname contains the NUL characters.
517	*/
518	static int refname_contains_nul(struct strbuf *refname)
519	{
520	return !!memchr(refname->buf, '\0', refname->len);
521	}
522
523	#define SMALL_FILE_SIZE (32*1024)
524
525	static int allocate_snapshot_buffer(struct snapshot snapshot, int fd, struct stat st)
526	{
527	ssize_t bytes_read;
528	size_t size;
529
530	size = xsize_t(st->st_size);
531	if (!size)
532	return 0;
533
534	if (mmap_strategy == MMAP_NONE \|\| size <= SMALL_FILE_SIZE) {
535	snapshot->buf = xmalloc(size);
536	bytes_read = read_in_full(fd, snapshot->buf, size);
537	if (bytes_read < 0 \|\| bytes_read != size)
538	die_errno("couldn't read %s", snapshot->refs->path);
539	snapshot->mmapped = 0;
540	} else {
541	snapshot->buf = xmmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);
542	snapshot->mmapped = 1;
543	}
544
545	snapshot->start = snapshot->buf;
546	snapshot->eof = snapshot->buf + size;
547
548	return 1;
549	}
550
551	/*
552	* Depending on `mmap_strategy`, either mmap or read the contents of
553	* the `packed-refs` file into the snapshot. Return 1 if the file
554	* existed and was read, or 0 if the file was absent or empty. Die on
555	* errors.
556	*/
557	static int load_contents(struct snapshot *snapshot)
558	{
559	struct stat st;
560	int ret;
561	int fd;
562
563	fd = open(snapshot->refs->path, O_RDONLY);
564	if (fd < 0) {
565	if (errno == ENOENT) {
566	/*
567	* This is OK; it just means that no
568	* "packed-refs" file has been written yet,
569	* which is equivalent to it being empty,
570	* which is its state when initialized with
571	* zeros.
572	*/
573	return 0;
574	} else {
575	die_errno("couldn't read %s", snapshot->refs->path);
576	}
577	}
578
579	stat_validity_update(&snapshot->validity, fd);
580
581	if (fstat(fd, &st) < 0)
582	die_errno("couldn't stat %s", snapshot->refs->path);
583
584	ret = allocate_snapshot_buffer(snapshot, fd, &st);
585
586	close(fd);
587	return ret;
588	}
589
590	static const char find_reference_location_1(struct snapshot snapshot,
591	const char *refname, int mustexist,
592	int start)
593	{
594	/*
595	* This is not quite a garden-variety binary search, because
596	* the data we're searching is made up of records, and we
597	* always need to find the beginning of a record to do a
598	* comparison. A "record" here is one line for the reference
599	* itself and zero or one peel lines that start with '^'. Our
600	* loop invariant is described in the next two comments.
601	*/
602
603	/*
604	* A pointer to the character at the start of a record whose
605	* preceding records all have reference names that come
606	* before `refname`.
607	*/
608	const char *lo = snapshot->start;
609
610	/*
611	* A pointer to a the first character of a record whose
612	* reference name comes after `refname`.
613	*/
614	const char *hi = snapshot->eof;
615
616	while (lo != hi) {
617	const char mid, rec;
618	int cmp;
619
620	mid = lo + (hi - lo) / 2;
621	rec = find_start_of_record(lo, mid);
622	cmp = cmp_record_to_refname(rec, refname, start, snapshot);
623	if (cmp < 0) {
624	lo = find_end_of_record(mid, hi);
625	} else if (cmp > 0) {
626	hi = rec;
627	} else {
628	return rec;
629	}
630	}
631
632	if (mustexist)
633	return NULL;
634	else
635	return lo;
636	}
637
638	/*
639	* Find the place in `snapshot->buf` where the start of the record for
640	* `refname` starts. If `mustexist` is true and the reference doesn't
641	* exist, then return NULL. If `mustexist` is false and the reference
642	* doesn't exist, then return the point where that reference would be
643	* inserted, or `snapshot->eof` (which might be NULL) if it would be
644	* inserted at the end of the file. In the latter mode, `refname`
645	* doesn't have to be a proper reference name; for example, one could
646	* search for "refs/replace/" to find the start of any replace
647	* references.
648	*
649	* The record is sought using a binary search, so `snapshot->buf` must
650	* be sorted.
651	*/
652	static const char find_reference_location(struct snapshot snapshot,
653	const char *refname, int mustexist)
654	{
655	return find_reference_location_1(snapshot, refname, mustexist, 1);
656	}
657
658	/*
659	* Find the place in `snapshot->buf` after the end of the record for
660	* `refname`. In other words, find the location of first thing after
661	* `refname`.
662	*
663	* Other semantics are identical to the ones in
664	* `find_reference_location()`.
665	*/
666	static const char find_reference_location_end(struct snapshot snapshot,
667	const char *refname,
668	int mustexist)
669	{
670	return find_reference_location_1(snapshot, refname, mustexist, 0);
671	}
672
673	/*
674	* Create a newly-allocated `snapshot` of the `packed-refs` file in
675	* its current state and return it. The return value will already have
676	* its reference count incremented.
677	*
678	* A comment line of the form "# pack-refs with: " may contain zero or
679	* more traits. We interpret the traits as follows:
680	*
681	* Neither `peeled` nor `fully-peeled`:
682	*
683	* Probably no references are peeled. But if the file contains a
684	* peeled value for a reference, we will use it.
685	*
686	* `peeled`:
687	*
688	* References under "refs/tags/", if they can be peeled, are
689	* peeled in this file. References outside of "refs/tags/" are
690	* probably not peeled even if they could have been, but if we find
691	* a peeled value for such a reference we will use it.
692	*
693	* `fully-peeled`:
694	*
695	* All references in the file that can be peeled are peeled.
696	* Inversely (and this is more important), any references in the
697	* file for which no peeled value is recorded is not peelable. This
698	* trait should typically be written alongside "peeled" for
699	* compatibility with older clients, but we do not require it
700	* (i.e., "peeled" is a no-op if "fully-peeled" is set).
701	*
702	* `sorted`:
703	*
704	* The references in this file are known to be sorted by refname.
705	*/
706	static struct snapshot create_snapshot(struct packed_ref_store refs)
707	{
708	struct snapshot snapshot = xcalloc(1, sizeof(snapshot));
709	int sorted = 0;
710
711	snapshot->refs = refs;
712	acquire_snapshot(snapshot);
713	snapshot->peeled = PEELED_NONE;
714
715	if (!load_contents(snapshot))
716	return snapshot;
717
718	/* If the file has a header line, process it: */
719	if (snapshot->buf < snapshot->eof && *snapshot->buf == '#') {
720	char tmp, p, *eol;
721	struct string_list traits = STRING_LIST_INIT_NODUP;
722
723	eol = memchr(snapshot->buf, '\n',
724	snapshot->eof - snapshot->buf);
725	if (!eol)
726	die_unterminated_line(refs->path,
727	snapshot->buf,
728	snapshot->eof - snapshot->buf);
729
730	tmp = xmemdupz(snapshot->buf, eol - snapshot->buf);
731
732	if (!skip_prefix(tmp, "# pack-refs with: ", (const char **)&p))
733	die_invalid_line(refs->path,
734	snapshot->buf,
735	snapshot->eof - snapshot->buf);
736
737	string_list_split_in_place(&traits, p, " ", -1);
738
739	if (unsorted_string_list_has_string(&traits, "fully-peeled"))
740	snapshot->peeled = PEELED_FULLY;
741	else if (unsorted_string_list_has_string(&traits, "peeled"))
742	snapshot->peeled = PEELED_TAGS;
743
744	sorted = unsorted_string_list_has_string(&traits, "sorted");
745
746	/* perhaps other traits later as well */
747
748	/* The "+ 1" is for the LF character. */
749	snapshot->start = eol + 1;
750
751	string_list_clear(&traits, 0);
752	free(tmp);
753	}
754
755	verify_buffer_safe(snapshot);
756
757	if (!sorted) {
758	sort_snapshot(snapshot);
759
760	/*
761	* Reordering the records might have moved a short one
762	* to the end of the buffer, so verify the buffer's
763	* safety again:
764	*/
765	verify_buffer_safe(snapshot);
766	}
767
768	if (mmap_strategy != MMAP_OK && snapshot->mmapped) {
769	/*
770	* We don't want to leave the file mmapped, so we are
771	* forced to make a copy now:
772	*/
773	size_t size = snapshot->eof - snapshot->start;
774	char *buf_copy = xmalloc(size);
775
776	memcpy(buf_copy, snapshot->start, size);
777	clear_snapshot_buffer(snapshot);
778	snapshot->buf = snapshot->start = buf_copy;
779	snapshot->eof = buf_copy + size;
780	}
781
782	return snapshot;
783	}
784
785	/*
786	* Check that `refs->snapshot` (if present) still reflects the
787	* contents of the `packed-refs` file. If not, clear the snapshot.
788	*/
789	static void validate_snapshot(struct packed_ref_store *refs)
790	{
791	if (refs->snapshot &&
792	!stat_validity_check(&refs->snapshot->validity, refs->path))
793	clear_snapshot(refs);
794	}
795
796	/*
797	* Get the `snapshot` for the specified packed_ref_store, creating and
798	* populating it if it hasn't been read before or if the file has been
799	* changed (according to its `validity` field) since it was last read.
800	* On the other hand, if we hold the lock, then assume that the file
801	* hasn't been changed out from under us, so skip the extra `stat()`
802	* call in `stat_validity_check()`. This function does not increase
803	* the snapshot's reference count on behalf of the caller.
804	*/
805	static struct snapshot get_snapshot(struct packed_ref_store refs)
806	{
807	if (!is_lock_file_locked(&refs->lock))
808	validate_snapshot(refs);
809
810	if (!refs->snapshot)
811	refs->snapshot = create_snapshot(refs);
812
813	return refs->snapshot;
814	}
815
816	static int packed_read_raw_ref(struct ref_store ref_store, const char refname,
817	struct object_id oid, struct strbuf referent UNUSED,
818	unsigned int type, int failure_errno)
819	{
820	struct packed_ref_store *refs =
821	packed_downcast(ref_store, REF_STORE_READ, "read_raw_ref");
822	struct snapshot *snapshot = get_snapshot(refs);
823	const char *rec;
824
825	*type = 0;
826
827	rec = find_reference_location(snapshot, refname, 1);
828
829	if (!rec) {
830	/* refname is not a packed reference. */
831	*failure_errno = ENOENT;
832	return -1;
833	}
834
835	if (get_oid_hex_algop(rec, oid, ref_store->repo->hash_algo))
836	die_invalid_line(refs->path, rec, snapshot->eof - rec);
837
838	*type = REF_ISPACKED;
839	return 0;
840	}
841
842	/*
843	* This value is set in `base.flags` if the peeled value of the
844	* current reference is known. In that case, `peeled` contains the
845	* correct peeled value for the reference, which might be `null_oid`
846	* if the reference is not a tag or if it is broken.
847	*/
848	#define REF_KNOWS_PEELED 0x40
849
850	/*
851	* An iterator over a snapshot of a `packed-refs` file.
852	*/
853	struct packed_ref_iterator {
854	struct ref_iterator base;
855
856	struct snapshot *snapshot;
857
858	char *prefix;
859
860	/* The current position in the snapshot's buffer: */
861	const char *pos;
862
863	/* The end of the part of the buffer that will be iterated over: */
864	const char *eof;
865
866	struct jump_list_entry {
867	const char *start;
868	const char *end;
869	} *jump;
870	size_t jump_nr, jump_alloc;
871	size_t jump_cur;
872
873	/* Scratch space for current values: */
874	struct object_id oid, peeled;
875	struct strbuf refname_buf;
876
877	struct repository *repo;
878	unsigned int flags;
879	};
880
881	/*
882	* Move the iterator to the next record in the snapshot. Adjust the fields in
883	* `iter` and return `ITER_OK` or `ITER_DONE`. This function does not free the
884	* iterator in the case of `ITER_DONE`.
885	*/
886	static int next_record(struct packed_ref_iterator *iter)
887	{
888	const char p, eol;
889
890	memset(&iter->base.ref, 0, sizeof(iter->base.ref));
891	strbuf_reset(&iter->refname_buf);
892
893	/*
894	* If iter->pos is contained within a skipped region, jump past
895	* it.
896	*
897	* Note that each skipped region is considered at most once,
898	* since they are ordered based on their starting position.
899	*/
900	while (iter->jump_cur < iter->jump_nr) {
901	struct jump_list_entry *curr = &iter->jump[iter->jump_cur];
902	if (iter->pos < curr->start)
903	break; /* not to the next jump yet */
904
905	iter->jump_cur++;
906	if (iter->pos < curr->end) {
907	iter->pos = curr->end;
908	trace2_counter_add(TRACE2_COUNTER_ID_PACKED_REFS_JUMPS, 1);
909	/* jumps are coalesced, so only one jump is necessary */
910	break;
911	}
912	}
913
914	if (iter->pos == iter->eof)
915	return ITER_DONE;
916
917	iter->base.ref.flags = REF_ISPACKED;
918	p = iter->pos;
919
920	if (iter->eof - p < snapshot_hexsz(iter->snapshot) + 2 \|\|
921	parse_oid_hex_algop(p, &iter->oid, &p, iter->repo->hash_algo) \|\|
922	!isspace(*p++))
923	die_invalid_line(iter->snapshot->refs->path,
924	iter->pos, iter->eof - iter->pos);
925	iter->base.ref.oid = &iter->oid;
926
927	eol = memchr(p, '\n', iter->eof - p);
928	if (!eol)
929	die_unterminated_line(iter->snapshot->refs->path,
930	iter->pos, iter->eof - iter->pos);
931
932	strbuf_add(&iter->refname_buf, p, eol - p);
933	iter->base.ref.name = iter->refname_buf.buf;
934
935	if (refname_contains_nul(&iter->refname_buf))
936	die("packed refname contains embedded NULL: %s", iter->base.ref.name);
937
938	if (check_refname_format(iter->base.ref.name, REFNAME_ALLOW_ONELEVEL)) {
939	if (!refname_is_safe(iter->base.ref.name))
940	die("packed refname is dangerous: %s",
941	iter->base.ref.name);
942	oidclr(&iter->oid, iter->repo->hash_algo);
943	iter->base.ref.flags \|= REF_BAD_NAME \| REF_ISBROKEN;
944	}
945	if (iter->snapshot->peeled == PEELED_FULLY \|\|
946	(iter->snapshot->peeled == PEELED_TAGS &&
947	starts_with(iter->base.ref.name, "refs/tags/")))
948	iter->base.ref.flags \|= REF_KNOWS_PEELED;
949
950	iter->pos = eol + 1;
951
952	if (iter->pos < iter->eof && *iter->pos == '^') {
953	p = iter->pos + 1;
954	if (iter->eof - p < snapshot_hexsz(iter->snapshot) + 1 \|\|
955	parse_oid_hex_algop(p, &iter->peeled, &p, iter->repo->hash_algo) \|\|
956	*p++ != '\n')
957	die_invalid_line(iter->snapshot->refs->path,
958	iter->pos, iter->eof - iter->pos);
959	iter->pos = p;
960
961	/*
962	* Regardless of what the file header said, we
963	* definitely know the value of this reference. But
964	* we suppress it if the reference is broken:
965	*/
966	if ((iter->base.ref.flags & REF_ISBROKEN)) {
967	oidclr(&iter->peeled, iter->repo->hash_algo);
968	iter->base.ref.flags &= ~REF_KNOWS_PEELED;
969	} else {
970	iter->base.ref.flags \|= REF_KNOWS_PEELED;
971	iter->base.ref.peeled_oid = &iter->peeled;
972	}
973	} else {
974	oidclr(&iter->peeled, iter->repo->hash_algo);
975	}
976
977	return ITER_OK;
978	}
979
980	static int packed_ref_iterator_advance(struct ref_iterator *ref_iterator)
981	{
982	struct packed_ref_iterator *iter =
983	(struct packed_ref_iterator *)ref_iterator;
984	int ok;
985
986	while ((ok = next_record(iter)) == ITER_OK) {
987	const char *refname = iter->base.ref.name;
988	const char *prefix = iter->prefix;
989
990	if (iter->flags & REFS_FOR_EACH_PER_WORKTREE_ONLY &&
991	!is_per_worktree_ref(iter->base.ref.name))
992	continue;
993
994	if (!(iter->flags & REFS_FOR_EACH_INCLUDE_BROKEN) &&
995	!ref_resolves_to_object(iter->base.ref.name, iter->repo,
996	&iter->oid, iter->flags))
997	continue;
998
999	while (prefix && *prefix) {
1000	if ((unsigned char)refname < (unsigned char)prefix)
1001	BUG("packed-refs backend yielded reference preceding its prefix");
1002	else if ((unsigned char)refname > (unsigned char)prefix)
1003	return ITER_DONE;
1004	prefix++;
1005	refname++;
1006	}
1007
1008	return ITER_OK;
1009	}
1010
1011	return ok;
1012	}
1013
1014	static int packed_ref_iterator_seek(struct ref_iterator *ref_iterator,
1015	const char *refname, unsigned int flags)
1016	{
1017	struct packed_ref_iterator *iter =
1018	(struct packed_ref_iterator *)ref_iterator;
1019	const char *start;
1020
1021	if (refname && *refname)
1022	start = find_reference_location(iter->snapshot, refname, 0);
1023	else
1024	start = iter->snapshot->start;
1025
1026	/* Unset any previously set prefix */
1027	FREE_AND_NULL(iter->prefix);
1028
1029	if (flags & REF_ITERATOR_SEEK_SET_PREFIX)
1030	iter->prefix = xstrdup_or_null(refname);
1031
1032	iter->pos = start;
1033	iter->eof = iter->snapshot->eof;
1034
1035	return 0;
1036	}
1037
1038	static void packed_ref_iterator_release(struct ref_iterator *ref_iterator)
1039	{
1040	struct packed_ref_iterator *iter =
1041	(struct packed_ref_iterator *)ref_iterator;
1042	strbuf_release(&iter->refname_buf);
1043	free(iter->jump);
1044	free(iter->prefix);
1045	release_snapshot(iter->snapshot);
1046	}
1047
1048	static struct ref_iterator_vtable packed_ref_iterator_vtable = {
1049	.advance = packed_ref_iterator_advance,
1050	.seek = packed_ref_iterator_seek,
1051	.release = packed_ref_iterator_release,
1052	};
1053
1054	static int jump_list_entry_cmp(const void va, const void vb)
1055	{
1056	const struct jump_list_entry *a = va;
1057	const struct jump_list_entry *b = vb;
1058
1059	if (a->start < b->start)
1060	return -1;
1061	if (a->start > b->start)
1062	return 1;
1063	return 0;
1064	}
1065
1066	static int has_glob_special(const char *str)
1067	{
1068	const char *p;
1069	for (p = str; *p; p++) {
1070	if (is_glob_special(*p))
1071	return 1;
1072	}
1073	return 0;
1074	}
1075
1076	static void populate_excluded_jump_list(struct packed_ref_iterator *iter,
1077	struct snapshot *snapshot,
1078	const char **excluded_patterns)
1079	{
1080	size_t i, j;
1081	const char **pattern;
1082	struct jump_list_entry *last_disjoint;
1083
1084	if (!excluded_patterns)
1085	return;
1086
1087	for (pattern = excluded_patterns; *pattern; pattern++) {
1088	struct jump_list_entry *e;
1089	const char start, end;
1090
1091	/*
1092	* We can't feed any excludes with globs in them to the
1093	* refs machinery. It only understands prefix matching.
1094	* We likewise can't even feed the string leading up to
1095	* the first meta-character, as something like "foo[a]"
1096	* should not exclude "foobar" (but the prefix "foo"
1097	* would match that and mark it for exclusion).
1098	*/
1099	if (has_glob_special(*pattern))
1100	continue;
1101
1102	start = find_reference_location(snapshot, *pattern, 0);
1103	end = find_reference_location_end(snapshot, *pattern, 0);
1104
1105	if (start == end)
1106	continue; /* nothing to jump over */
1107
1108	ALLOC_GROW(iter->jump, iter->jump_nr + 1, iter->jump_alloc);
1109
1110	e = &iter->jump[iter->jump_nr++];
1111	e->start = start;
1112	e->end = end;
1113	}
1114
1115	if (!iter->jump_nr) {
1116	/*
1117	* Every entry in exclude_patterns has a meta-character,
1118	* nothing to do here.
1119	*/
1120	return;
1121	}
1122
1123	QSORT(iter->jump, iter->jump_nr, jump_list_entry_cmp);
1124
1125	/*
1126	* As an optimization, merge adjacent entries in the jump list
1127	* to jump forwards as far as possible when entering a skipped
1128	* region.
1129	*
1130	* For example, if we have two skipped regions:
1131	*
1132	* [[A, B], [B, C]]
1133	*
1134	* we want to combine that into a single entry jumping from A to
1135	* C.
1136	*/
1137	last_disjoint = iter->jump;
1138
1139	for (i = 1, j = 1; i < iter->jump_nr; i++) {
1140	struct jump_list_entry *ours = &iter->jump[i];
1141	if (ours->start <= last_disjoint->end) {
1142	/* overlapping regions extend the previous one */
1143	last_disjoint->end = last_disjoint->end > ours->end
1144	? last_disjoint->end : ours->end;
1145	} else {
1146	/* otherwise, insert a new region */
1147	iter->jump[j++] = *ours;
1148	last_disjoint = ours;
1149	}
1150	}
1151
1152	iter->jump_nr = j;
1153	iter->jump_cur = 0;
1154	}
1155
1156	static struct ref_iterator *packed_ref_iterator_begin(
1157	struct ref_store *ref_store,
1158	const char prefix, const char *exclude_patterns,
1159	unsigned int flags)
1160	{
1161	struct packed_ref_store *refs;
1162	struct snapshot *snapshot;
1163	struct packed_ref_iterator *iter;
1164	struct ref_iterator *ref_iterator;
1165	unsigned int required_flags = REF_STORE_READ;
1166
1167	if (!(flags & REFS_FOR_EACH_INCLUDE_BROKEN))
1168	required_flags \|= REF_STORE_ODB;
1169	refs = packed_downcast(ref_store, required_flags, "ref_iterator_begin");
1170
1171	/*
1172	* Note that `get_snapshot()` internally checks whether the
1173	* snapshot is up to date with what is on disk, and re-reads
1174	* it if not.
1175	*/
1176	snapshot = get_snapshot(refs);
1177
1178	CALLOC_ARRAY(iter, 1);
1179	ref_iterator = &iter->base;
1180	base_ref_iterator_init(ref_iterator, &packed_ref_iterator_vtable);
1181
1182	if (exclude_patterns)
1183	populate_excluded_jump_list(iter, snapshot, exclude_patterns);
1184
1185	iter->snapshot = snapshot;
1186	acquire_snapshot(snapshot);
1187	strbuf_init(&iter->refname_buf, 0);
1188	iter->repo = ref_store->repo;
1189	iter->flags = flags;
1190
1191	if (packed_ref_iterator_seek(&iter->base, prefix,
1192	REF_ITERATOR_SEEK_SET_PREFIX) < 0) {
1193	ref_iterator_free(&iter->base);
1194	return NULL;
1195	}
1196
1197	return ref_iterator;
1198	}
1199
1200	/*
1201	* Write an entry to the packed-refs file for the specified refname.
1202	* If peeled is non-NULL, write it as the entry's peeled value. On
1203	* error, return a nonzero value and leave errno set at the value left
1204	* by the failing call to `fprintf()`.
1205	*/
1206	static int write_packed_entry(FILE fh, const char refname,
1207	const struct object_id *oid,
1208	const struct object_id *peeled)
1209	{
1210	if (fprintf(fh, "%s %s\n", oid_to_hex(oid), refname) < 0 \|\|
1211	(peeled && fprintf(fh, "^%s\n", oid_to_hex(peeled)) < 0))
1212	return -1;
1213
1214	return 0;
1215	}
1216
1217	int packed_refs_lock(struct ref_store ref_store, int flags, struct strbuf err)
1218	{
1219	struct packed_ref_store *refs =
1220	packed_downcast(ref_store, REF_STORE_WRITE \| REF_STORE_MAIN,
1221	"packed_refs_lock");
1222	static int timeout_configured = 0;
1223	static int timeout_value = 1000;
1224
1225	if (!timeout_configured) {
1226	repo_config_get_int(the_repository, "core.packedrefstimeout", &timeout_value);
1227	timeout_configured = 1;
1228	}
1229
1230	/*
1231	* Note that we close the lockfile immediately because we
1232	* don't write new content to it, but rather to a separate
1233	* tempfile.
1234	*/
1235	if (hold_lock_file_for_update_timeout(
1236	&refs->lock,
1237	refs->path,
1238	flags, timeout_value) < 0) {
1239	unable_to_lock_message(refs->path, errno, err);
1240	return -1;
1241	}
1242
1243	if (close_lock_file_gently(&refs->lock)) {
1244	strbuf_addf(err, "unable to close %s: %s", refs->path, strerror(errno));
1245	rollback_lock_file(&refs->lock);
1246	return -1;
1247	}
1248
1249	/*
1250	* There is a stat-validity problem might cause `update-ref -d`
1251	* lost the newly commit of a ref, because a new `packed-refs`
1252	* file might has the same on-disk file attributes such as
1253	* timestamp, file size and inode value, but has a changed
1254	* ref value.
1255	*
1256	* This could happen with a very small chance when
1257	* `update-ref -d` is called and at the same time another
1258	* `pack-refs --all` process is running.
1259	*
1260	* Now that we hold the `packed-refs` lock, it is important
1261	* to make sure we could read the latest version of
1262	* `packed-refs` file no matter we have just mmap it or not.
1263	* So what need to do is clear the snapshot if we hold it
1264	* already.
1265	*/
1266	clear_snapshot(refs);
1267
1268	/*
1269	* Now make sure that the packed-refs file as it exists in the
1270	* locked state is loaded into the snapshot:
1271	*/
1272	get_snapshot(refs);
1273	return 0;
1274	}
1275
1276	void packed_refs_unlock(struct ref_store *ref_store)
1277	{
1278	struct packed_ref_store *refs = packed_downcast(
1279	ref_store,
1280	REF_STORE_READ \| REF_STORE_WRITE,
1281	"packed_refs_unlock");
1282
1283	if (!is_lock_file_locked(&refs->lock))
1284	BUG("packed_refs_unlock() called when not locked");
1285	rollback_lock_file(&refs->lock);
1286	}
1287
1288	int packed_refs_is_locked(struct ref_store *ref_store)
1289	{
1290	struct packed_ref_store *refs = packed_downcast(
1291	ref_store,
1292	REF_STORE_READ \| REF_STORE_WRITE,
1293	"packed_refs_is_locked");
1294
1295	return is_lock_file_locked(&refs->lock);
1296	}
1297
1298	int packed_refs_size(struct ref_store *ref_store,
1299	size_t *out)
1300	{
1301	struct packed_ref_store *refs = packed_downcast(ref_store, REF_STORE_READ,
1302	"packed_refs_size");
1303	struct stat st;
1304
1305	if (stat(refs->path, &st) < 0) {
1306	if (errno != ENOENT)
1307	return -1;
1308	*out = 0;
1309	return 0;
1310	}
1311
1312	*out = st.st_size;
1313	return 0;
1314	}
1315
1316	/*
1317	* The packed-refs header line that we write out. Perhaps other traits
1318	* will be added later.
1319	*
1320	* Note that earlier versions of Git used to parse these traits by
1321	* looking for " trait " in the line. For this reason, the space after
1322	* the colon and the trailing space are required.
1323	*/
1324	static const char PACKED_REFS_HEADER[] =
1325	"# pack-refs with: peeled fully-peeled sorted \n";
1326
1327	static int packed_ref_store_create_on_disk(struct ref_store *ref_store UNUSED,
1328	int flags UNUSED,
1329	struct strbuf *err UNUSED)
1330	{
1331	/* Nothing to do. */
1332	return 0;
1333	}
1334
1335	static int packed_ref_store_remove_on_disk(struct ref_store *ref_store,
1336	struct strbuf *err)
1337	{
1338	struct packed_ref_store *refs = packed_downcast(ref_store, 0, "remove");
1339
1340	if (remove_path(refs->path) < 0) {
1341	strbuf_addstr(err, "could not delete packed-refs");
1342	return -1;
1343	}
1344
1345	return 0;
1346	}
1347
1348	/*
1349	* Write the packed refs from the current snapshot to the packed-refs
1350	* tempfile, incorporating any changes from `updates`. `updates` must
1351	* be a sorted string list whose keys are the refnames and whose util
1352	* values are `struct ref_update *`. On error, rollback the tempfile,
1353	* write an error message to `err`, and return a nonzero value.
1354	*
1355	* The packfile must be locked before calling this function and will
1356	* remain locked when it is done.
1357	*/
1358	static enum ref_transaction_error write_with_updates(struct packed_ref_store *refs,
1359	struct ref_transaction *transaction,
1360	struct strbuf *err)
1361	{
1362	enum ref_transaction_error ret = REF_TRANSACTION_ERROR_GENERIC;
1363	struct string_list *updates = &transaction->refnames;
1364	struct ref_iterator *iter = NULL;
1365	size_t i;
1366	int ok;
1367	FILE *out;
1368	struct strbuf sb = STRBUF_INIT;
1369	char *packed_refs_path;
1370
1371	if (!is_lock_file_locked(&refs->lock))
1372	BUG("write_with_updates() called while unlocked");
1373
1374	/*
1375	* If packed-refs is a symlink, we want to overwrite the
1376	* symlinked-to file, not the symlink itself. Also, put the
1377	* staging file next to it:
1378	*/
1379	packed_refs_path = get_locked_file_path(&refs->lock);
1380	strbuf_addf(&sb, "%s.new", packed_refs_path);
1381	free(packed_refs_path);
1382	refs->tempfile = create_tempfile(sb.buf);
1383	if (!refs->tempfile) {
1384	strbuf_addf(err, "unable to create file %s: %s",
1385	sb.buf, strerror(errno));
1386	strbuf_release(&sb);
1387	return REF_TRANSACTION_ERROR_GENERIC;
1388	}
1389	strbuf_release(&sb);
1390
1391	out = fdopen_tempfile(refs->tempfile, "w");
1392	if (!out) {
1393	strbuf_addf(err, "unable to fdopen packed-refs tempfile: %s",
1394	strerror(errno));
1395	goto error;
1396	}
1397
1398	if (fprintf(out, "%s", PACKED_REFS_HEADER) < 0)
1399	goto write_error;
1400
1401	/*
1402	* We iterate in parallel through the current list of refs and
1403	* the list of updates, processing an entry from at least one
1404	* of the lists each time through the loop. When the current
1405	* list of refs is exhausted, set iter to NULL. When the list
1406	* of updates is exhausted, leave i set to updates->nr.
1407	*/
1408	iter = packed_ref_iterator_begin(&refs->base, "", NULL,
1409	REFS_FOR_EACH_INCLUDE_BROKEN);
1410	if ((ok = ref_iterator_advance(iter)) != ITER_OK) {
1411	ref_iterator_free(iter);
1412	iter = NULL;
1413	}
1414
1415	i = 0;
1416
1417	while (iter \|\| i < updates->nr) {
1418	struct ref_update *update = NULL;
1419	int cmp;
1420
1421	if (i >= updates->nr) {
1422	cmp = -1;
1423	} else {
1424	update = updates->items[i].util;
1425
1426	if (!iter)
1427	cmp = +1;
1428	else
1429	cmp = strcmp(iter->ref.name, update->refname);
1430	}
1431
1432	if (!cmp) {
1433	/*
1434	* There is both an old value and an update
1435	* for this reference. Check the old value if
1436	* necessary:
1437	*/
1438	if ((update->flags & REF_HAVE_OLD)) {
1439	if (is_null_oid(&update->old_oid)) {
1440	strbuf_addf(err, "cannot update ref '%s': "
1441	"reference already exists",
1442	update->refname);
1443	ret = REF_TRANSACTION_ERROR_CREATE_EXISTS;
1444
1445	if (ref_transaction_maybe_set_rejected(transaction, i,
1446	ret, err)) {
1447	ret = 0;
1448	continue;
1449	}
1450
1451	goto error;
1452	} else if (!oideq(&update->old_oid, iter->ref.oid)) {
1453	strbuf_addf(err, "cannot update ref '%s': "
1454	"is at %s but expected %s",
1455	update->refname,
1456	oid_to_hex(iter->ref.oid),
1457	oid_to_hex(&update->old_oid));
1458	ret = REF_TRANSACTION_ERROR_INCORRECT_OLD_VALUE;
1459
1460	if (ref_transaction_maybe_set_rejected(transaction, i,
1461	ret, err)) {
1462	ret = 0;
1463	continue;
1464	}
1465
1466	goto error;
1467	}
1468	}
1469
1470	/* Now figure out what to use for the new value: */
1471	if ((update->flags & REF_HAVE_NEW)) {
1472	/*
1473	* The update takes precedence. Skip
1474	* the iterator over the unneeded
1475	* value.
1476	*/
1477	if ((ok = ref_iterator_advance(iter)) != ITER_OK) {
1478	ref_iterator_free(iter);
1479	iter = NULL;
1480	}
1481	cmp = +1;
1482	} else {
1483	/*
1484	* The update doesn't actually want to
1485	* change anything. We're done with it.
1486	*/
1487	i++;
1488	cmp = -1;
1489	}
1490	} else if (cmp > 0) {
1491	/*
1492	* There is no old value but there is an
1493	* update for this reference. Make sure that
1494	* the update didn't expect an existing value:
1495	*/
1496	if ((update->flags & REF_HAVE_OLD) &&
1497	!is_null_oid(&update->old_oid)) {
1498	strbuf_addf(err, "cannot update ref '%s': "
1499	"reference is missing but expected %s",
1500	update->refname,
1501	oid_to_hex(&update->old_oid));
1502	ret = REF_TRANSACTION_ERROR_NONEXISTENT_REF;
1503
1504	if (ref_transaction_maybe_set_rejected(transaction, i,
1505	ret, err)) {
1506	ret = 0;
1507	continue;
1508	}
1509
1510	goto error;
1511	}
1512	}
1513
1514	if (cmp < 0) {
1515	/* Pass the old reference through. */
1516	if (write_packed_entry(out, iter->ref.name,
1517	iter->ref.oid, iter->ref.peeled_oid))
1518	goto write_error;
1519
1520	if ((ok = ref_iterator_advance(iter)) != ITER_OK) {
1521	ref_iterator_free(iter);
1522	iter = NULL;
1523	}
1524	} else if (is_null_oid(&update->new_oid)) {
1525	/*
1526	* The update wants to delete the reference,
1527	* and the reference either didn't exist or we
1528	* have already skipped it. So we're done with
1529	* the update (and don't have to write
1530	* anything).
1531	*/
1532	i++;
1533	} else {
1534	bool peeled = update->flags & REF_HAVE_PEELED;
1535
1536	if (write_packed_entry(out, update->refname,
1537	&update->new_oid,
1538	peeled ? &update->peeled : NULL))
1539	goto write_error;
1540
1541	i++;
1542	}
1543	}
1544
1545	if (ok != ITER_DONE) {
1546	strbuf_addstr(err, "unable to write packed-refs file: "
1547	"error iterating over old contents");
1548	goto error;
1549	}
1550
1551	if (fflush(out) \|\|
1552	fsync_component(FSYNC_COMPONENT_REFERENCE, get_tempfile_fd(refs->tempfile)) \|\|
1553	close_tempfile_gently(refs->tempfile)) {
1554	strbuf_addf(err, "error closing file %s: %s",
1555	get_tempfile_path(refs->tempfile),
1556	strerror(errno));
1557	strbuf_release(&sb);
1558	delete_tempfile(&refs->tempfile);
1559	return REF_TRANSACTION_ERROR_GENERIC;
1560	}
1561
1562	return 0;
1563
1564	write_error:
1565	strbuf_addf(err, "error writing to %s: %s",
1566	get_tempfile_path(refs->tempfile), strerror(errno));
1567	ret = REF_TRANSACTION_ERROR_GENERIC;
1568
1569	error:
1570	ref_iterator_free(iter);
1571	delete_tempfile(&refs->tempfile);
1572	return ret;
1573	}
1574
1575	int is_packed_transaction_needed(struct ref_store *ref_store,
1576	struct ref_transaction *transaction)
1577	{
1578	struct packed_ref_store *refs = packed_downcast(
1579	ref_store,
1580	REF_STORE_READ,
1581	"is_packed_transaction_needed");
1582	struct strbuf referent = STRBUF_INIT;
1583	size_t i;
1584	int ret;
1585
1586	if (!is_lock_file_locked(&refs->lock))
1587	BUG("is_packed_transaction_needed() called while unlocked");
1588
1589	/*
1590	* We're only going to bother returning false for the common,
1591	* trivial case that references are only being deleted, their
1592	* old values are not being checked, and the old `packed-refs`
1593	* file doesn't contain any of those reference(s). This gives
1594	* false positives for some other cases that could
1595	* theoretically be optimized away:
1596	*
1597	* 1. It could be that the old value is being verified without
1598	* setting a new value. In this case, we could verify the
1599	* old value here and skip the update if it agrees. If it
1600	* disagrees, we could either let the update go through
1601	* (the actual commit would re-detect and report the
1602	* problem), or come up with a way of reporting such an
1603	* error to our caller.
1604	*
1605	* 2. It could be that a new value is being set, but that it
1606	* is identical to the current packed value of the
1607	* reference.
1608	*
1609	* Neither of these cases will come up in the current code,
1610	* because the only caller of this function passes to it a
1611	* transaction that only includes `delete` updates with no
1612	* `old_id`. Even if that ever changes, false positives only
1613	* cause an optimization to be missed; they do not affect
1614	* correctness.
1615	*/
1616
1617	/*
1618	* Start with the cheap checks that don't require old
1619	* reference values to be read:
1620	*/
1621	for (i = 0; i < transaction->nr; i++) {
1622	struct ref_update *update = transaction->updates[i];
1623
1624	if (update->flags & REF_HAVE_OLD)
1625	/* Have to check the old value -> needed. */
1626	return 1;
1627
1628	if ((update->flags & REF_HAVE_NEW) && !is_null_oid(&update->new_oid))
1629	/* Have to set a new value -> needed. */
1630	return 1;
1631	}
1632
1633	/*
1634	* The transaction isn't checking any old values nor is it
1635	* setting any nonzero new values, so it still might be able
1636	* to be skipped. Now do the more expensive check: the update
1637	* is needed if any of the updates is a delete, and the old
1638	* `packed-refs` file contains a value for that reference.
1639	*/
1640	ret = 0;
1641	for (i = 0; i < transaction->nr; i++) {
1642	struct ref_update *update = transaction->updates[i];
1643	int failure_errno;
1644	unsigned int type;
1645	struct object_id oid;
1646
1647	if (!(update->flags & REF_HAVE_NEW))
1648	/*
1649	* This reference isn't being deleted -> not
1650	* needed.
1651	*/
1652	continue;
1653
1654	if (!refs_read_raw_ref(ref_store, update->refname, &oid,
1655	&referent, &type, &failure_errno) \|\|
1656	failure_errno != ENOENT) {
1657	/*
1658	* We have to actually delete that reference
1659	* -> this transaction is needed.
1660	*/
1661	ret = 1;
1662	break;
1663	}
1664	}
1665
1666	strbuf_release(&referent);
1667	return ret;
1668	}
1669
1670	struct packed_transaction_backend_data {
1671	/* True iff the transaction owns the packed-refs lock. */
1672	int own_lock;
1673	};
1674
1675	static void packed_transaction_cleanup(struct packed_ref_store *refs,
1676	struct ref_transaction *transaction)
1677	{
1678	struct packed_transaction_backend_data *data = transaction->backend_data;
1679
1680	if (data) {
1681	if (is_tempfile_active(refs->tempfile))
1682	delete_tempfile(&refs->tempfile);
1683
1684	if (data->own_lock && is_lock_file_locked(&refs->lock)) {
1685	packed_refs_unlock(&refs->base);
1686	data->own_lock = 0;
1687	}
1688
1689	free(data);
1690	transaction->backend_data = NULL;
1691	}
1692
1693	transaction->state = REF_TRANSACTION_CLOSED;
1694	}
1695
1696	static int packed_transaction_prepare(struct ref_store *ref_store,
1697	struct ref_transaction *transaction,
1698	struct strbuf *err)
1699	{
1700	struct packed_ref_store *refs = packed_downcast(
1701	ref_store,
1702	REF_STORE_READ \| REF_STORE_WRITE \| REF_STORE_ODB,
1703	"ref_transaction_prepare");
1704	struct packed_transaction_backend_data *data;
1705	enum ref_transaction_error ret = REF_TRANSACTION_ERROR_GENERIC;
1706
1707	/*
1708	* Note that we don't skip transactions with zero updates,
1709	* because such a transaction might be executed for the side
1710	* effect of ensuring that all of the references are peeled or
1711	* ensuring that the `packed-refs` file is sorted. If the
1712	* caller wants to optimize away empty transactions, it should
1713	* do so itself.
1714	*/
1715
1716	CALLOC_ARRAY(data, 1);
1717
1718	transaction->backend_data = data;
1719
1720	if (!is_lock_file_locked(&refs->lock)) {
1721	if (packed_refs_lock(ref_store, 0, err))
1722	goto failure;
1723	data->own_lock = 1;
1724	}
1725
1726	ret = write_with_updates(refs, transaction, err);
1727	if (ret)
1728	goto failure;
1729
1730	transaction->state = REF_TRANSACTION_PREPARED;
1731	return 0;
1732
1733	failure:
1734	packed_transaction_cleanup(refs, transaction);
1735	return ret;
1736	}
1737
1738	static int packed_transaction_abort(struct ref_store *ref_store,
1739	struct ref_transaction *transaction,
1740	struct strbuf *err UNUSED)
1741	{
1742	struct packed_ref_store *refs = packed_downcast(
1743	ref_store,
1744	REF_STORE_READ \| REF_STORE_WRITE \| REF_STORE_ODB,
1745	"ref_transaction_abort");
1746
1747	packed_transaction_cleanup(refs, transaction);
1748	return 0;
1749	}
1750
1751	static int packed_transaction_finish(struct ref_store *ref_store,
1752	struct ref_transaction *transaction,
1753	struct strbuf *err)
1754	{
1755	struct packed_ref_store *refs = packed_downcast(
1756	ref_store,
1757	REF_STORE_READ \| REF_STORE_WRITE \| REF_STORE_ODB,
1758	"ref_transaction_finish");
1759	int ret = REF_TRANSACTION_ERROR_GENERIC;
1760	char *packed_refs_path;
1761
1762	clear_snapshot(refs);
1763
1764	packed_refs_path = get_locked_file_path(&refs->lock);
1765	if (rename_tempfile(&refs->tempfile, packed_refs_path)) {
1766	strbuf_addf(err, "error replacing %s: %s",
1767	refs->path, strerror(errno));
1768	goto cleanup;
1769	}
1770
1771	ret = 0;
1772
1773	cleanup:
1774	free(packed_refs_path);
1775	packed_transaction_cleanup(refs, transaction);
1776	return ret;
1777	}
1778
1779	static int packed_optimize(struct ref_store *ref_store UNUSED,
1780	struct refs_optimize_opts *opts UNUSED)
1781	{
1782	/*
1783	* Packed refs are already packed. It might be that loose refs
1784	* are packed into a packed refs store, but that is done by
1785	* updating the packed references via a transaction.
1786	*/
1787	return 0;
1788	}
1789
1790	static int packed_optimize_required(struct ref_store *ref_store UNUSED,
1791	struct refs_optimize_opts *opts UNUSED,
1792	bool *required)
1793	{
1794	/*
1795	* Packed refs are already optimized.
1796	*/
1797	*required = false;
1798	return 0;
1799	}
1800
1801	static struct ref_iterator packed_reflog_iterator_begin(struct ref_store ref_store UNUSED)
1802	{
1803	return empty_ref_iterator_begin();
1804	}
1805
1806	static int packed_fsck_ref_next_line(struct fsck_options *o,
1807	unsigned long line_number, const char *start,
1808	const char eof, const char *eol)
1809	{
1810	int ret = 0;
1811
1812	*eol = memchr(start, '\n', eof - start);
1813	if (!*eol) {
1814	struct strbuf packed_entry = STRBUF_INIT;
1815	struct fsck_ref_report report = { 0 };
1816
1817	strbuf_addf(&packed_entry, "packed-refs line %lu", line_number);
1818	report.path = packed_entry.buf;
1819	ret = fsck_report_ref(o, &report,
1820	FSCK_MSG_PACKED_REF_ENTRY_NOT_TERMINATED,
1821	"'%.*s' is not terminated with a newline",
1822	(int)(eof - start), start);
1823
1824	/*
1825	* There is no newline but we still want to parse it to the end of
1826	* the buffer.
1827	*/
1828	*eol = eof;
1829	strbuf_release(&packed_entry);
1830	}
1831
1832	return ret;
1833	}
1834
1835	static int packed_fsck_ref_header(struct fsck_options *o,
1836	const char start, const char eol,
1837	unsigned int *sorted)
1838	{
1839	struct string_list traits = STRING_LIST_INIT_NODUP;
1840	char *tmp_line;
1841	int ret = 0;
1842	char *p;
1843
1844	tmp_line = xmemdupz(start, eol - start);
1845	if (!skip_prefix(tmp_line, "# pack-refs with: ", (const char **)&p)) {
1846	struct fsck_ref_report report = { 0 };
1847	report.path = "packed-refs.header";
1848
1849	ret = fsck_report_ref(o, &report,
1850	FSCK_MSG_BAD_PACKED_REF_HEADER,
1851	"'%.*s' does not start with '# pack-refs with: '",
1852	(int)(eol - start), start);
1853	goto cleanup;
1854	}
1855
1856	string_list_split_in_place(&traits, p, " ", -1);
1857	*sorted = unsorted_string_list_has_string(&traits, "sorted");
1858
1859	cleanup:
1860	free(tmp_line);
1861	string_list_clear(&traits, 0);
1862	return ret;
1863	}
1864
1865	static int packed_fsck_ref_peeled_line(struct fsck_options *o,
1866	struct ref_store *ref_store,
1867	unsigned long line_number,
1868	const char start, const char eol)
1869	{
1870	struct strbuf packed_entry = STRBUF_INIT;
1871	struct fsck_ref_report report = { 0 };
1872	struct object_id peeled;
1873	const char *p;
1874	int ret = 0;
1875
1876	/*
1877	* Skip the '^' and parse the peeled oid.
1878	*/
1879	start++;
1880	if (parse_oid_hex_algop(start, &peeled, &p, ref_store->repo->hash_algo)) {
1881	strbuf_addf(&packed_entry, "packed-refs line %lu", line_number);
1882	report.path = packed_entry.buf;
1883
1884	ret = fsck_report_ref(o, &report,
1885	FSCK_MSG_BAD_PACKED_REF_ENTRY,
1886	"'%.*s' has invalid peeled oid",
1887	(int)(eol - start), start);
1888	goto cleanup;
1889	}
1890
1891	if (p != eol) {
1892	strbuf_addf(&packed_entry, "packed-refs line %lu", line_number);
1893	report.path = packed_entry.buf;
1894
1895	ret = fsck_report_ref(o, &report,
1896	FSCK_MSG_BAD_PACKED_REF_ENTRY,
1897	"has trailing garbage after peeled oid '%.*s'",
1898	(int)(eol - p), p);
1899	goto cleanup;
1900	}
1901
1902	cleanup:
1903	strbuf_release(&packed_entry);
1904	return ret;
1905	}
1906
1907	static int packed_fsck_ref_main_line(struct fsck_options *o,
1908	struct ref_store *ref_store,
1909	unsigned long line_number,
1910	struct strbuf *refname,
1911	const char start, const char eol)
1912	{
1913	struct strbuf packed_entry = STRBUF_INIT;
1914	struct fsck_ref_report report = { 0 };
1915	struct object_id oid;
1916	const char *p;
1917	int ret = 0;
1918
1919	if (parse_oid_hex_algop(start, &oid, &p, ref_store->repo->hash_algo)) {
1920	strbuf_addf(&packed_entry, "packed-refs line %lu", line_number);
1921	report.path = packed_entry.buf;
1922
1923	ret = fsck_report_ref(o, &report,
1924	FSCK_MSG_BAD_PACKED_REF_ENTRY,
1925	"'%.*s' has invalid oid",
1926	(int)(eol - start), start);
1927	goto cleanup;
1928	}
1929
1930	if (p == eol \|\| !isspace(*p)) {
1931	strbuf_addf(&packed_entry, "packed-refs line %lu", line_number);
1932	report.path = packed_entry.buf;
1933
1934	ret = fsck_report_ref(o, &report,
1935	FSCK_MSG_BAD_PACKED_REF_ENTRY,
1936	"has no space after oid '%s' but with '%.*s'",
1937	oid_to_hex(&oid), (int)(eol - p), p);
1938	goto cleanup;
1939	}
1940
1941	p++;
1942	strbuf_reset(refname);
1943	strbuf_add(refname, p, eol - p);
1944	if (refname_contains_nul(refname)) {
1945	strbuf_addf(&packed_entry, "packed-refs line %lu", line_number);
1946	report.path = packed_entry.buf;
1947
1948	ret = fsck_report_ref(o, &report,
1949	FSCK_MSG_BAD_PACKED_REF_ENTRY,
1950	"refname '%s' contains NULL binaries",
1951	refname->buf);
1952	}
1953
1954	if (check_refname_format(refname->buf, 0)) {
1955	strbuf_addf(&packed_entry, "packed-refs line %lu", line_number);
1956	report.path = packed_entry.buf;
1957
1958	ret = fsck_report_ref(o, &report,
1959	FSCK_MSG_BAD_REF_NAME,
1960	"has bad refname '%s'", refname->buf);
1961	}
1962
1963	cleanup:
1964	strbuf_release(&packed_entry);
1965	return ret;
1966	}
1967
1968	static int packed_fsck_ref_sorted(struct fsck_options *o,
1969	struct ref_store *ref_store,
1970	const char start, const char eof)
1971	{
1972	size_t hexsz = ref_store->repo->hash_algo->hexsz;
1973	struct strbuf packed_entry = STRBUF_INIT;
1974	struct fsck_ref_report report = { 0 };
1975	struct strbuf refname1 = STRBUF_INIT;
1976	struct strbuf refname2 = STRBUF_INIT;
1977	unsigned long line_number = 1;
1978	const char *former = NULL;
1979	const char *current;
1980	const char *eol;
1981	int ret = 0;
1982
1983	if (*start == '#') {
1984	eol = memchr(start, '\n', eof - start);
1985	start = eol + 1;
1986	line_number++;
1987	}
1988
1989	for (; start < eof; line_number++, start = eol + 1) {
1990	eol = memchr(start, '\n', eof - start);
1991
1992	if (*start == '^')
1993	continue;
1994
1995	if (!former) {
1996	former = start + hexsz + 1;
1997	continue;
1998	}
1999
2000	current = start + hexsz + 1;
2001	if (cmp_packed_refname(former, current) >= 0) {
2002	const char *err_fmt =
2003	"refname '%s' is less than previous refname '%s'";
2004
2005	eol = memchr(former, '\n', eof - former);
2006	strbuf_add(&refname1, former, eol - former);
2007	eol = memchr(current, '\n', eof - current);
2008	strbuf_add(&refname2, current, eol - current);
2009
2010	strbuf_addf(&packed_entry, "packed-refs line %lu", line_number);
2011	report.path = packed_entry.buf;
2012	ret = fsck_report_ref(o, &report,
2013	FSCK_MSG_PACKED_REF_UNSORTED,
2014	err_fmt, refname2.buf, refname1.buf);
2015	goto cleanup;
2016	}
2017	former = current;
2018	}
2019
2020	cleanup:
2021	strbuf_release(&packed_entry);
2022	strbuf_release(&refname1);
2023	strbuf_release(&refname2);
2024	return ret;
2025	}
2026
2027	static int packed_fsck_ref_content(struct fsck_options *o,
2028	struct ref_store *ref_store,
2029	unsigned int *sorted,
2030	const char start, const char eof)
2031	{
2032	struct strbuf refname = STRBUF_INIT;
2033	unsigned long line_number = 1;
2034	const char *eol;
2035	int ret = 0;
2036
2037	ret \|= packed_fsck_ref_next_line(o, line_number, start, eof, &eol);
2038	if (*start == '#') {
2039	ret \|= packed_fsck_ref_header(o, start, eol, sorted);
2040
2041	start = eol + 1;
2042	line_number++;
2043	}
2044
2045	while (start < eof) {
2046	ret \|= packed_fsck_ref_next_line(o, line_number, start, eof, &eol);
2047	ret \|= packed_fsck_ref_main_line(o, ref_store, line_number, &refname, start, eol);
2048	start = eol + 1;
2049	line_number++;
2050	if (start < eof && *start == '^') {
2051	ret \|= packed_fsck_ref_next_line(o, line_number, start, eof, &eol);
2052	ret \|= packed_fsck_ref_peeled_line(o, ref_store, line_number,
2053	start, eol);
2054	start = eol + 1;
2055	line_number++;
2056	}
2057	}
2058
2059	strbuf_release(&refname);
2060	return ret;
2061	}
2062
2063	static int packed_fsck(struct ref_store *ref_store,
2064	struct fsck_options *o,
2065	struct worktree *wt)
2066	{
2067	struct packed_ref_store *refs = packed_downcast(ref_store,
2068	REF_STORE_READ, "fsck");
2069	struct snapshot snapshot = { 0 };
2070	unsigned int sorted = 0;
2071	struct stat st;
2072	int ret = 0;
2073	int fd = -1;
2074
2075	if (!is_main_worktree(wt))
2076	goto cleanup;
2077
2078	if (o->verbose)
2079	fprintf_ln(stderr, "Checking packed-refs file %s", refs->path);
2080
2081	fd = open_nofollow(refs->path, O_RDONLY);
2082	if (fd < 0) {
2083	/*
2084	* If the packed-refs file doesn't exist, there's nothing
2085	* to check.
2086	*/
2087	if (errno == ENOENT)
2088	goto cleanup;
2089
2090	if (errno == ELOOP) {
2091	struct fsck_ref_report report = { 0 };
2092	report.path = "packed-refs";
2093	ret = fsck_report_ref(o, &report,
2094	FSCK_MSG_BAD_REF_FILETYPE,
2095	"not a regular file but a symlink");
2096	goto cleanup;
2097	}
2098
2099	ret = error_errno(_("unable to open '%s'"), refs->path);
2100	goto cleanup;
2101	} else if (fstat(fd, &st) < 0) {
2102	ret = error_errno(_("unable to stat '%s'"), refs->path);
2103	goto cleanup;
2104	} else if (!S_ISREG(st.st_mode)) {
2105	struct fsck_ref_report report = { 0 };
2106	report.path = "packed-refs";
2107	ret = fsck_report_ref(o, &report,
2108	FSCK_MSG_BAD_REF_FILETYPE,
2109	"not a regular file");
2110	goto cleanup;
2111	}
2112
2113	if (!allocate_snapshot_buffer(&snapshot, fd, &st)) {
2114	struct fsck_ref_report report = { 0 };
2115	report.path = "packed-refs";
2116	ret = fsck_report_ref(o, &report,
2117	FSCK_MSG_EMPTY_PACKED_REFS_FILE,
2118	"file is empty");
2119	goto cleanup;
2120	}
2121
2122	ret = packed_fsck_ref_content(o, ref_store, &sorted, snapshot.start,
2123	snapshot.eof);
2124	if (!ret && sorted)
2125	ret = packed_fsck_ref_sorted(o, ref_store, snapshot.start,
2126	snapshot.eof);
2127
2128	cleanup:
2129	if (fd >= 0)
2130	close(fd);
2131	clear_snapshot_buffer(&snapshot);
2132	return ret;
2133	}
2134
2135	struct ref_storage_be refs_be_packed = {
2136	.name = "packed",
2137	.init = packed_ref_store_init,
2138	.release = packed_ref_store_release,
2139	.create_on_disk = packed_ref_store_create_on_disk,
2140	.remove_on_disk = packed_ref_store_remove_on_disk,
2141
2142	.transaction_prepare = packed_transaction_prepare,
2143	.transaction_finish = packed_transaction_finish,
2144	.transaction_abort = packed_transaction_abort,
2145
2146	.optimize = packed_optimize,
2147	.optimize_required = packed_optimize_required,
2148
2149	.rename_ref = NULL,
2150	.copy_ref = NULL,
2151
2152	.iterator_begin = packed_ref_iterator_begin,
2153	.read_raw_ref = packed_read_raw_ref,
2154	.read_symbolic_ref = NULL,
2155
2156	.reflog_iterator_begin = packed_reflog_iterator_begin,
2157	.for_each_reflog_ent = NULL,
2158	.for_each_reflog_ent_reverse = NULL,
2159	.reflog_exists = NULL,
2160	.create_reflog = NULL,
2161	.delete_reflog = NULL,
2162	.reflog_expire = NULL,
2163
2164	.fsck = packed_fsck,
2165	};