BUG #14722: Segfault in tuplesort_heap_siftup, 32 bit overflow

On Thu, Jun 29, 2017 at 9:16 AM, <skoposov@cmu.edu> wrote:

I have a very large table (40e9 records) that I'm trying to create the index
on and I am getting a segmentation fault that could be traced as far as I
understand to a 32 bit int overflow in tuplesort_heap_siftup

Can your print the Tuplesortstate (the variable "state") within GDB,
and post it here?

--
Peter Geoghegan

--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs

On Thu, 2017-06-29 at 09:34 -0700, Peter Geoghegan wrote:

On Thu, Jun 29, 2017 at 9:16 AM, <skoposov@cmu.edu> wrote:

I have a very large table (40e9 records) that I'm trying to create the index
on and I am getting a segmentation fault that could be traced as far as I
understand to a 32 bit int overflow in tuplesort_heap_siftup

Can your print the Tuplesortstate (the variable "state") within GDB,
and post it here?

Here it is (it is a different run, as I closed the previous session,
but the bug is 100% reproduceable).

Program received signal SIGSEGV, Segmentation fault.
0x0000000000914cf8 in tuplesort_heap_siftup (state=0x234ffe8,
checkIndex=1 '\001') at tuplesort.c:3014
3014 HEAPCOMPARE(&memtuples[j], &memtuples[j
+ 1]) > 0)
(gdb) print (state)
$1 = (Tuplesortstate *) 0x234ffe8
(gdb) print (*state)
$2 = {status = TSS_BUILDRUNS, nKeys = 1, randomAccess = 0 '\000',
bounded = 0 '\000', boundUsed = 0 '\000', bound = 0, availMem =
-6442450776,
allowedMem = 75161927680, maxTapes = 262144, tapeRange = 262143,
sortcontext = 0x234e5c8, tapeset = 0x7fbf032a3048,
comparetup = 0x918d8a <comparetup_index_btree>, copytup = 0x919bbc
<copytup_index>, writetup = 0x91a243 <writetup_index>,
readtup = 0x91a31f <readtup_index>, memtuples = 0x7fb283aa1048,
memtupcount = 1342177275, memtupsize = 1342177279, growmemtuples = 0
'\000',
currentRun = 0, mergeactive = 0x7fc80aab9048 "", mergenext =
0x7fc80a23e048, mergelast = 0x7fc809ebc048, mergeavailslots =
0x7fc809dbb048,
mergeavailmem = 0x7fc8096ba048, mergefreelist = 0, mergefirstfree = 0,
Level = 1, destTape = 0, tp_fib = 0x7fc8095b9048, tp_runs =
0x7fc8094b8048,
tp_dummy = 0x7fc8093b7048, tp_tapenum = 0x7fc8081b7048, activeTapes =
0, result_tape = -1, current = 0, eof_reached = 0 '\000', markpos_block
= 0,
markpos_offset = 0, markpos_eof = 0 '\000', tupDesc = 0x0, sortKeys =
0x2350288, onlyKey = 0x0, abbrevNext = 10, indexInfo = 0x0, estate =
0x0,
heapRel = 0x7fd040f32f78, indexRel = 0x7fd040f3b8e0, enforceUnique = 0
'\000', hash_mask = 0, datumType = 0, datumTypeLen = 0,
datumTypeByVal = 0 '\000', ru_start = {tv = {tv_sec = 0, tv_usec = 0},
ru = {ru_utime = {tv_sec = 0, tv_usec = 0}, ru_stime = {tv_sec = 0,
tv_usec = 0}, ru_maxrss = 0, ru_ixrss = 0, ru_idrss = 0,
ru_isrss = 0, ru_minflt = 0, ru_majflt = 0, ru_nswap = 0, ru_inblock =
0,
ru_oublock = 0, ru_msgsnd = 0, ru_msgrcv = 0, ru_nsignals = 0,
ru_nvcsw = 0, ru_nivcsw = 0}}}

Regards,
Sergey

--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs

On Thu, Jun 29, 2017 at 9:16 AM, <skoposov@cmu.edu> wrote:

From a quick look of the code it looks to me that the reason for the bug is
the 32 bit int overflow in the j=2*i+1 calculation inside the
tuplesort_heap_siftup leading to negative values of j.

It seems likely that the explanation is as simple as that. This
happens during run generation with replacement selection. All versions
are affected, but version 9.6+ is dramatically less likely to be
affected, because replacement selection was all but killed in Postgres
9.6.

This is an oversight in commit 263865a. The fix is to use a variable
that won't overflow in tuplesort_heap_siftup() -- this is probably a
one-liner, because when the variable overflows today, the correct
behavior would be for control to break out of the loop that declares
the overflowing variable "j", and, I don't see any similar problem in
other heap maintenance routines. It's a very isolated problem.

I could write a patch.

--
Peter Geoghegan

--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs

On Thu, 2017-06-29 at 10:00 -0700, Peter Geoghegan wrote:

On Thu, Jun 29, 2017 at 9:16 AM, <skoposov@cmu.edu> wrote:

From a quick look of the code it looks to me that the reason for the bug is
the 32 bit int overflow in the j=2*i+1 calculation inside the
tuplesort_heap_siftup leading to negative values of j.

It seems likely that the explanation is as simple as that. This
happens during run generation with replacement selection. All versions
are affected, but version 9.6+ is dramatically less likely to be
affected, because replacement selection was all but killed in Postgres
9.6.

This is an oversight in commit 263865a. The fix is to use a variable
that won't overflow in tuplesort_heap_siftup() -- this is probably a
one-liner, because when the variable overflows today, the correct
behavior would be for control to break out of the loop that declares
the overflowing variable "j", and, I don't see any similar problem in
other heap maintenance routines. It's a very isolated problem.

I could write a patch.

For the time being I've just changed the type of i,j from int to long
(or int64) and I am running the index creation now. I let you submit a
patch -- thanks in advance.

I also noticed that the availMem variable was negative in the printout
of the TupleSortState.
availMem =-6442450776,
I don't know whether that's an issue on its own or was caused by the
(i,j) overflow. (availMem seems to be int64 variable though).

Sergey

--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs

On Thu, Jun 29, 2017 at 10:50 AM, Sergey Koposov <skoposov@cmu.edu> wrote:

For the time being I've just changed the type of i,j from int to long
(or int64) and I am running the index creation now. I let you submit a
patch -- thanks in advance.

That's more or less what I had in mind.

I also noticed that the availMem variable was negative in the printout
of the TupleSortState.
availMem =-6442450776,
I don't know whether that's an issue on its own or was caused by the
(i,j) overflow. (availMem seems to be int64 variable though).

That's definitely allowed to go negative, which is why it's int64.
That's about 6GB of memory, though, which seems unusually large.

--
Peter Geoghegan

--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs

On Thu, Jun 29, 2017 at 9:16 AM, <skoposov@cmu.edu> wrote:

Here are the commands leading to the crash:

wsdb=# set maintenance_work_mem to '70GB';

SET
wsdb=# create index on cgonzal.vvv_single_ks_sorted (q3c_ang2ipix(ra,dec));

----

Importantly the table has already been sorted by q3c_ang2ipix(ra,dec) !

BTW, given the exact details of what you're doing here, using only 1MB
of maintenance_work_mem will probably make the operation complete
sooner.

--
Peter Geoghegan

--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs

On Thu, 2017-06-29 at 11:59 -0700, Peter Geoghegan wrote:

On Thu, Jun 29, 2017 at 9:16 AM, <skoposov@cmu.edu> wrote:

Here are the commands leading to the crash:

wsdb=# set maintenance_work_mem to '70GB';

SET
wsdb=# create index on cgonzal.vvv_single_ks_sorted (q3c_ang2ipix(ra,dec));

----

Importantly the table has already been sorted by q3c_ang2ipix(ra,dec) !

BTW, given the exact details of what you're doing here, using only 1MB
of maintenance_work_mem will probably make the operation complete
sooner.

Thank you. It does seem to be ~ 50% faster.
It is somewhat unfortunate that maintenance_work_mem is
counterproductive in this scenario, given that indexing an ordered table
is a natural step in clustering a table...

Sergey

--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs

On Thu, 2017-06-29 at 10:00 -0700, Peter Geoghegan wrote:

On Thu, Jun 29, 2017 at 9:16 AM, <skoposov@cmu.edu> wrote:

From a quick look of the code it looks to me that the reason for the bug is
the 32 bit int overflow in the j=2*i+1 calculation inside the
tuplesort_heap_siftup leading to negative values of j.

It seems likely that the explanation is as simple as that. This
happens during run generation with replacement selection. All versions
are affected, but version 9.6+ is dramatically less likely to be
affected, because replacement selection was all but killed in Postgres
9.6.

This is an oversight in commit 263865a. The fix is to use a variable
that won't overflow in tuplesort_heap_siftup() -- this is probably a
one-liner, because when the variable overflows today, the correct
behavior would be for control to break out of the loop that declares
the overflowing variable "j", and, I don't see any similar problem in
other heap maintenance routines. It's a very isolated problem.

I could write a patch.

Just to avoid being forgotten, I attach a trivial patch against 9.5
branch as well as have created a commitfest submission
https://commitfest.postgresql.org/14/1189/

The script below allows to reproduce the bug (segfault) and test that
the patch fixes it: (>~70 GB of RAM are needed and 100+GB of disk
space)
---
create table xx3 as
select generate_series as a
from generate_series(0,(1.5*((1::bigint)<<31))::bigint);
set maintenance_work_mem to '70GB';
create index on xx3(a);
----

Hopefully somebody can take care of patching other PG branches.

Sergey

Sergey Koposov <skoposov@cmu.edu> writes:

On Thu, 2017-06-29 at 10:00 -0700, Peter Geoghegan wrote:

This is an oversight in commit 263865a. The fix is to use a variable
that won't overflow in tuplesort_heap_siftup() -- this is probably a
one-liner, because when the variable overflows today, the correct
behavior would be for control to break out of the loop that declares
the overflowing variable "j", and, I don't see any similar problem in
other heap maintenance routines. It's a very isolated problem.

I could write a patch.

Just to avoid being forgotten, I attach a trivial patch against 9.5
branch as well as have created a commitfest submission
https://commitfest.postgresql.org/14/1189/

I don't like s/int/int64/g as a fix for this. That loop is probably
a hot spot, and this fix is going to be expensive on any machine where
int64 isn't the native word width. How about something like this instead:

-		int			j = 2 * i + 1;
+		int			j;

+		if (unlikely(i > INT_MAX / 2))
+			break;		/* if j would overflow, we're done */
+		j = 2 * i + 1;
		if (j >= n)
			break;

regards, tom lane

--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs

On 2017-07-05 18:03:56 -0400, Tom Lane wrote:

Sergey Koposov <skoposov@cmu.edu> writes:

On Thu, 2017-06-29 at 10:00 -0700, Peter Geoghegan wrote:

This is an oversight in commit 263865a. The fix is to use a variable
that won't overflow in tuplesort_heap_siftup() -- this is probably a
one-liner, because when the variable overflows today, the correct
behavior would be for control to break out of the loop that declares
the overflowing variable "j", and, I don't see any similar problem in
other heap maintenance routines. It's a very isolated problem.

I could write a patch.

Just to avoid being forgotten, I attach a trivial patch against 9.5
branch as well as have created a commitfest submission
https://commitfest.postgresql.org/14/1189/

I don't like s/int/int64/g as a fix for this. That loop is probably
a hot spot, and this fix is going to be expensive on any machine where
int64 isn't the native word width. How about something like this instead:

-		int			j = 2 * i + 1;
+		int			j;

+		if (unlikely(i > INT_MAX / 2))
+			break;		/* if j would overflow, we're done */
+		j = 2 * i + 1;
if (j >= n)
break;

Isn't an added conditional likely going to be more costly than the
s/32/64/ bit calculations on the majority of machines pg runs on? I'm
quite doubtful that it's worth catering for the few cases where that's
really slow.

- Andres

--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs

On Wed, Jul 5, 2017 at 3:14 PM, Andres Freund <andres@anarazel.de> wrote:

Isn't an added conditional likely going to be more costly than the
s/32/64/ bit calculations on the majority of machines pg runs on? I'm
quite doubtful that it's worth catering for the few cases where that's
really slow.

I doubt that myself. Especially prior to Postgres 10, where merging
will have tuplesort_heap_insert() as the bottleneck.

In Postgres 10, tuplesort external sort run merging became much faster
following commit 24598337c8d. It might be noticeable if such a machine
were using Postgres 10 already, and really had something to lose, but
that seems very unlikely.

--
Peter Geoghegan

--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs

On Wed, Jul 5, 2017 at 3:19 PM, Peter Geoghegan <pg@bowt.ie> wrote:

I doubt that myself. Especially prior to Postgres 10, where merging
will have tuplesort_heap_insert() as the bottleneck.

BTW, I do of course understand that the reporter isn't talking about
merging, but rather is talking about run generation using replacement
selection. Replacement selection is more or less obsolete, and was
more or less removed in Postgres 9.6. I don't think that its needs
should be given much weight here; this is mostly about merging.

I wanted to make merging use its own dedicated function within the
patch that became 24598337c8d, and leave tuplesort_heap_insert() and
tuplesort_heap_siftup() as things used only by replacement selection +
Top-N heap sort, but Heikki overruled me on that. He might have been
right about that. I'm not sure, and never took the time to follow up
with it.

tuplesort_heap_replace_top(), which is where this logic lives now that
tuplesort_heap_siftup() was broken up, certainly is a red-hot code
path where individual instructions could matter. I've looked at the
disassembly of the function in the past, which is rare for me.

--
Peter Geoghegan

--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs

On 07/06/2017 01:14 AM, Andres Freund wrote:

On 2017-07-05 18:03:56 -0400, Tom Lane wrote:

I don't like s/int/int64/g as a fix for this. That loop is probably
a hot spot, and this fix is going to be expensive on any machine where
int64 isn't the native word width. How about something like this instead:

-		int			j = 2 * i + 1;
+		int			j;

+		if (unlikely(i > INT_MAX / 2))
+			break;		/* if j would overflow, we're done */
+		j = 2 * i + 1;
if (j >= n)
break;

Isn't an added conditional likely going to be more costly than the
s/32/64/ bit calculations on the majority of machines pg runs on? I'm
quite doubtful that it's worth catering for the few cases where that's
really slow.

Another option to use "unsigned int", on the assumption that UINT_MAX >=
INT_MAX * 2 + 1. And to eliminate that assumption, we can use (UINT_MAX
- 1) / 2 as the maximum size of the memtuples array, rather than INT_MAX.

- Heikki

--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs

Heikki Linnakangas <hlinnaka@iki.fi> writes:

On 07/06/2017 01:14 AM, Andres Freund wrote:

On 2017-07-05 18:03:56 -0400, Tom Lane wrote:

I don't like s/int/int64/g as a fix for this. That loop is probably
a hot spot, and this fix is going to be expensive on any machine where
int64 isn't the native word width. How about something like this instead:

Another option to use "unsigned int", on the assumption that UINT_MAX >=
INT_MAX * 2 + 1.

Ah, that seems like a fine idea.

And to eliminate that assumption, we can use (UINT_MAX
- 1) / 2 as the maximum size of the memtuples array, rather than INT_MAX.

Uh ... what assumption? That's certainly true on any twos-complement
machine. Besides, if you're worried about hypothetical portability
issues, I'm not sure it's any better to assume that (UINT_MAX - 1) / 2
fits in a signed int.

regards, tom lane

--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs

On Wed, Jul 12, 2017 at 8:42 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Another option to use "unsigned int", on the assumption that UINT_MAX >=
INT_MAX * 2 + 1.

Ah, that seems like a fine idea.

Works for me.

--
Peter Geoghegan

--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs

Peter Geoghegan <pg@bowt.ie> writes:

On Wed, Jul 12, 2017 at 8:42 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Another option to use "unsigned int", on the assumption that UINT_MAX >=
INT_MAX * 2 + 1.

Ah, that seems like a fine idea.

Works for me.

I'll go make it so, unless Heikki's already on it?

regards, tom lane

--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs

On 07/12/2017 07:14 PM, Tom Lane wrote:

Peter Geoghegan <pg@bowt.ie> writes:

On Wed, Jul 12, 2017 at 8:42 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Another option to use "unsigned int", on the assumption that UINT_MAX >=
INT_MAX * 2 + 1.

Ah, that seems like a fine idea.

Works for me.

I'll go make it so, unless Heikki's already on it?

I'm not. Thanks!

And to eliminate that assumption, we can use (UINT_MAX
- 1) / 2 as the maximum size of the memtuples array, rather than INT_MAX.

Uh ... what assumption? That's certainly true on any twos-complement
machine. Besides, if you're worried about hypothetical portability
issues, ...

Right, it's a hypothetical portability issue. The assumption we're
making is that UINT_MAX >= INT_MAX * 2 + 1. I'm not aware of any system
where it's not true, but I don't know what the C standards say about that.

... I'm not sure it's any better to assume that (UINT_MAX - 1) / 2
fits in a signed int.

Well, you could do Min(INT_MAX, (UINT_MAX - 1 / 2). Or just add a
StaticAssertion for it. Or just note in a comment that we're making that
assumption.

- Heikki

--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs

Heikki Linnakangas <hlinnaka@iki.fi> writes:

On 07/12/2017 07:14 PM, Tom Lane wrote:

Uh ... what assumption? That's certainly true on any twos-complement
machine. Besides, if you're worried about hypothetical portability
issues, ...

Right, it's a hypothetical portability issue. The assumption we're
making is that UINT_MAX >= INT_MAX * 2 + 1. I'm not aware of any system
where it's not true, but I don't know what the C standards say about that.

Actually, at the top of the loop we have i < n <= INT_MAX, so the
assumption only needs to be UINT_MAX >= INT_MAX * 2 - 1.

My copy of the C99 draft says, among other things

6.2.5 Types

[#6] For each of the signed integer types, there is a
corresponding (but different) unsigned integer type
(designated with the keyword unsigned) that uses the same
amount of storage (including sign information) and has the
same alignment requirements.

[#9] The range of nonnegative values of a signed integer
type is a subrange of the corresponding unsigned integer
type, and the representation of the same value in each type
is the same.

6.2.6.2 Integer types

[#1] For unsigned integer types other than unsigned char,
the bits of the object representation shall be divided into
two groups: value bits and padding bits (there need not be
any of the latter). If there are N value bits, each bit
shall represent a different power of 2 between 1 and 2N-1,
so that objects of that type shall be capable of
representing values from 0 to 2N-1 using a pure binary
representation; this shall be known as the value
representation. The values of any padding bits are
unspecified.37)

[#2] For signed integer types, the bits of the object
representation shall be divided into three groups: value
bits, padding bits, and the sign bit. There need not be any
padding bits; there shall be exactly one sign bit. Each bit
that is a value bit shall have the same value as the same
bit in the object representation of the corresponding
unsigned type (if there are M value bits in the signed type
and N in the unsigned type, then M<=N). If the sign bit is
zero, it shall not affect the resulting value. If the sign
bit is one, then the value shall be modified in one of the
following ways:

-- the corresponding value with sign bit 0 is negated;

-- the sign bit has the value -2N;

-- the sign bit has the value 1-2N.

[#3] The values of any padding bits are unspecified.

Both 6.2.5.9 and 6.2.6.2.2 constrain INT_MAX to be <= UINT_MAX.
In principle, you could have a conforming implementation in which
they were the same, and the sign bit of a signed integer was treated
as a useless padding bit in an unsigned integer. I can't imagine
anyone actually building it that way though; what would be the point?
But as long as there aren't wasted bits in an unsigned int, these
rules require INT_MAX to be <= UINT_MAX/2, AFAICS.

regards, tom lane

--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs

On Wed, Jul 12, 2017 at 9:20 AM, Heikki Linnakangas <hlinnaka@iki.fi> wrote:

Uh ... what assumption? That's certainly true on any twos-complement
machine. Besides, if you're worried about hypothetical portability
issues, ...

Right, it's a hypothetical portability issue. The assumption we're making is
that UINT_MAX >= INT_MAX * 2 + 1. I'm not aware of any system where it's not
true, but I don't know what the C standards say about that.

Intuitively, it seems very likely to be true, since two's complement
arithmetic is already assumed by Postgres, and addition and
multiplication work the same way at the instruction level for unsigned
and signed (two's complement) integers. In order for this to break,
int and unsigned int would have to have different widths.

Well, you could do Min(INT_MAX, (UINT_MAX - 1 / 2). Or just add a
StaticAssertion for it. Or just note in a comment that we're making that
assumption.

I like the idea of a StaticAssertion().

--
Peter Geoghegan

--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs