This page looks best with JavaScript enabled

MIT 6.S081 操作系统 课后实验笔记

 ·  ☕ 7 min read

实验环境搭建

课程主页:MIT 6.S081 Operating System

最开始make qemu报错,提示我没有 riscv64 版本的 binutils:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
> make qemu
***
*** Error: Couldn't find a riscv64 version of GCC/binutils.
*** To turn off this error, run 'gmake TOOLPREFIX= ...'.
***
gcc    -c -o kernel/entry.o kernel/entry.S
kernel/entry.S: Assembler messages:
kernel/entry.S:11: Error: no such instruction: `la sp,stack0'
kernel/entry.S:12: Error: no such instruction: `li a0,1024*4'
kernel/entry.S:13: Error: no such instruction: `csrr a1,mhartid'
kernel/entry.S:14: Error: no such instruction: `addi a1,a1,1'
kernel/entry.S:15: Error: too many memory references for `mul'
kernel/entry.S:16: Error: too many memory references for `add'
kernel/entry.S:20: Error: no such instruction: `j spin'
make: *** [<builtin>: kernel/entry.o] Error 1

ArchLinux 这样安装相关依赖,其他系统参考: 6.S081 tools / Fall 2020

1
sudo pacman -S riscv64-linux-gnu-binutils riscv64-linux-gnu-gcc riscv64-linux-gnu-gdb qemu-arch-extra

当我执行 make qemu之后:

1
2
3
4
> make qemu
qemu-system-riscv64 -machine virt -bios none -kernel kernel/kernel -m 128M -smp 3 -nographic -drive file=fs.img,if=none,format=raw,id=x0 -device virtio-blk-device,drive=x0,bus=virtio-mmio-bus.0
qemu-system-riscv64: error while loading shared libraries: liburing.so.1: cannot open shared object file: No such file or directory
make: *** [Makefile:209: qemu] Error 127

提示我没有liburing.so.1, 检查了我安装的 liburing 是 2.0.0 版本的,所以降级liburing即可
再次 执行 make qemu 终于进入xv6的交互界面了

Unix Utils

sleep

Implement the UNIX program sleep for xv6; your sleep should pause for a user-specified number of ticks. A tick is a notion of time defined by the xv6 kernel, namely the time between two interrupts from the timer chip. Your solution should be in the file user/sleep.c.
xv6实现 sleep命令

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#include "user/user.h"
int main(int argc, char* argv[]){
    if (argc != 2){
        fprintf(2, "usage: grep sleep [duration]\n");
        exit(1);
    }

    int duration = atoi(argv[1]);
    sleep(duration);
    exit(0);
}

pingpong

Write a program that uses UNIX system calls to ‘‘ping-pong’’ a byte between two processes over a pair of pipes, one for each direction. The parent should send a byte to the child; the child should print “: received ping”, where is its process ID, write the byte on the pipe to the parent, and exit; the parent should read the byte from the child, print “: received pong”, and exit. Your solution should be in the file user/pingpong.c.

利用管道和fork()xv6 实现pingpong命令,我使用了一对 pipe

 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
#include "kernel/types.h"
#include "user/user.h"

int main(int argc, char *argv[]) {
    int p2c[2];
    int c2p[2];
    if (pipe(p2c) != 0 || pipe(c2p) != 0) {
        fprintf(2, "faield to create pipe\n");
        exit(1);
    }
    const int ball = 0;
    int buf;

    int f = fork();
    if (f == -1) {
        fprintf(2, "failed to create child process\n");
        exit(1);
    }
    if (f == 0) {
        close(p2c[0]);
        printf("%d: received ping\n", getpid());

        write(c2p[1], &ball, 1);
        close(c2p[1]);
        read(p2c[0], &buf, 1);
    } else {
        write(p2c[1], &ball, 1);
        close(p2c[1]);

        read(c2p[0], &buf, 1);
        close(c2p[0]);
        printf("%d: received pong\n", getpid());
    }
    exit(0);
}

primes

sample

Your goal is to use pipe and fork to set up the pipeline. The first process feeds the numbers 2 through 35 into the pipeline. For each prime number, you will arrange to create one process that reads from its left neighbor over a pipe and writes to its right neighbor over another pipe. Since xv6 has limited number of file descriptors and processes, the first process can stop at 35.

题目要求已经说的很明确了,需要用fork来创造多个子进程来筛选来自父进程的管道里的数字流。
并且父进程需要系统调用:wait 来等待子进程筛选完所有的素数之后才可以退出。
使用递归,代码如下:

 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include "kernel/types.h"
#include "user/user.h"

void prime_sieve(int readPip) {
    int buf;
    int pp[2];
    if (pipe(pp) != 0) {
        fprintf(2, "failed to create pipe \n");
        exit(1);
    }
    int first = 2;
    int count = 0;
    while (read(readPip, &buf, 1) == 1) {
        if (count == 0) {
            count++;
            first = buf;
            printf("prime %d\n", buf);
        } else {
            if (buf % first != 0) {
                write(pp[1], &buf, 1);
                count++;
            }
        }
    }
    close(readPip);
    close(pp[1]);

    if (count <= 1) {
        exit(0);
    }

    int f = fork();
    if (f == -1) {
        fprintf(2, "failed to create child process\n");
        exit(1);
    }
    if (f == 0) {
//        sleep(10);
        prime_sieve(pp[0]);
    } else {
//        printf("%d read %d have done, waiting for %d\n", getpid(),count, f);
        wait(&f);
    }
}

int main(int argc, char *argv[]) {
    int pp[2];
    if (pipe(pp) != 0) {
        fprintf(2, "failed to create pipe \n");
        exit(1);
    }
    for (int i = 2; i <= 35; i++) {
        write(pp[1], &i, 1);
    }
    close(pp[1]);
    prime_sieve(pp[0]);
    exit(0);
}

find

Write a simple version of the UNIX find program: find all the files in a directory tree with a specific name.

Your solution is correct if produces the following output (when the file system contains the files b and a/b):

    $ make qemu
    ...
    init: starting sh
    $ echo > b
    $ mkdir a
    $ echo > a/b
    $ find . b
    ./b
    ./a/b
    $ 
  

我复用了ls.c里的fmtname,稍微改了改,因为ls.c里面的fmtname返回的字符串可能会包含空格后缀。
find里要注意不要在...目录下递归查找了。

 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"

char *fmtname(char *path) {
    static char buf[DIRSIZ + 1];
    char *p;

    // Find first character after last slash.
    for (p = path + strlen(path); p >= path && *p != '/'; p--);
    p++;

    // Return blank-padded name.
    if (strlen(p) >= DIRSIZ)
        return p;
    memmove(buf, p, strlen(p));
    memset(buf + strlen(p), ' ', DIRSIZ - strlen(p));
    if (strlen(buf) == 0) return buf;
    for (int i = strlen(buf) - 1; i > 0; i--) {
        if (buf[i - 1] != ' ') {
            buf[i] = '\0';
            return buf;
        }
    }
    return buf;
}

void find(char *path, char *pattern) {
    char buf[512], *p;
    int fd;
    struct dirent de;
    struct stat st;

    if ((fd = open(path, 0)) < 0) {
        fprintf(2, "ls: cannot open %s\n", path);
        return;
    }

    if (fstat(fd, &st) < 0) {
        fprintf(2, "ls: cannot stat %s\n", path);
        close(fd);
        return;
    }

    switch (st.type) {
        case T_FILE:
            if (strcmp(pattern, fmtname(path)) == 0) {
                printf("%s\n", fmtname(path));
            }
            break;

        case T_DIR:
            if (strlen(path) + 1 + DIRSIZ + 1 > sizeof buf) {
                printf("ls: path too long\n");
                break;
            }
            strcpy(buf, path);
            p = buf + strlen(buf);
            *p++ = '/';
            while (read(fd, &de, sizeof(de)) == sizeof(de)) {
                if (de.inum == 0)
                    continue;
                if (strcmp(de.name, ".") == 0 || strcmp(de.name, "..") == 0)
                    continue;

                memmove(p, de.name, DIRSIZ);
                p[DIRSIZ] = 0;
                if (stat(buf, &st) < 0) {
                    printf("ls: cannot stat %s\n", buf);
                    continue;
                }

                if (st.type == T_DIR) {
                    find(buf, pattern);
                } else {
                    if (strcmp(pattern, fmtname(buf)) == 0) {
                        printf("%s\n", buf);
                    }
                }
            }
            break;
    }
    close(fd);
}


int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(2, "usage: find [path] [patten]\n");
        exit(1);
    }
    char *path = argv[1];
    char *pattern = argv[2];
    find(path, pattern);
    exit(0);
}

xargs

xargs是我很喜欢的命令,关于xargs的实验的第一个要求是要能完成这样的功能:

1
2
    $ echo hello too | xargs echo bye
    bye hello too

提示中指出:使用系统调用fork()配合exec(),并使用wait来让父进程等待子进程结束。

 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
41
42
43
#include "kernel/types.h"
#include "user/user.h"

int main(int argc, char *argv[]) {
    char c;
    char buf[512];
    uint bi = 0;
    char *xv[128];
    int count = 0;
    for (int i = argc - 2; i < argc; i++) {
        xv[count] = argv[i];
        count++;
    }
    while (read(0, &c, 1) == 1) {
        if (c == ' ' || c == '\n') {
            count++;
            char *tmp = malloc(bi + 2);
            memcpy(tmp, buf, bi + 1);
            tmp[bi + 1] = '\0';
            xv[count - 1] = tmp;
            bi = 0;

            if (c == '\n') {
                int f = fork();
                if (f < 0) {
                    fprintf(2, "failed create child process\n");
                    exit(1);
                }
                if (f == 0) {
                    exit(exec(argv[1], xv));
                } else {
                    wait(&f);
                }
                bi = 0;
                count = 0;
            }
        } else {
            buf[bi] = c;
            bi++;
        }
    }
    exit(0);
}

实验要求的任务就是这些了。但是 unix utils 这一章还有一些扩展实验:

Unix utils: Optional challenge exercises

  1. Write an uptime program that prints the uptime in terms of ticks using the uptime system call. (easy)
  2. Support regular expressions in name matching for find. grep.c has some primitive support for regular expressions. (easy)
  3. The xv6 shell (user/sh.c) is just another user program and you can improve it. It is a minimal shell and lacks many features found in real shell. For example, modify the shell to not print a $ when processing shell commands from a file (moderate), modify the shell to support wait (easy), modify the shell to support lists of commands, separated by “;” (moderate), modify the shell to support sub-shells by implementing “(” and “)” (moderate), modify the shell to support tab completion (easy), modify the shell to keep a history of passed shell commands (moderate), or anything else you would like your shell to do. (If you are very ambitious, you may have to modify the kernel to support the kernel features you need; xv6 doesn’t support much.)

System Call

这章的实验是系统调用相关的。

trace

In this assignment you will add a system call tracing feature that may help you when debugging later labs. You’ll create a new trace system call that will control tracing. It should take one argument, an integer “mask”, whose bits specify which system calls to trace. For example, to trace the fork system call, a program calls trace(1 « SYS_fork), where SYS_fork is a syscall number from kernel/syscall.h. You have to modify the xv6 kernel to print out a line when each system call is about to return, if the system call’s number is set in the mask. The line should contain the process id, the name of the system call and the return value; you don’t need to print the system call arguments. The trace system call should enable tracing for the process that calls it and any children that it subsequently forks, but should not affect other processes.
trace 要求我们打印出命令执行过程中使用到的系统调用,并且要求fork()出的子进程也要打印出trace 信息;
那么,我将用户空间传来的tracemask 使用argint()来获取。
并且,在 struct proc 里放入 tracemask 字段:

1
2
3
4
5
6
7
// Per-process state
struct proc {
  ... // 省略

  int tracemask;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
void
syscall(void)
{
  int num;
  struct proc *p = myproc();

  num = p->trapframe->a7;
  if(num > 0 && num < NELEM(syscalls) && syscalls[num]) {
    p->trapframe->a0 = syscalls[num]();
    if (num > 0 && ((1<<num) & p->tracemask)){
        printf("%d: %s %d\n",p->pid,syscallcnames[num],p->trapframe->a0);
    }
  } else {
    printf("%d %s: unknown sys call %d\n",
            p->pid, p->name, num);
    p->trapframe->a0 = -1;
  }
}

然后在系统调用的调用函数里, 加上打印系统调用的判断条件。

 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
41
42
43
44
static char *syscallcnames[] = {
        [SYS_fork]    "fork",
        [SYS_exit]    "exit",
        [SYS_wait]    "wait",
        [SYS_pipe]    "pipe",
        [SYS_read]    "read",
        [SYS_kill]    "kill",
        [SYS_exec]    "exec",
        [SYS_fstat]   "fstat",
        [SYS_chdir]   "chdir",
        [SYS_dup]     "dup",
        [SYS_getpid]  "getpid",
        [SYS_sbrk]    "sbrk",
        [SYS_sleep]   "sleep",
        [SYS_uptime]  "uptime",
        [SYS_open]    "open",
        [SYS_write]   "write",
        [SYS_mknod]   "mknod",
        [SYS_unlink]  "unlink",
        [SYS_link]    "link",
        [SYS_mkdir]   "mkdir",
        [SYS_close]   "close",
        [SYS_trace]   "trace",
        [SYS_sysinfo] "sysinfo",
};

void
syscall(void)
{
  int num;
  struct proc *p = myproc();

  num = p->trapframe->a7;
  if(num > 0 && num < NELEM(syscalls) && syscalls[num]) {
    p->trapframe->a0 = syscalls[num]();
    if (num > 0 && ((1<<num) & p->tracemask)){
        printf("%d: %s %d\n",p->pid,syscallcnames[num],p->trapframe->a0);
    }
  } else {
    printf("%d %s: unknown sys call %d\n",
            p->pid, p->name, num);
    p->trapframe->a0 = -1;
  }
}

sysinfotest

sysinfotest 要求编写sysinfo 这个系统调用,拿到系统的非UNUSED 状态的进程数量,和空闲内存数值

1
2
3
4
struct sysinfo {
  uint64 freemem;   // amount of free memory (bytes)
  uint64 nproc;     // number of process
};

我在 kalloc.c 中为 kmem 增加了 freemem 字段。

1
2
3
4
5
struct {
  struct spinlock lock;
  struct run *freelist;
  uint64 freemem;
} kmem;

kfree() 中, 我添加了freemem 的自增命令, 在 kalloc() 增加freemem 的自减命令, 还有 kfreemem() 用来返回系统的空闲内存数量;

 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
41
42
43
44
45
46
void
kfree(void *pa)
{
  struct run *r;

  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");

  // Fill with junk to catch dangling refs.
  memset(pa, 1, PGSIZE);

  r = (struct run*)pa;

  acquire(&kmem.lock);
  r->next = kmem.freelist;
  kmem.freelist = r;
  kmem.freemem++;
  release(&kmem.lock);
}
void
kfree(void *pa)
{
  struct run *r;

  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");

  // Fill with junk to catch dangling refs.
  memset(pa, 1, PGSIZE);

  r = (struct run*)pa;

  acquire(&kmem.lock);
  r->next = kmem.freelist;
  kmem.freelist = r;
  kmem.freemem++;
  release(&kmem.lock);
}
uint64 kfreemem(){
  uint64 ret = 0;
  acquire(&kmem.lock);
  ret = kmem.freemem;
  release(&kmem.lock);
  return ret;
}

proc.c 中增加 process_count() 函数,来返回系统非UNUSED 状态的进程数量:

1
2
3
4
5
6
7
8
9
int process_count(){
    int count = 0;
    for(struct proc *p = proc; p < &proc[NPROC]; p++) {
        if (p->state != UNUSED)
            count++;
    }
    return count;
}

最后,sys_sysinfo():
要注意:拿到用户空间传来的地址后,要先用fetchaddr()看看这个地址是不是合法的

uint64
sys_sysinfo(void)
{
  uint64 uAddr = 0;
  if (argaddr(0, &uAddr) < 0) {
    return -1;
  }
  uint64 addr=0;
  if (fetchaddr(uAddr,&addr) != 0){
    return -1;
  }
  struct proc *p = myproc();

  struct sysinfo sinfo;
  sinfo.nproc = process_count();
  sinfo.freemem = kfreemem() * PGSIZE;
  printf("%d %d\n",sinfo.nproc,sinfo.freemem);

  copyout(p->pagetable, uAddr, (char *)&sinfo, sizeof(struct sysinfo));
  return 0;
}

Optional challenge exercises

  • Print the system call arguments for traced system calls (easy).
  • Compute the load average and export it through sysinfo(moderate).

Page Tables

阅读 xv6 book 第三章。

Share on

EXEC
WRITTEN BY
EXEC
Evil EXEC