rcore-os Blog
0%

Posted on Edited on In

前言

就组件化内核ArceOS来说，它是用于构建各种类型的操作系统的组件仓库。自然也能够支持微内核操作系统的构建，但是第三阶段中有unikernel、有monolithic-kernel、有Hyperisor，唯独没有微内核，有点遗憾。

本篇记录我对基于ArceOS构建微内核操作系统的方法的思考和实践。

需要的组件

硬件抽象层

底层硬件平台从支持aarch64开始。

  • arm_pl031
  • arm_gicv2

内核态

支持基本的特权操作。

  • axstd
  • axalloc
  • paging
  • axtask
  • axsync

用户态

用户态主要支持块设备、网络和文件系统等。

  • syscall
  • axmm
  • axvcpu
  • vfs
  • blk_drv
  • fat32

Posted on Edited on In

内存分配器-字节分配器：Chaos 一点都不 Chaos

分析内存结构

堆中的 Vec<Vec<u8>> 结构数据

使用上述任意分配器，并在 alloc 和 dealloc 函数，中分别打印 Layout。在打印结果中可以看到一些比较特殊的内存大小分别为 96、192、384

这是什么呢？根据 lab1/src/main.rs 中的测例代码分析可得知 let mut items: Vec<Vec<u8>> = Vec::new(); 的内层 Vec 将存放在堆内存中。

而 Rust 中的堆数据结构 中的一张图片展示了 Vec 的内存结构为指针、长度和容量，每一部分各占 usize，在 64 位系统中，uszie 大小为 8 字节，即一个空数组内存占用为 24 字节，这与 96 字节仍有出入。

再观察分配情况，在 Indicator: 0 时，96 字节的 alloc 是在第一次 32 字节 alloc 后产生的，猜测是在 items.push 后进行了一次 扩容，alloc_pass 修改为如下代码进行验证：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fn alloc_pass(delta: usize) -> Vec<Vec<u8>> {
    let mut items = Vec::new();
    let mut base = 32;
    loop {
        let c = (delta % 256) as u8;
        let a = vec![c; base+delta];
        items.push(a);
        println!("Item Capacity: {}", items.capacity());
        if base >= 512*1024 {
            break;
        }
        base *= 2;
    }
    items
}

结果为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Running bumb tests...
Indicator: 0
Item Capacity: 4
Item Capacity: 4
Item Capacity: 4
Item Capacity: 4
Item Capacity: 8
Item Capacity: 8
Item Capacity: 8
Item Capacity: 8
Item Capacity: 16
Item Capacity: 16
Item Capacity: 16
Item Capacity: 16
Item Capacity: 16
Item Capacity: 16
Item Capacity: 16

就对上了，24 * 4 = 96 24 * 8 = 192 24 * 16 = 384

同时，至少在这里来说，Vec 初始容量为 0，第一次扩容时为 4，扩容机制为每次容量翻倍。

存放数据的堆空间

再回到测例代码：

1
2
3
4
5
6
7
8
9
10
fn free_pass(items: &mut Vec<Vec<u8>>, delta: u8) {
    let total = items.len();
    for j in (0..total).rev() {
        if j % 2 == 0 {
            let ret = items.remove(j);
            assert_eq!(delta, ret[0]);
            assert_eq!(delta, ret[ret.len()-1]);
        }
    }
}

这段代码在检查是否为偶数项，偶数项数组才会被 free_pass 的 remove() 释放。

因此针对这段代码，可以在分配器中设置一个奇偶标志位，当标志位为奇数时将数据从内存的起始位置开始分配，偶数时分配在末尾位置且向起始位置增长。扩容时，不考虑内存扩容时传入的内存地址起始位置而只改变结尾位置时也无需多余操作。

Chaos 真的不 Chaos

整体结构

考虑：

  1. 堆中的 Vec<Vec<u8>> 数据结构，大小固定为 96 + 192 + 384 = 672 字节，位于可分配内存的起始位置
  2. 奇数项堆，动态增长，紧跟 672 字节
  3. 偶数项堆，动态增长，位于可分配内存的末尾位置

使用以下结构体来描述整个可分配内存区域

1
2
3
4
5
6
7
8
9
10
11
12
pub struct Chaos {
    pub vec_reserve: (usize, usize, usize),

    pub start: usize,
    pub end: usize,
    pub head: usize,
    pub tail: usize,
    pub is_even: bool,

    pub allocated: usize,
    pub total: usize,
}

内存结构如下：

memory

vec_reserve: (usize, usize, usize) 用作存储先前描述的三片特殊的堆中 Vec 元数据结构，vec_reserve 为固定长度：96 + 192 + 384 字节。

pub start: usize 和 pub end: usize 分别存储 init 或是 add_to_heap 时给定的可分配内存地址范围。

pub head: usize 和 pub tail: usize 分别存储当前奇数堆的末尾位置和偶数堆的起始位置，通过 head - start + vec_reserve 可以得出奇数堆大小，通过 end - tail 则可以得出偶数堆大小。

pub is_even: bool 用于记录上一次分配是奇数还是偶数，在分配的最后将其翻转。

实现

在开始之前，还要确定一个很重要的问题。目前的设计，并没有考虑扩容时分配在本程序堆内存前内存区域的地址，因此使用代码简单判断下：

1
2
3
4
5
6
7
8
pub fn add_to_heap(&mut self, start: usize, end: usize) {
    log::warn!("head: 0x{:x}, tail: 0x{:x}, start: 0x{:x}, end: 0x{:x}", self.head, self.tail, start, end);

    self.head = start;
    self.tail = end;

    panic!("add_to_heap");
}

从 add_to_heap 的输出：

1
2
3
4
5
6
Running bumb tests...
Indicator: 0
[  0.082919 0 lab_allocator::chaos:66] head, tail: 0xffffffc08026d2a0, 0xffffffc080275000
[  0.087323 0 lab_allocator::chaos:44] head: 0xffffffc08026d2a0, tail: 0xffffffc080275000, start: 0xffffffc080275000, end: 0xffffffc08027d000
[  0.091091 0 axruntime::lang_items:5] panicked at labs/lab_allocator/src/chaos.rs:49:9:
add_to_heap

可以看到后续追加的内存与当前程序的堆尾部是连续的，只需要更改 tail 字段扩容当前内存即可。

  1. 初始化以及扩容

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    pub unsafe fn init(&mut self, start: usize, size: usize) {
            self.vec_reserve = (start, start + 96, start + 96 + 192);
            
            self.start = start + 96 + 192 + 384;
            self.head = start + 96 + 192 + 384;

            self.end = start + size;
            self.tail = start + size;

            self.allocated = 96 + 192 + 384;
            self.total = self.end - self.start;
        }

        pub fn add_to_heap(&mut self, start: usize, end: usize) {
            self.end = end;
            self.tail = end;

            self.total += end - start;
        }

  2. 分配

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    pub fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, ()> {
        let vec_reserve_ptr = match layout.size() {
            96 => Some(self.vec_reserve.0 as *const u8),
            192 => Some(self.vec_reserve.1 as *const u8),
            384 => Some(self.vec_reserve.2 as *const u8),
            _ => None,
        };

        if vec_reserve_ptr.is_some() {
            return Ok(NonNull::new(vec_reserve_ptr.unwrap() as *mut u8).unwrap());
        }

        // check if memory is overflow
        if self.tail - layout.size() <= self.head {
            return Err(());
        }
            
        let ptr = if self.is_even {
            let mem = self.tail - layout.size();
            self.tail = mem;

            NonNull::new(mem as *mut u8).unwrap()
        } else {
            let mem = self.head;
            self.head = mem + layout.size();

            NonNull::new(mem as *mut u8).unwrap()
        };

        self.is_even = !self.is_even;
        self.allocated += layout.size();

        Ok(ptr)
    }

  3. 释放

    1
    2
    3
    4
    5
    6
    7
    8
    pub fn dealloc(&mut self, pos: NonNull<u8>, layout: Layout) {
        if (pos.as_ptr() as usize) < self.start + 96 + 192 + 384 {
            return;
        }

        self.tail +=layout.size();
        self.allocated -= layout.size();
    }

越界访问

第 32 轮分配时发生了 Unhandled Supervisor Page Fault，本机的 panic 位置为 0xffffffc0802005fc，远在可分配的起始地址 0xffffffc08026d2a0 前，猜测本次的 panic 发生在栈区或是发生在从 tail 进行分配或释放时发生的。

说起来很好笑，let mut pool = Vec::new(); 和 items 一样，也会占用一些堆区内存，但因为其只写不读，即使内部全部都是无效的堆内存地址也没有问题。但这提醒到了一点：在分配用于 items: Vec<Vec<u8>> 的堆内存时，使用了一个特判：

1
2
3
4
5
6
let vec_reserve_ptr = match layout.size() {
    96 => Some(self.vec_reserve.0 as *const u8),
    192 => Some(self.vec_reserve.1 as *const u8),
    384 => Some(self.vec_reserve.2 as *const u8),
    _ => None,
};

这几个数字并没有问题，但先前我们忽略了 let a = vec![c; base+delta]; 的 base 总是从 32 开始，每次 alloc 翻倍，delta 则每轮增加 1。恰好， 第 32 轮的第二次 alloc 时那么不恰好的 base = 64 和 delta = 32，这不是 96 了嘛 uwu，所以到这时候，原本该分配给 items: Vec<Vec<u8>> 的地址被当作了 tail 堆的起始地址，又因为 tail 是 tail = tail - size 取得空闲地址，所以结果是越界了。

根据观察后，在 Layout 中存在字段 align，align 字段在 items: Vec<Vec<u8>> 分配中总是 8，而普通分配总是 1。

因此简单写个判断就可以解决了：

1
2
3
if vec_reserve_ptr.is_some() && layout.align() == 8 {
    return Ok(NonNull::new(vec_reserve_ptr.unwrap() as *mut u8).unwrap());
}

处理完这个问题后，算法成功跑到 152 轮。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Indicator: 152
[ 25.511024 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f352a8, tail=0xffffffc085015be2, size=0xb8
[ 25.513985 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc085015b2a
[ 25.516487 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f352a8, tail=0xffffffc085015b2a, size=0xd8
[ 25.519232 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f352a8
[ 25.521127 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f35380, tail=0xffffffc085015b2a, size=0x118
[ 25.523938 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc085015a12
[ 25.525770 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f35380, tail=0xffffffc085015a12, size=0x198
[ 25.528492 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f35380
[ 25.530458 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f35518, tail=0xffffffc085015a12, size=0x298
[ 25.533267 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc08501577a
[ 25.535172 0 lab_allocator::chaos:94] head, tail: 0xffffffc084f35518, 0xffffffc08501577a
[ 25.537270 0 lab_allocator::chaos:95] dealloc_memory: pos=0xffffffc08026f000, size=0x60
[ 25.540115 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f35518, tail=0xffffffc08501577a, size=0x498
[ 25.542925 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f35518
[ 25.544869 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f359b0, tail=0xffffffc08501577a, size=0x898
[ 25.547528 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc085014ee2
[ 25.549466 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f359b0, tail=0xffffffc085014ee2, size=0x1098
[ 25.552112 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f359b0
[ 25.554013 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f36a48, tail=0xffffffc085014ee2, size=0x2098
[ 25.558305 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc085012e4a
[ 25.560458 0 lab_allocator::chaos:94] head, tail: 0xffffffc084f36a48, 0xffffffc085012e4a
[ 25.562665 0 lab_allocator::chaos:95] dealloc_memory: pos=0xffffffc08026f060, size=0xc0
[ 25.564900 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f36a48, tail=0xffffffc085012e4a, size=0x4098
[ 25.567790 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f36a48
[ 25.569725 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f3aae0, tail=0xffffffc085012e4a, size=0x8098
[ 25.572420 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc08500adb2
[ 25.575027 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f3aae0, tail=0xffffffc08500adb2, size=0x10098
[ 25.577664 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f3aae0
[ 25.579570 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f4ab78, tail=0xffffffc08500adb2, size=0x20098
[ 25.582385 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084fead1a
[ 25.584478 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f4ab78, tail=0xffffffc084fead1a, size=0x40098
[ 25.587429 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f4ab78
[ 25.591690 0 axruntime::lang_items:5] panicked at modules/axalloc/src/lib.rs:124:31:
Bumb: NoMemory.

预分配：尽可能使用更多的内存

在观察 152 轮和 add_memory 的 log 时发现：

  1. 本轮的偶数区并没有得到释放。
  2. 内存从一开始分配起，每次扩容即为前一次空间 x2，最大为 32 MB。而 qemu 虚拟机分配的是 128MB，只分配到了 32MB，显然还不是极限。
1
pub fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, ()> { Err(()) }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Indicator: 0
[  0.088199 0 lab_allocator::chaos:46] add_memory: start=0xffffffc080275000, end=0xffffffc08027d000 # 32768
[  0.090785 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08027d000, end=0xffffffc08028d000 # 65536
[  0.093210 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08028d000, end=0xffffffc0802ad000 # 131072
[  0.095720 0 lab_allocator::chaos:46] add_memory: start=0xffffffc0802ad000, end=0xffffffc0802ed000 # 262144
[  0.098368 0 lab_allocator::chaos:46] add_memory: start=0xffffffc0802ed000, end=0xffffffc08036d000 # 524288
[  0.100928 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08036d000, end=0xffffffc08046d000 # 1048576
[  0.103497 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08046d000, end=0xffffffc08066d000 # 2097152
[  0.106127 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08066d000, end=0xffffffc080a6d000 # 4194304
[  0.108677 0 lab_allocator::chaos:46] add_memory: start=0xffffffc080a6d000, end=0xffffffc08126d000 # 8388608
[  0.111219 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08126d000, end=0xffffffc08226d000 # 16777216
[  0.114057 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08226d000, end=0xffffffc08426d000 # 33554432 byte = 32MB
[  0.117634 0 axruntime::lang_items:5] panicked at modules/axalloc/src/lib.rs:124:31:
Bumb: NoMemory.

因此，我们可以打第一次 alloc 开始就强迫系统预分配一大堆内存给测例。比如在 pub fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, ()> 的合理位置添加下面的代码：

1
2
3
4
// get as much memory as possible
if self.end <= 0xffffffc08426d000 {
    return Err(());
}

修改后，轮数为 189。此时，内存分配量到达了 64MB，这样下来仍有很多剩余空间。

再挤一挤，内存还是有的

看一眼 axalloc 中：

1
2
3
4
5
6
7
8
9
let old_size = balloc.total_bytes();
let expand_size = old_size
    .max(layout.size())
    .next_power_of_two()
    .max(PAGE_SIZE);
let heap_ptr = match self.alloc_pages(expand_size / PAGE_SIZE, PAGE_SIZE) {
    Ok(ptr) => ptr,
    Err(e) => panic!("Bumb: {:?}.", e),
};

不难发现 axalloc 是依赖于 total_bytes() 来判断该扩容多少内存。

简单一些处理，只需要修改原先的 total_bytes 代码，使得 total_bytes 永远返回 0。 

1
2
3
pub fn total_bytes(&self) -> usize {
    0
}

修改后的最终轮数为 245。

也许还会在 我的博客 更新，代码仓库可能会在后续删除，为了不再占用的过多空间，完整代码同样也附带在我的博客里

Posted on Edited on In

Unikernel 模式内核特点

应用与内核处于同一特权级，共享同一内存空间，编译形成一个 image 即是应用又是内核。
无隔离无切换，简单高效但安全性低。

U.1.0 Hello

输出信息到屏幕。

引导过程：axhal

  • 暂存来自 openSBI 的两个参数
    • a0: hartid，当前 CPU 的 ID
    • a1: DTB 指针，设备树地址
  • 设置栈
    • la sp, {boot_stack}
      • 将预设的栈地址加载到sp。
    • li t0, {boot_stack_size}
      • 将预设的栈大小加载到t0。
    • add sp, sp, t0
      • 将 sp 和 t0 的值相加并存回 sp，相当于栈指针下移 t0，为栈留出 t0 内存空间，完成栈的设置。
  • 设置页表并开启 MMU
  • 修正虚拟高地址
    • 由于开启 MMU 导致地址空间切换，需要将 sp 加上虚拟高地址的偏移量。
  • 调用 rust_entry
    • mv a0, s0, mv a1, s1
      • 将 hartid 和 DTB指针 复制到寄存器 a0 和 a1。
    • la a2, {entry}
      • 将入口地址加载到a2寄存器。
    • add a2, a2, s2
      • 将 a2 寄存器加上虚拟高地址的偏移。
    • jalr a2
      • 跳转到 a2 地址，即执行 rust_entry 函数
    • j .
      • 无条件跳转到当前地址

引导过程：axruntime

  • 打印 LOGO 和基本信息
  • 初始化日志功能
  • 日志打印物理内存地址信息
  • #[cfg(feature = “xxx”)]
    • 按需执行各组件初始化，例如 alloc 组件需要初始化内存分配器。
  • 打印 CPU 信息，原子操作使已初始化 CPU 数量加一，等待所有 CPU 初始化
  • 进入 main 函数

运行过程：app:hello_world

  • 没有 std 支持，不提供 main 入口
  • axstd::println -> axstd::io::__print_impl -> axstd::io::Stdout::Write -> arceos_api::stdio::ax_console_write_bytes -> axhal::console::write_bytes -> riscv64_qemu_virt::putchar

U.2.0 Collections

组件：axalloc
目标：

  1. 动态内存分配，支持 Vec 集合类型。
  2. 动态内存分配框架和算法。

需要实现两类分配：

  • Bytes Alloc
    • 支持：Rust Vec, String…
    • 接口：#[global_allocator] Trait
    • 框架：axalloc::byteAllocator
    • 算法：allocator::TlsfByteAllocator, BuddyByteAllocator, SlabByteAllocator
  • Pages Alloc
    • 支持：驱动，页表自身
    • 接口：global_allocator() 全局函数
    • 框架：axalloc::pageAllocator
    • 算法：allocator::BitmapAllocator

GlobalAllocator 数据结构

使用 TlsfByteAllocator 作为字节分配器，BitmapPageAllocator 作为页分配器。

GlobalAllocator 接口

实现 #[global_allocator] Trait 和 global_allocator() 全局函数。

GlobalAllocator 框架

将字节分配器和页分配器组成一个简单的两级分配器。首先将全部内存区域分配给页分配器，然后分配一块小区域（32 KB）给字节分配器。当字节分配器分配时无可用内存时，会向页分配器请求追加内存。

U.3.0 ReadPFlash

组件：pagetable
目标：

  1. 引入页表组件，通过地址空间重映射，支持设备 MMIO。
  2. 地址空间概念，重映射意义，页表机制。

ArceOS 包括两阶段地址空间映射，Boot 阶段默认开启 1G 空间的恒等映射。如果需要支持 MMIO，需要指定 paging feature 实现重映射更大的空间。

PFlash

Qemu 的 PFlash 模拟闪存磁盘，启动时自动加载到固定的 MMIO 区域，读操作不需要驱动。Qemu 保留了 0 号 pflash 作为扩展固件使用， 1 号 pflash 提供给用户使用，地址是 0x2200_0000。

物理地址空间

  • 0x8020_0000：kernel Image
    • .bss
    • .data
    • .rodata
    • .text
  • 0x8000_0000：SBI
  • 0x0C00_0000: MMIO

分页阶段 1 - 早期启用

开启分页，恒等映射 0x8000_0000 到 0xC000_0000 的 1GB 地址空间。切换前后地址范围不变，但从物理空间切换到虚拟空间。

分页阶段2 - 重建映射

新建一个空的内核地址空间，并通过页表申请一个新的页，随后通过axhal 体系无关操作将根页表地址写入到 satp 寄存器。

U.4.0 ChildTask

组件：axtask
目标：

  1. 创建子任务，建立多任务基本框架。
  2. 任务、运行队列。

数据结构

  • entry：任务逻辑入口
  • state：任务状态
  • kstack：栈空间，ArceOS 任务相当于线程。
  • ctx：任务调度上下文
  • task_ext：扩展属性，用于宏内核和 Hypervisor 扩展。

接口

spawn & spawn_raw

生成一个新任务，加入 RUN_QUEUE。

yield_now

让出 CPU 控制权，切换到另一个已就绪任务。

sleep & sleep_until

睡眠指定时间。

exit

退出任务。

框架

初始化

运行队列初始化和定时器初始化。
初始两个任务，main是主线程任务，idle 是用于所有任务阻塞时执行的任务。

U.5.0 MsgQueue

组件：axsync
目标：

  1. 任务切换机制，协作式调度算法。
  2. 同步的方式，Mutex 的机制。

任务切换原理

保存当前任务上下文->切换->恢复下个任务上下文。上下文一般包含如下寄存器：

  • ra：函数返回地址寄存器。
  • sp：栈指针寄存器。
  • s0-s11：函数调用相关寄存器。

算法

协作式调度算法 FIFO
较简单，略。

同步原语

自旋锁

单 CPU 只需关中断+关抢占。多 CPU 需要相互可见内存变量进行原子互斥操作。

互斥锁

自旋锁+等待队列

内存分配算法

TLSF，Buddy，Slab 算法。较复杂，可单独了解，略 。

U.6.0 FairSched

组件：timer
目标：

  1. 抢占式调度，CFS 调度策略
  2. 时钟中断机制

抢占时机

  1. 内部条件：时间片耗尽
  2. 外部条件：启用抢占
    内外条件都满足时，才发生抢占。

抢占式调度算法 ROUND_ROBIN

定时器递减当前任务的时间片，耗尽时允许调度。

抢占式调度算法 CFS

vruntime= init_vruntime + (delta / weight(nice))。

vruntime 最小的任务就是优先权最高的任务，即当前任务。

新任务 vruntime = min_runtime，设置优先级即设置 nice 值。

队列基于 BTreeMap，排序基于 vruntime，队首是 vruntime 最小的任务。

U.7.0 ReadBlock

组件：axdriver、drv_block、drv_virtio
目标：

  1. 从磁盘块设备读数据，替换 PFlash
  2. 发现设备关联驱动、块设备、VirtIO 设备

axruntime::rust_main -> axdriver::init_drivers -> AllDevices::probe -> probe_bus_devices

axruntime 在启动后期，调用 axdriver。axdriver 负责发现设备和初始化，核心结构是 AllDevices。probe 基于总线发现设备，逐个匹配驱动并初始化。

按照平台有两种总线：

  1. PCI 总线，基于 PCI 总线协议。
  2. MMIO 总线，一般基于 FDT 解析，目前采用两级循环探测。

Virtio 驱动和 virtio 设备交互：

  1. Vring 环形队列，本质上是连续 page 页面。
  2. 中断响应通道，主要用于等待读取大块数据。

U.8.0 LoadApp

组件：fatfs、axfs_vfs
目标：

  1. 从文件系统加载应用和数据
  2. 文件系统初始化和文件操作

文件系统 mount 的意义：把易于存储的扁平化结构目录树转为易于搜索遍历的立体化形态目录树。

Posted on Edited on

本阶段忙于处理于学校的事情没有完全跟课。主要学习了Hypervisor虚拟化的内容，这也是我最感兴趣的部分。
通过实验学习，我了解到Hypervisor是如何模拟出多个虚拟机环境，让它们各自拥有独立的操作系统和硬件资，期望在后续的学习中对虚拟化技术有更深入的了解。

Posted on Edited on

Arceos 总结

核心学习了arceos作为组件化设计的理念，抽象微内核、宏内核和VVM之间的共同点。

基于这些比如调度task,内存空间mmaddr,文件系统fs的底层组件，可以方便的完成需求。

lab1 内存分配挑战

通过lab1内存分配器的实现，对内存加深了理解，就是个大byte[],物理地址就是index。

lab1核心实现就是借用操作系统的分配思想，内存空间分堆区和栈区，堆区存放不需要回收的数据（一直增长，没有内存碎片），栈区放需要回收的，包括vec中间扩容的。这部分处理掉可以达到373，参考实现：

https://github.com/martin1847/oscamp/blob/lab1/arceos/labs/lab_allocator/src/lib.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
# 每轮最小生存对象
>>> a = 262144 + 65536 + 16384 + 4096 + 1024 + 256 + 64 
# 每轮额外需要的临时空间
>>> tmp = sum([524288, 131072, 32768, 8192, 2048, 512, 128, 32])
699040
# [PA:0x8026f000, PA:0x88000000) free memory (READ | WRITE | FREE)
>>> total = 0x88000000 - 0x8026f000
131665920
>>> (total - tmp )/a
374.7221204907526
# 考虑每轮增加还有一部分额外内存，7 * sum[1..N]
>>> (total - tmp - 7 * sum(range(1,373)) )/a
373.33259132942686
Read more »

Posted on Edited on

2024 秋冬季开源操作系统训练营 项目基础阶段

进度情况：

由于忙于区域赛和大创申请书，三阶段的时间并不充足，作业仅仅做到hypervisor前的部分，仅阅读了部分源码。

Unikernel基础与框架

题1

只需要将

println!("[WithColor]: !");

改为
println!("\x1b[33m[WithColor]: Hello, Arceos!\x1b[0m");

可以打出黄色字体。

题2

要求实现HashMap，并且提供随机数，我还没办法理解随机数和HashMap的关系，所以写了一个简单的HashMap

1
2
3
4
5
6
7
8
9
10
11
struct KeyValue<K, V> {
    key: K,
    value: V,
}
pub struct HashMap<K, V> {
    buckets: Vec<Vec<Option<KeyValue<K, V>>>>,  
}
fn hash(&self, key: &K) -> usize {
    let key_ptr = key as *const _ as usize;
    key_ptr % self.buckets.len()
}

Unikernel地址空间与分页、多任务支持(协作式)

题目要求：

只能修改modules/bump_allocator组件的实现，支持bump内存分配算法。不能改其它部分。

Bumpallocator 结构体

1
2
3
4
5
6
7
pub struct EarlyAllocator<const PAGE_SIZE: usize> {
heap_start: usize,
heap_end: usize,
next: usize,
allocations: usize,
page_pos: usize,
}

Base allocator需要的init 与 add_memory

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

impl<const PAGE_SIZE: usize> BaseAllocator for EarlyAllocator<PAGE_SIZE> {
    fn add_memory(&mut self, start: usize, size: usize) -> AllocResult {
        
        self.heap_end = start + size;
        Ok(())
    }

    fn init(&mut self, start: usize, size: usize) {
        self.heap_start = start;
        self.heap_end = size + self.heap_start;
        self.next = self.heap_start;
    }
    
}

PageAllocator因没有dealloc所以未实现

1
2
3
4
5
6
7
8
fn alloc_pages(&mut self, num_pages: usize, align_pow2: usize) -> AllocResult<usize> {
let align_mask = (1 << align_pow2) - 1;
let required_size = num_pages * PAGE_SIZE;
let aligned_pos = (self.page_pos + align_mask) & !align_mask;
let allocated_pages = aligned_pos;
self.page_pos = aligned_pos + required_size;
Ok(allocated_pages)
}

ByteAllocator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
impl<const PAGE_SIZE:usize> ByteAllocator for EarlyAllocator<PAGE_SIZE>{
    fn alloc(&mut self, layout: Layout) -> AllocResult<NonNull<u8>> {
        let alloc_start = self.next;
        self.next = alloc_start + layout.size();
        self.allocations += 1;
        Ok(unsafe { NonNull::new_unchecked(alloc_start as *mut u8) })

    }
    fn dealloc(&mut self, pos: NonNull<u8>, layout: Layout) {
        self.allocations -= 1;
        if self.allocations == 0 {
            self.next = self.heap_start;
    }
    }

从Unikernel到宏内核

题目要求：

需要补全缺页加载代码。

观察m1.0.0 task中代码，发现用 current().task_ext()可以得到TaskExt，然后TaskExt中包含一个AddSpace 结构体，该结构体实现了处理缺页加载的方法。于是按照该思路需要补充的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
use axhal::{mem::VirtAddr,paging::MappingFlags};
use axhal::trap::{register_trap_handler,PAGE_FAULT};
#[register_trap_handler(PAGE_FAULT)]
fn handle_page_fault(vaddr: VirtAddr, access_flags: MappingFlags, is_user: bool) -> bool {
    if is_user {
        if !axtask::current()
            .task_ext()
            .aspace
            .lock()
            .handle_page_fault(vaddr, access_flags)
        {
            ax_println!("handle_page_fault failed, vaddr={:#x}", vaddr);
            axtask::exit(-1);
        } else {
            true
        }
        
    } 
    else{
        false
    }
    
}

感想：与 Rcore 相比，似乎 ArceOS显得更加复杂，因其为了实现模块之间的兼容性，采用了多层的封装、抽象和隔离机制。然而，从我的编程体验来看，从某个特定模块的视角来看，阅读 ArceOS 的代码反而比 Rcore 更加清晰。降低了局部代码阅读难度，是值得学习的编码习惯。同时，ArceOS 的课程内容十分丰富，极大地拓宽了我的操作系统视野。

Posted on Edited on In

3阶段由于研究生学院和导师这边事情太多，勉勉强强完成了那个堆分配器的设计，其他很多东西都没来得及看了。

但是这个堆分配器也不是没有东西说的，正常分配不走歪门邪道的话是能够通过325个测例。

简单介绍一下这个堆分配器。这是一个参考了 musl libc 堆分配器设计思路打造的一个更轻量级的堆分配器。既然更轻量，就意味着内存空间的浪费会比 musl libc 多一些。

musl libc 与 glibc 的分配器实现思路完全不同，这个因为我是 CTF pwn 手，对这两个分配器的源代码都是有过深入研究的。musl libc 是采用大页分配后小块拆分的方式完成分配，其内部有一个数组，保存不同 chunk 的大小，在实际的内存空间中，chunk 的大小只可能是这些数组中保存的值的其中之一。对于这些不同大小的 chunk，musl libc 将相同大小的 chunk 放在一个内存页中进行分配，且一次可能会分配多个内存页，使得这些内存页能够充满 chunk。这种设计相较于 glibc 在实现上更加简单，这从 musl libc 对于堆分配器的代码实现行数就可以看得出来。因为 musl libc 强调小块内存的分配，因此每个小块的控制结构被设计地尽可能小，只要能够索引到控制结构就行。这使得一个 musl libc 中的 chunk 只需要 4 个字节的控制结构，最小的 chunk 为 16 字节，相比较下 glibc 中至少需要 32 个字节（最小的 chunk 就是 32 字节大小）。

在本人的实现中，对于数组的定义略显粗糙，使得给定的测例可能会导致较多的空间浪费，这个空间浪费最多是发生在整页的大块内存直接分配上。因为为了方便起见，大于一页的单次分配都是使用 buddy system 完成分配的，如果一次需要 0x1001 的空间，实际就会分配出去 0x2000 的空间，会造成很大的浪费，偏偏测例里面还有很多这样的内存分配，就使得最终的结果没有那么好看。

另外需要指明，本人实现的堆分配器存在天然漏洞，根本原因是没有记录 chunk 的首地址。如果一次性分配了连续的 2 页内存，再尝试从中间进行释放，是可以完成释放的。主要是因为提供的 free 接口中给出了释放的 chunk 大小，如果有办法能够欺骗外部结构，让其能够从中间释放，那么堆分配器实际上会出现问题，可能会导致 chunk 的重叠。

Posted on Edited on

组件化操作系统

三阶段通过使用三周的时间，初步认识了组件化操作系统arceos，和之前的宏内核rcore，存在很大区别，组件化操作系统，通过将操作系统中通用模块进行封装、抽象，将操作系统中的各个模块分离开来，针对应用场景，对不同模块进行组合，完成功能。

不同的内核实现方式，势必都有其优势和劣势，如何针对应用场景进行扬长避短，并且快速搭建不同实现方式的内核，组件化操作系统给出了答案。

Unikernel

其思想更像是之前学习嵌入式中学习到的抽象层的概念，通过组件将通用的底层的功能进行封装，通过api接口与上层应用层进行连接，内核和应用共用地址空间，不需要特权转移，极大提高了任务运行效率。

宏内核

在组件化操作系统中，添加宏内核插件，此时通过系统调用为上层应用提供支持，在插件内部仍是通过调用组件的接口，完成系统调用功能。

宏内核插件也需要提供多任务调度、多地址空间等功能。

Hypervisor

这部分还没有进行学习，更多学习宏内核starry内容。

感悟

通过这部分的学习，初步认识了组件化操作系统，为阶段四的实习部分打下了基础，学习异构的思想，在四阶段中，也可以使用这种思想，为组件化操作系统添加更多的组件，支持更多的功能。

Posted on Edited on

Areos引导机制

  • 首先进入axhal中平台架构的boot程序的_start函数，参数为OpenSBI传入的两个参数，一个是hartid用于识别CPU，一个是dtb_ptr传入DTB的指针。
  • 然后会建立栈用于函数调用，准备页表启动MMU分页机制，后即可进入Rust。

然后进入axruntime初始化应用运行时的环境，即根据feature条件编译各组件框架

启用页表机制

SBI配置FW_TEXT_START，BIOS负责把SBI加载到内存的起始位置

0x8000 0000存放SBI，SBI会跳转到以0x8020 0000起始的内核代码，存放.bss、.data、.rodata、.text段。

axhal中的linker_riscv64-qemu-virt.lds指导rust的链接器来实现段布局

一阶段：即上面提到_start函数中的初始化MMU，将物理地址空间恒等映射，再添偏移量。

二阶段：重建映射，一阶段的映射并没有添加权限进行管理。若启用”paging”的feature，首先会调用axmm中的init_memory_management()，进行创建内核空间(new_kernel_aspace())，将根页表地址写入stap寄存器(axhal::paging::set_kernel_page_table_root)。

多任务

启用”multitask”的feature，执行axtask::init_scheduler(),会进行就绪队列的初始化，以及系统timers的初始化。

  • 就绪队列的初始化：初始化系统任务idle、main、gc
    • main为主任务，其他任务均为其子任务
    • idle，其他任务都阻塞时会执行它
    • gc，除main之外的任务退出后，将由gc负责回收清理

调度算法

CFS

“init_vruntime”在os启动调度的时候决定调度顺序，”nice”则是优先级，优先级越大”vruntime”增长越慢，从而达到高优先。

当时间片结束后，当前任务将被为设为可抢占，当前任务释放控制权，加入就绪队列。并且如果外部条件满足抢占，则会将就绪队列中的队首弹出并切换到该任务

宏内核

m_1_0启动

  • 首先为应用创建独立的用户地址空间。

axmm::new_user_aspace

  • 将应用程序代码加载到地址空间。

load_user_app

  • 初始化用户栈

init_user_stack

  • spawn创建用户任务，以用户地址空间及应用入口、用户栈为参数

task::spawn_user_task

  • 当前任务释放CPU，使用户任务运行

user_task.join

用户空间

页表管理内核地址空间和用户地址空间

内核地址空间只有高端（高地址）存放内核代码数据

用户地址空间高端存放内核，但这部分的页表项设为用户不可见，只有陷入内核态之后才能访问。低端地址存放应用

每个用户地址空间高端的内核均相同，只有存放应用的区域不同

地址空间后端Backend：

Linear：目标物理地址空间已经存在，直接建立映射关系，物理页帧必须连续

Alloc：仅建立空映射，当真正被访问时将会触发缺页异常，然后在缺页响应函数内部完成物理页帧的申请和补齐映射，也就是Lazy方式。物理页帧通常情况下不连续

ELF格式应用加载

代码段加载无偏移。

数据段加载到虚拟地址空间分为.data、.bss。但.bss在ELF文件中为节省空间紧凑存储不做存放，仅做标记位置和长度。内核直接预留空间并清零

缺页异常

当发生缺页异常时，由aspace的handle_page_fault来完成对物理页帧的申请与映射

首先检查发生页面错误的虚拟地址 vaddr 是否在当前虚拟地址范围 va_range 内。

然后找到vaddr的区域area，进入area的后端，缺页异常通常由后端Alloc的Lazy策略造成，故进入Alloc分支调用handle_page_fault_alloc对页表remap完成页表映射

Hypervisor

虚拟化基于RISCV64的S特权级的H扩展，Host将在HS特权级下进行VM_ENTRY以及VM_EXIT

S特权模式进行H扩展后，原有的s[xxx]寄存器组作用不变，将新增hs[xxx]和vs[xxx]

  • hs[xxx]寄存器组的作用：面向Guest进行路径控制
  • vs[xxx]寄存器组的作用：直接操纵Guset域中的VS，为其准备或设置状态

设置hstatus的SPV位（指示特权级模式的来源，1为VS，0为U）SPVP位（指示HS对V模式下地址空间是否由操作权限）

启动Guest之前，设置Guest的sstatus，设置初始特权级为Supervisor

设置sepc为OS启动入口地址VM_ENTRY，地址为0x8020 0000

run_guest切换：保存Host上下文，将Guest上下文（第一次切换为伪造的上下文）载入寄存器组

VM_EXIT返回Host：保存Guest上下文，将Host上下文载入寄存器组

Guest和Host地址空间

Hypervisor负责基于Host物理地址空间HPA面向Guest映射Guest物理地址空间GPA

Guest会认为GPA是实际的物理地址空间，它基于satp映射内部的GVA虚拟空间

启用RISC64指令集的G扩展：

  • 引入vsatp用于第一阶段的页表翻译，即将Guest的虚拟地址空间映射为Guest的物理地址空间
  • 引入hgatp用于第二阶段的页表翻译，即将Guest的物理地址空间映射到Host的物理地址空间

虚拟机物理地址空间布局

低端区域留给设备空间和DMA

0x8000 0000在Host中是存放SBI的，但是虚拟机没有M模式，是无法访问SBI，所以这部分进行保留

0x8020 0000存放内核

高于内核的地址用作物理内存区

Hypervisor主逻辑

  • 准备VM的资源：VM地址空间和单个vCPU
  • 切换到进入Guest的代码
  • 响应VM_EXIT各种原因的代码

实现流程：

  1. 创建地址空间 为目标虚拟机创建物理地址空间 axmm
  2. 建立区域布局 在地址空间中为Guest内核和设备建立区域 axmm
  3. 加载内核 把Guest内核Image加载到内核区域 axmm, axfs
  4. 初始化vCPU 把vCPU的启动入口设置为Guest内核入口，同时设置EPT页表地址

最后在Host和Guest环境循环切换，支持虚拟机持续运行

VCPU的准备：

  • 通过set_entry（VM_ENTRY）设置sepc来配置入口地址0x8020 0000
  • 通过set_ept_root向hgatp设置模式（SV39）和根页表的页帧

axruntime和axhal时钟中断处理

axhal::irq::register_handler 通过update_timer在中断向量表中注册对应的中断响应函数，更新时钟。然后axtask::on_timer_tick()触发定时任务