{"thread":{"id":"64466","subject":"[PATCH] attr: avoid recursion when expanding attribute macros","startedAt":"2025-11-11T22:36:49Z","lastAt":"2025-11-12T17:40:34Z","messageCount":8,"participants":["Jeff King","Ben Knoble","Patrick Steinhardt","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"530551","messageId":"20251111223647.GA4055973@coredump.intra.peff.net","threadId":"64466","inReplyTo":null,"subject":"[PATCH] attr: avoid recursion when expanding attribute macros","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-11-11T22:36:47Z","receivedAt":"2025-11-11T22:36:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Given a set of attribute macros like:\n\n   [attr]a1 a2\n   [attr]a2 a3\n   ...\n   [attr]a300000 -text\n   file a1\n\nexpanding the attributes for \"file\" requires expanding \"a1\" to \"a2\",\n\"a2\" to \"a3\", and so on until hitting a non-macro expansion (\"-text\", in\nthis case). We implement this via recursion: fill_one() calls\nmacroexpand_one(), which then recurses back to fill_one(). As a result,\nvery deep macro chains like the one above can run out of stack space and\ncause us to segfault.\n\nThe required stack space is fairly small; I needed on the order of\n200,000 entries to get a segfault on Linux. So it's unlikely anybody\nwould hit this accidentally, leaving only malicious inputs. There you\ncan easily construct a repo which will segfault on clone (we look at\nattributes during the checkout step, but you'd see the same trying to do\nother operations, like diff in a bare repo). It's mostly harmless, since\nanybody constructing such a repo is only preventing victims from cloning\ntheir evil garbage, but it could be a nuisance for hosting sites.\n\nOne option to prevent this is to limit the depth of recursion we'll\nallow. This is conceptually easy to implement, but it raises other\nquestions: what should the limit be, and do we need a configuration knob\nfor it?\n\nThe recursion here is simple enough that we can avoid those questions by\njust converting it to iteration instead. Rather than iterate over the\nstates of a match_attr in fill_one(), we'll put them all in a queue, and\nthe expansion of each can add to the queue rather than recursing. Note\nthat this is a LIFO queue in order to keep the same depth-first order we\ndid with the recursive implementation. I've avoided using the word\n\"stack\" in the code because the term is already heavily used to refer to\nthe stack of .gitattribute files that matches the tree structure of the\nrepository.\n\nThe test uses a limited stack size so we can trigger the problem with a\nmuch smaller input than the one shown above. The value here (3000) is\nenough to trigger the issue on my x86_64 Linux machine.\n\nReported-by: Ben Stav <benstav@miggo.io>\nSigned-off-by: Jeff King <peff@peff.net>\n---\n attr.c                | 50 +++++++++++++++++++++++++++++--------------\n t/t0003-attributes.sh | 20 +++++++++++++++++\n 2 files changed, 54 insertions(+), 16 deletions(-)\n\ndiff --git a/attr.c b/attr.c\nindex d1daeb0b4d..4999b7e09d 100644\n--- a/attr.c\n+++ b/attr.c\n@@ -1064,24 +1064,52 @@ static int path_matches(const char *pathname, int pathlen,\n \t\t\t      pattern, prefix, pat->patternlen);\n }\n \n-static int macroexpand_one(struct all_attrs_item *all_attrs, int nr, int rem);\n+struct attr_state_queue {\n+\tconst struct attr_state **items;\n+\tsize_t alloc, nr;\n+};\n+\n+static void attr_state_queue_push(struct attr_state_queue *t,\n+\t\t\t\t const struct match_attr *a)\n+{\n+\tfor (size_t i = 0; i < a->num_attr; i++) {\n+\t\tALLOC_GROW(t->items, t->nr + 1, t->alloc);\n+\t\tt->items[t->nr++] = &a->state[i];\n+\t}\n+}\n+\n+static const struct attr_state *attr_state_queue_pop(struct attr_state_queue *t)\n+{\n+\treturn t->nr ? t->items[--t->nr] : NULL;\n+}\n+\n+static void attr_state_queue_release(struct attr_state_queue *t)\n+{\n+\tfree(t->items);\n+}\n \n static int fill_one(struct all_attrs_item *all_attrs,\n \t\t    const struct match_attr *a, int rem)\n {\n-\tsize_t i;\n+\tstruct attr_state_queue todo = { 0 };\n+\tconst struct attr_state *state;\n \n-\tfor (i = a->num_attr; rem > 0 && i > 0; i--) {\n-\t\tconst struct git_attr *attr = a->state[i - 1].attr;\n+\tattr_state_queue_push(&todo, a);\n+\twhile (rem > 0 && (state = attr_state_queue_pop(&todo))) {\n+\t\tconst struct git_attr *attr = state->attr;\n \t\tconst char **n = &(all_attrs[attr->attr_nr].value);\n-\t\tconst char *v = a->state[i - 1].setto;\n+\t\tconst char *v = state->setto;\n \n \t\tif (*n == ATTR__UNKNOWN) {\n+\t\t\tconst struct all_attrs_item *item =\n+\t\t\t\t&all_attrs[attr->attr_nr];\n \t\t\t*n = v;\n \t\t\trem--;\n-\t\t\trem = macroexpand_one(all_attrs, attr->attr_nr, rem);\n+\t\t\tif (item->macro && item->value == ATTR__TRUE)\n+\t\t\t\tattr_state_queue_push(&todo, item->macro);\n \t\t}\n \t}\n+\tattr_state_queue_release(&todo);\n \treturn rem;\n }\n \n@@ -1106,16 +1134,6 @@ static int fill(const char *path, int pathlen, int basename_offset,\n \treturn rem;\n }\n \n-static int macroexpand_one(struct all_attrs_item *all_attrs, int nr, int rem)\n-{\n-\tconst struct all_attrs_item *item = &all_attrs[nr];\n-\n-\tif (item->macro && item->value == ATTR__TRUE)\n-\t\treturn fill_one(all_attrs, item->macro, rem);\n-\telse\n-\t\treturn rem;\n-}\n-\n /*\n  * Marks the attributes which are macros based on the attribute stack.\n  * This prevents having to search through the attribute stack each time\ndiff --git a/t/t0003-attributes.sh b/t/t0003-attributes.sh\nindex 3c98b622f2..582e207aa1 100755\n--- a/t/t0003-attributes.sh\n+++ b/t/t0003-attributes.sh\n@@ -664,4 +664,24 @@ test_expect_success 'user defined builtin_objectmode values are ignored' '\n \ttest_cmp expect err\n '\n \n+test_expect_success ULIMIT_STACK_SIZE 'deep macro recursion' '\n+\tn=3000 &&\n+\t{\n+\t\ti=0 &&\n+\t\twhile test $i -lt $n; do\n+\t\t\techo \"[attr]a$i a$((i+1))\" &&\n+\t\t\ti=$((i+1)) ||\n+\t\t\treturn 1\n+\t\tdone &&\n+\t\techo \"[attr]a$n -text\" &&\n+\t\techo \"file a0\"\n+\t} >.gitattributes &&\n+\t{\n+\t\techo \"file: text: unset\" &&\n+\t\ttest_seq -f \"file: a%d: set\" 0 $n\n+\t} >expect &&\n+\trun_with_limited_stack git check-attr -a file >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \n2.52.0.rc1.258.g0c10df6ae5\n"},{"id":"530556","messageId":"F6B66286-64B0-47AB-A31D-50A253F001D5@gmail.com","threadId":"64466","inReplyTo":"20251111223647.GA4055973@coredump.intra.peff.net","subject":"Re: [PATCH] attr: avoid recursion when expanding attribute macros","fromName":"Ben Knoble","fromEmail":"ben.knoble@gmail.com","sentAt":"2025-11-12T01:30:58Z","receivedAt":"2025-11-12T01:31:11Z","isPatch":true,"sender":{"key":"ben.knoble@gmail.com","avatar":"https://avatars.githubusercontent.com/u/22802209?v=4"},"body":"\n> Le 11 nov. 2025 à 17:37, Jeff King <peff@peff.net> a écrit :\n> \n> Given a set of attribute macros like:\n> \n>   [attr]a1 a2\n>   [attr]a2 a3\n>   ...\n>   [attr]a300000 -text\n>   file a1\n> \n> expanding the attributes for \"file\" requires expanding \"a1\" to \"a2\",\n> \"a2\" to \"a3\", and so on until hitting a non-macro expansion (\"-text\", in\n> this case). We implement this via recursion: fill_one() calls\n> macroexpand_one(), which then recurses back to fill_one(). As a result,\n> very deep macro chains like the one above can run out of stack space and\n> cause us to segfault.\n> \n> The required stack space is fairly small; I needed on the order of\n> 200,000 entries to get a segfault on Linux. So it's unlikely anybody\n> would hit this accidentally, leaving only malicious inputs. There you\n> can easily construct a repo which will segfault on clone (we look at\n> attributes during the checkout step, but you'd see the same trying to do\n> other operations, like diff in a bare repo). It's mostly harmless, since\n> anybody constructing such a repo is only preventing victims from cloning\n> their evil garbage, but it could be a nuisance for hosting sites.\n> \n> One option to prevent this is to limit the depth of recursion we'll\n> allow. This is conceptually easy to implement, but it raises other\n> questions: what should the limit be, and do we need a configuration knob\n> for it?\n> \n> The recursion here is simple enough that we can avoid those questions by\n> just converting it to iteration instead. Rather than iterate over the\n> states of a match_attr in fill_one(), we'll put them all in a queue, and\n> the expansion of each can add to the queue rather than recursing. Note\n> that this is a LIFO queue in order to keep the same depth-first order we\n> did with the recursive implementation. I've avoided using the word\n> \"stack\" in the code because the term is already heavily used to refer to\n> the stack of .gitattribute files that matches the tree structure of the\n> repository.\n\n\nWorth catching, and I agree with your choice of in-memory iteration over tunable depth.\n\nMy knowledge on memory models is a bit weak and I didn’t check directly, but are we implicitly assuming that we are less likely to run out of heap memory in such an evil case? In effect I suppose we’re turning a stack overflow segfault into an OOM error?\n\nThat seems like a fine assumption to me (I’m used to languages where the call stack lives more or less efficiently on the heap), just wanted to check my understanding. \n\nThe memory use has to go somewhere ;) presuming there’s no good way to only keep the relevant entries in memory, since I can of course find a large example that also uses each intermediate macro, so the code would need to get a lot smarter to collapse equivalence classes, prune unused paths, etc., which seems like a poor investment for what AFAICT is a little-used feature*.\n\n*I love it, and use it for custom diff drivers and the baked in hunk headers. But the diff definitions aren’t easily shareable, and I have to be aware of when to turn them off, so I end up not sharing the corresponding attributes either."},{"id":"530559","messageId":"aRQvyvMq61syGT7_@pks.im","threadId":"64466","inReplyTo":"20251111223647.GA4055973@coredump.intra.peff.net","subject":"Re: [PATCH] attr: avoid recursion when expanding attribute macros","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-11-12T06:57:14Z","receivedAt":"2025-11-12T06:57:21Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Tue, Nov 11, 2025 at 05:36:47PM -0500, Jeff King wrote:\n> Given a set of attribute macros like:\n> \n>    [attr]a1 a2\n>    [attr]a2 a3\n>    ...\n>    [attr]a300000 -text\n>    file a1\n> \n> expanding the attributes for \"file\" requires expanding \"a1\" to \"a2\",\n> \"a2\" to \"a3\", and so on until hitting a non-macro expansion (\"-text\", in\n> this case). We implement this via recursion: fill_one() calls\n> macroexpand_one(), which then recurses back to fill_one(). As a result,\n> very deep macro chains like the one above can run out of stack space and\n> cause us to segfault.\n> \n> The required stack space is fairly small; I needed on the order of\n> 200,000 entries to get a segfault on Linux. So it's unlikely anybody\n> would hit this accidentally, leaving only malicious inputs. There you\n> can easily construct a repo which will segfault on clone (we look at\n> attributes during the checkout step, but you'd see the same trying to do\n> other operations, like diff in a bare repo). It's mostly harmless, since\n> anybody constructing such a repo is only preventing victims from cloning\n> their evil garbage, but it could be a nuisance for hosting sites.\n> \n> One option to prevent this is to limit the depth of recursion we'll\n> allow. This is conceptually easy to implement, but it raises other\n> questions: what should the limit be, and do we need a configuration knob\n> for it?\n\nThat's fair, and as you demonstrate it's easy enough to turn recursion\ninto iteration. But it doesn't really solve the main problem: given\nmalicious input we'd now still crash eventually, even though we\nourselves control how exactly we crash. The main difference is that with\niteration it'll both:\n\n  - take longer for us to crash\n\n  - require way more memory along the way\n\nSo the evil garbage would continue to be a nuisance for users who want\nto clone such a repository, but now it's going to be more of a nuisance\nfor hosting sites given that it could lead to out-of-memory situations.\n\nI guess the reasoning here is that for this to become a real problem the\n\".gitattributes\" file would need to be excessively huge. We're probably\ntalking about many millions or even billions of attributes before this\ncould cause an OOM situation. And such a file would be large enough to\nbust the typical limits that the likes of GitHub and GitLab have in\nplace, so Git hosters already protect themselves against this crafted\ninput, even if only indirectly so.\n\nThe other angle is of course the wasted compute that an adversary can\ncause. But I don't really mind that too much: there's enough benign\noperations that require a bunch of compute, so I don't really see a\nreason why one would need to craft a \"compute waster\" with malicious\ninput.\n\nSo personally I would've probably leaned into the direction of enforcing\na hard limit. I don't see a reason why anybody would need more than a\ncouple of recursions, it culls both compute and memory growth, and it\nallows us to have a proper error message in case the limit is busted.\nFurthermore, we can demonstrate right now that it wasn't possible to\nhave unlimited recursion anyway, which makes it easier to put a new\nlimit into place.\n\nBut following my above reasoning I think it's okay to turn this into\niteration, as well, though, but I'd like to hear whether my train of\nthought matches yours.\n\nThanks!\n\nPatrick\n"},{"id":"530561","messageId":"20251112070907.GA431661@coredump.intra.peff.net","threadId":"64466","inReplyTo":"F6B66286-64B0-47AB-A31D-50A253F001D5@gmail.com","subject":"Re: [PATCH] attr: avoid recursion when expanding attribute macros","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-11-12T07:09:07Z","receivedAt":"2025-11-12T07:09:13Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Nov 11, 2025 at 08:30:58PM -0500, Ben Knoble wrote:\n\n> My knowledge on memory models is a bit weak and I didn’t check\n> directly, but are we implicitly assuming that we are less likely to\n> run out of heap memory in such an evil case? In effect I suppose we’re\n> turning a stack overflow segfault into an OOM error?\n\nYes, I think you could think of it that way. But there are two reasons\nto prefer heap:\n\n  1. The heap limits are _way_ bigger. The stack size on Linux is\n     usually 8MB, and that is considered large. It's much smaller on\n     other platforms (and especially if you have multiple threads).\n\n  2. In C, you don't have many options for detecting the case of running\n     out of stack, let alone recovering from it. Whereas you can check\n     for heap allocation failures. We don't tend to do anything besides\n     die() in git, but it's still nicer to have a controlled die than a\n     segfault.\n\nSo switching out stack recursion to spending heap memory essentially\nmakes the problem go away, or at least turns it into one of the zillion\nother ways that you can convince Git to allocate a bunch of heap memory. ;)\n\n> The memory use has to go somewhere ;) presuming there’s no good way to\n> only keep the relevant entries in memory, since I can of course find a\n> large example that also uses each intermediate macro, so the code\n> would need to get a lot smarter to collapse equivalence classes, prune\n> unused paths, etc., which seems like a poor investment for what AFAICT\n> is a little-used feature*.\n\nWe have a hard limit of 100MB on attributes files, which is mostly a\nmade-up number (it was the size that GitHub had been limiting for all\nblobs for years, so we knew nobody would complain about instituting it).\nFrom the research in 3c50032ff5 (attr: ignore overly large gitattributes\nfiles, 2022-12-01), it would probably be fine to drop it by a factor of\n10 or more.\n\nThough I think you might be able to chain macros across files (so\n\".gitattributes\" introduces macro \"foo\", and the \"sub/.gitattributes\"\nintroduces \"bar\" which resolves to \"foo\", and so on). In which case your\ntotal size is larger, and only eventually limited by how deep a tree\nwe'll accept (another place where we recurse, but there is a\nconfigurable depth limit).\n\nSo for the most part Git's protection against these sort of resource\nconsumption attacks is: die if the process wants too many resources, and\npeople who try to tickle those limits are only hurting their own repos.\nIt does put people who host arbitrary Git repos on the hook for managing\nresources at the OS level (so greedy and malicious processes are killed\nrather than bringing down the rest of the system).\n\n-Peff\n"},{"id":"530562","messageId":"20251112071651.GB431661@coredump.intra.peff.net","threadId":"64466","inReplyTo":"aRQvyvMq61syGT7_@pks.im","subject":"Re: [PATCH] attr: avoid recursion when expanding attribute macros","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-11-12T07:16:51Z","receivedAt":"2025-11-12T07:16:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Nov 12, 2025 at 07:57:14AM +0100, Patrick Steinhardt wrote:\n\n> So personally I would've probably leaned into the direction of enforcing\n> a hard limit. I don't see a reason why anybody would need more than a\n> couple of recursions, it culls both compute and memory growth, and it\n> allows us to have a proper error message in case the limit is busted.\n> Furthermore, we can demonstrate right now that it wasn't possible to\n> have unlimited recursion anyway, which makes it easier to put a new\n> limit into place.\n> \n> But following my above reasoning I think it's okay to turn this into\n> iteration, as well, though, but I'd like to hear whether my train of\n> thought matches yours.\n\nYeah, it does match mine. If I wanted to waste a bunch of CPU and memory\non a hosting site, there are a lot easier ways to do that than with\nreally long gitattributes.\n\nI'm not at all opposed to putting in a hard limit on top. My general\nfeeling is that it never hurts to convert recursion to iteration; it\nonly gives us more options. I'm not planning to work on a hard limit\nmyself, but if you want to, be my guest. :)\n\nI think if we do (or even if we don't), it may also be reasonable to\nshrink the max attribute file size to 10MB or even smaller.\n\n-Peff\n"},{"id":"530563","messageId":"20251112071757.GC431661@coredump.intra.peff.net","threadId":"64466","inReplyTo":"20251112070907.GA431661@coredump.intra.peff.net","subject":"Re: [PATCH] attr: avoid recursion when expanding attribute macros","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-11-12T07:17:57Z","receivedAt":"2025-11-12T07:17:58Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Nov 12, 2025 at 02:09:07AM -0500, Jeff King wrote:\n\n> Though I think you might be able to chain macros across files (so\n> \".gitattributes\" introduces macro \"foo\", and the \"sub/.gitattributes\"\n> introduces \"bar\" which resolves to \"foo\", and so on). In which case your\n> total size is larger, and only eventually limited by how deep a tree\n> we'll accept (another place where we recurse, but there is a\n> configurable depth limit).\n\nI did poke at this briefly, and the answer is: no, you can't do that. We\nallow macro definitions only at the top-level. Which makes sense, as\notherwise you get into confusing dependencies between files.\n\n-Peff\n"},{"id":"530579","messageId":"aRRflKWKpUtfn9tw@pks.im","threadId":"64466","inReplyTo":"20251112071651.GB431661@coredump.intra.peff.net","subject":"Re: [PATCH] attr: avoid recursion when expanding attribute macros","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-11-12T10:21:08Z","receivedAt":"2025-11-12T10:21:17Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Wed, Nov 12, 2025 at 02:16:51AM -0500, Jeff King wrote:\n> On Wed, Nov 12, 2025 at 07:57:14AM +0100, Patrick Steinhardt wrote:\n> \n> > So personally I would've probably leaned into the direction of enforcing\n> > a hard limit. I don't see a reason why anybody would need more than a\n> > couple of recursions, it culls both compute and memory growth, and it\n> > allows us to have a proper error message in case the limit is busted.\n> > Furthermore, we can demonstrate right now that it wasn't possible to\n> > have unlimited recursion anyway, which makes it easier to put a new\n> > limit into place.\n> > \n> > But following my above reasoning I think it's okay to turn this into\n> > iteration, as well, though, but I'd like to hear whether my train of\n> > thought matches yours.\n> \n> Yeah, it does match mine. If I wanted to waste a bunch of CPU and memory\n> on a hosting site, there are a lot easier ways to do that than with\n> really long gitattributes.\n> \n> I'm not at all opposed to putting in a hard limit on top. My general\n> feeling is that it never hurts to convert recursion to iteration; it\n> only gives us more options. I'm not planning to work on a hard limit\n> myself, but if you want to, be my guest. :)\n> \n> I think if we do (or even if we don't), it may also be reasonable to\n> shrink the max attribute file size to 10MB or even smaller.\n\nI think for now it's okay to convert this into iteration and not\nintroduce a limit, at least as long as we keep an open mind about\nintroducing such a limit in the future. I don't really expect that\nanyone will ever abuse this, but if I'm wrong and this happens at one\npoint in time we may have to introduce the limit retroactively.\n\nSo: I'm happy with your patch, but it might make sense to summarize the\ndiscussion in the commit message.\n\nThanks!\n\nPatrick\n"},{"id":"530609","messageId":"xmqqjyzvqhdc.fsf@gitster.g","threadId":"64466","inReplyTo":"aRQvyvMq61syGT7_@pks.im","subject":"Re: [PATCH] attr: avoid recursion when expanding attribute macros","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-11-12T17:40:31Z","receivedAt":"2025-11-12T17:40:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt <ps@pks.im> writes:\n\n> That's fair, and as you demonstrate it's easy enough to turn recursion\n> into iteration. But it doesn't really solve the main problem: given\n> malicious input we'd now still crash eventually, even though we\n> ...\n> So the evil garbage would continue to be a nuisance for users who want\n> to clone such a repository, but now it's going to be more of a nuisance\n> for hosting sites given that it could lead to out-of-memory situations.\n\nThat assumes there are users who want to clone such a repository\nwith evil garbage in it, doesn't it?  I am not sure how likely there\nexist such people, and even less sure if we want to actively support\nsuch users or discourage them.\n\nI like the conversion from recursion to iteraiton as a general\nprinciple, but somehow I do not think this particular one is an\nissue that warrants more than minimum effort on it.\n\nI also wonder how common the use of attribute macros (other than the\nbuilt-in ones) are.  Are folks working at hosting sites have easy\naccess to public data (i.e., super \"git grep\" that lets them sample\nsome random subset among many public repositories and work on them)?\n\nThanks.\n"}]}