{"thread":{"id":"56298","subject":"[PATCH] sparse-index: copy dir_hash in ensure_full_index()","startedAt":"2021-08-16T17:48:59Z","lastAt":"2021-08-23T19:28:01Z","messageCount":7,"participants":["Derrick Stolee via GitGitGadget","Derrick Stolee","Johannes Schindelin","Ævar Arnfjörð Bjarmason","Elijah Newren","Jeff Hostetler"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"432820","messageId":"pull.1017.git.1629136135286.gitgitgadget@gmail.com","threadId":"56298","inReplyTo":null,"subject":"[PATCH] sparse-index: copy dir_hash in ensure_full_index()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-08-16T17:48:55Z","receivedAt":"2021-08-16T17:48:59Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nCopy the 'index_state->dir_hash' back to the real istate after expanding\na sparse index.\n\nA crash was observed in 'git status' during some hashmap lookups with\ncorrupted hashmap entries.  During an index expansion, new cache-entries\nare added to the 'index_state->name_hash' and the 'dir_hash' in a\ntemporary 'index_state' variable 'full'.  However, only the 'name_hash'\nhashmap from this temp variable was copied back into the real 'istate'\nvariable.  The original copy of the 'dir_hash' was incorrectly\npreserved.  If the table in the 'full->dir_hash' hashmap were realloced,\nthe stale version (in 'istate') would be corrupted.\n\nThe test suite does not operate on index sizes sufficiently large to\ntrigger this reallocation, so they do not cover this behavior.\nIncreasing the test suite to cover such scale is fragile and likely\nwasteful.\n\nSigned-off-by: Jeff Hostetler <jeffhost@microsoft.com>\nSigned-off-by: Derrick Stolee <dstolee@microsoft.com>\n---\n    sparse-index: copy dir_hash in ensure_full_index()\n    \n    This fix is an issue we discovered in our first experimental release of\n    the sparse index in the microsoft/git fork. We fixed it in the latest\n    experimental release [1] and then I almost forgot about it until we\n    started rebasing sparse-index work on top of the 2.33.0 release\n    candidates.\n    \n    [1] https://github.com/microsoft/git/releases/tag/v2.32.0.vfs.0.102.exp\n    \n    This is a change that can be taken anywhere since 4300f8 (sparse-index:\n    implement ensure_full_index(), 2021-03-30), but this version is based on\n    v2.33.0-rc2.\n    \n    While the bug is alarming for users who hit it (seg fault) it requires\n    sufficient scale and use of the optional sparse index feature. We are\n    not recommending wide adoption of the sparse index yet because we don't\n    have a sufficient density of integrated commands. For that reason, I\n    don't think this should halt progress towards the full v2.33.0 release.\n    I did want to send this as soon as possible so that could be at the\n    discretion of the maintainer.\n    \n    Thanks, -Stolee\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1017%2Fderrickstolee%2Fsparse-index%2Ffix-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1017/derrickstolee/sparse-index/fix-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/1017\n\n sparse-index.c | 1 +\n 1 file changed, 1 insertion(+)\n\ndiff --git a/sparse-index.c b/sparse-index.c\nindex c6b4feec413..56eb65dc349 100644\n--- a/sparse-index.c\n+++ b/sparse-index.c\n@@ -283,6 +283,7 @@ void ensure_full_index(struct index_state *istate)\n \n \t/* Copy back into original index. */\n \tmemcpy(&istate->name_hash, &full->name_hash, sizeof(full->name_hash));\n+\tmemcpy(&istate->dir_hash, &full->dir_hash, sizeof(full->dir_hash));\n \tistate->sparse_index = 0;\n \tfree(istate->cache);\n \tistate->cache = full->cache;\n\nbase-commit: 5d213e46bb7b880238ff5ea3914e940a50ae9369\n-- \ngitgitgadget\n"},{"id":"433438","messageId":"5c0f41fb-e8d2-0aa5-66a3-6a61a98e8381@gmail.com","threadId":"56298","inReplyTo":"pull.1017.git.1629136135286.gitgitgadget@gmail.com","subject":"Re: [PATCH] sparse-index: copy dir_hash in ensure_full_index()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-08-23T13:13:59Z","receivedAt":"2021-08-23T13:14:03Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 8/16/2021 1:48 PM, Derrick Stolee via GitGitGadget wrote:\n> From: Jeff Hostetler <jeffhost@microsoft.com>\n> \n> Copy the 'index_state->dir_hash' back to the real istate after expanding\n> a sparse index.\n> \n> A crash was observed in 'git status' during some hashmap lookups with\n> corrupted hashmap entries.  During an index expansion, new cache-entries\n> are added to the 'index_state->name_hash' and the 'dir_hash' in a\n> temporary 'index_state' variable 'full'.  However, only the 'name_hash'\n> hashmap from this temp variable was copied back into the real 'istate'\n> variable.  The original copy of the 'dir_hash' was incorrectly\n> preserved.  If the table in the 'full->dir_hash' hashmap were realloced,\n> the stale version (in 'istate') would be corrupted.\n> \n> The test suite does not operate on index sizes sufficiently large to\n> trigger this reallocation, so they do not cover this behavior.\n> Increasing the test suite to cover such scale is fragile and likely\n> wasteful.\n> \n> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>\n> ---\n>     sparse-index: copy dir_hash in ensure_full_index()\n>     \n>     This fix is an issue we discovered in our first experimental release of\n>     the sparse index in the microsoft/git fork. We fixed it in the latest\n>     experimental release [1] and then I almost forgot about it until we\n>     started rebasing sparse-index work on top of the 2.33.0 release\n>     candidates.\n>     \n>     [1] https://github.com/microsoft/git/releases/tag/v2.32.0.vfs.0.102.exp\n>     \n>     This is a change that can be taken anywhere since 4300f8 (sparse-index:\n>     implement ensure_full_index(), 2021-03-30), but this version is based on\n>     v2.33.0-rc2.\n\nI sent this patch on the day of v2.33.0, so I'm not surprised that it\ngot lost in the shuffle. Could someone please take a look?\n\nIt also has not been picked up for the What's Cooking email.\n\nThanks,\n-Stolee\n"},{"id":"433441","messageId":"nycvar.QRO.7.76.6.2108231521320.55@tvgsbejvaqbjf.bet","threadId":"56298","inReplyTo":"pull.1017.git.1629136135286.gitgitgadget@gmail.com","subject":"Re: [PATCH] sparse-index: copy dir_hash in ensure_full_index()","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2021-08-23T13:22:22Z","receivedAt":"2021-08-23T13:22:36Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Stolee,\n\nOn Mon, 16 Aug 2021, Derrick Stolee via GitGitGadget wrote:\n\n> From: Jeff Hostetler <jeffhost@microsoft.com>\n>\n> Copy the 'index_state->dir_hash' back to the real istate after expanding\n> a sparse index.\n>\n> A crash was observed in 'git status' during some hashmap lookups with\n> corrupted hashmap entries.  During an index expansion, new cache-entries\n> are added to the 'index_state->name_hash' and the 'dir_hash' in a\n> temporary 'index_state' variable 'full'.  However, only the 'name_hash'\n> hashmap from this temp variable was copied back into the real 'istate'\n> variable.  The original copy of the 'dir_hash' was incorrectly\n> preserved.  If the table in the 'full->dir_hash' hashmap were realloced,\n> the stale version (in 'istate') would be corrupted.\n>\n> The test suite does not operate on index sizes sufficiently large to\n> trigger this reallocation, so they do not cover this behavior.\n> Increasing the test suite to cover such scale is fragile and likely\n> wasteful.\n\nThat explanation makes sense. And as the finder of the symptom, I can\nconfirm that it fixed the issue. So here is my `Reviewed-by:` ;-)\n\nCiao,\nDscho\n\n>\n> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>\n> ---\n>     sparse-index: copy dir_hash in ensure_full_index()\n>\n>     This fix is an issue we discovered in our first experimental release of\n>     the sparse index in the microsoft/git fork. We fixed it in the latest\n>     experimental release [1] and then I almost forgot about it until we\n>     started rebasing sparse-index work on top of the 2.33.0 release\n>     candidates.\n>\n>     [1] https://github.com/microsoft/git/releases/tag/v2.32.0.vfs.0.102.exp\n>\n>     This is a change that can be taken anywhere since 4300f8 (sparse-index:\n>     implement ensure_full_index(), 2021-03-30), but this version is based on\n>     v2.33.0-rc2.\n>\n>     While the bug is alarming for users who hit it (seg fault) it requires\n>     sufficient scale and use of the optional sparse index feature. We are\n>     not recommending wide adoption of the sparse index yet because we don't\n>     have a sufficient density of integrated commands. For that reason, I\n>     don't think this should halt progress towards the full v2.33.0 release.\n>     I did want to send this as soon as possible so that could be at the\n>     discretion of the maintainer.\n>\n>     Thanks, -Stolee\n>\n> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1017%2Fderrickstolee%2Fsparse-index%2Ffix-v1\n> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1017/derrickstolee/sparse-index/fix-v1\n> Pull-Request: https://github.com/gitgitgadget/git/pull/1017\n>\n>  sparse-index.c | 1 +\n>  1 file changed, 1 insertion(+)\n>\n> diff --git a/sparse-index.c b/sparse-index.c\n> index c6b4feec413..56eb65dc349 100644\n> --- a/sparse-index.c\n> +++ b/sparse-index.c\n> @@ -283,6 +283,7 @@ void ensure_full_index(struct index_state *istate)\n>\n>  \t/* Copy back into original index. */\n>  \tmemcpy(&istate->name_hash, &full->name_hash, sizeof(full->name_hash));\n> +\tmemcpy(&istate->dir_hash, &full->dir_hash, sizeof(full->dir_hash));\n>  \tistate->sparse_index = 0;\n>  \tfree(istate->cache);\n>  \tistate->cache = full->cache;\n>\n> base-commit: 5d213e46bb7b880238ff5ea3914e940a50ae9369\n> --\n> gitgitgadget\n>\n>\n"},{"id":"433445","messageId":"87h7fgfdah.fsf@evledraar.gmail.com","threadId":"56298","inReplyTo":"pull.1017.git.1629136135286.gitgitgadget@gmail.com","subject":"Re: [PATCH] sparse-index: copy dir_hash in ensure_full_index()","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-08-23T14:25:15Z","receivedAt":"2021-08-23T14:26:05Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Mon, Aug 16 2021, Derrick Stolee via GitGitGadget wrote:\n\n> From: Jeff Hostetler <jeffhost@microsoft.com>\n>\n> Copy the 'index_state->dir_hash' back to the real istate after expanding\n> a sparse index.\n>\n> A crash was observed in 'git status' during some hashmap lookups with\n> corrupted hashmap entries.  During an index expansion, new cache-entries\n> are added to the 'index_state->name_hash' and the 'dir_hash' in a\n> temporary 'index_state' variable 'full'.  However, only the 'name_hash'\n> hashmap from this temp variable was copied back into the real 'istate'\n> variable.  The original copy of the 'dir_hash' was incorrectly\n> preserved.  If the table in the 'full->dir_hash' hashmap were realloced,\n> the stale version (in 'istate') would be corrupted.\n>\n> The test suite does not operate on index sizes sufficiently large to\n> trigger this reallocation, so they do not cover this behavior.\n> Increasing the test suite to cover such scale is fragile and likely\n> wasteful.\n\nHow large does the index need to be to trigger this? I don't know if a\ntest here is useful, but FWIW if we had such a test then the EXPENSIVE\nprereq + GIT_TEST_LONG=true might be a good fit for it.\n\n> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>\n> ---\n>     sparse-index: copy dir_hash in ensure_full_index()\n>     \n>     This fix is an issue we discovered in our first experimental release of\n>     the sparse index in the microsoft/git fork. We fixed it in the latest\n>     experimental release [1] and then I almost forgot about it until we\n>     started rebasing sparse-index work on top of the 2.33.0 release\n>     candidates.\n>     \n>     [1] https://github.com/microsoft/git/releases/tag/v2.32.0.vfs.0.102.exp\n>     \n>     This is a change that can be taken anywhere since 4300f8 (sparse-index:\n>     implement ensure_full_index(), 2021-03-30), but this version is based on\n>     v2.33.0-rc2.\n>     \n>     While the bug is alarming for users who hit it (seg fault) it requires\n>     sufficient scale and use of the optional sparse index feature. We are\n>     not recommending wide adoption of the sparse index yet because we don't\n>     have a sufficient density of integrated commands. For that reason, I\n>     don't think this should halt progress towards the full v2.33.0 release.\n>     I did want to send this as soon as possible so that could be at the\n>     discretion of the maintainer.\n>     \n>     Thanks, -Stolee\n>\n> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1017%2Fderrickstolee%2Fsparse-index%2Ffix-v1\n> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1017/derrickstolee/sparse-index/fix-v1\n> Pull-Request: https://github.com/gitgitgadget/git/pull/1017\n>\n>  sparse-index.c | 1 +\n>  1 file changed, 1 insertion(+)\n>\n> diff --git a/sparse-index.c b/sparse-index.c\n> index c6b4feec413..56eb65dc349 100644\n> --- a/sparse-index.c\n> +++ b/sparse-index.c\n> @@ -283,6 +283,7 @@ void ensure_full_index(struct index_state *istate)\n>  \n>  \t/* Copy back into original index. */\n>  \tmemcpy(&istate->name_hash, &full->name_hash, sizeof(full->name_hash));\n> +\tmemcpy(&istate->dir_hash, &full->dir_hash, sizeof(full->dir_hash));\n>  \tistate->sparse_index = 0;\n>  \tfree(istate->cache);\n>  \tistate->cache = full->cache;\n>\n> base-commit: 5d213e46bb7b880238ff5ea3914e940a50ae9369\n\n"},{"id":"433470","messageId":"CABPp-BFF4S13NUjznqYfZ01ceJT7aGV3ybz8Yx2TWTcg3ri+eA@mail.gmail.com","threadId":"56298","inReplyTo":"5c0f41fb-e8d2-0aa5-66a3-6a61a98e8381@gmail.com","subject":"Re: [PATCH] sparse-index: copy dir_hash in ensure_full_index()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-08-23T17:54:20Z","receivedAt":"2021-08-23T17:54:34Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Mon, Aug 23, 2021 at 6:14 AM Derrick Stolee <stolee@gmail.com> wrote:\n>\n> On 8/16/2021 1:48 PM, Derrick Stolee via GitGitGadget wrote:\n> > From: Jeff Hostetler <jeffhost@microsoft.com>\n> >\n> > Copy the 'index_state->dir_hash' back to the real istate after expanding\n> > a sparse index.\n> >\n> > A crash was observed in 'git status' during some hashmap lookups with\n> > corrupted hashmap entries.  During an index expansion, new cache-entries\n> > are added to the 'index_state->name_hash' and the 'dir_hash' in a\n> > temporary 'index_state' variable 'full'.  However, only the 'name_hash'\n> > hashmap from this temp variable was copied back into the real 'istate'\n> > variable.  The original copy of the 'dir_hash' was incorrectly\n> > preserved.  If the table in the 'full->dir_hash' hashmap were realloced,\n> > the stale version (in 'istate') would be corrupted.\n> >\n> > The test suite does not operate on index sizes sufficiently large to\n> > trigger this reallocation, so they do not cover this behavior.\n> > Increasing the test suite to cover such scale is fragile and likely\n> > wasteful.\n> >\n> > Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n> > Signed-off-by: Derrick Stolee <dstolee@microsoft.com>\n> > ---\n> >     sparse-index: copy dir_hash in ensure_full_index()\n> >\n> >     This fix is an issue we discovered in our first experimental release of\n> >     the sparse index in the microsoft/git fork. We fixed it in the latest\n> >     experimental release [1] and then I almost forgot about it until we\n> >     started rebasing sparse-index work on top of the 2.33.0 release\n> >     candidates.\n> >\n> >     [1] https://github.com/microsoft/git/releases/tag/v2.32.0.vfs.0.102.exp\n> >\n> >     This is a change that can be taken anywhere since 4300f8 (sparse-index:\n> >     implement ensure_full_index(), 2021-03-30), but this version is based on\n> >     v2.33.0-rc2.\n>\n> I sent this patch on the day of v2.33.0, so I'm not surprised that it\n> got lost in the shuffle. Could someone please take a look?\n>\n> It also has not been picked up for the What's Cooking email.\n\nExplanation and the code make sense to me.  This function uses some\npretty low-level knowledge of how index_state is structured to do its\njob, and if index_state is updated in some significant way (which\nisn't likely), then someone would have to update this function.  I was\ntrying to think whether there was a way to future proof this function\nagainst such possibilities to ensure the need to update it is noticed,\nbut I'm not sure there is one.  But index_state doesn't seem\nparticularly likely to change, so this is probably fine.  So, here's\nmy ack.\n"},{"id":"433476","messageId":"8058589d-f84f-2fdc-6057-8242cde9df61@jeffhostetler.com","threadId":"56298","inReplyTo":"87h7fgfdah.fsf@evledraar.gmail.com","subject":"Re: [PATCH] sparse-index: copy dir_hash in ensure_full_index()","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2021-08-23T18:18:53Z","receivedAt":"2021-08-23T18:18:57Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 8/23/21 10:25 AM, Ævar Arnfjörð Bjarmason wrote:\n> \n> On Mon, Aug 16 2021, Derrick Stolee via GitGitGadget wrote:\n> \n>> From: Jeff Hostetler <jeffhost@microsoft.com>\n>>\n>> Copy the 'index_state->dir_hash' back to the real istate after expanding\n>> a sparse index.\n>>\n>> A crash was observed in 'git status' during some hashmap lookups with\n>> corrupted hashmap entries.  During an index expansion, new cache-entries\n>> are added to the 'index_state->name_hash' and the 'dir_hash' in a\n>> temporary 'index_state' variable 'full'.  However, only the 'name_hash'\n>> hashmap from this temp variable was copied back into the real 'istate'\n>> variable.  The original copy of the 'dir_hash' was incorrectly\n>> preserved.  If the table in the 'full->dir_hash' hashmap were realloced,\n>> the stale version (in 'istate') would be corrupted.\n>>\n>> The test suite does not operate on index sizes sufficiently large to\n>> trigger this reallocation, so they do not cover this behavior.\n>> Increasing the test suite to cover such scale is fragile and likely\n>> wasteful.\n> \n> How large does the index need to be to trigger this? I don't know if a\n> test here is useful, but FWIW if we had such a test then the EXPENSIVE\n> prereq + GIT_TEST_LONG=true might be a good fit for it.\n> \n\nThere would need to be enough directories in the repo to cause\nthe dir_hash to grow during an insert into the dir_hash.\nIIRC the hashmap table is initialized to 64 and auto reallocs when\nit hits 80% capacity, so somewhere in the area of 50 directories\nat minimum.\n\nWhether the error is observed would also depend on free() trashing\nthe contents of the memory and/or whether the memory was recycled\nby something else.\n\nJeff\n\n"},{"id":"433484","messageId":"2431b77d-0d10-0fd6-5ccd-8250db9f7998@gmail.com","threadId":"56298","inReplyTo":"8058589d-f84f-2fdc-6057-8242cde9df61@jeffhostetler.com","subject":"Re: [PATCH] sparse-index: copy dir_hash in ensure_full_index()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-08-23T19:27:57Z","receivedAt":"2021-08-23T19:28:01Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 8/23/2021 2:18 PM, Jeff Hostetler wrote:\n> On 8/23/21 10:25 AM, Ævar Arnfjörð Bjarmason wrote:\n>>\n>> On Mon, Aug 16 2021, Derrick Stolee via GitGitGadget wrote:\n>>\n>>> From: Jeff Hostetler <jeffhost@microsoft.com>\n>>>\n>>> Copy the 'index_state->dir_hash' back to the real istate after expanding\n>>> a sparse index.\n>>>\n>>> A crash was observed in 'git status' during some hashmap lookups with\n>>> corrupted hashmap entries.  During an index expansion, new cache-entries\n>>> are added to the 'index_state->name_hash' and the 'dir_hash' in a\n>>> temporary 'index_state' variable 'full'.  However, only the 'name_hash'\n>>> hashmap from this temp variable was copied back into the real 'istate'\n>>> variable.  The original copy of the 'dir_hash' was incorrectly\n>>> preserved.  If the table in the 'full->dir_hash' hashmap were realloced,\n>>> the stale version (in 'istate') would be corrupted.\n>>>\n>>> The test suite does not operate on index sizes sufficiently large to\n>>> trigger this reallocation, so they do not cover this behavior.\n>>> Increasing the test suite to cover such scale is fragile and likely\n>>> wasteful.\n>>\n>> How large does the index need to be to trigger this? I don't know if a\n>> test here is useful, but FWIW if we had such a test then the EXPENSIVE\n>> prereq + GIT_TEST_LONG=true might be a good fit for it.\n>>\n> \n> There would need to be enough directories in the repo to cause\n> the dir_hash to grow during an insert into the dir_hash.\n> IIRC the hashmap table is initialized to 64 and auto reallocs when\n> it hits 80% capacity, so somewhere in the area of 50 directories\n> at minimum.\n\nFurther complicating this is that the sparse index size matters\nrelative to the full index size, since the dir_hash has a given\nsize going into ensure_full_index() that depends on the sparse-index\nsize and the reallocation patterns.\n \n> Whether the error is observed would also depend on free() trashing\n> the contents of the memory and/or whether the memory was recycled\n> by something else.\n\nIssues like this cause this to be hard to reproduce. We did not\ncatch it in the performance test p2000-sparse-operations.sh, which\naims to measure how the index works at scale.\n\nThis makes me incredibly pessimistic that such a test will be\neffective at preventing a regression, let alone catching similar\nissues in the future.\n\nThanks,\n-Stolee\n"}]}