Linkers part 2

I’m back, and I’m still doing the linker technical introduction.

Shared libraries were invented as an optimization for virtual memory systems running many processes simultaneously. People noticed that there is a set of basic functions which appear in almost every program. Before shared libraries, in a system which runs multiple processes simultaneously, that meant that almost every process had a copy of exactly the same code. This suggested that on a virtual memory system it would be possible to arrange that code so that a single copy could be shared by every process using it. The virtual memory system would be used to map the single copy into the address space of each process which needed it. This would require less physical memory to run multiple programs, and thus yield better performance.

I believe the first implementation of shared libraries was on SVR3, based on COFF. This implementation was simple, and basically assigned each shared library a fixed portion of the virtual address space. This did not require any significant changes to the linker. However, requiring each shared library to reserve an appropriate portion of the virtual address space was inconvenient.

SunOS4 introduced a more flexible version of shared libraries, which was later picked up by SVR4. This implementation postponed some of the operation of the linker to runtime. When the program started, it would automatically run a limited version of the linker which would link the program proper with the shared libraries. The version of the linker which runs when the program starts is known as the dynamic linker. When it is necessary to distinguish them, I will refer to the version of the linker which creates the program as the program linker. This type of shared libraries was a significant change to the traditional program linker: it now had to build linking information which could be used efficiently at runtime by the dynamic linker.

That is the end of the introduction. You should now understand the basics of what a linker does. I will now turn to how it does it.

Basic Linker Data Types

The linker operates on a small number of basic data types: symbols, relocations, and contents. These are defined in the input object files. Here is an overview of each of these.

A symbol is basically a name and a value. Many symbols represent static objects in the original source code–that is, objects which exist in a single place for the duration of the program. For example, in an object file generated from C code, there will be a symbol for each function and for each global and static variable. The value of such a symbol is simply an offset into the contents. This type of symbol is known as a defined symbol. It’s important not to confuse the value of the symbol representing the variable my_global_var with the value of my_global_var itself. The value of the symbol is roughly the address of the variable: the value you would get from the expression &my_global_var in C.

Symbols are also used to indicate a reference to a name defined in a different object file. Such a reference is known as an undefined symbol. There are other less commonly used types of symbols which I will describe later.

During the linking process, the linker will assign an address to each defined symbol, and will resolve each undefined symbol by finding a defined symbol with the same name.

A relocation is a computation to perform on the contents. Most relocations refer to a symbol and to an offset within the contents. Many relocations will also provide an additional operand, known as the addend. A simple, and commonly used, relocation is “set this location in the contents to the value of this symbol plus this addend.” The types of computations that relocations do are inherently dependent on the architecture of the processor for which the linker is generating code. For example, RISC processors which require two or more instructions to form a memory address will have separate relocations to be used with each of those instructions; for example, “set this location in the contents to the lower 16 bits of the value of this symbol.”

During the linking process, the linker will perform all of the relocation computations as directed. A relocation in an object file may refer to an undefined symbol. If the linker is unable to resolve that symbol, it will normally issue an error (but not always: for some symbol types or some relocation types an error may not be appropriate).

The contents are what memory should look like during the execution of the program. Contents have a size, an array of bytes, and a type. They contain the machine code generated by the compiler and assembler (known as text). They contain the values of initialized variables (data). They contain static unnamed data like string constants and switch tables (read-only data or rdata). They contain uninitialized variables, in which case the array of bytes is generally omitted and assumed to contain only zeroes (bss). The compiler and the assembler work hard to generate exactly the right contents, but the linker really doesn’t care about them except as raw data. The linker reads the contents from each file, concatenates them all together sorted by type, applies the relocations, and writes the result into the executable file.

Basic Linker Operation

At this point we already know enough to understand the basic steps used by every linker.

  • Read the input object files. Determine the length and type of the contents. Read the symbols.
  • Build a symbol table containing all the symbols, linking undefined symbols to their definitions.
  • Decide where all the contents should go in the output executable file, which means deciding where they should go in memory when the program runs.
  • Read the contents data and the relocations. Apply the relocations to the contents. Write the result to the output file.
  • Optionally write out the complete symbol table with the final values of the symbols.

More tomorrow.

14 Comments »

  1. ncm said,

    August 27, 2007 @ 6:44 pm

    Apollo Aegis had shared libraries right from the beginning, in 1981. (Aegis heritage was usually traced directly to Multics, bypasing Unix.) Each shared library was assigned a fixed position in the address space, and each symbol given a fixed global 16-bit ID and entry in a table. Big programs and libraries tended to crowd that table, so Mentor Graphics had to poke out such unused C library functions as qsort.

  2. Ian Lance Taylor said,

    August 27, 2007 @ 9:45 pm

    Thanks for the info. I used Apollo Aegis systems around 1985, but I only programmed them in T, never in any compiled language. From the description, it seems pretty similar to SVR3 shared libraries.

  3. ncm said,

    August 28, 2007 @ 11:54 am

    Apollo Aegis was interesting in a number of other ways. All code, shared library or main program, were directly mapped (a la mmap), so the code was all concentrated at the beginning of the file, with annotations after. Page faults for code loaded via the net were satisfied via the net. The file system expanded environment variables in symbolic link text, a feature since implemented (to my knowledge, only) in DGUX and Dragonfly BSD. Apollo’s DSEE version control (and build) system became the basis for ClearCase. Apollo’s ACL permissions system and its remote procedure call apparatus was the basis for much of DCE and, thence, Microsoft CIFS.

  4. Mark J. Wielaard » Ian Lance Taylor’s Linker Notes said,

    August 31, 2007 @ 8:21 am

    […] Linkers part 2 – Linker Technical Introduction, Basic Linker Data Types, Basic Linker Operations. […]

  5. Joe Buck said,

    September 12, 2007 @ 9:16 pm

    Dec’s VMS had shared libraries from the beginning, in 1980. I was a VMS user before I was a Unix user (and before that used DEC’s RSX-11 and RT-11), and was regularly stunned when I went to grad school at UC Berkeley at all of the grad students who thought that any given computer science concept was invented when it first appeared in some flavor of Unix.

  6. Joe Buck said,

    September 12, 2007 @ 9:20 pm

    Also, I recall that the VMS shared library implementation was quite modern, in the sense that it used position-independent code and mapped shared libraries into address spaces at any point. The page size was tiny, however, only 512 bytes. But then, a whole department would share one massive Vax 11/780 with a whopping 2 Mb of memory back when I started.

  7. Ian Lance Taylor said,

    September 13, 2007 @ 10:26 am

    Thanks for the note. I used TOPS-20 some in high school, but I never used VMS very much.

  8. jrlevine said,

    September 13, 2007 @ 3:40 pm

    I think you’ll find that shared libraries go back to Multics in about 1969. The Multics machines had hardware segments (sort of like the 286’s but bigger) with each segment dynamically linking to others. Before that, executables with shared code were common, so that if three people were using the text editor they’d all share the same copy of the code, but each program had all of the libraries it needed linked into it. The PDP-6 timesharing system had that probably by 1965, early PDP-11 Unix by 1972 or 3. Again, these ideas go way, way back.

  9. rskrishnan said,

    October 8, 2007 @ 12:46 pm

    I think shared libraries have been around for a while. I have used VMS systems with some _very_ sophisticated linkers and loaders. I’ve also “seen” as/400 systems (but their terminology is totally gibberish to me).

    I really liked assemblers and linkers as discussed in “Systems Programming” by John J. Donovan. Very exhaustive discussion on what happens at each stage of the compile/link/load/execute process. Very informative and assumes very little knowledge going in.

  10. Ian Lance Taylor said,

    October 8, 2007 @ 10:07 pm

    Thanks for the note. Maybe some day I’ll research these earlier systems.

    Thanks for the pointer to Donovan’s book; I’m not familiar with it.

  11. Jessica Hamilton said,

    October 12, 2008 @ 6:39 pm

    Hi Ian,

    Your series on linkers has been interesting and informative. Especially since I am attempting (seemingly in vain) to write a very basic linker for ELF. No shared libraries or other strange stuff. Just combine objects and static libraries into a basic executable.

    I understand the basics of how it works, but haven’t really been able to figure out how to piece it together. I can parse objects and libraries, parse symbol tables, and print out most of this sort of information.

    I am hoping you could help me with a bit more of a breakdown of how to put this altogether. Something kind of like pseudo-code.

    Many Thanks,

    Jessica

  12. Ian Lance Taylor said,

    October 13, 2008 @ 9:21 pm

    Thanks for the note. I recommend that you look at the source code for the linker I wrote, gold. It’s even better than pseudo-code: it’s real code.

    To get a working linker concentrate on building the symbol table, placing the input sections in the output file, and applying relocations.

  13. Jessica Hamilton said,

    October 13, 2008 @ 11:27 pm

    Thanks Ian. Hopefully I can scrape the mechanics of linking out of all the multi-threading and syntax in general! My eyes tend to glaze over with C/C++, but maybe I’ll get there.

    Pseudo-code does have the advantage of simplicity over real code, btw ;-)

  14. berkus said,

    January 2, 2009 @ 10:31 am

    Jessica, I’m probably too late for the party, but take a look at this simple ELF linker:
    http://bzr.madfire.net/odin/files/head%3A/tools/sjofn/

RSS feed for comments on this post · TrackBack URI

Leave a Comment

You must be logged in to post a comment.