[BOLT] Improve Linux Kernel ORC reader

[maksfb]

Summary

• Sort ORC entries in the internal table. Older Linux kernels did not sort them in the file (only during boot time).
• Add an option to dump sorted ORC tables (--dump-orc).
• Associate entries in the internal ORC table with a BinaryFunction even when we are not changing the function.
• If the function doesn't have ORC entry at the start, propagate ORC state from a previous entry.

[Amir]

LG, but can we have some tests? Is it possible to add ORC information using assembly directives?

[maksfb]

Add test case.

[Amir]

Wow, ORC encoding is this simple.

bolt/lib/Rewrite/LinuxKernelRewriter.cpp

595

My understanding is this is optimized encoding (skipping redundant entries). I don't see that the test covers that – can you add a test for it?

[maksfb]

In D155767#4520901, @Amir wrote:

Wow, ORC encoding is this simple.

From https://www.kernel.org/doc/html/next/x86/orc-unwinder.html:

"Orcs, fearsome creatures of medieval folklore, are the Dwarves’ natural enemies. Similarly, the ORC unwinder was created in opposition to the complexity and slowness of DWARF."

[maksfb]

Add test case covering propagation of ORC info form another function.

bolt/lib/Rewrite/LinuxKernelRewriter.cpp

 #include "bolt/Utils/CommandLineOpts.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Errc.h"
 
 using namespace llvm;
 using namespace bolt;
 
 namespace opts {
+
 static cl::opt<bool>
     PrintORC("print-orc",
              cl::desc("print ORC unwind information for instructions"),
-             cl::init(true), cl::cat(BoltCategory));
-}
+             cl::init(true), cl::Hidden, cl::cat(BoltCategory));
+
+static cl::opt<bool>
+    DumpORC("dump-orc", cl::desc("dump raw ORC unwind information (sorted)"),
+            cl::init(false), cl::Hidden, cl::cat(BoltCategory));
+
+} // namespace opts
 
 /// Linux Kernel supports stack unwinding using ORC (oops rewind capability).
 /// ORC state at every IP can be described by the following data structure.
 struct ORCState {
   int16_t SPOffset;
   int16_t BPOffset;
   int16_t Info;
 
class LinuxKernelRewriter final : public MetadataRewriter {
   /// Size of entries in ORC sections.
   static constexpr size_t ORC_UNWIND_ENTRY_SIZE = 6;
   static constexpr size_t ORC_UNWIND_IP_ENTRY_SIZE = 4;
 
   struct ORCListEntry {
     uint64_t IP;        /// Instruction address.
     BinaryFunction *BF; /// Binary function corresponding to the entry.
     ORCState ORC;       /// Stack unwind info in ORC format.
+
+    bool operator<(const ORCListEntry &Other) const {
+      if (IP < Other.IP)
+        return 1;
+      if (IP > Other.IP)
+        return 0;
+      return ORC == NullORC;
+    }
   };
 
   using ORCListType = std::vector<ORCListEntry>;
   ORCListType ORCEntries;
 
   /// Insert an LKMarker for a given code pointer \p PC from a non-code section
   /// \p SectionName.
   void insertLKMarker(uint64_t PC, uint64_t SectionOffset,
Error LinuxKernelRewriter::readORCTables() {
   DataExtractor OrcDE = DataExtractor(ORCUnwindSection->getContents(),
                                       BC.AsmInfo->isLittleEndian(),
                                       BC.AsmInfo->getCodePointerSize());
   DataExtractor IPDE = DataExtractor(ORCUnwindIPSection->getContents(),
                                      BC.AsmInfo->isLittleEndian(),
                                      BC.AsmInfo->getCodePointerSize());
   DataExtractor::Cursor ORCCursor(0);
   DataExtractor::Cursor IPCursor(0);
+  uint64_t PrevIP = 0;
   for (uint32_t Index = 0; Index < NumEntries; ++Index) {
     const uint64_t IP =
         IPSectionAddress + IPCursor.tell() + (int32_t)IPDE.getU32(IPCursor);
 
+    // Consume the status of the cursor.
+    if (!IPCursor)
+      return createStringError(errc::executable_format_error,
+                               "out of bounds while reading ORC IP table");
+
+    if (IP < PrevIP && opts::Verbosity)
+      errs() << "BOLT-WARNING: out of order IP 0x" << Twine::utohexstr(IP)
+             << " detected while reading ORC\n";
+
+    PrevIP = IP;
+
     // Store all entries, includes those we are not going to update as the
     // tables need to be sorted globally before being written out.
     ORCEntries.push_back(ORCListEntry());
     ORCListEntry &Entry = ORCEntries.back();
 
     Entry.IP = IP;
     Entry.ORC.SPOffset = (int16_t)OrcDE.getU16(ORCCursor);
     Entry.ORC.BPOffset = (int16_t)OrcDE.getU16(ORCCursor);
     Entry.ORC.Info = (int16_t)OrcDE.getU16(ORCCursor);
 
-    // Consume the status of cursors.
-    if (!IPCursor || !ORCCursor)
+    // Consume the status of the cursor.
+    if (!ORCCursor)
       return createStringError(errc::executable_format_error,
                                "out of bounds while reading ORC");
 
     BinaryFunction *&BF = Entry.BF;
     BF = BC.getBinaryFunctionContainingAddress(IP, /*CheckPastEnd*/ true);
 
     // If the entry immediately pointing past the end of the function is not
     // the terminator entry, then it does not belong to this function.
     if (BF && BF->getAddress() + BF->getSize() == IP && Entry.ORC != NullORC)
       BF = 0;
 
     // If terminator entry points to the start of the function, then it belongs
     // to a different function that contains the previous IP.
     if (BF && BF->getAddress() == IP && Entry.ORC == NullORC)
       BF = BC.getBinaryFunctionContainingAddress(IP - 1);
 
     if (!BF) {
       if (opts::Verbosity)
         errs() << "BOLT-WARNING: no binary function found matching ORC 0x"
                << Twine::utohexstr(IP) << ": " << Entry.ORC << '\n';
       continue;
     }
 
-    if (!BC.shouldEmit(*BF) || Entry.ORC == NullORC)
+    if (Entry.ORC == NullORC)
+      continue;
+
+    BF->setHasORC(true);
+
+    if (!BF->hasInstructions())
       continue;
 
     MCInst *Inst = BF->getInstructionAtOffset(IP - BF->getAddress());
     if (!Inst)
       return createStringError(
           errc::executable_format_error,
           "no instruction at address 0x%" PRIx64 " in .orc_unwind_ip", IP);
 
     // Some addresses will have two entries associated with them. The first
     // one being a "weak" section terminator. Since we ignore the terminator,
     // we should only assign one entry per instruction.
     if (BC.MIB->hasAnnotation(*Inst, "ORC"))
       return createStringError(
           errc::executable_format_error,
           "duplicate non-terminal ORC IP 0x%" PRIx64 " in .orc_unwind_ip", IP);
 
     BC.MIB->addAnnotation(*Inst, "ORC", Entry.ORC);
+  }
 
-    BF->setHasORC(true);
+  // Older kernels could contain unsorted tables in the file as the tables  were
+  // sorted during boot time.
+  llvm::sort(ORCEntries);
+
+  if (opts::DumpORC) {
+    outs() << "BOLT-INFO: ORC unwind information:\n";
+    for (const ORCListEntry &E : ORCEntries) {
+      outs() << "0x" << Twine::utohexstr(E.IP) << ": " << E.ORC;
+      if (E.BF)
+        outs() << ": " << *E.BF;
+      outs() << '\n';
+    }
   }
 
   return Error::success();
 }
 
 Error LinuxKernelRewriter::processORCPostCFG() {
   // Propagate ORC to the rest of the function. We can annotate every
   // instruction in every function, but to minimize the overhead, we annotate
   // the first instruction in every basic block to reflect the state at the
   // entry. This way, the ORC state can be calculated based on annotations
   // regardless of the basic block layout. Note that if we insert/delete
   // instructions, we must take care to attach ORC info to the new/deleted ones.
   for (BinaryFunction &BF : llvm::make_second_range(BC.getBinaryFunctions())) {
-    if (!BF.hasORC())
-      continue;
 
     std::optional<ORCState> CurrentState;
     for (BinaryBasicBlock &BB : BF) {
       for (MCInst &Inst : BB) {
         ErrorOr<ORCState> State =
             BC.MIB->tryGetAnnotationAs<ORCState>(Inst, "ORC");
 
         if (State) {
           CurrentState = *State;
           continue;
         }
 
-        if (!CurrentState)
-          continue;
+        // In case there was no ORC entry that matched the function start
+        // address, we need to propagate ORC state from the previous entry.
+        if (!CurrentState) {
+          auto It =
+              llvm::partition_point(ORCEntries, [&](const ORCListEntry &E) {
+                return E.IP < BF.getAddress();
+              });
+          if (It != ORCEntries.begin())
+            It = std::prev(It);
+
+          if (It->ORC == NullORC && BF.hasORC())
+            errs() << "BOLT-WARNING: ORC unwind info excludes prologue for "
+                   << BF << '\n';
+
+          CurrentState = It->ORC;
+          if (It->ORC != NullORC)
+            BF.setHasORC(true);
+        }
 
         // While printing ORC, attach info to every instruction for convenience.
         if (opts::PrintORC || &Inst == &BB.front())
           BC.MIB->addAnnotation(Inst, "ORC", *CurrentState);
       }
     }
   }
 

bolt/test/X86/orc_unwind.s

+# REQUIRES: system-linux
+
+## Check that BOLT correctly reads ORC unwind information used by Linux Kernel.
+
+# RUN: llvm-mc -filetype=obj -triple x86_64-unknown-unknown %s -o %t.o
+# RUN: %clang %cflags %t.o -o %t.exe
+
+# RUN: llvm-bolt %t.exe --print-normalized --dump-orc --print-orc -o %t.out \
+# RUN:   |& FileCheck %s
+
+# CHECK:      BOLT-INFO: ORC unwind information:
+# CHECK-NEXT: {sp: 8, bp: 0, info: 0x5}: _start
+# CHECK-NEXT: {sp: 0, bp: 0, info: 0x0}: _start
+# CHECK-NEXT: {sp: 8, bp: 0, info: 0x5}: foo
+# CHECK-NEXT: {sp: 16, bp: -16, info: 0x15}: foo
+# CHECK-NEXT: {sp: 16, bp: -16, info: 0x14}: foo
+# CHECK-NEXT: {sp: 8, bp: 0, info: 0x5}: foo
+# CHECK-NEXT: {sp: 0, bp: 0, info: 0x0}: bar
+
+  .text
+  .globl _start
+  .type _start, %function
+_start:
+  .cfi_startproc
+
+  call foo
+# CHECK:      callq foo           # ORC: {sp: 8, bp: 0, info: 0x5}
+  ret
+  .cfi_endproc
+  .size _start, .-_start
+
+  .globl foo
+  .type foo, %function
+foo:
+  .cfi_startproc
+  push %rbp
+# CHECK:      pushq   %rbp        # ORC: {sp: 8, bp: 0, info: 0x5}
+.L1:
+  mov %rsp, %rbp
+# CHECK:      movq    %rsp, %rbp  # ORC: {sp: 16, bp: -16, info: 0x15}
+.L2:
+  pop %rbp
+# CHECK:      popq    %rbp        # ORC: {sp: 16, bp: -16, info: 0x14}
+.L3:
+  ret
+# CHECK:      retq                # ORC: {sp: 8, bp: 0, info: 0x5}
+  .cfi_endproc
+  .size foo, .-foo
+
+bar:
+  .cfi_startproc
+  ret
+# Same ORC info propagated from foo above.
+# CHECK:      retq                # ORC: {sp: 8, bp: 0, info: 0x5}
+.L4:
+  .cfi_endproc
+  .size bar, .-bar
+
+  .section .orc_unwind,"a",@progbits
+  .align 4
+  .section .orc_unwind_ip,"a",@progbits
+  .align 4
+
+# ORC for _start
+  .section .orc_unwind
+  .2byte 8
+  .2byte 0
+  .2byte 5
+  .section .orc_unwind_ip
+  .long _start - .
+
+  .section .orc_unwind
+  .2byte 0
+  .2byte 0
+  .2byte 0
+  .section .orc_unwind_ip
+  .long foo - .
+
+# ORC for foo
+  .section .orc_unwind
+  .2byte 8
+  .2byte 0
+  .2byte 5
+  .section .orc_unwind_ip
+  .long foo - .
+
+  .section .orc_unwind
+  .2byte 16
+  .2byte -16
+  .2byte 21
+  .section .orc_unwind_ip
+  .long .L1 - .
+
+  .section .orc_unwind
+  .2byte 16
+  .2byte -16
+  .2byte 20
+  .section .orc_unwind_ip
+  .long .L2 - .
+
+  .section .orc_unwind
+  .2byte 8
+  .2byte 0
+  .2byte 5
+  .section .orc_unwind_ip
+  .long .L3 - .
+
+  .section .orc_unwind
+  .2byte 0
+  .2byte 0
+  .2byte 0
+  .section .orc_unwind_ip
+  .long .L4 - .
+
+# Fake Linux Kernel sections
+  .section __ksymtab,"a",@progbits
+  .section __ksymtab_gpl,"a",@progbits
+  .section .pci_fixup,"a",@progbits