{"thread":{"id":"46784","subject":"[PATCH v2 00/21] Read `packed-refs` using mmap()","startedAt":"2017-09-19T06:22:50Z","lastAt":"2017-09-25T15:55:34Z","messageCount":40,"participants":["Michael Haggerty","Johannes Schindelin","Jeff King","Stefan Beller","Junio C Hamano"],"isPatch":true,"patchVersion":2,"patchTotal":21},"messages":[{"id":"328347","messageId":"cover.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":null,"subject":"[PATCH v2 00/21] Read `packed-refs` using mmap()","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:08Z","receivedAt":"2017-09-19T06:22:50Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"This is v2 of a patch series that changes the reading and caching of\nthe `packed-refs` file to use `mmap()`. Thanks to Junio, Stefan, and\nJohannes for their comments about v1 [1].\n\nThe main change since v1 is to accommodate Windows, which doesn't let\nyou replace a file using `rename()` if the file is currently mmapped.\nThis is unfortunate, because it means that Windows will never get the\nO(N) → O(lg N) improvement for reading single references that more\ncapable systems can now enjoy.\n\nThe background was discussed on the mailing list [2]. The bottom line\nis that on Windows, keeping the `packed-refs` lock mmapped would be\ntantamount to holding reader lock on that file, preventing anybody\n(even unrelated processes) from changing the `packed-refs` file while\nit is mmapped. This is even worse than the situation for packfiles\n(which is solved using `close_all_packs()`), because a packfile, once\ncreated, never needs to be replaced—every packfile has a filename that\nis determined from its contents. The worst that can happen if a\npackfile is locked is that another process cannot remove it, but that\nis not critical for correctness. The `packed-refs` file, on the other\nhand, always has the same filename and needs to be overwritten for\ncorrectness.\n\nSo the approach taken here is that a new compile-time option,\n`MMAP_PREVENTS_DELETE`, is introduced. When this option is set, then\nthe `packed-refs` file is read quickly into memory then closed.\n\nEven in that case, though, this branch brings significant performance\nbenefits, because instead of parsing the whole file and storing it\ninto lots of little objects in a `ref_cache` (which also involves a\nlot of small memory allocations), we copy the verbatim contents of the\nfile into memory. Then we use the same binary search techniques to\nfind any references that we need to read, just as we would do if the\nfile were memory mapped. This means that we only have to fully parse\nthe references that we are interested in, and hardly have to allocate\nany additional memory.\n\nI did some more careful benchmarks of this code vs. Git 2.14.1 on a\nrepository that is not quite as pathological. The test repo has 110k\nreferences that are fully packed in a `packed-refs` file that has the\n`sorted` trait. The current version is compiled three ways:\n\n* `NO_MMAP=YesPlease`—prevents all use of `mmap()`. This variant is\n O(N) when reading a single reference.\n\n* `MMAP_PREVENTS_DELETE=YesPlease`—uses mmap for the initial read, but\n quickly copies the contents to heap-allocated memory and munmaps\n right away. This variant is also O(N) when reading a single\n reference.\n\n* default (mmap enabled)—the `packed-refs` file is kept mmapped for as\n long as it is in use.\n\nThe commands that I timed were as follows:\n\n# for-each-ref, warm cache:\n$ git -C lots-of-refs for-each-ref --format=\"%(objectname) %(refname)\" >/dev/null\n\n# rev-parse, warm cache (this command was run 10 times then the total\n# time divided by 10):\n$ git -C lots-of-refs rev-parse --verify refs/remotes/origin/pr/38733\n\n# rev-parse, cold cache (but git binary warm):\n$ sync ; sudo sh -c 'echo 3 >/proc/sys/vm/drop_caches'; git rev-parse v1.0.0; time git -C lots-of-refs rev-parse --verify refs/remotes/origin/pr/38733\n\n(Note that the `rev-parse` commands involve a handful of reference\nlookups as the argument is DWIMmed.)\n\nResults:\n\n for-each-ref rev-parse rev-parse\n warm cache warm cache cold cache\n ------------ ---------- ----------\nv2.14.1 92 ms 23.7 ms 30 ms\nNO_MMAP=YesPlease 83 ms 3.4 ms 10 ms\nMMAP_PREVENTS_DELETE=YesPlease 82 ms 3.5 ms 11 ms\ndefault (mmap enabled) 81 ms 0.8 ms 6 ms\n\nSo this branch is a little bit faster at iterating over all\nreferences, but it really has big advantages when looking up single\nreferences. The advantage is smaller if `NO_MMAP` or\n`MMAP_PREVENTS_DELETE` is set, but is still quite significant.\n\nThis branch is also available from my fork on GitHub as branch\n`mmap-packed-refs`.\n\nMy main uncertainties are:\n\n1. Does this code actually work on Windows?\n\n2. Did I implement the new compile-time option correctly? (I just\n cargo-culted some existing options.) Is there some existing option\n that I could piggy-back off of instead of adding a new one?\n\n3. Is a compile-time option sufficient, or would the `mmap()` option\n need to be configurable at runtime, or even tested at repository\n create time as is done for some other filesystem properties in\n `create_default_files()`?\n\nMichael\n\n[1] https://public-inbox.org/git/cover.1505319366.git.mhagger@alum.mit.edu/\n[2] https://public-inbox.org/git/alpine.DEB.2.21.1.1709142101560.4132@virtualbox/\n https://public-inbox.org/git/alpine.DEB.2.21.1.1709150012550.219280@virtualbox/\n[3] https://github.com/mhagger/git\n\nJeff King (1):\n prefix_ref_iterator: break when we leave the prefix\n\nMichael Haggerty (20):\n ref_iterator: keep track of whether the iterator output is ordered\n packed_ref_cache: add a backlink to the associated `packed_ref_store`\n die_unterminated_line(), die_invalid_line(): new functions\n read_packed_refs(): use mmap to read the `packed-refs` file\n read_packed_refs(): only check for a header at the top of the file\n read_packed_refs(): make parsing of the header line more robust\n read_packed_refs(): read references with minimal copying\n packed_ref_cache: remember the file-wide peeling state\n mmapped_ref_iterator: add iterator over a packed-refs file\n mmapped_ref_iterator_advance(): no peeled value for broken refs\n packed-backend.c: reorder some definitions\n packed_ref_cache: keep the `packed-refs` file mmapped if possible\n read_packed_refs(): ensure that references are ordered when read\n packed_ref_iterator_begin(): iterate using `mmapped_ref_iterator`\n packed_read_raw_ref(): read the reference from the mmapped buffer\n ref_store: implement `refs_peel_ref()` generically\n packed_ref_store: get rid of the `ref_cache` entirely\n ref_cache: remove support for storing peeled values\n mmapped_ref_iterator: inline into `packed_ref_iterator`\n packed-backend.c: rename a bunch of things and update comments\n\n Makefile | 10 +\n config.mak.uname | 3 +\n refs.c | 22 +-\n refs/files-backend.c | 54 +--\n refs/iterator.c | 47 ++-\n refs/packed-backend.c | 978 ++++++++++++++++++++++++++++++++++++++------------\n refs/ref-cache.c | 44 +--\n refs/ref-cache.h | 35 +-\n refs/refs-internal.h | 26 +-\n 9 files changed, 850 insertions(+), 369 deletions(-)\n\n-- \n2.14.1\n\n"},{"id":"328348","messageId":"2bb2e8ccb57eef8acbea5004167751a007a1bd2f.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"[PATCH v2 02/21] prefix_ref_iterator: break when we leave the prefix","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:10Z","receivedAt":"2017-09-19T06:22:52Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Jeff King \n\nIf the underlying iterator is ordered, then `prefix_ref_iterator` can\nstop as soon as it sees a refname that comes after the prefix. This\nwill rarely make a big difference now, because `ref_cache_iterator`\nonly iterates over the directory containing the prefix (and usually\nthe prefix will span a whole directory anyway). But if *hint, hint* a\nfuture reference backend doesn't itself know where to stop the\niteration, then this optimization will be a big win.\n\nNote that there is no guarantee that the underlying iterator doesn't\ninclude output preceding the prefix, so we have to skip over any\nunwanted references before we get to the ones that we want.\n\nSigned-off-by: Jeff King \nSigned-off-by: Michael Haggerty \n---\n refs/iterator.c | 32 +++++++++++++++++++++++++++++++-\n 1 file changed, 31 insertions(+), 1 deletion(-)\n\ndiff --git a/refs/iterator.c b/refs/iterator.c\nindex c475360f0a..bd35da4e62 100644\n--- a/refs/iterator.c\n+++ b/refs/iterator.c\n@@ -287,6 +287,20 @@ struct prefix_ref_iterator {\n \tint trim;\n };\n \n+/* Return -1, 0, 1 if refname is before, inside, or after the prefix. */\n+static int compare_prefix(const char *refname, const char *prefix)\n+{\n+\twhile (*prefix) {\n+\t\tif (*refname != *prefix)\n+\t\t\treturn ((unsigned char)*refname < (unsigned char)*prefix) ? -1 : +1;\n+\n+\t\trefname++;\n+\t\tprefix++;\n+\t}\n+\n+\treturn 0;\n+}\n+\n static int prefix_ref_iterator_advance(struct ref_iterator *ref_iterator)\n {\n \tstruct prefix_ref_iterator *iter =\n@@ -294,9 +308,25 @@ static int prefix_ref_iterator_advance(struct ref_iterator *ref_iterator)\n \tint ok;\n \n \twhile ((ok = ref_iterator_advance(iter->iter0)) == ITER_OK) {\n-\t\tif (!starts_with(iter->iter0->refname, iter->prefix))\n+\t\tint cmp = compare_prefix(iter->iter0->refname, iter->prefix);\n+\n+\t\tif (cmp < 0)\n \t\t\tcontinue;\n \n+\t\tif (cmp > 0) {\n+\t\t\t/*\n+\t\t\t * If the source iterator is ordered, then we\n+\t\t\t * can stop the iteration as soon as we see a\n+\t\t\t * refname that comes after the prefix:\n+\t\t\t */\n+\t\t\tif (iter->iter0->ordered) {\n+\t\t\t\tok = ref_iterator_abort(iter->iter0);\n+\t\t\t\tbreak;\n+\t\t\t} else {\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t}\n+\n \t\tif (iter->trim) {\n \t\t\t/*\n \t\t\t * It is nonsense to trim off characters that\n-- \n2.14.1\n\n"},{"id":"328349","messageId":"7d40a319b3c41577efee8ef9f5c426b7517751ba.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"[PATCH v2 04/21] die_unterminated_line(), die_invalid_line(): new functions","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:12Z","receivedAt":"2017-09-19T06:22:55Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Extract some helper functions for reporting errors. While we're at it,\nprevent them from spewing unlimited output to the terminal. These\nfunctions will soon have more callers.\n\nThese functions accept the problematic line as a `(ptr, len)` pair\nrather than a NUL-terminated string, and `die_invalid_line()` checks\nfor an EOL itself, because these calling conventions will be\nconvenient for future callers. (Efficiency is not a concern here\nbecause these functions are only ever called if the `packed-refs` file\nis corrupt.)\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 28 +++++++++++++++++++++++++---\n 1 file changed, 25 insertions(+), 3 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex a3d9210cb0..5c50c223ef 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -161,6 +161,29 @@ static const char *parse_ref_line(struct strbuf *line, struct object_id *oid)\n \treturn ref;\n }\n \n+static NORETURN void die_unterminated_line(const char *path,\n+\t\t\t\t\t const char *p, size_t len)\n+{\n+\tif (len < 80)\n+\t\tdie(\"unterminated line in %s: %.*s\", path, (int)len, p);\n+\telse\n+\t\tdie(\"unterminated line in %s: %.75s...\", path, p);\n+}\n+\n+static NORETURN void die_invalid_line(const char *path,\n+\t\t\t\t const char *p, size_t len)\n+{\n+\tconst char *eol = memchr(p, '\\n', len);\n+\n+\tif (!eol)\n+\t\tdie_unterminated_line(path, p, len);\n+\telse if (eol - p < 80)\n+\t\tdie(\"unexpected line in %s: %.*s\", path, (int)(eol - p), p);\n+\telse\n+\t\tdie(\"unexpected line in %s: %.75s...\", path, p);\n+\n+}\n+\n /*\n * Read from the `packed-refs` file into a newly-allocated\n * `packed_ref_cache` and return it. The return value will already\n@@ -227,7 +250,7 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \t\tconst char *traits;\n \n \t\tif (!line.len || line.buf[line.len - 1] != '\\n')\n-\t\t\tdie(\"unterminated line in %s: %s\", refs->path, line.buf);\n+\t\t\tdie_unterminated_line(refs->path, line.buf, line.len);\n \n \t\tif (skip_prefix(line.buf, \"# pack-refs with:\", &traits)) {\n \t\t\tif (strstr(traits, \" fully-peeled \"))\n@@ -266,8 +289,7 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \t\t\t */\n \t\t\tlast->flag |= REF_KNOWS_PEELED;\n \t\t} else {\n-\t\t\tstrbuf_setlen(&line, line.len - 1);\n-\t\t\tdie(\"unexpected line in %s: %s\", refs->path, line.buf);\n+\t\t\tdie_invalid_line(refs->path, line.buf, line.len);\n \t\t}\n \t}\n \n-- \n2.14.1\n\n"},{"id":"328350","messageId":"67c4bf861beb095a63e8db72f1d37d6bfac39cd0.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"[PATCH v2 05/21] read_packed_refs(): use mmap to read the `packed-refs` file","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:13Z","receivedAt":"2017-09-19T06:22:57Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"It's still done in a pretty stupid way, involving more data copying\nthan necessary. That will improve in future commits.\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 42 ++++++++++++++++++++++++++++++++----------\n 1 file changed, 32 insertions(+), 10 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 5c50c223ef..154abbd83a 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -215,8 +215,12 @@ static NORETURN void die_invalid_line(const char *path,\n */\n static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n {\n-\tFILE *f;\n \tstruct packed_ref_cache *packed_refs = xcalloc(1, sizeof(*packed_refs));\n+\tint fd;\n+\tstruct stat st;\n+\tsize_t size;\n+\tchar *buf;\n+\tconst char *pos, *eol, *eof;\n \tstruct ref_entry *last = NULL;\n \tstruct strbuf line = STRBUF_INIT;\n \tenum { PEELED_NONE, PEELED_TAGS, PEELED_FULLY } peeled = PEELED_NONE;\n@@ -227,8 +231,8 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \tpacked_refs->cache = create_ref_cache(NULL, NULL);\n \tpacked_refs->cache->root->flag &= ~REF_INCOMPLETE;\n \n-\tf = fopen(refs->path, \"r\");\n-\tif (!f) {\n+\tfd = open(refs->path, O_RDONLY);\n+\tif (fd < 0) {\n \t\tif (errno == ENOENT) {\n \t\t\t/*\n \t\t\t * This is OK; it just means that no\n@@ -241,16 +245,27 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \t\t}\n \t}\n \n-\tstat_validity_update(&packed_refs->validity, fileno(f));\n+\tstat_validity_update(&packed_refs->validity, fd);\n+\n+\tif (fstat(fd, &st) < 0)\n+\t\tdie_errno(\"couldn't stat %s\", refs->path);\n+\n+\tsize = xsize_t(st.st_size);\n+\tbuf = xmmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tpos = buf;\n+\teof = buf + size;\n \n \tdir = get_ref_dir(packed_refs->cache->root);\n-\twhile (strbuf_getwholeline(&line, f, '\\n') != EOF) {\n+\twhile (pos < eof) {\n \t\tstruct object_id oid;\n \t\tconst char *refname;\n \t\tconst char *traits;\n \n-\t\tif (!line.len || line.buf[line.len - 1] != '\\n')\n-\t\t\tdie_unterminated_line(refs->path, line.buf, line.len);\n+\t\teol = memchr(pos, '\\n', eof - pos);\n+\t\tif (!eol)\n+\t\t\tdie_unterminated_line(refs->path, pos, eof - pos);\n+\n+\t\tstrbuf_add(&line, pos, eol + 1 - pos);\n \n \t\tif (skip_prefix(line.buf, \"# pack-refs with:\", &traits)) {\n \t\t\tif (strstr(traits, \" fully-peeled \"))\n@@ -258,7 +273,7 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \t\t\telse if (strstr(traits, \" peeled \"))\n \t\t\t\tpeeled = PEELED_TAGS;\n \t\t\t/* perhaps other traits later as well */\n-\t\t\tcontinue;\n+\t\t\tgoto next_line;\n \t\t}\n \n \t\trefname = parse_ref_line(&line, &oid);\n@@ -291,11 +306,18 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \t\t} else {\n \t\t\tdie_invalid_line(refs->path, line.buf, line.len);\n \t\t}\n+\n+\tnext_line:\n+\t\t/* The \"+ 1\" is for the LF character. */\n+\t\tpos = eol + 1;\n+\t\tstrbuf_reset(&line);\n \t}\n \n-\tfclose(f);\n-\tstrbuf_release(&line);\n+\tif (munmap(buf, size))\n+\t\tdie_errno(\"error ummapping packed-refs file\");\n+\tclose(fd);\n \n+\tstrbuf_release(&line);\n \treturn packed_refs;\n }\n \n-- \n2.14.1\n\n"},{"id":"328351","messageId":"597241da13f62d51fefd3396bfbab22a8f633a56.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"[PATCH v2 08/21] read_packed_refs(): read references with minimal copying","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:16Z","receivedAt":"2017-09-19T06:23:00Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Instead of copying data from the `packed-refs` file one line at time\nand then processing it, process the data in place as much as possible.\n\nAlso, instead of processing one line per iteration of the main loop,\nprocess a reference line plus its corresponding peeled line (if\npresent) together.\n\nNote that this change slightly tightens up the parsing of the\n`parse-ref` file. Previously, the parser would have accepted multiple\n\"peeled\" lines for a single reference (ignoring all but the last one).\nNow it would reject that.\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 101 ++++++++++++++++++++------------------------------\n 1 file changed, 40 insertions(+), 61 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex a45e3ff92f..2b80f244c8 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -134,33 +134,6 @@ static void clear_packed_ref_cache(struct packed_ref_store *refs)\n \t}\n }\n \n-/* The length of a peeled reference line in packed-refs, including EOL: */\n-#define PEELED_LINE_LENGTH 42\n-\n-/*\n- * Parse one line from a packed-refs file. Write the SHA1 to sha1.\n- * Return a pointer to the refname within the line (null-terminated),\n- * or NULL if there was a problem.\n- */\n-static const char *parse_ref_line(struct strbuf *line, struct object_id *oid)\n-{\n-\tconst char *ref;\n-\n-\tif (parse_oid_hex(line->buf, oid, &ref) < 0)\n-\t\treturn NULL;\n-\tif (!isspace(*ref++))\n-\t\treturn NULL;\n-\n-\tif (isspace(*ref))\n-\t\treturn NULL;\n-\n-\tif (line->buf[line->len - 1] != '\\n')\n-\t\treturn NULL;\n-\tline->buf[--line->len] = 0;\n-\n-\treturn ref;\n-}\n-\n static NORETURN void die_unterminated_line(const char *path,\n \t\t\t\t\t const char *p, size_t len)\n {\n@@ -221,8 +194,7 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \tsize_t size;\n \tchar *buf;\n \tconst char *pos, *eol, *eof;\n-\tstruct ref_entry *last = NULL;\n-\tstruct strbuf line = STRBUF_INIT;\n+\tstruct strbuf tmp = STRBUF_INIT;\n \tenum { PEELED_NONE, PEELED_TAGS, PEELED_FULLY } peeled = PEELED_NONE;\n \tstruct ref_dir *dir;\n \n@@ -264,9 +236,9 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \t\tif (!eol)\n \t\t\tdie_unterminated_line(refs->path, pos, eof - pos);\n \n-\t\tstrbuf_add(&line, pos, eol - pos);\n+\t\tstrbuf_add(&tmp, pos, eol - pos);\n \n-\t\tif (!skip_prefix(line.buf, \"# pack-refs with:\", (const char **)&p))\n+\t\tif (!skip_prefix(tmp.buf, \"# pack-refs with:\", (const char **)&p))\n \t\t\tdie_invalid_line(refs->path, pos, eof - pos);\n \n \t\tstring_list_split_in_place(&traits, p, ' ', -1);\n@@ -281,61 +253,68 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \t\tpos = eol + 1;\n \n \t\tstring_list_clear(&traits, 0);\n-\t\tstrbuf_reset(&line);\n+\t\tstrbuf_reset(&tmp);\n \t}\n \n \tdir = get_ref_dir(packed_refs->cache->root);\n \twhile (pos < eof) {\n+\t\tconst char *p = pos;\n \t\tstruct object_id oid;\n \t\tconst char *refname;\n+\t\tint flag = REF_ISPACKED;\n+\t\tstruct ref_entry *entry = NULL;\n \n-\t\teol = memchr(pos, '\\n', eof - pos);\n+\t\tif (eof - pos < GIT_SHA1_HEXSZ + 2 ||\n+\t\t parse_oid_hex(p, &oid, &p) ||\n+\t\t !isspace(*p++))\n+\t\t\tdie_invalid_line(refs->path, pos, eof - pos);\n+\n+\t\teol = memchr(p, '\\n', eof - p);\n \t\tif (!eol)\n \t\t\tdie_unterminated_line(refs->path, pos, eof - pos);\n \n-\t\tstrbuf_add(&line, pos, eol + 1 - pos);\n+\t\tstrbuf_add(&tmp, p, eol - p);\n+\t\trefname = tmp.buf;\n+\n+\t\tif (check_refname_format(refname, REFNAME_ALLOW_ONELEVEL)) {\n+\t\t\tif (!refname_is_safe(refname))\n+\t\t\t\tdie(\"packed refname is dangerous: %s\", refname);\n+\t\t\toidclr(&oid);\n+\t\t\tflag |= REF_BAD_NAME | REF_ISBROKEN;\n+\t\t}\n+\t\tif (peeled == PEELED_FULLY ||\n+\t\t (peeled == PEELED_TAGS && starts_with(refname, \"refs/tags/\")))\n+\t\t\tflag |= REF_KNOWS_PEELED;\n+\t\tentry = create_ref_entry(refname, &oid, flag);\n+\t\tadd_ref_entry(dir, entry);\n \n-\t\trefname = parse_ref_line(&line, &oid);\n-\t\tif (refname) {\n-\t\t\tint flag = REF_ISPACKED;\n+\t\tpos = eol + 1;\n+\n+\t\tif (pos < eof && *pos == '^') {\n+\t\t\tp = pos + 1;\n+\t\t\tif (eof - p < GIT_SHA1_HEXSZ + 1 ||\n+\t\t\t parse_oid_hex(p, &entry->u.value.peeled, &p) ||\n+\t\t\t *p++ != '\\n')\n+\t\t\t\tdie_invalid_line(refs->path, pos, eof - pos);\n \n-\t\t\tif (check_refname_format(refname, REFNAME_ALLOW_ONELEVEL)) {\n-\t\t\t\tif (!refname_is_safe(refname))\n-\t\t\t\t\tdie(\"packed refname is dangerous: %s\", refname);\n-\t\t\t\toidclr(&oid);\n-\t\t\t\tflag |= REF_BAD_NAME | REF_ISBROKEN;\n-\t\t\t}\n-\t\t\tlast = create_ref_entry(refname, &oid, flag);\n-\t\t\tif (peeled == PEELED_FULLY ||\n-\t\t\t (peeled == PEELED_TAGS && starts_with(refname, \"refs/tags/\")))\n-\t\t\t\tlast->flag |= REF_KNOWS_PEELED;\n-\t\t\tadd_ref_entry(dir, last);\n-\t\t} else if (last &&\n-\t\t line.buf[0] == '^' &&\n-\t\t line.len == PEELED_LINE_LENGTH &&\n-\t\t line.buf[PEELED_LINE_LENGTH - 1] == '\\n' &&\n-\t\t !get_oid_hex(line.buf + 1, &oid)) {\n-\t\t\toidcpy(&last->u.value.peeled, &oid);\n \t\t\t/*\n \t\t\t * Regardless of what the file header said,\n \t\t\t * we definitely know the value of *this*\n \t\t\t * reference:\n \t\t\t */\n-\t\t\tlast->flag |= REF_KNOWS_PEELED;\n-\t\t} else {\n-\t\t\tdie_invalid_line(refs->path, line.buf, line.len);\n+\t\t\tentry->flag |= REF_KNOWS_PEELED;\n+\n+\t\t\tpos = p;\n \t\t}\n \n-\t\t/* The \"+ 1\" is for the LF character. */\n-\t\tpos = eol + 1;\n-\t\tstrbuf_reset(&line);\n+\t\tstrbuf_reset(&tmp);\n \t}\n \n \tif (munmap(buf, size))\n \t\tdie_errno(\"error ummapping packed-refs file\");\n \tclose(fd);\n \n-\tstrbuf_release(&line);\n+\tstrbuf_release(&tmp);\n \treturn packed_refs;\n }\n \n-- \n2.14.1\n\n"},{"id":"328352","messageId":"6b7c9b6bd4160635cc5bebf5c0d6e298f05d4af4.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"[PATCH v2 09/21] packed_ref_cache: remember the file-wide peeling state","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:17Z","receivedAt":"2017-09-19T06:23:03Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Rather than store the peeling state (i.e., the one defined by traits\nin the `packed-refs` file header line) in a local variable in\n`read_packed_refs()`, store it permanently in `packed_ref_cache`. This\nwill be needed when we stop reading all packed refs at once.\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 17 ++++++++++++-----\n 1 file changed, 12 insertions(+), 5 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 2b80f244c8..ae276f3445 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -18,6 +18,12 @@ struct packed_ref_cache {\n \n \tstruct ref_cache *cache;\n \n+\t/*\n+\t * What is the peeled state of this cache? (This is usually\n+\t * determined from the header of the \"packed-refs\" file.)\n+\t */\n+\tenum { PEELED_NONE, PEELED_TAGS, PEELED_FULLY } peeled;\n+\n \t/*\n \t * Count of references to the data structure in this instance,\n \t * including the pointer from files_ref_store::packed if any.\n@@ -195,13 +201,13 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \tchar *buf;\n \tconst char *pos, *eol, *eof;\n \tstruct strbuf tmp = STRBUF_INIT;\n-\tenum { PEELED_NONE, PEELED_TAGS, PEELED_FULLY } peeled = PEELED_NONE;\n \tstruct ref_dir *dir;\n \n \tpacked_refs->refs = refs;\n \tacquire_packed_ref_cache(packed_refs);\n \tpacked_refs->cache = create_ref_cache(NULL, NULL);\n \tpacked_refs->cache->root->flag &= ~REF_INCOMPLETE;\n+\tpacked_refs->peeled = PEELED_NONE;\n \n \tfd = open(refs->path, O_RDONLY);\n \tif (fd < 0) {\n@@ -244,9 +250,9 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \t\tstring_list_split_in_place(&traits, p, ' ', -1);\n \n \t\tif (unsorted_string_list_has_string(&traits, \"fully-peeled\"))\n-\t\t\tpeeled = PEELED_FULLY;\n+\t\t\tpacked_refs->peeled = PEELED_FULLY;\n \t\telse if (unsorted_string_list_has_string(&traits, \"peeled\"))\n-\t\t\tpeeled = PEELED_TAGS;\n+\t\t\tpacked_refs->peeled = PEELED_TAGS;\n \t\t/* perhaps other traits later as well */\n \n \t\t/* The \"+ 1\" is for the LF character. */\n@@ -282,8 +288,9 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \t\t\toidclr(&oid);\n \t\t\tflag |= REF_BAD_NAME | REF_ISBROKEN;\n \t\t}\n-\t\tif (peeled == PEELED_FULLY ||\n-\t\t (peeled == PEELED_TAGS && starts_with(refname, \"refs/tags/\")))\n+\t\tif (packed_refs->peeled == PEELED_FULLY ||\n+\t\t (packed_refs->peeled == PEELED_TAGS &&\n+\t\t starts_with(refname, \"refs/tags/\")))\n \t\t\tflag |= REF_KNOWS_PEELED;\n \t\tentry = create_ref_entry(refname, &oid, flag);\n \t\tadd_ref_entry(dir, entry);\n-- \n2.14.1\n\n"},{"id":"328353","messageId":"aab75b5a61b5b71248267d29c04254b60f4ae385.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"[PATCH v2 10/21] mmapped_ref_iterator: add iterator over a packed-refs file","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:18Z","receivedAt":"2017-09-19T06:23:04Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Add a new `mmapped_ref_iterator`, which can iterate over the\nreferences in an mmapped `packed-refs` file directly. Use this\niterator from `read_packed_refs()` to fill the packed refs cache.\n\nNote that we are not yet willing to promise that the new iterator\ngenerates its output in order. That doesn't matter for now, because\nthe packed refs cache doesn't care what order it is filled.\n\nThis change adds a lot of boilerplate without providing any obvious\nbenefits. The benefits will come soon, when we get rid of the\n`ref_cache` for packed references altogether.\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 207 ++++++++++++++++++++++++++++++++++++--------------\n 1 file changed, 152 insertions(+), 55 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex ae276f3445..312116a99d 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -163,6 +163,141 @@ static NORETURN void die_invalid_line(const char *path,\n \n }\n \n+/*\n+ * An iterator over a packed-refs file that is currently mmapped.\n+ */\n+struct mmapped_ref_iterator {\n+\tstruct ref_iterator base;\n+\n+\tstruct packed_ref_cache *packed_refs;\n+\n+\t/* The current position in the mmapped file: */\n+\tconst char *pos;\n+\n+\t/* The end of the mmapped file: */\n+\tconst char *eof;\n+\n+\tstruct object_id oid, peeled;\n+\n+\tstruct strbuf refname_buf;\n+};\n+\n+static int mmapped_ref_iterator_advance(struct ref_iterator *ref_iterator)\n+{\n+\tstruct mmapped_ref_iterator *iter =\n+\t\t(struct mmapped_ref_iterator *)ref_iterator;\n+\tconst char *p = iter->pos, *eol;\n+\n+\tstrbuf_reset(&iter->refname_buf);\n+\n+\tif (iter->pos == iter->eof)\n+\t\treturn ref_iterator_abort(ref_iterator);\n+\n+\titer->base.flags = REF_ISPACKED;\n+\n+\tif (iter->eof - p < GIT_SHA1_HEXSZ + 2 ||\n+\t parse_oid_hex(p, &iter->oid, &p) ||\n+\t !isspace(*p++))\n+\t\tdie_invalid_line(iter->packed_refs->refs->path,\n+\t\t\t\t iter->pos, iter->eof - iter->pos);\n+\n+\teol = memchr(p, '\\n', iter->eof - p);\n+\tif (!eol)\n+\t\tdie_unterminated_line(iter->packed_refs->refs->path,\n+\t\t\t\t iter->pos, iter->eof - iter->pos);\n+\n+\tstrbuf_add(&iter->refname_buf, p, eol - p);\n+\titer->base.refname = iter->refname_buf.buf;\n+\n+\tif (check_refname_format(iter->base.refname, REFNAME_ALLOW_ONELEVEL)) {\n+\t\tif (!refname_is_safe(iter->base.refname))\n+\t\t\tdie(\"packed refname is dangerous: %s\",\n+\t\t\t iter->base.refname);\n+\t\toidclr(&iter->oid);\n+\t\titer->base.flags |= REF_BAD_NAME | REF_ISBROKEN;\n+\t}\n+\tif (iter->packed_refs->peeled == PEELED_FULLY ||\n+\t (iter->packed_refs->peeled == PEELED_TAGS &&\n+\t starts_with(iter->base.refname, \"refs/tags/\")))\n+\t\titer->base.flags |= REF_KNOWS_PEELED;\n+\n+\titer->pos = eol + 1;\n+\n+\tif (iter->pos < iter->eof && *iter->pos == '^') {\n+\t\tp = iter->pos + 1;\n+\t\tif (iter->eof - p < GIT_SHA1_HEXSZ + 1 ||\n+\t\t parse_oid_hex(p, &iter->peeled, &p) ||\n+\t\t *p++ != '\\n')\n+\t\t\tdie_invalid_line(iter->packed_refs->refs->path,\n+\t\t\t\t\t iter->pos, iter->eof - iter->pos);\n+\t\titer->pos = p;\n+\n+\t\t/*\n+\t\t * Regardless of what the file header said, we\n+\t\t * definitely know the value of *this* reference:\n+\t\t */\n+\t\titer->base.flags |= REF_KNOWS_PEELED;\n+\t} else {\n+\t\toidclr(&iter->peeled);\n+\t}\n+\n+\treturn ITER_OK;\n+}\n+\n+static int mmapped_ref_iterator_peel(struct ref_iterator *ref_iterator,\n+\t\t\t\t struct object_id *peeled)\n+{\n+\tstruct mmapped_ref_iterator *iter =\n+\t\t(struct mmapped_ref_iterator *)ref_iterator;\n+\n+\tif ((iter->base.flags & REF_KNOWS_PEELED)) {\n+\t\toidcpy(peeled, &iter->peeled);\n+\t\treturn is_null_oid(&iter->peeled) ? -1 : 0;\n+\t} else if ((iter->base.flags & (REF_ISBROKEN | REF_ISSYMREF))) {\n+\t\treturn -1;\n+\t} else {\n+\t\treturn !!peel_object(iter->oid.hash, peeled->hash);\n+\t}\n+}\n+\n+static int mmapped_ref_iterator_abort(struct ref_iterator *ref_iterator)\n+{\n+\tstruct mmapped_ref_iterator *iter =\n+\t\t(struct mmapped_ref_iterator *)ref_iterator;\n+\n+\trelease_packed_ref_cache(iter->packed_refs);\n+\tstrbuf_release(&iter->refname_buf);\n+\tbase_ref_iterator_free(ref_iterator);\n+\treturn ITER_DONE;\n+}\n+\n+static struct ref_iterator_vtable mmapped_ref_iterator_vtable = {\n+\tmmapped_ref_iterator_advance,\n+\tmmapped_ref_iterator_peel,\n+\tmmapped_ref_iterator_abort\n+};\n+\n+struct ref_iterator *mmapped_ref_iterator_begin(\n+\t\tconst char *packed_refs_file,\n+\t\tstruct packed_ref_cache *packed_refs,\n+\t\tconst char *pos, const char *eof)\n+{\n+\tstruct mmapped_ref_iterator *iter = xcalloc(1, sizeof(*iter));\n+\tstruct ref_iterator *ref_iterator = &iter->base;\n+\n+\tbase_ref_iterator_init(ref_iterator, &mmapped_ref_iterator_vtable, 0);\n+\n+\titer->packed_refs = packed_refs;\n+\tacquire_packed_ref_cache(iter->packed_refs);\n+\titer->pos = pos;\n+\titer->eof = eof;\n+\tstrbuf_init(&iter->refname_buf, 0);\n+\n+\titer->base.oid = &iter->oid;\n+\n+\treturn ref_iterator;\n+}\n+\n /*\n * Read from the `packed-refs` file into a newly-allocated\n * `packed_ref_cache` and return it. The return value will already\n@@ -199,9 +334,10 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \tstruct stat st;\n \tsize_t size;\n \tchar *buf;\n-\tconst char *pos, *eol, *eof;\n-\tstruct strbuf tmp = STRBUF_INIT;\n+\tconst char *pos, *eof;\n \tstruct ref_dir *dir;\n+\tstruct ref_iterator *iter;\n+\tint ok;\n \n \tpacked_refs->refs = refs;\n \tacquire_packed_ref_cache(packed_refs);\n@@ -235,7 +371,9 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \n \t/* If the file has a header line, process it: */\n \tif (pos < eof && *pos == '#') {\n+\t\tstruct strbuf tmp = STRBUF_INIT;\n \t\tchar *p;\n+\t\tconst char *eol;\n \t\tstruct string_list traits = STRING_LIST_INIT_NODUP;\n \n \t\teol = memchr(pos, '\\n', eof - pos);\n@@ -259,69 +397,28 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \t\tpos = eol + 1;\n \n \t\tstring_list_clear(&traits, 0);\n-\t\tstrbuf_reset(&tmp);\n+\t\tstrbuf_release(&tmp);\n \t}\n \n \tdir = get_ref_dir(packed_refs->cache->root);\n-\twhile (pos < eof) {\n-\t\tconst char *p = pos;\n-\t\tstruct object_id oid;\n-\t\tconst char *refname;\n-\t\tint flag = REF_ISPACKED;\n-\t\tstruct ref_entry *entry = NULL;\n-\n-\t\tif (eof - pos < GIT_SHA1_HEXSZ + 2 ||\n-\t\t parse_oid_hex(p, &oid, &p) ||\n-\t\t !isspace(*p++))\n-\t\t\tdie_invalid_line(refs->path, pos, eof - pos);\n+\titer = mmapped_ref_iterator_begin(refs->path, packed_refs, pos, eof);\n+\twhile ((ok = ref_iterator_advance(iter)) == ITER_OK) {\n+\t\tstruct ref_entry *entry =\n+\t\t\tcreate_ref_entry(iter->refname, iter->oid, iter->flags);\n \n-\t\teol = memchr(p, '\\n', eof - p);\n-\t\tif (!eol)\n-\t\t\tdie_unterminated_line(refs->path, pos, eof - pos);\n-\n-\t\tstrbuf_add(&tmp, p, eol - p);\n-\t\trefname = tmp.buf;\n-\n-\t\tif (check_refname_format(refname, REFNAME_ALLOW_ONELEVEL)) {\n-\t\t\tif (!refname_is_safe(refname))\n-\t\t\t\tdie(\"packed refname is dangerous: %s\", refname);\n-\t\t\toidclr(&oid);\n-\t\t\tflag |= REF_BAD_NAME | REF_ISBROKEN;\n-\t\t}\n-\t\tif (packed_refs->peeled == PEELED_FULLY ||\n-\t\t (packed_refs->peeled == PEELED_TAGS &&\n-\t\t starts_with(refname, \"refs/tags/\")))\n-\t\t\tflag |= REF_KNOWS_PEELED;\n-\t\tentry = create_ref_entry(refname, &oid, flag);\n+\t\tif ((iter->flags & REF_KNOWS_PEELED))\n+\t\t\tref_iterator_peel(iter, &entry->u.value.peeled);\n \t\tadd_ref_entry(dir, entry);\n-\n-\t\tpos = eol + 1;\n-\n-\t\tif (pos < eof && *pos == '^') {\n-\t\t\tp = pos + 1;\n-\t\t\tif (eof - p < GIT_SHA1_HEXSZ + 1 ||\n-\t\t\t parse_oid_hex(p, &entry->u.value.peeled, &p) ||\n-\t\t\t *p++ != '\\n')\n-\t\t\t\tdie_invalid_line(refs->path, pos, eof - pos);\n-\n-\t\t\t/*\n-\t\t\t * Regardless of what the file header said,\n-\t\t\t * we definitely know the value of *this*\n-\t\t\t * reference:\n-\t\t\t */\n-\t\t\tentry->flag |= REF_KNOWS_PEELED;\n-\n-\t\t\tpos = p;\n-\t\t}\n-\n-\t\tstrbuf_reset(&tmp);\n \t}\n \n+\tif (ok != ITER_DONE)\n+\t\tdie(\"error reading packed-refs file %s\", refs->path);\n+\n \tif (munmap(buf, size))\n-\t\tdie_errno(\"error ummapping packed-refs file\");\n+\t\tdie_errno(\"error ummapping packed-refs file %s\", refs->path);\n+\n \tclose(fd);\n \n-\tstrbuf_release(&tmp);\n \treturn packed_refs;\n }\n \n-- \n2.14.1\n\n"},{"id":"328354","messageId":"d34d2cbde67e9ef0b0b11910de19c7f722c2314c.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"[PATCH v2 11/21] mmapped_ref_iterator_advance(): no peeled value for broken refs","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:19Z","receivedAt":"2017-09-19T06:23:06Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"If a reference is broken, suppress its peeled value.\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 10 ++++++++--\n 1 file changed, 8 insertions(+), 2 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 312116a99d..724c88631d 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -234,9 +234,15 @@ static int mmapped_ref_iterator_advance(struct ref_iterator *ref_iterator)\n \n \t\t/*\n \t\t * Regardless of what the file header said, we\n-\t\t * definitely know the value of *this* reference:\n+\t\t * definitely know the value of *this* reference. But\n+\t\t * we suppress it if the reference is broken:\n \t\t */\n-\t\titer->base.flags |= REF_KNOWS_PEELED;\n+\t\tif ((iter->base.flags & REF_ISBROKEN)) {\n+\t\t\toidclr(&iter->peeled);\n+\t\t\titer->base.flags &= ~REF_KNOWS_PEELED;\n+\t\t} else {\n+\t\t\titer->base.flags |= REF_KNOWS_PEELED;\n+\t\t}\n \t} else {\n \t\toidclr(&iter->peeled);\n \t}\n-- \n2.14.1\n\n"},{"id":"328355","messageId":"b00a80a8ee82c18dfa7e6120261945546f7ae97d.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"[PATCH v2 12/21] packed-backend.c: reorder some definitions","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:20Z","receivedAt":"2017-09-19T06:23:08Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"No code has been changed. This will make subsequent patches more\nself-contained.\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 48 ++++++++++++++++++++++++------------------------\n 1 file changed, 24 insertions(+), 24 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 724c88631d..0fe41a7203 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -36,30 +36,6 @@ struct packed_ref_cache {\n \tstruct stat_validity validity;\n };\n \n-/*\n- * Increment the reference count of *packed_refs.\n- */\n-static void acquire_packed_ref_cache(struct packed_ref_cache *packed_refs)\n-{\n-\tpacked_refs->referrers++;\n-}\n-\n-/*\n- * Decrease the reference count of *packed_refs. If it goes to zero,\n- * free *packed_refs and return true; otherwise return false.\n- */\n-static int release_packed_ref_cache(struct packed_ref_cache *packed_refs)\n-{\n-\tif (!--packed_refs->referrers) {\n-\t\tfree_ref_cache(packed_refs->cache);\n-\t\tstat_validity_clear(&packed_refs->validity);\n-\t\tfree(packed_refs);\n-\t\treturn 1;\n-\t} else {\n-\t\treturn 0;\n-\t}\n-}\n-\n /*\n * A container for `packed-refs`-related data. It is not (yet) a\n * `ref_store`.\n@@ -92,6 +68,30 @@ struct packed_ref_store {\n \tstruct tempfile tempfile;\n };\n \n+/*\n+ * Increment the reference count of *packed_refs.\n+ */\n+static void acquire_packed_ref_cache(struct packed_ref_cache *packed_refs)\n+{\n+\tpacked_refs->referrers++;\n+}\n+\n+/*\n+ * Decrease the reference count of *packed_refs. If it goes to zero,\n+ * free *packed_refs and return true; otherwise return false.\n+ */\n+static int release_packed_ref_cache(struct packed_ref_cache *packed_refs)\n+{\n+\tif (!--packed_refs->referrers) {\n+\t\tfree_ref_cache(packed_refs->cache);\n+\t\tstat_validity_clear(&packed_refs->validity);\n+\t\tfree(packed_refs);\n+\t\treturn 1;\n+\t} else {\n+\t\treturn 0;\n+\t}\n+}\n+\n struct ref_store *packed_ref_store_create(const char *path,\n \t\t\t\t\t unsigned int store_flags)\n {\n-- \n2.14.1\n\n"},{"id":"328356","messageId":"b32234e07a1bd1e60442a13d97d7c4e51edf3336.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"[PATCH v2 13/21] packed_ref_cache: keep the `packed-refs` file mmapped if possible","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:21Z","receivedAt":"2017-09-19T06:23:12Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Keep a copy of the `packed-refs` file contents in memory for as long\nas a `packed_ref_cache` object is in use:\n\n* If the system allows it, keep the `packed-refs` file mmapped.\n\n* If not (either because the system doesn't support `mmap()` at all,\n or because a file that is currently mmapped cannot be replaced via\n `rename()`), then make a copy of the file's contents in\n heap-allocated space, and keep that around instead.\n\nWe base the choice of behavior on a new build-time switch,\n`MMAP_PREVENTS_DELETE`. By default, this switch is set for Windows\nvariants.\n\nThis whole change is still pointless, because we only read the\n`packed-refs` file contents immediately after instantiating the\n`packed_ref_cache`. But that will soon change.\n\nSigned-off-by: Michael Haggerty \n---\n Makefile | 10 +++\n config.mak.uname | 3 +\n refs/packed-backend.c | 184 ++++++++++++++++++++++++++++++++++++++------------\n 3 files changed, 155 insertions(+), 42 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex f2bb7f2f63..7a49f99c4f 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -200,6 +200,9 @@ all::\n #\n # Define NO_MMAP if you want to avoid mmap.\n #\n+# Define MMAP_PREVENTS_DELETE if a file that is currently mmapped cannot be\n+# deleted or cannot be replaced using rename().\n+#\n # Define NO_SYS_POLL_H if you don't have sys/poll.h.\n #\n # Define NO_POLL if you do not have or don't want to use poll().\n@@ -1383,6 +1386,13 @@ else\n \t\tCOMPAT_OBJS += compat/win32mmap.o\n \tendif\n endif\n+ifdef MMAP_PREVENTS_DELETE\n+\tBASIC_CFLAGS += -DMMAP_PREVENTS_DELETE\n+else\n+\tifdef USE_WIN32_MMAP\n+\t\tBASIC_CFLAGS += -DMMAP_PREVENTS_DELETE\n+\tendif\n+endif\n ifdef OBJECT_CREATION_USES_RENAMES\n \tCOMPAT_CFLAGS += -DOBJECT_CREATION_MODE=1\n endif\ndiff --git a/config.mak.uname b/config.mak.uname\nindex 6604b130f8..685a80d138 100644\n--- a/config.mak.uname\n+++ b/config.mak.uname\n@@ -184,6 +184,7 @@ ifeq ($(uname_O),Cygwin)\n \tUNRELIABLE_FSTAT = UnfortunatelyYes\n \tSPARSE_FLAGS = -isystem /usr/include/w32api -Wno-one-bit-signed-bitfield\n \tOBJECT_CREATION_USES_RENAMES = UnfortunatelyNeedsTo\n+\tMMAP_PREVENTS_DELETE = UnfortunatelyYes\n \tCOMPAT_OBJS += compat/cygwin.o\n \tFREAD_READS_DIRECTORIES = UnfortunatelyYes\n endif\n@@ -353,6 +354,7 @@ ifeq ($(uname_S),Windows)\n \tNO_ST_BLOCKS_IN_STRUCT_STAT = YesPlease\n \tNO_NSEC = YesPlease\n \tUSE_WIN32_MMAP = YesPlease\n+\tMMAP_PREVENTS_DELETE = UnfortunatelyYes\n \t# USE_NED_ALLOCATOR = YesPlease\n \tUNRELIABLE_FSTAT = UnfortunatelyYes\n \tOBJECT_CREATION_USES_RENAMES = UnfortunatelyNeedsTo\n@@ -501,6 +503,7 @@ ifneq (,$(findstring MINGW,$(uname_S)))\n \tNO_ST_BLOCKS_IN_STRUCT_STAT = YesPlease\n \tNO_NSEC = YesPlease\n \tUSE_WIN32_MMAP = YesPlease\n+\tMMAP_PREVENTS_DELETE = UnfortunatelyYes\n \tUSE_NED_ALLOCATOR = YesPlease\n \tUNRELIABLE_FSTAT = UnfortunatelyYes\n \tOBJECT_CREATION_USES_RENAMES = UnfortunatelyNeedsTo\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 0fe41a7203..4981516f1e 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -7,6 +7,35 @@\n #include \"../iterator.h\"\n #include \"../lockfile.h\"\n \n+enum mmap_strategy {\n+\t/*\n+\t * Don't use mmap() at all for reading `packed-refs`.\n+\t */\n+\tMMAP_NONE,\n+\n+\t/*\n+\t * Can use mmap() for reading `packed-refs`, but the file must\n+\t * not remain mmapped. This is the usual option on Windows,\n+\t * where you cannot rename a new version of a file onto a file\n+\t * that is currently mmapped.\n+\t */\n+\tMMAP_TEMPORARY,\n+\n+\t/*\n+\t * It is OK to leave the `packed-refs` file mmapped while\n+\t * arbitrary other code is running.\n+\t */\n+\tMMAP_OK\n+};\n+\n+#if defined(NO_MMAP)\n+static enum mmap_strategy mmap_strategy = MMAP_NONE;\n+#elif defined(MMAP_PREVENTS_DELETE)\n+static enum mmap_strategy mmap_strategy = MMAP_TEMPORARY;\n+#else\n+static enum mmap_strategy mmap_strategy = MMAP_OK;\n+#endif\n+\n struct packed_ref_store;\n \n struct packed_ref_cache {\n@@ -18,6 +47,21 @@ struct packed_ref_cache {\n \n \tstruct ref_cache *cache;\n \n+\t/* Is the `packed-refs` file currently mmapped? */\n+\tint mmapped;\n+\n+\t/*\n+\t * The contents of the `packed-refs` file. If the file is\n+\t * mmapped, this points at the mmapped contents of the file.\n+\t * If not, this points at heap-allocated memory containing the\n+\t * contents. If there were no contents (e.g., because the file\n+\t * didn't exist), `buf` and `eof` are both NULL.\n+\t */\n+\tchar *buf, *eof;\n+\n+\t/* The size of the header line, if any; otherwise, 0: */\n+\tsize_t header_len;\n+\n \t/*\n \t * What is the peeled state of this cache? (This is usually\n \t * determined from the header of the \"packed-refs\" file.)\n@@ -76,6 +120,26 @@ static void acquire_packed_ref_cache(struct packed_ref_cache *packed_refs)\n \tpacked_refs->referrers++;\n }\n \n+/*\n+ * If the buffer in `packed_refs` is active, then either munmap the\n+ * memory and close the file, or free the memory. Then set the buffer\n+ * pointers to NULL.\n+ */\n+static void release_packed_ref_buffer(struct packed_ref_cache *packed_refs)\n+{\n+\tif (packed_refs->mmapped) {\n+\t\tif (munmap(packed_refs->buf,\n+\t\t\t packed_refs->eof - packed_refs->buf))\n+\t\t\tdie_errno(\"error ummapping packed-refs file %s\",\n+\t\t\t\t packed_refs->refs->path);\n+\t\tpacked_refs->mmapped = 0;\n+\t} else {\n+\t\tfree(packed_refs->buf);\n+\t}\n+\tpacked_refs->buf = packed_refs->eof = NULL;\n+\tpacked_refs->header_len = 0;\n+}\n+\n /*\n * Decrease the reference count of *packed_refs. If it goes to zero,\n * free *packed_refs and return true; otherwise return false.\n@@ -85,6 +149,7 @@ static int release_packed_ref_cache(struct packed_ref_cache *packed_refs)\n \tif (!--packed_refs->referrers) {\n \t\tfree_ref_cache(packed_refs->cache);\n \t\tstat_validity_clear(&packed_refs->validity);\n+\t\trelease_packed_ref_buffer(packed_refs);\n \t\tfree(packed_refs);\n \t\treturn 1;\n \t} else {\n@@ -284,13 +349,15 @@ static struct ref_iterator_vtable mmapped_ref_iterator_vtable = {\n };\n \n struct ref_iterator *mmapped_ref_iterator_begin(\n-\t\tconst char *packed_refs_file,\n \t\tstruct packed_ref_cache *packed_refs,\n \t\tconst char *pos, const char *eof)\n {\n \tstruct mmapped_ref_iterator *iter = xcalloc(1, sizeof(*iter));\n \tstruct ref_iterator *ref_iterator = &iter->base;\n \n+\tif (!packed_refs->buf)\n+\t\treturn empty_ref_iterator_begin();\n+\n \tbase_ref_iterator_init(ref_iterator, &mmapped_ref_iterator_vtable, 0);\n \n \titer->packed_refs = packed_refs;\n@@ -304,6 +371,61 @@ struct ref_iterator *mmapped_ref_iterator_begin(\n \treturn ref_iterator;\n }\n \n+/*\n+ * Depending on `mmap_strategy`, either mmap or read the contents of\n+ * the `packed-refs` file into the `packed_refs` instance. Return 1 if\n+ * the file existed and was read, or 0 if the file was absent. Die on\n+ * errors.\n+ */\n+static int load_contents(struct packed_ref_cache *packed_refs)\n+{\n+\tint fd;\n+\tstruct stat st;\n+\tsize_t size, bytes_read;\n+\n+\tfd = open(packed_refs->refs->path, O_RDONLY);\n+\tif (fd < 0) {\n+\t\tif (errno == ENOENT) {\n+\t\t\t/*\n+\t\t\t * This is OK; it just means that no\n+\t\t\t * \"packed-refs\" file has been written yet,\n+\t\t\t * which is equivalent to it being empty,\n+\t\t\t * which is its state when initialized with\n+\t\t\t * zeros.\n+\t\t\t */\n+\t\t\treturn 0;\n+\t\t} else {\n+\t\t\tdie_errno(\"couldn't read %s\", packed_refs->refs->path);\n+\t\t}\n+\t}\n+\n+\tstat_validity_update(&packed_refs->validity, fd);\n+\n+\tif (fstat(fd, &st) < 0)\n+\t\tdie_errno(\"couldn't stat %s\", packed_refs->refs->path);\n+\tsize = xsize_t(st.st_size);\n+\n+\tswitch (mmap_strategy) {\n+\tcase MMAP_NONE:\n+\tcase MMAP_TEMPORARY:\n+\t\tpacked_refs->buf = xmalloc(size);\n+\t\tbytes_read = read_in_full(fd, packed_refs->buf, size);\n+\t\tif (bytes_read < 0 || bytes_read != size)\n+\t\t\tdie_errno(\"couldn't read %s\", packed_refs->refs->path);\n+\t\tpacked_refs->eof = packed_refs->buf + size;\n+\t\tpacked_refs->mmapped = 0;\n+\t\tbreak;\n+\tcase MMAP_OK:\n+\t\tpacked_refs->buf = xmmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\t\tpacked_refs->eof = packed_refs->buf + size;\n+\t\tpacked_refs->mmapped = 1;\n+\t\tbreak;\n+\t}\n+\tclose(fd);\n+\n+\treturn 1;\n+}\n+\n /*\n * Read from the `packed-refs` file into a newly-allocated\n * `packed_ref_cache` and return it. The return value will already\n@@ -336,11 +458,6 @@ struct ref_iterator *mmapped_ref_iterator_begin(\n static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n {\n \tstruct packed_ref_cache *packed_refs = xcalloc(1, sizeof(*packed_refs));\n-\tint fd;\n-\tstruct stat st;\n-\tsize_t size;\n-\tchar *buf;\n-\tconst char *pos, *eof;\n \tstruct ref_dir *dir;\n \tstruct ref_iterator *iter;\n \tint ok;\n@@ -351,45 +468,29 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \tpacked_refs->cache->root->flag &= ~REF_INCOMPLETE;\n \tpacked_refs->peeled = PEELED_NONE;\n \n-\tfd = open(refs->path, O_RDONLY);\n-\tif (fd < 0) {\n-\t\tif (errno == ENOENT) {\n-\t\t\t/*\n-\t\t\t * This is OK; it just means that no\n-\t\t\t * \"packed-refs\" file has been written yet,\n-\t\t\t * which is equivalent to it being empty.\n-\t\t\t */\n-\t\t\treturn packed_refs;\n-\t\t} else {\n-\t\t\tdie_errno(\"couldn't read %s\", refs->path);\n-\t\t}\n-\t}\n-\n-\tstat_validity_update(&packed_refs->validity, fd);\n-\n-\tif (fstat(fd, &st) < 0)\n-\t\tdie_errno(\"couldn't stat %s\", refs->path);\n-\n-\tsize = xsize_t(st.st_size);\n-\tbuf = xmmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);\n-\tpos = buf;\n-\teof = buf + size;\n+\tif (!load_contents(packed_refs))\n+\t\treturn packed_refs;\n \n \t/* If the file has a header line, process it: */\n-\tif (pos < eof && *pos == '#') {\n+\tif (packed_refs->buf < packed_refs->eof && *packed_refs->buf == '#') {\n \t\tstruct strbuf tmp = STRBUF_INIT;\n \t\tchar *p;\n \t\tconst char *eol;\n \t\tstruct string_list traits = STRING_LIST_INIT_NODUP;\n \n-\t\teol = memchr(pos, '\\n', eof - pos);\n+\t\teol = memchr(packed_refs->buf, '\\n',\n+\t\t\t packed_refs->eof - packed_refs->buf);\n \t\tif (!eol)\n-\t\t\tdie_unterminated_line(refs->path, pos, eof - pos);\n+\t\t\tdie_unterminated_line(refs->path,\n+\t\t\t\t\t packed_refs->buf,\n+\t\t\t\t\t packed_refs->eof - packed_refs->buf);\n \n-\t\tstrbuf_add(&tmp, pos, eol - pos);\n+\t\tstrbuf_add(&tmp, packed_refs->buf, eol - packed_refs->buf);\n \n \t\tif (!skip_prefix(tmp.buf, \"# pack-refs with:\", (const char **)&p))\n-\t\t\tdie_invalid_line(refs->path, pos, eof - pos);\n+\t\t\tdie_invalid_line(refs->path,\n+\t\t\t\t\t packed_refs->buf,\n+\t\t\t\t\t packed_refs->eof - packed_refs->buf);\n \n \t\tstring_list_split_in_place(&traits, p, ' ', -1);\n \n@@ -400,14 +501,17 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \t\t/* perhaps other traits later as well */\n \n \t\t/* The \"+ 1\" is for the LF character. */\n-\t\tpos = eol + 1;\n+\t\tpacked_refs->header_len = eol + 1 - packed_refs->buf;\n \n \t\tstring_list_clear(&traits, 0);\n \t\tstrbuf_release(&tmp);\n \t}\n \n \tdir = get_ref_dir(packed_refs->cache->root);\n-\titer = mmapped_ref_iterator_begin(refs->path, packed_refs, pos, eof);\n+\titer = mmapped_ref_iterator_begin(\n+\t\t\tpacked_refs,\n+\t\t\tpacked_refs->buf + packed_refs->header_len,\n+\t\t\tpacked_refs->eof);\n \twhile ((ok = ref_iterator_advance(iter)) == ITER_OK) {\n \t\tstruct ref_entry *entry =\n \t\t\tcreate_ref_entry(iter->refname, iter->oid, iter->flags);\n@@ -420,11 +524,6 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \tif (ok != ITER_DONE)\n \t\tdie(\"error reading packed-refs file %s\", refs->path);\n \n-\tif (munmap(buf, size))\n-\t\tdie_errno(\"error ummapping packed-refs file %s\", refs->path);\n-\n-\tclose(fd);\n-\n \treturn packed_refs;\n }\n \n@@ -1031,6 +1130,8 @@ static int packed_transaction_finish(struct ref_store *ref_store,\n \tint ret = TRANSACTION_GENERIC_ERROR;\n \tchar *packed_refs_path;\n \n+\tclear_packed_ref_cache(refs);\n+\n \tpacked_refs_path = get_locked_file_path(&refs->lock);\n \tif (rename_tempfile(&refs->tempfile, packed_refs_path)) {\n \t\tstrbuf_addf(err, \"error replacing %s: %s\",\n@@ -1038,7 +1139,6 @@ static int packed_transaction_finish(struct ref_store *ref_store,\n \t\tgoto cleanup;\n \t}\n \n-\tclear_packed_ref_cache(refs);\n \tret = 0;\n \n cleanup:\n-- \n2.14.1\n\n"},{"id":"328357","messageId":"5bb362d9cb74c7386cd072e3ecd49b22cea1d8d2.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"[PATCH v2 14/21] read_packed_refs(): ensure that references are ordered when read","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:22Z","receivedAt":"2017-09-19T06:23:14Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"It doesn't actually matter now, because the references are only\niterated over to fill the associated `ref_cache`, which itself puts\nthem in the correct order. But we want to get rid of the `ref_cache`,\nso we want to be able to iterate directly over the `packed-refs`\nbuffer, and then the iteration will need to be ordered correctly.\n\nIn fact, we already write the `packed-refs` file sorted, but it is\npossible that other Git clients don't get it right. So let's not\nassume that a `packed-refs` file is sorted unless it is explicitly\ndeclared to be so via a `sorted` trait in its header line.\n\nIf it is *not* declared to be sorted, then scan quickly through the\nfile to check. If it is found to be out of order, then sort the\nrecords into a new memory-only copy. This checking and sorting is done\nquickly, without parsing the full file contents. However, it needs a\nlittle bit of care to avoid reading past the end of the buffer even if\nthe `packed-refs` file is corrupt.\n\nSince *we* always write the file correctly sorted, include that trait\nwhen we write or rewrite a `packed-refs` file. This means that the\nscan described in the previous paragraph should only have to be done\nfor `packed-refs` files that were written by older versions of the Git\ncommand-line client, or by other clients that haven't yet learned to\nwrite the `sorted` trait.\n\nIf `packed-refs` was already sorted, then (if the system allows it) we\ncan use the mmapped file contents directly. But if the system doesn't\nallow a file that is currently mmapped to be replaced using\n`rename()`, then it would be bad for us to keep the file mmapped for\nany longer than necessary. So, on such systems, always make a copy of\nthe file contents, either as part of the sorting process, or\nafterwards.\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 223 +++++++++++++++++++++++++++++++++++++++++++++++---\n 1 file changed, 212 insertions(+), 11 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 4981516f1e..f336690f16 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -51,11 +51,12 @@ struct packed_ref_cache {\n \tint mmapped;\n \n \t/*\n-\t * The contents of the `packed-refs` file. If the file is\n-\t * mmapped, this points at the mmapped contents of the file.\n-\t * If not, this points at heap-allocated memory containing the\n-\t * contents. If there were no contents (e.g., because the file\n-\t * didn't exist), `buf` and `eof` are both NULL.\n+\t * The contents of the `packed-refs` file. If the file was\n+\t * already sorted, this points at the mmapped contents of the\n+\t * file. If not, this points at heap-allocated memory\n+\t * containing the contents, sorted. If there were no contents\n+\t * (e.g., because the file didn't exist), `buf` and `eof` are\n+\t * both NULL.\n \t */\n \tchar *buf, *eof;\n \n@@ -358,7 +359,7 @@ struct ref_iterator *mmapped_ref_iterator_begin(\n \tif (!packed_refs->buf)\n \t\treturn empty_ref_iterator_begin();\n \n-\tbase_ref_iterator_init(ref_iterator, &mmapped_ref_iterator_vtable, 0);\n+\tbase_ref_iterator_init(ref_iterator, &mmapped_ref_iterator_vtable, 1);\n \n \titer->packed_refs = packed_refs;\n \tacquire_packed_ref_cache(iter->packed_refs);\n@@ -371,6 +372,170 @@ struct ref_iterator *mmapped_ref_iterator_begin(\n \treturn ref_iterator;\n }\n \n+struct packed_ref_entry {\n+\tconst char *start;\n+\tsize_t len;\n+};\n+\n+static int cmp_packed_ref_entries(const void *v1, const void *v2)\n+{\n+\tconst struct packed_ref_entry *e1 = v1, *e2 = v2;\n+\tconst char *r1 = e1->start + GIT_SHA1_HEXSZ + 1;\n+\tconst char *r2 = e2->start + GIT_SHA1_HEXSZ + 1;\n+\n+\twhile (1) {\n+\t\tif (*r1 == '\\n')\n+\t\t\treturn *r2 == '\\n' ? 0 : -1;\n+\t\tif (*r1 != *r2) {\n+\t\t\tif (*r2 == '\\n')\n+\t\t\t\treturn 1;\n+\t\t\telse\n+\t\t\t\treturn (unsigned char)*r1 < (unsigned char)*r2 ? -1 : +1;\n+\t\t}\n+\t\tr1++;\n+\t\tr2++;\n+\t}\n+}\n+\n+/*\n+ * `packed_refs->buf` is not known to be sorted. Check whether it is,\n+ * and if not, sort it into new memory and munmap/free the old\n+ * storage.\n+ */\n+static void sort_packed_refs(struct packed_ref_cache *packed_refs)\n+{\n+\tstruct packed_ref_entry *entries = NULL;\n+\tsize_t alloc = 0, nr = 0;\n+\tint sorted = 1;\n+\tconst char *pos, *eof, *eol;\n+\tsize_t len, i;\n+\tchar *new_buffer, *dst;\n+\n+\tpos = packed_refs->buf + packed_refs->header_len;\n+\teof = packed_refs->eof;\n+\tlen = eof - pos;\n+\n+\tif (!len)\n+\t\treturn;\n+\n+\t/*\n+\t * Initialize entries based on a crude estimate of the number\n+\t * of references in the file (we'll grow it below if needed):\n+\t */\n+\tALLOC_GROW(entries, len / 80 + 20, alloc);\n+\n+\twhile (pos < eof) {\n+\t\teol = memchr(pos, '\\n', eof - pos);\n+\t\tif (!eol)\n+\t\t\t/* The safety check should prevent this. */\n+\t\t\tBUG(\"unterminated line found in packed-refs\");\n+\t\tif (eol - pos < GIT_SHA1_HEXSZ + 2)\n+\t\t\tdie_invalid_line(packed_refs->refs->path,\n+\t\t\t\t\t pos, eof - pos);\n+\t\teol++;\n+\t\tif (eol < eof && *eol == '^') {\n+\t\t\t/*\n+\t\t\t * Keep any peeled line together with its\n+\t\t\t * reference:\n+\t\t\t */\n+\t\t\tconst char *peeled_start = eol;\n+\n+\t\t\teol = memchr(peeled_start, '\\n', eof - peeled_start);\n+\t\t\tif (!eol)\n+\t\t\t\t/* The safety check should prevent this. */\n+\t\t\t\tBUG(\"unterminated peeled line found in packed-refs\");\n+\t\t\teol++;\n+\t\t}\n+\n+\t\tALLOC_GROW(entries, nr + 1, alloc);\n+\t\tentries[nr].start = pos;\n+\t\tentries[nr].len = eol - pos;\n+\t\tnr++;\n+\n+\t\tif (sorted &&\n+\t\t nr > 1 &&\n+\t\t cmp_packed_ref_entries(&entries[nr - 2],\n+\t\t\t\t\t &entries[nr - 1]) >= 0)\n+\t\t\tsorted = 0;\n+\n+\t\tpos = eol;\n+\t}\n+\n+\tif (sorted)\n+\t\tgoto cleanup;\n+\n+\t/* We need to sort the memory. First we sort the entries array: */\n+\tQSORT(entries, nr, cmp_packed_ref_entries);\n+\n+\t/*\n+\t * Allocate a new chunk of memory, and copy the old memory to\n+\t * the new in the order indicated by `entries` (not bothering\n+\t * with the header line):\n+\t */\n+\tnew_buffer = xmalloc(len);\n+\tfor (dst = new_buffer, i = 0; i < nr; i++) {\n+\t\tmemcpy(dst, entries[i].start, entries[i].len);\n+\t\tdst += entries[i].len;\n+\t}\n+\n+\t/*\n+\t * Now munmap the old buffer and use the sorted buffer in its\n+\t * place:\n+\t */\n+\trelease_packed_ref_buffer(packed_refs);\n+\tpacked_refs->buf = new_buffer;\n+\tpacked_refs->eof = new_buffer + len;\n+\tpacked_refs->header_len = 0;\n+\n+cleanup:\n+\tfree(entries);\n+}\n+\n+/*\n+ * Return a pointer to the start of the record that contains the\n+ * character `*p` (which must be within the buffer). If no other\n+ * record start is found, return `buf`.\n+ */\n+static const char *find_start_of_record(const char *buf, const char *p)\n+{\n+\twhile (p > buf && (p[-1] != '\\n' || p[0] == '^'))\n+\t\tp--;\n+\treturn p;\n+}\n+\n+/*\n+ * We want to be able to compare mmapped reference records quickly,\n+ * without totally parsing them. We can do so because the records are\n+ * LF-terminated, and the refname should start exactly (GIT_SHA1_HEXSZ\n+ * + 1) bytes past the beginning of the record.\n+ *\n+ * But what if the `packed-refs` file contains garbage? We're willing\n+ * to tolerate not detecting the problem, as long as we don't produce\n+ * totally garbled output (we can't afford to check the integrity of\n+ * the whole file during every Git invocation). But we do want to be\n+ * sure that we never read past the end of the buffer in memory and\n+ * perform an illegal memory access.\n+ *\n+ * Guarantee that minimum level of safety by verifying that the last\n+ * record in the file is LF-terminated, and that it has at least\n+ * (GIT_SHA1_HEXSZ + 1) characters before the LF. Die if either of\n+ * these checks fails.\n+ */\n+static void verify_buffer_safe(struct packed_ref_cache *packed_refs)\n+{\n+\tconst char *buf = packed_refs->buf + packed_refs->header_len;\n+\tconst char *eof = packed_refs->eof;\n+\tconst char *last_line;\n+\n+\tif (buf == eof)\n+\t\treturn;\n+\n+\tlast_line = find_start_of_record(buf, eof - 1);\n+\tif (*(eof - 1) != '\\n' || eof - last_line < GIT_SHA1_HEXSZ + 2)\n+\t\tdie_invalid_line(packed_refs->refs->path,\n+\t\t\t\t last_line, eof - last_line);\n+}\n+\n /*\n * Depending on `mmap_strategy`, either mmap or read the contents of\n * the `packed-refs` file into the `packed_refs` instance. Return 1 if\n@@ -407,7 +572,6 @@ static int load_contents(struct packed_ref_cache *packed_refs)\n \n \tswitch (mmap_strategy) {\n \tcase MMAP_NONE:\n-\tcase MMAP_TEMPORARY:\n \t\tpacked_refs->buf = xmalloc(size);\n \t\tbytes_read = read_in_full(fd, packed_refs->buf, size);\n \t\tif (bytes_read < 0 || bytes_read != size)\n@@ -415,6 +579,7 @@ static int load_contents(struct packed_ref_cache *packed_refs)\n \t\tpacked_refs->eof = packed_refs->buf + size;\n \t\tpacked_refs->mmapped = 0;\n \t\tbreak;\n+\tcase MMAP_TEMPORARY:\n \tcase MMAP_OK:\n \t\tpacked_refs->buf = xmmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);\n \t\tpacked_refs->eof = packed_refs->buf + size;\n@@ -434,19 +599,19 @@ static int load_contents(struct packed_ref_cache *packed_refs)\n * A comment line of the form \"# pack-refs with: \" may contain zero or\n * more traits. We interpret the traits as follows:\n *\n- * No traits:\n+ * Neither `peeled` nor `fully-peeled`:\n *\n * Probably no references are peeled. But if the file contains a\n * peeled value for a reference, we will use it.\n *\n- * peeled:\n+ * `peeled`:\n *\n * References under \"refs/tags/\", if they *can* be peeled, *are*\n * peeled in this file. References outside of \"refs/tags/\" are\n * probably not peeled even if they could have been, but if we find\n * a peeled value for such a reference we will use it.\n *\n- * fully-peeled:\n+ * `fully-peeled`:\n *\n * All references in the file that can be peeled are peeled.\n * Inversely (and this is more important), any references in the\n@@ -454,12 +619,17 @@ static int load_contents(struct packed_ref_cache *packed_refs)\n * trait should typically be written alongside \"peeled\" for\n * compatibility with older clients, but we do not require it\n * (i.e., \"peeled\" is a no-op if \"fully-peeled\" is set).\n+ *\n+ * `sorted`:\n+ *\n+ * The references in this file are known to be sorted by refname.\n */\n static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n {\n \tstruct packed_ref_cache *packed_refs = xcalloc(1, sizeof(*packed_refs));\n \tstruct ref_dir *dir;\n \tstruct ref_iterator *iter;\n+\tint sorted = 0;\n \tint ok;\n \n \tpacked_refs->refs = refs;\n@@ -498,6 +668,9 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \t\t\tpacked_refs->peeled = PEELED_FULLY;\n \t\telse if (unsorted_string_list_has_string(&traits, \"peeled\"))\n \t\t\tpacked_refs->peeled = PEELED_TAGS;\n+\n+\t\tsorted = unsorted_string_list_has_string(&traits, \"sorted\");\n+\n \t\t/* perhaps other traits later as well */\n \n \t\t/* The \"+ 1\" is for the LF character. */\n@@ -507,6 +680,34 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \t\tstrbuf_release(&tmp);\n \t}\n \n+\tverify_buffer_safe(packed_refs);\n+\n+\tif (!sorted) {\n+\t\tsort_packed_refs(packed_refs);\n+\n+\t\t/*\n+\t\t * Reordering the records might have moved a short one\n+\t\t * to the end of the buffer, so verify the buffer's\n+\t\t * safety again:\n+\t\t */\n+\t\tverify_buffer_safe(packed_refs);\n+\t}\n+\n+\tif (mmap_strategy != MMAP_OK && packed_refs->mmapped) {\n+\t\t/*\n+\t\t * We don't want to leave the file mmapped, so we are\n+\t\t * forced to make a copy now:\n+\t\t */\n+\t\tsize_t size = packed_refs->eof -\n+\t\t\t(packed_refs->buf + packed_refs->header_len);\n+\t\tchar *buf_copy = xmalloc(size);\n+\n+\t\tmemcpy(buf_copy, packed_refs->buf + packed_refs->header_len, size);\n+\t\trelease_packed_ref_buffer(packed_refs);\n+\t\tpacked_refs->buf = buf_copy;\n+\t\tpacked_refs->eof = buf_copy + size;\n+\t}\n+\n \tdir = get_ref_dir(packed_refs->cache->root);\n \titer = mmapped_ref_iterator_begin(\n \t\t\tpacked_refs,\n@@ -810,7 +1011,7 @@ int packed_refs_is_locked(struct ref_store *ref_store)\n * the colon and the trailing space are required.\n */\n static const char PACKED_REFS_HEADER[] =\n-\t\"# pack-refs with: peeled fully-peeled \\n\";\n+\t\"# pack-refs with: peeled fully-peeled sorted \\n\";\n \n static int packed_init_db(struct ref_store *ref_store, struct strbuf *err)\n {\n-- \n2.14.1\n\n"},{"id":"328358","messageId":"81f7f71db378c38e51e0d995f458d8fbd1ea43c9.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"[PATCH v2 15/21] packed_ref_iterator_begin(): iterate using `mmapped_ref_iterator`","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:23Z","receivedAt":"2017-09-19T06:23:19Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Now that we have an efficient way to iterate, in order, over the\nmmapped contents of the `packed-refs` file, we can use that directly\nto implement reference iteration for the `packed_ref_store`, rather\nthan iterating over the `ref_cache`. This is the next step towards\ngetting rid of the `ref_cache` entirely.\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 109 ++++++++++++++++++++++++++++++++++++++++++++++++--\n 1 file changed, 106 insertions(+), 3 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex f336690f16..53d0b7e3d6 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -397,6 +397,27 @@ static int cmp_packed_ref_entries(const void *v1, const void *v2)\n \t}\n }\n \n+/*\n+ * Compare a packed-refs record pointed to by `rec` to the specified\n+ * NUL-terminated refname.\n+ */\n+static int cmp_entry_to_refname(const char *rec, const char *refname)\n+{\n+\tconst char *r1 = rec + GIT_SHA1_HEXSZ + 1;\n+\tconst char *r2 = refname;\n+\n+\twhile (1) {\n+\t\tif (*r1 == '\\n')\n+\t\t\treturn *r2 ? -1 : 0;\n+\t\tif (!*r2)\n+\t\t\treturn 1;\n+\t\tif (*r1 != *r2)\n+\t\t\treturn (unsigned char)*r1 < (unsigned char)*r2 ? -1 : +1;\n+\t\tr1++;\n+\t\tr2++;\n+\t}\n+}\n+\n /*\n * `packed_refs->buf` is not known to be sorted. Check whether it is,\n * and if not, sort it into new memory and munmap/free the old\n@@ -503,6 +524,17 @@ static const char *find_start_of_record(const char *buf, const char *p)\n \treturn p;\n }\n \n+/*\n+ * Return a pointer to the start of the record following the record\n+ * that contains `*p`. If none is found before `end`, return `end`.\n+ */\n+static const char *find_end_of_record(const char *p, const char *end)\n+{\n+\twhile (++p < end && (p[-1] != '\\n' || p[0] == '^'))\n+\t\t;\n+\treturn p;\n+}\n+\n /*\n * We want to be able to compare mmapped reference records quickly,\n * without totally parsing them. We can do so because the records are\n@@ -591,6 +623,65 @@ static int load_contents(struct packed_ref_cache *packed_refs)\n \treturn 1;\n }\n \n+/*\n+ * Find the place in `cache->buf` where the start of the record for\n+ * `refname` starts. If `mustexist` is true and the reference doesn't\n+ * exist, then return NULL. If `mustexist` is false and the reference\n+ * doesn't exist, then return the point where that reference would be\n+ * inserted. In the latter mode, `refname` doesn't have to be a proper\n+ * reference name; for example, one could search for \"refs/replace/\"\n+ * to find the start of any replace references.\n+ *\n+ * The record is sought using a binary search, so `cache->buf` must be\n+ * sorted.\n+ */\n+static const char *find_reference_location(struct packed_ref_cache *cache,\n+\t\t\t\t\t const char *refname, int mustexist)\n+{\n+\t/*\n+\t * This is not *quite* a garden-variety binary search, because\n+\t * the data we're searching is made up of records, and we\n+\t * always need to find the beginning of a record to do a\n+\t * comparison. A \"record\" here is one line for the reference\n+\t * itself and zero or one peel lines that start with '^'. Our\n+\t * loop invariant is described in the next two comments.\n+\t */\n+\n+\t/*\n+\t * A pointer to the character at the start of a record whose\n+\t * preceding records all have reference names that come\n+\t * *before* `refname`.\n+\t */\n+\tconst char *lo = cache->buf + cache->header_len;\n+\n+\t/*\n+\t * A pointer to a the first character of a record whose\n+\t * reference name comes *after* `refname`.\n+\t */\n+\tconst char *hi = cache->eof;\n+\n+\twhile (lo < hi) {\n+\t\tconst char *mid, *rec;\n+\t\tint cmp;\n+\n+\t\tmid = lo + (hi - lo) / 2;\n+\t\trec = find_start_of_record(lo, mid);\n+\t\tcmp = cmp_entry_to_refname(rec, refname);\n+\t\tif (cmp < 0) {\n+\t\t\tlo = find_end_of_record(mid, hi);\n+\t\t} else if (cmp > 0) {\n+\t\t\thi = rec;\n+\t\t} else {\n+\t\t\treturn rec;\n+\t\t}\n+\t}\n+\n+\tif (mustexist)\n+\t\treturn NULL;\n+\telse\n+\t\treturn lo;\n+}\n+\n /*\n * Read from the `packed-refs` file into a newly-allocated\n * `packed_ref_cache` and return it. The return value will already\n@@ -887,6 +978,8 @@ static struct ref_iterator *packed_ref_iterator_begin(\n \t\tconst char *prefix, unsigned int flags)\n {\n \tstruct packed_ref_store *refs;\n+\tstruct packed_ref_cache *packed_refs;\n+\tconst char *start;\n \tstruct packed_ref_iterator *iter;\n \tstruct ref_iterator *ref_iterator;\n \tunsigned int required_flags = REF_STORE_READ;\n@@ -904,13 +997,23 @@ static struct ref_iterator *packed_ref_iterator_begin(\n \t * the packed-ref cache is up to date with what is on disk,\n \t * and re-reads it if not.\n \t */\n+\titer->cache = packed_refs = get_packed_ref_cache(refs);\n+\tacquire_packed_ref_cache(packed_refs);\n \n-\titer->cache = get_packed_ref_cache(refs);\n-\tacquire_packed_ref_cache(iter->cache);\n-\titer->iter0 = cache_ref_iterator_begin(iter->cache->cache, prefix, 0);\n+\tif (prefix && *prefix)\n+\t\tstart = find_reference_location(packed_refs, prefix, 0);\n+\telse\n+\t\tstart = packed_refs->buf + packed_refs->header_len;\n+\n+\titer->iter0 = mmapped_ref_iterator_begin(\n+\t\t\tpacked_refs, start, packed_refs->eof);\n \n \titer->flags = flags;\n \n+\tif (prefix && *prefix)\n+\t\t/* Stop iteration after we've gone *past* prefix: */\n+\t\tref_iterator = prefix_ref_iterator_begin(ref_iterator, prefix, 0);\n+\n \treturn ref_iterator;\n }\n \n-- \n2.14.1\n\n"},{"id":"328359","messageId":"6f86618771d29d29b7f70f4d4abb0f4761c6c873.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"[PATCH v2 18/21] packed_ref_store: get rid of the `ref_cache` entirely","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:26Z","receivedAt":"2017-09-19T06:23:21Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Now that everything has been changed to read what it needs directly\nout of the `packed-refs` file, `packed_ref_store` doesn't need to\nmaintain a `ref_cache` at all. So get rid of it.\n\nFirst of all, this will save a lot of memory and lots of little\nallocations. Instead of needing to store complicated parsed data\nstructures in memory, we just mmap the file (potentially sharing\nmemory with other processes) and parse only what we need.\n\nMoreover, since the mmapped access to the file reads only the parts of\nthe file that it needs, this might save reading all of the data from\ndisk at all (at least if the file starts out sorted).\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 29 ++---------------------------\n 1 file changed, 2 insertions(+), 27 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 6a930a440c..b4a01637a6 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -45,8 +45,6 @@ struct packed_ref_cache {\n \t */\n \tstruct packed_ref_store *refs;\n \n-\tstruct ref_cache *cache;\n-\n \t/* Is the `packed-refs` file currently mmapped? */\n \tint mmapped;\n \n@@ -148,7 +146,6 @@ static void release_packed_ref_buffer(struct packed_ref_cache *packed_refs)\n static int release_packed_ref_cache(struct packed_ref_cache *packed_refs)\n {\n \tif (!--packed_refs->referrers) {\n-\t\tfree_ref_cache(packed_refs->cache);\n \t\tstat_validity_clear(&packed_refs->validity);\n \t\trelease_packed_ref_buffer(packed_refs);\n \t\tfree(packed_refs);\n@@ -718,15 +715,10 @@ static const char *find_reference_location(struct packed_ref_cache *cache,\n static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n {\n \tstruct packed_ref_cache *packed_refs = xcalloc(1, sizeof(*packed_refs));\n-\tstruct ref_dir *dir;\n-\tstruct ref_iterator *iter;\n \tint sorted = 0;\n-\tint ok;\n \n \tpacked_refs->refs = refs;\n \tacquire_packed_ref_cache(packed_refs);\n-\tpacked_refs->cache = create_ref_cache(NULL, NULL);\n-\tpacked_refs->cache->root->flag &= ~REF_INCOMPLETE;\n \tpacked_refs->peeled = PEELED_NONE;\n \n \tif (!load_contents(packed_refs))\n@@ -799,23 +791,6 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \t\tpacked_refs->eof = buf_copy + size;\n \t}\n \n-\tdir = get_ref_dir(packed_refs->cache->root);\n-\titer = mmapped_ref_iterator_begin(\n-\t\t\tpacked_refs,\n-\t\t\tpacked_refs->buf + packed_refs->header_len,\n-\t\t\tpacked_refs->eof);\n-\twhile ((ok = ref_iterator_advance(iter)) == ITER_OK) {\n-\t\tstruct ref_entry *entry =\n-\t\t\tcreate_ref_entry(iter->refname, iter->oid, iter->flags);\n-\n-\t\tif ((iter->flags & REF_KNOWS_PEELED))\n-\t\t\tref_iterator_peel(iter, &entry->u.value.peeled);\n-\t\tadd_ref_entry(dir, entry);\n-\t}\n-\n-\tif (ok != ITER_DONE)\n-\t\tdie(\"error reading packed-refs file %s\", refs->path);\n-\n \treturn packed_refs;\n }\n \n@@ -974,8 +949,8 @@ static struct ref_iterator *packed_ref_iterator_begin(\n \telse\n \t\tstart = packed_refs->buf + packed_refs->header_len;\n \n-\titer->iter0 = mmapped_ref_iterator_begin(\n-\t\t\tpacked_refs, start, packed_refs->eof);\n+\titer->iter0 = mmapped_ref_iterator_begin(packed_refs,\n+\t\t\t\t\t\t start, packed_refs->eof);\n \n \titer->flags = flags;\n \n-- \n2.14.1\n\n"},{"id":"328360","messageId":"cdc0dee1402b2b7f0d27c8d140f472437afd2d6c.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"[PATCH v2 19/21] ref_cache: remove support for storing peeled values","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:27Z","receivedAt":"2017-09-19T06:23:26Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Now that the `packed-refs` backend doesn't use `ref_cache`, there is\nnobody left who might want to store peeled values of references in\n`ref_cache`. So remove that feature.\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 9 ++++++++-\n refs/ref-cache.c | 42 +-----------------------------------------\n refs/ref-cache.h | 32 ++------------------------------\n 3 files changed, 11 insertions(+), 72 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex b4a01637a6..b1571872fa 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -2,7 +2,6 @@\n #include \"../config.h\"\n #include \"../refs.h\"\n #include \"refs-internal.h\"\n-#include \"ref-cache.h\"\n #include \"packed-backend.h\"\n #include \"../iterator.h\"\n #include \"../lockfile.h\"\n@@ -226,6 +225,14 @@ static NORETURN void die_invalid_line(const char *path,\n \n }\n \n+/*\n+ * This value is set in `base.flags` if the peeled value of the\n+ * current reference is known. In that case, `peeled` contains the\n+ * correct peeled value for the reference, which might be `null_sha1`\n+ * if the reference is not a tag or if it is broken.\n+ */\n+#define REF_KNOWS_PEELED 0x40\n+\n /*\n * An iterator over a packed-refs file that is currently mmapped.\n */\ndiff --git a/refs/ref-cache.c b/refs/ref-cache.c\nindex 54dfb5218c..4f850e1b5c 100644\n--- a/refs/ref-cache.c\n+++ b/refs/ref-cache.c\n@@ -38,7 +38,6 @@ struct ref_entry *create_ref_entry(const char *refname,\n \n \tFLEX_ALLOC_STR(ref, name, refname);\n \toidcpy(&ref->u.value.oid, oid);\n-\toidclr(&ref->u.value.peeled);\n \tref->flag = flag;\n \treturn ref;\n }\n@@ -491,49 +490,10 @@ static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)\n \t}\n }\n \n-enum peel_status peel_entry(struct ref_entry *entry, int repeel)\n-{\n-\tenum peel_status status;\n-\n-\tif (entry->flag & REF_KNOWS_PEELED) {\n-\t\tif (repeel) {\n-\t\t\tentry->flag &= ~REF_KNOWS_PEELED;\n-\t\t\toidclr(&entry->u.value.peeled);\n-\t\t} else {\n-\t\t\treturn is_null_oid(&entry->u.value.peeled) ?\n-\t\t\t\tPEEL_NON_TAG : PEEL_PEELED;\n-\t\t}\n-\t}\n-\tif (entry->flag & REF_ISBROKEN)\n-\t\treturn PEEL_BROKEN;\n-\tif (entry->flag & REF_ISSYMREF)\n-\t\treturn PEEL_IS_SYMREF;\n-\n-\tstatus = peel_object(entry->u.value.oid.hash, entry->u.value.peeled.hash);\n-\tif (status == PEEL_PEELED || status == PEEL_NON_TAG)\n-\t\tentry->flag |= REF_KNOWS_PEELED;\n-\treturn status;\n-}\n-\n static int cache_ref_iterator_peel(struct ref_iterator *ref_iterator,\n \t\t\t\t struct object_id *peeled)\n {\n-\tstruct cache_ref_iterator *iter =\n-\t\t(struct cache_ref_iterator *)ref_iterator;\n-\tstruct cache_ref_iterator_level *level;\n-\tstruct ref_entry *entry;\n-\n-\tlevel = &iter->levels[iter->levels_nr - 1];\n-\n-\tif (level->index == -1)\n-\t\tdie(\"BUG: peel called before advance for cache iterator\");\n-\n-\tentry = level->dir->entries[level->index];\n-\n-\tif (peel_entry(entry, 0))\n-\t\treturn -1;\n-\toidcpy(peeled, &entry->u.value.peeled);\n-\treturn 0;\n+\treturn peel_object(ref_iterator->oid->hash, peeled->hash);\n }\n \n static int cache_ref_iterator_abort(struct ref_iterator *ref_iterator)\ndiff --git a/refs/ref-cache.h b/refs/ref-cache.h\nindex a082bfb06c..eda65e73ed 100644\n--- a/refs/ref-cache.h\n+++ b/refs/ref-cache.h\n@@ -38,14 +38,6 @@ struct ref_value {\n \t * referred to by the last reference in the symlink chain.\n \t */\n \tstruct object_id oid;\n-\n-\t/*\n-\t * If REF_KNOWS_PEELED, then this field holds the peeled value\n-\t * of this reference, or null if the reference is known not to\n-\t * be peelable. See the documentation for peel_ref() for an\n-\t * exact definition of \"peelable\".\n-\t */\n-\tstruct object_id peeled;\n };\n \n /*\n@@ -97,21 +89,14 @@ struct ref_dir {\n * public values; see refs.h.\n */\n \n-/*\n- * The field ref_entry->u.value.peeled of this value entry contains\n- * the correct peeled value for the reference, which might be\n- * null_sha1 if the reference is not a tag or if it is broken.\n- */\n-#define REF_KNOWS_PEELED 0x10\n-\n /* ref_entry represents a directory of references */\n-#define REF_DIR 0x20\n+#define REF_DIR 0x10\n \n /*\n * Entry has not yet been read from disk (used only for REF_DIR\n * entries representing loose references)\n */\n-#define REF_INCOMPLETE 0x40\n+#define REF_INCOMPLETE 0x20\n \n /*\n * A ref_entry represents either a reference or a \"subdirectory\" of\n@@ -252,17 +237,4 @@ struct ref_iterator *cache_ref_iterator_begin(struct ref_cache *cache,\n \t\t\t\t\t const char *prefix,\n \t\t\t\t\t int prime_dir);\n \n-/*\n- * Peel the entry (if possible) and return its new peel_status. If\n- * repeel is true, re-peel the entry even if there is an old peeled\n- * value that is already stored in it.\n- *\n- * It is OK to call this function with a packed reference entry that\n- * might be stale and might even refer to an object that has since\n- * been garbage-collected. In such a case, if the entry has\n- * REF_KNOWS_PEELED then leave the status unchanged and return\n- * PEEL_PEELED or PEEL_NON_TAG; otherwise, return PEEL_INVALID.\n- */\n-enum peel_status peel_entry(struct ref_entry *entry, int repeel);\n-\n #endif /* REFS_REF_CACHE_H */\n-- \n2.14.1\n\n"},{"id":"328361","messageId":"b67c03b2d47ab503e27a2dd3918af42b59766bdb.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"[PATCH v2 16/21] packed_read_raw_ref(): read the reference from the mmapped buffer","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:24Z","receivedAt":"2017-09-19T06:23:28Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Instead of reading the reference from the `ref_cache`, read it\ndirectly from the mmapped buffer.\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 14 +++++++++-----\n 1 file changed, 9 insertions(+), 5 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 53d0b7e3d6..2cf2f7f73d 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -875,18 +875,22 @@ static int packed_read_raw_ref(struct ref_store *ref_store,\n {\n \tstruct packed_ref_store *refs =\n \t\tpacked_downcast(ref_store, REF_STORE_READ, \"read_raw_ref\");\n-\n-\tstruct ref_entry *entry;\n+\tstruct packed_ref_cache *packed_refs = get_packed_ref_cache(refs);\n+\tconst char *rec;\n \n \t*type = 0;\n \n-\tentry = get_packed_ref(refs, refname);\n-\tif (!entry) {\n+\trec = find_reference_location(packed_refs, refname, 1);\n+\n+\tif (!rec) {\n+\t\t/* refname is not a packed reference. */\n \t\terrno = ENOENT;\n \t\treturn -1;\n \t}\n \n-\thashcpy(sha1, entry->u.value.oid.hash);\n+\tif (get_sha1_hex(rec, sha1))\n+\t\tdie_invalid_line(refs->path, rec, packed_refs->eof - rec);\n+\n \t*type = REF_ISPACKED;\n \treturn 0;\n }\n-- \n2.14.1\n\n"},{"id":"328362","messageId":"7e2152dc4d05bee9e822c4a9690a2c9d3b2fce6b.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"[PATCH v2 20/21] mmapped_ref_iterator: inline into `packed_ref_iterator`","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:28Z","receivedAt":"2017-09-19T06:23:30Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Since `packed_ref_iterator` is now delegating to\n`mmapped_ref_iterator` rather than `cache_ref_iterator` to do the\nheavy lifting, there is no need to keep the two iterators separate. So\n\"inline\" `mmapped_ref_iterator` into `packed_ref_iterator`. This\nremoves a bunch of boilerplate.\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 284 ++++++++++++++++++++------------------------------\n 1 file changed, 114 insertions(+), 170 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex b1571872fa..92b837a237 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -225,157 +225,6 @@ static NORETURN void die_invalid_line(const char *path,\n \n }\n \n-/*\n- * This value is set in `base.flags` if the peeled value of the\n- * current reference is known. In that case, `peeled` contains the\n- * correct peeled value for the reference, which might be `null_sha1`\n- * if the reference is not a tag or if it is broken.\n- */\n-#define REF_KNOWS_PEELED 0x40\n-\n-/*\n- * An iterator over a packed-refs file that is currently mmapped.\n- */\n-struct mmapped_ref_iterator {\n-\tstruct ref_iterator base;\n-\n-\tstruct packed_ref_cache *packed_refs;\n-\n-\t/* The current position in the mmapped file: */\n-\tconst char *pos;\n-\n-\t/* The end of the mmapped file: */\n-\tconst char *eof;\n-\n-\tstruct object_id oid, peeled;\n-\n-\tstruct strbuf refname_buf;\n-};\n-\n-static int mmapped_ref_iterator_advance(struct ref_iterator *ref_iterator)\n-{\n-\tstruct mmapped_ref_iterator *iter =\n-\t\t(struct mmapped_ref_iterator *)ref_iterator;\n-\tconst char *p = iter->pos, *eol;\n-\n-\tstrbuf_reset(&iter->refname_buf);\n-\n-\tif (iter->pos == iter->eof)\n-\t\treturn ref_iterator_abort(ref_iterator);\n-\n-\titer->base.flags = REF_ISPACKED;\n-\n-\tif (iter->eof - p < GIT_SHA1_HEXSZ + 2 ||\n-\t parse_oid_hex(p, &iter->oid, &p) ||\n-\t !isspace(*p++))\n-\t\tdie_invalid_line(iter->packed_refs->refs->path,\n-\t\t\t\t iter->pos, iter->eof - iter->pos);\n-\n-\teol = memchr(p, '\\n', iter->eof - p);\n-\tif (!eol)\n-\t\tdie_unterminated_line(iter->packed_refs->refs->path,\n-\t\t\t\t iter->pos, iter->eof - iter->pos);\n-\n-\tstrbuf_add(&iter->refname_buf, p, eol - p);\n-\titer->base.refname = iter->refname_buf.buf;\n-\n-\tif (check_refname_format(iter->base.refname, REFNAME_ALLOW_ONELEVEL)) {\n-\t\tif (!refname_is_safe(iter->base.refname))\n-\t\t\tdie(\"packed refname is dangerous: %s\",\n-\t\t\t iter->base.refname);\n-\t\toidclr(&iter->oid);\n-\t\titer->base.flags |= REF_BAD_NAME | REF_ISBROKEN;\n-\t}\n-\tif (iter->packed_refs->peeled == PEELED_FULLY ||\n-\t (iter->packed_refs->peeled == PEELED_TAGS &&\n-\t starts_with(iter->base.refname, \"refs/tags/\")))\n-\t\titer->base.flags |= REF_KNOWS_PEELED;\n-\n-\titer->pos = eol + 1;\n-\n-\tif (iter->pos < iter->eof && *iter->pos == '^') {\n-\t\tp = iter->pos + 1;\n-\t\tif (iter->eof - p < GIT_SHA1_HEXSZ + 1 ||\n-\t\t parse_oid_hex(p, &iter->peeled, &p) ||\n-\t\t *p++ != '\\n')\n-\t\t\tdie_invalid_line(iter->packed_refs->refs->path,\n-\t\t\t\t\t iter->pos, iter->eof - iter->pos);\n-\t\titer->pos = p;\n-\n-\t\t/*\n-\t\t * Regardless of what the file header said, we\n-\t\t * definitely know the value of *this* reference. But\n-\t\t * we suppress it if the reference is broken:\n-\t\t */\n-\t\tif ((iter->base.flags & REF_ISBROKEN)) {\n-\t\t\toidclr(&iter->peeled);\n-\t\t\titer->base.flags &= ~REF_KNOWS_PEELED;\n-\t\t} else {\n-\t\t\titer->base.flags |= REF_KNOWS_PEELED;\n-\t\t}\n-\t} else {\n-\t\toidclr(&iter->peeled);\n-\t}\n-\n-\treturn ITER_OK;\n-}\n-\n-static int mmapped_ref_iterator_peel(struct ref_iterator *ref_iterator,\n-\t\t\t\t struct object_id *peeled)\n-{\n-\tstruct mmapped_ref_iterator *iter =\n-\t\t(struct mmapped_ref_iterator *)ref_iterator;\n-\n-\tif ((iter->base.flags & REF_KNOWS_PEELED)) {\n-\t\toidcpy(peeled, &iter->peeled);\n-\t\treturn is_null_oid(&iter->peeled) ? -1 : 0;\n-\t} else if ((iter->base.flags & (REF_ISBROKEN | REF_ISSYMREF))) {\n-\t\treturn -1;\n-\t} else {\n-\t\treturn !!peel_object(iter->oid.hash, peeled->hash);\n-\t}\n-}\n-\n-static int mmapped_ref_iterator_abort(struct ref_iterator *ref_iterator)\n-{\n-\tstruct mmapped_ref_iterator *iter =\n-\t\t(struct mmapped_ref_iterator *)ref_iterator;\n-\n-\trelease_packed_ref_cache(iter->packed_refs);\n-\tstrbuf_release(&iter->refname_buf);\n-\tbase_ref_iterator_free(ref_iterator);\n-\treturn ITER_DONE;\n-}\n-\n-static struct ref_iterator_vtable mmapped_ref_iterator_vtable = {\n-\tmmapped_ref_iterator_advance,\n-\tmmapped_ref_iterator_peel,\n-\tmmapped_ref_iterator_abort\n-};\n-\n-struct ref_iterator *mmapped_ref_iterator_begin(\n-\t\tstruct packed_ref_cache *packed_refs,\n-\t\tconst char *pos, const char *eof)\n-{\n-\tstruct mmapped_ref_iterator *iter = xcalloc(1, sizeof(*iter));\n-\tstruct ref_iterator *ref_iterator = &iter->base;\n-\n-\tif (!packed_refs->buf)\n-\t\treturn empty_ref_iterator_begin();\n-\n-\tbase_ref_iterator_init(ref_iterator, &mmapped_ref_iterator_vtable, 1);\n-\n-\titer->packed_refs = packed_refs;\n-\tacquire_packed_ref_cache(iter->packed_refs);\n-\titer->pos = pos;\n-\titer->eof = eof;\n-\tstrbuf_init(&iter->refname_buf, 0);\n-\n-\titer->base.oid = &iter->oid;\n-\n-\treturn ref_iterator;\n-}\n-\n struct packed_ref_entry {\n \tconst char *start;\n \tsize_t len;\n@@ -857,38 +706,120 @@ static int packed_read_raw_ref(struct ref_store *ref_store,\n \treturn 0;\n }\n \n+/*\n+ * This value is set in `base.flags` if the peeled value of the\n+ * current reference is known. In that case, `peeled` contains the\n+ * correct peeled value for the reference, which might be `null_sha1`\n+ * if the reference is not a tag or if it is broken.\n+ */\n+#define REF_KNOWS_PEELED 0x40\n+\n+/*\n+ * An iterator over a packed-refs file that is currently mmapped.\n+ */\n struct packed_ref_iterator {\n \tstruct ref_iterator base;\n \n-\tstruct packed_ref_cache *cache;\n-\tstruct ref_iterator *iter0;\n+\tstruct packed_ref_cache *packed_refs;\n+\n+\t/* The current position in the mmapped file: */\n+\tconst char *pos;\n+\n+\t/* The end of the mmapped file: */\n+\tconst char *eof;\n+\n+\tstruct object_id oid, peeled;\n+\n+\tstruct strbuf refname_buf;\n+\n \tunsigned int flags;\n };\n \n+static int next_record(struct packed_ref_iterator *iter)\n+{\n+\tconst char *p = iter->pos, *eol;\n+\n+\tstrbuf_reset(&iter->refname_buf);\n+\n+\tif (iter->pos == iter->eof)\n+\t\treturn ITER_DONE;\n+\n+\titer->base.flags = REF_ISPACKED;\n+\n+\tif (iter->eof - p < GIT_SHA1_HEXSZ + 2 ||\n+\t parse_oid_hex(p, &iter->oid, &p) ||\n+\t !isspace(*p++))\n+\t\tdie_invalid_line(iter->packed_refs->refs->path,\n+\t\t\t\t iter->pos, iter->eof - iter->pos);\n+\n+\teol = memchr(p, '\\n', iter->eof - p);\n+\tif (!eol)\n+\t\tdie_unterminated_line(iter->packed_refs->refs->path,\n+\t\t\t\t iter->pos, iter->eof - iter->pos);\n+\n+\tstrbuf_add(&iter->refname_buf, p, eol - p);\n+\titer->base.refname = iter->refname_buf.buf;\n+\n+\tif (check_refname_format(iter->base.refname, REFNAME_ALLOW_ONELEVEL)) {\n+\t\tif (!refname_is_safe(iter->base.refname))\n+\t\t\tdie(\"packed refname is dangerous: %s\",\n+\t\t\t iter->base.refname);\n+\t\toidclr(&iter->oid);\n+\t\titer->base.flags |= REF_BAD_NAME | REF_ISBROKEN;\n+\t}\n+\tif (iter->packed_refs->peeled == PEELED_FULLY ||\n+\t (iter->packed_refs->peeled == PEELED_TAGS &&\n+\t starts_with(iter->base.refname, \"refs/tags/\")))\n+\t\titer->base.flags |= REF_KNOWS_PEELED;\n+\n+\titer->pos = eol + 1;\n+\n+\tif (iter->pos < iter->eof && *iter->pos == '^') {\n+\t\tp = iter->pos + 1;\n+\t\tif (iter->eof - p < GIT_SHA1_HEXSZ + 1 ||\n+\t\t parse_oid_hex(p, &iter->peeled, &p) ||\n+\t\t *p++ != '\\n')\n+\t\t\tdie_invalid_line(iter->packed_refs->refs->path,\n+\t\t\t\t\t iter->pos, iter->eof - iter->pos);\n+\t\titer->pos = p;\n+\n+\t\t/*\n+\t\t * Regardless of what the file header said, we\n+\t\t * definitely know the value of *this* reference. But\n+\t\t * we suppress it if the reference is broken:\n+\t\t */\n+\t\tif ((iter->base.flags & REF_ISBROKEN)) {\n+\t\t\toidclr(&iter->peeled);\n+\t\t\titer->base.flags &= ~REF_KNOWS_PEELED;\n+\t\t} else {\n+\t\t\titer->base.flags |= REF_KNOWS_PEELED;\n+\t\t}\n+\t} else {\n+\t\toidclr(&iter->peeled);\n+\t}\n+\n+\treturn ITER_OK;\n+}\n+\n static int packed_ref_iterator_advance(struct ref_iterator *ref_iterator)\n {\n \tstruct packed_ref_iterator *iter =\n \t\t(struct packed_ref_iterator *)ref_iterator;\n \tint ok;\n \n-\twhile ((ok = ref_iterator_advance(iter->iter0)) == ITER_OK) {\n+\twhile ((ok = next_record(iter)) == ITER_OK) {\n \t\tif (iter->flags & DO_FOR_EACH_PER_WORKTREE_ONLY &&\n-\t\t ref_type(iter->iter0->refname) != REF_TYPE_PER_WORKTREE)\n+\t\t ref_type(iter->base.refname) != REF_TYPE_PER_WORKTREE)\n \t\t\tcontinue;\n \n \t\tif (!(iter->flags & DO_FOR_EACH_INCLUDE_BROKEN) &&\n-\t\t !ref_resolves_to_object(iter->iter0->refname,\n-\t\t\t\t\t iter->iter0->oid,\n-\t\t\t\t\t iter->iter0->flags))\n+\t\t !ref_resolves_to_object(iter->base.refname, &iter->oid,\n+\t\t\t\t\t iter->flags))\n \t\t\tcontinue;\n \n-\t\titer->base.refname = iter->iter0->refname;\n-\t\titer->base.oid = iter->iter0->oid;\n-\t\titer->base.flags = iter->iter0->flags;\n \t\treturn ITER_OK;\n \t}\n \n-\titer->iter0 = NULL;\n \tif (ref_iterator_abort(ref_iterator) != ITER_DONE)\n \t\tok = ITER_ERROR;\n \n@@ -901,7 +832,14 @@ static int packed_ref_iterator_peel(struct ref_iterator *ref_iterator,\n \tstruct packed_ref_iterator *iter =\n \t\t(struct packed_ref_iterator *)ref_iterator;\n \n-\treturn ref_iterator_peel(iter->iter0, peeled);\n+\tif ((iter->base.flags & REF_KNOWS_PEELED)) {\n+\t\toidcpy(peeled, &iter->peeled);\n+\t\treturn is_null_oid(&iter->peeled) ? -1 : 0;\n+\t} else if ((iter->base.flags & (REF_ISBROKEN | REF_ISSYMREF))) {\n+\t\treturn -1;\n+\t} else {\n+\t\treturn !!peel_object(iter->oid.hash, peeled->hash);\n+\t}\n }\n \n static int packed_ref_iterator_abort(struct ref_iterator *ref_iterator)\n@@ -910,10 +848,8 @@ static int packed_ref_iterator_abort(struct ref_iterator *ref_iterator)\n \t\t(struct packed_ref_iterator *)ref_iterator;\n \tint ok = ITER_DONE;\n \n-\tif (iter->iter0)\n-\t\tok = ref_iterator_abort(iter->iter0);\n-\n-\trelease_packed_ref_cache(iter->cache);\n+\tstrbuf_release(&iter->refname_buf);\n+\trelease_packed_ref_cache(iter->packed_refs);\n \tbase_ref_iterator_free(ref_iterator);\n \treturn ok;\n }\n@@ -939,6 +875,11 @@ static struct ref_iterator *packed_ref_iterator_begin(\n \t\trequired_flags |= REF_STORE_ODB;\n \trefs = packed_downcast(ref_store, required_flags, \"ref_iterator_begin\");\n \n+\tpacked_refs = get_packed_ref_cache(refs);\n+\n+\tif (!packed_refs->buf)\n+\t\treturn empty_ref_iterator_begin();\n+\n \titer = xcalloc(1, sizeof(*iter));\n \tref_iterator = &iter->base;\n \tbase_ref_iterator_init(ref_iterator, &packed_ref_iterator_vtable, 1);\n@@ -948,7 +889,7 @@ static struct ref_iterator *packed_ref_iterator_begin(\n \t * the packed-ref cache is up to date with what is on disk,\n \t * and re-reads it if not.\n \t */\n-\titer->cache = packed_refs = get_packed_ref_cache(refs);\n+\titer->packed_refs = packed_refs;\n \tacquire_packed_ref_cache(packed_refs);\n \n \tif (prefix && *prefix)\n@@ -956,8 +897,11 @@ static struct ref_iterator *packed_ref_iterator_begin(\n \telse\n \t\tstart = packed_refs->buf + packed_refs->header_len;\n \n-\titer->iter0 = mmapped_ref_iterator_begin(packed_refs,\n-\t\t\t\t\t\t start, packed_refs->eof);\n+\titer->pos = start;\n+\titer->eof = packed_refs->eof;\n+\tstrbuf_init(&iter->refname_buf, 0);\n+\n+\titer->base.oid = &iter->oid;\n \n \titer->flags = flags;\n \n-- \n2.14.1\n\n"},{"id":"328363","messageId":"20d7a38b6f65c78df5979923f012dcfbf5ed4a55.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"[PATCH v2 21/21] packed-backend.c: rename a bunch of things and update comments","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:29Z","receivedAt":"2017-09-19T06:23:33Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"We've made huge changes to this file, and some of the old names and\ncomments are no longer very fitting. So rename a bunch of things:\n\n* `struct packed_ref_cache` → `struct snapshot`\n* `acquire_packed_ref_cache()` → `acquire_snapshot()`\n* `release_packed_ref_buffer()` → `clear_snapshot_buffer()`\n* `release_packed_ref_cache()` → `release_snapshot()`\n* `clear_packed_ref_cache()` → `clear_snapshot()`\n* `struct packed_ref_entry` → `struct snapshot_record`\n* `cmp_packed_ref_entries()` → `cmp_packed_ref_records()`\n* `cmp_entry_to_refname()` → `cmp_record_to_refname()`\n* `sort_packed_refs()` → `sort_snapshot()`\n* `read_packed_refs()` → `create_snapshot()`\n* `validate_packed_ref_cache()` → `validate_snapshot()`\n* `get_packed_ref_cache()` → `get_snapshot()`\n* Renamed local variables and struct members accordingly.\n\nAlso update a bunch of comments to reflect the renaming and the\naccumulated changes that the code has undergone.\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 422 +++++++++++++++++++++++++++-----------------------\n 1 file changed, 232 insertions(+), 190 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 92b837a237..b9351da843 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -37,10 +37,30 @@ static enum mmap_strategy mmap_strategy = MMAP_OK;\n \n struct packed_ref_store;\n \n-struct packed_ref_cache {\n+/*\n+ * A `snapshot` represents one snapshot of a `packed-refs` file.\n+ *\n+ * Normally, this will be a mmapped view of the contents of the\n+ * `packed-refs` file at the time the snapshot was created. However,\n+ * if the `packed-refs` file was not sorted, this might point at heap\n+ * memory holding the contents of the `packed-refs` file with its\n+ * records sorted by refname.\n+ *\n+ * `snapshot` instances are reference counted (via\n+ * `acquire_snapshot()` and `release_snapshot()`). This is to prevent\n+ * an instance from disappearing while an iterator is still iterating\n+ * over it. Instances are garbage collected when their `referrers`\n+ * count goes to zero.\n+ *\n+ * The most recent `snapshot`, if available, is referenced by the\n+ * `packed_ref_store`. Its freshness is checked whenever\n+ * `get_snapshot()` is called; if the existing snapshot is obsolete, a\n+ * new snapshot is taken.\n+ */\n+struct snapshot {\n \t/*\n \t * A back-pointer to the packed_ref_store with which this\n-\t * cache is associated:\n+\t * snapshot is associated:\n \t */\n \tstruct packed_ref_store *refs;\n \n@@ -61,26 +81,42 @@ struct packed_ref_cache {\n \tsize_t header_len;\n \n \t/*\n-\t * What is the peeled state of this cache? (This is usually\n-\t * determined from the header of the \"packed-refs\" file.)\n+\t * What is the peeled state of the `packed-refs` file that\n+\t * this snapshot represents? (This is usually determined from\n+\t * the file's header.)\n \t */\n \tenum { PEELED_NONE, PEELED_TAGS, PEELED_FULLY } peeled;\n \n \t/*\n-\t * Count of references to the data structure in this instance,\n-\t * including the pointer from files_ref_store::packed if any.\n-\t * The data will not be freed as long as the reference count\n-\t * is nonzero.\n+\t * Count of references to this instance, including the pointer\n+\t * from `packed_ref_store::snapshot`, if any. The instance\n+\t * will not be freed as long as the reference count is\n+\t * nonzero.\n \t */\n \tunsigned int referrers;\n \n-\t/* The metadata from when this packed-refs cache was read */\n+\t/*\n+\t * The metadata of the `packed-refs` file from which this\n+\t * snapshot was created, used to tell if the file has been\n+\t * replaced since we read it.\n+\t */\n \tstruct stat_validity validity;\n };\n \n /*\n- * A container for `packed-refs`-related data. It is not (yet) a\n- * `ref_store`.\n+ * A `ref_store` representing references stored in a `packed-refs`\n+ * file. It implements the `ref_store` interface, though it has some\n+ * limitations:\n+ *\n+ * - It cannot store symbolic references.\n+ *\n+ * - It cannot store reflogs.\n+ *\n+ * - It does not support reference renaming (though it could).\n+ *\n+ * On the other hand, it can be locked outside of a reference\n+ * transaction. In that case, it remains locked even after the\n+ * transaction is done and the new `packed-refs` file is activated.\n */\n struct packed_ref_store {\n \tstruct ref_store base;\n@@ -91,10 +127,10 @@ struct packed_ref_store {\n \tchar *path;\n \n \t/*\n-\t * A cache of the values read from the `packed-refs` file, if\n-\t * it might still be current; otherwise, NULL.\n+\t * A snapshot of the values read from the `packed-refs` file,\n+\t * if it might still be current; otherwise, NULL.\n \t */\n-\tstruct packed_ref_cache *cache;\n+\tstruct snapshot *snapshot;\n \n \t/*\n \t * Lock used for the \"packed-refs\" file. Note that this (and\n@@ -111,43 +147,42 @@ struct packed_ref_store {\n };\n \n /*\n- * Increment the reference count of *packed_refs.\n+ * Increment the reference count of `*snapshot`.\n */\n-static void acquire_packed_ref_cache(struct packed_ref_cache *packed_refs)\n+static void acquire_snapshot(struct snapshot *snapshot)\n {\n-\tpacked_refs->referrers++;\n+\tsnapshot->referrers++;\n }\n \n /*\n- * If the buffer in `packed_refs` is active, then either munmap the\n+ * If the buffer in `snapshot` is active, then either munmap the\n * memory and close the file, or free the memory. Then set the buffer\n * pointers to NULL.\n */\n-static void release_packed_ref_buffer(struct packed_ref_cache *packed_refs)\n+static void clear_snapshot_buffer(struct snapshot *snapshot)\n {\n-\tif (packed_refs->mmapped) {\n-\t\tif (munmap(packed_refs->buf,\n-\t\t\t packed_refs->eof - packed_refs->buf))\n+\tif (snapshot->mmapped) {\n+\t\tif (munmap(snapshot->buf, snapshot->eof - snapshot->buf))\n \t\t\tdie_errno(\"error ummapping packed-refs file %s\",\n-\t\t\t\t packed_refs->refs->path);\n-\t\tpacked_refs->mmapped = 0;\n+\t\t\t\t snapshot->refs->path);\n+\t\tsnapshot->mmapped = 0;\n \t} else {\n-\t\tfree(packed_refs->buf);\n+\t\tfree(snapshot->buf);\n \t}\n-\tpacked_refs->buf = packed_refs->eof = NULL;\n-\tpacked_refs->header_len = 0;\n+\tsnapshot->buf = snapshot->eof = NULL;\n+\tsnapshot->header_len = 0;\n }\n \n /*\n- * Decrease the reference count of *packed_refs. If it goes to zero,\n- * free *packed_refs and return true; otherwise return false.\n+ * Decrease the reference count of `*snapshot`. If it goes to zero,\n+ * free `*snapshot` and return true; otherwise return false.\n */\n-static int release_packed_ref_cache(struct packed_ref_cache *packed_refs)\n+static int release_snapshot(struct snapshot *snapshot)\n {\n-\tif (!--packed_refs->referrers) {\n-\t\tstat_validity_clear(&packed_refs->validity);\n-\t\trelease_packed_ref_buffer(packed_refs);\n-\t\tfree(packed_refs);\n+\tif (!--snapshot->referrers) {\n+\t\tstat_validity_clear(&snapshot->validity);\n+\t\tclear_snapshot_buffer(snapshot);\n+\t\tfree(snapshot);\n \t\treturn 1;\n \t} else {\n \t\treturn 0;\n@@ -192,13 +227,13 @@ static struct packed_ref_store *packed_downcast(struct ref_store *ref_store,\n \treturn refs;\n }\n \n-static void clear_packed_ref_cache(struct packed_ref_store *refs)\n+static void clear_snapshot(struct packed_ref_store *refs)\n {\n-\tif (refs->cache) {\n-\t\tstruct packed_ref_cache *cache = refs->cache;\n+\tif (refs->snapshot) {\n+\t\tstruct snapshot *snapshot = refs->snapshot;\n \n-\t\trefs->cache = NULL;\n-\t\trelease_packed_ref_cache(cache);\n+\t\trefs->snapshot = NULL;\n+\t\trelease_snapshot(snapshot);\n \t}\n }\n \n@@ -225,14 +260,14 @@ static NORETURN void die_invalid_line(const char *path,\n \n }\n \n-struct packed_ref_entry {\n+struct snapshot_record {\n \tconst char *start;\n \tsize_t len;\n };\n \n-static int cmp_packed_ref_entries(const void *v1, const void *v2)\n+static int cmp_packed_ref_records(const void *v1, const void *v2)\n {\n-\tconst struct packed_ref_entry *e1 = v1, *e2 = v2;\n+\tconst struct snapshot_record *e1 = v1, *e2 = v2;\n \tconst char *r1 = e1->start + GIT_SHA1_HEXSZ + 1;\n \tconst char *r2 = e2->start + GIT_SHA1_HEXSZ + 1;\n \n@@ -251,10 +286,10 @@ static int cmp_packed_ref_entries(const void *v1, const void *v2)\n }\n \n /*\n- * Compare a packed-refs record pointed to by `rec` to the specified\n- * NUL-terminated refname.\n+ * Compare a snapshot record at `rec` to the specified NUL-terminated\n+ * refname.\n */\n-static int cmp_entry_to_refname(const char *rec, const char *refname)\n+static int cmp_record_to_refname(const char *rec, const char *refname)\n {\n \tconst char *r1 = rec + GIT_SHA1_HEXSZ + 1;\n \tconst char *r2 = refname;\n@@ -272,31 +307,30 @@ static int cmp_entry_to_refname(const char *rec, const char *refname)\n }\n \n /*\n- * `packed_refs->buf` is not known to be sorted. Check whether it is,\n- * and if not, sort it into new memory and munmap/free the old\n- * storage.\n+ * `snapshot->buf` is not known to be sorted. Check whether it is, and\n+ * if not, sort it into new memory and munmap/free the old storage.\n */\n-static void sort_packed_refs(struct packed_ref_cache *packed_refs)\n+static void sort_snapshot(struct snapshot *snapshot)\n {\n-\tstruct packed_ref_entry *entries = NULL;\n+\tstruct snapshot_record *records = NULL;\n \tsize_t alloc = 0, nr = 0;\n \tint sorted = 1;\n \tconst char *pos, *eof, *eol;\n \tsize_t len, i;\n \tchar *new_buffer, *dst;\n \n-\tpos = packed_refs->buf + packed_refs->header_len;\n-\teof = packed_refs->eof;\n+\tpos = snapshot->buf + snapshot->header_len;\n+\teof = snapshot->eof;\n \tlen = eof - pos;\n \n \tif (!len)\n \t\treturn;\n \n \t/*\n-\t * Initialize entries based on a crude estimate of the number\n+\t * Initialize records based on a crude estimate of the number\n \t * of references in the file (we'll grow it below if needed):\n \t */\n-\tALLOC_GROW(entries, len / 80 + 20, alloc);\n+\tALLOC_GROW(records, len / 80 + 20, alloc);\n \n \twhile (pos < eof) {\n \t\teol = memchr(pos, '\\n', eof - pos);\n@@ -304,7 +338,7 @@ static void sort_packed_refs(struct packed_ref_cache *packed_refs)\n \t\t\t/* The safety check should prevent this. */\n \t\t\tBUG(\"unterminated line found in packed-refs\");\n \t\tif (eol - pos < GIT_SHA1_HEXSZ + 2)\n-\t\t\tdie_invalid_line(packed_refs->refs->path,\n+\t\t\tdie_invalid_line(snapshot->refs->path,\n \t\t\t\t\t pos, eof - pos);\n \t\teol++;\n \t\tif (eol < eof && *eol == '^') {\n@@ -321,15 +355,15 @@ static void sort_packed_refs(struct packed_ref_cache *packed_refs)\n \t\t\teol++;\n \t\t}\n \n-\t\tALLOC_GROW(entries, nr + 1, alloc);\n-\t\tentries[nr].start = pos;\n-\t\tentries[nr].len = eol - pos;\n+\t\tALLOC_GROW(records, nr + 1, alloc);\n+\t\trecords[nr].start = pos;\n+\t\trecords[nr].len = eol - pos;\n \t\tnr++;\n \n \t\tif (sorted &&\n \t\t nr > 1 &&\n-\t\t cmp_packed_ref_entries(&entries[nr - 2],\n-\t\t\t\t\t &entries[nr - 1]) >= 0)\n+\t\t cmp_packed_ref_records(&records[nr - 2],\n+\t\t\t\t\t &records[nr - 1]) >= 0)\n \t\t\tsorted = 0;\n \n \t\tpos = eol;\n@@ -338,31 +372,31 @@ static void sort_packed_refs(struct packed_ref_cache *packed_refs)\n \tif (sorted)\n \t\tgoto cleanup;\n \n-\t/* We need to sort the memory. First we sort the entries array: */\n-\tQSORT(entries, nr, cmp_packed_ref_entries);\n+\t/* We need to sort the memory. First we sort the records array: */\n+\tQSORT(records, nr, cmp_packed_ref_records);\n \n \t/*\n \t * Allocate a new chunk of memory, and copy the old memory to\n-\t * the new in the order indicated by `entries` (not bothering\n+\t * the new in the order indicated by `records` (not bothering\n \t * with the header line):\n \t */\n \tnew_buffer = xmalloc(len);\n \tfor (dst = new_buffer, i = 0; i < nr; i++) {\n-\t\tmemcpy(dst, entries[i].start, entries[i].len);\n-\t\tdst += entries[i].len;\n+\t\tmemcpy(dst, records[i].start, records[i].len);\n+\t\tdst += records[i].len;\n \t}\n \n \t/*\n \t * Now munmap the old buffer and use the sorted buffer in its\n \t * place:\n \t */\n-\trelease_packed_ref_buffer(packed_refs);\n-\tpacked_refs->buf = new_buffer;\n-\tpacked_refs->eof = new_buffer + len;\n-\tpacked_refs->header_len = 0;\n+\tclear_snapshot_buffer(snapshot);\n+\tsnapshot->buf = new_buffer;\n+\tsnapshot->eof = new_buffer + len;\n+\tsnapshot->header_len = 0;\n \n cleanup:\n-\tfree(entries);\n+\tfree(records);\n }\n \n /*\n@@ -406,10 +440,10 @@ static const char *find_end_of_record(const char *p, const char *end)\n * (GIT_SHA1_HEXSZ + 1) characters before the LF. Die if either of\n * these checks fails.\n */\n-static void verify_buffer_safe(struct packed_ref_cache *packed_refs)\n+static void verify_buffer_safe(struct snapshot *snapshot)\n {\n-\tconst char *buf = packed_refs->buf + packed_refs->header_len;\n-\tconst char *eof = packed_refs->eof;\n+\tconst char *buf = snapshot->buf + snapshot->header_len;\n+\tconst char *eof = snapshot->eof;\n \tconst char *last_line;\n \n \tif (buf == eof)\n@@ -417,23 +451,22 @@ static void verify_buffer_safe(struct packed_ref_cache *packed_refs)\n \n \tlast_line = find_start_of_record(buf, eof - 1);\n \tif (*(eof - 1) != '\\n' || eof - last_line < GIT_SHA1_HEXSZ + 2)\n-\t\tdie_invalid_line(packed_refs->refs->path,\n+\t\tdie_invalid_line(snapshot->refs->path,\n \t\t\t\t last_line, eof - last_line);\n }\n \n /*\n * Depending on `mmap_strategy`, either mmap or read the contents of\n- * the `packed-refs` file into the `packed_refs` instance. Return 1 if\n- * the file existed and was read, or 0 if the file was absent. Die on\n- * errors.\n+ * the `packed-refs` file into the snapshot. Return 1 if the file\n+ * existed and was read, or 0 if the file was absent. Die on errors.\n */\n-static int load_contents(struct packed_ref_cache *packed_refs)\n+static int load_contents(struct snapshot *snapshot)\n {\n \tint fd;\n \tstruct stat st;\n \tsize_t size, bytes_read;\n \n-\tfd = open(packed_refs->refs->path, O_RDONLY);\n+\tfd = open(snapshot->refs->path, O_RDONLY);\n \tif (fd < 0) {\n \t\tif (errno == ENOENT) {\n \t\t\t/*\n@@ -445,30 +478,30 @@ static int load_contents(struct packed_ref_cache *packed_refs)\n \t\t\t */\n \t\t\treturn 0;\n \t\t} else {\n-\t\t\tdie_errno(\"couldn't read %s\", packed_refs->refs->path);\n+\t\t\tdie_errno(\"couldn't read %s\", snapshot->refs->path);\n \t\t}\n \t}\n \n-\tstat_validity_update(&packed_refs->validity, fd);\n+\tstat_validity_update(&snapshot->validity, fd);\n \n \tif (fstat(fd, &st) < 0)\n-\t\tdie_errno(\"couldn't stat %s\", packed_refs->refs->path);\n+\t\tdie_errno(\"couldn't stat %s\", snapshot->refs->path);\n \tsize = xsize_t(st.st_size);\n \n \tswitch (mmap_strategy) {\n \tcase MMAP_NONE:\n-\t\tpacked_refs->buf = xmalloc(size);\n-\t\tbytes_read = read_in_full(fd, packed_refs->buf, size);\n+\t\tsnapshot->buf = xmalloc(size);\n+\t\tbytes_read = read_in_full(fd, snapshot->buf, size);\n \t\tif (bytes_read < 0 || bytes_read != size)\n-\t\t\tdie_errno(\"couldn't read %s\", packed_refs->refs->path);\n-\t\tpacked_refs->eof = packed_refs->buf + size;\n-\t\tpacked_refs->mmapped = 0;\n+\t\t\tdie_errno(\"couldn't read %s\", snapshot->refs->path);\n+\t\tsnapshot->eof = snapshot->buf + size;\n+\t\tsnapshot->mmapped = 0;\n \t\tbreak;\n \tcase MMAP_TEMPORARY:\n \tcase MMAP_OK:\n-\t\tpacked_refs->buf = xmmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);\n-\t\tpacked_refs->eof = packed_refs->buf + size;\n-\t\tpacked_refs->mmapped = 1;\n+\t\tsnapshot->buf = xmmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\t\tsnapshot->eof = snapshot->buf + size;\n+\t\tsnapshot->mmapped = 1;\n \t\tbreak;\n \t}\n \tclose(fd);\n@@ -477,7 +510,7 @@ static int load_contents(struct packed_ref_cache *packed_refs)\n }\n \n /*\n- * Find the place in `cache->buf` where the start of the record for\n+ * Find the place in `snapshot->buf` where the start of the record for\n * `refname` starts. If `mustexist` is true and the reference doesn't\n * exist, then return NULL. If `mustexist` is false and the reference\n * doesn't exist, then return the point where that reference would be\n@@ -485,10 +518,10 @@ static int load_contents(struct packed_ref_cache *packed_refs)\n * reference name; for example, one could search for \"refs/replace/\"\n * to find the start of any replace references.\n *\n- * The record is sought using a binary search, so `cache->buf` must be\n- * sorted.\n+ * The record is sought using a binary search, so `snapshot->buf` must\n+ * be sorted.\n */\n-static const char *find_reference_location(struct packed_ref_cache *cache,\n+static const char *find_reference_location(struct snapshot *snapshot,\n \t\t\t\t\t const char *refname, int mustexist)\n {\n \t/*\n@@ -505,13 +538,13 @@ static const char *find_reference_location(struct packed_ref_cache *cache,\n \t * preceding records all have reference names that come\n \t * *before* `refname`.\n \t */\n-\tconst char *lo = cache->buf + cache->header_len;\n+\tconst char *lo = snapshot->buf + snapshot->header_len;\n \n \t/*\n \t * A pointer to a the first character of a record whose\n \t * reference name comes *after* `refname`.\n \t */\n-\tconst char *hi = cache->eof;\n+\tconst char *hi = snapshot->eof;\n \n \twhile (lo < hi) {\n \t\tconst char *mid, *rec;\n@@ -519,7 +552,7 @@ static const char *find_reference_location(struct packed_ref_cache *cache,\n \n \t\tmid = lo + (hi - lo) / 2;\n \t\trec = find_start_of_record(lo, mid);\n-\t\tcmp = cmp_entry_to_refname(rec, refname);\n+\t\tcmp = cmp_record_to_refname(rec, refname);\n \t\tif (cmp < 0) {\n \t\t\tlo = find_end_of_record(mid, hi);\n \t\t} else if (cmp > 0) {\n@@ -536,9 +569,9 @@ static const char *find_reference_location(struct packed_ref_cache *cache,\n }\n \n /*\n- * Read from the `packed-refs` file into a newly-allocated\n- * `packed_ref_cache` and return it. The return value will already\n- * have its reference count incremented.\n+ * Create a newly-allocated `snapshot` of the `packed-refs` file in\n+ * its current state and return it. The return value will already have\n+ * its reference count incremented.\n *\n * A comment line of the form \"# pack-refs with: \" may contain zero or\n * more traits. We interpret the traits as follows:\n@@ -568,116 +601,117 @@ static const char *find_reference_location(struct packed_ref_cache *cache,\n *\n * The references in this file are known to be sorted by refname.\n */\n-static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n+static struct snapshot *create_snapshot(struct packed_ref_store *refs)\n {\n-\tstruct packed_ref_cache *packed_refs = xcalloc(1, sizeof(*packed_refs));\n+\tstruct snapshot *snapshot = xcalloc(1, sizeof(*snapshot));\n \tint sorted = 0;\n \n-\tpacked_refs->refs = refs;\n-\tacquire_packed_ref_cache(packed_refs);\n-\tpacked_refs->peeled = PEELED_NONE;\n+\tsnapshot->refs = refs;\n+\tacquire_snapshot(snapshot);\n+\tsnapshot->peeled = PEELED_NONE;\n \n-\tif (!load_contents(packed_refs))\n-\t\treturn packed_refs;\n+\tif (!load_contents(snapshot))\n+\t\treturn snapshot;\n \n \t/* If the file has a header line, process it: */\n-\tif (packed_refs->buf < packed_refs->eof && *packed_refs->buf == '#') {\n+\tif (snapshot->buf < snapshot->eof && *snapshot->buf == '#') {\n \t\tstruct strbuf tmp = STRBUF_INIT;\n \t\tchar *p;\n \t\tconst char *eol;\n \t\tstruct string_list traits = STRING_LIST_INIT_NODUP;\n \n-\t\teol = memchr(packed_refs->buf, '\\n',\n-\t\t\t packed_refs->eof - packed_refs->buf);\n+\t\teol = memchr(snapshot->buf, '\\n',\n+\t\t\t snapshot->eof - snapshot->buf);\n \t\tif (!eol)\n \t\t\tdie_unterminated_line(refs->path,\n-\t\t\t\t\t packed_refs->buf,\n-\t\t\t\t\t packed_refs->eof - packed_refs->buf);\n+\t\t\t\t\t snapshot->buf,\n+\t\t\t\t\t snapshot->eof - snapshot->buf);\n \n-\t\tstrbuf_add(&tmp, packed_refs->buf, eol - packed_refs->buf);\n+\t\tstrbuf_add(&tmp, snapshot->buf, eol - snapshot->buf);\n \n \t\tif (!skip_prefix(tmp.buf, \"# pack-refs with:\", (const char **)&p))\n \t\t\tdie_invalid_line(refs->path,\n-\t\t\t\t\t packed_refs->buf,\n-\t\t\t\t\t packed_refs->eof - packed_refs->buf);\n+\t\t\t\t\t snapshot->buf,\n+\t\t\t\t\t snapshot->eof - snapshot->buf);\n \n \t\tstring_list_split_in_place(&traits, p, ' ', -1);\n \n \t\tif (unsorted_string_list_has_string(&traits, \"fully-peeled\"))\n-\t\t\tpacked_refs->peeled = PEELED_FULLY;\n+\t\t\tsnapshot->peeled = PEELED_FULLY;\n \t\telse if (unsorted_string_list_has_string(&traits, \"peeled\"))\n-\t\t\tpacked_refs->peeled = PEELED_TAGS;\n+\t\t\tsnapshot->peeled = PEELED_TAGS;\n \n \t\tsorted = unsorted_string_list_has_string(&traits, \"sorted\");\n \n \t\t/* perhaps other traits later as well */\n \n \t\t/* The \"+ 1\" is for the LF character. */\n-\t\tpacked_refs->header_len = eol + 1 - packed_refs->buf;\n+\t\tsnapshot->header_len = eol + 1 - snapshot->buf;\n \n \t\tstring_list_clear(&traits, 0);\n \t\tstrbuf_release(&tmp);\n \t}\n \n-\tverify_buffer_safe(packed_refs);\n+\tverify_buffer_safe(snapshot);\n \n \tif (!sorted) {\n-\t\tsort_packed_refs(packed_refs);\n+\t\tsort_snapshot(snapshot);\n \n \t\t/*\n \t\t * Reordering the records might have moved a short one\n \t\t * to the end of the buffer, so verify the buffer's\n \t\t * safety again:\n \t\t */\n-\t\tverify_buffer_safe(packed_refs);\n+\t\tverify_buffer_safe(snapshot);\n \t}\n \n-\tif (mmap_strategy != MMAP_OK && packed_refs->mmapped) {\n+\tif (mmap_strategy != MMAP_OK && snapshot->mmapped) {\n \t\t/*\n \t\t * We don't want to leave the file mmapped, so we are\n \t\t * forced to make a copy now:\n \t\t */\n-\t\tsize_t size = packed_refs->eof -\n-\t\t\t(packed_refs->buf + packed_refs->header_len);\n+\t\tsize_t size = snapshot->eof -\n+\t\t\t(snapshot->buf + snapshot->header_len);\n \t\tchar *buf_copy = xmalloc(size);\n \n-\t\tmemcpy(buf_copy, packed_refs->buf + packed_refs->header_len, size);\n-\t\trelease_packed_ref_buffer(packed_refs);\n-\t\tpacked_refs->buf = buf_copy;\n-\t\tpacked_refs->eof = buf_copy + size;\n+\t\tmemcpy(buf_copy, snapshot->buf + snapshot->header_len, size);\n+\t\tclear_snapshot_buffer(snapshot);\n+\t\tsnapshot->buf = buf_copy;\n+\t\tsnapshot->eof = buf_copy + size;\n \t}\n \n-\treturn packed_refs;\n+\treturn snapshot;\n }\n \n /*\n- * Check that the packed refs cache (if any) still reflects the\n- * contents of the file. If not, clear the cache.\n+ * Check that `refs->snapshot` (if present) still reflects the\n+ * contents of the `packed-refs` file. If not, clear the snapshot.\n */\n-static void validate_packed_ref_cache(struct packed_ref_store *refs)\n+static void validate_snapshot(struct packed_ref_store *refs)\n {\n-\tif (refs->cache &&\n-\t !stat_validity_check(&refs->cache->validity, refs->path))\n-\t\tclear_packed_ref_cache(refs);\n+\tif (refs->snapshot &&\n+\t !stat_validity_check(&refs->snapshot->validity, refs->path))\n+\t\tclear_snapshot(refs);\n }\n \n /*\n- * Get the packed_ref_cache for the specified packed_ref_store,\n- * creating and populating it if it hasn't been read before or if the\n- * file has been changed (according to its `validity` field) since it\n- * was last read. On the other hand, if we hold the lock, then assume\n- * that the file hasn't been changed out from under us, so skip the\n- * extra `stat()` call in `stat_validity_check()`.\n+ * Get the `snapshot` for the specified packed_ref_store, creating and\n+ * populating it if it hasn't been read before or if the file has been\n+ * changed (according to its `validity` field) since it was last read.\n+ * On the other hand, if we hold the lock, then assume that the file\n+ * hasn't been changed out from under us, so skip the extra `stat()`\n+ * call in `stat_validity_check()`. This function does *not* increase\n+ * the snapshot's reference count on behalf of the caller.\n */\n-static struct packed_ref_cache *get_packed_ref_cache(struct packed_ref_store *refs)\n+static struct snapshot *get_snapshot(struct packed_ref_store *refs)\n {\n \tif (!is_lock_file_locked(&refs->lock))\n-\t\tvalidate_packed_ref_cache(refs);\n+\t\tvalidate_snapshot(refs);\n \n-\tif (!refs->cache)\n-\t\trefs->cache = read_packed_refs(refs);\n+\tif (!refs->snapshot)\n+\t\trefs->snapshot = create_snapshot(refs);\n \n-\treturn refs->cache;\n+\treturn refs->snapshot;\n }\n \n static int packed_read_raw_ref(struct ref_store *ref_store,\n@@ -686,12 +720,12 @@ static int packed_read_raw_ref(struct ref_store *ref_store,\n {\n \tstruct packed_ref_store *refs =\n \t\tpacked_downcast(ref_store, REF_STORE_READ, \"read_raw_ref\");\n-\tstruct packed_ref_cache *packed_refs = get_packed_ref_cache(refs);\n+\tstruct snapshot *snapshot = get_snapshot(refs);\n \tconst char *rec;\n \n \t*type = 0;\n \n-\trec = find_reference_location(packed_refs, refname, 1);\n+\trec = find_reference_location(snapshot, refname, 1);\n \n \tif (!rec) {\n \t\t/* refname is not a packed reference. */\n@@ -700,7 +734,7 @@ static int packed_read_raw_ref(struct ref_store *ref_store,\n \t}\n \n \tif (get_sha1_hex(rec, sha1))\n-\t\tdie_invalid_line(refs->path, rec, packed_refs->eof - rec);\n+\t\tdie_invalid_line(refs->path, rec, snapshot->eof - rec);\n \n \t*type = REF_ISPACKED;\n \treturn 0;\n@@ -715,26 +749,33 @@ static int packed_read_raw_ref(struct ref_store *ref_store,\n #define REF_KNOWS_PEELED 0x40\n \n /*\n- * An iterator over a packed-refs file that is currently mmapped.\n+ * An iterator over a snapshot of a `packed-refs` file.\n */\n struct packed_ref_iterator {\n \tstruct ref_iterator base;\n \n-\tstruct packed_ref_cache *packed_refs;\n+\tstruct snapshot *snapshot;\n \n-\t/* The current position in the mmapped file: */\n+\t/* The current position in the snapshot's buffer: */\n \tconst char *pos;\n \n-\t/* The end of the mmapped file: */\n+\t/* The end of the part of the buffer that will be iterated over: */\n \tconst char *eof;\n \n+\t/* Scratch space for current values: */\n \tstruct object_id oid, peeled;\n-\n \tstruct strbuf refname_buf;\n \n \tunsigned int flags;\n };\n \n+/*\n+ * Move the iterator to the next record in the snapshot, without\n+ * respect for whether the record is actually required by the current\n+ * iteration. Adjust the fields in `iter` and return `ITER_OK` or\n+ * `ITER_DONE`. This function does not free the iterator in the case\n+ * of `ITER_DONE`.\n+ */\n static int next_record(struct packed_ref_iterator *iter)\n {\n \tconst char *p = iter->pos, *eol;\n@@ -749,12 +790,12 @@ static int next_record(struct packed_ref_iterator *iter)\n \tif (iter->eof - p < GIT_SHA1_HEXSZ + 2 ||\n \t parse_oid_hex(p, &iter->oid, &p) ||\n \t !isspace(*p++))\n-\t\tdie_invalid_line(iter->packed_refs->refs->path,\n+\t\tdie_invalid_line(iter->snapshot->refs->path,\n \t\t\t\t iter->pos, iter->eof - iter->pos);\n \n \teol = memchr(p, '\\n', iter->eof - p);\n \tif (!eol)\n-\t\tdie_unterminated_line(iter->packed_refs->refs->path,\n+\t\tdie_unterminated_line(iter->snapshot->refs->path,\n \t\t\t\t iter->pos, iter->eof - iter->pos);\n \n \tstrbuf_add(&iter->refname_buf, p, eol - p);\n@@ -767,8 +808,8 @@ static int next_record(struct packed_ref_iterator *iter)\n \t\toidclr(&iter->oid);\n \t\titer->base.flags |= REF_BAD_NAME | REF_ISBROKEN;\n \t}\n-\tif (iter->packed_refs->peeled == PEELED_FULLY ||\n-\t (iter->packed_refs->peeled == PEELED_TAGS &&\n+\tif (iter->snapshot->peeled == PEELED_FULLY ||\n+\t (iter->snapshot->peeled == PEELED_TAGS &&\n \t starts_with(iter->base.refname, \"refs/tags/\")))\n \t\titer->base.flags |= REF_KNOWS_PEELED;\n \n@@ -779,7 +820,7 @@ static int next_record(struct packed_ref_iterator *iter)\n \t\tif (iter->eof - p < GIT_SHA1_HEXSZ + 1 ||\n \t\t parse_oid_hex(p, &iter->peeled, &p) ||\n \t\t *p++ != '\\n')\n-\t\t\tdie_invalid_line(iter->packed_refs->refs->path,\n+\t\t\tdie_invalid_line(iter->snapshot->refs->path,\n \t\t\t\t\t iter->pos, iter->eof - iter->pos);\n \t\titer->pos = p;\n \n@@ -849,7 +890,7 @@ static int packed_ref_iterator_abort(struct ref_iterator *ref_iterator)\n \tint ok = ITER_DONE;\n \n \tstrbuf_release(&iter->refname_buf);\n-\trelease_packed_ref_cache(iter->packed_refs);\n+\trelease_snapshot(iter->snapshot);\n \tbase_ref_iterator_free(ref_iterator);\n \treturn ok;\n }\n@@ -865,7 +906,7 @@ static struct ref_iterator *packed_ref_iterator_begin(\n \t\tconst char *prefix, unsigned int flags)\n {\n \tstruct packed_ref_store *refs;\n-\tstruct packed_ref_cache *packed_refs;\n+\tstruct snapshot *snapshot;\n \tconst char *start;\n \tstruct packed_ref_iterator *iter;\n \tstruct ref_iterator *ref_iterator;\n@@ -875,30 +916,30 @@ static struct ref_iterator *packed_ref_iterator_begin(\n \t\trequired_flags |= REF_STORE_ODB;\n \trefs = packed_downcast(ref_store, required_flags, \"ref_iterator_begin\");\n \n-\tpacked_refs = get_packed_ref_cache(refs);\n+\t/*\n+\t * Note that `get_snapshot()` internally checks whether the\n+\t * snapshot is up to date with what is on disk, and re-reads\n+\t * it if not.\n+\t */\n+\tsnapshot = get_snapshot(refs);\n \n-\tif (!packed_refs->buf)\n+\tif (!snapshot->buf)\n \t\treturn empty_ref_iterator_begin();\n \n \titer = xcalloc(1, sizeof(*iter));\n \tref_iterator = &iter->base;\n \tbase_ref_iterator_init(ref_iterator, &packed_ref_iterator_vtable, 1);\n \n-\t/*\n-\t * Note that get_packed_ref_cache() internally checks whether\n-\t * the packed-ref cache is up to date with what is on disk,\n-\t * and re-reads it if not.\n-\t */\n-\titer->packed_refs = packed_refs;\n-\tacquire_packed_ref_cache(packed_refs);\n+\titer->snapshot = snapshot;\n+\tacquire_snapshot(snapshot);\n \n \tif (prefix && *prefix)\n-\t\tstart = find_reference_location(packed_refs, prefix, 0);\n+\t\tstart = find_reference_location(snapshot, prefix, 0);\n \telse\n-\t\tstart = packed_refs->buf + packed_refs->header_len;\n+\t\tstart = snapshot->buf + snapshot->header_len;\n \n \titer->pos = start;\n-\titer->eof = packed_refs->eof;\n+\titer->eof = snapshot->eof;\n \tstrbuf_init(&iter->refname_buf, 0);\n \n \titer->base.oid = &iter->oid;\n@@ -962,19 +1003,19 @@ int packed_refs_lock(struct ref_store *ref_store, int flags, struct strbuf *err)\n \n \t/*\n \t * Now that we hold the `packed-refs` lock, make sure that our\n-\t * cache matches the current version of the file. Normally\n-\t * `get_packed_ref_cache()` does that for us, but that\n-\t * function assumes that when the file is locked, any existing\n-\t * cache is still valid. We've just locked the file, but it\n-\t * might have changed the moment *before* we locked it.\n+\t * snapshot matches the current version of the file. Normally\n+\t * `get_snapshot()` does that for us, but that function\n+\t * assumes that when the file is locked, any existing snapshot\n+\t * is still valid. We've just locked the file, but it might\n+\t * have changed the moment *before* we locked it.\n \t */\n-\tvalidate_packed_ref_cache(refs);\n+\tvalidate_snapshot(refs);\n \n \t/*\n \t * Now make sure that the packed-refs file as it exists in the\n-\t * locked state is loaded into the cache:\n+\t * locked state is loaded into the snapshot:\n \t */\n-\tget_packed_ref_cache(refs);\n+\tget_snapshot(refs);\n \treturn 0;\n }\n \n@@ -1001,8 +1042,8 @@ int packed_refs_is_locked(struct ref_store *ref_store)\n }\n \n /*\n- * The packed-refs header line that we write out. Perhaps other\n- * traits will be added later.\n+ * The packed-refs header line that we write out. Perhaps other traits\n+ * will be added later.\n *\n * Note that earlier versions of Git used to parse these traits by\n * looking for \" trait \" in the line. For this reason, the space after\n@@ -1018,9 +1059,9 @@ static int packed_init_db(struct ref_store *ref_store, struct strbuf *err)\n }\n \n /*\n- * Write the packed-refs from the cache to the packed-refs tempfile,\n- * incorporating any changes from `updates`. `updates` must be a\n- * sorted string list whose keys are the refnames and whose util\n+ * Write the packed refs from the current snapshot to the packed-refs\n+ * tempfile, incorporating any changes from `updates`. `updates` must\n+ * be a sorted string list whose keys are the refnames and whose util\n * values are `struct ref_update *`. On error, rollback the tempfile,\n * write an error message to `err`, and return a nonzero value.\n *\n@@ -1261,9 +1302,10 @@ static int packed_transaction_prepare(struct ref_store *ref_store,\n \t/*\n \t * Note that we *don't* skip transactions with zero updates,\n \t * because such a transaction might be executed for the side\n-\t * effect of ensuring that all of the references are peeled.\n-\t * If the caller wants to optimize away empty transactions, it\n-\t * should do so itself.\n+\t * effect of ensuring that all of the references are peeled or\n+\t * ensuring that the `packed-refs` file is sorted. If the\n+\t * caller wants to optimize away empty transactions, it should\n+\t * do so itself.\n \t */\n \n \tdata = xcalloc(1, sizeof(*data));\n@@ -1329,7 +1371,7 @@ static int packed_transaction_finish(struct ref_store *ref_store,\n \tint ret = TRANSACTION_GENERIC_ERROR;\n \tchar *packed_refs_path;\n \n-\tclear_packed_ref_cache(refs);\n+\tclear_snapshot(refs);\n \n \tpacked_refs_path = get_locked_file_path(&refs->lock);\n \tif (rename_tempfile(&refs->tempfile, packed_refs_path)) {\n-- \n2.14.1\n\n"},{"id":"328364","messageId":"4bfae266be39a1ecc217380f4a8b1eafb669f521.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"[PATCH v2 17/21] ref_store: implement `refs_peel_ref()` generically","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:25Z","receivedAt":"2017-09-19T06:23:37Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"We're about to stop storing packed refs in a `ref_cache`. That means\nthat the only way we have left to optimize `peel_ref()` is by checking\nwhether the reference being peeled is the one currently being iterated\nover (in `current_ref_iter`), and if so, using `ref_iterator_peel()`.\nBut this can be done generically; it doesn't have to be implemented\nper-backend.\n\nSo implement `refs_peel_ref()` in `refs.c` and remove the `peel_ref()`\nmethod from the refs API.\n\nThis removes the last callers of a couple of functions, so delete\nthem. More cleanup to come...\n\nSigned-off-by: Michael Haggerty \n---\n refs.c | 18 +++++++++++++++++-\n refs/files-backend.c | 38 --------------------------------------\n refs/packed-backend.c | 36 ------------------------------------\n refs/refs-internal.h | 3 ---\n 4 files changed, 17 insertions(+), 78 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 101c107ee8..c5e6f79c77 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1735,7 +1735,23 @@ int refs_pack_refs(struct ref_store *refs, unsigned int flags)\n int refs_peel_ref(struct ref_store *refs, const char *refname,\n \t\t unsigned char *sha1)\n {\n-\treturn refs->be->peel_ref(refs, refname, sha1);\n+\tint flag;\n+\tunsigned char base[20];\n+\n+\tif (current_ref_iter && current_ref_iter->refname == refname) {\n+\t\tstruct object_id peeled;\n+\n+\t\tif (ref_iterator_peel(current_ref_iter, &peeled))\n+\t\t\treturn -1;\n+\t\thashcpy(sha1, peeled.hash);\n+\t\treturn 0;\n+\t}\n+\n+\tif (refs_read_ref_full(refs, refname,\n+\t\t\t RESOLVE_REF_READING, base, &flag))\n+\t\treturn -1;\n+\n+\treturn peel_object(base, sha1);\n }\n \n int peel_ref(const char *refname, unsigned char *sha1)\ndiff --git a/refs/files-backend.c b/refs/files-backend.c\nindex 35648c89fc..7d12de88d0 100644\n--- a/refs/files-backend.c\n+++ b/refs/files-backend.c\n@@ -655,43 +655,6 @@ static int lock_raw_ref(struct files_ref_store *refs,\n \treturn ret;\n }\n \n-static int files_peel_ref(struct ref_store *ref_store,\n-\t\t\t const char *refname, unsigned char *sha1)\n-{\n-\tstruct files_ref_store *refs =\n-\t\tfiles_downcast(ref_store, REF_STORE_READ | REF_STORE_ODB,\n-\t\t\t \"peel_ref\");\n-\tint flag;\n-\tunsigned char base[20];\n-\n-\tif (current_ref_iter && current_ref_iter->refname == refname) {\n-\t\tstruct object_id peeled;\n-\n-\t\tif (ref_iterator_peel(current_ref_iter, &peeled))\n-\t\t\treturn -1;\n-\t\thashcpy(sha1, peeled.hash);\n-\t\treturn 0;\n-\t}\n-\n-\tif (refs_read_ref_full(ref_store, refname,\n-\t\t\t RESOLVE_REF_READING, base, &flag))\n-\t\treturn -1;\n-\n-\t/*\n-\t * If the reference is packed, read its ref_entry from the\n-\t * cache in the hope that we already know its peeled value.\n-\t * We only try this optimization on packed references because\n-\t * (a) forcing the filling of the loose reference cache could\n-\t * be expensive and (b) loose references anyway usually do not\n-\t * have REF_KNOWS_PEELED.\n-\t */\n-\tif (flag & REF_ISPACKED &&\n-\t !refs_peel_ref(refs->packed_ref_store, refname, sha1))\n-\t\treturn 0;\n-\n-\treturn peel_object(base, sha1);\n-}\n-\n struct files_ref_iterator {\n \tstruct ref_iterator base;\n \n@@ -3012,7 +2975,6 @@ struct ref_storage_be refs_be_files = {\n \tfiles_initial_transaction_commit,\n \n \tfiles_pack_refs,\n-\tfiles_peel_ref,\n \tfiles_create_symref,\n \tfiles_delete_refs,\n \tfiles_rename_ref,\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 2cf2f7f73d..6a930a440c 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -849,26 +849,6 @@ static struct packed_ref_cache *get_packed_ref_cache(struct packed_ref_store *re\n \treturn refs->cache;\n }\n \n-static struct ref_dir *get_packed_ref_dir(struct packed_ref_cache *packed_ref_cache)\n-{\n-\treturn get_ref_dir(packed_ref_cache->cache->root);\n-}\n-\n-static struct ref_dir *get_packed_refs(struct packed_ref_store *refs)\n-{\n-\treturn get_packed_ref_dir(get_packed_ref_cache(refs));\n-}\n-\n-/*\n- * Return the ref_entry for the given refname from the packed\n- * references. If it does not exist, return NULL.\n- */\n-static struct ref_entry *get_packed_ref(struct packed_ref_store *refs,\n-\t\t\t\t\tconst char *refname)\n-{\n-\treturn find_ref_entry(get_packed_refs(refs), refname);\n-}\n-\n static int packed_read_raw_ref(struct ref_store *ref_store,\n \t\t\t const char *refname, unsigned char *sha1,\n \t\t\t struct strbuf *referent, unsigned int *type)\n@@ -895,21 +875,6 @@ static int packed_read_raw_ref(struct ref_store *ref_store,\n \treturn 0;\n }\n \n-static int packed_peel_ref(struct ref_store *ref_store,\n-\t\t\t const char *refname, unsigned char *sha1)\n-{\n-\tstruct packed_ref_store *refs =\n-\t\tpacked_downcast(ref_store, REF_STORE_READ | REF_STORE_ODB,\n-\t\t\t\t\"peel_ref\");\n-\tstruct ref_entry *r = get_packed_ref(refs, refname);\n-\n-\tif (!r || peel_entry(r, 0))\n-\t\treturn -1;\n-\n-\thashcpy(sha1, r->u.value.peeled.hash);\n-\treturn 0;\n-}\n-\n struct packed_ref_iterator {\n \tstruct ref_iterator base;\n \n@@ -1596,7 +1561,6 @@ struct ref_storage_be refs_be_packed = {\n \tpacked_initial_transaction_commit,\n \n \tpacked_pack_refs,\n-\tpacked_peel_ref,\n \tpacked_create_symref,\n \tpacked_delete_refs,\n \tpacked_rename_ref,\ndiff --git a/refs/refs-internal.h b/refs/refs-internal.h\nindex d7f233beba..cc6c373f59 100644\n--- a/refs/refs-internal.h\n+++ b/refs/refs-internal.h\n@@ -562,8 +562,6 @@ typedef int ref_transaction_commit_fn(struct ref_store *refs,\n \t\t\t\t struct strbuf *err);\n \n typedef int pack_refs_fn(struct ref_store *ref_store, unsigned int flags);\n-typedef int peel_ref_fn(struct ref_store *ref_store,\n-\t\t\tconst char *refname, unsigned char *sha1);\n typedef int create_symref_fn(struct ref_store *ref_store,\n \t\t\t const char *ref_target,\n \t\t\t const char *refs_heads_master,\n@@ -668,7 +666,6 @@ struct ref_storage_be {\n \tref_transaction_commit_fn *initial_transaction_commit;\n \n \tpack_refs_fn *pack_refs;\n-\tpeel_ref_fn *peel_ref;\n \tcreate_symref_fn *create_symref;\n \tdelete_refs_fn *delete_refs;\n \trename_ref_fn *rename_ref;\n-- \n2.14.1\n\n"},{"id":"328365","messageId":"a1d50f3a452873f3d845742d378887aac14f7cb6.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"[PATCH v2 06/21] read_packed_refs(): only check for a header at the top of the file","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:14Z","receivedAt":"2017-09-19T06:23:41Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"This tightens up the parsing a bit; previously, stray header-looking\nlines would have been processed.\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 35 ++++++++++++++++++++++++-----------\n 1 file changed, 24 insertions(+), 11 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 154abbd83a..141f02b9c8 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -255,11 +255,34 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \tpos = buf;\n \teof = buf + size;\n \n+\t/* If the file has a header line, process it: */\n+\tif (pos < eof && *pos == '#') {\n+\t\tconst char *traits;\n+\n+\t\teol = memchr(pos, '\\n', eof - pos);\n+\t\tif (!eol)\n+\t\t\tdie_unterminated_line(refs->path, pos, eof - pos);\n+\n+\t\tstrbuf_add(&line, pos, eol + 1 - pos);\n+\n+\t\tif (!skip_prefix(line.buf, \"# pack-refs with:\", &traits))\n+\t\t\tdie_invalid_line(refs->path, pos, eof - pos);\n+\n+\t\tif (strstr(traits, \" fully-peeled \"))\n+\t\t\tpeeled = PEELED_FULLY;\n+\t\telse if (strstr(traits, \" peeled \"))\n+\t\t\tpeeled = PEELED_TAGS;\n+\t\t/* perhaps other traits later as well */\n+\n+\t\t/* The \"+ 1\" is for the LF character. */\n+\t\tpos = eol + 1;\n+\t\tstrbuf_reset(&line);\n+\t}\n+\n \tdir = get_ref_dir(packed_refs->cache->root);\n \twhile (pos < eof) {\n \t\tstruct object_id oid;\n \t\tconst char *refname;\n-\t\tconst char *traits;\n \n \t\teol = memchr(pos, '\\n', eof - pos);\n \t\tif (!eol)\n@@ -267,15 +290,6 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \n \t\tstrbuf_add(&line, pos, eol + 1 - pos);\n \n-\t\tif (skip_prefix(line.buf, \"# pack-refs with:\", &traits)) {\n-\t\t\tif (strstr(traits, \" fully-peeled \"))\n-\t\t\t\tpeeled = PEELED_FULLY;\n-\t\t\telse if (strstr(traits, \" peeled \"))\n-\t\t\t\tpeeled = PEELED_TAGS;\n-\t\t\t/* perhaps other traits later as well */\n-\t\t\tgoto next_line;\n-\t\t}\n-\n \t\trefname = parse_ref_line(&line, &oid);\n \t\tif (refname) {\n \t\t\tint flag = REF_ISPACKED;\n@@ -307,7 +321,6 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \t\t\tdie_invalid_line(refs->path, line.buf, line.len);\n \t\t}\n \n-\tnext_line:\n \t\t/* The \"+ 1\" is for the LF character. */\n \t\tpos = eol + 1;\n \t\tstrbuf_reset(&line);\n-- \n2.14.1\n\n"},{"id":"328366","messageId":"0cc2a9af0eeeb2ffbf1942d19fbcceb0c0cf6d5c.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"[PATCH v2 07/21] read_packed_refs(): make parsing of the header line more robust","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:15Z","receivedAt":"2017-09-19T06:23:43Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"The old code parsed the traits in the `packed-refs` header by looking\nfor the string \" trait \" (i.e., the name of the trait with a space on\neither side) in the header line. This is fragile, because if any other\nimplementation of Git forgets to write the trailing space, the last\ntrait would silently be ignored (and the error might never be\nnoticed).\n\nSo instead, use `string_list_split_in_place()` to split the traits\ninto tokens then use `unsorted_string_list_has_string()` to look for\nthe tokens we are interested in. This means that we can read the\ntraits correctly even if the header line is missing a trailing\nspace (or indeed, if it is missing the space after the colon, or if it\nhas multiple spaces somewhere).\n\nHowever, older Git clients (and perhaps other Git implementations)\nstill require the surrounding spaces, so we still have to output the\nheader with a trailing space.\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 21 +++++++++++++++------\n 1 file changed, 15 insertions(+), 6 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 141f02b9c8..a45e3ff92f 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -257,25 +257,30 @@ static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n \n \t/* If the file has a header line, process it: */\n \tif (pos < eof && *pos == '#') {\n-\t\tconst char *traits;\n+\t\tchar *p;\n+\t\tstruct string_list traits = STRING_LIST_INIT_NODUP;\n \n \t\teol = memchr(pos, '\\n', eof - pos);\n \t\tif (!eol)\n \t\t\tdie_unterminated_line(refs->path, pos, eof - pos);\n \n-\t\tstrbuf_add(&line, pos, eol + 1 - pos);\n+\t\tstrbuf_add(&line, pos, eol - pos);\n \n-\t\tif (!skip_prefix(line.buf, \"# pack-refs with:\", &traits))\n+\t\tif (!skip_prefix(line.buf, \"# pack-refs with:\", (const char **)&p))\n \t\t\tdie_invalid_line(refs->path, pos, eof - pos);\n \n-\t\tif (strstr(traits, \" fully-peeled \"))\n+\t\tstring_list_split_in_place(&traits, p, ' ', -1);\n+\n+\t\tif (unsorted_string_list_has_string(&traits, \"fully-peeled\"))\n \t\t\tpeeled = PEELED_FULLY;\n-\t\telse if (strstr(traits, \" peeled \"))\n+\t\telse if (unsorted_string_list_has_string(&traits, \"peeled\"))\n \t\t\tpeeled = PEELED_TAGS;\n \t\t/* perhaps other traits later as well */\n \n \t\t/* The \"+ 1\" is for the LF character. */\n \t\tpos = eol + 1;\n+\n+\t\tstring_list_clear(&traits, 0);\n \t\tstrbuf_reset(&line);\n \t}\n \n@@ -610,7 +615,11 @@ int packed_refs_is_locked(struct ref_store *ref_store)\n \n /*\n * The packed-refs header line that we write out. Perhaps other\n- * traits will be added later. The trailing space is required.\n+ * traits will be added later.\n+ *\n+ * Note that earlier versions of Git used to parse these traits by\n+ * looking for \" trait \" in the line. For this reason, the space after\n+ * the colon and the trailing space are required.\n */\n static const char PACKED_REFS_HEADER[] =\n \t\"# pack-refs with: peeled fully-peeled \\n\";\n-- \n2.14.1\n\n"},{"id":"328367","messageId":"cbad77c8cf579651c4448b1c6a5a7a703723eb9b.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"[PATCH v2 01/21] ref_iterator: keep track of whether the iterator output is ordered","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:09Z","receivedAt":"2017-09-19T06:23:49Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"References are iterated over in order by refname, but reflogs are not.\nSome consumers of reference iteration care about the difference. Teach\neach `ref_iterator` to keep track of whether its output is ordered.\n\n`overlay_ref_iterator` is one of the picky consumers. Add a sanity\ncheck in `overlay_ref_iterator_begin()` to verify that its inputs are\nordered.\n\nSigned-off-by: Michael Haggerty \n---\n refs.c | 4 ++++\n refs/files-backend.c | 16 +++++++++-------\n refs/iterator.c | 15 ++++++++++-----\n refs/packed-backend.c | 2 +-\n refs/ref-cache.c | 2 +-\n refs/ref-cache.h | 3 ++-\n refs/refs-internal.h | 23 +++++++++++++++++++----\n 7 files changed, 46 insertions(+), 19 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex b0106b8162..101c107ee8 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1309,6 +1309,10 @@ struct ref_iterator *refs_ref_iterator_begin(\n \tif (trim)\n \t\titer = prefix_ref_iterator_begin(iter, \"\", trim);\n \n+\t/* Sanity check for subclasses: */\n+\tif (!iter->ordered)\n+\t\tBUG(\"reference iterator is not ordered\");\n+\n \treturn iter;\n }\n \ndiff --git a/refs/files-backend.c b/refs/files-backend.c\nindex 961424a4ea..35648c89fc 100644\n--- a/refs/files-backend.c\n+++ b/refs/files-backend.c\n@@ -762,7 +762,7 @@ static struct ref_iterator *files_ref_iterator_begin(\n \t\tconst char *prefix, unsigned int flags)\n {\n \tstruct files_ref_store *refs;\n-\tstruct ref_iterator *loose_iter, *packed_iter;\n+\tstruct ref_iterator *loose_iter, *packed_iter, *overlay_iter;\n \tstruct files_ref_iterator *iter;\n \tstruct ref_iterator *ref_iterator;\n \tunsigned int required_flags = REF_STORE_READ;\n@@ -772,10 +772,6 @@ static struct ref_iterator *files_ref_iterator_begin(\n \n \trefs = files_downcast(ref_store, required_flags, \"ref_iterator_begin\");\n \n-\titer = xcalloc(1, sizeof(*iter));\n-\tref_iterator = &iter->base;\n-\tbase_ref_iterator_init(ref_iterator, &files_ref_iterator_vtable);\n-\n \t/*\n \t * We must make sure that all loose refs are read before\n \t * accessing the packed-refs file; this avoids a race\n@@ -811,7 +807,13 @@ static struct ref_iterator *files_ref_iterator_begin(\n \t\t\trefs->packed_ref_store, prefix, 0,\n \t\t\tDO_FOR_EACH_INCLUDE_BROKEN);\n \n-\titer->iter0 = overlay_ref_iterator_begin(loose_iter, packed_iter);\n+\toverlay_iter = overlay_ref_iterator_begin(loose_iter, packed_iter);\n+\n+\titer = xcalloc(1, sizeof(*iter));\n+\tref_iterator = &iter->base;\n+\tbase_ref_iterator_init(ref_iterator, &files_ref_iterator_vtable,\n+\t\t\t overlay_iter->ordered);\n+\titer->iter0 = overlay_iter;\n \titer->flags = flags;\n \n \treturn ref_iterator;\n@@ -2084,7 +2086,7 @@ static struct ref_iterator *files_reflog_iterator_begin(struct ref_store *ref_st\n \tstruct ref_iterator *ref_iterator = &iter->base;\n \tstruct strbuf sb = STRBUF_INIT;\n \n-\tbase_ref_iterator_init(ref_iterator, &files_reflog_iterator_vtable);\n+\tbase_ref_iterator_init(ref_iterator, &files_reflog_iterator_vtable, 0);\n \tfiles_reflog_path(refs, &sb, NULL);\n \titer->dir_iterator = dir_iterator_begin(sb.buf);\n \titer->ref_store = ref_store;\ndiff --git a/refs/iterator.c b/refs/iterator.c\nindex 4cf449ef66..c475360f0a 100644\n--- a/refs/iterator.c\n+++ b/refs/iterator.c\n@@ -25,9 +25,11 @@ int ref_iterator_abort(struct ref_iterator *ref_iterator)\n }\n \n void base_ref_iterator_init(struct ref_iterator *iter,\n-\t\t\t struct ref_iterator_vtable *vtable)\n+\t\t\t struct ref_iterator_vtable *vtable,\n+\t\t\t int ordered)\n {\n \titer->vtable = vtable;\n+\titer->ordered = !!ordered;\n \titer->refname = NULL;\n \titer->oid = NULL;\n \titer->flags = 0;\n@@ -72,7 +74,7 @@ struct ref_iterator *empty_ref_iterator_begin(void)\n \tstruct empty_ref_iterator *iter = xcalloc(1, sizeof(*iter));\n \tstruct ref_iterator *ref_iterator = &iter->base;\n \n-\tbase_ref_iterator_init(ref_iterator, &empty_ref_iterator_vtable);\n+\tbase_ref_iterator_init(ref_iterator, &empty_ref_iterator_vtable, 1);\n \treturn ref_iterator;\n }\n \n@@ -205,6 +207,7 @@ static struct ref_iterator_vtable merge_ref_iterator_vtable = {\n };\n \n struct ref_iterator *merge_ref_iterator_begin(\n+\t\tint ordered,\n \t\tstruct ref_iterator *iter0, struct ref_iterator *iter1,\n \t\tref_iterator_select_fn *select, void *cb_data)\n {\n@@ -219,7 +222,7 @@ struct ref_iterator *merge_ref_iterator_begin(\n \t * references through only if they exist in both iterators.\n \t */\n \n-\tbase_ref_iterator_init(ref_iterator, &merge_ref_iterator_vtable);\n+\tbase_ref_iterator_init(ref_iterator, &merge_ref_iterator_vtable, ordered);\n \titer->iter0 = iter0;\n \titer->iter1 = iter1;\n \titer->select = select;\n@@ -268,9 +271,11 @@ struct ref_iterator *overlay_ref_iterator_begin(\n \t} else if (is_empty_ref_iterator(back)) {\n \t\tref_iterator_abort(back);\n \t\treturn front;\n+\t} else if (!front->ordered || !back->ordered) {\n+\t\tBUG(\"overlay_ref_iterator requires ordered inputs\");\n \t}\n \n-\treturn merge_ref_iterator_begin(front, back,\n+\treturn merge_ref_iterator_begin(1, front, back,\n \t\t\t\t\toverlay_iterator_select, NULL);\n }\n \n@@ -361,7 +366,7 @@ struct ref_iterator *prefix_ref_iterator_begin(struct ref_iterator *iter0,\n \titer = xcalloc(1, sizeof(*iter));\n \tref_iterator = &iter->base;\n \n-\tbase_ref_iterator_init(ref_iterator, &prefix_ref_iterator_vtable);\n+\tbase_ref_iterator_init(ref_iterator, &prefix_ref_iterator_vtable, iter0->ordered);\n \n \titer->iter0 = iter0;\n \titer->prefix = xstrdup(prefix);\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 0279aeceea..e411501871 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -437,7 +437,7 @@ static struct ref_iterator *packed_ref_iterator_begin(\n \n \titer = xcalloc(1, sizeof(*iter));\n \tref_iterator = &iter->base;\n-\tbase_ref_iterator_init(ref_iterator, &packed_ref_iterator_vtable);\n+\tbase_ref_iterator_init(ref_iterator, &packed_ref_iterator_vtable, 1);\n \n \t/*\n \t * Note that get_packed_ref_cache() internally checks whether\ndiff --git a/refs/ref-cache.c b/refs/ref-cache.c\nindex 76bb723c86..54dfb5218c 100644\n--- a/refs/ref-cache.c\n+++ b/refs/ref-cache.c\n@@ -574,7 +574,7 @@ struct ref_iterator *cache_ref_iterator_begin(struct ref_cache *cache,\n \n \titer = xcalloc(1, sizeof(*iter));\n \tref_iterator = &iter->base;\n-\tbase_ref_iterator_init(ref_iterator, &cache_ref_iterator_vtable);\n+\tbase_ref_iterator_init(ref_iterator, &cache_ref_iterator_vtable, 1);\n \tALLOC_GROW(iter->levels, 10, iter->levels_alloc);\n \n \titer->levels_nr = 1;\ndiff --git a/refs/ref-cache.h b/refs/ref-cache.h\nindex 794f000fd3..a082bfb06c 100644\n--- a/refs/ref-cache.h\n+++ b/refs/ref-cache.h\n@@ -245,7 +245,8 @@ struct ref_entry *find_ref_entry(struct ref_dir *dir, const char *refname);\n * Start iterating over references in `cache`. If `prefix` is\n * specified, only include references whose names start with that\n * prefix. If `prime_dir` is true, then fill any incomplete\n- * directories before beginning the iteration.\n+ * directories before beginning the iteration. The output is ordered\n+ * by refname.\n */\n struct ref_iterator *cache_ref_iterator_begin(struct ref_cache *cache,\n \t\t\t\t\t const char *prefix,\ndiff --git a/refs/refs-internal.h b/refs/refs-internal.h\nindex d7d344de73..d7f233beba 100644\n--- a/refs/refs-internal.h\n+++ b/refs/refs-internal.h\n@@ -329,6 +329,13 @@ int refs_rename_ref_available(struct ref_store *refs,\n */\n struct ref_iterator {\n \tstruct ref_iterator_vtable *vtable;\n+\n+\t/*\n+\t * Does this `ref_iterator` iterate over references in order\n+\t * by refname?\n+\t */\n+\tunsigned int ordered : 1;\n+\n \tconst char *refname;\n \tconst struct object_id *oid;\n \tunsigned int flags;\n@@ -374,7 +381,7 @@ int is_empty_ref_iterator(struct ref_iterator *ref_iterator);\n * which the refname begins with prefix. If trim is non-zero, then\n * trim that many characters off the beginning of each refname. flags\n * can be DO_FOR_EACH_INCLUDE_BROKEN to include broken references in\n- * the iteration.\n+ * the iteration. The output is ordered by refname.\n */\n struct ref_iterator *refs_ref_iterator_begin(\n \t\tstruct ref_store *refs,\n@@ -400,9 +407,11 @@ typedef enum iterator_selection ref_iterator_select_fn(\n * Iterate over the entries from iter0 and iter1, with the values\n * interleaved as directed by the select function. The iterator takes\n * ownership of iter0 and iter1 and frees them when the iteration is\n- * over.\n+ * over. A derived class should set `ordered` to 1 or 0 based on\n+ * whether it generates its output in order by reference name.\n */\n struct ref_iterator *merge_ref_iterator_begin(\n+\t\tint ordered,\n \t\tstruct ref_iterator *iter0, struct ref_iterator *iter1,\n \t\tref_iterator_select_fn *select, void *cb_data);\n \n@@ -431,6 +440,8 @@ struct ref_iterator *overlay_ref_iterator_begin(\n * As an convenience to callers, if prefix is the empty string and\n * trim is zero, this function returns iter0 directly, without\n * wrapping it.\n+ *\n+ * The resulting ref_iterator is ordered if iter0 is.\n */\n struct ref_iterator *prefix_ref_iterator_begin(struct ref_iterator *iter0,\n \t\t\t\t\t const char *prefix,\n@@ -441,11 +452,14 @@ struct ref_iterator *prefix_ref_iterator_begin(struct ref_iterator *iter0,\n /*\n * Base class constructor for ref_iterators. Initialize the\n * ref_iterator part of iter, setting its vtable pointer as specified.\n+ * `ordered` should be set to 1 if the iterator will iterate over\n+ * references in order by refname; otherwise it should be set to 0.\n * This is meant to be called only by the initializers of derived\n * classes.\n */\n void base_ref_iterator_init(struct ref_iterator *iter,\n-\t\t\t struct ref_iterator_vtable *vtable);\n+\t\t\t struct ref_iterator_vtable *vtable,\n+\t\t\t int ordered);\n \n /*\n * Base class destructor for ref_iterators. Destroy the ref_iterator\n@@ -564,7 +578,8 @@ typedef int rename_ref_fn(struct ref_store *ref_store,\n * Iterate over the references in `ref_store` whose names start with\n * `prefix`. `prefix` is matched as a literal string, without regard\n * for path separators. If prefix is NULL or the empty string, iterate\n- * over all references in `ref_store`.\n+ * over all references in `ref_store`. The output is ordered by\n+ * refname.\n */\n typedef struct ref_iterator *ref_iterator_begin_fn(\n \t\tstruct ref_store *ref_store,\n-- \n2.14.1\n\n"},{"id":"328368","messageId":"3f231e673b9aa67347dd71c3d1c0eb813fe3a761.1505799700.git.mhagger@alum.mit.edu","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"[PATCH v2 03/21] packed_ref_cache: add a backlink to the associated `packed_ref_store`","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T06:22:11Z","receivedAt":"2017-09-19T06:23:51Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"It will prove convenient in upcoming patches.\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 23 ++++++++++++++++-------\n 1 file changed, 16 insertions(+), 7 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex e411501871..a3d9210cb0 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -7,7 +7,15 @@\n #include \"../iterator.h\"\n #include \"../lockfile.h\"\n \n+struct packed_ref_store;\n+\n struct packed_ref_cache {\n+\t/*\n+\t * A back-pointer to the packed_ref_store with which this\n+\t * cache is associated:\n+\t */\n+\tstruct packed_ref_store *refs;\n+\n \tstruct ref_cache *cache;\n \n \t/*\n@@ -154,7 +162,7 @@ static const char *parse_ref_line(struct strbuf *line, struct object_id *oid)\n }\n \n /*\n- * Read from `packed_refs_file` into a newly-allocated\n+ * Read from the `packed-refs` file into a newly-allocated\n * `packed_ref_cache` and return it. The return value will already\n * have its reference count incremented.\n *\n@@ -182,7 +190,7 @@ static const char *parse_ref_line(struct strbuf *line, struct object_id *oid)\n * compatibility with older clients, but we do not require it\n * (i.e., \"peeled\" is a no-op if \"fully-peeled\" is set).\n */\n-static struct packed_ref_cache *read_packed_refs(const char *packed_refs_file)\n+static struct packed_ref_cache *read_packed_refs(struct packed_ref_store *refs)\n {\n \tFILE *f;\n \tstruct packed_ref_cache *packed_refs = xcalloc(1, sizeof(*packed_refs));\n@@ -191,11 +199,12 @@ static struct packed_ref_cache *read_packed_refs(const char *packed_refs_file)\n \tenum { PEELED_NONE, PEELED_TAGS, PEELED_FULLY } peeled = PEELED_NONE;\n \tstruct ref_dir *dir;\n \n+\tpacked_refs->refs = refs;\n \tacquire_packed_ref_cache(packed_refs);\n \tpacked_refs->cache = create_ref_cache(NULL, NULL);\n \tpacked_refs->cache->root->flag &= ~REF_INCOMPLETE;\n \n-\tf = fopen(packed_refs_file, \"r\");\n+\tf = fopen(refs->path, \"r\");\n \tif (!f) {\n \t\tif (errno == ENOENT) {\n \t\t\t/*\n@@ -205,7 +214,7 @@ static struct packed_ref_cache *read_packed_refs(const char *packed_refs_file)\n \t\t\t */\n \t\t\treturn packed_refs;\n \t\t} else {\n-\t\t\tdie_errno(\"couldn't read %s\", packed_refs_file);\n+\t\t\tdie_errno(\"couldn't read %s\", refs->path);\n \t\t}\n \t}\n \n@@ -218,7 +227,7 @@ static struct packed_ref_cache *read_packed_refs(const char *packed_refs_file)\n \t\tconst char *traits;\n \n \t\tif (!line.len || line.buf[line.len - 1] != '\\n')\n-\t\t\tdie(\"unterminated line in %s: %s\", packed_refs_file, line.buf);\n+\t\t\tdie(\"unterminated line in %s: %s\", refs->path, line.buf);\n \n \t\tif (skip_prefix(line.buf, \"# pack-refs with:\", &traits)) {\n \t\t\tif (strstr(traits, \" fully-peeled \"))\n@@ -258,7 +267,7 @@ static struct packed_ref_cache *read_packed_refs(const char *packed_refs_file)\n \t\t\tlast->flag |= REF_KNOWS_PEELED;\n \t\t} else {\n \t\t\tstrbuf_setlen(&line, line.len - 1);\n-\t\t\tdie(\"unexpected line in %s: %s\", packed_refs_file, line.buf);\n+\t\t\tdie(\"unexpected line in %s: %s\", refs->path, line.buf);\n \t\t}\n \t}\n \n@@ -293,7 +302,7 @@ static struct packed_ref_cache *get_packed_ref_cache(struct packed_ref_store *re\n \t\tvalidate_packed_ref_cache(refs);\n \n \tif (!refs->cache)\n-\t\trefs->cache = read_packed_refs(refs->path);\n+\t\trefs->cache = read_packed_refs(refs);\n \n \treturn refs->cache;\n }\n-- \n2.14.1\n\n"},{"id":"328381","messageId":"354c8088-ae24-479d-3b4e-fe8e189223b2@alum.mit.edu","threadId":"46784","inReplyTo":"b32234e07a1bd1e60442a13d97d7c4e51edf3336.1505799700.git.mhagger@alum.mit.edu","subject":"Re: [PATCH v2 13/21] packed_ref_cache: keep the `packed-refs` file mmapped if possible","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-19T12:44:24Z","receivedAt":"2017-09-19T12:44:34Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 09/19/2017 08:22 AM, Michael Haggerty wrote:\n> Keep a copy of the `packed-refs` file contents in memory for as long\n> as a `packed_ref_cache` object is in use:\n> \n> * If the system allows it, keep the `packed-refs` file mmapped.\n> \n> * If not (either because the system doesn't support `mmap()` at all,\n> or because a file that is currently mmapped cannot be replaced via\n> `rename()`), then make a copy of the file's contents in\n> heap-allocated space, and keep that around instead.\n> \n> We base the choice of behavior on a new build-time switch,\n> `MMAP_PREVENTS_DELETE`. By default, this switch is set for Windows\n> variants.\n> \n> This whole change is still pointless, because we only read the\n> `packed-refs` file contents immediately after instantiating the\n> `packed_ref_cache`. But that will soon change.\n> \n> Signed-off-by: Michael Haggerty \n> ---\n> Makefile | 10 +++\n> config.mak.uname | 3 +\n> refs/packed-backend.c | 184 ++++++++++++++++++++++++++++++++++++++------------\n> 3 files changed, 155 insertions(+), 42 deletions(-)\n> \n> diff --git a/Makefile b/Makefile\n> index f2bb7f2f63..7a49f99c4f 100644\n> [...]\n> diff --git a/refs/packed-backend.c b/refs/packed-backend.c\n> index 0fe41a7203..4981516f1e 100644\n> --- a/refs/packed-backend.c\n> +++ b/refs/packed-backend.c\n> [...]\n> @@ -304,6 +371,61 @@ struct ref_iterator *mmapped_ref_iterator_begin(\n> \treturn ref_iterator;\n> }\n> \n> +/*\n> + * Depending on `mmap_strategy`, either mmap or read the contents of\n> + * the `packed-refs` file into the `packed_refs` instance. Return 1 if\n> + * the file existed and was read, or 0 if the file was absent. Die on\n> + * errors.\n> + */\n> +static int load_contents(struct packed_ref_cache *packed_refs)\n> +{\n> +\tint fd;\n> +\tstruct stat st;\n> +\tsize_t size, bytes_read;\n\nCoverity helpfully pointed out that `bytes_read` has to be signed:\n`ssize_t`. I'll fix that in the next round after waiting for other comments.\n\n> [...]\n\nMichael\n"},{"id":"328418","messageId":"alpine.DEB.2.21.1.1709192047450.219280@virtualbox","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"Re: [PATCH v2 00/21] Read `packed-refs` using mmap()","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2017-09-19T19:53:45Z","receivedAt":"2017-09-19T19:54:11Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Michael,\n\nOn Tue, 19 Sep 2017, Michael Haggerty wrote:\n\n> This is v2 of a patch series that changes the reading and caching of the\n> `packed-refs` file to use `mmap()`. Thanks to Junio, Stefan, and\n> Johannes for their comments about v1 [1].\n\nThank you for the new iteration.\n\n> The main change since v1 is to accommodate Windows, which doesn't let\n> you replace a file using `rename()` if the file is currently mmapped.\n> This is unfortunate, because it means that Windows will never get the\n> O(N) → O(lg N) improvement for reading single references that more\n> capable systems can now enjoy.\n\nTriggered by your enquiry, I looked into passing the FILE_SHARE_DELETE\nflag which I hoped would let us delete the file even if it still is open\n(and mapped). In my tests, this did not work. If anybody wants to have a\nlook at what I did (and whether they can make it work):\nhttps://github.com/dscho/git/tree/replace-wopen\n\n> The background was discussed on the mailing list [2]. The bottom line\n> is that on Windows, keeping the `packed-refs` lock mmapped would be\n> tantamount to holding reader lock on that file, preventing anybody\n> (even unrelated processes) from changing the `packed-refs` file while\n> it is mmapped. This is even worse than the situation for packfiles\n> (which is solved using `close_all_packs()`), because a packfile, once\n> created, never needs to be replaced—every packfile has a filename that\n> is determined from its contents. The worst that can happen if a\n> packfile is locked is that another process cannot remove it, but that\n> is not critical for correctness. The `packed-refs` file, on the other\n> hand, always has the same filename and needs to be overwritten for\n> correctness.\n> \n> So the approach taken here is that a new compile-time option,\n> `MMAP_PREVENTS_DELETE`, is introduced. When this option is set, then\n> the `packed-refs` file is read quickly into memory then closed.\n\nAnother approach would be to imitate close_all_packs() and rely on the\nWindows-specific code that retries renames in a staggered fashion, waiting\na little longer and longer before retrying, and finally telling the user\nthat some file cannot be overwritten:\nhttps://github.com/git-for-windows/git/blob/v2.14.1.windows.1/compat/mingw.c#L2439-L2441\n\nThis is not a new problem, by the way. If a file is in use while you try\nto run `git checkout` with a different version of that file, we have the\nexact same problem on Windows. And we deal with it using that\nretry_ask_yes_no() function.\n\nFor this to work, the current process really would need to be able to\nrelease all snapshots in one go (for simplicity, I would not even check\nthe filename but simply blow them all away when we want to overwrite\npacked-refs).\n\nI guess I should set aside some time to implement that on top of your\nseries (I *really* want our in-house users to benefit from that O(lg n)\nimprovement). In the meantime, I think this can go forward with the\ncurrent design.\n\nCiao,\nDscho"},{"id":"328478","messageId":"20170920182732.wy6bojeaonpxb3mc@sigill.intra.peff.net","threadId":"46784","inReplyTo":"597241da13f62d51fefd3396bfbab22a8f633a56.1505799700.git.mhagger@alum.mit.edu","subject":"Re: [PATCH v2 08/21] read_packed_refs(): read references with minimal copying","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-09-20T18:27:33Z","receivedAt":"2017-09-20T18:27:45Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Sep 19, 2017 at 08:22:16AM +0200, Michael Haggerty wrote:\n\n> Instead of copying data from the `packed-refs` file one line at time\n> and then processing it, process the data in place as much as possible.\n> \n> Also, instead of processing one line per iteration of the main loop,\n> process a reference line plus its corresponding peeled line (if\n> present) together.\n> \n> Note that this change slightly tightens up the parsing of the\n> `parse-ref` file. Previously, the parser would have accepted multiple\n\ns/parse-ref/packed-refs/, I assume\n\nThe patch itself looks good, though I did notice an interesting tangent.\n\n> +\t\tif (eof - pos < GIT_SHA1_HEXSZ + 2 ||\n> +\t\t parse_oid_hex(p, &oid, &p) ||\n> +\t\t !isspace(*p++))\n> +\t\t\tdie_invalid_line(refs->path, pos, eof - pos);\n\nI wondered why you didn't just check the output of parse_oid_hex(), and\nincluded the length check (since in the long run we'd like to get rid of\nuses of the static GIT_SHA1_HEXSZ macro). I imagine the answer is that\nthis is an mmap'd buffer, and we can't guarantee that parse_oid_hex()\nwouldn't walk off the end of it.\n\nThat's fine for now, but I suspect it may become a problem when we move\nto having a second hash function with a different length. You can't just\nsay \"it must have as many bytes as the longest hash\", because of course\nwe could have the shorter hash at the end of the buffer. But we also\ncan't say \"it must have as many bytes as the shortest hash\", because if\nthe content implies it's a longer hash, we'd read off the end of the\nbuffer.\n\nI think in the long run we will need a parse_oid_hex() function that\ntakes a ptr/len (or start/end) pair.\n\nSorry, that got a bit off-topic. I don't think there's anything to be\ndone now in your series. It just raises an interesting question for\npeople working on the hash conversion stuff. +cc brian as an FYI.\n\n-Peff\n"},{"id":"328479","messageId":"20170920182921.6c7zndcghivzevg3@sigill.intra.peff.net","threadId":"46784","inReplyTo":"d34d2cbde67e9ef0b0b11910de19c7f722c2314c.1505799700.git.mhagger@alum.mit.edu","subject":"Re: [PATCH v2 11/21] mmapped_ref_iterator_advance(): no peeled value for broken refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-09-20T18:29:21Z","receivedAt":"2017-09-20T18:29:34Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Sep 19, 2017 at 08:22:19AM +0200, Michael Haggerty wrote:\n\n> If a reference is broken, suppress its peeled value.\n\nMakes sense. Without this we might return an answer for \"git show\ntag^{commit}\" even if the repo is broken and the object pointed to by\n\"tag\" is missing.\n\n-Peff\n"},{"id":"328480","messageId":"20170920184058.w3tipgsz54ig7dm5@sigill.intra.peff.net","threadId":"46784","inReplyTo":"b32234e07a1bd1e60442a13d97d7c4e51edf3336.1505799700.git.mhagger@alum.mit.edu","subject":"Re: [PATCH v2 13/21] packed_ref_cache: keep the `packed-refs` file mmapped if possible","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-09-20T18:40:58Z","receivedAt":"2017-09-20T18:41:05Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Sep 19, 2017 at 08:22:21AM +0200, Michael Haggerty wrote:\n\n> Keep a copy of the `packed-refs` file contents in memory for as long\n> as a `packed_ref_cache` object is in use:\n> \n> * If the system allows it, keep the `packed-refs` file mmapped.\n> \n> * If not (either because the system doesn't support `mmap()` at all,\n> or because a file that is currently mmapped cannot be replaced via\n> `rename()`), then make a copy of the file's contents in\n> heap-allocated space, and keep that around instead.\n> \n> We base the choice of behavior on a new build-time switch,\n> `MMAP_PREVENTS_DELETE`. By default, this switch is set for Windows\n> variants.\n> \n> This whole change is still pointless, because we only read the\n> `packed-refs` file contents immediately after instantiating the\n> `packed_ref_cache`. But that will soon change.\n\nThe overall strategy for this compile-time knob makes sense, but one\nthing confused me:\n\n> +ifdef MMAP_PREVENTS_DELETE\n> +\tBASIC_CFLAGS += -DMMAP_PREVENTS_DELETE\n> +else\n> +\tifdef USE_WIN32_MMAP\n> +\t\tBASIC_CFLAGS += -DMMAP_PREVENTS_DELETE\n> +\tendif\n> +endif\n\nSo setting the knob does what you'd expect. But if you don't set it,\nthen we still auto-tweak it based on the USE_WIN32_MMAP knob. Do we need\nthat? It seems like we set our new knob in config.mak.uname any time\nwe'd set USE_WIN32_MMAP. So this only has an effect in two cases:\n\n 1. You aren't on Windows, but you set USE_WIN32_MMAP yourself.\n\n 2. You are on Windows, but you manually unset MMAP_PREVENTS_DELETE.\n\nI expect both cases are rare (and would probably involve somebody\nactively debugging these knobs). Probably it's a minor convenience in\ncase 1, but in case 2 it would be actively confusing, I'd think.\n\n> +enum mmap_strategy {\n> +\t/*\n> +\t * Don't use mmap() at all for reading `packed-refs`.\n> +\t */\n> +\tMMAP_NONE,\n> +\n> +\t/*\n> +\t * Can use mmap() for reading `packed-refs`, but the file must\n> +\t * not remain mmapped. This is the usual option on Windows,\n> +\t * where you cannot rename a new version of a file onto a file\n> +\t * that is currently mmapped.\n> +\t */\n> +\tMMAP_TEMPORARY,\n\nI suspect you originally distinguished these cases so that NO_MMAP does\nnot read into a fake-mmap buffer, followed by us copying it into another\nbuffer. But AFAICT we handle the \"NONE\" and \"TEMPORARY\" cases exactly\nthe same (by just doing a read_in_full() into our own buffer). Do we\nactually need separate strategies?\n\n-Peff\n"},{"id":"328483","messageId":"20170920185047.6fzuspaseofb7r5x@sigill.intra.peff.net","threadId":"46784","inReplyTo":"5bb362d9cb74c7386cd072e3ecd49b22cea1d8d2.1505799700.git.mhagger@alum.mit.edu","subject":"Re: [PATCH v2 14/21] read_packed_refs(): ensure that references are ordered when read","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-09-20T18:50:47Z","receivedAt":"2017-09-20T18:50:54Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Sep 19, 2017 at 08:22:22AM +0200, Michael Haggerty wrote:\n\n> If `packed-refs` was already sorted, then (if the system allows it) we\n> can use the mmapped file contents directly. But if the system doesn't\n> allow a file that is currently mmapped to be replaced using\n> `rename()`, then it would be bad for us to keep the file mmapped for\n> any longer than necessary. So, on such systems, always make a copy of\n> the file contents, either as part of the sorting process, or\n> afterwards.\n\nSo this sort-of answers my question from the previous commit (why we\ncare about the distinction between NONE and TEMPORARY), since we now\nstart treating them differently.\n\nBut I'm a bit confused why there's any advantage in the TEMPORARY case\nto doing the mmap-and-copy versus just treating it like NONE and reading\nit directly.\n\nHmm, I guess it comes down to the double-allocation thing again? Let me\nsee if I have this right:\n\n 1. For NO_MMAP, we'd read the buffer once. If it's sorted, good. If\n not, then we temporarily hold it in memory twice while we copy it\n into the new sorted buffer.\n\n 2. For TEMPORARY, we mmap once. If it's sorted, then we make a single\n copy. If it's not sorted, then we do the copy+sort as a single\n step.\n\n 3. For MMAP_OK, if it's sorted, we're done. Otherwise, we do the\n single copy.\n\nSo this is really there to help the TEMPORARY case reading an old\nunsorted file avoid needing to use double-the-ram during the copy?\n\nThat seems like a good reason (and it does not seem to add too much\ncomplexity).\n\n-Peff\n"},{"id":"328484","messageId":"20170920185119.upnyomtlxobxwvlw@sigill.intra.peff.net","threadId":"46784","inReplyTo":"20170920184058.w3tipgsz54ig7dm5@sigill.intra.peff.net","subject":"Re: [PATCH v2 13/21] packed_ref_cache: keep the `packed-refs` file mmapped if possible","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-09-20T18:51:20Z","receivedAt":"2017-09-20T18:51:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Sep 20, 2017 at 02:40:58PM -0400, Jeff King wrote:\n\n> > +enum mmap_strategy {\n> > +\t/*\n> > +\t * Don't use mmap() at all for reading `packed-refs`.\n> > +\t */\n> > +\tMMAP_NONE,\n> > +\n> > +\t/*\n> > +\t * Can use mmap() for reading `packed-refs`, but the file must\n> > +\t * not remain mmapped. This is the usual option on Windows,\n> > +\t * where you cannot rename a new version of a file onto a file\n> > +\t * that is currently mmapped.\n> > +\t */\n> > +\tMMAP_TEMPORARY,\n> \n> I suspect you originally distinguished these cases so that NO_MMAP does\n> not read into a fake-mmap buffer, followed by us copying it into another\n> buffer. But AFAICT we handle the \"NONE\" and \"TEMPORARY\" cases exactly\n> the same (by just doing a read_in_full() into our own buffer). Do we\n> actually need separate strategies?\n\nIn case you are reading these sequentially, I think I talked myself into\nthe utility of this during the next patch. ;)\n\n-Peff\n"},{"id":"328485","messageId":"20170920185724.ix7isdxfrsecxkjj@sigill.intra.peff.net","threadId":"46784","inReplyTo":"cover.1505799700.git.mhagger@alum.mit.edu","subject":"Re: [PATCH v2 00/21] Read `packed-refs` using mmap()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-09-20T18:57:25Z","receivedAt":"2017-09-20T18:57:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Sep 19, 2017 at 08:22:08AM +0200, Michael Haggerty wrote:\n\n> This branch is also available from my fork on GitHub as branch\n> `mmap-packed-refs`.\n> \n> My main uncertainties are:\n> \n> 1. Does this code actually work on Windows?\n> \n> 2. Did I implement the new compile-time option correctly? (I just\n> cargo-culted some existing options.) Is there some existing option\n> that I could piggy-back off of instead of adding a new one?\n> \n> 3. Is a compile-time option sufficient, or would the `mmap()` option\n> need to be configurable at runtime, or even tested at repository\n> create time as is done for some other filesystem properties in\n> `create_default_files()`?\n\nI can't really answer (1) due to lack of knowledge. For (2), I think\nit's mostly good, though I raised a small nit. For (3), I think this is\nreally an OS restriction and not a filesystem one, so probably\nbuild-time is OK (though of course Windows people may be able to correct\nme).\n\nI left a few comments, but overall it looks quite good to me.\n\n-Peff\n"},{"id":"328498","messageId":"CAGZ79kbwCAidGR3cgukdjckZVYwj+qbOikqN-e934uP1yk9Cuw@mail.gmail.com","threadId":"46784","inReplyTo":"2bb2e8ccb57eef8acbea5004167751a007a1bd2f.1505799700.git.mhagger@alum.mit.edu","subject":"Re: [PATCH v2 02/21] prefix_ref_iterator: break when we leave the prefix","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-09-20T20:25:43Z","receivedAt":"2017-09-20T20:25:51Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Mon, Sep 18, 2017 at 11:22 PM, Michael Haggerty wrote:\n> From: Jeff King \n>\n> If the underlying iterator is ordered, then `prefix_ref_iterator` can\n> stop as soon as it sees a refname that comes after the prefix. This\n> will rarely make a big difference now, because `ref_cache_iterator`\n> only iterates over the directory containing the prefix (and usually\n> the prefix will span a whole directory anyway). But if *hint, hint* a\n> future reference backend doesn't itself know where to stop the\n> iteration, then this optimization will be a big win.\n>\n> Note that there is no guarantee that the underlying iterator doesn't\n> include output preceding the prefix, so we have to skip over any\n> unwanted references before we get to the ones that we want.\n>\n> Signed-off-by: Jeff King \n> Signed-off-by: Michael Haggerty \n> ---\n> refs/iterator.c | 32 +++++++++++++++++++++++++++++++-\n> 1 file changed, 31 insertions(+), 1 deletion(-)\n>\n> diff --git a/refs/iterator.c b/refs/iterator.c\n> index c475360f0a..bd35da4e62 100644\n> --- a/refs/iterator.c\n> +++ b/refs/iterator.c\n> @@ -287,6 +287,20 @@ struct prefix_ref_iterator {\n> int trim;\n> };\n>\n> +/* Return -1, 0, 1 if refname is before, inside, or after the prefix. */\n> +static int compare_prefix(const char *refname, const char *prefix)\n> +{\n> + while (*prefix) {\n> + if (*refname != *prefix)\n> + return ((unsigned char)*refname < (unsigned char)*prefix) ? -1 : +1;\n\nThis looks interesting.\n\nWe get a signed char* , cast it to unsigned char* and then\ncompare byte by byte.\n\nThe cast lead me to think that this should work for non-ASCII\n(e.g. ANSI?), but given that there are multi-byte characters (e.g.\nUTF-8) depending on your encoding used, we may not assume\nthat in the given encoding the characters order by their byte order?\n\nBut this compare function is not to order by the natural encoding order,\nbut it's used to detect the '0' at the end of prefix, which orders\nbefore *any* unsigned char.\n\nWe cannot enhance starts_with for this case as we'd have to invert\nthe return value to differentiate between the prefix ordering before\nor after the given string.\n\nEssentially compare_prefix wants to provide the same return\nvalue as `strncmp(refname, prefix, min(strlen(refname), strlen(prefix)));`\nexcept that it is optimized as we do not have to walk over a string\nmultiple times (to determine length and then pass it to compare).\n\nFeel free to ignore the rambling, I just had to sort my thoughts.\nThe patch looks good.\n\nThanks,\nStefan\n\n> +\n> + refname++;\n> + prefix++;\n> + }\n> +\n> + return 0;\n> +}\n> +\n> static int prefix_ref_iterator_advance(struct ref_iterator *ref_iterator)\n> {\n> struct prefix_ref_iterator *iter =\n> @@ -294,9 +308,25 @@ static int prefix_ref_iterator_advance(struct ref_iterator *ref_iterator)\n> int ok;\n>\n> while ((ok = ref_iterator_advance(iter->iter0)) == ITER_OK) {\n> - if (!starts_with(iter->iter0->refname, iter->prefix))\n> + int cmp = compare_prefix(iter->iter0->refname, iter->prefix);\n> +\n> + if (cmp < 0)\n> continue;\n>\n> + if (cmp > 0) {\n> + /*\n> + * If the source iterator is ordered, then we\n> + * can stop the iteration as soon as we see a\n> + * refname that comes after the prefix:\n> + */\n> + if (iter->iter0->ordered) {\n> + ok = ref_iterator_abort(iter->iter0);\n> + break;\n> + } else {\n> + continue;\n> + }\n> + }\n> +\n> if (iter->trim) {\n> /*\n> * It is nonsense to trim off characters that\n> --\n> 2.14.1\n>\n"},{"id":"328541","messageId":"20170921045932.b5y33fm7gao27ium@sigill.intra.peff.net","threadId":"46784","inReplyTo":"CAGZ79kbwCAidGR3cgukdjckZVYwj+qbOikqN-e934uP1yk9Cuw@mail.gmail.com","subject":"Re: [PATCH v2 02/21] prefix_ref_iterator: break when we leave the prefix","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-09-21T04:59:32Z","receivedAt":"2017-09-21T04:59:39Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Sep 20, 2017 at 01:25:43PM -0700, Stefan Beller wrote:\n\n> > +/* Return -1, 0, 1 if refname is before, inside, or after the prefix. */\n> > +static int compare_prefix(const char *refname, const char *prefix)\n> > +{\n> > + while (*prefix) {\n> > + if (*refname != *prefix)\n> > + return ((unsigned char)*refname < (unsigned char)*prefix) ? -1 : +1;\n> \n> This looks interesting.\n> \n> We get a signed char* , cast it to unsigned char* and then\n> compare byte by byte.\n> \n> The cast lead me to think that this should work for non-ASCII\n> (e.g. ANSI?), but given that there are multi-byte characters (e.g.\n> UTF-8) depending on your encoding used, we may not assume\n> that in the given encoding the characters order by their byte order?\n\nWe don't really care about encodings here. We're doing a byte-wise\ncomparison. Which may include high-bit bytes for some encodings.\n\nThe important thing is that it match the byte-wise comparison that we\nuse elsewhere (e.g., in memcmp or strcmp), since our sort order must be\nthe same. And those functions are defined to do the funny \"subtract as\nunsigned\" rule.\n\n> But this compare function is not to order by the natural encoding order,\n> but it's used to detect the '0' at the end of prefix, which orders\n> before *any* unsigned char.\n\nIt's not just detecting the \"0\". We care about the ordering overall (so\nthat \"refs/foo\" comes after \"refs/bar\", and we know that \"refs/bar/baz\"\ncannot come after \"refs/foo\", and we can stop iterating).\n\n> We cannot enhance starts_with for this case as we'd have to invert\n> the return value to differentiate between the prefix ordering before\n> or after the given string.\n\nExactly. starts_with() is about a boolean match. But this is inherently\nabout matching the ordering of other \"cmp\" functions, but for a partial\nmatch. It's possible that's something we could use in a more general\ncase, but I don't know of one offhand.\n\n> Essentially compare_prefix wants to provide the same return\n> value as `strncmp(refname, prefix, min(strlen(refname), strlen(prefix)));`\n> except that it is optimized as we do not have to walk over a string\n> multiple times (to determine length and then pass it to compare).\n\nHmm, yeah, I think that would be an equivalent. I didn't think of that,\nbut as you say it would be less efficient.\n\n> Feel free to ignore the rambling, I just had to sort my thoughts.\n> The patch looks good.\n\nRambling is sometimes good if it points out holes in the original\nreasoning.\n\nThe patch is credited to me, but I actually screwed up the ordering by\nfailing to do the unsigned cast. Michael fixed that part before posting\nit. :)\n\n-Peff\n"},{"id":"328553","messageId":"b7936c07-a2a2-f17c-b557-2b4916cac3bc@alum.mit.edu","threadId":"46784","inReplyTo":"20170920182732.wy6bojeaonpxb3mc@sigill.intra.peff.net","subject":"Re: [PATCH v2 08/21] read_packed_refs(): read references with minimal copying","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-21T07:34:04Z","receivedAt":"2017-09-21T07:34:15Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 09/20/2017 08:27 PM, Jeff King wrote:\n> On Tue, Sep 19, 2017 at 08:22:16AM +0200, Michael Haggerty wrote:\n> \n>> Instead of copying data from the `packed-refs` file one line at time\n>> and then processing it, process the data in place as much as possible.\n>>\n>> Also, instead of processing one line per iteration of the main loop,\n>> process a reference line plus its corresponding peeled line (if\n>> present) together.\n>>\n>> Note that this change slightly tightens up the parsing of the\n>> `parse-ref` file. Previously, the parser would have accepted multiple\n> \n> s/parse-ref/packed-refs/, I assume\n\nThanks; will fix.\n\n> The patch itself looks good, though I did notice an interesting tangent.\n> \n>> +\t\tif (eof - pos < GIT_SHA1_HEXSZ + 2 ||\n>> +\t\t parse_oid_hex(p, &oid, &p) ||\n>> +\t\t !isspace(*p++))\n>> +\t\t\tdie_invalid_line(refs->path, pos, eof - pos);\n> \n> I wondered why you didn't just check the output of parse_oid_hex(), and\n> included the length check (since in the long run we'd like to get rid of\n> uses of the static GIT_SHA1_HEXSZ macro). I imagine the answer is that\n> this is an mmap'd buffer, and we can't guarantee that parse_oid_hex()\n> wouldn't walk off the end of it.\n\nYes.\n\n> That's fine for now, but I suspect it may become a problem when we move\n> to having a second hash function with a different length. You can't just\n> say \"it must have as many bytes as the longest hash\", because of course\n> we could have the shorter hash at the end of the buffer. But we also\n> can't say \"it must have as many bytes as the shortest hash\", because if\n> the content implies it's a longer hash, we'd read off the end of the\n> buffer.\n> \n> I think in the long run we will need a parse_oid_hex() function that\n> takes a ptr/len (or start/end) pair.\n\nYes, that makes sense.\n\n> [...]\n\nMichael\n"},{"id":"328554","messageId":"32b3d338-6781-a600-2c7e-65dc2818aab5@alum.mit.edu","threadId":"46784","inReplyTo":"CAGZ79kbwCAidGR3cgukdjckZVYwj+qbOikqN-e934uP1yk9Cuw@mail.gmail.com","subject":"Re: [PATCH v2 02/21] prefix_ref_iterator: break when we leave the prefix","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-21T07:42:35Z","receivedAt":"2017-09-21T07:42:43Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 09/20/2017 10:25 PM, Stefan Beller wrote:\n> On Mon, Sep 18, 2017 at 11:22 PM, Michael Haggerty wrote:\n>> [...]\n>> +/* Return -1, 0, 1 if refname is before, inside, or after the prefix. */\n>> +static int compare_prefix(const char *refname, const char *prefix)\n>> +{\n>> + while (*prefix) {\n>> + if (*refname != *prefix)\n>> + return ((unsigned char)*refname < (unsigned char)*prefix) ? -1 : +1;\n> \n> This looks interesting.\n> \n> We get a signed char* , cast it to unsigned char* and then\n> compare byte by byte.\n\nNot quite. We get a `char *` of unknown signedness (it's\nimplementation-dependent), dereference it into a `char`, then cast that\nvalue to `unsigned char`. What you described would be\n\n *(const unsigned char *)refname < *(const unsigned char *)prefix\n\nBut I assume that these two variants would result in identical assembly\ncode.\n\n> [...]\n\nMichael\n"},{"id":"328560","messageId":"b092c424-987a-fe00-43d4-17062000dfc0@alum.mit.edu","threadId":"46784","inReplyTo":"20170920185119.upnyomtlxobxwvlw@sigill.intra.peff.net","subject":"Re: [PATCH v2 13/21] packed_ref_cache: keep the `packed-refs` file mmapped if possible","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-21T08:04:01Z","receivedAt":"2017-09-21T08:04:10Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 09/20/2017 08:40 PM, Jeff King wrote:\n> [...]\n> The overall strategy for this compile-time knob makes sense, but one\n> thing confused me:\n> \n>> +ifdef MMAP_PREVENTS_DELETE\n>> +\tBASIC_CFLAGS += -DMMAP_PREVENTS_DELETE\n>> +else\n>> +\tifdef USE_WIN32_MMAP\n>> +\t\tBASIC_CFLAGS += -DMMAP_PREVENTS_DELETE\n>> +\tendif\n>> +endif\n> \n> So setting the knob does what you'd expect. But if you don't set it,\n> then we still auto-tweak it based on the USE_WIN32_MMAP knob. Do we need\n> that? It seems like we set our new knob in config.mak.uname any time\n> we'd set USE_WIN32_MMAP. So this only has an effect in two cases:\n> \n> 1. You aren't on Windows, but you set USE_WIN32_MMAP yourself.\n> \n> 2. You are on Windows, but you manually unset MMAP_PREVENTS_DELETE.\n> \n> I expect both cases are rare (and would probably involve somebody\n> actively debugging these knobs). Probably it's a minor convenience in\n> case 1, but in case 2 it would be actively confusing, I'd think.\n\nMakes sense. I'll delete the `else` clause from the above hunk.\n\nOn 09/20/2017 08:51 PM, Jeff King wrote:\n> On Wed, Sep 20, 2017 at 02:40:58PM -0400, Jeff King wrote:\n> \n>>> +enum mmap_strategy {\n>>> +\t/*\n>>> +\t * Don't use mmap() at all for reading `packed-refs`.\n>>> +\t */\n>>> +\tMMAP_NONE,\n>>> +\n>>> +\t/*\n>>> +\t * Can use mmap() for reading `packed-refs`, but the file must\n>>> +\t * not remain mmapped. This is the usual option on Windows,\n>>> +\t * where you cannot rename a new version of a file onto a file\n>>> +\t * that is currently mmapped.\n>>> +\t */\n>>> +\tMMAP_TEMPORARY,\n>>\n>> I suspect you originally distinguished these cases so that NO_MMAP does\n>> not read into a fake-mmap buffer, followed by us copying it into another\n>> buffer. But AFAICT we handle the \"NONE\" and \"TEMPORARY\" cases exactly\n>> the same (by just doing a read_in_full() into our own buffer). Do we\n>> actually need separate strategies?\n> \n> In case you are reading these sequentially, I think I talked myself into\n> the utility of this during the next patch. ;)\n\nSorry about that. I'll add a forward breadcrumb to the log message of\nthis commit.\n\nMichael\n"},{"id":"328561","messageId":"d16e3003-e10e-6767-4d00-65e264a4a548@alum.mit.edu","threadId":"46784","inReplyTo":"20170920185047.6fzuspaseofb7r5x@sigill.intra.peff.net","subject":"Re: [PATCH v2 14/21] read_packed_refs(): ensure that references are ordered when read","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-09-21T08:27:14Z","receivedAt":"2017-09-21T08:27:24Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 09/20/2017 08:50 PM, Jeff King wrote:\n> On Tue, Sep 19, 2017 at 08:22:22AM +0200, Michael Haggerty wrote:\n>> If `packed-refs` was already sorted, then (if the system allows it) we\n>> can use the mmapped file contents directly. But if the system doesn't\n>> allow a file that is currently mmapped to be replaced using\n>> `rename()`, then it would be bad for us to keep the file mmapped for\n>> any longer than necessary. So, on such systems, always make a copy of\n>> the file contents, either as part of the sorting process, or\n>> afterwards.\n> \n> So this sort-of answers my question from the previous commit (why we\n> care about the distinction between NONE and TEMPORARY), since we now\n> start treating them differently.\n> \n> But I'm a bit confused why there's any advantage in the TEMPORARY case\n> to doing the mmap-and-copy versus just treating it like NONE and reading\n> it directly.\n> \n> Hmm, I guess it comes down to the double-allocation thing again? Let me\n> see if I have this right:\n> \n> 1. For NO_MMAP, we'd read the buffer once. If it's sorted, good. If\n> not, then we temporarily hold it in memory twice while we copy it\n> into the new sorted buffer.\n> \n> 2. For TEMPORARY, we mmap once. If it's sorted, then we make a single\n> copy. If it's not sorted, then we do the copy+sort as a single\n> step.\n> \n> 3. For MMAP_OK, if it's sorted, we're done. Otherwise, we do the\n> single copy.\n> \n> So this is really there to help the TEMPORARY case reading an old\n> unsorted file avoid needing to use double-the-ram during the copy?\n> \n> That seems like a good reason (and it does not seem to add too much\n> complexity).\n\nYes, that's correct. A deeper question is whether it's worth this extra\neffort to optimize the conversion from \"unsorted\" to \"known-sorted\",\nwhich it seems should only happen once per repository. But\n\n* Many more Git commands read the `packed-refs` file than write it.\n So an \"unsorted\" file might have to be read multiple times before\n the first time it is rewritten with the \"sorted\" trait.\n\n* Users might have multiple Git clients writing their `packed-refs`\n file (e.g., the git CLI plus JGit in Eclipse), and they might not\n upgrade both clients at the same time to versions that write the\n \"sorted\" trait. So a single repository might go back and forth\n between \"unsorted\" and \"known-sorted\" multiple times in its\n life.\n\n* Theoretically, somebody might have a `packed-refs` file that is so\n big that it takes up more than half of memory. I think there are\n scenarios where such a file could be converted to \"sorted\" form\n in `MMAP_TEMPORARY` mode but would fail in `MMAP_NONE` mode.\n\nOn the downside, in my benchmarking on Linux, there were hints that the\n`MMAP_TEMPORARY` branch might be a *tiny* bit slower than the `MMAP_OK`\nbranch when operating on a known-sorted `packed-refs` file. But the\nspeed difference was barely detectable (and might be illusory). And\nanyway, the speed difference on Linux is moot, since on Linux `MMAP_OK`\nmode will usually be used. It *would* be interesting to know if there is\na significant speed difference on Windows. Dscho?\n\nMichael\n"},{"id":"328579","messageId":"CAGZ79kZ5xcw3hw_aEp2ggLbC8AQm8DwpqK3+i5UO7s+aGzgXjQ@mail.gmail.com","threadId":"46784","inReplyTo":"20170921045932.b5y33fm7gao27ium@sigill.intra.peff.net","subject":"Re: [PATCH v2 02/21] prefix_ref_iterator: break when we leave the prefix","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-09-21T17:29:03Z","receivedAt":"2017-09-21T17:29:09Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Wed, Sep 20, 2017 at 9:59 PM, Jeff King wrote:\n\n>> But this compare function is not to order by the natural encoding order,\n>> but it's used to detect the '0' at the end of prefix, which orders\n>> before *any* unsigned char.\n>\n> It's not just detecting the \"0\". We care about the ordering overall (so\n> that \"refs/foo\" comes after \"refs/bar\", and we know that \"refs/bar/baz\"\n> cannot come after \"refs/foo\", and we can stop iterating).\n\nrefs/{foo,bar,bar/baz} is all ASCII, such that the ordering by byte value\nand byte position (2nd order) orders 'correctly'. correct in the sense as\nGit expects. But if you use other encodings, the natural encoding\nmay differ from the arbitrary order that we have here. (Example\nutf-8 with BOM and smileys)\n\nHowever these different orders do not matter (according to my initial\nconclusion), because we need (a) find out about '\\0' and (b) only need\nonly 'arbitrary' order (which is referred to by the \" ordered\" trait).\n\n>> Essentially compare_prefix wants to provide the same return\n>> value as `strncmp(refname, prefix, min(strlen(refname), strlen(prefix)));`\n>> except that it is optimized as we do not have to walk over a string\n>> multiple times (to determine length and then pass it to compare).\n>\n> Hmm, yeah, I think that would be an equivalent. I didn't think of that,\n> but as you say it would be less efficient.\n\nI was just too lazy to check if we had the results of strlen around already,\nsuch that the comparison would be equally cheap, but more readable.\nAlso IIRC later patches enhance this function, so we shall not make use\nof the strncmp function here.\n\n> The patch is credited to me, but I actually screwed up the ordering by\n> failing to do the unsigned cast. Michael fixed that part before posting\n> it. :)\n\nThanks,\nStefan\n"},{"id":"328761","messageId":"xmqqlgl4h9ff.fsf@gitster.mtv.corp.google.com","threadId":"46784","inReplyTo":"354c8088-ae24-479d-3b4e-fe8e189223b2@alum.mit.edu","subject":"Re: [PATCH v2 13/21] packed_ref_cache: keep the `packed-refs` file mmapped if possible","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-09-24T06:56:04Z","receivedAt":"2017-09-24T06:56:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty writes:\n\n>> +\tstruct stat st;\n>> +\tsize_t size, bytes_read;\n>\n> Coverity helpfully pointed out that `bytes_read` has to be signed:\n> `ssize_t`. I'll fix that in the next round after waiting for other comments.\n\nThanks. \n\nThe macOS build at Travis also was also upset about it, so I'd\ntentatively queue a trivial squash on top.\n\n"},{"id":"328846","messageId":"alpine.DEB.2.21.1.1709251743230.40514@virtualbox","threadId":"46784","inReplyTo":"d16e3003-e10e-6767-4d00-65e264a4a548@alum.mit.edu","subject":"Re: [PATCH v2 14/21] read_packed_refs(): ensure that references are ordered when read","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2017-09-25T15:44:55Z","receivedAt":"2017-09-25T15:45:19Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Michael,\n\nOn Thu, 21 Sep 2017, Michael Haggerty wrote:\n\n> On 09/20/2017 08:50 PM, Jeff King wrote:\n> > On Tue, Sep 19, 2017 at 08:22:22AM +0200, Michael Haggerty wrote:\n> >> If `packed-refs` was already sorted, then (if the system allows it)\n> >> we can use the mmapped file contents directly. But if the system\n> >> doesn't allow a file that is currently mmapped to be replaced using\n> >> `rename()`, then it would be bad for us to keep the file mmapped for\n> >> any longer than necessary. So, on such systems, always make a copy of\n> >> the file contents, either as part of the sorting process, or\n> >> afterwards.\n> > \n> > So this sort-of answers my question from the previous commit (why we\n> > care about the distinction between NONE and TEMPORARY), since we now\n> > start treating them differently.\n> > \n> > But I'm a bit confused why there's any advantage in the TEMPORARY case\n> > to doing the mmap-and-copy versus just treating it like NONE and reading\n> > it directly.\n> > \n> > Hmm, I guess it comes down to the double-allocation thing again? Let me\n> > see if I have this right:\n> > \n> > 1. For NO_MMAP, we'd read the buffer once. If it's sorted, good. If\n> > not, then we temporarily hold it in memory twice while we copy it\n> > into the new sorted buffer.\n> > \n> > 2. For TEMPORARY, we mmap once. If it's sorted, then we make a single\n> > copy. If it's not sorted, then we do the copy+sort as a single\n> > step.\n> > \n> > 3. For MMAP_OK, if it's sorted, we're done. Otherwise, we do the\n> > single copy.\n> > \n> > So this is really there to help the TEMPORARY case reading an old\n> > unsorted file avoid needing to use double-the-ram during the copy?\n> > \n> > That seems like a good reason (and it does not seem to add too much\n> > complexity).\n> \n> Yes, that's correct. A deeper question is whether it's worth this extra\n> effort to optimize the conversion from \"unsorted\" to \"known-sorted\",\n> which it seems should only happen once per repository. But\n> \n> * Many more Git commands read the `packed-refs` file than write it.\n> So an \"unsorted\" file might have to be read multiple times before\n> the first time it is rewritten with the \"sorted\" trait.\n> \n> * Users might have multiple Git clients writing their `packed-refs`\n> file (e.g., the git CLI plus JGit in Eclipse), and they might not\n> upgrade both clients at the same time to versions that write the\n> \"sorted\" trait. So a single repository might go back and forth\n> between \"unsorted\" and \"known-sorted\" multiple times in its\n> life.\n> \n> * Theoretically, somebody might have a `packed-refs` file that is so\n> big that it takes up more than half of memory. I think there are\n> scenarios where such a file could be converted to \"sorted\" form\n> in `MMAP_TEMPORARY` mode but would fail in `MMAP_NONE` mode.\n> \n> On the downside, in my benchmarking on Linux, there were hints that the\n> `MMAP_TEMPORARY` branch might be a *tiny* bit slower than the `MMAP_OK`\n> branch when operating on a known-sorted `packed-refs` file. But the\n> speed difference was barely detectable (and might be illusory). And\n> anyway, the speed difference on Linux is moot, since on Linux `MMAP_OK`\n> mode will usually be used. It *would* be interesting to know if there is\n> a significant speed difference on Windows. Dscho?\n\nSadly, I lack the time to test this thoroughly, but my experience is that\nthose things are dominated by I/O on Windows, i.e. that the malloc() and\ncopy won't matter all that much.\n\nIn any case, the same argument you make for Linux holds, in reverse, for\nWindows: we cannot use MMAP_OK on Windows, so the point is moot ;-)\n\nCiao,\nDscho\n"},{"id":"328847","messageId":"alpine.DEB.2.21.1.1709251753560.40514@virtualbox","threadId":"46784","inReplyTo":"20170920185724.ix7isdxfrsecxkjj@sigill.intra.peff.net","subject":"Re: [PATCH v2 00/21] Read `packed-refs` using mmap()","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2017-09-25T15:55:12Z","receivedAt":"2017-09-25T15:55:34Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Peff,\n\n\nOn Wed, 20 Sep 2017, Jeff King wrote:\n\n> On Tue, Sep 19, 2017 at 08:22:08AM +0200, Michael Haggerty wrote:\n> \n> > This branch is also available from my fork on GitHub as branch\n> > `mmap-packed-refs`.\n> > \n> > My main uncertainties are:\n> > \n> > 1. Does this code actually work on Windows?\n> > \n> \n> I can't really answer (1) due to lack of knowledge.\n\nSorry, I have only a couple of minutes per day to look through the flood\nof emails from the Git mailing list and to answer them, so I forgot to say\nthat I had a VM build and test Michael's patches, and they worked on\nWindows.\n\nCiao,\nDscho\n"}]}