Introduction

I’m making much slower progress on this project then what I hoped for. I have a few modules ready for manufacturing but I still need more and I still need to figure out how I will test them if/when they show up.

In the meantime however, I started thinking about how to make this machine even more capable. Not because I want to complicate the initial build but because I don’t want to cut myself off form further improvements. And this being the large project it already is, I’m not going to build a second, improved machine. I need to be able to adopt the one I have.

One of these threads I was pulling on lately was operating systems. Would it be possible to develop a decent operating system for this machine? The immediate problem one runs into is that of protection: to get even just a single application isolated from the operating system, one needs to prevent the application code from doing whatever it wants. This is usually achieved by memory mapper units (MMUs) and access privileges nowadays. That of course is way too much for a simple machine as the one I’m working on, but can something else be done that’s good enough and cheap enough to implement?

Standing on the Shoulders of Giants

The Cray PVP machines (starting from the Cray-1 all the way to the SV-1) used a much simpler mechanism compared to the paged MMUs of today for user- and kernel-mode isolation: that of a pair of offset and limit registers. The actual Cray implementation is quite a bit more sophisticated, but the basic idea is this:

Let’s create a new register, called the offset registers. For every memory access, this offset is added to the program-visible address as it goes out to memory. This way, a program that reads from address 0x100 could actually – without it ever knowing – read from address 0x1100, if the offset register is set to 0x1000. What this gives us is a primitive way of dealing with logical and physical addresses: the running program sees a different set of addresses then what the memory subsystem actually serves.

This in turn allows the operating system to move the logical memory that the user application uses around in physical memory, which is an important feature if you want to keep multiple applications in memory at the same time.

Of course there are several more things that need to happen, one is being protection: so far any program can still access any physical location (after address roll-over at the top of the memory), only at different addresses. We however can also add a limit register. If the program tries to access any address that is higher than what’s held in the limit register, we generate an ‘address violation’, or AV event. At the very minimum deny access to the memory location for both reads and writes, but ideally interrupt program execution and inform the operating system of what the nasty user-mode code was up to.

These two features combined gives us virtual memory and access rights. All this is useless however without the third thing: somehow we have to prevent the user-mode program from modifying the aforementioned offset and limit registers. I don’t think I need to explain the reasoning here.

Applied science

So, how can we achieve this and how should we apply this idea to the Disintegrated machines’ architecture?

The physical memory map of the machine is the following:

Page zero is special because it contains – among other things – the reset and interrupt vectors. This is RAM, but special RAM, something that user-mode applications should not have access to.

The last 32 locations in memory (called page minus one) is also special, this is the location for I/O peripherals. User-mode code have no business in there either.

Between these two locations is some ROM and RAM, where both user- and kernel-mode code can live.

The instruction set also makes (logical) page zero and page minus one special, as those locations can be accesses using immediate addressing.

If we added our offset register idea and separated logical and physical memories, we can move user-code away from page 0 while maintaining the efficient access to the first 32 locations in the applications logical memory space.

A limit register can also prevent user-mode code from accessing high-enough physical addresses that would map into the I/O space in physical memory. All is good.

The actual implementation for a logical-to-physical translation could be the following: the bottom 9 bits of the 16-bit address are not touched. The top 7 bits are where all the magic is happening. Let’s look at how we could bolt this logic onto the existing processor (really almost any processor, not just the disintegrated machine):

For every memory access, we do two things in parallel: first, we add the contents of the (7-bit) offset register to the top seven bits of the logical address coming from the instruction. This, combined with the 9-bits of the original address makes up our physical address. Second, we subtract the top seven bits of the logical address from the 7-bit limit register. If the result is negative (the logical address is beyond the limit), we generate an access violation event that we will handle somehow (to be discussed later). There are some details here that we will have to come back to, but this is the basic idea.

In this implementation we had a decision to make already: should we check the logical or the physical address against limit violations? I chose logical addresses because that way we can do the limit check in parallel with address translation, so it’s faster.

Details

There are quite a few more details to go through which are specific to the disintegrated machine.

First off, what on earth does ‘INT_EN’ have to do with any of this? In fact, what is INT_EN? This is an internal processor signal (which we will have to expose now), that keeps track of whether interrupts are enabled or not. It’s high when interrupts are enabled. Code can change the state of this bit using the ISWAP instruction and of course the CPU automatically disables interrupts when handling interrupt or reset.

By AND-ing the interrupt enable signal with all bits of the offset and limit registers, we essentially implement a sneaky way of switching between user and kernel mode. First off, the hardware logic is this: whenever interrupts are disabled, we effectively turn both the limit and address registers to 0, which disables address translation: the whole address map is accessible to the program and logical and physical addresses are the same.

The only way to transition from user mode to the kernel is through an interrupt. This interrupt in turn disables interrupts (by the CPU), and that automatically disables translation now, so the interrupt handler starts executing in kernel mode. Great!

We can also return from kernel to user mode by programming the address and limit registers to their appropriate value while interrupts are disabled safe in our knowledge that they won’t take effect until interrupts are enabled again. We return to user-mode as we would normally do from an interrupt handler, using the ISWAP instruction. This enables interrupts, thus enabling the MMU. Also great.

The scheme however has a crucial component to it: we have to prevent user-mode code from ever disabling interrupts. If it was possible, user-mode code could disable the MMU and thus defeat our protection scheme. This can be done several ways, but for now, let’s just note that the USER_MODE flag that’s fed back to the processor is used for that purpose.

Before we go any further, lets discuss one more point: what if the kernel wants to enable interrupts without entering user-mode? Well, simple: it needs to zero out both the offset and limit registers before re-enabling interrupts. That way the MMU is effectively disabled even if interrupts are allowed.

Problems

Nothing is as simple as it first seems though. Let’s think about this a little. Our physical address is computed as follows:

How did the logical address come about? Well, it comes from the address latch of the CPU. you can see this on the CPU block diagram:

The address latch is enabled in phase 0 and 2, but it’s value is calculated in both phase 5 and 0 as well as 1 and 2 respectively:

This is done so that on the rising edge of L_BUS_A_ld, the value we load into the latch is already stable, which in turn gives the memory subsystem the whole 500ns to finish its dance and return the data (for a read).

What the memory needs to do is the following:

1. Address decode – realize that its a core memory access
2. Turn on the column drivers, wait for the current to ramp
3. Turn on the row drivers, wait for the current to ramp
4. Wait some more to detect core flips
5. Turn both column and row drivers off and wait for the current to ramp to zero.

All this needs to happen within 500ns. My measurements indicate that the core needs on the order of 200ns to flip. I simulated about 70ns current delay + on-ramp on each of the drivers (about 50ns for the off-side of things), so the total memory access cycle would be 70+70+200+50+50 = 440ns. We also have to keep some margin for the address decode (step 1 above), 60ns seems sufficient, but tight. Granted the data can be returned ~340ns after the start of the read, we still need to fit everything in 500ns one way or another.

This is the old, pre-MMU picture though. What happens if we inject the MMU logic between the CPU and the memory? Now, we also have to go through the adder of the address translation before we can start address decode. This delay is dominated by the carry-chain of the 7-bit adder, I would expect it to be on the order of 150ns.

So, with the MMU, we are now at 150+70+70+200+50+50 = 590ns.  And that’s before we consider address-decode which I would think needs around 50ns or so. So overall, we’re at 640ns, way over our budget.

We can solve the problem by running the clock slower, at 1.5MHz for instance. That works, not even the end of the world, but can we do better?

Second attempt

We know that the ALU, the logic that produces the value that is latched into the REG_BUS_A doesn’t need the full 500ns. It’s propagation delay is only about 330ns. Even better: since both the ALU and the MMU adder is dominated by the carry logic, their bits become valid in a sequential order. This means that the carry propagation of the ALU can hide most of the carry propagation of the MMU: the MMU technically needs to compute one extra 1-bit add after the ALU is done. That’s not much more than 50ns. Make it 70. Still, the ALU and the MMU can be done in 400ns, in time to be latched into the REG_BUS_A.

This would mean (in fact it does mean) that we want to move the MMU before REG_BUS_A on the CPU block diagram. This poses a problem though: the processor also uses REG_BUS_A as a temporary latch to hold the value for the REG+IMM addressing mode. This is why there’s a path back from REG_BUS_A to the ALU_A mux. If the MMU modified this value, it would be bad. Luckily, we know that if that path is utilized, no memory transaction will occur. In other words, a simple modification can be done to the MMU: disable address translation whenever the REG+IMM addressing mode is used. This happens whenever bit-10 of the instruction word (highest bit of the OP_B field) is 0. With these modifications, the MMU looks like this:

Finishing touches

Finally, let’s think about what to do with an access violation! First off, we have to prevent a read or write going through if an AV is signaled. This means that the AV signal (being active low) needs to be AND-ed with ‘bus_rd’ and the ‘bus_wr’ signals.

We also need a way to tell the CPU if an AV occurred. This involves raising an interrupt (it will be handled before the execution of the subsequent instruction, if interrupts are enabled and they are, as that’s the only situation when the MMU is even active). On top of this though, we need a way to tell the CPU the cause of the interrupt. The way to achieve this is to create an R/S flop, where the S (set) signal is connected to the AV signal and the R (reset) signal is connected to an I/O write request. This way we created a ‘sticky’ version of the AV signal. It gets set when an AV occurs but only reset when the processor queries its status. This can be a separate I/O location from the MMU_CFG_REGISTER, but we only have a precious few of them. Instead, we use the following logic: if we write the MMU_CFG_REGISTER with the LSB bit set (this is so far an unused bit), the AV flag is cleared. If we write it with the LSB cleared, the AV flag is unchanged. Reading the same location would return the status of the AV flag on the LSB bit.

All in all, this leaves us with something like this:

One last thing to think through: how to use the USER_MODE flag that we return to our (existing) CPU? The easiest thing would be to disable the handling of ISWAP instructions, on other words, incorporate it into the logic that distinguishes between SWAP and ISWAP: if the USER_MODE bit is set, both instructions decode as simple SWAP. This is an extra AND gate in the decoder logic.

Third attempt

I ended up coding up the MMU in Silicon, the Python framework I’m using for digital HW development (side-note: this is a completely undocumented project at this point, but you can check it out here: https://github.com/andrastantos/silicon.) During this and it’s subsequent bring-up, I of course encountered a lot of bugs, omissions and corner-cases. Drawing these diagrams is rather time-consuming, so instead of giving you yet another variant, let me paste here the MMU code. It’s not that large and it will serve as some advertisement for Silicon as well:

The ‘HighLatch’ is a latch primitive that has an active high enable input. The RSFlop is, well an R/S flip-flop primitive. The rest should be relatively self-explanatory. What is missing is any ability to read back the status of the AV bit from SW. This is done through the – to be explained – interrupt controller: I think it’s good practice to collect all interrupt source-enable and status-check bits into a single location, so SW can easily determine the cause of the interrupt, clear them and move on.

I ended up needing two control signals to determine if the MMU should be enabled (especially it’s AV check behavior): the ‘inst_fetch’ signal is asserted (high) whenever the CPU fetches an instruction, so phase 0 and phase 1 of the instruction execution. The signal ‘opb_is_mem_ref’ is asserted whenever the instruction itself generates memory reads or writes.

I decided that ‘user_mode’ should play into the enabling of the MMU. This is not strictly necessary, but the extra one transistor is probably worth the SW convenience. This way simply writing 1 to the MMU control register disables the MMU. Without it, you would need to write 0b0000000111111101, a bit more difficult a constant to deal with in SW. (To completely render the MMU inert, you need to set the LSB to ‘1’ during the write to clear any pending AV interrupts).

I also needed to modify the CPU implementation a bit: interrupts were not a well-tested area of the design and as it turns out, not only it was not compatible with AV behavior, but it was buggy as well. The main difference between interrupts and an AV (any precise exception, really) is that an interrupt can be handled when convenient. For an exception, you really have to interrupt right after the excepted instruction. To be precise (pun intended), you have to prevent execution of the subsequent instruction as well as side-effects from taking place from the excepted instruction. This later point is crucial: we have to prevent all side-effects, not just memory accesses (which the MMU already blocks) but register changes as well. This is not a big change to the CPU (and extra AND-gate), but a crucial one. The consequence is that when an exception happens, the saved $PC points to the excepting instruction, which becomes important for SW.

Software consequences

That was a decent segue into SW implications. Writing the kernel to take advantage of these new-fangled features is not hard, but takes some care.

For now, I’ve mapped to MMU control register to address 0xffff and the interrupt status register to 0xfffe. That can change though, so I’m going to call these locations ‘MMU_REG’ and ‘INT_REG’. Not terribly imaginative, I know, but serves the purpose.

Upon reset, interrupts are disabled, but the state of the MMU_REG is unknown, so the kernel should zero it out. Actually, it should write 0x0001 into it to ensure that the AV flag is also cleared. After this, interrupts can be enabled and the processor would stay in kernel mode.

When the kernel wants to return to user mode, it needs to first disable interrupts (if they were enabled), write the appropriate value into the MMU_REG (offset, limit, set the U bit as well as the AV bit to clear any potentially lingering AV interrupts) and ISWAP to the location in user mode it wants to execute. This enables the interrupts, enters user mode and turns on the MMU in one fell swoop.

User mode code executes and eventually interrupted. At that point the kernel gets execution back, with interrupts (and thus the MMU) disabled. It determines the cause of the interrupt, handles it appropriately. If in that process it wants to enable interrupts, it needs to write 0x0001 into the MMU_REG to clear the AV flag and neutralize the MMU.

Lastly, how do we handle cases when user mode code wants to give control back to the kernel (this is the case of a SYSCALL primitive)? The simplest thing to do is to create a convention for a controlled AV. One instruction that could be used for this purpose is:

MOV $PC, [0xffff]

This instruction normally would store the PC in the largest memory location, which would fall into the I/O page. This page needs to be protected from user-mode code, so 0xffff accesses are guaranteed to generate an AV (if the MMU is used properly). The bit-pattern for this instruction is 0b1000_1111_0011_1111 or 0x8f3f. Upon handling the (AV) intrrupt, the location of the MOV instruction is stored in (physical) memory location 1, so the handler can examine the instruction code stored there, compare it with this magic value and determine that in fact a SYSCALL was requested. The call number for instance can be stored in the following word and thus the return address would be two words down from the SYSCALL. This is very similar to how I described system call handling without the MMU case, except the magic invocation instruction changed.

Summary

I’m actually quite happy with this solution: from what I can tell, it should work, it wouldn’t be terribly expensive and would allow for way better functionality of the machine. What we would need is an extra 16-bit latch (for REG_MMU_CFG), two seven-bit adders, a handful of gates and an R/S flop. The existing CPU needs modifications, but not crazy complicated.

In fact, I think I’m going to include this logic even in the first variant. This means I have a lot of updating to do on various other pages describing the disintegrated machine, but that will have to wait for another day. For now, I’ll just keep these notes here.

Future work

With exceptions being handled in this rather restrictive manner (i.e. intercepting all side-effects from the currently executing instruction), can all interrupts be handled this way? If so, would that actually simplify the CPU design? This is something I need to think about.