{"thread":{"id":"65636","subject":"[PATCH 1/2] strbuf: use st_add3() in strbuf_grow()","startedAt":"2026-05-14T15:11:15Z","lastAt":"2026-05-19T00:57:19Z","messageCount":18,"participants":["René Scharfe","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"543326","messageId":"c6e9b337-c4fc-4cbd-ac32-e8d3814749b0@web.de","threadId":"65636","inReplyTo":null,"subject":"[PATCH 1/2] strbuf: use st_add3() in strbuf_grow()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-05-14T15:11:06Z","receivedAt":"2026-05-14T15:11:15Z","isPatch":true,"body":"Simplify the code by calling st_add3() to do overflow checks instead of\nopen-coding it.  This changes the error message to include the offending\nsummands, which can be helpful when tracking down the cause.\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n strbuf.c | 5 +----\n 1 file changed, 1 insertion(+), 4 deletions(-)\n\ndiff --git a/strbuf.c b/strbuf.c\nindex 3e04addc22..bb04d3910e 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -106,12 +106,9 @@ void strbuf_attach(struct strbuf *sb, void *buf, size_t len, size_t alloc)\n void strbuf_grow(struct strbuf *sb, size_t extra)\n {\n \tint new_buf = !sb->alloc;\n-\tif (unsigned_add_overflows(extra, 1) ||\n-\t    unsigned_add_overflows(sb->len, extra + 1))\n-\t\tdie(\"you want to use way too much memory\");\n \tif (new_buf)\n \t\tsb->buf = NULL;\n-\tALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);\n+\tALLOC_GROW(sb->buf, st_add3(sb->len, extra, 1), sb->alloc);\n \tif (new_buf)\n \t\tsb->buf[0] = '\\0';\n }\n-- \n2.54.0\n"},{"id":"543327","messageId":"0ded6062-f66a-4713-af24-d1b5aa654823@web.de","threadId":"65636","inReplyTo":"c6e9b337-c4fc-4cbd-ac32-e8d3814749b0@web.de","subject":"[PATCH 2/2] use __builtin_add_overflow() in st_add() with Clang","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-05-14T15:13:46Z","receivedAt":"2026-05-14T15:13:57Z","isPatch":true,"body":"Clang and GCC optimize away comparisons of overflow checks by checking\nthe carry flag on x64.  GCC does the same on ARM64, but Clang currently\n(version 22.1) doesn't.\n\nProvide a variant of st_add() that wraps __builtin_add_overflow() to\nhelp Clang optimize it.  Use it on all platforms for simplicity.\n\nOn an Apple M1 I get a nice speedup for a command that builds lots of\nstrings using a strbuf, which exercises the st_add3() in strbuf_grow()\nfor every line of output:\n\nBenchmark 1: ./git_main cat-file --batch-all-objects --batch-check='%(objectname)'\n  Time (mean ± σ):     119.8 ms ±   0.2 ms    [User: 113.0 ms, System: 5.8 ms]\n  Range (min … max):   119.6 ms … 120.4 ms    24 runs\n\nBenchmark 2: ./git cat-file --batch-all-objects --batch-check='%(objectname)'\n  Time (mean ± σ):     114.6 ms ±   0.1 ms    [User: 107.6 ms, System: 6.0 ms]\n  Range (min … max):   114.4 ms … 114.9 ms    25 runs\n\nSummary\n  ./git cat-file --batch-all-objects --batch-check='%(objectname)' ran\n    1.05 ± 0.00 times faster than ./git_main cat-file --batch-all-objects --batch-check='%(objectname)'\n\nSuggested-by: Jeff King <peff@peff.net>\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n git-compat-util.h | 12 ++++++++++++\n 1 file changed, 12 insertions(+)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex ae1bdc90a4..aa088d04bb 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -614,6 +614,17 @@ static inline bool strip_suffix(const char *str, const char *suffix,\n int git_open_cloexec(const char *name, int flags);\n #define git_open(name) git_open_cloexec(name, O_RDONLY)\n \n+/* Help Clang; GCC generates the same code for both variants. */\n+#if defined(__clang__)\n+static inline size_t st_add(size_t a, size_t b)\n+{\n+\tsize_t sum;\n+\tif (__builtin_add_overflow(a, b, &sum))\n+\t\tdie(\"size_t overflow: %\"PRIuMAX\" + %\"PRIuMAX,\n+\t\t    (uintmax_t)a, (uintmax_t)b);\n+\treturn sum;\n+}\n+#else\n static inline size_t st_add(size_t a, size_t b)\n {\n \tif (unsigned_add_overflows(a, b))\n@@ -621,6 +632,7 @@ static inline size_t st_add(size_t a, size_t b)\n \t\t    (uintmax_t)a, (uintmax_t)b);\n \treturn a + b;\n }\n+#endif\n #define st_add3(a,b,c)   st_add(st_add((a),(b)),(c))\n #define st_add4(a,b,c,d) st_add(st_add3((a),(b),(c)),(d))\n \n-- \n2.54.0\n"},{"id":"543353","messageId":"xmqqo6ihg690.fsf@gitster.g","threadId":"65636","inReplyTo":"c6e9b337-c4fc-4cbd-ac32-e8d3814749b0@web.de","subject":"Re: [PATCH 1/2] strbuf: use st_add3() in strbuf_grow()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-05-14T19:07:07Z","receivedAt":"2026-05-14T19:07:09Z","isPatch":true,"body":"René Scharfe <l.s.r@web.de> writes:\n\n> Simplify the code by calling st_add3() to do overflow checks instead of\n> open-coding it.  This changes the error message to include the offending\n> summands, which can be helpful when tracking down the cause.\n>\n> Signed-off-by: René Scharfe <l.s.r@web.de>\n> ---\n>  strbuf.c | 5 +----\n>  1 file changed, 1 insertion(+), 4 deletions(-)\n>\n> diff --git a/strbuf.c b/strbuf.c\n> index 3e04addc22..bb04d3910e 100644\n> --- a/strbuf.c\n> +++ b/strbuf.c\n> @@ -106,12 +106,9 @@ void strbuf_attach(struct strbuf *sb, void *buf, size_t len, size_t alloc)\n>  void strbuf_grow(struct strbuf *sb, size_t extra)\n>  {\n>  \tint new_buf = !sb->alloc;\n> -\tif (unsigned_add_overflows(extra, 1) ||\n> -\t    unsigned_add_overflows(sb->len, extra + 1))\n> -\t\tdie(\"you want to use way too much memory\");\n>  \tif (new_buf)\n>  \t\tsb->buf = NULL;\n> -\tALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);\n> +\tALLOC_GROW(sb->buf, st_add3(sb->len, extra, 1), sb->alloc);\n\nALLOC_GROW() being a macro that references its second argument three\ntimes, doesn't this rewrite rely on the compiler being clever enough\nto notice that checking for the same overflow three times is\npointless and does it only once?  I guess the original has the same\nissue already, so this may not be so bad but it makes me feel a bit\nqueasy.\n\n>  \tif (new_buf)\n>  \t\tsb->buf[0] = '\\0';\n>  }\n"},{"id":"543354","messageId":"xmqqjyt5g5zr.fsf@gitster.g","threadId":"65636","inReplyTo":"0ded6062-f66a-4713-af24-d1b5aa654823@web.de","subject":"Re: [PATCH 2/2] use __builtin_add_overflow() in st_add() with Clang","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-05-14T19:12:40Z","receivedAt":"2026-05-14T19:12:43Z","isPatch":true,"body":"René Scharfe <l.s.r@web.de> writes:\n\n> Provide a variant of st_add() that wraps __builtin_add_overflow() to\n> help Clang optimize it.  Use it on all platforms for simplicity.\n> ...\n> +/* Help Clang; GCC generates the same code for both variants. */\n> +#if defined(__clang__)\n> +static inline size_t st_add(size_t a, size_t b)\n> +{\n> +\tsize_t sum;\n> +\tif (__builtin_add_overflow(a, b, &sum))\n> +\t\tdie(\"size_t overflow: %\"PRIuMAX\" + %\"PRIuMAX,\n> +\t\t    (uintmax_t)a, (uintmax_t)b);\n> +\treturn sum;\n> +}\n> +#else\n>  static inline size_t st_add(size_t a, size_t b)\n>  {\n>  \tif (unsigned_add_overflows(a, b))\n> @@ -621,6 +632,7 @@ static inline size_t st_add(size_t a, size_t b)\n>  \t\t    (uintmax_t)a, (uintmax_t)b);\n>  \treturn a + b;\n>  }\n> +#endif\n\nMakes me wonder if we tweaked unsigned_add_overflows() to take an\nextra *dst parameter to match __builtin_add_overflow(), which of\ncourse requires us to all of 18 callsites, it might make the whole\nthing a bit simpler.  New uses of unsigned_add_overflows(), if we\never add them, would automatically benefit, right?\n"},{"id":"543359","messageId":"0c3b4e94-b56c-4c92-a4d8-0e4364f1257b@web.de","threadId":"65636","inReplyTo":"xmqqo6ihg690.fsf@gitster.g","subject":"Re: [PATCH 1/2] strbuf: use st_add3() in strbuf_grow()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-05-14T20:13:19Z","receivedAt":"2026-05-14T20:13:24Z","isPatch":true,"body":"On 5/14/26 9:07 PM, Junio C Hamano wrote:\n> René Scharfe <l.s.r@web.de> writes:\n> \n>> Simplify the code by calling st_add3() to do overflow checks instead of\n>> open-coding it.  This changes the error message to include the offending\n>> summands, which can be helpful when tracking down the cause.\n>>\n>> Signed-off-by: René Scharfe <l.s.r@web.de>\n>> ---\n>>  strbuf.c | 5 +----\n>>  1 file changed, 1 insertion(+), 4 deletions(-)\n>>\n>> diff --git a/strbuf.c b/strbuf.c\n>> index 3e04addc22..bb04d3910e 100644\n>> --- a/strbuf.c\n>> +++ b/strbuf.c\n>> @@ -106,12 +106,9 @@ void strbuf_attach(struct strbuf *sb, void *buf, size_t len, size_t alloc)\n>>  void strbuf_grow(struct strbuf *sb, size_t extra)\n>>  {\n>>  \tint new_buf = !sb->alloc;\n>> -\tif (unsigned_add_overflows(extra, 1) ||\n>> -\t    unsigned_add_overflows(sb->len, extra + 1))\n>> -\t\tdie(\"you want to use way too much memory\");\n>>  \tif (new_buf)\n>>  \t\tsb->buf = NULL;\n>> -\tALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);\n>> +\tALLOC_GROW(sb->buf, st_add3(sb->len, extra, 1), sb->alloc);\n> \n> ALLOC_GROW() being a macro that references its second argument three\n> times, doesn't this rewrite rely on the compiler being clever enough\n> to notice that checking for the same overflow three times is\n> pointless and does it only once?  I guess the original has the same\n> issue already, so this may not be so bad but it makes me feel a bit\n> queasy.\n\nAs long as it has no side-effect (as is the case for addition) and we\nkeep compiler optimization enabled we should be fine.\n\nI guess the reason for having multiple references as opposed to\nloading the value once into a private variable is to support arbitrary\ntypes.  In the end it needs to fit into a size_t, though.  Something\nlike this could bring the reference count down to one:\n\n--- 8< ---\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex ae1bdc90a4..ca89cfb0b3 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -812,6 +812,15 @@ 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 *out)\n+{\n+\tif (nr > alloc) {\n+\t\t*out = alloc_nr(alloc) < nr ? nr : alloc_nr(alloc);\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 +866,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--- >8 ---\n\nHmm, alloc_nr() doesn't do any overflow checking.  It should, though,\nshouldn't it?\n\nRené\n\n"},{"id":"543360","messageId":"fceded1f-60a2-48d2-91fc-5d2161272868@web.de","threadId":"65636","inReplyTo":"xmqqjyt5g5zr.fsf@gitster.g","subject":"Re: [PATCH 2/2] use __builtin_add_overflow() in st_add() with Clang","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-05-14T20:17:52Z","receivedAt":"2026-05-14T20:17:58Z","isPatch":true,"body":"On 5/14/26 9:12 PM, Junio C Hamano wrote:\n> René Scharfe <l.s.r@web.de> writes:\n> \n>> Provide a variant of st_add() that wraps __builtin_add_overflow() to\n>> help Clang optimize it.  Use it on all platforms for simplicity.\n>> ...\n>> +/* Help Clang; GCC generates the same code for both variants. */\n>> +#if defined(__clang__)\n>> +static inline size_t st_add(size_t a, size_t b)\n>> +{\n>> +\tsize_t sum;\n>> +\tif (__builtin_add_overflow(a, b, &sum))\n>> +\t\tdie(\"size_t overflow: %\"PRIuMAX\" + %\"PRIuMAX,\n>> +\t\t    (uintmax_t)a, (uintmax_t)b);\n>> +\treturn sum;\n>> +}\n>> +#else\n>>  static inline size_t st_add(size_t a, size_t b)\n>>  {\n>>  \tif (unsigned_add_overflows(a, b))\n>> @@ -621,6 +632,7 @@ static inline size_t st_add(size_t a, size_t b)\n>>  \t\t    (uintmax_t)a, (uintmax_t)b);\n>>  \treturn a + b;\n>>  }\n>> +#endif\n> \n> Makes me wonder if we tweaked unsigned_add_overflows() to take an\n> extra *dst parameter to match __builtin_add_overflow(), which of\n> course requires us to all of 18 callsites, it might make the whole\n> thing a bit simpler.  New uses of unsigned_add_overflows(), if we\n> ever add them, would automatically benefit, right?\n\nHmm.  It sounds like a lot of churn, but it would make sure that\nwe use the checked result and not check a + b and then go on and\nuse x + y because the code de-synced at some point.\n\nHow to do it, though?  It needs to be generic and evaluate its\narguments only once.  Perhaps like this?\n\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex ca89cfb0b3..27fbb622d7 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -103,6 +103,21 @@ struct strbuf;\n #define unsigned_add_overflows(a, b) \\\n     ((b) > maximum_unsigned_value_of_type(a) - (a))\n \n+static bool uint_add_overflow(uintmax_t a, uintmax_t b,\n+\t\t\t      uintmax_t *out, size_t out_size)\n+{\n+\tif (b > UINTMAX_MAX - a)\n+\t\treturn true;\n+\ta += b;\n+\tif (a > (UINTMAX_MAX >> (bitsizeof(uintmax_t) - CHAR_BIT * out_size)))\n+\t\treturn true;\n+\t*out = a;\n+\treturn false;\n+}\n+\n+#define UINT_ADD_OVERFLOW(a, b, out) \\\n+\tuint_add_overflow((a), (b), (out), sizeof(a))\n+\n /*\n  * Returns true if the multiplication of \"a\" and \"b\" will\n  * overflow. The types of \"a\" and \"b\" must match and must be unsigned.\n@@ -616,10 +631,11 @@ int git_open_cloexec(const char *name, int flags);\n \n static inline size_t st_add(size_t a, size_t b)\n {\n-\tif (unsigned_add_overflows(a, b))\n+\tsize_t ret;\n+\tif (UINT_ADD_OVERFLOW(a, b, &ret))\n \t\tdie(\"size_t overflow: %\"PRIuMAX\" + %\"PRIuMAX,\n \t\t    (uintmax_t)a, (uintmax_t)b);\n-\treturn a + b;\n+\treturn ret;\n }\n #define st_add3(a,b,c)   st_add(st_add((a),(b)),(c))\n #define st_add4(a,b,c,d) st_add(st_add3((a),(b),(c)),(d))\n\n"},{"id":"543373","messageId":"20260515043606.GA83595@coredump.intra.peff.net","threadId":"65636","inReplyTo":"0c3b4e94-b56c-4c92-a4d8-0e4364f1257b@web.de","subject":"Re: [PATCH 1/2] strbuf: use st_add3() in strbuf_grow()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-15T04:36:06Z","receivedAt":"2026-05-15T04:36:07Z","isPatch":true,"body":"On Thu, May 14, 2026 at 10:13:19PM +0200, René Scharfe wrote:\n\n> Hmm, alloc_nr() doesn't do any overflow checking.  It should, though,\n> shouldn't it?\n\nYes, probably. It's a known blind spot in the overflow checking, but\nI think is OK in practice because:\n\n  1. We are growing an existing buffer by ~3/2. So even with ordering\n     the multiplication first, an overflow implies that you have a\n     single buffer consuming ~1/3 of your address space.\n\n     On 64-bit systems that's impractically large, and on 32-bit systems I\n     think you generally run into fragmentation and address-space issues\n     first.\n\n  2. If alloc_nr(alloc) is less than the desired nr, we just use that nr\n     directly. So even if we did overflow, I think the result is\n     too-slow allocation, and not a buffer overflow.\n\nBut it would be nice to be less hand-wavy. One of the reasons I hadn't\ndug into it further is that I wanted to start making use of intrinsics\nto avoid slowdowns. But since you're already doing that (and finding\nthat the compiler was doing the fast thing anyway!) it might be a good\ntime to make the jump.\n\nThat's all assuming that no overflow happens before ALLOC_GROW() gets\nthe values. We also tend to do unchecked computions for the \"nr\" field\nthere, but it's usually just \"nr_foo + 1\", so the same logic applies:\nyou'd have to have an existing array consuming the entire address space\nminus one byte to trigger an overflow.\n\n-Peff\n"},{"id":"543374","messageId":"20260515044059.GB83595@coredump.intra.peff.net","threadId":"65636","inReplyTo":"0ded6062-f66a-4713-af24-d1b5aa654823@web.de","subject":"Re: [PATCH 2/2] use __builtin_add_overflow() in st_add() with Clang","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-15T04:40:59Z","receivedAt":"2026-05-15T04:41:01Z","isPatch":true,"body":"On Thu, May 14, 2026 at 05:13:46PM +0200, René Scharfe wrote:\n\n> Clang and GCC optimize away comparisons of overflow checks by checking\n> the carry flag on x64.  GCC does the same on ARM64, but Clang currently\n> (version 22.1) doesn't.\n> \n> Provide a variant of st_add() that wraps __builtin_add_overflow() to\n> help Clang optimize it.  Use it on all platforms for simplicity.\n\nOK. I probably would have just used the intrinsic everywhere with\n__GNUC__, but if gcc is already figuring it out, it doesn't matter in\npractice.\n\n> +/* Help Clang; GCC generates the same code for both variants. */\n> +#if defined(__clang__)\n> +static inline size_t st_add(size_t a, size_t b)\n> +{\n> +\tsize_t sum;\n> +\tif (__builtin_add_overflow(a, b, &sum))\n> +\t\tdie(\"size_t overflow: %\"PRIuMAX\" + %\"PRIuMAX,\n> +\t\t    (uintmax_t)a, (uintmax_t)b);\n> +\treturn sum;\n> +}\n> +#else\n>  static inline size_t st_add(size_t a, size_t b)\n>  {\n>  \tif (unsigned_add_overflows(a, b))\n\nIt's a shame we can't share more code here, especially the die message.\n\nI guess the ideal primitive is probably a wrapper with the same\ninterface as __builtin_add_overflow(), which could then be used\neverywhere that unsigned_add_overflows() with some minor conversion.\n\nBut it gets awkward to do as a macro, and using an inline function runs\ninto type questions.\n\n-Peff\n"},{"id":"543401","messageId":"459f5f2b-2565-4dae-9f9f-8848a5cb9d94@web.de","threadId":"65636","inReplyTo":"20260515043606.GA83595@coredump.intra.peff.net","subject":"Re: [PATCH 1/2] strbuf: use st_add3() in strbuf_grow()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-05-15T14:30:34Z","receivedAt":"2026-05-15T14:30:40Z","isPatch":true,"body":"On 5/15/26 6:36 AM, Jeff King wrote:\n> On Thu, May 14, 2026 at 10:13:19PM +0200, René Scharfe wrote:\n> \n>> Hmm, alloc_nr() doesn't do any overflow checking.  It should, though,\n>> shouldn't it?\n> \n> Yes, probably. It's a known blind spot in the overflow checking, but\n> I think is OK in practice because:\n> \n>   1. We are growing an existing buffer by ~3/2. So even with ordering\n>      the multiplication first, an overflow implies that you have a\n>      single buffer consuming ~1/3 of your address space.\n> \n>      On 64-bit systems that's impractically large, and on 32-bit systems I\n>      think you generally run into fragmentation and address-space issues\n>      first.\n> \n>   2. If alloc_nr(alloc) is less than the desired nr, we just use that nr\n>      directly. So even if we did overflow, I think the result is\n>      too-slow allocation, and not a buffer overflow.\n> > But it would be nice to be less hand-wavy. One of the reasons I hadn't\n> dug into it further is that I wanted to start making use of intrinsics\n> to avoid slowdowns. But since you're already doing that (and finding\n> that the compiler was doing the fast thing anyway!) it might be a good\n> time to make the jump.\n\nDidn't look at __builtin_mul_overflow() in detail; its situation could\nbe  different than for __builtin_add_overflow(), which turned out to be\nunnecessary on x64.\n\n> That's all assuming that no overflow happens before ALLOC_GROW() gets\n> the values. We also tend to do unchecked computions for the \"nr\" field\n> there, but it's usually just \"nr_foo + 1\", so the same logic applies:\n> you'd have to have an existing array consuming the entire address space\n> minus one byte to trigger an overflow.\nThe use in read-cache.c::do_read_index() looks odd.  Has been present\nsince commit one.  Is the point that it over-allocates to have room for\nadditions right from the start?  For read-only commands this only wastes\nmemory, no?\n\nRené\n\n"},{"id":"543403","messageId":"26b71f9c-0cc5-4bfd-9175-f45b584e202e@web.de","threadId":"65636","inReplyTo":"20260515044059.GB83595@coredump.intra.peff.net","subject":"Re: [PATCH 2/2] use __builtin_add_overflow() in st_add() with Clang","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-05-15T14:36:15Z","receivedAt":"2026-05-15T14:36:23Z","isPatch":true,"body":"On 5/15/26 6:40 AM, Jeff King wrote:\n> On Thu, May 14, 2026 at 05:13:46PM +0200, René Scharfe wrote:\n> \n>> Clang and GCC optimize away comparisons of overflow checks by checking\n>> the carry flag on x64.  GCC does the same on ARM64, but Clang currently\n>> (version 22.1) doesn't.\n>>\n>> Provide a variant of st_add() that wraps __builtin_add_overflow() to\n>> help Clang optimize it.  Use it on all platforms for simplicity.\n> \n> OK. I probably would have just used the intrinsic everywhere with\n> __GNUC__, but if gcc is already figuring it out, it doesn't matter in\n> practice.\n\nDid that initially, but found it hard to justify when it has no benefit\nand reduces the test coverage of the hand-made check significantly.\n\n>> +/* Help Clang; GCC generates the same code for both variants. */\n>> +#if defined(__clang__)\n>> +static inline size_t st_add(size_t a, size_t b)\n>> +{\n>> +\tsize_t sum;\n>> +\tif (__builtin_add_overflow(a, b, &sum))\n>> +\t\tdie(\"size_t overflow: %\"PRIuMAX\" + %\"PRIuMAX,\n>> +\t\t    (uintmax_t)a, (uintmax_t)b);\n>> +\treturn sum;\n>> +}\n>> +#else\n>>  static inline size_t st_add(size_t a, size_t b)\n>>  {\n>>  \tif (unsigned_add_overflows(a, b))\n> \n> It's a shame we can't share more code here, especially the die message.\n> \n> I guess the ideal primitive is probably a wrapper with the same\n> interface as __builtin_add_overflow(), which could then be used\n> everywhere that unsigned_add_overflows() with some minor conversion.\n\nJunio said the same. :)\n> But it gets awkward to do as a macro, and using an inline function runs\n> into type questions.\nIndeed.  If it was easy then this wouldn't exist as a builtin.  We\ncan approximate it somewhat, but will it be robust enough?\n\nRené\n\n"},{"id":"543415","messageId":"bcd974c5-3748-442f-9f5c-5b05888e0bc8@web.de","threadId":"65636","inReplyTo":"fceded1f-60a2-48d2-91fc-5d2161272868@web.de","subject":"Re: [PATCH 2/2] use __builtin_add_overflow() in st_add() with Clang","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-05-15T16:49:41Z","receivedAt":"2026-05-15T16:49:49Z","isPatch":true,"body":"On 5/14/26 10:17 PM, René Scharfe wrote:\n> On 5/14/26 9:12 PM, Junio C Hamano wrote:\n>> René Scharfe <l.s.r@web.de> writes:\n>>\n>>> Provide a variant of st_add() that wraps __builtin_add_overflow() to\n>>> help Clang optimize it.  Use it on all platforms for simplicity.\n>>> ...\n>>> +/* Help Clang; GCC generates the same code for both variants. */\n>>> +#if defined(__clang__)\n>>> +static inline size_t st_add(size_t a, size_t b)\n>>> +{\n>>> +\tsize_t sum;\n>>> +\tif (__builtin_add_overflow(a, b, &sum))\n>>> +\t\tdie(\"size_t overflow: %\"PRIuMAX\" + %\"PRIuMAX,\n>>> +\t\t    (uintmax_t)a, (uintmax_t)b);\n>>> +\treturn sum;\n>>> +}\n>>> +#else\n>>>  static inline size_t st_add(size_t a, size_t b)\n>>>  {\n>>>  \tif (unsigned_add_overflows(a, b))\n>>> @@ -621,6 +632,7 @@ static inline size_t st_add(size_t a, size_t b)\n>>>  \t\t    (uintmax_t)a, (uintmax_t)b);\n>>>  \treturn a + b;\n>>>  }\n>>> +#endif\n>>\n>> Makes me wonder if we tweaked unsigned_add_overflows() to take an\n>> extra *dst parameter to match __builtin_add_overflow(), which of\n>> course requires us to all of 18 callsites, it might make the whole\n>> thing a bit simpler.  New uses of unsigned_add_overflows(), if we\n>> ever add them, would automatically benefit, right?\n> \n> Hmm.  It sounds like a lot of churn, but it would make sure that\n> we use the checked result and not check a + b and then go on and\n> use x + y because the code de-synced at some point.\n> \n> How to do it, though?  It needs to be generic and evaluate its\n> arguments only once.  Perhaps like this?\n> \n> \n> diff --git a/git-compat-util.h b/git-compat-util.h\n> index ca89cfb0b3..27fbb622d7 100644\n> --- a/git-compat-util.h\n> +++ b/git-compat-util.h\n> @@ -103,6 +103,21 @@ struct strbuf;\n>  #define unsigned_add_overflows(a, b) \\\n>      ((b) > maximum_unsigned_value_of_type(a) - (a))\n>  \n> +static bool uint_add_overflow(uintmax_t a, uintmax_t b,\n> +\t\t\t      uintmax_t *out, size_t out_size)\n> +{\n> +\tif (b > UINTMAX_MAX - a)\n> +\t\treturn true;\n> +\ta += b;\n> +\tif (a > (UINTMAX_MAX >> (bitsizeof(uintmax_t) - CHAR_BIT * out_size)))\n> +\t\treturn true;\n> +\t*out = a;\n> +\treturn false;\n> +}\n> +\n> +#define UINT_ADD_OVERFLOW(a, b, out) \\\n> +\tuint_add_overflow((a), (b), (out), sizeof(a))\n> +\n>  /*\n>   * Returns true if the multiplication of \"a\" and \"b\" will\n>   * overflow. The types of \"a\" and \"b\" must match and must be unsigned.\n> @@ -616,10 +631,11 @@ int git_open_cloexec(const char *name, int flags);\n>  \n>  static inline size_t st_add(size_t a, size_t b)\n>  {\n> -\tif (unsigned_add_overflows(a, b))\n> +\tsize_t ret;\n> +\tif (UINT_ADD_OVERFLOW(a, b, &ret))\n\nType mismatch of third argument: pointer to size_t given, pointer to\nuintmax_t expected.\n\n>  \t\tdie(\"size_t overflow: %\"PRIuMAX\" + %\"PRIuMAX,\n>  \t\t    (uintmax_t)a, (uintmax_t)b);\n> -\treturn a + b;\n> +\treturn ret;\n>  }\n>  #define st_add3(a,b,c)   st_add(st_add((a),(b)),(c))\n>  #define st_add4(a,b,c,d) st_add(st_add3((a),(b),(c)),(d))\nPerhaps like this instead?\n\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex ae1bdc90a4..23ea42f373 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -103,6 +103,25 @@ struct strbuf;\n #define unsigned_add_overflows(a, b) \\\n     ((b) > maximum_unsigned_value_of_type(a) - (a))\n \n+static inline uintmax_t uint_add_overflow(uintmax_t a, uintmax_t b,\n+\t\t\t\t\t  uintmax_t max, bool *overflow)\n+{\n+\t*overflow = a > max || b > max - a;\n+\treturn a + b;\n+}\n+\n+#ifdef __clang__\n+#define UINT_ADD_OVERFLOW(a, b, out, overflow) \\\n+\t(*(overflow) = __builtin_add_overflow((a), (b), (out)))\n+#else\n+#define UINT_ADD_OVERFLOW(a, b, out, overflow) ( \\\n+\t*(out) = uint_add_overflow((a), (b), \\\n+\t\t\t\t   maximum_unsigned_value_of_type(*(out)), \\\n+\t\t\t\t   (overflow)), \\\n+\t*(overflow) \\\n+)\n+#endif\n+\n /*\n  * Returns true if the multiplication of \"a\" and \"b\" will\n  * overflow. The types of \"a\" and \"b\" must match and must be unsigned.\n@@ -616,10 +635,12 @@ int git_open_cloexec(const char *name, int flags);\n \n static inline size_t st_add(size_t a, size_t b)\n {\n-\tif (unsigned_add_overflows(a, b))\n+\tbool overflow;\n+\tsize_t ret;\n+\tif (UINT_ADD_OVERFLOW(a, b, &ret, &overflow))\n \t\tdie(\"size_t overflow: %\"PRIuMAX\" + %\"PRIuMAX,\n \t\t    (uintmax_t)a, (uintmax_t)b);\n-\treturn a + b;\n+\treturn ret;\n }\n #define st_add3(a,b,c)   st_add(st_add((a),(b)),(c))\n #define st_add4(a,b,c,d) st_add(st_add3((a),(b),(c)),(d))\n\n"},{"id":"543416","messageId":"20260515165059.GA88375@coredump.intra.peff.net","threadId":"65636","inReplyTo":"459f5f2b-2565-4dae-9f9f-8848a5cb9d94@web.de","subject":"Re: [PATCH 1/2] strbuf: use st_add3() in strbuf_grow()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-15T16:50:59Z","receivedAt":"2026-05-15T16:51:01Z","isPatch":true,"body":"On Fri, May 15, 2026 at 04:30:34PM +0200, René Scharfe wrote:\n\n> > That's all assuming that no overflow happens before ALLOC_GROW() gets\n> > the values. We also tend to do unchecked computions for the \"nr\" field\n> > there, but it's usually just \"nr_foo + 1\", so the same logic applies:\n> > you'd have to have an existing array consuming the entire address space\n> > minus one byte to trigger an overflow.\n>\n> The use in read-cache.c::do_read_index() looks odd.  Has been present\n> since commit one.  Is the point that it over-allocates to have room for\n> additions right from the start?  For read-only commands this only wastes\n> memory, no?\n\nHmm, yeah, that is weird, and unusual to use alloc_nr() directly. We are\npresumably picking up istate->cache_nr from the on-disk file, so it\ncould be anything, and that alloc_nr() could overflow.\n\nWe'd store the too-small value in alloc, so we _know_ it's too small. So\nlater when we use ALLOC_GROW(), the problem would be resolved as we grow\nthe array. I'm not convinced the initial load might not overflow the\narray, though.\n\n-Peff\n"},{"id":"543417","messageId":"20260515165324.GB88375@coredump.intra.peff.net","threadId":"65636","inReplyTo":"26b71f9c-0cc5-4bfd-9175-f45b584e202e@web.de","subject":"Re: [PATCH 2/2] use __builtin_add_overflow() in st_add() with Clang","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-15T16:53:24Z","receivedAt":"2026-05-15T16:53:25Z","isPatch":true,"body":"On Fri, May 15, 2026 at 04:36:15PM +0200, René Scharfe wrote:\n\n> > I guess the ideal primitive is probably a wrapper with the same\n> > interface as __builtin_add_overflow(), which could then be used\n> > everywhere that unsigned_add_overflows() with some minor conversion.\n> \n> Junio said the same. :)\n> > But it gets awkward to do as a macro, and using an inline function runs\n> > into type questions.\n> Indeed.  If it was easy then this wouldn't exist as a builtin.  We\n> can approximate it somewhat, but will it be robust enough?\n\nI always thought it was a builtin because the most efficient way\ninvolves checking the carry flag, which can't be accessed from C.\n\nBut yeah, the type issues are real, too. ;)\n\nI think we should take what you posted for now, and we can iterate on a\nmore general add-and-check interface later (or never if it's too\ntricky).\n\n-Peff\n"},{"id":"543564","messageId":"20260518202502.25682-3-l.s.r@web.de","threadId":"65636","inReplyTo":"20260518202502.25682-1-l.s.r@web.de","subject":"[PATCH v2 2/2] use __builtin_add_overflow() in st_add() with Clang","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-05-18T20:25:02Z","receivedAt":"2026-05-18T20:25:15Z","isPatch":true,"body":"Clang and GCC optimize away comparisons of overflow checks by checking\nthe carry flag on x64.  GCC does the same on ARM64, but Clang currently\n(version 22.1) doesn't.\n\nIt does this optimization for overflow checks that use its builtin\nfunction __builtin_add_overflow(), though.  Provide a non-generic\nlookalike for size_t that does the same checks as before as a fallback\nand use the original with Clang.  Use it on all platforms for simplicity.\n\nOn an Apple M1 I get a nice speedup for a command that builds lots of\nstrings using a strbuf, which exercises the st_add3() in strbuf_grow()\nfor every line of output:\n\nBenchmark 1: ./git_main cat-file --batch-all-objects --batch-check='%(objectname)'\n  Time (mean ± σ):     120.4 ms ±   0.2 ms    [User: 113.8 ms, System: 6.0 ms]\n  Range (min … max):   120.1 ms … 121.1 ms    24 runs\n\nBenchmark 2: ./git cat-file --batch-all-objects --batch-check='%(objectname)'\n  Time (mean ± σ):     115.5 ms ±   0.1 ms    [User: 108.6 ms, System: 5.8 ms]\n  Range (min … max):   115.2 ms … 115.8 ms    25 runs\n\nSummary\n  ./git cat-file --batch-all-objects --batch-check='%(objectname)' ran\n    1.04 ± 0.00 times faster than ./git_main cat-file --batch-all-objects --batch-check='%(objectname)'\n\nSuggested-by: Jeff King <peff@peff.net>\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n git-compat-util.h | 22 ++++++++++++++++++++--\n 1 file changed, 20 insertions(+), 2 deletions(-)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex ae1bdc90a4..5b1d15fe4f 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -614,12 +614,30 @@ static inline bool strip_suffix(const char *str, const char *suffix,\n int git_open_cloexec(const char *name, int flags);\n #define git_open(name) git_open_cloexec(name, O_RDONLY)\n \n-static inline size_t st_add(size_t a, size_t b)\n+\n+/*\n+ * Help Clang; GCC generates the same instructions for both variants on\n+ * x64 and aarch64.\n+ */\n+#ifdef __clang__\n+#define st_add_overflow __builtin_add_overflow\n+#else\n+static inline bool st_add_overflow(size_t a, size_t b, size_t *out)\n {\n \tif (unsigned_add_overflows(a, b))\n+\t\treturn true;\n+\t*out = a + b;\n+\treturn false;\n+}\n+#endif\n+\n+static inline size_t st_add(size_t a, size_t b)\n+{\n+\tsize_t result;\n+\tif (st_add_overflow(a, b, &result))\n \t\tdie(\"size_t overflow: %\"PRIuMAX\" + %\"PRIuMAX,\n \t\t    (uintmax_t)a, (uintmax_t)b);\n-\treturn a + b;\n+\treturn result;\n }\n #define st_add3(a,b,c)   st_add(st_add((a),(b)),(c))\n #define st_add4(a,b,c,d) st_add(st_add3((a),(b),(c)),(d))\n-- \n2.54.0\n\n"},{"id":"543566","messageId":"20260518202502.25682-1-l.s.r@web.de","threadId":"65636","inReplyTo":"c6e9b337-c4fc-4cbd-ac32-e8d3814749b0@web.de","subject":"[PATCH v2 0/2] use __builtin_add_overflow() in st_add() with Clang","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-05-18T20:25:00Z","receivedAt":"2026-05-18T20:25:17Z","isPatch":true,"body":"Changes since v2:\n- Pass variable instead of st_add3() expression to ALLOC_GROW.\n- Add the helper st_add_overflow() that mimics __builtin_add_overflow()\n  for size_t to avoid duplicating most of the definition of st_add().\n\n  strbuf: use st_add3() in strbuf_grow()\n  use __builtin_add_overflow() in st_add() with Clang\n\n git-compat-util.h | 22 ++++++++++++++++++++--\n strbuf.c          |  6 ++----\n 2 files changed, 22 insertions(+), 6 deletions(-)\n\nInterdiff against v1:\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex aa088d04bb..5b1d15fe4f 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -614,25 +614,31 @@ static inline bool strip_suffix(const char *str, const char *suffix,\n int git_open_cloexec(const char *name, int flags);\n #define git_open(name) git_open_cloexec(name, O_RDONLY)\n \n-/* Help Clang; GCC generates the same code for both variants. */\n-#if defined(__clang__)\n-static inline size_t st_add(size_t a, size_t b)\n+\n+/*\n+ * Help Clang; GCC generates the same instructions for both variants on\n+ * x64 and aarch64.\n+ */\n+#ifdef __clang__\n+#define st_add_overflow __builtin_add_overflow\n+#else\n+static inline bool st_add_overflow(size_t a, size_t b, size_t *out)\n {\n-\tsize_t sum;\n-\tif (__builtin_add_overflow(a, b, &sum))\n-\t\tdie(\"size_t overflow: %\"PRIuMAX\" + %\"PRIuMAX,\n-\t\t    (uintmax_t)a, (uintmax_t)b);\n-\treturn sum;\n+\tif (unsigned_add_overflows(a, b))\n+\t\treturn true;\n+\t*out = a + b;\n+\treturn false;\n }\n-#else\n+#endif\n+\n static inline size_t st_add(size_t a, size_t b)\n {\n-\tif (unsigned_add_overflows(a, b))\n+\tsize_t result;\n+\tif (st_add_overflow(a, b, &result))\n \t\tdie(\"size_t overflow: %\"PRIuMAX\" + %\"PRIuMAX,\n \t\t    (uintmax_t)a, (uintmax_t)b);\n-\treturn a + b;\n+\treturn result;\n }\n-#endif\n #define st_add3(a,b,c)   st_add(st_add((a),(b)),(c))\n #define st_add4(a,b,c,d) st_add(st_add3((a),(b),(c)),(d))\n \ndiff --git a/strbuf.c b/strbuf.c\nindex bb04d3910e..8610965d53 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -106,9 +106,10 @@ void strbuf_attach(struct strbuf *sb, void *buf, size_t len, size_t alloc)\n void strbuf_grow(struct strbuf *sb, size_t extra)\n {\n \tint new_buf = !sb->alloc;\n+\tsize_t new_len = st_add3(sb->len, extra, 1);\n \tif (new_buf)\n \t\tsb->buf = NULL;\n-\tALLOC_GROW(sb->buf, st_add3(sb->len, extra, 1), sb->alloc);\n+\tALLOC_GROW(sb->buf, new_len, sb->alloc);\n \tif (new_buf)\n \t\tsb->buf[0] = '\\0';\n }\n-- \n2.54.0\n\n"},{"id":"543565","messageId":"20260518202502.25682-2-l.s.r@web.de","threadId":"65636","inReplyTo":"20260518202502.25682-1-l.s.r@web.de","subject":"[PATCH v2 1/2] strbuf: use st_add3() in strbuf_grow()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-05-18T20:25:01Z","receivedAt":"2026-05-18T20:25:18Z","isPatch":true,"body":"Simplify the code by calling st_add3() to do overflow checks instead of\nopen-coding it.  This changes the error message to include the offending\nsummands, which can be helpful when tracking down the cause.\n\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n strbuf.c | 6 ++----\n 1 file changed, 2 insertions(+), 4 deletions(-)\n\ndiff --git a/strbuf.c b/strbuf.c\nindex 3e04addc22..8610965d53 100644\n--- a/strbuf.c\n+++ b/strbuf.c\n@@ -106,12 +106,10 @@ void strbuf_attach(struct strbuf *sb, void *buf, size_t len, size_t alloc)\n void strbuf_grow(struct strbuf *sb, size_t extra)\n {\n \tint new_buf = !sb->alloc;\n-\tif (unsigned_add_overflows(extra, 1) ||\n-\t    unsigned_add_overflows(sb->len, extra + 1))\n-\t\tdie(\"you want to use way too much memory\");\n+\tsize_t new_len = st_add3(sb->len, extra, 1);\n \tif (new_buf)\n \t\tsb->buf = NULL;\n-\tALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);\n+\tALLOC_GROW(sb->buf, new_len, sb->alloc);\n \tif (new_buf)\n \t\tsb->buf[0] = '\\0';\n }\n-- \n2.54.0\n\n"},{"id":"543569","messageId":"20260519004401.GB1612961@coredump.intra.peff.net","threadId":"65636","inReplyTo":"20260518202502.25682-1-l.s.r@web.de","subject":"Re: [PATCH v2 0/2] use __builtin_add_overflow() in st_add() with Clang","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-19T00:44:01Z","receivedAt":"2026-05-19T00:44:03Z","isPatch":true,"body":"On Mon, May 18, 2026 at 10:25:00PM +0200, René Scharfe wrote:\n\n> Changes since v2:\n> - Pass variable instead of st_add3() expression to ALLOC_GROW.\n> - Add the helper st_add_overflow() that mimics __builtin_add_overflow()\n>   for size_t to avoid duplicating most of the definition of st_add().\n> \n>   strbuf: use st_add3() in strbuf_grow()\n>   use __builtin_add_overflow() in st_add() with Clang\n\nThanks, this seems reasonable to me. The type-generic version of\nbuiltin_add_overflow() is much harder, but doing it just for st_add() is\nenough for our purposes here.\n\n-Peff\n"},{"id":"543572","messageId":"xmqq4ik4b4ia.fsf@gitster.g","threadId":"65636","inReplyTo":"20260518202502.25682-1-l.s.r@web.de","subject":"Re: [PATCH v2 0/2] use __builtin_add_overflow() in st_add() with Clang","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-05-19T00:57:17Z","receivedAt":"2026-05-19T00:57:19Z","isPatch":true,"body":"René Scharfe <l.s.r@web.de> writes:\n\n> Changes since v2:\n> - Pass variable instead of st_add3() expression to ALLOC_GROW.\n> - Add the helper st_add_overflow() that mimics __builtin_add_overflow()\n>   for size_t to avoid duplicating most of the definition of st_add().\n>\n>   strbuf: use st_add3() in strbuf_grow()\n>   use __builtin_add_overflow() in st_add() with Clang\n\nNice simplification without becoming overly ambitious.  Very well\ndone.\n\nLet me mark it for 'next'.\n\nThanks.\n"}]}