Strange GiST logic leading to uninitialized memory access in pg_trgm gist code
(From a report by user "ftzdomino" on IRC of a segfault while loading
data with a pg_trgm gist index)
If gtrgm_picksplit is invoked on a vector of exactly 2 items (which I
think is rare, but it can happen if gistSplit recurses or I think in
cases of secondary splits), then it tries to access cache[2] without
ever having initialized it, causing hilarity to ensue.
What I don't entirely understand is why the code is insisting on
treating the last item as special: given N items, it tries to find seeds
from the first N-1 items only. This would make a vague sort of sense if
the N'th item was always the just-inserted one, but this doesn't appear
to be always the case (e.g. recursive calls in gistSplit, or secondary
splits), and even if it were it's not clear that it would be correct
logic.
What gtrgm_picksplit currently does, as I read it, is:
take first N-1 items
(note that entryvec->n is N+1, it sets maxoff = entryvec->n - 2)
populate a cache of their signatures
find the two furthest apart as seeds
if we didn't choose two, then default to items 1 and 2 as seeds
(note here that if N=2 then item 2 is not cached)
make datums from the cache entries of the two seeds
(explodes here when N=2)
Increase maxoff and construct the cache entry for item N
Split all N items using the two seeds
Now the obvious simple fix is just to reorder those last two operations,
and the original reporter verified that doing so fixed their problem
(patch attached). But I'd really like to understand the logic here and
whether there is any reason to have this special treatment at all - why
would it not be better to just cache all N items upfront and consider
them all as potential seeds?
Another issue I don't understand yet is that even though this code is
largely unchanged since 8.x, the original reporter could not reproduce
the crash on any version before 13.0.
Anyone have any ideas? (If not, I'll commit and backpatch something like
the attached patch at some suitable time.)
--
Andrew (irc:RhodiumToad)
Attachments:
tgrm.patchtext/x-patchDownload
diff --git a/contrib/pg_trgm/trgm_gist.c b/contrib/pg_trgm/trgm_gist.c
index 9937ef9253..c7f2873e13 100644
--- a/contrib/pg_trgm/trgm_gist.c
+++ b/contrib/pg_trgm/trgm_gist.c
@@ -847,15 +847,22 @@ gtrgm_picksplit(PG_FUNCTION_ARGS)
v->spl_nleft = 0;
v->spl_nright = 0;
+ /*
+ * We ignored the last entry in the list above, and did not populate its
+ * cache entry yet, but if we were called with exactly 2 items then seed_2
+ * now points to it, so we must fill in the cache entry before trying to
+ * build datums from the seeds.
+ */
+ maxoff = OffsetNumberNext(maxoff);
+ fillcache(&cache[maxoff], GETENTRY(entryvec, maxoff),
+ &cache_sign[siglen * maxoff], siglen);
+
/* form initial .. */
datum_l = gtrgm_alloc(cache[seed_1].allistrue, siglen, cache[seed_1].sign);
datum_r = gtrgm_alloc(cache[seed_2].allistrue, siglen, cache[seed_2].sign);
union_l = GETSIGN(datum_l);
union_r = GETSIGN(datum_r);
- maxoff = OffsetNumberNext(maxoff);
- fillcache(&cache[maxoff], GETENTRY(entryvec, maxoff),
- &cache_sign[siglen * maxoff], siglen);
/* sort before ... */
costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
Hi!
On Wed, Nov 11, 2020 at 12:53 PM Andrew Gierth
<andrew@tao11.riddles.org.uk> wrote:
Now the obvious simple fix is just to reorder those last two operations,
and the original reporter verified that doing so fixed their problem
(patch attached). But I'd really like to understand the logic here and
whether there is any reason to have this special treatment at all - why
would it not be better to just cache all N items upfront and consider
them all as potential seeds?
I think this comes from the idea that when N items are passed to the
picksplit method, then the first N-1 are existing items on the page,
while the last Nth is the new item to be inserted. So, we are trying
to split first N-1 items and then insert the last Nth item there. But
this is wrong for two reasons.
1) As you've pointed out, GiST code doesn't necessarily pass items to
the picksplit method in that way.
2) Even if items are passed as assumed, there is no point in having
special handling of the item to be inserted. It's better to consider
the whole set of items to produce a better split.
Another issue I don't understand yet is that even though this code is
largely unchanged since 8.x, the original reporter could not reproduce
the crash on any version before 13.0.
I think this is related to my commit 911e702077. It has changed the
memory allocation for the signatures to support the signatures of
variable length. So, it seems that despite the error existing since
8.x, it started causing segfaults only since 911e702077.
Anyone have any ideas? (If not, I'll commit and backpatch something like
the attached patch at some suitable time.)
I would rather propose to rip off special handling of the last item
completely (see the attached patch).
------
Regards,
Alexander Korotkov
Attachments:
0001-Fix-handling-of-the-last-item-in-gtrgm_picksplit.patchapplication/octet-stream; name=0001-Fix-handling-of-the-last-item-in-gtrgm_picksplit.patchDownload
From 6c9250aec8e952556c7f58c76896d8ff08a03dce Mon Sep 17 00:00:00 2001
From: Alexander Korotkov <akorotkov@postgresql.org>
Date: Thu, 12 Nov 2020 06:16:30 +0300
Subject: [PATCH] Fix handling of the last item in gtrgm_picksplit()
Reported-by:
Bug:
Discussion:
Author:
Reviewed-by:
Tested-by:
Backpatch-through:
---
contrib/pg_trgm/trgm_gist.c | 12 ++++--------
1 file changed, 4 insertions(+), 8 deletions(-)
diff --git a/contrib/pg_trgm/trgm_gist.c b/contrib/pg_trgm/trgm_gist.c
index 2a067306354..9c0ed6ed73a 100644
--- a/contrib/pg_trgm/trgm_gist.c
+++ b/contrib/pg_trgm/trgm_gist.c
@@ -786,7 +786,7 @@ Datum
gtrgm_picksplit(PG_FUNCTION_ARGS)
{
GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
- OffsetNumber maxoff = entryvec->n - 2;
+ OffsetNumber maxoff = entryvec->n - 1;
GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
int siglen = GET_SIGLEN();
OffsetNumber k,
@@ -811,8 +811,8 @@ gtrgm_picksplit(PG_FUNCTION_ARGS)
SPLITCOST *costvector;
/* cache the sign data for each existing item */
- cache = (CACHESIGN *) palloc(sizeof(CACHESIGN) * (maxoff + 2));
- cache_sign = palloc(siglen * (maxoff + 2));
+ cache = (CACHESIGN *) palloc(sizeof(CACHESIGN) * (maxoff + 1));
+ cache_sign = palloc(siglen * (maxoff + 1));
for (k = FirstOffsetNumber; k <= maxoff; k = OffsetNumberNext(k))
fillcache(&cache[k], GETENTRY(entryvec, k), &cache_sign[siglen * k],
@@ -841,7 +841,7 @@ gtrgm_picksplit(PG_FUNCTION_ARGS)
}
/* initialize the result vectors */
- nbytes = (maxoff + 2) * sizeof(OffsetNumber);
+ nbytes = maxoff * sizeof(OffsetNumber);
v->spl_left = left = (OffsetNumber *) palloc(nbytes);
v->spl_right = right = (OffsetNumber *) palloc(nbytes);
v->spl_nleft = 0;
@@ -853,9 +853,6 @@ gtrgm_picksplit(PG_FUNCTION_ARGS)
union_l = GETSIGN(datum_l);
union_r = GETSIGN(datum_r);
- maxoff = OffsetNumberNext(maxoff);
- fillcache(&cache[maxoff], GETENTRY(entryvec, maxoff),
- &cache_sign[siglen * maxoff], siglen);
/* sort before ... */
costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
@@ -944,7 +941,6 @@ gtrgm_picksplit(PG_FUNCTION_ARGS)
}
}
- *right = *left = FirstOffsetNumber;
v->spl_ldatum = PointerGetDatum(datum_l);
v->spl_rdatum = PointerGetDatum(datum_r);
--
2.14.3
"Alexander" == Alexander Korotkov <aekorotkov@gmail.com> writes:
Another issue I don't understand yet is that even though this code
is largely unchanged since 8.x, the original reporter could not
reproduce the crash on any version before 13.0.
Alexander> I think this is related to my commit 911e702077. It has
Alexander> changed the memory allocation for the signatures to support
Alexander> the signatures of variable length. So, it seems that despite
Alexander> the error existing since 8.x, it started causing segfaults
Alexander> only since 911e702077.
Aha. Prior to that change, cache[i].sign was an array rather than a
pointer, so it would not crash even when accessed without
initialization. What would happen instead is that an incorrect signature
would be used, which might lead to problems later in index lookups
(though I haven't tested that).
Alexander> I would rather propose to rip off special handling of the
Alexander> last item completely (see the attached patch).
Yeah. I'll go with that, once I finish testing it.
--
Andrew (irc:RhodiumToad)