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

From: Jeff King <[email-masked]>
Date: Thu, 9 Oct 2025 01:52:37 -0400

On Thu, Sep 25, 2025 at 06:33:13AM -0700, Junio C Hamano wrote:

> Jeff King <[email-masked]> writes:
> 
> > 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.
> 
> We'd be protecting ourselves by noticing that n+k wraps around with
> st_add() and friends, and relying on malloc() and realloc() to
> notice and signal an error.  Use of size_t to count the number of
> things that are getting allocated is not making these any easier to
> do compared to the case you were counting in "int", no?  Either way
> we'd need to be careful.

Yes and no. I agree it is probably good to check for overflow as a
general principle, even if using size_t. But it is also easy to miss
such spots, and I do think using size_t (or something similarly large)
can provide some backup safety.

If you are getting values "foo" and "bar" from the user and computing a
length like "size_t len = foo * bar", then the size of the type will not
help you, and you need to do checked arithmetic. But I think those cases
are relatively easy to spot. The much more insidious ones are those that
append to a data structure one item at a time. With a type that is close
to the practical size of memory, you will fail to grow your data
structure before you hit the overflow. With a much smaller type like
int (on an LP64 platform), it is much easier for malicious input to
cause funky wrapping[1].

If your position is "it would not matter if we were properly checking
for overflow", then I agree. I just think it's hard to catch all of the
spots. But maybe I am being overly pessimistic. _Most_ of that should go
through ALLOC_GROW() or similar, so the checks could be centralized-ish[2].

-Peff

[1] We have had (and I'd wager probably still have) bugs where an
    attacker can wrap around to negative int. We get saved from a
    vulnerability here because the negative value is eventually cast to
    a gigantic size_t to allocate, which fails. In that sense I think
    "unsigned int" is the _most_ dangerous type to use.

[2] I think there are some practical implementation questions here, too.
    If we use st_add() etc in ALLOC_GROW(), then we may get caught by
    accidental type promotions, where those functions say "sure, it is
    OK to increase this len", but then return a size_t which is
    truncated when we try to stuff it back in an "int". So to make
    ALLOC_GROW() type independent, we probably need to do some more
    macro hackery with our checked arithmetic to make sure we are
    operating with the same size type that the caller is using. Not
    impossible, but something we'd have to be careful to get right.