* 뇌피셜이 난무할 수 있습니다.
* 개인 공부 용도로 작성하였습니다.
* 이해하기 드럽게 어렵네...
* 카이스트 핀토스 강의든 깃북이든 좀 많이 불친절한 것 같다 ㅎㅎㅎ.. 내가 잘 몰라서 그런거일수도 있지만!
* 특히 카이스트 핀토스 강의에서는 is it simple, very interesting 이러시는데 솔직히 듣다보면 화가 날 때가 좀 있었다 ^.^
* 프로젝트3 완료 후 수정 필요
* Github

cow만 fail되는 경우인 1개는 1번 떴었으나 계속해서 2 ~ 6개의 범위로 fail된다. lock을 촘촘히 잘 걸지 못하서 그런 거라 생각해 file 관련 부분들에 적절하게 다 걸어보았으나... 해결되지 않는다.

참고자료

• Assignment
• 한양대 PPT

---

Project 3: Virtual Memory

Introduction

• 현재 우리가 구현한 핀토스는 적절한 동기화와 함께 여러 쓰레드를 잘 다룰 수 있다. 그리고 한 번에 여러 사용자 프로그램도 load할 수 있다.
• 반면 run할 수 있는 프로그램의 수와 그 크기는, 머신의 메인 메모리 크기에 의해 제한되어져 있다.
• 이번 프로젝트에서는 이러한 제한을 없애고 마치 무한한 메모리를 가졌다는 착각에 빠지도록 만드는 것이 주 목적이다.

---

Background

Source Files

• 이번 프로젝트에서는 vm 폴더에서 작업하게 될 것이다.
• vm.c는 가상 메모리를 위한 일반적인 인터페이스를 제공해주고 있다.
  • 이 파일에서 page table을 구현해야 한다.
• uninit.c는 초기화되지 않은 페이지들을 위한 함수들을 제공해주고 있다.
  • 모든 페이지는 처음에 초기화되지 않은 페이지들로 제공이 되고, 그 다음 anonymous pages 혹은 file-backed pages로 변환된다.
• anon.c는 anonymous pages를 위한 함수를 제공해준다.
• file.c는 file-backed pages를 위한 함수를 제공해준다.
• pml4는 하드웨어가 직접 건드리는 영역이다. 이를 건드리기보다는, 이를 보완하기 위해 그저 page와 frame의 정보들을 담는 용도, 직접적인 맵핑이 아니라 서로의 정보를 효율적으로 저장하기 위해 supplemental page table을 만든다.
• c의 경우 메모리 초기화를 하지 않는다. 이 자체가 많은 비용이 들 수 있다. 따라서 test를 돌릴 때 초기 메모리 등 내용이 다를 수 있기 때문에 다른 결과가 나올 수 있다. 기기마다 test의 결과가 다른 이유도 이와 연관되어 있을 수도 있다.

Memory Terminology

Pages

• 페이지는 때때로 virtual page라고도 불리며, 가상 메모리 주소에서 4096B(4KB) 만큼의 페이지 사이즈를 가지는 연속적인 부분이다.
• 페이지는 page-aligned되어야 한다. 따라서 페이지 사이즈로 균등히 나눠진 가상 주소에서 페이지 주소가 시작된다.
• 64비트 가상 주소의 마지막 12비트는 위와 같이 page offset이다. 12비트 위의 나머지 비트들은 각각의 페이지 테이블에서 어디에 위치하는지 표시하기 위한 index를 나타내기 위해 사용된다.
• 64비트 시스템(핀토스도 64비트)에서는 4-level 페이지 테이블을 이용하고 그로 인해 위와 같은 가상 주소를 사용한다.
• 각각의 사용자 프로세스는 사용자 가상 페이지들의 집합을 독립적으로 가지고 있고(사용자마다 가상 메모리 공간이 있고 이것들이 모두 페이지들로 나뉘어져 있는데 이것들이 모이면 사용자 프로세스가 될 것이다), 그 페이지들은 가상 주소 KERN_BASE(0x8004000000) 아래에 있는 페이지들이다. 즉 늘 그래왔듯이 커널 아래 공간으로, 사용자 공간을 말한다.(가상 주소)
• 반면 어떤 쓰레드나 프로세스가 돌고 있는지와는 상관 없이, 커널 가상 페이지들은 전역이라서 같은 위치에 남아있다.(맵핑된다)
• 커널은 사용자와 커널 페이지(사용자 공간, 커널 공간) 모두 접근할 수 있다. 반면 사용자 프로세스는 오직 자신의 주소 공간만 접근이 가능하다.

Frames

• physical frame이라고도 불리는 프레임은 물리 메모리에서 연속적인 부분이다. 페이지와 사이즈가 같으며 page_aligned되어 있다. 그러므로 64비트 물리적 주소는 frame number와, 프레임 내에서 원하는 데이터가 어디 있는지 찾을 수 있는 frame offset으로 나뉘어져 있다.
  
• x86-64 아키텍처는 물리 주소의 메모리에 직접적으로 접근하는 방법을 제공하지 않는다.
  • 핀토스는 커널 가상 메모리의 1번째 페이지가, 물리 메모리의 1번째 프레임과 맵핑되도록 하여
  • 물리 주소의 메모리에 접근할 수 있게 한다.
  • 커널 가상 메모리를 통해 프레임에 접근할 수 있게 된다.

Page Tables

• 페이지 테이블은, CPU가 가상 주소를 물리 주소로, 즉 페이지에서 프레임으로 변환하기 위해 사용하는 자료구조이다.
• 페이지 테이블을 통해서 가상 주소가 물리 주소로 바뀌는데, 이 때 offset은 변하지 않는다. page number가 frame number로 바뀌어진다.

Swap Slots

• swap slot은 디스크 공간에서 스왑 영역에 존재하는 페이지 크기들의 집합이다.

---

Resource Management Overview

• 구현 해야 할 자료 구조들
  • Supplemental page table
    • 페이지 테이블을 보완할 자료구조로, 이를 통해 page fault를 처리할 수 있어야 한다.
    • page fault가 나면 프로세스를 죽이는 것이 아니라, 프로세스가 찾으려는 page를 찾아서 물리 메모리에 적재시켜서 demand loading을 할 수 있어야 한다.
  • Frame table
    • 프레임을 효과적으로 퇴거하기 위해 필요한 자료구조이다.(swap out)
  • Swap table
    • swap slot들이 어떻게 사용되고 있는지 추적한다.
• 위 테이블들을 각기 다른 테이블로 구현할 필요는 없다. 관련된 것들을 전체적이든 부분적으로든 하나로 통합된 데이터 구조를 구현하는 것이 편할 것이다.
• 간편하게 하기 위해 calloc 혹은 malloc을 이용해 이 자료구조들을 페이지를 이용하지 않은 메모리에 저장할 수도 있다. 이렇게 하면 포인터가 덮여씌워지지 않고 계속 남아 있다는 걸 확신할 수 있다?

---

Managing the Supplemental Page Table

• 보완된 페이지 테이블은 각 페이지마다 추가적으로 데이터를 가진 페이지 테이블을 보완한다.
• 기존 페이지 테이블 pml4...는 구성이 제한되어 있어 사용할 수 없다.(pml4를 통한 페이지 테이블에 우리가 무언가를 추가할 수가 없다. x86-64 아키텍처, 즉 하드웨어가 pml4를 제공해주고 있기 때문인가?)
• Supplemental Page Table의 목적
  • page fault 발생 시, 커널은 어떤 데이터가 실제로 그 page에 있어야 하는지 알아내기 위해 Supplemental Page Table에서 page fault가 발생한 가상 페이지를 찾는다.
  • 프로세스 종료 시 어떤 자원들이 free되면 되는지 알아내기 위해 Supplemental Page Table을 탐색한다.

Organization of Supplemental Page Tables

• page들 혹은 segment들을 다루는 Supplemental page table로 구성한다.
  • page들을 다루는 supplemental page table을 만들겠다.

Handling page fault

• Supplemental page table을 가장 중요하게 사용하는 것은 page fault handler이다.
  • 프로젝트 2에서 page fault는 단순히 버그 였지만
  • 프로젝트 3에서는 page fault 발생 시, 접근하려던 그 page를 파일이든 swap slot이든 메모리로 가지고 와야 한다.
  • exception.c에 위치한 page_fault 함수는 vm.c에 위치한 vm_try_handle_fault 함수를 호출한다.
  • vm_try_handle_fault
    1. page fault가 발생한 페이지를 Supplemental page table에서 찾는다.
       • struct page를 만드는 것이 아니라, fault난 struct page를 Supplemental page table에서 찾아야 할 것 같다.
       • 유효한 접근이라면, supplemental page table과 연결된, 그 page fault난 struct page를 통해 file system에 있거나, swap slot에 있거나, 혹은 모든 데이터 값이 0인 page가 될 수 있는 page를 탐색한다.(page fault난 page의 내용을 찾는 것 같다)
         • 이 때 만약 사용자 프로세스가 커널 가상 메모리 내의 페이지를 접근하려는 경우, 혹은 read-only 페이지에 write 하려는 경우, 해당 프로세스에 의해 보여지면 안되는 페이지에 접근하거나? 이러한 경우의 접근은 유효하지 않다.
         • 이렇게 유효하지 않은 접근을 한 프로세스는 종료되어야 하고, 그 프로세스의 자원도 모두 free 시켜야 한다.
    2. 페이지(가상)를 저장하기 위한 프레임(물리)을 얻는다.
       • vm_get_frame 이용해서?
       • swap out하고 나서 매칭시키면 되나?
    3. 파일 시스템 혹은 swap area에서 데이터를 읽어서, 혹은 데이터를 모두 0으로 만들어 frame에 넣는다.
    4. page fault가 발생한 가상 주소의 page table entry가 physical page를 가리키도록 한다. 이 때 mmu.c의 함수를 사용하면 된다.
       • page fault난 struct page의 va가 struct frame의 kva와 연결되어, 해당 페이지가 이제 진짜 물리 메모리를 쓸 수 있도록 하는 건가?
       • 물리 메모리에 올라가 있지 않은 것은 그러면 va와 kva가 연결 안되어 있겠네?

---

Managing the Frame Table

• frame table은 각 frame entry(struct frame을 말하는 것 같다)를 가지고 있다. 이러한 struct frame은 어떤 page에 의해 쓰여지고 있는지, 즉 점유 중인 page를 가르키는 포인터를 가지고 있다.
• 이러한 frame table은 free인 frame이 존재하지 않을 때, 어느 frame을 퇴거할 수 있게 한다.
• 사용자 프로세스를 이루는 페이지들을 위한 frame들은 user pool에서 가지고 와야 한다.
• frame table의 가장 중요한 연산은 사용되고 있지 않은 frame을 가지고 오는 것이다. 이것은 frame이 free일 때 가지고 오면 되므로 구현하기 쉽다.(제발 쉽다는 말 좀 적당히 해라 ㅎㅎㅎ)
  • free인 frame이 없다면, 어떤 프레임을 퇴거하여 free인 frame을 만들어야 한다.
• 퇴거 절차
  • 페이지 교체 알고리즘에 따라 퇴거할 프레임을 고른다.
    • accessed bit와 dirty bit가 효과적으로 사용될 것이다.
  • page table(pml4...를 말하나?)에서 프레임에 대한 그 페이지의 참조를 제거한다. 서로의 관계를 끊는다고 생각해야겠다.
    • sharing을 구현하지 않았다면, 프레임에는 하나의 페이지만 참조하고 있을 수 있다. 가리키고 있을 수 있다.

---

Memory Management

• 핀토스의 가상 메모리 시스템을 보완하기 위해, 가상 페이지와 물리 프레임을 관리할 필요가 있다.
  • 따라서 가상 혹은 물리 메모리(페이지, 프레임)가 어떤 목적으로, 누구에게 의해 사용되고 있는지 추적해야 한다.
• Supplemental Page table을 다루고 나서 (Physical) 프레임을 다루어야 한다.
• 여기서 페이지는 가상 페이지이며 프레임은 물리 페이지이다.

Page Structure and Operations

struct page

struct page {
  const struct page_operations *operations;
  void *va;              /* Address in terms of user space */
  struct frame *frame;   /* Back reference for frame */

  union {
    struct uninit_page uninit;
    struct anon_page anon;
    struct file_page file;
#ifdef EFILESYS
    struct page_cache page_cache;
#endif
  };
};

• 이 struct page는 가상 메모리의 페이지를 나타낸다. 이 struct page는 우리가 페이지에 대해 알아야 하는 모든 정보를 저장하고 있다.
• union에서 오직 한 멤버만 한 번에(at a time) 값을 가질 수 있다.
  • 즉 page는 uninit_page 혹은 anon_page 혹은 file_page 혹은 page_cache가 될 수 있다.
  • 만약 어떤 페이지가 anonymous page라면 그 struct page의 anon_page anon은 값을 가지고 있을 것이다.
    • 이 anon_page 멤버는 anonymous page를 유지하기 위한 모든 필요한 정보를 포함하고 있다.

Page Operations

• page는 VM_UNINIT, VM_ANON, VM_FILE 중 1개가 될 수 있다.
• 페이지마다 swap in, swap out, destroy page와 같은 연산을 해야하는데, 이는 페이지의 타입에 따라 요구되는 단계와 그 단계에서 이루어지는 작업이 다르다.
  • VM_ANON, VM_FILE에 의해 불려지는 destroy는 달라야 한다.
  • 이러한 경우를 다루기 위한 가장 쉬운 방법은 switch-case이다.

---

Anonymous Page

Page Initialization with Lazy Loading

• struct page는 할당되어 있으나, 전용 실제 물리 프레임은 없는 상태(페이지의 실제 내용이 load되지 않은 상태)
  • 새로운 물리 frame을 받고 거기에 load를 하나? 가상 page의 내용을?
• 실제 내용은 진짜 그 페이지가 필요할 때 page fault가 발생하여 load되게 된다.
  
  
• 3가지 page types가 있고 초기화 루틴은 각 페이지 타입에 따라 다르다.
• initialization flow
  • (사용자 프로세스가 요청)커널이 새로운 페이지에 대해 요청을 받으면(프로세스가 새로운 페이지를 요청한 건가?) vm_alloc_page_with_initializer이 호출된다.
  • initializer가 요청 받은 페이지에 대해 struct page를 할당하며(프로세스가 실행하고자 하는 페이지인데 커널 입장에서는 새로운?) 페이지 타입에 따른 initializer를 설정한다.
  • 이후 사용자 프로세스에게 제어권을 넘긴다.(컨텍스트 스위칭)
  • 이 때 사용자 프로세스가 실행되면 page fault가 발생하는데,
    • 사용자 프로세스 입장에서는 내용이 있는 페이지라고 굳건히 믿으며 그 페이지에 접근하려 하지만
    • 실제로는 그 페이지에는 내용이 없기 때문이다.(앞에서 할당만 받았지 내용을 load하진 않았다)
  • page fault를 다루는 프로시저가 진행될 동안, uninit_initalize가 호출되어 이전에 설정해둔 initializer를 호출한다.
  • 이 때 이 initializer는 anon_initializer 혹은 file_backed_initializer가 될 수 있다.
    
    
• life cycle of page
  • initialize ->(page_fault -> lazy-load -> swap-in -> swap-out ... 반복) -> destroy
  • life cycle 동안 이러한 각 전환들은, page type에 따라 요구하는 프로시저가 다르다. 위 라이프 사이클은 하나의 예시이다.
  • 이번 프로젝트에서 각 page type마다의 전환들을 구현하는 것이 주 목적이다.

Lazy Loading for Executable

• lazy loading에서는, 프로세스가 실행되면 오직 필요한 페이지들만 메인 메모리로 load된다.

  • 모든 페이지들을 바로 올리는 eager loading에 비해 오버헤드가 적다.
    
    

• 모든 페이지들은 처음 VM_INIT page로 초기화되며 생성된다.

  • struct uninit_page
  • uninitialized page를 생성하고 초기화하고 파괴하는 함수를 구현해야 한다.
    
    

• 유효한 page fault가 발생하면 exception.c의 page fault handler는 제어권을 vm_try_handle_fault로 넘긴다.
  
  

• bogus fault

  • 3가지 경우
    • lazy-loaded, swaped-out page, write-protected page
    • 여기서는 lazy-loaded만 고려한다.

• page fault가 lazy loading의 경우라면, 커널은 우리가 vm_alloc_page_with_initializer를 통해 설정한 initialier를, segment를 지연시키며 load하게 한다.

• vm_alloc_page_with_initializer()를 구현한다. 인자로 받은 page의 vm_type에 따라 그에 맞는 initializer를 셋팅한다. 그리고 uninit_new를 호출한다. 맨 처음 page가 생성될 땐 uninit으로 초기화되기 때문이다.

• vm_alloc_page_with_initializer

---

Stack Growth

• 프로젝트 2에서 stack들은, USER_STACK으로 부터 시작되는, 한 페이지 정도의 사이즈만 가지고 있었다. 따라서 프로그램의 실행은 단지 이 한 페이지에 의해 제한됐었다.
  • 이제, stack이 현재 사이즈보다 초과하려고 하면 추가적인 페이지를 할당하도록 구현한다.
• stack 접근의 경우에만 추가 페이지를 할당한다.
  • stack 접근과는 다른 접근을 구별할 수 있어야 한다.
  • 뭔 말이지?
  • stack 접근이 아닌 경우는 다 제꾸라는 건가?
    • 그렇다면 커널 공간을 가르키거나, NULL이거나, stack - 8보다 아래인 경우인가?
• User programs are buggy if they write to the stack below the stack pointer, because typical real OSes may interrupt a process at any time to deliver a "signal," which modifies data on the stack. However, the x86-64 PUSH instruction checks access permissions before it adjusts the stack pointer, so it may cause a page fault 8 bytes below the stack pointer.
  • 뭔 말이고...
  • 어쨋든 rsp로부터 8바이트 밑에서 page fault가 발생한다.
• system call(syscall_handler) 이나 page fault가 일어났을 때, 이 함수 인자인 struct intr_frame의 rsp를 가져올 수 있다.
• 잘못된 메모리 접근을 감지하기 위해 page fault에 의존하는 경우, 커널에서 page fault가 발생하는 경우도 처리해야 한다.
  • 커널 모드일 때도 page fault가 발생할 수 있다?
    • 커널의 스택도 넘칠 수가 있으니까.
    • 이 때도 stack을 새로 할당해주나? 아니면 그냥 종료시키나?
• 사용자 모드에서 커널 모드로 진입하면(lib/user/syscall.c의 syscall 함수에서 syscall instruction이 실행되고, syscall_init->syscall-entry.S의 어셈블리어로 인해 현재 쓰레드의 인터럽트 프레임의 rsp는 커널 스택을 가르키게 된다) 현재 쓰레드의 인터럽트 프레임의 rsp는 커널 스택을 가르키게 된다. 커널 모드이니 커널 스택에다가 데이터를 쌓게 되는 것이다. 주의할 점은 여기서 syscall_handler, 혹은 page_fault의 인자는 현재 쓰레드의 인터럽트 프레임이 아닌, 해당 함수를 진입할 때 넘겨준 인터럽트 걸리기 전의 쓰레드의 인터럽트 프레임으로, 이 때의 인터럽트 프레임은 유저 공간의 스택을 가르키는 rsp를 가지고 있을 것이다.
  • 어쨋든 커널 모드로 진입하여 만나는 함수인 syscall_handler 혹은 page_fault에서의 인터럽트 프레임은 커널 모드 전에 넘겨줬던 인자이기 때문에 유저 스택을 가르키는 rsp를 가진 인터럽트 프레임이지만, 현재 쓰레드(thread_current())의 인터럽트 프레임의 rsp를 찍어보면 커널 모드이기 때문에 커널 스택을 가르키고 있다.
• 유저 모드에서 커널 모드로 가는 그 지점에, 해당(현재) 쓰레드의 인터럽트 프레임의 rsp를 strucrt thread에 담아두어야 한다고 한다.
  • thread는 그대로 유지가 되므로 커널 모드로 진입했더라도 thread_current()를 하면 유저 모드 때의 쓰레드와 같은 쓰레드를 가르키고 있을 것이다. 따라서 struct thread는 바뀌지 않을테니, 커널 모드로 바뀌어도 struct thread는 유지되어, 커널 모드로 진입하기 전에 저장해두었던 rsp를 찾을 수 있을 것 같다.
  • rsp를 저장하는 자료구조를 만들어야 할 것 같다.
    
    
• stack growth를 위한 함수 수정
  • vm_try_handle_fault
    • stack growth 상황인지 식별할 수 있어야 한다.

---

Memory Mapped Files

• 이번 과제에서는 memory-mapped pages를 구현한다.
  • anonymous pages와는 다르게, memory-mapped pages는 file-backed로 맵핑된다. (file-backed pages를 말하는 것 같다)
  • 이 file-backed pages의 내용들은, 이미 존재하고 있는 어떤 파일의 데이터를 똑같이 가지고 있다.
  • page fault가 발생하면, 물리 프레임은 곧바로 할당되고, 파일의 내용들은 프레임으로 복사된다. (frame->kva에 memcpy를 쓰면 되나?)
  • file-backed pages는 unmap되거나 swap out될 때, 내용의 어떤 변화든 파일에 반영되어야 한다.(dirty bit가 1이면 반영해야 될 것 같은 느낌이 든다)
  • mmap은 너무 작은 파일에 적용하면, 오히려 page fault를 하는 데에 드는 비용이 더 많이 들 수 있다.
    • 자주 사용하지 않으면서 작은 파일이라면 그냥 read를 쓰는 것이 비용을 줄일 수 있다.

mmap and munmap System Call

• memory mapped files를 위한 두 시스템 콜인 mmap과 munmap을 구현한다.(시스템 콜이니까 syscall.c에서 작업해야 될 것 같다)
• mmap된 영역의 페이지들은 lazy load 되어야 한다.
• use the mmaped file itself as a backing store for the mapping. ???
  • 맵핑을 위해 그 맵핑된 파일을 backing store처럼 사용해라
  • mmap하면 파일의 내용이 물리 메모리로 올라가게 되는데, 그렇게 되면 디스크에 있는 내용을 쓰는 것이 아니라 물리 메모리에 있는 것을 쓰라는 건가? 아니면 쓰게 된다는 것인가? 먼 말이고...
• vm/file.c의 do_mmap과 do_munmap을 사용해 mmap과 munmap을 구현한다.

mmap

• mmap

void *mmap (void *addr, size_t length, int writable, int fd, off_t offset)

• fd 파일을 열고, 그 파일에서 offset만큼 떨어진 위치에서, length만큼을 가상 주소의 addr과 맵핑시킨다.
  • 이 때 addr은 struct page의(type이 VM_FILE인) va가 될 것 같다.
  • 테스트 케이스 중 mmap-misalign을 보니 mmap을 할 때 들어오는 addr 자체가 page-aligned이 되어 있어야 할 것 같다. 그렇지 않으면 fail을 내야 한다.
• 파일은 addr에서 시작하는 연속적인 virtual page에 맵핑된다.
• 파일의 길이가 PGSIZE의 배수가 아니라면, 마지막 페이지는 4096을 모두 데이터로 채우지 못한다. 마지막 부분은 삐져나오게 된다. page fault가 일어나 load되어야 할 때 나머지 부분은 0으로 채우고, unmap 혹은 swap out될 때에도 이를 반영해야 한다.(구체적으로는 어떻게 구현해야 할지 헷갈린다. 구현하면서 어떻게 해야할지 생각해봐야겠다)
• mmap이 성공하면 파일과 맵핑이 된 va를 반환한다.
• 반면 실패하면 파일과의 맵핑이 유효하지 않은 주소인 NULL을 반환한다.

• mmap 실패
  • fd로 open한 file의 길이가 0 바이트일 때 실패한다.
  • 인자로 받은 addr이 page-align이 되어 있지 않을 때 실패한다.
  • 혹은 맵핑으로 인해 생성되는 페이지들의 범위가, 이미 존재하는 맵핑 페이지들과(stack도 포함) 겹칠 때 실패한다.
  • Linux에서 0, 즉 NULL을 addr 값으로 주면 맵핑을 생성할 적절한 주소를 kernel이 알아서 찾아준다.
    • 하지만 핀토스에서는 가상 페이지 0을 맵핑되지 않는 것으로 간주하기 때문에 addr이 0이면 실패로 처리한다.
  • file의 특정 위치인 offset부터 맵핑시키려는 크기인 length가 0이면 실패한다.
  • fd가 console input과 console output을 나타내는 0과 1이면 맵핑할 수 없으므로 실패 처리한다.
• memory-mapped pages는 anonymous pages처럼 lazy load 되어야 한다.
  • vm_alloc_page_with_initializer 혹은 vm_alloc_page를 사용해 struct page를 만든다.

munmap

• munmap

void munmap (void *addr)

• Unmaps the mapping for the specified address range addr, which must be the virtual address returned by a previous call to mmap by the same process that has not yet been unmapped.
  • 뭔 말이고 또...
• process exit될 때 모든 맵핑들은 unmap된다. 맵핑이 unmap될 때 프로세스에 의해 쓰여진(write를 한, dirty bit가 1인?) 모든 페이지들은 파일에 반영이 되어야 한다.(file_write_at를 이 때 쓰는건가?)
  • 프로세스에 의해 write가 실행된 페이지가 아니라면(페이지에 dirty bit 관련 flag가 필요한건가?) 파일에 반영되면 안된다.
• 이렇게 반영을 마치고 나서 페이지가 제거된다. The pages are then removed from the process's list of virtual pages??? (정확히는 파악 못했다. 구현하면서 다시 보자)
• file을 닫거나 close하는 것은 맵핑을 unmap시키지 않는다.
  • 맵핑이 한 번 생성되면 munmap이나 process exit이 될 때까지는 이 맵핑은 유효하다. 사라지지 않는다.
  • 각 맵핑마다 독립적이고 분리된 파일 참조를 얻기 위해, mmap에서 file_reopen을 써야 한다.
    • file_reopen은 파일 객체를 복사해서 새로운 것을 반환해준다.
• 두 개 이상의 프로세스가 같은 파일을 맵핑할 때, 일관성이 유지되는 데이터를 본다는 요구사항은 없다. Unix는 이럴 때 똑같은 물리 페이지를 공유한다. 그리고 mmap은 사용자가 해당 페이지를 공유할 수 있도록, 혹은 private하게 사용할 수 있도록 하는 인자를 가지고 있다.
  • 이게 핀토스에서의 mmap을 말하는 것 같진 않다. 적어도 지금까지는. 지금의 mmap에는 이러한 인자가 없어 보인다.

---

Swap In/Out

• 메모리 swapping은 물리 메모리의 사용률을 극대화하기 위한 메모리 재생 기술이다.
  • 쉽게 말해서 메모리를 효과적으로 사용하기 위함이라고 하는 것 같다.
• 메인 메모리의 프레임이 할당되면, 사용자 프로그램의 할당 요청을 더 이상 처리할 수 없다.
  • 무슨 소리지? 꽉 찼을 때의 경우를 말하는 건가?
    • 메인 메모리의 프레임이 할당되면, 다른 사용자 프로그램이 그 메모리를 할당 요청할 수 없게 된다는 뜻인가?
  • 한 가지 솔루션은, 최근에 사용되지 않은 프레임을 교체하는 것이다.(이 때 근데 왜 디스크에 있다는 듯이 말하지?)
  • 이것은 그 메모리 자원을 할당 해제 시키고, 다른 사용자 프로세스가 사용할 수 있게 만든다.

• swapping은 OS에 의해 이루어진다. 메모리가 모두 할당되었음에도 불구하고 OS가 메모리 할당 요청을 받게 되면, 즉 frame을 만들어서 page에게 줘야 한다면, OS는 어떤 페이지를 swap disk로 내쫓는 선택을 하게 된다.(이 때 LRU 등의 알고리즘이 사용될 것 같다)
  • 이 때 그 쫓겨나려하는 메모리의 데이터들은 디스크에 모두 반영된다.(반영되어야 한다)
  • 사용자 프로세스가 그 swap out된 page에 접근하려고 하면, OS는 이전에 데이터가 반영된 그 page를 메인 메모리에 올리게 된다.
  • 이번에도 file_write_at, pml4_is_dirty, pml4_set_dirty를 써야 할 것 같은 느낌이 든다.(do_munmap이랑 비슷할 것 같은 느낌이다)

• swap out되는 페이지는 anonymous page이거나 file-backed page이다. 이번에는 이 두 경우에 대해 어떻게 swapping을 할지 구현해야 한다.

• 모든 swapping 연산들은 명시적으로 불려지는 것이 아니라, 함수 포인터들에 의해 불려진다.(감이 잘 안온다)
• 이 함수 포인터 들은 struct page_operations file_ops의 멤버들이고, 이것들은 page initializer에 의해 등록된다.(file_backed_initializer)
  
  • 이 친구들 말하는 건가?

Anonymous Page

• vm_anon_init과 anon_initializer를 변경하라고 한다.
• anonymous page(VM_ANON)는 file-backed page(VM_FILE)와는 다르게 백업 저장소가 따로 없다. 디스크에 anonymous page가 없다라고 생각해야 겠다.
  • anonymous page는 mmap으로 인해 불려진 것이 아니므로 mapped_file이 따로 없었으나 file-backed page는 mmap으로 생성되어 mapped_file이 있었다. 이러한 점으로 인해 file-backed page는 백업 저장소가 있다고 하는 것이지 않나 싶다. 디스크의 파일을 기반으로 하니까.
  • 어쨋든, 이렇게 anonymous page도 디스크로 가려면 디스크 영역이 필요할 것이다. 따라서 핀토스에서 이번에는 anonymous page의 swapping을 위해 임시적으로 swap disk라고 불리는 백업 저장소를 anonymous page에게 지원한다.
  • 어떻게... 주는교...?

• vm_anon_init

void vm_anon_init (void)

• 이 함수에서는 앞서 말한 anonymous page를 위한 백업 저장소인 swap disk를 셋업하라고 한다.(어떤 함수나 라이브러리를 쓰는건지 말이라도 해주지 좀 ㅎㅎㅎ)
  • 이러한 swap disk에서 사용 가능한 것과, 사용 중인 것을 구분하기 위해(관리하기 위해) 이러한 것들을 포함하는 자료구조가 필요하다.(아이고...)
  • 이것들도 PGSIZE, 즉 4096 bytes 단위로 관리되어야 한다.

• anon_initializer

bool anon_initializer (struct page *page, enum vm_type type, void *kva)

• 이것은 anonymous page를 initializer이다. swapping을 위해 anon_page에 정보를 담아야 한다.
  • 아까 말한 swap disk를 담아야 하나?
  • 이제 anonymous page가 swapping 할 수 있도록 anon_swap_in과 anon_swap_out을 구현해야 한다.
  • swap in이 되기 위해서는 swap out이 되어야 하므로, swap out을 먼저 구현하는 것이 나을 수 있다.
    • swap out, swap in이 이루어지면 각각의 과정에서 데이터를 디스크에 잘 반영하고, 가지고 올 때에도 안전하게 가져와야 한다.
      • swap out할 때 바뀐 데이터를 swap disk에 반영하고(file_write_at???), synchronization을 쓰라는 건가? lock_acquire 등등?

• anon_swap_in

static bool anon_swap_in (struct page *page, void *kva)

• swap disk에서 메모리로 데이터를 읽으면서, swap disk에서 메인 메모리로 anonymous_page를 swap in 한다.
  • 그 데이터의 위치는 그 page를 swap out할 때 swap disk가 struct page에 저장되어야 하는 위치이다.(머선 말이고!!??)
  • swap table을 업데이트 한다.

• anon_swap_out

static bool anon_swap_out (struct page *page)

• 메모리의 내용을 swap disk에 반영하면서, anonymous page를 메모리에서 swap disk로 swap out 한다.
  • 먼저 swap table을 사용하면서 swap disk의 free한 swap slot을 찾는다.(swap slot이랑 swap disk랑 다른가?)
    • swap partition에서 page 사이즈의 디스크 영역을 swap slot이라고 한다. 구현 해보면서 감을 잡자.
  • 그러고 나면 page의 데이터를 그 slot에 반영한다.(swap disk안에 page 사이즈의 swap slot이 있는건가?)
  • 이 데이터의 위치는 struct page에 저장되어야 한다.(왜 그럴까?)
  • 만약 이 때 free swap slot이 더 이상 없다면, kernel을 panic 시켜야 한다.

File-Mapped Page

• mmap에 의해 file-backed page(VM_FILE)는 disk의 file로부터 온 페이지로서, 그 file의 내용을 담고 있기 때문에 그 mmaped file이 백업 저장소로 사용된다.
  • file-backed page가 제거되면 mmaped file에 데이터를 기록한다. (앞에서 한 내용... 아닌가? 좀 다른 맥락인가?)

• file_backed_swap_in

static bool file_backed_swap_in (struct page *page, void *kva)

• file-backed page의 file로부터 데이터를 메모리에 읽히면서, 그 struct page의 kva에 swap in된다.(이 또한 감이 잘 안 잡힌다)

  • 이 때 file system을 사용하기 때문에 동기화를 해야 한다.
    • lock_acquire를 써야겠다.

• file_backed_swap_out

static bool file_backed_swap_out (struct page *page)

• 데이터를 file에다가 write하면서 그 page를 swap out 한다.
  • 이 때 그 page가 dirty한지 check를 먼저 한다.
  • dirty하지 않다면, 즉 write 되는 등 수정되지 않았다면 파일에다가 데이터를 수정하면서 swap out할 필요가 없다.
  • page를 swap out하고 나서, dirty bit를 0으로 만들어야 한다.
    

---

Hash Table

• va를 page table에 요청 했을 때, va가 kva와 맵핑되어 있지 않으면 page fault가 발생한다.

• 이 때 va가 포함된 가상 페이지에 대한 정보를 찾아서 swap in을 하던가 해야 한다.

• 이렇게 va에 해당하는 vm_entry(struct page)를 탐색해서 찾아야 한다.

  • 그러기 위해서는 vm_entry를 탐색할 수 있도록 하나의 자료구조로 저장해야 한다.
  • 여기서는 탐색이 빠른 hash table에 저장해둔다.
  • va를 해싱하여 저장한다.
  • 핀토스에서는 hash table에서 충돌이 일어날 경우 연결 리스트로 관리한다.

• Supplemental page table을 hash table로 구현(hash table 구현 또한 수정 가능)

• supplemental_page_table_init 함수 구현

• 해쉬 테이블 구조는 key' -> hashing -> (key'', value)였나?

  • 따라서 struct hash의 멤버를 직접 접근할 수 없고, 그럴 필요도 없다.
  • 대신 해쉬 테이블 함수와 매크로를 사용한다.
    

• hash_entry를 사용해 struct hash_elem을 얻을 수 있다.

• hash functions

  • hash_bytes
  • hash_string
  • hash_int

• hash_less_func, less?

• 사용자 프로그램의 virtual page를 위해 physical frame 할당 시 palloc_get_page(PAL_USER)을 통해서, 즉 user pool에서 할당되도록 해야 한다.

• 시간되면 카이스트 핀토스 영상 15분, 27분부터 다시 보자.

• assignment의 hash table example

• assignment의 page table

• Supplemental page table을 쓰면 page fault를 처리할 수 있는 이유는 무엇인가?

• 가상 메모리 관련 함수들의 매개변수가 거의 spt라서, thread에 hash를 넣는게 맞을까?

• 가상 메모리, page fault를 구현하기 위한 부가적인 정보들(부가적인 page 정보)는 그냥 struct page에다가 해야 맞지 않을까? spt에 하면 해당 page마다 정보를 담을 수가 없을 거 같음.

  • 오히려 쓰레드(프로세스)에 대한 부가적인 정보가 spt에 들어간다면 맞을 것 같음.

• Swap Table, Frame Table은 전역으로 짜도 되지 않을까?

• anon_page : 구조체에 멤버 추가 필요, 익명 페이지의 상태와 관련된 정보들?

• swap table에서 프로세스(쓰레드)에 대한 모든 페이지들을 다 가지고 있나?

• malloc, calloc은 kernel pool에서 가지고 온다.

  • palloc_get_page(PAL_USER)는 user pool에서 가지고 온다.

• PMT에 올라가는 page number, 즉 page, page table entry, struct page는 물리적인 메모리에 올라가는(PMT에 있으므로) malloc ㄱㄱ

• The contents will be loaded only at which it is truly needed, which is signaled by a page fault.

• struct page는 vm_entry로, page table entry이다.

• struct frame은 frame entry로, frame table entry이다.

---

PintOS - Virtual Memory 동영상

• process.c의 load_segment에서

uint8_t *kpage = palloc_get_page(PAL_USER);

---

카이스트 핀토스 강의 - Virtual Memory 1

* 이 동영상은 32비트 기준

• 실행가능한 파일 전체가 시작부터 모두 메모리에 적재되는 방식이 현재 핀토스이다.

  • 실행하지 않는 부분도 메모리에 적재되기 때문에 이는 비효율적이다.

• What we have to do

  • Enable demand paging/swapping
  • Enable stack growth
    • in current pintos process is allocated one page of stack
    • 현재 핀토스에서는 프로세스가 stack을 끝까지 다 채워놓고 overflow가 발생하면 프로세스가 죽는 방식인 것 같다.
  • Implement memory mapped file
    • implement mmap() and munmap()
    • 현재 2가지 physical page가 존재한다.
      • disk에 매칭된 페이지와, 그렇지 않은 페이지
        
        • 1, 2(Stack, BSS)는 disk와 매칭되어 있지 않으나 3, 4, 5(Code, Data)는 disk와 매칭되어 있다.
        • 이 때 1, 2가 anonymous page이다.
          • 초기화되지 않았기 때문에, 자신이 어떻게 될지 모르는 것들을 저장하고 있는 페이지
        • 3, 4, 5가 file-backed page이다. 파일에 기반하고 있다.
          • 이미 초기화되어 있던, 이렇게 쓰면 된다, 이렇게 저장된 정보였다라는, 이미 디스크에서, 파일에 기반한, 정보를 이미 담고 있던 페이지
  • Enable accessing user memory

• VPN : virtual page number

• PFN : physical frame number

• pintos has an array of physical page frame, and each frame has a number.

• page directory -> page table -> page

  • two-level page table

• swap space에는 disk의 physical page들이 있다.

• Demand Paging

  • Load the page from the disk as required.
  • A page in virtual memory can be either in-memory only(anonymous page) or part of a file(file-backed page)
  • 페이지가 위치할 수 있는 영역?
    • text : part of file. it's binary file
    • data : 페이지가 data 영역의 페이지, ex. ELF
    • BSS : 초기화되지 않은 전역 변수
      • in-memory only, so does not have matching disk space
    • stack and heap : in-memory only
    • mmap()ed region : part of file

• Page Fault

  • page_fault()는 주어진 페이지가 존재하지 않을 때 호출된다.
    • we have to modify this function.
  • 현재 핀토스는 page fault 발생 시 프로세스를 kill한다.
  • 하지만 이제 page fault가 발생하면
    • disk를 탐색하여
    • page frame을 할당하고
    • and load the appropriate page from the disk to the allocated page frame

• how pintos handles page fault, if the virtual memory is implemented.

  • page fault가 발생하면,
  • 그 메모리 접근이 유효한지, 즉 주소가 유효한지 확인한다.
    • 유효하지 않다면(invalid) 프로세스를 죽인다.
      • 다음과 같은 경우
        • Not valid user address
        • Kernel address
        • Permission error
          • attempt to write to the read-only page
          • 핀토스가 이 permission을 확인하여 이러한 잘못된 작동을 하려하는 프로세스를 죽인다.
  • 유효하다면(valid), 그리고 현재 메인 메모리에 존재하지 않는 page를 찾으려고 한다면
    • 가상 메모리 페이지로 가야 할 컨텐츠를 탐색한다.(실제 그 페이지가 존재하는 physical page를 찾는다)
      • file system이든, swap area든. 아니면 그냥 새로운 페이지가 될 수도 있다(all-zero page)
    • page frame을 할당 받는다.(frame table을 탐색하여 free frame을 찾는다)
      • DRAM(메인 메모리)은 free 혹은 allocated된 페이지들로 구성되어 있다.
      • page fault가 발생하면 DRAM의 page frame을 탐색하여 할당시켜야 한다.
    • file 혹은 disk로 부터 찾은 page, 아니면 all-zero page를 page frame으로 load시킨다.
    • once pintos fetch the data from the disk to the page frame, pintos has to update the page table, 끝
    • page를 찾았다면 메인 메모리에서 사용할 수 있는(free된 걸 말하는 건가?) page frame을 찾아서 할당시키고(allocate) 거기다가 데이터(페이지)를 덮어씌우는 건가? 그리고 나서 page table 업데이트?

• page table은 x86 CPU에 의해 만들어져있다. pml4 말하는 건가?

• Supplemental page table
  

  • virtual page number -> physical frame number
  • 가상 메모리를 구현하기 위해서는, 각 페이지마다 추가적인 정보가 필요하다.
    • virtual page가 disk 상에서 어디에 존재하고 있는지
      • 그래야 demand paging이 되지 않을까, 메인 메모리에 없을 때 disk에서 들고와야 하니까.
    • 주어진 virtual page가 file backed인지, in-memory(anonymous)인지
  • additional information
    • virtual page number
    • read/write permission
    • type of virtual page
      • a page of ELF executable file
        • 실행 파일은 수정되면 안된다. 따라서 general file과 ELF executable file로 분류를 나누었다.
      • a page of general file
      • a page of swap area(anonymous page)
        • does not have file backed region, does not have matching file.
    • 해당 페이지가 어느 곳으로부터 왔고(reference to the file object), 거기서 어디에 위치하고 있었는지?(offset)
    • page에 적힌 data 양
      • 4KB를 할당받지만, 모두 유효하진 않을 수도 있다.
      • ex. 2.6KB만 유효한 data일 경우
        • 페이지가 그 파일의 마지막일 경우 4KB로 딱 맞아 떨어지지 않을 수 있다.
          
    • swap area에서 어디에 위치하고 있는지
    • in-memory flag : 메모리에 있는지 없는지

• 가상 메모리를 구현하기 위한 Big Picture
  

• vm_entry가 page마다 선언되어 있다.(64비트에서 vm_entry는 뭐지? 구현하는 건가?)

  • struct page인 것 같다.

• 프로그램이 메인 메모리에 없는 데이터에 접근하려고 하면 page fault가 발생한다.

• 프로그램이 메모리의 특정 영역에 접근하려고 시도하면

  • 페이지 테이블을 먼저 확인한다.
  • 메모리에 없다면 page fault가 발생한다.
  • array of page frame entries(frame table)에서 free frame을 찾아 할당한다.

• set of vm_entry를 구현하기 위해 hash table을 사용할 것이다.

• process_craete_initd -> thread_create -> initd -> supplemental page table 초기화

• __do_fork 때도 supplemental page table을 초기화해준다.

• process_exit에서 vm entry(32비트), hash table을 deallocate한다.
  

• Address Space Initialization
  

  • Original Pintos : ELF 파일을 모두 읽어 모든 데이터를 physical memory에 할당시킨다.
    • 첫 번째 스텝 - load_segment() : data, code 세그먼트를 읽는다.
    • 두 번째 스텝 - setup_stack() : stack의 실제 페이지를 frame에 할당한다.
  • Pintos with VM
    • 페이지 테이블을 할당한다. 이 때 모든 entry는 맵핑되어 있지 않기 때문에 유효하지 않다.
    • 각 페이지의 physical memory를 할당하는 것이 아니라, 각 페이지에 대한 vm_entry를 할당한다.

• modify load_segment()
  

/* Get a page of memory. */
uint8_t *kpage = palloc_get_page(PAL_USER);
if (kpage == NULL)
	return false;

/* Load this page. */
if (file_read(file, kpage, page_read_bytes) != (int)page_read_bytes)
{
	palloc_free_page(kpage);
	return false;
}
memset(kpage + page_read_bytes, 0, page_zero_bytes);

/* Add the page to the process's address space. */
if (!install_page(upage, kpage, writable))
{
	printf("fail\n");
	palloc_free_page(kpage);
	return false;
}

• load_segment에서 지워져야 하는 부분(Delete)이다.

• Add해야 하는 부분은 vm_alloc_page_with_initializer에서 한다.

• vm_alloc_page_with_initializer에 aux로 다음 3가지 이상을 넘겨줘야 할 것 같다.

  • offset
  • size of the files to read(read_bytes)
  • zero_bytes
  • ...

• 그 다음 vm_entry를 hash table에 삽입한다.

• stack initialization
  

  • Original pintos
    • only 1 페이지를 할당하고
      • 따라서 스택을 다 쓰게 되면, 1 페이지 밖에 못 받았으니 1 페이지를 다 쓰게 되면 process가 kill된다.
    • page table을 셋팅하고(install page)
    • stack pointer(rsp)를 셋팅한다.
  • Add
    • stack을 위한 4KB의 struct page를 형성한다.(오직 stack을 위한 건가?)
    • 해당 vm_entry, 즉 struct page의 field를 initialize 한다.
    • hash table에 삽입한다.

• Design of Demand Paging
  

  • page가 메모리에 존재하지 않다면 (not-present) disk로부터 load한다.
  • 이러한 page fault가 발생하면 vm_entry를 탐색하여 메모리에 올라갈 가상 메모리가 있는지 탐색한다.
  • Demand Paging 단계
    • 1. 필요한 메모리가 물리 메모리에 올라가 있지 않다면 page_fault가 발생
    • 2. 가상 메모리 목록들(vm_entry 혹은 struct page)에서 해당하는 필요한 메모리가 있는지 확인한다.(사용자 프로세스의 메모리가 아니거나, 커널 공간이거나, NULL을 가르키는 등 잘못된 메모리를 사용자 프로세스가 요구할 수도 있다)
    • 3. 있다면 page frame, 즉 빈 물리 frame을 탐색하여 할당받는다.
    • 4. disk에서 data를 load한다.(lazy_load_segment)
    • 5. install_page() 함수를 사용해, 가상 메모리(va)와 물리 메모리(kva, kernel virtual address이지만, pintos는, 정확히는 x86-64 아키텍처는 물리 메모리에 직접적으로 접근하는 방법을 제공하지 않는다. 대신에 kernel virtual address를 물리 메모리랑 직접적으로 맵핑시켜놓았다. kernel virtual memory의 첫 번째 페이지는 물리 메모리의 첫 번째 페이지랑 맵핑 되어 있다. 그냥 kernel virtual memory의 첫 번째 페이지가 물리 메모리의 첫 번째 페이지라고 생각해야겠다)를 맵핑시키고 이를 pml4에 추가한다.

• 강의에서는 handle_mm_fault를 고치라고 하는데, 64비트 카이스트 핀토스에서는 vm_try_handle_fault 함수를 수정하면 될 것 같다.

• load a file page to physical memory
  

• 동적 객체인 vm_entry(struct page)를 할당 받기 위해 malloc을 사용할 수 있고, 해제할 때는 free를 사용하면 된다.

---

카이스트 핀토스 강의 - Virtual Memory 2

* 이 동영상은 32비트 기준

• 가상 메모리의 백그라운드를 구현하겠다.
• 구현해야 할 것들
  • Paging(Swapping)
  • Growing Stack
  • Memory mapped file
  • Accessing user memory

Swapping

• page frame를 관리하는 자료구조를 구현한다.
• LRU, clock, second-chance와 같은 page replacement 알고리즘을 구현한다.
  • victim 페이지가 data 세그먼트 혹은 stack 세그먼트 영역의 페이지일 경우 swap space에 저장한다.(swap out)
  • 이렇게 swap out된 페이지들은 Demand Paging에 의해 reload된다.
• 가상 메모리를 구현하기 위해서는 MMU로부터의 하드웨어의 지원이 필요하다.
  
  • 주목해야할 비트가 2가지 있는데, dirty bit와 access bit이다.
    • dirty bit
      • 해당 페이지가 물리 메모리에 올라가서, 해당 페이지에 데이터가 쓰여질 때 page table의 해당 페이지의 dirty bit가 하드웨어에 의해 1로 셋팅된다.
    • access bit
      • 해당 페이지가 참조될 때마다 page table의 해당 페이지의 access bit가 하드웨어에 의해 1로 셋팅된다.(그냥 참조될 때일까? 아니면 page frame을 얻었을 때일까?)
  • dirty bit가 1로 셋팅된 페이지가 희생자로 선택될 때, 즉 swap out 되어져야 할 때, 이 페이지에 일어난 변화는 disk에도 반영이 되어야 한다.
  • 하드웨어는 access bit를 0으로 재셋팅 시켜주지 않는다. OS가 0으로 해주어야 한다.
    • 사용자 프로세스가 가상 메모리의 페이지를 요구했을 때는 하드웨어가 알아서 1로 셋팅해주지만, swap out될 때는 OS가 0으로 셋팅해주어야 하는 것 같다.(하드웨어가 인지하여 0으로 셋팅해준다고 가정하면, swap space로 올 때 뜻하지 않게 왔음에도 불구하고 제대로 왔다고 0으로 셋팅해줄 수도 있으니까 그런가? 소프트웨어, 즉 OS가 0으로 셋팅해준다고 가정하면, 제대로 swap out할 때에만 0으로 셋팅해준다고 했을 때 제대로 swap out이 되지 않았다면 swap space에 들어가도 access bit이 1일 것 같다)
• page table manipulation functions
  • pml4_is_dirty
    • va의 page의 dirty bit가 0이 아니라면 true를 반환한다.
  • pml4_set_dirty
    • va의 page의 dirty bit를 0 혹은 1로 셋팅한다.
  • pml4_is_accessed
    • va의 page의 access bit를 반환한다.
  • pml4_set_accessed
    • va의 page의 access bit를 0 혹은 1로 셋팅한다.
• 물리 메모리를 차지하고 있는 페이지 중 어떤 페이지를 교체해줘야 하는지 알아야 하기 때문에 page frame이라는 자료구조가 필요한데 struct frame으로 구현이 되어 있다.
  • 물리 메모리 중 어떤 page frame을 가지고 있는지 frame number(kva)를 가지고 있다.
  • 이 struct frame은 어떤 가상 페이지에 의해 사용되고 있는지, 그 가상 페이지가 무엇인지 정보를 가지고 있다.(맵핑이 되어 있다)
    • struct frame 안에 struct page가 있다.
  • 어떤 쓰레드(프로세스)에 속해 있는지, struct thread에 대한 정보를 가지고 있다.
    • struct frame 안에 struct thread를 만들어야 할 것 같다.
  • LRU를 구현하기 위한 field를 가지고 있다?
    • 현재 시점으로서는 frame table에 속하기 위한 list_elem을 말하는 것 같다. 이것도 추가해야 겠다.
• swapping을 위한 struct frame의 사용
  
• LRU list(frame table 말하는 건가?)는 전역 변수로 선언해야 한다.
  • 일단 frame을 관리하기 위해서는 frame이 생성될 때, frame을 관리하는 자료구조에 넣어야 하니
  • vm_do_claim_page에서 vm_get_frame에 성공 시 frame table에 넣어주면 될 것 같다.

Growing Stack

• 현재 핀토스는 사용자 프로세스마다의 stack의 크기를 4KB로 고정해두었기 때문에, 사용자 프로세스가 이보다 더 많은 양의 지역 변수를 쓰려고 하면 프로세스는 kill되고 OS(핀토스)는 halt(정지)된다.
• 여기서 우리는 확장 가능한 stack을 구현해야 한다.
  • 사용자 프로세스가, 사용자 프로세스의 stack 바깥에 놓여 있는 주소에 접근하려고 하면, stack을 확장하는 것으로 간주하고 stack을 확장한다.
    • ex. 사용자 프로세스가 rsp - 32의 주소에 접근하려고 했다면 stack을 확장한다.
      • 여기서 32의 의미가 뭐지? 64비트에서는 64이려나? 8바이트?
      • rsp가 끝까지 간 상태에서 push를 할 경우 rsp가 stack의 맨 끝인 stack_bottom에서 + 32(혹은 64?)를 가르키게 될 텐데 이 때를 말하는 건가?
      • stack 초과로 인한 page fault 인지 확인할 필요가 있을 것 같다.
• stack의 최대 크기는 8MB로 제한한다.
  • 64비트 카이스트 핀토스에서는 1MB로 제한한다.
    
• grow limit 내의 접근일 경우, 유효한 접근으로 보고 stack을 확장한다.
  • 하지만 이를 넘어서는 접근은 유효하지 않은 접근으로 보고 segmentation fault를 발생시킨다.
  • 잘못된 접근이니까.
• Stack extension mechanism
  
  • page fault가 발생하면 frame을 할당 받는다.
  • va에 해당하는 vm_entry(struct page)를 탐색해서 찾고 vm_type을 확인한다.
    • ANON이면 swap space에서 가져오면(swap in) 된다. file mapped가 아니라서 그대로 가지고 오면 되는 것 같다.
    • stack growth 상황이면 stack을 확장한다.
  • 완료 후 page table을 setup한다. (install_page 혹은 pml4_set_page)

Memory Mapped File

mmap

• mmap을 사용하면, video controller와 같이 빠른 응답 시간이 필요한 장치들에게 적합하다.
  • read를 자주 하는데 mmap을 사용하면 read로 disk에 가서 계속 읽는 것이 아니라, mmap으로 1번만 disk에서 읽어서 맵핑한 것들을 물리 메모리에 올려두면 read를 하지 않고(필요할 때마다 시간이 많이 드는 I/O 작업인 disk에 가는 것이 아니라) 바로바로 물리메모리에서 읽어 오기 때문에 시간이 절약될 것 같다.
• role of mmap
  • file을 process address space, 즉 사용자 주소 공간(virtual address)의 어느 한 주소에 맵핑시키고 싶을 때 사용한다.
  • 이 맵핑된 가상 주소에 무언가를 저장한다면, 파일의 내용들이 직접적으로 반영이 될 것이다. ???

• mmap and munmap의 디테일
  • mmap을 사용하면 디스크의 파일이 프로세스의 가상 주소 공간 중 어떤 가상 주소(addr)에 맵핑된다.
  • 1. mmap이 호출되면, vm_entry(struct page)를 만든다.
    • file의 사이즈가 3개의 페이지라면, 3개의 연속적인 주소 공간을(struct page) 할당 받는다.
    • 즉 파일의 페이지 수에 맞춰, 연속적으로 이어지는 vm_entry를 만든다.
  • 2. 만들어진 vm_entry를 spt에 넣는다.
  • 3. 이제 프로세스가 이 vm_entry에 접근하려고 하면, 그러니까 page의 va 영역에 접근하려고 하면 demand loading이 일어나게 된다.
• 64비트 카이스트 핀토스의 mmap은 5개의 인자를 필요로 한다.
  • void *addr : 가상 주소 공간 중 어디에 파일을 맵핑시킬지, 즉 virtual address이다.
  • size_t length : 파일에서 필요한 데이터의 길이
  • int writable : 해당 페이지에 write 할 수 있는지 없는지를 나타내나?
  • int fd : 어떤 파일을 가상 주소에 맵핑시킬건지
  • off_t offset : 그 파일의 어디에서 맵핑을 시작할건지
• demand paging 방식으로 데이터를 메모리에 적재한다.
• memory mapped page, 즉 file-backed page는(파일이 아니고 페이지이다) swap space가 아닌 파일의 원래 위치로 swap out된다.(데이터가 변경되었으면 변경된 것도 반영을 하나?)
• fragmented page라면 페이지의 사용되지 않는 부분은 0으로 채워야 한다.
  • 10KB 파일이라면 3개의 페이지가 생길텐데 이 중 1개의 페이지의 나머지인 사용하지 않는 2KB는 0으로 채워야 한다.
• mapping id를 반환한다.
  • 이 때 이 id는 프로세스 내의 mapped file들 사이에 식별해내기 위해 unique하다.(모든 mapping들은 각자 고유의 id를 가지고 있다. 겹치지 않는다)
• mmap이 실패하는 경우
  • mmap하려는 파일의 사이즈가 0일 때
  • addr이 페이지 단위로 정렬된 주소가 아닐 때
  • addr이 이미 사용 중일 때(이미 같은, 혹은 다른 파일과 맵핑 중일 때를 말하는 건가?)
  • addr이 NULL(0)일 때
  • STDIN(0), STDOUT(1) 파일과는 맵핑이 불가능하다.

munmap

• munmap
  • mmap_list에서 맵핑된 것들을 unmap시킨다.
• Requirements
  • 프로세스가 종료될 때(process_exit) 프로세스의 모든 맵핑들은 암묵적으로 unmap되고 있다.
  • 맵핑이 unmap될 때 페이지의 내용들은 파일에 쓰여져야 한다.(바뀌었으면 디스크의 파일에도 반영이 되어야 한다)
  • munmap을 함에 따라, 페이지들은 프로세스의 가상 페이지 리스트에서 제거된다. Upon munmap, the pages are removed from virtual page list of the process.
  • mmap에 따라 맵핑이 한 번 생성되면, mmap하는 파일이 닫히든 삭제되든 mmap에 의해 생성된 맵핑은 unmap될 때까지 사라지지 않고 유효하다.(즉 파일이 닫히거나 삭제된다고 해서 맵핑이 사라지지 않는다)
  • 두 개 이상의 프로세스가 똑같은 파일을 맵핑한다면, 그 프로세스들은 동시적으로 맵핑한 것들을 볼 수 없다.(맵핑한 것들이 복제되어 프로세스에게 주어지기 때문에, 프로세스 각자가 쓰다보면 파일의 내용이 서로 달라지게 된다. 애초에 복제되어서 주어지기 때문에 같은 맵핑을 받더라도 쓰다보면 파일의 내용이 서로 달라지게 된다)
• munmap의 동작
  
  • 1. mmap_list에서 어떤 mapping을 제거할지 순회한다.
  • 2. mapping(mmap_list)를 찾았다면 그 안의 VM_FILE 타입인 struct page들을 모두 해제한다.(할당해제하라는 건가?)
  • 3. 이후에 mmap_list를 해제한다.
    • 이 때 바뀐 파일의 내용이 디스크의 파일에도 반영되도록 write back해줘야될 것 같은 느낌이 든다.

struct mmap_file

• additional structure(구조체 하나 더 만들어야 하나...?)
• 맵핑된 파일로부터의 정보들을 담고 있는 자료구조이다.(아직 무슨 느낌인지 감이 잡히진 않는다)
  • 담고 있는 정보들
    - mapping id
    - (pointer to)mapping file object
    - mmap_file list element
    - vm_entry list(이 맵핑과 연관된 struct page들)
    
• 조금 헷갈린다. VM_ANON 페이지들은 hash table인 spt의 vm에서 관리하는 것 같고,
• mmap_file들 즉 맵핑들은 list를 만들어서 따로 관리하는 것 같다.
  • 이 맵핑으로 인해 만들어진 vm_entry, 즉 struct page들(VM_FILE)들이 mmap_file의 vme_list로 연결되어 있다.
• thread
  • mmap_list > mmap_file > VM_FILE
  • vm > hash table > VM_ANON

vm_try_handle_fault

• struct page가 VM_FILE이면, 그 struct page의 맵핑에 해당하는 데이터를 load시킨다.
  • (vm_try_handle_fault와 vm_alloc_page_with_initializer를 수정해야 할 것 같다)

process_exit

• mapping_list의 모든 vm_entry를 release한다.(제거하라는 건가?)

Managing mapped files

• struct thread에 mmap_list를 추가해야 한다.
  • 쓰레드와 연관된 맵핑들(mmap_file)이 여기에 연결되어 있다.
  • 이 맵핑들은 페이지 혹은 페이지들을 가지고 있다.
    • mmap할 때 맵핑하고자하는 것이 2페이지, 3페이지가 될 수 있다.
    • 이러한 페이지들이 mmap_file에 연결되어 있다.

Modify page fault

• page fault을 모두 handle할 수 있는 최종 모습이다.

mmap & munmap

• file_reopen을 사용하는 것을 보니 복사해서 던져주는 것 같다.
• munmap이 필요하여 mmap_list를 순회할 때 제거하려는 맵핑의 id가 일치하는지, mapid을 탐색하는 것 같다.
  • 마지막에는 file_close도 해줘야 하는 것 같다.

---

APPENDIX - Virtual Address

The x86-64 doesn't provide any way to directly access memory given a physical address. This ability is often necessary in an operating system kernel, so Pintos works around it by mapping kernel virtual memory one-to-one to physical memory. That is, virtual address > KERN_BASE accesses physical address 0, virtual address KERN_BASE + 0x1234 accesses physical address 0x1234, and so on up to the size of the machine's physical memory. Thus, adding KERN_BASE to a physical address obtains a kernel virtual address that accesses that address; conversely, subtracting KERN_BASE from a kernel virtual address obtains the corresponding physical address.