llvm dev - Jul 2016 - Should analyses be able to hold AssertingVH to IR? (related to PR28400)

On Mon, Jul 11, 2016 at 7:51 PM, Sanjoy Das <sanjoy at
playingwithpointers.com>
wrote:
> Hi Sean,
>
> Sean Silva wrote:
> > While building test-suite with the new PM, I ran into problems with
> > AssertingVH being triggered which is obvious in retrospect:
> > https://llvm.org/bugs/show_bug.cgi?id=28400
> >
> > Both cases I ran into revolve around LVI which holds AssertingVH.
> > Essentially, what happens is this:
> >
> > 1. LVI holds an AssertingVH pointing at a BasicBlock
> > 2. Some other pass ends up deleting that BB (e.g. SimplifyCFG)
> > 3. BOOM
> >
> > Notice that this ends up happening even though SimplifyCFG ultimately
> > invalidates LVI. But that only happens after the AssertingVH has been
> > triggered.
> >
> > We would avoid this issue in principle by just switching those
> > AssertingVH to observing pointers, but then we would have dangling
> > pointers. I'm pretty sure that any analysis that keeps pointers to
IR is
> > in fact ending up with dangling pointers like this.
> >
> > I've noticed that AssumptionCache using CallbackVH that allow it
to
> > update its data structures correctly in this case.
> >
> > Just using regular pointers will end up with dangling pointers in this
> > scenario. This isn't a problem in practice since the analysis will
> > hopefully be invalidated and stop holding the dangling pointers, but
it
> > just seems weird. Thankfully, ASan can generally catch problems if we
do
> > try to access through any of these dangling pointers.
>
> But asan won't catch problems (insofar I understand how it works) if
> the free'ed BasicBlock is used as a key in a DenseMap or something --
> if another BasicBlock gets allocated to the same location we'll end up
> returning bad cached results.
>
ASan's allocator is specifically hardened against reusing memory, which
mitigates this, but I'm not sure by how much (but I think by a significant
amount).


>
> I think the Right Solution(TM) here is to create a new wrapper around
> (Small)DenseMap that in debug mode uses a CallbackVH in a way that:
>
>  - The map is "poisoned" if a key is deleted.
>  - A poisoned map can only be cleared; inserting, removing or looking
>    up elements in a poisoned map fails a assertions.
>
> If needed, we can allow erasing deleted keys from poisoned maps, but
> then we won't catch bugs like:
>
>   M[k] = v;
>   delete k;
>   k1 = new Key();  // allocated to the same location as k1
>   M.erase(k1);  // "successful" deletion.
>
> However, this quite a bit of work, and I'm not sure if the payoff will
> be worth it.

Hmm.. interesting idea but yeah that seems like a lot of work. From my
basic testing, it seems like LVI is the only analysis that uses this
pattern so I'm especially not sure it is worth it for a single analysis
(unless we want to change more analyses to use this pattern).

There's a relatively simple workaround for now which is manually
invalidating LVI at the end of passes that use it (JumpThreading and
CorrelatedValuePropagation).

-- Sean Silva

>
>
> -- Sanjoy
>
>
> > Thoughts? For the moment I have put in a workaround (r274457) that
makes
> > jump-threading invalidate LVI.
> >
> > -- Sean Silva
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160711/673ccac6/attachment.html>

Hi Sean,

Sean Silva wrote:
 >
 >     But asan won't catch problems (insofar I understand how it works)
if
 >     the free'ed BasicBlock is used as a key in a DenseMap or something
--
 >     if another BasicBlock gets allocated to the same location we'll 
end up
 >     returning bad cached results.
 >
 >
 > ASan's allocator is specifically hardened against reusing memory,
which
 > mitigates this, but I'm not sure by how much (but I think by a
 > significant amount).

Do you mean it will re-use memory less often?  Won't that just hide
the bug above?  If anything, I don't want ASan to "mitigate" bugs,
I
want it to make the bug trigger more often. :)

(Or did I just re-state what you were saying?)

-- Sanjoy

On Mon, Jul 11, 2016 at 11:17 PM, Sanjoy Das <sanjoy at
playingwithpointers.com
> wrote:
> Hi Sean,
>
> Sean Silva wrote:
> >
> >     But asan won't catch problems (insofar I understand how it
works) if
> >     the free'ed BasicBlock is used as a key in a DenseMap or
something --
> >     if another BasicBlock gets allocated to the same location
we'll end
> up
> >     returning bad cached results.
> >
> >
> > ASan's allocator is specifically hardened against reusing memory,
which
> > mitigates this, but I'm not sure by how much (but I think by a
> > significant amount).
>
> Do you mean it will re-use memory less often?  Won't that just hide
> the bug above?  If anything, I don't want ASan to "mitigate"
bugs, I
> want it to make the bug trigger more often. :)
>
ASan's reuses it less often, but keeps it poisoned so that dangling
pointers get caught. This makes it less likely that re-use will cause
invalid analysis results. BUT it makes it more likely that when we access a
dangling pointer, it falls into a poisoned heap area. So the net result is
that it catches dangling pointers better.

Or to put it another way, the "heap slot reuse causes invalid analysis
results" situation is actually a subset of "we access a dangling
pointer"
which is what we really want to catch (I mean "dangling" in a sense
that a
pointer stays "dangling" even if its heap slot is reused). By avoiding
reuse of heap slots, the dangling pointer is more likely to be in a heap
slot that ASan is keeping poisoned and not reusing (hence it can detect the
error).

-- Sean Silva

>
> (Or did I just re-state what you were saying?)
>
> -- Sanjoy
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160711/f89e07d8/attachment.html>