12. Exceptions, Traps and Interrupts.
Part of
22C:40, Computer Organization and Hardware Notes
|
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:
int distance( int x1, int y1, int x2, int y2 ) /* return the cartesian distance between <x1, y1> and <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 the distance between two points can never be negative, and the square of a number can never be negative, we can use negative values as error indicators. Confining ourselves to the purely sequential subset of C and C++ and ignoring overflows resulting from adding or subtracting, this leads us to the following awful code:
int distance( int x1, int y1, int x2, int y2 ) /* return the cartesian distance between <x1, y1> and <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 from which exception handling mechanisms could be developed, the modern model of exception handling did not reach maturity until the development of the Ada language in the late 1970s. The Ada exception model, with various changes was incorporated into C++, Java and several other 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 terminology varies between languages causes a transfer of control to that exception's current handler. Consider the following example, using Ada syntax:
procedure X is K: BOOLEAN; -- a local variable begin ... the body of X, code here might raise CONSTRAINT_ERROR ... exception when CONSTRAINT_ERROR => ... the handler for constraint errors ... end X; |
In this example, the subroutine named X installs a handler for the CONSTRAINT_ERROR exception. The identity of any previously installed handler for this exception is saved, and on exit from X, the previous handler will be re-installed. Within the body of X as well as within the body of any subroutines called from X, raising the CONSTRAINT_ERROR exception will cause an immediate transfer of control to the handler, unless a new handler is installed.
The CONSTRAINT_ERROR exception is one of Ada's predefined exceptions. It is used when a program tries to use a value that is outside the range of legal values for some operation. When an array index is out of bounds, for example, it is raised.
It is important to note that raising an exception does more than just transfer control to the handler for that exception. It also restores the context of that handler! So, for example, 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 that are pushed onto a stack, raising an exception must restore the stack pointer to its value at the time the handler was installed.
Exceptions in C++ and Java are considerably, and perhaps unnecessarily more complex. Handlers in those languages may be parameterized arbitrarily, and the algorithm for matching an exception to its handler is based on the type compatability of the actual parameters provided when the exception is raised with the formal parameters on the handler. All issues of type compatability are high-level language issues, above the level of assembly language, and if these are stripped off, the semantics that remains for a C++ or Java exception is not too different from that of Ada.
Exercises
a) Modify the distance() routine given above so that it not only returns a negative value if the calles 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 where both variables are positive. This will produce an overflow if a+b>max, but this boolean expression cannot be evaluated on a machine where max is the larges integer that can be represented. Therefore, we must do a bit of algebra and note that a+b>max implies a>max-b; we can evaluate this expression!
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?
The attributes we have enumerated for exceptions above lead, in a fairly direct way, to an assembly language implementation. First, we noted that exceptions are global. This leads us, immediately, to the conclusion that, in the Hawk assembly language, we must put them in a common block, since common blocks are the only place to put global variables in our language.
The second question we must ask is, what are the components of an exception? There are two that were mentioned in the previous section. First, each exception must identify its current handler. Since the handler is a piece of code, the identity of that handler is just the address of the entry point of that code. Second, we said that, on entry to the handler, the activation record of the subroutine containing that handler must be restored. Therefore, the exception must identify the activation record of the handler. Because exceptions may be raised anywhere, we should put the generic declarations applicable to all exceptions in a header file that can be included by any routine that wants to declare an exception, install a handler or raise an exception.
; 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 |
To declare an exception, we need to allocate a global variable to hold that exception. In Ada, there are a number of predefined exceptions, CONSTRAINT_ERROR for example, is predefined, and it is raised by an attempt to use an array index outside the legal range of values, by an attempt to follow a null pointer or by an attempt to assign a value to a variable that is outside the legal range of values for that variable. Suppose we wanted to imitate this in the Hawk assembly language. The first thing we would do is include the following in our main program:
USE "exceptions.h" COMMON CONSTRAINT_ERROR, EXSIZE PCONERR:W CONSTRAINT_ERROR |
This code is no different from the declaration of any other global variable on the Hawk. We have declared that we want a globally allocated block of variables called CONSTRAINT_ERROR, of size EXSIZE to be allocated in RAM. Then, as part of the program, we have asked for a word holding a pointer to this global variable, with the label PCONERR.
It is legal to repeat this declaration exactly in any separately assembled files of the source program that need to deal with this exception, either to raise it or to handle it. In the SMAL assembly language, common blocks with the same name always refer to the same region of memory. All such common blocks should, of course, be declared to have the same size! When this is done following the pattern shown above, while there will be only one shared common block, each user of this common will have a private copy of the pointer PCONERR; the label on this word is a purely local symbol, while the word holds a pointer to a global object.
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 style of activation record construction discussed at the end of Chapter 10:
... declarations of other local variables ARSIZE = ... OLDCON = ARSIZE ; save area for previous handler ARSIZE = ARSIZE + EXSIZE |
These are entirely unremarkable declarations for a local variable that is part of the activation record. The overall control structure of a C++ or Java try-catch block, or the overall structure of an Ada block that ends with an exception handler would be as follows in machine language:
; start of try clause ; 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 ; end of try clause MYHAND: ; start of handler ; restore old CONSTRAINT_ERROR exception from OLDCON in my AR ... body of handler MYHANDEND: ; end of handler |
There are some strong similarities between the above control structure and the structure of an if-then-else block. The try clause strongly resembles the then clause because it ends with a branch to the end of the entire structure. Similarly, the handler itself resembles an else clause since it begins with a label. The big difference between this structure and an if-then-else block is that the transfer of control to the handler is done from anywhere inside the try block, or from anywhere inside any routine called from there, while the control transfer to an else clause comes from only one place, the evaluation of the predicate in the if clause.
The actual code to save the state of a global variable in a local variable is unremarkable, it is no different for exceptions than it would be for any other type of variable. Installing a handler is fairly simple too, involving simply storing the address of the handler and a pointer to the activation record.
; save old CONSTRAINT_ERROR exception in OLDCON in my AR LOAD R3,PCONERR LOAD R4,R3,EXHAND ; oldcon.exhand = constraint_error.exhand STORE R4,R2,OLDCON+EXHAND LOAD R4,R3,EXAR ; oldcon.exar = constraint_error.exar STORE R4,R2,OLDCON+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:
; restore old CONSTRAINT_ERROR exception from OLDCON in my AR LOAD R3,PCONERR LOAD R4,R2,OLDCON+EXHAND STORE R4,R3,EXHAND ; constraint_error.exhand = oldcon.exhand LOAD R4,R2,OLDCON+EXAR STORE R4,R3,EXAR ; constraint_error.exar = oldcon.exar |
Typically, the old handler would be restored immediately prior to a jump to the end of the exception handler, or alternatively, immediately prior to a return from the function. In any case, the initial code of the handler itself must also restore the previous handler. Now, we have the complete mechanism in place, allowing the following code to be used to transfer control to the exception handler:
LOAD R1,PCONERR 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:
BR MYHAND ; raise constraint_error locally |
Things are further simplified in the main program, since there is no previous handler for any exceptions declared there, there is no need to save the prevous handler on entry to the main program, nor is there any need to restore the previous handler at the end.
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 usually rely on things stored in its activation record, but there is no eacy 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 in its activation record its return address and anything else on which the exception handler relies.
Exercises
c) Write a Hawk main program that simply initializes the display, installs a default handler for CONSTRAINT_ERROR and then calls the external subroutine APPLICATION. The default 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 number of words in the exception variable and the names of the fields of this variable. Write a pair of subroutines that hide this information. The interface to these subroutines 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 number of words in the exception variable and the names of the fields of this variable. Write a pair of macros that can be included in the file exception.h that hide this information.
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. In this case, there is no sense in having the multiply routine handle exceptions, but because multiplication can easily produce a value too large to store in one word, it is quite appropriate to raise a constraint error when an oversized value is produced as a result.
MULTIPLY: ; link through R1 ; R3 = multiplier on entry, product on return ; R4 = multiplicand on entry, destroyed ; R5 = temporary copy of multiplier, destroyed ; uses no other registers MOVE R5,R3 ; move the multiplier CLR R3 ; product = 0; TESTR R5 BZS MULTLX ; if (multiplier != 0) { MULTLP: ; do { 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: ; } SL R4,1 ; multiplicand = multiplicand << 1; BCS RCONERR ; if carry set, raise constraint error TESTR R5 BZR MULTLP ; } while (multiplier != 0); MULTLX: ; } JUMPS R1 ; return product; RCONERR: ; common code for raising constraint error LOAD R1,PCONERR LOAD R2,R1,EXAR ; AR = constraint_error.exar LOAD R1,R1,EXHAND JUMPS R4 ; PC = constraint_error.exhand |
The above code illustrates something about exception handling. It is sometimes very easy to detect an exception; testing the overflow bit or the carry bit is frequently all that it takes, but then, there is a sequence of 4 instructions needed to actually raise the exception. This sequence is identical for all routines that may decide to raise a particular exception, so it is appropriate to write this block of code once and let all the different checks for this exception simply jump to this little block of code.
Suppose we translate the code for distance() from the start of this chapter to Hawk assembly language, and we use the above multiply routine to compute the squares required by this distance routine. The application needs to find and print the distance between two points. When this code works, we want the output to give the distance, for example, saying "the distance is 39 microns", but if there is an range-constraint exception, we want the output "the distance is too big". We can do this with the following code
; activation record format RA = 0 X1 = 4 ; saved parameters Y1 = 8 X2 = 12 Y2 = 16 ARSIZE = 20 OLDCON = ARSIZE ; save old constraint error handler ARSIZE = ARSIZE + EXSIZE SHOWDIST: ; on entry, R3 = x1 ; R4 = y1 ; R5 = x2 ; R6 = y2 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 LOAD R1,PDSPST ADDI R2,ARSIZE JSRS R1,R1 ; dspst( "the distance is " ); ADDI R2,-ARSIZE ; save old CONSTRAINT_ERROR exception in OLDCON in my AR LOAD R3,PCONERR LOAD R4,R3,EXHAND ; oldcon.exhand = constraint_error.exhand STORE R4,R2,OLDCON+EXHAND LOAD R4,R3,EXAR ; oldcon.exar = constraint_error.exar STORE R4,R2,OLDCON+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 LOAD R4,R2,Y1 LOAD R5,R2,X2 LOAD R6,R2,Y2 ADDI R2,ARSIZE JSR R1,DISTANCE ; R3 = distance( x1, y1, x2, y2 ); LOAD R1,PDSPDEC JSRS R1,R1 ; dspdec( R3 ); |
LEA R3,SDUNIT LOAD R1,PDSPST JSRS R1,R1 ; dspst( " microns" ); ADDI R2,-ARSIZE ; restore old CONSTRAINT_ERROR exception from OLDCON in my AR LOAD R3,PCONERR LOAD R4,R2,OLDCON+EXHAND 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 SDHAND: ; exception handler for showdist ; restore old CONSTRAINT_ERROR exception from OLDCON in my AR LOAD R3,PCONERR LOAD R4,R2,OLDCON+EXHAND 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 LOAD R1,PDSPST ADDI R2,ARSIZE JSRS R1,R1 ; dspst( "too big" ); ADDI R2,-ARSIZE ; code outside of exception handler SDDONE: LEA R3,SDCRLF LOAD R1,PDSPST ADDI R2,ARSIZE JSRS R1,R1 ; dspst( "\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 equivalent representations for exceptions. One could, for example, represent an exception with a global variable that was a simple pointer to a local variable in the block that has installed the current exception handler. That local variable, in turn, would hold the address of the handler, the address of the activation record, and the previous value of the global pointer.
Exercises
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. There are still some extra increments and decrements of R2 included in this code; they are there for clarity. Find and eliminate them.
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 any changes you need to make because of any difference in the exception handling model of your target language.
i) Work out the code for saving the old handler and installing a new one, the code for restoring the old handler, and the code for raising an exception, using the alternative representation for exceptions suggested at the end of the section above. Does this alternative require more or less memory? Does this alternative make installing and de-installing handlers faster or slower? Does this alternative make raising exceptions faster or slower?
While the overflow and carry bits in the condition codes of the Hawk and similar machines such as the Pentium can be used to detect exceptions in integer arithmetic operations, the most important exception detection mechanisms of these machines center around detecting exceptions caused by illegal instructions, illegal memory references, and similar faults in the program. Most computer systems detect some or all of the following special conditions:
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 memory location. Following an uninitialized or null pointer usually causes such a fault. |
Illegal Instruction | An instruction was executed that is not defined in the instruction set of this computer. Accidentally jumping to an area of memory that does not contain code usually causes such a fault. |
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 set to permit them. |
In general, the central processors of modern computers have no understanding of the exception handling mechanisms of the programming languages being used. Instead, the central processor has a completely different model for handling these exceptions, referred to as a trap mechanism. Trap mechanisms were introduced on computers of the 1950s and 1960s, well before programming languages had reasonable exception processing models, and in almost all cases, it is the operating system that handles traps, not the applicaton program.
In the case of the Hawk, traps operate as follows: First, the instruction that caused the trap is aborted. All traps can be traced back to the execution of a specific instruction, the instruction that caused the trap. The address of this program in memory is saved in a special register within the Hawk processor, the TPC or trap program counter. In the case that the trap involved an illegal memory address, the address that caused the trap is saved in a second register, the TMA or trap memory address register. The level field of the processor status word is also saved in a special field, the old level field, and once all this information is saved, the program counter is set to a value determined by the nature of the trap, and the level field of the processor status word is set to zero (the most permissive level).
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 processor guarantees that traps will always be detected before an instruction has a chance to change any of the registers within the processor. Therefore, between the old level field of the processor status word, the TPC register and the contents of registers 1 to 15, everything is just as it was immediately prior to executing the instruction that caused the trap.
When a trap occurs, the new value of the program counter is set to a value that depends on the cause of the trap. Each component of the processor that is involved in detecting traps may provide a 4-bit code; this code is provides bits 4 to 7 of the new value of the program counter, 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 machine. The following locations in the trap vector are used by the trap hardware described here:
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 orr 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, a topic we will discuss after dealing with traps.
The final tools we need for dealing with traps are tools for examining and setting 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, so, for example, CPUGET R4,TPC gets the trap program counter register into register 4, and CPUSET R4,PSW sets the processor status word to the contents of register 4. These special instructions have the potential to access up to 16 distinct special registers within the Hawk processor. In commercial processors, special registers are frequently included for diagnostic purposes, and sometimes, the interfaces for devices closely allied to the processor are included here. In the Hawk, 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, it is essential.
There is one important feature of the CPUGET instruction: When it is used to get a special 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 would be to completely undo the effects of the trap and try, again, to execute the instruction that caused the trap. Normally, the trap service routine would, of course, do more than this, since retrying the instruction that caused the trap would just cause the trap again, hardly an interesting thing to do!
Exercises
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 with an inappropriate level? A complete and adequate answer to this question rests on the fact that the level field is also used to control other features of the processor that we have yet to discuss. All you need to know about these is that they are essential features of a secure system.
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 is enough to help in debugging your program, but if your program needs to handle this exception, it is not enough. To handle an exception, you need to install code in the appropriate location in the trap vector to jump to your own trap handler, and 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:
. = #10 ; bus error entry in the trap vector LOAD R1,PBUSER JUMPS R1 ; go to rest of handler ALIGN 4 PBUSER: W BUSERR ; pointer to the rest of the bus error code |
The weakness of this minimalist approach is that it prevents us from writing a trap handler that displays the contents of all of the registers. The Hawk monitor gets around this by using the trap-save register, TSV, to save the contents of one register before it uses that register to jump to the trap service routine. It is important to remember that the TSV register is never used by applications programs, but only in the context of trap handlers and similar code, so we never need to save and restore the old contents of TSV.
. = #10 ; bus error entry in the trap vector CPUSET R1,TSV ; save R1 LOAD R1,PBUSER JUMPS R1 ; go to rest of handler ALIGN 4 PBUSER: W BUSERR ; pointer to the rest of the bus error code |
The second version of the trap vector code given here uses 8 bytes for instructions and 4 bytes for the word holding the address of BUSERR, the remainder of our code. There is room to squeeze in two 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 a null pointer, so logically, following an unitialized or random-valued pointer ought to raise a similar exception.
COMMON CONSTRAINT_ERROR,EXSIZE PCONER: W CONSTRAINT_ERROR BUSERR: ; intercept bus error exceptions LOAD R1,PCONER ; setup to raise CONSTRAINT_ERROR LOAD R2,R1,EXAR ; R2 = CONSTRAINT_ERROR.EXAR LOAD R1,R1,EXHAND CPUSET R1,TPC CPUGET R0,TPC ; PC = CONSTRAINT_ERROR.EXHAND ; 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 will be illustrated in the next section.
Exercises
l) Modify the bus error trap handler code given above so that it saves copies of all of the registers that it modifies in a common block called TRAPSAVE, including the copy of register one that was previously saved in the TSV register. Trap handlers can then recover this information if it is needed, for example, for debugging.
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 trap handlers, not hardware.
The term virtual machine borrows from terminology originally used in classical optics. In optics, systems of mirrors and lenses may cast several images. Some of these are real images, in the sense that if you put a sheet of film where the image appears to be, the film will capture that image as a photograph. Other images are said to be virtual images; this means that they look like images, but when you put film at the apparent location of the image, it will capture nothing. Virtual images are always seen through lenses, reflected in mirrors, or behind holograms.
In the same sense, a virtual machine looks, from the programmer's perspective, like a real machine, but it is an artifact created by the cooperation of some software with a real machine. Some virtual machines are created entirely by software! The Hawk emulator is an example, and so is an IBM PC emulator that runs on an Apple Mac. Other virtual machines are mixtures of real hardware and softwarer; these are created using trap handlers.
In the Hawk, there are several unimplemented instructions; if the opcode for one of these is used, the result is an illegal instruction trap. In addition, if the level field of the processor status word is 11112, use of the CPUSET and CPUGET instructions causes privilege violation traps.
Suppose we wanted to use the CPUGET opcode as a multiply instruction. To do this, we must install a new privilege violation handler. Because our software multiplication routine needs many registers, we will save everything on entry to the trap service routine and then restore it on exit.
COMMON SAVEREGS,17<<2 ; save area for registers PCSAVE = 0 ; displacements within save area R1SAVE = 1<<2 R2SAVE = 2<<2 R3SAVE = 3<<2 R4SAVE = 4<<2 R5SAVE = 5<<2 R6SAVE = 6<<2 R7SAVE = 7<<2 R8SAVE = 8<<2 R9SAVE = 9<<2 RASAVE = 10<<2 RBSAVE = 11<<2 RCSAVE = 12<<2 RDSAVE = 13<<2 RESAVE = 14<<2 RFSAVE = 15<<2 PSWSAVE = 16<<2 |
The code to save registers in this register save area begins in the trap vector; this code loads register 2 with a pointer to the register save area so that it can save register 1, and then it loads register 1 with the address of the remainder of the handler. The pointers needed by this code and any other trap vector code should be grouped at the end of the trap vector:
. = #30 ; privilege violation trap vector entry CPUSET R2,TSV ; save R1 temporarily LOAD R2,PSAVER STORE R1,R2,R1SAVE ; save R2 properly LOAD R1,PPRIVH JUMPS R1 ; go to the handler ; the above code occupies exactly 16 bytes! . = #100 ; the end of the trap vector PSAVER: W SAVEREGS PPRIVH:W PRIVHAND |
The remainder of the privilege violation trap handler is closely tied to this code, since, on entry, it must assume that only register 1 has been properly saved, and that register 2 is still carelessly saved in the trap save register. Even the condition codes are still un-saved and vulnerable to any instruction that might change them! The remainder of the job of saving registers is done as follows:
; privilege violation trap handler PRIVHAND: ; on entry, R2 points to the register save area ; R1 has been saved ; TSV still holds the saved 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 R6,R2,R6SAVE STORE R7,R2,R7SAVE STORE R8,R2,R8SAVE STORE R9,R2,R9SAVE STORE R10,R2,RASAVE STORE R11,R2,RBSAVE STORE R12,R2,RCSAVE 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, let us focus on the problem of returning from the trap! We do this by restoring the registers, and then, very carefully, we end by using the CPUSET and CPUGET instrucitons to put the program counter and processor status word back.
; return from any trap handler TRAPEXIT: ; on entry, R2 points to register save area LOAD R15,R2,RFSAVE ; start restoring registers LOAD R14,R2,RESAVE LOAD R13,R2,RDSAVE LOAD R12,R2,RCSAVE LOAD R11,R2,RBSAVE LOAD R10,R2,RASAVE LOAD R9,R2,R9SAVE LOAD R8,R2,R8SAVE LOAD R7,R2,R7SAVE LOAD R6,R2,R6SAVE 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 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! |
Now, we are ready to give the middle block of code that fits between saving the registers and restoring them. This block of code does the actual work of our virtual machine when the hardware detects and traps the use of the CPUGET instruction. First, the trap service routine must find what instruction was attempted? If it was not CPUGET, we should raise an exception.
; see if the protection violation was CPUGET ; all registers have been saved ; R2 points to register save area LOAD R3,R2,PCSAVE ; get the saved program counter LOADS R4,R3 EXTH R5,R4,R3 ; the the halfword it points to ; R4 is the instruction that caused the trap! LIL R6,#F0F0 AND R5,R6 ; clear all but the opcode bits CMPI R5,OPCPUGET ; is it a CPUGET instruction? BEQ ISCPUGET LOAD R3,R2,PSWSAVE ; it is not CPUGET! CPUSET R3,PSW ; restore saved PSW LOAD R1,PPROGERR LOAD R2,R1,EXAR LOAD R1,R1,EXHAND CPUSET R1,TPC CPUGET R0,TPC ; raise PROGRAM_ERROR exception |
In the above code, once we separated out the instructions that we intend to emulate, adding them to the instruction set of the user's virtual machine, the remaining protection violations are signalled using the PROGRAM_ERROR exception. In the unlikely event that the user installs a handler for this exception, the user program can recover, but it would be a good idea if the default handler printed out the registers and halted in order to help the user do some debugging.
With all of the above pieces in place, we can now extend the user's virtual machine by writing the code that converts CPUGET instructions into multiply instructions. This code begins by getting copies of the user's source and destination registers, and then it multiplies them before returning the result to the user's destination register. In addition, the trap handler must increment the saved program counter before it returns.
ISCPUGET: ; protection violation caused by CPUGET ; R2 points to register save area ; R3 is the saved program counter ; R4 is the word pointed to by PC EXTH R5,R4,R3 ; get the instruction EXTH R6,R4,R3 ; get the instruction (again) SR R5,8 TRUNC R5,4 ; R5 is the dst register number TRUNC R6,4 ; R6 is the src register number ADDSI R3,2 STORES 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 ... STORES R3,R5 ; update the saved dst register JUMP TRAPEXIT ; go return to user |
Now that we have defined a multiply instruction, we also need to extend our assembly language with a multiply macro! This will look something like the following:
MACRO TIMES =src,=dst H #1010 | ((dst-R0) << 8) | (src-R0) ENDMAC |
In this macro, we could have used dst and src instead of dst-R0 and src-R0, but 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. The result is better error checking at assembly time.
Exercises
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 that are built into the monitor. Some of these routines need to use R2 as a stack pointer. What single line of code in the above discussion of trap handlers would you have to change in order to allow this! (Hint: We used R2 as a pointer to the register save area for a very good 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) Write a handler for the illegal instruction trap that recognizes the two unimplemented memory reference instructions and turns one of them into add register to memory, emulating the full indexed addressing model of the Hawk in determining the address of the word in memory that will be added to.
The mechanisms we have described above for trap handling serve a second purpose on essentially all modern computers, and that is handling external events signalled by input-output devices. When these mechanisms are triggered by an external device, we refer to the event as an interrupt, not a trap, but the mechanisms for handling these events are very similar.
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:
int trapvector, interruptvector; while (TRUE) do { try { fetch_and_execute_one_instruction(); } 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, if execution of an instruction raises no exceptions and if no external device requests an interrupt, the complexity at the end of this code does nothing, so it is equivalent to the naieve view of the fetch-execute cycle. If that instruction raises a trap, however, or if an external device requests an interrupt, the story is different.
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 interrupt the central processor when the deivice is ready to perform an input or output operation and only when the program running on the central processor is ready to deal with this condition. Typically, we use the ready bit in the device status register to determine when the device will attempt to request an interrupt, but we design the device so that this request will only be made if the interrupt is enabled. The Hawk keyboard interface register logic for this is typical:
On all modern machines, there are hierarchies of interrupt enable bits. Not only do we include an interrupt enable bit in the interface logic for each device, but we also have global interrupt enable rules. In the case of the Hawk, the global rules are determined by the contents of the level field of the processor status word. If this field is 00002, all interrupts are disabled, while if this field is 11112, all interrupts are enabled. Intermediate values of this field enable some interrupts and disable others.
Most modern processor designs include something equivalent to the Hawk level field to determine the current interrupt priority at which the system is executing. Frequently, the processor hardware has a set of outputs that directly report the current level to external logic, and it is up to that logic to give meaning to these bits. In the case of the Hawk, there are two sensible ways of doing this. First, each bit of the level field could be used to enable one group of related devices. In that case, we can think in terms of 5 levels, encoded as 00002, 00012, 00112, 01112, and 11112. This allows the simplest interface hardware, and is suitable only for systems with only a few devices that can request interrupts.
The other approach is to add an external priority interrupt decoder, so that we have 16 levels, encoded as a 4-bit binary number. Mixtures of these schemes are perfectly possible, in which, for example the most significant bit of the level field is used to enable one particular device, while the least significant 3 bits are decoded to create 8 different interrupt levels. In practice, this latter approach is highly likely, since 8-way priority interrupt support chips are widely available, and since we can easily set aside trap vector entries 8 to 15, at addresses 8016 to F016 to handle interrupts from these devices.
Interrupt priority involves two distinct issues: First, if two distinct devices request interrupts at the same time, which device wins, and second, what if one interrupt service routine is running when a second device requests an interrupt. The first issue, that of deciding which interrupt to service when multiple requests are simultaneous, is always solved entirely in hardware. The second issue involves software.
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 should 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.
Exercises
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.