{"thread":{"id":"37834","subject":"[RFC/PATCH] cache-tree: avoid infinite loop on zero-entry tree","startedAt":"2014-10-29T17:11:58Z","lastAt":"2014-10-29T18:52:50Z","messageCount":3,"participants":["Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"251178","messageId":"20141029171158.GA32188@peff.net","threadId":"37834","inReplyTo":null,"subject":"[RFC/PATCH] cache-tree: avoid infinite loop on zero-entry tree","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-10-29T17:11:58Z","receivedAt":"2014-10-29T17:11:58Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The loop in cache-tree's update_one iterates over all the\nentries in the index. For each one, we find the cache-tree\nsubtree which represents our path (creating it if\nnecessary), and then recurse into update_one again. The\nreturn value we get is the number of index entries that\nbelonged in that subtree. So for example, with entries:\n\n    a/one\n    a/two\n    b/one\n\nWe start by processing the first entry, \"a/one\".  We would\nfind the subtree for \"a\" and recurse into update_one. That\nwould then handle \"a/one\" and \"a/two\", and return the value\n2. The parent function then skips past the 2 handled\nentries, and we continue by processing \"b/one\".\n\nIf the recursed-into update_one ever returns 0, then we make\nno forward progress in our loop. We would process \"a/one\"\nover and over, infinitely.\n\nThis should not happen normally. Any subtree we create must\nhave at least one path in it (the one that we are\nprocessing!). However, we may also reuse a cache-tree entry\nwe found in the on-disk index. For the same reason, this\nshould also never have zero entries. However, certain buggy\nversions of libgit2 could produce such bogus cache-tree\nrecords. The libgit2 bug has since been fixed, but it does\nnot hurt to protect ourselves against bogus input coming\nfrom the on-disk data structures.\n\nNote that this is not a die(\"BUG\") or assert, because it is\nnot an internal bug, but rather a corrupted on-disk\nstructure. It's possible that we could even recover from it\n(by throwing out the bogus cache-tree entry), but it is not\nworth the effort; the important thing is that we report an\nerror instead of looping infinitely.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nI'm a little iffy on this just because it is fixing one particular bug,\nand I am sure there are probably a bunch of other ways to have a bogus\nindex. Fundamentally, I think we pretty much trust that the index was\nnot maliciously generated (unlike packfiles, for instance, which can\ncome from elsewhere).  Still, this is one step closer to safe, and the\nbug was seen in the wild, so maybe it is worth doing.\n\nWe could alternatively (or in addition) reject 0-entry cache trees when\nreading them from disk. The trick, though, is that it is not just\nrecords with 0 entries, but ones where the sum of the entries and\nsubtree entries is 0. Given that it is not something we expect to\nhappen, it is easier to catch it here. And we know there can be no\nregressions for missed corner cases, because the case we are catching\nhere would _always_ have gone into an infinite loop before this patch.\n\n cache-tree.c | 2 ++\n 1 file changed, 2 insertions(+)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 215202c..32772b9 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -303,6 +303,8 @@ static int update_one(struct cache_tree *it,\n \t\t\t\t    flags);\n \t\tif (subcnt < 0)\n \t\t\treturn subcnt;\n+\t\tif (!subcnt)\n+\t\t\tdie(\"index cache-tree records empty sub-tree\");\n \t\ti += subcnt;\n \t\tsub->count = subcnt; /* to be used in the next loop */\n \t\t*skip_count += subskip;\n-- \n2.1.2.596.g7379948\n"},{"id":"251184","messageId":"xmqqppdayal7.fsf@gitster.dls.corp.google.com","threadId":"37834","inReplyTo":"20141029171158.GA32188@peff.net","subject":"Re: [RFC/PATCH] cache-tree: avoid infinite loop on zero-entry tree","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-10-29T18:50:12Z","receivedAt":"2014-10-29T18:50:12Z","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> I'm a little iffy on this just because it is fixing one particular bug,\n> and I am sure there are probably a bunch of other ways to have a bogus\n> index. Fundamentally, I think we pretty much trust that the index was\n> not maliciously generated (unlike packfiles, for instance, which can\n> come from elsewhere).  Still, this is one step closer to safe, and the\n> bug was seen in the wild, so maybe it is worth doing.\n\nIs it cheap to sanity-check the input when we map in the cache-tree\nupon read_cache()?  Then we can just invalidate the cache-tree,\neither in its entirety (easy) or just the bogus subpart (maybe not\nworth doing).\n\n> We could alternatively (or in addition) reject 0-entry cache trees when\n> reading them from disk. The trick, though, is that it is not just\n> records with 0 entries, but ones where the sum of the entries and\n> subtree entries is 0. Given that it is not something we expect to\n> happen, it is easier to catch it here. And we know there can be no\n> regressions for missed corner cases, because the case we are catching\n> here would _always_ have gone into an infinite loop before this patch.\n\nOK.  I wonder if we can instead die here but propagate the error\nback up the callchain and have the ultimate caller rebuild the cache\ntree without paying attention to the existing data that we now know\nis bogus.\n\n>  cache-tree.c | 2 ++\n>  1 file changed, 2 insertions(+)\n>\n> diff --git a/cache-tree.c b/cache-tree.c\n> index 215202c..32772b9 100644\n> --- a/cache-tree.c\n> +++ b/cache-tree.c\n> @@ -303,6 +303,8 @@ static int update_one(struct cache_tree *it,\n>  \t\t\t\t    flags);\n>  \t\tif (subcnt < 0)\n>  \t\t\treturn subcnt;\n> +\t\tif (!subcnt)\n> +\t\t\tdie(\"index cache-tree records empty sub-tree\");\n>  \t\ti += subcnt;\n>  \t\tsub->count = subcnt; /* to be used in the next loop */\n>  \t\t*skip_count += subskip;\n"},{"id":"251185","messageId":"20141029185249.GA26740@peff.net","threadId":"37834","inReplyTo":"xmqqppdayal7.fsf@gitster.dls.corp.google.com","subject":"Re: [RFC/PATCH] cache-tree: avoid infinite loop on zero-entry tree","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-10-29T18:52:50Z","receivedAt":"2014-10-29T18:52:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 29, 2014 at 11:50:12AM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > I'm a little iffy on this just because it is fixing one particular bug,\n> > and I am sure there are probably a bunch of other ways to have a bogus\n> > index. Fundamentally, I think we pretty much trust that the index was\n> > not maliciously generated (unlike packfiles, for instance, which can\n> > come from elsewhere).  Still, this is one step closer to safe, and the\n> > bug was seen in the wild, so maybe it is worth doing.\n> \n> Is it cheap to sanity-check the input when we map in the cache-tree\n> upon read_cache()?  Then we can just invalidate the cache-tree,\n> either in its entirety (easy) or just the bogus subpart (maybe not\n> worth doing).\n\nI think it is not super-expensive, but it is not as easy as:\n\n  if (!it->entry_count)\n\treturn -1;\n\n> > We could alternatively (or in addition) reject 0-entry cache trees when\n> > reading them from disk. The trick, though, is that it is not just\n> > records with 0 entries, but ones where the sum of the entries and\n> > subtree entries is 0. Given that it is not something we expect to\n> > happen, it is easier to catch it here. And we know there can be no\n> > regressions for missed corner cases, because the case we are catching\n> > here would _always_ have gone into an infinite loop before this patch.\n> \n> OK.  I wonder if we can instead die here but propagate the error\n> back up the callchain and have the ultimate caller rebuild the cache\n> tree without paying attention to the existing data that we now know\n> is bogus.\n\nYeah, that would make sense to me, but I was not familiar with the\ncache-tree code to do it easily (and given that this is not something\nthat should ever happen, I didn't want to spend time digging in).\n\nI can provide you with a real-world test case if you want to explore it\nfurther.\n\n-Peff\n"}]}