--- /dev/null
+<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>
+
projects / apple / ld64.git / blobdiff