Rmap -1- (Reverse Mapping)

<kernel v5.0>

Rmap -1- (Reverse Mapping)

Rmap은 물리 주소를 사용하여 가상 주소에 역 매핑하는 방법이다. 역방향 매핑하는 항목들은 anon 메모리에 해당하는 페이지들로만 제한한다. 공유된 anon 페이지를 사용하는 모든 태스크의 각 VM에서 사용하는 페이지 테이블 엔트리를 찾아 매핑을 제거할 때 사용한다.

  • 위의 역방향 매핑과 반대인 페이지 테이블은 가상 주소를 사용하여 물리 주소에 매핑하는 방법이다.

 

다음 그림은 정방향 매핑과 역방향 매핑을 사용한 rmap의 컨셉을 보여준다.

 

rmap 종류

다음 그림과 같이 유저 페이지 종류에 따라 다른 3 가지 타입의 rmap을 구성할 수 있다.

  • Anonymous 매핑
    • 유저 스택, 유저 힙 및 CoW 페이지가 할당될 때 사용한다.
  • KSM 매핑
    • VM_MERGEABLE 영역인 경우 물리 메모리 데이터가 동일한 경우 유저 anon 페이지를 병합할 수 있다.
  • File 매핑
    • 코드, 라이브러리, 데이터 파일, 공유 메모리, 디바이스 등이 로드 및 할당될 때 사용한다.

 

Fault 핸들러와 rmap 생성

사용자 메모리 할당이 요청되면 커널은 가상 주소 공간을 사용한다는 표식으로 VMA를 생성 또는 확장하고, 실제 물리 메모리는 할당하지 않는다. 그런 후 해당 유저 영역에 접근 시 fault가 발생하게 되는데, 이 때 fault 핸들러는 fault가 발생한 주소가 사용자 주소 공간의 어떤 VMA에 위치했는지 알아온다. 그리고 fault가 발생한 주소가 유효한 경우 뒤늦게 물리 페이지를 할당하는 lazy 할당 정책을 사용한다. 이 때 정방향 매핑을 사용하여 페이지 테이블 엔트리를 갱신하고, 역방향 매핑인 rmap도 추가한다.

 

다음 그림은 페이지 할당 요청 후 실제 메모리 사용 시 fault 핸들러에 의해 페이지 할당 및 매핑/역매핑이 수행되는 과정을 보여준다.

 

다음 그림과 같이 anon rmap 상태를 간략히 보여준다.

  • 정방향 매핑 시 여러 단계의 페이지 테이블(pgd -> pud -> pmd -> pte)을 사용한다.
  • 역방향 매핑 시 각 anon 페이지들은 AV(anon_vma 구조체)에 연결되어 표현된다.
    • 아래 그림에서 VMA와 AV가 AVC(anon_vma_chain)을 통해 연결되는데 AVC 표기는 생략하였다.
    • 연결될 때 page->mapping에 PAGE_MAPPING_ANON 플래그가 추가된 anon_vma 구조체 주소가 사용된다.

 

가상 주소 공간 관리(VMA 관리)

유저 프로세스 각각마다 가상 주소 공간이 존재하며, 이들의 매핑을 위해 페이지 테이블이 사용된다.  유저 가상 주소 공간에는 유저가 요청한 여러 개의 가상 주소 영역이 등록되는데, 이들이 vm_area_struct 구조체를 할당하여 표현되는 VMA이다.

  • 참고로 프로세스에 child 스레드들이 존재하는 경우 child 스레드들도 task_struct로 관리된다. 그러나 사용자 주소 공간은 유저 프로세스 공간을 같이 공유하며 사용한다. 따라서 모든 child 스레드들의 mm_struct는 동일하다.

 

VMA가 관리되는 자료 구조는 RB 트리와 리스트 두 개의 자료 구조를 사용하여 관리되며, 두 개를 사용하는 이유는 빈 공간 범위 검색에 효과적으로 대응되는 방법이 이 두 개의 자료 구조를 사용하는 방식이다.

  • RB 트리
    • 시작 주소의 검색에 빠르게 대응할 수 있다.
  • 리니어 링크드 리스트
    • VMA 들이 주소로 정렬되어 관리되어 있어, 정렬된 VMA들 간의 free 공간 사이즈를 빠르게 알아낼 수 있다.

 

다음 그림은 유저 주소 공간에 3개의 가상 주소 영역(VMA)이 등록되어 관리되는 모습을 보여준다.

 

다음과 같이 프로세스(pid 1481)에 등록된 VMA들을 보여준다. 파일과 관련없는 anon vma를 확인해본다.

  • 표기되는 순서대로 다음과 같다.
    • 시작 가상 주소(vma->vm_start)
    • 끝 가상 주소(vma->vm_end)
    • 플래그 여부 (VM_READ, VM_WRITE, VM_EXEC, VM_MAYSHARE)
    • 파일이 매핑된 경우 오프셋 주소(vma->vm_pgoff << PAGE_SHIFT)
    • 파일이 매핑된 경우 디바이스의 메이저 및 마이너 번호
    • 파일이 매핑된 경우 inode 번호
    • 파일이 매핑된 경우 파일명, anon vma의 경우 공백 또는 괄호 []로 표기
      •  heap, vvar, vdso, stack 영역들은 특별하게 괄호 []를 통해 표시되는 anon vma이다.
$ cat /proc/1481/maps
00400000-004ec000 r-xp 00000000 b3:05 26                                 /bin/bash
004fb000-004ff000 r--p 000eb000 b3:05 26                                 /bin/bash
004ff000-00508000 rw-p 000ef000 b3:05 26                                 /bin/bash
00508000-00512000 rw-p 00000000 00:00 0
30d7f000-30f1d000 rw-p 00000000 00:00 0                                  [heap]
7f87324000-7f8732d000 r-xp 00000000 b3:05 2173                           /lib/aarch64-linux-gnu/libnss_files-2.24.so
7f8732d000-7f8733c000 ---p 00009000 b3:05 2173                           /lib/aarch64-linux-gnu/libnss_files-2.24.so
7f8733c000-7f8733d000 r--p 00008000 b3:05 2173                           /lib/aarch64-linux-gnu/libnss_files-2.24.so
7f8733d000-7f8733e000 rw-p 00009000 b3:05 2173                           /lib/aarch64-linux-gnu/libnss_files-2.24.so
7f8733e000-7f87344000 rw-p 00000000 00:00 0
7f87344000-7f8734d000 r-xp 00000000 b3:05 2197                           /lib/aarch64-linux-gnu/libnss_nis-2.24.so
7f87370000-7f8737f000 ---p 00012000 b3:05 2243                           /lib/aarch64-linux-gnu/libnsl-2.24.so
(...생략...)
7f8771b000-7f8771c000 r--p 00000000 b3:05 7362                           /usr/lib/locale/C.UTF-8/LC_IDENTIFICATION
7f8771c000-7f87721000 rw-p 00000000 00:00 0
7f87721000-7f87722000 r--p 00000000 00:00 0                              [vvar]
7f87722000-7f87723000 r-xp 00000000 00:00 0                              [vdso]
7f87723000-7f87724000 r--p 0001c000 b3:05 2253                           /lib/aarch64-linux-gnu/ld-2.24.so
7f87724000-7f87726000 rw-p 0001d000 b3:05 2253                           /lib/aarch64-linux-gnu/ld-2.24.so
7fcdc27000-7fcdc48000 rw-p 00000000 00:00 0                              [stack]

 

다음 명령을 사용하면 위의 정보를 더 자세히 볼 수 있다.

$ cat /proc/1481/smaps
00400000-004ec000 r-xp 00000000 b3:05 26                                 /bin/bash
Size:                944 kB
Rss:                 936 kB
Pss:                 311 kB
Shared_Clean:        936 kB
Shared_Dirty:          0 kB
Private_Clean:         0 kB
Private_Dirty:         0 kB
Referenced:          936 kB
Anonymous:             0 kB
AnonHugePages:         0 kB
Shared_Hugetlb:        0 kB
Private_Hugetlb:       0 kB
Swap:                  0 kB
SwapPss:               0 kB
KernelPageSize:        4 kB
MMUPageSize:           4 kB
Locked:                0 kB
VmFlags: rd ex mr mw me dw
(...생략...) 
7fcdc27000-7fcdc48000 rw-p 00000000 00:00 0                              [stack]
Size:                132 kB
Rss:                  32 kB
Pss:                  32 kB
Shared_Clean:          0 kB
Shared_Dirty:          0 kB
Private_Clean:         0 kB
Private_Dirty:        32 kB
Referenced:           32 kB
Anonymous:            32 kB
AnonHugePages:         0 kB
Shared_Hugetlb:        0 kB
Private_Hugetlb:       0 kB
Swap:                  0 kB
SwapPss:               0 kB
KernelPageSize:        4 kB
MMUPageSize:           4 kB
Locked:                0 kB
VmFlags: rd wr mr mw me gd ac

 

VM 플래그

다음은 vma->vm_flags에서 사용되는 VM 플래그들이다.

  • 우측에 표시된 두 글자는 maps 또는 smaps로 출력 시 약식 표기법이다.
VM_READ         rd
VM_WRITE        wr
VM_EXEC         ex
VM_SHARED       sh
VM_MAYREAD      mr
VM_MAYWRITE     mw
VM_MAYEXEC      me
VM_MAYSHARE     ms
VM_GROWSDOWN    gd
VM_UFFD_MISSING 
VM_PFNMAP       pf
VM_DENYWRITE    dw
VM_UFFD_WP      
VM_LOCKED       lo
VM_IO           io
VM_SEQ_READ     sr
VM_RAND_READ    rr
VM_DONTCOPY     dc
VM_DONTEXPAND   de
VM_LOCKONFAULT  
VM_ACCOUNT      ac
VM_NORESERVE    nr
VM_HUGETLB      ht
VM_SYNC         sf
VM_ARCH_1       ar
VM_WIPEONFORK   wf
VM_DONTDUMP     dd
VM_SOFTDIRTY    sd
VM_MIXEDMAP     mm
VM_HUGEPAGE     hg
VM_NOHUGEPAGE   nh
VM_MERGEABLE	mg

 

anonymous 타입 VMA

anonymous 타입 VMA(vm_area_struct)를 관리하기 위해 AV(anon_vma 구조체)가 사용되고 VMA와 AV의 연결에 AVC(anon_vma_chain 구조체)를 사용하여 관리한다.

  • AV는 많은 VMA를 포함시킬 수 있도록 RB 트리를 사용하여 관리한다.
  • VMA는 AV를 포함시킬 수 있도록 여전히 리니어 링크드 리스트를 사용하여 관리한다.

 

다음 그림은 VMA와 AV간의 연결에 AVC가 사용되는 모습을 보여준다.

 

anon_vma 병합

VMA가 인접하고 속성이 비슷한 경우 anon_vma를 별도로 생성하지 않고 기존 것을 그대로 사용할 수 있다.

 


Fork된 child 프로세스에서의 관리

다음 그림은 fork된 child 프로세스와의 관계를 보여준다.

 

다음 그림은 두 번의 child 프로세스를 fork하여 부모 VMA가 clone되고 AV가 생성된 후 링크된 모습을 보여준다.

 

다음 그림과 같이 AV의 부모(parent) 관계가 표현된다.

 

다음 그림과 같이 AV의 처음 생성된 루트(root) 관계가 표현된다.

 

다음 그림과 같이 VMA가 1:1 직접 가리키는 관계가 표현된다.

 

rmap을 사용한 효율적인 매핑 제거

공유 페이지의 매핑을 제거할 때 정방향 매핑만을 사용하려면 정방향 매핑에 사용된 모든 수 많은 사용자 페이지 테이블을 뒤져야 하는 문제가 있다. 이 때 역방향 매핑을 사용하여 VMA(가상 주소 영역)를 찾고,  VMA에서 사용되는 사용자 페이지 테이블에서만 매핑 해제하는 방식을 사용하면 빠르게 제거할 수 있다.

 

다음 그림은 부모 프로세스와 fork된 child 프로세스 사이에서 공유된 페이지의 매핑을 제거할 때 검색할 VMA #1, #2를 찾을 수 있도록 괸리되는 모습을 보여준다.

  • 자식 프로세스 B가 fork될 때 VMA#1을 clone하여 VMA #2를 만든다.
  • 새롭게 자식 프로세스 B가 할당한 페이지들은 각각의 VMA#2, VMA#3에서 생성되어 관리되는 모습을 알 수 있다.

 


anon_vma 초기화

anon_vma_init()

mm/rmap.c

void __init anon_vma_init(void)
{
        anon_vma_cachep = kmem_cache_create("anon_vma", sizeof(struct anon_vma),
                        0, SLAB_DESTROY_BY_RCU|SLAB_PANIC, anon_vma_ctor);
        anon_vma_chain_cachep = KMEM_CACHE(anon_vma_chain, SLAB_PANIC);
}

anon_vma 및 anon_vma_chain 구조체 할당 목적으로 slub 캐시를 생성한다.

  • 코드 라인 3에서 anon_vma 구조체 할당 목적으로 slub 캐시를 생성하고, 초기화 시 anon_vma_ctor() 함수가 호출되게 하다.
  • 코드 라인 5에서 anon_vma_chain 구조체 할당 목적으로 slub 캐시를 생성한다.

 

anon_vma 할당

anon_vma_alloc()

mm/rmap.c

static inline struct anon_vma *anon_vma_alloc(void)
{
        struct anon_vma *anon_vma;

        anon_vma = kmem_cache_alloc(anon_vma_cachep, GFP_KERNEL);
        if (anon_vma) {
                atomic_set(&anon_vma->refcount, 1);
                anon_vma->degree = 1;   /* Reference for first vma */
                anon_vma->parent = anon_vma;
                /*
                 * Initialise the anon_vma root to point to itself. If called
                 * from fork, the root will be reset to the parents anon_vma.
                 */
                anon_vma->root = anon_vma;
        }

        return anon_vma;
}

anon_vma를 할당한다.

  • 할당한 anon_vma 구조체의 멤버 degree를 1로 설정하여 가장 선두에 위치했음을 식별하게하고, parent 및 root도 자기 자신을 가리키게 한다.

 

anon_vma 해제

anon_vma_free()

mm/rmap.c

static inline void anon_vma_free(struct anon_vma *anon_vma)
{
        VM_BUG_ON(atomic_read(&anon_vma->refcount));

        /*
         * Synchronize against page_lock_anon_vma_read() such that
         * we can safely hold the lock without the anon_vma getting
         * freed.
         *
         * Relies on the full mb implied by the atomic_dec_and_test() from
         * put_anon_vma() against the acquire barrier implied by
         * down_read_trylock() from page_lock_anon_vma_read(). This orders:
         *
         * page_lock_anon_vma_read()    VS      put_anon_vma()
         *   down_read_trylock()                  atomic_dec_and_test()
         *   LOCK                                 MB
         *   atomic_read()                        rwsem_is_locked()
         *
         * LOCK should suffice since the actual taking of the lock must
         * happen _before_ what follows.
         */
        might_sleep();
        if (rwsem_is_locked(&anon_vma->root->rwsem)) {
                anon_vma_lock_write(anon_vma);
                anon_vma_unlock_write(anon_vma);
        }

        kmem_cache_free(anon_vma_cachep, anon_vma);
}

anon_vma를 할당 해제한다.

 


anon_vma 준비

유저용 free 페이지를 준비할 때 anon_vma를 준비하도록 요청하는 곳은 많은데, 그 중 주요 루틴들은 다음과 같다.

  • fault 시 메모리 할당 관련
    • do_cow_fault()
    • wp_page_copy()
    • do_anonymous_page()
  • 스택 확장 관련
    • expand_upwards()
    • expand_downwards()
  • migration 관련
    • migrate_vma_insert_page()

 

anon_vma_prepare()

include/linux/rmap.h

static inline int anon_vma_prepare(struct vm_area_struct *vma)
{
        if (likely(vma->anon_vma))
                return 0;

        return __anon_vma_prepare(vma);
}

vma 영역에 anon_vma를 준비한다.

  • 코드 라인 3~4에서 vma에 이미 anon_vma가 이미 준비되어 사용중인 경우 성공(0)을 반환한다.
  • 코드 라인 6에서 vma에 anon 페이지들을 관리하는 anon_vma 자료 구조를 준비하여 어태치한다.

 

__anon_vma_prepare()

mm/rmap.c

/**
 * __anon_vma_prepare - attach an anon_vma to a memory region
 * @vma: the memory region in question
 *
 * This makes sure the memory mapping described by 'vma' has
 * an 'anon_vma' attached to it, so that we can associate the
 * anonymous pages mapped into it with that anon_vma.
 *
 * The common case will be that we already have one, which
 * is handled inline by anon_vma_prepare(). But if
 * not we either need to find an adjacent mapping that we
 * can re-use the anon_vma from (very common when the only
 * reason for splitting a vma has been mprotect()), or we
 * allocate a new one.
 *
 * Anon-vma allocations are very subtle, because we may have
 * optimistically looked up an anon_vma in page_lock_anon_vma_read()
 * and that may actually touch the spinlock even in the newly
 * allocated vma (it depends on RCU to make sure that the
 * anon_vma isn't actually destroyed).
 *
 * As a result, we need to do proper anon_vma locking even
 * for the new allocation. At the same time, we do not want
 * to do any locking for the common case of already having
 * an anon_vma.
 *
 * This must be called with the mmap_sem held for reading.
 */
int __anon_vma_prepare(struct vm_area_struct *vma)
{
        struct mm_struct *mm = vma->vm_mm;
        struct anon_vma *anon_vma, *allocated;
        struct anon_vma_chain *avc;

        might_sleep();

        avc = anon_vma_chain_alloc(GFP_KERNEL);
        if (!avc)
                goto out_enomem;

        anon_vma = find_mergeable_anon_vma(vma);
        allocated = NULL;
        if (!anon_vma) {
                anon_vma = anon_vma_alloc();
                if (unlikely(!anon_vma))
                        goto out_enomem_free_avc;
                allocated = anon_vma;
        }

        anon_vma_lock_write(anon_vma);
        /* page_table_lock to protect against threads */
        spin_lock(&mm->page_table_lock);
        if (likely(!vma->anon_vma)) {
                vma->anon_vma = anon_vma;
                anon_vma_chain_link(vma, avc, anon_vma);
                /* vma reference or self-parent link for new root */
                anon_vma->degree++;
                allocated = NULL;
                avc = NULL;
        }
        spin_unlock(&mm->page_table_lock);
        anon_vma_unlock_write(anon_vma);

        if (unlikely(allocated))
                put_anon_vma(allocated);
        if (unlikely(avc))
                anon_vma_chain_free(avc);

        return 0;

 out_enomem_free_avc:
        anon_vma_chain_free(avc);
 out_enomem:
        return -ENOMEM;
}

vma에 anon 페이지들을 관리하는 anon_vma 자료 구조를 준비하여 어태치한다. anon_vma는 anon_vma_chain을 통해 vma에 연결된다.

  • 코드 라인 9~11에서 anon_vma_chain을 할당한다.
  • 코드 라인 13~20에서 이웃한 vma 영역의 병합 가능한 anon_vma를 찾아 가져오거나 발견하지 못하면 anon_vma를 새로 할당한다.
  • 코드 라인 22~34에서 락을 획득 후 vma에 처음 anon_vma를 연결하는 경우 anon_vma 및 anon_vma_chain을 vma에 어태치한다.
  • 코드 라인 36~39에서 낮은 확률로 할당한 anon_vma 및 anon_vma_chain을 vma에 어태치하지 못한 경우 할당하였던 anon_vma와 anon_vma_chain을 할당 해제한다.

 

다음 그림은 처음 anon_vma 사용 시 anon_vma를 할당하여 준비하는 과정을 보여준다.

 

find_mergeable_anon_vma()

mm/mmap.c

/*
 * find_mergeable_anon_vma is used by anon_vma_prepare, to check
 * neighbouring vmas for a suitable anon_vma, before it goes off
 * to allocate a new anon_vma.  It checks because a repetitive
 * sequence of mprotects and faults may otherwise lead to distinct
 * anon_vmas being allocated, preventing vma merge in subsequent
 * mprotect.
 */
struct anon_vma *find_mergeable_anon_vma(struct vm_area_struct *vma)
{
        struct anon_vma *anon_vma;
        struct vm_area_struct *near;

        near = vma->vm_next;
        if (!near)
                goto try_prev;

        anon_vma = reusable_anon_vma(near, vma, near);
        if (anon_vma)
                return anon_vma;
try_prev:
        near = vma->vm_prev;
        if (!near)
                goto none;

        anon_vma = reusable_anon_vma(near, near, vma);
        if (anon_vma)
                return anon_vma;
none:
        /*
         * There's no absolute need to look only at touching neighbours:
         * we could search further afield for "compatible" anon_vmas.
         * But it would probably just be a waste of time searching,
         * or lead to too many vmas hanging off the same anon_vma.
         * We're trying to allow mprotect remerging later on,
         * not trying to minimize memory used for anon_vmas.
         */
        return NULL;
}

이웃한 vma에 병합 가능한 anon_vma가 있으면 해당 anon_vma를 반환한다.

  • 코드 라인 6~12에서 @vma  영역 -> 이웃한 영역에 같이 사용할 수 있는 vma가 있는지 확인하여 존재하는 경우 이웃한 영역의 anon_vma를 반환한다.
  • 코드 라인 13~20에서 이웃한 영역 -> @vma 영역에 같이 사용할 수 있는 vma가 있는지 확인하여 존재하는 경우 이웃한 영역의 anon_vma를 반환한다.

 

다음 그림은 vma에 이웃한 두 VMA를 대상으로 병합 가능한 anon_vma를 반환하는 모습을 보여준다.

 

reusable_anon_vma()

mm/mmap.c

/*
 * Do some basic sanity checking to see if we can re-use the anon_vma
 * from 'old'. The 'a'/'b' vma's are in VM order - one of them will be
 * the same as 'old', the other will be the new one that is trying
 * to share the anon_vma.
 *
 * NOTE! This runs with mm_sem held for reading, so it is possible that
 * the anon_vma of 'old' is concurrently in the process of being set up
 * by another page fault trying to merge _that_. But that's ok: if it
 * is being set up, that automatically means that it will be a singleton
 * acceptable for merging, so we can do all of this optimistically. But
 * we do that READ_ONCE() to make sure that we never re-load the pointer.
 *
 * IOW: that the "list_is_singular()" test on the anon_vma_chain only
 * matters for the 'stable anon_vma' case (ie the thing we want to avoid
 * is to return an anon_vma that is "complex" due to having gone through
 * a fork).
 *
 * We also make sure that the two vma's are compatible (adjacent,
 * and with the same memory policies). That's all stable, even with just
 * a read lock on the mm_sem.
 */
static struct anon_vma *reusable_anon_vma(struct vm_area_struct *old, struct vm_area_struct *a, struu
ct vm_area_struct *b)
{
        if (anon_vma_compatible(a, b)) {
                struct anon_vma *anon_vma = READ_ONCE(old->anon_vma);

                if (anon_vma && list_is_singular(&old->anon_vma_chain))
                        return anon_vma;
        }
        return NULL;
}

@a anon 영역과 @b anon 영역의 anon_vma이 병합 가능한 경우 @old 영역의 anon_vma를 찾아 반환한다.

  • 코드 라인 4에서 @a anon 영역과 @b anon 영역이 병합 가능한 경우이다.
  • 코드 라인 5~8에서 @old 영역의 anon_vma가 존재하고, @old 영역에 avc가 하나만 등록되어 있는 경우 anon_vma를 반환한다.

 

anon_vma_compatible()

mm/mmap.c

/*
 * Rough compatbility check to quickly see if it's even worth looking
 * at sharing an anon_vma.
 *
 * They need to have the same vm_file, and the flags can only differ
 * in things that mprotect may change.
 *
 * NOTE! The fact that we share an anon_vma doesn't _have_ to mean that
 * we can merge the two vma's. For example, we refuse to merge a vma if
 * there is a vm_ops->close() function, because that indicates that the
 * driver is doing some kind of reference counting. But that doesn't
 * really matter for the anon_vma sharing case.
 */
static int anon_vma_compatible(struct vm_area_struct *a, struct vm_area_struct *b)
{
        return a->vm_end == b->vm_start &&
                mpol_equal(vma_policy(a), vma_policy(b)) &&
                a->vm_file == b->vm_file &&
                !((a->vm_flags ^ b->vm_flags) & ~(VM_READ|VM_WRITE|VM_EXEC|VM_SOFTDIRTY)) &&
                b->vm_pgoff == a->vm_pgoff + ((b->vm_start - a->vm_start) >> PAGE_SHIFT);
}

 

다음 두 anon 영역에 대해 같이 병합되어 사용될 수 있는지 여부를 반환한다. 다음 조건들을 모두 허용하는 경우 병합 가능(1)을 반환한다.

  • a 영역 다음 b 영역으로 두 영역이 붙어있다.
  • 두 영역의 vma policy가 같다.
  • 두 영역에서 read, write, exec, softdirty 이외의 플래그 사용이 서로 같다.
  • 두 영역의 vm_file이 같고, vm_pgoff가 a와 b영역 순서대로 지정되어 있다.

 

다음과 같이 가상 주소 영역의 두 VMA 영역이 같이 사용될 수 있는지 여부를 알아내는 과정을 보여준다.

 


anon_vma_chain를 사용한 링크

anon_vma_chain_alloc()

mm/rmap.c

static inline struct anon_vma_chain *anon_vma_chain_alloc(gfp_t gfp)
{
        return kmem_cache_alloc(anon_vma_chain_cachep, gfp);
}

kmem 캐시에 준비된 anon_vma_chain 구조체를 할당한다.

 

anon_vma_chain_free()

mm/rmap.c

static void anon_vma_chain_free(struct anon_vma_chain *anon_vma_chain)
{
        kmem_cache_free(anon_vma_chain_cachep, anon_vma_chain);
}

anon_vma_chain 구조체를 할당 해제하여 kmem 캐시로 돌려보낸다.

 

anon_vma_chain_link()

mm/rmap.c

static void anon_vma_chain_link(struct vm_area_struct *vma,
                                struct anon_vma_chain *avc,
                                struct anon_vma *anon_vma)
{
        avc->vma = vma;
        avc->anon_vma = anon_vma;
        list_add(&avc->same_vma, &vma->anon_vma_chain);
        anon_vma_interval_tree_insert(avc, &anon_vma->rb_root);
}

vma 및 anon_vma 간에 avc를 사용하여 링크시킨다.

  • 코드 라인 5~6에서 @avc가 @vma 및 @anon_vma를 가리킬 수 있도록 지정한다.
  • 코드 라인 7에서 vma의 anon_vma_chain 리스트에 @avc를 추가한다.
  • 코드 라인 8에서 @anon_vma의 RB 트리에 @avc를 추가한다.

 

다음 그림은 vma 및 anon_vma가 avc를 통해 링크되는 모습을 보여준다.

 


anon 페이지에 매핑 추가

page_add_anon_rmap()

mm/rmap.c

/**
 * page_add_anon_rmap - add pte mapping to an anonymous page
 * @page:       the page to add the mapping to
 * @vma:        the vm area in which the mapping is added
 * @address:    the user virtual address mapped
 * @compound:   charge the page as compound or small page
 *
 * The caller needs to hold the pte lock, and the page must be locked in
 * the anon_vma case: to serialize mapping,index checking after setting,
 * and to ensure that PageAnon is not being upgraded racily to PageKsm
 * (but PageKsm is never downgraded to PageAnon).
 */
void page_add_anon_rmap(struct page *page,
        struct vm_area_struct *vma, unsigned long address, bool compound)
{
        do_page_add_anon_rmap(page, vma, address, compound ? RMAP_COMPOUND : 0);
}

공유 anon 페이지에 역방향 매핑을 추가한다.

 

do_page_add_anon_rmap()

주의: 이 함수는 do_swap_page()로부터 비공유 anon 페이지에 대한 역방향 매핑을 추가할 때에만 사용된다. 그 외의 경우는 위 page_add_anon_rmap() 함수를 사용해야 한다.

mm/rmap.c

/*
 * Special version of the above for do_swap_page, which often runs
 * into pages that are exclusively owned by the current process.
 * Everybody else should continue to use page_add_anon_rmap above.
 */
void do_page_add_anon_rmap(struct page *page,
        struct vm_area_struct *vma, unsigned long address, int flags)
{
        bool compound = flags & RMAP_COMPOUND;
        bool first;

        if (compound) {
                atomic_t *mapcount;
                VM_BUG_ON_PAGE(!PageLocked(page), page);
                VM_BUG_ON_PAGE(!PageTransHuge(page), page);
                mapcount = compound_mapcount_ptr(page);
                first = atomic_inc_and_test(mapcount);
        } else {
                first = atomic_inc_and_test(&page->_mapcount);
        }

        if (first) {
                int nr = compound ? hpage_nr_pages(page) : 1;
                /*
                 * We use the irq-unsafe __{inc|mod}_zone_page_stat because
                 * these counters are not modified in interrupt context, and
                 * pte lock(a spinlock) is held, which implies preemption
                 * disabled.
                 */
                if (compound)
                        __inc_node_page_state(page, NR_ANON_THPS);
                __mod_node_page_state(page_pgdat(page), NR_ANON_MAPPED, nr);
        }
        if (unlikely(PageKsm(page)))
                return;

        VM_BUG_ON_PAGE(!PageLocked(page), page);

        /* address might be in next vma when migration races vma_adjust */
        if (first)
                __page_set_anon_rmap(page, vma, address,
                                flags & RMAP_EXCLUSIVE);
        else
                __page_check_anon_rmap(page, vma, address);
}

anon 페이지에 역방향 매핑을 추가한다.

  • 코드 라인 4에서 플래그에 compound 요청이 있었는지 여부를 확인한다.
  • 코드 라인 7~15에서 해당 페이지에 대한 매핑 카운트를 1 증가시키고 처음 매핑 여부를 알아온다.
  • 코드 라인 17~28에서 첫 매핑 시 nr_anon_mapped 카운터를 페이지 수만큼 증가시킨다. compound 페이지인 경우 nr_anon_thps 카운터도 1 증가시킨다.
  • 코드 라인 29~30에서 낮은 확률로 ksm 페이지인 경우 함수를 빠져나간다.
  • 코드 라인 35~39에서 첫 매핑인 경우 페이지를 새 anonymous rmap으로 매핑한다. 그 외의 경우는 디버그 이외에는 아무것도 수행하지 않는다.

 

page_add_new_anon_rmap()

mm/rmap.c

/**
 * page_add_new_anon_rmap - add pte mapping to a new anonymous page
 * @page:       the page to add the mapping to
 * @vma:        the vm area in which the mapping is added
 * @address:    the user virtual address mapped
 * @compound:   charge the page as compound or small page
 *
 * Same as page_add_anon_rmap but must only be called on *new* pages.
 * This means the inc-and-test can be bypassed.
 * Page does not have to be locked.
 */
void page_add_new_anon_rmap(struct page *page,
        struct vm_area_struct *vma, unsigned long address, bool compound)
{
        int nr = compound ? hpage_nr_pages(page) : 1;

        VM_BUG_ON_VMA(address < vma->vm_start || address >= vma->vm_end, vma);
        __SetPageSwapBacked(page);
        if (compound) {
                VM_BUG_ON_PAGE(!PageTransHuge(page), page);
                /* increment count (starts at -1) */
                atomic_set(compound_mapcount_ptr(page), 0);
                __inc_node_page_state(page, NR_ANON_THPS);
        } else {
                /* Anon THP always mapped first with PMD */
                VM_BUG_ON_PAGE(PageTransCompound(page), page);
                /* increment count (starts at -1) */
                atomic_set(&page->_mapcount, 0);
        }
        __mod_node_page_state(page_pgdat(page), NR_ANON_MAPPED, nr);
        __page_set_anon_rmap(page, vma, address, 1);
}

태스크 전용 anon 페이지에 rmap을 지정한다.

  • 코드 라인 7에서 새로 할당 받은 anon 페이지이므로 PG_swapbacked 플래그를 추가한다.
  • 코드 라인 8~12에서 compound 페이지인 경우 컴파운드 매핑 카운터를 0으로 리셋하고, NR_ANON_THPS 카운터를 증가시킨다.
  • 코드 라인 13~18에서 compound 페이지가 아닌 경우 매핑 카운터를 0으로 리셋한다.
  • 코드 라인 19~20에서 NR_ANON_MAPPED 카운터를 증가시키고 anon rmap을 설정한다.

 

__page_set_anon_rmap()

mm/rmap.c

/**
 * __page_set_anon_rmap - set up new anonymous rmap
 * @page:       Page or Hugepage to add to rmap
 * @vma:        VM area to add page to.
 * @address:    User virtual address of the mapping
 * @exclusive:  the page is exclusively owned by the current process
 */
static void __page_set_anon_rmap(struct page *page,
        struct vm_area_struct *vma, unsigned long address, int exclusive)
{
        struct anon_vma *anon_vma = vma->anon_vma;

        BUG_ON(!anon_vma);

        if (PageAnon(page))
                return;

        /*
         * If the page isn't exclusively mapped into this vma,
         * we must use the _oldest_ possible anon_vma for the
         * page mapping!
         */
        if (!exclusive)
                anon_vma = anon_vma->root;

        anon_vma = (void *) anon_vma + PAGE_MAPPING_ANON;
        page->mapping = (struct address_space *) anon_vma;
        page->index = linear_page_index(vma, address);
}

페이지를 anonymous rmap으로 지정한다.

  • 코드 라인 8~9에서 페이지가 이미 anon 매핑이된 경우 함수를 빠져나간다.
  • 코드 라인 16~17에서 페이지가 현재 태스크 전용이 아닌 shared 페이지인 경우 루트 anon_vma를 사용한다.
  • 코드 라인 19~21에서 페이지에 anon 매핑을 한다.
    • page->mapping에는 anon_vma 포인터에 PAGE_PAPPING_ANON 플래그를 더해 지정한다.
    • page->index에는 vma에 지정된 페이지 offset + (주소 pfn – vm 시작 pfn)에 대한 값을 지정한다.

 

다음 그림과 같이 anon 페이지를 rmap에 매핑하는 과정을 보여준다.

  • anon 매핑된 페이지는 PageAnon(page) 함수를 통해 true를 반환한다.

 

linear_page_index()

include/linux/pagemap.h

static inline pgoff_t linear_page_index(struct vm_area_struct *vma,
                                        unsigned long address)
{
        pgoff_t pgoff;
        if (unlikely(is_vm_hugetlb_page(vma)))
                return linear_hugepage_index(vma, address);
        pgoff = (address - vma->vm_start) >> PAGE_SHIFT;
        pgoff += vma->vm_pgoff;
        return pgoff;
}

vma 영역내에서 요청한 주소에 해당하는 페이지 offset을 vma->vm_pgoff를 더한 인덱스 값을 반환한다.

 


페이지에서 rmap 매핑 제거

page_remove_rmap()

mm/rmap.c

/**
 * page_remove_rmap - take down pte mapping from a page
 * @page:       page to remove mapping from
 * @compound:   uncharge the page as compound or small page
 *
 * The caller needs to hold the pte lock.
 */
void page_remove_rmap(struct page *page, bool compound)
{
        if (!PageAnon(page))
                return page_remove_file_rmap(page, compound);

        if (compound)
                return page_remove_anon_compound_rmap(page);

        /* page still mapped by someone else? */
        if (!atomic_add_negative(-1, &page->_mapcount))
                return;

        /*
         * We use the irq-unsafe __{inc|mod}_zone_page_stat because
         * these counters are not modified in interrupt context, and
         * pte lock(a spinlock) is held, which implies preemption disabled.
         */
        __dec_node_page_state(page, NR_ANON_MAPPED);

        if (unlikely(PageMlocked(page)))
                clear_page_mlock(page);

        if (PageTransCompound(page))
                deferred_split_huge_page(compound_head(page));

        /*
         * It would be tidy to reset the PageAnon mapping here,
         * but that might overwrite a racing page_add_anon_rmap
         * which increments mapcount after us but sets mapping
         * before us: so leave the reset to free_unref_page,
         * and remember that it's only reliable while mapped.
         * Leaving it set also helps swapoff to reinstate ptes
         * faster for those pages still in swapcache.
         */
}

페이지에서역방향 매핑(rmap)을 제거한다.

 

page_remove_file_rmap()

mm/rmap.c

static void page_remove_file_rmap(struct page *page, bool compound)
{
        int i, nr = 1;

        VM_BUG_ON_PAGE(compound && !PageHead(page), page);
        lock_page_memcg(page);

        /* Hugepages are not counted in NR_FILE_MAPPED for now. */
        if (unlikely(PageHuge(page))) {
                /* hugetlb pages are always mapped with pmds */
                atomic_dec(compound_mapcount_ptr(page));
                goto out;
        }

        /* page still mapped by someone else? */
        if (compound && PageTransHuge(page)) {
                for (i = 0, nr = 0; i < HPAGE_PMD_NR; i++) {
                        if (atomic_add_negative(-1, &page[i]._mapcount))
                                nr++;
                }
                if (!atomic_add_negative(-1, compound_mapcount_ptr(page)))
                        goto out;
                VM_BUG_ON_PAGE(!PageSwapBacked(page), page);
                __dec_node_page_state(page, NR_SHMEM_PMDMAPPED);
        } else {
                if (!atomic_add_negative(-1, &page->_mapcount))
                        goto out;
        }

        /*
         * We use the irq-unsafe __{inc|mod}_lruvec_page_state because
         * these counters are not modified in interrupt context, and
         * pte lock(a spinlock) is held, which implies preemption disabled.
         */
        __mod_lruvec_page_state(page, NR_FILE_MAPPED, -nr);

        if (unlikely(PageMlocked(page)))
                clear_page_mlock(page);
out:
        unlock_page_memcg(page);
}

파일 페이지의 역방향 매핑(rmap)을 제거한다.

 


Child 프로세스 fork 시 anon_vma 생성 및 연결

anon_vma_fork()

mm/rmap.c

/*
 * Attach vma to its own anon_vma, as well as to the anon_vmas that
 * the corresponding VMA in the parent process is attached to.
 * Returns 0 on success, non-zero on failure.
 */
int anon_vma_fork(struct vm_area_struct *vma, struct vm_area_struct *pvma)
{
        struct anon_vma_chain *avc;
        struct anon_vma *anon_vma;
        int error;

        /* Don't bother if the parent process has no anon_vma here. */
        if (!pvma->anon_vma)
                return 0;

        /* Drop inherited anon_vma, we'll reuse existing or allocate new. */
        vma->anon_vma = NULL;

        /*
         * First, attach the new VMA to the parent VMA's anon_vmas,
         * so rmap can find non-COWed pages in child processes.
         */
        error = anon_vma_clone(vma, pvma);
        if (error)
                return error;

        /* An existing anon_vma has been reused, all done then. */
        if (vma->anon_vma)
                return 0;

        /* Then add our own anon_vma. */
        anon_vma = anon_vma_alloc();
        if (!anon_vma)
                goto out_error;
        avc = anon_vma_chain_alloc(GFP_KERNEL);
        if (!avc)
                goto out_error_free_anon_vma;

        /*
         * The root anon_vma's spinlock is the lock actually used when we
         * lock any of the anon_vmas in this anon_vma tree.
         */
        anon_vma->root = pvma->anon_vma->root;
        anon_vma->parent = pvma->anon_vma;
        /*
         * With refcounts, an anon_vma can stay around longer than the
         * process it belongs to. The root anon_vma needs to be pinned until
         * this anon_vma is freed, because the lock lives in the root.
         */
        get_anon_vma(anon_vma->root);
        /* Mark this anon_vma as the one where our new (COWed) pages go. */
        vma->anon_vma = anon_vma;
        anon_vma_lock_write(anon_vma);
        anon_vma_chain_link(vma, avc, anon_vma);
        anon_vma->parent->degree++;
        anon_vma_unlock_write(anon_vma);

        return 0;

 out_error_free_anon_vma:
        put_anon_vma(anon_vma);
 out_error:
        unlink_anon_vmas(vma);
        return -ENOMEM;
}

fork되어 자식 프로세스에 생성된 @vma를 부모 @pvma들에 존재하는 anon_vma 수 만큼 새로 할당한 후 연결한다. 또한 @vma에 대응하는 anon_vma도 재사용하거나 할당한다.

  • 코드 라인 8~9에서 부모 vma에 anon_vma가 지정된 적이 없으면 성공(0)을 반환한다.
  • 코드 라인 12에서 부모 태스크로부터 상속하여 만든 vma의 anon_vma를 다시 재설정하기 위해 null을 담는다.
  • 코드 라인 18~20에서 부모 vma들에 연결된 anon_vma들과 새로 clone될 vma와 링크한다.
  • 코드 라인 23~24에서 anon_vma가 재사용된 경우 성공(0)을 반환한다.
  • 코드 라인 27~32에서 anon_vma와 anon_vma_chain 구조체를 할당해온다.
  • 코드 라인 38~39에서 anon_vma의 루트와 부모 관계를 지정한다.
  • 코드 라인 45~53에서 anon_vma를 anon_vma_chain을 통해 vm_area_struct와 링크하고 성공(0)을 반환한다.

 

다음 그림은 child 프로세스가 fork되면서 anon_vma_fork()가 세 번 호출되어 나타나는 결과를 보여준다.

 

anon_vma_clone()

이 함수의 주 호출 패스는 다음과 같다.

  • 태스크가 fork되어 부모 태스크의 vma를 clone
    • anon_vma_fork()
  • VMA를 split할 때 기존 VMA를 clone
    • __split_vma()

mm/rmap.c

/*
 * Attach the anon_vmas from src to dst.
 * Returns 0 on success, -ENOMEM on failure.
 *
 * If dst->anon_vma is NULL this function tries to find and reuse existing
 * anon_vma which has no vmas and only one child anon_vma. This prevents
 * degradation of anon_vma hierarchy to endless linear chain in case of
 * constantly forking task. On the other hand, an anon_vma with more than one
 * child isn't reused even if there was no alive vma, thus rmap walker has a
 * good chance of avoiding scanning the whole hierarchy when it searches where
 * page is mapped.
 */
int anon_vma_clone(struct vm_area_struct *dst, struct vm_area_struct *src)
{
        struct anon_vma_chain *avc, *pavc;
        struct anon_vma *root = NULL;

        list_for_each_entry_reverse(pavc, &src->anon_vma_chain, same_vma) {
                struct anon_vma *anon_vma;

                avc = anon_vma_chain_alloc(GFP_NOWAIT | __GFP_NOWARN);
                if (unlikely(!avc)) {
                        unlock_anon_vma_root(root);
                        root = NULL;
                        avc = anon_vma_chain_alloc(GFP_KERNEL);
                        if (!avc)
                                goto enomem_failure;
                }
                anon_vma = pavc->anon_vma;
                root = lock_anon_vma_root(root, anon_vma);
                anon_vma_chain_link(dst, avc, anon_vma);

                /*
                 * Reuse existing anon_vma if its degree lower than two,
                 * that means it has no vma and only one anon_vma child.
                 *
                 * Do not chose parent anon_vma, otherwise first child
                 * will always reuse it. Root anon_vma is never reused:
                 * it has self-parent reference and at least one child.
                 */
                if (!dst->anon_vma && anon_vma != src->anon_vma &&
                                anon_vma->degree < 2)
                        dst->anon_vma = anon_vma;
        }
        if (dst->anon_vma)
                dst->anon_vma->degree++;
        unlock_anon_vma_root(root);
        return 0;

 enomem_failure:
        /*
         * dst->anon_vma is dropped here otherwise its degree can be incorrectly
         * decremented in unlink_anon_vmas().
         * We can safely do this because callers of anon_vma_clone() don't care
         * about dst->anon_vma if anon_vma_clone() failed.
         */
        dst->anon_vma = NULL;
        unlink_anon_vmas(dst);
        return -ENOMEM;
}

@src vma들에 연결된 anon_vma들과 @dst vma를 링크한다.

  • 코드 라인 6에서 @src vma의 anon_vma_chain 리스트에 연결된 avc들을 순회한다.
  • 코드 라인 9~16에서 anon_vma_chain을 할당한다. 만일 할당이 실패하면 root에 락이 걸려있는 경우에 한 해 더 한 번 시도해본다.
  • 코드 라인 17~18에서 root anon_vma를 알아온다.
  • 코드 라인 19에서 @dst vma와 순회 중인 anon_vma 사잏에 새로 할당한 anon_vma_chain을 사용하여 링크한다.
  • 코드 라인 29~31에서 anon_vma 하이라키가 계속 끝 없이 증가되는 것을 막기 위한 패치이다. 첫 번째 child vma는 vma를 가지지 않는 부모 anon_vma를 재 사용하게 한다.
  • 코드 라인 33~34에서 @dst vma에 anon_vma가 지정된 경우 degree를 상향 시킨다.

 

참고

 

 

2 thoughts to “Rmap -1- (Reverse Mapping)”

문영일에게 댓글 남기기 댓글 취소

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다