任务五 实现伙伴系统

任务设计

•采用什么样的数据结构？    实现伙伴系统需要采用树的结构用于节点的选择行为同时采用线性表的结构用于内存空间的存储，从而才有实现合并的可能，由于伙伴系统独特的二分性质，我们可以考虑采用线性表来保存树，这样我们就可以使得两个数据结构合并为线性表。参考ff_malloc的实现方法，由于我们采用线性表保存树，可以不再需要next指针，next指针指向当前的伙伴系统头。

定义伙伴系统头：
union buddy_header{
    struct Buddy_header
    {
        union buddy_header *next;
        unsigned size;
        unsigned upper_available;
    };


    union header reserve[2];
};

•为了更快的查询某一区块大小的可用节点是否存在，我们可以再开设一个数组，available[i]表示大小为2^i^的区块当前可用数量，并限制分配的最小单位是1个区块。•空间不足时的处理？    空间不足时，可以新建一个新的伙伴系统，但这要求我们需要有一个伙伴系统的管理系统，我们可以将多个伙伴系统的指针用链表连接起来，并保存各个伙伴系统的关键信息（起点位置、伙伴系统总大小、最小available和最大available）。各个伙伴系统的分配可以结合之前的ff_malloc或者wf_malloc实现。•如何进行空间划分？    伙伴系统将首先去适配不需要划分的叶子节点，没有这样的节点时，再去寻找最接近它大小的叶子节点，然后进行叶子节点分裂，并不断维护available数组以及当前伙伴系统的信息。•如何判断伙伴系统应该进行合并，何时合并？    伙伴系统要进行合并应该根据它当前的位置及大小，推算出它应该去合并的兄弟节点位置，这是比较容易计算的，具体为，如果伙伴节点的位置是合并后大小的倍数，则兄弟节点位于更高地址，反之，兄弟节点位于较低位置，合并后，修改相关header和available数组内容。

综上，大概要实现这样一个多伙伴系统：

逻辑框图

各个功能实现

•buddy_malloc函数

// 使用buddy_system分配空间入口,与逻辑图相同
void *buddy_malloc(int size){
    unsigned true_size = compute_true_size(size, BLOCK);
    union buddy_header *use_buddy = check(true_size);
    unsigned malloc_size = (1 << true_size * 2) + 2;
    if(malloc_size < NALLOC) malloc_size = NALLOC + 2;
    if(!use_buddy) use_buddy = (union buddy_header *) create_a_buddy_sys(malloc_size);
    union ff_header *block = find_element(use_buddy, true_size);
    printf("alloc %d size\n" ,block -> meta.len);
    block -> meta.using = 1;
    available_drop(block -> meta.len);
    print();
    return (void*)(block + 1);
}

•buddy_free函数

// 回收伙伴系统空间，并归并，详见逻辑框图，如果根节点都没有使用，调用ff_malloc的free方法回收空间
void buddy_free(void *ptr){
    union ff_header* block = (union ff_header*)ptr - 1;
    block -> meta.using = 0;
    available_add(block -> meta.len);
    union buddy_header* bptr = buddy_list;
    printf("free block size %d\n", block -> meta.len);
    //定位所在的伙伴系统
    while(bptr && !((union ff_header *)bptr < ptr && (union ff_header*)bptr + bptr -> buddy.size + 2 > ptr)) bptr = bptr -> buddy.next;
    if(!bptr) return;
    union ff_header *st = (union ff_header*) bptr + 2;
    while(1){
        int offset = block - st;
        if(offset % (2 * block -> meta.len)){
            block -= block -> meta.len;
        }
        if(!merge(block)) break;
    }
    printf("block size: %d, buddy size: %d\n", block -> meta.len, bptr -> buddy.size);
    // 销毁空间未使用的伙伴系统
    if(block -> meta.len == bptr -> buddy.size) {
      union buddy_header* pre = buddy_list;
      if(pre -> buddy.next) {while(pre -> buddy.next != bptr) pre = pre -> buddy.next;
      pre -> buddy.next = bptr -> buddy.next;}
      else buddy_list = NULL;
      free((void*)bptr);
    }
}

其他具体功能实现函数

•创建一个伙伴系统

// 创建一个大小为size(包含头部)的伙伴系统
void *create_a_buddy_sys(unsigned size){
    printf("create_a_buddy_sys size %d\n", size);
    union buddy_header *p = (union buddy_header *) ff_malloc(size * sizeof(union ff_header));
    p -> buddy.upper_available = size - 2;
    p -> buddy.size = size - 2;
    union ff_header *ptr = (union ff_header *)(p + 1);
    ptr -> meta.len = size - 2;
    // 将新伙伴系统前插
    p -> buddy.next = buddy_list;
    buddy_list = p;
    // 维护available数组
    available_add(size - 2);
    print();
    return p;
}

•匹配当前存在的伙伴系统，未找到返回NULL

// check true_size 需要的空间能否匹配到存在的伙伴系统
void *check(unsigned true_size){
    int st = multiples_2(true_size);
    for(;st < 32; st ++){
        if(available[st]) break;
    }
    // 没有大于2的st次方的可用块(即没有可用的伙伴系统)
    if(st == 32) return NULL;
    union buddy_header *p = buddy_list;
    // 判断各个伙伴系统能分配的最大空间和我们需求的关系
    while(p && p -> buddy.upper_available < (1 << st)) p = p -> buddy.next;
    return p;
}

•分裂节点，并维护资源

// 将p节点，分裂为两个节点，并维护相关头部和available数组
void *divide(union buddy_header *b, union ff_header *p, int true_size){
    printf("divide size %d block\n", p -> meta.len);
    int flag = 1;
    while(p -> meta.len != true_size){
        if(flag && b -> buddy.upper_available == p -> meta.len){
            b -> buddy.upper_available /= 2;
            flag = 0;
        }
        available_drop(p -> meta.len);
        p -> meta.len /= 2;
        (p + p -> meta.len) -> meta.len = p -> meta.len;
        available_add(p -> meta.len);
        available_add(p -> meta.len);
    }
    return p;
}

•寻找正确的放置位置，遵循最小区块优先

// 寻找大小为true_size应该放置的位置
void *find_element(union buddy_header *buddy, unsigned true_size){
    true_size = 1 << multiples_2(true_size);
    union ff_header *p = (union ff_header*)buddy + 2;
    int minn = 0x3f3f3f3f;
    union ff_header *pick;
    while(p - (union ff_header*)buddy <= buddy -> buddy.size + 2)
    {
        // 寻找区块中最小的、大于需求的、未被使用的可用block
        if(p -> meta.len < minn && p -> meta.len >= true_size && !p -> meta.using){
            minn = p -> meta.len;
            pick = p;
        }
        p += true_size;
    }
    return divide(buddy, pick, true_size);
}

•将指定节点与右侧兄弟节点合并

// 将block节点和其右边的节点尝试合并，并维护available数组
int merge(union ff_header* block){
    union ff_header* another = block + block -> meta.len;
    if(block -> meta.using || another -> meta.using) return 0;
    if(block -> meta.len != another -> meta.len) return 0;
    printf("merge size %d\n", block -> meta.len);
    available_drop(block -> meta.len);
    available_drop(block -> meta.len);
    block -> meta.len *= 2;
    available_add(block -> meta.len);
    another -> meta.len = 0;
    print();
    return 1;
}

•工具函数

// 获取应该为size分配2的多少次方的节点
int multiples_2(int size){
    size --;
    int count = 0;
    while(size){
        count ++;
        size = size >> 1;
    }
    return count;
}


// size大小的节点可用数加1
void available_add(int size){
    available[multiples_2(size)] ++;
}


// size大小节点可用数减1
void available_drop(int size){
    available[multiples_2(size)] --;
}


// 比特大小换算为区块大小
int compute_true_size(int size, int mode)
{
    if(mode == BUDDY) return (size + sizeof(union ff_header) * 2 - 1) / sizeof(union ff_header) + 1;
    if(mode == BLOCK) return (size + sizeof(union ff_header) - 1) / sizeof(union ff_header) + 1;
    if(mode == TRUE_SIZE) return (size - 1) / sizeof(union ff_header) + 1;
}


// 调试使用，打印available数组
void print(void)
{
  int i = 0;
  while( i < 32)
  {
    printf("%d ", available[i]);
    i ++;
  }
  printf("\n");
}

整体测试

同样使用test.c进行测试，并打印出available数组。（输出有1072行，只进行部分展示）

获取空间：

create_a_buddy_sys size 1026 # 创建了一个1026大小的伙伴系统
ff_malloc: alloc size 514 at loop 1 size 1024
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 # 创建后 对应2的10次方空间就可用了
divide size 1024 block
alloc 2 size
0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
# 分配了一个 2区块大小出去，现存2的2、3、4、5、6、7、8、9次方可用各1个
divide size 2 block
alloc 2 size
0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 # 后面都成功分配了
divide size 4 block
alloc 4 size
0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
divide size 8 block
alloc 4 size
0 0 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
divide size 4 block
alloc 4 size
0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
divide size 16 block
alloc 4 size
0 0 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
divide size 8 block
alloc 8 size
0 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

释放空间：

free block size 32
merge size 32
0 0 0 0 0 1 2 1 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
merge size 64
0 0 0 0 0 1 0 2 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
merge size 128
0 0 0 0 0 1 0 0 1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
block size: 256, buddy size: 1024
free block size 32
block size: 32, buddy size: 1024
free block size 32
merge size 32
0 0 0 0 0 1 1 0 1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
block size: 64, buddy size: 1024
free block size 32
block size: 32, buddy size: 1024
free block size 32
merge size 32
0 0 0 0 0 1 2 0 1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
merge size 64
0 0 0 0 0 1 0 1 1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
block size: 128, buddy size: 1024
free block size 32
block size: 32, buddy size: 1024
free block size 32
merge size 32
0 0 0 0 0 1 1 1 1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
block size: 64, buddy size: 1024
free block size 32
merge size 32
0 0 0 0 0 0 2 1 1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
merge size 64
0 0 0 0 0 0 0 2 1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
merge size 128
0 0 0 0 0 0 0 0 2 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
merge size 256
0 0 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
merge size 512
0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
block size: 1024, buddy size: 1024 # 最后空间完全回收，伙伴系统被释放

经过测试，伙伴系统工作正常。