[LLVMdev] use after free [was: A quick update on FreeBSD support]

[Marcel Moolenaar]

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