2024开源操作系统训练营 rCore Chapter6练习

编程作业

思路

linkat

本实验需要实现 3 个与文件系统相关的系统调用，首先是用来创建文件硬链接的 linkat.

首先介绍一下什么是硬链接，硬链接作为一种抽象概念，可以看作指向一个文件实体的指针，类似于 C++ 中的智能指针 shared_ptr。而从内核代码的角度来看，硬链接在文件系统中的实体就是 文件目录项 。每个硬链接对应一个目录项，这个目录项指向一个相同的索引节点（inode），每个 inode 存储了文件的实际数据块（的指针）及其元数据（文件大小、文件类型等）。

由于 rCore 的文件系统被简化为单级目录（只包含根目录），因此实现 linkat 的思路就很清晰了：根据文件名 old_name 查找其对应的 inode，获取 inode_id 并将引用计数加一，创建一个新的目录项 (new_name, inode_id)，将其插入根目录的数据段末尾。

需要注意的是，rCore 文件系统的 inode 分为虚拟文件系统层的 Inode 和在持久化设备（硬盘）上实际存储的 DistInode，可以通过 Inode 所实现的 read_disk_inode 和 modify_disk_inode 读取或修改其对应的 DiskInode。因此实际的代码实现，可以按照以下几个步骤进行：

1. 使用 self.find(old_name) 查找当前目录（ROOT_DIR）下的名为 old_name 的文件对应的 Inode，引用名为 inode。
2. 使用 self.read_disk_inode() 获取当前目录的 DiskInode 的只读引用。获取当前目录下 old_name 文件的 inode_id；获取当前目录的文件数据（目录的文件数据全部由目录项构成）的总大小，记为 offset，用于最后将新目录项添加至末尾。
3. 使用 inode.modify_disk_inode 获取 old_name 文件的 DiskInode 的可变引用。将其引用计数（原本没有该字段，需要自行添加）加一。
4. 创建新的目录项，并使用 self.write_at 将其写入偏移量为 offset 的位置。

/// Create a hard link with new_name for file with old_name
pub fn linkat(&self, old_name: &str, new_name: &str) -> isize {
    // get inode of file with old_name
    let inode = self.find(old_name);
    if inode.is_none() {
        return -1;
    }
    let inode = inode.unwrap();

    let mut id = 0;         // inode id
    let mut offset = 0;     // last position of data of inode
    self.read_disk_inode(|dinode| {
        id = self.find_inode_id(old_name, dinode).unwrap();
        offset = dinode.size as usize;
    });
    inode.modify_disk_inode(|dinode| {
        dinode.nlink += 1;  // increase reference count
    });
    let new_entry = DirEntry::new(new_name, id);

    // insert a new directory entry into ROOT_DIR
    self.write_at(offset, new_entry.as_bytes());
    0
}

unlinkat

第二个需要实现的是取消硬链接的 unlinkat，基本思路为：根据文件名 name 查找对应的 inode，将引用计数减一，最后将其根目录下对应的目录项移除。下面直接介绍具体实现方法：

1. 使用 self.find(name) 查找当前目录（ROOT_DIR）下的名为 name 的文件对应的 Inode，引用名为 inode。
2. 使用 inode.modify_disk_inode() 获取 inode 文件的 DiskInode 的可变引用。将引用计数减一，如果引用计数减为零，代表该文件的所有硬链接都被解除，此时可以使用 inode.clear() 释放该文件 inode 和数据的内存空间。
3. 使用 self.modify_disk_inode() 获取当前目录的 DiskInode 的可变引用。遍历当前目录下的所有目录项，将名称为 name 的目录项移除（为了实现的方便，可以直接用空的目录项覆写）。

在我的测试中，使用 inode.clear() 清空文件 inode 和数据内存空间的操作可能会在测试样例 ch6_file3 处超时，但测试样例不会对此进行测试，因此如果出现超时的情况，可以考虑移除这一操作。

/// Remove a hard link with name
pub fn unlinkat(&self, name: &str) -> isize {
    // get inode of file with name
    let inode = self.find(name);
    if inode.is_none() {
        return -1;
    }
    let inode = inode.unwrap();

    let mut is_zero_link = false;
    inode.modify_disk_inode(|dinode| {
        dinode.nlink -= 1;
        if dinode.nlink == 0 {
            is_zero_link = true;
        }
    });
    // Test will timeout with the code below, what the fuck??
    // Free memory of inode and file data
    if is_zero_link {
        inode.clear();
    }

    let mut res = -1;
    self.modify_disk_inode(|dinode| {
        // Remove(For simplisity, not remove, just set to empty)
        // the directory entry with name in the ROOT_DIR
        let fcnt = (dinode.size as usize) / DIRENT_SZ;
        for i in 0..fcnt {
            let mut dirent = DirEntry::empty();
            assert_eq!(
                dinode.read_at(i * DIRENT_SZ, dirent.as_bytes_mut(), &self.block_device),
                DIRENT_SZ
            );
            if dirent.name() == name {
                dirent = DirEntry::empty();
                dinode.write_at(i * DIRENT_SZ, dirent.as_bytes(), &self.block_device);
                res = 0;
                break;
            }
        }
    });
    res
}

fstat

第三个需要实现的是获取文件状态的 fstat，相较于 linkat 和 unlinkat 来说要复杂一些。

首先要解决的问题是：如何根据文件描述符 fd 获取其对应的 Inode 结构？这里必须要明确一个概念，所谓文件描述符，本质上只是一个无符号整型，其值为对应文件在当前进程文件描述符表中的 索引 。文件描述符表的元素为一个 trait 对象（在其他面向对象语言中相当于虚基类）dyn File，它表示一个抽象的“文件”实体。该“虚基类”有三种具体实现：标准输入 Stdin、标准输出 Stdout 和普通文件 OSInode，我们需要关注的便是 OSInode 的实现。

一种直接的想法是直接对 OSInode 数据结构进行扩展，为其实现 fstat 操作。但是请注意，文件描述符表的元素类型为虚基类 File，因此它无法直接调用其“派生类” OSInode 中所实现的方法，因此在这里我选择为 File 这个 trait 添加 get_stat 方法，并在 OSInode 中对其进行具体实现（Stdin 和 Stdout 也要实现，可以选择加一个 panic!("Not implemented!"); 进行占位）。

我对 Rust 还不太了解，不过我推测这里应该可以使用类似 C++ 中的动态类型转换 dynamic_cast 将 dyn File 类型转换为 OSInode，请读者批评指正。

构建起文件描述符到 Inode 的接口后，便可以开始具体实现 fstat 了，需要获取三个文件状态：inode_id、文件类型（普通文件或目录）、硬链接数量。接下来分别介绍：

首先是 inode_id，在 rCore 的文件系统实现中，inode_id（索引结点号）和文件描述符类似，也是 索引 ，指向其对应的 DiskInode 在 inode 位图中的位置。因此我们可以通过 Inode 结构中的 block_id 和 block_offset 将 inode_id 计算出来，计算方式如下：

/// Get inode id based upon block id and block offset
pub fn get_ino(&self, block_id: usize, block_offset: usize) -> usize {
    let inode_size = size_of::<DiskInode>();
    let inode_cnt = (BLOCK_SZ / inode_size) as usize;
    (block_id - self.inode_area_start_block as usize) * inode_cnt + block_offset / inode_size
}

文件类型和硬链接数量的获取比较简单，可以通过使用 read_disk_inode 获取 inode 对应的 DiskInode 的只读引用，并从中读取相关信息即可。

前向兼容

前向兼容可以借助 git cherry-pick 命令将其他分支的提交移植到当前分支，有关它的具体用法，可以参考我写的 Chapter5 练习中的介绍。

需要非常注意的一点是，spawn 系统调用移植后，需要添加 拷贝父进程文件描述符表 的操作，否则可能就会导致测试程序无法被正常加载（本章测试进程使用 spawn 系统调用进行创建）。

代码

diff --git a/easy-fs/src/efs.rs b/easy-fs/src/efs.rs
index 202b9eb..52828c2 100644
--- a/easy-fs/src/efs.rs
+++ b/easy-fs/src/efs.rs
@@ -1,3 +1,5 @@
+use core::mem::size_of;
+
 use super::{
     block_cache_sync_all, get_block_cache, Bitmap, BlockDevice, DiskInode, DiskInodeType, Inode,
     SuperBlock,
@@ -148,4 +150,11 @@ impl EasyFileSystem {
             (block_id - self.data_area_start_block) as usize,
         )
     }
+
+    /// Get inode id based upon block id and block offset
+    pub fn get_ino(&self, block_id: usize, block_offset: usize) -> usize {
+        let inode_size = size_of::<DiskInode>();
+        let inode_cnt = (BLOCK_SZ / inode_size) as usize;
+        (block_id - self.inode_area_start_block as usize) * inode_cnt + block_offset / inode_size
+    }
 }
diff --git a/easy-fs/src/layout.rs b/easy-fs/src/layout.rs
index 0a3ac79..692f5e7 100644
--- a/easy-fs/src/layout.rs
+++ b/easy-fs/src/layout.rs
@@ -70,7 +70,9 @@ impl SuperBlock {
 /// Type of a disk inode
 #[derive(PartialEq)]
 pub enum DiskInodeType {
+    /// file type
     File,
+    /// directory type
     Directory,
 }
 
@@ -86,6 +88,7 @@ pub struct DiskInode {
     pub indirect1: u32,
     pub indirect2: u32,
     type_: DiskInodeType,
+    pub nlink: u32,
 }
 
 impl DiskInode {
@@ -97,6 +100,7 @@ impl DiskInode {
         self.indirect1 = 0;
         self.indirect2 = 0;
         self.type_ = type_;
+        self.nlink = 1;
     }
     /// Whether this inode is a directory
     pub fn is_dir(&self) -> bool {
diff --git a/easy-fs/src/lib.rs b/easy-fs/src/lib.rs
index 822c237..d146f19 100644
--- a/easy-fs/src/lib.rs
+++ b/easy-fs/src/lib.rs
@@ -16,3 +16,4 @@ pub use block_dev::BlockDevice;
 pub use efs::EasyFileSystem;
 use layout::*;
 pub use vfs::Inode;
+pub use layout::DiskInodeType;
\ No newline at end of file
diff --git a/easy-fs/src/vfs.rs b/easy-fs/src/vfs.rs
index 9908385..cb56ad9 100644
--- a/easy-fs/src/vfs.rs
+++ b/easy-fs/src/vfs.rs
@@ -183,4 +183,93 @@ impl Inode {
         });
         block_cache_sync_all();
     }
+    /// Create a hard link with new_name for file with old_name
+    pub fn linkat(&self, old_name: &str, new_name: &str) -> isize {
+        // get inode of file with old_name
+        let inode = self.find(old_name);
+        if inode.is_none() {
+            return -1;
+        }
+        let inode = inode.unwrap();
+
+        let mut id = 0;         // inode id
+        let mut offset = 0;     // last position of data of inode
+        self.read_disk_inode(|dinode| {
+            id = self.find_inode_id(old_name, dinode).unwrap();
+            offset = dinode.size as usize;
+        });
+        inode.modify_disk_inode(|dinode| {
+            dinode.nlink += 1;  // increase reference count
+        });
+        let new_entry = DirEntry::new(new_name, id);
+
+        // insert a new directory entry into ROOT_DIR
+        self.write_at(offset, new_entry.as_bytes());
+        0
+    }
+    /// Remove a hard link with name
+    pub fn unlinkat(&self, name: &str) -> isize {
+        // get inode of file with name
+        let inode = self.find(name);
+        if inode.is_none() {
+            return -1;
+        }
+        let inode = inode.unwrap();
+
+        let mut is_zero_link = false;
+        inode.modify_disk_inode(|dinode| {
+            dinode.nlink -= 1;
+            if dinode.nlink == 0 {
+                is_zero_link = true;
+            }
+        });
+        // Test will timeout with the code below, what the fuck??
+        // Free memory of inode and file data
+        // if is_zero_link {
+        //     inode.clear();
+        // }
+        
+        let mut res = -1;
+        self.modify_disk_inode(|dinode| {
+            // Remove(For simplisity, not remove, just set to empty) 
+            // the directory entry with name in the ROOT_DIR
+            let fcnt = (dinode.size as usize) / DIRENT_SZ;
+            for i in 0..fcnt {
+                let mut dirent = DirEntry::empty();
+                assert_eq!(
+                    dinode.read_at(i * DIRENT_SZ, dirent.as_bytes_mut(), &self.block_device),
+                    DIRENT_SZ
+                );
+                if dirent.name() == name {
+                    dirent = DirEntry::empty();
+                    dinode.write_at(i * DIRENT_SZ, dirent.as_bytes(), &self.block_device);
+                    res = 0;
+                    break;
+                }
+            }
+        });
+        res
+    }
+    /// Get nlink of the inode
+    pub fn get_nlink(&self) -> u32 {
+        let mut nlink = 0;
+        self.read_disk_inode(|dinode| {
+            nlink = dinode.nlink;
+        });
+        nlink
+    }
+    /// Get file type of the inode
+    pub fn get_file_type(&self) -> DiskInodeType {
+        let mut ftype = DiskInodeType::File;
+        self.read_disk_inode(|dinode| {
+            if dinode.is_dir() {
+                ftype = DiskInodeType::Directory;
+            }
+        });
+        ftype
+    }
+    /// Get inode number of the inode
+    pub fn get_ino(&self) -> u32 {
+        let fs = self.fs.lock();
+        fs.get_ino(self.block_id, self.block_offset) as u32
+    }
 }
--- a/os/src/config.rs
+++ b/os/src/config.rs
@@ -25,3 +25,5 @@ pub const CLOCK_FREQ: usize = 12500000;
 pub const MEMORY_END: usize = 0x88000000;
 /// The base address of control registers in Virtio_Block device
 pub const MMIO: &[(usize, usize)] = &[(0x10001000, 0x1000)];
+/// big constant for process scheduling
+pub const BIG_STRIDE: isize = 1000_000;
diff --git a/os/src/fs/inode.rs b/os/src/fs/inode.rs
index 3f1f208..7c63086 100644
--- a/os/src/fs/inode.rs
+++ b/os/src/fs/inode.rs
@@ -4,14 +4,14 @@
 //!
 //! `UPSafeCell<OSInodeInner>` -> `OSInode`: for static `ROOT_INODE`,we
 //! need to wrap `OSInodeInner` into `UPSafeCell`
-use super::File;
+use super::{File, Stat, StatMode};
 use crate::drivers::BLOCK_DEVICE;
 use crate::mm::UserBuffer;
 use crate::sync::UPSafeCell;
 use alloc::sync::Arc;
 use alloc::vec::Vec;
 use bitflags::*;
-use easy_fs::{EasyFileSystem, Inode};
+use easy_fs::{DiskInodeType, EasyFileSystem, Inode};
 use lazy_static::*;
 
 /// inode in memory
@@ -55,6 +55,7 @@ impl OSInode {
 }
 
 lazy_static! {
+    /// The inode of root directory
     pub static ref ROOT_INODE: Arc<Inode> = {
         let efs = EasyFileSystem::open(BLOCK_DEVICE.clone());
         Arc::new(EasyFileSystem::root_inode(&efs))
@@ -155,4 +156,15 @@ impl File for OSInode {
         }
         total_write_size
     }
+    fn get_stat(&self) -> Stat {
+        let inner = self.inner.exclusive_access();
+        let ino = inner.inode.get_ino() as u64;
+        let mode = match inner.inode.get_file_type() {
+            DiskInodeType::File => StatMode::FILE,
+            DiskInodeType::Directory => StatMode::DIR,
+        };
+        let nlink = inner.inode.get_nlink();
+        Stat::new(ino, mode, nlink)
+    }
 }
diff --git a/os/src/fs/mod.rs b/os/src/fs/mod.rs
index 4c99179..522eb4f 100644
--- a/os/src/fs/mod.rs
+++ b/os/src/fs/mod.rs
@@ -15,6 +15,8 @@ pub trait File: Send + Sync {
     fn read(&self, buf: UserBuffer) -> usize;
     /// write to the file from buf, return the number of bytes written
     fn write(&self, buf: UserBuffer) -> usize;
+    /// get Stat of the inode
+    fn get_stat(&self) -> Stat;
 }
 
 /// The stat of a inode
@@ -33,6 +35,19 @@ pub struct Stat {
     pad: [u64; 7],
 }
 
+impl Stat {
+    /// Create a new Stat with default dev and pad
+    pub fn new(ino: u64, mode: StatMode, nlink: u32) -> Stat {
+        Stat {
+            dev: 0,
+            ino,
+            mode,
+            nlink,
+            pad: [0; 7],
+        }
+    }
+}
+
 bitflags! {
     /// The mode of a inode
     /// whether a directory or a file
@@ -46,5 +61,5 @@ bitflags! {
     }
 }
 
-pub use inode::{list_apps, open_file, OSInode, OpenFlags};
+pub use inode::{list_apps, open_file, OSInode, OpenFlags, ROOT_INODE};
 pub use stdio::{Stdin, Stdout};
diff --git a/os/src/fs/stdio.rs b/os/src/fs/stdio.rs
index 6075a65..8b5c36f 100644
--- a/os/src/fs/stdio.rs
+++ b/os/src/fs/stdio.rs
@@ -1,5 +1,5 @@
 //!Stdin & Stdout
-use super::File;
+use super::{File, Stat};
 use crate::mm::UserBuffer;
 use crate::sbi::console_getchar;
 use crate::task::suspend_current_and_run_next;
@@ -39,6 +39,9 @@ impl File for Stdin {
     fn write(&self, _user_buf: UserBuffer) -> usize {
         panic!("Cannot write to stdin!");
     }
+    fn get_stat(&self) -> Stat {
+        panic!("Not implemented!");
+    }
 }
 
 impl File for Stdout {
@@ -57,4 +60,7 @@ impl File for Stdout {
         }
         user_buf.len()
     }
+    fn get_stat(&self) -> Stat {
+        panic!("Not implemented!");
+    }
 }
diff --git a/os/src/mm/frame_allocator.rs b/os/src/mm/frame_allocator.rs
index 44f20cd..2fa6939 100644
--- a/os/src/mm/frame_allocator.rs
+++ b/os/src/mm/frame_allocator.rs
@@ -1,7 +1,7 @@
 //! Implementation of [`FrameAllocator`] which
 //! controls all the frames in the operating system.
 use super::{PhysAddr, PhysPageNum};
-use crate::config::MEMORY_END;
+use crate::config::{MEMORY_END, PAGE_SIZE};
 use crate::sync::UPSafeCell;
 use alloc::vec::Vec;
 use core::fmt::{self, Debug, Formatter};
@@ -134,3 +134,10 @@ pub fn frame_allocator_test() {
     drop(v);
     println!("frame_allocator_test passed!");
 }
+
+/// Check if the remaining physical memory is sufficient
+pub fn is_mem_sufficient(_len: usize) -> bool {
+    let fa = FRAME_ALLOCATOR.exclusive_access();
+    let page_cnt = fa.end - fa.current + fa.recycled.len();
+    (_len + PAGE_SIZE - 1) / PAGE_SIZE <= page_cnt
+}
diff --git a/os/src/mm/memory_set.rs b/os/src/mm/memory_set.rs
index a5a9ede..58ac256 100644
--- a/os/src/mm/memory_set.rs
+++ b/os/src/mm/memory_set.rs
@@ -66,6 +66,19 @@ impl MemorySet {
             None,
         );
     }
+    /// Remove framed area
+    pub fn remove_framed_area(&mut self, range: VPNRange) {
+        let mut idx = 0;
+        for area in self.areas.iter_mut() {
+            if area.vpn_range.get_start().0 == range.get_start().0 
+                && area.vpn_range.get_end().0 == range.get_end().0 {
+                area.unmap(&mut self.page_table);
+                break;
+            }
+            idx += 1;
+        }
+        self.areas.remove(idx);
+    }
     /// remove a area
     pub fn remove_area_with_start_vpn(&mut self, start_vpn: VirtPageNum) {
         if let Some((idx, area)) = self
diff --git a/os/src/mm/mod.rs b/os/src/mm/mod.rs
index d75c373..a2ac413 100644
--- a/os/src/mm/mod.rs
+++ b/os/src/mm/mod.rs
@@ -12,9 +12,10 @@ mod heap_allocator;
 mod memory_set;
 mod page_table;
 
-use address::VPNRange;
+pub use address::VPNRange;
 pub use address::{PhysAddr, PhysPageNum, StepByOne, VirtAddr, VirtPageNum};
 pub use frame_allocator::{frame_alloc, frame_dealloc, FrameTracker};
+pub use frame_allocator::is_mem_sufficient;
 pub use memory_set::remap_test;
 pub use memory_set::{kernel_token, MapPermission, MemorySet, KERNEL_SPACE};
 use page_table::PTEFlags;
diff --git a/os/src/syscall/fs.rs b/os/src/syscall/fs.rs
index 864d6ba..b27deac 100644
--- a/os/src/syscall/fs.rs
+++ b/os/src/syscall/fs.rs
@@ -1,5 +1,7 @@
 //! File and filesystem-related syscalls
-use crate::fs::{open_file, OpenFlags, Stat};
+use core::mem::size_of;
+
+use crate::fs::{open_file, OpenFlags, Stat, ROOT_INODE};
 use crate::mm::{translated_byte_buffer, translated_str, UserBuffer};
 use crate::task::{current_task, current_user_token};
 
@@ -78,26 +80,55 @@ pub fn sys_close(fd: usize) -> isize {
 /// YOUR JOB: Implement fstat.
 pub fn sys_fstat(_fd: usize, _st: *mut Stat) -> isize {
     trace!(
-        "kernel:pid[{}] sys_fstat NOT IMPLEMENTED",
+        "kernel:pid[{}] sys_fstat",
         current_task().unwrap().pid.0
     );
-    -1
+    let task = current_task().unwrap();
+    let inner = task.inner_exclusive_access();
+    if _fd > inner.fd_table.len() {
+        return -1;
+    }
+    if let Some(file) = &inner.fd_table[_fd] {
+        let file = file.clone();
+        drop(inner);
+        let stat: Stat = file.get_stat();
+        let buffers = translated_byte_buffer(
+            current_user_token(), _st as *const u8, size_of::<Stat>());
+        let mut stat_ptr = &stat as *const _ as *const u8;
+        for buffer in buffers {
+            unsafe {
+                stat_ptr.copy_to(buffer.as_mut_ptr(), buffer.len());
+                stat_ptr = stat_ptr.add(buffer.len());
+            }
+        }
+        0
+    } else {
+        -1
+    }
 }
 
 /// YOUR JOB: Implement linkat.
 pub fn sys_linkat(_old_name: *const u8, _new_name: *const u8) -> isize {
     trace!(
-        "kernel:pid[{}] sys_linkat NOT IMPLEMENTED",
+        "kernel:pid[{}] sys_linkat",
         current_task().unwrap().pid.0
     );
-    -1
+    let token = current_user_token();
+    let _old_name = translated_str(token, _old_name);
+    let _new_name = translated_str(token, _new_name);
+    if _old_name == _new_name {
+        return -1;
+    }
+    ROOT_INODE.linkat(&_old_name, &_new_name)
 }
 
 /// YOUR JOB: Implement unlinkat.
 pub fn sys_unlinkat(_name: *const u8) -> isize {
     trace!(
-        "kernel:pid[{}] sys_unlinkat NOT IMPLEMENTED",
+        "kernel:pid[{}] sys_unlinkat",
         current_task().unwrap().pid.0
     );
-    -1
+    let token = current_user_token();
+    let _name = translated_str(token, _name);
+    ROOT_INODE.unlinkat(&_name)
 }
diff --git a/os/src/syscall/mod.rs b/os/src/syscall/mod.rs
index 613d44e..34197ed 100644
--- a/os/src/syscall/mod.rs
+++ b/os/src/syscall/mod.rs
@@ -59,8 +59,10 @@ use process::*;
 
 use crate::fs::Stat;
 
+use crate::task::current_task;
 /// handle syscall exception with `syscall_id` and other arguments
 pub fn syscall(syscall_id: usize, args: [usize; 4]) -> isize {
+    current_task().unwrap().inc_syscall_times(syscall_id);
     match syscall_id {
         SYSCALL_OPEN => sys_open(args[1] as *const u8, args[2] as u32),
         SYSCALL_CLOSE => sys_close(args[0]),
diff --git a/os/src/syscall/process.rs b/os/src/syscall/process.rs
index 316897d..974412a 100644
--- a/os/src/syscall/process.rs
+++ b/os/src/syscall/process.rs
@@ -1,15 +1,17 @@
 //! Process management syscalls
-//!
+
+use core::mem::size_of;
+
 use alloc::sync::Arc;
 
 use crate::{
     config::MAX_SYSCALL_NUM,
     fs::{open_file, OpenFlags},
-    mm::{translated_refmut, translated_str},
+    mm::{translated_byte_buffer, translated_refmut, translated_str},
+    mm::{is_mem_sufficient, VirtAddr},
     task::{
-        add_task, current_task, current_user_token, exit_current_and_run_next,
-        suspend_current_and_run_next, TaskStatus,
-    },
+        add_task, current_task, current_user_token, exit_current_and_run_next, suspend_current_and_run_next, TaskStatus
+    }, timer::get_time_us,
 };
 
 #[repr(C)]
@@ -119,10 +121,24 @@ pub fn sys_waitpid(pid: isize, exit_code_ptr: *mut i32) -> isize {
 /// HINT: What if [`TimeVal`] is splitted by two pages ?
 pub fn sys_get_time(_ts: *mut TimeVal, _tz: usize) -> isize {
     trace!(
-        "kernel:pid[{}] sys_get_time NOT IMPLEMENTED",
+        "kernel:pid[{}] sys_get_time",
         current_task().unwrap().pid.0
     );
-    -1
+    let _us = get_time_us();
+    let time_val = TimeVal {
+        sec: _us / 1_000_000,
+        usec: _us % 1_000_000,
+    };
+    let buffers = translated_byte_buffer(
+        current_user_token(), _ts as *const u8, size_of::<TimeVal>());
+    let mut time_val_ptr = &time_val as *const _ as *const u8;
+    for buffer in buffers {
+        unsafe {
+            time_val_ptr.copy_to(buffer.as_mut_ptr(), buffer.len());
+            time_val_ptr = time_val_ptr.add(buffer.len());
+        }
+    }
+    0
 }
 
 /// YOUR JOB: Finish sys_task_info to pass testcases
@@ -130,28 +146,60 @@ pub fn sys_get_time(_ts: *mut TimeVal, _tz: usize) -> isize {
 /// HINT: What if [`TaskInfo`] is splitted by two pages ?
 pub fn sys_task_info(_ti: *mut TaskInfo) -> isize {
     trace!(
-        "kernel:pid[{}] sys_task_info NOT IMPLEMENTED",
+        "kernel:pid[{}] sys_task_info",
         current_task().unwrap().pid.0
     );
-    -1
+    let task_info = TaskInfo {
+        status: TaskStatus::Running,
+        syscall_times: current_task().unwrap().get_syscall_times(),
+        time: current_task().unwrap().get_scheduled_timespan(),
+    };
+    let buffers = translated_byte_buffer(
+        current_user_token(), _ti as *const u8, size_of::<TaskInfo>());
+    let mut task_info_ptr = &task_info as *const _ as *const u8;
+    for buffer in buffers {
+        unsafe {
+            task_info_ptr.copy_to(buffer.as_mut_ptr(), buffer.len());
+            task_info_ptr = task_info_ptr.add(buffer.len());
+        }
+    }
+    0
 }
 
 /// YOUR JOB: Implement mmap.
 pub fn sys_mmap(_start: usize, _len: usize, _port: usize) -> isize {
     trace!(
-        "kernel:pid[{}] sys_mmap NOT IMPLEMENTED",
+        "kernel:pid[{}] sys_mmap",
         current_task().unwrap().pid.0
     );
-    -1
+    let start_va = VirtAddr::from(_start);
+    // 1. illegal start virtual address or port
+    if !start_va.aligned() || _port & !0x7 != 0 || _port & 0x7 == 0 {
+        return -1;
+    }
+
+    // 2. Check is there sufficient physical memory
+    if !is_mem_sufficient(_len) {
+        return -1;
+    }
+    
+    let end_va = VirtAddr::from(_start + _len);
+    current_task().unwrap().mmap(start_va, end_va, _port)
 }
 
 /// YOUR JOB: Implement munmap.
 pub fn sys_munmap(_start: usize, _len: usize) -> isize {
     trace!(
-        "kernel:pid[{}] sys_munmap NOT IMPLEMENTED",
+        "kernel:pid[{}] sys_munmap",
         current_task().unwrap().pid.0
     );
-    -1
+    let start_va = VirtAddr::from(_start);
+    if !start_va.aligned() {
+        return -1;
+    }
+    
+    let end_va = VirtAddr::from(_start + _len);
+    current_task().unwrap().munmap(start_va, end_va)
 }
 
 /// change data segment size
@@ -168,17 +216,34 @@ pub fn sys_sbrk(size: i32) -> isize {
 /// HINT: fork + exec =/= spawn
 pub fn sys_spawn(_path: *const u8) -> isize {
     trace!(
-        "kernel:pid[{}] sys_spawn NOT IMPLEMENTED",
+        "kernel:pid[{}] sys_spawn",
         current_task().unwrap().pid.0
     );
-    -1
+    
+    // spawn a new process based upon _path
+    let token = current_user_token();
+    let _path = translated_str(token, _path);
+    let data_opt = open_file(&_path, OpenFlags::RDONLY);
+    if data_opt.is_none() {  // invalid file name
+        return -1;
+    }
+    let current_task = current_task().unwrap();
+    let new_task = current_task.spawn(data_opt.unwrap().read_all().as_slice());
+    let new_pid = new_task.getpid();
+    add_task(new_task);
+    new_pid as isize
 }
 
 // YOUR JOB: Set task priority.
 pub fn sys_set_priority(_prio: isize) -> isize {
     trace!(
-        "kernel:pid[{}] sys_set_priority NOT IMPLEMENTED",
+        "kernel:pid[{}] sys_set_priority",
         current_task().unwrap().pid.0
     );
-    -1
+    if _prio <= 1 {
+        return -1;
+    }
+    let current_task = current_task().unwrap();
+    current_task.set_prio(_prio);
+    _prio
 }
diff --git a/os/src/task/manager.rs b/os/src/task/manager.rs
index 99393a4..b0f2b52 100644
--- a/os/src/task/manager.rs
+++ b/os/src/task/manager.rs
@@ -19,11 +19,27 @@ impl TaskManager {
     }
     /// Add process back to ready queue
     pub fn add(&mut self, task: Arc<TaskControlBlock>) {
+        task.inc_stride();
         self.ready_queue.push_back(task);
     }
     /// Take a process out of the ready queue
     pub fn fetch(&mut self) -> Option<Arc<TaskControlBlock>> {
-        self.ready_queue.pop_front()
+        // self.ready_queue.pop_front()
+        let mut min_stride = isize::MAX;
+        let mut best_idx = 0;
+        for (idx, tcb) in self.ready_queue.iter().enumerate() {
+            let stride = tcb.get_stride();
+            if min_stride > stride {
+                min_stride = stride;
+                best_idx = idx;
+            }
+        }
+        if min_stride == isize::MAX {
+            None
+        } else {
+            self.ready_queue.swap(0, best_idx);
+            self.ready_queue.pop_front()
+        }
     }
 }
 
diff --git a/os/src/task/processor.rs b/os/src/task/processor.rs
index f05fa09..14b8ae0 100644
--- a/os/src/task/processor.rs
+++ b/os/src/task/processor.rs
@@ -8,6 +8,7 @@ use super::__switch;
 use super::{fetch_task, TaskStatus};
 use super::{TaskContext, TaskControlBlock};
 use crate::sync::UPSafeCell;
+use crate::timer::get_time_ms;
 use crate::trap::TrapContext;
 use alloc::sync::Arc;
 use lazy_static::*;
@@ -61,6 +62,11 @@ pub fn run_tasks() {
             let mut task_inner = task.inner_exclusive_access();
             let next_task_cx_ptr = &task_inner.task_cx as *const TaskContext;
             task_inner.task_status = TaskStatus::Running;
+            // if the task is being called for the first time,
+            if task_inner.time == 0usize {
+                // then set it to the current time
+                task_inner.time = get_time_ms();
+            }
             // release coming task_inner manually
             drop(task_inner);
             // release coming task TCB manually
diff --git a/os/src/task/task.rs b/os/src/task/task.rs
index ff5b581..d8c5510 100644
--- a/os/src/task/task.rs
+++ b/os/src/task/task.rs
@@ -1,10 +1,11 @@
 //! Types related to task management & Functions for completely changing TCB
 use super::TaskContext;
 use super::{kstack_alloc, pid_alloc, KernelStack, PidHandle};
-use crate::config::TRAP_CONTEXT_BASE;
 use crate::fs::{File, Stdin, Stdout};
-use crate::mm::{MemorySet, PhysPageNum, VirtAddr, KERNEL_SPACE};
+use crate::config::{BIG_STRIDE, MAX_SYSCALL_NUM, TRAP_CONTEXT_BASE};
+use crate::mm::{MapPermission, MemorySet, PhysPageNum, VPNRange, VirtAddr, VirtPageNum, KERNEL_SPACE};
 use crate::sync::UPSafeCell;
+use crate::timer::get_time_ms;
 use crate::trap::{trap_handler, TrapContext};
 use alloc::sync::{Arc, Weak};
 use alloc::vec;
@@ -36,6 +37,86 @@ impl TaskControlBlock {
         let inner = self.inner_exclusive_access();
         inner.memory_set.token()
     }
+    /// Set the schduling priority
+    pub fn set_prio(&self, prio: isize) {
+        let mut inner = self.inner_exclusive_access();
+        inner.set_prio(prio);
+    }
+    /// Get the schduling stride
+    pub fn get_stride(&self) -> isize {
+        let inner = self.inner_exclusive_access();
+        inner.stride
+    }
+    /// Increase the stride by pass
+    pub fn inc_stride(&self) {
+        let mut inner = self.inner_exclusive_access();
+        inner.inc_stride();
+    }
+    /// Get syscall times
+    pub fn get_syscall_times(&self) -> [u32; MAX_SYSCALL_NUM] {
+        let inner = self.inner.exclusive_access();
+        inner.syscall_times.clone()
+    }
+    /// Get time span between current time and first scheduled time
+    pub fn get_scheduled_timespan(&self) -> usize {
+        let inner = self.inner.exclusive_access();
+        get_time_ms() - inner.time
+    }
+    /// Increase syscall times
+    pub fn inc_syscall_times(&self, syscall_id: usize) -> bool {
+        if syscall_id >= MAX_SYSCALL_NUM {
+            return false;
+        }
+        let mut inner = self.inner.exclusive_access();
+        inner.syscall_times[syscall_id] += 1;
+        true
+    }
+    /// Map some pages to memory_set
+    pub fn mmap(&self, start_va: VirtAddr, end_va: VirtAddr, port: usize) -> isize {
+        let mut inner = self.inner.exclusive_access();
+        let vpn_range = VPNRange::new(
+            VirtPageNum::from(start_va),
+            end_va.ceil()
+        );
+        
+        // 3. Check if trying to map mapped page
+        for vpn in vpn_range {
+            if let Some(pte) = inner.memory_set.translate(vpn) {
+                if pte.is_valid() {
+                    return -1;
+                }
+            }
+        }
+
+        // After checking all errors may occur,
+        // push a new map_area to current memory_set
+        let perm = MapPermission::from_bits((port as u8) << 1).unwrap() | MapPermission::U;
+        inner.memory_set.insert_framed_area(start_va, end_va, perm);
+        0
+    }
+
+    /// Unmap some pages in memory set
+    pub fn munmap(&self, start_va: VirtAddr, end_va: VirtAddr) -> isize {
+        let mut inner = self.inner.exclusive_access();
+        let vpn_range = VPNRange::new(
+            VirtPageNum::from(start_va),
+            end_va.ceil(),
+        );
+
+        // 1. Check if trying to unmap unmapped page
+        for vpn in vpn_range {
+            if let Some(pte) = inner.memory_set.translate(vpn) {
+                if !pte.is_valid() {
+                    return -1
+                }
+            }
+        }
+
+        // After checking all errors may occur,
+        // remove some pages from current memory_set
+        inner.memory_set.remove_framed_area(vpn_range);
+        0
+    }
 }
 
 pub struct TaskControlBlockInner {
@@ -71,6 +152,18 @@ pub struct TaskControlBlockInner {
 
     /// Program break
     pub program_brk: usize,
+
+    /// Scheduling priority
+    pub prio: isize,
+
+    /// Scheduling stride
+    pub stride: isize,
+
+    /// The syscall times
+    pub syscall_times: [u32; MAX_SYSCALL_NUM],
+
+    /// The first time the task was scheduled
+    pub time: usize,
 }
 
 impl TaskControlBlockInner {
@@ -94,6 +187,13 @@ impl TaskControlBlockInner {
             self.fd_table.len() - 1
         }
     }
+    pub fn set_prio(&mut self, prio: isize) {
+        self.prio = prio;
+    }
+    pub fn inc_stride(&mut self) {
+        let pass = BIG_STRIDE / self.prio;
+        self.stride += pass;
+    }
 }
 
 impl TaskControlBlock {
@@ -135,6 +235,10 @@ impl TaskControlBlock {
                     ],
                     heap_bottom: user_sp,
                     program_brk: user_sp,
+                    prio: 16,
+                    stride: 0,
+                    syscall_times: [0u32; MAX_SYSCALL_NUM],
+                    time: 0usize,
                 })
             },
         };
@@ -216,6 +320,10 @@ impl TaskControlBlock {
                     fd_table: new_fd_table,
                     heap_bottom: parent_inner.heap_bottom,
                     program_brk: parent_inner.program_brk,
+                    prio: 16,
+                    stride: 0,
+                    syscall_times: [0u32; MAX_SYSCALL_NUM],
+                    time: 0usize,
                 })
             },
         });
@@ -231,6 +339,65 @@ impl TaskControlBlock {
         // ---- release parent PCB
     }
 
+    /// parent process spawn the child process
+    pub fn spawn(self: &Arc<Self>, elf_data: &[u8]) -> Arc<Self> {
+        let mut parent_inner = self.inner_exclusive_access();
+        // create a user space based upon elf_data
+        let (memory_set, user_sp, entry_point) = MemorySet::from_elf(elf_data);
+        let trap_cx_ppn = memory_set
+            .translate(VirtAddr::from(TRAP_CONTEXT_BASE).into())
+            .unwrap()
+            .ppn();
+        // alloc a pid and a kernel stack in kernel space
+        let pid_handle = pid_alloc();
+        let kernel_stack = kstack_alloc();
+        let kernel_stack_top = kernel_stack.get_top();
+        // copy fd table
+        let mut new_fd_table: Vec<Option<Arc<dyn File + Send + Sync>>> = Vec::new();
+        for fd in parent_inner.fd_table.iter() {
+            if let Some(file) = fd {
+                new_fd_table.push(Some(file.clone()));
+            } else {
+                new_fd_table.push(None);
+            }
+        }
+        let task_control_block = Arc::new(TaskControlBlock {
+            pid: pid_handle,
+            kernel_stack,
+            inner: unsafe {
+                UPSafeCell::new(TaskControlBlockInner {
+                    trap_cx_ppn,
+                    base_size: user_sp,
+                    task_cx: TaskContext::goto_trap_return(kernel_stack_top),
+                    task_status: TaskStatus::Ready,
+                    memory_set,
+                    parent: Some(Arc::downgrade(self)),
+                    children: Vec::new(),
+                    exit_code: 0,
+                    heap_bottom: parent_inner.heap_bottom,
+                    program_brk: parent_inner.program_brk,
+                    fd_table: new_fd_table,
+                    prio: 16,
+                    stride: 0,
+                    syscall_times: [0u32; MAX_SYSCALL_NUM],
+                    time: 0usize,
+                })
+            },
+        });
+        // add child
+        parent_inner.children.push(task_control_block.clone());
+        // modify trap_cx
+        let trap_cx = task_control_block.inner_exclusive_access().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
+    }
+
     /// get pid of process
     pub fn getpid(&self) -> usize {
         self.pid.0

问答作业

Q: 在我们的 easy-fs 中，root inode 起着什么作用？如果 root inode 中的内容损坏了，会发生什么？

A: root inode 起着根目录的作用，如果 root inode 中的内容（例如文件数据链接 direct、indirect 等）损坏了，可能导致根目录下的文件无法被正常访问。