Lab1 Xv6 and Unix utilities

开学！

启动 xv6

git

git clone git://g.csail.mit.edu/xv6-labs-2022

# 查看 git 日志
git status
git log

# 用于获取实验所需文件
git checkout util

# 当完成一个实验并想要检记录进度可使用 git commit
git commit -am 'my solution for util lab exercise 1

# 查看相比上一次 commit 的变化
git diff

# 查看相比最初的变化
git diff origin/util

建立并运行 xv6

• make qemu

  • 第一步就出错了。。。

    • Error: Couldn't find a riscv64 version of GCC/binutils.
    • 缺少 RISC-V 相关的 GCC/binutils
    • 搜索 binutils apt search binutils | grep riscv64
    • 安装第一个即可
    • sudo apt install binutils-riscv64-linux-gnu

  • 接着是另一个报错

    • riscv64-linux-gnu-gcc -c -o kernel/entry.o kernel/entry.S
    • make: riscv64-linux-gnu-gcc: No such file or directory
    • make: *** [\<builtin\>: kernel/entry.o] Error 127
    • 安装对应的 gcc sudo apt install gcc-10-riscv64-linux-gnu
    • 进入 /usr/bin 目录，建立软链接
    • sudo ln -s riscv64-linux-gnu-gcc-10 riscv64-linux-gnu-gcc

  • 后面又是缺少什么文件，去翻了翻 lab 介绍，发现已经给了工具链接 lab tools page

    • sudo apt-get install git build-essential gdb-multiarch qemu-system-misc gcc-riscv64-linux-gnu binutils-riscv64-linux-gnu
    • 这里的 gcc-riscv64-linux-gnu 下载的是 gcc-11，要再下回 gcc-10，不然会报错
    • sudo apt install gcc-10-riscv64-linux-gnu
    • cd /usr/bin; sudo ln -s riscv64-linux-gnu-gcc-10 riscv64-linux-gnu-gcc
    • 结果一气呵成~

里面有一些很基本的命令

xv6 kernel is booting

hart 1 starting
hart 2 starting
init: starting sh

$ ls
.              1 1 1024
..             1 1 1024
README         2 2 2227
xargstest.sh   2 3 93
cat            2 4 32832
echo           2 5 31728
forktest       2 6 15680
grep           2 7 36176
init           2 8 32152
kill           2 9 31712
ln             2 10 31520
ls             2 11 34728
mkdir          2 12 31784
rm             2 13 31768
sh             2 14 53960
stressfs       2 15 32496
usertests      2 16 181776
grind          2 17 47696
wc             2 18 33832
zombie         2 19 31168
console        3 20 0

-甚至都没有 clear

Ctrl-p 打印进程信息

Ctrl-a x 退出 qemu

结论：做任何事之前先看介绍

成绩测试

# 测试所有实验
make grade

# 测试一个程序
./grade-lab-util name
# 或
make GRADEFLAGS=name grade

sleep

在 bash 中测试，能够多参数且如果一个参数错误就不执行

user/sleep.c

#include "kernel/types.h"
#include "user/user.h"

int isDigitStr(char *str) {
    for(int i = 0; i < strlen(str); i++) {
        if(str[i] < '0' || str[i] > '9') {
            return 0;
        }
    }
    
    return 1;
}

int main(int argc, char *argv[]) {
    int status = 0;
    if(argc == 1) {
        printf("sleep: missing operand\n");
        status = -1;
    }

    for(int i = 1; i < argc && !status; i++) {
        if(!isDigitStr(argv[i])) {
            printf("sleep: invalid time interval\n");
            status = -1;
        }
    }

    for(int i = 1; i < argc && !status; i++) {
        sleep(atoi(argv[i]));
    }

    exit(status);
}

源代码放在 user 目录下，每次写完一个程序在 Makefile 中的 UPROGS 下添加一行 $U/_sleep\

然后 make qemu 编译运行

之后可以在 qemu 外运行 /grade-lab-util sleep 进行单项测试

$ ./grade-lab-util sleep
make: 'kernel/kernel' is up to date.
== Test sleep, no arguments == sleep, no arguments: OK (1.5s)
== Test sleep, returns == sleep, returns: OK (0.6s)
== Test sleep, makes syscall == sleep, makes syscall: OK (1.0s)

pingpong

简单题

父进程发送子进程一个字节，子进程收到后再给父进程一个字节

user/pingpong.c

#include "kernel/types.h"
#include "user/user.h"

int main(int argc, char *argv[]) {
    int pid, p[2];

    pipe(p);
    pid = fork();
    if(pid == 0) {
        if(read(p[0], 0, 1)) {
            pid = getpid();
            printf("%d: received ping\n", pid);
            write(p[1], "L", 1);
            exit(0);
        }
    } else {
        write(p[1], "H", 1);
        if(read(p[0], 0, 1)) {
            pid = getpid();
            printf("%d: received pong\n", pid);
        }
        exit(0);
    }

    exit(-1);
}

primes

有点难度，想了好久，感觉是要用递归，但是没想出来怎么写

想到在看网课的时候，进入子进程先把 close(0)，然后 dup(p[1])，也就是把子进程的标准输入改为管道的输入了，这样就容易写递归了

每次只输出接收到的第一个数，它必然是素数

当从输入接收不到 prime 的时候 exit(0)

这里注意 dup(p[1]) 后要把管道都给关了

user/primes.c

#include "kernel/types.h"
#include "user/user.h"

void printPrime(int prime);
void primes(int start);

int main(int argc, char *argv[]) {
    primes(1);
    exit(-1);
}

void printPrime(int prime) {
    printf("prime %d\n", prime);
}

void primes(int start) {
    int prime = 2;
    int n, pid, p[2];

    if(!start && read(0, &prime, sizeof(prime)) == 0) {
        exit(0);
    }
    printPrime(prime);

    pipe(p);
    pid = fork();
    if(pid == 0) {
        // p[0] => stdin
        close(0);
        dup(p[0]);
        close(p[0]);

        // do not need p[1]
        close(p[1]);

        primes(0);
        exit(0);
    } else {
        if(start == 1) {
            for(int i = 3; i <= 35; i++) {
                if(i % prime != 0) {
                    write(p[1], &i, sizeof(i));
                }
            }
        } else {
            while(read(0, &n, sizeof(n))) {
                if(i % prime != 0) {
                    write(p[1], &n, sizeof(n));
                }
            }
        }
        close(p[1]);

        // wait for child process
        int status;
        wait(&status);
        exit(status);
    }
}

find

同样也是递归，从目录里查找文件可以参考 ./user/ls.c

当找的是文件或者时比较名字

当找的是目录时，从 fd 读取 struct dirent[]，表示目录下的每个文件，里面有 name，表示文件名，注意过滤 . 和 ..

user/find.c

#include "kernel/types.h"
#include "kernel/fcntl.h"
#include "kernel/stat.h"
#include "kernel/fs.h"
#include "user/user.h"

int find(char *path, char *filename);

int main(int argc, char *argv[]) {
    if(argc != 3) {
        printf("find: invalid arguments\n");
    }

    int status = find(argv[1], argv[2]);
    exit(status);
}

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

    if((fd = open(path, O_RDONLY)) < 0) {
        printf("find: cannot open %s\n", path);
        return -1;
    }

    if(fstat(fd, &st) < 0) {
        printf("find: cannot stat %s\n", path);
        close(fd);
        return -1;
    }

    switch (st.type) {
        case T_DEVICE:
        case T_FILE:
            name = path;
            // get position of filename
            for(int i = strlen(path) - 1; i >= 0; i--) {
                if(path[i] == '/') {
                    name = &path[i+1];
                    break;
                }
            }
            if(!strcmp(name, filename)) {
                printf("%s\n", path);
            }
            break;

        // if path is directory
        case T_DIR:
            if(strlen(path)+1+DIRSIZ+1 > sizeof(buf)) {
                printf("find: path too long\n");
                close(fd);
                return -1;
            }
            strcpy(buf, path);
            p = buf + strlen(buf);
            *p++ = '/';
            while(read(fd, &de, sizeof(de)) == sizeof(de)) {
                // excpet for "." and ".."
                if(de.inum == 0 || !strcmp(de.name, ".") || !strcmp(de.name, "..")) {
                    continue;
                }
                memmove(p, de.name, DIRSIZ);
                p[DIRSIZ] = '\0';
                find(buf, filename);
            }
            break;
    }
    
    close(fd);
    return 0;
}

xargs

一开始没懂 sh 怎么实现管道

测试发现就是将管道的读端作为 | 右边程序的标准输入

主要是判断什么时候跳出循环

user/xargs.c

#include "kernel/types.h"
#include "kernel/param.h"
#include "user/user.h"

int main(int argc, char *argv[]) {
    int status, pid, new_argc;
    int idx = 0;
    char buf;
    char *new_argv[MAXARG];

    for(int i = 1; i < argc; i++) {
        new_argv[i-1] = argv[i];	
    }

    while(read(0, &buf, 1)) {
        new_argc = argc;
        idx = 0;
        new_argv[new_argc-1] = (char*)malloc(MAXARG);
        do {
            // only read one line each time
            if(buf == '\n') {
                new_argv[new_argc-1][idx] = '\0';
                new_argv[new_argc] = 0;
                break;
            } else if(buf == ' ') {
                // if meet ' ', divide into more argv
                // except for two ' '
                if(idx == 0) {
                    continue;
                }
                new_argv[new_argc-1][idx] = '\0';
                new_argc++;
                idx = 0;
                new_argv[new_argc-1] = (char*)malloc(MAXARG);
                continue;
            }
            new_argv[new_argc-1][idx++] = buf;
        } while(read(0, &buf, 1));

        pid = fork();
        if(pid == 0) {
            exec(new_argv[0], new_argv);
            printf("wrong command\n");
            exit(-1);
        } else {
            wait(&status);
        }

        for(int i = argc; i <= new_argc; i++) {
            free(new_argv[i-1]);
        }
    }

    exit(status);
}

Optional challenge exercises

写一个 uptime 程序来调用 uptime 系统调用

直接调用 uptime 然后打印返回值就好了

对 grep 实现正则匹配

yysy，对正则表达式不是很了解

改造 sh

#todo