MIT 6.S081/Fall 2019实验 Lab: Allocator for xv6，用好友分配器替换 xv6 内核中的页面分配器，修改分配和释放文件方法，使用buddy allocator进行动态地分配和释放；同时，实现一个优化，减少buddy allocator对内存的使用。

本文对主要思路和关键部分的代码实现进行说明，完整代码实现可以参考我的GitHub仓库.

1. 使用buddy allocator

修改file.c文件，删去ftable结构体中file[NFILE]的声明：

struct {
  struct spinlock lock;
} ftable;

在filealloc中使用bd_malloc进行动态申请，同时每次申请之后对f进行初始化：

struct file*
filealloc(void)
{
  acquire(&ftable.lock);
  struct file *f  = bd_malloc(sizeof(struct file));
  if (f) {
    memset(f, 0, sizeof(struct file));
    f->ref = 1;
    release(&ftable.lock);
    return f;
  }
  release(&ftable.lock);
  return 0;
}

之后对fileclose进行修改，使用对应的bd_free进行释放，需要使用acquire对f->ref进行保护：

void
fileclose(struct file *f)
{
  struct file ff;

  acquire(&ftable.lock);
  if(f->ref < 1)
    panic("fileclose");
  if(--f->ref > 0){
    release(&ftable.lock);
    return;
  }
  ff = *f;
  f->ref = 0;
  f->type = FD_NONE;
  release(&ftable.lock);

  if(ff.type == FD_PIPE){
    pipeclose(ff.pipe, ff.writable);
  } else if(ff.type == FD_INODE || ff.type == FD_DEVICE){
    begin_op(ff.ip->dev);
    iput(ff.ip);
    end_op(ff.ip->dev);
  }

  bd_free(f);
}

2. 优化伙伴系统算法

首先修改bd_init函数，减半分配给struct sz_info的空间：

for (int k = 0; k < nsizes; k++) {
    lst_init(&bd_sizes[k].free);
    sz = sizeof(char)* ROUNDUP(NBLK(k), 16)/16;
    bd_sizes[k].alloc = p;
    memset(bd_sizes[k].alloc, 0, sz);
    p += sz;
  }

Buddy alloctor管理内存时会在内存区域头部存放metadata，所以有部分的空间是不可用的（unavailable），通过以下代码可知：

// done allocating; mark the memory range [base, p) as allocated, so
  // that buddy will not hand out that memory.
  int meta = bd_mark_data_structures(p);
  
  // mark the unavailable memory range [end, HEAP_SIZE) as allocated,
  // so that buddy will not hand out that memory.
  int unavailable = bd_mark_unavailable(end, p);
  void *bd_end = bd_base+BLK_SIZE(MAXSIZE)-unavailable;

所以可用的available space为[p, end]，之后在初始化每层的buddy时，需要考虑边界范围。之后通过函数bd_initfree对每层进行初始化，修改函数bd_initfree。

在函数入口增加左右边界min_left，max_right，对应可用空间[p, end]。

int free = bd_initfree(p, bd_end, p, end);

函数bd_initfree中，通过调用bd_initfree_pair分别对内存块和它的buddy进行初始化，所以初始化的操作在bd_initfree_pair中进行，对应修改bd_initfree_pair的函数入口，增加min_left和max_right。

int
bd_initfree(void *bd_left, void *bd_right, void *min_left, void *max_right) {
  int free = 0;

  for (int k = 0; k < MAXSIZE; k++) {   // skip max size
    int left = blk_index_next(k, bd_left);
    int right = blk_index(k, bd_right);
    free += bd_initfree_pair(k, left, min_left, max_right);
    if(right <= left)
      continue;
    free += bd_initfree_pair(k, right, min_left, max_right);
  }
  return free;
}

bd_initfree_pair函数通过判断传入的内存块是否已经allocted，以及它的buddy是否空闲来判断是将buddy放入free list还是该内存块放入free list。因为使用一个bit来同时记录一对buddy的alloc情况，所以需要修改判断函数bit_isset，新的函数命名为new_bit_isset，因为分配给alloc的空间减半，故其中将index除以2。

void new_bit_set(char *array, int index) {
  index /= 2;
  char m = (1 << (index % 8));
  array[index/8] ^= m;
}

若该内存块已经allocted，则判断buddy是否为free，方法为判断buddy的地址是否在可用空间内，即[min_left, max_right)。如果在可用空间之内，则将buddy加入free list，否则将该内存块加入free list。

if(new_bit_isset(bd_sizes[k].alloc, bi)) {
    // one of the pair is free
	free = BLK_SIZE(k);
    if(addr(k, buddy) >= min_left && addr(k, buddy) < max_right)
      lst_push(&bd_sizes[k].free, addr(k, buddy));   // put buddy on free list
    else
      lst_push(&bd_sizes[k].free, addr(k, bi));      // put bi on free list
}

接着修改bd_malloc函数，将其中对alloc的set操作换为new_bit_set，通过异或操作，只用一个bit位来记录一对buddy的alloc情况，其中注意需要将index除以2。

int new_bit_isset(char *array, int index) {
  index /= 2;
  char b = array[index/8];
  char m = (1 << (index % 8));
  return (b & m) == m;
}

修改bd_malloc函数时，需要注意set split的函数仍然需要使用原来的set函数，只有对alloc的set函数需要进行替换。

void * bd_malloc(uint64 nbytes)
{
  int fk, k;

  acquire(&lock);

  // Find a free block >= nbytes, starting with smallest k possible
  fk = firstk(nbytes);
  for (k = fk; k < nsizes; k++) {
    if(!lst_empty(&bd_sizes[k].free))
      break;
  }
  if(k >= nsizes) { // No free blocks?
    release(&lock);
    return 0;
  }

  // Found a block; pop it and potentially split it.
  char *p = lst_pop(&bd_sizes[k].free);
  new_bit_set(bd_sizes[k].alloc, blk_index(k, p));
  for(; k > fk; k--) {
    // split a block at size k and mark one half allocated at size k-1
    // and put the buddy on the free list at size k-1
    char *q = p + BLK_SIZE(k-1);   // p's buddy
    bit_set(bd_sizes[k].split, blk_index(k, p));
    new_bit_set(bd_sizes[k-1].alloc, blk_index(k-1, p));
    lst_push(&bd_sizes[k-1].free, q);
  }
  release(&lock);

  return p;
}

对应的，修改bd_mark函数中对alloc声明部分的函数为new_bit_set，对split的声明部分不变：

void bd_mark(void *start, void *stop) {
  int bi, bj;

  if (((uint64) start % LEAF_SIZE != 0) || ((uint64) stop % LEAF_SIZE != 0))
    panic("bd_mark");

  for (int k = 0; k < nsizes; k++) {
    bi = blk_index(k, start);
    bj = blk_index_next(k, stop);
    for(; bi < bj; bi++) {
      if(k > 0) {
        // if a block is allocated at size k, mark it as split too.
        bit_set(bd_sizes[k].split, bi);
      }
      new_bit_set(bd_sizes[k].alloc, bi);
    }
  }
}

最后，修改bd_free函数，其中判断函数修改为new_bit_isset，对buddy的alloc函数更换为new_bit_set：

void bd_free(void *p) {
  void *q;
  int k;

  acquire(&lock);
  for (k = size(p); k < MAXSIZE; k++) {
    int bi = blk_index(k, p);
    int buddy = (bi % 2 == 0) ? bi+1 : bi-1;
    new_bit_set(bd_sizes[k].alloc, bi); // free p at size k
    if (new_bit_isset(bd_sizes[k].alloc, buddy)) {  // is buddy allocated?
      break;   // break out of loop
    }
    // budy is free; merge with buddy
    q = addr(k, buddy);
    lst_remove(q);    // remove buddy from free list
    if(buddy % 2 == 0) {
      p = q;
    }
    // at size k+1, mark that the merged buddy pair isn't split
    // anymore
    bit_clear(bd_sizes[k+1].split, blk_index(k+1, p));
  }
  lst_push(&bd_sizes[k].free, p);
  release(&lock);
}

本实验主要通过使用动态声明buddy alloctor来优化xv6的文件系统。其中动态声明解决静态声明文件的大小限制，不用受限于file文件的结构体数目。同时，优化buddy alloctor，使用一个bit位来同时记录一对buddy的alloc情况，节省内存空间。

实验过程中最主要的困难在于理解buddy alloctor的分配和释放逻辑，需要知道整个流程以及流程中的函数调用，需要看懂每个函数中每行代码的作用。之后需要修改其中关于alloc的部分，减少分配空间，重写set函数。