13. Exceptions, Traps and Interrupts

Part of 22C:60, Computer Organization Notes
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science


Up to this point, we have focused on purely sequential control transfers, with no provision for exceptional conditions. In fact, programmers never need to go beyond these simple models, but by adding exceptions to our programming languages and interrupt mechanisms to our computer hardware, we can write programs far more compactly than we could if we were forced to handle exceptions with explicit error returns. To illustrate this, consider the following simple program:

A simple subroutine with no exception handling
int distance( int x1, int y1, int x2, int y2 ) {
        /* return cartesian distance from <x1, y1> to <x2, y2> */
        return squareroot( square( x1 - x2 ) + square( y1 - y2 ) );

Here, we assume that square() and squareroot() are subroutines that compute the appropriate functions of their arguments. This code looks straightforward, until you consider the possibility that squaring a number, or addition, or subtraction would produce an overflow.

A classic way to deal with errors within functions is to define some return value as an error flag. For example, since neither the distance between two points nor the square of a number can be negative, we could use negative values as error indicators. One of the reasons that the IEEE standard floating point representation includes NaNs (values that are not a number) is to facilitate this. Confining ourselves to the purely sequential subset of C and C++ and ignoring overflows resulting from adding or subtracting, this leads to the following hard-to-read code:

Clumsy exception handling makes code hard to read
int distance( int x1, int y1, int x2, int y2 ) {
        /* return cartesian distance from <x1, y1> to <x2, y2>
           returns a negative value if there is an overflow */
        int squarex = square( x1 - x2 );
        int squarey = square( y1 - y2 );
        if ((squarex < 0) || (squarey < 0)) {
                /* taking the square produced an overflow */
                return -1;
        } else {
                return squareroot( squarex + squarey );

The above code becomes even worse if we attempt to detect overflow in the addition or subtraction operators. This is why, in the late 1960s programming language designers began to explore what we now call exception handling mechanisms. Although the language PL/I developed by IBM in the mid 1960s had a crude exception handling mechanism, and although Pascal and C, both developed around 1970, had primitives that could be used to build exception handling mechanisms, the modern model of exception handling did not reach maturity until the development of the Ada language in the late 1970s. Variants of the Ada exception model have been incorporated into C++, Java and many more recent languages.

In this model, exceptions are global objects, so an exception may be raised anywhere in the code. Wherever the exception is raised, the result is a transfer of control to the current handler for that exception. At any instant, each exception defined in the program must have exactly one handler. Raising or throwing an exception (the terms vary between languages) causes a control transfer to that exception's current handler. Consider the following example, using Ada syntax:

An exception handler in Ada
procedure X is
    K: BOOLEAN; -- a local variable
    ... the body of X, code here might raise CONSTRAINT_ERROR ...
        ... the handler for constraint errors ...
end X;

Here, the subroutine named X installs a handler for the CONSTRAINT_ERROR exception. The identity of any previous handler for this exception is saved, to be restored on exit from X. Within the body of X and any subroutines X calls, raising CONSTRAINT_ERROR will cause an immediate transfer of control to the handler, unless there is a more local handler. CONSTRAINT_ERROR is predefined in Ada, raised when a program tries to use a value outside the legal range for the use at hand.

Note that raising an exception does more than just transfer control to the handler. It also restores the context of the handler. In the above Ada code, because the CONSTRAINT_ERROR handler is part of the subroutine X, it has access to any and all local variables of X; in this case, the Boolean variable K. From this, we conclude that if local variables are stored in activation records pushed onto a stack, raising an exception must restore the stack to its state at the time the handler was installed.

Exceptions in C++ and Java are considerably, and perhaps unnecessarily more complex. In these languages, handlers may be parameterized, and programs distinguish between different exceptions by testing the values of the parameters. Furthermore, the usual explanation of exception handling in these languages is given in terms of a complex computation instead of a quick jump to the appropriate handler. The core mechanism discussed here underlies the typical implementation of C++ exceptions and could be used in compiled versions of Java.


a) Modify the distance() routine given above so that it not only returns a negative value if the calls to square() or squareroot() involve overflows, but also if any of the sums or differences produce an overflow. Since C and C++ do integer arithmetic without reporting any exceptions, you will have to use explicit if statements to do this! Consider the sum a+b for positive values. This will produce an overflow if (a+b)>max, but this Boolean expression is useless when max is the largest possible integer. Therefore, we must do some algebra and note that (a+b)>max implies a>(max-b); the latter expression is useful.

b) What happens to the variables of a program when an exception is raised and handled? Which variables can be trusted to have well determined values, and of these, which will have their values unchanged from the time the handler was installed? Which variables have undetermined or ill defined values as a result of the exception being raised?

Exceptions at the Machine Level

The above discussion of exception semantics leads fairly directly to an assembly language implementation. From the fact that exceptions are global we conclude that, in SMAL Hawk language, each exception must be a COMMON block. That is our only available tool to allocate global variables.

In the previous section, we mentioned two components of an exception. First, each exception must identify its current handler. Since the handler is a piece of code, the identity of that handler must be the address of that code. Second, on entry to the handler, we noted that the activation record of the subroutine containing the handler must be restored. Therefore, the exception must hold a pointer to the handler's activation record. Because exceptions may be raised anywhere, we should put the declarations applicable to all exceptions in a header file for use anywhere exceptions are used.

The header file for Hawk exception handling
; exceptions.h -- declarations applying to exceptions

; an exception is a record structure with the following fields
EXHAND  =       0       ; one word, the address of the handler
EXAR    =       4       ; one word, the handler's activation record
EXSIZE  =       8       ; the total size of the exception record

In Ada, there are a number of predefined exceptions, CONSTRAINT_ERROR for example, which is raised by an attempt to use an array index outside the legal range, by an attempt to follow a null pointer or by an attempt to assign a value to a variable outside that variable's legal range of values. To allow access to a CONSTRAINT_ERROR exception in assembly language, we can use the following code, duplicated in in each source file where this exception is raised or handled:

Declaring an exception in a Hawk program
        USE     "exceptions.h"


This code merely declares a global variable, an uninitialized a block of EXSIZE bytes named CONSTRAINT_ERROR. Each file that repeats this code will be able to load its address into a register. Recall that repeating a common declaration creates only one shared copy of that common block.

Suppose a routine within the program wants to install a handler for constraint errors. The routine must include, in its activation record, space to save the previous handler for the exception. This can be declared as follows, using the local variable declaration macro discussed at the end of Chapter 11:

Activation record field for a routine including an exception handler
ARSIZE  =       0
        ...  definitions of other local variables
        LOCAL   OLDCON, EXSIZE  ; old CONSTRAINT_ERROR handler save area

These are normal declarations for a local variable in an activation record. The control structure of a C++ or Java try-catch block, or of an Ada block ending with an exception handler would be as follows:

Overall structure of a block that handles exceptions
        ; save old CONSTRAINT_ERROR exception in OLDCON in my AR
        ; install MYHAND as new CONSTRAINT_ERROR handler

        ... body of try clause

        ; restore old CONSTRAINT_ERROR exception from OLDCON in my AR

        BR      MYHANDEND

        ; restore old CONSTRAINT_ERROR exception from OLDCON in my AR

        ... body of handler


The above control structure resembles an if-then-else block. The try clause resembles a then clause, ending with a branch to the end. The handler itself resembles an else clause, beginning with a label. The big difference is that this structure transfers control to the handler from anywhere in the try clause or any routine it calls. In contrast, the control transfer to an else clause comes from only one place.

The code to save the state of a global variable in a local variable is no different for exceptions than it would be for any other variable. Installing a handler is fairly simple too:

Code to save the old handler and install a new handler
        ; save old CONSTRAINT_ERROR exception in OLDCON in my AR
        LOAD    R4,R3,EXHAND    ; oldcon.exhand = constraint_error.exhand
        LOAD    R4,R3,EXAR      ; oldcon.exar = constraint_error.exar

        ; install MYHAND as new CONSTRAINT_ERROR handler
        LEA     R4,MYHAND
        STORE   R4,R3,EXHAND    ; constraint_error.exhand = myhand
        STORE   R2,R3,EXAR      ; constraint_error.exar   = AR

Note in the above code that indexed addressing using R2 and the displacement OLDCON addresses the first word of the OLDCON field in the activation record. Since this field is a multiword object, we can use OLDCON+EXHAND to reference one word of this object and OLDCON+EXAR to reference the other word of the object. Restoring the old handler reverses the logic of the save code above:

Code to restore the old handler
        ; restore old CONSTRAINT_ERROR exception from OLDCON in my AR
        STORE   R4,R3,EXHAND    ; constraint_error.exhand = oldcon.exhand
        LOAD    R4,R2,OLDCON+EXAR
        STORE   R4,R3,EXAR      ; constraint_error.exar = oldcon.exar

The old handler must be restored at the end of the try clause, immediately before the jump to the end of the exception handler, and if the exception is raised in the body of the handler, or in code called from the body, the old handler must be restored before any code in the handler itself is executed. With the handler properly installed, we can raise an exception as follows:

Raising an exception, the general case
        LOAD    R2,R1,EXAR      ; AR = constraint_error.exar
        LOAD    R1,R1,EXHAND
        JUMPS   R1              ; PC = constraint_error.exhand

A far more compact transfer of control to the exception handler is possible if we know that the handler is local. The above verson must be used when the handler is not local, for example, when the exception is being raised in a library routine and it must be handled by some user routine. If the exception is being raised locally, within the body of the try clause, we can use a far simpler formulation because register 2 does not need to change. In that case, we raise the exception with a simple branch instruction:

Raising a local exception
        BR      MYHAND          ; raise constraint_error locally

There are two options in the main program. One is to install a default handler for all exceptions, while the other is to leave the handler uninitialized, leading to undefined behavior for exceptions raised outside the context of an installed handler.

We must ask, for any exception mechanism, exactly what is restored by the transfer of control to the exception handler, and what is lost as the exception is raised. For the machine code outlined above, the author of the exception handler can rely on things stored in the local activation record, but there is no easy way for it to account for what is or is not in the registers at the time the exception is raised. Therefore, any routine that installs an exception handler must save the return address and anything else it needs in its own activation record and not rely on called routines to save and restore anything.


c) Write a Hawk main program that installs a default handler for CONSTRAINT_ERROR and then calls the external subroutine APPLICATION. Your handler should just print out the message constraint error in the upper left corner of the display and then exit.

d) The code given here to save the old handler and install its replacement and the code given here to restore the old handler violates the data abstraction of the exception mechanism by exposing, to the programmer, the internal structure of the exception variable. Write a pair of subroutines to hide this information. The interface to these belongs in the file exception.h and the subroutines would go in a new file, exception.a.

e) The code given here to save the old handler and install its replacement and the code given here to restore the old handler violates the data abstraction of the exception mechanism by exposing, to the programmer, the internal structure of the exception variable. Write a pair of macros that can be included in the file exception.h that hide this information.

An Example

To illustrate this set of exception handling tools, consider the problem of adding support for exceptions to one of the unsigned multiply routines given in Chapter 9. Multiplication can produce values too large to store in one word, so it is appropriate to raise a constraint error when this occurs.

Unsigned multiplication with overflow detection
        ; expects R3 = unsigned multiplier
        ;         R4 = multiplicand
        ; uses    R5 = temporary copy of multiplier
        ; returns R3 = unsigned product
        MOVE    R5,R3           ; -- move the multiplier
        CLR     R3              ; product = 0;
        TESTR   R5
        BZS     MULTLX          ; if (multiplier != 0) {
MULTLP:                         ;   do { -- loop exits by break
        SRU     R5,1            ;     multiplier = multiplier >> 1;
        BCR     MULTEI          ;     if (multiplier was odd) {
        ADD     R3,R3,R4        ;       product = product + multiplicand;
        BCS     RCONERR         ;       if carry set, raise constraint error
MULTEI:                         ;     }
        TESTR   R5
        BZS     MULTLX          ;     if (multiplier != 0) break;
        SL      R4,1            ;     multiplicand = multiplicand << 1;
        BCS     RCONERR         ;     if carry set, raise constraint error
        BR      MULTLP          ;   }
MULTLX:                         ; }
        JUMPS   R1              ; return product;

RCONERR:                        ; common code for raising constraint error
        LOAD    R2,R1,EXAR      ; AR = constraint_error.exar
        LOAD    R1,R1,EXHAND
        JUMPS   R4              ; PC = constraint_error.exhand

This code tests the carry bit to detect unsigned overflows after both the ADD and SL. On detecting an overflow, the code branches to the 4 instruction sequence to raise the exception. This sequence is identical wherever the exception might be raised, so it is written just once instead of duplicating it where needed.

Suppose we have an assembly language version of the code for distance() from the start of this chapter that uses use the above multiply routine to compute the required squares. The following code calls this and outputs the distance in decimal, for example, saying "the distance is 39 microns", but if there is an range-constraint exception, it outputs "the distance is too big". To do this, it installs a handler.

Code that installs a handler, part 1
; activation record format for the Show Distance routine
ARSIZE  =       0
        LOCAL   RETAD,4
        LOCAL   X1,4            ; saved parameters
        LOCAL   Y1,4
        LOCAL   X2,4
        LOCAL   Y2,4
        LOCAL   OLDCON,EXSIZE   ; save old constraint error handler

SHOWDIST:       ; expects (R3,R4) = (x1,y1) point 1
                ;         (R5,R6) = (x2,y2) point 2
        STORES  R1,R2           ; -- save return address
        STORE   R3,R2,X1
        STORE   R4,R2,Y1
        STORE   R5,R2,X2
        STORE   R6,R2,Y2        ; -- save parameters

        LEA     R3,SDMSG        ; -- parameter
        ADDI    R2,ARSIZE
        LIL     R1,PUTS
        JSRS    R1,R1           ; puts( "the distance is " );
        ADDI    R2,-ARSIZE
        ; save old CONSTRAINT_ERROR exception in OLDCON in my AR
        LOAD    R4,R3,EXHAND    ; oldcon.exhand = constraint_error.exhand
        LOAD    R4,R3,EXAR      ; oldcon.exar = constraint_error.exar

        ; install MYHAND as new CONSTRAINT_ERROR handler
        LEA     R4,SDHAND
        STORE   R4,R3,EXHAND    ; constraint_error.exhand = sdhand
        STORE   R2,R3,EXAR      ; constraint_error.exar   = AR

        ; body of code to which new handler applies
        LOAD    R3,R2,X1        ; -- parameters
        LOAD    R4,R2,Y1
        LOAD    R5,R2,X2
        LOAD    R6,R2,Y2
        ADDI    R2,ARSIZE
        JSR     R1,DISTANCE     ; R3 = distance( x1, y1, x2, y2 );

        LIL     R1,PUTDEC
        JSRS    R1,R1           ; putdec( R3 );

        LEA     R3,SDUNIT       ; -- parameter
        LIL     R1,PUTS
        JSRS    R1,R1           ; puts( " microns" );
        ADDI    R2,-ARSIZE

        ; restore old CONSTRAINT_ERROR exception from OLDCON in my AR
        STORE   R4,R3,EXHAND    ; constraint_error.exhand = oldcon.exhand
        LOAD    R4,R2,OLDCON+EXAR
        STORE   R4,R3,EXAR      ; constraint_error.exar = oldcon.exar
        BR      SDDONE          ; skip around exception handler

Code that installs a handler, part 2
SDHAND:                         ; exception handler for showdist
        ; restore old CONSTRAINT_ERROR exception from OLDCON in my AR
        STORE   R4,R3,EXHAND    ; constraint_error.exhand = oldcon.exhand
        LOAD    R4,R2,OLDCON+EXAR
        STORE   R4,R3,EXAR      ; constraint_error.exar = oldcon.exar

        LEA     R3,SDTBIG       ; -- parameter
        LIL     R1,PUTS
        ADDI    R2,ARSIZE
        JSRS    R1,R1           ; puts( "too big" );
        ADDI    R2,-ARSIZE

        ; code outside of exception handler
        LEA     R3,SDCRLF       ; -- parameter
        LIL     R1,PUTS
        ADDI    R2,ARSIZE
        JSRS    R1,R1           ; puts( "\r\n" );
        ADDI    R2,-ARSIZE

        LOADS   R1,R2
        JSRS    R1,R1           ; return

SDMSG:  ASCII   "the distance is ",0
SDUNIT: ASCII   " microns",0
SDTBIG: ASCII   "too big",0
SDCRLF: B       CR,LF,0

There are other ways to handle exceptions. Consider representing an exception with a global variable pointing to a local variable in the block that installed the current handler. This local variable holds the addresses of the handler, its activation record pointer and the previous value of the global pointer. This makes saving and restoring exceptions significantly faster, while slightly slowing the code to raise an exception. In this case, the global variable is now just one word, a pointer, while the record of exception installation is three words in the activation record of the routine that installed the exception.


f) The code for SHOWDIST given here contains modest optimizations -- it avoids incrementing and decrementing R2, the activation record pointer, between many pairs of successive calls. Find and eliminate the extra increments and decrements of R2 that remain.

g) Evaluate the beneift eliminating the string SDCRLF from SHOWDIST and making the output identical to the original by adding a trailing carriage return and linefeed to the ends of the two strings SDUNIT and SDTBIG. How much smaller will the program be if this change is made? How much faster will the program run?

h) Translate the code for SHOWDIST to Ada, C++ or Java, documenting the changes needed because of any difference in the exception handling model of the new language.

i) Give code for saving the old handler and installing a new one, code for restoring the old handler, and code for raising an exception, using the alternative representation for exceptions suggested at the end of the section above. Does save code space? Does it save stack space?

Traps: Exceptions Detected by Hardware

While the overflow and carry condition codes of the Hawk and other computers can be used to detect exception conditions in integer arithmetic, the most important hardware exception detection mechanisms center around detecting illegal instructions, illegal memory references, and other major program faults. Most processors can detect some or all of the following:

System Reset
Someone pushed the reset button on the computer system, or the machine was just turned on.

Bus Error
An attempt was made to read or write a nonexistant memory location or to write to a read-only location. Following uninitialized or null pointers can cause this.

Illegal Instruction
An instruction was executed that is not defined in the instruction set of this computer. Accidentally jumping to a random memory location can cause this.

Privilege Violation
An instruction was executed that is not permitted in the current operating mode. In the case of the Hawk, the CPUGET and CPUSET instructions are only permitted if the level field of the processor status word is not 11112.

In general, the central processors of modern computers have no understanding of the exception handling mechanisms of high-level programming languages. Instead, processors have a different exceptiom model, referred to as a trap mechanism. Trap mechanisms were introduced on computers of the 1950s and 1960s, well before the exception models of high-level languages. In almost all cases, operating systems handle traps, not applicaton programs.

Traps on the Hawk operate as follows: First, the instruction that caused the trap is aborted. All traps can be traced back to the execution or attempted execution of some instruction. Then, several things are saved. The address of the instruction that caused the trap is saved in a special register, TPC or the trap program counter. If the trap involved an illegal memory address, that address is saved in another register, TMA or the trap memory address. At the same time, the level field of the processor status is saved in the old-level field. Finally, after it is saved, the program counter is set to a value determined by the trap, and the level field of the processor status word is set to zero (the most permissive level).

The Hawk processor status word
31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
level old level BCD carry N Z V C

It is important to note that the Hawk guarantees that traps will always be detected before an instruction has any side effects on registers or memory. Therefore, the old-level field of the processor status word, the value of the TPC register and the contents of general purpose registers 1 to 15 completely describe the state of the program immediately before it executed the instruction that caused the trap.

When a trap occurs, the new program counter value is set depending on the cause of the trap. Each component of the processor that detects trap conditions provides a 4-bit code to identify the cause; this code sets bits 4 to 7 of the new program counter value, with the remaining bits set to zero. As a result, memory locations from 0 up to 10016 are reserved for trap processing. These locations constitute the trap vector of the Hawk. The following locations in the trap vector are used by the trap hardware described here:

The Hawk Trap Vector
System Reset 0000000016 Power-on or someone pushed reset.
Bus Error 0000001016 Illegal memory reference.
Illegal Instruction 0000002016 Use of an unimplemented opcode.
Privilege Violation 0000003016 Use of CPUGET or CPUSET when level is 11112.

Higher numbered locations in the trap vector are available for use by coprocessors, and they are used by interrupt service routines, topics we will discuss later.

The final tools we need for dealing with traps are tools to examine and set the special fields of the processor status word and the special registers, TPC and TMA. These are all manipulated using the CPUSET and CPUGET instructions. For example, CPUGET R4,TPC loads the trap program counter TPC into R4, and CPUSET R4,PSW stores the contents of R4 into the processor status word. These instructions can access 16 special registers within the processor. In commercial processors, special registers are commonly included for self testing, and sometimes, the interfaces for devices closely allied to the processor are included here. There is also a TSV register, advertised as the trap-save register but actually just 32 bits with no committed purpose – although as we will see, we need it here.

When CPUGET is used to load a special CPU register into register zero, this is interpreted as loading the program counter, and it has the side effect of restoring the level field of the processor status word to the old level. Thus, if the only instruction of a trap handler is CPUGET R0,TPC the effect is to completely undo the effects of the trap and try, again, to execute the instruction that caused the trap. This is almost certain to lead to another trap, putting the processor into an infinite loop. The hawk.h file defines the instruction RTT, meaning return from trap as an alternative name for CPUGET R0,TPC.


j) What special registers are available within the Hawk processor and how are they encoded for reference by the CPUSET and CPUGET instructions; you will have to look this up in the Hawk manual.

k) Why is the CPUSET instruction dangerous enough that it forces a trap when a user tries to execute it when the level field is 11112?

A Trap Handler

The default trap handlers installed by the Hawk monitor simply print out the contents of the trap program counter and trap memory address registers before halting the program. This helps during debugging, but if a program needs to handle the exception, it is not enough. To handle an exception, the program must install code in the appropriate location in the trap vector to jump to its own trap handler. This handler should then translate from the Hawk's trap model to the exception handling model of your program.

Each entry in the Hawk trap vector is only 16 bytes long, which is 8 halfwords or 4 words. If we have no desire to be able to examine or restore registers, this is more than enough to allow a jump to the user's own trap service routine:

Minimalist code to intercept bus error traps
.       =       #10             ; bus error entry in the trap vector
        LIL     R1,BUSER
        JUMPS   R1              ; go to rest of handler

This minimalist code destroys R1, which might prevent us from writing a handler that displays this for debugging. The Hawk monitor uses a special register to solve this problem, TSV, the trap-save register. TSV exists only to solve this one problem and is never used by application programs.

Better code to intercept bus error traps
.       =       #10             ; bus error entry in the trap vector
        CPUSET  R1,TSV          ; save R1
        LIL     R1,BUSER
        JUMPS   R1              ; go to rest of handler

This second version of the trap vector code given above uses a total of 8 bytes of code. There is room to squeeze in four more halfwords of code, if we wanted to do so.

Given either of the above bits of code, we can write a trap handler to convert bus error traps into constraint error exceptions, using the Ada convention that the exception CONSTRAINT_ERROR is to be raised whenever a program tries to use an invalid pointer.

Better code to intercept bus error traps

BUSERR:                ; intercept bus error exceptions
        LOAD    R2,R1,EXAR      ; R2 = CONSTRAINT_ERROR.EXAR
        LOAD    R1,R1,EXHAND
        CPUSET  R1,TPC
                                ; note:  PSW.level is restored!

If we wanted our default trap handler to be able to print out all of the registers as they were at the time of the trap, we would have to add more code to the above to save the values of registers in some dedicated memory area before using any registers for trap handling. This is illustrated in the next section.


l) Modify the bus error trap handler given above so it saves copies of every register it modifies in a common block called TRAPSAVE, including the copy of R1 that was initially saved in TSV. This lets the trap handler recover this information if it is needed.

Emulation Traps and Virtual Machines

Traps have important uses other than exception handling. Of these, one of the most important is in the creation of a virtual machine that supports features not present in the actual hardware. To a user writing machine language code, a virtual machine appears to be hardware, except that some instructions take much longer to execute than others. These are the instructions that are executed by software in trap handlers, not by hardware.

The term virtual machine borrows from the field of optics. Systems of mirrors and lenses may cast several images. Some images are real. If you put a sheet of film where a real image appears to be, the film will capture that image as a photograph. Other images are said to be virtual. They look like images, but if you put film where a virtual image seems to be, you get nothing but a blur. Virtual images are always seen through lenses, reflected in mirrors, or behind holograms.

From the programmer's viewpoint, a virtual machine looks like a real machine, but it is an artifact created by a mixture of hardware and software. The Hawk virtual machine is created entirely by software, the Hawk emulator. Virtual machines that mix real hardware with software are created using trap handlers.

The Hawk has several unimplemented opcodes. Executing one of them causes an illegal instruction trap. In addition, if the level field of the processor status word is 11112, CPUSET and CPUGET cause privilege violation traps. As we will see later, this, in combination with a memory management unit, allows us to securely confine an untrusted program to a virtual machine with access to only limited parts of main memory.

The opcode 0001dddd 1000ssss2 is unimplemented on the Hawk. As a halfword, with the bytes in the correct order and register fields set to zero, this is 801016. Suppose we wanted to use this as the opcode for a virtual register-to-register multiply instruction using an unimplemented instruction trap handler. Our software multiplication routine might need the value of any register, so our handler needs to save everything in a register save area on entry and then restore it on exit.

Defining a Register Save Area
        COMMON  SAVEREGS,17<<2  ; save area for registers
PCSAVE  =       0               ; displacements within save area
R1SAVE  =       1<<2
R2SAVE  =       2<<2
R3SAVE  =       3<<2
RESAVE  =       14<<2
RFSAVE  =       15<<2
PSWSAVE =       16<<2

The code to save the registers begins in the trap vector, right after saving R2 in the TSV register. Each entry in the trap vector is 16 bytes, and there is no reason not to use this space before jumping to the remainder of the trap handler.

Unimplemented instruction trap vector code
.       =       #20             ; unimplemented instruction trap
        CPUSET  R2,TSV          ; save R2 temporarily
        LIL     R2,SAVER
        STORE   R1,R2,R1SAVE    ; save R1 properly
        LIL     R1,UNIMP
        JUMPS   R1              ; go to the handler
        ; the above code occupies exactly 16 bytes!

The remainder of the trap handler is closely tied to this code. On entry, it must assume that only R1 has been completely saved, and that R2 is still saved in TSV. The fact that the Hawk LOAD and STORE instructions do not touch the condition codes is essential to the correct functioning of this code, since the PSW has yet to be saved. The following code saves the entire CPU state:

Saving the rest of the registers
; unimplemented instruction trap handler continuation

UNIMP:  ; expects R2 points to the register save area
        ;         R1 has been saved properly
        ;         TSV still holds the saved value of R2
        ;         PSW (including CCs) still unsaved
        CPUGET  R1,PSW
        STORE   R1,R2,PSWSAVE   ; PSW is now properly saved
        CPUGET  R1,TSV
        STORE   R1,R2,R2SAVE    ; R1 is now properly saved
        CPUGET  R1,TPC
        STORE   R1,R2,PCSAVE    ; PC is now properly saved
        STORE   R3,R2,R3SAVE    ; continue saving R3 to R15
        STORE   R4,R2,R4SAVE
        STORE   R5,R2,R5SAVE
        STORE   R13,R2,RDSAVE
        STORE   R14,R2,RESAVE
        STORE   R15,R2,RFSAVE   ; entire CPU state is now saved

The code for detecting the instruction we want to emulate goes next, but before we distract ourselves with this, we will focus on the problem of returning from the trap. We do this by restoring the registers, and then, finally, we use CPUSET and CPUGET to restore the program counter and processor status word.

Restoring the registers
; return from any trap handler
        ; expects R2 points to the register save area
        LOAD    R15,R2,RFSAVE   ; start restoring registers
        LOAD    R14,R2,RESAVE
        LOAD    R13,R2,RDSAVE
        LOAD    R5,R2,R5SAVE
        LOAD    R4,R2,R4SAVE
        LOAD    R3,R2,R3SAVE    ; R15 to R3 now all restored
        LOAD    R1,R2,PCSAVE
        CPUSET  R1,TPC		; PC partially restored
        LOAD    R1,R2,PSWSAVE
        CPUSET  R1,PSW          ; PSW now restored
        LOAD    R1,R2,R1SAVE    ; R1 restored without changing CCs
        LOAD    R2,R2,R2SAVE    ; R2 restored without changing CCs
        CPUGET  R0,TPC          ; return from trap!

The above code uses the strange semantics of R0 on the Hawk machine. In the context of the CPUGET instruction, R0 refers to the program counter, so the final instruction above loads the program counter from the TPC register. This has the side effect of restoring the level field of the PSW.

The code that does the actual work of our virtual machine, between saving and restoring the registers, begins by finding out what instruction was attempted. If it was not 0001dddd 1000ssss2, we should raise the same exception that the original handler would have raised.

Checking what instruction caused the trap
; see if the unimplemented instr was 0001dddd 1000ssss (#8s1d)
        ; expects all registers have been saved
        ;         R2 points to the register save area
        LOAD    R3,R2,PCSAVE    ; get the saved program counter
        LOADS   R4,R3
        EXTH    R5,R4,R3        ; get the halfword it points to
                		; -- the instruction that trapped!
        LIL     R6,#F0F0
        AND     R6,R5           ; clear all but the opcode bits
        CMPI    R6,#8010        ; is it the target instruction?
        BEQ     ISMULT

        LIL     R3,PROGERR      ; not the target, raise exception!
        LOAD    R4,R3,EXAR
	STORE   R4,R2,R2SAVE    ; edit saved processor state
        LOAD    R4,R1,EXHAND
	JUMP	TRAPEXIT        ; normal trap exit code finish it

In the above, once we separated out the instruction or instructions we intend to virtualize, the remaining protection violations are signalled using the program error exception.

With these pieces in place, we can extend the user's virtual machine by writing the code that gives meaning to the undefined opcode we selected for multiply. The code begins by getting copies of the user's saved source and destination registers, and after it multiplies them, it returns the result to the user's saved destination register. In addition, the handler increments the saved program counter before return.

Making an unimplemented instruction do multiplication
ISMULT: ; illegal instruction trap, instruction was #8s1d
        ; expects R2 points to register save area
        ;         R3 is the saved program counter
        ;         R5 is the halfword pointed to by PC, #8s1d
        MOVE    R6,R5           ; copy the instruction
        SR      R5,8
        TRUNC   R5,4            ; R5 is the src register number
        TRUNC   R6,4            ; R6 is the dst register number

        ADDSI   R3,2
        STORE   R3,R2,PCSAVE    ; increment saved PC

        ADDSL   R5,R2,2         ; R5 points to saved dst register
        ADDSL   R6,R2,2         ; R6 points to saved src register

        LOADS   R3,R5           ; R3 is the dst operand
        LOADS   R4,R6           ; R4 is the src operand

        ... code to multiply R3 = R3 * R4 not using R5 and R6 ...

        STORES  R3,R5           ; update the saved dst register
        JUMP    TRAPEXIT        ; go return to user

Now that we have defined a multiply instruction, we should extend our assembly language with a multiply macro added to hawk.h. We can do this as follows:

How to assemble the new instruction
	; note: the following uses an unimplemented
	; opcode and is implemented by emulation using
	; a trap service routine.
        MACRO   TIMES   =dst,=src
          B #10 | (dst - R0)
          B #80 | (src - R0)

In this macro, we wrote dst-R0 and src-R0. By explicitly subtracting R0 from each register, we force the assembler to check that dst and src are relocated relative to the same relocation base as is used for the registers. This allows some error checking at assembly time.


m) Find all of the opcodes in the Hawk instruction set that cause illegal instruction traps. Do this by searching the lists of opcodes in the appendices of the Hawk manual.

n) What code should you add to the start of the main program if you want user code to be able to use the TIMES instruction defined here?

o) Suppose you wanted to be able to call Hawk monitor routines from your trap handler, for example, to use the multiply or divide routines in the monitor. Some of these use R2 as a stack pointer. What code would you add to the code given above above for trap handlers in order to allow this? (Hint: We used R2 as a pointer to the register save area for a reason.)

p) Assume you are not allowed to call subroutines from the trap handler. Add the multiply code to the figure above in place of the text ... code to multiply R3 = R3 * R4 ... (You will have to add this code in-line, without calling a subroutine).

q) The virtual multiply instruction given above does not set the condition codes. Add code so that it sets N and Z to report whether the result is negative or zero.


The trap handling mechanisms described above serve a second purpose on most computers: Handling external events signalled by input-output devices. When these mechanisms are triggered by a device, we refer to the event as an interrupt, not a trap, but the action taken by the CPU remains the same. The control transfer uses the trap vector, so it is also called the interrupt vector, and the code to save and restore registers is the same. Only the cause of the control transfer and handler are different.

In essentially all modern computers, the fetch execute cycle of the hardware is more complex than we have indicated up to this point, in part because of the need to handle exceptional conditions, and in part because of the need for interrupt handling. The Hawk processor is quite typical; here is a more honest and complete presentation of the algorithm implemented by the Hawk processor:

The fetch-execute cycle
int trapvector, interruptvector;
while (TRUE) do {
        try {
        } catch( int vector ) {
                trapvector = vector;
        if (trapvector == 0) {
                trapvector = interruptvector;
                interruptvector = 0;
        if (trapvector != 0) {
                PSW.old_level = PSW.level;
                PSW.level = 0;
                TPC = PC;
                PC = trapvector;
                trapvector = 0;

Under normal circumstances, where instruction raise no exceptions and no devices request interrupts, the extra logic at the end of this code does nothing. It behaves like the original simple fetch-execute cycle. If an instruction raises a trap, or if an external device requests an interrupt, things are different. The extra logic shown above would slow down a software implementation, but if this is done in hardware, there is no run-time cost except when there is actually an interrupt or trap.

Interrupts and traps both use the same trap vector. In the case of traps, it is up to the hardware inside the processor to specify which trap vector entry will be used. In the case of interrupts, it is up to the external device to specify this.

External devices should only raise their interrupt request (IRQ) lines when both the deivice is ready to perform an input or output operation and the program running on the central processor is ready to deal with it. All modern computers have are hierarchies of interrupt enable bits. Each device has its own interrupt enable bit, and there are also one or more global interrupt enable bits. In the case of the Hawk, the global interrupt enable bits are the level field of the processor status word. If this field is 00002, all interrupts are disabled, while 11112 enables all interrupts. Intermediate values enable just some.

Typically, the ready bit in each device's status register determines when that device will attempt to request an interrupt, but only when that device's interrupt enable bit is set. The device-specific interrupt enable bit is completely separate from the global interrupt enable bits in the central processor. The Hawk keyboard interface register logic for this is typical:
Interrupt request logic in the keyboard status register
Keyboard Status Register

The Hawk level field is typical of modern processors. It determines the interrupt priority level. Higher priority devices can interrupt lower priority devices, but not the reverse. Many processors have a set of outputs that directly report the current priority level to external logic, and that logic gives meaning to these bits. In the case of the Hawk, there are two good ways to do this. First, each bit of the level field could be used to enable a different group of devices. In that case, we could have 5 levels, encoded as 00002, 00012, 00112, 01112, and 11112. This allows simple interface hardware, but it is only appropriate if there are only a few device classes.

The other approach is to add a priority interrupt decoder. This allows for 16 levels, encoded as a 4-bit binary number. Mixtures of these schemes are perfectly possible. For example, the most significant bit of the level field on the Hawk enables the memory management unit, so we could use the least significant 3 bits to create 8 different interrupt levels. This mixed model allows use of trap vector entries 8 to 15, at addresses 8016 to F016 for the corresponding interrupt levels.

Assigning interrupt priority involves two issues: First, if two devices request interrupts at the same time, the priority determines which device wins. Second, if one interrupt service routine is running, the priority of an device requesting an interrupt determines whether that request will be granted before the first routine terminates.

On the Hawk, if two interrupt service routines use separate register save areas, then the lower priority interrupt service routine can re-enable interrupts between the time it saves its registers and the time it restores them. It must not enable its own interrupt, but it can set the level field of the processor status word (using the CPUSET instruction) to allow all higher priority interrupts.


r) If each bit of the level field enables interrupts for one device, and if the keyboard interrupt enable bit in the level field of the processor status word is 00102, what instructions should be used just after saving all of the registers to enable all other interrupts?

s) If the least significant 3 bits of the level field of the PSW are used to encode a binary interrupt level, with 00002 meaning disable all interrupts and 01112 meaning enable all interrupts, and if keyboard interrupts are enabled whenever the interrupt level is 00102 or greater, what instructions should be used just after saving all of the registers to enable all other interrupts?

t) If interrupts were enabled within an interrupt service routine, what code must be inserted just before the code to restore the values of the registers in order to make sure that the job of restoring the registers is not itself interrupted.

u) Suppose two different devices have equal priority and they use the same trap vector entry. How can the software determine which device requested the interrupt? Hint: Each device has its own ready bit and its own interrupt enable bit.