[PATCH] Fix potential overflow in binary search mid calculation
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.
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.
Attachments:
0001-Fix-potential-overflow-in-binary-search-mid-calculat.patchapplication/octet-stream; name=0001-Fix-potential-overflow-in-binary-search-mid-calculat.patchDownload
From e8bc4f975ef181c63641d8e24392642dc080ecd8 Mon Sep 17 00:00:00 2001
From: Jianghua Yang <yjhjstz@gmail.com>
Date: Tue, 1 Apr 2025 04:26:05 +0800
Subject: [PATCH] Fix potential overflow in binary search mid calculation.
---
src/backend/utils/mmgr/dsa.c | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
diff --git a/src/backend/utils/mmgr/dsa.c b/src/backend/utils/mmgr/dsa.c
index 2d4639a6362..64e276bf465 100644
--- a/src/backend/utils/mmgr/dsa.c
+++ b/src/backend/utils/mmgr/dsa.c
@@ -783,7 +783,8 @@ dsa_allocate_extended(dsa_area *area, size_t size, int flags)
while (min < max)
{
- uint16 mid = (min + max) / 2;
+ /* Avoid overflow in the middle calculation */
+ uint16 mid = min + (max - min) / 2;
uint16 class_size = dsa_size_classes[mid];
if (class_size < size)
--
2.25.1
Jianghua Yang <yjhjstz@gmail.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 DescriptionIn 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.
PatchA patch implementing this fix is attached.
--
Thanks, Tender Wang