자주 읽는 file의 cache page와 오래 사용하지 않은 anonymous page를 똑같이 버리면 reclaim 비용이 커집니다. 그러나 모든 memory access마다 kernel이 folio를 list 앞으로 옮기는 것도 현실적이지 않습니다. mapped memory의 load와 store 대부분은 kernel을 호출하지 않기 때문입니다.
classic LRU는 완전한 접근 순서를 기록하는 대신 page table의 accessed 상태와 folio의 software 상태를 조합합니다. 여기서는 이 classic 경로를 설명합니다. MGLRU가 활성화된 경우의 generation·tier 정책을 같은 알고리즘으로 읽어서는 안 됩니다.
Accessed bit는 최근 사용의 표본입니다
x86-64에서는 CPU가 page table entry의 accessed bit를 설정합니다. pte_young() 같은 helper로 이를 검사하며, kernel이 지우기 전까지 남는 sticky 상태입니다. folio_referenced()는 reverse mapping을 따라 folio를 mapping한 page table들을 확인하고 사용 흔적을 다음 검사를 위해 정리합니다. huge mapping은 해당 page-table level을 고려해야 합니다.
검사와 정리는 별개 작업처럼 보이지만 같은 관찰 주기에 연결됩니다. PTE 경로의 ptep_clear_flush_young_notify() 계열은 young 상태의 test-and-clear와 필요한 TLB·secondary MMU 통지를 연결합니다. 다음 scan에서 같은 오래된 흔적을 새 접근으로 다시 세지 않으려면 이를 지워야 합니다. 정확한 helper와 필요한 flush는 architecture 및 page-table level에 따라 달라집니다.
이 값은 정확한 마지막 접근 시각도, 읽은 byte 수나 access 횟수도 아닙니다. 두 검사 사이에 한 번 썼든 여러 번 썼든 동일한 흔적으로 보일 수 있습니다. rmap을 안정적으로 읽을 수 없는 경우 역시 단순히 사용되지 않았다고 판정해서는 안 됩니다.
하나의 LRU만 쓰면 tail에 도착한 page마다 실제로 hot한지 확인하는 낭비가 커집니다. active와 inactive를 나누면 inactive에서 실제 회수 후보를 고르고, active에서 보호할 후보를 관리할 수 있습니다. active를 줄인다는 것은 대체로 inactive로 내리는 aging이지 physical free가 아닙니다.
Anonymous와 file은 버린 뒤의 비용이 다릅니다
clean file folio는 cache에서 제거한 뒤 필요하면 file에서 다시 읽을 수 있습니다. ordinary anonymous 내용은 복원할 backing을 마련해야 하므로 swap-out이 필요할 수 있습니다. 그래서 active/inactive 각각을 anon/file로 나눈 네 evictable list를 둡니다.
이 분류에서 PG_swapbacked는 중요하지만, 이미 swap slot을 배정받았다는 뜻은 아닙니다. LRU family를 고르는 성격과 실제 swap cache membership은 별개입니다. lazy-free anonymous memory처럼 사용자가 보는 anonymous mapping과 LRU family가 일치하지 않는 경우도 있습니다.
LRU_UNEVICTABLE은 회수할 수 없는 folio를 위한 분류와 accounting을 제공합니다. 이를 언제든 순회할 수 있는 다섯 번째 evictable queue로 생각하면 안 됩니다. 관련 구현에서는 해당 list head를 poison하여 잘못된 접근을 방지합니다. PG_active와 PG_unevictable을 동시에 유효한 상태로 만드는 것도 잘못입니다.
첫 흔적과 반복 사용을 나눠 봅니다
inactive folio를 검사할 때에는 page table의 참조 흔적과 이전 PG_referenced를 함께 봅니다. v6.18 classic 경로의 ordinary anon/file folio에서는 한 PTE의 첫 사용 흔적을 발견하면 PG_referenced를 남기고 KEEP으로 한 차례 더 기회를 줄 수 있습니다. 다음 검사에서 사용 흔적이 다시 보이거나 여러 PTE에서 참조가 발견되면 ACTIVATE로 보호를 강화합니다.
이 과정은 먼저 folio_referenced()의 결과를 얻고 기존 referenced 상태를 test-and-clear한 뒤, 이번 page-table 관찰에 따라 mark를 다시 남기는 방식입니다. 새 mapping을 만든 fault 자체도 young 상태를 만들므로 첫 흔적만으로 반복 사용을 단정하지 않습니다. KEEP은 inactive에서 다시 검사할 기회를 주는 것이고, ACTIVATE는 active로 옮겨 보호하는 것이며, RECLAIM은 뒤의 unmap·writeback·refcount 검사로 진행할 수 있다는 뜻입니다. 어느 결과도 곧바로 physical free를 완료했다는 반환값은 아닙니다.
실제 판정에는 예외가 있습니다. locked VMA가 발견되면 일반 회수에서 빼야 하며, reference 검사 자체를 확정할 수 없으면 보존할 수 있습니다. executable file mapping은 첫 사용에도 activation할 수 있습니다. v6.18의 FOLIOREF_* 결과를 오래된 PAGEREF_* 이름과 비교할 때에는 이름뿐 아니라 branch도 확인해야 합니다. 특히 옛 version의 swap-backed 조기 activation을 v6.18의 ordinary anon 표에 가져오면 안 됩니다.
active list에서는 inactive처럼 두 번의 기회를 판정하는 것이 주목적이 아닙니다. active anon을 aging하여 inactive에 공급하고, file의 경우 참조된 executable 내용을 추가 보호할 수 있습니다. active에서 한 바퀴 돌았다는 사실은 영구 보호를 뜻하지 않습니다.
Software access는 또 다른 경로입니다
file read·write나 swap-in처럼 kernel이 사용 사실을 아는 경로에서는 folio_mark_accessed()를 호출합니다. 이 helper도 첫 관찰에서 referenced를 남기고, inactive이면서 이미 referenced인 folio를 재관찰하면 activation을 시도하는 식으로 동작합니다. activation 후 referenced를 정리하는 software 경로와 reclaim이 activation하면서 referenced를 남기는 경로를 같은 상태 전이로 합치면 안 됩니다.
reclaim이 activation하면서 mark를 남기는 것은 나중에 다시 inactive로 내려왔을 때 사용 이력을 빠르게 회복하는 데 도움이 됩니다. software 경로는 active이지만 referenced가 없던 folio에도 referenced를 설정할 수 있습니다. 반면 이미 unevictable인 folio는 사용 사실을 표시할 수 있어도 일반 active list로 승격시키지 않습니다.
folio가 아직 실제 LRU에 들어가지 않고 per-CPU add batch에 대기할 수도 있습니다. 이 경우에는 이미 list에 있는 folio를 옮기는 방법과 다른 처리가 필요합니다. idle 표시가 있었다면 사용이 관찰되었으므로 그 상태도 정리하고 working-set accounting에도 사용 사실을 알립니다.
아래는 v6.18의 전체 helper입니다. 고전 경로에 앞서 drop-behind folio를 무시하고, MGLRU가 활성화되어 있으면 generation reference 갱신으로 돌아가는 branch가 있습니다. 이 조기 반환에는 아래쪽 classic activation과 idle 정리가 적용되지 않습니다.
// SPDX-License-Identifier: GPL-2.0-only
/*
* linux/mm/swap.c
*
* Copyright (C) 1991, 1992, 1993, 1994 Linus Torvalds
*/
/*
* This file contains the default values for the operation of the
* Linux VM subsystem. Fine-tuning documentation can be found in
* Documentation/admin-guide/sysctl/vm.rst.
* Started 18.12.91
* Swap aging added 23.2.95, Stephen Tweedie.
* Buffermem limits added 12.3.98, Rik van Riel.
*/
/* Extracted unchanged from Linux v6.18, mm/swap.c:455-488.
* Complete named function; surrounding kernel context is required.
* Source: https://github.com/torvalds/linux/blob/v6.18/mm/swap.c#L455-L488
* License text: GPL-2.0.txt (in this directory).
*/
void folio_mark_accessed(struct folio *folio)
{
if (folio_test_dropbehind(folio))
return;
if (lru_gen_enabled()) {
lru_gen_inc_refs(folio);
return;
}
if (!folio_test_referenced(folio)) {
folio_set_referenced(folio);
} else if (folio_test_unevictable(folio)) {
/*
* Unevictable pages are on the "LRU_UNEVICTABLE" list. But,
* this list is never rotated or maintained, so marking an
* unevictable page accessed has no effect.
*/
} else if (!folio_test_active(folio)) {
/*
* If the folio is on the LRU, queue it for activation via
* cpu_fbatches.lru_activate. Otherwise, assume the folio is in a
* folio_batch, mark it active and it'll be moved to the active
* LRU on the next drain.
*/
if (folio_test_lru(folio))
folio_activate(folio);
else
__lru_cache_activate_folio(folio);
folio_clear_referenced(folio);
workingset_activation(folio);
}
if (folio_test_idle(folio))
folio_clear_idle(folio);
}
lruvec은 Node와 memcg의 교차점입니다
struct lruvec은 node별·memory cgroup별 reclaim 상태를 묶습니다. folio의 node는 physical page metadata에서 얻고, memcg는 folio의 소속을 통해 찾습니다. 이 둘에 대응하는 lruvec을 선택해야 하므로 process 하나에 LRU 하나가 있다고 생각하면 곤란합니다. 여러 process가 같은 file folio를 공유할 수 있고, folio의 소속은 접근하는 process와 별개입니다.
관련 helper인 folio_lruvec()은 folio의 memcg와 folio_pgdat()의 node를 연결해 mem_cgroup_lruvec()으로 찾습니다. memcg를 사용하지 않는 구성에서는 node 자체의 lruvec으로 이어집니다. 특정 process의 현재 cgroup만 보고 이미 존재하는 folio의 list를 골라서는 안 됩니다.
lists[]는 LRU 분류의 시작점이며 lru_lock은 list와 관련 상태의 동시 변경을 보호합니다. anon_cost와 file_cost는 양쪽 회수 비용을 비교할 때 사용합니다. nonresident_age와 refault snapshot은 쫓겨난 page가 얼마나 빨리 돌아오는지 판단하는 working-set 정보입니다. pgdat은 해당 node metadata와 연결하고, congestion 관련 상태는 writeback에 막힌 회수 상황을 전달합니다. 이런 field를 단순 queue 길이 하나로 대체할 수는 없습니다.
Field의 type과 configuration도 구조의 일부입니다
anon_cost·file_cost와 refaults[]·flags는 unsigned long이지만 nonresident_age는 atomic_long_t입니다. 모두 같은 정수처럼 대입하는 구조가 아닙니다. lists는 struct list_head 배열, lru_lock은 spinlock_t, pgdat은 struct pglist_data *입니다. CONFIG_MEMCG가 꺼진 구성에는 이 pgdat member 자체가 없습니다. 동적 실행 중 값이 NULL인 상황과 compile-time member 부재는 구분해야 합니다.
아래는 v6.18의 전체 선언입니다. classic LRU의 공통 field 뒤에 configuration에 따른 MGLRU의 lrugen·mm_state, 그리고 zswap_lruvec_state도 보입니다. 같은 struct에 존재한다고 해서 classic scan이 MGLRU의 generation 정책을 수행한다는 뜻은 아닙니다.
/* SPDX-License-Identifier: GPL-2.0 */
/* Extracted unchanged from Linux v6.18, include/linux/mmzone.h:669-698.
* Full struct declaration; surrounding kernel context is required.
* Source: https://github.com/torvalds/linux/blob/v6.18/include/linux/mmzone.h#L669
* License text: GPL-2.0.txt (in this directory).
*/
struct lruvec {
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_LRU_GEN
/* evictable pages divided into generations */
struct lru_gen_folio lrugen;
#ifdef CONFIG_LRU_GEN_WALKS_MMU
/* to concurrently iterate lru_gen_mm_list */
struct lru_gen_mm_state mm_state;
#endif
#endif /* CONFIG_LRU_GEN */
#ifdef CONFIG_MEMCG
struct pglist_data *pgdat;
#endif
struct zswap_lruvec_state zswap_lruvec_state;
};
List 조작과 folio 수명은 함께 보호해야 합니다
folio_lru_list()는 active·unevictable·swap-backed 상태를 보고 family와 active/inactive index를 정합니다. enum의 배치는 inactive index에 LRU_ACTIVE를 더해 active index를 얻을 수 있도록 구성되어 있습니다. lruvec_add_folio()·삭제 helper는 이 분류에 따라 list와 통계를 함께 갱신합니다.
lruvec_add_folio()와 tail 추가 helper의 차이는 list의 앞과 뒤 중 어느 쪽에 연결하느냐입니다. size accounting은 folio 한 개가 아니라 folio_nr_pages()만큼이며, folio의 zone 번호를 함께 사용합니다. 삭제는 같은 양을 음수로 반영합니다. unevictable은 accounting 대상이지만 일반 add/delete처럼 list head를 연결·해제하지 않으며, tail helper에는 unevictable을 넣지 않는다는 전제가 있습니다. caller는 lruvec lock을 확보한 상태여야 합니다.
아래 네 정의는 v6.18의 전체 code입니다. 고전 list 조작보다 앞에 있는 lru_gen_add_folio()·lru_gen_del_folio()가 처리를 완료하면 helper는 그대로 반환합니다. 따라서 classic list와 generation 구조에 같은 folio를 이중으로 연결하는 순서가 아닙니다.
v6.18 분류 helper · 전체 code · GPL-2.0
/* SPDX-License-Identifier: GPL-2.0 */
/* Extracted unchanged from Linux v6.18, include/linux/mm_inline.h:87-101.
* Complete named function; surrounding kernel context is required.
* Source: https://github.com/torvalds/linux/blob/v6.18/include/linux/mm_inline.h#L87-L101
* License text: GPL-2.0.txt (in this directory).
*/
static __always_inline enum lru_list folio_lru_list(const struct folio *folio)
{
enum lru_list lru;
VM_BUG_ON_FOLIO(folio_test_active(folio) && folio_test_unevictable(folio), folio);
if (folio_test_unevictable(folio))
return LRU_UNEVICTABLE;
lru = folio_is_file_lru(folio) ? LRU_INACTIVE_FILE : LRU_INACTIVE_ANON;
if (folio_test_active(folio))
lru += LRU_ACTIVE;
return lru;
}
/* SPDX-License-Identifier: GPL-2.0 */
/* Extracted unchanged from Linux v6.18, include/linux/mm_inline.h:340-352.
* Complete named function; surrounding kernel context is required.
* Source: https://github.com/torvalds/linux/blob/v6.18/include/linux/mm_inline.h#L340-L352
* License text: GPL-2.0.txt (in this directory).
*/
static __always_inline
void lruvec_add_folio(struct lruvec *lruvec, struct folio *folio)
{
enum lru_list lru = folio_lru_list(folio);
if (lru_gen_add_folio(lruvec, folio, false))
return;
update_lru_size(lruvec, lru, folio_zonenum(folio),
folio_nr_pages(folio));
if (lru != LRU_UNEVICTABLE)
list_add(&folio->lru, &lruvec->lists[lru]);
}
/* SPDX-License-Identifier: GPL-2.0 */
/* Extracted unchanged from Linux v6.18, include/linux/mm_inline.h:354-366.
* Complete named function; surrounding kernel context is required.
* Source: https://github.com/torvalds/linux/blob/v6.18/include/linux/mm_inline.h#L354-L366
* License text: GPL-2.0.txt (in this directory).
*/
static __always_inline
void lruvec_add_folio_tail(struct lruvec *lruvec, struct folio *folio)
{
enum lru_list lru = folio_lru_list(folio);
if (lru_gen_add_folio(lruvec, folio, true))
return;
update_lru_size(lruvec, lru, folio_zonenum(folio),
folio_nr_pages(folio));
/* This is not expected to be used on LRU_UNEVICTABLE */
list_add_tail(&folio->lru, &lruvec->lists[lru]);
}
/* SPDX-License-Identifier: GPL-2.0 */
/* Extracted unchanged from Linux v6.18, include/linux/mm_inline.h:368-380.
* Complete named function; surrounding kernel context is required.
* Source: https://github.com/torvalds/linux/blob/v6.18/include/linux/mm_inline.h#L368-L380
* License text: GPL-2.0.txt (in this directory).
*/
static __always_inline
void lruvec_del_folio(struct lruvec *lruvec, struct folio *folio)
{
enum lru_list lru = folio_lru_list(folio);
if (lru_gen_del_folio(lruvec, folio, false))
return;
if (lru != LRU_UNEVICTABLE)
list_del(&folio->lru);
update_lru_size(lruvec, lru, folio_zonenum(folio),
-folio_nr_pages(folio));
}
대부분의 추가·이동 작업은 folio batch로 모으지만, hot path인 isolate_lru_folios()는 list를 직접 다룹니다. 옛 이름은 isolate_lru_pages()입니다. compaction 역시 migration을 위해 후보를 isolate하고, 최종 free 경로는 아직 LRU에 남은 folio를 제거해야 합니다. 목적이 다른데도 모두 같은 list에 손을 대므로 공통 lock·상태 규칙이 중요합니다.
고전 호출 경로의 add_page_to_lru_list()·del_page_from_lru_list()는 page를 folio helper로 연결하는 wrapper이며, 스스로 lock을 대신 잡아 주는 인터페이스가 아닙니다. compaction의 isolate_migratepages_block()은 migrate 가능한 pageblock 후보를, reclaim의 isolation은 active/inactive scan 후보를 꺼냅니다. batch release 계열과 마지막 folio_put() 계열도 아직 LRU에 남은 object의 연결을 정리해야 합니다. 이런 제거 경로를 새 folio를 추가하는 batch 경로와 같은 사건으로 세어서는 안 됩니다.
isolation은 list ownership을 잠시 바꾸는 것입니다. folio reference를 확보하지 않으면 list 연결이 안정적이어도 object가 사라질 수 있고, reference를 확보했다고 data를 수정할 folio lock까지 얻은 것은 아닙니다. 회수에 실패한 folio를 올바른 list로 되돌리는 작업 역시 isolation과 한 쌍입니다.
batch가 아닌 경로의 실제 호출·reference 순서는 LRU 복귀와 마지막 put에서 고전 source의 전체 함수와 함께 이어서 살펴봅니다.
참고 자료
- Lorenzo Stoakes, The Linux Memory Manager, Early Access 2025, Chapter 11, LRU Vectors.
- Linux v6.18 mm/vmscan.c:
folio_check_references(), active/inactive reclaim. - Linux v6.18 mm/swap.c:
folio_mark_accessed()와 batch 연계. - Linux v6.18 include/linux/mm_inline.h: LRU family와 list 조작.
- Linux v6.18 mm/rmap.c: PTE·PMD의 young 상태와 notifier를 연결하는 reference 검사.
- Linux v6.18 include/linux/mmzone.h:
struct lruvec과 node별 metadata의 연결.