Re: [PATCH] [Outreachy PATCH] diff-delta: use safe integer arithmetic

From: Junio C Hamano <gitster@pobox.com>
Date: Oct 23, 2026, 18:45 UTC
Message-ID: <xmqqcxt05k8r.fsf@gitster.g>
In-Reply-To: <CABh_KWgBzCXCSn4FUTSg+rXYj9vm6+AVZnDn3iR_4UJCsB8tjw@mail.gmail.com>

Srujith Poojary <poojarysrujith@gmail.com> writes:

Show 35 quoted lines

> On Fri, Oct 23, 2026 at 9:00 PM Junio C Hamano <gitster@pobox.com> wrote:
>>
>> Srujith Poojary <poojarysrujith@gmail.com> writes:
>>
>> > Thank you for clarifying this. You are right—st_add() and st_mult()
>> > call die() on overflow rather than returning NULL.
>> > I will update the commit message to accurately reflect this behavior
>> > and submit v2.
>>
>> Please don't, before making sure if it can overflow.  With the
>> number of entries capped like this:
>>
>>         if (bufsize >= 0xffffffffUL)
>>                 entries = 0xfffffffeU / RABIN_WINDOW;
>>
>> and then computed
>>
>>         hsize = entries / 4;
>>         for (i = 4; (1u << i) < hsize; i++);
>>         hsize = 1 << i;
>>         /* allocate lookup index */
>>         memsize = sizeof(*hash) * hsize +
>>                   sizeof(*entry) * entries;
>>
>> it may not be possible to overflow size_t even on 32-bit platforms.
>> I didn't have time to do math yet myself, though.
>>
>
> Hi Phillip and Junio,
>
> Thank you for the detailed feedback.
>
> I checked the bounds: since entries is capped by (0xffffffu /
> RABIN_WINDOW), hsize remains small, making a size_t overflow
> impossible even on 32-bit systems.

Hmph, I actually came to a different conclusion, but my math is probably weaker X-<.

entries is capped by 1^32 / 16 = 1^28, and hsize is capped at 1^26.

sizeof(*hash) is 4 bytes on 32-bit platforms.

struct index_entry has a pointer and an unsigned, i.e. 8 bytes. struct unpacked_index_entry has the above index_entry plus a pointer, i.e. 8+4=12 bytes or 16 bytes (with 4-byte padding). That is the sizeof(*entry).

If "struct unpacked_index_entry" has 4-byte padding to align at 8-byte boundary, then memsize = 4 * 1^26 + 16 * 1^28 can overflow size_t's range that is 1^32. If the struct does not have extra padding, this would fit below 1^32. We have no guarantee what the compiler would do, so we need to assume the worst.

Of course it is entirely a different matter if malloc() would allow such a large allocation even if math does not overflow, but the focus of this patch is to make sure memsize is computed as a large allocation in such a case without wrapping around.