Linkers and Loaders (1999) [pdf]

https://www.wh0rd.org/books/linkers-and-loaders/linkers_and_loaders.pdf

by Tomte • 2 years ago

182 37 2 years ago

fractalb2• 2 years ago

I want to learn more about linkers and loaders. Can someone tell me if this is still relevant today? Any other books that are more recent?

begriffs• 2 years ago

I have a hard-copy of this book, and it seems like the PDF isn't the final version, judging by the hand drawn illustrations at least.

The book does dive into some old and arcane object file formats, but that's interesting in its own way. Nice to get a comparison of how different systems did things.

After reading that book and other sources, I examined how people typically create libraries in the UNIX/Linux world. Some of the common practices seem to be lacking, so I wrote an article about how they might be improved: https://begriffs.com/posts/2021-07-04-shared-libraries.html

Edit: That covers the dynamic linking side of things at least.

t-3• 2 years ago

The concepts are still relevant, but the specifics are mostly outdated. If you read this and then read the relevant standards documents for your platform, you should have a good grounding. I don't know of any other books that cover the topic well.

bregma• 2 years ago

Still pretty much relevant in terms of introductory understanding. Some specific details seem slightly anachronistic for the general population (segmented memory for example, which still exists in modern PC hardware but is of little import to the great majority).

Tomte• 2 years ago

A book that’s even older: http://www.davidsalomon.name/assem.advertis/AssemAd.html

monocasa• 2 years ago

Very relevant.

The big outlier not listed here is apple. Quick overview from someone who's written binary analysis tools targeting most of these:

Mach-O is the format they use, going back to nextstep. They use it everywhere including their kernels and their internal only L4 variant they run on the secure enclave. Instead of being structured as a declarative table of the expected address space when loaded (like PE and and ELF), Mach-O is built around a command list that has to be run to load the file. So instead of an entry point address in a table somewhere, mach-o has a 'start a thread with this address' command in the command list. Really composable, which means binaries can do a lot of nasty things with that command list.

They also very heavily embrace their ld cache to the point that they don't bother including a lot of the system libraries on the actual root filesystem anymore, and the kernel is ultimately a cache of the minimal kernel image itself as well as the drivers need at least to boot all in one file (and actually all of the drivers I think on iOS with driver loading disabled if it's not in the cache?).

There's a neat wrapper format of Mach-O called "fat binaries" that lets you hold multiple Mach-O images in one file, tagged by architecture. This is what's letting current osx have the same application be a native arm binary and a native x86_64 binary, the loader just picks the right one based on current arch and settings.

I think those are the main points, but I might have missed something; this was pretty off the cuff.

Someone• 2 years ago

Mach-O is built around a command list that has to be run to load the file. So instead of an entry point address in a table somewhere, mach-o has a 'start a thread with this address' command in the command list. Really composable, which means binaries can do a lot of nasty things with that command list.

ELF isn’t immune to doing nasty things at link time. https://www.usenix.org/system/files/conference/woot13/woot13... has an example where they make ping call execl on arbitrary executables as root by tweaking such a declarative table.

saagarjha• 2 years ago

I don’t disagree about the nature of load commands but Apple has been moving away from, say, LC_UNIXTHREAD for years at this point. For the most part load commands are becoming more and more similar to what ELF has, with a list of segments, some extra metadata, etc.

mzs2• 2 years ago

There was also CFM-68K and PEF for PPC before osx (also used for BeOS I think): https://developer.apple.com/library/archive/documentation/ma...

lgg• 2 years ago

Conceptually not much has changed since the book was written, but in practice there has been a lot of advancement. For example, ASLR and the increase in the number of libraries has greatly increased the pressure to make relocations efficient, modern architecture including PC relative load/store and branch instructions has greatly reduced the cost of PIC code, and code signing has made mutating program text to apply relocations problematic.

On Darwin we redesigned our fixup format so it can be efficiently applied during page in. That did in include adding a few new load commands to describe the new data, as well as a change in how we store pointers in the data segments, but those are not really properties of mach-o so much as the runtime.

I generally find that a lot of things attribute to the file format are actually more about how it is used rather than what it supports. Back when Mac OS X first shipped people argued about PEF vs mach-o, but what all the arguments all boiled down to was the calling convention (TOC vs GOT), either of which could have been support by either format.

Another example is symbol lookup. Darwin uses two level namespaces (where binds include both the symbol name and the library it is expected to be resolved from), and Linux uses flat namespaces (where binds only include the symbol name which is then searched for in all the available libraries). People often act as though that is a file format difference, but mach-o supports both (though the higher level parts of the Darwin OS stack depend on two level namespaces, the low level parts can work with a flat namespace, which is important since a lot of CLI tools that are primarily developed on Linux depend on that). Likewise, ELF also supports both, Solaris uses two level namespaces (they call it ELF Direct Binding).

Upvoter33• 2 years ago

definitely worth reading and understanding. Concepts haven't really changed.

snnn• 2 years ago

The mechanisms for Windows DLLs have been changed a lot(like how thread local vars are handled). Besides, this book could not cover C++11's magic statics, or Windows' ARM64X format, or Apple's universal2, because these things are very new. Windows now has the apiset concept, which is very unique. Upon it there are direct forwarding and reverse forwarders.

I think for C/C++ programmers it is more practical to know that: 1. The construction/destruction order for global vars in DLLs(shared libs) are very different between Linux and Windows. It means the same code might work fine on one platform but no the other one. It imposes challenges on writing portable code. 2. On Linux it is hard to get a shared lib cleanly unloaded, and it might affect how global vars are destructed, and might cause unexpected crashes at exit. 3. Since Windows has a DLL loader lock, there are a lot of things you cannot do in C++ classes constructors/destructors if the classes could be used to define a global variable. For example, no thread synchronization is allowed. 4. It is difficult to cleanup a thread local variable if the variable lies in a DLL and the variable's destructor depends on another global object. 5. When one static lib depends on another, a linker wouldn't use this information to sort the initialization order of global vars. It means it could be the case that A.lib depends on B.lib but A.lib get initialized first. The best way to avoid this problem is using dynamic linking.

For Windows related topics I highly recommend the "Windows Internals" book.

fabiensanglard• 2 years ago

Here is my modest contribution:

https://fabiensanglard.net/dc/ld.php

fractalb2• 2 years ago

Wow. That looks neat. Thanks for the link :)

elteto2• 2 years ago

This is a good book, probably still relevant but not up to date. See Advanced C and C++ Compiling [0] for a more modern treatment, including using tools like objdump, nm, and readelf to explore compilation artifacts.

[0] https://a.co/d/gckw03M

0xcafefood• 2 years ago

https://practicalbinaryanalysis.com/ may not be focused on linking and loading per se, but touches on these topics in a way that felt (to me) more lucid than the book you've linked.

elteto2• 2 years ago

Very nice! Thanks for the link.

kragen3• 2 years ago

ian lance taylor, author of gold, major binutils contributor, and one of the core golang team, wrote a book on linkers as a series of 20 blog posts in 02008, which of course also includes using tools like objdump, nm, and readelf to explore compilation artifacts https://lwn.net/Articles/276782/

levine's book was the book in the 01990s

KerrAvon• 2 years ago

Big retro revival in the 3700’s, huh?

jollyllama• 2 years ago

Has the subject matter just not changed much since a ~decade ago not to warrant new books?

fuzztester• 2 years ago

Someone ping gumby :)

https://news.ycombinator.com/user?id=gumby

He's likely to have something interesting to say here.

adancalderon• 2 years ago

This is a fun book. I remember checking it out from the NC State University Library.

qorrect• 2 years ago

Yeah this book takes me back too. It is very approachable and yeah even fun.

UncleOxidant• 2 years ago

I remember seeing this book on my boss' desk in the late 90s. I commented something like "There's a whole book on linkers and loaders?!". Turns out he was reading it because he was working on a side project that would eventually become his paid gig (he left about a year later).

ndand• 2 years ago

Steve Yegge mentions the book in the "Compilers, why learn them?" episode,

https://www.youtube.com/watch?v=o87pOVK8khc&t=1939s

"you're not done actually when you learn how compilers work you also need to learn how linkers and loaders work and you need to learn how to operating systems work before all of the magic is gone. So you really want to learn compilers and operating systems and then get this book that I have called Linkers and Loaders it's like the only book on linkers and loaders. I should have brought it and uh and it's really good"

CalChris• 2 years ago

Absolutely start with Levine. There's a lot that hasn't changed and Levine will give you a solid background in the old school. I have a hard copy and it's not going anywhere.

Next up, the Ian Lance Taylor's 20-part series. This will give you some motivation why the Levine world needed to change: performance.

https://lwn.net/Articles/276782/

Next, look at LLVM's lld and their Developer Meeting tutorials on it. There have been many but Rui Ueyama 2017 lld: A Fast, Simple and Portable Linker and Peter Smith's How to add a new target to LLD are where to start. Bluntly, Rui utterly solved/crushed/killed the linker performance problem. He probably should get an ACM Software System award but won't.

After that Oracle's (!) Linker and Libraries Guide and their Linker Aliens blog posts have a lot of gritty detail.

https://docs.oracle.com/cd/E23824_01/html/819-0690/toc.html

http://www.linker-aliens.org

mzs2• 2 years ago

The Oracle version is basically doc 817-1984 from Solaris 10, and yes it is very good.

dang• 2 years ago

Linkers and Loaders (1999) - https://news.ycombinator.com/item?id=18424233 - Nov 2018 (26 comments)

Linkers and Loaders - https://news.ycombinator.com/item?id=828638 - Sept 2009 (3 comments)

throwway120385• 2 years ago

Possessing any information on the subject makes one feel like a wizard if one is the only person on the team with such knowledge. Kind of like being able to explain which parts of the network stack are affected by the values emitted from ip route.

meindnoch• 2 years ago

Sssshhh! Don't spill the beans! I've built my house without mortgage due to knowledge like this.

chrsw• 2 years ago

Legendary book

hovav• 2 years ago

Levine's /Linkers and Loaders/ is a great book, but it's still in print, and this is an unauthorized copy.

The author's home page (https://www.iecc.com/linker/) used to host a PostScript version for download, but it no longer does, now saying: "Chapters were available in an excessive variety of formats, but are not any longer due to chronic piracy."

These days there is lots of information about linkers and loaders to be had without violating Levine's copyright; see https://www.toolchains.net/ for many links.

userbinator• 2 years ago

I suspect "chronic piracy" is an euphemism for "massive bandwidth usage".

Incidentally, the Internet Archive still remembers.

iraqmtpizza• 2 years ago

any relation to richard levine?

Linkers and Loaders (1999) [pdf]

Related Stories