malloc从原理到实践

简介

使用过c语言的都知道malloc是一个动态分配内存的函数
malloc的全称是memory allocation，中文叫动态内存分配，用于申请一块连续的指定大小的内存块区域以void*类型返回分配的内存区域地址

malloc分配的内存大小至少为size参数所指定的字节数
malloc的返回值是一个指针，指向一段可用内存的起始地址

使用示例

char *ptr = (char *)malloc(10);  //分配10个字节的内存空间，用来存放字符

数据结构

arena
- mem_block_desc-内存块描述符指针
  - block_size，规格
  - block_per_arena，容量
  - free_list
- 由free_list指向的内存块数组（内存池区域）

arena结构.png

arena是个提供内存分配的数据结构，它分为两部分，一部分是元信息，用来描述自己内存池中空闲内存块的数量，这其中包括内存块描述符指针，通过它可以间接获知本arena所包含内存块的规格大小，此部分占用的内存空间是固定的，约为12字节。另一部分就是内存池区域，这里面有无数的内存块，此部分占用arena大量的空间。我们把每个内存块命名为mem_block，他们是内存分配粒度更细的资源。

内存块描述符代表内存分配的规则，从16字节，到32，64，，，1024字节共7种规格。结构上的区别就是block_size不同，free_list中指向的内存块规则不同。

malloc函数实际上就是通过arena申请这些内存块。arena是个内存仓库，并不直接对外提供内存分配，只有内存块描述符才对外提供内存块，内存块描述符将同类的空闲内存块汇聚到一起，作为某一规格内存块的分配入口。因此，内存块描述符与arena是一对多的关系，每个arena都要与唯一的内存块描述符关联起来，多个同一规格的arena为同一规格的内存块描述符供应内存块，他们各自元信息中用内存块描述符指针指向同一个内存块描述符。

arena.png

结构定义

memory.h

/*内存块*/
struct mem_block{
    struct list_elem free_elem;
}
/*内存块描述符*/
struct mem_block_desc{
    //内存块大小
    unit32_t block_size;
    //本arena中容纳此mem_block的数量
    unit32_t block_per_arena;
    //目前可用的mem_block链表
    struct list free_list;
}

#define DESC_CNT 7

memory.c

struc arena{
    //此arena关联的mem_block_desc
    struct mem_block_desc* desc;
    //large为true时，cnt表示的是页框数量。否则cnt表示空闲mem_block数量
    unit32_t cnt;
    bool large;
}


//内核内存块描述符数组
struct mem_block_desc k_block_desc[DESC_CNT];
//生成内核内存池和用户内存池
struct pool kernel_pool,user_pool;
//此结构用来给内核分配虚拟地址
struct virtual_addr kernal_vaddr;
/*为malloc做准备*/
void block_desc_init(struct mem_block_desc* desc_array){
    uint16_t desc_idx, block_size = 16;
    //初始化每个mem_block_desc描述符
    for(desc_idx = 0; desc_idx < DESC_CNT; desc_idx++){
        desc_array[desc_idx].block_size = block_size;
        //减去arena大小再向下整除
        desc_array[desc_idx].block_per_arena = (PG_SIZE - sizeof(struct arena)) / block_size;
        list_init(&desc_array[desc_idx].free_list);
        block_size * = 2;
    }
}

void mem_init(){
    put_str("mem_init start\n");
    unit32_t mem_byte_total = (*(unit32_t*)(0xb00));
    //初始化内存池
    mem_pool_init(mem_byte_total);
    //初始化mem_block_desc数组，为malloc做准备
    block_desc_init(k_block_desc);
    put_str("mem_init done\n");

}

PG_SIZE = 4KB 4096

sys_malloc的功能是分配并维护内存资源，动态创建arena以满足对内存块的分配

代码实现