malloc 是 C 标准库中用于动态内存分配的函数。

我们已经实现了内存管理，但是分配的内存都是以4KB大小的页框为单位的，为此必须实现一种小内存块的管理，可以满足任意内存大小的分配。

arena是个提供内存分配的数据结构，它分为两部分：

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

为了跟踪每个arena中的空闲内存块，分别为每一种规格的内存块建立一个内存块描述符，即 mem_block_desc，在其中记录内存块规格大小，以及位于所有同类arena中的空闲内存块链表。

内存块描述符将所有同类arena中空闲内存块汇总，分配小块内存时必须先经过此入口，系统从它的空闲内存块链表free_list中挑选一块内存。

我们这里的内存块以16字节为起始，向上依次是32字节、64字节、128字节、256字节、512字节、1024字节，总共7种规格，因此，内存块描述符也就这7种。

最大内存块容量不会超过1024字节，如果申请的内存量较大，超过1024字节，处理大内存请求时也会创建个arena，但不会再将它拆分成小内存块，而是直接将整块大内存分配出去。

在内存管理系统中，arena为任意大小内存的分配提供了统一的接口，它既支持1024字节以下的小块内存的分配，又支持大于1024字节以上的大块内存，malloc函数实际上就是通过arena申请这些内存块。arena是个内存仓库，并不直接对外提供内存分配，只有内存块描述符才对外提供内存块，内存块描述符将同类arena中的空闲内存块汇聚到一起，作为某一规格内存块的分配入口。因此，内存块描述符与arena是一对多的关系，每个arena都要与唯一的内存块描述符关联起来，多个同一规格的arena为同一规格的内存块描述符供应内存块，它们各自的元信息中用内存块描述符指针指向同一个内存块描述符。

当一个arena中的内存块不够用时，需要用多个arena为同一规格内存块，此例的内存块描述符规格是16字节，因此与其关联的arena规格也必须是16字节。 当它的内存块分配耗尽时，系统又创建右边的arena(虚线表示的)，从而保证该规格的内存块货源充足。

在我们的实现中，针对小内存块的arena占用1页框内存，除了元信息外的剩下的内存被平均分成多个小内存块。

接下来先实现7种规格的内存块描述符

在/kernel/memory.h定义，增加以下代码，其余不需要变化。

用到list_elem，定义在list.h，记得加上头文件

#include "list.h"

/* 内存块 */
struct mem_block {
    struct list_elem free_elem;
};


/* 内存块描述符 */
struct mem_block_desc {
    uint32_t block_size;        // 内存块大小
    uint32_t blocks_per_arena;  // 本 arena(一页) 中可容纳此 mem_block 的数量
    struct list free_list;      // 目前可用的 mem_block 链表
};


#define DESC_CNT 7             // 内存块描述符个数

/* 为 malloc 做准备 */
void block_desc_init(struct mem_block_desc* desc_array);

内存块结构struct mem_block，结构中只有一个成员struct list_elem，用来添加到同规格内存块描述符的free_list中。内存块mem_block所占用的内存是从arena中拆分出来的，其相关属性用 mem_block_desc 来描述。

内存块描述符结构struct mem_block_desc，有3个成员，free_list是空闲内存块链表，block_size是本描述符的规格，它的free_list中只能添加规格为block_size的内存块。blocks_per_arena是告诉本arena中可容纳规格为block_size的内存块的数量。链表free_list的长度是无限大的，并不等于blocks_per_arena个元素。因为blocks_per_arena只是一个arena能够提供的内存块个数，而此free_list 可以由多个 arena 提供内存块。

最后的宏DESC_CNT表示内存块描述符的数量，其值为7，原因是我们的内存块规格大小是以以2为底的指数方程来设计的，从16字节起，分别是16、32、64、128、256、512、1024字节，共有7种规格的内存块。对于小内存的arena来说，其大小是一页框4096字节，其中的内存块是大小一致的。除了元信息占用的内存外，arena中不能同时容纳两个2048的内存块，2048下一级内存规格就是1024，故最大的内存块就是1024字节。当申请的内存大小超过1024时就直接返回一个页框，不再从arena中划分，因为意义不大。

接着看/kernel/memory.c

/* 内存仓库 arena 元信息 */
struct arena {
    struct mem_block_desc* desc;    // 此 arena 关联的 mem_block_desc
    // large 为 true 时, cnt 表示的是页框数
    // 否则 cnt 表示空闲 mem_block 数量
    uint32_t cnt;
    bool large;
};


struct mem_block_desc k_block_descs[DESC_CNT];  // 内核内存块描述符数组

/* 为 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 中的内存块数量
        // blocks_per_arena(本 arena 中可容纳此 mem_block 的数量) = 
        // (每页大小 - arena 元信息) /  内存块规格
        desc_array[desc_idx].blocks_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");
    uint32_t mem_bytes_total = (*(uint32_t*) (0xb00));  // 获取物理内存大小
    mem_pool_init(mem_bytes_total);                     // 初始化内存池
    // 初始化 mem_block_desc 数组 descs, 为 malloc 做准备
    block_desc_init(k_block_descs);
    put_str("mem_init done\n");
}

arena元信息结构就是struct arena，此结构仅有3个成员，占 12字节的空间。 将来我们会从堆中创建它，我们会给arena结构体指针赋予1个页框以上的内存，那时候的arena就是个名符其实的内存仓库了，页框中除了此结构体外的部分都将作为arena的内存池区域，该区域会被平均拆分成多个规格大小相等的内存块，即mem_block，这些mem_block会被添加到内存块描述符的free_list。

结构中第1个成员是desc，它指向本arena中的内存块被关联到哪个内存块描述符，同一规格的arena只能关联到同一规格的内存块描述符，比如本arena中的内存块规格为64字节，desc只能指向规格为64字节的内存块描述符。第2个成员是cnt，它的意义要取决于第3个成员large的值。 当large为ture时，cnt表示的是本arena占用的页框数，否则large为false时，cnt表示本arena中还有多少空闲内存块可用，将来释放内存时要用到此项。

接下来定义的是内核内存块描述符数组k_block_descs[DESC_CNT]，共有7种描述符规格。用户进程也有自己的内存块描述符数组，将来定义在pcb中。

最后是内存块初始化函数block_desc_init，此函数接受1个参数，内存块描述符数组指针desc_array，功能是初始化数组内 7个描述符。 前面介绍的内存块描述符就是底层结构，在此主要就是初始化它，其他的arena及arena中的mem_block都是按需分配，将来通过malloc分配内存块时再创建。

这里就是通过for分别初始化内核内存块描述符的block_size、blocks_per_arena和free_list。 block_size起始值为16，desc_idx起始值为0，循环体的最后会将其乘以2，因此下标desc_idx 越低，block_size越小，也就是说，内核和用户内存块描述符数组中，下标越低的内存块描述符，其表示的 内存块容量越小，我们在将来会用到此结论。对blocks_per_arena初始化时，减去arena的大小后再向下整除，这样保证内存块数量不会越过此arena占用的页框边界，不过会浪费一部分内存。最后调用list_init初始化内存块描述符的free_list。

为了实现用户进程的堆内存管理，在pcb中增加了内存块描述符数组u_block_desc[DESC_CNT]。

修改/thread/thread.h的结构体task_struct

/*进程或线程的pcb，程序控制块*/
struct task_struct{
    uint32_t* self_kstack;      //各内核线程都用自己的内核栈
    pid_t pid;
    enum task_status status;
    uint8_t priority;           //线程优先级
    char name[16];
    uint8_t ticks;              //每次在处理器上的嘀咕数
    uint32_t elapsed_ticks;     //此任务自上CPU运行至今用了多少CPU嘀咕数，也就是任务运行了多久
    struct list_elem general_tag;       //用于线程在一般队列中的节点
    struct list_elem all_list_tag;      //用于线程队列thread_all_list中的结点
    uint32_t* pgdir;            //进程自己页表的虚拟地址，如果是线程则为NULL
    struct virtual_addr userprog_vaddr;     //用户进程的虚拟地址
    struct mem_block_desc u_block_desc[DESC_CNT];   //用户进程内存块描述符
    uint32_t stack_magic;       //栈的边界标记，用于检测栈的溢出
};

该数组在使用前必须要初始化，我们是在process.c中的函数process_execute中完成初始化工作的

修改/userprog/process.c

其实就是在process_execute函数里加上block_desc_init(thread->u_block_desc)

/*创建用户进程并加入到就绪队列中*/
void process_execute(void* filename,char* name){
    /*PCB内核的数据结构，由内核来维护进程信息，因此要在内核内存池中申请*/

    struct task_struct* thread = get_kernel_pages(1);
    init_thread(thread,name,default_prio);
    create_user_vaddr_bitmap(thread);
    thread_create(thread,start_process,filename);
    thread->pgdir = create_page_dir();
    block_desc_init(thread->u_block_desc);  // 初始化进程的内存块描述符
    enum intr_status old_status = intr_disable();
    ASSERT(!elem_find(&thread_ready_list,&thread->general_tag));
    list_append(&thread_ready_list,&thread->general_tag);

    ASSERT(!elem_find(&thread_all_list,&thread->all_list_tag));
    list_append(&thread_all_list,&thread->all_list_tag);
    intr_set_status(old_status);
}

arena在需要时由程序动态创建，创建它的函数就是sys_malloc，它就是malloc对应的子功能处理函数sys_malloc，sys_malloc的功能是分配并维护内存块资源，动态创建arena以满足内存块的分配。

在/kernel/memory.c增加三个函数

/* 返回 arena 中第 idx 个内存块的地址 */
static struct mem_block* arena2block(struct arena* a, uint32_t idx) {
    // 在arena所指的的页框中，跳过元信息部分，再用idx乘以arena中内存块的大小
    return (struct mem_block*) ((uint32_t) a + sizeof(struct arena) + idx * a->desc->block_size);
}


/* 返回内存块 b 所在的 arena地址 */
static struct arena* block2arena(struct mem_block* b) {
    // 将 7 种类型的内存块转换为内存块所在的arena，由于此类内存块所在的arena占据完整的1页，所以前20位是一样的
    return (struct arena*) ((uint32_t) b & 0xfffff000);
}

/* 在堆中申请 size 字节内存 */
void* sys_malloc(uint32_t size) {
    enum pool_flags PF;
    struct pool* mem_pool;
    uint32_t pool_size;
    struct mem_block_desc* descs;
    struct task_struct* cur_thread = running_thread();

    // 判断用哪个内存池
    if(cur_thread->pgdir == NULL) {
        // 若为内核线程
        PF = PF_KERNEL;
        pool_size = kernel_pool.pool_size;
        mem_pool = &kernel_pool;
        descs = k_block_descs;

    } else {
        // 用户进程 pcb 中的 pgdir 会在为其分配页表时创建
        PF = PF_USER;
        pool_size = user_pool.pool_size;
        mem_pool = &user_pool;
        descs = cur_thread->u_block_desc;
    }

    // 若申请的内存不在内存池容量范围内则直接返回 NULL
    if(!(size > 0 && size < pool_size)) {
        return NULL;
    }

    struct arena* a;
    struct mem_block* b;
    lock_acquire(&mem_pool->lock);

    // 超过最大内存块 1024, 就分配页框
    if(size > 1024) {
        // 向上取整, 得到分配的页框数量
        uint32_t page_cnt = DIV_ROUND_UP(size + sizeof(struct arena), PG_SIZE);

        a = malloc_page(PF, page_cnt);

        if(a != NULL) {
            memset(a, 0, page_cnt * PG_SIZE);   // 将分配的内存清零
            // 对于分配的大块页框, 将 desc 置为 NULL, cnt 置为页框数, large 置为 true
            a->desc = NULL;
            a->cnt = page_cnt;
            a->large = true;
            lock_release(&mem_pool->lock);
            return (void*) (a + 1);             // 跨过 arena 大小, 把剩下的内存返回

        } else {
            lock_release(&mem_pool->lock);
            return NULL;
        }

    } else {
        // 若申请的内存小于等于 1024, 可在各种规格的 mem_block_desc 中去适配
        uint8_t desc_idx;

        // 从内存块描述符中匹配合适的内存块规格
        for(desc_idx = 0; desc_idx < DESC_CNT; desc_idx++) {
            if(size <= descs[desc_idx].block_size) {
                // 从小往大, 找到后退出
                break;
            }
        }

        // 若 mem_block_desc 的 free_list 中已经没有可用的 mem_block
        // 就创建新的 arena 提供 mem_block
        if(list_empty(&descs[desc_idx].free_list)) {
            a = malloc_page(PF, 1);     // 分配 1 页框做为 arena
            if(a == NULL) {
                lock_release(&mem_pool->lock);
                return NULL;
            }
            memset(a, 0, PG_SIZE);      // 清空申请的页框

            // 对于分配的小块内存, 将 desc 置为相应内存块描述符
            // cnt 置为 arena 可用的内存块数, large 置为 false
            a->desc = &descs[desc_idx];
            a->large = false;
            a->cnt = &descs[desc_idx].blocks_per_arena;
            uint32_t block_idx;

            enum intr_status old_status = intr_disable();

            // 开始将 arena 拆分成内存块, 并添加到内存块描述符的 free_list 中
            for(block_idx = 0; block_idx < descs[desc_idx].blocks_per_arena; block_idx++) {
                b = arena2block(a, block_idx);
                ASSERT(!elem_find(&a->desc->free_list, &b->free_elem));
                list_append(&a->desc->free_list, &b->free_elem);
            }
            intr_set_status(old_status);
        }

        // 开始分配内存块
        // 从 free_list 弹出一个内存块(mem_block)中的list_elem, 获取 mem_block 的地址
        b = elem2entry(struct mem_block, free_elem, list_pop(&(descs[desc_idx].free_list)));
        memset(b, 0, descs[desc_idx].block_size);

        a = block2arena(b);     // 获取内存块 b 所在的 arena
        a->cnt--;               // 将此 arena 中的空闲块数减 1
        lock_release(&mem_pool->lock);
        return (void*) b;
    }
}

上面用到interrupt.h文件定义的enum intr_status，记得加入头文件

#include "interrupt.h"

arena2block 函数block2arena 函数实现有关 arena和 mem_block 互相转换的功能。

arena2block接受两个参数，arena指针a和内存块mem_block在arena中的索引，函数功能是返回arena中第idx个内存块的首地址。arena是从堆中创建的，方法是使arena结构体指针指向从堆中返回的一个或多个页框的内存，因此arena结构体struct arena并不是全部arena的大小，结构体中仅有3个成员，它就是我们所说的arena的元信息。 在arena指针指向的页框中，除去元信息外的部分才被用于内存块的平均拆分，每个内存块都是相等的大小且连续挨着，因此arena2block的原理是在arena指针指向的页框中，跳过元信息部分，即struct arena的大小，再用idx乘以该arena中内存块大小，最终的地址便是arena中第idx个内存块的首地址,，最后将其转换成mem_block类型后返回。 内存块大小记录在由desc指向的内存块描述符的block_size中。 转换过程对应的代码是”return (struct mem_block*)((uint32_t)a + sizeof(struct arena) +idx *a->desc->block_size)”。

block2arena函数接受一个参数，内存块指针b。 block2arena用于将7种规格的内存块转换为内存块所在的arena，由于此类内存块所在的arena占据1个完整的自然页框，所以arena中的内存块都属于这 1页框之内，内存块的高20位地址便是arena所在的地址，将此地址转换成(struct arena*)后返回即可，对应代码”return (struct arena*)((uint32_t)b & Oxf000)”。

sys_malloc函数只有一个参数size，size是申请的内存字节数。 函数开头定义了一些变量: PF、mem_pool、 pool_size和deses，它们的值由内存申请者来决定，这里的内存申请者包括内核线程和用户进程两种，后面代码就是针对这两种情况为它们赋值。

接下来定义了arena指针a和mem_block指针b，指针a用来指向新创建的arena，指针b用来指向arena中的mem_block。 arena既可处理大于1024字节的大内存分配，也支持1024字节以内的小内存分配，各自的实现还是有些区别的，下面要分这两种情况来处理。

首先判断如果申请的内存量大于 1024 字节，先计算内存量 size 需要的页框数，宏 DIV_ROUND_UP 除法向上取整，计算出的页框数存入变量page_cnt。 下面的代码”a = malloc_page(PF, page-ent)”就是从堆中创建arena，也就是把malloc_page返回的页框地址赋值给arena指针a。 所以，内存中并没有struct arena和struct mem_block静态实例，只有指向堆中的指针。 此时指针a指向的内存以页框为粒度，前12字节始终是元信息结构。 之后调用memset将arena清0。

之后开始初始化arena的元信息。 对大内存的处理我们直接返回arena的内存区就好，不需要再将其拆分成小内存块，因此没有对应的内存块描述符，故”a->desc=NULL”，a->cnt此时的意义是此arena 占用的页框数，因此a->cnt=page_cnt。 “a->large=true”表示此arena用于处理大于1024字节以上的内存分配。 arena中可被用户使用的部分是内存池部分，也就是要跨过arena前面的元信息部分，用”(a+1)”跨过arena元信息，也就是跨过一个struct arena的大小。 最后通过”return (void*)(a + 1)”把 arena中的内存池起始地址返回，此地址便是为用户分配的内存地址。

处理内存小于1024字节的情况有7种规格的内存块描述符，把它们都遍历一次，下面用for循环排查所有的内存块描述符，我们在初始化内存块描述符时，下标越低，其 block_size 的值越小，desc_idx 初始为0，从低容量的内存块向上找，把 7 种 block_size 都遍历一遍。 比如申请的内存量size为120字节，规格为128字节的内存块是最适合的。 找到后退出循环，desc_idx 便是最合适的内存块索引。 在分配之前先要判断是否有可用的内存块，这里是通过内存块描述符中的 free_list 是否为空判断的，具体功能代码是“if（list_empty(&descs[desc_idx].free_list))”。 如果free_list为空，表示目前的供货商arena已经被分配光了，此规格大小的内存块已经没有了，此时需要再创建新的arena。

“a=malloc_page(PF, 1)” 分配1页内存来创建新的arena，之后用memset(a,0, PG_SIZE)清0。 下面为新的arena初始化元信息，这次的arena用于小内存块分配，所以其desc指针必须指向具体的内存块描述符，代码”a->desc=&descs[desc_idx];”使desc指向上面找到的内存块描述符。 a->large置为false，表示此 arena不用于处理大于1024 字节的大内存。 a->cnt 置为descs[desc_idx].blocks_per_arena，表示此 arena 现在具有的空闲内存块数量。随着以后的分配，会将 a->cnt 的值减少。

在创建新的arena后，下一步是将它拆分成内存块，此部分是在for(block_idx = 0; block_idx < descs[desc_idx].blocks_per_arena; block_idx++)的for循环开始的，循环次数是descs[desc_idx].blocks_per_arena这表示此arena将被拆分成的内存块数量。 拆分内存块是通过arena2block 函数完成的，它在arena中按照内存块的索引block_idx拆分出相应的内存块。 指针b指向每次新拆分出来的内存块，然后将其添加到内存块描述符的free_list中。 以后每次发现目标内存块描述符的free_list为空时，就重新为这样block_size大小的块创建arena，将arena打散成block_size大小的内存块，继续添加到内存块描述符的free_list中。 这样一来，为同一内存块描述符提供内存块的arena将越来越多，这些arena 的desc 都指向同一个内存块描述符。

下面开始分配内存块，内存块被汇总在内存块描述符的free_list中，我们用list_pop从free_list中弹出一 个内存块，此时得到的仅仅是内存块mem_block中list_elem的地址，因此要用到elem2entry宏将其转换 成 mem_block 的地址。 a = block2arena(b)通过函数 block2arena(b)获取内存块 b 所在的 arena地址，然后将 a->cnt 减 1，表示空闲内存块少了一个。 此项是供将来释放内存使用的，释放内存时会参考cnt的值，用来判断是将mem_block回收到内存块描述符的free_list中，还是直接释放内存块所在的arena。最后将内存块b的地址转换成void*后返回，此地址便是用户进程得到的内存地址。

修改main.c看看执行结果：

#include "print.h"
#include "init.h"
#include "debug.h"
#include "memory.h"
#include "thread.h"
#include "interrupt.h"
#include "console.h"
#include "process.h"
#include "syscall-init.h"
#include "syscall.h"
#include "stdio.h"

void k_thread_a(void*);
void k_thread_b(void*);
void u_prog_a(void);
void u_prog_b(void);

int prog_a_pid = 0, prog_b_pid = 0;

int main() {
    put_str("I am kernel\n");
    init_all();

    intr_enable();    // 打开中断, 使时钟中断起作用
    thread_start("k_thread_a", 31, k_thread_a, "I am thread_a");
    thread_start("k_thread_b", 31, k_thread_b, "I am thread_b ");

    while(1);
    return 0;
}

/* 在线程中运行的函数 */
void k_thread_a(void* arg) {
    char* para = arg;
    void* addr = sys_malloc(33);
    console_put_str(" I am thread_a, sys_malloc(33), addr is 0x");
    console_put_int((int) addr);
    console_put_char('\n');
    while(1);
}

/* 在线程中运行的函数 */
void k_thread_b(void* arg) {
    char* para = arg;
    void* addr = sys_malloc(63);
    console_put_str(" I am thread_b, sys_malloc(63), addr is 0x");
    console_put_int((int) addr);
    console_put_char('\n');
    while(1);
}

/* 测试用户进程 */
void u_prog_a(void) {
    char* name = "prog_a";
    printf(" I am %s, my pid:%d%c", name, getpid(),'\n');
    while(1);
}

/* 测试用户进程 */
void u_prog_b(void) {
    char* name = "prog_b";
    printf(" I am %s, my pid:%d%c", name, getpid(), '\n');
    while(1);
}

执行结果如下：

线程k_thread_a中调用 sys_malloc(33)申请33字节的内存，线程k_thread_b中调用 sys_malloc(63)申请63字节的内存。然后将返回地址转换成整型后再打印出来。

两个线程的输出分别是0xc010200c和0xc010204c。这两个线程申请的内存字节一个是33，一个是63，它们与规格为64字节的内存块最接近，因此sys_malloc会创建规格为64字节的arena，然后把它拆分成64字节的内存块，由于是第1次申请内存且只申请了一种内存块，故系统中只存在这一个arena。 把线程thread_a获得的内存地址0xc010200c拆分成0xc0102000+0xc来看，其中0xc0102000是arena的首地址，0xc是arena元信息大小，故返回的0xc010200c是arena中第1个64字节内存块的地址。 线程thread_b获得的内存地址是0xc010204c，它与0xc010200c相差为0x40，即十进制64字节，这证明thread_a申请的33字节也占用了64字节的内存块，thread_b申请的63字节占用的是arena中第2个64字节内存块。

参考

郑钢著操作系统真象还原

田宇著一个64位操作系统的设计与实现

丁渊著ORANGE’S：一个操作系统的实现