Subject: Small and unlikely overflow hazard in bms_next_member()

From: David Rowley <[email-masked]>
Date: Thu, 2 Apr 2026 17:09:00 +1300

I've been working on bms_left_shift_members() to bitshift members
either left or right in order to tidy up some existing code and
improve a future Bitmapset use case I'm currently working on.

When testing some ERROR code I added to ensure we don't get an
excessively large left shift value and end up with members higher than
INT32_MAX, I discovered that bms_next_member() can't handle that
value, as "prevbit++" will wrap to INT32_MIN and then we'll try to
access a negative array index, i.e. seg fault.

I appreciate that such a large member is quite unlikely, but if this
isn't fixed then I need to code my error checking code to disallow
members >= INT32_MAX rather than > INT32_MAX. I did have a comment
explaining why I was doing that, but fixing the bug saves the weird
special case and the comment.

Patched attached. I was thinking it might not be worthy of
backpatching, but I'll entertain alternative views on that.

David

---

From: Tom Lane <[email-masked]>
Date: Thu, 02 Apr 2026 00:22:48 -0400

> I appreciate that such a large member is quite unlikely,

I think it's impossible, and if it's not then this is not the
only place in bitmapset.c that could theoretically overflow.
As an example, bms_prev_member does

	Assert(prevbit <= a->nwords * BITS_PER_BITMAPWORD);

but if the bitmapset were large enough to accommodate INT_MAX
as a member then a->nwords * BITS_PER_BITMAPWORD must overflow.

I don't think we should add cycles here for this purpose.
If it makes you feel better, maybe add Asserts to
bms_make_singleton and bms_add_member to constrain the
maximum member value to somewhat less than INT_MAX?

			regards, tom lane

---

From: Chao Li <[email-masked]>
Date: Thu, 2 Apr 2026 14:38:46 +0800

> On Apr 2, 2026, at 12:09, David Rowley <[email-masked]> wrote:
> 
> <bms_next_member_fix.patch>

Both the return value of bms_next_member() and the parameter “prevbit" are defined as int, which seems to imply that a bitmap can hold at most INT32_MAX elements. So I wonder if a cleaner fix would be to just add a range guard, like this:

```
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 786f343b3c9..7f79f81f278 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -1294,7 +1294,7 @@ bms_next_member(const Bitmapset *a, int prevbit)

        Assert(bms_is_valid_set(a));

-       if (a == NULL)
+       if (a == NULL || prevbit == INT32_MAX)
                return -2;
        nwords = a->nwords;
        prevbit++;
```

Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/

---

From: jie wang <[email-masked]>
Date: Thu, 2 Apr 2026 15:54:18 +0800

Chao Li <[email-masked]> 于2026年4月2日周四 14:39写道：

> Both the return value of bms_next_member() and the parameter “prevbit" are
> defined as int, which seems to imply that a bitmap can hold at most
> INT32_MAX elements. So I wonder if a cleaner fix would be to just add a
> range guard, like this:
>
> ```
Hi,

The both solutions look good to me. I am slightly keen on Chao's version
that looks simpler to me.

Thanks!
wang jie

---

From: David Rowley <[email-masked]>
Date: Fri, 3 Apr 2026 11:12:15 +1300

> as a member then a->nwords * BITS_PER_BITMAPWORD must overflow.

I missed that one. That's annoying. Even "prevbit = a->nwords *
BITS_PER_BITMAPWORD - 1;" is undefined if it wraps due to the signed
maths.

> I don't think we should add cycles here for this purpose.

I'm not keen on slowing things down for this either. I did do some
experiments in [1] that sees fewer instructions from using 64-bit
maths. I might go off and see if there are any wins there that also
give us the INT_MAX fix. It's not great effort to reward ratio
though...

David

[1] https://godbolt.org/z/Eh1vzssq7

---

From: David Rowley <[email-masked]>
Date: Fri, 3 Apr 2026 11:20:50 +1300

> +       if (a == NULL || prevbit == INT32_MAX)

I don't think that's a nice way at all. Adding a special case plus
extra instructions, including a new jump instruction for the boolean
short-circuiting. More instruction decoding, more L1i space needed,
more branches to predict and more space in the branch predictor tables
to overwrite other useful branches. Adds run-time overhead.

I was aiming for low overhead and no special cases. 2a600a93c means we
don't care about the performance on 32-bit hardware anymore, so that
can't be used as a counterargument.

David

---

From: David Rowley <[email-masked]>
Date: Fri, 3 Apr 2026 15:08:58 +1300

> give us the INT_MAX fix. It's not great effort to reward ratio

The reduction in instructions with the patched version got me curious
to see if it would translate into a performance increase.  I tested on
an AMD Zen2 machine, and it's a decent amount faster than master. I
tested with gcc and clang.

I also scanned over the remaining parts of bitmapset.c and didn't find
anywhere else that has overflow risk aside from what you pointed out
in bms_prev_member().

The attached patch contains the benchmark function I added to the
test_bitmapset module. It should apply to master with a bit of noise.

CREATE EXTENSION test_bitmapset;
SELECT
    generate_series(1,3) AS run,
    bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 AS
bms_next_member_us,
    bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 AS
bms_prev_member_us;

master (gcc)

 run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
   1 |              26473 |              40404
   2 |              26218 |              40413
   3 |              26209 |              40387

patched (gcc)

 run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
   1 |              25409 |              29705
   2 |              24905 |              29693
   3 |              24870 |              29707

Times are in microseconds to do 1 million bms_*_member() loops over
the entire set.

I've also attached the full results I got. I've also included the
results from Chao's version, which does slow things down decently on
clang.

IMO, if we can make bitmapset.c work with INT_MAX members and get a
performance increase, then we should do it.

David

---

From: Chao Li <[email-masked]>
Date: Fri, 3 Apr 2026 11:24:08 +0800

> On Apr 3, 2026, at 10:08, David Rowley <[email-masked]> wrote:
> 
> <benchmark_results.txt><bms_fixes.patch>

I also did a load test with a standalone c program with 4 versions:

* The original bms_next_member (Original)
* The fast version from [1], that uses 64bit maths (Fast)
* The original version + INT32_MAX check + 64bit maths (Original2)
* I tried the other approach that pulls up the first iteration, so that removes "mask = (~(bitmapword) 0);” from the loop. (PullUp)

Note: all tests used -O2 to build the executable.

On my MacBook M4, the Fast version constantly won, and PullUp version performed badly.
```
% gcc --version
Apple clang version 17.0.0 (clang-1700.6.4.2)
Target: arm64-apple-darwin25.3.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin
```

A typical test run:
```
Benchmarking 100000 iterations...

Original:  0.48893 seconds
Fast:      0.46979 seconds
Original2:      0.47740 seconds
PullUp: 0.48029 seconds
``` 

On my Windows laptop, Intel(R) Core Ultra 5, with WSL based Ubuntu, Orignal2 won in the most runs, and the PullUp version was faster than Fast version.
```
chaol@lichao-highgo:~$ gcc --version                                                                            
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0                                                                      
Copyright (C) 2023 Free Software Foundation, Inc.                                                              
This is free software; see the source for copying conditions.  There is NO                                      
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
```

A typical test run:
```
Original:  0.99849 seconds                                                                                      
Fast:      0.74722 seconds                                                                                      
Original2:      0.59407 seconds                                                                                
PullUp: 0.62746 seconds     
```

Then I also tried to run on Windows directly. Here, PullUp version performed the best.
```
$ gcc --version
gcc.exe (Rev13, Built by MSYS2 project) 15.2.0
Copyright (C) 2025 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
```

A typical test run:
```
Original:  0.32931 seconds
Fast:      0.32740 seconds
Original2:      0.32378 seconds
PullUp: 0.30795 seconds
```

I’m curious that, when something performs differently across platforms, which platform should take priority?

Please see the attached test program. It’s possible I did something wrong.

---

From: David Rowley <[email-masked]>
Date: Sat, 4 Apr 2026 00:42:17 +1300

> I also did a load test with a standalone c program with 4 versions:

I think you'd be better off picking a more realistic Bitmapset. The
code is doing:

    int words_to_alloc = 20000; // Large set to bypass CPU cache slightly
    Bitmapset *bms = malloc(sizeof(Bitmapset) + words_to_alloc *
sizeof(bitmapword));
    bms->nwords = words_to_alloc;
    memset(bms->words, 0, words_to_alloc * sizeof(bitmapword));

    /* Set a bit far into the set to force a long scan */
    int target_bit = (words_to_alloc - 1) * 64 + 10;
    bms->words[words_to_alloc - 1] |= (1ULL << 10);

A set with 20k words! Then you're doing:

    for (int i = 0; i < iterations; i++) sink = bms_next_member(bms, 0);

So you're not looping correctly over the set, as looping over a set
with 1 member requires 2 calls to the function.

I'd say this unrealistically favours the unrolled loop version, as
most of the effort is in the loop looping over empty words and you can
do that without the extra bit-wise AND that the other versions have.
That version also seems to apply both the 64-bit fix and the INT_MAX
fix. Why both?  Because you're only calling the function once per
iteration, it also means your || INT_MAX is only executed once, rather
than n_members + 1 as it would normally be executed. That'll make your
version seem better than it is.

I fixed all that and changed the Bitmapset to something more realistic
with how it's more likely to be seen in PostgreSQL and ran the
benchmark with a proper bms_next_member loop. File attached and
results below:

Zen2 Linux

$ gcc test_bms_next.c -O2 -o test_bms_next && ./test_bms_next
Benchmarking 100000000 iterations...

Original:  0.62113 seconds
David's:          0.70257 seconds
Chao's version:   1.70691 seconds
Unrolled loop: 1.56239 seconds
2800000000

$ clang test_bms_next.c -O2 -o test_bms_next && ./test_bms_next
Benchmarking 100000000 iterations...

Original:  1.11263 seconds
David's:          0.87399 seconds
Chao's version:   0.52962 seconds
Unrolled loop: 1.07799 seconds
2800000000

Apple M2:

Benchmarking 100000000 iterations...

Original:  0.64023 seconds
David's:          0.41087 seconds
Chao's version:   1.21113 seconds
Unrolled loop: 0.55924 seconds
2800000000

> I’m curious that, when something performs differently across platforms, which platform should take priority?

I don't think it matters too much for this case. If we were actually
working on a function that was a bottleneck, then it would be worth
looking deeper and seeing if the compilers are producing suboptimal
code and then try to coax them into making better code. As a last
resort, have two versions and some preprocessor to decide which one.
However, this just isn't performance-critical enough to warrant such
an effort. I think we're already going far too far with this. I just
want to fix the bug. If performance increases in some way as a result
of that, then good.

If I sum up the times from each version of the above results, I get:

Original: 2.37399
David's: 1.98743
Chao's: 3.44766
Unrolled: 3.19962

I'm happy to go with the fastest one. I expect the one with the fewest
instructions is likely more important when running it in the planner,
as that's less to decode. I didn't look, but I expect your loop
unrolled version and your || INT_MAX version to have more
instructions.

David

---

From: Chao Li <[email-masked]>
Date: Fri, 3 Apr 2026 21:28:03 +0800

> On Apr 3, 2026, at 19:42, David Rowley <[email-masked]> wrote:
> 
> <test_bms_next2.c>

In test_bms_next2.c, you set words_to_alloc = 1, which disables the optimization in the unrolled version. If I change words_to_alloc = 2, then on my MacBook M4, the unrolled version seems to win:
```
chaol@ChaodeMacBook-Air test % ./test_bms_next2
Benchmarking 100000000 iterations...

Original:  0.61559 seconds
David's:	  0.61651 seconds
Chao's version:	  1.06033 seconds
Unrolled loop: 0.60561 seconds
2800000000
```

(I also checked on Godbolt, from the instruction-count perspective, the unrolled version actually looks the worst.)

I guess one-word Bitmapset are probably the most common case in practice. So overall, I agree that your version is the best choice. Please go ahead with it as we have already gained both a bug fix and a performance improvement. If we really want to study the performance more deeply, I think that would be a separate topic.

It was fun working on this patch, and thank you for your patience.

Best regards,

---

From: David Rowley <[email-masked]>
Date: Sat, 4 Apr 2026 16:30:32 +1300

> Unrolled loop: 0.60561 seconds

Doing the same locally, here's what I get on my Zen2 machine:

drowley@amd3990x:~$ gcc test_bms_next.c -O2 -o test_bms_next && ./test_bms_next
Benchmarking 100000000 iterations...

Original:  1.21125 seconds
David's:          1.11997 seconds
Chao's version:   1.72662 seconds
Unrolled loop: 1.63090 seconds
2800000000
drowley@amd3990x:~$ clang test_bms_next.c -O2 -o test_bms_next &&
./test_bms_next
Benchmarking 100000000 iterations...

Original:  1.10780 seconds
David's:          1.05968 seconds
Chao's version:   1.87123 seconds
Unrolled loop: 1.11002 seconds
2800000000

> I guess one-word Bitmapset are probably the most common case in practice. So overall, I agree that your version is the best choice. Please go ahead with it as we have already gained both a bug fix…

Yeah, but it's better to find bottlenecks and focus there than to
optimise blindly without knowing if it'll make any actual difference.
It's still important to test for regressions when modifying code and
try to avoid them, as it's sometimes not obvious if the code being
modified is critical for performance.

I also don't think we should be doing anything to optimise for
multi-word sets at the expense of slowing down single-word sets. Not
that it's very representative of the real world, but I added some
telemetry to bitmapset.c and I see 43 multi-word sets being created
and 1.45 million single-word sets created during make check, or 1 in
33785, if you prefer.

diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 786f343b3c9..21b5053e9a2 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -219,6 +219,10 @@ bms_make_singleton(int x)
        int                     wordnum,
                                bitnum;

+       if (x >= 64)
+               elog(NOTICE, "multi-word set bms_make_singleton");
+       else
+               elog(NOTICE, "single-word set bms_make_singleton");
        if (x < 0)
                elog(ERROR, "negative bitmapset member not allowed");
        wordnum = WORDNUM(x);
@@ -811,6 +815,9 @@ bms_add_member(Bitmapset *a, int x)
        wordnum = WORDNUM(x);
        bitnum = BITNUM(x);

+       if (x >= 64 && a->nwords == 1)
+               elog(NOTICE, "multi-set bms_add_member");
+
        /* enlarge the set if necessary */
        if (wordnum >= a->nwords)
        {

Not quite perfect as a set made first as a single word set that later
becomes a multi-word set will be double counted. The number of
operations on the sets is likely more important anyway, not the number
of sets being created. The point is, multi-word sets are rare for most
workloads.

David

---

From: Chao Li <[email-masked]>
Date: Mon, 6 Apr 2026 10:00:38 +0800

> On Apr 4, 2026, at 11:30, David Rowley <[email-masked]> wrote:
> 

I just tried my Windows laptop with both MSYS2 and WSL Ubuntu, and on both of them the original version and David’s version consistently performed better than the other versions.

I have a new finding from Godbolt: adding likely(w != 0) seems to reduce the instruction count by one. bms_next_member_fast has 26 instructions, while after adding "likely", bms_next_member_fast2 has 25. It seems that this may avoid one jump and perhaps be slightly better, but I’m not sure. I’m really not an expert in assembly.

Then I tested. “likely” doesn’t seem to help on Mac:
```
chaol@ChaodeMacBook-Air test % ./test_bms_next2
Benchmarking 100000000 iterations...

Original:  0.54994 seconds
David's:	  0.78218 seconds
David's likely:	  0.78990 seconds
Chao's version:	  1.11530 seconds
Unrolled loop: 0.47660 seconds
3500000000
```

But it helps slightly on Windows:
```
$ ./test_bms_next2
Benchmarking 100000000 iterations...

Original:  1.45312 seconds
David's:          1.48438 seconds
David's likely:   1.40625 seconds
Chao's version:   3.12500 seconds
Unrolled loop: 2.95312 seconds
-794967296
```

I’m not suggesting adding likely() to your version, I’m just sharing the information for your reference and leaving the decision to you.

> multi-word sets at the expense of slowing down single-word sets.

Fully agreed.

> Not

What tests did you run after adding the logs to collect the data? This is a method I might borrow in the future for similar investigations.

Best regards,

---

From: David Rowley <[email-masked]>
Date: Mon, 13 Apr 2026 00:33:04 +1200

> What tests did you run after adding the logs to collect the data? This is a method I might borrow in the future for similar investigations.

"make check" then grep regression.diffs for the NOTICE message and
pipe to "wc -l"

---

From: David Rowley <[email-masked]>
Date: Mon, 13 Apr 2026 01:17:02 +1200

> performance increase, then we should do it.

Re-thinking this after a week's holiday, it seems fine to use an
unsigned 32-bit int rather than a 64-bit int to fix this bug. I'd
previously been uncertain if there were any guarantees in C to what
(unsigned int) -1 would return, but going by [1] at 6.3.1.3, it says:

"Otherwise, if the new type is unsigned, the value is converted by
repeatedly adding or subtracting one more than the maximum value that
can be represented in the new type until the value is in the range of
the new type."

So, it seems even on one's complement that -1 as an unsigned int will
be UINT_MAX. When we add 1 to UINT_MAX, we're guaranteed to get 0, as
it's unsigned maths and overflows are going to result in a value
modulus the max value for the type.

That leads me to the attached v2 patch. Compiler Explorer link showing
the assembly at [2].

Testing the performance, it's better than master, so I got rid of the
size_t wordnum stuff. We're post-freeze now, so fiddling with other
optimisations seems a bit off the table as there appears to be no
performance regression to compensate for now, per:

drowley@amd3990x:~$ gcc test_bms_next3.c -O2 -o test_bms_next3 &&
./test_bms_next3
Benchmarking 100000000 bms_next_member iterations...
master: 1.18330 seconds
Patched: 1.05493 seconds

Benchmarking 100000000 bms_prev_member iterations...
master: 2.94522 seconds
Patched: 1.86130 seconds

drowley@amd3990x:~$ clang test_bms_next3.c -O2 -o test_bms_next3 &&
./test_bms_next3
Benchmarking 100000000 bms_next_member iterations...
master: 1.07860 seconds
Patched: 1.07896 seconds

Benchmarking 100000000 bms_prev_member iterations...
master: 2.76550 seconds
Patched: 2.12369 seconds

David

[1] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf
[2] https://godbolt.org/z/xW96rxd3P

---

From: David Rowley <[email-masked]>
Date: Mon, 13 Apr 2026 11:41:40 +1200

> modulus the max value for the type.

I've pushed that version. No backpatch.

David

---

From: Chao Li <[email-masked]>
Date: Mon, 13 Apr 2026 08:23:26 +0800

> On Apr 12, 2026, at 21:17, David Rowley <[email-masked]> wrote:
> 
> <test_bms_next3.c><v2-0001-Fix-unlikely-overflow-bug-in-bms_next_member.patch>

I just tried test_bms_next3 on my MacBook, looks like patched bms_prev_member is much faster there. I ran about 10 times, the results were consistent.
```
chaol@ChaodeMacBook-Air test % gcc test_bms_next3.c -O2 -o test_bms_next3
test_bms_next3.c:281:18: warning: format specifies type 'long' but the argument has type 'int64' (aka 'long long') [-Wformat]
  281 |         printf("%ld\n", count);
      |                 ~~~     ^~~~~
      |                 %lld
1 warning generated.
chaol@ChaodeMacBook-Air test % ./test_bms_next3
Benchmarking 100000000 bms_next_member iterations...
master: 0.49287 seconds
Patched: 0.47315 seconds

master: 1.04644 seconds
Patched: 0.58053 seconds
2800000000
```

Best regards,

---

From: David Rowley <[email-masked]>
Date: Mon, 13 Apr 2026 14:43:01 +1200

> I just tried test_bms_next3 on my MacBook, looks like patched bms_prev_member is much faster there. I ran about 10 times, the results were consistent.

Thanks. I saw similar results.

David