reclaim이 folio 하나를 선택했을 때에는 시작 virtual address가 없습니다. page table을 정방향으로 걷는 대신, 그 folio를 mapping할 가능성이 있는 VMA를 찾아야 합니다. 이 반대 방향의 index가 reverse mapping, 즉 rmap입니다.
folio마다 VMA 목록을 두지 않는 이유
fork() 직후 같은 anonymous folio가 parent와 child의 서로 다른 VMA에 연결됩니다. child가 일부 page만 쓰면 해당 page는 새 folio가 되지만 다른 page는 계속 공유합니다. VMA는 split·merge될 수도 있습니다. folio마다 VMA list를 직접 보관하면 경계를 한 번 바꿀 때 연결된 page들을 대량으로 수정해야 합니다.
Linux는 folio와 VMA 사이에 anon_vma를 둡니다. folio는 mapping field를 통해 이 중간 객체에 연결되고, VMA 경계가 바뀌면 객체의 interval index를 조정합니다. 개별 folio pointer를 전부 바꾸지 않고도 후보 집합을 유지할 수 있습니다.
active pointer와 ancestry list
VMA의 anon_vma는 새 anonymous folio를 연결할 active 대상을 정합니다. anon_vma_chain list는 이 VMA가 공유했을 가능성이 있는 여러 anon_vma와의 관계입니다. 새 CoW page를 어디에 연결할지와 과거 공유 page를 어디서 찾을지를 분리한 표현입니다. 아직 anonymous folio가 필요하지 않았으면 active pointer는 NULL일 수 있습니다.
anon_vma_chain, 줄여서 AVC 하나는 특정 VMA와 특정 anon_vma를 연결합니다. same_vma는 VMA list의 node, rb는 anon_vma interval tree의 node이며 양 끝 object pointer를 함께 보관합니다. 하나의 node를 여러 list나 tree에 동시에 넣을 수 없으므로 연결마다 AVC가 필요합니다.
VMA 쪽 list와 anon_vma 쪽 tree의 보호 범위도 다릅니다. list 변경에는 mmap/page-table 쪽의 설치 동기화가 관계하고, interval tree의 변경에는 anon_vma root rwsem이 관계합니다. 같은 AVC에 들어 있는 두 node라는 이유로 한쪽 lock이 다른쪽의 모든 변경까지 보호한다고 가정해서는 안 됩니다. caller가 관계를 설치하는지, tree를 검색하는지에 맞춰 필요한 보호를 확인해야 합니다.
interval의 끝은 inclusive last입니다
VMA의 VA 범위는 [vm_start, vm_end)이지만 rmap interval은 vm_pgoff부터 vm_pgoff + vma_pages - 1까지입니다. rb_subtree_last도 subtree의 최대 inclusive last를 저장합니다. exclusive end를 그대로 넣으면 다음 page까지 검색하게 되며, 반대로 1을 두 번 빼면 마지막 page를 놓칩니다.
debug field의 cached start·last는 이 index의 일관성을 검증하기 위한 값이지 또 다른 주소 변환 원본이 아닙니다. fork한 VMA들은 같은 interval로 여러 번 검색될 수 있고 split한 VMA들은 서로 다른 interval을 맡을 수 있습니다.
root lock, child count, object reference
anon_vma의 parent와 root는 fork ancestry를 표현합니다. lock helper는 전체 계보가 공유하는 root의 rwsem을 사용합니다. 따라서 child가 살아 있는 동안 root lock object도 살아 있어야 합니다. 최초 객체의 parent와 root가 자기 자신을 가리키는 것은 이 규칙의 단일-object 경우입니다.
num_children은 ancestry 관계, num_active_vmas는 새 folio의 active 대상으로 사용하는 VMA 수, refcount는 anon_vma object 수명을 나타냅니다. folio mapcount와는 다릅니다. AVC list가 길다는 사실도 현재 모든 page가 모든 ancestor folio를 mapping한다는 증명은 아닙니다.
file rmap은 연결 층이 더 얇습니다
file folio는 address_space에 연결되며 i_mmap interval tree가 file offset을 mapping할 수 있는 VMA를 찾습니다. VMA가 file의 정체성을 잃지 않으므로 AVC ancestry 층 대신 VMA의 tree node를 직접 사용합니다. i_pages XArray는 offset에서 cached folio를 찾는 별도 index입니다.
private file VMA는 file 관계를 유지하면서 일부 PTE가 anonymous CoW folio를 가리킬 수 있습니다. 한 VMA에 file rmap과 anonymous rmap 관계가 동시에 있을 수 있는 이유입니다. rmap의 결과를 정확한 현재 mapping 목록으로 간주하지 말아야 하는 이유도 여기서 드러납니다.
세 객체의 전체 정의를 함께 읽습니다
아래 코드는 책의 지면에서 code를 옮긴 것이 아니라 공식 Linux v6.0 source의 전체 struct 정의입니다. 원본 지면의 vm_next·vm_prev와 field 배치는 이 historical tag와 대응하지만, 이것만으로 책 전체의 exact tag를 확정하지는 않습니다. 뒤의 v6.18 link는 별도로 고정한 비교 자료이며 두 version의 layout을 섞어 읽지 않으셔야 합니다. Kernel context에 의존하는 source이므로 standalone C 실습이나 실행 검증 결과가 아닙니다.
먼저 vm_area_struct 전체에서 anonymous 관계와 file 관계가 같은 객체에 들어 있다는 점을 확인해 보겠습니다. vm_file이 있다고 anon_vma_chain이 항상 비어 있어야 하는 것은 아닙니다. 반대로 AVC list가 길다는 사실을 현재 process의 PID ancestry를 완전히 복원하는 규칙으로 사용하지도 않습니다. List는 현재 유지하는 backing 계보의 연결입니다.
/* SPDX-License-Identifier: GPL-2.0 */
/* Upstream Linux v6.0: include/linux/mm_types.h:403-483
* Exact source lines, not a restored book listing or standalone program.
*/
struct vm_area_struct {
/* The first cache line has the info for VMA tree walking. */
unsigned long vm_start; /* Our start address within vm_mm. */
unsigned long vm_end; /* The first byte after our end address
within vm_mm. */
/* linked list of VM areas per task, sorted by address */
struct vm_area_struct *vm_next, *vm_prev;
struct rb_node vm_rb;
/*
* Largest free memory gap in bytes to the left of this VMA.
* Either between this VMA and vma->vm_prev, or between one of the
* VMAs below us in the VMA rbtree and its ->vm_prev. This helps
* get_unmapped_area find a free area of the right size.
*/
unsigned long rb_subtree_gap;
/* Second cache line starts here. */
struct mm_struct *vm_mm; /* The address space we belong to. */
/*
* Access permissions of this VMA.
* See vmf_insert_mixed_prot() for discussion.
*/
pgprot_t vm_page_prot;
unsigned long vm_flags; /* Flags, see mm.h. */
/*
* For areas with an address space and backing store,
* linkage into the address_space->i_mmap interval tree.
*
* For private anonymous mappings, a pointer to a null terminated string
* containing the name given to the vma, or NULL if unnamed.
*/
union {
struct {
struct rb_node rb;
unsigned long rb_subtree_last;
} shared;
/*
* Serialized by mmap_sem. Never use directly because it is
* valid only when vm_file is NULL. Use anon_vma_name instead.
*/
struct anon_vma_name *anon_name;
};
/*
* A file's MAP_PRIVATE vma can be in both i_mmap tree and anon_vma
* list, after a COW of one of the file pages. A MAP_SHARED vma
* can only be in the i_mmap tree. An anonymous MAP_PRIVATE, stack
* or brk vma (with NULL file) can only be in an anon_vma list.
*/
struct list_head anon_vma_chain; /* Serialized by mmap_lock &
* page_table_lock */
struct anon_vma *anon_vma; /* Serialized by page_table_lock */
/* Function pointers to deal with this struct. */
const struct vm_operations_struct *vm_ops;
/* Information about our backing store: */
unsigned long vm_pgoff; /* Offset (within vm_file) in PAGE_SIZE
units */
struct file * vm_file; /* File we map to (can be NULL). */
void * vm_private_data; /* was vm_pte (shared mem) */
#ifdef CONFIG_SWAP
atomic_long_t swap_readahead_info;
#endif
#ifndef CONFIG_MMU
struct vm_region *vm_region; /* NOMMU mapping region */
#endif
#ifdef CONFIG_NUMA
struct mempolicy *vm_policy; /* NUMA policy for the VMA */
#endif
struct vm_userfaultfd_ctx vm_userfaultfd_ctx;
} __randomize_layout;
anon_vma의 rwsem은 root를 통해 공유합니다. num_children에는 root의 self-parent 관계도 포함되지만 새 fork child의 counter까지 무조건 1이라는 뜻은 아닙니다. Child는 parent를 다른 anon_vma로 바꾸므로, 실제 연결을 만든 operation과 함께 counter를 읽으셔야 합니다. rb_root의 pointer LSB를 mm_take_all_locks()가 표시용으로 쓰는 주석도 있어, lock 없이 내부 node를 일반 pointer처럼 해석하면 안 됩니다.
/* SPDX-License-Identifier: GPL-2.0 */
/* Upstream Linux v6.0: include/linux/rmap.h:31-67
* Exact source lines, not a restored book listing or standalone program.
*/
struct anon_vma {
struct anon_vma *root; /* Root of this anon_vma tree */
struct rw_semaphore rwsem; /* W: modification, R: walking the list */
/*
* The refcount is taken on an anon_vma when there is no
* guarantee that the vma of page tables will exist for
* the duration of the operation. A caller that takes
* the reference is responsible for clearing up the
* anon_vma if they are the last user on release
*/
atomic_t refcount;
/*
* Count of child anon_vmas. Equals to the count of all anon_vmas that
* have ->parent pointing to this one, including itself.
*
* This counter is used for making decision about reusing anon_vma
* instead of forking new one. See comments in function anon_vma_clone.
*/
unsigned long num_children;
/* Count of VMAs whose ->anon_vma pointer points to this object. */
unsigned long num_active_vmas;
struct anon_vma *parent; /* Parent of this anon_vma */
/*
* NOTE: the LSB of the rb_root.rb_node is set by
* mm_take_all_locks() _after_ taking the above lock. So the
* rb_root must only be read/written after taking the above lock
* to be sure to see a valid next pointer. The LSB bit itself
* is serialized by a system wide lock only visible to
* mm_take_all_locks() (mm_all_locks_mutex).
*/
/* Interval tree of private "related" vmas */
struct rb_root_cached rb_root;
};
AVC의 rb_subtree_last는 interval의 inclusive last를 기준으로 읽습니다. VA의 exclusive vm_end와 같은 값이 아닙니다. 두 page를 vm_pgoff=1024부터 나타낸다면 interval은 [1024,1025]이며 1026은 포함하지 않습니다. CONFIG_DEBUG_VM_RB field도 잘라 내지 않고 아래 정의에 남겼습니다. 이는 configuration별 layout을 생략하지 않았다는 뜻이지 특정 configuration으로 build했다는 뜻은 아닙니다.
/* SPDX-License-Identifier: GPL-2.0 */
/* Upstream Linux v6.0: include/linux/rmap.h:82-91
* Exact source lines, not a restored book listing or standalone program.
*/
struct anon_vma_chain {
struct vm_area_struct *vma;
struct anon_vma *anon_vma;
struct list_head same_vma; /* locked by mmap_lock & page_table_lock */
struct rb_node rb; /* locked by anon_vma->rwsem */
unsigned long rb_subtree_last;
#ifdef CONFIG_DEBUG_VM_RB
unsigned long cached_vma_start, cached_vma_last;
#endif
};
File 쪽에서는 서로 다른 struct file이 같은 address_space에 도달할 수 있습니다. i_pages는 mapping이 없어도 file data를 찾게 하고, i_mmap은 그 file offset을 mapping하는 VMA 후보를 찾습니다. MAP_PRIVATE의 CoW 뒤에도 VMA가 file tree에 남는 것과 CoW page 자체가 anonymous인 것은 양립합니다. Truncate 경로의 invalidation을 일반적인 기존 크기 내 pwrite()와 동일시하지는 않겠습니다.
Code 출처는 Linux v6.0 mm_types.h와 rmap.h입니다. 원래 SPDX·copyright notice를 source 파일에 보존했고 COPYING, GPL-2.0, Linux-syscall-note를 함께 두었습니다. Line 범위·source SHA·commit은 chapter 검수 기록의 code manifest에서 추적합니다.
참고 자료
Lorenzo Stoakes, The Linux Memory Manager, Chapter 7 §7.0.1–§7.0.4.3. Linux v6.18 include/linux/rmap.h, mm/interval_tree.c를 참고하실 수 있습니다.