ChCore实验 2: 内存管理

1 物理内存管理

1.1 物理内存布局

上图展示了 ChCore 的物理内存布局。其中，物理地址img_start以下是保留的。img_start~img_end（img_start被硬编码为 0x80000）被分为了两个区域：其中的底部区域作为 bootloader 代码、数据和 CPU 栈，每个 CPU 栈的大小为 4KB；顶部区域用于内核的代码、数据和 CPU 栈，每个CPU 栈的大小为 8KB。img_end以上空闲的物理内存由物理页分配器管理。分配器将内存区域划分为两个范围：元数据范围和页面范围，它们的大小与页面数（npages）有关。页面元数据包括list_node和flags等。

问题 1

请简单解释，在哪个文件或代码段中指定了 ChCore 物理内存布局。你可以从两个方面回答这个问题: 编译阶段和运行时阶段。

编译阶段：Lab1中看到，在scripts/linker-aarch64.lds.in中定义了保留、BootLoader和Kernel各段的LMA和VMA

#include "../boot/image.h"

SECTIONS
{
    . = TEXT_OFFSET;
    img_start = .;
    init : {
        ${init_object}
    }

    . = ALIGN(SZ_16K);

    init_end = ABSOLUTE(.);

    .text KERNEL_VADDR + init_end : AT(init_end) {
        *(.text*)
    }

    . = ALIGN(SZ_64K);
    .data : {
        *(.data*)
    }
    . = ALIGN(SZ_64K);

    .rodata : {
        *(.rodata*)
    }
    _edata = . - KERNEL_VADDR;

    _bss_start = . - KERNEL_VADDR;
    .bss : {
        *(.bss*)
    }
    _bss_end = . - KERNEL_VADDR;
    . = ALIGN(SZ_64K);
    img_end = . - KERNEL_VADDR;
}

运行阶段：在kernel/mm/mm.c的mm_init()中定义了页面元数据和页面的物理地址。

void mm_init(void)
{
	vaddr_t free_mem_start = 0;
	struct page *page_meta_start = NULL;
	u64 npages = 0;
	u64 start_vaddr = 0;

	free_mem_start =
	    phys_to_virt(ROUND_UP((vaddr_t) (&img_end), PAGE_SIZE));
	npages = NPAGES;
	start_vaddr = START_VADDR;
	kdebug("[CHCORE] mm: free_mem_start is 0x%lx, free_mem_end is 0x%lx\n",
	       free_mem_start, phys_to_virt(PHYSICAL_MEM_END));

	if ((free_mem_start + npages * sizeof(struct page)) > start_vaddr) {
		BUG("kernel panic: init_mm metadata is too large!\n");
	}

	page_meta_start = (struct page *)free_mem_start;
	kdebug("page_meta_start: 0x%lx, real_start_vadd: 0x%lx,"
	       "npages: 0x%lx, meta_page_size: 0x%lx\n",
	       page_meta_start, start_vaddr, npages, sizeof(struct page));

	/* buddy alloctor for managing physical memory */
	init_buddy(&global_mem, page_meta_start, start_vaddr, npages);

	/* slab alloctor for allocating small memory regions */
	init_slab();

	map_kernel_space(KBASE + (128UL << 21), 128UL << 21, 128UL << 21);
	//check whether kernel space [KABSE + 256 : KBASE + 512] is mapped 
	kernel_space_check();
}

1.2 伙伴系统

对于伙伴系统的介绍，详见纸质书P126。

ChCore 基于以上的物理内存布局，实现物理内存分配器：每个物理页面对应一个struct page对象维护页面信息，并且通过该对象的链表跟踪哪些页面是空闲的。

一种主流的内存管理机制——伙伴系统可以用于组织物理页面。伙伴系统中的每个内存块都有一个阶（order） ， 阶是从 0 到指定上限buddy_max_order的整数。一个 n 阶的块的大小为 $ 2^n $ * PAGE_SIZE， 因此这些内存块的大小正好是比它小一个阶的内存块的大小的两倍。内存块的大小是 2 次幂对齐，使地址计算变得简单。当一个较大的内存块被分割时，它被分成两个较小的内存块，这两个小内存块相互成为唯一的伙伴。一个分割内存块也只能与它唯一的伙伴块进行合并（合并成他们分割前的块）。

struct global_mem是用来描述物理内存的数据结构，保存了伙伴系统中一组空闲内存块的链表free_lists，每组链表中使用list_head链接所有同order的内存块。 ChCore 提供了一些有用的函数和宏来操作struct list_head:

• init_list_head(struct list_head * head) ：初始化列表头
• list_add(struct list_head *new, struct list_head *head)：向列表的头部添加新节点
• list_del(struct list_head *entry)：删除列表中的这个节点
• list_entry(ptr, type, member)：使用给定的ptr获取相应的对象， member是对应对象中struct list_head的变量名

练习 1

实 现kernel/mm/buddy.c中 的 四 个 函 数：buddy_get_pages()，split_page()，buddy_free_pages()，merge_page()。
请参考伙伴块索引等功能的辅助函数:get_buddy_chunk()。

踩坑记录：
需要为测试文件加权限，参考https://zhuanlan.zhihu.com/p/551630526。

在docker中调试需要安装GDB，但会缺权限。
make docker后，用docker exec -it -u root 4d300bc3f689 bash 以root权限进入docker（bash前换成自己的容器号），然后apt-get update，即可安装。

在实现四个函数前，首先查看一下buddy.h中对于page、page_mem_pool的定义

#pragma once

#include <common/types.h>
#include <common/list.h>

/*
 * Supported Order: [0, BUDDY_MAX_ORDER).
 * The max allocated size (continous physical memory size) is
 * 2^(BUDDY_MAX_ORDER - 1) * 4K, i.e., 16M.
 */
#define BUDDY_PAGE_SIZE     (0x1000)
#define BUDDY_MAX_ORDER     (14UL)

/* `struct page` is the metadata of one physical 4k page. */
struct page {
	/* Free list */
	struct list_head node;
	/* Whether the correspond physical page is free now. */
	int allocated;
	/* The order of the memory chunck that this page belongs to. */
	int order;
	/* Used for ChCore slab allocator. */
	void *slab;
};

struct free_list {
	struct list_head free_list;
	u64 nr_free;
};

/* Disjoint physical memory can be represented by several phys_mem_pool. */
struct phys_mem_pool {
	/*
	 * The start virtual address (for used in kernel) of
	 * this physical memory pool.
	 */
	u64 pool_start_addr;
	u64 pool_mem_size;

	/*
	 * This field is only used in ChCore unit test.
	 * The number of (4k) physical pages in this physical memory pool.
	 */
	u64 pool_phys_page_num;

	/*
	 * The start virtual address (for used in kernel) of
	 * the metadata area of this pool.
	 */
	struct page *page_metadata;

	/* The free list of different free-memory-chunk orders. */
	struct free_list free_lists[BUDDY_MAX_ORDER];
};

/* Currently, ChCore only uses one physical memory pool. */
extern struct phys_mem_pool global_mem;

void init_buddy(struct phys_mem_pool *zone, struct page *start_page,
		vaddr_t start_addr, u64 page_num);

struct page *buddy_get_pages(struct phys_mem_pool *, u64 order);
void buddy_free_pages(struct phys_mem_pool *, struct page *page);

void *page_to_virt(struct phys_mem_pool *, struct page *page);
struct page *virt_to_page(struct phys_mem_pool *, void *ptr);
u64 get_free_mem_size_from_buddy(struct phys_mem_pool *);

page包含结点指针，是否被分配，以及阶数的信息。

phys_mem_pool由page_metadata和freelists构成（freelists是由BUDDY_MAX_ORDER个freelist构成的数组，每个阶空闲页储存在一个freelist中）。

后面涉及到从phys_mem_pool中添加、删除一个指定的页。每次操作除了向链表中增删元素外，还需要维护freelist中的节点数信息，为此在ChCore提供的函数基础上，实现page_add()和page_del()两个函数以便使用。

/*
chcore提供的函数：
• init_list_head(struct list_head * head)：初始化列表头
• list_add(struct list_head *new, struct list_head *head)：向列表的头部添加新节点
• list_del(struct list_head *entry)：删除列表中的这个节点
• list_entry(ptr, type, member)：使用给定的ptr获取相应的对象，member是对应对象中struct list_head的变量名
为了方便,这里实现page_add,page_del两个函数,分别在内存池对应order的free_list中加入/删除一个free page
*/
//add a page into a pool
void page_add(struct phys_mem_pool *pool, struct page *page) {
	struct free_list *fl = & pool->free_lists[page->order];
	list_add(& page->node, & fl->free_list);
	fl->nr_free++;
}
//del a page from a pool
void page_del(struct phys_mem_pool *pool, struct page *page) {
	struct free_list *fl = & pool->free_lists[page->order];
	list_del(& page->node);
	fl->nr_free--;
}

首先来看split_page()和merge_page()。

split_page()的过程：

1. 首先将原来的page从内存池中暂时删除。

2. 每次首先将page的order减1，然后使用get_buddy_chunk()获取伙伴页，将伙伴页加入内存池。直到达到指定的order。（注意，这里顺序一定不能反，因为get_buddy_chunk()对page的order有依赖）。

3. 将最后得到的page加回内存池。

merge_page()的过程相似，但略有差异。

1. 首先将原来的page从内存池中暂时删除。

2. 每次首先使用get_buddy_chunk()获取伙伴页，调整page在左、buddy_page在右，然后将伙伴页从内存池中删去并将page的order加1，就完成了页的合并（因为当前页和伙伴页在内存上连续）。继续合并下去，直到无法继续合并。

3. 将最后得到的page加回内存池。

实现代码如下。测试数据有很多边界情况，比如get_buddy_chunk()可能会返回一个不同阶的page（暂时没去深究它的原理）,需要耐心调试。

/*
 * split_page: split the memory block into two smaller sub-block, whose order
 * is half of the origin page.
 * pool @ physical memory structure reserved in the kernel
 * order @ order for origin page block
 * page @ splitted page
 * 
 * Hints: don't forget to substract the free page number for the corresponding free_list.
 * you can invoke split_page recursively until the given page can not be splitted into two
 * smaller sub-pages.
 */
static struct page* split_page(struct phys_mem_pool *pool, u64 order,
			       struct page *page)
{
	// <lab2>
	//检查page是否可用(未被分配)
	if (page->allocated) {
		kwarn("split_page: Try to split an allocated page\n");
		return NULL;	
	}
	//从pool中删去这个page
	page_del(pool, page);

	//不需要递归
	while (page->order > order) {
		//分裂,并将buddy_page加进pool
		page->order--;
		struct page *buddy_page = get_buddy_chunk(pool, page);
		if (buddy_page != NULL) {
			buddy_page->allocated = 0;
			buddy_page->order = page->order;
			page_add(pool, buddy_page);
		}
	}
	//将最终的page加进pool
	page_add(pool, page);
	return page;
	//struct page *split_page = NULL;
	//return split_page;
	// </lab2>
}

/*
 * merge_page: merge the given page with the buddy page
 * pool @ physical memory structure reserved in the kernel
 * page @ merged page (attempted)
 * 
 * Hints: you can invoke the merge_page recursively until
 * there is not corresponding buddy page. get_buddy_chunk
 * is helpful in this function.
 */
static struct page *merge_page(struct phys_mem_pool *pool, struct page *page)
{
	// <lab2>

	//检查page是否可用(未被分配)
	if (page->allocated) {
		kwarn("merge_page:Try to merge an allocated page\n");
		return NULL;	
	}

	//从pool中删去原来的page
	page_del(pool, page);

	//不断合并,until there is not corresponding buddy page
	while (page->order < BUDDY_MAX_ORDER - 1) {
		struct page* buddy_page = get_buddy_chunk(pool, page);
		if (buddy_page == NULL || buddy_page->allocated || buddy_page->order != page->order) break;
		//调整为page在左，buddy在右
		if (page > buddy_page) { struct page* tmp = buddy_page; buddy_page = page; page = tmp; }
		//合并,并从pool中删去buddy_page.
		buddy_page->allocated = 1;
		page_del(pool, buddy_page);
		page->order++;	//buddy_page在内存上连续，直接左节点order++;
	}

	//将最终的page加进pool
	page->allocated = 0;
	page_add(pool, page);

	return page;
	//struct page *merge_page = NULL;
	//return merge_page;
	// </lab2>
}

下面来看buddy_get_pages()，功能是从pool中获取一个指定order的page。
根据注释给出的提示，只需要找到第一个不小于order的不为空的freelist，从中获取一个结点并分裂到指定的order即可。最后需要将得到的page标记为已分配。

/*
 * buddy_get_pages: get free page from buddy system.
 * pool @ physical memory structure reserved in the kernel
 * order @ get the (1<<order) continous pages from the buddy system
 * 
 * Hints: Find the corresonding free_list which can allocate 1<<order
 * continuous pages and don't forget to split the list node after allocation   
 */
struct page *buddy_get_pages(struct phys_mem_pool *pool, u64 order)
{
	// <lab2>
	//struct page *page = NULL;
	
	//找到第一个>=order且有空闲的order
	u64 get_order = order;
	while (get_order < BUDDY_MAX_ORDER && pool->free_lists[get_order].nr_free <= 0) {
		get_order++;
	}

	//找不到所需的free pages
	if (get_order >= BUDDY_MAX_ORDER) {
		kwarn("buddy_get_pages: no avaliable pages");
	}

	//list_entry(ptr, type, member)：
	//使用给定的ptr获取相应的对象，member是对应对象中struct list_head的变量名
	struct page *get_page = list_entry(pool->free_lists[get_order].free_list.next, struct page, node);

	if (get_page == NULL) {
		return NULL;
	}
	
	//分割到指定的order,并标记为已分配
	split_page(pool, order, get_page);
	get_page->allocated = 1;
	page_del(pool, get_page);

	return get_page;
	// </lab2>
}

最后是buddy_free_pages(),相对比较简单，将指定页标记为未分配，然后尝试向上合并。

/*
 * buddy_free_pages: give back the pages to buddy system
 * pool @ physical memory structure reserved in the kernel
 * page @ free page structure
 * 
 * Hints: you can invoke merge_page.
 */
void buddy_free_pages(struct phys_mem_pool *pool, struct page *page)
{
	// <lab2>
	if (page->allocated == 0) {
		kwarn("buddy_free_pages: Try to free a free page\n");
		//return;
	}

	page->allocated = 0;
	page_add(pool, page);
	//尝试向上合并
	merge_page(pool, page);
	// </lab2>
}

本栏目推荐文章
• ThreadLocal真的会造成内存泄漏吗？
• 数组内存图
• C++ 单例模式以及内存管理
• JVM内存参数设置
• 【C语言】动态内存申请，堆空间与栈空间差异
• 虚拟化与大页内存与numa
• Prometheus监控k8s集群节点主机内存/CPU使用率
• Prometheus监控容器内pod节点内存/CPU使用率
• GBD调试之内存查看与修改(五)
• [转帖]解Bug之路-记一次JVM堆外内存泄露Bug的查找