C 中的动态内存分配¶

本节导读¶

到目前为止，如果将我们的内核也看成一个应用，那么其中所有的变量都是被静态分配在内存中的，这样在对空闲内存的使用方面缺少灵活性。我们希望能在操作系统中提供动态申请和释放内存的能力，这样就可以加强操作系统对各种以内存为基础的资源分配与管理。

在应用程序的视角中，动态内存分配中的内存，其实就是操作系统管理的“堆（Heap）”。但现在要实现操作系统，那么就需要操作系统自身能提供动态内存分配的能力。如果要实现动态内存分配的能力，需要操作系统需要有如下功能：

初始时能提供一块大内存空间作为初始的“堆”。在没有分页机制情况下，这块空间是物理内存空间，否则就是虚拟内存空间。
提供在堆上分配一块内存的函数接口。这样函数调用方就能够得到一块地址连续的空闲内存块进行读写。
提供释放内存的函数接口。能够回收内存，以备后续的内存分配请求。
提供空闲空间管理的连续内存分配算法。能够有效地管理空闲快，这样就能够动态地维护一系列空闲和已分配的内存块。
（可选）提供建立在堆上的数据结构和操作。有了上述基本的内存分配与释放函数接口，就可以实现类似动态数组，动态字典等空间灵活可变的堆数据结构，提高编程的灵活性。

在使用C++语言的过程中，大家其实对new/delete的使用方法已经烂熟于心了。在C中，对动态内存的申请是采用如下的函数实现的:

void* malloc (size_t size);
void free (void* ptr);

其中，malloc 的作用是从堆中分配一块大小为 size 字节的空间，并返回一个指向它的指针。而后续不用的时候，将这个指针传给 free 即可在堆中回收这块空间。我们通过返回的指针变量来间接访问堆上的空间，而无法直接进行访问。事实上，我们在程序中能够直接看到的变量都是被静态分配在栈或者全局数据段上的，它们大小在编译期已知，比如这里一个指针类型的大小就可以等于计算机可寻址空间的位宽。这样的它们却可以作为背后一块大小在编译期无法确定的空间的代表，这是一件非常有趣的事情。

对于同一个页的地址而言它对应的物理内存时连续的。但是，连续的虚拟地址空间不一定对应着连续的物理地址空间，因此我们需要一个数据结构来存储哪些物理内存是可用的。对于这种给不连续的情况，我们采用了链表的数据结构，将空闲的每个PAGE大小的物理内存空间作为listnode来进行内存的管理。这些新增的代码在kalloc.c之中。

kalloc之中的动态内存分配¶

我们采用链表结构记录空闲的物理地址。因此当应用程序申请一段动态内存的时候，只需要把链表头所指向地址拿出即可。

// os/kalloc.c
struct linklist {
    struct linklist *next;
};

struct {
    struct linklist *freelist;
} kmem;

注意，我们的管理仅仅在页这个粒度进行，所以所有的地址必须是 PAGE_SIZE 对齐的。

// os/kalloc.c

// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
void *kalloc(void)
{
    struct linklist *l;
    l = kmem.freelist;
    if (l) {
        kmem.freelist = l->next;
        memset((char *)l, 5, PGSIZE); // fill with junk
    }
    return (void *)l;
}

// Free the page of physical memory pointed at by v,
// which normally should have been returned by a
// call to kalloc().  (The exception is when
// initializing the allocator; see kinit above.)
void kfree(void *pa)
{
    struct linklist *l;
    if (((uint64)pa % PGSIZE) != 0 || (char *)pa < ekernel ||
        (uint64)pa >= PHYSTOP)
        panic("kfree");
    // Fill with junk to catch dangling refs.
    memset(pa, 1, PGSIZE);
    l = (struct linklist *)pa;
    l->next = kmem.freelist;
    kmem.freelist = l;
}

那么我们的内核有那些空闲内存需要管理呢？事实上，qemu 已经规定了内核需要管理的内存范围，可以参考这里，具体来说，需要软件管理的内存为 [0x80000000, 0x88000000)，其中，rustsbi 使用了 [0x80000000, 0x80200000) 的范围，其余都是内核使用。来看看 kmem 的初始化

// os/kalloc.c

// ekernel 为链接脚本定义的内核代码结束地址，PHYSTOP = 0x88000000
void
kinit()
{
    freerange(ekernel, (void*)PHYSTOP);
}

// kfree [pa_start, pa_end)
void
freerange(void *pa_start, void *pa_end)
{
    char *p;
    p = (char*)PGROUNDUP((uint64)pa_start);
    for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE)
        kfree(p);
}

我们在main函数中会执行kinit，它会初始化从ekernel到PHYSTOP的所有物理地址作为空闲的物理地址。freerange中调用的kfree函数以页为单位向对应内存中填入垃圾数据（全1），并把初始化好的一个页作为新的空闲listnode插入到链表首部。

注意,C语言之中要求进行内存回收，也就是malloc以及free要成对出现。但是我们的OS中不强制要求这一点，也就是如果测例本身未在申请动态内存后显式地调用free来释放内存，OS无需帮助它释放内存。