Message-ID: <CAKwvOdnGL_9cJ+ETNce89+z7CTDctjACS8DFsLu=ev4+vkVkUw@mail.gmail.com>
Date:   Tue, 2 Jul 2019 13:53:51 -0700
From:   Nick Desaulniers <ndesaulniers@...gle.com>
To:     Peter Zijlstra <peterz@...radead.org>,
        Thomas Gleixner <tglx@...utronix.de>,
        Josh Poimboeuf <jpoimboe@...hat.com>
Cc:     clang-built-linux <clang-built-linux@...glegroups.com>,
        Kees Cook <keescook@...gle.com>,
        LKML <linux-kernel@...r.kernel.org>,
        Craig Topper <craig.topper@...el.com>,
        Alexander Potapenko <glider@...gle.com>,
        Bill Wendling <morbo@...gle.com>,
        Stephen Hines <srhines@...gle.com>
Subject: objtool warnings in prerelease clang-9

TL;DR
LLVM currently has a bug when unrolling loops containing asm goto and
we have a fix in hand.

Following up from our thread last week (https://lkml.org/lkml/2019/6/29/14).

With an x86 defconfig (6fbc7275c7a9) +clang 9 (e1006259d84d), I see
the following 4 warnings from objtool:
arch/x86/events/intel/core.o: warning: objtool:
intel_pmu_nhm_workaround()+0xa8: unreachable instruction
arch/x86/kernel/cpu/mtrr/generic.o: warning: objtool:
get_fixed_ranges()+0x9b: unreachable instruction
arch/x86/kernel/platform-quirks.o: warning: objtool:
x86_early_init_platform_quirks()+0x84: unreachable instruction
drivers/gpu/drm/i915/i915_gem_execbuffer.o: warning: objtool:
.altinstr_replacement+0x88: redundant UACCESS disable

Peter mentioned seeing 6 cases:
https://lkml.org/lkml/2019/6/27/118

We have 21 open reports (mostly unverified, I think someone was
testing -O3 -march=native):
https://github.com/ClangBuiltLinux/linux/issues?q=is%3Aissue+is%3Aopen+label%3Aobjtool

Taking a look specifically at arch/x86/kernel/cpu/mtrr/generic.o (as
tglx and Peter did in https://lkml.org/lkml/2019/6/27/118:

Disassembly and jump table:
https://gist.github.com/nickdesaulniers/395129e75d9f7afe028db832145594d8
More concise snippet:
https://gist.github.com/nickdesaulniers/a3159782908cb6e50e26ea9563b14c20

Of interest are the disassembled __jump_table entries; in groups of
three, there is a group for which the second element is duplicated
with a previous group.  This is bad because (as explained by Peter in
https://lkml.org/lkml/2019/6/27/118) the triples are in the form (code
location, jump target, pointer to key).  Duplicate or repeated jump
targets are unexpected, and will lead to incorrect control flow after
patching such code locations.  Also, the jump target should be 0x7
bytes ahead of the location, IIUC.

I've annotated the concise snippet:
https://gist.github.com/nickdesaulniers/c0cb8fc67720a5abbadf42fde5440a8e
we can see that two groups in the __jump_table share a similar jump
target, unexpectedly.

Now that we can identify what's bad (duplicate __jump_table entries),
we can try to creduce the input.
(https://nickdesaulniers.github.io/blog/2019/01/18/finding-compiler-bugs-with-c-reduce/)

The preprocessed input is 37497 lines long.  We want to reduce it
down, but I haven't been able to write a correct "interestingness
test" for creduce where I was then able to make sense of the output.
Instead, I'm looking into program slicing:
https://en.wikipedia.org/wiki/Program_slicing.  We'd want to do this
for C code, and it should be possible to implement with libclang, but
since it doesn't exist yet AFAICT and llvm-extract does, we can do the
program slicing on the LLVM IR level.  This will also give us a test
case to add to the compiler's test suite.

$ clang <same c flags kernel uses via `make V=`> \
  -emit-llvm -S -Xclang -disable-llvm- passes -o get_fixed_ranges generic.ll
$ llvm-extract -func get_fixed_ranges generic.ll -o
generic.get_fixed_ranges.ll -S --recursive

is a more manageable 541 lines of LLVM IR.
https://gist.github.com/nickdesaulniers/73aef95e9735a50765f654ebdcbb99dd

`callbr` is the LLVM IR instruction representing `asm goto`.
https://llvm.org/docs/LangRef.html#callbr-instruction
The gist of the instruction is:
callbr ... <list of block addresses from the label list> to
<fallthrough basic block [<list of block addresses from the label
list>].  IIUC, the repeated list of addresses better match.

We can then observe the middle end work its optimizations:
$ opt -O2 -print-before-all -print-after-all
generic.get_fixed_ranges.ll -S -o - 2>&1 | less
(27199 lines of output, omitted)
Here's the relevant snippet of the 27199 lines:
https://gist.github.com/nickdesaulniers/089bf56165675065bca830cd7da767d8

grepping through the output and looking for the first pass which
contains non-matching list of block addresses in the label list, we
come upon:

```
callbr void asm sideeffect "1:.byte
0x0f,0x1f,0x44,0x00,0\0A\09.pushsection __jump_table,  \22aw\22 \0A\09
.balign 8 \0A\09.long 1b - ., ${2:l} - . \0A\09 .quad ${0:c} + ${1:c}
- .\0A\09.popsection \0A\09",
"i,i,X,~{dirflag},~{fpsr},~{flags}"(%struct.static_key* getelementptr
inbounds (%struct.tracepoint, %struct.tracepoint*
@__tracepoint_read_msr, i64 0, i32 1), i1 false, i8*
blockaddress(@get_fixed_ranges, %20)) #6
          to label %native_read_msr.exit31.1 [label %49], !srcloc !4
```

(particularly I would have expected the `%20` and `%49` to match.)

which occurs before "MergedLoadStoreMotion," but due to what looks
like a bug in the pass printer
(https://lists.llvm.org/pipermail/cfe-dev/2019-July/062795.html)
doesn't print the results of loop unrolling, which runs just before
"MergedLoadStoreMotion."

I see that `get_fixed_ranges` is a loop that gets unrolled to have a
trip count of two.
$ opt -O2 -debug-only=loop-unroll generic.get_fixed_ranges.ll -S -o /dev/null
...
Loop Unroll: F[get_fixed_ranges] Loop %
  Loop Size = 27
  Trip Count = 2
  Trip Multiple = 2
COMPLETELY UNROLLING loop % with trip count 2!

If I manually add some print statements to loop unrolling, I can see
that before we unroll the loop, things look good. After unrolling the
loop, things look bad.  Indeed, if I kneecap loop unrolling the
problem goes away:

$ opt -O2 -debug-only=loop-unroll -unroll-full-max-count=0
generic.get_fixed_ranges.ll -S -o -

So this is a bug in our loop unroller when unrolling IR
representations of asm goto.  Peter's guess that this was a bug in
inlining was very close!  Function inlining and loop unrolling are
closely related and probably share a lot of machinery related to
cloning of basic blocks and instructions.  In this case, if we have a
loop with asm goto and we unroll the loop, the referenced labels from
the asm goto statement need to reflect the newly duplicated labels.
In this case, the new duplicated asm goto is referencing the initial
asm goto's label, which would result in non-sensical control flow at
runtime.

In the loop unroller, I can see that we skip loop unrolling in the
event of "indirectbr" instructions.
https://github.com/llvm/llvm-project/blob/97316fff5d6a7c3d2c072301a118ac0cb5094ad8/llvm/lib/Transforms/Utils/LoopUnroll.cpp#L294
https://github.com/llvm/llvm-project/blob/97316fff5d6a7c3d2c072301a118ac0cb5094ad8/llvm/lib/Analysis/LoopInfo.cpp#L432

Conservatively, we can block loop unrolling when we see asm goto in a loop:
diff --git a/llvm/lib/Analysis/LoopInfo.cpp b/llvm/lib/Analysis/LoopInfo.cpp
index 00dbe30c2b3d..f800c890d1db 100644
--- a/llvm/lib/Analysis/LoopInfo.cpp
+++ b/llvm/lib/Analysis/LoopInfo.cpp
@@ -433,7 +433,8 @@ bool Loop::isSafeToClone() const {
   // Return false if any loop blocks contain indirectbrs, or there
are any calls
   // to noduplicate functions.
   for (BasicBlock *BB : this->blocks()) {
-    if (isa<IndirectBrInst>(BB->getTerminator()))
+    if (isa<IndirectBrInst>(BB->getTerminator()) ||
+        isa<CallBrInst>(BB->getTerminator()))
       return false;

     for (Instruction &I : *BB)

This causes objtool to not find any issues in
arch/x86/kernel/cpu/mtrr/generic.o.  I don't observe any duplication
in the __jump_table section of the resulting .o file.  It also cuts
down the objtool warnings I observe in a defconfig (listed at the
beginning of the email) from 4 to 2. (platform-quirks.o predates asm
goto, i915_gem_execbuffer.o is likely a separate bug).

Coincidentally, Alexander and Bill just found what I think is the same bug:
https://bugs.llvm.org/show_bug.cgi?id=42489

So for now we'll be conservative/correct and disable unrolling of
loops that contain asm goto; then we can use the same test case to
permit unrolling with the correct code transformations added.
-- 
Thanks,
~Nick Desaulniers

Powered by blists - more mailing lists