Stack Growth

In project 2, the stack was a single page starting from the USER_STACK, and programs' executions were limited to this size. Now, if the stack grows past its current size, we allocate additional pages as necessary.

기존의 스택은 USER_STACK에서 시작하는 하나의 페이지였으며, 프로그램의 실행이 스택의 크기까지로 제한되었다.

스택이 기존의 크기보다 증가하면 추가적인 페이지를 할당할 수 있다.

Allocate additional pages only if they "appear" to be stack accesses. Devise a heuristic that attempts to distinguish stack accesses from other accesses.

스택의 접근이 가능한 경우에 한해 추가적인 페이지를 할당한다.

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.

유저 프로그램은 스택 포인터가 가리키는 부분 이하의 영역에 쓰려고 하면 잦은 버그가 발생한다. x86-64 시스템은 스택 포인터를 변경하기 전에 접근 권한을 확인하기 때문에, 스택 포인터 8바이트 아래에서 페이지 폴트를 유발할 수 있다.

You will need to be able to obtain the current value of the user program's stack pointer. Within a system call or a page fault generated by a user program, you can retrieve it from the rsp member of the struct intr_frame passed to syscall_handler() or page_fault(), respectively. If you depend on page faults to detect invalid memory access, you will need to handle another case, where a page fault occurs in the kernel. Since the processor only saves the stack pointer when an exception causes a switch from user to kernel mode, reading rsp out of the struct intr_frame passed to page_fault() would yield an undefined value, not the user stack pointer. You will need to arrange another way, such as saving rsp into struct thread on the initial transition from user to kernel mode.

유저 프로그램의 스택 포인터가 가리키는 현재의 주소값을 알아야 한다. 시스템 콜이나 유저 프로그램에 의한 페이지 폴트의 경우, syscall_handler()나 page_fault()로 전달되는 intr_frame 구조체의 멤버인 rsp로부터 확인할 수 있다.

프로세서는 예외가 유저에서 커널 모드로의 전환을 발생하는 경우에만 스택 포인터를 저장하기 때문에 intr_frame 구조체에서 rsp를 page_fault()로 전달되면 정해지지 않은 값을 전달한다.

Process Address Space 공간에서 가상주소를 페이지 테이블을 통해 Physical Memory에 존재하는 물리주소를 맵핑하면 디스크로부터 데이터를 읽어들인다.

가상주소 공간에는 스택과 Unintialized 데이터, Initialized 데이터와 텍스트가 저장된다.

기존의 핀토스 운영체제 시스템은 스왑을 사용할 수 없으며 요구 페이징을 사용할 수 없다.

가상 메모리가 구현되어 있지 않기 때문에 가상 메모리 시스템을 구현한다.

요구 페이징은 저장 공간 디스크에 저장된 파일과 페이지 중 요구된 페이지들만 물리 메모리에 적재하는 방식을 의미한다.

요구 페이징은 인스트럭션이 실행되면 가상주소로부터 가상 페이지 번호를 추출하여 페이지 테이블을 참조한다.

페이지 테이블에 물리 페이지가 존재하지 않을 시 페이지 폴트가 발생한다.

페이지 폴트 발생시 페이지 프레임을 할당하고 페이지 테이블을 갱신한다.

새로 할당된 프레임에 해당되는 페이지를 디스크에서 페이지 프레임에 탑재한다.

1. 인스트럭션을 실행한다.

2. 가상주소를 물리주소로 변환한다.

3. 페이지가 존재하지 않을 경우 페이지 폴트가 발생한다.

4. 새로 할당된 프레임에 해당하는 페이지를 디스크에서 4KB만큼 읽고 물리 메모리에 적재한다.

논리주소가 필요하고 페이지의 데이터를 가지고 있는 vm_entry들을 해시 테이블로 관리한다.

vm_entry는 페이지 당 하나씩 존재하며 각 페이지의 파일 포인터, 오프셋, 크기를 저장한다.

프로그램 초기 탑재시 가상 주소공간 각 페이지에 vm_entry를 할당한다. (thread 구조체의 해시 테이블 필드 vm에 저장)

프로그램 실행시 페이지 테이블을 검색하고 페이지 폴트가 발생할 시 가상주소에 해당하는 vm_entry를 탐색한다.

vm_entry에 존재하지 않는 가상주소는 segmentation fault가 발생한다.

vm_entry가 존재할 경우 페이지 프레임을 할당하고 vm_entry에 있는 파일 포인터와 읽기 시작할 오프셋, 읽어야 할 크기 등을 참조해서 페이지를 (디스크에서 물리 메모리로) 로드하고 페이지 테이블을 갱신한다.

기존의 핀토스는 ELF 이미지 각 페이지를 물리 메모리로 읽어들인다.

load_segment()를 이용해 데이터와 코드 세그먼트를 물리 메모리로 읽어들이고 setup_stack()을 이용해 스택에 물리 페이지를 할당한다.

수정하고자 하는 핀토스의 가상주소 공간 초기화 과정은 디스크 이미지의 세그먼트를 적재하는 것이 아니라 물리 메모리를 할당하는 대신 가상 페이지마다 vm_entry를 통해 적재할 정보들을 관리한다.

프로세스가 요청한 페이지들에 대해서만 물리 페이지를 할당해주는 기법인 요구 페이징을 구현한다.

현재 핀토스는 프로그램의 모든 세그먼트에 대해 물리 페이지를 할당한다.

요구 페이징을 위해 요청한 페이지에 대해서만 물리 페이지 할당을 수행한다.

페이지 폴트가 발생할 시 해당 vm_entry의 존재 유무를 확인하고, vm_entry의 가상주소에 해당하는 물리 페이지를 할당하고 vm_entry의 정보를 참조하여 디스크에 저장되어 있는 실제 데이터를 로드한다.

thread 구조체에 vm_entry를 관리하는 해시 테이블 vm를 생성한다.

해시 테이블 vm은 buckets란 필드를 포함하고 각 bucket에 vm_entry를 저장한다.

vm_entry는 페이지 테이블을 가리키고 스택은 물리 메모리를? (보류)

vm_entry는 가상 메모리의 가상주소에 접근하여 페이지 테이블을 참조한다.

페이지 테이블에 물리 프레임이 맵핑되어 있지 않으면 페이지 폴트가 발생한다.

파일의 포인터, 읽기 시작할 오프셋, 읽어야 할 데이터의 크기가 필요하다.

물리 메모리에 물리 프레임을 할당하고 저장공간으로부터 요구된 페이지와 파일 내용을 물리 메모리에 적재한다.

페이지 테이블은 가상 페이지와 물리 프레임을 맵핑한다.

가상주소는 페이지 테이블 인덱스와 페이지 오프셋으로 구성된다.

페이지 오프셋은 해당 페이지 또는 프레임의 첫 주소를 0으로 봤을 때의 주소를 의미한다.

물리주소는 프레임 번호와 오프셋으로 구성된다.

물리주소의 오프셋은 가상주소의 오프셋과 동일하며 프레임 번호는 페이지 테이블의 프레임 넘버?

페이지 테이블의 구조는 2단계 페이지 테이블의 구조로 이루어져 있으며,

thread 구조체의 멤버인 pagedir(pml4)는 페이지 디렉토리의 시작하는 주소를 가리키며,

해당 페이지 디렉토리의 인덱스를 통해 페이지 테이블을 가리킨다.

vm_entry의 type 필드는 가상주소의 타입을 저장하며 vm_entry은 세 가지 타입으로 분류될 수 있다.

VM_BIN은 바이너리 파일로부터 데이터를 로드하고, VM_FILE은 맵핑된 파일로부터 데이터를 로드하고, VM_ANON은 스왑 영역으로부터 데이터를 로드한다.

vm_entry 구조체는 분류되는 타입인 type을 멤버로 가진다.

*vaddr은 vm_entry가 관리하는 가상 페이지의 번호를 나타낸다.

writable은 True일 경우 해당 주소에 읽기와 쓰기가 가능하다는 것을 의미한다.

is_loaded는 물리 메모리의 탑재 여부를 알려주는 플래그이다.

file 구조체는 가상주소와 맵핑된 파일을 나타낸다.

mmap_elem 구조체는 mmap_list의 구성요소이다.

offset은 읽어야 할 파일의 오프셋을 나타낸다.

read_bytes는 가상 페이지에 쓰여져 있는 데이터의 크기이다.

zero_bytes는 0으로 채울 남은 페이지의 바이트를 의미한다. (보류)

hash_elem 구조체의 elem은 해시 테이블의 구성요소이다.

페이지 폴트가 일어날 때마다 가상주소에 해당하는 vm_entry를 탐색해야 한다.

따라서 해당 가상주소의 가상 페이지를 표현하는 vm_entry가 필요하다.

물리 메모리에 접근할 때 해당 주소의 가상 페이지를 표현하는 vm_entry를 탐색한다.

vm_entry들은 빠르게 탐색할 수 있는 자료구조인 해시 테이블의 형태로 관리한다. (vaddr 키를 이용해 해시 값을 추출한다.)

체이닝 해시 테이블 (보류)

thread 구조체에 해시 테이블 자료구조를 추가한다. (vm)

프로세스 생성시 해시 테이블을 초기화하고 vm_entry들을 해시 테이블에 추가한다.

프로세스를 실행하는 도중 페이지 폴트가 발생할 시 vm_entry를 해시 테이블에서 탐색한다.

프로세스 종료시 해시 테이블의 buckets 리스트와 vm_entry를 제거한다.

프로세스마다 가상주소 공간이 할당되므로 가상 페이지들을 관리할 수 있는 자료구조인 해시 테이블을 정의한다.

find_vme(): 인자로 입력 받은 vaddr에 해당하는 vm_entry를 검색한 후 반환한다. vm_entry 가상 메모리 주소에 해당하는 페이지 번호를 추출하고 hash_find()를 사용하여 vm_entry를 검색한 후 반환한다.

pg_round_down()? (보류)

vm_destroy(): hash_destroy()를 사용하여 해시 테이블의 버킷 리스트와 vm_entry를 제거 (프로세스 종료시 사용할 것 같다. -> process_exit()에 추가)

가상 주소공간 초기화

기존의 핀토스는 물리 페이지를 할당하고 파일의 내용을 4KB 읽어서 물리 메모리에 적재한다.

페이지 테이블의 가상주소와 물리주소를 맵핑한다.

가상 주소공간 초기화 하는 이유? (보류)

주소공간 초기화 관련 함수 (ELF 세그먼트)

load_segment() 함수는 ELF 포맷 파일의 세그먼트를 프로세스 가상 주소공간에 탑재하는 함수이다.

load_segment() 함수에 프로세스 가상 메모리 관련 자료구조를 초기화하는 기능을 추가한다.

vm_entry 구조체의 할당, 필드값 초기화, 해시 테이블 삽입을 추가한다.

기존의 load_segment() 함수에서 물리 페이지를 할당하고 데이터를 파일에서 페이지로 로드하고 페이지 테이블을 설정하는 부분을 삭제하고 vm_entry을 생성하고 vm_entry를 해시 테이블에 삽입하도록 수정한다.

왜 4KB인지?

기존의 setup_stack() 함수는 단일 페이지를 할당하고 페이지 테이블을 설정하고 스택 포인터를 설정한다.

스택 포인터의 역할?

4KB 스택의 vm_entry를 생성하고 vm_entry 필드값을 초기화하고 vm 해시 테이블에 삽입한다.

가상주소 유효성 검사

주소 유효성 검사란 가상주소에 해당하는 vm_entry가 존재하는지 검사하는 것이다.

시스템 콜(read/write)을 사용할 시 인자로 주어지는 문자열이나 버퍼의 주소에 해당하는 vm_entry가 존재하는지 검사한다.

read() 시스템 콜의 경우 버퍼의 시작주소에 해당하는 vm_entry의 존재여부를 검사한다.

write() 시스템 콜의 경우 문자열의 시작주소에 해당하는 vm_entry의 존재여부를 검사한다.

기존의 check_address() 함수는 esp에 대한 유저 메모리 영역을 체크한다.

vm_entry를 사용하여 유효성 검사 작업을 수행하도록 수정한다.

vm_entry를 반환하도록 수정한다.

check_valid_buffer() 함수는 버퍼를 사용하는 read() 시스템 콜의 버퍼의 주소가 유효한 가상주소인지 검사한다.

버퍼의 역할과 위치?

버퍼의 유효성을 검사하는 함수이다.

to_write() 변수는 버퍼의 내용에 쓸 수 있는지를 검사하는 변수이다.

check_valid_buffer()는 시스템 콜 핸들러의 SYS_READ()에 추가한다.

check_valid_string() 함수는 write() 시스템 콜에서 사용할 문자열의 주소값이 유효한 가상주소인지 검사하는 함수이다.

시스템 콜 핸들러의 SYS_EXEC에 check_valid_buffer() 함수를 추가한다.

시스템 콜 호출 시 인자의 유효성을 검사하도록 수정한다.

기존 check_addres()의 두 번째 인자를 f에서 esp로 변경한다. (변경하는 이유?)

요구 페이징 구현

thread 구조체의 vm_entry를 관리하는 해시 테이블 vm의 buckets에 vm_entry들을 저장한다.

vm_entry에서 페이지 테이블을 참조하는 과정에서

1. 메모리 접근 및 페이지 폴트 page_fault()

2. vm_entry를 확인 find_vme()

3. 물리 메모리 할당 handle_mm_fault()

4. 디스크에서 메모리로 데이터를 로드 load_file()

5. 페이지 테이블 설정 install_page()

1. 페이지 폴트 처리

핀토스는 페이지 폴트 발생시 처리를 위해 page_fault() 함수가 존재한다.

기존의 page_fault()는 page_fault 처리는 permission, 주소 유효성 검사 후 오류 발생시 segmentation fault를 발생시키고 kill(-1)하여 프로세스는 종료시킨다.

fault_addr의 유효성을 검사하고 페이지 폴트 핸들러 함수(handle_mm_fault())를 호출하도록 수정한다.

페이지 폴트 발생시 page_fault() 호출

폴트가 발생한 물리주소가 유효한지 확인하여 유효한 경우 vm_entry를 검색한다.

handle_mm_fault()를 호출하여 페이지를 할당하고 데이터를 로드하고 페이지 테이블을 갱신한다.

2. 페이지 폴트 핸들러 구현

handle_mm_fault() 함수를 수정한다.

페이지 폴트 발생시 물리 페이지를 할당하고 디스크에 있는 파일을 물리 페이지로 load한다. (load_file() 함수 사용)

물리 메모리에 적재가 완료되면 가상주소와 물리주소를 페이지 테이블로 맵핑한다. (install_page() 함수 사용)

3. 물리 메모리에 파일 쓰기

물리 메모리 할당 완료 후 실제 디스크의 파일을 물리 페이지로 load한다.

load_file() 디스크에 존재하는 페이지를 물리 메모리로 로드하는 함수이다.

vm_entry의 파일 오프셋으로 한 페이지를 kaddr로 읽어 들이는 함수를 구현한다.

4KB를 전부 write하지 못했다면 나머지를 0으로 채운다.

vm_entry의 vaddr를 통해 페이지 테이블을 참조하고 물리 메모리에 디스크로부터 오프셋에 위치하는? 파일을 적재한다.

install_page()는 페이지 주소 맵핑 함수로 페이지 테이블에 물리주소와 가상주소를 맵핑시킨다.

인자로 입력된 물리 페이지 kpage와 가상 페이지 upage를 맵핑한다.

왜 물리 페이지가 kpage이고 가상 페이지가 upage인지?

페이지 테이블과 페이지 디렉토리를 이용해서 물리주소와 가상주소의 맵핑을 관리하는 구조이다.

페이지 디렉토리는 페이지 테이블의 주소를 갖고 있는 테이블로 가상 페이지에 대한 엔트리 사용을 효율적으로 관리하기 위해 카테고리를 사용한다.

페이지 테이블은 가상주소에 맵핑된 물리주소를 갖고 있는 엔트리들의 집합이다.

palloc_get_page()는 4KB의 페이지를 할당하고 페이지의 물리주소를 리턴한다.

인자 flags는 PAL_USER, PAL_KERNEL, PAL_ZERO가 존재한다.

PAL_USER: 유저 메모리 풀에서 페이지를 할당한다.

PAL_KERNEL: 커널 메모리 풀에서 페이지를 할당한다.

PAL_ZERO: 페이지를 '0'으로 초기화한다.

palloc_free_page(): 페이지의 물리주소를 인자로 입력하고 페이지를 다시 여유 메모리 풀에 넣는다. (보류)