doc/design/linker.html

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