Introduction

The goal of this lab assignment is to extend the LC-3b simulator you wrote in Lab 2 to handle virtual memory, exceptions, and interrupts. You will augment the existing LC-3b microarchitecture with facilities for virtual to physical address translation and access protection checks. You will also provide microarchitectural support for detecting and handling timer interrupts, page fault exceptions, and protection exceptions.

In Lab 3, the address space of the LC-3b is divided into pages of 512 locations. The LC-3b virtual address space has 128 pages, while physical memory has 32 frames. Virtual pages 0-23, which are reserved for the operating system, will be mapped to frames 0-23 and will always be resident in physical memory. Frames 24-31 are available for swapping virtual pages of user programs. There are two modes of operation: supervisor and user. Virtual pages 0-23 cannot be accessed unless the LC-3b is in supervisor mode. Since user programs operate in user mode, they cannot access those pages. Thus the user virtual memory space is 104 pages (pages 24-127).

The input to this new simulator will be:

1. A file entitled ucode which holds the expanded microcontrol store.
2. A file holding an LC-3b program that gets loaded into physical frame 8 (x1000). This will be the page table.
3. A file holding an LC-3b user program that gets loaded into virtual page 24 (x3000).
4. A file holding data for the program in page 24. This data will be loaded into virtual page 96 (xC000).
5. A file holding the interrupt/exception vector table that gets loaded into virtual page 1 (x0200). You should form the contents of this table based on the vectors of each interrupt/exception and starting addresses of the service routine for each interrupt/exception.
6. A file holding an LC-3b program that gets loaded into virtual page 9 (x1200). This will be the interrupt service routine.
7. A file holding an LC-3b program that gets loaded into virtual page 10 (x1400). This will be the page fault exception handler.
8. A file holding an LC-3b program that gets loaded into virtual page 11 (x1600). This will be the protection exception handler.

New shell code A modified shell code has been written for you:

lc3bsim3.c (If you used the old shell code for Lab 2, download lc3bsim3_old.c)

This shell code has the capability of loading the page table into memory. You will need to copy and paste the code you wrote for Lab 2 into this new shell code.

Note that a new command line parameter has been added: the pagetable. To run the simulator, type:

lc3bsim3 <micro_code_file> <page table file> <program_file_1> <program_file_2> ...

The first parameter is the microcode file as before. The second parameter is the page table in LC-3b machine language. Note that since the page table is in physical memory, the first line of this file should have a physical address. For all the program files, (including the interrupt & exception handlers) which are in virtual memory, the first line should have a virtual address.

Specifications

This Lab consists of 3 parts, which we will describe in detail:
1. Adding support for virtual memory
2. Adding support for timer interrupts
3. Adding support for page fault and protection exceptions

1. Adding support for virtual memory

   The Page Table

   The page table should be placed at the beginning of frame 8 of physical memory. A page table entry (PTE) contains only 9 bits of information, but for convenience, it is represented in a full 16 bit word. Thus one page table entry occupies two memory locations. The format of each page table entry is as follows:

   PFN = PTE[13:9], the page frame number

   P = PTE[3], the protection bit
   P=0 -> page can only be accessed in supervisor mode
   P=1 -> user has full rights to the page

   V = PTE[2], the valid bit (V=1 for a valid page)

   M = PTE[1], the modified bit (M=1 if page has been written)

   R = PTE[0], the reference bit
   R=1 -> page has been referenced since last timer interrupt
   R=0 -> otherwise

   All other bits are set to zero.

   Page Table Access from the Datapath

   During the execution of instructions, your microcode will have to convert virtual addresses to physical addresses, as well as modify PTE's when necessary. To make address translation possible, we have added more structures to the datapath. We have added these registers: Page Table Base Register (PTBR) and Virtual Address Register (VA). The PTBR points to the first entry of the page table in physical memory. It's used to access a particular PTE during translation. To read from this register onto the bus, you should assert the GatePTBR signal. The VA register is a temporary register to hold the current address under translation. To read the VA register onto the bus and to write to the VA register from the bus, you should assert the GateVA and LD.VA control signals respectively.

   Translating Addresses

   Assume that at the beginning of each address translation phase the virtual address is located in the MAR, and if the operation is a write, a source register holds the data to be written. Address translation consists of the following steps:

   • Save the MAR into the temporary register VA
   
    
   • Load the MAR with the address of the PTE of the current table
   MAR[15:8] <- PTBR[15:8]
   MAR[7:0] <- LSHF(VA[15:9], 1)
    
   • Read the PTE of the current table into the MDR
   
    
   • Check for a protection exception
   
    
   • Check for a page fault
   
    
   • Set the R bit (reference bit) of the PTE
   
    
   • If the pending access is a write, set the M bit of the PTE
   
    
   • Write the PTE back to memory
   
    
   • Load the physical address into the MAR
   MAR[13:9] <- PFN
   MAR[8:0] <- VA[8:0]
    
   • If the operation is a write, load the MDR with the source register

   To add support for virtual memory, you first need to determine when you need to perform the address translation. Then, you will need to determine how to modify the state diagram so that it supports a "micro-subroutine" written in microcode to translate addresses. You will also need to determine how to return back to the correct state once address translation is complete. For this, you need to augment the microsequencer. You are free to add new control signals, gates, muxes, temporary registers as you wish as long as you fully document your changes.

2. Adding support for timer interrupts

   Timer Interrupt

   In this lab, a timer interrupt will occur at cycle 500. When the timer generates an interrupt, the microarchitecture may be in the middle of executing an instruction. You need to decide exactly when the interrupt is detected and add the necessary microarchitectural support to handle interrupts. When the interrupt is detected the following actions will be taken by the processor:

   1. The privilege mode (most significant bit of the PSR, program status register) is set to 0, which indicates supervisor-level privilege. Interrupt service routine will be executed with supervisor-level privilege.

   2. R6 is set to the supervisor stack pointer if that is not already the case.

   3. The old PSR (PSR before PSR[15] is set to 0) and PC are pushed onto the supervisor stack. Supervisor stack pointer is decremented on each push. Note that the supervisor stack is different from user stack. Interrupt service routines can access the supervisor stack using R6. You should initialize the supervisor stack pointer to address 0x3000. Note that R6 will refer to the user stack while your program is running. It will refer to the supervisor stack while the interrupt service routine is being executed. If the system is in user mode when an interrupt is detected, the microarchitecture should transparently switch R6 so that it points to the supervisor stack. You need to implement this "stack switching" in microcode. You will need to modify the datapath, add new states to the state machine, and possibly add new control signals to support this operation. You may add registers to the datapath to save and restore user and supervisor stack pointers.

   4. The interrupting event supplies its 8-bit interrupt vector (INTV). The interrupt vector for the timer is 0x01.

   5. The processor left-shifts the interrupt vector one bit, yielding x02, and adds it to the base address of the interrupt/exception vector table (x200), yielding the address of the memory location (x0202), which contains the starting address of the interrupt service routine.

   6. The contents of memory location x0202, which should be x1200 for this assignment, are read and loaded into the PC.

   7. The processor begins execution of the interrupt service routine.

   The first step in adding support for interrupts is to determine how the state diagram of the LC-3b can be modified to handle interrupts. You will have to augment the microsequencer with additional logic to sequence these new states, and extend the existing microinstructions with additional bits for both the microsequencer and the datapath. You may augment current microinstruction fields and add new fields. You may also add new logic to the datapath. You are free to implement this as you wish, but you must document your method.

   RTI Instruction

   Next, you have to implement an instruction for returning from an interrupt. This will be used in the interrupt service routine to transfer control back to the interrupted program. This instruction, called RTI (return from interrupt), has the opcode 1000, and pops the old PC and PSR off the supervisor stack. If the RTI transfers control back to a user-level program, then the microcode should switch the stack pointer back so that R6 points to the user stack. (See the ISA reference for details on the RTI instruction)

3. Adding support for exceptions

   Page Fault Exception

   If the page accessed by a user program is not valid (not in physical memory), then a page fault exception will occur. Exception handling for page faults is very similar to interrupt handling as described above with an important difference: the exception-causing instruction should not be allowed to complete before the exception is handled. Hence, the memory access that causes the page fault exception also should not be allowed to complete. You will need to change the mode of the machine to supervisor, switch to the supervisor stack, push the decremented PC and PSR on the supervisor stack and load the PC with the address of the exception service routine. The exception vector for page fault exception is x02. You can store the exception vector in a separate EXCV register and add this register to the interrupt/exception vector table base register to get the address of the location that contains the starting address of the exception service routine. You are free to implement this as you wish, but keep in mind the possibility of combining the states used for initiating the interrupt service routine and those used for initiating the exception service routine.

   You will also write the exception service routine for the page fault. This routine should start at memory location x1400. For the purposes of this assignment, the exception service routine will simply halt the machine. However, don't rely on this. We can test your simulator by replacing your exception routine with our routine which returns from the exception handler using the RTI instruction instead of halting the machine. Upon return from the exception handler, the instruction that caused the exception should be re-executed.

   Protection Exception

   Protection exceptions occur only when the machine is in user mode, and a memory page whose PTE protection bit is set to 0 is accessed. The memory access that causes a protection exception should not be allowed to complete. Similar to a page fault, the processor takes the necessary steps and jumps to a handler routine to handle the protection exception. Exception vector for the protection exception is x04. The exception handler for the protection exception is located starting at x1600. This routine should halt the machine. However, as with the page fault exception, do not assume that the machine will always be halted after a protection exception occurs.

Tips on getting started

We suggest that you implement each of the three functionalities and test them one by one before putting them all together. This should make the debugging process simpler. For example, you can start by implementing the virtual memory support. Once you test and make sure that address translation works, you can move on to adding support for interrupts and exceptions. When designing the mechanisms to support interrupts and exceptions keep in mind that they are handled very similarly. In your microcode, states for pushing the PSR and PC on stack and loading the address of handler routines could be shared for both exception and interrupt handling.

Writing Code

The user program in page 24 should do the following: calculate the sum of the first 20 values stored in the memory locations beginning with xC000 (notice this is on page 96). This sum should then be stored at xC014. Then the program should jump to the address pointed to by this sum. Page 96 contains data to be used by the program on page 24. The following numbers should be stored there:
x0012, x0011, x2F39, x1023, x1002, x00F6, x0912, x0123, x0456, x0789, x0ABC, x0DEF, x0000, x0001, x0002, x0003, x0004, x0005, x0006, x0007.
These should be loaded into page 96 on initialization of the simulator.

The interrupt service routine must traverse the entire page table, clearing the R bits of each PTE. You may assume when writing this code that the start address of the page table is fixed.

The exception handlers you will submit should simply halt the machine.

Initial Page Table Contents

The page table will be initialized upon simulator start-up. It should look as follows:

Pages 0-23 are in frames 0-23. They are valid and inaccessible by the user.
Page 24 is in frame 25. It is valid and accessible by the user.
Page 96 is in frame 28. It is valid and accessible by the user.
Page 126 is in frame 29. It is valid and accessible by the user. This page contains the user stack.
All other pages are invalid.

1. Adequately documented source code of your simulator called lc3bsim3.c.
2. The assembly code for the interrupt service routine, the page table, the interrupt/exception vector table, the page fault exception handler, the protection exception handler, the user program, and the data on page 96, called int.asm, pagetable.asm, vector_table.asm, except_pf.asm, except_prot.asm, add.asm, and data.asm respectively.
3. The machine code for the interrupt service routine, the page table, the interrupt/exception vector table, the page fault exception handler, the protection exception handler, the user program, and the data on page 96, called int.hex, pagetable.hex, vector_table.hex, except_pf.hex, except_prot.hex, add.hex and data.hex respectively.
4. The new microcode called ucode3.
5. A file called dumpsim. To generate this file, simulate the LC-3b assembly programs by following the instructions at the end of this section.
6. A text file called readme that explains how you implemented this lab assignment. This readme file should describe the following:
   1. Changes you made to the state diagram. Include a picture similar to the state machine that shows the new states you added (only show your changes or mark your changes in a new state diagram). This picture should include the encodings of new states you added. Clearly show where each state fits in the current state diagram. Describe what happens in each new state.
   2. Changes you made to the datapath. Clearly show the new structures added, along with the control signals controlling those structures. Describe the purpose of each structure.
   3. New control signals you added to each microinstruction. Briefly explain what each control signal is used for.
   4. Changes you made to the microsequencer. Draw a logic diagram of your new microsequencer and describe why you made the changes.

How to generate the dumpsim file

Dump the memory locations containing the page table entries once before the 500th cycle, once after the ISR is done, and finally after the page fault halts the execution of the program (you should get a page fault after the jump). Also, dump memory location x3814 (corresponding to which virtual address?) and the current registers after the page fault.

Things To Consider

The user stack should start at address 0xFE00 and the supervisor stack should start at virtual address 0x3000.

1. When do you need to do address translation? How will you return from the address translation to the correct state? An obvious solution would be to have a register which holds the 6-bit return address. Although this is acceptable, think about the possibility of other solutions, e.g. a mechanism that is similar to COND bits in the microsequencer?
2. Since the page table is in physical memory, and the PTBR contains a physical address, the interrupt service routine needs to access the PTEs using physical addresses. An easy way to do this is to turn off virtual to physical address translation when operating in system mode. This will have the added benefit of reducing the number of cycles taken to execute the ISR. What restriction does turning off virtual to physical address translation place on the interrupt service routine code?
3. The microcode used for starting the exception service routine is very similar to the microcode that is used for starting the interrupt service routine. Are there any differences? With these differences in mind perhaps you can combine the states used for interrupt and exception handling.
4. The interrupt service routine should not change any register values which are being used by the main program. We should be able to test the service routine you wrote with a main program (and a simulator) written by us and both programs should work correctly. Therefore, if your interrupt service routine destroys any registers, it should save the original values of those registers before destroying them and restore those values before returning control to the main program. Note that this saving/restoring of general purpose registers could also be supported by microcode. Is this a good idea? A related issue is the saving and restoring of condition codes. This has to be done in microcode, it cannot be done by the interrupt service routine. Why?
5. Make sure you check Appendix A for the description of PSR, the RTI instruction, privilege mode, user stack, supervisor stack, and more information on interrupt processing.
6. The functionality of your modifications to support interrupts and exceptions should not depend on the interrupt and exception handlers you write for this assignment. We should be able to replace your interrupt and exception handlers with handlers written by us, and your code should still work correctly. Conversely, the functionality of your interrupt and exception handlers should not depend on the user program you wrote for this assignment. We should be able to use your exception and interrupt handlers in our simulator running a user program different from what you wrote.
7. Basic LC-3b microarchitecture described in Appendix C makes use of 31 of the available 64 states. This leaves you with 33 states to accomodate your changes to support virtual memory, exceptions and interrupts. Try to avoid expanding the size of the control store.. You can avoid this by careful thinking and design before starting coding.
8. You do not need to worry about nested interrupts for this assignment.