| Message ID | pull.1053.git.1633512591608.gitgitgadget@gmail.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | [RFC] sparse index: fix use-after-free bug in cache_tree_verify() | expand |
On 10/6/2021 5:29 AM, Phillip Wood via GitGitGadget wrote: > From: Phillip Wood <phillip.wood@dunelm.org.uk> > > In a sparse index it is possible for the tree that is being verified > to be freed while it is being verified. This happens when > index_name_pos() looks up a entry that is missing from the index and > that would be a descendant of a sparse entry. That triggers a call to > ensure_full_index() which frees the cache tree that is being verified. > Carrying on trying to verify the tree after this results in a > use-after-free bug. Instead restart the verification if a sparse index > is converted to a full index. This bug is triggered by a call to > reset_head() in "git rebase --apply". Thanks to René Scharfe for his > help analyzing the problem. Thank you for identifying an interesting case! I hadn't thought to change the mode from --merge to --apply. > In a sparse index it is possible for the tree that is being verified to > be freed while it is being verified. This is an RFC as I'm not familiar > with the cache tree code. I'm confused as to why this bug is triggered > by the sequence > > unpack_trees() > prime_cache_tree() > write_locked_index() > > but not > > unpack_trees() > write_locked_index() > > > as unpack_trees() appears to update the cache tree with > > if (!cache_tree_fully_valid(o->result.cache_tree)) > cache_tree_update(&o->result, > WRITE_TREE_SILENT | > WRITE_TREE_REPAIR); > > > and I don't understand why the cache tree from prime_cache_tree() > results in different behavior. It concerns me that this fix is hiding > another bug. prime_cache_tree() appears to clear the cache tree and start from scratch from a tree object instead of using the index. In particular, prime_cache_tree_rec() does not stop at the sparse-checkout cone, so the cache tree is the full size at that point. When the verify_one() method reaches these nodes that are outside of the cone, index_name_pos() triggers the index expansion in a way that the cache-tree that is restricted to the sparse-checkout cone does not. Hopefully that helps clear up _why_ this happens. There is a remaining issue that "git rebase --apply" will be a lot slower than "git rebase --merge" because of this construction of a cache-tree that is much larger than necessary. I will make note of this as a potential improvement for the future. > -static void verify_one(struct repository *r, > - struct index_state *istate, > - struct cache_tree *it, > - struct strbuf *path) > +static int verify_one(struct repository *r, > + struct index_state *istate, > + struct cache_tree *it, > + struct strbuf *path) > { > int i, pos, len = path->len; > struct strbuf tree_buf = STRBUF_INIT; > @@ -837,21 +837,30 @@ static void verify_one(struct repository *r, > > for (i = 0; i < it->subtree_nr; i++) { > strbuf_addf(path, "%s/", it->down[i]->name); > - verify_one(r, istate, it->down[i]->cache_tree, path); > + if (verify_one(r, istate, it->down[i]->cache_tree, path)) > + return 1; > strbuf_setlen(path, len); > } > > if (it->entry_count < 0 || > /* no verification on tests (t7003) that replace trees */ > lookup_replace_object(r, &it->oid) != &it->oid) > - return; > + return 0; > > if (path->len) { > + /* > + * If the index is sparse index_name_pos() may trigger > + * ensure_full_index() which will free the tree that is being > + * verified. > + */ > + int is_sparse = istate->sparse_index; > pos = index_name_pos(istate, path->buf, path->len); > + if (is_sparse && !istate->sparse_index) > + return 1; I think this guard is good to have, even if we fix prime_cache_tree() to avoid triggering expansion here in most cases. > if (pos >= 0) { > verify_one_sparse(r, istate, it, path, pos); > - return; > + return 0; > } > > pos = -pos - 1; > @@ -899,6 +908,7 @@ static void verify_one(struct repository *r, > oid_to_hex(&new_oid), oid_to_hex(&it->oid)); > strbuf_setlen(path, len); > strbuf_release(&tree_buf); > + return 0; > } > > void cache_tree_verify(struct repository *r, struct index_state *istate) > @@ -907,6 +917,9 @@ void cache_tree_verify(struct repository *r, struct index_state *istate) > > if (!istate->cache_tree) > return; > - verify_one(r, istate, istate->cache_tree, &path); > + if (verify_one(r, istate, istate->cache_tree, &path)) { > + strbuf_reset(&path); > + verify_one(r, istate, istate->cache_tree, &path); > + } And this limits us to doing at most two passes. Good. > test_expect_success 'merge, cherry-pick, and rebase' ' > init_repos && > > - for OPERATION in "merge -m merge" cherry-pick rebase > + for OPERATION in "merge -m merge" cherry-pick "rebase --apply" "rebase --merge" Thank you for the additional test! Thanks, -Stolee
Hi Stolee On 06/10/2021 12:20, Derrick Stolee wrote: > On 10/6/2021 5:29 AM, Phillip Wood via GitGitGadget wrote: >> From: Phillip Wood <phillip.wood@dunelm.org.uk> >> >> In a sparse index it is possible for the tree that is being verified >> to be freed while it is being verified. This happens when >> index_name_pos() looks up a entry that is missing from the index and >> that would be a descendant of a sparse entry. That triggers a call to >> ensure_full_index() which frees the cache tree that is being verified. >> Carrying on trying to verify the tree after this results in a >> use-after-free bug. Instead restart the verification if a sparse index >> is converted to a full index. This bug is triggered by a call to >> reset_head() in "git rebase --apply". Thanks to René Scharfe for his >> help analyzing the problem. > > Thank you for identifying an interesting case! I hadn't thought to > change the mode from --merge to --apply. Thanks, I can't really take much credit for that though - Junio pointed out that my patch converting the merge based rebase to use the same checkout code as the apply based rebase broke a test in seen and René diagnosed the problem. >> In a sparse index it is possible for the tree that is being verified to >> be freed while it is being verified. This is an RFC as I'm not familiar >> with the cache tree code. I'm confused as to why this bug is triggered >> by the sequence >> >> unpack_trees() >> prime_cache_tree() >> write_locked_index() >> >> but not >> >> unpack_trees() >> write_locked_index() >> >> >> as unpack_trees() appears to update the cache tree with >> >> if (!cache_tree_fully_valid(o->result.cache_tree)) >> cache_tree_update(&o->result, >> WRITE_TREE_SILENT | >> WRITE_TREE_REPAIR); >> >> >> and I don't understand why the cache tree from prime_cache_tree() >> results in different behavior. It concerns me that this fix is hiding >> another bug. > > prime_cache_tree() appears to clear the cache tree and start from scratch > from a tree object instead of using the index. > > In particular, prime_cache_tree_rec() does not stop at the sparse-checkout > cone, so the cache tree is the full size at that point. > > When the verify_one() method reaches these nodes that are outside of the > cone, index_name_pos() triggers the index expansion in a way that the > cache-tree that is restricted to the sparse-checkout cone does not. > > Hopefully that helps clear up _why_ this happens. It does thanks - we end up with a full cache tree but a sparse index > There is a remaining issue that "git rebase --apply" will be a lot slower > than "git rebase --merge" because of this construction of a cache-tree > that is much larger than necessary. > > I will make note of this as a potential improvement for the future. I think I'm going to remove the call to prime_cache_tree(). Correct me if I'm wrong but as I understand it unpack_trees() updates the cache tree so the call to prime_cache_tree() is not needed (I think it was copied from builtin/rebase.c which does need to call prime_cache_tree() if it has updated a few paths rather than the whole top-level tree). In any case I've just noticed that one of Victoria's patches[1] looks like it fixes prime_cache_tree() with a sparse index. [1] https://lore.kernel.org/git/78cd85d8dcc790251ce8235e649902cf6adf091a.1633440057.git.gitgitgadget@gmail.com/ >> -static void verify_one(struct repository *r, >> - struct index_state *istate, >> - struct cache_tree *it, >> - struct strbuf *path) >> +static int verify_one(struct repository *r, >> + struct index_state *istate, >> + struct cache_tree *it, >> + struct strbuf *path) >> { >> int i, pos, len = path->len; >> struct strbuf tree_buf = STRBUF_INIT; >> @@ -837,21 +837,30 @@ static void verify_one(struct repository *r, >> >> for (i = 0; i < it->subtree_nr; i++) { >> strbuf_addf(path, "%s/", it->down[i]->name); >> - verify_one(r, istate, it->down[i]->cache_tree, path); >> + if (verify_one(r, istate, it->down[i]->cache_tree, path)) >> + return 1; >> strbuf_setlen(path, len); >> } >> >> if (it->entry_count < 0 || >> /* no verification on tests (t7003) that replace trees */ >> lookup_replace_object(r, &it->oid) != &it->oid) >> - return; >> + return 0; >> >> if (path->len) { >> + /* >> + * If the index is sparse index_name_pos() may trigger >> + * ensure_full_index() which will free the tree that is being >> + * verified. >> + */ >> + int is_sparse = istate->sparse_index; >> pos = index_name_pos(istate, path->buf, path->len); >> + if (is_sparse && !istate->sparse_index) >> + return 1; > > I think this guard is good to have, even if we fix prime_cache_tree() to > avoid triggering expansion here in most cases. > >> if (pos >= 0) { >> verify_one_sparse(r, istate, it, path, pos); >> - return; >> + return 0; >> } >> >> pos = -pos - 1; >> @@ -899,6 +908,7 @@ static void verify_one(struct repository *r, >> oid_to_hex(&new_oid), oid_to_hex(&it->oid)); >> strbuf_setlen(path, len); >> strbuf_release(&tree_buf); >> + return 0; >> } >> >> void cache_tree_verify(struct repository *r, struct index_state *istate) >> @@ -907,6 +917,9 @@ void cache_tree_verify(struct repository *r, struct index_state *istate) >> >> if (!istate->cache_tree) >> return; >> - verify_one(r, istate, istate->cache_tree, &path); >> + if (verify_one(r, istate, istate->cache_tree, &path)) { >> + strbuf_reset(&path); >> + verify_one(r, istate, istate->cache_tree, &path); >> + } > > And this limits us to doing at most two passes. Good. In theory ensure_full_index() will only ever be called once but I wanted to make sure we could not get into an infinite loop. >> test_expect_success 'merge, cherry-pick, and rebase' ' >> init_repos && >> >> - for OPERATION in "merge -m merge" cherry-pick rebase >> + for OPERATION in "merge -m merge" cherry-pick "rebase --apply" "rebase --merge" > > Thank you for the additional test! Thanks for your explanation and looking at the patch Best Wishes Phillip > Thanks, > -Stolee >
On 10/6/21 10:01 AM, Phillip Wood wrote: > Hi Stolee > > On 06/10/2021 12:20, Derrick Stolee wrote: >> In particular, prime_cache_tree_rec() does not stop at the sparse-checkout >> cone, so the cache tree is the full size at that point. >> >> When the verify_one() method reaches these nodes that are outside of the >> cone, index_name_pos() triggers the index expansion in a way that the >> cache-tree that is restricted to the sparse-checkout cone does not. >> >> Hopefully that helps clear up _why_ this happens. > > It does thanks - we end up with a full cache tree but a sparse index That's a short-and-sweet way to describe it. >> There is a remaining issue that "git rebase --apply" will be a lot slower >> than "git rebase --merge" because of this construction of a cache-tree >> that is much larger than necessary. >> >> I will make note of this as a potential improvement for the future. > > I think I'm going to remove the call to prime_cache_tree(). Correct me if I'm wrong but as I understand it unpack_trees() updates the cache tree so the call to prime_cache_tree() is not needed (I think it was copied from builtin/rebase.c which does need to call prime_cache_tree() if it has updated a few paths rather than the whole top-level tree). In any case I've just noticed that one of Victoria's patches[1] looks like it fixes prime_cache_tree() with a sparse index. > > [1] https://lore.kernel.org/git/78cd85d8dcc790251ce8235e649902cf6adf091a.1633440057.git.gitgitgadget@gmail.com/ Of course it does! I'm losing track of all the ongoing work in the sparse index as I've been distracted and out of it for a while. It's in good hands. Thanks, -Stolee
"Phillip Wood via GitGitGadget" <gitgitgadget@gmail.com> writes: /* * Please document what the values that can be returned from * this function are and what they mean, just before this * funciton. I am guessing that this is "all bets are off and * you need to redo the computation again over the full in-core * index"? It is not an error and I think it makes sense to use * positive 1 like this patch does instead of -1. */ > > -static void verify_one(struct repository *r, > - struct index_state *istate, > - struct cache_tree *it, > - struct strbuf *path) > +static int verify_one(struct repository *r, > + struct index_state *istate, > + struct cache_tree *it, > + struct strbuf *path) > { > @@ -907,6 +917,9 @@ void cache_tree_verify(struct repository *r, struct index_state *istate) > > if (!istate->cache_tree) > return; > - verify_one(r, istate, istate->cache_tree, &path); > + if (verify_one(r, istate, istate->cache_tree, &path)) { > + strbuf_reset(&path); > + verify_one(r, istate, istate->cache_tree, &path); > + } > strbuf_release(&path); > } This is just a style thing, but I would find it easier to follow if it just recursed into itself, i.e. - verify_one(...); + if (verify_one(...)) + cache_tree_verify(r, istate); or - verify_one(...); + again: + if (verify_one(...)) + strbuf_reset(&path); + goto again; } } On the other hand, if the new code wants to say "I would retry at most once, otherwise there is something wrong in me", then > - verify_one(r, istate, istate->cache_tree, &path); > + if (verify_one(r, istate, istate->cache_tree, &path)) { > + strbuf_reset(&path); > + if (verify_one(r, istate, istate->cache_tree, &path)) > + BUG("..."); > + } would be better. Other than that, nicely done. > diff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh > index 886e78715fe..85d5279b33c 100755 > --- a/t/t1092-sparse-checkout-compatibility.sh > +++ b/t/t1092-sparse-checkout-compatibility.sh > @@ -484,7 +484,7 @@ test_expect_success 'checkout and reset (mixed) [sparse]' ' > test_expect_success 'merge, cherry-pick, and rebase' ' > init_repos && > > - for OPERATION in "merge -m merge" cherry-pick rebase > + for OPERATION in "merge -m merge" cherry-pick "rebase --apply" "rebase --merge" > do > test_all_match git checkout -B temp update-deep && > test_all_match git $OPERATION update-folder1 && > > base-commit: cefe983a320c03d7843ac78e73bd513a27806845
On 10/6/2021 3:17 PM, Junio C Hamano wrote: > "Phillip Wood via GitGitGadget" <gitgitgadget@gmail.com> writes: >> @@ -907,6 +917,9 @@ void cache_tree_verify(struct repository *r, struct index_state *istate) >> >> if (!istate->cache_tree) >> return; >> - verify_one(r, istate, istate->cache_tree, &path); >> + if (verify_one(r, istate, istate->cache_tree, &path)) { >> + strbuf_reset(&path); >> + verify_one(r, istate, istate->cache_tree, &path); >> + } >> strbuf_release(&path); >> } > > This is just a style thing, but I would find it easier to follow if > it just recursed into itself, i.e. > > - verify_one(...); > + if (verify_one(...)) > + cache_tree_verify(r, istate); > > or > > - verify_one(...); > + again: > + if (verify_one(...)) > + strbuf_reset(&path); > + goto again; > } } > > On the other hand, if the new code wants to say "I would retry at > most once, otherwise there is something wrong in me", then > >> - verify_one(r, istate, istate->cache_tree, &path); >> + if (verify_one(r, istate, istate->cache_tree, &path)) { >> + strbuf_reset(&path); >> + if (verify_one(r, istate, istate->cache_tree, &path)) >> + BUG("..."); >> + } > > would be better. I'm in favor of this second option. Thanks, -Stolee
diff --git a/cache-tree.c b/cache-tree.c index 90919f9e345..7bdbbc24268 100644 --- a/cache-tree.c +++ b/cache-tree.c @@ -826,10 +826,10 @@ static void verify_one_sparse(struct repository *r, path->buf); } -static void verify_one(struct repository *r, - struct index_state *istate, - struct cache_tree *it, - struct strbuf *path) +static int verify_one(struct repository *r, + struct index_state *istate, + struct cache_tree *it, + struct strbuf *path) { int i, pos, len = path->len; struct strbuf tree_buf = STRBUF_INIT; @@ -837,21 +837,30 @@ static void verify_one(struct repository *r, for (i = 0; i < it->subtree_nr; i++) { strbuf_addf(path, "%s/", it->down[i]->name); - verify_one(r, istate, it->down[i]->cache_tree, path); + if (verify_one(r, istate, it->down[i]->cache_tree, path)) + return 1; strbuf_setlen(path, len); } if (it->entry_count < 0 || /* no verification on tests (t7003) that replace trees */ lookup_replace_object(r, &it->oid) != &it->oid) - return; + return 0; if (path->len) { + /* + * If the index is sparse index_name_pos() may trigger + * ensure_full_index() which will free the tree that is being + * verified. + */ + int is_sparse = istate->sparse_index; pos = index_name_pos(istate, path->buf, path->len); + if (is_sparse && !istate->sparse_index) + return 1; if (pos >= 0) { verify_one_sparse(r, istate, it, path, pos); - return; + return 0; } pos = -pos - 1; @@ -899,6 +908,7 @@ static void verify_one(struct repository *r, oid_to_hex(&new_oid), oid_to_hex(&it->oid)); strbuf_setlen(path, len); strbuf_release(&tree_buf); + return 0; } void cache_tree_verify(struct repository *r, struct index_state *istate) @@ -907,6 +917,9 @@ void cache_tree_verify(struct repository *r, struct index_state *istate) if (!istate->cache_tree) return; - verify_one(r, istate, istate->cache_tree, &path); + if (verify_one(r, istate, istate->cache_tree, &path)) { + strbuf_reset(&path); + verify_one(r, istate, istate->cache_tree, &path); + } strbuf_release(&path); } diff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh index 886e78715fe..85d5279b33c 100755 --- a/t/t1092-sparse-checkout-compatibility.sh +++ b/t/t1092-sparse-checkout-compatibility.sh @@ -484,7 +484,7 @@ test_expect_success 'checkout and reset (mixed) [sparse]' ' test_expect_success 'merge, cherry-pick, and rebase' ' init_repos && - for OPERATION in "merge -m merge" cherry-pick rebase + for OPERATION in "merge -m merge" cherry-pick "rebase --apply" "rebase --merge" do test_all_match git checkout -B temp update-deep && test_all_match git $OPERATION update-folder1 &&