From: Phillip Wood <phillip.wood123@gmail.com>
Date: Wed, 21 May 2025 15:19:59 GMT
Subject: Re: [PATCH 1/4] midx repack: avoid integer overflow on 32 bit systems
Message-ID: <a87e6f8f-e6b3-4d91-8b0a-312962819eb4@gmail.com>
In-Reply-To: <aCzBvvZDS2OFJ30h@nand.local>

Hi Taylor

On 20/05/2025 18:54, Taylor Blau wrote:
> On Tue, May 20, 2025 at 04:04:24PM +0100, Phillip Wood wrote:
>> diff --git a/midx-write.c b/midx-write.c
>> index dd3b3070e55..c7cb2315431 100644
>> --- a/midx-write.c
>> +++ b/midx-write.c
>> @@ -1699,19 +1699,23 @@ static void fill_included_packs_batch(struct repository *r,
>>   	for (i = 0; total_size < batch_size && i < m->num_packs; i++) {
>>   		int pack_int_id = pack_info[i].pack_int_id;
>>   		struct packed_git *p = m->packs[pack_int_id];
>> -		size_t expected_size;
>> +		uint64_t expected_size;
>>
>>   		if (!want_included_pack(r, m, pack_kept_objects, pack_int_id))
>>   			continue;
>>
>> -		expected_size = st_mult(p->pack_size,
>> -					pack_info[i].referenced_objects);
>> +		expected_size = uint64_mult(p->pack_size,
>> +					    pack_info[i].referenced_objects);
> 
> Makes sense.
> 
>>   		expected_size /= p->num_objects;
>>
>>   		if (expected_size >= batch_size)
>>   			continue;
>>
>> -		total_size += expected_size;
>> +		if (unsigned_add_overflows (total_size, (size_t)expected_size))
>> +			total_size = SIZE_MAX;
>> +		else
>> +			total_size += expected_size;
>> +
> 
> But this part I am not totally following. Here we have 'total_size'
> declared as a size_t, and 'expected_size' as a uint64_t, and (on 32-bit
> systems) down-cast to a 32-bit unsigned value.
> 
> So if 'expected_size' is larger than SIZE_MAX, we should set
> 'total_size' to SIZE_MAX. But that may not happen, say if
> 'expected_size' is (2^32-1<<32). Should total_size also be declared as a
> uint64_t here?

By this point we know that expected_size < SIZE_MAX due to the test in 
the context lines above this change. batch_size is declared as size_t 
and to get here expected_size < batch_size. I'll add a sentence to the 
commit message to make that clearer.

> I wondered if it might be easier to count down from the given batch_size
> instead of adding up to it (requiring the second
> unsigned_add_overflows() check). I tried it out and got this instead:

I think you're right that we if we counted down we'd need one less 
comparison but I'm not sure if it is worth the churn. In the diff below

     factor = pack_info[i].referenced_objects / p->num_objects;

can only ever be zero or one as factor is declared as uint64_t so I 
don't think it works as-is. If you're happy with the shifted-integer 
approach in the next patch I'd rather just stick with that.

Thanks

Phillip

> --- 8< ---
> diff --git a/midx-write.c b/midx-write.c
> index 48a4dc5e94..f81dd9ff6d 100644
> --- a/midx-write.c
> +++ b/midx-write.c
> @@ -1671,7 +1671,7 @@ static void fill_included_packs_batch(struct repository *r,
>   				      size_t batch_size)
>   {
>   	uint32_t i;
> -	size_t total_size;
> +	uint64_t remaining = batch_size;
>   	struct repack_info *pack_info;
>   	int pack_kept_objects = 0;
> 
> @@ -1695,23 +1695,23 @@ static void fill_included_packs_batch(struct repository *r,
> 
>   	QSORT(pack_info, m->num_packs, compare_by_mtime);
> 
> -	total_size = 0;
> -	for (i = 0; total_size < batch_size && i < m->num_packs; i++) {
> +	for (i = 0; i < m->num_packs; i++) {
>   		int pack_int_id = pack_info[i].pack_int_id;
>   		struct packed_git *p = m->packs[pack_int_id];
> -		size_t expected_size;
> +		uint64_t expected_size, factor;
> 
>   		if (!want_included_pack(r, m, pack_kept_objects, pack_int_id))
>   			continue;
> 
> -		expected_size = st_mult(p->pack_size,
> -					pack_info[i].referenced_objects);
> -		expected_size /= p->num_objects;
> +		factor = pack_info[i].referenced_objects / p->num_objects;
> +		if (p->pack_size > UINT64_MAX / factor)
> +			die(...);
> 
> -		if (expected_size >= batch_size)
> -			continue;
> +		expected_size = p->pack_size * factor;
> +		if (expected_size > remaining)
> +			break;
> 
> -		total_size += expected_size;
> +		remaining -= expected_size;
>   		include_pack[pack_int_id] = 1;
>   	}
> --- >8 ---
> 
> That reduces the two overflow checks down to one, and avoids the need to
> introduce a uint64_t-specific variant of the st_add() function.
> 
> Thanks,
> Taylor