libstdc++/26: red black tree crashes after 128 inserts

[jaten at accessone dot com]

>Number:         26
>Category:       libstdc++
>Synopsis:       red black tree crashes after 128 inserts
>Confidential:   no
>Severity:       critical
>Priority:       high
>Responsible:    unassigned
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Mon Jan 17 20:07:00 PST 2000
>Closed-Date:
>Last-Modified:
>Originator:     Jason Aten (jaten@accessone.com)
>Release:        libstdc++.so.2.9.0
>Organization:
>Environment:

>Description:
on line 232 of stl_tree.h
  x->left = y->right;

y can be 0x0 and so asking fro ->right gives us:

Program received signal SIGSEGV, Segmentation fault.
0x7f220 in __rb_tree_rotate_right__FP19__rb_tree_node_baseRP19__rb_tree_node_base (x=0x1bc8e0, root=@0xcbcc4)
    at /home/jaten/local/include/g++/stl_tree.h:232
(gdb) bt
#0  0x7f220 in __rb_tree_rotate_right__FP19__rb_tree_node_baseRP19__rb_tree_node_base (x=0x1bc8e0, root=@0xcbcc4)
    at /home/jaten/local/include/g++/stl_tree.h:232
#1  0x7f128 in __rb_tree_rebalance__FP19__rb_tree_node_baseRP19__rb_tree_node_base (x=0x1bc910, root=@0xcbcc4)
    at /home/jaten/local/include/g++/stl_tree.h:267
#2  0x77298 in __insert__t7rb_tree5ZdZdZt8identity1ZdZt4less1ZdZt24__default_alloc_template2b0i0P19__rb_tree_node_baseT1RCd (
    this=0xeeb055c0, x_=0x0, y_=0x1bcaf0, v=@0x239ce0) at /home/jaten/local/include/g++/stl_tree.h:703
#3  0x77578 in rb_tree<double, double, identity<double>, less<double>, __default_alloc_template<false, 0> >::insert_unique (
    this=0xeeb055c0, v=@0x239ce0) at /home/jaten/local/include/g++/stl_tree.h:741
#4  0x7d374 in set<double, less<double>, __default_alloc_template<false, 0> >::insert (this=0xeeb055c0, x=@0x239ce0)
    at /home/jaten/local/include/g++/stl_set.h:116
#5  0x24618 in coreng_impl::correlateGene (this=0xbbcf0, geneID=12529, warehouseID=1, pValueThreshold=0.01, 
    thePValueOperator=org_rosetta_compute_coreng_intersectionOp, targetGeneIDs=@0xeeb059a0, refineExperimentIDs=@0xeeb05990, 
    excludedPairs=@0xeeb05978, maxPositivelyCorrelatedPointCount=30, maxNegativelyCorrelatedPointCount=0, 
    theProgressListener=0xbf038, options=0xb9000 "") at coreng_impl.cpp:1991
#6  0x3bc30 in org_rosetta_compute_coreng_CorrelationEngine_skel::_OB_op_correlateGene (this=0xbbe80, _ob_buf=@0xbeca8, 
    _ob_sw=false, _ob_offIn=60, _ob_offOut=24) at combo_skel.cpp:1236
#7  0x3ce54 in org_rosetta_compute_coreng_CorrelationEngine_skel::_OB_dispatch (this=0xbbe80, _ob_op=0xb6b78 "correlateGene", 
    _ob_buf=@0xbeca8, _ob_sw=false, _ob_offIn=60, _ob_offOut=24) at combo_skel.cpp:1424
#8  0xef5e402c in CORBA_BOA::_OB_dispatch (this=0xba988, key=@0xeeb05bd4, op=0xb6b78 "correlateGene", buf=@0xbeca8, sw=false, 
    offIn=60, offOut=24) at BOA.cpp:716
#9  0xef632aac in OBGIOPServerWorker::dispatchRequest (this=0xbc870, buf=@0xbeca8, swap=false) at GIOPServerWorker.cpp:418
#10 0xef67ba48 in OBGIOPServerWorkerThreaded::Dispatcher::run () from /home/jaten/local/lib/libOB.so
#11 0xef3c0c6c in JTCThread::_JTC_startThreadHook (this=0xbeb78) at Thread.cpp:1234
#12 0xef3bc458 in threadStart (arg=0xbeb78) at Thread.cpp:196
(gdb) up 5
#5  0x24618 in coreng_impl::correlateGene (this=0xbbcf0, geneID=12529, warehouseID=1, pValueThreshold=0.01, 
    thePValueOperator=org_rosetta_compute_coreng_intersectionOp, targetGeneIDs=@0xeeb059a0, refineExperimentIDs=@0xeeb05990, 
    excludedPairs=@0xeeb05978, maxPositivelyCorrelatedPointCount=30, maxNegativelyCorrelatedPointCount=0, 
    theProgressListener=0xbf038, options=0xb9000 "") at coreng_impl.cpp:1991
(gdb) p i
$1 = 128
(gdb) down
#4  0x7d374 in set<double, less<double>, __default_alloc_template<false, 0> >::insert (this=0xeeb055c0, x=@0x239ce0)
    at /home/jaten/local/include/g++/stl_set.h:116
(gdb) p x
$2 = (org_rosetta_compute_warehouse_EGID &) @0x239ce0: 10086
(gdb) down 5
#0  0x7f220 in __rb_tree_rotate_right__FP19__rb_tree_node_baseRP19__rb_tree_node_base (x=0x1bc8e0, root=@0xcbcc4)
    at /home/jaten/local/include/g++/stl_tree.h:232
(gdb) p x
$3 = (__rb_tree_node_base *) 0x1bc8e0
(gdb) p y
$4 = (__rb_tree_node_base *) 0x0
(gdb) up
#1  0x7f128 in __rb_tree_rebalance__FP19__rb_tree_node_baseRP19__rb_tree_node_base (x=0x1bc910, root=@0xcbcc4)
    at /home/jaten/local/include/g++/stl_tree.h:267
(gdb) p root
$5 = (__rb_tree_node_base *&) @0xcbcc4: 0xcc248
(gdb) p x->parent
$6 = (__rb_tree_node_base *) 0xd05a0
(gdb) p x->parent->parent
$7 = (__rb_tree_node_base *) 0xd0570
(gdb) down
#0  0x7f220 in __rb_tree_rotate_right__FP19__rb_tree_node_baseRP19__rb_tree_node_base (x=0x1bc8e0, root=@0xcbcc4)
    at /home/jaten/local/include/g++/stl_tree.h:232
(gdb) p x
$8 = (__rb_tree_node_base *) 0x1bc8e0
(gdb) p root
$9 = (__rb_tree_node_base *&) @0xcbcc4: 0xcc248
(gdb) p x->left
$10 = (__rb_tree_node_base *) 0x0
(gdb) up 5
#5  0x24618 in coreng_impl::correlateGene (this=0xbbcf0, geneID=12529, warehouseID=1, pValueThreshold=0.01, 
    thePValueOperator=org_rosetta_compute_coreng_intersectionOp, targetGeneIDs=@0xeeb059a0, refineExperimentIDs=@0xeeb05990, 
    excludedPairs=@0xeeb05978, maxPositivelyCorrelatedPointCount=30, maxNegativelyCorrelatedPointCount=0, 
    theProgressListener=0xbf038, options=0xb9000 "") at coreng_impl.cpp:1991
(gdb)  p i
$11 = 128
(gdb) list
1986	   // ==============================================
1987	   egid_set geneSet;
1988	
1989	   for (i = 0; i < num_allgenes; i++)
1990	   {
1991	      geneSet.insert((*p_allgenes)[i]);
1992	   }
1993	
1994	   // ============================================
1995	   // Now locate our query 
(gdb) 
>How-To-Repeat:
intermittant problem, hard to reproduce.
>Fix:

>Release-Note:
>Audit-Trail:
>Unformatted: