一、页面回收概述

 Linux中页面回收主要是通过两种方式触发的，一种是由“内存严重不足”事件触发的；一种是由后台进程 kswapd触发的，该进程周期性地运行，一旦检测到内存不足，就会触发页面回收操作。对于第一种情况，系统会调用函数 try_to_free_pages()去检查当前内存区域中的页面，回收那些最不常用的页面。对于第二种情况，函数 balance_pgdat()是入口函数。以下是linux3.5中页面回收关键代码流程图。

http://img.my.csdn.net/uploads/201304/19/1366360883_7320.png

其中，shrink_zone() 函数是 Linux操作系统实现页面回收的最核心的函数之一，它实现了对一个内存区域的页面进行回收的功能，该函数主要做了两件事情：

• 将某些页面从 active 链表移到 inactive 链表，这是由函数 shrink_active_list() 实现的。
• 从 inactive 链表中选定一定数目的页面，将其放到一个临时链表中，这由函数 shrink_inactive_list() 完成。该函数最终会调用 shrink_page_list() 去回收这些页面。函数 shrink_page_list() 返回的是回收成功的页面数目。

二、LRU链表

LRU链表是页框回收算法的核心数据结构。lru链表是统称，细分为：活动链表、非活动链表。

http://img.my.csdn.net/uploads/201304/19/1366360892_3774.png

每个zone都有一组lru链表，页面都被放到自己对应的zone的LRU中。

structzone {

……

struct lruvec  lruvec;

……

}

一组LRU由几对链表组成，有磁盘高速缓存页面（包括文件映射页面）的链表、匿名映射页面的链表、等。一对链表实际上是active和inactive两个链表，前者是最近使用过的页面、后者是最近未使用的页面。

struct lruvec {

structlist_head lists[NR_LRU_LISTS];

structzone_reclaim_stat reclaim_stat;

#ifdefCONFIG_CGROUP_MEM_RES_CTLR

structzone *zone;

#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

};

处于此两个链表中的页框标志位也需要相应设置：PG_lru,PG_active。前者的标志表明页在活动或非活动页链表中，而后者是页在活动链表中。当是属于非活动链表时，标志位要清。

三、LRU 缓存

前边提到，页面根据其活跃程度会在active链表和 inactive链表之间来回移动，如果要将某个页面插入到这两个链表中去，必须要通过自旋锁以保证对链表的并发访问操作不会出错。为了降低锁的竞争，Linux提供了一种特殊的缓存：LRU缓存，用以批量地向 LRU链表中快速地添加页面。有了 LRU缓存之后，新页不会被马上添加到相应的链表上去，而是先被放到一个缓冲区中去，当该缓冲区缓存了足够多的页面之后，缓冲区中的页面才会被一次性地全部添加到相应的 LRU链表中去。Linux采用这种方法降低了锁的竞争，极大地提升了系统的性能。

LRU缓存用到了 pagevec结构，如下所示:

struct pagevec {

unsignedlong nr;

unsignedlong cold;

structpage *pages[PAGEVEC_SIZE];

};

         pagevec这个结构就是用来管理 LRU缓存中的这些页面的。该结构定义了一个数组，这个数组中的项是指向 page结构的指针。一个pagevec结构最多可以存在 14个这样的项（PAGEVEC_SIZE的默认值是 14）。当一个 pagevec 的结构满了，那么该 pagevec中的所有页面会一次性地被移动到相应的 LRU链表上去。

用来实现 LRU缓存的两个关键函数是 lru_cache_add()和lru_cache_add_active()。前者用于延迟将页面添加到 inactive链表上去，后者用于延迟将页面添加到 active链表上去。这两个函数都会将要移动的页面先放到页向量 pagevec中，当pagevec满了（已经装了 14个页面的描述符指针），pagevec结构中的所有页面才会被一次性地移动到相应的链表上去。

四、内存页的状态迁移

下图概括总结了如何在两个链表之间移动页面。

http://img.my.csdn.net/uploads/201304/19/1366360898_9222.png

当非活动链表中的某一个页被访问时，那么并不是立刻移入活动链表，而是先检查这个标志位，如果这个标志置位为0则置位（为1），此页依然保留在非活动链表中。当再次访问到此页时，检查此标识符，如果为1，那么移入活动链表。如果两次访问时间间距超过了给定间隔，那么就要重新设置此标志位。如果移动进入了活动链表，那么PG_active标志位也将被置位。可以说，在移动移出这两个动作中，PG_referenced和PG_active两个标志位是配合使用的。同理，当页的活动减少时，如果要将其转入inactive链表，则需要两次page_referenced调用，而其中不能插入mark_page_accessed调用。

在内核看来，anon最重要，filemap其次，buffer/cache最不重要。具体的表现：

• anon page直接就在 active list中（代码实现在page_add_new_anon_rmap），一般系统比较少才能调用到shrink_active_list（调用的目的只是平衡anon的活动链表和非活动链表），更突出了它的重要性。
• buffer/cache只mark_page_accessed一次的话（一般至少一次），shrink_inactive_list会直接释放它。
• filemap只访问一次的话，第一次shrink_inactive_list会把他keep在inactive list中，第二次shrink_inactive_list就会释放它。
• anon page只访问一次的话，第一次shrink_active_list会把他移到inactive list中，然后下次shrink_inactive_list就会释放它。

五、页面在 active链表和 inactive链表之间来回移动涉及的函数

1.mark_page_accessed

voidmark_page_accessed(struct page *page)

{

if(!PageActive(page) && !PageUnevictable(page) &&

PageReferenced(page)&& PageLRU(page)) {

activate_page(page);

ClearPageReferenced(page);

}else if (!PageReferenced(page)) {

SetPageReferenced(page);

}

}

该函数实现了如下表所示的状态迁移：

2.activate_page

voidactivate_page(struct page *page)

{

if(PageLRU(page) && !PageActive(page) && !PageUnevictable(page)){

structpagevec *pvec = &get_cpu_var(activate_page_pvecs);

page_cache_get(page);

if(!pagevec_add(pvec, page))

pagevec_lru_move_fn(pvec,__activate_page, NULL);

put_cpu_var(activate_page_pvecs);

}

}

activate_page函数的目的是将页从非活动链表中移动到活动链表，首先检查page是不是lru链表中的，然后判断页是不是在非活动链表中。如果在，就使用pagevec_add将该页添加到特定于CPU的页向量pvec中。pagevec_add返回的是添加之后页向量中仍然空闲的项数目，返回0表示pvec满了，这时pvec结构中的所有页面才会被一次性地移动到相应的链表上去。其中get_cpu_var的作用是阻止CPU处理中断。

3.page_referenced

intpage_referenced(struct page *page,

    int is_locked,

    struct mem_cgroup *memcg,

    unsigned long *vm_flags)

{

intreferenced = 0;

intwe_locked = 0;

*vm_flags= 0;

if(page_mapped(page) && page_rmapping(page)) {

if(!is_locked && (!PageAnon(page) || PageKsm(page))) {

we_locked= trylock_page(page);

if(!we_locked) {

referenced++;

gotoout;

}

}

if (unlikely(PageKsm(page))//内核同页合并，具有写保护的页。

referenced += page_referenced_ksm(page,memcg,vm_flags);//计算访问该KSM页的次数

elseif (PageAnon(page))

referenced += page_referenced_anon(page,memcg,vm_flags);//计算该访问匿名映射页的次数

elseif (page->mapping)

referenced += page_referenced_file(page,memcg,vm_flags);//计算访问该文件映射页的次数

if(we_locked)

unlock_page(page);

//该函数在X86处理器上为空，那么PG_referenced在哪里复位呢？

if(page_test_and_clear_young(page_to_pfn(page)))

referenced++;

}

out:

returnreferenced;

}

释放page时候，通过 page_referenced函数来实现page的二次机会释放。在页框回收算法中，对每个页的扫描都会调用该函数，函数返回最近引用该页的次数。

http://img.my.csdn.net/uploads/201304/19/1366360903_4387.png

具体实现是，page_referenced通过反向映射找到所有的pte并检查其access位，如果有最近刚访问的pte话（access位设置）,这个page不会立刻释放，而是重新加入到lru中，并且清除所有pte的access标志。下次再释放该page的时候，没有最近访问了的pte了。这个时候真正的释放，从而实现二次机会。

其中清除pte的access标志位的函数调用路径是：

page_referenced()

->page_referenced_ksm()/page_referenced_anon()/page_referenced_file()

->page_referenced_one()

->ptep_clear_flush_young()

->ptep_test_and_clear_young()

->test_and_clear_bit(_PAGE_BIT_ACCESSED,(unsignedlong *) &ptep->pte);