chaos 是一个用 Rust 编写的基于 2024 春夏季开源操作系统训练营 rCore 项目的 RISC-V 架构的兼容 POSIX 协议的操作系统内核。
- 王诺贤：文件系统设计与 EXT4 支持，部分 syscalls 实现；
- 陈宽宽：进程、内存管理设计，部分 syscall 实现；
- 乐一然：部分 syscalls 实现。
决赛阶段，我们大幅重构了 chaos 的代码，不仅在原先 FAT32 的基础上增加了一个 ext4 文件系统，并且将原先继承自 rCore 的内核与用户空间页表分离的做法修改为了用户与内核共享同一个地址空间，并且对于进程和线程做了进一步的抽象。经过重构，内核的代码变得更为精简，开发时对于各类资源的管理变得更为清晰，内核trap的效率也有了极大提升。
进程是操作系统中资源管理的基本单位，而线程是操作系统调度的基本单位。在决赛阶段，我们学习 Linux 的做法，对代码进行了大幅重构，将进程和线程用同一个数据结构来表示，这意味着线程此时被当作了一种轻量级进程来看待。内核中只有线程被进行调度。只有在线程退出时我们才考虑进程。二者被统一抽象为了任务，并一般通过其 pid 和 tid 来区分其是否作为线程/进程，每一个任务都有其全局唯一的 pid ， 而同一个线程组中 tid 的值相同，为主线程的 pid值。
// os/src/task/task.rs
/// Task control block structure
pub struct TaskControlBlock {
/// immutable
/// Kernel stack corresponding to PID
pub kstack: KernelStack,
/// thread id，作为进程时 pid == tid；作为线程时，tid 为其线程组 leader (父进程)的 pid 号。
pub tid: usize,
/// process id, the only identifier of the tasks
pub pid: PidHandle,
/// whether to send SIGCHLD when the task exits
pub send_sigchld_when_exit: bool,
/// mutable
inner: UPSafeCell<TaskControlBlockInner>,
}经过重构，TCB 和 PCB 被合并为了同一个数据结构，任务被分为可变和不可变两个部分管理。不可变部分仅包含 TCB 创建时就被分配的 pid ，而对于可变那部分我们封装为 TaskControlBlockInner 由于进程的父进程和其锁管理的线程都需要持有其所有权，我们使用Rust的智能指针 Arc 将其包裹以确保异步安全性，而 Arc 在Rust中默认不可变，因此我们管理 TaskControlBlockInner 时利用了Rust的内部可变性。我们封装了 RefCell ：
// os/src/sync/up.rs
pub struct UPSafeCell<T> {
/// inner data
inner: RefCell<T>,
}
unsafe impl<T> Sync for UPSafeCell<T> {}
impl<T> UPSafeCell<T> {
/// User is responsible to guarantee that inner struct is only used in
/// uniprocessor.
pub unsafe fn new(value: T) -> Self {
Self {
inner: RefCell::new(value),
}
}
/// Panic if the data has been borrowed.
pub fn exclusive_access(&self) -> RefMut<'_, T> {
self.inner.borrow_mut()
}
}RefCell 是 Rust 标准库中的一个类型，提供了在运行时进行可变借用检查的能力。它允许在单线程环境中进行内部可变性（interior mutability）。Sync 是一个标记 trait，表示类型可以安全地在多个线程间共享引用。RefCell 本身不是 Sync 的，因为它只在单线程环境中保证安全，因此我们通过 unsafe impl 声明，承诺 UPSafeCell 可以安全地在多线程环境中共享。在多核环境下，这种方法并不安全，只是一种在多核尚未实现的情况下的临时措施。
可变部分的内容如下：
// os/src/task/process.rs
pub struct TaskControlBlockInner {
/// memory set(address space)
pub memory_set: MemorySet,
/// The physical page number of the frame where the trap context is placed
pub trap_cx_ppn: PhysPageNum,
/// Save task context
pub task_cx: TaskContext,
/// Maintain the execution status of the current process
pub task_status: TaskStatus,
/// syscall times of tasks
pub syscall_times: [u32; MAX_SYSCALL_NUM],
/// the time task was first run
pub first_time: Option<usize>,
///
pub clear_child_tid: usize,
/// working directory
pub work_dir: Arc<Dentry>,
/// father task control block
pub parent: Option<Weak<TaskControlBlock>>,
/// children task control block
pub children: Vec<Arc<TaskControlBlock>>,
/// thread group
pub threads: Vec<Option<Arc<TaskControlBlock>>>,
/// user stack
pub user_stack_top: usize,
/// exit code
pub exit_code: Option<i32>,
/// file descriptor table
pub fd_table: Vec<Option<Arc<dyn File>>>,
/// clock time stop watch
pub clock_stop_watch: usize,
/// user clock time
pub user_clock: usize,
/// kernel clock time
pub kernel_clock: usize,
/// Record the usage of heap_area in MemorySet
pub heap_base: VirtAddr,
///
pub heap_end: VirtAddr,
/// is zombie?
pub is_zombie: bool,
/// signal flags
pub signals: SignalFlags,
// Signal actions
pub signal_actions: SignalActions,
pub signals_pending: SignalFlags,
}每个成员的作用如注释所述。我们通过对子进程持强引用，对父进程持弱引用来防止循环引用造成的内存泄漏。
在原先的rCore中，内核地址空间有一张单独的页表，每一次 trap 都需要切换页表才能实现，这导致 tlb 会被频繁的刷新，大大降低了运行的效率；同时，用户地址空间与内核地址空间的互相访问还会需要地址的转译，较为麻烦。因此我们决定重写这个机制，让用户地址空间和内核地址空间共享一张页表。
内核地址空间与用户地址空间共享同一张页表之后，原先的进程调度机制也需要大改。原先由于在进入和退出内核时都需要修改页表，因此不同用户进程之间的地址空间切换非常自然，现在由于一般的 syscall 陷入不需要再切换页表，只需要在新进程被调度时切换，因此我们在调度一个进程时需要把他的 trap 入口重定向至专用的 entry ，确保调度到一个进程的时候会第一时间切换到它的地址空间。
__user_entry:
# a0: *TrapContext in user space(Constant); a1: user space token
# switch to user space
csrw satp, a1
sfence.vma
csrw sscratch, a0
mv sp, a0
# now sp points to TrapContext in user space, start restoring based on it
# restore sstatus/sepc
ld t0, 32*8(sp)
ld t1, 33*8(sp)
csrw sstatus, t0
csrw sepc, t1
# restore general purpose registers except x0/sp/tp
ld x1, 1*8(sp)
ld x3, 3*8(sp)
.set n, 5
.rept 27
LOAD_GP %n
.set n, n+1
.endr
# back to user stack
ld sp, 2*8(sp)
sretchaos 支持响应来自内核态的中断，我们在进入中断时，将中断入口设置为内核中断处理函数的入口，这样就保证可以正确的处理内核态中断。
// os/src/trap/mod.rs
/// set trap entry for traps happen in kernel(supervisor) mode
fn set_kernel_trap_entry() {
extern "C" {
fn __trap_from_kernel();
}
unsafe {
stvec::write(__trap_from_kernel as usize, TrapMode::Direct);
}
}
//其余的中断实现较为常规，这里不做赘述，我们也计划支持浮点数应用的运行，只需要开启浮点数支持，并在中断处理函数中额外保存与恢复浮点数寄存器即可。
为了让内核态核用户态共用一张页表，我们需要对地址空间进行适当分割。这里我们直接利用 SV39 的机制：64 位虚拟地址只有低 39 位有效，[63 : 39] 这 25 位必须和第 38 位相同，即对于 SV39 机制来说，有效的地址范围为 0x0000000000000000 - 0x0000003fffffffff 和 0xffffffc000000000 - 0xffffffffffffffff ，这恰好分成两份，还能根据符号位（作为补码看）轻易辨别地址属于哪个区间。因此我们把用户地址空间映射到 0x0000000000000000 - 0x0000003fffffffff ，把内核地址空间映射到 0xffffffc000000000 - 0xffffffffffffffff 。我们的内存管理机制就基于这个展开。
我们重新排布了用户地址空间的内存分布，将用户栈放置在代码段之后，再将用户堆放置在用户栈之后，同时设置一个保护页（Guard Page），防止越界访问。同时我们把进程中断上下文放置在用户地址空间高处，即从 0x3fffffe000 开始向下延伸，按照 pid 进行分配，确保了内存的有序访问。
// os/src/mm/memory_set.rs
// map user stack with U flags
let max_end_va: VirtAddr = max_end_vpn.into();
let mut user_stack_bottom: usize = max_end_va.into();
user_stack_bottom += PAGE_SIZE;
let user_stack_top: usize = user_stack_bottom + USER_STACK_SIZE;
debug!("user_stack_bottom: {:#x}", user_stack_bottom);
let user_heap_base: usize = user_stack_top + PAGE_SIZE;进程之间有时不可避免的需要互相访问内存，因此我们需要一个访问其他进程地址空间的方式。我们的做法是进行一次临时映射，将当前地址空间的虚拟地址映射到其他地址空间你想要访问的物理地址，创建一个临时管道，以供临时访问。
/// 向另一个地址空间的地址写数据
pub fn write_to_user_ptr<T>(&mut self, token: usize, ptr: *mut T) -> &'static mut T {
let user_pagetable = PageTable::from_token(token);
let va = VirtAddr::from(ptr as usize);
let pa = user_pagetable.translate_va(va).unwrap();
self.page_table
.map_allow_cover(va.floor(), pa.floor(), PTEFlags::R | PTEFlags::W);
let translated_ptr: &mut T = va.get_mut();
translated_ptr
}要想内核地址和用户地址共用页表，还需要考虑一个很大的问题，即如何让平滑的切换页表，因为切换页表时正在内核地址空间执行，操作不当会导致严重错误。我们的应对方法是单独设置一张内核管理页表，由这张内核管理页表来管理内核地址空间所持有的物理页帧，所有的内核地址空间的映射和分配也仅对于这张页表进行。
那么，进程所持有的页表应该怎么处理呢，我们只需要在为新进程创建页表时，将内核管理页表高位部分的第一级映射复制过来就行，即把新页表的内核部分指向由内核管理页表所管理的内存。这样，mmu 在第一轮查表后就会直接去查阅内核管理页表。
这种做法不仅保证了所有页表的内核部分完全一致，在切换页表时可以平滑过渡，还实现了内核物理页帧的集中管理，在需要回收时非常方便。
chaos 文件系统的设计目标是最大程度将文件系统与内核解耦合，从而降低内核代码的复杂性，也能更方便地为 chaos 增加新的文件系统支持。目前 chaos 已经实现了解耦合的基础目标，并且支持了 FAT32 和 EXT4 文件系统。
为了将文件系统和内核更加彻底地解耦合，我们在初赛的基础上继续重构了文件系统，将初赛保留的 OSInode 删除，完全剩下 trait Inode。
trait Inode 的具体定义如下：
// os/src/fs/inode.rs
pub trait Inode: Send + Sync {
/// get status of file
fn fstat(self: Arc<Self>) -> Stat;
/// find the disk inode of the file with 'name'
fn find(self: Arc<Self>, name: &str) -> Option<Arc<dyn Inode>>;
/// create a file with 'name' in the root directory
fn create(self: Arc<Self>, name: &str, stat: StatMode) -> Option<Arc<dyn Inode>>;
/// create a link with a disk inode under current inode
fn link(self: Arc<Self>, old_name: &str, new_name: &str) -> Option<Arc<dyn Inode>>;
/// Remove a link under current inode
fn unlink(self: Arc<Self>, name: &str) -> bool;
/// list the file names in the root directory
fn ls(self: Arc<Self>) -> Vec<String>;
/// Read the content in offset position of the file into 'buf'
fn read_at(self: Arc<Self>, offset: usize, buf: &mut [u8]) -> usize;
/// Write the content in 'buf' into offset position of the file
fn write_at(self: Arc<Self>, offset: usize, buf: &[u8]) -> usize;
/// Set the file(disk inode) length to zero, delloc all data blocks of the file.
fn clear(self: Arc<Self>);
/// Get the current directory name
fn current_dirname(self: Arc<Self>) -> Option<String>;
}由于删去了 OSInode，为其实现的 trait File 也必须改成在更加底层的类型上实现。因此对于一个具体的 Inode（例如 FAT32Inode），我们需要额外对其实现 trait File。
这样的修改会导致一个问题：原本是 OSInode 实现了 trait File，当我们持有一个指向 OSInode 的 Arc<dyn File> 时，可以简单地通过 unsafe { x as *const OSInode} 的方式转换成 OSInode（一个具体的例子是：MemorySet 的 fd_table）。而现在，由于 Inode 和 File 都是 trait 了，无法直接进行转换。
为此，我们设计了两个转换函数，实现 Arc<dyn File> 和 Arc<dyn Inode> 的相互转换：
pub fn cast_file_to_inode(file: Arc<dyn File>) -> Option<Arc<dyn Inode>> {
unsafe {
let file_ptr = Arc::into_raw(file);
let file_ref = &*(file_ptr as *const dyn Any);
if file_ref.is::<Fat32Inode>() {
let inode_ptr = file_ptr as *const Fat32Inode;
let inode = Arc::from_raw(inode_ptr);
Some(inode)
} else if file_ref.is::<Ext4Inode>() {
let inode_ptr = file_ptr as *const Ext4Inode;
let inode = Arc::from_raw(inode_ptr);
Some(inode)
} else {
// 如果转换失败，我们需要重新创建原始的 Arc 以避免内存泄漏
let _ = Arc::from_raw(file_ptr);
None
}
}
}
pub fn cast_inode_to_file(inode: Arc<dyn Inode>) -> Option<Arc<dyn File>> {
unsafe {
let inode_ptr = Arc::into_raw(inode);
let inode_ref = &*(inode_ptr as *const dyn Any);
if inode_ref.is::<Fat32Inode>() {
let file_ptr = inode_ptr as *const Fat32Inode;
let file = Arc::from_raw(file_ptr);
Some(file)
} else if inode_ref.is::<Ext4Inode>() {
let file_ptr = inode_ptr as *const Ext4Inode;
let file = Arc::from_raw(file_ptr);
Some(file)
} else {
// 如果转换失败，我们需要重新创建原始的 Arc 以避免内存泄漏
let _ = Arc::from_raw(inode_ptr);
None
}
}
}chaos 支持 FAT32 文件系统，能够实现读、写、创建目录项、删除目录项等基础操作。
FAT32 文件系统并没有 inode 的概念，取而代之的是「簇」。一个簇的大小为四个扇区，每个扇区的大小是 512B，则一个簇的大小为 4KB。FAT32 将硬盘从前往后按簇进行划分，并从 0 开始标号。
簇的概念与 inode 相似，因此我们可以用 inode 来表示 FAT32 中簇的概念，创建出 Fat32Inode 类型，并将其实现 trait Inode：
// os/src/fs/fat32/inode.rs
#[derive(Clone)]
pub struct Fat32Inode {
pub type_: Fat32InodeType,
pub dentry: Arc<Mutex<Fat32Dentry>>,
pub start_cluster: usize,
pub fs: Arc<Mutex<Fat32FS>>,
pub bdev: Arc<dyn BlockDevice>,
}
impl Inode for Fat32Inode {
// 具体的实现方法在这里略过
}下面对 Fat32Inode 的成员变量进行解释：
type_：该文件的类型，例如文件、目录、盘符等。dentry： 该文件/目录的对应目录项。通过记录目录项所在的簇号和偏移量实现。start_cluster：该文件/目录的起始簇号。fs：提供了操作该 FAT32 文件系统的一些方法。FAT 表对象也是存放在其中。bdev：该文件系统所在的块设备。用于对块设备进行读取/写入操作。
Fat32FS 类型包含了超级快、FAT 表，以及提供了一系列与 FAT32 有关的方法：
// os/src/fs/fat32/file_system.rs
pub struct Fat32FS {
pub sb: Fat32SB,
pub fat: Arc<FAT>,
pub bdev: Arc<dyn BlockDevice>,
}
impl Fat32FS {
/// load a exist fat32 file system from block device
pub fn load(bdev: Arc<dyn BlockDevice>) -> Arc<Mutex<Self>>;
/// get root inode
pub fn root_inode(fs: &Arc<Mutex<Fat32FS>>) -> Fat32Inode;
/// get cluster chain
pub fn cluster_chain(&self, start_cluster: usize) -> Vec<usize>;
/// read a cluster
pub fn read_cluster(&self, cluster: usize, buf: &mut [u8; 4096]);
/// write a cluster
pub fn write_cluster(&self, cluster: usize, buf: &[u8; 4096]);
/// get next dentry sector id and offset
pub fn next_dentry_id(&self, sector_id: usize, offset: usize) -> Option<(usize, usize)>;
/// get a dentry with sector id and offset
pub fn get_dentry(&self, sector_id: &mut usize, offset: &mut usize) -> Option<Fat32Dentry>;
/// remove a dentry
pub fn remove_dentry(&self, dentry: &Fat32Dentry);
}除了 Fat32Inode 和 Fat32FS 以外，FAT、Fat32Dentry 和 Fat32SB 也实现了一些方法，用于获取其内部的信息。在此不过多展开。
通过以上类型组合，最终形成了 fat32 模块。最后只需将 Fat32Inode 暴露给内核，就实现了对 FAT32 文件系统的支持。
chaos 通过 vfs 虚拟文件系统，集成了外部库 ext4_rs，从而获得了对 EXT4 文件系统的支持。
在内核中，EXT4 的 Inode 实现如下：
pub struct Ext4Inode {
pub fs: Arc<Ext4FS>,
pub ino: u32,
pub inner: UPSafeCell<Ext4InodeInner>,
}
pub struct Ext4InodeInner {
pub fpos: usize,
}EXT4 的 FileSystem 实现如下：
pub struct Ext4FS {
pub ext4: Arc<Ext4>,
}由于对 ext4_rs 外部库的访问只需要使用 inode 号（ino），因此内核的 Inode 中只存储了 ino。所有对于文件系统的操作都通过 Ext4FS 内部的 ext4 属性中的各种方法来完成。
为了集成 ext4_rs 外部库，我们需要为虚拟块设备 VirtIOBlock 实现其要求的 ext4_rs::BlockDevice trait，实现如下：
impl ext4_rs::BlockDevice for VirtIOBlock {
fn read_offset(&self, offset: usize) -> Vec<u8> {
let mut buf = [0u8; BLOCK_SIZE];
self.0
.lock()
.read_blocks(offset / BLOCK_SZ, &mut buf)
.expect("Error when reading VirtIOBlk");
buf[offset % BLOCK_SZ..].to_vec()
}
fn write_offset(&self, offset: usize, data: &[u8]) {
debug!("write_offset: offset = {:#x}", offset);
let mut write_size = 0;
while write_size < data.len() {
let block_id = (offset + write_size) / BLOCK_SZ;
let block_offset = (offset + write_size) % BLOCK_SZ;
let mut buf = [0u8; BLOCK_SZ];
let copy_size = core::cmp::min(data.len() - write_size, BLOCK_SZ - block_offset);
self.0
.lock()
.read_blocks(block_id, &mut buf)
.expect("Error when reading VirtIOBlk");
buf[block_offset..block_offset + copy_size]
.copy_from_slice(&data[write_size..write_size + copy_size]);
self.0
.lock()
.write_blocks(block_id, &buf)
.expect("Error when writing VirtIOBlk");
write_size += copy_size;
}
}
}接下来，为 Ext4Inode 实现 Inode trait 和 File trait，就可以作为支持的文件系统使用。
chaos 项目从初始化仓库到完成初赛的所有赛题，仅仅花费了一周的时间。在这七天里，我们实现了众多的 syscalls、文件系统的重构、 FAT32 的支持……这些成就，离不开队员们良好的沟通、相互的信任和夜以继日的努力。
在 chaos 的开发过程中，我们参考了许多优秀的开源项目，例如 Linux、Titanix、Main.os(2)(1)(1) 等。不过，我们仅参考了这些项目的优秀思想，代码均是自己实现。
如此短的开发时间，注定了 chaos 会存在许多潜在的问题以及一些功能的缺失。在未来的时间里，我们会逐步将 chaos 进行重构，朝着更为完整的操作系统内核前进。
未来计划：
- 整理、重构代码，解耦合；
- 实现无栈协程；
- 实现多核支持；
- 适配更多的文件系统，例如 dev、proc 等；
- 移植 busybox 和 libc；
- 增加网卡驱动和网络栈，实现网络功能；
- ……