From: Andrew Gierth <andrew@tao11.riddles.org.uk>
To: pgsql-bugs@lists.postgresql.org
Subject: Re: BUG #15518: intarray index crashes hard
Date: Fri, 23 Nov 2018 21:49:22 +0000
Message-ID: <878t1jsczr.fsf@news-spur.riddles.org.uk> (raw)
In-Reply-To: <15518-799e426c3b4f8358@postgresql.org>
References: <15518-799e426c3b4f8358@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:iafix.patch (text/x-patch, 4.3K) downloaddiff --git a/contrib/intarray/_int_gist.c b/contrib/intarray/_int_gist.cindex 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.cindex 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;
}
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: pgsql-bugs@postgresql.org
Cc: andrew@tao11.riddles.org.uk, pgsql-bugs@lists.postgresql.org
Subject: Re: BUG #15518: intarray index crashes hard
In-Reply-To: <878t1jsczr.fsf@news-spur.riddles.org.uk>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
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