# SteinsOS Docuemnt

[SteinsOS](https://github.com/0x59616e/SteinsOS) is an OS targeting single-core
armv8-a written in Rust including these features:

- [non-preemptive kernel](https://en.wikipedia.org/wiki/Kernel_preemption)
- Preemptive multi-tasking
- File system
- Virutal memory
- [Buddy memory allocation](https://en.wikipedia.org/wiki/Buddy_memory_allocation)

This document will focus on the design of SteinsOS. If you want to learn
operating system principles, please refer to these resources:

- [Operating Systems: Three Easy Pieces](https://pages.cs.wisc.edu/~remzi/OSTEP/)
- [MIT 6.S081 Fall 2020](https://pdos.csail.mit.edu/6.828/2020/schedule.html)

## Memory Allocator

### Why memory allocator is important ?

Because in Rust, if we want to use [`alloc`](https://doc.rust-lang.org/alloc/index.html) crate, which has tons of excellent modules like [`vec`](https://doc.rust-lang.org/alloc/vec/index.html), [`string`](https://doc.rust-lang.org/alloc/string/index.html), we must have a memory allocator.

SteinsOS has two kinds of buddy allocator. The first one is buddy allocator.

### Buddy allocator
[source code](https://github.com/0x59616e/SteinsOS/blob/main/kernel/src/mm/buddyallocator.rs)

The buddy allocator in SteinsOS has eleven orders of memory blocks, range from 0 to 10, managed with linked list. Please refer to source code for further details. It's not complicated ;)

### Slab allocator

[source code](https://github.com/0x59616e/SteinsOS/blob/main/kernel/src/mm/slaballocator.rs)

The other memory allocator in SteinsOS is slab allocator.

Some of you may be confused, and a question may come to your mind:

> Why another memory allocator ?

Cause buddy allocator allocates memory in units of 4K bytes. That's a waste of memory if we just want 24 bytes. So, we need a "small memory allocator". That's what slab allocator does.

It asks a page from buddy allocator, divides it into a smaller size, manages it with linked list.

When being asked for memory, slab will check whether the size is too big or not. If so, it will propagate the request to buddy allocator:

unsafe impl GlobalAlloc for SlabAllocator {
     unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
            if layout.size() > MAXIMUM_SLAB_SIZE {
                return BuddyAllocator.alloc(layout);
            }
            ...
    }
}

Otherwise, it rounds up the requested size to the minimum size we have:

unsafe impl GlobalAlloc for SlabAllocator {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
    ...
        let (size, idx) = Self::get_size_and_index(layout.size());

        SLAB_LIST[idx].alloc_one(size)
    }
}

impl SlabAllocator {
    fn get_size_and_index(size: usize) -> (usize, usize) {
        let size = round_up_with(size.next_power_of_two(), MINIMUM_SLAB_SIZE);
        let idx = (size >> MINIMUM_SLAB_SIZE_SHIFT).trailing_zeros() as usize;
        (size, idx)
    }
}

And return the result:

unsafe impl GlobalAlloc for SlabAllocator {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        ...
        SLAB_LIST[idx].alloc_one(size)
    }
}

#[repr(transparent)]
#[derive(Clone, Copy)]
struct SlabNode(*mut SlabNode);

impl SlabNode {
    unsafe fn alloc_one(&mut self, size: usize) -> *mut u8 {
        if self.0.is_null() {
            let frame = BuddyAllocator.alloc(Layout::from_size_align_unchecked(PAGESIZE, 4));
            self.init(size, frame);
        }

        let res = self.0;
        self.0 = (*self.0).0;
        let res = res as *mut u8;
        core::slice::from_raw_parts_mut(res, size).fill(0);
        res
    }
    unsafe fn init(&mut self, size: usize, ptr: *mut u8) {   
        for i in (0..PAGESIZE).step_by(size) {
            (ptr.add(i) as *mut SlabNode).write(SlabNode(ptr.add(i + size) as *mut SlabNode));
        }
        // last one
        (ptr.add(PAGESIZE - size) as *mut SlabNode).write(SlabNode(core::ptr::null_mut()));
        self.0 = ptr as *mut Self;
    }
    ...
}

### Summary

Buddy allocator is "big memory allocator", it manages memory in units of 4K bytes; Slab allocator is "small memory allocator", it manages memory with size range from 8 bytes to 1024 bytes.

### Virtual Memory

to be continued...