On May 25, 2008, at 12:58 AM, Bill Wendling wrote:> On May 24, 2008, at 4:25 PM, Marcel Moolenaar wrote: > >> On May 24, 2008, at 12:12 PM, Bill Wendling wrote: >> >>> Let us know if you would like extra eyes on the two PPC failures. >>> Many >>> of us have a lot of experience with C++. :-) Do you know where these >>> allocations are? >> >> I don't mind if people help out, so here's some information: >> > Could you try this (massively hacky) patch out to see if it fixes your > problem? > > Index: lib/Transforms/Scalar/PredicateSimplifier.cpp > ==================================================================> --- lib/Transforms/Scalar/PredicateSimplifier.cpp (revision 51554) > +++ lib/Transforms/Scalar/PredicateSimplifier.cpp (working copy) > @@ -674,6 +674,15 @@ > const_iterator begin() const { return Relations.begin(); } > const_iterator end() const { return Relations.end(); } > > + Edge &operator[](unsigned Idx) { > + return Relations[Idx]; > + } > + const Edge &operator[](unsigned Idx) const { > + return Relations[Idx]; > + } > + > + size_t size() const { return Relations.size(); } > + > iterator find(unsigned n, DomTreeDFS::Node *Subtree) { > iterator E = end(); > for (iterator I = std::lower_bound(begin(), E, n); > @@ -1599,18 +1608,23 @@ > for (SetVector<unsigned>::iterator I = Remove.begin(), E > Remove.end(); > I != E; ++I) { > unsigned n = *I; > - for (Node::iterator NI = IG.node(n)->begin(), NE > IG.node(n)->end(); > - NI != NE; ++NI) { > - if (NI->Subtree->DominatedBy(Top)) { > - if (NI->To == n1) { > - assert((NI->LV & EQ_BIT) && "Node inequal to > itself."); > + Node *N = IG.node(n); > + for (unsigned Size = N->size(), i = 0; i < Size; ++i) { > + InequalityGraph::Edge *E = &(*N)[i]; > + if (E->Subtree->DominatedBy(Top)) { > + if (E->To == n1) { > + assert((E->LV & EQ_BIT) && "Node inequal to > itself."); > continue; > } > - if (Remove.count(NI->To)) > + if (Remove.count(E->To)) > continue; > > - IG.node(NI->To)->update(n1, reversePredicate(NI->LV), > Top); > - IG.node(n1)->update(NI->To, NI->LV, Top); > + IG.node(E->To)->update(n1, reversePredicate(E->LV), > Top); > + E = &(*N)[i]; > + Size = N->size(); > + IG.node(n1)->update(E->To, E->LV, Top); > + E = &(*N)[i]; > + Size = N->size(); > } > } > }Alas, it didn't fix the problem: ... gmake[3]: Entering directory `/nfs/llvm/obj/powerpc/lib/Transforms/ Scalar' llvm[3]: Compiling PredicateSimplifier.cpp for Debug build /nfs/llvm/src/llvm/lib/Transforms/Scalar/PredicateSimplifier.cpp: In constructor '<unnamed>::InequalityGraph::Edge::Edge()': /nfs/llvm/src/llvm/lib/Transforms/Scalar/PredicateSimplifier.cpp:607: warning: format '%p' expects type 'void*', but argument 2 has type '<unnamed>::InequalityGraph::Edge*' llvm[3]: Building Debug Archive Library libLLVMScalarOpts.a gmake[3]: Leaving directory `/nfs/llvm/obj/powerpc/lib/Transforms/ Scalar' ... xserve% Debug/bin/opt -predsimplify -disable-output < x.bc Assertion failed: (validPredicate(R) && "Invalid predicate."), function update, file /nfs/llvm/src/llvm/lib/Transforms/Scalar/ PredicateSimplifier.cpp, line 711. Abort (core dumped) (gdb) bt #0 0x2229ce08 in kill () from /lib/libc.so.7 #1 0x22000848 in raise () from /lib/libthr.so.3 #2 0x2229b6ec in abort () from /lib/libc.so.7 #3 0x22281d80 in __assert () from /lib/libc.so.7 #4 0x01c34b4c in update (this=0x200c940, n=1515870810, R=1515870810, Subtree=0x20298c0) at /nfs/llvm/src/llvm/lib/Transforms/Scalar/ PredicateSimplifier.cpp:711 #5 0x01c3d224 in makeEqual (this=0x7fffd580, V1=0x2009730, V2=0x2006624) at /nfs/llvm/src/llvm/lib/Transforms/Scalar/ PredicateSimplifier.cpp:1626 #6 0x01c3dc2c in solve (this=0x7fffd580) at /nfs/llvm/src/llvm/lib/ Transforms/Scalar/PredicateSimplifier.cpp:2165 #7 0x01c3fa70 in visitBranchInst (this=0x7fffd678, BI=@0x2006714) at / nfs/llvm/src/llvm/lib/Transforms/Scalar/PredicateSimplifier.cpp:2461 #8 0x01c3fca4 in visitBr (this=0x7fffd678, I=@0x2006714) at Instruction.def:98 #9 0x01c4014c in visit (this=0x7fffd678, I=@0x2006714) at Instruction.def:98 #10 0x01c40bbc in visitInstruction (this=0x2006790, I=0x2006714, DT=0x2029800) at /nfs/llvm/src/llvm/lib/Transforms/Scalar/ PredicateSimplifier.cpp:2390 #11 0x01c40d5c in visitBasicBlock (this=0x2006790, Node=0x2029800) at / nfs/llvm/src/llvm/lib/Transforms/Scalar/PredicateSimplifier.cpp:2334 #12 0x01c411cc in runOnFunction (this=0x2006790, F=@0x2006510) at /nfs/ llvm/src/llvm/lib/Transforms/Scalar/PredicateSimplifier.cpp:2412 #13 0x01e84874 in llvm::FPPassManager::runOnFunction (this=0x2021080, F=@0x2006510) at /nfs/llvm/src/llvm/lib/VMCore/PassManager.cpp:1178 #14 0x01e84aac in llvm::FPPassManager::runOnModule (this=0x2021080, M=@0x20093a0) at /nfs/llvm/src/llvm/lib/VMCore/PassManager.cpp:1198 #15 0x01e8432c in llvm::MPPassManager::runOnModule (this=0x202c110, M=@0x20093a0) at /nfs/llvm/src/llvm/lib/VMCore/PassManager.cpp:1248 #16 0x01e84588 in llvm::PassManagerImpl::run (this=0x201d100, M=@0x20093a0) at /nfs/llvm/src/llvm/lib/VMCore/PassManager.cpp:1322 #17 0x01e84648 in llvm::PassManager::run (this=0x7fffdb40, M=@0x20093a0) at /nfs/llvm/src/llvm/lib/VMCore/PassManager.cpp:1354 #18 0x01a70774 in main (argc=3, argv=0x7fffdbf8) at /nfs/llvm/src/llvm/ tools/opt/opt.cpp:431 (gdb) x /x E 0x2036390: 0x5a5a5a5a (gdb) p n1 $1 = 5 (gdb) p *N $2 = {_vptr$Node = 0x5a5a5a5a, Relations = {<llvm::SmallVectorImpl<<unnamed>::InequalityGraph::Edge>> = {Begin = 0x5a5a5a5a, End = 0x5a5a5a5a, Capacity = 0x5a5a5a5a, FirstEl = 90 'Z'}, InlineElts = 'Z' <repeats 47 times>}} FYI, -- Marcel Moolenaar xcllnt at mac.com
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. I tried it on my Mac, enabling a mode where malloc initializes memory with 0xAA and deallocated memory with 0x55, but didn't run into the crash that you see here. Perhaps you can track down where the node "4" is being created and see if the values for it aren't being initialized. If they are being initialized, then set a watch on the node to see where they get overwritten. -bw> ... > gmake[3]: Entering directory `/nfs/llvm/obj/powerpc/lib/Transforms/ > Scalar' > llvm[3]: Compiling PredicateSimplifier.cpp for Debug build > /nfs/llvm/src/llvm/lib/Transforms/Scalar/PredicateSimplifier.cpp: In > constructor '<unnamed>::InequalityGraph::Edge::Edge()': > /nfs/llvm/src/llvm/lib/Transforms/Scalar/PredicateSimplifier.cpp:607: > warning: format '%p' expects type 'void*', but argument 2 has type > '<unnamed>::InequalityGraph::Edge*' > llvm[3]: Building Debug Archive Library libLLVMScalarOpts.a > gmake[3]: Leaving directory `/nfs/llvm/obj/powerpc/lib/Transforms/ > Scalar' > ... > > xserve% Debug/bin/opt -predsimplify -disable-output < x.bc > Assertion failed: (validPredicate(R) && "Invalid predicate."), > function update, file /nfs/llvm/src/llvm/lib/Transforms/Scalar/ > PredicateSimplifier.cpp, line 711. > Abort (core dumped) > > > (gdb) bt > #0 0x2229ce08 in kill () from /lib/libc.so.7 > #1 0x22000848 in raise () from /lib/libthr.so.3 > #2 0x2229b6ec in abort () from /lib/libc.so.7 > #3 0x22281d80 in __assert () from /lib/libc.so.7 > #4 0x01c34b4c in update (this=0x200c940, n=1515870810, R=1515870810, > Subtree=0x20298c0) at /nfs/llvm/src/llvm/lib/Transforms/Scalar/ > PredicateSimplifier.cpp:711 > #5 0x01c3d224 in makeEqual (this=0x7fffd580, V1=0x2009730, > V2=0x2006624) at /nfs/llvm/src/llvm/lib/Transforms/Scalar/ > PredicateSimplifier.cpp:1626 > #6 0x01c3dc2c in solve (this=0x7fffd580) at /nfs/llvm/src/llvm/lib/ > Transforms/Scalar/PredicateSimplifier.cpp:2165 > #7 0x01c3fa70 in visitBranchInst (this=0x7fffd678, BI=@0x2006714) > at / > nfs/llvm/src/llvm/lib/Transforms/Scalar/PredicateSimplifier.cpp:2461 > #8 0x01c3fca4 in visitBr (this=0x7fffd678, I=@0x2006714) at > Instruction.def:98 > #9 0x01c4014c in visit (this=0x7fffd678, I=@0x2006714) at > Instruction.def:98 > #10 0x01c40bbc in visitInstruction (this=0x2006790, I=0x2006714, > DT=0x2029800) at /nfs/llvm/src/llvm/lib/Transforms/Scalar/ > PredicateSimplifier.cpp:2390 > #11 0x01c40d5c in visitBasicBlock (this=0x2006790, Node=0x2029800) > at / > nfs/llvm/src/llvm/lib/Transforms/Scalar/PredicateSimplifier.cpp:2334 > #12 0x01c411cc in runOnFunction (this=0x2006790, F=@0x2006510) at / > nfs/ > llvm/src/llvm/lib/Transforms/Scalar/PredicateSimplifier.cpp:2412 > #13 0x01e84874 in llvm::FPPassManager::runOnFunction (this=0x2021080, > F=@0x2006510) at /nfs/llvm/src/llvm/lib/VMCore/PassManager.cpp:1178 > #14 0x01e84aac in llvm::FPPassManager::runOnModule (this=0x2021080, > M=@0x20093a0) at /nfs/llvm/src/llvm/lib/VMCore/PassManager.cpp:1198 > #15 0x01e8432c in llvm::MPPassManager::runOnModule (this=0x202c110, > M=@0x20093a0) at /nfs/llvm/src/llvm/lib/VMCore/PassManager.cpp:1248 > #16 0x01e84588 in llvm::PassManagerImpl::run (this=0x201d100, > M=@0x20093a0) at /nfs/llvm/src/llvm/lib/VMCore/PassManager.cpp:1322 > #17 0x01e84648 in llvm::PassManager::run (this=0x7fffdb40, > M=@0x20093a0) at /nfs/llvm/src/llvm/lib/VMCore/PassManager.cpp:1354 > #18 0x01a70774 in main (argc=3, argv=0x7fffdbf8) at /nfs/llvm/src/ > llvm/ > tools/opt/opt.cpp:431 > > (gdb) x /x E > 0x2036390: 0x5a5a5a5a > (gdb) p n1 > $1 = 5 > (gdb) p *N > $2 = {_vptr$Node = 0x5a5a5a5a, Relations > {<llvm::SmallVectorImpl<<unnamed>::InequalityGraph::Edge>> = {Begin > 0x5a5a5a5a, End = 0x5a5a5a5a, Capacity = 0x5a5a5a5a, FirstEl = 90 > 'Z'}, InlineElts = 'Z' <repeats 47 times>}} > > FYI, > > -- > Marcel Moolenaar > xcllnt at mac.com > > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
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.It sounded very plausible to me :-) I'll keep it in the back of my mind...> I tried it on my Mac, enabling a mode where malloc initializes memory > with 0xAA and deallocated memory with 0x55, but didn't run into the > crash that you see here.Hmmm, odd. I've been trying to figure out on the side why I see this on powerpc and not i386 or amd64 for example. Endianness was one thought, but given that it works on your Mac, it cannot be that simple. I guess it simply means bad code generation is slowly creeping on the list of suspects...> Perhaps you can track down where the node "4" > is being created and see if the values for it aren't being > initialized. If they are being initialized, then set a watch on the > node to see where they get overwritten.Will do... -- Marcel Moolenaar xcllnt at mac.com
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