And it reminds me of John Levine mentioning in this book that the number of linker authors on this planet are just a handful (or something similar to that). No wonder, we just have this one book on the guts of linkers and loaders!
The analogy is that a linker (and an OS loader of shared libraries!) is like a compacting garbage collector – which I just wrote and spent awhile debugging, so it’s burned into my brain. My way of digesting this:
A garbage collector walks a graph of objects in memory starting from a live set / stack roots; a linker walks a function call graph, starting from main()
A compacting garbage collector produces a contiguous block of objects; A linker produces the contiguous executable (well at least the “text” portion of it).
GCs are conerned with data pages; linkers are concerned with code pages.
A garbage collector has to find edges within objects (there are several ways to do this); a linker has to find calls within functions
A leaf object has no pointers (e.g. Point {int x, int y}); a leaf function calls no others (abs() or something)
The Cheney GC algorithm is clever about the order in which objects are moved, so it can modify pointers correctly. The linker has the same issue with regard to adjusting code offsets
I don’t think it’s fair to say a linker is like a garbage collector. A linker may have a garbage collector (and that is probably a good thing for linker to have), but its purpose is to resolve symbol references.
It’s not about the linker having a garbage collector, but about the similarities in what a compacting gc and linker do. They both walk from a set of roots, trace, fix up, and move things around. The linker could also yeet dead code, but doesn’t have to. The isomorphism is the traversal.
I do not understand linkers, but the post reminded me of this book Linkers and Loaders
And it reminds me of John Levine mentioning in this book that the number of linker authors on this planet are just a handful (or something similar to that). No wonder, we just have this one book on the guts of linkers and loaders!
I treat them as a black box and don’t understand them either, but this comment on the same article gave me a bunch of insight into it:
https://news.ycombinator.com/item?id=27446341
The analogy is that a linker (and an OS loader of shared libraries!) is like a compacting garbage collector – which I just wrote and spent awhile debugging, so it’s burned into my brain. My way of digesting this:
Point {int x, int y}); a leaf function calls no others (abs()or something)I don’t think it’s fair to say a linker is like a garbage collector. A linker may have a garbage collector (and that is probably a good thing for linker to have), but its purpose is to resolve symbol references.
It’s not about the linker having a garbage collector, but about the similarities in what a compacting gc and linker do. They both walk from a set of roots, trace, fix up, and move things around. The linker could also yeet dead code, but doesn’t have to. The isomorphism is the traversal.