内存分配
我们实现的内存分配比较简单，主要是伙伴算法和一个简单（陋）的Slab
1. 伙伴算法
+---------------------------------------------------------------------+
| Buddy System (Free Lists) |
+---------------------------------------------------------------------+
| |
| Level 0: [2^0] → □ ↔ □ ↔ □ ↔ ... (双向循环链表，块大小= PGSIZE * 1) |
| |
| Level 1: [2^1] → ■ ↔ ■ ↔ ... (块大小= PGSIZE * 2) |
| |
| Level 2: [2^2] → ▣ ↔ ▣ ↔ ... (块大小= PGSIZE * 4) |
| |
| Level 3: [2^3] → ▩ ↔ ▩ ↔ ... (块大小= PGSIZE * 8) |
| |
| Level 4: [2^4] → ▢ ↔ ▢ ↔ ... (块大小= PGSIZE * 16) |
| |
| Level 5: [2^5] → □□ ↔ □□ ↔ ... (块大小= PGSIZE * 32) |
| |
| Level 6: [2^6] → ■■ ↔ ■■ ↔ ... (块大小= PGSIZE * 64) |
| |
| Level 7: [2^7] → ▣▣ ↔ ▣▣ ↔ ... (块大小= PGSIZE * 128) |
| |
| Level 8: [2^8] → ▩▩ ↔ ▩▩ ↔ ... (块大小= PGSIZE * 256) |
| |
| Level 9: [2^9] → ▢▢ ↔ ▢▢ ↔ ... (块大小= PGSIZE * 512) |
| |
| Level 10: [2^10] → □□□□ ↔ □□□□ ↔ ... (块大小= PGSIZE * 1024) |
| |
+---------------------------------------------------------------------+1.1 核心算法
// 寻找当前 page 的伙伴
static struct page *find_buddy(const struct page *page, const int order)
{
uint64_t index = get_pg_index(page);
uint64_t buddy_index = index ^ (1UL << order);
...
}2. Slab
我们实现了一个简单的分配对象的方法。该方法的架构如下图：
我们仅仅实现了用于分配小内存对象，而没有其他任何的缓存对齐等一堆其他的复杂机制。
每一个热门的对象都可以为其建立专用的 kmem_cache缓存，该缓存管理了该专门对象的分配与回收。
kmem_cache->full_slabs：连接分配完的slab;kmem_cache->part_slabs：连接还有空的slab;kmem_cache->cpu_slabs：每个CPU的专用slab;kmem_cache->list：kmem_cache自身全局的链条;
在我们的实现中，严格来说，Slab只是那个小的结构体，但是我们实际使用的时候，是直接使用了一个完整的物理页面(图中的mem_page)，页面的底部放置这个结构体，该结构体上方放置空闲对象的地址链表free_list（使用堆栈实现），因为总共一个页面，也就是说，这个free_list其实是有数量限制的，我们允许的最小对象大小为 16B，slab结构体大小只有一点点。我们姑且就算剩余4000B（此处PGSIZE为4096，64位上指针为8B），那么4000/8 = 500，也就是说可以放置500个指针，管理500个对象，这数量对于我们来说已经完全够了，若不够，可以另外创建slab挂到part_list，而不是大家都挤在一起。
2.1 初始化
每个slab，都会指向一个**连续分配（我们上文基于伙伴算法实现）**的区域，该区域由1到若干个页面组成，每个页面（page）被标记的时候会有指针指向该 slab。初始化的时候，slab会把该空间根据所需对象的大小进行连续等分，然后把每一个的地址都压入free_list中,备好待用。
2.2 申请
申请的时候，由于我们只看part_slabs中的slab们，这里的都是表示有空的 slab，直接从第一个slab的空闲列表弹出一个即可。
如果part_slabs为空，则会新申请一个 slab 挂到part_slabs上，再分配。
2.3 回收
还记得初始化的时候每个页面（page）都有slab指针标记吗，那么根据当前地址，可以顺藤摸瓜找到page，然后找到 slab，然后压回free_list就好。
2.4销毁
这个就释放对应的资源就好。
kmalloc和kfree基于 Slab 实现，本质上就是分配一堆 size = 16,32,64,128......的对象然后进行申请。申请某个大小S，就让S向上对齐2的幂。