Book Review: Linkers & Loaders

A Few Decades Late Book Reviews

Linkers & Loaders, by John R. Levine
Morgan Kaufmann Publishers, October 1999; 256 pages, ISBN 1-55860-496-0; $60.95

Published in 1999, Linkers & Loaders is one of the more recent books reviewed in this series. Interestingly, after more than a decade, the work is both relevant and showing its age.

The first chapter explains, among other things, that linking and relocation dates back to the 1940s and in fact predates compiled languages. On reflection, this is not surprising: linkers and loaders deal with object code and are largely language agnostic. Machine code needed to be linked and relocated even when it had been written by hand or created by simple assemblers.

The second chapter provides a broad overview of application binary interfaces (ABIs) and looks in closer detail at three architectures: IBM S/360, Sun SPARC, and Intel 386. These architectures are used as examples throughout the book, although other architectures (e.g. PDP-11) are mentioned where it is relevant.

In the third chapter, Levine presents several object formats in increasing order of complexity: DOS COM files, UNIX a.out files, DOS EXE files, relocatable a.out, ELF, IBM S/360 object format, Microsoft PE/COFF format, and finally the most baroque of all, the OMF file.

With the basics out of the way, the next four chapters explain the operation of a linker, in the order the work is performed. Those chapters are: Storage Allocation, Symbol Management, Libraries, and Relocation. Here Levine covers how a linker collects and orders code and data segments; how symbol resolution is performed; how libraries are searched; and how relocations are applied to create an output image.

Along the way, the author explains the concepts of common blocks, name mangling, and weak externals. Several common library formats are also presented.

The eighth chapter is dedicated to loading. It covers load-time relocation and explains the need for and implementation of position-independent code, with its advantages and drawbacks. The time-honored though mostly obsolete concept of overlays is also explained.

The remaining chapters cover more advanced (and optional) linking and loading techniques. Shared libraries are presented in chapter nine, with emphasis on static shared libraries implemented on COFF UNIX systems, BSD/OS and early Linux.

The following chapter delves into dynamic linking and loading. Most of the space is devoted to ELF dynamic linking, with details of PLTs (Procedure Linkage Tables), GOTs (Global Offset Tables), and dynamic loading. Microsoft dynamic libraries (DLLs) are also covered and major differences between ELF and Microsoft dynamic linking are explained.

The eleventh and final chapter explains some of the less widely used linker techniques developed to deal with C++, as well as various link-time optimizations. The Java linking model is also mentioned.

Linkers & Loaders is a well written, clearly laid out book. It is structured in a very logical manner, first explaining the need for linking and the environment it exists in, then covering basic linker operation, and continuing to optional/advanced linking techniques. Numerous examples refer to common programming languages, file formats, and hardware architectures.

The book does not explain how to use a linker and deliberately makes very few references to specific products. Instead, it explains why a linker is needed and what exactly it does. Numerous historical references elucidate the evolution of linkers and loaders and may answer certain questions that are otherwise difficult to find answers to (what’s the deal with ranlib? what was lorder/tsort for? why the underscores decorating symbol names? etc.).

Even veteran programmers may find the book valuable as it covers a broad spectrum of platforms, clearly reflecting the author’s extensive experience. UNIX, Windows, and IBM S/360 are emphasized throughout the book as representatives of widely used yet significantly different platforms.

An updated edition of Linkers & Loaders would have to cover the AMD64 architecture, and would also probably mention OS X object formats and dynamic linking. However, the bulk of the book is just as relevant today as it had been when it was first published.