find_vma()가 NULL이 아닌 pointer를 반환했습니다. 이제 원하는 주소를 안전하게 접근해도 될까요? 아직 아닙니다. 이 함수는 그 주소를 포함하는 VMA뿐 아니라 그 뒤에 있는 첫 VMA도 반환할 수 있습니다. 빈 구간에서 얻은 결과를 containment 검사 없이 사용하면 mapping이 없던 주소를 있는 것으로 오인하게 됩니다.
이 반환 계약은 자료구조가 바뀌어도 중요한 경계입니다. 과거 Linux는 주소순 linked list, augmented red-black tree와 작은 cache를 조합했고, upstream v6.18은 Maple Tree를 사용합니다. 둘을 나누어 보면 바뀐 구현과 유지된 의미를 함께 이해할 수 있습니다.
gap을 검색하는 짧은 예
4 KiB page 환경에서 두 VMA가 있다고 가정하겠습니다. A는 [0x10000, 0x14000), B는 [0x20000, 0x24000)입니다. 두 범위 사이에는 mapping이 없는 gap이 있습니다. find_vma(mm, 0x12000)은 A를 반환하고, find_vma(mm, 0x18000)은 B를 반환할 수 있습니다. 후자의 주소는 B의 시작보다 작습니다.
반환값이 주소를 포함하려면 vma->vm_start <= addr까지 확인해야 합니다. 함수가 이미 끝 조건에 맞는 다음 range를 골랐다는 사실만으로 시작 조건도 만족하는 것은 아닙니다. 주소가 마지막 VMA의 끝 이상이면 뒤에 후보가 없으므로 NULL을 반환합니다.
검색 대상이 한 주소가 아니라 range일 때에는 질문을 다시 정해야 합니다. 전체 range가 하나의 VMA에 포함되는지, 적어도 하나와 겹치는지, 여러 VMA로 나누어 순회할 것인지는 다른 계약입니다. current find_vma_intersection()은 overlap 검색을 제공하며 exclusive end를 tree의 inclusive bound에 맞게 변환합니다. 비어 있는 range나 끝주소 overflow를 정상 입력이라고 가정해서는 안 됩니다.
과거에는 list와 tree를 함께 유지했습니다
historical 구현의 mm->mmap은 가장 낮은 주소의 VMA를 가리키고 각 VMA의 vm_prev와 vm_next가 주소순으로 이어졌습니다. 이 구조는 선형 순회와 이웃 접근이 간단하지만 arbitrary address 검색에는 비효율적입니다. 그래서 mm->mm_rb에 각 VMA의 vm_rb node를 연결한 red-black tree도 유지했습니다.
non-overlap invariant가 있으므로 VMA들의 시작과 끝 순서는 서로 일치합니다. historical find_vma()는 vm_end > addr인 후보를 발견하면 더 낮은 주소의 적합 후보를 찾아 왼쪽으로 내려가고, 끝이 이미 지나간 범위라면 오른쪽으로 갑니다. 시작도 주소 이하인 후보를 만나면 containment를 만족하므로 일찍 종료할 수 있습니다.
이 구조는 추상적인 '주소를 key로 한 tree' 이상의 정보를 가집니다. rb_subtree_gap augmentation은 그 subtree에서 mapping 배치에 쓸 수 있는 큰 gap을 요약하여 검색을 줄입니다. 단순히 현재 node의 왼쪽 subtree만의 길이로 설명하면 정확하지 않습니다. 새 이웃 관계가 생기거나 tree가 회전하면 gap 요약도 함께 갱신해야 합니다.
위 설명의 구체적인 historical 대조점은 Linux v5.18 mm/mmap.c입니다. 이것을 v6.18의 field layout이라고 읽지 않도록 버전을 분리해야 합니다.
삽입은 overlap 검사부터 시작합니다
historical find_vma_links()는 새 [addr, end)를 넣을 parent와 child pointer 위치, 그리고 predecessor를 함께 찾습니다. 기존 vm_end > addr이면 왼쪽 후보인데, 이때 기존 vm_start < end까지 성립하면 두 범위는 겹칩니다. 반대로 기존 끝이 새 시작 이하라면 오른쪽으로 가며 그 node를 predecessor 후보로 기억합니다.
이 overlap 검사는 '기존 VMA가 새 VMA의 시작을 포함하는가'만의 검사가 아닙니다. 새 range가 기존 VMA 전체를 덮는 경우에도 막아야 하므로 새 끝과 기존 시작의 비교가 필요합니다. 끝점이 딱 닿는 인접 범위는 half-open 계약에 따라 허용됩니다.
검색이 빈 child pointer에 도달하면 그 slot이 새 node의 연결 위치입니다. predecessor는 오른쪽으로 이동했을 때 갱신합니다. 왼쪽으로 내려간 parent는 새 range보다 뒤쪽 후보이므로 이전 VMA라고 부를 수 없기 때문입니다. 이것이 tree 삽입 위치와 주소순 list의 연결 정보를 한 번에 준비하는 방법입니다.
__vma_link_list()는 앞뒤 pointer와 첫 VMA head를 갱신하고, __vma_link_rb()는 node를 연결하여 balancing과 gap augmentation을 유지합니다. vma_link()는 mm의 VMA count와 file reverse mapping 관계 등도 조율합니다. list에만 넣거나 tree에만 넣는 중간 상태를 외부 reader에게 정상 상태로 공개해서는 안 됩니다.
제거와 data page 해제는 별개입니다
historical v6.0의 __vma_unlink()는 tree에서 node를 지우고 gap 요약을 갱신하는 경로와 __vma_unlink_list()를 연결합니다. list에서는 predecessor와 successor를 연결해 해당 VMA를 건너뛰며, 첫 VMA였다면 mm의 head도 바뀝니다. 마지막에는 cache를 무효화하여 stale VMA를 돌려주지 않게 합니다.
그러나 index에서 node를 제거했다는 사실만으로 모든 PTE, folio reference, reverse mapping과 filesystem callback의 정리가 끝난 것은 아닙니다. munmap()의 전체 작업에는 범위 split, translation 제거, TLB와 page-table 수명 처리, accounting 및 backing 관계의 정리가 포함될 수 있습니다. index helper는 그중 일부를 담당합니다.
현재도 이 경계는 남아 있습니다. Maple Tree에서 range를 지운다고 physical page가 tree에 의해 자동 free되는 것은 아닙니다. 다른 VMA가 같은 page를 mapping하거나 page cache가 reference를 유지할 수 있으므로 translation 제거와 마지막 backing reference 반환은 따로 판단해야 합니다.
삽입과 제거의 전체 code는 VMA 삽입과 여러 index의 유지에서 이어서 읽을 수 있습니다. 여기서는 조회의 계약을 구현과 직접 연결하겠습니다. 아래는 official v6.0 find_vma()의 전체 정의입니다. kernel 의존성이 있는 GPL code이며 원래 SPDX·출처와 code/GPL-2.0.txt를 함께 보존했습니다.
// SPDX-License-Identifier: GPL-2.0-only
/*
* mm/mmap.c
*
* Written by obz.
*
* Address space accounting code <alan@lxorguk.ukuu.org.uk>
*/
/*
* Official Linux v6.0: mm/mmap.c
* Complete function; source lines 2253-2283.
* Body unchanged. Kernel dependencies and configuration are required.
* Source URL, SHA, commit, and license: provenance.json; GPL-2.0.txt.
*/
struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
{
struct rb_node *rb_node;
struct vm_area_struct *vma;
mmap_assert_locked(mm);
/* Check the cache first. */
vma = vmacache_find(mm, addr);
if (likely(vma))
return vma;
rb_node = mm->mm_rb.rb_node;
while (rb_node) {
struct vm_area_struct *tmp;
tmp = rb_entry(rb_node, struct vm_area_struct, vm_rb);
if (tmp->vm_end > addr) {
vma = tmp;
if (tmp->vm_start <= addr)
break;
rb_node = rb_node->rb_left;
} else
rb_node = rb_node->rb_right;
}
if (vma)
vmacache_update(addr, vma);
return vma;
}
vmacache_find()가 실패하여 NULL을 반환한 값이 tree 검색의 초기 후보이기도 합니다. 뒤의 tree loop에서 적합한 끝을 만나면 후보를 저장하며 왼쪽으로 더 내려갑니다. 결과를 cache에 넣더라도 cache hit의 containment 조건은 다시 검사하므로, gap 검색 결과를 저장했다고 gap이 mapping된 것으로 바뀌지 않습니다.
작은 cache는 containment만 빠르게 답했습니다
historical vmacache는 task별 네 개 VMA pointer와 sequence number를 유지했습니다. 주소 hash는 x86-64에서 PMD-sized chunk를 기준으로 시작 slot을 골랐지만 lookup은 네 slot을 모두 순회할 수 있었습니다. 같은 2 MiB chunk에 속한 주소들이 같은 시작 slot을 고르는 것과 그 chunk 전체가 반드시 하나의 VMA에 속하는 것은 다른 이야기입니다.
cache hit는 실제 containment를 확인해야 합니다. tree 검색처럼 '주소 뒤의 첫 VMA'를 cache hit로 삼을 수는 없습니다. 또한 현재 task의 mm에 대한 적절한 사용인지 검사하고 kernel thread 등의 이용은 제외했습니다. 다른 mm을 조회하면서 current task의 오래된 pointer를 무심코 쓰면 잘못된 결과가 됩니다.
mm의 sequence와 task cache의 sequence가 다르면 array를 비우고 새 sequence를 기록합니다. 같을 때 유효한 것이지, 같을 때 invalidation하는 것이 아닙니다. 각 VMA를 제거할 때 모든 thread의 네 slot을 즉시 찾아다니며 지우는 대신 sequence로 다음 lookup의 폐기를 유도한 것입니다. 하지만 이 cache도 VMA 접근에 필요한 mmap locking 자체를 대체하지 않았습니다.
해당 구현은 v5.18 mm/vmacache.c와 vmacache.h에서 확인할 수 있습니다. 이 네-entry cache를 v6.18 VMA lookup의 필수 첫 단계로 그려서는 안 됩니다.
전체 구현은 v6.0 mm_types_task.h와 mm/vmacache.c에 있습니다. hash의 shift는 MMU 구성에서 PMD_SHIFT, 그 밖에서는 PAGE_SHIFT이며, 정확한 macro는 다음과 같습니다.
#define VMACACHE_HASH(addr) ((addr >> VMACACHE_SHIFT) & VMACACHE_MASK)
/* SPDX-License-Identifier: GPL-2.0 */
/*
* Official Linux v6.0: include/linux/mm_types_task.h
* Complete struct; source lines 34-37.
* Body unchanged. Kernel dependencies and configuration are required.
* Source URL, SHA, commit, and license: provenance.json; GPL-2.0.txt.
*/
struct vmacache {
u64 seqnum;
struct vm_area_struct *vmas[VMACACHE_SIZE];
};
// SPDX-License-Identifier: GPL-2.0
/*
* Copyright (C) 2014 Davidlohr Bueso.
*/
/*
* Official Linux v6.0: mm/vmacache.c
* Complete function; source lines 30-33.
* Body unchanged. Kernel dependencies and configuration are required.
* Source URL, SHA, commit, and license: provenance.json; GPL-2.0.txt.
*/
static inline bool vmacache_valid_mm(struct mm_struct *mm)
{
return current->mm == mm && !(current->flags & PF_KTHREAD);
}
// SPDX-License-Identifier: GPL-2.0
/*
* Copyright (C) 2014 Davidlohr Bueso.
*/
/*
* Official Linux v6.0: mm/vmacache.c
* Complete function; source lines 41-59.
* Body unchanged. Kernel dependencies and configuration are required.
* Source URL, SHA, commit, and license: provenance.json; GPL-2.0.txt.
*/
static bool vmacache_valid(struct mm_struct *mm)
{
struct task_struct *curr;
if (!vmacache_valid_mm(mm))
return false;
curr = current;
if (mm->vmacache_seqnum != curr->vmacache.seqnum) {
/*
* First attempt will always be invalid, initialize
* the new cache for this task here.
*/
curr->vmacache.seqnum = mm->vmacache_seqnum;
vmacache_flush(curr);
return false;
}
return true;
}
// SPDX-License-Identifier: GPL-2.0
/*
* Copyright (C) 2014 Davidlohr Bueso.
*/
/*
* Official Linux v6.0: mm/vmacache.c
* Complete function; source lines 61-89.
* Body unchanged. Kernel dependencies and configuration are required.
* Source URL, SHA, commit, and license: provenance.json; GPL-2.0.txt.
*/
struct vm_area_struct *vmacache_find(struct mm_struct *mm, unsigned long addr)
{
int idx = VMACACHE_HASH(addr);
int i;
count_vm_vmacache_event(VMACACHE_FIND_CALLS);
if (!vmacache_valid(mm))
return NULL;
for (i = 0; i < VMACACHE_SIZE; i++) {
struct vm_area_struct *vma = current->vmacache.vmas[idx];
if (vma) {
#ifdef CONFIG_DEBUG_VM_VMACACHE
if (WARN_ON_ONCE(vma->vm_mm != mm))
break;
#endif
if (vma->vm_start <= addr && vma->vm_end > addr) {
count_vm_vmacache_event(VMACACHE_FIND_HITS);
return vma;
}
}
if (++idx == VMACACHE_SIZE)
idx = 0;
}
return NULL;
}
// SPDX-License-Identifier: GPL-2.0
/*
* Copyright (C) 2014 Davidlohr Bueso.
*/
/*
* Official Linux v6.0: mm/vmacache.c
* Complete function; source lines 35-39.
* Body unchanged. Kernel dependencies and configuration are required.
* Source URL, SHA, commit, and license: provenance.json; GPL-2.0.txt.
*/
void vmacache_update(unsigned long addr, struct vm_area_struct *newvma)
{
if (vmacache_valid_mm(newvma->vm_mm))
current->vmacache.vmas[VMACACHE_HASH(addr)] = newvma;
}
validity 검사는 current->mm == mm만 보지 않고 PF_KTHREAD도 제외합니다. 명시적으로 mm을 채택한 kernel thread도 task-local cache의 적용 대상이 아니라는 계약입니다. sequence mismatch에서는 새 sequence를 기록하고 array를 flush한 뒤 이번 lookup은 miss로 반환합니다. update는 계산한 한 slot을 덮지만 find는 그 slot부터 wrap하며 네 slot을 확인합니다. hash 충돌이 곧 lookup 실패는 아니며, 배열에 raw pointer를 보관한다는 사실이 reference 획득을 뜻하지도 않습니다.
Maple Tree가 바꾼 부분과 남긴 계약
v6.18은 mm->mm_mt에 non-overlapping VMA range를 저장합니다. Maple Tree는 여러 range를 한 node에서 다루는 B-tree 계열 구조이며 range lookup, 이웃 순회와 gap 검색을 지원합니다. VMA 내부의 예전 vm_next, vm_prev, vm_rb 조합이 현재 자료구조에 그대로 남아 있는 모델이 아닙니다.
그림은 같은 virtual range를 historical list·tree와 현재 range index로 표현합니다. 앞의 두-VMA 예제와 다른 세-VMA 입력이며, node 내부 배치와 변경 시의 lock 순서는 생략했습니다. file backing의 reverse index는 이 그림에 포함하지 않았습니다.
현재 find_vma()는 mt_find()를 이용하며 mmap lock 보유를 요구합니다. VMA iterator는 다음·이전 range를 순회하는 상태를 보관합니다. VMA의 exclusive end와 Maple Tree의 inclusive index 범위를 맞추는 것도 wrapper의 역할입니다. raw tree API와 VMA helper의 bound 계약을 섞지 않아야 합니다.
Maple Tree가 RCU-safe 조회를 지원해도 VMA pointer가 자동으로 영구 reference를 얻는 것은 아닙니다. 일반적인 helper는 mmap lock을 따르고, fault의 per-VMA 경로는 lock_vma_under_rcu()와 검증 및 fallback을 따릅니다. RCU는 자료구조를 안전하게 찾아가는 방법의 일부이지 permission 검사, 객체 mutation과 page pinning을 한꺼번에 대신하지 않습니다.
자료구조를 바꾼 목적에는 cache 효율과 range 순회 비용 개선이 있지만, 독자가 먼저 지켜야 할 계약은 같습니다. 조회 결과가 주소를 포함하는지, lookup부터 이용까지 어떤 보호가 유지되는지, index 변경과 translation 제거 중 무엇을 수행했는지입니다. 이 세 질문은 tree 이름이 바뀌어도 유효합니다.
다음은 v6.18 find_vma()의 전체 정의입니다. 코드가 짧아져도 반환한 VMA의 시작 경계 검사와 이용 중 보호라는 caller의 책임은 사라지지 않습니다.
// SPDX-License-Identifier: GPL-2.0-only
/*
* mm/mmap.c
*
* Written by obz.
*
* Address space accounting code <alan@lxorguk.ukuu.org.uk>
*/
/*
* Official Linux v6.18: mm/mmap.c
* Complete function; source lines 904-910.
* Body unchanged. Kernel dependencies and configuration are required.
* Source URL, SHA, commit, and license: provenance.json; GPL-2.0.txt.
*/
struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
{
unsigned long index = addr;
mmap_assert_locked(mm);
return mt_find(&mm->mm_mt, &index, ULONG_MAX);
}
참고 자료
- Lorenzo Stoakes, The Linux Memory Manager, Early Access 2025, Chapter 4의 VMA layout, insertion/removal, traversal과 VMA cache 설명.
- Linux v5.18 mmap.c: historical list와 red-black tree 구현
- Linux v5.18 vmacache.c: cache 유효성 및 containment
- Linux v5.18 vmacache.h: sequence invalidation
- Linux v6.18 mmap.c: current find_vma와 VMA iterator
- Linux v6.18 Maple Tree 문서
- Linux v6.18 process address-space locking