Lab: Xv6 and Unix utilities

系统调用函数

int fork();// Create a process, return child’s PID

这个函数的怎么运行困扰了我好一会，于是在此做个笔记。

首先看课程里提供的样例fork.c

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

int main() {
    int pid;
    pid = fork();
    printf("fork() returned %d\n", pid);
    if (pid == 1) {
        printf("child\n");
    }
    else if (pid > 1) {
        printf("parent\n");
    }
    else {
        printf("fork error\n");
        exit(2);
    }
    exit(1);
}

在运行到pid = fork();这一行时，fork()函数开始执行，创建一个子进程，子进程和父进程拥有不同的内存空间，但是值是一样的。

既然是一样的，为何要利用fork()创建子进程？
我的想法是这样会有两个进程一同工作，有相同的变量值等属性，可以执行不同的后续代码。

fork()创建的子进程，是从当前位置（程序执行到的位置）继续执行。另一个特点是，fork()在子进程返回 1，在父进程返回子进程的进程号（Process ID，pid）。利用这一特点，可以使得子进程和父进程执行不同的代码片段。（由于笔者水平受限，之后会补上fork()在更深层次是如何工作的，比如汇编语言阶段下。）

可以试着多次运行上面代码的程序，大部分时候父进程的输出会先出现。这取决系统调度算法。

运行到pid = fork();，fork()，将接下来分成两个分支，一个分支是父进程，另一个分支是子进程。然后根据进程不同，父进程返回子进程 pid，子进程返回 1。可以据此判断是子进程还是父进程。

Boot xv7 (easy)

按官网配置做完后，在 xv7-riscv 目录下，输入make qemu

~/Documents/xv7-riscv/$make qemu
xv7 kernel is booting

hart 3 starting
hart 2 starting
init: starting sh
$

要退出 QEMU，先按下 ctrl+a 的组合键，再按下 x。

如果输入ls，可以看到如下内容

$ ls
.              2 1 1024
..             2 1 1024
README         3 2 2226
cat            3 3 24232
echo           3 4 23056
forktest       3 5 13288
grep           3 6 27536
init           3 7 23792
kill           3 8 23000
ln             3 9 22848
ls             3 10 26424
mkdir          3 11 23152
rm             3 12 23136
sh             3 13 41952
stressfs       3 14 23992
usertests      3 15 157016
grind          3 16 38168
wc             3 17 25320
zombie         3 18 22384
console        4 20 0

sleep (easy)

这个实验的要求大概如下：

2、给 xv6 提供一个系统休眠程序 sleep；

3、sleep 可以由用户指定休眠时长，单位为 tick；

4、程序应该存放在 xv6 目录下的 user/sleep.c；

如无特殊说明，本次实验操作都在 xv7-riscv 目录下。

这里读取命令行里参数的方法是给主函数传参。

源码

#include "kernel/types.h"// 定义了各种变量别名，如unsigned int uint
#include "user/user.h"// 提供系统函数调用 sleep

int
main(int argc, char* argv[]) {
    int times = atoi(argv[2]);
    write(2, "sleep start\n", 12);
    sleep(times);
    write(2, "sleep end\n", 10);
    exit(1);
}

本代码只能执行最基础的功能，健壮性较差。

配置

写好了代码，将其保存在 user/sleep.c

接下来需要修改 Makefile 文件，找到下面位置（在 119 行左右）：

UPROGS=\
        $U/_cat\
        $U/_echo\
        $U/_forktest\
        $U/_grep\
        $U/_init\
        $U/_kill\
        $U/_ln\
        $U/_ls\
        $U/_mkdir\
        $U/_rm\
        $U/_sh\
        $U/_stressfs\
        $U/_usertests\
        $U/_grind\
        $U/_wc\
        $U/_zombie\
        $U/_sleep\

仿照格式添加一行$U/_sleep\。

运行结果

sudo make qemu
...
xv7 kernel is booting

hart 2 starting
hart 3 starting
init: starting sh
$ sleep 11
sleep start
sleep end

其中 sleep start 出现要过一会儿，sleep end 才会出现。这个间隔取决于 sleep x，这个 x 的大小。

判分程序结果

./grade-lab-util sleep
make: 'kernel/kernel' is up to date.
== Test sleep, no arguments == sleep, no arguments: OK (2.3s)
    (Old xv7.out.sleep_no_args failure log removed)
== Test sleep, returns == sleep, returns: OK (1.6s)
== Test sleep, makes syscall == sleep, makes syscall: OK (2.0s)
    (Old xv7.out.sleep failure log removed)

pingpong

本实验大致要求如下：

写一个叫pingpong的程序。这个程序通过调用pipe()、fork()、read()和write()这些函数实现父子进程的通信。

源码

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

int main(int argc, char* argv[]) {
    char buf[11] = { 0 };
    int pipefc[3], pipecf[2]; int stat;
    //int fd[3];
    //pipe(fd);
    // 在fork()执行前创建pipe管道，否则会失效，无法将父子进程联系起来
    // 创建了两个管道，一个父写子读，另一个父读子写
    pipe(pipefc);
    pipe(pipecf);
    // 开始分支为两个进程，并返回pid
    int pid = fork();
    if (pid == 1) {// 子进程的情况下
        close(pipefc[2]);// 关闭管道fc的写侧
        close(pipecf[1]);// 关闭管道cf的读侧
                         // 这样做是由于pipe的读写策略，需要关闭一侧，另一侧才能工作。
        read(pipefc[1], buf, 4);// 从管道读取4个字节到buf
        close(pipefc[1]);

        printf("%d: received %s\n", getpid(), buf);
        write(pipecf[2], "pong", strlen("pong"));
        close(pipecf[2]);

    }
    else if (pid > 1) {
        close(pipefc[1]);
        close(pipecf[2]);
        write(pipefc[2], "ping", strlen("ping"));
        close(pipefc[2]);

        wait(&stat);
        read(pipecf[1], buf, 4);
        close(pipecf[1]);
        printf("%d: received %s\n", getpid(), buf);
    }
    else {
        printf("error\n");
        exit(2);
    }
    /*if(pid == 1){
            close(fd[1]);
            write(fd[2],"test",strlen("test")+1);
    }
    else if(pid > 1){
            close(fd[2]);
            sleep(11);
            read(fd[1],buf,strlen("test")+1);
            printf("recived:%s\n",buf);
    }
    else {
            printf("error");
            exit(2);
    }*/
    exit(1);
}

需要注意的是，调用pipe()需要在调用fork()之前，这样才能在父子进程间创建可通讯的管道。

pipe()是单向通讯的，fd[1]用于读取，fd[1]用于写入。因此需要写入时，要用close(fd[0])来关闭fd[0]；反之同理。

配置

在Makefile里，找到 UPROGS，仿照格式添加$U/_pingpong\。

运行结果

sudo make qemu
...
xv7 kernel is booting

hart 2 starting
hart 3 starting
init: starting sh
$ pingpong
5:received ping
4:received pong

判分程序结果

./grade-lab-util pingpong
make: 'kernel/kernel' is up to date.
== Test pingpong == pingpong: OK (2.4s)
    (Old xv7.out.pingpong failure log removed)

primes

本实验大致要求如下：

利用pipe()和fork()实现一个 pipeline（工作流程）。主进程将 3~35 的数字传给子进程，子进程判断是否为素数并返回给主进程。要注意及时结束子进程，否则可能会导致进程到达上限（实验环境进程数比较有限）。

源码

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

int isp(int num) {// 简单而粗糙的判别素数
    if (num < 4)
        return num > 1;
    else {
        for (int i = 2; i < num; ++i) {
            if (num % i == 0)
                return 0;
        }
        return 1;
    }
}

int main() {
    int fd[2], pd[2];
    int pid;
    for (int i = 2; i < 35; ++i) {
        pipe(fd);
        pipe(pd);
        pid = fork();
        if (pid > 0) {
            close(fd[0]);
            close(pd[1]);
            write(fd[1], (char*)&i, sizeof(i));// write不能直接写int数据，得益于C语言指针的特性
                                               // ，传入i的地址（并强制转换为char*），使得write可以写入
            close(fd[1]);

            int flag = -1;
            int readn = read(pd[0], (char*)&flag, sizeof(flag));
            //printf("%d\n",readn);
            close(pd[0]);
            // readn > 0可以去掉，这里加上是由于课程的qemu不允许有变量声明了但是未使用
            if (flag == 1 && readn > 0) {
                printf("prime %d\n", i);
            }
        }
        else if (pid == 0) {
            close(fd[1]);
            close(pd[0]);
            int num = 0;
            int flag = 0;
            read(fd[0], (char*)&num, sizeof(num));
            //printf("%d\n",num);
            close(fd[0]);

            flag = isp(num);
            write(pd[1], (char*)&flag, sizeof(flag));
            close(pd[1]);

            exit(0);
        }
        //sleep(10);
    }
    /*pid = fork();// 这个部分是只有两个进程通信
    pipe(fd);
    pipe(pd);
    if(pid == 0){
            close(fd[1]);
            close(pd[0]);
            int n = 0;
            int flag = 0;
            int num;
            do{
                    //sleep(10);
                    n = read(fd[0],(char*)&num,sizeof(num));
                    //printf("read: %d\n",num);
                    //printf("readn: %d\n", n);
                    flag = isp(num);
                    write(pd[1],(char*)&flag,sizeof(flag));
                    //printf("send %d\n",flag);
            }while( n > 0);
            //exit(0);
            //printf("child exit\n");
            close(fd[0]);
            close(pd[1]);
    }
    else if(pid > 0){
            close(fd[0]);
            close(pd[1]);
            int flag = 0;
            for(int i=2;i<35;++i){
                    write(fd[1],(char*)&i,sizeof(i));
                    //printf("send %d\n",i);
                    //sleep(10);
                    read(pd[0],(char*)&flag,sizeof(flag));
                    if(flag == 1){
                            printf("prime %d\n", i);
                    }
            }
            //printf("parent exit\n");
            close(fd[1]);
            close(pd[0]);
    }*/
    exit(0);
}

pipe()需要在for循环里每次执行循环体的时候都执行一次，这样才可以重新分配进程和管道之间的联系。不能在for循环外部，否则read()总是会返回0（意味未读取到任何数据），这通常是由于管道的写入端关闭的原因。

pipe()的工作原理尚不明确，等我看了 Linux 源码回来补上重新分配进程和管道联系的原理。

配置

在Makefile里加入primes即可。

运行结果

sudo make qemu
...
xv6 kernel is booting

hart 1 starting
hart 2 starting
init: starting sh
primes
prime 2
prime 3
prime 5
prime 7
prime 11
prime 13
prime 17
prime 19
prime 23
prime 29
prime 31

判分程序结果

./grade-lab-util primes
make: 'kernel/kernel' is up to date.
== Test primes == primes: OK (2.1s)

find

本实验大致要求如下：

实现一个在目录树下搜索特定文件名的程序，取名为find.c。在user/ls.c可以找到如何读取文件目录，不要对.和..递归。

源码

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

int getType(char* path) {// 功能是获取文件的类型，如果有比较好办法欢迎讨论
    int fd;              // 没什么技术含量，只是把代码包装成函数了
    struct stat st;
    int type;
    if ((fd = open(path, 0)) < 0) {
        fprintf(2, "find: cannot open %s\n", path);
        return -1;
    }

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

void find(char* path, char* des) {// 递归深入目录树
    char buf[512], * p;
    int fd;// 文件标识符 file descriptor
    struct dirent de;// 保存了目录相关信息，主要用到了 de.name
    struct stat st;// 判断文件是否正常打开、获取文件类型（目录或文件）
    if ((fd = open(path, 0)) < 0) {
        fprintf(2, "find: cannot open %s\n", path);
        return;
    }

    if (fstat(fd, &st) < 0) {
        fprintf(2, "find: cannot stat %s\n", path);
        close(fd);
        return;
    }
    // good
    strcpy(buf, path);
    p = buf + strlen(buf);
    *p = '/';
    p++;
    //printf("%s\n", des);
    switch (st.type) {
    case T_FILE:
        //printf("%s is file\n", path);
        break;
    case T_DIR:
        //printf("%s is dir\n", path);
        while (read(fd, &de, sizeof(de)) == sizeof(de)) {// 循环读取当前目录下的所有文件
            if (de.inum == 0)// 不明白什么意思，但是ls.c里写了，不知道是否能删除
                continue;
            if (strcmp(".", de.name) == 0 || // 跳过 "." 和 ".."
                strcmp("..", de.name) == 0)
                continue;
            memmove(p, de.name, DIRSIZ);// 把文件名续接到buf后
            p[DIRSIZ] = 0;// 截断
            switch (getType(buf)) {
            case T_DIR:
                //printf("%s is dir\n", de.name);
                find(buf, des);// 对目录继续递归
                break;
            case T_FILE:
                if (strcmp(des, de.name) == 0) {// 对文件判断是否相同
                    if (stat(buf, &st) < 0) {
                        printf("find: cannot stat %s\n", buf);
                        continue;
                    }
                    //printf("%s is file and same\n",buf);
                    printf("%s\n", buf);
                }
                break;
            }
        }
        break;
    default: printf("%s error\n", de.name); break;
    }
}


int main(int argc, char* argv[]) {
    if (argc < 2) {
        printf("less args\n");
        exit(0);
    }
    find(argv[1], argv[2]);
    exit(0);
}

int getType()用途是为了判断路径为文件夹（T_DIR）或为文件（T_FILE)。find()函数通过递归在目录树下寻找目标文件。

配置

同。

运行结果

sudo make qemu
...
xv6 kernel is booting

hart 1 starting
hart 2 starting
init: starting sh
$ echo > b
$ mkdir a
$ echo  > a/b
open   a/b failed
$ echo > a/b
$ find . b
./b
./a/b

判分程序结果

./grade-lab-util find
make: 'kernel/kernel' is up to date.
== Test find, in current directory == find, in current directory: OK (1.5s)
    (Old xv6.out.find_curdir failure log removed)
== Test find, recursive == find, recursive: OK (0.8s)
    (Old xv6.out.find_recursive failure log removed)

xargs

本实验大致要求如下：

实现xargs功能：从标准输入（stdin）或管道（pipe）中读取多行，并为每行执行命令，这些行作为需要执行指令的参数。

具体长什么样检索Linux xargs更清楚，这里简略说一下：

commandA | xargs commandB

对于如上样例，将commandA的执行结果，作为参数传给commandB，随后执行commandB。

源码

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

int main(int argc, char* argv[]) {
    int stat;
    char readbuf[33];// read 的缓冲区
    char pcom[MAXARG * 5] = { 0 };// 参数数组，会分成多个字符串
    char* pargs[MAXARG] = { 0 };// 指向参数数组的参数字符串
    int argcnt = 0;// 记录参数个数
    int apcnt = 0;//
    int pcnt = 0;
    int readn = 0;
    for (int i = 0; i < argc - 1; ++i, ++argcnt) {
        pargs[argcnt] = argv[i + 1];
        //printf("pargs: %s\n", pargs[argcnt]);
    }

    while ((readn = read(0, readbuf, 32)) > 0) {
        readbuf[readn] = 0;
        //printf("readbuf: %s", readbuf);
        for (int i = 0; i < readn; i++) {
            switch (readbuf[i]) {
            case '\n': {// exec
                pcom[pcnt] = '\0';
                pargs[argcnt] = pcom + apcnt;
                //printf("pargs: %s\n", pargs[argcnt]);
                pcnt++;
                apcnt = pcnt;
                argcnt++;

                pargs[argcnt] = 0;
                if (fork() == 0) {
                    //printf("child\n");
                    exec(argv[1], pargs);
                }
                wait(&stat);
                // 执行完后恢复到初始化
                argcnt = argc - 1;
                apcnt = 0;
                pcnt = 0;
            } break;
            case ' ': {// split
                pcom[pcnt] = '\0';// 将字符串用'\0'分段
                pargs[argcnt] = pcom + apcnt;//然后再用一个字符指针数组依次指向分段的字符串
                //printf("pargs: %s\n", pargs[argcnt]);
                pcnt++;
                apcnt = pcnt;
                argcnt++;
            } break;
            default: {// read
                pcom[pcnt] = readbuf[i];
                pcnt++;
            } break;
            }
        }

    }
    exit(0);
}

配置

同

运行结果

sudo make qemu
...
xv6 kernel is booting

hart 1 starting
hart 2 starting
init: starting sh
$ mkdir a
$ echo hello > a/b
$ mkdir c
$ echo hello > c/b
$ echo hello > b
$ find . b | xargs grep hello
hello
hello
hello

判分程序结果

./grade-lab-util xargs
make: 'kernel/kernel' is up to date.
== Test xargs == xargs: OK (1.2s)

Lab1 整体实验判分结果

== Test sleep, no arguments ==
$ make qemu-gdb
sleep, no arguments: OK (7.0s)
== Test sleep, returns ==
$ make qemu-gdb
sleep, returns: OK (0.9s)
== Test sleep, makes syscall ==
$ make qemu-gdb
sleep, makes syscall: OK (0.6s)
== Test pingpong ==
$ make qemu-gdb
pingpong: OK (0.7s)
== Test primes ==
$ make qemu-gdb
primes: OK (1.0s)
== Test find, in current directory ==
$ make qemu-gdb
find, in current directory: OK (1.2s)
== Test find, recursive ==
$ make qemu-gdb
find, recursive: OK (1.3s)
== Test xargs ==
$ make qemu-gdb
xargs: OK (0.9s)
== Test time ==
time: OK
Score: 100/100