[llvm-dev] [RFC] Design of a TBAA sanitizer
Hal Finkel via llvm-dev
At EuroLLVM, Chandler and I chatted about the design for a potential
TBAA sanitizer. Here's my attempt to summarize:
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.
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.
For example, we need to detect:
double f = ...; return *(int*) &f; // We should catch this.
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.
1 Byte:
00 = 0 = unknown type
01 = 1 = hole
10 = 2 = hole
11 = 3 = all one-byte types (slow path, see note later on this)
2 Bytes:
0000 = 0 = unknown type
0101 = 5 = short
0110 = 6 = hole (A)
0111 = 7 = wchar_t (under some ABIs)
1001 = 9 = hole (B)
1010 = 10 = hole (C)
1011 = 11 = char16_t
1111 = 15 = all other types (slow path)
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.
4 Bytes:
0000 0000 = 0 = unknown type
A A = int
A B = float
B A = pointer (under some ABIs)
B B = long (under some ABIs)
A 1111 = wchar_t (under some ABIs)
B 1111 = char32_t
A C = hole (D)
C A = hole (E)
B C = hole (F)
C B = hole (G)
C C = hole (H)
1111 1111 = 255 = all other types (slow path)
8 Bytes:
0000 0000 0000 0000 = 0 = unknown type
D D = double
D E = long (under some ABIs)
E D = long long (under some ABIs)
E E = long double (under some ABIs)
D F = pointer (under some ABIs)
F D = hole (I)
E F = hole (J)
F E = hole
F F = hole
...
1111 1111 1111 1111 = 65535 = all other types
16 Bytes:
0 = unknown type
| | = __int128_t
I J = long long (under some ABIs)
J I = long double (under some ABIs)
J J = hole
...
-1 = all other types
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.
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).
Obviously the fact that we have no fast-path encodings for one-byte
types could be problematic. Note however that:
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.
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.
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.
Thoughts?
Thanks again,
Hal
--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory
_______________________________________________
LLVM Developers mailing list
llvm...@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Dean Michael Berris via llvm-dev
Stephen Kell via llvm-dev
> TBAA sanitizer. Here's my attempt to summarize:
>
> 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.
It's not quite the same thing, but at last year's EuroLLVM, Chris
Diamand and I presented a Clang-based tool for detecting bad pointer
casts. This seems to be fairly good at identifying code which needs
-fno-strict-aliasing... although it is not designed for checking of
exactly that. <http://www.llvm.org/devmtg/2016-03/#presentation9>
Funnily enough, I was about to e-mail this list with some notes about
that system, since I currently have some spare cycles which could
perhaps help get the Clang/LLVM parts contributed. I'll mostly save
those thoughts for a separate thread (appearing soon!), but continuing
on-topic below....
> 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.
Slightly provocative question, but are you sure that byte-scale shadow
memory is a good fit? It might be, depending on the rest of the design
(more below). A possible alternative is to maintain metadata only at
allocation granularity... my approach does this, and it helps keep the
overhead pretty low in time and space, with two caveats. One is about
checking casts, not dereferences (more below); the other is needing more
complex run-time machinery to understand what "allocations" are.
(However, that has a ton of other applications, so I believe it's very
good value.)
Just so I'm understanding: is this talking about shadowing memory with
its "leaf" type only, or with its "top-level" type? So if I have, say,
the following usually-64-bit type:
struct compound { int x; float y; }
... would we paint the shadow area with an alternating pattern of int
(0110 0110) and floats (0110 1001)? Or would we be using the "all other
types" thing since the memory is actually "compound"?
> 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.
Aha, the pointers-to-pointers problem. Treating all pointers the same
feels like a mistake because, say, aliasing a T* through a void** is
frequently done and really quite useful (although technically UB, if I
understand correctly; is this exploited in LLVM?), whereas aliasing a T*
through an arbitrary S** is probably a bug.
Just for contrast: I'm familiar with this problem, and my way around
this comes in a few parts. I check pointer creation (casts) only; checks
on pointer use (dereference) are unnecessary. Usually it takes a while
before people believe me on this, but the short story is that
pointer-creation checks enforce an invariant that no bad-type pointer
gets into circulation. So dereferences are always okay (until the first
warning, at least; execution can continue after a warning, in a
best-effort no-guarantees fashion). This also greatly helps performance.
I precisely record the type of pointer-typed storage, e.g. so an array
of T** really is recorded as such. There are then some special
allowances for "generic pointers to pointers", including void** , which
need checking *writes* through them. These checks ignore the
dereferenced pointer's type, and check directly for a match between the
type of the written-to storage (the pointer in target memory) and the
type of the pointed-to object (i.e. what's on the end of the pointer
being written). Caching can part-amortise repeated similar checks.
Just as a note, my infrastructure uses a similar comdat trick for the
type descriptors, although the internal structure is quite a bit more
elaborate.
> Thoughts?
My high-level thought is the following question. Is the plan fixed on
developing a tool specifically for C/C++ effective-type rules, i.e.
focused on catching/fixing those particular cases of UB and with the
goal of improving user code performance? Or is there any interest in the
overlapping but distinct problem of helping users detect and debug
bad-pointer problems of a type flavour (i.e. those that are not bounds
errors or temporal errors)?
Plenty of pointer bugs are not UB... e.g. for any heap allocation
("object without a declared type", in C11-speak) I'm allowed to scribble
over it, thereby changing its effective type. It's only UB if I read it
with its previous effective type. But the scribbling itself is fairly
likely to be the bug, because programmers rarely want to change the type
of an allocation mid-lifetime. Meanwhile, many pointer-type problems are
too indirect or complex for the compiler to actually do TBAA-derived
optimisation on, leaving little to be gained from the UB/TBAA point of
view... but again, plenty from the debugging perspective. I suspect the
biggest value of any tool, even if geared specifically towards TBAA,
will turn out to be largely in debugging scenarios more general than
effective-type UB bugs.
I realise all the above might come across as "here's the problem I'd
solve instead" which may not be helpful... I'm interested by any tool in
this general space, so looking forward to hearing more, and happy to
follow up on any of the above,
Stephen.
PS: on top of the EuroLLVM '16 talk, in case you're wondering about how
my system works, the following research papers might help. Or feel free
just to ask questions....
- "Dynamically diagnosing run-time type errors in unsafe code" (OOPSLA '16)
<http://www.cl.cam.ac.uk/~srk31/#oopsla16a>
- "Towards a dynamic object model within Unix processes" (Onward '15)
<http://www.cl.cam.ac.uk/~srk31/#onward15>
... or code if you prefer:
<https://github.com/stephenrkell/liballocs>
<https://github.com/stephenrkell/libcrunch>
<https://github.com/chrisdiamand/clangcrunch>.
Stephen Kell via llvm-dev
> TBAA sanitizer. Here's my attempt to summarize:
>
> 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.
It's not quite the same thing, but at last year's EuroLLVM, Chris
Diamand and I presented a Clang-based tool for detecting bad pointer
casts. This seems to be fairly good at identifying code which needs
-fno-strict-aliasing... although it is not designed for checking of
exactly that. <http://www.llvm.org/devmtg/2016-03/#presentation9>
Funnily enough, I was about to e-mail this list with some notes about
that system, since I currently have some spare cycles which could
perhaps help get the Clang/LLVM parts contributed. I'll mostly save
those thoughts for a separate thread (appearing soon!), but continuing
on-topic below....
> 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.
Slightly provocative question, but are you sure that byte-scale shadow
memory is a good fit? It might be, depending on the rest of the design
(more below). A possible alternative is to maintain metadata only at
allocation granularity... my approach does this, and it helps keep the
overhead pretty low in time and space, with two caveats. One is about
checking casts, not dereferences (more below); the other is needing more
complex run-time machinery to understand what "allocations" are.
(However, that has a ton of other applications, so I believe it's very
good value.)
> When
Just so I'm understanding: is this talking about shadowing memory with
its "leaf" type only, or with its "top-level" type? So if I have, say,
the following usually-64-bit type:
struct compound { int x; float y; }
... would we paint the shadow area with an alternating pattern of int
(0110 0110) and floats (0110 1001)? Or would we be using the "all other
types" thing since the memory is actually "compound"?
> 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.
Aha, the pointers-to-pointers problem. Treating all pointers the same
feels like a mistake because, say, aliasing a T* through a void** is
often done and really quite useful, whereas aliasing a T* through an
arbitrary S** is probably a bug. That said, maybe the former only
belongs in -fno-strict-aliasing code (it's technically UB), in which
case better to catch it. (Does LLVM exploit this UB?)
Just for contrast: I'm familiar with this problem, and my way around
this comes in a few parts. I check pointer creation (casts) only; checks
on pointer use (dereference) are unnecessary. Usually it takes a while
before people believe me on this, but the short story is that
pointer-creation checks enforce an invariant that no bad-type pointer
gets into circulation. So dereferences are always okay (until the first
warning, at least; execution can continue after a warning, in a
best-effort no-guarantees fashion). This also greatly helps performance.
I precisely record the type of pointer-typed storage, e.g. so an array
of T** really is recorded as such. There are then some special
allowances for "generic pointers to pointers", including void** , which
need checking *writes* through them. These checks ignore the
dereferenced pointer's type, and check directly for a match between the
type of the written-to storage (the pointer in target memory) and the
type of the pointed-to object (i.e. what's on the end of the pointer
being written). Caching can part-amortise repeated similar checks.
Just as a note, my infrastructure uses a similar comdat trick for the
> Thoughts?
Stephen.
_______________________________________________
Andrey Bokhanko via llvm-dev
s2 = (S1*)s1;
s2->s2_f2 = 0; // allowed
Hal Finkel via llvm-dev
Hi Hal,
I'm not too knowledgable about these areas so pardon the potentially ignorant questions.
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?
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?
Third, what would the results look like? Can it tell where the aliasing violations happened?
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.
Thanks,
Hal
Hal Finkel via llvm-dev
>> At EuroLLVM, Chandler and I chatted about the design for a potential
>> TBAA sanitizer. Here's my attempt to summarize:
>>
>> 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.
> It's not quite the same thing, but at last year's EuroLLVM, Chris
> Diamand and I presented a Clang-based tool for detecting bad pointer
> casts. This seems to be fairly good at identifying code which needs
> -fno-strict-aliasing... although it is not designed for checking of
> exactly that. <http://www.llvm.org/devmtg/2016-03/#presentation9>
>
> Funnily enough, I was about to e-mail this list with some notes about
> that system, since I currently have some spare cycles which could
> perhaps help get the Clang/LLVM parts contributed. I'll mostly save
> those thoughts for a separate thread (appearing soon!), but continuing
> on-topic below....
Sounds neat.
>
>> 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.
> Slightly provocative question, but are you sure that byte-scale shadow
> memory is a good fit?
Am I sure? No. But I *think* that is because I'd like to avoid false
positives, and that means dealing with places where we dynamically
change the type of part of an allocation (via placement new or
whatever). This certainly seems necessary to deal with some C++
containers at least.
I intended to imply that we'd fill with the alternating pattern
indicating int and float.
>
>> 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.
> Aha, the pointers-to-pointers problem. Treating all pointers the same
> feels like a mistake because, say, aliasing a T* through a void** is
> frequently done and really quite useful (although technically UB, if I
> understand correctly; is this exploited in LLVM?
I don't know if it is exploited by LLVM, although as I recall, all
implementations of posix_memalign and similar functions potentially run
afoul of the rules (because they need to store the new pointer as a
void* regardless of what it actually is). I'm not sure how strict we can
be here in practice. Currently, AFAIKT, Clang emits TBAA metadata which
does not differentiate between pointer types (it calls them all "any
pointer").
> ), whereas aliasing a T*
> through an arbitrary S** is probably a bug.
>
> Just for contrast: I'm familiar with this problem, and my way around
> this comes in a few parts. I check pointer creation (casts) only; checks
> on pointer use (dereference) are unnecessary. Usually it takes a while
> before people believe me on this, but the short story is that
> pointer-creation checks enforce an invariant that no bad-type pointer
> gets into circulation. So dereferences are always okay (until the first
> warning, at least; execution can continue after a warning, in a
> best-effort no-guarantees fashion). This also greatly helps performance.
I'm sure this is true, but the problem is that C/C++ don't actually
outlaw such pointer casts. As you also mention below, it only becomes a
problem if such pointers are used to access an object of some
incompatible type. If the sanitizer has false positives then it is not
nearly as useful to me, even though the technique you describe might
actually find more bugs. They seems like complementary techniques.
My goal is the former, although I certainly believe there is also value
in the latter.
>
> Plenty of pointer bugs are not UB... e.g. for any heap allocation
> ("object without a declared type", in C11-speak) I'm allowed to scribble
> over it, thereby changing its effective type. It's only UB if I read it
> with its previous effective type.
Yes.
> But the scribbling itself is fairly
> likely to be the bug,
Agreed. However, there are also legitimate use cases, and
implementations of standard types (variant, any, etc.) may actually do this.
> because programmers rarely want to change the type
> of an allocation mid-lifetime. Meanwhile, many pointer-type problems are
> too indirect or complex for the compiler to actually do TBAA-derived
> optimisation on, leaving little to be gained from the UB/TBAA point of
> view... but again, plenty from the debugging perspective. I suspect the
> biggest value of any tool, even if geared specifically towards TBAA,
> will turn out to be largely in debugging scenarios more general than
> effective-type UB bugs.
My motivation is to help people who are currently forced to build their
code with -fno-strict-aliasing figure out what needs to be fixed in
their code so they don't need to do that.
>
> I realise all the above might come across as "here's the problem I'd
> solve instead" which may not be helpful... I'm interested by any tool in
> this general space, so looking forward to hearing more, and happy to
> follow up on any of the above,
This was good feedback. Your work is indeed focused on a slightly
different problem. It could be interesting and useful to have both.
Thanks,
Hal
>
> Stephen.
>
> PS: on top of the EuroLLVM '16 talk, in case you're wondering about how
> my system works, the following research papers might help. Or feel free
> just to ask questions....
>
> - "Dynamically diagnosing run-time type errors in unsafe code" (OOPSLA '16)
> <http://www.cl.cam.ac.uk/~srk31/#oopsla16a>
>
> - "Towards a dynamic object model within Unix processes" (Onward '15)
> <http://www.cl.cam.ac.uk/~srk31/#onward15>
>
> ... or code if you prefer:
> <https://github.com/stephenrkell/liballocs>
> <https://github.com/stephenrkell/libcrunch>
> <https://github.com/chrisdiamand/clangcrunch>.
--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory
_______________________________________________
Hal Finkel via llvm-dev
struct {Hi Hal,I wonder how your solution will handle the following?
int s1_f1;
float s1_f2;
int s1_f3;
float s1_f4;} S1;
struct {
int s2_f1;
float s2_f2;
int *s2_f3; // to add some interest, suppose that sizeof(int) == sizeof(int *)
float s2_f4;} S2;
S1 *s1; S2 *s2;
...
s2 = (S1*)s1;
s2->s2_f1 = 0; // allowed
s2->s2_f2 = 0; // allowed
s2->s2_f3 = 0; // not allowed
s2->s2_f4 = 0; // not allowed
Also, when you plan to set types for allocated memory?
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).
What types will be set for memory allocated by a malloc call?
Thanks again,
Hal
Andrey Bokhanko via llvm-dev
===
Daniel Berlin via llvm-dev
void f(s1 *s1p, s2 *s2p) {
Hal Finkel via llvm-dev
Hal,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).
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?
-Hal
Kostya Serebryany via llvm-dev
Peter Collingbourne via llvm-dev
Sanjoy Das via llvm-dev
On April 11, 2017 at 11:55:12 AM, Kostya Serebryany via llvm-dev
(llvm...@lists.llvm.org) wrote:
> Evgeniy and I recently discussed something similar for detecting bad casts
> (code named: TypeSanitizer).
> The approach with the shadow memory looked attractive at the first glance,
> but then we've drowned in details.
>
> Specifically for TBAA, I had another idea, not involving shadow memory.
> Consider LLVM queries MayAlias(P1, P2) and the result is false, i.e. we
> think that P1 and P2 point to disjoint memory regions.
> Then we insert a run-time check that intervals [P1,sizeof(*P1)) and
> [P2,sizeof(*P2)) don't intersect.
>
> For functions with a reasonable number of pointer pairs where MayAlias(P1,
> P2)==false we could insert checks for all such pairs.
I'm not very clear on how this will fit into TBAA -- I don't think
TBAA decides aliasing relation between pointers, but it decides
aliasing relation between accesses (!tbaa metadata only exists on
accesses).
This means, at least in LLVM IR, you have to account for cases like:
if (A)
*(int *)ptr = 20;
if (B)
float f = *(float *)ptr;
where ptr does not have a type (according to TBAA), but you want to
crash the program if both A and B are true.
-- Sanjoy
Kostya Serebryany via llvm-dev
Hi,
On April 11, 2017 at 11:55:12 AM, Kostya Serebryany via llvm-dev
(llvm...@lists.llvm.org) wrote:
> Evgeniy and I recently discussed something similar for detecting bad casts
> (code named: TypeSanitizer).
> The approach with the shadow memory looked attractive at the first glance,
> but then we've drowned in details.
>
> Specifically for TBAA, I had another idea, not involving shadow memory.
> Consider LLVM queries MayAlias(P1, P2) and the result is false, i.e. we
> think that P1 and P2 point to disjoint memory regions.
> Then we insert a run-time check that intervals [P1,sizeof(*P1)) and
> [P2,sizeof(*P2)) don't intersect.
>
> For functions with a reasonable number of pointer pairs where MayAlias(P1,
> P2)==false we could insert checks for all such pairs.
I'm not very clear on how this will fit into TBAA -- I don't think
TBAA decides aliasing relation between pointers, but it decides
aliasing relation between accesses (!tbaa metadata only exists on
accesses).
Sanjoy Das via llvm-dev
On April 11, 2017 at 1:30:10 PM, Kostya Serebryany (k...@google.com) wrote:
> of course, but accesses are done via pointers, and if TBAA queries
> MayAlias(AccessViaP1, AccessViaP2)
> there should (??) be a point in the IR where both P1 and P2 exist together
> and can be compared.
That may not be possible (though I'm second guessing what exactly you
have in mind so maybe I'm missing something here):
ptr0 = malloc();
*(int*)ptr0 = 20; // access0
free(ptr0);
ptr1 = calloc(); // bitwise equal to ptr0 by chance
float f = *(float *)ptr1; // access1
The program above is fine (no TBAA violations), but at location
access1 ptr1 and ptr0 overlap despite being NoAlias.
-- Sanjoy
Sanjoy Das via llvm-dev
On April 11, 2017 at 1:37:20 PM, Sanjoy Das
(san...@playingwithpointers.com) wrote:
> Hi Kostya,
>
> On April 11, 2017 at 1:30:10 PM, Kostya Serebryany (k...@google.com) wrote:
>
> > of course, but accesses are done via pointers, and if TBAA queries
> > MayAlias(AccessViaP1, AccessViaP2)
> > there should (??) be a point in the IR where both P1 and P2 exist together
> > and can be compared.
>
> That may not be possible (though I'm second guessing what exactly you have in mind so maybe
> I'm missing something here):
>
> ptr0 = malloc();
> *(int*)ptr0 = 20; // access0
> free(ptr0);
> ptr1 = calloc(); // bitwise equal to ptr0 by chance
> float f = *(float *)ptr1; // access1
>
> The program above is fine (no TBAA violations), but at location access1 ptr1 and ptr0
> overlap despite being NoAlias.
Actually this isn't specific to TBAA. Even without TBAA we mark
malloc's return value as NoAlias, so in
ptr0 = malloc();
free(ptr0);
ptr1 = malloc();
ptr0 and ptr1 will be NoAlias despite overlapping (there is actually a
real soundness issue here in LLVM's semantics, but I don't want to
digress). You can also recreate the pattern with realloc.
The same problem exists with constant addresses. LLVM states that
constant locations are noalias with themselves, and you again have the
"noalias does not imply pointer inequality" problem.
-- Sanjoy
Kostya Serebryany via llvm-dev
Hi,
On April 11, 2017 at 1:37:20 PM, Sanjoy Das
(sanjoy@playingwithpointers.com) wrote:
> Hi Kostya,
>
> On April 11, 2017 at 1:30:10 PM, Kostya Serebryany (k...@google.com) wrote:
>
> > of course, but accesses are done via pointers, and if TBAA queries
> > MayAlias(AccessViaP1, AccessViaP2)
> > there should (??) be a point in the IR where both P1 and P2 exist together
> > and can be compared.
>
> That may not be possible (though I'm second guessing what exactly you have in mind so maybe
> I'm missing something here):
>
> ptr0 = malloc();
> *(int*)ptr0 = 20; // access0
> free(ptr0);
> ptr1 = calloc(); // bitwise equal to ptr0 by chance
> float f = *(float *)ptr1; // access1
>
> The program above is fine (no TBAA violations), but at location access1 ptr1 and ptr0
> overlap despite being NoAlias.
Actually this isn't specific to TBAA. Even without TBAA we mark
malloc's return value as NoAlias, so in
ptr0 = malloc();
free(ptr0);
ptr1 = malloc();
ptr0 and ptr1 will be NoAlias despite overlapping (there is actually a
real soundness issue here in LLVM's semantics, but I don't want to
digress). You can also recreate the pattern with realloc.
The same problem exists with constant addresses. LLVM states that
constant locations are noalias with themselves, and you again have the
"noalias does not imply pointer inequality" problem.
Sanjoy Das via llvm-dev
On April 11, 2017 at 2:39:44 PM, Kostya Serebryany (k...@google.com) wrote:
> > ptr0 = malloc();
> > free(ptr0);
> > ptr1 = malloc();
> >
> > ptr0 and ptr1 will be NoAlias despite overlapping (there is actually a
> > real soundness issue here in LLVM's semantics, but I don't want to
> > digress). You can also recreate the pattern with realloc.
> >
>
> In both of your examples there is no place in the program where both P0 and
> P1 are live simultaneously,
> i.e. no analysis path is expected to query MayAlias(AccessToP0,
> AccessToP1). No?
I may be misunderstanding what you meant, but I don't see why not.
Say you had (all values are SSA values):
%p0 = malloc()
store i32 0, i32* %p0 // S0
free(%p0)
%p1 = malloc()
store i32 1, i32* %p1 // S1
and some pass wanted to sink S0 to after S1. So it starts checking
"from the bottom", as
Alias(S0, S1) = NoAlias
Alias(S0, malloc()) = NoAlias
Alias(S0, free(%p0)) = MayAlias
etc. The last MayAlias will prevent it from doing the sink, but I
don't see why it can't ask the Alias(S0, S1) question.
> > The same problem exists with constant addresses. LLVM states that
> > constant locations are noalias with themselves, and you again have the
> > "noalias does not imply pointer inequality" problem.
>
> That won't even have to be special cased, because if we emit a check
> ConstPtr != ConstPtr,
> such a check will be trivially optimized away.
But won't it be constant folded to trigger the sanitizer crash /
warning? That is, since LLVM will state the ConstPtr NoAlias
ConstPtr, you'll emit the check:
if (overlap(ConstPtr, Sz, ConstPtr, Sz))
abort();
which will get constant folded to
if (true) abort();
If you meant that the implementation of overlap will differ based on
whether the pointers are constant pointers or not, I'm not sure if
that will work, since the fact that the values whose aliasness (I
think I invented a new word :P ) you're checking could have been
arbitrarily obscured (AA could have looked through PHIs and selects
etc.) which will prevent you from rediscovering that the values were
constant pointers in some cases.
-- Sanjoy
Kostya Serebryany via llvm-dev
> > The same problem exists with constant addresses. LLVM states that
> > constant locations are noalias with themselves, and you again have the
> > "noalias does not imply pointer inequality" problem.
>
> That won't even have to be special cased, because if we emit a check
> ConstPtr != ConstPtr,
> such a check will be trivially optimized away.
But won't it be constant folded to trigger the sanitizer crash /
warning? That is, since LLVM will state the ConstPtr NoAlias
ConstPtr, you'll emit the check:
if (overlap(ConstPtr, Sz, ConstPtr, Sz))
abort();
which will get constant folded to
if (true) abort();
Sanjoy Das via llvm-dev
> On Tue, Apr 11, 2017 at 3:14 PM, Sanjoy Das
But that the problem right -- AA told you that S0 and S1 *are* okay to
reorder. In fact, if your original program would have been:
p0 = malloc()
free(p0)
p1 = malloc()
*p0 = 20 // S0
*p1 = 20 // S1
then S0 and S1 would have been okay to reorder (since the original
program has UB). But you cannot assert !overlap(p0, p1) in the well
defined program I mentioned earlier.
-- Sanjoy
>
>
>
> >
> > > > The same problem exists with constant addresses. LLVM states that
> > > > constant locations are noalias with themselves, and you again have the
> > > > "noalias does not imply pointer inequality" problem.
> > >
> > > That won't even have to be special cased, because if we emit a check
> > > ConstPtr != ConstPtr,
> > > such a check will be trivially optimized away.
> >
> > But won't it be constant folded to trigger the sanitizer crash /
> > warning? That is, since LLVM will state the ConstPtr NoAlias
> > ConstPtr, you'll emit the check:
> >
> > if (overlap(ConstPtr, Sz, ConstPtr, Sz))
> > abort();
> >
> > which will get constant folded to
> >
> > if (true) abort();
> >
>
> ah, yes, you are right, then this will have to be special-cased.
>
>
> >
> > If you meant that the implementation of overlap will differ based on
> > whether the pointers are constant pointers or not, I'm not sure if
> > that will work, since the fact that the values whose aliasness (I
> > think I invented a new word :P ) you're checking could have been
> > arbitrarily obscured (AA could have looked through PHIs and selects
> > etc.) which will prevent you from rediscovering that the values were
> > constant pointers in some cases.
> >
> > -- Sanjoy
> >
>
Kostya Serebryany via llvm-dev
Sanjoy Das via llvm-dev
On Tue, Apr 11, 2017 at 5:45 PM, Kostya Serebryany <k...@google.com> wrote:
>> p0 = malloc()
>> free(p0)
>> p1 = malloc()
>> *p0 = 20 // S0
>> *p1 = 20 // S1
>>
>> then S0 and S1 would have been okay to reorder (since the original
>> program has UB). But you cannot assert !overlap(p0, p1) in the well
>> defined program I mentioned earlier.
>
>
> Yea.. tricky...
> Well, if we combine this kind of checking with asan your particular problem
> is gone (because asan has quarantine for free-d memory and it won't be
> reused immediately)
I'm not sure if the problem is *gone* (since IIUC ASan will eventually
re-use the memory), but yes it will happen less often.
-- Sanjoy
>
>
>>
>>
>> -- Sanjoy
>>
>> >
>> >
>> >
>> > >
>> > > > > The same problem exists with constant addresses. LLVM states that
>> > > > > constant locations are noalias with themselves, and you again have
>> > > > > the
>> > > > > "noalias does not imply pointer inequality" problem.
>> > > >
>> > > > That won't even have to be special cased, because if we emit a check
>> > > > ConstPtr != ConstPtr,
>> > > > such a check will be trivially optimized away.
>> > >
>> > > But won't it be constant folded to trigger the sanitizer crash /
>> > > warning? That is, since LLVM will state the ConstPtr NoAlias
>> > > ConstPtr, you'll emit the check:
>> > >
>> > > if (overlap(ConstPtr, Sz, ConstPtr, Sz))
>> > > abort();
>> > >
>> > > which will get constant folded to
>> > >
>> > > if (true) abort();
>> > >
>> >
>> > ah, yes, you are right, then this will have to be special-cased.
>> >
>> >
>> > >
>> > > If you meant that the implementation of overlap will differ based on
>> > > whether the pointers are constant pointers or not, I'm not sure if
>> > > that will work, since the fact that the values whose aliasness (I
>> > > think I invented a new word :P ) you're checking could have been
>> > > arbitrarily obscured (AA could have looked through PHIs and selects
>> > > etc.) which will prevent you from rediscovering that the values were
>> > > constant pointers in some cases.
>> > >
>> > > -- Sanjoy
>> > >
>> >
>
>
Stephen Kell via llvm-dev
> >>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.
> >Slightly provocative question, but are you sure that byte-scale shadow
> >memory is a good fit?
>
> Am I sure? No. But I *think* that is because I'd like to avoid false
> positives, and that means dealing with places where we dynamically change
> the type of part of an allocation (via placement new or whatever). This
> certainly seems necessary to deal with some C++ containers at least.
(Sorry for the delayed response. Short summary is "I agree with you" but
wanted to pick some nits/details anyway. :-)
Can you elaborate on the C++ containers thing? If it's just std::variant
and things like std::any that use aligned_storage_t, then see below.
The dynamically-changing-types thing seems to work okay in both cases.
In my runtime it is possible to change the recorded type of a heap
allocation, and to create new types at run time. So there are levers to
deal with the "part of an allocation" thing, though it does get a bit
ugly. (At present, a bit more engineering is necessary to support this
trick for stack objects, e.g. to do placement new on them... but I see
no real problem supporting it.)
I can see the simplicity benefits of shadow memory, so I'm not arguing
too hard against it -- just feeling my way around the issues....
> >Just so I'm understanding: is this talking about shadowing memory with
> >its "leaf" type only, or with its "top-level" type? So if I have, say,
> >the following usually-64-bit type:
> >
> >struct compound { int x; float y; }
> >
> >... would we paint the shadow area with an alternating pattern of int
> >(0110 0110) and floats (0110 1001)? Or would we be using the "all other
> >types" thing since the memory is actually "compound"?
>
> I intended to imply that we'd fill with the alternating pattern indicating
> int and float.
Understood.
I'm now scratching my head about whether that sacrifices the ability to
detect UB where the problematic "access" is of a composite type. Passing
a struct to a function is a kind of access that comes to mind. (I'm
wavering about "object" versus "subobject", a distinction which I have
never properly understood in C11....)
> >>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.
> >Aha, the pointers-to-pointers problem. Treating all pointers the same
> >feels like a mistake because, say, aliasing a T* through a void** is
> >frequently done and really quite useful (although technically UB, if I
> >understand correctly; is this exploited in LLVM?
>
> I don't know if it is exploited by LLVM, although as I recall, all
> implementations of posix_memalign and similar functions potentially run
> afoul of the rules (because they need to store the new pointer as a void*
> regardless of what it actually is).
I think returning a pointer like posix_memalign() does it is okay -- the
client just has to declare the written-to pointer as a void*. If they
want a different type of pointer, they have to do a cast/assignment
after the call. So it's clients that are in danger of UB here... they
might use it the sloppy way, by casting a T** to void**. Of course,
*not* doing this gets tedious in some cases, e.g. when calling generic
linked-structure routines written in C.
> I'm not sure how strict we can be here
> in practice. Currently, AFAIKT, Clang emits TBAA metadata which does not
> differentiate between pointer types (it calls them all "any pointer").
Interesting -- I should take a look at this (thanks).
> >), whereas aliasing a T*
> >through an arbitrary S** is probably a bug.
> >
> >Just for contrast: I'm familiar with this problem, and my way around
> >this comes in a few parts. I check pointer creation (casts) only; checks
> >on pointer use (dereference) are unnecessary. Usually it takes a while
> >before people believe me on this, but the short story is that
> >pointer-creation checks enforce an invariant that no bad-type pointer
> >gets into circulation. So dereferences are always okay (until the first
> >warning, at least; execution can continue after a warning, in a
> >best-effort no-guarantees fashion). This also greatly helps performance.
>
> I'm sure this is true, but the problem is that C/C++ don't actually outlaw
> such pointer casts. As you also mention below, it only becomes a problem if
> such pointers are used to access an object of some incompatible type. If the
> sanitizer has false positives then it is not nearly as useful to me, even
> though the technique you describe might actually find more bugs.
Fair point. For what it's worth, I do also care a lot about minimising
false positives, and there's a trick I should have mentioned: issuing a
"trap pointer" when a bad cast occurs, to delay warnings until it's
used. On x86-64 this just means flipping some high-order bits so we get
a non-canonical address that can be losslessly converted back to the
real address. Trap bits are erased for pointer comparisons, or on casts
back to a good type. If a trap pointer is used (definitely a bug!), the
segfault handler generates a sensible warning message, decodes the
faulting instruction, "de-traps" the relevant pointer in the saved
register file, and resumes the program. (This could work a bit better
than it currently does; happy to elaborate.)
> >>Thoughts?
> >My high-level thought is the following question. Is the plan fixed on
> >developing a tool specifically for C/C++ effective-type rules, i.e.
> >focused on catching/fixing those particular cases of UB and with the
> >goal of improving user code performance? Or is there any interest in the
> >overlapping but distinct problem of helping users detect and debug
> >bad-pointer problems of a type flavour (i.e. those that are not bounds
> >errors or temporal errors)?
>
> My goal is the former, although I certainly believe there is also value in
> the latter.
Understood.
> >Plenty of pointer bugs are not UB... e.g. for any heap allocation
> >("object without a declared type", in C11-speak) I'm allowed to scribble
> >over it, thereby changing its effective type. It's only UB if I read it
> >with its previous effective type.
>
> Yes.
>
> > But the scribbling itself is fairly
> >likely to be the bug,
>
> Agreed. However, there are also legitimate use cases, and implementations of
> standard types (variant, any, etc.) may actually do this.
I agree that there is some risk of false positives here, but I think the
range of problematic code is really small and does not include the cases
you mention.
The core issue is whether type-changing writes should need to be flagged
specially in the code somehow, allowing them to be instrumented
appropriately, or whether arbitrary writes must be able to silently
change effective types. A 100% faithful adherence to standard C does
require the latter. However, I don't think C++ std::variant or std::any
are examples of code that do this, because they pretty much have to use
unions and/or placement new, which are both ways of doing the
flagging.
I do know some C code that relies on silently type-changing writes. In
fact in SPEC CPU2006 alone there are two cases -- one in bzip2, one in
lbm. The lbm case is bonkers and really should be a union. In the bzip2
case it is arguably sane; my tentative fix is to add a realloc() on the
heap array with a different type but the same size -- basically my
hacked-up C version of signalling a "placement new".
In general, relying on the "no declared type" property of heap storage
is pretty fragile, because code suddenly becomes UB if you refactor it
so that a heap object becomes a stack or static object. So asking users
to manually suppress these warnings doesn't seem unreasonable to me,
just as writing your own memcpy() would do... although no doubt opinions
differ.
(I admit I haven't tried much C++ or standard-library code yet with my
system. Also, for full disclosure: currently I do not have great support
for unions... although it errs on the side of avoiding false positives,
and I think I've figured out how it can be made to work precisely.)
> > because programmers rarely want to change the type
> >of an allocation mid-lifetime. Meanwhile, many pointer-type problems are
> >too indirect or complex for the compiler to actually do TBAA-derived
> >optimisation on, leaving little to be gained from the UB/TBAA point of
> >view... but again, plenty from the debugging perspective. I suspect the
> >biggest value of any tool, even if geared specifically towards TBAA,
> >will turn out to be largely in debugging scenarios more general than
> >effective-type UB bugs.
>
> My motivation is to help people who are currently forced to build their code
> with -fno-strict-aliasing figure out what needs to be fixed in their code so
> they don't need to do that.
Thanks for the clarification.
> This was good feedback. Your work is indeed focused on a slightly different
> problem. It could be interesting and useful to have both.
I will happily agree with this, despite the above nitpicks. :-) And (no
obligation but) I'd love to be directed towards any further
problematic/awkward code not covered by the above.
Stephen
Andrey Bokhanko via llvm-dev
===
Hal Finkel via llvm-dev
Evgeniy and I recently discussed something similar for detecting bad casts (code named: TypeSanitizer).The approach with the shadow memory looked attractive at the first glance, but then we've drowned in details.
Specifically for TBAA, I had another idea, not involving shadow memory.Consider LLVM queries MayAlias(P1, P2) and the result is false, i.e. we think that P1 and P2 point to disjoint memory regions.Then we insert a run-time check that intervals [P1,sizeof(*P1)) and [P2,sizeof(*P2)) don't intersect.
For functions with a reasonable number of pointer pairs where MayAlias(P1, P2)==false we could insert checks for all such pairs.For larger functions -- only for those pairs where the optimizer actually queried MayAlias(P1, P2).
The overlap checks could certainly suffer from the lifetime/memory-reuse issue that's been discussed, although that never same up in practice in my tests. I should add, however, that the compile-time overhead of inserting the checks, even just using the pre-recorded checks, was large. There are a lot of AA checks, even restricting to the intra-BB checks as done by the instruction scheduler; including other passes would only make that grow.
-Hal
Hal Finkel via llvm-dev
>>>> 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.
>>> Slightly provocative question, but are you sure that byte-scale shadow
>>> memory is a good fit?
>> Am I sure? No. But I *think* that is because I'd like to avoid false
>> positives, and that means dealing with places where we dynamically change
>> the type of part of an allocation (via placement new or whatever). This
>> certainly seems necessary to deal with some C++ containers at least.
> (Sorry for the delayed response. Short summary is "I agree with you" but
> wanted to pick some nits/details anyway. :-)
>
> Can you elaborate on the C++ containers thing? If it's just std::variant
> and things like std::any that use aligned_storage_t, then see below.
Those are what come to mind (although in general it is legal to
partially end the lifetime of an allocated array by placement-newing
over parts of it).
>
> The dynamically-changing-types thing seems to work okay in both cases.
> In my runtime it is possible to change the recorded type of a heap
> allocation, and to create new types at run time. So there are levers to
> deal with the "part of an allocation" thing, though it does get a bit
> ugly. (At present, a bit more engineering is necessary to support this
> trick for stack objects, e.g. to do placement new on them... but I see
> no real problem supporting it.)
>
> I can see the simplicity benefits of shadow memory, so I'm not arguing
> too hard against it -- just feeling my way around the issues....
>
>>> Just so I'm understanding: is this talking about shadowing memory with
>>> its "leaf" type only, or with its "top-level" type? So if I have, say,
>>> the following usually-64-bit type:
>>>
>>> struct compound { int x; float y; }
>>>
>>> ... would we paint the shadow area with an alternating pattern of int
>>> (0110 0110) and floats (0110 1001)? Or would we be using the "all other
>>> types" thing since the memory is actually "compound"?
>> I intended to imply that we'd fill with the alternating pattern indicating
>> int and float.
> Understood.
>
> I'm now scratching my head about whether that sacrifices the ability to
> detect UB where the problematic "access" is of a composite type. Passing
> a struct to a function is a kind of access that comes to mind. (I'm
> wavering about "object" versus "subobject", a distinction which I have
> never properly understood in C11....)
Yea. I'm currently concerned that this compact scheme does not really
work because it can't capture the semantics contained in our struct-path
TBAA (which is, I believe, equivalent to your point here), which means
that we might not catch violations of properties on which the optimizer
might otherwise rely.
This makes sense. Thanks for mentioning this.
Good point.
Me too :-) - We might find out...
-Hal
>
> Stephen
--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory
_______________________________________________
Hal Finkel via llvm-dev
While not using the compressed shadow representation discussed here,
mostly because it can't handle the struct-path (offset) information in
our TBAA, I've posted patches for an initial TBAA sanitizer implementation:
https://reviews.llvm.org/D32197 (Runtime)
https://reviews.llvm.org/D32198 (LLVM)
https://reviews.llvm.org/D32199 (Clang)
Please try it out / review / etc.
-Hal
On 04/04/2017 03:13 PM, Hal Finkel wrote:
> Hi everyone,
>
> At EuroLLVM, Chandler and I chatted about the design for a potential
> TBAA sanitizer. Here's my attempt to summarize:
>
> 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.
>
> 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
> 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.
>
--