| .. _design: |
| |
| Linker Design |
| ============= |
| |
| Note: this document discuss Mach-O port of LLD. For ELF and COFF, |
| see :doc:`index`. |
| |
| Introduction |
| ------------ |
| |
| lld is a new generation of linker. It is not "section" based like traditional |
| linkers which mostly just interlace sections from multiple object files into the |
| output file. Instead, lld is based on "Atoms". Traditional section based |
| linking work well for simple linking, but their model makes advanced linking |
| features difficult to implement. Features like dead code stripping, reordering |
| functions for locality, and C++ coalescing require the linker to work at a finer |
| grain. |
| |
| An atom is an indivisible chunk of code or data. An atom has a set of |
| attributes, such as: name, scope, content-type, alignment, etc. An atom also |
| has a list of References. A Reference contains: a kind, an optional offset, an |
| optional addend, and an optional target atom. |
| |
| The Atom model allows the linker to use standard graph theory models for linking |
| data structures. Each atom is a node, and each Reference is an edge. The |
| feature of dead code stripping is implemented by following edges to mark all |
| live atoms, and then delete the non-live atoms. |
| |
| |
| Atom Model |
| ---------- |
| |
| An atom is an indivisible chunk of code or data. Typically each user written |
| function or global variable is an atom. In addition, the compiler may emit |
| other atoms, such as for literal c-strings or floating point constants, or for |
| runtime data structures like dwarf unwind info or pointers to initializers. |
| |
| A simple "hello world" object file would be modeled like this: |
| |
| .. image:: hello.png |
| |
| There are three atoms: main, a proxy for printf, and an anonymous atom |
| containing the c-string literal "hello world". The Atom "main" has two |
| references. One is the call site for the call to printf, and the other is a |
| reference for the instruction that loads the address of the c-string literal. |
| |
| There are only four different types of atoms: |
| |
| * DefinedAtom |
| 95% of all atoms. This is a chunk of code or data |
| |
| * UndefinedAtom |
| This is a place holder in object files for a reference to some atom |
| outside the translation unit.During core linking it is usually replaced |
| by (coalesced into) another Atom. |
| |
| * SharedLibraryAtom |
| If a required symbol name turns out to be defined in a dynamic shared |
| library (and not some object file). A SharedLibraryAtom is the |
| placeholder Atom used to represent that fact. |
| |
| It is similar to an UndefinedAtom, but it also tracks information |
| about the associated shared library. |
| |
| * AbsoluteAtom |
| This is for embedded support where some stuff is implemented in ROM at |
| some fixed address. This atom has no content. It is just an address |
| that the Writer needs to fix up any references to point to. |
| |
| |
| File Model |
| ---------- |
| |
| The linker views the input files as basically containers of Atoms and |
| References, and just a few attributes of their own. The linker works with three |
| kinds of files: object files, static libraries, and dynamic shared libraries. |
| Each kind of file has reader object which presents the file in the model |
| expected by the linker. |
| |
| Object File |
| ~~~~~~~~~~~ |
| |
| An object file is just a container of atoms. When linking an object file, a |
| reader is instantiated which parses the object file and instantiates a set of |
| atoms representing all content in the .o file. The linker adds all those atoms |
| to a master graph. |
| |
| Static Library (Archive) |
| ~~~~~~~~~~~~~~~~~~~~~~~~ |
| |
| This is the traditional unix static archive which is just a collection of object |
| files with a "table of contents". When linking with a static library, by default |
| nothing is added to the master graph of atoms. Instead, if after merging all |
| atoms from object files into a master graph, if any "undefined" atoms are left |
| remaining in the master graph, the linker reads the table of contents for each |
| static library to see if any have the needed definitions. If so, the set of |
| atoms from the specified object file in the static library is added to the |
| master graph of atoms. |
| |
| Dynamic Library (Shared Object) |
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| |
| Dynamic libraries are different than object files and static libraries in that |
| they don't directly add any content. Their purpose is to check at build time |
| that the remaining undefined references can be resolved at runtime, and provide |
| a list of dynamic libraries (SO_NEEDED) that will be needed at runtime. The way |
| this is modeled in the linker is that a dynamic library contributes no atoms to |
| the initial graph of atoms. Instead, (like static libraries) if there are |
| "undefined" atoms in the master graph of all atoms, then each dynamic library is |
| checked to see if exports the required symbol. If so, a "shared library" atom is |
| instantiated by the by the reader which the linker uses to replace the |
| "undefined" atom. |
| |
| Linking Steps |
| ------------- |
| |
| Through the use of abstract Atoms, the core of linking is architecture |
| independent and file format independent. All command line parsing is factored |
| out into a separate "options" abstraction which enables the linker to be driven |
| with different command line sets. |
| |
| The overall steps in linking are: |
| |
| #. Command line processing |
| |
| #. Parsing input files |
| |
| #. Resolving |
| |
| #. Passes/Optimizations |
| |
| #. Generate output file |
| |
| The Resolving and Passes steps are done purely on the master graph of atoms, so |
| they have no notion of file formats such as mach-o or ELF. |
| |
| |
| Input Files |
| ~~~~~~~~~~~ |
| |
| Existing developer tools using different file formats for object files. |
| A goal of lld is to be file format independent. This is done |
| through a plug-in model for reading object files. The lld::Reader is the base |
| class for all object file readers. A Reader follows the factory method pattern. |
| A Reader instantiates an lld::File object (which is a graph of Atoms) from a |
| given object file (on disk or in-memory). |
| |
| Every Reader subclass defines its own "options" class (for instance the mach-o |
| Reader defines the class ReaderOptionsMachO). This options class is the |
| one-and-only way to control how the Reader operates when parsing an input file |
| into an Atom graph. For instance, you may want the Reader to only accept |
| certain architectures. The options class can be instantiated from command |
| line options, or it can be subclassed and the ivars programmatically set. |
| |
| Resolving |
| ~~~~~~~~~ |
| |
| The resolving step takes all the atoms' graphs from each object file and |
| combines them into one master object graph. Unfortunately, it is not as simple |
| as appending the atom list from each file into one big list. There are many |
| cases where atoms need to be coalesced. That is, two or more atoms need to be |
| coalesced into one atom. This is necessary to support: C language "tentative |
| definitions", C++ weak symbols for templates and inlines defined in headers, |
| replacing undefined atoms with actual definition atoms, and for merging copies |
| of constants like c-strings and floating point constants. |
| |
| The linker support coalescing by-name and by-content. By-name is used for |
| tentative definitions and weak symbols. By-content is used for constant data |
| that can be merged. |
| |
| The resolving process maintains some global linking "state", including a "symbol |
| table" which is a map from llvm::StringRef to lld::Atom*. With these data |
| structures, the linker iterates all atoms in all input files. For each atom, it |
| checks if the atom is named and has a global or hidden scope. If so, the atom |
| is added to the symbol table map. If there already is a matching atom in that |
| table, that means the current atom needs to be coalesced with the found atom, or |
| it is a multiple definition error. |
| |
| When all initial input file atoms have been processed by the resolver, a scan is |
| made to see if there are any undefined atoms in the graph. If there are, the |
| linker scans all libraries (both static and dynamic) looking for definitions to |
| replace the undefined atoms. It is an error if any undefined atoms are left |
| remaining. |
| |
| Dead code stripping (if requested) is done at the end of resolving. The linker |
| does a simple mark-and-sweep. It starts with "root" atoms (like "main" in a main |
| executable) and follows each references and marks each Atom that it visits as |
| "live". When done, all atoms not marked "live" are removed. |
| |
| The result of the Resolving phase is the creation of an lld::File object. The |
| goal is that the lld::File model is **the** internal representation |
| throughout the linker. The file readers parse (mach-o, ELF, COFF) into an |
| lld::File. The file writers (mach-o, ELF, COFF) taken an lld::File and produce |
| their file kind, and every Pass only operates on an lld::File. This is not only |
| a simpler, consistent model, but it enables the state of the linker to be dumped |
| at any point in the link for testing purposes. |
| |
| |
| Passes |
| ~~~~~~ |
| |
| The Passes step is an open ended set of routines that each get a change to |
| modify or enhance the current lld::File object. Some example Passes are: |
| |
| * stub (PLT) generation |
| |
| * GOT instantiation |
| |
| * order_file optimization |
| |
| * branch island generation |
| |
| * branch shim generation |
| |
| * Objective-C optimizations (Darwin specific) |
| |
| * TLV instantiation (Darwin specific) |
| |
| * DTrace probe processing (Darwin specific) |
| |
| * compact unwind encoding (Darwin specific) |
| |
| |
| Some of these passes are specific to Darwin's runtime environments. But many of |
| the passes are applicable to any OS (such as generating branch island for out of |
| range branch instructions). |
| |
| The general structure of a pass is to iterate through the atoms in the current |
| lld::File object, inspecting each atom and doing something. For instance, the |
| stub pass, looks for call sites to shared library atoms (e.g. call to printf). |
| It then instantiates a "stub" atom (PLT entry) and a "lazy pointer" atom for |
| each proxy atom needed, and these new atoms are added to the current lld::File |
| object. Next, all the noted call sites to shared library atoms have their |
| References altered to point to the stub atom instead of the shared library atom. |
| |
| |
| Generate Output File |
| ~~~~~~~~~~~~~~~~~~~~ |
| |
| Once the passes are done, the output file writer is given current lld::File |
| object. The writer's job is to create the executable content file wrapper and |
| place the content of the atoms into it. |
| |
| lld uses a plug-in model for writing output files. All concrete writers (e.g. |
| ELF, mach-o, etc) are subclasses of the lld::Writer class. |
| |
| Unlike the Reader class which has just one method to instantiate an lld::File, |
| the Writer class has multiple methods. The crucial method is to generate the |
| output file, but there are also methods which allow the Writer to contribute |
| Atoms to the resolver and specify passes to run. |
| |
| An example of contributing |
| atoms is that if the Writer knows a main executable is being linked and such |
| an executable requires a specially named entry point (e.g. "_main"), the Writer |
| can add an UndefinedAtom with that special name to the resolver. This will |
| cause the resolver to issue an error if that symbol is not defined. |
| |
| Sometimes a Writer supports lazily created symbols, such as names for the start |
| of sections. To support this, the Writer can create a File object which vends |
| no initial atoms, but does lazily supply atoms by name as needed. |
| |
| Every Writer subclass defines its own "options" class (for instance the mach-o |
| Writer defines the class WriterOptionsMachO). This options class is the |
| one-and-only way to control how the Writer operates when producing an output |
| file from an Atom graph. For instance, you may want the Writer to optimize |
| the output for certain OS versions, or strip local symbols, etc. The options |
| class can be instantiated from command line options, or it can be subclassed |
| and the ivars programmatically set. |
| |
| |
| lld::File representations |
| ------------------------- |
| |
| Just as LLVM has three representations of its IR model, lld has two |
| representations of its File/Atom/Reference model: |
| |
| * In memory, abstract C++ classes (lld::Atom, lld::Reference, and lld::File). |
| |
| * textual (in YAML) |
| |
| |
| Textual representations in YAML |
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| |
| In designing a textual format we want something easy for humans to read and easy |
| for the linker to parse. Since an atom has lots of attributes most of which are |
| usually just the default, we should define default values for every attribute so |
| that those can be omitted from the text representation. Here is the atoms for a |
| simple hello world program expressed in YAML:: |
| |
| target-triple: x86_64-apple-darwin11 |
| |
| atoms: |
| - name: _main |
| scope: global |
| type: code |
| content: [ 55, 48, 89, e5, 48, 8d, 3d, 00, 00, 00, 00, 30, c0, e8, 00, 00, |
| 00, 00, 31, c0, 5d, c3 ] |
| fixups: |
| - offset: 07 |
| kind: pcrel32 |
| target: 2 |
| - offset: 0E |
| kind: call32 |
| target: _fprintf |
| |
| - type: c-string |
| content: [ 73, 5A, 00 ] |
| |
| ... |
| |
| The biggest use for the textual format will be writing test cases. Writing test |
| cases in C is problematic because the compiler may vary its output over time for |
| its own optimization reasons which my inadvertently disable or break the linker |
| feature trying to be tested. By writing test cases in the linkers own textual |
| format, we can exactly specify every attribute of every atom and thus target |
| specific linker logic. |
| |
| The textual/YAML format follows the ReaderWriter patterns used in lld. The lld |
| library comes with the classes: ReaderYAML and WriterYAML. |
| |
| |
| Testing |
| ------- |
| |
| The lld project contains a test suite which is being built up as new code is |
| added to lld. All new lld functionality should have a tests added to the test |
| suite. The test suite is `lit <http://llvm.org/cmds/lit.html/>`_ driven. Each |
| test is a text file with comments telling lit how to run the test and check the |
| result To facilitate testing, the lld project builds a tool called lld-core. |
| This tool reads a YAML file (default from stdin), parses it into one or more |
| lld::File objects in memory and then feeds those lld::File objects to the |
| resolver phase. |
| |
| |
| Resolver testing |
| ~~~~~~~~~~~~~~~~ |
| |
| Basic testing is the "core linking" or resolving phase. That is where the |
| linker merges object files. All test cases are written in YAML. One feature of |
| YAML is that it allows multiple "documents" to be encoding in one YAML stream. |
| That means one text file can appear to the linker as multiple .o files - the |
| normal case for the linker. |
| |
| Here is a simple example of a core linking test case. It checks that an |
| undefined atom from one file will be replaced by a definition from another |
| file:: |
| |
| # RUN: lld-core %s | FileCheck %s |
| |
| # |
| # Test that undefined atoms are replaced with defined atoms. |
| # |
| |
| --- |
| atoms: |
| - name: foo |
| definition: undefined |
| --- |
| atoms: |
| - name: foo |
| scope: global |
| type: code |
| ... |
| |
| # CHECK: name: foo |
| # CHECK: scope: global |
| # CHECK: type: code |
| # CHECK-NOT: name: foo |
| # CHECK: ... |
| |
| |
| Passes testing |
| ~~~~~~~~~~~~~~ |
| |
| Since Passes just operate on an lld::File object, the lld-core tool has the |
| option to run a particular pass (after resolving). Thus, you can write a YAML |
| test case with carefully crafted input to exercise areas of a Pass and the check |
| the resulting lld::File object as represented in YAML. |
| |
| |
| Design Issues |
| ------------- |
| |
| There are a number of open issues in the design of lld. The plan is to wait and |
| make these design decisions when we need to. |
| |
| |
| Debug Info |
| ~~~~~~~~~~ |
| |
| Currently, the lld model says nothing about debug info. But the most popular |
| debug format is DWARF and there is some impedance mismatch with the lld model |
| and DWARF. In lld there are just Atoms and only Atoms that need to be in a |
| special section at runtime have an associated section. Also, Atoms do not have |
| addresses. The way DWARF is spec'ed different parts of DWARF are supposed to go |
| into specially named sections and the DWARF references function code by address. |
| |
| CPU and OS specific functionality |
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| |
| Currently, lld has an abstract "Platform" that deals with any CPU or OS specific |
| differences in linking. We just keep adding virtual methods to the base |
| Platform class as we find linking areas that might need customization. At some |
| point we'll need to structure this better. |
| |
| |
| File Attributes |
| ~~~~~~~~~~~~~~~ |
| |
| Currently, lld::File just has a path and a way to iterate its atoms. We will |
| need to add more attributes on a File. For example, some equivalent to the |
| target triple. There is also a number of cached or computed attributes that |
| could make various Passes more efficient. For instance, on Darwin there are a |
| number of Objective-C optimizations that can be done by a Pass. But it would |
| improve the plain C case if the Objective-C optimization Pass did not have to |
| scan all atoms looking for any Objective-C data structures. This could be done |
| if the lld::File object had an attribute that said if the file had any |
| Objective-C data in it. The Resolving phase would then be required to "merge" |
| that attribute as object files are added. |