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@cmu.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@\320\177\000\000'Z\216\000\000\000\000\000\030\003\364@\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