Category: Operating System and System Software

大家好，最近对RISC-V xv6教学用操作系统做了一个系列相关主题的介绍，希望能对相关的读者朋友们(特别是相关专业在读的大学同学们)在相关方面提供一点有用的资源和信息，期待大家的反馈意见，谢谢。 References

本篇文章将向大家介绍riscv-xv6中的文件系统的设计和实现思路，在操作系统中，文件是一个更宽泛的概念，其包含对多种资源的抽象，如外围交互设备，存储设备以及网络等，这篇文章将简要介绍我们日常使用的狭义的文件系统(file system)的实现机制。 磁盘的物理结构和读写逻辑结构的理解，与硬件物理结构有关的有设备号，磁道，扇区，柱面等，与读写逻辑结构有关的有设备号和块号（blockno），关于磁盘的物理结构和读写逻辑结构以及读写方法可以参考[1]。 缓冲区缓存（buffer cache，在kernel/bio.c中实现）是为磁盘访问提供缓存的实现，可以提高磁盘读写的效率。LRU采用了双向循环链表进行的实现，完整实现思路可以参考[2]，但在riscv-xv6的实现中没有用到哈希函数，而是采用遍历的方式进行的查找，riscv-xv6中的具体的实现参考[3]，当前的head节点为最近访问的节点（哨兵节点），head节点的前驱节点为最久未使用的节点，而后继节点为离当前head最近时间使用过的节点，依此类推。在缓冲区的实现代码中，bget函数用于根据dev和blockno来获取磁盘缓冲区，如果已经在缓存区中缓存，则引用计数加一并用睡眠锁互斥访问；如果在缓冲区中没有，则从LRU中找到离当前最久的未使用的缓冲区并通过睡眠锁实现互斥访问。bread和bwrite是实现磁盘块读写的函数，其中都是基于缓冲区的buf（和磁盘块对应）作为媒介，在riscv-xv6中磁盘块读操作通过函数virtio_disk_rw(b, 0)将磁盘内容读到缓冲区，磁盘块写操作通过virtio_disk_rw(b, 1)函数将缓冲区的内容写到磁盘里，整个磁盘缓冲区以及块读写的实现参考[3]。 inode（索引节点）是 UNIX 文件系统（如 ext4、xfs）中用于描述文件元数据的结构体，它存储了文件的关键信息， inode和dinode结构体中addr数据项用来存放硬盘中具体数据的位置，详细的解释可以参考[4]，整个文件的读写的实现见kernel/fs.c代码文件。在riscv-xv6中，当前运行的活动（active）的inode存放在itable结构里，itable没有实现类似buffer cache这样的LRU访问功能，inode 只有在 ref == 0 时才会被回收，但没有 LRU 淘汰策略。只要 ref > 0，inode 就不会被回收，即使它是最久未使用的 inode。 问题1：inode中的dev和inum和major和minor的关系，dinode中为什么不需要dev和inum？回答可以参考[5]中的结构体的字段的定义作用和对比分析。 问题2：inode加载到内容之后，readi去读取时还是调用到了bread，为什么会这样？回答：inode 是文件在内存中的表示，而 dinode（磁盘上的 inode）是文件在磁盘上的存储形式。它们的结构类似，但 dinode 是存储在磁盘上的，而 inode 是加载到内存中的表示，在dinode数据项的基础之上多了dev和inum以及睡眠锁等。inode 结构不存储文件内容，只包含文件的元信息（例如 size、addrs）。ilock函数会调用bread函数读取inode数据元数据。数据块号 (addrs[]) 是指向实际文件内容的磁盘块，但数据仍然需要 通过调用bread() 读取。inode索引节点以及文件本身数据读写操作实现参考[6]。 问题3：riscv-xv6系统中的文件目录结构组织方法介绍，xv6中文件路径如何和inode关联？回答：riscv-xv6中，文件或目录的结构体数据为dirent，包括名称和inum，inum=0表示目录。在磁盘上，一个目录的inode通过 inode->addrs 指向其数据块，而数据块的内容就是多个dirent 结构体的数组。该数组的每一项表示目录下的文件或子目录。整个文件系统中超级块保存了文件系统的结构，具体信息参考[7]。 问题4：riscv-xv6中读文件的过程中涉及哪些关键函数的调用路径，关键函数的实现机制是怎样的？回答：可以简要概括为sys_read->fileread->readi->bread等，其中sys_read为系统调用的入口，fileread为sys_read判断当前为读文件操作后调用的函数，readi为读取indoe节点的文件数据，其中首先会通过ilock函数实现inode节点的读取（如果inode节点不在内存，也需要通过bread从磁盘读取dinode数据到inode节点里），然后通过inode节点中的addr信息去调用bread函数读取文件的具体数据块内容。 问题5：sys_open打开文件如何实现文件名到inode的映射，具体调用了哪些关键函数路径？回答：主要通过namei，namex，dirlookup等关键函数实现文件路径到inode的映射，会调用iget从itable中获取inode节点。sys_read只读取已经打开的file结构体文件，ilock的作用表现在同一路径的文件被多个进程加载，实现数据的互斥访问(并且如果dinode没有加载，则通过bread等函数实现从磁盘加载对应的dinode数据到inode结构体中)。更多关于文件读写的相关说明见[8]。 References

本篇文章将向大家介绍一下riscv-xv6的进程调度的实现分析。 riscv-xv6进程调度发生的时机：xv6中进程为单线程的，进程是调度的单位。xv6采用的是抢占式时间片轮转（Round Robin）调度，分时系统的时间片到达或与硬件交互过程中需要等待从而阻塞当前进程(如read系统调用将当前进程的状态设为睡眠)让出cpu时需要调度在等待队列中的进程； 进程调度中的几个关键函数：2、scheduler，进程调度器，每个cpu共享这个调度器代码，但有独立运行的调度器，其内部会从进程表里循环遍历查找状态为”RUNNABLE”的进程并调用sched函数进行调度运行(不同CPU对应的调度器通过锁机制实现进程的安全访问)，调度器内部执行的swtch函数，此时swtch首先保存cpu里的context状态，也就是当前运行的scheduler的cpu环境上下文，并加载马上在cpu上运行的进程的context上下文到cpu寄存器里。2、调度器外部执行的sched，在sched函数实现内部调用了swtch函数，该函数为当前的进程保存上下文（当前进程准备让出cpu执行，将ra,sp以及cpu的callee registers的寄存器状态保存到进程的结构体的context数据里），并加载cpu结构体数据里的context到cpu的寄存器里（cpu结构体里的context为scheduler函数上次调度进程执行时的上下文环境，从而恢复scheduler调度器的执行上下文，开始进程调度）。sched函数会在几个地方被调用:(1)，进程退出，exit函数执行，调度可执行的进程开始运行；（2），进程阻塞到睡眠状态，调度其他进程执行；(3)，当分时的定时器中断到来，发生trap时，kerneltrap和usertrap里通过调用yield函数让出当前进程的cpu执行权限（当前进程从RUNNING的状态更新为RUNNABLE的状态，即ready的可调度状态）。 关于sleep和wakeup的分析：1、sleep发生的可能的场合，硬件中断，如读写操作（异步交互通信，以及硬件共享时的竞态条件需要用到的睡眠锁等），需要阻塞进程异步等待消息准备好；2、sleep系统调用，让当前进程等待大约多少时间（可以以tickes的count为参数，可以参考实验[2]）；3、wait系统调用，父进程会调用sleep等待子进程结束。wakeup被调用的时候基本为当阻塞的进程满足继续运行的条件，如硬件输入输出相关信息到达，包括定时器时间中断到达（定时器时间中断到达除了会唤醒相关进程到RUNNALBLE状态外，也会调用yield函数调度其他进程开始运行）。相关函数的实现可参考[3]

本篇文章主要介绍riscv-xv6中的锁机制，在riscv-xv6系统中，内核有不少的共享变量，如进程表，物理内存空闲链表，用于console读写的缓冲区等，这些共享变量在多个进程中共享需要互斥进行访问，否则就会出现数据一致性问题。 在riscv-xv6中有两种锁机制，一种为自旋锁（spinlock)，一种为睡眠锁（sleeplock）。下面分别介绍一起其实现的机制原理以及应用的场合。 spinlock的实现: 关于__sync_lock_test_and_set函数和__sync_synchronize函数的实现和详细注释可以参考[1]；用push_off关闭中断可以解决在嵌套调用情况下可能会导致的误开中断的问题[2]。 问答：在锁的获取和释放之间的过程中断为什么要关闭，如果中断不关闭，可能会出现哪些问题？自旋锁的临界区代码可以在不同 CPU 上执行吗？也就是自旋锁中为什么加上cpu结构体的指针？ 回答：这三个问题是spinlock实现中的相互有关联的问题，将做一起回答。中断与特定的cpu相关，如果中断没有关闭，有可能会出现中断导致当前进程被挂起，下次调度运行时自旋锁的临界区代码就可以运行在不同的cpu上，这样可能会带来：（1）、cpu缓存一致性问题带来的性能问题；（2）、进程A已经获取锁并由于中断（如定时器中断）被让出cpu进入等待状态，进程B刚好也要获取锁，但由于锁已经被进程A获取，进程B将阻塞，导致系统处于较为复杂的进程间依赖情况，影响调度性能，有可能会导致死锁；（3）如果临界区在同一个cpu上不间断运行，如果当前 CPU 已持有锁并再次尝试获取，就可以直接报错，防止出现递归锁问题和死锁。（4）在多核系统中，调试并发问题是非常困难的，如果锁结构中存有持有锁的 CPU，那么：可以方便地打印日志，追踪哪个 CPU 在哪个时刻 获取了锁。在出现死锁或资源竞争时，能够快速确定哪个 CPU 或线程导致的问题。 睡眠锁的实现：睡眠锁的使用场景可以参考[3]，sleeplock是阻塞式锁，用于长时间拥有资源的使用权限和持有锁的场景，如文件系统。关于acquiresleep和sleep函数的实现，可以参考[4]中的注释说明。在文件系统的缓冲区缓存的访问中，就调用了acquiresleep来访问缓冲区（如果已经被其他进程锁住，则进入睡眠等待，否则加锁并返回缓冲区，见[5]中的bget函数的实现和注释） References

这篇文章以sh进程为例介绍操作系统中进程和设备交互的过程，涉及traps的流程处理，硬件驱动，进程的阻塞、唤醒和调度等部分的相关知识技能点。 1、在xv6中，设备以一种特殊的文件类型（FD_DEVICE）存在，文件结构体的描述见[2]，其中major成员变量记录设备文件的主设备号，用于区分不同设备。参考[3]以sh程序为例介绍了进程和uart硬件交互的过程。从上述过程的分析来看，硬件中断既可以在用户态触发，也可以在内核态触发。 2、从用户态触发的usertrap和内核态触发的kerneltrap都会调用devintr 函数中进行中断处理实现，具体函数的注释见[6] 3、uart设备是遵循串口协议的双工通信的设备，能实现信息的收发，在xv6系统中uart可以模拟输入的键盘和输出的终端（屏幕）设备。以用户进程等待接收字符串为例，可以参考[3]中的具体的示例的流程处理分析。 问题：在sh这样的程序中[4]，console接收用户键盘输入的字符（进程本身处于阻塞挂起状态[5]），同时也要反馈到显示终端，当用户输入回车时才唤醒进程处于ready等待调度，反馈到终端的过程具体时怎样的？ 回答：consoleintr函数里将接收的字符放入接收缓冲区，同时通过consputc函数将字符发送到终端，uartintr驱动响应函数既能够处理接收缓冲区（如某一个进程等待用户输入），也能够处理发送缓冲区（如另外一个进程程序输出内容到终端）。 References

riscv-xv6是基于多核的riscv指令架构的教学用操作系统的实现，这篇短文将在已有相关启动流程介绍[1]的基础上补充介绍riscv-xv6。 1、入口_entry的汇编代码见entry.S[2]，_entry的代码会加载在kernel加载到内存的起始位置0x80000000，每个hart(hart 的全称是 Hardware Thread，即硬件线程。在 xv6 操作系统中，hart 通常用于表示一个 CPU 核心)会调用start.c的代码执行。在 xv6 操作系统中，stack0 是一个用作临时工作栈的区域（其为全局变量，在内核的数据区），特别是在内核早期启动阶段，操作系统还没有设置完进程的内核栈时。当设置了分页功能，启动了第一个用户进程后，操作系统的内核将会运行在kstack特定的栈区（不同的进程可以并行运行在不同的进程对应的内核栈区位置）。 2、start.c的代码中相关的知识点：mstatus时machine status register，MSTATUS 寄存器用于存储 CPU 的状态信息，包括当前执行模式和中断状态等信息，其代码及注释参考[3]和[4]。 3、这里主要解释main.c函数的相关处理逻辑。start.c的最后通过调用mret指令，进入main函数[5]，其中kinit函数（代码见kernel/kalloc.c）实现了物理内存的初始化(将从end到PHYSTOP的内存空间按照PAGESIZE大小为单元串接成空闲页链表），kvminit（kernel/vm.c）实现了内核页表的生成和虚拟地址到物理地址的直接映射；kvminithart函数将内核页表地址设置到SATP寄存器从而使能分页功能(turn on paging)；procinit函数初始化进程表（编译时生成在内核的数据区），以及进程表中每一个proc结构中对应的内核栈地址，在 riscv-xv6 或其他类似操作系统中，内核的数据区中的一些结构（例如由 kalloc 管理的内存块列表）是 动态变化的，并且内核的数据区是允许这种变化的。kalloc（内存分配器）管理的内存块列表和其他数据结构，虽然会动态修改数据内容（如指针更新、内存块分配和回收），但是并不需要为这些数据结构的变化分配新的内存空间。因此，内核的数据区的大小可以被认为是固定的，也就是说，数据区的大小在系统启动时就已经确定，并且在运行过程中不会扩展或缩小。trapinit函数初始化计时器相关的自旋锁，在xv6系统中有一个全局变量ticks。trapinithart函数将kernelvec的代码段初始地址赋值给stvec寄存器，以便在内核态能响应中断处理（kerneltrap函数进一步会调用devintr函数），关于文件系统和persistent memory驱动相关的内容，后面的文章将有专门介绍。关于user/initcode和不同cpu核的初始化顺序问题，可以分别参考引文[6]和[7]。初始化过程之后，每一个cpu都将调用scheduler()函数调度进程开始执行。 问答： 1、问题：不同的cpu共享内核页，每个cpu的stvec寄存器共享kernelvec和uservec代码段，由于这些代码没有共享变量，为可重入代码，因此可以方便共享，是可以这么理解对吗 回答：kernelvec和uservec分别为在内核态和用户态发生trap时所需要的处理逻辑，没有共享变量（tramponline.S的uservec和kernelvec.S的kernelvec），每个cpu运行有自己的内核栈kstack和trapframe结构体数据，因此不同的cpu的内核态中断处理和用户态中断处理代码可以共享。 2、问题：每个cpu是不是有其自己的定时器，从定时器的中断处理来看，好像只对0号cpu的定时器中断做了处理？ 回答：是的，选择0号cpu处理时间中断，方便了系统统一的时间计数和进程调度处理，虽然在riscv等芯片实现中每个cpu核有自己的定时器，但操作系统选择在0号cpu上统一处理，方便了集中管理时间和进程调度。在芯片的设计中，cpu的每个核心之间有共享cache，cache的作用在于快速的获取数据，根据存储访问速度来看，cpu访问cache的速度比内存的速度快多个数量级。由于进程调度的出现，同一个进程（线程）可能在不同的cpu上运行，因此cpu共享cache是有必要的，但cache也分级数（尽管每个 CPU 核心有自己的 L1 和 L2 缓存，但它们通常共享 L3 缓存。这意味着在多核系统中，多个 CPU 核心之间可以共享 L3 缓存来加速数据访问。但由于每个 CPU 核心的 L1 和 L2 缓存是独立的，因此数据迁移和缓存一致性依然是一个重要问题。）。不同cpu共享内核的代码，但有其独立运行的内核栈，其逻辑计算相对独立且可以并行执行。 References

这篇文章介绍riscv-xv6的操作系统接口(operating system interface)的实现，系统调用实现了用户态和内核态的隔离，也为实现了不同进程之间的隔离提供了条件（还有其他的机制如虚拟内存和页表等机制一起为实现不同进程的隔离提供了完整解决方案）。在riscv-xv6的user目录下，一般是用户程序的实现源码，如cat，echo, sh等，在这些程序的实现过程中，会调用内核态执行的代码逻辑，如文件读写，fork，exec等系统调用，下面就简要介绍一下添加一个系统调用的实现方法以及系统调用等trap发生时的处理过程逻辑分析。 1、在user/user.h中定义系统调用的prototype（signature），在usys.pl定义添加的系统调用的entry（通过编译过程会生成usys.S，用于生成系统调用的stubs，桩函数作为占位符，通常用于测试、RPC 代理，或者未完成的函数。）sutb里定义了通过指令ecall以及系统调用的参数和系统调用函数指针数组index等信息传递到内核去调用系统调用函数的实现（将系统调用的函数序号索引放入a7寄存器，参考引文[2]）。 2、用户程序调用系统调用函数时触发stub函数，会执行ecall指令， 触发异常（trap），进入 S-mode（Supervisor Mode）。ecall 不会自动保存寄存器状态，需要软件（操作系统）来管理寄存器的保存与恢复。当 ecall 发生时，CPU 会保存当前 sepc（保存陷入前的 PC）;设置 scause（记录 trap 原因，ecall 在 S-mode 下的 scause=8）;切换到 stvec 处理 trap（uservec代码段）;清除 SIE 位（即 sstatus.SIE = 0，禁用中断）;更新 sstatus.SPP（记录陷入前的特权级）。 3、uservec代码段的功能为：(1)、保存当前用户态执行的cpu的寄存器到trapframe结构中；(2)并将trapframe中保存的内核的栈指针，页表地址等进行加载，并最后调用usertrap函数，具体实现参看引文[3]。usertrap最后调用syscall实现系统函数在内核中的真正执行，usertrap的代码实现根据不同的trap发生的条件（系统调用，硬件中断，时钟定时器中断）做对应的处理，具体可以参考引文[4]。几个关键的寄存器:(1)、stvec（// Supervisor Trap-Vector Base Address）存放发生trap时的代码起始地址，在用户态时应指向uservec[5]，在内核态时应为kernelvec[6]；kerneltrap发生的情形有外部硬件按中断和时钟中断以及一些运行时错误等（由于已经在内核态，不存在系统调用的的情况。进入 kerneltrap() 前，RISC-V 硬件自动清除 sie，确保不会在处理中断时发生新的中断抢占。sie 负责控制中断使能，如果 sie=0，新的中断不会打断当前的 kerneltrap 处理流程[8]。kerneltrap的处理过程代码及分析参考[12]。 4、usertrapret[7]为从usertrap执行完准备返回用户态时需要执行的代码，主要的逻辑有：关闭硬件中断；设置stvec为uservec；设置寄存器为用户态权限；执行寄存器状态恢复等操作（userret代码段[9]）。 5、在创建用户进程的时候相关的函数调用路径有： allocproc([10]) -> forkret([11])-> usertrapret-> w_stvec(trampoline_uservec)（[7]）,可以看到创建用户进程时子进程被调度开始运行时将uservec代码段起始地址设置到stvec寄存器的问题。关于设置stvec为uservec代码段的流程的更多的分析：（1）、fork() 创建子进程，并设置其 state =…

本篇文章将简要介绍内核页表和用户进程页表的机制，页表实现了内存的虚拟地址到物理地址的转换，虚拟地址机制实现了进程之间物理存储空间的隔离。在os中，物理内存一般以页（一页，一般为4096字节）进行分配和管理。 在riscv-xv6中实现了三级页表机制：level2，level1，level0。sv39的寻址方式中，virtual address由9+9+9（三级页表项，每一级页表的directory有2^9=512项PTE条目，PTE的组成为（reserved(10bit)+PPN(44bit)+flags(10bit))。其中标记位为PTE_R，PTE_W，PTE_X等，如果这三项都没有标记，则表示该PTE不是叶子PTE，可以通过该PTE进一步检索下一级页表，否则该PPN（对齐到4096，即4K字节）+12位的offset即为具体的物理地址。其中虚拟地址翻译的细节图解如下图所示。 内核页表和用户进程的页表的虚拟地址到物理地址的转换机制相同，都是通过上述的地址转换细节实现。两者细节分别如下： 内核页表机制：低地址一般为外围硬件的寄存器和低地址物理内存对应，其地址映射图示为，其中PLIC（ platform-level interrupt controller (PLIC) ），UART0定义为UART的寄存器对应的物理内存地址。VIRTIO为 virtio mmio interface，其中KERNBASE（0x80000000）到PHYSTOP（0x88000000=PHYSTOP (KERNBASE + 128*1024*1024)）为xv6所支持的实际物理内存空间 其中kvmmake函数内核映射的代码可以参考引文[1]。其中代码段中下面的两行实现内核的代码和剩余空间的映射,确保内核可以管理所有物理内存。 其中通过kinit函数将内核代码数据段之上的物理内存空间按照物理页的粒度进行初始化并形成链表，kfree实现以页为单位的内存空间的释放，kalloc实现以页为单位的内存空间的申请（提供了锁机制实现了多进程的互斥访问），释放和申请相应的也需要对链表进行操作，具体实现可以参考引文[2]。从上图可以看出，kstack0，kstack1等为用户进程所对应的内核栈，也在kvmmake函数里实现 用户进程的地址空间通过fork、exec和sbrk等系统调用来生成，其中fork创建子进程，复制父进程地址空间的内容（会申请新的页表和PTE对应的物理内存空间，并通过函数memmove将父进程的内容进行复制，包括增加文件描述符的引用计数等），exec通过加载可行性的elf格式的文件，加载代码段数据段到用户页表里（生成了新的页表并释放就的页表空间，具体见引文[3]），然后生成stack空间，堆空间的生成通过sbrk系统调用来生成，其中栈空间的基地址为低地址，栈顶指针为高地址，栈空间从上到下维护程序代码执行的生命周期，包括参数，临时变量等等。 几个问题： 1、用户进程和其对应的内核栈如何实现的关联？回答：初始化进程表的时候实现的关联，具体可以参考引文[4]的代码实现。 2、在用户进程的用户态申请内存时如何实现的？是基于srbk的系统调用吗？回答：扩展堆区的大小可以用srbk系统调用来生成，进一步调用growproc函数和uvmalloc来实现进程的用户空间的存储空间的增长或缩减，可以参考引文[5]的具体实现。 References