Build the input tree

• Goal: High-level intermediate reprensentation
• Based on command line
• ...and file system content
• Deals with positional arguments (--start-group, --as-needed)
• Nesting: linker archives contain objects
• Typed objects: object files, linker archives, shared libraries

Build fragment reference graph

• Goal: symbol resolution
• Build a graph with sections as nodes, symbol references as edges
• Traverse input tree and look for files
• If it requested OR provides a missing definition
• ...process sections and symbol table
• Linker groups: use stack, push when hitting start
• ...repeat from start as long as new undefined reference occur
• Optimize for cache locality
• Place symbol attributes and initial part of name in same cache line

Layout sections

• Goal: decide section order and final positions
• Merge sections with same name and subsections
• Drop redundant or unused sections
• Finalize symbol values
• Advantage of late layout: avoids recomputations
• Single pass for ordering and address assignment

Compute relocations

• Apply finalized symbol values to relocations
• Decide which relocations are known at link time
• ...and which are left for the run time linker
• ...or whether they can be replaced by cheaper versions
• Constant tables vs limited intermediate encoding
• Global dynamic vs initial exec TLS method

Write output

• Goal: write final binary
• Apply relocations to input sections
• Write resulting sections/segmentions
• Mix in metadata
• Use memory mapped files if possible
• ...helps page lookup table (TLB) cache
• ...improves page locality
• ...helps filesystem cache

Performance: Time and memory use

Output size

• MCLinker behaves like --export-dynamic
• Text size difference in .rodata and .dynstr

Linking GCC's cc1

Implementation status: MI

• Most basic ELF functionality works:
  • Static/dynamic linkage
  • Partial linking
  • Visibility and binding rules
  • DT_NEEDED not honoured yet

i386 and amd64

• build.sh release works
• ...using a fallback to GNU ld for parts depending on linker scripts
• TLS support incomplete: relaxation tests fail

ARM

• build.sh release builds
• ...using a few more hacks than X86
• ...parts of libc.so don't work optimized
• ...analysis is still running
• TLS support incomplete
• ARM ELF header flags problematic
• Optional system linker for Android
• No support for AArch64

MIPS

• Used by Android/MIPS
• NetBSD untested (yet)
• No support for N64 or O64