From: Jeff King <peff@peff.net>
Date: Wed, 24 Sep 2025 05:36:01 GMT
Subject: Re: [PATCH v2 2/4] string-list: replace negative index encoding with "exact_match" parameter
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:

> >> 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.

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