Marcel Moolenaar
2008-May-26 22:05 UTC
[LLVMdev] use after free [was: A quick update on FreeBSD support]
On May 26, 2008, at 1:25 AM, Bill Wendling wrote:> On May 25, 2008, at 1:39 PM, Marcel Moolenaar wrote: >> On May 25, 2008, at 12:58 AM, Bill Wendling wrote: >> >>> Could you try this (massively hacky) patch out to see if it fixes >>> your >>> problem? >>> >>> >> Alas, it didn't fix the problem: >> > Crumbs. > > I think that the analysis I told you before wasn't fully correct. I > think I mentioned something about "n = 4" and that could cause the > SmallVector to reallocate things. But that was in error.The analysis seems to be right after all. The node iterator (NI) is clobbered when node 5 is added. The reason it sometimes causes a failure may be related to whether NI is dereferenced after it's being clobbered. This is highly platform specific, as well as optimization specific. The problem exists on all platforms that I've seen so far. In short: The call to update() on line 1612 of PredicateSimplifier.cpp can result in the resizing of the node vector, which breaks dereferencing NI in the call to update() on line 1613 of PredicateSimplifier.cpp. (gdb) run Starting program: /nfs/llvm/obj/amd64/Debug/bin/opt -predsimplify - disable-output < ../powerpc/x.bc [New LWP 100066] [New Thread 0xd040b0 (LWP 100066)] [Switching to Thread 0xd040b0 (LWP 100066)] Breakpoint 3, makeEqual (this=0x7fffffffe110, V1=0xd1c420, V2=0xd3b168) at /nfs/llvm/src/llvm/lib/Transforms/Scalar/ PredicateSimplifier.cpp:1612 1612 IG.node(NI->To)->update(n1, reversePredicate(NI- >LV), Top); (gdb) p NI $28 = ((anonymous namespace)::InequalityGraph::Edge *) 0xd56340 (gdb) watch *0xd56340 Watchpoint 6: *13984576 (gdb) c Continuing. Watchpoint 6: *13984576 Old value = 2 New value = 1515870810 0x00000008013e1e84 in memset () from /lib/libc.so.7 (gdb) bt #0 0x00000008013e1e84 in memset () from /lib/libc.so.7 #1 0x000000080136ecd1 in malloc_usable_size () from /lib/libc.so.7 #2 0x000000080136eec7 in free () from /lib/libc.so.7 #3 0x00000000007cdf7d in deallocate (this=0xd2e178, __p=0xd561c0) at new_allocator.h:97 #4 0x00000000007cdfaf in _M_deallocate (this=0xd2e178, __p=0xd561c0, __n=4) at stl_vector.h:134 #5 0x00000000007d66ef in _M_fill_insert (this=0xd2e178, __position {_M_current = 0xd56380}, __n=1, __x=@0x7fffffffdbb0) at vector.tcc:381 #6 0x00000000007d676d in insert (this=0xd2e178, __position {_M_current = 0xd56380}, __n=1, __x=@0x7fffffffdbb0) at stl_vector.h:653 #7 0x00000000007d67f7 in resize (this=0xd2e178, __new_size=5, __x=@0x7fffffffdbb0) at stl_vector.h:421 #8 0x00000000007d6877 in node (this=0xd2e160, index=5) at /nfs/llvm/src/llvm/lib/Transforms/Scalar/ PredicateSimplifier.cpp:749 #9 0x00000000007ddcc3 in makeEqual (this=0x7fffffffe110, V1=0xd1c420, V2=0xd3b168) The following quick-n-dirty fix avoids dereferencing the clobbered NI and as such fixes the superficial problem (i.e. the assert): Index: PredicateSimplifier.cpp ==================================================================--- PredicateSimplifier.cpp (revision 51550) +++ PredicateSimplifier.cpp (working copy) @@ -1609,8 +1609,10 @@ if (Remove.count(NI->To)) continue; - IG.node(NI->To)->update(n1, reversePredicate(NI->LV), Top); - IG.node(n1)->update(NI->To, NI->LV, Top); + unsigned tmpTo = NI->To; + LatticeVal tmpLV = NI->LV; + IG.node(tmpTo)->update(n1, reversePredicate(tmpLV), Top); + IG.node(n1)->update(tmpTo, tmpLV, Top); } } } Of course, it doesn't address the bigger problem of having NI iterate over freed memory. Bill's patch looks on the surface to do the right thing. I don't know yet why it didn't though. Ideally the problem should be handled by the abstract datatype itself. An indirect iterator, either the addition of one or replacing the current unsafe iterator with one, should be a good solution. FYI, -- Marcel Moolenaar xcllnt at mac.com
Nick Lewycky
2008-May-26 22:53 UTC
[LLVMdev] use after free [was: A quick update on FreeBSD support]
Thanks for tracking this down! I can't seem to reproduce it on Linux, even with valgrind. Can you try out this patch and let me know whether it works? Nick Marcel Moolenaar wrote:> On May 26, 2008, at 1:25 AM, Bill Wendling wrote: > >> On May 25, 2008, at 1:39 PM, Marcel Moolenaar wrote: >>> On May 25, 2008, at 12:58 AM, Bill Wendling wrote: >>> >>>> Could you try this (massively hacky) patch out to see if it fixes >>>> your >>>> problem? >>>> >>>> >>> Alas, it didn't fix the problem: >>> >> Crumbs. >> >> I think that the analysis I told you before wasn't fully correct. I >> think I mentioned something about "n = 4" and that could cause the >> SmallVector to reallocate things. But that was in error. > > The analysis seems to be right after all. The node iterator (NI) is > clobbered when node 5 is added. The reason it sometimes causes a > failure may be related to whether NI is dereferenced after it's > being clobbered. This is highly platform specific, as well as > optimization specific. The problem exists on all platforms that > I've seen so far. > > In short: > > The call to update() on line 1612 of PredicateSimplifier.cpp can > result in the resizing of the node vector, which breaks dereferencing > NI in the call to update() on line 1613 of PredicateSimplifier.cpp. > > (gdb) run > Starting program: /nfs/llvm/obj/amd64/Debug/bin/opt -predsimplify - > disable-output < ../powerpc/x.bc > [New LWP 100066] > [New Thread 0xd040b0 (LWP 100066)] > [Switching to Thread 0xd040b0 (LWP 100066)] > > Breakpoint 3, makeEqual (this=0x7fffffffe110, V1=0xd1c420, V2=0xd3b168) > at /nfs/llvm/src/llvm/lib/Transforms/Scalar/ > PredicateSimplifier.cpp:1612 > 1612 IG.node(NI->To)->update(n1, reversePredicate(NI- > >LV), Top); > (gdb) p NI > $28 = ((anonymous namespace)::InequalityGraph::Edge *) 0xd56340 > (gdb) watch *0xd56340 > Watchpoint 6: *13984576 > (gdb) c > Continuing. > Watchpoint 6: *13984576 > > Old value = 2 > New value = 1515870810 > 0x00000008013e1e84 in memset () from /lib/libc.so.7 > (gdb) bt > #0 0x00000008013e1e84 in memset () from /lib/libc.so.7 > #1 0x000000080136ecd1 in malloc_usable_size () from /lib/libc.so.7 > #2 0x000000080136eec7 in free () from /lib/libc.so.7 > #3 0x00000000007cdf7d in deallocate (this=0xd2e178, __p=0xd561c0) > at new_allocator.h:97 > #4 0x00000000007cdfaf in _M_deallocate (this=0xd2e178, __p=0xd561c0, > __n=4) > at stl_vector.h:134 > #5 0x00000000007d66ef in _M_fill_insert (this=0xd2e178, __position> {_M_current = 0xd56380}, __n=1, __x=@0x7fffffffdbb0) at > vector.tcc:381 > #6 0x00000000007d676d in insert (this=0xd2e178, __position> {_M_current = 0xd56380}, __n=1, __x=@0x7fffffffdbb0) at > stl_vector.h:653 > #7 0x00000000007d67f7 in resize (this=0xd2e178, __new_size=5, > __x=@0x7fffffffdbb0) at stl_vector.h:421 > #8 0x00000000007d6877 in node (this=0xd2e160, index=5) > at /nfs/llvm/src/llvm/lib/Transforms/Scalar/ > PredicateSimplifier.cpp:749 > #9 0x00000000007ddcc3 in makeEqual (this=0x7fffffffe110, V1=0xd1c420, > V2=0xd3b168) > > > The following quick-n-dirty fix avoids dereferencing the clobbered NI > and as such fixes the superficial problem (i.e. the assert): > > Index: PredicateSimplifier.cpp > ==================================================================> --- PredicateSimplifier.cpp (revision 51550) > +++ PredicateSimplifier.cpp (working copy) > @@ -1609,8 +1609,10 @@ > if (Remove.count(NI->To)) > continue; > > - IG.node(NI->To)->update(n1, reversePredicate(NI->LV), > Top); > - IG.node(n1)->update(NI->To, NI->LV, Top); > + unsigned tmpTo = NI->To; > + LatticeVal tmpLV = NI->LV; > + IG.node(tmpTo)->update(n1, reversePredicate(tmpLV), Top); > + IG.node(n1)->update(tmpTo, tmpLV, Top); > } > } > } > > > Of course, it doesn't address the bigger problem of having NI iterate > over freed memory. Bill's patch looks on the surface to do the right > thing. I don't know yet why it didn't though. Ideally the problem should > be handled by the abstract datatype itself. An indirect iterator, either > the addition of one or replacing the current unsafe iterator with one, > should be a good solution. > > FYI, >-------------- next part -------------- An embedded and charset-unspecified text was scrubbed... Name: patch URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080526/9d031572/attachment.ksh>
On May 26, 2008, at 3:53 PM, Nick Lewycky wrote:> Thanks for tracking this down! I can't seem to reproduce it on > Linux, even with valgrind. > > Can you try out this patch and let me know whether it works?We have a winner :-) FYI, -- Marcel Moolenaar xcllnt at mac.com