{"thread":{"id":"58287","subject":"[BUG] git rev-list --missing=allow-promisor","startedAt":"2022-08-10T21:34:11Z","lastAt":"2022-08-16T02:35:43Z","messageCount":5,"participants":["Andrew Olsen","Jeff King","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"461036","messageId":"CAPJmHpVssKshapGYDF-ifU1fts-jFTC-HqxnjN8meSMP3weB4g@mail.gmail.com","threadId":"58287","inReplyTo":null,"subject":"[BUG] git rev-list --missing=allow-promisor","fromName":"Andrew Olsen","fromEmail":"andrew.olsen@koordinates.com","sentAt":"2022-08-10T21:33:54Z","receivedAt":"2022-08-10T21:34:11Z","isPatch":false,"sender":{"key":"andrew.olsen@koordinates.com","avatar":"https://gravatar.com/avatar/f316140b761c57e8a68f9f93ea80a2aceac0c1d37df1b4aec24997025d441a34?d=mp&s=160"},"body":"Steps to reproduce:\n1. Create a git repository with missing+promised blobs.\nFor example, I did this:\ngit clone git@github.com:git/git.git git-no-blobs --filter=blob:none\n--depth=1 --bare\n\n--filter=blob:none - don't fetch any blobs\n--depth=1 - we don't need git's entire history, just one commit is fine\n--bare - this avoids git fetching any blobs as part of the checkout operation\n\n2. In this repository, run:\ngit rev-list HEAD --objects --missing=allow-promisor\n\nExpected outcome:\ngit rev-list prints the paths and OIDs of all the objects\n\nActual outcome:\nAny of the following:\na) git rev-list prints the paths and OIDs of all the objects\nb) git rev-list fails with \"fatal: malformed mode in tree entry\"\nc) git rev-list fails with \"fatal: too-short tree object\"\n\nDiagnosis:\nWith missing=allow-promisor, when git encounters a missing object, it\ncalls is_promisor on it, which in turn calls add_promisor_object on\nlots of things.\nIn this line in add_promisor_object, the buffer of the tree that we\nare currently traversing is freed:\nhttps://github.com/git/git/blob/master/packfile.c#L2242\nThis clearly causes problems but not in a deterministic way.\n"},{"id":"461060","messageId":"YvS50W6wku5Y/NC7@coredump.intra.peff.net","threadId":"58287","inReplyTo":"CAPJmHpVssKshapGYDF-ifU1fts-jFTC-HqxnjN8meSMP3weB4g@mail.gmail.com","subject":"Re: [BUG] git rev-list --missing=allow-promisor","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2022-08-11T08:12:01Z","receivedAt":"2022-08-11T08:12:11Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 11, 2022 at 09:33:54AM +1200, Andrew Olsen wrote:\n\n> Steps to reproduce:\n> 1. Create a git repository with missing+promised blobs.\n> For example, I did this:\n> git clone git@github.com:git/git.git git-no-blobs --filter=blob:none\n> --depth=1 --bare\n> \n> --filter=blob:none - don't fetch any blobs\n> --depth=1 - we don't need git's entire history, just one commit is fine\n> --bare - this avoids git fetching any blobs as part of the checkout operation\n> \n> 2. In this repository, run:\n> git rev-list HEAD --objects --missing=allow-promisor\n\nThanks for a clear report. I can reproduce this easily.\n\n> Expected outcome:\n> git rev-list prints the paths and OIDs of all the objects\n> \n> Actual outcome:\n> Any of the following:\n> a) git rev-list prints the paths and OIDs of all the objects\n> b) git rev-list fails with \"fatal: malformed mode in tree entry\"\n> c) git rev-list fails with \"fatal: too-short tree object\"\n\nEven better is to compile with SANITIZE=address, which reliably shows\nthat this is indeed a use-after-free.\n\n> Diagnosis:\n> With missing=allow-promisor, when git encounters a missing object, it\n> calls is_promisor on it, which in turn calls add_promisor_object on\n> lots of things.\n> In this line in add_promisor_object, the buffer of the tree that we\n> are currently traversing is freed:\n> https://github.com/git/git/blob/master/packfile.c#L2242\n\nUgh, yes. This is due to my fcc07e980b (is_promisor_object(): free tree\nbuffer after parsing, 2021-04-13). In most cases we'll have just\nallocated memory for the tree buffer in parse_object(), but occasionally\nwe'll jump into is_promisor_object() while looking at an existing tree,\nand parse_object() will just reuse the buffer cached in the struct.\n\nIt would be really nice to have some kind of reference-counting for\nthese cached buffers, but doing it everywhere may be rather complicated.\nAn easier hack to fix this area is for it to check ahead of time whether\nthere's a cached buffer we'll reuse. That only fixes this spot, but this\nfunction is rather unlike most others in that it starts looking at new\nrandom trees in the middle of an existing tree traversal (this would be\npossible in a regular tree walk if you could have circular references,\nbut you can't easily because of sha1).\n\nSo something like this makes the bug go away, though it does feel a\nlittle dirty:\n\n---\ndiff --git a/packfile.c b/packfile.c\nindex 6b0eb9048e..c3186c1a02 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -2217,7 +2217,14 @@ static int add_promisor_object(const struct object_id *oid,\n \t\t\t       void *set_)\n {\n \tstruct oidset *set = set_;\n-\tstruct object *obj = parse_object(the_repository, oid);\n+\tstruct object *obj;\n+\tint save_tree_buffer = 0;\n+\n+\tobj = lookup_object(the_repository, oid);\n+\tif (obj && obj->type == OBJ_TREE && obj->parsed)\n+\t\tsave_tree_buffer = 1;\n+\n+\tobj = parse_object(the_repository, oid);\n \tif (!obj)\n \t\treturn 1;\n \n@@ -2239,7 +2246,8 @@ static int add_promisor_object(const struct object_id *oid,\n \t\t\treturn 0;\n \t\twhile (tree_entry_gently(&desc, &entry))\n \t\t\toidset_insert(set, &entry.oid);\n-\t\tfree_tree_buffer(tree);\n+\t\tif (!save_tree_buffer)\n+\t\t\tfree_tree_buffer(tree);\n \t} else if (obj->type == OBJ_COMMIT) {\n \t\tstruct commit *commit = (struct commit *) obj;\n \t\tstruct commit_list *parents = commit->parents;\n\n-Peff\n"},{"id":"461182","messageId":"YviWO9Bhz5PU1HaL@coredump.intra.peff.net","threadId":"58287","inReplyTo":"YvS50W6wku5Y/NC7@coredump.intra.peff.net","subject":"[PATCH] is_promisor_object(): fix use-after-free of tree buffer","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2022-08-14T06:29:15Z","receivedAt":"2022-08-14T06:29:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 11, 2022 at 04:12:01AM -0400, Jeff King wrote:\n\n> So something like this makes the bug go away, though it does feel a\n> little dirty:\n\nHaving slept on this, I actually think it's the right approach, for the\nreasons given in the commit message below. And we definitely need to do\n_something_ to fix the bug, and preferably something small and un-risky,\nsince this should probably go to 'maint'. The other obvious option is\nreverting the original patch, but I think the memory savings it brought\nwould be hard to give up, and this patch should reliably fix the bug.\n\nThanks again for a clear bug report.\n\n-- >8 --\nSubject: is_promisor_object(): fix use-after-free of tree buffer\n\nSince commit fcc07e980b (is_promisor_object(): free tree buffer after\nparsing, 2021-04-13), we'll always free the buffers attached to a\n\"struct tree\" after searching them for promisor links. But there's an\nimportant case where we don't want to do so: if somebody else is already\nusing the tree!\n\nThis can happen during a \"rev-list --missing=allow-promisor\" traversal\nin a partial clone that is missing one or more trees or blobs. The\nbacktrace for the free looks like this:\n\n      #1 free_tree_buffer tree.c:147\n      #2 add_promisor_object packfile.c:2250\n      #3 for_each_object_in_pack packfile.c:2190\n      #4 for_each_packed_object packfile.c:2215\n      #5 is_promisor_object packfile.c:2272\n      #6 finish_object__ma builtin/rev-list.c:245\n      #7 finish_object builtin/rev-list.c:261\n      #8 show_object builtin/rev-list.c:274\n      #9 process_blob list-objects.c:63\n      #10 process_tree_contents list-objects.c:145\n      #11 process_tree list-objects.c:201\n      #12 traverse_trees_and_blobs list-objects.c:344\n      [...]\n\nWe're in the middle of walking through the entries of a tree object via\nprocess_tree_contents(). We see a blob (or it could even be another tree\nentry) that we don't have, so we call is_promisor_object() to check it.\nThat function loops over all of the objects in the promisor packfile,\nincluding the tree we're currently walking. When we're done with it\nthere, we free the tree buffer. But as we return to the walk in\nprocess_tree_contents(), it's still holding on to a pointer to that\nbuffer, via its tree_desc iterator, and it accesses the freed memory.\n\nEven a trivial use of \"--missing=allow-promisor\" triggers this problem,\nas the included test demonstrates (it's just a vanilla --blob:none\nclone).\n\nWe can detect this case by only freeing the tree buffer if it was\nallocated on our behalf. This is a little tricky since that happens\ninside parse_object(), and it doesn't tell us whether the object was\nalready parsed, or whether it allocated the buffer itself. But by\nchecking for an already-parsed tree beforehand, we can distinguish the\ntwo cases.\n\nThat feels a little hacky, and does incur an extra lookup in the\nobject-hash table. But that cost is fairly minimal compared to actually\nloading objects (and since we're iterating the whole pack here, we're\nlikely to be loading most objects, rather than reusing cached results).\n\nIt may also be a good direction for this function in general, as there\nare other possible optimizations that rely on doing some analysis before\nparsing:\n\n  - we could detect blobs and avoid reading their contents; they can't\n    link to other objects, but parse_object() doesn't know that we don't\n    care about checking their hashes.\n\n  - we could avoid allocating object structs entirely for most objects\n    (since we really only need them in the oidset), which would save\n    some memory.\n\n  - promisor commits could use the commit-graph rather than loading the\n    object from disk\n\nThis commit doesn't do any of those optimizations, but I think it argues\nthat this direction is reasonable, rather than relying on parse_object()\nand trying to teach it to give us more information about whether it\nparsed.\n\nThe included test fails reliably under SANITIZE=address just when\nrunning \"rev-list --missing=allow-promisor\". Checking the output isn't\nstrictly necessary to detect the bug, but it seems like a reasonable\naddition given the general lack of coverage for \"allow-promisor\" in the\ntest suite.\n\nReported-by: Andrew Olsen <andrew.olsen@koordinates.com>\nSigned-off-by: Jeff King <peff@peff.net>\n---\nThe bug is in v2.32.0. I prepared this directly on top of fcc07e980b,\nbut it should apply cleanly to any recent maint or master tips.\n\n packfile.c               | 15 +++++++++++++--\n t/t5616-partial-clone.sh |  7 +++++++\n 2 files changed, 20 insertions(+), 2 deletions(-)\n\ndiff --git a/packfile.c b/packfile.c\nindex b79cbc8cd4..1556a5c3f3 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -2225,7 +2225,17 @@ static int add_promisor_object(const struct object_id *oid,\n \t\t\t       void *set_)\n {\n \tstruct oidset *set = set_;\n-\tstruct object *obj = parse_object(the_repository, oid);\n+\tstruct object *obj;\n+\tint we_parsed_object;\n+\n+\tobj = lookup_object(the_repository, oid);\n+\tif (obj && obj->parsed) {\n+\t\twe_parsed_object = 0;\n+\t} else {\n+\t\twe_parsed_object = 1;\n+\t\tobj = parse_object(the_repository, oid);\n+\t}\n+\n \tif (!obj)\n \t\treturn 1;\n \n@@ -2247,7 +2257,8 @@ static int add_promisor_object(const struct object_id *oid,\n \t\t\treturn 0;\n \t\twhile (tree_entry_gently(&desc, &entry))\n \t\t\toidset_insert(set, &entry.oid);\n-\t\tfree_tree_buffer(tree);\n+\t\tif (we_parsed_object)\n+\t\t\tfree_tree_buffer(tree);\n \t} else if (obj->type == OBJ_COMMIT) {\n \t\tstruct commit *commit = (struct commit *) obj;\n \t\tstruct commit_list *parents = commit->parents;\ndiff --git a/t/t5616-partial-clone.sh b/t/t5616-partial-clone.sh\nindex 5cb415386e..9c0e422a14 100755\n--- a/t/t5616-partial-clone.sh\n+++ b/t/t5616-partial-clone.sh\n@@ -49,6 +49,13 @@ test_expect_success 'do partial clone 1' '\n \ttest \"$(git -C pc1 config --local remote.origin.partialclonefilter)\" = \"blob:none\"\n '\n \n+test_expect_success 'rev-list --missing=allow-promisor on partial clone' '\n+\tgit -C pc1 rev-list --objects --missing=allow-promisor HEAD >actual &&\n+\tgit -C pc1 rev-list --objects --missing=print HEAD >expect.raw &&\n+\tgrep -v \"^?\" expect.raw >expect &&\n+\ttest_cmp expect actual\n+'\n+\n test_expect_success 'verify that .promisor file contains refs fetched' '\n \tls pc1/.git/objects/pack/pack-*.promisor >promisorlist &&\n \ttest_line_count = 1 promisorlist &&\n-- \n2.37.1.926.g40145d0bb9\n\n"},{"id":"461216","messageId":"xmqqmtc63wdf.fsf@gitster.g","threadId":"58287","inReplyTo":"YviWO9Bhz5PU1HaL@coredump.intra.peff.net","subject":"Re: [PATCH] is_promisor_object(): fix use-after-free of tree buffer","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-08-15T05:32:12Z","receivedAt":"2022-08-15T05:32:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> This can happen during a \"rev-list --missing=allow-promisor\" traversal\n> in a partial clone that is missing one or more trees or blobs. The\n> backtrace for the free looks like this:\n>\n>       #1 free_tree_buffer tree.c:147\n>       #2 add_promisor_object packfile.c:2250\n>       #3 for_each_object_in_pack packfile.c:2190\n>       #4 for_each_packed_object packfile.c:2215\n>       #5 is_promisor_object packfile.c:2272\n>       #6 finish_object__ma builtin/rev-list.c:245\n>       #7 finish_object builtin/rev-list.c:261\n>       #8 show_object builtin/rev-list.c:274\n>       #9 process_blob list-objects.c:63\n>       #10 process_tree_contents list-objects.c:145\n>       #11 process_tree list-objects.c:201\n>       #12 traverse_trees_and_blobs list-objects.c:344\n>       [...]\n>\n> We're in the middle of walking through the entries of a tree object via\n> process_tree_contents(). We see a blob (or it could even be another tree\n> entry) that we don't have, so we call is_promisor_object() to check it.\n> That function loops over all of the objects in the promisor packfile,\n> including the tree we're currently walking.\n\nI forgot that the above \"loops over\" happens only once to populate\nthe oidset hashtable, and briefly wondered if we are being grossly\ninefficient by scanning pack .idx file each time we encounter a\nmissing object.  \"Upon first call, that function loops over\n... walking, to prepare a hashtable to answer if any object id is\nreferred to by an object in promisor packs\" would have helped ;-). \n\n> It may also be a good direction for this function in general, as there\n> are other possible optimizations that rely on doing some analysis before\n> parsing:\n>\n>   - we could detect blobs and avoid reading their contents; they can't\n>     link to other objects, but parse_object() doesn't know that we don't\n>     care about checking their hashes.\n>\n>   - we could avoid allocating object structs entirely for most objects\n>     (since we really only need them in the oidset), which would save\n>     some memory.\n>\n>   - promisor commits could use the commit-graph rather than loading the\n>     object from disk\n>\n> This commit doesn't do any of those optimizations, but I think it argues\n> that this direction is reasonable, rather than relying on parse_object()\n> and trying to teach it to give us more information about whether it\n> parsed.\n\nYeah, all of the future bits sound sensible. \n\nWill queue.\n\nThanks.\n"},{"id":"461258","messageId":"YvrOWY2x19G1jCTK@coredump.intra.peff.net","threadId":"58287","inReplyTo":"xmqqmtc63wdf.fsf@gitster.g","subject":"Re: [PATCH] is_promisor_object(): fix use-after-free of tree buffer","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2022-08-15T22:53:13Z","receivedAt":"2022-08-16T02:35:43Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Aug 14, 2022 at 10:32:12PM -0700, Junio C Hamano wrote:\n\n> > We're in the middle of walking through the entries of a tree object via\n> > process_tree_contents(). We see a blob (or it could even be another tree\n> > entry) that we don't have, so we call is_promisor_object() to check it.\n> > That function loops over all of the objects in the promisor packfile,\n> > including the tree we're currently walking.\n> \n> I forgot that the above \"loops over\" happens only once to populate\n> the oidset hashtable, and briefly wondered if we are being grossly\n> inefficient by scanning pack .idx file each time we encounter a\n> missing object.  \"Upon first call, that function loops over\n> ... walking, to prepare a hashtable to answer if any object id is\n> referred to by an object in promisor packs\" would have helped ;-).\n\nRight. When you have worked in an area, sometimes it is easy to forget\nwhich things are common knowledge and which are not. :) I don't mind at\nall if you want to amend the commit message as you apply.\n\n> > It may also be a good direction for this function in general, as there\n> > are other possible optimizations that rely on doing some analysis before\n> > parsing:\n> >\n> >   - we could detect blobs and avoid reading their contents; they can't\n> >     link to other objects, but parse_object() doesn't know that we don't\n> >     care about checking their hashes.\n> >\n> >   - we could avoid allocating object structs entirely for most objects\n> >     (since we really only need them in the oidset), which would save\n> >     some memory.\n> >\n> >   - promisor commits could use the commit-graph rather than loading the\n> >     object from disk\n> >\n> > This commit doesn't do any of those optimizations, but I think it argues\n> > that this direction is reasonable, rather than relying on parse_object()\n> > and trying to teach it to give us more information about whether it\n> > parsed.\n> \n> Yeah, all of the future bits sound sensible. \n\nI very intentionally didn't work on those things yet, because I wanted\nto make sure we got a simple fix in as quickly as possible. That said, I\ndon't have immediate plans for them. They are perhaps not quite small\nenough for #leftoverbits, but I think they might also be nice bite-sized\nchunks for somebody wanting to get their feet wet in that part of the\ncode.\n\n-Peff\n"}]}