# Project 2: User Programs ## Preliminaries Yicheng Kang 10225101538@stu.ecnu.edu.cn ### References - https://github.com/NicoleMayer/pintos_project2/blob/master/pintos_report.md - https://www.dengzexuan.top/2021/05/pintos-project2 - https://github.com/codyjack/OS-pintos/blob/master/PROJECT2-DESIGNDOC - https://zhuanlan.zhihu.com/p/441433700 ## Process Termination Messages #### DATA STRUCTURES 在`thread`结构体中添加`st_exit`保存退出状态 #### ALGORITHMS 每个线程结束时,都会调用`thread_exit()`函数,而通过以下三行: ```c #ifdef USERPROG process_exit (); #endif ``` 我们可以知道,如果是用户进程,则会调用`process_exit ()`。因此我们只需要在`process_exit ()`里添加进程终止信息。添加下面这行即可: ```c printf("%s: exit(%d)\n", t_cur->name, t_cur->exit_code); ``` `t_cur`指向当前线程,`t_cur->name`即线程名称,`t_cur->exit_code`即`exit code`。 ## Argument Passing #### DATA STRUCTURES >A1: Copy here the declaration of each new or changed struct or struct member, global or static variable, typedef, or enumeration. Identify the purpose of each in 25 words or less. 这个部分不需要定义新的数据结构。 #### ALGORITHMS >A2: Briefly describe how you implemented argument parsing. How do you arrange for the elements of argv[] to be in the right order? >How do you avoid overflowing the stack page? 在<process.c>中,我们通过`process_execute`函数来把获传入的`file_name`分割成文件名、参数,并压入栈中。其修改后的代码如下: ```c tid_t process_execute (const char *file_name) { char *proc_cmd_copy1, *proc_cmd_copy2; tid_t tid; /* Make two copies of PROC_CMD (one for proc_name and one for start_process). Otherwise there's a race between the caller and load(). */ proc_cmd_copy1 = palloc_get_page(0); proc_cmd_copy2 = palloc_get_page(0); if (proc_cmd_copy1 == NULL || proc_cmd_copy2 == NULL) return TID_ERROR; strlcpy (proc_cmd_copy1, file_name, PGSIZE); strlcpy (proc_cmd_copy2, file_name, PGSIZE); char *save_ptr; char *proc_name = strtok_r(proc_cmd_copy1, " ", &save_ptr); /* Create a new thread to execute PROC_CMD. */ tid = thread_create (proc_name, PRI_DEFAULT, start_process, proc_cmd_copy2); palloc_free_page(proc_cmd_copy1); if (tid == TID_ERROR) { return TID_ERROR; } sema_down(&thread_current()->sema_exec); if (!thread_current()->exec_success) { return -1; } thread_current()->exec_success = false; // reset the flag for next spawn return tid; } ``` 其中`stroke_r`函数的用法如下: ```c char *strtok_r (char *s, const char *delimiters, char **save_ptr) ; ``` 其返回值是排在前面的被分割出的字串,或者为NULL,s是传入的字符串。 由于该函数会改变传入字符串的值,因此我们需要先对`file_name`进行拷贝,得到`proc_cmd_copy1`和`proc_cmd_copy2`。其中`proc_cmd_copy1`用来获取`proc_name`,也就是要执行的命令名称。而`proc_cmd_copy2`用来作为`thread_create`的参数传入来创建线程。 接下来看`thread_create`的定义: ```c tid_t thread_create (const char *name, int priority,thread_func *function, void *aux) ``` `name`即线程名,`priority`为优先级,`function`为要执行的函数,`aux`为传入参数。在这个函数中,调用了`start_process`,压栈过程在这部分中完成。 `start_process`会先调用`load`函数,为用户程序分配内存空间,然后开始建立堆栈,下面着重说明堆栈的建立过程。 ![](https://s2.loli.net/2023/12/06/oIL4cN9td7Wbkrj.png) 上图是pintos文档中对用户的栈的介绍,非常清晰明了。我们首先要知道内核是会保存一部分虚拟内存空间的,并不是所有的虚拟内存空间都可以为用户所用。这里只有`0x00000000`到`0xC0000000`是被分配给用户使用的。栈帧`%ESP`一开始指向`0xC0000000`。栈是从高地址向低地址扩展的,而又因为`word-align`(字对齐),因此`%ESP`每次都减少4。每次传入参数,就进行上述“压栈”操作。根据上图提示,我们在最后还要压入一个`0`作为返回地址。 下面我们来进行实现。 1. 设置`%ESP`到`0xc0000000`,即`PHYS_BASE` ```c if_.esp = PHYS_BASE; ``` 2. 拆分命令,将参数置于栈顶并记录他们的地址 ```c for (token = strtok_r (proc_cmd_copy, " ", &save_ptr); token != NULL; token = strtok_r (NULL, " ", &save_ptr)) { size_t arg_len = strlen(token) + 1; if_.esp -= arg_len; memcpy(if_.esp, token, arg_len); argv[argc++] = if_.esp; } ``` `strtok_r (proc_cmd_copy, " ", &save_ptr)`表示以空格为分隔符进行拆分。 `arg_len`加一是考虑了字符串的结束符`\0`。 3. 进行字对齐,并压入每个字符串的地址,设立哨兵空指针 ```c //字对齐 uintptr_t tmp = (uintptr_t)if_.esp; if (tmp % 4 != 0) tmp -= tmp % 4; if_.esp = (void *)tmp; //压入每一个字符串的地址 size_t ptr_size = sizeof(void *); // size of a pointer if_.esp -= ptr_size; memset(if_.esp, 0, ptr_size); // null pointer sentinel for (int i = argc-1; i >= 0; i--) { if_.esp -= ptr_size; memcpy(if_.esp, &argv[i], ptr_size); } ``` 4. 压入`argv[0]`的地址 ```c if_.esp -= ptr_size; *(uintptr_t *)if_.esp = ((uintptr_t)if_.esp + ptr_size); ``` 我们知道`argv[0]`的地址,就能知道所有参数的地址了。 5. 压入参数数量`argc` ```c if_.esp -= ptr_size; *(int *)if_.esp = argc; ``` 6. 压入返回地址`0` ```c if_.esp -= ptr_size; memset(if_.esp, 0, ptr_size); ``` 为了防止栈溢出,有两种方法: 1. 每次使用栈之前都检查`%ESP`的有效性 2. 抛出异常,返回-1。 #### RATIONALE >A3: Why does Pintos implement strtok_r() but not strtok()? `strtok_r`比`strtok`在线程级别上更加安全,`strtok_r`中的`save_ptr`是由调用者提供的,在 pintos 中,内核 将命令分为命令行(可执行文件名)和参数。因此,我们需要将参数地址放在我们稍后可以找到的地方。 >A4: In Pintos, the kernel separates commands into a executable name and arguments. In Unix-like systems, the shell does this separation. Identify at least two advantages of the Unix approach. 1) 缩短内核时间 2) 强大的检查功能。在将可执行文件传递给内核之前,先检查该文件是否存在以避免内核失效。检查参数是否超过限制。 3) 一旦能分离命令,就能进行高级预处理,更像一个解释器,而不仅仅是一个接口。比如一次传递多组命令行,如 cd、mkdir tmp、touch test 和 pipe。 ## System Calls #### DATA STRUCTURES >B1: Copy here the declaration of each new or changed struct or struct member, global or static variable, typedef, or enumeration. Identify the purpose of each in 25 words or less. - 在<thread.h>新建结构体`child` ```c struct child { tid_t tid; /* tid of the thread */ bool isrun; /* whether the child's thread is run successfully */ struct list_elem child_elem; /* list of children */ struct semaphore sema; /* semaphore to control waiting */ int store_exit; /* the exit status of child thread */ }; ``` - 在<thread.h>中原有的`thread`结构体中添加如下变量 ```c struct list childs;/* The list of childs */ struct child * thread_child;/* Store the child of this thread */ int st_exit;/* Exit status */ struct semaphore sema;/* Control the child process's logic, finish parent waiting for child */ bool success;/* Judge whehter the child's thread execute successfully */ struct thread* parent;/* Parent thread of the thread */ struct list files; /* the list of opened files */ int file_fd; /* File's number thread has */ struct file * file_owned; /* the file opened */ ``` - 在<syscall.c>中新建结构体`syscalls` ```c struct list files; /* List of opened files */ int file_fd; /* File's descriptor */ struct file * file_owned; /* The file opened */ ``` - 在<syscall.c>中新建结构体`process_file` ```c struct thread_file{ int fd; struct file* file; struct list_elem file_elem; }; ``` >B2: Describe how file descriptors are associated with open files. Are file descriptors unique within the entire OS or just within a single process? 文件描述符在形式上是一个非负整数。实际上,它是一个索引值,指向内核为每一个进程所维护的该进程打开文件的记录表。当程序打开一个现有文件或者创建一个新文件时,内核向进程返回一个文件描述符。习惯惯上,标准输入(standard input)的文件描述符是 0,标准输出(standard output)是 1,标准错误(standard error)是 2。在此实现中,文件描述符与通过系统调用打开的每个文件一一对应。文件描述符在整个操作系统中是唯一的。在线程结构体上不应该放置太多信息,因此在内核中维护一个列表(list files 结构列表),因为每次文件访问都要经过内核。 #### ALGORITHMS >B3: Describe your code for reading and writing user data from the kernel. - read 1. 首先检查buffer和buffer+size是否都是合法指针,如果不是就返回-1。 这里调用`check_read_user_ptr(buffer, size)`来实现。 其代码如下: ```c static void * check_read_user_ptr(const void *ptr, size_t size) { if (!is_user_vaddr(ptr)) { terminate_process(); } for (size_t i = 0; i < size; i++) { // check if every byte is safe to read if (get_user(ptr + i) == -1) { terminate_process(); } } return (void *)ptr; // remove const } ``` 功能是检查用户提供的指针是否可以安全读取。如果安全,返回指针本身,或者调用terminate_process()(不返回)来终止进程,退出代码为-1。 2. 判断是否是`STDIN`,是则调用`input_getc()` ```c if (fd == 0) { // read from STDIN for (size_t i = 0; i < size; i++) { *(uint8_t *)buf = input_getc(); buf += sizeof(uint8_t); } f->eax = size; return; } ``` 3. 判断是否是`STDOUT`,是则终止 ```c if (fd == 1) // read from STDOUT, terminate terminate_process(); ``` 4. 都不是,正常读,需要在读前获取锁,在读完之后释放 ```c struct file_entry *entry = get_file(fd); if (entry != NULL) { lock_acquire(&filesys_lock); f->eax = file_read(entry->f, buf, size); lock_release(&filesys_lock); } else { f->eax = -1; } ``` - write 1. 首先检查buffer和buffer+size是否都是合法指针,如果不是就返回-1。 这里调用`check_read_user_ptr(buffer, size)`来实现。 2. 判断是否是`STDIN`,是则终止 ```c if (fd == 0) { // write to STDIN, terminate terminate_process(); ``` 3. 判断是否是`STDOUT`,是则调用`putbuf`输出 ```c if (fd == 1) { // write to STDOUT putbuf((char *)buf, size); f->eax = size; return; } ``` 4. 都不是,正常写,需要在写前获取锁,在写完之后释放 ```c struct file_entry *entry = get_file(fd);; if (entry != NULL) { lock_acquire(&filesys_lock); f->eax = file_write(entry->f, buf, size); lock_release(&filesys_lock); } else { f->eax = -1; } ``` >B4: Suppose a system call causes a full page (4,096 bytes) of data >to be copied from user space into the kernel. What is the least >and the greatest possible number of inspections of the page table >(e.g. calls to pagedir_get_page()) that might result? What about >for a system call that only copies 2 bytes of data? Is there room >for improvement in these numbers, and how much? - 对于一个完整页面的数据: 最小值是1。如果第一次检查(pagedir_get_page)返回一个页面头部,可以根据地址确定,那么我们实际上不需要再进行任何检查,它可能包含一页的数据。 最大值可能是4096,如果它不是连续的,那么在这种情况下,我们必须检查每个地址以确保有效访问。当它是连续的时候,最大值将是2,如果我们得到一个不是页面头部的内核虚拟地址,我们肯定要检查完整页面数据的起始指针和结束指针,看看它是否被映射。 - 对于2字节的数据: 最小值也是1。与上面类似,如果我们得到一个内核虚拟地址,其末尾有超过2字节的空间,我们知道它在这一页中,不需要进行额外的检查。 最大值也是2。如果它不是连续的,或者如果它是连续的但我们得到一个内核虚拟地址,离页面末尾仅有1字节的距离,我们必须检查另一个字节的位置。 - 改进: 似乎没有太多改进的空间。 >B5: Briefly describe your implementation of the "wait" system call >and how it interacts with process termination. 首先检查传入的pid是否合法,调用`check_read_user_ptr`函数即可。若合法就调用`process_wait`函数。 其代码如下: ```c static void syscall_wait(struct intr_frame *f) { int pid = *(int *)check_read_user_ptr(f->esp + ptr_size, sizeof(int)); f->eax = process_wait(pid); } ``` `process_wait`: ```c int process_wait (tid_t child_tid) { struct thread *t_cur = thread_current(); struct list_elem *e; for (e = list_begin (&t_cur->child_list); e != list_end (&t_cur->child_list); e = list_next (e)) { struct child_entry *entry = list_entry(e, struct child_entry, elem); if (entry->tid == child_tid) { if (!entry->is_waiting_on && entry->is_alive) { entry->is_waiting_on = true; sema_down(&entry->wait_sema); // wait for child process to exit return entry->exit_code; } else if (entry->is_waiting_on) { // already waiting on child return -1; } else { // child has terminated, retrieve exit_code return entry->exit_code; } } } return -1; // child_tid is not a child of current process } ``` >B6: Any access to user program memory at a user-specified address >can fail due to a bad pointer value. Such accesses must cause the >process to be terminated. System calls are fraught with such >accesses, e.g. a "write" system call requires reading the system >call number from the user stack, then each of the call's three >arguments, then an arbitrary amount of user memory, and any of >these can fail at any point. This poses a design and >error-handling problem: how do you best avoid obscuring the primary >function of code in a morass of error-handling? Furthermore, when >an error is detected, how do you ensure that all temporarily >allocated resources (locks, buffers, etc.) are freed? In a few >paragraphs, describe the strategy or strategies you adopted for >managing these issues. Give an example. 首先,避免不良的用户内存访问是通过在验证之前进行检查来实现的。检查的意思是使用我们编写的`check_read_user_ptr`函数来检查是否为NULL,是否为有效的用户地址以及是否已在进程的页面目录中映射。以“write”系统调用为例,首先会检查esp指针和三个参数指针,如果有任何无效的内容,将终止进程。然后在进入write函数之后,将在使用之前检查缓冲区的起始指针和缓冲区的结束指针(buffer + size - 1)。 其次,当错误仍然发生时,我们抛出page_fault异常,由中断处理程序进行处理。我们使用`check_read_user_ptr`函数检查fault_addr是否是有效的指针。如果它无效,将终止进程。以bad-jump2-test(*(int *)0xC0000000 = 42;)为例,它试图写入一个无效地址,我们无法阻止这种情况发生,因此,在page_fault异常处理程序内部,我们通过调用`check_read_user_ptr`函数发现0xC0000000不是有效地址,因此将进程的返回状态设置为-1,并终止进程。 其他系统调用的实现: - **halt** 由`sys_halt (intr_frame* f)`函数实现,调用`shutdown_power_off`函数即可。 ```c static void syscall_halt(struct intr_frame *f UNUSED) { shutdown_power_off(); } ``` - **exec** 由函数`sys_exec(intr_frame* f)`实现,首先会检查由`file_name`引用的文件是否有效(检查文件名指针、内存地址、页面和页面内容是否有效)。如果无效,则返回-1,否则会调用`process_execute(const char *file_name)`函数。 ```c static void syscall_exec(struct intr_frame *f) { char *cmd = *(char **)check_read_user_ptr(f->esp + ptr_size, ptr_size); check_read_user_str(cmd); f->eax = process_execute(cmd); } ``` - **create** 由函数`sys_create(struct intr_frame* f)`实现,只需调用`filesys_create`函数,并使用`acquire_lock_f()`获取锁,在完成后使用`release_lock_f()`释放它。这个锁的过程将在后续方法中用于其他文件系统操作。 ```c static void syscall_create(struct intr_frame *f) { char *file_name = *(char **)check_read_user_ptr(f->esp + ptr_size, ptr_size); check_read_user_str(file_name); unsigned file_size = *(unsigned *)check_read_user_ptr(f->esp + 2 * ptr_size, sizeof(unsigned)); lock_acquire(&filesys_lock); bool res = filesys_create(file_name, file_size); f->eax = res; lock_release(&filesys_lock); } ``` - **remove** 由函数`sys_remove(struct intr_frame* f)`实现,只需调用`filesys_remove (const char *name)`函数。 ```c static void syscall_remove(struct intr_frame *f) { char *file_name = *(char **)check_read_user_ptr(f->esp + ptr_size, ptr_size); check_read_user_str(file_name); lock_acquire(&filesys_lock); f->eax = filesys_remove(file_name); lock_release(&filesys_lock); } ``` - **open** 由函数`sys_open(struct intr_frame* f)`实现,首先需要通过`filesys_open (const char *name)`函数打开文件。然后,需要将具有结构`thread_file`的文件推送到线程的已打开文件列表`files`中。 ```c static void syscall_open(struct intr_frame *f) { char *file_name = *(char **)check_read_user_ptr(f->esp + ptr_size, ptr_size); check_read_user_str(file_name); lock_acquire(&filesys_lock); struct file *opened_file = filesys_open(file_name); lock_release(&filesys_lock); if (opened_file == NULL) { f->eax = -1; return; } struct thread *t_cur = thread_current(); struct file_entry *entry = malloc(sizeof(struct file_entry)); entry->fd = t_cur->next_fd++; entry->f = opened_file; list_push_back(&t_cur->file_list, &entry->elem); f->eax = entry->fd; } ``` - **seek** 由函数`sys_seek(struct intr_frame* f)`实现,只需调用`file_seek (struct file *file, off_t new_pos)`函数。 ```c static void syscall_seek(struct intr_frame *f) { int fd = *(int *)check_read_user_ptr(f->esp + ptr_size, sizeof(int)); unsigned pos = *(int *)check_read_user_ptr(f->esp + 2 * ptr_size, sizeof(unsigned)); struct file_entry *entry = get_file(fd);; if (entry != NULL) { lock_acquire(&filesys_lock); file_seek(entry->f, pos); lock_release(&filesys_lock); } } ``` - **tell** 由函数`sys_tell(struct intr_frame* f)`实现,首先从`find_file_id(int file_id)`中找到文件,然后调用`file_tell (struct file *file)`函数进行系统调用tell。 ```c static void syscall_tell(struct intr_frame *f) { int fd = *(int *)check_read_user_ptr(f->esp + ptr_size, sizeof(int)); struct file_entry *entry = get_file(fd);; if (entry != NULL) { lock_acquire(&filesys_lock); f->eax = file_tell(entry->f); lock_release(&filesys_lock); } else { f->eax = -1; } } ``` - **close** 由函数`sys_close(struct intr_frame* f)`实现,首先从`find_file_id(int file_id)`中找到文件,然后调用`file_close (struct file *file)`函数进行系统调用close。最后,我们从线程的文件列表中移除文件并释放文件。 ```c static void syscall_close(struct intr_frame *f) { int fd = *(int *)check_read_user_ptr(f->esp + ptr_size, sizeof(int)); struct file_entry *entry = get_file(fd); if (entry != NULL) { lock_acquire(&filesys_lock); file_close(entry->f); list_remove(&entry->elem); free(entry); lock_release(&filesys_lock); } } ``` - **filesize** 由函数`sys_filesize(struct intr_frame* f)`实现,首先从`find_file_id(int file_id)`中找到文件,然后调用`file_length (struct file *file)`函数进行系统调用filesize。 ```c static void syscall_filesize(struct intr_frame *f) { int fd = *(int *)check_read_user_ptr(f->esp + ptr_size, sizeof(int)); struct file_entry *entry = get_file(fd);; if (entry->f == NULL) { f->eax = -1; } else { lock_acquire(&filesys_lock); f->eax = file_length(entry->f); lock_release(&filesys_lock); } } ``` #### SYNCHRONIZATION >B7: The "exec" system call returns -1 if loading the new executable >fails, so it cannot return before the new executable has completed >loading. How does your code ensure this? How is the load >success/failure status passed back to the thread that calls "exec"? 在进程执行的过程中,如果进程失败,execute函数将返回-1,因为它不能继续执行。为了实现这个功能,我在结构体thread中添加了一个用于记录线程是否成功执行的变量`success`。此外,我们使用结构体thread的变量`parent`来获取其父进程,并根据加载的结果设置其状态。将子进程的执行结果记录在父进程中而不是子进程中是一个很好的设计。我们使用信号量来实现父进程等待子进程。当创建一个子进程时,它会调用`sema_down`来阻塞父进程。当子进程完成时,它会调用`sema_up`来唤醒父进程。这种方式确保了父进程能够等待子进程的完成,而不需要忙等(busy-waiting)。 >B8: Consider parent process P with child process C. How do you >ensure proper synchronization and avoid race conditions when P >calls wait(C) before C exits? After C exits? How do you ensure >that all resources are freed in each case? How about when P >terminates without waiting, before C exits? After C exits? Are >there any special cases? 在等待进程的过程中(通过信号量来实现等待),当一个父进程需要等待它的子进程时,会调用`sema_down`来阻塞父进程。当子进程完成时,父进程将会被`sema_up`的调用唤醒。这种方式确保了父进程能够等待子进程的完成,而不需要忙等。 - P在C退出之前调用wait(C): - P会调用`sema_down`,当子进程被创建并退出后,调用`sema_up`,唤醒父进程。 - P在C退出后调用wait(C): - P将获得`sema`并发现C已经退出,然后直接检查其退出状态。 - P在C退出之前没有等待而终止: - P内的列表将被释放,锁将被释放,因为除了父进程没有其他人会等待信号,所以不需要发信号通知条件。当C尝试设置其状态并发现父进程已经退出时,它将忽略它并继续执行。 - P在C退出后终止: - 对于P也会发生相同的情况,即释放P所拥有的所有资源。 #### RATIONALE >B9: Why did you choose to implement access to user memory from the >kernel in the way that you did? 我选择通过在使用内存空间之前对它的有效性进行验证,我使用了`check_read_user_ptr`这个函数。这比使用`putuser`和`getuser`函数更加简单高效。 >B10: What advantages or disadvantages can you see to your design >for file descriptors? 优点: 1. 线程结构的空间占用小。 2. 内核了解所有已打开的文件,从而增加了更灵活地操作已打开文件的能力。 缺点: 1. 占用了内核空间,用户程序可能打开大量文件以导致内核崩溃。 2. 需要额外的工作来实现父进程已打开文件的继承。 >B11: The default tid_t to pid_t mapping is the identity mapping. >If you changed it, what advantages are there to your approach? 并没有修改线程id到进程id的映射方式。 ## Denying Writes to Executables(bonus) #### DATA STRUCTURES 在<filesys.h>中添加`struct lock filesys_lock`,作为文件访问的互斥锁。 #### ALGORITHMS Pintos提供了`file_deny_write()`函数用来禁止对打开的文件进行写操作,`file_allow_write()`函数用来对文件允许写入。同时,当一个文件被关闭后也可以写入。` file_deny_write()`断言判断文件是否为空,其次将文件置为不可被写入状态并且修改该文件的索引节点内容。最后将进程当下打开的文件指针指向`file`。 在`start_process`中添加如下代码: ```c lock_acquire(&filesys_lock); struct file *f = filesys_open(proc_name); file_deny_write(f); lock_release(&filesys_lock); thread_current()->exec_file = f; ``` 第一行表示获取锁,此时只有该进程可以对文件进行修改。 第三行调用了`file_deny_write()`函数,禁止对打开的`f`指向的文件进行写操作。 第四行释放锁。 第五行将当前进程打开的文件指向`f`。 在`process_exit`中添加如下代码: ```c lock_acquire(&filesys_lock); file_close(t_cur->exec_file); lock_release(&filesys_lock); ``` 同样的,先获取锁,然后调用`file_close`关闭文件,最后释放锁。 `file_close`的代码如下: ```c void file_close (struct file *file) { if (file != NULL) { file_allow_write (file); inode_close (file->inode); free (file); } } ``` 其中调用了`file_allow_write()`函数,恢复对文件的写入权限。