分区页框分配器子系统
管理区分配器：他的作用就在分配一个包含足够多的空闲页框的内存管理区。
函数分析：在restart段中，引用了关键函数zone_watermark_ok,其参数中有mark,对应z->pages_low.z指向当前管理区描述符。for循环的目的就是依次扫描各个zone。而在water函数中，min=mark;min的含义为除了被分配出去的页框外，内存管理区中至少还有min个空闲页框。而在watermark函数中，关键的if语句，就是判定所申请的是否符合大小，lowmem_reserve字段的是指明在处理内存不足的临界情况下每个管理区必须保留的页框数。如果当前不能满足时，进入循环，如果{zh1}分配失败，就返回1，成功返回0.除了被分配的页之外，这里在order至少为k的块中起码还有min/2^k个空闲页框，对于每个k,取值在1和分配的order之间，如果order大于0，那么在大小至少为2的块中起码还有min/2个空闲页框；如果order大于1，那么在大小至少为4的块中起码还有min/4个空闲页框……这就是for的用途。
if (free_pages <= min + z->lowmem_reserve[classzone_idx])
return 0;
for (o = 0; o < order; o++) {
/* At the next order, this order's pages become unavailable */
free_pages -= z->free_area[o].nr_free << o;
/* Require fewer higher order pages to be free */
min >>= 1;
if (free_pages <= min)
return 0;
}
继续扫描zone,直到找到合适为止，然后分配空闲页框。分配完毕后，返回page.如果循环结束，依然没有找到合适的，证明现在各个zone都没有多少空闲页框，那么就启动wakeup_kswapd函数来回首页框。然后在重复上个for,在回收函数已经将足够的页框回收后，分配新的空闲页框。此时的min阀值变成了pages_min.也就是当内存空闲不足时，会多次扫描各个zone区，不断的将min变小。这就是restart段中前三个for循环体的作用。
for (i = 0; (z = zones[i]) != NULL; i++) {
if (!zone_watermark_ok(z, order, z->pages_low,classzone_idx, 0, 0))
continue;
page = buffered_rmqueue(z, order, gfp_mask);
if (page)
goto got_pg;
}
for (i = 0; (z = zones[i]) != NULL; i++)
wakeup_kswapd(z, order);
for (i = 0; (z = zones[i]) != NULL; i++) {
if (!zone_watermark_ok(z, order, z->pages_min,classzone_idx, can_try_harder,gfp_mask & __GFP_HIGH))
continue;
page = buffered_rmqueue(z, order, gfp_mask);
if (page)
goto got_pg;
}
如果两次都没有扫描到合适的内存空闲，那么min就在下一次扫描中被忽视，因为每个zone都有保留一定的内存空闲，以便于在空闲不足时使用，通过前两次的扫描都没有合适的，那么现在空闲内存肯定不足，此时如果等待分配内存的进程是用于回收页框且不是中断处理程序或者可延迟函数时，那么就启动后备空闲分配给它。因为此时等待的请求进程是释放页框的，如果依然分配失败的话，那么返回错误信息。以上就是restart段的作用，也就是通过三次扫描，前两次是试图获得空闲，{zh1}一次是在没有空闲的时候来释放页框，如果依然没有办法的话，只能返回错误信息。
if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE))) && !in_interrupt()) {
for (i = 0; (z = zones[i]) != NULL; i++) {
page = buffered_rmqueue(z, order, gfp_mask);
if (page)
goto got_pg;
}
goto nopage;
而rebalance的作用就在于无法解决是，先阻断进程，然后启用进程，然后试图回收一部分页框，然后继续返回restart段。如果还不行，那么就要强行杀死一个进程。具体会在回首页框部分阐述。
伙伴系统算法：此算法是为了解决大块连续的页框分配，这是一个内存管理上的问题，称为：外碎片（external fragmentation）。解决思路就是用链表来记录现有的空闲页框块。而连续页框的个数也分为了1,2,4,8,16,32,64,128,256,512,1024几种，以适应不同请求大小的需要，同样大小的页框块各自成为链表，而结构free_area中的元素free_list就是双向链表的表头。在有请求时，找到适合大小的块给与分配，如果没有寻找更大的块，因为下一个块一定是比上一个块大一倍的，所以分配后，赋予的部分，也就是和上个块相等的部分将接入上个块的循环链表中。以此类推，总之超过需要请求的部分，会以以下各个块的大小重新加入空闲页框链表，直到{zh1}一级，也就是1为止。释放时，也是同样的道理。而与此配合的还有另外一个元素lru,它是指向相邻元素的指针，是包含于struct page中的一个元素。另外一个重要元素就是mem_map数组，其中用来存放所有的页描述符，而页描述符中保存着的是页框的状态信息，类型为page.内存管理区中元素struct page* zone_mem_map指向管理区的{dy}个页描述符的指针。
struct free_area {
struct list_head free_list;
//连续的页框块的循环链表的表头，此链表集中了大小为2^k页的空闲块对应的页描述符（包含每个空闲起始页框的页描述符）。
unsigned long nr_free;
};
申请一个块的函数：两个参数，前一个zone是管理区描述符地址，后一个是请求空闲页块大小的对数。函数中关键的是for循环体。其中MAX_ORDER就是空闲块的{zd0}对数值，也就是1,2……1024的对数11.current_order=order,此时以需要的大小为循环起点，链表的起点是zone->free_area，管理区描述符地址是当前zone管理区的起始地址，后面的current_order就是位移。找到最适合当前大小的循环链表的节点，area的类型就是free_area,以上就是这句area=zone->free_area+current_order语句的意思，接下来，如果当前节点上没有空闲块，就继续到下一个节点寻找，if语句的作用就在于此。list_empty(&area->free_list),括号中的元素正是每个循环链表的开头。如果有合适的，就将其的页描述符地址返回，也就是page=……的语句。然后从链表中摘除相应元素。同时nr_free也减一。
如果要修改使其符合特定需求的时候，比如所设计的系统所分配的块都是小块时，最容易直观的方式就是修改free_area空闲块链表个数，也就是1,2……1024进行调整。
static struct page *__rmqueue(struct zone *zone, unsigned int order)
{
struct free_area * area;
unsigned int current_order;
struct page *page;
for (current_order = order; current_order < MAX_ORDER; ++current_order) {
area = zone->free_area + current_order;
if (list_empty(&area->free_list))
continue;
page = list_entry(area->free_list.next, struct page, lru);
list_del(&page->lru);
rmv_page_order(page);
area->nr_free--;
zone->free_pages -= 1UL << order;
return expand(zone, page, order, current_order, area);
}
return NULL;
}
释放一个块的函数：释放的目的是要将块插回到循环链表中，以便于下次使用，那么首先要注意的就是这个块不能丢，其中的元素page就是释放块中所包含的{dy}个页框描述符的地址。同时要知道所释放的块的大小是多少，以便于正确插入队列，元素order就是释放块大小的对数。而函数中的base的作用在语句page_idx=page-base中得到了体现，base中包含的是管理区中（zone）的{dy}个页框，减完后得到的是当前块内的{dy}个页框下标。
函数思想：关键点在于while循环体。首先从参数中得到释放块的大小，然后得到当前块的{dy}个页框下标。通过order_size来改变zone->free_pages的计数，因为要释放，所以区中的空闲页框数量也会相应增加。然后进入循环体，同样是以MAX_ORDER来作为循环次数。且以order为起点来开始循环，就是从参数中导入的参数大小来寻找伙伴。area元素就是前面谈到的空闲块循环链表元素。再看page_idx^(1 << order),等价于page_idx+order或者page_idx-order.从这句中可以得到两个信息，首先是buddy_idx元素的含义是块下标，是page_idx块的伙伴！之所以这句可以起到这个作用，就在于在伙伴系统中，内存是按照顺序来分配的，只有这样的分配方式才可以用加减释放块大小的方式找到相应大小的伙伴！而buddy再加上块的起始地址，则可以得到伙伴块的{dy}个页描述符。
在page_is_buddy函数中，首先判断buddy是否描述了大小为order_size的空闲页框块的{dy}个页。他的{dy}个页必须空闲，属于动态内存。而private字段必须存放将要被释放块的order.如果此时order与伙伴的order相等，则跳出循环，接入对应的free_area数组中。此时整个过程完成。如果不等于当前伙伴的大小，则继续循环，在下一个order的伙伴中插入。
static inline void __free_pages_bulk (struct page *page, struct page *base,struct zone *zone, unsigned int order)
{
unsigned long page_idx;
struct page *coalesced;
int order_size = 1 << order;
page_idx = page - base;
zone->free_pages += order_size;
while (order < MAX_ORDER-1) {
struct free_area *area;
struct page *buddy;
int buddy_idx;
buddy_idx = (page_idx ^ (1 << order));
buddy = base + buddy_idx;
if (!page_is_buddy(buddy, order))
break;
/* Move the buddy up one level. */
list_del(&buddy->lru);
area = zone->free_area + order;
area->nr_free--;
rmv_page_order(buddy);
page_idx &= buddy_idx;
order++;
}
coalesced = base + page_idx;
set_page_order(coalesced, order);
list_add(&coalesced->lru, &zone->free_area[order].free_list);
zone->free_area[order].nr_free++;
}
每cpu页框高速缓存:算法目的是当cpu执行对单页框申请或者释放的时候，如果依然使用伙伴系统的话，一是浪费资源；二是效率低下；针对这种情况内存管理区定义了一个每cpu页框高速缓存。而cpu高速缓存也分为冷热两种。冷高速缓存是当dma操作填充时，不用经过cpu时的选择。而热高速缓存是硬件高速缓存，映射的是刚被访问的“热”页框单元。表示它们的数据结构是per_cpu_pageset,per_cpu_pages,还有zone结构中pageset字段。三个之间发生关联用以描述这个部分的结构和链接。通过per_cpu_pageset结构体中的字段pcp字段就可以看到，数组元素为2，一个定义为冷，一个定义为热，对应到同类型的per_cpu_pages结构体，此结构中的各位都是表明当前状态的。
通过percpu_pages的各个字段，可以直观的看到高速缓存到底如何运作，有用于记录当前页框个数的，以便于用来判断是否越界，是否需要补充，也有用来表示每次请求时需要添加和删除的页框个数，count,batch字段都是用来判断高速缓存是否被限制在一定范围内。而list链表则是关键的，这个字段的出现，清晰的表明了高速缓存中的页框描述符也是以链表性质来描述的。通过以上几点，申请和删除函数的三分之一已经清晰明了。
struct per_cpu_pages {
int count; /* number of pages in the list 高速缓存中的页框个数*/
int low; /* low watermark, refill needed高速缓存的下界buffered_rmqueue函数中将看到count小于此项时就需要补充*/
int high; /* high watermark, emptying needed高速缓存上界，表示高速缓存用尽 */
int batch; /* chunk size for buddy add/remove高速缓存中将要添加或者删去的页框个数 */
struct list_head list; /* the list of pages 高速缓存中包含的页框描述符链表*/
};
struct per_cpu_pageset {
struct per_cpu_pages pcp[2]; /* 0: hot. 1: cold */
}
除了这几个结构外，还有就是页框分配标志，也就是在申请函数中的参数gfp_flags.这个参数表示的是请求页框的标志。在zone中，因为分为三个区：normal,highmem,dma,其中就有两个修饰标志，分别是__GFP_DMA,__GFP_HIGH之所以没有normal的标志，在于此区间是{zx0}优先级，而其他两个只有在标志明确表明时，才拥有优先满足内存分配请求。几个优先级别是这样的，如果表明dma，则只能从dma区间获得需要页，如果high没有被标示，则要从normal,dma的顺序来从内存管理区获得页框，如果high被置位，则要从high,normal,dma这样的顺序获得需要页框。
因为高速缓存是分冷热的，所以gfp_flag的标示中也有__GFP_COLD，表示所请求的页框可能为冷的，也就是从dma中的获得，不经过cpu.
内存是拥有保留内存池的，__GFP_HIGH，此标示的目的就是允许访问保留的内存池。
在请求页框分配的时候，进程请求后，内核可能对于内存的分配操作并不成功。此时将产生问题，也会产生几种情况，如一次内存分配不成功后就不再重试（__GFP_NORETRY），于此对应的是内核会反复尝试分配直到成功为止（__GFP_REPEAT）。这两个比较重要，此外还有两个：__GFP_NOWARN（一次内存分配失败不产生警告），__GFP_NOFAIL与__GFP_REPEAT相同。
内核子系统中，除了分页分框子系统外，还有slab。对应于此，gfp_flags也有相应标示：__GFP_NO_GROW,slab分配器不允许增大slab高速缓存。
除此外，还有几项：
__GFP_WAIT（允许内核对等待空闲页框的当前进程进行阻塞）
__GFP_IO（允许内核在低端内存页上执行i/o传输以释放页框）
__GFP_FS（如果清零，则不允许内核执行依赖于文件系统的操作）
__GFP_COMP（属于扩展页的页框）
__GFP_ZERO（任何返回的页框必须被填满0）
#define __GFP_WAIT 0x10 /* Can wait and reschedule? */
#define __GFP_HIGH 0x20 /* Should access emergency pools? */
#define __GFP_IO 0x40 /* Can start physical IO? */
#define __GFP_FS 0x80 /* Can call down to low-level FS? */
#define __GFP_COLD 0x100 /* Cache-cold page required */
#define __GFP_NOWARN 0x200 /* Suppress page allocation failure warning */
#define __GFP_REPEAT 0x400 /* Retry the allocation. Might fail */
#define __GFP_NOFAIL 0x800 /* Retry for ever. Cannot fail */
#define __GFP_NORETRY 0x1000 /* Do not retry. Might fail */
#define __GFP_NO_GROW 0x2000 /* Slab internal usage */
#define __GFP_COMP 0x4000 /* Add compound page metadata */
#define __GFP_ZERO 0x8000 /* Return zeroed page on success */
#define GFP_LEVEL_MASK (__GFP_WAIT|__GFP_HIGH|__GFP_IO|__GFP_FS| \
__GFP_COLD|__GFP_NOWARN|__GFP_REPEAT| \
__GFP_NOFAIL|__GFP_NORETRY|__GFP_NO_GROW|__GFP_COMP)
#define GFP_ATOMIC (__GFP_HIGH)
#define GFP_NOIO (__GFP_WAIT)
#define GFP_NOFS (__GFP_WAIT | __GFP_IO)
#define GFP_KERNEL (__GFP_WAIT | __GFP_IO | __GFP_FS)
#define GFP_USER (__GFP_WAIT | __GFP_IO | __GFP_FS)
#define GFP_HIGHUSER (__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_HIGHMEM)
#define GFP_DMA __GFP_DMA
以上几个就是页框请求的组合。
函数buffered_rmqueue作用：在指定的内存管理区中分配页框，使用每cpu页框高速缓存来处理单一页框请求。通过以上的铺垫，对于此函数就很好理解了，先通过gfp_flags标志判定是冷还是热，然后进入{dy}选择判断，因为是单页框的释放或者申请，故order==0,也就是1的对数，然后通过zone中的字段pageset中的pcp，几个结构完成串联，得到当前高速缓存的状态，然后判断，如果count<=low,也就是小于等于下界的时候，就需要从伙伴系统中分配一个单一页框，函数rmqueue_bulk,看参数提供的zone,就是管理区指针，0就是对数，batch,就是当前需要的，以及pcp->list就是申请后该插入哪个链表。然后此时已经分配到了后，count自然不会再如前面的判断，此时就可以将这个插入链表，并且返回页框的页描述符指针，然后删除指向下一个伙伴的指针lru.
如果此时还没有达到内存分配要求，则进入下一个判断，此时直接再从伙伴系统中调用一个页框。如果完成分配后，对页框进行初始化，比如函数中的__GFP_ZERO,清零，或者属于扩展页时。
static struct page *buffered_rmqueue(struct zone *zone, int order, int gfp_flags)
{
unsigned long flags;
struct page *page = NULL;
int cold = !!(gfp_flags & __GFP_COLD);
if (order == 0) {
struct per_cpu_pages *pcp;
pcp = &zone->pageset[get_cpu()].pcp[cold];
local_irq_save(flags);
if (pcp->count <= pcp->low)
pcp->count += rmqueue_bulk(zone, 0,pcp->batch, &pcp->list);
if (pcp->count) {
page = list_entry(pcp->list.next, struct page, lru);
list_del(&page->lru);
pcp->count--;
}
local_irq_restore(flags);
put_cpu();
}
if (page == NULL) {
spin_lock_irqsave(&zone->lock, flags);
page = __rmqueue(zone, order);
spin_unlock_irqrestore(&zone->lock, flags);
}
if (page != NULL) {
BUG_ON(bad_range(zone, page));
mod_page_state_zone(zone, pgalloc, 1 << order);
prep_new_page(page, order);
if (gfp_flags & __GFP_ZERO) prep_zero_page(page, order, gfp_flags);
if (order && (gfp_flags & __GFP_COMP)) prep_compound_page(page, order);
}
return page;
}
而对应的释放高速缓存页框函数free_hot_cold_page，则是通过两个对应冷热不同情况的函数引用来间接完成的，比如在两个函数中分别只有一行语句：free_hot_cold_page(page, 0);free_hot_cold_page(page, 1);函数参数的0与1，对应的正是冷热不同情况。完成释放操作的主要在函数后面一部分，与申请函数思想大同小异。
static void fastcall free_hot_cold_page(struct page *page, int cold)
{
struct zone *zone = page_zone(page);
struct per_cpu_pages *pcp;
unsigned long flags;
arch_free_page(page, 0);
kernel_map_pages(page, 1, 0);
inc_page_state(pgfree);
if (PageAnon(page))
page->mapping = NULL;
free_pages_check(__FUNCTION__, page);
pcp = &zone->pageset[get_cpu()].pcp[cold];
local_irq_save(flags);
if (pcp->count >= pcp->high)
pcp->count -= free_pages_bulk(zone, pcp->batch, &pcp->list, 0);
list_add(&page->lru, &pcp->list);
pcp->count++;
local_irq_restore(flags);
put_cpu();
}
