MIT 6.828 - Lab - Locks

课程主页：https://pdos.csail.mit.edu/6.828/2023/index.html

Memory allocator

xv6 使用了一个空闲链表来管理空闲的物理内存。分配内存时从空闲链表中拿一个，释放内存时将其加入空闲链表，并使用一个自旋锁来保护空闲链表。当多个核同时在执行内存分配和释放时，会出现比较严重的冲突。本实验的目的是重新设计内存分配的数据结构，降低锁冲突。

一种很直观的思路是为每个核创建一个空闲链表：

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

初始化的时候，给每个核分配一定的内存：

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

在 free 的时候，将内存放入当前 CPU 对应的空闲链表即可：

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

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

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

  r = (struct run*)pa;
  int cpu = cpuid();

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

在分配内存时，先尝试从当前 CPU 对应的空闲链表中分配，如果当前 CPU 的空闲链表中没有可用内存，则尝试去其他 CPU 的空闲链表中拿。

void *
alloc(int cpu)
{
  struct run *r;

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

  if(r)
    memset((char*)r, 5, PGSIZE); // fill with junk
  return (void*)r;
}

void *
kalloc(void)
{
  struct run *r;
  int cpu = cpuid();
  r = alloc(cpu);
  if (r) {
    return r;
  }
  for (int i = 0; i < NCPU; i++) {
    if (i == cpu) {
      continue;
    }
    r = alloc(i);
    if (r) {
      return r;
    }
  }
  return r;
}

Buffer cache

xv6 的实现中，所有的 cache buffer 存储在 bcache.buf 中，使用一个空闲链表来管理，并使用 bcache.lock 来做并发保护。多个核并发地获取 buf 的时候，这里锁冲突会比较严重。

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;
} bcache;

改进的思路依然是把数据分散保存在互不干扰的多个链表中，每个链表使用一个锁来保护：

#define NBUCKET (NCPU + 7)

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 bucket[NBUCKET];
  struct spinlock bucket_lock[NBUCKET];
} bcache;

cache.buf[NBUF]:
[ buf | buf | buf | buf | buf | buf | buf | buf | buf | buf | buf | buf | buf | buf ]



cache.bucket:
[ head ]  <-> [ buf ] <-> [ buf ]
[ head ]  <-> [ buf ] <-> [ buf ] <-> [ buf ] <-> [ buf ]
[ head ]  <-> [ buf ] <-> [ buf ] <-> [ buf ]
[ head ]  <-> [ buf ]
[ head ]  <-> [ buf ] <-> [ buf ]

在初始化的时候，将所有的 buf 均匀地分散到所有的 bucket 中：

void
binit(void)
{
  struct buf *b;

  initlock(&bcache.lock, "bcache");

  for (int i = 0; i < NBUCKET; i++) {
    initlock(&bcache.bucket_lock[i], "bcache.bucket");
    // Create linked list of buffers
    bcache.bucket[i].prev = &bcache.bucket[i];
    bcache.bucket[i].next = &bcache.bucket[i];
  }

  for (b = bcache.buf; b < bcache.buf+ NBUF; b++) {
    int idx = (b - bcache.buf) % NBUCKET;
    b->next = bcache.bucket[idx].next;
    b->prev = &bcache.bucket[idx];
    initsleeplock(&b->lock, "buffer");
    bcache.bucket[idx].next->prev = b;
    bcache.bucket[idx].next = b;
  }
}

获取的时候，可以使用 blockno 映射到对应的 bucket，并在该 bucket 中查找。如果找不到，则找一个空闲的 buf 返回。

static struct buf*
bget(uint dev, uint blockno)
{
  struct buf *b;

  int idx = blockno % NBUCKET;
  acquire(&bcache.bucket_lock[idx]);
  // Is the block already cached?
  for (b = bcache.bucket[idx].next; b != &bcache.bucket[idx]; b = b->next) {
    if (b->dev == dev && b->blockno == blockno) {
      b->refcnt++;
      release(&bcache.bucket_lock[idx]);
      acquiresleep(&b->lock);
      return b;
    }
  }

  // 尝试在当前 bucket 中找一个空闲的 buf
  for (b = bcache.bucket[idx].prev; b != &bcache.bucket[idx]; b = b->prev) {
    if (b->refcnt == 0) {
      b->dev = dev;
      b->blockno = blockno;
      b->valid = 0;
      b->refcnt = 1;
      release(&bcache.bucket_lock[idx]);
      acquiresleep(&b->lock);
      return b;
    }
  }

  // 遍历所有的 bucket，寻找空闲的 buf
  for (int i = 0; i < NBUCKET; i++) {
    // 跳过前面已经查找过的 bucket
    if (i == idx) {
      continue;
    }
    acquire(&bcache.bucket_lock[i]);
    // Not cached.
    // Recycle the least recently used (LRU) unused buffer.
    for (b = bcache.bucket[i].prev; b != &bcache.bucket[i]; b = b->prev) {
      if (b->refcnt == 0) {
        b->dev = dev;
        b->blockno = blockno;
        b->valid = 0;
        b->refcnt = 1;

        // 在其他 bucket 中找到了空闲的 buf，此时需要将其移动到 blockno 对应的 bucket 中
        
        // 从原 bucket 中删除
        b->next->prev = b->prev;
        b->prev->next = b->next;

        // 插入到 blockno 对应的 bucket 中
        b->next = bcache.bucket[idx].next;
        b->prev = &bcache.bucket[idx];
        bcache.bucket[idx].next->prev = b;
        bcache.bucket[idx].next = b;

        release(&bcache.bucket_lock[idx]);
        release(&bcache.bucket_lock[i]);
        acquiresleep(&b->lock);
        return b;
      }
    }
    release(&bcache.bucket_lock[i]);
  }
  panic("bget: no buffers");
}

因为分配出去的 buf 一定存储在 b->blockno 对应的 bucket 中，因此在减小 refcount 的时候，可以只对 bucket 加锁。

void
brelse(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("brelse");

  releasesleep(&b->lock);
  int idx = b->blockno % NBUCKET;
  acquire(&bcache.bucket_lock[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.bucket[idx].next;
    b->prev = &bcache.bucket[idx];
    bcache.bucket[idx].next->prev = b;
    bcache.bucket[idx].next = b;
  }

  release(&bcache.bucket_lock[idx]);
}

完整变更

diff --git a/kernel/bio.c b/kernel/bio.c
index 60d91a6..7caa213 100644
--- a/kernel/bio.c
+++ b/kernel/bio.c
@@ -23,6 +23,8 @@
 #include "fs.h"
 #include "buf.h"
 
+#define NBUCKET (NCPU + 7)
+
 struct {
   struct spinlock lock;
   struct buf buf[NBUF];
@@ -30,7 +32,8 @@ struct {
   // 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 bucket[NBUCKET];
+  struct spinlock bucket_lock[NBUCKET];
 } bcache;
 
 void
@@ -40,15 +43,20 @@ binit(void)
 
   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;
+  for (int i = 0; i < NBUCKET; i++) {
+    initlock(&bcache.bucket_lock[i], "bcache.bucket");
+    // Create linked list of buffers
+    bcache.bucket[i].prev = &bcache.bucket[i];
+    bcache.bucket[i].next = &bcache.bucket[i];
+  }
+
+  for (b = bcache.buf; b < bcache.buf+ NBUF; b++) {
+    int idx = (b - bcache.buf) % NBUCKET;
+    b->next = bcache.bucket[idx].next;
+    b->prev = &bcache.bucket[idx];
     initsleeplock(&b->lock, "buffer");
-    bcache.head.next->prev = b;
-    bcache.head.next = b;
+    bcache.bucket[idx].next->prev = b;
+    bcache.bucket[idx].next = b;
   }
 }
 
@@ -60,31 +68,60 @@ bget(uint dev, uint blockno)
 {
   struct buf *b;
 
-  acquire(&bcache.lock);
-
+  int idx = blockno % NBUCKET;
+  acquire(&bcache.bucket_lock[idx]);
   // Is the block already cached?
-  for(b = bcache.head.next; b != &bcache.head; b = b->next){
-    if(b->dev == dev && b->blockno == blockno){
+  for (b = bcache.bucket[idx].next; b != &bcache.bucket[idx]; b = b->next) {
+    if (b->dev == dev && b->blockno == blockno) {
       b->refcnt++;
-      release(&bcache.lock);
+      release(&bcache.bucket_lock[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) {
+  for (b = bcache.bucket[idx].prev; b != &bcache.bucket[idx]; b = b->prev) {
+    if (b->refcnt == 0) {
       b->dev = dev;
       b->blockno = blockno;
       b->valid = 0;
       b->refcnt = 1;
-      release(&bcache.lock);
+      release(&bcache.bucket_lock[idx]);
       acquiresleep(&b->lock);
       return b;
     }
   }
+
+  for (int i = 0; i < NBUCKET; i++) {
+    if (i == idx) {
+      continue;
+    }
+    acquire(&bcache.bucket_lock[i]);
+    // Not cached.
+    // Recycle the least recently used (LRU) unused buffer.
+    for (b = bcache.bucket[i].prev; b != &bcache.bucket[i]; b = b->prev) {
+      if (b->refcnt == 0) {
+        b->dev = dev;
+        b->blockno = blockno;
+        b->valid = 0;
+        b->refcnt = 1;
+
+        b->next->prev = b->prev;
+        b->prev->next = b->next;
+
+        b->next = bcache.bucket[idx].next;
+        b->prev = &bcache.bucket[idx];
+        bcache.bucket[idx].next->prev = b;
+        bcache.bucket[idx].next = b;
+
+        release(&bcache.bucket_lock[idx]);
+        release(&bcache.bucket_lock[i]);
+        acquiresleep(&b->lock);
+        return b;
+      }
+    }
+    release(&bcache.bucket_lock[i]);
+  }
   panic("bget: no buffers");
 }
 
@@ -120,20 +157,20 @@ brelse(struct buf *b)
     panic("brelse");
 
   releasesleep(&b->lock);
-
-  acquire(&bcache.lock);
+  int idx = b->blockno % NBUCKET;
+  acquire(&bcache.bucket_lock[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->next = bcache.bucket[idx].next;
+    b->prev = &bcache.bucket[idx];
+    bcache.bucket[idx].next->prev = b;
+    bcache.bucket[idx].next = b;
   }
-  
-  release(&bcache.lock);
+
+  release(&bcache.bucket_lock[idx]);
 }
 
 void
diff --git a/kernel/kalloc.c b/kernel/kalloc.c
index 0699e7e..f616f3b 100644
--- a/kernel/kalloc.c
+++ b/kernel/kalloc.c
@@ -21,13 +21,18 @@ struct run {
 struct {
   struct spinlock lock;
   struct run *freelist;
-} kmem;
+} kmem[NCPU];
 
 void
 kinit()
 {
-  initlock(&kmem.lock, "kmem");
-  freerange(end, (void*)PHYSTOP);
+  int step = (PHYSTOP - (uint64)end) / NCPU;
+  void *start = end;
+  for (int i = 0; i < NCPU; i++) {
+    initlock(&kmem[i].lock, "kmem");
+    freerange(start, start + step);
+    start += step;
+  }
 }
 
 void
@@ -55,28 +60,50 @@ kfree(void *pa)
   memset(pa, 1, PGSIZE);
 
   r = (struct run*)pa;
+  int cpu = cpuid();
 
-  acquire(&kmem.lock);
-  r->next = kmem.freelist;
-  kmem.freelist = r;
-  release(&kmem.lock);
+  acquire(&kmem[cpu].lock);
+  r->next = kmem[cpu].freelist;
+  kmem[cpu].freelist = r;
+  release(&kmem[cpu].lock);
 }
 
 // Allocate one 4096-byte page of physical memory.
 // Returns a pointer that the kernel can use.
 // Returns 0 if the memory cannot be allocated.
 void *
-kalloc(void)
+alloc(int cpu)
 {
   struct run *r;
 
-  acquire(&kmem.lock);
-  r = kmem.freelist;
+  acquire(&kmem[cpu].lock);
+  r = kmem[cpu].freelist;
   if(r)
-    kmem.freelist = r->next;
-  release(&kmem.lock);
+    kmem[cpu].freelist = r->next;
+  release(&kmem[cpu].lock);
 
   if(r)
     memset((char*)r, 5, PGSIZE); // fill with junk
   return (void*)r;
 }
+
+void *
+kalloc(void)
+{
+  struct run *r;
+  int cpu = cpuid();
+  r = alloc(cpu);
+  if (r) {
+    return r;
+  }
+  for (int i = 0; i < NCPU; i++) {
+    if (i == cpu) {
+      continue;
+    }
+    r = alloc(i);
+    if (r) {
+      return r;
+    }
+  }
+  return r;
+}