[llvm-dev] [RFC] CFI for indirect calls with ThinLTO

Tue May 23 17:16:34 PDT 2017

On Tue, May 23, 2017 at 5:14 PM, Peter Collingbourne <peter at pcc.me.uk>
wrote:

>
>
> On Tue, May 23, 2017 at 4:39 PM, Evgenii Stepanov <
> eugeni.stepanov at gmail.com> wrote:
>
>> On Tue, May 16, 2017 at 4:33 PM, Evgenii Stepanov
>> <eugeni.stepanov at gmail.com> wrote:
>> > On Mon, May 15, 2017 at 6:44 PM, Peter Collingbourne <peter at pcc.me.uk>
>> wrote:
>> >> Thanks for sending this out. A few comments below.
>> >>
>> >> On Mon, May 15, 2017 at 5:17 PM, Evgenii Stepanov via llvm-dev
>> >> <llvm-dev at lists.llvm.org> wrote:
>> >>>
>> >>> Hi,
>> >>>
>> >>> this is a proposal for the implementation of CFI-icall [1] with
>> ThinLTO.
>> >>>
>> >>> Jumptables are generated in the merged module. To generate a
>> >>> jumptable, we need a list of functions with !type annotations,
>> >>> including (in non-cross-dso mode) external functions. Unfortunately,
>> >>> LLVM IR does not preserve unused function declarations, and we don’t
>> >>> want to copy the actual function bodies to the merged module.
>> >>>
>> >>> Indirect call targets can be represented in the following way using
>> >>> named metadata:
>> >>>
>> >>> void foo() {}
>> >>> int bar() { return 0; }
>> >>>
>> >>> # Merged module
>> >>> !cfi.functions = !{!1, !3}
>> >>> !1 = !{!"bar", i8 0, !2}
>> >>> !2 = !{i64 0, !"_ZTSFiE"}
>> >>> !3 = !{!"foo", i8 0, !4}
>> >>> !4 = !{i64 0, !"_ZTSFvE"}
>> >>
>> >>
>> >> Presumably there would be no entries in !cfi.functions for functions
>> defined
>> >> in the merged module, as the type metadata would come from the module
>> >> itself.
>> >
>> > Right. The same as with vtable CFI, LowerTypeTests will use
>> > !cfi.functions in addition to the regular logic.
>> >
>> >>>
>> >>>
>> >>> Each function is described by a tuple of
>> >>> * Promoted name as a string
>> >>
>> >>
>> >> I imagine that we would only promote a function if it is address-taken.
>> >> Otherwise we could be inhibiting optimization significantly.
>> >
>> > Yes. Cfi.functions would include all external functions +
>> > address-taken internal functions. We could also do global analysis
>> > (i.e. skip jumptable for hidden non-address-taken functions), but that
>> > needs more information passed to the combined module (or summary).
>> >
>> >>
>> >>> * Linkage (see below)
>> >>> * Type(s)
>> >>>
>> >>>
>> >>> A function can have multiple types. In the Cross-DSO mode each
>> >>> function has a second “external” numeric type, and we might want to
>> >>> allow “relaxed” type checking in the future where a function could
>> >>> conform to multiple types. In that case the metadata would look like
>> >>> this:
>> >>>
>> >>> !4 = !{!"bar", i8 0, !5, !6}
>> >>> !5 = !{i64 0, !"_ZTSFiE"}
>> >>> !6 = !{i64 0, i64 751454132325070187}
>> >>>
>> >>> “Linkage” is one of: definition, external declaration, external weak
>> >>> declaration.
>> >>>
>> >>> In the merged “merged” module, !cfi.functions may contain multiple
>> >>> entries for each function. We pick one with the strongest linkage
>> >>> (i.e. the definition, if it is available) in LowerTypeTests.
>> >>
>> >>
>> >> It's unfortunate that this design effectively requires that the
>> >> LowerTypeTests pass recompute the linkage for each symbol, as the
>> linker
>> >> already knows this information (and could, in principle, provide it to
>> the
>> >> pass). But I'm not sure if there's a better way to do it.
>> >>
>> >>>
>> >>>
>> >>> The LTO step emits, for a defined function named “f”:
>> >>> declare void f.cfi()
>> >>> .jumptable:
>> >>>     …
>> >>>     call f.cfi
>> >>>     ...
>> >>> f.cfi-jt = alias .jumptable + offset
>> >>> f = alias f.cfi-jt
>> >>>
>> >>> The same for an external (either weak or strong) declaration of a
>> >>> function named “f”:
>> >>> .jumptable:
>> >>>     …
>> >>>     call f
>> >>>     ...
>> >>> f.cfi-jt = alias .jumptable + offset
>> >>>
>> >>
>> >> One thing to be careful about is summary-based dead stripping: the pass
>> >> needs to be able to query whether any specific function is still live
>> in
>> >> order to avoid introducing undefined symbol references. I think we can
>> do
>> >> that by adding a Live flag to GlobalValueSummaryInfo (which I think
>> should
>> >> also let us fix a number of FIXMEs elsewhere, e.g.
>> >> http://llvm-cs.pcc.me.uk/lib/Transforms/IPO/LowerTypeTests.cpp#1447
>> >> http://llvm-cs.pcc.me.uk/lib/Transforms/IPO/WholeProgramDevi
>> rt.cpp#1329),
>> >> and have the pass check the flag for each function.
>>
>> One thing I've noticed is that the regular LTO pipeline runs with the
>> merged module before summary based dead stripping. This way jumptables
>> generation in LowerTypeTests can not skip dead functions, which
>> effectively disables dead stripping of address-taken functions. This
>> sounds backwards. Per Peter's advice I've swapped the order with a
>> trivial patch, and it does not seem to break anything.
>>
>> Another thing I've noticed is all the extra cfi symbols in thinlto
>> modules (like __typeid_ZZZ_global_addr) hang around in the final
>> binary as .hidden symbols in the regular (non-dynamic) symbol table.
>> This is bad for binary size, and also confuses the symbolizer, because
>> f and f.cfi-jt have the same address (unless f is undefined) and there
>> is basically a 50% chance to see f.cfi-jt instead of f in cfi error
>> messages.
>>
>
> Function names can also receive other suffixes, such as "$hex_digits" or
> ".llvm.hex_digits" for promoted local symbols, and I don't see a way around
> at least those two. We may need to teach the symbolizer to strip the
> suffixes.
>
> We may be able to avoid having both the non-.cfi-jt and .cfi-jt symbol by
> emitting only the .cfi-jt symbol for symbols defined locally, and only the
> non-.cfi-jt symbol for symbols defined externally, and make the .cfi-jt
> rewrite conditional on whether the symbol is defined externally.
>

I meant: "emitting only the .cfi-jt symbol for symbols defined externally,
and only the non-.cfi-jt symbol for symbols defined locally"

> Regarding the __typeid_* symbols, I don't have a good solution. At least
> LLD will add all non-GC'd global symbols in the symbol table to .symtab.
> There may be some semantics in bfd or gold that we can take advantage of
> somehow and implement in lld as well. Or we may want to extend ELF somehow,
> but I'm not sure whether that would be worth it.
>
> Peter
>
>
>>
>> >
>> > Sounds good.
>> >
>> >>> Weak external linkage is used in the lowering of uses of @f. This is
>> >>> done both in the merged module and in ThinLTO backends. Uses of strong
>> >>> definitions and declarations are replaced with f.cfi-jt. Uses of weak
>> >>> external declarations a replaced with (f ? f.cfi-jt : 0) instead.
>> >>>
>> >>>
>> >>> ThinLTO backends need to know which functions have jumptable entries
>> >>> created for them (they will need to be RAUWed with f.cfi-jt). In the
>> >>> Cross-DSO mode, external functions don’t get jumptable entries. This
>> >>> information is passed back from the LTO step through combined summary.
>> >>> The current idea is to add a new record, FunctionTypeResolution, which
>> >>> would contain a set of function names in the jumptable.
>> >>
>> >>
>> >> It occurred to me that this design could prevent inlining of indirect
>> calls
>> >> via constant propagation. For example, suppose that we have a module
>> that
>> >> looks like this:
>> >>
>> >> define void @f() {
>> >>   ret void
>> >> }
>> >>
>> >> define void @g() {
>> >>   %fp = call i8* @identity(i8* @f)
>> >>   call void %fp()
>> >> }
>> >>
>> >> and a second module:
>> >>
>> >> define i8* @identity(i8* %ptr) {
>> >>   return %ptr
>> >> }
>> >>
>> >> and @identity is imported into the first module. Now I think the first
>> >> module would look like this after optimization:
>> >>
>> >> define void @f.cfi() {
>> >>   ret void
>> >> }
>> >>
>> >> declare void @f.cfi-jt()
>> >>
>> >> define void @g.cfi() {
>> >>   call void @f.cfi-jt()
>> >> }
>> >>
>> >> So we cannot inline f.cfi into g.cfi, as the optimizer does not know
>> that
>> >> f.cfi-jt can be replaced with f.cfi. I'm not sure how likely this
>> would be
>> >> in practice, but something to keep in mind.
>> >>
>> >> Peter
>> >>
>> >>>
>> >>> == Alternatives
>> >>>
>> >>> Function type information can be passed in the summary, as a list of
>> >>> records (name, linkage, type(, type)*).
>> >>> * Type can be either a string or a number. This complicates the
>> encoding.
>> >>> * The code in LowerTypeTests works with !type metadata in the same
>> >>> format as described above. It would need to either recreate the
>> >>> metadata from the summary, or deal with different input formats.
>> >>> I don’t see any advantages to this encoding. Could it be more compact
>> >>> than the metadata approach?
>> >>>
>> >>> [1]
>> >>> https://clang.llvm.org/docs/ControlFlowIntegrity.html#indire
>> ct-function-call-checking
>> >>> _______________________________________________
>> >>> LLVM Developers mailing list
>> >>> llvm-dev at lists.llvm.org
>> >>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>> >>
>> >>
>> >>
>> >>
>> >> --
>> >> --
>> >> Peter
>>
>
>
>
> --
> --
> Peter
>

-- 
-- 
Peter
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170523/502e6ed6/attachment.html>