This is chapter 6 of a multi-part series on writing a RISC-V OS in Rust.

Table of Contents → Chapter 5 → (Chapter 6) → Chapter 7

Process Memory

08 December 2019: Patreon only

23 December 2019: Public

Overview

Processes are the whole point of the operating system. We want to start doing "stuff", which we'll fit into a process and get it going. We will update the process structure in the future as we add features to a process. For now, we need a program counter (which instruction is executing), and a stack for local memory.

We will not create our standard library for processes. In this chapter, we're just going to write kernel functions and wrap them into a process. When we start creating our user processes, we will need to read from the block device and start executing instructions. That's quite a ways a way, since we will need system calls and so forth.

The Process Structure

Each process must contain some information so that we can run it. We need to know some information, such as all of the registers, the MMU table, and the process' state.

The process structure isn't finished. I debated finishing it, but I think taking it step-by-step will help us understand what is needed and why that section needs to be stored in a process structure.

pub enum ProcessState {
  Running,
  Sleeping,
  Waiting,
  Dead,
}

#[repr(C)]
pub struct Process {
  frame:           TrapFrame,
  stack:           *mut u8,
  program_counter: usize,
  pid:             u16,
  root:            *mut Table,
  state:           ProcessState,
}

The process contains a stack, which we are going give to the sp (stack pointer) register. However, this stack shows the top of the stack, so we need to add the size. Remember that a stack grows from high memory to low memory (you subtract to allocate and you add to deallocate).

The program counter will contain the address of the instruction to be executed next. We can get this through the mepc register (machine exception program counter). When we interrupt our process either with a context-switch timer or an illegal instruction, or as a response to a UART input, the CPU will put the instruction about to be executed in mepc. We can restart our process by going back here and start executing instructions again.

Trap Frame

We are currently on a single-processor system. We will upgrade this to a multi-hart system, but for now, it makes much more sense just doing this for now. The trap frame allows us to freeze frame the process while we're handling it via the kernel. This is a MUST when switching back and forth. Could you imagine if a register you just set was changed by the kernel?

A process is defined by its context. The TrapFrame shows what it looks like on the CPU: (1) the general purpose registers (32 of these), (2) the floating point registers (32 of these too), (3) the MMU, (4) a stack for handling this process' interrupt context. I also store the hartid so that we don't have the same process running on two harts at the same time.

#[repr(C)]
#[derive(Clone, Copy)]
pub struct TrapFrame {
  pub regs:       [usize; 32], // 0 - 255
  pub fregs:      [usize; 32], // 256 - 511
  pub satp:       usize,       // 512 - 519
  pub trap_stack: *mut u8,     // 520
  pub hartid:     usize,       // 528
}

Making a Process

We need to allocate memory for the process' stack and the process structure itself. We will be using the MMU, so we can give it a known starting point for all processes. I chose 0x2000_0000. When we make external processes and compile them, we need to know the starting memory address. Since this is virtual memory, it essentially can be anything we want.

impl Process {
  pub fn new_default(func: fn()) -> Self {
    let func_addr = func as usize;
    // We will convert NEXT_PID below into an atomic increment when
    // we start getting into multi-hart processing. For now, we want
    // a process. Get it to work, then improve it!
    let mut ret_proc =
      Process { frame:           TrapFrame::zero(),
                stack:           alloc(STACK_PAGES),
                program_counter: PROCESS_STARTING_ADDR,
                pid:             unsafe { NEXT_PID },
                root:            zalloc(1) as *mut Table,
                state:           ProcessState::Waiting,
                data:            ProcessData::zero(), };
    unsafe {
      NEXT_PID += 1;
    }
    // Now we move the stack pointer to the bottom of the
    // allocation. The spec shows that register x2 (2) is the stack
    // pointer.
    // We could use ret_proc.stack.add, but that's an unsafe
    // function which would require an unsafe block. So, convert it
    // to usize first and then add PAGE_SIZE is better.
    // We also need to set the stack adjustment so that it is at the
    // bottom of the memory and far away from heap allocations.
    ret_proc.frame.regs[2] = STACK_ADDR + PAGE_SIZE * STACK_PAGES;
    // Map the stack on the MMU
    let pt;
    unsafe {
      pt = &mut *ret_proc.root;
    }
    let saddr = ret_proc.stack as usize;
    // We need to map the stack onto the user process' virtual
    // memory This gets a little hairy because we need to also map
    // the function code too.
    for i in 0..STACK_PAGES {
      let addr = i * PAGE_SIZE;
      map(
          pt,
          STACK_ADDR + addr,
          saddr + addr,
          EntryBits::UserReadWrite.val(),
          0,
      );
    }
    // Map the program counter on the MMU
    map(
        pt,
        PROCESS_STARTING_ADDR,
        func_addr,
        EntryBits::UserReadExecute.val(),
        0,
    );
    map(
        pt,
        PROCESS_STARTING_ADDR + 0x1001,
        func_addr + 0x1001,
        EntryBits::UserReadExecute.val(),
        0,
    );
    ret_proc
  }
}

impl Drop for Process {
  /// Since we're storing ownership of a Process in the linked list,
  /// we can cause it to deallocate automatically when it is removed.
  fn drop(&mut self) {
    // We allocate the stack as a page.
    dealloc(self.stack);
    // This is unsafe, but it's at the drop stage, so we won't
    // be using this again.
    unsafe {
      // Remember that unmap unmaps all levels of page tables
      // except for the root. It also deallocates the memory
      // associated with the tables.
      unmap(&mut *self.root);
    }
    dealloc(self.root as *mut u8);
  }
}

The Process structure's implementation is fairly simple, right now. Rust requires us to have some value for all fields, so we create these helper functions to do just that.

When we create a process, we're not really "creating" it. Instead, we're allocating memory to hold the meta-data of a process. For now, all of the process code is stored as a Rust function. Later, we will load the binary instructions from the block device and execute that way. Notice that all we need to do is create a stack. I allocated 2 pages for a stack, giving the stack 4096 * 2 = 8192 bytes. This is small, but it should be more than enough for what we're doing.

Afterward, we allocate the page table and map all relevant portions for when the MMU is turned on. Keep in mind that we'll be executing in user mode, so all kernel functions will be off limits and cause a page fault should we want to access it. In order to fully implement the process, we need system calls. These allow a user space process to request services, such as printing to the console.

Process At the CPU Level

The process at the CPU level is handled whenever we hit a trap. We're going to use the CLINT timer as our context switch timer. For now, I've allocated a full 1 second to each process. This is way too slow for normal operation, but it makes it easier to debug as we see a process step through its execution.

Every time the CLINT timer hits, we are going to store the current context, jump into Rust (via m_trap in trap.rs), and then handle what needs to be done. I've chosen to use machine mode to handle interrupts since we don't have to worry about switching the MMU (it's off in machine mode) or running into recursive faults.

The CLINT timer is controlled through MMIO as follows:

unsafe {
  let mtimecmp = 0x0200_4000 as *mut u64;
  let mtime = 0x0200_bff8 as *const u64;
  // The frequency given by QEMU is 10_000_000 Hz, so this sets
  // the next interrupt to fire one second from now.
  mtimecmp.write_volatile(mtime.read_volatile() + 10_000_000);
}

The mtimecmp is the register that stores a time in the future. When the mtime hits this value, it interrupts the CPU with a "machine timer interrupt" cause. We can use this periodic timer to interrupt our process and switch to another. This is a technique called "time slicing", where we allocate a slice of the CPUs time to each process. The faster the timer interrupts, the more processes we can shovel through in a given time. However, each process can only execute a fraction of the instructions. Furthermore, the context switch (the m_trap_handler) code gets executed for each and every interrupt.

The timer frequency is somewhat of an art. Linux went through this debate when they offered the 1,000Hz (one-thousand interrupts per second). Meaning that each process was able to run 1/1000th of a second. Granted, with the speed of processors today, that's a ton of instructions, but back in the day, this was controversial.

Trap Handler w/ Trap Frames

Our trap handler must be able to handle different trap frames since any process can be running (or even the kernel) when we need to hit the trap handler.

m_trap_vector:
# All registers are volatile here, we need to save them
# before we do anything.
csrrw	t6, mscratch, t6
# csrrw will atomically swap t6 into mscratch and the old
# value of mscratch into t6. This is nice because we just
# switched values and didn't destroy anything -- all atomically!
# in cpu.rs we have a structure of:
#  32 gp regs		0
#  32 fp regs		256
#  SATP register	512
#  Trap stack       520
#  CPU HARTID		528
# We use t6 as the temporary register because it is the very
# bottom register (x31)
.set 	i, 1
.rept	30
  save_gp	%i
  .set	i, i+1
.endr

# Save the actual t6 register, which we swapped into
# mscratch
mv		t5, t6
csrr	t6, mscratch
save_gp 31, t5

# Restore the kernel trap frame into mscratch
csrw	mscratch, t5

# Get ready to go into Rust (trap.rs)
# We don't want to write into the user's stack or whomever
# messed with us here.
csrr	a0, mepc
csrr	a1, mtval
csrr	a2, mcause
csrr	a3, mhartid
csrr	a4, mstatus
mv		a5, t5
ld		sp, 520(a5)
call	m_trap

# When we get here, we've returned from m_trap, restore registers
# and return.
# m_trap will return the return address via a0.

csrw	mepc, a0

# Now load the trap frame back into t6
csrr	t6, mscratch

# Restore all GP registers
.set	i, 1
.rept	31
  load_gp %i
  .set	i, i+1
.endr

# Since we ran this loop 31 times starting with i = 1,
# the last one loaded t6 back to its original value.

mret  

We have to manually manipulate the TrapFrame fields, so it is important to know the offsets. Anytime we change the TrapFrame structure, we need to make sure our assembly code reflects this change.

In the assembly code, we can see the first thing we do is freeze the currently running process. We're using the mscratch register to hold the TrapFrame of the currently executing process (or kernel--which uses KERNEL_TRAP_FRAME). The csrrw instruction will atomically store the value of the t6 register and return the old value (the trap frame's memory address) into t6. Remember, we have to keep ALL registers pristine, and this is an excellent way to do so!

We use the t6 register out of convenience. It is register number 32 (index 31), so it is the very last register when we loop through to save or restore the register.

I use GNU's .altmacro to allow for a macro loop as I've shown above to save and restore the registers. Many times you'll see all 32 registers being saved or restored, but the way I've done it cleans up the code significantly.

csrr	a0, mepc
csrr	a1, mtval
csrr	a2, mcause
csrr	a3, mhartid
csrr	a4, mstatus
mv		a5, t5
ld		sp, 520(a5)
call	m_trap

This portion of the trap handler is used to forward the parameters to the rust function m_trap, which looks like the following:

extern "C" fn m_trap(epc: usize,
    tval: usize,
    cause: usize,
    hart: usize,
    status: usize,
    frame: *mut TrapFrame) -> usize

By ABI convention, a0 is the epc, a1 is the tval, a2 is the cause, a3 is the hart, a4 is the status, and a5 is a pointer to the trap frame. You'll also notice that we return a usize. This is used to return the memory address of the next instruction to execute. Notice that the next instruction after calling m_trap is to load the a0 register into mepc. Also by ABI convention, the return value from Rust is stored in a0.

The First Process -- Init

Our scheduling algorithm (later) will require at least one process at all times. Just like Linux, we're going to call this process init.

The point of this chapter is to show how a process will look in the abstract view. I'm going to improve upon this chapter by adding a scheduler and showing a process actually in motion. This will be the basis for our operating system. One additional thing we need for a process to actually do anything is to implement system calls, so you can look forward to that!

Table of Contents → Chapter 5 → (Chapter 6) → Chapter 7