Message ID | 20200130095338.GC840531@coredump.intra.peff.net (mailing list archive) |
---|---|
State | New, archived |
Headers | show |
Series | some minor memory allocation cleanups | expand |
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.
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
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.
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);
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(-)