Bonus Question 2

Deadline	Tuesday, December 5, 11:59pm Extensions are not given for Bonus Questions
Name on Marmoset	BQ2
To Submit	`linker.cc` or `linker.rkt`
Bonus Points	Up to +0.25% on your final grade

Writing a Linker

This question is about writing a linker for MERL files. You are to implement the algorithm for linking two MERL files described in the lectures and course notes.

The behaviour of your program should match that of the course tool cs241.linker. This tool takes a sequence of command line arguments, each of which is the name of a MERL file, links all the files together, then outputs the MERL file (just as plain binary data, not in any special human-readable form).

cs241.linker file1.merl file2.merl ... fileN.merl

You were only taught the linking algorithm for two files, not an arbitrary number of files. However, linking an arbitrary number of files can be done by just linking the first two, linking the result of that with the next one, and so on.

We provide starter code that reads the command line arguments and calls the two-file linking routine repeatedly to link all the files. So, you just need to implement the two-file linking routine.

MERL Specification

The MERL Specification may be useful as a reference for this question.

Starter Code

We provide the following starter code:

C++ Starter Code: linker.cc
Racket Starter Code: linker.rkt

The starter code requires the following library for working with MERL files, which should be placed in the same directory as the starter code.

C++ MERL Library: merl-cpp.zip (contains two files, merl.h and merl.cc)
Racket MERL Library: merl.rkt

The starter code provides a main program that reads the MERL files whose names are provided on the command line, and links all the files by calling a helper function that links two files at a time. You need to implement this two-file linking function.

By default, the provided two-file linking function just outputs a hardcoded example MERL file to demonstrate the use of the starter code. You should replace this with an implementation of the actual linking algorithm.

You can compile the C++ starter code with this command (requires merl.h and merl.cc in the same directory as linker.cc):

g++ linker.cc merl.cc -o linker

The Racket starter code can be run directly as follows, as long as merl.rkt is in the same directory as linker.rkt:

racket linker.rkt

Testing

The assembler cs241.linkasm can be used to produce MERL files from MIPS assembly source code. This assembler supports the .import and .export directives that are required to produce linkable MERL files.

The cs241.linker tool serves as a reference implementation of the linker.

Example

Create a file called m1.asm with the following contents:

.import kitten
lis $3
.word kitten
jr $3

Create a file called m2.asm with the following contents:

.export kitten
kitten: add $3, $2, $1
jr $31

Run both files through cs241.linkasm to create MERL files:

cs241.linkasm < m1.asm > m1.merl
cs241.linkasm < m2.asm > m2.merl

Now you can pass both files to your linker:

./linker m1.merl m2.merl > output.merl

Or if using Racket:

racket linker.rkt m1.merl m2.merl > output.merl

Your linker's output should be a MERL file, which is a raw sequence of 32-bit binary words that will not be easily readable if sent to the terminal. You can examine the contents of the MERL file with cs241.binview or xxd. Below we are using xxd with the -c4 option (4 bytes, or one word, per line).

xxd -c4 output.merl
00000000: 1000 0002  ....        beq $0, $0, 2    (start of header)
00000004: 0000 004c  ...L        endModule value  (address of end of file)
00000008: 0000 0020  ...         endCode value    (address of end of code segment)
0000000c: 0000 1814  ....        lis $3           (start of code segment)
00000010: 0000 0018  ....        .word kitten
00000014: 0060 0008  .`..        jr $3
00000018: 0041 1820  .A.         kitten: add $3, $2, $1
0000001c: 03e0 0008  ....        jr $31
00000020: 0000 0001  ....        REL format code  (start of footer)
00000024: 0000 0010  ....        Value to relocate is at address 0x10
00000028: 0000 0005  ....        ESD (export) format code
0000002c: 0000 0018  ....        Exported label is at address 0x18
00000030: 0000 0006  ....        Length of label name
00000034: 0000 006b  ...k        ASCII code for k       
00000038: 0000 0069  ...i        ASCII code for i
0000003c: 0000 0074  ...t        ASCII code for t
00000040: 0000 0074  ...t        ASCII code for t
00000044: 0000 0065  ...e        ASCII code for e
00000048: 0000 006e  ...n        ASCII code for n

Above, there are annotations in italics which are not part of the xxd output, and were added to explain the structure of the MERL file. You can see that the linked file contains a single header, followed by the two code segments combined. The footer contains a REL entry, because as a result of the linking algorithm, the ESR (import) entry was resolved and changed into a REL. The footer also contains an ESD (export) entry carred over from m2.asm.

To view the reference linker's output for comparison, run it as follows:

cs241.linker m1.merl m2.merl > reference-output.merl
xxd -c4 reference-output.merl

Even if your linker is correct, the output of the reference linker will not necessarily be identical to your linker, because the order of the entries in the MERL footer can vary. See below for a discussion of how to deal with this and a Bash script to help with testing.

One issue with using this reference implementation is there is more than one possible correct output for a MERL linker. The entries in the MERL footer (relocation and external symbol table) do not have to appear in any specific order, so even if your output is correct, it might not match the output of the reference implementation because the order might be different.

A solution to this issue is to use the cs241.merl tool. The intended purpose of this tool is to remove the metadata from a MERL file (header and footer) and output the MIPS code segment (optionally with relocation). However, as a side effect, the tool also prints a text representation of the MERL header information and the entries in the MERL footer, with one line per entry, on standard error. This lets us compare with the reference implementation as follows.

Run your linker and store the output in my-output.merl.
Run the reference linker and store the output in reference-output.merl.
Run my-output.merl through cs241.merl, storing standard output in my-code.mips and standard error in my-metadata-unsorted.txt.
Run reference-output.merl through cs241.merl, storing standard output in expected-code.mips and standard error in reference-metadata.txt.
Use the sort command to sort my-metadata-unsorted.txt and store the result in my-metadata.txt. The purpose of sorting is to make sure differences in the order of entries are ignored.
Use the sort command to sort reference-metadata.txt and store the result in expected-metadata.txt.
Use the diff command to compare my-code.mips and expected-code.mips.
Use the diff command to compare my-metadata.txt and expected-metadata.txt.

It's kind of horrible but it works. Below is a Bash script that takes a sequence of MERL files as command line arguments and performs all the above steps.

If you are using Racket, replace ./linker on the second line with racket linker.rkt.

#!/bin/bash
./linker     "$@" > my-output.merl
cs241.linker "$@" > reference-output.merl

cs241.merl 0 < my-output.merl        > my-code.mips       2> my-metadata-unsorted.txt
cs241.merl 0 < reference-output.merl > expected-code.mips 2> reference-metadata.txt

sort < my-metadata-unsorted.txt > my-metadata.txt
sort < reference-metadata.txt   > expected-metadata.txt

echo "Comparing the MIPS code segments with diff"
if diff my-code.mips expected-code.mips > /dev/null; then
  echo "No difference!"
fi
echo "Comparing the MERL metadata with diff"
if diff my-metadata.txt expected-metadata.txt > /dev/null; then
  echo "No difference!"
fi

Save the above file as linker-test.bash and run chmod u+x linker-test.bash to make the script executable. Then you can run it as follows to test your linker:

./linker-test.bash file1.merl file2.merl ... fileN.merl