Re: [PATCH] Fix potential overflow in binary search mid calculation

Jianghua Yang <yjhjstz(at)gmail(dot)com> 于2025年4月1日周二 04:29写道：

> Dear PostgreSQL Developers,
>
> I have identified a potential integer overflow issue in the binary search
> implementation within the DSA size class lookup code.
> Issue Description
>
> In the current implementation, the calculation of mid is performed as:
>
> uint16 mid = (max + min) / 2;
>
> Since both max and min are of type uint16, adding them together may exceed
> 65535, leading to an overflow and incorrect behavior in the binary
> search logic. This could result in incorrect indexing into the
> dsa_size_classes array.
>
The value of min is from the array dsa_size_class_map. The max value in
dsa_size_class_map[] is 25.
The value of max is the length of dsa_size_classes[], which is not too
large.
It will not happen that (max + min) exceeds 65535.

> Proposed Fix
>
> To prevent this overflow, we should use the alternative calculation method:
>
> uint16 mid = min + (max - min) / 2;
>
> This approach ensures that (max - min) does not exceed 65535, preventing
> the addition from overflowing while still correctly computing the middle
> index.
> Patch
>
> A patch implementing this fix is attached.
>

--
Thanks, Tender Wang