<div dir="ltr">One other thing: if this can be used for control-flow integrity, I assume it has to have good knowledge of the available indirect call targets. Could we also use this information for devirtualization?<div><br></div><div>-- Sean Silva</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Jan 27, 2015 at 1:07 PM, Peter Collingbourne <span dir="ltr"><<a href="mailto:peter@pcc.me.uk" target="_blank">peter@pcc.me.uk</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi all,<br>
<br>
I would like to propose a mechanism that allows IR modules to co-operatively<br>
build a pointer set corresponding to addresses within a given set of<br>
globals. The specific use case I have in mind is to provide a mechanism<br>
for a C++ program to efficiently verify (at each call site) that a vtable<br>
pointer is in the set of valid vtable pointers for the class or its derived<br>
classes. One way of doing this is for a toolchain component to build, for each<br>
class, a bit set that maps to the memory region allocated for the vtables,<br>
such that each 1 bit in the bit set maps to a valid vtable for that class,<br>
and lay out the vtables next to each other, to minimize the total size of<br>
the bit sets. Call sites would perform a range check followed by a load of<br>
the appropriate bit from the bit set.<br>
<br>
To give a concrete example, suppose we have the following classes:<br>
<br>
struct A { virtual void f(); };<br>
struct B : A { virtual void f(), g(); };<br>
struct C : A { virtual void f(), h(); };<br>
<br>
with the following vtables:<br>
<br>
_ZTV1A = { &A::rtti, &A::f };<br>
_ZTV1B = { &B::rtti, &B::f, &B::g };<br>
_ZTV1C = { &C::rtti, &C::f, &C::h };<br>
<br>
The set of valid vtables for static class A is {&_ZTV1A[1], &_ZTV1B[1],<br>
&_ZTV1C[1]}, for B is {&_ZTV1B[1]} and for C is {&_ZTV1C[1]}. The toolchain<br>
would lay out _ZTV1A, _ZTV1B and _ZTV1C consecutively, and generate bit sets<br>
like this:<br>
<br>
A = {0,1,0,1,0,0,1,0}<br>
B = {0,0,0,1,0,0,0,0}<br>
C = {0,0,0,0,0,0,1,0}<br>
<br>
A call site (say the static type of the call is A) will check whether the<br>
object's vtable falls in the range [_ZTV1A, _ZTV1C], and is sizeof(void<br>
*)-aligned. It would then load the (vtable-_ZTV1A)/sizeof(void *)'th entry<br>
in A's bitset, which will be 1 if the vtable is valid for A.<br>
<br>
We are now faced with a number of implementation questions: how do we represent<br>
these (potentially partial) bit sets in LLVM, and how do we arrange to lay<br>
out the globals and build the complete bit sets? Remember that classes B<br>
and C may be in different translation units, so we do not necessarily have<br>
a complete picture of A's bit set at A's compile time.<br>
<br>
What I propose is that the parts of the bit sets be represented as arrays<br>
of pointers, which will be resolved through some mechanism (either at<br>
LTO time, or at regular (non-LTO) link time) to bit sets corresponding to<br>
those addresses. This mechanism would also be responsible for laying out<br>
the referenced globals (i.e. the vtables) as close together as possible. We<br>
introduce a new flag on globals, the so-called "bitset" flag, which causes<br>
the global to be transformed using this mechanism. Such a global cannot be<br>
accessed in the normal way. It may only be accessed using an intrinsic that<br>
tests whether a given pointer is in the set.<br>
<br>
To return to our concrete example, a translation unit defining the vtable<br>
for A may also define the following global:<br>
<br>
@_ZBS1A = appending bitset constant [1 x i8*] [gep(@_ZTV1A, 0, 1)]<br>
<br>
A translation unit defining B would define:<br>
<br>
@_ZBS1A = appending bitset constant [1 x i8*] [gep(@_ZTV1B, 0, 1)]<br>
@_ZBS1B = appending bitset constant [1 x i8*] [gep(@_ZTV1B, 0, 1)]<br>
<br>
And C:<br>
<br>
@_ZBS1A = appending bitset constant [1 x i8*] [gep(@_ZTV1C, 0, 1)]<br>
@_ZBS1C = appending bitset constant [1 x i8*] [gep(@_ZTV1C, 0, 1)]<br>
<br>
A later mechanism would combine the bitset globals, lay out the referenced<br>
globals and build the bit sets. In the LTO case, the IR linker can already<br>
do the combination step if the globals are given appending linkage. A<br>
later compiler pass (which we will call the "bitset lowering pass") would lay out<br>
the globals (by combining them into a single large global, and RAUWing the<br>
original globals with aliases that gep into the large global) and build the<br>
bit sets. In the non-LTO case, we could also invent an object-file-specific<br>
mechanism for the backend to tell the linker to combine and build the bit sets,<br>
for example by placing the bitset globals in a specifically named section,<br>
and place the referenced globals in individual sections so that the linker<br>
can rearrange them.<br>
<br>
As previously mentioned, an intrinsic would be used to test entries in the<br>
bit set at call sites. For example, the relevant IR for the following C++ code:<br>
<br>
A *some_object = ...;<br>
some_object->f();<br>
<br>
might look like this:<br>
<br>
%vtable = load i8** %some_object<br>
%p = call i1 @llvm.bitset.test(i8* %vtable, i8* @_ZBS1A) readnone<br>
br i1 %p, label %continue, label %trap<br>
<br>
In the LTO case, such intrinsic calls would be lowered by the bitset lowering pass<br>
into the appropriate range/bit set check code, which might look like this:<br>
(pseudocode for 64-bit platform)<br>
<br>
if %vtable & 7 != 0 || %vtable < global_start_addr(_ZBS1A) || %vtable > global_end_addr(_ZBS1A) {<br>
  %p = 0<br>
} else {<br>
  %p = bitset(_ZBS1A)[(%vtable - global_start_addr(_ZBS1A)) >> 3]<br>
}<br>
<br>
In the non-LTO case, we would generate similar code, but with appropriate<br>
relocations so that the required constants (global start/end address, bitset<br>
address, mask, shift amount) would receive appropriate linker-determined<br>
values.<br>
<br>
The first step I propose to make in this direction is a patch that adds<br>
support for the bitset flag on globals, and introduces the bitset lowering pass. A<br>
later step would involve building backend support, and linker support in lld.<br>
<br>
Comments appreciated.<br>
<br>
Thanks,<br>
<span class="HOEnZb"><font color="#888888">--<br>
Peter<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</font></span></blockquote></div><br></div>