Qifan Wang
The Jungle Book
A blog for programming

MIT 6.S081 Lab 8: Locks

I have no methods; all I do is to accept people as they are.

6.S081课程的第八个Lab，为 xv6 的堆与buf缓冲区提供细粒度锁机制，减少 lock contention 以提高性能。

Memory allocator

在 xv6 原本设计中，内核用一个 freelist 负责堆资源的管理。试想多个进程频繁地增长收缩其地址空间，导致并发调用 kalloc 与 kfree 。由于 kmem.lock 保护 freelist ，同一时间只有一个执行流拥有这个锁，这会导致大量 acquire 中的循环在竞争这个锁。这也是所谓的 lock contention 现象。衡量 lock contention 的指标就是 acquire 中的循环迭代次数 loop iterations。p.s. 因为是自旋锁。 kalloctest 程序在衡量 xv6 中 kmem/bcache 的锁争用。我们的任务在于将 kmem 与 bcache 中共享数据切割成更小的粒度，用细粒度的锁提高并发性。

在 Linux 系统中可以用 perf-lock 相关命令分析统计不同的锁行为，其中包括锁争用的统计。具体见perf-lock mannual

per-CPU freelists

设计上，可以将 freelist 分成每个 CPU 负责单独一个。在某个CPU上执行流只会向其负责的 freelist 申请与归还内存。

//kernel/kalloc.c
struct {
  struct spinlock lock;
  struct run *freelist;
  char lockName[8];
} kmem[NCPU];

void
kinit()
{
  int i;
  
  for(i = 0; i < NCPU; ++i) {
    snprintf(kmem[i].lockName, 8, "kmem_%d", i);
    initlock(&kmem[i].lock, kmem[i].lockName);
  }

  freerange(end, (void*)PHYSTOP);
}

源文件 kernel/proc.c 中的函数 cpuid 可以返回当前的 CPU 核心编号。但需要小心，只有在 push_off() 与 pop_off() 关闭/开启中断的 scope 中，才能保证返回的 CPU ID 是不变的。否则，一个执行流在调用 cpuid 后，又被调度到其他 CPU 上执行，原来返回的 CPU 核心编号就是错的。

修改后的 kfree 函数如下。可以看到，使用 cpu_id 的代码必须关闭中断。

// 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)
{
  struct run *r;
  int cpu_id;

  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;

  // get current cpu id
  push_off();
  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();
}

stealing

将原来唯一的资源切成小粒度时，有个问题需要注意，如果某个 CPU 的 freelist 被使用完，但仍有 kalloc 申请资源，其实仍有机会为其分配。因为其他的 freelist 可能仍有空闲页面。这时就需要实现从其他资源富裕的 freelist 窃取资源。 stealing 的思想是简单的，但是实现上需要注意死锁与资源泄漏的情况。

所有 freelist 的锁都是平级的。试想，如果 CPU A 的 freelist 用尽，在持有锁 A 的情况下，申请 CPU B 的锁，但 B 也有可能正在申请 A 的锁，造成循环等待，产生死锁。为了避免这个问题，就是在设计上，执行流不能在同时持有一个以上的平级的锁。

以下两个工具函数，steal_page 与 add2tail。前者通过快慢指针，从其他freelist夺取一半的空闲页面；后者将 content 添加到 head 指示的 freelist 的末尾。

static struct run*
steal_page(int cpu_id) {
  struct run *slow, *fast, *ret;
  int i;

  for (i = 0; i < NCPU; ++i) {
    if (cpu_id == i)
      continue;
    
    acquire(&kmem[i].lock);
    if (kmem[i].freelist) {
      slow = fast = kmem[i].freelist;

      while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
      }

      
      ret = kmem[i].freelist;
      kmem[i].freelist = slow->next;
      slow->next = 0;
      release(&kmem[i].lock);
      return ret;
      
    }
    release(&kmem[i].lock);
  }

  return 0;
}


static void 
add2tail(struct run* head, struct run* content) {
  while (head->next)
    head = head->next;
  head->next = content;
}

修改的 kalloc 代码看上去很冗余，但是必要的。比如在调用 steal_page 后，又再次检查当前的 freelist 是否为空，并做不同处理。这个是必须的。因为在 stealing 阶段，没有持有当前 CPU freelist 的锁，之前检查得出的结论是失效的。p.s. 在这里其实没有失效，因为当前 CPU 的执行流关闭了中断，没有其他执行流能让这个空 freelist 获取空闲页面。但这个检查的模式在多线程模型中是必要的，因为关中断不是在所有设计中都是一致的，其他线程可能会修改之前的数据。

// 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)
{
  struct run *r;
  int cpu_id;

  // get current cpu id
  push_off();
  cpu_id = cpuid();
  
  acquire(&kmem[cpu_id].lock);
  r = kmem[cpu_id].freelist;
  if(r)
    kmem[cpu_id].freelist = r->next;
  release(&kmem[cpu_id].lock);

  // steal page for empty free-list
  if (r == 0) {

    r = steal_page(cpu_id);
    
    if(r) {
      acquire(&kmem[cpu_id].lock);
      if (kmem[cpu_id].freelist == 0)
        kmem[cpu_id].freelist = r->next;
      else {
        // special case: current freelist become not empty
        add2tail(kmem[cpu_id].freelist, r);
        r = kmem[cpu_id].freelist;
        kmem[cpu_id].freelist = r->next;
      }
      release(&kmem[cpu_id].lock); 
    }
  }

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

  pop_off();
  return (void*)r;
}

bcache

如果多个进程密集地使用文件系统，它们很可能竞争使用 bcache.loc 这个保护磁盘 block cache 的锁。这一部分实验的任务是修改 block cache 使得在 bcachetest 程序测试下，竞争 bcache 中的锁的次数尽可能小。修改 bget 与 brelse 函数使得查询和释放 bcache 中不同的 block 时减少用锁的冲突。p.s 就是不需要全部等待 bcache.lock 。同时，必须保证每个 block 最多只被缓存一次（为了这点需要保留bcache级别的锁，和前一个实验不同）。

hash bucket

减少 block cache 中的争用比 kalloc 更棘手，因为 bcache cache 是真正在进程(以及cpu)之间共享的。对于 kalloc，可以通过为每个CPU分配自己的 allocator 来消除大部分争用；这对块缓存不起作用。我们可以使用哈希表，每个哈希桶 bucket 有一个锁，以此来查找缓存中的 block 。可以使用固定数量的 bucket ，而不动态地调整哈希表的大小。使用素数桶(例如13)来减少散列冲突的可能性。

#define NBUCKET 13
#define BIO_HASH(x) (x % NBUCKET)

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

  // Linked lists of each bucket buffers, through prev/next.
  // Sorted by how recently the buffer was used.
  // head.next is most recent, head.prev is least.
  struct buf buc_head[NBUCKET];

  struct spinlock buc_locks[NBUCKET];
} bcache;

实验建议使用时间戳来指示上一次使用，即使用 kernel/trap.c 中的 ticks 变量。如此，brelse 函数不需要获取 bcache lock 而 bget 通过时间戳来选择 LRU empty block 以完成驱逐与重新缓存。向结构体 buf 添加时间戳字段记录上次 access 情况。

// in kernel/buf.h
struct buf {
  int valid;   // has data been read from disk?
  int disk;    // does disk "own" buf?
  uint dev;
  uint blockno;
  struct sleeplock lock;
  uint refcnt;
  struct buf *prev; // LRU cache list
  struct buf *next;

  uint64 lasttick; // last access
  uchar data[BSIZE];
};

修改的 brelse 就只用持有 bucket 级别的锁，且不用像之前的 LRU 双链表结构一样将引用计数为 0 的 buf 进行移动。p.s. 我为了后续的 stealing 方便，还是保留了双链表的结构。

// Release a locked buffer.
// Move to the head of the most-recently-used list.
void
brelse(struct buf *b)
{
  int id;

  if(!holdingsleep(&b->lock))
    panic("brelse");

  releasesleep(&b->lock);

  id = BIO_HASH(b->blockno);

  acquire(&bcache.buc_locks[id]);
  b->refcnt--;
  if (b->refcnt == 0) {
    // no one is waiting for it.
    b->lasttick = ticks;
  }
  
  release(&bcache.buc_locks[id]);
}

eviction

在修改 bget 时必须考虑到，如果一个目标 block 未缓存，需要将 unused buf 拿来使用。这个过程伴随将其 bucket 满了，可能需要从其他 bucket 取 unused buf。类似 kmem 里的窃取流程，为避免死锁不能同时持有两个 bucket 锁。除此之外，还需注意”必须保证每个 block 最多只被缓存一次”。试想，两个执行流并发地为同一个 block 进行 evicition ，如果没有一个全局的锁控制，之后会有两个 blockno 相同的 buf 存在。这比 kmem 的情况要复杂一些。因为 kmem 的 freelist 并不在乎空闲页面的数据存在相等的可能（无必要）。

封装了双链表的删除与插入操作，以便窃取。

static void 
removeFrom(struct buf* b) {
  b->next->prev = b->prev;
  b->prev->next = b->next;
}

static void 
insertTo(struct buf* b, int bucketID) {
  b->next = bcache.buc_head[bucketID].next;
  b->prev = &bcache.buc_head[bucketID];
  bcache.buc_head[bucketID].next->prev = b;
  bcache.buc_head[bucketID].next = b;
}

修改后的 bget 代码如下，

// 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)
{
  int i, id, oldInd;
  uint lastvisit;
  struct buf *b;
  struct buf *pick;

  id = BIO_HASH(blockno);

  acquire(&bcache.buc_locks[id]);

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

  release(&bcache.buc_locks[id]);

  // eviction
  acquire(&bcache.lock);
  acquire(&bcache.buc_locks[id]);
  
  // must search again. There might be an eviction after last search.
  for(b = bcache.buc_head[id].next; b != &bcache.buc_head[id]; b = b->next){
    if(b->dev == dev && b->blockno == blockno){
      b->refcnt++;
      release(&bcache.buc_locks[id]);
      release(&bcache.lock);
      acquiresleep(&b->lock);
      return b;
    }
  }

  release(&bcache.buc_locks[id]);

  lastvisit = 0xffffffff;
  pick = 0;
  oldInd = -1;
  // Not cached.
  // Recycle the least recently used (LRU) unused buffer by time stamp
  for (i = 0; i < NBUCKET; i++) {
    acquire(&bcache.buc_locks[i]);
    
    // find lru unused buf in this bucket
    struct buf* curPick = 0;
    for (b = bcache.buc_head[i].next; b != &bcache.buc_head[i]; b = b->next) {
      if (b->refcnt == 0 && b->lasttick <= lastvisit) {
        lastvisit = b->lasttick;
        curPick = b;
      }
    }

    if(curPick) {

      if (pick) {
        
        removeFrom(curPick);
        release(&bcache.buc_locks[i]);

        // ensure most two locks acquired
        // restore
        acquire(&bcache.buc_locks[oldInd]);
        insertTo(pick, oldInd);
        release(&bcache.buc_locks[oldInd]);

        pick = curPick;
        oldInd = i;

      } else {
        removeFrom(curPick);
        release(&bcache.buc_locks[i]);

        pick = curPick;
        oldInd = i;
      }
    } else {
      release(&bcache.buc_locks[i]);
    }
    
  }
  
  if (pick) {
    pick->dev = dev;
    pick->blockno = blockno;
    pick->valid = 0;
    pick->refcnt = 1;

    // insert to 
    acquire(&bcache.buc_locks[id]);
    insertTo(pick, id);
    release(&bcache.buc_locks[id]);

    release(&bcache.lock);
    acquiresleep(&pick->lock);
    return pick;
  }


  release(&bcache.lock);

  panic("bget: no buffers");
}

其主要流程为，

  1. 持有当前哈希桶的锁情况下，搜索桶内是否有缓存。
  2. 持有全局锁 bcache.lock 情况下，
    • 持有当前哈希桶的锁，再次搜索桶内。这一步必要，因为其他线程可能完成一次 eviction
    • 持有不同哈希桶的锁，在各个桶内搜索 LRU empty buf，并将选中的 buf 从原桶中删除。
    • 如果更换 pick buf 则需要将之前选中的 buf 还原到原桶中。我用 oldInd 记录原哈希桶。
    • 如果有符合条件的 pick buf，改写其元信息，将其插入 blockno 的哈希桶内。

这样的设计保证多进程在

  • 使用同一个 blockno buf 时
  • 因为没有命中缓存，执行 eviction 代码，寻找 unused block 以代替时，
  • 使用同一个哈希桶时，

的并发正确性。

Conclusion

细粒度的锁可以减少锁的争用，提高性能。但实现需要小心避免死锁与资源泄漏。在本次实验的场景下，我通过保证加锁顺序，破坏循环等待条件，任何执行流不可能同时持有一个以上的同一级的细粒度锁，因此内核代码可以避免死锁。

但除了死锁以外，资源泄漏（还有其他资源被浪费的现象）也是可能发生的。在多线程的模型下，

  • 如果持有锁 L2 ，之前在同一级锁 L1 的临界区内得出的结论，此时并不一定成立。因为机器可能在此线程出 L1 临界区后，调度其他线程又进入锁 L1 的临界区。这也是为什么在 kalloc 与 bget 代码中有重复检查的代码。
  • 如果有窃取流程，被窃取的资源在离开锁 L1 保护的数据结构后，未加入锁 L2 保护的数据结构前。其”保护者” 并不存在。这个 剥夺-插入 的流程一定要符合数据结构的 invariant，以避免资源泄漏。是否要在细粒度锁之上加一个高级别的 eviction lock 则要视情况而定。如果 eviction 不允许多个执行流同时执行，例如多个进程为同一个 blockno 并行 eviction 会导致多个buf的 blockno 相同（这是资源浪费，也可看作某种泄漏），那么就需要一个 eviction lock 原子化 eviction 流程。

正如第十课讨论的，

死锁的危险通常限制了锁的粒度，因为细粒度锁带来更复杂的代码，更多死锁与资源泄漏的危险。锁的粒度决策需要由性能度量和复杂性考虑来驱动。everything is trade-off.

Reference

  1. 6.S081
  2. perf-lock mannual
  3. 第十课

Table of Contents