Join us on Facebook!
Join us on Facebook!
— Written by Triangles on November 15, 2020 • updated on November 18, 2020 • ID 85 —
Understanding the complexity behind 3rd-party code. On Windows, Linux and macOS.
Writing modern software often means to glue existing pieces together, rather than reinventing everything from scratch. The task can be trivial or full of intricacies, depending on the tools and the platforms you are working with. In this article I want to investigate such art of reuse in C and C++ languages, from a technical point of view.
A library is code designed to be reused by other programs. It is made of one or more human-readable header files that contain the declaration of variables, functions, classes and other programming elements that the library provides. The actual implementation lies in a precompiled binary, distributed along with the headers.
The library header is included in the source code of any program that wants to make use of it: the inclusion informs the compiler about the library content. Then, during the compilation stage, the binary part gets somehow connected to the final executable.
A library is just normal C or C++ code written by a human and then compiled with a compiler, except for the absence of main(), the entry point function called when a program is executed. Libraries are plugged into existing executables where the main() function is already present: adding it twice would screw up the whole program and prevent a correct execution.
Let's pretend you have a library called GraphicLib that contains a single function drawPixel(int x, int y). The library is designed to paint black pixels on screen and is already installed somewhere in your system. A minimalistic C or C++ program that makes use of it would look like this:
#include <GraphicLib.h>
int main()
{
drawPixel(0, 0);
return 0;
}
In words: you first include the library header file, then you invoke the function drawPixel(0, 0) that comes with the imported library. The snippet above is ready to be compiled into an executable. In C and C++ the operation is split into two parts: the compilation stage performed by the compiler and the linking stage performed by the linker.
During the compilation stage, the compiler transforms your source code into machine language. More specifically, it turns each source file into an object file: a file that contains machine code, not yet executable. When the drawPixel() function is processed, the compiler is unable to find a proper definition — that is the actual source code — and so it realizes it must be somewhere else. Indeed, the drawPixel() function implementation lies in the library's precompiled binary. The compiler doesn't mind this and it just marks the function as undefined in the object file.
During the linking stage, the linker is responsible for gathering all the object files together in a single executable. The linker also has to find what has been marked as undefined by the compiler. Normally you need to instruct it where to search, by passing it the full path or the name of the library that contains the missing definition. If the linker is unable to find a missing piece, an error is thrown and the compilation stops, typically with a message like undefined reference to 'drawPixel'.
The nature of the library determines how the linker connects it to the final executable. Compiled libraries come in two flavors: static or dynamic. Each format has advantages, drawbacks and differs in how it is handled during the linking stage. Let's dig deeper.
A static library is simply a collection of binary objects archived into a single file, usually with a .a extension on Unix-like systems and .lib on Windows. A static library gets merged by the linker into the final executable during the linking stage. More specifically, the linker copies all the elements marked as undefined by the compiler from the library into the executable file.
Static libraries are good for portability: your program contains everything it needs in a single executable file, which is easier to distribute and install for the end user. On the other hand, the program grows bigger. Historically, libraries could only be static.
A dynamic library (also known as shared library) is a slightly more complex creature. It contains binary data like a static library and has a .so extension on Linux, .dylib on macOS/iOS and .dll on Windows. A dynamic library is designed to be linked to the main executable, rather than being merged into it. The linker creates a special connection between functions and variables used in the main executable and their actual implementations provided by the dynamic library. This way multiple programs can reference to the same library without the need for each to have its own copy.
Using dynamic libraries results in a smaller final executable, as it doesn't contain the actual library code. Also, if the library is updated, all programs that link to it will instantly benefit. Conversely, a program that uses static libraries needs to be recompiled every time a new version of the library is published in order to merge the changes into the final executable.
This is an important property when it comes to security: bugfixes in a dynamic library will automatically propagate to all programs that link to it, with no need to recompile. Unfortunately this mechanism makes the whole program more susceptible to breaking: what if the library changes in a way that is no longer usable by the executable? I'll investigate this problem in the final paragraphs of this article.
Let's pretend to stop the compilation of the GraphicLib example above, right before the linking stage. We would end up with the object file generated by the compiler, not yet ready to be executed. As said before, such file contains a missing function that the linker has to find somewhere. How does that information look like exactly?
A compiled program is essentially a long list of machine code instructions. The processor doesn't care about human-readable names for functions and data such as drawPixel: it just needs their address (that is, the offset within the file) and their size, in order to process and execute them. Unfortunately this is not enough for the linker to do its job of gathering the pieces together. The linker can't locate a function called drawPixel if everything it has is just a bunch of hexadecimal addresses.
For this reason, compilers include symbols in their object files. A symbol is a human-readable name given to functions and data that come with a program. For example, drawPixel could be a symbol for the drawPixel(int x, int y) function. Symbols are used by the linker to search for undefined stuff marked by the compiler: if a symbol is found somewhere — for example in an external library, the linker can continue its collage job.
Operating systems provide tools to list symbols in object files, for example nm on Linux and macOS or dumpbin.exe on Windows. I'm on Linux right now, so running nm on our hypothetical object file would spit out something like this (output truncated to the interesting part):
...
000000000000001c T main
U drawPixel
...
The nm output is tabular data formatted as follows:
[address] [flag] [symbol]
In words, the object file contains two symbols: main and drawPixel. The first one has been found by the compiler — the T flag means the symbol exists — and has a specific address. This is pretty obvious, as we have defined the main() function right in the source code. Conversely, the drawPixel symbol has been marked as undefined (U flag) because the compiler couldn't find the implementation. As you can see there's no address for it yet.
The linker's job is to parse the object file for any undefined symbol and find a suitable definition in the library you have passed it as a command line parameter. This process is called symbol resolution and depends on the type of library in use. Another step called symbol relocation is needed to give each copied symbol definition a correct and unique address. This is necessary as symbol addresses start from 0 in static and dynamic libraries: symbol relocation is the act of adjusting them to fit properly into the final executable.
With static libraries, the linker searches inside the library's precompiled binary for the matching symbol: if found, the symbol definition (i.e. the source code) is copied into the final executable. Assuming GraphicLib is a static library, running nm on the final executable after symbol resolution + relocation would yield something like this:
...
000000000000001c T main
0000000000001135 T drawPixel
...
The drawPixel symbol is now defined (T flag) and has a proper, unique address.
With dynamic libraries, the linker only performs symbol resolution: relocation is deferred when program is launched. When a symbol is found, the linker just records its name and the library it comes from inside the final executable. Running nm on it would yield the same initial results:
...
000000000000001c T main
U drawPixel
...
As you can see the drawPixel symbol is still undefined. The additional information stored by the linker can be extracted with tools like readelf on Linux, gobjdump on macOS or dumpbin on Windows: they are used to peep inside a binary executable and print, among other things, the dynamic libraries needed by the program.
For example: assuming GraphicLib is a Linux dynamic library called graphiclib.so, this is what readelf -d run on the final executable would print out (truncated for clarity, and the -d flag means "show me the dynamic stuff"):
...
0x0000000000000001 (NEEDED) Shared library: [graphiclib.so]
...
The readelf -d output is tabular data formatted as follows:
[address] [type] [name]
In words: the program needs ((NEEDED)) a dynamic library called graphiclib.so. The funny hexadecimal number is just a placeholder to signify the lack of a pre-defined load address: it will be decided at runtime.
Dynamic libraries on Windows require an extra step during linkage. By default, all symbols in a DLL are invisible from the outside. Library's authors have to change the visibility of a symbol — or export it — if they want to make it available to the linker. There are multiple ways of doing this: the easiest one is to mark the function in the library's source code with the special attribute __declspec(dllexport), a Microsoft-specific extension to C and C++.
Symbols can be stripped off a binary file. This is useful especially for a sub-category of symbols called debug symbols, optionally generated by the compiler. They allow debuggers to print fancy function and variable names instead of raw memory addresses, making the debug process more pleasant to humans. On macOS and Linux debug symbols are part of the binary file and are often removed from the final executable with command-line tools like strip when it's time to distribute the software.
Beware though: strip can also remove all symbols, including those needed by the linker during the final linkage. While it's safe to strip an executable, deleting all symbols from a library renders it useless for linking! Luckily there's no such risk on Windows, where debug symbols aren't part of the binaries: they are stored in separate files called "Program Database" files (.pdb files).
A program linked against a static library has all dependencies self-contained in the binary file: this is called compile-time linking. The operating system reads instructions and data from the executable and copies them into memory with no modification, ready to be processed by the CPU.
A program linked against a dynamic library still needs to resolve undefined symbols. When the program is run, an operating system component called dynamic linker parses the executable file for the missing pieces left by the normal linker, loads up in memory the required dynamic libraries — if not already present — and performs symbol resolution as needed. This is called load-time linking.
Specifically, the dynamic linker makes use of the information we found when we called the nm and readelf commands above: the undefined symbol drawPixel lies in graphiclib.so. The difference here is that the linkage is not hardcoded in the binary file, but live performed in memory every time the program is started, right before the main() function invocation.
Side note: run-time linking is a third form of linking that can take place while the program is running. Functions like dlopen on Unix or LoadLibrary on Windows give you the ability to load dynamic libraries at runtime, according to your program's logic. This technique is also used to implement a certain kind of plug-in architecture, where pieces are conditionally loaded on demand.
The executable only contains the library name, as we saw in the readelf output, but the dynamic linker knows several default places to look for. Each operating system follows its own rules:
%PATH%);/lib and /usr/lib are searched by default. The LD_LIBRARY_PATH environment variable holds additional directories for the dynamic linker to look into. The absolute dynamic library path also can be hardcoded into the executable by setting the RUNPATH tag during compilation (RPATH is the same thing, deprecated). Finally the dynamic linker can be configured directly by altering the /etc/ld.so.conf file. All these settings are processed on program startup according to a specific order;@executable_path, @loader_path and @rpath that get expanded by the dynamic linker on startup. Specifically, @rpath is set at compile time and contains a list of directories suitable for the search. Like Linux, macOS also provides LD_LIBRARY_PATH and a bunch of other environment variables, ignored if the System Integrity Protection (SIP) is enabled.All this machinery is required to make an executable that depends on dynamic libraries work even when moved around the filesystem. The opposite is not true: change a dynamic library location and all the programs that depend on it will crash at startup with a dynamic linker error. The variables mentioned above are also often tweaked when distributing executables along with their dynamic libraries in a single package, for example with macOS bundles or Linux Appimages.
Programs and dynamic libraries talk to eachother in binary, and their dialog is governed by specific rules and conventions known as the Application Binary Interface (ABI). The ABI defines on a binary level how the layout of structures should be, the expected number of parameters a function may take, the expected return types, pointer sizes and many other things — naming conventions for symbols included. A program and a dynamic library are ABI compatible if they both agree on such rules: ABI compatibility means a program and a dynamic library can interact together without errors.
Several things can be done to avoid ABI problems when programming a new version of a dynamic library that is already linked by an existing executable. In case the ABI compatibility is broken, the only way to fix it is to recompile the program that depends on it. This way the primary advantage of using dynamic libraries is lost and additional effort is required by developers and maintainers of the program. Library authors always strive to keep ABI compatibility at all costs to avoid such headaches.
This is a common scenario known as inter-library dependency. Let's assume library A depends on library B: if B is a static library, all required symbols are resolved and merged into A during A's compilation stage, before shipping it to the public. If B is a dynamic library, symbols will be left as undefined in A for a later resolution. This is the same thing that happens when linking libraries into final executables, after all.
Let's now consider both A and B as dynamic libraries and a program that depends only on A. The linker, during the linking stage, will store references only to A, even if library A needs stuff that resides in B. Inspecting the final executable would yield something like this on Linux:
...
0x0000000000000001 (NEEDED) Shared library: [liba.so]
...
There's no trace of B: when the program is run, the dynamic linker will recursively walk through all the required dynamic libraries, starting from those found in the final executable, until all dependencies are met. The libraries are then loaded in memory (if not already present). The same strategy is used on Windows and macOS too.
Clearly you can't get the list of dynamic dependencies by looking inside the executable alone. Tools like ldd on Linux, Dependencies on Windows and otool on macOS are designed to do the dynamic linker's hard work and recursively detect all the dependencies needed. Some of them actually invoke the dynamic linker, which is the same thing as running the program, at least for the very first stage. Their usage is then discouraged if you suspect the executable contains malicious code!
Wikipedia — Symbol (programming)
Wikipedia — Static library
Wikipedia — Dynamic linker
Wikipedia — Linker (computing)
Wikipedia — Dynamic-link library
Eli Bendersky's website — Position Independent Code (PIC) in shared libraries
StackOverflow — How to distribute a Mac OS X with dependent libraries?
The Inside Story on Shared Libraries and Dynamic Loading
David A. Wheeler — Program Library HOWTO
Better understanding Linux secondary dependencies solving with examples
dlopen(3) — Linux manual page
Oracle Solaris Blog — Inside ELF Symbol Tables
Beginner's Guide to Linkers
Linux Journal Linkers — and Loaders
Computer Systems: A Programmer's Perspective — Chapter 7: Linking
Compiling, Linking and Debugging Tips for C++
Flameeyes's Weblog — The why and how of RPATH
CMake wiki — RPATH handling
libc++ 12.0 documentation
ld.so(8) — Linux manual page
mikeash.com — Friday Q&A 2009-11-06: Linking and Install Names