Project 1-2: MIPS Linker

Computer Architecture I ShanghaiTech University
Project 1.1 Project 1.2 Project 2.1

The Linker

In part 1 of this project, we wrote an assembler in C. Now, we will continue where we left off by implementing a linker in MIPS. The linker processes object files (which in our project are .out files) and generates an executable file. In the rest of this document, "input" will be used interchangeably with "object file", and "output" with "executable file".

The linker has two main tasks, combining code and relocating symbols. Code from each input file's .text segment is merged together to create an executable. This also determines the absolute address of each symbol (recall that the assembler outputs a symbol table containing the relative address of each symbol). Since the absolute address is known, instructions that rely on absolute addressing can have the addresses filled in.

The skeleton files contain many lines of code, and it can be easy to get lost in the details. Here is a overview of how the linker functions:

For the sake of simplicity, we will skip many of the error checking steps that a linker would normally perform. The checks that you do need to perform are stated in the instructions.

Implementation Steps

We will be developing with MARS. MARS runs very slowly across SSH connections, so if you have not done so, you should download MARS onto your computer by clicking here. MARS requires Java J2SE 1.5 or later installed onto your computer. Also, since MARS is a Java application, its behavior should be the same regardless of the operating system you are using.

When assembling a program with MARS, make sure that the program is in the current tab. When you open multiple tabs, it can be easy to forget which one you are on.

Also, make sure you go to "Settings" and turn on the "Initialize Program Counter to global 'main' if defined" option:

Step 0: Obtaining the Files

1. Download the files here.

Step 1: String Utilities

In linker-src/string.s, implement strlen(), strncpy(), and copy_of_str(). copy_of_str() should allocate memory dynamically using Syscall 9, and it is recommended that you use strlen() and strncpy() in its implementation. Do not modify the other functions in the file, but you should take a look at their descriptions, since they may come in handy later. Also, if you are stuck on a function, looking at the implementation of a related function may help you.

You can find test cases in linker-test/test_string.s. Note that if you have not implemented a function, the tester may crash. You can comment out test cases for functions that you have not yet implemented.

Step 2: Symbol List

In linker-src/symbol_list.s, complete the implmentation of SymbolList, which serves the same purpose that SymbolTable did in project 1-1. SymbolList uses a linked list to keep track of (symbol addr, symbol name) pairs. An empty SymbolList is simply a pointer to NULL. When an (addr, name) pair is added to a SymbolList, a new list node is created and added to the front of the list. If the SymbolList list node struct were to be declared in C, it would be:

typedef struct symbollist { 
    int addr;
    char* name;
    struct symbollist* next; 
} SymbolList;

If you are having trouble with addr_for_symbol(), it may be helpful to look at symbol_for_addr(), which is already defined for you. Test cases for SymbolList can be found in linker-test/test_symbol_list.s. You do NOT need to free the list, as MARS has no free syscall.

Step 3: Linker Utilities

Before you continue, it may be a good idea to look at the slides CALL lecture as a quick refresher.

This step requires you to make changes in two files, linker-src/parsetools.s and linker-src/linker_utils.s. In the first file, you will be implementing hex_to_str(), which writes a 32-bit number in hexadecimal format. Tests for this function can be found in linker-test/test_parsetools.s.

For the second part, you will be implementing inst_needs_relocation() and relocate_inst(). inst_needs_relocation() will be called on each instruction, and it should return 1 for any instruction that needs relocating. relocate_inst() performs the actual relocation, using the symbol table and relocation table provided. You will need to perform error-checking for relocate_inst() as described in the comments.

Step 4: Completing the Linker

You will need to complete the implementation of write_machine_code() in linker-src/linker.s. This function will copy the .text section of an object file (the input) to the executable (the output) while performing any relocations as neccessary. The first part of the function searches for the .text segment in the object file. Once that is found, the function will write to the executable one instruction at a time. Instructions are first converted from characters to a number, relocations are performed if neccessary, and the instruction is written in hexadecimal to the executable.

Instead of writing the function from scratch, we have provided 7 blanks for you to fill in (each blank consists of one or more instructions). Each blank is denoted by YOUR_INSTRUCTIONS_HERE and accompanied by a description. After you have filled in all the blanks, your linker should be ready to run!

Please do not give away what instructions should go inside each blank.

Coding Restrictions

Do not change anything in or below the lines stating "DO NOT MODIFY ANYTHING BELOW THIS POINT" - autolab will refuse your submissions in this case!

In your code you are NOT allowed to use the following registers: $t0, $t1, $t6, $t7, $t8, $t9, $s0, $s1, $s2, $s3, $s4, $s5 . So basically you have $t2 to $t5 as well as $s6 and $s7 to work with. Also, you are not allowed to use any $x where x is just a number.

Also you are required to write a meaningful comment in English in at least every second line you add!

Test Cases

Test cases for each of the functions you wrote in steps 1-3 are in the linker-tests directory. The test case for each file is preceeded by the prefix test_ (for example, test cases for linker-src/string.s are located in linker-tests/test_string.s). To run the tests, open the appropriate test file in MARS and press Run.

Each test file contains test cases for every function you need to implement in the corresponding source file (so linker-tests/test_string.s contains test cases for strlen(), strncpy(), and copy_of_str()). The test cases are run from the main() function of the test file. If you have not implemented all the functions in a given source file, you may want to comment out tests for functions you haven't implemented. Fro example, if you've implmented strlen() and strncpy() but not copy_of_str(), you should comment out the line jal test_copy_of_str before running the test.

Running the Linker

The linker accepts an arbitrary number of input (object) file names followed by an output file name. The input files will be combined, and the result be placed in the output file. If the output file already exists, it will be overwritten. The files will be combined in the order that they were given (eg. input file 1 goes first, then input file 2, etc).

When running in MARS, after you assemble your code you can enter arguments into the "Program Arguments" text field, located at the top of the text segment. MARS interprets file paths as relative to the executable itself. You may need to place a copy of MARS in your proj1 directory and run that.

If you want to run from the command line, we have also give you an executable called linker You may first need to turn on the execute permission:

chmod u+x linker

Afterwards, you can pass in the input and output file names by supplying them as arguments. Note that the linker requires at least one input and one output name, so you need to specify two arguments at minimum.

./linker <input 1 name> <input 2 name> ... <input N name> <output name>

We have give some sample input-output pairs, which may be useful as a reference during step 4. The inputs are located in link-in and outputs are located in link-out. linker1.out (recall that we use .out to denote object files, which are inputs to the linker) and linker2.out are standalone test cases, but linker3A.out and linker3B.out should be linked together:

./linker link-in/linker1.out link-out/output1
./linker link-in/linker2.out link-out/output2
./linker link-in/linker3A.out link-in/linker3B.out link-out/output3

You can compare your output to the reference outputs in the link-out/ref directory. diff may be useful:

diff link-out/output1 link-out/ref/output1_ref
diff link-out/output2 link-out/ref/output2_ref
diff link-out/output3 link-out/ref/output3_ref

Debugging Tips

• Make sure you are assembling from the correct tab. MARS always assembles from the currently active tab.
• Note that there are two tabs when running MARS at the bottom, "Mars Messages" and "Run I/O". The first shows error messages while the second displays your program's output. If your program runs succesfully, the Run I/O tab will be active, but if your program crashes, the Mars Messages tab will be shown with an error message. Parts of your program may still have been run successfully though, and you can click on the Run I/O tab. This can help you figure out what part of the program causes the crash. Note that program output from previous runs are also displayed, so it may be helpful to press the "Clear" button after assembling and before running.
• If you are getting "invalid program counter value" errors, check to make sure that 1) you have checked "initialize program counter to globl main" and 2) you are following function calling conventions. Are you calling functions with jal? Are you saving $ra.
• If you are getting "address out of range" errors, you are passing an invalid address to a load/store command. The best way to debug these errors is to set breakpoints around the line which causes the error, and then step through your code while observing how values in your register change.
• If MARS seems to freeze, your program may be in an infinite loop. Try pausing MARS and stepping through the program. Are you forgetting a termination check? Or maybe you are forgetting to increment a variable?
• After MARS assembles your code, it can be hard if you are trying to find a specific line. However, since MARS keeps comments that are on the same line as an instruction, you can tag a line of interest with an easy-to-find comment.
• Similarly, it may be a good idea to label the first and last lines of each function with comments like "#Begin func_name()" and "#End func_name()". That way, it'll be easier to figure out where you are.
• It can also be helpful to insert print syscalls in the middle of your function. See the Help menu for various types of prints. Be aware that you may clobber the $a0 and $v0 registers!

Submission

Autolab will open later.