{"thread":{"id":"52716","subject":"[PATCH 0/3] some minor memory allocation cleanups","startedAt":"2020-01-30T09:51:58Z","lastAt":"2020-02-01T15:32:16Z","messageCount":13,"participants":["Jeff King","Elijah Newren","Taylor Blau"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"390775","messageId":"20200130095155.GA839988@coredump.intra.peff.net","threadId":"52716","inReplyTo":null,"subject":"[PATCH 0/3] some minor memory allocation cleanups","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-01-30T09:51:55Z","receivedAt":"2020-01-30T09:51:58Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"These are a result of me poking at the results of:\n\n git grep 'x[mc]alloc.*[+*] '\n\nlooking for any buffer allocation computations that could overflow (and\nhence under-allocate).\n\nThere are a few hits left after this in the commit-graph code. Those\nwill be dealt with in a separate series (coming soon!) since they have\nother problems, as discussed in:\n\n https://lore.kernel.org/git/20191027042116.GA5801@sigill.intra.peff.net/\n\n(those have to do with normalize_path_copy(), hence the only\nsemi-related documentation patch here).\n\n [1/3]: normalize_path_copy(): document \"dst\" size expectations\n [2/3]: walker_fetch(): avoid raw array length computation\n [3/3]: traverse_trees(): use stack array for name entries\n\n path.c | 2 ++\n tree-walk.c | 13 ++++++++-----\n walker.c | 4 +++-\n 3 files changed, 13 insertions(+), 6 deletions(-)\n\n-Peff\n"},{"id":"390776","messageId":"20200130095219.GA840531@coredump.intra.peff.net","threadId":"52716","inReplyTo":"20200130095155.GA839988@coredump.intra.peff.net","subject":"[PATCH 1/3] normalize_path_copy(): document \"dst\" size expectations","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-01-30T09:52:19Z","receivedAt":"2020-01-30T09:52:21Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We take a \"dst\" buffer to write into, but there's no matching \"len\"\nparameter. The hidden assumption is that normalizing always makes things\nsmaller, so we're OK as long as \"dst\" is at least as big as \"src\". Let's\ndocument that explicitly.\n\nSigned-off-by: Jeff King \n---\n path.c | 2 ++\n 1 file changed, 2 insertions(+)\n\ndiff --git a/path.c b/path.c\nindex a76eec8b96..88cf593007 100644\n--- a/path.c\n+++ b/path.c\n@@ -1077,6 +1077,8 @@ const char *remove_leading_path(const char *in, const char *prefix)\n \n /*\n * It is okay if dst == src, but they should not overlap otherwise.\n+ * The \"dst\" buffer must be at least as long as \"src\"; normalizing may shrink\n+ * the size of the path, but will never grow it.\n *\n * Performs the following normalizations on src, storing the result in dst:\n * - Ensures that components are separated by '/' (Windows only)\n-- \n2.25.0.515.gaba5347bc6\n\n"},{"id":"390777","messageId":"20200130095232.GB840531@coredump.intra.peff.net","threadId":"52716","inReplyTo":"20200130095155.GA839988@coredump.intra.peff.net","subject":"[PATCH 2/3] walker_fetch(): avoid raw array length computation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-01-30T09:52:32Z","receivedAt":"2020-01-30T09:52:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We compute the length of an array of object_id's with a raw\nmultiplication. In theory this could trigger an integer overflow which\nwould cause an under-allocation (and eventually an out of bounds write).\n\nI doubt this can be triggered in practice, since you'd need to feed it\nan enormous number of target objects, which would typically come from\nthe ref advertisement and be using proportional memory. And even on\n64-bit systems, where \"int\" is much smaller than \"size_t\", that should\nhold: even though \"targets\" is an int, the multiplication will be done\nas a size_t because of the use of sizeof().\n\nBut we can easily fix it by using ALLOC_ARRAY(), which uses st_mult()\nunder the hood.\n\nSigned-off-by: Jeff King \n---\n walker.c | 4 +++-\n 1 file changed, 3 insertions(+), 1 deletion(-)\n\ndiff --git a/walker.c b/walker.c\nindex 06cd2bd569..bb010f7a2b 100644\n--- a/walker.c\n+++ b/walker.c\n@@ -261,12 +261,14 @@ int walker_fetch(struct walker *walker, int targets, char **target,\n \tstruct strbuf refname = STRBUF_INIT;\n \tstruct strbuf err = STRBUF_INIT;\n \tstruct ref_transaction *transaction = NULL;\n-\tstruct object_id *oids = xmalloc(targets * sizeof(struct object_id));\n+\tstruct object_id *oids;\n \tchar *msg = NULL;\n \tint i, ret = -1;\n \n \tsave_commit_buffer = 0;\n \n+\tALLOC_ARRAY(oids, targets);\n+\n \tif (write_ref) {\n \t\ttransaction = ref_transaction_begin(&err);\n \t\tif (!transaction) {\n-- \n2.25.0.515.gaba5347bc6\n\n"},{"id":"390778","messageId":"20200130095338.GC840531@coredump.intra.peff.net","threadId":"52716","inReplyTo":"20200130095155.GA839988@coredump.intra.peff.net","subject":"[PATCH 3/3] traverse_trees(): use stack array for name entries","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-01-30T09:53:38Z","receivedAt":"2020-01-30T09:53:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We heap-allocate our arrays of name_entry structs, etc, with one entry\nper tree we're asked to traverse. The code does a raw multiplication in\nthe xmalloc() call, which I find when auditing for integer overflows\nduring allocation.\n\nWe could \"fix\" this by using ALLOC_ARRAY() instead. But as it turns out,\nthe maximum size of these arrays is limited at compile time:\n\n - merge_trees() always passes in 3 trees\n\n - unpack_trees() and its brethren never pass in more than\n MAX_UNPACK_TREES\n\nSo we can simplify even further by just using a stack array and bounding\nit with MAX_UNPACK_TREES. There should be no concern with overflowing\nthe stack, since MAX_UNPACK_TREES is only 8 and the structs themselves\nare small.\n\nNote that since we're replacing xcalloc(), we have to move one of the\nNULL initializations into a loop.\n\nSigned-off-by: Jeff King \n---\n\nThis does increase the coupling between tree-walk and unpack-trees a\nbit. I'd be OK just switching to ALLOC_ARRAY(), too. I doubt the\nperformance improvement is measurable, and the cleanup free() calls are\nalready there.\n\n tree-walk.c | 13 ++++++++-----\n 1 file changed, 8 insertions(+), 5 deletions(-)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex d5a8e096a6..3093cf7098 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -410,15 +410,20 @@ int traverse_trees(struct index_state *istate,\n \t\t struct traverse_info *info)\n {\n \tint error = 0;\n-\tstruct name_entry *entry = xmalloc(n*sizeof(*entry));\n+\tstruct name_entry entry[MAX_UNPACK_TREES];\n \tint i;\n-\tstruct tree_desc_x *tx = xcalloc(n, sizeof(*tx));\n+\tstruct tree_desc_x tx[ARRAY_SIZE(entry)];\n \tstruct strbuf base = STRBUF_INIT;\n \tint interesting = 1;\n \tchar *traverse_path;\n \n-\tfor (i = 0; i < n; i++)\n+\tif (n >= ARRAY_SIZE(entry))\n+\t\tBUG(\"traverse_trees() called with too many trees (%d)\", n);\n+\n+\tfor (i = 0; i < n; i++) {\n \t\ttx[i].d = t[i];\n+\t\ttx[i].skip = NULL;\n+\t}\n \n \tif (info->prev) {\n \t\tstrbuf_make_traverse_path(&base, info->prev,\n@@ -506,10 +511,8 @@ int traverse_trees(struct index_state *istate,\n \t\t\tif (mask & (1ul << i))\n \t\t\t\tupdate_extended_entry(tx + i, entry + i);\n \t}\n-\tfree(entry);\n \tfor (i = 0; i < n; i++)\n \t\tfree_extended_entry(tx + i);\n-\tfree(tx);\n \tfree(traverse_path);\n \tinfo->traverse_path = NULL;\n \tstrbuf_release(&base);\n-- \n2.25.0.515.gaba5347bc6\n"},{"id":"390799","messageId":"CABPp-BE7E--8Yz3PAcjPQX2RCsbq0Q0gURi3RJuE64KM0eo6mA@mail.gmail.com","threadId":"52716","inReplyTo":"20200130095338.GC840531@coredump.intra.peff.net","subject":"Re: [PATCH 3/3] traverse_trees(): use stack array for name entries","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-01-30T14:57:26Z","receivedAt":"2020-01-30T14:57:40Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Jan 30, 2020 at 1:54 AM Jeff King wrote:\n>\n> We heap-allocate our arrays of name_entry structs, etc, with one entry\n> per tree we're asked to traverse. The code does a raw multiplication in\n> the xmalloc() call, which I find when auditing for integer overflows\n> during allocation.\n>\n> We could \"fix\" this by using ALLOC_ARRAY() instead. But as it turns out,\n> the maximum size of these arrays is limited at compile time:\n>\n> - merge_trees() always passes in 3 trees\n>\n> - unpack_trees() and its brethren never pass in more than\n> MAX_UNPACK_TREES\n>\n> So we can simplify even further by just using a stack array and bounding\n> it with MAX_UNPACK_TREES. There should be no concern with overflowing\n> the stack, since MAX_UNPACK_TREES is only 8 and the structs themselves\n> are small.\n>\n> Note that since we're replacing xcalloc(), we have to move one of the\n> NULL initializations into a loop.\n>\n> Signed-off-by: Jeff King \n> ---\n>\n> This does increase the coupling between tree-walk and unpack-trees a\n> bit. I'd be OK just switching to ALLOC_ARRAY(), too. I doubt the\n> performance improvement is measurable, and the cleanup free() calls are\n> already there.\n\nCould we undo this cyclic dependency between tree-walk and\nunpack-trees by defining MAX_TRAVERSE_TREES in tree-walk.h, making\nMAX_UNPACK_TREES in unpack-trees.h be defined to MAX_TRAVERSE_TREES,\nand remove the include of unpack-trees.h in tree-walk.c?\n\n> tree-walk.c | 13 ++++++++-----\n> 1 file changed, 8 insertions(+), 5 deletions(-)\n>\n> diff --git a/tree-walk.c b/tree-walk.c\n> index d5a8e096a6..3093cf7098 100644\n> --- a/tree-walk.c\n> +++ b/tree-walk.c\n> @@ -410,15 +410,20 @@ int traverse_trees(struct index_state *istate,\n> struct traverse_info *info)\n> {\n> int error = 0;\n> - struct name_entry *entry = xmalloc(n*sizeof(*entry));\n> + struct name_entry entry[MAX_UNPACK_TREES];\n> int i;\n> - struct tree_desc_x *tx = xcalloc(n, sizeof(*tx));\n> + struct tree_desc_x tx[ARRAY_SIZE(entry)];\n> struct strbuf base = STRBUF_INIT;\n> int interesting = 1;\n> char *traverse_path;\n>\n> - for (i = 0; i < n; i++)\n> + if (n >= ARRAY_SIZE(entry))\n> + BUG(\"traverse_trees() called with too many trees (%d)\", n);\n> +\n> + for (i = 0; i < n; i++) {\n> tx[i].d = t[i];\n> + tx[i].skip = NULL;\n> + }\n>\n> if (info->prev) {\n> strbuf_make_traverse_path(&base, info->prev,\n> @@ -506,10 +511,8 @@ int traverse_trees(struct index_state *istate,\n> if (mask & (1ul << i))\n> update_extended_entry(tx + i, entry + i);\n> }\n> - free(entry);\n> for (i = 0; i < n; i++)\n> free_extended_entry(tx + i);\n> - free(tx);\n> free(traverse_path);\n> info->traverse_path = NULL;\n> strbuf_release(&base);\n> --\n> 2.25.0.515.gaba5347bc6\n\nLooks good to me otherwise.\n"},{"id":"390800","messageId":"CABPp-BHmj6g_M=XjuQY5cd+G2EneerFPktDLnPbbUALksA-Gfw@mail.gmail.com","threadId":"52716","inReplyTo":"20200130095155.GA839988@coredump.intra.peff.net","subject":"Re: [PATCH 0/3] some minor memory allocation cleanups","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-01-30T14:59:59Z","receivedAt":"2020-01-30T15:00:13Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Jan 30, 2020 at 1:53 AM Jeff King wrote:\n>\n> These are a result of me poking at the results of:\n>\n> git grep 'x[mc]alloc.*[+*] '\n>\n> looking for any buffer allocation computations that could overflow (and\n> hence under-allocate).\n>\n> There are a few hits left after this in the commit-graph code. Those\n> will be dealt with in a separate series (coming soon!) since they have\n> other problems, as discussed in:\n>\n> https://lore.kernel.org/git/20191027042116.GA5801@sigill.intra.peff.net/\n>\n> (those have to do with normalize_path_copy(), hence the only\n> semi-related documentation patch here).\n>\n> [1/3]: normalize_path_copy(): document \"dst\" size expectations\n> [2/3]: walker_fetch(): avoid raw array length computation\n> [3/3]: traverse_trees(): use stack array for name entries\n>\n> path.c | 2 ++\n> tree-walk.c | 13 ++++++++-----\n> walker.c | 4 +++-\n> 3 files changed, 13 insertions(+), 6 deletions(-)\n>\n> -Peff\n\nOther than introducing (or extending?) a cyclic dependency between\ntree-walk and unpack-trees that I'd prefer to remove, this series\nlooks good to me.\n"},{"id":"390833","messageId":"20200130201247.GA26000@syl.local","threadId":"52716","inReplyTo":"20200130095219.GA840531@coredump.intra.peff.net","subject":"Re: [PATCH 1/3] normalize_path_copy(): document \"dst\" size expectations","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-01-30T20:12:47Z","receivedAt":"2020-01-30T20:12:51Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, Jan 30, 2020 at 04:52:19AM -0500, Jeff King wrote:\n> We take a \"dst\" buffer to write into, but there's no matching \"len\"\n> parameter. The hidden assumption is that normalizing always makes things\n> smaller, so we're OK as long as \"dst\" is at least as big as \"src\". Let's\n> document that explicitly.\n>\n> Signed-off-by: Jeff King \n> ---\n> path.c | 2 ++\n> 1 file changed, 2 insertions(+)\n>\n> diff --git a/path.c b/path.c\n> index a76eec8b96..88cf593007 100644\n> --- a/path.c\n> +++ b/path.c\n> @@ -1077,6 +1077,8 @@ const char *remove_leading_path(const char *in, const char *prefix)\n>\n> /*\n> * It is okay if dst == src, but they should not overlap otherwise.\n> + * The \"dst\" buffer must be at least as long as \"src\"; normalizing may shrink\n> + * the size of the path, but will never grow it.\n\nThanks for documenting this. It's quite helpful, and hopefully should\nprevent bugs like the one you alluded to in your cover letter from\ngetting in in the future.\n\n> *\n> * Performs the following normalizations on src, storing the result in dst:\n> * - Ensures that components are separated by '/' (Windows only)\n> --\n> 2.25.0.515.gaba5347bc6\n\nThis looks obviously good to me.\n\nThanks,\nTaylor\n"},{"id":"390872","messageId":"20200130230338.GA37366@syl.local","threadId":"52716","inReplyTo":"20200130095155.GA839988@coredump.intra.peff.net","subject":"Re: [PATCH 0/3] some minor memory allocation cleanups","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-01-30T23:03:38Z","receivedAt":"2020-01-30T23:03:41Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Hi Peff,\n\nOn Thu, Jan 30, 2020 at 04:51:55AM -0500, Jeff King wrote:\n> These are a result of me poking at the results of:\n>\n> git grep 'x[mc]alloc.*[+*] '\n>\n> looking for any buffer allocation computations that could overflow (and\n> hence under-allocate).\n>\n> There are a few hits left after this in the commit-graph code. Those\n> will be dealt with in a separate series (coming soon!) since they have\n> other problems, as discussed in:\n\nI just sent the series you're referring to in [1].\n\n> https://lore.kernel.org/git/20191027042116.GA5801@sigill.intra.peff.net/\n>\n> (those have to do with normalize_path_copy(), hence the only\n> semi-related documentation patch here).\n>\n> [1/3]: normalize_path_copy(): document \"dst\" size expectations\n> [2/3]: walker_fetch(): avoid raw array length computation\n> [3/3]: traverse_trees(): use stack array for name entries\n>\n> path.c | 2 ++\n> tree-walk.c | 13 ++++++++-----\n> walker.c | 4 +++-\n> 3 files changed, 13 insertions(+), 6 deletions(-)\n>\n> -Peff\n\n[1]: https://lore.kernel.org/git/cover.1580424766.git.me@ttaylorr.com/\n\nThanks,\nTaylor\n"},{"id":"390885","messageId":"20200131084535.GA2857810@coredump.intra.peff.net","threadId":"52716","inReplyTo":"20200130201247.GA26000@syl.local","subject":"Re: [PATCH 1/3] normalize_path_copy(): document \"dst\" size expectations","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-01-31T08:45:35Z","receivedAt":"2020-01-31T08:45:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 30, 2020 at 12:12:47PM -0800, Taylor Blau wrote:\n\n> > @@ -1077,6 +1077,8 @@ const char *remove_leading_path(const char *in, const char *prefix)\n> >\n> > /*\n> > * It is okay if dst == src, but they should not overlap otherwise.\n> > + * The \"dst\" buffer must be at least as long as \"src\"; normalizing may shrink\n> > + * the size of the path, but will never grow it.\n> \n> Thanks for documenting this. It's quite helpful, and hopefully should\n> prevent bugs like the one you alluded to in your cover letter from\n> getting in in the future.\n\nTo be picky, I didn't find an actual bug around buffer lengths; the\nproblem was a failure to check the error code. This was just something I\nhappened to find confusing auditing the code.\n\n-Peff\n"},{"id":"390890","messageId":"20200131092936.GA2916051@coredump.intra.peff.net","threadId":"52716","inReplyTo":"CABPp-BE7E--8Yz3PAcjPQX2RCsbq0Q0gURi3RJuE64KM0eo6mA@mail.gmail.com","subject":"Re: [PATCH 3/3] traverse_trees(): use stack array for name entries","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-01-31T09:29:36Z","receivedAt":"2020-01-31T09:29:39Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 30, 2020 at 06:57:26AM -0800, Elijah Newren wrote:\n\n> > This does increase the coupling between tree-walk and unpack-trees a\n> > bit. I'd be OK just switching to ALLOC_ARRAY(), too. I doubt the\n> > performance improvement is measurable, and the cleanup free() calls are\n> > already there.\n> \n> Could we undo this cyclic dependency between tree-walk and\n> unpack-trees by defining MAX_TRAVERSE_TREES in tree-walk.h, making\n> MAX_UNPACK_TREES in unpack-trees.h be defined to MAX_TRAVERSE_TREES,\n> and remove the include of unpack-trees.h in tree-walk.c?\n\nI don't mind doing that, but I had a hard time trying to write a commit\nmessage. I.e., I can explain the current use of MAX_UNPACK_TREES here,\nor defining MAX_TRAVERSE_TREES as MAX_UNPACK_TREES by saying \"this is an\narbitrary limit, but it's the highest value any caller would use with\nus\".\n\nBut to define MAX_UNPACK_TREES in terms of MAX_TRAVERSE_TREES, I feel\nwe've created a circular reasoning in the justification.\n\nI'm not even sure whether the current value of 8 is meaningful. It comes\nfrom this commit:\n\n commit ca885a4fe6444bed840295378848904106c87c85\n Author: Junio C Hamano \n Date: Thu Mar 13 22:07:18 2008 -0700\n \n read-tree() and unpack_trees(): use consistent limit\n \n read-tree -m can read up to MAX_TREES, which was arbitrarily set to 8 since\n August 2007 (4 is needed to deal with 2 merge-base case).\n \n However, the updated unpack_trees() code had an advertised limit of 4\n (which it enforced). In reality the code was prepared to take only 3\n trees and giving 4 caused it to stomp on its stack. Rename the MAX_TREES\n constant to MAX_UNPACK_TREES, move it to the unpack-trees.h common header\n file, and use it from both places to avoid future confusion.\n\nwhich kind of makes me wonder if we should just go back to calling it\nMAX_TREES. I guess that's too vague, though.\n\nSo I dunno. It would be easy to do as you asked, but I'm not convinced\nit actually untangles anything meaningful.\n\n-Peff\n"},{"id":"390932","messageId":"CABPp-BFXwin5mR7z7Ocx9bq5LadFF4CxZR03HzZxh5f=1+F6NQ@mail.gmail.com","threadId":"52716","inReplyTo":"20200131092936.GA2916051@coredump.intra.peff.net","subject":"Re: [PATCH 3/3] traverse_trees(): use stack array for name entries","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-01-31T18:52:30Z","receivedAt":"2020-01-31T18:52:46Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Jan 31, 2020 at 1:29 AM Jeff King wrote:\n>\n> On Thu, Jan 30, 2020 at 06:57:26AM -0800, Elijah Newren wrote:\n>\n> > > This does increase the coupling between tree-walk and unpack-trees a\n> > > bit. I'd be OK just switching to ALLOC_ARRAY(), too. I doubt the\n> > > performance improvement is measurable, and the cleanup free() calls are\n> > > already there.\n> >\n> > Could we undo this cyclic dependency between tree-walk and\n> > unpack-trees by defining MAX_TRAVERSE_TREES in tree-walk.h, making\n> > MAX_UNPACK_TREES in unpack-trees.h be defined to MAX_TRAVERSE_TREES,\n> > and remove the include of unpack-trees.h in tree-walk.c?\n>\n> I don't mind doing that, but I had a hard time trying to write a commit\n> message. I.e., I can explain the current use of MAX_UNPACK_TREES here,\n> or defining MAX_TRAVERSE_TREES as MAX_UNPACK_TREES by saying \"this is an\n> arbitrary limit, but it's the highest value any caller would use with\n> us\".\n>\n> But to define MAX_UNPACK_TREES in terms of MAX_TRAVERSE_TREES, I feel\n> we've created a circular reasoning in the justification.\n\nIt may be circular in how it came about, but I don't see how it's\ncircular from first principles: unpack_trees() uses traverse_trees()\nto do its work (whereas tree-walk.c shouldn't call any functions from\nunpack-trees). For simplicity and lacking any justification for huge\nnumbers of trees, we want to impose a small limit on both for how many\ntrees they can simultaneously operate on -- though we want to leave a\nlittle wiggle room by generously setting the limit much higher than we\nexpect any caller to ever want. unpack-trees certainly can't have a\nhigher limit than tree-walk, and we don't know of callers outside\nunpack_trees that would want to traverse more trees than\nunpack_trees() does, so we just set them both to the same value, 8.\n\n> I'm not even sure whether the current value of 8 is meaningful. It comes\n> from this commit:\n>\n> commit ca885a4fe6444bed840295378848904106c87c85\n> Author: Junio C Hamano \n> Date: Thu Mar 13 22:07:18 2008 -0700\n>\n> read-tree() and unpack_trees(): use consistent limit\n>\n> read-tree -m can read up to MAX_TREES, which was arbitrarily set to 8 since\n> August 2007 (4 is needed to deal with 2 merge-base case).\n>\n> However, the updated unpack_trees() code had an advertised limit of 4\n> (which it enforced). In reality the code was prepared to take only 3\n> trees and giving 4 caused it to stomp on its stack. Rename the MAX_TREES\n> constant to MAX_UNPACK_TREES, move it to the unpack-trees.h common header\n> file, and use it from both places to avoid future confusion.\n>\n> which kind of makes me wonder if we should just go back to calling it\n> MAX_TREES. I guess that's too vague, though.\n>\n> So I dunno. It would be easy to do as you asked, but I'm not convinced\n> it actually untangles anything meaningful.\n\nAs far as I can tell, before your change, we can remove the\n #include \"unpack-trees.h\"\nfrom tree-walk.c; nothing uses it. I do like snipping includes and\ndependencies where they aren't necessary, and this one seems like one\nthat could be removed.\n\nBut, it's not a big deal; if you want to leave that for future work\nfor someone else (perhaps even asking me to turn my paragraph above\ninto a commit message that rips it out and defines one #define in\nterms of the other), that's fine.\n"},{"id":"390989","messageId":"20200201113922.GE1864948@coredump.intra.peff.net","threadId":"52716","inReplyTo":"CABPp-BFXwin5mR7z7Ocx9bq5LadFF4CxZR03HzZxh5f=1+F6NQ@mail.gmail.com","subject":"[PATCH] tree-walk.c: break circular dependency with unpack-trees","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-01T11:39:22Z","receivedAt":"2020-02-01T11:39:24Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jan 31, 2020 at 10:52:30AM -0800, Elijah Newren wrote:\n\n> As far as I can tell, before your change, we can remove the\n> #include \"unpack-trees.h\"\n> from tree-walk.c; nothing uses it. I do like snipping includes and\n> dependencies where they aren't necessary, and this one seems like one\n> that could be removed.\n\nYeah, I think that is the case.\n\n> But, it's not a big deal; if you want to leave that for future work\n> for someone else (perhaps even asking me to turn my paragraph above\n> into a commit message that rips it out and defines one #define in\n> terms of the other), that's fine.\n\nLet's do it now while we're thinking about it. How about the patch below\non top of my series?\n\n-- >8 --\nSubject: [PATCH] tree-walk.c: break circular dependency with unpack-trees\n\nThe unpack-trees API depends on the tree-walk API. But we've recently\nintroduced a dependency in tree-walk.c on MAX_UNPACK_TREES, which\ndoesn't otherwise care about unpack-trees at all.\n\nLet's break that dependency by reversing the constants: we'll introduce\na new MAX_TRAVERSE_TREES which belongs to the tree-walk API. And then we\ncan define MAX_UNPACK_TREES in terms of that (since unpack-trees cannot\npossibly work with more trees than it can traverse at once via\ntree-walk).\n\nThe value for both will remain at 8. This is somewhat arbitrary and\nprobably more than is necessary, per ca885a4fe6 (read-tree() and\nunpack_trees(): use consistent limit, 2008-03-13), but there's not\nreally any pressing need to reduce it.\n\nSuggested-by: Elijah Newren \nSigned-off-by: Jeff King \n---\n tree-walk.c | 3 +--\n tree-walk.h | 2 ++\n unpack-trees.h | 2 +-\n 3 files changed, 4 insertions(+), 3 deletions(-)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 3093cf7098..bb0ad34c54 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -1,6 +1,5 @@\n #include \"cache.h\"\n #include \"tree-walk.h\"\n-#include \"unpack-trees.h\"\n #include \"dir.h\"\n #include \"object-store.h\"\n #include \"tree.h\"\n@@ -410,7 +409,7 @@ int traverse_trees(struct index_state *istate,\n \t\t struct traverse_info *info)\n {\n \tint error = 0;\n-\tstruct name_entry entry[MAX_UNPACK_TREES];\n+\tstruct name_entry entry[MAX_TRAVERSE_TREES];\n \tint i;\n \tstruct tree_desc_x tx[ARRAY_SIZE(entry)];\n \tstruct strbuf base = STRBUF_INIT;\ndiff --git a/tree-walk.h b/tree-walk.h\nindex 826396c8ed..a5058469e9 100644\n--- a/tree-walk.h\n+++ b/tree-walk.h\n@@ -3,6 +3,8 @@\n \n #include \"cache.h\"\n \n+#define MAX_TRAVERSE_TREES 8\n+\n /**\n * The tree walking API is used to traverse and inspect trees.\n */\ndiff --git a/unpack-trees.h b/unpack-trees.h\nindex ca94a421a5..ae1557fb80 100644\n--- a/unpack-trees.h\n+++ b/unpack-trees.h\n@@ -6,7 +6,7 @@\n #include \"string-list.h\"\n #include \"tree-walk.h\"\n \n-#define MAX_UNPACK_TREES 8\n+#define MAX_UNPACK_TREES MAX_TRAVERSE_TREES\n \n struct cache_entry;\n struct unpack_trees_options;\n-- \n2.25.0.538.g1d5d7023b0\n\n"},{"id":"390993","messageId":"CABPp-BFPt7dcsc0a4jq1fisEszm=cmtk549rWgzyh2MpN1xMBw@mail.gmail.com","threadId":"52716","inReplyTo":"20200201113922.GE1864948@coredump.intra.peff.net","subject":"Re: [PATCH] tree-walk.c: break circular dependency with unpack-trees","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-02-01T15:32:02Z","receivedAt":"2020-02-01T15:32:16Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Sat, Feb 1, 2020 at 3:39 AM Jeff King wrote:\n>\n> On Fri, Jan 31, 2020 at 10:52:30AM -0800, Elijah Newren wrote:\n>\n> > As far as I can tell, before your change, we can remove the\n> > #include \"unpack-trees.h\"\n> > from tree-walk.c; nothing uses it. I do like snipping includes and\n> > dependencies where they aren't necessary, and this one seems like one\n> > that could be removed.\n>\n> Yeah, I think that is the case.\n>\n> > But, it's not a big deal; if you want to leave that for future work\n> > for someone else (perhaps even asking me to turn my paragraph above\n> > into a commit message that rips it out and defines one #define in\n> > terms of the other), that's fine.\n>\n> Let's do it now while we're thinking about it. How about the patch below\n> on top of my series?\n>\n> -- >8 --\n> Subject: [PATCH] tree-walk.c: break circular dependency with unpack-trees\n>\n> The unpack-trees API depends on the tree-walk API. But we've recently\n> introduced a dependency in tree-walk.c on MAX_UNPACK_TREES, which\n> doesn't otherwise care about unpack-trees at all.\n>\n> Let's break that dependency by reversing the constants: we'll introduce\n> a new MAX_TRAVERSE_TREES which belongs to the tree-walk API. And then we\n> can define MAX_UNPACK_TREES in terms of that (since unpack-trees cannot\n> possibly work with more trees than it can traverse at once via\n> tree-walk).\n>\n> The value for both will remain at 8. This is somewhat arbitrary and\n> probably more than is necessary, per ca885a4fe6 (read-tree() and\n> unpack_trees(): use consistent limit, 2008-03-13), but there's not\n> really any pressing need to reduce it.\n>\n> Suggested-by: Elijah Newren \n> Signed-off-by: Jeff King \n> ---\n> tree-walk.c | 3 +--\n> tree-walk.h | 2 ++\n> unpack-trees.h | 2 +-\n> 3 files changed, 4 insertions(+), 3 deletions(-)\n>\n> diff --git a/tree-walk.c b/tree-walk.c\n> index 3093cf7098..bb0ad34c54 100644\n> --- a/tree-walk.c\n> +++ b/tree-walk.c\n> @@ -1,6 +1,5 @@\n> #include \"cache.h\"\n> #include \"tree-walk.h\"\n> -#include \"unpack-trees.h\"\n> #include \"dir.h\"\n> #include \"object-store.h\"\n> #include \"tree.h\"\n> @@ -410,7 +409,7 @@ int traverse_trees(struct index_state *istate,\n> struct traverse_info *info)\n> {\n> int error = 0;\n> - struct name_entry entry[MAX_UNPACK_TREES];\n> + struct name_entry entry[MAX_TRAVERSE_TREES];\n> int i;\n> struct tree_desc_x tx[ARRAY_SIZE(entry)];\n> struct strbuf base = STRBUF_INIT;\n> diff --git a/tree-walk.h b/tree-walk.h\n> index 826396c8ed..a5058469e9 100644\n> --- a/tree-walk.h\n> +++ b/tree-walk.h\n> @@ -3,6 +3,8 @@\n>\n> #include \"cache.h\"\n>\n> +#define MAX_TRAVERSE_TREES 8\n> +\n> /**\n> * The tree walking API is used to traverse and inspect trees.\n> */\n> diff --git a/unpack-trees.h b/unpack-trees.h\n> index ca94a421a5..ae1557fb80 100644\n> --- a/unpack-trees.h\n> +++ b/unpack-trees.h\n> @@ -6,7 +6,7 @@\n> #include \"string-list.h\"\n> #include \"tree-walk.h\"\n>\n> -#define MAX_UNPACK_TREES 8\n> +#define MAX_UNPACK_TREES MAX_TRAVERSE_TREES\n>\n> struct cache_entry;\n> struct unpack_trees_options;\n> --\n> 2.25.0.538.g1d5d7023b0\n\nLooks great, thanks!\n"}]}