A look at dynamic linking

The dynamic linker is a critical component of modern Linux systems, being responsible for setting up the address space of most processes. While statically linked binaries have become more popular over time as the tradeoffs that originally led to dynamic linking become less relevant, dynamic linking is still the default. This article looks at what steps the dynamic linker takes to prepare a program for execution.

Invoking the linker

When the Linux kernel is asked to execute a program, it looks at the start of the file to determine what kind of program it is. The kernel then consults both its built-in rules for shell scripts and native binaries and the binfmt_misc settings (a feature of the kernel allowing users to register custom program interpreters) to determine how to handle the program. A file beginning with "#!" is identified as the input of the interpreter named on the rest of the line. This faculty is what lets the kernel appear to execute shell scripts directly — in reality executing an interpreter and passing the script as an argument. A file starting with "\x7fELF", on the other hand, is recognized an an ELF file. The kernel first looks to see whether the file contains a PT_INTERP element in the program header. When present, this element indicates that the program is dynamically linked.

The PT_INTERP element also specifies which dynamic linker the program expects to be linked by — also called the interpreter, confusingly. On Linux, the dynamic linker is usually stored at an architecture-specific path such as /lib64/ld-linux-x86-64.so.2. It is not allowed to itself be dynamically linked, to avoid an infinite regress. Once the dynamic linker has been found, the kernel sets up an initial address space for it in the same fashion as any other statically linked executable and gives it an open file descriptor pointing to the program to be executed.

Relocation

The dynamic linker's job is to arrange for the process's address space to contain both the main executable itself, and all of the libraries upon which it depends. For modern executables, that almost certainly means loading position-independent code, which is designed to be run from a non-fixed base address. Many parts of the code do still need to know where the different sections of memory are located, however, so position-independent executables contain a list of "relocations": specific places in the binary that the dynamic linker needs to patch with the actual address of various components in memory. In most programs, the majority of relocations are patches to the Global Offset Table (GOT), which contains pointers to global variables or loaded sections and link-time constants.

Giving the dynamic linker the flexibility to load different components at different addresses serves several purposes. The oldest form of position-independent code was on architectures where memory addresses were accessed relative to a base register, allowing for multiple copies of a single program to reside in memory at different addresses. The invention of dynamic address translation obviated that motivation. Modern toolchains use this flexibility for address-space layout randomization (ASLR), by allowing the dynamic linker to add an element of randomness to the chosen locations. Statically linked programs with position-independent code, including the dynamic linker itself, are loaded at a random address chosen by the kernel. Therefore, the first major task of the dynamic linker is to read its own program header and apply relocations to itself. This process includes patching the subsequent code with the location of global structures and functions — prior to applying these relocations, the linker is careful not to call any functions from other compilation units or access global variables.

Once the dynamic linker has applied relocations itself, it can then perform OS-specific setup by calling the functions for its particular platform. On Linux, it calls brk() to set up the process's data segment, including allocating some space there for its own state, and informing malloc() to put allocations in the newly-allocated space (which is separate from the program's eventual heap). At this point, malloc() refers to a temporary implementation, which cannot even free memory, that is used while the dynamic linker is identifying and applying relocations to necessary dependencies.

The first step in identifying dependencies is to set up the link map — the structure that records information for use by dlinfo(). Once that is done, the dynamic linker finds where the kernel mapped the vDSO, a shared object includes code that can service some system calls without needing to switch to the kernel, a technique that is most often used for the gettimeofday() system call. The dynamic linker places the vDSO in the link map, so that the same code that handles linking other dependencies can handle shared objects that call into the vDSO.

By this point, it may seem as though the stage is set to actually read and link the shared objects upon which the program depends, but there is one more step to complete. Users can override functions at run time by specifying shared objects in the LD_PRELOAD environment variable. Overriding functions in this way can be used for many purposes, such as to debug an application, to use an alternate allocator such as the Boehm-Demers-Weiser conservative garbage collector or jemalloc, or to fake the time and date for the application using libfaketime, for example. The dynamic linker resolves preloaded libraries first, so that when it is linking later libraries it can direct them to the overridden function definitions in one pass.

Now the dynamic linker has everything that it needs to finish arranging the address space of the program. Starting with the program being loaded, the linker looks for DT_NEEDED declarations in the program's header, which indicate that the program depends on another shared object. The linker searches for these DT_NEEDED declarations recursively, building a list of all shared objects that will be required by any of the program's transitive dependencies. DT_NEEDED entries can include absolute paths, but they can also include relative paths that are resolved by consulting the directories in the LD_LIBRARY_PATH environment variable, or a default set of directories. The dynamic linker then traverses this list of dependencies backward, so that a shared object's dependencies will be loaded before it is.

For each shared object, the linker opens the resolved file, loads it into a newly allocated (and, with ASLR, random) location in the address space, and then performs the set of relocations listed in the shared object's header. Then it adds the shared object to the link map.

The exception is the dynamic linker itself. Programs are allowed to depend on the dynamic linker as a library, to supply functions such as dlinfo(), but the linker would be broken if it applied relocations to itself in the middle of the loop, so it excludes itself from the dependency list. As described above, it has already applied relocations to itself. But the linker occasionally makes use of functions that can be overridden by preloaded libraries. Therefore, once all of the program's dependencies have been slotted into the address space, the linker applies relocations to itself one final time, so that now it will refer to the overridden version of any functions it uses. Now the malloc() implementation that the dynamic linker uses switches from the simplified implementation used so far to the generic implementation used by the rest of the program.

With all the shared libraries loaded, the dynamic linker has completed most of its work. Before jumping to the main program, however, it sets up thread-local storage (TLS) and performs any initialization required by the C library. Then it restores the state of the program's arguments and environment that the kernel supplied and jumps to the entry point of the program.

User code

One might expect that the duties of the dynamic linker end where the main program begins, but this is not so. Not only must it service requests to dlopen() new shared objects that are required at run time, but there is one more part of the dynamic linker that runs during the lifetime of the loaded program: updating the Procedure Linkage Table (PLT).

While programs could simply use relocations to directly patch CALL instructions in the text of the program, "text relocations" like this cause two performance problems. Firstly, since the number of relocations required would depend on the number of calls to the given function (which may be large), the initial application of those relocations to a shared object can be slow. Secondly, since text relocations involve dirtying the pages of memory containing a program's executable code, different processes running the same program can no longer share the same underlying memory, increasing the memory usage of the program. These performance problems mean that text relocations are largely frowned on by the maintainers of dynamic linkers.

Modern compilers and linkers work around this problem by creating a PLT — a special standalone section that contains an indirection for each externally defined function. Calls to these functions from within the program are compiled to a call to the PLT, which then contains a jump to the real location of the external function. The PLT could also directly use text relocations, but most architectures instead use indirect jumps through function pointers stored in a second GOT (separated from the program's normal GOT in its own section called ".plt.got"). Separating out the function pointers is useful on architectures that have no way to compactly encode a direct jump to an arbitrary part of the address space, but it is also useful for one final performance trick: lazy linking.

Unlike with relocations that point to data, which need to be resolved before the program starts running because the dynamic linker cannot know when they will be accessed, the relocations in the PLT's GOT don't need to be applied immediately. The dynamic linker initially fills the PLT's GOT with the address of a function from the dynamic linker itself. This function consults the link map to determine where the external symbol in question is located, and then rewrites the corresponding entry of the PLT's GOT. Linking is only performed for external functions that are actually called, and only once the program has started up. For most programs, this improves performance and makes the initial startup speed of the program faster.

Lazy linking can be turned off using the LD_BIND_NOW environment variable, or by compiling the program with the "-z now" linker option. As of the new glibc release, version 2.39, glibc's dynamic linker also supports rewriting elements of the PLT to use direct jumps instead of indirect jumps, on systems where that would have a performance benefit. The article covering the announcement claimed that the introduction of PLT rewriting was security-motivated, but a commenter pointed out that the existence of the former two methods suggests that PLT rewriting is mostly useful as a performance-tuning setting. There is one security benefit of disabling lazy linking, though: it permits "Relocation Read-Only" (RELRO), a security mitigation where the dynamic linker remaps the GOT (and the PLT's GOT) as read-only once they have been filled out, preventing an attack from overwriting them to gain control of the process's control flow.

The dynamic linker is largely invisible to most programs, but it performs a critical role in establishing the address space of every process. Most programmers will never need to interact with the exact process by which it sets up a program to be run. However, the dynamic linker's apparent stability belies a surprising amount of complexity required to ensure that programs can be prepared for execution efficiently.