Rmap -1- (Reverse Mapping)

<kernel v5.15>

Rmap -1- (Reverse Mapping)

Rmap은 물리 주소를 사용하여 가상 주소에 역 매핑하는 방법이다. 이러한 rmap을 사용하여 물리 페이지를 사용하는 모든 VM 및 가상 주소를 찾도록 rmap_walk를 사용하며, 이렇게 찾은 매핑(VM, 가상주소, pte)에 대해 여러 가지 작업을 수행하도록 요청하는 API는 다음과 같다.

  • try_to_unmap()
  • page_mkclean()
  • page_referenced()
  • try_to_migrate()
  • page_mlock()
  • page_make_device_exclusive()
  • remove_migration_ptes()
  • page_idle_clear_pte_refs()
  • try_to_munlock()

 

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

 

rmap 종류

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

  • Anonymous 매핑
    • 유저 스택, 유저 힙 및 CoW 페이지가 할당될 때 사용한다.
    • 아래 그림의 1)번
  • KSM 매핑
    • VM_MERGEABLE 영역인 경우 물리 메모리 데이터가 동일한 경우 유저 anon 페이지를 병합할 수 있다.
    • 아래 그림의 2)번
  • File 매핑
    • 코드, 라이브러리, 데이터 파일, 공유 메모리, 디바이스 등이 로드 및 할당될 때 사용한다.
    • 아래 그림의 3)번
  • non-lru movable 매핑
    • non-lru movable을 지원하는 파일 시스템의 페이지들이 매핑될 때 사용하며, 이 페이지들은 migration이 가능하다.
    • 아래 그림의 3)번
    • 2016년 커널 v4.8-rc1에서 추가되었다.

 

page 구조체의 mapping 멤버에는 위의 구조체 들을 가리키고, 하위 2비트의 플래그를 통해 구분을 할 수 있다.

  • anynymouse 페이지
    • PAGE_MAPPING_ANON(1)
  • ksm 페이지
    • PAGE_MAPPING_KSM(3) = PAGE_MAPPING_ANON(1) + PAGE_MAPPING_MOVABLE(2)
  • file 페이지
    • 하위 비트 모두 0
  • non-lru movable 페이지
    • PAGE_MAPPING_MOVABLE(2)

 

Fault 핸들러와 VMA 생성

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

 

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

 

다음 그림은 fault 핸들러를 통해 최초 VMA가 생성되는 과정을 보여준다.

 

Fault 핸들러와 rmap 생성

 

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

  • 정방향 매핑 시 여러 단계의 페이지 테이블(pgd -> p4d -> 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_TYPESAFE_BY_RCU|SLAB_PANIC|SLAB_ACCOUNT,
                        anon_vma_ctor);
        anon_vma_chain_cachep = KMEM_CACHE(anon_vma_chain,
                        SLAB_PANIC|SLAB_ACCOUNT);
}

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

  • 코드 라인 3에서 anon_vma 구조체 할당 목적으로 slub 캐시를 생성하고, 초기화 시 anon_vma_ctor() 함수가 호출되게 한다.
  • 코드 라인 6에서 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 rwsem 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_lock 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을 할당 해제한다.

 

다음 그림은 AV(anon_vma)를  준비하는데 새로 생성하거나, 기존 AV를 사용하는 과정을 보여준다.

 

다음 그림은 처음 anon_vma 사용 시 AV(anon_vma)를 할당하여 VMA(vm_area_struct)와 AVC(anon_vma_chain)을 통해 연결되는 과정을 보여준다.

 

AV(anon_vma)의 degree & refcount 관리

AV(anon_vma)의 lifetime 관리

  • refcount
    • 참조 카운터로 0이 되면 소멸한다.
    • AVC(anon_vma_chain)을 통해 VMA가 연결될 때마다 증가한다.
  • degree
    • VMA의 owner(vma->anon_vma로 지정된 AV)로 지정될 때마다 degree가 증가된다.
    • AV가 최초 생성되었을 때 1이지만 곧바로 VMA와 연결되고 VMA의 owner로 지정되므로 2로 시작한다.
    • 이 값이 1이 되는 경우는 AV를 재사용(reuse)할 수 있는 상황이다.
      • fork된 자식 프로세스 하나만 동작 중이면서 부모 process가 종료된 경우이다.
      • It has no vma and only one anon_vma child

 

다음 그림은 AV의 degree 및 refcount의 변화를 보여준다.

 

다음 그림은 merged AV의 degree 및 refcount의 변화를 보여준다.

 

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 = NULL;

        /* Try next first. */
        if (vma->vm_next) {
                anon_vma = reusable_anon_vma(vma->vm_next, vma, vma->vm_next);
                if (anon_vma)
                        return anon_vma;
        }

        /* Try prev next. */
        if (vma->vm_prev)
                anon_vma = reusable_anon_vma(vma->vm_prev, vma->vm_prev, vma);

        /*
         * We might reach here with anon_vma == NULL if we can't find
         * any reusable anon_vma.
         * 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 anon_vma;
}

이웃한 vma에 병합 가능한 anon_vma가 있으면 해당 anon_vma를 반환한다. 병합 가능한 anon_vma가 없으면 null을 반환한다. (null을 반환하면 새롭게 생성하여 사용한다)

  • 코드 라인 6~10에서 @vma  영역 다음의 이웃한 vma 영역에 anon_vma를 같이 사용할 수 있으면 해당 이웃 vma가 사용하는 anon_vma를 알아온다.
  • 코드 라인 13~14에서 @vma  영역 이전의 이웃한 vma 영역에 anon_vma를 같이 사용할 수 있으면 해당 이웃 vma가 사용하는 anon_vma를 알아온다.
  • 코드 라인 26에서 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 compatibility 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_ACCESS_FLAGS | 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 이외의 플래그 사용이 서로 같다.
    • #define VM_ACCESS_FLAGS (VM_READ | VM_WRITE | VM_EXEC)
  • 두 영역의 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 (unlikely(PageKsm(page)))
                lock_page_memcg(page);
        else
                VM_BUG_ON_PAGE(!PageLocked(page), page);

        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 ? thp_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))) {
                unlock_page_memcg(page);
                return;
        }

        /* 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~10에서 Ksm 페이지의 경우 페이지와 memcg 바인딩을 위한 락을 건다.
  • 코드 라인 12~20에서 해당 페이지에 대한 매핑 카운트를 1 증가시키고 처음 매핑 여부를 알아온다.
  • 코드 라인 22~33에서 첫 매핑 시 nr_anon_mapped 카운터를 페이지 수만큼 증가시킨다. compound 페이지인 경우 nr_anon_thps 카운터도 1 증가시킨다.
  • 코드 라인 34~37에서 Ksm 페이지의 경우 위에서 건 락을 풀고 함수를 빠져나간다.
  • 코드 라인 40~44에서 첫 매핑인 경우 페이지를 새 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 ? thp_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);
                if (hpage_pincount_available(page))
                        atomic_set(compound_pincount_ptr(page), 0);

                __mod_lruvec_page_state(page, NR_ANON_THPS, nr);
        } 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_lruvec_page_state(page_pgdat(page), NR_ANON_MAPPED, nr);
        __page_set_anon_rmap(page, vma, address, 1);
}

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

  • 코드 라인 7에서 새로 할당 받은 anon 페이지이므로 PG_swapbacked 플래그를 추가한다.
  • 코드 라인 8~15에서 compound 페이지인 경우 컴파운드 매핑 카운터를 0으로 리셋하고, NR_ANON_THPS 카운터를 증가시킨다.
  • 코드 라인 16~21에서 compound 페이지가 아닌 경우 매핑 카운터를 0으로 리셋한다.
  • 코드 라인 22~23에서 NR_ANON_MAPPED 카운터를 증가시키고 페이지에 anon rmap을 설정한다.
    • page->mapping = anon_vma
    • page->index = linear_page_index(vma, address)

 

__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;

        /*
         * page_idle does a lockless/optimistic rmap scan on page->mapping.
         * Make sure the compiler doesn't split the stores of anon_vma and
         * the PAGE_MAPPING_ANON type identifier, otherwise the rmap code
         * could mistake the mapping for a struct address_space and crash.
        /*
        anon_vma = (void *) anon_vma + PAGE_MAPPING_ANON;
        WRITE_ONCE(page->mapping = (struct address_space *) anon_vma);
        page->index = linear_page_index(vma, address);
}

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

  • 코드 라인 8~9에서 페이지가 이미 anon 매핑이된 경우 함수를 빠져나간다.
  • 코드 라인 16~17에서 페이지가 현재 태스크 전용이 아닌 shared 페이지인 경우 루트 anon_vma를 사용한다.
  • 코드 라인 25~27에서 페이지에 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)
{
        lock_page_memcg(page);

        if (!PageAnon(page)) {
                page_remove_file_rmap(page, compound);
                goto out;
        }

        if (compound) {
                page_remove_anon_compound_rmap(page);
                goto out;
        }

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

        /*
         * 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_lruvec_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.
         */
out:
        unlock_page_memcg(page);
}

페이지에서역방향 매핑(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));
                return;
        }

        /* page still mapped by someone else? */
        if (compound && PageTransHuge(page)) {
                int nr_pages = thp_nr_pages(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)))
                        return;
                if (PageSwapBacked(page))
                        __mod_lruvec_page_state(page, NR_SHMEM_PMDMAPPED,
                                                -nr_pages);
                else
                        __mod_lruvec_page_state(page, NR_FILE_PMDMAPPED,
                                                -nr_pages);
        } else {
                if (!atomic_add_negative(-1, &page->_mapcount))
                        return;
        }

        /*
         * 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 rwsem 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.
 *
 * anon_vma_clone() is called by __vma_adjust(), __split_vma(), copy_vma() and
 * anon_vma_fork(). The first three want an exact copy of src, while the last
 * one, anon_vma_fork(), may try to reuse an existing anon_vma to prevent
 * endless growth of anon_vma. Since dst->anon_vma is set to NULL before call,
 * we can identify this case by checking (!dst->anon_vma && src->anon_vma).
 *
 * If (!dst->anon_vma && src->anon_vma) is true, 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 && src->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 수만큼 pvac를 순회한다.
    • @src vma의 anon_vma_chain 리스트에 연결된 avc들을 순회한다.
  • 코드 라인 9~16에서 anon_vma_chain을 할당한다. 만일 할당이 실패하면 anon_vma root 락을 풀고 다시 한 번 더 할당을 시도해본다.
  • 코드 라인 17에서 순회 중인 pvac에 연결된 anon_vma를 알아온다.
  • 코드 라인 18에서 root anon_vma 락을 건다.
  • 코드 라인 19에서 clone된 @dst vma와 순회 중인 anon_vma 사이에 새로 할당한 anon_vma_chain을 사용하여 링크한다.
  • 코드 라인 29~31에서 anon_vma 하이라키가 계속 끝 없이 증가되는 것을 막기 위한 패치이다. vma를 소유하지 않았고, 조부모 이상의 anon_vma를 대상으로 오직 하나의 child anon_vma를 가진 anon_vma는 재 사용하게 한다.
  • 코드 라인 32~33에서 @dst vma에 anon_vma가 지정된 경우 degree를 상향 시킨다.

 


반복되는 fork hierarchy로부터 anon_vma의 끝없는 증가 방지 패치

참고:

 

다음과 같이 반복되는 fork로 인해 anon_vma가 끝없이 증가를 하던 것을 anon_vma를 reuse하는 방법으로 패치하였다.

#include <unistd.h>

int main(int argc, char *argv[])
{
        pid_t pid;

        while (1) {
                pid = fork();
                if (pid == -1) {
                        /* error */
                        return 1;
                }
                if (pid) {
                        /* parent */
                        sleep(2);
                        break;
                }
                else {
                        /* child */
                        sleep(1);
                }
        }

        return 0;
}

 

다음 그림은 조부모 프로세스로부터 부모 및 자식까지 fork 될 때 AV의 연결되는 과정을 보여준다.

  • fork 과정을 자세히 보여주기 위해 조부모 프로세스에 1개의 VMA와 AV 만을 사용하였다.

 

다음 그림은 부모 프로세스 종료 후 AV를 재사용할 수 있는 상태를 보여준다.

  • 만일 fork한 자식 프로세스 B가 종료하면 부모 프로세스의 AV는 재사용 없이 free된다.

 

다음 그림은 자식 프로세스가 조부모 프로세스의 AV를 다시 재사용(reuse)하는 과정을 보여준다.

  • 부모 프로세스는 제외하고 조부모 이상이 사용하였던 AV를 대상으로 degree가 1이이어야 한다.

 

참고

 

 

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

  1. 안녕하세요! 문영일님!

    지난번 16기 스터디 참여해주셔서 정말 큰 도움을 주신 커널 버전 v5.1 기준 compaction 은 서브 시스템은 복습까지 끝나고,
    rmap 서브시스템 쪽을 열심히보고 있는데요.

    기억에는 지난번에 보시구 수정해주셨던 것 같은데, 반영이 안 되어있는건지 궁금해서 댓글로 문의드립니다.

    글 처음에

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

    바로 다음 문단에 설명되어 있는 reverse mapping 종류가 있는데,

    맨 처음 줄에 anon page 의 경우로 reverse mapping 하는 것으로 착각할 수도 있을 것 같다구
    말씀해주시구 그때 수정해주셨었습니다.

    항상 감사드립니다~

    1. 그러게요. ^^;
      anon 단어를 삭제하였습니다.
      설명도 일부 변경하였고, 3 가지 방법 -> 4 가지 방법으로 추가하였습니다. (그림은 나중에)
      감사합니다.

댓글 남기기

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