MIT 6.S081 | 0x08 Locks

2024-07-04

链接：https://pdos.csail.mit.edu/6.S081/2021/labs/lock.html
难度：🟦🟥

Before writing code, make sure to read the following parts from the xv6 book:
Chapter 6: “Locking” and the corresponding code.
Section 3.5: “Code: Physical memory allocator”
Section 8.1 through 8.3: “Overview”, “Buffer cache layer”, and “Code: Buffer cache”

🟦 Memory allocator

Your job is to implement per-CPU freelists, and stealing when a CPU’s free list is empty. You must give all of your locks names that start with “kmem”. That is, you should call initlock for each of your locks, and pass a name that starts with “kmem”. Run kalloctest to see if your implementation has reduced lock contention. To check that it can still allocate all of memory, run usertests sbrkmuch. Your output will look similar to that shown below, with much-reduced contention in total on kmem locks, although the specific numbers will differ. Make sure all tests in usertests pass. make grade should say that the kalloctests pass.

分析

xv6 使用 kalloc/kfree 来对内存进行分配和释放，全局只用一把锁进行管理：

struct run {
  struct run *next;
};

struct {
  struct spinlock lock;
  struct run *freelist;
} kmem;

这种实现简单直接，但是在遇到多核情况下时，对 kmem.lock 这把锁的竞争会很激烈。所以这一 Part 的任务就是想一个办法减少锁的竞争。

题目也给出了解决的思路，就是为每个 CPU 分别维护一个 freelist 和对应的锁，这样每个锁的粒度就会变小，锁的竞争也就减小了。整理一下，我们需要做的工作有：

为每个 CPU 分别维护一个 freelist 和 lock
当某个 CPU 的 freelist 为空时，从其他 CPU 的 freelist 中偷取一些

第一部分直接就能写出来，将 kmem 这个结构体变成一个数组就行，CPU 的数量已经用宏定义好了：

struct {
  struct spinlock lock;
  struct run *freelist;
} kmem[NCPU];

这样每个 CPU 都有了对应的 freelist 与 lock，在 kalloc/kfree 的时候，使用 cpuid() 获取对应的 CPU 号进行操作就好。剩下就是第二个部分的工作了：当一个 CPU 的 freelist 为空时，怎么从其他的 CPU 那里“偷”一些空间出来？

这个时候就要遍历 kmem 的其他 freelist 了，在遍历的时候记得跳过自己的 cpuid，在读取每个 CPU 的 freelist 时也要记得加锁。具体的细节可以看下面的代码。

代码

diff --git a/kernel/kalloc.c b/kernel/kalloc.c
index 0699e7e..ce21891 100644
--- a/kernel/kalloc.c
+++ b/kernel/kalloc.c
@@ -9,6 +9,8 @@
 #include "riscv.h"
 #include "defs.h"
 
+#define TOTAL_STEAL 64
+
 void freerange(void *pa_start, void *pa_end);
 
 extern char end[]; // first address after kernel.
@@ -21,12 +23,25 @@ struct run {
 struct {
   struct spinlock lock;
   struct run *freelist;
-} kmem;
+} kmem[NCPU];
+
+char *kmem_names[] = {
+  "kmem_lock_0",
+  "kmem_lock_1",
+  "kmem_lock_2",
+  "kmem_lock_3",
+  "kmem_lock_4",
+  "kmem_lock_5",
+  "kmem_lock_6",
+  "kmem_lock_7",
+};
 
 void
 kinit()
 {
-  initlock(&kmem.lock, "kmem");
+  for (int i = 0; i < NCPU; i++) {
+    initlock(&kmem[i].lock, kmem_names[i]);
+  }
   freerange(end, (void*)PHYSTOP);
 }
 
@@ -35,8 +50,10 @@ freerange(void *pa_start, void *pa_end)
 {
   char *p;
   p = (char*)PGROUNDUP((uint64)pa_start);
+  push_off();
   for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE)
     kfree(p);
+  pop_off();
 }
 
 // Free the page of physical memory pointed at by pa,
@@ -56,10 +73,13 @@ kfree(void *pa)
 
   r = (struct run*)pa;
 
-  acquire(&kmem.lock);
-  r->next = kmem.freelist;
-  kmem.freelist = r;
-  release(&kmem.lock);
+  push_off();
+  int cpu_id = cpuid();
+  acquire(&kmem[cpu_id].lock);
+  r->next = kmem[cpu_id].freelist;
+  kmem[cpu_id].freelist = r;
+  release(&kmem[cpu_id].lock);
+  pop_off();
 }
 
 // Allocate one 4096-byte page of physical memory.
@@ -70,11 +90,37 @@ kalloc(void)
 {
   struct run *r;
 
-  acquire(&kmem.lock);
-  r = kmem.freelist;
-  if(r)
-    kmem.freelist = r->next;
-  release(&kmem.lock);
+  push_off();
+  int cpu_id = cpuid();
+
+  acquire(&kmem[cpu_id].lock);
+  if (!kmem[cpu_id].freelist) {
+    // no enough space, try to steal space from other cpu
+    int list_left = TOTAL_STEAL;
+    for (int i = 0; i < NCPU; i++) {
+      if (i == cpu_id) continue;
+      acquire(&kmem[i].lock);
+      struct run *r_other_cpu = kmem[i].freelist;
+      while (r_other_cpu && list_left) {
+        // find free space, steal!
+        kmem[i].freelist = r_other_cpu->next;
+        r_other_cpu->next = kmem[cpu_id].freelist;
+        kmem[cpu_id].freelist = r_other_cpu;
+        r_other_cpu = kmem[i].freelist;
+        list_left--;
+      }
+      release(&kmem[i].lock);
+      if (list_left == 0) break;
+    }
+  }
+  release(&kmem[cpu_id].lock);
+
+  r = kmem[cpu_id].freelist;
+  if(r) {
+    kmem[cpu_id].freelist = r->next;
+  }
+
+  pop_off();
 
   if(r)
     memset((char*)r, 5, PGSIZE); // fill with junk

🟥 Buffer cache

Modify the block cache so that the number of acquire loop iterations for all locks in the bcache is close to zero when running bcachetest. Ideally the sum of the counts for all locks involved in the block cache should be zero, but it’s OK if the sum is less than 500. Modify bget and brelse so that concurrent lookups and releases for different blocks that are in the bcache are unlikely to conflict on locks (e.g., don’t all have to wait for bcache.lock). You must maintain the invariant that at most one copy of each block is cached. When you are done, your output should be similar to that shown below (though not identical). Make sure usertests still passes. make grade should pass all tests when you are done.

分析

操作系统在读取硬盘数据时，会将读取到的数据缓存到内存中，这样下次再读取相同的数据时就可以直接从内存中读取，而不用再次从硬盘中读取。这个缓存就是缓冲区缓存（Buffer Cache），在 xv6 中是通过 bcache 这个结构体来实现的：

struct {
  struct spinlock lock;
  struct buf buf[NBUF];

  // Linked list of all buffers, through prev/next.
  // head.next is most recently used.
  struct buf head;
} bcache;

这个 bcache 是真的在多 CPU 多进程中共享的，全局只有一个锁：bcache.lock，锁竞争很激烈。提示有说用哈希表来减少竞争，其实就是一个大锁变成多个小锁，先设置 NBUCKET 个桶，每个桶对应一个锁，然后在 bget 和 brelse 中对这些锁进行操作。下面是修改后的 bcache 结构体：

struct {
  struct spinlock lock;
  struct buf buf[NBUF];

  // Linked list of all buffers, through prev/next.
  // head.next is most recently used.
  struct buf head[NBUCKET];
  struct spinlock head_lock[NBUCKET];
} bcache;

原先只有一个 bcache.head，LRU 算法实现起来很方便。但是在有多个桶的时候，LRU 算法就比较捉急，因为每个桶都可能有一个最少使用的块，或者全局最少使用的块和当前操作的桶不在一个桶中，逻辑很复杂。提示也贴心地指出了如何解决：直接记录 buf 上次使用的 ticks 即可。找到全局 ticks 最少的那个 buf，然后将其放到当前桶的最前面。

最后很可能出问题的地方就是如何保证不发生死锁，这里有个博客讨论了这个问题，可以仔细去看看。总之一定要仔细考虑每个锁的顺序，不要出现循环等待的情况。

代码

diff --git a/kernel/bio.c b/kernel/bio.c
index 60d91a6..255d23e 100644
--- a/kernel/bio.c
+++ b/kernel/bio.c
@@ -23,32 +23,57 @@
 #include "fs.h"
 #include "buf.h"
 
+#define NBUCKET 13
+
+extern uint ticks;
+
 struct {
-  struct spinlock lock;
   struct buf buf[NBUF];
 
   // Linked list of all buffers, through prev/next.
   // Sorted by how recently the buffer was used.
   // head.next is most recent, head.prev is least.
-  struct buf head;
+  struct buf head[NBUCKET];
+  struct spinlock head_lock[NBUCKET];
 } bcache;
 
+char * head_lock_name[] = {
+  "bcache_head_lock_0",
+  "bcache_head_lock_1",
+  "bcache_head_lock_2",
+  "bcache_head_lock_3",
+  "bcache_head_lock_4",
+  "bcache_head_lock_5",
+  "bcache_head_lock_6",
+  "bcache_head_lock_7",
+  "bcache_head_lock_8",
+  "bcache_head_lock_9",
+  "bcache_head_lock_10",
+  "bcache_head_lock_11",
+  "bcache_head_lock_12",
+};
+
 void
 binit(void)
 {
   struct buf *b;
 
-  initlock(&bcache.lock, "bcache");
-
   // Create linked list of buffers
-  bcache.head.prev = &bcache.head;
-  bcache.head.next = &bcache.head;
-  for(b = bcache.buf; b < bcache.buf+NBUF; b++){
-    b->next = bcache.head.next;
-    b->prev = &bcache.head;
-    initsleeplock(&b->lock, "buffer");
-    bcache.head.next->prev = b;
-    bcache.head.next = b;
+  for (int i = 0; i < NBUCKET; i++) {
+    initlock(&bcache.head_lock[i], head_lock_name[i]);
+    bcache.head[i].prev = &bcache.head[i];
+    bcache.head[i].next = &bcache.head[i];
+  }
+  for (int i = 0; i < NBUF; i++) {
+    uint hash_idx = i % NBUCKET;
+    b = &bcache.buf[i];
+
+    b->next = bcache.head[hash_idx].next;
+    b->prev = &bcache.head[hash_idx];
+    b->last_use = ticks;
+    initsleeplock(&bcache.buf[i].lock, "buffer");
+    bcache.head[hash_idx].next->prev = b;
+    bcache.head[hash_idx].next = b;
   }
 }
 
@@ -59,32 +84,67 @@ static struct buf*
 bget(uint dev, uint blockno)
 {
   struct buf *b;
+  uint min_last_use;
+
+  uint hash_idx = blockno % NBUCKET;
 
-  acquire(&bcache.lock);
+  acquire(&bcache.head_lock[hash_idx]);
 
   // Is the block already cached?
-  for(b = bcache.head.next; b != &bcache.head; b = b->next){
+  for(b = bcache.head[hash_idx].next; b != &bcache.head[hash_idx]; b = b->next){
     if(b->dev == dev && b->blockno == blockno){
       b->refcnt++;
-      release(&bcache.lock);
+      b->last_use = ticks;
+      release(&bcache.head_lock[hash_idx]);
       acquiresleep(&b->lock);
       return b;
     }
   }
 
   // Not cached.
-  // Recycle the least recently used (LRU) unused buffer.
-  for(b = bcache.head.prev; b != &bcache.head; b = b->prev){
-    if(b->refcnt == 0) {
+  // Recycle the least recently used unused buffer.
+  min_last_use = __UINT32_MAX__;
+  b = 0;
+  for (int i = 0; i < NBUF; i++) {
+    if (bcache.buf[i].refcnt == 0 && min_last_use > bcache.buf[i].last_use) {
+      min_last_use = bcache.buf[i].last_use;
+      b = &bcache.buf[i];
+    }
+  }
+
+  if (b != 0) {
+    // Find an available buffer
+    uint no = b->blockno;
+    if (no % NBUCKET == hash_idx) {
       b->dev = dev;
       b->blockno = blockno;
       b->valid = 0;
       b->refcnt = 1;
-      release(&bcache.lock);
+      b->last_use = ticks;
+      release(&bcache.head_lock[hash_idx]);
       acquiresleep(&b->lock);
       return b;
     }
+    acquire(&bcache.head_lock[no % NBUCKET]);
+    b->dev = dev;
+    b->blockno = blockno;
+    b->valid = 0;
+    b->refcnt = 1;
+    b->last_use = ticks;
+    // Steal!
+    b->next->prev = b->prev;
+    b->prev->next = b->next;
+    release(&bcache.head_lock[no % NBUCKET]);
+
+    b->next = bcache.head[hash_idx].next;
+    b->prev = &bcache.head[hash_idx];
+    bcache.head[hash_idx].next->prev = b;
+    bcache.head[hash_idx].next = b;
+    release(&bcache.head_lock[hash_idx]);
+    acquiresleep(&b->lock);
+    return b;
   }
+
   panic("bget: no buffers");
 }
 
@@ -121,33 +181,29 @@ brelse(struct buf *b)
 
   releasesleep(&b->lock);
 
-  acquire(&bcache.lock);
+  uint hash_idx = b->blockno % NBUCKET;
+  acquire(&bcache.head_lock[hash_idx]);
   b->refcnt--;
   if (b->refcnt == 0) {
-    // no one is waiting for it.
-    b->next->prev = b->prev;
-    b->prev->next = b->next;
-    b->next = bcache.head.next;
-    b->prev = &bcache.head;
-    bcache.head.next->prev = b;
-    bcache.head.next = b;
+    b->last_use = ticks;
   }
-  
-  release(&bcache.lock);
+  release(&bcache.head_lock[hash_idx]);
 }
 
 void
 bpin(struct buf *b) {
-  acquire(&bcache.lock);
+  uint hash_idx = b->blockno % NBUCKET;
+  acquire(&bcache.head_lock[hash_idx]);
   b->refcnt++;
-  release(&bcache.lock);
+  release(&bcache.head_lock[hash_idx]);
 }
 
 void
 bunpin(struct buf *b) {
-  acquire(&bcache.lock);
+  uint hash_idx = b->blockno % NBUCKET;
+  acquire(&bcache.head_lock[hash_idx]);
   b->refcnt--;
-  release(&bcache.lock);
+  release(&bcache.head_lock[hash_idx]);
 }
 
 
diff --git a/kernel/buf.h b/kernel/buf.h
index 4616e9e..635ec1e 100644
--- a/kernel/buf.h
+++ b/kernel/buf.h
@@ -5,6 +5,7 @@ struct buf {
   uint blockno;
   struct sleeplock lock;
   uint refcnt;
+  uint last_use;
   struct buf *prev; // LRU cache list
   struct buf *next;
   uchar data[BSIZE];

其他

这次的实验在最后 make grade 的时候又出了问题：kalloctest 超时，然后 usertests 中的 textwrite 一直过不了。前面这个问题我一开始是在 kalloc 中一次只偷 1 页的内容，后来改成了一次偷 64 页，然后还是超时了，在网上搜了搜其他人的实现¹，原封不动抄过来，还是超时 😩。

textwrites 的那个测试一直过不了，下面是这个测试的部分内容：

  ...
  pid = fork();
  if(pid == 0) {
    volatile int *addr = (int *) 0;
    *addr = 10;
    exit(1);
  } else if(pid < 0){
  ...

这段测试用于验证操作系统内核是否正确实现了对程序试图向只读（通常是文本段，存放代码）内存区域写入数据的行为的保护。这种保护通常通过引发一个段错误（segmentation fault）来实现，这是大多数现代操作系统为了防止程序破坏自身或其他程序的一种安全机制。可是我没有通过。就很烦，转到其他分支进行测试，居然都没通过 😂（在做 COW 的时候就发现了），暂时还没想好咋该 ~~太菜了呜呜呜~~，之后再看吧。

https://blog.miigon.net/posts/s081-lab8-locks/