内存管理（31）内存回收1

1.LRU类型

这么区分的主要原因是因为文件映射页面（page cache）总是容易被回收的，因为通常他们都不用被回写。而匿名页需要先交换到交换空间然后还要回写磁盘最后才能被回收。

2.LRU是如何实现页面老化的？

2.1.LRU的页面添加

//页面添加的核心代码块/** * list_add - add a new entry * @new: new entry to be added * @head: list head to add it after * * Insert a new entry after the specified head. * This is good for implementing stacks. */static inline void list_add(struct list_head *new, struct list_head *head){	__list_add(new, head, head->next);			//添加page到LRU的头部}static __always_inline void add_page_to_lru_list(struct page *page,				struct lruvec *lruvec, enum lru_list lru){	...	list_add(&page->lru, &lruvec->lists[lru]);			//添加page到LRU	__mod_zone_page_state(lruvec_zone(lruvec), NR_LRU_BASE + lru, nr_pages);}static void __pagevec_lru_add_fn(struct page *page, struct lruvec *lruvec,				 void *arg){	int file = page_is_file_cache(page);	int active = PageActive(page);	enum lru_list lru = page_lru(page);			//确定page应该添加到那种类型的LRU列表	VM_BUG_ON_PAGE(PageLRU(page), page);	SetPageLRU(page);	add_page_to_lru_list(page, lruvec, lru);			//添加page到LRU	update_page_reclaim_stat(lruvec, file, active);	trace_mm_lru_insertion(page, lru);}/* * Add the passed pages to the LRU, then drop the caller's refcount * on them.  Reinitialises the caller's pagevec. */void __pagevec_lru_add(struct pagevec *pvec){	pagevec_lru_move_fn(pvec, __pagevec_lru_add_fn, NULL);}#define PAGEVEC_SIZE	14static inline unsigned pagevec_space(struct pagevec *pvec){	return PAGEVEC_SIZE - pvec->nr;				//PVEC剩余空间}static void __lru_cache_add(struct page *page){	struct pagevec *pvec = &get_cpu_var(lru_add_pvec);	page_cache_get(page);				//引用+1	if (!pagevec_space(pvec))			//pvec是否有空间		__pagevec_lru_add(pvec);		//没有空间，把pvec中原有的page添加到LRU	pagevec_add(pvec, page);			//把page添加到pvec中	put_cpu_var(lru_add_pvec);}void lru_cache_add(struct page *page){	VM_BUG_ON_PAGE(PageActive(page) && PageUnevictable(page), page);	VM_BUG_ON_PAGE(PageLRU(page), page);	__lru_cache_add(page);}

2.2.LRU中的page摘除

/*LRU上页面的摘除*/#define lru_to_page(_head) (list_entry((_head)->prev, struct page, lru))page = lru_to_page(page_list);			//从head->prev也就是LRU的链表尾选pagelist_del(&page->lru);			//从LRU链表上摘除page

3.回收算法：LRU经典算法

系统是通过往LRU链表头加page,现存的页面往后移动。当系统内存短缺时，系统从LRU链表尾换出page，当系统需要时，这些换出的page又会被添加到LRU链表的头部。如下图所示：

LRU经典算法示意图

显然这个页面有缺陷，因为它没有考虑页面是否是经常使用，有些经常使用的页面到了一定时候它一定会到达LRU的队列尾部，无论它是否被使用都会被换出。为了解决这个问题就有了经典算法的改进版，第二次机会算法。

4.回收算法：第二次机会法

第二次机会法在置换页面跟经典算法一样也是置换不活跃LRU链表尾部的页面。不过它给每个页面增加了一个标志位L_PTE_YONG，当这个状态位被置位它将不会被换出，被给予第二次机会并清0该状态位。直到所有页面被淘汰过或者给予了2次机会，这期间如果该页有被访问过标志位又会被置位并又给予2次机会并再次清除标志位，否则就会被淘汰。如果循环往复，经常被访问的页面就会被一直保留下来。

4.1.page_check_references函数

//2次机会算法的关键代码static enum page_references page_check_references(struct page *page,						  struct scan_control *sc){	int referenced_ptes, referenced_page;	unsigned long vm_flags;	referenced_ptes = page_referenced(page, 1, sc->target_mem_cgroup,					  &vm_flags);			//引用PTE的访问数	referenced_page = TestClearPageReferenced(page);		//返回PG_referenced位值，并清0	/*	 * Mlock lost the isolation race with us.  Let try_to_unmap()	 * move the page to the unevictable list.	 */	if (vm_flags & VM_LOCKED)		return PAGEREF_RECLAIM;	if (referenced_ptes) {				//page被访问过?		if (PageSwapBacked(page))		//匿名页？			return PAGEREF_ACTIVATE;	//放回活跃链表		/*		 * All mapped pages start out with page table		 * references from the instantiating fault, so we need		 * to look twice if a mapped file page is used more		 * than once.		 *		 * Mark it and spare it for another trip around the		 * inactive list.  Another page table reference will		 * lead to its activation.		 *		 * Note: the mark is set for activated pages as well		 * so that recently deactivated but used pages are		 * quickly recovered.		 */		SetPageReferenced(page);					//为什么PG_referenced置位，请见下面说明    //referenced_page==1？或者引用PTE的访问数>1? 对于第一次访问的page其referenced_page=0		if (referenced_page || referenced_ptes > 1)				return PAGEREF_ACTIVATE;		//放入活跃LRU队列		/*		 * Activate file-backed executable pages after first usage.		 */		if (vm_flags & VM_EXEC)			//可执行页面？			return PAGEREF_ACTIVATE;	//放入活跃LRU队列		return PAGEREF_KEEP;			//保持在不活跃LRU队列	}	/* Reclaim if clean, defer dirty pages to writeback */	if (referenced_page && !PageSwapBacked(page))		return PAGEREF_RECLAIM_CLEAN;	return PAGEREF_RECLAIM;			//放入准备回收的队列}

4.2.page_referenced函数实现

/** * page_referenced - test if the page was referenced * @page: the page to test * @is_locked: caller holds lock on the page * @memcg: target memory cgroup * @vm_flags: collect encountered vma->vm_flags who actually referenced the page * * Quick test_and_clear_referenced for all mappings to a page, * returns the number of ptes which referenced the page. */int page_referenced(struct page *page,		    int is_locked,		    struct mem_cgroup *memcg,		    unsigned long *vm_flags){	int ret;	int we_locked = 0;    struct rmap_walk_control rwc = {		.rmap_one = page_referenced_one,		.arg = (void *)&pra,		.anon_lock = page_lock_anon_vma_read,	};...	ret = rmap_walk(page, &rwc);	//遍历所有映射该页面的PTE，通过反向映射得到引用PTE的访问数量	*vm_flags = pra.vm_flags;	return pra.referenced;}t//遍历到的每一个PTE都会调用page_referenced_one函数static int page_referenced_one(struct page *page, struct vm_area_struct *vma,			unsigned long address, void *arg){	struct mm_struct *mm = vma->vm_mm;	spinlock_t *ptl;	int referenced = 0;	struct page_referenced_arg *pra = arg;...				if (ptep_clear_flush_young_notify(vma, address, pte)) {			/*			 * Don't treat a reference through a sequentially read			 * mapping as such.  If the page has been used in			 * another mapping, we will catch it; if this other			 * mapping is already gone, the unmap path will have			 * set PG_referenced or activated the page.			 */			if (likely(!(vma->vm_flags & VM_SEQ_READ)))				referenced++;		}		pte_unmap_unlock(pte, ptl);	}	if (referenced) {		pra->referenced++;		pra->vm_flags |= vma->vm_flags;	}	pra->mapcount--;	if (!pra->mapcount)		return SWAP_SUCCESS; /* To break the loop */	return SWAP_AGAIN;}