{"thread":{"id":"56652","subject":"[PATCH] [RFC] sparse index: fix use-after-free bug in cache_tree_verify()","startedAt":"2021-10-06T09:29:56Z","lastAt":"2021-10-18T09:37:34Z","messageCount":26,"participants":["Phillip Wood via GitGitGadget","Derrick Stolee","Phillip Wood","Junio C Hamano","Bagas Sanjaya"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"438028","messageId":"pull.1053.git.1633512591608.gitgitgadget@gmail.com","threadId":"56652","inReplyTo":null,"subject":"[PATCH] [RFC] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Phillip Wood via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-10-06T09:29:51Z","receivedAt":"2021-10-06T09:29:56Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"From: Phillip Wood \n\nIn a sparse index it is possible for the tree that is being verified\nto be freed while it is being verified. This happens when\nindex_name_pos() looks up a entry that is missing from the index and\nthat would be a descendant of a sparse entry. That triggers a call to\nensure_full_index() which frees the cache tree that is being verified.\nCarrying on trying to verify the tree after this results in a\nuse-after-free bug. Instead restart the verification if a sparse index\nis converted to a full index. This bug is triggered by a call to\nreset_head() in \"git rebase --apply\". Thanks to René Scharfe for his\nhelp analyzing the problem.\n\n==74345==ERROR: AddressSanitizer: heap-use-after-free on address 0x606000001b20 at pc 0x557cbe82d3a2 bp 0x7ffdfee08090 sp 0x7ffdfee08080\nREAD of size 4 at 0x606000001b20 thread T0\n #0 0x557cbe82d3a1 in verify_one /home/phil/src/git/cache-tree.c:863\n #1 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #2 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #3 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #4 0x557cbe830a2b in cache_tree_verify /home/phil/src/git/cache-tree.c:910\n #5 0x557cbea53741 in write_locked_index /home/phil/src/git/read-cache.c:3250\n #6 0x557cbeab7fdd in reset_head /home/phil/src/git/reset.c:87\n #7 0x557cbe72147f in cmd_rebase builtin/rebase.c:2074\n #8 0x557cbe5bd151 in run_builtin /home/phil/src/git/git.c:461\n #9 0x557cbe5bd151 in handle_builtin /home/phil/src/git/git.c:714\n #10 0x557cbe5c0503 in run_argv /home/phil/src/git/git.c:781\n #11 0x557cbe5c0503 in cmd_main /home/phil/src/git/git.c:912\n #12 0x557cbe5bad28 in main /home/phil/src/git/common-main.c:52\n #13 0x7fdd4b82eb24 in __libc_start_main (/usr/lib/libc.so.6+0x27b24)\n #14 0x557cbe5bcb8d in _start (/home/phil/src/git/git+0x1b9b8d)\n\n0x606000001b20 is located 0 bytes inside of 56-byte region [0x606000001b20,0x606000001b58)\nfreed by thread T0 here:\n #0 0x7fdd4bacff19 in __interceptor_free /build/gcc/src/gcc/libsanitizer/asan/asan_malloc_linux.cpp:127\n #1 0x557cbe82af60 in cache_tree_free /home/phil/src/git/cache-tree.c:35\n #2 0x557cbe82aee5 in cache_tree_free /home/phil/src/git/cache-tree.c:31\n #3 0x557cbe82aee5 in cache_tree_free /home/phil/src/git/cache-tree.c:31\n #4 0x557cbe82aee5 in cache_tree_free /home/phil/src/git/cache-tree.c:31\n #5 0x557cbeb2557a in ensure_full_index /home/phil/src/git/sparse-index.c:310\n #6 0x557cbea45c4a in index_name_stage_pos /home/phil/src/git/read-cache.c:588\n #7 0x557cbe82ce37 in verify_one /home/phil/src/git/cache-tree.c:850\n #8 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #9 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #10 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #11 0x557cbe830a2b in cache_tree_verify /home/phil/src/git/cache-tree.c:910\n #12 0x557cbea53741 in write_locked_index /home/phil/src/git/read-cache.c:3250\n #13 0x557cbeab7fdd in reset_head /home/phil/src/git/reset.c:87\n #14 0x557cbe72147f in cmd_rebase builtin/rebase.c:2074\n #15 0x557cbe5bd151 in run_builtin /home/phil/src/git/git.c:461\n #16 0x557cbe5bd151 in handle_builtin /home/phil/src/git/git.c:714\n #17 0x557cbe5c0503 in run_argv /home/phil/src/git/git.c:781\n #18 0x557cbe5c0503 in cmd_main /home/phil/src/git/git.c:912\n #19 0x557cbe5bad28 in main /home/phil/src/git/common-main.c:52\n #20 0x7fdd4b82eb24 in __libc_start_main (/usr/lib/libc.so.6+0x27b24)\n\npreviously allocated by thread T0 here:\n #0 0x7fdd4bad0459 in __interceptor_calloc /build/gcc/src/gcc/libsanitizer/asan/asan_malloc_linux.cpp:154\n #1 0x557cbebc1807 in xcalloc /home/phil/src/git/wrapper.c:140\n #2 0x557cbe82b7d8 in cache_tree /home/phil/src/git/cache-tree.c:17\n #3 0x557cbe82b7d8 in prime_cache_tree_rec /home/phil/src/git/cache-tree.c:763\n #4 0x557cbe82b837 in prime_cache_tree_rec /home/phil/src/git/cache-tree.c:764\n #5 0x557cbe82b837 in prime_cache_tree_rec /home/phil/src/git/cache-tree.c:764\n #6 0x557cbe8304e1 in prime_cache_tree /home/phil/src/git/cache-tree.c:779\n #7 0x557cbeab7fa7 in reset_head /home/phil/src/git/reset.c:85\n #8 0x557cbe72147f in cmd_rebase builtin/rebase.c:2074\n #9 0x557cbe5bd151 in run_builtin /home/phil/src/git/git.c:461\n #10 0x557cbe5bd151 in handle_builtin /home/phil/src/git/git.c:714\n #11 0x557cbe5c0503 in run_argv /home/phil/src/git/git.c:781\n #12 0x557cbe5c0503 in cmd_main /home/phil/src/git/git.c:912\n #13 0x557cbe5bad28 in main /home/phil/src/git/common-main.c:52\n #14 0x7fdd4b82eb24 in __libc_start_main (/usr/lib/libc.so.6+0x27b24)\n\nSigned-off-by: Phillip Wood \n---\n [RFC] sparse index: fix use-after-free bug in cache_tree_verify()\n \n In a sparse index it is possible for the tree that is being verified to\n be freed while it is being verified. This is an RFC as I'm not familiar\n with the cache tree code. I'm confused as to why this bug is triggered\n by the sequence\n \n unpack_trees()\n prime_cache_tree()\n write_locked_index()\n \n \n but not\n \n unpack_trees()\n write_locked_index()\n \n \n as unpack_trees() appears to update the cache tree with\n \n if (!cache_tree_fully_valid(o->result.cache_tree))\n cache_tree_update(&o->result,\n WRITE_TREE_SILENT |\n WRITE_TREE_REPAIR);\n \n \n and I don't understand why the cache tree from prime_cache_tree()\n results in different behavior. It concerns me that this fix is hiding\n another bug.\n \n Best Wishes\n \n Phillip\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1053%2Fphillipwood%2Fwip%2Fsparse-index-fix-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1053/phillipwood/wip/sparse-index-fix-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/1053\n\n cache-tree.c | 29 +++++++++++++++++-------\n t/t1092-sparse-checkout-compatibility.sh | 2 +-\n 2 files changed, 22 insertions(+), 9 deletions(-)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 90919f9e345..7bdbbc24268 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -826,10 +826,10 @@ static void verify_one_sparse(struct repository *r,\n \t\t path->buf);\n }\n \n-static void verify_one(struct repository *r,\n-\t\t struct index_state *istate,\n-\t\t struct cache_tree *it,\n-\t\t struct strbuf *path)\n+static int verify_one(struct repository *r,\n+\t\t struct index_state *istate,\n+\t\t struct cache_tree *it,\n+\t\t struct strbuf *path)\n {\n \tint i, pos, len = path->len;\n \tstruct strbuf tree_buf = STRBUF_INIT;\n@@ -837,21 +837,30 @@ static void verify_one(struct repository *r,\n \n \tfor (i = 0; i < it->subtree_nr; i++) {\n \t\tstrbuf_addf(path, \"%s/\", it->down[i]->name);\n-\t\tverify_one(r, istate, it->down[i]->cache_tree, path);\n+\t\tif (verify_one(r, istate, it->down[i]->cache_tree, path))\n+\t\t\treturn 1;\n \t\tstrbuf_setlen(path, len);\n \t}\n \n \tif (it->entry_count < 0 ||\n \t /* no verification on tests (t7003) that replace trees */\n \t lookup_replace_object(r, &it->oid) != &it->oid)\n-\t\treturn;\n+\t\treturn 0;\n \n \tif (path->len) {\n+\t\t/*\n+\t\t * If the index is sparse index_name_pos() may trigger\n+\t\t * ensure_full_index() which will free the tree that is being\n+\t\t * verified.\n+\t\t */\n+\t\tint is_sparse = istate->sparse_index;\n \t\tpos = index_name_pos(istate, path->buf, path->len);\n+\t\tif (is_sparse && !istate->sparse_index)\n+\t\t\treturn 1;\n \n \t\tif (pos >= 0) {\n \t\t\tverify_one_sparse(r, istate, it, path, pos);\n-\t\t\treturn;\n+\t\t\treturn 0;\n \t\t}\n \n \t\tpos = -pos - 1;\n@@ -899,6 +908,7 @@ static void verify_one(struct repository *r,\n \t\t oid_to_hex(&new_oid), oid_to_hex(&it->oid));\n \tstrbuf_setlen(path, len);\n \tstrbuf_release(&tree_buf);\n+\treturn 0;\n }\n \n void cache_tree_verify(struct repository *r, struct index_state *istate)\n@@ -907,6 +917,9 @@ void cache_tree_verify(struct repository *r, struct index_state *istate)\n \n \tif (!istate->cache_tree)\n \t\treturn;\n-\tverify_one(r, istate, istate->cache_tree, &path);\n+\tif (verify_one(r, istate, istate->cache_tree, &path)) {\n+\t\tstrbuf_reset(&path);\n+\t\tverify_one(r, istate, istate->cache_tree, &path);\n+\t}\n \tstrbuf_release(&path);\n }\ndiff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\nindex 886e78715fe..85d5279b33c 100755\n--- a/t/t1092-sparse-checkout-compatibility.sh\n+++ b/t/t1092-sparse-checkout-compatibility.sh\n@@ -484,7 +484,7 @@ test_expect_success 'checkout and reset (mixed) [sparse]' '\n test_expect_success 'merge, cherry-pick, and rebase' '\n \tinit_repos &&\n \n-\tfor OPERATION in \"merge -m merge\" cherry-pick rebase\n+\tfor OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply\" \"rebase --merge\"\n \tdo\n \t\ttest_all_match git checkout -B temp update-deep &&\n \t\ttest_all_match git $OPERATION update-folder1 &&\n\nbase-commit: cefe983a320c03d7843ac78e73bd513a27806845\n-- \ngitgitgadget\n"},{"id":"438059","messageId":"2b1f0e56-5bb4-7f41-5a1e-d8a21096084a@gmail.com","threadId":"56652","inReplyTo":"pull.1053.git.1633512591608.gitgitgadget@gmail.com","subject":"Re: [PATCH] [RFC] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-10-06T11:20:19Z","receivedAt":"2021-10-06T11:20:25Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/6/2021 5:29 AM, Phillip Wood via GitGitGadget wrote:\n> From: Phillip Wood \n> \n> In a sparse index it is possible for the tree that is being verified\n> to be freed while it is being verified. This happens when\n> index_name_pos() looks up a entry that is missing from the index and\n> that would be a descendant of a sparse entry. That triggers a call to\n> ensure_full_index() which frees the cache tree that is being verified.\n> Carrying on trying to verify the tree after this results in a\n> use-after-free bug. Instead restart the verification if a sparse index\n> is converted to a full index. This bug is triggered by a call to\n> reset_head() in \"git rebase --apply\". Thanks to René Scharfe for his\n> help analyzing the problem.\n\nThank you for identifying an interesting case! I hadn't thought to\nchange the mode from --merge to --apply.\n\n> In a sparse index it is possible for the tree that is being verified to\n> be freed while it is being verified. This is an RFC as I'm not familiar\n> with the cache tree code. I'm confused as to why this bug is triggered\n> by the sequence\n> \n> unpack_trees()\n> prime_cache_tree()\n> write_locked_index()\n> \n> but not\n> \n> unpack_trees()\n> write_locked_index()\n> \n> \n> as unpack_trees() appears to update the cache tree with\n> \n> if (!cache_tree_fully_valid(o->result.cache_tree))\n> cache_tree_update(&o->result,\n> WRITE_TREE_SILENT |\n> WRITE_TREE_REPAIR);\n> \n> \n> and I don't understand why the cache tree from prime_cache_tree()\n> results in different behavior. It concerns me that this fix is hiding\n> another bug.\n\nprime_cache_tree() appears to clear the cache tree and start from scratch\nfrom a tree object instead of using the index.\n\nIn particular, prime_cache_tree_rec() does not stop at the sparse-checkout\ncone, so the cache tree is the full size at that point.\n\nWhen the verify_one() method reaches these nodes that are outside of the\ncone, index_name_pos() triggers the index expansion in a way that the\ncache-tree that is restricted to the sparse-checkout cone does not.\n\nHopefully that helps clear up _why_ this happens.\n\nThere is a remaining issue that \"git rebase --apply\" will be a lot slower\nthan \"git rebase --merge\" because of this construction of a cache-tree\nthat is much larger than necessary.\n\nI will make note of this as a potential improvement for the future.\n\n> -static void verify_one(struct repository *r,\n> -\t\t struct index_state *istate,\n> -\t\t struct cache_tree *it,\n> -\t\t struct strbuf *path)\n> +static int verify_one(struct repository *r,\n> +\t\t struct index_state *istate,\n> +\t\t struct cache_tree *it,\n> +\t\t struct strbuf *path)\n> {\n> \tint i, pos, len = path->len;\n> \tstruct strbuf tree_buf = STRBUF_INIT;\n> @@ -837,21 +837,30 @@ static void verify_one(struct repository *r,\n> \n> \tfor (i = 0; i < it->subtree_nr; i++) {\n> \t\tstrbuf_addf(path, \"%s/\", it->down[i]->name);\n> -\t\tverify_one(r, istate, it->down[i]->cache_tree, path);\n> +\t\tif (verify_one(r, istate, it->down[i]->cache_tree, path))\n> +\t\t\treturn 1;\n> \t\tstrbuf_setlen(path, len);\n> \t}\n> \n> \tif (it->entry_count < 0 ||\n> \t /* no verification on tests (t7003) that replace trees */\n> \t lookup_replace_object(r, &it->oid) != &it->oid)\n> -\t\treturn;\n> +\t\treturn 0;\n> \n> \tif (path->len) {\n> +\t\t/*\n> +\t\t * If the index is sparse index_name_pos() may trigger\n> +\t\t * ensure_full_index() which will free the tree that is being\n> +\t\t * verified.\n> +\t\t */\n> +\t\tint is_sparse = istate->sparse_index;\n> \t\tpos = index_name_pos(istate, path->buf, path->len);\n> +\t\tif (is_sparse && !istate->sparse_index)\n> +\t\t\treturn 1;\n\nI think this guard is good to have, even if we fix prime_cache_tree() to\navoid triggering expansion here in most cases.\n\n> \t\tif (pos >= 0) {\n> \t\t\tverify_one_sparse(r, istate, it, path, pos);\n> -\t\t\treturn;\n> +\t\t\treturn 0;\n> \t\t}\n> \n> \t\tpos = -pos - 1;\n> @@ -899,6 +908,7 @@ static void verify_one(struct repository *r,\n> \t\t oid_to_hex(&new_oid), oid_to_hex(&it->oid));\n> \tstrbuf_setlen(path, len);\n> \tstrbuf_release(&tree_buf);\n> +\treturn 0;\n> }\n> \n> void cache_tree_verify(struct repository *r, struct index_state *istate)\n> @@ -907,6 +917,9 @@ void cache_tree_verify(struct repository *r, struct index_state *istate)\n> \n> \tif (!istate->cache_tree)\n> \t\treturn;\n> -\tverify_one(r, istate, istate->cache_tree, &path);\n> +\tif (verify_one(r, istate, istate->cache_tree, &path)) {\n> +\t\tstrbuf_reset(&path);\n> +\t\tverify_one(r, istate, istate->cache_tree, &path);\n> +\t}\n\nAnd this limits us to doing at most two passes. Good.\n\n> test_expect_success 'merge, cherry-pick, and rebase' '\n> \tinit_repos &&\n> \n> -\tfor OPERATION in \"merge -m merge\" cherry-pick rebase\n> +\tfor OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply\" \"rebase --merge\"\n\nThank you for the additional test!\n\nThanks,\n-Stolee\n"},{"id":"438065","messageId":"cfd6f82d-01c3-d6be-a535-76255e599c89@gmail.com","threadId":"56652","inReplyTo":"2b1f0e56-5bb4-7f41-5a1e-d8a21096084a@gmail.com","subject":"Re: [PATCH] [RFC] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2021-10-06T14:01:18Z","receivedAt":"2021-10-06T14:01:24Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Hi Stolee\n\nOn 06/10/2021 12:20, Derrick Stolee wrote:\n> On 10/6/2021 5:29 AM, Phillip Wood via GitGitGadget wrote:\n>> From: Phillip Wood \n>>\n>> In a sparse index it is possible for the tree that is being verified\n>> to be freed while it is being verified. This happens when\n>> index_name_pos() looks up a entry that is missing from the index and\n>> that would be a descendant of a sparse entry. That triggers a call to\n>> ensure_full_index() which frees the cache tree that is being verified.\n>> Carrying on trying to verify the tree after this results in a\n>> use-after-free bug. Instead restart the verification if a sparse index\n>> is converted to a full index. This bug is triggered by a call to\n>> reset_head() in \"git rebase --apply\". Thanks to René Scharfe for his\n>> help analyzing the problem.\n> \n> Thank you for identifying an interesting case! I hadn't thought to\n> change the mode from --merge to --apply.\n\nThanks, I can't really take much credit for that though - Junio pointed \nout that my patch converting the merge based rebase to use the same \ncheckout code as the apply based rebase broke a test in seen and René \ndiagnosed the problem.\n\n>> In a sparse index it is possible for the tree that is being verified to\n>> be freed while it is being verified. This is an RFC as I'm not familiar\n>> with the cache tree code. I'm confused as to why this bug is triggered\n>> by the sequence\n>> \n>> unpack_trees()\n>> prime_cache_tree()\n>> write_locked_index()\n>> \n>> but not\n>> \n>> unpack_trees()\n>> write_locked_index()\n>> \n>> \n>> as unpack_trees() appears to update the cache tree with\n>> \n>> if (!cache_tree_fully_valid(o->result.cache_tree))\n>> cache_tree_update(&o->result,\n>> WRITE_TREE_SILENT |\n>> WRITE_TREE_REPAIR);\n>> \n>> \n>> and I don't understand why the cache tree from prime_cache_tree()\n>> results in different behavior. It concerns me that this fix is hiding\n>> another bug.\n> \n> prime_cache_tree() appears to clear the cache tree and start from scratch\n> from a tree object instead of using the index.\n> \n> In particular, prime_cache_tree_rec() does not stop at the sparse-checkout\n> cone, so the cache tree is the full size at that point.\n> \n> When the verify_one() method reaches these nodes that are outside of the\n> cone, index_name_pos() triggers the index expansion in a way that the\n> cache-tree that is restricted to the sparse-checkout cone does not.\n> \n> Hopefully that helps clear up _why_ this happens.\n\nIt does thanks - we end up with a full cache tree but a sparse index\n\n> There is a remaining issue that \"git rebase --apply\" will be a lot slower\n> than \"git rebase --merge\" because of this construction of a cache-tree\n> that is much larger than necessary.\n> \n> I will make note of this as a potential improvement for the future.\n\nI think I'm going to remove the call to prime_cache_tree(). Correct me \nif I'm wrong but as I understand it unpack_trees() updates the cache \ntree so the call to prime_cache_tree() is not needed (I think it was \ncopied from builtin/rebase.c which does need to call prime_cache_tree() \nif it has updated a few paths rather than the whole top-level tree). In \nany case I've just noticed that one of Victoria's patches[1] looks like \nit fixes prime_cache_tree() with a sparse index.\n\n[1] \nhttps://lore.kernel.org/git/78cd85d8dcc790251ce8235e649902cf6adf091a.1633440057.git.gitgitgadget@gmail.com/\n\n>> -static void verify_one(struct repository *r,\n>> -\t\t struct index_state *istate,\n>> -\t\t struct cache_tree *it,\n>> -\t\t struct strbuf *path)\n>> +static int verify_one(struct repository *r,\n>> +\t\t struct index_state *istate,\n>> +\t\t struct cache_tree *it,\n>> +\t\t struct strbuf *path)\n>> {\n>> \tint i, pos, len = path->len;\n>> \tstruct strbuf tree_buf = STRBUF_INIT;\n>> @@ -837,21 +837,30 @@ static void verify_one(struct repository *r,\n>> \n>> \tfor (i = 0; i < it->subtree_nr; i++) {\n>> \t\tstrbuf_addf(path, \"%s/\", it->down[i]->name);\n>> -\t\tverify_one(r, istate, it->down[i]->cache_tree, path);\n>> +\t\tif (verify_one(r, istate, it->down[i]->cache_tree, path))\n>> +\t\t\treturn 1;\n>> \t\tstrbuf_setlen(path, len);\n>> \t}\n>> \n>> \tif (it->entry_count < 0 ||\n>> \t /* no verification on tests (t7003) that replace trees */\n>> \t lookup_replace_object(r, &it->oid) != &it->oid)\n>> -\t\treturn;\n>> +\t\treturn 0;\n>> \n>> \tif (path->len) {\n>> +\t\t/*\n>> +\t\t * If the index is sparse index_name_pos() may trigger\n>> +\t\t * ensure_full_index() which will free the tree that is being\n>> +\t\t * verified.\n>> +\t\t */\n>> +\t\tint is_sparse = istate->sparse_index;\n>> \t\tpos = index_name_pos(istate, path->buf, path->len);\n>> +\t\tif (is_sparse && !istate->sparse_index)\n>> +\t\t\treturn 1;\n> \n> I think this guard is good to have, even if we fix prime_cache_tree() to\n> avoid triggering expansion here in most cases.\n> \n>> \t\tif (pos >= 0) {\n>> \t\t\tverify_one_sparse(r, istate, it, path, pos);\n>> -\t\t\treturn;\n>> +\t\t\treturn 0;\n>> \t\t}\n>> \n>> \t\tpos = -pos - 1;\n>> @@ -899,6 +908,7 @@ static void verify_one(struct repository *r,\n>> \t\t oid_to_hex(&new_oid), oid_to_hex(&it->oid));\n>> \tstrbuf_setlen(path, len);\n>> \tstrbuf_release(&tree_buf);\n>> +\treturn 0;\n>> }\n>> \n>> void cache_tree_verify(struct repository *r, struct index_state *istate)\n>> @@ -907,6 +917,9 @@ void cache_tree_verify(struct repository *r, struct index_state *istate)\n>> \n>> \tif (!istate->cache_tree)\n>> \t\treturn;\n>> -\tverify_one(r, istate, istate->cache_tree, &path);\n>> +\tif (verify_one(r, istate, istate->cache_tree, &path)) {\n>> +\t\tstrbuf_reset(&path);\n>> +\t\tverify_one(r, istate, istate->cache_tree, &path);\n>> +\t}\n> \n> And this limits us to doing at most two passes. Good.\n\nIn theory ensure_full_index() will only ever be called once but I wanted \nto make sure we could not get into an infinite loop.\n\n>> test_expect_success 'merge, cherry-pick, and rebase' '\n>> \tinit_repos &&\n>> \n>> -\tfor OPERATION in \"merge -m merge\" cherry-pick rebase\n>> +\tfor OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply\" \"rebase --merge\"\n> \n> Thank you for the additional test!\n\nThanks for your explanation and looking at the patch\n\nBest Wishes\n\nPhillip\n\n> Thanks,\n> -Stolee\n> \n"},{"id":"438068","messageId":"96320021-66dc-966f-2222-25d308247596@gmail.com","threadId":"56652","inReplyTo":"cfd6f82d-01c3-d6be-a535-76255e599c89@gmail.com","subject":"Re: [PATCH] [RFC] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-10-06T14:19:41Z","receivedAt":"2021-10-06T14:19:49Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/6/21 10:01 AM, Phillip Wood wrote:\n> Hi Stolee\n> \n> On 06/10/2021 12:20, Derrick Stolee wrote:\n>> In particular, prime_cache_tree_rec() does not stop at the sparse-checkout\n>> cone, so the cache tree is the full size at that point.\n>>\n>> When the verify_one() method reaches these nodes that are outside of the\n>> cone, index_name_pos() triggers the index expansion in a way that the\n>> cache-tree that is restricted to the sparse-checkout cone does not.\n>>\n>> Hopefully that helps clear up _why_ this happens.\n> \n> It does thanks - we end up with a full cache tree but a sparse index\n\nThat's a short-and-sweet way to describe it.\n\n>> There is a remaining issue that \"git rebase --apply\" will be a lot slower\n>> than \"git rebase --merge\" because of this construction of a cache-tree\n>> that is much larger than necessary.\n>>\n>> I will make note of this as a potential improvement for the future.\n> \n> 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.\n> \n> [1] https://lore.kernel.org/git/78cd85d8dcc790251ce8235e649902cf6adf091a.1633440057.git.gitgitgadget@gmail.com/\n\nOf course it does! I'm losing track of all the ongoing work in\nthe sparse index as I've been distracted and out of it for a\nwhile. It's in good hands.\n\nThanks,\n-Stolee\n"},{"id":"438087","messageId":"xmqq1r4yrmhp.fsf@gitster.g","threadId":"56652","inReplyTo":"pull.1053.git.1633512591608.gitgitgadget@gmail.com","subject":"Re: [PATCH] [RFC] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-10-06T19:17:54Z","receivedAt":"2021-10-06T19:18:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Phillip Wood via GitGitGadget\" writes:\n\n/*\n * Please document what the values that can be returned from\n * this function are and what they mean, just before this\n * funciton. I am guessing that this is \"all bets are off and\n * you need to redo the computation again over the full in-core\n * index\"? It is not an error and I think it makes sense to use\n * positive 1 like this patch does instead of -1.\n */\n> \n> -static void verify_one(struct repository *r,\n> -\t\t struct index_state *istate,\n> -\t\t struct cache_tree *it,\n> -\t\t struct strbuf *path)\n> +static int verify_one(struct repository *r,\n> +\t\t struct index_state *istate,\n> +\t\t struct cache_tree *it,\n> +\t\t struct strbuf *path)\n> {\n\n\n\n> @@ -907,6 +917,9 @@ void cache_tree_verify(struct repository *r, struct index_state *istate)\n> \n> \tif (!istate->cache_tree)\n> \t\treturn;\n> -\tverify_one(r, istate, istate->cache_tree, &path);\n> +\tif (verify_one(r, istate, istate->cache_tree, &path)) {\n> +\t\tstrbuf_reset(&path);\n> +\t\tverify_one(r, istate, istate->cache_tree, &path);\n> +\t}\n> \tstrbuf_release(&path);\n> }\n\nThis is just a style thing, but I would find it easier to follow if\nit just recursed into itself, i.e.\n\n-\tverify_one(...);\n+\tif (verify_one(...))\n+\t\tcache_tree_verify(r, istate);\n\nor\n\n-\tverify_one(...);\n+\tagain:\n+\tif (verify_one(...))\n+\t\tstrbuf_reset(&path);\n+\t\tgoto again;\n}\t}\n\nOn the other hand, if the new code wants to say \"I would retry at\nmost once, otherwise there is something wrong in me\", then\n\n> -\tverify_one(r, istate, istate->cache_tree, &path);\n> +\tif (verify_one(r, istate, istate->cache_tree, &path)) {\n> +\t\tstrbuf_reset(&path);\n> +\t\tif (verify_one(r, istate, istate->cache_tree, &path))\n> +\t\t\tBUG(\"...\");\n> +\t}\n\nwould be better.\n\nOther than that, nicely done.\n\n> diff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\n> index 886e78715fe..85d5279b33c 100755\n> --- a/t/t1092-sparse-checkout-compatibility.sh\n> +++ b/t/t1092-sparse-checkout-compatibility.sh\n> @@ -484,7 +484,7 @@ test_expect_success 'checkout and reset (mixed) [sparse]' '\n> test_expect_success 'merge, cherry-pick, and rebase' '\n> \tinit_repos &&\n> \n> -\tfor OPERATION in \"merge -m merge\" cherry-pick rebase\n> +\tfor OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply\" \"rebase --merge\"\n> \tdo\n> \t\ttest_all_match git checkout -B temp update-deep &&\n> \t\ttest_all_match git $OPERATION update-folder1 &&\n>\n> base-commit: cefe983a320c03d7843ac78e73bd513a27806845\n"},{"id":"438103","messageId":"7ef4f68c-8c32-86ea-f8a6-cd673ed281c7@gmail.com","threadId":"56652","inReplyTo":"xmqq1r4yrmhp.fsf@gitster.g","subject":"Re: [PATCH] [RFC] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-10-06T20:43:45Z","receivedAt":"2021-10-06T20:43:57Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/6/2021 3:17 PM, Junio C Hamano wrote:\n> \"Phillip Wood via GitGitGadget\" writes:\n>> @@ -907,6 +917,9 @@ void cache_tree_verify(struct repository *r, struct index_state *istate)\n>> \n>> \tif (!istate->cache_tree)\n>> \t\treturn;\n>> -\tverify_one(r, istate, istate->cache_tree, &path);\n>> +\tif (verify_one(r, istate, istate->cache_tree, &path)) {\n>> +\t\tstrbuf_reset(&path);\n>> +\t\tverify_one(r, istate, istate->cache_tree, &path);\n>> +\t}\n>> \tstrbuf_release(&path);\n>> }\n> \n> This is just a style thing, but I would find it easier to follow if\n> it just recursed into itself, i.e.\n> \n> -\tverify_one(...);\n> +\tif (verify_one(...))\n> +\t\tcache_tree_verify(r, istate);\n> \n> or\n> \n> -\tverify_one(...);\n> +\tagain:\n> +\tif (verify_one(...))\n> +\t\tstrbuf_reset(&path);\n> +\t\tgoto again;\n> }\t}\n> \n> On the other hand, if the new code wants to say \"I would retry at\n> most once, otherwise there is something wrong in me\", then\n> \n>> -\tverify_one(r, istate, istate->cache_tree, &path);\n>> +\tif (verify_one(r, istate, istate->cache_tree, &path)) {\n>> +\t\tstrbuf_reset(&path);\n>> +\t\tif (verify_one(r, istate, istate->cache_tree, &path))\n>> +\t\t\tBUG(\"...\");\n>> +\t}\n> \n> would be better.\n\nI'm in favor of this second option.\n\nThanks,\n-Stolee\n"},{"id":"438132","messageId":"pull.1053.v2.git.1633600244854.gitgitgadget@gmail.com","threadId":"56652","inReplyTo":"pull.1053.git.1633512591608.gitgitgadget@gmail.com","subject":"[PATCH v2] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Phillip Wood via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-10-07T09:50:44Z","receivedAt":"2021-10-07T09:51:05Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"From: Phillip Wood \n\nIn a sparse index it is possible for the tree that is being verified\nto be freed while it is being verified. This happens when the index is\nsparse but the cache tree is not and index_name_pos() looks up a path\nfrom the cache tree that is a descendant of a sparse index entry. That\ntriggers a call to ensure_full_index() which frees the cache tree that\nis being verified. Carrying on trying to verify the tree after this\nresults in a use-after-free bug. Instead restart the verification if a\nsparse index is converted to a full index. This bug is triggered by a\ncall to reset_head() in \"git rebase --apply\". Thanks to René Scharfe\nand Derick Stolee for their help analyzing the problem.\n\n==74345==ERROR: AddressSanitizer: heap-use-after-free on address 0x606000001b20 at pc 0x557cbe82d3a2 bp 0x7ffdfee08090 sp 0x7ffdfee08080\nREAD of size 4 at 0x606000001b20 thread T0\n #0 0x557cbe82d3a1 in verify_one /home/phil/src/git/cache-tree.c:863\n #1 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #2 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #3 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #4 0x557cbe830a2b in cache_tree_verify /home/phil/src/git/cache-tree.c:910\n #5 0x557cbea53741 in write_locked_index /home/phil/src/git/read-cache.c:3250\n #6 0x557cbeab7fdd in reset_head /home/phil/src/git/reset.c:87\n #7 0x557cbe72147f in cmd_rebase builtin/rebase.c:2074\n #8 0x557cbe5bd151 in run_builtin /home/phil/src/git/git.c:461\n #9 0x557cbe5bd151 in handle_builtin /home/phil/src/git/git.c:714\n #10 0x557cbe5c0503 in run_argv /home/phil/src/git/git.c:781\n #11 0x557cbe5c0503 in cmd_main /home/phil/src/git/git.c:912\n #12 0x557cbe5bad28 in main /home/phil/src/git/common-main.c:52\n #13 0x7fdd4b82eb24 in __libc_start_main (/usr/lib/libc.so.6+0x27b24)\n #14 0x557cbe5bcb8d in _start (/home/phil/src/git/git+0x1b9b8d)\n\n0x606000001b20 is located 0 bytes inside of 56-byte region [0x606000001b20,0x606000001b58)\nfreed by thread T0 here:\n #0 0x7fdd4bacff19 in __interceptor_free /build/gcc/src/gcc/libsanitizer/asan/asan_malloc_linux.cpp:127\n #1 0x557cbe82af60 in cache_tree_free /home/phil/src/git/cache-tree.c:35\n #2 0x557cbe82aee5 in cache_tree_free /home/phil/src/git/cache-tree.c:31\n #3 0x557cbe82aee5 in cache_tree_free /home/phil/src/git/cache-tree.c:31\n #4 0x557cbe82aee5 in cache_tree_free /home/phil/src/git/cache-tree.c:31\n #5 0x557cbeb2557a in ensure_full_index /home/phil/src/git/sparse-index.c:310\n #6 0x557cbea45c4a in index_name_stage_pos /home/phil/src/git/read-cache.c:588\n #7 0x557cbe82ce37 in verify_one /home/phil/src/git/cache-tree.c:850\n #8 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #9 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #10 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #11 0x557cbe830a2b in cache_tree_verify /home/phil/src/git/cache-tree.c:910\n #12 0x557cbea53741 in write_locked_index /home/phil/src/git/read-cache.c:3250\n #13 0x557cbeab7fdd in reset_head /home/phil/src/git/reset.c:87\n #14 0x557cbe72147f in cmd_rebase builtin/rebase.c:2074\n #15 0x557cbe5bd151 in run_builtin /home/phil/src/git/git.c:461\n #16 0x557cbe5bd151 in handle_builtin /home/phil/src/git/git.c:714\n #17 0x557cbe5c0503 in run_argv /home/phil/src/git/git.c:781\n #18 0x557cbe5c0503 in cmd_main /home/phil/src/git/git.c:912\n #19 0x557cbe5bad28 in main /home/phil/src/git/common-main.c:52\n #20 0x7fdd4b82eb24 in __libc_start_main (/usr/lib/libc.so.6+0x27b24)\n\npreviously allocated by thread T0 here:\n #0 0x7fdd4bad0459 in __interceptor_calloc /build/gcc/src/gcc/libsanitizer/asan/asan_malloc_linux.cpp:154\n #1 0x557cbebc1807 in xcalloc /home/phil/src/git/wrapper.c:140\n #2 0x557cbe82b7d8 in cache_tree /home/phil/src/git/cache-tree.c:17\n #3 0x557cbe82b7d8 in prime_cache_tree_rec /home/phil/src/git/cache-tree.c:763\n #4 0x557cbe82b837 in prime_cache_tree_rec /home/phil/src/git/cache-tree.c:764\n #5 0x557cbe82b837 in prime_cache_tree_rec /home/phil/src/git/cache-tree.c:764\n #6 0x557cbe8304e1 in prime_cache_tree /home/phil/src/git/cache-tree.c:779\n #7 0x557cbeab7fa7 in reset_head /home/phil/src/git/reset.c:85\n #8 0x557cbe72147f in cmd_rebase builtin/rebase.c:2074\n #9 0x557cbe5bd151 in run_builtin /home/phil/src/git/git.c:461\n #10 0x557cbe5bd151 in handle_builtin /home/phil/src/git/git.c:714\n #11 0x557cbe5c0503 in run_argv /home/phil/src/git/git.c:781\n #12 0x557cbe5c0503 in cmd_main /home/phil/src/git/git.c:912\n #13 0x557cbe5bad28 in main /home/phil/src/git/common-main.c:52\n #14 0x7fdd4b82eb24 in __libc_start_main (/usr/lib/libc.so.6+0x27b24)\n\nSigned-off-by: Phillip Wood \n---\n [RFC] sparse index: fix use-after-free bug in cache_tree_verify()\n \n Thanks for the feedback and help, here are the changes from the RFC\n \n * Updated commit message and comments to make it clear this is\n triggered by a sparse index with a full cache tree based on Stolee's\n explanation.\n * Added a comment and BUG() suggested by Junio\n \n RFC cover letter In a sparse index it is possible for the tree that is\n being verified to be freed while it is being verified. This is an RFC as\n I'm not familiar with the cache tree code. I'm confused as to why this\n bug is triggered by the sequence\n \n unpack_trees()\n prime_cache_tree()\n write_locked_index()\n \n \n but not\n \n unpack_trees()\n write_locked_index()\n \n \n as unpack_trees() appears to update the cache tree with\n \n if (!cache_tree_fully_valid(o->result.cache_tree))\n cache_tree_update(&o->result,\n WRITE_TREE_SILENT |\n WRITE_TREE_REPAIR);\n \n \n and I don't understand why the cache tree from prime_cache_tree()\n results in different behavior. It concerns me that this fix is hiding\n another bug.\n \n Best Wishes\n \n Phillip\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1053%2Fphillipwood%2Fwip%2Fsparse-index-fix-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1053/phillipwood/wip/sparse-index-fix-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/1053\n\nRange-diff vs v1:\n\n 1: 358b7afb653 ! 1: 4ee972fee2e [RFC] sparse index: fix use-after-free bug in cache_tree_verify()\n @@ Metadata\n Author: Phillip Wood \n \n ## Commit message ##\n - [RFC] sparse index: fix use-after-free bug in cache_tree_verify()\n + sparse index: fix use-after-free bug in cache_tree_verify()\n \n In a sparse index it is possible for the tree that is being verified\n - to be freed while it is being verified. This happens when\n - index_name_pos() looks up a entry that is missing from the index and\n - that would be a descendant of a sparse entry. That triggers a call to\n - ensure_full_index() which frees the cache tree that is being verified.\n - Carrying on trying to verify the tree after this results in a\n - use-after-free bug. Instead restart the verification if a sparse index\n - is converted to a full index. This bug is triggered by a call to\n - reset_head() in \"git rebase --apply\". Thanks to René Scharfe for his\n - help analyzing the problem.\n + to be freed while it is being verified. This happens when the index is\n + sparse but the cache tree is not and index_name_pos() looks up a path\n + from the cache tree that is a descendant of a sparse index entry. That\n + triggers a call to ensure_full_index() which frees the cache tree that\n + is being verified. Carrying on trying to verify the tree after this\n + results in a use-after-free bug. Instead restart the verification if a\n + sparse index is converted to a full index. This bug is triggered by a\n + call to reset_head() in \"git rebase --apply\". Thanks to René Scharfe\n + and Derick Stolee for their help analyzing the problem.\n \n ==74345==ERROR: AddressSanitizer: heap-use-after-free on address 0x606000001b20 at pc 0x557cbe82d3a2 bp 0x7ffdfee08090 sp 0x7ffdfee08080\n READ of size 4 at 0x606000001b20 thread T0\n @@ cache-tree.c: static void verify_one_sparse(struct repository *r,\n -\t\t struct index_state *istate,\n -\t\t struct cache_tree *it,\n -\t\t struct strbuf *path)\n ++/*\n ++ * Returns:\n ++ * 0 - Verification completed.\n ++ * 1 - Restart verification - a call to ensure_full_index() freed the cache\n ++ * tree that is being verified and verification needs to be restarted from\n ++ * the new toplevel cache tree.\n ++ */\n +static int verify_one(struct repository *r,\n +\t\t struct index_state *istate,\n +\t\t struct cache_tree *it,\n @@ cache-tree.c: static void verify_one(struct repository *r,\n \n \tif (path->len) {\n +\t\t/*\n -+\t\t * If the index is sparse index_name_pos() may trigger\n -+\t\t * ensure_full_index() which will free the tree that is being\n -+\t\t * verified.\n ++\t\t * If the index is sparse and the cache tree is not\n ++\t\t * index_name_pos() may trigger ensure_full_index() which will\n ++\t\t * free the tree that is being verified.\n +\t\t */\n +\t\tint is_sparse = istate->sparse_index;\n \t\tpos = index_name_pos(istate, path->buf, path->len);\n @@ cache-tree.c: void cache_tree_verify(struct repository *r, struct index_state *i\n -\tverify_one(r, istate, istate->cache_tree, &path);\n +\tif (verify_one(r, istate, istate->cache_tree, &path)) {\n +\t\tstrbuf_reset(&path);\n -+\t\tverify_one(r, istate, istate->cache_tree, &path);\n ++\t\tif (verify_one(r, istate, istate->cache_tree, &path))\n ++\t\t\tBUG(\"ensure_full_index() called twice while verifying cache tree\");\n +\t}\n \tstrbuf_release(&path);\n }\n\n\n cache-tree.c | 37 +++++++++++++++++++-----\n t/t1092-sparse-checkout-compatibility.sh | 2 +-\n 2 files changed, 30 insertions(+), 9 deletions(-)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 90919f9e345..8044e21bcf3 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -826,10 +826,17 @@ static void verify_one_sparse(struct repository *r,\n \t\t path->buf);\n }\n \n-static void verify_one(struct repository *r,\n-\t\t struct index_state *istate,\n-\t\t struct cache_tree *it,\n-\t\t struct strbuf *path)\n+/*\n+ * Returns:\n+ * 0 - Verification completed.\n+ * 1 - Restart verification - a call to ensure_full_index() freed the cache\n+ * tree that is being verified and verification needs to be restarted from\n+ * the new toplevel cache tree.\n+ */\n+static int verify_one(struct repository *r,\n+\t\t struct index_state *istate,\n+\t\t struct cache_tree *it,\n+\t\t struct strbuf *path)\n {\n \tint i, pos, len = path->len;\n \tstruct strbuf tree_buf = STRBUF_INIT;\n@@ -837,21 +844,30 @@ static void verify_one(struct repository *r,\n \n \tfor (i = 0; i < it->subtree_nr; i++) {\n \t\tstrbuf_addf(path, \"%s/\", it->down[i]->name);\n-\t\tverify_one(r, istate, it->down[i]->cache_tree, path);\n+\t\tif (verify_one(r, istate, it->down[i]->cache_tree, path))\n+\t\t\treturn 1;\n \t\tstrbuf_setlen(path, len);\n \t}\n \n \tif (it->entry_count < 0 ||\n \t /* no verification on tests (t7003) that replace trees */\n \t lookup_replace_object(r, &it->oid) != &it->oid)\n-\t\treturn;\n+\t\treturn 0;\n \n \tif (path->len) {\n+\t\t/*\n+\t\t * If the index is sparse and the cache tree is not\n+\t\t * index_name_pos() may trigger ensure_full_index() which will\n+\t\t * free the tree that is being verified.\n+\t\t */\n+\t\tint is_sparse = istate->sparse_index;\n \t\tpos = index_name_pos(istate, path->buf, path->len);\n+\t\tif (is_sparse && !istate->sparse_index)\n+\t\t\treturn 1;\n \n \t\tif (pos >= 0) {\n \t\t\tverify_one_sparse(r, istate, it, path, pos);\n-\t\t\treturn;\n+\t\t\treturn 0;\n \t\t}\n \n \t\tpos = -pos - 1;\n@@ -899,6 +915,7 @@ static void verify_one(struct repository *r,\n \t\t oid_to_hex(&new_oid), oid_to_hex(&it->oid));\n \tstrbuf_setlen(path, len);\n \tstrbuf_release(&tree_buf);\n+\treturn 0;\n }\n \n void cache_tree_verify(struct repository *r, struct index_state *istate)\n@@ -907,6 +924,10 @@ void cache_tree_verify(struct repository *r, struct index_state *istate)\n \n \tif (!istate->cache_tree)\n \t\treturn;\n-\tverify_one(r, istate, istate->cache_tree, &path);\n+\tif (verify_one(r, istate, istate->cache_tree, &path)) {\n+\t\tstrbuf_reset(&path);\n+\t\tif (verify_one(r, istate, istate->cache_tree, &path))\n+\t\t\tBUG(\"ensure_full_index() called twice while verifying cache tree\");\n+\t}\n \tstrbuf_release(&path);\n }\ndiff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\nindex 886e78715fe..85d5279b33c 100755\n--- a/t/t1092-sparse-checkout-compatibility.sh\n+++ b/t/t1092-sparse-checkout-compatibility.sh\n@@ -484,7 +484,7 @@ test_expect_success 'checkout and reset (mixed) [sparse]' '\n test_expect_success 'merge, cherry-pick, and rebase' '\n \tinit_repos &&\n \n-\tfor OPERATION in \"merge -m merge\" cherry-pick rebase\n+\tfor OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply\" \"rebase --merge\"\n \tdo\n \t\ttest_all_match git checkout -B temp update-deep &&\n \t\ttest_all_match git $OPERATION update-folder1 &&\n\nbase-commit: cefe983a320c03d7843ac78e73bd513a27806845\n-- \ngitgitgadget\n"},{"id":"438162","messageId":"a5011892-1dfe-31ab-12fe-d586eb0e9dbd@gmail.com","threadId":"56652","inReplyTo":"pull.1053.v2.git.1633600244854.gitgitgadget@gmail.com","subject":"Re: [PATCH v2] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-10-07T13:35:04Z","receivedAt":"2021-10-07T13:35:10Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/7/2021 5:50 AM, Phillip Wood via GitGitGadget wrote:\n> From: Phillip Wood \n> \n> In a sparse index it is possible for the tree that is being verified\n> to be freed while it is being verified. This happens when the index is\n> sparse but the cache tree is not and index_name_pos() looks up a path\n> from the cache tree that is a descendant of a sparse index entry. That\n> triggers a call to ensure_full_index() which frees the cache tree that\n> is being verified. Carrying on trying to verify the tree after this\n> results in a use-after-free bug. Instead restart the verification if a\n> sparse index is converted to a full index. This bug is triggered by a\n> call to reset_head() in \"git rebase --apply\". Thanks to René Scharfe\n> and Derick Stolee for their help analyzing the problem.\n\nnit: s/Derick/Derrick/\n\nOtherwise, this version looks good to me. Thanks for putting the last\nbit of polish on it.\n\nI'm taking this patch into our microsoft/git fork as we speak [1].\n\n[1] https://github.com/microsoft/git/pull/439\n\nThanks,\n-Stolee\n"},{"id":"438169","messageId":"3bf4e767-294e-0f30-f0bc-ffa706a86835@gmail.com","threadId":"56652","inReplyTo":"pull.1053.v2.git.1633600244854.gitgitgadget@gmail.com","subject":"Re: [PATCH v2] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-10-07T13:53:51Z","receivedAt":"2021-10-07T13:53:55Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/7/2021 5:50 AM, Phillip Wood via GitGitGadget wrote:\n> From: Phillip Wood \n...\n> diff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\n> index 886e78715fe..85d5279b33c 100755\n> --- a/t/t1092-sparse-checkout-compatibility.sh\n> +++ b/t/t1092-sparse-checkout-compatibility.sh\n> @@ -484,7 +484,7 @@ test_expect_success 'checkout and reset (mixed) [sparse]' '\n> test_expect_success 'merge, cherry-pick, and rebase' '\n> \tinit_repos &&\n> \n> -\tfor OPERATION in \"merge -m merge\" cherry-pick rebase\n> +\tfor OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply\" \"rebase --merge\"\n\nI spoke too soon. On my machine, the 'git rebase --apply' tests fail\nbecause of some verbose output that does not match across the full\nand sparse cases. Using \"rebase -q --apply\" works for me.\n\nThanks,\n-Stolee\n\n"},{"id":"438172","messageId":"c7ce1fd0-21c9-9ee9-bade-f3cec58d1029@gmail.com","threadId":"56652","inReplyTo":"a5011892-1dfe-31ab-12fe-d586eb0e9dbd@gmail.com","subject":"Re: [PATCH v2] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2021-10-07T14:59:32Z","receivedAt":"2021-10-07T14:59:38Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Hi Stolee\n\nOn 07/10/2021 14:35, Derrick Stolee wrote:\n> On 10/7/2021 5:50 AM, Phillip Wood via GitGitGadget wrote:\n>> From: Phillip Wood \n>>\n>> In a sparse index it is possible for the tree that is being verified\n>> to be freed while it is being verified. This happens when the index is\n>> sparse but the cache tree is not and index_name_pos() looks up a path\n>> from the cache tree that is a descendant of a sparse index entry. That\n>> triggers a call to ensure_full_index() which frees the cache tree that\n>> is being verified. Carrying on trying to verify the tree after this\n>> results in a use-after-free bug. Instead restart the verification if a\n>> sparse index is converted to a full index. This bug is triggered by a\n>> call to reset_head() in \"git rebase --apply\". Thanks to René Scharfe\n>> and Derick Stolee for their help analyzing the problem.\n> \n> nit: s/Derick/Derrick/\n\nSorry, maybe Junio can tweak that when he applies the patch, if not I'll \nfix it.\n\n> Otherwise, this version looks good to me. Thanks for putting the last\n> bit of polish on it.\n> \n> I'm taking this patch into our microsoft/git fork as we speak [1].\n> \n> [1] https://github.com/microsoft/git/pull/439\n\nThat's nice to know, Thanks\n\nPhillip\n"},{"id":"438173","messageId":"028aef79-d4cd-5202-f657-4b5045f85d0f@gmail.com","threadId":"56652","inReplyTo":"3bf4e767-294e-0f30-f0bc-ffa706a86835@gmail.com","subject":"Re: [PATCH v2] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2021-10-07T15:05:53Z","receivedAt":"2021-10-07T15:06:02Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Hi Stolee\n\nOn 07/10/2021 14:53, Derrick Stolee wrote:\n> On 10/7/2021 5:50 AM, Phillip Wood via GitGitGadget wrote:\n>> From: Phillip Wood \n> ...\n>> diff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\n>> index 886e78715fe..85d5279b33c 100755\n>> --- a/t/t1092-sparse-checkout-compatibility.sh\n>> +++ b/t/t1092-sparse-checkout-compatibility.sh\n>> @@ -484,7 +484,7 @@ test_expect_success 'checkout and reset (mixed) [sparse]' '\n>> test_expect_success 'merge, cherry-pick, and rebase' '\n>> \tinit_repos &&\n>> \n>> -\tfor OPERATION in \"merge -m merge\" cherry-pick rebase\n>> +\tfor OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply\" \"rebase --merge\"\n> \n> I spoke too soon. On my machine, the 'git rebase --apply' tests fail\n> because of some verbose output that does not match across the full\n> and sparse cases. Using \"rebase -q --apply\" works for me.\n\nOh, that's strange, the CI tests pass on gitgitgadget and that script \npasses locally for me. Do you know what the output is that does not match?\n\nBest Wishes\n\nPhillip\n\n> Thanks,\n> -Stolee\n> \n"},{"id":"438174","messageId":"69f83ec7-315e-0488-774c-bb8490001b13@gmail.com","threadId":"56652","inReplyTo":"028aef79-d4cd-5202-f657-4b5045f85d0f@gmail.com","subject":"Re: [PATCH v2] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-10-07T15:44:50Z","receivedAt":"2021-10-07T15:44:55Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/7/2021 11:05 AM, Phillip Wood wrote:\n> Hi Stolee\n> \n> On 07/10/2021 14:53, Derrick Stolee wrote:\n>> On 10/7/2021 5:50 AM, Phillip Wood via GitGitGadget wrote:\n>>> From: Phillip Wood \n>> ...\n>>> diff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\n>>> index 886e78715fe..85d5279b33c 100755\n>>> --- a/t/t1092-sparse-checkout-compatibility.sh\n>>> +++ b/t/t1092-sparse-checkout-compatibility.sh\n>>> @@ -484,7 +484,7 @@ test_expect_success 'checkout and reset (mixed) [sparse]' '\n>>>   test_expect_success 'merge, cherry-pick, and rebase' '\n>>>       init_repos &&\n>>>   -    for OPERATION in \"merge -m merge\" cherry-pick rebase\n>>> +    for OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply\" \"rebase --merge\"\n>>\n>> I spoke too soon. On my machine, the 'git rebase --apply' tests fail\n>> because of some verbose output that does not match across the full\n>> and sparse cases. Using \"rebase -q --apply\" works for me.\n> \n> Oh, that's strange, the CI tests pass on gitgitgadget and that script passes locally for me. Do you know what the output is that does not match?\n\nIt's entirely possible that it's something in git-for-windows/git or\nmicrosoft/git that is causing the difference:\n\n+ diff -u full-checkout-out sparse-checkout-out\n--- full-checkout-out\t2021-10-07 13:37:00.475394970 +0000\n+++ sparse-checkout-out\t2021-10-07 13:37:00.531396095 +0000\n@@ -1,3 +1,10 @@\n First, rewinding head to replay your work on top of it...\n Applying: update folder1\n+Using index info to reconstruct a base tree...\n+Falling back to patching base and 3-way merge...\n+Merging:\n+e1886b3 update folder2\n+virtual update folder1\n+found 1 common ancestor:\n+virtual b4ad7e16921c16e36f1d5d45ea4fa186efa8422a\n Applying: update deep\n+ return 1\nerror: last command exited with $?=1\n\n[1] https://github.com/microsoft/git/runs/3827705316?check_suite_focus=true#step:5:10469\n\nThanks,\n-Stolee\n"},{"id":"438184","messageId":"ebbe8616-0863-812b-e112-103680f7298b@gmail.com","threadId":"56652","inReplyTo":"69f83ec7-315e-0488-774c-bb8490001b13@gmail.com","subject":"Re: [PATCH v2] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2021-10-07T17:59:41Z","receivedAt":"2021-10-07T17:59:46Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Hi Stolee\n\nOn 07/10/2021 16:44, Derrick Stolee wrote:\n> On 10/7/2021 11:05 AM, Phillip Wood wrote:\n>> Hi Stolee\n>>\n>> On 07/10/2021 14:53, Derrick Stolee wrote:\n>>> On 10/7/2021 5:50 AM, Phillip Wood via GitGitGadget wrote:\n>>>> From: Phillip Wood \n>>> ...\n>>>> diff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\n>>>> index 886e78715fe..85d5279b33c 100755\n>>>> --- a/t/t1092-sparse-checkout-compatibility.sh\n>>>> +++ b/t/t1092-sparse-checkout-compatibility.sh\n>>>> @@ -484,7 +484,7 @@ test_expect_success 'checkout and reset (mixed) [sparse]' '\n>>>>   test_expect_success 'merge, cherry-pick, and rebase' '\n>>>>       init_repos &&\n>>>>   -    for OPERATION in \"merge -m merge\" cherry-pick rebase\n>>>> +    for OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply\" \"rebase --merge\"\n>>>\n>>> I spoke too soon. On my machine, the 'git rebase --apply' tests fail\n>>> because of some verbose output that does not match across the full\n>>> and sparse cases. Using \"rebase -q --apply\" works for me.\n>>\n>> Oh, that's strange, the CI tests pass on gitgitgadget and that script passes locally for me. Do you know what the output is that does not match?\n> \n> It's entirely possible that it's something in git-for-windows/git or\n> microsoft/git that is causing the difference:\n\nYes, if I apply the hunk below from 044d9fdaeb (\"sparse-checkout:\navoid writing entries with the skip-worktree bit\", 2017-03-01) which\nis in microsoft/vfs-2.33.0 to my fix then I see the same failure. It\nlooks like this change makes the apply back end fall back to a three\nway merge where a simple patch application succeeded before. Adding\n\"-q\" to the test feels like a bit of a hack but it's probably the best\nwe can do - at least it still catches any crashes.\n\nBest Wishes\n\nPhillip\n\ndiff --git a/apply.c b/apply.c\nindex 43a0aebf4e..4c1ca6d360 100644\n--- a/apply.c\n+++ b/apply.c\n@@ -3346,6 +3345,24 @@ static int checkout_target(struct index_state *istate,\n {\n struct checkout costate = CHECKOUT_INIT;\n \n+ /*\n+ * Do not checkout the entry if the skipworktree bit is set\n+ *\n+ * Both callers of this method (check_preimage and load_current)\n+ * check for the existance of the file before calling this\n+ * method so we know that the file doesn't exist at this point\n+ * and we don't need to perform that check again here.\n+ * We just need to check the skip-worktree and return.\n+ *\n+ * This is to prevent git from creating a file in the\n+ * working directory that has the skip-worktree bit on,\n+ * then updating the index from the patch and not keeping\n+ * the working directory version up to date with what it\n+ * changed the index version to be.\n+ */\n+ if (ce_skip_worktree(ce))\n+ return 0;\n+\n costate.refresh_cache = 1;\n costate.istate = istate;\n if (checkout_entry(ce, &costate, NULL, NULL) ||\n\n\n> + diff -u full-checkout-out sparse-checkout-out\n> --- full-checkout-out\t2021-10-07 13:37:00.475394970 +0000\n> +++ sparse-checkout-out\t2021-10-07 13:37:00.531396095 +0000\n> @@ -1,3 +1,10 @@\n> First, rewinding head to replay your work on top of it...\n> Applying: update folder1\n> +Using index info to reconstruct a base tree...\n> +Falling back to patching base and 3-way merge...\n> +Merging:\n> +e1886b3 update folder2\n> +virtual update folder1\n> +found 1 common ancestor:\n> +virtual b4ad7e16921c16e36f1d5d45ea4fa186efa8422a\n> Applying: update deep\n> + return 1\n> error: last command exited with $?=1\n> \n> [1] https://github.com/microsoft/git/runs/3827705316?check_suite_focus=true#step:5:10469\n> \n> Thanks,\n> -Stolee\n> \n\n"},{"id":"438187","messageId":"pull.1053.v3.git.1633630041829.gitgitgadget@gmail.com","threadId":"56652","inReplyTo":"pull.1053.v2.git.1633600244854.gitgitgadget@gmail.com","subject":"[PATCH v3] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Phillip Wood via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-10-07T18:07:21Z","receivedAt":"2021-10-07T18:07:35Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"From: Phillip Wood \n\nIn a sparse index it is possible for the tree that is being verified\nto be freed while it is being verified. This happens when the index is\nsparse but the cache tree is not and index_name_pos() looks up a path\nfrom the cache tree that is a descendant of a sparse index entry. That\ntriggers a call to ensure_full_index() which frees the cache tree that\nis being verified. Carrying on trying to verify the tree after this\nresults in a use-after-free bug. Instead restart the verification if a\nsparse index is converted to a full index. This bug is triggered by a\ncall to reset_head() in \"git rebase --apply\". Thanks to René Scharfe\nand Derrick Stolee for their help analyzing the problem.\n\n==74345==ERROR: AddressSanitizer: heap-use-after-free on address 0x606000001b20 at pc 0x557cbe82d3a2 bp 0x7ffdfee08090 sp 0x7ffdfee08080\nREAD of size 4 at 0x606000001b20 thread T0\n #0 0x557cbe82d3a1 in verify_one /home/phil/src/git/cache-tree.c:863\n #1 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #2 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #3 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #4 0x557cbe830a2b in cache_tree_verify /home/phil/src/git/cache-tree.c:910\n #5 0x557cbea53741 in write_locked_index /home/phil/src/git/read-cache.c:3250\n #6 0x557cbeab7fdd in reset_head /home/phil/src/git/reset.c:87\n #7 0x557cbe72147f in cmd_rebase builtin/rebase.c:2074\n #8 0x557cbe5bd151 in run_builtin /home/phil/src/git/git.c:461\n #9 0x557cbe5bd151 in handle_builtin /home/phil/src/git/git.c:714\n #10 0x557cbe5c0503 in run_argv /home/phil/src/git/git.c:781\n #11 0x557cbe5c0503 in cmd_main /home/phil/src/git/git.c:912\n #12 0x557cbe5bad28 in main /home/phil/src/git/common-main.c:52\n #13 0x7fdd4b82eb24 in __libc_start_main (/usr/lib/libc.so.6+0x27b24)\n #14 0x557cbe5bcb8d in _start (/home/phil/src/git/git+0x1b9b8d)\n\n0x606000001b20 is located 0 bytes inside of 56-byte region [0x606000001b20,0x606000001b58)\nfreed by thread T0 here:\n #0 0x7fdd4bacff19 in __interceptor_free /build/gcc/src/gcc/libsanitizer/asan/asan_malloc_linux.cpp:127\n #1 0x557cbe82af60 in cache_tree_free /home/phil/src/git/cache-tree.c:35\n #2 0x557cbe82aee5 in cache_tree_free /home/phil/src/git/cache-tree.c:31\n #3 0x557cbe82aee5 in cache_tree_free /home/phil/src/git/cache-tree.c:31\n #4 0x557cbe82aee5 in cache_tree_free /home/phil/src/git/cache-tree.c:31\n #5 0x557cbeb2557a in ensure_full_index /home/phil/src/git/sparse-index.c:310\n #6 0x557cbea45c4a in index_name_stage_pos /home/phil/src/git/read-cache.c:588\n #7 0x557cbe82ce37 in verify_one /home/phil/src/git/cache-tree.c:850\n #8 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #9 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #10 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #11 0x557cbe830a2b in cache_tree_verify /home/phil/src/git/cache-tree.c:910\n #12 0x557cbea53741 in write_locked_index /home/phil/src/git/read-cache.c:3250\n #13 0x557cbeab7fdd in reset_head /home/phil/src/git/reset.c:87\n #14 0x557cbe72147f in cmd_rebase builtin/rebase.c:2074\n #15 0x557cbe5bd151 in run_builtin /home/phil/src/git/git.c:461\n #16 0x557cbe5bd151 in handle_builtin /home/phil/src/git/git.c:714\n #17 0x557cbe5c0503 in run_argv /home/phil/src/git/git.c:781\n #18 0x557cbe5c0503 in cmd_main /home/phil/src/git/git.c:912\n #19 0x557cbe5bad28 in main /home/phil/src/git/common-main.c:52\n #20 0x7fdd4b82eb24 in __libc_start_main (/usr/lib/libc.so.6+0x27b24)\n\npreviously allocated by thread T0 here:\n #0 0x7fdd4bad0459 in __interceptor_calloc /build/gcc/src/gcc/libsanitizer/asan/asan_malloc_linux.cpp:154\n #1 0x557cbebc1807 in xcalloc /home/phil/src/git/wrapper.c:140\n #2 0x557cbe82b7d8 in cache_tree /home/phil/src/git/cache-tree.c:17\n #3 0x557cbe82b7d8 in prime_cache_tree_rec /home/phil/src/git/cache-tree.c:763\n #4 0x557cbe82b837 in prime_cache_tree_rec /home/phil/src/git/cache-tree.c:764\n #5 0x557cbe82b837 in prime_cache_tree_rec /home/phil/src/git/cache-tree.c:764\n #6 0x557cbe8304e1 in prime_cache_tree /home/phil/src/git/cache-tree.c:779\n #7 0x557cbeab7fa7 in reset_head /home/phil/src/git/reset.c:85\n #8 0x557cbe72147f in cmd_rebase builtin/rebase.c:2074\n #9 0x557cbe5bd151 in run_builtin /home/phil/src/git/git.c:461\n #10 0x557cbe5bd151 in handle_builtin /home/phil/src/git/git.c:714\n #11 0x557cbe5c0503 in run_argv /home/phil/src/git/git.c:781\n #12 0x557cbe5c0503 in cmd_main /home/phil/src/git/git.c:912\n #13 0x557cbe5bad28 in main /home/phil/src/git/common-main.c:52\n #14 0x7fdd4b82eb24 in __libc_start_main (/usr/lib/libc.so.6+0x27b24)\n\nSigned-off-by: Phillip Wood \n---\n [RFC] sparse index: fix use-after-free bug in cache_tree_verify()\n \n Changes since V2\n \n * Fixed the spelling of Stolee's name (sorry Stolee)\n * Added \"-q\" to the test to prevent a failure on Microsoft's fork[1]\n \n [1]\n https://lore.kernel.org/git/ebbe8616-0863-812b-e112-103680f7298b@gmail.com/\n \n Thanks for the feedback and help, here are the changes from the RFC\n \n * Updated commit message and comments to make it clear this is\n triggered by a sparse index with a full cache tree based on Stolee's\n explanation.\n * Added a comment and BUG() suggested by Junio\n \n RFC cover letter In a sparse index it is possible for the tree that is\n being verified to be freed while it is being verified. This is an RFC as\n I'm not familiar with the cache tree code. I'm confused as to why this\n bug is triggered by the sequence\n \n unpack_trees()\n prime_cache_tree()\n write_locked_index()\n \n \n but not\n \n unpack_trees()\n write_locked_index()\n \n \n as unpack_trees() appears to update the cache tree with\n \n if (!cache_tree_fully_valid(o->result.cache_tree))\n cache_tree_update(&o->result,\n WRITE_TREE_SILENT |\n WRITE_TREE_REPAIR);\n \n \n and I don't understand why the cache tree from prime_cache_tree()\n results in different behavior. It concerns me that this fix is hiding\n another bug.\n \n Best Wishes\n \n Phillip\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1053%2Fphillipwood%2Fwip%2Fsparse-index-fix-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1053/phillipwood/wip/sparse-index-fix-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/1053\n\nRange-diff vs v2:\n\n 1: 4ee972fee2e ! 1: b3dbe02fcc3 sparse index: fix use-after-free bug in cache_tree_verify()\n @@ Commit message\n results in a use-after-free bug. Instead restart the verification if a\n sparse index is converted to a full index. This bug is triggered by a\n call to reset_head() in \"git rebase --apply\". Thanks to René Scharfe\n - and Derick Stolee for their help analyzing the problem.\n + and Derrick Stolee for their help analyzing the problem.\n \n ==74345==ERROR: AddressSanitizer: heap-use-after-free on address 0x606000001b20 at pc 0x557cbe82d3a2 bp 0x7ffdfee08090 sp 0x7ffdfee08080\n READ of size 4 at 0x606000001b20 thread T0\n @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'checkout and rese\n \tinit_repos &&\n \n -\tfor OPERATION in \"merge -m merge\" cherry-pick rebase\n -+\tfor OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply\" \"rebase --merge\"\n ++\tfor OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply -q\" \"rebase --merge\"\n \tdo\n \t\ttest_all_match git checkout -B temp update-deep &&\n \t\ttest_all_match git $OPERATION update-folder1 &&\n\n\n cache-tree.c | 37 +++++++++++++++++++-----\n t/t1092-sparse-checkout-compatibility.sh | 2 +-\n 2 files changed, 30 insertions(+), 9 deletions(-)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 90919f9e345..8044e21bcf3 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -826,10 +826,17 @@ static void verify_one_sparse(struct repository *r,\n \t\t path->buf);\n }\n \n-static void verify_one(struct repository *r,\n-\t\t struct index_state *istate,\n-\t\t struct cache_tree *it,\n-\t\t struct strbuf *path)\n+/*\n+ * Returns:\n+ * 0 - Verification completed.\n+ * 1 - Restart verification - a call to ensure_full_index() freed the cache\n+ * tree that is being verified and verification needs to be restarted from\n+ * the new toplevel cache tree.\n+ */\n+static int verify_one(struct repository *r,\n+\t\t struct index_state *istate,\n+\t\t struct cache_tree *it,\n+\t\t struct strbuf *path)\n {\n \tint i, pos, len = path->len;\n \tstruct strbuf tree_buf = STRBUF_INIT;\n@@ -837,21 +844,30 @@ static void verify_one(struct repository *r,\n \n \tfor (i = 0; i < it->subtree_nr; i++) {\n \t\tstrbuf_addf(path, \"%s/\", it->down[i]->name);\n-\t\tverify_one(r, istate, it->down[i]->cache_tree, path);\n+\t\tif (verify_one(r, istate, it->down[i]->cache_tree, path))\n+\t\t\treturn 1;\n \t\tstrbuf_setlen(path, len);\n \t}\n \n \tif (it->entry_count < 0 ||\n \t /* no verification on tests (t7003) that replace trees */\n \t lookup_replace_object(r, &it->oid) != &it->oid)\n-\t\treturn;\n+\t\treturn 0;\n \n \tif (path->len) {\n+\t\t/*\n+\t\t * If the index is sparse and the cache tree is not\n+\t\t * index_name_pos() may trigger ensure_full_index() which will\n+\t\t * free the tree that is being verified.\n+\t\t */\n+\t\tint is_sparse = istate->sparse_index;\n \t\tpos = index_name_pos(istate, path->buf, path->len);\n+\t\tif (is_sparse && !istate->sparse_index)\n+\t\t\treturn 1;\n \n \t\tif (pos >= 0) {\n \t\t\tverify_one_sparse(r, istate, it, path, pos);\n-\t\t\treturn;\n+\t\t\treturn 0;\n \t\t}\n \n \t\tpos = -pos - 1;\n@@ -899,6 +915,7 @@ static void verify_one(struct repository *r,\n \t\t oid_to_hex(&new_oid), oid_to_hex(&it->oid));\n \tstrbuf_setlen(path, len);\n \tstrbuf_release(&tree_buf);\n+\treturn 0;\n }\n \n void cache_tree_verify(struct repository *r, struct index_state *istate)\n@@ -907,6 +924,10 @@ void cache_tree_verify(struct repository *r, struct index_state *istate)\n \n \tif (!istate->cache_tree)\n \t\treturn;\n-\tverify_one(r, istate, istate->cache_tree, &path);\n+\tif (verify_one(r, istate, istate->cache_tree, &path)) {\n+\t\tstrbuf_reset(&path);\n+\t\tif (verify_one(r, istate, istate->cache_tree, &path))\n+\t\t\tBUG(\"ensure_full_index() called twice while verifying cache tree\");\n+\t}\n \tstrbuf_release(&path);\n }\ndiff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\nindex 886e78715fe..80c77bb432e 100755\n--- a/t/t1092-sparse-checkout-compatibility.sh\n+++ b/t/t1092-sparse-checkout-compatibility.sh\n@@ -484,7 +484,7 @@ test_expect_success 'checkout and reset (mixed) [sparse]' '\n test_expect_success 'merge, cherry-pick, and rebase' '\n \tinit_repos &&\n \n-\tfor OPERATION in \"merge -m merge\" cherry-pick rebase\n+\tfor OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply -q\" \"rebase --merge\"\n \tdo\n \t\ttest_all_match git checkout -B temp update-deep &&\n \t\ttest_all_match git $OPERATION update-folder1 &&\n\nbase-commit: cefe983a320c03d7843ac78e73bd513a27806845\n-- \ngitgitgadget\n"},{"id":"438238","messageId":"xmqqee8wpm0u.fsf@gitster.g","threadId":"56652","inReplyTo":"pull.1053.v3.git.1633630041829.gitgitgadget@gmail.com","subject":"Re: [PATCH v3] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-10-07T21:23:13Z","receivedAt":"2021-10-07T21:23:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Phillip Wood via GitGitGadget\" writes:\n\n> * Fixed the spelling of Stolee's name (sorry Stolee)\n> * Added \"-q\" to the test to prevent a failure on Microsoft's fork[1]\n> \n> [1]\n> https://lore.kernel.org/git/ebbe8616-0863-812b-e112-103680f7298b@gmail.com/\n\nI've seen the exchange, but ...\n\n> -\tfor OPERATION in \"merge -m merge\" cherry-pick rebase\n> +\tfor OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply -q\" \"rebase --merge\"\n> \tdo\n\n... it looks too strange that only one of them requires a \"--quiet\"\noption. Is it a possibility to get whoever's fork corrected so that\nit behaves sensibly without requiring the \"-q\" option only for the\nparticular rebase backend?\n\nIn the meantime, I'll queue the patch as-is (I actually queued the\nprevious round with namefix already).\n\nThanks.\n"},{"id":"438284","messageId":"4ccaad06-a1ae-bd1b-f25d-bfa899ffa98f@gmail.com","threadId":"56652","inReplyTo":"xmqqee8wpm0u.fsf@gitster.g","subject":"Re: [PATCH v3] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2021-10-08T09:09:46Z","receivedAt":"2021-10-08T09:09:50Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"On 07/10/2021 22:23, Junio C Hamano wrote:\n> \"Phillip Wood via GitGitGadget\" writes:\n> \n>> * Fixed the spelling of Stolee's name (sorry Stolee)\n>> * Added \"-q\" to the test to prevent a failure on Microsoft's fork[1]\n>> \n>> [1]\n>> https://lore.kernel.org/git/ebbe8616-0863-812b-e112-103680f7298b@gmail.com/\n> \n> I've seen the exchange, but ...\n> \n>> -\tfor OPERATION in \"merge -m merge\" cherry-pick rebase\n>> +\tfor OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply -q\" \"rebase --merge\"\n>> \tdo\n> \n> ... it looks too strange that only one of them requires a \"--quiet\"\n> option. Is it a possibility to get whoever's fork corrected so that\n> it behaves sensibly without requiring the \"-q\" option only for the\n> particular rebase backend?\n\nThe issue is caused by a patch that Microsoft is carrying that stops \napply from creating paths with the skip-worktree bit set. As they're \nupstreaming their sparse index and checkout work I expect it will show \nup on the list sooner or later. I agree the \"-q\" is odd and it also \nmeans the test is weaker but I'm not sure what else we can do.\n\n> In the meantime, I'll queue the patch as-is (I actually queued the\n> previous round with namefix already).\n\nThanks\n\nPhillip\n\n> Thanks.\n> \n\n"},{"id":"438289","messageId":"905e3d0f-0541-ffad-c05b-e7ebc6bed94c@gmail.com","threadId":"56652","inReplyTo":"pull.1053.v3.git.1633630041829.gitgitgadget@gmail.com","subject":"Re: [PATCH v3] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Bagas Sanjaya","fromEmail":"bagasdotme@gmail.com","sentAt":"2021-10-08T09:38:27Z","receivedAt":"2021-10-08T09:38:39Z","isPatch":true,"sender":{"key":"bagasdotme@gmail.com","avatar":"https://avatars.githubusercontent.com/u/40219486?v=4"},"body":"On 08/10/21 01.07, Phillip Wood via GitGitGadget wrote:\n> -static void verify_one(struct repository *r,\n> -\t\t struct index_state *istate,\n> -\t\t struct cache_tree *it,\n> -\t\t struct strbuf *path)\n> +/*\n> + * Returns:\n> + * 0 - Verification completed.\n> + * 1 - Restart verification - a call to ensure_full_index() freed the cache\n> + * tree that is being verified and verification needs to be restarted from\n> + * the new toplevel cache tree.\n> + */\n> +static int verify_one(struct repository *r,\n> +\t\t struct index_state *istate,\n> +\t\t struct cache_tree *it,\n> +\t\t struct strbuf *path)\n> {\n> \tint i, pos, len = path->len;\n> \tstruct strbuf tree_buf = STRBUF_INIT;\n\nWhat is verify_one() doing? I think it worth mentioning it in the \ncomment above.\n\n-- \nAn old man doll... just what I always wanted! - Clara\n"},{"id":"438308","messageId":"e281c2e2-2044-1a11-e2bc-5ab3ee92c300@gmail.com","threadId":"56652","inReplyTo":"4ccaad06-a1ae-bd1b-f25d-bfa899ffa98f@gmail.com","subject":"Re: [PATCH v3] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-10-08T18:53:07Z","receivedAt":"2021-10-08T18:53:25Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/8/2021 5:09 AM, Phillip Wood wrote:\n> On 07/10/2021 22:23, Junio C Hamano wrote:\n>> \"Phillip Wood via GitGitGadget\" writes:\n>>\n>>>       * Fixed the spelling of Stolee's name (sorry Stolee)\n>>>       * Added \"-q\" to the test to prevent a failure on Microsoft's fork[1]\n>>>           [1]\n>>>      https://lore.kernel.org/git/ebbe8616-0863-812b-e112-103680f7298b@gmail.com/\n>>\n>> I've seen the exchange, but ...\n>>\n>>> -    for OPERATION in \"merge -m merge\" cherry-pick rebase\n>>> +    for OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply -q\" \"rebase --merge\"\n>>>       do\n>>\n>> ... it looks too strange that only one of them requires a \"--quiet\"\n>> option.  Is it a possibility to get whoever's fork corrected so that\n>> it behaves sensibly without requiring the \"-q\" option only for the\n>> particular rebase backend?\n> \n> The issue is caused by a patch that Microsoft is carrying that stops apply from creating paths with the skip-worktree bit set. As they're upstreaming their sparse index and checkout work I expect it will show up on the list sooner or later. I agree the \"-q\" is odd and it also means the test is weaker but I'm not sure what else we can do.\n\nThat particular patch is old and is due to some interactions with\nhow VFS for Git (ab)uses the skip-worktree bit. I'm not sure it will\never come upstream. It is probably very much like a recent example [1]\nthat we tried to upstream only to realize that it should be replaced\nwith something better.\n\n[1] https://lore.kernel.org/git/65905bf4e001118e8b9ced95c1bcecbacb6334ac.1633013461.git.gitgitgadget@gmail.com/\n\nI'm fine to leave the `-q` out of this patch and I can add it myself\nwhen we take this into microsoft/git. That can also motivate me to\nrethink that patch.\n\nThanks,\n-Stolee\n"},{"id":"438333","messageId":"xmqqwnmnjnn5.fsf@gitster.g","threadId":"56652","inReplyTo":"4ccaad06-a1ae-bd1b-f25d-bfa899ffa98f@gmail.com","subject":"Re: [PATCH v3] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-10-08T19:57:02Z","receivedAt":"2021-10-08T19:57:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Phillip Wood writes:\n\n> On 07/10/2021 22:23, Junio C Hamano wrote:\n>> \"Phillip Wood via GitGitGadget\" writes:\n>> \n>>> * Fixed the spelling of Stolee's name (sorry Stolee)\n>>> * Added \"-q\" to the test to prevent a failure on Microsoft's fork[1]\n>>> [1]\n>>> https://lore.kernel.org/git/ebbe8616-0863-812b-e112-103680f7298b@gmail.com/\n>> I've seen the exchange, but ...\n>> \n>>> -\tfor OPERATION in \"merge -m merge\" cherry-pick rebase\n>>> +\tfor OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply -q\" \"rebase --merge\"\n>>> \tdo\n>> ... it looks too strange that only one of them requires a \"--quiet\"\n>> option. Is it a possibility to get whoever's fork corrected so that\n>> it behaves sensibly without requiring the \"-q\" option only for the\n>> particular rebase backend?\n>\n> The issue is caused by a patch that Microsoft is carrying that stops\n> apply from creating paths with the skip-worktree bit set. As they're \n> upstreaming their sparse index and checkout work I expect it will show\n> up on the list sooner or later. I agree the \"-q\" is odd and it also \n> means the test is weaker but I'm not sure what else we can do.\n\nPerhaps passing \"-q\" to the other variant of \"rebase\" would make it\nclear that (1) we do not want to worry about traces involved in the\nverbose message generation and (2) there is nothing fishy going on\nin only one of the \"rebase\" backends.\n\n"},{"id":"438751","messageId":"554ebfd6-63bd-50ec-5f55-4b5ea4a9fd03@gmail.com","threadId":"56652","inReplyTo":"905e3d0f-0541-ffad-c05b-e7ebc6bed94c@gmail.com","subject":"Re: [PATCH v3] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2021-10-14T09:40:27Z","receivedAt":"2021-10-14T09:40:32Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Hi Bagas\n\nOn 08/10/2021 10:38, Bagas Sanjaya wrote:\n> On 08/10/21 01.07, Phillip Wood via GitGitGadget wrote:\n>> -static void verify_one(struct repository *r,\n>> -               struct index_state *istate,\n>> -               struct cache_tree *it,\n>> -               struct strbuf *path)\n>> +/*\n>> + * Returns:\n>> + *  0 - Verification completed.\n>> + *  1 - Restart verification - a call to ensure_full_index() freed \n>> the cache\n>> + *      tree that is being verified and verification needs to be \n>> restarted from\n>> + *      the new toplevel cache tree.\n>> + */\n>> +static int verify_one(struct repository *r,\n>> +              struct index_state *istate,\n>> +              struct cache_tree *it,\n>> +              struct strbuf *path)\n>>   {\n>>       int i, pos, len = path->len;\n>>       struct strbuf tree_buf = STRBUF_INIT;\n> \n> What is verify_one() doing? I think it worth mentioning it in the \n> comment above.\n\nI think it's pretty obvious if you read the code rather than my patch. \nIt is a common pattern in git that a function with \"one\" in the name is \na helper for another similarly named function without the \"one\". In this \ncase verify_one() is a recursive helper for cache_tree_verify()\n\nBest Wishes\n\nPhillip\n"},{"id":"438755","messageId":"6dd3ba9f-7054-93f3-7798-d4a4a211899a@gmail.com","threadId":"56652","inReplyTo":"xmqqwnmnjnn5.fsf@gitster.g","subject":"Re: [PATCH v3] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2021-10-14T13:34:28Z","receivedAt":"2021-10-14T13:34:35Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Hi Junio\n\nOn 08/10/2021 20:57, Junio C Hamano wrote:\n> Phillip Wood writes:\n> \n>> On 07/10/2021 22:23, Junio C Hamano wrote:\n>>> \"Phillip Wood via GitGitGadget\" writes:\n>>>\n>>>> * Fixed the spelling of Stolee's name (sorry Stolee)\n>>>> * Added \"-q\" to the test to prevent a failure on Microsoft's fork[1]\n>>>> [1]\n>>>> https://lore.kernel.org/git/ebbe8616-0863-812b-e112-103680f7298b@gmail.com/\n>>> I've seen the exchange, but ...\n>>>\n>>>> -\tfor OPERATION in \"merge -m merge\" cherry-pick rebase\n>>>> +\tfor OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply -q\" \"rebase --merge\"\n>>>> \tdo\n>>> ... it looks too strange that only one of them requires a \"--quiet\"\n>>> option. Is it a possibility to get whoever's fork corrected so that\n>>> it behaves sensibly without requiring the \"-q\" option only for the\n>>> particular rebase backend?\n>>\n>> The issue is caused by a patch that Microsoft is carrying that stops\n>> apply from creating paths with the skip-worktree bit set. As they're\n>> upstreaming their sparse index and checkout work I expect it will show\n>> up on the list sooner or later. I agree the \"-q\" is odd and it also\n>> means the test is weaker but I'm not sure what else we can do.\n> \n> Perhaps passing \"-q\" to the other variant of \"rebase\" would make it\n> clear that (1) we do not want to worry about traces involved in the\n> verbose message generation and (2) there is nothing fishy going on\n> in only one of the \"rebase\" backends.\n\nI'm not sure about that. There are really three levels of output from \nrebase - quiet, normal and verbose. I think passing \"-q\" suppresses \nvirtually all the output - there is no indication of which commits have \nbeen picked. As test appears to be comparing the output of the command \nfor the sparse and non-spare case as a proxy for \"it behaves the same \nfor sparse and non-sparse checkouts/indexes\" passing \"-q\" to rebase \nweakens the test considerably. Stolee indicated [1] that he is happy for \nus to drop the \"-q\" for the \"--apply\" case so I'd be inclined to go back \nto your corrected version of V2.\n\nBest Wishes\n\nPhillip\n\n[1] \nhttps://lore.kernel.org/git/e281c2e2-2044-1a11-e2bc-5ab3ee92c300@gmail.com/\n"},{"id":"438762","messageId":"xmqqmtnbd0c1.fsf@gitster.g","threadId":"56652","inReplyTo":"6dd3ba9f-7054-93f3-7798-d4a4a211899a@gmail.com","subject":"Re: [PATCH v3] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-10-14T16:42:54Z","receivedAt":"2021-10-14T16:43:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Phillip Wood writes:\n\n> I'm not sure about that. There are really three levels of output from\n> rebase - quiet, normal and verbose. I think passing \"-q\" suppresses \n> virtually all the output - there is no indication of which commits\n> have been picked. As test appears to be comparing the output of the\n> command for the sparse and non-spare case as a proxy for \"it behaves\n> the same for sparse and non-sparse checkouts/indexes\" passing \"-q\" to\n> rebase weakens the test considerably.\n\nTrue. Also because the behaviour of \"rebase\" using different\nbackends are sufficiently different, I no longer consider it a funny\ninconsistency that one backend has to to use \"-q\" while the other\ndoesn't.\n\n> Stolee indicated [1] that he is\n> happy for us to drop the \"-q\" for the \"--apply\" case so I'd be\n> inclined to go back to your corrected version of V2.\n\nOK. Can we have a v4 that is identical to \"corrected\" v2, then,\nplease? That's easier than having to dig v2 up and remember and\napply the \"correction\" ;-).\n\nThanks.\n"},{"id":"438924","messageId":"pull.1053.v4.git.1634375229338.gitgitgadget@gmail.com","threadId":"56652","inReplyTo":"pull.1053.v3.git.1633630041829.gitgitgadget@gmail.com","subject":"[PATCH v4] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Phillip Wood via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-10-16T09:07:09Z","receivedAt":"2021-10-16T09:08:29Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"From: Phillip Wood \n\nIn a sparse index it is possible for the tree that is being verified\nto be freed while it is being verified. This happens when the index is\nsparse but the cache tree is not and index_name_pos() looks up a path\nfrom the cache tree that is a descendant of a sparse index entry. That\ntriggers a call to ensure_full_index() which frees the cache tree that\nis being verified. Carrying on trying to verify the tree after this\nresults in a use-after-free bug. Instead restart the verification if a\nsparse index is converted to a full index. This bug is triggered by a\ncall to reset_head() in \"git rebase --apply\". Thanks to René Scharfe\nand Derrick Stolee for their help analyzing the problem.\n\n==74345==ERROR: AddressSanitizer: heap-use-after-free on address 0x606000001b20 at pc 0x557cbe82d3a2 bp 0x7ffdfee08090 sp 0x7ffdfee08080\nREAD of size 4 at 0x606000001b20 thread T0\n #0 0x557cbe82d3a1 in verify_one /home/phil/src/git/cache-tree.c:863\n #1 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #2 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #3 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #4 0x557cbe830a2b in cache_tree_verify /home/phil/src/git/cache-tree.c:910\n #5 0x557cbea53741 in write_locked_index /home/phil/src/git/read-cache.c:3250\n #6 0x557cbeab7fdd in reset_head /home/phil/src/git/reset.c:87\n #7 0x557cbe72147f in cmd_rebase builtin/rebase.c:2074\n #8 0x557cbe5bd151 in run_builtin /home/phil/src/git/git.c:461\n #9 0x557cbe5bd151 in handle_builtin /home/phil/src/git/git.c:714\n #10 0x557cbe5c0503 in run_argv /home/phil/src/git/git.c:781\n #11 0x557cbe5c0503 in cmd_main /home/phil/src/git/git.c:912\n #12 0x557cbe5bad28 in main /home/phil/src/git/common-main.c:52\n #13 0x7fdd4b82eb24 in __libc_start_main (/usr/lib/libc.so.6+0x27b24)\n #14 0x557cbe5bcb8d in _start (/home/phil/src/git/git+0x1b9b8d)\n\n0x606000001b20 is located 0 bytes inside of 56-byte region [0x606000001b20,0x606000001b58)\nfreed by thread T0 here:\n #0 0x7fdd4bacff19 in __interceptor_free /build/gcc/src/gcc/libsanitizer/asan/asan_malloc_linux.cpp:127\n #1 0x557cbe82af60 in cache_tree_free /home/phil/src/git/cache-tree.c:35\n #2 0x557cbe82aee5 in cache_tree_free /home/phil/src/git/cache-tree.c:31\n #3 0x557cbe82aee5 in cache_tree_free /home/phil/src/git/cache-tree.c:31\n #4 0x557cbe82aee5 in cache_tree_free /home/phil/src/git/cache-tree.c:31\n #5 0x557cbeb2557a in ensure_full_index /home/phil/src/git/sparse-index.c:310\n #6 0x557cbea45c4a in index_name_stage_pos /home/phil/src/git/read-cache.c:588\n #7 0x557cbe82ce37 in verify_one /home/phil/src/git/cache-tree.c:850\n #8 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #9 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #10 0x557cbe82ca9d in verify_one /home/phil/src/git/cache-tree.c:840\n #11 0x557cbe830a2b in cache_tree_verify /home/phil/src/git/cache-tree.c:910\n #12 0x557cbea53741 in write_locked_index /home/phil/src/git/read-cache.c:3250\n #13 0x557cbeab7fdd in reset_head /home/phil/src/git/reset.c:87\n #14 0x557cbe72147f in cmd_rebase builtin/rebase.c:2074\n #15 0x557cbe5bd151 in run_builtin /home/phil/src/git/git.c:461\n #16 0x557cbe5bd151 in handle_builtin /home/phil/src/git/git.c:714\n #17 0x557cbe5c0503 in run_argv /home/phil/src/git/git.c:781\n #18 0x557cbe5c0503 in cmd_main /home/phil/src/git/git.c:912\n #19 0x557cbe5bad28 in main /home/phil/src/git/common-main.c:52\n #20 0x7fdd4b82eb24 in __libc_start_main (/usr/lib/libc.so.6+0x27b24)\n\npreviously allocated by thread T0 here:\n #0 0x7fdd4bad0459 in __interceptor_calloc /build/gcc/src/gcc/libsanitizer/asan/asan_malloc_linux.cpp:154\n #1 0x557cbebc1807 in xcalloc /home/phil/src/git/wrapper.c:140\n #2 0x557cbe82b7d8 in cache_tree /home/phil/src/git/cache-tree.c:17\n #3 0x557cbe82b7d8 in prime_cache_tree_rec /home/phil/src/git/cache-tree.c:763\n #4 0x557cbe82b837 in prime_cache_tree_rec /home/phil/src/git/cache-tree.c:764\n #5 0x557cbe82b837 in prime_cache_tree_rec /home/phil/src/git/cache-tree.c:764\n #6 0x557cbe8304e1 in prime_cache_tree /home/phil/src/git/cache-tree.c:779\n #7 0x557cbeab7fa7 in reset_head /home/phil/src/git/reset.c:85\n #8 0x557cbe72147f in cmd_rebase builtin/rebase.c:2074\n #9 0x557cbe5bd151 in run_builtin /home/phil/src/git/git.c:461\n #10 0x557cbe5bd151 in handle_builtin /home/phil/src/git/git.c:714\n #11 0x557cbe5c0503 in run_argv /home/phil/src/git/git.c:781\n #12 0x557cbe5c0503 in cmd_main /home/phil/src/git/git.c:912\n #13 0x557cbe5bad28 in main /home/phil/src/git/common-main.c:52\n #14 0x7fdd4b82eb24 in __libc_start_main (/usr/lib/libc.so.6+0x27b24)\n\nSigned-off-by: Phillip Wood \n---\n [RFC] sparse index: fix use-after-free bug in cache_tree_verify()\n \n Changes since V3\n \n * removed \"-q\" from the test [1]. This is the same as V2 with a typo\n fixed in the commit message\n \n [1] https://lore.kernel.org/git/\n e281c2e2-2044-1a11-e2bc-5ab3ee92c300@gmail.com/\n \n Changes since V2\n \n * Fixed the spelling of Stolee's name (sorry Stolee)\n * Added \"-q\" to the test to prevent a failure on Microsoft's fork[1]\n \n [1]\n https://lore.kernel.org/git/ebbe8616-0863-812b-e112-103680f7298b@gmail.com/\n \n Thanks for the feedback and help, here are the changes from the RFC\n \n * Updated commit message and comments to make it clear this is\n triggered by a sparse index with a full cache tree based on Stolee's\n explanation.\n * Added a comment and BUG() suggested by Junio\n \n RFC cover letter In a sparse index it is possible for the tree that is\n being verified to be freed while it is being verified. This is an RFC as\n I'm not familiar with the cache tree code. I'm confused as to why this\n bug is triggered by the sequence\n \n unpack_trees()\n prime_cache_tree()\n write_locked_index()\n \n \n but not\n \n unpack_trees()\n write_locked_index()\n \n \n as unpack_trees() appears to update the cache tree with\n \n if (!cache_tree_fully_valid(o->result.cache_tree))\n cache_tree_update(&o->result,\n WRITE_TREE_SILENT |\n WRITE_TREE_REPAIR);\n \n \n and I don't understand why the cache tree from prime_cache_tree()\n results in different behavior. It concerns me that this fix is hiding\n another bug.\n \n Best Wishes\n \n Phillip\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1053%2Fphillipwood%2Fwip%2Fsparse-index-fix-v4\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1053/phillipwood/wip/sparse-index-fix-v4\nPull-Request: https://github.com/gitgitgadget/git/pull/1053\n\nRange-diff vs v3:\n\n 1: b3dbe02fcc3 ! 1: ea7e93e1a47 sparse index: fix use-after-free bug in cache_tree_verify()\n @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'checkout and rese\n \tinit_repos &&\n \n -\tfor OPERATION in \"merge -m merge\" cherry-pick rebase\n -+\tfor OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply -q\" \"rebase --merge\"\n ++\tfor OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply\" \"rebase --merge\"\n \tdo\n \t\ttest_all_match git checkout -B temp update-deep &&\n \t\ttest_all_match git $OPERATION update-folder1 &&\n\n\n cache-tree.c | 37 +++++++++++++++++++-----\n t/t1092-sparse-checkout-compatibility.sh | 2 +-\n 2 files changed, 30 insertions(+), 9 deletions(-)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 90919f9e345..8044e21bcf3 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -826,10 +826,17 @@ static void verify_one_sparse(struct repository *r,\n \t\t path->buf);\n }\n \n-static void verify_one(struct repository *r,\n-\t\t struct index_state *istate,\n-\t\t struct cache_tree *it,\n-\t\t struct strbuf *path)\n+/*\n+ * Returns:\n+ * 0 - Verification completed.\n+ * 1 - Restart verification - a call to ensure_full_index() freed the cache\n+ * tree that is being verified and verification needs to be restarted from\n+ * the new toplevel cache tree.\n+ */\n+static int verify_one(struct repository *r,\n+\t\t struct index_state *istate,\n+\t\t struct cache_tree *it,\n+\t\t struct strbuf *path)\n {\n \tint i, pos, len = path->len;\n \tstruct strbuf tree_buf = STRBUF_INIT;\n@@ -837,21 +844,30 @@ static void verify_one(struct repository *r,\n \n \tfor (i = 0; i < it->subtree_nr; i++) {\n \t\tstrbuf_addf(path, \"%s/\", it->down[i]->name);\n-\t\tverify_one(r, istate, it->down[i]->cache_tree, path);\n+\t\tif (verify_one(r, istate, it->down[i]->cache_tree, path))\n+\t\t\treturn 1;\n \t\tstrbuf_setlen(path, len);\n \t}\n \n \tif (it->entry_count < 0 ||\n \t /* no verification on tests (t7003) that replace trees */\n \t lookup_replace_object(r, &it->oid) != &it->oid)\n-\t\treturn;\n+\t\treturn 0;\n \n \tif (path->len) {\n+\t\t/*\n+\t\t * If the index is sparse and the cache tree is not\n+\t\t * index_name_pos() may trigger ensure_full_index() which will\n+\t\t * free the tree that is being verified.\n+\t\t */\n+\t\tint is_sparse = istate->sparse_index;\n \t\tpos = index_name_pos(istate, path->buf, path->len);\n+\t\tif (is_sparse && !istate->sparse_index)\n+\t\t\treturn 1;\n \n \t\tif (pos >= 0) {\n \t\t\tverify_one_sparse(r, istate, it, path, pos);\n-\t\t\treturn;\n+\t\t\treturn 0;\n \t\t}\n \n \t\tpos = -pos - 1;\n@@ -899,6 +915,7 @@ static void verify_one(struct repository *r,\n \t\t oid_to_hex(&new_oid), oid_to_hex(&it->oid));\n \tstrbuf_setlen(path, len);\n \tstrbuf_release(&tree_buf);\n+\treturn 0;\n }\n \n void cache_tree_verify(struct repository *r, struct index_state *istate)\n@@ -907,6 +924,10 @@ void cache_tree_verify(struct repository *r, struct index_state *istate)\n \n \tif (!istate->cache_tree)\n \t\treturn;\n-\tverify_one(r, istate, istate->cache_tree, &path);\n+\tif (verify_one(r, istate, istate->cache_tree, &path)) {\n+\t\tstrbuf_reset(&path);\n+\t\tif (verify_one(r, istate, istate->cache_tree, &path))\n+\t\t\tBUG(\"ensure_full_index() called twice while verifying cache tree\");\n+\t}\n \tstrbuf_release(&path);\n }\ndiff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\nindex 886e78715fe..85d5279b33c 100755\n--- a/t/t1092-sparse-checkout-compatibility.sh\n+++ b/t/t1092-sparse-checkout-compatibility.sh\n@@ -484,7 +484,7 @@ test_expect_success 'checkout and reset (mixed) [sparse]' '\n test_expect_success 'merge, cherry-pick, and rebase' '\n \tinit_repos &&\n \n-\tfor OPERATION in \"merge -m merge\" cherry-pick rebase\n+\tfor OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply\" \"rebase --merge\"\n \tdo\n \t\ttest_all_match git checkout -B temp update-deep &&\n \t\ttest_all_match git $OPERATION update-folder1 &&\n\nbase-commit: cefe983a320c03d7843ac78e73bd513a27806845\n-- \ngitgitgadget\n"},{"id":"438962","messageId":"xmqqilxw1a9v.fsf@gitster.g","threadId":"56652","inReplyTo":"pull.1053.v4.git.1634375229338.gitgitgadget@gmail.com","subject":"Re: [PATCH v4] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-10-17T05:38:04Z","receivedAt":"2021-10-17T05:48:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Phillip Wood via GitGitGadget\" writes:\n\n> [RFC] sparse index: fix use-after-free bug in cache_tree_verify()\n> \n> Changes since V3\n> \n> * removed \"-q\" from the test [1]. This is the same as V2 with a typo\n> fixed in the commit message\n> \n> [1] https://lore.kernel.org/git/\n> e281c2e2-2044-1a11-e2bc-5ab3ee92c300@gmail.com/\n\nThanks. Unfortunately I've already merged the previosu version on\nthe 11th, so I took the liberty of turning this round into an\nincremental. How does this look?\n\n----- >8 --------- >8 --------- >8 --------- >8 -----\nFrom: Phillip Wood \nDate: Sat, 16 Oct 2021 09:07:09 +0000\nSubject: [PATCH] t1092: run \"rebase --apply\" without \"-q\" in the test\n\nWe run a few Git subcommands and make sure they produce identical\nresults with and without sparse-index. To this set of subcommands,\nan earlier commit added \"rebase --apply\", but did so with the \"-q\"\noption, in order to work around a breakge caused by a version used\nat Microsoft with some unreleased changes.\n\nBecause we would want to make sure the commands produce indentical\nresults, including reports given to the output that lists which\ncommits were picked, use of \"-q\" loses too much interesting\ninformation. Let's drop \"-q\" from the command invocation and\nrevisit the issue when the problematic changes are upstreamed.\n\nSigned-off-by: Phillip Wood \nHelped-by: Derrick Stolee \nSigned-off-by: Junio C Hamano \n---\n t/t1092-sparse-checkout-compatibility.sh | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\nindex 80c77bb432..85d5279b33 100755\n--- a/t/t1092-sparse-checkout-compatibility.sh\n+++ b/t/t1092-sparse-checkout-compatibility.sh\n@@ -484,7 +484,7 @@ test_expect_success 'checkout and reset (mixed) [sparse]' '\n test_expect_success 'merge, cherry-pick, and rebase' '\n \tinit_repos &&\n \n-\tfor OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply -q\" \"rebase --merge\"\n+\tfor OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply\" \"rebase --merge\"\n \tdo\n \t\ttest_all_match git checkout -B temp update-deep &&\n \t\ttest_all_match git $OPERATION update-folder1 &&\n-- \n2.33.1-877-g9d049ddf90\n\n"},{"id":"438973","messageId":"08129e78-a900-0688-572d-1b5b51709629@gmail.com","threadId":"56652","inReplyTo":"xmqqilxw1a9v.fsf@gitster.g","subject":"Re: [PATCH v4] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-10-17T19:35:20Z","receivedAt":"2021-10-17T19:35:26Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/17/2021 1:38 AM, Junio C Hamano wrote:\n> \"Phillip Wood via GitGitGadget\" writes:\n> \n>> [RFC] sparse index: fix use-after-free bug in cache_tree_verify()\n>> \n>> Changes since V3\n>> \n>> * removed \"-q\" from the test [1]. This is the same as V2 with a typo\n>> fixed in the commit message\n>> \n>> [1] https://lore.kernel.org/git/\n>> e281c2e2-2044-1a11-e2bc-5ab3ee92c300@gmail.com/\n> \n> Thanks. Unfortunately I've already merged the previosu version on\n> the 11th, so I took the liberty of turning this round into an\n> incremental. How does this look?\n> \n> ----- >8 --------- >8 --------- >8 --------- >8 -----\n> From: Phillip Wood \n> Date: Sat, 16 Oct 2021 09:07:09 +0000\n> Subject: [PATCH] t1092: run \"rebase --apply\" without \"-q\" in the test\n> \n> We run a few Git subcommands and make sure they produce identical\n> results with and without sparse-index. To this set of subcommands,\n> an earlier commit added \"rebase --apply\", but did so with the \"-q\"\n> option, in order to work around a breakge caused by a version used\n\ns/breakge/breakage/\n\n> at Microsoft with some unreleased changes.\n> \n> Because we would want to make sure the commands produce indentical\n\ns/indentical/identical/\n\n> results, including reports given to the output that lists which\n> commits were picked, use of \"-q\" loses too much interesting\n> information. Let's drop \"-q\" from the command invocation and\n> revisit the issue when the problematic changes are upstreamed.\n\nI think this summarizes the situation quite well. Thanks.\n\n-Stolee\n"},{"id":"438980","messageId":"3d0ff15e-469d-c659-4b32-295c7645bb8d@gmail.com","threadId":"56652","inReplyTo":"xmqqilxw1a9v.fsf@gitster.g","subject":"Re: [PATCH v4] sparse index: fix use-after-free bug in cache_tree_verify()","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2021-10-18T09:37:23Z","receivedAt":"2021-10-18T09:37:34Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Hi Junio\n\nOn 17/10/2021 06:38, Junio C Hamano wrote:\n> \"Phillip Wood via GitGitGadget\" writes:\n> \n>> [RFC] sparse index: fix use-after-free bug in cache_tree_verify()\n>> \n>> Changes since V3\n>> \n>> * removed \"-q\" from the test [1]. This is the same as V2 with a typo\n>> fixed in the commit message\n>> \n>> [1] https://lore.kernel.org/git/\n>> e281c2e2-2044-1a11-e2bc-5ab3ee92c300@gmail.com/\n> \n> Thanks. Unfortunately I've already merged the previosu version on\n> the 11th,\n\nOh sorry I'd missed that\n\n so I took the liberty of turning this round into an\n> incremental. How does this look?\nIt looks fine to me with Stolee's typo fixes\n\nThanks\n\nPhillip\n\n> ----- >8 --------- >8 --------- >8 --------- >8 -----\n> From: Phillip Wood \n> Date: Sat, 16 Oct 2021 09:07:09 +0000\n> Subject: [PATCH] t1092: run \"rebase --apply\" without \"-q\" in the test\n> \n> We run a few Git subcommands and make sure they produce identical\n> results with and without sparse-index. To this set of subcommands,\n> an earlier commit added \"rebase --apply\", but did so with the \"-q\"\n> option, in order to work around a breakge caused by a version used\n> at Microsoft with some unreleased changes.\n> \n> Because we would want to make sure the commands produce indentical\n> results, including reports given to the output that lists which\n> commits were picked, use of \"-q\" loses too much interesting\n> information. Let's drop \"-q\" from the command invocation and\n> revisit the issue when the problematic changes are upstreamed.\n> \n> Signed-off-by: Phillip Wood \n> Helped-by: Derrick Stolee \n> Signed-off-by: Junio C Hamano \n> ---\n> t/t1092-sparse-checkout-compatibility.sh | 2 +-\n> 1 file changed, 1 insertion(+), 1 deletion(-)\n> \n> diff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\n> index 80c77bb432..85d5279b33 100755\n> --- a/t/t1092-sparse-checkout-compatibility.sh\n> +++ b/t/t1092-sparse-checkout-compatibility.sh\n> @@ -484,7 +484,7 @@ test_expect_success 'checkout and reset (mixed) [sparse]' '\n> test_expect_success 'merge, cherry-pick, and rebase' '\n> \tinit_repos &&\n> \n> -\tfor OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply -q\" \"rebase --merge\"\n> +\tfor OPERATION in \"merge -m merge\" cherry-pick \"rebase --apply\" \"rebase --merge\"\n> \tdo\n> \t\ttest_all_match git checkout -B temp update-deep &&\n> \t\ttest_all_match git $OPERATION update-folder1 &&\n> \n"}]}