patch, 3 partssome minor memory allocation cleanups

> We take a "dst" buffer to write into, but there's no matching "len"
> parameter. The hidden assumption is that normalizing always makes things
> smaller, so we're OK as long as "dst" is at least as big as "src". Let's
> document that explicitly.
>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
>  path.c | 2 ++
>  1 file changed, 2 insertions(+)
>
> diff --git a/path.c b/path.c
> index a76eec8b96..88cf593007 100644
> --- a/path.c
> +++ b/path.c
> @@ -1077,6 +1077,8 @@ const char *remove_leading_path(const char *in, const char *prefix)
>
>  /*
>   * It is okay if dst == src, but they should not overlap otherwise.
> + * The "dst" buffer must be at least as long as "src"; normalizing may shrink
> + * the size of the path, but will never grow it.

>   *
>   * Performs the following normalizations on src, storing the result in dst:
>   * - Ensures that components are separated by '/' (Windows only)
> --
> 2.25.0.515.gaba5347bc6

> > @@ -1077,6 +1077,8 @@ const char *remove_leading_path(const char *in, const char *prefix)
> >
> >  /*
> >   * It is okay if dst == src, but they should not overlap otherwise.
> > + * The "dst" buffer must be at least as long as "src"; normalizing may shrink
> > + * the size of the path, but will never grow it.
> 
> Thanks for documenting this. It's quite helpful, and hopefully should
> prevent bugs like the one you alluded to in your cover letter from
> getting in in the future.

>
> We heap-allocate our arrays of name_entry structs, etc, with one entry
> per tree we're asked to traverse. The code does a raw multiplication in
> the xmalloc() call, which I find when auditing for integer overflows
> during allocation.
>
> We could "fix" this by using ALLOC_ARRAY() instead. But as it turns out,
> the maximum size of these arrays is limited at compile time:
>
>   - merge_trees() always passes in 3 trees
>
>   - unpack_trees() and its brethren never pass in more than
>     MAX_UNPACK_TREES
>
> So we can simplify even further by just using a stack array and bounding
> it with MAX_UNPACK_TREES. There should be no concern with overflowing
> the stack, since MAX_UNPACK_TREES is only 8 and the structs themselves
> are small.
>
> Note that since we're replacing xcalloc(), we have to move one of the
> NULL initializations into a loop.
>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
>
> This does increase the coupling between tree-walk and unpack-trees a
> bit. I'd be OK just switching to ALLOC_ARRAY(), too. I doubt the
> performance improvement is measurable, and the cleanup free() calls are
> already there.

>  tree-walk.c | 13 ++++++++-----
>  1 file changed, 8 insertions(+), 5 deletions(-)
>
> diff --git a/tree-walk.c b/tree-walk.c
> index d5a8e096a6..3093cf7098 100644
> --- a/tree-walk.c
> +++ b/tree-walk.c
> @@ -410,15 +410,20 @@ int traverse_trees(struct index_state *istate,
>                    struct traverse_info *info)
>  {
>         int error = 0;
> -       struct name_entry *entry = xmalloc(n*sizeof(*entry));
> +       struct name_entry entry[MAX_UNPACK_TREES];
>         int i;
> -       struct tree_desc_x *tx = xcalloc(n, sizeof(*tx));
> +       struct tree_desc_x tx[ARRAY_SIZE(entry)];
>         struct strbuf base = STRBUF_INIT;
>         int interesting = 1;
>         char *traverse_path;
>
> -       for (i = 0; i < n; i++)
> +       if (n >= ARRAY_SIZE(entry))
> +               BUG("traverse_trees() called with too many trees (%d)", n);
> +
> +       for (i = 0; i < n; i++) {
>                 tx[i].d = t[i];
> +               tx[i].skip = NULL;
> +       }
>
>         if (info->prev) {
>                 strbuf_make_traverse_path(&base, info->prev,
> @@ -506,10 +511,8 @@ int traverse_trees(struct index_state *istate,
>                         if (mask & (1ul << i))
>                                 update_extended_entry(tx + i, entry + i);
>         }
> -       free(entry);
>         for (i = 0; i < n; i++)
>                 free_extended_entry(tx + i);
> -       free(tx);
>         free(traverse_path);
>         info->traverse_path = NULL;
>         strbuf_release(&base);
> --
> 2.25.0.515.gaba5347bc6

> > This does increase the coupling between tree-walk and unpack-trees a
> > bit. I'd be OK just switching to ALLOC_ARRAY(), too. I doubt the
> > performance improvement is measurable, and the cleanup free() calls are
> > already there.
> 
> Could we undo this cyclic dependency between tree-walk and
> unpack-trees by defining MAX_TRAVERSE_TREES in tree-walk.h, making
> MAX_UNPACK_TREES in unpack-trees.h be defined to MAX_TRAVERSE_TREES,
> and remove the include of unpack-trees.h in tree-walk.c?

>
> On Thu, Jan 30, 2020 at 06:57:26AM -0800, Elijah Newren wrote:
>
> > > This does increase the coupling between tree-walk and unpack-trees a
> > > bit. I'd be OK just switching to ALLOC_ARRAY(), too. I doubt the
> > > performance improvement is measurable, and the cleanup free() calls are
> > > already there.
> >
> > Could we undo this cyclic dependency between tree-walk and
> > unpack-trees by defining MAX_TRAVERSE_TREES in tree-walk.h, making
> > MAX_UNPACK_TREES in unpack-trees.h be defined to MAX_TRAVERSE_TREES,
> > and remove the include of unpack-trees.h in tree-walk.c?
>
> I don't mind doing that, but I had a hard time trying to write a commit
> message. I.e., I can explain the current use of MAX_UNPACK_TREES here,
> or defining MAX_TRAVERSE_TREES as MAX_UNPACK_TREES by saying "this is an
> arbitrary limit, but it's the highest value any caller would use with
> us".
>
> But to define MAX_UNPACK_TREES in terms of MAX_TRAVERSE_TREES, I feel
> we've created a circular reasoning in the justification.

> I'm not even sure whether the current value of 8 is meaningful. It comes
> from this commit:
>
>   commit ca885a4fe6444bed840295378848904106c87c85
>   Author: Junio C Hamano <gitster@pobox.com>
>   Date:   Thu Mar 13 22:07:18 2008 -0700
>
>       read-tree() and unpack_trees(): use consistent limit
>
>       read-tree -m can read up to MAX_TREES, which was arbitrarily set to 8 since
>       August 2007 (4 is needed to deal with 2 merge-base case).
>
>       However, the updated unpack_trees() code had an advertised limit of 4
>       (which it enforced).  In reality the code was prepared to take only 3
>       trees and giving 4 caused it to stomp on its stack.  Rename the MAX_TREES
>       constant to MAX_UNPACK_TREES, move it to the unpack-trees.h common header
>       file, and use it from both places to avoid future confusion.
>
> which kind of makes me wonder if we should just go back to calling it
> MAX_TREES. I guess that's too vague, though.
>
> So I dunno. It would be easy to do as you asked, but I'm not convinced
> it actually untangles anything meaningful.

> As far as I can tell, before your change, we can remove the
>    #include "unpack-trees.h"
> from tree-walk.c; nothing uses it.  I do like snipping includes and
> dependencies where they aren't necessary, and this one seems like one
> that could be removed.

>
> On Fri, Jan 31, 2020 at 10:52:30AM -0800, Elijah Newren wrote:
>
> > As far as I can tell, before your change, we can remove the
> >    #include "unpack-trees.h"
> > from tree-walk.c; nothing uses it.  I do like snipping includes and
> > dependencies where they aren't necessary, and this one seems like one
> > that could be removed.
>
> Yeah, I think that is the case.
>
> > But, it's not a big deal; if you want to leave that for future work
> > for someone else (perhaps even asking me to turn my paragraph above
> > into a commit message that rips it out and defines one #define in
> > terms of the other), that's fine.
>
> Let's do it now while we're thinking about it. How about the patch below
> on top of my series?
>
> -- >8 --
> Subject: [PATCH] tree-walk.c: break circular dependency with unpack-trees
>
> The unpack-trees API depends on the tree-walk API. But we've recently
> introduced a dependency in tree-walk.c on MAX_UNPACK_TREES, which
> doesn't otherwise care about unpack-trees at all.
>
> Let's break that dependency by reversing the constants: we'll introduce
> a new MAX_TRAVERSE_TREES which belongs to the tree-walk API. And then we
> can define MAX_UNPACK_TREES in terms of that (since unpack-trees cannot
> possibly work with more trees than it can traverse at once via
> tree-walk).
>
> The value for both will remain at 8. This is somewhat arbitrary and
> probably more than is necessary, per ca885a4fe6 (read-tree() and
> unpack_trees(): use consistent limit, 2008-03-13), but there's not
> really any pressing need to reduce it.
>
> Suggested-by: Elijah Newren <newren@gmail.com>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
>  tree-walk.c    | 3 +--
>  tree-walk.h    | 2 ++
>  unpack-trees.h | 2 +-
>  3 files changed, 4 insertions(+), 3 deletions(-)
>
> diff --git a/tree-walk.c b/tree-walk.c
> index 3093cf7098..bb0ad34c54 100644
> --- a/tree-walk.c
> +++ b/tree-walk.c
> @@ -1,6 +1,5 @@
>  #include "cache.h"
>  #include "tree-walk.h"
> -#include "unpack-trees.h"
>  #include "dir.h"
>  #include "object-store.h"
>  #include "tree.h"
> @@ -410,7 +409,7 @@ int traverse_trees(struct index_state *istate,
>                    struct traverse_info *info)
>  {
>         int error = 0;
> -       struct name_entry entry[MAX_UNPACK_TREES];
> +       struct name_entry entry[MAX_TRAVERSE_TREES];
>         int i;
>         struct tree_desc_x tx[ARRAY_SIZE(entry)];
>         struct strbuf base = STRBUF_INIT;
> diff --git a/tree-walk.h b/tree-walk.h
> index 826396c8ed..a5058469e9 100644
> --- a/tree-walk.h
> +++ b/tree-walk.h
> @@ -3,6 +3,8 @@
>
>  #include "cache.h"
>
> +#define MAX_TRAVERSE_TREES 8
> +
>  /**
>   * The tree walking API is used to traverse and inspect trees.
>   */
> diff --git a/unpack-trees.h b/unpack-trees.h
> index ca94a421a5..ae1557fb80 100644
> --- a/unpack-trees.h
> +++ b/unpack-trees.h
> @@ -6,7 +6,7 @@
>  #include "string-list.h"
>  #include "tree-walk.h"
>
> -#define MAX_UNPACK_TREES 8
> +#define MAX_UNPACK_TREES MAX_TRAVERSE_TREES
>
>  struct cache_entry;
>  struct unpack_trees_options;
> --
> 2.25.0.538.g1d5d7023b0

>
> These are a result of me poking at the results of:
>
>   git grep 'x[mc]alloc.*[+*] '
>
> looking for any buffer allocation computations that could overflow (and
> hence under-allocate).
>
> There are a few hits left after this in the commit-graph code. Those
> will be dealt with in a separate series (coming soon!) since they have
> other problems, as discussed in:
>
>   https://lore.kernel.org/git/20191027042116.GA5801@sigill.intra.peff.net/
>
> (those have to do with normalize_path_copy(), hence the only
> semi-related documentation patch here).
>
>   [1/3]: normalize_path_copy(): document "dst" size expectations
>   [2/3]: walker_fetch(): avoid raw array length computation
>   [3/3]: traverse_trees(): use stack array for name entries
>
>  path.c      |  2 ++
>  tree-walk.c | 13 ++++++++-----
>  walker.c    |  4 +++-
>  3 files changed, 13 insertions(+), 6 deletions(-)
>
> -Peff

> These are a result of me poking at the results of:
>
>   git grep 'x[mc]alloc.*[+*] '
>
> looking for any buffer allocation computations that could overflow (and
> hence under-allocate).
>
> There are a few hits left after this in the commit-graph code. Those
> will be dealt with in a separate series (coming soon!) since they have
> other problems, as discussed in:

>   https://lore.kernel.org/git/20191027042116.GA5801@sigill.intra.peff.net/
>
> (those have to do with normalize_path_copy(), hence the only
> semi-related documentation patch here).
>
>   [1/3]: normalize_path_copy(): document "dst" size expectations
>   [2/3]: walker_fetch(): avoid raw array length computation
>   [3/3]: traverse_trees(): use stack array for name entries
>
>  path.c      |  2 ++
>  tree-walk.c | 13 ++++++++-----
>  walker.c    |  4 +++-
>  3 files changed, 13 insertions(+), 6 deletions(-)
>
> -Peff