[内核内存] 伙伴系统5---buffered_rmqueue(页面分配核心函数)

╰+攻爆jí腚メ 2023-01-14 01:51 171阅读 0赞

### 文章目录 ###

*  buffered\_rmqueue
 *   *  buffered\_rmqueue流程图
     *  buffered\_rmqueue函数源码分析
     *  单页分配（pcp）
     *   *  rmqueue\_bulk
     *  多页分配（order>0）
     *   *  快速分配\_\_rmqueue\_smallest
         *   *  辅助函数expand
         *  慢速分配\_\_rmqueue\_fallback
         *   *  \_\_rmqueue\_fallback源码分析
             *   *  全局pageblock\_order变量
                 *  通过迁移类型分组来实现反碎片化（转：http://blog.csdn.net/vanbreaker/article/details/7626670 ）

# buffered\_rmqueue #

buffered\_rmqueue是伙伴系统中在指定zone区域进行页面分配的核心函数，前面介绍的get\_page\_from\_freelist函数就调用了该函在选定的zone区域中进行内存页面分配工作。

## buffered\_rmqueue流程图 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA5MjMwODM_size_16_color_FFFFFF_t_70_pic_center]

具体执行步骤描述如下:

1.  如果oder为0表示分配单页，这个时候就从pcplist中分配（冷热页）
2.  如果设置了ALLOC\_HARDER表示一次高优先级的分配，就从free\_list\[MIGRATE\_HIGHATOMIC\]的链表中分配。MIGRATE\_HIGHATOMIC类型的页用于一些紧急情况下的内存分配。
3.  前面情况都未满足最后就进行普通的分配，尝试从指定迁移类型migratetype的链表中去分配，若指定的迁移类型中没有就从其他的迁移内心链表中去偷取(查找后备类型fallbacks\[MIGRATE\_TYPES\]\[4\]`，并将查找到的页面移动到所需的`MIGRATE\`类型中，移动成功后，重新尝试分配)。

## buffered\_rmqueue函数源码分析 ##

//mm/page_alloc.c
    /* *@preferred_zone:初始时分配页面指定的zone *@zone:该函数指定分配页面的zone *@order:内存块页的个数2^order *@gfp_flags *@alloc_flags:指定分配标志 *@migratetype：指定迁移类型 */
    static inline
    struct page *buffered_rmqueue(struct zone *preferred_zone,
    			struct zone *zone, unsigned int order,
    			gfp_t gfp_flags, unsigned int alloc_flags,
    			int migratetype)
    { 
    	unsigned long flags;
    	struct page *page;
    	//_GFP_COLD行为标志，分配器应该使用高速缓存中快要淘汰出去的页
    	bool cold = ((gfp_flags & __GFP_COLD) != 0);
        //如果order==0,分配单页,内存从pcplist链表中分配（冷热页）
    	if (likely(order == 0)) { 
    		struct per_cpu_pages *pcp;
    		struct list_head *list;
            /*禁止本地CPU中断，禁止前先保存中断状态： *这里需要关中断，因为内存回收过程可能发送核间中断，强制每个核从每CPU缓存中 *释放页面。而且中断处理函数也会分配单页。 */
    		local_lock_irqsave(pa_lock, flags);
    		do { 
    			//获取到cpu高速缓存页
    			pcp = &this_cpu_ptr(zone->pageset)->pcp;
    			//根据迁移类型获取高速缓存区的的freelist
    			list = &pcp->lists[migratetype];
    			//该链表为空，大概率上次获取的cpu高速缓存的迁移类型和这次不一致
    			if (list_empty(list)) { 
    				//从伙伴系统中获得页，然后向高速缓存中添加内存页
    				pcp->count += rmqueue_bulk(zone, 0,
    						pcp->batch, list,
    						migratetype, cold);
    				// 如果链表仍然为空，那么说明伙伴系统中页面也没有了，分配失败
    				if (unlikely(list_empty(list)))
    					goto failed;
    			}
    			//如果分配的页面不需要考虑硬件缓存(注意不是每CPU页面缓存)，则取出链表的最后一个节点返回给上层
    			if (cold)
    				page = list_last_entry(list, struct page, lru);
    			else
    			    //如果要考虑硬件缓存，则取出链表的第一个页面，这个页面是最近刚释放到每CPU缓存的，缓存热度更高
    				page = list_first_entry(list, struct page, lru);
                //将页面从每CPU缓存链表中取出，并将每CPU缓存计数减1
    			list_del(&page->lru);
    			pcp->count--;
    
    		} while (check_new_pcp(page));
    	} else { 
    		//分配的是多个页面，不需要考虑每CPU页面缓存，直接从系统中分配
    		/* * We most definitely don't want callers attempting to * allocate greater than order-1 page units with __GFP_NOFAIL. */
    		//__GFP_NOFAIL已经不推荐使用
    		WARN_ON_ONCE((gfp_flags & __GFP_NOFAIL) && (order > 1));
    		//关中断，并获得管理区的锁
    		local_spin_lock_irqsave(pa_lock, &zone->lock, flags);
    
    		do { 
    			page = NULL;
    			//分配标志中设置了ALLOC_HARDER，则从free_list[MIGRATE_HIGHATOMIC]的链表中进行页面分配
    			if (alloc_flags & ALLOC_HARDER) { 
    				page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);
    				if (page)
    					trace_mm_page_alloc_zone_locked(page, order, migratetype);
    			}
    			/*(1)前面条件都未分配到内存，先在该zone上按指定的迁移类型（migratetype）分配; *(2)如果在该zone上按指定的迁移类型分配内存失败后，则再选用其它备用的迁移列表进行分配方法如下: * 查找后备类型fallbacks[MIGRATE_TYPES][4]，并将查找到的页面移动到所需的MIGRATE类型 * 中，移动成功后，重新尝试分配 */
    			if (!page)
    				page = __rmqueue(zone, order, migratetype);
    		/*这里进行安全性检查，并进行一些善后工作。 * 如果页面标志破坏，返回的页面出现了问题，则返回试图分配其他页面。 * 内核会有这样的BUG存在吗?除了驱动或者模块有问题外? */
    		} while (page && check_new_pages(page, order));
    		if (!page) { 
    			spin_unlock(&zone->lock);
    			goto failed;
    		}
    		//已经分配了1 << order个页面，这里进行管理区空闲页面统计计数 
    		__mod_zone_freepage_state(zone, -(1 << order),
    					  get_pcppage_migratetype(page));
    		//先回收（打开）锁,待后面统计计数设置完毕后再开中断
    		spin_unlock(&zone->lock);
    	}
        //事件统计计数，debug（调试）用
    	__count_zid_vm_events(PGALLOC, page_zonenum(page), 1 << order);
    	zone_statistics(preferred_zone, zone, gfp_flags);
    	//恢复中断
    	local_unlock_irqrestore(pa_lock, flags);
    
    	VM_BUG_ON_PAGE(bad_range(zone, page), page);
    	return page;
    
    failed:
    	local_unlock_irqrestore(pa_lock, flags);
    	return NULL;
    }

## 单页分配（pcp） ##

当order==0时，伙伴系统主要从该zone的pcp链表中获取单页即进行冷热页分配，下面对相关概念进行简要介绍：

*  在Linux Kernel的物理内存管理的Buddy System中，引入了冷热页的概念。冷页表示该空闲页较大概率已经不在高速缓存中了(一般是指L2 Cache)，热页表示该空闲页仍然在高速缓存中。冷热页是针对于每CPU的；每个zone中都会针对于所有的CPU初始化一个冷热页的per-cpu-pageset.
 *  当内核分配一个物理页框时，有一些规范来约束我们是分配热页还是冷页。当页框是CPU使用的，则分配热页。当页框是DMA设备使用的，则分配冷页。因为DMA设备不会用到CPU高速缓存，所以没必要使用热页。
 *  Buddy System在给某个进程分配某个zone中空闲页的时候，首先需要用自旋锁锁住该zone,然后分配页。这样，如果多个CPU上的进程同时进行分配页，便会竞争。引入了per-cpu-set后，当多个CPU上的进程同时分配页的时候，竞争便不会发生，提高了效率。另外当释放单个页面时，空闲页面首先放回到per-cpu-pageset中，以减少zone中自旋锁的使用。当页面缓存中的页面数量超过阀值时，再将页面放回到伙伴系统中。
 *  使用每CPU冷热页还有一个好处是，能保证某个页一直黏在1个CPU上，这有助于提高Cache的命中率。
 *  在Linux中，对于UMA的架构，冷热页是在一条链表上进行管理。热页在前，冷页在后。CPU每释放一个order为0的页，如果per-cpu-pageset中的页数少于其指定的阈值，便会将释放的页插入到冷热页链表的开始处。这样，之前插入的热页便会随着其后热页源源不断的插入向后移动，其页由热变冷的几率便大大增加。

### rmqueue\_bulk ###

单页分配的具体流程参考代码注释，本小节主要介绍一下当分配冷热页时该zone的pcp中指定迁移类型的链表为空时，系统的处理方式。简单概括就是从伙伴系统中得到相关空闲页，然后填充到cpu的高速缓存中去（pcp中指定迁移类型的链表），最后再进行页分配。下面通过代码来对该过程进行详细的介绍。

内核通过rmqueue\_bulk辅助函数来对pcp中指定迁移类型的空链表进行填充。学习该代码前先了解pcp相关的几个重要结构体

冷热分配器

//include/linux/mmzone.h
    struct per_cpu_pageset { 
        struct per_cpu_pages pcp;
    #ifdef CONFIG_NUMA
        s8 expire;
    #endif
    #ifdef CONFIG_SMP
        s8 stat_threshold;
        s8 vm_stat_diff[NR_VM_ZONE_STAT_ITEMS];
    #endif
    };

cpu缓存页数组

//include/linux/mmzone.h
    struct per_cpu_pages { 
        int count;      /* number of pages in the list 列表中页数*/
        int high;       /* high watermark, emptying needed 列表页数的上限*/
        int batch;      /* chunk size for buddy add/remove 添加和删除页时，一次操作多少页。不是单页删除和填充的，而是以该单位页来操作的*/
     
        /* Lists of pages, one per migrate type stored on the pcp-lists */
        struct list_head lists[MIGRATE_PCPTYPES];//迁移类型的链表
    };

rmqueue\_bulk函数：从伙伴系统中获取到页，填充到cpu高速缓存中

//mm/page_alloc.c
     /* *(1)从伙伴系统中批量取出页面放到cpu的缓存中去，pcp每次添加和删除页都是 * 是定义好的（由struct per_cpu_pages的batch决定） *(2)分配的页存储在list中 *(3)函数返回值是此处成功从伙伴系统中取出的页(即是添加到pcp中的页数) *@zone： @order： *@count:从伙伴系统中获取页的最大个数 *@list: *@migratetype: @cold: */
    static int rmqueue_bulk(struct zone *zone, unsigned int order,
    			unsigned long count, struct list_head *list,
    			int migratetype, bool cold)
    { 
    	int i, alloced = 0;
        //获取管理区的自旋锁
    	spin_lock(&zone->lock);
    	//重复指定的次数从伙伴系统中取出空闲内存页，并插入list（单页处理）
    	for (i = 0; i < count; ++i) { 
    		//伙伴系统中取出对应的页
    		struct page *page = __rmqueue(zone, order, migratetype);
    		//伙伴系统中没有空闲页了退出
    		if (unlikely(page == NULL))
    			break;
    		//对取出的页进行检查，不满足条件跳过到下一次循环
    		//????该页的去向问题？？？？
    		if (unlikely(check_pcp_refill(page)))
    			continue;
    		//若是热页添加到表头，
    		if (likely(!cold))
    			list_add(&page->lru, list);
    		//否则添加到表尾
    		else
    			list_add_tail(&page->lru, list);
            //list->pre==NULL表示该元素在表头，list->next==NULL表示该元素在表尾
    		list = &page->lru;
    		//计算器（list中包含了几个页）
    		alloced++;
    		/* *若迁移类型是cma，修改伙伴系统cma迁移类型空闲页面的计数统计:更新zone的vm_stat *数组成员的NR_FREE_CMA_PAGES对应的数据和全局vm_zone_stat数组的NR_FREE_CMA_PAGES对应数据 */
    		if (is_migrate_cma(get_pcppage_migratetype(page)))
    			__mod_zone_page_state(zone, NR_FREE_CMA_PAGES,
    					      -(1 << order));
    	}
    
    	 /* *（1）减少管理区伙伴系统空闲页的计数:此处用的是i而不是alloced，alloced指的是添加到pcp中的页面数, * 在循环中由于check_pcp_refill的筛选，会导致某些页不会添加到pcp中但是仍然会从伙伴系统中删除 *（2）更新zone的vm_stat数组成员的NR_FREE_PAGES对应的数据和全局vm_zone_stat数组NR_FREE_PAGES * 数据 */
    	__mod_zone_page_state(zone, NR_FREE_PAGES, -(i << order));
    	spin_unlock(&zone->lock);
    	return alloced;
    }

rmqueue\_bulk函数中有一个重要函数 \_\_rmqueue后面会做详细介绍

最后对单页分配步骤做一个简单介绍:

1.  取出当前zone的pcp链表（&this\_cpu\_ptr(zone->pageset)->pcp），并根据迁移类型找到对应的list.
2.  判段list链表是否为空:
    
     (a)空: 从伙伴系统中获取特定个指定的页放入对应的pcp链表中，最后根据cold从list取出一个页
    
    (b) 非空: 直接从list中根据cold取出一个页（冷页表尾巴，热页表头）
3.  最后进通过\_\_mod\_zone\_page\_state分别对相关数据镜像统计计算

## 多页分配（order>0） ##

如果是order大于0是使用\_\_rmqueue进行分配分配流程：

1.  快速分配:通过\_\_rmqueue\_smallest函数在指定的migratetype类型链表上进行扫描分配内存，成功则返回page
2.  慢速分配:如果（1）分配失败，就调用\_\_rmqueue\_fallback尝试在其他类型的链表进行分配(注意:若指定分配类型是MIGRATE\_MOVABLE，当进入慢分配流程时要先调用\_\_rmqueue\_smallest在MIGRATE\_CMA类型列表上进行分配，成功返回；若再失败最后才调用\_\_rmqueue\_fallback函数进行分配).

//mm/page_alloc.c
    static struct page *__rmqueue(struct zone *zone, unsigned int order,
    				int migratetype)
    { 
    	struct page *page;
        //扫描migratetype指定的类型列表，找到合适的连续内存快
    	page = __rmqueue_smallest(zone, order, migratetype);
    	/* *上面分配失败，那么就调用__rmqueue_fallback尝试从其他类型的链表分配（MIGRATE_MOVABLE例外）： *(1)若指定的迁移类型是MIGRATE_MOVABLE，先调用 __rmqueue_smallest直接快速在MIGRATE_CMA类型列表 中去查找，成功直接返回，失败则调用__rmqueue_fallback在慢速的进行内存块分配 *(2)根据static int fallbacks[MIRGRATE_TYPES][MIGRATE_TYPES-1] 这个fallback数据来顺序查找 */
    
    	if (unlikely(!page)) { 
    		//
    		if (migratetype == MIGRATE_MOVABLE)
    			page = __rmqueue_cma_fallback(zone, order);
    
    		if (!page)
    			page = __rmqueue_fallback(zone, order, migratetype);
    	}
        //貌似是调试代码
    	trace_mm_page_alloc_zone_locked(page, order, migratetype);
    	return page;
    }

### 快速分配\_\_rmqueue\_smallest ###

直接从指定的迁移类型链表中进行内存分配:

1.  先从order阶的MIGRATE类型链表获取页块，找到直接返回，如果没找到从更大的order中查找直到MAX\_ORDER
2.  找到页块后，从伙伴系统对应链表中删除，最后调用expand函数进行伙伴系统链表网的缝补工作

//mm/page_alloc.c
    /* *遍历指定迁移类型的伙伴系统链表,从链表中移动最小数量的页面返回给调用者.这是伙伴系统的快速处理流程. *@zone: 在该管理区的伙伴系统中分配页面 *@order: 要分配的页面数量阶. *@migratetype: 在该迁移类型的链表中获取页面 */
    static inline
    struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
    						int migratetype)
    { 
    	unsigned int current_order;
    	struct free_area *area;
    	struct page *page;
    
    	/* Find a page of the appropriate size in the preferred list */
    	//从指定的阶到最大阶进行遍历,直到找到一个可以分配的链表
    	for (current_order = order; current_order < MAX_ORDER; ++current_order) { 
    		//找到该阶对应的空闲页面链表
    		area = &(zone->free_area[current_order]);
    		//搜索该阶的空闲链中是否有指定迁移类型的空闲页块，没有就搜索下一阶链表（page是链表的第一个元素） 
    		page = list_first_entry_or_null(&area->free_list[migratetype],
    							struct page, lru);
    		if (!page)
    			continue;
    		//将第一个元素从链表中摘除
    		list_del(&page->lru);
    		//rmv_page_order将页面的伙伴标志位清0,表示该页不再属于伙伴系统.同时将Private标志清0
    		rmv_page_order(page);
    		//当前阶的空闲计数减1
    		area->nr_free--;
            /* * 将大阶的页面块中未用的部分还回伙伴系统 * 如果当前阶没有可用的空闲页,而必须将高阶的空闲页面分割,则expand将高阶的页面分割后放回伙伴系统 * 如:我们将阶为4的页面分割,并向上层返回阶为2的页面,那么,我们需要将其中分割剩下的阶为3,2的页面放回 * 伙伴系统. */
    		expand(zone, page, order, current_order, area, migratetype);
    		//？？？貌似设置该空闲页块的迁移类型，保存在连续内存块的首页struct pag的index成员中
    		set_pcppage_migratetype(page, migratetype);
    		return page;
    	}
    
    	return NULL;
    }

#### 辅助函数expand ####

expand函数示意图

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA5MjMwODM_size_16_color_FFFFFF_t_70_pic_center 1]

expand()函数就是实现“切蛋糕”的功能。这里的参数high就是current\_order，通常是current\_order要比需求的order要大。每比较一次，area减一，相当于退了一级order，最后通过list\_add把剩下的内存块添加到低一级的空闲链表中。

//mm/page_alloc.c
    /* *将伙伴系指定zone同一迁移类型的链表中高阶的页面分割成低阶的页面，并将不需要使用的低阶页面 *放回对应阶的链表中. *@zone:所有的操作都在该zone上完成 *@page：高阶上分配得到的页块 *@low:要分配出去的低阶（有一半会保留） *@high:被分割的高阶 *@area:高阶页块所在的空闲页链表 *@migratetype 迁移类型 */
    static inline void expand(struct zone *zone, struct page *page,
    	int low, int high, struct free_area *area,
    	int migratetype)
    { 
    	unsigned long size = 1 << high;
    	/* *如果我们要将阶为4的页面组分割，分配出去的阶是2，则high=4，low=2 * (1)先需要将4阶的页块分配成两块3阶的页面 * (2)将两块3阶的页块中靠前的页块分配成两块2阶的页块，靠后的7阶页块放入伙伴系统7阶链表中 * (3)靠前的2阶页块返回用作伙伴系统分配使用，靠后的2阶页块放入伙伴系统6阶的链表中 * 其实最后非配出去的页块就是的首地址就是8阶页块的首地址 */
    	while (high > low) { 
    		//本次要放回伙伴系统的链表指针
    		area--;
    		//本次要放回伙伴系统的链表阶
    		high--;
    		/* *将当前阶的页块一分为二，前半块页块(page[0:size-2])继续用于切分或分配出去（分配出去size = 2^low），后 *半块页块(page[size:2*size-1])加入伙伴系统对应的free_list链表中 */
    		size >>= 1;
    		//检查要加入伙伴系统的页块首页是否在管理区的范围内
    		VM_BUG_ON_PAGE(bad_range(zone, &page[size]), &page[size]);
    
    		/* * Mark as guard pages (or page), that will allow to * merge back to allocator when buddy will be freed. * Corresponding page table entries will not be touched, * pages will stay not present in virtual address space */
    		if (set_page_guard(zone, &page[size], high, migratetype))
    			continue;
            //将后半块页块链入相应迁移类型的链表中
    		list_add(&page[size].lru, &area->free_list[migratetype]);
    		//该阶的空闲页面计数值加1
    		area->nr_free++;
    		//标记页面的阶
    		set_page_order(&page[size], high);
    	}
    }

### 慢速分配\_\_rmqueue\_fallback ###

执行到\_\_rmqueue\_fallback函数表示上面指定迁移类型从伙伴系统中分配内存失败（指定迁移类型空闲内存不足），所以要用备用迁移列表.

//mm/page_alloc.c
    static int fallbacks[MIGRATE_TYPES][4] = { 
    	[MIGRATE_UNMOVABLE]   = {  MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_TYPES },
    	[MIGRATE_RECLAIMABLE] = {  MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_TYPES },
    	[MIGRATE_MOVABLE]     = {  MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES },
    #ifdef CONFIG_CMA
    	[MIGRATE_CMA]         = {  MIGRATE_TYPES }, /* Never used */
    #endif
    #ifdef CONFIG_MEMORY_ISOLATION
    	[MIGRATE_ISOLATE]     = {  MIGRATE_TYPES }, /* Never used */
    #endif
    };

fallbacks的每一行对应一种迁移类型的备用迁移域的搜索顺序，比如当内核想要分配一个MIGRATE\_RECLAIMABLE迁移类型的内存时，若MIGRATE\_RECLAIMABLE对应的列表为空，则需要遍历fallback\[MIGRATE\_RECLAIMABLE\]数组。首先搜索MIGRATE\_UNMOVABLE对应的列表看是否有满足要求的内存块，若没有再搜索MIGRATE\_MOVABLE列表仍然没有就结束后补搜索，内存分配失败（MIGRATE\_TYPES 是遍历的结束标志）

#### \_\_rmqueue\_fallback源码分析 ####

伙伴系统分配页时，当迁移类型的内存不足时，系统就调用\_\_rmqueue\_fallback来进行后补分配:

//mm/page_alloc.c
    //尝试从start_migratetype备选迁移列表中搜索出一块大小为2^order个页的连续空闲页块
    static inline struct page *
    __rmqueue_fallback(struct zone *zone, unsigned int order, int start_migratetype)
    { 
    	struct free_area *area;
    	unsigned int current_order;
    	struct page *page;
    	int fallback_mt;
    	bool can_steal;
    
    	/* Find the largest possible block of pages in the other list */
    	/* *从最高阶搜索,这样可以尽量的将其他迁移列表中的大块分割,避免形成过多的碎片 *(和指定迁移类型的遍历不一样，为什么从最大阶遍历可以防止内存碎片化？？？) */
    	for (current_order = MAX_ORDER-1;
    				current_order >= order && current_order <= MAX_ORDER-1;
    				--current_order) { 
    		//获取当前阶的free_area
    		area = &(zone->free_area[current_order]);
    		 /* *在area内存区域中，遍历start_migratetype对应的备用数组，看是否能在备选迁移类型的列表中找到 *一块满足要求的内存块（阶大于等于current_order小于等于Max_ORDER-1） *(1)函数返回-1表示未找到满足要求的内存块 *(2)*can_steal为True表示需要先把该函数找到的后补空闲内存块先迁移到指定的迁移类型 * （start_migratetype）列表上去（避免碎片化） */
    		fallback_mt = find_suitable_fallback(area, current_order,
    				start_migratetype, false, &can_steal);
    		if (fallback_mt == -1)
    			continue;
    		//取满足要求备用列表的第一个元素（指向空内存块的首页虚拟地址）
    		page = list_first_entry(&area->free_list[fallback_mt],
    						struct page, lru);
    		//若能steal，先将page对应的空闲内存块迁移到start_migratetype链表上去
    		if (can_steal)
    			steal_suitable_fallback(zone, page, start_migratetype);
    
    		//从page处分配2^order个页的空闲内存出去（方式和多页分配一样）
    		area->nr_free--;
    		list_del(&page->lru);
    		rmv_page_order(page);
            //将大阶页面块中未用的页还回伙伴系统
    		expand(zone, page, order, current_order, area,
    					start_migratetype);
            //貌似设置该空闲页块的迁移类型，保存在连续内存块的首页struct pag的index成员中
    		set_pcppage_migratetype(page, start_migratetype);
    		//调试代码，跟踪页的迁移类型（原本想分配start_migratetype，内存不足从fallback_mt中steal）
    		trace_mm_page_alloc_extfrag(page, order, current_order,
    			start_migratetype, fallback_mt);
    
    		return page;
    	}
    
    	return NULL;
    }

函数中用find\_suitable\_fallback在备选列表中找出一块合适的空闲内存块。该函数参数中有一个中要参数&can\_steal，该参数若为True，表示伙伴系统需要先把该合适的空闲内存块先从其对应的后补迁移类型链表中移动到内存分配指定的迁移类型链表中去,最后按快速分配方式分配需要的空闲内存块。can\_steal值由下面函数确定:

static bool can_steal_fallback(unsigned int order, int start_mt)
    { 
        //分割的页面是一个大页面,则将整个页面全部迁移到指定迁移类型的链表中,这样可以避免过多的碎片
    	if (order >= pageblock_order)
    		return true;
    
    	if (order >= pageblock_order / 2 ||
    		start_mt == MIGRATE_RECLAIMABLE ||/*目前分配的是可回收页面,这类页面有突发的特点,将页面全部迁移 *到可回收链表中,可以避免将其他迁移链表分割成太多的碎片*/
    		start_mt == MIGRATE_UNMOVABLE ||
    		page_group_by_mobility_disabled) /* 指定了迁移策略,总是将被分割的页面迁移 */
    		return true;
    
    	return false;
    }

若find\_suitable\_fallback函数执行后返回的can\_steal为true伙伴系统会执行steal\_suitable\_fallback函数将find\_suitable\_fallback找到的内存块从后补迁移类型的区域迁移到指定迁移类型链表中去。

static void steal_suitable_fallback(struct zone *zone, struct page *page,
    							  int start_type)
    { 
    	unsigned int current_order = page_order(page);
    	int pages;
    
    	/* Take ownership for orders >= pageblock_order */
    	//当要迁移的页被内核认定为大页，内核会将将超出的部分的迁移类型设为指定迁移类型
    	if (current_order >= pageblock_order) { 
    		change_pageblock_range(page, current_order, start_type);
    		return;
    	}
    	/* *试图将当前页所处的最大内存(pageblock_order)块移到之前指定的迁移类型对应的链表中，只有空闲页才会移动， *所以真正可移动的页数pages可能小于pageblock_nr_pages */
    	pages = move_freepages_block(zone, page, start_type);
    	//如果可移动的页面数量较多,则将整个大内存块的迁移类型修改指定迁移类型
    	/* Claim the whole block if over half of it is free */
    	if (pages >= (1 << (pageblock_order-1)) ||
    			page_group_by_mobility_disabled)
    		set_pageblock_migratetype(page, start_type);
    }

最后函数将备用链表中的找到的大块内存分配出去，大块内存未使用完的内存仍然是同过expend返回给指定迁移类型的链表对应的order中去

##### 全局pageblock\_order变量 #####

若深入分析该函数源码我们会碰到两个全局变量**pageblock\_order**和**pageblock\_nr\_pages**

伙伴系统从一个zone进行内存分配，先会在指定迁移类型的的空闲链表中进行内存分配，若内存分配失败，则会按照fallbacks指定的次序从备用迁移类型的空闲链表中尝试内存分配.上述特性总是被编译进内核中，但是这种内核内存以移动性分组的特性只有在linux os中有足够的内存分配到每种迁移类型对应的空闲链表时才有意义.也就是伙伴系统中每个迁移类型的链表需要具有**适量**的内存，伙伴系统按迁移类型分组的机制才有意义.linux 内核是通过两个全局变量**pageblock\_order**和**pageblock\_nr\_pages**来对上面提到的**适量**进行判定.linux内核认为一个**pageblock\_order**阶的连续页块是一个**适量**大的内存，而,**pageblock\_nr\_pages**则表示该分配阶对应的页数。如果体系结构提供了**巨型页机制**,则**pageblock\_order**通常定义为**巨型页对应的分配阶**。两个变量定义在include/linux/pageblock-flag.h文件中。如果体系结构**不支持巨型页**, 则将其定义为**第二高的分配阶**, 即`MAX_ORDER - 1`

/* If huge pages are not used, group by MAX_ORDER_NR_PAGES */
    #define pageblock_order (MAX_ORDER-1)

如果各迁移类型的链表中没有一块适量大的连续内存,那么页面迁移不会提供任何好处,因此在可用内存太少时内核会关闭该特性.这是在build\_all\_zonelists函数中检查的,该函数用于初始化内存域列表.如果没有足够的内存可用, 则全局变量page\_group\_by\_mobility\_disabled设置为0, 否则设置为1.

##### 通过迁移类型分组来实现反碎片化（转：http://blog.csdn.net/vanbreaker/article/details/7626670 ） #####

其实linux在启动初期所有的内存都被标识为可以移动的，因此一开始其它迁移类型都没有属于自己的空闲内存。当系统要分配其它迁移类型的内存时，都是通过从可移动迁移类型的内存链表中夺取一部分过来，让系统根据实际迁移类型来进行内存的分配。\_\_rmqueue\_fallback函数就实现了上诉内存分配的功能。

\_\_rmqueue\_fallback在借用备用迁移类型链表中的空闲内存块来分配指定迁移类型的内存块时，做了一些细节处理来防止内存碎片化（比较认同下面说法，正确性有待求证）：

1.  从上面的源码可以看出\_\_rmqueue\_fallback函数在备用迁移类型中搜索内存块时，for循环优先遍历大的内存块，这和伙伴系统优先分配小块内存的原则相反。仔细琢磨会发现这样处理的原因是为了避免新迁移类型中引入碎片。假如A类型中内存不足向B类型求援，假设只从B中分配一块最适合的小块，那么过会儿又请求分配A类型内存，又得向B类型求援，这样来来回回从B类型中一点一点的分配内存将会导致B类型的内存四处都散布碎片，如果这些内存一直得不到释放……内核已经不敢想象了……B类型可能会因为A类型而引入的碎片导致其再也分配不出大的内存块了。出于这种原因，内核选择直接分配一块最大的内存块给A，你们爱怎么打怎么闹随便你们，反正都是在A类型中进行，只要不拖累我B类型就可以了
2.  当请求分配的内存比较大时或者最初的请求类型为可回收类型（有些系统不可移动类型页会算上）时，会表现得内存块的迁移会表现地更加积极，也就是将对应的最大内存块搬到最初的请求类型对应的链表中。这里判断一个比较大的内存类型的条件是用来和前面优先遍历大内存块的for循环相呼应的，也就是说假如得到的内存块是一个比较小的内存块，那就说明该内存类型自己也没有大块可分配的连续内存了，因此就不执行搬迁工作。而对于可回收类型的内存要执行搬迁是因为在一些时候，内核可能会非常频繁地申请小块可回收类型的内存。
3.  当搬迁的内存大小大于大块内存的一半时，将彻底将这块内存化为己有，也就是说将这片大块内存区对应的页类型标识位图区域标识成最初申请的内存类型

用<<深入Linux内核架构>>本小节内容作为总结，“实际上，在启动期间分配可移动内存区的情况较少，那么分配器有很高的几率分配长度最大的内存区，并将其从可移动列表转换到不可移动列表。由于分配的内存区长度是最大的，因此不会向可移动内存中引入碎片。总而言之，这种做法避免了启动期间内核分配的内存(经常在系统的整个运行时间都不释放)散布到物理内存各处，从而使其他类型的内存分配免受碎片的干扰，这也是页可移动性分组框架的最重要目标之一”

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA5MjMwODM_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/87d4eacaf3d24b49821c91eb2c001fd4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA5MjMwODM_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/54c5e756b49640d6976ad8a02b806697.png