# VMA 삽입은 pointer 하나를 잇는 작업이 아닙니다

자료구조를 이해했다는 것과 자료구조를 안전하게 변경할 수 있다는 것은 다릅니다. 예전 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 정의](https://github.com/torvalds/linux/blob/v6.18/include/linux/rbtree_types.h#L5-L9) 전체입니다. generic container의 구조와 historical VMA 이용 알고리즘의 tag를 구별합니다.

<!-- include-code:code/v6_18_rb_node.c -->

[v6.0 `find_vma_links()`](https://github.com/torvalds/linux/blob/v6.0/mm/mmap.c#L488-L521)는 predecessor, parent, 그리고 새 node pointer를 쓸 slot을 반환합니다. 전체 함수는 다음과 같습니다. kernel 내부 GPL code이며 원래 SPDX·출처와 `code/GPL-2.0.txt`를 함께 보존했습니다.

<!-- include-code:code/v6_0_find_vma_links.c -->

`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 연결](https://github.com/torvalds/linux/blob/v6.0/mm/util.c#L275-L291)과 [tree 연결](https://github.com/torvalds/linux/blob/v6.0/mm/mmap.c#L595-L643)의 전체 함수입니다.

<!-- include-code:code/v6_0___vma_link.c -->

<!-- include-code:code/v6_0___vma_link_list.c -->

<!-- include-code:code/v6_0___vma_link_rb.c -->

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`](https://github.com/torvalds/linux/blob/v6.0/mm/mmap.c#L645-L680)에 있습니다.

<!-- include-code:code/v6_0___insert_vm_struct.c -->

<!-- include-code:code/v6_0_vma_link.c -->

`__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()`](https://github.com/torvalds/linux/blob/v6.0/mm/mmap.c#L682-L690)와 [`__vma_unlink_list()`](https://github.com/torvalds/linux/blob/v6.0/mm/util.c#L293-L305) 전체입니다.

<!-- include-code:code/v6_0___vma_unlink.c -->

<!-- include-code:code/v6_0___vma_unlink_list.c -->

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 변경 함수 전체](https://github.com/torvalds/linux/blob/v6.0/mm/mmap.c)
- [Linux v6.0 util.c: VMA list 연결과 제거](https://github.com/torvalds/linux/blob/v6.0/mm/util.c)
- [Linux v6.18 rbtree_types.h: generic node 정의](https://github.com/torvalds/linux/blob/v6.18/include/linux/rbtree_types.h)
- [Linux v6.18 mmap.c: current Maple Tree 기반 구현](https://github.com/torvalds/linux/blob/v6.18/mm/mmap.c)