linux2.6内核分析——LRU链表

LRU链表
本文转自http://liurugongzi.blog.sohu.com/153648100.html
lru链表是统称，细分为：活动链表、非活动链表。链表中存放的是属于进程用户态地址空间或者页高速缓存的所有页。前者是最近被访问过的页，后者是一段时间内未曾访问过的页，这样的好处是提高效率，减少搬运次数。而lru也是页框回收算法的核心数据结构。这两个双向链表是通过zone描述符结合入系统中，在zone中，有两个字段：active_list,inactive_list.一个是活动链表的表头，一个是非活动链表的表头。而同时，处于此两个链表中的页框标志位也需要相应设置：PG_lru,PG_active.前者的标志表明页在活动或非活动页链表中，而后者是页在活动链表中。当是属于非活动链表时，标志位要清。而页描述符中的字段lru指向的是链表中的下一页。如此，则形成了从zone管理区描述符中一个字段为起始点链接而成的lru链表。而处理链表也有几个相应的函数：

static inline void add_page_to_active_list(struct zone *zone, struct page *page)
static inline void add_page_to_inactive_list(struct zone *zone, struct page *page)
static inline void del_page_from_active_list(struct zone *zone, struct page *page)
static inline void del_page_from_inactive_list(struct zone *zone, struct page *page)
static inline void del_page_from_lru(struct zone *zone, struct page *page)
void fastcall activate_page(struct page *page)
void fastcall lru_cache_add(struct page *page)
void fastcall lru_cache_add_active(struct page *page)

两个插入和删除链表的函数是很简单的，参数都是zone和page.使用的语句也是链表操作语句：list_add，list_del所不同的是，其中的参数传递：
list_add(&page->lru, &zone->active_list);
list_add(&page->lru, &zone->inactive_list);
list_del(&page->lru);
list_del(&page->lru);
而加入完毕后，zone中表示页数目的字段也相应增加：
zone->nr_active++;
zone->nr_inactive++;
zone->nr_active--;
zone->nr_inactive--;

而del_page_from_lru也与前两个大同小异其中不同之处在于判断了页的PG_active标志位。

static inline void del_page_from_lru(struct zone *zone, struct page *page)
{
        list_del(&page->lru);
        if (PageActive(page)) {
                ClearPageActive(page);
                zone->nr_active--;
        } else {
                zone->nr_inactive--;
        }
}

而activate_page函数的目的就是将页从非活动链表中移动到活动链表，其中的if块就是这个作用，首先检查是不是lru链表中的，然后判断页是不是在非活动链表中。如果在，就删除。而删除的目的是为了移动到活动链表中，而在活动链表中的页的PG_active标志位需要置位，于是SetPageActive(page);

void fastcall activate_page(struct page *page)
{
        struct zone *zone = page_zone(page);
        spin_lock_irq(&zone->lru_lock);
        if (PageLRU(page) && !PageActive(page)) {
                del_page_from_inactive_list(zone, page);
                SetPageActive(page);
                add_page_to_active_list(zone, page);
                inc_page_state(pgactivate);
        }
        spin_unlock_irq(&zone->lru_lock);
}

而之所以设计这个框架，目的就是为了便于PFRA移动页。而这中有涉及到一个页标志的使用：PG_referenced(刚被访问过的页)。当非活动链表中的某一个页被访问时，那么并不是立刻移入活动链表，而是先检查这个标志位，如果这个标志置位为0则置位（为1），此页依然保留在非活动链表中。当再次访问到此页时，检查此标识符，如果为1，那么移入活动链表。如果两次访问时间间距超过了给定间隔，那么就要重新设置此标志位。如果移动进入了活动链表，那么PG_active标志位也将被置位。可以说，在移动移出这两个动作中，PG_referenced和PG_active两个标志位是配合使用的。

而涉及到这两个动作的关键函数有三个：
void fastcall mark_page_accessed(struct page *page)
int page_referenced(struct page *page, int is_locked, int ignore_token)
static void refill_inactive_zone(struct zone *zone, struct scan_control *sc)

/*
 * Mark a page as having seen activity.
 *
 * inactive,unreferenced        ->      inactive,referenced
 * inactive,referenced          ->      active,unreferenced
 * active,unreferenced          ->      active,referenced
 */
void fastcall mark_page_accessed(struct page *page)
{
        if (!PageActive(page) && PageReferenced(page) && PageLRU(page)) {
                activate_page(page);
                ClearPageReferenced(page);
        } else if (!PageReferenced(page)) {
                SetPageReferenced(page);
        }
}

这个函数的作用就是必须把页标记为访问过时调用。看函数的注释，三种状态之间的转化：当非活动链表和未使用过时调用函数，变为非活动链表和使用过；当非活动链表和使用过时调用函数，变为活动链表和未使用过；当活动链表未使用过时调用函数，变为活动链表并使用过。完成以上功能的就是函数的目的。在函数体的if第一个判断中，首先是判断页是否在lru链表中，还要判断页的标志PG_referenced是否置位，还要判断页的PG_active标志是否置位。如果此时页标志的组合是：在lru链表中，并且在单位时间内使用过，并且未在活动链表中，则将此页调入活动链表，并且清除PG_referenced标志。然后在下一个判断语句中，条件是页没有被刚刚使用过。也就是PG_referenced标志位并没有置位为1.那么此时就要置未。

而函数page_referenced的作用就是扫描时，对部分标志位进行清零工作，比如PG_referenced.

回收函数的重点是refill_inactive_zone函数。而函数中用到一个重要结构：scan_control，这个结构也是被PFRA广泛使用，其中的各个字段存放着回首操作执行的各种信息，直接影响到系统的策略取舍。

struct scan_control {
        unsigned long nr_to_scan;活动链表中待扫描的目标页数
        unsigned long nr_scanned;当前迭代中扫描过的非活动页数
        unsigned long nr_reclaimed;当前迭代中回收的页数
        unsigned long nr_mapped;用户态地址空间引用的页数
        int nr_to_reclaim;待回收的目标页数
        unsigned int priority;扫描优先级范围从12到0，低优先级表示扫描更多的页
        unsigned int gfp_mask;调用进程传来的GFP掩码
        int may_writepage;如果置位，则允许将脏页写到磁盘（只针对便携情形）
};

这个函数所从事的基本工作始终是循环判断标志，然后将页插入不同的链表。前后需要四次循环。在移动过程中的判断，需要一个临时的辅助链表LIST_HEAD(l_hold);

第一次循环：在这个循环判断语句中，int pgscanned = 0;int nr_pages = sc->nr_to_scan（活动链表中待扫描的目标页数）;可见循环的第一个条件就是活动链表中的目标页的个数，下一个条件就是list_empty(&zone->active_list)或者链表为空时结束。将扫描页加入到临时链表中 list_add(&page->lru, &l_hold);而如果标志为0，则一定是伙伴系统中的，所以要放回到活动链表中。因为伙伴系统是准备分配大块内存区时使用，而并不是“零星”使用的。

while (pgscanned < nr_pages && !list_empty(&zone->active_list)) {
                page = lru_to_page(&zone->active_list);
                prefetchw_prev_lru_page(page, &zone->active_list, flags);
                list_del(&page->lru);
                if (get_page_testone(page)) {
                        __put_page(page);
                        SetPageLRU(page);
                        list_add(&page->lru, &zone->active_list);
                } else {
                        list_add(&page->lru, &l_hold);
                        pgmoved++;
                }
                pgscanned++;
        }


在完成第一个循环体后，临时链表中已经有了页，而在活动链表中也已经摘除了部分页，这些是准备回收的页。然后就是准备工作以及“计算交换值”。

        zone->pages_scanned += pgscanned;
        zone->nr_active -= pgmoved;
        distress = 100 >> zone->prev_priority;
        mapped_ratio = (sc->nr_mapped * 100) / total_memory;
        swap_tendency = mapped_ratio / 2 + distress + vm_swappiness;
        if (swap_tendency >= 100)
                reclaim_mapped = 1;

交换倾向值是用来决定系统回收方式的。它的目的是用来判断不同情况下，回收数量的多少。也就是说，当回收的页框数量太多的时候，那么系统的效率就会受到很大的影响，也就是回收了过多的活动链表中的页。而如果回收的数量太少，那么同样非活动链表中的准备引用页数量不足以弥补系统调用，那么效率也会受到影响，而如何保持均衡，就是通过这个数值来判断的。而在结构sc_contrl中的字段priority，是对应zone中的prev_priority;后者是管理区优先级。而另一种方式就是通过计算，也就是交换倾向数值。

lru链表中有两类页：属于用户态地址空间的页、不属于任何用户态进程且在页高速缓存中的页。而PFRA倾向与把用户态进程的页保留在ram中，从而压缩页高速缓存。而这个数值的作用就是决定函数是移动所有的页，还是仅仅移动不属于用户态进程的页。

交换倾向值＝映射比率／2+负荷值＋交换值

其中映射比率由字段：nr_mapped来表示，也就是占有可分配页框的比率。如果这个数值大，那么系统中的大部分动态内存大部分用于用户态进程，反之则用于页高速缓存。
而负荷值是表示回收页框算法在管理区中回收页框的效率。也就是字段：prev_priority
交换值则为用户定义的常数，通常为60，在/proc/sys/vm/swappiness中可以修改数值。

当交换倾向数值大于100时，页将从进程地址空间回收。当交换值被人为设置为0时，那么系统不会从用户态地址空间回收。如果人为设置为100时，那么每次调用此函数都会从用户态地址空间回收。以上就是这段程序的用途。

第二次循环：则是通过上面的交换数值以及一些条件来判断是否加入活动链表，其余的一概加入非活动链表。也就是从第一次循环中摘出的那些页的第二次再分配。

while (!list_empty(&l_hold)) {
                cond_resched();
                page = lru_to_page(&l_hold);
                list_del(&page->lru);
                if (page_mapped(page)) {
                        if (!reclaim_mapped || (total_swap_pages == 0 && PageAnon(page)) || page_referenced(page, 0, sc->priority <= 0)) {
                                list_add(&page->lru, &l_active);
                                continue;
                        }
                }
                list_add(&page->lru, &l_inactive);
        }


第三次循环：将页移入到管理区非活动链表中。

        while (!list_empty(&l_inactive)) {
                page = lru_to_page(&l_inactive);
                prefetchw_prev_lru_page(page, &l_inactive, flags);
                list_move(&page->lru, &zone->inactive_list);
                pgmoved++;
                if (!pagevec_add(&pvec, page)) {
                        zone->nr_inactive += pgmoved;
                        spin_unlock_irq(&zone->lru_lock);
                        pgdeactivate += pgmoved;
                        pgmoved = 0;
                        if (buffer_heads_over_limit)
                                pagevec_strip(&pvec);
                        __pagevec_release(&pvec);
                        spin_lock_irq(&zone->lru_lock);
                }
        }


第四次循环，将页移入到管理区的活动链表中。

 while (!list_empty(&l_active)) {
                page = lru_to_page(&l_active);
                prefetchw_prev_lru_page(page, &l_active, flags);
                if (TestSetPageLRU(page))
                        BUG();
                BUG_ON(!PageActive(page));
                list_move(&page->lru, &zone->active_list);
                pgmoved++;
                if (!pagevec_add(&pvec, page)) {
                        zone->nr_active += pgmoved;
                        pgmoved = 0;
                        spin_unlock_irq(&zone->lru_lock);
                        __pagevec_release(&pvec);
                        spin_lock_irq(&zone->lru_lock);
                }
        }