virtual address space

최대 4GB (archi. dep.)

접근 불가 영역도 존재
    ex.
    08048000 - 0804c000
    prcess에게 접근 권한이 없는 메모리 주소 영역
    유효한 주소의 이런 영역을 -> 메모리 영역이라고 함

segment fault

    유효하지 않은 영역에 access 시 발생

memory section types

    1) text section (RO)
    2) data section (RW)
        실행 파일의 초기값이 있는 전역 변수가 할당된 메모리
    3) zero page (BSS)
        초기값이 없는 전역 변수가 들어 있는 영역
    4) process user space stack
    5) C lib용
        text, data, BSS sections
    6) memory 할당 file 영역
    7) 공유 메모리 구간
    8) malloc 등의 함수와 관련된 '익명' 할당 메모리


    process address space의 모든 유효 address는 한 영역에 속함
    영역은 겹치지 않음
    
    실행 중인 process는
        stack
        object code
        global variables
        memory allocation file
       
        등 여러 구분된 memory sections들을 지님



Memroy Descriptor

    memory descriptor로 process의 memory address space를 표현
   
    <linuc/mm_types.h> 내
   
    struct mm_struct {
        struct vm_area_struct   *mmap;           <-
        struct rb_root           mm_rb;


            동일 자료 구조에 대한 두가지 표현 (각각 list와 rb tree - O(lnN) time)           
           
            보통 중복 표현을 피하지만,
            list의 경우 순차 탐색에 용이하며, rb tree는 특정 항목 탐색에 용이
           
            이렇게 같은 data를 두 가지 다른 접근 방식으로 사용하는 것 --> thread tree


       
        struct vm_area_struct   *mmap_cache;      <- 최근 사용한 메모리 영역
        ...
        pgd_t                   *pgd;            <- 전체 page list
       
        atomic_t                 mm_users;       <- 주소 공간 사용자 (process 개수 - 즉, thread 개수)
        atomic_t                 mm_count;       <- mm_struct의 참조 횟수
       
                9개의 thread가 주소 공간을 공유해도, mm_users 값은 9지만, mm_count는 1임
                mm_users 값이 0이 될 때 mm_count도 0이 됨 (이때 메모리 해제)

        ...

        struct list_head        mmlist;            /* list of all mm_structs */
       
            모든 mm_struct는 mlist를 통해서 list로 관리됨
            list 내 최초 item은 init processs의 address space를 나타내는 init_mm memory descriptor임
            mm_struct init_mm은, /kernel/mm/init-mm.c에 존재
           
                kernel/fork.c에 정의된 mmlist_lock에 의해서 동시 접근이 제한



        unsigned long   start_code;           /* start address of code */
        unsigned long   end_code;             /* final address of code */
        unsigned long   start_data;           /* start address of data */
        unsigned long   end_data;             /* final address of data */
        unsigned long   start_brk;            /* start address of heap */
        unsigned long   brk;                  /* final address of heap */
        unsigned long   start_stack;          /* start address of stack */
        unsigned long   arg_start;            /* start of arguments */
        unsigned long   arg_end;              /* end of arguments */
        unsigned long   env_start;            /* start of environment */
        unsigned long   env_end;              /* end of environment */

        unsigned long       rss;                  /* pages allocated */
        unsigned long       total_vm;             /* total number of pages */
        ...
        cpumask_t cpu_vm_mask; /* lazy TLB switch mask */
        ...
        struct core_state *core_state; /* core dump support */
        ...
   };



memory descriptor allocation

    특정 task의 memory descriptor는 task의 process descriptor 내 mm 항목(mm_struct)을 통해 연결되어 있음
   
    즉,
        current->mm 은 현재 process의 memory descriptor를 의미
   
    fork 시,
        copy_mm 함수가 parent process의 memory descriptor를 child process로 복사
   
    mm_struct
        allocate_mm은 mm_cachep (slab cache 임)를 통해 mm_struct를 할당
        process는 보통 독자적인 mm_struct (즉, 돚가적인 process address space)를 할당 받음

    clone
        에서 CLONE_VM flag로,
        ㅂ모와 자식간 주소 공간 공유
            위 flag 설정 시,
            tsk->mm = current->mm; 임
       
        이런 process를 thread라고 함
       
   
    process 종료 시,
        exit_mm이 호출 (@ kernel/exit.c)
        mm_count를 줄이고, 0이 되면, 더 이상 memory descriptor 사용처가 없기에 free_mm 호출
            free_mm --> kmem_cache_free

        mm_struct 구조체가 mm_cachep slab cache로 돌아감



mm_struct 구조체와 KERNEL thread

    kernel thread process의 memroy descriptor인 mm은 NULL
   
    kernel memory 접근을 위한 page table과 같이 kernel thread에 일부 data가 필요한 경우가 존재   
    kernel thread는 이전에 실행한 task의 memory descriptor를 사용
   
    process가 scheduling 될 시, process의 mm 항목이 참조하는 process address space가 load 됨
    새로운 address




    새로운 address space를 사용하도록 active_mm을 update
    kernel thread는 자신만의 address space가 없기에 mm은 NULL
   
    kernel thread가 scheduling 되면, mm 항목이 NULL 이라는 것을 확인하고
    사용 중인 이전 process의 주소 공간을 그대로 둠
    kernel thread의 memory descriptor의 active_mm을 이전 process memory descriptor가 가리키던 곳으로 갱신
   
    이로서 kernel thread는 이전 process의 page table이 필요할 때 사용 가능
    kernel thread는 user level address space에 접근하지 않으므로 커널 memory에 해당하는 address space 정보만 사용



virtual memory area (VMA)


    +----------------+ *   1 +-----------+
    | vm_area_struct |<----<>| mm_struct |
    +----------------+       +-----------+

        특정 process의 address space를 표현하는 memory descriptor(mm_struct)는 여러 memory area (vm_area_struct)로 구성



    vm_area_struct로 표현 <linux/mm_types.h>
   
        리눅서 커널에서 memory area는 가상 메모리 영역(VMA)라고 부르는 경우가 많음
        주어진 주소 공간에서 연속된 구간에 해당하는 단일 메모리 영역을 나타냄
   
        각 memory area를 독립적인 memory object로 간주 (area 별로 권한 및 작업 가능 범위가 다름)
   
            여러 종류의 memory ara에 대한 '추상'화된 표현
   
        memroy가 할당된 file, process의 user level stack과 같은 서로 다른 유형의 memory area를 VMA 구조체로 표현
   
            VFS에서 사용했던 객체지향 접근법과 동일

   

    struct vm_area_struct {
        ...
        struct mm_struct *vm_mm;                    /* The address space we belong to. */
   
            VMA에 대당하는 mm_struct임
            VMA 별로 고유한 mm_struct를 지님
   
                두 개의 별도 process가 같은 file을 각자의 주소 공간에 할당하는 경우,
                각자 별도의 vm_area_struct를 통해 각자의 memory 공간을 식별
   
                반면, 주소 공간 공유 경우,
                두 thread는 모든 vm_area_struct 구조체를 공유
   
   
        unsigned long vm_start;                        /* Our start address within vm_mm. */
        unsigned long vm_end;                        /* The first byte after our end address within vm_mm. */
   

        pgprot_t vm_page_prot;                        /* Access permissions of this VMA. */   
   
        struct vm_area_struct *vm_next, *vm_prev;    VMA list         
   
        struct rb_node vm_rb;                        tree 상의 VMA node
   
   
        union....
   
   
        struct anon_vma *anon_vma;                   익명 VMA 객체
   
   
        struct vm_operations_struct *vm_ops;         관련 동작 (해당 VMA 영역에 대한 동작)
   
        struct file * vm_file;                 할당된 file (can be NULL)
   
        ...
    };




    각 memory descriptor는 process address space 내의 고유 구간을 나타냄
    vm_start 항목은 해당 구간의 (낮은)시작 address
    vm_end는 구간의 마지막 주소(높은)
   
    vm_end - vm_start가 memory area의 byte length [vm_start, vm_end)




VMA flag


    vm_area_struct
     +- ...
     +- unsigned long vm_flags



    <linux/mm.h>
   
    VMA flag는 hardware가 아닌 kernel의 동작 지정


    VM_READ,
    VM_WRITE
    VM_EXEC
    VM_SHARED           page will be shared
                        memory region이 여러 process가 공유함을 의미
                        shared mapping
                        (개별 할당인 경우 private mapping)
    ...
    VM_IO               mmap 호출 시 설정 됨 (메모리 영역이 process의 core dump에 들어가지 않게 함)
    VM_SEQ_READ         sequentially accessible page
                        app이 해당 역에 대해 순차적 읽기 동작을 수행한다고 kerenl에 알림
                        (커널이 해당 vm_area_struct 영역에 대해서 미리 읽기 기능을 사용할 수 있음)

    VM_RAND_READ        VM_SEQ_READ의 반대
    ...
    VM_RESERVED         memory region이 swap 되지 않도록 하는 역할 (device driver 할당에서 사용)
   
   
    ex.
        object code는 VM_READ, VM_EXEC는 할당해야 함,
                      VM_WRITE는 할당하면 안 됨

        object data는 VM_READ, VM_WRITE 할당, VM_EXEC는 할당 X


VMA 동작

    vm_area_struct 구조체의 vm_ops 항목
        : 커널이 해당 memory region을 조작히는 방법

   
   
    vm_operations_struct
     +- void (*open)(struct vm_area_struct * area);
     +- void (*close)(struct vm_area_struct * area);
     +- int (*fault)(struct vm_area_struct *vma, struct vm_fault *vmf);
     |
     +- int (*page_mkwrite)(struct vm_area_struct *vma, struct vm_fault *vmf);
     +- int (*access)(struct vm_area_struct *vma, unsigned long addr, void *buf, int len, int write);
     |
     +- NUMA ops
     |
     +- int (*remap_pages)(struct vm_area_struct *vma, unsigned long addr, unsigned long size, pgoff_t pgoff);


    int fault
        : physical memory가 없는 page에 access 시page fault handler가 호출하는 함수
   
    int page_mkwrite(...)
        : read only page를 writeable하게 변경 시 page fault handler가 호출하는 함수

    int access(...)
        : get_user_pages() 호출 failure 시 access_process_vm에서 호출하는 함수



memory area list & tree (memory area thread tree)

   
        struct mm_struct {
            struct vm_area_struct * mmap;        /* list of VMAs */
            struct rb_root mm_rb;
            struct vm_area_struct * mmap_cache;    /* last find_vma result */
           
            ...
           

    mmap과 mm_rb는 thread tree 자료 구조임
   
        mmap
            : 모든 memory area object를 하나의 linked list로 보관
           
            vm_area_struct의 vm_next 항목을 통해 list 형태로 연결 됨
            오름착순 정렬
            첫 번째 memory area는 mmap pointer가 가키리는 vm_area_sturct
            마지막 구조체는 NULL

        mm_Rb
            : 모든 memory area 객체를 RB-tree로 연결
            mm_rb가 가리키는 곳이 RB-tree의 root
            address space에 속하는  각 vm_area_struct 구조체는 vm_rb 항목을 통해서 연결됨

            cf.
            RB-tree는
                왼편이 우측보다 작은 값
                각 노드는 Red, Back의 상태를 지님
            
                red의 child는 black
                root에서 left로 가는 모든 경로는 같은 개수의 black node가 있음
                root node는 항상 red node
               
                검색, 삽입, 삭제가 O(log(n))   <-- O(logN)을 보장한다는 것이 특징 (FBT는 보장은 못함)


Actual memory area

    process의 address space와 memory area 내부
   
        /proc
        pmap utility
       
        를 통해서 살펴 볼 수 있음


    ex.
        특정 app의 address space (mm_struct의 각 vm_area_struct) 살펴보기
       
       
            text area
            data area
            BSS  area
           
        shared lib. link 시 각 shared lib이 사용하는 text/data/BSS area가 존재
       
            그리고
            process의 stack area

       
        /proc/<pid>/maps
       
            00e80000-00faf000       r-xp    00000000 03:01 208530  /lib/tls/libc-2.5.1.so
            ...
           
            시작-끝  권한  offset  majkor:minor  inode  file


        pmap 1426
       
            ... 더 보기 편하게 출력
           
            4001e000 (4KB)  rw-p    (00:00 0)                   <-- ZI
            bfffe000 (8KB)  rwxp    (00:00 0)       [ stack ]   <-- process stack


    실행코드이기에 text area는 read/executable
    반면 data area와 BSS area는 read/write 가능
   
        1340KB 중 40KB만 writable area
       
        늘 write가 불가능한 영역은 모든 process가 하나만 사용한다.
        (즉, write 발생 시 memory 영역을 복사 하는 CoW 정책에 의함)
       

        위에서 ZI는 file이 할당되어 있지 않은 장치 00:00과 0번 inode memory area이다.



memroy area handling

    커널은 주어진 VMA에 대해서 주소 존재 여부 확인과 같은 동작을 빈번히 수행함   
    mmap의 기본 동작을 구성


    struct vm_area_struct *
    find_vma(sruct mm_struct *mm, unsigned long addr);
   
        주어진 주소공간(mm)에 대해 vm_end 항목 값이 addr 보다 큰 첫 번째 memory area를 찾음
        addr이 들어 있거나 addr 보다 큰 주소로 시작하는 첫 번째 memory area를 찾음
       
            해당 vm_area_struct를 리턴
            (VMA는 addr 보다 큰 주소이기에 addr이 VMA에 반드시 들어 있음을 보장하지는 않음)

        find_vma의 return은 memory descriptor(mm)의 mmap_cache 항목 안에 cache 됨
            VMA에 대한 동작이 수행 되었다는 의미이므로, cache의 temporal 특성에 의해 hit rate는 30~40%

        주어진 주소가 cache에 없으면 memory descriptor(mm)에 속한 memory area(vma_area_struct)를 탐색
            RB-tree를 통해 탐색


            struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
            {
                struct vm_area_struct *vma = NULL;
               
                vma = ACCESS_ONCE(mm->mmap_cache);
                if (!(vma && vma->vm_end > addr && vma->vm_start <= addr)) {  <-- cache에 없으면,
                    ...
                   
                    rb_node = mm->mm_rb.rb_node;
                    vma = NULL;
                   
                    while (rb_node) {
                        struct vm_area_struct *vma_tmp;
                        vma_tmp = rb_entry(rb_node, struct vm_area_struct, vm_rb);
                       
                        if (vma_tmp->vm_end > addr) {
                            vma = vma_tmp;
                           
                            if (vma_tmp->vm_start <= addr)
                                break;
                            rb_node = rb_node->rb_left;
                        } else {
                            rb_node = rb_node->rb_right;
                        }
                    }
                   
                    if (vma)
                        mm->mmap_cache = vma;           <-- 방금 찾은 것은 cache에 keep (hit rate 30~40%)           
                }
           
                return vma;
            }



    struct vm_area_struct *
    find_vma_prev(struct mm_struct *mm, unsigned long addr,
        struct vm_area_struct **pprev)
       
       
        find_vma의 동작과 동일하나 addr 이전의 마지막 VMA를 반환하는 점이 다름
        mm/mmap.c file에 정의되어 있음, <linux/mm.h>에 선언
       
        pprev 인자에는 addr 앞 쪽의 VMA pointer가 저장됨


    static inline struct vm_area_struct *
    find_vma_intersection(struct mm_struct * mm, unsigned long start_addr, unsigned long end_addr)
   
        지정한 주소 범위와 중첩되는 첫 번째 VMA를 리턴
   
        struct vm_area_struct * vma = find_vma(mm,start_addr);
        if (vma && end_addr <= vma->vm_start)
            vma = NULL;
        return vma;



mmap() & do_mmap(): address range generation


    do_mmap
        : do_mmap은 process의 address space에 address range를 추가
        기존 memory area의 확장 or 생성 시 기존 address space에 address range를 추가


        커널이 연속된 주소 범위를 새로 만들 때 사용
        (단 생성된 주소 범위가 기존 주소 범위와 인접하면 병합해서 합침 -> 즉, 생성이라고 부를 수 없음)
       
        합병 불가능 시,
            1) vm_area_cachep slab cache에서 새로운 vm_area_struct 구조체를 할당,
            2) vma_link 호출
                새로운 VMA을 address space의 linked list와 RB-tree에 추가
            3) memory descriptor (mm_struct)의 total_vm 항목 갱신
           
            그리고
            새로 생성된 주소 범위의 초기 주소 값을 리턴


    do_mmap 함수의 동작은 mmap system call을 통해 user space에 제공됨
        mmap system call 호출은 다음과 같이 정의

            unsigned long sys_mmap2(unsigned long addr, size_t len,
                        unsigned long prot, unsigned long flags,
                        unsigned long fd, unsigned long pgoff)
            {
                return do_mmap2(addr, len, prot, flags, fd, pgoff, PAGE_SHIFT-12);
            }
           
           
            이 system call은 mmap의 두 번째 변화형이라 mmap2임
            워래 mmap은 마지막 인자로 byte unit offset을 사용했음
           
            mmap2는 page unit offset 사용
                offset이 더 커져서 더 큰 file 할당 가능
               

       
    do_mmap(file *file, addr, len, prot, flga, offset)
   
        offset 위치에 len 길이만큼 주소 범위를 할당
        file에 NULL, offset에 0 지정 경우
            anynymous mapping
       
        file과 offset이 지정된 경우
            file-backed mapping

        prot
            : page 접근 권한 지정
                PROT_READ       : VM_READ에 해당
                PROT_WRITE      : VM_WRITE
                PROT_EXEC       : VM_EXEC
                PROT_NONE       : page에 접근 불가

        flag
            : VMA flag에 해당하는 flag
           
                MAP_SHARED      : 공유 가능 allocation
                MAP_PRIVATE     : 공유 불가
                MAP_FIXED       : 새로 생성되는 주소 range는 지정한 addr 주소에서 시작
                MAP_ANYNYMOUS   : 파일 지정 할당이 아닌 익명 할당
                ....



munmap() & do_munmap(): address range free

    do_munmap
     : 지정한 process address space에서 address range를 제거
     (즉, VMA를 제거)
    
    
        int do_munmap(struct mm_struct *mm, start, len)

    int munmap(void *start, len)


    이 system call은 mm//mmap.c file에 정의
    단순히 do_munmap()의 wrapper
   
   
   
        armlinkage long sys_munmap(unsigned long addr, size_t len)
        {
            ...
            struct mm_struct *mm;
           
            mm = current->mm;
            down_write(&mm->mmap_sem);
            ret = do_munmap(mm, addr, len);
            up_write(&mm>mmap_sem);
            return ret;
        }
   
       
Page table

    virtual address는, physical page table entry (page-frame)이 할당된 virtual page table entry를 사용
   
    page table에 access는 CPU가 내부적으로 알아서,
        virtual address --> logical address --> linear address --> physical address
       
            각 단계별 page table들이 level 별로 존재
   
    Linux page table
        3 level로 구성       
        H/W가 3 level을 지원하지 않아도 Linux kernel은 3 단계를 사용
       
        세 단계를 사용하는 것은 일종의 '최대 공약수' 같은 개념
        필요에 의해 compiler optimization을 통해 kernel page table을 단순화 시킬 수 있음
       
    PGD (Page Global Directory)
        최상위 page table은 (page global directory인)pgd_t 형 배열
       
            pgd_t는 대부분 unsigned long

        PGD는 PMD (Page Middle Directory)를 가리킴
       
            pmd_t
           
        PMD는 PTE (Page Table Entry)를 가리킴
       
            pte_t

 
                                                                            +-------+
                              +-------+              +-------+              | pte_t |          +------+
    +-----------+             | pgd_t |              | pmd_t |              +-------+    +---> | page |
    | mm_struct |------+      +-------+              +-------+              | pte_t |    |     +---|--+
    +-----------+      |      | pgd_t |       +----->| pmd_t |--------+     +-------+    |         |
                       |      +-------+       |      +-------+        |     | pte_t |    |         |
                       +----->| pgd_t | ------+      | pmd_t |        |     +-------+    |         v
                              +-------+              +-------+        |     | pte_t |    |      page-frame
                              | pgd_t |              | pmd_t |        |     +-------+    |
                              +-------+              +-------+        +---->| pte_t |----+
                              | pgd_t |              | pmd_t |              +-------+
                              +-------+              +-------+

     TLB 사용
        TLB hit 시 TLB entry 사용
        아니면 위의 단계를 수행해서 physical page-frame 값 획득