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
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?