The 2.5 kinds of program linking and how they work.
Programmers write a bunch of “how to” instructions typically bundled as subroutines. Usually, these involve accessing other subroutines. After the compiler turns the source code into machine code it is the job of the linker and loader to make sure each subroutine can find each other subroutine it wants to use.
The static linker takes the assorted machine-code subroutines that came out of the compiler, as well as from some static library files, and combines them into an “executable”. Executables are just files in a particular format: in Linux they are ELF, in Windows they are PE/COFF, and in OS X they are DWARF. There are reasons to care about the file format, but for our purposes they are all roughly the same.
The biggest thing a static linker needs to do is assign addresses to everything. Internally, computers work with numbered bins instead of names, so everything in the program needs to get a bin number (or address). So the linker translates quasi-machine-code versions of “invoke the ‘splashscreen’ subroutine” into true machine-code versions of “invoke 72165334” “splashscreen” and “72165334” are just random examples and places the code for “splashscreen” starting at address 72165334. Since the compiler often generates addresses internally, this also involves changing all those numbers to be relative to the starting addresses.
Mostly, when a static linker works no one even notices it is there. There are some tricks a linker can do to lay out memory to help prevent common security holes, improve code cache performance, etc., but these are fairly specialized topics.
A linked executable contains all the information that is needed to initialize memory prior to running a program: the subroutines all have addresses, the data all has addresses, the subroutines know about each other and the data they use, and there are instructions for the loader.
The loader is a program that reads an executable and runs the program. This involves setting up memory and similar tasks, as well as re-doing the linker’s job for some dynamic libraries.
Dynamic libraries are like other libraries, except they are linked when you run the program instead of when you compile the program. Dynamic linking allows a slowly-changing program to benefit from improvements in a rapidly-changing library, and it also can improve system performance by saving memory. This latter function depends on virtual memory.
I mentioned earlier that memory is numbered, and this is true. But it turns out there are actually two numbers for each piece of memory. When a program asks for address 10111010110000001001100011100100 the virtual memory system splits it into two pieces: the more-significant bits 101110101100000010 are treated as a “page number” while the remaining bits 01100011100100 are treated as an offset within that page. Physical memory is also split into pages, and there’s a virtual page table that maps each program’s virtual pages onto physical pages.
There is a lot of reasons why virtual memory is a good thing: multiple programs can use the same addresses for different purposes, programs can be prevented from messing with each other’s data, programs can use more memory than is actually present on the computer, and so on. But the big one from the loader’s point of view is that if fifteen program are all using the same dynamic library we can load that library onto just one place in physical memory and map that onto whatever pages are available in each in each program’s virtual address space.
In summary, the loader reads the executable created by the linker, sets up memory as requested by the executable, maps any required libraries into the program’s virtual address space and fixes any addresses that need fixing as a consequence, it is possible no addresses need fixing, depending on how the executable file was designed. and then lets the program run.
There is no particular reason why a loader needs to do the loading of shared libraries before the program begins to run. Another option is to have the program link to the loader itself and invoke the loader’s “load this subroutine from this dynamic library” subroutine as it runs. The mechanics of such run-time loading are the same as execution-time loading.
Run-time loading has both a benefit and a penalty. The benefit is that the program can react to missing libraries. “Try loading the fancy optimized eigenvalue computing subroutine, but if you can’t find it use my sloppy slow version as a backup.” The penalty is that it is hard to tell in advance what libraries are needed because the dynamic libraries aren’t listed in the executable They almost always are present, just as data that will be passed to some subroutine as the program runs rather than in the list of libraries needed. . In my limited experience, run-time loading is common in Windows programming, almost universal in OS X programming, and unusual in Linux programming. Why this should be so, I have no idea.
If you static-link, you need to redistribute your program if someone updates the library. If you dynamic-link to a particular version of a library, same thing. If you dynamic-link to a library without a version some update to that library might break your program. If you dynamic-link to a library without a version but in a special directory only used by your program, then your program can be updated by copying an updated version into that directory; but you have to ship all of your libraries and who is going to know to put the updated version in there anyway?
More on which as this series continues.
Looking for comments…