物理内存探测与管理

我们知道，物理内存通常是一片 RAM ，我们可以把它看成一个以字节为单位的大数组，通过物理地址找到对应的位置进行读写。但是，物理地址并不仅仅只能访问物理内存，也可以用来访问其他的外设，因此你也可以认为物理内存也算是一种外设。

这样设计是因为：如果访问其他外设要使用不同的指令（如 x86 单独提供了in, out 指令来访问不同于内存的IO地址空间），会比较麻烦，于是很多 CPU（如 RISC-V，ARM，MIPS 等）通过 MMIO(Memory Mapped I/O) 技术将外设映射到一段物理地址，这样我们访问其他外设就和访问物理内存一样啦！

我们先不管那些外设，来看物理内存。

物理内存探测

操作系统怎样知道物理内存所在的那段物理地址呢？在 RISC-V 中，这个一般是由 bootloader ，即 OpenSBI 来完成的。它来完成对于包括物理内存在内的各外设的扫描，将扫描结果以 DTB(Device Tree Blob) 的格式保存在物理内存中的某个地方。随后 OpenSBI 会将其地址保存在 a1 寄存器中，给我们使用。

这个扫描结果描述了所有外设的信息，当中也包括 Qemu 模拟的 RISC-V 计算机中的物理内存。

Qemu 模拟的 RISC-V virt 计算机中的物理内存

通过查看virt.c的virt_memmap[]的定义，可以了解到 Qemu 模拟的 RISC-V virt 计算机的详细物理内存布局。可以看到，整个物理内存中有不少内存空洞（即含义为unmapped的地址空间），也有很多外设特定的地址空间，现在我们看不懂没有关系，后面会慢慢涉及到。目前只需关心最后一块含义为DRAM的地址空间，这就是 OS 将要管理的 128MB 的内存空间。

起始地址终止地址含义
0x00x100QEMU VIRT_DEBUG
0x1000x1000unmapped
0x10000x12000QEMU MROM (包括 hard-coded reset vector; device tree)
0x120000x100000unmapped
0x1000000x101000QEMU VIRT_TEST
0x1010000x2000000unmapped
0x20000000x2010000QEMU VIRT_CLINT
0x20100000x3000000unmapped
0x30000000x3010000QEMU VIRT_PCIE_PIO
0x30100000xc000000unmapped
0xc0000000x10000000QEMU VIRT_PLIC
0x100000000x10000100QEMU VIRT_UART0
0x100001000x10001000unmapped
0x100010000x10002000QEMU VIRT_VIRTIO
0x100020000x20000000unmapped
0x200000000x24000000QEMU VIRT_FLASH
0x240000000x30000000unmapped
0x300000000x40000000QEMU VIRT_PCIE_ECAM
0x400000000x80000000QEMU VIRT_PCIE_MMIO
0x800000000x88000000DRAM 缺省 128MB，大小可配置

不过为了简单起见，我们并不打算自己去解析这个结果。因为我们知道，Qemu 规定的 DRAM 物理内存的起始物理地址为 0x80000000 。而在 Qemu 中，可以使用 -m 指定 RAM 的大小，默认是

物理内存探测与管理 - 图1

。因此，默认的 DRAM 物理内存地址范围就是 [0x80000000,0x88000000) 。我们直接将 DRAM 物理内存结束地址硬编码到内核中：

  1. // src/lib.rs
  3. mod consts;
  5. // src/consts.rs
  7. pub const PHYSICAL_MEMORY_END: usize = 0x88000000;

但是，有一部分 DRAM 空间已经被占用，不能用来存别的东西了！

  • 物理地址空间 [0x80000000,0x80200000) 被 OpenSBI 占用；
  • 物理地址空间 [0x80200000,KernelEnd) 被内核各代码与数据段占用；
  • 其实设备树扫描结果 DTB 还占用了一部分物理内存，不过由于我们不打算使用它，所以可以将它所占用的空间用来存别的东西。

于是，我们可以用来存别的东西的物理内存的物理地址范围是：[KernelEnd, 0x88000000) 。这里的 KernelEnd​ 为内核代码结尾的物理地址。在 linker64.ld 中定义的 end 符号为内核代码结尾的虚拟地址，我们需要通过偏移量来将其转化为物理地址。

我们来将可用的物理内存地址范围打印出来：

  1. // src/consts.rs
  3. pub const KERNEL_BEGIN_PADDR: usize = 0x80200000;
  4. pub const KERNEL_BEGIN_VADDR: usize = 0x80200000;
  6. // src/init.rs
  8. use crate::consts::*;
  10. #[no_mangle]
  11. pub extern "C" fn rust_main() -> ! {
  12.     extern "C" {
  13.         fn end();
  14.     }
  15.     println!(
  16.         "free physical memory paddr = [{:#x}, {:#x})",
  17.         end as usize - KERNEL_BEGIN_VADDR + KERNEL_BEGIN_PADDR,
  18.         PHYSICAL_MEMORY_END
  19.     );
  20.     crate::interrupt::init();
  21.     crate::timer::init();
  22.     loop {}
  23. }

可用物理内存地址

free physical memory paddr = [0x8020b000, 0x88000000)

物理页帧与物理页号

通常，我们在分配物理内存时并不是以字节为单位，而是以一物理页帧(Frame)，即连续的

物理内存探测与管理 - 图2

字节为单位分配。我们希望用物理页号(Physical Page Number, PPN) 来代表一物理页，实际上代表物理地址范围在

物理内存探测与管理 - 图3

的一物理页。

不难看出，物理页号与物理页形成一一映射。为了能够使用物理页号这种表达方式，每个物理页的开头地址必须是

物理内存探测与管理 - 图4

的倍数。但这也给了我们一个方便：对于一个物理地址，其除以

物理内存探测与管理 - 图5

(或者说右移

物理内存探测与管理 - 图6

位) 的商即为这个物理地址所在的物理页号。

以这种方式，我们看一下可用物理内存的物理页号表达。将 init.rs 中的输出语句略做改动：

  1. // src/init.rs
  3. println!(
  4.         "free physical memory ppn = [{:#x}, {:#x})",
  5.         ((end as usize - KERNEL_BEGIN_VADDR + KERNEL_BEGIN_PADDR) >> 12) + 1,
  6.         PHYSICAL_MEMORY_END >> 12
  7. );

可用物理页号区间

free physical memory ppn = [0x8020c, 0x88000)

物理内存页式管理

对于物理内存的页式管理而言，我们所要支持的操作是：

  1. 分配一个物理页，返回其物理页号；
  2. 给定一个物理页号，回收其对应的物理页。
  3. 给定一个页号区间进行初始化。

我们考虑用一颗非递归线段树来维护这些操作。节点上的值存的是

物理内存探测与管理 - 图7

表示这个节点对应的区间内是否还有空闲物理页（0=空闲，1=被占用）。

  1. // src/const.rs
  3. pub const MAX_PHYSICAL_MEMORY: usize = 0x8000000;
  4. pub const MAX_PHYSICAL_PAGES: usize = MAX_PHYSICAL_MEMORY >> 12;
  6. // src/lib.rs
  8. mod memory;
  10. // src/memory/mod.rs
  12. mod frame_allocator;
  14. // src/memory/frame_allocator.rs
  16. use crate::consts::MAX_PHYSICAL_PAGES;
  18. pub struct SegmentTreeAllocator {
  19.     a: [u8; MAX_PHYSICAL_PAGES << 1],
  20.     m: usize,
  21.     n: usize,
  22.     offset: usize
  23. }
  25. impl SegmentTreeAllocator {
  26.     // 使用物理页号区间 [l,r) 进行初始化
  27.     pub fn init(&mut self, l: usize, r: usize) {
  28.         self.offset = l - 1;
  29.         self.n = r - l;
  30.         self.m = 1;
  31.         while self.m < self.n + 2 {
  32.             self.m = self.m << 1;
  33.         }
  34.         for i in (1..(self.m << 1)) { self.a[i] = 1; }
  35.         for i in (1..self.n) { self.a[self.m + i] = 0; }
  36.         for i in (1..self.m).rev() { self.a[i] = self.a[i << 1] & self.a[(i << 1) | 1]; }
  37.     }
  38.     // 分配一个物理页
  39.     // 自上而下寻找可用的最小物理页号
  40.     // 注意，我们假定永远不会出现物理页耗尽的情况
  41.     pub fn alloc(&mut self) -> usize {
  42.         // assume that we never run out of physical memory
  43.         if self.a[1] == 1 {
  44.             panic!("physical memory depleted!");
  45.         }
  46.         let mut p = 1;
  47.         while p < self.m {
  48.             if self.a[p << 1] == 0 { p = p << 1; } else { p = (p << 1) | 1; }
  49.         }
  50.         let result = p + self.offset - self.m;
  51.         self.a[p] = 1;
  52.         p >>= 1;
  53.         while p > 0 {
  54.             self.a[p] = self.a[p << 1] & self.a[(p << 1) | 1];
  55.             p >>= 1;
  56.         }
  57.         result
  58.     }
  59.     // 回收物理页号为 n 的物理页
  60.     // 自下而上进行更新
  61.     pub fn dealloc(&mut self, n: usize) {
  62.         let mut p = n + self.m - self.offset;
  63.         assert!(self.a[p] == 1);
  64.         self.a[p] = 0;
  65.         p >>= 1;
  66.         while p > 0 {
  67.             self.a[p] = self.a[p << 1] & self.a[(p << 1) | 1];
  68.             p >>= 1;
  69.         }
  70.     }
  71. }

事实上每次分配的是可用的物理页号最小的页面，具体实现方面就不赘述了。

我们还需要将这个类实例化并声明为 static ，因为它在整个程序 运行过程当中均有效。

  1. // os/Cargo.toml
  3. [dependencies]
  4. spin = "0.5.2"
  6. // src/memory/frame_allocator.rs
  8. use spin::Mutex;
  10. pub static SEGMENT_TREE_ALLOCATOR: Mutex<SegmentTreeAllocator> = Mutex::new(SegmentTreeAllocator {
  11.     a: [0; MAX_PHYSICAL_PAGES << 1],
  12.     m: 0,
  13.     n: 0,
  14.     offset: 0
  15. });

我们注意到在内核中开了一块比较大的静态内存，a 数组。那么 a 数组究竟有多大呢？实际上 a 数组的大小为最大可能物理页数的二倍，因此 a 数组大小仅为物理内存大小的

物理内存探测与管理 - 图8

，可说是微乎其微。

我们本来想把 SEGMENT_TREE_ALLOCATOR 声明为 static mut 类型，这是因为首先它需要是 static 类型的；其次，它的三个方法 init, alloc, dealloc 都需要修改自身。

但是，对于 static mut 类型的修改操作是 unsafe 的。我们之后会提到线程的概念，对于 static 类型的静态数据，所有的线程都能访问。当一个线程正在访问这段数据的时候，如果另一个线程也来访问，就可能会产生冲突，并带来难以预测的结果。

所以我们的方法是使用 spin::Mutex<T> 给这段数据加一把锁，一个线程试图通过 .lock() 打开锁来获取内部数据的可变引用，如果钥匙被别的线程所占用，那么这个线程就会一直卡在这里；直到那个占用了钥匙的线程对内部数据的访问结束，锁被释放，将钥匙交还出来，被卡住的那个线程拿到了钥匙，就可打开锁获取内部引用，访问内部数据。

这里使用的是 spin::Mutex<T> ， 我们在 Cargo.toml 中添加依赖。幸运的是，它也无需任何操作系统支持（即支持 no_std），我们可以放心使用。

我们在 src/memory/mod.rs 里面再对这个类包装一下：

  1. // src/memory/mod.rs
  3. use frame_allocator::SEGMENT_TREE_ALLOCATOR as FRAME_ALLOCATOR;
  4. use riscv::addr::{
  5.     // 分别为虚拟地址、物理地址、虚拟页、物理页帧
  6.     // 非常方便，之后会经常用到
  7.     // 用法可参见 https://github.com/rcore-os/riscv/blob/master/src/addr.rs
  8.     VirtAddr,
  9.     PhysAddr,
  10.     Page,
  11.     Frame
  12. };
  14. pub fn init(l: usize, r: usize) {
  15.     FRAME_ALLOCATOR.lock().init(l, r);
  16.     println!("++++ setup memory!    ++++");
  17. }
  18. pub fn alloc_frame() -> Option<Frame> {
  19.     //将物理页号转为物理页帧
  20.     Some(Frame::of_ppn(FRAME_ALLOCATOR.lock().alloc()))
  21. }
  22. pub fn dealloc_frame(f: Frame) {
  23.     FRAME_ALLOCATOR.lock().dealloc(f.number())
  24. }

现在我们来测试一下它是否能够很好的完成物理页分配与回收：

  1. // src/init.rs
  3. use crate::memory::{
  4.     alloc_frame,
  5.     dealloc_frame
  6. };
  8. #[no_mangle]
  9. pub extern "C" fn rust_main() -> ! {
  10.     extern "C" {
  11.         fn end();
  12.     }
  13.     println!("kernel end vaddr = {:#x}", end as usize);
  14.     println!(
  15.         "free physical memory ppn = [{:#x}, {:#x})",
  16.         ((end as usize - KERNEL_BEGIN_VADDR + KERNEL_BEGIN_PADDR) >> 12) + 1,
  17.         PHYSICAL_MEMORY_END >> 12
  18.     );
  19.     crate::interrupt::init();
  21.     crate::memory::init(
  22.         ((end as usize - KERNEL_BEGIN_VADDR + KERNEL_BEGIN_PADDR) >> 12) + 1,
  23.         PHYSICAL_MEMORY_END >> 12
  24.     );
  25.     frame_allocating_test();
  26.     crate::timer::init();
  28.     unsafe {
  29.         asm!("ebreak"::::"volatile");
  30.     }
  31.     panic!("end of rust_main");
  32.     loop {}
  33. }
  35. fn frame_allocating_test() {
  36.     println!("alloc {:x?}", alloc_frame());
  37.     let f = alloc_frame();
  38.     println!("alloc {:x?}", f);
  39.     println!("alloc {:x?}", alloc_frame());
  40.     println!("dealloc {:x?}", f);
  41.     dealloc_frame(f.unwrap());
  42.     println!("alloc {:x?}", alloc_frame());
  43.     println!("alloc {:x?}", alloc_frame());
  44. }

我们尝试在分配的过程中回收，之后再进行分配，结果如何呢？

物理页分配与回收测试

  1. free physical memory paddr = [0x8021f020, 0x88000000)
  2. free physical memory ppn = [0x80220, 0x88000)
  3. ++++ setup interrupt! ++++
  4. ++++ setup timer!     ++++
  5. ++++ setup memory!    ++++
  6. alloc Some(Frame(PhysAddr(80220000)))
  7. alloc Some(Frame(PhysAddr(80221000)))
  8. alloc Some(Frame(PhysAddr(80222000)))
  9. dealloc Some(Frame(PhysAddr(80221000)))
  10. alloc Some(Frame(PhysAddr(80221000)))
  11. alloc Some(Frame(PhysAddr(80223000)))
  12. * 100 ticks *
  13. * 100 ticks *
  14. ...

我们回收的页面接下来马上就又被分配出去了。

如果结果有问题的话，在这里能找到现有的代码。

不过，这种物理内存分配给人一种过家家的感觉。无论表面上分配、回收做得怎样井井有条，实际上都并没有对物理内存产生任何影响！不要着急，我们之后会使用它们的。