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  CommonSection =
41  &G->createSection(CommonSectionName, MemProt::Read | MemProt::Write);
42  return *CommonSection;
43  }
44 
45  std::unique_ptr<LinkGraph> G;
46 
47 private:
48  static StringRef CommonSectionName;
49  static ArrayRef<const char *> DwarfSectionNames;
50 
51  Section *CommonSection = nullptr;
52 };
53 
54 /// Ling-graph building code that's specific to the given ELFT, but common
55 /// across all architectures.
56 template <typename ELFT>
59 
60 public:
62  StringRef FileName,
63  LinkGraph::GetEdgeKindNameFunction GetEdgeKindName);
64 
65  /// Attempt to construct and return the LinkGraph.
67 
68  /// Call to derived class to handle relocations. These require
69  /// architecture specific knowledge to map to JITLink edge kinds.
70  virtual Error addRelocations() = 0;
71 
72 protected:
73  using ELFSectionIndex = unsigned;
74  using ELFSymbolIndex = unsigned;
75 
76  bool isRelocatable() const {
77  return Obj.getHeader().e_type == llvm::ELF::ET_REL;
78  }
79 
80  void setGraphSection(ELFSectionIndex SecIndex, Section &Sec) {
81  assert(!GraphSections.count(SecIndex) && "Duplicate section at index");
82  GraphSections[SecIndex] = &Sec;
83  }
84 
86  auto I = GraphSections.find(SecIndex);
87  if (I == GraphSections.end())
88  return nullptr;
89  return I->second;
90  }
91 
92  void setGraphSymbol(ELFSymbolIndex SymIndex, Symbol &Sym) {
93  assert(!GraphSymbols.count(SymIndex) && "Duplicate symbol at index");
94  GraphSymbols[SymIndex] = &Sym;
95  }
96 
98  auto I = GraphSymbols.find(SymIndex);
99  if (I == GraphSymbols.end())
100  return nullptr;
101  return I->second;
102  }
103 
105  getSymbolLinkageAndScope(const typename ELFT::Sym &Sym, StringRef Name);
106 
107  Error prepare();
110 
111  /// Traverse all matching relocation records in the given section. The handler
112  /// function Func should be callable with this signature:
113  /// Error(const typename ELFT::Rela &,
114  /// const typename ELFT::Shdr &, Section &)
115  ///
116  template <typename RelocHandlerFunction>
117  Error forEachRelocation(const typename ELFT::Shdr &RelSect,
118  RelocHandlerFunction &&Func,
119  bool ProcessDebugSections = false);
120 
121  /// Traverse all matching relocation records in the given section. Convenience
122  /// wrapper to allow passing a member function for the handler.
123  ///
124  template <typename ClassT, typename RelocHandlerMethod>
125  Error forEachRelocation(const typename ELFT::Shdr &RelSect, ClassT *Instance,
126  RelocHandlerMethod &&Method,
127  bool ProcessDebugSections = false) {
128  return forEachRelocation(
129  RelSect,
130  [Instance, Method](const auto &Rel, const auto &Target, auto &GS) {
131  return (Instance->*Method)(Rel, Target, GS);
132  },
133  ProcessDebugSections);
134  }
135 
136  const ELFFile &Obj;
137 
138  typename ELFFile::Elf_Shdr_Range Sections;
139  const typename ELFFile::Elf_Shdr *SymTabSec = nullptr;
141 
142  // Maps ELF section indexes to LinkGraph Sections.
143  // Only SHF_ALLOC sections will have graph sections.
146  DenseMap<const typename ELFFile::Elf_Shdr *,
149 };
150 
151 template <typename ELFT>
153  const ELFFile &Obj, Triple TT, StringRef FileName,
154  LinkGraph::GetEdgeKindNameFunction GetEdgeKindName)
155  : ELFLinkGraphBuilderBase(std::make_unique<LinkGraph>(
156  FileName.str(), Triple(std::move(TT)), ELFT::Is64Bits ? 8 : 4,
157  support::endianness(ELFT::TargetEndianness),
158  std::move(GetEdgeKindName))),
159  Obj(Obj) {
160  LLVM_DEBUG(
161  { dbgs() << "Created ELFLinkGraphBuilder for \"" << FileName << "\""; });
162 }
163 
164 template <typename ELFT>
166  if (!isRelocatable())
167  return make_error<JITLinkError>("Object is not a relocatable ELF file");
168 
169  if (auto Err = prepare())
170  return std::move(Err);
171 
172  if (auto Err = graphifySections())
173  return std::move(Err);
174 
175  if (auto Err = graphifySymbols())
176  return std::move(Err);
177 
178  if (auto Err = addRelocations())
179  return std::move(Err);
180 
181  return std::move(G);
182 }
183 
184 template <typename ELFT>
187  const typename ELFT::Sym &Sym, StringRef Name) {
188  Linkage L = Linkage::Strong;
190 
191  switch (Sym.getBinding()) {
192  case ELF::STB_LOCAL:
193  S = Scope::Local;
194  break;
195  case ELF::STB_GLOBAL:
196  // Nothing to do here.
197  break;
198  case ELF::STB_WEAK:
199  case ELF::STB_GNU_UNIQUE:
200  L = Linkage::Weak;
201  break;
202  default:
203  return make_error<StringError>(
204  "Unrecognized symbol binding " +
205  Twine(static_cast<int>(Sym.getBinding())) + " for " + Name,
207  }
208 
209  switch (Sym.getVisibility()) {
210  case ELF::STV_DEFAULT:
211  case ELF::STV_PROTECTED:
212  // FIXME: Make STV_DEFAULT symbols pre-emptible? This probably needs
213  // Orc support.
214  // Otherwise nothing to do here.
215  break;
216  case ELF::STV_HIDDEN:
217  // Default scope -> Hidden scope. No effect on local scope.
218  if (S == Scope::Default)
219  S = Scope::Hidden;
220  break;
221  case ELF::STV_INTERNAL:
222  return make_error<StringError>(
223  "Unrecognized symbol visibility " +
224  Twine(static_cast<int>(Sym.getVisibility())) + " for " + Name,
226  }
227 
228  return std::make_pair(L, S);
229 }
230 
231 template <typename ELFT> Error ELFLinkGraphBuilder<ELFT>::prepare() {
232  LLVM_DEBUG(dbgs() << " Preparing to build...\n");
233 
234  // Get the sections array.
235  if (auto SectionsOrErr = Obj.sections())
236  Sections = *SectionsOrErr;
237  else
238  return SectionsOrErr.takeError();
239 
240  // Get the section string table.
241  if (auto SectionStringTabOrErr = Obj.getSectionStringTable(Sections))
242  SectionStringTab = *SectionStringTabOrErr;
243  else
244  return SectionStringTabOrErr.takeError();
245 
246  // Get the SHT_SYMTAB section.
247  for (auto &Sec : Sections) {
248  if (Sec.sh_type == ELF::SHT_SYMTAB) {
249  if (!SymTabSec)
250  SymTabSec = &Sec;
251  else
252  return make_error<JITLinkError>("Multiple SHT_SYMTAB sections in " +
253  G->getName());
254  }
255 
256  // Extended table.
257  if (Sec.sh_type == ELF::SHT_SYMTAB_SHNDX) {
258  uint32_t SymtabNdx = Sec.sh_link;
259  if (SymtabNdx >= Sections.size())
260  return make_error<JITLinkError>("sh_link is out of bound");
261 
262  auto ShndxTable = Obj.getSHNDXTable(Sec);
263  if (!ShndxTable)
264  return ShndxTable.takeError();
265 
266  ShndxTables.insert({&Sections[SymtabNdx], *ShndxTable});
267  }
268  }
269 
270  return Error::success();
271 }
272 
274  LLVM_DEBUG(dbgs() << " Creating graph sections...\n");
275 
276  // For each section...
277  for (ELFSectionIndex SecIndex = 0; SecIndex != Sections.size(); ++SecIndex) {
278 
279  auto &Sec = Sections[SecIndex];
280 
281  // Start by getting the section name.
282  auto Name = Obj.getSectionName(Sec, SectionStringTab);
283  if (!Name)
284  return Name.takeError();
285 
286  // If the name indicates that it's a debug section then skip it: We don't
287  // support those yet.
288  if (isDwarfSection(*Name)) {
289  LLVM_DEBUG({
290  dbgs() << " " << SecIndex << ": \"" << *Name
291  << "\" is a debug section: "
292  "No graph section will be created.\n";
293  });
294  continue;
295  }
296 
297  // Skip non-SHF_ALLOC sections
298  if (!(Sec.sh_flags & ELF::SHF_ALLOC)) {
299  LLVM_DEBUG({
300  dbgs() << " " << SecIndex << ": \"" << *Name
301  << "\" is not an SHF_ALLOC section: "
302  "No graph section will be created.\n";
303  });
304  continue;
305  }
306 
307  LLVM_DEBUG({
308  dbgs() << " " << SecIndex << ": Creating section for \"" << *Name
309  << "\"\n";
310  });
311 
312  // Get the section's memory protection flags.
313  MemProt Prot;
314  if (Sec.sh_flags & ELF::SHF_EXECINSTR)
315  Prot = MemProt::Read | MemProt::Exec;
316  else
317  Prot = MemProt::Read | MemProt::Write;
318 
319  auto &GraphSec = G->createSection(*Name, Prot);
320  if (Sec.sh_type != ELF::SHT_NOBITS) {
321  auto Data = Obj.template getSectionContentsAsArray<char>(Sec);
322  if (!Data)
323  return Data.takeError();
324 
325  G->createContentBlock(GraphSec, *Data, Sec.sh_addr, Sec.sh_addralign, 0);
326  } else
327  G->createZeroFillBlock(GraphSec, Sec.sh_size, Sec.sh_addr,
328  Sec.sh_addralign, 0);
329 
330  setGraphSection(SecIndex, GraphSec);
331  }
332 
333  return Error::success();
334 }
335 
337  LLVM_DEBUG(dbgs() << " Creating graph symbols...\n");
338 
339  // No SYMTAB -- Bail out early.
340  if (!SymTabSec)
341  return Error::success();
342 
343  // Get the section content as a Symbols array.
344  auto Symbols = Obj.symbols(SymTabSec);
345  if (!Symbols)
346  return Symbols.takeError();
347 
348  // Get the string table for this section.
349  auto StringTab = Obj.getStringTableForSymtab(*SymTabSec, Sections);
350  if (!StringTab)
351  return StringTab.takeError();
352 
353  LLVM_DEBUG({
354  StringRef SymTabName;
355 
356  if (auto SymTabNameOrErr = Obj.getSectionName(*SymTabSec, SectionStringTab))
357  SymTabName = *SymTabNameOrErr;
358  else {
359  dbgs() << "Could not get ELF SHT_SYMTAB section name for logging: "
360  << toString(SymTabNameOrErr.takeError()) << "\n";
361  SymTabName = "<SHT_SYMTAB section with invalid name>";
362  }
363 
364  dbgs() << " Adding symbols from symtab section \"" << SymTabName
365  << "\"\n";
366  });
367 
368  for (ELFSymbolIndex SymIndex = 0; SymIndex != Symbols->size(); ++SymIndex) {
369  auto &Sym = (*Symbols)[SymIndex];
370 
371  // Check symbol type.
372  switch (Sym.getType()) {
373  case ELF::STT_FILE:
374  LLVM_DEBUG({
375  if (auto Name = Sym.getName(*StringTab))
376  dbgs() << " " << SymIndex << ": Skipping STT_FILE symbol \""
377  << *Name << "\"\n";
378  else {
379  dbgs() << "Could not get STT_FILE symbol name: "
380  << toString(Name.takeError()) << "\n";
381  dbgs() << " " << SymIndex
382  << ": Skipping STT_FILE symbol with invalid name\n";
383  }
384  });
385  continue;
386  break;
387  }
388 
389  // Get the symbol name.
390  auto Name = Sym.getName(*StringTab);
391  if (!Name)
392  return Name.takeError();
393 
394  // Handle common symbols specially.
395  if (Sym.isCommon()) {
396  Symbol &GSym =
397  G->addCommonSymbol(*Name, Scope::Default, getCommonSection(), 0,
398  Sym.st_size, Sym.getValue(), false);
399  setGraphSymbol(SymIndex, GSym);
400  continue;
401  }
402 
403  // Map Visibility and Binding to Scope and Linkage:
404  Linkage L;
405  Scope S;
406 
407  if (auto LSOrErr = getSymbolLinkageAndScope(Sym, *Name))
408  std::tie(L, S) = *LSOrErr;
409  else
410  return LSOrErr.takeError();
411 
412  if (Sym.isDefined() &&
413  (Sym.getType() == ELF::STT_NOTYPE || Sym.getType() == ELF::STT_FUNC ||
414  Sym.getType() == ELF::STT_OBJECT ||
415  Sym.getType() == ELF::STT_SECTION || Sym.getType() == ELF::STT_TLS)) {
416  // Handle extended tables.
417  unsigned Shndx = Sym.st_shndx;
418  if (Shndx == ELF::SHN_XINDEX) {
419  auto ShndxTable = ShndxTables.find(SymTabSec);
420  if (ShndxTable == ShndxTables.end())
421  continue;
422  auto NdxOrErr = object::getExtendedSymbolTableIndex<ELFT>(
423  Sym, SymIndex, ShndxTable->second);
424  if (!NdxOrErr)
425  return NdxOrErr.takeError();
426  Shndx = *NdxOrErr;
427  }
428  if (auto *GraphSec = getGraphSection(Shndx)) {
429  Block *B = nullptr;
430  {
431  auto Blocks = GraphSec->blocks();
432  assert(Blocks.begin() != Blocks.end() && "No blocks for section");
433  assert(std::next(Blocks.begin()) == Blocks.end() &&
434  "Multiple blocks for section");
435  B = *Blocks.begin();
436  }
437 
438  LLVM_DEBUG({
439  dbgs() << " " << SymIndex
440  << ": Creating defined graph symbol for ELF symbol \"" << *Name
441  << "\"\n";
442  });
443 
444  if (Sym.getType() == ELF::STT_SECTION)
445  *Name = GraphSec->getName();
446 
447  auto &GSym =
448  G->addDefinedSymbol(*B, Sym.getValue(), *Name, Sym.st_size, L, S,
449  Sym.getType() == ELF::STT_FUNC, false);
450  setGraphSymbol(SymIndex, GSym);
451  }
452  } else if (Sym.isUndefined() && Sym.isExternal()) {
453  LLVM_DEBUG({
454  dbgs() << " " << SymIndex
455  << ": Creating external graph symbol for ELF symbol \"" << *Name
456  << "\"\n";
457  });
458  auto &GSym = G->addExternalSymbol(*Name, Sym.st_size, L);
459  setGraphSymbol(SymIndex, GSym);
460  } else {
461  LLVM_DEBUG({
462  dbgs() << " " << SymIndex
463  << ": Not creating graph symbol for ELF symbol \"" << *Name
464  << "\" with unrecognized type\n";
465  });
466  }
467  }
468 
469  return Error::success();
470 }
471 
472 template <typename ELFT>
473 template <typename RelocHandlerFunction>
475  const typename ELFT::Shdr &RelSect, RelocHandlerFunction &&Func,
476  bool ProcessDebugSections) {
477 
478  // Only look into sections that store relocation entries.
479  if (RelSect.sh_type != ELF::SHT_RELA && RelSect.sh_type != ELF::SHT_REL)
480  return Error::success();
481 
482  // sh_info contains the section header index of the target (FixupSection),
483  // which is the section to which all relocations in RelSect apply.
484  auto FixupSection = Obj.getSection(RelSect.sh_info);
485  if (!FixupSection)
486  return FixupSection.takeError();
487 
488  // Target sections have names in valid ELF object files.
489  Expected<StringRef> Name = Obj.getSectionName(**FixupSection);
490  if (!Name)
491  return Name.takeError();
492  LLVM_DEBUG(dbgs() << " " << *Name << ":\n");
493 
494  // Consider skipping these relocations.
495  if (!ProcessDebugSections && isDwarfSection(*Name)) {
496  LLVM_DEBUG(dbgs() << " skipped (dwarf section)\n\n");
497  return Error::success();
498  }
499 
500  // Lookup the link-graph node corresponding to the target section name.
501  Section *GraphSect = G->findSectionByName(*Name);
502  if (!GraphSect)
503  return make_error<StringError>(
504  "Refencing a section that wasn't added to the graph: " + *Name,
506 
507  auto RelEntries = Obj.relas(RelSect);
508  if (!RelEntries)
509  return RelEntries.takeError();
510 
511  // Let the callee process relocation entries one by one.
512  for (const typename ELFT::Rela &R : *RelEntries)
513  if (Error Err = Func(R, **FixupSection, *GraphSect))
514  return Err;
515 
516  LLVM_DEBUG(dbgs() << "\n");
517  return Error::success();
518 }
519 
520 } // end namespace jitlink
521 } // end namespace llvm
522 
523 #undef DEBUG_TYPE
524 
525 #endif // LIB_EXECUTIONENGINE_JITLINK_ELFLINKGRAPHBUILDER_H
llvm::ELF::SHT_RELA
@ SHT_RELA
Definition: ELF.h:919
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::X86AS::GS
@ GS
Definition: X86.h:187
llvm::ELF::STB_GNU_UNIQUE
@ STB_GNU_UNIQUE
Definition: ELF.h:1147
llvm::Target
Target - Wrapper for Target specific information.
Definition: TargetRegistry.h:137
llvm::ELF::SHN_XINDEX
@ SHN_XINDEX
Definition: ELF.h:909
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::STV_INTERNAL
@ STV_INTERNAL
Definition: ELF.h:1175
llvm::Expected
Tagged union holding either a T or a Error.
Definition: APFloat.h:42
llvm::Data
@ Data
Definition: SIMachineScheduler.h:55
llvm::ELF::SHF_EXECINSTR
@ SHF_EXECINSTR
Definition: ELF.h:997
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:207
llvm::ELF::STT_TLS
@ STT_TLS
Definition: ELF.h:1162
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::ELF::SHT_SYMTAB
@ SHT_SYMTAB
Definition: ELF.h:917
llvm::ELF::STB_WEAK
@ STB_WEAK
Definition: ELF.h:1146
llvm::ELF::SHT_SYMTAB_SHNDX
@ SHT_SYMTAB_SHNDX
Definition: ELF.h:931
llvm::ELF::STV_DEFAULT
@ STV_DEFAULT
Definition: ELF.h:1174
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::ELF::STT_FILE
@ STT_FILE
Definition: ELF.h:1160
llvm::ELF::STB_GLOBAL
@ STB_GLOBAL
Definition: ELF.h:1145
FormatVariadic.h
llvm::ELF::STT_FUNC
@ STT_FUNC
Definition: ELF.h:1158
llvm::ELF::STB_LOCAL
@ STB_LOCAL
Definition: ELF.h:1144
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
ELF.h
llvm::ELF::SHT_REL
@ SHT_REL
Definition: ELF.h:924
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::ELF::SHF_ALLOC
@ SHF_ALLOC
Definition: ELF.h:994
llvm::DenseMap
Definition: DenseMap.h:714
llvm::ELF::STV_PROTECTED
@ STV_PROTECTED
Definition: ELF.h:1177
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:1665
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:1658
llvm::ELF::STT_OBJECT
@ STT_OBJECT
Definition: ELF.h:1157
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:57
llvm::ELF::STV_HIDDEN
@ STV_HIDDEN
Definition: ELF.h:1176
uint32_t
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::object::ELFFile::getHeader
const Elf_Ehdr & getHeader() const
Definition: ELF.h:188
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::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::STT_SECTION
@ STT_SECTION
Definition: ELF.h:1159
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::ET_REL
@ ET_REL
Definition: ELF.h:117
isDwarfSection
static bool isDwarfSection(const MCObjectFileInfo *FI, const MCSection *Section)
Definition: NVPTXTargetStreamer.cpp:42
llvm::ELF::STT_NOTYPE
@ STT_NOTYPE
Definition: ELF.h:1156
llvm::ELF::SHT_NOBITS
@ SHT_NOBITS
Definition: ELF.h:923
llvm::object::ELFFile
Definition: ELF.h:94
Debug.h
Shdr
Elf_Shdr Shdr
Definition: ELFObjHandler.cpp:79