# 物理内存管理

在初期为了尽快写完后面的内容，我们先设计了一款简单的first-fit算法，然后又重写了一个伙伴系统算法，当然，我们在这两种算法的基础上做了自己的改进。

## first-fit算法

### 算法思路
first-fit算法顾名思义，就是找到第一个符合条件的连续区域，然后分配这个连续区域。

### 数据结构
这样的场景非常适合用链表来实现，但是因为现在正在写的是物理内存分配器，不可能有动态的链表，因此我们使用数组来模拟链表。我们链表除了pre、nxt,节点还包含一个表示是否使用的flags，一个用于表示后面几个节点属于他管理的num。链表结构体的定义如下：


```cpp
struct Page
{
	Uint64 flags, //
		   num; //后面有几个页属于他管理
	Page *pre,
		 *nxt;
};
```

### 实现方法

#### 初始化
我们使用链表来维护我们的空闲内存，初始化的时候，分配空闲物理内存除以页大小个节点，链表头结点的num设置为节点数量，表示包括他自己后面的num个节点都由他来管理，flags设置为0，表示未被使用。

#### 分配内存

请求分配内存时，假设需要x个，则从链表头结点开始往后找，找到一个num>x的空闲节点，将这个节点的n设置为x，把连带它的后面x个节点从链表摘下来。然后再把链表重新拼接起来。

#### 回收内存

回收内存的时候，因为每个节点都可以计算出编号，因此我们把他直接连接回链表即可。如果当前头节点在要回收的链表之后，则把当前节点设置为头结点，再连接上原来的头结点即可。

需要注意的是，我们每次连接上的时候，都要看一下后面第n+1个位置，如果这个位置也是空闲的，那么就可以把这两个相邻的串合并。但是这样有一个问题，就是如果回收的顺序是从后往前，由于无法确定回收节点的前一个串的其实节点，因此无法判断是否可以合并。所以我们在分配的时候，还需要再次检查一下时候可以合并。

## 伙伴系统+线段树

### 算法思路
伙伴系统的思路是，内存被分成含有很多页面的大块, 每一块都是2个页面大小的方幂. 如果找不到想要的块, 一个大块会被分成两部分, 这两部分彼此就成为伙伴. 其中一半被用来分配, 而另一半则空闲. 这些块在以后分配的过程中会继续被二分直至产生一个所需大小的块. 当一个块被最终释放时, 其伙伴将被检测出来, 如果伙伴也空闲则合并两者。

使用伙伴系统可以很好的解决外部碎片问题。

### 数据结构

#### 链表结构体

我们借鉴了linux的设计，也分为zone和page两个结构体，zone里面的free_area[i]表示的是大小为2^i个页的空闲内存链表。

```cpp
struct Page
{
	Page *pre,*next;
	int flags;//-1:不可使用，0未使用，1已使用
	int order;
	int index;
	Uint64 addr;
};
```
#### Zone、FreeArea结构体
```cpp
class FreeArea
{
	public:
		Page head;
};

class Zone
{
	public:
		Uint64 physical_memory_size;
		Uint64 end_addr;//物理内存结束地址

		Uint64 page_size;//每个页的大小
		Uint64 page_base;//内核结束地址，也就是页表的起始地址
		Page * page;

		Uint64 page_num;//页的数量
		Uint64 valid_page_num;//实际可用的页的数量

		Uint64 page_need_memory;//页表需要的内存

		Uint64 free_memory_start_addr;//除去页表，实际可用内存的起始地址
		Uint64 free_memory_size;//除去页表，实际可用内存的大小
		/*
		|----kernel---------------|------------------page-------------|---------------free_memory-----------|
		-------------kernel_end(page_base)------------------free_memmory_start---------------------------end_addr
		*/
	
		int max_order;
		int max_depth;
		FreeArea  free_area[64];
};
```

### 实现方法

伙伴系统最重要的是如何找到一块物理内存的伙伴，以及把他们合并，把一块大的内存分裂为两块小内存。

在linux中，使用了flag标记的方法，而在我们的系统中，我们使用了线段树来维护的方式。我们线段树的根节点对应着最大的一块物理内存，例如2^10个页，那么线段树的根节点就是2^10个页的大小，且他的起始地址为0,index为1。根节点下面两个节点，index分别为2和3，大小都是2^9个页的大小，管理的页分别为[0,2^9)和[2^9,2^10)。2号节点和三号节点下面又各有两个节点，以此类推，直到最下层每个节点代表2^0=1个页。

在这种设计中，要找到一个节点的伙伴和父节点都是非常方便的。因为我们可以直到index为1的节点的物理地址是多少——初始化的时候记录一下即可。然后对于index为i的节点，获取他们兄弟节点的方法为，如果是奇数，就返回index-1，否则就返回index+1号节点。使用代码实现为：

```cpp
Page* Zone::GetPartner(Page * p)
{
    if(p->index%2==1)
    {
        return &page[p->index - 1];
    }
    else
    {
        return &page[p->index + 1];
    }
}
```

而如果要找到i号节点的父亲、左孩子、友孩子，则只要返回i*/2,i\*2,i\*2+1即可。

分配内存与伙伴系统是一样的，对于一次要求i个页的分配，则去free_area中order = $\lceil log(i) \rceil$ 的位置寻找一个节点即可。如果没有，则去找order = $\lceil log(i) +1 \rceil$ 的位置，如果还没有，则去找order = $\lceil log(i) + 2 \rceil$ 的位置，依次类推，直到找到一个节点。如果不是第一就直接找到的，则需要把节点不断地分裂。

回收内存的时候，我们只要使用GetPartner()函数，看一下他的伙伴是否是未被使用状态，如果是，则将他们两个合并成一个大的节点，插入到free_area中，否则直接将自己插入到free_area中。

## 遇到的问题

我们的内存分配器遇到了两个当时困扰我们很久的问题，一个就是用来存储线段树的内存被改写了，后来发现是连接脚本没有写对，一些内核的数据和我们的线段树的数据放在了同一片物理内存区域，导致被改写。第二个是有些节点会被分配两次，之后检查发现是线段树分裂的时候，将这个节点从链表上摘下来了，但是忘记设置了他的flag位，导致这个节点的伙伴在判断的时候错误的认为这个节点没有被使用，把这个节点有合并起来连接到链表上，之后分配的时候又重新分裂，而分裂的时候直接将他插入了空闲内存区域，导致同一个节点在我们的空闲内存链表上被插入了两次。







-----------------

By：PeaceSheep

2022.06.05