OSTEP & Redox: Introduction & The Process - Himwant

Introduction

Hi, I am Akshit Gaur. I recently finished my first ever “internship” over at Redox OS in the form of their Redox Summer of Code, a project that I am going to be forever grateful for. Redox OS is the reason I learned Rust, the reason I got obsessed with operating systems, and ultimately, the project that gave me my first shot at writing production kernel code.

To further my learning, I have decided to read the Operating Systems: Three Easy Pieces book, and as I read through each chapter, I am going to try and document how Redox does it. Hopefully, it should help me in my journey along with providing documentation for Redox as well!

The Process

In Chapter 4, the authors introduce The Process, the fundamental abstraction of a running Program. In Unix or xv6, this is usually represented by a massive C struct called struct proc.

Keep in mind that being an Open Source project with not a very large amount of contributors means that the reason most of the following exist is because they remain the easiest acceptable way to do things, not because they are the most optimal or though out in detail when they were being written. As a result, with time most of them are expected to be simplified away.

What is the Context here?

Redox uses the word Context for a Thread (A Process is a userspace object which can have multiple threads), so let’s open up src/context/context.rs and look at the ingredients needed to bake the perfect process. Welcome to my kitchen,

The first thing we need is some way to address it, so we do things the old fashioned way here, assign an id to it! In most of the code, we don’t actually use it (we are no longer in the old times of C, get on with the times man!), instead opting to use a reference to it. But we do still use it in two places,

a. As a tie-breaker when storing the Contexts in the ordered queue (we will talk more about this later).

b. To give some diagnostics when profiling is enabled.
We need a signal handler (TBD/To Be Discussed, i.e. I too haven’t read about it; but don’t fret! When the chapter comes, we will study together friend).
```
    pub sig: Option<SignalState>,
```
There are a few things that we need to actually schedule a context, information without which either the scheduling itself (no matter how simple) would not be possible, or some diagnostics regarding it.

a. First is that Status of the context, it does not make sense to run a dead context through the scheduling policy and mechanisms. A context can be in one of the following possible states- Runnable, Blocked (Soft or Hard), or Dead.

b. Next is if the context is already running on one of the CPUs. If yes, then which CPU is it running on?

c. We also store the time when this context was last switched to (i.e., given time to run on the CPU) and how much CPU time it has received till now.

d. We store its preference on which CPUs it can run on.

which gives us,
```
   pub status: Status,
   pub status_reason: &'static str,
   pub running: bool,
   pub cpu_id: Option<LogicalCpuId>,
   pub switch_time: u128,
   pub cpu_time: u128,
   pub sched_affinity: LogicalCpuSet,
```
Sometimes, we might catch a context in the middle of a syscall which requires special consideration, so we store that information as well!
```
   pub inside_syscall: bool,
```
Userspace is a rude rude man, and doesn’t give us nice page-aligned buffers for syscalls, so we have no option but to add extra space around the edges.
```
   pub syscall_head: SyscallFrame,
   pub syscall_tail: SyscallFrame,
```
If a context is blocked as a timer, we need to store when it wants to wake up. Unlike you, a process needs to wake up on time, they have no hands to slap that snooze button after all.
Now comes the meat of the matter, the most primal thing, the registers themselves!!! Hold your horses though, as they are arch-specific, we just abstract over them here. If you want to, you can go read the code

We also need to store some SIMD and FPU registers on a context switch, which due to various reasons, are more flexible if stored separately.
```
   pub arch: arch::Context,
   pub kfx: AlignedBox<[u8], { arch::KFX_ALIGN }>,
```
A Context needs storage to actually perform its computations, therefore, we need to store the kernel stack of the context! We give them the option to NOT contain anything too, because the First Context kmain resides entirely on the stack, it does not need a kstack on the heap.
```
    pub kstack: Option<Kstack>,
```
By virtue of the virtualisation, we need to provide a context with its own address space; but with Rust, we do not need magic values to indicate ‘no address space’. We just wrap it in an Option as contexts that just spawned or are being killed may have no address space to call their own.
```
   pub addr_space: Option<Arc<AddrSpaceWrapper>>,
```
Congratulations!! You ARE the father/mother!! And now you need to name it, I know you are a programmer and it is the hardest part of the job, but we still need to get it done, otherwise your spouse, looking at the ps output, might be tempted to SIGKILL you.
```
    pub name: ArrayString<CONTEXT_NAME_CAPAC>,
```
We need to store what files the Context has opened.
```
    pub files: Arc<LockedFdTbl>,
```
All the contexts (except kmain) primarily live in userspace, going down to kernel only when interrupts or syscalls occur.
You want to kill the Context, it holds something you deem dear (maybe your favourite deer photograph?), so you can’t kill it this exact instant, you mark it to die…
```
    pub being_sigkilled: bool,
```
I’ve got no witty remarks for the next one, it isn’t from a fundamental theoretical need that we do this, rather the needs of the implementation (which isn’t complete right now btw). We need a place to store the returned page from a lazy mmap (i.e., only requesting the underlying pages when first triggered by the page table).
```
    pub fmap_ret: Option<Frame>,
```

The next are the things needed for the scheduler, which I have already talked about in excruciating detail!

    /// Priority
    pub prio: usize,
    /// Virtual Run Time
    pub vtime: u64,
    /// Virtual Deadline
    pub vd: u64,
    /// Remaining Slice of allocated time
    pub rem_slice: u64,
    /// Is currently active?
    pub is_active: bool,
    /// Key for the RunQueue
    pub queue_key: Option<(u64, Reverse<u64>, u32)>,

We need to keep track of who owns a context for various reasons- signal delivery, displaying statistics, cleaning up, etc.
```
    pub owner_proc_id: Option<NonZeroUsize>,
```
Redox is still eating its veggies and growing, here are a few areas. We will move to Capabilities in this section too, pinky promise! Until then, enjoy the old-school Unix identity fields.
```
    pub euid: u32,
    pub egid: u32,
    pub pid: usize,
```
PreemptGuard, and thus preempt_locks, is redundant since it was added to fix a bug and will be removed once the bug disappears. In reality, interrupts are disabled everywhere in the kernel except kmain, so we don’t need it.
```
    pub(super) preempt_locks: usize,
```

And that concludes the introduction of our friend here, certainly much more lengthy compared to the book, which is going to be a theme for this series (or any series looking at a non-toy kernel tbh). Let’s move on to the next section the related APIs!

Where is the Context?

The book briefly mentions that two tracking lists exist in the kernel, one which tracks the “active” processes and the second tracks blocked processes. I am quite proud to say that Redox is better in the second department; we do not need to track all the blocked Contexts, only the timers!

Master List

We keep a master list containing a Weak reference to all non-dead contexts. The benefit in storing them as Weak reference is they are automatically dropped when the actual Strong references are dropped and their memory is freed!

static CONTEXTS: RwLock<L2, BTreeSet<ContextRef>> = RwLock::new(BTreeSet::new());

We add two helper functions too, one to get read access, another to get write.

pub fn contexts(token: LockToken<'_, L1>) -> RwLockReadGuard<'_, L2, BTreeSet<ContextRef>> {
    CONTEXTS.read(token)
}
pub fn contexts_mut(token: LockToken<'_, L1>) -> RwLockWriteGuard<'_, L2, BTreeSet<ContextRef>> {
    CONTEXTS.write(token)
}

Active List & Idle List

I have already covered this in my EEVDF post, but I will reiterate just the relevant bits here. RunContextData is the super struct that contains the active list, timer list and more.

pub struct RunContextData {
    queue: BTreeMap<(u64, Reverse<u64>, u32), (u64, u64, WeakContextRef)>, // ((vd, rem_slice, ctxt_id), (vtime, weight, context))
    timers: BTreeSet<(u128, WeakContextRef)>,                              // (wake, context)
    ...
}

queue is the actual list that stores all the active contexts (on that CPU); it is a BTreeMap (see the EEVDF post for the content and ordering).

timers store the timers (duh). It is a BTreeSet which allows O(log N) complexity in finding the contexts that need to be woken up on this tick.

Conclusion

Now you have the Context which will prove necessary going forward. As you can see, an actual kernel (micro-kernel actually) requires quite a bit more bookkeeping (or bitkeeping amirite?!) than a toy OS.

And with that, I will see you next time!