Lab5: Process

0x00 The Concepts and Syscalls

It’s hard to define what a process is. Usually it is a procedure in which the OS selects an executable file and performs the dynamic execution. During the execution there will be many interaction between the process and the hardware or virtual resources, and we know those are handled by the OS through syscalls. Besides, there are some important syscalls specially made for process management: fork/exec/waitpid:

• fork: When a process (let’s name it A) call fork, the kernel will create a new process (let’s name it B) which is almost identical to A: they have exactly same stack, .text segment or other data segment content, and every registers except a0 which stores the return value of the syscall. They are in different address spaces but the bytes stores in these address space are exactly same at the moment fork returns. The only way a process can figure out whether it is the new process or the old parent is the returen value of fork: 0 for the new born process and pid of child process for the parent. This parent-child relation is very important in unix-like OS.
• exec: This will help us run a new program in the current address space, use it together with fork we can easily create a process that runs a new program.
• waitpid: When a process returns, the memory resources it have consumed cannot be fully recycled through the exit syscall, for eaxmple the current kernel stack. A typical solution for this is to mark the process as zombie, then it’s parent process do the rest recycle work and get the exit status through the waitpid syscall.

0x01 Data Structures for Process

RAII is heavily used to help us safe memory management. For a process, we bind its pid, kernel stack, and address space(MemorySet) to a TaskControlBlock. The TCBs ares stored in a tree formed by the parent-child relations(created through fork&exec) between processes:

pub struct TaskControlBlock {
    // immutable
    pub pid: PidHandle,
    pub kernel_stack: KernelStack,
    // mutable
    inner: UPSafeCell<TaskControlBlockInner>,
}

pub struct TaskControlBlockInner {
    pub trap_cx_ppn: PhysPageNum,
    pub base_size: usize,
    pub priority: usize,
    pub pass: usize,
    pub task_cx: TaskContext,
    pub task_status: TaskStatus,
    pub memory_set: MemorySet,
    pub parent: Option<Weak<TaskControlBlock> >,
    pub children: Vec<Arc<TaskControlBlock> >,
    pub exit_code: i32,
}

Here we use alloc::sync::Weak to wrap the parent pointer so that there will be no cyclic refernces between the parent and it’s child.

Another significant modification from previous chapter is that we split the original task manager module into Processor and TaskManager.
– The Processor module maintains the CPU’s states, including current process and idle task context. In a single-core CPU environment, we only create one gloable instance of Processor.
– The TaskManager stores all Arcs in a BTreeMap, so that we can easily fetch/remove or add/insert tasks(processes) with our scheduler.

pub struct TaskManager {
    ready_queue: BTreeMap<usize, Arc<TaskControlBlock>>,
    scheduler: Box<Scheduler>,
}

impl TaskManager {
    pub fn new() -> Self {
        let stride_scheduler: Scheduler = Scheduler::new();
        Self {
            ready_queue: BTreeMap::new(),
            scheduler: Box::new(stride_scheduler),
        }
    }

    pub fn add(&mut self, task: Arc<TaskControlBlock>) {
        // update pass for stride scheduler
        let mut task_inner = task.inner_exclusive_access();
        task_inner.pass += BIG_STRIDE / task_inner.priority;
        drop(task_inner);
        self.scheduler.insert_task(task.getpid(), task.clone().inner_exclusive_access().pass);
        self.ready_queue.insert(task.getpid(), task);
    }

    pub fn fetch(&mut self) -> Option<Arc<TaskControlBlock>> {
        let next_pid = loop {
            if let Some(next_pid) = self.scheduler.find_next_task() {
                // TODO how about wait state
                if self.ready_queue.contains_key(&next_pid){
                    break next_pid
                }
            } else {
                return None;
            }

        };
        let (_, task) = self.ready_queue.remove_entry(&next_pid).unwrap();
        Some(task)
    }
}

0x02 Process Management

继续阅读“rCore-OS Lab5: Process”

Lab4: Address Space

Address Space is a significant mechanism in modern operating system. By adding an abstract layer between code and physical memory, it frees the developers from the painful memory arrangement work, helping them focus more on their code other than the hardware stuff.

The following figure gives an overview of how Address Space works:

Having Address Space enabled, the codes can only see the Virtual Address. If a process wants to access any address virt_addr, it will be first translated to Physical Address by CPU’s MMU module according to the process’s page table.

0x00 Hardware supports for Multilevel Paging in RISCV

The MMU is disabled by default, thus previously any program are able to access any physical memory. We can enbale the MMU by setting a register named satp:

The above figure shows the meaning of bits in satp:

• MODE controls how the MMU translate address. When MODE = 0 the MMU is disabled, and when ‘MODE’ = 8 the MMU use page table mechanism to translate the address.
• ASID indetifies the address space by id, since we don’t have process implemented yet we just ignore it.
• PPN is the physical page number of the root page table entry.

The address format under page table mechanism consists of two parts: page number and offset:

Each page table entry consists of 3 level virtual page number (vpn) and several flag bits:

With these knowledge we can easily understand how the MMU translates virtual memory address:

TLB

TLB (Translation Lookaside Buffer) works like some kinds of cache, note that we have to use sfence.vma instruction to refresh it after we change satp or any page table entry.

0x01 Address Space of Kernel and User

After satp is enabled, the memory of kernel and user applications are seperated, we need to carefully handle the interaction between different address spaces. In rCore, the designers use a Trampoline to bridge the kernel and usermode applications:

The virtual address of Trampoline is exactly same across each user spaces and the kernel space. Note that there is a guard page between kernel stacks. Those holes in the address space are settled to prevent buffer overflow damage in kernel stack.

The address space of the kernel is illustrated in the following figure:

The permissions here are critical for system security: no page table can be both writable and executable. Besides, we use identical mapping here, so the kernel can read/write any user space memory in an easy way.

In user mode, the address space is quite familiar to us:

We palce the TrapContext just under the Trampoline.

0x02 Multi-tasking with Address Space

__all_traps and trap_return shoud take care of the address space switch. Note that for each task, we should set their TaskContext’s initial ra to trap_return. We don’t have the ra pushed in kernel stack for the first time to run a task so we have to handle this manually.

The syscall call stack is:

syscall: user space ecall -> __all_traps(trampoline) -> trap_handler -> do syscall -> trap_return -> __restore -> user space

The switch process is:
继续阅读“rCore-OS Lab4: Address Space”