BUG #14722: Segfault in tuplesort_heap_siftup, 32 bit overflow

The following bug has been logged on the website:

Bug reference: 14722
Logged by: Sergey Koposov
Email address: skoposov(at)cmu(dot)edu
PostgreSQL version: 9.5.7
Operating system: Debian 7.11, x86_64
Description:

Hi,

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

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) !

--

Here is the table info:
wsdb=# explain select * from cgonzal.vvv_single_ks_sorted;
QUERY PLAN

---------------------------------------------------------------------------------------
Seq Scan on vvv_single_ks_sorted (cost=0.00..968967342.13 rows=43362626913
width=72)
(1 row)

wsdb=# \d cgonzal.vvv_single_ks_sorted
Table "cgonzal.vvv_single_ks_sorted"
Column | Type | Modifiers
---------+------------------+-----------
objid | bigint |
ra | double precision |
dec | double precision |
x | real |
y | real |
chip | integer |
mag | real |
e_mag | real |
class | integer |
frameid | bigint |
zp | double precision |
obj_id | bigint |

--------

Here is the gdb full stacktrace:
(gdb) bt full
#0 0x0000000000914cf8 in tuplesort_heap_siftup (state=0x23503f8,
checkIndex=1 '\001') at tuplesort.c:3014
j = -1879048193
memtuples = 0x7fb283aa1048
tuple = 0x7fba03aa0fd0
i = 1207959551
n = 1342177275
#1 0x000000000091430a in dumptuples (state=0x23503f8, alltuples=0 '\000')
at tuplesort.c:2648
__func__ = "dumptuples"
#2 0x00000000009120a3 in puttuple_common (state=0x23503f8,
tuple=0x7ffe420fefc0) at tuplesort.c:1468
__func__ = "puttuple_common"
#3 0x0000000000911d85 in tuplesort_putindextuplevalues (state=0x23503f8,
rel=0x7fd040f3b8e0, self=0x234ba34, values=0x7ffe420ff360,
isnull=0x7ffe420ff340 "") at tuplesort.c:1321
oldcontext = 0x23340b8
stup = {tuple = 0x7fbf040f6ae8, datum1 = 4710889527840951089,
isnull1 = 0 '\000', tupindex = 0}
original = 4710889527840951089
tuple = 0x7fbf040f6ae8
#4 0x00000000004d26dd in _bt_spool (btspool=0x234cba0, self=0x234ba34,
values=0x7ffe420ff360, isnull=0x7ffe420ff340 "") at nbtsort.c:192
No locals.
#5 0x00000000004cba67 in btbuildCallback (index=0x7fd040f3b8e0,
htup=0x234ba30, values=0x7ffe420ff360, isnull=0x7ffe420ff340 "",
tupleIsAlive=1 '\001', state=0x7ffe420ff550) at nbtree.c:179
buildstate = 0x7ffe420ff550
#6 0x0000000000525d8e in IndexBuildHeapRangeScan
(heapRelation=0x7fd040f32f78, indexRelation=0x7fd040f3b8e0,
indexInfo=0x2348308,
allow_sync=1 '\001', anyvisible=0 '\000', start_blockno=0,
numblocks=4294967295, callback=0x4cba0a <btbuildCallback>,
callback_state=0x7ffe420ff550) at index.c:2591
tupleIsAlive = 1 '\001'
is_system_catalog = 0 '\000'
checking_uniqueness = 0 '\000'
scan = 0x234b9e8
heapTuple = 0x234ba30
values = {4710889527840951089, 9472000, 36863416, 1089733344,
140730006762416, 9195433, 140730006762448, 140532419658520, 140730006762528,

140532419658464, 140730006762448, 9261444, 1976, 140532419658520,
4999282, 128, 36962306, 17179869199, 140730006762544, 9473335, 37029384,
37020152, 18288211008, 9498080, 37029368, 37020152,
140730006762592, 9478487, 140730006762624, 37029384, 64, 37020152}
isnull =
"\000\314\366(at)\320\177\000\000'Z\216\000\000\000\000\000\030\003\364(at)\320\177\000\000\310A3\002\000\000\000"
reltuples = 1342177279
predicate = 0x0
slot = 0x2348e08
estate = 0x2358448
---Type <return> to continue, or q <return> to quit---
econtext = 0x2358558
snapshot = 0xd366e0
OldestXmin = 1148880660
root_blkno = 16570089
root_offsets = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33,
34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68,

69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 0 <repeats 210
times>}
__func__ = "IndexBuildHeapRangeScan"
#7 0x0000000000525556 in IndexBuildHeapScan (heapRelation=0x7fd040f32f78,
indexRelation=0x7fd040f3b8e0, indexInfo=0x2348308, allow_sync=1 '\001',
callback=0x4cba0a <btbuildCallback>, callback_state=0x7ffe420ff550) at
index.c:2162
No locals.
#8 0x00000000004cb979 in btbuild (fcinfo=0x7ffe420ff5d0) at nbtree.c:121
heap = 0x7fd040f32f78
index = 0x7fd040f3b8e0
indexInfo = 0x2348308
result = 0x234be28
reltuples = 6.9529861680561111e-310
buildstate = {isUnique = 0 '\000', haveDead = 0 '\000', heapRel =
0x7fd040f32f78, spool = 0x234cba0, spool2 = 0x0, indtuples = 1342177278}
__func__ = "btbuild"
#9 0x00000000008e8a13 in OidFunctionCall3Coll (functionId=338, collation=0,
arg1=140532419604344, arg2=140532419639520, arg3=36995848) at fmgr.c:1649
flinfo = {fn_addr = 0x4cb854 <btbuild>, fn_oid = 338, fn_nargs = 3,
fn_strict = 1 '\001', fn_retset = 0 '\000', fn_stats = 2 '\002',
fn_extra = 0x0, fn_mcxt = 0x23340b8, fn_expr = 0x0}
fcinfo = {flinfo = 0x7ffe420ff980, context = 0x0, resultinfo = 0x0,
fncollation = 0, isnull = 0 '\000', nargs = 3, arg = {140532419604344,
140532419639520, 36995848, 140532419656080, 68756505104, 128,
13, 17179869199, 140730006763184, 9472170, 128, 36023424, 140730006763152,

17189342519, 140532419627520, 36913336, 36023424, 37017440,
37017424, 36913336, 140730006763200, 512, 1108342496, 25769803839,
140730006763248, 9473335, 140532419653944, 36023424,
26878146304, 6912158, 140532419653928, 36023424, 140730006763296, 9478487,

140730006763296, 140532419653944, 0, 36023424, 140730006763328,
9230214, 672953898141726960, 140532419653944, 140730006763792, 9231509,
10999411261461, 140532419639520, 70458938492543, 156684292, 0,
18446744069414584320, 65536, 0, 140532419654472, 140532419654744,
672953910093598724, 16405, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
140532419656112, 140532419656056, 140532419657096, 37019880, 37027816,
37028344,
37028368, 37028392, 37028416, 37028584, 0, 0, 0, 0, 0, 0,
37028560, 0, 0, 0, 0, 36491160, 0, 0, 0, 13854912, 140532419640320,
8626848200,
36633224, 8589934592, 140730006763808, 6798261,
672953909936914436, 13854912},
argnull =
"\000\000\000\000\000\000\000\000\240h\323\000\000\000\000\000`\371\017B\376\177\000\000\032\274g\000\000\000\000\000\240h\323\000\
000\000\000\000\023\000\000\000\016\000\000\000\300\371\017B\376\177\000\000\aۍ",
'\000' <repeats 13 times>, "hD\224\000\000\000\000\000p<\224\000\000\
000\000\000\331\a\000\000\016\000\000\000\260\371\017B"}
result = 42949672962
__func__ = "OidFunctionCall3Coll"
#10 0x00000000005252a3 in index_build (heapRelation=0x7fd040f32f78,
indexRelation=0x7fd040f3b8e0, indexInfo=0x2348308, isprimary=0 '\000',
---Type <return> to continue, or q <return> to quit---
isreindex=0 '\000') at index.c:2025
procedure = 338
stats = 0x234cfec
save_userid = 10
save_sec_context = 0
save_nestlevel = 2
__func__ = "index_build"
#11 0x0000000000523f98 in index_create (heapRelation=0x7fd040f32f78,
indexRelationName=0x234b8e8 "vvv_single_ks_sorted_q3c_ang2ipix_idx",
indexRelationId=156684292, relFileNode=0, indexInfo=0x2348308,
indexColNames=0x234b638, accessMethodObjectId=403, tableSpaceId=0,
collationObjectId=0x234bdf8, classObjectId=0x234be10,
coloptions=0x234be28, reloptions=0, isprimary=0 '\000', isconstraint=0
'\000',
deferrable=0 '\000', initdeferred=0 '\000', allow_system_table_mods=0
'\000', skip_build=0 '\000', concurrent=0 '\000', is_internal=0 '\000',
if_not_exists=0 '\000') at index.c:1100
heapRelationId = 156673270
pg_class = 0x7fd040f81208
indexRelation = 0x7fd040f3b8e0
indexTupDesc = 0x23486c8
shared_relation = 0 '\000'
mapped_relation = 0 '\000'
is_exclusion = 0 '\000'
[120/270]
namespaceId = 16842
i = 1
relpersistence = 112 'p'
__func__ = "index_create"
#12 0x00000000005e9d27 in DefineIndex (relationId=156673270, stmt=0x23485f8,
indexRelationId=0, is_alter_table=0 '\000', check_rights=1 '\001',
skip_build=0 '\000', quiet=0 '\000') at indexcmds.c:607
indexRelationName = 0x234b8e8
"vvv_single_ks_sorted_q3c_ang2ipix_idx"
accessMethodName = 0x2348930 "btree"
typeObjectId = 0x234b780
collationObjectId = 0x234bdf8
classObjectId = 0x234be10
accessMethodId = 403
namespaceId = 16842
tablespaceId = 0
indexColNames = 0x234b638
rel = 0x7fd040f32f78
indexRelation = 0x23340b8
tuple = 0x7fd040f39b30
---Type <return> to continue, or q <return> to quit---
accessMethodForm = 0x7fd040f39ba8
amcanorder = 1 '\001'
amoptions = 2785
reloptions = 0
coloptions = 0x234be28
indexInfo = 0x2348308
numberOfAttributes = 1
limitXmin = 0
old_snapshots = 0x7fd040f32f78
address = {classId = 36997560, objectId = 0, objectSubId =
36995848}
n_old_snapshots = 0
heaprelid = {relId = 1108343952, dbId = 32766}
heaplocktag = {locktag_field1 = 4657712, locktag_field2 = 0,
locktag_field3 = 1108347536, locktag_field4 = 32766, locktag_type = 0
'\000',
locktag_lockmethodid = 0 '\000'}
lockmode = 5
snapshot = 0x2348308
i = 0
__func__ = "DefineIndex"
#13 0x00000000007ab5ec in ProcessUtilitySlow (parsetree=0x230c138,
queryString=0x230b268 "create index on cgonzal.vvv_single_ks_sorted
(q3c_ang2ipix(ra,dec));", context=PROCESS_UTILITY_TOPLEVEL, params=0x0,
dest=0x230c4d8, completionTag=0x7ffe42100420 "") at utility.c:1259
stmt = 0x23485f8
relid = 156673270
lockmode = 5
save_exception_stack = 0x7ffe421002e0
save_context_stack = 0x0
local_sigjmp_buf = {{__jmpbuf = {0, 8080871256505359237, 4657712,
140730006768272, 0, 0, 8080871325866564485, -8081285932728411259},
__mask_was_saved = 0, __saved_mask = {__val = {64, 36632424,
140730006765464, 140730006765472, 13829056, 8192, 36973152, 4657712, 5,
140730006765328, 9476353, 64, 0, 36973248, 13829056,
64}}}}
isTopLevel = 1 '\001'
isCompleteQuery = 1 '\001'
needCleanup = 0 '\000'
commandCollected = 0 '\000'
address = {classId = 0, objectId = 0, objectSubId = 13829056}
secondaryObject = {classId = 0, objectId = 0, objectSubId = 0}
__func__ = "ProcessUtilitySlow"
#14 0x00000000007aaa16 in standard_ProcessUtility (parsetree=0x230c138,
---Type <return> to continue, or q <return> to quit---
queryString=0x230b268 "create index on cgonzal.vvv_single_ks_sorted
(q3c_ang2ipix(ra,dec));", context=PROCESS_UTILITY_TOPLEVEL, params=0x0,
dest=0x230c4d8, completionTag=0x7ffe42100420 "") at utility.c:892
isTopLevel = 1 '\001'
__func__ = "standard_ProcessUtility"
#15 0x00000000007a9beb in ProcessUtility (parsetree=0x230c138,
queryString=0x230b268 "create index on cgonzal.vvv_single_ks_sorted
(q3c_ang2ipix(ra,dec));", context=PROCESS_UTILITY_TOPLEVEL, params=0x0,
dest=0x230c4d8, completionTag=0x7ffe42100420 "") at utility.c:334
No locals.
#16 0x00000000007a8e07 in PortalRunUtility (portal=0x2278798,
utilityStmt=0x230c138, isTopLevel=1 '\001', dest=0x230c4d8,
completionTag=0x7ffe42100420 "") at pquery.c:1183
active_snapshot_set = 1 '\001'
__func__ = "PortalRunUtility"
#17 0x00000000007a8fae in PortalRunMulti (portal=0x2278798, isTopLevel=1
'\001', dest=0x230c4d8, altdest=0x230c4d8,
completionTag=0x7ffe4210042[50/270]
at pquery.c:1314
stmt = 0x230c138
active_snapshot_set = 0 '\000'
stmtlist_item = 0x230c488
#18 0x00000000007a85c2 in PortalRun (portal=0x2278798,
count=9223372036854775807, isTopLevel=1 '\001', dest=0x230c4d8,
altdest=0x230c4d8,
completionTag=0x7ffe42100420 "") at pquery.c:812
save_exception_stack = 0x7ffe42100560
save_context_stack = 0x0
local_sigjmp_buf = {{__jmpbuf = {0, 8080871256352267141, 4657712,
140730006768272, 0, 0, 8080871256442444677, -8081285932000961659},
__mask_was_saved = 0, __saved_mask = {__val = {3432, 9356099,
36745776, 13, 0, 140730006766512, 9477730, 36624768, 88, 0, 36750640, 88,
9359107, 36750552, 36750640, 0}}}}
result = 0 '\000'
nprocessed = 32766
saveTopTransactionResourceOwner = 0x22ef878
saveTopTransactionContext = 0x22ef768
saveActivePortal = 0x0
saveResourceOwner = 0x22ef878
savePortalContext = 0x0
saveMemoryContext = 0x22ef768
__func__ = "PortalRun"
#19 0x00000000007a2ac3 in exec_simple_query (query_string=0x230b268 "create
index on cgonzal.vvv_single_ks_sorted (q3c_ang2ipix(ra,dec));")
[29/270]
at postgres.c:1104
parsetree = 0x230c138
portal = 0x2278798
---Type <return> to continue, or q <return> to quit---
snapshot_set = 0 '\000'
commandTag = 0xa4fc46 "CREATE INDEX"
completionTag =
"\000\004\020B\376\177\000\000\243b\217\000\000\000\000\000p\004\020B\376\177\000\000\000
\000\000D\000\000\000p\004\020B\376\1
77\000\000\252i\217\000\000\000\000\000\002\000\000\000\002\000\000\000J\000\000\000\000\000\000"
querytree_list = 0x230c458
plantree_list = 0x230c4a8
receiver = 0x230c4d8
format = 0
dest = DestRemote
oldcontext = 0x22ef768
parsetree_list = 0x230c1e8
parsetree_item = 0x230c1c8
save_log_statement_stats = 0 '\000'
was_logged = 0 '\000'
isTopLevel = 1 '\001'
msec_str =
"\260\004\020B\376\177\000\000\177:\217\000\000\000\000\000\006\000\000\000D\000\000\000h\262\060\002\000\000\000"
__func__ = "exec_simple_query"
#20 0x00000000007a69b2 in PostgresMain (argc=1, argv=0x225a220,
dbname=0x225a0d8 "wsdb", username=0x225a0b8 "postgres") at postgres.c:4051
query_string = 0x230b268 "create index on
cgonzal.vvv_single_ks_sorted (q3c_ang2ipix(ra,dec));"
firstchar = 81
input_message = {data = 0x230b268 "create index on
cgonzal.vvv_single_ks_sorted (q3c_ang2ipix(ra,dec));", len = 69, maxlen =
1024,
cursor = 69}
local_sigjmp_buf = {{__jmpbuf = {0, 8080871256293546885, 4657712,
140730006768272, 0, 0, 8080871256322907013, -8081285930984760443},
__mask_was_saved = 1, __saved_mask = {__val = {0, 36017624, 0,
0, 0, 0, 1024, 0, 30064771199, 140730006767152, 9473335, 36150008,
36017624, 30064771088, 36150008, 36149992}}}}
send_ready_for_query = 0 '\000'
__func__ = "PostgresMain"
#21 0x0000000000732973 in BackendRun (port=0x22a3050) at postmaster.c:4255
av = 0x225a220
maxac = 2
ac = 1
secs = 552065929
usecs = 554900
i = 1
__func__ = "BackendRun"
#22 0x0000000000732106 in BackendStartup (port=0x22a3050) at
postmaster.c:3929
bn = 0x22a3230
---Type <return> to continue, or q <return> to quit---
pid = 0
__func__ = "BackendStartup"
#23 0x000000000072ea84 in ServerLoop () at postmaster.c:1699
port = 0x22a3050
i = 4
rmask = {fds_bits = {128, 0 <repeats 15 times>}}
selres = 1
now = 1498750719
readmask = {fds_bits = {248, 0 <repeats 15 times>}}
nSockets = 8
last_lockfile_recheck_time = 1498750679
last_touch_time = 1498750679
__func__ = "ServerLoop"
#24 0x000000000072e100 in PostmasterMain (argc=3, argv=0x2259310) at
postmaster.c:1307
opt = -1
status = 0
userDoption = 0x227ad40 "/mnt/bigdata/pgdata9.5"
listen_addr_saved = 1 '\001'
i = 64
output_config_variable = 0x0
__func__ = "PostmasterMain"
#25 0x000000000068ecda in main (argc=3, argv=0x2259310) at main.c:228
do_check_root = 1 '\001'

----

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.

Regards,
Sergey Koposov