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

From: Jeff King <peff@peff.net>
Date: Sep 24, 2025, 05:36 UTC
Message-ID: <20250924053601.GC1173044@coredump.intra.peff.net>
In-Reply-To: <xmqq348dovi3.fsf@gitster.g>

On Tue, Sep 23, 2025 at 11:48:36AM -0700, Junio C Hamano wrote:

Show 17 quoted lines

> >> 1. It prevents us from using the full range of size_t, which is
> >>    necessary for large string list.
> 
> It is a disease to think that countable things must be counted in
> size_t and it needs to be somehow cured.
> 
> It is a type to count the size of memory allocations, nothing more.
> If you are holding 1000-bytes per the stuff you are counting, you
> would not need the full range of size_t --- you'll ran out your
> memory way before you fill size_t with the things you are counting.
> 
> When there is no external constraints (like you need to specify
> exact size to describe a file format to be interoperable), the most
> appropriate type to count things in is a platform natural "int".
> You wouldn't be handling billions of strings in string-list anyway
> (and that is smaller than half of 32-bit size_t; 64-bit size_t is
> much larger).

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.

A nice property of counting everything as size_t is that if we are storing even a single byte per item, we will fail to allocate before hitting an integer overflow. So no, we do not expect to store billions of strings. But it is not that hard to convince Git to allocate billions of items in a list on a 64-bit system with 32-bit ints. And it is nice to know that iterating over them or trying to extend the array will never hit an integer overflow bug.

I'd say the "right" size for preventing overflows probably only needs to be 58-60 bits or so, since usually we are storing more than one byte (plus overhead). But 64-bit is the natural machine word size that matches what we want. However, we should _not_ be worried about losing one bit to making it signed, especially if that makes it less error-prone to convert instances of "int" to use "size_t". I would be surprised if an attacker could convince a program to truly use up half of its address space.

Show 6 quoted lines

> >> 2. Using int for indices while other parts of the codebase use size_t
> >>    creates signed comparison warnings when these values are compared.
> 
> The other thing may be (mis)using size_t when it should not be.  If
> they were also using "int" that would also squelch the warnings from
> "-Wsign-compare".

So I really care only about truncation and overflow above. Sign issues can cause bugs, of course, but the real issue is the size mismatch between "int" and "size_t". And while -Wsign-compare is sometimes an easy way to find those mismatches (because of the sign mismatch between them), it may bring more hassle than it's worth.

I didn't participate in the count_t discussion a month or two ago. But I think it could make sense to have a count_t that is really just a larger "int", but is still signed.

-Peff