LLVM  14.0.0git
ELFLinkGraphBuilder.h
Go to the documentation of this file.
1 //===------- ELFLinkGraphBuilder.h - ELF LinkGraph builder ------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Generic ELF LinkGraph building code.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LIB_EXECUTIONENGINE_JITLINK_ELFLINKGRAPHBUILDER_H
14 #define LIB_EXECUTIONENGINE_JITLINK_ELFLINKGRAPHBUILDER_H
15 
17 #include "llvm/Object/ELF.h"
18 #include "llvm/Support/Debug.h"
19 #include "llvm/Support/Error.h"
21 
22 #define DEBUG_TYPE "jitlink"
23 
24 namespace llvm {
25 namespace jitlink {
26 
27 /// Common link-graph building code shared between all ELFFiles.
29 public:
30  ELFLinkGraphBuilderBase(std::unique_ptr<LinkGraph> G) : G(std::move(G)) {}
31  virtual ~ELFLinkGraphBuilderBase();
32 
33 protected:
35  return llvm::is_contained(DwarfSectionNames, SectionName);
36  }
37 
39  if (!CommonSection) {
40  auto Prot = static_cast<sys::Memory::ProtectionFlags>(
42  CommonSection = &G->createSection(CommonSectionName, Prot);
43  }
44  return *CommonSection;
45  }
46 
47  std::unique_ptr<LinkGraph> G;
48 
49 private:
50  static StringRef CommonSectionName;
51  static ArrayRef<const char *> DwarfSectionNames;
52 
53  Section *CommonSection = nullptr;
54 };
55 
56 /// Ling-graph building code that's specific to the given ELFT, but common
57 /// across all architectures.
58 template <typename ELFT>
61 
62 public:
64  StringRef FileName,
65  LinkGraph::GetEdgeKindNameFunction GetEdgeKindName);
66 
67  /// Attempt to construct and return the LinkGraph.
69 
70  /// Call to derived class to handle relocations. These require
71  /// architecture specific knowledge to map to JITLink edge kinds.
72  virtual Error addRelocations() = 0;
73 
74 protected:
75  using ELFSectionIndex = unsigned;
76  using ELFSymbolIndex = unsigned;
77 
78  bool isRelocatable() const {
79  return Obj.getHeader().e_type == llvm::ELF::ET_REL;
80  }
81 
82  void setGraphSection(ELFSectionIndex SecIndex, Section &Sec) {
83  assert(!GraphSections.count(SecIndex) && "Duplicate section at index");
84  GraphSections[SecIndex] = &Sec;
85  }
86 
88  auto I = GraphSections.find(SecIndex);
89  if (I == GraphSections.end())
90  return nullptr;
91  return I->second;
92  }
93 
94  void setGraphSymbol(ELFSymbolIndex SymIndex, Symbol &Sym) {
95  assert(!GraphSymbols.count(SymIndex) && "Duplicate symbol at index");
96  GraphSymbols[SymIndex] = &Sym;
97  }
98 
100  auto I = GraphSymbols.find(SymIndex);
101  if (I == GraphSymbols.end())
102  return nullptr;
103  return I->second;
104  }
105 
107  getSymbolLinkageAndScope(const typename ELFT::Sym &Sym, StringRef Name);
108 
109  Error prepare();
112 
113  /// Traverse all matching relocation records in the given section. The handler
114  /// function Func should be callable with this signature:
115  /// Error(const typename ELFT::Rela &,
116  /// const typename ELFT::Shdr &, Section &)
117  ///
118  template <typename RelocHandlerFunction>
119  Error forEachRelocation(const typename ELFT::Shdr &RelSect,
120  RelocHandlerFunction &&Func,
121  bool ProcessDebugSections = false);
122 
123  /// Traverse all matching relocation records in the given section. Convenience
124  /// wrapper to allow passing a member function for the handler.
125  ///
126  template <typename ClassT, typename RelocHandlerMethod>
127  Error forEachRelocation(const typename ELFT::Shdr &RelSect, ClassT *Instance,
128  RelocHandlerMethod &&Method,
129  bool ProcessDebugSections = false) {
130  return forEachRelocation(
131  RelSect,
132  [Instance, Method](const auto &Rel, const auto &Target, auto &GS) {
133  return (Instance->*Method)(Rel, Target, GS);
134  },
135  ProcessDebugSections);
136  }
137 
138  const ELFFile &Obj;
139 
140  typename ELFFile::Elf_Shdr_Range Sections;
141  const typename ELFFile::Elf_Shdr *SymTabSec = nullptr;
143 
144  // Maps ELF section indexes to LinkGraph Sections.
145  // Only SHF_ALLOC sections will have graph sections.
148 };
149 
150 template <typename ELFT>
152  const ELFFile &Obj, Triple TT, StringRef FileName,
153  LinkGraph::GetEdgeKindNameFunction GetEdgeKindName)
154  : ELFLinkGraphBuilderBase(std::make_unique<LinkGraph>(
155  FileName.str(), Triple(std::move(TT)), ELFT::Is64Bits ? 8 : 4,
156  support::endianness(ELFT::TargetEndianness),
157  std::move(GetEdgeKindName))),
158  Obj(Obj) {
159  LLVM_DEBUG(
160  { dbgs() << "Created ELFLinkGraphBuilder for \"" << FileName << "\""; });
161 }
162 
163 template <typename ELFT>
165  if (!isRelocatable())
166  return make_error<JITLinkError>("Object is not a relocatable ELF file");
167 
168  if (auto Err = prepare())
169  return std::move(Err);
170 
171  if (auto Err = graphifySections())
172  return std::move(Err);
173 
174  if (auto Err = graphifySymbols())
175  return std::move(Err);
176 
177  if (auto Err = addRelocations())
178  return std::move(Err);
179 
180  return std::move(G);
181 }
182 
183 template <typename ELFT>
186  const typename ELFT::Sym &Sym, StringRef Name) {
187  Linkage L = Linkage::Strong;
189 
190  switch (Sym.getBinding()) {
191  case ELF::STB_LOCAL:
192  S = Scope::Local;
193  break;
194  case ELF::STB_GLOBAL:
195  // Nothing to do here.
196  break;
197  case ELF::STB_WEAK:
198  case ELF::STB_GNU_UNIQUE:
199  L = Linkage::Weak;
200  break;
201  default:
202  return make_error<StringError>(
203  "Unrecognized symbol binding " +
204  Twine(static_cast<int>(Sym.getBinding())) + " for " + Name,
206  }
207 
208  switch (Sym.getVisibility()) {
209  case ELF::STV_DEFAULT:
210  case ELF::STV_PROTECTED:
211  // FIXME: Make STV_DEFAULT symbols pre-emptible? This probably needs
212  // Orc support.
213  // Otherwise nothing to do here.
214  break;
215  case ELF::STV_HIDDEN:
216  // Default scope -> Hidden scope. No effect on local scope.
217  if (S == Scope::Default)
218  S = Scope::Hidden;
219  break;
220  case ELF::STV_INTERNAL:
221  return make_error<StringError>(
222  "Unrecognized symbol visibility " +
223  Twine(static_cast<int>(Sym.getVisibility())) + " for " + Name,
225  }
226 
227  return std::make_pair(L, S);
228 }
229 
230 template <typename ELFT> Error ELFLinkGraphBuilder<ELFT>::prepare() {
231  LLVM_DEBUG(dbgs() << " Preparing to build...\n");
232 
233  // Get the sections array.
234  if (auto SectionsOrErr = Obj.sections())
235  Sections = *SectionsOrErr;
236  else
237  return SectionsOrErr.takeError();
238 
239  // Get the section string table.
240  if (auto SectionStringTabOrErr = Obj.getSectionStringTable(Sections))
241  SectionStringTab = *SectionStringTabOrErr;
242  else
243  return SectionStringTabOrErr.takeError();
244 
245  // Get the SHT_SYMTAB section.
246  for (auto &Sec : Sections)
247  if (Sec.sh_type == ELF::SHT_SYMTAB) {
248  if (!SymTabSec)
249  SymTabSec = &Sec;
250  else
251  return make_error<JITLinkError>("Multiple SHT_SYMTAB sections in " +
252  G->getName());
253  }
254 
255  return Error::success();
256 }
257 
259  LLVM_DEBUG(dbgs() << " Creating graph sections...\n");
260 
261  // For each section...
262  for (ELFSectionIndex SecIndex = 0; SecIndex != Sections.size(); ++SecIndex) {
263 
264  auto &Sec = Sections[SecIndex];
265 
266  // Start by getting the section name.
267  auto Name = Obj.getSectionName(Sec, SectionStringTab);
268  if (!Name)
269  return Name.takeError();
270 
271  // If the name indicates that it's a debug section then skip it: We don't
272  // support those yet.
273  if (isDwarfSection(*Name)) {
274  LLVM_DEBUG({
275  dbgs() << " " << SecIndex << ": \"" << *Name
276  << "\" is a debug section: "
277  "No graph section will be created.\n";
278  });
279  continue;
280  }
281 
282  // Skip non-SHF_ALLOC sections
283  if (!(Sec.sh_flags & ELF::SHF_ALLOC)) {
284  LLVM_DEBUG({
285  dbgs() << " " << SecIndex << ": \"" << *Name
286  << "\" is not an SHF_ALLOC section: "
287  "No graph section will be created.\n";
288  });
289  continue;
290  }
291 
292  LLVM_DEBUG({
293  dbgs() << " " << SecIndex << ": Creating section for \"" << *Name
294  << "\"\n";
295  });
296 
297  // Get the section's memory protection flags.
299  if (Sec.sh_flags & ELF::SHF_EXECINSTR)
300  Prot = static_cast<sys::Memory::ProtectionFlags>(sys::Memory::MF_READ |
301  sys::Memory::MF_EXEC);
302  else
303  Prot = static_cast<sys::Memory::ProtectionFlags>(sys::Memory::MF_READ |
304  sys::Memory::MF_WRITE);
305 
306  // For now we just use this to skip the "undefined" section, probably need
307  // to revist.
308  if (Sec.sh_size == 0)
309  continue;
310 
311  auto &GraphSec = G->createSection(*Name, Prot);
312  if (Sec.sh_type != ELF::SHT_NOBITS) {
313  auto Data = Obj.template getSectionContentsAsArray<char>(Sec);
314  if (!Data)
315  return Data.takeError();
316 
317  G->createContentBlock(GraphSec, *Data, Sec.sh_addr, Sec.sh_addralign, 0);
318  } else
319  G->createZeroFillBlock(GraphSec, Sec.sh_size, Sec.sh_addr,
320  Sec.sh_addralign, 0);
321 
322  setGraphSection(SecIndex, GraphSec);
323  }
324 
325  return Error::success();
326 }
327 
329  LLVM_DEBUG(dbgs() << " Creating graph symbols...\n");
330 
331  // No SYMTAB -- Bail out early.
332  if (!SymTabSec)
333  return Error::success();
334 
335  // Get the section content as a Symbols array.
336  auto Symbols = Obj.symbols(SymTabSec);
337  if (!Symbols)
338  return Symbols.takeError();
339 
340  // Get the string table for this section.
341  auto StringTab = Obj.getStringTableForSymtab(*SymTabSec, Sections);
342  if (!StringTab)
343  return StringTab.takeError();
344 
345  LLVM_DEBUG({
346  StringRef SymTabName;
347 
348  if (auto SymTabNameOrErr = Obj.getSectionName(*SymTabSec, SectionStringTab))
349  SymTabName = *SymTabNameOrErr;
350  else {
351  dbgs() << "Could not get ELF SHT_SYMTAB section name for logging: "
352  << toString(SymTabNameOrErr.takeError()) << "\n";
353  SymTabName = "<SHT_SYMTAB section with invalid name>";
354  }
355 
356  dbgs() << " Adding symbols from symtab section \"" << SymTabName
357  << "\"\n";
358  });
359 
360  for (ELFSymbolIndex SymIndex = 0; SymIndex != Symbols->size(); ++SymIndex) {
361  auto &Sym = (*Symbols)[SymIndex];
362 
363  // Check symbol type.
364  switch (Sym.getType()) {
365  case ELF::STT_FILE:
366  LLVM_DEBUG({
367  if (auto Name = Sym.getName(*StringTab))
368  dbgs() << " " << SymIndex << ": Skipping STT_FILE symbol \""
369  << *Name << "\"\n";
370  else {
371  dbgs() << "Could not get STT_FILE symbol name: "
372  << toString(Name.takeError()) << "\n";
373  dbgs() << " " << SymIndex
374  << ": Skipping STT_FILE symbol with invalid name\n";
375  }
376  });
377  continue;
378  break;
379  }
380 
381  // Get the symbol name.
382  auto Name = Sym.getName(*StringTab);
383  if (!Name)
384  return Name.takeError();
385 
386  // Handle common symbols specially.
387  if (Sym.isCommon()) {
388  Symbol &GSym =
389  G->addCommonSymbol(*Name, Scope::Default, getCommonSection(), 0,
390  Sym.st_size, Sym.getValue(), false);
391  setGraphSymbol(SymIndex, GSym);
392  continue;
393  }
394 
395  // Map Visibility and Binding to Scope and Linkage:
396  Linkage L;
397  Scope S;
398 
399  if (auto LSOrErr = getSymbolLinkageAndScope(Sym, *Name))
400  std::tie(L, S) = *LSOrErr;
401  else
402  return LSOrErr.takeError();
403 
404  if (Sym.isDefined() &&
405  (Sym.getType() == ELF::STT_NOTYPE || Sym.getType() == ELF::STT_FUNC ||
406  Sym.getType() == ELF::STT_OBJECT ||
407  Sym.getType() == ELF::STT_SECTION || Sym.getType() == ELF::STT_TLS)) {
408 
409  // FIXME: Handle extended tables.
410  if (auto *GraphSec = getGraphSection(Sym.st_shndx)) {
411  Block *B = nullptr;
412  {
413  auto Blocks = GraphSec->blocks();
414  assert(Blocks.begin() != Blocks.end() && "No blocks for section");
415  assert(std::next(Blocks.begin()) == Blocks.end() &&
416  "Multiple blocks for section");
417  B = *Blocks.begin();
418  }
419 
420  LLVM_DEBUG({
421  dbgs() << " " << SymIndex
422  << ": Creating defined graph symbol for ELF symbol \"" << *Name
423  << "\"\n";
424  });
425 
426  if (Sym.getType() == ELF::STT_SECTION)
427  *Name = GraphSec->getName();
428 
429  auto &GSym =
430  G->addDefinedSymbol(*B, Sym.getValue(), *Name, Sym.st_size, L, S,
431  Sym.getType() == ELF::STT_FUNC, false);
432  setGraphSymbol(SymIndex, GSym);
433  }
434  } else if (Sym.isUndefined() && Sym.isExternal()) {
435  LLVM_DEBUG({
436  dbgs() << " " << SymIndex
437  << ": Creating external graph symbol for ELF symbol \"" << *Name
438  << "\"\n";
439  });
440  auto &GSym = G->addExternalSymbol(*Name, Sym.st_size, L);
441  setGraphSymbol(SymIndex, GSym);
442  } else {
443  LLVM_DEBUG({
444  dbgs() << " " << SymIndex
445  << ": Not creating graph symbol for ELF symbol \"" << *Name
446  << "\" with unrecognized type\n";
447  });
448  }
449  }
450 
451  return Error::success();
452 }
453 
454 template <typename ELFT>
455 template <typename RelocHandlerFunction>
457  const typename ELFT::Shdr &RelSect, RelocHandlerFunction &&Func,
458  bool ProcessDebugSections) {
459 
460  // Only look into sections that store relocation entries.
461  if (RelSect.sh_type != ELF::SHT_RELA && RelSect.sh_type != ELF::SHT_REL)
462  return Error::success();
463 
464  // sh_info contains the section header index of the target (FixupSection),
465  // which is the section to which all relocations in RelSect apply.
466  auto FixupSection = Obj.getSection(RelSect.sh_info);
467  if (!FixupSection)
468  return FixupSection.takeError();
469 
470  // Target sections have names in valid ELF object files.
471  Expected<StringRef> Name = Obj.getSectionName(**FixupSection);
472  if (!Name)
473  return Name.takeError();
474  LLVM_DEBUG(dbgs() << " " << *Name << ":\n");
475 
476  // Consider skipping these relocations.
477  if (!ProcessDebugSections && isDwarfSection(*Name)) {
478  LLVM_DEBUG(dbgs() << " skipped (dwarf section)\n\n");
479  return Error::success();
480  }
481 
482  // Lookup the link-graph node corresponding to the target section name.
483  Section *GraphSect = G->findSectionByName(*Name);
484  if (!GraphSect)
485  return make_error<StringError>(
486  "Refencing a section that wasn't added to the graph: " + *Name,
488 
489  auto RelEntries = Obj.relas(RelSect);
490  if (!RelEntries)
491  return RelEntries.takeError();
492 
493  // Let the callee process relocation entries one by one.
494  for (const typename ELFT::Rela &R : *RelEntries)
495  if (Error Err = Func(R, **FixupSection, *GraphSect))
496  return Err;
497 
498  LLVM_DEBUG(dbgs() << "\n");
499  return Error::success();
500 }
501 
502 } // end namespace jitlink
503 } // end namespace llvm
504 
505 #undef DEBUG_TYPE
506 
507 #endif // LIB_EXECUTIONENGINE_JITLINK_ELFLINKGRAPHBUILDER_H
llvm::sys::Memory::MF_READ
@ MF_READ
Definition: Memory.h:55
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::sys::Memory::MF_WRITE
@ MF_WRITE
Definition: Memory.h:56
llvm::ELF::STT_NOTYPE
@ STT_NOTYPE
Definition: ELF.h:1150
llvm::Target
Target - Wrapper for Target specific information.
Definition: TargetRegistry.h:137
llvm::ELF::STT_TLS
@ STT_TLS
Definition: ELF.h:1156
llvm::ELF::STT_FILE
@ STT_FILE
Definition: ELF.h:1154
Error.h
llvm::Triple
Triple - Helper class for working with autoconf configuration names.
Definition: Triple.h:45
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::ELF::STB_GLOBAL
@ STB_GLOBAL
Definition: ELF.h:1139
llvm::ELF::SHF_EXECINSTR
@ SHF_EXECINSTR
Definition: ELF.h:991
llvm::Expected
Tagged union holding either a T or a Error.
Definition: APFloat.h:42
llvm::ELF::SHT_RELA
@ SHT_RELA
Definition: ELF.h:913
llvm::Data
@ Data
Definition: SIMachineScheduler.h:55
llvm::ELF::SHT_SYMTAB
@ SHT_SYMTAB
Definition: ELF.h:911
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:198
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::ELF::STV_HIDDEN
@ STV_HIDDEN
Definition: ELF.h:1170
llvm::sys::Memory::ProtectionFlags
ProtectionFlags
Definition: Memory.h:54
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
FormatVariadic.h
llvm::ELF::STB_WEAK
@ STB_WEAK
Definition: ELF.h:1140
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
ELF.h
llvm::X86AS::GS
@ GS
Definition: X86.h:187
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1616
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1609
llvm::ELF::STV_DEFAULT
@ STV_DEFAULT
Definition: ELF.h:1168
llvm::ELF::STT_FUNC
@ STT_FUNC
Definition: ELF.h:1152
llvm::ELF::STV_PROTECTED
@ STV_PROTECTED
Definition: ELF.h:1171
llvm::ELF::SHF_ALLOC
@ SHF_ALLOC
Definition: ELF.h:988
llvm::ArrayRef< const char * >
llvm::wasm::toString
std::string toString(WasmSymbolType type)
Definition: Wasm.cpp:11
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::ELF::STV_INTERNAL
@ STV_INTERNAL
Definition: ELF.h:1169
llvm::object::ELFFile::getHeader
const Elf_Ehdr & getHeader() const
Definition: ELF.h:192
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
std
Definition: BitVector.h:838
llvm::ELF::STT_OBJECT
@ STT_OBJECT
Definition: ELF.h:1151
llvm::inconvertibleErrorCode
std::error_code inconvertibleErrorCode()
The value returned by this function can be returned from convertToErrorCode for Error values where no...
Definition: Error.cpp:77
llvm::SectionName
Definition: DWARFSection.h:21
llvm::Error
Lightweight error class with error context and mandatory checking.
Definition: Error.h:157
llvm::TargetStackID::Default
@ Default
Definition: TargetFrameLowering.h:28
llvm::ELF::STB_LOCAL
@ STB_LOCAL
Definition: ELF.h:1138
support
Reimplement select in terms of SEL *We would really like to support but we need to prove that the add doesn t need to overflow between the two bit chunks *Implement pre post increment support(e.g. PR935) *Implement smarter const ant generation for binops with large immediates. A few ARMv6T2 ops should be pattern matched
Definition: README.txt:10
llvm::support::endianness
endianness
Definition: Endian.h:27
llvm::ELF::STT_SECTION
@ STT_SECTION
Definition: ELF.h:1153
llvm::ELF::ET_REL
@ ET_REL
Definition: ELF.h:117
llvm::ELF::SHT_REL
@ SHT_REL
Definition: ELF.h:918
isDwarfSection
static bool isDwarfSection(const MCObjectFileInfo *FI, const MCSection *Section)
Definition: NVPTXTargetStreamer.cpp:42
llvm::ELF::SHT_NOBITS
@ SHT_NOBITS
Definition: ELF.h:917
llvm::object::ELFFile
Definition: ELF.h:98
Debug.h
llvm::ELF::STB_GNU_UNIQUE
@ STB_GNU_UNIQUE
Definition: ELF.h:1141
Shdr
Elf_Shdr Shdr
Definition: ELFObjHandler.cpp:79