Linking on Linux x86–64 Machines

Linking is the process of combining various pieces of code and files to construct a single file that can be loaded into memory and then executed.
Linking can be performed at compile-time. It can also be performed at load-time when the program is getting copied into the memory. Or at run-time, while the program is running.
Linking plays a crucial job in software development because it enables separate compilation, which in turn helps to structure large projects in various small modules instead of one monolithic source file. In addition to being organized in smaller more-manageable modules, linking also accelerates compile-time because those modules can be compiled once and linked many times. If one module gets an edit, we only need to recompile this particular file and then re-link the project.

Linking can be useful to learn for a couple of reasons, despite being not very ostensible at the beginning.

• While doing large projects, you’ll likely face a linker error that states that the program is missing a module or library function. Those can be somewhat not understandable. If you’re not familiar with linking and what are the techniques that the linker uses to resolve those symbols, those might be very perplexing and confounding.
• Understanding linking will let you avoid very nasty errors. Often while using multiple global variables in different modules, linkers will have to decide on which of those to resolve a reference to. This can dramatically affect your program silently without any warnings. If you’re not familiar with the rules that linkers use to make such decisions, your programs can be vulnerable to those nasty errors and baffling run-times behaviors.
• Linking is significantly related to scoping rules. Learning linking will make you understand how those scoping rules are implemented, e.g., what is the difference between locals and globals, what does it mean to define a variable as a static or extern.

Compilation process overveiw

GNU compilation system provides us with a compiler driver (GCC) that is used to run a file (or a set of files) through a series of steps that essentially convert the source file from the ASCII format to an executable that can readily be run.
These steps can be seen by running GCC with -v option.

• You’ll (optionally because, in some GCC versions, it’s integrated into the compiler) see it call the C preprocessor cpp with some arguments and file names.
• Next, it will call the C compiler cc1 on the temp files generated by the preprocessor.
• Then it will call the assembler as that converts those assembly files into object code.
• Followed by the linker ld or an intermediary that is used as a driver for the linker.

This whole process will result in an executable file that you can run in the shell using ./a.out. When the shell sees such a command, it invokes an operating system command called the loader. The loader copies the executable to the memory and transfer the control to its beginning.

There are two main types of linking used in today’s systems, static linking, and dynamic linking. In this post, I will be discussing static linking in general, and hopefully will tackle static library linking and dynamic library linking in subsequent ones.

Static Linking

The ld Linux program is a static linker. It takes in as inputs a bunch of relocatable object files and produces a fully-linked executable file that can be subsequently loaded into memory and run.

Those relocatable object files are the output of the compilation process until after going through the assembler. They consist of various sections that contain different things, e.g., an area that includes instructions, a section that includes initialized global variables, and a section that contains uninitialized global variables.

Building the executable out of those object files requires two main phases.

The first of those is symbol resolution, in which the linker tries to identify all the symbols (which might be functions or global variables) referenced by the object files and try to resolve those symbol references to use precisely one symbol definition.

The second of those is relocation. The output of the assembler is in the form of relocatable object files, this naming is because they start addresses from 0, and replace the value of each symbol that is not known at compile-time to 0, in the second phase of linking, namely, relocation, those object files are relocated by associating those 0’s to the actual address of the symbol that is resolved in the first phase.
The linker does this relocation by the aid of relocation entries that the compiler and assembler generate, telling the linker that in the following instruction, there’s a symbol that needs relocation to the address of the correct symbol.

Object Files

There are three main types of object files, relocatable object files, executable object files, and shared object files.
Relocatable object files are those output by the compiler and assembler.
Executable object files are those processed by the linker and ready to be loaded to memory and get executed.
Shared object is a type of relocatable object files that the linker can link dynamically at load-time or run-time.

Different systems use different formats for object files. We will focus in this post on ELF-64(Executable and Linkable Format), which is used by modern Linux systems, although I’ve read that other formats are mostly similar.

ELF-64 Description and Sections

The ELF-64 format consists of several sections that are merely contiguous bytes.
The very first section is called the ELF header.
It starts with some bits that describe the word size and byte ordering of the system (endianness). The rest of the ELF header has information about the type of the machine, e.g., x86–64, the offset of the section header table, and the object file type.

• Section header table: Has the locations(offsets) of each of the subsequent sections.
• .text: Includes the machine code of the program.
• .rodata: Read-only data, such as those allocated in the following manner in C:char *str = “Hello World.”; and switch statement jump tables.
• .data: Contains initialized global and static variables.
• .bss: Contains uninitialized global and static variables, and any global or static variable that is initialized to zero, this does not take space for variables and is used as a placeholder. At run-time, those variables are loaded into memory as zero.
• .symtab: Acts as a symbol table.
• .rel.text: Contains relocation entries for the .text section, i.e., for global functions that are called and need to be resolved to a symbol.
• .rel.data: Contains relocation entries for the .data section, i.e., for global variables that are referenced and need to be resolved to a symbol.
• .debug_*: Typically, more than one section that contains information required for debugging, e.g., a symbol table for local variables, line mapping between machine code and original source code, etc.
• .strtab: String table that contains names of symbols in .symtab and .debug section and section names, this is typically null-terminated strings.

The .symtab section is always existent in the linked executable, while debug sections are only present if gcc was run with the -g flag, this implies that only function-local symbols are not included if not compiled in debug mode. to get rid of the symbol table section, run the strip program in Linux, which can be used to strip any sections from the object file.

Symbols types

There are three main kinds of symbols that the linker has to deal with in each object module.
Global Symbols, External Symbols, and Local Symbols.
Global Symbols are symbols that are defined by the object module and can be referenced by other modules.
External Symbols are symbols that are defined in another object module and referenced by the current module.
Local Symbols are symbols that are defined and referenced only by the object module. Those correspond to static variables and functions in C. Those symbols are invisible outside the module that defines them.

Local symbol does not refer to a function-local variable, those are handled at runtime using registers and the stack frame. Local symbols in the context of linking are those which are defined using the static keyword.

Function-local variables are not handled at runtime in the stack frame, they’re used as local variables and the compiler allocates space for them either in the .data or the .bss segments, thats why those static variables are presistent over the life span of the program, not deallocated when their scope ends.

int f() {
 static int x = 0;
 return x;
}
int g() {
 static int x = 1;
 return x;
}

In the previous code snippet, the compiler would allocate space for two different versions of the x variable in the .data segment, one for fand one for g and might give them a suffix to distinguish them from each other, e.g.,x.1 and x.2and will, of course, treat them as two local symbols.

Symbol Tables

Assemblers build symbol tables as a section in the ELF-64 object files. Those tables consist of entries that have information about the symbols.

Those Entries are structured more or less contain the following fields: name, type, binding, section, value, and size.

struct ELF64_symbol {
    int name;
    char type: 4, 
         binding: 4,
    short section;
    long value;
    size_t size;
};

• name: Contains a byte-offset to the null-terminated name of the index in the .strtab section in ELF64
• type: Indicates whether the symbol belongs to a function or a variable.
• binding: Indicates whether the symbol is global or local.
• section: Indicates the ELF64 section in which the symbol is allocated, essentially an index into the section header table.
• value: For relocatable object files, it contains the symbol offset in the section, whereas in executable object files, it contains the absolute address of the object of the associated symbol.
• size: stores the size in bytes of the object.

Three pseudosections have no entries in the section header table. Those are COMMON, UNDEF, and ABS.

• COMMON: Contains symbols for uninitialized global variables that are not yet allocated.
• UNDEF: Contains symbols that are not defined by the source file associated with the object file.
• ABS: Contains symbols that do not need relocation.

GCC assigns symbols to .bss or COMMON sections using the following convention:

COMMON: Uninitialized global variables.

.bss: Uninitialized static variables and global and static variables initialized to zero.

Example, Consider the following code:

static int a;
int b;
static int c = 0;
int d = 0;
static int e = 12;
int f = 13;
int main() {
    func();
    return 0;
}

Compiling and assembling the above code to produce the relocatable object file and inspecting the program using readelf usinggcc -c a.c && readelf --all a.o

We can see the following in the .symtab section.

Symbol table '.symtab' contains 17 entries:
Num:    Value          Size Type    Bind   Vis      Ndx Name
0:  0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND
1:  0000000000000000     0 FILE    LOCAL  DEFAULT  ABS a.c
2:  0000000000000000     0 SECTION LOCAL  DEFAULT    1
3:  0000000000000000     0 SECTION LOCAL  DEFAULT    3
4:  0000000000000000     0 SECTION LOCAL  DEFAULT    4
5:  0000000000000004     4 OBJECT  LOCAL  DEFAULT    4 a
6:  0000000000000008     4 OBJECT  LOCAL  DEFAULT    4 c
7:  0000000000000000     4 OBJECT  LOCAL  DEFAULT    3 e
8:  0000000000000000     0 SECTION LOCAL  DEFAULT    6
9:  0000000000000000     0 SECTION LOCAL  DEFAULT    7
10: 0000000000000000     0 SECTION LOCAL  DEFAULT    5
11: 0000000000000004     4 OBJECT  GLOBAL DEFAULT  COM b
12: 0000000000000000     4 OBJECT  GLOBAL DEFAULT    4 d
13: 0000000000000004     4 OBJECT  GLOBAL DEFAULT    3 f
14: 0000000000000000    21 FUNC    GLOBAL DEFAULT    1 main
15: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND _GLOBAL_OFFSET_TABLE_
16: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND func

The column Ndx specifies the index of the section in the symbol header table. The ones of interest here are:

3: .data segment.

4: .bss segment.

If we investigate each of the variables we defined in the global scope:

• a: section 4, i.e., .bss section, because it’s an uninitialized static.
• b: COMMON pseudosection, because it’s an uninitialized global.
• c: section 4, i.e., .bss section, because it’s a static initialized to zero.
• d: section 4, i.e., .bss section, because it’s a global initialized to zero.
• e: section 3, i.e., .data section, decause it’s initialized static.
• f: section 3, i.e., .data section, because it’s an initialized global.
• func: UND, for UNDEF, because it’s referenced in this module but has to be declared in another module.

Symbol Resolution:

Linker has to associate every symbol reference with only one symbol definition from the symbol tables of the relocatable object files.

In the case of a module-local variable, which is defined and referenced in the same module, It is pretty straightforward because the compiler does not allow having more than one definition of a static variable. This definition is used every time the variable is referenced.

In the case of global symbols, there are some rules that GCC follows to resolve symbol references across files.

The compiler and assembler associate each global variable with a strong or weak label, and this label is encoded in the symbol table for the linker to use it.

• A strong symbol is either an initialized variable or a function.
• A weak symbol is an uninitialized variable.

If multiple symbols have the same name, the compiler will choose only one for all the references using the following rules:

• If there are more than one strong symbol of the same name, this is not allowed and will result in a compilation error.
• If there are only one strong symbol and one or more weak symbols, the linker will choose the strong symbol.
• If there are only one or more weak symbols, the linker will choose any of them.

Example:

// a.c
#include <stdio.h>
    int i = 10;
    int main() {
    printf("%d", i);
}
// b.c
int i = 12;

compiled with gcc a.c b.c will give an error because there are two strong symbols called i. However, if one of them were uninitialized, the linker would have chosen the initialized one immediately.

If both were uninitialized, the linker would’ve chosen arbitrarily between them, but here, and because both will be COMMON symbols, both will be initialized to zero at load-time, so the value printed will be 0 in both cases.

Another example that will give an often perplexing behavior:

// a.c
int x = 10; 
void func();
int main() {
    func();
    printf("%d", x);
return 0;
}
// b.c
int x;
void func() {
    x = 15;
}

The intended behavior would most probably be that calling func() would edit x that exists in b.c, but according to the rules that the linker will use, all references to the x symbol will reference the version in a.c because it’s a strong symbol and the one in b.c is a weak symbol.

This will often happen entirely silently. No warnings will fire. The linker will not report that it followed such a strategy. Understanding linking is the way to save yourself from getting into such an action.

Another very baffling result is when the data types are of different sizes, linkers have very little knowledge about data types, so it will just write any size of data in any place:

// a.c 
#include <stdio.h>
int x = 10;
int y = 11;
void func();
int main() {
    func();
    printf("%d %d", x, y);
    return 0;
}
double x;
void func() {
    x = 0.0;
}

Fortunately, compiling the two files will run with a warning, if ignored, calling the function func will write the binary form of 0.0 in the memory that both x and y inhabit.

This program will output 0 0, because 0.0 has the binary form of all zeros, so the memory that x and y are in will be filled in with zeros.

The prgram can avoid those bugs by linking with the GCC flag -fno-common, which means do not arbitrarily select one of several variables defined with the same name, raise an error, or use the flag -Werror which will treat warnings as errors, and any warnings will stop the compilation process.

One thing to note is that how the linker resolves symbols are the reason why there’s this distinction between .bss and COMMON sections.
Essentially, COMMON symbols will be transferred to .bss at load time, but the compiler knows very little on how the linker will choose the definition of symbol to resolve references to.

• If there is more than one strong symbol with the same name, this will raise an error.
• If there is only one strong symbol, this will be chosen and assigned to the .bss section.
• If there are more than one weak symbol, the compiler explicitly marks those as COMMON. The linker can afterward select only one and move it to the .bss section.

Similarly, static variables are never assigned to COMMON because, by definition, static variables cause no trouble to linker to choose from. Each static variable will be tied to the module which defines it, so they’re confidently assigned to .bss or .data.