[Linux Kernel 5] LRU (Memory Reclaim)

리눅스 커널은 메모리 부족시 reclaim에 LRU(Least Recently Used) 정책을 사용한다.

 

 

1. Basis

 

커널은 리스트를 이용하여 LRU를 구현한다.

커널 2.4엔 하나의 리스트를, 커널 2.6.28 이전엔 active_list와 inactive_list를,

그 이후엔 5개의 리스트를 사용했다.

또한, 커널 4.7까지는 리스트를 구조체 zone에서 관리했는데,

4.8부터는 구조체 pglist_data에서 관리한다.

5개의 리스트는 다음과 같다.

• pglist_data->__lruvec.lists[LRU_INACTIVE_ANON]
• pglist_data->__lruvec.lists[LRU_ACTIVE_ANON]
• pglist_data->__lruvec.lists[LRU_INACTIVE_FILE]
• pglist_data->__lruvec.lists[LRU_ACTIVE_FILE]
• pglist_data->__lruvec.lists[LRU_UNEVICTABLE]

_ANON 타입은 anonymous 메모리를 매핑하여 사용한 페이지이며, _FILE 타입은 파일을 매핑하여 사용하는 페이지이다.

INACTIVE_ 타입은 회수 후보 페이지이며, ACTIVE_ 타입은 할당 후 최근에 사용해 다시 접근할 확률이 높은 페이지이다.

주기적으로 inactive list와 active list의 비율을 비교하여 active의 후미(cold) 페이지를 inactive list로 옮기고, 참조된 페이지는 active list의 선두(hot)에 옮긴다.

UNEVICTABLE 타입은 reclaim 대상이 아닌 페이지다.

또한, 리스트를 여럿으로 나눴어도 페이지 추가/이동 시마다 리스트를 조작하는건 비효율적이다.

따라서 페이지를 한번에 PAGEVEC_SIZE(15)개씩 저장할 수 있는 다음 pagevec 구조체들을 캐시로 사용한다.

static DEFINE_PER_CPU(struct pagevec, lru_add_pvec);
static DEFINE_PER_CPU(struct pagevec, lru_rotate_pvecs);
static DEFINE_PER_CPU(struct pagevec, lru_deactivate_file_pvecs);
static DEFINE_PER_CPU(struct pagevec, lru_deactivate_pvecs);
static DEFINE_PER_CPU(struct pagevec, lru_lazyfree_pvecs);
#ifdef CONFIG_SMP
static DEFINE_PER_CPU(struct pagevec, activate_page_pvecs);

 

LRU 리스트가 zone 구조체에서 pglist_data 구조체로 옮겨갔다는 것에서 알 수 있듯이,

과거엔 zone별로 LRU 리스트(lruvec)을 관리했다면,

현재는 memory cgroup의 node별로 lruvec을 관리한다.

 

 

 

2. LRU Data Structure

 

/*
 * We do arithmetic on the LRU lists in various places in the code,
 * so it is important to keep the active lists LRU_ACTIVE higher in
 * the array than the corresponding inactive lists, and to keep
 * the *_FILE lists LRU_FILE higher than the corresponding _ANON lists.
 *
 * This has to be kept in sync with the statistics in zone_stat_item
 * above and the descriptions in vmstat_text in mm/vmstat.c
 */
#define LRU_BASE 0
#define LRU_ACTIVE 1
#define LRU_FILE 2
 
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 zone_reclaim_stat {
	/*
	 * The pageout code in vmscan.c keeps track of how many of the
	 * mem/swap backed and file backed pages are referenced.
	 * The higher the rotated/scanned ratio, the more valuable
	 * that cache is.
	 *
	 * The anon LRU stats live in [0], file LRU stats in [1]
	 */
	unsigned long		recent_rotated[2];
	unsigned long		recent_scanned[2];
};
 
struct lruvec {
	struct list_head		lists[NR_LRU_LISTS];
	struct zone_reclaim_stat	reclaim_stat;
	/* Evictions & activations on the inactive file list */
	atomic_long_t			inactive_age;
	/* Refaults at the time of last reclaim cycle */
	unsigned long			refaults;
	/* Various lruvec state flags (enum lruvec_flags) */
	unsigned long			flags;
#ifdef CONFIG_MEMCG
	struct pglist_data *pgdat;
#endif
};
 
 
 
#define PAGEVEC_SIZE	15
 
struct pagevec {
	unsigned char nr;
	bool percpu_pvec_drained;
	struct page *pages[PAGEVEC_SIZE];
};
 

lruvec의 멤버는 쉽게 이해할 수 있다.

pagevec의 멤버 nr은 pagevec에서 관리하는 페이지 수이다.

 

 

 

3. LRU 제어 함수

 

/* linux/mm/swap.c */
extern void lru_cache_add(struct page *);
extern void lru_cache_add_anon(struct page *page);
extern void lru_cache_add_file(struct page *page);
extern void lru_add_page_tail(struct page *page, struct page *page_tail,
			 struct lruvec *lruvec, struct list_head *head);
extern void activate_page(struct page *);
extern void mark_page_accessed(struct page *);
extern void lru_add_drain(void);
extern void lru_add_drain_cpu(int cpu);
extern void lru_add_drain_all(void);
extern void rotate_reclaimable_page(struct page *page);
extern void deactivate_file_page(struct page *page);
extern void deactivate_page(struct page *page);
extern void mark_page_lazyfree(struct page *page);
extern void swap_setup(void);
 
extern void lru_cache_add_active_or_unevictable(struct page *page,
						struct vm_area_struct *vma);

 

fs상 여러 코드상에서 add_to_page_cache_lru 함수를 호출하면 이 함수는 내부적으로 lru_cache_add를 호출한다.

lru_cache_add는 __lru_cache_add를 호출하여 lru_add_pvec 캐시에 페이지를 추가하거나 캐시가 꽉 찬 경우 pagevec_lru_move_fn을 호출하여 LRU 리스트에 직접 페이지를 추가한다.

 

이런 식으로 함수들이 사용하는 pagevec을 짝지으면 다음과 같다.

function	pagevec
lru_cache_add	lru_add_pvec
lru_cache_add_anon	lru_add_pvec
lru_cache_add_file	lru_add_pvec
activate_page	activate_page_pvecs
mark_page_accessed	activate_page_pvecs | lru_add_pvec
rotate_reclaimable_page	lru_rotate_pvecs
deactivate_file_page	lru_deactivate_file_pvecs
deactivate_page	lru_deactivate_pvecs
mark_page_lazyfree	lru_lazyfree_pvecs

lru_add_drain_xxx 함수는 pagevec 캐시에 있는 페이지를 LRU 리스트로 옮기는데 사용한다.

/*
 * Drain pages out of the cpu's pagevecs.
 * Either "cpu" is the current CPU, and preemption has already been
 * disabled; or "cpu" is being hot-unplugged, and is already dead.
 */
void lru_add_drain_cpu(int cpu)
{
	struct pagevec *pvec = &per_cpu(lru_add_pvec, cpu);
 
	if (pagevec_count(pvec))
		__pagevec_lru_add(pvec);
 
	pvec = &per_cpu(lru_rotate_pvecs, cpu);
	if (pagevec_count(pvec)) {
		unsigned long flags;
 
		/* No harm done if a racing interrupt already did this */
		local_irq_save(flags);
		pagevec_move_tail(pvec);
		local_irq_restore(flags);
	}
 
	pvec = &per_cpu(lru_deactivate_file_pvecs, cpu);
	if (pagevec_count(pvec))
		pagevec_lru_move_fn(pvec, lru_deactivate_file_fn, NULL);
 
	pvec = &per_cpu(lru_deactivate_pvecs, cpu);
	if (pagevec_count(pvec))
		pagevec_lru_move_fn(pvec, lru_deactivate_fn, NULL);
 
	pvec = &per_cpu(lru_lazyfree_pvecs, cpu);
	if (pagevec_count(pvec))
		pagevec_lru_move_fn(pvec, lru_lazyfree_fn, NULL);
 
	activate_page_drain(cpu);
}
 
static void pagevec_lru_move_fn(struct pagevec *pvec,
	void (*move_fn)(struct page *page, struct lruvec *lruvec, void *arg),
	void *arg)
{
	int i;
	struct pglist_data *pgdat = NULL;
	struct lruvec *lruvec;
	unsigned long flags = 0;
 
	for (i = 0; i < pagevec_count(pvec); i++) {
		struct page *page = pvec->pages[i];
		struct pglist_data *pagepgdat = page_pgdat(page);
 
		if (pagepgdat != pgdat) {
			if (pgdat)
				spin_unlock_irqrestore(&pgdat->lru_lock, flags);
			pgdat = pagepgdat;
			spin_lock_irqsave(&pgdat->lru_lock, flags);
		}
 
		lruvec = mem_cgroup_page_lruvec(page, pgdat);
		(*move_fn)(page, lruvec, arg);
	}
	if (pgdat)
		spin_unlock_irqrestore(&pgdat->lru_lock, flags);
	release_pages(pvec->pages, pvec->nr);
	pagevec_reinit(pvec);
}

pagevec_lru_move_fn는 인자로 전달받은 pagevec에 move_fn을 호출하여 페이지를 옮긴다.

 

또한 위 함수들에서 내부적으로 호출하는 LRU 리스트 업데이트 헬퍼 함수들은 다음과 같다.

static __always_inline void add_page_to_lru_list(struct page *page,
				struct lruvec *lruvec, enum lru_list lru)
{
	update_lru_size(lruvec, lru, page_zonenum(page), hpage_nr_pages(page));
	list_add(&page->lru, &lruvec->lists[lru]);
}
 
static __always_inline void add_page_to_lru_list_tail(struct page *page,
				struct lruvec *lruvec, enum lru_list lru)
{
	update_lru_size(lruvec, lru, page_zonenum(page), hpage_nr_pages(page));
	list_add_tail(&page->lru, &lruvec->lists[lru]);
}
 
static __always_inline void del_page_from_lru_list(struct page *page,
				struct lruvec *lruvec, enum lru_list lru)
{
	list_del(&page->lru);
	update_lru_size(lruvec, lru, page_zonenum(page), -hpage_nr_pages(page));
}

 

 

 

4. LRU 리스트 뷰어 예제 소스

 

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/sched.h>
#include <linux/mm.h>
#include <linux/list.h>
#include <linux/cpuset.h>
#include <linux/memcontrol.h>
 
#define prev_page(p)	list_entry((p)->lru.prev, struct page, lru)
 
void show_pfn(struct list_head *src)
{
	int page_count = 0;
	struct page *p = NULL;
 
	while (!list_empty(src))
	{
		if (++page_count >= 20)
			break;
 
		p = lru_to_page(src);
		printk(KERN_CONT "(%lx) ", page_to_pfn(p));
		p = prev_page(p);
	}
}
 
void show_list(void)
{
	struct pglist_data *current_pglist = NULL;
	struct lruvec *lruvec = NULL;
	struct mem_cgroup *memcg = NULL;
	struct mem_cgroup_per_node *mz;
	int i;
 
	for (i = 0; i < MAX_NUMNODES; i++) {
		if (NODE_DATA(i) == NULL)
			continue;
 
		current_pglist = NODE_DATA(i);
 
		if (current_pglist->node_present_pages == 0) {
			printk(KERN_ALERT "Node-%d does not have any pages.\n", i);
			continue;
		}
 
		spin_lock_irq(&current_pglist->lru_lock);
 
		memcg = get_mem_cgroup_from_mm(NULL);
		mz = mem_cgroup_nodeinfo(memcg, current_pglist->node_id);
		lruvec = &mz->lruvec;
 
		printk("========== LRU_ACTIVE_FILE ============\n");
		show_pfn(&lruvec->lists[LRU_ACTIVE_FILE]);
		printk("========== LRU_INACTIVE_FILE ============\n");
		show_pfn(&lruvec->lists[LRU_INACTIVE_FILE]);
		printk("========== LRU_ACTIVE_ANON ============\n");
		show_pfn(&lruvec->lists[LRU_ACTIVE_ANON]);
		printk("========== LRU_INACTIVE_ANON ============\n");
		show_pfn(&lruvec->lists[LRU_INACTIVE_ANON]);
		printk("========== LRU_UNEVICTABLE ============\n");
		show_pfn(&lruvec->lists[LRU_UNEVICTABLE]);
 
		spin_unlock_irq(&current_pglist->lru_lock);
	}
}
 
static int __init show_lru_init(void)
{
	if (mem_cgroup_disabled())
		printk("memcg disabled\n");
	else
		printk("memcg enabled\n");
	show_list();
	return 0;
}
 
static void __exit show_lru_exit(void)
{
}
 
module_init(show_lru_init);
module_exit(show_lru_exit);
MODULE_LICENSE("GPL");

show_pfn 함수에선 lru_to_page 함수로 lru 리스트의 페이지를 가져와 출력하는걸 20번 반복한다.

show_list 함수에선 root memcg의 lruvec을 구해서 lruvec 리스트들을 show_pfn으로 출력한다.

 

 

 

5. 실행 결과

 

dmesg 결과

dmesg의 결과 같은 주소가 20번 출력된 것을 보니 해당 리스트에는 엔트리가 하나씩 존재한 것으로 유추할 수 있다.

 

 

---

 

예제의 show_pfn 함수에서 src를 갱신해주지 않아서 생긴 문제 확인