이 포스팅은 제가 친구와 PintOS 과제를 하면서 떠올린 생각이나 삽질을 하는 과정을 의식의 흐름대로 적은 글이며 글을 작성한 이후 원래 코드에서 일부 오타나 버그가 수정되었을 수 있습니다. 즉 이 포스팅은 정답을 알려주는 포스팅이 아님을 밝힙니다.
나머지 복잡한 친구들
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
pass tests/filesys/base/lg-create
pass tests/filesys/base/lg-full
pass tests/filesys/base/lg-random
pass tests/filesys/base/lg-seq-block
pass tests/filesys/base/lg-seq-random
pass tests/filesys/base/sm-create
pass tests/filesys/base/sm-full
pass tests/filesys/base/sm-random
pass tests/filesys/base/sm-seq-block
pass tests/filesys/base/sm-seq-random
FAIL tests/filesys/base/syn-read
pass tests/filesys/base/syn-remove
FAIL tests/filesys/base/syn-write
FAIL tests/userprog/no-vm/multi-oom이제 12개만 더 통과하면 된다! rox-simple부터 열어보자. 이 파일은 이렇게 생겼다.
void
test_main (void)
{
int handle;
char buffer[16];
CHECK ((handle = open ("rox-simple")) > 1, "open \"rox-simple\"");
CHECK (read (handle, buffer, sizeof buffer) == (int) sizeof buffer,
"read \"rox-simple\"");
CHECK (write (handle, buffer, sizeof buffer) == 0,
"try to write \"rox-simple\"");
}테스트 케이스 상에서는 buffer의 크기가 16인데, 쓰기를 시도할 때 EOF에 도달했기 때문에 0이 출력되어야 하는데 우리의 write()의 결과는 16을 출력하고 있다.
우리가 계속 system call만 하고 있었는데, 그 다음 문제가 바로 실행 가능한 파일에 대한 write()를 거부하는 것이었다.
글을 읽어보니, 실행되고 있는 파일이 실행 도중에 수정되는 것을 막아야 한다고 하니, process_create_initd()와 process_exec()에서 공통적으로 실행되는 load() 함수에서 다음과 같이, 기존에 실행 중인 파일에 대한 쓰기를 허용하고 새로 실행할 파일에 대한 쓰기를 거부하는 코드를 추가하며, 프로세스가 종료될 때 쓰기를 허용하는 코드를 추가하면 될 것 같다.
static bool
load(const char *file_name, struct intr_frame *if_)
{
struct thread *t = thread_current();
// ...
if (t->running_file != NULL)
{
file_allow_write(t->running_file);
t->running_file = NULL;
}
/* Open executable file. */
file = filesys_open(file_name);
file_deny_write(file);
t->running_file = file;
// ...
}
void _exit(int status)
{
// ...
/* Call the thread_exit() function. */
printf("%s: exit(%d)\n", thread_name(), status);
/* Allow write to executables. */
file_allow_write(curr->running_file);
thread_exit();
}하지만 이렇게 했더니, 이미 쓰기가 허용된 파일에 file_allow_write()를 했다는 오류가 발생했다. 찾아보니, 기존에 정의된 file_close() 안에 file_allow_write()가 내장되어 있었기 때문이었다. load()가 끝나면 file_close()가 호출되고, 나중에 우리가 file_allow_write()를 호출하면 오류가 나는 것이었다. 즉, 우리는 file_allow_write() 함수를 직접 사용하지 않고 file_close() 함수를 통해 닫으면 될 것 같다.
/* Closes FILE. */
void
file_close (struct file *file) {
if (file != NULL) {
file_allow_write (file);
inode_close (file->inode);
free (file);
}
}즉, _open()에서 파일을 열 때, 현재 실행되고 있는 파일 이름과 열려고 하는 파일 이름을 비교하여 같으면, 열리긴 열리되 쓰기가 불가능하게 설정하고, 프로세스가 종료될 때 닫으면 되겠다.
int _open(const char *file)
{
check_address((void *)file);
struct file *f = filesys_open(file);
if (f == NULL)
return -1;
struct thread *curr = thread_current();
if (!strcmp(thread_name(), file))
file_deny_write(f);
// ...
}
void _exit(int status)
{
/* Close all open files. */
struct thread *curr = thread_current();
for (int i = 2; i < MAX_FILE_NUM; i++)
_close(i);
// ...
}
void _close(int fd)
{
if (fd < 2 || fd >= MAX_FILE_NUM)
return; /* Ignore stdin, stdout and invalid fd. */
struct thread *curr = thread_current();
if (curr->fd_table[fd] != NULL)
file_close(curr->fd_table[fd]);
// ...
}즉, _exit()는 명시적으로 모든 파일에 대해 _close()를 호출하므로, 여기에 파일을 닫는 file_close() 함수를 사용하면 될 것 같다!
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/syn-read
FAIL tests/filesys/base/syn-write
FAIL tests/userprog/no-vm/multi-oom이제 9개 남았다! bad-read부터 보자.
void
test_main (void)
{
msg ("Congratulations - you have successfully dereferenced NULL: %d",
*(int *)NULL);
fail ("should have exited with -1");
}지금까지는 이런 코드가 Page fault와 함께 Kernel Panic을 발생시켰다면, 이 부분을 exit(-1)로 처리해 주면 될 것 같다. 이를 위해 Page fault와 관련된 코드로 들어가 보자. 안 그래도 이걸 고쳐야 할 것 같다고 적혀 있는 것 같다.
/* Page fault handler. This is a skeleton that must be filled in
to implement virtual memory. Some solutions to project 2 may
also require modifying this code.
At entry, the address that faulted is in CR2 (Control Register
2) and information about the fault, formatted as described in
the PF_* macros in exception.h, is in F's error_code member. The
example code here shows how to parse that information. You
can find more information about both of these in the
description of "Interrupt 14--Page Fault Exception (#PF)" in
[IA32-v3a] section 5.15 "Exception and Interrupt Reference". */
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. */
/* Obtain faulting address, the virtual address that was
accessed to cause the fault. It may point to code or to
data. It is not necessarily the address of the instruction
that caused the fault (that's f->rip). */
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
/* Count page faults. */
page_fault_cnt++;
/* If the fault is true fault, show info and exit. */
printf ("Page fault at %p: %s error %s page in %s context.\n",
fault_addr,
not_present ? "not present" : "rights violation",
write ? "writing" : "reading",
user ? "user" : "kernel");
kill (f);
}일단 우리는 Page fault를 따로 처리하지 않을 것이기 때문에, 그냥 Page fault가 발생하면 _exit(-1)을 통해 프로세스를 종료할 예정이다.
FAIL tests/filesys/base/syn-read
pass tests/filesys/base/syn-remove
FAIL tests/filesys/base/syn-write
FAIL tests/userprog/no-vm/multi-oom이제 3개 남았는데, 뭔가 동시에 파일을 열고 닫는 것 같은데 생각해 보면 우리가 같은 파일에 다양한 프로세스가 접근해서 수정하는 경우를 생각하지 않았으니, syn-remove가 통과했지만 이것도 운에 따라서 달라질 수 있기 때문에 이 3개를 먼저 고려해 주도록 하자.
방법은 간단할 것 같은데, 하나의 프로세스에서 _create(), _remove(), _read(), _write(), _open(), _close() 같은 파일 관련 system call을 처리할 때 다른 프로세스가 접근하지 못하도록 하면 되지 않을까?
즉 이러한 system call을 처리하는 프로세스만 파일에 접근할 수 있어야 하니, 다른 프로세스를 기다리는 세마포어와 같은 구조체보다 lock을 사용하는 것이 가장 적절한 방법인 것 같다!
그러므로 syscall.c 파일에 모든 프로세스가 공유할 수 있는 글로벌 lock을 하나 정의하고, 함수의 시작과 끝에 lock을 획득/반납하는 코드를 추가해야 할 것 같다.
struct lock global_file_lock;
int _read(int fd, void *buffer, unsigned length)
{
check_address(buffer);
if (buffer == NULL)
return -1;
if (fd == 1)
return -1;
if (fd < 0 || fd >= MAX_FILE_NUM)
return -1;
lock_acquire(&global_file_lock);
// ...
lock_release(&global_file_lock);
return result;
}다음과 같이 여러 함수들에 lock을 걸어주고 실행했더니...
child-syn-read: exit(3)
(syn-read) wait for child 4 of 10 returned 3 (expected 3)
Interrupt 0x0d (#GP General Protection Exception) at rip=800421c52b
cr2=0000000000000000 error= 0
rax cccccccccccccc0c rbx 00008004242f2000 rcx 0000000000403818 rdx 000000800421e0b8
rsp 0000008004242ec0 rbp 0000008004242ef0 rsi 0000000000000000 rdi 00000080042420a0
rip 000000800421c52b r8 0000000000000000 r9 0000000000000000 r10 0000000000000000
r11 0000000000000216 r12 000000800421d5dd r13 00008004227b5000 r14 00008004227b5000
r15 00008004206ac600 rflags 00000296
es: 001b ds: 001b cs: 0008 ss: 0010
Kernel PANIC at ../../userprog/exception.c:99 in kill(): Kernel bug - unexpected interrupt in kernel
Call stack: 0x80042185ab 0x800421d394 0x80042094a3 0x80042098c1 0x800421e08a 0x800421d82e 0x800421d506 0x4007b9 0x4002be 0x400fa7 0x400ff0
Translation of call stack:
0x00000080042185ab: debug_panic (lib/kernel/debug.c:32)
0x000000800421d394: kill (userprog/exception.c:105)
0x00000080042094a3: intr_handler (threads/interrupt.c:352)
0x00000080042098c1: intr_entry (threads/intr-stubs.o:?)
0x000000800421e08a: _wait (userprog/syscall.c:396)
0x000000800421d82e: syscall_handler (userprog/syscall.c:130)
0x000000800421d506: no_sti (userprog/syscall-entry.o:?)
0x00000000004007b9: (unknown)
0x00000000004002be: (unknown)
0x0000000000400fa7: (unknown)
0x0000000000400ff0: (unknown)
_wait()쪽에서 General Protection Exception이라는 게 발생했다...! 찾아보니 Segmentation Fault랑 비슷하다는데, 무엇이 문제일까? 이를 위해 syn_read.c를 뜯어보자!
/* Spawns 10 child processes, all of which read from the same
file and make sure that the contents are what they should
be. */
#include <random.h>
#include <stdio.h>
#include <syscall.h>
#include "tests/lib.h"
#include "tests/main.h"
#include "tests/filesys/base/syn-read.h"
static char buf[BUF_SIZE];
#define CHILD_CNT 10
void
test_main (void)
{
pid_t children[CHILD_CNT];
int fd;
CHECK (create (file_name, sizeof buf), "create \"%s\"", file_name);
CHECK ((fd = open (file_name)) > 1, "open \"%s\"", file_name);
random_bytes (buf, sizeof buf);
CHECK (write (fd, buf, sizeof buf) > 0, "write \"%s\"", file_name);
msg ("close \"%s\"", file_name);
close (fd);
exec_children ("child-syn-read", children, CHILD_CNT);
wait_children (children, CHILD_CNT);
}exec_children()과 wait_children()도 뜯어보자.
void
exec_children (const char *child_name, pid_t pids[], size_t child_cnt)
{
size_t i;
for (i = 0; i < child_cnt; i++)
{
char cmd_line[128];
snprintf (cmd_line, sizeof cmd_line, "%s %zu", child_name, i);
if ((pids[i] = fork (child_name))){
CHECK (pids[i] != PID_ERROR,
"exec child %zu of %zu: \"%s\"", i + 1, child_cnt, cmd_line);
} else {
exec (cmd_line);
}
}
}
void
wait_children (pid_t pids[], size_t child_cnt)
{
size_t i;
for (i = 0; i < child_cnt; i++)
{
int status = wait (pids[i]);
CHECK (status == (int) i,
"wait for child %zu of %zu returned %d (expected %zu)",
i + 1, child_cnt, status, i);
}
}즉, exec_children()은 현재 프로세스를 fork()한 후 자식 프로세스를 실행하는 것을 10번 반복하고, wait_children()은 이것을 생성된 순서대로 기다린다. 그럼 여기에서, fork(), exec(), wait()가 몇 번 실행되었는지 확인해 보자.
Executing 'syn-read':
(syn-read) begin
(syn-read) create "data"
(syn-read) open "data"
(syn-read) write "data"
(syn-read) close "data"
Fork 1번째 실행 시작
(syn-read) exec child 1 of 10: "child-syn-read 0"
Fork 2번째 실행 시작
(syn-read) exec child 2 of 10: "child-syn-read 1"
Fork 3번째 실행 시작
(syn-read) exec child 3 of 10: "child-syn-read 2"
Fork 4번째 실행 시작
(syn-read) exec child 4 of 10: "child-syn-read 3"
Fork 5번째 실행 시작
(syn-read) exec child 5 of 10: "child-syn-read 4"
Fork 6번째 실행 시작
(syn-read) exec child 6 of 10: "child-syn-read 5"
Fork 7번째 실행 시작
(syn-read) exec child 7 of 10: "child-syn-read 6"
Fork 8번째 실행 시작
(syn-read) exec child 8 of 10: "child-syn-read 7"
Fork 9번째 실행 시작
(syn-read) exec child 9 of 10: "child-syn-read 8"
Fork 10번째 실행 시작
(syn-read) exec child 10 of 10: "child-syn-read 9"
Wait 1번째 실행 시작
Exit 1번째 실행 시작
child-syn-read: exit(0)
Exit 1번째 실행 끝
Wait 1번째 실행 끝
(syn-read) wait for child 1 of 10 returned 0 (expected 0)
Wait 2번째 실행 시작
Exit 2번째 실행 시작
child-syn-read: exit(5)
Exit 2번째 실행 끝
Exit 3번째 실행 시작
child-syn-read: exit(8)
Exit 3번째 실행 끝
Exit 4번째 실행 시작
child-syn-read: exit(6)
Exit 4번째 실행 끝
Exit 5번째 실행 시작
child-syn-read: exit(9)
Exit 5번째 실행 끝
Exit 6번째 실행 시작
child-syn-read: exit(7)
Exit 6번째 실행 끝
Exit 7번째 실행 시작
child-syn-read: exit(1)
Exit 7번째 실행 끝
Wait 2번째 실행 끝
(syn-read) wait for child 2 of 10 returned 1 (expected 1)
Wait 3번째 실행 시작
Exit 8번째 실행 시작
child-syn-read: exit(2)
Exit 8번째 실행 끝
Wait 3번째 실행 끝
(syn-read) wait for child 3 of 10 returned 2 (expected 2)
Wait 4번째 실행 시작
Exit 9번째 실행 시작
child-syn-read: exit(4)
Exit 9번째 실행 끝
Exit 10번째 실행 시작
child-syn-read: exit(3)
Exit 10번째 실행 끝
Wait 4번째 실행 끝
(syn-read) wait for child 4 of 10 returned 3 (expected 3)
Wait 5번째 실행 시작
Interrupt 0x0d (#GP General Protection Exception) at rip=800421c52b이것을 보면, wait()가 10번이 실행되지 못하고 중간에서 오류가 나는 것을 볼 수 있다. 이 횟수는 심지어 실행할 때마다 조금씩 다른데, 우리의 생각에는 이미 자식 프로세스가 종료되었을 때 wait()를 호출하면 문제가 발생하는 게 아닐까 하는 생각이 들었다! 그래서, 일단 thread 구조체에 child_list_lock을 추가해서, 자식 프로세스 리스트를 수정할 때 lock을 획득하고 나서 수정할 수 있도록 코드를 수정하였다.
struct thread
{
// ...
struct lock child_list_lock; /* Lock for child list iteration. IMPLEMENTED IN PROJECT 2-3. */
// ...
}void process_exit(void)
{
// ...
if (curr->parent_thread != NULL)
{
lock_acquire(&curr->parent_thread->child_list_lock);
struct list_elem *e;
for (e = list_begin(&curr->parent_thread->child_threads);
e != list_end(&curr->parent_thread->child_threads);
e = list_next(e))
{
// ...
lock_release(&curr->parent_thread->child_list_lock);
curr->parent_thread = NULL;
}
// ...
}int process_wait(tid_t child_tid UNUSED)
{
// ...
lock_acquire(&curr->child_list_lock);
for (e = list_begin(&curr->child_threads);
e != list_end(&curr->child_threads);
e = list_next(e))
{
struct thread *t = list_entry(e, struct thread, c_elem);
if (t->tid == child_tid)
{
// ...
lock_release(&curr->child_list_lock);
return curr->child_exit_status;
}
}
// ...
}이렇게 하고 다시 테스트를 했더니, 예외가 사라지고 대신 잘못된 exit_status를 받아 실패했다!
FAIL tests/filesys/base/syn-write
run: wait for child 1 of 10 returned 9 (expected 0): FAILEDwait()의 설명을 보면 아래와 같은데...
It is perfectly legal for a parent process to wait for child processes
that have already terminated by the time the parent calls wait,
but the kernel must still allow the parent to retrieve its child’s exit status,
or learn that the child was terminated by the kernel.
즉, 이미 자식 프로세스가 종료된 후 wait()이 호출되었더라도 부모 프로세스는 자식 프로세스가 어떻게 종료되었는지 알고 있어야 한다는 것이다.
우리는 _exit()를 구현할 때, 부모 프로세스의 int child_exit_status 필드를 수정하고 있는데 이렇게 된다면 가장 최근에 종료된 자식 프로세스 하나에 대한 정보만 알 수 있으니 일단 이 부분을 고쳐야 할 것 같다.
그렇다면, 이 문제를 해결하기 위한 두 가지 방법을 생각할 수 있다.
- 자식 프로세스의
exit_status를 정수 하나가 아닌 리스트로 저장하여, 만약wait()가 호출될 때 이미 자식 프로세스가 끝났더라도 종료될 당시의exit_status를 저장할 수 있도록 한다.- 자식 프로세스가 종료될 때 자식 프로세스에
exit_status를 저장하고, 종료될 때 스레드 구조체를 없애는 것이 아니라wait()가 반환될 때 없앤다.
이 두 가지 방법을 생각해 보면 굳이 자식 프로세스의 exit_status를 담는 리스트가 필요하지는 않을 것 같지만, 사실 fork() 이후 wait() 없이 프로세스가 종료되는 경우도 있기 때문에, 2번 방법을 사용한다면 wait()가 호출되지 않을 때 종료된 프로세스의 thread 구조체가 계속 남아 있게 된다. 즉 1번 방법을 사용하도록 하자!
자식 프로세스의 tid와 exit_status를 하나의 구조체인 struct tid_status에 저장하고, thread 구조체에 리스트로 저장하자.
struct tid_status
{
tid_t tid;
int status;
struct list_elem elem;
};struct thread
{
// ...
struct list tid_exit_status;
// ...
}프로세스가 종료될 때, 부모 프로세스에 자식 프로세스의 tid와 exit_status를 담은 tid_status를 추가하고, wait()에서 이미 종료된 자식 프로세스의 tid를 받으면 tid_exit_status 리스트에서 찾아서 종료될 당시의 exit_status를 반환한다.
void _exit(int status)
{
// ...
if (curr->parent_thread != NULL)
{
struct tid_status *ts = malloc(sizeof(struct tid_status));
ts->tid = curr->tid;
ts->status = status;
list_push_back(&curr->parent_thread->tid_status_list, &ts->elem);
}
// ...
}int process_wait(tid_t child_tid UNUSED)
{
// ...
/* After child exit, find its exit status. */
for (e = list_begin(&curr->tid_status_list);
e != list_end(&curr->tid_status_list);
e = list_next(e))
{
struct tid_status *ts = list_entry(e, struct tid_status, elem);
if (ts->tid == child_tid)
{
int ret = ts->status;
list_remove(e);
free(ts);
return ret;
}
}
/* Search miss. */
return -1;
}이렇게 이미 종료된 자식 프로세스의 tid와 exit_status 매핑을 저장해서 반환한 결과 syn-read와 syn-write까지 통과할 수 있게 되었다! 글은 되게 짧지만 나름 거의 2주 넘게 고민하고 있던 문제였는데 결국 풀려서 너무 행복했다...
FAIL tests/userprog/no-vm/multi-oom
1 of 95 tests failed.이것은 메모리 누수를 검사하는 테스트 케이스라고 하는데, fork() 를 계속 하고 파일을 열 수 있을 때까지 열어서 메모리를 소비하는 테스트 케이스라고 한다. 즉 할당한 공간을 해제하는 것이 정말 중요하다고 볼 수 있다. 일단, consume_some_resources() 함수에 정의된 fdmax가 126이라 우리가 정의한 MAX_FILE_NUM = 128과 달랐는데, 생각해 보니 stdin과 stdout을 제외해야 하기 때문에 우선 MAX_FILE_NUM을 126으로 수정하였다.
// multi-oom.c
static void
consume_some_resources(void)
{
int fd, fdmax = 126;
// ...
}
int main(int argc UNUSED, char *argv[] UNUSED)
{
msg("begin");
int first_run_depth = make_children();
CHECK(first_run_depth >= EXPECTED_DEPTH_TO_PASS, "Spawned at least %d children.", EXPECTED_DEPTH_TO_PASS);
for (int i = 0; i < EXPECTED_REPETITIONS; i++)
{
int current_run_depth = make_children();
if (current_run_depth < first_run_depth)
{
fail("should have forked at least %d times, but %d times forked",
first_run_depth, current_run_depth);
}
}
msg("success. Program forked %d iterations.", EXPECTED_REPETITIONS);
msg("end");
}디버깅이 어려웠지만 문제는 생각보다 간단했는데, 바로 __do_fork()에서 성공과 실패에 따른 분기를 정확히 처리해 주지 않아서, 즉 fork()가 성공하지 못했을 때 실행되어야 하는 코드가 제대로 실행되지 않아서였던 것 같다.
static void
__do_fork(void *aux)
{
// ...
/* IMPLEMENTED IN PROJECT 2-3.
If success, specify the parent-child relationship. */
list_push_back(&parent->child_threads, ¤t->c_elem);
current->parent_thread = parent;
sema_up(fork_sema); /* IMPLEMENTED IN PROJECT 2-3. */
do_iret(&if_);
error:
succ = false;
sema_up(fork_sema); /* IMPLEMENTED IN PROJECT 2-3. */
/* DELETED IN PROJECT 2-3.
thread_exit();
*/
_exit(-1);
}이걸 고치니 마지막 테스트를 통과하였는데, 저번에 프로세스가 종료될 때 struct thread를 남겨두는 것이 아니라 malloc()과 list를 이용하여 자식 프로세스의 exit_status를 저장하도록 exit()와 wait()를 수정한 결과, Recursive fork가 28번만 성공하면 되는 테스트 케이스에서 100번 넘게 성공하며 wait() 없이 exit()된 struct thread의 공간을 굉장히 많이 절약했기 때문이 아닐까 생각하였다!
All 95 tests passed.드디어 Project 2를 마무리했고, 이번에는 그냥 돌아가면 되는 코드를 짠 게 아니라 나름대로 디자인과 성능까지 생각하면서 실행되었다는 사실이 좋은 것 같다!
