threads / rfc / 37834

RFC patchcache-tree: avoid infinite loop on zero-entry tree

Subject: [RFC/PATCH] cache-tree: avoid infinite loop on zero-entry tree

## tl;dr

3 messages between Oct 29, 2014 and Oct 29, 2014. Diffs are folded; open one to read it.

replies: 2people: 2as markdown or json

Jeff King· Oct 29, 2014, 17:11 UTC · lore

The loop in cache-tree's update_one iterates over all the entries in the index. For each one, we find the cache-tree subtree which represents our path (creating it if necessary), and then recurse into update_one again. The return value we get is the number of index entries that belonged in that subtree. So for example, with entries:

    a/one
    a/two
    b/one

We start by processing the first entry, "a/one".  We would
find the subtree for "a" and recurse into update_one. That
would then handle "a/one" and "a/two", and return the value
2. The parent function then skips past the 2 handled
entries, and we continue by processing "b/one".

If the recursed-into update_one ever returns 0, then we make no forward progress in our loop. We would process "a/one" over and over, infinitely.

This should not happen normally. Any subtree we create must have at least one path in it (the one that we are processing!). However, we may also reuse a cache-tree entry we found in the on-disk index. For the same reason, this should also never have zero entries. However, certain buggy versions of libgit2 could produce such bogus cache-tree records. The libgit2 bug has since been fixed, but it does not hurt to protect ourselves against bogus input coming from the on-disk data structures.

Note that this is not a die("BUG") or assert, because it is not an internal bug, but rather a corrupted on-disk structure. It's possible that we could even recover from it (by throwing out the bogus cache-tree entry), but it is not worth the effort; the important thing is that we report an error instead of looping infinitely.

Signed-off-by: Jeff King <peff@peff.net>
---
I'm a little iffy on this just because it is fixing one particular bug,
and I am sure there are probably a bunch of other ways to have a bogus
index. Fundamentally, I think we pretty much trust that the index was
not maliciously generated (unlike packfiles, for instance, which can
come from elsewhere).  Still, this is one step closer to safe, and the
bug was seen in the wild, so maybe it is worth doing.

We could alternatively (or in addition) reject 0-entry cache trees when reading them from disk. The trick, though, is that it is not just records with 0 entries, but ones where the sum of the entries and subtree entries is 0. Given that it is not something we expect to happen, it is easier to catch it here. And we know there can be no regressions for missed corner cases, because the case we are catching here would _always_ have gone into an infinite loop before this patch.

 cache-tree.c | 2 ++
 1 file changed, 2 insertions(+)

Show changes to cache-tree.c +2 −0

diff --git a/cache-tree.c b/cache-tree.c
index 215202c..32772b9 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -303,6 +303,8 @@ static int update_one(struct cache_tree *it,
 				    flags);
 		if (subcnt < 0)
 			return subcnt;
+		if (!subcnt)
+			die("index cache-tree records empty sub-tree");
 		i += subcnt;
 		sub->count = subcnt; /* to be used in the next loop */
 		*skip_count += subskip;

-- 
2.1.2.596.g7379948

Junio C Hamano· Oct 29, 2014, 18:50 UTC · re: Jeff King · lore

Re: [RFC/PATCH] cache-tree: avoid infinite loop on zero-entry tree

Jeff King <peff@peff.net> writes:

Show 6 quoted lines

> I'm a little iffy on this just because it is fixing one particular bug,
> and I am sure there are probably a bunch of other ways to have a bogus
> index. Fundamentally, I think we pretty much trust that the index was
> not maliciously generated (unlike packfiles, for instance, which can
> come from elsewhere).  Still, this is one step closer to safe, and the
> bug was seen in the wild, so maybe it is worth doing.

Is it cheap to sanity-check the input when we map in the cache-tree upon read_cache()? Then we can just invalidate the cache-tree, either in its entirety (easy) or just the bogus subpart (maybe not worth doing).

Show 7 quoted lines

> We could alternatively (or in addition) reject 0-entry cache trees when
> reading them from disk. The trick, though, is that it is not just
> records with 0 entries, but ones where the sum of the entries and
> subtree entries is 0. Given that it is not something we expect to
> happen, it is easier to catch it here. And we know there can be no
> regressions for missed corner cases, because the case we are catching
> here would _always_ have gone into an infinite loop before this patch.

OK. I wonder if we can instead die here but propagate the error back up the callchain and have the ultimate caller rebuild the cache tree without paying attention to the existing data that we now know is bogus.

Show 16 quoted lines

>  cache-tree.c | 2 ++
>  1 file changed, 2 insertions(+)
>
> diff --git a/cache-tree.c b/cache-tree.c
> index 215202c..32772b9 100644
> --- a/cache-tree.c
> +++ b/cache-tree.c
> @@ -303,6 +303,8 @@ static int update_one(struct cache_tree *it,
>  				    flags);
>  		if (subcnt < 0)
>  			return subcnt;
> +		if (!subcnt)
> +			die("index cache-tree records empty sub-tree");
>  		i += subcnt;
>  		sub->count = subcnt; /* to be used in the next loop */
>  		*skip_count += subskip;

Jeff King· Oct 29, 2014, 18:52 UTC · re: Junio C Hamano · lore

Re: [RFC/PATCH] cache-tree: avoid infinite loop on zero-entry tree

On Wed, Oct 29, 2014 at 11:50:12AM -0700, Junio C Hamano wrote:

Show 13 quoted lines

> Jeff King <peff@peff.net> writes:
> 
> > I'm a little iffy on this just because it is fixing one particular bug,
> > and I am sure there are probably a bunch of other ways to have a bogus
> > index. Fundamentally, I think we pretty much trust that the index was
> > not maliciously generated (unlike packfiles, for instance, which can
> > come from elsewhere).  Still, this is one step closer to safe, and the
> > bug was seen in the wild, so maybe it is worth doing.
> 
> Is it cheap to sanity-check the input when we map in the cache-tree
> upon read_cache()?  Then we can just invalidate the cache-tree,
> either in its entirety (easy) or just the bogus subpart (maybe not
> worth doing).

I think it is not super-expensive, but it is not as easy as:

  if (!it->entry_count)
	return -1;

Show 12 quoted lines

> > We could alternatively (or in addition) reject 0-entry cache trees when
> > reading them from disk. The trick, though, is that it is not just
> > records with 0 entries, but ones where the sum of the entries and
> > subtree entries is 0. Given that it is not something we expect to
> > happen, it is easier to catch it here. And we know there can be no
> > regressions for missed corner cases, because the case we are catching
> > here would _always_ have gone into an infinite loop before this patch.
> 
> OK.  I wonder if we can instead die here but propagate the error
> back up the callchain and have the ultimate caller rebuild the cache
> tree without paying attention to the existing data that we now know
> is bogus.

Yeah, that would make sense to me, but I was not familiar with the cache-tree code to do it easily (and given that this is not something that should ever happen, I didn't want to spend time digging in).

I can provide you with a real-world test case if you want to explore it further.

-Peff