Halide
Elf.h
Go to the documentation of this file.
1 #ifndef HALIDE_ELF_H
2 #define HALIDE_ELF_H
3 
4 #include <algorithm>
5 #include <memory>
6 #include <vector>
7 #include <list>
8 #include <string>
9 #include <iterator>
10 #include <limits>
11 
12 namespace Halide {
13 namespace Internal {
14 namespace Elf {
15 
16 // This ELF parser mostly deserializes the object into a graph
17 // structure in memory. It replaces indices into tables (sections,
18 // symbols, etc.) with a weakly referenced graph of pointers. The
19 // Object datastructure owns all of the objects. This namespace exists
20 // because it is very difficult to use LLVM's object parser to modify
21 // an object (it's fine for parsing only). This was built using
22 // http://www.skyfree.org/linux/references/ELF_Format.pdf as a reference
23 // for the ELF structs and constants.
24 
25 
26 class Object;
27 class Symbol;
28 class Section;
29 class Relocation;
30 
31 // Helpful wrapper to allow range-based for loops.
32 template <typename T>
34  T b, e;
35 public:
36  iterator_range(T b, T e) : b(b), e(e) {}
37 
38  T begin() const { return b; }
39  T end() const { return e; }
40 };
41 
42 /** Describes a symbol */
43 class Symbol {
44 public:
45  enum Binding : uint8_t {
46  STB_LOCAL = 0,
47  STB_GLOBAL = 1,
48  STB_WEAK = 2,
49  STB_LOPROC = 13,
50  STB_HIPROC = 15,
51  };
52 
53  enum Type : uint8_t {
54  STT_NOTYPE = 0,
55  STT_OBJECT = 1,
56  STT_FUNC = 2,
57  STT_SECTION = 3,
58  STT_FILE = 4,
59  STT_LOPROC = 13,
60  STT_HIPROC = 15,
61  };
62 
64  STV_DEFAULT = 0,
65  STV_INTERNAL = 1,
66  STV_HIDDEN = 2,
67  STV_PROTECTED = 3,
68  };
69 
70 private:
71  std::string name;
72  const Section *definition = nullptr;
73  uint64_t offset = 0;
74  uint32_t size = 0;
75  Binding binding = STB_LOCAL;
76  Type type = STT_NOTYPE;
77  Visibility visibility = STV_DEFAULT;
78 
79 public:
80  Symbol() {}
81  Symbol(const std::string &name) : name(name) {}
82 
83  /** Accesses the name of this symbol. */
84  ///@{
85  Symbol &set_name(const std::string &name) {
86  this->name = name;
87  return *this;
88  }
89  const std::string &get_name() const { return name; }
90  ///@}
91 
92  /** Accesses the type of this symbol. */
93  ///@{
94  Symbol &set_type(Type type) {
95  this->type = type;
96  return *this;
97  }
98  Type get_type() const { return type; }
99  ///@}
100 
101  /** Accesses the properties that describe the definition of this symbol. */
102  ///@{
103  Symbol &define(const Section *section, uint64_t offset, uint32_t size) {
104  this->definition = section;
105  this->offset = offset;
106  this->size = size;
107  return *this;
108  }
109  bool is_defined() const { return definition != nullptr; }
110  const Section *get_section() const { return definition; }
111  uint64_t get_offset() const { return offset; }
112  uint32_t get_size() const { return size; }
113  ///@}
114 
115  /** Access the binding and visibility of this symbol. See the ELF
116  * spec for more information about these properties. */
117  ///@{
119  this->binding = binding;
120  return *this;
121  }
123  this->visibility = visibility;
124  return *this;
125  }
126  Binding get_binding() const { return binding; }
127  Visibility get_visibility() const { return visibility; }
128  ///@}
129 };
130 
131 /** Describes a relocation to be applied to an offset of a section in
132  * an Object. */
133 class Relocation {
134  uint32_t type = 0;
135  uint64_t offset = 0;
136  int64_t addend = 0;
137  const Symbol *symbol = nullptr;
138 
139 public:
141  Relocation(uint32_t type, uint64_t offset, int64_t addend, const Symbol *symbol)
142  : type(type), offset(offset), addend(addend), symbol(symbol) {}
143 
144  /** The type of relocation to be applied. The meaning of this
145  * value depends on the machine of the object. */
146  ///@{
148  this->type = type;
149  return *this;
150  }
151  uint32_t get_type() const { return type; }
152  ///@}
153 
154  /** Where to apply the relocation. This is relative to the section
155  * the relocation belongs to. */
156  ///@{
158  this->offset = offset;
159  return *this;
160  }
161  uint64_t get_offset() const { return offset; }
162  ///@}
163 
164  /** The value to replace with the relocation is the address of the symbol plus the addend. */
165  ///@{
166  Relocation &set_symbol(const Symbol *symbol) {
167  this->symbol = symbol;
168  return *this;
169  }
171  this->addend = addend;
172  return *this;
173  }
174  const Symbol *get_symbol() const { return symbol; }
175  int64_t get_addend() const { return addend; }
176  ///@}
177 };
178 
179 /** Describes a section of an object file. */
180 class Section {
181 public:
182  enum Type : uint32_t {
183  SHT_NULL = 0,
184  SHT_PROGBITS = 1,
185  SHT_SYMTAB = 2,
186  SHT_STRTAB = 3,
187  SHT_RELA = 4,
188  SHT_HASH = 5,
189  SHT_DYNAMIC = 6,
190  SHT_NOTE = 7,
191  SHT_NOBITS = 8,
192  SHT_REL = 9,
193  SHT_SHLIB = 10,
194  SHT_DYNSYM = 11,
195  SHT_LOPROC = 0x70000000,
196  SHT_HIPROC = 0x7fffffff,
197  SHT_LOUSER = 0x80000000,
198  SHT_HIUSER = 0xffffffff,
199  };
200 
201  enum Flag : uint32_t {
202  SHF_WRITE = 0x1,
203  SHF_ALLOC = 0x2,
204  SHF_EXECINSTR = 0x4,
205  SHF_MASKPROC = 0xf0000000,
206  };
207 
208  typedef std::vector<Relocation> RelocationList;
209  typedef RelocationList::iterator relocation_iterator;
210  typedef RelocationList::const_iterator const_relocation_iterator;
211 
212  typedef std::vector<char>::iterator contents_iterator;
213  typedef std::vector<char>::const_iterator const_contents_iterator;
214 
215 private:
216  std::string name;
217  Type type = SHT_NULL;
218  uint32_t flags = 0;
219  std::vector<char> contents;
220  // Sections may have a size larger than the contents.
221  uint64_t size = 0;
222  uint64_t alignment = 1;
223  RelocationList relocs;
224 
225 public:
226  Section() {}
227  Section(const std::string &name, Type type) : name(name), type(type) {}
228 
229  Section &set_name(const std::string &name) {
230  this->name = name;
231  return *this;
232  }
233  const std::string &get_name() const { return name; }
234 
236  this->type = type;
237  return *this;
238  }
239  Type get_type() const { return type; }
240 
242  this->flags |= flag;
243  return *this; }
245  this->flags &= ~flag;
246  return *this;
247  }
249  this->flags = flags;
250  return *this;
251  }
252  uint32_t get_flags() const { return flags; }
253  bool is_alloc() const { return (flags & SHF_ALLOC) != 0; }
254  bool is_writable() const { return (flags & SHF_WRITE) != 0; }
255 
256  /** Get or set the size of the section. The size may be larger
257  * than the content. */
258  ///@{
260  this->size = size;
261  return *this;
262  }
263  uint64_t get_size() const { return std::max((uint64_t) size, (uint64_t) contents.size()); }
264  ///@}
265 
267  this->alignment = alignment;
268  return *this;
269  }
270  uint64_t get_alignment() const { return alignment; }
271 
272  Section &set_contents(std::vector<char> contents) {
273  this->contents = std::move(contents);
274  return *this;
275  }
276  template <typename It>
278  this->contents.assign(begin, end);
279  return *this;
280  }
281  template <typename It>
283  this->contents.insert(this->contents.end(), begin, end);
284  return *this;
285  }
286  template <typename It>
288  typedef typename std::iterator_traits<It>::value_type T;
289  uint64_t size_bytes = std::distance(begin, end) * sizeof(T);
290  this->contents.insert(this->contents.begin(), begin, end);
291 
292  // When we add data to the start of the section, we need to fix up
293  // the offsets of the relocations linked to this section.
294  for (Relocation &r : relocations()) {
295  r.set_offset(r.get_offset() + size_bytes);
296  }
297 
298  return *this;
299  }
300  /** Set, append or prepend an object to the contents, assuming T is a
301  * trivially copyable datatype. */
302  template <typename T>
303  Section &set_contents(const std::vector<T> &contents) {
304  this->contents.assign((const char *)contents.data(), (const char *)(contents.data() + contents.size()));
305  return *this;
306  }
307  template <typename T>
308  Section &append_contents(const T& x) {
309  return append_contents((const char *)&x, (const char *)(&x + 1));
310  }
311  template <typename T>
312  Section &prepend_contents(const T& x) {
313  return prepend_contents((const char *)&x, (const char *)(&x + 1));
314  }
315  const std::vector<char> &get_contents() const { return contents; }
316  contents_iterator contents_begin() { return contents.begin(); }
317  contents_iterator contents_end() { return contents.end(); }
318  const_contents_iterator contents_begin() const { return contents.begin(); }
319  const_contents_iterator contents_end() const { return contents.end(); }
320  const char *contents_data() const { return contents.data(); }
321  size_t contents_size() const { return contents.size(); }
322  bool contents_empty() const { return contents.empty(); }
323 
324  Section &set_relocations(std::vector<Relocation> relocs) {
325  this->relocs = std::move(relocs);
326  return *this;
327  }
328  template <typename It>
330  this->relocs.assign(begin, end);
331  return *this;
332  }
333  void add_relocation(const Relocation &reloc) { relocs.push_back(reloc); }
334  relocation_iterator relocations_begin() { return relocs.begin(); }
335  relocation_iterator relocations_end() { return relocs.end(); }
336  iterator_range<relocation_iterator> relocations() { return {relocs.begin(), relocs.end()}; }
337  const_relocation_iterator relocations_begin() const { return relocs.begin(); }
338  const_relocation_iterator relocations_end() const { return relocs.end(); }
339  iterator_range<const_relocation_iterator> relocations() const { return {relocs.begin(), relocs.end()}; }
340  size_t relocations_size() const { return relocs.size(); }
341 };
342 
343 /** Base class for a target architecture to implement the target
344  * specific aspects of linking. */
345 class Linker {
346 public:
347  virtual ~Linker() {}
348 
349  virtual uint16_t get_machine() = 0;
350  virtual uint32_t get_flags() = 0;
351  virtual uint32_t get_version() = 0;
352  virtual void append_dynamic(Section &dynamic) = 0;
353 
354  /** Add or get an entry to the global offset table (GOT) with a
355  * relocation pointing to sym. */
356  virtual uint64_t get_got_entry(Section &got, const Symbol &sym) = 0;
357 
358  /** Check to see if this relocation should go through the PLT. */
359  virtual bool needs_plt_entry(const Relocation &reloc) = 0;
360 
361  /** Add a PLT entry for a symbol sym defined externally. Returns a
362  * symbol representing the PLT entry. */
363  virtual Symbol add_plt_entry(const Symbol &sym, Section &plt, Section &got,
364  const Symbol &got_sym) = 0;
365 
366  /** Perform a relocation. This function may opt to not apply the
367  * relocation, and return a new relocation to be performed at
368  * runtime. This requires that the section to apply the relocation
369  * to is writable at runtime. */
370  virtual Relocation relocate(uint64_t fixup_offset, char *fixup_addr, uint64_t type,
371  const Symbol *sym, uint64_t sym_offset, int64_t addend,
372  Section &got) = 0;
373 
374 };
375 
376 /** Holds all of the relevant sections and symbols for an object. */
377 class Object {
378 public:
379  enum Type : uint16_t {
380  ET_NONE = 0,
381  ET_REL = 1,
382  ET_EXEC = 2,
383  ET_DYN = 3,
384  ET_CORE = 4,
385  ET_LOPROC = 0xff00,
386  ET_HIPROC = 0xffff,
387  };
388 
389  // We use lists for sections and symbols to avoid iterator
390  // invalidation when we modify the containers.
391  typedef std::list<Section> SectionList;
392  typedef typename SectionList::iterator section_iterator;
393  typedef typename SectionList::const_iterator const_section_iterator;
394 
395  typedef std::list<Symbol> SymbolList;
396  typedef typename SymbolList::iterator symbol_iterator;
397  typedef typename SymbolList::const_iterator const_symbol_iterator;
398 
399 private:
400  SectionList secs;
401  SymbolList syms;
402 
403  Type type = ET_NONE;
404  uint16_t machine = 0;
405  uint32_t version = 0;
406  uint64_t entry = 0;
407  uint32_t flags = 0;
408 
409  Object(const Object &);
410  void operator = (const Object &);
411 
412 public:
413  Object() {}
414 
415  Type get_type() const { return type; }
416  uint16_t get_machine() const { return machine; }
417  uint32_t get_version() const { return version; }
418  uint64_t get_entry() const { return entry; }
419  uint32_t get_flags() const { return flags; }
420 
422  this->type = type;
423  return *this;
424  }
426  this->machine = machine;
427  return *this;
428  }
430  this->version = version;
431  return *this;
432  }
434  this->entry = entry;
435  return *this;
436  }
438  this->flags = flags;
439  return *this;
440  }
441 
442  /** Parse an object in memory to an Object. */
443  static std::unique_ptr<Object> parse_object(const char *data, size_t size);
444 
445  /** Write a shared object in memory. */
446  std::vector<char> write_shared_object(Linker *linker, const std::vector<std::string> &depedencies = {},
447  const std::string &soname = "");
448 
449  section_iterator sections_begin() { return secs.begin(); }
450  section_iterator sections_end() { return secs.end(); }
451  iterator_range<section_iterator> sections() { return {secs.begin(), secs.end()}; }
452  const_section_iterator sections_begin() const { return secs.begin(); }
453  const_section_iterator sections_end() const { return secs.end(); }
454  iterator_range<const_section_iterator> sections() const { return {secs.begin(), secs.end()}; }
455  size_t sections_size() const { return secs.size(); }
456  section_iterator find_section(const std::string &name);
457 
458  section_iterator add_section(const std::string &name, Section::Type type);
459  section_iterator add_relocation_section(const Section &for_section);
460  section_iterator erase_section(section_iterator i) { return secs.erase(i); }
461 
462  section_iterator merge_sections(const std::vector<section_iterator> &sections);
463  section_iterator merge_text_sections();
464 
465  symbol_iterator symbols_begin() { return syms.begin(); }
466  symbol_iterator symbols_end() { return syms.end(); }
467  iterator_range<symbol_iterator> symbols() { return {syms.begin(), syms.end()}; }
468  const_symbol_iterator symbols_begin() const { return syms.begin(); }
469  const_symbol_iterator symbols_end() const { return syms.end(); }
470  iterator_range<const_symbol_iterator> symbols() const { return {syms.begin(), syms.end()}; }
471  size_t symbols_size() const { return syms.size(); }
472  symbol_iterator find_symbol(const std::string &name);
473  const_symbol_iterator find_symbol(const std::string &name) const;
474 
475  symbol_iterator add_symbol(const std::string &name);
476 };
477 
478 } // namespace Elf
479 } // namespace Internal
480 } // namespace Halide
481 
482 #endif
Holds all of the relevant sections and symbols for an object.
Definition: Elf.h:377
Symbol & set_name(const std::string &name)
Accesses the name of this symbol.
Definition: Elf.h:85
bool contents_empty() const
Definition: Elf.h:322
Section & set_contents(It begin, It end)
Definition: Elf.h:277
iterator_range< relocation_iterator > relocations()
Definition: Elf.h:336
relocation_iterator relocations_begin()
Definition: Elf.h:334
Object & set_version(uint32_t version)
Definition: Elf.h:429
SectionList::iterator section_iterator
Definition: Elf.h:392
Describes a symbol.
Definition: Elf.h:43
Section & prepend_contents(const T &x)
Definition: Elf.h:312
iterator_range< const_section_iterator > sections() const
Definition: Elf.h:454
std::vector< Relocation > RelocationList
Definition: Elf.h:208
SymbolList::const_iterator const_symbol_iterator
Definition: Elf.h:397
Relocation & set_offset(uint64_t offset)
Where to apply the relocation.
Definition: Elf.h:157
section_iterator sections_end()
Definition: Elf.h:450
uint32_t get_type() const
The type of relocation to be applied.
Definition: Elf.h:151
const char * contents_data() const
Definition: Elf.h:320
Section & set_alignment(uint64_t alignment)
Definition: Elf.h:266
const Section * get_section() const
Accesses the properties that describe the definition of this symbol.
Definition: Elf.h:110
Describes a relocation to be applied to an offset of a section in an Object.
Definition: Elf.h:133
Section & set_relocations(It begin, It end)
Definition: Elf.h:329
bool is_writable() const
Definition: Elf.h:254
Section & prepend_contents(It begin, It end)
Definition: Elf.h:287
uint32_t get_flags() const
Definition: Elf.h:252
Type get_type() const
Definition: Elf.h:239
Symbol & define(const Section *section, uint64_t offset, uint32_t size)
Accesses the properties that describe the definition of this symbol.
Definition: Elf.h:103
section_iterator erase_section(section_iterator i)
Definition: Elf.h:460
std::list< Section > SectionList
Definition: Elf.h:391
section_iterator sections_begin()
Definition: Elf.h:449
Section & set_relocations(std::vector< Relocation > relocs)
Definition: Elf.h:324
Type get_type() const
Definition: Elf.h:415
uint64_t get_entry() const
Definition: Elf.h:418
Section & append_contents(const T &x)
Definition: Elf.h:308
const std::string & get_name() const
Accesses the name of this symbol.
Definition: Elf.h:89
Binding get_binding() const
Access the binding and visibility of this symbol.
Definition: Elf.h:126
Defines methods for manipulating and analyzing boolean expressions.
std::vector< char >::const_iterator const_contents_iterator
Definition: Elf.h:213
const_relocation_iterator relocations_end() const
Definition: Elf.h:338
uint32_t get_size() const
Accesses the properties that describe the definition of this symbol.
Definition: Elf.h:112
const_section_iterator sections_begin() const
Definition: Elf.h:452
unsigned __INT8_TYPE__ uint8_t
uint64_t get_offset() const
Accesses the properties that describe the definition of this symbol.
Definition: Elf.h:111
Describes a section of an object file.
Definition: Elf.h:180
RelocationList::const_iterator const_relocation_iterator
Definition: Elf.h:210
const_symbol_iterator symbols_end() const
Definition: Elf.h:469
const Symbol * get_symbol() const
The value to replace with the relocation is the address of the symbol plus the addend.
Definition: Elf.h:174
const_contents_iterator contents_begin() const
Definition: Elf.h:318
uint16_t get_machine() const
Definition: Elf.h:416
Section & set_contents(std::vector< char > contents)
Definition: Elf.h:272
size_t relocations_size() const
Definition: Elf.h:340
iterator_range< const_relocation_iterator > relocations() const
Definition: Elf.h:339
Relocation & set_type(uint32_t type)
The type of relocation to be applied.
Definition: Elf.h:147
Object & set_entry(uint64_t entry)
Definition: Elf.h:433
uint64_t get_size() const
Get or set the size of the section.
Definition: Elf.h:263
Relocation(uint32_t type, uint64_t offset, int64_t addend, const Symbol *symbol)
Definition: Elf.h:141
const_symbol_iterator symbols_begin() const
Definition: Elf.h:468
const std::vector< char > & get_contents() const
Definition: Elf.h:315
Symbol & set_type(Type type)
Accesses the type of this symbol.
Definition: Elf.h:94
iterator_range< symbol_iterator > symbols()
Definition: Elf.h:467
unsigned __INT32_TYPE__ uint32_t
Base class for a target architecture to implement the target specific aspects of linking.
Definition: Elf.h:345
Symbol & set_binding(Binding binding)
Access the binding and visibility of this symbol.
Definition: Elf.h:118
SymbolList::iterator symbol_iterator
Definition: Elf.h:396
signed __INT64_TYPE__ int64_t
Section & set_name(const std::string &name)
Definition: Elf.h:229
Section & set_size(uint64_t size)
Get or set the size of the section.
Definition: Elf.h:259
std::list< Symbol > SymbolList
Definition: Elf.h:395
Relocation & set_addend(int64_t addend)
The value to replace with the relocation is the address of the symbol plus the addend.
Definition: Elf.h:170
relocation_iterator relocations_end()
Definition: Elf.h:335
uint64_t get_offset() const
Where to apply the relocation.
Definition: Elf.h:161
iterator_range< const_symbol_iterator > symbols() const
Definition: Elf.h:470
Section & set_contents(const std::vector< T > &contents)
Set, append or prepend an object to the contents, assuming T is a trivially copyable datatype...
Definition: Elf.h:303
size_t sections_size() const
Definition: Elf.h:455
SectionList::const_iterator const_section_iterator
Definition: Elf.h:393
symbol_iterator symbols_begin()
Definition: Elf.h:465
Section & set_flag(Flag flag)
Definition: Elf.h:241
Symbol & set_visibility(Visibility visibility)
Access the binding and visibility of this symbol.
Definition: Elf.h:122
RelocationList::iterator relocation_iterator
Definition: Elf.h:209
uint32_t get_flags() const
Definition: Elf.h:419
Object & set_type(Type type)
Definition: Elf.h:421
unsigned __INT16_TYPE__ uint16_t
Object & set_machine(uint16_t machine)
Definition: Elf.h:425
Object & set_flags(uint32_t flags)
Definition: Elf.h:437
Section & set_flags(uint32_t flags)
Definition: Elf.h:248
bool is_defined() const
Accesses the properties that describe the definition of this symbol.
Definition: Elf.h:109
size_t symbols_size() const
Definition: Elf.h:471
const std::string & get_name() const
Definition: Elf.h:233
Section & append_contents(It begin, It end)
Definition: Elf.h:282
symbol_iterator symbols_end()
Definition: Elf.h:466
const_section_iterator sections_end() const
Definition: Elf.h:453
Visibility get_visibility() const
Access the binding and visibility of this symbol.
Definition: Elf.h:127
iterator_range< section_iterator > sections()
Definition: Elf.h:451
Section(const std::string &name, Type type)
Definition: Elf.h:227
uint32_t get_version() const
Definition: Elf.h:417
Relocation & set_symbol(const Symbol *symbol)
The value to replace with the relocation is the address of the symbol plus the addend.
Definition: Elf.h:166
std::vector< char >::iterator contents_iterator
Definition: Elf.h:212
const_contents_iterator contents_end() const
Definition: Elf.h:319
Section & remove_flag(Flag flag)
Definition: Elf.h:244
size_t contents_size() const
Definition: Elf.h:321
Type get_type() const
Accesses the type of this symbol.
Definition: Elf.h:98
unsigned __INT64_TYPE__ uint64_t
Symbol(const std::string &name)
Definition: Elf.h:81
Section & set_type(Type type)
Definition: Elf.h:235
contents_iterator contents_end()
Definition: Elf.h:317
void add_relocation(const Relocation &reloc)
Definition: Elf.h:333
Expr max(FuncRef a, FuncRef b)
Explicit overloads of min and max for FuncRef.
Definition: Func.h:419
contents_iterator contents_begin()
Definition: Elf.h:316
bool is_alloc() const
Definition: Elf.h:253
int64_t get_addend() const
The value to replace with the relocation is the address of the symbol plus the addend.
Definition: Elf.h:175
const_relocation_iterator relocations_begin() const
Definition: Elf.h:337
uint64_t get_alignment() const
Definition: Elf.h:270