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 
16 #include "llvm/ExecutionEngine/JITLink/JITLink.h"
17 #include "llvm/Object/ELF.h"
18 #include "llvm/Support/Debug.h"
19 #include "llvm/Support/Error.h"
20 #include "llvm/Support/FormatVariadic.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.
28 class ELFLinkGraphBuilderBase {
29 public:
30   ELFLinkGraphBuilderBase(std::unique_ptr<LinkGraph> G) : G(std::move(G)) {}
31   virtual ~ELFLinkGraphBuilderBase();
32 
33 protected:
34   static bool isDwarfSection(StringRef SectionName) {
35     return llvm::is_contained(DwarfSectionNames, SectionName);
36   }
37 
38   Section &getCommonSection() {
39     if (!CommonSection) {
40       auto Prot = static_cast<sys::Memory::ProtectionFlags>(
41           sys::Memory::MF_READ | sys::Memory::MF_WRITE);
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>
59 class ELFLinkGraphBuilder : public ELFLinkGraphBuilderBase {
60   using ELFFile = object::ELFFile<ELFT>;
61 
62 public:
63   ELFLinkGraphBuilder(const object::ELFFile<ELFT> &Obj, Triple TT,
64                       StringRef FileName,
65                       LinkGraph::GetEdgeKindNameFunction GetEdgeKindName);
66 
67   /// Attempt to construct and return the LinkGraph.
68   Expected<std::unique_ptr<LinkGraph>> buildGraph();
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 
87   Section *getGraphSection(ELFSectionIndex SecIndex) {
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 
99   Symbol *getGraphSymbol(ELFSymbolIndex SymIndex) {
100     auto I = GraphSymbols.find(SymIndex);
101     if (I == GraphSymbols.end())
102       return nullptr;
103     return I->second;
104   }
105 
106   Expected<std::pair<Linkage, Scope>>
107   getSymbolLinkageAndScope(const typename ELFT::Sym &Sym, StringRef Name);
108 
109   Error prepare();
110   Error graphifySections();
111   Error graphifySymbols();
112 
113   const ELFFile &Obj;
114 
115   typename ELFFile::Elf_Shdr_Range Sections;
116   const typename ELFFile::Elf_Shdr *SymTabSec = nullptr;
117   StringRef SectionStringTab;
118 
119   // Maps ELF section indexes to LinkGraph Sections.
120   // Only SHF_ALLOC sections will have graph sections.
121   DenseMap<ELFSectionIndex, Section *> GraphSections;
122   DenseMap<ELFSymbolIndex, Symbol *> GraphSymbols;
123 };
124 
125 template <typename ELFT>
126 ELFLinkGraphBuilder<ELFT>::ELFLinkGraphBuilder(
127     const ELFFile &Obj, Triple TT, StringRef FileName,
128     LinkGraph::GetEdgeKindNameFunction GetEdgeKindName)
129     : ELFLinkGraphBuilderBase(std::make_unique<LinkGraph>(
130           FileName.str(), Triple(std::move(TT)), ELFT::Is64Bits ? 8 : 4,
131           support::endianness(ELFT::TargetEndianness),
132           std::move(GetEdgeKindName))),
133       Obj(Obj) {
134   LLVM_DEBUG(
135       { dbgs() << "Created ELFLinkGraphBuilder for \"" << FileName << "\""; });
136 }
137 
138 template <typename ELFT>
139 Expected<std::unique_ptr<LinkGraph>> ELFLinkGraphBuilder<ELFT>::buildGraph() {
140   if (!isRelocatable())
141     return make_error<JITLinkError>("Object is not a relocatable ELF file");
142 
143   if (auto Err = prepare())
144     return std::move(Err);
145 
146   if (auto Err = graphifySections())
147     return std::move(Err);
148 
149   if (auto Err = graphifySymbols())
150     return std::move(Err);
151 
152   if (auto Err = addRelocations())
153     return std::move(Err);
154 
155   return std::move(G);
156 }
157 
158 template <typename ELFT>
159 Expected<std::pair<Linkage, Scope>>
160 ELFLinkGraphBuilder<ELFT>::getSymbolLinkageAndScope(
161     const typename ELFT::Sym &Sym, StringRef Name) {
162   Linkage L = Linkage::Strong;
163   Scope S = Scope::Default;
164 
165   switch (Sym.getBinding()) {
166   case ELF::STB_LOCAL:
167     S = Scope::Local;
168     break;
169   case ELF::STB_GLOBAL:
170     // Nothing to do here.
171     break;
172   case ELF::STB_WEAK:
173     L = Linkage::Weak;
174     break;
175   default:
176     return make_error<StringError>("Unrecognized symbol binding for " + Name,
177                                    inconvertibleErrorCode());
178   }
179 
180   switch (Sym.getVisibility()) {
181   case ELF::STV_DEFAULT:
182   case ELF::STV_PROTECTED:
183     // FIXME: Make STV_DEFAULT symbols pre-emptible? This probably needs
184     // Orc support.
185     // Otherwise nothing to do here.
186     break;
187   case ELF::STV_HIDDEN:
188     // Default scope -> Hidden scope. No effect on local scope.
189     if (S == Scope::Default)
190       S = Scope::Hidden;
191     break;
192   case ELF::STV_INTERNAL:
193     return make_error<StringError>("Unrecognized symbol visibility for " + Name,
194                                    inconvertibleErrorCode());
195   }
196 
197   return std::make_pair(L, S);
198 }
199 
200 template <typename ELFT> Error ELFLinkGraphBuilder<ELFT>::prepare() {
201   LLVM_DEBUG(dbgs() << "  Preparing to build...\n");
202 
203   // Get the sections array.
204   if (auto SectionsOrErr = Obj.sections())
205     Sections = *SectionsOrErr;
206   else
207     return SectionsOrErr.takeError();
208 
209   // Get the section string table.
210   if (auto SectionStringTabOrErr = Obj.getSectionStringTable(Sections))
211     SectionStringTab = *SectionStringTabOrErr;
212   else
213     return SectionStringTabOrErr.takeError();
214 
215   // Get the SHT_SYMTAB section.
216   for (auto &Sec : Sections)
217     if (Sec.sh_type == ELF::SHT_SYMTAB) {
218       if (!SymTabSec)
219         SymTabSec = &Sec;
220       else
221         return make_error<JITLinkError>("Multiple SHT_SYMTAB sections in " +
222                                         G->getName());
223     }
224 
225   return Error::success();
226 }
227 
228 template <typename ELFT> Error ELFLinkGraphBuilder<ELFT>::graphifySections() {
229   LLVM_DEBUG(dbgs() << "  Creating graph sections...\n");
230 
231   // For each section...
232   for (ELFSectionIndex SecIndex = 0; SecIndex != Sections.size(); ++SecIndex) {
233 
234     auto &Sec = Sections[SecIndex];
235 
236     // Start by getting the section name.
237     auto Name = Obj.getSectionName(Sec, SectionStringTab);
238     if (!Name)
239       return Name.takeError();
240 
241     // If the name indicates that it's a debug section then skip it: We don't
242     // support those yet.
243     if (isDwarfSection(*Name)) {
244       LLVM_DEBUG({
245         dbgs() << "    " << SecIndex << ": \"" << *Name
246                << "\" is a debug section: "
247                   "No graph section will be created.\n";
248       });
249       continue;
250     }
251 
252     // Skip non-SHF_ALLOC sections
253     if (!(Sec.sh_flags & ELF::SHF_ALLOC)) {
254       LLVM_DEBUG({
255         dbgs() << "    " << SecIndex << ": \"" << *Name
256                << "\" is not an SHF_ALLOC section: "
257                   "No graph section will be created.\n";
258       });
259       continue;
260     }
261 
262     LLVM_DEBUG({
263       dbgs() << "    " << SecIndex << ": Creating section for \"" << *Name
264              << "\"\n";
265     });
266 
267     // Get the section's memory protection flags.
268     sys::Memory::ProtectionFlags Prot;
269     if (Sec.sh_flags & ELF::SHF_EXECINSTR)
270       Prot = static_cast<sys::Memory::ProtectionFlags>(sys::Memory::MF_READ |
271                                                        sys::Memory::MF_EXEC);
272     else
273       Prot = static_cast<sys::Memory::ProtectionFlags>(sys::Memory::MF_READ |
274                                                        sys::Memory::MF_WRITE);
275 
276     // For now we just use this to skip the "undefined" section, probably need
277     // to revist.
278     if (Sec.sh_size == 0)
279       continue;
280 
281     auto &GraphSec = G->createSection(*Name, Prot);
282     if (Sec.sh_type != ELF::SHT_NOBITS) {
283       auto Data = Obj.template getSectionContentsAsArray<char>(Sec);
284       if (!Data)
285         return Data.takeError();
286 
287       G->createContentBlock(GraphSec, *Data, Sec.sh_addr, Sec.sh_addralign, 0);
288     } else
289       G->createZeroFillBlock(GraphSec, Sec.sh_size, Sec.sh_addr,
290                              Sec.sh_addralign, 0);
291 
292     setGraphSection(SecIndex, GraphSec);
293   }
294 
295   return Error::success();
296 }
297 
298 template <typename ELFT> Error ELFLinkGraphBuilder<ELFT>::graphifySymbols() {
299   LLVM_DEBUG(dbgs() << "  Creating graph symbols...\n");
300 
301   // No SYMTAB -- Bail out early.
302   if (!SymTabSec)
303     return Error::success();
304 
305   // Get the section content as a Symbols array.
306   auto Symbols = Obj.symbols(SymTabSec);
307   if (!Symbols)
308     return Symbols.takeError();
309 
310   // Get the string table for this section.
311   auto StringTab = Obj.getStringTableForSymtab(*SymTabSec, Sections);
312   if (!StringTab)
313     return StringTab.takeError();
314 
315   LLVM_DEBUG({
316     StringRef SymTabName;
317 
318     if (auto SymTabNameOrErr = Obj.getSectionName(*SymTabSec, SectionStringTab))
319       SymTabName = *SymTabNameOrErr;
320     else {
321       dbgs() << "Could not get ELF SHT_SYMTAB section name for logging: "
322              << toString(SymTabNameOrErr.takeError()) << "\n";
323       SymTabName = "<SHT_SYMTAB section with invalid name>";
324     }
325 
326     dbgs() << "    Adding symbols from symtab section \"" << SymTabName
327            << "\"\n";
328   });
329 
330   for (ELFSymbolIndex SymIndex = 0; SymIndex != Symbols->size(); ++SymIndex) {
331     auto &Sym = (*Symbols)[SymIndex];
332 
333     // Check symbol type.
334     switch (Sym.getType()) {
335     case ELF::STT_FILE:
336       LLVM_DEBUG({
337         if (auto Name = Sym.getName(*StringTab))
338           dbgs() << "      " << SymIndex << ": Skipping STT_FILE symbol \""
339                  << *Name << "\"\n";
340         else {
341           dbgs() << "Could not get STT_FILE symbol name: "
342                  << toString(Name.takeError()) << "\n";
343           dbgs() << "     " << SymIndex
344                  << ": Skipping STT_FILE symbol with invalid name\n";
345         }
346       });
347       continue;
348       break;
349     }
350 
351     // Get the symbol name.
352     auto Name = Sym.getName(*StringTab);
353     if (!Name)
354       return Name.takeError();
355 
356     // Handle common symbols specially.
357     if (Sym.isCommon()) {
358       Symbol &GSym =
359           G->addCommonSymbol(*Name, Scope::Default, getCommonSection(), 0,
360                              Sym.st_size, Sym.getValue(), false);
361       setGraphSymbol(SymIndex, GSym);
362       continue;
363     }
364 
365     // Map Visibility and Binding to Scope and Linkage:
366     Linkage L;
367     Scope S;
368 
369     if (auto LSOrErr = getSymbolLinkageAndScope(Sym, *Name))
370       std::tie(L, S) = *LSOrErr;
371     else
372       return LSOrErr.takeError();
373 
374     if (Sym.isDefined() &&
375         (Sym.getType() == ELF::STT_NOTYPE || Sym.getType() == ELF::STT_FUNC ||
376          Sym.getType() == ELF::STT_OBJECT ||
377          Sym.getType() == ELF::STT_SECTION)) {
378 
379       // FIXME: Handle extended tables.
380       if (auto *GraphSec = getGraphSection(Sym.st_shndx)) {
381         Block *B = nullptr;
382         {
383           auto Blocks = GraphSec->blocks();
384           assert(Blocks.begin() != Blocks.end() && "No blocks for section");
385           assert(std::next(Blocks.begin()) == Blocks.end() &&
386                  "Multiple blocks for section");
387           B = *Blocks.begin();
388         }
389 
390         LLVM_DEBUG({
391           dbgs() << "      " << SymIndex
392                  << ": Creating defined graph symbol for ELF symbol \"" << *Name
393                  << "\"\n";
394         });
395 
396         if (Sym.getType() == ELF::STT_SECTION)
397           *Name = GraphSec->getName();
398 
399         auto &GSym =
400             G->addDefinedSymbol(*B, Sym.getValue(), *Name, Sym.st_size, L, S,
401                                 Sym.getType() == ELF::STT_FUNC, false);
402         setGraphSymbol(SymIndex, GSym);
403       }
404     } else if (Sym.isUndefined() && Sym.isExternal()) {
405       LLVM_DEBUG({
406         dbgs() << "      " << SymIndex
407                << ": Creating external graph symbol for ELF symbol \"" << *Name
408                << "\"\n";
409       });
410       auto &GSym = G->addExternalSymbol(*Name, Sym.st_size, L);
411       setGraphSymbol(SymIndex, GSym);
412     } else {
413       LLVM_DEBUG({
414         dbgs() << "      " << SymIndex
415                << ": Not creating graph symbol for ELF symbol \"" << *Name
416                << "\" with unrecognized type\n";
417       });
418     }
419   }
420 
421   return Error::success();
422 }
423 
424 } // end namespace jitlink
425 } // end namespace llvm
426 
427 #undef DEBUG_TYPE
428 
429 #endif // LIB_EXECUTIONENGINE_JITLINK_ELFLINKGRAPHBUILDER_H
430