Final

内容
分值
负责助教
备注

Console

10

Pipe

10

O

File Descriptor

20

Shell

20

Exec

20

Fork

20

Mmap

10

O

自选 Bonus

20

O

说明

  • O：不实现此部分也可以启动 shell。如果时间来不及，请优先保证你能启动 shell，因为启动 shell 所占分值较大。建议优先完成：File Descriptor + Exec + Fork + Shell + Console + Pipe。

  • 满分 100 分，超出的部分算 bonus。

1. File Descriptor

在这一部分，我们将完成和文件（file）以及文件描述符有关的最终实现。

你也许有疑问：为什么已经有了完整的硬盘文件/目录抽象（inode），还需要再包装一层？答案正如我们所常说：UNIX 的设计哲学是一切皆文件，除了狭义上的硬盘上的“文件”，我们还有设备文件（device File）和管道文件（pipe file）等等。这些文件的特点是：它们不是硬盘上的文件，而是内核中的一些数据结构，但和硬盘文件一样都可以作为读写操作的对象。

因此，我们需要为它们再设计一套抽象，使得用户态程序可以通过同一套机制来访问它们中的任何一个。这套机制就是文件（file）。

从面向对象的角度理解“一切皆文件”

从面向对象的角度来看，“一切皆文件”可以将“文件”这一概念视为一个抽象类（abstract class）或接口（interface）。这一理念的核心在于通过一套统一的接口操作多种资源。这一原则不仅能够最大限度地复用已有代码，还具备良好的可扩展性，符合软件工程中久经验证的优秀实践之一：开闭原则（OCP）。

在 Linux 系统中，这套接口的实现通过以下结构体定义：

struct file_operations {
  struct module *owner;
	loff_t (*llseek) (struct file *, loff_t, int);
	ssize_t (*read) (struct file *, char *, size_t, loff_t *);
	ssize_t (*write) (struct file *, const char *, size_t, loff_t *);
	int (*readdir) (struct file *, void *, filldir_t);
	unsigned int (*poll) (struct file *, struct poll_table_struct *);
	int (*ioctl) (struct inode *, struct file *, unsigned int, unsigned long);
	int (*mmap) (struct file *, struct vm_area_struct *);
	int (*open) (struct inode *, struct file *);
	int (*flush) (struct file *);
	int (*release) (struct inode *, struct file *);
	int (*fsync) (struct file *, struct dentry *, int datasync);
	int (*fasync) (int, struct file *, int);
	int (*lock) (struct file *, int, struct file_lock *);
	ssize_t (*readv) (struct file *, const struct iovec *, unsigned long, loff_t *);
	ssize_t (*writev) (struct file *, const struct iovec *, unsigned long, loff_t *);
};

支持该接口的资源通常以数据为中心。例如：

  • 键盘作为字符设备，管理用户输入的字符数据。

  • 管道文件管理一段由某进程输出、供另一进程输入的数据。

  • /dev/random 设备管理随机数据。

文件除了需要持有底层对象以外，还有一些额外的字段：

  • 文件以偏移量（对于硬盘文件就是从文件开头的字节数，对于设备文件和管道文件就是迄今为止读/写的字节数）来标识当前读写的位置；

  • 文件为了能同时被多个进程持有，需要记录当前持有者的数量；

  • 文件还需要记录当前可行的读写模式（例如，设备文件可能仅能以只读模式打开，管道文件可能一头只写、一头只读，没有权限写的硬盘文件可能也仅能以只读模式打开）。

为了节省不必要的开支，所有的文件对象被组织在一个全局文件表中（一个数组），而每个进程又有自己的进程文件表（同样是一个数组）。进程文件表中，每个文件对象都有一个文件描述符（file descriptor）来标识自己。文件描述符是一个非负整数，即进程文件表中的下标，通过它可以找到对应的文件对象。

一个极简的文件对象如下所示：

enum file_type {
    NONE,    // 未使用
    DEVICE,  // 设备文件
    INODE,   // 硬盘文件
    PIPE,    // 管道文件
};

struct file {
    enum file_type type;    // 文件类型
    bool readable, writable;// 读写模式
    int refcnt;             // 当前持有者数量
    usize offset;           // 当前读写偏移量
    union {
        struct inode *inode;    // 硬盘文件的下层接口（Inode）
        struct device *device;  // 设备文件的下层接口（Device）
        struct pipe *pipe;      // 管道文件的下层接口（Pipe）
    };
};

值得注意的是，在本实验中我们进行了一些简化和修改：

我们支持的外设很少（只有一个终端字符设备），而且我们目前还没有做出虚拟文件系统（VFS）的接口，因此为简便起见，我们不再为设备（device）设计一个单独的抽象，而是直接复用硬盘的 inode 抽象，将其看作设备文件的下层接口。 也就是说，当我们创建一个设备文件时，我们将在硬盘上创建一个实在的 inode，其类型为 INODE_DEVICE。因此，你的inode 接口也要考虑到设备文件的情况（例如 inode_read 等函数可能调用设备文件的下层接口，如 console_read）。当然，这是后话了。

1.1. 任务

任务 1：实现 src/fs/file.c 的下列函数：

// 从全局文件表中分配一个空闲的文件
struct file* file_alloc();

// 获取文件的元信息（类型、偏移量等）
int file_stat(struct file* f, struct stat* st);

// 关闭文件
void file_close(struct file* f);

// 将长度为 n 的 addr 写入 f 的当前偏移处
isize file_read(struct file* f, char* addr, isize n);

// 将长度为 n 的 addr 从 f 的当前偏移处读入
isize file_write(struct file* f, char* addr, isize n);

// 文件的引用数+1
struct file* file_dup(struct file* f);

// 初始化全局文件表
void init_ftable();

// 初始化/释放进程文件表
void init_oftable(struct oftable*);
void free_oftable(struct oftable*);

任务 2：截止目前我们都未编写路径字符串（例如 /this/is//my/path/so_cool.txt）的解析逻辑。我们在 src/fs/inode.c 中实现了比较困难的部分，你需要完成其中的namex函数（可见inode.c中的注释部分）：

static Inode* namex(const char* path, bool nameiparent, char* name, OpContext* ctx)

任务 3：为了对接用户态程序，我们需要在 src/kernel/sysfile.c 中实现一些系统调用：

任务 4：实现辅助函数：

// 从描述符获得文件
static struct file *fd2file(int fd);

// 从进程文件表中分配一个空闲的位置给 f
int fdalloc(struct file *f);

// 根据路径创建一个 Inode
Inode *create(const char *path, short type, short major, short minor, OpContext *ctx);

任务 5（可以以后再做）：参考讲解部分，修改 inode.c 中 read 和 write 函数，以支持设备文件。

2. Fork & Exec

fork 和 execve 是 Unix/Linux 系统编程中两个核心的系统调用，用于创建新进程和执行新的程序。fork 用于从当前进程（父进程）中创建一个新进程（子进程），而 execve 用于在当前进程中执行一个新程序。fork 和 execve 的组合使用是实现多进程和加载新程序的核心机制。在本部分中，我们将实现 fork 和 execve 系统调用，为后续启动 shell 做好准备。

2.1. ELF 可执行文件格式

ELF 文件描述了一个程序。它可以看作一个程序的“镜像”，就像 ISO 文件是一个光盘的“镜像”一样。ELF 文件包含程序的入口地址、各个段的大小、各个段的属性（可读、可写、可执行等）等等。我们按照这些信息，将程序加载到内存中，然后跳转到入口地址，就可以运行这个程序了。

在本部分中，我们需要实现 ELF 文件的解析和加载。后续，我们运行用户程序（如 ls, mkdir 等）前都需要加载其 ELF 到内存中。在这里，我们给出两个会用到的结构体定义（相关头文件：musl/include/elf.h）：

/**
 * ELF Header：ELF 文件的入口点，位于文件的开头，描述了文件的整体布局和重要属性。
 */
typedef struct {
  	// 标识 ELF 文件的魔数、架构类型（32/64 位）、字节序（小端/大端）等。
		unsigned char e_ident[EI_NIDENT];
  
  	// 文件类型（可执行文件、共享库、目标文件等）。
    Elf64_Half    e_type;
  
  	// 指定目标机器架构（如 x86、ARM）。
    Elf64_Half    e_machine;
  
  	// ELF 版本信息。
    Elf64_Word    e_version;
  
  	// 程序入口地址（可执行文件运行时的起始地址）。
    Elf64_Addr    e_entry;
  
  	// 程序头表（Program Header Table）的偏移量。
    Elf64_Off     e_phoff;
  
  	// 段头表（Section Header Table）的偏移量。
    Elf64_Off     e_shoff;
    Elf64_Word    e_flags;
    Elf64_Half    e_ehsize;
    Elf64_Half    e_phentsize;
    Elf64_Half    e_phnum;
    Elf64_Half    e_shentsize;
    Elf64_Half    e_shnum;
    Elf64_Half    e_shstrndx;
} Elf64_Ehdr;


/**
 * Program Header Table (PHT)：描述程序运行时需要加载的段信息，主要用于可执行文件和共享库。
 */
typedef struct {
  	// 段类型（如加载段、动态段、解释器段等）。
    Elf64_Word    p_type;
  
  	// 段的权限（可读、可写、可执行）。
    Elf64_Word    p_flags;
  
  	// 段在文件中的偏移量。
    Elf64_Off     p_offset;
  
  	// 段的虚拟地址（内存中的地址）。
    Elf64_Addr    p_vaddr;
  
  	//  段的物理地址（针对嵌入式设备）。
    Elf64_Addr    p_paddr;
  
  	// 段在文件中的大小。
    Elf64_Xword   p_filesz;
  
  	// 段在内存中的大小（可能大于文件中大小）。
    Elf64_Xword   p_memsz;
  
  	// 段的对齐要求。
    Elf64_Xword   p_align;
} Elf64_Phdr;

注意：ELF 文件中的 section header 和实验中的 struct section 并不一样，本次实验不用考虑 ELF 中的 section header，但是需要明确 ELF 中的 Elf64_Phdr 与 lab 中 struct section 的对应关系。

提示：可以参考 xv6 加载 ELF 的实现。

2.2. fork() 系统调用

计算机系统基础（ICS）复习：用户程序调用 fork() 将创建一个当前进程的完整复制，我们通过 fork() 的返回值区分亲进程和子进程（亲进程的返回值是子进程的 PID ，子进程的返回值是 0）。

在实现 fork() 的内核侧时，我们需要从进程的结构体（Proc）入手，判断其中的成员是否需要复制，是否需要修改。例如，我们需要深拷贝亲进程的页表给子进程，需要“复制”亲进程的文件描述符给子进程等。

思考：文件描述符的“复制”是什么意思？

注意：为了配合 fork()，你可能需要在原先的 UserContext 中加入所有寄存器的值。此外，你还需要保存tpidr0 和 q0，因为musl libc会使用它们。

提示：可以参考 xv6 fork 的实现。

2.3. execve() 系统调用

/**
 * @path: 可执行文件的地址。
 * @argv: 运行文件的参数（即 main 函数中的 argv ）。
 * @envp: 环境变量
 */
int execve(const char* path, char* const argv[], char* const envp[])

execve() 替换当前进程为 path 所指的 ELF 格式文件，加载该 ELF 文件，并运行该程序。你需要读取 Elf64_Ehdr 和 Elf64_Phdr 结构，注意根据 p_flags 的信息判断 section 类型，把 p_vaddr, p_memsz, p_offset 等信息填入到实验框架中的 struct section 对应位置；将文件中的代码和数据加载到内存中，并设置好用户栈、堆等空间；最后跳转到 ELF 文件的入口地址开始执行。

思考：替换 ELF 文件时，当前进程的哪些部分需要释放，哪些部分不需要？

思考：是否需要把 argv 和 envp 中的实际文本信息复制到新进程的地址空间中？

提示：下面提供了一个 execve 的大致流程：

/*
 * Step1: Load data from the file stored in `path`.
 * The first `sizeof(struct Elf64_Ehdr)` bytes is the ELF header part.
 * You should check the ELF magic number and get the `e_phoff` and `e_phnum` which is the starting byte of program header.
 *
 * Step2: Load program headers and the program itself
 * Program headers are stored like: struct Elf64_Phdr phdr[e_phnum];
 * e_phoff is the offset of the headers in file, namely, the address of phdr[0].
 * For each program header, if the type(p_type) is LOAD, you should load them:
 * A naive way is 
 * (1) allocate memory, va region [vaddr, vaddr+filesz)
 * (2) copy [offset, offset + filesz) of file to va [vaddr, vaddr+filesz) of memory
 * Since we have applied dynamic virtual memory management, you can try to only set the file and offset (lazy allocation)
 * (hints: there are two loadable program headers in most exectuable file at this lab, the first header indicates the text section(flag=RX) and the second one is the data+bss section(flag=RW). You can verify that by check the header flags. The second header has [p_vaddr, p_vaddr+p_filesz) the data section and [p_vaddr+p_filesz, p_vaddr+p_memsz) the bss section which is required to set to 0, you may have to put data and bss in a single struct section. COW by using the zero page is encouraged)

 * Step3: Allocate and initialize user stack.
 * The va of the user stack is not required to be any fixed value. It can be randomized. (hints: you can directly allocate user stack at one time, or apply lazy allocation)
 * Push argument strings.
 * The initial stack may like
 *   +-------------+
 *   | envp[m] = 0 |
 *   +-------------+
 *   |    ....     |
 *   +-------------+
 *   |   envp[0]   |  ignore the envp if you do not want to implement
 *   +-------------+
 *   | argv[n] = 0 |  n == argc
 *   +-------------+
 *   |    ....     |
 *   +-------------+
 *   |   argv[0]   |
 *   +-------------+
 *   |    argc     |
 *   +-------------+  <== sp

 * ## Example
 * sp -= 8; *(size_t *)sp = argc; (hints: sp can be directly written if current pgdir is the new one)
 * thisproc()->tf->sp = sp; (hints: Stack pointer must be aligned to 16B!)
 * The entry point addresses is stored in elf_header.entry
*/

提示：在execve()中，一般可执行文件中可以加载的只有两段：RX的部分+RW的部分（其它部分会跳过）（因此只设置两种状态，一种是RX，另一种是RW）

  • RX的部分： 代码部分，主要包括 text 段，属性为 ST_FILE + RO

  • RW的部分：数据部分，包括了 data + bss 段

2.4. copyout

copyout 复制内容到给定的页表上，在 execve 中，为了将一个用户地址空间的内容复制到另一个用户地址空间上，可能需要调用这样的函数。如果你使用其他实现，则不需要实现这个函数。

/*                                        
 * Copy len bytes from p to user address va in page table pgdir.
 * Allocate a file descriptor for the given file.
 * Allocate physical pages if required.
 * Takes over file reference from caller on success.
 * Useful when pgdir is not the current page table.
 * return 0 if success else -1
 */                                                          
int copyout(struct pgdir* pd, void* va, void *p, usize len)

2.5. 任务

任务 1：实现下列内容：

  • kernel/syscall.c 中的 user_readable 和 user_writeable：检查syscall中由用户程序传入的指针所指向的内存空间是否有效且可被用户程序读写。

  • kernel/proc.c 中的 fork。

  • kernel/exec.c 中的 execve。

  • kernel/pt.c 中的 copyout（可选）。

  • kernel/paging.c 中的 copy_sections。

  • kernel/paging.c 中的 init_sections：不需要再单独初始化 heap 段。

  • kernel/paging.c 中的 pgfault：增加有关文件的处理逻辑。

3. Shell

本部分我们将尝试启动 shell 。

3.1. 任务

任务1：补全两个用户态程序的实现：

  1. cat(1)：src/user/cat/main.c。要求支持cat + 单一文件名的命令形式，即输出单一文件，其他功能可以自行补充。

  2. mkdir(1)：src/user/mkdir/main.c。

任务2：内核启动后执行第一个用户态程序 src/user/init.S。在 src/kernel/core.c 的 kernel_entry() 中手动创建并启动第一个用户态进程。(即将 init.S 的代码映射到进程的 section 中)。

提示：可以在core.c中使用 extern char icode[]; extern char eicode[]; 来获得 init.S 的代码段的内核地址。这样的操作我们在 Lab 0 中清空 BSS 段时也用过。

实现成功后，内核将输出 shell 的 prompt（$）。此时，你仍然无法与内核交互，下面我们将实现 console，支持用户输入命令，运行程序。

4. Console

在开发中，我们常常使用诸如 printf(), getchar() 等标准库函数实现用户输入与交互。然而，截至目前，我们的内核尚未支持键盘输入功能。因此，基于前一部分已实现的 shell，我们将进一步扩展功能，设计和实现 console，使用户能够通过键盘输入与 shell 交互，从而执行相关命令和运行硬盘上的程序。

当用户通过键盘输入内容时，内核会接收到 UART 触发的中断。通过读取 UART 的相关寄存器（由 uart_get_char() 实现），我们可以获得用户输入的具体字符。以下是 UART 的中断处理函数：

static void uartintr()
{
    /**
     * Invoke the console interrupt handler here. 
     * Without this, the shell may fail to properly handle user inputs.
     */
    char c = uart_get_char();
    if (c != 0xFF) {
        console_intr(c);
    }

    device_put_u32(UART_ICR, 1 << 4 | 1 << 5);
}

在中断处理流程中，我们首先通过 uart_get_char() 获取用户输入的字符 c，然后将其交由 console_intr 函数处理。中断处理完成后，通过 device_put_u32 清除 UART 的中断状态。

console 是一个被抽象为文件的设备，主要管理用户输入的数据，即输入/输出缓冲区。在 console_intr 函数中，用户输入的字符会写入 console 的缓冲区，成为 console 所管理的核心数据。

正如之前所提到的，“一切皆文件”的设计理念使我们能够通过统一的接口对各种资源进行操作。在本实验中，用户态的 shell 通过内核提供的 read 和 write 接口，通过读写 console，实现与用户的交互。

具体来说：

  • 读取用户输入：shell 调用 read 接口，从缓冲区读取用户输入的字符。通过读取这些字符，shell 可以解析并执行用户输入的命令，例如 echo hello。在这种情况下，shell 会理解用户是希望以 hello 为参数运行 echo 程序。

  • 输出到终端：shell 调用 write 接口，将需要显示的内容写入缓冲区。内核会从缓冲区中读取这些内容，并通过 UART 将其输出到终端供用户查看。

回显

用户在终端中输入命令时，需要实时看到自己输入的内容。例如用户输入命令 ls -al的同时，终端会显示出用户输入的命令，避免用户像输入密码一样“盲打”，给用户带来了良好的交互体验。

原理：当用户在键盘上输入字符时，内核会触发 UART 中断，执行以下流程：用户键盘输入 -> 内核的 UART 中断 -> console_intr(c) -> 将 c 写入缓冲区 -> uart_put_char(c) 回显给用户。

索引

struct console 定义了三个重要的索引，用于跟踪缓冲区的状态：

  • read_idx：标识已被用户态（通过调用 read 的 shell）读取的位置。

  • write_idx：标识已被用户态（通过调用 write 的 shell）写入的位置。

  • edit_idx：标识当前用户编辑的光标位置。

4.1. 任务

任务 1：完成 console_intr，处理下述情况：

  1. backspace：对应字符 c 为 \x7f。删除前一个字符，即 input.edit_idx--。注意，位于 input.write_idx 前的已回显字符不能删除。

  2. Ctrl+U：删除一行。

  3. Ctrl+D：更新 input.write_idx 到 input.edit_idx。表示 EOF。本身也要写入缓冲区和回显。

  4. 普通字符写入和回显。

回显会用到 uart_put_char 向console写入内容。

任务 2：完成 console_read 和 console_write，并在 inode_read 和 inode_write 中调用（前面我们已经提到，我们复用了 inode 作为设备文件的抽象）。

提示：可以参考 xv6 console 的实现。

5. Pipe

相信到目前为止，你已经对“一切皆文件”的哲学有了较深的理解。在本部分，你将在“一切皆文件”哲学的指导下，实现 pipe。

在 Linux 中，pipe（管道） 是一种进程间通信（IPC, Inter-Process Communication）机制，用于将一个进程的输出直接作为另一个进程的输入。它通过一种“生产者-消费者”模型实现数据流的传递，主要用于命令之间的协作，避免使用临时文件。

管道的创建与使用

  1. 在 Shell 中使用管道：管道符号是 |，将前一个命令的输出传递给后一个命令作为输入。例如：

    ls -l | grep "txt"

    其中，ls -l 列出了当前目录的详细信息，而 grep "txt" 过滤包含 txt 的文件。该命令的作用是筛选出当前目录下的 txt 文件。

  2. pipe() 是一个低级系统调用，用于创建一个匿名管道。它返回两个文件描述符：读端pipefd[0]和写端pipefd[1]。

    #include <unistd.h>
#include <stdio.h>
#include <string.h>

int main() {
    int pipefd[2];
    char buffer[128];
    if (pipe(pipefd) == -1) {
        perror("pipe");
        return 1;
    }

    // 写入管道
    write(pipefd[1], "Hello, Pipe!", strlen("Hello, Pipe!") + 1);

    // 读取管道
    read(pipefd[0], buffer, sizeof(buffer));
    printf("Read from pipe: %s\n", buffer);

    return 0;
}

5.1. 任务

任务1：完成 pipe.c 中的内容。

任务2：完成 sysfile.c 中的 pipe2，实现相关系统调用。

提示：可以参考 xv6 pipe 的实现。

6. File Mapping

什么是 mmap() ？

mmap，从函数名就可以看出来这是memory map，即内存映射，是一种内存映射文件的方法，将一个文件或者其它对象映射到进程的地址空间，实现文件磁盘地址和进程虚拟地址空间中一段虚拟地址的一一对映关系。mmap() 系统调用使得进程之间通过映射同一个普通文件实现共享内存。普通文件被映射到进程地址空间后，进程可以向访问普通内存一样对文件进行访问，不必再调用 read() ，write() 等操作。

为什么要用 mmap() ？

Linux通过内存映像机制来提供用户程序对内存直接访问的能力。内存映像的意思是把内核中特定部分的内存空间映射到用户级程序的内存空间去。也就是说，用户空间和内核空间共享一块相同的内存。这样做的直观效果显而易见：内核在这块地址内存储变更的任何数据，用户可以立即发现和使用，根本无须数据拷贝。举个例子理解一下，使用 mmap 方式获取磁盘上的文件信息，只需要将磁盘上的数据拷贝至那块共享内存中去，用户进程可以直接获取到信息，而相对于传统的 write/read IO 系统调用, 必须先把数据从磁盘拷贝至到内核缓冲区中（页缓冲），然后再把数据拷贝至用户进程中。两者相比，mmap 会少一次拷贝数据，这样带来的性能提升是巨大的。

参考资料：XV6学习（15）Lab mmap: Mmap - 星見遥 - 博客园

6.1. 任务

任务 1：实现下列系统调用。

void *mmap (void *addr, size_t length, int prot, int flags, int fd, off_t offset);
int munmap(void *addr, size_t length);

7. 构建、测试与提交

在拉取了最新的框架后，我们需要：

git submodule update --init

在构建时，我们需要：

cd build
cmake ..
make libc -j
make qemu

当你完成全部任务后，如果一切顺利，将进入 shell，你可以自己运行里面的程序。我们也编写了一个 usertests 程序供测试。

提交日期为 2025 年 1 月 26 日，如有特殊情况请联系助教。

PreviousLab 7: MMNextARM 中断机制

Last updated