[WEEK 09] PintOS - Project 2: User Programs (Introduction)

신호정 벨로그·2021년 10월 4일
pintos
0

Today I Learned

목록 보기
46/89

Background

Up to now, all of the code you have run under Pintos has been part of the operating system kernel. This means, for example, that all the test code from the last assignment ran as part of the kernel, with full access to privileged parts of the system. Once we start running user programs on top of the operating system, this is no longer true. This project deals with the consequences.

이전까지 핀토스에서 실행된 모든 코드는 operating system kernel의 일부였다. 다시 말해 이전 과제에서 실행된 모든 테스트 코드는 시스템으로부터 특별한 권한을 부여 받아 커널의 일부로 실행되었다. 그러나 유저 프로그램에서는 이전과 다르다.

We allow more than one process to run at a time. Each process has one thread (multithreaded processes are not supported). User programs are written under the illusion that they have the entire machine. 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.

사용자는 한 프로세스 이상을 동시에 실행하도록 한다. 각 프로세스는 한 개의 쓰레드를 가진다. 유저 프로그램은 모든 머신을 공유한다는 가정 하에 작성되었다. 즉 사용자가 여러 개의 프로세스를 load하고 실행하려 하면 사용자는 메모리, 스케줄링을 포함한 다른 부분들을 관리해야 한다.

In the previous project, we compiled our test code directly into your kernel, so we had to require certain specific function interfaces within the kernel. From now on, we will test your operating system by running user programs. This gives you much greater freedom. You must make sure that the user program interface meets the specifications described here, but given that constraint you are free to restructure or rewrite kernel code however you wish. All of your codes should never located in block that enclosed by #ifdef VM. This blocks will be included after enabling the virtual memory subsystem, which you will implement in the project 3. Also, if the codes is enclosed by #ifndef VM, those codes will be omitted from project 3.

Using the File System

To put a file into the Pintos virtual machine, firstly you need to be able to create a simulated disk with a file system partition. The pintos-mkdisk program provides this functionality. From the userprog/build directory, execute pintos-mkdisk filesys.dsk 2. This command creates a simulated disk named filesys.dsk that contains a 2 MB Pintos file system partition. Then, specify the disk by passing --fs-disk filesys.dsk after pintos but before -- (i.e. pintos --fs-disk filesys.disk -- KERNEL_COMMANDS...). The -- is needed because --fs-disk is for the pintos script, not for the simulated kernel. Afterward, format the file system partition by passing -f -q on the kernel's command line: pintos SCRIPT_COMMANDS -- -f -q. The -f option causes the file system to be formatted, and -q causes Pintos to exit as soon as the format is done.

핀토스 가상 머신에 파일을 추가하기 위해선 파일 시스템으로 분리된 simulated disk를 먼저 생성해야 한다. 핀토스 mkdisk 프로그램은 이러한 기능을 제공한다.

Virtual Memory Layout

Virtual memory in Pintos is divided into two regions: user virtual memory and kernel virtual memory. User virtual memory ranges from virtual address 0 up to KERN_BASE, which is defined in include/threads/vaddr.h and defaults to 0x8004000000 Kernel virtual memory occupies the rest of the virtual address space.

핀토스에서의 가상 메모리는 유저 가상 메모리와 커널 가상 메모리 두 영역으로 구성되어 있다. 유저 가상 메모리는 가상 주소 0부터 include/threads/vaddr.h에서 정의된 KERN_BASE까지 위치하며 커널 가상 메모리는 나머지 가상 주소 공간을 차지한다.

User virtual memory is per-process. When the kernel switches from one process to another, it also switches user virtual address spaces by changing the processor's page directory base register (see pml4_activate() in thread/mmu.c). struct thread contains a pointer to a process's page table.

유저 가상 메모리는 프로세스 단위로 구성되어 있다. 커널이 한 프로세스에서 다른 프로세스로 전환되면, 유저 가상 주소 또한 프로세서의 페이지 디렉토리 베이스 레지스터로 전환한다. thread 구조체는 프로세스의 페이지 테이블을 가리키는 포인터를 포함한다.

Kernel virtual memory is global. It is always mapped the same way, regardless of what user process or kernel thread is running. In Pintos, kernel virtual memory is mapped one-to-one to physical memory, starting at KERN_BASE. 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.

커널 가상 메모리는 전역 메모리이다. 커널 가상 메모리는 유저 프로세스 또는 커널 쓰레드가 실행중인것과 상관없이 항상 같은 방식으로 매핑된다. 핀토스에서 커널 가상 메모리는 KERN_BASE에서 시작하여 실제 메모리 공간과 일대일 대응으로 매핑된다.가상 주소 KERN_BASE는 실제 메모리 주소 0에 접근한다. 가상 주소 KERN_BASE + 0x1234에서 실제 주소 0x1234까지 접근한다. 그 이후로는 머신의 실제 메모리 공간의 크기에 따라 달라진다.

A user program can only access its own user virtual memory. An attempt to access kernel virtual memory causes a page fault, handled by page_fault() in userprog/exception.c, and the process will be terminated. Kernel threads can access both kernel virtual memory and, if a user process is running, the user virtual memory of the running process. However, even in the kernel, an attempt to access memory at an unmapped user virtual address will cause a page fault.

유저 프로그램은 해당 프로그램의 유저 가상 메모리 공간에만 접근이 가능하다. 커널 가상 메모리에 접근을 시도하면 userprog/exception.c 파일에서 다루는 page fault라는 문제가 발생하며 프로세스가 종료될 것이다. 커널 쓰레드는 커널 가상 메모리 공간에 접근 가능하며, 유저 프로세스가 실행 중이면 실행 중인 프로세스의 유저 가상 공간에도 접근이 가능하다. 하지만 커널에서는 매핑되지 않은 유저 가상 공간에 접근을 시도하면 유저 가상 공간은 페이지 폴트를 유발한다.

Typical Memory Layout

Conceptually, each process is free to lay out its own user virtual memory however it chooses. In practice, user virtual memory is laid out like this:

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

In this project, the user stack is fixed in size, but in project 3 it will be allowed to grow. Traditionally, the size of the uninitialized data segment can be adjusted with a system call, but you will not have to implement this.

프로젝트 2에서는 고정된 크기의 유저 스택을 가진다. 하지만 프로젝트 3에서는 유저 스택의 크기가 증가할 것이다. uninitialized data segment는 시스템 콜에 의해 조정이 가능하다.

The code segment in Pintos starts at user virtual address 0x400000, approximately 128 MB from the bottom of the address space. This value was typical value in ubuntu and has no deep significance.

핀토스에서의 code segment는 대략 128MB 크기의 주소 공간의 아래 부분에서부터 유저 가상 공간 0x400000에서 시작한다.

The linker sets the layout of a user program in memory, as directed by a "linker script" that tells it the names and locations of the various program segments. You can learn more about linker scripts by reading the "Scripts" chapter in the linker manual, accessible via info ld.

리눅스 x86-64 런타임 메모리 구성

  1. Read-only Code Segment, Read/Write Data Segment: x86-64 리눅스 시스템에서 코드 세그먼트는 주소 0x400000에서 시작하고, 뒤이어 데이터 세그먼트가 온다.

  2. Run-time Heap: 런타임 힙은 데이터 세그먼트 다음에 따라오고, malloc 라이브러리를 호출해서 위로 성장한다.

  3. Memory-mapped region for shared libraries: 다음에는 공유 모듈들을 위해 예약된 영역이 존재한다.

  4. User Stack: 사용자 스택은 가장 큰 합법적 사용자 주소(2^48 - 1) 아래에서 시작해서 더 작은 메모리 주소 방향인 아래로 성장한다.

  5. Kernel Memory: 스택 위의 영역은 운영체제의 메모리 상주 부분인 커널의 코드와 데이터를 위해 예약되어 있다.

링커 개념 읽고 다시 보기

To view the layout of a particular executable, run objdump with the -p option.

Accessing User Memory

As part of a system call, the kernel must often access memory through pointers provided by a user program. The kernel must be very careful about doing so, because the user can pass a null pointer, a pointer to unmapped virtual memory, or a pointer to kernel virtual address space (above KERN_BASE). All of these types of invalid pointers must be rejected without harm to the kernel or other running processes, by terminating the offending process and freeing its resources.

커널은 시스템 콜의 일부로서 메모리 공간을 유저 프로그램에서 제공되는 포인터를 통해 접근해야 한다. 커널이 포인터를 통해 메모리 공간을 접근하는 과정에서 유저는 가상 메모리 공간에 매핑 되지 않거나 커널 가상 공간에 매핑된 null pointer를 사용할 수 있다. 이러한 유효하지 않은 종류의 포인터는 offending 프로세스를 종료하고 할당된 리소스를 해제함으로써 커널이나 다른 실행 중인 프로세스에 피해를 주지 않고 거절(reject)되어야 한다.

There are at least two reasonable ways to do this correctly. The first method is to verify the validity of a user-provided pointer, then dereference it. If you choose this route, you'll want to look at the functions in thread/mmu.c and in include/threads/vaddr.h. This is the simplest way to handle user memory access.

이러한 방법을 올바르게 실행하는 두 가지 방법이 존재한다. 첫 번째 방법은 user-provided 포인터의 유효성을 검증한 후 역참조하는 것이다. 이 방법을 사용하기로 결정하면 thread/mmu.c과 include/threads/vaddr.h에서 정의된 함수를 파악해야 한다. 이 방법은 유저 메모리에 대한 접근을 다루는 가장 간단한 방법이다.

The second method is to check only that a user pointer points below KERN_BASE, then dereference it. An invalid user pointer will cause a "page fault" that you can handle by modifying the code for page_fault() in userprog/exception.c. This technique is normally faster because it takes advantage of the processor's MMU, so it tends to be used in real kernels (including Linux).

두 번째 방법은 유저 포인터가 KERN_BASE를 가리키는지 확인한 후 역참조하는 방법이다. 유효하지 않은 유저 포인터는 userprog/exception.c에서 구현된 코드를 수정함으로써 다룰 수 있는 페이지 폴트를 유발할 것이다. 이러한 방법은 프로세서의 MMU를 이용하기 때문에 일반적으로 더 빠르며 리눅스를 포함한 실제 커널에서 사용되는 경향이 있다.

In either case, you need to make sure not to "leak" resources. For example, suppose that your system call has acquired a lock or allocated memory with malloc(). If you encounter an invalid user pointer afterward, you must still be sure to release the lock or free the page of memory. If you choose to verify user pointers before dereferencing them, this should be straightforward. It's more difficult to handle if an invalid pointer causes a page fault, because there's no way to return an error code from a memory access. Therefore, for those who want to try the latter technique, we'll provide a little bit of helpful code:

둘 중 어떤 경우에도 리소스가 낭비되지 않도록 확인하는 것이 필요하다. 예를 들어 시스템 콜을 호출하여 락 또는 malloc() 함수를 통해 할당된 메모리를 획득하였다고 가정한다. 나중에 유효하지 않은 유저 포인터를 만나게 되면 사용자는 락을 반환하거나 할당된 메모리의 페이지를 해제해야 한다. 첫 번째 방법을 통해 유저 포인터의 유효성을 확인하기로 결정하면 직관적이어야 한다. 메모리 공간에서는 에러 코드를 리턴하지 않기 때문에 유효하지 않은 포인터가 페이지 폴트를 유발하면 더욱 대처하기 어렵다. 따라서 두 번째 방법을 사용하고자 한다면 핀토스에서 아래에 코드로부터 도움을 얻을 수 있다.

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

Each of these functions assumes that the user address has already been verified to be below KERN_BASE. They also assume that you've modified page_fault() so that a page fault in the kernel merely sets rax to -1 and copies its former value into %rip.

두 함수는 모두 유저 주소 공간이 이미 KERN_BASE에서 검증되었다고 가정한다. 또한 userprog에서 page_fault() 함수를 커널에서의 페이지 폴트가 -1에서 시작하여 이전의 값을 %rip로 복사할 것으로 수정하였다고 가정한다.

결과

pass tests/threads/priority-donate-chain
FAIL tests/userprog/args-none
FAIL tests/userprog/args-single
FAIL tests/userprog/args-multiple
FAIL tests/userprog/args-many
FAIL tests/userprog/args-dbl-space
FAIL tests/userprog/halt
FAIL tests/userprog/exit
FAIL tests/userprog/create-normal
FAIL tests/userprog/create-empty
FAIL tests/userprog/create-null
FAIL tests/userprog/create-bad-ptr
FAIL tests/userprog/create-long
FAIL tests/userprog/create-exists
FAIL tests/userprog/create-bound
FAIL tests/userprog/open-normal
FAIL tests/userprog/open-missing
FAIL tests/userprog/open-boundary
FAIL tests/userprog/open-empty
FAIL tests/userprog/open-null
FAIL tests/userprog/open-bad-ptr
FAIL tests/userprog/open-twice
FAIL tests/userprog/close-normal
FAIL tests/userprog/close-twice
FAIL tests/userprog/close-bad-fd
FAIL tests/userprog/read-normal
FAIL tests/userprog/read-bad-ptr
FAIL tests/userprog/read-boundary
FAIL tests/userprog/read-zero
FAIL tests/userprog/read-stdout
FAIL tests/userprog/read-bad-fd
FAIL tests/userprog/write-normal
FAIL tests/userprog/write-bad-ptr
FAIL tests/userprog/write-boundary
FAIL tests/userprog/write-zero
FAIL tests/userprog/write-stdin
FAIL tests/userprog/write-bad-fd
FAIL tests/userprog/fork-once
FAIL tests/userprog/fork-multiple
FAIL tests/userprog/fork-recursive
FAIL tests/userprog/fork-read
FAIL tests/userprog/fork-close
FAIL tests/userprog/fork-boundary
FAIL tests/userprog/exec-once
FAIL tests/userprog/exec-arg
FAIL tests/userprog/exec-boundary
FAIL tests/userprog/exec-missing
FAIL tests/userprog/exec-bad-ptr
FAIL tests/userprog/exec-read
FAIL tests/userprog/wait-simple
FAIL tests/userprog/wait-twice
FAIL tests/userprog/wait-killed
FAIL tests/userprog/wait-bad-pid
FAIL tests/userprog/multi-recurse
FAIL tests/userprog/multi-child-fd
FAIL tests/userprog/rox-simple
FAIL tests/userprog/rox-child
FAIL tests/userprog/rox-multichild
FAIL tests/userprog/bad-read
FAIL tests/userprog/bad-write
FAIL tests/userprog/bad-read2
FAIL tests/userprog/bad-write2
FAIL tests/userprog/bad-jump
FAIL tests/userprog/bad-jump2
FAIL tests/filesys/base/lg-create
FAIL tests/filesys/base/lg-full
FAIL tests/filesys/base/lg-random
FAIL tests/filesys/base/lg-seq-block
FAIL tests/filesys/base/lg-seq-random
FAIL tests/filesys/base/sm-create
FAIL tests/filesys/base/sm-full
FAIL tests/filesys/base/sm-random
FAIL tests/filesys/base/sm-seq-block
FAIL tests/filesys/base/sm-seq-random
FAIL tests/filesys/base/syn-read
FAIL tests/filesys/base/syn-remove
FAIL tests/filesys/base/syn-write
FAIL tests/userprog/no-vm/multi-oom
pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
pass tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
pass tests/threads/priority-change
pass tests/threads/priority-donate-one
pass tests/threads/priority-donate-multiple
pass tests/threads/priority-donate-multiple2
pass tests/threads/priority-donate-nest
pass tests/threads/priority-donate-sema
pass tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
pass tests/threads/priority-sema
pass tests/threads/priority-condvar
pass tests/threads/priority-donate-chain
77 of 95 tests failed.
profile
신호정 벨로그
hello world
이전 포스트

[WEEK 08] Weekly I Learned

다음 포스트

[WEEK 09] PintOS - Project 2: User Programs (Argument Passing)

0개의 댓글