Follow our illustrated blog on Embedded Software Architecture

How to build a hybrid solar/wind energy harvester?

The linker demystified, part 1

The linker demystified, part 1, 9.7 out of 10 based on 3 ratings
VN:F [1.9.22_1171]
Rating: 9.7/10 (3 votes cast)

Transforming source code into an executable program involves a number of steps called a software build process. In its simplest form, these steps are limited to a compiler translating source code written in a high-level programming language (such as C) into low-level object code, and a linker combining the object code into a single executable file. In this article, we will focus on the last step, discussing how the linker puts the different pieces of code together into a chunk of binary data which can be executed by a microprocessor/micro-controller. Part two will focus on the difference between static and dynamic linking, and how to customize the linking stage using linker scripts.

Compiler output

The linker starts where the compiler ends. Therefore we should start by looking at what the compiler actually produces: a bunch of object code. For the sake of convenience, we’ll assume that all code is written in C.

Consider the following blocks of code:

/*************
 * file1.c
 *************/
int a;
extern int b;
int fn1(void);
void fn2() {
    b = fn1();
}

int main() {
    return 0;
}
/*************
 * file2.c
 *************/
int b = 3;
int fn1() {
    return 1;
}

The first block shows the contents of file1.c, which holds the definition of global variable a, functions fn2 and main, as well as the declaration of variable b, using the keyword extern, and the function prototype of fn1. The second file contains the definitions of said declarations.

Invoking the compiler on above files, results in the object files file1.o and file2.o; one for each source file the compiler got as input. Such an object file contains machine code, which can be directly understood by the processor, and is divided into a number of sections of which the following are the most relevant:

  • .data section: contains all initialized global and static variable definitions
  • .bss section: contains all global and static variables that are either initialized to zero or are not initialized at all
  • .text section: holds all function definitions

Using nm or objdump, we are able to analyze the contents of both object files:

Symbols from file1.o:

Name    Value   Class  Type         Size     Line  Section

a     |00000004|   C  |      OBJECT|00000004|     |*COM*
b     |        |   U  |      NOTYPE|        |     |*UND*
fn1   |        |   U  |      NOTYPE|        |     |*UND*
fn2   |00000000|   T  |        FUNC|00000024|     |.text
main  |00000024|   T  |        FUNC|00000018|     |.text
Symbols from file2.o:

Name    Value   Class  Type         Size     Line  Section

b     |00000000|   D  |      OBJECT|00000004|     |.data
fn1   |00000000|   T  |        FUNC|00000018|     |.text

The above output lists the symbols from the object files. These symbols are characterized among others by their size, the section in the object file in which they reside and the class they belong to.

The first object file contains 4 symbols. The uninitialized global variable a is categorized as a Common (C) symbol, meaning that the linker is able to merge it later and if it finds no implementation, it will be treated as uninitialized data. Therefore, this symbol is not yet assigned to the .bss section as any uninitialized variable normally would be. We will see later on, when we link both object files, that the symbol will be classified as Uninitialized (B). As a side note, this behavior can be altered using the compiler option -fno-common, causing the compiler to sort it as .bss right away.

The symbols b and fn1, both declarations of respectively a variable and a function, are denoted as Undefined (U). As the compiler could not find a value or implementation of these symbols when parsing the source file, they are left empty (for now).

The final symbols fn2 and main are associated with a function definition and are therefore assigned to the .text section in which all executable code is placed.

The second object file holds 2 symbols: the initialized global variable b, denoted with a capital D, is assigned to the .data section; and the function definition fn1, assigned to the .text section, similar to fn2.

Linking

Now that we have examined the contents of the object files, it is time to link both together. Invoke your toolchain’s linker, e.g. ld file1.o file2.o -o result.o, and ignore for now any warnings regarding missing _start symbols. The resulting object file result.o should contain more or less, depending on your toolchain and target platform, the following symbols:

Symbols from result.o:

Name         Value   Class  Type     Size     Line Section

__bss_start|08049138|   A  |  NOTYPE|        |     |*ABS*
_edata     |08049138|   A  |  NOTYPE|        |     |*ABS*
_end       |0804913c|   A  |  NOTYPE|        |     |*ABS*
_start     |        |   U  |  NOTYPE|        |     |*UND*
a          |08049138|   B  |  OBJECT|00000004|     |.bss
b          |08049134|   D  |  OBJECT|00000004|     |.data
fn1        |080480b0|   T  |    FUNC|0000000a|     |.text
fn2        |08048094|   T  |    FUNC|00000012|     |.text
main       |080480a6|   T  |    FUNC|0000000a|     |.text

Before explaining the symbols starting with a ‘_’, let us compare the previously discussed symbols with the contents of the resulting object file. First of all, whereas variable a was categorized as a Common symbol by the compiler, the linker has classified it to the .bss section as it has not found any initialization. The symbols b and fn1 lacked any information in file1.o and therefore were classified as Undefined; the linker found the corresponding information in the second object file, thereby completing this missing information in the resulting result.o. Second, the value of the symbols has changed significantly. On 32-bit platforms this value is an 8-digit hexadecimal number that represents the symbol’s address within the process’ address space. Merging the symbols together, results in a different location of the symbols when compared to the original object files.

As for the remaining symbols, the linker added a number of placeholders that indicate the start and end of the object sections. As you may suspect, _bss_start points to the beginning of the .bss section, _edata is the first address after the .data section and _end holds the first address after the .bss section. Please note that these symbols are marked as Absolute, meaning they don’t belong to any section.

Finally, one symbol remains to be explained: _start. This symbol is classified as undefined, hence the linker warning, and represents the entry point of the object file. This entry point is a set of instructions that among others sets up stack memory and frame pointers, initializes data in RAM, performs any specific platform initialization and finally calls the main() function. Depending on your platform, this symbol is either provided by the toolchain’s Standard C library (on a Linux platform, this would typically be glibc) and more specifically the C Runtime initialization object file (crt0.o) or by a custom linker script (as we will see in part 2 of this article).

Linking continued

So without the _starts symbol our object file is not executable, simply because the execution environment wouldn’t know where to start executing. Therefore we need to link file1.o and file2.o against the Standard C library and crt0.o in order to obtain an executable object file. By default, the GCC compiler performs the linking stage as well, thereby automatically linking against libc. The exact compiler and linking commands can be looked up using the -v option when invoking gcc.

Examining the fully functional executable, would not only show that the _start symbol has obtained a valid address, the number of symbols has also increased significantly. These additional symbols originate from the libc library collection; discussing them in detail however, is beyond the scope of this article.

The loader takes over

To have the operating system actually execute an executable, the file must first be read from disk and its contents loaded into memory. This is where the loader steps in. From the file’s header, the loader determines the size of the text and data segments and sets up a new address space in memory. This memory space is filled with machine instructions and data. Any arguments that were passed, are copied on the stack. Several machine registers are set, including the stack pointer and the program counter which now points at the _start routine. The executable has now become a process of our operating system, all set to go.

Sections vs segments, a case of ‘tomato’ vs ‘tomahto’?

No, it is not. An ELF (Executable and Linkable Format) file, the standard binary file format for executables on Unix and Unix-like systems (including Linux), differentiates between information that is needed for linking and for execution. The former is organised into several sections as we discussed in the first paragraph, the latter is grouped into segments. Elaborating a bit on the previous paragraph, all the sections of the executable that are to be loaded into memory, are entirely encompassed within segments. Such a segment has among others a virtual and a physical address, a file offset, a given file and memory size and a certain alignment. The loader iterates over the various segments, and starts copying the segment’s contents from the file offset to memory at the virtual address (or the physical address when the operating system does not use virtual memory).

A prelude on linker scripts

As mentioned in the preface of this article, linker scripts allow for customisation of the linking process. Such customisation is normally not necessary on systems that dispose of a full-fledged operating system like Linux. On bare-metal embedded systems however, where resources are typically scarce, it is essential to have full control on how these resources are allocated.

Among others a linker script allows you to define the entry point of your executable, thereby modifying the startup flow. Further more it enables a developer to identify different memory regions, flash – RAM – stack – heap, define its size and assign symbols or even entire sections to it. A sensible example would be the assignment of the .text section, as well as all symbols from the .data section that are classified as constant, to the flash memory resulting in more available space in RAM. Another example is to put the interrupt vector table on a predefined memory location where the processor is hard-coded to look for.

Please wait for the second part of this article for a more in-depth discussion on linker scripts and its syntax.

Would you like to know more?

More information on the linking stage and the inner workings of linkers can be found in this freely available book. A reference on the Executable and Linkable Format (ELF) can be found here.

Stay tuned for the second part of this article, covering dynamic linking and linker scripts.

VN:F [1.9.22_1171]
Rating: 9.7/10 (3 votes cast)
Share

Comments

  1. John Smith says

    Still waiting for part two!

Speak Your Mind

*