[内核内存] 伙伴系统7---__free_pages(页块释放)

绝地灬酷狼 2023-01-14 12:59 189阅读 0赞

### 文章目录 ###

*  \_\_free\_pages
 *   *  \_\_free\_pages\_ok多页释放函数
     *   *  free\_one\_page函数
         *   *  \_\_free\_one\_page函数
             *   *  \_\_find\_buddy\_index
                 *  if (max\_order < MAX\_ORDER)引入目的
                 *  释放页加入伙伴系统实例演示
 *  参考

# \_\_free\_pages #

linux内核中伙伴系统内存释放函数间的调用关系可用下图来表述  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA5MjMwODM_size_16_color_FFFFFF_t_70_pic_center]

代码

//释放一个页，传入参数是页框首地址的虚拟地址
    #define free_page(addr) free_pages((addr), 0)
    
    //释放2^order大小的页块,传入参数是页框首地址的虚拟地址
    void free_pages(unsigned long addr, unsigned int order)
    { 
    	if (addr != 0) { 
    		VM_BUG_ON(!virt_addr_valid((void *)addr));
    		__free_pages(virt_to_page((void *)addr), order);
    	}
    }
    
    //释放一个页，传入参数是指向该页对应的虚拟地址
    #define __free_page(page) __free_pages((page), 0)
    
    //释放2^order大小的页块，传入参数是指向该内存块首页对应的struct page结构体的指针
    void __free_pages(struct page *page, unsigned int order)
    { 
    	//判断if the page has no users？检查页块是否被进程使用，就是struct page的_refcount是否为0
    	if (put_page_testzero(page)) { 
            //若果是单页放回CPU高速缓存，若是多页内存块，放回伙伴系统空闲链表
    		if (order == 0)
    		    //设置为热页
    			free_hot_cold_page(page, false);
    		else
    			__free_pages_ok(page, order);
    	}
    }

据上可以看出,伙伴系统内存释放函数的核心函数是\_\_free\_pages,该函数的执行流程比较简单如下所示:

1.  检查该页块是否被其它进程使用(通过struct page的\_refcount成员是否为0判断),有则释放失败
2.  检查是否为单页框
    
    1.  是: 则将该页放到CPU单页框的高速缓存链表中。若此时pcp链表中页框数量超过列表页数的上限（pcp->high）,则把pcp列表中的pcp->batch个页框放回到伙伴系统中
    2.  否: 则将页块释放到伙伴系统对应的空闲链表中，释放后会对伙伴系统空闲链表做一次检查，看新合入的页块是否能和其它页块合并成更大页块，直到不能合并为止。比如：释放一块order=2的页块，会检查该页块能否在伙伴系统中找到一个合适的页块合并成order=3的页块。若能合并两个页框，然后接着检查看能否再找到一块合适的order=3的页块与新合并的页框再次合并成一块order=4的页块…直到不能合并为止。

示意图：

![img][]

**ps**: 懒得画图上图直接从网上拷贝下来，单页释放时它直接将MIGRATE\_CMA和MIGRATE\_HIGHATOMIC类型的页在MIGRATE\_UNMOVABLE类型的pcp list中，而本文则是将其放置在MIGRATE\_MOVABLE类型的pcp list上

\#\#1.1 free\_hot\_cold\_page单页释放函数

源码分析：

void free_hot_cold_page(struct page *page, bool cold)
    { 
    	//获取page对应页所在zone
    	struct zone *zone = page_zone(page);
    	struct per_cpu_pages *pcp;
    	unsigned long flags;
    	//求出该页对应的pfn物理页框号
    	unsigned long pfn = page_to_pfn(page);
    	int migratetype;
        //释放前检查该页是否满足释放条件,并对页相关数据和成员释放前的准备操作
    	if (!free_pcp_prepare(page))
    		return;
        //获取页块所在的pageblock的内存块的迁移类型
    	migratetype = get_pfnblock_migratetype(page, pfn);
        /* *设置页框迁移类型为所在pageblock的迁移类型，因为在页框使用过程中，这段pageblock可能移动到了其他类型: * page->index = migratetype */
    	set_pcppage_migratetype(page, migratetype);
    	//禁止irq中断
    	local_lock_irqsave(pa_lock, flags);
    	//统计cpu上页面释放的次数
    	__count_vm_event(PGFREE);
    
    	/* *根据页所在页块(pageblock)的迁移类型来判断该页最终因该释放的位置: (1)MIGRATE_UNMOVABLE, MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE三个按原来的类型释放 (2)MIGRATE_CMA, MIGRATE_HIGHATOMIC类型释放到MIGRATE_MOVABLE类型中 (3)MIGRATE_ISOLATE类型释放到伙伴系统order=0的对应迁移类型的空闲链表中 */
    	if (migratetype >= MIGRATE_PCPTYPES) { 
    		if (unlikely(is_migrate_isolate(migratetype))) { 
    			free_one_page(zone, page, pfn, 0, migratetype);
    			goto out;
    		}
    		migratetype = MIGRATE_MOVABLE;
    	}
        //获取当前cpu的pcp页链表
    	pcp = &this_cpu_ptr(zone->pageset)->pcp;
    	/* *hot页加入到pcp list头部，优先分配，冷页加入到pcp list尾部： *热页冷页的意思就是当一个页被释放时，默认设置为热页，因为该页可能有些地址的数据还处于映射到CPUcache的情 *况，当该CPU上有进程申请单个页框时，优先把这些热页分配出去，这样能提高cache命中率，提高效率。而实现方法也 *很简单，如果是热页，则把它加入到CPU页框高速缓存链表的链表头，如果是冷页，则加入到链表尾 */	
    	if (!cold)
    		list_add(&page->lru, &pcp->lists[migratetype]);
    	else
    		//
    		list_add_tail(&page->lru, &pcp->lists[migratetype]);
    	//pcp list空闲页+1
    	pcp->count++;
    	//若当前pcp list中的页块数量大于设置的最高值，则将pcp->patch数量的页框放回伙伴系统中
    	if (pcp->count >= pcp->high) { 
    		unsigned long batch = READ_ONCE(pcp->batch);
    		LIST_HEAD(dst);
    		//将pcp中要释放的patch个页隔离在dst链表中，批量添加到伙伴系统对应的链表中（减少锁竞争）
    		isolate_pcp_pages(batch, pcp, &dst);
    		pcp->count -= batch;
    		local_unlock_irqrestore(pa_lock, flags);
            //批量将隔离的页释放到伙伴系统对应迁移类型的0阶链表中
    		free_pcppages_bulk(zone, batch, &dst);
    		return;
    	}
    
    out:
    	local_unlock_irqrestore(pa_lock, flags);
    }

free\_pcppages\_bulk

函数功能:将页面缓存中的页面释放一部分到伙伴系统中

static void free_pcppages_bulk(struct zone *zone, int count,
    			       struct list_head *list)
    { 
    	unsigned long nr_scanned;
    	bool isolated_pageblocks;
    	unsigned long flags;
        /* * 虽然管理区可以按照CPU节点分类，但是也可以跨CPU节点进行内存分配， 因此这里需要用自旋锁保护管理区使用每 * CPU缓存的目的，也是为了减少使用这把锁。 */ 
    	spin_lock_irqsave(&zone->lock, flags);
    	isolated_pageblocks = has_isolate_pageblock(zone);
    	/* *pages_scanned代表最后一次内存紧张以来，页面回收过程已经扫描的页数。 目前正在释放内存，将此清0，待回收过 *程随后回收时重新计数 */
    	nr_scanned = node_page_state(zone->zone_pgdat, NR_PAGES_SCANNED);
    	if (nr_scanned)
    		__mod_node_page_state(zone->zone_pgdat, NR_PAGES_SCANNED, -nr_scanned);
    
    	while (!list_empty(list)) { 
    		struct page *page;
    		int mt;	/* migratetype of the to-be-freed page */
            //通过pcp->list找到第一个lru，再通过lru成员找到对应的struct page
    		page = list_first_entry(list, struct page, lru);
    		/* must delete as __free_one_page list manipulates */
    		//lru取出后，pcp->list链表就不再指向它了，就要从链表里面移除
    		list_del(&page->lru);
    
    		mt = get_pcppage_migratetype(page);
    		/* MIGRATE_ISOLATE page should not go to pcplists */
    		VM_BUG_ON_PAGE(is_migrate_isolate(mt), page);
    		/* Pageblock could have been isolated meanwhile */
    		if (unlikely(isolated_pageblocks))
    			mt = get_pageblock_migratetype(page);
    
    		if (bulkfree_pcp_prepare(page))
    			continue;
    		//核心函数，将page对应的页添加到伙伴系统中
    		__free_one_page(page, page_to_pfn(page), zone, 0, mt);
    		trace_mm_page_pcpu_drain(page, 0, mt);
    		count--;
    	}
    	WARN_ON(count != 0);
    	spin_unlock_irqrestore(&zone->lock, flags);
    }

因为在页面回收时是将要回收的页面插入到双链表的表头，而从上述函数中可以看出，在将页面切换出高速缓存的时候，也是从链表头按顺序获取的，因此整个切换策略就是后进先出，即最后进入高速缓存的先切换出去

## \_\_free\_pages\_ok多页释放函数 ##

static void __free_pages_ok(struct page *page, unsigned int order)
    { 
    	unsigned long flags;
    	int migratetype;
    	unsigned long pfn = page_to_pfn(page);
        /*对将释放的内存块中的对每个页面进行检查，看这些页面中是否存在不能释放的页面，页会对要释放的页块中页进行相关数 *据的初始化操作 */
    	if (!free_pages_prepare(page, order, true))
    		return;
        //获取页块所在的pageblock的内存块的迁移类型
    	migratetype = get_pfnblock_migratetype(page, pfn);
        //禁止irq中断
    	local_lock_irqsave(pa_lock, flags);
        //统计当前cpu上一共释放的页框数
    	__count_vm_events(PGFREE, 1 << order);
        //连续页框释放核心函数
    	free_one_page(page_zone(page), page, pfn, order, migratetype);
    	local_unlock_irqrestore(pa_lock, flags);
    }

需要注意，无论在释放单页框还是连续页框时，在释放时都会获取此页所在的pageblock的类型，pageblock大小为大页的大小或者2^MAX\_ORDER-1的大小，表明这段大小的内存都为一种迁移类型(MIGRATE\_MOVABALE,MIGRATE\_RECLAIMABLE等)，当释放时，都会获取页所在的pageblock的类型，然后把此页设置为与pageblock一致的类型，因为有种情况是：比如一个pageblock为MIGRATE\_MOVABLE类型，并且有部分页已经被使用(这些正在被使用的页都为MIGRATE\_MOVABLE)，然后MIGRATE\_RECLAIMABLE类型的页不足，需要从MIGRATE\_MOVABLE这里获取这个pageblock到MIGRATE\_RECLAIMABLE类型中，这个pageblock的类型就被修改成了MIGRATE\_RECLAIMABLE，这样就造成了正在使用的页的类型会与pageblock的类型不一致。在多个连续页框释放的时候也会遇到这种情况，所以在\_\_free\_pages\_ok()函数也会在释放页框的时候校对pageblock的类型并进行更改（释放前页的迁移类型与pageblock迁移类型一致）。页的类型保存在页描述page->index中

### free\_one\_page函数 ###

static void free_one_page(struct zone *zone,
    				struct page *page, unsigned long pfn,
    				unsigned int order,
    				int migratetype)
    { 
    	unsigned long nr_scanned;
    	unsigned long flags;
    	//给释放内存块所在zone区域上锁
    	spin_lock_irqsave(&zone->lock, flags);
    	//数据更新
    	nr_scanned = node_page_state(zone->zone_pgdat, NR_PAGES_SCANNED);
    	if (nr_scanned)
    		__mod_node_page_state(zone->zone_pgdat, NR_PAGES_SCANNED, -nr_scanned);
        //内存隔离使用
    	if (unlikely(has_isolate_pageblock(zone) ||
    		is_migrate_isolate(migratetype))) { 
    		migratetype = get_pfnblock_migratetype(page, pfn);
    	}
    	//释放以page为首页，大小为2^order个页的连续内存块，这些释放的页块迁移类型为上面获得的migratetype
    	__free_one_page(page, pfn, zone, order, migratetype);
    	//对应zone区域解锁
    	spin_unlock_irqrestore(&zone->lock, flags);
    }

#### \_\_free\_one\_page函数 ####

当内核释放一个物理页块后，该函数试图将在伙伴系统中找到一个与之对应的伙伴块将他们合并，得到一个大一阶的内存块;如果还能合并一个更大一阶的内存块，那么继续进行合并,获得更高阶的内存块;上诉该过程会重复执行，直至所有可能的伙伴对都已经合并,并将改变尽可能向上传播或者内存块的order达到了规定的最大阶为止；将最终获得的内存块添加到伙伴系统对应的空闲链表中。具体的代码实现细节如下所示:

static inline void __free_one_page(struct page *page,
    		unsigned long pfn,
    		struct zone *zone, unsigned int order,
    		int migratetype)
    { 
    	//page_idx用于保存页块中第一个页框的下标，该下表针对zone管理区，不是node
    	unsigned long page_idx;
    	unsigned long combined_idx;
    	unsigned long uninitialized_var(buddy_idx);
    	struct page *buddy;
    	unsigned int max_order;
    
    	max_order = min_t(unsigned int, MAX_ORDER, pageblock_order + 1);
    
    	VM_BUG_ON(!zone_is_initialized(zone));
    	VM_BUG_ON_PAGE(page->flags & PAGE_FLAGS_CHECK_AT_PREP, page);
    
    	VM_BUG_ON(migratetype == -1);
    	if (likely(!is_migrate_isolate(migratetype)))
    		__mod_zone_freepage_state(zone, 1 << order, migratetype);
        //获取该页在页块中的索引
    	page_idx = pfn & ((1 << MAX_ORDER) - 1);
        //若释放的页不是所释放页框的第一个页，则说明参数有误
    	VM_BUG_ON_PAGE(page_idx & ((1 << order) - 1), page);
    	//检验页块是否有效，检查是否有空洞，页块中的页面是否都在同一个zone中
    	VM_BUG_ON_PAGE(bad_range(zone, page), page);
    
    continue_merging:
        /* *释放页块以后，当前页块可能与前后的空闲页块组成更大的空闲页面。存在的话就将空闲页块从伙伴系统中 *取出来进行合并。循环上述操作，直到无法从伙伴系统找出合适空闲页块与当前页块进行合并或者 *order<max_order-1为止。最后退出循环后将最终的页块添加到伙伴系统对应的空闲链表（order,migratetype都要对 *应） */
    	while (order < max_order - 1) { 
    		//找到与当前页块属于同一个阶的伙伴页块首地址的物理页框号（限定了范围，只截取了pfn低位）
    		buddy_idx = __find_buddy_index(page_idx, order);
    		//通过对应关系计算出buddy_idx对应物理页的struct page指针（计算伙伴页块首页的页地址）
    		buddy = page + (buddy_idx - page_idx);
    		/* *判断释放页块和伙伴页块是否能进行合并操作，主要做一下判断： * (a) the buddy is not in a hole && * (b) the buddy is in the buddy system && * (c) a page and its buddy have the same order && * (d) a page and its buddy are in the same zone. */
    		if (!page_is_buddy(page, buddy, order))
    			goto done_merging;
    		/* * Our buddy is free or it is CONFIG_DEBUG_PAGEALLOC guard page, * merge with it and move up one order. */
    		/*页面调试功能，页面被释放时是整个的从内核地址空间中移除的。该选项显著地降低了速度，但它也能迅速指出特 *定类型的内存崩溃错误，需要配置CONFIG_DEBUG_PAGEALLOC */
    		if (page_is_guard(buddy)) { 
    			clear_page_guard(zone, buddy, order, migratetype);
    		} else { 
    			//能够合并，则将伙伴页块从伙伴系统中摘除
    			list_del(&buddy->lru);
    			//减少该zone当前阶中的空闲页计数
    			zone->free_area[order].nr_free--;
    			//清除伙伴页的伙伴标志，将该页块用于合并
    			rmv_page_order(buddy);
    		}
    		//合并后新页块的起始页的物理页框号（限定了范围，只截取了pfn低位）
    		combined_idx = buddy_idx & page_idx;
    		//起始页的struct page指针
    		page = page + (combined_idx - page_idx);
    		page_idx = combined_idx;
    		order++;
    	}
        /* *该if判断实现逻辑很有意思需要细细品才能了解内核的用意:当order>=pageblock_order&&order<MAX_ORDER *时，内核不想将isolate迁移类型的大块内存块和非isolate迁移类型的大块内存进行合并。而其它条件下，若伙伴系 *统中还存在能够合并的空闲内存块，还是按照while循环的处理方式进行内存块合并操作。 */
    	if (max_order < MAX_ORDER) { 
    		/* If we are here, it means order is >= pageblock_order. * We want to prevent merge between freepages on isolate * pageblock and normal pageblock. Without this, pageblock * isolation could cause incorrect freepage or CMA accounting. * * We don't want to hit this code for the more frequent * low-order merging. */
    		if (unlikely(has_isolate_pageblock(zone))) { 
    			int buddy_mt;
    
    			buddy_idx = __find_buddy_index(page_idx, order);
    			buddy = page + (buddy_idx - page_idx);
    			buddy_mt = get_pageblock_migratetype(buddy);
    
    			if (migratetype != buddy_mt
    					&& (is_migrate_isolate(migratetype) ||
    						is_migrate_isolate(buddy_mt)))
    				goto done_merging;
    		}
    		max_order++;
    		goto continue_merging;
    	}
    
    done_merging:
    	//标记了释放的连续page已经和之后的连续页形成了一个2的order次方的连续页框块
    	set_page_order(page, order);
    
        /* *如果合并后将要放入伙伴系统的内存块A的阶不是最大阶，这里内核先对其伙伴块进行一个检查，如果检查到伙伴页是 *空闲的，且满足与A合并的要求，则A的伙伴页可能即将释放，释放完全后就能够与A合并得到一个更大的空闲内存块。为 *了防止A内存块放入伙伴系统后很快就被分配出去，不能立即将释放的伙伴块合并成一个更大的内存块于是将A添加到伙伴 *系统对应空闲列表的末尾（保证伙伴系统具有尽可能多的大块内存块，缓解内存碎片化） */
    	if ((order < MAX_ORDER-2) && pfn_valid_within(page_to_pfn(buddy))) { 
    		struct page *higher_page, *higher_buddy;
    		combined_idx = buddy_idx & page_idx;
    		higher_page = page + (combined_idx - page_idx);
    		buddy_idx = __find_buddy_index(combined_idx, order + 1);
    		higher_buddy = higher_page + (buddy_idx - combined_idx);
    		//更高阶的页面是空闲的，属于伙伴系统 
    		if (page_is_buddy(higher_page, higher_buddy, order + 1)) { 
    			//将当前页面合并到空闲链表的最后，尽量避免将它分配出去
    			list_add_tail(&page->lru,
    				&zone->free_area[order].free_list[migratetype]);
    			goto out;
    		}
    	}
    	//将内存块为MAX_ORDER-1阶的内存块，添加到伙伴系统对应链表的表头
    	list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
    out:
        //伙伴系统对应空闲链表中页块数量加1
    	zone->free_area[order].nr_free++;
    }

##### \_\_find\_buddy\_index #####

\_page\_find\_buddy()用来找到是释放页块块的伙伴块

__find_buddy_index(unsigned long page_idx,unsigned int order)
    { 
           return page_idx ^ (1 << order);
    }

根据linux的管理策略以及伙伴系统的定义，伙伴系统中每个内存页块的第一个页帧号用来标志该页，因此对于order阶的两个伙伴，它们只有1<<order这个比特位是不同的，这样，只需要将该比特与取反即可，而根据异或的定义，一个比特和0异或还是本身，一个比特和1异或刚好可以取反。因此可以通过上述代码快速找到释放页块在伙伴系统中的伙伴块。

##### if (max\_order < MAX\_ORDER)引入目的 #####

该函数中while循环只是对order<max\_order-1的内存块进行了合并操作，但是当oder>=max\_order-1时，若伙伴系统中仍然存在满足要求的空闲内存块，难道内核就不进行合并操作了吗？？？，其实不然，if (max\_order < MAX\_ORDER)里就是内存对大块内存进行的合并操作的。

*  linux内核将order大于pageblock\_order的内存块认为是大块内存，函数中while循环先对小块内存进行合并，小块内存合并过程中，系统是没有在意两个合并内存块的迁移类型,只要能找到合适的伙伴块就进行合并。
 *  函数while循环退出后，若max\_order < MAX\_ORDER。在伙伴系统中可能还存在合适的大块空闲内存块能够和while循环中获得的page\_idx内存块进行合并。但是linux内核并不乐意将大块的isolate内存块和非isolate内存块进行合并，因为这样可能会导致incorrect free page or CMA accounting。所以函数在进行大块内存合并时，对两个合并块的迁移类型做了如下的判断:
    
        if (migratetype != buddy_mt
        					&& (is_migrate_isolate(migratetype) ||
        						is_migrate_isolate(buddy_mt)))
    
     *  若两个合并的大块内存中**有且只有一个**是MIGRATE\_ISOLATE迁移类型的内存块。则结束合并过程，直接goto done\_merging。将当前的合并块加入到伙伴系统对应的空闲链表中去
     *  若两个合并的大块内存中**不是只有一个**内存块是MIGRATE\_ISOLATE。则函数执行如下代码:
        
            max_order++;
            		goto continue_merging;
        
        跳转到上面的while循环继续对两个大块内存块进行合并操作。

##### 释放页加入伙伴系统实例演示 #####

假设一个将要释放的页order=0，page\_idx=10:

*  计算它伙伴块的page\_idx:10^(1<<0)=11
 *  通过page\_is\_buddy函数判断两块内存能否进行合并（判断page\_idx=11的内存块是否在伙伴系统中，order是否为0，且是否和page\_idx=10的内存块在一个zone中）
    
     *  不能合并就直接将其添加到伙伴系统对应的空闲链表上
     *  能合并，则将两块内存进行合并，得到一块order=1的内存块，起始页的偏移为10&~(1<<0)=10
 *  假设上面能进行合并.继续循环上述的操作找到它的伙伴页块page\_idx:10^(1<<1)=8，然后判断伙伴块能否进行合并。若能合并，新的内存块的起始页的page\_idx:10&~(1<<1)=8,order=2.如此推到下去，直到新内存块找不到伙伴块或者order超过规定的最大值max\_order - 1，为止。最后将最终获得的内存块添加到伙伴系统对应的链表中去。可以通过下面图来分析伙伴系统释放页的整个过程:

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

# 参考 #

https://blog.csdn.net/iteye\_4515/article/details/82407488

https://www.cnblogs.com/savionyin/p/8310737.html

https://www.cnblogs.com/LoyenWang/p/11666939.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA5MjMwODM_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/d434d9fe9a864eae8a754d4ac898311f.png
[img]: /images/20221022/e2ed0821c17a4e599a167cd7682f03a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA5MjMwODM_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/64ac71387825469191cf42b5718669d7.png