<div dir="ltr">Evgeniy and I recently discussed something similar for detecting bad casts (code named: TypeSanitizer). <div>The approach with the shadow memory looked attractive at the first glance, but then we've drowned in details. </div><div><br></div><div>Specifically for TBAA, I had another idea, not involving shadow memory.</div><div>Consider LLVM queries MayAlias(P1, P2) and the result is false, i.e. we think that P1 and P2 point to disjoint memory regions. </div><div>Then we insert a run-time check that intervals [P1,sizeof(*P1)) and [P2,sizeof(*P2)) don't intersect. </div><div><br></div><div>For functions with a reasonable number of pointer pairs where MayAlias(P1, P2)==false we could insert checks for all such pairs. </div><div>For larger functions -- only for those pairs where the optimizer actually queried MayAlias(P1, P2).</div><div><br></div><div>--kcc </div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Apr 11, 2017 at 3:49 AM, 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">
  
    
  
  <div bgcolor="#FFFFFF" text="#000000"><span class="">
    <p><br>
    </p>
    <div class="m_-806542491375291881moz-cite-prefix">On 04/11/2017 03:46 AM, Andrey Bokhanko
      wrote:<br>
    </div>
    <blockquote type="cite">
      
      <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>
          </div>
        </div>
      </div>
    </blockquote>
    <br></span>
    Good point. You (likely) wouldn't want to compile your memcpy /
    memset / etc. implementations with the TBAA sanitizer enabled (or
    we'd need to provide an attribute to disable it for certain
    functions). If they only use char* themselves, then it's fine, but
    if not, that's implementation magic. However, memset, etc. does need
    to be able to 'unset' the type of memory and memcpy needs to be able
    to copy types (at least for PODs). The sanitizer would need to hook
    them for that purpose.<br>
    <br>
     -Hal<div><div class="h5"><br>
    <br>
    <blockquote type="cite">
      <div dir="ltr">
        <div>
          <div>
            <div>
              <div><br>
              </div>
              Yours,<br>
            </div>
            Andrey<br>
            ===<br>
          </div>
          Compiler Architect<br>
        </div>
        NXP<br>
        <br>
      </div>
      <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_-806542491375291881m_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_-806542491375291881h5"><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_-806542491375291881m_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_-806542491375291881m_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>
    </blockquote>
    <br>
    <pre class="m_-806542491375291881moz-signature" cols="72">-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
  </div></div></div>

<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></blockquote></div><br></div>