Lab: Xv6 and Unix utilities

Boot xv6

按照描述操作即可，如果仓库失效可能需要另外寻找其他的源。

sleep

使用系统调用 int sleep(int n) 即可, clock tick 与实际时间的比例不明, 代码如下:

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

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

    int ticks = atoi(argv[1]);
    if (ticks <= 0) {
        fprintf(2, "sleep: A wrong number of time provided.\\n");
        exit(1);
    }

    sleep(ticks);
    exit(0);
}

pingpong

一个比较简单的程序, 先 pipe() 再 fork() 可以使父程序与子程序共享一条管道; 同时由于 fork() 的性质, 任一进程关闭文件描述符时不会影响另一个进程的同名文件描述符, 因此只需 pipe() 一条管道即可, 代码如下:

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

int p[2];
char buf[5];
int status;

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

    if (fork() == 0) {
        read(p[0], buf, 4);
        if (strcmp(buf, "ping")) {
            exit(1);
        }
        close(p[0]);

        pid = getpid();
        printf("%d: received ping\\n", pid);

        write(p[1], "pong", 4);
        close(p[1]);

        exit(0);
    } else {
        write(p[1], "ping", 4);
        close(p[1]);

        wait(&status);
        if (status != 0) {
            printf("child failed.\\n");
            exit(1);
        }

        read(p[0], buf, 4);
        if (strcmp(buf, "pong")) {
            exit(1);
        }
        close(p[0]);

        pid = getpid();
        printf("%d: received pong\\n", pid);
        
        exit(0);
    }
}

primes

由于题目要求 (中文文档图示), 实现采用了最简单的阿氏筛, 同时因为文档提到了文件描述符数量限制, 欧拉筛可能无法实现. 通过递归函数的方式实现递归 fork(), 即父进程 fork() 得到子进程, 子进程再次 fork() 新的子进程直至完成要求, 代码如下:

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

char isPrime[40];
int p[2], numbers[40];

void recursive() {
    // count 需要除以 4, 因为返回值为读取到的字节数;
    // flag 用以标记当前这一步筛选后是否还有代筛选数字.
    int count = read(p[0], numbers, 35 * sizeof(int)) / 4, flag = 0;

    printf("prime %d\\n", numbers[0]);

    // 筛去质数的倍数, 题目要求导致不能使用欧拉筛法.
    for (int i = 2; i < 35; ++i) {
        if (i * numbers[0] > 35) {
            break;
        }
        isPrime[i * numbers[0]] = 0;
    }

    // 将筛去后的数字通过管道告知其子程序.
    for (int i = 1; i < count; ++i) {
        if (!isPrime[numbers[i]]) {
            continue;
        }
        write(p[1], numbers + i, 4);
        flag = 1;
    }

    // 如果不存在待筛去的数字, 则不再 fork(), 如果不使用 flag 会导致死锁.
    // 如果有待筛数字则 fork() 一个新的进程递归执行这一步. 
    // 父进程则将管道关闭, 这一步须在 fork() 后执行, 然而这样似乎不能保证 fork() 后立即执行.
    if (flag && fork() == 0) {
        recursive();
    } else {
        close(p[0]);
        close(p[1]);
        wait(0);
    }
}

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

    for (int i = 2; i <= 35; ++i) {
        isPrime[i] = 1;
        write(p[1], &i, 4);
    }

    recursive();
    exit(0);
}

find

由于英文文档推荐参考 user/ls.c, 因此实现大量使用其中的代码. 要求中的递归查询实现较易, 传递一个路径给递归函数, 如果对应的是文件则比较是否与 pattern 一致, 如果是路径则遍历路径下的文件并递归调用函数即可, 代码如下:

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

char* fmtname(char* path) {
    static char buffer[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(buffer, p, strlen(p));

    // 一定要有这一步
    buffer[strlen(p)] = 0;
    
    return buffer;
}

void find(char* pattern, char* path) {
    char buf[512], *p;
    int fd;
    struct dirent de;
    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;
    }

    switch (st.type) {
        case T_DIR:
            if (strlen(path) + 1 + DIRSIZ + 1 > sizeof buf) {
                printf("find: path too long\\n");
                break;
            }
            // 将路径拷贝至 buf 中
            strcpy(buf, path);

            // 在 buf 的末尾添加一个 '/' 并使 p 指向 buf 的末尾
            p = buf + strlen(buf);
            *p++ = '/';

            while (read(fd, &de, sizeof(de)) == sizeof(de)) {
                if (de.inum == 0 || !strcmp(de.name, ".") || !strcmp(de.name, ".."))
                    continue;

                // 将文件名添加到 buf 的末尾并加上 \\0
                memmove(p, de.name, DIRSIZ);
                p[DIRSIZ] = 0;

                find(pattern, buf);
            }
            break;

        default: {
            char* filename = fmtname(path);

            if (!strcmp(filename, pattern)) {
                printf("%s\\n", path);
            }
        
            break;
        }
    }
    close(fd);
}

int main(int argc, char* argv[]) {
    char *pattern, *path;

    if (argc < 3) {
        fprintf(2, "usage: find path pattern\\n");
        exit(1);
    }
    path = argv[1];
    pattern = argv[2];

    find(pattern, path);

    exit(0);
}

xargs

实现较易, 编写一个函数逐字节从管道中读入并判断行尾以按行读入, 而后再声明一个新的参数数组, 将原有的参数拷贝过去, 最后逐行读入新参数并通过 fork() 和 exec() 执行即可, 代码如下:

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

char* read_line(int fd) {
    static char buf[512];
    char *p = buf;
    int count = 0;

    while (1) {
        if ((count = read(fd, p, 1)) < 0) {
            fprintf(2, "xargs: cannot read from file discriptor %d\\n", fd);
            return 0;
        }

        if (!count || *p == '\\n')
            break;
        ++p;
    }

    *p = 0;
    return buf;
}

int main(int argc, char* argv[]) {
    char *command = argv[1], *args[MAXARG] = {command};

    if (argc < 2) {
        fprintf(2, "usage: somecommand | xargs command\\n");
        exit(1);
    }

    for (int i = 2 ; i < argc; ++i)
        args[i - 1] = argv[i];

    for (int i = 0; i < MAXARG; ++i) {
        char* arg = read_line(0);
        if (!arg)
            exit(1);
        if (!strlen(arg))
            break;

        args[argc - 1] = arg;

        if (fork() == 0) {
            exec(command, args);
        } else {
            int status;
            wait(&status);
            if (status)
                exit(status);
        }
    }

    exit(0);
}

吐槽