Fault Braindump
Home ] Up ] New Stuff ] Minix Port ] Magic-2? ] Overview ] Photo Gallery ] Construction ] Technical Info ] My Other Projects ] Links ]

Fault/Interrupt brain dump, 12/18/2001

Lately, I've been trying to wrap my brain around how to handle traps and interrupts - largely without success. I think I've got a bit of a mental block here. I can see the general outline, but am having trouble internalizing all of the details - which, in this case, I think are critical to nail down.

Anway, here goes a brain dump of where I am (in the hopes that writing it down will move me closer to a reasonable solution).

Overview:

The M-1 microcode engine operates as an endless loop whose flow is determined by the instruction stream. However, there are times when we want to break out of that endless loop - for interrupts and faults. Interrupts are requests for attention by devices outside of the CPU, whereas fault represent situations in which something has happened during the execution of an instruction that prevents further progress. Interrupts can arrive at any time (hence, "asynchronous"), whereas faults happen at specific times ("synchronous").

Here's a cut at what kind of faults M-1 should expect to see:

Page not present ; fault Page not writeable ; fault Overflow ; fault Breakpoint ; fault Privilege violation ; fault

As for interrupts, these will largely correspond to outside devices:

Heartbeat timer ; interrupt Serial port ; interrupt (1 or more) Hard drive ; interrupt (1 or more) Keyboard ; interrupt (maybe, may poll instead) ...

When one of these events occurs, we need to stop processing normal instruction, save the current state of the machine (so we can resume later), and then branch off to some special code to service the event.

[Sideline note: There's also the syscall instruction, which will be implemented as a flavor of fault. This instruction must cause a transition into supervisor mode, which faults and interrupts automatically do. A difference between syscall and normal faults is that when we return after processing a syscall, we want to return to the instruction following the sysceall op.]

Now, let's look at these things in more detail.

Faults:

As mentioned earlier, a fault may occur during processing of an instruction. When an instruction faults, we need to be able to recreate the machine state as it occurred before the faulting instruction begain executing. [Note: an exception here is when we fault half-way through a 16-bit store. We won't attempt to undo the memory change].

For example, if we take a page fault while executing a "POP A", we want to be able to service the page fault, and then re-execute the "POP A", hopefully this time successfully. This means we need to and be able to either suppress changes to any other register state once the faulting situation is detected or save backup-copies of changed state. The M-1 features backup registers for PC and SP. During the fetch cycle of each instruction, the starting values of PC and SP are saved. Then, during execution we can freely update PC and SP. Other registers, however, are not saved. So, we must ensure that we don't change anything until after we have successfully handled all potentially-faulting microinstructions.

An example of the above in action is the microcode for 16-bit loads into the accumulator. Because M-1 features an 8-bit data bus, we must do the load in two 8-bit chunks. One way of writing the microcode for the load would be to load the low byte, latch it into the low byte of A, then increment the MAR, load the second byte and latch it into the high byte of A. However, what happens if the load is across a page boundary and we take a page fault on the high-byte load? In this case, we will have already written the low byte of A - which is illegal. To solve this particular case, we latch the low byte into the TA register, and then load the high byte and latch the high byte into A and the low byte from TA into A at the same time. The complete the solution, we further require that the "latch" signal which causes A to take its new value is suppressed whenever a fault occurs.

In more detail, all faults must be detected during the first half of the system clock. With a few exception, all latch signals (which occur midway through the system clock cycle) are to be AND'd with ~FAULT.

Interrupts:

Interrupts are much like faults in the general actions that need to be taken. However, the big difference is that interrupts don't require immediate action to be taken. Rather then worry about the complexity of trying to deal with the possibility of interrupting an instruction's executation at any point, we can choose to only take interrupts between instruction executions. And, that is what we do. M-1 will only look to see if an interrupt is pending immediately before a fetch microinstruction is executed. The fetch microinstruction is located at microcode address 0x00. Thus, the condition for taking an interrupt is:

2nd half of system clock (which is responsible for identifying next microinstructin to execute) AND current_microinstruction.next == &fetch (0x00) AND interrupt_pending == TRUE.

When these conditions are met, the microinstruction sequencer reroutes microinstruction execution to go to the interrupt-handling microcode rather than fetch.

Simplifications

Now, given that faults and interrupts are similar, we'd really like to be able to build a single mechanism for handling them. To handle the microinstruction control, we can do this fairly simply. Note that the big difference in faults and interrupts is that faults must take effect immediately, whereas interrupts can be deferred to in-between instruction execution. The solution here is to cause faults to immedately abort further microexecution and go directly to an "in between" instruction state, where we look for both faults and interrupts.

The way this is done is to clear the "next" field of the current microinstruction. Since the fetch microinstruction address is zero, this is equivalent to:

if (fault_detected){ 
    fault_pending = TRUE; 
    current_microinstruction.next = &fetch; (0x00) 
}

Now, combining this with the above, our system clock cycles looks something like:

**** Falling edge of system clock 

bulletNew control signals latched onto control lines, enabling data from registers, memory and ALUs to flow onto internal busses.

**** 1st half of system clock 

bulletFault condition detected.

**** Rising edge of system clock 

bulletif (fault_detected) { fault_pending = TRUE; current_microinstruction.next = &fetch; // (0x00) }
bulletif ((system_clock && !FAULT) && current_microinstruction.register[x].latch) { latch_results(x); }

**** Second half of system clock 

bulletMPC = current_microinstruction.next; // MPC -> Microcode PC 
bulletIf (MPC == &next) { if (fault_pending) MPC = &fault_handling_microcode else if (interrupt_pending) MPC = &interrupt_handling_microcode } 
bulletFetch microcode instruction from MicrocodeStore[MPC] and generate new control signals.

One other little twist here is that we also need the ability to prevent both traps and interrupts from happening during critical periods (including handling traps and interrupts). As far as traps go, we can simply require the OS programmer to ensure that trap and interrupts handlers cannot themselves trap. For interrupts, though, we need to have a special mechanism to prevent their arrival. What we do is introduce an interrupt disable control bit (which lives in the FLAGS register (or MSR, if I decide to keep it). We'll deal with the logic of interrupt suppression shortly, and merely assert that for the above we assume that "interrupt_pending" really means that we have an interrupt request and interrupts are not currently suppressed. Also, most real architectures have the ability to have maskable and non-maskable interrupts. I'm going to skip non-maskable. They're mostly used for power-fail recovery, and I don't care much about that.

To implement this with a minimum of logic, I'm going to play some games. We will use 7 74273 octal D flip-flops to hold the current microinstruction word. These parts have asynchronous clear lines that will be tied to the fault logic. When a fault is detected during the first half of the system clock, all control signals will be cleared. This will force us to go to fetch next, as well as deassert any latch control bits - thus preventing any unwanted register changes. [NOTE: also for the power-on reset circuitry, I require that a microcode instruction of all zeros must be effectively a nop that branches to fetch.]

*PROBLEMS*:

First, this scheme places a constraint on the execution circuitry such that we need to be able to detect a fault early enough that the new microcode signals have a chance to propogate through the field decoders to deassert any latch signals. This is probably not a big deal, now that I think about it. The memory address was placed in the MAR in the previous instructinon, so the fault detection will have already taken place. We need only AND the page not present/invalid write detected with the current instruction's READ/WRITE bits to generate memory faults. For programmatic faults such as break and syscall, we can sidestep the problem by having them just jump directly to the appropriate fault microcode. Trap on overflow is similar, only with a conditional branch.

The second problem is more serious. If we are asynchronously clearing the current microinstruction whenever we detect a fault at any time during the first half of the system clock, we might spuriously detect what looks like a faulting condition but in reality is just some signals bouncing around during the early signal settling time. Ouch. Let me think about this one for a while.

*SOLUTIONS*:

Okay, maybe I can solve spurious fault detection as follows:

Instead of suppressing results getting latched by clearing the current microinstruction word and thus deasserting the individual latch signals, why don't I instead prevent the rising edge of the system clock from showing up. For example, instead of:

if (current_microinstructin.latch_A && system_clock.rising_edge) A = new_value

we tie a copy of the system clock to the fault detection bit:

if (current_microinstruction.latch_A && (system_clock.rising_edge && !fault_detected)) A = new_value

Also, we will still use the trick to clear the next field of the microinstruction, but that will happen on the system clock's rising edge (which will ensure that the fault detection bit is stable). So

if (system_clock.rising_edge && fault_detected) current_microinstruction.next = 0;

Yes, this seems much better. The value of the fault-detected bit is only important starting at what would be the rising edge of the system clock. By then all important signals will be stable. We'll need to duplicate the system clock to have one copy that runs to latch circuitry, and the other for everything else that doesn't need latch suppression on fault. Also, we'll need to sure that the fault-pending bit is cleared before the next system clock rising edge.

Good. Now, back to implementation details. I think I can further simplify the logic in the microinstruction sequencer which changes microexecution from from fetch (0x00) to the fault/exception-handling microcode. First, we reserve microcode locations 1, 2 and 3. Now, we change the logic as follows:

MPC = MPC | ((MPC==0) && (fault_pending | interrupt_pending))

where fault_pending is either 2 or 0, and interrupt_pending is either 1 or 0. This will yield the following possibilities:

MPC != fetch => goto MPC MPC == fetch, fault_pending == 0, interrupt_pending == 0 => goto fetch (address 0) MPC == fetch, fault_pending == 0, interrupt_pending == 1 => goto 1 (handle interrupt) MPC == fetch, fault_pending == 2, interrupt_pending == 0 => goto 2 (handle fault) MPC == fetch, fault_pending == 2, interrupt_pending == 1 => goto 3 (handle interrupt with fault pending)

Note that in case 3, which has both a fault and interrupt pending, we choose to handle the interrupt. We could probably do this either way, but I think this will be cleaner. The interrupt is asking for attention, and the fault will be there to be re-raised when we return. Note, though, that we can't just use the "handle interrupt" microcode entry directly as we must first roll back SP and PC to their beginning values because fault has left us in an intermediate state.

The Hard Part

Well, the previous discussion covered what I consider the easy part. Now we've got to deal with interrupt/trap priority, what the external interrupt line (or lines) look like, how we acknowledge interrupts, how we vector to the appropriate interrupt handler, and finally how (or if) we can fit DMA in into this scheme cheaply.

Priority

We need to prioritize interrupts and traps. Some devices need immediate servicing, while other can wait. On the fault side, it is possible to have multiple traps in one situation: a page that is not present is also not writeable. In this case, the not present fault is the one that matters and it should take priority.

There's a nice TTL device, the 74148, that seems to be designed for this sort of thing - the priority encoder. It has eight input lines, and reports the number of the highest order active line (as well as an output saying whether any lines are active). So, we can simply hook up our fault detect and interrupt request lines to these devices. I'll envision one 74148 for faults, and another for interrupts. The "data present" outputs will be "fault_pending" and "interrupt_pending", and the priority codes can be used to construct the interrupt/fault handler vector address. We can do something like have vectors 0..7 be for faults, and 8..15 be for interrupts. As far at the block diagram goes, we can have some enable that cause either the fault or the priority encoder to jam the four bits representing the fault/interrupt into bits 10-13 of IVEC_base (driving bits 14 & 15 to be 0). To simply life, we can require that IVEC_base must be 256-byte aligned, and we construct the lower byte of the address using the encoder outputs. Thus, the interrupt handler address is construted as follows:

bits 0-7 : IVEC_base bits 8-9 : Always 0 bit 10 : 0 if fault, 1 if interrupt bits 11-13 : Output of 1 of 2 priority encoders (mux'd on bit 10) bits 14-15 : Always 0

For example, to do a page fault transition, we'd:

o Copy MAR to TA o Copy SSP to SP o Set mode to supervisor o Push TSP onto system stack o Push TPC onto system stack o Push A onto system stack o Push TA (i.e. - the faulting address) onto system stack o Push FLAGS onto system stack o Copy IVEC_base/fault bits into PC and MAR o Goto fetch

Hmm - here's an idea. I need to be able to distinguish between memory faults that are using the supervisor page table vs. those using the user page table. Perhaps I can use bit 9 above to distingish them. In this way, I'll have separate vectors for user and supervisor memory faults. That will save me from having to check in the handler, and also might make the logic simpler (since I don't have to save that bit in FLAGS or the MSW - which I'm hoping I can drop).

Okay, back to the design....

Where I start getting really fuzzy, is on the circuitry on the other side of the interrupt 74148. The difficulty here is that we need to handle:

o Disabling all interrupts. Should this happen between the device and the 74148, or between the output of the 74148 and "interrupt_pending". o Acknowledging interrupts. When several interrupts arrive at once, we select one to service. We then must cause that device's interrupt request to be deasserted.

Let me throw a stake in the ground. Will the following simple scheme work?

Devices tied directly to 74148 inputs. Output of 74148 AND'd with interrup_enable flip-flop. The result is interrupt_pending. When a device wants to be serviced, it asserts the interrupt request and must keep it asserted until the interrupt handler associated with that device takes specific action to cause the device to deassert the requeset line. This also means that we must automatically disable interrupts on entry to an interrupt handler and keep them disabled until the handler causes the current device to drop the request.

PROBLEM #1: The heartbeat timer. We want to request an interrupt one for each rising edge of the clock.

PROBLEM #2: Are devices accustomed to asserting a request line and keeping it asserted until manually deasserting? Check out specs for a standard UART to get an idea of typical usage.

Solutions?

Perhaps I need to do something with flip-flops here. When the device wants an interrupt, it sets the flip-flop. When we decide to handle that interrupt, we can use a decoder to reset that flip-flop. The device can either keep asserting or not - but it won't be considered to have made a new interrupt request until it deasserts and then reasserts. What flavor of flip-flop to use here?