linux内存伙伴算法(三：分配页)
伙伴系统中用于分配页的函数如下：
alloc_pages(mask,order)分配2^order页并返回一个struct page的实例，表示分配的内存块的起始页。alloc_page(mask)是前者在order=0情况下的简化形式，只分配一页。
get_zeroed_page(mask)分配一页并返回一个page实例，页对应的内存填充0(所有其他函数分配之后的内容是未定义的)。
__get_free_pages(mask,order)和__get_free_page(mask)的工作方式与上述函数相同，但返回分配内存块的虚拟地址，而不是page实例。
get_dma_pages(gfp_mask,order)用来获得适用于DMA的页。
在空闲内存无法满足请求以至于分配失败的情况下，所有上述函数都返回空指针(alloc_pages和alloc_page)或者0(get_zeroed_page、__get_free_pages和__get_free_page)。因此内核在各次分配之后必须检查返回的结果。这种惯例与设计得很好的用户层应用程序没有什么不同，但在内核中忽略检查将会导致严重得多的故障。
前述所有函数中使用的mask参数的语义是什么？linux将内核划分为内存域，内核提供了所谓的内存域修饰符，来指定从哪个内存域分配所需的页。
主要的函数是alloc_pages_node。alloc_pages_node源代码的详细分析如下：gfp_mask是一些标志位，用来制定如何寻找空闲页框,order用来表示所需物理块的大小，从空闲链表中获取2^order页内存,在管理区链表zonelist中依次查找每个区，从中找到满足要求的区{const gfp_t wait = gfp_mask & __GFP_WAIT;//gfp_mask是申请内存时用到的控制字，这一句就是为了检测我们的控制字里面是否有__GPF_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);//如果在gfp_mask中设置了__GFP_WAIT位，表明内核可以阻塞当前进程，来等待空闲页面。在分配开始之前即阻塞，目的是为了等待其它进程释放更多的页面if (should_fail_alloc_page(gfp_mask, order))//通过简单算法在真正分配前检查分配是否会失败，避免进入真正的分配程序后浪费系统时间return NULL;restart:z = zonelist->zones; //zonelist是struct node中的一个成员，它表示系统内所有normal内存页区的连接链表,首先让z指向第一个管理区if (unlikely(*z == NULL)) {//如果发现头指针为空，即没有指向struct zone的有效指针，我们就直接返回错误/* * Happens if we have an empty zonelist as a result of * GFP_THISNODE being used on a memoryless node */return NULL;}page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,zonelist, ALLOC_WMARK_LOW|ALLOC_CPUSET);//get_page_from_freelist以指定的watermark来分配页面。每个zone struct中定义了三个watermark：pages_min, pages_low, pages_high，表示zone中应保持的空闲页面的阈值。get_page_from_freelist函数通过设置Alloc flags来选择watermark。if (page)//首先以pages_low watermark分配页面，如果分配成功，则跳转到got_pggoto got_pg;/* * GFP_THISNODE (meaning __GFP_THISNODE, __GFP_NORETRY and * __GFP_NOWARN set) should not cause reclaim since the subsystem * (f.e. slab) using GFP_THISNODE may choose to trigger reclaim * using a larger set of nodes after it has established that the * allowed per node queues are empty and that nodes are * over allocated. */if (NUMA_BUILD && (gfp_mask & GFP_THISNODE) == GFP_THISNODE)//如果pages_low watermark分配失败的话，检查gfp_mask，如果GFP_THISNODE标志被设置，表明不能重试，因此跳转到nopage，返回失败goto nopage;for (z = zonelist->zones; *z; z++)wakeup_kswapd(*z, order);//否则调用kswapd对zonelist中的所有zone进行页面回收，期待能将一些闲置页面交换到文件系统中/* * OK, we're below the kswapd watermark and have kicked background * reclaim. Now things get more complex, so set up alloc_flags according * to how we want to proceed. * * The caller may dip into page reserves a bit more if the caller * cannot run direct reclaim, or if the caller has realtime scheduling * policy or is asking for __GFP_HIGH memory. GFP_ATOMIC requests will * set both ALLOC_HARDER (!wait) and ALLOC_HIGH (__GFP_HIGH). */alloc_flags = ALLOC_WMARK_MIN;//设置alloc_flags的值，以page_min watermark来分配内存if ((unlikely(rt_task(p)) && !in_interrupt()) || !wait)//假若进程是非中断处理程序的实时进程，或者该进程不能被阻塞，那么这个时候，我要在最低阈值的标准的基础上，再次降低阈值alloc_flags |= ALLOC_HARDER;if (gfp_mask & __GFP_HIGH)//允许使用保留页面__GFP_HIGHalloc_flags |= ALLOC_HIGH;if (wait)alloc_flags |= ALLOC_CPUSET;/* * Go through the zonelist again. Let __GFP_HIGH and allocations * coming from realtime tasks go deeper into reserves. * * This is the last chance, in general, before the goto nopage. * Ignore cpuset if GFP_ATOMIC (!wait) rather than fail alloc. * See also cpuset_zone_allowed() comment in kernel/cpuset.c. */page = get_page_from_freelist(gfp_mask, order, zonelist, alloc_flags);//以指定的watermark来分配页面，详细讨论见下文if (page)//分配成功，就进入got_pggoto got_pg;/* This allocation should allow future memory freeing. */rebalance://上面的第二次分配失败if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE)))//如果当前进程允许本次申请的内存可以被释放，并且不处于软硬中断的状态，我们不顾忌必须保留最小空闲内存页，强行分配&& !in_interrupt()) {if (!(gfp_mask & __GFP_NOMEMALLOC)) {//如果gfp_mask设置不需要保留紧急内存区域，以不设watermark再次分配页面nofail_alloc:/* go through the zonelist yet again, ignoring mins */page = get_page_from_freelist(gfp_mask, order,zonelist, ALLOC_NO_WATERMARKS);//以不设watermark进行第三次分配if (page)//第三次分配成功goto got_pg;if (gfp_mask & __GFP_NOFAIL) {//第三次分配失败，如果gfp_mask设置了__GFP_NOFAIL，则不断重试，直到分配成功congestion_wait(WRITE, HZ/50);goto nofail_alloc;}}goto nopage;}/* Atomic allocations - we can't balance anything */if (!wait)//原子分配，不允许阻塞，则只能返回失败信号，分配失败goto nopage;cond_resched();//重新调度之后，试图释放一些不常用的页面/* We now go into synchronous reclaim */cpuset_memory_pressure_bump();//开始进行同步内存回收p->flags |= PF_MEMALLOC;//进程的标志位设置为PF_MEMALLOCreclaim_state.reclaimed_slab = 0;//对于不再活跃的SLAB也给回收掉p->reclaim_state = &reclaim_state;//改变进程回收的状态did_some_progress = try_to_free_pages(zonelist->zones, order, gfp_mask);//该函数选择最近不十分活跃的页，将其写到交换区，在物理内存中腾出空间p->reclaim_state = NULL;p->flags &= ~PF_MEMALLOC;cond_resched();if (order != 0)drain_all_local_pages();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)) {//如果内核可能执行影响VFS层的调用而又没有设置GFP_NORETRY，那么调用OOM killerif (!try_set_zone_oom(zonelist)) {schedule_timeout_uninterruptible(1);goto restart;}/* * Go through the zonelist yet one more time, keep * very high watermark here, this is only to catch * a parallel oom killing, we must fail if we're still * under heavy pressure. */page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,zonelist, ALLOC_WMARK_HIGH|ALLOC_CPUSET);if (page) {clear_zonelist_oom(zonelist);goto got_pg;}/* The OOM killer will not help higher order allocs so fail */if (order > PAGE_ALLOC_COSTLY_ORDER) {//杀死一个进程未必立即出现多余2^PAGE_ALLOC_CODTLY_ORDER页的连续内存区，因此如果当前要分配如此大的内存区，那么内核会饶恕所选择的进程，不执行杀死进程的任务，而是承认失败并跳转到nopageclear_zonelist_oom(zonelist);goto nopage;}out_of_memory(zonelist, gfp_mask, order);//选择一个内核认为犯有分配过多内存“罪行”的进程，并杀死该进程。这有很大几率腾出较多的空闲页，然后跳转到标号restart，重试分配内存的操作clear_zonelist_oom(zonelist);goto restart;}/* * Don't let big-order allocations loop unless the caller explicitly * requests that. Wait for some write requests to complete then retry. * * In this implementation, __GFP_REPEAT means __GFP_NOFAIL for order * <= 3, but that may not be true in other implementations. *///如果设置了__GFP_NORETRY，或内核不允许可能影响VFS层的操作do_retry = 0;if (!(gfp_mask & __GFP_NORETRY)) {//没有设置__GFP_NORETRYif ((order <= PAGE_ALLOC_COSTLY_ORDER) ||(gfp_mask & __GFP_REPEAT))//如果分配长度小于2^PAGE_ALLOC_COSTLY_ORDER或设置了__GFP_REPEAT，则内核进入无限循环do_retry = 1;if (gfp_mask & __GFP_NOFAIL)//如果设置了不允许分配失败，内核也会进入无限循环do_retry = 1;}if (do_retry) {congestion_wait(WRITE, HZ/50);goto rebalance;}nopage:if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) {printk(KERN_WARNING "%s: page allocation failure."" order:%d, mode:0x%x\n",p->comm, order, gfp_mask);dump_stack();show_mem();}got_pg:return page;}get_page_from_freelist源代码的详细分析如下：
在允许的节点中，遍历满足要求的管理区do {/* * In NUMA, this could be a policy zonelist which contains * zones that may not be allowed by the current gfp_mask. * Check the zone is allowed by the current flags */if (unlikely(alloc_should_filter_zonelist(zonelist))) {//根据zonelist->zlcache_ptr来确定是否需要过滤掉此内存区链表，关于过滤的条件还不是很清楚，请指教if (highest_zoneidx == -1)highest_zoneidx = gfp_zone(gfp_mask);//gfp_zone用于指定分配内存的内存域if (zone_idx(*z) > highest_zoneidx)//首先考虑利用上面指定的内存域，对于一些分配代价高于指定内存域的内存域先不考虑continue;}if (NUMA_BUILD && zlc_active &&//是第一遍分配，在其他管理区中分配页面时需要考虑其页面是否充足!zlc_zone_worth_trying(zonelist, z, allowednodes))//该管理区页面不是很充足，考虑下一个管理区continue;zone = *z;if ((alloc_flags & ALLOC_CPUSET) &&!cpuset_zone_allowed_softwall(zone, gfp_mask))//当前分配标志不允许在该管理区中分配页面goto try_next_zone;if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {//分配时需要考虑watermarkunsigned long mark;//根据分配标志，确定使用哪一个watermarkif (alloc_flags & ALLOC_WMARK_MIN)mark = zone->pages_min;else if (alloc_flags & ALLOC_WMARK_LOW)mark = zone->pages_low;elsemark = zone->pages_high;if (!zone_watermark_ok(zone, order, mark, classzone_idx, alloc_flags)) {//该管理区的可用内存不可以满足本次分配的要求if (!zone_reclaim_mode ||//但不满足分配要求时，如果此内存域不能回收内存或者是回收不到可用内存时，就会跳转到this_zone_full !zone_reclaim(zone, gfp_mask, order))goto this_zone_full;}}page = buffered_rmqueue(zonelist, zone, order, gfp_mask);//调用伙伴系统的分配函数if (page)// 从伙伴系统分配成功，退出break;this_zone_full:if (NUMA_BUILD)zlc_mark_zone_full(zonelist, z);//标记该管理区空间不足，下次分配时将略过本管理区，避免浪费太多时间try_next_zone:if (NUMA_BUILD && !did_zlc_setup) {//当前管理区内存不足，需要加大在其他区中的分配力度/* we do zlc_setup after the first zone is tried */allowednodes = zlc_setup(zonelist, alloc_flags);zlc_active = 1;did_zlc_setup = 1;}} while (*(++z) != NULL);if (unlikely(NUMA_BUILD && page == NULL && zlc_active)) {// 第一遍分配不成功，则取消zlc_active，这样会尽量从其他节点中分配内存/* Disable zlc cache for second zonelist scan */zlc_active = 0;goto zonelist_scan;}return page;}关于上面一段代码中zlc_active的作用不明白，还望理解的人指点一下。
static struct page *buffered_rmqueue(struct zonelist *zonelist,struct zone *zone, int order, gfp_t gfp_flags){unsigned long flags;struct page *page;int cold = !!(gfp_flags & __GFP_COLD);//如果分配参数指定了__GFP_COLD标志，则设置cold标志，两次取反操作确保cold是0或者1，why？请指教int cpu;int migratetype = allocflags_to_migratetype(gfp_flags);//根据gfp_flags获得迁移类型again:cpu = get_cpu();//获取本CPUif (likely(order == 0)) {//分配单页，需要管理每CPU页面缓存struct per_cpu_pages *pcp;pcp = &zone_pcp(zone, cpu)->pcp[cold];//取得本CPU的页面缓存对象local_irq_save(flags);//这里需要关中断，因为内存回收过程可能发送核间中断，强制每个核从每CPU缓存中释放页面。而且中断处理函数也会分配单页。if (!pcp->count) {//缓存为空，需要扩大缓存的大小pcp->count = rmqueue_bulk(zone, 0,pcp->batch, &pcp->list, migratetype);//从伙伴系统中摘除一批页面到缓存中，补充的页面个数由每CPU缓存的batch字段指定if (unlikely(!pcp->count))//如果缓存仍然为空，那么说明伙伴系统中页面也没有了，分配失败goto failed;}/* Find a page of the appropriate migrate type */list_for_each_entry(page, &pcp->list, lru)//遍历每CPU缓存中的所有页，检查是否有指定类型的迁移类型的页可用if (page_private(page) == migratetype)break;/* Allocate more to the pcp list if necessary */if (unlikely(&page->lru == &pcp->list)) {pcp->count += rmqueue_bulk(zone, 0,pcp->batch, &pcp->list, migratetype);page = list_entry(pcp->list.next, struct page, lru);}list_del(&page->lru);//将页面从每CPU缓存链表中取出，并将每CPU缓存计数减1pcp->count--;} else {spin_lock_irqsave(&zone->lock, flags);page = __rmqueue(zone, order, migratetype);spin_unlock(&zone->lock);if (!page)goto failed;}__count_zone_vm_events(PGALLOC, zone, 1 << order);zone_statistics(zonelist, zone);local_irq_restore(flags);put_cpu();VM_BUG_ON(bad_range(zone, page));if (prep_new_page(page, order, gfp_flags))goto again;return page;failed:local_irq_restore(flags);put_cpu();return NULL;}我也知道有很多的细节都没有分析到位，但是我也没有办法，曾经想着把里面涉及到的每一个函数都分析到位，但是那样的话自己相当的痛苦，因为那样的结果就是很多天都没有办法前进一点，会让人相当的有挫败感，最后只能选择大概先都过一遍，因为自己是一个内核的初学者，而内核前后的关联又很大，也只能先过一遍，到后面我会重新回来看我写得博客，能增进一些分析就增进一些分析。如果您认为上面确实有很重要的地方我没有分析到，希望您指点。
