git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH] evaluate the second argument of ALLOC_GROW only once

From
René Scharfe <l.s.r@web.de>
Date
May 16, 2026, 11:10 UTC
Message-ID
<23be5317-4f28-4871-8aab-5281f4da5f0e@web.de>
In-Reply-To
<20260516025119.GA832077@coredump.intra.peff.net>
On 5/16/26 4:51 AM, Jeff King wrote:
Show 61 quoted lines
> On Sat, May 16, 2026 at 01:01:05AM +0200, René Scharfe wrote:
> 
>>> I think as long as the behavior remains "slow, but we do not overflow
>>> any buffers" when you reach these limits, that's OK. Nobody is going to
>>> do it in practice, and we just want to make sure that malicious inputs
>>> cannot get out-of-bounds writes. It might be worth adding a comment,
>>> though, to make sure nobody ever swaps "alloc_grow_new_alloc_" for
>>> "alloc" in that macro.
>> There is no overflow check in either version (yet), so neither is safe
>> to operate close to the boundary.  Close meaning the intermediate term
>> (alloc + 16) * 3 being bigger than the maximum value.
> 
> Yes, but for some definition of safe. Both before and after your patch,
> as we get close to the boundary the allocation will grow slower than it
> should, but we'll never write out of bounds. The behavior for the "git
> foo" I showed earlier is slightly different:
> 
>   - before your patch, ~2GB we stop doubling and instead start growing
>     the array by one at each ALLOC_GROW() call. This is because
>     alloc_nr() overflows to a small value, but the:
> 
>       if (alloc_nr(alloc) < (nr))
>               alloc = (nr);
> 
>     check kicks in.
> 
>   - after your patch we grow to ~4GB, and then things get super slow.
>     This is because we correctly compute the new allocation as a size_t,
>     but then truncate it while assigning to alloc. So on the next
>     ALLOC_GROW() call, we'll think the buffer is way too small and try
>     to realloc again. I don't know why this is so much slower than the
>     grow-by-one above, but it is.
> 
> Neither is really correct, but both are in the realm of OK: stupidly
> large input doesn't perform well, but there's no buffer overflow
> vulnerability.
> 
> What I was worried about is what happens if you tweak your patch like
> this:
> 
> diff --git a/git-compat-util.h b/git-compat-util.h
> index 2bc1f43f48..0730dd24ad 100644
> --- a/git-compat-util.h
> +++ b/git-compat-util.h
> @@ -870,7 +870,7 @@ static inline bool st_alloc_nr(size_t nr, size_t alloc, size_t *outp)
>  		size_t alloc_grow_new_alloc_; \
>  		if (st_alloc_nr((nr), (alloc), &alloc_grow_new_alloc_)) { \
>  			alloc = alloc_grow_new_alloc_; \
> -			REALLOC_ARRAY(x, alloc_grow_new_alloc_); \
> +			REALLOC_ARRAY(x, alloc); \
>  		} \
>  	} while (0)
>  
> 
> In that case we really do end up with too-small allocations and
> out-of-bounds writes.
> 
> Maybe you saw that coming and that's why you wrote it as you did. But it
> is definitely subtle enough that I think it would merit a big warning
> comment that "alloc" and "alloc_grow_new_alloc_" are not necessarily the
> same type, and hence not necessarily the same value.

It was the economic thing to do: Fetching the value of user-supplied alloc variable makes no sense when we have our calculated size_t value at hand.

Show 42 quoted lines
>> Here's a demo program exercising the arithmetic part of the macros:
> 
> I think the difference isn't in the arithmetic values that come out, but
> in what is fed to realloc() itself. And in your harness, realloc is just
> "x = true". If you actually store the value that would be passed to
> realloc() like this:
> 
> diff --git a/foo.c.orig b/foo.c
> index 2fbce8c..7498f36 100644
> --- a/foo.c.orig
> +++ b/foo.c
> @@ -11,7 +11,7 @@
>  				alloc = (nr); \
>  			else \
>  				alloc = alloc_nr(alloc); \
> -			x = true; \
> +			x = alloc; \
>  		} \
>  	} while (0)
>  
> @@ -31,7 +31,7 @@ static inline bool st_alloc_nr(size_t nr, size_t alloc, size_t *outp)
>  		size_t alloc_grow_new_alloc_; \
>  		if (st_alloc_nr((nr), (alloc), &alloc_grow_new_alloc_)) { \
>  			alloc = alloc_grow_new_alloc_; \
> -			x = true; \
> +			x = alloc_grow_new_alloc_; \
>  		} \
>  	} while (0)
>  
> @@ -44,7 +44,7 @@ int main(int argc, char **argv)
>  	for (T i = 0;; i++) {
>  		for (T j = MIN;; j++) {
>  			T alloc1 = j, alloc2 = j;
> -			bool allocated1 = false, allocated2 = false;
> +			size_t allocated1 = 0, allocated2 = 0;
>  			ALLOC_GROW1(allocated1, i, alloc1);
>  			ALLOC_GROW2(allocated2, i, alloc2);
>  			if (alloc1 != alloc2 || allocated1 != allocated2)
> 
> then you see the differences. For negative values, yeah, you end up with
> big size_t values. But for an unsigned type you get different small
> allocations.

Good point. For unsigned char I get differences starting at 156 elements, here just the first few:

unsigned char nr=156 0 (155 -> 0) vs 256 (155 -> 0) unsigned char nr=157 0 (155 -> 0) vs 256 (155 -> 0) unsigned char nr=157 2 (156 -> 2) vs 258 (156 -> 2)

So the current code cuts the allocation size to 0 if you have an array of 155 and ask for more entries. That would cause a buffer overrun. With the patch ALLOC_GROW actually grows the buffer.

For signed char I see a different failure mode:

signed char nr=71 18446744073709551489 (70 -> -127) vs 129 (70 -> -127) signed char nr=72 18446744073709551489 (70 -> -127) vs 129 (70 -> -127) signed char nr=72 18446744073709551490 (71 -> -126) vs 130 (71 -> -126)

The current code tries to allocate (something close to) infinity, which would terminate the program. With the patch ALLOC_GROW actually grows the buffer.

I don't see this for int and unsigned, though. Weird C integer promotion rules hit us here, I guess. Just this, as you mentioned:

ALLOC_GROW1 unsigned nr=1787844770 1787844770 (1787844769 -> 1787844770) step too small, abort ALLOC_GROW1 int nr=1787844770 1787844770 (1787844769 -> 1787844770) step too small, abort

The demo code is now big and hairy enough to need its own tests, though. *snicker*

René

#include <limits.h> #include <stdbool.h> #include <stdio.h>

#define alloc_nr(x) (((x)+16)*3/2)
#define ALLOC_GROW1(x, nr, alloc) \
	do { \
		if ((nr) > alloc) { \
			if (alloc_nr(alloc) < (nr)) \
				alloc = (nr); \
			else \
				alloc = alloc_nr(alloc); \
			x = alloc; \
		} \
	} while (0)
static inline bool st_alloc_nr(size_t nr, size_t alloc, size_t *outp)
{
	if (nr > alloc) {
		size_t out = alloc_nr(alloc);
		*outp = out < nr ? nr : out;
		return true;
	}
	return false;
}
#define ALLOC_GROW2(x, nr, alloc) \
	do { \
		size_t alloc_grow_new_alloc_; \
		if (st_alloc_nr((nr), (alloc), &alloc_grow_new_alloc_)) { \
			alloc = alloc_grow_new_alloc_; \
			x = alloc_grow_new_alloc_; \
		} \
	} while (0)
#define COMPARE(T, P, nr, alloc1, alloc_sz1, alloc2, alloc_sz2) do { \
	T orig_alloc1 = alloc1, orig_alloc2 = alloc2; \
	ALLOC_GROW1(alloc_sz1, nr, alloc1); \
	ALLOC_GROW2(alloc_sz2, nr, alloc2); \
	if (alloc_sz1 != alloc_sz2) \
		printf(#T" nr="P" %zu ("P" -> "P") vs %zu ("P" -> "P")\n", \
		       nr,  \
		       alloc_sz1, orig_alloc1, alloc1, \
		       alloc_sz2, orig_alloc2, alloc2); \
} while (0)
#define COMPARE_ALL(T, MIN, MAX, P) do { \
	for (T nr = 0;; nr++) { \
		for (T alloc = MIN;; alloc++) { \
			T alloc1 = alloc, alloc2 = alloc; \
			size_t alloc_sz1 = alloc1, alloc_sz2 = alloc2; \
			COMPARE(T, P, nr, alloc1, alloc_sz1, alloc2, alloc_sz2); \
			if (alloc == MAX) \
				break; \
		} \
		if (nr == MAX) \
			break; \
	} \
} while (0)
#define COMPARE_GROWTH(T, MAX, P) do { \
	T alloc1 = 0, alloc2 = 0; \
	size_t alloc_sz1 = 0, alloc_sz2 = 0; \
	for (T nr = 0;; nr++) { \
		COMPARE(T, P, nr, alloc1, alloc_sz1, alloc2, alloc_sz2); \
		if (nr == MAX) \
			break; \
	} \
} while (0)
#define CHECK_GROWTH_ONE(T, MAX, P, ALLOC_GROW) do { \
	T alloc = 0; \
	size_t alloc_sz = 0; \
	for (T nr = 0;; nr++) { \
		T orig_alloc = alloc; \
		size_t orig_alloc_sz = alloc_sz; \
		ALLOC_GROW(alloc_sz, nr, alloc); \
		if (alloc_sz < (size_t)nr) \
			printf(#ALLOC_GROW" "#T" nr="P" %zu ("P" -> "P")" \
			       " too small\n", \
			       nr, alloc_sz, orig_alloc, alloc); \
		if (alloc_sz > alloc_nr((size_t)nr)) \
			printf(#ALLOC_GROW" "#T" nr="P" %zu ("P" -> "P")" \
			       " too big\n", \
			       nr, alloc_sz, orig_alloc, alloc); \
		if (alloc_sz > orig_alloc_sz && \
		    alloc_sz - alloc_sz / 3 < orig_alloc_sz) { \
			printf(#ALLOC_GROW" "#T" nr="P" %zu ("P" -> "P")" \
			       " step too small, abort\n", \
			       nr, alloc_sz, orig_alloc, alloc); \
			break; \
		} \
		if (nr == MAX) \
			break; \
	} \
} while (0)
#define CHECK_GROWTH(T, MAX, P) do { \
	CHECK_GROWTH_ONE(T, MAX, P, ALLOC_GROW1); \
	CHECK_GROWTH_ONE(T, MAX, P, ALLOC_GROW2); \
} while (0)
int main(int argc, char **argv)
{
	COMPARE_ALL(unsigned char, 0, UCHAR_MAX, "%hhu");
	COMPARE_ALL(signed char, 0, SCHAR_MAX, "%hhd");
	COMPARE_GROWTH(short, SHRT_MAX, "%hd");
	CHECK_GROWTH(short, SHRT_MAX, "%hd");
	CHECK_GROWTH(unsigned short, USHRT_MAX, "%hu");
	CHECK_GROWTH(unsigned, UINT_MAX, "%u");
	CHECK_GROWTH(int, INT_MAX, "%d");
	return 0;
}
Previous: Jeff KingNext: Johannes Sixt
Message 6 of 8 in “evaluate the second argument of ALLOC_GROW only once”
  1. evaluate the second argument of ALLOC_GROW only onceRené Scharfe, May 15, 2026
  2. Jeff KingMay 15, 2026
  3. Jeff KingMay 15, 2026
  4. René ScharfeMay 15, 2026
  5. Jeff KingMay 16, 2026
  6. René ScharfeMay 16, 2026
  7. Johannes SixtMay 16, 2026
  8. Jeff KingMay 19, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.