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:
|
|
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:
|
|
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:
|
|
-his used to only display the global header.-Wis 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
LOADheaders refer to portions of code: they indicate where they are located within the ELF, and where they should be loaded in memory.
|
|
- 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.
|
|
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:
|
|
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:
|
|
- R_X86_64_RELATIVE: Those entries exist for the program to relocate
itself. Indeed, our program is position-independent (see
Typein 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
democome 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:
|
|
Explanation: this line calls the function at address
0x1129, which turns out to bea.
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:
|
|
Explanation: this line calls the function whose address is stored at
RIP + 0x2f53.RIPis the instruction pointer; it contains the address of the current instruction (here0x107f).
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 withLD_BIND_NOW(see ld.so(8)).
INIT and FINI
We continue our exploration of the DYNAMIC segment with INIT and FINI functions:
|
|
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?
|
|
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)):
|
|
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=1inMY_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:
|
|
So what is there at 0x1060 then? Let’s see:
|
|
_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()
- User registered constructors (e.g.
- Calling the libc initialization routine,
__libc_start_main - Grabbing
argcandargvfrom 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:
|
|
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!