[linux内存管理] 第037篇 LRU链表详解

struct lruvec {
 ///LRU链表数组，每个内存节点都有5种类型LRU链表
	struct list_head		lists[NR_LRU_LISTS];
	/* per lruvec lru_lock for memcg */
	spinlock_t			lru_lock;
	/*
	 * These track the cost of reclaiming one LRU - file or anon -
	 * over the other. As the observed cost of reclaiming one LRU
	 * increases, the reclaim scan balance tips toward the other.
	 */
	unsigned long			anon_cost;
	unsigned long			file_cost;
	/* Non-resident age, driven by LRU movement */
	atomic_long_t			nonresident_age;
	/* Refaults at the time of last reclaim cycle */
	unsigned long			refaults[ANON_AND_FILE];
	/* Various lruvec state flags (enum lruvec_flags) */
	unsigned long			flags;
#ifdef CONFIG_MEMCG
	struct pglist_data *pgdat;
#endif
};

enum lru_list {
	LRU_INACTIVE_ANON = LRU_BASE,
	LRU_ACTIVE_ANON = LRU_BASE + LRU_ACTIVE,
	LRU_INACTIVE_FILE = LRU_BASE + LRU_FILE,
	LRU_ACTIVE_FILE = LRU_BASE + LRU_FILE + LRU_ACTIVE,
	LRU_UNEVICTABLE,
	NR_LRU_LISTS
};

struct page {
    /* ... */
    struct {    /* 使用联合体节省空间 */
        struct list_head lru;
        /* 或用于slab等其他用途 */
    };
    unsigned long flags;    /* 包含PG_active, PG_referenced等标志 */
    /* ... */
};

void lru_cache_add(struct page *page)
{
	struct pagevec *pvec;

	VM_BUG_ON_PAGE(PageActive(page) && PageUnevictable(page), page);
	VM_BUG_ON_PAGE(PageLRU(page), page);

	get_page(page);
	local_lock(&lru_pvecs.lock);
	///获取页向量组
	pvec = this_cpu_ptr(&lru_pvecs.lru_add);

	///将page加入页向量组，并判断是否需要刷新
	///这里为提高性能，对page加入lru做了个批处理，一次性加入15个page
	if (pagevec_add_and_need_flush(pvec, page))
		///将pvec一次性加入lru链表
		__pagevec_lru_add(pvec);
	local_unlock(&lru_pvecs.lock);
}

///页向量组，批量处理，对一对页面执行同样操作
struct pagevec {
	unsigned char nr;
	bool percpu_pvec_drained;
	struct page *pages[PAGEVEC_SIZE];
};

/*
 * The following struct pagevec are grouped together because they are protected
 * by disabling preemption (and interrupts remain enabled).
 */
struct lru_pvecs {
	local_lock_t lock;
	struct pagevec lru_add;   				//待加入 LRU 的页面
	struct pagevec lru_deactivate_file;		//待去激活的file页面 activate->inactivate
	struct pagevec lru_deactivate;			//待去激活的file/匿名页面 activate->inactivate
	struct pagevec lru_lazyfree;			//用于延迟释放匿名交换页 activate->inactivate
#ifdef CONFIG_SMP
	struct pagevec activate_page;			//待激活的页面 inactivate->activate
#endif

};
///定义per cpu变量的缓存页向量组
static DEFINE_PER_CPU(struct lru_pvecs, lru_pvecs) = {
	.lock = INIT_LOCAL_LOCK(lock),
};

/* return true if pagevec needs to drain */
static bool pagevec_add_and_need_flush(struct pagevec *pvec, struct page *page)
{
	bool ret = false;

	if (!pagevec_add(pvec, page) || PageCompound(page) ||
			lru_cache_disabled())
		ret = true;

	return ret;
}

static inline unsigned pagevec_space(struct pagevec *pvec)
{
	return PAGEVEC_SIZE - pvec->nr;
}

/*
 * Add a page to a pagevec.  Returns the number of slots still available.
 */
static inline unsigned pagevec_add(struct pagevec *pvec, struct page *page)
{
	pvec->pages[pvec->nr++] = page;
	return pagevec_space(pvec);
}

static __always_inline int PageCompound(struct page *page)
{
	return test_bit(PG_head, &page->flags) || PageTail(page);
}

void __pagevec_lru_add(struct pagevec *pvec)
{
	int i;
	struct lruvec *lruvec = NULL;
	unsigned long flags = 0;

///遍历pvec所有页面
	for (i = 0; i < pagevec_count(pvec); i++) {
		struct page *page = pvec->pages[i];

		lruvec = relock_page_lruvec_irqsave(page, lruvec, &flags);
		///page加入lru
		__pagevec_lru_add_fn(page, lruvec);
	}
	if (lruvec)
		unlock_page_lruvec_irqrestore(lruvec, flags);
	release_pages(pvec->pages, pvec->nr);
	pagevec_reinit(pvec);
}

static void __pagevec_lru_add_fn(struct page *page, struct lruvec *lruvec)
{
	//清除 PG_mlocked 标志并获取页面数量
	int was_unevictable = TestClearPageUnevictable(page);
	int nr_pages = thp_nr_pages(page);

	VM_BUG_ON_PAGE(PageLRU(page), page);

	//设置 PG_lru 标志并添加内存屏障
	SetPageLRU(page);
	smp_mb__after_atomic();

	if (page_evictable(page)) {
		// 如果page是PG_unevictable置位，则获取LRU_UNEVICTABLE链表
		// 如果page是匿名页，并且PG_active置位，则获取LRU_ACTIVE_ANON链表，
		// 否则是LRU_INACTIVE_ANON链表。
		// 如果page是文件页，并且PG_active置位，则获取LRU_ACTIVE_FILE链表，
		// 否则是LRU_INACTIVE_FILE链表。
		if (was_unevictable)
			__count_vm_events(UNEVICTABLE_PGRESCUED, nr_pages);
	} else {
		//不可回收页面 
		//清除 PG_active 标志
		ClearPageActive(page);
		//重新设置 PG_mlocked 标志
		SetPageUnevictable(page);
		if (!was_unevictable)
			__count_vm_events(UNEVICTABLE_PGCULLED, nr_pages);
	}
	/* 
	* 将page加入到对应lru链表头部中：
	* 1. 获取页的数量，如果支持透明大叶，会是多个页
	* 2. 通过mem_cgroup_update_lru_size更新lruvec中lru类型的链表的page num
	* 3. 加入对应lru链表头部，更新统计
	*/
	add_page_to_lru_list(page, lruvec);
	// 触发内核跟踪点，记录页面加入 LRU 链表的事件，用于性能分析和调试。
	trace_mm_lru_insertion(page);
}

static __always_inline void add_page_to_lru_list(struct page *page,
				struct lruvec *lruvec)
{
	///获取page页面类型
	enum lru_list lru = page_lru(page);

	update_lru_size(lruvec, lru, page_zonenum(page), thp_nr_pages(page));

	///将page加入到lru链表
	list_add(&page->lru, &lruvec->lists[lru]);
}

static __always_inline enum lru_list page_lru(struct page *page)
{
	enum lru_list lru;
	// 断言：页面不能同时是活跃且不可回收的
	VM_BUG_ON_PAGE(PageActive(page) && PageUnevictable(page), page);
	
	// 判断邪恶面是否不可回收，就是检查页面的 PG_mlocked 标志
	if (PageUnevictable(page))
		return LRU_UNEVICTABLE;

	///判断是否为文件页还是匿名页，根据不同页面类型放在不同的lru链表
	lru = page_is_file_lru(page) ? LRU_INACTIVE_FILE : LRU_INACTIVE_ANON;
	// 判断页面是否活跃
	if (PageActive(page))
		lru += LRU_ACTIVE;

	return lru;
}

// mm/filemap.c
struct page *pagecache_get_page(...)
{
	//...
	
    page = __page_cache_alloc(gfp_mask);
    if (page) {
        // 分配成功后初始化页面
        err = add_to_page_cache_lru(page, mapping, index, gfp_mask);
        if (unlikely(err)) {
            put_page(page);
            page = NULL;
        }
    }
    return page;
}

int add_to_page_cache_lru(struct page *page, struct address_space *mapping,
                          pgoff_t offset, gfp_t gfp_mask)
{
	//...
	
    // 将页面添加到页缓存树中
    int ret = add_to_page_cache(page, mapping, offset, gfp_mask);
    if (ret == 0)
        lru_cache_add(page);  // 关键：加入LRU系统
    return ret;
}

// mm/memory.c
static vm_fault_t do_anonymous_page(struct vm_fault *vmf)
{
    struct vm_area_struct *vma = vmf->vma;
    struct page *page;
    
    // 分配零初始化的匿名页
    page = alloc_zeroed_user_highpage_movable(vma, vmf->address);
    if (!page)
        goto oom;
    
    // 初始化页面
    __SetPageUptodate(page);
    
    // 建立页表映射
    entry = mk_pte(page, vma->vm_page_prot);
    set_pte_at(vma->vm_mm, vmf->address, vmf->pte, entry);
    
    // 更新反向映射
    page_add_new_anon_rmap(page, vma, vmf->address, false);
    
    // 关键：匿名页加入LRU系统
    lru_cache_add_inactive_or_unevictable(page, vma);
    
    return VM_FAULT_NOPAGE;
}

// mm/swap.c
void lru_cache_add_inactive_or_unevictable(struct page *page,
					 struct vm_area_struct *vma)
{
	bool unevictable;

	VM_BUG_ON_PAGE(PageLRU(page), page);

	unevictable = (vma->vm_flags & (VM_LOCKED | VM_SPECIAL)) == VM_LOCKED;
	if (unlikely(unevictable) && !TestSetPageMlocked(page)) {
		int nr_pages = thp_nr_pages(page);
		/*
		 * We use the irq-unsafe __mod_zone_page_state because this
		 * counter is not modified from interrupt context, and the pte
		 * lock is held(spinlock), which implies preemption disabled.
		 */
		__mod_zone_page_state(page_zone(page), NR_MLOCK, nr_pages);
		count_vm_events(UNEVICTABLE_PGMLOCKED, nr_pages);
	}
	lru_cache_add(page);
}

vm_fault_t filemap_fault(struct vm_fault *vmf)
{

	 ///如果pagecache已经存在，直接获取
	page = find_get_page(mapping, offset);
	if (likely(page)) {
		/*
		 * We found the page, so try async readahead before waiting for
		 * the lock.
		 */
		if (!(vmf->flags & FAULT_FLAG_TRIED))
			///直接读到pagecache
			fpin = do_async_mmap_readahead(vmf, page);
		if (unlikely(!PageUptodate(page))) {
			filemap_invalidate_lock_shared(mapping);
			mapping_locked = true;
		}
	} else {
		/* No page in the page cache at all */
		count_vm_event(PGMAJFAULT);
		count_memcg_event_mm(vmf->vma->vm_mm, PGMAJFAULT);
		ret = VM_FAULT_MAJOR;
		fpin = do_sync_mmap_readahead(vmf);
retry_find:
		/*
		 * See comment in filemap_create_page() why we need
		 * invalidate_lock
		 */
		if (!mapping_locked) {
			filemap_invalidate_lock_shared(mapping);
			mapping_locked = true;
		}
		///pagecache不存在，分配一个
		page = pagecache_get_page(mapping, offset,
					  FGP_CREAT|FGP_FOR_MMAP,
					  vmf->gfp_mask);
		if (!page) {
			if (fpin)
				goto out_retry;
			filemap_invalidate_unlock_shared(mapping);
			return VM_FAULT_OOM;
		}
	}
}

struct page *pagecache_get_page(struct address_space *mapping, pgoff_t index,
		int fgp_flags, gfp_t gfp_mask)
{
		///分配一个page，并读入文件内容, 用于pagecache
		page = __page_cache_alloc(gfp_mask);
		
		///page加入lru链表
		err = add_to_page_cache_lru(page, mapping, index, gfp_mask);

}

// mm/swap_state.c
struct page *__read_swap_cache_async(swp_entry_t entry, gfp_t gfp_mask,
                                     struct vm_area_struct *vma,
                                     unsigned long addr)
{
    struct page *page;
    
    // 分配页面
    page = alloc_page_vma(gfp_mask, vma, addr);
    if (!page)
        return NULL;
    
	/* May fail (-ENOMEM) if XArray node allocation failed. */
	if (add_to_swap_cache(page, entry, gfp_mask & GFP_RECLAIM_MASK, &shadow))
		goto fail_unlock;

	mem_cgroup_swapin_uncharge_swap(entry);

	if (shadow)
		workingset_refault(page, shadow);

	/* Caller will initiate read into locked page */
	lru_cache_add(page);
	*new_page_allocated = true;
	return page;
}

static void activate_page(struct page *page)
{
	page = compound_head(page);
	if (PageLRU(page) && !PageActive(page) && !PageUnevictable(page)) {
		struct pagevec *pvec;

		local_lock(&lru_pvecs.lock);
		// 获取本cpu的active_page链表
		pvec = this_cpu_ptr(&lru_pvecs.activate_page);
		get_page(page);
		if (pagevec_add_and_need_flush(pvec, page))     ///加入页向量组
			pagevec_lru_move_fn(pvec, __activate_page); ///从不活跃链表移除
		local_unlock(&lru_pvecs.lock);
	}
}

static void __activate_page(struct page *page, struct lruvec *lruvec)
{
	if (!PageActive(page) && !PageUnevictable(page)) {
		int nr_pages = thp_nr_pages(page);

		del_page_from_lru_list(page, lruvec); ///从不活跃链表删除掉
		SetPageActive(page);
		add_page_to_lru_list(page, lruvec);   ///添加到活跃链表
		trace_mm_lru_activate(page);

		__count_vm_events(PGACTIVATE, nr_pages);
		__count_memcg_events(lruvec_memcg(lruvec), PGACTIVATE,
				     nr_pages);
	}
}

void deactivate_page(struct page *page)
{
	//确保页面当前在活跃链表。 
	//排除不可回收的页面（如 mlock 锁定的页面）。
	if (PageLRU(page) && PageActive(page) && !PageUnevictable(page)) {
		struct pagevec *pvec;

		local_lock(&lru_pvecs.lock);
		// 获取本cpu的deactivate缓存链表
		pvec = this_cpu_ptr(&lru_pvecs.lru_deactivate);
		get_page(page);
		if (pagevec_add_and_need_flush(pvec, page))
			pagevec_lru_move_fn(pvec, lru_deactivate_fn);
		local_unlock(&lru_pvecs.lock);
	}
}

static void lru_deactivate_fn(struct page *page, struct lruvec *lruvec)
{
	if (PageActive(page) && !PageUnevictable(page)) {
		//若页面是透明大页，返回其包含的基页数量（如 2MB 大页返回 512）；普通页返回 1。
		int nr_pages = thp_nr_pages(page);
		//将页面从其当前所属的活跃 LRU 链表中删除。
		del_page_from_lru_list(page, lruvec);
		//移除活跃状态标志。
		ClearPageActive(page);
		//清除引用标记
		ClearPageReferenced(page);
		//将页面添加到非活跃 LRU 链表（默认插入头部）。
		add_page_to_lru_list(page, lruvec);

		__count_vm_events(PGDEACTIVATE, nr_pages);
		__count_memcg_events(lruvec_memcg(lruvec), PGDEACTIVATE,
				     nr_pages);
	}
}

 ///将文件页从LRU_ACTIVE放入LRU_INACTIVE
void deactivate_file_page(struct page *page)
{
	/*
	 * In a workload with many unevictable page such as mprotect,
	 * unevictable page deactivation for accelerating reclaim is pointless.
	 */
	if (PageUnevictable(page))
		return;

	if (likely(get_page_unless_zero(page))) {
		struct pagevec *pvec;

		local_lock(&lru_pvecs.lock);
		pvec = this_cpu_ptr(&lru_pvecs.lru_deactivate_file);

		if (pagevec_add_and_need_flush(pvec, page))
			pagevec_lru_move_fn(pvec, lru_deactivate_file_fn);
		local_unlock(&lru_pvecs.lock);
	}
}

static void lru_deactivate_file_fn(struct page *page, struct lruvec *lruvec)
{
	bool active = PageActive(page);
	int nr_pages = thp_nr_pages(page);

	///page不可回收,退出
	if (PageUnevictable(page))
		return;

	/* Some processes are using the page */
	///page被映射使用中，退出
	if (page_mapped(page))
		return;

	///从LRU_ACTIVE中删除
	del_page_from_lru_list(page, lruvec);
	///清除PG_active和PG_referenced标记
	ClearPageActive(page);
	ClearPageReferenced(page);

	//根据页面状态重新加入链表 
	//脏页/回写页
	if (PageWriteback(page) || PageDirty(page)) {
		/*
		 * PG_reclaim could be raced with end_page_writeback
		 * It can make readahead confusing.  But race window
		 * is _really_ small and  it's non-critical problem.
		 */
		 ///如果需要回写或脏页，加到LRU链表头
		add_page_to_lru_list(page, lruvec);
		///设置PG_reclaim标记
		SetPageReclaim(page);
	} else {
		/*
		 * The page's writeback ends up during pagevec
		 * We move that page into tail of inactive.
		 */
		 ///加到LRU链表尾，尽快回收
		add_page_to_lru_list_tail(page, lruvec);
		__count_vm_events(PGROTATED, nr_pages);
	}

	if (active) {
		__count_vm_events(PGDEACTIVATE, nr_pages);
		__count_memcg_events(lruvec_memcg(lruvec), PGDEACTIVATE,
				     nr_pages);
	}
}

void mark_page_accessed(struct page *page)
{
	//处理复合页
	page = compound_head(page);

	///PG_referenced==0，无论活跃或不活跃链表，都置1
	if (!PageReferenced(page)) {
		//对应状态转换：inactive,unreferenced → inactive,referenced。 
		//对应状态转换：active,unreferenced → active,referenced
		SetPageReferenced(page);
	} else if (PageUnevictable(page)) {
		// 处理不可回收页面
		/*
		 * Unevictable pages are on the "LRU_UNEVICTABLE" list. But,
		 * this list is never rotated or maintained, so marking an
		 * evictable page accessed has no effect.
		 */
	} else if (!PageActive(page)) {
		// 激活非活跃页面
		/*
		 * If the page is on the LRU, queue it for activation via
		 * lru_pvecs.activate_page. Otherwise, assume the page is on a
		 * pagevec, mark it active and it'll be moved to the active
		 * LRU on the next drain.
		 */
		 ///页面被访问,且referenced不为0，但不是活跃，将访问位清零，加入到活跃链表

		 ///加入到活跃链表：
		 ///   如果page在当前在lru(inactive)，先从原来lru删除，再加入也向量组，等待激活;
		 ///   如果page在页向量组, 激活标志位，将来会加入活跃链表
		if (PageLRU(page))
			activate_page(page);
		else
			__lru_cache_activate_page(page);   ///设置活跃标记
		// 状态转换：inactive,referenced → active,unreferenced
		ClearPageReferenced(page);  ///清除referenced=0
		workingset_activation(page);
	}
	if (page_is_idle(page))
		clear_page_idle(page);
}

inactive,unreferenced -> inactive,referenced
inactive,referenced -> active,unreferenced
active,unreferenced -> active,referenced

/*******************************************************************************
 * func:扫描不活跃链表时，会被调用;返回page_references页面行为类型
 * 无页面访问，无映射，回收

 * 当页面有访问，引用了PTE时，要放回到活跃LRU链表的情况有:
 * (1)页面是匿名页面(PageSwapBacked(page));
 * (2)页面位于最近第二次访问的文件缓存，或共享的文件缓存中；
 * (3)页面位于可执行文件的缓存中；
 *
 * 为了解决大量仅使用一次的page cache页面，充斥活跃链表问题，2.6.29开始做了如下优化
 * 当第一次读文件时，不调用mark_page_accessed(),
 * 即referenced_ptes=1，referenced_page=0
 ******************************************************************************/
static enum page_references page_check_references(struct page *page,
						  struct scan_control *sc)
{
	int referenced_ptes, referenced_page;
	unsigned long vm_flags;

	///检查页面，引用了多少个PTE(referenced_ptes),是否有访问
	referenced_ptes = page_referenced(page, 1, sc->target_mem_cgroup,
					  &vm_flags);

	///返回PG_referenced的值(只跟是否访问有关，与历史值无关)，并清除PG_referenced标记
	referenced_page = TestClearPageReferenced(page);

	/*
	 * 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;

///referenced_ptes有映射pte
	if (referenced_ptes) {
		/*
		 * 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);

		///referenced_page > 0， 访问过，放入活跃链表
		///referenced_ptes>1, 多个vma映射，放入活跃链表
		if (referenced_page || referenced_ptes > 1)
			return PAGEREF_ACTIVATE;

		/*
		 * Activate file-backed executable pages after first usage.
		 */
		 ///映射可执行文件,或匿名页面，放入活跃链表
		if ((vm_flags & VM_EXEC) && !PageSwapBacked(page))
			return PAGEREF_ACTIVATE;

		///referenced_page==0，referenced_ptes==1，继续放在不活跃链表，优化读文件大量一次性page cache占用活跃链表问题
		return PAGEREF_KEEP;
	}

	/* Reclaim if clean, defer dirty pages to writeback */
	///没有被访问，也无映射回收页面
	if (referenced_page && !PageSwapBacked(page))
		return PAGEREF_RECLAIM_CLEAN;

	return PAGEREF_RECLAIM;
}

int page_referenced(struct page *page,
		    int is_locked,
		    struct mem_cgroup *memcg,
		    unsigned long *vm_flags)
{
	int we_locked = 0;
	struct page_referenced_arg pra = {
		.mapcount = total_mapcount(page),
		.memcg = memcg,
	};
	struct rmap_walk_control rwc = {
		.rmap_one = page_referenced_one,
		.arg = (void *)&pra,
		.anon_lock = page_lock_anon_vma_read,
	};

	*vm_flags = 0;
	if (!pra.mapcount)  ///判断_mapcount是否大于等于0
		return 0;

	if (!page_rmapping(page)) ///判断page->mapping是否有地址空间映射
		return 0;

	if (!is_locked && (!PageAnon(page) || PageKsm(page))) {
		we_locked = trylock_page(page);
		if (!we_locked)
			return 1;
	}

	/*
	 * If we are reclaiming on behalf of a cgroup, skip
	 * counting on behalf of references from different
	 * cgroups
	 */
	if (memcg) {
		rwc.invalid_vma = invalid_page_referenced_vma;
	}

	rmap_walk(page, &rwc);   ///遍历映射page的所有VMA，调用rmap_one()函数，判断是否有映射的pte,统计映射pte总数
	*vm_flags = pra.vm_flags;

	if (we_locked)
		unlock_page(page);

	return pra.referenced;
}