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,10 @@ uint64_t Address, JumpTable::JumpTableType Type); + bool validJumpTableEntry(uint64_t EntryAddress, BinaryFunction *BF, + BinaryFunction *&TargetBF, + 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,15 @@ } } + // IMPORTANT: + // creating jump table without BranchType == POSSIBLE_PIC_JUMP_TABLE + // is dangerous --> False Positive. + // --> Should only be done in BF.processIndirectBranch() + // --> Temporarily keep this code to avoid failing tests + // Original purpose: // With relocations, catch jump table references outside of the basic block // containing the indirect jump. + // --> There are binaries where all references are fake jump table. if (HasRelocations) { const MemoryContentsType MemType = analyzeMemoryAt(Address, BF); if (MemType == MemoryContentsType::POSSIBLE_PIC_JUMP_TABLE && IsPCRel) { @@ -490,6 +497,65 @@ return false; } +bool BinaryContext::validJumpTableEntry(uint64_t EntryAddress, + BinaryFunction *BF, + BinaryFunction *&TargetBF, + BinaryFunction *ValidExternalTargetBF) { + TargetBF = getBinaryFunctionContainingAddress(EntryAddress); + // Property 1: Entry must target a valid function body + if (!TargetBF) + return false; + + // Property 2: Entry cannot target invalid instruction bounds + if (TargetBF->getState() == BinaryFunction::State::Disassembled && + !TargetBF->getInstructionAtOffset(EntryAddress - + TargetBF->getAddress())) { + LLVM_DEBUG(dbgs() << "FAIL: no instruction at this offset\n"); + return false; + } + + // Property 3: Entry cannot target more than 1 other-fragment + if (IsStripped && TargetBF != BF) { + // First time, the different fragment target can be any fragment + if (ValidExternalTargetBF == nullptr) { + ValidExternalTargetBF = TargetBF; + TargetBF->IsFragment = true; + return registerFragment(*TargetBF, *BF); + } + // Second time, the different fragment target must be similar + return TargetBF == ValidExternalTargetBF; + } + + // Property 4: EntryAddress cannot target a callable function --> Pending! + // (a) Previously: not allow jump table targeting current function entry + // --> Due to the assumption that function entry is always callable target + // --> The assumption is not realistic, temporarily relax this property + // IMPORTANT: + // (b) In future: + // --> Implement callable function identification + // --> EntryAddress cannot point to function entry + // --> EntryAddress can point to a sibling fragment entry + if (TargetBF == BF) + return EntryAddress != BF->getAddress(); + + // 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 + // --> No information about parent-fragment relation + if (IsStripped) { + TargetBF->IsFragment = true; + return registerFragment(*TargetBF, *BF); + } + + // Property 6: Perform further check for non-stripped binaries + // BF and TargetBF have parent-fragment relation + // (a) TargetBF is parent fragment + if (BF->isFragment()) + return registerFragment(*BF, *TargetBF); + // (b) BF is parent fragment + return TargetBF->isFragment() && registerFragment(*TargetBF, *BF); +} + bool BinaryContext::analyzeJumpTable( const uint64_t Address, const JumpTable::JumpTableType Type, BinaryFunction &BF, const uint64_t NextJTAddress, @@ -499,29 +565,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,38 +624,31 @@ 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()) { + // Verify if Value is a valid jump table entry + if (!validJumpTableEntry(Value, &BF, TargetBF, ValidExternalTargetBF)) { 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"; + else if (TargetBF == nullptr) + dbgs() << "FAIL: jump table targets are not contained in a valid " + << "function\n"; + else { + dbgs() << "FAIL: jump table are invalid:\n"; + dbgs() << " ! current function: " << BF.getPrintName() << "\n"; + dbgs() << " ! target function: " << 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'; + } }); 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"); - break; - } - ++NumRealEntries; if (TargetBF != &BF) 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,17 @@ } } + // IMPORTANT: analyzeIndirectBranch does not analyze PIC jump table pattern + // that cross fragments + // --> failed to recognize BranchType + // --> miscount jump table parents + // 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 + // 4. Create jump tables + // 5. Update map with new indirect branches, including jump tables + // 6. If some unclaimed PC-relative relocations in data, repeat from 3->5 IndirectBranchType BranchType = BC.MIB->analyzeIndirectBranch( Instruction, Begin, Instructions.end(), PtrSize, MemLocInstr, BaseRegNum, IndexRegNum, DispValue, DispExpr, PCRelBaseInstr); @@ -1672,6 +1683,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/lib/Rewrite/RewriteInstance.cpp b/bolt/lib/Rewrite/RewriteInstance.cpp --- a/bolt/lib/Rewrite/RewriteInstance.cpp +++ b/bolt/lib/Rewrite/RewriteInstance.cpp @@ -2913,14 +2913,20 @@ BC->populateJumpTables(); + // postProcessJumpTables may register secondary entry points for TargetBF + // postProcessJumpTables for all functions before postProcessEntryPoints for (auto &BFI : BC->getBinaryFunctions()) { BinaryFunction &Function = BFI.second; - if (!shouldDisassemble(Function)) continue; + Function.postProcessJumpTables(); + } + for (auto &BFI : BC->getBinaryFunctions()) { + BinaryFunction &Function = BFI.second; + if (!shouldDisassemble(Function)) + continue; Function.postProcessEntryPoints(); - Function.postProcessJumpTables(); } BC->clearJumpTableTempData(); 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