# 고전 VMA 조정 코드를 읽는 법: 범위와 object 수명을 함께 봅니다

VMA의 start와 end를 바꾸는 동안 다른 index가 예전 범위를 가리킨다면 rmap 검색과 file invalidation은 잘못된 대상을 찾게 됩니다. 반대로 tree에서만 제거하고 reference를 정리하지 않으면 더 이상 주소 공간에 없는 VMA가 자원을 붙잡습니다. 이 두 문제를 한 함수 안에서 다루는 고전 구현이 `__vma_adjust()`입니다.

이 글에서는 Linux v5.18의 RB-tree 구현을 고정해 구조체와 함수 전체를 읽고, 마지막에 v6.18의 Maple Tree 기반 경로와 비교합니다. 아래 code는 kernel source context를 필요로 하는 실제 정의입니다. standalone 실행 프로그램이나 현재 system에서 측정한 결과는 아닙니다. code의 GPL 조건과 이 글의 독립적인 한국어 해설을 구분하며 [GPL license 원문](code/GPL-2.0.txt)을 함께 둡니다.

## vm_area_struct의 연결들은 서로 다른 index입니다

다음은 [Linux v5.18 include/linux/mm_types.h](https://github.com/torvalds/linux/blob/v5.18/include/linux/mm_types.h)의 `vm_area_struct` 정의 전체입니다. 원 header의 SPDX 식별자는 GPL-2.0입니다. configuration 조건과 마지막 `__randomize_layout`까지 남겼으며 tab만 네 spaces로 표시했습니다. 특정 build의 고정 ABI layout이나 모든 field의 실제 byte offset을 제시하는 자료는 아닙니다.

```c
/* SPDX-License-Identifier: GPL-2.0 */
/* Linux v5.18, include/linux/mm_types.h */
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;
```

`vm_next`·`vm_prev`와 `vm_rb`는 process 주소 순서에 관계합니다. `rb_subtree_gap`은 빈 구간 검색용 요약이며 file page index가 아닙니다. 반면 `shared.rb`·`shared.rb_subtree_last`는 file의 `i_mmap` interval index입니다. `anon_vma_chain`은 같은 VMA가 여러 anonymous ancestry에 연결될 수 있게 합니다. private file mapping에는 file 관계와 anonymous CoW 관계가 동시에 존재할 수 있습니다.

이 version의 `shared` node와 anonymous name pointer는 union을 공유합니다. 그래서 name을 임의로 직접 읽는 대신 해당 helper와 file/anonymous 조건을 지켜야 합니다. `vm_file`·`vm_policy`·anonymous name은 pointer 값 복사만으로 새 object의 수명이 확보되는 field가 아닙니다. `vm_private_data` 역시 driver가 부여한 의미를 일반 allocator가 알 수 있는 field가 아닙니다.

## __vma_adjust 전체에서 제어 흐름을 봅니다

아래는 [Linux v5.18 mm/mmap.c의 __vma_adjust()](https://github.com/torvalds/linux/blob/v5.18/mm/mmap.c) 전체이며 GPL-2.0-only code입니다. THP·uprobe 호출과 debug 경고, 실패 반환, 두 번째 pass를 모두 포함합니다. 함수 이름만 나열한 호출 관계도와 달리 실제 조건과 cleanup을 직접 확인할 수 있습니다.

```c
// SPDX-License-Identifier: GPL-2.0-only
// Linux v5.18, mm/mmap.c. Written by obz.
// Address space accounting code: <alan@lxorguk.ukuu.org.uk>
int __vma_adjust(struct vm_area_struct *vma, unsigned long start,
    unsigned long end, pgoff_t pgoff, struct vm_area_struct *insert,
    struct vm_area_struct *expand)
{
    struct mm_struct *mm = vma->vm_mm;
    struct vm_area_struct *next = vma->vm_next, *orig_vma = vma;
    struct address_space *mapping = NULL;
    struct rb_root_cached *root = NULL;
    struct anon_vma *anon_vma = NULL;
    struct file *file = vma->vm_file;
    bool start_changed = false, end_changed = false;
    long adjust_next = 0;
    int remove_next = 0;

    if (next && !insert) {
        struct vm_area_struct *exporter = NULL, *importer = NULL;

        if (end >= next->vm_end) {
            /*
             * vma expands, overlapping all the next, and
             * perhaps the one after too (mprotect case 6).
             * The only other cases that gets here are
             * case 1, case 7 and case 8.
             */
            if (next == expand) {
                /*
                 * The only case where we don't expand "vma"
                 * and we expand "next" instead is case 8.
                 */
                VM_WARN_ON(end != next->vm_end);
                /*
                 * remove_next == 3 means we're
                 * removing "vma" and that to do so we
                 * swapped "vma" and "next".
                 */
                remove_next = 3;
                VM_WARN_ON(file != next->vm_file);
                swap(vma, next);
            } else {
                VM_WARN_ON(expand != vma);
                /*
                 * case 1, 6, 7, remove_next == 2 is case 6,
                 * remove_next == 1 is case 1 or 7.
                 */
                remove_next = 1 + (end > next->vm_end);
                VM_WARN_ON(remove_next == 2 &&
                       end != next->vm_next->vm_end);
                /* trim end to next, for case 6 first pass */
                end = next->vm_end;
            }

            exporter = next;
            importer = vma;

            /*
             * If next doesn't have anon_vma, import from vma after
             * next, if the vma overlaps with it.
             */
            if (remove_next == 2 && !next->anon_vma)
                exporter = next->vm_next;

        } else if (end > next->vm_start) {
            /*
             * vma expands, overlapping part of the next:
             * mprotect case 5 shifting the boundary up.
             */
            adjust_next = (end - next->vm_start);
            exporter = next;
            importer = vma;
            VM_WARN_ON(expand != importer);
        } else if (end < vma->vm_end) {
            /*
             * vma shrinks, and !insert tells it's not
             * split_vma inserting another: so it must be
             * mprotect case 4 shifting the boundary down.
             */
            adjust_next = -(vma->vm_end - end);
            exporter = vma;
            importer = next;
            VM_WARN_ON(expand != importer);
        }

        /*
         * Easily overlooked: when mprotect shifts the boundary,
         * make sure the expanding vma has anon_vma set if the
         * shrinking vma had, to cover any anon pages imported.
         */
        if (exporter && exporter->anon_vma && !importer->anon_vma) {
            int error;

            importer->anon_vma = exporter->anon_vma;
            error = anon_vma_clone(importer, exporter);
            if (error)
                return error;
        }
    }
again:
    vma_adjust_trans_huge(orig_vma, start, end, adjust_next);

    if (file) {
        mapping = file->f_mapping;
        root = &mapping->i_mmap;
        uprobe_munmap(vma, vma->vm_start, vma->vm_end);

        if (adjust_next)
            uprobe_munmap(next, next->vm_start, next->vm_end);

        i_mmap_lock_write(mapping);
        if (insert) {
            /*
             * Put into interval tree now, so instantiated pages
             * are visible to arm/parisc __flush_dcache_page
             * throughout; but we cannot insert into address
             * space until vma start or end is updated.
             */
            __vma_link_file(insert);
        }
    }

    anon_vma = vma->anon_vma;
    if (!anon_vma && adjust_next)
        anon_vma = next->anon_vma;
    if (anon_vma) {
        VM_WARN_ON(adjust_next && next->anon_vma &&
               anon_vma != next->anon_vma);
        anon_vma_lock_write(anon_vma);
        anon_vma_interval_tree_pre_update_vma(vma);
        if (adjust_next)
            anon_vma_interval_tree_pre_update_vma(next);
    }

    if (file) {
        flush_dcache_mmap_lock(mapping);
        vma_interval_tree_remove(vma, root);
        if (adjust_next)
            vma_interval_tree_remove(next, root);
    }

    if (start != vma->vm_start) {
        vma->vm_start = start;
        start_changed = true;
    }
    if (end != vma->vm_end) {
        vma->vm_end = end;
        end_changed = true;
    }
    vma->vm_pgoff = pgoff;
    if (adjust_next) {
        next->vm_start += adjust_next;
        next->vm_pgoff += adjust_next >> PAGE_SHIFT;
    }

    if (file) {
        if (adjust_next)
            vma_interval_tree_insert(next, root);
        vma_interval_tree_insert(vma, root);
        flush_dcache_mmap_unlock(mapping);
    }

    if (remove_next) {
        /*
         * vma_merge has merged next into vma, and needs
         * us to remove next before dropping the locks.
         */
        if (remove_next != 3)
            __vma_unlink(mm, next, next);
        else
            /*
             * vma is not before next if they've been
             * swapped.
             *
             * pre-swap() next->vm_start was reduced so
             * tell validate_mm_rb to ignore pre-swap()
             * "next" (which is stored in post-swap()
             * "vma").
             */
            __vma_unlink(mm, next, vma);
        if (file)
            __remove_shared_vm_struct(next, file, mapping);
    } else if (insert) {
        /*
         * split_vma has split insert from vma, and needs
         * us to insert it before dropping the locks
         * (it may either follow vma or precede it).
         */
        __insert_vm_struct(mm, insert);
    } else {
        if (start_changed)
            vma_gap_update(vma);
        if (end_changed) {
            if (!next)
                mm->highest_vm_end = vm_end_gap(vma);
            else if (!adjust_next)
                vma_gap_update(next);
        }
    }

    if (anon_vma) {
        anon_vma_interval_tree_post_update_vma(vma);
        if (adjust_next)
            anon_vma_interval_tree_post_update_vma(next);
        anon_vma_unlock_write(anon_vma);
    }

    if (file) {
        i_mmap_unlock_write(mapping);
        uprobe_mmap(vma);

        if (adjust_next)
            uprobe_mmap(next);
    }

    if (remove_next) {
        if (file) {
            uprobe_munmap(next, next->vm_start, next->vm_end);
            fput(file);
        }
        if (next->anon_vma)
            anon_vma_merge(vma, next);
        mm->map_count--;
        mpol_put(vma_policy(next));
        vm_area_free(next);
        /*
         * In mprotect's case 6 (see comments on vma_merge),
         * we must remove another next too. It would clutter
         * up the code too much to do both in one go.
         */
        if (remove_next != 3) {
            /*
             * If "next" was removed and vma->vm_end was
             * expanded (up) over it, in turn
             * "next->vm_prev->vm_end" changed and the
             * "vma->vm_next" gap must be updated.
             */
            next = vma->vm_next;
        } else {
            /*
             * For the scope of the comment "next" and
             * "vma" considered pre-swap(): if "vma" was
             * removed, next->vm_start was expanded (down)
             * over it and the "next" gap must be updated.
             * Because of the swap() the post-swap() "vma"
             * actually points to pre-swap() "next"
             * (post-swap() "next" as opposed is now a
             * dangling pointer).
             */
            next = vma;
        }
        if (remove_next == 2) {
            remove_next = 1;
            end = next->vm_end;
            goto again;
        }
        else if (next)
            vma_gap_update(next);
        else {
            /*
             * If remove_next == 2 we obviously can't
             * reach this path.
             *
             * If remove_next == 3 we can't reach this
             * path because pre-swap() next is always not
             * NULL. pre-swap() "next" is not being
             * removed and its next->vm_end is not altered
             * (and furthermore "end" already matches
             * next->vm_end in remove_next == 3).
             *
             * We reach this only in the remove_next == 1
             * case if the "next" vma that was removed was
             * the highest vma of the mm. However in such
             * case next->vm_end == "end" and the extended
             * "vma" has vma->vm_end == next->vm_end so
             * mm->highest_vm_end doesn't need any update
             * in remove_next == 1 case.
             */
            VM_WARN_ON(mm->highest_vm_end != vm_end_gap(vma));
        }
    }
    if (insert && file)
        uprobe_mmap(insert);

    validate_mm(mm);

    return 0;
}
```

## 세 번의 경계를 따라 읽습니다

첫 경계는 아직 tree를 고치기 전입니다. internal next와 insert 유무에 따라 전체 흡수, 부분 경계 이동, case 8의 pointer 교환을 결정합니다. exporter에만 anonymous ancestry가 있으면 importer가 이를 이어받도록 clone을 준비합니다. 이 allocation이 실패하면 이후 tree 조정을 진행하지 않습니다. 이 시점과 이미 index를 갱신한 뒤의 cleanup을 같은 실패 단계로 묶으면 안 됩니다.

두 번째 경계는 index 보호입니다. file mapping에서는 uprobe에 옛 범위를 알린 뒤 `i_mmap_rwsem`을 write로 잡습니다. 필요한 anon_vma lock도 잡고 해당 VMA의 interval node들을 제거합니다. 그 뒤에야 start/end/pgoff와 이웃의 경계를 바꾸고 node들을 새 범위로 재삽입합니다. file lock과 anon_vma lock을 놓기 전에 주소 list/tree의 제거 또는 insertion도 처리합니다. `flush_dcache_mmap_lock()` 계열의 architecture hook과 mmap semaphore, TLB flush는 같은 동작이 아닙니다.

세 번째 경계는 흡수된 object의 수명 종료입니다. 주소 및 rmap index에서 숨긴 뒤 file reference, anonymous chain, map count, policy를 정리하고 VMA object를 해제합니다. `next`를 free한 뒤 그 pointer로 다음 이웃을 읽지 않고 살아 있는 `vma->vm_next`에서 다시 구합니다. case 8에서는 교환 후의 vma가 살아남은 successor이므로 `next = vma`로 gap 갱신 대상을 다시 정합니다.

## case 6은 같은 범위 수정의 두 pass입니다

독립 예로 process의 VA page 범위가 P=`[10, 14)`, M=`[14, 18)`, N=`[18, 22)`라고 하겠습니다. M의 속성을 바꾸어 양옆과 같아지면 첫 pass는 P를 page 18까지 늘리고 M object를 제거합니다. 두 번째 pass는 살아 있는 P를 page 22까지 늘리고 N object를 제거합니다. page 내용을 두 번 복사하는 과정이 아니라 VMA metadata와 reference를 두 단계로 흡수하는 과정입니다.

첫 pass에서는 `remove_next=2`이고 end를 중간 VMA의 끝으로 제한합니다. cleanup 뒤 `remove_next=1`과 다음 생존 VMA의 끝으로 바꾸어 다시 시작합니다. 마지막에 주소 순서는 바뀌지 않았으므로 살아남은 RB node를 무조건 제거·재삽입하지는 않습니다. 그러나 subtree gap, `highest_vm_end`, file/anonymous interval endpoint는 새 상태를 반영해야 합니다. 이 고전 구현의 `CONFIG_DEBUG_VM_RB`가 켜졌을 때 `validate_mm()`은 주소 list/tree와 gap 불변식을 점검하지만 lock의 역할을 대신하지 않습니다.

## v6.18에서는 구현의 단위를 다시 잡습니다

[Linux v6.18 mm/vma.c](https://github.com/torvalds/linux/blob/v6.18/mm/vma.c)는 VMA iterator, `vma_merge_struct`, `vma_prepare()`·`vma_complete()`로 작업을 나눕니다. 위 구조체의 next/prev/RB node와 고전 case별 지역변수는 현대 구현의 동일한 field 목록이 아닙니다. 또한 per-VMA write 준비가 추가되는 현대 경로에 고전 mmap write lock 설명만으로 모든 보호 규칙을 충족한다고 가정해서는 안 됩니다.

version 사이에 유지되는 질문은 명확합니다. 어떤 object가 살아남고, 어떤 index를 어느 lock 아래에서 바꾸며, 어떤 reference를 마지막에 반납하는지입니다. 이 세 가지를 함수 전체와 연결하면 긴 code를 줄이지 않고도 부분 경로의 의미를 추적할 수 있습니다.

본문에 수록한 v5.18 정의의 원 파일 전체는 [다운로드 가능한 source 목록](code/README.md)에서 읽으실 수 있습니다. 원 header·license를 보존한 파일과 본문의 표시용 code block을 구분하며, 이 파일 목록이 kernel의 모든 build dependency를 제공하는 것은 아닙니다.

## 참고 자료

Lorenzo Stoakes, *The Linux Memory Manager*, Chapter 5 §5.1.3. 고전 정의와 구현은 [Linux v5.18 mm_types.h](https://github.com/torvalds/linux/blob/v5.18/include/linux/mm_types.h), [mm/mmap.c](https://github.com/torvalds/linux/blob/v5.18/mm/mmap.c)를 사용했습니다. 현대 보호 범위는 [v6.18 Process Addresses](https://www.kernel.org/doc/html/v6.18/mm/process_addrs.html)와 해당 tag의 source를 구분해 참고하실 수 있습니다.