https://github.com/halide/Halide
Tip revision: f9e4c7878385f43cf88cca23d5bd663233e9e7da authored by Steven Johnson on 27 April 2021, 19:14:54 UTC
Add support for dynamic tensors to hannk (#5942)
Add support for dynamic tensors to hannk (#5942)
Tip revision: f9e4c78
Elf.cpp
#include "Elf.h"
#include "Debug.h"
#include "Error.h"
#include "Util.h"
#include <algorithm>
#include <array>
#include <iomanip>
#include <map>
#include <memory>
namespace Halide {
namespace Internal {
namespace Elf {
namespace {
// http://www.skyfree.org/linux/references/ELF_Format.pdf
enum : uint32_t {
PT_NULL = 0,
PT_LOAD = 1,
PT_DYNAMIC = 2,
PT_INTERP = 3,
PT_NOTE = 4,
PT_SHLIB = 5,
PT_PHDR = 6,
PT_LOPROC = 0x70000000,
PT_HIPROC = 0x7fffffff,
};
enum : uint32_t {
PF_X = 1,
PF_W = 2,
PF_R = 4,
PF_MASKOS = 0x0ff00000,
PF_MASKPROC = 0xf0000000,
};
enum : uint32_t {
DT_NULL = 0,
DT_NEEDED = 1,
DT_PLTRELSZ = 2,
DT_PLTGOT = 3,
DT_HASH = 4,
DT_STRTAB = 5,
DT_SYMTAB = 6,
DT_RELA = 7,
DT_RELASZ = 8,
DT_RELAENT = 9,
DT_STRSZ = 10,
DT_SYMENT = 11,
DT_INIT = 12,
DT_FINI = 13,
DT_SONAME = 14,
DT_RPATH = 15,
DT_SYMBOLIC = 16,
DT_REL = 17,
DT_RELSZ = 18,
DT_RELENT = 19,
DT_PLTREL = 20,
DT_DEBUG = 21,
DT_TEXTREL = 22,
DT_JMPREL = 23,
DT_LOPROC = 0x70000000,
DT_HIPROC = 0x7fffffff,
};
enum : uint32_t {
STN_UNDEF = 0
};
const char elf_magic[] = {0x7f, 'E', 'L', 'F'};
template<int bits>
struct Types;
template<>
struct Types<32> {
typedef uint32_t addr_t;
typedef int32_t addr_off_t;
};
template<typename T>
struct Ehdr {
typedef typename T::addr_t addr_t;
typedef typename T::addr_off_t addr_off_t;
uint8_t e_ident[16];
uint16_t e_type;
uint16_t e_machine;
uint32_t e_version;
addr_t e_entry;
addr_t e_phoff;
addr_t e_shoff;
uint32_t e_flags;
uint16_t e_ehsize;
uint16_t e_phentsize;
uint16_t e_phnum;
uint16_t e_shentsize;
uint16_t e_shnum;
uint16_t e_shstrndx;
};
template<typename T>
struct Phdr {
typedef typename T::addr_t addr_t;
typedef typename T::addr_off_t addr_off_t;
uint32_t p_type;
uint32_t p_offset;
addr_t p_vaddr;
addr_t p_paddr;
uint32_t p_filesz;
uint32_t p_memsz;
uint32_t p_flags;
uint32_t p_align;
};
template<typename T>
struct Shdr {
typedef typename T::addr_t addr_t;
typedef typename T::addr_off_t addr_off_t;
uint32_t sh_name;
uint32_t sh_type;
addr_t sh_flags;
addr_t sh_addr;
addr_t sh_offset;
addr_t sh_size;
uint32_t sh_link;
uint32_t sh_info;
addr_t sh_addralign;
addr_t sh_entsize;
};
template<typename T>
struct Rel {
typedef typename T::addr_t addr_t;
typedef typename T::addr_off_t addr_off_t;
addr_t r_offset;
addr_t r_info;
uint32_t r_type() const {
if (sizeof(addr_t) == 8) {
return r_info & 0xffffffff;
} else {
return r_info & 0xff;
}
}
uint32_t r_sym() const {
if (sizeof(addr_t) == 8) {
return (uint64_t)r_info >> 32;
} else {
return r_info >> 8;
}
}
static addr_t make_info(uint32_t type, uint32_t sym) {
if (sizeof(addr_t) == 8) {
return (uint64_t)type | ((uint64_t)sym << 32);
} else {
return (type & 0xff) | (sym << 8);
}
}
void set_r_type(uint32_t type) {
r_info = make_info(type, r_sym());
}
void set_r_sym(uint32_t sym) {
r_info = make_info(r_type(), sym);
}
Rel(addr_t offset, addr_t info)
: r_offset(offset), r_info(info) {
}
Rel(addr_t offset, uint32_t type, uint32_t sym)
: r_offset(offset), r_info(make_info(type, sym)) {
}
};
template<typename T>
struct Rela : public Rel<T> {
typedef typename T::addr_t addr_t;
typedef typename T::addr_off_t addr_off_t;
addr_off_t r_addend;
Rela(addr_t offset, addr_t info, addr_off_t addend)
: Rel<T>(offset, info), r_addend(addend) {
}
Rela(addr_t offset, uint32_t type, uint32_t sym, addr_off_t addend)
: Rel<T>(offset, type, sym), r_addend(addend) {
}
};
template<typename T>
struct Sym;
template<>
struct Sym<Types<32>> {
uint32_t st_name;
uint32_t st_value;
uint32_t st_size;
uint8_t st_info;
uint8_t st_other;
uint16_t st_shndx;
uint8_t get_binding() const {
return st_info >> 4;
}
uint8_t get_type() const {
return st_info & 0xf;
}
static uint8_t make_info(uint8_t binding, uint8_t type) {
return (binding << 4) | (type & 0xf);
}
void set_binding(uint8_t binding) {
st_info = make_info(binding, get_type());
}
void set_type(uint8_t type) {
st_info = make_info(get_binding(), type);
}
};
template<typename T>
struct Dyn {
typedef typename T::addr_t addr_t;
typedef typename T::addr_off_t addr_off_t;
uint32_t d_tag;
union {
uint32_t d_val;
addr_t d_ptr;
};
};
class StringTable {
// TODO: We could be smarter and find substrings in the existing
// table, not just whole strings. It would probably be fine to just
// put every substring of each new string into the cache.
std::map<std::string, uint32_t> cache;
public:
std::vector<char> table;
StringTable() {
// For our cache to work, we need something in the table to
// start with so index 0 isn't valid (it will be the empty
// string).
table.push_back(0);
}
uint32_t get(const std::string &str) {
uint32_t &index = cache[str];
if (index == 0) {
index = table.size();
table.insert(table.end(), str.begin(), str.end());
table.push_back(0);
}
return index;
}
};
const char *assert_string_valid(const char *name, const char *data, size_t size) {
internal_assert(data <= name && name + strlen(name) + 1 <= data + size);
return name;
}
template<typename T>
void append_object(std::vector<char> &buf, const T &data) {
buf.insert(buf.end(), (const char *)&data, (const char *)(&data + 1));
}
template<typename It>
void append(std::vector<char> &buf, It begin, It end) {
buf.reserve(buf.size() + std::distance(begin, end) * sizeof(*begin));
for (It i = begin; i != end; i++) {
append_object(buf, *i);
}
}
void append_zeros(std::vector<char> &buf, size_t count) {
buf.insert(buf.end(), count, (char)0);
}
void append_padding(std::vector<char> &buf, size_t alignment) {
buf.resize((buf.size() + alignment - 1) & ~(alignment - 1));
}
// Cast one type to another, asserting that the type is in the range
// of the target type.
template<typename T, typename U>
T safe_cast(U x) {
internal_assert(std::numeric_limits<T>::min() <= x && x <= std::numeric_limits<T>::max());
return static_cast<T>(x);
}
// Assign a type from a potentially different type, using safe_cast
// above to validate the assignment.
template<typename T, typename U>
void safe_assign(T &dest, U src) {
dest = safe_cast<T>(src);
}
unsigned long elf_hash(const char *name) {
unsigned long h = 0;
unsigned long g;
for (char c = *name; c; c = *name++) {
h = (h << 4) + c;
g = h & 0xf0000000;
if (g != 0) {
h ^= g >> 24;
}
h &= ~g;
}
return h;
}
template<typename T>
std::unique_ptr<Object> parse_object_internal(const char *data, size_t size) {
Ehdr<T> header = *(const Ehdr<T> *)data;
internal_assert(memcmp(header.e_ident, elf_magic, sizeof(elf_magic)) == 0);
internal_assert(header.e_type == Object::ET_REL || header.e_type == Object::ET_DYN);
std::unique_ptr<Object> obj(new Object());
obj->set_type((Object::Type)header.e_type)
.set_machine(header.e_machine)
.set_version(header.e_version)
.set_entry(header.e_entry)
.set_flags(header.e_flags);
auto get_section_header = [&](int idx) -> const Shdr<T> * {
const char *at = data + header.e_shoff + idx * header.e_shentsize;
internal_assert(data <= at && at + sizeof(Shdr<T>) <= data + size)
<< "Section header out of bounds.\n";
return (const Shdr<T> *)at;
};
// Find the string table.
const char *strings = nullptr;
for (int i = 0; i < header.e_shnum; i++) {
const Shdr<T> *sh = get_section_header(i);
if (sh->sh_type == Section::SHT_STRTAB) {
internal_assert(!strings) << "Found more than one string table.\n";
strings = data + sh->sh_offset;
internal_assert(data <= strings && strings + sh->sh_size <= data + size);
}
}
internal_assert(strings)
<< "String table not found.\n";
// Load the rest of the sections.
std::map<int, Section *> section_map;
for (uint16_t i = 0; i < header.e_shnum; i++) {
const Shdr<T> *sh = get_section_header(i);
if (sh->sh_type != Section::SHT_SYMTAB && sh->sh_type != Section::SHT_STRTAB &&
sh->sh_type != Section::SHT_REL && sh->sh_type != Section::SHT_RELA) {
const char *name = assert_string_valid(&strings[sh->sh_name], data, size);
auto section = obj->add_section(name, (Section::Type)sh->sh_type);
section->set_flags(sh->sh_flags)
.set_size(sh->sh_size)
.set_alignment(sh->sh_addralign);
if (sh->sh_type == Section::SHT_NOBITS) {
// This section doesn't have any data to load.
} else if (sh->sh_type == Section::SHT_NULL) {
} else {
const char *sh_data = data + sh->sh_offset;
internal_assert(data <= sh_data && sh_data + sh->sh_size <= data + size);
section->set_contents(sh_data, sh_data + sh->sh_size);
}
section_map[i] = &*section;
}
}
// Find and load the symbols.
std::map<int, Symbol *> symbol_map;
for (uint16_t i = 0; i < header.e_shnum; i++) {
const Shdr<T> *sh = get_section_header(i);
if (sh->sh_type == Section::SHT_SYMTAB) {
internal_assert(sh->sh_entsize == sizeof(Sym<T>));
// Skip symbol 0, which is a null symbol.
for (uint64_t j = 1; j < sh->sh_size / sizeof(Sym<T>); ++j) {
const char *sym_ptr = data + sh->sh_offset + j * sizeof(Sym<T>);
internal_assert(data <= sym_ptr && sym_ptr + sizeof(Sym<T>) <= data + size);
const Sym<T> &sym = *(const Sym<T> *)sym_ptr;
const char *name = assert_string_valid(&strings[sym.st_name], data, size);
auto symbol = obj->add_symbol(name);
symbol->set_type((Symbol::Type)sym.get_type())
.set_binding((Symbol::Binding)sym.get_binding())
.set_visibility((Symbol::Visibility)sym.st_other);
if (sym.st_shndx != 0) {
symbol->define(section_map[sym.st_shndx], sym.st_value, sym.st_size);
}
symbol_map[j] = &*symbol;
}
}
}
// Load relocations.
for (uint16_t i = 0; i < header.e_shnum; i++) {
const Shdr<T> *sh = get_section_header(i);
internal_assert(sh->sh_type != Section::SHT_REL) << "Section::SHT_REL not supported\n";
if (sh->sh_type == Section::SHT_RELA) {
const char *name = assert_string_valid(&strings[sh->sh_name], data, size);
internal_assert(strncmp(name, ".rela.", 6) == 0);
internal_assert(sh->sh_entsize == sizeof(Rela<T>));
auto to_relocate = obj->find_section(name + 5);
internal_assert(to_relocate != obj->sections_end());
// TODO: This assert should work, but it seems like this
// isn't a reliable test. We rely on the names intead.
//internal_assert(&*to_relocate == section_map[sh->sh_link]);
for (uint64_t i = 0; i < sh->sh_size / sh->sh_entsize; i++) {
const char *rela_ptr = data + sh->sh_offset + i * sh->sh_entsize;
internal_assert(data <= rela_ptr && rela_ptr + sizeof(Rela<T>) <= data + size);
const Rela<T> &rela = *(const Rela<T> *)rela_ptr;
Relocation reloc(rela.r_type(), rela.r_offset, rela.r_addend, symbol_map[rela.r_sym()]);
to_relocate->add_relocation(reloc);
}
}
}
return obj;
}
} // namespace
std::unique_ptr<Object> Object::parse_object(const char *data, size_t size) {
return parse_object_internal<Types<32>>(data, size);
}
Object::symbol_iterator Object::add_symbol(const std::string &name) {
syms.emplace_back(name);
return std::prev(syms.end());
}
Object::section_iterator Object::add_section(const std::string &name, Section::Type type) {
secs.emplace_back(name, type);
return std::prev(secs.end());
}
Object::section_iterator Object::find_section(const std::string &name) {
for (section_iterator i = sections_begin(); i != sections_end(); ++i) {
if (i->get_name() == name) {
return i;
}
}
return sections_end();
}
Object::symbol_iterator Object::find_symbol(const std::string &name) {
for (symbol_iterator i = symbols_begin(); i != symbols_end(); ++i) {
if (i->get_name() == name) {
return i;
}
}
return symbols_end();
}
Object::const_symbol_iterator Object::find_symbol(const std::string &name) const {
for (const_symbol_iterator i = symbols_begin(); i != symbols_end(); ++i) {
if (i->get_name() == name) {
return i;
}
}
return symbols_end();
}
Object::section_iterator Object::merge_sections(const std::vector<section_iterator> &to_merge) {
internal_assert(!to_merge.empty());
section_iterator merged = *to_merge.begin();
std::vector<char> contents = merged->get_contents();
for (auto i = to_merge.begin() + 1; i != to_merge.end(); ++i) {
section_iterator s = *i;
internal_assert(s->get_type() == merged->get_type());
// Make the new text section have an alignment that
// satisfies all sections. This should be gcd, not max,
// but we assume that all of the alignments are powers of
// 2.
uint64_t alignment = std::max(merged->get_alignment(), s->get_alignment());
merged->set_alignment(alignment);
append_padding(contents, alignment);
// The offset of the section in the new merged section.
uint64_t offset = contents.size();
append(contents, s->contents_begin(), s->contents_end());
for (auto j = s->relocations_begin(); j != s->relocations_end(); j++) {
Elf::Relocation reloc = *j;
reloc.set_offset(reloc.get_offset() + offset);
merged->add_relocation(reloc);
}
// Find all of the symbols that were defined in this section, and update them.
for (auto j = symbols_begin(); j != symbols_end(); j++) {
if (j->get_section() == &*s) {
j->define(&*merged, j->get_offset() + offset, j->get_size());
}
}
}
merged->set_contents(contents.begin(), contents.end());
// Remove all of the sections we merged.
for (auto i = to_merge.begin() + 1; i != to_merge.end(); ++i) {
erase_section(*i);
}
return merged;
}
Object::section_iterator Object::merge_text_sections() {
std::vector<section_iterator> text_sections;
for (auto i = sections_begin(); i != sections_end(); i++) {
if (i->get_type() == Section::SHT_PROGBITS && starts_with(i->get_name(), ".text")) {
text_sections.push_back(i);
}
}
section_iterator text = merge_sections(text_sections);
text->set_name(".text");
return text;
}
template<typename T>
std::vector<char> write_shared_object_internal(Object &obj, Linker *linker, const std::vector<std::string> &dependencies,
const std::string &soname) {
typedef typename T::addr_t addr_t;
// The buffer we will be writing to.
std::vector<char> output;
// Declare the things we need to put in the shared object.
Ehdr<T> ehdr;
std::array<Phdr<T>, 3> phdrs;
memset(&ehdr, 0, sizeof(ehdr));
memset(&phdrs[0], 0, sizeof(phdrs));
auto &text_phdr = phdrs[0];
auto &data_phdr = phdrs[1];
auto &dyn_phdr = phdrs[2];
// The text program header starts at the beginning of the object.
text_phdr.p_type = PT_LOAD;
text_phdr.p_flags = PF_X | PF_R;
text_phdr.p_offset = 0;
text_phdr.p_align = 4096;
// We need to build a string table as we go.
StringTable strings;
// And build a list of section headers.
std::vector<Shdr<T>> shdrs;
// Add the null section now.
Shdr<T> sh_null;
memset(&sh_null, 0, sizeof(sh_null));
shdrs.push_back(sh_null);
// We also need a mapping of section objects to section headers.
std::map<const Section *, uint16_t> section_idxs;
// Define a helper function to write a section to the shared
// object, making a section header for it.
auto write_section = [&](const Section &s, uint64_t entsize) {
uint64_t alignment = s.get_alignment();
append_padding(output, alignment);
uint64_t offset = output.size();
debug(2) << "Writing section " << s.get_name() << " at offset " << offset << "\n";
const std::vector<char> &contents = s.get_contents();
append(output, contents.begin(), contents.end());
if (contents.size() < s.get_size()) {
append_zeros(output, s.get_size() - contents.size());
}
append_padding(output, alignment);
Shdr<T> shdr;
shdr.sh_name = strings.get(s.get_name());
safe_assign(shdr.sh_type, s.get_type());
safe_assign(shdr.sh_flags, s.get_flags());
safe_assign(shdr.sh_offset, offset);
safe_assign(shdr.sh_addr, offset);
safe_assign(shdr.sh_size, s.get_size());
safe_assign(shdr.sh_addralign, alignment);
shdr.sh_link = 0;
shdr.sh_info = 0;
safe_assign(shdr.sh_entsize, entsize);
uint16_t shndx = safe_cast<uint16_t>(shdrs.size());
section_idxs[&s] = shndx;
shdrs.push_back(shdr);
return shndx;
};
// And a helper to get the offset we've given a section.
auto get_section_offset = [&](const Section &s) -> uint64_t {
uint16_t idx = section_idxs[&s];
return shdrs[idx].sh_offset;
};
// We need to define the GOT symbol.
uint64_t max_got_size = obj.symbols_size() * 2 * sizeof(addr_t);
Section got(".got", Section::SHT_PROGBITS);
got.set_alignment(4);
got.set_size(max_got_size);
got.set_flags(Section::SHF_ALLOC);
Symbol got_sym("_GLOBAL_OFFSET_TABLE_");
got_sym.define(&got, 0, max_got_size);
got_sym.set_type(Symbol::STT_OBJECT);
got_sym.set_visibility(Symbol::STV_HIDDEN);
Symbol dynamic_sym("_DYNAMIC");
dynamic_sym.define(&got, 0, 4);
dynamic_sym.set_type(Symbol::STT_OBJECT);
got.append_contents((addr_t)0);
// On some platforms, GOT slots 1 and 2 are also reserved.
got.append_contents((addr_t)0);
got.append_contents((addr_t)0);
// Since we can't change the object, start a map of all of the
// symbols that we can mutate. If a symbol from the object is a
// key in this map, we use the mapped value instead.
std::map<const Symbol *, const Symbol *> symbols;
symbols[&dynamic_sym] = &dynamic_sym;
Object::section_iterator iter_dtors = obj.find_section(".dtors");
Symbol dtor_list_sym("__DTOR_LIST__");
if (iter_dtors != obj.sections_end()) {
Section *dtors = &(*iter_dtors);
dtor_list_sym.define(dtors, 0, 0);
dtor_list_sym.set_type(Symbol::STT_NOTYPE);
dtor_list_sym.set_visibility(Symbol::STV_DEFAULT);
dtor_list_sym.set_binding(Symbol::STB_GLOBAL);
}
Object::section_iterator iter_ctors = obj.find_section(".ctors");
Symbol ctor_end_sym("__CTOR_END__");
if (iter_ctors != obj.sections_end()) {
Section *ctors = &(*iter_ctors);
internal_assert(ctors->get_size() == ctors->contents_size())
<< "There should no padding at the end of the .ctors section\n";
ctor_end_sym.define(ctors, ctors->get_size(), 0);
ctor_end_sym.set_type(Symbol::STT_NOTYPE);
ctor_end_sym.set_visibility(Symbol::STV_DEFAULT);
ctor_end_sym.set_binding(Symbol::STB_GLOBAL);
}
for (const Symbol &i : obj.symbols()) {
if (i.get_name() == "_GLOBAL_OFFSET_TABLE_") {
symbols[&i] = &got_sym;
} else if (i.get_name() == "__DTOR_LIST__") {
// It is our job to create this symbol. So, a defined __DTOR_LIST__
// symbol shouldn't be present already.
internal_assert(!i.is_defined()) << "__DTOR_LIST__ already defined\n";
symbols[&i] = &dtor_list_sym;
} else if (i.get_name() == "__CTOR_END__") {
internal_assert(!i.is_defined()) << "__CTOR_END__ already defined\n";
symbols[&i] = &ctor_end_sym;
} else {
symbols[&i] = &i;
}
}
// Get a symbol from a relocation, accounting for the symbol map
// above.
auto get_symbol = [&](const Relocation &r) {
const Symbol *sym = r.get_symbol();
if (!sym) {
return sym;
}
auto i = symbols.find(sym);
if (i != symbols.end()) {
return i->second;
}
return sym;
};
// Check if a relocation needs a PLT entry, which adds some
// additional conditions on top of what the linker implementation
// wants.
auto needs_plt_entry = [&](const Relocation &r) {
const Symbol *s = get_symbol(r);
if (!s || s->is_defined()) {
return false;
}
if (s->get_type() != Symbol::STT_NOTYPE) {
return false;
}
return linker->needs_plt_entry(r);
};
// We need to build the PLT, so it can be positioned along with
// the rest of the text sections.
Section plt(".plt", Section::SHT_PROGBITS);
plt.set_alignment(16);
plt.set_flags(Section::SHF_ALLOC | Section::SHF_EXECINSTR);
std::list<Symbol> plt_symbols;
std::map<const Symbol *, const Symbol *> plt_defs;
// Hack: We're defining the global offset table, so it shouldn't be treated as an external symbol.
plt_defs[&got_sym] = &got_sym;
for (const Section &s : obj.sections()) {
for (const Relocation &r : s.relocations()) {
if (!needs_plt_entry(r)) {
continue;
}
const Symbol *sym = get_symbol(r);
const Symbol *&plt_def = plt_defs[sym];
if (plt_def) {
// We already made a PLT entry for this symbol.
continue;
}
debug(2) << "Defining PLT entry for " << sym->get_name() << "\n";
plt_symbols.push_back(linker->add_plt_entry(*sym, plt, got, got_sym));
plt_def = &plt_symbols.back();
symbols[plt_def] = plt_def;
}
}
// Start placing the sections into the shared object.
// Leave room for the header, and program headers at the beginning of the file.
append_zeros(output, sizeof(ehdr));
append_zeros(output, sizeof(phdrs[0]) * 3);
// We need to perform the relocations. To do that, we need to position the sections
// where they will go in the final shared object.
write_section(plt, 0);
for (const Section &s : obj.sections()) {
if (s.is_alloc() && !s.is_writable()) {
write_section(s, 0);
}
}
append_padding(output, 4096);
text_phdr.p_filesz = output.size() - text_phdr.p_offset;
data_phdr.p_type = PT_LOAD;
data_phdr.p_flags = PF_W | PF_R;
safe_assign(data_phdr.p_offset, output.size());
data_phdr.p_align = 4096;
for (const Section &s : obj.sections()) {
if (s.is_alloc() && s.is_writable()) {
write_section(s, 0);
}
}
// The got will be written again later, after we add entries to it.
write_section(got, 0);
/// Now that we've written the sections that define symbols, we
// can generate the symbol table.
Section symtab(".symtab", Section::SHT_SYMTAB);
symtab.set_alignment(4);
symtab.set_flag(Section::SHF_ALLOC);
std::vector<Sym<T>> syms;
Sym<T> undef_sym;
memset(&undef_sym, 0, sizeof(undef_sym));
syms.push_back(undef_sym);
// Ensure that we output the symbols deterministically, since a map of pointers
// will vary in ordering from run to tun.
std::vector<std::pair<const Symbol *, const Symbol *>> sorted_symbols;
for (const auto &i : symbols) {
sorted_symbols.emplace_back(i);
}
std::sort(sorted_symbols.begin(), sorted_symbols.end(),
[&](const std::pair<const Symbol *, const Symbol *> &lhs, const std::pair<const Symbol *, const Symbol *> &rhs) {
return lhs.first->get_name() < rhs.first->get_name();
});
std::map<const Symbol *, uint16_t> symbol_idxs;
uint64_t local_count = 0;
for (bool is_local : {true, false}) {
for (const auto &i : sorted_symbols) {
const Symbol *s = i.second;
if ((s->get_binding() == Symbol::STB_LOCAL) != is_local) {
continue;
}
uint64_t value = s->get_offset();
// In shared objects, the symbol value is a virtual address,
// not a section offset.
if (s->is_defined()) {
value += get_section_offset(*s->get_section());
}
Sym<T> sym;
safe_assign(sym.st_name, strings.get(s->get_name()));
safe_assign(sym.st_value, value);
safe_assign(sym.st_size, s->get_size());
sym.set_type(s->get_type());
sym.set_binding(s->get_binding());
safe_assign(sym.st_other, s->get_visibility());
sym.st_shndx = section_idxs[s->get_section()];
safe_assign(symbol_idxs[s], syms.size());
syms.push_back(sym);
}
if (is_local) {
local_count = syms.size();
}
}
symtab.set_contents(syms);
uint16_t symtab_idx = write_section(symtab, sizeof(syms[0]));
safe_assign(shdrs[symtab_idx].sh_info, local_count);
// Also write the symbol table as SHT_DYNSYM.
Section dynsym = symtab;
dynsym.set_name(".dynsym");
dynsym.set_type(Section::SHT_DYNSYM);
uint16_t dynsym_idx = write_section(dynsym, sizeof(syms[0]));
shdrs[dynsym_idx].sh_info = local_count;
// We really do need to make a hash table. Make a trivial one with one bucket.
Section hash(".hash", Section::SHT_HASH);
hash.set_alignment(4);
hash.set_flag(Section::SHF_ALLOC);
size_t sym_count = syms.size();
// TODO: Fix non-trivial hash tables so they work with dlsym.
size_t bucket_count = 1;
std::vector<uint32_t> hash_table(bucket_count + sym_count + 2);
safe_assign(hash_table[0], bucket_count);
safe_assign(hash_table[1], sym_count);
uint32_t *buckets = &hash_table[2];
uint32_t *chains = buckets + bucket_count;
for (size_t i = 0; i < sym_count; i++) {
const char *name = &strings.table[syms[i].st_name];
uint32_t hash = elf_hash(name) % bucket_count;
chains[i] = buckets[hash];
safe_assign(buckets[hash], i);
}
hash.set_contents(hash_table);
uint16_t hash_idx = write_section(hash, sizeof(hash_table[0]));
auto do_relocations = [&](const Section &s) {
debug(2) << "Processing relocations for section " << s.get_name() << "\n";
for (const Relocation &r : s.relocations()) {
const Symbol *sym = get_symbol(r);
if (needs_plt_entry(r)) {
// This relocation is a function call, we need to use the PLT entry for this symbol.
auto plt_def = plt_defs.find(sym);
internal_assert(plt_def != plt_defs.end());
debug(2) << "Using PLT entry " << plt_def->second->get_name() << " for symbol " << sym->get_name() << "\n";
sym = plt_def->second;
}
uint64_t fixup_offset = get_section_offset(s) + r.get_offset();
char *fixup_addr = output.data() + fixup_offset;
uint64_t sym_offset = 0;
if (sym && sym->is_defined()) {
sym_offset = get_section_offset(*sym->get_section()) + sym->get_offset();
debug(2) << "Symbol " << sym->get_name() << " is defined at " << sym_offset << "\n";
}
Relocation new_reloc = linker->relocate(fixup_offset, fixup_addr, r.get_type(), sym, sym_offset, r.get_addend(), got);
if (new_reloc.get_type() != 0) {
// The linker wants a dynamic relocation here. This
// section must be writable at runtime.
internal_assert(s.is_writable());
debug(2) << "Linker returned new relocation type " << new_reloc.get_type() << "\n";
new_reloc.set_offset(new_reloc.get_offset() - get_section_offset(got));
got.add_relocation(new_reloc);
}
}
};
// Now that we've generated the symbol table, we can do relocations.
do_relocations(plt);
for (const Section &s : obj.sections()) {
do_relocations(s);
}
// Now we can write the GOT.
internal_assert(got.contents_size() <= max_got_size);
memcpy(output.data() + get_section_offset(got), got.contents_data(), got.contents_size());
auto write_relocation_section = [&](const Section &s) {
uint64_t alignment = 8;
append_padding(output, alignment);
uint64_t offset = output.size();
for (const Relocation &r : s.relocations()) {
uint64_t i_offset = get_section_offset(s) + r.get_offset();
Rela<T> rela(i_offset, r.get_type(), symbol_idxs[get_symbol(r)], r.get_addend());
append_object(output, rela);
}
uint64_t size = output.size() - offset;
append_padding(output, alignment);
Shdr<T> shdr;
safe_assign(shdr.sh_name, strings.get(".rela" + s.get_name()));
shdr.sh_type = Section::SHT_RELA;
shdr.sh_flags = Section::SHF_ALLOC;
safe_assign(shdr.sh_offset, offset);
safe_assign(shdr.sh_addr, offset);
safe_assign(shdr.sh_size, size);
safe_assign(shdr.sh_addralign, alignment);
safe_assign(shdr.sh_link, symtab_idx);
safe_assign(shdr.sh_info, section_idxs[&s]);
shdr.sh_entsize = sizeof(Rela<T>);
uint16_t shndx = safe_cast<uint16_t>(shdrs.size());
shdrs.push_back(shdr);
return shndx;
};
addr_t rela_got_idx = write_relocation_section(got);
// Add some strings we know we'll need in the string table after we write it.
strings.get(soname);
for (const auto &i : dependencies) {
strings.get(i);
}
Section dynamic(".dynamic", Section::SHT_DYNAMIC);
strings.get(dynamic.get_name());
dynamic.set_alignment(4);
dynamic.set_flag(Section::SHF_ALLOC);
Section strtab(".strtab", Section::SHT_STRTAB);
strings.get(strtab.get_name());
strtab.set_flag(Section::SHF_ALLOC);
strtab.set_contents(strings.table);
uint16_t strtab_idx = write_section(strtab, 0);
std::vector<Dyn<T>> dyn;
auto make_dyn = [](int32_t tag, addr_t val) {
Dyn<T> d;
d.d_tag = tag;
d.d_val = val;
return d;
};
for (const auto &i : dependencies) {
dyn.push_back(make_dyn(DT_NEEDED, strings.get(i)));
}
if (!soname.empty()) {
dyn.push_back(make_dyn(DT_SONAME, strings.get(soname)));
}
dyn.push_back(make_dyn(DT_SYMBOLIC, 0));
// This is really required...
dyn.push_back(make_dyn(DT_HASH, get_section_offset(hash)));
// Address of the symbol table.
dyn.push_back(make_dyn(DT_SYMTAB, shdrs[dynsym_idx].sh_offset));
dyn.push_back(make_dyn(DT_SYMENT, shdrs[dynsym_idx].sh_entsize));
// Address of the string table.
dyn.push_back(make_dyn(DT_STRTAB, get_section_offset(strtab)));
dyn.push_back(make_dyn(DT_STRSZ, strtab.get_size()));
// Offset to the GOT.
dyn.push_back(make_dyn(DT_PLTGOT, get_section_offset(got)));
// Relocations associated with the PLT.
addr_t pltrelsz = sizeof(Rela<T>) * plt_symbols.size();
dyn.push_back(make_dyn(DT_JMPREL, shdrs[rela_got_idx].sh_offset));
dyn.push_back(make_dyn(DT_PLTREL, DT_RELA));
dyn.push_back(make_dyn(DT_PLTRELSZ, pltrelsz));
// Other relocations.
dyn.push_back(make_dyn(DT_RELA, shdrs[rela_got_idx].sh_offset + pltrelsz));
dyn.push_back(make_dyn(DT_RELASZ, shdrs[rela_got_idx].sh_size - pltrelsz));
dyn.push_back(make_dyn(DT_RELAENT, sizeof(Rela<T>)));
// DT_FINI
Object::section_iterator iter_fini = obj.find_section(".fini.halide");
if (iter_fini != obj.sections_end()) {
Section &fini = *iter_fini;
dyn.push_back(make_dyn(DT_FINI, get_section_offset(fini)));
}
// DT_INIT
Object::section_iterator iter_init = obj.find_section(".init.halide");
if (iter_init != obj.sections_end()) {
Section &init = *iter_init;
dyn.push_back(make_dyn(DT_INIT, get_section_offset(init)));
}
dynamic.set_contents(dyn);
// Add any target specific stuff.
linker->append_dynamic(dynamic);
// Null terminator.
dynamic.append_contents((uint32_t)DT_NULL);
dynamic.append_contents((addr_t)0);
uint16_t dyn_idx = write_section(dynamic, sizeof(dyn[0]));
dyn_phdr.p_type = PT_DYNAMIC;
dyn_phdr.p_offset = shdrs[dyn_idx].sh_offset;
dyn_phdr.p_flags = PF_R;
dyn_phdr.p_filesz = shdrs[dyn_idx].sh_size;
dyn_phdr.p_memsz = dyn_phdr.p_filesz;
dyn_phdr.p_align = 4;
append_padding(output, 4096);
safe_assign(data_phdr.p_filesz, output.size() - data_phdr.p_offset);
// Setup the section headers.
shdrs[symtab_idx].sh_link = strtab_idx;
shdrs[dynsym_idx].sh_link = strtab_idx;
shdrs[dyn_idx].sh_link = strtab_idx;
shdrs[hash_idx].sh_link = dynsym_idx;
// Write the section header table.
ehdr.e_shoff = output.size();
ehdr.e_shnum = shdrs.size();
ehdr.e_shentsize = sizeof(shdrs[0]);
for (auto &i : shdrs) {
append_object(output, i);
}
// Now go back and write the headers.
memcpy(ehdr.e_ident, elf_magic, 4);
ehdr.e_ident[4] = 1;
ehdr.e_ident[5] = 1;
ehdr.e_ident[6] = 1;
ehdr.e_type = Object::ET_DYN;
ehdr.e_machine = linker->get_machine();
ehdr.e_ehsize = sizeof(ehdr);
ehdr.e_version = linker->get_version();
ehdr.e_entry = obj.get_entry();
ehdr.e_flags = linker->get_flags();
ehdr.e_phoff = sizeof(ehdr);
ehdr.e_phentsize = sizeof(phdrs[0]);
ehdr.e_phnum = phdrs.size();
ehdr.e_shstrndx = strtab_idx;
memcpy(output.data(), &ehdr, sizeof(ehdr));
for (auto &i : phdrs) {
i.p_vaddr = i.p_offset;
i.p_paddr = i.p_offset;
i.p_memsz = i.p_filesz;
}
memcpy(output.data() + ehdr.e_phoff, phdrs.data(), sizeof(phdrs));
return output;
}
std::vector<char> Object::write_shared_object(Linker *linker, const std::vector<std::string> &dependencies,
const std::string &soname) {
return write_shared_object_internal<Types<32>>(*this, linker, dependencies, soname);
}
} // namespace Elf
} // namespace Internal
} // namespace Halide