<div dir="ltr"><div><div><div><div><div>Hi Daniel,<br><br></div>I looked through the C and C++ standards and there is nothing there to support my case. So I guess you are right and I was mistaken. Sorry for confusion.<br><br></div>Yours,<br></div>Andrey<br>===<br></div>Compiler Architect<br></div>NXP<br><br><div><div><br></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Apr 11, 2017 at 11:07 AM, Daniel Berlin <span dir="ltr"><<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">C++ only allows this for two things in a union.<div>Same with C11.</div><div>This is the "common initial sequence rule".</div><div><br></div><div>What you are showing is very clearly forbidden by the effective type rules.<br><div><br></div><div>Cerebus (<a href="https://www.cl.cam.ac.uk/~pes20/cerberus/" target="_blank">https://www.cl.cam.ac.uk/~<wbr>pes20/cerberus/</a>) agrees:</div><div><div>#include <stdio.h></div><div> </div><div>typedef struct { int i1; } s1;</div><div>typedef struct { int i2; } s2;</div><div> </div><div>void f(s1 *s1p, s2 *s2p) {</div><div> s1p->i1 = 2;</div><div> s2p->i2 = 3;</div><div> printf("%i\n", s1p->i1);</div><div>}</div><div> </div><div>int main() {</div><div> s1 s = {.i1 = 1};</div><div> f(&s, (s2 *)&s);</div><div>}</div><div><br></div></div></div><div>GCC -O2 will print 2 instead of 3.</div><div><br></div><div>The only way this is legal is if you did:<br><div>typedef struct { int i1; } s1;</div></div><div>typedef struct { s1 base; } s2;</div><div><br></div><div><div><br class="m_5102625317184904640gmail-Apple-interchange-newline">void f(s1 *s1p, s2 *s2p) {</div><div> s1p->i1 = 2;</div><div> s2p->base.i1 = 3;</div><div> printf("%i\n", s1p->i1);</div><div>}</div><div> </div><div>int main() {</div><div> s1 s = {.i1 = 1};</div><div> f(&s, (s2 *)&s);</div><div>}</div></div><div>This would be legal.</div><div><br></div><div>Gcc prints 3 ;)</div><div><br></div><div><br></div><div><br></div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Apr 11, 2017 at 1:46 AM, Andrey Bokhanko via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div><div><div>Hal,<br><br></div>To clarify, my example meant to illustrate that for memory references to structures' fields you have to keep a user-defined type, even for one byte accesses. C++ allows references to "initial member sequence" using pointers to structures of different types. And yes, there are programs in the wild that rely on this (don't remember details... this was from previous life).<br><br></div><div>Another thing to consider -- what about memset / memcpy / etc that inherently rely on type punning? If not inlined, they don't present problems for an optimizer -- probably shouldn't be considered as aliasing rules violation?<br></div><div><br></div>Yours,<br></div>Andrey<br>===<br></div>Compiler Architect<br></div>NXP<br><br></div><div class="m_5102625317184904640HOEnZb"><div class="m_5102625317184904640h5"><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Apr 11, 2017 at 12:05 AM, Hal Finkel <span dir="ltr"><<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000"><span>
<p><br>
</p>
<div class="m_5102625317184904640m_-1356200992995945943m_7989103750356669834moz-cite-prefix">On 04/10/2017 09:55 AM, Andrey Bokhanko
wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">
<div>
<div>
<div>
<div>
<div>Hi Hal,<br>
<br>
</div>
I wonder how your solution will handle the following?<br>
<br>
</div>
struct {<br>
</div>
<div> int s1_f1;<br>
</div>
<div> float s1_f2;<br>
</div>
<div> int s1_f3;<br>
</div>
<div> float s1_f4;<br>
</div>
} S1;<br>
</div>
<div><br>
</div>
struct {<br>
</div>
<div> int s2_f1;<br>
</div>
<div> float s2_f2;<br>
</div>
<div> int *s2_f3; // to add some interest, suppose that
sizeof(int) == sizeof(int *)<br>
</div>
<div> float s2_f4;<br>
</div>
} S2;<br>
<div><br>
</div>
<div>S1 *s1; S2 *s2;<br>
</div>
<div>...<br>
s2 = (S1*)s1;<br>
</div>
<div>s2->s2_f1 = 0; // allowed<br>
s2->s2_f2 = 0; // allowed<br>
</div>
<div>s2->s2_f3 = 0; // not allowed<br>
</div>
<div>s2->s2_f4 = 0; // not allowed<br>
<br>
</div>
<div>Also, when you plan to set types for allocated memory?</div>
</div>
</blockquote>
<br></span>
The most-general thing seems to be to set the types along with a
store. As a result, the proposed scheme would not find a fault with
the code above, but would complain if anyone actually later read
S1.s1_f3.<br>
<br>
If we want to catch these kinds of problems directly we'd need to
have the compiler insert code when the type is constructed to mark
the types, and then we'd need to check those types around stores.
This also sounds like a useful enhancement (although somewhat more
complicated to implement).<span><br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div> What types will be set for memory allocated by a malloc
call?<br>
</div>
</div>
</blockquote>
<br></span>
Memory would be untyped (or of unknown type) when allocated.<br>
<br>
Thanks again,<br>
Hal<div><div class="m_5102625317184904640m_-1356200992995945943h5"><br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div><br>
</div>
<div>Yours,<br>
</div>
<div>Andrey<br>
</div>
<div><br>
</div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Tue, Apr 4, 2017 at 10:13 PM, Hal
Finkel via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi
everyone,<br>
<br>
At EuroLLVM, Chandler and I chatted about the design for a
potential TBAA sanitizer. Here's my attempt to summarize:<br>
<br>
C/C++ have type-based aliasing rules, and LLVM's optimizer
can exploit these given TBAA metadata added by Clang.
Roughly, a pointer of given type cannot be used to access an
object of a different type (with, of course, certain
exceptions). Unfortunately, there's a lot of code in the
wild that violates these rules (e.g. for type punning), and
such code often must be built with -fno-strict-aliasing.
Performance is often sacrificed as a result. Part of the
problem is the difficulty of finding TBAA violations. A
sanitizer would help.<br>
<br>
A design goal of a TBAA sanitizer is to limit the
shadow-memory overhead of the implementation. ASan, for
example, uses 1 bit per byte. Here we're hoping to keep the
overhead down to 2 bits per byte for the TBAA sanitizing. We
might be able to do this, while handling all common types on
the fast path, if we use both alignment and type
information. When accessing data of B bytes, 2*B bits of
shadow memory can be used. Thus, we'll get 2 bits for a
one-byte type, 4 bits for a two-byte type, etc. Moreover, we
need appropriate holes in the encoding space so that no type
has a shadow encoding that overlaps with an aligned part of
a larger type's encoding.<br>
For example, we need to detect:<br>
<br>
double f = ...; return *(int*) &f; // We should catch
this.<br>
<br>
We might use the following encoding. The idea is that the
common case, for which we need a reasonable fast path, is
that type types are exactly equal. For this case, we want a
simple comparison of the shadow type encodings to be
sufficient to validate the access. For cases where the
encodings don't match (and isn't zero to indicate an unknown
type), or for which there is no direct encoding for the
access type, a slow path must be used. All of this assumes
that we're validating the the pointer alignment first, and
then checking the type encodings.<br>
<br>
1 Byte:<br>
00 = 0 = unknown type<br>
01 = 1 = hole<br>
10 = 2 = hole<br>
11 = 3 = all one-byte types (slow path, see note later on
this)<br>
<br>
2 Bytes:<br>
0000 = 0 = unknown type<br>
0101 = 5 = short<br>
0110 = 6 = hole (A)<br>
0111 = 7 = wchar_t (under some ABIs)<br>
1001 = 9 = hole (B)<br>
1010 = 10 = hole (C)<br>
1011 = 11 = char16_t<br>
1111 = 15 = all other types (slow path)<br>
<br>
It is important here to have wchar_t have a direct encoding
here because wchar_t is two bytes on Windows, and moreover,
wchar_t is very commonly used on Windows. The partial
encoding overlap of wchar_t (i.e. 0111) with the 11
one-byte-type encoding works because 11 always indicates a
slow-path check.<br>
<br>
4 Bytes:<br>
0000 0000 = 0 = unknown type<br>
A A = int<br>
A B = float<br>
B A = pointer (under some ABIs)<br>
B B = long (under some ABIs)<br>
A 1111 = wchar_t (under some ABIs)<br>
B 1111 = char32_t<br>
A C = hole (D)<br>
C A = hole (E)<br>
B C = hole (F)<br>
C B = hole (G)<br>
C C = hole (H)<br>
1111 1111 = 255 = all other types (slow path)<br>
<br>
8 Bytes:<br>
0000 0000 0000 0000 = 0 = unknown type<br>
D D = double<br>
D E = long (under some ABIs)<br>
E D = long long (under some ABIs)<br>
E E = long double (under some ABIs)<br>
D F = pointer (under some ABIs)<br>
F D = hole (I)<br>
E F = hole (J)<br>
F E = hole<br>
F F = hole<br>
...<br>
1111 1111 1111 1111 = 65535 = all other types<br>
<br>
16 Bytes:<br>
0 = unknown type<br>
| | = __int128_t<br>
I J = long long (under some ABIs)<br>
J I = long double (under some ABIs)<br>
J J = hole<br>
...<br>
-1 = all other types<br>
<br>
For pointers, this scheme would consider all pointers to be
the same (regardless of pointee type). Doing otherwise would
mostly requiring putting pointer-type checking on the slow
path (i.e. access via a pointer pointer), and that could add
considerable overhead. We might, however, split out function
pointers from other pointers. We could provide a
compile-time option to control the granularity of
pointer-type checks.<br>
<br>
Builtin vector types for which the vector element type has a
direct encoding also naturally have a direct encoding (the
concatenation of the encoding for the element type).<br>
<br>
Obviously the fact that we have no fast-path encodings for
one-byte types could be problematic. Note however that:<br>
<br>
1. If a larger type is being used to access a smaller type
(plus more), the encodings won't match, so we always end up
on the slow path.<br>
<br>
2. If the access type is a one-byte type, we would want to
validate quickly. However, most common one-byte types are
universally aliasing (i.e. not subject to TBAA violations).
Specifically, for C/C++, pointers to char, unsigned char,
signed char (C only), and std::byte, can be used to access
any part of any type. That leaves signed char (C++ only),
bool/_Bool, and enums with a [signed/unsigned] char base
type (C++ only, std::byte exempted) as pointee types we
might wish to validate. We'd always need to fall back to the
slow path to validate these. We could provide a compile-time
option to disable such one-byte access checking if
necessary.<br>
<br>
How would the slow path work? First, the code needs to find
the beginning of the allocation. It can do this by scanning
backwards in the ASan shadow memory. Once located, we'll
read a pointer to a type-description structure from that
"red zone" location. For dynamic allocations, ASan's
allocator will ensure such a space for the pointer exists.
For static allocations and globals, the compiler will ensure
it exists. The compiler will make sure that all constructors
locate this field and fill it in. Destructors can clear it.
If two of these type-description-structure pointers are
equal, then we can conclude that the types are equal. If
not, then we need to interpret the structure. The pointer
itself might be to an interval map (to deal with arrays,
placement new, etc. - we can use the low bit of the pointer
to differentiate between an actual type-description
structure and an interval map), and the leaves of the
interval map point to actual type-description structures.
The type-description structure is an array of (offset, type)
pairs, where the type field is also a
type-description-structure pointer. The type-description
structures themselves are comdat globals emitted in each
relevant translation unit, where the comdat key is formed
using the mangled type name (and size, etc.), and pointers
to these symbols are then used to identify the types.<br>
<br>
Thoughts?<br>
<br>
Thanks again,<br>
Hal<span class="m_5102625317184904640m_-1356200992995945943m_7989103750356669834HOEnZb"><font color="#888888"><br>
<br>
-- <br>
Hal Finkel<br>
Lead, Compiler Technology and Programming Languages<br>
Leadership Computing Facility<br>
Argonne National Laboratory<br>
<br>
______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
</font></span></blockquote>
</div>
<br>
</div>
</blockquote>
<br>
<pre class="m_5102625317184904640m_-1356200992995945943m_7989103750356669834moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</div></div></div>
</blockquote></div><br></div>
</div></div><br>______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
<br></blockquote></div><br></div>
</div></div></blockquote></div><br></div>