04 Linking
Motivation¶
Example C program
// main.c
int sum(int *a, int n);
int array[2] = {1, 2};
int main(int argc, char** argv) {
int val = sum(array, 2);
return val;
}
Programs are translated and linked using a compiler driver:
- linux> gcc -Og -o prog main.c sum.c
- linux> ./prog
![[Screen Shot 2024-06-14 at 04.30.31.png]]
Compiler driver: Invokes the language preprocessor, compiler, assembler, linker on behalf of the user. An example is the GCC driver.
Language processor: GNU C Preprocessor includes the headers and expands the macros to convert *.c to *.i.
Compiler: C compiler compiles preprocessed code to assembly code by converting *.i to *.s file. (Some compilers generate object code directly)
Assembler: Assembler converts the assembly code to machine code in the relocatable object file *.o.
Linker: Combines the object files to create a binary executable object file.
Linking: Collection and combining pieces of code and data into a single file for execution. Can be done at different times. - Compile time: Source code is translated into machine code. - Load time: Program is loaded into memory and executed by the loader. - Run time: When instructions of the program are executed.
Why Linkers? 1. Modularity: Program can be written as a collection of smaller source files, rather than one monolithic mass. Can build libraries of common functions. 2. Efficiency: Compilation time is reduced for individual modules. Executable size is reduced when shared libraries can be taken advantage of.
Static Linkers: Take a collection of relocatable object files and generate a fully-linked executable object file. The file consists of continguous code and data sections. The linkers must perform two functions.
Symbol resolution: Ensuring that each reference is associated with exactly one definition.
void swap() {...} /* definition */
swap() /* reference */
int *xp = &x; /* definition & reference */
Symbol relocation: Addresses of symbol definitions from object files are associated with memory locations.
What it does¶
Step 1: Symbol resolution¶
- Programs define and reference symbols (global variables and functions):
void swap() {…} /* define symbol swap */swap(); /* reference symbol swap */int *xp = &x; /* define symbol xp, reference x */
- Symbol definitions are stored in object file (by assembler) in symbol table
- Symbol table is an array of entries
- Each entry includes name, size, and location of symbol
- During symbol resolution step, the linker associates each symbol reference with exactly one symbol definition.![[Screen Shot 2024-06-14 at 04.42.00.png]]
Step 2: Relocation¶
- Merges separate code and data sections into single sections
- Relocates symbols from their relative locations in the .o files to their final absolute memory locations in the executable.
- Updates all references to these symbols to reflect their new positions.
Three Kinds of Object Files (Modules)¶
- Relocatable object file (.o file)
- Contains code and data in a form that can be combined with other relocatable object files to form executable object file.
- Each .o file is produced from exactly one source (.c) file
- Executable object file (a.out file)
- Contains code and data in a form that can be copied directly into memory and then executed.
- Shared object file (.so file)
- Special type of relocatable object file that can be loaded into memory and linked dynamically, at either load time or run-time.
- Called Dynamic Link Libraries (DLLs) by Windows
Executable and Linkable Format (ELF)¶
- Standard binary format for object files
- One unified format for
- Relocatable object files (.o)
- Executable object files (a.out)
- Shared object files (.so)
- Generic name: ELF binaries ![[Screen Shot 2024-06-14 at 05.31.20.png]] ![[Screen Shot 2024-06-14 at 05.31.34.png]]
Types of object files
A relocatable object file is an .o file that is produced from one source .c file. An executable object file is an a.out file generated by the linker. A shared object file is a relocatable object .so file that can be loaded into memory and linked dynamically.
The object file format used by Linux and Unix is called Executable and Linkable Format (ELF).
ELF header - Word size, byte ordering, file type (o, so, out)
Section header table - Where different sections are in memory
.text - Machine code
.rodata - Read only data such as jump tables
.data - Initialized global variables
.bss - Uninitialized global variables (No space taken by data)
.symtab - Symbol entries for procedures and global variables
.rel.text - Relocation info for .text section (Not needed in exe)
.rel.data - Relocation info for .data section (Not needed in exe)
.debug - Source code to line number in machine code
.strtab - String table for symbols in .symtab .debug
Section header table - Where different sections start
Symbol
Global symbols: Symbols defined by module "m" that can be referenced by other modules. - e.g., Non-static C functions and non-static global variables.
External symbols: Symbols that are referenced by module "m" but defined by other modules.
Local symbols: Symbols defined and referenced exclusively by module "m".
- e.g., static C functions and global variables. These are stored in .bss or .data. Local linker symbols are not the same as local program variables which are stored in the stack.
How it works¶
Symbol table: Assemblers use the symbols exported by compilers to build the table. This means *.s files do not have them yet. Each entry is shown below.
typedef struct {
int name; /* .strtab offset */
char type:4, binding:4; /* Function or data, local or global */
char reserved; /* Unused */
short section; /* Section header index */
long value; /* Section offset or abs address */
long size; /* Object size in bytes */
}
Pseudosections: Sections not indexed in the section header table. ABS means that the symbol should not be relocated. UNDEF means symbols are defined not in the module. COMMON means uninitialized data objects that are not allocated.
Uninitialized data objects may be defined in other modules so compiler defers the decision to the linker by assigning COMMON section in relocatable object files. COMMON section is not present in executable object files.
Aside from uninitialized variables... zero-initialized variables are assigned it to .bss instead of .data becuase at runtime, variables in this section are assigned zero. This saves space.
Symbol resolution
Straightforward for references to local symbols which are defined in the same module. Compiler ensures that static variables have unique names and defined only once.
It is more complex for global symbols. The compiler can accept undefined variables anyway and the failure will occur at the linker.
Compiler exports each global symbol either as strong (Procedures and initialized globals) or weak (Uninitialized globals). The assembler encodes the information implicitly in the symbol tables. The linker uses the following rules -
- Multiple strong symbols not allowed.
- Strong symbol is chosen over weak symbols.
- If multiple weak symbols, an arbitrary one is picked.
For example, calling the function f() results in x -> 0x0 and y -> 0x80000000.
/* foo.c */
#include <stdio.h>
void f(void);
int y = 15213; /* Address: 0x601020 */
int x = 15213; /* Address: 0x601024 */
int main() {
f();
return 0;
}
Static libraries
Related functions are compiled into separate object modules and packaged into a single static library. At link time, the linker will only resolve object modules referenced by the program. On Linux, static libraries are stored in a format called archive as *.a files.
To create a static library of multiple modules, we can use the AR tool -
We can also create a vector.h header file to define the function prototypes.
/* main2.c */
#include <stdio.h>
#include "vector.h"
int x[2] = {1, 2};
int y[2] = {3, 4};
int x[2];
int main() {
addvec(x, y, z, 2);
printf("z = [%d %d]\n", z[0], z[1]);
return 0;
}
Symbol resolution of static libraries
Linker scans the relocatable object files and archives from left to right as given in the command line.
E = { relocatable object files to be merged }
U = { unresolved symbols }
D = { defined symbols }
for each file f (left to right):
if f is relocatable object file:
Add f to E.
Update U and D with definitions and references.
if f is an archive:
Try to match symbols in U and add matched members to E.
Update U and D with definitions and references.
if U is non-empty:
Throw error
Rule of thumb is that static libraries should be ordered at the end of the command line. The libraries requiring dependencies should not be placed at the end.
Relocation
After symbol resolution, the linker knows the exact sizes of the code and data sections. In relocation, it merges the input modules and assign runtime addresses to each symbol. There are two steps.
Relocating sections: Linker aggregates sections of the same type and assign runtime addresses to sections and symbol definitions.
Relocating symbol references: Linker modifies every symbol reference so that each points to the correct runtime address. Linker relies on relocation entries for while have been generated by the assembler.
Relocation entry
Assembler generates a relocation entry whenever external variables are referenced by the module. Entries for code are in .rel.text and entries for data are in .rel.data.
typedef struct {
long offset; /* Section offset of the reference */
long type:32, /* Relocation type */
symbol:32; /* Symbol table index */
long addend; /* Constant part of relocation expression */
} Elf64_Rela;
There are two relocation types. R_X86_64_PC32 is for PC-relative referencing. R_X86_64_32 is for absolute referencing.
Relocation algorithm
foreach section s {
foreach relocation entry r {
// Ptr to the placeholder bytes
// The address in the current process (not runtime)
refptr = s + r.offset;
if (r.type == R_X86_64_PC32) {
// The address during runtime
refaddr = ADDR(s) + r.offset;
*refptr = ADDR(r.symbol) + r.addend - refaddr;
}
if (r.type == R_X86_64_32)
*refptr = ADDR(r.symbol) + r.addend;
}
}
Example of relocation
At offset 0xa, array will have to be referenced with PC-relative address. At offset 0xf, sum will have to be referenced with absolute address.
int array[2] = {1, 2};
int main() {
int val = sum(array, 2);
return val;
}
0000000000000000 <main>:
0: 48 83 ec 08 sub $0x8, %rsp
4: be 02 00 00 00 mov $0x2, %esi
9: bf 00 00 00 00 mov $0x0, %edi # %edi = &array
(R_X86_64_32 array)
e: e8 00 00 00 00 callq 13 <main+0x13> # sum()
(R_X86_64_PC32 sum-0x4)
13: 48 83 c4 09 add $0x8, %rsp
17: c3 retq
At line 0xe, there is 1-byte opcode 0xe8 and a 4-byte placeholder for the PC-relative reference to sum() function. The placeholder will be replaced with PC-relative reference after the relocation algorithm is run. (Note: Jumps and Calls always use PC-relative addresses)
At line 0x9, there is 1-byte opcode and a 4-byte placeholder for the absolute reference to array. After relocation, the address will point to somewhere in the .data section.
At load time, the loader can copy the bytes directly into memory and execute without any modifications. The .rel.text and .rel.data sections are no longer required.
Executable object file
The format is similar to relocatable object file. It includes the entry point which is the first instruction to execute. There is also .init section which executes before the main program.
Loading executable object file into memory
The loader copies (Map virtual memory pages) the code and data from the executable object file into memory and jumps to the entry point. The runtime heap follows the .data section and grows upwards. The user stack starts from the largest legal user address (248 - 1) and grows down.
Heap, data and code segments actually have gaps between them due to alignment requirements and the address-space layout randomization.
Shared libraries (Dynamic link libraries)
Provide a mechanism where one executable copy can be shared between different programs. Unlike static libraries, the linking of references is deferred until load time or even runtime.
The linker does not resolve the references such as printf() during relocation. It only notes in the symbol table that these references will have to be resolved during load time. When executable file is created, linking is only partially complete.
During load time, the loader (execve) loads the executable and runs the dynamic linker. The dynamic linker allocates text and data of shared libraries into memory and relocate the references in the executable object file. Control is returned to the entry point afterwards.
Linking during runtime example
#include <stdio.h>
#include <stdlib.h>
#include <dlfcn.h>
int x[2] = {1, 2};
int y[2] = {3, 4};
int z[2];
int main() {
void *handle;
void (*addvec)(int *, int *, int *, int);
char *error;
/* Dynamically load the shared library that contains addvec() */
handle = dlopen("./libvector.so", RTLD_LAZY);
if (!handle) {
fprintf(stderr, "%s\n", dlerror());
exit(1);
}
...
/* Get a pointer to the addvec() function we just loaded */
addvec = dlsym(handle, "addvec");
if ((error = dlerror()) != NULL) {
fprintf(stderr, "%s\n", error);
exit(1);
}
/* Now we can call addvec() just like any other function */
addvec(x, y, z, 2);
printf("z = [%d %d]\n", z[0], z[1]);
/* Unload the shared library */
if (dlclose(handle) < 0) {
fprintf(stderr, "%s\n", dlerror());
exit(1);
}
return 0;
}
Virtual Address Space of a Linux Process
Kernel address space starts with 1 (top). User address space starts with 0 (bottom).