xv6

---

操作系统接口

文件描述符

每个进程有一个私有的文件描述符表，这是shell可以执行IO重定向以及管道的基础。

每个文件描述符都有一个与文件关联的偏移。

fork后，子进程拥有和父进程一致的文件描述符表，再次执行exec后，也仍然会保留该文件描述符表（除了使用closeonexec选项）。这允许了IO重定向，使得不同的进程可以访问相同的文件描述符。比如cat的实现：cat < input.txt

char *argv[2];
argv[0] = "cat";
argv[1] = 0;
if(fork() == 0) {
    close(0);
    open("input.txt", O_RDONLY);
    exec("cat", argv);
}

open默认返回最小未使用的文件描述符：0。

为什么不直接给一个创建新进程的接口，而是分为先fork，再exec，因为这样创建的子进程在fork之后exec之前，还有一段时间，这里可以执行一些任务，比如可以修改文件描述符。（其实exec执行的程序不知道文件描述符的事情，他们需要完成的事情只是从0读从1写，文件描述符的修改是由shell进程完成的，毕竟执行exec前的程序都可以看成是父进程即shell进程）

通过fork或者dup系统调用来源自相同的文件描述符共享同一个偏移地址。否则文件描述符不共享偏移，即使是通过open打开相同的文件。

ls existing-file non-existing-file > tmp1 2>&1,这里让文件描述符2是文件描述符1的复制品（dup）。可以让错误输出也输出到文件描述符1上。

管道

如果管道没有数据，read会等待直到有数据写到管道上，或者所有写端的文件描述符都被关闭了。

类似grep fork sh.c | wc -l管道的实现，父进程创建一个管道，然后fork两次，产生两个子进程，（可能会将读端dup到0，写端dup到1），然后执行exec调用两者的子程序。

相比于临时文件，管道的几个优点：

• 管道（进程的）自动清理其中的数据，而临时文件需要收到清理。
• 管道可以处理长的数据，而临时文件先需要保证拥有足够的空间来保存这些文件。
• 管道允许并行执行，一个进程写一个进程读。而临时文件是一个进程写完后，另一个进程才读。
• 管道没有数据就会阻塞，直到有数据。而临时文件为空时，只会收到一个提示。

文件系统

不以/开头的地址，都是相对于当前进程当前目录的相对地址。

mknod创建一个设备文件，与之关联的是主设备号和次设备号。当使用opeen打开一个设备文件是，read和write不是使用文件系统打开该设备文件，而是通过内核的设备驱动程序来处理。

目录的数据部分包含者文件名以及与之对应的inode节点，inode节点保存着文件的元数据，比如类型，长度，位置，连接数。

操作系统组织

操作系统必须满足多路复用，因此又必须实现隔离和交互。

本节介绍针对单内核操作系统是如何实现上面三条规则的。

抽象物理资源

强隔离需要应用程序和操作系统之间存在一个边界。以防止内核数据遭到破坏。

CPU也提供隔离支持。在RISC-V处理器指令集中，有三种指令执行模式：机器模式，管理员模式，和用户模式。（ARM指令集也是类似）

• 机器模式：有着完全的权限，Xv6会在这个模式执行几行，然后进入管理员模式
• 管理员模式：允许执行特权指令：enable/disable 中断，读写页表寄存器（切换上下文有用）
• 用户模式

应用程序只能执行用户模式的指令，叫做在用户空间运行。

在特权模式的软件能执行特权指令，又叫做在特权空间运行。在内核空间运行的软件叫做内核。

在RISC-V中，使用ecall可以切换处理器模式到管理员模式，然后在某一个地址进入内核。

核心设计

整个操作系统都在内核模式运行——单内核。

• 优点：这种模式很简单，也便于不同的模块之间共享资源。
• 缺点：操作系统因为有很多部分组成，所以不同部分之间的接口很复杂，内核开发者容易写bug，在单内核系统中，特权模式的一个bug很容易导致内核崩溃。（可以把内核理解成一个完整的应用程序，他由于不同模块.c.h编译而成）

为了避免这个缺点：提出了微内核（大部分操作系统代码都在用户空间执行，也即以用户模式运行）

如上图，文件系统在用户空间运行，如果一个shell想要访问文件系统的话，它需要通过系统调用send发送一条消息给文件服务器并且等待回应。很多系统模块都以这种服务器的形式运行在用户空间。所以内核只需要包含很少的指令，比如启动应用程序，发送消息等。

进程概览

隔离的单元是进程。进程抽象防止一个进程破坏另一个进程的资源。

每个进程都有一个执行线程。每个进程都有用户栈和内核栈。当产生系统调用或者中断时，使用的是内核栈。

一个进程可以调用ecall指令，来触发一个系统调用，他会提升硬件特权，并且进入到一个内核定义的入口，这个入口的代码会更换栈以及执行系统调用对应的指令，当系统调用完成时，内核通过sret指令切换用户栈并且返回用户空间。

开始xv6以及第一个进程

从汇编函数_entry开始,该函数设置了一个栈，然后调用了start函数。

start执行了一些只在机器模式才有用的配置，禁止管理者模式中的虚拟地址转换，将所有中断和异常委托给管理者模式。然后通过mret返回到管理模式。（这需要往mstatus寄存器写管理者模式，并将返回地址mepc设为main的地址）

main初始化了几个设备和子系统，通过userinit创建了第一个进程。然后执行exec，创建了几个设备文件，然后通过文件描述符0， 1， 2打开，然后在console上开了个shell。

`_entry -> （start）start.c -> main.c -> userinit -> （start）initcode.s -> init

页表

陷阱以及系统调用

RISC-V陷阱机制

来自用户空间的陷阱

代码：调用系统调用

参数是通过a0和a1寄存器传递，系统调用号通过a7寄存器传递。系统调用号匹配syscalls数组中的条目。ecall指令陷入内核，然后执行uservec，usertrap，然后是syscall，如我们所见。syscall给a0寄存器返回负数代表错误，返回0及正数代表正确。（而C调用惯例也是用a0保存返回值。）

void syscall(void)//至于为什么没有参数，可能是被前两个函数使用了
{
  int num;
  struct proc *p = myproc();
  num = p->trapframe->a7;
  if(num > 0 && num < NELEM(syscalls) && syscalls[num]) {
    p->trapframe->a0 = syscalls[num]();//这里根据系统调用号，去执行对应的系统调用。
  } else {
    printf("%d %s: unknown sys call %d\n",
            p->pid, p->name, num);
    p->trapframe->a0 = -1;
  }
}

系统调用参数

系统调用需要用户代码传递的参数，因为用户代码会调用系统调用包装函数，而这些参数最初位于RISC-V惯例放的位置-寄存器。内核陷阱代码会报错用户的寄存器到当前进程的陷阱帧，然后内核从陷阱帧中获取参数，这些函数argint、argaddr、argfd代表获取第n个系统调用参数，分别以整数、指针、文件描述符的形式读取。这三个函数都调用argraw从陷阱帧获取数据。

传参时，面临两个问题：

• 如果用户传送错误的指针地址
• 用户的页表和内核的页表，不一致，如何保证地址是通用的呢

为此，内核提供了安全的函数来从用户地址转换数据，getchstr是一个例子。它通过调用copyinstr来获取字符串。

copyinstr拷贝最多max个字节从用户页表中的虚拟地址srcva到dst。这个函数会使用walkaddr来遍历页表来确定srcva的物理地址pa0。因为进入内核模式后虚拟地址转换是关闭的，所以内核模式的地址就是物理地址，所以copyinstr可以直接将字符串从pa0拷贝到dst。同时，walkaddr还要检查用户提供的虚拟地址是不是该用户的。

类似的，copyout拷贝数据到用户空间。

layout split

一个愚蠢的问题：页表项中存储的地址是虚拟地址还是物理地址？

物理地址，原因：如果存储的是虚拟地址，那么就需要使用mmu将虚拟地址转换为物理地址，而我们查询页表项就是为了进行从虚拟地址到物理地址的转换。

Trap

陷阱处理的四个阶段：

• 硬件行为，（比如保存状态，切换cpu状态等）
• 汇编vector，为c代码做准备
• C trap处理器，决定如何处理这个trap
• 系统调用以及设备驱动程序

trap机制

RISC-V cpu有很多寄存器用来控制traps以及获取traps的状态。

• stvec，内核往这个寄存器写trap处理程序的地址，然后RISC-V调转到这里进行执行。
• sepc，保存着trap结束后的返回地址，sret(return from trap)会将sepc拷贝到pc寄存器。内核可以往sepc写地址来决定返回到哪里。
• scause，描述产生trap的原因
• sscratch，内核可以在这里放一个值
• sstatus，其中的SIE位用来开关设备中断。关闭之后，设备中断会延迟。SPP位代表trap是从用户模式来的还是从管理员模式来的，这也会决定sret返回的模式。

机器模式也有对应的寄存器，有特殊的用途比如，计时器中断。

当中断发生时（处理寄存器中断），RISC-V硬件完成如下的步骤：

• 当前trap是设备中断并且sstatus的SIE位是被清空的，不做下面的任务。
• 清空SIE关闭中断
• 拷贝pc到sepc
• 保存当前处理器模式到sstatus的SPP位
• 设置scause
• 设置处理器模式为管理员
• 拷贝stvec到pc寄存器。
• 开始执行新pc。

可见硬件只完成必要的操作，切换pc寄存器，并不会切换页表切换栈，这些操作需要在后续程序中实现。

用户空间的Traps

uservec ---> usertrap ---> usertrapret ---> userret

可以通过系统调用，或者非法操作，或者设备中断可以让traps在用户空间中产生。

在执行uservec中的程序时，需要切换页表为内核页表，为了切换前后代码执行顺序不变，需要让uservec所在的页面TRAMPOLINE在前后两个页表中有相同的虚拟地址。

uservec在切换页表前：

• 需要保存用户寄存器，将所有寄存器保存到trapframe页面中。在进入用户空间前，sscratch指向每个进程独有的trapframe，交换a0和sscratch寄存器，然后使用a0来保存所有的寄存器。每个进程在初始化时都会分配一个页面用于trapframe，将其映射在虚拟地址TRAPFRAME中，进程的p->tramframe也指向栈帧的物理地址，这样内核可以直接使用p->tramframe->axx来访问所有被保存的寄存器。
• 保存了所有的寄存器

之后，需要从tramframe中读取当前进程的内核栈、当前CPU的hartid、usertrap的地址、内核页表的地址。uservec切换satp，然后调整到usertrap。

usertrap的工作是确定trap的原因，然后处理，返回。他首先会切换stvec寄存器为kernelvec，因为可能发生内核导致的traps。然后会保存sepc到trapframe中，因为可能出现进程切换而导致sepc被覆盖。然后根据traps的类型决定处理方式：

• 系统调用：syscall。会往sepc+4，因为sepc保存到是ecall的地址，需要返回到ecall的下一个指令。对于下面两种情况，因为没有ecall，显然不用+4.
• 设备中断：devintr
• 异常：kill出错的进程。

处理完后，判断进程是否被kill或者是否应该让出cpu（如果该trap是一个时钟中断）。

返回用户空间的第一个调用是usertrapret，这个函数设置了RISC-V的控制寄存器为之后从用户空间到的·trap做准备（包括将stvec设为uservec，准备uservec依赖的trapframes到）。他会配置trapframe中的satp、sp、hartid、trap等。（可以发现，前面触发trap时，会保存寄存器，也会从trapframe中读取这四个值）。会设置sepc，给出trap返回的地址。

最后需要返回到userret进行执行，在这里会切换用户页表，从trapframe恢复寄存器，然后使用sret返回到trap前的地址。

注意切换页表都需要在trampoline中断代码中完成，只有在这个部分，用户页表和内核页表的地址映射才是完全一致的，切换页表后才不会导致出错。

来自内核的trap

RISC-V本来不针对来自用户的trap和来自内核的trap做区分，但是xv6这里针对来自内核的trap提供了kerneltrap代码。

xv6在内核中又遇到trap时，会保存寄存器到栈中，最终返回时从栈恢复到寄存器。其中只可能遇到两种trap：

• 设备中断，这时会处理中断
• 异常，在内核中发生异常，肯定是严重错误，需要使用panic

进入trap时，RISC-V自动关闭中断，直到设置stvec后才会重新开启中断。

页错误异常

页错误异常可以用来实现copy-on-write，lazy allocation，paging from disk，automatically extending stacks and memory-mapped files。

三种页错误：

• 加载页错误——不能加载
• 存储页错误——不能存储
• 指令页错误——不能翻译指令

copy-on-write：子进程用于父进程页表的备份以及读权限，需要写时创建新页面。

lazy allocation：当进程使用sbrk分配内存时，内核将页表项标注为invalid，但是告诉进程分配成功。这样当进程实际使用内存时，才会进行分配。

paging from disk：可以将物理页写到磁盘，将页表项的设为无效。当需要使用时，内核知道这个页面在磁盘上，会在内存分配页面，将磁盘的页面读入。

vm的两个优点：

• 隔离
• 重定向

优化方式

系统调用从用户空间拷贝字符串需要进行很多处理（内核没法直接访问进程的虚拟空间），为了提升效率，可以将内存映射到每个进程的用户页表（加上特定的权限flags），这样内核就可以直接使用用户的页表，提升很多效率。比如linux就有这种设计。（Linux 中的 内核直接映射（__PAGE_KERNEL）

read, write系统调用会进行很多函数调用，显得低效，可以将一个文件映射到页表中，实现对文件的直接读写。

类似x86，RISC-V在进入函数时也会创建新的栈帧：第一个位置通常存储返回值，第二个位置存储上一个函数的栈帧起始位置。然后让本函数的栈帧指向第一个位置。（x86的ebp类似于s0，x86的esp类似于sp）

main
1c:	1141                	addi	sp,sp,-16
1e:	e406                	sd	ra,8(sp)
20:	e022                	sd	s0,0(sp)
22:	0800                	addi	s0,sp,16

中断和设备驱动

设备驱动执行代码包含两部分，一部分是在内核线程中，他会控制设备执行一些操作，另一部分是在中断，设备会通过中断返回结果。

console输入

type char -> 中断 -> trap -> devintr -> uartintr -> consoleintr(处理delete等特殊字符) -通过锁唤醒> consoleread

console输出

write system call -> uartputc ->uartstart
发送完一个字节会收到中断->uartintr->uartstart

第一种传输方式可以立刻发送发缓冲区的第一个字节，但再发送第二个字节时可能第一个字节还没发送完成，所有会直接返回。第二个及之后的字节会在收到发成完成中断后再发送。

通过中断以及维护着一个uart_tx_buf, uart_rx_buf，成功完成了进程和设备活动的解耦，允许进程与IO并发，尤其是当外部设备是慢速的并且需要快速响应。这又是IO并发。（平衡高速设备和低速设备的一种方式就是缓冲区）

驱动并发

两个需要关注的问题：

可以看到，consoleintr需要先使用acquire获取锁，这回包含驱动的数据。

一个进程在阻塞等待设备输入时，此时中断到来打断了另一个进程，中断没法决定自己打断的是哪个进程，也没法把数据发给用户空间（很难知道用户页表），所以只能做很少的工作（比如将数据拷贝到buffer），然后唤醒使用read的进程来处理。

时间中断

有是在硬件产生中断，在usertrap和kerneltrap中使用的yield就会导致进程的切换。

RISC-V需要在机器模式处理时钟中断，机器模式没有分页有单独的控制寄存器。在启动还处于机器模式时，

• 会配置CLINT硬件，让其计数达到一定值时产生中断，
• 会设置scratch 区域，用来保存寄存器的值，类似于trapframe。
• 设置mtvec，使能定时器中断。

时钟中断可以在用户或者内核代码中发送，时钟中断必须保证不破坏内核代码，基本策略是，当发生了时钟中断，触发一个软件中断，然后返回。而这个软件中断可以被禁止。

真实情况

xv6在执行内核程序时也允许时钟中断，这可以避免某个内核线程消耗太多CPU资源，但是我们也必须小心内核程序可能在某个地方被挂起，然后在其他地方继续运行。

UART驱动每次获取一个字节，这种是可编程IO，由软件驱动数据的移动，更高效的模式是DMA。

UART拷贝数据要先到内核的缓冲区，然后才拷贝到应用程序的缓冲区，这降低了效率，一些系统可以直接在用户空间和设备硬件之间移动数据。

锁

xv6内核可以交叉执行多个任务，原因有：

• 多个处理器硬件
• 分时复用CPU
• 设备中断

The word concurrency refers to situations in which
multiple instruction streams are interleaved, due to multiprocessor parallelism, thread switching,
or interrupts.

并发控制技术：针对以及支持并发性的技术。（锁）

竞态条件

锁

某些任务需要要么执行完，要么不执行，如果执行了但没有完全执行，那么当前的状态是无效的，单条指令或者原子指令不用考虑这个问题，因为他们占用CPU一个计算周期，不可能被分为两部分，如果有多条指令，则需要使用关中断或者锁来进行保护，使其不被打断。

spinlock以及sleep-locks

避免死锁：按照一定顺序申请锁。

避免中断申请被中断代码获得的锁：再使用中断使用过的锁之前，都应该关闭中断。（也可以更加保守一点，只要代码申请了任何锁，都要关闭中断）关中断只是关闭当前CPU的中断，其他CPU也可以产生中断，并且申请当前CPU已经获得的锁，这样是可以的。

编译器和CPU都可以对指令重新排序，这不会改变运行的结果，并发执行很可能导致多处理器上的不正确行为。CPU的顺序规则称为内存模型。

使用__sync_synchronize()来产生内存屏障。不能重排序存储和加载指令超过这个屏障。

spinlock的缺点：浪费时间，拥有spinlock时不能yield。（拥有spinlock时，中断处于关闭状态）

sleeplock使用spinlock来来保护锁的状态，并且会yield CPU并且释放spinlock。不能在中断使用sleeplock，因为会导致yield。

• 不能在spinlock临界区使用sleeplock，因为可能导致yield
• 但可以在sleeplock临界区使用spinlock。

真实世界

最好将锁隐藏在高级的结构（比如同步队列中）。

如果直接使用锁，最好使用一个工具来判断静态条件，因为很容易会忽略需要锁的不变量。

许多cpu都需要访问锁时，原子指令需要从其他cpu的cache移动到另一个缓存。这可能导致很多的资源消耗。

为了避免消耗，许多操作系统使用无锁数据结构或者算法，比如直接使用原子指令来插入链表，但这更复杂。

调度

共享内存的线程？

• xv6 kernel thread，每个用户进程有一个内核线程，这些内核线程之间共享相同的地址空间。
• 用户进程，不共享地址空间。

复用

实现复用有如下挑战：

• 如何切换进程
• 如何透明的切换用户进程——时钟中断
• CPU可能同时切换进程，这需要锁
• 进程的资源需要被释放，但某些东西不能自己释放，比如内核栈。
• 每个cpu应该知道当前执行的进程是什么，以便于系统调用影响正确的进程的状态。
• sleep和wakeup，要注意避免通知的丢失。

调度

进程切换期间也需要维护不变量，（这些不变量只有全部更改后才能到达一个有效的状态）。

• 不变量（切换出时的）：进程状态、进程内核线程的的寄存器，c->proc指向本进程
• 不变量（切换到的）：进程状态，p->context需要保存进程寄存器，c->proc指向本进程。

睡眠和唤醒

当在等待信号量时，为了避免空等，可以使用睡眠。当信号量计数增加时，可以使用唤醒。如下：

void V(struct semaphore *s)
{
    acquire(&s->lock);
    s->count += 1;
    wakeup(s);
    release(&s->lock);
}
void P(struct semaphore *s)
{
    acquire(&s->lock);
    while(s->count == 0)
    	sleep(s, &s->lock);
    s->count -= 1;
    release(&s->lock);
}

关键在于判断P 判断 s->count之后，消费者sleep之前，可以有一个生产者通过V增加信号量的计数，这样，消费者就丢失了一次唤醒信号。为了解决这个问题，在sleep的参数中加上一个s->lock,

void
sleep(void *chan, struct spinlock *lk)
{
  struct proc *p = myproc();
  acquire(&p->lock);  //DOC: sleeplock1
  release(lk);

  p->chan = chan;
  p->state = SLEEPING;
  sched();
  p->chan = 0;
  release(&p->lock);
  acquire(lk);
}

这样，sleep可以在申请p->lock后再来释放信号量的锁。因为就算此时有一个生产者通过wakeup来唤醒消费者，也必须先获得该进程的锁，而sleep代码中已经获得了进程锁，这就保证了生产者的wakeup没法再消费者彻底sleep前执行。（进程锁是在scheduler中的for-loop单次循环结束时释放）

有没有可能其他进程获取了进程锁，比如父进程调用wait，

可能有一种想法认为，有没有可能在sleep获取进程锁之前，消费者修改了信号量计数，但这是不可能的，因为V操作也必须遵循锁的申请顺序，先申请信号量锁，然后是进程锁。而当前进程已经获得了信号量锁，这避免了其他CPU的进程调用wakeup。而且信号量锁是spinlock，它在申请时会关闭中断，这也避免了当前CPU出现进程切换。

真实世界

xv6直接使用for-loop进行调度，而真实系统会有更多目标，比如公平以及高吞吐量。这可能导致优先级反转和车队效应。

• 优先级反转：高优先级进程等待低优先级进程的锁。
• 车队效应：

sleep和wakeup是简单有效的同步方式，还有其他方式，第一个挑战是，避免丢失唤醒问题，

• 单CPU环境下，可以在关闭中断，就可以避免当前进程被打断，同时因为没有别的CPU，就可以避免其他的wakeup执行。
• xv6 && FreeBSD，在sleep中添加了一个锁，在sleep时，因为涉及到进程状态修改，还需要获得进程的锁，所有可以在获取进程的锁后释放sleep参数中的锁。
• 文献plan9：使用一个回调函数，即将sleep前检测一次。
• Linux，使用进程等待队列，这个队列有内部锁。

All of these mechanisms share the same flavor: the sleep condition is protected by some
kind of lock dropped atomically during sleep.

在条件变量领域，sleep和wakeup又被称为wait和signal。

中断进程已经清理是非常复杂的。被清理的进程可能处于内核睡眠中，许多操作系统使用显示的机制比如longjmp（通常用于异常处理）来展开栈。还有其他方法可以唤醒睡眠的进程，即使等待的事件没有发生，比如Unix的信号，系统调用直接返回-1。

文件系统

如下几个挑战：

• 文件系统需要使用磁盘上的数据结构来代表命名的文件夹以及文件，来记录块的属性。
• 文件系统必须支持crash恢复，比如掉电之后，文件系统也必须是有效的。（类似于原子操作，保持不变量）
• 不同进程都可以同时操控文件系统，所有文件系统的代码必须协调维持不变量。
• 磁盘比内存慢很多，所以需要在内存维护常用的块。

概览

在xv6中，文件系统犹如上分层：

• 磁盘层：从磁盘读或者写blocks。
• Buffer cache层，缓存磁盘块以及同步，确保同时只有一个内核进程可以修改它。
• logging 层，给上层提供接口，使之可以在一次事务中对多个块进行多个操作，以及确保操作的原子性。
• inode层，提供了独立的文件，由一个inode数字以及一些包含文件数据的块组成。
• 文件夹层，包含inode数字以及文件名。
• pathname层，一个路径，比如/usr/rtm/xv6/fs.c。
• 文件描述符层，抽象Unix资源。

如何在磁盘存储数据以及其他信息，

Buffer cache层

buffer cache有两个任务：

• 同步访问磁盘，确保内存只有一个该块的备份，以及同时只有一个线程可以使用那个块。
• 缓存常用的块。

提供的接口：bread、bwrite、brealese。

• bread返回一个内存cache，可以在该区域读或者写磁盘。返回的buffer被spinlock锁上了，保证只有一个线程可以访问。
• bwrite将内存cache写入磁盘

buffer cache大小是固定的，当读取的磁盘block时，也会出现换入换出。

release策略，释放时，将buffer放到链表头的后面(虽然release了，但是没有释放对应的buffer，因为要从硬盘加载时，可以直接加载，避免分配空buffer页面，然后从硬盘读数据)，这样最近访问过的会停留在链表的开头，最久访问的停在链表的结尾

tips:

• 在磁盘缓存寻找磁盘上的某个扇区时的数据时，从bcache.head向后开始找（MRU），最近被访问过的也许很容易再次被访问。
• 在磁盘缓存寻找空闲缓冲区时，从bcache.head往前开始找（LRU), 没有被使用过的更可能是空闲的。

Logging layer

对磁盘文件进行操作时，因为涉及到多个操作，不是原子操作，当执行了部分指令突然掉电，产生的后果不可想象。xv6使用logging来解决这个问题。xv6系统不会直接往文件系统写数据结构，取而代之的是，

• 它在磁盘上放一个log来描述将要对磁盘的所以写操作。
• 一旦系统调用log了所有的操作，会向磁盘写一个特殊的commit记录来表示之前的log是一个完整的操作。
• 系统调用将写操作复制到磁盘上的文件系统数据结构中。（如果在这里crash了，那么部分区域会被写两次，但也不影响数据的有效性）
• 这些完成之后，系统调用会擦除磁盘的log。

如果系统crash以及reboot了，会根据log是否完整来恢复操作或者忽略。

先commit记录，然后再进行复制

Log的设计

磁盘超级块会指定log的地址。它由一个header块和一串待更新的块组成。header块包含一个含有扇区数字的数组，还有一个log扇区的数量，这个值为0代表没有完整的commit，非零代表存在完整的commit。

可以将多个进程的操作合并为一个事务，然后commit。系统调用中指定的写操作要保证原子性为了避免上述情况，log系统只在没有文件系统调用时才提交事务。

当多个文件系统系统调用完成，并执行end_op后，在最后的commit部分，会执行几个步骤：

• 从缓存往磁盘的log区域写数据
• 往磁盘的header块写数据——commit点
• 根据log的内容往磁盘写数据
• 清空header块

Block allocator

使用balloc和bfree来获取磁盘block，这两个函数必须在事务事务之间调用。

balloc根据bitmap来查找空闲的block，balloc会将从buffer中读取每一个block的状态，而buffer刚好是排他访问的（第二个进程访问该buffer时会sleep），所以balloc不用显示的锁。

Inode layer

inode可以指在磁盘的数据，它包含一个文件的大小，磁盘块序号等。也可以指在内存中的inode。

inode数字指的是inode的序号。

iget和iput用于获取inode节点指针（并不保证inode指向磁盘某个文件），每次调用iget，inode的ref值加一，调用iput，inode的ref减一，在ref大于0时，系统会保持该inode在cache中。iget提供非排他的访问。

ilock可以保证指定inode是从磁盘中读取出来的，该inode对应着磁盘的某个文件。（可以用来从磁盘读inode，也可以只是锁定inode）

在某些情况下，将索引节点指针的获取与锁定分离有助于避免死锁。inode的作用主要是同步对inode的访问，避免多个进程修改同个文件。

xv6 文件系统

硬盘文件系统结构dinode，目录项dirent

内存文件系统结构inode buffer，block buffer。

如何找到一个路径对应的文件：

首先内存中应该缓存有根目录的inode节点。从根目录开始，逐级解析，找给定路径名中的每个目录。比如找根目录下的home文件夹，首先要知道根目录对应的inode number，这个应该要记录在内存中，然后从磁盘把该inode number 对应的dinode结构体加载到内存的inode buffer，然后根据内存中的inode buffer获取根目录data部分对应的block number，然后从磁盘加载这些内容到block buffer，每个目录项目由名字和inode number两部分构成，检查其中的名字是否匹配我们的path中的文件名，找到了则会记录该次寻找的inode number。（之后在把该inode在磁盘的结构dinode加载到inode buffer……）,不断寻找，直到找到或者没有找到。

ext3

什么是IO并发：I/O并发允许系统在等待一个I/O操作完成的同时继续处理其他I/O请求。常见实现方式包括：多线程，异步IO，IO多路复用，DMA。

• 异步系统调用——>进而实现IO并发

  • 缺陷：调用返回了，文件操作可能未完成。
  • 解决方式：使用fsync同步。

• batching，

  • 每隔一定时间，关闭并写入当前事务，并打开新的事务
  • 写吸收，对多个相同块的写入只会导致一个块被写入磁盘。
  • 集中写入更高效（利于寻道）

• 并发性

  • 许多系统调用可以同时进行

提供给用户空间的虚拟内存

之前的内容，是在内核空间处理页错误，以便实现lazy alloc等。unix也给用户空间提供了捕获错误，处理错误的机会。比如使用信号捕获页错误，在信号处理函数中使用mmap，munmap，mprotect来处理页错误。

• 示例，但需要使用很多页面来存放斐波拉奇数列时，可以在用户空间处理页错误，每次访问新页面时，munmap旧页面，使得我们实际上同时只使用了一个页面。

微内核

VMM

• HPA：Host Physical Address
• HVA：Host Virtual Address
• GPA：Guest Physical Address
• GVA：Guest Virtual Address
• PDBR：页目录表物理基地址寄存器，X86上叫CR3
• EPT：扩展页表

• 影子页表——主要通过软件实现。
  • 创建：将物理页面设为写保护的，操作系统尝试写时，会触发vm exit，在其中进行gpa到hva的页面映射(类似malloc)，完成hva到hpa的映射（使用直接映射应该可以吧）。建立从gva到hpa的映射，即影子页表。
  • 使用：操作系统载入页表基址到PDBR时，会将被VMM截获这一特权指令，VMM会将对应的影子页表加载到PDBR, 从而实现真正的内存访问。
• EPT——引入EPTP寄存器，用来指向EPT页表基地址，查询得到GPA后，还会通过EPT进行再次转换得到HPA。（由于页表的地址也必须是物理地址，所以访问每级页表时，都需要先通过EPT得到HPA）
• 

虚拟设备

• 第一种方式，对硬件的完全的虚拟，当guest system访问硬件的寄存器时，产生vm exit 到 vmm中，由vmm进行模拟。相当低效。
• 第二种方式，vmm建立虚拟设备，guest system也需要安装次虚拟设备对应的驱动，避免像第一种方式反复产生vmm exit。
• 第三种方式，直接访问硬件，通常单个硬件可以供多个guest system使用。

对虚拟机的硬件支持 VT-x

guest system可以使用一套单独的特权寄存器。比如（stvec，scause ）

meltdown

有一些技术可以实现对内核的攻击，能够是我们在用户空间访问内核数据或者程序，即使pte设置了权限。有一种攻击方式是利用cpu的实现细节，比如：预测执行，缓存。

预测执行——提升性能的方式

通常在从内存加载一个数据时，需要花费几百个时钟周期，在这段时间内，CPU可能继续预测执行，等到数据加载完成时，再来确定是保留还是撤销预测执行的指令。（像下面第二行，会有分支预测，第四行ye’you）

r0 = <something>
r1 = valid // valid is in ram
if(r1 == 1){
	r2 = *r0
	r3 = r2 + 1
}
else{
	r3 = 0
}

内存屏障，如下代码：

critical_section();
unlock();

实际执行时，可能因为乱序执行（编译器重排或者CPU乱序执行），导致unlock之后，才回去更新critical中的内存，这导致了错误，所以通过memory barrier来保证：在它前面的 所有读写指令 必须完成。

什么时候需要考虑乱序执行：

• 在多线程程序中访问共享变量时
• 实现锁、CAS、自旋、无锁队列等低层同步原语时
• 在不使用同步机制时尝试自己“优化”并发

基本思想：将内核信息比如某一个bit为0还是1表示为某一个page是cached还是没有cached。流程如下：

• 执行大量加载操作，这可能要花费很多时钟周期，这导致后续的一段指令会以预测执行开始执行，比如9-13.
• 找到内核地址，读取其中的数据（如果L1cache命中了，预测执行时并不会检测页表标志位，会在retire时检测），根据其中一个位为0还是1将buffer[0-4096]还是buffer[4096-8192]加载到cache中。
• 内核检测到错误，引发pagefault，进入用户定义的pagefault handler，返回到用户程序。
• 检测从buffer[0-4096]和buffer[4096-8192]读取数据的时间差别，小的是cached过的，代表内核数据的对应位置是0.
• 重复很多次，将内核数据统统读取出来。

RCU——READ-COPY-UPDATE

很多内核数据需要大量读，少量写，为此，出现了读写锁。

读写锁可以很好的包含数据，但是降低了效率。主要是因为在执行CAS时，在修改l->n这个共享变量时，需要无效化该变量在不同cache上的对应的副本。（我们想避免在读取数据时修改n这个共享变量——避免使用读锁，因为它会导致性能的大幅降低）

不使用读锁时的一些问题：

• 写者正在修改链表中的某个元素——可能读到无效的数据
• 写者正在向链表插入某个元素——可能提前遇到尾节点。
• 写者正在从链表删除某个元素——可能读到freelist中的数据。

针对上面的问题，提出了一些解决方法：

• 先创建一个新的节点，在其中更新数据，将他的尾指针指向正确的位置，然后让他的前一个节点指向这个新的节点（应该不用使用原子指令吧，本来也只有一条指令）。
• 增加内存屏蔽指令，比如插入节点时，两个指针的修改是有先后顺序的。
• 什么时候删除被delete的节点
  • 肯定不能直接删除，因为可能有进程正在读取该节点
  • 为每个节点维持一个引用计数怎么样？肯定不行，我们就是为了避免读者修改引用计数才考虑使用RCU, 这里又给每一个节点增加一个引用计数，工作量大了n倍。
  • 给出如下两个限制，来保证删除时间
    • 读者使用RCU时，不能进行上下文切换。（能切换时，说明已经不使用上面的节点了）
    • 写者会等待所以核心进行一次上下文切换后，才删除上面的节点。

tips. 要不咋不共享了吧，太麻烦了吧。😧

• 比如kalloc实验，为每个核心维护一个半共享的链表。