<div dir="ltr">Hi all,<div><br></div><div>As promised, here is a brain dump on how I see CFI for vcalls working under ThinLTO. Most of this has been prototyped, so the design does appear to be sound. For context on how CFI currently works under regular LTO, please read:</div><div><br></div><div><a href="http://llvm.org/docs/TypeMetadata.html">http://llvm.org/docs/TypeMetadata.html</a><br></div><div><a href="http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html">http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html</a></div><div><a href="http://clang.llvm.org/docs/LTOVisibility.html">http://clang.llvm.org/docs/LTOVisibility.html</a></div><div><br></div><div>==== Summary extensions ====</div><div><br></div><div>The combined summary index would be extended to include a mapping from type identifiers to "resolutions". The resolution would control what type of code we generate to create a CFI check for that type identifier. Here are the resolutions that we would support:</div><div><br></div><div>Inline32, Inline64, SingleBit: these would cause us to generate code as described in "Short Inline Bit Vectors" in the design document: <a href="http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html#short-inline-bit-vectors">http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html#short-inline-bit-vectors</a><br></div><div>AllOnes: this would cause us to generate code as described in "Eliminating Bit Vector Checks for All-Ones Bit Vectors" in the design document: <a href="http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html#eliminating-bit-vector-checks-for-all-ones-bit-vectors">http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html#eliminating-bit-vector-checks-for-all-ones-bit-vectors</a></div><div><div>Unsat: no vtable is a member of that type identifier, so we can simply replace type checks for that type identifier with "false"</div><div>ByteArray: we emit the general form of the type check, similar to the one shown at the end of <a href="http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html#forward-edge-cfi-for-virtual-calls">http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html#forward-edge-cfi-for-virtual-calls</a> just before "Optimizations"</div><div><br></div><div>Armed with that information, we have a general idea of what the code to implement the type check would look like. In fact, given one of these values, the code will be identical to any other check that uses that resolution, modulo the constant values embedded in the code.</div><div><br></div><div>To expand on what I mean by "constant values", let's look at a typical CFI check in the ByteArray case. Consider this module (based on test/Transforms/LowerTypeTests/simple.ll):</div><div><br></div><div><div>@a = constant i32 1, !type !0, !type !2</div><div>@b = constant [63 x i32] zeroinitializer, !type !0, !type !1</div><div>@c = constant i32 3, !type !1, !type !2</div><div>@d = constant [2 x i32] [i32 4, i32 5], !type !3</div></div><div><div><br></div><div>!0 = !{i32 0, !"typeid1"}</div><div>!3 = !{i32 4, !"typeid1"}</div><div>!1 = !{i32 0, !"typeid2"}<br></div><div>!2 = !{i32 0, !"typeid3"}<br></div></div><div><br></div><div><div>define i1 @baz(i32* %p) {</div></div><div> %x = call i1 @llvm.type.test(i8* %pi8, metadata !"typeid3")<br></div><div> ret i1 %x</div><div>}</div><div><br></div><div>Here is the IR after the LowerTypeTests pass has run. I've marked the places where we use a constant value:</div><div><br></div><div><div>define i1 @baz(i32* %p) {</div><div> %pi8 = bitcast i32* %p to i8*</div><div> %1 = ptrtoint i8* %pi8 to i32</div><div> %2 = sub i32 %1, ptrtoint ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* @0 to i32)</div><div> %3 = lshr i32 %2, 2 ; CONSTANT: rotate count</div><div> %4 = shl i32 %2, 30 ; CONSTANT: 32-rotate count</div><div> %5 = or i32 %3, %4</div><div> %6 = icmp ult i32 %5, 66 ; CONSTANT: size of byte array</div><div> br i1 %6, label %7, label %12</div><div><br></div><div>; <label>:7: ; preds = %0</div><div> %8 = getelementptr i8, i8* @bits_use, i32 %5</div><div> %9 = load i8, i8* %8</div><div> %10 = and i8 %9, 2 ; CONSTANT: bit mask</div><div> %11 = icmp ne i8 %10, 0</div><div> br label %12</div><div><br></div><div>; <label>:12: ; preds = %0, %7</div><div> %13 = phi i1 [ false, %0 ], [ %11, %7 ]</div><div> ret i1 %13</div><div>}</div></div><div><br></div><div>Here is what the asm for the above looks like:</div><div><br></div><div><div>baz:</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>leaq<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>.L__unnamed_1(%rip), %rax<br></div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>subl<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>%eax, %edi</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>roll<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>$30, %edi ; CONSTANT: 32-rotate count</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>cmpl<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>$65, %edi ; CONSTANT: size of byte array</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>ja<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>.LBB2_1</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"><br></span></div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>movslq<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>%edi, %rax</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>leaq<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>.Lbits_use(%rip), %rcx</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>movb<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>(%rax,%rcx), %al</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>andb<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>$2, %al ; CONSTANT: bit mask</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>shrb<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>%al</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>retq</div><div>.LBB2_1:</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>xorl<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>%eax, %eax</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>retq</div></div><div><br></div><div>A naive summary encoding would map a type identifier to a tuple of (resolution, rotate count, size of byte array, bit mask), and pull the latter three out of the summary as constants. However, the disadvantage of hard coding the constants in the IR like this is that any change to one of the constants will invalidate any cache entry that depends on a constant value. For example, if I add a class to a hierarchy, that would most likely increase the size of the byte array, which may invalidate every cache entry containing a check for a class in that hierarchy. To avoid this, we only include resolutions in the summary and obtain the constants using absolute symbol references. Here is what the asm code may look like:</div><div><br></div><div><div>baz:</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>leaq<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>__typeid_typeid3_global_addr(%rip), %rax</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>subl<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>%eax, %edi</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>rorl<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>$__typeid_typeid3_rotate_count, %edi</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>cmpl<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>$__typeid_typeid3_size, %edi</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>ja<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>.LBB2_1</div><div><br></div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>movslq<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>%edi, %rax</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>leaq<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>__typeid_typeid3_byte_array(%rip), %rcx</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>movb<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>(%rax,%rcx), %al</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>andb<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>$__typeid_typeid3_bitmask, %al</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>shrb<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>%al</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>retq</div><div>.LBB2_1:</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>xorl<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>%eax, %eax</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>retq</div></div><div><br></div><div>The appropriate representation for this at the IR level is the subject of the RFC entitled 'Absolute or "fixed address" symbols as immediate operands'. We can imagine, though, that it could look something like this:</div><div><br></div><div>@__typeid_typeid3_rotate_count = external globalconst i8</div><div>@__typeid_typeid3_size = external globalconst i32</div><div>@__typeid_typeid3_bit_mask = external globalconst i8</div><div>@__typeid_typeid3_byte_array = external global i8</div><div><div>@__typeid_typeid3_global_addr = external global i8</div></div><div><br></div><div><div>define i1 @baz(i32* %p) {</div><div> %pi8 = bitcast i32* %p to i8*</div><div> %1 = ptrtoint i8* %pi8 to i32</div><div> %2 = sub i32 %1, ptrtoint (i8* @__typeid_typeid3_global_addr to i32)</div><div> %3 = lshr i32 %2, i8 @__typeid_typeid3_rotate_count</div><div> %4 = shl i32 %2, sub i8 (i8 32, i8 @__typeid_typeid3_rotate_count)</div><div> %5 = or i32 %3, %4 </div><div> %6 = icmp ult i32 %5, i32 @__typeid_typeid3_size</div><div> br i1 %6, label %7, label %12</div><div><br></div><div>; <label>:7: ; preds = %0</div><div> %8 = getelementptr i8, i8* @__typeid_typeid3_byte_array, i32 %5</div><div> %9 = load i8, i8* %8</div><div> %10 = and i8 %9, @__typeid_typeid3_bitmask</div><div> %11 = icmp ne i8 %10, 0</div><div> br label %12</div><div><br></div><div>; <label>:12: ; preds = %0, %7</div><div> %13 = phi i1 [ false, %0 ], [ %11, %7 ]</div><div> ret i1 %13</div><div>}</div></div><div><br></div><div>==== Getting resolutions into the summary ====</div><div><br></div><div>Now that we've looked at how code is generated for the individual modules, let's look at how the resolutions are computed and put into the summary.</div><div><br></div><div>The first step happens when we compile the translation unit with clang. I propose to change the bitcode format for any module that defines virtual tables with hidden LTO visibility. The bitcode would contain two modules: one to be compiled with regular LTO and the other to be compiled with ThinLTO. The regular LTO module would contain only the following:</div><div><ul><li>the definitions of those virtual tables that have hidden LTO visibility<br></li><li>the !type metadata for those virtual tables<br></li><li>a list of type tests required by the corresponding ThinLTO module, in a GlobalMDNode named "llvm.export.type.tests"</li></ul></div><div>The ThinLTO module would contain the rest of the original module.</div><div><br></div><div>For example, here is what the regular LTO module for our example above would look like:</div><div><br></div><div><div>@a = constant i32 1, !type !0, !type !2</div><div>@b = constant [63 x i32] zeroinitializer, !type !0, !type !1</div><div>@c = constant i32 3, !type !1, !type !2</div><div>@d = constant [2 x i32] [i32 4, i32 5], !type !3</div><div><br></div><div>!0 = !{i32 0, !"typeid1"}</div><div>!3 = !{i32 4, !"typeid1"}</div><div>!1 = !{i32 0, !"typeid2"}</div><div>!2 = !{i32 0, !"typeid3"}</div><div><br></div></div><div>!8 = !{!"typeid3"}<br></div><div>!llvm.export.type.tests = !{!8}</div><div><br></div><div>and here is the ThinLTO module:</div><div><br></div><div><div>define i1 @baz(i32* %p) {</div><div> %x = call i1 @llvm.type.test(i8* %pi8, metadata !"typeid3")</div><div> ret i1 %x</div><div>}</div></div><div><br></div><div>The regular LTO modules are merged and compiled in the usual way, so we would end up merging the type definitions together with the list of required data.</div><div><br></div><div>When the LowerTypeTests pass is given a module with the "llvm.export.type.tests" global MDNode, it "exports" each of the type identifiers mentioned in the MDNode by storing a resolution in the combined summary, and by creating definitions of each of the symbols that shall be required to satisfy the link time dependencies in the individual ThinLTO modules. Here is an example of what the combined module would look like:</div><div><br></div><div>@0 = [...] ; combined global for a, b, c and d</div><div>@bits = [...] ; combined global byte array</div><div><br></div><div><div>@__typeid_typeid3_global_addr = hidden alias i8, bitcast ({...}* @0 to i8*)</div><div>@__typeid_typeid3_rotate_count = hidden globalconst i8 2</div><div><div>@__typeid_typeid3_size = hidden globalconst i32 65</div></div><div>@__typeid_typeid3_byte_array = hidden alias i8, i8* @bits</div><div>@__typeid_typeid3_bit_mask = hidden globalconst i8 2</div></div><div><br></div><div>The ThinLTO backend processes would run after regular LTO, so they would have access to the resolutions in the summary. If the module summary is present, LowerTypeTests will "import" the appropriate type identifier by generating code containing external references to these symbols, as described previously.</div><div><br></div><div>Thanks,</div>-- <br><div class="gmail_signature"><div dir="ltr">-- <div>Peter</div></div></div>
</div></div>