P2A

MCLinker - the final toolchain frontierJörg Sonnenberger
March 16, 2013

Abstract
LLVM and Clang provide the top half of an integrated BSD licensed cross-platform toolchain. The
MCLinker project implements the remaining parts.
It is compact, modular and efficient. Currently
supported platforms are ELF systems running X86(32bit and 64bit), ARM and MIPS. MIPS64 andHexagon are work-in-progress.

1Introduction

Following the GPL3 announcement of the Free Software Foundation, the LLVM project gained a lotof traction. The Clang front-end allows replacing GCC for C and C++ code on many important platforms. The Machine Code layer provides
an integrated assembler, replacing the dependency
on external assemblers for most situations. The
combination provides a powerful toolchain with full
support for cross-compilation. For a long time,
the only major component missing to replace GNU
binutils has been a linker. This gap is now filled by
the Machine Code Linker (MCLinker) project.
This paper first introduces the architecture ofMCLinker and compares it to GNU ld. The performance for linking large programs is evaluated andcompared with GNU ld and Google gold. A detailed status report of the implementation is presented as well as list of future projects.

2Architecture

MCLinker is a modern, modular linker. It is designed to process input in three separate phases:• Building the input tree based on command line
and implicit default values.
• Resolve symbols.
• Determine output positions, apply relocations
and write output files.
GNU ld doesn’t have a clear phase separation;individual steps are re-applied iteratively until all
input files are processed and all resolvable symbols
are resolved. The result is complicated and cacheunfriendly code.

Google gold on the other hand mixes the first twophases. Symbols that can’t be resolved in the firstround are retried later. This choice improves themaintainability of performance of the linker code,
but is still more complicated than the design ofMCLinker. It is useful to note that gold supports
multi-threading during the relocation processing tospeed up linking large input sets.

2.1

Input tree

The input tree is the first intermediate representation (IR) used by MCLinker. It contains vertices
for every input file and all positional options. Positional options are options like –start-group or –asneeded that change the handling of a subset of theinput files. Input files can form subtrees, e.g. linker
archives form a subtree with a child node for everyarchive member. Edges in the input graph are either positional relationships for options or inclusion
links for archives.

2.2

Symbol resolution

Symbol resolution is implemented using tree iteration. As result of symbol resolution, the low-level
IR is created: the fragment reference graph. Thisgraph represents the individual sections found during input process and the symbolic dependencies
between them.
The input tree is traversed and for every input
file it is checked whether it must be included in theoutput. An input file is included if it was explicitly
mentioned on the command line or if it provides
a definition for a currently undefined symbol. If
the input is to be included, its sections and symbol
table are processed. When the tree iteration hits
the start of a linker group, the current position ispushed onto a stack. Iteration continues until thecorresponding end is seen. The linker now checks ifany new undefined reference was found while processing this group. If so, the process starts again
from memorized position.
The data structures used for symbol resolution
are highly optimized to maximize cache locality.
The symbol attributes and the initial part of thename share a cache line on modern CPUs. This
helps the CPU when linking large programs with

P2A

many smaller functions; C++ applications are wellknown for such characteristics.

2.3

Layout

The layout step is the first part of the last linking
phase. It is responsible for deciding what sections
should be written in which order and to what position. It merges sections as necessary or drops them,
if they are redundant (e.g. multiple inline definitions for C++ methods). At the end of this phase,the symbol values are finalized.
Defering the section merging until such a latestep in the linking process has the advantage of
avoiding many redundant computations. The listof all input sections is known at this point and after a single ordering pass, addresses can be assigned
directly.

2.4

Relocation

The resulting binaries have the following size:
MCLinkerGNU ld
goldllvm-tblgen.text
2,123,527
1,827,773
1,786,483
.data
2,408
2,664
2,520.bss
5,360
5,912
2,520
clang
.text 34,299,746 26,917,022 26,698,448.data
21,984
22,112
22,112.bss
47,62447,73647,704
Both MCLinker and gold are significantly fasterthan GNU ld. MCLinker is clearly pulling in too
many objects, which is responsible for the muchlarger binaries. This is likely also reponsible fora good part of the performance difference to gold.
Evidently, further analysis is needed.
Of special interest for embedded use isthe memory footprint of the different linkers:
MCLinker
GNU ldgold
llvm-tblgen 17,508KB 17,700KB 17,528KB
clang
176MB
150MB
182MB
The peak Resident Memory Size shows clearly
that both MCLinker and gold are optimised for inmemory processing. Since they are reading the fullsymbol tables of all input files first, they require
more memory.

The relocation step follows the layout step and is responsible for determining the symbol values in thevarious places that reference the symbols. It may
prepare to modify the instructions to replace morecostly code with simpler sequences. This helps
platforms with limited immediate value ranges like
Implementation status
ARM and MIPS to load short (relative) address di- 4
rectly instead of using constant tables. It can also
be used to use more efficient access methods for Linker functionality falls into two categories. The
first is generic features like symbol versioning which
Thread Local Storage (TLS).
are handled in the platform independent core. The
second is features specific to a target platform likethe handling of the different relocation types.
2.5 Writing
Once the relocation step is done, all that is left isapplying the relocations to the input sections andwriting the result to the output file with any metadata necessary for the file format. MCLinker aggressively uses memory mapped files when possible.
This leverages the page lookup table (TLB) cacheand improves page locality. It helps improves theuse of the OS file system cache.

3Performance

To measure the performance of MCLinker, thellvm-tblgen and clang binaries were built using thenormal options in NetBSD (-O2, no -g). The final linker invocation was repeated using MCLinker,
GNU ld and Google gold. For MCLinker the current development version of March 11 was used.
GNU ld and gold are both from GNU binutils
2.22.90.
MCLinker GNU ldgoldllvm-tblgen
0.05s
0.10s 0.04s
clang
0.69s
1.41s 0.44s

4.1

Platform independent

Most features necessary for ELF systems are implemented. This includes static and shared linkage
as well partially linking objects to form a new relocatable object. Weak symbols are overwritten bystrong definitions. The different visibility types arehandled. Missing for shared libraries is the processing of DT NEEDED entries and loading the symbols of the referenced objects. This means that currently only symbols in libraries explicitly requestedon the command line are found, when standard
ELF behavior is to recursively scan libraries andtheir dependencies. This omission is not absolved
by recent versions of GNU ld switching to the same
broken semantic.
C++ requires constructor and destructor support. The compiler uses .ctors or .init array sections (or .dtor and .fini array for destructors) toimplement this. MCLinker has full support for either form. It doesn’t try to convert one mechanism into the other due to the slightly different
ordering rules. Support for COMDAT-sections isP2A

present. This allows defining the implemention ofa function in more than one object file and letting the linker pick one. It is used for implicit
template specialisations. The .eh frame sections
necessary for exception handling are correctly processed and the associated .eh frame hdr section iscreated. The latter provides a fast binary searchtable to reduce runtime overhead. One issue in thisarea is the missing support for relocations into the.eh frame section. This is needed for support theolder register frame info style shared library interface.
The platform-independent part of TLS support
is present. This concerns the proper merging of
the .tdata and .tbss sections and the correspondingsegments.
Support for symbol versioning is missing. ForNetBSD, it is only used by libgcc at the moment, so
it is primarily an issue for missing MCLinker builds
with non-MCLinker ones. It is far more importantfor FreeBSD though.
Linker scripts are required in certain situations
that need more granular control over the image layout. For NetBSD, this concerns RUMP and thekernel. It is planned to add this feature during thesecond quarter of 2013.
Support for other binary formats like Mach-O isplanned, but not implemented.

4.2

NetBSD/i386

NetBSD/i386 needs a few workarounds for the lackof linker scripts. With a fallback to using GNU
ld, a NetBSD release build can be finished. The
result works well with few regressions seen in theATF testsuite results. The only remaining platform
specific issues is the incomplete support for TLS relaxations, i.e. converting dynamic TLS relocations
into faster relocations for the main binary.

4.3

NetBSD/amd64

AMD64 is the youngest platform supported byMCLinker; the initial changes were added by
H.J. Lu in early February. It is still maturing.
NetBSD/amd64 shows the same issues as NetBSD/i386 and has some additional problems with certain relocation types. At the time of writing, thisprimarily affects libc and libstdc++.

4.4

ARM and MIPS

ARM and MIPS are the original platforms for mostof the MCLinker work. Since last year, it is possible
to build a full Android system on those platforms.
NetBSD has not been tested yet though. Support iscurrently limited to the 32bit variants of the ARM
and MIPS ABIs.

5Future work

The biggest priority for the MCLinker project is tofinish the missing platform independent features.
This means adding symbol versioning and linker
script support. Another important item is support
for Link Time Optimisation (LTO). Open researchquestions include the impact of fine-grained layout
decisions by creating individual sections for every
function in the compiler and letting the linker figureout the best placement.
Support for the alternative 32bit ABI on X86(X32), MIPS64 and Hexagon is work-in-progres.

6SummaryMCLinker provides a cross-compiling friendly linker
for many platforms targetted by the BSDs. It ismaking huge progress towards fully replacing GNU
ld on i386 and AMD64 for NetBSD, with a similarstate easily reachable for ARM and MIPS. A GPL
free toolchain is within reach now.