# 页面分配算法

如果要在ucore中实现连续物理内存分配算法，则需要考虑的事情比较多，相对课本上的物理内存分配算法描述要复杂不少。下面介绍一下如果要实现一个FirstFit内存分配算法的大致流程。原理FirstFit内存分配算法上很简单，但要在ucore中实现，需要充分了解和利用ucore已有的数据结构和相关操作、关键的一些全局变量等。

## 关键数据结构与变量

`first_fit`分配算法需要维护一个查找有序（地址按从小到大排列）空闲块（以页为最小单位的连续地址空间）的数据结构，而双向链表是一个很好的选择。

`libs/list.h`定义了可挂接任意元素的通用双向链表结构和对应的操作，所以需要了解如何使用这个文件提供的各种函数，从而可以完成对双向链表的初始化/插入/删除等。

显然，我们可以通过`free_area_t`数据结构来完成对空闲块的管理。而`default_pmm.c`中定义的`free_area`变量就是干这个事情的。

`kern/mm/pmm.h`中定义了一个通用的分配算法的函数列表，用`pmm_manager` 表示。其中`init`函数就是用来初始化`free_area`变量的, `first_fit`分配算法可直接重用`default_init`函数的实现。`init_memmap`函数需要根据现有的内存情况构建空闲块列表的初始状态。何时应该执行这个函数呢？

通过分析代码，可以知道：

```
kern_init --> pmm_init-->page_init-->init_memmap--> pmm_manager->init_memmap
```

所以，`default_init_memmap`需要根据`page_init`函数中传递过来的参数（某个连续地址的空闲块的起始页，页个数）来建立一个连续内存空闲块的双向链表。这里有一个假定`page_init`函数是按地址从小到大的顺序传来的连续内存空闲块的。链表头是`free_area.free_list`，链表项是Page数据结构的`base->page_link`。这样我们就依靠Page数据结构中的成员变量`page_link`形成了连续内存空闲块列表。

## 设计实现

`default_init_memmap`函数将根据每个物理页帧的情况来建立空闲页链表，且空闲页块应该是根据地址高低形成一个有序链表。根据上述变量的定义，`default_init_memmap`可大致实现如下：

```c
default_init_memmap(struct Page *base, size_t n) {
    struct Page *p = base;
    for (; p != base + n; p ++) {
        p->flags = p->property = 0;
        set_page_ref(p, 0);
    }
    base->property = n;
    SetPageProperty(base);
    nr_free += n;
    list_add(&free_list, &(base->page_link));
}
```

如果要分配一个页，那要考虑哪些呢？这里就需要考虑实现`default_alloc_pages`函数，注意参数n表示要分配n个页。另外，需要注意实现时尽量多考虑一些边界情况，这样确保软件的鲁棒性。比如

```c
if (n > nr_free) {
return NULL;
}
```

这样可以确保分配不会超出范围。也可加一些 `assert`函数，在有错误出现时，能够迅速发现。比如 n应该大于0，我们就可以加上

```c
assert(n \> 0);
```

这样在n<=0的情况下，ucore会迅速报错。`firstfit`需要从空闲链表头开始查找最小的地址，通过`list_next`找到下一个空闲块元素，通过`le2page`宏可以由链表元素获得对应的`Page`指针`p`。通过`p->property`可以了解此空闲块的大小。如果>=n，这就找到了！如果\<n，则list\_next，继续查找。直到`list_next== &free_list`，这表示找完了一遍了。找到后，就要从新组织空闲块，然后把找到的page返回。所以`default_alloc_pages`可大致实现如下：

```c
static struct Page *
default_alloc_pages(size_t n) {
    if (n > nr_free) {
        return NULL;
    }
    struct Page *page = NULL;
    list_entry_t *le = &free_list;
    while ((le = list_next(le)) != &free_list) {
        struct Page *p = le2page(le, page_link);
        if (p->property >= n) {
            page = p;
            break;
        }
    }
    if (page != NULL) {
        list_del(&(page->page_link));
        if (page->property > n) {
            struct Page *p = page + n;
            p->property = page->property - n;
            list_add(&free_list, &(p->page_link));
        }
        nr_free -= n;
        ClearPageProperty(page);
    }
    return page;
}
```

`default_free_pages`函数的实现其实是`default_alloc_pages`的逆过程，不过需要考虑空闲块的合并问题。这里就不再细讲了。自行阅读代码。

{% hint style="info" %}
看完了first fit算法了，就需要自己实现best fit算法了噢，思路都是一样的，依葫芦画瓢。
{% endhint %}


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nankai.gitbook.io/ucore-os-on-risc-v64/lab2/ye-mian-fen-pei-suan-fa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.