[DevLog][PintOS] PRJ3 Virtual Memory/Memory Management to Stack Growth

Project3: Virtual Memory

01) Memory management

struct page

요구 페이징 (Demand Paging)을 구현하고, 스왑 인/아웃을 관리하기 위한 페이지 구조체가 다음과 같이 선언되어 있다. va는 페이지의 시작 주소, 즉 유저 프로세스의 가상주소이다. frame은 페이지와 매핑된 물리 메모리 정보를 가지고 있는 구조체로, 매핑 전까지는 NULL로 유지된다.

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

핀토스의 PRJ3에서는 페이지를 세 가지 타입으로 나누는데, (page_cache를 제외하고 보자면) uninit, anon, file이다. anon은 스택/힙과 같은 anonymous 메모리를 말한다. file은 mmap을 통해 파일과 매핑된 메모리, 또는 초기에 lazy_load_segment 함수를 통해 올린 .text, .data 세그먼트와 같은 file_backed_memory 를 말한다. uninit은 가상주소의 메모리 영역이 예약되어 있지만, 실제로 물리 메모리와 매핑되지 않은 상태를 의미한다. 따라서, page fault가 발생했는데, 해당 주소가 uninit type의 페이지라는 것을 커널이 알고 있다면, (즉, lazy load가 필요한 상황임을 알고 있다면) 물리 메모리와 해당 가상주소를 매핑하여 anon 또는 file type의 메모리로 초기화해 줄 수 있다.

page map level 4

/* The function table for page operations.
 * This is one way of implementing "interface" in C.
 * Put the table of "method" into the struct's member, and
 * call it whenever you needed. */
struct page_operations {
  bool (*swap_in)(struct page *, void *);
  bool (*swap_out)(struct page *);
  void (*destroy)(struct page *);
  enum vm_type type;
};


#define swap_in(page, v) (page)->operations->swap_in((page), v)
#define swap_out(page) (page)->operations->swap_out(page)
#define destroy(page) if ((page)->operations->destroy) (page)->operations->destroy(page)

• operations: 각 페이지의 동작을 정의한다. 포인트는 페이지의 타입이 변할 때마다 swap_in, swap_out, destroy 필드에 해당 타입의 연산을 구현한 함수를 매핑한다는 점이다. 이러한 방식을 사용하면, 페이지의 타입에 관계없이 swap_in 매크로를 사용해 각 페이지별로 다른 루틴을 실행시킬 수 있다. uninit type의 swap_in을 실행하면, anon_initializer가 실행되고, 이 때 operation 필드를 anon_operation으로 바꾸어 주는 식이다.

bool anon_initializer(struct page *page, enum vm_type type, void *kva) {
  /* Set up the handler */
  page->operations = &anon_ops;
  struct anon_page *anon_page = &page->anon;
  ...

• union: 페이지의 타입에 따라 관리해야 할 정보가 다를 수 있다. 이를테면, uninit type의 페이지는, 물리 메모리와 매핑될 때 실행해야 할 함수 (init, initializer ...) 포인터를 가지고 있다가 매핑된 이후에 함수를 실행함으로서 lazy load할 수 있다. 또 file_backed type의 페이지는, 물리 메모리와 매핑이 해제될 때 변경된 내용을 파일에 다시 써 주어야 할 수 있으므로 매핑 정보를 들고 있어야 한다. 이러한 정보를 관리해주기 위해 구조체 안에 필드를 각각 다 만들 필요 없이, (페이지는 한 번에 하나의 상태만 가지므로) union을 사용한다. union은 메모리 공간을 멤버가 공유하는 자료구조인데, 그 크기는 가장 큰 멤버의 크기로 결정된다. 따라서 한 번에 하나의 멤버 변수만 사용할 수 있다. 그래서 상태별 정보를 저장하는데 유용한 것 같다.

)

https://www.tcpschool.com/

Supplemetal Page Table

다양한 Page Fault 시나리오를 처리하기 위해 Supplemental Page Table을 사용한다. 이를테면, lazy load해야 하는 가상주소인지를 확인하기 위해 SPT를 확인해볼 수 있다. 또, SPT 안의 page struct를 보고 이 페이지가 물리 메모리와 매핑될 때 수행되어야 할 작업 (ex. file read)을 실행할 수 있다.

우리 조는 SPT를 해시 테이블로 구현했다. 해시 테이블은 key와 value를 매핑하는 자료구조이다.

👀 Wikipedia 정리

• associative array (연관 배열): CS분야에서 associative array, map, symbol table, 또는 dictionary는 각 키가 해당 집합에서 최소 한 번 이상 등장하는, 여러 개의 키-값 쌍의 집합으로 이루어진 추상 자료형이다. 수학적 용어에서 associative array란 유한한 정의역을 가진 함수이다. 일반적으로 lookup, remove, insert 연산을 지원한다.
• dictionary problem: associative array를 구현하는 효율적인 자료구조를 설계하는 고전적인 문제이다. 이 문제의 해답으로 제시된 것 중 주요한 두 가지가 바로 hash table과 search tree이다.
• hash table: 해시 테이블은 연관 배열을 구현하기 위해 hash function을 사용해 인덱스를 계산하고, 값을 해당 인덱스의 버킷(또는 슬롯)에 저장한다. 저장된 값을 찾기 위해서는 다시 hash function을 사용해서 인덱스에 접근한다. 이상적으로는, 하나의 키가 하나의 값으로 매핑되어야 하기에 각 버킷에 저장되는 값은 하나여야 한다. 그러기 위해서, 모든 키에 대해 해시 함수의 리턴값이 유니크해야 한다. 하지만 대부분의 해시 테이블 디자인은 완벽하지 않은 해시 함수를 사용하기에, 둘 이상의 키에 대해 같은 index를 생성하는 hash collision이 발생할 수 있다.

pintos의 include/lib/kernel/hash.c에서 제공하는 해시 테이블 자료구조는 최초 4개의 버킷으로 해시 테이블이 초기화되고, 이 버킷들은 struct list타입을 갖는다. 즉, 버킷 하나에 여러 개의 값이 저장될 수 있고, list의 사용법과 동일하게 저장하고자 하는 구조체 안에 hash_elem필드를 추가함으로서 구현할 수 있다. 테이블에 하나가 insert될 때 마다 필요한 버킷의 수를 재계산하여 (각 버킷 당 BEST_ELEMS_PER_BUCKET개만 저장하도록) 재배치하는 rehash 함수를 돌린다. 버킷이 늘어날 필요가 없는 경우 rehash하지 않는다. 이러한 방법을 통해 해시 테이블의 lookup, insert, remove는 $O(1)$ 시간복잡도를 갖게 된다.

/* Returns the bucket in H that E belongs in. */
static struct list *find_bucket(struct hash *h, struct hash_elem *e) {
  size_t bucket_idx = h->hash(e, h->aux) & (h->bucket_cnt - 1);
  return &h->buckets[bucket_idx];
}

👀 버킷의 개수는 왜 2의 제곱수일까?

버킷은 2의 제곱수로 늘어나는데, (4, 8, 16 , ...) 이는 해시 코드를 통해 데이터가 저장될 버킷의 인덱스를 결정할 때 사용하는 모듈러 연산을 최적화하는 목적으로 이해될 수 있다. 버킷을 찾는 위 코드를 보면 hash_code % bucket_count가 아니라 hash_code & (bucket_count - 1)이런 식으로 모듈러 연산을 구현하고 있는데, 만약 버킷의 수가 2의 제곱수라면 bucket_count - 1을 함으로서 최상위 1비트 이하 비트를 반전시킬 수 있다. 이 값을 AND 연산을 취하면 다음과 같이 모듈러 연산과 동일해지게 된다. 비트 연산은 모듈러 연산 대비 빠르다. (이거 말고 또 다른 이유가 있을 것 같다. 찾아볼것..)

hash_code = 13 // 1101
buck_cnt  = 4  // 100

hash_code & (buck_cnt - 1) = 1101 & 0011 // 1 is result of modulo(hash_code, buck_cnt)

자료구조를 결정했으니 spt와 관련된 함수를 구현해주면 된다. 기존 해시 코드에 있는 함수를 그대로 사용한다.

• supplemental_page_table_init: hash_init을 콜하고, hash_hash_func와 (hash_find에 필요한) hash_less_func을 넣어준다.
• spt_find_page: 가상주소값을 기준으로 spt를 검색하여 반환한다.
• spt_insert_page: 페이지를 해시 테이블에 삽입한다.

struct frame

/* The representation of "frame" */
struct frame {
  void *kva; /* kernel virtual address */
  struct page *page;
};

물리 메모리를 관리하기 위한 구조체이다. palloc_get_page로 받아온 물리 메모리의 kva, kernel virtual address를 저장한다. 메모리를 모두 사용해 스왑 디스크 공간으로 evict할 경우와 같이 프레임을 관리할 때 프레임 테이블과 프레임 구조체를 사용할 수 있겠다.

👀 커널 가상 주소?

pintos 코드를 짜다 보면 두 가지 주소체계를 마주하게 된다. 하나는 pml4를 사용한 주소체계로, 각 레벨의 페이지 테이블의 오프셋을 9비트씩, 그리고 프레임 오프셋을 12비트 저장하고 있는 가상주소다. 다른 하나는 커널의 주소공간을 특정하기 위해 설정된 라인인 KERN_BASE를 더하거나 뺌으로서 가상주소와 물리주소를 매핑하는 주소체계로, 커널 코드에서 작동한다. ..? 이 부분을 좀 더 알기 위해서는 palloc.c의 palloc_init을 보아야 할 것 같다..

👀 loader.S의 pml4 만드는 부분

/* loader.h */ 
/* Physical address of kernel base. */
#define LOADER_KERN_BASE 0x8004000000

/* start.S */
#define RELOC(x) (x - LOADER_KERN_BASE)

...

#### Create page directory and page table and
#### set page directory base register (cr3).
setup_page_table:
# 1. fill boot_pml4e with zeros
    lea (RELOC(boot_pml4e)), %edi  // boot_pml4e에서 LOADER_KERN_BASE를 빼서 %edi 레지스터에 저장
    xor %eax, %eax               // %eax를 0으로 초기화
    mov $0x400, %ecx             // %ecx = $0x400 (1024)
    rep stosl (%edi)             // %eax를 %edi가 가리키는 위치에 저장하고 %edi를 증가시키는 것을 %ecx만큼 수행한다.

# 2. set pdpts
    lea (RELOC(boot_pml4e)), %edi  // pml4 physical addr
    lea (RELOC(boot_pdpt1)), %ebx  // pdpt1 physical addr
    orl $(PTE_P | PTE_W), %ebx     // pdpt1 is p & w
    mov %ebx, (%edi)               // pml4 save pdpt1
    lea (RELOC(boot_pdpt2)), %ebx  // pdpt2 physical addr
    orl $(PTE_P | PTE_W), %ebx     // pdpt2 is p & w
    mov %ebx, 8(%edi)              // pml4 save pdpt2

# 3. set pdpes
    lea (RELOC(boot_pdpt1)), %edi  // pdpt1 physical addr
    lea (RELOC(boot_pde1)), %ebx   // pde1 physical addr
    orl $(PTE_P | PTE_W), %ebx     // pde1 is p & w
    mov %ebx, (%edi)               // pdpt1 save pde1

    lea (RELOC(boot_pdpt2)), %edi  // pdpt2 physical addr
    lea (RELOC(boot_pde2)), %ebx   // pde2 physical addr
    orl $(PTE_P | PTE_W), %ebx     // pde2 is p & w
    mov %ebx, (%edi)               // pdpt2 save pde2

# 4. setup pdes
    mov $128, %ecx
    lea (RELOC(boot_pde1)), %ebx   // pde1 physical addr
    lea (RELOC(boot_pde2)), %edx   // pde2 physical addr
    add $256, %edx                 // %edx = 256 (2^8)
    mov $(PTE_P | PTE_W | 0x180), %eax // 0x183

fill_pdes:
    mov %eax, (%ebx)               // pde1 = %eax
    mov %eax, (%edx)               // pde2 = %eax
    add $8, %ebx                   // next
    add $8, %edx                   // next
    add $0x200000, %eax            // %eax += 2MB
    dec %ecx                       // %ecx --
    cmp $0, %ecx                   // %ecx = 128, loops 128
    jne fill_pdes

# 5. Load page directory base register (cr3).
    lea (RELOC(boot_pml4e)), %eax
    mov %eax, %cr3

...

// reserve 0x1000 (4096) bytes memory.
boot_pml4e:
  .space  0x1000
boot_pdpt1:
  .space  0x1000
boot_pdpt2:
  .space  0x1000
boot_pde1:
  .space  0x1000
boot_pde2:
  .space  0x1000

👀 알아볼 내용들..

• RELOC 매크로를 통해 kernel virtual address에서 physical address로 바꾸어서 pte에 기록하고 있는데, 그렇다면 kernel va와 pa의 매핑이 언젠가 코드상에서 이루어진 상태일 것 같다. 그 작업을 하는 부분은 어디에 있는지?
• page_init에서 만드는 base_pml4랑은 뭐가 다른지? → base_pml4는 모든 유저 프로세스가 일차적으로 상속하는(?) 내용이다. base_pml4에는 커널 코드가 write-protect하게 주소 지정이 되어 있는데, pml4_create에서 바로 이 pml4의 내용을 가져온다. pml4_activate(NULL); 같은 코드를 실행하면 내부적으로 pml4 ? pml4 : base_pml4 식으로 base_pml4가 cr3 레지스터에 올라간다.

/* Creates a new page map level 4 (pml4) has mappings for kernel
 * virtual addresses, but none for user virtual addresses.
 * Returns the new page directory, or a null pointer if memory
 * allocation fails. */
uint64_t *pml4_create(void) {
    uint64_t *pml4 = palloc_get_page(0);
    if (pml4) memcpy(pml4, base_pml4, PGSIZE);
    return pml4;
}

02) Anonymous Page

디스크 기반이 아닌 페이지, 즉 익명 페이지는 주로 스택 또는 힙 메모리를 가리킨다.

• Anonymous page: 파일과 매핑되지 않은 페이지
• File-backed page: 디스크에 있는 파일과 직접 매핑된 페이지로, 이 페이지에서 변경된 내용은 파일에도 반영되어야 함.

👀 ELF 파일을 로드할 때 file-backed가 아닌 anonymous로 지정하는 이유?

static bool load_segment(struct file *file, off_t ofs, uint8_t *upage,
                         uint32_t read_bytes, uint32_t zero_bytes,
                         bool writable) {
  ...
  while (read_bytes > 0 || zero_bytes > 0) {
    ...
    if (!vm_alloc_page_with_initializer(VM_ANON, upage, writable,
                                        lazy_load_segment, aux)) {
      return false;
    }

File-backed page는 페이지의 변경사항을 디스크의 파일에 저장해야 하는 페이지 종류를 나타내기 위한 타입이다. ELF 파일의 코드와 데이터(.data, .bss) 영역은 변경되었다고 해서 디스크에 반영되면 안 된다. 따라서 VM_ANON으로 initialize 하도록 타입을 지정한다. (그리고 swap out되었다가 다시 swap in 되었을 때도 이전의 변경내용을 유지해야 한다. 즉, 파일이 아닌 swap disk에 기록되어야 한다.)

Lazy loading segments

ELF 실행 파일을 lazy하게 load해보자

bool vm_alloc_page_with_initializer(enum vm_type type, void *upage,
                                    bool writable, vm_initializer *init,
                                    void *aux);

VM의 load_segment함수는 void* kpage = palloc_get_page(PAL_USER | PAL_ZERO); 대신 이 함수를 불러서 가상주소공간을 예약해두고, 실제 해당 주소에서 페이지 폴트가 발생했을 때 물리 메모리와 매핑해준다. 예약된 가상주소공간임을 알기 위해 spt를 활용한다. 즉, 위 함수를 실행하면, 4KB 물리 메모리를 받는 것이 아니라, struct page 라는 작은 구조체만 만들어서 현재 스레드(또는 유저 프로세스)의 spt에 넣어 둔다.

struct page* page = calloc(1, sizeof(struct page));
switch(type)
    case VM_ANON:
        uninit_new(page, upage, init, type, aux, anon_initializer);
    case VM_FILE:
        uninit_new(page, upage, init, type, aux, file_backed_initializer);
    ...

spt_insert_page(&thread_current()->spt, page);

uninit.c에 있는 uninit_new함수는 주어진 인자를 page 구조체의 필드에 넣어주는 함수이다. 아직 초기화되지 않은, 즉 물리 메모리와 매핑되지 않은 페이지를 의미한다. 인자로 전달된 type에 따라 initializer 함수를 넣어 주면 page->uninit->initializer 필드에 넣어두었다가 실행된다. (언제 실행되냐면!! uninit의 swap_in 때)

load_segment 함수는 위와 같이 가상주소공간을 예약해두는 것으로 종료된다. 그 후 프로세스가 실행되어 해당 페이지에 fault가 발생하면 실제 ELF 파일의 내용을 읽어서 로드해주어야 한다.

// init.c 과정 중 페이지 폴트의 vec_no에 page_fault 함수를 매핑해 둔다.
// 타이머 인터럽트는 intr_register_ext로 초기화했지만
// page fault는 internal exception이므로 intr_register_int로 초기화.
void exception_init(void) {
  ...
  intr_register_int(14, 0, INTR_OFF, page_fault, "#PF Page-Fault Exception");
}

// intr_handler 함수 안에서 page_fault가 콜 된다.
static void page_fault(struct intr_frame *f) {
  bool not_present;    /* True: not-present page, false: writing r/o page. */
  bool write;          /* True: access was write, false: access was read. */
  bool user;           /* True: access by user, false: access by kernel. */
  void *fault_addr;    /* Fault address. */
  struct thread *curr; /* Current thread. */

  fault_addr = (void *)rcr2();

  /* Turn interrupts back on (they were only off so that we could
     be assured of reading CR2 before it changed). */
  intr_enable();

  /* Determine cause. */
  not_present = (f->error_code & PF_P) == 0;
  write = (f->error_code & PF_W) != 0;
  user = (f->error_code & PF_U) != 0;

#ifdef VM
  /* For project 3 and later. */
  if (vm_try_handle_fault(f, fault_addr, user, write, not_present)) return;
#endif

exception.c의 exception_init 에서 페이지 폴트의 vec_no인 14번과 page_fault 함수가 매핑되고, 14번 인터럽트가 발생하면 이 함수가 실행된다. 그 안의 vm_try_handle_fault가 우리가 구현해야 하는 함수이다.

요구 페이징을 구현하므로, 페이지 폴트가 발생하는 시나리오 중 단순 bad ptr이 아닌 lazy loading 인 경우가 생겼다.

+) bad pointer가 아닌 세 가지 fault case

1. lazy loading: 페이지에 해당 파일로부터 읽어서 데이터를 로드해줘야 한다. 또는 익명 페이지인 경우 물리 메모리를 할당해 매핑해야 한다.
2. write-protect: 쓰기 보호된 페이지에 대한 쓰기 접근인 경우 실제로 fault가 발생해야 한다.
3. swap-out page: 페이지 교체로 인해 페이지가 스왑 디스크로 out된 상황이라면, 다시 in해야 한다.

lazy loading만 생각해 보면, 만약 fault가 발생한 address가 이전에 예약된 주소공간이라면, spt에서 찾을 수 있다. 따라서 spt를 검색해서 해당 가상주소를 갖는 페이지 정보가 있는지 확인하고, 있다면 물리 메모리를 매핑해준다. 없다면 return false 한다.

bool vm_do_claim_page(struct page* page) {
    struct frame* frame = vm_get_frame();

    frame->page = page;
    page->frame = frame;

    /* mark page as present. */
    page->flags = page->flags | PTE_P;

    return swap_in(page, frame->kva);
}

물리 메모리를 할당하고, 구조체끼리 연결한 후 swap_in을 실행한다. 이 때는 uninit_operation의 swap_in이 실행되는데, 이는 uninit_initialize 함수이다.

/* Initalize the page on first fault */
static bool uninit_initialize(struct page *page, void *kva) {
  struct thread* curr = thread_current();
  struct uninit_page *uninit = &page->uninit;

  /* Fetch first, page_initialize may overwrite the values */
  vm_initializer *init = uninit->init;
  void *aux = uninit->aux;

  return uninit->page_initializer(page, uninit->type, kva) &&
         (init ? init(page, aux) : true) && install_page(page);
}

여기서 이전에 vm_alloc_page_with_initializer에서 인자로 넘겼던 init, aux와 initializer 가 사용되는 것을 볼 수 있다. anon_initializer 또는 file_backed_initializer를 실행하고, install_page로 현재 스레드의 pml4에 매핑을 만들어 주었다. 이 함수를 실행함으로서 lazy loading 과정이 마무리된다.

두 번째 그림에 하나 빠진 게 있는데, 마지막으로 해당 가상주소와 할당된 메모리의 물리주소를 현재 스레드의 pml4에 set해주어야 한다.

Copy spt table

fork 시스템 콜을 호출할 때, 부모와 자식 간의 spt table을 복제해 주어야 한다. 주의할 점은, file_info와 같이 malloc으로 할당받은 구조체 정보도 복제해야 한다는 점이다. 따라서 타입별로 복제를 잘 해주는 게 중요하다.

또 프로세스 fork를 할 때, lazy하게 load할 파일이 부모 혹은 자식에서 먼저 닫혀 버리는 경우를 주의해야 한다. 따라서 동일한 파일을 file_duplicate과 같은 함수를 이용해 한번 더 열어 주는 것이 안전하다. (특히 ELF 실행 파일의 경우)

static void spt_copy_page(struct hash_elem *e, void *aux) {
  struct supplemental_page_table *dsc_spt =
      (struct supplemental_page_table *)aux;
  struct hash *dsc_hash = &dsc_spt->hash;
  struct page *src_page = hash_entry(e, struct page, elem);

  /* Copy spt entries. */
  struct page *dsc_page = calloc(1, sizeof(struct page));
  memcpy(dsc_page, src_page, sizeof(struct page));

  /* Deconnect from parent's hash table. */
  memset(&dsc_page->elem, 0, sizeof(struct hash_elem));
  hash_insert(dsc_hash, &dsc_page->elem);

  if (!pg_present(src_page)) {
    /* If uninitialized segement page, copy file info. */
    struct file_info *dsc_aux;
    struct file_info *src_aux = (struct file_info *)src_page->uninit.aux;

    dsc_aux = calloc(1, sizeof(struct file_info));
    memcpy(dsc_aux, src_aux, sizeof(struct file_info));
    dsc_page->uninit.aux = dsc_aux;

  } else {
    /* Claim page if present. */
    struct frame *dsc_frame = vm_get_frame();
    ASSERT(src_page->frame->kva)
    ASSERT(dsc_page->frame->kva)

    dsc_page->frame = dsc_frame;
    dsc_frame->page = dsc_page;
    memcpy(dsc_page->frame->kva, src_page->frame->kva, PGSIZE);

    install_page(dsc_page);
  }
}

03) Stack Growth

스택의 크기는 초기에 4KB로 세팅된다. 스택은 setup_stack 함수가 리턴되기 전에 실제 물리 메모리를 할당받도록 구현하는데, 이는 실행파일 load과정에서 setup_stack이 호출된 직후 실행파일의 인자를 스택에 쌓아주기 때문이다. 만약 즉시 1개 페이지를 할당받지 않는다면 인자를 쌓는 과정에서 폴트가 발생하고, 그 때 스택이 만들어질수도 있(긴 있)다. 하지만 lazy loading이 실제로 접근이 언제 이루어질 지 모르기 때문에 접근 후에 메모리를 할당해주는 전략 이라는 점에서, 접근이 이루어질 것임을 아는 메모리에 대해서는 즉시 할당해 주는 것이 합리적일 수 있다.

만약 스택의 공간이 부족하다면 스택을 최대 1MB까지 늘려 주어야 한다. 이를 vm_try_handle_fault에서 어떻게 구현할 수 있을까? 이 경우 fault가 발생한 address는 spt에 없을 것이라는 사실을 짐작할 수 있다.

bool vm_try_handle_fault(struct intr_frame *f, void *addr, bool user,
                         bool write, bool not_present) {

  struct supplemental_page_table *spt = &thread_current()->spt;
  void *upage = pg_round_down(addr);
  void *curr_rsp = (void *)f->rsp;

  /* Validate stack overflow. */
  if (STACK_LIMIT < addr && addr < spt->stack_bottom) {
    /* If current stack is not full, not a stack overflow. */
    if (curr_rsp != addr) return false;
    /* If stack overflow */
    return vm_stack_growth(upage);
  }

• if(STACK_LIMIT < addr && addr < spt->stack_bottom && curr_rsp == addr)

이를 통해 스택을 늘리려는 시도임을 체크할 수 있다. 스택을 확장하려고 하면, rsp값이 스택 영역의 밖으로 감소한 다음, 해당 rsp가 참조하는 주소에 접근할 것이다. 따라서 fault가 발생한 주소와 rsp값과 같다면, 유효한 스택 확장 시도로 볼 수 있을 것이다. (그 전에 STACK_LIMIT과 spt->stack_bottom을 기준으로 stack address임을 체크하고, rsp와 비교하여 스택 확장 시도의 유효성을 검증한다.)

/* Growing the stack. */
static bool vm_stack_growth(void *addr) {
  /* If addr exceeds STACK_LIMIT, return false. */
  if (addr <= STACK_LIMIT) {
    return false;
  }

  struct supplemental_page_table *spt = &thread_current()->spt;
  spt->stack_bottom = addr;
  return vm_alloc_page(VM_ANON, addr, true);
}

bool vm_alloc_page_with_initializer(enum vm_type type, void *upage,
                                    bool writable, vm_initializer *init,
                                    void *aux) {
    // make page struct and insert spt
    ...
    /* If stack page, claim immediately. */
    if (upage == spt->stack_bottom) {
      if (!vm_do_claim_page(page)) goto err;
    }

vm_alloc_page_with_initializer 함수를 스택 페이지인 경우 즉시 claim하도록 짜 두었으므로 vm_stack_growth에서는 spt의 stack_bottom 값을 PGSIZE만큼 늘린 후 vm_alloc_page를 콜 하기만 하면 된다.

👀 아래와 같은 코드에서는 fault addr가 rsp와 다른 주소인 거 아냐?

int main() {
    char arr[65536]; // 64KB

    arr[0] = 4;
    return 0;
}

배열의 원소가 4KB를 초과하는 65536개 이고, 0번째 원소(가장 낮은 주소)에 접근하므로 fault address는 rsp + 65536 이 되지 않을까? 하지만 그렇지 않다.. 위와 같은 c코드를 gcc 컴파일러로 컴파일하면 아래와 같은 코드를 뱉는다.

main:
.LFB0:
    .cfi_startproc
    endbr64
    pushq    %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    leaq    -61440(%rsp), %r11
.LPSRL0:
    subq    $4096, %rsp
    orq    $0, (%rsp)        // 🔥 fault!
    cmpq    %r11, %rsp
    jne    .LPSRL0
    subq    $3976, %rsp
    movb    $4, -65536(%rbp)
    movl    $0, %eax
    leave
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc

.LFB0라벨의 마지막 라인을 보면 %rsp값에서 61440를 뺀 값을 %r11 레지스터에 저장하고 있다. 이는 배열의 크기와 비교해 더 늘려 주어야 하는 스택 사이즈를 계산하고 있는 것으로 보인다. 그리고, %r11과 현재 %rsp값을 비교하면서 $4096씩 스택 영역을 늘려주고 있다. 이 때 orq $0, (%rsp) 라인에 의해 실제적으로 페이지 폴트가 발생하는데, 이는 %rsp값에 접근해 0과의 or연산을 수행하기 때문이다. (0과의 or이므로 연산 결과는 바뀌지 않는다. 폴트를 발생시키려는 의도로 보인다.)

👀 그러면 배열을 선언하면서 스택 사이즈를 늘려주는데, 이것은 스택을 lazy하지 않게 할당하는 것 아닌가?

lazy load는 운영체제가 하는 일이고, page fault를 일으키면서 스택을 늘려주는 것은 사용자 프로그램이다. 어떻게 보면, 운영체제가 lazy load라는 방식을 택하고 있기 때문에 유저 프로그램이 page fault를 고의적으로 발생시키며 스택을 늘리도록 컴파일되는 것이다.

+) 이 부분에 대한 GPT 코멘트를 달아둔다: 컴파일러가 스택을 늘리는 코드를 생성하는 이유는 스택을 lazy하게 할당하는 운영체제와 상호 작용하기 위함입니다. Lazy loading은 운영체제에서 페이지 할당을 효율적으로 하기 위한 전략입니다. 스택 영역이 확장되면, 프로그램은 실제로 해당 영역에 접근할 때까지 메모리를 할당받지 않습니다. 이 접근은 페이지 폴트를 발생시키고, 운영체제는 그 때 페이지를 할당합니다. (...) lazy loading은 운영체제의 기능입니다. 그럼에도 불구하고, 컴파일러는 이러한 운영체제의 특성을 이용하여 스택 확장 코드를 생성합니다. 이것은 운영체제의 특성과 상호 작용하는 프로그램의 최적화 예제입니다.

👀 왜 한번에 65536만큼 rsp에서 빼지 않고 4096씩 빼도록 컴파일될까?

스택은 위에서 아래로, 힙은 아래에서 위로 확장되므로 일반적인 사용자 프로그램에서 두 영역은 충돌하지 않는다. 그러나 스택 오버플로우 공격과 같은 보안 위협에서 스택의 크기가 힙을 침범하여 과도하게 확장되면 두 메모리 공간이 충돌할 수 있다. 이러한 공격에 대비하기 위해, 스택의 끝(가장 낮은 주소)에는 Red Zone 또는 Stack Guard Page라고 불리는 경계가 존재한다. 이 페이지는 접근 금지된 구역으로, 해당 구역에 접근하게 되면 시스템은 Fault를 감지하고 프로세스를 종료시킨다. (즉, 이 페이지에 대한 접근은 곧 잘못된 메모리 접근으로 인지된다.) 그런데 만약 컴파일러가 한번에 프로그램이 요청한 만큼 스택을 확장하도록 컴파일한다면 이 Stack Guard Page를 스킵한 주소값으로 rsp가 설정될 수 있게 된다. 따라서 한 페이지 단위로, 반복적으로 rsp를 감소시키면서 금지 구역에 접근하는지를 감지할 수 있도록 컴파일된다. (-fno-stack-protector 옵션을 끄면 컴파일 결과가 달라질까? 확인해 볼 것.)

Red Zone: wikipedia
A closer look at the stack guard page

---

여기까지 다 했으면, 이제서야 1주차 2주차 코드가 물리적인 메모리를 갖고.. 실행되기 시작한다. 이제 각 프로세스는 요구 페이징이라는 훌륭한 전략을 사용해 전체 메모리를 더욱 효율적으로 사용할 수 있게 된다..