Linking and Loading of a Computer Program...C program perspective

Linking and loading happens when we are compiling a code to generate an executable code. These are the final stages which gives architecture dependent final touches to the object files and create a single executable at the end.

The Setup

Let us suppose we have a couple( x.c and y.c) of C program files and these programs contain non-definitive declarations only and the actual definition exists in another file which is also subjected to compilation.

So, the content of the files looks like this,

Content of x.c

//extern keyword means that the definition of x resides somewhere else
extern int x; 

//the function definition is also missing from here
int add(int a,int b);

int main()
{
	add(x,1);
	return 0;
	}

And for another file y.c

//both of the missing definitions from x are present here!
int x=10;
int add(int a,int b){
	return a+b;
}

We are going to use gcc to convert them into the corresponding object files by issuing the command: gcc -c -O0 x.c and gcc -c -O0 y.c. Now we have 2 object files named x.o and y.o but inside these object files components still do not know where the definitions exist, or even if they exist somewhere, it is the job of the linker to find all the definitions and connect them with each other among object files.

Compilers like GNU's gcc or clang invoke linker implicitly when you compile the code without using the -c flag which tells the system to only compile and not link anything.

The Process : Static Linking

Linker is going to look for the relocation table inside each object file and find what are the definitions that are present in these files and what definitions are required by them.

Let us analyze the object files using UNIX tools like objdump and nm which are 2 most common tools to analyze binaries.

Comand: $ objdump -d x.o

x.o:     file format elf64-x86-64
Disassembly of section .text:
0000000000000000 
:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   8b 05 00 00 00 00       mov    0x0(%rip),%eax
   a:   be 01 00 00 00          mov    $0x1,%esi
   f:   89 c7                   mov    %eax,%edi
  11:   e8 00 00 00 00          callq  16 
  16:   b8 00 00 00 00          mov    0x0,%eax
  1b:   5d                      pop    %rbp
  1c:   c3                      retq 

As you can see in red, that are the addresses which are left empty by the gcc are just left as 0x0. Now running another command will show us that there are a few tables in each object file called the Symbol Table and Relocation Table, which tells the linker about the symbols that are present in the object file.

Command to see a Relocation Table: $ objdump -r x.o

RELOCATION RECORDS FOR [.text]:
OFFSET           TYPE              VALUE 
0000000000000006 R_X86_64_PC32     x-0x0000000000000004
0000000000000012 R_X86_64_PLT32    add-0x0000000000000004


RELOCATION RECORDS FOR [.eh_frame]:
OFFSET           TYPE              VALUE 
0000000000000020 R_X86_64_PC32     .text

To view A symbol table which actually states all the symbols present in the object file we will use nm which is designed for that same purpose.

Command: $ nm x.o

                 U add
                 U _GLOBAL_OFFSET_TABLE_
0000000000000000 T main
                 U x

We can see that the symbol table for x.o contains entries with a U in front of it, which means that it is a global undefined symbol. (src: man nm)

Command: $ nm y.o

0000000000000000 T add
0000000000000000 D x

Now, both of the definitions are present in the y.o file and the linker needs to use these definition while combining them into an executable.

So, lets link these files and create an executable ELF file and look at the assembly code if the addresses are filled in those places.

Command: $ ld x.o y.o -o xy

Command: $ objdump -d xy

Disassembly of section .text:

0000000000401000 :
  401000:       55                      push   %rbp
  401001:       48 89 e5                mov    %rsp,%rbp
  401004:       89 7d fc                mov    %edi,-0x4(%rbp)
  401007:       89 75 f8                mov    %esi,-0x8(%rbp)
  40100a:       8b 55 fc                mov    -0x4(%rbp),%edx
  40100d:       8b 45 f8                mov    -0x8(%rbp),%eax
  401010:       01 d0                   add    %edx,%eax
  401012:       5d                      pop    %rbp
  401013:       c3                      retq   

0000000000401014 
:
  401014:       55                      push   %rbp
  401015:       48 89 e5                mov    %rsp,%rbp
  401018:       8b 05 e2 2f 00 00       mov     0x2fe2(%rip),%eax   # 404000 
  40101e:       be 01 00 00 00          mov    $0x1,%esi
  401023:       89 c7                   mov    %eax,%edi
  401025:       e8 d6 ff ff ff          callq  401000 
  40102a:       b8 00 00 00 00          mov    $0x0,%eax
  40102f:       5d                      pop    %rbp
  401030:       c3                      retq

As you can see in the green,  the address values are added in the linked executable file! All this was about when we are linking statically.

The Linker Script

To be able to link everything together the linker needs a little help from the operating system in the form of a linker script which tells the linker how to place sections inside of the memory. Let me show an example of a simple linker script.

Let’s say that the code should be loaded at address 0x10000, and that the data should start at address 0x8000000.  Here is a linker script which will do that:

SECTIONS
{
  . = 0x10000;
  .text : { *(.text) } // this is the code section
  . = 0x8000000;
  .data : { *(.data) } // initialized data
  .bss : { *(.bss) } //  uninitialized static data
}

Now, it should be clear to the reader how linker decides which addresses to assign to different sections of the code.

There are many default linker script present in a UNIX-like system, for example, in my desktop debian, there are a bunch of them present at /lib/x86_64-linux-gnu/ldscripts.

The Process: Dynamic Linking

Till now we have not seen any #include statements which are used to include header files. These header files are often paired with a shared library, which is a lib-*.so file(so stands for shared library I guess), residing somewhere on your machine specified by LD_LIBRARY_PATH environment variable.

We ask the compiler to take those into account while linking by using -l option. For example, gcc -L. -lmyfile.so

Overview

Let's say that we use printf from standard library in C. That function is defined in the library file associated with stdio.h header which is called libc.so which is compiled binary shared object file containing symbol definition for the printf.

Only at the link time the linker checks if the required function symbol is present in the libc.so file and if it does not, then shows an error indicating that the function symbol definition is not found. But, if it is found, then it does not link it immediately but in fact attatches itself to the executable binary in the form of the dynamic linker and just sits there till execution happens.

While executing the code, the code contains a Procedure Linkage Table, also seen as .plt section in the elf binary file along with the Global linkage Table, shortened to .glt. It is the task of these two table to keep a record of what has been dynamically linked and what has not.

The first time a linkage is required, an address to an entry in the .plt is given which invokes the dynamic linker, which loads the shared library into the memory using a syscall dlopen() and places it's newly loaded address in the .plt so that if the code calls the function again, it should run directly from the linkage table.

Overview: Loading

Loader is generally a part of the operating system. In case of linux the exec***() family of functions take an executable ELF file, break it open, loads it in memory then initializes processor registers and sets the IP register to point to the entry section in the ELF header to kick start the execution.

Position Independent Execution

Nowadays, to protect from Return Oriented Programming (ROP) attacks, code is loaded with random addresses assigned to functions and data members, or sections.

It is the job of the loader to make sure that the addresses are correctly altered before each execution.

Conclusion

In order for the program to run we need to properly link it with the code from other object files and then with a shared library using a component of the loader that sticks inside your binary when you link. Then the job of the loader is to just place it in memory and give a green light to the CPU to start executing the code.

Thankyou for reading!!