<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p><br>
</p>
<div class="moz-cite-prefix">On 04/06/2017 10:15 PM, Dean Michael
Berris wrote:<br>
</div>
<blockquote
cite="mid:6C94E667-E322-4498-B983-81CCBECC6882@gmail.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
Hi Hal,
<div class=""><br class="">
</div>
<div class="">I'm not too knowledgable about these areas so pardon
the potentially ignorant questions.</div>
</blockquote>
<br>
No problem.<br>
<br>
<blockquote
cite="mid:6C94E667-E322-4498-B983-81CCBECC6882@gmail.com"
type="cite">
<div class=""><br class="">
</div>
<div class="">First, does this mean the instrumentation/rewriting
happens at the front-end so we can identify places where the
aliasing might happen and annotate those when generating the IR?
Say, in clang, does it only annotate potentially egregious cases
or does it have to do it for all pointer operations?</div>
</blockquote>
<br>
Clang already generates TBAA metadata on relevant memory accesses,
and I envision an IR-level instrumentation pass looking for memory
accesses with TBAA metadata and generating TBAA-sanitizer checks
prior to such accesses. The simplest way to do this is to set the
types on stores and verify them on loads (along with atomicrmw and
cmpxchg). We can also clear out type information upon encountering a
lifetime.end intrinsic.<br>
<br>
<blockquote
cite="mid:6C94E667-E322-4498-B983-81CCBECC6882@gmail.com"
type="cite">
<div class=""><br class="">
</div>
<div class="">Second, how do you report the errors in the
sanitiser? Is the intent to run like ASAN where it will fail on
cases where it trips? Or does it only collect the information?</div>
</blockquote>
<br>
I propose that it run along with ASAN, specifically as an
enhancement to ASAN, using the existing ASAN shadow data to find the
beginning of allocations for the slow-path check.<br>
<br>
<blockquote
cite="mid:6C94E667-E322-4498-B983-81CCBECC6882@gmail.com"
type="cite">
<div class=""><br class="">
</div>
<div class="">Third, what would the results look like? Can it tell
where the aliasing violations happened?</div>
</blockquote>
<br>
This should happen very much like ASAN. The difference being that
the resulting report will name the type being loaded and the type
actually stored at the relevant location.<br>
<br>
<blockquote
cite="mid:6C94E667-E322-4498-B983-81CCBECC6882@gmail.com"
type="cite">
<div class=""><br class="">
</div>
<div class="">Lastly, how do features like c++11 unions get
tracked, or the upcoming std::variant<...> implementations
that might do some trickery? I suspect this is also dependent on
things like alignment and padding, and even with packed
representations of structs that get union'ed with character
arrays, etc.</div>
</blockquote>
<br>
I think that all of those things should just work; they all follow
the rule that to read a type you need to write that type first, and
unions, variant, etc. ensure that types are stored at
properly-aligned addresses for each type.<br>
<br>
Thanks,<br>
Hal<br>
<br>
<blockquote
cite="mid:6C94E667-E322-4498-B983-81CCBECC6882@gmail.com"
type="cite">
<div class=""><br class="">
</div>
<div class="">/me quickly Googles for TBAA's definition.</div>
<div class=""><br class="">
</div>
<div class="">Cheers</div>
<div class=""><br class="">
<div>
<blockquote type="cite" class="">
<div class="">On 5 Apr 2017, at 06:13, Hal Finkel via
llvm-dev <<a moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>>
wrote:</div>
<br class="Apple-interchange-newline">
<div class="">
<div class="">Hi everyone,<br class="">
<br class="">
At EuroLLVM, Chandler and I chatted about the design for
a potential TBAA sanitizer. Here's my attempt to
summarize:<br class="">
<br class="">
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 class="">
<br class="">
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 class="">
For example, we need to detect:<br class="">
<br class="">
double f = ...; return *(int*) &f; // We should
catch this.<br class="">
<br class="">
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 class="">
<br class="">
1 Byte:<br class="">
00 = 0 = unknown type<br class="">
01 = 1 = hole<br class="">
10 = 2 = hole<br class="">
11 = 3 = all one-byte types (slow path, see note later
on this)<br class="">
<br class="">
2 Bytes:<br class="">
0000 = 0 = unknown type<br class="">
0101 = 5 = short<br class="">
0110 = 6 = hole (A)<br class="">
0111 = 7 = wchar_t (under some ABIs)<br class="">
1001 = 9 = hole (B)<br class="">
1010 = 10 = hole (C)<br class="">
1011 = 11 = char16_t<br class="">
1111 = 15 = all other types (slow path)<br class="">
<br class="">
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 class="">
<br class="">
4 Bytes:<br class="">
0000 0000 = 0 = unknown type<br class="">
A A = int<br class="">
A B = float<br class="">
B A = pointer (under some ABIs)<br class="">
B B = long (under some ABIs)<br class="">
A 1111 = wchar_t (under some ABIs)<br class="">
B 1111 = char32_t<br class="">
A C = hole (D)<br class="">
C A = hole (E)<br class="">
B C = hole (F)<br class="">
C B = hole (G)<br class="">
C C = hole (H)<br class="">
1111 1111 = 255 = all other types (slow path)<br
class="">
<br class="">
8 Bytes:<br class="">
0000 0000 0000 0000 = 0 = unknown type<br class="">
D D = double<br class="">
D E = long (under some ABIs)<br class="">
E D = long long (under some ABIs)<br class="">
E E = long double (under some ABIs)<br class="">
D F = pointer (under some ABIs)<br class="">
F D = hole (I)<br class="">
E F = hole (J)<br class="">
F E = hole<br class="">
F F = hole<br class="">
...<br class="">
1111 1111 1111 1111 = 65535 = all other types<br
class="">
<br class="">
16 Bytes:<br class="">
0 = unknown type<br class="">
| | = __int128_t<br class="">
I J = long long (under some ABIs)<br class="">
J I = long double (under some ABIs)<br class="">
J J = hole<br class="">
...<br class="">
-1 = all other types<br class="">
<br class="">
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
class="">
<br class="">
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 class="">
<br class="">
Obviously the fact that we have no fast-path encodings
for one-byte types could be problematic. Note however
that:<br class="">
<br class="">
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 class="">
<br class="">
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
class="">
<br class="">
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 class="">
<br class="">
Thoughts?<br class="">
<br class="">
Thanks again,<br class="">
Hal<br class="">
<br class="">
-- <br class="">
Hal Finkel<br class="">
Lead, Compiler Technology and Programming Languages<br
class="">
Leadership Computing Facility<br class="">
Argonne National Laboratory<br class="">
<br class="">
_______________________________________________<br
class="">
LLVM Developers mailing list<br class="">
<a moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a><br
class="">
<a class="moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br
class="">
</div>
</div>
</blockquote>
</div>
<br class="">
<div class="">
<div style="color: rgb(0, 0, 0); letter-spacing: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
word-wrap: break-word; -webkit-nbsp-mode: space;
-webkit-line-break: after-white-space;" class="">
<div style="color: rgb(0, 0, 0); letter-spacing: normal;
orphans: auto; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
word-wrap: break-word; -webkit-nbsp-mode: space;
-webkit-line-break: after-white-space;" class="">-- Dean</div>
</div>
</div>
<br class="">
</div>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</body>
</html>