2024开源OS训练营 - rCore实验记录

发表于 分类于 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 6 分钟

#Chapter 4 内存管理

#内存布局

所谓 OS 内核无非就是一个裸机上跑的程序，首先要确定的就是程序本身的内存布局问题。

说到内存布局那就是 linker 的工作范围了，linker script 启动。

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
// @linker.ld
OUTPUT_ARCH(riscv)
ENTRY(_start)
BASE_ADDRESS = 0x80200000; // 程序加载的起始地址

SECTIONS
{
    . = BASE_ADDRESS;
    skernel = .;    // 定义标签 skernel -> 0x80200000

    stext = .;      // 定义标签 stext 代码段开始
    .text : {       // .text 段，把之前的几个段放这里
        *(.text.entry)
        . = ALIGN(4K);
        strampoline = .;    // 定义标签 strampoline 跳板页
        *(.text.trampoline);
        . = ALIGN(4K);
        *(.text .text.*)
    }

    . = ALIGN(4K);
    etext = .;      // 定义标签 etext 代码段结束
    srodata = .;    // 定义标签 srodata 只读数据段开始
    .rodata : {
        *(.rodata .rodata.*)
        *(.srodata .srodata.*)
    }

    . = ALIGN(4K);
    erodata = .;    // 定义标签 erodata 只读数据段结束
    sdata = .;      // 定义标签 sdata 数据段开始
    .data : {
        *(.data .data.*)
        *(.sdata .sdata.*)
    }

    . = ALIGN(4K);
    edata = .;      // 定义标签 edata 数据段结束
    sbss_with_stack = .;    // 定义标签 sbss_with_stack 堆栈段开始
    .bss : {        // .bss 段
        *(.bss.stack)
        sbss = .;
        *(.bss .bss.*)
        *(.sbss .sbss.*)
    }

    . = ALIGN(4K);
    ebss = .;       // 定义标签 ebss 堆栈段结束
    ekernel = .;    // 定义标签 ekernel 内核结束

    /DISCARD/ : {   // 丢弃段
        *(.eh_frame)
    }
}

所以，rcore 的内存布局：

  • skernel(0x80200000) - srodata: 代码段
  • srodata - erodata: 只读数据段
  • sdata - edata: 数据段
  • sbss_with_stack - sbss: 栈
  • sbss - ebss: bss 段
  • ekernel: 内核结束

在 entry.asm 中定义了 _start 符号，这是程序的入口地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    .section .text.entry
    .globl _start
_start:
    la sp, boot_stack_top
    call rust_main  ; 调用 rust_main 函数

    ; 下面定义一些全局变量
    ; boot_stack_lower_bound 是堆栈的起始地址，大小为 16 个 Page = 64KB
    ; boot_stack_top 是堆栈的结束地址
    .section .bss.stack
    .globl boot_stack_lower_bound
boot_stack_lower_bound:
    .space 4096 * 16
    .globl boot_stack_top
boot_stack_top:

Rust 语言的入口是 rust_main 函数，这个函数在 main.rs 中定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#[no_mangle]
/// the rust entry-point of os
pub fn rust_main() -> ! {
    clear_bss();        // 把 sbss 到 ebss 的内存清零
    kernel_log_info();  // 打印段的起始和结束地址，日志输出由SBI提供
    mm::init();         // 初始化内存管理（堆内存管理，页表管理）
    println!("[kernel] back to world!");
    mm::remap_test();
    trap::init();
    trap::enable_timer_interrupt();
    timer::set_next_trigger();
    task::run_first_task(); // 运行第一个任务
    panic!("Unreachable in rust_main!");
}

#内存管理子系统

内存管理子系统主要包括：

  • heap_allocator: 堆内存管理
  • frame_allocator: 页表管理
  • KERNEL_SPACE: 内核空间
1
2
3
4
5
pub fn init() {
    heap_allocator::init_heap();
    frame_allocator::init_frame_allocator();
    KERNEL_SPACE.exclusive_access().activate();
}

第一部分内核堆其实就是一个巨大的全局数组，会被编译器放在 .bss 段，然后通过堆内存管理器进行管理。

1
2
3
4
5
6
7
8
9
10
11
pub const KERNEL_HEAP_SIZE: usize = 0x200_0000;

static mut HEAP_SPACE: [u8; KERNEL_HEAP_SIZE] = [0; KERNEL_HEAP_SIZE];
/// initiate heap allocator
pub fn init_heap() {
    unsafe {
        HEAP_ALLOCATOR
            .lock()
            .init(HEAP_SPACE.as_ptr() as usize, KERNEL_HEAP_SIZE);
    }
}

第二部分是物理页管理，负责管理计算机上从 ekernel 到 MEMORY_END 之间的物理内存。物理内存是分页管理的，页大小固定是 4k。

  • PhysPageNum 物理页号
  • PhysAddr 物理地址
  • VirtPageNum 虚拟页号
  • VirtAddr 虚拟地址
1
2
3
4
5
6
7
8
9
10
11
12
pub const MEMORY_END: usize = 0x88000000;

/// initiate the frame allocator using `ekernel` and `MEMORY_END`
pub fn init_frame_allocator() {
    extern "C" {
        fn ekernel();
    }
    FRAME_ALLOCATOR.exclusive_access().init(
        PhysAddr::from(ekernel as usize).ceil(),
        PhysAddr::from(MEMORY_END).floor(),
    );
}

第三部分页表管理，记录内核以及进程的地址空间

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
/// 一个进程或者内核的地址空间
pub struct MemorySet {
    page_table: PageTable,
    areas: Vec<MapArea>, // 多个映射区段，不保证有序
}

/// 真实生效的页表，维护PTE
pub struct PageTable {
    root_ppn: PhysPageNum, // 指向页表所在的物理页，其上保存PTE
    frames: Vec<FrameTracker>,
}

/// 预备页映射关系
pub struct MapArea {
    vpn_range: VPNRange, // 页范围
    data_frames: BTreeMap<VirtPageNum, FrameTracker>,
    map_type: MapType,
    map_perm: MapPermission,
}

/// 一段连续的虚拟页
pub type VPNRange = SimpleRange<VirtPageNum>;

/// 用RAII风格管理的物理页
pub struct FrameTracker {
    /// physical page number
    pub ppn: PhysPageNum,
}

MapArea 结构表示一段连续的虚拟内存映射，用于快捷修改page_table。

内存映射分为两种类型：

  • Identical：虚拟页号 X 映射到物理页号 X
  • Framed：虚拟页映射到临时分配的物理页

相关方法：

  • MapArea::map(self, page_table) 修改page_table，执行自身所描述的映射
  • MapArea::unmap(self, page_table) 修改page_table，取消自身所描述的映射
  • MapArea::append_to(self, page_table, new_end) 修改page_table，更新自身描述的映射的结束位置
  • MapArea::shrink_to(self, page_table, new_end) 修改page_table，更新自身描述的映射的结束位置

跳板页映射：把地址空间最高的地址映射到 strampoline 页

1
2
3
4
5
6
7
8
9
pub const TRAMPOLINE: usize = usize::MAX - PAGE_SIZE + 1;

fn map_trampoline(&mut self) {
    self.page_table.map(
        VirtAddr::from(TRAMPOLINE).into(),
        PhysAddr::from(strampoline as usize).into(),
        PTEFlags::R | PTEFlags::X,
    );
}

#Chapter 6 文件系统

与内存类似，硬盘也被分成固定大小的块，按照 block_id 读写。rCore 采用的块大小为 512 字节。

#块读写层

  • BlockDevice::read_block(&self, block_id: usize, buf) 从硬盘上读取一个块
  • BlockDevice::write_block(&self, block_id: usize, buf) 在硬盘上写入一个块

目前只有一个 VirtIOBlock 实现了这个 trait

#硬盘块缓存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/// Cached block inside memory
pub struct BlockCache {
    /// cached block data
    cache: [u8; BLOCK_SZ],
    /// underlying block id
    block_id: usize,
    /// underlying block device
    block_device: Arc<dyn BlockDevice>,
    /// whether the block is dirty
    modified: bool,
}

impl BlockCache {
    pub fn read<T, V>(&self, offset: usize, f: impl FnOnce(&T) -> V) -> V {
        f(self.get_ref(offset))
    }

    pub fn modify<T, V>(&mut self, offset: usize, f: impl FnOnce(&mut T) -> V) -> V {
        f(self.get_mut(offset))
    }
}

提供了read和modify两个 API 用于读和写一个硬盘块，读和写的操作需要作为一个FnOnce回调函数传入。

缓存块的管理内部使用了一个队列：

1
2
3
4
5
6
7
8
9
10
11
pub struct BlockCacheManager {
    queue: VecDeque<(usize, Arc<Mutex<BlockCache>>)>,
}

impl BlockCacheManager {
    pub fn get_block_cache(
        &mut self,
        block_id: usize,
        block_device: Arc<dyn BlockDevice>,
    ) -> Arc<Mutex<BlockCache>> { ... }
}

get_block_cache(block_id, block_device) 用于获取对应块的 BlockCache。

#EasyFS 文件系统

1
2
3
4
5
6
7
8
9
10
11
12
/// An easy file system on block
pub struct EasyFileSystem {
    /// Real device
    pub block_device: Arc<dyn BlockDevice>,
    /// Inode bitmap
    pub inode_bitmap: Bitmap,
    /// Data bitmap
    pub data_bitmap: Bitmap,
    /// Inode区块范围
    inode_area_start_block: u32,
    data_area_start_block: u32,
}

文件系统结构：

  • [0]：超级块；
  • [1, 1+inode_bitmap_blocks)：inode 位图区
    • 大小：共inode_bitmap_blocks个块，每个块大小是 512 字节，能够表示 4k 个状态位
    • 记录每一个inode是否被使用
  • [inode_area_start_block, ]：inode 区
    • 保存位图区能表示数量的inode
    • inode连续存储，总大小取整到 block 边界
    • inode按顺序编号，从 0 开始
  • [...]：data 位图区
  • [data_area_start_block, total_blocks)：data 区

超级块：

1
2
3
4
5
6
7
8
pub struct SuperBlock {
    magic: u32,  // 0x3b800001
    pub total_blocks: u32,
    pub inode_bitmap_blocks: u32,
    pub inode_area_blocks: u32,
    pub data_bitmap_blocks: u32,
    pub data_area_blocks: u32,
}

inode 结构设计：

1
2
3
4
5
6
7
8
9
/// A disk inode
#[repr(C)]
pub struct DiskInode {
    pub size: u32,
    pub direct: [u32; INODE_DIRECT_COUNT],
    pub indirect1: u32,
    pub indirect2: u32,
    type_: DiskInodeType,
}

inode 采用了经典的三级索引设计，有 28 个直接条目；1 个间接索引，包含 128 个条目；1 个二级间接索引，包含 128 个间接索引，等于128*128个直接条目。

Easyfs 中的0号inode是文件系统的根节点。

Easyfs 没有多级目录设计。

#Chapter 8 同步机制

死锁检测：

  • 用一个全局变量记录每个task的hold和wait集合，即当前持有的资源（及数量）和正在等待的资源。
  • 在尝试获取资源（即加锁）时，进行死锁检测。

死锁检测算法就是对未来的执行状态进行模拟：找到下一个可以执行的任务，模拟执行，然后释放它拥有的资源，循环。当所有任务都可以执行，说明不存在死锁；否则就是存在死锁。