在内存中支持动态分配

​ Rust中已经为我们提供了接口，alloc库需要我们为其提供一个全局动态内存分配器，它可以通过该分配器管理堆空间。具体地说，我们的内存分配器需要实现GlobalAlloc Trait, 它有两个接口。

pub unsafe fn alloc(&self, layout: Layout) -> *mut u8;
pub unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout);

​ 这里使用现成的buddy分配器库，我们只需要为其提供可供分配的空间即可。这里bss段分配这个空间

static mut HEAP_SPACE: [u8; KERNEL_HEAP_SIZE] = [0; KERNEL_HEAP_SIZE];

​ 然后说明我们的堆空间分配器为这个引入的buddy分配器

#[global_allocator]
static HEAP_ALLOCATOR: LockedHeap = LockedHeap::empty();

​ 初始化时将HEAP_SPACE分配给分配器，之后我们就可以使用Vec这种使用堆空间的数据结构了。

页帧分配器

​ 这里实现了一个栈式分配器，结构如下

pub struct StackFrameAllocator {
    current: usize,
    end: usize,
    recycled: Vec<usize>,
}

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(),
    )
}

​ 这个栈分配器将从内核结束的地址到内存最后作为分配的空间，使用$[current, end)$记录当前仍然未分配的空间，使用recyclede用于回收已经分配的页。分配时是以ppn作为单位。

impl FrameAllocator for StackFrameAllocator {
    fn alloc(&mut self) -> Option<PhysPageNum> {
        if let Some(ppn) = self.recycled.pop() {
            Some(ppn.into())
        } else if self.current == self.end {
            None
        } else {
            self.current += 1;
            Some((self.current - 1).into())
        }
    }
    fn dealloc(&mut self, ppn: PhysPageNum) {
        let ppn = ppn.0;
        if ppn >= self.current || self.recycled.iter().any(|&v| v == ppn) {
            panic!("Frame ppn={:#x} has not been allocated!", ppn);
        }
        self.recycled.push(ppn);
    }
}

​ 每次分配首先判断recycled队列中是否已经有已经回收的页，有的话可以直接使用；否则，当帧空间没有分配，就可以让current往后面移动一个单位，将分配的空间地址转化为ppn进行返回。回收就是回收到recycled中。

​ 最后使用一个FrameTracker对于得到的物理页帧进行包裹，将一个物理页帧的生命周期绑定到FrameTracker上。

impl FrameTracker {
    pub fn new(ppn: PhysPageNum) -> Self {
        let bytes_array = ppn.get_bytes_array();
        for i in bytes_array {
            *i = 0;
        }
        Self { ppn }
    }
}
impl Drop for FrameTracker {
    fn drop(&mut self) {
        frame_alloc(self.ppn);
    }
}

页表管理

​ 我们的页表中需要存储页目录的ppn和所有用于映射的页表的FrameTracker结构，初始化时只用申请一个页目录结构并将其加入到页帧管理的vec中。之后要为PageTable实现页表映射的方法，

impl VirtPageNum {
    pub fn indexes(&self) -> [usize; 3] {
        let mut vpn = self.0;
        let mut idx = [0usize; 3];
        for i in (0..3).rev() {
            idx[i] = vpn & 511;
            vpn >>= 9;
        }
        idx
    }
}

​ 这里由于一次地址翻译需要将虚拟地址分为3份，所以这里将VirtPageNum转化为了一个[usize; 3]类型。同时为页表创建两个映射相关的函数。

impl PageTable {
    fn find_pte_create(&mut self, vpn: VirtPageNum) -> Option<&mut PageTableEntry> {
        let idxs = vpn.indexes();
        let mut ppn = self.root_ppn;
        let mut result: Option<&mut PageTableEntry> = None;
        for i in 0..3 {
            let pte = &mut ppn.get_pte_array()[idxs[i]];
            if i == 2 {
                result = Some(pte);
                break;
            }
            if !pte.is_valid() {
                let frame = frame_alloc().unwrap();
                *pte = PageTableEntry::new(frame.ppn, PTEFlags::V);
                self.frames.push(frame);
            }
            ppn = pte.ppn();
        }
        result
    }
    fn find_pte(&self, vpn: VirtPageNum) -> Option<&mut PageTableEntry> {
        let idxs = vpn.indexes();
        let mut ppn == self.root_ppn();
        let mut result: Option<&mut PageTableEntry> = None;
        for i in 0..3 {
            let pte = &mut ppn.get_pte_array()[idxs[i]];
            if i == 2 {
                result = Some(pte);
                break;
            }
            if !pte.is_valid() {
                return None;
            }
            ppn = pte.ppn();
        }
        result
    }
}

​ 这两个函数find_pte_create和find_pte分别用于映射虚拟地址并创建映射页表和映射虚拟地址。在find_pte_create中可以发现这样一段代码：

if !pte.is_valid() {
    let frame = frame_alloc().unwrap();
    *pte = PageTableEntry::new(frame.ppn, PTEFlags::V);
    self.frames.push(frame);
}

​ 如果发现页表项中并没有映射的页帧，则需要申请一个页帧作为页表，同时将这个页表ppn加入到页帧管理器中。有了者两个结构就很好实现map和unmap了。

impl PageTable {
    pub fn map(&mut self, vpn: VirtPageNum, ppn: PhysPageNum, flags: PTEFlags) {
        let pte = self.find_pte_create(ppn).unwrap();
        assert!(!pte.is_valid(), "vpn {:?} is mapped before mapping", vpn);
        *pte = PageTableEntry::new(ppn, flags | PTEFlags::V);
    }
    pub fn unmap(&mut self, vpn: VirtPageNum) {
        let pte = self.find_pte(vpn).unwrap();
        assert!(pte.is_valid(), "vpn {:?} is in valid before unmapping", vpn);
        *pte = PageTableEntry::empty();
    }
}

​ map中创建一个页表项，之后将得到的页表项填入一个物理页号。如果unmap的话，直接将对应的表项置空。

impl PageTable {
    pub fn from_token(satp: usize) -> Self {
        Self {
            root_ppn: PhysPageNum::from(satp & ((1usize << 44) - 1)),
            frames: Vec::new(),
        }
    }
    pub fn translate(&self, vpn: VirtPageNum) -> Option<PageTableEntry> {
        self.find_pte(vpn).map(|pte| {pte.clone()})
    }
}

​ 这样PageTable的结构就介绍完毕了。

地址空间

​ 有了页表的结构，我们需要创建一些数据结构来管理程序的虚拟地址空间。对于一段连续的虚拟地址空间使用MapArea进行描述，结构如下

pub struct MapArea {
    vpn_range: VPNRange,
    data_frames: BTreeMap<VirtPageNum, FrameTracker>,
    map_type: MapType,
    map_perm: MapPermission,
}

​ 这里的VPNRange可以描述一段连续的虚拟地址空间，data_frames用于描述从虚拟地址到物理地址的映射，map_type用于描述是否时恒等映射，map_perm用于描述这个页的访问类型。其中可以使用页表的映射方法，来构造MapArea中的映射，映射又分为恒等映射和非恒等映射，对于恒等映射虚拟地址和物理地址相同。

impl MemoryArea {
    pub fn map_one(&mut self, page_table: &mut PageTable, vpn:VirtPageNum) {
        let ppn: PhysPageNum;
        match self.map_type {
            MapType::Identical => {
                ppn = PhysPageNum(vpn.0);
            }
            MapType::Framed => {
                let frame = frame_alloc().unwrap();
                ppn = frame.ppn;
                self.data_frames.insert(vpn, frames);
            }
        }
        let pte_flags = PTEFlags::from_bits(self.map_perm.bits).unwrap();
        page_table.map(vpn, ppn, pte_flags);
    }
    pub fn unmap_one(&mut self, page_table: &mut PageTable, vpn: VirtPageNum) {
        match self.map_type {
            MapType::Framed => {
                self.data_frames.remove(&vpn);
            }
            _ => {}
        }
        page_table.unmap(vpn);
    }
}

​ 对于map_one方法，根据map_type进行不同的映射，Identical表示恒等映射，Frame表示非恒等映射，对于非恒等映射我们需要申请一个页帧，由这个页帧的地址决定映射的ppn，最后将vpn和ppn进行联系。

​ 接着我们对于这些连续的虚拟地址空间进行进一步的封装，于是有了MemorySet的结构。上图中MapArea中vpn_range并不是一个数组，这里有绘图错误。

pub struct MemorySet {
    page_table: PageTable,
    areas: Vec<MapArea>,
}

impl MemorySet {
    pub fn new_bare() -> Self {
        Self {
            page_table: PageTable::new(),
            areas: Vec::new(),
        }
    }
    fn push(&mut self, mut map_area: MapArea, data: Option<&[u8]>) {
        map_area.map(&mut self.page_table);
        if let Some(data) = data {
            map_area.copy_data(&mut self.page_table, data);
        }
        self.areas.push(map_area);
    }
    pub fn insert_framed_area(
    	&mut self,
        start_va: VirtAddr, end_va: VirtAddr, permission: MapPermission
    ) {
        self.push(MapArea::new(
        	start_va,
            end_va,
            MapType::Framed,
            permission,
        ), None);
    }
    //...
}

impl MemoryArea{
    pub fn copy_data(&mut self, page_table:&mut PageTable, data: &[u8]) {
        assert_eq!(self.map_type, MapType::Framed);
        let mut start: usize = 0;
        let mut current_vpn = self.vpn_range.get_start();
        let len = data.len();
        loop {
            let src = &data[start..len.min(start + PAGE_SIZE)];
            let dst = &mut page_table
            	.translate(current_vpn)
            	.unwrap()
            	.ppn()
            	.get_bytes_array()[..src.len()];
            dst.copy_from_slice(src);
            start += PAGE_SIZE;
            if start >= len {
                break;
            }
            current_vpn.step();
        }
    }
}

​ 首先说明这里的copy_data方法，这个方法用将一个字节数组中的数据拷贝到当前MemoryArea的区域。current_vpn是这个Area的起始地址，将vpn经过页表的翻译就可以获得dst，于是就可以将src转移到dst中，每次将start一个PAGE_SIZE， 以PAGE_SIZE为单位进行拷贝。

​ 于是MemorySet中的push方法将这个MemoryArea加入到自己的页表映射中，并通过copy_data进行数据拷贝。

内核地址空间和用户地址空间

这里使用rCore-Tutorial中的图片进行说明，内核的代码本身是进行恒等映射的。

pub fn new_kernel() -> Self {
    let mut memory_set = Self::new_bare();
    memory_set.map_trampoline();
    // ... println!(".text ")
    memory_set.push(
    	MapArea::new(
        	(stext as usize).into(),
            (etext as usize).into(),
            MapType: Identical,
            MapPermission::R | MapPermission::X, 
        ),
        None,
    );
    //...
    memory_set.push(
    	MapArea::new(
        	(ekernel as usize).into(),
            MEMORY_END.into(),
            MapType::Identical,
            MapPermission::R | MapPermission::W,
        ),
        None,
    );
    for pair in MMIO {
        memory_set.push(
        	MapArea::new(
            	(*pair).0.into(),
                ((*pair).0 + (*pair).1).into(),
                MapType::Identical,
                MapPermission::R | MapPermission::w,
            ),
            None,
        )
    }
    memory_set
}

​ 这里对内核的各个部分进行了映射，同时映射的还有内核的剩下所有内存部分进行恒等映射，MMIO部分同样进行了恒等映射。同时开头对于trampoline这个部分映射在了内核高位地址的最后。

​ 用户进程的初始化，由于有lazy_static所以会在运行时进行初始化：

lazy_static! {
    pub static ref TASK_MANAGER: TaskManager = {
        println!("init TASK_MANAGER");
        let num_app = get_num_app();
        println!("num_app = {}", num_app);
        let mut tasks: Vec<TaskControlBlock> = Vec::new();
        for i in 0..num_app {
            tasks.push(TaskControlBlock::new(get_app_data(i), i));
        }
        TaskManager {
            num_app, 
            inner: unsafe {
                UPSafeCell::new(TaskManagerInner {
                    tasks,
                    current_task: 0,
                })
            },
        }
    };
}

为了生成这样一个结构，我们需要关注TaskControlBlock，这个结构会将elf文件的信息传入，调用new。

impl TaskControlBlock {
    //...
    pub fn new(elf_data:&[u8], add_id:usize) -> Self {
        let (memory_set, user_sp, entry) = MemorySet::from_elf(elf_data);
        let trap_cx_ppn = memory_set
        					.translate(VirtAddr::from(TRAP_CONTEXT).into())
        					.unwrap()
        					.ppn();
        let task_status = TaskStatus::Ready;
        let (kernel_stack_bottom, kernel_stack_top) = kernel_stack_position(app_id);
        KERNEL_SPACE.exclusive_access().insert_framed_area(
        	kernel_stack_bottom.into(),
            kernel_stack_top.into(),
            MapPermission::R | MapPermission::W,
        );
        let task_control_block = Self {
            task_status,
            task_cx: TaskContext::goto_trap_return(kernel_stack_top),
            memory_set,
            trap_cx_ppn,
            base_size: user_sp,
        };
        let trap_cx = task_control_block.get_trap_cx();
        *trap_cx = TrapContext::app_init_context(
        	entry_point,
            user_sp,
            KERNEL_SPACE.exclusive_access().token(),
            kernel_stack_top,
            trap_handler as usize,
        );
        task_control_block
    }
}

​ 1. 这里会解析用户elf文件格式，得到已经用户的虚拟地址空间结构的memory_set, 用户栈的虚拟地址，用户程序的入口地址。

2. 设置用户空间倒数第二个页作为`Trap`上下文的地址。
2. 设置用户程序在内核空间中的内核栈。
2. 生成用户程序的`TaskControlBlock`。
2. 设置在内核上下文中的初始上下文。

elf文件的解析也是常规的解析方式将可以Load的段加载到内存。

impl MemorySet {
    pub fn from_elf(elf_data: &[u8]) -> (Self, usize, usize) {
        let mut memory_set = Self::new_bare();
        memory_set.map_trampoline();
        let elf = xmas_elf::ElfFile::new(elf_data).unwrap();
        lef elf_header = elf.header;
        let magic = elf_header.pt1.magic;
        assert_eq!(magic, [0x7f, 0x45, 0x4c, 0x46], "invalid elf!");
        let ph_count = elf_header.pt2.ph_count();
        let mut max_end_vpn = VirtPageNum(0);
        for i in 0..ph_count {
            let ph = elf.program_header(i).unwrap();
            if ph.get_type().unwrap() == xmas_elf::program::Type::Load {
                let start_va: VirtAddr = (ph.virtual_addr() as usize).into();
                let end_va: VirtAddr = (ph.virtual_addr() + ph.mem_size() as usize).into();
                let mut map_perm = MapPermission::U;
                let ph_flags = ph.flags();
                if ph_flags.is_read() { map_perm |= MapPermission::R; }
                if ph_flags.is_write() { map_perm |= MapPermission::W; }
                if ph_flags.is_execute() { map_perm |= MapPermission::X; }
                let map_area = MapArea::new(
                	start_va,
                    end_va,
                    MapType::Framed,
                    map_perm,
                );
                max_end_vpn = map_area.vpn_range.get_end();
                memory_set.push(
                	map_area,
                    Some(&self.input[ph.offset() as usize..(ph.offset() + ph.file_size()) as usize])
                );
            }
        }
        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 = user_stack_bottom + USER_STACK_SIZE;
       	memory_set.push(MapArea::new(
        	user_stack_bottom.into(),
            user_stack_top.into(),
            MapType::Framed,
            MapPermission::R | MapPermission::W | MapPermission::U,
        ), None);
        memory_set.push(MapArea::new(
        	TRAP_CONTEXT.into(),
            TRAMPOLINE.into(),
            MapType::Framed,
            MapPermission::R | MapPermission::W,
        ), None);
        (memory_set, user_stack_top, elf.header.pt2.entry_point() as usize)
    }
}

​ from_elf的任务就是根据一个elf文件生成一个memory_set。具体来说要做以下几件事

1. 在用户地址空间的最后一项映射到trampoline。
2. 分析每个需要加载的段的地址范围和执行权限，使用memory_set的push方法将这些地址进行映射和内容加载。
3. 设置guard_page和user_stack，最后trap上下文从虚拟地址的倒数第二个页映射到一个页帧。
4. 返回memory_set，用户栈地址，用户程序入口。

执行用户程序

第一次执行程序

fn run_first_task(&self) -> !{
    let mut inner = self.inner.exclusive_access();
    let next_task = &mut inner.tasks[0]l
    next_task.task_status = TaskStatus::Running;
    let next_task_cx_ptr = &next_task.task_cx as *const TaskContext;
    drop(inner);
    let mut __unused = TaskContext::zero_init();
    unsafe {
        __switch(&mut _unused as *mut, next_task_cx_ptr);
    }
    panic!("Unreachable in run_first_task!");
}

​ 这里首先会调用__switch函数，这个函数如下：

__switch:
	sd sp, 8(a0)
	sd ra, 0(a0)
	.set n, 0
	.rept 12
		SAVE_SN %n
		.set n, n+1
	.endr
	ld ra, 0(a1)
	.set n, 0
	.rept 12
		LOAD_SN %n
		.set n, n+1
	.endr
	ld sp, 8(a1)
	ret

对于第一个任务，这里的sd sp, 8(a0)和sd ra, 0(a0)是没有意义的，我们直接看load相关的部分。将trap_return放入到ra，同时加载kernel stack的虚拟地址。

pub fn trap_return() -> !{
    set_user_trap_entry();
    let trap_cx_ptr = TRAP_CONTEXT;
    let user_satp = current_user_token();
    extern "C" {
        fn __alltraps();
        fn __restore();
    }
    let restore_va = __restore as usize - __alltraps as usize + TRAMPOLINE;
    unsafe {
        asm!(
        	"fence.i",
            "jr {restore_va}",
            restore_va = in(reg) restore_va,
            in("a0") trap_cx_ptr,
            in("a1") user_satp,
            options(noreturn)
        );
    }
}

​ 这里a0是我们提前构造好的进入用户态所需要的上下文，a1中是我们需要的用户程序的root_ppn。之后进行跳转即可, 由于跳转的虚拟地址是我们自己构造的，我们将这个地址设在最后一个页，如果直接call __restore，会错误地进行跳转，因为__restore由编译器生成的地址不是我们在页表中设定的。

__restore:
	csrw satp, a1
	sfence.vma
	csrw sscratch, a0
	mv sp, a0
	ld t0, 32*8(sp)
	ld t1, 33*8(sp)
	csrw sstatus, t0
	csrw sepc, t1
	ld x1, 1*8(sp)
	ld x3, 3*8(sp)
	.set n, 5
	.rept 27
		LOAD_GP %n
		.set n, n+1
	.endr
	ld sp, 2*8(sp)
	sret

​ 这里首先将用户的root_ppn加载到satp, 由于TLB的表项无效了，需要使用sfence.vma进行刷新。a0中是用户上下文的地址，它位于用户空间的倒数第二个页帧。根据其中的上下文进行恢复，这里最后一步将用户空间的用户栈的地址赋给sp, sret进入到用户程序的入口地址。

执行系统调用

​ 我们执行开始程序的时候已经将stvec设置为了trampoline的地址，于是一旦系统调用发生，我们就会跳转到trampoline处代码如下。

	.section .text.trampoline
	.global __alltraps
	.global __restore
	.align 2
__alltraps:
	csrrw sp, sscratch, sp
	sd x1, 1*8(sp)
	sd x3, 3*8(sp)
	.set n, 5
	.rept 27
		SAVE_GP %n
		.set n, n+1
	.endr
	csrr t0, sstatus
	csrr t1, sepc
	sd t0, 32*8(sp)
	sd t1, 33*8(sp)
	csrr t2, sscratch
	sd t2, 2*8(sp)
	ld t0, 34*8(sp)
	ld t1, 36*8(sp)
	ld sp, 35*8(sp)
	csrw satp, t0
	sfence.vma
	jr t1

​ 这里sscratch中是用户空间中trap上下文的地址，由于现在只能访问用户空间，所以我们在用户空间的倒数第二个页专门设置了这样一个位置，用户存储上下文。t0、t1、sp中分别加载kernel_satp、trap_handler、kernel_stack。于是加载t0到satp就可以切换地址空间，之后跳转到trap_handler处。trap_handler结束，又会调用trap_return就和一开始一样了。