=========================================================================== Assignment #12 - LMC Linking, Relocation, and Loading =========================================================================== - Ian! D. Allen - idallen@idallen.ca - www.idallen.com Available online: Thursday April 14, 2011 Upload due date: Upload answer file before 23:59 (midnight) on Thursday April 21, 2011 Answers will be posted shortly after the due date/time. Late assignments may or may not be marked. Submission method: Create a plain text file using the exact name "assignment12.txt" Upload the file via the Assignment12 "Upload File" facility in Blackboard. Use "Attach File" and "Submit" to upload your plain text file. No wordprocessor documents. Do not send email. Use only "Attach File". Use the file name given above. Upload only one single file of plain text, not HTML, not MSWord. No fonts, no word-processing. Plain text only. Did I mention that the format is plain text (VIM/Nano/Pico/Gedit or Notepad)? NO WORD PROCESSOR DOCUMENTS ACCEPTED. No marks are awarded for submitting under the wrong assignment number. Not all assignments will be marked. See the Week 1 Notes for details. Answers will be posted after the due date/time. Questions similar to ones on these assignments will appear on your tests and exams. ============================================================================== DO THIS: Edit this file and answer the following questions underneath each question. Upload the file containing the questions and answers before the due date. Some of the answers below will require reading the links published in the weekly course notes. ============================================================================== 0. What is the date for your Final Exam? DAT2343 - Monday Apr 25 10h30 (10:30am to 1pm) - P214 - Final exam You must read and understand 000_test_instructions.html before the exam. *** Z+C+S+O Flags Section *** 1. Perform the indicated 8-bit hexadecimal arithmetic. Show the 8-bit result value and indicate by check marks the correct "ON" states of the Zero, Carry, Sign, and Overflow flags after the arithmetic. Indicate by check marks (type an X in the space) if the 8-bit result is correct for signed two's complement arithmetic (OK-SIGN) and/or correct for unsigned arithmetic (OK-UNSIGN). Leave flags that are OFF blank: (Reference: Assignment 8) 90 + B0 = _______ Z___ C___ S___ O___ OK-SIGN___ OK-UNSIGN___ 80 + 70 = _______ Z___ C___ S___ O___ OK-SIGN___ OK-UNSIGN___ 70 + 50 = _______ Z___ C___ S___ O___ OK-SIGN___ OK-UNSIGN___ FF + FF = _______ Z___ C___ S___ O___ OK-SIGN___ OK-UNSIGN___ 80 + 80 = _______ Z___ C___ S___ O___ OK-SIGN___ OK-UNSIGN___ 90 + B0 = 40_____ Z___ C_X_ S___ O_X_ OK-SIGN___ OK-UNSIGN___ 80 + 70 = F0_____ Z___ C___ S_X_ O___ OK-SIGN_X_ OK-UNSIGN_X_ 70 + 50 = C0_____ Z___ C___ S_X_ O_X_ OK-SIGN___ OK-UNSIGN_X_ FF + FF = FE_____ Z___ C_X_ S_X_ O___ OK-SIGN_X_ OK-UNSIGN___ 80 + 80 = 00_____ Z_X_ C_X_ S___ O_X_ OK-SIGN___ OK-UNSIGN___ *** Linking and Object Files Section *** Reference: 370_LMC_link.html - Linking and Generation of Executable Code from Source Program Files Reference: 373_LMC_object_file_format.html - Linking and External "Object" Files and Libraries 2. What is the difference between a Public Symbol and a Global Symbol? (trick question) No difference. A Global Label is available to the linker to resolve External References, just as a Public Symbol is. 3. What is the purpose of the LMC mnemonic pseudo-instruction PUB? PUB: This symbol and its memory location should be put into the Public Label Table when the module is assembled into an object file. This symbol and its address are available to other modules. 4. What is the purpose of the LMC mnemonic pseudo-instruction EXT? EXT: This symbol refers to a memory address in some other module. The symbol and its location should be put into the External References Table in the object file. The linker must satisfy this reference with some Public Label address when the program is linked. 5. Identify the four components of an "Object" file and describe the purpose of each component in your own words. 0. The machine code instructions (the program itself). 1. a Public label table containing a list of all Public Labels defined within the module, and their corresponding mailbox (memory) addresses. "Public" labels are labels that should be made available to other modules. All other labels are private, local labels that are not visible to other modules. 2. an External Reference table containing a list of all memory addresses that make references to "public" labels defined in other modules, plus the name of the actual label being referenced. 3. a Relocation Address table containing a list of all the addresses containing instructions that include address references to addresses within the module (based on the false assumption that the module would be loaded starting at address 00). All relocatable memory address references will need to be adjusted to reflect the true memory address values once the true starting address of the module has been established by the linker. Read these explanations. Put them away. Now, write your own words. 6. In your own words, explain how a "linker" program uses the relocatable address list, the public (or "global") label definition table, and the external reference table (all from within a collection of object files) to generate an "executable" version of a program. The linker reads the object files and places all the machine code for all the modules into memory, one after the other, noting the start location of each module in memory. This start location is the "relocation offset" that has to be used to relocate addresses within the module. The linker uses the above "relocation offsets" to "relocate" the addresses in all the tables that accompany all the modules loaded - three tables for each module. Now, all three tables correctly refer to address locations within the relocated modules in memory. The linker matches up all External References with the Public Label tables, plugging in the actual (relocated) addresses of the external modules into the machine code at the location specified by the External Reference table. Any External Reference that can't find a corresponding Public Label causes a link-time error. The linker uses the Relocation Address tables in all the modules to relocate all the relocatable addresses in the code within each module. Now, the code refers to the correct memory locations. The resulting "linked" code is saved as an executable binary program. Read these explanations. Put them away. Now, write your own words. In the course notes (370_LMC_link.html) you will find an LMC main program and two subroutines "Pause" and "Dble". These questions are based on those three modules, their machine code, and their object file tables. 7. Provide the contents of each of the three relocated 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.) The tables should reflect the relocated locations of the modules loaded in the given order: Main, Pause, Dble. Hint: All this information is already worked out in the web page. The whole link process involves three steps, summarized at the bottom of the above web page: 1. copying module machine code into memory 2. relocating the code and tables for the new memory locations 3. resolving external references using public symbols Looking at each of the three modules, we can build the nine tables using the existing tables and adding the load address offsets. MAIN loads at 00, PAUSE loads at 16, and DBLE loads at 25: MAIN (loads starting at 00, length: 16): Public Symbol Table: MAIN 00 External Reference Table: PAUSE 02 ARG 04 DBLE 05 Relocatable Instruction Table: 00, 03, 06, 07, 08, 09, 11 No changes needed to any of the tables, since MAIN loads at zero. PAUSE (loads starting at 16, length: 9): Public Symbol Table: PAUSE (01 + 16 =) 17 External Reference Table: no external references Relocatable Instruction Table: ([01, 02, 03, 05, 06] + 16 =) 17, 18, 19, 21, 22 Every location in each of the three tables has had 16 added to it. DBLE (loads starting at 25, length: 7): Public Symbol Table: ARG (00 + 25 =) 25 DBLE (02 + 25 =) 27 External Reference Table: PAUSE (05 + 25 =) 30 Relocatable Instruction Table: ([02, 03, 06] + 25 =) 27, 28, 31 Every location in each of the three tables has had 25 added to it. 8. Delete the first two instructions from the MAIN program (LDA COUNT, OUT) and move the MAIN and Repeat labels to the CALL PAUSE instruction that is now the first instruction of the new, shorter MAIN program. Re-assemble the new, shorter MAIN program to produce a new object file. Give the new, shorter MAIN Object File here (14 instructions of machine code and three tables); Intermediate Step: hand-assemble the program into machine code : MAIN 00 000 : Repeat CALL Pause 01 111 : LDA Count 02 200 : STO Arg ; store subroutine argument 03 000 : CALL Dble 04 111 : LDA Count ; count += 1 05 312 : ADD One 06 211 : STO Count 07 413 : SUB Max ; while ( count < max ) 08 802 : SKP 09 900 : JMP Repeat 10 700 : HLT 11 000 : Count DAT 000 ; local symbol (not Public) 12 001 : One DAT 001 ; local symbol (not Public) 13 010 : Max DAT 010 ; local symbol (not Public) MAIN Machine Code 000 111 200 000 111 312 211 413 802 900 700 000 001 010 Public Symbol Table: MAIN 00 External Reference Table: PAUSE 00 ARG 02 DBLE 03 Relocatable Instruction Table: 01, 04, 05, 06, 07, 09 9. Do a link and load of the New MAIN (previous question), Pause, and Dble. Load the three modules into memory in the order: New MAIN, Pause, Dble. New MAIN loads starting at zero, followed by Pause, followed by Dble. Generate the nine new relocated tables that would be associated with the object code for each of the three modules New 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.) The tables should reflect the relocated locations of the modules loaded in the given order starting at 00: New MAIN, Pause, Dble. The whole link process involves three steps, summarized at the bottom of the above web page: 1. copying module code into memory 2. relocating the code and tables for the new memory locations 3. resolving external references using public symbols Looking at each of the three modules, we can build the nine tables using the existing tables and adding the load address offsets. MAIN loads at 00, PAUSE loads at 14, and DBLE loads at 23: MAIN (loads starting at 00, length: 14): Public Symbol Table: MAIN 00 External Reference Table: PAUSE 00 ARG 02 DBLE 03 Relocatable Instruction Table: 01, 04, 05, 06, 07, 09 No changes needed to any of the tables, since MAIN loads at zero. PAUSE (loads starting at 14, length: 9): Public Symbol Table: PAUSE (01 + 14 =) 15 External Reference Table: no external references Relocatable Instruction Table: ([01, 02, 03, 05, 06] + 14 =) 15, 16, 17, 19, 20 Every location in each of the three tables has had 14 added to it. DBLE (loads starting at 23, length: 7): Public Symbol Table: ARG (00 + 23 =) 23 DBLE (02 + 23 =) 25 External Reference Table: PAUSE (05 + 23 =) 28 Relocatable Instruction Table: ([02, 03, 06] + 23 =) 25, 26, 29 Every location in each of the three tables has had 23 added to it. 10. Using the tables from the previous question, generate the relocated and linked machine code for the Dble module loaded at its new address. Show the original object code of Dble (before any modifications), followed by the fully modified (relocated and linked) code for the Dble module in its new location in memory. Beside each location that has been modified, give the reason why the modification was made. Answer this question using a multi-column table: Column 1: original address Column 2: original object code before any modifications Column 3: new address in memory Column 4: new object code (fully relocated and linked) Column 5: reason for object code change (if any change) Example five-column table format for your answer: Original New Reason for change -------- ------- ------------------------------------------- 00: 117 20: 137 local memory reference relocated by +20 01: 000 21: 023 "CALL foo" external subroutine located at 23 02: 700 22: 700 no change ... This question usually appears on the Final Exam. We look at the three tables for DBLE (above) to know where to modify the code for DBLE. The tables tell us all we need to know. The three tables for DBLE (above) say DBLE has one External Reference to PAUSE at 28. We look up the symbol PAUSE in all the Public Symbol Tables and find it has value 15. We add 15 to location 28. The three tables for DBLE (above) say DBLE has three Relocatable Instructions at 25, 26, and 29. We add the load module offset 23 (DBLE loads at 23) to each of these three locations. Note that if we have the three tables (as we would find in a pre-compiled object module) we don't need to refer to the source code. We summarize this way (as you would do on an exam): Original New Reason for change -------- ------- ------------------------------------------- 00: 000 23: 000 no change 01: 000 24: 000 no change 02: 100 25: 123 local memory reference relocated by +23 03: 300 26: 323 local memory reference relocated by +23 04: 600 27: 600 no change 05: 000 28: 015 "CALL Pause" external subroutine located at 15 06: 901 29: 924 local memory reference relocated by +23 -- | Ian! D. Allen - idallen@idallen.ca - Ottawa, Ontario, Canada | Home Page: http://idallen.com/ Contact Improv: http://contactimprov.ca/ | College professor (Free/Libre GNU+Linux) at: http://teaching.idallen.com/ | Defend digital freedom: http://eff.org/ and have fun: http://fools.ca/