CFI: Drop !kcfi_type metadata for non-address-taken globals with LTO

[samitolvanen]

Another feature suggestion from @lvwr:

When LTO is used, hashes may be suppressed for non-local + non-address taken functions.

This would work similarly to ibt-seal. Basically, with LTO we can tell for sure that non-address-taken globals are not indirectly called, which means we can drop the !kcfi_type metadata from them, thus making these functions invalid indirect call targets.

cc @kees

[nickdesaulniers]

That's nice; it sounds like LTO will no longer be strictly necessary for kCFI, but will still improve kCFI when used.

[samitolvanen]

Here's a quick draft: samitolvanen/llvm-project@0d3cc88

With x86_64 defconfig + LTO_CLANG_FULL + CFI_CLANG, the number of indirectly callable functions dropped from 46647 to 34712 (-11935 = ~-25.6%) and the kernel booted just fine in my tests.

However, with LTO_CLANG_THIN, the kcfi-seal attribute resulted in the type hash getting dropped from another 1000+ functions, and I ended up with a kernel that failed to boot. The main issue appears to be that Function::hasAddressTaken() returns false for some address-taken globals (e.g. e820__memory_setup_default, which leads to an early boot crash).

@lvwr Do you remember running into similar issues with ThinLTO when you implemented ibt-seal? I'm not sure if ThinLTO even keeps track of address-taken functions across TUs.

[samitolvanen]

I confirmed that ThinLTO doesn't know about cross-TU address taking, which means -mibt-seal also doesn't work correctly. Here's a reproducer:

$ cat thinlto1.c 
extern void g(void);
void *f(void) { return &g; }
$ cat thinlto2.c 
void g(void) {}

Which I compiled with -flto=thin and IBT using the kernel code model, and then ensured Clang set the ibt-seal flag:

$ clang -c -flto=thin -fcf-protection=branch -mibt-seal -mcmodel=kernel thinlto?.c
$ llvm-dis -o - thinlto1.o | grep ibt-seal
!2 = !{i32 8, !"ibt-seal", i32 1}
$ llvm-dis -o - thinlto2.o | grep ibt-seal
!2 = !{i32 8, !"ibt-seal", i32 1}

When linked into a binary, we have no endbr64 instructions:

$ ld.lld -r -o thinlto.o thinlto?.o
$ objdump -d -r thinlto.o

thinlto.o:     file format elf64-x86-64


Disassembly of section .text.f:

0000000000000000 <f>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   48 8d 05 00 00 00 00    lea    0x0(%rip),%rax        # b <f+0xb>
                        7: R_X86_64_PC32        g-0x4
   b:   5d                      pop    %rbp
   c:   c3                      ret

Disassembly of section .text.g:

0000000000000000 <g>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   5d                      pop    %rbp
   5:   c3                      ret

Since the address of g was taken in the other TU, the function should have an endbr64. However, when I compile the reproducer with -flto instead of -flto=thin, ibt-seal works correctly again:

$ objdump -d -r fulllto.o

fulllto.o:     file format elf64-x86-64


Disassembly of section .text.f:

0000000000000000 <f>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   48 8d 05 00 00 00 00    lea    0x0(%rip),%rax        # b <f+0xb>
                        7: R_X86_64_PC32        g-0x4
   b:   5d                      pop    %rbp
   c:   c3                      ret

Disassembly of section .text.g:

0000000000000000 <g>:
   0:   f3 0f 1e fa             endbr64
   4:   55                      push   %rbp
   5:   48 89 e5                mov    %rsp,%rbp
   8:   5d                      pop  

So, it looks like the *-seal optimizations are only going to work with full LTO.

[nickdesaulniers]

ThinLTO doesn't know about cross-TU address taking

I asked Teresa Johnson about that, her thoughts:

ThinLTO might need to be taught something to propagate the necessary info. There should be a ref edge from f -> g in the index
If this optimization is only IR scoped it might need to have a ThinLTO version to propagate the cross-TU ref info to the referenced func symbol for the ThinLTO backend to manage.
But yes, if that is an optimization that relies on seeing references to functions only on IR, it sounds like an accurate statement that ThinLTO will not work automatically
The ref info is there in the index (it should be), so just need a flag or something to propagate the info back and make the optimization look at the summary too, or something to that effect.

[samitolvanen]

Yes, that makes perfect sense, thanks for checking with Teresa. I'll disable kcfi-seal with ThinLTO initially and we can later see how much work it would be to make this work with ThinLTO as well.

[samitolvanen]

Testing this a bit more, it looks like this optimization doesn't play nicely with arm64's alternative_cb where the callback functions are defined in stand-alone assembly, but the indirect calls to them in __apply_alternatives have a KCFI check. I'll have to think of a reasonable solution here. At least I didn't run into any issues on x86_64... yet!

[samitolvanen]

Adding __used to the affected functions fixes the arm64 issue, but I decided it's probably best to add the compiled feature behind a codegen option nevertheless so it can be disabled for specific translation units if needed -- just like ibt-seal:

https://github.com/samitolvanen/llvm-project/commits/kcfi-seal

I'll try to clean this up this week, do some more testing, and upload a patch to Phabricator for review.

[samitolvanen]

https://reviews.llvm.org/D138337

[samitolvanen]

Based on feedback from @pcc, I hacked together a version of the patch that doesn't drop type information for functions with VisibleToRegularObj set in symbol resolution. While this definitely does solve the issue with functions that are only address-taken in assembly but called indirectly in C, it also results in almost no types getting dropped from vmlinux.

Here are updated numbers with ToT Linux + the latest Clang:

__cfi_ symbols	Configuration
46642	x86_64 defconfig without kcfi-seal
46610	With kcfi-seal, but VisibleToRegularObj not dropped
34513	With kcfi-seal

It seems to me like the only feasible path forward is to keep this behind a flag so we can disable it if needed, or sprinkle the relevant kernel functions with __used to make sure we don't drop their type information with LTO. Thoughts?

[pcc]

Do you understand why VisibleToRegularObj is being set on most of the symbols?

[samitolvanen]

Do you understand why VisibleToRegularObj is being set on most of the symbols?

Looking at the code in LLD, it's because the kernel is doing a relocatable link. What do you think about also adding isUsedInRegularObj to SymbolResolution. I didn't test that yet, but it looks like that would be a more useful signal here.

[pcc]

The problem with relocatable links is that basically every symbol must be pessimistically considered to be used, because the linker doesn't know which symbols will be used in the final link. If the final link takes the address of one of those symbols, that would cause a problem. So I don't think that exposing isUsedInRegularObj would help here.

What might be useful would be if it were possible to filter the symbols exported from the object file when the relocatable link occurs. This would also have benefits for regular LTO because the compiler would be able to optimize more aggressively (e.g. if A calls B and B has no other calls, it would almost always be beneficial to inline B into A because it would not be necessary to emit another copy of B). This could use the existing version script syntax to specify the list of symbols.

[samitolvanen]

So I don't think that exposing isUsedInRegularObj would help here.

You're correct, that didn't look useful after all.

What might be useful would be if it were possible to filter the symbols exported from the object file when the relocatable link occurs. This would also have benefits for regular LTO because the compiler would be able to optimize more aggressively (e.g. if A calls B and B has no other calls, it would almost always be beneficial to inline B into A because it would not be necessary to emit another copy of B). This could use the existing version script syntax to specify the list of symbols.

Sure, I can see how that could benefit LTO, but this requires coming up with a list of symbols. Using the module exports wouldn't be sufficient as none of the functions used with alternative_cb are exported, for example. Perhaps we'd have to additionally go through all the non-bitcode files included in the relocatable link and check for undefined symbols? Or did you have some clever idea in mind for this?