Linking

Let's look at hello world

#include <stdlib.h>
#include <stdio.h>

int main(void) {
	printf("Hello world!\n");
	return EXIT_SUCCESS;
}

Compile $ gcc -0g hello-world.c $ ls -l a.out outputs -rwxr-xr-x. 1 phi users 8512 Nov 16 03:57 a.out

• It's pretty small.

Dynamic Linking

Dynamic makes code smaller beacuse the executables do not need the complete copy of any library functions. Results in the need of less disk space

When two executables share the same library, they can use the same instance of the library, so only one copy needs to be loaded into memory. Overall, this means that we need less RAM.

It also means that when a library is updated, there is no need to recompile, and every single executable that uses the library wil automatically be updated.

Static Linking

Compile with --static Tells it to copy every c library used by your program. This results in a very large file.

Used if you are executing your program in an enviornment where shared (dynamic) linking is not available.

Example:

We have code in two files.

main.c

int sum(int *a, int n);

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

int main() {
	int val = sum(array, 2);
return val;
}

• The declaration int sum(int *a, int n); gives the compiler enough information to know that it will exist by the time the linker generates the executable. sum is external

sum.c

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

Now, we compile and run

$ gcc -Og -o prog main.c sum.c
$ ./prog
$ echo $?

The above outputs:

3

• Each source files produces a corresponding an object file. main.c --> main.o
• cpp is the preprocessor, which is a text replacement tool. It replaces text like #include or #define.
• cc1 is the actual compiler. It takes the preprocessed code and translates it to assembly code.
• as takes the generate assembly code and translates it to an object (.o) file.
• main.o and sum.o are "relocatable" object files.
  • These cannot be be. Although the object files can be run, the memory addresses are not meaningful. Furthermore, the external references are not resolved (there are missing details).
• ld is the linker. It combines all the .o files into a single executable.

Responsibilitiies of Linker

The static linker has two jobs

• place code/data in memory at known addresses
• and resovles references to symbols (a named code or data object that may or not may not have been defined in any .o files)

The linker can do all of this because it knows where it placed the object data and code.

In other words, the linker is in charge of

• symbol resolution
  • object files define and reference symbols (functions, global variables, static variables)
  • need to connect symbol (use) to exactly one definition (the actual address of code/data)
• relocation
  • assemblers generate object files that starts at address 0 (this is not realistic, it is simply a placeholder that needs to be resolved later)
  • when combining multiple object files, code must be shifted
  • all reference to memory addresses must be adjusted
  • assembler stores meta information in object file
  • linker is guided by relocation entries

Object Files

The relocatable object file (.o files) has binary code and meta information that allows symbolr resolution and relocation.

An executable object file (exe) has binary code that can be copied into memory and executed

Shared object file (.so) are binary code that can be loaded into memory and be linked dynamically

• Executable object files and shared object file can be loaded into memory by the operating system.

Relocatable Object Files is typically in the Executable and Linkable Format (ELF). It's a very common data file in Linux and it contains

• header
• a collection of sections with different type of data
  • these sections will be loaded into memory
    • .text has machine code of compiled program
    • .rodata has read-only data (e.g., strings in printf statements)
    • .data has initialized global and static C variables
    • .bss has uninitialized global and static C variables
  • these sections are metadata
    • .symtab contains an entry for every symbol that is defined or referenced by this file
    • .rel.text and .rel.data is the relocation entries. These are placeholders for unknown references or placeholders in the .text section. These are modified when object is relocated
    • .debug debugging symbol table when compiled with -g
    • .line mapping between line number and machine code when compiled with -g
    • .strtab string table for .symtab and .debug
• section header table

Symbols are basically labels.

• Global symbols (.globl) that can be used by other objects
• Global symbols of other objects (not defined here)
• Local symbols only used in object defined with "static" attribute
• Note: non-static local variable are not exposed

ELF Symbol Table Entry

Name	Pointer to string of symbol name
Type	Function or data type
Binding	Indicates local or global
Section	Index of which section it belongs to
Value	Section offset
Size	Size in bytes

Example When you check out the ELF symbol table with

$ readelf -a main.o

• main is a function (FUNC) in section .text (1)
• array is an object (OBJECT) in section .data (3)
• sum is undefined (UND)

Symbol Resolution

• Linker must resolve all symbols to connect references to addresses
• Local symbols are contained to their object, each has a unique name
• Symbols in an object file may be undefined (listed as UND in symbol table) ⇒ these must be defined in other objects

If not found, linker complains:

$ gcc -Og main.c

/tmp/ccZzl3Pp.o: In function `main':
main.c:(.text+0xf): undefined reference to `sum'
collect2: error: ld returned 1 exit status

Static Library

Goal: link various standard functions statically → binary without dependency

There are two methods

• Plan A
  • put everything into big libc.o
  • link it to the application object file... but that adds too big of a file
• Plab B (actually used)
  • have separate object files printf.o, scanf.o, ...
  • link only the ones that are needed... but that requires a lot of tedious bookkeeping by programmer

To solve the problem caused by Plan B, we use archives, .a files. It's sort of like a zip file with no compression. It's a collection of .o files accompanied by a dictionary that connects the symbol name to the file.

• It combines object files printf.o, scanf.o, ... into archive libc.a
• The linker picks out the ones that are needed $ gcc main.c /usr/lib/libc.a
• Build your own library with $ ar rcs libmy.a my1.o my2.o my3.o

Relocation

• Multiple object files
• Merge all sections, e.g., all .data sections together
• Assign run time memory addresses for each symbol
• Modify each symbol reference
• This is aided by relocation entries

A relocation entry

Offset	Offset of reference within object
Type	Relocation type (absolute 32 bit address or address relative to program counter)
Symbol	Symbol table index
Added	Constant part of relocation expression

Loading Executable Object FIles