llvm dev - Dec 2011 - [LLVMdev] load widening conflicts with AddressSanitizer

On Dec 16, 2011, at 12:39 PM, Kostya Serebryany wrote:
> > Do we consider the above transformation legal?
Yes, the transformation is perfectly legal for the normal compiler.
> > I would argue that it should not be legal.  We don't actually know
what
> > comes after the 22 byte object.  Is it another memory object?  A
> > memory-mapped I/O device?  Unmapped memory?  Padded junk space? 
Reading
> > memory-mapped I/O could have nasty side effects, and accessing
unmapped
> > memory could cause the program to fault even though it was written
correctly
> > as the source-language level.
Device memory accesses need to be done with volatile.  This can't cause a
paging problem (e.g. causing an additional page fault where none existed before)
on systems that use power-of-two sized pages.
> Having the load hit unmapped memory is impossible on common
> architectures given the alignment we're talking about here.  And if
> memory-mapped IO comes after the memory object, the object itself also
> has some sort of unusual semantics, so it should be using volatile
> loads anyway.
> 
> Would would be the right way to disable load widening when AddressSanitizer
(or SAFECode) is enabled?
This is a good question.  Would it be possible for ASan to do its
instrumentation earlier?  I supposed we could add a "do not widen"
metadata hint on load instructions or something like that.

-Chris


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20111216/eb6ac5a5/attachment.html>

>
> This is a good question.  Would it be possible for ASan to do its
> instrumentation earlier?
>
It would be possible but undesirable.
First, asan blows up the IR and running asan early will increase the
compile-time.
Second, asan greatly benefits from all optimizations running before it
because it needs to instrument less memory accesses.
It actually benefits from load widening too: in the test case above asan
instruments only one load instead of two.

In this case, we have an array of 22 bytes which is 16-aligned.
I suspect that load widening changed the alignment of alloca instruction to
make the transformation legal. Right?
Can we change the load widening algorithm to also change the size of alloca
instruction to be dividable by 16?
This will solve the problem, at least the variant I observe now.

--kcc


> I supposed we could add a "do not widen" metadata hint on load
> instructions or something like that.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20111216/87f110ed/attachment.html>

On Dec 16, 2011, at 2:27 PM, Kostya Serebryany wrote:
> This is a good question.  Would it be possible for ASan to do its
instrumentation earlier?
> 
> It would be possible but undesirable. 
> First, asan blows up the IR and running asan early will increase the
compile-time.
> Second, asan greatly benefits from all optimizations running before it
because it needs to instrument less memory accesses.
> It actually benefits from load widening too: in the test case above asan
instruments only one load instead of two.
You certainly wouldn't want to run asan before mem2reg/SRoA, but after that,
the benefits are probably small.  I'd guess that there is some non-zero
value to exposing the code generated by asan to the optimizer.  Have you looked
at that at all?
> In this case, we have an array of 22 bytes which is 16-aligned. 
> I suspect that load widening changed the alignment of alloca instruction to
make the transformation legal. Right?
> Can we change the load widening algorithm to also change the size of alloca
instruction to be dividable by 16?
> This will solve the problem, at least the variant I observe now. 
I believe it is 16-byte aligned based on ABI requirements for x86-64, though
you're right that the optimizer will increase alignment in other cases.  In
any case, we don't want to increase the size of the object, because that
would prevent packing some other data in after it.  For example, a 2-byte
aligned 10 byte object can be placed after it in memory if we keep it 22-bytes
in size.

-Chris

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20111216/801b6ac8/attachment.html>

On 12/16/11 4:14 PM, Chris Lattner wrote:
> On Dec 16, 2011, at 12:39 PM, Kostya Serebryany wrote:
>>
>>     > Do we consider the above transformation legal?
>>
>
> Yes, the transformation is perfectly legal for the normal compiler.
So how do you guarantee that the behavior is predictable regardless of 
hardware platform if you don't define what the behavior should be?
>
>>     > I would argue that it should not be legal.  We don't
actually
>>     know what
>>     > comes after the 22 byte object.  Is it another memory object? 
A
>>     > memory-mapped I/O device?  Unmapped memory?  Padded junk
>>     space?  Reading
>>     > memory-mapped I/O could have nasty side effects, and accessing
>>     unmapped
>>     > memory could cause the program to fault even though it was
>>     written correctly
>>     > as the source-language level.
>>
>
> Device memory accesses need to be done with volatile.  This can't 
> cause a paging problem (e.g. causing an additional page fault where 
> none existed before) on systems that use power-of-two sized pages.
I think people are misunderstanding my point about I/O memory.  I wasn't 
saying that the alloca is supposed to access I/O memory; I was saying 
that it is possible for I/O memory to be located contiguously after the 
memory object should the memory object be the last object on its memory 
page.

Now, after thinking about it, I realize why that can't happen if the 
memory is aligned to a 16-byte boundary on most architectures.  However, 
does load-widening actually check that the memory is 16-byte aligned?  
If not, then I don't see why this can't be a problem with memory 
allocated at arbitrary alignments.  Furthermore, you're making 
assumptions about the underlying MMU.  What if you have a funky 
architecture that someone is porting LLVM to, or someone is using x86-32 
segments in an interesting way?

If load-widening searches back through the def-use chains to check that 
the memory is aligned, then fixing the transform to always perform 
defined behavior seems easy enough: we check that the alloca is of the 
right alignment, and then we boost the allocated size if necessary.  
Since we'll never increase the size by more than 8 bytes, this seems 
reasonable.

Moreover, I don't really understand the rationale for allowing a 
transform to introduce undefined behavior into programs that exhibit no 
undefined behavior.  It's a source of subtle problems in the future when 
architectures change or someone does something unconventional, and it 
trips up memory safety tools and static analysis tools that are working 
correctly.  The only reason I see for tolerating it is if fixing the 
problem would be detrimental to performance.  If Kostya or I or someone 
else fixes load-widening so that it doesn't introduce undefined 
behavior, is it going to really hurt performance?

-- John T.
>
>>     Having the load hit unmapped memory is impossible on common
>>     architectures given the alignment we're talking about here. 
And if
>>     memory-mapped IO comes after the memory object, the object itself
>>     also
>>     has some sort of unusual semantics, so it should be using volatile
>>     loads anyway.
>>
>>
>> Would would be the right way to disable load widening when 
>> AddressSanitizer (or SAFECode) is enabled?
>
> This is a good question.  Would it be possible for ASan to do its 
> instrumentation earlier?  I supposed we could add a "do not
widen"
> metadata hint on load instructions or something like that.
>
> -Chris
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20111216/e0f11222/attachment.html>

On Dec 16, 2011, at 2:41 PM, John Criswell wrote:
> On 12/16/11 4:14 PM, Chris Lattner wrote:
>> 
>> On Dec 16, 2011, at 12:39 PM, Kostya Serebryany wrote:
>>> > Do we consider the above transformation legal?
>> 
>> Yes, the transformation is perfectly legal for the normal compiler.
> 
> So how do you guarantee that the behavior is predictable regardless of
hardware platform if you don't define what the behavior should be?
I'm not sure what you mean.  What isn't defined?
>>> > I would argue that it should not be legal.  We don't
actually know what
>>> > comes after the 22 byte object.  Is it another memory object? 
A
>>> > memory-mapped I/O device?  Unmapped memory?  Padded junk
space?  Reading
>>> > memory-mapped I/O could have nasty side effects, and accessing
unmapped
>>> > memory could cause the program to fault even though it was
written correctly
>>> > as the source-language level.
>> 
>> Device memory accesses need to be done with volatile.  This can't
cause a paging problem (e.g. causing an additional page fault where none existed
before) on systems that use power-of-two sized pages.
> 
> I think people are misunderstanding my point about I/O memory.  I
wasn't saying that the alloca is supposed to access I/O memory; I was saying
that it is possible for I/O memory to be located contiguously after the memory
object should the memory object be the last object on its memory page.
There is no way for this transformation to introduce a page spanning load.
> Now, after thinking about it, I realize why that can't happen if the
memory is aligned to a 16-byte boundary on most architectures.  However, does
load-widening actually check that the memory is 16-byte aligned?
Yes.
> What if you have a funky architecture that someone is porting LLVM to, or
someone is using x86-32 segments in an interesting way?
We'll burn that bridge when we get to it ;-)
> Moreover, I don't really understand the rationale for allowing a
transform to introduce undefined behavior into programs that exhibit no
undefined behavior.
There is no undefined behavior here.  This is exactly analogous to the code you
get for bitfield accesses.  If you have an uninitialized struct and start
storing into its fields (to initialize it)  you get a series of "load +
mask + or + store" operations.  These are loading and touching
"undefined" bits in a completely defined way.

-Chris

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20111216/7dae1cfb/attachment.html>