========================================== Answers for Relocation and Linking Problem ========================================== idallen@ncf.ca Under the heading "Separate Subroutine Assembly" on this page: http://www.algonquinc.on.ca/infosystems/pincka/dat2343/lect062b.htm you will find an LMC main program and two subroutines "PAUSE" and "DBLE". A table containing the relocated and linked code for module "PAUSE" is shown in the last Step 4 in Section 3 "Link Processing" in that page. Here are three questions and answers based on this web page: ============================================================================ 1) Provide a list of the contents of each of the three external tables that would be associated with the object code for each of the three modules MAIN, PAUSE, and DBLE. (That means 3 tables for each of the three modules: 9 tables in all; some of the tables may be empty.) ******* ANSWER: ******* Looking at each of the modules, we can build the nine tables: MAIN: (Note: This module is built starting at location zero.) External Reference Table: PAUSE 02 DBLE 04 DBLE 05 Public Symbol Table: no public symbols given (an omission) (if there were a "MAIN" public symbol, it would be at 00) Relocatable Instruction Table: 00, 03, 06, 07, 08, 09, 11 PAUSE: (Note: This module is built starting at location "-1", not zero!) External Reference Table: no external references Public Symbol Table: PAUSE 00 Relocatable Instruction Table: 00, 01, 02, 04, 05 DBLE: (Note: This module is built starting at location "-1", not zero!) External Reference Table: PAUSE 05 Public Symbol Table: DBLE 00 Relocatable Instruction Table: 00, 02, 03, 06 The code for the DBLE and PAUSE modules was written as if it began at location "-1" (99) not at location "00". (The first location in each of those modules is labelled "99", not "00". This is unusual.) ============================================================================ 2) Using its three tables, do the relocation and linking for the "DBLE" module that starts at location 25/26. Produce a table similar to that produced for "PAUSE" in the last Step 4 in Section 3 "Link Processing". Show the original object code ("values in object file") and the modified (relocated and linked) code ("modified instructions") for the DBLE module. ******* ANSWER: ******* The web page shows the three modules copied into memory in the order MAIN, PAUSE, DBLE. DBLE started loading at memory location 25. (The *label* "DBLE" ended up at location 26.) DBLE was built separately as if it loaded at mailbox location "-1" (99). (This is unusual - most modules are built to start at zero!) We actually loaded the DBLE module in memory starting at location 25, so to relocate it we must add 25 - (-1) = 26 to every memory reference in the module, including memory references in all three tables in the module. (Note that the DBLE *module* loaded starting at location 25. The Public Symbol "DBLE" now falls at location 26 in memory.) Let's relocate the three tables associated with module DBLE first by adding 26 to every address in the three tables: DBLE: External Reference Table: PAUSE (05 + 26 =) 31 Public Symbol Table: DBLE (00 + 26 =) 26 Relocatable Instruction Table: ([00, 02, 03, 06] + 26 =) 26, 28, 29, 32 Now, let's use the (relocated) addresses in three tables to relocate and link DBLE where it now sits in memory (in mailboxes 25 through 32). First, let's use the Relocatable Instruction Table to tell us which addresses inside DBLE need relocation. We will add 26 to the address fields of the instructions at these locations: 26, 28, 29, 32 The result is: LOC BEFORE AFTER REASON FOR CHANGE --- ------ ----- ------------------------------------------- 26: 902 928 ; added 26 for relocation from -1 to 25 28: 101 127 ; same 29: 301 327 ; same 32: 999 925 ; same Next, let's use the External Reference Table to tell us which addresses inside DBLE need linking to external symbols. The table only has one entry in it: "PAUSE 31"; we only have one reference to an external symbol, PAUSE, to find and link in. We loaded the label PAUSE into memory at location 17. (The *module* PAUSE loaded starting at location 16; the *symbol* PAUSE ended up at location 17.) Our External Reference Table now says that we must add that address 17 to memory location 31. The result is: LOC BEFORE AFTER REASON FOR CHANGE --- ------ ----- ---------------------------------- 31: 000 017 ; address of "PAUSE" linked in (added) That completes the relocation and the linking for DBLE. The final result for the whole DBLE module in memory is: LOC BEFORE AFTER REASON FOR CHANGE --- ------ ----- ------------------------------------------- 25: 000 000 26: 902 928 ; DBLE: added 26 for relocation from -1 to 25 27: 000 000 28: 101 127 ; DBLE: added 26 for relocation from -1 to 25 29: 301 327 ; DBLE: added 26 for relocation from -1 to 25 30: 600 600 31: 000 017 ; address of "PAUSE" linked in (added) 32: 999 925 ; DBLE: added 26 for relocation from -1 to 25 ============================================================================ 3) Assuming the modules were loaded in the new order DBLE, PAUSE, MAIN (with the DBLE module loading starting at location zero, followed by PAUSE and then by the MAIN module), use the information in MAIN's three tables to generate the relocated and linked object code for the MAIN module loaded at its new address. Show the original object code ("values in object file") and the modified (relocated and linked) code ("modified instructions") for the MAIN module. ******* ANSWER: ******* We'll do the relocation and linking for all three modules, since it isn't much more work. From the previous questions, we already have the nine tables we need to do the actual relocation and linking of the three modules, in any order. We have three basic steps: 1) Copy the modules into memory and observe where each gets loaded. 2) Relocate the tables and the instruction codes in memory. 3) Resolve external addresses for the code in memory. ----------------------------------- STEP ONE - COPY MODULES INTO MEMORY ----------------------------------- First the linker copies all the object code into memory in the given order - DBLE, PAUSE, MAIN - without any modifications: LOCATION Contents --------- -------- ------------------------ start of DBLE module (00) 00: 000 01: 902 <-- this is where the DBLE public label is 02: 000 03: 101 04: 301 05: 600 06: 000 <-- this is "CALL PAUSE" 07: 999 ------------------------ end of DBLE, start of PAUSE module (08) 08: 000 09: 106 <-- this is where the PAUSE public label is 10: 407 11: 206 12: 801 13: 900 14: 999 15: 000 16: 001 ------------------------ end of PAUSE, start of MAIN module (17) 17: 113 <-- if MAIN had a label "MAIN", it would be here 18: 600 19: 000 <-- this is "CALL PAUSE" 20: 113 21: 201 <-- this is "STO DBLE+1" 22: 000 <-- this is "CALL DBLE" 23: 113 24: 314 25: 213 26: 415 27: 802 28: 900 29: 700 30: 000 31: 001 32: 010 The above list shows the machine instructions loaded sequentially in memory, one after the other, before any linking or relocation is done. I've added some comments to show where some key instructions and locations are. MAIN didn't have a public label "MAIN"; if it had, the label would be pointing to the first executable instruction of MAIN. Be careful to distinguish the different uses of the names DBLE and PAUSE: The *module* DBLE is 8 instructions long and is loaded starting at address 00. The *label* DBLE is a symbolic public name for a single address inside the DBLE module. They are not the same. The *module* PAUSE is 9 instructions long and is loaded starting at address 08. The *label* PAUSE is a symbolic public name for a single address inside the PAUSE module. They are not the same. --------------------- STEP TWO - RELOCATION --------------------- Having loaded the modules in memory, the linker notes the actual memory address where each module starts and compares it with the memory address where the module was originally built to start. The code for the DBLE and PAUSE modules was written as if it began at location "-1" (99) not at location "00". (The first location in each of those modules is labelled "99", not "00". This is unusual.) Here's a summary of where the modules were originally built to load, and where the linker actually loaded them in memory: MODULE NAME BUILT TO LOAD AT ACTUALLY LOADED STARTING AT ADDRESS ----------- ---------------- ----------------------------------- DBLE "-1" (99) 00 PAUSE "-1" (99) 08 MAIN 00 17 The difference is the amount by which the addresses in the module need to be relocated: Relocation Offsets for each module: DBLE: built to start at "-1", actually loaded at 00 - relocated by 00 - (-1) = 01 PAUSE: built to start at "-1", actually loaded at 08 - relocated by 08 - (-1) = 09 MAIN: built to start at "00", actually loaded at 17 - relocated by 17 - 00 = 17 Now that we have the relocation offset for each of the three modules, we can relocate all the addresses that need relocation for each module. We have two places where this relocation work must be done: (1) the three tables associated with each module and (2) the code for the module that we just loaded into memory. We'll relocate the addresses in the tables first, since we'll need the tables to help us find the relocatable addresses in the code in memory. Since all the tables for each module contain addresses inside the modules, all the addresses inside all the tables must be relocated. Here are the nine tables in relocated form: DBLE: (Relocated from "-1" to "00", a difference of 01) External Reference Table: (after relocation) PAUSE (05 + 01 =) 06 Public Symbol Table: (after relocation) DBLE (00 + 01 =) 01 Relocatable Instruction Table: (after relocation) ([00, 02, 03, 06] + 01 =) 01, 03, 04, 07 PAUSE: (Relocated from "-1" to "08", a difference of 09) External Reference Table: (after relocation) no external references Public Symbol Table: (after relocation) PAUSE (00 + 09 =) 09 Relocatable Instruction Table: (after relocation) ([00, 01, 02, 04, 05] + 09 =) 09, 10, 11, 13, 14 MAIN: (Relocated from "00" to "17", a difference of 17) External Reference Table: (after relocation) PAUSE (02 + 17 =) 19 DBLE (04 + 17 =) 21 DBLE (05 + 17 =) 22 Public Symbol Table: (after relocation) no public symbols given (an omission) (if there were a "MAIN" public symbol, it would be at 00+17=17) Relocatable Instruction Table: (after relocation) ([00, 03, 06, 07, 08, 09, 11] + 17 =) 17, 20, 23, 24, 25, 26, 28 The above nine tables are now completely relocated and correctly refer to the three modules where they now sit in memory. Again, be sure about the difference between the name of a module and the name of a label inside that module: The Public Symbol "DBLE" is now located at mailbox 01; the whole *routine* that makes up DBLE was loaded starting at mailbox 00. Module DBLE is loaded at mailbox 00, with public label "DBLE" at mailbox 01. The Public Symbol "PAUSE" is now located at mailbox 09, the whole *routine* that makes up PAUSE was loaded starting at mailbox 08. Module PAUSE is loaded at mailbox 08, with public label "PAUSE" at mailbox 09. Module MAIN loaded at mailbox 17, with no public label. (If there were such a label, "MAIN", it would be at mailbox 17, the start of the code.) Having relocated all the tables, we must now relocate the addresses in the *code* for each module that is in memory, using the Relocatable Instruction Table for each module to tell us which instructions in memory to relocate. Using those three Relocatable Instruction tables, we generate the following 16 changes to the object code in memory: LOC BEFORE AFTER REASON FOR CHANGE --- ------ ----- ------------------------------------------- 01: 902 903 ; DBLE: added 01 for relocation from -1 to zero 03: 101 102 ; same 04: 301 302 ; same 07: 999 900 ; same -------------------------- 09: 106 115 ; PAUSE: added 09 for relocation from -1 to 08 10: 407 416 ; same 11: 206 215 ; same 13: 900 909 ; same 14: 999 908 ; same -------------------------- 17: 113 130 ; MAIN: added 17 for relocation from 00 to 17 20: 113 130 ; same 23: 113 130 ; same 24: 314 331 ; same 25: 213 230 ; same 26: 415 432 ; same 28: 900 917 ; same Those are the 16 instructions that needed relocating, as given by the three Relocatable Instruction tables. Next: Resolving external references. -------------------- STEP THREE - LINKING -------------------- Only MAIN and DBLE have an External References table - module PAUSE does not refer to any labels outside the module. Let's resolve the external references for DBLE first: The (relocated) table of External References for DBLE shows "PAUSE 06". The linker must fix location 06 in memory with the real address of the PAUSE Public Symbol at link time. The linker looks in all the Public Symbol tables for some symbol named "PAUSE". It finds a Public Symbol named PAUSE in the module PAUSE, with location "09". When the linker runs, it will use the relocated External Reference information "PAUSE 06" to go to memory location 06 and it will change the "000" at that location to "009" ("CALL PAUSE"), because it now knows that the Public Symbol "PAUSE" is located at memory address "09". (Note that the linker is resolving a reference to the *label* PAUSE at location "09", not the location of the whole PAUSE module at location "08".) This is the change the linker makes to the machine codes loaded in memory: LOC BEFORE AFTER REASON FOR CHANGE --- ------ ----- ---------------------------------- 06: 000 009 ; address of "PAUSE" linked in (added) Let's resolve the external references for MAIN next: The (relocated) table of External References for MAIN has three entries: PAUSE 19 DBLE 21 DBLE 22 The linker must fix location 19 in memory with the real address of the PAUSE Public Symbol at link time. It must fix locations 21 and 22 by adding in the address of the DBLE Public Symbol. The linker looks in all the Public Symbol tables for some symbol named "PAUSE". It finds a Public Symbol named PAUSE in the module PAUSE, with location "09". The linker looks in all the Public Symbol tables for some symbol named "DBLE". It finds a Public Symbol named DBLE in the module DBLE, with location "01". When the linker runs, it will use the relocated External Reference information "PAUSE 19" to go to memory location 19 and it will change the "000" at that location to "009" ("CALL PAUSE"), because it now knows that the label "PAUSE" is located at memory address "09". The linker will also go to memory locations 21 and 22 and add the address where it found the Public Symbol DBLE (01). Using that new, relocated External References table for MAIN, we make these next three changes to the machine codes loaded in memory: LOC BEFORE AFTER REASON FOR CHANGE --- ------ ----- ---------------------------------- 19: 000 009 ; address of "PAUSE" (09) linked in (added) 21: 201 202 ; address of "DBLE" (01) linked in (added) 22: 000 001 ; address of "DBLE" (01) linked in (added) Note how the addresses of PAUSE and DBLE are simply *added* to the address fields of the instructions. In most cases, the existing address field is zero (a direct reference to the external symbol). We have made four more changes to the in-memory codes to resolve the four external references. That's it for resolving External References. We're done. We have relocated nine tables and 16 instructions in memory, and we have made 4 more changes to instructions in memory to resolve external symbols. The final result in memory, all three modules fully Linked (4 changes) and Relocated (16 changes) looks like this (20 changed instructions total): R = Relocated Instruction L = External Symbol resolved (linked) LOC BEFORE AFTER REASON FOR CHANGE --- ------ ----- ------------------------------------------- 00: 000 000 01: 902 R 903 ; DBLE: added 01 for relocation from -1 to 00 02: 000 000 03: 101 R 102 ; DBLE: added 01 for relocation from -1 to 00 04: 301 R 302 ; DBLE: added 01 for relocation from -1 to 00 05: 600 600 06: 000 L 009 ; address of "PAUSE" (09) linked in (added) 07: 999 R 900 ; DBLE: added 01 for relocation from -1 to 00 ------------------ 08: 000 000 09: 106 R 115 ; PAUSE: added 09 for relocation from -1 to 08 10: 407 R 416 ; PAUSE: added 09 for relocation from -1 to 08 11: 206 R 215 ; PAUSE: added 09 for relocation from -1 to 08 12: 801 801 13: 900 R 909 ; PAUSE: added 09 for relocation from -1 to 08 14: 999 R 908 ; PAUSE: added 09 for relocation from -1 to 08 15: 000 000 16: 001 001 ------------------ 17: 113 R 130 ; MAIN: added 17 for relocation from 00 to 17 18: 600 600 19: 000 L 009 ; address of "PAUSE" (09) linked in (added) 20: 113 R 130 ; MAIN: added 17 for relocation from 00 to 17 21: 201 L 202 ; address of "DBLE" (01) linked in (added) 22: 000 L 001 ; address of "DBLE" (01) linked in (added) 23: 113 R 130 ; MAIN: added 17 for relocation from 00 to 17 24: 314 R 331 ; MAIN: added 17 for relocation from 00 to 17 25: 213 R 230 ; MAIN: added 17 for relocation from 00 to 17 26: 415 R 432 ; MAIN: added 17 for relocation from 00 to 17 27: 802 802 28: 900 R 917 ; MAIN: added 17 for relocation from 00 to 17 29: 700 700 30: 000 000 31: 001 001 32: 010 010 That's all. Assuming we start running this code at the beginning of MAIN (loction 17), the above code will now run as a coherhent unit, with all the address references correct.