sparse-index: copy dir_hash in ensure_full_index()

PATCH In review Derrick Stolee via GitGitGadget 6 participants 7 messages Aug 16, 2021 – Aug 23, 2021

lore

Share & tools

lore

Derrick Stolee via GitGitGadget

author

2021-08-16 17:48 UTC #0 lore raw

PATCH 1/1 sparse-index: copy dir_hash in ensure_full_index()

From: Jeff Hostetler <[email protected]>

Copy the 'index_state->dir_hash' back to the real istate after expanding a sparse index.

A crash was observed in 'git status' during some hashmap lookups with corrupted hashmap entries. During an index expansion, new cache-entries are added to the 'index_state->name_hash' and the 'dir_hash' in a temporary 'index_state' variable 'full'. However, only the 'name_hash' hashmap from this temp variable was copied back into the real 'istate' variable. The original copy of the 'dir_hash' was incorrectly preserved. If the table in the 'full->dir_hash' hashmap were realloced, the stale version (in 'istate') would be corrupted.

The test suite does not operate on index sizes sufficiently large to trigger this reallocation, so they do not cover this behavior. Increasing the test suite to cover such scale is fragile and likely wasteful.

Signed-off-by Jeff Hostetler <[email protected]>

Signed-off-by Derrick Stolee <[email protected]>

---
sparse-index: copy dir_hash in ensure_full_index()

This fix is an issue we discovered in our first experimental release of the sparse index in the microsoft/git fork. We fixed it in the latest experimental release [1] and then I almost forgot about it until we started rebasing sparse-index work on top of the 2.33.0 release candidates.

[1] https://github.com/microsoft/git/releases/tag/v2.32.0.vfs.0.102.exp

This is a change that can be taken anywhere since 4300f8 (sparse-index:
implement ensure_full_index(), 2021-03-30), but this version is based on v2.33.0-rc2.

While the bug is alarming for users who hit it (seg fault) it requires sufficient scale and use of the optional sparse index feature. We are not recommending wide adoption of the sparse index yet because we don't have a sufficient density of integrated commands. For that reason, I don't think this should halt progress towards the full v2.33.0 release. I did want to send this as soon as possible so that could be at the discretion of the maintainer.

Thanks, -Stolee

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1017%2Fderrickstolee%2Fsparse-index%2Ffix-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1017/derrickstolee/sparse-index/fix-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1017

 sparse-index.c | 1 +
 1 file changed, 1 insertion(+)

sparse-index.c +1 -0

index c6b4feec413..56eb65dc349 100644
@@ -283,6 +283,7 @@ void ensure_full_index(struct index_state *istate)
 
 	/* Copy back into original index. */
 	memcpy(&istate->name_hash, &full->name_hash, sizeof(full->name_hash));
+	memcpy(&istate->dir_hash, &full->dir_hash, sizeof(full->dir_hash));
 	istate->sparse_index = 0;
 	free(istate->cache);
 	istate->cache = full->cache;

base-commit: 5d213e46bb7b880238ff5ea3914e940a50ae9369

Signature · 1 line

gitgitgadget

Derrick Stolee

2021-08-23 13:14 UTC #1 lore raw

Quoted 30 lines · Derrick Stolee via GitGitGadget

From: Jeff Hostetler <[email protected]>
Copy the 'index_state->dir_hash' back to the real istate after expanding a sparse index.
A crash was observed in 'git status' during some hashmap lookups with corrupted hashmap entries. During an index expansion, new cache-entries are added to the 'index_state->name_hash' and the 'dir_hash' in a temporary 'index_state' variable 'full'. However, only the 'name_hash' hashmap from this temp variable was copied back into the real 'istate' variable. The original copy of the 'dir_hash' was incorrectly preserved. If the table in the 'full->dir_hash' hashmap were realloced, the stale version (in 'istate') would be corrupted.
The test suite does not operate on index sizes sufficiently large to trigger this reallocation, so they do not cover this behavior. Increasing the test suite to cover such scale is fragile and likely wasteful.
Signed-off-by Jeff Hostetler <[email protected]>
Signed-off-by Derrick Stolee <[email protected]>
---
sparse-index: copy dir_hash in ensure_full_index()
This fix is an issue we discovered in our first experimental release of the sparse index in the microsoft/git fork. We fixed it in the latest experimental release [1] and then I almost forgot about it until we started rebasing sparse-index work on top of the 2.33.0 release candidates.

Quoted 5 lines

[1] https://github.com/microsoft/git/releases/tag/v2.32.0.vfs.0.102.exp
This is a change that can be taken anywhere since 4300f8 (sparse-index:
implement ensure_full_index(), 2021-03-30), but this version is based on v2.33.0-rc2.

I sent this patch on the day of v2.33.0, so I'm not surprised that it got lost in the shuffle. Could someone please take a look?

It also has not been picked up for the What's Cooking email.

Thanks,
-Stolee

Johannes Schindelin

2021-08-23 13:22 UTC #3 lore raw

In reply to Derrick Stolee via GitGitGadget

Hi Stolee,

Quoted 14 lines · Derrick Stolee via GitGitGadget

From: Jeff Hostetler <[email protected]>
Copy the 'index_state->dir_hash' back to the real istate after expanding a sparse index.
A crash was observed in 'git status' during some hashmap lookups with corrupted hashmap entries. During an index expansion, new cache-entries are added to the 'index_state->name_hash' and the 'dir_hash' in a temporary 'index_state' variable 'full'. However, only the 'name_hash' hashmap from this temp variable was copied back into the real 'istate' variable. The original copy of the 'dir_hash' was incorrectly preserved. If the table in the 'full->dir_hash' hashmap were realloced, the stale version (in 'istate') would be corrupted.

Quoted 4 lines

The test suite does not operate on index sizes sufficiently large to trigger this reallocation, so they do not cover this behavior. Increasing the test suite to cover such scale is fragile and likely wasteful.

That explanation makes sense. And as the finder of the symptom, I can confirm that it fixed the issue. So here is my Reviewed-by: ;-)

Ciao,
Dscho

Quoted 53 lines

Signed-off-by Jeff Hostetler <[email protected]>
Signed-off-by Derrick Stolee <[email protected]>
---
sparse-index: copy dir_hash in ensure_full_index()
This fix is an issue we discovered in our first experimental release of the sparse index in the microsoft/git fork. We fixed it in the latest experimental release [1] and then I almost forgot about it until we started rebasing sparse-index work on top of the 2.33.0 release candidates.
[1] https://github.com/microsoft/git/releases/tag/v2.32.0.vfs.0.102.exp
This is a change that can be taken anywhere since 4300f8 (sparse-index:
implement ensure_full_index(), 2021-03-30), but this version is based on v2.33.0-rc2.
While the bug is alarming for users who hit it (seg fault) it requires sufficient scale and use of the optional sparse index feature. We are not recommending wide adoption of the sparse index yet because we don't have a sufficient density of integrated commands. For that reason, I don't think this should halt progress towards the full v2.33.0 release. I did want to send this as soon as possible so that could be at the discretion of the maintainer.
Thanks, -Stolee
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1017%2Fderrickstolee%2Fsparse-index%2Ffix-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1017/derrickstolee/sparse-index/fix-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1017
 sparse-index.c | 1 +
 1 file changed, 1 insertion(+)
sparse-index.c +1 -0
index c6b4feec413..56eb65dc349 100644
@@ -283,6 +283,7 @@ void ensure_full_index(struct index_state *istate)
 
 	/* Copy back into original index. */
 	memcpy(&istate->name_hash, &full->name_hash, sizeof(full->name_hash));
+	memcpy(&istate->dir_hash, &full->dir_hash, sizeof(full->dir_hash));
 	istate->sparse_index = 0;
 	free(istate->cache);
 	istate->cache = full->cache;
base-commit: 5d213e46bb7b880238ff5ea3914e940a50ae9369 --
gitgitgadget

Ævar Arnfjörð Bjarmason

2021-08-23 14:26 UTC #4 lore raw

In reply to Derrick Stolee via GitGitGadget

Quoted 14 lines · Derrick Stolee via GitGitGadget

From: Jeff Hostetler <[email protected]>
Copy the 'index_state->dir_hash' back to the real istate after expanding a sparse index.
A crash was observed in 'git status' during some hashmap lookups with corrupted hashmap entries. During an index expansion, new cache-entries are added to the 'index_state->name_hash' and the 'dir_hash' in a temporary 'index_state' variable 'full'. However, only the 'name_hash' hashmap from this temp variable was copied back into the real 'istate' variable. The original copy of the 'dir_hash' was incorrectly preserved. If the table in the 'full->dir_hash' hashmap were realloced, the stale version (in 'istate') would be corrupted.

Quoted 4 lines

The test suite does not operate on index sizes sufficiently large to trigger this reallocation, so they do not cover this behavior. Increasing the test suite to cover such scale is fragile and likely wasteful.

How large does the index need to be to trigger this? I don't know if a test here is useful, but FWIW if we had such a test then the EXPENSIVE prereq + GIT_TEST_LONG=true might be a good fit for it.

Quoted 48 lines

Signed-off-by Jeff Hostetler <[email protected]>
Signed-off-by Derrick Stolee <[email protected]>
---
sparse-index: copy dir_hash in ensure_full_index()
This fix is an issue we discovered in our first experimental release of the sparse index in the microsoft/git fork. We fixed it in the latest experimental release [1] and then I almost forgot about it until we started rebasing sparse-index work on top of the 2.33.0 release candidates.
[1] https://github.com/microsoft/git/releases/tag/v2.32.0.vfs.0.102.exp
This is a change that can be taken anywhere since 4300f8 (sparse-index:
implement ensure_full_index(), 2021-03-30), but this version is based on v2.33.0-rc2.
While the bug is alarming for users who hit it (seg fault) it requires sufficient scale and use of the optional sparse index feature. We are not recommending wide adoption of the sparse index yet because we don't have a sufficient density of integrated commands. For that reason, I don't think this should halt progress towards the full v2.33.0 release. I did want to send this as soon as possible so that could be at the discretion of the maintainer.
Thanks, -Stolee
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1017%2Fderrickstolee%2Fsparse-index%2Ffix-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1017/derrickstolee/sparse-index/fix-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1017
 sparse-index.c | 1 +
 1 file changed, 1 insertion(+)
sparse-index.c +1 -0
index c6b4feec413..56eb65dc349 100644
@@ -283,6 +283,7 @@ void ensure_full_index(struct index_state *istate)
 
 	/* Copy back into original index. */
 	memcpy(&istate->name_hash, &full->name_hash, sizeof(full->name_hash));
+	memcpy(&istate->dir_hash, &full->dir_hash, sizeof(full->dir_hash));
 	istate->sparse_index = 0;
 	free(istate->cache);
 	istate->cache = full->cache;
base-commit: 5d213e46bb7b880238ff5ea3914e940a50ae9369

Elijah Newren

2021-08-23 17:54 UTC #2 lore raw

In reply to Derrick Stolee

Quoted 34 lines · Derrick Stolee

Quoted 32 lines · Derrick Stolee via GitGitGadget
From: Jeff Hostetler <[email protected]>
Copy the 'index_state->dir_hash' back to the real istate after expanding a sparse index.
A crash was observed in 'git status' during some hashmap lookups with corrupted hashmap entries. During an index expansion, new cache-entries are added to the 'index_state->name_hash' and the 'dir_hash' in a temporary 'index_state' variable 'full'. However, only the 'name_hash' hashmap from this temp variable was copied back into the real 'istate' variable. The original copy of the 'dir_hash' was incorrectly preserved. If the table in the 'full->dir_hash' hashmap were realloced, the stale version (in 'istate') would be corrupted.
The test suite does not operate on index sizes sufficiently large to trigger this reallocation, so they do not cover this behavior. Increasing the test suite to cover such scale is fragile and likely wasteful.
Signed-off-by Jeff Hostetler <[email protected]>
Signed-off-by Derrick Stolee <[email protected]>
---
sparse-index: copy dir_hash in ensure_full_index()
This fix is an issue we discovered in our first experimental release of the sparse index in the microsoft/git fork. We fixed it in the latest experimental release [1] and then I almost forgot about it until we started rebasing sparse-index work on top of the 2.33.0 release candidates.
[1] https://github.com/microsoft/git/releases/tag/v2.32.0.vfs.0.102.exp

Quoted 8 lines

Quoted 3 lines
This is a change that can be taken anywhere since 4300f8 (sparse-index:
implement ensure_full_index(), 2021-03-30), but this version is based on v2.33.0-rc2.
I sent this patch on the day of v2.33.0, so I'm not surprised that it got lost in the shuffle. Could someone please take a look?
It also has not been picked up for the What's Cooking email.

Explanation and the code make sense to me. This function uses some pretty low-level knowledge of how index_state is structured to do its job, and if index_state is updated in some significant way (which isn't likely), then someone would have to update this function. I was trying to think whether there was a way to future proof this function against such possibilities to ensure the need to update it is noticed, but I'm not sure there is one. But index_state doesn't seem particularly likely to change, so this is probably fine. So, here's my ack.

Jeff Hostetler

2021-08-23 18:18 UTC #5 lore raw

In reply to Ævar Arnfjörð Bjarmason

Quoted 17 lines · Ævar Arnfjörð Bjarmason

Quoted 14 lines · Derrick Stolee via GitGitGadget
From: Jeff Hostetler <[email protected]>
Copy the 'index_state->dir_hash' back to the real istate after expanding a sparse index.
A crash was observed in 'git status' during some hashmap lookups with corrupted hashmap entries. During an index expansion, new cache-entries are added to the 'index_state->name_hash' and the 'dir_hash' in a temporary 'index_state' variable 'full'. However, only the 'name_hash' hashmap from this temp variable was copied back into the real 'istate' variable. The original copy of the 'dir_hash' was incorrectly preserved. If the table in the 'full->dir_hash' hashmap were realloced, the stale version (in 'istate') would be corrupted.

Quoted 9 lines

Quoted 4 lines
The test suite does not operate on index sizes sufficiently large to trigger this reallocation, so they do not cover this behavior. Increasing the test suite to cover such scale is fragile and likely wasteful.
How large does the index need to be to trigger this? I don't know if a test here is useful, but FWIW if we had such a test then the EXPENSIVE prereq + GIT_TEST_LONG=true might be a good fit for it.

There would need to be enough directories in the repo to cause the dir_hash to grow during an insert into the dir_hash. IIRC the hashmap table is initialized to 64 and auto reallocs when it hits 80% capacity, so somewhere in the area of 50 directories at minimum.

Whether the error is observed would also depend on free() trashing the contents of the memory and/or whether the memory was recycled by something else.

Jeff

Derrick Stolee

2021-08-23 19:28 UTC #6 lore raw

Quoted 28 lines · Jeff Hostetler

Quoted 17 lines · Ævar Arnfjörð Bjarmason
Quoted 14 lines · Derrick Stolee via GitGitGadget
From: Jeff Hostetler <[email protected]>
Copy the 'index_state->dir_hash' back to the real istate after expanding a sparse index.
A crash was observed in 'git status' during some hashmap lookups with corrupted hashmap entries. During an index expansion, new cache-entries are added to the 'index_state->name_hash' and the 'dir_hash' in a temporary 'index_state' variable 'full'. However, only the 'name_hash' hashmap from this temp variable was copied back into the real 'istate' variable. The original copy of the 'dir_hash' was incorrectly preserved. If the table in the 'full->dir_hash' hashmap were realloced, the stale version (in 'istate') would be corrupted.
Quoted 9 lines
Quoted 4 lines
The test suite does not operate on index sizes sufficiently large to trigger this reallocation, so they do not cover this behavior. Increasing the test suite to cover such scale is fragile and likely wasteful.
How large does the index need to be to trigger this? I don't know if a test here is useful, but FWIW if we had such a test then the EXPENSIVE prereq + GIT_TEST_LONG=true might be a good fit for it.

Quoted 5 lines

There would need to be enough directories in the repo to cause the dir_hash to grow during an insert into the dir_hash. IIRC the hashmap table is initialized to 64 and auto reallocs when it hits 80% capacity, so somewhere in the area of 50 directories at minimum.

Further complicating this is that the sparse index size matters relative to the full index size, since the dir_hash has a given size going into ensure_full_index() that depends on the sparse-index size and the reallocation patterns.

Quoted 3 lines

Whether the error is observed would also depend on free() trashing the contents of the memory and/or whether the memory was recycled by something else.

Issues like this cause this to be hard to reproduce. We did not catch it in the performance test p2000-sparse-operations.sh, which aims to measure how the index works at scale.

This makes me incredibly pessimistic that such a test will be effective at preventing a regression, let alone catching similar issues in the future.

Thanks,
-Stolee