search

zoniony / zoniony.github.io

blog
1 stars 0 forks source link

6.S081 lab3 Allocator for xv6 #6

Open zoniony opened 4 years ago

zoniony commented 4 years ago

我太菜了

lab3

ODQn1p

Lab: Allocator for xv6

File Buddy

file.c没什么说的，用bd_malloc动态分配struct file替换struct file file[NFILE];静态分配来突破NFILE数量的限制。记得fileclose的时候bd_free掉

buddy.c修改的代码量很少，主要是要看懂它怎么实现。重点在bd_init函数

先理解buddy system

伙伴系统即Buddy System，是一种简单高效的内存分配策略。其主要思想是将大块内存按照一定策略去不断拆分（在到达最小的块之前），直至存在满足指定请求大小的最小块。其中块的大小由其相对根块的位置指定，通常称为order(阶)。一个最简单的拆分方式就是以2为指数进行拆分，例如定义最小块的大小为64K，order上限为4，则最大块的大小为：

*64K 2^4 = 1024K**

最大块的order为4，最小块的order为0。对于请求大小为k的块，最小块为N，则其order值为align(k)/N。为什么叫buddy system呢？假设一个大块A所分解成的两个小块B和C，其中B和C就相互为彼此的 天使 buddy。只有彼此的buddy才能够进行合并。

使用Buddy算法的的应用有很多，其中Linux内核就是一个，此外jemalloc也是使用Buddy技术的一个现代内存分配器。

维基百科中有一个很直观的例子：Buddy memory allocation。Linux内核中的伙伴系统块大小为一页，通常是4096字节。最大的order一般是10，即MAX_ORDER为11。

先给meta date分配内存,也就是struct sz_info结构体

struct sz_info {
  Bd_list free;
  char *alloc;
  char *split;
};

Bd_list free双向链表管理需要分配的每块内存

chra *alloc 标记是否分配的tag

char *split 标记对应是否分裂

 // compute the number of sizes we need to manage [base, end)
  nsizes = log2(((char *)end-p)/LEAF_SIZE) + 1;
  if((char*)end-p > BLK_SIZE(MAXSIZE)) {
    nsizes++;  // round up to the next power of 2
  }

  printf("bd: memory sz is %d bytes; allocate an size array of length %d\n",
         (char*) end - p, nsizes);

  // allocate bd_sizes array
  bd_sizes = (Sz_info *) p;
  p += sizeof(Sz_info) * nsizes;
  memset(bd_sizes, 0, sizeof(Sz_info) * nsizes);

  // initialize free list and allocate the alloc array for each size k
  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;
  }

  // allocate the split array for each size k, except for k = 0, since
  // we will not split blocks of size k = 0, the smallest size.
  for (int k = 1; k < nsizes; k++) {
    sz = sizeof(char)* (ROUNDUP(NBLK(k), 8))/8;
    bd_sizes[k].split = p;
    memset(bd_sizes[k].split, 0, sz);
    p += sz;
  }
  p = (char *) ROUNDUP((uint64) p, LEAF_SIZE);

内存分部大概如下

+---------------------------------+0x8002a000
|        bd_sizes[nsizes]         |
+---------------------------------+0x8002a300
|                                 |
|                                 |
|                                 |
|                                 |
|                                 |
|                                 |
|                                 |
|           alloc                 |
|                                 |
|                                 |
|                                 |
|                                 |
|                                 |
|                                 |
|                                 |
+---------------------------------+0x8022a302
|                                 |
|                                 |
|                                 |
|                                 |
|          split                  |
|                                 |
|                                 |
|                                 |
|                                 |
+---------------------------------+0x8032a304
|                                 |
|                                 |
|                                 |
|                                 |
|                                 |
|                                 |
|                                 |
|                                 |
|                                 |
|                                 |
|                                 |
|                                 |
|                                 |
|                                 |
|                                 |
|                                 |
+---------------------------------+

其中alloc1byte能表示0x10*8的内存地址，1bit代表0x10

其中bit_xxx操作就是通过位运算来实现的.

一段0x80的内存已经被分配那么bit为11111111，也就是f

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

// Set bit at position index in array to 1
void bit_set(char *array, int index) {
  char b = array[index/8];
  char m = (1 << (index % 8));
  array[index/8] = (b | m);
}

// Clear bit at position index in array
void bit_clear(char *array, int index) {
  char b = array[index/8];
  char m = (1 << (index % 8));
  array[index/8] = (b & ~m);
}

而mate date肯定不能再进行分配,所以进行标记

  // 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);
//........
  // initialize free lists for each size k
  int free = bd_initfree(p, bd_end);

而且在0x8032a310和最后的位置位置相邻的位置就是mate date肯定不能当buddy进行分裂，所以提前把这两个地址放入list里面

// Initialize the free lists for each size k.  For each size k, there
// are only two pairs that may have a buddy that should be on free list:
// bd_left and bd_right.
int
bd_initfree(void *bd_left, void *bd_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, 1);
    if(right <= left)
      continue;
    free += bd_initfree_pair(k, right, 0);
  }
  return free;
}

找每个不同大小块的位置是通过和bd_base位置距离进行判断

// Compute the block index for address p at size k
int
blk_index(int k, char *p) {
  int n = p - (char *) bd_base;
  return n / BLK_SIZE(k);
}
// Compute the first block at size k that doesn't contain p
int
blk_index_next(int k, char *p) {
  int n = (p - (char *) bd_base) / BLK_SIZE(k);
  if((p - (char*) bd_base) % BLK_SIZE(k) != 0)
      n++;
  return n ;
}

改动

这里可以发现alloc占了内存0x20000

0x20000 * 8 = 0x1000000

似乎大小刚好管理分配的内存

但是这里可以优化。

可以省10000h的空间,sz = sizeof(char)* ROUNDUP(NBLK(k), 8)/8;缩小成sz = sizeof(char)* ROUNDUP(NBLK(k), 16)/16;

  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，空间缩小了一半

通过在free或者malloc的时候只需要判断它的buddy是否分配。粗暴点的方法就是每一bit代表一块，只需要用bit_isset判断是否被标记就行了。

但是更简便的方式是将这一对buddy看成一块，只需要用异或判断对应buddy的状态就可以知道是否被占用。

这里最代表的是if(bit_get(bd_sizes[k].alloc, bi))就能判断buddy是否被分配

// If a block is marked as allocated and the buddy is free, put the
// buddy on the free list at size k.
int
bd_initfree_pair(int k, int bi) {
  int buddy = (bi % 2 == 0) ? bi+1 : bi-1;
  int free = 0;
  if(bit_get(bd_sizes[k].alloc, bi)) {
    // one of the pair is free
    free = BLK_SIZE(k);
    if(bit_isset(bd_sizes[k].alloc, bi))
      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
  }
  return free;
}

所以这里优化通过异或来代表一对buddy来缩小空间。以达到可以分配更多的内存

int bit_get(char *array, int index) {

  index >>= 1;
  char b = array[index/8];
  char m = (1 << (index % 8));
  return (b & m) == m;
}

bd_malloc和bd_free还是很容易修改，重点还是在bd_init去处理边界的时候需要额外判断处理

具体看源码= =