pg.ddx.io pgsql-bugs@postgresql.org mailing list archive
help / color / mirror / Atom feedBUG #15518: intarray index crashes hard
2+ messages / 2 participants
[nested] [flat]
* BUG #15518: intarray index crashes hard
@ 2018-11-22 22:28 PG Bug reporting form <noreply@postgresql.org>
0 siblings, 1 reply; 2+ messages in thread
From: PG Bug reporting form @ 2018-11-22 22:28 UTC (permalink / raw)
To: pgsql-bugs@lists.postgresql.org; +Cc: andrew@tao11.riddles.org.uk
The following bug has been logged on the website:
Bug reference: 15518
Logged by: Andrew Gierth
Email address: andrew@tao11.riddles.org.uk
PostgreSQL version: 11.1
Operating system: any
Description:
Based on a report from IRC:
create extension intarray;
create table ibreak (id integer, a integer[]);
create index on ibreak using gist (a);
insert into ibreak
select i, array(select hashint4(i*j) from generate_series(1,100) j)
from generate_series(1,20) i;
-- segfault
This happens because the default "small" intarray opclass, gist__int_ops,
has wholly inadequate sanity checks on the data; while it will reject
individual rows with too many distinct values, it will happily construct
compressed non-leaf keys that will crash the decompression code due to
overflowing an "int", or produce an unhelpful memory allocation error, or
consume vast amounts of CPU time without checking for interrupts.
This isn't new; it looks like this issue has existed as long as intarray
has.
Obviously it's not intended that gist__int_ops should actually work with
data of this kind - that's what gist__intbig_ops is for. But it's not
reasonable for it to crash rather than returning an error.
I'm working on a patch.
^ permalink raw reply [nested|flat] 2+ messages in thread
* Re: BUG #15518: intarray index crashes hard
@ 2018-11-23 21:49 Andrew Gierth <andrew@tao11.riddles.org.uk>
parent: PG Bug reporting form <noreply@postgresql.org>
0 siblings, 0 replies; 2+ messages in thread
From: Andrew Gierth @ 2018-11-23 21:49 UTC (permalink / raw)
To: pgsql-bugs@lists.postgresql.org
>>>>> "PG" == PG Bug reporting form <noreply@postgresql.org> writes:
PG> Obviously it's not intended that gist__int_ops should actually work
PG> with data of this kind - that's what gist__intbig_ops is for. But
PG> it's not reasonable for it to crash rather than returning an error.
PG> I'm working on a patch.
And here it is.
This version doesn't restrict the sparseness of keys any more than it
needs to for safety. This necessitates improving the O(N^2) compression
algorithm to O(N), because otherwise it's possible to create datasets
that cause a single compression call to run for months (with no check
for interrupts, either).
There are essentially 4 specific issues addressed:
1. Integer overflow in internal_size could result in memory corruption
in decompression since a zero-length array would be allocated and
then written to.
2. Integer overflow in g_int_compress could cause pessimal merge
choices, resulting in unnecessarily large ranges (which would in turn
trigger issue 1 above)
3. Even without overflow, array sizes could become large enough to cause
unexplained memory allocation errors, so cap the sizes and report
actual errors pointing at gist__intbig_ops as needed.
4. Large inputs to the compression function always consist of large runs
of consecutive integers, and the compression loop was processing
these one at a time in an O(N^2) manner with a lot of overhead. The
expected runtime of this function could easily exceed 6 months as a
result. Performing a linear-time first pass reduces the worst case
to something on the order of seconds.
--
Andrew (irc:RhodiumToad)
Attachments:
[text/x-patch] iafix.patch (4.3K, ../../878t1jsczr.fsf@news-spur.riddles.org.uk/2-iafix.patch)
download | inline diff:
diff --git a/contrib/intarray/_int_gist.c b/contrib/intarray/_int_gist.c
index 911d18023b..fe10cb56b6 100644
--- a/contrib/intarray/_int_gist.c
+++ b/contrib/intarray/_int_gist.c
@@ -13,6 +13,17 @@
#define GETENTRY(vec,pos) ((ArrayType *) DatumGetPointer((vec)->vector[(pos)].key))
/*
+ * Control the maximum sparseness of compressed keys.
+ *
+ * The upper safe bound for this limit is half the maximum allocatable array
+ * size. A lower bound would give more guarantees that pathological data
+ * wouldn't eat excessive CPU and memory, but at the expense of breaking
+ * possibly working (after a fashion) indexes.
+ */
+#define MAXNUMELTS (Min((MaxAllocSize / sizeof(Datum)),((MaxAllocSize - ARR_OVERHEAD_NONULLS(1)) / sizeof(int)))/2)
+/* or: #define MAXNUMELTS 1000000 */
+
+/*
** GiST support methods
*/
PG_FUNCTION_INFO_V1(g_int_consistent);
@@ -141,11 +152,13 @@ g_int_compress(PG_FUNCTION_ARGS)
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
GISTENTRY *retval;
ArrayType *r;
- int len;
+ int len,
+ lenr;
int *dr;
int i,
- min,
+ j,
cand;
+ int64 min;
if (entry->leafkey)
{
@@ -186,23 +199,62 @@ g_int_compress(PG_FUNCTION_ARGS)
dr = ARRPTR(r);
- for (i = len - 1; i >= 0; i--)
- dr[2 * i] = dr[2 * i + 1] = dr[i];
+ /*
+ * "len" at this point is the number of ranges we will construct.
+ * "lenr" is the number of ranges we must eventually remove by
+ * merging, we must be careful to remove no more than this number.
+ */
+ lenr = len - MAXNUMRANGE;
+
+ /*
+ * Initially assume we can merge consecutive ints into a range. but we
+ * must count every value removed and stop when lenr runs out
+ */
+ for (j = i = len - 1; i > 0 && lenr > 0; i--, j--)
+ {
+ int r_end = dr[i];
+ int r_start = r_end;
+ while (i > 0 && lenr > 0 && dr[i-1] == r_start - 1)
+ --r_start, --i, --lenr;
+ dr[2*j] = r_start;
+ dr[2*j+1] = r_end;
+ }
+ /* just copy the rest, if any, as trivial ranges */
+ for (; i >= 0; i--, j--)
+ dr[2*j] = dr[2*j + 1] = dr[i];
- len *= 2;
+ if (++j)
+ {
+ /*
+ * shunt everything down to start at the right place
+ */
+ memmove((void *) &dr[0], (void *) &dr[2*j], 2*(len - j) * sizeof(int32));
+ }
+ /*
+ * make "len" be number of array elements, not ranges
+ */
+ len = 2*(len - j);
cand = 1;
while (len > MAXNUMRANGE * 2)
{
- min = INT_MAX;
+ min = PG_INT64_MAX;
for (i = 2; i < len; i += 2)
- if (min > (dr[i] - dr[i - 1]))
+ if (min > ((int64)dr[i] - (int64)dr[i - 1]))
{
- min = (dr[i] - dr[i - 1]);
+ min = ((int64)dr[i] - (int64)dr[i - 1]);
cand = i;
}
memmove((void *) &dr[cand - 1], (void *) &dr[cand + 1], (len - cand - 1) * sizeof(int32));
len -= 2;
}
+ /*
+ * check sparseness of result
+ */
+ lenr = internal_size(dr, len);
+ if (lenr < 0 || lenr > MAXNUMELTS)
+ ereport(ERROR,
+ (errmsg("data is too sparse, recreate index using gist__intbig_ops opclass instead")));
+
r = resize_intArrayType(r, len);
retval = palloc(sizeof(GISTENTRY));
gistentryinit(*retval, PointerGetDatum(r),
@@ -260,6 +312,9 @@ g_int_decompress(PG_FUNCTION_ARGS)
din = ARRPTR(in);
lenr = internal_size(din, lenin);
+ if (lenr < 0 || lenr > MAXNUMELTS)
+ ereport(ERROR,
+ (errmsg("compressed array is too big, recreate index using gist__intbig_ops opclass instead")));
r = new_intArrayType(lenr);
dr = ARRPTR(r);
diff --git a/contrib/intarray/_int_tool.c b/contrib/intarray/_int_tool.c
index d86485dfa5..7288b35b02 100644
--- a/contrib/intarray/_int_tool.c
+++ b/contrib/intarray/_int_tool.c
@@ -225,6 +225,7 @@ new_intArrayType(int num)
/* if no elements, return a zero-dimensional array */
if (num <= 0)
{
+ Assert(num == 0);
r = construct_empty_array(INT4OID);
return r;
}
@@ -252,6 +253,7 @@ resize_intArrayType(ArrayType *a, int num)
/* if no elements, return a zero-dimensional array */
if (num <= 0)
{
+ Assert(num == 0);
ARR_NDIM(a) = 0;
return a;
}
@@ -289,14 +291,18 @@ int
internal_size(int *a, int len)
{
int i,
- size = 0;
+ size;
+ int64 tsize = 0;
for (i = 0; i < len; i += 2)
{
if (!i || a[i] != a[i - 1]) /* do not count repeated range */
- size += a[i + 1] - a[i] + 1;
+ tsize += (int64)(a[i + 1]) - (int64)(a[i]) + 1;
}
+ size = (int) tsize;
+ if ((int64)size != tsize)
+ return -1; /* overflow */
return size;
}
^ permalink raw reply [nested|flat] 2+ messages in thread
end of thread, other threads:[~2018-11-23 21:49 UTC | newest]
Thread overview: 2+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2018-11-22 22:28 BUG #15518: intarray index crashes hard PG Bug reporting form <noreply@postgresql.org>
2018-11-23 21:49 ` Andrew Gierth <andrew@tao11.riddles.org.uk>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox