Compilers, Assemblers, Linkers

Regardless of OS, the program has to pass 4 stages to make a running executable

1. Preprocessing is the first pass of any C compilation. It processes include-files, conditional compilation instructions and macros.

2. Compilation is the second pass. It takes the output of the preprocessor, and the source code, and generates assembler source code.

3. Assembly is the third stage of compilation. It takes the assembly source code and produces an assembly listing with offsets. The assembler output is stored in an object file.

4. Linking is the final stage of compilation. It takes one or more object files or libraries as input and combines them to produce a single (usually executable) file. In doing so, it resolves references to external symbols, assigns final addresses to procedures/functions and variables, and revises code and data to reflect new addresses (a process called relocation)

ELF - (Executable and Linking Format) is file format that defines how an object file is composed and organized. With this information, your kernel and the binary loader know how to load the file, where to look for the code, where to look the initialized data, which shared library that needs to be loaded and so on.

Different sections in an executable format are:

Section	Description
.text	This section contains the executable instruction codes and is shared among every process running the same binary. This section usually has READ and EXECUTE permissions only. This section is the one most affected by optimization.
.bss	BSS stands for ‘Block Started by Symbol’. It holds un-initialized global and static variables. Since the BSS only holds variables that don't have any values yet, it doesn't actually need to store the image of these variables. The size that BSS will require at runtime is recorded in the object file, but the BSS (unlike the data section) doesn't take up any actual space in the object file.
.data	Contains the initialized global and static variables and their values. It is usually the largest part of the executable. It usually has READ/WRITE permissions.
.rdata	Also known as .rodata (read-only data) section. This contains constants and string literals.
.reloc	Stores the information required for relocating the image while loading.
Symbol table	A symbol is basically a name and an address. Symbol table holds information needed to locate and relocate a program’s symbolic definitions and references. A symbol table index is a subscript into this array. Index 0 both designates the first entry in the table and serves as the undefined symbol index. The symbol table contains an array of symbol entries.
Relocation records	Relocation is the process of connecting symbolic references with symbolic definitions. For example, when a program calls a function, the associated call instruction must transfer control to the proper destination address at execution. Re-locatable files must have relocation entries’ which are necessary because they contain information that describes how to modify their section contents, thus allowing executable and shared object files to hold the right information for a process's program image. Simply said relocation records are information used by the linker to adjust section contents.

Good link describing the use of readelf and object dump:

Process Loading:

• Before we can run an executable, firstly we have to load it into memory.

• This is done by the loader, which is generally part of the operating system. The loader does the following things (from other things):

1. Memory and access validation - Firstly, the OS system kernel reads in the program file’s header information and does the validation for type, access permissions, memory requirement and its ability to run its instructions. It confirms that file is an executable image and calculates memory requirements.

2. Process setup includes:

1. Allocates primary memory for the program's execution.

2. Copies address space from secondary to primary memory.

3. Copies the .text and .data sections from the executable into primary memory.

4. Copies program arguments (e.g., command line arguments) onto the stack.

5. Initializes registers: sets the esp (stack pointer) to point to top of stack, clears the rest.

6. Jumps to start routine, which: copies main()'s arguments off of the stack, and jumps to main().

• Address space is memory space that contains program code, stack, and data segments or in other word, all data the program uses as it runs.

• The memory layout, consists of three segments (text, data, and stack), in simplified form is shown in Figure w.5.

• The dynamic data segment is also referred to as the heap, the place dynamically allocated memory (such as from malloc() and new) comes from. Dynamically allocated memory is memory allocated at run time instead of compile/link time.

• This organization enables any division of the dynamically allocated memory between the heap (explicitly) and the stack (implicitly). This explains why the stack grows downward and heap grows upward.

  • Before we can run an executable, firstly we have to load it into memory.

  • This is done by the loader, which is generally part of the operating system. The loader does the following things (from other things):

  1. Memory and access validation - Firstly, the OS system kernel reads in the program file’s header information and does the validation for type, access permissions, memory requirement and its ability to run its instructions. It confirms that file is an executable image and calculates memory requirements.

  2. Process setup includes:

  1. Allocates primary memory for the program's execution.

  2. Copies address space from secondary to primary memory.

  3. Copies the .text and .data sections from the executable into primary memory.

  4. Copies program arguments (e.g., command line arguments) onto the stack.

  5. Initializes registers: sets the esp (stack pointer) to point to top of stack, clears the rest.

  6. Jumps to start routine, which: copies main()'s arguments off of the stack, and jumps to main().

• Address space is memory space that contains program code, stack, and data segments or in other word, all data the program uses as it runs.

• The memory layout, consists of three segments (text, data, and stack), in simplified form is shown in Figure w.5.

• The dynamic data segment is also referred to as the heap, the place dynamically allocated memory (such as from malloc() and new) comes from. Dynamically allocated memory is memory allocated at run time instead of compile/link time.

• This organization enables any division of the dynamically allocated memory between the heap (explicitly) and the stack (implicitly). This explains why the stack grows downward and heap grows upward.

Run time data structure: From sections to segments

• A process is a running program. This means that the operating system has loaded the executable file for the program into memory, has arranged it to have access to its command-line arguments and environment variables, and has started it running.

• Typically a process has 5 different areas of memory allocated to it as listed in Table w.5 (refer to Figure w.4):

Segment	Description
Code - text segment	Often referred to as the text segment, this is the area in which the executable instructions reside. For example, Linux/Unix arranges things so that multiple running instances of the same program share their code if possible. Only one copy of the instructions for the same program resides in memory at any time. The portion of the executable file containing the text segment is the text section.
Initialized data – data segment	Statically allocated and global data that are initialized with nonzero values live in the data segment. Each process running the same program has its own data segment. The portion of the executable file containing the data segment is the data section.
Uninitialized data – bss segment	BSS stands for ‘Block Started by Symbol’. Global and statically allocated data that initialized to zero by default are kept in what is called the BSS area of the process. Each process running the same program has its own BSS area. When running, the BSS data are placed in the data segment. In the executable file, they are stored in the BSS section. For Linux/Unix the format of an executable, only variables that are initialized to a nonzero value occupy space in the executable’s disk file.
Heap	The heap is where dynamic memory (obtained by malloc(), calloc(), realloc() and new for C++) comes from. Everything on a heap is anonymous, thus you can only access parts of it through a pointer. As memory is allocated on the heap, the process’s address space grows. Although it is possible to give memory back to the system and shrink a process’s address space, this is almost never done because it will be allocated to other process again. Freed memory (free() and delete) goes back to the heap, creating what is called holes. It is typical for the heap to grow upward. This means that successive items that are added to the heap are added at addresses that are numerically greater than previous items. It is also typical for the heap to start immediately after the BSS area of the data segment. The end of the heap is marked by a pointer known as the break. You cannot reference past the break. You can, however, move the break pointer (via brk() and sbrk() system calls) to a new position to increase the amount of heap memory available.
Stack	The stack segment is where local (automatic) variables are allocated. In C program, local variables are all variables declared inside the opening left curly brace of a function body including the main() or other left curly brace that aren’t defined as static. The data is popped up or pushed into the stack following the Last In First Out (LIFO) rule. The stack holds local variables, temporary information, function parameters, return address and the like. When a function is called, a stack frame (or a procedure activation record) is created and PUSHed onto the top of the stack. This stack frame contains information such as the address from which the function was called and where to jump back to when the function is finished (return address), parameters, local variables, and any other information needed by the invoked function. The order of the information may vary by system and compiler. When a function returns, the stack frame is POPped from the stack. Typically the stack grows downward, meaning that items deeper in the call chain are at numerically lower addresses and toward the heap.
Table w.5

• When a program is running, the initialized data, BSS and heap areas are usually placed into a single contiguous area called a data segment.

• The stack segment and code segment are separate from the data segment and from each other as illustrated in Figure w.4.

• Although it is theoretically possible for the stack and heap to grow into each other, the operating system prevents that event.

• The relationship among the different sections/segments is summarized in Table w.6, executable program segments and their locations.

Executable file section (disk file)	Address space segment	Program memory segment
.text	Text	Code
.data	Data	Initialized data
.bss	Data	BSS
-	Data	Heap
-	Stack	Stack

The Process:

• The diagram below shows the memory layout of a typical C’s process. The process load segments (corresponding to "text" and "data" in the diagram) at the process's base address.

• The main stack is located just below and grows downwards. Any additional threads or function calls that are created will have their own stacks, located below the main stack.

• Each of the stack frames is separated by a guard page to detect stack overflows among stacks frame. The heap is located above the process and grows upwards.

• In the middle of the process's address space, there is a region is reserved for shared objects. When a new process is created, the process manager first maps the two segments from the executable into memory.

• It then decodes the program's ELF header. If the program header indicates that the executable was linked against a shared library, the process manager will extract the name of the dynamic interpreter from the program header.

• The dynamic interpreter points to a shared library that contains the runtime linker code. The process manager will load this shared library in memory and will then pass control to the runtime linker code in this library.