Introduction

We’ve all executed thousands of programs on Linux machines. The process is blazingly simple: ./my_program. Right away, main() is called and the program starts. The process seems easy: Linux loads the program’s machine code into RAM before asking the CPU to execute it. Simple, right? Or is it? What if I told you running a program is actually a long journey? What if I told you your OS does a massive amount of work to get your program to run? Or, even crazier, what if I told you main is VERY far from being the first piece of code of your program to run? You don’t trust me? Well, see for yourself:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
❯ cat demo.c
#include <stdio.h>

__attribute__((constructor)) void i_run_before_main()
{
    printf("hello from that weird function\n");
}

int main()
{
    printf("main starts here!\n");
    return 0;
}
❯ ./demo
hello from that weird function
main starts here!

This program is called demo, and I’ll refer to it several times throughout the article, so don’t forget about it. Today, we’re going to dive into the entire startup process of a program, from the ELF format to program loading, dynamic linking, memory mapping, and the final transfer of control to your code.

This article focuses on Linux x86-64. Only C programs will be discussed here, but most concepts also apply to other programming languages. GCC will be used as the reference compiler throughout this article. While any compiler conforming to the C standard could be used, GCC was chosen because of its widespread adoption and availability on Linux systems.

The ELF format

Presentation

Let’s compile our code:

1
❯ gcc demo.c -o demo

GCC output is not raw machine code: GCC produces Executable and Linkable Format files (aka ELF), the Linux equivalent of Windows’ .exe files. ELF files do include the program’s machine code, of course, but they also provide a lot of additional information about our program. To navigate through such a file, we can use a very handy program, readelf.

An ELF file starts with a global header (ELF header in elf(5)): it gives global information about the file, and it is also the starting point for programs such as readelf to understand how to read the file. Let’s use it on demo:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
❯ readelf -hW demo
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              DYN (Position-Independent Executable file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x1060
  Start of program headers:          64 (bytes into file)
  Start of section headers:          14016 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           56 (bytes)
  Number of program headers:         13
  Size of section headers:           64 (bytes)
  Number of section headers:         31
  Section header string table index: 30

-h is used to only display the global header. -W is used for better readability. All options are described in readelf(1).

We now know precisely what this file is: it is a 64-bit ELF file, compiled to run on UNIX systems with the System V ABI, on x86-64 processors (the meaning of these terms will be explained in the following sections). We are also given the offset in the file of program headers and section headers. Those are important ELF concepts, so let’s define them:

  • Program headers: This is what the OS will use to understand how to load the program. For example, the LOAD headers refer to portions of code: they indicate where they are located within the ELF, and where they should be loaded in memory.
1
2
3
4
5
6
❯ readelf -lW demo | grep -E 'LOAD|FileSiz'
  Type           Offset   VirtAddr           PhysAddr           FileSiz  MemSiz   Flg Align
  LOAD           0x000000 0x0000000000000000 0x0000000000000000 0x000640 0x000640 R   0x1000
  LOAD           0x001000 0x0000000000001000 0x0000000000001000 0x000191 0x000191 R E 0x1000
  LOAD           0x002000 0x0000000000002000 0x0000000000002000 0x000144 0x000144 R   0x1000
  LOAD           0x002db0 0x0000000000003db0 0x0000000000003db0 0x000260 0x000268 RW  0x1000
  • Section headers: You can think of sections as logical containers that organize the contents of the program. They are mainly used by the compiler as well as the dynamic linker, which we will cover later on.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
❯ readelf -SW demo | head -15 | tail -13 | cut -c1-70
Section Headers:
  [Nr] Name              Type            Address          Off    Size
  [ 0]                   NULL            0000000000000000 000000 00000
  [ 1] .interp           PROGBITS        0000000000000318 000318 00001
  [ 2] .note.gnu.property NOTE            0000000000000338 000338 0000
  [ 3] .note.gnu.build-id NOTE            0000000000000368 000368 0000
  [ 4] .note.ABI-tag     NOTE            000000000000038c 00038c 00002
  [ 5] .gnu.hash         GNU_HASH        00000000000003b0 0003b0 00002
  [ 6] .dynsym           DYNSYM          00000000000003d8 0003d8 0000a
  [ 7] .dynstr           STRTAB          0000000000000480 000480 00008
  [ 8] .gnu.version      VERSYM          000000000000050e 00050e 00000
  [ 9] .gnu.version_r    VERNEED         0000000000000520 000520 00003
  [10] .rela.dyn         RELA            0000000000000550 000550 0000d

Program loading

Armed with this new knowledge, we are now ready to dive into the depths of how Linux loads our program!

Statically linked programs

Code loading

The first thing the OS does, when a program is started with execve(2), is to make sure the program is compatible with the current machine. As we’ve seen, the ELF global header will be a great help for that. As statically linked programs are rather simple, the entire setup is quite simple too. All the OS has to do is to load the code from the ELF into memory (RAM). As mentioned earlier, the relevant information is located in the LOAD segments from the program headers we listed above. Let’s break them down (see PT_LOAD and the Elf64_Phdr fields in elf(5)):

  • Offset: where in the ELF file this segment starts
  • VirtAddr: where this segment should be loaded in memory
  • PhysAddr: irrelevant/unused on Linux
  • FileSiz: size of the segment in the ELF
  • MemSiz: size of the segment in memory
  • Flg: protection flags

The OS will then perform something like memcpy(VirtAddr, ELF_start_address+offset, FileSiz). FileSiz may be less than MemSiz (see the last segment). This simply means that the extra bytes should be zeroed. This is especially useful for the BSS section, which contains all the data that should be zeroed at program start. Instead of storing all those zeros inside the ELF, we simply indicate a MemSiz greater than FileSiz.

Finally, Flg indicates the type of memory protection that should be applied to each segment:

  • R: Read
  • W: Write
  • E: Executable

Three combinations are common:

  • RE: for sections that should be executed but not modified, typically code
  • R: for read-only data, such as string literals
  • RW: for data sections, where most variables live

Paging

The aforementioned mechanism creates a big issue: if a program requires its code to be loaded at specific addresses, how can we run two instances of the same program? Both instances cannot live at the same place at the same time! So what can we do about it? The answer lies in a memory mechanism at the core of x86 CPUs, paging.

To understand paging, we first need to explain how the CPU manages memory. The main memory, the one that lives in your RAM, is referred to as physical memory. Physical memory is divided into fixed-size portions, called frames. Frames are the smallest amount of memory the CPU can manipulate. If you want to allocate or deallocate memory, or change access rights, you can only do it on entire frames. The memory can then be represented like so, given a frame size of 0x1000:

Address Frame
0x0000 0x0
0x1000 0x1
… …

Any data stored in memory has a physical address; this is the location where the data is stored inside the physical memory. A physical address can be represented by the index of its frame along with the offset within that frame. For example, the address 0xab123 is within frame 0xab at offset 0x123. When accessing the address, the CPU first checks that you have the required access rights to read/write/execute that frame, depending on the context. If you do, it then adds the offset to the frame beginning address in order to get the exact memory location.

Paging introduces a new concept: pages. A page is simply a reference to an arbitrary frame. For example, page 0xab could be a reference to frame 0xdc. Let’s see how paging works with the address 0xab123. When paging is enabled, 0xab is no longer interpreted as a frame index; it becomes a page index. Any data inside page 0xab is physically stored in frame 0xdc. In this system, 0xab123 no longer represents the physical address where the data is stored. Such addresses are called virtual addresses.

Paging allows us to shape the address space however we want: by changing the frame a page points to, we change the meaning of all virtual addresses within that page; we make them point elsewhere in physical memory. It is worth noting that paging makes it possible to create contiguous ranges of virtual memory that refer to non-contiguous physical memory. For example:

Virtual address Page Frame pointed to by page Physical Address
0x0000 0x0 0xa 0xa000
0x1000 0x1 0x2 0x2000
… … … …

The relation between pages and frames is stored in a data structure called a page table. It is a giant page_index->frame_index mapping. The OS is the only program authorized to manipulate page tables.

Now let’s get back to our original question: how can two identical programs run at the same time, knowing that they should be loaded at the exact same address? In practice, all programs use virtual addresses. Any address we manipulate actually points to an arbitrary physical address. The answer to our question is then quite straightforward: the OS constructs a different set of page tables per program. Virtual addresses may be similar across two programs, but the OS arranges page tables so that the underlying physical addresses do not overlap. When it asks the CPU to execute an instance of a program, it also tells it which page tables to use. That way, the same (virtual) address in each program actually refers to a different physical address!

Dynamically linked programs

Dynamically linked programs require a slightly more elaborate setup, as they are not self-sufficient. Notice that everything we discussed in the ‘Statically linked programs’ paragraph also applies to dynamically linked programs.

The DYNAMIC segment

Most information related to the ‘dynamic’ part of a program is stored in the dynamic table, whose entries are listed under Dynamic tags in elf(5). This table is quite big, so we won’t be able to cover all of its content. We’ll focus on the most interesting parts.

Dependencies

Dependencies are registered in ‘NEEDED’ entries of the table. For example, demo depends on libc.so.6:

1
2
❯ readelf -dW demo | grep libc
 0x0000000000000001 (NEEDED)             Shared library: [libc.so.6]

Relocations

Relocations are a way of filling in missing information at runtime (even though they are also widely used at compile-time, but this is out of scope). When a program is compiled, it has no idea where its dependencies will be loaded in memory at load time. This is why relocations exist: the program lists the addresses it is missing and where they should be written so that it can use them. Every relocation type is defined in section 4.4 of the System V ABI. Let’s review the ones in demo:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
❯ readelf -rW demo

Relocation section '.rela.dyn' at offset 0x550 contains 9 entries:
    Offset             Info             Type               Symbol's Value  Symbol's Name + Addend
0000000000003db0  0000000000000008 R_X86_64_RELATIVE                         1140
0000000000003db8  0000000000000008 R_X86_64_RELATIVE                         1149
0000000000003dc0  0000000000000008 R_X86_64_RELATIVE                         1100
0000000000004008  0000000000000008 R_X86_64_RELATIVE                         4008
0000000000003fd8  0000000100000006 R_X86_64_GLOB_DAT      0000000000000000 __libc_start_main@GLIBC_2.34 + 0
0000000000003fe0  0000000200000006 R_X86_64_GLOB_DAT      0000000000000000 _ITM_deregisterTMCloneTable + 0
0000000000003fe8  0000000400000006 R_X86_64_GLOB_DAT      0000000000000000 __gmon_start__ + 0
0000000000003ff0  0000000500000006 R_X86_64_GLOB_DAT      0000000000000000 _ITM_registerTMCloneTable + 0
0000000000003ff8  0000000600000006 R_X86_64_GLOB_DAT      0000000000000000 __cxa_finalize@GLIBC_2.2.5 + 0

Relocation section '.rela.plt' at offset 0x628 contains 1 entry:
    Offset             Info             Type               Symbol's Value  Symbol's Name + Addend
0000000000003fd0  0000000300000007 R_X86_64_JUMP_SLOT     0000000000000000 puts@GLIBC_2.2.5 + 0
  • R_X86_64_RELATIVE: Those entries exist for the program to relocate itself. Indeed, our program is position-independent (see Type in its ELF header). That means it can be loaded at any address, called the load_address (or base_address). R_X86_64_RELATIVE entries help it know the absolute address of some of its own symbols. For example, the first entry means “At this memory address, write: load_address + 1140”.

The other types of relocations are tied to the Global Offset Table (GOT, ABI section 5.2). The GOT is a table of addresses, which is loaded in memory and filled at load time. It contains addresses the program will need at runtime to access symbols it didn’t know the address of at compile time.

  • R_X86_64_GLOB_DAT: All the symbols of this type of relocation we saw in demo come from libc. They are initialization/cleanup-related functions our program will call. Here, the program asks to fill the corresponding GOT entry of each of those symbols with their address. To understand the process better, let’s first see what happens when calling a regular function we know the address of. To do that, I’ll use objdump, a program that displays assembly code out of ELF files:
1
2
3
4
5
6
❯ cat test2.c
void a () {}                    // A dummy function that does nothing
int main() { a(); return 0; }   // We just call a and quit
❯ gcc -o test2 test2.c -g
❯ objdump -d --no-show-raw-insn test2 | grep 'call.*<a>'
    1141:	call   1129 <a>

Explanation: this line calls the function at address 0x1129, which turns out to be a.

The code does nothing but “Call the function at that well known specific address”. Now if we take a quick look at the assembly code of demo, here is what we see:

1
2
❯ objdump -d --no-show-raw-insn demo | grep 'libc_start'
    107f:	call   *0x2f53(%rip)        # 3fd8 <__libc_start_main@GLIBC_2.34>

Explanation: this line calls the function whose address is stored at RIP + 0x2f53. RIP is the instruction pointer; it contains the address of the current instruction (here 0x107f).

RIP + 0x2f53 is the GOT entry that the R_X86_64_GLOB_DAT relocation asks to fill. That way, we provide the address of the function that the code will call at runtime!

  • R_X86_64_JUMP_SLOT: This is a slightly more complex relocation type that allows lazy binding. Binding is the process of associating a symbol (here puts) with its address. Binding can be either eager or lazy. Eager binding consists of binding all symbols at load time. Lazy binding only binds symbols when they are first used, at runtime. The GOT entry of lazily bound symbols is then not filled with the symbol address, but rather with the address of a function responsible for actually binding the symbol. That way, the program starts immediately without its symbols being bound. If a symbol is accessed at runtime, the binder function will then be called, performing the actual binding. Eager binding can be forced with LD_BIND_NOW (see ld.so(8)).

INIT and FINI

We continue our exploration of the DYNAMIC segment with INIT and FINI functions:

1
2
3
4
5
6
7
❯ readelf -dW demo | grep -E 'INIT|FINI'
 0x000000000000000c (INIT)               0x1000
 0x000000000000000d (FINI)               0x1184
 0x0000000000000019 (INIT_ARRAY)         0x3db0
 0x000000000000001b (INIT_ARRAYSZ)       16 (bytes)
 0x000000000000001a (FINI_ARRAY)         0x3dc0
 0x000000000000001c (FINI_ARRAYSZ)       8 (bytes)

Init functions are meant to be executed before main. For example, this is where you find the code that will initialize global variables. INIT contains a single function address, while INIT_ARRAY is an array of function addresses. As their differences are subtle and historical, we won’t cover them today. The only thing you need to know is that it is mandatory that all of those functions are executed BEFORE main. Now, do you remember the weird function inside demo.c?

1
2
3
4
__attribute__((constructor)) void i_run_before_main()
{
    printf("hello from that weird function\n");
}

Well, now you can understand why it runs before main. The attribute constructor instructs GCC to include the address of that function inside INIT_ARRAY, allowing it to run before main! Similarly, FINI and FINI_ARRAY contain addresses of functions that must run AFTER main.

Program interpreter

Here is the workflow we covered so far:

Step Entity responsible
Source code Developer
ELF GCC
Code loading OS
Dynamically linked executables specific setup Interpreter

A new challenger has entered the arena: the Interpreter. It is responsible for all the preparation needed by dynamically linked programs. Its presence is indicated by the INTERP program header (PT_INTERP in elf(5)):

1
2
3
❯ readelf -lW demo | grep -A1 INTERP
  INTERP         0x000318 0x0000000000000318 0x0000000000000318 0x00001c 0x00001c R   0x1
      [Requesting program interpreter: /lib64/ld-linux-x86-64.so.2]

When you ask your OS to start a program, it loads its code AS WELL AS the interpreter (execve(2)). Execution is subsequently handed over to the interpreter rather than the program itself. The interpreter (ld.so(8)) will then perform:

  • self-relocation
  • recursive dependency loading
  • relocation processing
  • calling INIT and INIT_ARRAY functions (for statically linked programs, the program calls them itself)
  • jumping to the main program entry point

Stack setup

Our program is now very close to being ready, but it still lacks a very important step: stack setup. The initial stack layout is governed by the Application Binary Interface (ABI). An ABI is “an interface exposed by software that is defined for in-process machine code access”, as Wikipedia puts it. Basically, it is a collection of rules that define how programs interact with each other and with the OS. It specifies things such as how function calls are made, how data types are laid out in memory, how binaries are structured… AND what the initial stack layout of a process should be. Our program uses the System V ABI (see OS/ABI in its ELF header).

Figure 3.9 of the ABI defines the mandatory stack layout. It is the responsibility of the OS to allocate memory for the stack, set the stack pointer rsp to that address, and fill the stack with the aforementioned information. Among other things, we find:

  • argc: the number of arguments
  • argv: an array of argument pointers
  • envp: an array of environment variable pointers (for example MY_VARIABLE=1 in MY_VARIABLE=1 ./my_program)
  • auxiliary vector: this array contains information about the main program. This is mainly useful for the OS to transmit information to the interpreter.

Time for main?

This section is specific to C/C++ programs

We now have everything we need! Code is loaded along with its dependencies and relocations have been processed. Let’s run main! The dynamic linker (or the OS if no interpreter is required) asks the CPU to jump to the program entry point, whose address is given by the ELF header: 0x1060. Surprisingly, 0x1060 is not the address of main. Indeed, main is at 0x1163:

1
2
❯ objdump -d --no-show-raw-insn demo | grep 'main' | tail -1
0000000000001163 <main>:

So what is there at 0x1060 then? Let’s see:

1
2
❯ objdump -d --no-show-raw-insn demo | grep '1060' | head -1
0000000000001060 <_start>:

_start is the actual entry point of our program. Its goal is to initialize the C runtime, the environment required for a C program to run. Its main goals are:

  • Calling constructors (cf. INIT and INIT_ARRAY), such as:
    • User registered constructors (e.g. __attribute__((constructor)))
    • C++ global variable constructors
    • Global variables that require dynamic initialization, like int x = some_function()
  • Calling the libc initialization routine, __libc_start_main
  • Grabbing argc and argv from the stack
  • Jumping to main (finally!)

We are left with a genuine question: where does _start come from? It is not part of the source code!

_start is part of a collection of files which together contain the whole C runtime initialization and cleanup code. Those files are automatically included in a program during compilation (unless -nostartfiles is used). Here are the ones used in demo:

1
2
3
4
5
6
❯ gcc demo.c -o demo -v 2>&1 | grep -o 'crt[^.]*\.o'
crt1.o
crti.o
crtbeginS.o
crtendS.o
crtn.o

Here, “crt” stands for “C RunTime”.

Wrapping up

We made it: main has finally been called! Let’s review the main steps involved in the execution of an ELF:

  • code loading: the OS loads the code into memory following LOAD segments
  • stack allocation and setup
  • for dynamically linked programs only, the interpreter is loaded, and it will perform:
    • self-relocation
    • recursive dependency loading
    • relocation processing
    • jumping to the main program entry point

You now have a solid understanding of what happens under the hood when you start your programs on Linux x86-64. Maybe this will help you realize how blazingly fast modern CPUs and OSs are, considering that so many steps are required to perform an action as simple as starting a program!

Bibliography