Linkers

Symbol Resolution

The purpose of symbol resolution is take each symbol (the names for certain functions and variables in the source code files) and bind it with one, and only one, definition (the initializations of those names). To understand what this means, we revisit compilers.

From the compiler section, we saw that after a compiler receives source code, it will generate a symbol table. This is a table containing the names, memory sizes, and other information about identifiers (variable and function names) used in the program. Each of these identifiers are called symbols. Because each source code file results in its own object file, the object files will contain their own symbol tables.

The symbol tables generated by the compiler will often contain a large amount of information. This includes symbols for function arguments and local. The linker, however, is only looking at three kinds of symbols. Suppose we have two source code files, 𝐴 and 𝐵, compiled to their respective object files.

1. Global symbols. These are identifiers defined in 𝐴 that can be referenced and used in 𝐵, or vice versa. In languages like C, these take the form of nonstatic functions or global variables.
2. External symbols. These are identifiers used in 𝐴 or 𝐵 that are defined elsewhere. For example, if 𝐵 uses the math.h module and uses the acosh function, acosh is called an external. It's defined outside of 𝐵 but used by 𝐵.
3. Local symbols. These are identifiers defined globally in 𝐴 that can only be used by 𝐴. Or, in 𝐵's case, the identifiers defined globally in 𝐵 that can only be used by 𝐵. In languages like C, these are are called static functions or global variables.

What about all of the local identifiers? Those are not looked at by the linker. Remember, the linker's operates at the file (or global) level. The linker will not touch locals — it assumes that the identifiers are already in the correct place, ready to go.

When the linker receives the object files, it will go through each file, and resolve the symbol references: an identifier associated with a symbol. For example, in the two programs we saw previously:

// main.c
int sum(int *a, int n);

int arr[2] = {1,2};

int main(int argc, char** argv) {
	int val = sum(arr, 2);

	return 0;
}

// sum.c
int sum(int *a, int n) {
	int i, s = 0;
	for (i = 0; i < n; i++) {
		s += a[i];
	}
	return s;
}

In main.c, we have two symbols for the linker: array and main. We also have symbol reference: sum. This symbol refers to the sum defined in sum.c In sum.c we have one symbol: sum.

For example, compiling the files into a single object file called prog and running the command:

objdump -t prog

we get the following output:

0000000100000000 g     F __TEXT,__text __mh_execute_header
0000000100004000 g     O __DATA,__data _arr
0000000100003f30 g     F __TEXT,__text _main
0000000100003f60 g     F __TEXT,__text _sum
0000000000000000         _UND_ dyld_stub_binder

Let's put this information into an actual table:

Each row in the table is a symbol entry, and each entry has the following fields:

1. The symbol offset contains the offset values for each symbol. We can think of this value as corresponding to the symbol's index in its respective section. This is how the linker quickly finds the symbols.
2. The binding indicates whether the symbol is a global, static, or reference.
3. The type indicates whether the symbol is a function (F), object (O), or undefined (_UND_).
4. The section indicates which section the symbol belongs to. In this case, we see that it's either the text section, or the data section.
5. Finally, the name field provides the symbol's name.

The last row, dyld_stub_binder, is an output we may or may not see depending on the compiler we use. The output above was generated on Mac OS X, which uses dynamic linking. The dyld_stub_binder is a function that takes a symbol and effectively designates it as a symbol to be dynamically linked. We'll cover this in more detail when we get to dynamic linking. If we had instead written:

#include <stdio.h>

int sum(int *a, int n);

int arr[2] = {1,2};

int main(int argc, char** argv) {
	int val = sum(arr, 2);
	printf("%d\n", val);
	return 0;
}

we would see the symbol table:

0000000100008008 l     O __DATA,__data __dyld_private
0000000100000000 g     F __TEXT,__text __mh_execute_header
0000000100008010 g     O __DATA,__data _arr
0000000100003ef0 g     F __TEXT,__text _main
0000000100003f40 g     F __TEXT,__text _sum
0000000000000000         _UND_ _printf
0000000000000000         _UND_ dyld_stub_binder

Now, back to symbol resolution. Say we wanted to link two files, main.c and foo.c:

// main.c
void foo();
int main() {
	foo();
	return 0;
}

// foo.c
void foo() {
	printf("foo!\n");
}

When the linker receives main.o and foo.o, the symbol tables look as follows. For main.o, we have:

0000000000000000 g     F __TEXT,__text _main
0000000000000000         _UND_ _foo

and for foo.o, we have:

0000000000000000 g     F __TEXT,__text _foo
0000000000000000         _UND_ _printf

Notice how the entries in the symbol table are undefined. This is because we're only seeing the symbol tables outputted by the compiler. All the compiler does is create symbol tables for the code in the file its given. It doesn't have a clue about what's going on in some other file. Thus, when the compiler encounters these undefined symbols, it marks the entry as undefined, indicating to the linker: "This is probably defined in some other module."

The linker's job at the symbol resolution stage is as follows:

1. Fill in those undefined entries.
2. If there are duplicate entries, pick one so there aren't duplicates.

This is done by creating a single large symbol table, as we saw earlier. Say we link the main.o and foo.o into prog.

Just to remind ourselves, the linker's job is to take the two symbol tables from main.o and foo.o:

and create a single monolithic symbol table for prog:

// main.c
int baz=1;
int main() {
	...
}

// foo.c
int baz;
p2() {}

// fileA.c
long int x;
int main() {
	....
}

// fileB.c
double x = 3.14;

// module.c
#include "global.h"
int f() {
	return g+1;
}

// main.c
#define INITIALIZE
#include "global.h"

int main() {
	int x = g * 2;
}

// global.h
#ifdef INITIALIZE
	int g = 23;
#else
	extern int g;
#endif

Symbol Relocation

Once the linker has resolved all of the references without error, it essentially has three separate tables with entries that (1) have no duplicates and (2) have all the references defined. The final step is to pull each section from the tables and merge them into a single giant table.

To do so, the linker must adjust some of the addresses for the variables and functions to ensure everything is sequential. Once it has completed this alignment process, it outputs the executable, ready for our execution.

To tie this back to our earlier discussions on memory, the linker only handles the globals, externals, local globals, and statics. Everything else is handled at runtime (the stack), the operating system (the heap and external libraries).