Lab: Xv6 and Unix utilities

MIT6.S081(Fall 2020): Operating System Engineering Schedule

实验主页

环境:CentOS 8

Boot xv6

首先需要准备环境

Lab Tools

Lab Tools Page

git clone --recursive https://github.com/riscv/riscv-gnu-toolchain
# 官网是通过apt安装的,而yum会导致下面的包有一些会装失败,请自行搜索失败包的安装方法
yum install autoconf automake autotools-dev curl libmpc-dev libmpfr-dev libgmp-dev gawk build-essential bison flex texinfo gperf libtool patchutils bc zlib1g-dev libexpat-dev

cd riscv-gnu-toolchain
./configure --prefix=/usr/local
sudo make
cd ..

Lab Tools的github仓库特别多子模块,疯狂套娃,下载起来非常的慢,而且非常大,有6G多,也非常容易连接断开。我是通过公司网下到本地再用scp传到服务器上的,这一步可能比较麻烦。

Qemu

wget https://download.qemu.org/qemu-5.1.0.tar.xz
tar xf qemu-5.1.0.tar.xz

cd qemu-5.1.0
./configure --disable-kvm --disable-werror --prefix=/usr/local --target-list="riscv64-softmmu"
make
sudo make install
cd ..

这个过程可能也会有一些包没装好,自己看失败信息装一下就好了

检查Lab Tools和Qemu安装结果

riscv64-unknown-elf-gcc --version
# 显示如下
riscv64-unknown-elf-gcc (GCC) 11.1.0
Copyright (C) 2021 Free Software Foundation, Inc.

qemu-system-riscv64 --version
# 显示如下
QEMU emulator version 5.1.0
Copyright (c) 2003-2020 Fabrice Bellard and the QEMU Project developers

xv6

git clone git://g.csail.mit.edu/xv6-labs-2020
cd xv6-labs-2020
git checkout util

make qemu

# 输出如下
xv6 kernel is booting

hart 2 starting
hart 1 starting
init: starting sh

这样就成功进入xv6的shell中了,如果需要退出的话,按Ctrl + a x

编译

对于每一个小的实验,将代码写到指定的位置,然后在Makefile文件中的UPROGS段下加上自己的程序进行编译,再次进入xv6的shell就会看到自己程序的可执行文件。比如写了一个sleep程序,通过下面的方式注册函数即可。

# Makefile

UPROGS=\
	...
	$U/_sleep\

测试

在xv6根目录下,注意不是xv6的shell环境中,通过下面的方式对自己写的程序进行测试即可。

./grade-lab-util program_name

# example
# ./grade-lab-util sleep

到这一步环境就准备好了,可以开始做实验了。

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.

Code

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

int main(int argc, char *argv[]) {
    if (argc <= 1) {
        fprintf(2, "usage: sleep ticks\n");
        exit(1);
    }
    int sleep_ticks = atoi(argv[1]);
    sleep(sleep_ticks);
    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.

Code

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

int main(int argc, char *argv[]) {
    if (argc != 1) {
        fprintf(2, "usage: pingpong\n");
        exit(1);
    }

    char buf[8];
    int p[2];
    if (pipe(p) < 0) {
        fprintf(2, "pipe error...\n");
        exit(1);
    }

    if (fork() == 0) {
        read(p[0], buf, 5);
        fprintf(1, "%d: received %s", getpid(), buf);
        close(p[0]);

        write(p[1], "pong\n", 5);
        close(p[1]);
        exit(0);
    } else {
        write(p[1], "ping\n", 5);
        close(p[1]);

        wait(0);

        read(p[0], buf, 5);
        fprintf(1, "%d: received %s", getpid(), buf);
        close(p[0]);
    }
    exit(0);
}

primes

Write a concurrent version of prime sieve using pipes. This idea is due to Doug McIlroy, inventor of Unix pipes. The picture halfway down this page and the surrounding text explain how to do it. Your solution should be in the file user/primes.c.

primes

实验要求输出35之前的素数,要求的做法和素数筛法很像。实验要求主进程通过pipe向它的一个子进程顺序传递2~35的数字,这个子进程接收到的第一个数字(这里是2)就是一个素数,然后将其输出,之后接收到的数字(3~35),能够被这个素数(这里是2)整除的,都抛弃掉不处理,其余的数通过同样的方式传递给它的子进程,就是一个疯狂套娃的过程,直到最后一个子进程没有数字需要传递时,就exit回去。

Code

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

#define R 0
#define W 1

void wait_for_number(int p[]) {
    close(p[W]);
    int num;
    if (read(p[R], &num, sizeof(num))) {
        fprintf(W, "prime %d\n", num);

        int pd[2];
        if (pipe(pd) != 0) {
            fprintf(2, "primes: pipe error\n");
            exit(1);
        }

        if (fork() == 0) {
            wait_for_number(pd);
        } else {
            close(pd[R]);
            int other_num;
            while (read(p[R], &other_num, sizeof(other_num))) {
                if (other_num % num != 0) {
                    write(pd[W], &other_num, sizeof(other_num));
                }
            }
            close(pd[W]);
            wait(0);
        }
    }
    close(p[R]);
    exit(0);
}

int main(int argc, char *argv[]) {
    if (argc != 1) {
        fprintf(2, "usage: primes\n");
        exit(1);
    }

    int p[2];
    if (pipe(p) != 0) {
        fprintf(2, "primes: pipe error\n");
        exit(1);
    }

    if (fork() == 0) {
        wait_for_number(p);
    } else {
        close(p[R]);
        for (int i = 2; i <= 35; i++) {
            write(p[W], &i, sizeof(i));
        }
        close(p[W]);
        wait(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 should be in the file user/find.c.

Code

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

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

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

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

    if (st.type != T_DIR) {
        fprintf(2, "find: %s is not a directory\n", path);
        close(fd);
        exit(1);
    }

    if (strlen(path) + 1 + DIRSIZ + 1 > sizeof buf) {
        fprintf(2, "find: path too long\n");
        close(fd);
        exit(1);
    }

    strcpy(buf, path);
    pos = buf + strlen(buf) - 1;
    if (*pos++ != '/') {
        *pos++ = '/';
    }

    while (read(fd, &de, sizeof(de)) == sizeof(de)) {
	// 一开始没判断inum为0导致爆栈
        if (de.inum == 0 || !strcmp(de.name, ".") || !strcmp(de.name, ".."))
            continue;
        memmove(pos, de.name, DIRSIZ);
        pos[DIRSIZ] = 0;
        if (stat(buf, &st) < 0) {
            fprintf(2, "find: cannot stat %s\n", buf);
            close(fd);
            exit(1);
        }
        if (st.type == T_FILE && !strcmp(de.name, file_name)) {
            fprintf(1, "%s\n", buf);
        } else if (st.type == T_DIR) {
            find(buf, file_name);
        }
    }
    close(fd);
}

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

xargs

Write a simple version of the UNIX xargs program: read lines from the standard input and run a command for each line, supplying the line as arguments to the command. Your solution should be in the file user/xargs.c.

Code

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

#define BUF_SIZE 1024

int main(int argc, char *argv[]) {
    if (argc < 2) {
        fprintf(2, "usage: xargs command\n");
        exit(1);
    }

    int can_read = 1;
    char *_argv[MAXARG];
    char buf[BUF_SIZE];

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

    while (can_read) {
        char c;
        int _argv_cnt = argc - 1;
        int buf_idx = 0;
        int buf_begin = 0;
        while (1) {
            can_read = read(0, &c, sizeof(c));
            if (!can_read)
                exit(0);
            if (c == ' ' || c == '\n') {
                buf[buf_idx++] = 0;
                _argv[_argv_cnt++] = &buf[buf_begin];
                buf_begin = buf_idx;
                if (c == '\n')
                    break;
            } else {
                buf[buf_idx++] = c;
            }
        }

        _argv[_argv_cnt] = 0;

        if (fork() == 0) {
            exec(_argv[0], _argv);
        } else {
            wait(0);
        }
    }
    exit(0);
}

Test

make clean
make qemu

$ sh < xargstest.sh
$ $ $ $ $ $ hello
hello
hello
$ $