public inbox for [email protected]
help / color / mirror / Atom feedFrom: Ayush Tiwari <[email protected]>
To: 王跃林 <[email protected]>
Cc: pgsql-bugs <[email protected]>
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 constraints
Date: Thu, 18 Jun 2026 00:49:03 +0530
Message-ID: <CAJTYsWWSx+5-kVaivB_znaQCk3TmHrO4QNNM-CD3AN-oOSmG8w@mail.gmail.com> (raw)
In-Reply-To: <AH*AvQCYKhQGVvPWi1GiU4oY.8.1781609375063.Hmail.3020001251@tju.edu.cn>
References: <AH*AvQCYKhQGVvPWi1GiU4oY.8.1781609375063.Hmail.3020001251@tju.edu.cn>
Hi,
On Tue, 16 Jun 2026 at 16:59, 王跃林 <[email protected]> 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
Attachments:
[application/octet-stream] 0001-Fix-btree_gist-strategy-on-internal-index-pages.patch (4.6K, ../CAJTYsWWSx+5-kVaivB_znaQCk3TmHrO4QNNM-CD3AN-oOSmG8w@mail.gmail.com/3-0001-Fix-btree_gist-strategy-on-internal-index-pages.patch)
download | inline diff:
From a53b3f59a7d01f01d21d7f19fd6d34a9a3860228 Mon Sep 17 00:00:00 2001
From: Ayush Tiwari <[email protected]>
Date: Wed, 17 Jun 2026 22:52:36 +0530
Subject: [PATCH v1] Fix btree_gist <> strategy on internal index pages
gbt_var_consistent() handled the <> (BtreeGistNotEqual) strategy without
distinguishing leaf from internal pages, unlike every other strategy.
Internal keys are lossy, truncated prefixes, and for bit/varbit the
leaf-to-node transform drops the VarBit length header, so such a key is
not a valid value of the indexed type.
Passing it to the type's equality function is a type confusion. For
bit/varbit it reaches bit_cmp(), where VARBITBYTES() computes VARSIZE - 8;
a key with VARSIZE < 8 yields a negative length that, passed to memcmp()
as size_t, becomes huge and reads out of bounds (eventually crashing the
backend). Even without a crash it can give wrong equality results and
defeat an exclusion constraint declared with <>.
Make the <> branch distinguish leaf and internal pages: on a leaf, negate
the equality test against the stored value; on an internal page, recurse
unconditionally. The fix is in the shared gbt_var_consistent() and so
covers every variable-length type. Add a regression test.
---
contrib/btree_gist/btree_utils_var.c | 14 +++++++++++--
contrib/btree_gist/expected/not_equal.out | 24 +++++++++++++++++++++++
contrib/btree_gist/sql/not_equal.sql | 18 +++++++++++++++++
3 files changed, 54 insertions(+), 2 deletions(-)
diff --git a/contrib/btree_gist/btree_utils_var.c b/contrib/btree_gist/btree_utils_var.c
index 25c3bbe8eac..6043dd811bc 100644
--- a/contrib/btree_gist/btree_utils_var.c
+++ b/contrib/btree_gist/btree_utils_var.c
@@ -611,8 +611,18 @@ gbt_var_consistent(GBT_VARKEY_R *key,
|| gbt_var_node_pf_match(key, query, tinfo);
break;
case BtreeGistNotEqualStrategyNumber:
- retval = !(tinfo->f_eq(query, key->lower, collation, flinfo) &&
- tinfo->f_eq(query, key->upper, collation, flinfo));
+
+ /*
+ * Must distinguish leaf and internal pages. Internal keys are
+ * lossy, truncated prefixes whose representation may differ from
+ * the leaf form (e.g. bit/varbit), so f_eq() on them can give
+ * wrong answers or read out of bounds. An internal page may
+ * always hold a non-equal value, so just recurse into it.
+ */
+ if (is_leaf)
+ retval = !tinfo->f_eq(query, key->lower, collation, flinfo);
+ else
+ retval = true;
break;
default:
retval = false;
diff --git a/contrib/btree_gist/expected/not_equal.out b/contrib/btree_gist/expected/not_equal.out
index 85b1e868a87..922950e0c2f 100644
--- a/contrib/btree_gist/expected/not_equal.out
+++ b/contrib/btree_gist/expected/not_equal.out
@@ -39,3 +39,27 @@ INSERT INTO zoo VALUES(123, 'lion');
ERROR: conflicting key value violates exclusion constraint "zoo_cage_animal_excl"
DETAIL: Key (cage, animal)=(123, lion) conflicts with existing key (cage, animal)=(123, zebra).
INSERT INTO zoo VALUES(124, 'lion');
+-- A <> search must descend internal pages instead of comparing the query to a
+-- truncated internal key. Use a multi-level index and check it agrees with seq scan.
+CREATE TABLE bitne (a bit(8));
+INSERT INTO bitne SELECT (g % 256)::bit(8) FROM generate_series(1, 20000) g;
+CREATE INDEX bitne_idx ON bitne USING gist (a);
+SET enable_seqscan to on;
+SET enable_indexscan to off;
+SET enable_bitmapscan to off;
+SELECT count(*) FROM bitne WHERE a <> B'00000000';
+ count
+-------
+ 19922
+(1 row)
+
+SET enable_seqscan to off;
+SET enable_indexscan to on;
+SET enable_bitmapscan to on;
+SELECT count(*) FROM bitne WHERE a <> B'00000000';
+ count
+-------
+ 19922
+(1 row)
+
+DROP TABLE bitne;
diff --git a/contrib/btree_gist/sql/not_equal.sql b/contrib/btree_gist/sql/not_equal.sql
index 6dfac5d0aae..ecb135f47d2 100644
--- a/contrib/btree_gist/sql/not_equal.sql
+++ b/contrib/btree_gist/sql/not_equal.sql
@@ -34,3 +34,21 @@ INSERT INTO zoo VALUES(123, 'zebra');
INSERT INTO zoo VALUES(123, 'zebra');
INSERT INTO zoo VALUES(123, 'lion');
INSERT INTO zoo VALUES(124, 'lion');
+
+-- A <> search must descend internal pages instead of comparing the query to a
+-- truncated internal key. Use a multi-level index and check it agrees with seq scan.
+CREATE TABLE bitne (a bit(8));
+INSERT INTO bitne SELECT (g % 256)::bit(8) FROM generate_series(1, 20000) g;
+CREATE INDEX bitne_idx ON bitne USING gist (a);
+
+SET enable_seqscan to on;
+SET enable_indexscan to off;
+SET enable_bitmapscan to off;
+SELECT count(*) FROM bitne WHERE a <> B'00000000';
+
+SET enable_seqscan to off;
+SET enable_indexscan to on;
+SET enable_bitmapscan to on;
+SELECT count(*) FROM bitne WHERE a <> B'00000000';
+
+DROP TABLE bitne;
--
2.34.1
view thread (13+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected]
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 constraints
In-Reply-To: <CAJTYsWWSx+5-kVaivB_znaQCk3TmHrO4QNNM-CD3AN-oOSmG8w@mail.gmail.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox