Re: [PATCH v2 2/4] string-list: replace negative index encoding with "exact_match" parameter

From: Jeff King <peff@peff.net>
Date: Sep 25, 2025, 02:50 UTC
Message-ID: <20250925025040.GB3202669@coredump.intra.peff.net>
In-Reply-To: <xmqqwm5om1gy.fsf@gitster.g>

On Wed, Sep 24, 2025 at 06:20:13AM -0700, Junio C Hamano wrote:

Show 11 quoted lines

> Jeff King <peff@peff.net> writes:
> 
> > I agree that size_t is much more than one needs for counting most
> > things. But the problem is that "int" is much too small, if you are
> > worried about malicious input causing integer overflows that could cause
> > memory access errors.
> 
> Well, a malicious input can cause overflow/wraparound size_t while
> parsing, so I do not think that is really an argument.
> 
> The code need to be protected against such overflows either way.

Yes, but it's much harder to wrap a size_t, especially if the code is allocating as it goes (e.g., a loop expanding an array). Because if expanding your allocation from "n" to "n+k" items will overflow, then that implies the current allocation is within "k" items of filling up the entire memory space.

In many cases "k" is 1, or a small-ish number (like the size of a struct). In cases where the size is computed purely from untrusted input, we do need overflow checks (and have added them over the years). We do those checks in the size_t space, since that's how we count allocated bytes, even if the thing we are storing is not 1 byte per item.

If a data structure uses a smaller type (like "int") to do book-keeping for its allocation, it risks the case where the smaller type wraps, but is still valid as a size_t. For a signed type and a small "k" this is often OK (if you wrap 2^31-1 around to -2^31, that ends up as an implausibly large size_t and the allocation will fail). But there are cases where you can wrap straight back around to "0", underallocate, and have an unexpectedly small allocation.

I don't _think_ we have any cases of those anymore, but it's hard to audit for. And IMHO easier to reason about if we use size_t for book-keeping.

But if we use size_t inside string_list, say, and you do this:

   for (int i = 0; i < list.nr; i++)
	printf("got: %s", list->items[i].string);

Now we have another problem. The string list can store more than 2^31 items (even if we do not expect it to). And at some point you start looking at list->items[-2147483648]. It's at least an out-of-bounds read, rather than a write, but it's still rather ugly (and a clever attacker can often stuff buffers to convince it to read whatever values they want).

If the iterator is a size_t, then overflow in that loop is impossible (because it implies we've allocated the entire address space). And ditto if it is a signed 64-bit value (which would implies we've allocated half of the entire address space).

So yes, I'd agree we need to protect against overflows, and that's what I'm advocating for. But I think consistently using integer types that are sized along with our memory is an important part of our strategy there.

-Peff