[PintOS] Project 2: User Programs 큰 그림 그리기

Project 2: User Programs💡Git book Introduction

Background & Our goal

PintOS Project 1에서 실행했던 Alarm clock, Scheduling 등 모든 코드는 OS 커널의 한 부분이었다. 구현했던 코드들은 커널의 일부로서 시스템에 중요한 부분에 접근할 수 있는 특권을 가지고 실행되었던 것이다. 테스트 코드 또한 직접 컴파일 했었다.

 

이제 Project 2에서는 유저 프로그램을 실행할 부분을 작업할 시간이다. 해당 PintOS 코드에서 유저 프로그램을 로드하고 실행하는데 필요한 기본 코드들은 이미 있지만, 이 코드로는 I/O나 상호작용이 가능하지 않다. 즉, 프로그램이 시스템 콜을 통해서 OS와 상호작용할 수 있도록 만들어야한다. OS 위에서 작동하는 유저 프로그램을 실행하면 시스템에 중요한 부분을 접근할 수 있는 "특권"은 없을 것이다. 

 

즉, 앞으로 구현해야할 시스템 콜(system call)은 운영체제의 커널이 제공하는 서비스에 대해 유저 프로그램의 요청에 따라 커널에 접근하기 위한 인터페이스이다. 왜냐, 유저 프로그램은 접근할 특권이 없으니까..!

* User mode VS Kernel mode

요약)

- 커널 모드(Kernel Mode): Privileged mode

- 유저 모드(User Mode): Unprivileged mode

커널 모드는 모든 자원에 접근할 수 있지만 유저 모드에서는 자원 접근이 한정적이다. 굳이 커널 모드와 유저 모드로 나눈 이유는 운영체제를 프로세스로부터 보호하여 추상화를 하기 위함이다. 

여러 프로세스가 모두 자원을 사용할 권한이 있다면 관리가 되지 않을 것이다. 따라서 유저모드에서 자원을 할당받아야 하면 운영체제에 시스템 콜을 보내 커널 모드에 진입하여 자원을 할당 받고 사용하며 사용을 마치면 권한을 반납한다. 이러한 모드 변경을 Context Switching이라고 한다. 시스템 콜에 대한 실행 코드는 운영체제가 미리 갖고 있다. 우리는 이번 프로젝트에서 시스템 콜에 대한 실행 코드를 직접 구현한다.

 

PintOS에서는 각각의 프로세스들은 하나의 쓰레드를 가진다. 멀티 쓰레드 프로세스를 지원하지 않는다. 그렇기 때문에 유저 프로그램들은 자신들이 컴퓨터 전체를 소유한다는 환상 하에 쓰여진다. This means that when you load and run multiple processes at a time, you must manage memory, scheduling, and other state correctly to maintain this illusion. 

 

Project 1에서는 테스트 코드를 커널에 바로 컴파일 했기에, 커널 안에서 상호작용하는 특정 함수들을 필요로 했었다. 이번 프로젝트에서는 유저 프로그램을 실행함으로써 운영체제를 "테스트"할 것이다. 주의할 점은 코드들을 절대로 #ifdef VM으로 감싸진 코드 블록 내에 위치하면 안 된다. 이 코드 블록은 프로젝트 3에서 구현할 부분으로 가상 메모리 하위 시스템을 활성화한 후 포함한다.

 

Source Files

process.c, process.h

: ELF 바이너리들을 로드하고 프로세스를 실행한다.(Loads ELF binaries and starts processes.)

ELF(Executable and Linkable Format)이란?

: 실행 파일, 목적 파일, 공유 라이브러리 그리고 코어 덤프를 위한 표준 파일 형식이다. ELF는 linux, solarix, 그리고 많은 운영체제에서 목적 파일, 공유 라이브러리, 그리고 실행 파일들을 위해 사용되는 파일 포맷이다.

 

ELF file이란?

: ELF는 리눅스 시스템에서 사용되는 중요 실행 파일 형식이다. 사용자 어플리케이션, 공유 라이브러리, 커널 모듈, 커널 자체 모두 ELF 형식으로 저장된다.

 

Reference) https://ko.wikipedia.org/wiki/ELF_%ED%8C%8C%EC%9D%BC_%ED%98%95%EC%8B%9D

 

syscall.c, syscall.h

: 유저 프로세스가 일부 커널 기능에 접근하려고 할 때마다 시스템 콜이 호출된다. 이게 시스템 콜 핸들러의 기본 구조이다.

현재 상태에서는 이 때 단지 message를 출력하고 유저 프로세스를 종료시키게 되어있다.

이번 프로젝트의 part2에서 시스템 콜이 필요로 하는 다른 일을 수행하는 코드를 수행하게 될 것이다. 

 

exception.c, exception.h

: 유저 프로세스가 특별한 접근 권한을 필요로 하거나 금지된 연산을 수행할 경우 exception 혹은 fault로 들어간다. 

exception.c, exception.h 파일들은 예외사항을 처리한다.

현재 상태에서는 단지 message를 호출하고 process를 종료시키게 되어있다.

프로젝트에 대한 일부 해결책은 이 파일 내에 있는 page_fault()를 수정하는 것이다.

 

* 응용 프로그램이 시스템 콜을 호출하면 하드웨어는 '트랩 핸들러'를 실행하여 하드웨어 특권 수준을 커널 모드로 격상시킴. 커널 모드에서 운영체제는 시스템 하드웨어를 자유롭게 접근할 수 있음 

 

tss.c, tss.h

Task-State Segement(TSS)는 x86 아키텍쳐의 문맥교환에 사용된다. 하지만 x86-64에서 문맥 교환(Context Switching = Task Switching)은 지원이 중단된 기능이다. 그래도 TSS는 여전히 ring switching 동안 스택 포인터를 찾아내기 위해 사용되고 있다. 이는 유저 프로세스가 인터럽트 핸들러에 진입할 때, 하드웨어는 TSS에게 커널의 스택 포인터를 찾아달라고 요청한다는 의미이다.

 

Using the File System

이번 프로젝트에서는 파일 시스템 코드와 인터페이스해야한다. 왜냐하면 유저 프로그램은 파일 시스템으로부터 로드되고, 구현해야할 시스템 콜들은 파일 시스템을 다루기 때문이다.

 

There is no need to modify the file system code for this project. 

"이번 프로젝트에서 이 파일 시스템 코드를 수정할 필요도 없고, 수정하지 않기를 권합니다. 파일 시스템에 정신을 뺏기지 마시고 이번 프로젝트의 중점 과제에 집중하세요"

 

Proper use of the file system routines now will make life much easier for project 4.

그러나 그때까지는 다음 제한 사항을 허용해야 한다.

• 내부 동기화를 하지마세요. 동시 접근은 서로를 방해할 것. 동기화(synchronization)를 사용하여 한 번에 하나의 프로세스만 파일 시스템 코드를 실행하도록 해야한다. 
• 파일 사이즈는 파일이 생성될 때 고정된다. 루트 디렉토리가 파일이기 때문에 생성될 수 있는 파일의 갯수들도 제한되게 된다.
• 파일의 데이터는 single extent로 할당된다. 즉, 한 파일의 데이터는 디스크 섹터를 연속적으로 차지해야 한다. 그래서 파일 시스템이 사용되고 시간이 흐르면서 외부 단편화가 큰 문제가 될 수 있다.
• 하위 디렉토리들을 만들지 마세요.
• 파일의 이름은 14자로 제한한다.
• 연산 중에 (디스크에 읽고 쓰는 중에) 시스템 crash가 발생하면 자동으로 복구되지 못하는 방식으로 디스크를 망쳐버릴 수도 있다. 파일 시스템 복구 툴 같은 것은 없다.

 

How User Programs Work

이 프로젝트에서 쓰이는 어떤 시스템 콜도 메모리 할당을 허락하지 않기 때문에 malloc()은 사용할 수 없다. 

또한 부동소수점 연산(floating point operations)을 사용하는 프로그램을 실행시킬 수 없다. 왜냐하면 커널은 문맥 교환이 일어날 때 프로세서의 부동 소수점을 저장하고 복구하지 않기 때문이다. 

 

핀토스는 userporg/process.c에 제공된 로더로 ELF 실행 파일을 로드할 수 있다.

실제로 당신은 x86-64 ELF 실행 파일들을 만들어내는 임의의 컴파일러와 링커를 사용해서 핀토스를 위한 프로그램을 만들 수있다. 테스트 프로그램은 simulated 파일 시스템에 복사할 때까지 핀토스가 유용한 작업을 할 수 없다는 것을 즉시 깨달아야한다.

 

다양한 프로그램들을 파일 시스템에 복사하기 전까지는 아무런 흥미로운 작업을 할 수 없다. 간혹 디버깅을 하다보면 filesys.dsk가 사용불가능한 상태가 되는 경우가 발생할텐데, 그럴 때마다 복사해서 덮어쓸 수 있는 클린한 레퍼런스 파일 시스템 디스크를 만들어놓으면 좋을 것이다.

 

Virtual Memory Layout

핀토스의 가상 메모리는 2개의 영역으로 나눌 수 있다.

1) User Virtual Memory; 유저 가상 메모리 (0 ~ KERN_BASE)

유저 가상 메모리는 가상 주소 0부터 KERN_BASE까지의 범위를 가진다. KERN_BASE는 include/threads/vaddr.h에 정의되어 있고 기본적으로 0x8004000000이다. 커널 가상 메모리는 가상 주소 공간의 나머리를 차지한다.

 

하나의 프로세스는 하나의 유저 가상 메모리를 가진다. 프로세스 문맥 교환이 일어날 때, 커널은 프로세서의 'page directory base register(see pml4_activate() in thread/mmu.c)'를 바꿈으로써 유저 가상 주소 공간 또한 바꿔준다. 스레드 구조체는 하나의 프로세스의 페이지 테이블을 가리키는 포인터를 가지고 있다.

 

2) Kernel Virtual Memory; 커널 가상 메모리

커널 가상 메모리는 전역적이다. 커널 가상 메모리는 어떤 유저 프로세스 또는 커널 스레드가 CPU 제어권을 획득해 RUNNING인지에 관계없이 항상 같은 방식으로 매핑된다. 핀토스에서 커널 가상 메모리(kernel virtual memory)는 물리 메모리(physical memory)와 일대일 매핑이 된다. (KERN_BASE에서 시작)

다시 말해, 가상 주소인 KERN_BASE는 물리 주소 0에 매핑되고, 가상주소 KERN_BASE + 0x1234는 물리 주소 0x1234에 대응된다.

 

user program은 자신의 user virtual memory에만 접근이 가능하다. kernel의 virtual memory에 접근하면 page fault를 일으킨다.(page_fault() 함수에 의해 in userprog/exception.c) 그리고 process는 종료된다.

 

kernel thread는 kernel virtual memory에 접근가능하고, 만약 process가 running 상태라면 user virtual memory에도 접근가능하다. 그러나 unmapped user virtual address에 접근하면 page fault가 일어난다.

 

Q. 유저 가상 메모리 범위가 0 ~ KERN_BASE이고 커널의 가상 메모리 범위가 KERN_BASE ~ 나머지 공간이라고 되어 있는데 그렇다면 KERN_BASE부터는 커널의 가상 메모리 공간인데 KERN_BASE에서 physical memory와 1대1 맵핑된다는 의미가 무엇인가요?

 

A. kernel 역시 process와 흡사하게 protected mode에서 동작하여, page table을 통한 virtual address transition을 통해 memory에 접근해야합니다. 따라서 직접적인 read/write를 위해, 또는 process에게 memory를 할당하기 위해 physical memory를 mapping하는데, 이를 kernel virtual address라고 칭하는 것입니다. 아래 그림을 보시면 user process mapping과 kernel mapping이 어떻게 이뤄지는지 살펴보실 수 있습니다. 

해당 루틴은 threads/init.c의 paging_init 함수에서 구현되어 있으며, 이는 kernel main 함수에서 호출된다. (https://github.com/casys-kaist/pintos-kaist/blob/ee7443d7ae850c7cb704db6e8213c5cb67cacd0b/threads/init.c#L147)

 

Typical Memory Layout

개념적으로 각각의 프로세스는 자유롭게 자신의 가상 메모리를 배치할 수 있다.

User Virtual Memory(유저 가상 메모리)는 아래와 같은 레이아웃을 가진다.

프로젝트 2에서, 유저 스택의 크기는 고정되어 있지만, 프로젝트 3에서는 유저 스택의 크기는 가변적이게 된다. 

핀토스에서 코드 세그먼트는 가상 메모리 0x400000에서 시작하고, 대략 주소 공간의 바닥에서 128MB만큼 떨어져 있다. 

한 실행파일의 레이아웃을 보기 위해서는 -p 옵션과 함게 objdump 명령어를 실행시켜보면 된다.

USER_STACK +----------------------------------+
           |             user stack           |
           |                 |                |
           |                 |                |
           |                 V                |
           |           grows downward         |
           |                                  |
           |                                  |
           |                                  |
           |                                  |
           |           grows upward           |
           |                 ^                |
           |                 |                |
           |                 |                |
           +----------------------------------+
           | uninitialized data segment (BSS) |
           +----------------------------------+
           |     initialized data segment     |
           +----------------------------------+
           |            code segment          |
 0x400000  +----------------------------------+
           |                                  |
           |                                  |
           |                                  |
           |                                  |
           |                                  |
       0   +----------------------------------+

 

Accessing User Memory

System call의 일부로서, 커널은 유저 프로그램이 제공한 포인터들을 통해서 메모리에 자주 접근해야한다.

이 때 매우 주의해야 하는데, 왜냐하면 user는 NULL pointer, unmapped virtual memory에 대한 pointer, kernel virtual address space에 대한 pointer(above KERN_BASE)를 kernel에게 전달할 수 있기 때문이다. 이러한 모든 유형의 유효하지 않은 포인터는 문제가 되는 프로세스를 종료하고 해당 리소스를 해제하여 커널이나 실행 중인 다른 프로세스에 해를 끼치지 않고 거부되어야 한다.

 

유저가 전달한 잘못된 포인터에 문제 없이 잘 대응하기 위해서 2개의 방법이 있다. 

1. 유저가 전달한 포인터(user-provided pointer)에 문제가 없는지 검사한 후에 역참조(dereference)하는 것이다.

* 역참조: 주소값을 통해 값에 접근

이 방법을 선택한다면, thread/mmu.c와 include/threads/vaddr.h에 있는 함수들을 살펴보라.

이 방법이 유저 메모리 접근을 가장 쉽게 처리할 수 있는 방법이다. 

 

2.  KERN_BASE 아래의 pointer들인지 확인한 후, 역참조한다.

유효하지 않은 user pointer는 page fault를 일으킨다. 이 코드는 userprog/exceptions.c 파일에 있는 page_fault() 함수를 수정함으로써 페이지 폴트를 다룰 수 있다. 이 기술은 일반적으로 프로세서의 MMU(Memory Management Unit)을 이용하기 때문에 더 빠르며, 따라서 리눅스를 포함한 실제 커널에서도 많이 사용된다. 

 

두 경우 모두, 자원을 leak 하지 않도록 주의해야한다.(누수가 발생하지 않도록)

system call이 lock을 요청했거나, malloc() 함수를 통해 메모리 할당받았다고 가정해보자.

만약 올바르지 못한 유저 포인터를 맞닥뜨리게 된다 해도, 여전히 lock을 풀 수 있어야 하고 메모리 페이지는 free 되어야 한다.  

왜냐하면 memory 접근에서 error code를 반환하는 방법이 없기 때문이다. 따라서, 두 번재 방법을 시도하려는 사람에 유용한 코드를 제공한다.

/* Reads a byte at user virtual address UADDR.
 * UADDR must be below KERN_BASE.
 * Returns the byte value if successful, -1 if a segfault
 * occurred. */
static int64_t
get_user (const uint8_t *uaddr) {
    int64_t result;
    __asm __volatile (
    "movabsq $done_get, %0\n"
    "movzbq %1, %0\n"
    "done_get:\n"
    : "=&a" (result) : "m" (*uaddr));
    return result;
}

/* Writes BYTE to user address UDST.
 * UDST must be below KERN_BASE.
 * Returns true if successful, false if a segfault occurred. */
static bool
put_user (uint8_t *udst, uint8_t byte) {
    int64_t error_code;
    __asm __volatile (
    "movabsq $done_put, %0\n"
    "movb %b2, %1\n"
    "done_put:\n"
    : "=&a" (error_code), "=m" (*udst) : "q" (byte));
    return error_code != -1;
}

 이 함수들 각각은 유저 주소가 KERN_BASE 아래에 존재한다는게 검증되었다고 가정한다. 또한 이 함수들은 page_fault()를 수정해서 kernel 안에 있는 page fault는 rax를 -1로 설정하고 이전값을 %rip에 복사하도록 했다는 것을 가정한다.

 

---

어쩌다보니 큰 그림이 아니라 세부적으로 들어가게되었다..

Project 2에서 고려해야할 부분 => Project 2부터는 user program이 등장하는데, breakpoint는 user program의 코드(tests/userprog/args.c 등.)가 아닌, kernel 코드(process.c 등.)에만 걸 수 있다는 점에 유의

 

Thanks to class B translators ..~