1.. _design: 2 3Linker Design 4============= 5 6Note: this document discuss Mach-O port of LLD. For ELF and COFF, 7see :doc:`index`. 8 9Introduction 10------------ 11 12lld is a new generation of linker. It is not "section" based like traditional 13linkers which mostly just interlace sections from multiple object files into the 14output file. Instead, lld is based on "Atoms". Traditional section based 15linking work well for simple linking, but their model makes advanced linking 16features difficult to implement. Features like dead code stripping, reordering 17functions for locality, and C++ coalescing require the linker to work at a finer 18grain. 19 20An atom is an indivisible chunk of code or data. An atom has a set of 21attributes, such as: name, scope, content-type, alignment, etc. An atom also 22has a list of References. A Reference contains: a kind, an optional offset, an 23optional addend, and an optional target atom. 24 25The Atom model allows the linker to use standard graph theory models for linking 26data structures. Each atom is a node, and each Reference is an edge. The 27feature of dead code stripping is implemented by following edges to mark all 28live atoms, and then delete the non-live atoms. 29 30 31Atom Model 32---------- 33 34An atom is an indivisible chunk of code or data. Typically each user written 35function or global variable is an atom. In addition, the compiler may emit 36other atoms, such as for literal c-strings or floating point constants, or for 37runtime data structures like dwarf unwind info or pointers to initializers. 38 39A simple "hello world" object file would be modeled like this: 40 41.. image:: hello.png 42 43There are three atoms: main, a proxy for printf, and an anonymous atom 44containing the c-string literal "hello world". The Atom "main" has two 45references. One is the call site for the call to printf, and the other is a 46reference for the instruction that loads the address of the c-string literal. 47 48There are only four different types of atoms: 49 50 * DefinedAtom 51 95% of all atoms. This is a chunk of code or data 52 53 * UndefinedAtom 54 This is a place holder in object files for a reference to some atom 55 outside the translation unit.During core linking it is usually replaced 56 by (coalesced into) another Atom. 57 58 * SharedLibraryAtom 59 If a required symbol name turns out to be defined in a dynamic shared 60 library (and not some object file). A SharedLibraryAtom is the 61 placeholder Atom used to represent that fact. 62 63 It is similar to an UndefinedAtom, but it also tracks information 64 about the associated shared library. 65 66 * AbsoluteAtom 67 This is for embedded support where some stuff is implemented in ROM at 68 some fixed address. This atom has no content. It is just an address 69 that the Writer needs to fix up any references to point to. 70 71 72File Model 73---------- 74 75The linker views the input files as basically containers of Atoms and 76References, and just a few attributes of their own. The linker works with three 77kinds of files: object files, static libraries, and dynamic shared libraries. 78Each kind of file has reader object which presents the file in the model 79expected by the linker. 80 81Object File 82~~~~~~~~~~~ 83 84An object file is just a container of atoms. When linking an object file, a 85reader is instantiated which parses the object file and instantiates a set of 86atoms representing all content in the .o file. The linker adds all those atoms 87to a master graph. 88 89Static Library (Archive) 90~~~~~~~~~~~~~~~~~~~~~~~~ 91 92This is the traditional unix static archive which is just a collection of object 93files with a "table of contents". When linking with a static library, by default 94nothing is added to the master graph of atoms. Instead, if after merging all 95atoms from object files into a master graph, if any "undefined" atoms are left 96remaining in the master graph, the linker reads the table of contents for each 97static library to see if any have the needed definitions. If so, the set of 98atoms from the specified object file in the static library is added to the 99master graph of atoms. 100 101Dynamic Library (Shared Object) 102~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 103 104Dynamic libraries are different than object files and static libraries in that 105they don't directly add any content. Their purpose is to check at build time 106that the remaining undefined references can be resolved at runtime, and provide 107a list of dynamic libraries (SO_NEEDED) that will be needed at runtime. The way 108this is modeled in the linker is that a dynamic library contributes no atoms to 109the initial graph of atoms. Instead, (like static libraries) if there are 110"undefined" atoms in the master graph of all atoms, then each dynamic library is 111checked to see if exports the required symbol. If so, a "shared library" atom is 112instantiated by the by the reader which the linker uses to replace the 113"undefined" atom. 114 115Linking Steps 116------------- 117 118Through the use of abstract Atoms, the core of linking is architecture 119independent and file format independent. All command line parsing is factored 120out into a separate "options" abstraction which enables the linker to be driven 121with different command line sets. 122 123The overall steps in linking are: 124 125 #. Command line processing 126 127 #. Parsing input files 128 129 #. Resolving 130 131 #. Passes/Optimizations 132 133 #. Generate output file 134 135The Resolving and Passes steps are done purely on the master graph of atoms, so 136they have no notion of file formats such as mach-o or ELF. 137 138 139Input Files 140~~~~~~~~~~~ 141 142Existing developer tools using different file formats for object files. 143A goal of lld is to be file format independent. This is done 144through a plug-in model for reading object files. The lld::Reader is the base 145class for all object file readers. A Reader follows the factory method pattern. 146A Reader instantiates an lld::File object (which is a graph of Atoms) from a 147given object file (on disk or in-memory). 148 149Every Reader subclass defines its own "options" class (for instance the mach-o 150Reader defines the class ReaderOptionsMachO). This options class is the 151one-and-only way to control how the Reader operates when parsing an input file 152into an Atom graph. For instance, you may want the Reader to only accept 153certain architectures. The options class can be instantiated from command 154line options, or it can be subclassed and the ivars programmatically set. 155 156Resolving 157~~~~~~~~~ 158 159The resolving step takes all the atoms' graphs from each object file and 160combines them into one master object graph. Unfortunately, it is not as simple 161as appending the atom list from each file into one big list. There are many 162cases where atoms need to be coalesced. That is, two or more atoms need to be 163coalesced into one atom. This is necessary to support: C language "tentative 164definitions", C++ weak symbols for templates and inlines defined in headers, 165replacing undefined atoms with actual definition atoms, and for merging copies 166of constants like c-strings and floating point constants. 167 168The linker support coalescing by-name and by-content. By-name is used for 169tentative definitions and weak symbols. By-content is used for constant data 170that can be merged. 171 172The resolving process maintains some global linking "state", including a "symbol 173table" which is a map from llvm::StringRef to lld::Atom*. With these data 174structures, the linker iterates all atoms in all input files. For each atom, it 175checks if the atom is named and has a global or hidden scope. If so, the atom 176is added to the symbol table map. If there already is a matching atom in that 177table, that means the current atom needs to be coalesced with the found atom, or 178it is a multiple definition error. 179 180When all initial input file atoms have been processed by the resolver, a scan is 181made to see if there are any undefined atoms in the graph. If there are, the 182linker scans all libraries (both static and dynamic) looking for definitions to 183replace the undefined atoms. It is an error if any undefined atoms are left 184remaining. 185 186Dead code stripping (if requested) is done at the end of resolving. The linker 187does a simple mark-and-sweep. It starts with "root" atoms (like "main" in a main 188executable) and follows each references and marks each Atom that it visits as 189"live". When done, all atoms not marked "live" are removed. 190 191The result of the Resolving phase is the creation of an lld::File object. The 192goal is that the lld::File model is **the** internal representation 193throughout the linker. The file readers parse (mach-o, ELF, COFF) into an 194lld::File. The file writers (mach-o, ELF, COFF) taken an lld::File and produce 195their file kind, and every Pass only operates on an lld::File. This is not only 196a simpler, consistent model, but it enables the state of the linker to be dumped 197at any point in the link for testing purposes. 198 199 200Passes 201~~~~~~ 202 203The Passes step is an open ended set of routines that each get a change to 204modify or enhance the current lld::File object. Some example Passes are: 205 206 * stub (PLT) generation 207 208 * GOT instantiation 209 210 * order_file optimization 211 212 * branch island generation 213 214 * branch shim generation 215 216 * Objective-C optimizations (Darwin specific) 217 218 * TLV instantiation (Darwin specific) 219 220 * DTrace probe processing (Darwin specific) 221 222 * compact unwind encoding (Darwin specific) 223 224 225Some of these passes are specific to Darwin's runtime environments. But many of 226the passes are applicable to any OS (such as generating branch island for out of 227range branch instructions). 228 229The general structure of a pass is to iterate through the atoms in the current 230lld::File object, inspecting each atom and doing something. For instance, the 231stub pass, looks for call sites to shared library atoms (e.g. call to printf). 232It then instantiates a "stub" atom (PLT entry) and a "lazy pointer" atom for 233each proxy atom needed, and these new atoms are added to the current lld::File 234object. Next, all the noted call sites to shared library atoms have their 235References altered to point to the stub atom instead of the shared library atom. 236 237 238Generate Output File 239~~~~~~~~~~~~~~~~~~~~ 240 241Once the passes are done, the output file writer is given current lld::File 242object. The writer's job is to create the executable content file wrapper and 243place the content of the atoms into it. 244 245lld uses a plug-in model for writing output files. All concrete writers (e.g. 246ELF, mach-o, etc) are subclasses of the lld::Writer class. 247 248Unlike the Reader class which has just one method to instantiate an lld::File, 249the Writer class has multiple methods. The crucial method is to generate the 250output file, but there are also methods which allow the Writer to contribute 251Atoms to the resolver and specify passes to run. 252 253An example of contributing 254atoms is that if the Writer knows a main executable is being linked and such 255an executable requires a specially named entry point (e.g. "_main"), the Writer 256can add an UndefinedAtom with that special name to the resolver. This will 257cause the resolver to issue an error if that symbol is not defined. 258 259Sometimes a Writer supports lazily created symbols, such as names for the start 260of sections. To support this, the Writer can create a File object which vends 261no initial atoms, but does lazily supply atoms by name as needed. 262 263Every Writer subclass defines its own "options" class (for instance the mach-o 264Writer defines the class WriterOptionsMachO). This options class is the 265one-and-only way to control how the Writer operates when producing an output 266file from an Atom graph. For instance, you may want the Writer to optimize 267the output for certain OS versions, or strip local symbols, etc. The options 268class can be instantiated from command line options, or it can be subclassed 269and the ivars programmatically set. 270 271 272lld::File representations 273------------------------- 274 275Just as LLVM has three representations of its IR model, lld has two 276representations of its File/Atom/Reference model: 277 278 * In memory, abstract C++ classes (lld::Atom, lld::Reference, and lld::File). 279 280 * textual (in YAML) 281 282 283Textual representations in YAML 284~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 285 286In designing a textual format we want something easy for humans to read and easy 287for the linker to parse. Since an atom has lots of attributes most of which are 288usually just the default, we should define default values for every attribute so 289that those can be omitted from the text representation. Here is the atoms for a 290simple hello world program expressed in YAML:: 291 292 target-triple: x86_64-apple-darwin11 293 294 atoms: 295 - name: _main 296 scope: global 297 type: code 298 content: [ 55, 48, 89, e5, 48, 8d, 3d, 00, 00, 00, 00, 30, c0, e8, 00, 00, 299 00, 00, 31, c0, 5d, c3 ] 300 fixups: 301 - offset: 07 302 kind: pcrel32 303 target: 2 304 - offset: 0E 305 kind: call32 306 target: _fprintf 307 308 - type: c-string 309 content: [ 73, 5A, 00 ] 310 311 ... 312 313The biggest use for the textual format will be writing test cases. Writing test 314cases in C is problematic because the compiler may vary its output over time for 315its own optimization reasons which my inadvertently disable or break the linker 316feature trying to be tested. By writing test cases in the linkers own textual 317format, we can exactly specify every attribute of every atom and thus target 318specific linker logic. 319 320The textual/YAML format follows the ReaderWriter patterns used in lld. The lld 321library comes with the classes: ReaderYAML and WriterYAML. 322 323 324Testing 325------- 326 327The lld project contains a test suite which is being built up as new code is 328added to lld. All new lld functionality should have a tests added to the test 329suite. The test suite is `lit <https://llvm.org/cmds/lit.html/>`_ driven. Each 330test is a text file with comments telling lit how to run the test and check the 331result To facilitate testing, the lld project builds a tool called lld-core. 332This tool reads a YAML file (default from stdin), parses it into one or more 333lld::File objects in memory and then feeds those lld::File objects to the 334resolver phase. 335 336 337Resolver testing 338~~~~~~~~~~~~~~~~ 339 340Basic testing is the "core linking" or resolving phase. That is where the 341linker merges object files. All test cases are written in YAML. One feature of 342YAML is that it allows multiple "documents" to be encoding in one YAML stream. 343That means one text file can appear to the linker as multiple .o files - the 344normal case for the linker. 345 346Here is a simple example of a core linking test case. It checks that an 347undefined atom from one file will be replaced by a definition from another 348file:: 349 350 # RUN: lld-core %s | FileCheck %s 351 352 # 353 # Test that undefined atoms are replaced with defined atoms. 354 # 355 356 --- 357 atoms: 358 - name: foo 359 definition: undefined 360 --- 361 atoms: 362 - name: foo 363 scope: global 364 type: code 365 ... 366 367 # CHECK: name: foo 368 # CHECK: scope: global 369 # CHECK: type: code 370 # CHECK-NOT: name: foo 371 # CHECK: ... 372 373 374Passes testing 375~~~~~~~~~~~~~~ 376 377Since Passes just operate on an lld::File object, the lld-core tool has the 378option to run a particular pass (after resolving). Thus, you can write a YAML 379test case with carefully crafted input to exercise areas of a Pass and the check 380the resulting lld::File object as represented in YAML. 381 382 383Design Issues 384------------- 385 386There are a number of open issues in the design of lld. The plan is to wait and 387make these design decisions when we need to. 388 389 390Debug Info 391~~~~~~~~~~ 392 393Currently, the lld model says nothing about debug info. But the most popular 394debug format is DWARF and there is some impedance mismatch with the lld model 395and DWARF. In lld there are just Atoms and only Atoms that need to be in a 396special section at runtime have an associated section. Also, Atoms do not have 397addresses. The way DWARF is spec'ed different parts of DWARF are supposed to go 398into specially named sections and the DWARF references function code by address. 399 400CPU and OS specific functionality 401~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 402 403Currently, lld has an abstract "Platform" that deals with any CPU or OS specific 404differences in linking. We just keep adding virtual methods to the base 405Platform class as we find linking areas that might need customization. At some 406point we'll need to structure this better. 407 408 409File Attributes 410~~~~~~~~~~~~~~~ 411 412Currently, lld::File just has a path and a way to iterate its atoms. We will 413need to add more attributes on a File. For example, some equivalent to the 414target triple. There is also a number of cached or computed attributes that 415could make various Passes more efficient. For instance, on Darwin there are a 416number of Objective-C optimizations that can be done by a Pass. But it would 417improve the plain C case if the Objective-C optimization Pass did not have to 418scan all atoms looking for any Objective-C data structures. This could be done 419if the lld::File object had an attribute that said if the file had any 420Objective-C data in it. The Resolving phase would then be required to "merge" 421that attribute as object files are added. 422