Supplement to the hw5 main assignment.

Implementing Address Translation

Description

Address translation allows a program to be linked to run at a specific address (zero), but actually be loaded in memory anywhere. It works by adding some offset to all addresses generated by the program, meaning both the PC and addresses generated by load and store instructions.

For instance, suppose the program contains this code:

0x00000100    loop:   beq  $t0, $0, skip
0x00000104            add  $t1, $t1, $t0
0x00000108            j    loop  # this instruction encodes the address 0x100

and that the $gp contains the value 0x00000400 (meaning that there are 0x100 instuctions in the program, as they precede the static data area in memory). The hex values to the left are the addresses of the instructions, assuming the program is loaded in memory at address 0. So, if the first instruction is being executed, the PC would have value 0x100. When we get to the last, it will reset the PC to 0x100, forming a loop. That's what happens, without address translation.

Now suppose the program is loaded in memory starting at address 0x1000. Without address translation there's a problem: the jump instruction will still go to location 0x100, which is wrong. Address translation fixes this by distinguishing between virtual addresses and physical addresses. The addresses used by the program, including those in the PC, are virtual -- they're a consistent way for the program to name memory locations, but they are not necessarily the actual memory locations in use. Address translation converts the virtual addresses to physical addresses, ones that can be given to memory. In Cebollita, the translation is simple: add the Memory Base register to each virtual address to form the physical address. So, in this example, while this program is running the Memory Base register would be set to 0x1000. The jump would give a virtual address of 0x100, which would be translated to physical address 0x1100, which is right.

Down the path a bit, the operating system (including the loader) will use the address translation capability to make it easy to load programs - read the program from disk into some free memory, at any address. Now set the Memory Base register to that address, and let the program run.

In preparation for that, a couple more things are required. First, there will be many programs in memory at a time (including the OS itself). We don't want a bug in one program to wipe out the memory contents of another. So, to protect against this, we keep a Memory Length register as well as the memory base. The length register contains the number of bytes that were allocated to the program that is running. Each time a virtual address is issued to memory by that program (i.e., the PC on instruction fetch and any load or store effective address), it is compared against the length register. To be legal, it must be less than the length register (because otherwise it refers to memory belonging to another program.) This means that on every use of a virtual address your SMOK machine must perform this comparison. If it succeeds, everything is fine and just execute the instruction. If it fails, for now just halt the machine.

Building Applications

The usual rules apply. Additionally, to test that address translation is working, you need to:
1. compile/assemble/link an application as though it were going to be loaded at address 0
2. then actually load it at some other address (say, 0x100). Step 1 is easy -- Cebollita always links for address 0. Unfortunately, step 2 isn't as easy -- SMOK will load a Cebollita .exe file only at location 0. (The same is true of Cebollita itself, by the way.)

To get around this, we'll use a different kind of file to load into the SMOK memory component -- one not generated by Cebollita, but generated by hand. It should be enough to test execution of a few instructions, which is all you should need to convince yourself this part of the assignment is working.

The new file is a .smokmem file. You create it by hand, using some text editor. The format is described starting here.

As an example, this (untested) file contents should result in a the instructions indicated being loaded at address 0x100:

@0x100
0x3408000a    # ori  $t0, $0, 10
0x11080001    # beq  $t0, $t0, 1
0x08000002    # j    0x2
0x40000018    # halt