Let’s start with a review of linker basics: The compiler creates an output file containing relocatable objects. These objects are the data and machine instructions corresponding to the source programs. This chapter uses the sophisticated form of linking found on all SVR4 systems as its example.

Where the Linker Is in the Phases of Compilation

Most compilers are not one giant program. They usually consist of up to half-a-dozen smaller programs, invoked by a control program called a “compiler driver.” Some pieces that can be conveniently split out into individual programs are: the preprocessor, the syntactic and semantic checker, the code generator, the assembler, the optimizer, the linker, and, of course, a driver program to invoke all these pieces and pass the right options to each (see Figure 5-1). An optimizer can be added after almost any of these phases. The current SPARCompilers do most optimizations on the intermediate representation between the front and back ends of the compiler.

Figure 5-1. A Compiler is Often Split into Smaller Programs

They are written in pieces because they are easier to design and maintain if each specialized part is a program in its own right. For instance, the rules controlling preprocessing are unique to that phase and have little in common with the rest of C. The C preprocessor is often (but not always) a separate program. If the code generator (also known as the “back end”) is written as a stand-alone program, it can probably be shared by other languages. The trade-off is that running several smaller programs will take longer than running one big program (because of the overhead of initiating a process and sending information between the phases). You can look at the individual phases of compilation by using the -# option. The -V option will provide version information.

You can pass options to each phase, by giving the compiler-driver a special -W option that says “pass this option to that phase.” The “W” will be followed by a character indicating the phase, a comma, and then the option. The characters that represent each phase are shown in Figure 5-1.

So to pass any option through the compiler driver to the linker, you have to prefix it by “-Wl,” to tell the compiler driver that this option is intended for the link editor, not the preprocessor, compiler, assembler, or another compilation phase. The command

cc -Wl,-m main.c > main.linker.map

An object file isn’t directly executable; it needs to be fed into a linker first. The linker identifies the main routine as the initial entry point (place to start executing), binds symbolic references to memory addresses, unites all the object files, and joins them with the libraries to produce an executable.

There’s a big difference between the linking facilities available on PC’s and those on bigger systems. PC’s typically provide only a small number of elementary I/O services, known as the BIOS routines. These exist in a fixed location in memory, and are not part of each executable. If a PC program or suite of programs requires more sophisticated services, they can be provided in a library, but the implementor must link the library into each executable. There’s no provision in MS-DOS for “factoring out” a library common to several programs and installing it just once on the PC.

UNIX systems used to be the same. When you linked a program, a copy of each library routine that you used went into the executable. In recent years, a more modern and superior paradigm known as dynamic linking has been adopted. Dynamic linking allows a system to provide a big collection of libraries with many useful services, but the program will look for these at runtime rather than having the library binaries bound in as part of the executable. IBM’s OS/2 operating system has dynamic linking, as does Microsoft’s new flagship NT operating system. In recent years, Microsoft Windows^® has introduced this ability for the windowing part of PC applications.

If a copy of the libraries is physically part of the executable, then we say the executable has been statically linked; if the executable merely contains filenames that enable the loader to find the program’s library references at runtime, then we say it has been dynamically linked. The canonical names for the three phases of collecting modules together and preparing them for execution are link-editing, loading, and runtime linking. Statically linked modules are link edited and then loaded to run them. Dynamically linked modules are link-edited and then loaded and runtime-linked to run them. At execution, before main() is called, the runtime loader brings the shared data objects into the process address space. It doesn’t resolve external function calls until the call is actually made, so there’s no penalty to linking against a library that you may not call. The two linking methods are compared in Figure 5-2.

Figure 5-2. Static Linking versus Dynamic Linking

Even with static linking, the whole of libc. a is not brought into the executable, just the routines needed.

Dynamic linking is the more modern approach, and has the advantage of much smaller executable size. Dynamic linking trades off more efficient use of the disk and a quicker link-edit phase for a small runtime penalty (since some of the linker’s work is deferred until loadtime).

Handy Heuristic

One Purpose of Dynamic Linking Is the ABI

A major purpose of dynamic linking is to decouple programs from the particular library versions they use. Instead, we have the convention that the system provides an interface to programs, and that this interface is stable over time and successive OS releases.

Programs can call services promised by the interface, and not worry about how they are provided or how the underlying implementation may change. Because this is an interface between application programs and the services provided by library binary executables, we call it an Application Binary Interface or ABI.

A single ABI is the purpose of unifying the UNIX world around AT&T’s SVr4. The ABI guarantees that the libraries exist on all compliant machines, and ensures the integrity of the interface. There are four specific libraries for which dynamic linking is mandatory: libc (C runtimes), libsys (other system runtimes), libX (X windowing), and libnsl (networking services). Other libraries can be statically linked, but dynamic linking is strongly preferred.

In the past, application vendors had to relink their software with each new release of the OS or a library. It caused a huge amount of extra work for all concerned. The ABI does away with this, and guarantees that well-behaved applications will not be affected by well-behaved upgrades in underlying system software.

Although an individual executable has a slightly greater start-up cost, dynamic linking helps overall performance in two ways:

For example, if you have eight XView™ applications running, only one copy of the XView library text segment has to be mapped into memory. The first process’s mmap ^[1] call will result in the kernel mapping the shared object into memory. The next seven process mmaps will cause the kernel to share the existing mapping in each process. Each of the eight processes will share one copy of the XView library in memory. If the library were statically linked, there would be eight individual copies consuming more physical memory and causing more paging.

Dynamic linking permits easy versioning of libraries. New libraries can be shipped; once installed on the system, old programs automatically get the benefit of the new versions without needing to be relinked.

Finally (much less common, but still possible), dynamic linking allows users to select at runtime which library to execute against. It’s possible to create library versions that are tuned for speed, or for memory efficiency, or that contain extra debugging information, and to allow the user to express a preference when execution takes place by substituting one library file for another.

Dynamic linking is “just-in-time” linking. It does mean that programs need to be able to find their libraries at runtime. The linker accomplishes this by putting library filenames or pathnames into the executable; and this in turn, means that libraries cannot be moved completely arbitrarily. If you linked your program against library /usr/lib/libthread.so, you cannot move the library to a different directory unless you specified it to the linker. Otherwise, the program will fail at runtime when it calls a function in the library, with an error message like:

ld.so.1: main: fatal: libthread.so: can’t open file: errno=2

This is also an issue when you are executing on a different machine than the one on which you compiled. The execution machine must have all the libraries that you linked with, and must have them in the directories where you told the linker they would be. For the standard system libraries, this isn’t a problem.

The main reason for using shared libraries is to get the benefit of the ABI—freeing your software from the need to recompile with each new release of a library or OS. As a side benefit, there are also overall system performance advantages.

Anyone can create a static or dynamic library. You simply compile some code without a main routine, and process the resulting .o files with the correct utility—“ar” for static libraries, or “ld” for dynamic libraries.

Software Dogma

Only Use Dynamic Linking!

Dynamic linking is now the default on computers running System V release 4 UNIX, and it should always be used. Static linking is now functionally obsolete, and should be allowed to rest in peace.

The major risk you run with static linking is that future versions of the operating system will be incompatible with the system libraries bound in with your executable. If your application was statically linked on OS version N and you try to run it on version N+1, it may run, or it may fail with a core dump or a less obvious error.

There is no guarantee that an earlier version of the system libraries will execute correctly on a later version of the system. Indeed, it is usually safer to assume the opposite. However, if an application is dynamically linked on version N of the system, it will correctly pick up the version N+1 libraries when run on version N+1 of the system. In contrast, statically linked applications have to be regenerated for every new release of the operating system to ensure that they keep running.

Furthermore, some libraries (such as libaio.so, libdl.so, libsys.so, libresolv.so, and librpcsvc.so) are only available in dynamic form. You are obliged to link dynamically if your application uses any of these libraries. The best policy is to avoid problems by making sure that all applications are dynamically linked.

Static libraries are known as archives and they are created and updated by the ar—for archive—utility. The ar utility is misnamed; if truth in advertising applied to software, it would really be called something like glue_files_together or even static_library_updater. Convention dictates that static libraries have a “.a” extension on their filename. There isn’t an example of creating a static library here, because they are obsolete now, and we don’t want to encourage anyone to communicate with the spirit world.

There was an interim kind of linking used in SVR3, midway between static linking and dynamic linking, known as “static shared libraries”. Their addresses were fixed throughout their life, and thus could be bound to without the indirection required with dynamic linking. On the other hand, they were inflexible and required a lot of special support in the system. We won’t consider them further.

A dynamically linked library is created by the link editor, ld. The conventional file extension for a dynamic library is “.so” meaning “shared object”—every program linked against this library shares the same one copy, in contrast to static linking, in which everyone is (wastefully) given their own copy of the contents of the library. In its simplest form, a dynamic library can be created by using the -G option to cc, like this:

% cat tomato.c 
    my_lib_function() {printf(“library routine called
”); } 

% cc -o libfruit.so -G tomato.c

You can then write routines that use this library, and link with it in this manner:

% cat test.c 
    main() { my_lib_function(); } 

% cc test.c -L/home/linden -R/home/linden -lfruit 
% a.out 
library routine called

The -L/home/linden -R/home/linden options tell the linker in which directories to look for libraries at linktime and at runtime, respectively.

You will probably also want to use the -K pic compiler option to produce position-independent code for your libraries. Position-independent code means that the generated code makes sure that every global data access is done through an extra indirection. This makes it easy to relocate the data simply by changing one value in the table of global offsets. Similarly, every function call is generated as a call through an indirect address in a procedure linkage table. The text can thus easily be relocated to anywhere, simply by fixing up the offset tables. So when the code is mapped in at runtime, the runtime linker can directly put it wherever there is room, and the code itself doesn’t have to be changed.

By default, the compilers don’t generate PICode as the additional pointer dereference is a fraction slower at runtime. However, if you don’t use PICode, the generated code is tied to a fixed address—fine for an executable, but slower for a shared library, since every global reference now has to be fixed up at runtime by page modification, in turn making the page unshareable.

The runtime linker will fix up the page references anyway, but the task is greatly simplified with position-independent code. It is a trade-off whether PICode is slower or faster than letting the runtime linker fix up the code. A rule of thumb is to always use PICode for libraries. Position-independent code is especially useful for shared libraries because each process that uses a shared library will generally map it at a different virtual address (though sharing one physical copy).

A related term is “pure code.” A pure executable is one that contains only code (no static or initialized data). It is “pure” in the sense that it doesn’t have to be modified to be executed by any specific process. It references its data off the stack or from another (impure) segment. A pure code segment can be shared. If you are generating PIcode (indicating sharing) you usually want it to be pure, too.

There are five essential, non-obvious conventions to master when using libraries. These aren’t explained very clearly in most C books or manuals, probably because the language documenters consider linking part of the surrounding operating system, while the operating system people view linking as part of the language. As a result, no one makes much more than a passing reference to it unless someone from the linker team gets involved! Here are the essential UNIX linking facts of life:

In order for the symbols to get extracted from the math library, you need to put the file containing the unresolved references first, like so:

cc main.c -lm

This causes no end of angst for the unwary. Everyone is used to the general command form of <command> <options> <files>, so to have the linker adopt the different convention of <command> <files> <options> is very confusing. It’s exacerbated by the fact that it will silently accept the first version and do the wrong thing. At one point, Sun’s compiler group amended the compiler drivers so that they coped with the situation. We changed the SunOS 4.x unbundled compiler drivers from SC0.0 through SC2.0.1 so they would “do the right thing” if a user omitted -lm. Although it was the right thing, it was different from what AT&T did, and broke our compliance with the System V Interface Definition; so the former behavior had to be reinstated. In any case, from SunOS 5.2 onwards a dynamically linked version of the math library /usr/lib/libm.so is provided.

Handy Heuristic

Where to Put Library Options

Always put the -l library options at the rightmost end of your compilation command line.

Similar problems have been seen on PC’s, where Borland compiler drivers tried to guess whether the floating-point libraries needed to be linked in. Unfortunately, they sometimes guessed wrongly, leading to the error:

scanf : floating point formats not linked 
Abnormal program termination

They seem to guess wrongly when the program uses floating-point formats in scanf() or printf() but doesn’t call any other floating-point routines. The workaround is to give the linker more of a clue, by declaring a function like this in a module that will be included in the link:

static void forcefloat(float *p) 
{ float f = *p; forcefloat(&f); }

Don’t actually call the function, merely ensure that it is linked in. This provides a solid enough clue to the Borland PC linker that the floating-point library really is needed.

NB: a similar message, saying “floating point not loaded” is printed by the Microsoft C runtime system when the software needs a numeric coprocessor but your computer doesn’t have one installed. You fix it by relinking the program, using the floating-point emulation library.

Interpositioning (some people call it “interposing”) is the practice of supplanting a library function by a user-written function of the same name. This is a technique only for people who enjoy a good walk on the wild side of the fast lane without a safety net. It enables a library function to be replaced in a particular program, usually for debugging or performance reasons. But like a gun with no safety catch, while it lets experts get faster results, it also makes it very easy for novices to hurt themselves.

Interpositioning requires great care. It’s all too easy to do this accidentally and replace a symbol in a library by a different definition in your own code. Not only are all the calls that you make to the library routine replaced by calls to your version, but all calls from system routines now reference your routine instead. A compiler will typically not issue an error message when it notices a redefinition of a library routine. In keeping with C’s philosophy that the programmer is always right, it assumes the programmer meant to do it.

Over the years we have seen no convincing examples where interpositioning was essential but the effect could not be obtained in a different (perhaps less convenient) manner. We have seen many instances where a default global scope symbol combined with interpositioning to create a hard-to-find bug (see Figure 5-3). We have seen a dozen or so bug reports and emergency problem escalations from even the most knowledgeable software developers. Unhappily, it’s not a bug; the implementation is supposed to work this way.

Figure 5-3. Diagram of Interpositioning and Default Global Scope

Most programmers have not memorized all the names in the C library, and common names like index or mktemp tend to be chosen surprisingly often. Sometimes bugs of this kind even get into production code.

Software Dogma

An Interpositioning Bug in SunOS

Under SunOS 4.0.3, the printing program /usr/ucb/lpr occasionally issued the error message “out of memory” and refused to print. The fault appeared randomly, and it was very hard to track down. Finally, it was traced to an unintended interpositioning bug.

The programmer had implemented lpr with a routine, global by default, called mktemp(), which expected three arguments. Unknown to the programmer, that duplicated a name already present in the (pre-ANSI) C library, which did a similar job but only took one argument.

Unfortunately, lpr also invoked the library routine getwd(), which expects to use the library version of mktemp. Instead, it was bound to lpr ’s special version! Thus, when getwd() called mktemp, it put one argument on the stack, but the lpr version of mktemp retrieved three. Depending on the random values it found, lpr failed with the “out of memory” error.

Moral: Don’t make any symbols in your program global, unless they are meant to be part of your interface!

lpr was fixed by declaring its mktemp as static, making it invisible outside its own file (we could equally have given it a different name). Mktemp has now been replaced by the library routine tmpnam in ANSI C. However, the opportunity for the interpositioning problem still exists.

If an identifier is shown in Table 5-2, never declare it in your own program. Some of these are always reserved, and others are only reserved if you include a specific header file. Some of these are reserved only in global scope, and others are reserved for both global and file scope. Also note that all keywords are reserved, but are left out of the table below for simplicity. The easiest way to stay out of trouble is to regard all these identifiers as belonging to the system at all times. Don’t use them for your identifiers.

Some entries look like is[a-z]anything.

This means any identifier that begins with the string “is” followed by any other lowercase letter (but not, for example, a digit) followed by any characters.

Other entries look like acos,-f,-l.

This indicates that the three identifiers acos, acosf, and acosl are reserved. All routines in the math header file have a basic version that takes a double-precision argument. There can also be two extra versions: the basename with a l suffix is a version of the routine with quad precision arguments (type “long double”), and the f suffix is a version with single precision (“float”).

Remember that under ANSI section 6.1.2 (Identifiers), an implementation can define letter case not significant for external identifiers. Also, external identifiers only need be significant in the first six characters (ANSI section 5.2.4.1, Translation Limits). Both of these expand the number of identifiers that you should avoid. The list above consists of the C library symbols that you may not redefine. There will be additional symbols for each additional library you link against. Check the ABI document ^[2] for a list of these.

The problem of name space pollution is only partially addressed in ANSI C. ANSI C out-laws a user redefining a system name (effectively outlawing interpositioning) in section 7.1.2.1:

If an identifier is reserved, it means that the user is not allowed to redefine it. However, this is not a constraint, so it does not require an error message when it sees it happen. It just causes unportable, undefined behavior. In other words, if one of your function names is the same as a C library function name (deliberately or inadvertently), you have created a nonconforming program, but the translator is not obliged to warn you about it. We would much rather the standard required the compiler to issue a warning diagnostic, and let it make up its own mind about stuff like the maximum number of case labels it can handle in a switch statement.

Use the “-m” option to ld for a linker report that includes a note of symbols which have been interposed. In general, the “-m” option to ld will produce a memory map or listing showing what has been put where in the executable. It also shows multiple instances of the same symbol, and by looking at what files these occur in, the user can determine if any interpositioning took place.

The -D option to ld was introduced with SunOS 5.3 to provide better link-editor debugging. The option (fully documented in the Linker and Libraries Manual) allows the user to display the link-editing process and input file inclusion. It’s especially useful for mon-itoring the extraction of objects from archives. It can also be used to display runtime bindings.

Ld is a complicated program with many more options and conventions than those explained here. Our description is more than enough for most purposes, and there are four further sources of help, in increasing order of sophistication:

Some combination of these should provide information on any subtle linker special effects you need.

Handy Heuristic

When “botch” Appears

Under SunOS 4.x, an occurrence of the word “botch” in an error message means that the loader has discovered an internal inconsistency. This is usually due to faulty input files.

Under SunOS 5.x, the loader is much more rigorous about checking its input for correctness and consistency. It doesn’t need to complain about internal errors, and the “botch” messages have been dropped.

At the dawn of the electronic age, as the potential of computers first started to unfold, a debate arose over whether systems would one day have artificial intelligence. That quickly led to the question, “How can we tell if a machine thinks?” In a 1950 paper in the journal Mind, British mathematician Alan Turing cut through the philosophical tangle by suggesting a practical test. Turing proposed that a human interrogator converse (via teletype, to avoid sight and sound clues) with another person and with a computer. If the human interrogator was unable to correctly identify which was which after a period of five minutes, then the computer would be said to have exhibited artificial intelligence. This scenario has come to be called the Turing Test.

Over the decades since Turing proposed this trial, the Turing test has taken place several times, sometimes with astonishing results. We describe some of those tests and reproduce the dialogue that took place so you can judge for yourself.