Allow the new element count passed to ALLOC_GROW to be a complex expression with side-effects by evaluating it only once, as a parameter to a new helper function.

Suggested-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: René Scharfe <l.s.r@web.de>
---
 git-compat-util.h | 20 ++++++++++++++------
 1 file changed, 14 insertions(+), 6 deletions(-)

On Fri, May 15, 2026 at 08:16:50PM +0200, René Scharfe wrote:

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.

-Peff

On Fri, May 15, 2026 at 03:08:18PM -0400, Jeff King wrote:

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:

On 5/15/26 9:50 PM, Jeff King wrote:

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;
}

On Sat, May 16, 2026 at 01:01:05AM +0200, René Scharfe wrote:

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:

Am 15.05.26 um 21:50 schrieb Jeff King:

Protect against double-evaluation of "alloc", too, using

	size_t *palloc = &(alloc);

and use *palloc in the two places, then all callers are forced to work with a size_t as third argument. Don't know what the damage would be, though.

-- Hannes

On 5/16/26 4:51 AM, Jeff King wrote:

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.

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;
}

On Sat, May 16, 2026 at 08:55:54AM +0200, Johannes Sixt wrote:

I think it would be nice if all ALLOC_GROW() callers used a size_t, and then we checked the size_t computation for overflow. But from a rough guess (taking your suggestion and trying to compile) we'd need to adjust ~200 callers.

And it's not just a straight conversion:

  1. Sometimes the ability to represent a negative value is important,
     and each site has to be audited. If we could agree on a "as big as
     size_t but signed" type, that might help.

  2. Changing the alloc variable type without the matching "nr" can
     actually make things worse. We tend to catch overflow-by-1 for
     signed types incidentally because it results in a stupidly large
     allocation request. But if made our allocations correct, then we
     might overflow on "nr" and start writing to some huge negative
     offset before the array.

So I think it would be a fair bit of work, though I would feel better about the resulting state.

-Peff