자료구조를 이해했다는 것과 자료구조를 안전하게 변경할 수 있다는 것은 다릅니다. 예전 Linux의 VMA는 주소순 list와 red-black tree에 동시에 들어갔습니다. 여기에 gap augmentation, file reverse mapping과 lookup cache까지 더해집니다. 새 VMA를 한 군데에만 연결하면 다른 observer가 보는 주소 공간은 서로 달라집니다.
이 글은 official v6.0의 historical 구현을 기준으로 변경의 순서를 읽습니다. 현재 v6.18의 process VMA index는 Maple Tree이므로 아래 함수를 현행 API로 사용해서는 안 됩니다. 책의 정확한 upstream revision을 확정한 것도 아닙니다. 정의 전체를 읽을 수 있는 고정된 비교 기준을 선택한 것입니다.
삽입 위치와 predecessor를 함께 찾습니다
rb_node는 parent·color를 담는 word와 왼쪽·오른쪽 child pointer를 갖습니다. 정렬은 이 node 자체가 아니라 이를 포함하는 VMA의 범위와 non-overlap invariant가 결정합니다. 다음은 official v6.18 generic rb_node 정의 전체입니다. generic container의 구조와 historical VMA 이용 알고리즘의 tag를 구별합니다.
/* SPDX-License-Identifier: GPL-2.0-or-later */
/*
* Official Linux v6.18: include/linux/rbtree_types.h
* Complete struct; source lines 5-9.
* Body unchanged. Kernel dependencies and configuration are required.
* Source URL, SHA, commit, and license: provenance.json; GPL-2.0.txt.
*/
struct rb_node {
unsigned long __rb_parent_color;
struct rb_node *rb_right;
struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
v6.0 find_vma_links()는 predecessor, parent, 그리고 새 node pointer를 쓸 slot을 반환합니다. 전체 함수는 다음과 같습니다. 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 488-521.
* Body unchanged. Kernel dependencies and configuration are required.
* Source URL, SHA, commit, and license: provenance.json; GPL-2.0.txt.
*/
static int find_vma_links(struct mm_struct *mm, unsigned long addr,
unsigned long end, struct vm_area_struct **pprev,
struct rb_node ***rb_link, struct rb_node **rb_parent)
{
struct rb_node **__rb_link, *__rb_parent, *rb_prev;
mmap_assert_locked(mm);
__rb_link = &mm->mm_rb.rb_node;
rb_prev = __rb_parent = NULL;
while (*__rb_link) {
struct vm_area_struct *vma_tmp;
__rb_parent = *__rb_link;
vma_tmp = rb_entry(__rb_parent, struct vm_area_struct, vm_rb);
if (vma_tmp->vm_end > addr) {
/* Fail if an existing vma overlaps the area */
if (vma_tmp->vm_start < end)
return -ENOMEM;
__rb_link = &__rb_parent->rb_left;
} else {
rb_prev = __rb_parent;
__rb_link = &__rb_parent->rb_right;
}
}
*pprev = NULL;
if (rb_prev)
*pprev = rb_entry(rb_prev, struct vm_area_struct, vm_rb);
*rb_link = __rb_link;
*rb_parent = __rb_parent;
return 0;
}
rb_link의 결과는 단순한 node pointer가 아닙니다. root pointer 또는 parent의 child field를 가리키는 pointer입니다. 그래서 caller가 그 자리에 새 node를 연결할 수 있습니다. 빈 tree에서는 parent와 predecessor가 NULL이며 slot은 root입니다.
기존 VMA의 끝이 새 시작보다 크면 왼쪽 후보를 봅니다. 이때 기존 시작이 새 끝보다 작으면 overlap이므로 -ENOMEM입니다. 주소 부족만이 이 errno의 의미는 아니라는 점이 드러납니다. 기존 끝이 새 시작 이하이면 오른쪽으로 이동하며 predecessor를 갱신합니다. 끝점이 맞닿은 half-open range는 overlap이 아닙니다. 탐색 함수의 mmap_assert_locked()는 최소 보호 전제를 검사할 뿐, 실제 삽입이 read lock만으로 허용된다는 뜻은 아닙니다.
이 helper는 ordinary insertion 외에도 historical split의 __insert_vm_struct(), special mapping의 insert_vm_struct(), 이동에 쓰는 copy_vma(), 기존 mapping을 제거하면서 삽입 위치도 얻는 munmap_vma_range() 계열에서 이용되었습니다. 검색 결과의 pointer가 유효한 동안 변경을 직렬화하는 caller 계약이 필요합니다.
list와 gap을 같은 변경으로 유지합니다
다음은 v6.0 list 연결과 tree 연결의 전체 함수입니다.
// 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 636-643.
* Body unchanged. Kernel dependencies and configuration are required.
* Source URL, SHA, commit, and license: provenance.json; GPL-2.0.txt.
*/
static void
__vma_link(struct mm_struct *mm, struct vm_area_struct *vma,
struct vm_area_struct *prev, struct rb_node **rb_link,
struct rb_node *rb_parent)
{
__vma_link_list(mm, vma, prev);
__vma_link_rb(mm, vma, rb_link, rb_parent);
}
// SPDX-License-Identifier: GPL-2.0-only
/*
* Official Linux v6.0: mm/util.c
* Complete function; source lines 275-291.
* Body unchanged. Kernel dependencies and configuration are required.
* Source URL, SHA, commit, and license: provenance.json; GPL-2.0.txt.
*/
void __vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma,
struct vm_area_struct *prev)
{
struct vm_area_struct *next;
vma->vm_prev = prev;
if (prev) {
next = prev->vm_next;
prev->vm_next = vma;
} else {
next = mm->mmap;
mm->mmap = vma;
}
vma->vm_next = next;
if (next)
next->vm_prev = vma;
}
// 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 595-617.
* Body unchanged. Kernel dependencies and configuration are required.
* Source URL, SHA, commit, and license: provenance.json; GPL-2.0.txt.
*/
void __vma_link_rb(struct mm_struct *mm, struct vm_area_struct *vma,
struct rb_node **rb_link, struct rb_node *rb_parent)
{
/* Update tracking information for the gap following the new vma. */
if (vma->vm_next)
vma_gap_update(vma->vm_next);
else
mm->highest_vm_end = vm_end_gap(vma);
/*
* vma->vm_prev wasn't known when we followed the rbtree to find the
* correct insertion point for that vma. As a result, we could not
* update the vma vm_rb parents rb_subtree_gap values on the way down.
* So, we first insert the vma with a zero rb_subtree_gap value
* (to be consistent with what we did on the way down), and then
* immediately update the gap to the correct value. Finally we
* rebalance the rbtree after all augmented values have been set.
*/
rb_link_node(&vma->vm_rb, rb_parent, rb_link);
vma->rb_subtree_gap = 0;
vma_gap_update(vma);
vma_rb_insert(vma, &mm->mm_rb);
}
list에서는 predecessor가 있으면 그 뒤에 넣고, 없으면 mm->mmap head를 바꿉니다. successor가 있으면 역방향 pointer도 바꿉니다. head·tail·중간 삽입을 같은 코드가 처리하지만 NULL 분기를 생략할 수는 없습니다.
tree에서는 새 VMA 앞의 gap뿐 아니라 다음 VMA 앞의 gap도 바뀝니다. successor가 없으면 highest_vm_end를 갱신합니다. 이 값은 vm_end_gap()을 사용하므로 stack guard 정책을 무시한 단순 최대 byte 주소로만 해석하지 않습니다. 새 node의 rb_subtree_gap을 우선 0으로 두고 실제 predecessor가 연결된 뒤 vma_gap_update()로 요약을 전파합니다. 마지막 augmented insertion은 balancing 중에도 gap 정보를 유지합니다. tree rotation만 올바르면 placement 검색도 저절로 올바르다는 모델은 부족합니다.
file reverse index에는 별도 보호가 있습니다
다음 두 전체 함수는 v6.0 mm/mmap.c에 있습니다.
// 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 670-680.
* Body unchanged. Kernel dependencies and configuration are required.
* Source URL, SHA, commit, and license: provenance.json; GPL-2.0.txt.
*/
static void __insert_vm_struct(struct mm_struct *mm, struct vm_area_struct *vma)
{
struct vm_area_struct *prev;
struct rb_node **rb_link, *rb_parent;
if (find_vma_links(mm, vma->vm_start, vma->vm_end,
&prev, &rb_link, &rb_parent))
BUG();
__vma_link(mm, vma, prev, rb_link, rb_parent);
mm->map_count++;
}
// 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 645-664.
* Body unchanged. Kernel dependencies and configuration are required.
* Source URL, SHA, commit, and license: provenance.json; GPL-2.0.txt.
*/
static void vma_link(struct mm_struct *mm, struct vm_area_struct *vma,
struct vm_area_struct *prev, struct rb_node **rb_link,
struct rb_node *rb_parent)
{
struct address_space *mapping = NULL;
if (vma->vm_file) {
mapping = vma->vm_file->f_mapping;
i_mmap_lock_write(mapping);
}
__vma_link(mm, vma, prev, rb_link, rb_parent);
__vma_link_file(vma);
if (mapping)
i_mmap_unlock_write(mapping);
mm->map_count++;
validate_mm(mm);
}
__insert_vm_struct()는 split 중 이미 file interval tree 관계가 준비된 상황을 전제로 합니다. overlap 발견은 정상적인 user 오류 반환이 아니라 내부 invariant 위반이어서 BUG()로 처리합니다. 검색 helper가 errno를 반환한다는 사실만으로 모든 caller가 이를 recoverable failure로 처리한다고 가정하면 안 됩니다.
반면 vma_link()는 file이 있으면 address_space의 i_mmap write lock을 얻고 process index와 file reverse index를 함께 갱신합니다. file이 없는 VMA에는 같은 file lock을 잡을 이유가 없습니다. map_count 증가와 debug validation도 wrapper의 책임입니다. private file VMA가 anonymous CoW page를 포함할 수 있어도 file offset의 원래 관계를 잃지 않는 이유가 이 이중 index에 있습니다.
제거는 cache 무효화까지 이어집니다
아래는 v6.0 __vma_unlink()와 __vma_unlink_list() 전체입니다.
// 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 682-690.
* Body unchanged. Kernel dependencies and configuration are required.
* Source URL, SHA, commit, and license: provenance.json; GPL-2.0.txt.
*/
static __always_inline void __vma_unlink(struct mm_struct *mm,
struct vm_area_struct *vma,
struct vm_area_struct *ignore)
{
vma_rb_erase_ignore(vma, &mm->mm_rb, ignore);
__vma_unlink_list(mm, vma);
/* Kill the cache */
vmacache_invalidate(mm);
}
// SPDX-License-Identifier: GPL-2.0-only
/*
* Official Linux v6.0: mm/util.c
* Complete function; source lines 293-305.
* Body unchanged. Kernel dependencies and configuration are required.
* Source URL, SHA, commit, and license: provenance.json; GPL-2.0.txt.
*/
void __vma_unlink_list(struct mm_struct *mm, struct vm_area_struct *vma)
{
struct vm_area_struct *prev, *next;
next = vma->vm_next;
prev = vma->vm_prev;
if (prev)
prev->vm_next = next;
else
mm->mmap = next;
if (next)
next->vm_prev = prev;
}
tree에서는 erase와 augmentation을 처리하고 list에서는 이웃을 서로 연결합니다. cache invalidation은 mm의 sequence를 바꾸어 task별 stale pointer의 재사용을 막습니다. 여기에는 data folio를 free하는 코드도 map_count를 감소시키는 코드도 없습니다. 호출자가 전체 unmap 작업에서 수행하는 책임을 이 낮은 helper에 덧붙여 읽어서는 안 됩니다.
현재 Maple Tree는 예전 list/tree 이중 연결을 대체했지만 index 변경, VMA 수명, page-table 제거, TLB invalidation과 backing reference 반환은 여전히 다른 질문입니다. 자료구조의 이름보다 변경 전후에 유지해야 할 invariant를 먼저 읽는 습관은 그대로 유효합니다.
참고 자료
- Lorenzo Stoakes, The Linux Memory Manager, Early Access 2025, Chapter 4의 VMA layout과 insertion/removal 설명.
- Linux v6.0 mmap.c: historical VMA 변경 함수 전체
- Linux v6.0 util.c: VMA list 연결과 제거
- Linux v6.18 rbtree_types.h: generic node 정의
- Linux v6.18 mmap.c: current Maple Tree 기반 구현