<html> <head> <title>Linker</title> </head> <body> <h1> Inside the Linker </h1> <div class="doc_author"> <p>Written by <a href="mailto:kledzik@apple.com">Nick Kledzik</a></p> </div> <h2> <a name="introduction">Introduction</a> </h2> <p>The Darwin linker 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. The Darwin linker 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. </p> <p>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 Fixups. A Fixup contains: a kind, an optional offset, an optional addend, and an optional target atom.</p> <p>The Atom model allows the linker to use standard graph theory models for linking data structures. Each atom is a node, and each Fixup 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.</p> <br> <h2> <a name="Atom model">Atom model</a> </h2> <p>An atom is an indivisible chuck 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. </p> <p>A simple "hello world" object file would be modeled like this:</p> <img src="hello.png" alt="hello world graphic"/> <p>There are two atoms: main and an anonymous atom containing the c-string literal "hello world". The Atom "main" has two fixups. One is the call site for the call to printf, and the other is a fixup for the instruction that loads the address of the c-string literal. </p> <br> <h2> <a name="File model">File model</a> </h2> <p>The linker views the input files as basically containers of Atoms and Fixups, and just a few attributes of their own. The linker works with three kinds of files: object files, static libraries, and dynamic libraries. Each kind of file has reader object which presents the file in the model expected by the linker.</p> <h4> <a>Object File</a> </h4> An object file is just a container of atoms. When linking with an object file, all atoms are added to the initial graph of atoms. <h4> <a>Static Library (Archive)</a> </h4> 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 initial graph of atoms. Instead, if there are unresolved references (dangling edges) in the master graph of all atoms, and the table of contents for a static library says that one of the object files in the library defines one of the missing symbols (dangling edge), the set of atoms from the specified object file in the static library is added to the master graph of atoms. <h4> <a>Dynamic Library (Shared Object)</a> </h4> Dynamic libraries are unique in that the don't directly add add any atoms. Their purpose is to check at build time that all references are resolved 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 unresolved references (dangling edges) in the master graph of all atoms, if a dynamic library exports a required symbol, then a "proxy" atom is instantiated by the linker. The proxy atom allows the master atom graph to have all edges resolved and also records from which dynamic library a symbol came.</p> <br> <h2> <a name="Linking Steps">Linking Steps</a> </h2> <p>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.</p> <p>The overall steps in linking are:<p> <ol> <li>Command line processing</li> <li>Parsing input files</li> <li>Resolving</li> <li>Passes/Optimizations</li> <li>Generate output file</li> </ol> <p>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.</p> <h4> <a>Resolving</a> </h4> <p>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, and for merging copies of constants like c-strings and floating point constants.</p> <p>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. </p> <p>When one atom has a reference (FixUp) to another atom, there is also a binding type: by-name, direct, or indirect. A Fixup contains a tagged union that if the binding type is by-name, the union field is a pointer to a c-string. If the binding type is direct, the union is a pointer to an Atom. If the binding type is indirect, the union is a index into a table of pointers to Atoms. Below is a graphical representation of the binding types:</p> <img src="bindings.png" alt="binding types graphic"/> <p>Input file Atoms contain only direct and by-name references. Direct references are used for atoms defined in the same object file for which the target atom is either unnamed or cannot change. For instance, calling a static function in a translation unit will result in a direct reference to the static functions's atom. Also the FDE (dwarf unwind info) for a function has a direct reference to its function. On the other hand references to global symbols (e.g. call to printf) use by-name binding in object files. </p> <p>The resolving process maintains some global linking "state", including: a "symbol table" which is a map from c-string to Atom*, an indirect symbol table which is a growable array of Atom*, and for each kind of coalesable constants there is a content to Atom* map. With these data structures, the linker walks all atoms in all input files. For each atom, it checks if the atom should be in one symbol table or one of the coalescing tables. If so, it attempts to add the atom. If there already is a matching atom in that table, that means the current atom needs to be coalesced with the found atom. </p> <p>To support coalescing, all references to coalesable atoms are changed to indirect binding and an entry is added to the indirect table which points to the current chosen atom. When all input atoms have been processed by the resolver, there should be only direct and indirect bindings left. If there are any NULL entries in the indirect table, that means there are undefined references. The linker then looks to the supplied libraries (both static and dynamic) to resolve those references. </p> <p>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. </p> <h4> <a>Passes</a> </h4> <p>The Passes step is an open ended set of routines that each get a change to modify or enhance the master graph of atoms. Passes are only run if the master graph of atoms is completely resolved (no dangling edges). The current set of Passes in the Darwin linker are:</p> <ul> <li>Objective-C optimizations (Apple)</li> <li>stub (PLT) generation</li> <li>GOT instantiation</li> <li>TLV instantiation (Apple)</li> <li>order_file optimization</li> <li>branch island generation</li> <li>branch shim generation</li> <li>dtrace probe processing (Apple)</li> <li>compact unwind encoding (Apple)</li> </ul> <p>Some of these passes are specific to Apple's runtime environments. But many of the passes are applicable to any OS (such as generating branch island for out of range branch instructions).</p> <p>The general structure of a pass is to walk the master graph inspecting each atom and doing something. For instance, the stub pass, walks the graph looking for atoms with call sites to proxy 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 master graph. Next all the noted call sites to proxy atoms are replaced with calls to the corresponding stub atom.</p> <h4><a>Generate Output File</a> </h4> <p>Once the passes are done, the output file generator is given a sorted list of atoms. Its job is to create the executable content file wrapper and place the content of the atoms into it. </p> <h2> <a name="Future Directions">Future Directions</a> </h2> <h4><a>Sections</a> </h4> <p>The current use of sections in mach-o .o files over-constrains the linker. By default, the linker should preserve the section an atom is in. But since all sections must be contiguous in the output, that limits the ability of the linker to order atoms for locality. It would be helpful to enrich the object file with with reason something is in the section it is. For instance, is the section found at runtime? Or was the use of a section just a quick way to group some content together? </p> <p>The ELF model for sections is a little better than mach-o because ELF sections have write and execute bits, whereas mach-o sections must be in some segment and the segment has the write and execute bits. </p> <h4><a>Mach-o Object File Format</a> </h4> <p> The messiest part of the linker is the mach-o parser. This is because mach-o is a traditional section and symbols based file format. The parser must infer atom boundaries using two approaches. The first is that some section types have well defined content which the linker can parse into atoms (e.g. __cstring, __eh_frame). The other approach is a naming convention (which the compiler follows) by which the linker breaks sections into atoms at any non-local (not starting with 'L') symbol. The processing the linker has to do parse mach-o .o files is a significant part of the link time. </p> <p>Given that the assembler writes object files once, whereas the linker reads them many times (during development), it would make sense to optimize the object file format to be something the linker can read/parse efficiently.</p> <h4><a>New Object File Model</a> </h4> <p>LLVM has a nice model for its IR. There are three representations: the binary bit code file, the in-memory object model, and a textual representation. LLVM contains utility possible code for converting between these representations. The same model makes sense for atoms too. There should be three representations for atoms: binary file, in-memory, and textual. The Darwin linker already has an in-memory C++ object model for Atoms. All we need is a textual representation and binary file format. </p> <p>Note: in the darwin linker the binary format for input object files is independent of the output executable format. That is, we could have one universal object file format which the linker could use as input to produce mach-o, ELF, or PE executables.</p> <p> The object file binary format should be designed to instantiate into atoms as fast as possible. The obvious way to do that is that the file format would be an array of atoms. The linker just mmaps in the file and looks at the header to see how many atoms there and instantiate that many atoms with the atom attribute information coming from that array. The trick is designing this in a way that can be extended as the Atom mode evolves and new attributes are added. </p> <p> 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. One possile format is YAML. Here is the atoms for a simple hello world program expressed in YAML. </p> <pre> --- target-triple: x86_64-apple-darwin11 source: atoms: - name: _main scope: linkage-unit type: code alignment: power: 4 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 merge: by-content content: [ 73, 5A, 00 ] ... </pre> <p>One big use for the textual format will be writing test cases. The Darwin linker test suite test cases are written mostly in C/C++ and a few assembly files. The use of C means the same test case can be compiled for different architectures. But 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. </p> <h4><a>Debug Info</a> </h4> <p>Around 2005 when Apple switched from using STABS to using DWARF for debug information, we made a design decision to have the linker ignore DWARF in .o files. This improves linking performance because the linker is not copying tons of debug info. Instead, the linker adds "debug notes" into output binary that contain the paths of the original .o files. During development the Darwin debugger will notice the debug notes and the load the dwarf debug information from the original object files. For release builds, a tool named dsymutil is run on the program. It finds the debug notes and then the original object files, then reads, merges and optimizes all the dwarf debug information into one .dSYM file which can be loaded by the debugger if needed.</p> <p>The current way DWARF is generated is that all debug information for all functions in a translation unit are merged and optimized into sections based on debug info kind. For instance the mapping of instructions to source line numbers for all functions is compressed and put in one section. This does not play well in an Atom based file format. One idea is to have the compiler emit some intermediate representation debug information (one which is partitioned per atom) into the Atom based file format. The linker could then have code to convert that intermediate debug into to final dwarf. This is still an open question.</p> <h4><a>Extending Atom attributes to ELF and XCOFF</a> </h4> <p>The current set of attributes defined for Atoms in the darwin linker were chosen to meet the requirements of developing code to run on iOS and Mac OS X. Below is a list of the attributes and their possible values. It may just require adding more values to support ELF and XCOFF. Or there may need to be new attributes added to capture new functionality. </p> <ul> <li>Name</li> <li>Size</li> <li>Section (I'd like to get rid of this)</li> <li>ContentType (currently some of this comes from section)</li> <ul> <li>code</li> <li>stub</li> <li>data</li> <li>zeroFill</li> <li>initializerPointer</li> <li>objc1Class</li> <li>objc2Class</li> <li>objcClassPointer</li> <li>objc2CategoryList</li> <li>non-lazy-pointer</li> <li>lazy-pointer</li> <li>constant</li> <li>literal4</li> <li>literal8</li> <li>literal16</li> <li>cstring</li> <li>cstringPointer</li> <li>utf16string</li> <li>CFString</li> <li>CFI</li> <li>LSDA</li> </ul> </li> <li>Scope <ul> <li>translationUnit (static functions)</li> <li>linkageUnit (visibility hidden)</li> <li>global</li> </ul> </li> <li>DefinitionKind <ul> <li>regular</li> <li>tentative (ANSI C feature)</li> <li>absolute (assembly code feature)</li> <li>proxy (stand-in for dynamic library symbol)</li> </ul> </li> <li>Combine <ul> <li>never</li> <li>byName (weak symbols)</li> <li>byContent (simple constants)</li> <li>byContentAndReferences (complex constants)</li> </ul> </li> <li>SymbolTableStatus <ul> <li>In</li> <li>notIn (anonymous)</li> <li>inAsAbsolute (assembly code feature)</li> <li>inAndNeverStrip (tell strip tool to leave)</li> <li>inWithRandomName (mach-o .o feature)</li> </ul> <li>Alignment <ul> <li>powerOfTwo</li> <li>modulus</li> </ul> <li>NeverDeadStrip (boolean)</li> <li>IsThumb (ARM specific)</li> </ul> <p>Where does dllexport fit in here? Where does visibility protected and internal fit? Protected seems like scope=global plus the rule to not indirect references to it. Internal is like hidden plus enables some compiler optimizations. I'm not sure the linker needs to know about internal. </p> </body> </html>