[3/3] traverse_trees(): use stack array for name entries
diff mbox series

Message ID 20200130095338.GC840531@coredump.intra.peff.net
State New
Headers show
Series
  • some minor memory allocation cleanups
Related show

Commit Message

Jeff King Jan. 30, 2020, 9:53 a.m. UTC
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(-)

Comments

Elijah Newren Jan. 30, 2020, 2:57 p.m. UTC | #1
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.
Jeff King Jan. 31, 2020, 9:29 a.m. UTC | #2
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.

-Peff
Elijah Newren Jan. 31, 2020, 6:52 p.m. UTC | #3
On Fri, Jan 31, 2020 at 1:29 AM Jeff King <peff@peff.net> wrote:
>
> 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.

It may be circular in how it came about, but I don't see how it's
circular from first principles: unpack_trees() uses traverse_trees()
to do its work (whereas tree-walk.c shouldn't call any functions from
unpack-trees).  For simplicity and lacking any justification for huge
numbers of trees, we want to impose a small limit on both for how many
trees they can simultaneously operate on -- though we want to leave a
little wiggle room by generously setting the limit much higher than we
expect any caller to ever want.  unpack-trees certainly can't have a
higher limit than tree-walk, and we don't know of callers outside
unpack_trees that would want to traverse more trees than
unpack_trees() does, so we just set them both to the same value, 8.

> 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.

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.

Patch
diff mbox series

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);