陈浪平的博客

先导知识

xv6的文件系统设计的层次是这样子的：

1
2
3
4
5
6
7

system calls
  name ops | FD ops
  inodes
  inode cache
  log
  buffer cache
  virtio_disk driver

磁盘本身是按照扇区作为基本单位的，一个扇区是512字节。绝大部分的操作系统一页是4096字节，所以是8个扇区；但是xv6的一个block是2个扇区。

xv6的磁盘的布局是这样子的：

1
2
3
4
5
6
7

0: unused
1: super block (size, ninodes)
2: log for transactions
32: array of inodes, packed into blocks
45: block in-use bitmap (0=free, 1=used)
46: file/dir content blocks
end of disk

每一个inode的结构是这个样子的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

type (free, file, directory, device)
nlink
size
addrs[12+1]

------------------------------------------------------      
  
struct inode {
  uint dev;           // Device number
  uint inum;          // Inode number
  int ref;            // Reference count
  struct sleeplock lock; // protects everything below here
  int valid;          // inode has been read from disk?

  short type;         // copy of disk inode
  short major;
  short minor;
  short nlink;
  uint size;
  uint addrs[NDIRECT+1];
};

其中一个inode的大小是64字节。这里可能仔细算一算会发现，上面的inode明显超过了64字节，这是因为上面的这个inode并不是存放在磁盘上的，而是存放在内存之中的。存放在磁盘上对应的数据结构是dinode：

1
2
3
4
5
6
7
8

struct dinode {
  short type;           // File type
  short major;          // Major device number (T_DEVICE only)
  short minor;          // Minor device number (T_DEVICE only)
  short nlink;          // Number of links to inode in file system
  uint size;            // Size of file (bytes)
  uint addrs[NDIRECT+1];   // Data block addresses
};

short = 4字节，uint = 8字节，正好64字节。

当执行一个echo hi > x ，可以简单追踪一下对于磁盘来说发生了什么，其实主要是三个步骤，分别是创建x这个文件、往x里面写入文件、更新对应的inode。具体步骤如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// create
bwrite: block 33 by ialloc   // allocate inode in inode block 33
bwrite: block 33 by iupdate  // update inode (e.g., set nlink)
bwrite: block 46 by writei   // write directory entry, adding "x" by dirlink()
bwrite: block 32 by iupdate  // update directory inode, because inode may have changed
bwrite: block 33 by iupdate  // itrunc new inode (even though nothing changed)
// write
bwrite: block 45 by balloc   // allocate a block in bitmap block 45
bwrite: block 595 by bzero   // zero the allocated block (block 524)
bwrite: block 595 by writei  // write to it (hi)
bwrite: block 33 by iupdate  // update inode
// write
bwrite: block 595 by writei  // write to it (\n)
bwrite: block 33 by iupdate  // update inode

首先是在33号inode中分配了对应的inode，并且更新了这个inode（挺奇怪为什么不是在同一个write来完成的）然后在当前的目录中新增一个文件x，即在direntry中新增这个文件名和inode之间的映射。然后还需要去访问对应的父节点的inode进行修改。

创建好inode之后就可以就去对应的数据块中进行数据的写入了？还首先需要去bitmap中声明该数据块被使用了，然后就可以去对应的数据块进行读取了。

第三部分其实是因为，echo本身还会往最后加入一个\n，所以还有一次write。

Large files（中等）

在原版xv6中，由于一个iNode只有13个数据block，其中一个是间接区（256个），另外12个是直接区，一共是268个block，一个block在xv6中是1K，所以原版xv6只能支持最大268KB的文件。

有一个测试程序bigfile，能够检测最大的文件能够到多大，要达到65803才可以。

一共13个block指针，那么11个作为直接指针，1个作为一级的间接区，1个作为二级的间接区。这样就是 11 + 1*256 + 1 * 256 * 256 = 65803刚刚好。

Preliminaries

最开始的文件系统是由mkfs来构造的，而原始的xv6一共是200000个blocks，这个其实是由kernel/param.h中的FSSIZE来进行控制的。

What to Look At

在磁盘上的iNode数据对应的数据结构是struct dinode，除此之外比较重要的代码是fs.c中的bmap()，确保你了解这个函数在做什么，

Your Job

把其中的一个直接块改成双间接层的块。

hints：

• 确保你了解了bmap，推荐画一个关系图。
• 思考一下如何索引这些间接块和二级间接块。
• 如果你修改了NDIRECT，记得删除fs.img然后重新构造一个。
• 对于任何bread，不要忘记使用brelse
• 确保itrunc释放所有的块。

修改常量

根据上面的计算，我们应该把直接的块映射改成11。并且修改对应的数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
13

#define NDIRECT 11
#define NINDIRECT (BSIZE / sizeof(uint))
#define MAXFILE (NDIRECT + NINDIRECT + NINDIRECT * NINDIRECT)

// On-disk inode structure
struct dinode {
  short type;           // File type
  short major;          // Major device number (T_DEVICE only)
  short minor;          // Minor device number (T_DEVICE only)
  short nlink;          // Number of links to inode in file system
  uint size;            // Size of file (bytes)
  uint addrs[NDIRECT+2];   // Data block addresses
};

同理还有inode别忘记也修改。

修改bmap

• 确定你真正的目标。这一点其实caoz也写过一篇对应的文章，在书中对应的是十个你想变得更富有的原因，然后找到其中最最重要的三条。
• 想象自己富有的样子。因为图形化远远比文字更直观，所以书中推荐搞一本相册，里面贴上愿望的照片，这样就能激励你自己。
• 搞一个梦想存储罐，开始为你的梦想存钱。

为了能够有效建立自己的自信心，可以弄一个成功日记，在里面记录了自己成功做的事，不用很成功的事情，就算是自己完成了一些小事，也可以记进去。

• 为别人解决问题，也就是你的技能、学识等自我价值能够满足他人，就可以进行收费获取报酬。
• 把精力放到你知道的、你了解的和你擅长的上面去。
• 72小时定理：做事要趁早，不然超过72小时，人们就会对它失去兴趣，就再也不会去做了。
• 毁掉你的信用卡（这条我不同意）
• 按照最少的金额偿还你的贷款（也就是如果能分24期，就不要分12期；虽然我个人并不反对这一点，但是欠别人钱总让我觉得很不爽，所以我如果可能应该都是选择选择少的分期）
• 除去那些必须的金额，你还会剩下一些钱。将这些钱一半存起来，另外一半用于还贷。不要急着还款，这样当你债务清零的时候，你的资产也是零，这样是非常不好的。
• 积累你的资产，用这些资产来产生利息，把利息用来消费。
• 书中推荐的资金分配比例是：投资：储蓄：消费 = 5 : 4 : 1，注意，这里说的资金是，扣除掉最低的那些生活所需的金额之后的钱。

如何投资

书中提出了三条投资原则：

1. 投资要保证资金的安全。
2. 当然我们希望收益越高越好，但是这条其实是和第一条矛盾的，所以我觉得更加准确的来说，应该是
3. 操作要简单。

股票是什么？

你拥有这个公司的一部分，如果这个公司出售了，那你就能按照股票所占的比例获得对应的金额；当然实际中肯定是其他人希望从你手里购买这个股票，然后你卖给他，然后才能获得收益。当然前提是那个人认为这个股票能够带来更多的收益。

只要你不出售股票，就不会有亏损（当然也不会有盈利）。只要你持有股票，那么公司就必须定时向你分红。

基金就是把各种股票综合在一起，用来进行风险对冲的一种投资方式。

将一部分资金投入到流动性好的理财产品中。

Lab8 locks

在本实验中，您将获得重新设计代码以提高并行编程的经验。多核计算机上并行性差的常见原因是锁争用较高。改善并行性通常涉及更改数据结构和锁定策略，以减少争用。 您将为xv6内存分配器和块缓存执行此操作。

先导知识

在Linux中，一个进程可以有多个用户态的线程；但是在xv6中，只有一个用户态的线程；xv6只有两个线程，分别是用户态的线程和内核态的线程。

xv6在两种情况下，会切换CPU从一个进程到另外一个进程，第一种是当进程等待IO的时候，等待子进程退出的时候，或者是调用sleep系统调用的时候。第二种就是强制一些长时间占用CPU的进程切换，也就是利用时钟中断强制切换。

在设计xv6的时候，考虑到了多核的情况，它每一个CPU的核心会有一个调度器线程——scheduler thread，且每一个调度器线程都具有一个栈和context。

进行进程切换的时候，还是比较复杂的。首先是通过系统调用或者是中断进入到内核线程，然后通过上下文切换到当前CPU的调度程序线程（scheduler thread），然后上下文切换到新进程的内核线程，最后通过trap返回到用户级进程。每一个CPU都会有自己的调度线程。假设从进程A切换到进程B，下图是xv6中如何进行切换的：

在进行切换的时候其实最重要的就是栈的切换和PC计数器（但是你会发现代码中，其实我们并没有保存PC寄存器23333）的切换。在xv6中的swtch是用汇编代码写的，本质上就是保存第一个参数所指的所有寄存器，恢复第二个参数所指的寄存器。swtch的函数声明是这样子的：

1

void swtch(struct context*, struct context*);

也就是把当前寄存器的值放入第一个context中，把第二个context指向的寄存器的值放入当前的寄存器中。

usertrap可能会调用yeild（当时钟中断发生的时候，内核主动放弃了CPU，转而调用yeild），而在yeild中则是会使用sched()，然后在sched()之中会调用swtch，swtch即是核心函数，把当前的进程的context存起来，并且恢复mycpu()->context，也就是说当调用完swtch之后，接下来就会执行上一次保存在cpu->context的ra寄存器中的地址的代码了。并且此时用的是上一次调用swtch的内核栈。

每个进程至少有两个线程，一个用户线程，一个内核线程。进程要么正在执行其用户线程，要么就是在内核线程中处理系统调用或中断。

trapframe中存的是用户的寄存器，而context存放的则是RISC-V的寄存器。从一个进程切换到另外一个进程，大致需要以下过程：

1. 首先需要先进入到内核（线程），那么就需要把用户的寄存器保存到p->trapframe。
2. 然后从内核线程切换到scheduler thread，然后把内核线程的寄存器保存到p->context中。
3. scheduler thread到另外一个内核线程，从p->context中恢复到内核线程的寄存器。
4. 从内核恢复到用户线程，从p->trapframe中恢复。

追踪一下

写了一个最简单的死循环函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include "kernel/types.h"
#include "user/user.h"

int main(int argc, char const *argv[])
{
    int pid;
    char c;

    pid = fork();
    if (pid == 0)
    {
        c = 's';
    }
    else
    {
        c = 'f';
    }

    // 无限循环
    for (int i = 0;; i++)
    {
        if (i % 6000000 == 0)
        {
            write(2, &c, 1);
        }
    }

    return 0;
}

这个程序就是两个父子进程轮流打印一下字符，父进程打印f，子进程打印s。

然后记得把qemu的核心数设置成1来模拟单核。

如果希望能够追踪时钟中断，那么显然应该在devintr这个函数返回2的时候下断点，所以我挑选了一下，就把断点下在了b trap.c:207，然后使用finish完成当前的函数，这个时候就会发现此时到了usertrap，因为我们写的是死循环，而此时必然是时间到了，所以触发的是timer interrupt，所以会触发一个yeild来强制其进行进程的切换。

此时打印一下，p->name = “spin”，pid = 3（如果是4，推荐换成继续执行变成3，这样之后会比较方便，当然本质上没有区别）。紧接着我们跟着进入yeild里面。发现yeild本身首先会获取当前的进程，并且它会给当前的进程上锁，然后把当前的进程修改成RUNNABLE状态（其实此时还是进程自己在执行，相当于进程自己把自己的状态从RUNNING切换到了RUNNABLE，但是由于有锁，所以不需要担心）。

改完状态之后就会进入到sched，这里才是切换的关键。核心的一句其实就是swtch(&p->context, &mycpu()->context);，即把当前的寄存器的值放入到进程的context中，然后把调度线程的context加载到当前寄存器中，而这里是不需要修改pc的，因为return address已经修改了，只需要一个ret指令就可以回去。

此时的mycpu()->context可能还不太明确，这里面到底是什么，这里可以先放一放，跟踪下去就知道了。

之后就进入到kernel/proc.c的scheduler()函数中了。这是因为mycpu()->context中的ra指向的就是这里。

此时此刻还没有切换好，因为进来的时候拿了锁，但是还没有释放，所以第一件事情就是释放锁。此时此刻其实已经没有在任何进程中运行了，而是在CPU的调度器线程中执行了。然后调度器线程会从列表中找到一个RUNNABLE的进程（会先持有锁），然后又开始了。

首先把这个进程的状态设置成RUNNING，然后开始调用swtch(&c->context, &p->context);，这里是核心。

这里的这一句，把当前的cpu的寄存器放到了调度器线程的context中，然后把即将运行的这个进程的上下文加载进来，然后一调用ret就会跳转到当时进程离开的地方继续执行，其实就是当时swtch的下一句，然后就可以正常通过usertrap中返回了。

而调度器线程中的context也保证了，下一次调度的时候返回的时候仍然会回到scheduler中的swtch下一句继续执行。

Uthread: switching between threads（中等）

在这个练习中，你需要自己设计一套用户线程的切换。现在已经有了两个实现的文件，分别是user/uthread.c和user/uthread_switch.S。

然后你需要完成user/uthread.c中的函数thread_create() 和 thread_schedule() ；以及 user/uthread_switch.S中的thread_switch 。其中的一点是，thread_schedule()调度第一个线程的时候，线程需要执行对应的create函数中传递进来的函数，而且需要在自己的栈中执行。同时还需要确保在切换线程的时候，能够保存寄存器和恢复寄存器，那么应该把这些寄存器的信息放在哪里呢？

hints：

• thread_switch需要保存寄存器，保存那些callee-save寄存器即可，为什么？
• user/uthread.asm对于debug来说很有用。

其实就是类似在已经提供好的代码之上进行一点代码的填写，然后就完成了，仿照的是POSIX标准写的pthread代码。

确定线程的结构体

由于线程切换需要保存它需要寄存器，所以必然需要一个数据结构来保存寄存器内容，而正好proc.h里面有对应的结构，所以直接引入头文件然后就可以开始使用了。

1
2
3
4
5

struct thread {
  char       stack[STACK_SIZE]; /* the thread's stack */
  int        state;             /* FREE, RUNNING, RUNNABLE */
  struct     context context;   /* 上下文  */
};

修改创建线程函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void 
thread_create(void (*func)())
{
  struct thread *t;

  for (t = all_thread; t < all_thread + MAX_THREAD; t++) {
    if (t->state == FREE) break;
  }
  t->state = RUNNABLE;
  // YOUR CODE HERE
  // 使ra指向开始的func地址，这样调度完成直接就去执行func了
  t->context.ra = (uint64)func;
  // 设置好对应的栈地址，这里注意需要让栈指向地址最大处
  t->context.sp = (uint64)t->stack+STACK_SIZE;
}

修改线程切换函数

1
2
3
4
5
6
7
8
9
10
11

if (current_thread != next_thread) {         /* switch threads?  */
  next_thread->state = RUNNING;
  t = current_thread;
  current_thread = next_thread;
  /* YOUR CODE HERE
     * Invoke thread_switch to switch from t to next_thread:
     * thread_switch(??, ??);
     */
  thread_switch(&t->context,&next_thread->context);
} else
  next_thread = 0;

就是最基本的线程切换函数，把当前的线程保存到t中（此时t是当前的线程），然后切换到新的线程中。

汇编代码

其实就是抄袭之前的swtch的代码，真的是一模一样的抄。

结果

然后就这样过了…..但是不得不说，这里的代码确实值得好好学一学，因为这些代码就是用户级线程的精华。

Using threads（中等）

这个作业不需要在xv6中完成，而是需要在真正具有多核处理器上运行。这一部分探索一下Unix自带的pthread函数库，notxv6/ph.c包含了一个简单的hash table，如果是单线程中使用是正确的，但是多线程就会有问题。

这个作业其实就是给一个hashtable，然后把它改装成concurrent hashtable（简化版的），并且要保证正确性和快速性。

如果要保证正确性，那直接在put前面加个锁，就完事儿了，正确性肯定没问题；但是如果为了速度，就需要把整个hashtable切分成几个桶，这样相当于把锁的粒度给细化了。

实在是太简单了，就不贴代码了。

Barrier（中等）

类似java中的CountDownLatch，在代码中设置一个点，当所有的线程都到达这个点之后，才开始继续执行。需要用到条件变量。同样这个实现需要在真实的设备上做，不要在xv6中实现。

提示，可以使用下面的函数：

1
2

pthread_cond_wait(&cond, &mutex);  // go to sleep on cond, releasing lock mutex, acquiring upon wake up
pthread_cond_broadcast(&cond);     // wake up every thread sleeping on cond

总结

如果了解了xv6中的进程切换，那么实现一个用户线程真的是轻而易举；同时如果有一点点并发的经验，那么实现这两个实验也是轻而易举。

书中的第六章讲的是锁，但是这部分配套的实验其实是：

当时是先做的实验，然后才看的Locking这一章。现在知道了，因为lab中的物理内存的引用计数数组是共享的，所以访问它修改它需要获取锁。

锁实现

Xv6，包括现在的很多操作系统，实现锁的最基本都是依靠底层的CPU指令，比如compare and swap，原子交换；亦或者是test and set这类。这个原子性是由指令来进行保证的。但是并不是一定要原子指令的支持，因为没有原子指令也是可以实现锁的。

那么首先第一个问题，CPU又是怎么实现原子性指令的呢？如果具体要追溯下去，这是Intel的商业机密，更加具体可以参考这个回答。这里只能简单分析一下：

On most instructions a lock prefix must be explicitly used except for the xchg instruction where the lock prefix is implied if the instruction involves a memory address.

几乎所有的指令都需要用lock来修饰才能保证原子性，但是xchg这条指令如果访问的是内存地址，那么会自动加上lock，所以本质上来说，一条指令如果希望它是原子性的，那么就加上Lock。

在java中，CAS本质上用的LOCK CMPXCHG，虽然和上面的xchg不一样，但是在多CPU环境下，虚拟机会自动帮你加上lock前缀，让它成为原子性的。

这里需要了解，CAS虽然底层用了lock cmpxchg这条指令，但是它确实是无锁编程，因为指令上的lock仅仅保证了这条指令的原子性，代价远远比操作系统实现的lock要小的多。而操作系统实现的lock，会让线程等待很久很久（相对指令来说）。无锁编程在于把这些会引发冲突的代码整合成原子性的代码。

其实lock前缀只有在多核的CPU上才需要，在单核的CPU中是不需要的。lock的实现方式是这样的：

• 当访问的数据在内存时，通过在总线锁（也看到有人说其实是更加细粒度的，不过总线锁在理解层面更加简单）实现原子性；
• 当访问的数据在处理器的缓存时，通过缓存一致性协议（如MESI协议）实现原子性；

所以了解了指令的原子性，就可以理解锁的基本理念了。

锁与中断处理

想象这么一个场景，如果在用户态有一个进程获取了锁，然后此时发生了中断，那么操作系统就进到中断处理程序中处理，如果这个中断处理程序也需要获取这把锁怎么办？中断处理程序永远也回不去，同时用户态的代码也永远执行不了，这样就造成了死锁。xv6的解决办法很简单，在获取锁的代码中，直接把中断给关了，然后只有当锁被释放了，才打开中断。

锁的种类

在xv6中实现了两种锁，第一种就是熟悉的自旋锁，如果没获得锁就一直死循环。还有一种是sleep锁，也就是没有获取到锁的话，就会使用sleep，不过这是之后的内容。

这个其实就是Lab5的拓展，在上一个lab中我们实现了sbrk的懒分配，到了这一lab就实现进程的写时复制。

在xv6的原始实现中，父进程是直接把自己的所有的内存复制给了子进程。

写时复制技术，在子进程的页表中创建的条目是指向父进程的物理页中的，并且让子进程页表和父进程页表中的PTE都不能写（也就是不论是父进程还是子进程，都不能写）。不论任何一方想要去写这个物理内存，就会触发一个page fault，然后为触发这个错误的进程分配一个物理页，把原来的那一页的内容复制过来，这次的PTE_W位可以设置成1。

当然写时复制技术也有棘手的地方：如果有多个进程都指向一个相同的物理内存，到时候要怎么回收？

Implement copy-on write（困难）

这里首先介绍一下xv6的测试程序：cowtest，它的第一个测试就是分配了超过物理内存一半的空间，所以如果子进程老老实实复制了，那么必然超过了内存的限制。

这里介绍一下这个测试程序会测试哪些内容：

• 修改父进程复制物理内存的代码。在父进程和子进程都记得要把PTE_W清掉。
• 修改中断处理程序。在其中的page fault处理函数中，使用kalloc分配新的物理页面，把旧的页面复制到新的页面中，并且设置新的页面的PTE_W。
• 需要确保，只有当所有的进程都不引用当前的物理页之后，物理页才会被kfree掉，但是这个引用计数应该保存在哪里呢？
• 别忘记还需要修改copyout这个函数

一些hints：

• 上一个lazy分配的实验已经让你很熟悉相关的技术了，但是请不要基于上一个实验，忘了上一个实验吧，这里重新开始。
• 记录一下PTE是否用于COW是很有用的，可以通过RSW的保留位来解决。
• usertests还进行了一些别的测试，所以不要忘记使用它进行测试。
• 在kernel/riscv.h中还有别的一些很有用的宏和定义。
• 如果COW的页错误在没有空闲的物理页的时候发生了，那么应该干掉进程。

从上面的提示中我们可以得到几个信息，首先是我们必然需要一个数组用来记录每个物理页的引用；其次是我们可以自己定义RSW位，这里直接把图片复制过来：

也就是图中的8和9是可以让我们自己定义的。有了这些知识，就可以开始做啦。

添加物理页的引用

我在kernel/vm.c中新增了一个数组：

1

int physical_ref[(PHYSTOP - KERNBASE) / PGSIZE]; // 每个物理页的引用计数器

新增页表的标志位

在kernel/riscv.h中，新增一个宏：

1

#define PTE_COW (1L << 8)  // cow位，表示这个页是被父子进程共享的

这里其实8和9都是OK的。

修改fork过程

fork的时候调用了uvmcopy()进行物理页的复制，所以进行物理内存的修改：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

// Given a parent process's page table, copy
// its memory into a child's page table.
// Copies both the page table and the
// physical memory.
// returns 0 on success, -1 on failure.
// frees any allocated pages on failure.
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;

  for(i = 0; i < sz; i += PGSIZE){
    if((pte = walk(old, i, 0)) == 0)
      panic("uvmcopy: pte should exist");
    if((*pte & PTE_V) == 0)
      panic("uvmcopy: page not present");
    pa = PTE2PA(*pte);
    // 删除掉PTE_W
    *pte = *pte & ~PTE_W;
    // 新增PTE_COW位
    *pte = *pte | PTE_COW;
    flags = PTE_FLAGS(*pte);
    // 目前不分配物理内存
    // if((mem = kalloc()) == 0)
    //   goto err;
    // memmove(mem, (char*)pa, PGSIZE);
    physical_ref[(pa - KERNBASE)/PGSIZE]++;
    if(mappages(new, i, PGSIZE, pa, flags) != 0){
      // 由于上一步并没有分配物理内存，所以映射关系安装失败的话，不需要释放物理内存
      // kfree(mem);
      goto err;
    }
  }
  return 0;

 err:
  uvmunmap(new, 0, i / PGSIZE, 1);
  return -1;
}

处理physical_ref

我一开始是这么想的，当使用mappages安装对应的关系的时候，也就是此时有虚拟内存映射了物理内存，需要将引用计数加一；而uvmunmap则是解绑对应的关系，所以需要在这里将对应的引用计数进行减一处理。当减完发现是0了，才需要将物理内存清空。代码是这样的：

1
2
3
4
5
6
7
8
9

........
*pte = PA2PTE(pa) | perm | PTE_V;
if (pa >= KERNBASE)
{
  // 引用计数加一
  physical_ref[(pa - KERNBASE) / PGSIZE] += 1;
}
if(a == last)
........

1
2
3
4
5
6
7
8
9
10
11
12
13
14

if(do_free){
  uint64 pa = PTE2PA(*pte);
  if (pa >= KERNBASE)
  {
    // 引用计数减一
    physical_ref[(pa - KERNBASE) / PGSIZE] -= 1;
  }

  if (physical_ref[(pa - KERNBASE) / PGSIZE] == 0)
  {
    // 释放物理页
    kfree((void *)pa);
  }
}

后来想想不对劲，因为mappages函数是绑定虚拟地址到物理地址的映射关系，如果不绑定难道物理内存的引用计数就应该是0吗？同时也不应该在uvmunmap中进行引用计数减一。

仔细想想其实应该在kalloc和kfree两个函数中进行引用计数的增加和减少：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void *
kalloc(void)
{
  struct run *r;

  acquire(&kmem.lock);
  r = kmem.freelist;
  if(r)
    kmem.freelist = r->next;
  release(&kmem.lock);

  if(r){
    memset((char*)r, 5, PGSIZE); // fill with junk
    if ((uint64)r >= KERNBASE)
    {
      // 引用计数加一
      physical_ref[((uint64)r - KERNBASE) / PGSIZE] += 1;
    }
  }
  return (void*)r;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

void
kfree(void *pa)
{
  struct run *r;

  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");

  // 首先引用计数减一
  physical_ref[((uint64)pa - KERNBASE) / PGSIZE] -= 1;
  if(physical_ref[((uint64)pa - KERNBASE) / PGSIZE] > 0){
    // 如果此时还有引用的，那就啥也不做
    return;
  }

  // Fill with junk to catch dangling refs.
  memset(pa, 1, PGSIZE);

  r = (struct run*)pa;

  acquire(&kmem.lock);
  r->next = kmem.freelist;
  kmem.freelist = r;
  release(&kmem.lock);
}

处理缺页中断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

else if(r_scause() == 13 || r_scause() == 15){
  // 进入中断处理程序
  uint64 va = r_stval();
  uint64 pa;
  uint flag;
  pte_t *pte;

  if (va >= MAXVA)
  {
    p->killed = 1;
    panic("va >= MAXVA");
  }

  if (va <= PGROUNDDOWN(p->trapframe->sp) && va >= PGROUNDDOWN(p->trapframe->sp) - PGSIZE)
  {
    p->killed = 1;
    panic("it is in guard page!");
  }
  va = PGROUNDDOWN(va);
  if ((pte = walk(p->pagetable, va, 0)) == 0 || (*pte & PTE_COW) == 0)
  {
    // 如果没有对应的pte，或者pte并不是cow，说明这次缺页中断并不是cow引发的，那处理不了
    p->killed = 1;
  }else{
    // 如果能进到这里，说明已经确定是COW引发的中断了
    pa = PTE2PA(*pte);
    flag = PTE_FLAGS(*pte);
    char *mem = kalloc();
    if (mem == 0)
    {
      // 分配物理页失败
      // panic("kalloc!");
      p->killed = 1;
      goto done;
    }
    // 复制到新开辟的页中
    memmove(mem, (char*)pa, PGSIZE);
    // 清除原来的物理页，这里不一定真正的清除
    kfree((void*)pa);
    // 修改对应的pte，把COW拿掉，W加上
    flag = (flag & ~PTE_COW) | PTE_W;
    *pte = PA2PTE((uint64)mem) | flag;
  }
}

还是抄了很多的之前的lazy分配233333。因为有了PTE_COW位判断，所以很容易很判断出是不是因为COW引发的。然后就复制一份，并且设置对应的PTE就可以了。

最后不要忘记我们的引用数组需要清零init设置、以及对freerange的时候的特殊处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void
kinit()
{
  for(int i = 0;i<(PHYSTOP - KERNBASE) / PGSIZE;i++){
    physical_ref[i] = 0;
  }
  initlock(&kmem.lock, "kmem");
  freerange(end, (void*)PHYSTOP);
}

void
freerange(void *pa_start, void *pa_end)
{
  char *p;
  p = (char*)PGROUNDUP((uint64)pa_start);
  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE){
    physical_ref[((uint64)p - KERNBASE)/PGSIZE]++;
    kfree(p);
  }
}

这里的freerange为什么要先1，是因为后面有一个kfree，前面的加一正好让kfree能够正常工作。

总结

这部分完成了COW，总体来说我觉得难度不大，照着思路做其实很容易。

但是上面的代码其实是有问题的，而且这一个lab是位于locking这个章节下面，所以其实它是希望你能够使用锁来对这个引用数组操作，否则可能会出现多个进程同时处理这个引用数组导致问题的发生。

这部分并没有对应的lab，但是个人觉得理解它还是非常有必要的。我个人认为重在理解这个过程，因为我自己应该是不会去接触驱动的。

先导知识

我们之前在使用fork的时候，是直接复制的物理内存。然而这么做其实是非常浪费的，因为在实际中发现，fork完之后立马执行exec的概率很大，而exec是去加载特定的镜像，所以复制这个动作完全是浪费的。

除了fork这个系统调用以外，还有一些可以利用懒复制的应用。比如sbrk，它的作用是开辟内存空间，但是如果应用要了就开辟空间，而应用要是最后没去使用就很浪费；所以比较好的做法是在页表中给它新增映射关系，但是并不分配真正的物理内存；还有一个就是可以不全加载一个进程的所有内容到内存中，而是真正要被用到的时候才加载进来。

Eliminate allocation from sbrk()（简单）

这个就是把分配物理内存的代码移除，但是proc的size记得要加。还有一个比较容易忽视的点是，当缩小的时候，页表的内存空间必须马上回收（这个其实是第三个小实验的内容….）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

uint64
sys_sbrk(void)
{
  int addr;
  int n;
  struct proc *p;
  p = myproc();

  if (argint(0, &n) < 0)
    return -1;
  addr = p->sz;
  // if(growproc(n) < 0)
  //   return -1;
  if (n < 0)
    p->sz = uvmdealloc(p->pagetable, p->sz, p->sz + n);
  else
    p->sz += n;
  return addr;
}

先导知识

有三种方式能够让CPU进入到特权模式：系统调用、中断和异常。

CPU层面的支持

首先需要介绍一下CPU中的寄存器支持。

• stvec：存放中断处理程序的地址
• sepc：将当前将要被中断的程序的PC放到这里。因为PC马上就要放入stvec中的地址了。
• scause：描述了发生trap的原因。
• sscratch：这个值是内核放的，在后面处理的时候非常方便。
• sstatus：这其中有两个位非常重要，一个是SIE，用来屏蔽中断的。还有一个是SPP，用来控制是用户模式还是监督者模式。

还有一个寄存器，也挺重要的，satp用来指向当前所用的页表。

硬件过程

有了CPU的寄存器介绍，就可以稍微简单来看下硬件发生一次trap的时候具体是怎么操作的（定时器的中断是一个例外）。

1. 如果发生的是设备中断，而且发生当前屏蔽了中断，那就直接不管，也没有下面那么多过程了。所以如果在屏蔽中断的时候，此时磁盘完成读写，那消息就丢掉了。
2. 禁用中断（防止在中断的时候被中断），就是把SIE给清除掉。
3. 把当前程序的PC赋值到sepc寄存器中。
4. 把目前是用户态还是监督者（内核态）信息记录在SPP。
5. 设置好scause寄存器。
6. CPU把模式转换成监督者模式（也就是x86中的ring0）
7. 把stvec的值写入到pc中，这样就可以执行中断处理程序了。

仔细看一看会发现，基本上就处理了上面的4个寄存器，除此之外，内核栈的切换、页表的切换等等完全没有做。这是为了留给操作系统最大的灵活性，让操作系统自己来实现。

mac

我的设备用的是mbp2018款的，操作系统用的是macOS: 11.2.1-x86_64（Big Sur）

xv6的绝大部分的按照这个教程走即可。

对于拥有Homebrew来说其实只需要：

1
2
3
4

$ brew tap riscv/riscv				// 设置brew源
$ brew install riscv-tools		// 安装对应的工具
PATH=$PATH:/usr/local/opt/riscv-gnu-toolchain/bin		// 加入到路径中
$ brew install qemu						// 安装虚拟机

一套安装下来，如果命令riscv64-unknown-elf-gcc --version可以输出riscv架构下的gcc的版本号，说明gcc安装成功。同理qemu-system-riscv64 --version如果输出了qemu的版本号，说明qemu安装成功。

到这里，如果能够成功启动xv6，那么基本上可以说安装成功了。