MIT 6.828 Util Lab

在xv6操作系统上实现一些实用小程序

实验准备（Lab1 Boot xv6）

在ubuntu18上进行实验

根据2021年的实验网站进行配置，但是发现用不了qemu-system-riscv64，只能自己手动构建riscv的toolchain，参考2020年的网站。

项目克隆下来后，使用make时提示riscv64-linux-gnu-gcc的命令行参数错误，参照这个issue更改Makefile。

最终可以make qemu了。

Lab2 sleep

利用xv6的系统调用，实现sleep命令。

使用 $ ./grade-lab-util sleep 对实验打分

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

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

Lab3 pingpong

通过创建管道实现父子进程通信，注意，对于一个进程来说，管道是单向的，所以要实现双向通讯，必须创建两个管道。

read(read_pipe, buf, buf_len)是阻塞的，除非关闭了管道的所有写端口（包括子进程），read返回0。

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

int main(void) {
    int p2c[2], c2p[2];
    char buf[1];

    if(pipe(p2c) < 0) {
        fprintf(2, "%s\n", "Cannot create pipe p2c.");
        exit(1);
    }

    if(pipe(c2p) < 0) {
        fprintf(2, "%s\n", "Cannot create pipe c2p.");
        exit(1);
    }


    if (fork() == 0) {
        // child process
        close(p2c[1]);  // close the write to parent

        read(p2c[0], buf, 1);
        printf("%d: received ping\n", getpid());  // 2. child receive the byte
        close(c2p[0]);
        write(c2p[1], buf, 1);  // 3. tell parent

        close(p2c[0]);
        close(c2p[1]);
        exit(0);
    } else {
        close(p2c[0]);  // close the read

        write(p2c[1], "a", 1);   // 1. send a byte to child

        close(c2p[1]);
        read(c2p[0], buf, 1);
        printf("%d: received pong\n", getpid());  // 4. parent got the byte

        close(p2c[1]);
        close(c2p[0]);
        exit(0);
    }
}

Lab4 primes

使用管道实现素数筛，每一个阶段实现打印管道中到来的第一个素数a，判断剩余到达的数是否能被a整除，如果不能，则送入下一阶段的管道。参考实现。

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

const int limit = 35;

void panic(char* buf) {
    fprintf(2, "%s\n", buf);
    exit(1);
}

void cull(int readPipe, int writePipe, int prime) {
    uint32 n;
    while (read(readPipe, &n, 4)) {
        if (n % prime != 0) {
            write(writePipe, &n, 4);
        }
    }
}
/**
 * return the another pipe contains group of numbers that cannot be divided by prime
 * @param prime
 * @param readPipe
 * @return
 */
void primeFilters(int readPipe) {
    uint32 prime;
    if (read(readPipe, &prime, 4)) {
        printf("prime %d\n", prime);

        int newPipe[2];
        if (pipe(newPipe) < 0) {
            panic("cannot create pipe.");
        }

        if (fork() == 0) {
            // child generate new sequence
            close(newPipe[0]);
            cull(readPipe, newPipe[1], prime);
            close(newPipe[1]);
        } else {
            // parent forward the pipe to next stage
            close(newPipe[1]);
            primeFilters(newPipe[0]);
            close(newPipe[0]);
        }
    }
}

int main(void) {
    int p[2];
    if (pipe(p) < 0) {
        panic("Cannot create pipe.");
    }

    if (fork() == 0) {
        // child
        close(p[1]);
        primeFilters(p[0]);
        close(p[0]);
    } else {
        // parent
        close(p[0]);
        for (uint32 i = 2; i <= limit; ++i) {
            write(p[1], &i, 4);
        }
        close(p[1]);
        wait(0); // wait all children
    }
    exit(0);
}

Lab5 find

递归得查找目录，用了来自ls.c的fmtname来规范化文件名，同时借鉴grep.c的正则匹配。

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

char curDir[DIRSIZ], parDir[DIRSIZ];
int match(char*, char*);

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));
    return buf;
}

char *trim(char *path) {
    char *p;
    static char buf[DIRSIZ];
    for (p = path + strlen(path) - 1; p >= path && *p == ' '; p--)
        ;
    p++;
    memmove(buf, path, p-path);
    buf[p-path] = 0;
    return buf;
}

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

    char *dirname = fmtname(path);
//    if (strcmp(name, dirname) == 0) { // compare
    if (match(name, trim(dirname))) {
        printf("%s\n", dirname);
        return;
    }

    if (st.type == T_DIR) {
        if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){
            printf("find: path too long\n");
            return;
        }

        strcpy(buf, path);
        p = buf+strlen(buf);
        *p++ = '/';

        while(read(fd, &de, sizeof(de))) {
            if (de.inum == 0) {
                continue;
            }
            memmove(p, de.name, DIRSIZ);
            p[DIRSIZ] = 0;
            if(stat(buf, &st) < 0){
                printf("find: cannot stat %s\n", buf);
                continue;
            }
            char *itemname = fmtname(buf);
//            if (!strcmp(name, itemname)) {  // compare
            if (match(name, trim(itemname))) {
                printf("%s\n", buf);
            } else {
                if (st.type == T_DIR) {
                    if (strcmp(curDir, itemname) && strcmp(parDir, itemname)){
                        find(buf, name);
                    }
                }
            }
        }
    }
}

int main(int argc, char* argv[]) {
    if (argc < 3) {
        fprintf(2, "Usage: find\n");
        exit(1);
    }
    while (argv[1][strlen(argv[1])-1] == '/') {
        argv[1][strlen(argv[1])-1] = 0;
    }

    strcpy(curDir, fmtname("."));
    strcpy(parDir, fmtname(".."));

    for (int i = 2; i < argc; i++) {
//        char nameBuf[DIRSIZ];
//        strcpy(nameBuf, fmtname(argv[i]));
        find(argv[1], argv[i]);
    }
    exit(0);
}


int matchhere(char*, char*);
int matchstar(int, char*, char*);

int
match(char *re, char *text)
{
    if(re[0] == '^')
        return matchhere(re+1, text);
    do{  // must look at empty string
        if(matchhere(re, text))
            return 1;
    }while(*text++ != '\0');
    return 0;
}

// matchhere: search for re at beginning of text
int matchhere(char *re, char *text)
{
    if(re[0] == '\0')
        return 1;
    if(re[1] == '*')
        return matchstar(re[0], re+2, text);
    if(re[0] == '$' && re[1] == '\0')
        return *text == '\0';
    if(*text!='\0' && (re[0]=='.' || re[0]==*text))
        return matchhere(re+1, text+1);
    return 0;
}

// matchstar: search for c*re at beginning of text
int matchstar(int c, char *re, char *text)
{
    do{  // a * matches zero or more instances
        if(matchhere(re, text))
            return 1;
    }while(*text!='\0' && (*text++==c || c=='.'));
    return 0;
}

Lab6 xargs

没有按照实验的要求一次读取一个字符直至'\n'，而是批量读取，之后来分割，所以代码有些复杂。在运用指针数组的时候注意。

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

int main(int argc, char* argv[]) {
    if (argc < 2) {
        fprintf(2, "Usage: %s cmd args...\n", argv[0]);
        exit(1);
    }

    char *execargv[MAXARG];
    for (int i = 1; i < argc; ++i) {
        execargv[i-1] = argv[i];
    }

    char buf[1024];
    int n, m;

    m = 0;
    while ((n = read(0, buf+m, sizeof(buf)-m-1)) > 0) {
        char *bp = buf + m, *p;
        p = bp;
        while (p < buf + m + n) {
            if (*p == '\n') {
                *p = '\0';
            }
            p++;
        }
        m += n;
        buf[m] = '\0';

        p = bp;
        while (p < bp + n) {
            if (strlen(p) == 0) {
                p++;
                continue;
            }

            if (fork() == 0) {
                // child
//                strcpy(execargv[argc], p);  // WRONG!! copy the args from stdin
                execargv[argc-1] = p;  // 注意未分配内存，只保存栈指针
                execargv[argc] = 0;
                exec(execargv[0], execargv);
                fprintf(2, "exec %s failed\n", execargv[0]);
                exit(1);
            } else {
                wait(0);
            }
            p += (strlen(p) + 1);
        }
    }
    exit(0);
}

END