linux内存管理--伙伴系统和内存分配器
3.1页框的管理
所有的页框描述符都存放在mem_map数组中。
3.1.1page数据结构
3.2伙伴系统
通常我们用alloc_pages(), alloc_page(), __get_free_pages(), __get_free_page(), get_zeroed_page() 来获取页框，前两个返回的是页描述符的地址，后面两个返回的是物理页的线性地址。高端内存的分配只能通过前两个分配函数，后面两个由于是线性地址，不可以直接使用。这四个函数接口最终都会调用到伙伴系统的相关接口进行内存的分配工作。
linux内核的伙伴算法最大限度的减少了内存的碎片，其实应该说成是尽自己最大的努力减少了内存的碎片。其思想就是将物理内存分成11个块链表，每个链表包含的是大小为1,2,4,8...512,1024的连续页框块。举例来说要分配256个连续页框，会先到块大小为256的链表中查找空闲块，若有直接返回，若没有，去大小为512的链表中进行查找，将512大小块分为两部分，一部分返回，一部分插入256大小的链表中，若512大小的链表中还没有，到1024大小的链表中查找，取出256大小的块，将剩下的512,256的块分别插入到各个链表中，内存释放的过程则是相反的。
在分配过程中由大块分解而成的小块中没有被分配的块将一直等着被分配的块被释放从而和其合并，合并的操作正是在页面释放的过程中，最终的结果就是相当与没有分解大块，伙伴系统一直在向这个结果收敛，这就是为何伙伴系统能避免碎片的原因。伙伴系统在分配和释放两个方向上执行分解和合并两个互逆的操作，如果一开始系统没有碎片，那么最终的碎片将最小化，因为互逆的操作将最大力度的抵消碎片的产生，这就是精髓了。
伙伴系统的算法主要使用了zone描述符中的zone_mem_map字段和free_area数组，zone_mem_map指向了内存管理区的物理页的起始地址，free_area则代表着我们上面提到的11个链表。
struct free_area {
struct list_headfree_list;//块链表头
unsigned long *map;//块分配的位图
};
struct free_area中的free_list字段是空闲内存块的链表头，空闲内存块通过内存描述符的lru字段链接成链表，一个大小为1024页框的内存块中，其第一个页框的private字段保存了对应的order即10，第一个页框也有一个标记位，表明是否是buddy的内存块。在页框被释放时用该字段判断是否可以和它的伙伴内存块合为更大的内存块。3.2.1内存块的分配
struct page * fastcall__alloc_pages(gfp_t gfp_mask, unsigned int order,struct zonelist *zonelist){const gfp_t wait = gfp_mask & __GFP_WAIT;struct zone **z;struct page *page;struct reclaim_state reclaim_state;struct task_struct *p = current;int do_retry;int alloc_flags;int did_some_progress;might_sleep_if(wait);restart://zonelist->zones代表了内存分配时使用内存管理区的顺序z = zonelist->zones; //一开始先以zone->page_low做为基准进行内存分配page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,zonelist, ALLOC_WMARK_LOW|ALLOC_CPUSET);//分配到页框，退出if (page)goto got_pg;//没有分配到页框， 唤醒kswapd进行内存回收do {wakeup_kswapd(*z, order);} while (*(++z));//调用kswapd进程回收内存后，进行第二次回收，页面基准值为zone->min_pages，alloc_flags = ALLOC_WMARK_MIN;//当前进程是实时进程且不在中断中或者进程不允许等待，内存分配会比较//紧迫，需要置ALLOC_HARDER标记进一步来缩小内存基准值if ((unlikely(rt_task(p)) && !in_interrupt()) || !wait)alloc_flags |= ALLOC_HARDER;//__GFP_HIGH标志着允许访问紧急内存池if (gfp_mask & __GFP_HIGH)alloc_flags |= ALLOC_HIGH;//通常GFP_ATOMIC是不允许进程休眠来等待内存释放的if (wait)alloc_flags |= ALLOC_CPUSET;//再次获取页面page = get_page_from_freelist(gfp_mask, order, zonelist, alloc_flags);//获取到了，OK，退出if (page)goto got_pg;//还是无法获取页面，系统内存肯定不足，在非中断和软中断的情况下，进行第三次扫描//PF_MEMALLOC标记的意思是不想让内存分配失败，可以动用紧急内存if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE)))&& !in_interrupt()) {//__GFP_NOMEMALLOC表明了不允许没有内存分配，进行第三次扫描，第三次扫描绘忽略阈值判断，//动用紧急内存if (!(gfp_mask & __GFP_NOMEMALLOC)) {nofail_alloc:/* go through the zonelist yet again, ignoring mins */page = get_page_from_freelist(gfp_mask, order,zonelist, ALLOC_NO_WATERMARKS);//分配到了页面，退出if (page)goto got_pg;//没有分配到页面，不允许失败if (gfp_mask & __GFP_NOFAIL) {blk_congestion_wait(WRITE, HZ/50);goto nofail_alloc;}}goto nopage;}//进程不允许睡眠等待，苦逼了，只能返回NULL了if (!wait)goto nopage;rebalance://检查是否有其它进程需要调度运行cond_resched();/* We now go into synchronous reclaim */cpuset_memory_pressure_bump();//给进程设定PF_MEMALLOC标记位p->flags |= PF_MEMALLOC;reclaim_state.reclaimed_slab = 0;p->reclaim_state = &reclaim_state;//调用内存回收函数进行内存回收did_some_progress = try_to_free_pages(zonelist->zones, gfp_mask);p->reclaim_state = NULL;p->flags &= ~PF_MEMALLOC;//内存回收过程可能耗时太多，检查是否有进程需要进行调度cond_resched();//如果内存回收的确回收到了一些页面if (likely(did_some_progress)) {//再次尝试回收页面page = get_page_from_freelist(gfp_mask, order,zonelist, alloc_flags);if (page)goto got_pg;} else if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {//该情况下页面回收并没有回收到任何页框，或许系统到了//危急的时刻了!!!杀死一个其他的进程，然后一切从头再来!page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,zonelist, ALLOC_WMARK_HIGH|ALLOC_CPUSET);if (page)goto got_pg;out_of_memory(zonelist, gfp_mask, order);goto restart;}do_retry = 0;//gfp_mask标记中GFP_NORETRY表明了是否允许再次扫描内存管理区if (!(gfp_mask & __GFP_NORETRY)) {//GFP_REPEAT,GFP_NOFAIL都要求反复对内存管理区进行扫描if ((order <= 3) || (gfp_mask & __GFP_REPEAT))do_retry = 1;if (gfp_mask & __GFP_NOFAIL)do_retry = 1;}//需要再次尝试内存分配的话，调用blk_congestion_wait()等待一会，if (do_retry) {blk_congestion_wait(WRITE, HZ/50);goto rebalance;}nopage:if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) {dump_stack();show_mem();}got_pg:return page;}3.3.2get_page_from_freelist在代码中到伙伴系统分配内存的代码实现实际在get_page_from_freelist（）中。static struct page *get_page_from_freelist(gfp_t gfp_mask, unsigned int order,struct zonelist *zonelist, int alloc_flags){struct zone **z = zonelist->zones;struct page *page = NULL;int classzone_idx = zone_idx(*z);do {if ((alloc_flags & ALLOC_CPUSET) &&!cpuset_zone_allowed(*z, gfp_mask))continue;if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {unsigned long mark;//alloc_flags决定了mark的大小，mark是衡量是否可以从该内存管理区分配页框的标准//用于下面的zone_watermark_okif (alloc_flags & ALLOC_WMARK_MIN)mark = (*z)->pages_min;else if (alloc_flags & ALLOC_WMARK_LOW)mark = (*z)->pages_low;elsemark = (*z)->pages_high;//zone中的剩余内存不能达到标准，需要回收内存if (!zone_watermark_ok(*z, order, mark, classzone_idx, alloc_flags))if (!zone_reclaim_mode || !zone_reclaim(*z, gfp_mask, order))continue;}//调用bufferd_rmqueue向伙伴系统申请内存页框page = buffered_rmqueue(zonelist, *z, order, gfp_mask);if (page) {break;}} while (*(++z) != NULL);return page;}3.3.3 zone_watermark_okint zone_watermark_ok(struct zone *z, int order, unsigned long mark, int classzone_idx, int alloc_flags){//基准值是mark，可以使zone->low,high,min中的任何一个值long min = mark, free_pages = z->free_pages - (1 << order) + 1;int o;//如果__GFP_WAIT被置位，通常ALLOC_HIGH被置位，将最小值减去1/2if (alloc_flags & ALLOC_HIGH)min -= min / 2;//如果__GFP_WAIT被置位，如果当前进程是一个实时进程并且已经在进程上下文中，已经完成了//内存分配，则alloc_flag中的ALLOC_HARDER被置位,min再减少1/4if (alloc_flags & ALLOC_HARDER)min -= min / 4; //空闲页面少于min 加上管理区的保留页面数if (free_pages <= min + z->lowmem_reserve[classzone_idx])return 0;//对于0-order个大小的页面空闲链表，对于每个链表，都//对于order为k的块至少有min/2(k)个页框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;}return 1;}
