关于操作系统:从零开始写-OS-内核-实现堆和-malloc

系列目录

• 序篇
• 筹备工作
• BIOS 启动到实模式
• GDT 与保护模式
• 虚拟内存初探
• 加载并进入 kernel
• 显示与打印
• 全局描述符表 GDT
• 中断解决
• 虚拟内存欠缺
• 实现堆和 malloc
• 创立第一个内核线程
• 多线程运行与切换
• 锁与多线程同步
• 过程的实现
• 进入用户态
• 一个简略的文件系统
• 加载可执行程序
• 零碎调用的实现
• 键盘驱动
• 运行 shell

黑盒 malloc

到目前为止，所有的内存都是动态调配的，这显然不是一种高效的做法，不可能满足后续 kernel 开发的需要，动静分配内存也就是 malloc 是咱们必须要实现的性能。

想必你在以前 C 编程里用过 malloc，晓得它是用来调配一块指定大小的内存返回给你，用完还得手动 free；如果你对它还感到神秘，不晓得它外部到底做了什么事件的，或者说连它调配进去的内存大略在什么中央都不晓得的，甚至连 malloc 这个单词是什么的缩写都不晓得的，那须要检查一下了。

哈别缓和，这个我的项目的意义就在于带你扫视这些底层常识和原理。malloc 确实是咱们平时始终用，但可能从未真正详察过的货色，这一篇将解读并实现一个简略的 malloc 库函数。

堆 heap

malloc 调配的内存是在 堆 heap 上的，这里的 heap 不是数据结构里讲的大顶堆小顶堆那种，它只是一块单纯的内存区域而已，例如在用户空间的 heap 位于 stack 和程序加载区域之间：

而在 kernel 空间要实现 malloc，同样须要在一大块 heap 上进行操作。回到咱们的 kernel 空间，它目前的状态是这样：

前三个 4MB 曾经被占用，从 0xC0C00000 开始是自由空间，咱们无妨就将 kernel 的 heap 空间从这里开始划定，到某处完结，即图中粉红色区域，当前这里就是咱们挖内存的高兴星球。

heap 上的 malloc

heap 是一个大池子，malloc 做的事件就是在 heap 里圈地盘挖内存，例如你须要 32 bytes 内存，它就在 heap 上找一段还没有被应用的，长度为 32 bytes 的区域给你，就是这样而已。

这看上去非常简单，然而实际上却是一个很宏大简单的课题。这里有几个外围问题须要解决：

• 建设一个数据结构治理内存块的调配和开释，确保所有都正确有序；
• 速度快，内存碎片少；

先看第一个问题，建设一个数据结构来治理这块内存，这并不是像它看上的那么简略。这里的数据结构并不是在别的中央额定建设的，而是自身就坐落在 heap 上的，也就是说它是内建的，因为这依然是一个蛋鸡问题。通常意义上的数据结构，例如链表，树，hash 表之类的，个别都是须要动静分配内存的，然而 heap 的本意就是用来解决动静分配内存的问题的，这样又回到了原点。所以治理 heap 本人的数据结构，是在 heap 外部自我编织的，这与当前要讲的的磁盘文件系统很相似。

对于第二个问题，实质上就是性能问题，这并不是咱们这个我的项目的重点。咱们首先须要保障的是正确性，否则所有性能都无从谈起。对于内存动态分配治理的问题切实是一个太巨大简单的课题，有各种各样的技术论文和实现形式在探讨这些问题，光是 C 规范库里 malloc 实现就及其简单了。咱们限于工夫和本身程度，不会在这方面深挖，而是采纳一种最简略的实现形式。

kmalloc 设计思路

这里加了一个 k，叫 kmalloc，也就是 kernel malloc，示意这是 kernel 空间的 malloc 函数，外围 API 有这几个：

void* kmalloc(uint32 size);
void* kmalloc_aligned(uint32 size);
void free(void* ptr);

其中 kmalloc_aligned 示意调配进去的内存块，起始地址是 page aligned 的，这在 kernel 开发中是一个常见需要。

我这里采纳的实现形式，是照搬了之前举荐的教程 JamesM’s kernel development tutorials 里的办法，因为这的确应该是最简略弱智的形式了。不过下面教程里的代码我实测下来应该是有问题的，所以我应用它的思路齐全本人实现了一遍，并且加上了测试，目前来看是没什么大问题，当然如有 bug 在劫难逃，欢送斧正，代码在 src/mem/kheap.c。

实现思路很简略，就是将所有的空白区域的地位用一个有序数组存起来：

这样当你须要调配一块指定大小为 t 的内存时，就从这个数组里找到第一个大于 t 的空白区域，就能够从下面割下一块大小为 t 的区域，而后将剩下的空白局部还回去，并且使数组依然有序。

其实数组并不强求有序，有序的目标只是为了能更高效地查找适合的空白块。你能够一个个遍历，也能够应用二分查找。

当你要 free 一块曾经调配的内存，就将它从新放回数组里就能够了。当然这里也有一些非凡状况，例如 free 的区域的左邻右舍正好也是空白区域，那么能够将它们合并成一个大的空白区域。对于 heap 来讲，当然是更欢送大块的空白区域，因为大空白的可切分能力更强，这意味着更少的 碎片（fragment），而碎片是令人讨厌的。

因而咱们的 heap，能够布局为两个区域：

1. 下面提到的有序数组 ordered array，
2. 大片的内存区域，用来理论分配内存的，咱们称之为内存池 memory pool：

而内存池中的每一块（红色或者灰色），也不是 100% 齐全拿进去给使用者的，它外面也蕴含了对于这个色块的一些信息：

咱们将 memory pool 里的每一块区域叫 block，它的放大如上图所示，它有一个 header，定义为：

struct kheap_block_header {
  uint32 magic;
  uint8 is_hole;
  uint32 size;
} __attribute__((packed));

其中：

• magic 是用来标识 header 的；
• is_hole 示意这个 block 是被应用的（灰色），还是自在的（红色）；
• size 示意的是这个 block 里真正可调配进来的内存区域大小，即图中蓝色斜线局部；

对应的，block 还有一个 footer：

struct kheap_block_footer {
  uint32 magic;
  kheap_block_header_t* header;
} __attribute__((packed));

其中：

• magic 和 header 里的一样；
• header 是指向 header 的指针，因为某些状况下咱们须要从 footer 登程，定位到 header 的地位；

好了，设计思路局部到此结束，接下来就是实现。

kmalloc 实现

有序数组 ordered_array

首先须要实现 ordered array 的构造，咱们能够将它封装为一个抽象类，我的代码实现在 src/utils/ordered_array.c 里，可供参考。

typedef void* type_t;

typedef struct ordered_array {
  type_t array;
  uint32 size;
  uint32 max_size;
  comparator_t comparator;
} ordered_array_t;

对于这个类，须要意识到的外围概念是，这是一个 指针数组，字段 array 即示意这个数组，因而它是一个泛型，这个类还须要传入一个 comparator 用于为数组排序：

// An comparator function is used to sort elements.
//
// Returns -1, 0 or 1 if the first element
// is <, == or > the second, respectively.
typedef int32 (*comparator_t)(type_t, type_t);

具体的实现细节不多说，比较简单，就是插入排序而已；

另外留神这个数组的大小是动静可变的，一开始是 0，随着插入和删除元素，size 一直变动；最大 capacity 由 max_size 管制；

heap 构造

接下来定义 kheap 的构造：

typedef struct kernel_heap {
  ordered_array_t index;
  uint32 start_address;
  uint32 end_address;
  uint32 size;
  uint32 max_address;
} kheap_t;

这里定义了一些对于 heap 的大小的一些字段：start_address 和 end_address 示意以后 heap 的起始和完结地位。这里要留神，heap 一开始是比拟小的，而后在应用过程中能够逐步变大。当找不到一块适合的空白区域分配内存时，能够扩大（expand）以后 heap：

接下来，就是之前说的 ordered_array，字段命名为 index，用于有序保留所有的空白 block。留神一下这里的 index 初始化的形式，它的外部指针数组 array 起始地址就是整个 heap 的起始地址，kheap_block_comparator 比拟的是两个 block 的大小：

kheap_t create_kheap(uint32 start,
                     uint32 end,
                     uint32 max) {
  kheap_t kheap;

  // Initialize the index array.
  kheap.index = ordered_array_create((type_t*)start, KHEAP_INDEX_NUM, &kheap_block_comparator);
  
  // ...

  make_block(start, end - start - BLOCK_META_SIZE, IS_HOLE);
  ordered_array_insert(&kheap.index, (type_t)start);

  // ...
}

整个 heap 初始化，只有 1 个大的空白 block：

malloc 实现

有了下面的设计和铺垫，malloc 实际上曾经瓜熟蒂落，只有从 index 数组里找到一个适合的红色 block，在下面切下须要的内存，将它变成一个灰色的 block 调配给用户，而后将剩下的红色局部从新放回 index 数组即可。它的实现外围函数是 alloc。

alloc 的难点在于切割后剩下局部的解决，并不是任何状况下残余的局部都须要返还给 kheap，最起码的，残余局部的大小须要大于 header + footer，这个应该很好了解。

另外，这里比拟值得探讨的是当要求 page_align 时，即调用 kmalloc_aligned，状况会变得复杂。个别状况的 free block 不太可能正好是 page aligned，所以在它外部寻找到第一个 page aligned 的中央，从那里开始切割：

虚线标出了 page aligned 的点位。这样的宰割带来一个问题就是切割下来局部的后面和前面都可能无余留区域，所以须要将它们也从新返还 kheap。在我的代码实现里，规定了它后面那块预留区域的大小，必须能包容一个残缺的 block（大于 header + footer），否则会到下一个 page aligned 的中央开始切割。

free 实现

free 函数的实现相对而言比较简单，须要思考的中央就是被 free 的 block，如果左邻右舍也是 free 的，那么能够 merge 成一个大的 free block：

总结

这一篇其实算是一个很独立的篇章，即便不放在 kernel 这个大我的项目里，也能够独自拿进去做一个课题。动态内存调配是水很深的一个课题，咱们这里只是采纳了一种最简略的实现形式，但即便它是最简略的，要正确地实现它依然并不容易。我在开发中花了几天工夫，并加以大量测试才根本调通。就像实现 paging 那样，kheap 也必须保障相对的正确，因为在后续的开发中，它将是咱们分配内存的主战场。