Overview

A program must be:

  1. Written - this is done using an editor. The result is a text file.
  2. Compiled - translate the text file into a sequence of codes that the machine (or virtual machine) can understand and execute.
  3. Linked - the program might make use of other programs, or libraries of programs. These must be brought together with the program and the interconnecting references resolved.
  4. Loaded - the combined program must be moved into memory. In doing so, there must be addresses assigned to the data and instructions.
The linking and loading are accomplished by a program which is variously called the linker, or the loader, or the linking loader. Although linking and loading are conceptually separate, it is exceedingly common that a single program combine those function. So "linking" and "loading" mean the same thing, when speaking informally, although they are separate actions. In unix systems, for instance, its name is ld, suggesting the word loader, but the man page says linker. The linking-loader is so fundamental that I doubt your system will boot without it. Windows, in fact, builds the linker into the operating system.

The linking/loading can be further broken down in function:

  1. Placement: figuring out where things should go, selecting addresses, or type of memory regime (stack, BSS, heap or text).
  2. Symbol management: keeping track of the names of variables and functions for use by other programs (exporting) or finding functions and variables for use by this program (importing).
  3. Relocation: modifying the compiler's results according to the placement.
  4. Fixups: modifying the compiler's results according to the resolved external symbols.

The files processed by the linking loader have a certain format. These have evolved over the years as the demands on linkers have become more sophisticated. For instance, to save memory, libraries are now shared, and earlier file formats did not support shared libraries. In Windows, the libraries, shared or otherwise, are called DLL's. In unix, they are either .a files or .so files. Dot-so are "shared objects", whereas the Dot-A files are "archives", and are sort of non-shared objects.

In short, windows using a PE format, called Portable Execution, and modern unix uses an ELF, Executable and Linking Format, format. OSX uses Mach-O format (macho?). These all descend from unix's first format, which is generally called "a.out", after the default name of the output of the standard unix compiler. [On checking with bwk, a.out would be short for "as output", the assembler being "as".] From this decended COFF, Common Object File Format, which PE adopted with amendments, but unix abandoned for ELF.

In unix, the loader ld is invokable from the compiler, cc, so rarely does one become aware of it as a separate program. As is typical, only when there are problems is it of interest.

Shared libraries, digression on linking/loading

Libraries can also be shared in this manner. If the libraries are pure code, and read-only, there is no security danger of processes affecting each other through manipulation of the library code. However there is a complication if the libraries are not mapped to the same virtual addresses in every process. There might be absolute address reference in the library, and this absolute address must be correct when the code is run in each of the process virtual address spaces. For instance, the library might call a subroutine by the entry point address.

The solutions are either to map the library at the same address, or to otherwise employ position independent code (PIC). Microsoft does not support PIC and therefore shared libraries, known in Microsoft as DLL's, are carefully pre-bound to specific addresses, known throughout all of the kingdom of Microsoft. These are also known as the shared DLL's. This method can only take you so far, but it works well for all the major DLL's.

Position independent code runs no matter where it is located. It can employ relative rather than absolute addressing. Although the code is located differently in each address space, locations within the library maintain the same offsets from each other. Addressing using these offsets is called relative addressing, and it is one component of PIC. Another is to collect up all absolute addresses into a table, and within the code reference the variable by its location in the table. Then by having a separate copy of the table for each address space, the table can be filled out with the absolute addresses appropriate for the space. This occurs across most unix variants and is called the global offset table (GOT).

The GOT solves the problem of shared libraries. It could be used to record the absolute addresses of both proceedures and code so that the library can refer to those locations in an position independent way. However, for functions, an additional mechanism is used, the procedure linking table (PLT). This is not so much a table as a vector of jumps. The jumps include pulling the target of the jump from the GOT. A call to one of these vectors is therefore like calling the procedure whose address is found in the GOT table.

In this case, it is preferable to call the PLT, rather than having the code use the GOT directly. The GOT table initially does not have the address of the target function. Instead, it has the address of a loading routine which will look up the target function's address, and replace that address in the GOT table. Therefore, a function is not linked in until the first time it is called; and once called, future calls to the PLT will directly jump to the target function.