#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;

 const addr_t r_offset;
 const 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;
 }
 }

 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)) {
 }

private:
 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);
 }
 }
};

template<typename T>
struct Rela : public Rel<T> {
 typedef typename T::addr_t addr_t;
 typedef typename T::addr_off_t addr_off_t;

 const 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;
 }

 void set_binding_and_type(uint8_t binding, uint8_t type) {
 st_info = make_info(binding, type);
 }

private:
 static uint8_t make_info(uint8_t binding, uint8_t type) {
 return (binding << 4) | (type & 0xf);
 }
};

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_binding_and_type(s->get_binding(), s->get_type());
 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