Fw:Re: Fw: gbt_var_consistent in contrib/btree_gist/btree_utils_var.c has internal-node type confusion on the <> strategy, bypassing exclusion constraints

Hi,

On Tue, 16 Jun 2026 at 16:59, 王跃林 <violin0613@tju.edu.cn> wrote:

0800, 王跃林 wrote:

gbt_var_node_truncate (btree_utils_var.c:214) truncates internal node keys to a common-prefix length. The resulting bytea can have VARSIZE anywhere from 4 upward. When the truncated VARSIZE is below 8 and that key reaches bit_cmp via the buggy BtreeGistNotEqual branch, bytelen becomes negative. Passed to memcmp as size_t, that is several GB. ASan catches it as negative-size-param. A production build without ASan will eventually SEGV when the read crosses an unmapped page.

Thanks for the report!

In gbt_var_consistent() (contrib/btree_gist/btree_utils_var.c), the <>
(BtreeGistNotEqual) branch is the only strategy that does not distinguish
leaf from internal pages. It applies the type's equality function directly
to the stored key on both bounds:

retval = !(tinfo->f_eq(query, key->lower, ...) &&
tinfo->f_eq(query, key->upper, ...));

That seems to be the problem: on internal pages those keys are
truncated (and for bit/varbit the length header is gone too), so
they aren't really valid values to hand to the type's equality
function. Hence the negative length reaching memcmp().

Would it make sense to just have <> follow the same leaf-vs-internal
pattern as the other strategies; negate equality on a leaf, and
otherwise recurse? An internal page can always contain some
non-equal value, so I don't think we lose anything by descending.
I put together a small patch along those lines (plus a bit(8) test
that goes through internal pages); it's attached if it's useful.
(PS. The test exercises the path but passes on a plain build; the OOB
read shows up under ASan (negative-size-param).)

I didn't touch the fixed-size path in btree_utils_num.c, since its
internal keys look like they're exact lower/upper values, but
please correct me if I'm missing something there.

Regards,
Ayush

The analysis and fix look correct. The BtreeGistNotEqual branch is the only strategy that bypasses the is_leaf check and passes potentially truncated internal-node keys directly to f_eq, which is unsafe for types like bit and varbit that require a minimum valid header size. Returning true for internal nodes is the right conservative choice and is consistent with how the other strategies handle the internal-node case.

王跃林
3020001251@tju.edu.cn

Original:
From：Ayush Tiwari <ayushtiwari.slg01@gmail.com>Date：2026-06-18 03:19:03(中国 (GMT+08:00))To：王跃林<violin0613@tju.edu.cn>Cc：pgsql-bugs <pgsql-bugs@postgresql.org>Subject：Re: Fw:Re: Fw: gbt_var_consistent in contrib/btree_gist/btree_utils_var.c has internal-node type confusion on the <> strategy, bypassing exclusion constraintsHi,

On Tue, 16 Jun 2026 at 16:59, 王跃林 <violin0613@tju.edu.cn> wrote:

0800, 王跃林 wrote:

gbt_var_node_truncate (btree_utils_var.c:214) truncates internal node keys to a common-prefix length. The resulting bytea can have VARSIZE anywhere from 4 upward. When the truncated VARSIZE is below 8 and that key reaches bit_cmp via the buggy BtreeGistNotEqual branch, bytelen becomes negative. Passed to memcmp as size_t, that is several GB. ASan catches it as negative-size-param. A production build without ASan will eventually SEGV when the read crosses an unmapped page.

Thanks for the report!

In gbt_var_consistent() (contrib/btree_gist/btree_utils_var.c), the <>
(BtreeGistNotEqual) branch is the only strategy that does not distinguish
leaf from internal pages. It applies the type's equality function directly
to the stored key on both bounds:

retval = !(tinfo->f_eq(query, key->lower, ...) &&
tinfo->f_eq(query, key->upper, ...));

That seems to be the problem: on internal pages those keys are
truncated (and for bit/varbit the length header is gone too), so
they aren't really valid values to hand to the type's equality
function. Hence the negative length reaching memcmp().

Would it make sense to just have <> follow the same leaf-vs-internal
pattern as the other strategies; negate equality on a leaf, and
otherwise recurse? An internal page can always contain some
non-equal value, so I don't think we lose anything by descending.
I put together a small patch along those lines (plus a bit(8) test
that goes through internal pages); it's attached if it's useful.
(PS. The test exercises the path but passes on a plain build; the OOB
read shows up under ASan (negative-size-param).)

I didn't touch the fixed-size path in btree_utils_num.c, since its
internal keys look like they're exact lower/upper values, but
please correct me if I'm missing something there.

Regards,
Ayush

=?UTF-8?B?546L6LeD5p6X?= <violin0613@tju.edu.cn> writes:

The analysis and fix look correct. The BtreeGistNotEqual branch is
the only strategy that bypasses the is_leaf check and passes
potentially truncated internal-node keys directly to f_eq, which is
unsafe for types like bit and varbit that require a minimum valid
header size. Returning true for internal nodes is the right
conservative choice and is consistent with how the other strategies
handle the internal-node case.

None of this passes the smell test for me. If it's unsafe to
call the type's f_eq function on a truncated key, how is it
any safer to call the f_cmp function? IOW, why aren't *all* the
cases in gbt_var_consistent() broken?

It looks to me like gbt_var_node_truncate adjusts the length words
of the truncated keys so that they are still valid, just shorter.
Or at least it's trying to. That works fine for text and bytea,
but it's not fine for bit/varbit because (a) it fails to update the
"bit_len" field that follows the length word, and (b) the common
prefix length selection logic doesn't know that it mustn't truncate
away any part of the bit_len field. So my own thought about fixing
this is that type bit needs a custom truncation method.

It might well be that gbt_var_consistent's not-equal case is
broken too, but this discussion hasn't established that IMO.
(I continue to regret that we ever accepted such underdocumented code.
I think we ought to reverse-engineer a comment explaining what
gbt_var_consistent is doing, eg, why are all of the tests seemingly
reversed?)

regards, tom lane

Hi,

On Thu, 2 Jul 2026 at 20:08, Tom Lane <tgl@sss.pgh.pa.us> wrote:

=?UTF-8?B?546L6LeD5p6X?= <violin0613@tju.edu.cn> writes:

The analysis and fix look correct. The BtreeGistNotEqual branch is
the only strategy that bypasses the is_leaf check and passes
potentially truncated internal-node keys directly to f_eq, which is
unsafe for types like bit and varbit that require a minimum valid
header size. Returning true for internal nodes is the right
conservative choice and is consistent with how the other strategies
handle the internal-node case.

None of this passes the smell test for me. If it's unsafe to
call the type's f_eq function on a truncated key, how is it
any safer to call the f_cmp function? IOW, why aren't *all* the
cases in gbt_var_consistent() broken?

I think the difference is that for bit/varbit f_eq and f_cmp aren't the
same kind of function. f_eq is biteq (reads bit_len, does VARSIZE-8),
while f_cmp is byteacmp (plain byte-wise, only needs the varlena
header). On internal pages every other strategy goes through
f_cmp/byteacmp, and only the <> branch reaches f_eq. So I believe
that's why the byte-wise cases stay safe on a truncated key and <>
doesn't.

It looks to me like gbt_var_node_truncate adjusts the length words
of the truncated keys so that they are still valid, just shorter.
Or at least it's trying to. That works fine for text and bytea,
but it's not fine for bit/varbit because (a) it fails to update the
"bit_len" field that follows the length word, and (b) the common
prefix length selection logic doesn't know that it mustn't truncate
away any part of the bit_len field. So my own thought about fixing
this is that type bit needs a custom truncation method.

That was my first assumption too, but it looks like the node key has
no bit_len to preserve: gbt_bit_l2n/gbt_bit_xfrm seem to drop it and
keep only the raw bits before truncation runs. If so, a custom
truncation may not help, since the crash seems to come from <> calling
biteq rather than a damaged bit_len. Though I'm not fully sure I'm
reading the l2n step right.

(I continue to regret that we ever accepted such underdocumented code.
I think we ought to reverse-engineer a comment explaining what
gbt_var_consistent is doing, eg, why are all of the tests seemingly
reversed?)

Agreed, we can add a comment there.

Regards,
Ayush

Ayush Tiwari <ayushtiwari.slg01@gmail.com> writes:

On Thu, 2 Jul 2026 at 20:08, Tom Lane <tgl@sss.pgh.pa.us> wrote:

None of this passes the smell test for me. If it's unsafe to
call the type's f_eq function on a truncated key, how is it
any safer to call the f_cmp function?

I think the difference is that for bit/varbit f_eq and f_cmp aren't the
same kind of function. f_eq is biteq (reads bit_len, does VARSIZE-8),
while f_cmp is byteacmp (plain byte-wise, only needs the varlena
header).

Oh! You are right, the internal keys are *not* valid bit/varbit
values, just bytea. The level of non-documentation in this code
is staggering.

So the actual API contract here is that f_eq etc. are to be used only
on leaf keys, while f_cmp is to be used only on internal keys. It's
not too surprising that whoever added NotEqual support didn't know
that, it being documented nowhere.

It kind of looks actually like there's an expectation that all
internal keys are effectively bytea's; note the naming of
gbt_bytea_pf_match, despite the fact that it's applied to all
types under the purview of btree_utils_var.c.

Anyway, I think part of our work here has got to be to raise the
level of documentation of this code. I've had it with having
to reverse-engineer details as fundamental as these.

regards, tom lane

Hi,

On Thu, 2 Jul 2026 at 22:24, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Ayush Tiwari <ayushtiwari.slg01@gmail.com> writes:

On Thu, 2 Jul 2026 at 20:08, Tom Lane <tgl@sss.pgh.pa.us> wrote:

None of this passes the smell test for me. If it's unsafe to
call the type's f_eq function on a truncated key, how is it
any safer to call the f_cmp function?

I think the difference is that for bit/varbit f_eq and f_cmp aren't the
same kind of function. f_eq is biteq (reads bit_len, does VARSIZE-8),
while f_cmp is byteacmp (plain byte-wise, only needs the varlena
header).

Oh! You are right, the internal keys are *not* valid bit/varbit
values, just bytea. The level of non-documentation in this code
is staggering.

So the actual API contract here is that f_eq etc. are to be used only
on leaf keys, while f_cmp is to be used only on internal keys. It's
not too surprising that whoever added NotEqual support didn't know
that, it being documented nowhere.

It kind of looks actually like there's an expectation that all
internal keys are effectively bytea's; note the naming of
gbt_bytea_pf_match, despite the fact that it's applied to all
types under the purview of btree_utils_var.c.

Anyway, I think part of our work here has got to be to raise the
level of documentation of this code. I've had it with having
to reverse-engineer details as fundamental as these.

I've added some documentation in code, patch attached.

Please help reviewing if it looks good or should we be adding
something more.

Regards,
Ayush

Ayush Tiwari <ayushtiwari.slg01@gmail.com> writes:

On Thu, 2 Jul 2026 at 22:24, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Anyway, I think part of our work here has got to be to raise the
level of documentation of this code. I've had it with having
to reverse-engineer details as fundamental as these.

I've added some documentation in code, patch attached.

I had something considerably more ambitious in mind, so I had a
go at that --- and was glad that I did so, because the review
turned up an additional bug as well as some other opportunities
for improvement.

v3-0001 is a documentation-improvement patch. I only touched
the files associated with btree_utils_var.c. Maybe it's worth
doing something similar for the btree_utils_num.c group, but
I have the impression that those are way simpler.

v3-0002 is your patch, editorialized a bit. I left out the
test case because it seemed fairly expensive for something
that won't expose a bug in normal builds. (BTW, I wonder
if rather than documenting the comparisons as being reversed,
we should just flip them all.)

v3-0003 fixes a bug I identified: index builds that use the
gbt_bit_ssup_cmp infrastructure will sort the entries in a
way that doesn't match the bit types' actual ordering,
leading to what's probably a very inefficient index.

v3-0004 and v3-0005 clean up some things that seem like
dead code to me.

0003 through 0005 could use more eyeballs on them.

Also, it occurs to me after another look at 0002 that what was
perhaps intended was something like this for the non-leaf case:

if (is_leaf)
retval = !(tinfo->f_eq(query, key->lower, collation, flinfo));
else
retval = tinfo->trnc ||
!(tinfo->f_cmp(query, key->lower, collation, flinfo) == 0 &&
tinfo->f_cmp(query, key->upper, collation, flinfo) == 0);

That is, if we're looking at non-truncated keys and lower == upper,
then we know that all the keys below this node are exactly that
value, so we can avoid descending if that value is equal to the query.
Most of the time this would not pay off in any savings, but if you
had an index on a column with only a few values, maybe there would be
leaf pages like that? I would think that the planner would avoid
choosing to implement a <> query with an indexscan unless there was
a pretty large fraction of the table that <> would reject, so maybe
this actually is worth doing.

regards, tom lane

Hi,

On Fri, 3 Jul 2026 at 04:32, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Ayush Tiwari <ayushtiwari.slg01@gmail.com> writes:

On Thu, 2 Jul 2026 at 22:24, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Anyway, I think part of our work here has got to be to raise the
level of documentation of this code. I've had it with having
to reverse-engineer details as fundamental as these.

I've added some documentation in code, patch attached.

I had something considerably more ambitious in mind, so I had a
go at that --- and was glad that I did so, because the review
turned up an additional bug as well as some other opportunities
for improvement.

Thanks for working on the patch!

v3-0001 is a documentation-improvement patch. I only touched

the files associated with btree_utils_var.c. Maybe it's worth
doing something similar for the btree_utils_num.c group, but
I have the impression that those are way simpler.

0001 LGTM

v3-0002 is your patch, editorialized a bit. I left out the
test case because it seemed fairly expensive for something
that won't expose a bug in normal builds. (BTW, I wonder
if rather than documenting the comparisons as being reversed,
we should just flip them all.)

I'd lean towards flipping them for readability, though I'm not sure
it's worth the backpatch churn? I guess we could start a new
thread for master on this.

v3-0003 fixes a bug I identified: index builds that use the

gbt_bit_ssup_cmp infrastructure will sort the entries in a
way that doesn't match the bit types' actual ordering,
leading to what's probably a very inefficient index.

It looks right to me, leaf entries are real bit/varbit values, so bitcmp
is the right comparator there.

v3-0004 and v3-0005 clean up some things that seem like
dead code to me.

One small thing on 0005: once gbt_var_node_cp_len stops using
pg_mblen_range, the "#include "mb/pg_wchar.h"" in btree_utils_var.c
looks like it becomes unused. Might be worth dropping it too.

Also, it occurs to me after another look at 0002 that what was
perhaps intended was something like this for the non-leaf case:

if (is_leaf)
retval = !(tinfo->f_eq(query, key->lower, collation,
flinfo));
else
retval = tinfo->trnc ||
!(tinfo->f_cmp(query, key->lower, collation, flinfo)
== 0 &&
tinfo->f_cmp(query, key->upper, collation, flinfo)
== 0);

That is, if we're looking at non-truncated keys and lower == upper,
then we know that all the keys below this node are exactly that
value, so we can avoid descending if that value is equal to the query.
Most of the time this would not pay off in any savings, but if you
had an index on a column with only a few values, maybe there would be
leaf pages like that? I would think that the planner would avoid
choosing to implement a <> query with an indexscan unless there was
a pretty large fraction of the table that <> would reject, so maybe
this actually is worth doing.

I think that optimization is correct. For the non-truncatable types
the internal lower/upper are exact min/max (built via f_cmp in
gbt_var_bin_union with no truncation), so if both equal the query
then everything below does too, and pruning can't drop a match.
Are you planning on including it in the backpatch or to keep the
optimization just part of master, and the bug fix backpatched?

Regards,
Ayush

Ayush Tiwari <ayushtiwari.slg01@gmail.com> writes:

Are you planning on including it in the backpatch or to keep the
optimization just part of master, and the bug fix backpatched?

I was intending to back-patch only the bug fixes, ie 0002 and 0003.
If we make additional cosmetic changes to gbt_var_consistent(),
I could go either way on whether to include those in the back-patch.

BTW, thinking some more about 0004: isn't it pointless to check
gbt_var_node_pf_match in the gbt_var_consistent cases that
only constrain the lower bound, that is LessEqual and Less? In

retval = tinfo->f_cmp(query, key->lower, collation, flinfo) >= 0
|| gbt_var_node_pf_match(key, query, tinfo);

if query >= key->lower then we must search the node, but if it
isn't then the prefix match against upper can't succeed either.

regards, tom lane

Hi,

On Fri, 3 Jul 2026 at 19:20, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Ayush Tiwari <ayushtiwari.slg01@gmail.com> writes:

Are you planning on including it in the backpatch or to keep the
optimization just part of master, and the bug fix backpatched?

I was intending to back-patch only the bug fixes, ie 0002 and 0003.
If we make additional cosmetic changes to gbt_var_consistent(),
I could go either way on whether to include those in the back-patch.

Sounds good.

BTW, thinking some more about 0004: isn't it pointless to check
gbt_var_node_pf_match in the gbt_var_consistent cases that
only constrain the lower bound, that is LessEqual and Less? In

retval = tinfo->f_cmp(query, key->lower, collation,
flinfo) >= 0
|| gbt_var_node_pf_match(key, query, tinfo);

if query >= key->lower then we must search the node, but if it
isn't then the prefix match against upper can't succeed either.

Hmm, looks like the || gbt_var_node_pf_match(...) clause isn't
needed in the BTLessStrategyNumber and BTLessEqualStrategyNumber
cases. Those only compare against the lower bound, and if query
sorts before lower then it sorts before upper too, so a prefix
match against the (truncated) upper can never succeed there.
I tried changing it locally and ran the regression tests, all passed.

Regards,
Ayush

Ayush Tiwari <ayushtiwari.slg01@gmail.com> writes:

On Fri, 3 Jul 2026 at 19:20, Tom Lane <tgl@sss.pgh.pa.us> wrote:

BTW, thinking some more about 0004: isn't it pointless to check
gbt_var_node_pf_match in the gbt_var_consistent cases that
only constrain the lower bound, that is LessEqual and Less?

Hmm, looks like the || gbt_var_node_pf_match(...) clause isn't
needed in the BTLessStrategyNumber and BTLessEqualStrategyNumber
cases. Those only compare against the lower bound, and if query
sorts before lower then it sorts before upper too, so a prefix
match against the (truncated) upper can never succeed there.
I tried changing it locally and ran the regression tests, all passed.

I did some more work on that idea (just cosmetic changes) and
pushed everything. Thanks for working on this!

regards, tom lane