第4章アルゴリズムの言語による実現：低水準プログラミング言語

A linker classifies symbols in three categories as illustrated in Figure 4.23 and Figure 4.24. A symbol can be the name of a variable or a string. In other cases, it can be the function names or procedure, such as

• Global symbols: Symbols defined by module m that can be referenced by other modules (e.g., non-static C functions and non-static global variables)

• External symbols: Global symbols that are referenced by module m but defined by some other module.

• Local symbols: Symbols that are defined and referenced exclusively by module m (e.g., C functions and global variables defined with the static attribute); local linker symbols are not local program variables (linker does not deal with the local variables of a function). Also note that local non-static C variables are stored on the stack while local static C variables are stored in either .bss, or .data.

Program symbols are either strong (e.g., procedures and initialized globals) or weak (e.g., uninitialized globals). A strong symbol has a unique memory location. Let’s take the example of: int array[2] = {1 ,2};. This creates an ambiguity during the linking process when there is another file that tries to access the same symbol again due to strong definition. On the other hand, a weak symbol allows multiple definitions of the same symbol without creating an ambiguity. This helps during the linking process when another file creates a strong definition of the same name. In languages like C and C++, the weak symbol is defined using the _attribute_((weak)) keyword. Global variables should be avoided (i.e., use static whenever you can, initialize the global variable, or use extern if you reference an external global variable).

The linker applies the following rules:

• Rule 1: Multiple strong symbols are not allowed. Each item can be defined only once, otherwise the linker issues an error.

• Rule 2: Given a strong symbol and multiple weak symbols, choose the strong symbol (references to the weak symbol resolve to the strong symbol).

• Rule 3: If there are multiple weak symbols, pick an arbitrary one (can override this with gcc –fno-common). “-fno-common” helps in catching accidental common name collisions.

Functions commonly used by programmers (e.g., math, I/O, memory management, string manipulation) can be packaged into a file called a library. A static library (or .a, an archive file) is a simple kind of library that that copies the contents of object files into a single file called an archive. The linker tries to resolve unresolved external references by looking for the symbols in one or more archives. An external reference is a symbol that is used in a module, but not defined in that module, so it is expected to be defined in some other module. If an archive member file resolves a reference, the linker links it into the executable. The archiver allows incremental updates; it also recompiles functions that changed and replaces the corresponding .o file in the archive (Figure 4.25).

Commonly used libraries include libc.a (the C standard library), which handles: I/O, memory allocation, signal handling, string handling, data and time, random numbers, and integer math. Another common library is libm.a (the C math library) that handles floating point math (e.g., sin, cos, tan, log, exp, sqrt).

Figure 4.26 illustrates how to link programs with static libraries.

The linker uses the following algorithm to resolve external references:

1. Scan .o files and .a files in the command line order.

2. During the scan, keep a list of the current unresolved references.

3. As each new .o or .a file, obj, is encountered, try to resolve each unresolved reference in the list against the symbols defined in obj.

4. If any entries in the unresolved list at end of scan, then issue error.

Therefore, the command line order matters and libraries should be placed at the end of the command line to avoid linker errors as illustrated in Figure 4.27.