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

["René Scharfe" <l.s.r@web.de>]

On 5/15/26 9:50 PM, Jeff King wrote:
> On Fri, May 15, 2026 at 03:08:18PM -0400, Jeff King wrote:
> 
>> On Fri, May 15, 2026 at 08:16:50PM +0200, René Scharfe wrote:
>>
>>> +		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_); \
>>>  		} \
>>
>> What happens if a caller passes in an argument that isn't a size_t?
>> We'll check for overflow in the size_t space, and then truncate it when
>> we assign to alloc, I think.
>>
>> I think we generally try to hold allocations in size_t these days, but
>> I'd be surprised if there weren't a few "int" holdouts. Grepping around,
>> alloc_node() seems to be an example.
>>
>> BTW, non-size_t arguments nullifies my earlier hand-waving around "nr +
>> 1 overflowing implies we've filled up the address space". But we are
>> still protected in the existing code by the:
>>
>>   if (alloc_nr(alloc) < (nr))
>> 	alloc = (nr);
>>
>> logic. But with your patch, that all happens in the size_t space, so I
>> think it would actually introduce possible array overflows when the
>> caller is using a smaller type.
> 
> Hmm, playing with it and looking a little closer, I think we don't end
> up overflowing the buffer because you use the size_t for
> REALLOC_ARRAY(). So the result is big, but then "alloc" is truncated.
> 
> And then on the next call, we think "oh no, the allocation is way too
> small" because we are using the truncated value. So we try to size up
> for every single allocation, even though it's actually big enough, and
> the program slows to a crawl. ;)
> 
> For reference, IU was using this hack to play around and demonstrate:
> 
> diff --git a/git.c b/git.c
> index 5a40eab8a2..638bbc69e4 100644
> --- a/git.c
> +++ b/git.c
> @@ -969,6 +969,19 @@ int cmd_main(int argc, const char **argv)
>  
>  	cmd = argv[0];
>  
> +	if (!strcmp(cmd, "foo")) {
> +		unsigned char *buf = NULL;
> +		unsigned nr = 0, alloc = 0;
> +		for (unsigned i = 0; i < UINT_MAX; i++) {
> +			ALLOC_GROW(buf, nr + 1, alloc);
> +			if (i % 313370 == 0)
> +				warning("at i=%u, alloc=%u, nr=%u", i, alloc, nr);
> +			buf[nr++] = i % 256;
> +		}
> +		printf("done, final nr=%u, alloc=%u\n", nr, alloc);
> +		return 0;
> +	}
> +
>  	/*
>  	 * We use PATH to find git commands, but we prepend some higher
>  	 * precedence paths: the "--exec-path" option, the GIT_EXEC_PATH
> 
> 
> The same problem exists in several places in actual code, but I'm not
> sure how practical it is to trigger. The alloc_node() is counting not
> just objects, but blocks of objects. So you'd need 2*31 * 1024 objects
> of one type, which is probably going to run afoul of other limitations.
> Other cases are similar; for example "yes | git fetch-pack --stdin foo"
> will grow an array indefinitely, but at one strbuf per line it starts
> swapping on my 64GB machine at only 350M entries.
> 
> 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.

Does the size_t arithmetic make matters worse?  The only change I can
see is that it interprets negative values as big unsigned ones and
then doesn't reallocate.  The outcome for positive values is the same,
overflow and all, no?

Here's a demo program exercising the arithmetic part of the macros:


#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 = true; \
		} \
	} 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 = true; \
		} \
	} while (0)

#define T signed char
#define MIN 0
#define MAX SCHAR_MAX

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;
			ALLOC_GROW1(allocated1, i, alloc1);
			ALLOC_GROW2(allocated2, i, alloc2);
			if (alloc1 != alloc2 || allocated1 != allocated2)
				printf("%zu %zu %d %zu %d %zu\n",
				       (size_t)i, (size_t)j,
				       allocated1, (size_t)alloc1,
				       allocated2, (size_t)alloc2);
			if (j == MAX)
				break;
		}
		if (i == MAX)
			break;
	}
	return 0;
}