MIT 6.S081 Lab util

Compulsory exercises

Lab guidance

• About easy / moderate / hard

Boot xv6 (easy)

• 启动xv6

在shell中

$ cd xv6-labs-2021
$ make qemu

在xv6 shell中列出文件

$ ls

在xv6中
Ctrl-p 打印进程信息
Ctrl-a x 退出qemu

sleep (easy)

• 了解系统调用

  • xv6文档p11
    

• 代码实现

code

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

int main(int argc, char *argv[])
{
    if (argc != 2) {
        //error
        fprintf(2, "Error arg number!");
        exit(1);
    } else {
        int time = atoi(argv[1]);
        sleep(time);
        exit(0);
    }
}

• 补全Makefile

$U/_sleep\

• 测试

$ cd xv6-labs-2021

$ ./grade-lab-util sleep
# Or #
$ make GRADEFLAGS=sleep grade

pingpong (easy)

• 图解
  
  

• 代码实现

code

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

int main(int argc, char *argv[])
{
    int p[2];
    int pid;
    pipe(p);
    if (fork() == 0) {
        // child
        pid = getpid();
        char buf[2];
        read(p[0], buf, 1);
        close(p[0]);
        printf("%d: received ping\n", pid);
        write(p[1], buf, 1);
        close(p[1]);
        exit(0);
    } else {
        // parent
        pid = getpid();
        char ball[2] = "b";
        char buf[2];
        write(p[1], ball, 1);
        close(p[1]);
        wait(0);
        read(p[0], buf, 1);
        printf("%d: received pong\n", pid);
        close(p[0]);
        exit(0);
    }
}

primes (moderate)/(hard)

• 图解
  

• 根据分析需要使用两个管道分别用于左邻居和右邻居

• 代码实现

code

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

void childPrime(int p[2]) {
    // p -> left, pr -> right
    // [0] -> read, [1] -> write
    close(p[1]);
    // get first prime
    int prime;
    if (read(p[0], &prime, 4) != 4) {
        exit(0);
    }
    printf("prime %d\n", prime);

    int pr[2];
    pipe(pr);

    if (fork() == 0) {
        childPrime(pr);
    } else {        
        close(pr[0]);
        // drop multiple of prime
        int n;
        while (read(p[0], &n, 4) == 4) {
            if (n % prime != 0) {
                if (write(pr[1], &n, 4) != 4) {
                    fprintf(2, "write error");
                }          
            }
        }
        // close read left
        close(p[0]);
        // close write right
        close(pr[1]);

        wait(0);    
    }
    exit(0);
}

int main(int argc, char *argv[])
{
    int p[2];
    pipe(p);
    if (fork() == 0) {
        // child
        childPrime(p);
    } else {
        // parent
        // close read
        close(p[0]);
        for (int i = 2; i <= 35; i++) {
            if (write(p[1], &i, 4) != 4) {
                fprintf(2, "write error");
                exit(1);
            }
        }
        // close write
        close(p[1]);

        wait(0);
    }
    exit(0);
}

find (moderate)

• 阅读ls.c了解文件系统

• 代码实现

code

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

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;
}

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

    if((fd = open(pwd, 0)) < 0){
        fprintf(2, "cannot open %s\n", pwd);
        return;
    }

    if(fstat(fd, &st) < 0){
        fprintf(2, "cannot stat %s\n", pwd);
        close(fd);
        return;
    }  

    if (read(fd, &de, sizeof(de)) != sizeof(de)){
        exit(1);
    }

    switch(st.type){
    case T_FILE:
        if (strcmp(de.name, filename) == 0) {
            printf("%s/%s\n", pwd, filename);
        }
        break;

    case T_DIR:
        if (strlen(pwd) + 1 + DIRSIZ + 1 > sizeof buf) {
            printf("path too long\n");
            break;
        }
        strcpy(buf, pwd);
        p = buf+strlen(buf);
        *p++ = '/';
        while (read(fd, &de, sizeof(de)) == sizeof(de)) {
            if (de.inum == 0 || strcmp(de.name, ".") ==0 || \
                strcmp(de.name, "..") == 0) {
                continue;
            }
            memmove(p, de.name, DIRSIZ);
            p[DIRSIZ] = 0;
            if (stat(buf, &st) < 0) {
                printf("cannot stat %\n", buf);
                continue;
            }

            if (st.type == T_FILE) {
                if (strcmp(de.name, filename) == 0) {
                    printf("%s\n", buf);
                }
            } else if (st.type == T_DIR) {
                find(buf, filename);
            }
        }
        break;
    }    
    close(fd);
}

int main(int argc, char *argv[])
{
    if (argc != 3) {
        fprintf(2, "error number!");
        exit(1);
    } else {
        char* pwd = argv[1];
        char* filename = argv[2];
        find(pwd, filename);
        exit(0);
    }
}

xargs (moderate)

• 了解xargs

  • 教程
  • 要求实现简易的xarg，即实现下列命令行调用

$ find . b | xargs grep hello

$ echo hello too | xargs echo bye
bye hello too

• 代码实现(reference)

code

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

void copy(char **p1, char *p2) {
    *p1 = malloc(strlen(p2) + 1);
    strcpy(*p1, p2);
}

int readLine(char **pars, int i){
    int d = 1024;
    char buf[d];
    int j = 0;
    // 读取1行
    while (read(0, buf + j, 1)){
        // 按行划分
        if (buf[j] == '\n'){
            buf[j] = 0;
            break;
        }
        j++;
        if (j == d){
            fprintf(2, "Parameters are too long!\n");
            exit(1);
        }
    }
    
    // 没有读取内容
    if (j == 0){
        return -1;
    }

    // 按照空格划分
    int k = 0;
    while (k < j){
        if (i > MAXARG){
            fprintf(2, "Too much parameters!\n");
            exit(1);
        }
        // '   abc   sdf'
        // 忽略
        while ((k < j) && (buf[k] == ' ')){
            k++;
        }
        // 起始位置
        int l = k;
        // 保留字符
        while ((k < j) && (buf[k] != ' ')){
            k++;
        }
        // 注意需要k++
        buf[k++] = 0;
        copy(&pars[i], buf + l);
        i++;
    }

    return i;
}

int main(int argc, char *argv[])
{
    if (argc < 2) {
        fprintf(2, "error arg number");
        exit(1);
    } else {
        char *args[MAXARG]; 
        int i;
        int j;
        for (i = 1, j = 0; i < argc; i++, j++) {
            copy(&args[j], argv[i]);
        }

        int end;
        while ((end = readLine(args, argc - 1)) != -1) {
            args[end] = 0;
            if (fork() == 0) {
                // child
                exec(args[0], args);
                exit(1);
            } else {
                wait(0);
            }
        }
        
    }
    exit(0);
}

Optional challenge exercises

• Write an uptime program that prints the uptime in terms of ticks using the uptime system call. (easy)

• Support regular expressions in name matching for find. grep.c has some primitive support for regular expressions. (easy)

• The xv6 shell (user/sh.c) is just another user program and you can improve it.