search

benedictpaten / pinchesAndCacti

Library for constructing pinch graphs and cactus graphs
MIT License
11 stars 4 forks source link

integer overflow causes pinch to hang and allocate memory forever #4

Open joelarmstrong opened 9 years ago

joelarmstrong commented 9 years ago

Can't possibly matter for any realistic use case, but may as well document it in case it ever matters. When picking random pinches from the default test set I noticed that one seems to keep splitting segments forever. Presumably this is because of the nearly 2^63-base long thread. Backtrace:

#0  0x00000000004325f8 in avl_find (tree=0x6628f0, item=0x23d67f920) at impl/avl.c:71
#1  0x000000000041fbd9 in stSortedSet_search (sortedSet=0x6628b0, object=0x23d67f920) at impl/sonLibSortedSet.c:126
#2  stSortedSet_insert (sortedSet=0x6628b0, object=0x23d67f920) at impl/sonLibSortedSet.c:117
#3  0x0000000000414a5f in stPinchSegment_splitP (segment=0x23c995540, leftBlockLength=203373893722)
    at impl/stPinchGraphs.c:256
#4  0x0000000000414c90 in stPinchSegment_split (segment=0x23c995540, leftSideOfSplitPoint=4252648802076727205)
    at impl/stPinchGraphs.c:297
#5  0x0000000000415523 in stPinchThread_pinchTrimNegative (segment=0x17ec5ed0, length=203373893722)
    at impl/stPinchGraphs.c:473
#6  0x00000000004155d3 in stPinchThread_pinchNegativeP (segment1=0x1b1e236a0, segment2=0x17ec5ed0, 
    start1=7818508918895673344, start2=3181537203931054080, length=1071111801519566848) at impl/stPinchGraphs.c:486
#7  0x0000000000415800 in stPinchThread_pinchNegative (thread1=0x662880, thread2=0x662880, start1=7818508918895673344, 
    start2=3181537203931054080, length=1170592771588616192) at impl/stPinchGraphs.c:517
#8  0x0000000000415a28 in stPinchThread_pinch (thread1=0x662880, thread2=0x662880, start1=7818508918895673344, 
    start2=3181537203931054080, length=1170592771588616192, strand2=false) at impl/stPinchGraphs.c:540
#9  0x000000000040ea4b in testStPinchUndo (testCase=0x6625a0) at tests/stPinchGraphsTest.c:1277
#10 0x0000000000436601 in CuTestRun (tc=0x6625a0) at CuTest.c:143
#11 0x0000000000436ca6 in CuSuiteRun (testSuite=0x65e560) at CuTest.c:290
#12 0x0000000000401741 in stPinchesAndCactiRunAllTests () at tests/allTests.c:21
#13 0x00000000004017b8 in main (argc=2, argv=0x7fffffffd6a8) at tests/allTests.c:32

And a massive number of segments are in the thread:

(gdb) p stSortedSet_size(segment->thread->segments)
$15 = 85833176

from only 40 or so pinches on the graph total.

benedictpaten commented 9 years ago

Oops, I will fix.

On Fri, Apr 10, 2015 at 11:14 PM, Joel Armstrong notifications@github.com wrote:

Can't possibly matter for any realistic use case, but may as well document it in case it ever matters. When picking random pinches from the default test set I noticed that one seems to keep splitting segments forever. Presumably this is because of the nearly 2^63-base long thread. Backtrace:

0 0x00000000004325f8 in avl_find (tree=0x6628f0, item=0x23d67f920) at impl/avl.c:71

1 0x000000000041fbd9 in stSortedSet_search (sortedSet=0x6628b0, object=0x23d67f920) at impl/sonLibSortedSet.c:126

2 stSortedSet_insert (sortedSet=0x6628b0, object=0x23d67f920) at impl/sonLibSortedSet.c:117

3 0x0000000000414a5f in stPinchSegment_splitP (segment=0x23c995540, leftBlockLength=203373893722)

at impl/stPinchGraphs.c:256

4 0x0000000000414c90 in stPinchSegment_split (segment=0x23c995540, leftSideOfSplitPoint=4252648802076727205)

at impl/stPinchGraphs.c:297

5 0x0000000000415523 in stPinchThread_pinchTrimNegative (segment=0x17ec5ed0, length=203373893722)

at impl/stPinchGraphs.c:473

6 0x00000000004155d3 in stPinchThread_pinchNegativeP (segment1=0x1b1e236a0, segment2=0x17ec5ed0,

start1=7818508918895673344, start2=3181537203931054080, length=1071111801519566848) at impl/stPinchGraphs.c:486

7 0x0000000000415800 in stPinchThread_pinchNegative (thread1=0x662880, thread2=0x662880, start1=7818508918895673344,

start2=3181537203931054080, length=1170592771588616192) at impl/stPinchGraphs.c:517

8 0x0000000000415a28 in stPinchThread_pinch (thread1=0x662880, thread2=0x662880, start1=7818508918895673344,

start2=3181537203931054080, length=1170592771588616192, strand2=false) at impl/stPinchGraphs.c:540

9 0x000000000040ea4b in testStPinchUndo (testCase=0x6625a0) at tests/stPinchGraphsTest.c:1277

10 0x0000000000436601 in CuTestRun (tc=0x6625a0) at CuTest.c:143

11 0x0000000000436ca6 in CuSuiteRun (testSuite=0x65e560) at CuTest.c:290

12 0x0000000000401741 in stPinchesAndCactiRunAllTests () at tests/allTests.c:21

13 0x00000000004017b8 in main (argc=2, argv=0x7fffffffd6a8) at tests/allTests.c:32

And a massive number of segments are in the thread:

(gdb) p stSortedSet_size(segment->thread->segments) $15 = 85833176

from only 40 or so pinches on the graph total.

— Reply to this email directly or view it on GitHub https://github.com/benedictpaten/pinchesAndCacti/issues/4.

joelarmstrong commented 9 years ago

I'll fix it, I'm already working with the pinch code anyway adding some functionality we need for an online cactus graph. Just wanted to make sure I made an issue so I didn't forget about it.