<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Apr 11, 2017 at 1:40 PM, Sanjoy Das <span dir="ltr"><<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi,<br>
<br>
On April 11, 2017 at 1:37:20 PM, Sanjoy Das<br>
<span class="gmail-">(<a href="mailto:sanjoy@playingwithpointers.com">sanjoy@playingwithpointers.<wbr>com</a>) wrote:<br>
> Hi Kostya,<br>
><br>
> On April 11, 2017 at 1:30:10 PM, Kostya Serebryany (<a href="mailto:kcc@google.com">kcc@google.com</a>) wrote:<br>
><br>
> > of course, but accesses are done via pointers, and if TBAA queries<br>
> > MayAlias(AccessViaP1, AccessViaP2)<br>
> > there should (??) be a point in the IR where both P1 and P2 exist together<br>
> > and can be compared.<br>
><br>
> That may not be possible (though I'm second guessing what exactly you have in mind so maybe<br>
> I'm missing something here):<br>
><br>
> ptr0 = malloc();<br>
> *(int*)ptr0 = 20; // access0<br>
> free(ptr0);<br>
> ptr1 = calloc(); // bitwise equal to ptr0 by chance<br>
> float f = *(float *)ptr1; // access1<br>
><br>
> The program above is fine (no TBAA violations), but at location access1 ptr1 and ptr0<br>
> overlap despite being NoAlias.<br>
<br>
</span>Actually this isn't specific to TBAA.  Even without TBAA we mark<br>
malloc's return value as NoAlias, so in<br>
<br>
ptr0 = malloc();<br>
free(ptr0);<br>
ptr1 = malloc();<br>
<br>
ptr0 and ptr1 will be NoAlias despite overlapping (there is actually a<br>
real soundness issue here in LLVM's semantics, but I don't want to<br>
digress).  You can also recreate the pattern with realloc.<br></blockquote><div><br></div><div>In both of your examples there is no place in the program where both P0 and P1 are live simultaneously,  </div><div>i.e. no analysis path is expected to query MayAlias(AccessToP0, AccessToP1). No? </div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
The same problem exists with constant addresses.  LLVM states that<br>
constant locations are noalias with themselves, and you again have the<br>
"noalias does not imply pointer inequality" problem.<br></blockquote><div><br></div><div>That won't even have to be special cased, because if we emit a check ConstPtr != ConstPtr, </div><div>such a check will be trivially optimized away. </div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<span class="gmail-HOEnZb"><font color="#888888"><br>
-- Sanjoy<br>
</font></span><div class="gmail-HOEnZb"><div class="gmail-h5"><br>
><br>
> -- Sanjoy<br>
><br>
> ><br>
> ><br>
> > ><br>
> > > This means, at least in LLVM IR, you have to account for cases like:<br>
> > ><br>
> > > if (A)<br>
> > > *(int *)ptr = 20;<br>
> > > if (B)<br>
> > > float f = *(float *)ptr;<br>
> > ><br>
> > > where ptr does not have a type (according to TBAA), but you want to<br>
> > > crash the program if both A and B are true.<br>
> > ><br>
> > > -- Sanjoy<br>
> > ><br>
> > > > For larger functions -- only for those pairs where the optimizer actually<br>
> > > > queried MayAlias(P1, P2).<br>
> > > ><br>
> > > > --kcc<br>
> > > ><br>
> > > ><br>
> > > > On Tue, Apr 11, 2017 at 3:49 AM, Hal Finkel via llvm-dev <<br>
> > > > <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br>
> > > ><br>
> > > > ><br>
> > > > > On 04/11/2017 03:46 AM, Andrey Bokhanko wrote:<br>
> > > > ><br>
> > > > > Hal,<br>
> > > > ><br>
> > > > > To clarify, my example meant to illustrate that for memory references<br>
> > > to<br>
> > > > > structures' fields you have to keep a user-defined type, even for one<br>
> > > byte<br>
> > > > > accesses. C++ allows references to "initial member sequence" using<br>
> > > pointers<br>
> > > > > to structures of different types. And yes, there are programs in the<br>
> > > wild<br>
> > > > > that rely on this (don't remember details... this was from previous<br>
> > > life).<br>
> > > > ><br>
> > > > > Another thing to consider -- what about memset / memcpy / etc that<br>
> > > > > inherently rely on type punning? If not inlined, they don't present<br>
> > > > > problems for an optimizer -- probably shouldn't be considered as<br>
> > > aliasing<br>
> > > > > rules violation?<br>
> > > > ><br>
> > > > ><br>
> > > > > Good point. You (likely) wouldn't want to compile your memcpy / memset<br>
> > > /<br>
> > > > > etc. implementations with the TBAA sanitizer enabled (or we'd need to<br>
> > > > > provide an attribute to disable it for certain functions). If they<br>
> > > only use<br>
> > > > > char* themselves, then it's fine, but if not, that's implementation<br>
> > > magic.<br>
> > > > > However, memset, etc. does need to be able to 'unset' the type of<br>
> > > memory<br>
> > > > > and memcpy needs to be able to copy types (at least for PODs). The<br>
> > > > > sanitizer would need to hook them for that purpose.<br>
> > > > ><br>
> > > > > -Hal<br>
> > > > ><br>
> > > > ><br>
> > > > ><br>
> > > > > Yours,<br>
> > > > > Andrey<br>
> > > > > ===<br>
> > > > > Compiler Architect<br>
> > > > > NXP<br>
> > > > ><br>
> > > > ><br>
> > > > > On Tue, Apr 11, 2017 at 12:05 AM, Hal Finkel wrote:<br>
> > > > ><br>
> > > > >><br>
> > > > >> On 04/10/2017 09:55 AM, Andrey Bokhanko wrote:<br>
> > > > >><br>
> > > > >> Hi Hal,<br>
> > > > >><br>
> > > > >> I wonder how your solution will handle the following?<br>
> > > > >><br>
> > > > >> struct {<br>
> > > > >> int s1_f1;<br>
> > > > >> float s1_f2;<br>
> > > > >> int s1_f3;<br>
> > > > >> float s1_f4;<br>
> > > > >> } S1;<br>
> > > > >><br>
> > > > >> struct {<br>
> > > > >> int s2_f1;<br>
> > > > >> float s2_f2;<br>
> > > > >> int *s2_f3; // to add some interest, suppose that sizeof(int) ==<br>
> > > > >> sizeof(int *)<br>
> > > > >> float s2_f4;<br>
> > > > >> } S2;<br>
> > > > >><br>
> > > > >> S1 *s1; S2 *s2;<br>
> > > > >> ...<br>
> > > > >> s2 = (S1*)s1;<br>
> > > > >> s2->s2_f1 = 0; // allowed<br>
> > > > >> s2->s2_f2 = 0; // allowed<br>
> > > > >> s2->s2_f3 = 0; // not allowed<br>
> > > > >> s2->s2_f4 = 0; // not allowed<br>
> > > > >><br>
> > > > >> Also, when you plan to set types for allocated memory?<br>
> > > > >><br>
> > > > >><br>
> > > > >> The most-general thing seems to be to set the types along with a<br>
> > > store.<br>
> > > > >> As a result, the proposed scheme would not find a fault with the code<br>
> > > > >> 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<br>
> > > > >> the compiler insert code when the type is constructed to mark the<br>
> > > types,<br>
> > > > >> and then we'd need to check those types around stores. This also<br>
> > > sounds<br>
> > > > >> like a useful enhancement (although somewhat more complicated to<br>
> > > implement).<br>
> > > > >><br>
> > > > >> What types will be set for memory allocated by a malloc call?<br>
> > > > >><br>
> > > > >><br>
> > > > >> Memory would be untyped (or of unknown type) when allocated.<br>
> > > > >><br>
> > > > >> Thanks again,<br>
> > > > >> Hal<br>
> > > > >><br>
> > > > >><br>
> > > > >><br>
> > > > >> Yours,<br>
> > > > >> Andrey<br>
> > > > >><br>
> > > > >><br>
> > > > >> On Tue, Apr 4, 2017 at 10:13 PM, Hal Finkel via llvm-dev <<br>
> > > > >> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br>
> > > > >><br>
> > > > >>> Hi everyone,<br>
> > > > >>><br>
> > > > >>> At EuroLLVM, Chandler and I chatted about the design for a potential<br>
> > > > >>> TBAA sanitizer. Here's my attempt to summarize:<br>
> > > > >>><br>
> > > > >>> C/C++ have type-based aliasing rules, and LLVM's optimizer can<br>
> > > exploit<br>
> > > > >>> these given TBAA metadata added by Clang. Roughly, a pointer of<br>
> > > given type<br>
> > > > >>> cannot be used to access an object of a different type (with, of<br>
> > > course,<br>
> > > > >>> certain exceptions). Unfortunately, there's a lot of code in the<br>
> > > wild that<br>
> > > > >>> violates these rules (e.g. for type punning), and such code often<br>
> > > must be<br>
> > > > >>> built with -fno-strict-aliasing. Performance is often sacrificed as a<br>
> > > > >>> result. Part of the problem is the difficulty of finding TBAA<br>
> > > violations. A<br>
> > > > >>> sanitizer would help.<br>
> > > > >>><br>
> > > > >>> A design goal of a TBAA sanitizer is to limit the shadow-memory<br>
> > > overhead<br>
> > > > >>> of the implementation. ASan, for example, uses 1 bit per byte. Here<br>
> > > we're<br>
> > > > >>> hoping to keep the overhead down to 2 bits per byte for the TBAA<br>
> > > > >>> sanitizing. We might be able to do this, while handling all common<br>
> > > types on<br>
> > > > >>> the fast path, if we use both alignment and type information. When<br>
> > > > >>> accessing data of B bytes, 2*B bits of shadow memory can be used.<br>
> > > Thus,<br>
> > > > >>> we'll get 2 bits for a one-byte type, 4 bits for a two-byte type,<br>
> > > etc.<br>
> > > > >>> Moreover, we need appropriate holes in the encoding space so that no<br>
> > > type<br>
> > > > >>> has a shadow encoding that overlaps with an aligned part of a larger<br>
> > > type's<br>
> > > > >>> 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<br>
> > > case,<br>
> > > > >>> for which we need a reasonable fast path, is that type types are<br>
> > > exactly<br>
> > > > >>> equal. For this case, we want a simple comparison of the shadow type<br>
> > > > >>> encodings to be sufficient to validate the access. For cases where<br>
> > > the<br>
> > > > >>> encodings don't match (and isn't zero to indicate an unknown type),<br>
> > > or for<br>
> > > > >>> which there is no direct encoding for the access type, a slow path<br>
> > > must be<br>
> > > > >>> used. All of this assumes that we're validating the the pointer<br>
> > > alignment<br>
> > > > >>> 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<br>
> > > because<br>
> > > > >>> wchar_t is two bytes on Windows, and moreover, wchar_t is very<br>
> > > commonly<br>
> > > > >>> used on Windows. The partial encoding overlap of wchar_t (i.e. 0111)<br>
> > > with<br>
> > > > >>> the 11 one-byte-type encoding works because 11 always indicates a<br>
> > > slow-path<br>
> > > > >>> 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<br>
> > > > >>> (regardless of pointee type). Doing otherwise would mostly requiring<br>
> > > > >>> putting pointer-type checking on the slow path (i.e. access via a<br>
> > > pointer<br>
> > > > >>> pointer), and that could add considerable overhead. We might,<br>
> > > however,<br>
> > > > >>> split out function pointers from other pointers. We could provide a<br>
> > > > >>> compile-time option to control the granularity of pointer-type<br>
> > > checks.<br>
> > > > >>><br>
> > > > >>> Builtin vector types for which the vector element type has a direct<br>
> > > > >>> encoding also naturally have a direct encoding (the concatenation of<br>
> > > the<br>
> > > > >>> encoding for the element type).<br>
> > > > >>><br>
> > > > >>> Obviously the fact that we have no fast-path encodings for one-byte<br>
> > > > >>> types could be problematic. Note however that:<br>
> > > > >>><br>
> > > > >>> 1. If a larger type is being used to access a smaller type (plus<br>
> > > more),<br>
> > > > >>> 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<br>
> > > > >>> quickly. However, most common one-byte types are universally<br>
> > > aliasing (i.e.<br>
> > > > >>> not subject to TBAA violations). Specifically, for C/C++, pointers<br>
> > > to char,<br>
> > > > >>> unsigned char, signed char (C only), and std::byte, can be used to<br>
> > > access<br>
> > > > >>> any part of any type. That leaves signed char (C++ only),<br>
> > > bool/_Bool, and<br>
> > > > >>> enums with a [signed/unsigned] char base type (C++ only, std::byte<br>
> > > > >>> exempted) as pointee types we might wish to validate. We'd always<br>
> > > need to<br>
> > > > >>> fall back to the slow path to validate these. We could provide a<br>
> > > > >>> compile-time option to disable such one-byte access checking if<br>
> > > necessary.<br>
> > > > >>><br>
> > > > >>> How would the slow path work? First, the code needs to find the<br>
> > > > >>> beginning of the allocation. It can do this by scanning backwards in<br>
> > > the<br>
> > > > >>> ASan shadow memory. Once located, we'll read a pointer to a<br>
> > > > >>> type-description structure from that "red zone" location. For dynamic<br>
> > > > >>> allocations, ASan's allocator will ensure such a space for the<br>
> > > pointer<br>
> > > > >>> exists. For static allocations and globals, the compiler will ensure<br>
> > > it<br>
> > > > >>> exists. The compiler will make sure that all constructors locate<br>
> > > this field<br>
> > > > >>> and fill it in. Destructors can clear it. If two of these<br>
> > > > >>> type-description-structure pointers are equal, then we can conclude<br>
> > > that<br>
> > > > >>> the types are equal. If not, then we need to interpret the<br>
> > > structure. The<br>
> > > > >>> pointer itself might be to an interval map (to deal with arrays,<br>
> > > placement<br>
> > > > >>> new, etc. - we can use the low bit of the pointer to differentiate<br>
> > > between<br>
> > > > >>> an actual type-description structure and an interval map), and the<br>
> > > leaves<br>
> > > > >>> of the interval map point to actual type-description structures. The<br>
> > > > >>> type-description structure is an array of (offset, type) pairs,<br>
> > > where the<br>
> > > > >>> type field is also a type-description-structure pointer. The<br>
> > > > >>> type-description structures themselves are comdat globals emitted in<br>
> > > each<br>
> > > > >>> relevant translation unit, where the comdat key is formed using the<br>
> > > mangled<br>
> > > > >>> type name (and size, etc.), and pointers to these symbols are then<br>
> > > used to<br>
> > > > >>> identify the types.<br>
> > > > >>><br>
> > > > >>> Thoughts?<br>
> > > > >>><br>
> > > > >>> Thanks again,<br>
> > > > >>> Hal<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">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>
> > > > >><br>
> > > > >><br>
> > > > >> --<br>
> > > > >> Hal Finkel<br>
> > > > >> Lead, Compiler Technology and Programming Languages<br>
> > > > >> Leadership Computing Facility<br>
> > > > >> Argonne National Laboratory<br>
> > > > >><br>
> > > > >><br>
> > > > ><br>
> > > > > --<br>
> > > > > Hal Finkel<br>
> > > > > Lead, Compiler Technology and Programming Languages<br>
> > > > > Leadership Computing Facility<br>
> > > > > Argonne National Laboratory<br>
> > > > ><br>
> > > > ><br>
> > > > > ______________________________<wbr>_________________<br>
> > > > > LLVM Developers mailing list<br>
> > > > > <a href="mailto:llvm-dev@lists.llvm.org">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>
> > > > ><br>
> > > > ______________________________<wbr>_________________<br>
> > > > LLVM Developers mailing list<br>
> > > > <a href="mailto:llvm-dev@lists.llvm.org">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>
> > ><br>
> ><br>
><br>
</div></div></blockquote></div><br></div></div>