{"thread":{"id":"65643","subject":"[PATCH] evaluate the second argument of ALLOC_GROW only once","startedAt":"2026-05-15T18:16:58Z","lastAt":"2026-05-19T00:41:50Z","messageCount":8,"participants":["René Scharfe","Jeff King","Johannes Sixt"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"543422","messageId":"323f5677-301b-4d7a-b552-6606597c2b1f@web.de","threadId":"65643","inReplyTo":null,"subject":"[PATCH] evaluate the second argument of ALLOC_GROW only once","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-05-15T18:16:50Z","receivedAt":"2026-05-15T18:16:58Z","isPatch":true,"body":"Allow the new element count passed to ALLOC_GROW to be a complex\nexpression with side-effects by evaluating it only once, as a parameter\nto a new helper function.\n\nSuggested-by: Junio C Hamano <gitster@pobox.com>\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n git-compat-util.h | 20 ++++++++++++++------\n 1 file changed, 14 insertions(+), 6 deletions(-)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex ae1bdc90a4..2bc1f43f48 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -812,6 +812,16 @@ static inline void move_array(void *dst, const void *src, size_t n, size_t size)\n \n #define alloc_nr(x) (((x)+16)*3/2)\n \n+static inline bool st_alloc_nr(size_t nr, size_t alloc, size_t *outp)\n+{\n+\tif (nr > alloc) {\n+\t\tsize_t out = alloc_nr(alloc);\n+\t\t*outp = out < nr ? nr : out;\n+\t\treturn true;\n+\t}\n+\treturn false;\n+}\n+\n /**\n  * Dynamically growing an array using realloc() is error prone and boring.\n  *\n@@ -857,12 +867,10 @@ static inline void move_array(void *dst, const void *src, size_t n, size_t size)\n  */\n #define ALLOC_GROW(x, nr, alloc) \\\n \tdo { \\\n-\t\tif ((nr) > alloc) { \\\n-\t\t\tif (alloc_nr(alloc) < (nr)) \\\n-\t\t\t\talloc = (nr); \\\n-\t\t\telse \\\n-\t\t\t\talloc = alloc_nr(alloc); \\\n-\t\t\tREALLOC_ARRAY(x, alloc); \\\n+\t\tsize_t alloc_grow_new_alloc_; \\\n+\t\tif (st_alloc_nr((nr), (alloc), &alloc_grow_new_alloc_)) { \\\n+\t\t\talloc = alloc_grow_new_alloc_; \\\n+\t\t\tREALLOC_ARRAY(x, alloc_grow_new_alloc_); \\\n \t\t} \\\n \t} while (0)\n \n-- \n2.54.0\n"},{"id":"543423","messageId":"20260515190818.GA98370@coredump.intra.peff.net","threadId":"65643","inReplyTo":"323f5677-301b-4d7a-b552-6606597c2b1f@web.de","subject":"Re: [PATCH] evaluate the second argument of ALLOC_GROW only once","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-15T19:08:18Z","receivedAt":"2026-05-15T19:08:20Z","isPatch":true,"body":"On Fri, May 15, 2026 at 08:16:50PM +0200, René Scharfe wrote:\n\n> +\t\tsize_t alloc_grow_new_alloc_; \\\n> +\t\tif (st_alloc_nr((nr), (alloc), &alloc_grow_new_alloc_)) { \\\n> +\t\t\talloc = alloc_grow_new_alloc_; \\\n> +\t\t\tREALLOC_ARRAY(x, alloc_grow_new_alloc_); \\\n>  \t\t} \\\n\nWhat happens if a caller passes in an argument that isn't a size_t?\nWe'll check for overflow in the size_t space, and then truncate it when\nwe assign to alloc, I think.\n\nI think we generally try to hold allocations in size_t these days, but\nI'd be surprised if there weren't a few \"int\" holdouts. Grepping around,\nalloc_node() seems to be an example.\n\nBTW, non-size_t arguments nullifies my earlier hand-waving around \"nr +\n1 overflowing implies we've filled up the address space\". But we are\nstill protected in the existing code by the:\n\n  if (alloc_nr(alloc) < (nr))\n\talloc = (nr);\n\nlogic. But with your patch, that all happens in the size_t space, so I\nthink it would actually introduce possible array overflows when the\ncaller is using a smaller type.\n\n-Peff\n"},{"id":"543424","messageId":"20260515195049.GA149960@coredump.intra.peff.net","threadId":"65643","inReplyTo":"20260515190818.GA98370@coredump.intra.peff.net","subject":"Re: [PATCH] evaluate the second argument of ALLOC_GROW only once","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-15T19:50:49Z","receivedAt":"2026-05-15T19:50:51Z","isPatch":true,"body":"On Fri, May 15, 2026 at 03:08:18PM -0400, Jeff King wrote:\n\n> On Fri, May 15, 2026 at 08:16:50PM +0200, René Scharfe wrote:\n> \n> > +\t\tsize_t alloc_grow_new_alloc_; \\\n> > +\t\tif (st_alloc_nr((nr), (alloc), &alloc_grow_new_alloc_)) { \\\n> > +\t\t\talloc = alloc_grow_new_alloc_; \\\n> > +\t\t\tREALLOC_ARRAY(x, alloc_grow_new_alloc_); \\\n> >  \t\t} \\\n> \n> What happens if a caller passes in an argument that isn't a size_t?\n> We'll check for overflow in the size_t space, and then truncate it when\n> we assign to alloc, I think.\n> \n> I think we generally try to hold allocations in size_t these days, but\n> I'd be surprised if there weren't a few \"int\" holdouts. Grepping around,\n> alloc_node() seems to be an example.\n> \n> BTW, non-size_t arguments nullifies my earlier hand-waving around \"nr +\n> 1 overflowing implies we've filled up the address space\". But we are\n> still protected in the existing code by the:\n> \n>   if (alloc_nr(alloc) < (nr))\n> \talloc = (nr);\n> \n> logic. But with your patch, that all happens in the size_t space, so I\n> think it would actually introduce possible array overflows when the\n> caller is using a smaller type.\n\nHmm, playing with it and looking a little closer, I think we don't end\nup overflowing the buffer because you use the size_t for\nREALLOC_ARRAY(). So the result is big, but then \"alloc\" is truncated.\n\nAnd then on the next call, we think \"oh no, the allocation is way too\nsmall\" because we are using the truncated value. So we try to size up\nfor every single allocation, even though it's actually big enough, and\nthe program slows to a crawl. ;)\n\nFor reference, IU was using this hack to play around and demonstrate:\n\ndiff --git a/git.c b/git.c\nindex 5a40eab8a2..638bbc69e4 100644\n--- a/git.c\n+++ b/git.c\n@@ -969,6 +969,19 @@ int cmd_main(int argc, const char **argv)\n \n \tcmd = argv[0];\n \n+\tif (!strcmp(cmd, \"foo\")) {\n+\t\tunsigned char *buf = NULL;\n+\t\tunsigned nr = 0, alloc = 0;\n+\t\tfor (unsigned i = 0; i < UINT_MAX; i++) {\n+\t\t\tALLOC_GROW(buf, nr + 1, alloc);\n+\t\t\tif (i % 313370 == 0)\n+\t\t\t\twarning(\"at i=%u, alloc=%u, nr=%u\", i, alloc, nr);\n+\t\t\tbuf[nr++] = i % 256;\n+\t\t}\n+\t\tprintf(\"done, final nr=%u, alloc=%u\\n\", nr, alloc);\n+\t\treturn 0;\n+\t}\n+\n \t/*\n \t * We use PATH to find git commands, but we prepend some higher\n \t * precedence paths: the \"--exec-path\" option, the GIT_EXEC_PATH\n\n\nThe same problem exists in several places in actual code, but I'm not\nsure how practical it is to trigger. The alloc_node() is counting not\njust objects, but blocks of objects. So you'd need 2*31 * 1024 objects\nof one type, which is probably going to run afoul of other limitations.\nOther cases are similar; for example \"yes | git fetch-pack --stdin foo\"\nwill grow an array indefinitely, but at one strbuf per line it starts\nswapping on my 64GB machine at only 350M entries.\n\nI think as long as the behavior remains \"slow, but we do not overflow\nany buffers\" when you reach these limits, that's OK. Nobody is going to\ndo it in practice, and we just want to make sure that malicious inputs\ncannot get out-of-bounds writes. It might be worth adding a comment,\nthough, to make sure nobody ever swaps \"alloc_grow_new_alloc_\" for\n\"alloc\" in that macro.\n\n-Peff\n"},{"id":"543427","messageId":"1d79d7bc-5441-4e72-9cb0-e8900f57172c@web.de","threadId":"65643","inReplyTo":"20260515195049.GA149960@coredump.intra.peff.net","subject":"Re: [PATCH] evaluate the second argument of ALLOC_GROW only once","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-05-15T23:01:05Z","receivedAt":"2026-05-15T23:01:07Z","isPatch":true,"body":"On 5/15/26 9:50 PM, Jeff King wrote:\n> On Fri, May 15, 2026 at 03:08:18PM -0400, Jeff King wrote:\n> \n>> On Fri, May 15, 2026 at 08:16:50PM +0200, René Scharfe wrote:\n>>\n>>> +\t\tsize_t alloc_grow_new_alloc_; \\\n>>> +\t\tif (st_alloc_nr((nr), (alloc), &alloc_grow_new_alloc_)) { \\\n>>> +\t\t\talloc = alloc_grow_new_alloc_; \\\n>>> +\t\t\tREALLOC_ARRAY(x, alloc_grow_new_alloc_); \\\n>>>  \t\t} \\\n>>\n>> What happens if a caller passes in an argument that isn't a size_t?\n>> We'll check for overflow in the size_t space, and then truncate it when\n>> we assign to alloc, I think.\n>>\n>> I think we generally try to hold allocations in size_t these days, but\n>> I'd be surprised if there weren't a few \"int\" holdouts. Grepping around,\n>> alloc_node() seems to be an example.\n>>\n>> BTW, non-size_t arguments nullifies my earlier hand-waving around \"nr +\n>> 1 overflowing implies we've filled up the address space\". But we are\n>> still protected in the existing code by the:\n>>\n>>   if (alloc_nr(alloc) < (nr))\n>> \talloc = (nr);\n>>\n>> logic. But with your patch, that all happens in the size_t space, so I\n>> think it would actually introduce possible array overflows when the\n>> caller is using a smaller type.\n> \n> Hmm, playing with it and looking a little closer, I think we don't end\n> up overflowing the buffer because you use the size_t for\n> REALLOC_ARRAY(). So the result is big, but then \"alloc\" is truncated.\n> \n> And then on the next call, we think \"oh no, the allocation is way too\n> small\" because we are using the truncated value. So we try to size up\n> for every single allocation, even though it's actually big enough, and\n> the program slows to a crawl. ;)\n> \n> For reference, IU was using this hack to play around and demonstrate:\n> \n> diff --git a/git.c b/git.c\n> index 5a40eab8a2..638bbc69e4 100644\n> --- a/git.c\n> +++ b/git.c\n> @@ -969,6 +969,19 @@ int cmd_main(int argc, const char **argv)\n>  \n>  \tcmd = argv[0];\n>  \n> +\tif (!strcmp(cmd, \"foo\")) {\n> +\t\tunsigned char *buf = NULL;\n> +\t\tunsigned nr = 0, alloc = 0;\n> +\t\tfor (unsigned i = 0; i < UINT_MAX; i++) {\n> +\t\t\tALLOC_GROW(buf, nr + 1, alloc);\n> +\t\t\tif (i % 313370 == 0)\n> +\t\t\t\twarning(\"at i=%u, alloc=%u, nr=%u\", i, alloc, nr);\n> +\t\t\tbuf[nr++] = i % 256;\n> +\t\t}\n> +\t\tprintf(\"done, final nr=%u, alloc=%u\\n\", nr, alloc);\n> +\t\treturn 0;\n> +\t}\n> +\n>  \t/*\n>  \t * We use PATH to find git commands, but we prepend some higher\n>  \t * precedence paths: the \"--exec-path\" option, the GIT_EXEC_PATH\n> \n> \n> The same problem exists in several places in actual code, but I'm not\n> sure how practical it is to trigger. The alloc_node() is counting not\n> just objects, but blocks of objects. So you'd need 2*31 * 1024 objects\n> of one type, which is probably going to run afoul of other limitations.\n> Other cases are similar; for example \"yes | git fetch-pack --stdin foo\"\n> will grow an array indefinitely, but at one strbuf per line it starts\n> swapping on my 64GB machine at only 350M entries.\n> \n> I think as long as the behavior remains \"slow, but we do not overflow\n> any buffers\" when you reach these limits, that's OK. Nobody is going to\n> do it in practice, and we just want to make sure that malicious inputs\n> cannot get out-of-bounds writes. It might be worth adding a comment,\n> though, to make sure nobody ever swaps \"alloc_grow_new_alloc_\" for\n> \"alloc\" in that macro.\nThere is no overflow check in either version (yet), so neither is safe\nto operate close to the boundary.  Close meaning the intermediate term\n(alloc + 16) * 3 being bigger than the maximum value.\n\nDoes the size_t arithmetic make matters worse?  The only change I can\nsee is that it interprets negative values as big unsigned ones and\nthen doesn't reallocate.  The outcome for positive values is the same,\noverflow and all, no?\n\nHere's a demo program exercising the arithmetic part of the macros:\n\n\n#include <limits.h>\n#include <stdbool.h>\n#include <stdio.h>\n\n#define alloc_nr(x) (((x)+16)*3/2)\n\n#define ALLOC_GROW1(x, nr, alloc) \\\n\tdo { \\\n\t\tif ((nr) > alloc) { \\\n\t\t\tif (alloc_nr(alloc) < (nr)) \\\n\t\t\t\talloc = (nr); \\\n\t\t\telse \\\n\t\t\t\talloc = alloc_nr(alloc); \\\n\t\t\tx = true; \\\n\t\t} \\\n\t} while (0)\n\nstatic inline bool st_alloc_nr(size_t nr, size_t alloc, size_t *outp)\n{\n\tif (nr > alloc) {\n\t\tsize_t out = alloc_nr(alloc);\n\t\t*outp = out < nr ? nr : out;\n\t\treturn true;\n\t}\n\treturn false;\n}\n\n\n#define ALLOC_GROW2(x, nr, alloc) \\\n\tdo { \\\n\t\tsize_t alloc_grow_new_alloc_; \\\n\t\tif (st_alloc_nr((nr), (alloc), &alloc_grow_new_alloc_)) { \\\n\t\t\talloc = alloc_grow_new_alloc_; \\\n\t\t\tx = true; \\\n\t\t} \\\n\t} while (0)\n\n#define T signed char\n#define MIN 0\n#define MAX SCHAR_MAX\n\nint main(int argc, char **argv)\n{\n\tfor (T i = 0;; i++) {\n\t\tfor (T j = MIN;; j++) {\n\t\t\tT alloc1 = j, alloc2 = j;\n\t\t\tbool allocated1 = false, allocated2 = false;\n\t\t\tALLOC_GROW1(allocated1, i, alloc1);\n\t\t\tALLOC_GROW2(allocated2, i, alloc2);\n\t\t\tif (alloc1 != alloc2 || allocated1 != allocated2)\n\t\t\t\tprintf(\"%zu %zu %d %zu %d %zu\\n\",\n\t\t\t\t       (size_t)i, (size_t)j,\n\t\t\t\t       allocated1, (size_t)alloc1,\n\t\t\t\t       allocated2, (size_t)alloc2);\n\t\t\tif (j == MAX)\n\t\t\t\tbreak;\n\t\t}\n\t\tif (i == MAX)\n\t\t\tbreak;\n\t}\n\treturn 0;\n}\n\n\n"},{"id":"543436","messageId":"20260516025119.GA832077@coredump.intra.peff.net","threadId":"65643","inReplyTo":"1d79d7bc-5441-4e72-9cb0-e8900f57172c@web.de","subject":"Re: [PATCH] evaluate the second argument of ALLOC_GROW only once","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-16T02:51:19Z","receivedAt":"2026-05-16T02:51:21Z","isPatch":true,"body":"On Sat, May 16, 2026 at 01:01:05AM +0200, René Scharfe wrote:\n\n> > I think as long as the behavior remains \"slow, but we do not overflow\n> > any buffers\" when you reach these limits, that's OK. Nobody is going to\n> > do it in practice, and we just want to make sure that malicious inputs\n> > cannot get out-of-bounds writes. It might be worth adding a comment,\n> > though, to make sure nobody ever swaps \"alloc_grow_new_alloc_\" for\n> > \"alloc\" in that macro.\n> There is no overflow check in either version (yet), so neither is safe\n> to operate close to the boundary.  Close meaning the intermediate term\n> (alloc + 16) * 3 being bigger than the maximum value.\n\nYes, but for some definition of safe. Both before and after your patch,\nas we get close to the boundary the allocation will grow slower than it\nshould, but we'll never write out of bounds. The behavior for the \"git\nfoo\" I showed earlier is slightly different:\n\n  - before your patch, ~2GB we stop doubling and instead start growing\n    the array by one at each ALLOC_GROW() call. This is because\n    alloc_nr() overflows to a small value, but the:\n\n      if (alloc_nr(alloc) < (nr))\n              alloc = (nr);\n\n    check kicks in.\n\n  - after your patch we grow to ~4GB, and then things get super slow.\n    This is because we correctly compute the new allocation as a size_t,\n    but then truncate it while assigning to alloc. So on the next\n    ALLOC_GROW() call, we'll think the buffer is way too small and try\n    to realloc again. I don't know why this is so much slower than the\n    grow-by-one above, but it is.\n\nNeither is really correct, but both are in the realm of OK: stupidly\nlarge input doesn't perform well, but there's no buffer overflow\nvulnerability.\n\nWhat I was worried about is what happens if you tweak your patch like\nthis:\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex 2bc1f43f48..0730dd24ad 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -870,7 +870,7 @@ static inline bool st_alloc_nr(size_t nr, size_t alloc, size_t *outp)\n \t\tsize_t alloc_grow_new_alloc_; \\\n \t\tif (st_alloc_nr((nr), (alloc), &alloc_grow_new_alloc_)) { \\\n \t\t\talloc = alloc_grow_new_alloc_; \\\n-\t\t\tREALLOC_ARRAY(x, alloc_grow_new_alloc_); \\\n+\t\t\tREALLOC_ARRAY(x, alloc); \\\n \t\t} \\\n \t} while (0)\n \n\nIn that case we really do end up with too-small allocations and\nout-of-bounds writes.\n\nMaybe you saw that coming and that's why you wrote it as you did. But it\nis definitely subtle enough that I think it would merit a big warning\ncomment that \"alloc\" and \"alloc_grow_new_alloc_\" are not necessarily the\nsame type, and hence not necessarily the same value.\n\n> Here's a demo program exercising the arithmetic part of the macros:\n\nI think the difference isn't in the arithmetic values that come out, but\nin what is fed to realloc() itself. And in your harness, realloc is just\n\"x = true\". If you actually store the value that would be passed to\nrealloc() like this:\n\ndiff --git a/foo.c.orig b/foo.c\nindex 2fbce8c..7498f36 100644\n--- a/foo.c.orig\n+++ b/foo.c\n@@ -11,7 +11,7 @@\n \t\t\t\talloc = (nr); \\\n \t\t\telse \\\n \t\t\t\talloc = alloc_nr(alloc); \\\n-\t\t\tx = true; \\\n+\t\t\tx = alloc; \\\n \t\t} \\\n \t} while (0)\n \n@@ -31,7 +31,7 @@ static inline bool st_alloc_nr(size_t nr, size_t alloc, size_t *outp)\n \t\tsize_t alloc_grow_new_alloc_; \\\n \t\tif (st_alloc_nr((nr), (alloc), &alloc_grow_new_alloc_)) { \\\n \t\t\talloc = alloc_grow_new_alloc_; \\\n-\t\t\tx = true; \\\n+\t\t\tx = alloc_grow_new_alloc_; \\\n \t\t} \\\n \t} while (0)\n \n@@ -44,7 +44,7 @@ int main(int argc, char **argv)\n \tfor (T i = 0;; i++) {\n \t\tfor (T j = MIN;; j++) {\n \t\t\tT alloc1 = j, alloc2 = j;\n-\t\t\tbool allocated1 = false, allocated2 = false;\n+\t\t\tsize_t allocated1 = 0, allocated2 = 0;\n \t\t\tALLOC_GROW1(allocated1, i, alloc1);\n \t\t\tALLOC_GROW2(allocated2, i, alloc2);\n \t\t\tif (alloc1 != alloc2 || allocated1 != allocated2)\n\nthen you see the differences. For negative values, yeah, you end up with\nbig size_t values. But for an unsigned type you get different small\nallocations.\n\n-Peff\n"},{"id":"543438","messageId":"9ce768d4-0cbf-4494-a1d3-55fd3b05b61e@kdbg.org","threadId":"65643","inReplyTo":"20260515195049.GA149960@coredump.intra.peff.net","subject":"Re: [PATCH] evaluate the second argument of ALLOC_GROW only once","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2026-05-16T06:55:54Z","receivedAt":"2026-05-16T06:56:03Z","isPatch":true,"body":"Am 15.05.26 um 21:50 schrieb Jeff King:\n> On Fri, May 15, 2026 at 03:08:18PM -0400, Jeff King wrote:\n> \n>> On Fri, May 15, 2026 at 08:16:50PM +0200, René Scharfe wrote:\n>>\n>>> +\t\tsize_t alloc_grow_new_alloc_; \\\n>>> +\t\tif (st_alloc_nr((nr), (alloc), &alloc_grow_new_alloc_)) { \\\n>>> +\t\t\talloc = alloc_grow_new_alloc_; \\\n>>> +\t\t\tREALLOC_ARRAY(x, alloc_grow_new_alloc_); \\\n>>>  \t\t} \\\n>>\n>> What happens if a caller passes in an argument that isn't a size_t?\n>> We'll check for overflow in the size_t space, and then truncate it when\n>> we assign to alloc, I think.\n\n> \n> Hmm, playing with it and looking a little closer, I think we don't end\n> up overflowing the buffer because you use the size_t for\n> REALLOC_ARRAY(). So the result is big, but then \"alloc\" is truncated.\n\nProtect against double-evaluation of \"alloc\", too, using\n\n\tsize_t *palloc = &(alloc);\n\nand use *palloc in the two places, then all callers are forced to work\nwith a size_t as third argument. Don't know what the damage would be,\nthough.\n\n-- Hannes\n\n"},{"id":"543446","messageId":"23be5317-4f28-4871-8aab-5281f4da5f0e@web.de","threadId":"65643","inReplyTo":"20260516025119.GA832077@coredump.intra.peff.net","subject":"Re: [PATCH] evaluate the second argument of ALLOC_GROW only once","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-05-16T11:10:09Z","receivedAt":"2026-05-16T11:10:12Z","isPatch":true,"body":"On 5/16/26 4:51 AM, Jeff King wrote:\n> On Sat, May 16, 2026 at 01:01:05AM +0200, René Scharfe wrote:\n> \n>>> I think as long as the behavior remains \"slow, but we do not overflow\n>>> any buffers\" when you reach these limits, that's OK. Nobody is going to\n>>> do it in practice, and we just want to make sure that malicious inputs\n>>> cannot get out-of-bounds writes. It might be worth adding a comment,\n>>> though, to make sure nobody ever swaps \"alloc_grow_new_alloc_\" for\n>>> \"alloc\" in that macro.\n>> There is no overflow check in either version (yet), so neither is safe\n>> to operate close to the boundary.  Close meaning the intermediate term\n>> (alloc + 16) * 3 being bigger than the maximum value.\n> \n> Yes, but for some definition of safe. Both before and after your patch,\n> as we get close to the boundary the allocation will grow slower than it\n> should, but we'll never write out of bounds. The behavior for the \"git\n> foo\" I showed earlier is slightly different:\n> \n>   - before your patch, ~2GB we stop doubling and instead start growing\n>     the array by one at each ALLOC_GROW() call. This is because\n>     alloc_nr() overflows to a small value, but the:\n> \n>       if (alloc_nr(alloc) < (nr))\n>               alloc = (nr);\n> \n>     check kicks in.\n> \n>   - after your patch we grow to ~4GB, and then things get super slow.\n>     This is because we correctly compute the new allocation as a size_t,\n>     but then truncate it while assigning to alloc. So on the next\n>     ALLOC_GROW() call, we'll think the buffer is way too small and try\n>     to realloc again. I don't know why this is so much slower than the\n>     grow-by-one above, but it is.\n> \n> Neither is really correct, but both are in the realm of OK: stupidly\n> large input doesn't perform well, but there's no buffer overflow\n> vulnerability.\n> \n> What I was worried about is what happens if you tweak your patch like\n> this:\n> \n> diff --git a/git-compat-util.h b/git-compat-util.h\n> index 2bc1f43f48..0730dd24ad 100644\n> --- a/git-compat-util.h\n> +++ b/git-compat-util.h\n> @@ -870,7 +870,7 @@ static inline bool st_alloc_nr(size_t nr, size_t alloc, size_t *outp)\n>  \t\tsize_t alloc_grow_new_alloc_; \\\n>  \t\tif (st_alloc_nr((nr), (alloc), &alloc_grow_new_alloc_)) { \\\n>  \t\t\talloc = alloc_grow_new_alloc_; \\\n> -\t\t\tREALLOC_ARRAY(x, alloc_grow_new_alloc_); \\\n> +\t\t\tREALLOC_ARRAY(x, alloc); \\\n>  \t\t} \\\n>  \t} while (0)\n>  \n> \n> In that case we really do end up with too-small allocations and\n> out-of-bounds writes.\n> \n> Maybe you saw that coming and that's why you wrote it as you did. But it\n> is definitely subtle enough that I think it would merit a big warning\n> comment that \"alloc\" and \"alloc_grow_new_alloc_\" are not necessarily the\n> same type, and hence not necessarily the same value.\n\nIt was the economic thing to do: Fetching the value of user-supplied\nalloc variable makes no sense when we have our calculated size_t value\nat hand.\n\n>> Here's a demo program exercising the arithmetic part of the macros:\n> \n> I think the difference isn't in the arithmetic values that come out, but\n> in what is fed to realloc() itself. And in your harness, realloc is just\n> \"x = true\". If you actually store the value that would be passed to\n> realloc() like this:\n> \n> diff --git a/foo.c.orig b/foo.c\n> index 2fbce8c..7498f36 100644\n> --- a/foo.c.orig\n> +++ b/foo.c\n> @@ -11,7 +11,7 @@\n>  \t\t\t\talloc = (nr); \\\n>  \t\t\telse \\\n>  \t\t\t\talloc = alloc_nr(alloc); \\\n> -\t\t\tx = true; \\\n> +\t\t\tx = alloc; \\\n>  \t\t} \\\n>  \t} while (0)\n>  \n> @@ -31,7 +31,7 @@ static inline bool st_alloc_nr(size_t nr, size_t alloc, size_t *outp)\n>  \t\tsize_t alloc_grow_new_alloc_; \\\n>  \t\tif (st_alloc_nr((nr), (alloc), &alloc_grow_new_alloc_)) { \\\n>  \t\t\talloc = alloc_grow_new_alloc_; \\\n> -\t\t\tx = true; \\\n> +\t\t\tx = alloc_grow_new_alloc_; \\\n>  \t\t} \\\n>  \t} while (0)\n>  \n> @@ -44,7 +44,7 @@ int main(int argc, char **argv)\n>  \tfor (T i = 0;; i++) {\n>  \t\tfor (T j = MIN;; j++) {\n>  \t\t\tT alloc1 = j, alloc2 = j;\n> -\t\t\tbool allocated1 = false, allocated2 = false;\n> +\t\t\tsize_t allocated1 = 0, allocated2 = 0;\n>  \t\t\tALLOC_GROW1(allocated1, i, alloc1);\n>  \t\t\tALLOC_GROW2(allocated2, i, alloc2);\n>  \t\t\tif (alloc1 != alloc2 || allocated1 != allocated2)\n> \n> then you see the differences. For negative values, yeah, you end up with\n> big size_t values. But for an unsigned type you get different small\n> allocations.\nGood point.  For unsigned char I get differences starting at 156\nelements, here just the first few:\n\nunsigned char nr=156 0 (155 -> 0) vs 256 (155 -> 0)\nunsigned char nr=157 0 (155 -> 0) vs 256 (155 -> 0)\nunsigned char nr=157 2 (156 -> 2) vs 258 (156 -> 2)\n\nSo the current code cuts the allocation size to 0 if you have an\narray of 155 and ask for more entries.  That would cause a buffer\noverrun.  With the patch ALLOC_GROW actually grows the buffer.\n\nFor signed char I see a different failure mode:\n\nsigned char nr=71 18446744073709551489 (70 -> -127) vs 129 (70 -> -127)\nsigned char nr=72 18446744073709551489 (70 -> -127) vs 129 (70 -> -127)\nsigned char nr=72 18446744073709551490 (71 -> -126) vs 130 (71 -> -126)\n\nThe current code tries to allocate (something close to) infinity,\nwhich would terminate the program.  With the patch ALLOC_GROW\nactually grows the buffer.\n\nI don't see this for int and unsigned, though.  Weird C integer\npromotion rules hit us here, I guess.  Just this, as you mentioned:\n\nALLOC_GROW1 unsigned nr=1787844770 1787844770 (1787844769 -> 1787844770) step too small, abort\nALLOC_GROW1 int nr=1787844770 1787844770 (1787844769 -> 1787844770) step too small, abort\n\nThe demo code is now big and hairy enough to need its own\ntests, though.  *snicker*\n\nRené\n\n\n#include <limits.h>\n#include <stdbool.h>\n#include <stdio.h>\n\n#define alloc_nr(x) (((x)+16)*3/2)\n\n#define ALLOC_GROW1(x, nr, alloc) \\\n\tdo { \\\n\t\tif ((nr) > alloc) { \\\n\t\t\tif (alloc_nr(alloc) < (nr)) \\\n\t\t\t\talloc = (nr); \\\n\t\t\telse \\\n\t\t\t\talloc = alloc_nr(alloc); \\\n\t\t\tx = alloc; \\\n\t\t} \\\n\t} while (0)\n\nstatic inline bool st_alloc_nr(size_t nr, size_t alloc, size_t *outp)\n{\n\tif (nr > alloc) {\n\t\tsize_t out = alloc_nr(alloc);\n\t\t*outp = out < nr ? nr : out;\n\t\treturn true;\n\t}\n\treturn false;\n}\n\n\n#define ALLOC_GROW2(x, nr, alloc) \\\n\tdo { \\\n\t\tsize_t alloc_grow_new_alloc_; \\\n\t\tif (st_alloc_nr((nr), (alloc), &alloc_grow_new_alloc_)) { \\\n\t\t\talloc = alloc_grow_new_alloc_; \\\n\t\t\tx = alloc_grow_new_alloc_; \\\n\t\t} \\\n\t} while (0)\n\n#define COMPARE(T, P, nr, alloc1, alloc_sz1, alloc2, alloc_sz2) do { \\\n\tT orig_alloc1 = alloc1, orig_alloc2 = alloc2; \\\n\tALLOC_GROW1(alloc_sz1, nr, alloc1); \\\n\tALLOC_GROW2(alloc_sz2, nr, alloc2); \\\n\tif (alloc_sz1 != alloc_sz2) \\\n\t\tprintf(#T\" nr=\"P\" %zu (\"P\" -> \"P\") vs %zu (\"P\" -> \"P\")\\n\", \\\n\t\t       nr,  \\\n\t\t       alloc_sz1, orig_alloc1, alloc1, \\\n\t\t       alloc_sz2, orig_alloc2, alloc2); \\\n} while (0)\n\n#define COMPARE_ALL(T, MIN, MAX, P) do { \\\n\tfor (T nr = 0;; nr++) { \\\n\t\tfor (T alloc = MIN;; alloc++) { \\\n\t\t\tT alloc1 = alloc, alloc2 = alloc; \\\n\t\t\tsize_t alloc_sz1 = alloc1, alloc_sz2 = alloc2; \\\n\t\t\tCOMPARE(T, P, nr, alloc1, alloc_sz1, alloc2, alloc_sz2); \\\n\t\t\tif (alloc == MAX) \\\n\t\t\t\tbreak; \\\n\t\t} \\\n\t\tif (nr == MAX) \\\n\t\t\tbreak; \\\n\t} \\\n} while (0)\n\n#define COMPARE_GROWTH(T, MAX, P) do { \\\n\tT alloc1 = 0, alloc2 = 0; \\\n\tsize_t alloc_sz1 = 0, alloc_sz2 = 0; \\\n\tfor (T nr = 0;; nr++) { \\\n\t\tCOMPARE(T, P, nr, alloc1, alloc_sz1, alloc2, alloc_sz2); \\\n\t\tif (nr == MAX) \\\n\t\t\tbreak; \\\n\t} \\\n} while (0)\n\n#define CHECK_GROWTH_ONE(T, MAX, P, ALLOC_GROW) do { \\\n\tT alloc = 0; \\\n\tsize_t alloc_sz = 0; \\\n\tfor (T nr = 0;; nr++) { \\\n\t\tT orig_alloc = alloc; \\\n\t\tsize_t orig_alloc_sz = alloc_sz; \\\n\t\tALLOC_GROW(alloc_sz, nr, alloc); \\\n\t\tif (alloc_sz < (size_t)nr) \\\n\t\t\tprintf(#ALLOC_GROW\" \"#T\" nr=\"P\" %zu (\"P\" -> \"P\")\" \\\n\t\t\t       \" too small\\n\", \\\n\t\t\t       nr, alloc_sz, orig_alloc, alloc); \\\n\t\tif (alloc_sz > alloc_nr((size_t)nr)) \\\n\t\t\tprintf(#ALLOC_GROW\" \"#T\" nr=\"P\" %zu (\"P\" -> \"P\")\" \\\n\t\t\t       \" too big\\n\", \\\n\t\t\t       nr, alloc_sz, orig_alloc, alloc); \\\n\t\tif (alloc_sz > orig_alloc_sz && \\\n\t\t    alloc_sz - alloc_sz / 3 < orig_alloc_sz) { \\\n\t\t\tprintf(#ALLOC_GROW\" \"#T\" nr=\"P\" %zu (\"P\" -> \"P\")\" \\\n\t\t\t       \" step too small, abort\\n\", \\\n\t\t\t       nr, alloc_sz, orig_alloc, alloc); \\\n\t\t\tbreak; \\\n\t\t} \\\n\t\tif (nr == MAX) \\\n\t\t\tbreak; \\\n\t} \\\n} while (0)\n\n#define CHECK_GROWTH(T, MAX, P) do { \\\n\tCHECK_GROWTH_ONE(T, MAX, P, ALLOC_GROW1); \\\n\tCHECK_GROWTH_ONE(T, MAX, P, ALLOC_GROW2); \\\n} while (0)\n\nint main(int argc, char **argv)\n{\n\tCOMPARE_ALL(unsigned char, 0, UCHAR_MAX, \"%hhu\");\n\tCOMPARE_ALL(signed char, 0, SCHAR_MAX, \"%hhd\");\n\tCOMPARE_GROWTH(short, SHRT_MAX, \"%hd\");\n\tCHECK_GROWTH(short, SHRT_MAX, \"%hd\");\n\tCHECK_GROWTH(unsigned short, USHRT_MAX, \"%hu\");\n\tCHECK_GROWTH(unsigned, UINT_MAX, \"%u\");\n\tCHECK_GROWTH(int, INT_MAX, \"%d\");\n\treturn 0;\n}\n\n"},{"id":"543568","messageId":"20260519004143.GA1612961@coredump.intra.peff.net","threadId":"65643","inReplyTo":"9ce768d4-0cbf-4494-a1d3-55fd3b05b61e@kdbg.org","subject":"Re: [PATCH] evaluate the second argument of ALLOC_GROW only once","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-19T00:41:43Z","receivedAt":"2026-05-19T00:41:50Z","isPatch":true,"body":"On Sat, May 16, 2026 at 08:55:54AM +0200, Johannes Sixt wrote:\n\n> > Hmm, playing with it and looking a little closer, I think we don't end\n> > up overflowing the buffer because you use the size_t for\n> > REALLOC_ARRAY(). So the result is big, but then \"alloc\" is truncated.\n> \n> Protect against double-evaluation of \"alloc\", too, using\n> \n> \tsize_t *palloc = &(alloc);\n> \n> and use *palloc in the two places, then all callers are forced to work\n> with a size_t as third argument. Don't know what the damage would be,\n> though.\n\nI think it would be nice if all ALLOC_GROW() callers used a size_t, and\nthen we checked the size_t computation for overflow. But from a rough\nguess (taking your suggestion and trying to compile) we'd need to adjust\n~200 callers.\n\nAnd it's not just a straight conversion:\n\n  1. Sometimes the ability to represent a negative value is important,\n     and each site has to be audited. If we could agree on a \"as big as\n     size_t but signed\" type, that might help.\n\n  2. Changing the alloc variable type without the matching \"nr\" can\n     actually make things worse. We tend to catch overflow-by-1 for\n     signed types incidentally because it results in a stupidly large\n     allocation request. But if made our allocations correct, then we\n     might overflow on \"nr\" and start writing to some huge negative\n     offset before the array.\n\nSo I think it would be a fair bit of work, though I would feel better\nabout the resulting state.\n\n-Peff\n"}]}