{"thread":{"id":"50910","subject":"[PATCH 0/1] Fix an off-by-one bug in the untracked cache code","startedAt":"2019-04-10T12:56:51Z","lastAt":"2019-04-19T20:02:05Z","messageCount":13,"participants":["Johannes Schindelin via GitGitGadget","Jeff King","Junio C Hamano","Duy Nguyen"],"isPatch":true,"patchVersion":1,"patchTotal":1},"messages":[{"id":"373579","messageId":"pull.178.git.gitgitgadget@gmail.com","threadId":"50910","inReplyTo":null,"subject":"[PATCH 0/1] Fix an off-by-one bug in the untracked cache code","fromName":"Johannes Schindelin via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2019-04-10T12:56:47Z","receivedAt":"2019-04-10T12:56:51Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Frankly, I am surprised it took me this long to discover this bug, as I am\nrunning with the untracked cache for ages now.\n\nBut as of recent, I am running more and more long-running commands, mostly\nrebases to keep what I call \"ever-green\" branches up to date, where Git for\nWindows' patch thicket is rebased onto core Git's four integration branches,\nand when there are no merge conflicts to stop the rebase early, I got this\nreally obscure crash (no error message, no nothing to indicate what it was).\n\nIt cost me two full work days to chase this one down.\n\nJohannes Schindelin (1):\n untracked cache: fix off-by-one\n\n dir.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\n\nbase-commit: e35b8cb8e212e3557efc565157ceb5cbaaf0d87f\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-178%2Fdscho%2Funtracked-cache-off-by-one-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-178/dscho/untracked-cache-off-by-one-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/178\n-- \ngitgitgadget\n"},{"id":"373580","messageId":"a7f75cefb682546862be4dd8b48f91c4034c5d5a.1554901006.git.gitgitgadget@gmail.com","threadId":"50910","inReplyTo":"pull.178.git.gitgitgadget@gmail.com","subject":"[PATCH 1/1] untracked cache: fix off-by-one","fromName":"Johannes Schindelin via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2019-04-10T12:56:48Z","receivedAt":"2019-04-10T12:56:52Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"From: Johannes Schindelin \n\nIn f9e6c649589e (untracked cache: load from UNTR index extension,\n2015-03-08), code was added to read back the untracked cache from an\nindex extension.\n\nProbably in the endeavor to avoid the `calloc()` implied by\n`FLEX_ALLOC_STR()` (it is hard to know why exactly, the commit message\nof that commit is a bit parsimonious with information), it calls\n`malloc()` manually and then `memcpy()`s the bits and pieces into place.\n\nIt allocates the size of `struct untracked_cache_dir` plus the string\nlength of the untracked file name, then copies the information in two\nsteps: first the fixed-size metadata, then the name. And here lies the\nrub: it includes the trailing NUL byte in the name.\n\nIf `FLEX_ARRAY` is defined as 0, this results in a buffer overrun.\n\nTo fix this, let's just add 1, for the trailing NUL byte. Technically,\nthis overallocates on platforms where `FLEX_ARRAY` is 1, but it should\nnot matter much in reality, as `malloc()` usually overallocates anyway,\nunless the size to allocate aligns exactly with some internal chunk size\n(see below for more on that).\n\nThe real strange thing is that neither valgrind nor DrMemory catches\nthis bug. In this developer's tests, a `memcpy()` (but not a\n`memset()`!) could write up to 4 bytes after the allocated memory range\nbefore valgrind would start reporting an issue.\n\nHowever, when running Git built with nedmalloc as allocator, under rare\nconditions (and inconsistently at that), this bug triggered an `abort()`\nbecause nedmalloc rounds up the size to be `malloc()`ed to a multiple of\na certain chunk size, then adds a few bytes to be used for storing some\ninternal state. If there is no rounding up to do (because the size is\nalready a multiple of that chunk size), and if the buffer is overrun as\nin the code patched in this commit, the internal state is corrupted.\n\nThe scenario that triggered this here bug fix entailed a git.git\ncheckout with an extra copy of the source code in an untracked\nsubdirectory, meaning that there was an untracked subdirectory called\n\"thunderbird-patch-inline\" whose name's length is exactly 24 bytes,\nwhich, added to the size of above-mentioned `struct untracked_cache_dir`\nthat weighs in with 104 bytes on a 64-bit system, amounts to 128,\naligning perfectly with nedmalloc's chunk size.\n\nAs there is no obvious way to trigger this bug reliably, on all\nplatforms supported by Git, and as the bug is obvious enough, this patch\ncomes without a regression test.\n\nSigned-off-by: Johannes Schindelin \n---\n dir.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/dir.c b/dir.c\nindex b2cabadf25..f5293a6536 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -2760,7 +2760,7 @@ static int read_one_dir(struct untracked_cache_dir **untracked_,\n \tnext = data + len + 1;\n \tif (next > rd->end)\n \t\treturn -1;\n-\t*untracked_ = untracked = xmalloc(st_add(sizeof(*untracked), len));\n+\t*untracked_ = untracked = xmalloc(st_add3(sizeof(*untracked), len, 1));\n \tmemcpy(untracked, &ud, sizeof(ud));\n \tmemcpy(untracked->name, data, len + 1);\n \tdata = next;\n-- \ngitgitgadget\n"},{"id":"373585","messageId":"20190410162029.GA30818@sigill.intra.peff.net","threadId":"50910","inReplyTo":"a7f75cefb682546862be4dd8b48f91c4034c5d5a.1554901006.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/1] untracked cache: fix off-by-one","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-04-10T16:20:29Z","receivedAt":"2019-04-10T16:20:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Apr 10, 2019 at 05:56:48AM -0700, Johannes Schindelin via GitGitGadget wrote:\n\n> Probably in the endeavor to avoid the `calloc()` implied by\n> `FLEX_ALLOC_STR()` (it is hard to know why exactly, the commit message\n> of that commit is a bit parsimonious with information), it calls\n> `malloc()` manually and then `memcpy()`s the bits and pieces into place.\n\nYou have a talent for understatement. :)\n\n> It allocates the size of `struct untracked_cache_dir` plus the string\n> length of the untracked file name, then copies the information in two\n> steps: first the fixed-size metadata, then the name. And here lies the\n> rub: it includes the trailing NUL byte in the name.\n> \n> If `FLEX_ARRAY` is defined as 0, this results in a buffer overrun.\n> \n> To fix this, let's just add 1, for the trailing NUL byte. Technically,\n> this overallocates on platforms where `FLEX_ARRAY` is 1, but it should\n> not matter much in reality, as `malloc()` usually overallocates anyway,\n> unless the size to allocate aligns exactly with some internal chunk size\n> (see below for more on that).\n\nYeah, every struct on a platform where FLEX_ARRAY is 1 ends up\nover-allocated by 1 byte. We could account for that in all of our flex\nallocations, but I don't it affects enough platforms to be worth the\nbother.\n\n> The real strange thing is that neither valgrind nor DrMemory catches\n> this bug. In this developer's tests, a `memcpy()` (but not a\n> `memset()`!) could write up to 4 bytes after the allocated memory range\n> before valgrind would start reporting an issue.\n\nI couldn't get it to trigger with ASan, either. I assume it's due to\nalignment (i.e., those tools are stuck poisoning at the end of a page,\nbut the start of the struct needs to be page-aligned). But that would\nimply that we could trigger it with different path lengths, which I\nwasn't able to do. So I dunno.\n\n> However, when running Git built with nedmalloc as allocator, under rare\n> conditions (and inconsistently at that), this bug triggered an `abort()`\n> because nedmalloc rounds up the size to be `malloc()`ed to a multiple of\n> a certain chunk size, then adds a few bytes to be used for storing some\n> internal state. If there is no rounding up to do (because the size is\n> already a multiple of that chunk size), and if the buffer is overrun as\n> in the code patched in this commit, the internal state is corrupted.\n>\n> The scenario that triggered this here bug fix entailed a git.git\n> checkout with an extra copy of the source code in an untracked\n> subdirectory, meaning that there was an untracked subdirectory called\n> \"thunderbird-patch-inline\" whose name's length is exactly 24 bytes,\n> which, added to the size of above-mentioned `struct untracked_cache_dir`\n> that weighs in with 104 bytes on a 64-bit system, amounts to 128,\n> aligning perfectly with nedmalloc's chunk size.\n\nRight, that makes sense that the length would impact it there.\n\n> As there is no obvious way to trigger this bug reliably, on all\n> platforms supported by Git, and as the bug is obvious enough, this patch\n> comes without a regression test.\n\nMakes sense. This code path should be well-covered by the existing tests\nanyway, so even if we could get those tools to trigger, I don't think\nthere would be much point in adding a new test.\n\n> diff --git a/dir.c b/dir.c\n> index b2cabadf25..f5293a6536 100644\n> --- a/dir.c\n> +++ b/dir.c\n> @@ -2760,7 +2760,7 @@ static int read_one_dir(struct untracked_cache_dir **untracked_,\n> \tnext = data + len + 1;\n> \tif (next > rd->end)\n> \t\treturn -1;\n> -\t*untracked_ = untracked = xmalloc(st_add(sizeof(*untracked), len));\n> +\t*untracked_ = untracked = xmalloc(st_add3(sizeof(*untracked), len, 1));\n> \tmemcpy(untracked, &ud, sizeof(ud));\n> \tmemcpy(untracked->name, data, len + 1);\n\nThis is obviously correct, even just from the context.\n\nIMHO it is worth it in cases like this to just use FLEX_ALLOC for\nsimplicity; calloc() is not too expensive. However, there's an\ninteresting subtlety there. Our length comes from this line just above\nyour hunk:\n\n len = strlen((const char *)data);\n\nhow do we know that data actually contains a NUL? It's ultimately\npointing to our mmap of the index file. So I think a malformed index\nwould potentially cause us to go off the end of the array and read\narbitrary memory.\n\nThe right thing is probably something like:\n\n eos = memchr(data, '\\0', end - data);\n if (!eos)\n\treturn error(\"malformed untracked cache extension\");\n len = eos - data;\n\nI wouldn't be at all surprised if other bits of the index code have the\nsame issue, though. And at any rate, thinking about that should\ndefinitely not hold up your fix.\n\n-Peff\n"},{"id":"373700","messageId":"xmqq7ec00z9t.fsf@gitster-ct.c.googlers.com","threadId":"50910","inReplyTo":"20190410162029.GA30818@sigill.intra.peff.net","subject":"Re: [PATCH 1/1] untracked cache: fix off-by-one","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-04-12T01:48:30Z","receivedAt":"2019-04-12T01:48:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Yeah, every struct on a platform where FLEX_ARRAY is 1 ends up\n> over-allocated by 1 byte. We could account for that in all of our flex\n> allocations, but I don't it affects enough platforms to be worth the\n> bother.\n\nIt was an explicit design decision to declare that the\noverallocation was a non-problem back when we invented FLEX_ARRAY\nmacro. We could probably have instead decided to pass number of\nbytes to be stored in the flex-array (including NUL if that is a\ncharacter array) then subtract the value of FLEX_ARRAY if FLEX_ARRAY\nwere limited to only 0 or 1, but that was not workable as it is the\nmost natural to define FLEX_ARRAY to an empty string, i.e. making an\narray field decl to \"type field[];\", for the more recent compilers.\n\n\n>> As there is no obvious way to trigger this bug reliably, on all\n>> platforms supported by Git, and as the bug is obvious enough, this patch\n>> comes without a regression test.\n>\n> Makes sense. This code path should be well-covered by the existing tests\n> anyway, so even if we could get those tools to trigger, I don't think\n> there would be much point in adding a new test.\n\nYeah, it is already super that this obscure bug was spotted in the\nfirst place. It is true that this may regress without a test, but I\ndo not think it is reasonable to expect that it is possible to write\na reliable crash-detecting test for this one.\n\n> The right thing is probably something like:\n>\n> eos = memchr(data, '\\0', end - data);\n> if (!eos)\n> \treturn error(\"malformed untracked cache extension\");\n> len = eos - data;\n>\n> I wouldn't be at all surprised if other bits of the index code have the\n> same issue, though. And at any rate, thinking about that should\n> definitely not hold up your fix.\n\nTrue, true. I wonder if folks intereseted in libFuzzer can chime in\nwith something useful here, but that is totally independent.\n\n"},{"id":"374135","messageId":"20190418211408.GA18011@sigill.intra.peff.net","threadId":"50910","inReplyTo":"xmqq7ec00z9t.fsf@gitster-ct.c.googlers.com","subject":"[PATCH 0/3] untracked cache parsing fixups","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-04-18T21:14:08Z","receivedAt":"2019-04-18T21:14:11Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"[+cc Duy as the master of all things untracked-cache]\n\nOn Fri, Apr 12, 2019 at 10:48:30AM +0900, Junio C Hamano wrote:\n\n> > The right thing is probably something like:\n> >\n> > eos = memchr(data, '\\0', end - data);\n> > if (!eos)\n> > \treturn error(\"malformed untracked cache extension\");\n> > len = eos - data;\n> >\n> > I wouldn't be at all surprised if other bits of the index code have the\n> > same issue, though. And at any rate, thinking about that should\n> > definitely not hold up your fix.\n> \n> True, true. I wonder if folks intereseted in libFuzzer can chime in\n> with something useful here, but that is totally independent.\n\nJust so we don't forget about it, I wrote this fix up as a patch. And in\nfact it led to a few other cleanups. I think the first one is definitely\nworth doing now, even if there are other similar cases lurking in the\nrest of the index code.\n\nThe other two are optional, though I think they are worth it (and not\ntoo hard to verify that they are doing the right thing).\n\nThese are on top of js/untracked-cache-allocfix (though they could\neasily be ported to a separate topic if we want).\n\n [1/3]: untracked-cache: be defensive about missing NULs in index\n [2/3]: untracked-cache: simplify parsing by dropping \"next\"\n [3/3]: untracked-cache: simplify parsing by dropping \"len\"\n\n dir.c | 41 ++++++++++++++++++-----------------------\n 1 file changed, 18 insertions(+), 23 deletions(-)\n\n-Peff\n"},{"id":"374136","messageId":"20190418211701.GA18520@sigill.intra.peff.net","threadId":"50910","inReplyTo":"20190418211408.GA18011@sigill.intra.peff.net","subject":"[PATCH 1/3] untracked-cache: be defensive about missing NULs in index","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-04-18T21:17:02Z","receivedAt":"2019-04-18T21:17:05Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The on-disk format for the untracked-cache extension contains\nNUL-terminated filenames. We parse these from the mmap'd file using\nstring functions like strlen(). This works fine in the normal case, but\nif we see a malformed or corrupted index, we might read off the end of\nour mmap.\n\nInstead, let's use memchr() to find the trailing NUL within the bytes we\nknow are available, and return an error if it's missing.\n\nNote that we can further simplify by folding another range check into\nour conditional. After we find the end of the string, we set \"next\" to\nthe byte after the string and treat it as an error if there are no such\nbytes left. That saves us from having to do a range check at the\nbeginning of each subsequent string (and works because there is always\ndata after each string). We can do both range checks together by\nchecking \"!eos\" (we didn't find a NUL) and \"eos == end\" (it was on the\nlast available byte, meaning there's nothing after). This replaces the\nexisting \"next > end\" checks.\n\nNote also that the decode_varint() calls have a similar problem (we\ndon't even pass them \"end\"; they just keep parsing). These are probably\nOK in practice since varints have a finite length (we stop parsing when\nwe'd overflow a uintmax_t), so the worst case is that we'd overflow into\nreading the trailing bytes of the index.\n\nSigned-off-by: Jeff King \n---\n dir.c | 18 +++++++++++-------\n 1 file changed, 11 insertions(+), 7 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex f5293a6536..7b0513c476 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -2733,6 +2733,7 @@ static int read_one_dir(struct untracked_cache_dir **untracked_,\n {\n \tstruct untracked_cache_dir ud, *untracked;\n \tconst unsigned char *next, *data = rd->data, *end = rd->end;\n+\tconst unsigned char *eos;\n \tunsigned int value;\n \tint i, len;\n \n@@ -2756,21 +2757,24 @@ static int read_one_dir(struct untracked_cache_dir **untracked_,\n \tALLOC_ARRAY(ud.dirs, ud.dirs_nr);\n \tdata = next;\n \n-\tlen = strlen((const char *)data);\n-\tnext = data + len + 1;\n-\tif (next > rd->end)\n+\teos = memchr(data, '\\0', end - data);\n+\tif (!eos || eos == end)\n \t\treturn -1;\n+\tlen = eos - data;\n+\tnext = eos + 1;\n+\n \t*untracked_ = untracked = xmalloc(st_add3(sizeof(*untracked), len, 1));\n \tmemcpy(untracked, &ud, sizeof(ud));\n \tmemcpy(untracked->name, data, len + 1);\n \tdata = next;\n \n \tfor (i = 0; i < untracked->untracked_nr; i++) {\n-\t\tlen = strlen((const char *)data);\n-\t\tnext = data + len + 1;\n-\t\tif (next > rd->end)\n+\t\teos = memchr(data, '\\0', end - data);\n+\t\tif (!eos || eos == end)\n \t\t\treturn -1;\n-\t\tuntracked->untracked[i] = xstrdup((const char*)data);\n+\t\tlen = eos - data;\n+\t\tnext = eos + 1;\n+\t\tuntracked->untracked[i] = xmemdupz(data, len);\n \t\tdata = next;\n \t}\n \n-- \n2.21.0.1092.g8b0302e9c4\n\n"},{"id":"374137","messageId":"20190418211738.GB18520@sigill.intra.peff.net","threadId":"50910","inReplyTo":"20190418211408.GA18011@sigill.intra.peff.net","subject":"[PATCH 2/3] untracked-cache: simplify parsing by dropping \"next\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-04-18T21:17:38Z","receivedAt":"2019-04-18T21:17:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When we parse an on-disk untracked cache, we have two pointers, \"data\"\nand \"next\". As we parse, we point \"next\" to the end of an element, and\nthen later update \"data\" to match.\n\nBut we actually don't need two pointers. Each parsing step can just\nupdate \"data\" directly from other variables we hold (and we don't have\nto worry about bailing in an intermediate state, since any parsing\nfailure causes us to immediately discard \"data\" and return).\n\nSigned-off-by: Jeff King \n---\n dir.c | 20 +++++++-------------\n 1 file changed, 7 insertions(+), 13 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 7b0513c476..17865f44df 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -2732,50 +2732,44 @@ static int read_one_dir(struct untracked_cache_dir **untracked_,\n \t\t\tstruct read_data *rd)\n {\n \tstruct untracked_cache_dir ud, *untracked;\n-\tconst unsigned char *next, *data = rd->data, *end = rd->end;\n+\tconst unsigned char *data = rd->data, *end = rd->end;\n \tconst unsigned char *eos;\n \tunsigned int value;\n \tint i, len;\n \n \tmemset(&ud, 0, sizeof(ud));\n \n-\tnext = data;\n-\tvalue = decode_varint(&next);\n-\tif (next > end)\n+\tvalue = decode_varint(&data);\n+\tif (data > end)\n \t\treturn -1;\n \tud.recurse\t = 1;\n \tud.untracked_alloc = value;\n \tud.untracked_nr\t = value;\n \tif (ud.untracked_nr)\n \t\tALLOC_ARRAY(ud.untracked, ud.untracked_nr);\n-\tdata = next;\n \n-\tnext = data;\n-\tud.dirs_alloc = ud.dirs_nr = decode_varint(&next);\n-\tif (next > end)\n+\tud.dirs_alloc = ud.dirs_nr = decode_varint(&data);\n+\tif (data > end)\n \t\treturn -1;\n \tALLOC_ARRAY(ud.dirs, ud.dirs_nr);\n-\tdata = next;\n \n \teos = memchr(data, '\\0', end - data);\n \tif (!eos || eos == end)\n \t\treturn -1;\n \tlen = eos - data;\n-\tnext = eos + 1;\n \n \t*untracked_ = untracked = xmalloc(st_add3(sizeof(*untracked), len, 1));\n \tmemcpy(untracked, &ud, sizeof(ud));\n \tmemcpy(untracked->name, data, len + 1);\n-\tdata = next;\n+\tdata = eos + 1;\n \n \tfor (i = 0; i < untracked->untracked_nr; i++) {\n \t\teos = memchr(data, '\\0', end - data);\n \t\tif (!eos || eos == end)\n \t\t\treturn -1;\n \t\tlen = eos - data;\n-\t\tnext = eos + 1;\n \t\tuntracked->untracked[i] = xmemdupz(data, len);\n-\t\tdata = next;\n+\t\tdata = eos + 1;\n \t}\n \n \trd->ucd[rd->index++] = untracked;\n-- \n2.21.0.1092.g8b0302e9c4\n\n"},{"id":"374138","messageId":"20190418211835.GC18520@sigill.intra.peff.net","threadId":"50910","inReplyTo":"20190418211408.GA18011@sigill.intra.peff.net","subject":"[PATCH 3/3] untracked-cache: simplify parsing by dropping \"len\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-04-18T21:18:35Z","receivedAt":"2019-04-18T21:18:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The code which parses untracked-cache extensions from disk keeps a \"len\"\nvariable, which is the size of the string we are parsing. But since we\nnow have an \"end of string\" variable, we can just use that to get the\nlength when we need it. This eliminates the need to keep \"len\" up to\ndate (and removes the possibility of any errors where \"len\" and \"eos\"\nget out of sync).\n\nAs a bonus, it means we are not storing a string length in an \"int\",\nwhich is a potential source of overflows (though in this case it seems\nfairly unlikely for that to cause any memory problems).\n\nSigned-off-by: Jeff King \n---\n dir.c | 13 +++++--------\n 1 file changed, 5 insertions(+), 8 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 17865f44df..60438b2cdc 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -2735,7 +2735,7 @@ static int read_one_dir(struct untracked_cache_dir **untracked_,\n \tconst unsigned char *data = rd->data, *end = rd->end;\n \tconst unsigned char *eos;\n \tunsigned int value;\n-\tint i, len;\n+\tint i;\n \n \tmemset(&ud, 0, sizeof(ud));\n \n@@ -2756,28 +2756,25 @@ static int read_one_dir(struct untracked_cache_dir **untracked_,\n \teos = memchr(data, '\\0', end - data);\n \tif (!eos || eos == end)\n \t\treturn -1;\n-\tlen = eos - data;\n \n-\t*untracked_ = untracked = xmalloc(st_add3(sizeof(*untracked), len, 1));\n+\t*untracked_ = untracked = xmalloc(st_add3(sizeof(*untracked), eos - data, 1));\n \tmemcpy(untracked, &ud, sizeof(ud));\n-\tmemcpy(untracked->name, data, len + 1);\n+\tmemcpy(untracked->name, data, eos - data + 1);\n \tdata = eos + 1;\n \n \tfor (i = 0; i < untracked->untracked_nr; i++) {\n \t\teos = memchr(data, '\\0', end - data);\n \t\tif (!eos || eos == end)\n \t\t\treturn -1;\n-\t\tlen = eos - data;\n-\t\tuntracked->untracked[i] = xmemdupz(data, len);\n+\t\tuntracked->untracked[i] = xmemdupz(data, eos - data);\n \t\tdata = eos + 1;\n \t}\n \n \trd->ucd[rd->index++] = untracked;\n \trd->data = data;\n \n \tfor (i = 0; i < untracked->dirs_nr; i++) {\n-\t\tlen = read_one_dir(untracked->dirs + i, rd);\n-\t\tif (len < 0)\n+\t\tif (read_one_dir(untracked->dirs + i, rd) < 0)\n \t\t\treturn -1;\n \t}\n \treturn 0;\n-- \n2.21.0.1092.g8b0302e9c4\n"},{"id":"374139","messageId":"20190418212405.GA18623@sigill.intra.peff.net","threadId":"50910","inReplyTo":"20190418211408.GA18011@sigill.intra.peff.net","subject":"[PATCH 4/3] untracked-cache: use FLEX_ALLOC to create internal structs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-04-18T21:24:05Z","receivedAt":"2019-04-18T21:24:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Apr 18, 2019 at 05:14:08PM -0400, Jeff King wrote:\n\n> Just so we don't forget about it, I wrote this fix up as a patch. And in\n> fact it led to a few other cleanups. I think the first one is definitely\n> worth doing now, even if there are other similar cases lurking in the\n> rest of the index code.\n> \n> The other two are optional, though I think they are worth it (and not\n> too hard to verify that they are doing the right thing).\n> \n> These are on top of js/untracked-cache-allocfix (though they could\n> easily be ported to a separate topic if we want).\n> \n> [1/3]: untracked-cache: be defensive about missing NULs in index\n> [2/3]: untracked-cache: simplify parsing by dropping \"next\"\n> [3/3]: untracked-cache: simplify parsing by dropping \"len\"\n\nI also wondered if we could just accept the cost of calloc() here and\nuse FLEX_ALLOC to simplify things. That resulted in the patch below, but\nI didn't include it with the initial 3, because I think it's too\nsubtle/gross for my tastes.\n\n-- >8 --\nSubject: untracked-cache: use FLEX_ALLOC to create internal structs\n\nThe untracked_cache_dir struct has a FLEX_ARRAY in it. Let's use\nFLEX_ALLOC_MEM to allocate it, which saves us having to compute the\nlength ourselves.\n\nIn theory this could be slightly slower, since the FLEX_ALLOC macros use\ncalloc (and we just memcpy over most of the contents anyway). But in\npractice this distinction is not generally measurable.\n\nNote that because we then fill in the pre-flex elements of the struct\nusing a memcpy, we need to take care to use the exact size of that\nspace and _not_ \"sizeof(ud)\", since the latter may include padding (or\neven an extra byte on systems where FLEX_ARRAY is 1).\n\nSigned-off-by: Jeff King \n---\nIf we wanted to go this route, I think it would make sense to provide a\nFLEX_ALLOC macro that takes a \"template\" set of bytes as a ptr/len pair,\nand writes it before we fill in the flex portion.\n\nThen we could do something like:\n\n FLEX_ALLOC_COPY(untracked, &ud, sizeof(ud), name, data, eos - data);\n\nIf this is the only such case, it's probably not worth it (I didn't\nreally look around for more, though).\n\n dir.c | 6 +++---\n 1 file changed, 3 insertions(+), 3 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 60438b2cdc..7cd4eec198 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -2757,9 +2757,9 @@ static int read_one_dir(struct untracked_cache_dir **untracked_,\n \tif (!eos || eos == end)\n \t\treturn -1;\n \n-\t*untracked_ = untracked = xmalloc(st_add3(sizeof(*untracked), eos - data, 1));\n-\tmemcpy(untracked, &ud, sizeof(ud));\n-\tmemcpy(untracked->name, data, eos - data + 1);\n+\tFLEX_ALLOC_MEM(untracked, name, data, eos - data);\n+\tmemcpy(untracked, &ud, offsetof(struct untracked_cache_dir, name));\n+\t*untracked_ = untracked;\n \tdata = eos + 1;\n \n \tfor (i = 0; i < untracked->untracked_nr; i++) {\n-- \n2.21.0.1092.g8b0302e9c4\n\n"},{"id":"374144","messageId":"CACsJy8BHwM5dUqa-FOjr3smxJT6kW4z7vLUJvsHuhjxwUjvkBw@mail.gmail.com","threadId":"50910","inReplyTo":"20190418212405.GA18623@sigill.intra.peff.net","subject":"Re: [PATCH 4/3] untracked-cache: use FLEX_ALLOC to create internal structs","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2019-04-19T09:18:25Z","receivedAt":"2019-04-19T18:27:27Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Apr 19, 2019 at 4:24 AM Jeff King wrote:\n>\n> On Thu, Apr 18, 2019 at 05:14:08PM -0400, Jeff King wrote:\n>\n> > Just so we don't forget about it, I wrote this fix up as a patch. And in\n> > fact it led to a few other cleanups. I think the first one is definitely\n> > worth doing now, even if there are other similar cases lurking in the\n> > rest of the index code.\n> >\n> > The other two are optional, though I think they are worth it (and not\n> > too hard to verify that they are doing the right thing).\n> >\n> > These are on top of js/untracked-cache-allocfix (though they could\n> > easily be ported to a separate topic if we want).\n> >\n> > [1/3]: untracked-cache: be defensive about missing NULs in index\n> > [2/3]: untracked-cache: simplify parsing by dropping \"next\"\n> > [3/3]: untracked-cache: simplify parsing by dropping \"len\"\n>\n> I also wondered if we could just accept the cost of calloc() here and\n> use FLEX_ALLOC to simplify things. That resulted in the patch below, but\n> I didn't include it with the initial 3, because I think it's too\n> subtle/gross for my tastes.\n\nIt's probably ok. If I remember correctly, reading UNTR extension (on\na huge repo) took the longest time after Ben added support for reading\nthe index with multiple threads. So performance is a concern, but I\ndon't think calloc() would be the problem. malloc() itself without the\nmemory pool could probably slow down more when we have lots and lots\nof directories.\n\n> -- >8 --\n> Subject: untracked-cache: use FLEX_ALLOC to create internal structs\n>\n> The untracked_cache_dir struct has a FLEX_ARRAY in it. Let's use\n> FLEX_ALLOC_MEM to allocate it, which saves us having to compute the\n> length ourselves.\n>\n> In theory this could be slightly slower, since the FLEX_ALLOC macros use\n> calloc (and we just memcpy over most of the contents anyway). But in\n> practice this distinction is not generally measurable.\n>\n> Note that because we then fill in the pre-flex elements of the struct\n> using a memcpy, we need to take care to use the exact size of that\n> space and _not_ \"sizeof(ud)\", since the latter may include padding (or\n> even an extra byte on systems where FLEX_ARRAY is 1).\n>\n> Signed-off-by: Jeff King \n> ---\n> If we wanted to go this route, I think it would make sense to provide a\n> FLEX_ALLOC macro that takes a \"template\" set of bytes as a ptr/len pair,\n> and writes it before we fill in the flex portion.\n>\n> Then we could do something like:\n>\n> FLEX_ALLOC_COPY(untracked, &ud, sizeof(ud), name, data, eos - data);\n>\n> If this is the only such case, it's probably not worth it (I didn't\n> really look around for more, though).\n>\n> dir.c | 6 +++---\n> 1 file changed, 3 insertions(+), 3 deletions(-)\n>\n> diff --git a/dir.c b/dir.c\n> index 60438b2cdc..7cd4eec198 100644\n> --- a/dir.c\n> +++ b/dir.c\n> @@ -2757,9 +2757,9 @@ static int read_one_dir(struct untracked_cache_dir **untracked_,\n> if (!eos || eos == end)\n> return -1;\n>\n> - *untracked_ = untracked = xmalloc(st_add3(sizeof(*untracked), eos - data, 1));\n> - memcpy(untracked, &ud, sizeof(ud));\n> - memcpy(untracked->name, data, eos - data + 1);\n> + FLEX_ALLOC_MEM(untracked, name, data, eos - data);\n> + memcpy(untracked, &ud, offsetof(struct untracked_cache_dir, name));\n> + *untracked_ = untracked;\n> data = eos + 1;\n>\n> for (i = 0; i < untracked->untracked_nr; i++) {\n> --\n> 2.21.0.1092.g8b0302e9c4\n>\n\n\n-- \nDuy\n"},{"id":"374145","messageId":"xmqq5zraeezm.fsf@gitster-ct.c.googlers.com","threadId":"50910","inReplyTo":"20190418211738.GB18520@sigill.intra.peff.net","subject":"Re: [PATCH 2/3] untracked-cache: simplify parsing by dropping \"next\"","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-04-19T05:33:17Z","receivedAt":"2019-04-19T18:37:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> When we parse an on-disk untracked cache, we have two pointers, \"data\"\n> and \"next\". As we parse, we point \"next\" to the end of an element, and\n> then later update \"data\" to match.\n>\n> But we actually don't need two pointers. Each parsing step can just\n> update \"data\" directly from other variables we hold (and we don't have\n> to worry about bailing in an intermediate state, since any parsing\n> failure causes us to immediately discard \"data\" and return).\n\n;-) \n\nMy first reaction was \"you can do so now you have introduced\neos--why didn't you do that in the previous step?\", but losing\n'next' from the varint parsing step would certainly have been\npossible even before that change. So I agree that it makes much\nmore sense to do this step separately from the previous one.\n\nThe code after the patch certainly reads easier and simpler.\n\nThanks.\n\n> Signed-off-by: Jeff King \n> ---\n> dir.c | 20 +++++++-------------\n> 1 file changed, 7 insertions(+), 13 deletions(-)\n>\n> diff --git a/dir.c b/dir.c\n> index 7b0513c476..17865f44df 100644\n> --- a/dir.c\n> +++ b/dir.c\n> @@ -2732,50 +2732,44 @@ static int read_one_dir(struct untracked_cache_dir **untracked_,\n> \t\t\tstruct read_data *rd)\n> {\n> \tstruct untracked_cache_dir ud, *untracked;\n> -\tconst unsigned char *next, *data = rd->data, *end = rd->end;\n> +\tconst unsigned char *data = rd->data, *end = rd->end;\n> \tconst unsigned char *eos;\n> \tunsigned int value;\n> \tint i, len;\n> \n> \tmemset(&ud, 0, sizeof(ud));\n> \n> -\tnext = data;\n> -\tvalue = decode_varint(&next);\n> -\tif (next > end)\n> +\tvalue = decode_varint(&data);\n> +\tif (data > end)\n> \t\treturn -1;\n> \tud.recurse\t = 1;\n> \tud.untracked_alloc = value;\n> \tud.untracked_nr\t = value;\n> \tif (ud.untracked_nr)\n> \t\tALLOC_ARRAY(ud.untracked, ud.untracked_nr);\n> -\tdata = next;\n> \n> -\tnext = data;\n> -\tud.dirs_alloc = ud.dirs_nr = decode_varint(&next);\n> -\tif (next > end)\n> +\tud.dirs_alloc = ud.dirs_nr = decode_varint(&data);\n> +\tif (data > end)\n> \t\treturn -1;\n> \tALLOC_ARRAY(ud.dirs, ud.dirs_nr);\n> -\tdata = next;\n> \n> \teos = memchr(data, '\\0', end - data);\n> \tif (!eos || eos == end)\n> \t\treturn -1;\n> \tlen = eos - data;\n> -\tnext = eos + 1;\n> \n> \t*untracked_ = untracked = xmalloc(st_add3(sizeof(*untracked), len, 1));\n> \tmemcpy(untracked, &ud, sizeof(ud));\n> \tmemcpy(untracked->name, data, len + 1);\n> -\tdata = next;\n> +\tdata = eos + 1;\n> \n> \tfor (i = 0; i < untracked->untracked_nr; i++) {\n> \t\teos = memchr(data, '\\0', end - data);\n> \t\tif (!eos || eos == end)\n> \t\t\treturn -1;\n> \t\tlen = eos - data;\n> -\t\tnext = eos + 1;\n> \t\tuntracked->untracked[i] = xmemdupz(data, len);\n> -\t\tdata = next;\n> +\t\tdata = eos + 1;\n> \t}\n> \n> \trd->ucd[rd->index++] = untracked;\n"},{"id":"374158","messageId":"20190419194329.GA28277@sigill.intra.peff.net","threadId":"50910","inReplyTo":"CACsJy8BHwM5dUqa-FOjr3smxJT6kW4z7vLUJvsHuhjxwUjvkBw@mail.gmail.com","subject":"Re: [PATCH 4/3] untracked-cache: use FLEX_ALLOC to create internal structs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-04-19T19:43:29Z","receivedAt":"2019-04-19T19:43:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Apr 19, 2019 at 04:18:25PM +0700, Duy Nguyen wrote:\n\n> > I also wondered if we could just accept the cost of calloc() here and\n> > use FLEX_ALLOC to simplify things. That resulted in the patch below, but\n> > I didn't include it with the initial 3, because I think it's too\n> > subtle/gross for my tastes.\n> \n> It's probably ok. If I remember correctly, reading UNTR extension (on\n> a huge repo) took the longest time after Ben added support for reading\n> the index with multiple threads. So performance is a concern, but I\n> don't think calloc() would be the problem. malloc() itself without the\n> memory pool could probably slow down more when we have lots and lots\n> of directories.\n\nI think if we do the FLEX_ALLOC_COPY() thing I mentioned that it would\nprobably _not_ use calloc() there, since we'd know we were copying in\nthe content from elsewhere. So that concern would go away either way. :)\n\n(But I'm still skeptical that FLEX_ALLOC_COPY() is worth it unless we\ncan find at least one other caller).\n\n-Peff\n"},{"id":"374162","messageId":"xmqqa7gmef55.fsf@gitster-ct.c.googlers.com","threadId":"50910","inReplyTo":"20190418211701.GA18520@sigill.intra.peff.net","subject":"Re: [PATCH 1/3] untracked-cache: be defensive about missing NULs in index","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-04-19T05:29:58Z","receivedAt":"2019-04-19T20:02:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> -\tlen = strlen((const char *)data);\n> -\tnext = data + len + 1;\n> -\tif (next > rd->end)\n> +\teos = memchr(data, '\\0', end - data);\n> +\tif (!eos || eos == end)\n> \t\treturn -1;\n> +\tlen = eos - data;\n> +\tnext = eos + 1;\n\nYup, much nicer.\n\n> -\t\tlen = strlen((const char *)data);\n> -\t\tnext = data + len + 1;\n> -\t\tif (next > rd->end)\n> +\t\teos = memchr(data, '\\0', end - data);\n> +\t\tif (!eos || eos == end)\n> \t\t\treturn -1;\n> -\t\tuntracked->untracked[i] = xstrdup((const char*)data);\n> +\t\tlen = eos - data;\n> +\t\tnext = eos + 1;\n> +\t\tuntracked->untracked[i] = xmemdupz(data, len);\n\nSame here, too.\n\nThanks.\n"}]}