本阶段实验由于处于学校考试密集时间，因此没有完全跟课。主要认真学习了Hypervisor虚拟化的内容，也是我项目实习阶段最想要实践的内容。
基本理清Hypervisor运行原理和过程，课后作业完成了一部分。

ArceOS

2024.11.09

Rust 相关

关键字sym

在Rust中，sym 关键字用于引用函数或符号名称，通常出现在 asm! 宏的内联汇编代码中。sym 允许在汇编代码中引用Rust中的函数或全局变量，以便编译器能正确地将这些引用转换为相应的内存地址或符号。

原始字符串

在Rust中，字符串前r#"str"表示原始字符串字面量（raw string literal）。使用r前缀的字符串可以避免转义字符的干扰，直接包含特殊字符，如反斜杠\或双引号"。

1

let json = r#"{"name": "John", "age": 30}"#;

option_env!宏

在Rust中，option_env! 宏用于在编译时获取环境变量的值，并将其作为 Option<&'static str> 返回。

Rust条件编译

Rust 中的条件编译允许根据特定条件编译或排除某些代码片段。作用范围通常为其紧邻的代码块或声明项。对于较大的代码片段或模块内容，可以将 #[cfg(...)] 等属性放在模块或块的开头，实现更大范围的条件编译。

• #[cfg(...)] 属性
• #[cfg_attr(...)] 属性
  有条件地应用属性。适合在某些条件下添加其他属性。
• cfg! 宏
  用于在运行时检查条件编译状态，并返回布尔值。

2024.11.10

ArceOS 部分目录结构

1
2
3
4
5

.
├── api/                        // 用户调用系统的接口
├── modules/                    // 操作系统模块
├── platforms/                  // 硬件平台相关配置
└── ulib/                       // 用户lib

ArceOS Makefile

如果设置了PLATFORM变量，会覆盖ARCH变量。

1
2
3
4

# ./Makefile
PFLASH ?= y
PFLASH_IMG ?= pflash.img  # 并行闪存（Parallel Flash）
DISK_IMG ?= disk.img  # FAT32文件系统，/mnt/sbin是./target/riscv64gc-unknown-none-elf/release/origin

主要编译过程见./scripts/make/build.mk

QEMU相关

qemu-system-riscv64 -m 128M -smp 1 -machine virt -bios default -kernel tour/u_1_0/u_1_0_riscv64-qemu-virt.bin -drive if=pflash,file=/home/zone/Code/Rust/oscamp/arceos/pflash.img,format=raw,unit=1 -nographic -D qemu.log -d in_asm,int,mmu,pcall,cpu_reset,guest_errors

• -m 128M：分配128MB的内存给虚拟机。
• -smp 1：指定虚拟机使用1个CPU。
• -machine virt：指定使用虚拟化的机器类型。
• -bios default：使用默认的BIOS。
• -kernel tour/u_1_0/u_1_0_riscv64-qemu-virt.bin：指定要加载的内核镜像文件。
• -drive if=pflash,file=/home/zone/Code/Rust/oscamp/arceos/pflash.img,format=raw,unit=1：指定一个闪存驱动器，使用原始格式的镜像文件
• -nographic：禁用图形输出，使用纯文本模式。
• -D qemu.log：将QEMU的日志输出到qemu.log
• -d in_asm,int,mmu,pcall,cpu_reset,guest_errors：启用详细的调试信息，包括指令、中断、内存管理单元、过程调用、CPU重置和来宾错误。

Rust相关

build.rs

用于编译第三方的非Rust代码，只需在根目录下添加一个build.rs文件，Cargo会优先编译和执行该构建脚本，然后再构建整个项目。

Workspace

一个工作空间是由多个 package 组成的集合，它们共享同一个 Cargo.lock 文件、输出目录和一些设置(例如 profiles : 编译器设置和优化)。组成工作空间的 packages 被称之为工作空间的成员。

工作空间有两种类型：

• root package。若一个 package 的 Cargo.toml 包含了 [package] 的同时又包含了 [workspace] 部分，则该 package 被称为工作空间的根 package。
• 虚拟清单（virtual manifest）。若一个 Cargo.toml 有 [workspace] 但是没有 [package] 部分，则它是虚拟清单类型的工作空间。

特性：

• 所有package共享同一个位于根目录的Cargo.lock
• 所有package共享同一个输出目录，默认是位于根目录下的target目录
• 只有根目录的Cargo.toml才能包含 [patch], [replace] 和 [profile.*]，而成员的 Cargo.toml 中的相应部分将被自动忽略

1
2
3
4
5
6
7

[workspace]
resolver = "2"
members = [
    "modules/axalloc",
    "modules/axconfig",
    # ...
]

2024.11.11

ArceOS在riscv64-qemu-virt中的部分启动流程

• 下层的SBI初始化完成后将跳转到modules/axhal/src/platform/qemu_virt_riscv/boot.rs::_start()
  • 设置boot_stack
  • 设置初始page_table
  • 开启SV39分页，清除地址映射缓存
  • sp += phys_virt_offset
• 跳转到modules/axhal/src/platform/qemu_virt_riscv/mod.rs::rust_entry()
  • 清零bss段
  • 设置CPU_ID和IS_BSP
  • 设置trap向量表
  • 设置系统启动时间
• 跳转到modules/axruntime/src/lib.rs::rust_main()
  • enable Logging
  • 初始化全局堆内存分配器
  • 冲映射kernel各个段的地址空间
  • platform相关的初始化
  • 初始化调度器
  • 设备与驱动初始化
  • 如果有启动其他CPU
  • 初始化中断
  • 等待所有CPU启动
  • 执行用户程序
  • 清理然后退出

axalloc

接口

• Rust Trait #[global_allocator]:static GLOBAL_ALLOCATOR: GlobalAllocator

  1 2 3 4 5 6 7 8

  pub struct GlobalAllocator { balloc: SpinNoIrq<DefaultByteAllocator>, palloc: SpinNoIrq<BitmapPageAllocator<PAGE_SIZE>>, } // 必须为GlobalAllocator实现GlobalAlloc Trait // 全部内存先交给palloc管理 // 然后给balloc预先分配一小块内存作为堆空间 // 当调用balloc.alloc遇到堆空间不够用时，向palloc请求更多的内存

  GlobalAllocator提供alloc_pages(&self, num_pages: usize, align_pow2: usize)和dealloc_pages(&self, pos: usize, num_pages: usize)函数用于页的分配和回收
• 供外部调用的函数：
  • global_allocator() -> &'static GlobalAllocator
  • global_init(start_vaddr: usize, size: usize)
  • global_add_memory(start_vaddr: usize, size: usize) -> AllocResult

算法

1. TLSF (Two-Level Segregated Fit)
   通过将内存块分成多个大小类别（segregated fit）来实现快速分配。TLSF 的主要特点包括：
   快速分配和释放：分配和释放操作的时间复杂度接近 O(1)。
   低碎片率：通过精细的大小类别划分，减少内存碎片。
   适用于实时系统：由于其高效性和确定性，TLSF 常用于实时系统。

2. Slab Allocator
   通过预先分配一组称为“slab”的内存块来管理对象。Slab 分配器的主要特点包括：
   高效的对象分配：适用于频繁分配和释放固定大小对象的场景。
   减少碎片：通过预先分配和重用内存块，减少内存碎片。
   缓存对象：可以缓存已分配的对象，减少分配和释放的开销。

3. Buddy Allocator
   通过将内存块递归地分割成两部分来管理内存。Buddy 分配器的主要特点包括：
   快速分配和释放：分配和释放操作的时间复杂度为 O(log n)。
   合并相邻块：当两个相邻的内存块都空闲时，可以合并成一个更大的块，减少碎片。
   适用于大块内存分配：适合需要分配和释放大块内存的场景。

4. BitmapPage Allocator
   每个内存块对应一个位，位的状态表示该块是否已分配。BitmapPage 分配器的主要特点包括：
   简单实现：位图结构简单，易于实现和管理。
   快速查找：通过位图可以快速查找空闲块。
   适用于小块内存分配：适合需要频繁分配和释放小块内存的场景。

2024.11.12

Rust 相关

内属性和外属性

在 Rust 中，内属性（inner attribute）和外属性（outer attribute）用于不同的上下文，它们的放置顺序需要符合特定的规则。

• 外属性（outer attribute）用在项的外部（如函数、模块、结构体等），以 #[attribute] 的形式表示。
• 内属性（inner attribute）用在代码块的内部，通常用于全局的配置和文件级别的作用，以 #![attribute] 的形式表示。

Rust 不允许在某些位置先使用外属性再使用内属性。具体来说，内属性必须在模块或文件的最开头，并且需要放在任何外属性之前。

2024.11.13

axstd

HashMap

HashMap：数组+链表（+红黑树）。链表（或加上红黑树）针对出现hash冲突的情况

要在axstd里实现基础的HashMap功能，最简单的方法是在lib.rs里加上pub use hashbrown::hash_map::HashMap as HashMap

或者仿照std添加collections模块，目录结构如下：

1
2
3
4
5
6
7

ulib/axstd/src
│
└── collections
     ├── hash
     │   ├── map.rs
     │   └── mod.rs
     └── mod.rs

部分代码如下，主要是在RadomState的new函数中调用底层模块提供的生产随机数接口来设置keys：

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
36
37

use hashbrown::hash_map::HashMap as base_hashmap;
// ...

#[derive(Clone)]
pub struct RandomState {
    k0: u64,
    k1: u64,
}

impl RandomState {
    pub fn new() -> Self {
        let random_u128 = arceos_api::misc::random();
        RandomState {
            k0: random_u128 as u64,
            k1: (random_u128 >> 64) as u64,
        }
    }
}

impl BuildHasher for RandomState {
    type Hasher = DefaultHasher;
    fn build_hasher(&self) -> DefaultHasher {
        DefaultHasher(SipHasher::new_with_keys(self.k0, self.k1))
    }
}

...

#[allow(deprecated)]
#[derive(Clone, Debug)]
pub struct DefaultHasher(SipHasher);

impl Hasher for DefaultHasher {
    //...
}

pub type HashMap<K, V, S = RandomState> = base_hashmap<K, V, S>;

2024.11.14

QEMU相关

PFlash

QEMU的PFlash模拟闪存磁盘，启动时自动从文件加载内容到固定的MMIO区域，对读操作不需要驱动，可以直接访问。写操作仍需要驱动。

rust-analyzer

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

// .vscode/settings.json
{
  // 避免不必要的检查
  "rust-analyzer.check.allTargets": false,
  // 检查程序时传递给cargo的features
  "rust-analyzer.cargo.features": ["axstd"],
  "rust-analyzer.cargo.target": "riscv64gc-unknown-none-elf",
  "rust-analyzer.cargo.targetDir": "/path/to/oscamp/arceos/target",
  // "rust-analyzer.cargo.extraArgs": [
  //     "--target=riscv64gc-unknown-none-elf",
  //     "--features=axstd"
  // ],
  // "rust-analyzer.cargo.extraEnv": {
  // }
}

2024.11.17

unwrap()调用的问题

每次调用 unwrap() 都会返回一个新的实例，而不是同一个实例。因此通过unwrap修改数值无法生效。
可以通过if let Some(ref mut T)获取可变引用来修改。

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

#[derive(Copy, Clone, Debug)]
struct A {
    a: i32,
}

fn main() {
    let a = Some(A { a: 0 });
    println!("{}", a.unwrap().a);
    //0 
    a.unwrap().a = 1;
    println!("{}", a.unwrap().a);
    // 0
    if let Some(ref mut tmp) = a {
        tmp.a = 2;
    }
    println!("{}", a.unwrap().a);
    // 2
}

2024.11.18

lab1

Heap区域划分

通过分析lab1的测试样例代码可知alloc行为可以抽象为以下三种：

1. 固定大小且不回收的Vec，这些Vec的位置和大小在分配完成后就不再变化。
2. 固定大小但会回收的Vec，且回收顺序与分配顺序相反。
3. 可变大小的Vec，这些Vec主要用来临时存储前两中Vec的地址
   这一类Vec在任意时刻的数量不超过4个，且长度相对较段，因此选择在Heap区域的开头为其预留固定大小的空间（例如4KB）。

针对第一种类型，从前向后分配，针对第二种类型，从后向前分配。

特殊处理

为了简化实现，在系统将所有Heap空间分配给LabByteAllocator管理之前，LabByteAllocator的alloc函数都会返回分配失败。

除此之外，为了能够让Heap空间能够全部分配给LabByteAllocator而没有浪费，需要对LabByteAllocator的total_bytes()函数进行特殊处理，而不是返回实际的总字节数。

在axalloc中，当遇到分配器分配失败时，会将分配器的total_bytes()方法的返回值作为扩展的空间大小。假设Heap空间的结束地址是HEAP_END，当前分配器管理空间的结束地址是END，让total_bytes()返回(HEAP_END-END)/2就能尽可能将HEAP空间分配给LabByteAllocator。

2024.11.24

Rust相关

rust-analyzer

在编译时makefile会有一些预处理行为，例如设置环境变量、添加cargo参数等等。为了保持rust-analyzer分析代码时的环境与实际编译时尽量保持一致，需要添加相应的配置。

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

{
    "rust-analyzer.check.overrideCommand": [
        "cargo",
        // 改变当前目录、
        "-C",
        "/path/to/oscamp/arceos/tour/u_7_0",
        "check",
        //添加unstable flag
        "-Z",
        "unstable-options",
        "--workspace",
        "--message-format=json-diagnostic-rendered-ansi",
        "--manifest-path",
        "/path/to/oscamp/arceos/tour/u_7_0/Cargo.toml",
        "--keep-going",
        "--release",
    ],
    // 添加需要的features
    "rust-analyzer.cargo.features": [
        "axstd/irq",
        // "axstd/rtc",
    ],
    "rust-analyzer.cargo.target": "riscv64gc-unknown-none-elf",
    "rust-analyzer.cargo.targetDir": "/path/to/oscamp/arceos/target",
    "rust-analyzer.cargo.extraEnv": {
        "AX_PLATFORM": "riscv64-qemu-virt",
    }
}

RISC-V相关

异常Exception和中断Interrupt

在 RISC-V 架构语境下，异常和中断都是一种Trap，但他们被触发的原因不同。

• 异常与当前CPU的指令执行是同步的，异常被触发的原因一定能追溯到某条指令的执行，会在执行下一条指令前先进入异常处理流程。
• 中断则异步与当前正在执行的指令，也就是说中断来自于哪个外设以及中断如何触发完全与处理器正在执行的当前指令无关。相比于异常，中断与特权级的联系更加紧密。
  RISC-V 的中断可以分成三类：
  • 软件中断 (Software Interrupt)：由软件控制发出的中断
  • 时钟中断 (Timer Interrupt)：由时钟电路发出的中断
  • 外部中断 (External Interrupt)：由外设发出的中断

arceos在axhal::arch::riscv::trap::riscv_trap_handler()中指定了异常的处理函数，然后通过全局静态变量IRQ: [fn(usize) -> bool]注册中断处理函数。axhal::irq::handler_irq用于分发IRQ对应的中断到实际的处理函数。
axhal::irq::register_handler用于初始化注册中断处理函数。

ArceOS相关

初始任务

在初始化阶段创建了三个任务：

• idle：持续调用yield_now()函数的死循环
• main：init进程
• gc：回收所有退出的任务和相应的资源

2024.11.26

ArceOS相关

axtask

接口

• spawn
• yield_now:Current task gives up the CPU time voluntarily, and switches to another ready task.
• sleep
• exit

axdriver

for_each_drivers!

这个宏的作用主要是为每一种设备类型（virtio-net、ramdisk等）添加统一的处理代码，类似于for循环遍历所有的设备类型。

PCIe ECAM

PCI协议定义了256bytes配置空间，PCIe将配置空间扩展到了4KB。

PCI Express配置模型支持两种配置空间访问机制：

• PCI-compatible Configuration Access Mechanism
• PCI Express Enhanced Configuration Access Mechanism
  CAM模式是PCI协议定义的访问方式，而ECAM则是PCIe协议定义的访问方式。

一般来说，系统地址空间会预留256MB（256bus * 32dev * 8func * 4k）空间给ECAM机制使用，当然如果系统比较差，不支持那么多bus号，也可以预留小一点。

Function是PCI设备中的独立子模块，一个设备可以包含多个功能，每个功能可以执行不同的任务。例如：一个PCI网卡可能同时具有以太网控制器（Function 0）和无线网卡（Function 1）两种功能。

axfs

lookup

在当前的axfs::fs::fatfs::lookup实现中，会对传入的path参数先调用open_file，如果返回Err则再调用open_dir，因此如何path传入的是一个文件夹路径，会在err信息中看到Is a directory报错。

同步

对编译器和CPU实施的重排指令行为进行控制

• C++ memory_order_relaxed/Rust Ordering::Relaxed：无fencing作用，cpu和编译器可以重排指令
• C++ memory_order_release/Rust Ordering::Release：前面的访存指令不能排到这条指令之后
• C++ memory_order_acquire/Rust Ordering::Acquire：后面的访存指令不能排到这条指令之前
• C++ memory_order_acq_rel/Rust Ordering::AcqRel：acquire+release
• C++ memory_order_seq_cst/Rust Ordering::SeqCst：AcqRel+所有使用SeqCst的指令严格有序
• C++ memory_order_acquire：

2024.11.28

ArceOS相关

VFS

VFS定义文件系统的接口层，为操作系统提供统一的接口操作不同的文件系统。

文件系统节点的操作流程：

• 获取Root目录节点：VfsOps::root_dir()
• 解析路径，逐级通过lookup方法找到对应节点：VfsNodeOps::lookup()
• 对目标节点进行操作：VfsNodeOps::op_xxx()

Linux常用的文件系统

• ProcFS：用于提供进程信息的接口
• SysFS：用于向用户暴露设备信息，主要用于替代传统的devfs
• DevFS：目前主要是为了兼容性而存在

以上三种文件系统都是ramfs的实例，在运行时构建。

2024.11.30

Rust相关

声明宏与过程宏

• 声明宏匹配对应模式然后以另一部分代码替换当前代码
• 过程宏更像函数，接收一段Rust代码，产生另一些代码作为输出。过程宏的参数为TokenSteam类型，返回值也是TokenSteam类型。

handle_trap!声明宏会根据#[def_trap_handler]声明的变量，查找对应#[register_trap_handler(...)]注册的处理函数。

axmm

宏内核地址空间管理相关对象的层次构成：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// 每个task都有一个地址空间
pub struct AddrSpace {
    va_range: VirtAddrRange,
    areas: MemorySet<Backend>,
    pt: PageTable,
}

// 对BTreeMap的简单封装，用于管理MemoryArea
pub struct MemorySet<B: MappingBackend> {
    areas: BTreeMap<B::Addr, MemoryArea<B>>,
}

// 对应一段连续的虚拟内存区域，关联一个负责实现具体映射行为的Backend
// Backend决定map、unmap、protect的行为，目前有Linear和Alloc两种，Linear对应的物理页帧必须连续
pub struct MemoryArea<B: MappingBackend> {
    va_range: AddrRange<B::Addr>,
    flags: B::Flags,
    backend: B,
}

TODO

Hypervisor

也是很高兴能进入三阶段学习。三阶段让我对操作系统的理解更进一步，通过课后的作业，我也学到了不少知识。

个人收获

• 学会了操作系统对设备的挂载
• 了解了 unikernel 到宏内核的转化
• 对操作系统内存分配的了解更进一步
• 通过查漏补缺对上一阶段掌握不熟的知识进行了复习

通过阅读 arceos 的源代码和课后练习，我的程序编写能力也得到了锻炼，让我对操作系统有了全新的认识。

未来展望

通过这个阶段的学习，我有以下打算：

• 四阶段希望进行宏内核的学习
• 在寒假时间自己实现一个轻量级的 unikernel 内核，并通过组件化的形式将他变成宏内核

最后，感谢老师的悉心教导，也感谢平台提供的学习机会，让我有了深入学习操作系统的机会。

After the 3rd stage of the 2024 autumn winter open source operating system training camp, I would like to share my experience and summary with you.

There are three system structures to compare:

• Unikernel
  • Single-Privilege Physical-Address-Space Combination-of-Kernel-and-UserApps
• Macrokernel Mode
  • Multi-Privilege Paging-Address-Space Isolation-between-Kernel-and-UserApps
• Hypervisor (Virtual) Mode
  • Isolation-between-Host-and-Guest

The critical key to the Component-based design is the Feature. This can be configured in the Cargo.toml file and in the Makefile environment variable, which can decide which content to compile and link. It feels like a advanced #if - #endif switch option.

Unikernel

We use 3 stages to express the system advancing from bare-metal program to a component-based system.

• Bare-metal program
  • Hardfirm + Bootloader
  • Initialize the special registers
  • Initialize MMU (for Paging)
  • Initialize Stack
  • Initialize Interrupt Vector
  • Initialize Peripherals / Devices
  • Transfer to main program
• Layer / Hierarchy
  • Hardfirm + Bootloader (Layer)
  • Hardware Initialization(Layer): the special registers 、MMU(for Paging)、STACK、Interrupt Vector
  • Peripherals (Layer)
  • Transfer to main program (Layer)
• Component-based
  • Hardfirm + Bootloader
  • Hardware Initialization (HAL)
  • Runtime Environment (RTE)
  • Transfer to main program

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
36

void Reset_Handler(void) {
  __asm__ volatile(
  ".code 32                                         \n"
  "CPSID   if                                      \n"// Mask interrupts
  /* Put any cores other than 0 to sleep */
  "MRC     p15, 0, R0, c0, c0, 5                   \n"  /* Read MPIDR */
  "ANDS    R0, R0, #3                              \n"
  "goToSleep:                                      \n"
  "ITT  NE                                         \n"  /* Needed when in Thumb mode for following WFINE instruction */
  "WFINE                                           \n"
  "BNE     goToSleep                               \n"
  /* Reset SCTLR Settings */
  "MRC     p15, 0, R0, c1, c0, 0                   \n"  /* Read CP15 System Control register */
  "BIC     R0, R0, #(0x1 << 12)                    \n"  /* Clear I bit 12 to disable I Cache */
  "BIC     R0, R0, #(0x1 <<  2)                    \n"  /* Clear C bit  2 to disable D Cache */
  "BIC     R0, R0, #0x1                            \n"  /* Clear M bit  0 to disable MMU */
  "BIC     R0, R0, #(0x1 << 11)                    \n"  /* Clear Z bit 11 to disable branch prediction */
  "BIC     R0, R0, #(0x1 << 13)                    \n"  /* Clear V bit 13 to disable hivecs */
  "BIC     R0, R0, #(0x1 << 29)                    \n"  /* Clear AFE bit 29 to enable the full range of access permissions */
  "ORR     R0, R0, #(0x1 << 30)                    \n"  /* Set TE bit to take exceptions in Thumb mode */
  "MCR     p15, 0, R0, c1, c0, 0                   \n"  /* Write value back to CP15 System Control register */
  "ISB                                             \n"
  /* Configure ACTLR */
  "MRC     p15, 0, r0, c1, c0, 1                   \n"  /* Read CP15 Auxiliary Control Register */
  "ORR     r0, r0, #(1 <<  1)                      \n"  /* Enable L2 prefetch hint (UNK/WI since r4p1) */
  "MCR     p15, 0, r0, c1, c0, 1                   \n"  /* Write CP15 Auxiliary Control Register */
  /* Set Vector Base Address Register (VBAR) to point to this application's vector table */
  "LDR    R0, =Vectors                             \n"
  "MCR    p15, 0, R0, c12, c0, 0                   \n"
  "ISB                                             \n"
  ...
  "CPSIE  if                                       \n"// Unmask interrupts
  "BL __libc_init_array \n"
  "BL     main                                     \n"
  ...)
}

The above code selected from the HAL Code of STM32MP13, as the initialization and reset handler code, which will help initialize STACK, Interrupt-Vector and critical registers, and end up transferring to main program.
The code is followed similar logic as the rCore, and can help us have a better understanding of the MCU, MPU and CPU.

Like rCore, We need to provide implementation for the memory interfaces about heap operations, to avoid memory leaks and memory fragmentation.
This can help us manage memory more efficiently, and provide convenience for future expansion.

There are 2 kinds of Memory Allocation Functions: One is based on Page (palloc), and the other is based on Byte (balloc), where the “ByteAlloc” is based on “PageAlloc”.

If we take “PageAlloc” based on “ByteAlloc”, it will be difficult to align.

Algorithm for Memory Allocation

• TLSF, Two-Level Segregated Fit
• Buddy
• Slab
• Bump

How to enable paging mechanism:

1. Early in the kernel startup, use the ruled identity mapping part of memory
   • 0xffff_ffc0_8000_0000 ~ 0xffff_ffc0_C000_FFFF $\rightarrow$ 0x8000_0000~0xC000_0000
   • Note that some address-related registers, such as SP, need to be changed to linear addresses
2. Then if paging feature specified, rebuild the complete paging reflect.

Task switching:
Swaps the task currently being executed with a task in the ready queue.
For Single-core CPU, the form of multitasking can only be concurrent, but not parallel.

State of Task

• Running
  • The number is equal to the number of processor cores
  • SWITCH-TO: Ready or Blocked or Exited
• Ready
  • Is ready to be scheduled at any time
  • SWITCH-TO: Running
• Blocked
  • Waiting for an event or resource satisfying a condition
  • SWITCH-TO: Ready
• Exited
  • The task is finished and waiting to be recycled

Task switching: Firsty, save the context of the current task. Then, restore the context of the new task. Finally, trandfer to switch tasks.
Note that the interrupt enable state of the processor switching the task, should be off during the switching process (CLI).
If neccessary, the Spinlock and Mutex are required to be used to avoid race conditions (SMP?).

There are usual preemption conditions: One is the time slice of the task is exhausted, and the other is the interrupt source, such as the clock (Timer). The privilege level may be used to determine the nested or re-entry of the traps.

Algorithm of Scheduling

• Collaborative scheduling algorithm (FIFO, fair)
• Preemptive scheduling algorithm (Privileged)
  • ROUND_ROBIN
  • CFS (Completely Fair Scheduler)

The DEVICEs are usually in the kinds of net, block, display and so on.

How to discover and initialize devices

• (axruntime at startup) discovers the device and initializes it with the appropriate driver
• axdriver Indicates the process of discovering and initializing devices
  • 2-stage cyclic detection discovers the device
    • Level 1: traverses all virtio_mmio address ranges, determined by the platform physical memory layout, and performs transition page mapping
    • Level 2: Enumerate devices with the for_each_drivers macro, and then probe each virtio device probe_mmio
• probe discovers devices based on the bus, matches drivers one by one, and initializes them
  • Bus connecting with devices
    • PCI
    • MMIO

A File System is a mechanism used in an operating system to manage files and data on computer storage devices such as hard disks, SSDS, flash memory, etc.
(In Linux, every device will also exist as one or more files)

File System

• RAMFS: A memory-based virtual file system
  • For temporary data storage that is fast but easy to lose.
• DEVFS: Device file system
  • For managing and accessing hardware devices, simplifying the development and access of device drivers.
• ProcFS: process file system
  • Provides system process and status information for system monitoring and management.
• SysFS: System file system
  • Exports kernel objects and properties for viewing and managing hardware devices and drivers.

Macro kernel

More than before:

• Privilege Level
• Address space

So we need

• Map user/kernel space (address space)
  • Usual method
    • The high end of the page table is used as kernel space
    • The low end is used as user application space, because user programs mostly start from low addresses
  • Kernel space is shared and user space is used independently
• Add system call (cross-privilege + address space)

The user applications toggle between two privilege levels:

• Task Context : User Level, execute application logic
• Trap Context : Kernel Level, handle system calls and exceptions

Address space Area mapping Back-end Backend maps specific areas in a space

• Linear
  • case The target physical address space area already exists, and the mapping relationship is directly established
  • It can be used for MMIO area mapping and special shared address area mapping
  • Corresponding physical page frames must be consecutive
• Alloc (Lazy)
  • case Use missing page exception (亡羊补牢)
  • Mapped by page, the corresponding physical page frames are usually discontinuous

To compatible with Linux applications, we should implement the compatible system calls, file systems and other system resources. This asks us to follow the POSIX standard.

POSIX allows developers to write applications using a standard set of apis without worrying about differences in the underlying operating system.

Except Windows, many modern operating systems, such as Linux, macOS (based on Unix), and many embedded systems (RtOS ?) , are partially or fully POSIX compliant. This allows applications developed on these systems to run seamlessly on different platforms.

When loading the ELF-formatted application, the VirtAddr and MemSiz are used to place the segment in the target virtual memory location. Beware that some segments like .bss are all zeros, so the actual data is not stored in the ELF file, but rather dynamically allocated space is requested.

The important support to do is to implemwnt hosted-standing environment main function.
We should provide:

• Parameter information (argc and argv): parameter number, parameter string pointer array
• Environment information (envv): environment variable string pointer array

Hypervisor

Each virtual machine has its own independent virtual machine hardware, based on the physical computer. Each virtual machine runs its own operating system, and the operating system believes that it is alone in the execution environment, and cannot distinguish whether the environment is a physical machine or a virtual machine. (ideal state)

This is similar to virtualization software, like VMware ?

Is the virtual 8086 mode on x86 the same or similar principle?

The difference between a Hypervisor and an Emulator is whether the architecture of the virtual running environment is the same as that of the physical running environment that supports it.

It Seems to have something to do with emulation KVM acceleration.

Layers of resource objects supported by the Hypervisor:

• VM: manages the address space.
• vCPU: indicates the virtualization of computing resources and the flow of execution on VMS
• vMem: Memory virtualization based on the physical space layout of VMS
• vDevice: indicates device virtualization, including direct mapping and emulation
• vUtilities: interrupts virtualization and bus device operation

Usually use below items to implement a Hypervisor:

• run_guest is responsible for entering Guest environment
• guest_exit is responsible for exiting Guest environment

rCore第二阶段总结报告

第二阶段回顾

​ 本以为第一阶段后将是一马平川，却不曾想第二阶段竟是噩梦的开始。本以为第二阶段也和第一阶段一样，只需断断续续抽出一周的零碎时间即可轻易完成，但只有亲身尝试过才会知道这种想法多么的错误，最后几乎是推掉了所有的学业任务，把一整周都投入在了rCore上才勉勉强强卡ddl写完了所有lab。

​ 第零章和到第二章可以说是第二阶段的环境配置和任务理解阶段，由于上一阶段仅仅是在mac电脑上轻松写代码，故在一开始的环境配置上还是耗费了小两天，在此过程中第一次接触到了windows的wsl，然后一步一步在实验指导书的指导下搭建了 vscode + wsl + ubuntu20.02 这样的开发环境，在阅读前面几章的文档内容后也对所学的知识、实验的相关方向有了大致的了解，并能够初步运行起来自己的rust-os。在第一章的学习过程中，我理解了应用程序的执行环境，对 应用程序、函数调用、标准库、系统调用、操作系统、指令集和硬件平台 这些概念又有了新的认识，有种学习汇编语言的感觉，另外也接触到了 裸机编程、目标三元组 这些比较新的东西。但也仅停留在有印象的层面，没能深入理解其中奥秘；第二章的内容比较全面，我了解到了应用程序执行过程和操作系统的特权级切换机制，了解了编写risc-v的链接脚本来控制内存布局、内嵌汇编、异常处理、上下文切换的实现，这些操作在代码中的实现，更是让我操作系统的课上所学映入了现实，第二章的批处理调度系统，也是一个很好的帮助我入门并理解整体的代码架构的案例。

​ 后面几章就没有那么多时间细细咀嚼了，通常都是扫两眼知识然后直奔作业，除了文件系统外，其他由于都在课上学过，因此在gpt的帮助下没有被卡住太久的时间。也很感谢用心设计该实验教程的学长/学姐，不仅让我们快速入门了os，还让我们快速了解了如何系统开发一个os的各个功能。

​ 在lab1实验就卡了很久——不会仔细品读知识中所蕴含的代码实现细节，也不会投机取巧地去看看测试用例和作业所给的提示，而仅仅是闭门造车，最终卡了许久才在群聊天记录中找到了问题的关键所在，也就是时间的记录问题，当然在写的过程中也遇到诸如生命周期等等问题，让语言基础不太牢固的我举步维艰。

​ lab2是虚拟存储多级页表实验，虽然在课上老听说页表的神奇和重要性，但从没有像本次实验这样深刻地接触过操作系统中的页表，最初做的时候由于考虑的太多又无法实现便导致一度停滞不前，后来在发呆的时候又仔细重新阅读了一下题目的要求，发现需要实现的东西都还挺简单的，而且测试用例也给的非常宽松因此很快的做完了，并没有想象中那么复杂。

​ lab3是有关进程的简单创建和调度，实现上并不困难，主要难度还是在于代码结构发生了较大变化，比如本来 task_manager 做的事情现在换成了 process 在做。

​ lab4是最痛苦的一次实验，在把ch5的代码移植过来后发现仅需要过三个测试文件即可便觉得它很简单，但真正想要得心应手地写出来需要对文件系统和代码实现有详细的理解，最终还是在听了ddl前的讲解才恍然大悟：linkat和create略像前一章所提到的fork和spawn，否则将根本无从下手然后白白浪费时间并放弃之前的一切努力。在给 inode 加上 inode_id 相关的方法后很快完成了这次实验。

​ lab5的内容相对比较熟悉，也是课上自认为十分简单的死锁检测问题，但代码框架阅读起来难度较大，最终将前面的 sys_get_time 搬过来后跟着题目的提示实现了资源分配图和死锁检测系统调用的实现

第二阶段收获

​ 这次的第二阶段学习就像一场不断挑战极限的马拉松，让我既感到疲惫不堪，又充满了意想不到的收获。在本阶段的学习中，我获得了关于操作系统核心机制的更深入理解，体验到了真实操作系统开发的复杂性和细致入微的编程要求，特别是在进程管理、内存管理、以及文件系统的设计上有了全新的认识。

​ 首先，通过批处理调度系统的实现，我理解了特权级切换、上下文保存与恢复等机制。这种直接操控硬件资源的编程体验帮助我更好地理解了操作系统在管理硬件与应用间的角色。其次，在实现文件系统的过程中，我也是初次了解了文件路径解析、inode 管理和文件描述符等底层概念，这不仅让我理解了文件系统的设计精髓，也磨炼了抽象和模块化编程的能力。

​ 同时，在死锁检测的实验中，资源分配图的设计让我更深刻地理解了进程间的依赖关系和并发控制策略，学习知识的最好方式绝对是动手实践。

​ 总的来说，这一阶段的收获不止是技术上的进步，更让我体会到了系统开发的全局性思维和精确性要求。这不仅提升了我的编程能力，也让我更有信心面对后续操作系统开发中的复杂问题。

rCore第一阶段总结报告

参加训练营的契机

​ 本人是大三信息安全专业学生，起因是在学期初老师在班级群中转发了本次训练营的相关推送，正好本学期在修操作系统专业课，再加上在过去的两年实际上没有学过过硬的技术，就希望能通过本次训练营收获到许多实际项目开发相关的东西，希望能做到技多不压身。

第一阶段回顾

​ 本阶段的主要任务是根据 rust语言官方圣经 来学习rust语法，并在简单的知识训练、算法实现中掌握基本的编程逻辑和rust语言的独特思维。在学习过程中最大的感受就是，这是一门非常“麻烦”（或者说拗口）、非常底层但却非常“安全”的语言。

​ 在进一步地阅读文档和代码实操的过程中，我也深深地体会到了rust语言的魅力，很多在其他语言中不需要关注的问题，都是rust使用者的家常便饭，例如所有权与借用、生命周期、模式匹配、并发和线程、内存管理、特征泛型、智能指针、宏等等全新的概念，在学习的过程中，也能十分自然地和以往所写过的语言进行对比，也能十分自然地联想到自己所学的专业知识，整个学习过程是痛苦而充满趣味和成就感的。

​ 最终也是断断续续地在国庆后完成了110分的编程题目，虽然很多地方都有囫囵吞枣、只求大概的不好处理，但还算是初步打开了rust语言的大门。

阶段目标与晋级条件

• 从零开始构建操作系统的各个模块，不断完善操作系统核心功能

• 完成5道rCore操作系统大实验编程题，深入领会OS重要概念，掌握必备技能

• 排行榜积分达到500分，方可进入项目阶段学习，参与团队合作完成关键任务

阶段个人总结

从本阶段开始本人感到明显的学习吃力，各种新概念在教学过程中如泉涌般浮现在脑海，难以在短时间内完全消化完毕。 故专门抽出一整个周末以及课余时间反复研读与理解教学文档，深入洞悉各种新概念的内涵，在彻底理解相关知识点后再结合视频直播中老师的讲解理解每一行代码的实现逻辑（5W1H原则：‌Why（何因）‌、‌What（何事）‌、‌Where（何地）‌、‌When（何时）‌、‌Who（何物）‌、‌How（何法））。在确保完全弄懂文档知识点与代码的实现逻辑之后，方才着手完成每个实验的习题。

通过本阶段的学习，我也认识到学习操作系统相较于其他编程实践项目需要投入更多的精力，对于陌生的技术栈需要花更多的心思去理解其技术细节与应用方式，不能向以前一样盲目自信而心不在焉地学习。同时这几次实验也建立起我实战大型编程项目的经验，为以后参与更多更繁杂的编程项目打下基础。

阶段目标与晋级条件

• Rust编程语言为学习操作系统设计与实现打下坚实基础

• 通过完成100道Rustling编程题，强化训练Rust编程技能

• 该阶段排行榜达到满分可晋级，进入专业阶段学习

阶段个人总结

Rust 语言是参加本训练营必须掌握的一门语言，因为本训练营的所有项目均基于本语言编写。由于本人已学习过 Rust 编程语言，故本阶段无太大压力，跟着晋级要求完成 rustlings习题后即达成目标。

而重点是后续专业阶段 rCore 操作系统的学习与代码理解，因操作系统相关知识早已忘记（虽然曾跟着网络教程阅读过 Linux 内核源码，但年代久远早已忘记细节），故需要一定时间重拾相关知识，并跟着实验在旧知识基础上提升自己的理解水平。

附：本人学习 Rust 语言的主要参考视频教程。

记得恢复package.json

主要内容

组件化内核实验路线

• 第一周 组件化内核基础和Unikernel模式（以下4部分压缩合并到3次课）
  内核组件化基本概念、思路和框架 (U.1)
  内存管理 - 分页、地址空间(U.3)和动态内存分配(U.2)
  任务调度 - 任务与运行队列(U.4)、协作式调度(U.5) 、 抢占式调度(U.6)
  块设备驱动(U.7)和文件系统(U.8)
• 第二周 宏内核扩展（其中第3次课由郑友捷老师讲，内容待定）
  从Unikernel到宏内核的扩展 (M.1)
  用户地址空间管理和页面异常(M.2)
  进程和Linux应用支持(M.3)
• 第三周 Hypervisor扩展
  从Unikernel到宏内核的扩展 (H.1)
  Guest地址空间管理(H.2)
  VMExit各类情况处理与设备管理 (H.3)
  
  
  

  ArceOS框架

  除了运行需要的基本工具外，其他所有东西都可以以组件的形式添加到内核中，通过rust提供的feature，能够自行选择需要的组件，实现内核最小化运行。
  axfeat是一个空的feature，用来汇聚所有的feature。
  
  

作业

在println!宏定义处添加颜色输出控制信息。

hashbrown有在no_std模式下使用的hashmap，在axstd文件夹下进行修改。
Cargo.toml中添加依赖hashbrown = "0.15"
axstd/src/lib.rs 将原来的 alloc::collections删除
添加 mod collections
在src下创建文件夹collections，在mod.rs中添加如下代码，

1
2
3

#[cfg(feature = "alloc")]
#[doc(hidden)]
pub use hashbrown::HashMap as HashMap;

需要为hashmap添加全局分配器，所以要引入alloc，否则会报出如下错误

1

error: no global memory allocator found but one is required; link to std or add `#[global_allocator]` to a static item that implements the GlobalAlloc trait

第一阶段 - rust基础与算法

由于我有rust基础，没有遇到什么困难，但还是第一次完整地做一次rustlings，有一定收获

第二阶段 - 专业阶段

实验环境配置

rcore开发的环境配置比较繁琐，而我恰好比较熟悉nix，因此我用nix定义的一个完美兼容rcore的开发环境。由于不需要 rustup ， 必须在 os/Makefile 中禁用 rust 环境的检测. flake.nix 如下：

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

{
  description = "rCore dev flake";

  inputs = {
    nixpkgs.url = "github:NixOS/nixpkgs/nixpkgs-unstable";
    oldnixpkgs.url = "github:NixOS/nixpkgs/7cf5ccf1cdb2ba5f08f0ac29fc3d04b0b59a07e4";
    flake-utils.url = "github:numtide/flake-utils";
    rust-overlay = {
      url = "github:oxalica/rust-overlay";
      inputs.nixpkgs.follows = "nixpkgs";
    };
  };

  outputs = {
    nixpkgs,
    oldnixpkgs,
    flake-utils,
    rust-overlay,
    ...
  }:
    flake-utils.lib.eachDefaultSystem (system: let
      pkgs = import nixpkgs {
        inherit system;
        overlays = [(import rust-overlay)];
      };
      oldpkgs = import oldnixpkgs {
        inherit system;
      };
    in {
      devShells.default = pkgs.mkShell {
        packages = with pkgs;
          [
            (rust-bin.nightly."2024-05-02".minimal.override {
              extensions = [
                "rust-src"
                "llvm-tools"
                "rustfmt"
                "rust-analyzer"
                "rust-docs"
                "clippy"
              ];
              targets = ["riscv64gc-unknown-none-elf"];
            })
            cargo-binutils
            python3
            gdb
            tmux
          ]
          ++ [oldpkgs.qemu];

        # 进入环境后显示rust和qemu版本
        shellHook = ''
          rustc --version
          cargo --version
          qemu-system-riscv64 --version
          qemu-riscv64 --version
        '';
      };
    });
}

这份 flake.nix 也已经分享到官方问答论坛

第一/二章

阅读这两章需要先了解riscv，特别是特权级相关设计。

主要参考:

• RISC-V开放架构设计之道
• The RISC-V Reader: An Open Architecture Atlas 前一个的英文原著，而且有能下载到单独的RISC-V Green Card，方便查阅
• RISC-V Instruction Set Manual 完整详细

第三章：多道程序与分时多任务

学习了系统调用，陷入等知识，上下文切换过程中通用寄存器和CSR的使用加深了我对riscv特权级设计的理解。

本章练习较为简单。

第四章：地址空间

SV39的设计又引入了若干相关的寄存器，如satp, pmp csr。查阅riscv manul以加深理解。

本章练习中，为了处理请求映射已经被映射的页的错误，我使用了Result错误传递，无法想象如果不使用Result和?语法糖我的代码会多么丑陋。然而很奇怪，整个rcore中极少使用Result。

第五章：进程及进程管理

本章内容比较轻松，完善了TCB的设计并实现fork()和exec()系统调用。

本章练习也比较简单。

第六章：文件系统

easy-fs is NOT easy！层层抽象几乎让我晕头转向！

尽管如此，easy-fs囊括了superblock、索引节点、blockcache等现代文件系统中的基础概念，似乎不能再精简了。

link和unlink操作主要是查找inode并创建/删除目录项。在inode_block里创建与删除目录项无非是一些线性序列的操作，但由于没有封装成&[DirEntry]，需要手动操作，比较费劲。将来有空我会尝试改进一下。

第七章：进程间通信

本章内容较少，但进程间通信是个大话题，还需拓展学习。

第八章：并发

学习了多线程的同步与互斥。

练习：学习了死锁检测算法