设计目标
- 实现伙伴系统
- 实现2MB大页映射
- 引入COW机制
三者的关系：
- 大页需要底层的物理内存分配器能够按2MB对齐的连续物理块
- COW需要物理内存分配器能够追踪物理页的引用计数
- 当共享的对象是大页，COW需要支持在必要时拆分大页的问题
伙伴系统
原始的XV6物理页分配按照4KB为粒度，但是并不适合大页的分配。因此需要设计一个能够按需分配2MB对齐的连续物理块的分配器，因此想到参考Linux的伙伴系统。
伙伴系统的机制：
当申请特定大小内存块时，优先匹配对应阶数的链表；
若无可用的块则向上拆分高阶块；
释放时合并相邻的空闲块。
核心数据结构与接口
数据结构：
/* 页元数据 */
struct page {int ref; //当前物理页引用计数uchar order; //当前块对应的阶uchar is_free; //是否在freelist中uchar usable; //是否可以被分配器管理
};
/* 按照Order来维护空闲页链表 */
struct {struct spinlock lock;struct run *freelist[BUDDY_MAX_ORDER + 1];
} kmem;
/* 全局的物理页元数据 */
static struct page pages[KMEM_NPAGE];
新增接口：
void* kalloc_order(int);
void kfree_order(void *, int);
void kaddref_order(void *, int);//用于在COW场景下一整块共享页的引用计数整体增加
void ksplit_order(void *, int, int);//用于COW与大页的拆分情况
void kaddref(void *);
int kgetref(void *);
分配链路
//暴露的接口，用于分配order阶的连续物理页
void *
kalloc_order(int order)
{void *pa;int idx;int i;int npage;acquire(&kmem.lock);pa = alloc_block(order);//实际的分配if(pa){//分配成功，开始按页修改元数据：增加引用计数，设置非free，设置阶数idx = pa_index((uint64)pa);npage = 1 << order;for(i = 0; i < npage; i++){pages[idx + i].ref = 1;pages[idx + i].is_free = 0;pages[idx + i].order = order;}}release(&kmem.lock);if(pa)memset(pa, 5, PGSIZE << order); // fill with junkreturn pa;
}
//找到一片按2^order*4KB对齐的连续物理页
static void *
alloc_block(int order)
{int o;int idx;struct run *r;if(!valid_order(order))panic("kalloc_order");
//从低阶往高阶找是否有足够空间for(o = order; o <= BUDDY_MAX_ORDER; o++){r = kmem.freelist[o];if(r)break;}if(o > BUDDY_MAX_ORDER)return 0;idx = pa_index((uint64)r);kmem.freelist[o] = r->next;pages[idx].is_free = 0;//TODO：可能多余了？
//如果拿到的空间大于实际需要的，则一阶一阶往下打碎while(o > order){o--;push_block(idx + (1 << o), o);}pages[idx].order = order;pages[idx].is_free = 0;return (void*)index_pa(idx);
}
//辅助函数，把对应页开始的order阶的空间放入对应的freelist中
static void
push_block(int idx, int order)
{struct run *r;pages[idx].order = order;pages[idx].is_free = 1;r = (struct run*)index_pa(idx);r->next = kmem.freelist[order];kmem.freelist[order] = r;
}
释放链路
//暴露的接口，用于释放order阶的内存
void
kfree_order(void *pa, int order)
{int idx;int i;int npage;int ref;if(!valid_order(order) || ((uint64)pa % (PGSIZE << order)) != 0)panic("kfree_order");if(!valid_page((uint64)pa))panic("kfree_order");idx = pa_index((uint64)pa);npage = 1 << order;if(idx + npage > KMEM_NPAGE)panic("kfree_order");acquire(&kmem.lock);if(pages[idx].is_free || pages[idx].order != order)panic("kfree_order");ref = pages[idx].ref;//并不直接释放，只是减少引用计数（为了适配COW机制）for(i = 0; i < npage; i++){if(!pages[idx + i].usable || pages[idx + i].order != order ||pages[idx + i].ref != ref || ref < 1)panic("kfree_order");pages[idx + i].ref--;}if(ref > 1){//如果引用计数大于1则直接返回，否则才真的释放release(&kmem.lock);return;}memset(pa, 1, PGSIZE << order);pages[idx].order = order;free_block(idx, order);release(&kmem.lock);
}
//释放内存块并自动向上合并
static void
free_block(int idx, int order)
{int buddy;while(order < BUDDY_MAX_ORDER){//合并buddy = idx ^ (1 << order); //MAGIC：用于找到伙伴的索引if(buddy < 0 || buddy >= KMEM_NPAGE)break;if(!pages[buddy].usable || !pages[buddy].is_free || pages[buddy].order != order)break;remove_block(buddy, order);//从freelist中移除if(buddy < idx)//小的idx = buddy;order++;}push_block(idx, order);//把合并结束的放到对应的freelist中
}
//把buddy从对应的freelist中移除
static void
remove_block(int idx, int order)
{struct run **p;struct run *r;p = &kmem.freelist[order];r = (struct run*)index_pa(idx);while(*p){if(*p == r){*p = r->next;pages[idx].is_free = 0;return;}p = &(*p)->next;}panic("buddy remove");
}