{"thread":{"id":"47606","subject":"[PATCH] packed_ref_cache: don't use mmap() for small files","startedAt":"2018-01-13T16:18:40Z","lastAt":"2018-02-15T16:54:35Z","messageCount":33,"participants":["Kim Gybels","Johannes Schindelin","Michael Haggerty","Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"336559","messageId":"20180113161149.9564-1-kgybels@infogroep.be","threadId":"47606","inReplyTo":null,"subject":"[PATCH] packed_ref_cache: don't use mmap() for small files","fromName":"Kim Gybels","fromEmail":"kgybels@infogroep.be","sentAt":"2018-01-13T16:11:49Z","receivedAt":"2018-01-13T16:18:40Z","isPatch":true,"sender":{"key":"kgybels@infogroep.be","avatar":"https://avatars.githubusercontent.com/u/2051188?v=4"},"body":"Take a hint from commit ea68b0ce9f8ce8da3e360aed3cbd6720159ffbee and use\nread() instead of mmap() for small packed-refs files.\n\nThis also fixes the problem[1] where xmmap() returns NULL for zero\nlength[2], for which munmap() later fails.\n\nAlternatively, we could simply check for NULL before munmap(), or\nintroduce an xmunmap() that could be used together with xmmap().\n\n[1] https://github.com/git-for-windows/git/issues/1410\n[2] Logic introduced in commit 9130ac1e1966adb9922e64f645730d0d45383495\n\nSigned-off-by: Kim Gybels \n---\n refs/packed-backend.c | 14 ++++++++------\n 1 file changed, 8 insertions(+), 6 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex dab8a85d9a..7177e5bc2f 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -455,6 +455,8 @@ static void verify_buffer_safe(struct snapshot *snapshot)\n \t\t\t\t last_line, eof - last_line);\n }\n \n+#define SMALL_FILE_SIZE (32*1024)\n+\n /*\n * Depending on `mmap_strategy`, either mmap or read the contents of\n * the `packed-refs` file into the snapshot. Return 1 if the file\n@@ -489,21 +491,21 @@ static int load_contents(struct snapshot *snapshot)\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+\tif (!size) {\n+\t\tsnapshot->buf = NULL;\n+\t\tsnapshot->eof = NULL;\n+\t\tsnapshot->mmapped = 0;\n+\t} else if (size <= SMALL_FILE_SIZE || mmap_strategy == MMAP_NONE) {\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\", 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} else {\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 \n-- \n2.15.1.windows.2\n\n"},{"id":"336566","messageId":"nycvar.QRO.7.76.6.1801131954380.31@ZVAVAG-6OXH6DA.rhebcr.pbec.zvpebfbsg.pbz","threadId":"47606","inReplyTo":"20180113161149.9564-1-kgybels@infogroep.be","subject":"Re: [PATCH] packed_ref_cache: don't use mmap() for small files","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2018-01-13T18:56:26Z","receivedAt":"2018-01-13T18:56:47Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sat, 13 Jan 2018, Kim Gybels wrote:\n\n> Take a hint from commit ea68b0ce9f8ce8da3e360aed3cbd6720159ffbee and use\n\nMaybe use\n\n\tea68b0ce9f8 (hash-object: don't use mmap() for small files,\n\t2010-02-21)\n\ninstead of the full commit name?\n\n> read() instead of mmap() for small packed-refs files.\n> \n> This also fixes the problem[1] where xmmap() returns NULL for zero\n> length[2], for which munmap() later fails.\n> \n> Alternatively, we could simply check for NULL before munmap(), or\n> introduce an xmunmap() that could be used together with xmmap().\n> \n> [1] https://github.com/git-for-windows/git/issues/1410\n> [2] Logic introduced in commit 9130ac1e1966adb9922e64f645730d0d45383495\n> \n> Signed-off-by: Kim Gybels \n> ---\n> refs/packed-backend.c | 14 ++++++++------\n> 1 file changed, 8 insertions(+), 6 deletions(-)\n> \n> diff --git a/refs/packed-backend.c b/refs/packed-backend.c\n> index dab8a85d9a..7177e5bc2f 100644\n> --- a/refs/packed-backend.c\n> +++ b/refs/packed-backend.c\n> @@ -455,6 +455,8 @@ static void verify_buffer_safe(struct snapshot *snapshot)\n> \t\t\t\t last_line, eof - last_line);\n> }\n> \n> +#define SMALL_FILE_SIZE (32*1024)\n> +\n> /*\n> * Depending on `mmap_strategy`, either mmap or read the contents of\n> * the `packed-refs` file into the snapshot. Return 1 if the file\n> @@ -489,21 +491,21 @@ static int load_contents(struct snapshot *snapshot)\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> +\tif (!size) {\n> +\t\tsnapshot->buf = NULL;\n> +\t\tsnapshot->eof = NULL;\n> +\t\tsnapshot->mmapped = 0;\n> +\t} else if (size <= SMALL_FILE_SIZE || mmap_strategy == MMAP_NONE) {\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\", 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} else {\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\nNicely explained, and nicely solved, for a potential extra performance\nbenefit ;-)\n\nThank you!\nDscho\n"},{"id":"336597","messageId":"20180114191416.2368-1-kgybels@infogroep.be","threadId":"47606","inReplyTo":"20180113161149.9564-1-kgybels@infogroep.be","subject":"[PATCH v2] packed_ref_cache: don't use mmap() for small files","fromName":"Kim Gybels","fromEmail":"kgybels@infogroep.be","sentAt":"2018-01-14T19:14:16Z","receivedAt":"2018-01-14T19:15:26Z","isPatch":true,"sender":{"key":"kgybels@infogroep.be","avatar":"https://avatars.githubusercontent.com/u/2051188?v=4"},"body":"Take a hint from commit ea68b0ce9f8 (hash-object: don't use mmap() for\nsmall files, 2010-02-21) and use read() instead of mmap() for small\npacked-refs files.\n\nThis also fixes the problem[1] where xmmap() returns NULL for zero\nlength[2], for which munmap() later fails.\n\nAlternatively, we could simply check for NULL before munmap(), or\nintroduce xmunmap() that could be used together with xmmap().\n\n[1] https://github.com/git-for-windows/git/issues/1410\n[2] Logic introduced in commit 9130ac1e196 (Better error messages for\n corrupt databases, 2007-01-11)\n\nSigned-off-by: Kim Gybels \n---\nChange since v1: reworded commit message based on Johannes Schindelin's\nfeedback: shorter commit hashes, and included commit titles.\n\n refs/packed-backend.c | 14 ++++++++------\n 1 file changed, 8 insertions(+), 6 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex dab8a85d9a..7177e5bc2f 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -455,6 +455,8 @@ static void verify_buffer_safe(struct snapshot *snapshot)\n \t\t\t\t last_line, eof - last_line);\n }\n \n+#define SMALL_FILE_SIZE (32*1024)\n+\n /*\n * Depending on `mmap_strategy`, either mmap or read the contents of\n * the `packed-refs` file into the snapshot. Return 1 if the file\n@@ -489,21 +491,21 @@ static int load_contents(struct snapshot *snapshot)\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+\tif (!size) {\n+\t\tsnapshot->buf = NULL;\n+\t\tsnapshot->eof = NULL;\n+\t\tsnapshot->mmapped = 0;\n+\t} else if (size <= SMALL_FILE_SIZE || mmap_strategy == MMAP_NONE) {\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\", 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} else {\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 \n-- \n2.16.0.rc2.windows.1\n\n"},{"id":"336617","messageId":"cover.1516017331.git.mhagger@alum.mit.edu","threadId":"47606","inReplyTo":"20180114191416.2368-1-kgybels@infogroep.be","subject":"[PATCH 0/3] Supplements to \"packed_ref_cache: don't use mmap() for small files\"","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2018-01-15T12:17:32Z","receivedAt":"2018-01-15T12:17:58Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Thanks for your patch. I haven't measured the performance difference\nof `mmap()` vs. `read()` for small `packed-refs` files, but it's not\nsurprising that `read()` would be faster.\n\nI especially like the fix for zero-length `packed-refs` files. (Even\nthough AFAIK Git never writes such files, they are totally legitimate\nand shouldn't cause Git to fail.) With or without the additions\nmentioned below,\n\nReviewed-by: Michael Haggerty \n\nWhile reviewing your patch, I realized that some areas of the existing\ncode use constructs that are undefined according to the C standard,\nsuch as computing `NULL + 0` and `NULL - NULL`. This was already wrong\n(and would come up more frequently after your change). Even though\nthese are unlikely to be problems in the real world, it would be good\nto avoid them.\n\nSo I will follow up this email with three patches:\n\n1. Mention that `snapshot::buf` can be NULL for empty files\n\n I suggest squashing this into your patch, to make it clear that\n `snapshot::buf` and `snapshot::eof` can also be NULL if the\n `packed-refs` file is empty.\n\n2. create_snapshot(): exit early if the file was empty\n\n Avoid undefined behavior by returning early if `snapshot->buf` is\n NULL.\n\n3. find_reference_location(): don't invoke if `snapshot->buf` is NULL\n\n Avoid undefined behavior and confusing semantics by not calling\n `find_reference_location()` when `snapshot->buf` is NULL.\n\nMichael\n\nMichael Haggerty (3):\n SQUASH? Mention that `snapshot::buf` can be NULL for empty files\n create_snapshot(): exit early if the file was empty\n find_reference_location(): don't invoke if `snapshot->buf` is NULL\n\n refs/packed-backend.c | 21 ++++++++++++++-------\n 1 file changed, 14 insertions(+), 7 deletions(-)\n\n-- \n2.14.2\n\n"},{"id":"336618","messageId":"131281e13bd6c25246e0e0ab263fc9a2f364d6e0.1516017331.git.mhagger@alum.mit.edu","threadId":"47606","inReplyTo":"20180114191416.2368-1-kgybels@infogroep.be","subject":"[PATCH 1/3] SQUASH? Mention that `snapshot::buf` can be NULL for empty files","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2018-01-15T12:17:33Z","receivedAt":"2018-01-15T12:18:00Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Signed-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 10 +++++-----\n 1 file changed, 5 insertions(+), 5 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 01a13cb817..f20f05b4df 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -69,11 +69,11 @@ struct snapshot {\n \n \t/*\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 * already sorted and if mmapping is allowed, this points at\n+\t * the mmapped contents of the file. If not, this points at\n+\t * heap-allocated memory containing the contents, sorted. If\n+\t * there were no contents (e.g., because the file didn't exist\n+\t * or was empty), `buf` and `eof` are both NULL.\n \t */\n \tchar *buf, *eof;\n \n-- \n2.14.2\n\n"},{"id":"336619","messageId":"02915e24958741927467ed750e9782d02ec40c80.1516017331.git.mhagger@alum.mit.edu","threadId":"47606","inReplyTo":"20180114191416.2368-1-kgybels@infogroep.be","subject":"[PATCH 2/3] create_snapshot(): exit early if the file was empty","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2018-01-15T12:17:34Z","receivedAt":"2018-01-15T12:18:03Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"If the `packed_refs` files is entirely empty (i.e., not even a header\nline), then `load_contents()` returns 1 even though `snapshot->buf`\nand `snapshot->eof` both end up set to NULL. In that case, the\nsubsequent processing that `create_snapshot()` does is unnecessary,\nand also involves computing `NULL - NULL` and `NULL + 0`, which are\nprobably safe in real life but are technically undefined in C.\n\nSidestep both issues by exiting early if `snapshot->buf` is NULL.\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex f20f05b4df..36796d65f0 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -613,7 +613,7 @@ static struct snapshot *create_snapshot(struct packed_ref_store *refs)\n \tacquire_snapshot(snapshot);\n \tsnapshot->peeled = PEELED_NONE;\n \n-\tif (!load_contents(snapshot))\n+\tif (!load_contents(snapshot) || !snapshot->buf)\n \t\treturn snapshot;\n \n \t/* If the file has a header line, process it: */\n-- \n2.14.2\n\n"},{"id":"336620","messageId":"46a457904cf0261e337dfd94dc2f1d62abf64053.1516017331.git.mhagger@alum.mit.edu","threadId":"47606","inReplyTo":"20180114191416.2368-1-kgybels@infogroep.be","subject":"[PATCH 3/3] find_reference_location(): don't invoke if `snapshot->buf` is NULL","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2018-01-15T12:17:35Z","receivedAt":"2018-01-15T12:18:06Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"If `snapshot->buf` is NULL, then `find_reference_location()` has two\nproblems:\n\n1. It relies on behavior that is technically undefined in C, such as\n computing `NULL + 0`.\n\n2. It returns NULL if the reference doesn't exist, even if `mustexist`\n is not set. This problem doesn't come up in the current code,\n because we never call this function with `snapshot->buf == NULL`\n and `mustexist` set. But it is something that future callers need\n to be aware of.\n\nWe could fix the first problem by adding some extra logic to the\nfunction. But considering both problems together, it is more\nstraightforward to document that the function should only be called if\n`snapshot->buf` is non-NULL.\n\nAdjust `packed_read_raw_ref()` to return early if `snapshot->buf` is\nNULL rather than calling `find_reference_location()`.\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 9 ++++++++-\n 1 file changed, 8 insertions(+), 1 deletion(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 36796d65f0..ed2b396bef 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -521,8 +521,9 @@ static int load_contents(struct snapshot *snapshot)\n * reference name; for example, one could search for \"refs/replace/\"\n * to find the start of any replace references.\n *\n+ * This function must only be called if `snapshot->buf` is non-NULL.\n * The record is sought using a binary search, so `snapshot->buf` must\n- * be sorted.\n+ * also be sorted.\n */\n static const char *find_reference_location(struct snapshot *snapshot,\n \t\t\t\t\t const char *refname, int mustexist)\n@@ -728,6 +729,12 @@ static int packed_read_raw_ref(struct ref_store *ref_store,\n \n \t*type = 0;\n \n+\tif (!snapshot->buf) {\n+\t\t/* There are no packed references */\n+\t\terrno = ENOENT;\n+\t\treturn -1;\n+\t}\n+\n \trec = find_reference_location(snapshot, refname, 1);\n \n \tif (!rec) {\n-- \n2.14.2\n\n"},{"id":"336627","messageId":"20180115211505.GA4778@sigill.intra.peff.net","threadId":"47606","inReplyTo":"20180113161149.9564-1-kgybels@infogroep.be","subject":"Re: [PATCH] packed_ref_cache: don't use mmap() for small files","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-01-15T21:15:05Z","receivedAt":"2018-01-15T21:15:13Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Jan 13, 2018 at 05:11:49PM +0100, Kim Gybels wrote:\n\n> Take a hint from commit ea68b0ce9f8ce8da3e360aed3cbd6720159ffbee and use\n> read() instead of mmap() for small packed-refs files.\n> \n> This also fixes the problem[1] where xmmap() returns NULL for zero\n> length[2], for which munmap() later fails.\n> \n> Alternatively, we could simply check for NULL before munmap(), or\n> introduce an xmunmap() that could be used together with xmmap().\n\nThis looks good to me, and since it's a recent-ish regression, I think\nwe should take the minimal fix here.\n\nBut it does make me wonder whether xmmap() ought to be doing this \"small\nmmap\" optimization for us. Obviously that only works when we do\nMAP_PRIVATE and never write to the result. But that's how we always use\nit anyway, and we're restricted to that to work with the NO_MMAP wrapper\nin compat/mmap.c.\n\n> @@ -489,21 +491,21 @@ static int load_contents(struct snapshot *snapshot)\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> +\tif (!size) {\n> +\t\tsnapshot->buf = NULL;\n> +\t\tsnapshot->eof = NULL;\n> +\t\tsnapshot->mmapped = 0;\n> +\t} else if (size <= SMALL_FILE_SIZE || mmap_strategy == MMAP_NONE) {\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\", snapshot->refs->path);\n> \t\tsnapshot->eof = snapshot->buf + size;\n> \t\tsnapshot->mmapped = 0;\n\nIf the \"!size\" case is just lumped in with \"size <= SMALL_FILE_SIZE\",\nthen we'd try to xmalloc(0), which is guaranteed to work (we fallback to\na 1-byte allocation if necessary). Would that make things simpler and\nmore consistent for the rest of the code to always have snapshot->buf be\na valid pointer (just based on seeing Michael's follow-up patches)?\n\n-Peff\n"},{"id":"336636","messageId":"20180115233751.GA1781@infogroep.be","threadId":"47606","inReplyTo":"20180115211505.GA4778@sigill.intra.peff.net","subject":"Re: [PATCH] packed_ref_cache: don't use mmap() for small files","fromName":"Kim Gybels","fromEmail":"kgybels@infogroep.be","sentAt":"2018-01-15T23:37:51Z","receivedAt":"2018-01-15T23:47:42Z","isPatch":true,"sender":{"key":"kgybels@infogroep.be","avatar":"https://avatars.githubusercontent.com/u/2051188?v=4"},"body":"On (15/01/18 16:15), Jeff King wrote:\n\n> On Sat, Jan 13, 2018 at 05:11:49PM +0100, Kim Gybels wrote:\n> \n> > Take a hint from commit ea68b0ce9f8ce8da3e360aed3cbd6720159ffbee and use\n> > read() instead of mmap() for small packed-refs files.\n> > \n> > This also fixes the problem[1] where xmmap() returns NULL for zero\n> > length[2], for which munmap() later fails.\n> > \n> > Alternatively, we could simply check for NULL before munmap(), or\n> > introduce an xmunmap() that could be used together with xmmap().\n> \n> This looks good to me, and since it's a recent-ish regression, I think\n> we should take the minimal fix here.\n\nThe minimal fix being a simple NULL check before munmap()?\n\n> But it does make me wonder whether xmmap() ought to be doing this \"small\n> mmap\" optimization for us. Obviously that only works when we do\n> MAP_PRIVATE and never write to the result. But that's how we always use\n> it anyway, and we're restricted to that to work with the NO_MMAP wrapper\n> in compat/mmap.c.\n\nMaybe I should have left the optimization for small files out of the patch for\nthe zero length regression. After all, read() vs mmap() performance might\ndepend on other factors than just size.\n\n> > @@ -489,21 +491,21 @@ static int load_contents(struct snapshot *snapshot)\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> > +\tif (!size) {\n> > +\t\tsnapshot->buf = NULL;\n> > +\t\tsnapshot->eof = NULL;\n> > +\t\tsnapshot->mmapped = 0;\n> > +\t} else if (size <= SMALL_FILE_SIZE || mmap_strategy == MMAP_NONE) {\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\", snapshot->refs->path);\n> > \t\tsnapshot->eof = snapshot->buf + size;\n> > \t\tsnapshot->mmapped = 0;\n> \n> If the \"!size\" case is just lumped in with \"size <= SMALL_FILE_SIZE\",\n> then we'd try to xmalloc(0), which is guaranteed to work (we fallback to\n> a 1-byte allocation if necessary). Would that make things simpler and\n> more consistent for the rest of the code to always have snapshot->buf be\n> a valid pointer (just based on seeing Michael's follow-up patches)?\n\nIndeed, all those patches are to avoid using the NULL pointers in ways that are\nundefined. We could also copy index_core's way of handling the zero length\ncase:\nret = index_mem(sha1, \"\", size, type, path, flags);\n\nPoint to some static memory instead of NULL, then all the pointer arithmetic is defined.\n\n-Kim\n"},{"id":"336637","messageId":"20180115235251.GA21900@sigill.intra.peff.net","threadId":"47606","inReplyTo":"20180115233751.GA1781@infogroep.be","subject":"Re: [PATCH] packed_ref_cache: don't use mmap() for small files","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-01-15T23:52:52Z","receivedAt":"2018-01-15T23:52:58Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 16, 2018 at 12:37:51AM +0100, Kim Gybels wrote:\n\n> > This looks good to me, and since it's a recent-ish regression, I think\n> > we should take the minimal fix here.\n> \n> The minimal fix being a simple NULL check before munmap()?\n\nSorry to be unclear. I just meant that your patch is probably fine\nas-is. I didn't want to hold up a regression fix with a bunch of\nnit-picking or possible future work, when we could build that on top\nlater.\n\n> > But it does make me wonder whether xmmap() ought to be doing this \"small\n> > mmap\" optimization for us. Obviously that only works when we do\n> > MAP_PRIVATE and never write to the result. But that's how we always use\n> > it anyway, and we're restricted to that to work with the NO_MMAP wrapper\n> > in compat/mmap.c.\n> \n> Maybe I should have left the optimization for small files out of the patch for\n> the zero length regression. After all, read() vs mmap() performance might\n> depend on other factors than just size.\n\nI'd be OK including it here, since there's prior art in the commit you\nreferenced. Though of course actual numbers are always good when\nclaiming an optimization. :)\n\n> > If the \"!size\" case is just lumped in with \"size <= SMALL_FILE_SIZE\",\n> > then we'd try to xmalloc(0), which is guaranteed to work (we fallback to\n> > a 1-byte allocation if necessary). Would that make things simpler and\n> > more consistent for the rest of the code to always have snapshot->buf be\n> > a valid pointer (just based on seeing Michael's follow-up patches)?\n> \n> Indeed, all those patches are to avoid using the NULL pointers in ways that are\n> undefined. We could also copy index_core's way of handling the zero length\n> case:\n> ret = index_mem(sha1, \"\", size, type, path, flags);\n> \n> Point to some static memory instead of NULL, then all the pointer arithmetic is defined.\n\nYep, that would work, too. I don't think the overhead of a\nonce-per-process xmalloc(0) is a big deal, though, if it keeps the code\nsimpler (though I admit it is not that complex either way).\n\n-Peff\n"},{"id":"336672","messageId":"20180116193815.4568-1-kgybels@infogroep.be","threadId":"47606","inReplyTo":"20180115235251.GA21900@sigill.intra.peff.net","subject":"[PATCH v3] packed_ref_cache: don't use mmap() for small files","fromName":"Kim Gybels","fromEmail":"kgybels@infogroep.be","sentAt":"2018-01-16T19:38:15Z","receivedAt":"2018-01-16T19:39:14Z","isPatch":true,"sender":{"key":"kgybels@infogroep.be","avatar":"https://avatars.githubusercontent.com/u/2051188?v=4"},"body":"Take a hint from commit ea68b0ce9f8 (hash-object: don't use mmap() for\nsmall files, 2010-02-21) and use read() instead of mmap() for small\npacked-refs files.\n\nThis also fixes the problem[1] where xmmap() returns NULL for zero\nlength[2], for which munmap() later fails.\n\nAlternatively, we could simply check for NULL before munmap(), or\nintroduce xmunmap() that could be used together with xmmap(). However,\nalways setting snapshot->buf to a valid pointer, by relying on\nxmalloc(0)'s fallback to 1-byte allocation, makes using snapshots\neasier.\n\n[1] https://github.com/git-for-windows/git/issues/1410\n[2] Logic introduced in commit 9130ac1e196 (Better error messages for\n corrupt databases, 2007-01-11)\n\nSigned-off-by: Kim Gybels \n---\n\nChange since v2: removed separate case for zero length as suggested by Peff,\nensuring that snapshot->buf is always a valid pointer.\n\n refs/packed-backend.c | 10 ++++------\n 1 file changed, 4 insertions(+), 6 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex dab8a85d9a..b6e2bc3c1d 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -455,6 +455,8 @@ static void verify_buffer_safe(struct snapshot *snapshot)\n \t\t\t\t last_line, eof - last_line);\n }\n \n+#define SMALL_FILE_SIZE (32*1024)\n+\n /*\n * Depending on `mmap_strategy`, either mmap or read the contents of\n * the `packed-refs` file into the snapshot. Return 1 if the file\n@@ -489,21 +491,17 @@ static int load_contents(struct snapshot *snapshot)\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+\tif (size <= SMALL_FILE_SIZE || mmap_strategy == MMAP_NONE) {\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\", 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} else {\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 \n-- \n2.15.1.windows.2\n\n"},{"id":"336718","messageId":"nycvar.QRO.7.76.6.1801172123020.31@ZVAVAG-6OXH6DA.rhebcr.pbec.zvpebfbsg.pbz","threadId":"47606","inReplyTo":"cover.1516017331.git.mhagger@alum.mit.edu","subject":"Re: [PATCH 0/3] Supplements to \"packed_ref_cache: don't use mmap() for small files\"","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2018-01-17T20:23:44Z","receivedAt":"2018-01-17T20:24:14Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Michael,\n\nOn Mon, 15 Jan 2018, Michael Haggerty wrote:\n\n> Thanks for your patch. I haven't measured the performance difference\n> of `mmap()` vs. `read()` for small `packed-refs` files, but it's not\n> surprising that `read()` would be faster.\n> \n> I especially like the fix for zero-length `packed-refs` files. (Even\n> though AFAIK Git never writes such files, they are totally legitimate\n> and shouldn't cause Git to fail.) With or without the additions\n> mentioned below,\n> \n> Reviewed-by: Michael Haggerty \n> \n> While reviewing your patch, I realized that some areas of the existing\n> code use constructs that are undefined according to the C standard,\n> such as computing `NULL + 0` and `NULL - NULL`. This was already wrong\n> (and would come up more frequently after your change). Even though\n> these are unlikely to be problems in the real world, it would be good\n> to avoid them.\n> \n> So I will follow up this email with three patches:\n> \n> 1. Mention that `snapshot::buf` can be NULL for empty files\n> \n> I suggest squashing this into your patch, to make it clear that\n> `snapshot::buf` and `snapshot::eof` can also be NULL if the\n> `packed-refs` file is empty.\n> \n> 2. create_snapshot(): exit early if the file was empty\n> \n> Avoid undefined behavior by returning early if `snapshot->buf` is\n> NULL.\n> \n> 3. find_reference_location(): don't invoke if `snapshot->buf` is NULL\n> \n> Avoid undefined behavior and confusing semantics by not calling\n> `find_reference_location()` when `snapshot->buf` is NULL.\n> \n> Michael\n> \n> Michael Haggerty (3):\n> SQUASH? Mention that `snapshot::buf` can be NULL for empty files\n> create_snapshot(): exit early if the file was empty\n> find_reference_location(): don't invoke if `snapshot->buf` is NULL\n\nI reviewed those patches and find the straight-forward (and obviously\ngood).\n\nThanks,\nDscho\n"},{"id":"336729","messageId":"xmqqvag0qhjg.fsf@gitster.mtv.corp.google.com","threadId":"47606","inReplyTo":"cover.1516017331.git.mhagger@alum.mit.edu","subject":"Re: [PATCH 0/3] Supplements to \"packed_ref_cache: don't use mmap() for small files\"","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-01-17T21:52:51Z","receivedAt":"2018-01-17T21:52:59Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty writes:\n\n> So I will follow up this email with three patches:\n>\n> 1. Mention that `snapshot::buf` can be NULL for empty files\n>\n> I suggest squashing this into your patch, to make it clear that\n> `snapshot::buf` and `snapshot::eof` can also be NULL if the\n> `packed-refs` file is empty.\n>\n> 2. create_snapshot(): exit early if the file was empty\n>\n> Avoid undefined behavior by returning early if `snapshot->buf` is\n> NULL.\n>\n> 3. find_reference_location(): don't invoke if `snapshot->buf` is NULL\n>\n> Avoid undefined behavior and confusing semantics by not calling\n> `find_reference_location()` when `snapshot->buf` is NULL.\n\nThese look all sensible with today's code and with v2 from this\nthread.\n\nWith the v3, i.e. \"do the xmalloc() even for size==0\", however,\nsnapshot->buf would never be NULL, so I'd shelve them for now,\nthough.\n\nThanks.\n"},{"id":"336732","messageId":"20180117220902.GA14952@sigill.intra.peff.net","threadId":"47606","inReplyTo":"20180116193815.4568-1-kgybels@infogroep.be","subject":"Re: [PATCH v3] packed_ref_cache: don't use mmap() for small files","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-01-17T22:09:02Z","receivedAt":"2018-01-17T22:09:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 16, 2018 at 08:38:15PM +0100, Kim Gybels wrote:\n\n> Take a hint from commit ea68b0ce9f8 (hash-object: don't use mmap() for\n> small files, 2010-02-21) and use read() instead of mmap() for small\n> packed-refs files.\n> \n> This also fixes the problem[1] where xmmap() returns NULL for zero\n> length[2], for which munmap() later fails.\n> \n> Alternatively, we could simply check for NULL before munmap(), or\n> introduce xmunmap() that could be used together with xmmap(). However,\n> always setting snapshot->buf to a valid pointer, by relying on\n> xmalloc(0)'s fallback to 1-byte allocation, makes using snapshots\n> easier.\n> \n> [1] https://github.com/git-for-windows/git/issues/1410\n> [2] Logic introduced in commit 9130ac1e196 (Better error messages for\n> corrupt databases, 2007-01-11)\n> \n> Signed-off-by: Kim Gybels \n> ---\n> \n> Change since v2: removed separate case for zero length as suggested by Peff,\n> ensuring that snapshot->buf is always a valid pointer.\n\nThanks, this looks fine to me (I'd be curious to hear from Michael if\nthis eliminates the need for the other patches).\n\n-Peff\n"},{"id":"337018","messageId":"29c51594-6e29-be34-3d5f-2b9f399490f2@alum.mit.edu","threadId":"47606","inReplyTo":"20180117220902.GA14952@sigill.intra.peff.net","subject":"Re: [PATCH v3] packed_ref_cache: don't use mmap() for small files","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2018-01-21T04:41:48Z","receivedAt":"2018-01-21T04:41:58Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 01/17/2018 11:09 PM, Jeff King wrote:\n> On Tue, Jan 16, 2018 at 08:38:15PM +0100, Kim Gybels wrote:\n> \n>> Take a hint from commit ea68b0ce9f8 (hash-object: don't use mmap() for\n>> small files, 2010-02-21) and use read() instead of mmap() for small\n>> packed-refs files.\n>>\n>> This also fixes the problem[1] where xmmap() returns NULL for zero\n>> length[2], for which munmap() later fails.\n>>\n>> Alternatively, we could simply check for NULL before munmap(), or\n>> introduce xmunmap() that could be used together with xmmap(). However,\n>> always setting snapshot->buf to a valid pointer, by relying on\n>> xmalloc(0)'s fallback to 1-byte allocation, makes using snapshots\n>> easier.\n>>\n>> [1] https://github.com/git-for-windows/git/issues/1410\n>> [2] Logic introduced in commit 9130ac1e196 (Better error messages for\n>> corrupt databases, 2007-01-11)\n>>\n>> Signed-off-by: Kim Gybels \n>> ---\n>>\n>> Change since v2: removed separate case for zero length as suggested by Peff,\n>> ensuring that snapshot->buf is always a valid pointer.\n> \n> Thanks, this looks fine to me (I'd be curious to hear from Michael if\n> this eliminates the need for the other patches).\n\n`snapshot->buf` can still be NULL if the `packed-refs` file didn't exist\n(see the earlier code path in `load_contents()`). So either that code\npath *also* has to get the `xmalloc()` treatment, or my third patch is\nstill necessary. (My second patch wouldn't be necessary because the\nENOENT case makes `load_contents()` return 0, triggering the early exit\nfrom `create_snapshot()`.)\n\nI don't have a strong preference either way.\n\nMichael\n"},{"id":"337099","messageId":"xmqqh8rdn113.fsf@gitster.mtv.corp.google.com","threadId":"47606","inReplyTo":"29c51594-6e29-be34-3d5f-2b9f399490f2@alum.mit.edu","subject":"Re: [PATCH v3] packed_ref_cache: don't use mmap() for small files","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-01-22T19:31:20Z","receivedAt":"2018-01-22T19:31:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty writes:\n\n> `snapshot->buf` can still be NULL if the `packed-refs` file didn't exist\n> (see the earlier code path in `load_contents()`). So either that code\n> path *also* has to get the `xmalloc()` treatment, or my third patch is\n> still necessary. (My second patch wouldn't be necessary because the\n> ENOENT case makes `load_contents()` return 0, triggering the early exit\n> from `create_snapshot()`.)\n>\n> I don't have a strong preference either way.\n\nWhich would be a two-liner, like the attached, which does not look\ntoo bad by itself.\n\nThe direction, if we take this approach, means that we are declaring\nthat .buf being NULL is an invalid state for a snapshot to be in,\ninstead of saying \"an empty snapshot looks exactly like one that was\nfreshly initialized\", which seems to be the intention of the original\ndesign.\n\nAfter Kim's fix and with 3/3 in your follow-up series, various\nhelpers are still unsafe against .buf being NULL, like\nsort_snapshot(), verify_buffer_safe(), clear_snapshot_buffer() (only\nwhen mmapped bit is set), find_reference_location().\n\npacked_ref_iterator_begin() checks if snapshot->buf is NULL and\nreturns early. At the first glance, this appears a useful short cut\nto optimize the empty case away, but the check also is acting as a\nguard to prevent a snapshot with NULL .buf from being fed to an\nunsafe find_reference_location(). An implicit guard like this feels\na bit more brittle than my liking. If we ensure .buf is never NULL,\nthat check can become a pure short-cut optimization and stop being\na correctness thing.\n\nSo...\n\n\n refs/packed-backend.c | 9 ++++-----\n 1 file changed, 4 insertions(+), 5 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex b6e2bc3c1d..1eeb5c7f80 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -473,12 +473,11 @@ static int load_contents(struct snapshot *snapshot)\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 * Treat missing \"packed-refs\" as equivalent to\n+\t\t\t * it being empty.\n \t\t\t */\n+\t\t\tsnapshot->eof = snapshot->buf = xmalloc(0);\n+\t\t\tsnapshot->mmapped = 0;\n \t\t\treturn 0;\n \t\t} else {\n \t\t\tdie_errno(\"couldn't read %s\", snapshot->refs->path);\n"},{"id":"337227","messageId":"cea5e366-dc95-6f41-6373-f8bbef103561@alum.mit.edu","threadId":"47606","inReplyTo":"xmqqh8rdn113.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v3] packed_ref_cache: don't use mmap() for small files","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2018-01-24T11:05:01Z","receivedAt":"2018-01-24T11:05:12Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 01/22/2018 08:31 PM, Junio C Hamano wrote:\n> Michael Haggerty writes:\n> \n>> `snapshot->buf` can still be NULL if the `packed-refs` file didn't exist\n>> (see the earlier code path in `load_contents()`). So either that code\n>> path *also* has to get the `xmalloc()` treatment, or my third patch is\n>> still necessary. (My second patch wouldn't be necessary because the\n>> ENOENT case makes `load_contents()` return 0, triggering the early exit\n>> from `create_snapshot()`.)\n>>\n>> I don't have a strong preference either way.\n> \n> Which would be a two-liner, like the attached, which does not look\n> too bad by itself.\n> \n> The direction, if we take this approach, means that we are declaring\n> that .buf being NULL is an invalid state for a snapshot to be in,\n> instead of saying \"an empty snapshot looks exactly like one that was\n> freshly initialized\", which seems to be the intention of the original\n> design.\n> \n> After Kim's fix and with 3/3 in your follow-up series, various\n> helpers are still unsafe against .buf being NULL, like\n> sort_snapshot(), verify_buffer_safe(), clear_snapshot_buffer() (only\n> when mmapped bit is set), find_reference_location().\n> \n> packed_ref_iterator_begin() checks if snapshot->buf is NULL and\n> returns early. At the first glance, this appears a useful short cut\n> to optimize the empty case away, but the check also is acting as a\n> guard to prevent a snapshot with NULL .buf from being fed to an\n> unsafe find_reference_location(). An implicit guard like this feels\n> a bit more brittle than my liking. If we ensure .buf is never NULL,\n> that check can become a pure short-cut optimization and stop being\n> a correctness thing.\n> \n> So...\n> \n> \n> refs/packed-backend.c | 9 ++++-----\n> 1 file changed, 4 insertions(+), 5 deletions(-)\n> \n> diff --git a/refs/packed-backend.c b/refs/packed-backend.c\n> index b6e2bc3c1d..1eeb5c7f80 100644\n> --- a/refs/packed-backend.c\n> +++ b/refs/packed-backend.c\n> @@ -473,12 +473,11 @@ static int load_contents(struct snapshot *snapshot)\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 * Treat missing \"packed-refs\" as equivalent to\n> +\t\t\t * it being empty.\n> \t\t\t */\n> +\t\t\tsnapshot->eof = snapshot->buf = xmalloc(0);\n> +\t\t\tsnapshot->mmapped = 0;\n> \t\t\treturn 0;\n> \t\t} else {\n> \t\t\tdie_errno(\"couldn't read %s\", snapshot->refs->path);\n> \n\nThat would work, though if you go this way, please also change the\ndocstring for `snapshot::buf`, which still says that `buf` and `eof` can\nbe `NULL`.\n\nThe other alternative, making `snapshot` safe for NULLs, becomes easier\nif `snapshot` stores a pointer to the start of the reference section of\nthe `packed-refs` contents (i.e., after the header line), rather than\nrepeatedly computing that address from `snapshot->buf +\nsnapshot->header_len`. With this change, code that is technically\nundefined when the fields are NULL can more easily be replaced with code\nthat is safe for NULL. For example,\n\n pos = snapshot->buf + snapshot->header_len\n\nbecomes\n\n pos = snapshot->start\n\n, and\n\n len = snapshot->eof - pos;\n if (!len) [...]\n\nbecomes\n\n if (pos == snapshot->eof) [...]\n len = snapshot->eof - pos;\n\n. In this way, most of the special-casing for NULL goes away (and some\ncode becomes simpler, as well).\n\nIn a moment I'll send a patch series illustrating this approach. I think\npatches 01, 02, and 04 are improvements regardless of whether we decide\nto make NULL safe.\n\nThe change to using `read()` rather than `mmap()` for small\n`packed-refs` feels like it should be an improvement, but it occurred to\nme that the performance numbers quoted in ea68b0ce9f8 (hash-object:\ndon't use mmap() for small files, 2010-02-21) are not directly\napplicable to the `packed-refs` file. As far as I understand, the file\nmmapped in `index_fd()` is always read in full, whereas the main point\nof mmapping the packed-refs file is to avoid having to read the whole\nfile at all in some situations. That being said, a 32 KiB file would\nonly be 8 pages (assuming a page size of 4 KiB), and by the time you've\nread the header and binary-searched to find the desired record, you've\nprobably paged in most of the file anyway. Reading the whole file at\nonce, in order, is almost certainly cheaper.\n\nMichael\n"},{"id":"337243","messageId":"cover.1516791909.git.mhagger@alum.mit.edu","threadId":"47606","inReplyTo":"cea5e366-dc95-6f41-6373-f8bbef103561@alum.mit.edu","subject":"[PATCH 0/6] Yet another approach to handling empty snapshots","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2018-01-24T11:14:10Z","receivedAt":"2018-01-24T11:14:28Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"This patch series fixes the handling of empty packed-refs snapshots\n(i.e., those with `snapshot->buf` and friends equal to `NULL`), partly\nby changing `snapshot` to store a pointer to the start of the\npost-header `packed-refs` content instead of `header_len`. It makes a\ncouple of other improvements as well.\n\nI'm not sure whether I like this approach better than the alternative\nof always setting `snapshot->buf` to a non-NULL value, by allocating a\nlength-1 bit of RAM if necessary. The latter is less intrusive, though\neven if that approach is taken, I think patches 01, 02, and 04 from\nthis patch series would be worthwhile improvements.\n\nMichael\n\nKim Gybels (1):\n packed_ref_cache: don't use mmap() for small files\n\nMichael Haggerty (5):\n struct snapshot: store `start` rather than `header_len`\n create_snapshot(): use `xmemdupz()` rather than a strbuf\n find_reference_location(): make function safe for empty snapshots\n packed_ref_iterator_begin(): make optimization more general\n load_contents(): don't try to mmap an empty file\n\n refs/packed-backend.c | 106 ++++++++++++++++++++++++++------------------------\n 1 file changed, 55 insertions(+), 51 deletions(-)\n\n-- \n2.14.2\n\n"},{"id":"337244","messageId":"2adb70b238a5f7f65f19344007e1743cc96644b8.1516791909.git.mhagger@alum.mit.edu","threadId":"47606","inReplyTo":"cea5e366-dc95-6f41-6373-f8bbef103561@alum.mit.edu","subject":"[PATCH 1/6] struct snapshot: store `start` rather than `header_len`","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2018-01-24T11:14:11Z","receivedAt":"2018-01-24T11:14:31Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Store a pointer to the start of the actual references within the\n`packed-refs` contents rather than storing the length of the header.\nThis is more convenient for most users of this field.\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 64 ++++++++++++++++++++++++++-------------------------\n 1 file changed, 33 insertions(+), 31 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 023243fd5f..b872267f02 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -68,17 +68,21 @@ struct snapshot {\n \tint mmapped;\n \n \t/*\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 * The contents of the `packed-refs` file:\n+\t *\n+\t * - buf -- a pointer to the start of the memory\n+\t * - start -- a pointer to the first byte of actual references\n+ * (i.e., after the header line, if one is present)\n+\t * - eof -- a pointer just past the end of the reference\n+ * contents\n+\t *\n+\t * If the `packed-refs` file was already sorted, `buf` points\n+\t * at the mmapped contents of the file. If not, it points at\n+\t * heap-allocated memory containing the contents, sorted. If\n+\t * there were no contents (e.g., because the file didn't\n+\t * exist), `buf`, `start`, and `eof` are all 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+\tchar *buf, *start, *eof;\n \n \t/*\n \t * What is the peeled state of the `packed-refs` file that\n@@ -169,8 +173,7 @@ static void clear_snapshot_buffer(struct snapshot *snapshot)\n \t} else {\n \t\tfree(snapshot->buf);\n \t}\n-\tsnapshot->buf = snapshot->eof = NULL;\n-\tsnapshot->header_len = 0;\n+\tsnapshot->buf = snapshot->start = snapshot->eof = NULL;\n }\n \n /*\n@@ -319,13 +322,14 @@ static void sort_snapshot(struct snapshot *snapshot)\n \tsize_t len, i;\n \tchar *new_buffer, *dst;\n \n-\tpos = snapshot->buf + snapshot->header_len;\n+\tpos = snapshot->start;\n \teof = snapshot->eof;\n-\tlen = eof - pos;\n \n-\tif (!len)\n+\tif (pos == eof)\n \t\treturn;\n \n+\tlen = eof - pos;\n+\n \t/*\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@@ -391,9 +395,8 @@ static void sort_snapshot(struct snapshot *snapshot)\n \t * place:\n \t */\n \tclear_snapshot_buffer(snapshot);\n-\tsnapshot->buf = new_buffer;\n+\tsnapshot->buf = snapshot->start = new_buffer;\n \tsnapshot->eof = new_buffer + len;\n-\tsnapshot->header_len = 0;\n \n cleanup:\n \tfree(records);\n@@ -442,14 +445,14 @@ static const char *find_end_of_record(const char *p, const char *end)\n */\n static void verify_buffer_safe(struct snapshot *snapshot)\n {\n-\tconst char *buf = snapshot->buf + snapshot->header_len;\n+\tconst char *start = snapshot->start;\n \tconst char *eof = snapshot->eof;\n \tconst char *last_line;\n \n-\tif (buf == eof)\n+\tif (start == eof)\n \t\treturn;\n \n-\tlast_line = find_start_of_record(buf, eof - 1);\n+\tlast_line = find_start_of_record(start, eof - 1);\n \tif (*(eof - 1) != '\\n' || eof - last_line < GIT_SHA1_HEXSZ + 2)\n \t\tdie_invalid_line(snapshot->refs->path,\n \t\t\t\t last_line, eof - last_line);\n@@ -495,18 +498,19 @@ static int load_contents(struct snapshot *snapshot)\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\", 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\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 \n+\tsnapshot->start = snapshot->buf;\n+\tsnapshot->eof = snapshot->buf + size;\n+\n \treturn 1;\n }\n \n@@ -539,7 +543,7 @@ static const char *find_reference_location(struct snapshot *snapshot,\n \t * preceding records all have reference names that come\n \t * *before* `refname`.\n \t */\n-\tconst char *lo = snapshot->buf + snapshot->header_len;\n+\tconst char *lo = snapshot->start;\n \n \t/*\n \t * A pointer to a the first character of a record whose\n@@ -617,8 +621,7 @@ static struct snapshot *create_snapshot(struct packed_ref_store *refs)\n \t/* If the file has a header line, process it: */\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\tchar *p, *eol;\n \t\tstruct string_list traits = STRING_LIST_INIT_NODUP;\n \n \t\teol = memchr(snapshot->buf, '\\n',\n@@ -647,7 +650,7 @@ static struct snapshot *create_snapshot(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\tsnapshot->header_len = eol + 1 - snapshot->buf;\n+\t\tsnapshot->start = eol + 1;\n \n \t\tstring_list_clear(&traits, 0);\n \t\tstrbuf_release(&tmp);\n@@ -671,13 +674,12 @@ static struct snapshot *create_snapshot(struct packed_ref_store *refs)\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 = snapshot->eof -\n-\t\t\t(snapshot->buf + snapshot->header_len);\n+\t\tsize_t size = snapshot->eof - snapshot->start;\n \t\tchar *buf_copy = xmalloc(size);\n \n-\t\tmemcpy(buf_copy, snapshot->buf + snapshot->header_len, size);\n+\t\tmemcpy(buf_copy, snapshot->start, size);\n \t\tclear_snapshot_buffer(snapshot);\n-\t\tsnapshot->buf = buf_copy;\n+\t\tsnapshot->buf = snapshot->start = buf_copy;\n \t\tsnapshot->eof = buf_copy + size;\n \t}\n \n@@ -937,7 +939,7 @@ static struct ref_iterator *packed_ref_iterator_begin(\n \tif (prefix && *prefix)\n \t\tstart = find_reference_location(snapshot, prefix, 0);\n \telse\n-\t\tstart = snapshot->buf + snapshot->header_len;\n+\t\tstart = snapshot->start;\n \n \titer->pos = start;\n \titer->eof = snapshot->eof;\n-- \n2.14.2\n\n"},{"id":"337245","messageId":"e9f9ed1944c297a68c2b76f5d4ddd73e279bd207.1516791909.git.mhagger@alum.mit.edu","threadId":"47606","inReplyTo":"cea5e366-dc95-6f41-6373-f8bbef103561@alum.mit.edu","subject":"[PATCH 3/6] find_reference_location(): make function safe for empty snapshots","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2018-01-24T11:14:13Z","receivedAt":"2018-01-24T11:14:36Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"This function had two problems if called for an empty snapshot (i.e.,\n`snapshot->start == snapshot->eof == NULL`):\n\n* It checked `NULL < NULL`, which is undefined by C (albeit highly\n unlikely to fail in the real world).\n\n* (Assuming the above comparison behaved as expected), it returned\n NULL when `mustexist` was false, contrary to its docstring.\n\nChange the check and fix the docstring.\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 10 ++++++----\n 1 file changed, 6 insertions(+), 4 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 08698de6ea..361affd7ad 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -519,9 +519,11 @@ static int load_contents(struct snapshot *snapshot)\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+ * inserted, or `snapshot->eof` (which might be NULL) if it would be\n+ * inserted at the end of the file. In the latter mode, `refname`\n+ * doesn't have to be a proper reference name; for example, one could\n+ * search for \"refs/replace/\" to find the start of any replace\n+ * references.\n *\n * The record is sought using a binary search, so `snapshot->buf` must\n * be sorted.\n@@ -551,7 +553,7 @@ static const char *find_reference_location(struct snapshot *snapshot,\n \t */\n \tconst char *hi = snapshot->eof;\n \n-\twhile (lo < hi) {\n+\twhile (lo != hi) {\n \t\tconst char *mid, *rec;\n \t\tint cmp;\n \n-- \n2.14.2\n\n"},{"id":"337246","messageId":"612a0b909d1f73bb706e9c44a6e1d737f3a2bf95.1516791909.git.mhagger@alum.mit.edu","threadId":"47606","inReplyTo":"cea5e366-dc95-6f41-6373-f8bbef103561@alum.mit.edu","subject":"[PATCH 2/6] create_snapshot(): use `xmemdupz()` rather than a strbuf","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2018-01-24T11:14:12Z","receivedAt":"2018-01-24T11:14:39Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"It's lighter weight.\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 9 ++++-----\n 1 file changed, 4 insertions(+), 5 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex b872267f02..08698de6ea 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -620,8 +620,7 @@ static struct snapshot *create_snapshot(struct packed_ref_store *refs)\n \n \t/* If the file has a header line, process it: */\n \tif (snapshot->buf < snapshot->eof && *snapshot->buf == '#') {\n-\t\tstruct strbuf tmp = STRBUF_INIT;\n-\t\tchar *p, *eol;\n+\t\tchar *tmp, *p, *eol;\n \t\tstruct string_list traits = STRING_LIST_INIT_NODUP;\n \n \t\teol = memchr(snapshot->buf, '\\n',\n@@ -631,9 +630,9 @@ static struct snapshot *create_snapshot(struct packed_ref_store *refs)\n \t\t\t\t\t snapshot->buf,\n \t\t\t\t\t snapshot->eof - snapshot->buf);\n \n-\t\tstrbuf_add(&tmp, snapshot->buf, eol - snapshot->buf);\n+\t\ttmp = xmemdupz(snapshot->buf, eol - snapshot->buf);\n \n-\t\tif (!skip_prefix(tmp.buf, \"# pack-refs with:\", (const char **)&p))\n+\t\tif (!skip_prefix(tmp, \"# pack-refs with:\", (const char **)&p))\n \t\t\tdie_invalid_line(refs->path,\n \t\t\t\t\t snapshot->buf,\n \t\t\t\t\t snapshot->eof - snapshot->buf);\n@@ -653,7 +652,7 @@ static struct snapshot *create_snapshot(struct packed_ref_store *refs)\n \t\tsnapshot->start = eol + 1;\n \n \t\tstring_list_clear(&traits, 0);\n-\t\tstrbuf_release(&tmp);\n+\t\tfree(tmp);\n \t}\n \n \tverify_buffer_safe(snapshot);\n-- \n2.14.2\n\n"},{"id":"337247","messageId":"f06611f06a8b01843bd71cd9fedec0f1eb0ee551.1516791909.git.mhagger@alum.mit.edu","threadId":"47606","inReplyTo":"cea5e366-dc95-6f41-6373-f8bbef103561@alum.mit.edu","subject":"[PATCH 5/6] load_contents(): don't try to mmap an empty file","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2018-01-24T11:14:15Z","receivedAt":"2018-01-24T11:14:42Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"We don't actually create zero-length `packed-refs` files, but they are\nvalid and we should handle them correctly. The old code `xmmap()`ed\nsuch files, which led to an error when `munmap()` was called. So, if\nthe `packed-refs` file is empty, leave the snapshot at its zero values\nand return 0 without trying to read or mmap the file.\n\nReturning 0 also makes `create_snapshot()` exit early, which avoids\nthe technically undefined comparison `NULL < NULL`.\n\nReported-by: Kim Gybels \nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 13 ++++++-------\n 1 file changed, 6 insertions(+), 7 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 988c45402b..e829cf206d 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -461,7 +461,8 @@ static void verify_buffer_safe(struct snapshot *snapshot)\n /*\n * Depending on `mmap_strategy`, either mmap or read the contents of\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+ * existed and was read, or 0 if the file was absent or empty. Die on\n+ * errors.\n */\n static int load_contents(struct snapshot *snapshot)\n {\n@@ -492,19 +493,17 @@ static int load_contents(struct snapshot *snapshot)\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+\tif (!size) {\n+\t\treturn 0;\n+\t} else if (mmap_strategy == MMAP_NONE) {\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\", snapshot->refs->path);\n \t\tsnapshot->mmapped = 0;\n-\t\tbreak;\n-\tcase MMAP_TEMPORARY:\n-\tcase MMAP_OK:\n+\t} else {\n \t\tsnapshot->buf = xmmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);\n \t\tsnapshot->mmapped = 1;\n-\t\tbreak;\n \t}\n \tclose(fd);\n \n-- \n2.14.2\n\n"},{"id":"337248","messageId":"bf6c0c67430b936738f5e8891b82022d0127acb0.1516791909.git.mhagger@alum.mit.edu","threadId":"47606","inReplyTo":"cea5e366-dc95-6f41-6373-f8bbef103561@alum.mit.edu","subject":"[PATCH 4/6] packed_ref_iterator_begin(): make optimization more general","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2018-01-24T11:14:14Z","receivedAt":"2018-01-24T11:14:45Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"We can return an empty iterator not only if the `packed-refs` file is\nmissing, but also if it is empty or if there are no references whose\nnames succeed `prefix`. Optimize away those cases as well by moving\nthe call to `find_reference_location()` higher in the function and\nchecking whether the determined start position is the same as\n`snapshot->eof`. (This is possible now because the previous commit\nmade `find_reference_location()` robust against empty snapshots.)\n\nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 12 ++++++------\n 1 file changed, 6 insertions(+), 6 deletions(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 361affd7ad..988c45402b 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -927,7 +927,12 @@ static struct ref_iterator *packed_ref_iterator_begin(\n \t */\n \tsnapshot = get_snapshot(refs);\n \n-\tif (!snapshot->buf)\n+\tif (prefix && *prefix)\n+\t\tstart = find_reference_location(snapshot, prefix, 0);\n+\telse\n+\t\tstart = snapshot->start;\n+\n+\tif (start == snapshot->eof)\n \t\treturn empty_ref_iterator_begin();\n \n \titer = xcalloc(1, sizeof(*iter));\n@@ -937,11 +942,6 @@ static struct ref_iterator *packed_ref_iterator_begin(\n \titer->snapshot = snapshot;\n \tacquire_snapshot(snapshot);\n \n-\tif (prefix && *prefix)\n-\t\tstart = find_reference_location(snapshot, prefix, 0);\n-\telse\n-\t\tstart = snapshot->start;\n-\n \titer->pos = start;\n \titer->eof = snapshot->eof;\n \tstrbuf_init(&iter->refname_buf, 0);\n-- \n2.14.2\n\n"},{"id":"337249","messageId":"411272c9a3fd159ceae4649ebdb9d121ba0ea742.1516791909.git.mhagger@alum.mit.edu","threadId":"47606","inReplyTo":"cea5e366-dc95-6f41-6373-f8bbef103561@alum.mit.edu","subject":"[PATCH 6/6] packed_ref_cache: don't use mmap() for small files","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2018-01-24T11:14:16Z","receivedAt":"2018-01-24T11:14:48Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Kim Gybels \n\nTake a hint from commit ea68b0ce9f8 (hash-object: don't use mmap() for\nsmall files, 2010-02-21) and use read() instead of mmap() for small\npacked-refs files.\n\nSigned-off-by: Kim Gybels \nSigned-off-by: Junio C Hamano \nSigned-off-by: Michael Haggerty \n---\n refs/packed-backend.c | 4 +++-\n 1 file changed, 3 insertions(+), 1 deletion(-)\n\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex e829cf206d..8b4b45da67 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -458,6 +458,8 @@ static void verify_buffer_safe(struct snapshot *snapshot)\n \t\t\t\t last_line, eof - last_line);\n }\n \n+#define SMALL_FILE_SIZE (32*1024)\n+\n /*\n * Depending on `mmap_strategy`, either mmap or read the contents of\n * the `packed-refs` file into the snapshot. Return 1 if the file\n@@ -495,7 +497,7 @@ static int load_contents(struct snapshot *snapshot)\n \n \tif (!size) {\n \t\treturn 0;\n-\t} else if (mmap_strategy == MMAP_NONE) {\n+\t} else if (mmap_strategy == MMAP_NONE || size <= SMALL_FILE_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-- \n2.14.2\n\n"},{"id":"337273","messageId":"xmqq607rf7y1.fsf@gitster.mtv.corp.google.com","threadId":"47606","inReplyTo":"cea5e366-dc95-6f41-6373-f8bbef103561@alum.mit.edu","subject":"Re: [PATCH v3] packed_ref_cache: don't use mmap() for small files","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-01-24T18:05:58Z","receivedAt":"2018-01-24T18:06:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty writes:\n\n> The change to using `read()` rather than `mmap()` for small\n> `packed-refs` feels like it should be an improvement, but it occurred to\n> me that the performance numbers quoted in ea68b0ce9f8 (hash-object:\n> don't use mmap() for small files, 2010-02-21) are not directly\n> applicable to the `packed-refs` file. As far as I understand, the file\n> mmapped in `index_fd()` is always read in full, whereas the main point\n> of mmapping the packed-refs file is to avoid having to read the whole\n> file at all in some situations. That being said, a 32 KiB file would\n> only be 8 pages (assuming a page size of 4 KiB), and by the time you've\n> read the header and binary-searched to find the desired record, you've\n> probably paged in most of the file anyway. Reading the whole file at\n> once, in order, is almost certainly cheaper.\n\nYup. So unless your \"small\" is meaningfully large, we are likely to\nbe better off with read(2), but I suspect that this might not be\neven measuable since we are only talking about \"small\" files.\n"},{"id":"337293","messageId":"20180124202754.GA7773@sigill.intra.peff.net","threadId":"47606","inReplyTo":"e9f9ed1944c297a68c2b76f5d4ddd73e279bd207.1516791909.git.mhagger@alum.mit.edu","subject":"Re: [PATCH 3/6] find_reference_location(): make function safe for empty snapshots","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-01-24T20:27:54Z","receivedAt":"2018-01-24T20:28:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jan 24, 2018 at 12:14:13PM +0100, Michael Haggerty wrote:\n\n> diff --git a/refs/packed-backend.c b/refs/packed-backend.c\n> index 08698de6ea..361affd7ad 100644\n> --- a/refs/packed-backend.c\n> +++ b/refs/packed-backend.c\n> [...]\n> @@ -551,7 +553,7 @@ static const char *find_reference_location(struct snapshot *snapshot,\n> \t */\n> \tconst char *hi = snapshot->eof;\n> \n> -\twhile (lo < hi) {\n> +\twhile (lo != hi) {\n> \t\tconst char *mid, *rec;\n> \t\tint cmp;\n\nThis tightens the binary search termination condition. If we ever did\nsee \"hi > lo\", we'd want to terminate the loop. Is that ever possible?\n\nI think the answer is \"no\". Our \"hi\" here is an exclusive bound, so we\nshould never go past it via find_end_of_record() when assigning \"lo\".\nAnd \"hi\" is always assigned from the start of the current record. That\ncan never cross \"lo\", because find_start_of_record() ensures it.\n\nSo I think it's fine, but I wanted to double check.\n\n-Peff\n"},{"id":"337294","messageId":"20180124203258.GB7773@sigill.intra.peff.net","threadId":"47606","inReplyTo":"bf6c0c67430b936738f5e8891b82022d0127acb0.1516791909.git.mhagger@alum.mit.edu","subject":"Re: [PATCH 4/6] packed_ref_iterator_begin(): make optimization more general","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-01-24T20:32:58Z","receivedAt":"2018-01-24T20:33:05Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jan 24, 2018 at 12:14:14PM +0100, Michael Haggerty wrote:\n\n> We can return an empty iterator not only if the `packed-refs` file is\n> missing, but also if it is empty or if there are no references whose\n> names succeed `prefix`. Optimize away those cases as well by moving\n> the call to `find_reference_location()` higher in the function and\n> checking whether the determined start position is the same as\n> `snapshot->eof`. (This is possible now because the previous commit\n> made `find_reference_location()` robust against empty snapshots.)\n\nMakes sense.\n\n> @@ -937,11 +942,6 @@ static struct ref_iterator *packed_ref_iterator_begin(\n> \titer->snapshot = snapshot;\n> \tacquire_snapshot(snapshot);\n> \n> -\tif (prefix && *prefix)\n> -\t\tstart = find_reference_location(snapshot, prefix, 0);\n> -\telse\n> -\t\tstart = snapshot->start;\n> -\n\nI did a double-take here that we are now looking at the snapshot without\ncalling acquire_snapshot(). But that function is just about taking a\nrefcount on it. The actual acquisition of data happens in\nget_snapshot().\n\n-Peff\n"},{"id":"337297","messageId":"20180124203645.GC7773@sigill.intra.peff.net","threadId":"47606","inReplyTo":"2adb70b238a5f7f65f19344007e1743cc96644b8.1516791909.git.mhagger@alum.mit.edu","subject":"Re: [PATCH 1/6] struct snapshot: store `start` rather than `header_len`","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-01-24T20:36:45Z","receivedAt":"2018-01-24T20:36:51Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jan 24, 2018 at 12:14:11PM +0100, Michael Haggerty wrote:\n\n> Store a pointer to the start of the actual references within the\n> `packed-refs` contents rather than storing the length of the header.\n> This is more convenient for most users of this field.\n\nThis makes sense. It means that the \"start\" pointer needs to be\ninvalidated if \"buf\" ever changes. But that was pretty much the case\nalready with \"header_len\" (because \"buf\" is not a heap buffer that we\nmight realloc; if it ever changes it is because we re-read the file, and\nwe would have to re-parse the header length anyway).\n\n-Peff\n"},{"id":"337298","messageId":"20180124203806.GD7773@sigill.intra.peff.net","threadId":"47606","inReplyTo":"cover.1516791909.git.mhagger@alum.mit.edu","subject":"Re: [PATCH 0/6] Yet another approach to handling empty snapshots","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-01-24T20:38:06Z","receivedAt":"2018-01-24T20:38:12Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jan 24, 2018 at 12:14:10PM +0100, Michael Haggerty wrote:\n\n> This patch series fixes the handling of empty packed-refs snapshots\n> (i.e., those with `snapshot->buf` and friends equal to `NULL`), partly\n> by changing `snapshot` to store a pointer to the start of the\n> post-header `packed-refs` content instead of `header_len`. It makes a\n> couple of other improvements as well.\n> \n> I'm not sure whether I like this approach better than the alternative\n> of always setting `snapshot->buf` to a non-NULL value, by allocating a\n> length-1 bit of RAM if necessary. The latter is less intrusive, though\n> even if that approach is taken, I think patches 01, 02, and 04 from\n> this patch series would be worthwhile improvements.\n\nThis looks good to me. I agree that 1, 2, and 4 are improvements\nregardless (but 4 as it is now depends on 3, right?).\n\nI don't have a strong opinion between this series and the other options\npresented. It's probably not worth agonizing over, so we should pick one\nand move on.\n\n-Peff\n"},{"id":"337305","messageId":"xmqqfu6vc70l.fsf@gitster.mtv.corp.google.com","threadId":"47606","inReplyTo":"cover.1516791909.git.mhagger@alum.mit.edu","subject":"Re: [PATCH 0/6] Yet another approach to handling empty snapshots","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-01-24T20:54:18Z","receivedAt":"2018-01-24T20:54:26Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty writes:\n\n> This patch series fixes the handling of empty packed-refs snapshots\n> (i.e., those with `snapshot->buf` and friends equal to `NULL`), partly\n> by changing `snapshot` to store a pointer to the start of the\n> post-header `packed-refs` content instead of `header_len`. It makes a\n> couple of other improvements as well.\n>\n> I'm not sure whether I like this approach better than the alternative\n> of always setting `snapshot->buf` to a non-NULL value, by allocating a\n> length-1 bit of RAM if necessary. The latter is less intrusive, though\n> even if that approach is taken, I think patches 01, 02, and 04 from\n> this patch series would be worthwhile improvements.\n\nI do not have a strong preference either way, but somehow feel that\nthis is more \"coherent\" ;-) That is certainly subjective, though.\n\nThanks.\n"},{"id":"337308","messageId":"xmqq8tcnc68r.fsf@gitster.mtv.corp.google.com","threadId":"47606","inReplyTo":"20180124202754.GA7773@sigill.intra.peff.net","subject":"Re: [PATCH 3/6] find_reference_location(): make function safe for empty snapshots","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-01-24T21:11:00Z","receivedAt":"2018-01-24T21:11:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Wed, Jan 24, 2018 at 12:14:13PM +0100, Michael Haggerty wrote:\n>\n>> diff --git a/refs/packed-backend.c b/refs/packed-backend.c\n>> index 08698de6ea..361affd7ad 100644\n>> --- a/refs/packed-backend.c\n>> +++ b/refs/packed-backend.c\n>> [...]\n>> @@ -551,7 +553,7 @@ static const char *find_reference_location(struct snapshot *snapshot,\n>> \t */\n>> \tconst char *hi = snapshot->eof;\n>> \n>> -\twhile (lo < hi) {\n>> +\twhile (lo != hi) {\n>> \t\tconst char *mid, *rec;\n>> \t\tint cmp;\n>\n> This tightens the binary search termination condition. If we ever did\n> see \"hi > lo\", we'd want to terminate the loop. Is that ever possible?\n\nI think you meant \"lo > hi\", but I shared the same \"Huh?\" moment.\n\nBecause \"While lo is strictly lower than hi\" is a so well\nestablished binary search pattern, even though we know that it is\nequivalent to \"While lo and hi is different\" due to your analysis\nbelow, the new code looks somewhat strange at the first glance.\n\n> I think the answer is \"no\". Our \"hi\" here is an exclusive bound, so we\n> should never go past it via find_end_of_record() when assigning \"lo\".\n> And \"hi\" is always assigned from the start of the current record. That\n> can never cross \"lo\", because find_start_of_record() ensures it.\n>\n> So I think it's fine, but I wanted to double check.\n\nIt would be much simpler to reason about if we instead do\n\n\t#define is_empty_snapshot(s) ((s)->start == NULL)\n\n\tif (is_empty_snapshot(snapshot))\n\t\treturn NULL;\n\nor something like that upfront.\n\t\n\n"},{"id":"337316","messageId":"20180124213410.GA8952@sigill.intra.peff.net","threadId":"47606","inReplyTo":"xmqq8tcnc68r.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 3/6] find_reference_location(): make function safe for empty snapshots","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-01-24T21:34:11Z","receivedAt":"2018-01-24T21:34:17Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jan 24, 2018 at 01:11:00PM -0800, Junio C Hamano wrote:\n\n> > This tightens the binary search termination condition. If we ever did\n> > see \"hi > lo\", we'd want to terminate the loop. Is that ever possible?\n> \n> I think you meant \"lo > hi\", but I shared the same \"Huh?\" moment.\n\nEr, yeah. Sorry about that.\n\n> Because \"While lo is strictly lower than hi\" is a so well\n> established binary search pattern, even though we know that it is\n> equivalent to \"While lo and hi is different\" due to your analysis\n> below, the new code looks somewhat strange at the first glance.\n\nI thought at first that this was due to the way the record-finding\nhappens, but I think even in our normal binary searches, it is an\ninvariant that \"lo <= hi\".\n\n> > I think the answer is \"no\". Our \"hi\" here is an exclusive bound, so we\n> > should never go past it via find_end_of_record() when assigning \"lo\".\n> > And \"hi\" is always assigned from the start of the current record. That\n> > can never cross \"lo\", because find_start_of_record() ensures it.\n> >\n> > So I think it's fine, but I wanted to double check.\n> \n> It would be much simpler to reason about if we instead do\n> \n> \t#define is_empty_snapshot(s) ((s)->start == NULL)\n> \n> \tif (is_empty_snapshot(snapshot))\n> \t\treturn NULL;\n> \n> or something like that upfront.\n\nYes, I agree that would also work.\n\n-Peff\n"},{"id":"339476","messageId":"nycvar.QRO.7.76.6.1802151753060.35@ZVAVAG-6OXH6DA.rhebcr.pbec.zvpebfbsg.pbz","threadId":"47606","inReplyTo":"cover.1516791909.git.mhagger@alum.mit.edu","subject":"Re: [PATCH 0/6] Yet another approach to handling empty snapshots","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2018-02-15T16:54:08Z","receivedAt":"2018-02-15T16:54:35Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Michael,\n\nOn Wed, 24 Jan 2018, Michael Haggerty wrote:\n\n> This patch series fixes the handling of empty packed-refs snapshots\n> (i.e., those with `snapshot->buf` and friends equal to `NULL`), partly\n> by changing `snapshot` to store a pointer to the start of the\n> post-header `packed-refs` content instead of `header_len`. It makes a\n> couple of other improvements as well.\n> \n> I'm not sure whether I like this approach better than the alternative\n> of always setting `snapshot->buf` to a non-NULL value, by allocating a\n> length-1 bit of RAM if necessary. The latter is less intrusive, though\n> even if that approach is taken, I think patches 01, 02, and 04 from\n> this patch series would be worthwhile improvements.\n\nThank you for Cc:ing me on this patch series. I tried to find some time to\nreview it, I really did, but failed. As I saw that others already had a\ngood look at it, I will just archive the mail thread.\n\nI hope you do not mind!\n\nCiao,\nDscho\n"}]}