From 0d8ae1e3435accab5130d71dfc872507043ca4f1 Mon Sep 17 00:00:00 2001 From: Lang Hames Date: Tue, 7 May 2019 22:56:40 +0000 Subject: [PATCH] Reapply r360194 "[JITLink] Add support for MachO .alt_entry atoms." with fixes. This patch modifies MachOAtomGraphBuilder to use setLayoutNext rather than addEdge, and fixes a bug in the section layout algorithm that could result in atoms appearing more than once in the section ordering (which resulted in those atoms being assigned invalid addresses during layout). llvm-svn: 360205 --- .../include/llvm/ExecutionEngine/JITLink/JITLink.h | 2 +- .../lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp | 36 +++---- .../JITLink/MachOAtomGraphBuilder.cpp | 109 +++++++++++++++++++-- .../JITLink/MachOAtomGraphBuilder.h | 5 + llvm/lib/ExecutionEngine/JITLink/MachO_x86_64.cpp | 7 +- .../JITLink/X86/MachO_x86-64_relocations.s | 64 +++++++++++- 6 files changed, 192 insertions(+), 31 deletions(-) diff --git a/llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h b/llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h index 4e527f1..dd4fe36 100644 --- a/llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h +++ b/llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h @@ -470,7 +470,7 @@ public: void addEdge(Edge::Kind K, Edge::OffsetT Offset, Atom &Target, Edge::AddendT Addend) { assert(K != Edge::LayoutNext && - "Layout edges should be added via addLayoutNext"); + "Layout edges should be added via setLayoutNext"); Edges.push_back(Edge(K, Offset, Target, Addend)); } diff --git a/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp b/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp index 38ad1ec..8e4cfa0 100644 --- a/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp +++ b/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp @@ -170,31 +170,31 @@ void JITLinkerBase::layOutAtoms() { auto &SL = KV.second; for (auto *SIList : {&SL.ContentSections, &SL.ZeroFillSections}) { for (auto &SI : *SIList) { - std::vector LayoutHeads; - LayoutHeads.reserve(SI.S->atoms_size()); - - // First build the list of layout-heads (i.e. "heads" of layout-next - // chains). - DenseSet AlreadyLayedOut; - for (auto *DA : SI.S->atoms()) { - if (AlreadyLayedOut.count(DA)) - continue; - LayoutHeads.push_back(DA); - while (DA->hasLayoutNext()) { - auto &Next = DA->getLayoutNext(); - AlreadyLayedOut.insert(&Next); - DA = &Next; - } - } + // First build the set of layout-heads (i.e. "heads" of layout-next + // chains) by copying the section atoms, then eliminating any that + // appear as layout-next targets. + DenseSet LayoutHeads; + for (auto *DA : SI.S->atoms()) + LayoutHeads.insert(DA); + + for (auto *DA : SI.S->atoms()) + if (DA->hasLayoutNext()) + LayoutHeads.erase(&DA->getLayoutNext()); + + // Next, sort the layout heads by address order. + std::vector OrderedLayoutHeads; + OrderedLayoutHeads.reserve(LayoutHeads.size()); + for (auto *DA : LayoutHeads) + OrderedLayoutHeads.push_back(DA); // Now sort the list of layout heads by address. - std::sort(LayoutHeads.begin(), LayoutHeads.end(), + std::sort(OrderedLayoutHeads.begin(), OrderedLayoutHeads.end(), [](const DefinedAtom *LHS, const DefinedAtom *RHS) { return LHS->getAddress() < RHS->getAddress(); }); // Now populate the SI.Atoms field by appending each of the chains. - for (auto *DA : LayoutHeads) { + for (auto *DA : OrderedLayoutHeads) { SI.Atoms.push_back(DA); while (DA->hasLayoutNext()) { auto &Next = DA->getLayoutNext(); diff --git a/llvm/lib/ExecutionEngine/JITLink/MachOAtomGraphBuilder.cpp b/llvm/lib/ExecutionEngine/JITLink/MachOAtomGraphBuilder.cpp index 670fc3e..5feff39 100644 --- a/llvm/lib/ExecutionEngine/JITLink/MachOAtomGraphBuilder.cpp +++ b/llvm/lib/ExecutionEngine/JITLink/MachOAtomGraphBuilder.cpp @@ -44,6 +44,33 @@ void MachOAtomGraphBuilder::addCustomAtomizer(StringRef SectionName, CustomAtomizeFunctions[SectionName] = std::move(Atomizer); } +bool MachOAtomGraphBuilder::areLayoutLocked(const Atom &A, const Atom &B) { + // If these atoms are the same then they're trivially "locked". + if (&A == &B) + return true; + + // If A and B are different, check whether either is undefined. (in which + // case they are not locked). + if (!A.isDefined() || !B.isDefined()) + return false; + + // A and B are different, but they're both defined atoms. We need to check + // whether they're part of the same alt_entry chain. + auto &DA = static_cast(A); + auto &DB = static_cast(B); + + auto AStartItr = AltEntryStarts.find(&DA); + if (AStartItr == AltEntryStarts.end()) // If A is not in a chain bail out. + return false; + + auto BStartItr = AltEntryStarts.find(&DB); + if (BStartItr == AltEntryStarts.end()) // If B is not in a chain bail out. + return false; + + // A and B are layout locked if they're in the same chain. + return AStartItr->second == BStartItr->second; +} + unsigned MachOAtomGraphBuilder::getPointerSize(const object::MachOObjectFile &Obj) { return Obj.is64Bit() ? 8 : 4; @@ -126,6 +153,9 @@ Error MachOAtomGraphBuilder::addNonCustomAtoms() { DenseMap SecToAtoms; DenseMap FirstOrdinal; + std::vector AltEntryAtoms; + + DenseSet ProcessedSymbols; // Used to check for duplicate defs. for (auto SymI = Obj.symbol_begin(), SymE = Obj.symbol_end(); SymI != SymE; ++SymI) { @@ -135,6 +165,14 @@ Error MachOAtomGraphBuilder::addNonCustomAtoms() { if (!Name) return Name.takeError(); + // Bail out on duplicate definitions: There should never be more than one + // definition for a symbol in a given object file. + if (ProcessedSymbols.count(*Name)) + return make_error("Duplicate definition within object: " + + *Name); + else + ProcessedSymbols.insert(*Name); + auto Addr = Sym.getAddress(); if (!Addr) return Addr.takeError(); @@ -189,24 +227,35 @@ Error MachOAtomGraphBuilder::addNonCustomAtoms() { auto &Sec = SecByIndexItr->second; - auto &A = G->addDefinedAtom(Sec.getGenericSection(), *Name, *Addr, - std::max(Sym.getAlignment(), 1U)); + auto &DA = G->addDefinedAtom(Sec.getGenericSection(), *Name, *Addr, + std::max(Sym.getAlignment(), 1U)); + + DA.setGlobal(Flags & object::SymbolRef::SF_Global); + DA.setExported(Flags & object::SymbolRef::SF_Exported); + DA.setWeak(Flags & object::SymbolRef::SF_Weak); - A.setGlobal(Flags & object::SymbolRef::SF_Global); - A.setExported(Flags & object::SymbolRef::SF_Exported); - A.setWeak(Flags & object::SymbolRef::SF_Weak); + DA.setCallable(*SymType & object::SymbolRef::ST_Function); - A.setCallable(*SymType & object::SymbolRef::ST_Function); + // Check alt-entry. + { + uint16_t NDesc = 0; + if (Obj.is64Bit()) + NDesc = Obj.getSymbolTableEntry(SymI->getRawDataRefImpl()).n_desc; + else + NDesc = Obj.getSymbolTableEntry(SymI->getRawDataRefImpl()).n_desc; + if (NDesc & MachO::N_ALT_ENTRY) + AltEntryAtoms.push_back(&DA); + } LLVM_DEBUG({ dbgs() << " Added " << *Name << " addr: " << format("0x%016" PRIx64, *Addr) - << ", align: " << A.getAlignment() + << ", align: " << DA.getAlignment() << ", section: " << Sec.getGenericSection().getName() << "\n"; }); auto &SecAtoms = SecToAtoms[&Sec]; - SecAtoms[A.getAddress() - Sec.getAddress()] = &A; + SecAtoms[DA.getAddress() - Sec.getAddress()] = &DA; } // Add anonymous atoms. @@ -263,6 +312,50 @@ Error MachOAtomGraphBuilder::addNonCustomAtoms() { } } + LLVM_DEBUG(dbgs() << "Adding alt-entry starts\n"); + + // Sort alt-entry atoms by address in ascending order. + llvm::sort(AltEntryAtoms.begin(), AltEntryAtoms.end(), + [](const DefinedAtom *LHS, const DefinedAtom *RHS) { + return LHS->getAddress() < RHS->getAddress(); + }); + + // Process alt-entry atoms in address order to build the table of alt-entry + // atoms to alt-entry chain starts. + for (auto *DA : AltEntryAtoms) { + assert(!AltEntryStarts.count(DA) && "Duplicate entry in AltEntryStarts"); + + // DA is an alt-entry atom. Look for the predecessor atom that it is locked + // to, bailing out if we do not find one. + auto AltEntryPred = G->findAtomByAddress(DA->getAddress() - 1); + if (!AltEntryPred) + return AltEntryPred.takeError(); + + // Add a LayoutNext edge from the predecessor to this atom. + AltEntryPred->setLayoutNext(*DA); + + // Check to see whether the predecessor itself is an alt-entry atom. + auto AltEntryStartItr = AltEntryStarts.find(&*AltEntryPred); + if (AltEntryStartItr != AltEntryStarts.end()) { + // If the predecessor was an alt-entry atom then re-use its value. + AltEntryStarts[DA] = AltEntryStartItr->second; + LLVM_DEBUG({ + dbgs() << " " << *DA << " -> " << *AltEntryStartItr->second + << " (based on existing entry for " << *AltEntryPred << ")\n"; + }); + } else { + // If the predecessor does not have an entry then add an entry for this + // atom (i.e. the alt_entry atom) and a self-reference entry for the + /// predecessory atom that is the start of this chain. + AltEntryStarts[&*AltEntryPred] = &*AltEntryPred; + AltEntryStarts[DA] = &*AltEntryPred; + LLVM_DEBUG({ + dbgs() << " " << *AltEntryPred << " -> " << *AltEntryPred << "\n" + << " " << *DA << " -> " << *AltEntryPred << "\n"; + }); + } + } + return Error::success(); } diff --git a/llvm/lib/ExecutionEngine/JITLink/MachOAtomGraphBuilder.h b/llvm/lib/ExecutionEngine/JITLink/MachOAtomGraphBuilder.h index 340a11d..540e2c3 100644 --- a/llvm/lib/ExecutionEngine/JITLink/MachOAtomGraphBuilder.h +++ b/llvm/lib/ExecutionEngine/JITLink/MachOAtomGraphBuilder.h @@ -96,6 +96,10 @@ protected: virtual Error addRelocations() = 0; + /// Returns true if Atom A and Atom B are at a fixed offset from one another + /// (i.e. if they're part of the same alt-entry chain). + bool areLayoutLocked(const Atom &A, const Atom &B); + private: static unsigned getPointerSize(const object::MachOObjectFile &Obj); static support::endianness getEndianness(const object::MachOObjectFile &Obj); @@ -108,6 +112,7 @@ private: const object::MachOObjectFile &Obj; std::unique_ptr G; + DenseMap AltEntryStarts; DenseMap Sections; StringMap CustomAtomizeFunctions; Optional CommonSymbolsSection; diff --git a/llvm/lib/ExecutionEngine/JITLink/MachO_x86_64.cpp b/llvm/lib/ExecutionEngine/JITLink/MachO_x86_64.cpp index 75725db..d9472e4 100644 --- a/llvm/lib/ExecutionEngine/JITLink/MachO_x86_64.cpp +++ b/llvm/lib/ExecutionEngine/JITLink/MachO_x86_64.cpp @@ -181,19 +181,20 @@ private: MachOX86RelocationKind DeltaKind; Atom *TargetAtom; uint64_t Addend; - if (&AtomToFix == &*FromAtom) { + if (areLayoutLocked(AtomToFix, *FromAtom)) { TargetAtom = ToAtom; DeltaKind = (SubRI.r_length == 3) ? Delta64 : Delta32; Addend = FixupValue + (FixupAddress - FromAtom->getAddress()); // FIXME: handle extern 'from'. - } else if (&AtomToFix == ToAtom) { + } else if (areLayoutLocked(AtomToFix, *ToAtom)) { TargetAtom = &*FromAtom; DeltaKind = (SubRI.r_length == 3) ? NegDelta64 : NegDelta32; Addend = FixupValue - (FixupAddress - ToAtom->getAddress()); } else { // AtomToFix was neither FromAtom nor ToAtom. return make_error("SUBTRACTOR relocation must fix up " - "either 'A' or 'B'"); + "either 'A' or 'B' (or an atom in one " + "of their alt-entry groups)"); } return PairRelocInfo(DeltaKind, TargetAtom, Addend); diff --git a/llvm/test/ExecutionEngine/JITLink/X86/MachO_x86-64_relocations.s b/llvm/test/ExecutionEngine/JITLink/X86/MachO_x86-64_relocations.s index 6a9f0b4..9ff382d 100644 --- a/llvm/test/ExecutionEngine/JITLink/X86/MachO_x86-64_relocations.s +++ b/llvm/test/ExecutionEngine/JITLink/X86/MachO_x86-64_relocations.s @@ -129,13 +129,19 @@ Lanon_minuend_quad: Lanon_minuend_long: .long Lanon_minuend_long - named_data + 2 - # Named quad storage target (first named atom in __data). .globl named_data .p2align 3 named_data: .quad 0x2222222222222222 +# An alt-entry point for named_data + .globl named_data_alt_entry + .p2align 3 + .alt_entry named_data_alt_entry +named_data_alt_entry: + .quad 0 + # Check X86_64_RELOC_UNSIGNED / extern handling by putting the address of a # local named function in a pointer variable. # @@ -201,4 +207,60 @@ minuend_quad3: minuend_long3: .long minuend_long3 - named_data + 2 +# Check X86_64_RELOC_SUBTRACTOR handling for exprs of the form +# "A: .quad/long B - C + D", where 'B' or 'C' is at a fixed offset from 'A' +# (i.e. is part of an alt_entry chain that includes 'A'). +# +# Check "A: .long B - C + D" where 'B' is an alt_entry for 'A'. +# jitlink-check: *{4}subtractor_with_alt_entry_minuend_long = (subtractor_with_alt_entry_minuend_long_B - named_data + 2)[31:0] + .globl subtractor_with_alt_entry_minuend_long + .p2align 2 +subtractor_with_alt_entry_minuend_long: + .long subtractor_with_alt_entry_minuend_long_B - named_data + 2 + + .globl subtractor_with_alt_entry_minuend_long_B + .p2align 2 + .alt_entry subtractor_with_alt_entry_minuend_long_B +subtractor_with_alt_entry_minuend_long_B: + .long 0 + +# Check "A: .quad B - C + D" where 'B' is an alt_entry for 'A'. +# jitlink-check: *{8}subtractor_with_alt_entry_minuend_quad = (subtractor_with_alt_entry_minuend_quad_B - named_data + 2) + .globl subtractor_with_alt_entry_minuend_quad + .p2align 3 +subtractor_with_alt_entry_minuend_quad: + .quad subtractor_with_alt_entry_minuend_quad_B - named_data + 2 + + .globl subtractor_with_alt_entry_minuend_quad_B + .p2align 3 + .alt_entry subtractor_with_alt_entry_minuend_quad_B +subtractor_with_alt_entry_minuend_quad_B: + .quad 0 + +# Check "A: .long B - C + D" where 'C' is an alt_entry for 'A'. +# jitlink-check: *{4}subtractor_with_alt_entry_subtrahend_long = (named_data - subtractor_with_alt_entry_subtrahend_long_B + 2)[31:0] + .globl subtractor_with_alt_entry_subtrahend_long + .p2align 2 +subtractor_with_alt_entry_subtrahend_long: + .long named_data - subtractor_with_alt_entry_subtrahend_long_B + 2 + + .globl subtractor_with_alt_entry_subtrahend_long_B + .p2align 2 + .alt_entry subtractor_with_alt_entry_subtrahend_long_B +subtractor_with_alt_entry_subtrahend_long_B: + .long 0 + +# Check "A: .quad B - C + D" where 'B' is an alt_entry for 'A'. +# jitlink-check: *{8}subtractor_with_alt_entry_subtrahend_quad = (named_data - subtractor_with_alt_entry_subtrahend_quad_B + 2) + .globl subtractor_with_alt_entry_subtrahend_quad + .p2align 3 +subtractor_with_alt_entry_subtrahend_quad: + .quad named_data - subtractor_with_alt_entry_subtrahend_quad_B + 2 + + .globl subtractor_with_alt_entry_subtrahend_quad_B + .p2align 3 + .alt_entry subtractor_with_alt_entry_subtrahend_quad_B +subtractor_with_alt_entry_subtrahend_quad_B: + .quad 0 + .subsections_via_symbols -- 2.7.4