[PATCH 01/10] tree-walk: reduce stack size for recursive functions

The traverse_trees() and traverse_trees_recursive() functions call each other recursively. In a deep tree, this can result in running out of stack space and crashing.

There's obviously going to be some limit here based on available stack, but the problem is exacerbated by a few large structs, many of which we over-allocate. For example, in traverse_trees() we store a name_entry and tree_desc_x per tree, both of which contain an object_id (which is now 32 bytes). And we allocate 8 of them (from MAX_TRAVERSE_TREES), even though many traversals will only look at 1 or 2.

Interestingly, we used to allocate these on the heap, prior to 8dd40c0472 (traverse_trees(): use stack array for name entries, 2020-01-30). That commit was trying to simplify away allocation size computations, and naively assumed that the sizes were small enough not to matter. And they don't in normal cases, but on my stock Debian system I see a crash running "git archive" on a tree with ~3600 entries. That's deep enough we wouldn't see it in practice, but probably shallow enough that we'd prefer not to make it a hard limit. Especially because other systems may have even smaller stacks.

We can replace these stack variables with a few malloc invocations. This reduces the stack sizes for the two functions from 1128 and 752 bytes, respectively, down to 40 and 92 bytes. That allows a depth of ~13000 on my machine (the improvement isn't in linear proportion because my numbers don't count the size of parameters and other function overhead).

The possible downsides are:

  1. We now have to remember to free(). But both functions have an easy
     single exit (and already had to clean up other bits anyway).

  2. The extra malloc()/free() overhead might be measurable. I tested
     this by setting up a 3000-depth tree with a single blob and running
     "git archive" on it. After switching to the heap, it consistently
     runs 2-3% faster! Presumably this is because the 1K+ of wasted
     stack space penalized memory caches.

On a more real-world case like linux.git, the speed difference isn't measurable at all, simply because most trees aren't that deep and there's so much other work going on (like accessing the objects themselves). So the improvement I saw should be taken as evidence that we're not making anything worse, but isn't really that interesting on its own. The main motivation here is that we're now less likely to run out of stack space and crash.

Signed-off-by: Jeff King <peff@peff.net>
---
 tree-walk.c    | 10 ++++++----
 unpack-trees.c |  9 +++++++--
 2 files changed, 13 insertions(+), 6 deletions(-)