diff --git a/bolt/include/bolt/Core/BinaryContext.h b/bolt/include/bolt/Core/BinaryContext.h --- a/bolt/include/bolt/Core/BinaryContext.h +++ b/bolt/include/bolt/Core/BinaryContext.h @@ -480,6 +480,16 @@ uint64_t Address, JumpTable::JumpTableType Type); + /// Validate a possible jump table entry at \p Address for \p Function + /// Return true if it is a valid jump table entry + /// + /// Function is a function referencing the jump table + /// Address is the address of the jump table target + /// ValidExternalTargetBF is the first external function which jump table + /// points to. This is used in a heuristic for stripped binaries + bool isValidJumpTableEntry(uint64_t Address, BinaryFunction &Function, + BinaryFunction *&ValidExternalTargetBF); + /// Analyze a possible jump table of type \p Type at a given \p Address. /// \p BF is a function referencing the jump table. /// Return true if the jump table was detected at \p Address, and false diff --git a/bolt/lib/Core/BinaryContext.cpp b/bolt/lib/Core/BinaryContext.cpp --- a/bolt/lib/Core/BinaryContext.cpp +++ b/bolt/lib/Core/BinaryContext.cpp @@ -419,8 +419,16 @@ } } - // With relocations, catch jump table references outside of the basic block - // containing the indirect jump. + // IMPORTANT: + // Creating jump table without checking BranchType == POSSIBLE_PIC_JUMP_TABLE + // can lead to false positives, especially when processing stripped binaries. + // But it's less likely to affect nonstripped binaries due to strong check + // + // In addition, processIndirectBranch() check both MemType and BranchType, + // but the current version fails to analyze cross-function jump table pattern, + // potentially leading to false negatives. + // + // Keep this code for now to avoid false negatives. if (HasRelocations) { const MemoryContentsType MemType = analyzeMemoryAt(Address, BF); if (MemType == MemoryContentsType::POSSIBLE_PIC_JUMP_TABLE && IsPCRel) { @@ -490,6 +498,90 @@ return false; } +bool BinaryContext::isValidJumpTableEntry( + uint64_t Address, BinaryFunction &Function, + BinaryFunction *&ValidExternalTargetBF) { + + BinaryFunction *TargetBF = getBinaryFunctionContainingAddress(Address); + + // Property 1: Entry must target a valid function body + if (!TargetBF) { + LLVM_DEBUG(dbgs() << "Invalid jump table entry candidate: not point to any " + << "function\n";); + return false; + } + + // Property 2: Entry cannot target invalid instruction bounds + // Disassembly is not decoupled from branch analysis, so this property could + // be bypassed for some jump tables during disassembly, leading to some false + // positives. However, populateJumpTables will reevaluate all jump tables + // with this property again + if (TargetBF->getState() == BinaryFunction::State::Disassembled && + !TargetBF->getInstructionAtOffset(Address - TargetBF->getAddress())) { + LLVM_DEBUG(dbgs() << "Invalid jump table entry candidate: fail instruction " + << "boundary check\n"); + return false; + } + + // Property 3: Entry cannot target more than 1 other-fragment + if (IsStripped && TargetBF != &Function) { + // First time, the different fragment target can be any fragment + if (ValidExternalTargetBF == nullptr) { + ValidExternalTargetBF = TargetBF; + TargetBF->IsFragment = true; + return registerFragment(*TargetBF, Function); + } + // Second time, the different fragment target must be similar + LLVM_DEBUG(if (TargetBF != ValidExternalTargetBF) dbgs() + << "Invalid jump table entry candidate: point to more than " + << "one sibling fragment\n";); + return TargetBF == ValidExternalTargetBF; + } + + // Property 4: Address cannot point to a callable function entry + // This property is not implemented yet! + // Compute a subset of definite callable function entry, and prohibit entries + // pointing to such function. Identify callable function using properties + // (a) Containing prologue + // (b) Reached by a direct call + // (c) Referenced in GOT and/or VTable + // (d) Passed ABI checks, e.g., callee-saved preservation + + // Property 5: Non-overlapping jump tables + // This property was already enforced in calculating UpperBound + // Relax policy for stripped binaries by accept all entries at this point + if (IsStripped) { + if (TargetBF != &Function) { + TargetBF->IsFragment = true; + return registerFragment(*TargetBF, Function); + } + return true; + } + + // Property 6: Perform further check for non-stripped binaries + // (a) TargetBF and Function + if (TargetBF == &Function) + return true; + // (b) TargetBF is parent fragment + if (Function.isFragment()) { + bool IsValid = registerFragment(Function, *TargetBF); + LLVM_DEBUG(if (!IsValid) dbgs() + << "Invalid jump table entry candidate: point to a different" + << " function\n";); + return IsValid; + } + // (c) BF is parent fragment + else if (TargetBF->isFragment()) { + bool IsValid = registerFragment(*TargetBF, Function); + LLVM_DEBUG(if (!IsValid) dbgs() + << "Invalid jump table entry candidate: point to a different" + << " function\n";); + return IsValid; + } + + return false; +} + bool BinaryContext::analyzeJumpTable( const uint64_t Address, const JumpTable::JumpTableType Type, BinaryFunction &BF, const uint64_t NextJTAddress, @@ -499,29 +591,13 @@ // Number of targets other than __builtin_unreachable. uint64_t NumRealEntries = 0; + BinaryFunction *ValidExternalTargetBF = nullptr; auto addEntryAddress = [&](uint64_t EntryAddress) { if (EntriesAsAddress) EntriesAsAddress->emplace_back(EntryAddress); }; - auto doesBelongToFunction = [&](const uint64_t Addr, - BinaryFunction *TargetBF) -> bool { - if (BF.containsAddress(Addr)) - return true; - // Nothing to do if we failed to identify the containing function. - if (!TargetBF) - return false; - // Case 1: check if BF is a fragment and TargetBF is its parent. - if (BF.isFragment()) { - // Parent function may or may not be already registered. - // Set parent link based on function name matching heuristic. - return registerFragment(BF, *TargetBF); - } - // Case 2: check if TargetBF is a fragment and BF is its parent. - return TargetBF->isFragment() && registerFragment(*TargetBF, BF); - }; - ErrorOr Section = getSectionForAddress(Address); if (!Section) return false; @@ -574,41 +650,15 @@ continue; } - // Function or one of its fragments. BinaryFunction *TargetBF = getBinaryFunctionContainingAddress(Value); - // We assume that a jump table cannot have function start as an entry. - if (!doesBelongToFunction(Value, TargetBF) || Value == BF.getAddress()) { - LLVM_DEBUG({ - if (!BF.containsAddress(Value)) { - dbgs() << "FAIL: function doesn't contain this address\n"; - if (TargetBF) { - dbgs() << " ! function containing this address: " - << TargetBF->getPrintName() << '\n'; - if (TargetBF->isFragment()) - dbgs() << " ! is a fragment\n"; - for (BinaryFunction *TargetParent : TargetBF->ParentFragments) - dbgs() << " ! its parent is " - << (TargetParent ? TargetParent->getPrintName() : "(none)") - << '\n'; - } - } - if (Value == BF.getAddress()) - dbgs() << "FAIL: jump table cannot have function start as an entry\n"; - }); - break; - } - - // Check there's an instruction at this offset. - if (TargetBF->getState() == BinaryFunction::State::Disassembled && - !TargetBF->getInstructionAtOffset(Value - TargetBF->getAddress())) { - LLVM_DEBUG(dbgs() << "FAIL: no instruction at this offset\n"); + // Verify if Value is a valid jump table entry + if (!isValidJumpTableEntry(Value, BF, ValidExternalTargetBF)) break; - } ++NumRealEntries; - if (TargetBF != &BF) + if (TargetBF != nullptr && TargetBF != &BF) BF.setHasIndirectTargetToSplitFragment(true); addEntryAddress(Value); } @@ -766,10 +816,6 @@ const MCSymbol * BinaryContext::getOrCreateJumpTable(BinaryFunction &Function, uint64_t Address, JumpTable::JumpTableType Type) { - auto isFragmentOf = [](BinaryFunction *Fragment, BinaryFunction *Parent) { - return (Fragment->isFragment() && Fragment->isParentFragment(Parent)); - }; - // Two fragments of same function access same jump table if (JumpTable *JT = getJumpTableContainingAddress(Address)) { assert(JT->Type == Type && "jump table types have to match"); @@ -778,21 +824,26 @@ // Prevent associating a jump table to a specific fragment twice. // This simple check arises from the assumption: no more than 2 fragments. if (JT->Parents.size() == 1 && JT->Parents[0] != &Function) { - bool SameFunction = isFragmentOf(JT->Parents[0], &Function) || - isFragmentOf(&Function, JT->Parents[0]); - assert(SameFunction && - "cannot re-use jump table of a different function"); - // Duplicate the entry for the parent function for easy access - JT->Parents.push_back(&Function); - if (opts::Verbosity > 2) { - outs() << "BOLT-INFO: Multiple fragments access same jump table: " - << JT->Parents[0]->getPrintName() << "; " - << Function.getPrintName() << "\n"; - JT->print(outs()); + // Register parent-fragment if applicable + bool IsSibling = false; + if (Function.isFragment()) + IsSibling = registerFragment(Function, *(JT->Parents[0])); + else if (JT->Parents[0]->isFragment()) + IsSibling = registerFragment(*(JT->Parents[0]), Function); + assert(IsSibling && "cannot re-use jump table of a different function"); + if (IsSibling) { + // Duplicate the entry for the parent function for easy access + Function.JumpTables.emplace(Address, JT); + JT->Parents.push_back(&Function); + for (BinaryFunction *Parent: JT->Parents) + Parent->setHasIndirectTargetToSplitFragment(true); + if (opts::Verbosity > 2) { + outs() << "BOLT-INFO: Multiple fragments access same jump table: " + << JT->Parents[0]->getPrintName() << "; " + << Function.getPrintName() << "\n"; + JT->print(outs()); + } } - Function.JumpTables.emplace(Address, JT); - JT->Parents[0]->setHasIndirectTargetToSplitFragment(true); - JT->Parents[1]->setHasIndirectTargetToSplitFragment(true); } bool IsJumpTableParent = false; diff --git a/bolt/lib/Core/BinaryFunction.cpp b/bolt/lib/Core/BinaryFunction.cpp --- a/bolt/lib/Core/BinaryFunction.cpp +++ b/bolt/lib/Core/BinaryFunction.cpp @@ -790,6 +790,16 @@ } } + // IMPORTANT: analyzeIndirectBranch does not analyze PIC jump table pattern + // that cross fragments, lead to false negatives + // Solution: + // 1. Lift all instructions in every instruction to MCInst + // 2. Build map (Branch -> Dest) from all direct branches + // 3. Identify indirect BranchType with respect to CFG based on the mapping + // 4. Analyze for potential jump tables + // 5. Update map (Branch -> Dest) with new discovered indirect branches, + // including jump tables + // 6. Repeat step 3-5 until no new indirect branch targets is found IndirectBranchType BranchType = BC.MIB->analyzeIndirectBranch( Instruction, Begin, Instructions.end(), PtrSize, MemLocInstr, BaseRegNum, IndexRegNum, DispValue, DispExpr, PCRelBaseInstr); @@ -1671,6 +1681,11 @@ TargetBF->getAddress()); JT.Entries.push_back(Label); } + // If jump table entry is fragment entry, the label already exists + else { + MCSymbol *Label = TargetBF->getLabels().at(0); + JT.Entries.push_back(Label); + } } } diff --git a/bolt/test/X86/false-jump-table.s b/bolt/test/X86/false-jump-table.s --- a/bolt/test/X86/false-jump-table.s +++ b/bolt/test/X86/false-jump-table.s @@ -1,5 +1,10 @@ -# Check that jump table detection does not fail on a false -# reference to a jump table. +# There are two conditions of a valid jump table +# (a) MemType is POSSIBLE_JUMP_TABLE +# (b) BranchType is POSSIBLE_JUMP_TABLE +# Only then, in principle, a jump table will be created/accessed. + +# This test checks if a jump table is created based solely on MemType. +# This test may need revision in future. # REQUIRES: system-linux diff --git a/bolt/test/X86/jump-table-move-pic.s b/bolt/test/X86/jump-table-move-pic.s new file mode 100644 --- /dev/null +++ b/bolt/test/X86/jump-table-move-pic.s @@ -0,0 +1,62 @@ +# Test -jump-tables=move with stripped/non-stripped binary with split function +# accessing the jump table, reproduces the unresolved symbol issue due to losing +# symbols referenced from a jump table. + +# REQUIRES: system-linux + +# RUN: llvm-mc -filetype=obj -triple x86_64-unknown-unknown %s -o %t.o +# RUN: %clang %cflags -no-pie %t.o -o %t.exe -Wl,-q +# RUN: llvm-bolt %t.exe -o %t.out --lite=0 -v=1 --jump-tables=move -print-cfg 2>&1 | FileCheck %s -check-prefix=CHECK-NOSTRIP + + +# CHECK-NOSTRIP-NOT: unclaimed PC-relative relocations left in data +# CHECK-NOSTRIP: BOLT-INFO: marking main.cold.1 as a fragment of main +# CHECK-NOSTRIP: Ignoring main.cold.1 +# CHECK-NOSTRIP: Ignoring main +# CHECK-NOSTRIP: Binary Function "main.cold.1" after building cfg +# CHECK-NOSTRIP: PIC Jump table JUMP_TABLE for function main.cold.1 at {{.*}} with a total count of 0 +# CHECK-NOSTRIP-NEXT: 0x0000 : [[ENTRY:.+]] +# CHECK-NOSTRIP-NEXT: 0x0004 : [[ENTRY]] + + +# RUN: cp %t.exe %t.tmp.exe +# RUN: llvm-strip -s %t.tmp.exe +# RUN: llvm-bolt %t.tmp.exe -o %t.out --lite=0 -v=1 --jump-tables=move -print-cfg 2>&1 | FileCheck %s -check-prefix=CHECK-STRIP + +# CHECK-STRIP-NOT: unclaimed PC-relative relocations left in data +# CHECK-STRIP: BOLT-INFO: marking [[MAIN:.+]] as a fragment of [[MAIN_COLD:.+]] +# CHECK-STRIP: Ignoring [[MAIN_COLD]] +# CHECK-STRIP: Ignoring [[MAIN]] +# CHECK-STRIP: Binary Function "[[MAIN_COLD]]" after building cfg +# CHECK-STRIP: PIC Jump table JUMP_TABLE/[[MAIN_COLD]]{{.*}} for function [[MAIN_COLD]] at {{.*}} with a total count of 0 +# CHECK-STRIP-NEXT: 0x0000 : [[ENTRY:.+]] +# CHECK-STRIP-NEXT: 0x0004 : [[ENTRY]] + + .text + .globl main + .type main, %function + .p2align 2 +main: + .cfi_startproc + cmpl $0x67, %edi + jne main.cold.1 +LBB0: + retq + .cfi_endproc + + .globl main.cold.1 + .type main.cold.1, %function + .p2align 2 +main.cold.1: + .cfi_startproc + leaq JUMP_TABLE(%rip), %rax + movslq (%rax,%rdx,4), %rcx + addq %rax, %rcx + jmpq *%rcx + .cfi_endproc + + .rodata + .globl JUMP_TABLE +JUMP_TABLE: + .long LBB0-JUMP_TABLE + .long LBB0-JUMP_TABLE diff --git a/bolt/test/X86/split-func-jump-table-fragment-noparent.s b/bolt/test/X86/split-func-jump-table-fragment-noparent.s --- a/bolt/test/X86/split-func-jump-table-fragment-noparent.s +++ b/bolt/test/X86/split-func-jump-table-fragment-noparent.s @@ -1,22 +1,52 @@ # This reproduces a bug with jump table identification where jump table has -# entries pointing to code in function and its cold fragment. -# The fragment is only reachable through jump table. +# entries pointing to code in function and its cold fragment. The fragment is +# only reachable through jump table. +# This test verifies support for both stripped and non-stripped binaries. # REQUIRES: system-linux + # RUN: llvm-mc -filetype=obj -triple x86_64-unknown-unknown %s -o %t.o -# RUN: llvm-strip --strip-unneeded %t.o # RUN: %clang %cflags %t.o -o %t.exe -Wl,-q -# RUN: llvm-bolt %t.exe -o %t.out --lite=0 -v=1 2>&1 | FileCheck %s +# RUN: llvm-strip --strip-unneeded %t.exe +# RUN: llvm-bolt %t.exe -o %t.out --lite=0 -v=1 -print-cfg 2>&1 | FileCheck %s -check-prefix=CHECK-NOSTRIP + +# CHECK-NOSTRIP-NOT: unclaimed PC-relative relocations left in data +# CHECK-NOSTRIP: BOLT-INFO: marking main.cold.1 as a fragment of main +# CHECK-NOSTRIP: Ignoring main +# CHECK-NOSTRIP: Ignoring main.cold.1 +# CHECK-NOSTRIP: Binary Function "main" after building cfg +# CHECK-NOSTRIP: PIC Jump table JUMP_TABLE for function main at {{.*}} with a total count of 0 +# CHECK-NOSTRIP-NEXT: 0x0000 : {{.+}} +# CHECK-NOSTRIP-NEXT: 0x0004 : [[LBB3:.+]] +# CHECK-NOSTRIP-NEXT: 0x0008 : {{.*}}main.cold.1{{.*}} +# CHECK-NOSTRIP-NEXT: 0x000c : [[LBB3]] +# CHECK-NOSTRIP: Binary Function "main.cold.1" after building cfg + + +# RUN: cp %t.exe %t.tmp.exe +# RUN: llvm-strip -s %t.tmp.exe +# RUN: llvm-bolt %t.tmp.exe -o %t.out --lite=0 -v=1 -print-cfg 2>&1 | FileCheck %s -check-prefix=CHECK-STRIP + +# CHECK-STRIP-NOT: unclaimed PC-relative relocations left in data +# CHECK-STRIP: BOLT-INFO: marking [[MAIN_COLD:.+]] as a fragment of [[MAIN:.+]] +# CHECK-STRIP: Ignoring [[MAIN]] +# CHECK-STRIP: Ignoring [[MAIN_COLD]] +# CHECK-STRIP: Binary Function "[[MAIN]]" after building cfg +# CHECK-STRIP: PIC Jump table JUMP_TABLE/[[MAIN]]{{.*}} for function [[MAIN]] at {{.*}} with a total count of 0 +# CHECK-STRIP-NEXT: 0x0000 : {{.+}} +# CHECK-STRIP-NEXT: 0x0004 : [[LBB3:.+]] +# CHECK-STRIP-NEXT: 0x0008 : {{.*}}[[MAIN_COLD]]{{.*}} +# CHECK-STRIP-NEXT: 0x000c : [[LBB3]] +# CHECK-STRIP: Binary Function "[[MAIN_COLD]]" after building cfg -# CHECK-NOT: unclaimed PC-relative relocations left in data -# CHECK: BOLT-INFO: marking main.cold.1 as a fragment of main .text .globl main .type main, %function .p2align 2 main: LBB0: + .cfi_startproc andl $0xf, %ecx cmpb $0x4, %cl # exit through ret @@ -35,6 +65,7 @@ LBB3: addq $0x8, %rsp ret + .cfi_endproc .size main, .-main # cold fragment is only reachable through jump table @@ -42,11 +73,13 @@ .type main.cold.1, %function .p2align 2 main.cold.1: + .cfi_startproc # load bearing nop: pad LBB4 so that it can't be treated # as __builtin_unreachable by analyzeJumpTable nop LBB4: callq abort +.cfi_endproc .size main.cold.1, .-main.cold.1 .rodata diff --git a/bolt/test/X86/split-func-jump-table-fragment.s b/bolt/test/X86/split-func-jump-table-fragment.s --- a/bolt/test/X86/split-func-jump-table-fragment.s +++ b/bolt/test/X86/split-func-jump-table-fragment.s @@ -1,21 +1,53 @@ # This reproduces a bug with jump table identification where jump table has # entries pointing to code in function and its cold fragment. +# This test verifies support for both stripped and non-stripped binaries. # REQUIRES: system-linux + + # RUN: llvm-mc -filetype=obj -triple x86_64-unknown-unknown %s -o %t.o -# RUN: llvm-strip --strip-unneeded %t.o # RUN: %clang %cflags %t.o -o %t.exe -Wl,-q -# RUN: llvm-bolt %t.exe -o %t.out --lite=0 -v=1 2>&1 | FileCheck %s +# RUN: llvm-strip --strip-unneeded %t.exe +# RUN: llvm-bolt %t.exe -o %t.out --lite=0 -v=1 -print-cfg 2>&1 | FileCheck %s -check-prefix=CHECK-NOSTRIP + +# CHECK-NOSTRIP-NOT: unclaimed PC-relative relocations left in data +# CHECK-NOSTRIP: BOLT-INFO: marking main.cold.1 as a fragment of main +# CHECK-NOSTRIP: Ignoring main +# CHECK-NOSTRIP: Ignoring main.cold.1 +# CHECK-NOSTRIP: Binary Function "main" after building cfg +# CHECK-NOSTRIP: PIC Jump table JUMP_TABLE for function main at {{.*}} with a total count of 0 +# CHECK-NOSTRIP-NEXT: 0x0000 : {{.+}} +# CHECK-NOSTRIP-NEXT: 0x0004 : [[LBB3:.+]] +# CHECK-NOSTRIP-NEXT: 0x0008 : {{.*}}main.cold.1{{.*}} +# CHECK-NOSTRIP-NEXT: 0x000c : [[LBB3]] +# CHECK-NOSTRIP: Binary Function "main.cold.1" after building cfg + + + +# RUN: cp %t.exe %t.tmp.exe +# RUN: llvm-strip -s %t.tmp.exe +# RUN: llvm-bolt %t.tmp.exe -o %t.out --lite=0 -v=1 -print-cfg 2>&1 | FileCheck %s -check-prefix=CHECK-STRIP + +# CHECK-STRIP-NOT: unclaimed PC-relative relocations left in data +# CHECK-STRIP: BOLT-INFO: marking [[MAIN_COLD:.+]] as a fragment of [[MAIN:.+]] +# CHECK-STRIP: Ignoring [[MAIN]] +# CHECK-STRIP: Ignoring [[MAIN_COLD]] +# CHECK-STRIP: Binary Function "[[MAIN]]" after building cfg +# CHECK-STRIP: PIC Jump table JUMP_TABLE/[[MAIN]]{{.*}} for function [[MAIN]] at {{.*}} with a total count of 0 +# CHECK-STRIP-NEXT: 0x0000 : {{.+}} +# CHECK-STRIP-NEXT: 0x0004 : [[LBB3:.+]] +# CHECK-STRIP-NEXT: 0x0008 : {{.*}}[[MAIN_COLD]]{{.*}} +# CHECK-STRIP-NEXT: 0x000c : [[LBB3]] +# CHECK-STRIP: Binary Function "[[MAIN_COLD]]" after building cfg -# CHECK-NOT: unclaimed PC-relative relocations left in data -# CHECK: BOLT-INFO: marking main.cold.1 as a fragment of main .text .globl main .type main, %function .p2align 2 main: LBB0: + .cfi_startproc andl $0xf, %ecx cmpb $0x4, %cl # exit through abort in main.cold.1, registers cold fragment the regular way @@ -34,6 +66,7 @@ LBB3: addq $0x8, %rsp ret + .cfi_endproc .size main, .-main .globl main.cold.1 @@ -42,9 +75,11 @@ main.cold.1: # load bearing nop: pad LBB4 so that it can't be treated # as __builtin_unreachable by analyzeJumpTable + .cfi_startproc nop LBB4: callq abort + .cfi_endproc .size main.cold.1, .-main.cold.1 .rodata