Originally called a linkage editor by IBM.
A linker is an example of a utility program included with an operating system distribution. Like a compiler, the linker is not part of the operating system per se, i.e. it does not run in supervisor mode. Unlike a compiler it is OS dependent (what object/load file format is used) and is not (normally) language dependent.
Link of course.
When the compiler and assembler have finished processing a module, they produce an object module that is almost runnable. There are two remaining tasks to be accomplished for the object module to be runnable. Both are involved with linking (that word, again) together multiple object modules. The tasks are relocating relative addresses and resolving external references.
The output of a linker is called a load module because it is now ready to be loaded and run.
To see how a linker works lets consider the following example, which is the first dataset from lab #1. The description in lab1 is more detailed.
The target machine is word addressable and has a memory of 250 words, each consisting of 4 decimal digits. The first (leftmost) digit is the opcode and the remaining three digits form an address.
Each object module contains three parts, a definition list, the program text itself, and a use list. Each definition is a pair (sym, loc). Each use is a symbol.
The program text consists of a count N followed by N pairs (type, word), where word is a 4-digit instruction described above and type is a single character indicating if the address in the word is Immediate, Absolute, Relative, or External.
Input set #1 1 xy 2 2 z xy 5 R 1004 I 5678 E 2000 R 8002 E 7001 0 1 z 6 R 8001 E 1000 E 1000 E 3000 R 1002 A 1010 0 1 z 2 R 5001 E 4000 1 z 2 2 xy z 3 A 8000 E 1001 E 2000
The first pass simply finds the base address of each module and produces the symbol table giving the values for xy and z (2 and 15 respectively). The second pass does the real work using the symbol table and base addresses produced in pass one.
Symbol Table xy=2 z=15 Memory Map +0 0: R 1004 1004+0 = 1004 1: I 5678 5678 2: xy: E 2000 ->z 2015 3: R 8002 8002+0 = 8002 4: E 7001 ->xy 7002 +5 0 R 8001 8001+5 = 8006 1 E 1000 ->z 1015 2 E 1000 ->z 1015 3 E 3000 ->z 3015 4 R 1002 1002+5 = 1007 5 A 1010 1010 +11 0 R 5001 5001+11= 5012 1 E 4000 ->z 4015 +13 0 A 8000 8000 1 E 1001 ->z 1015 2 z: E 2000 ->xy 2002
(Unofficial) Remark: It is faster (less I/O) to do a one pass approach, but is harder since you need ``fix-up code'' whenever a use occurs in a module that precedes the module with the definition.
The linker on unix is mistakenly called ld (for loader), which is unfortunate since it links but does not load.
Lab #1: Implement a linker. The specific assignment is detailed on the sheet handed out in in class and is due in three weeks. The content of the handout is available on the web as well (see the class home page).