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 each word consists 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, a use list, and the program text itself.
The definition list consists of a count N followed by N definitions. Each definition is a pair (sym, loc) signifying that sym is defined at relative address loc.
The use list consists of a count N followed by N uses. Each use is again a pair (sym, loc), but this time signifying that sym is used in the linked list started at loc. The address in loc points to the next use of sym. An address of 777 is the sentinel ending the list.
The program text consists of a count N followed by N pairs (type, word), where word is a 4-digit instruction as described above and type is a single character indicating if the address in the word is Immediate, Absolute, Relative, or External.
The actions taken by the linker depend on the type of the address, as we now illustrate. Consider the first input set from the lab.
4
1 xy 2
2 xy 4 z 2
5 R 1004 I 5678 E 2777 R 8002 E 7777
0
1 z 3
6 R 8001 E 1777 E 1001 E 3002 R 1002 A 1010
0
1 z 1
2 R 5001 E 4777
1 z 2
1 xy 2
3 A 8000 E 1777 E 2001
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.
The resulting output (shown below) is more detailed than I expect you to produce. The detail is there to help me explain what the linker is doing. All I would expect from you is the symbol table and the rightmost column of the memory map.
Symbol Table
xy=2
z=15
Memory Map
+0
0: R 1004 1004+0 = 1004
1: I 5678 5678
2: xy: E 2777 ->z 2015
3: R 8002 8002+0 = 8002
4: E 7777 ->xy 7002
+5
0 R 8001 8001+5 = 8006
1 E 1777 ->z 1015
2 E 1001 ->z 1015
3 E 3002 ->z 3015
4 R 1002 1002+5 = 1007
5 A 1010 1010
+11
0 R 5001 5001+11= 5012
1 E 4777 ->z 4015
+13
0 A 8000 8000
1 E 1777 ->xy 1002
2 z: E 2001 ->xy 2002
Note: 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.
Detailed requirements can be found in req/lab1-linker.pdf.
Testable inputs and outputs can be found in deliverables/tests.
This README file is adapted from Professor Yan Shvartzshnaider's Operating System class, originally written by Professor Allan Gottlieb.