Using the TRAP instruction

I was in the middle of a disassembly project (more on that in future posts!) but I encountered this discrete issue and I thought it would be worth a specific post.

Background: Interrupt handling

In normal operation the CPU is executing a series of instructions representing whatever program has been loaded into memory. Then an event happens - maybe a timer expires, data becomes available from an I/O device or hardware error takes place. The event needs to get the CPU's attention and the way it does this is by generating an interrupt.

The CPU now needs to decide whether the event that has taken place has sufficiently high priority for it to stop what it is doing and handle the interrupt. To achieve this the CPU has an execution priority, which is set in the Processor Status Word (bits 5-7). The CPU execution priority can be set by the code that is currently running.

The incoming interrupt also has a priority. If the priority of the incoming interrupt is greater than the current CPU priority, the CPU will stop whatever it was doing and deal with the interrupt.

The CPU cannot be interrupted mid-instruction. Therefore, interrupt handling only takes place between the execution of two instructions. To handle the interrupt the CPU pushes the current value of the Program Counter (PC) and the Program Status Word (PSW) onto the stack. It then loads a new PC and PSW from a location in memory known as an interrupt vector.

The location of the interrupt vector depends on the type of interrupt that has taken place. For some interrupts, such as hardware errors, the interrupt vectors are fixed. On the PDP-11 Programming Card, for example, you can see some of the standard interrupt vector locations:

Interrupts generated by external I/O devices are often configurable, with standard defaults. For example, the paper tape reader uses, by default, interrupt vector 070, although that can be configured with jumpers on the physical device.

So, the CPU loads the PC and PSW from the interrupt vector, jumps to the location in memory specified there, and starts executing code. This code is the interrupt handling routine. Once the interrupt handling is complete, as indicated by the RTT ("Return from Trap") instruction in the interrupt handling routine, the CPU will pop the previous PC and PSW values from the stack and resume executing whatever it was doing before the interrupt occurred.

What is the TRAP instruction used for?

You always hear TRAPs being referred to as software interrupts. But what does that actually mean?

The bit that a TRAP and an interrupt have in common is that they both interrupt the flow of the currently executing code. The difference is that an interrupt arises asynchronously, when an external event happens, triggering the interruption, whereas a software TRAP is generated synchronously within by the code itself.

I imagine a software TRAP is like the currently executing code saying to the CPU "I want you to interrupt my execution, go and do a certain task, and then come back and continue executing." In this regard, a software TRAP is actually quite a lot like a system call in C. In C, for example, if you use the "open()" system call, it's a bit like you are telling the kernel "I want you to interrupt my execution, go and open a file, then come back and continue executing." That's what a software TRAP is used for.

The structure of the TRAP instruction(s)?

The TRAP instructions have opcodes from 104400 to 104777. In other words, they are all of the form (in binary) "1 000 100 1xx xxx xxx".

In code, you will see this is written as:

TRAP 2 
; (opcode = 1 000 100 100 000 010)
TRAP 72 
; (opcode = 1 000 100 100 111 010)

When a TRAP is executed, here are the set of operations that are carried out:

1. The Stack Pointer (SP) is decremented and the current value of the Processor Status Word (PSW) is assigned to the address pointed to by the stack pointer.

2. The SP is decremented again and the current value of the Program Counter (PC) is assigned to the address pointed to by the stack pointer.

3. The TRAP vector address is 34, so the content of memory address 34 is moved to the PC.

4. The second part of the TRAP vector, the PSW value, is at address 36, so the content of address 36 is moved to the PSW.

5. Execution will continue at the address from the TRAP vector, which is now in the PC.

Here, now, is the question that has given rise to this entire post:

It is reasonable to assume that a programmer expected something different to happen when they wrote "TRAP 2" as opposed to when they wrote "TRAP 72" in their code, but there is only one TRAP vector, at address 34. How does the TRAP vector take into account the "parameter" with which the software TRAP was invoked?

Using the TRAP "parameter"

The only place that the TRAP "parameter" is available is in the opcode of the instruction. Here is some sample code that will get the TRAP "parameter":

D 000034 000100
D 000036 000000
...
D 000100 MOV (SP), R0
D 000102 SUB #2, R0
D 000106 MOV (R0), R1
D 000110 BIC #177400, R1
D 000114 RTT
...
D 1000 NOP
D 1002 TRAP 0
D 1004 NOP
D 1006 TRAP 2
D 1010 NOP
D 1012 TRAP 32
D 1014 NOP
...

The main code starts at address 1000:

D 1000 NOP
D 1002 TRAP 0
D 1004 NOP
D 1006 TRAP 2
D 1010 NOP
D 1012 TRAP 32
D 1014 NOP

For the purposes of this example there are three TRAP instructions with a NOP in between each one. This is meant to represent the main code that the CPU is executing. When a TRAP is encountered the CPU stops executing this code, pushes the PSW onto the stack, pushes the PC onto the stack and then loads the PC and PSW with the value found in the TRAP vector.

These two lines set up the TRAP vector:

D 000034 000100
D 000036 000000

Address 000034 contains the address that is placed in the PC when a TRAP instruction is encountered. Note that the TRAP handling routine can be found at address 100:

D 000100 MOV (SP), R0
D 000102 SUB #2, R0
D 000106 MOV (R0), R1
D 000110 BIC #177400, R1
D 000114 RTT 

When the code at at 000100 starts running, the stack pointer points at the address of the instruction after the TRAP instruction. In the case of the "TRAP 0" the value 1004 will be on the stack.

D 000100 MOV (SP), R0

The first instruction moves the stack pointer value (1004) into register R0.

D 000102 SUB #2, R0

Next, two is substracted from the value in R0. It now contains the memory address of the TRAP instruction (i.e. 1002).

D 000106 MOV (R0), R1

The next instruction moves the value from the memory address contained in R0 into R1. R1 will now contain the opcode of the TRAP instruction (i.e. 104400).

D 000110 BIC #177400, R1

The next instruction clears all bits in the instruction except the lower byte, that contains the TRAP "parameter" value.

D 000114 RTT 

R1 now contains the TRAP "parameter", which could now be used to branch based on its value, for example. In this case, I just return from the trap handling routine. This will return to the NOP instruction after the "TRAP 0". For testing purposes, I added two more TRAPs to make sure the code worked as it should. In each case the TRAP "parameter" is correctly stored in R1, as expected.

A really cool way of handling TRAPs

I have been working on disassembling the PDP-11 BASIC code and TRAPs are used extensively in that code. The TRAP handling is done in a really interesting way that I'd like to describe here.

These are the relevant instructions:

000034 000100 
000036 000000 
...
000100 011666 MOV (SP), 2(SP)
000104 162716 SUB #2, (SP)
000110 013646 MOV @(SP)+, -(SP)
000112 006216 ASR (SP)
000114 103404 BCS 126
000116 006316 ASL (SP)
000120 062716 ADD #73654, (SP)
000124 013607 MOV @(SP)+, PC
000126 ...
...
000254 000476 
000256 000574 
...

As far as I can tell idea here is that there are subroutines at various locations throughout the code that the programmer wants to invoke via TRAP calls.

Normally an trap handling routine needs to end with an "RTT" instruction, to Return from Trap. The RTT instruction will restore the PC and PSW that were pushed onto the stack when the TRAP instruction was executed. However, subroutines elsewhere in the code are going to end with an "RTS" instruction, to Return from Subroutine. This will only restore a single register value from the stack, rather than two. One of the cool things about this technique is that it allows subroutine code to be used as subroutines but also as TRAP handling routines.

Let's talk through the code.

000034 000100 
000036 000000 

These first two lines are the TRAP vector. This means that whenever a TRAP instruction is executed, the PC is loaded with the value 000100 and the PSW is loaded with the value 000000.

Before any code is executed, let's think about the situation on the stack:

1. SP points at the PC return address (i.e. the PC of the instruction immediately after the TRAP instruction we are currently executing).

2. The previous stack entry (i.e. at SP+2) is the PSW that was stored before the TRAP moved the value at 000036 into the PSW.

000100 011666 MOV (SP), 2(SP)

This first instruction moves the value at the address pointed to by SP, to the address SP+2. In other words, it overwrites the stored PSW value with another copy of the PC return address. We now have two copies of the PC return address on the stack.

000104 162716 SUB #2, (SP)

Now, subtract 2 from the PC return address pointed to by SP. This will make the value in the address pointed to by SP point at the TRAP instruction. The stack now looks like this:

1. SP points at the memory address of the TRAP instruction we are executing.

2. The previous stack entry (at SP+2) points at the PC return address (the address after the TRAP instruction).

000110 013646 MOV @(SP)+, -(SP)

This instruction does loads, so I'll break it down like this:

1. Get the value stored at the memory location stored in SP. This is the TRAP instruction opcode.

2. Increment SP after reading the value, so now SP points at the PC return address (the value that used to contain the PSW).

3. Decrement the SP again, so now SP points at the memory address of the TRAP instruction and store the TRAP instruction opcode there.

So now the stack looks like this:

1. SP points at the TRAP instruction opcode

2. The previous stack entry (at SP+2) points at the PC return address (the address after the TRAP instruction)

000112 006216 ASR (SP)
000114 103404 BCS 126

Shift the value in the memory address pointed to by the stack pointer (i.e. the TRAP opcode) to the right. If it was odd a 1 will be moved into the Carry Flag. The BCS will then jump to address 126.

This means that only even TRAP values are handled using the example code I am talking about here (NOTE: this is an excerpt so there is more to this code than I have included here).

000116 006316 ASL (SP)

We have now confirmed that the TRAP "parameter" is even, we shift the value to the right to restore its value.

000120 062716 ADD #73654, (SP)

Now a constant value is added onto the memory address pointed to by the stack pointer.

Let's add this to a few sample values and see what happens.

1. "TRAP 0" has opcode 104400. If you add 73654 to this you get 200254. This value is too big to fit in the register, so it will overflow and you'll be left with 000254.

2. "TRAP 2" has opcode 104402. If you add 73654 to this you get 200256. Again, this will overflow and you'll be left with the value 000256.

The pattern should be pretty clear; for each even TRAP "parameter" value, this addition will place a word value, starting at address 254, into the memory address pointed to by SP.

000124 013607 MOV @(SP)+, PC

Now, the last instruction takes the value of the memory address contained in the stack pointer and places it in the program counter. The SP is incremented so now it points at the PC return address, which we stored in the memory location that used to contain the PSW.

If we take a quick look at a couple of memory addresses:

000254 000476 
000256 000574 

The value at address 254 contains the memory address of the subroutine to be executed when TRAP 0 is invoked, the value at address 256 contains the memory address of the subroutine to be executed when TRAP 2 is invoked, and so on.

What this code has implemented (with eight assembly language instructions!!!!) is, in effect, a table of function pointers, starting at address 000254, that consist of subroutines throughout the code and are invoked based on the TRAP "parameter".

When those subroutines are finished, they all end with "RTS PC" which means that the PC value from the stack (at the location where we overwrote the PSW) will be used as the return address and placed back into the PC, so that the original execution can continue.

Isn't that so cool!? Or maybe it's just me!

The EMT instruction

The examples I have provided here have been based on the TRAP instruction, but the exact same techniques can be used with the EMT ("Emulator Trap") instruction. However, if you look at PDP documentation (e.g. the PDP11/70 Handbook) it notes that EMT is often used by DEC software, so the TRAP function is recommended for general use.