I wrote a linker everyone can understand
briancallahan.net
briancallahan.net
A linker in first approximation just concatenates files.
In second approximation, it splits every input file into N parts (code and data, basically), then concatenates the corresponding parts in each input file, and writes all concatenated parts ("sections") to the output file.
It needs to fix up references at the end and it needs symbols for that, but that's kind of an implementation detail.
Even diagnosing duplicate symbols is a convenience feature if you look at things this way.
Symbols become more important if you want to write a "real" linker that supports weak symbols and symbols imported from dynamic libraries. But for the understanding the basics, it helps to deemphasize symbols, in my opinion.
This description is a reverse process of how the linker goes through and does all of it: first it loads all the input files, then resolves the symbols to build a link plan, then it fixes up necessary relocations, and finally it streams it all into the output file. I don't think it helps to omit any part of the process from the description--symbols are not "kind of an implementation detail," they are a core feature of what linkers provide.
Indeed, if I were to provide this as a blog post, I see no reason to not immediately reach for describing this using the full complexity of ELF and "real linkers" as the basis of description. You don't really gain anything from a simpler description, and building a linker that can build even relatively complex libraries such as glibc or Firefox's libxul is likely to be pretty simple--the really hard part of linkers is supporting things like linker scripts, which is not common operation.
A simple linker doesn't need symbols for a link plan, or even a link plan (assuming you just load all input files and ignore static library indices). It doesn't even need a symbol table, it can do a full scan of all input files every time it needs a symbol during relocation processing. The symbol table is just a performance optimization.
Again, this changes for a real linker with weak symbols, comdats, section gc, etc.
I baselessly claim that a simple linker that doesn't need to read elf can be < 200 lines :) If you want to do elf, I think that becomes difficult.
Chapter 6
http://people.inf.ethz.ch/wirth/ProjectOberon/PO.System.pdf
Or the re-implementation of Turbo Pascal one for MS-DOS,
'collect1' collects pairs of (name, address) and puts it in a table called 'collect'. Then 'process1' finds any names and substitutes the address found in the 'collect' table.
A GC has a series of roots which point at blobs of memory. The GC needs to understand where further references are located in the pointed memory; a simple GC follows these references, avoiding cycles, until it has traced through the live set. It calculates new addresses for each blob of memory, then goes through the live set a second time, moving each object into its final position and adjusting all the references to point to their final locations.
A linker starts out with a main() function or equivalent which is a blob of code, contained in an object file produced by the compiler. The object file contains a table of references to all the external symbols used by the code, as well as the locations in the code that the references are made, classified by type of reference (e.g. absolute vs relative references). The references in the main() function are like the set of GC roots. The object file also contains a table of exports, all the symbols which it exposes externally.
The linker then locates the object code or data for each unresolved external reference (in other object files supplied on the command line, or in archive library files - indexed concatenations of object files). This process is followed recursively until the live set - the set of blobs of code and data - to be assembled into the final executable is determined.
Once all these blobs have been found, they can be copied into the final executable, and all the references to symbols can be filled in with appropriate offsets. There's details here: relative offsets may be baked in, but the locations of absolute offsets need to be marked in the final executable so that the operating system loader can adjust them if it needs to load the executable somewhere other than its preferred address.
The operating system loader is itself a linker. It, too, needs to follow a similar process, but instead of object files, it's dealing with shared objects (DLLs in Windows), and it's chasing down external references, loading things, and adjusting offsets as necessary (address space layout randomization (ASLR), load address conflicts (a lot more common in 32-bit address spaces)). The OS loader can also be lazy; instead of resolving a reference, it can fill it with a stub which is only resolved on first call. This delays linkage failures, but if the application tests for versions etc. before invoking, the developer gets the ergonomics of early bound linking with the features of late-bound linking that would otherwise need manual use of dlsym / GetProcAddress.
If you're interested in the topic, I highly recommend Linkers and Loaders by John Levine, long-time moderator of comp.compilers.
Smart linker relates to eliminating dead code. Depending on how symbols are packaged, or how well the compiler is integrated with the linker, there's a risk of including private (i.e. non-exported) code/data in the final executable which is never referenced but is simply co-located with code or data which is linked in. But it's not really a technical term, it's a marketing term from Delphi.
Like 'optimising compiler' - are there really any non-niche compilers that do not optimise? Maybe some first-tier JITs.
Linkers have more scope for smartness. The size of a block of code can be quite sensitive to the addressing mode (near vs far for e.g. 16-bit x86, relative offsets of various widths vs absolute etc.) used for each reference. An intelligent linker can adjust the code depending on where the target ends up, altering the addressing mode. The scope for optimization here depends on the ordering in the final executable, density of references and so on.
static int foo(void) {
return 4;
}
int bar(void) {
return 42 + foo();
}
(I can't answer your question in detail because it's been a long time since I've been poking around in object files and I don't know what C/C++ compilers and linkers have been doing with them recently. I was a compiler engineer at Borland for more than 5 years, but it was years ago.)
> Another downside is that you do have to arrange the object files in the command line in an order that makes sense for this linear approach. The first object file must be the entry point of the program. Different arrangements of object files may work for linking your executable but will produce an organizationally different executable. You may or may not care about this.
[chapter1]\s\e\e\ {chapter2}\ \f\o\r\ \m\o\r\e[chapter2]\g\o\ \b\a\c\k\ \t\o\ {chapter1}
And arguably, it kinda makes more sense than trying to quote the { and [ instead: you've already lost the ability to just copy a blob from one file to another with a couple of places patched at known offsets, so you may as well simplify your life further.
It somehow hurts my brain to almost double your file size, but who cares? That's the computers problem, not yours.
"I wrote a linker that works!" -> No-one can understand all of it.
As for interesting stuff... relative jumps are normally not used for jumping to a symbol defined in a different object, and base address computations are trivially supported by sticking a special symbol at the beginning of every object file.
So the OP wrote a linker. But did they write one which understands linker script? Does it understand shared libraries, multiple architectures, multiple object file formats, ...? Is it 'smart'? Can it link itself? Does it support zero pages, ASLR, non-executable stacks+heaps? Is it fast?
Linkers are hard. Relocs and fixups are really hard. The Oracle® Solaris 11.4 Linkers and Libraries Guide is 500+ pages [1]. But if the development environment is done well, you won't have to worry about that, which is pretty cool.
[1] I always wanted a Linker Alien t-shirt.
It's also a breath of fresh air in an industry whose practitioners can't distinguish technology from magic.
And sadly often don't want to. My biggest pet peeve is helping someone figure out a bug, and when I see the problem and start explaining what's happening they give me some sort of "I don't want to know about all that, just tell me how to fix it!" response. If you want to spend my time to learn something so you can contribute to the project better - cool I'm in as along as it takes. If you just want to use my knowledge and time so you can work less - fuck off, I have my own deadlines for my own work.
First, who said "everyone" here refers to the "layman"?
How does this handle endian, word sizes, and dreaded alignment? Is packing enough?
* { background: #fbfcff; }
Disabling that rule or using reader mode helps to read the article.
> * { background: #fbfcff; }
You also say:
> ... makes everything (including text) almost white.
Doesn't that rule just force the background to (nearly) white? Why do you say it forces everything including text to white?
This elitist UI thing of forcing deliberately blind schemes is trash