|< The main() and command line arguments | Main | C Memory Allocation and De-allocation Functions >| Site Index | Download |


 

 

 

 

COMPILER, ASSEMBLER, LINKER AND LOADER:

A BRIEF STORY

 

 

 

 

 

 

 

 

 

 

 

 

 

My Training Period: xx hours

 

Note:

This Module presents quite a detail story of a process (running program). However, it is an excerpt from more complete, Tenouk's buffer overflow Tutorial. It tries to investigate how the C/C++ source codes preprocessed, compiled, linked and loaded as a running program.  It is based on the GCC (GNU Compiler Collection).  When you use the IDE (Integrated Development Environment) compilers such as Microsoft Visual C++, Borland C++ Builder etc. the processes discussed here quite transparent.  The commands and examples of the gcc, gdb, g++, gas and friends are discussed in Linux gnu gcc, g++, gdb and gas 1 and Linux gnu gcc, g++, gdb and gas 2.  Have a nice day!

 

The C compiler ability:

  • Able to understand and appreciate the processes involved in preprocessing, compiling, linking, loading and running C/C++ programs.

 

W.1  COMPILERS, ASSEMBLERS and LINKERS

  • Normally the C’s program building process involves four stages and utilizes different ‘tools’ such as a preprocessor, compiler, assembler, and linker.

  • At the end there should be a single executable file.  Below are the stages that happen in order regardless of the operating system/compiler and graphically illustrated in Figure w.1.

  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).

  • Bear in mind that if you use the IDE type compilers, these processes quite transparent.

  • Now we are going to examine more details about the process that happen before and after the linking stage.  For any given input file, the file name suffix (file extension) determines what kind of compilation is done and the example for GCC is listed in Table w.1.

  • In UNIX/Linux, the executable or binary file doesn’t have extension whereas in Windows the executables for example may have .exe, .com and .dll.

File extension

Description

file_name.c

C source code which must be preprocessed.

file_name.i

C source code which should not be preprocessed.

file_name.ii

C++ source code which should not be preprocessed.

file_name.h

C header file (not to be compiled or linked).

file_name.cc

file_name.cp

file_name.cxx

file_name.cpp

file_name.c++

file_name.C

C++ source code which must be preprocessed.  For file_name.cxx, the xx must both be literally character x and file_name.C, is capital c.

file_name.s

Assembler code.

file_name.S

Assembler code which must be preprocessed.

file_name.o

Object file by default, the object file name for a source file is made by replacing the extension .c, .i, .s etc with .o

 

Table w.1

  • The following Figure shows the steps involved in the process of building the C program starting from the compilation until the loading of the executable image into the memory for program running.

Compiler assembler linker and loader

 

Figure w.1:  Compile, link and execute stages for running program (a process)

 

W.2  OBJECT FILES and EXECUTABLE

  • After the source code has been assembled, it will produce an Object files (e.g. .o, .obj) and then linked, producing an executable files.

  • An object and executable come in several formats such as ELF (Executable and Linking Format) and COFF (Common Object-File Format).  For example, ELF is used on Linux systems, while COFF is used on Windows systems.

  • Other object file formats are listed in the following Table.

Object File Format

Description

a.out

The a.out format is the original file format for Unix.  It consists of three sections: text, data, and bss, which are for program code, initialized data, and uninitialized data, respectively.  This format is so simple that it doesn't have any reserved place for debugging information.  The only debugging format for a.out is stabs, which is encoded as a set of normal symbols with distinctive attributes.

COFF

The COFF (Common Object File Format) format was introduced with System V Release 3 (SVR3) Unix. COFF files may have multiple sections, each prefixed by a header. The number of sections is limited.  The COFF specification includes support for debugging but the debugging information was limited.  There is no file extension for this format.

ECOFF

A variant of COFF.  ECOFF is an Extended COFF originally introduced for Mips and Alpha workstations.

XCOFF

The IBM RS/6000 running AIX uses an object file format called XCOFF (eXtended COFF). The COFF sections, symbols, and line numbers are used, but debugging symbols are dbx-style stabs whose strings are located in the .debug section (rather than the string table).  The default name for an XCOFF executable file is a.out.

PE

Windows 9x and NT use the PE (Portable Executable) format for their executables.  PE is basically COFF with additional headers.  The extension normally .exe.

ELF

The ELF (Executable and Linking Format) format came with System V Release 4 (SVR4) Unix.  ELF is similar to COFF in being organized into a number of sections, but it removes many of COFF's limitations.  ELF used on most modern Unix systems, including GNU/Linux, Solaris and Irix. Also used on many embedded systems.

SOM/ESOM

SOM (System Object Module) and ESOM (Extended SOM) is HP's object file and debug format (not to be confused with IBM's SOM, which is a cross-language Application Binary Interface - ABI).

 

Table w.2

 

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.

 

Table w.3:  Segments in executable file

/* testprog1.c */

#include <stdio.h>

static void display(int i, int *ptr);

 

int main(void)

{

      int x = 5;

      int *xptr = &x;

      printf("In main() program:\n");

      printf("x value is %d and is stored at address %p.\n", x, &x);

      printf("xptr pointer points to address %p which holds a value of %d.\n", xptr, *xptr);

      display(x, xptr);

      return 0;

}

 

void display(int y, int *yptr)

{

      char var[7] = "ABCDEF"; 

      printf("In display() function:\n");

      printf("y value is %d and is stored at address %p.\n", y, &y);

      printf("yptr pointer points to address %p which holds a value of %d.\n", yptr, *yptr);

}

 

[bodo@bakawali test]$ gcc -c testprog1.c

[bodo@bakawali test]$ readelf -a testprog1.o

ELF Header:

  Magic:   7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00

  Class:                                  ELF32

  Data:                                   2's complement, little endian

  Version:                                1 (current)

  OS/ABI:            UNIX - System V

  ABI Version:              0

  Type:              REL (Relocatable file)

  Machine:           Intel 80386

  Version:           0x1

  Entry point address:      0x0

  Start of program headers: 0 (bytes into file)

  Start of section headers: 672 (bytes into file)

  Flags:                    0x0

  Size of this header:      52 (bytes)

  Size of program headers:  0 (bytes)

  Number of program headers:       0

  Size of section headers:         40 (bytes)

  Number of section headers:       11

  Section header string table index:      8

 

Section Headers:

  [Nr] Name          Type          Addr     Off        Size     ES Flg Lk Inf Al

  [ 0]               NULL          00000000 000000 000000 00      0   0  0

  [ 1] .text         PROGBITS      00000000 000034 0000de 00  AX   0   0  4

  [ 2] .rel.text     REL           00000000 00052c 000068 08      9   1  4

  [ 3] .data         PROGBIT       00000000 000114 000000 00         WA  0   0  4

  [ 4] .bss          NOBIT         00000000 000114 000000 00  WA  0   0  4

  [ 5] .rodata              PROGBITS      00000000 000114 00010a 00      A  0   0  4

  [ 6] .note.GNU-stack      PROGBITS      00000000 00021e 000000 00      0   0  1

  [ 7] .comment      PROGBITS      00000000 00021e 000031 00      0   0  1

  [ 8] .shstrtab     STRTAB 00000000 00024f 000051 00       0   0  1

  [ 9] .symtab              SYMTAB 00000000 000458 0000b0 10     10  9  4

  [10] .strtab              STRTAB 00000000 000508 000021 00      0   0  1

Key to Flags:

  W (write), A (alloc), X (execute), M (merge), S (strings)

  I (info), L (link order), G (group), x (unknown)

  O (extra OS processing required) o (OS specific), p (processor specific)

 

There are no program headers in this file.

 

Relocation section '.rel.text' at offset 0x52c contains 13 entries:

 Offset       Info                 Type   Sym.Value  Sym. Name

0000002d  00000501 R_386_32 00000000   .rodata

00000032  00000a02 R_386_PC32      00000000   printf

00000044  00000501 R_386_32 00000000   .rodata

00000049  00000a02 R_386_PC32      00000000   printf

0000005c  00000501 R_386_32 00000000   .rodata

00000061  00000a02 R_386_PC32      00000000   printf

0000008c  00000501 R_386_32 00000000   .rodata

0000009c  00000501 R_386_32 00000000   .rodata

000000a1  00000a02 R_386_PC32      00000000   printf

000000b3  00000501 R_386_32 00000000   .rodata

000000b8  00000a02 R_386_PC32      00000000   printf

000000cb  00000501 R_386_32 00000000   .rodata

000000d0  00000a02 R_386_PC32      00000000   printf

 

There are no unwind sections in this file.

 

Symbol table '.symtab' contains 11 entries:

   Num:    Value     Size Type    Bind        Vis             Ndx Name

     0: 00000000     0 NOTYPE  LOCAL  DEFAULT  UND

     1: 00000000     0 FILE    LOCAL  DEFAULT  ABS testprog1.c

     2: 00000000     0 SECTION LOCAL  DEFAULT    1

     3: 00000000     0 SECTION LOCAL  DEFAULT    3

     4: 00000000     0 SECTION LOCAL  DEFAULT    4

     5: 00000000     0 SECTION LOCAL  DEFAULT    5

     6: 00000080     94 FUNC   LOCAL  DEFAULT    1 display

     7: 00000000     0 SECTION LOCAL  DEFAULT    6

     8: 00000000     0 SECTION LOCAL  DEFAULT    7

     9: 00000000     128 FUNC  GLOBAL DEFAULT    1 main

    10: 00000000     0 NOTYPE  GLOBAL DEFAULT  UND printf

 

No version information found in this file.

 

Section

Description

1

Text (.section .text)

Contain code (instructions).

Contain the _start label.

2

Read-Only Data (.section .rodata)

Contains pre-initialized constants.

3

Read-Write Data (.section .data)

Contains pre-initialized variables.

4

BSS (.section .bss)

Contains un-initialized data.

 

Table w.4

;initializing data

 

 

.section

.data

 

x:

.byte

128

;one byte initialized to 128

y:

.long

1,1000,10000

;3 long words

 

 

 

 

;initializing ascii data

 

 

.ascii

"hello"

;ascii without null character

 

asciz

"hello"

;ascii with \0

 

 

 

 

;allocating memory in bss

 

 

.section

.bss

 

 

.equ

BUFFSIZE 1024

;define a constant

 

.comm

z, 4, 4

;allocate 4 bytes for x with

;4-byte alignment

 

 

 

 

;making symbols externally visible

 

 

.section

.data

 

 

.globl

w

;declare externally visible

;e.g: int w = 10

 

.text

 

 

 

.globl

fool

;e.g: fool(void) {…}

fool:

 

 

 

 

 

 

 

leave

 

 

 

return

 

 

 

W.3  RELOCATION RECORDS

W.4  SYMBOL TABLE

Relocation record and symbol table

 

Figure w.2: The relocation record

 

W.5  LINKING

Linking all together by linker

 

Figure w.3:  The object files linking process

 

W.5.1  SHARED OBJECTS

  • In a typical system, a number of programs will be running. Each program relies on a number of functions, some of which will be standard C library functions, like printf(), malloc(), strcpy(), etc. and some are non-standard or user defined functions.

  • If every program uses the standard C library, it means that each program would normally have a unique copy of this particular library present within it. Unfortunately, this result in wasted resources, degrade the efficiency and performance.

  • Since the C library is common, it is better to have each program reference the common, one instance of that library, instead of having each program contain a copy of the library.

  • This is implemented during the linking process where some of the objects are linked during the link time whereas some done during the run time (deferred/dynamic linking).

W.5.2  STATICALLY LINKED

  • The term ‘statically linked’ means that the program and the particular library that it’s linked against are combined together by the linker at link time.

  • This means that the binding between the program and the particular library is fixed and known at link time before the program run. It also means that we can't change this binding, unless we re-link the program with a new version of the library.

 

gcc –static filename.c –o filename

W.5.3  DYNAMICALLY LINKED

  1. Program files (on disk) become much smaller because they need not hold all necessary text and data segments information.  It is very useful for portability.

  2. Standard libraries may be upgraded or patched without every one program need to be re-linked.  This clearly requires some agreed module-naming convention that enables the dynamic linker to find the newest, installed module such as some version specification.  Furthermore the distribution of the libraries is in binary form (no source), including dynamically linked libraries (DLLs) and when you change your program you only have to recompile the file that was changed.

  3. Software vendors need only provide the related libraries module required.  Additional runtime linking functions allow such programs to programmatically-link the required modules only.

  4. In combination with virtual memory, dynamic linking permits two or more processes to share read-only executable modules such as standard C libraries.  Using this technique, only one copy of a module needs be resident in memory at any time, and multiple processes, each can executes this shared code (read only).  This results in a considerable memory saving, although demands an efficient swapping policy.

W.6  HOW SHARED OBJECTS ARE USED

W.6.1  SOME ELF FORMAT DETAILS

W.6.2  ELF SECTIONS

  1. .init           - Startup

  2. .text          - String

  3. .fini           - Shutdown

  4. .rodata     - Read Only

  5. .data         - Initialized Data

  6. .tdata        - Initialized Thread Data

  7. .tbss          - Uninitialized Thread Data

  8. .ctors         - Constructors

  9. .dtors         - Destructors

  10. .got            - Global Offset Table

  11. .bss           - Uninitialized Data

 

Linking and execution view

Figure w.4:  Simplified object file format: linking view and execution view.

W.7  PROCESS LOADING

  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().

 

Process memory layout

Figure w.4:  Process memory layout

 

W.8  RUNTIME DATA STRUCTURE – From Sections to Segments

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

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

 

Table w.6

 

W.9  THE PROCESS (IMAGE)

Another big picture of the C process memory layout

Figure w.5:  C’s process memory layout on an x86.

 

 

W.10  RUNTIME LINKER AND SHARED LIBRARY LOADING

  1. Load-time dynamic linking – the application program is read from the disk (disk file) into memory and unresolved references are located.  The load time loader finds all necessary external symbols and alters all references to each symbol (all previously zeroed) to memory references relative to the beginning of the program.

  2. Run-time dynamic linking – the application program is read from disk (disk file) into memory and unresolved references are left as invalid (typically zero).  The first access of an invalid, unresolved, reference results in a software trap.  The run-time dynamic linker determines why this trap occurred and seeks the necessary external symbol.  Only this symbol is loaded into memory and linked into the calling program.

W.11  SYMBOL NAME RESOLUTION

W.12  DYNAMIC ADDRESS TRANSLATION

  1. Each process can use addresses starting at 0, even if other processes are running, or even if the same program is running more than one time.

  2. Address spaces are protected.

  3. Can fool process further into thinking it has memory that's much larger than available physical memory (virtual memory).

Physical and virtual address: Address translation

 

Figure w.6: Physical and virtual address: Address translation

 

 

 

 

 

 

 

 

 

 

 

 

 

Further related reading:

 

  1. Check the best selling C / C++, Linux and Open Source books at Amazon.com.

  2. To view Windows the executable file content, you can use dumpbin tool that comes with Microsoft Visual Studio or more powerful one is a free PEBrowse utility.

  3. For Linux/Unix/Fedora you can use readelf or other tools that can be found Linux gnu gcc, g++, gdb and gas 1 or Linux gnu gcc, g++, gdb and gas 2.

  4. Windows implementation of processes, threads and synchronization using C can be found Win32 processes and threads tutorials.

  5. Windows Dynamic-Link Library, DLL story and program examples can be found Win32 DLL tutorials.

  6. Windows Services story can be found Windows Services tutorials.

 

 

 

 

 

 

 

|< The main() and command line arguments | Main | C Memory Allocation and De-allocation Functions >| Site Index | Download |