Linux 物理内存 管理 的理解

唉，我真笨，终于明白了Linux物理内存的模式。
总是想，物理内存还得内存管，一旦要分配新数据结构，就成了鸡蛋问题。
心得如下：

首先，假设我们有4G+的物理内存。

Linux下物理内存用page结构管理。理解后抽象出的简化page结构如下：

struct page page {
struct page * next;   /* 下一个“页内存区”*/
long used;   /* 是否被使用 */
}; /* sizeof(page) = 8 bytes */

--------------------
在系统初始化的时候，在内核空间中空出(4G/4K)*8bytes=8M的空间出来，如，1M~9M的区域，将这个区域全部置零。实质上这等价于着我们在内存中分配了2^20个page结构。

我们不能用类似于：

page_ptr = (page*)malloc(sizeof(page)*1M);

来分配，为什么？---“鸡蛋问题”，malloc函数背后用来做记录的数据的空间哪里来？谁管理？

--------------------
如果使用Buddy Allocator来管理物理页，我们可以采取的管理方式如下：
用一个

struct page * FreeList[32]; /* 可以管理的最大空闲区域为4G */

来记录所有内存空洞（1page, 2pages, 4pages, 8pages, etc）
假设我们真的有4G的物理内存，那么FreeList[31] = &page[0]; 这意味着page[0]之后的2^32 bytes空间是空闲的。
FreeList[0:30] = NULL;

在假设我们做了如下两个操作：
get_pages(1); /* 分配1页 */
get_pages(5); /* 分配5页 */

看看我们的allocator怎么处理，从这个处理过程中也就可以看出物理页的管理方式了。Go！
首先请求分配1页，FreeList[0] = NULL； 表示正好没有合适的1页，那么allocator就会沿着FreeList往上找，最后找到了FreeList[31]，这么有米！就拿它开刀了！--- 我们要从2^32字节中切出2^12字节来~~
2^32 = 2^31 + 2^ 30 + 2^ 29 + …… + 2^13 + 2^12 + 2^12
切出 2^12 字节后，FreeList[31]再也没有资格指向page[0]后的4G内存了，它完了！被一个小小的4K页面给干掉了！
此时,FreeList[31] <- NULL，表示没有连续的2^32 字节的内存区域了。但是，FreeList[31]的灭亡，却带来了无数小集团的诞生：
2^31，2^ 30， 2^ 29， …… ，2^13 ，2^12等， 我们可以采取这样的方式来排列这些小集团

|\\\\\| 1page |        2pages      |             …               |                 512K pages               |

表示被分配出去的2^12字节。然后，分别让 FreeList[0] = &page[1], FreeList[1] = &page[2], FreeList[3]=&page[4]，…… page[i]中的i需要计算一下，按照从大到小的块来切，不难算出。

下面执行get_pages(5)，5页内存需要到指示8页内存的的FreeList[3]中找，将那8页中的高5页切出来分配给用户，剩余的3页 可以分为1页+2页，1页可以链入FreeList[0]中，2页可以链入FreeList[1]中。最初我对这个很迷惑：这么一链，岂不是又要分配新的 指针之类的结构么？其实不用！不妨在去看看page结构的定义~:) 明白了吧？其中的next项就是应付这个的.大体的操作方式如下：

/* 将page[5]之后的两页链入FreeList[1]的链表头 */
page[5].next = FreeList[1];
FreeList[1] = &page[5]; /* 5,6两页 */

/* 将page[4]这一页页链入FreeList[0]的链表头 */
page[4].next = FreeList[0];
FreeList[0] = &page[4]; /* 第4页 */

有了这样一种方式，就算最后的内存零散为了一页一页的（第奇数页空闲，第偶数页已被分配）也不怕了：所有零散页都被链入到FreeList[0]所指示的链表中了 *_*