Home

MIT 6.828 - 7. Lab 07: Locks

Tags: MIT 6.828

实验总结

  1. 本次实验用时约 15 个小时。
  2. 收获是对多核、无锁原语理解更深入了。
  3. 最后一个实验的实现有问题，我不知道怎么改了。

实验结束后的全部代码在：https://github.com/monkey2000/xv6-riscv/tree/lock/

0. 实验准备

实验指导链接

上来直接：

$ cd xv6-riscv-fall19
$ git checkout lock

1. Memory allocator

这块是要给 Paged Allocator 加入 per-core freelist 和 stealing 。

// Physical memory allocator, for user processes,
// kernel stacks, page-table pages,
// and pipe buffers. Allocates whole 4096-byte pages.

#include "types.h"
#include "param.h"
#include "memlayout.h"
#include "spinlock.h"
#include "riscv.h"
#include "defs.h"

void freerange(void *pa_start, void *pa_end);

extern char end[]; // first address after kernel.
                   // defined by kernel.ld.

struct run {
  struct run *next;
};

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

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

void
freerange(void *pa_start, void *pa_end)
{
  push_off();

  char *p;
  p = (char*)PGROUNDUP((uint64)pa_start);
  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE)
    kfree(p);
  
  pop_off();
}

// Free the page of physical memory pointed at by v,
// which normally should have been returned by a
// call to kalloc().  (The exception is when
// initializing the allocator; see kinit above.)
void
kfree(void *pa)
{
  push_off();
  int id = cpuid();
  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;

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

  pop_off();
}

// 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)
{
  push_off();
  int id = cpuid();

  struct run *r;

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

  if(!r) {
    for(int i=0;i<NCPU;i++) {
      acquire(&kmem.lock[i]);
      r = kmem.freelist[i];
      if(r)
        kmem.freelist[i] = r->next;
      release(&kmem.lock[i]);

      if(r)
        break;
    }
  }

  if(r)
    memset((char*)r, 5, PGSIZE); // fill with junk
  
  pop_off();

  return (void*)r;
}

2. Buffer cache

这个是给 fs 的 buffer io 加入多核支持，我的问题似乎是没有把 buffer freelist 设计成 per-core 的（回头改，因为实验指导里没让这么做 TAT），所以说用无锁原语胡乱实现一通，也没有起到好的效果。

 
// Buffer cache.
//
// The buffer cache is a linked list of buf structures holding
// cached copies of disk block contents.  Caching disk blocks
// in memory reduces the number of disk reads and also provides
// a synchronization point for disk blocks used by multiple processes.
//
// Interface:
// * To get a buffer for a particular disk block, call bread.
// * After changing buffer data, call bwrite to write it to disk.
// * When done with the buffer, call brelse.
// * Do not use the buffer after calling brelse.
// * Only one process at a time can use a buffer,
//     so do not keep them longer than necessary.


#include "types.h"
#include "param.h"
#include "spinlock.h"
#include "sleeplock.h"
#include "riscv.h"
#include "defs.h"
#include "fs.h"
#include "buf.h"

struct {
  struct buf buf[NBUF];
  uint unused[NBUF];

  // unused buffers
  // struct spinlock unused_lock;
  // struct buf unused_head;

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

void
binit(void)
{
  struct buf *b;

  // initlock(&bcache.unused_lock, "bcache.unused");

  for(int i = 0; i < NBUCKET; i++)
    initlock(&bcache.bucket_lock[i], "bcache.bucket");

  // Create linked list of unused buffers
  // bcache.unused_head.prev = &bcache.unused_head;
  // bcache.unused_head.next = &bcache.unused_head;
  for(b = bcache.buf; b < bcache.buf+NBUF; b++){
    // b->next = bcache.unused_head.next;
    // b->prev = &bcache.unused_head;
    initsleeplock(&b->lock, "buffer");
    b->used = 0;
    // bcache.unused_head.next->prev = b;
    // bcache.unused_head.next = b;
  }

  // Initialize buckets
  for(int i = 0; i < NBUCKET; i++) {
    bcache.bucket_head[i].prev = &bcache.bucket_head[i];
    bcache.bucket_head[i].next = &bcache.bucket_head[i];
  }
}

// Look through buffer cache for block on device dev.
// If not found, allocate a buffer.
// In either case, return locked buffer.
static struct buf*
bget(uint dev, uint blockno)
{
  struct buf *b;

  uint id = ((((uint64)dev) << 32) | blockno) % NBUCKET;

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

  // Not cached; recycle an unused buffer.
  // acquire(&bcache.unused_lock);
  for (int i = 0; i < NBUF; i++) {
    if(!bcache.buf[i].used && __sync_bool_compare_and_swap(&bcache.buf[i].used, 0, 1)) {
      b = &bcache.buf[i];
      if(b->refcnt == 0) {
        // release(&bcache.unused_lock);

        b->dev = dev;
        b->blockno = blockno;
        b->valid = 0;
        b->refcnt = 1;

        
        b->next = bcache.bucket_head[id].next;
        b->prev = &bcache.bucket_head[id];
        bcache.bucket_head[id].next->prev = b;
        bcache.bucket_head[id].next = b;
        release(&bcache.bucket_lock[id]);
        acquiresleep(&b->lock);
        return b;
      }
    }
  }

  panic("bget: no buffers");
}

// Return a locked buf with the contents of the indicated block.
struct buf*
bread(uint dev, uint blockno)
{
  struct buf *b;

  b = bget(dev, blockno);
  if(!b->valid) {
    virtio_disk_rw(b->dev, b, 0);
    b->valid = 1;
  }
  return b;
}

// Write b's contents to disk.  Must be locked.
void
bwrite(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("bwrite");
  virtio_disk_rw(b->dev, b, 1);
}

// Release a locked buffer.
// Move to the head of the MRU list.
void
brelse(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("brelse");

  releasesleep(&b->lock);

  uint id = ((((uint64)b->dev) << 32) | b->blockno) % NBUCKET;

  acquire(&bcache.bucket_lock[id]);
  b->refcnt--;
  if (b->refcnt == 0) {
    // no one is waiting for it.
    b->next->prev = b->prev;
    b->prev->next = b->next;
    // acquire(&bcache.unused_lock);
    // b->next = bcache.unused_head.next;
    // b->prev = &bcache.unused_head;
    // bcache.unused_head.next->prev = b;
    // bcache.unused_head.next = b;
    // release(&bcache.unused_lock);
    if(!__sync_bool_compare_and_swap(&b->used, 1, 0))
      panic("brelse_cas");
  }
  
  release(&bcache.bucket_lock[id]);
}

void
bpin(struct buf *b) {
  uint id = ((((uint64)b->dev) << 32) | b->blockno) % NBUCKET;

  acquire(&bcache.bucket_lock[id]);
  b->refcnt++;
  release(&bcache.bucket_lock[id]);
}

void
bunpin(struct buf *b) {
  uint id = ((((uint64)b->dev) << 32) | b->blockno) % NBUCKET;

  acquire(&bcache.bucket_lock[id]);
  b->refcnt--;
  release(&bcache.bucket_lock[id]);
}
知识共享许可协议 2000 - 2099 MonKey's Blog | 自豪的采用 Vite + React + MDX + KaTeX