[NOT FOR SUBMISSION] Fragmented DWARF prototype

[jhenderson]

Summary

This is the linker patch and python script I used to create and link the packages for my fragmented DWARF experiment. See the LLVM Dev 2020 "Fragmented DWARF" for full details.

To use the script, first create a linker reproducer package (optional, but easiest for reproducing the results), extract it, then run the following command:

python fragment_package.py -o <output directory> <input package directory> --bindir <directory containing llvm-dwarfdump and llvm-ar>

This will copy the input package to the output directory, fragmenting all ELF object files (including those in archives) along the way. It will also create a file called <something>.success next to each input file, after it has fragmented it, indicating to the script to skip the file next time, in case the process is aborted. Deleting these files or using --force-split will cause the script to not skip the files.

It's worth noting that at this time, the script does not attempt to patch up DWARF length fields, meaning the output DWARF will not be readable.

The linker changes are necessary to get the output to be what is expected, due to the slightly abused method of using SHF_LINK_ORDER in the script currently. Longer term this should be replaced with the use of SHT_GROUP sections instead. Note that these changes disable SHF_LINK_ORDER's ordering effect.

The linker can be used to link the output of the script as normal. If someone wishes to repeat the experiment I did to gather the figures in the presentation for their own code base, simply run the linker with and without --gc-sections. --mark-live-pc allows turning up the "aggressiveness" of GC-ing by skipping some of the relocations during liveness analysis. It takes a decimal from 0 to 1 (1 == default, normal GC), which represents the fraction of relocations to use per file. It's not an entirely accurate modelling (IIRC, the first relocation in each file is always used, for example), but gives some approximate controls.

lld/Common/Args.cpp

static int64_t getInteger(opt::InputArgList &args, unsigned key,
   if (to_integer(s, v, base))
     return v;
 
   StringRef spelling = args.getArgString(a->getIndex());
   error(spelling + ": number expected, but got '" + a->getValue() + "'");
   return 0;
 }
 
+double lld::args::getDouble(opt::InputArgList &args, unsigned key, int64_t Default) {
+  auto *a = args.getLastArg(key);
+  if (!a)
+    return Default;
+
+  double v;
+  if (to_float(a->getValue(), v))
+    return v;
+
+  StringRef spelling = args.getArgString(a->getIndex());
+  error(spelling + ": float expected, but got '" + a->getValue() + "'");
+  return 0;
+}
+
 int64_t lld::args::getInteger(opt::InputArgList &args, unsigned key,
                               int64_t Default) {
   return ::getInteger(args, key, Default, 10);
 }
 
 int64_t lld::args::getHex(opt::InputArgList &args, unsigned key,
                           int64_t Default) {
   return ::getInteger(args, key, Default, 16);

lld/ELF/Config.h

struct Configuration {
   UnresolvedPolicy unresolvedSymbols;
   Target2Policy target2;
   ARMVFPArgKind armVFPArgs = ARMVFPArgKind::Default;
   BuildIdKind buildId = BuildIdKind::None;
   SeparateSegmentKind zSeparate;
   ELFKind ekind = ELFNoneKind;
   uint16_t emachine = llvm::ELF::EM_NONE;
   llvm::Optional<uint64_t> imageBase;
+  double markLivePc = 1;
+  uint64_t numSeen = 0;
+  uint64_t numMarked = 0;
   uint64_t commonPageSize;
   uint64_t maxPageSize;
   uint64_t mipsGotSize;
   uint64_t zStackSize;
   unsigned ltoPartitions;
   unsigned ltoo;
   unsigned optimize;
   StringRef thinLTOJobs;

lld/ELF/Driver.cpp

if (auto *arg = args.getLastArg(OPT_hash_style)) {
     else if (s == "gnu")
       config->gnuHash = true;
     else if (s == "both")
       config->sysvHash = config->gnuHash = true;
     else
       error("unknown -hash-style: " + s);
   }
 
+  if (args.hasArg(OPT_mark_live_pc))
+    config->markLivePc = args::getDouble(args, OPT_mark_live_pc, 1);
+
   if (args.hasArg(OPT_print_map))
     config->mapFile = "-";
 
   // Page alignment can be disabled by the -n (--nmagic) and -N (--omagic).
   // As PT_GNU_RELRO relies on Paging, do not create it when we have disabled
   // it.
   if (config->nmagic || config->omagic)
     config->zRelro = false;

lld/ELF/InputFiles.cpp

if (!(sec.sh_flags & SHF_LINK_ORDER) || !sec.sh_link)
       continue;
 
     InputSectionBase *linkSec = nullptr;
     if (sec.sh_link < this->sections.size())
       linkSec = this->sections[sec.sh_link];
     if (!linkSec)
       fatal(toString(this) + ": invalid sh_link index: " + Twine(sec.sh_link));
 
+    if (linkSec == &InputSection::discarded) {
+        this->sections[i] = &InputSection::discarded;
+        continue;
+    }
+
     // A SHF_LINK_ORDER section is discarded if its linked-to section is
     // discarded.
     InputSection *isec = cast<InputSection>(this->sections[i]);
     linkSec->dependentSections.push_back(isec);
     if (!isa<InputSection>(linkSec))
       error("a section " + isec->name +
             " with SHF_LINK_ORDER should not refer a non-regular section: " +
             toString(linkSec));

lld/ELF/InputSection.cpp

static int64_t getTlsTpOffset(const Symbol &s) {
   case EM_RISCV:
     return s.getVA(0) + (tls->p_vaddr & (tls->p_align - 1));
 
     // Variant 2.
   case EM_HEXAGON:
   case EM_SPARCV9:
   case EM_386:
   case EM_X86_64:
+    if (!tls)
+        return 0;
     return s.getVA(0) - tls->p_memsz -
            ((-tls->p_vaddr - tls->p_memsz) & (tls->p_align - 1));
   default:
     llvm_unreachable("unhandled Config->EMachine");
   }
 }
 
 uint64_t InputSectionBase::getRelocTargetVA(const InputFile *file, RelType type,

lld/ELF/MarkLive.cpp

static uint64_t getAddend(InputSectionBase &sec,
                           const typename ELFT::Rela &rel) {
   return rel.r_addend;
 }
 
 template <class ELFT>
 template <class RelTy>
 void MarkLive<ELFT>::resolveReloc(InputSectionBase &sec, RelTy &rel,
                                   bool isLSDA) {
+  bool isRegular = isa<InputSection>(sec);
+  if (isRegular) {
+    //lld::outs() << sec.file->getName() << ':' << sec.name << '(' << rel.r_offset << ')';
+    ++config->numSeen;
+    assert(config->numSeen > config->numMarked);
+    if (((double)config->numMarked / double(config->numSeen)) >=
+        config->markLivePc)
+    {
+      //lld::outs() << ": ignored\n";
+      return;
+    }
+    //lld::outs() << ": used\n";
+    ++config->numMarked;
+  }
+
   Symbol &sym = sec.getFile<ELFT>()->getRelocTargetSym(rel);
 
   // If a symbol is referenced in a live section, it is used.
   sym.used = true;
 
   if (auto *d = dyn_cast<Defined>(&sym)) {
     auto *relSec = dyn_cast_or_null<InputSectionBase>(d->section);
     if (!relSec)

 template <class ELFT>
 void MarkLive<ELFT>::enqueue(InputSectionBase *sec, uint64_t offset) {
   // Skip over discarded sections. This in theory shouldn't happen, because
   // the ELF spec doesn't allow a relocation to point to a deduplicated
   // COMDAT section directly. Unfortunately this happens in practice (e.g.
   // .eh_frame) so we need to add a check.
   if (sec == &InputSection::discarded)
     return;
+  //if (!sec->name.startswith(".debug_"))
+  //  lld::outs() << "enqueue: " + sec->file->getName() + ": " +  sec->name + "\n";
 
   // Usually, a whole section is marked as live or dead, but in mergeable
   // (splittable) sections, each piece of data has independent liveness bit.
   // So we explicitly tell it which offset is in use.
   if (auto *ms = dyn_cast<MergeInputSection>(sec))
     ms->getSectionPiece(offset)->live = true;
 
   // Set Sec->Partition to the meet (i.e. the "minimum") of Partition and
if (auto *eh = dyn_cast<EhInputSection>(sec)) {
         continue;
 
       if (eh->areRelocsRela)
         scanEhFrameSection(*eh, eh->template relas<ELFT>());
       else
         scanEhFrameSection(*eh, eh->template rels<ELFT>());
     }
 
+    //if (!sec->name.startswith(".debug_") && sec->file)
+    //  lld::outs() << "section: " + sec->file->getName() + ": " + sec->name + "\n";
+
     if (sec->flags & SHF_LINK_ORDER)
       continue;
 
     if (isReserved(sec) || script->shouldKeep(sec)) {
       enqueue(sec, 0);
     } else if (isValidCIdentifier(sec->name)) {
       cNamedSections[saver.save("__start_" + sec->name)].push_back(sec);
       cNamedSections[saver.save("__stop_" + sec->name)].push_back(sec);
     }
   }
 
   mark();
 }
 
 template <class ELFT> void MarkLive<ELFT>::mark() {
   // Mark all reachable sections.
   while (!queue.empty()) {
     InputSectionBase &sec = *queue.pop_back_val();
+    if (sec.name.startswith(".debug_"))
+      continue;
+
+    //lld::outs() << "marking: " + sec.file->getName() + ": " +  sec.name + "\n";
 
     if (sec.areRelocsRela) {
       for (const typename ELFT::Rela &rel : sec.template relas<ELFT>())
         resolveReloc(sec, rel, false);
     } else {
       for (const typename ELFT::Rel &rel : sec.template rels<ELFT>())
         resolveReloc(sec, rel, false);
     }

lld/ELF/Options.td

 
 defm library: Eq<"library", "Root name of library to use">,
   MetaVarName<"<libName>">;
 
 def m: JoinedOrSeparate<["-"], "m">, HelpText<"Set target emulation">;
 
 defm Map: Eq<"Map", "Print a link map to the specified file">;
 
+defm mark_live_pc : Eq<"mark-live-pc", "Percentage of relocations to use in mark live calculations">, MetaVarName<"<percent>">;
+
 defm merge_exidx_entries: B<"merge-exidx-entries",
     "Enable merging .ARM.exidx entries (default)",
     "Disable merging .ARM.exidx entries">;
 
 defm mmap_output_file: BB<"mmap-output-file",
     "Mmap the output file for writing (default)",
     "Do not mmap the output file for writing">;
 

lld/ELF/Writer.cpp

StringRef elf::getOutputSectionName(const InputSectionBase *s) {
   // A BssSection created for a common symbol is identified as "COMMON" in
   // linker scripts. It should go to .bss section.
   if (s->name == "COMMON")
     return ".bss";
 
   if (script->hasSectionsCommand)
     return s->name;
 
+  if ((s->flags & SHF_ALLOC) == 0)
+      return s->name;
+
   // When no SECTIONS is specified, emulate GNU ld's internal linker scripts
   // by grouping sections with certain prefixes.
 
   // GNU ld places text sections with prefix ".text.hot.", ".text.unknown.",
   // ".text.unlikely.", ".text.startup." or ".text.exit." before others.
   // We provide an option -z keep-text-section-prefix to group such sections
   // into separate output sections. This is more flexible. See also
   // sortISDBySectionOrder().
for (OutputSection *sec : outputSections) {
     if (!(sec->flags & SHF_LINK_ORDER))
       continue;
 
     // The ARM.exidx section use SHF_LINK_ORDER, but we have consolidated
     // this processing inside the ARMExidxsyntheticsection::finalizeContents().
     if (!config->relocatable && config->emachine == EM_ARM &&
         sec->type == SHT_ARM_EXIDX)
       continue;
-
-    // Link order may be distributed across several InputSectionDescriptions.
-    // Sorting is performed separately.
-    std::vector<InputSection **> scriptSections;
-    std::vector<InputSection *> sections;
-    for (BaseCommand *base : sec->sectionCommands) {
-      auto *isd = dyn_cast<InputSectionDescription>(base);
-      if (!isd)
-        continue;
-      bool hasLinkOrder = false;
-      scriptSections.clear();
-      sections.clear();
-      for (InputSection *&isec : isd->sections) {
-        if (isec->flags & SHF_LINK_ORDER) {
-          InputSection *link = isec->getLinkOrderDep();
-          if (link && !link->getParent())
-            error(toString(isec) + ": sh_link points to discarded section " +
-                  toString(link));
-          hasLinkOrder = true;
-        }
-        scriptSections.push_back(&isec);
-        sections.push_back(isec);
-      }
-      if (hasLinkOrder && errorCount() == 0) {
-        llvm::stable_sort(sections, compareByFilePosition);
-        for (int i = 0, n = sections.size(); i != n; ++i)
-          *scriptSections[i] = sections[i];
-      }
-    }
   }
 }
 
 static void finalizeSynthetic(SyntheticSection *sec) {
   if (sec && sec->isNeeded() && sec->getParent())
     sec->finalizeContents();
 }
 

lld/include/lld/Common/Args.h

 }
 } // namespace llvm
 
 namespace lld {
 namespace args {
 
 llvm::CodeGenOpt::Level getCGOptLevel(int optLevelLTO);
 
 int64_t getInteger(llvm::opt::InputArgList &args, unsigned key,
+                   int64_t Default, int base);
+int64_t getInteger(llvm::opt::InputArgList &args, unsigned key,
                    int64_t Default);
-
+double getDouble(llvm::opt::InputArgList &args, unsigned key, int64_t Default);
 int64_t getHex(llvm::opt::InputArgList &args, unsigned key, int64_t Default);
-
 std::vector<StringRef> getStrings(llvm::opt::InputArgList &args, int id);
 
 uint64_t getZOptionValue(llvm::opt::InputArgList &args, int id, StringRef key,
                          uint64_t Default);
 
 std::vector<StringRef> getLines(MemoryBufferRef mb);
 
 StringRef getFilenameWithoutExe(StringRef path);
 
 } // namespace args
 } // namespace lld
 
 #endif

llvm/utils/fragment_package.py

+from __future__ import print_function
+import argparse
+import json
+import os
+import re
+import shutil
+import struct
+import subprocess
+import tempfile
+import time
+
+cached_extensions = ['.success']
+
+def parse_commandline():
+    parser = argparse.ArgumentParser()
+    parser.add_argument('--force-split', help='redo split action', action='store_true')
+    parser.add_argument('--force-archive-split', help='redo split action for archives only', action='store_true')
+    parser.add_argument('--outdir', '-o', help='root directory of output package', default='outdir')
+    parser.add_argument('--bin', help='directory containing required tools', default='.')
+    parser.add_argument('--tmpdir', help='directory to use as a temporary directory for editing')
+    parser.add_argument('input', help='directory or file to copy and fragment')
+    return parser.parse_args()
+
+def find_files(search_path):
+    if os.path.isfile(search_path):
+        return [search_path]
+    objs = []
+    for root, _, files in os.walk(search_path):
+        for f in files:
+            if not any([f.endswith(c) for c in cached_extensions]):
+                objs.append(os.path.join(root, f))
+    return objs
+
+NORMAL_KIND = 0
+ELF_KIND = 1
+ARCHIVE_KIND = 2
+
+def get_file_kind(path):
+    with open(path, 'rb') as fp:
+        magic = fp.read(8)
+        if magic.startswith(b'\x7fELF'):
+            return ELF_KIND
+        elif magic == b'!<arch>\n':
+            return ARCHIVE_KIND
+        # TODO: thin archives?
+    return NORMAL_KIND
+
+def copy_to_dir(src, root, outdir):
+    """
+        Copy src to outdir, maintaining the directory structure relative to root.
+        Create any subdirectories required.
+    """
+    dest = os.path.join(outdir, os.path.relpath(os.path.dirname(src), root))
+    if not os.path.exists(dest):
+        os.makedirs(dest)
+    shutil.copy2(src, dest)
+    return os.path.join(dest, os.path.basename(src))
+
+def extract_members(archive, bindir):
+    """
+        Extract all members from archive using the tools located in bindir.
+        Return the list of members.
+        The archive must be the only file in its directory.
+    """
+    directory = os.path.dirname(archive)
+    assert len(os.listdir(directory)) == 1, "should only have one archive in directory"
+    cwd = os.getcwd()
+    os.chdir(directory)
+    llvm_ar = os.path.join(bindir, 'llvm-ar.exe')
+    archive_name = os.path.basename(archive)
+    subprocess.check_call([llvm_ar, 'x', archive_name])
+    stdout = subprocess.check_output([llvm_ar, 't', archive_name]).decode('utf-8')
+    members = stdout.split('\n')
+    os.chdir(cwd)
+    return [os.path.join(directory, member.strip()) for member in members if len(member.strip()) > 0]
+
+def replace_archive(members, archive, tmpdir, bindir):
+    """
+        Delete and recreate archive, with the specified members, using the tools
+        located at bindir.
+    """
+    os.remove(archive)
+    response_path = os.path.join(tmpdir, 'response.rsp')
+    assert not os.path.exists(response_path)
+    with open(response_path, 'w') as response:
+        response.writelines(['"' + m + '"' + '\n' for m in members])
+    subprocess.check_call([os.path.join(bindir, 'llvm-ar.exe'), 'rc', archive, '@' + response_path])
+
+NONE = 0
+DEBUG_INFO = 1
+DEBUG_RANGES = 2
+DEBUG_ARANGES = 3
+DEBUG_LOC = 4
+DEBUG_LINE = 5
+
+tag_regex = re.compile(b'(0x[0-9a-f]+):( +)(DW_TAG_variable|DW_TAG_subprogram)')
+tag_addr_regex = re.compile(b' +(DW_AT_low_pc|DW_AT_ranges|(DW_AT_location.*\(DW_OP_addr)).*')
+prologue_length_regex = re.compile(b' +prologue_length: (0x[0-9a-f]+)')
+end_sequence_regex = re.compile(b'(0x[0-9a-f]+): 00 DW_LNE_end_sequence')
+loc_offset_regex = re.compile(b'(0x[0-9a-f]+):')
+ranges_end_regex = re.compile(b'[0-9a-f]+ <End of list>')
+
+def analyse_dwarfdump(path, original, bindir):
+    dwarfdump = os.path.join(bindir, 'llvm-dwarfdump')
+    stdout = subprocess.check_output([dwarfdump, '--debug-info', '--debug-line', '--debug-loc', '--debug-aranges', '--verbose', path])
+    info_var_offsets = []
+    info_func_offsets = []
+    location = NONE
+    in_variable = False
+    in_function = False
+    has_address = False
+    ranges_offsets = []
+    range_starts = []
+    line_offsets = []
+    aranges_offsets = []
+    loc_offsets = []
+
+    for line in stdout.splitlines():
+        if line == b'.debug_info contents:':
+            location = DEBUG_INFO
+            continue
+        if line == b'.debug_ranges contents:':
+            location = DEBUG_RANGES
+            new_list = True
+            ranges_offset = 0
+            continue
+        if line == b'.debug_loc contents:':
+            location = DEBUG_LOC
+            continue
+        if line == b'.debug_aranges contents:':
+            location = DEBUG_ARANGES
+            aranges_offset = 0
+            continue
+        if line == b'.debug_line contents:':
+            location = DEBUG_LINE
+            continue
+
+        # Split to create sections containing sequences of areas covered by
+        # variable/subprogram tags and those not. Nested variables are
+        # considered part of the subprogram. Variables and subprograms without
+        # a DW_AT_low_pc or DW_AT_ranges are also ignored, since these can't
+        # represent any actual addresses.
+        if location == DEBUG_INFO:
+            if in_variable or in_function:
+                if not has_address:
+                    match = tag_addr_regex.match(line)
+                    if match:
+                        has_address = True
+                match = re.match(b'(0x[0-9a-f]+):' + b' ' * indent + b'(DW_TAG|NULL)', line)
+                if not match:
+                    continue
+                end = int(match.group(1), 16)
+                if in_variable:
+                    in_variable = False
+                    if has_address:
+                        info_var_offsets.append((offset, end))
+                else:
+                    in_function = False
+                    if has_address:
+                        info_func_offsets.append((offset, end))
+                has_address = False
+
+            if not in_variable and not in_function:
+                match = tag_regex.match(line)
+                if not match:
+                    continue
+                offset = int(match.group(1), 16)
+                indent = len(match.group(2))
+                if match.group(3) == b'DW_TAG_variable':
+                    in_variable = True
+                else:
+                    in_function = True
+
+        # For now, split each .debug_ranges entry into its own one.
+        # Additionally, add an empty section at the start of each
+        # sequence, to hold the symbol.
+        # TODO: combine consecutive range entries into single section, including
+        # any terminator if all entries in a list are for the same symbol.
+        if location == DEBUG_RANGES:
+            if len(line) == 0:
+                location = NONE
+                continue
+            if new_list:
+                range_starts.append(ranges_offsets)
+            if new_list and len(ranges_offsets) != 0:
+                ranges_offsets.append(ranges_offset)
+            new_list = False
+            ranges_offsets.append(ranges_offset)
+            ranges_offset += 0x10
+            if ranges_end_regex.match(line):
+                new_list = True
+
+        # Split into a header section, followed by one per entry, and a trailing
+        # section containing terminator.
+        if location == DEBUG_ARANGES:
+            if len(line) == 0:
+                location = NONE
+                continue
+            aranges_offset += 0x10
+            aranges_offsets.append(aranges_offset) # Header and entries are all same size.
+
+        # Split each location sequence into its own section.
+        if location == DEBUG_LOC:
+            match = loc_offset_regex.match(line)
+            if not match:
+                continue
+            offset = int(match.group(1), 16)
+            # .debug_loc doesn't need a distinct header or section start symbol
+            # so don't add offset 0.
+            if offset != 0:
+                loc_offsets.append(offset)
+
+        # Split to create a header section, a section per sequence, and a trailing
+        # empty section (used for length marker).
+        if location == DEBUG_LINE:
+            if len(line_offsets) == 0:
+                match = prologue_length_regex.match(line)
+                if not match:
+                    continue
+                line_offsets.append(int(match.group(1), 16) + 10) # Assume V4, DWARF32.
+            else:
+                match = end_sequence_regex.match(line)
+                if not match:
+                    continue
+                line_offsets.append(int(match.group(1), 16) + 3) # 00 + length + opcode.
+
+    return (info_func_offsets, info_var_offsets, line_offsets, aranges_offsets, loc_offsets, ranges_offsets, range_starts)
+
+byte = struct.Struct('<B')
+half = struct.Struct('<H')
+word = struct.Struct('<I')
+quad = struct.Struct('<Q')
+
+class StringTable(object):
+    def __init__(self, elf, offset):
+        self._elf = elf
+        self._offset = offset
+        self._strings = {}
+
+    def get_string(self, offset):
+        if offset in self._strings:
+            return self._strings[offset]
+        self._elf.seek(self._offset + offset)
+        chars = []
+        char = self._elf.read(1)
+        while char != b'\x00':
+            chars.append(char)
+            char = self._elf.read(1)
+        result = b''.join(chars)
+        self._strings[offset] = result
+        return result
+
+class Symbol(object):
+    def __init__(self, st_type, st_shndx):
+        self.type = st_type
+        self.shndx = st_shndx
+
+class SymbolTable(object):
+    def __init__(self, elf, offset, strtab):
+       self._elf = elf
+       self._offset = offset
+       self._strtab = strtab
+       self.symtab_shndx = None
+
+    def get_symbol(self, index):
+        self._elf.seek(self._offset + index * 24 + 4)
+        st_info = byte.unpack(self._elf.read(1))[0]
+        self._elf.seek(self._offset + index * 24 + 6)
+        st_shndx = half.unpack(self._elf.read(2))[0]
+        if st_shndx == SHN_XINDEX:
+            st_shndx = self.symtab_shndx.get_index(index)
+        return Symbol(st_info & 0xf, st_shndx)
+
+class SymtabShndxTable(object):
+    def __init__(self, elf, offset):
+        self._elf = elf
+        self._offset = offset
+
+    def get_index(self, sym_index):
+        self._elf.seek(self._offset + sym_index * 4)
+        return word.unpack(self._elf.read(4))[0]
+
+class SectionHeaderTable(object):
+    def __init__(self, shdr_table, shnum):
+        self._shdrs = []
+        for i in range(0, shnum):
+            self._shdrs.append(shdr_table[i * 64 : (i + 1) * 64])
+
+    def get(self, index):
+        return self._shdrs[index]
+
+    def update(self, index, shdr):
+        self._shdrs[index] = shdr
+
+    def add(self, shdr):
+        self._shdrs.append(shdr)
+
+    def size(self):
+        return len(self._shdrs)
+
+    def write(self, elf, offset):
+        # Update ELF header and null shdr (if needed).
+        elf.seek(40)
+        elf.write(quad.pack(offset))
+        elf.seek(60)
+        shnum = len(self._shdrs)
+        if shnum < 0xff00:
+            elf.write(half.pack(shnum))
+        else:
+            elf.write(half.pack(0))
+            null_shdr = self.get(0)
+            self.update(0, null_shdr[:32] + quad.pack(shnum) + null_shdr[40:])
+
+        # Write table.
+        elf.seek(offset)
+        for shdr in self._shdrs:
+            elf.write(shdr)
+
+def make_debug_info_split_points(func_offsets, var_offsets):
+    offsets = []
+    for start, end in func_offsets:
+        offsets.extend([start, end])
+    for start, end in var_offsets:
+        offsets.extend([start, end])
+    offsets = sorted(set(offsets))
+    return offsets
+
+def split_shdr(elf, shdr_table, shdr, index, split_points, use_original=True, info=None, links=None, link_order=False):
+    initial_flags = quad.unpack(shdr[8:16])[0]
+    initial_offset = quad.unpack(shdr[24:32])[0]
+    total_size = quad.unpack(shdr[32:40])[0]
+    split_points.append(total_size)
+    start = initial_offset
+    if use_original:
+        where = index
+        output_secs = []
+    else:
+        where = shdr_table.size()
+        # Replace the original with a null entry. At the time of writing, LLD doesn't
+        # support relocation sections before their targets in the shdr table.
+        shdr_table.update(index, b'\0' * 64)
+        output_secs = [(0, 0, index)]
+    i = 0
+    assert info is None or len(split_points) == len(info)
+    assert links is None or len(split_points) == len(links)
+    assert links is not None or not link_order
+    for end in split_points:
+        output_secs.append((start - initial_offset, end, where))
+        end += initial_offset
+
+        # Only need to change offset, size, info, link, flags
+        shdr_to_update = shdr[:8]
+        if link_order and links[i] is not None:
+            shdr_to_update += quad.pack(initial_flags | SHF_LINK_ORDER)
+        else:
+            shdr_to_update += quad.pack(initial_flags)
+
+        shdr_to_update += shdr[16:24]
+        offset = quad.pack(start)
+        size = quad.pack(end - start)
+        shdr_to_update += offset + size
+
+        if links is not None:
+            sh_link = links[i]
+            if sh_link is None:
+                sh_link = 0
+            shdr_to_update += word.pack(sh_link)
+        else:
+            shdr_to_update += shdr[40:44]
+        if info is not None:
+            shdr_to_update += word.pack(info[i])
+        else:
+            shdr_to_update += shdr[44:48]
+        shdr_to_update += shdr[48:]
+
+        if where == index:
+            shdr_table.update(where, shdr_to_update)
+        else:
+            shdr_table.add(shdr_to_update)
+
+        start = end
+        where = shdr_table.size()
+        i += 1
+
+    return output_secs
+
+STT_SECTION = 3
+SHF_ALLOC = 2
+SHF_MERGE = 0x10
+SHF_LINK_ORDER = 0x80
+
+def set_link_order(shdr_table, shndx, link):
+    # Patched section should have SHF_LINK_ORDER and sh_link set.
+    shdr = shdr_table.get(shndx)
+    sh_flags = quad.unpack(shdr[8:16])[0]
+    sh_flags |= SHF_LINK_ORDER
+    shdr_table.update(shndx, shdr[:8] + quad.pack(sh_flags) + shdr[16:40] + word.pack(link) + shdr[44:])
+
+def get_reloc_data(elf, reloc_offset):
+    elf.seek(reloc_offset)
+    r_offset = quad.unpack(elf.read(8))[0]
+    r_sym = quad.unpack(elf.read(8))[0] >> 32
+    return r_offset, r_sym
+
+def set_reloc_offset(elf, reloc_offset, new_offset):
+    elf.seek(reloc_offset)
+    elf.write(quad.pack(new_offset))
+
+def split_relocs(elf, shdr_table, symtab, shdr, index, debug_sec_shdrs):
+    data_offset = quad.unpack(shdr[24:32])[0]
+    reloc_count = quad.unpack(shdr[32:40])[0] // 0x18
+    elf.seek(data_offset)
+    patched_shdr_i = 0
+    split_points = []
+    info = [] # The sh_info values to use.
+    symbol_shndxs = set()
+    assert debug_sec_shdrs[0][0] == 0
+    for i in range(0, reloc_count):
+        reloc_offset = data_offset + i * 0x18
+        r_offset, sym_index = get_reloc_data(elf, reloc_offset)
+
+        # The relocation could be patching either the current section, or a
+        # later one. Find the right one.
+        # If the relocation's r_offset is greater than the section's end, it is
+        # not the right section.
+        previous_shdr_index = debug_sec_shdrs[patched_shdr_i][2]
+        # Skip empty sections - the relocation can't be patching those.
+        while debug_sec_shdrs[patched_shdr_i][0] == debug_sec_shdrs[patched_shdr_i][1]:
+            patched_shdr_i += 1
+        while r_offset >= debug_sec_shdrs[patched_shdr_i][1]:
+            if debug_sec_shdrs[patched_shdr_i][0] == debug_sec_shdrs[patched_shdr_i][1]:
+                patched_shdr_i += 1
+                continue
+            if len(symbol_shndxs) == 1:
+                shndx = symbol_shndxs.pop()
+                if shndx != -1:
+                    assert shndx != 0, 'invalid section index for SHF_LINK_ORDER'
+                    set_link_order(shdr_table, previous_shdr_index, shndx)
+            symbol_shndxs = set()
+            patched_shdr_i += 1
+        assert r_offset >= debug_sec_shdrs[patched_shdr_i][0]
+        patched_shdr_index = debug_sec_shdrs[patched_shdr_i][2]
+
+        symbol = symtab.get_symbol(sym_index)
+        patched_shdr = shdr_table.get(symbol.shndx)
+        sh_flags = quad.unpack(patched_shdr[8:16])[0]
+        if symbol.type != STT_SECTION:
+            # Don't allow SHF_LINK_ORDER where the section refers to
+            # an undefined symbol.
+            if symbol.shndx == 0:
+                symbol_shndxs.add(-1)
+            else:
+                symbol_shndxs.add(symbol.shndx)
+        else:
+            if sh_flags & SHF_ALLOC:
+                # LLD doesn't like SHF_LINK_ORDER to mergeable sections.
+                if sh_flags & SHF_MERGE:
+                    symbol_shndxs.add(-1)
+                else:
+                    assert symbol.shndx != 0, "sym_index = {}".format(sym_index)
+                    symbol_shndxs.add(symbol.shndx)
+
+        # Update the target offset to be relative to the new target section.
+        r_offset -= debug_sec_shdrs[patched_shdr_i][0]
+        elf.seek(reloc_offset)
+        elf.write(quad.pack(r_offset))
+
+        # We're in the right section now. If it was the same as the previous
+        # relocation, just continue. Otherwise, create the next split point.
+        if len(info) > 0 and info[-1] == patched_shdr_index:
+            continue
+        # No need to add a specific split point for the first relocation.
+        if i != 0:
+            split_points.append(i * 0x18)
+        info.append(patched_shdr_index)
+
+    # If the last relocation patches the last section, the link order won't have
+    # been set yet.
+    if len(symbol_shndxs) == 1:
+        # LLD doesn't like SHF_LINK_ORDER to mergeable sections.
+        shndx = symbol_shndxs.pop()
+        if shndx != -1:
+            set_link_order(shdr_table, patched_shdr_index, shndx)
+
+    return len(split_shdr(elf, shdr_table, shdr, index, split_points, False, info)) - 1
+
+def split_debug_ranges(elf, shdr_table, symtab, ranges_shdr, ranges_shndx, rela_shdr, rela_shndx):
+    # TODO: Add symbols for section starts.
+    # This code assumes that the relocations are in offset order.
+    # Each entry will either be a pair of relocations to the same symbol, or a
+    # terminating entry with no relocations.
+    # If a range list consists solely of relocations to the same symbol, assume
+    # the terminator and whole range can be discarded with that symbol.
+    # If not, merge adjacent entries referencing the same symbol, and leave the
+    # terminator alone.
+    sh_offset = quad.unpack(ranges_shdr[24:32])[0]
+    rela_shoffset = quad.unpack(rela_shdr[24:32])[0]
+    sh_size = quad.unpack(ranges_shdr[32:40])[0]
+    reloc_count = quad.unpack(rela_shdr[32:40])[0] // 0x18
+    reloc_index = 0
+    if reloc_index != reloc_count:
+        r_offset, r_sym = get_reloc_data(elf, rela_shoffset + reloc_index * 0x18)
+    else:
+        r_offset = None
+        r_sym = None
+    ranges_split_points = []
+    reloc_split_points = []
+    list_start = 0
+    list_reloc_start = reloc_index
+    list_syms = []
+    for sh_offset in range(0, sh_size, 0x10):
+        if r_offset is None or r_offset >= sh_offset + 0x10:
+            # Terminator entry.
+            if len(list_syms) == 0:
+                # list_syms of 0 means just a terminator is in the list, so there
+                # are no relocations for the entire list.
+                ranges_split_points.append((sh_offset + 0x10, None))
+            elif len(list_syms) == 1:
+                ranges_split_points.append((sh_offset + 0x10, list_syms[0]))
+                reloc_split_points.append(reloc_index * 0x18)
+            else:
+                assert len(list_syms) == (sh_offset - list_start) // 0x10
+                ranges_split_points.extend(zip(range(list_start + 0x10, sh_offset + 1, 0x10), list_syms))
+                ranges_split_points.append((sh_offset + 0x10, None))
+                reloc_split_points.extend(range(list_reloc_start * 0x18 + 0x30, reloc_index * 0x18 + 1, 0x30))
+            list_start = sh_offset + 0x10
+            list_reloc_start = reloc_index
+            list_syms = []
+            continue
+        # range entry.
+        if r_offset != sh_offset:
+            assert False, "unexpected relocation r_offset at offset {}".format(reloc_index * 0x18)
+        else:
+            reloc_index += 1
+            assert reloc_index != reloc_count, "incorrect number of relocations"
+            r_offset2, r_sym2 = get_reloc_data(elf, rela_shoffset + reloc_index * 0x18)
+            assert r_offset2 == sh_offset + 8, "next reloc at offset {} does not patch expected location".format(reloc_index * 0x18)
+            assert r_sym == r_sym2, "range entry at offset {} does not have common symbol".format(sh_offset)
+            symbol_shndx = symtab.get_symbol(r_sym).shndx
+            if len(list_syms) == 0:
+                list_syms = [symbol_shndx]
+            elif len(list_syms) == 1 and list_syms[0] != symbol_shndx:
+                list_syms = [list_syms[0]] * ((sh_offset - list_start) // 0x10) + [symbol_shndx]
+            elif len(list_syms) > 1:
+                list_syms.append(symbol_shndx)
+            reloc_index += 1
+            if reloc_index != reloc_count:
+                r_offset, r_sym = get_reloc_data(elf, rela_shoffset + reloc_index * 0x18)
+            else:
+                r_offset = None
+                r_sym = None
+
+    split_points, links = ([point for point, link in ranges_split_points], [link for point, link in ranges_split_points])
+    del split_points[-1]
+    new_ranges_secs = (split_shdr(elf, shdr_table, ranges_shdr, ranges_shndx, split_points, links=links, link_order=True))
+    infos = [new_ranges_secs[i][2] for i in range(0, len(links)) if links[i] is not None]
+
+    if len(reloc_split_points) > 0:
+        new_offset = 0
+        reloc_split_i = 0
+        for reloc_offset in range(rela_shoffset, reloc_split_points[-1] + rela_shoffset, 0x18):
+            if len(reloc_split_points) > reloc_split_i and reloc_offset >= (reloc_split_points[reloc_split_i] + rela_shoffset):
+                reloc_split_i += 1
+                new_offset = 0
+            set_reloc_offset(elf, reloc_offset, new_offset)
+            new_offset += 8
+
+    del reloc_split_points[-1]
+    reloc_sec_count = len(split_shdr(elf, shdr_table, rela_shdr, rela_shndx, reloc_split_points, info=infos))
+    return len(new_ranges_secs) + reloc_sec_count
+
+SHT_PROGBITS = 1
+SHT_SYMTAB = 2
+SHT_RELA = 4
+SHT_SYMTAB_SHNDX = 18
+
+SHN_XINDEX = 0xffff
+
+def fragment(path, original, bindir):
+    start_time = time.time()
+
+    (func_offsets, var_offsets, line_offsets, aranges_offsets, loc_offsets, ranges_offsets, range_start_offsets) = analyse_dwarfdump(path, original, bindir)
+    print("dwarfdump analysis time: %f" % (time.time() - start_time))
+    debug_indexes = {}
+    rela_debug_indexes = {}
+    text_indexes = {}
+    data_indexes = {}
+
+    additional_syms = 0
+    need_info_length_reloc = len(func_offsets) + len(var_offsets) > 0
+    if need_info_length_reloc:
+        additional_syms += 1
+    need_line_length_reloc = len(line_offsets) > 0
+    if need_line_length_reloc:
+        additional_syms += 1
+    need_aranges_length_reloc = len(aranges_offsets) > 0
+    if need_aranges_length_reloc:
+        additional_syms += 1
+    additional_syms += len(loc_offsets) + 1
+    additional_syms += len(range_start_offsets)
+
+    with open(path, 'r+b') as elf:
+        elf.seek(40)
+        shoff = quad.unpack(elf.read(8))[0]
+        assert shoff != 0, 'object with no shdrs is unsupported'
+        elf.seek(60)
+        shnum = half.unpack(elf.read(2))[0]
+        shstrndx = half.unpack(elf.read(2))[0]
+
+        ## e_shnum == 0 means the first section header sh_size contains the real
+        ## number of sections.
+        if shnum == 0:
+            elf.seek(shoff + 32)
+            shnum = quad.unpack(elf.read(8))[0]
+        elf.seek(shoff)
+        shdr_table = SectionHeaderTable(elf.read(shnum * 64), shnum)
+
+        ## e_shstrndx == SHN_XINDEX means the first section header sh_link
+        ## contains the real index.
+        if shstrndx == SHN_XINDEX:
+            shstrndx = word.unpack(shdr_table.get(0)[40:44])[0]
+        strtab_shdr = shdr_table.get(shstrndx)
+        strtab = StringTable(elf, quad.unpack(strtab_shdr[24:32])[0])
+        symtab_shndx = None
+
+        start_time = time.time()
+        for i in range(0, shnum):
+            shdr = shdr_table.get(i)
+            sh_name = word.unpack(shdr[:4])[0]
+            sh_type = word.unpack(shdr[4:8])[0]
+            name = strtab.get_string(sh_name)
+            if sh_type == SHT_PROGBITS and name.startswith(b'.debug'):
+                assert name not in debug_indexes
+                debug_indexes[name] = {}
+                debug_indexes[name]['index'] = i
+                debug_indexes[name]['shdr'] = shdr
+            elif sh_type == SHT_RELA and name.startswith(b'.rela.debug'):
+                assert name not in rela_debug_indexes
+                rela_debug_indexes[name] = {}
+                rela_debug_indexes[name]['index'] = i
+                rela_debug_indexes[name]['shdr'] = shdr
+            elif sh_type == SHT_SYMTAB:
+                sh_offset = quad.unpack(shdr[24:32])[0]
+                sh_link = word.unpack(shdr[40:44])[0]
+                if sh_link == shstrndx:
+                    sym_strtab = strtab
+                else:
+                    symtab_strtab_shdr = shdr_table.get(sh_link)
+                    sym_strtab = StringTable(elf, quad.unpack(elf.read(8))[0])
+                symtab = SymbolTable(elf, sh_offset, sym_strtab)
+            elif sh_type == SHT_SYMTAB_SHNDX:
+                symtab_shndx = SymtabShndxTable(elf, quad.unpack(shdr[24:32])[0])
+
+        print("shdr read time: %f" % (time.time() - start_time))
+
+        if len(debug_indexes) == 0:
+            # No debug data, so nothing to do here.
+            return
+
+        if symtab_shndx is not None:
+            symtab.symtab_shndx = symtab_shndx
+
+        start_time = time.time()
+        if b'.debug_info' in debug_indexes:
+            splits = make_debug_info_split_points(func_offsets, var_offsets)
+            debug_info_secs = split_shdr(elf, shdr_table, debug_indexes[b'.debug_info']['shdr'], debug_indexes[b'.debug_info']['index'], splits)
+            shnum += len(debug_info_secs) - 1
+            if b'.rela.debug_info' in rela_debug_indexes:
+                shnum += split_relocs(elf, shdr_table, symtab, rela_debug_indexes[b'.rela.debug_info']['shdr'], rela_debug_indexes[b'.rela.debug_info']['index'], debug_info_secs) - 1
+            # TODO: Add relocation + symbol for length
+        if b'.debug_line' in debug_indexes:
+            debug_line_secs = split_shdr(elf, shdr_table, debug_indexes[b'.debug_line']['shdr'], debug_indexes[b'.debug_line']['index'], line_offsets)
+            shnum += len(debug_line_secs) - 1
+            if b'.rela.debug_line' in rela_debug_indexes:
+                shnum += split_relocs(elf, shdr_table, symtab, rela_debug_indexes[b'.rela.debug_line']['shdr'], rela_debug_indexes[b'.rela.debug_line']['index'], debug_line_secs) - 1
+            # TODO: Add relocation + symbol for length
+        if b'.debug_aranges' in debug_indexes:
+            debug_aranges_secs = split_shdr(elf, shdr_table, debug_indexes[b'.debug_aranges']['shdr'], debug_indexes[b'.debug_aranges']['index'], aranges_offsets)
+            shnum += len(debug_aranges_secs) - 1
+            if b'.rela.debug_aranges' in rela_debug_indexes:
+                shnum += split_relocs(elf, shdr_table, symtab, rela_debug_indexes[b'.rela.debug_aranges']['shdr'], rela_debug_indexes[b'.rela.debug_aranges']['index'], debug_aranges_secs) - 1
+            # TODO: Add relocation + symbol for length
+        if b'.debug_loc' in debug_indexes:
+            debug_loc_secs = split_shdr(elf, shdr_table, debug_indexes[b'.debug_loc']['shdr'], debug_indexes[b'.debug_loc']['index'], loc_offsets)
+            shnum += len(debug_loc_secs) - 1
+            if b'.rela.debug_loc' in rela_debug_indexes:
+                shnum += split_relocs(elf, shdr_table, symtab, rela_debug_indexes[b'.rela.debug_loc']['shdr'], rela_debug_indexes[b'.rela.debug_loc']['index'], debug_loc_secs) - 1
+            # TODO: Add symbols for each section.
+        if b'.debug_ranges' in debug_indexes and b'.rela.debug_ranges' in rela_debug_indexes:
+            shnum += split_debug_ranges(elf,
+                                        shdr_table,
+                                        symtab,
+                                        debug_indexes[b'.debug_ranges']['shdr'],
+                                        debug_indexes[b'.debug_ranges']['index'],
+                                        rela_debug_indexes[b'.rela.debug_ranges']['shdr'],
+                                        rela_debug_indexes[b'.rela.debug_ranges']['index'])
+        print("split debug time: %f" % (time.time() - start_time))
+
+        shdr_table.write(elf, shoff)
+
+def copy_and_fragment(path, root, outdir, tmpdir, force_split, force_archive_split, bindir):
+    """
+        Copy the file at path to outdir, fragmenting it either en route, or once
+        at the destination, using tools located in bindir. The output file will
+        be placed in outdir in the same relative structure as path is in root.
+    """
+    success_file = os.path.normpath(path) + '.success'
+    if force_split and os.path.exists(success_file):
+        os.remove(success_file)
+    dest = os.path.join(outdir, os.path.relpath(path, root))
+    kind = get_file_kind(path)
+    if os.path.exists(success_file) and os.path.exists(dest) and not (force_archive_split and kind == ARCHIVE_KIND):
+        return
+
+    if kind == NORMAL_KIND:
+        copy_to_dir(path, root, outdir)
+    elif kind == ARCHIVE_KIND:
+        if tmpdir is None:
+            tmpdir = tempfile.mkdtemp()
+        elif os.path.exists(tmpdir):
+            shutil.rmtree(tmpdir)
+            os.makedirs(tmpdir)
+        else:
+            os.makedirs(tmpdir)
+        archive = copy_to_dir(path, root, tmpdir)
+        members = extract_members(archive, bindir)
+        for member in members:
+            fragment(member, path + '.' + os.path.basename(member), bindir)
+        replace_archive(members, archive, tmpdir, bindir)
+        copy_to_dir(archive, tmpdir, outdir)
+
+    else:
+        obj = copy_to_dir(path, root, outdir)
+        fragment(obj, path, bindir)
+
+    with open(success_file, 'w') as success:
+        json.dump(path, success)
+
+def main():
+    start = time.time()
+    args = parse_commandline()
+    files = find_files(args.input)
+    if args.force_split:
+        shutil.rmtree(args.outdir)
+    i = 1
+    if not os.path.exists(args.outdir):
+        os.makedirs(args.outdir)
+    for f in files:
+        print("Fragmenting %s [%d/%d]" % (f, i, len(files)))
+        copy_and_fragment(f, args.input, args.outdir, args.tmpdir, args.force_split, args.force_archive_split, args.bin)
+        i += 1
+    print("Total time: %f" % (time.time() - start))
+
+if __name__ == '__main__':
+    main()