A New Linker

This means that if an object pulled in from a library late in the link line needs a symbol from a library earlier in the link line, the linker won't automatically find it. An example should help to make this clearer; let's suppose we have the following object files, and a link line that pulls in a.o, b.o, -lx and -ly. Open a link in a new window or tab. In order to open a link in a new window / tab, add target='blank' inside the tag: Open page in new window The code will create this link: Open page in new window. New window or new tab. You can't set whether the link will be opened in a new window or new tab. It depends on the browser's settings. Open a link in a new window with specified size. How to Open Hyperlinks in a New Browser Tab or Window. The short answer is: just add a target='blank' attribute to your links (anchor tags). For example, if you have a link that says the following: a href='https://www.thesitewizard.com/'thesitewizard.coma.

GNU Binutils

The GNU Binutils are a collection of binary tools. The main ones are:

  • ld - the GNU linker.
  • as - the GNU assembler.

But they also include:

  • addr2line - Converts addresses into filenames and line numbers.
  • ar - A utility for creating, modifying and extracting from archives.
  • c++filt - Filter to demangle encoded C++ symbols.
  • dlltool - Creates files for building and using DLLs.
  • gold - A new, faster, ELF only linker, still in beta test.
  • gprof - Displays profiling information.
  • nlmconv - Converts object code into an NLM.
  • nm - Lists symbols from object files.
  • objcopy - Copies and translates object files.
  • objdump - Displays information from object files.
  • ranlib - Generates an index to the contents of an archive.
  • readelf - Displays information from any ELF format object file.
  • size - Lists the section sizes of an object or archive file.
  • strings - Lists printable strings from files.
  • strip - Discards symbols.
  • windmc - A Windows compatible message compiler.
  • windres - A compiler for Windows resource files.

Most of these programs use BFD, the Binary File Descriptor library, to do low-level manipulation. Many of them also use the opcodes library to assemble and disassemble machine instructions.

The binutils have been ported to most major Unix variants as well as Wintel systems, and their main reason for existence is to give the GNU system (and GNU/Linux) the facility to compile and link programs.

Obtaining binutils

The latest release of GNU binutils is 2.36. The various NEWS files (binutils, gas, and ld) have details of what has changed in this release.

See the SOFTWARE page for information on obtaining releases of GNU binutils and other GNU software. The current release can be downloaded from https://ftp.gnu.org/gnu/binutils or, preferably, from a nearby mirror through the generic URL https://ftpmirror.gnu.org/binutils.

If you plan to do active work on GNU binutils, you can access the development source tree by anonymous git:

git clone git://sourceware.org/git/binutils-gdb.git

Alternatively, you can use the gitweb interface, or the source snapshots, available as bzipped tar files via anonymous FTP from ftp://sourceware.org/pub/binutils/snapshots.

Bug reports

There is a bug-tracking system at https://sourceware.org/bugzilla/.

A new link

Mailing lists

There are three binutils mailing lists:

<[email protected]> (archives)
For reporting bugs.
<[email protected]> (archives)
For discussing binutils issues.
binutils-cvs (archives)
A read-only mailing list containing the notes from checkins to the binutils git repository. (This list has an odd name for historical reasons.)

You can use this form to subscribe to the [email protected] or [email protected] mailing lists:

To subscribe to the [email protected] mailing list, see the bug-binutils info page.

You may wish to browse the old mail archives of the gas2 and bfd mailing lists. These were the discussion lists for binutils until May 1999. Please do not send mail to them any longer.

Documentation

The documentation for binutils 2.36 is available.

A guide to porting the binutils to a new target has been contributed.

This article is intended to help C & C++ programmers understand theessentials of what the linker does. I've explained this to a numberof colleagues over the years, so I decided it was time to write itdown so that it's more widely available (and so that I don't have toexplain it again). [Updated March 2009 to includemore information on the pecularities of linking on Windows, plussome clarification on the one definition rule.]

A typical example of what triggers this explanation is when I helpsomeone who has a link error like:

If your reaction to this is 'almost certainlymissing Newextern 'C'' then you probably already know everything inthis article.

Table of Contents

Naming of Parts: What's in a C File

This section is a quick reminder of the different parts of a Cfile. If everything in the sample C file listingbelow makes sense to you, you can probably skip to thenext section.

The first division to understand is between declarations anddefinitions. A definition associates aname with an implementation of that name, which could be either data or code:

  • A definition of a variable induces the compiler to reserve some space for that variable, and possibly fill that space with a particular value.
  • A definition of a function induces the compiler to generate code for that function.
A declaration tells the C compiler that adefinition of something (with a particular name) exists elsewherein the program, probably in a different C file. (Note that adefinition also counts as a declaration—it's a declaration thatalso happens to fill in the particular 'elsewhere').

For variables, the definitions split into two sorts:

  • global variables, which exist for the whole lifetime of the program ('static extent'), and which are usually accessible in lots of different functions
  • local variables, which only exist while a particular function is being executed ('local extent') and are only accessible within that function
To be clear, by 'accessible' we mean 'can be referred to using thename associated with the variable by its definition'.

There are a couple of special cases where things aren't so immediatelyobvious:

  • static local variables are actually global variables, because they exist for the lifetime of the program, even though they're only visible inside a single function
  • likewise static global variables also count as global variables, even though they can only be accessed by the functions in the particular file where they were defined
While we're on the subject of the 'static' keyword, it'salso worth pointing out that making a function static justnarrows down the number of places that are able to refer to thatfunction by name (specifically, to other functions in the same file).

For both global and local variable definitions, we can also make a distinctionbetween whether the variable is initialized or not—that is,whether the space associated with the particular name is pre-filledwith a particular value.

Finally, we can store information in memory that is dynamicallyallocated using malloc or new. There is noway to refer to thespace allocated by name, so we have to use pointers instead—anamed variable (the pointer) holds the address of the unnamed piece ofmemory. This piece of memory can also be deallocated withfree or delete, so the space is referred to as having 'dynamicextent'.

Let's put all that together:
CodeData
GlobalLocalDynamic
InitializedUninitializedInitializedUninitialized
Declarationint fn(int x);extern int x;extern int x;N/AN/AN/A
Definitionint fn(int x) { ... }int x = 1;
(at file scope)
int x;
(at file scope)
int x = 1;
(at function scope)
int x;
(at function scope)
(int* p = malloc(sizeof(int));)

What The C Compiler Does

The C compiler's job is to convert a C file from text that the human can(usually) understand, into stuff that the computer canunderstand. This output by the compiler as anobject file. On UNIX platforms these object files normallyhave a .o suffix; on Windows they have a.obj suffix. The contents of an object file areessentially two kinds of things:

  • code, corresponding to definitions of functions in the C file
  • data, corresponding to definitions of global variables in the C file (for an initialized global variable, the initial value of the variable also has to be stored in the object file).
Instances of either of these kinds of things will have namesassociated with them—the names of the variables orfunctions whose definitions generated them.

Object code is the sequence of (suitably encoded) machineinstructions that correspond to the C instructions that the programmerhas written—all of those ifs and whilesand even gotos. All of these instructions need tomanipulate information of some sort, and that information needs to bekept somewhere—that's the job of the variables. The code canalso refer to other bits of code—specifically, to other Cfunctions in the program.

Wherever the code refers to a variable or function, the compiler onlyallows this if it has previously seen a declaration for that variable orfunction—the declaration is a promise that a definition existssomewhere else in the whole program.

The job of the linker is to make good on these promises, but in themeanwhile what does the compiler do with all of these promises when itis generating an object file?

Basically, the compiler leaves a blank. The blank (a 'reference') hasa name associated to it, but the value corresponding to that name isnot yet known.

With that in mind, we can depict the object file corresponding to the program given above like this:

Dissecting An Object File

We've kept everything at a high level so far; it's useful to see howthis actually works in practice. The key tool for this is the commandnm, which gives information about the symbols in an objectfile on UNIX platforms. On Windows, thedumpbincommand with the /symbols option is roughly equivalent;there is alsoaWindows port of theGNU binutilstools which includes an nm.exe.

Let's have a look at what nm gives on the object fileproduced from the C file above:

The output on different platforms can vary a bit (check theman pages to find out more on a particular version), butthe key information given is the class of each symbol, and its size(when available). The class can have a number of different values:

  • A class of U indicates an undefined reference, one of the 'blanks' mentioned previously. For this object, there are two: 'fn_a' and 'z_global'. (Some versions of nm may also print out a section, which will be *UND* or UNDEF in this case)
  • A class of t or T indicates where code is defined; the different classes indicate whether the function is local to this file (t) or not (T)—i.e. whether the function was originally declared with static. Again, some systems may also show a section, something like .text
  • A class of d or D indicates an initialized global variable, and again the particular class indicates whether the variable is local (d) or not (D). If there's a section, it will be something like .data
  • For an uninitialized global variable, we get b if it's static/local, and B or C when it's not. The section in this case will probably be something like .bss or *COM*.

We may also get some symbols that weren't part of the original inputC file; we'll ignore these as they're typically part of thecompiler's nefarious internal mechanisms for getting your program tolink.

What The Linker Does: Part 1

We mentioned earlier that a declaration of a function or a variable isa promise to the C compiler that somewhere else in the program is adefinition for that function or variable, and that the linker's jobs isto make good on that promise. With the diagram of anobject file in front of us, we can also describe this as 'fillingin the blanks'.

To illustrate this, let's have a companion C file to the one given previously:

With these two diagrams, we can see that all of the dots can joinedup (if they couldn't be, then the linker would emit an errormessage). Every thing has its place, and every place has its thing, and thelinker can fill in all of the blanks as shown (on a UNIX system, thelinker is typically invoked with ld).

As for object files, we can use nm toexamine the resulting executable file:

This has all of the symbols from the two objects, and all of theundefined references have vanished. The symbols have also all beenreordered so that similar types of things are together, and there area few added extras to help the operating system deal with the wholething as an executable program.

There's also a fair number of complicatingdetails cluttering up the output, but if you filter out anything startingwith an underscore it gets a lot simpler.

Duplicate Symbols

The previous section mentioned that if the linker cannot find adefinition for a symbol to join to references to that symbol, thenit will give an error message. So what happens if there aretwo definitions for a symbol when it comes to link time?

In C++, the situation is straightforward. The language has a constraint known as the onedefinition rule, which says that there has to be exactly onedefinition for a symbol when it comes to link time, no more and noless. (The relevant section of the C++ standard is 3.2, whichalso mentions some exceptions that we'llcome to later on.)

For C, things are slightly less clear. There has to be exactlyone definition of any functions or initialized global variables,but the definition of an uninitialized global variablecan be treated as a tentative definition. C then allows(or at least does not forbid) different source files to havetentative definitions for the same object.

However, linkers also have to cope with other programming languages thanjust C and C++, and the one definition rule isn't always appropriate for them.For example, the normal model for Fortran code is effectively to havea copy of each global variable in every file that references it;the linker is required to fold duplicates by picking one of the copies(the largest version, if they are different sizes) and throw away therest. (This model is sometimes known as the 'common model'of linking, after the Fortran COMMON keyword.)

As a result, it's actually quite common for UNIX linkers not tocomplain about duplicate definitions of symbols—at least, notwhen the duplicate symbol is an uninitialized global variable(this is sometimes known as the 'relaxed ref/def model' of linking).If this worries you (and it probably should), check the documentation foryour compiler linker—there may well be a --work-properlyoption that tightens up the behavior. For example, for the GNUtoolchain the -fno-common option to the compiler forcesit to put uninitialized variables into the BSS segment rather thangenerating these common blocks.

What The Operating System Does

Now that the linker has produced an executable program with all of thereferences to symbols joined up to suitable definitions of thosesymbols, we need to pause briefly to understand what the operatingsystem does when you run the program.

Running the program obviously involves executing the machine code, so theoperating system clearly has to transfer the machine code from the executablefile on the hard disk into the computer's memory, where the CPU canget at it. This chunk of the program's memory is known as the codesegment or text segment.

Code is nothing without data, so all of the globalvariables need to have some space in the computer's memory too.However, there's a difference between initialized and uninitializedglobal variables. Initialized variables have particularvalues that need to be used to begin with, and these values are stored in the objectfiles and in the executable file. When the program is started, the OScopies these values into the program's memory in the data segment.

For uninitialized variables, the OS can assume that they all juststart with the initial value 0, so there's no need to copy anyvalues. This chunk of memory, that gets initialized to 0, is known asthe bss segment.

This means that space can be saved in the executable file on disk; theinitial values of initialized variables have to be stored in the file,but for the uninitialized variables we just need a count of how muchspace is needed for them.

You may have noticed that all of the discussion of object files andlinkers so far has only talked about global variables; there's been nomention of the local variables and dynamically allocated memorymentioned earlier.

These pieces of data don't need any linker involvement, because theirlifetime only occurs when the program is running—long after thelinker has finished its business. However, for the sake ofcompleteness, we can quickly point out here that:

  • local variables are allocated on a piece of memory known as the stack, which grows and shrinks as different functions are called and complete
  • dynamically allocated memory is taken from an area known as the heap, and the malloc function keeps track of where all the available space in this area is.

We can add in these chunks of memory to complete our picture of whatthe memory space of a running process looks like. Because both theheap and the stack can change size as the program runs, it's quitecommon to arrange matters so that the stack grows in one directionwhile the heap grows in the other. That way, the program will onlyrun out of memory when they meet in the middle (and at that point, thememory space really will be full).

What The Linker Does: Part 2

Now that we've covered the very basics of theoperation of a linker, we can plough on to describe some morecomplicating details—roughly in the order that these featureswere historically added to linkers.

The main observation that affected the function of the linker is this:if lots of different programs need to do the samesorts of things (write output to the screen, read files from the harddisk, etc), then it clearly makes sense to commonize this code in oneplace and have lots of different programs use it.

This is perfectly feasible to do by just using the same object fileswhen linking different programs, but it makes life much easier ifwhole collections of related object files are kept together in oneeasily accessible place: a library

Static Libraries

The most basic incarnation of a library is a static library.The previous section mentioned that you could share code by justreusing object files; it turns out that static libraries really aren'tmuch more sophisticated than that.

On UNIX systems, the command to produce a static library is normallyar, and the library file that it producestypically has a .a extension. These library files arenormally also prefixed with 'lib' and passed to thelinker with a '-l' option followed by the name of the library, withoutprefix or extension (so '-lfred' will pickup 'libfred.a').

(Historically, a program called ranlib also used to be needed for static libraries, in order to build an index of symbols at the start of the library. Nowadays the ar tool tends to do this itself.)

On Windows, static libraries have a .LIB extensionand are produced by the LIB tool,but this can be confusing as the same extension is also usedfor an 'import library', which just holds a list of thethings available in a DLL—see thesection on Windows DLLs.

As the linker trundles through its collection of object files to bejoined together, it builds a list of the symbols it hasn't been ableto resolve yet. When all of the explicitly specified objects are donewith, the linker now has another place to look for the symbols thatare left on this unresolved list—in the library. If the unresolvedsymbol is defined in one of the objects in the library, then that object isadded in, exactly as if the user had given it on the command line in the firstplace, and the link continues.

Note the granularity of what gets pulled in from the library: if someparticular symbol's definition is needed, the whole object that containsthat symbol's definition is included. This means that the process canbe one step forwards, one step back—the newly added object mayresolve one undefined reference, but it may well come with a wholecollection of new undefined references of its own for the linker toresolve.

Another important detail to note is the order of events; thelibraries are consulted only when then the normal linking is done, andthey are processed in order, left to right. This means that ifan object pulled in from a library late in the link line needs asymbol from a library earlier in the link line, the linker won'tautomatically find it.

An example should help to make this clearer; let's suppose we have thefollowing object files, and a link line that pulls ina.o, b.o, -lx and-ly.

Once the linker has processed a.o and b.o,it will have resolved the references to b2 anda3, leaving x12 and y22 asstill undefined. At this point, the linker checks the firstlibrary libx.a for these symbols, and finds that it can pull inx1.o to satisfy the x12 reference;however, doing so also adds x23 and y12to the list of undefined references (so the list is nowy22, x23 and y12).

The linker is still dealing with libx.a, sothe x23 reference is easily satisfied, by also pulling inx2.o from libx.a. However, this also addsy11 to the list of undefineds (which is now y22,y12 and y11). None of these can be resolvedfurther using libx.a, so the linker moves on toliby.a.

Here, the same sort of process applies and the linker will pull inboth of y1.o and y2.o. The first of theseadds a reference to y21, but since y2.o isbeing pulled in anyway, that reference is easily resolved. The netof this process is that all of the undefined references have beenresolved, and some but not all of the objects in the libraries havebeen included into the final executable.

Notice that the situation would have been a little different if (say)b.o also had a reference to y32. If thishad been the case, the linking of libx.a would haveworked the same, but the processing of liby.a would alsohave pulled in y3.o. Pulling in this object would haveadded x31 to the list of unresolved symbols, and the link wouldhave failed—by this stage the linker has already finished withlibx.a and would not find the definition (in x3.o)for this symbol.

(By the way, this example has a cyclic dependency between thetwo libraries libx.a and liby.a; this istypically a Bad Thing, particularly on Windows)

Shared Libraries

For popular libraries like the C standard library (normallylibc), having a static library has an obviousdisadvantage—every executable program has a copy of thesame code. This can take up a lot of unnecessary disk space, if everysingle executable file has a copy of printf andfopen and suchlike.

A slightly less obvious disadvantage is that once a program has beenstatically linked, the code in it is fixed forever. If someone findsand fixes a bug in printf, then every program has to belinked again in order to pick up the fixed code.

To get around these and other problems, shared libraries wereintroduced (normally indicated by a .so extension, or.dll on Windows machines and.dylib on Mac OS X). For these kinds oflibraries, the normal command line linker doesn't necessarily join upall of the dots. Instead, the regular linker takes a kind of 'IOU'note, and defers the payment of that note until the moment when theprogram is actually run.

What this boils down to is this: if the linker finds that thedefinition for a particular symbol is in a shared library, then itdoesn't include the definition of that symbol in the finalexecutable. Instead, the linker records the name of symbol and which libraryit is supposed to come from in the executable file instead.

When the program is run, the operating system arranges that theseremaining bits of linking are done 'just in time' for the program torun. Before the main function is run, a smaller versionof the linker (often called ld.so) goes through thesepromissory notes and does the last stage of the link there andthen—pulling in the code of the library and joining up all of thedots.

This means that none of the executable files have a copy of the codefor printf. If a new, fixed, version ofprintf is available, it can be slipped in just bychanging libc.so—it'll get picked up the next timeany program runs.

There's another big difference with how shared libraries work comparedto static libraries, and that shows up in the granularity of thelink. If a particular symbol is pulled in from a particular shared library (sayprintf in libc.so), then the whole ofthat shared library is mapped into the address space of the program.This is very different from the behavior of a static library, whereonly the particular objects that held undefined symbols got pulled in.

Put another way, a shared library is itself produced as a result of arun of the linker (rather than just forming a big pile of objects likear does), with references between objects in the samelibrary getting resolved. Once again, nm is a usefultool for illustrating this: for the examplelibraries above it will produce sets of results for the individual objectfiles when run on a static version of the library, but for the sharedversion of the library, liby.so has only x31as an undefined symbol. Also, for the library-ordering example at theend of the previous section, there wouldn't be a problem:adding a reference to y32 into b.c wouldmake no difference, as all of the contents of y3.o andx3.o are already pulled in anyway.

As an aside, another useful tool is ldd; on Unix platforms this shows the set of shared libraries that an executable (or a shared library) depends on, together with an indication of where those libraries are likely to be found. For the program to run successfully, the loader needs to be able to find all of these libraries, together with all of their dependencies in turn. (Typically, the loader looks for libraries in the list of directories held in the LD_LIBRARY_PATH environment variable.)

The reason for this larger granularity is because modern operatingsystems are clever enough that you can save more than just theduplicate disk space that happens with static libraries; differentrunning processes that use the same shared library can also share thecode segment (but not the data/bss segments—two differentprocesses could be in different places for their strtokafter all). In order to do this, the whole library has to be mappedin one go, so that the internal references all line up to the sameplaces—if one process pulled in a.o andc.o and another pulled inb.o and c.o, there wouldn't be anycommonality for the OS to leverage.

Windows DLLs

Although the general principles of shared libraries are roughly similaron Unix platforms and Windows, that are a few details that can catchout the unwary.

Exporting Symbols

The most major difference between the two is that symbols are notautomatically exported by Windows libraries. On Unix, allof the symbols from all of the object files that were linked intothe shared library are visible to users of the library. On Windows,the programmer has to explicitly choose to make particular symbolsvisible—i.e. to export them.

There are three ways to export a symbol from a Windows DLL (andall three ways can be mixed together in the same library).

  • In the source code, declare the symbol as __declspec(dllexport), thusly:
  • On the invocation of the linker, use the /export:symbol_to_exportoption to LINK.EXE.
  • Get the linker to pull in a module definition (.DEF) file (by using the /DEF:def_file linker option), and in that file include an EXPORTS section that contains the symbols you want to export.

Once C++ is added in to the mix, the first of these options is the easiest because thecompiler takes care of the name mangling for you.

.LIB and Other Library-Related Files

This neatly leads on to the second complication with Windows libraries: the information aboutexported symbols that the linker needs to join things up is not held in the DLL itself. Instead,this information is held in a corresponding .LIB file.

The .LIB file associated with a DLL describes what (exported) symbols are present in theDLL, together with their locations. Any other binary that uses the DLL needs to look in the .LIBfile so that it can join up the symbols correctly.

To confuse things, the .LIB extension is also used for static libraries.

In fact, there are a wide variety of different files that can be relevant for Windows libraries.As well as the .LIB file and the (optional) .DEF file mentioned in the previoussection, you might see all of the following files associated with your Windows library.

  • Link output files:
    • library.DLL: The library code itself; this is needed (at run-time) by any executable that uses the library.
    • library.LIB: An 'import library' file which describes what symbols are where in the output DLL. This file is only produced if the DLL exports some symbols; if no symbols are exported, there is no point in having the .LIB file. This file is needed at link-time by anything that uses this library.
    • library.EXP: An 'export file' for the library being linked, which is needed when linking binaries with circular dependencies.
    • library.ILK: If the /INCREMENTAL option was specified to the linker so that incremental linking is enabled, this file holds the status of the incremental linking. Needed for any future incremental linking of this library.
    • library.PDB: If the /DEBUG option was specified to the linker, this file is a program database containing debugging information for the library.
    • library.MAP: If the /MAP option was specified to the linker, this file holds a description of the internal layout of the library.
  • Link input files:
    • library.LIB: An 'import library' file which describes what symbols are where in any other DLLs that are needed by the thing being linked.
    • library.LIB: A static library file which contains a collection of object files that are needed by the thing being linked. Note the ambiguous use of the .LIB extension.
    • library.DEF: A 'module definition' file which allows control of various details of the linked library, including the export of symbols.
    • library.EXP: An 'export file' for the library being linked, which can indicate that a previous run of LIB.EXE for the library has already created the .LIB file for the library. Relevant when linking binaries with circular dependencies.
    • library.ILK: Incremental linking status file; see above.
    • library.RES: Resource file that contains information about the various GUI widgets that the executable uses; these are included in the final binary file.

This is contrast to Unix, where most of the information held in these extra files is (usually) just includedin the library itself.

Importing Symbols

As well as requiring DLLs to explicitly declare which symbols they export, Windowsalso allows binaries that use library code to explicitly declare which symbols they import.This is optional, but gives a speed optimization due to somehistorical features of 16-bit windows.

To do this, declare the symbolas __declspec(dllimport) in the source code, thusly:

It's normal good practice in C to have a single declaration for any function or global variable, held in aheader file. This leads to a bit of a conundrum: the code in the DLL that holds the definition of thefunction/variable needs to export the symbol, but any code outside the DLL needs to import thesymbol.

A common way round this is to use a preprocessor macro in the header file.

The C file in the DLL which defines the function and variable ensures thatthe preprocessor variable EXPORTING_XYZ_DLL_SYMSis #defined before it includes this header file, and so does an export of the symbols.Any other code that pulls in this header file doesn't define the symbol and so indicates an import of the symbols.

Circular Dependencies

One final complication with DLLs is that Windows is stricter than Unix in requiring every symbol tohave a resolution at link time. On Unix, it's possible to link a shared library that contains anunresolved symbol that the linker has never seen; in this situation, any other code that pulls in thisshared library must provide that symbol, or the program will fail to load. Windows doesn't allow thissort of laxity.

In most systems this isn't a problem. Executables rely on high-level libraries, the high-level librariesrely on lower-level libraries, and everything gets linked in the opposite order—low-level librariesfirst, then higher-level libraries, and finally the executables that rely on it all.

However, if there are circular dependencies between binaries, then things are trickier. If X.DLLneeds a symbol from Y.DLL, and Y.DLL needs a symbol from X.DLL, thenthere is a chicken-and-egg problem: whichever library is linked first won't be able to find all of itssymbols.

Windows does provide a way around this,roughly as follows.

  • First, fake a link of library X. Run LIB.EXE (not LINK.EXE) to produce an X.LIB file that is the same as would have been produced by LINK.EXE. No X.DLL file is produced, but a X.EXP file does get emitted.
  • Link library Y as normal; this pulls in the X.LIB file from the previous step, and outputs both a Y.DLL and a Y.LIB file.
  • Finally link library X properly. This is almost the same as normal, but it additionally includes the X.EXP file created in the first step. As normal, this link will pull in the Y.LIB file from the previous step and will create a X.DLL file. Unlike normal, the link will skip the process of creating an X.LIB file, because there one already there from the first step (which is what the .EXP file indicates).

Of course, a better idea is usually to re-organize the libraries so that there aren't any circulardependencies….

Adding C++ To The Picture

C++ provides a number of extra features over and above what'savailable in C, and a number of these features interact with theoperation of the linker. This wasn't originally the case—thefirst C++ implementations came as a front end to a C compiler, so theback end of the linker didn't need to be changed—but as time wenton, sufficiently sophisticated features were added that the linker hadto be enhanced to support them.

Function Overloading & Name Mangling

The first change that C++ allows is the ability to overload afunction, so there can be different versions of the same namedfunctions, differing in the types that the function accepts (thefunction's signature):

This obviously gives a problem for the linker: when some other coderefers to max, which one does it mean?

The solution that was adopted for this is called namemangling, because all of the information about the functionsignature is mangled into a textual form, and that becomes the actualname of the symbol as seen by the linker. Different signaturefunctions get mangled to different names, so the uniqueness problemgoes away.

I'm not going to go into details of the schemes used (which vary fromplatform to platform anyway), but a quick look at the object filecorresponding to the code above gives some hints (remember,nm is your friend!):

Here we can see that our three functions called max allget different names in the object files, and we can make a fairlyshrewd guess that the two letters after the 'max' are encoding thetypes of the parameters—'i' for int, 'f' forfloat and 'd' for double (things get a lotmore complex when classes, namespaces, templates and overloadedoperators get added into the mangling mix, though!).

It's also worth noting that there will normally be some way ofconverting between the user-visible names for things (thedemangled names) and the linker-visible names for things (themangled names). This might be a separate program(e.g. c++filt) or a command-line option(e.g. --demangle as an option to GNU nm), which givesresults like:

The area where this mangling scheme most commonly trips people up iswhen C and C++ code is intermingled. All of the symbols produced bythe C++ compiler are mangled; all of the symbols produced by the Ccompiler are just as they appear in the source file. To get aroundthis, the C++ language allows you to put extern'C' around the declaration & definition of a function.This basically tells the C++ compiler that this particular name shouldnot be mangled—either because it's the definition of a C++function that some C code needs to call, or because it's a C functionthat some C++ code needs to call.

For the example given right at the start of this page, it's easy tosee that there's a good chance someone has forgotten this extern'C' declaration in their link of C and C++ together.

The big hint here is that the error message includes a functionsignature—it's not just complaining about plain oldfindmax missing. In other words, the C++ code isactually looking for something like '_Z7findmaxii' but only finding'findmax', and so it fails to link.

By the way, note that an extern'C' linkage declaration is ignored for member functions (7.5.4of the C++ standard).

Initialization of Statics

The next feature that C++ has over C that affects the linker is theability to have object constructors. A constructor is a pieceof code that sets up the contents of an object; as such it isconceptually equivalent to an initializer value for a variable butwith the key practical difference that it involves arbitrary pieces ofcode.

Recall from an earlier section that a globalvariable can start off with a particular value. In C, constructing theinitial value of such a global variable is easy: the particular valueis just copied from the data segment of the executablefile into the relevant place in the memory for the soon-to-be-runningprogram.

In C++, the construction process is allowed to be much morecomplicated than just copying in a fixed value; all of the code in thevarious constructors for the class hierarchy has to be run, before theprogram itself starts running properly.

To deal with this, the compiler includes some extra information in theobject files for each C++ file; specifically, the list of constructorsthat need to be called for this particular file. At link time, thelinker combines all of these individual lists into one big list, andincludes code that goes through the list one by one, calling all ofthese global object constructors.

Note that the order in which all of these constructors forglobal objects get called is not defined—it's entirely at themercy of what the linker chooses to do. (See Scott Meyers' EffectiveC++ for more details—Item 47 in thesecondedition, Item 4 in thethird edition).

We can hunt down these lists by once again using nm.Consider the following C++ file:

For this code, the (demangled) output of nm gives:

There are various things here, but the one we're interested in is thetwo entries with class as W (which indicates a 'weak' symbol)and with section names like'.gnu.linkonce.t.stuff'. These are the markersfor global object constructors, and we can see that the corresponding'Name' fields look sensible—one for each of the two constructorsused.

Templates

In an earlier section, we gave an example of threedifferent versions of a max function, each of which tookdifferent types of argument. However, we can see that the lines ofsource code for these three functions are absolutely identical, and itseems a shame to have to copy and paste identical code.

C++ introduces the idea of templates to allow code like this tobe written once and for all. We can create a header filemax_template.h with the single unique code for max:

and include this header file in C++ code to use the templated function:

This C++ file uses bothmax<int>(int,int)and max<double>(double,double), but a different C++file might use different instantiations of the template—saymax<float>(float,float)or evenmax<MyFloatingPointClass>(MyFloatingPointClass,MyFloatingPointClass).

Each of these different instantiations of the template involvesdifferent actual machine code, so by the time that the program isfinally linked, the compiler and linker need to make sure thatevery instantiation of the template that is used has code includedinto the program (and no unused template instantiations are includedto bloat the program size).

So how do they do this? There are normally two ways of arrangingthis: by folding duplicate instantiations, or by deferringinstantiation until link time (I like to refer to these as the saneway and the Sun way).

For the duplicate instantiation approach, each object file containsthe code for all of the templates that it uses. For the particularexample C++ file above, the contents of the object file are:

and we can see that both max<int>(int,int)and max<double>(double,double) are present.

These definitions are listed as weak symbols, and this meansthat when the linker produces the final executable program, it canthrow away all but one of these duplicate definitions (and if it'sfeeling generous, it can check that all the duplicate definitionsactually look like they are the same code). The most significantdownside of this approach is that all of the individual object filestake up much more room on the hard disk.

The other approach (which is used by the Solaris C++ compiler suite) isto include none of the template definitions in the object files, butinstead to leave them all as undefined symbols. When it comes to linktime, the linker can collect together all of the undefined symbolsthat actually correspond to template instantiations, and go andgenerate the machine code for these instantiations there and then.

A New Inheritance

This saves space in the individual object files, but has thedisadvantage that the linker needs to keep track of where the headerfile containing the source code, and needs to be able to invoke theC++ compiler at link time (which may slow down the link).

Dynamically Loaded Libraries

The last feature that we'll talk about on this page is the dynamicloading of shared libraries. A previous sectiondescribed how using shared libraries means that thefinal link is deferred until the moment when the program is run. Onmodern systems, it's possible to defer linking to even later than that.

This is done with a pair of system calls, dlopen anddlsym (the rough Windows equivalents of these are calledLoadLibrary and GetProcAddress). The firstof these takes the name of a shared library and loads it into theaddress space of the running process. Of course, this extra librarymay itself have undefined symbols, so this call to dlopenmay also trigger the loading of other shared libraries.

The dlopen also allows the choice ofwhether to resolve all of these references at the instant that thelibrary is loaded (RTLD_NOW), or one by one as eachundefined reference is hit (RTLD_LAZY). The first waymeans that the dlopen call takes much longer, but thesecond way involves the slight risk that sometime later the programwill discover that there is an undefined reference that can't beresolved—at which point, the program will be terminated.

Of course, there's no way for a symbol from the dynamically loadedlibrary to have a name. However, as ever with programming problems,this is easily solved by adding an extra level of indirection—inthis case, by using a pointer to the space for the symbol, rather thanreferring to it by name. The call dlsym takes a stringparameter that gives the name of the symbol to be found, and returns apointer to its location (or NULL if it can't be found).

Interaction with C++ Features

This dynamic loading feature is all very spangly, but how does itinteract with the various C++ features that affect the overallbehavior of linkers?

The first observation is that mangled names are a bit tricky. Whendlsym is called, it takes a string containing the name ofthe symbol to be found. This has to be the linker-visible version ofthe name; in other words, the mangled version of the name.

Because the particular name mangling schemes can vary from platform toplatform and from compiler to compiler, this means that it's prettymuch impossible to dynamically locate a C++ symbol in a portable way.Even if you're happy to stick to one particular compiler and delvearound in its internals, there are more problems in store—foranything other than vanilla C-like functions, you have to worry aboutpulling vtables and such like.

All in all, it's usually best to just stick to having a single, wellknown extern 'C' entrypoint that can bedlsymed; this entrypoint can be a factory method thatreturns pointers to full instances of a C++ class, allowing all of theC++ goodness to be accessed.

The compiler can sort out constructors for global objects in adlopened library because there are a couple of specialsymbols that can be defined in the library and whichthe linker (whether load-time or run-time) will call when thelibrary is dynamically loaded or unloaded—so the necessaryconstructor and destructor calls can be put there.In Unix these are functions called _init and_fini, or for morerecent systems using the GNU toolchain, these are any functionsmarked with __attribute__((constructor)) or__attribute__((destructor)). In Windows,the relevant function is DllMainwith a reason parameter or DLL_PROCESS_ATTACHor DLL_PROCESS_DETACH.

Finally, dynamic loading works fine with the 'fold duplicates'approach to template instantiation, but is much trickier with the'compile templates at link time' approach—in this case, 'linktime' is after the program is running (and possibly on a differentmachine than holds the source code). Check the compiler & linkerdocumentation for ways round this.

More Details

The contents of this page have deliberately skipped a lot of detailsabout how linkers work, because I've found that the level ofdescription here covers 95% of the everyday problems that programmersencounter with the link steps for their programs.

If you want to go further, some additional references are:

  • John Levine, Linkers and Loaders: contains lots and lots of information about the details of linkers and loaders work, including all the things I've skipped here. There also appears to be an online version of it (or an early draft of it) here
  • Excellent link on the Mach-O format for binaries on Mac OS X [Added 27-Mar-06]
  • Peter Van Der Linden, Expert C Programming: excellent book which includes more information about how C code transforms into a running program than any other C text I've encountered
  • Scott Meyers, More Effective C++: Item 34 covers the pitfalls of combining C and C++ in the same program (whether linker-related or not).
  • Bjarne Stroustrup, The Design and Evolution of C++: section 11.3 discusses linkage in C++ and how it came about
  • Margaret A. Ellis & Bjarne Stroustrup, The Annotated C++ Reference Manual: section 7.2c describes one particular name mangling scheme
  • Two interesting articles on creating tiny Linux executables and a minimal Hello World in particular.
  • 'How To Write Shared Libraries' [PDF] by Ulrich Drepper has more details on ELF and relocation.

Many thanks to Mike Capp and Ed Wilson for useful suggestions about this page.

Copyright (c) 2004-2005,2009-2010 David Drysdale

Permission is granted to copy, distribute and/or modify this documentunder the terms of the GNU Free Documentation License, Version 1.1 or anylater version published by the Free Software Foundation; with no InvariantSections, with no Front-Cover Texts, and with no Back-Cover Texts. A copyof the license is availablehere.