Steve's
0%

CS162 Project 1: User Programs

发表于 更新于
本文字数： 10k 阅读时长 ≈ 9 分钟

这次的Project 1分为了三个小任务，分别是：

  • Argument Passing 传递参数
  • Process Control Syscalls 实现进程控制相关系统调用
  • File Operation Syscalls 实现文件操作系统调用

参数传递

首先要完成的是main函数的参数传递，有了参数传递就可以在main函数中使用argc和argv了。

参数传递的就是把程序的参数依次放到用户栈空间中，具体的栈空间如图，可以在这里找到。

按照次序把每一个参数放到栈中，然后注意一下栈对齐(对齐到16字节)，最后把argv和argc放进去。

了解了栈空间的样子后，这一部分就很好实现了。

我们主要在userprog/process.c文件中start_process修改

文件名修改

首先是考虑到诸如ls -la的情况，这时候ls是我们的程序名，所以应该先把程序名分离出来作为参数传递给load函数来读取ELF。

1
2
3
4
5
6
char *args[128];
size_t argc = 0;
char *save_ptr;
char *token = strtok_r(file_name, " ", &save_ptr);
...
success = load (token, &if_.eip, &if_.esp);

参数分离

当成功的读取可执行文件后，接下来就要把每一个参数分离出来，注意要使用strtok_r而不是strtok。

1
2
3
4
5
6
while (token != NULL)
{
    args[argc++] = token;
    token = strtok_r(NULL, " ", &save_ptr);
}
args[argc] = NULL;

注意argv[argc]应该为NULL。

参数复制

然后把argv依次复制到用户栈空间中，注意复制的长度应该为字符串长度+1(末尾的\0).

1
2
3
4
5
6
7
8
9
size_t len;
int i;
for (i = argc-1; i >= 0; i--)
{
    len = strlen(args[i]);
    if_.esp -= len + 1;
    memcpy(if_.esp, args[i], len+1);
    args[i] = (char *)if_.esp;  //save stack args address
}

if_就是一个interrupt frame，因为我们要假装是从一个中断返回到程序中，这样就可以恢复程序的eip、esp等。

栈对齐

接下来我们来处理栈空间对齐的问题，需要注意的是栈空间是16字节，同时看上边的那张图中，是argc的地址对齐到16字节。

1
2
3
4
5
while ((uint32_t)(if_.esp - sizeof(char **)*(argc+1) - 2*sizeof(void *)) % 16 != 0)
{
    if_.esp -= 1;
    *((uint8_t *) if_.esp) = (uint8_t)0;
}

这就是为什么if_.esp后边还需要减去那一堆东西。

入栈

下边没什么好说的，依次放进栈就好了.

1
2
3
4
5
6
7
8
9
10
11
12
for (i = argc; i >= 0; i--)
{
    if_.esp -= sizeof(char **);
    *((char **)if_.esp) = args[i];
}
if_.esp -= sizeof(char **);
*((char ***) if_.esp) = if_.esp + sizeof(char **);  // argv
if_.esp -= sizeof(int);
memcpy(if_.esp, &argc, sizeof(size_t));             // argc
if_.esp -= sizeof(void (*)());
typedef void (*ret_func)();
*((ret_func *) if_.esp) = NULL;                     // return adress (NULL)

至此argument passing和stack align的几个测试点是可以过的。

进程相关系统调用

系统调用流程

我打算把exec和wait放到最后来说，所以这里先实现halt和practice，我们先来研究下一个用户程序是怎么调用syscall的。

首先是在用户态下的lib/user/syscall.c中，使用了一些内嵌汇编来把系统调用的参数入栈，并且调用0x30中断。

0x30中断的处理程序在userprog/syscall.c中，syscall_init中向系统注册了中断，使用syscall_handler来处理。

syscall_handler中，使用interrupt frame中的esp来访问用户栈。我们可以通过args来访问系统调用的参数，同时我们把参数返回值放到eax寄存器中。

参数验证

但是注意，我们现在是在内核态，用户传来的参数很有可能是有问题的，所以我们需要验证一下用户的参数，确保用户的参数是在用户的空间内，并且是处于已经分配的page。

这里实现了三个函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void vaild_uaddr(void *uaddr) {
  if (!is_user_vaddr(uaddr) || !pagedir_get_page(thread_current()->pagedir, uaddr) )
    syscall_exit(-1);
}

void vaild_ptr(void *ptr, size_t size) {
  vaild_uaddr(ptr);
  vaild_uaddr(ptr+size-1);
}

void vaild_str(char *ptr) {
  vaild_uaddr((void *)ptr);
  void *kaddr = pagedir_get_page(thread_current()->pagedir, ptr);
  vaild_ptr((void *)ptr, sizeof(char)*(strlen(kaddr)+1));
}
  • vaild_uaddr是用来验证参数是否在用户空间内，并且page已经分配。
  • vaild_ptr是验证一段内存是否都在用户空间内。
  • vaild_str是验证一个字符串，注意我们不能在用户给的字符串地址上使用strlen，因为很可能用户给的字符串在遇到\0之前就已经超出了用户空间或者是未分配的page。

halt和practice

有了上边的铺垫，实现这两个syscall就轻而易举了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static void
syscall_handler (struct intr_frame *f)
{
  uint32_t* args = ((uint32_t*) f->esp);
  vaild_uaddr(args);
  vaild_ptr(args, sizeof(void *));

  switch (args[0])
    {
      case SYS_HALT:
        shutdown_power_off();
        break;
      case SYS_PRACTICE:
        vaild_ptr(&args[1], sizeof(uint32_t));
        f->eax = syscall_practice(args[1]);
        break;
    }
}

int
syscall_practice (uint32_t i) {
  return i+1;
}

文件操作相关系统调用

对于文件的操作并不是很难，但是要考虑到同步的问题，我们不希望看到两个线程同时读取同一个文件，所以简单粗暴加上一个全局文件锁就完事了。

添加file_elem

我们需要在userprog/thread.h中对线程结构进行一些修改，把每个线程的文件分开。

1
2
3
4
5
6
7
8
9
10
11
12
struct thread {
    ...
    struct list file_list;
    int fd_count;
    struct lock file_list_lock;
}

struct file_elem {
  int fd;
  struct file *file;
  struct list_elem elem;
};

file_elem是一个列表项，记录了一个程序每个打开文件的file descriptor和struct *file。

同时需要在thread初始化的时候初始化一下file_list和fd_count，在init_thread中

1
2
3
4
5
6
7
8
9
10
static void
init_thread (struct thread *t, const char *name, int priority)
{
    ...
    //File
    list_init(&t->file_list);
    t->fd_count = 2;
    lock_init(&t->file_list_lock);
    ...
}

syscall

实现syscall就比较简单了，这里就放一个例子，其他的同理

userprog/syscall.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
struct lock file_lock;

struct file_elem *get_file_by_fd(int fd) {
  struct thread *current_thread = thread_current();
  struct list_elem *e;

  lock_acquire(&current_thread->file_list_lock);
  for (e = list_begin(&current_thread->file_list); e != list_end(&current_thread->file_list); e = list_next(e)) {
    struct file_elem *fe = list_entry(e, struct file_elem, elem);
    if (fe->fd == fd) {
      lock_release(&current_thread->file_list_lock);
      return fe;
    }
  }
  lock_release(&current_thread->file_list_lock);
  return NULL;
}

int
syscall_open (char *filename) {
  struct thread *current_thread = thread_current();

  lock_acquire(&file_lock);
  struct file *fi = filesys_open(filename);  
  lock_release(&file_lock);

  if (fi != NULL) {
    struct file_elem *fe = malloc(sizeof(struct file_elem));
    fe->file = fi;

    lock_acquire(&current_thread->file_list_lock);
    fe->fd = current_thread->fd_count;
    current_thread->fd_count++; //need lock
    list_push_front(&current_thread->file_list, &fe->elem);
    lock_release(&current_thread->file_list_lock);

    return fe->fd;
  }
  return -1;
}

注意在syscall_handler中要验证一下文件名这个字符串

1
2
3
4
5
case SYS_OPEN:
    vaild_ptr(&args[1], sizeof(uint32_t));
    vaild_str((char *)args[1]);
    f->eax = syscall_open((char *)args[1]);
    break;

exec和wait(还有exit)

要实现exec和wait，首先要对thread进行一些修改

修改thread

1
2
3
4
5
6
7
8
struct thread {
    bool load_success;                  /* Binary load success. */
    struct semaphore load_sema;         /* Load semaphore. */
    struct thread *parent;              /* Parent list. */
    struct list child_list;             /* Child list. */

    struct child_process *waiting_child;
}
  • load_succecc是本进程是否加载完毕的标记
  • load_sema是加载完毕的semaphore，因为我们需要确定程序是否正确的加载才能返回exec
  • parent不解释
  • child_list是子进程的list
1
2
3
4
5
6
7
struct child_process {
   tid_t tid;
   int exit_status;
   bool is_exit;
   struct semaphore wait_sema;
   struct list_elem child_elem;
};

在子进程的struct中需要记录一下exit_status来传递给父进程的wait。wait_sema是一个子进程

同样的，我们也需要在进程的初始化中对新增加的几个成员进行初始化

1
2
3
4
5
6
7
8
9
10
11
static void
init_thread (struct thread *t, const char *name, int priority)
{
    ...
    //Child
    t->waiting_child = NULL;
    list_init(&t->child_list);
    t->parent = running_thread();
    sema_init(&t->load_sema, 0);
    ...
}

并且添加了一个辅助函数帮助使用tid来查找子进程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct child_process *find_child_thread(tid_t child_tid) {
  struct thread *current_thread = thread_current();

  struct child_process *cp;
  struct list_elem *elem;

  for (elem = list_begin(&current_thread->child_list); elem != list_end(&current_thread->child_list); elem = list_next(elem)) {
    cp = list_entry(elem, struct child_process, child_elem);
    if (cp->tid == child_tid)
      return cp;
  }

  return NULL;
}

exec

我们先处理一下加载成功的问题，在start_procsess中，添加上加载成功后修改flag

1
2
3
4
5
6
7
8
9
static void
start_process (void *file_name_)
{
  ...
  struct thread *current_thread = thread_current();
  current_thread->parent->load_success = success;
  sema_up(&current_thread->parent->load_sema);
  ...
}

在process_execute中添加上等待sema

1
2
3
4
5
6
7
8
9
10
11
12
13
14
tid_t
process_execute (const char *file_name)
{
    ...
    tid = thread_create (thread_name, PRI_DEFAULT, start_process, fn_copy);
    free(thread_name);
    if (tid == TID_ERROR)
        palloc_free_page (fn_copy);
    else {
        sema_down(&current_thread->load_sema);
    if (!current_thread->load_success)
        return -1;
  }
}

这样就可以去实现syscall_exec了

1
2
3
4
5
6
7
8
tid_t
syscall_exec (const char *file) {
  tid_t tid =  process_execute(file);
  if (thread_current()->load_success && tid != TID_ERROR)
    return tid;
  else
    return -1;
}

exit与wait

当我们需要wait一个子线程的时候，我们等待子线程的wait_sema

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int
process_wait (tid_t child_tid)
{
  struct thread *current_thread = thread_current();

  enum intr_level old_level = intr_disable(); 
  struct child_process *cp = find_child_thread(child_tid);
  intr_set_level(old_level);
  
  if (!cp)
    return -1;
  
  current_thread->waiting_child = cp;

  if (!cp->is_exit)
    sema_down(&cp->wait_sema);

  list_remove(&cp->child_elem);

  return cp->exit_status;
}

同时我们也需要修改下进程退出的逻辑，需要在thread_exit中设置下wait_sema

1
2
3
4
5
6
7
8
9
10
11
12
13
void
thread_exit (void)
{
  ...
  enum intr_level old_level = intr_disable();
  if (thread_current()->parent->waiting_child != NULL) {
    if (thread_current()->parent->waiting_child->tid == thread_current()->tid) {
      sema_up(&thread_current()->parent->waiting_child->wait_sema);
    }
  }
  intr_set_level(old_level);
  ...
}

这样就可以去实现exec和exit了

1
2
3
4
5
6
7
8
tid_t
syscall_exec (const char *file) {
  tid_t tid =  process_execute(file);
  if (thread_current()->load_success && tid != TID_ERROR)
    return tid;
  else
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int
syscall_exit (uint32_t status) {
  printf ("%s: exit(%d)\n", &thread_current ()->name, status);

  struct thread *current_thread = thread_current();
  struct child_process *cp;
  struct list_elem *elem;

  enum intr_level old_level = intr_disable();
  for (elem = list_begin(&current_thread->parent->child_list); elem != list_end(&current_thread->parent->child_list); elem = list_next(elem)) {
    cp = list_entry(elem, struct child_process, child_elem);
    if (cp->tid == current_thread->tid) {
      cp->is_exit =  true;
      cp->exit_status = status;
    }
  }
  intr_set_level(old_level);

  thread_exit ();
  return status;
}

当线程退出的时候我们把exit_status保存一下，并记录下子进程已经退出。

杂项

rox

当一个进程正在执行的时候，我们需要保证没有人可以改变ELF文件，所以需要在load中进行一些修改，

1
2
3
4
5
6
7
8
9
10
11
12
bool
load (const char *file_name, void (**eip) (void), void **esp)
{
    ...
    file_deny_write(file);
    thread_current()->exe_file = file;
 done:
    if (file == NULL)
        file_close(file);
    /* We arrive here whether the load is successful or not. */
    return success;
}

同时在进程退出之后需要恢复

1
2
3
4
5
6
7
8
9
10
void
process_exit (void)
{
    ...
    if (cur->exe_file != NULL) {
        file_allow_write(cur->exe_file);
        file_close(cur->exe_file);
    }
    ...
}

错误退出

当一个用户线程因为page fault而退出的时候，我们需要让这个进程退出

在userprog/exception.c中

1
2
3
4
5
6
7
8
static void
page_fault (struct intr_frame *f)
{
    ...
    if (user)
        syscall_exit(-1);
    ...
}

退出的时候文件关闭

最后发现有个multi-oom的测试点总是过不去，在这个程序中exec出来很多层子进程，并且每个子进程都执行一些打开文件的操作。最终发现原来是当线程退出的时候并没有关闭打开的文件，所以在syscall_exit中添加关闭文件的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int
syscall_exit (uint32_t status) {
    printf ("%s: exit(%d)\n", &thread_current ()->name, status);

    struct thread *current_thread = thread_current();
    struct child_process *cp;
    struct list_elem *elem, *prev;

    lock_acquire(&file_lock);
    for(elem = list_begin(&thread_current()->file_list); elem != list_end(&thread_current()->file_list);) {
        struct file_elem *fe = list_entry(elem, struct file_elem,  elem);
        file_close(fe->file);
        elem = list_next(elem);
        free(fe);
    }
    lock_release(&file_lock);
    ...
}

Final

最终88个测试点全部通过