Re: [BUG] Segfault on git describe

[Jeff King <peff@peff.net>]

On Wed, Mar 19, 2014 at 10:34:29PM +0000, Dragos Foianu wrote:

> The name_rev function recursively calls itself which is why the backtrace is
> so big. Unfortunately, for repos with long histories it can lead to Stack
> Overflows. This is pretty much what happened in your case.
> 
> I tested it on my computer and I get the same results. I managed to get it
> working by doubling my default stacksize:
> 
> ulimit -S -s 16192
> 
> Considering your project is a very large one and merely allocating a few
> more resources fixes the problem, I'm not sure it warrants rewriting the
> function to use less stack. You will have to wait for one of the maintainers
> to give you a definitive answer.

Thanks for looking into the problem.

As a general rule, I think we are interested in reducing recursion in
functions which can go O(depth of history) or deeper. I'd say that
O(lg(depth of history)) is probably OK.

There is some precedent in 941ba8d (Eliminate recursion in
setting/clearing marks in commit list, 2012-01-14), for example.

Also, in:

  abe601b (sha1_file: remove recursion in unpack_entry, 2013-03-27)

  790d96c (sha1_file: remove recursion in packed_object_info,
  2013-03-25)

  2baad22 (index-pack: eliminate recursion in find_unresolved_deltas,
  2012-01-14)

though I think those recurse in the size of delta chain, which is not
nearly so big.

So I think we'd be happy to see it converted to an iterative process
(probably with a stack on the heap). In addition to name-rev, I believe
that "tag --contains" will recurse down the longest history path, too (I
think there may have been experimental patches for the latter, but you'd
have to search the list archive).

-Peff