Re: [PATCH 3/3] traverse_trees(): use stack array for name entries

[Elijah Newren <newren@gmail.com>]

On Thu, Jan 30, 2020 at 1:54 AM Jeff King <peff@peff.net> wrote:
>
> 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.

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?

>  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

Looks good to me otherwise.