MIT 6s081 lab1:Xv6 and Unix utilities

Lab1: Xv6 and Unix utilities

作业网址：https://pdos.csail.mit.edu/6.828/2020/labs/util.html

Boot xv6(easy)

下载，启动xv6系统

$ git clone git://g.csail.mit.edu/xv6-labs-2020
Cloning into 'xv6-labs-2020'...
...
$ cd xv6-labs-2020
$ git checkout util
Branch 'util' set up to track remote branch 'util' from 'origin'.
Switched to a new branch 'util'
Build and run xv6:
$ make qemu
To quit qemu type: Ctrl-a x.

sleep(easy)

使用system call sleep.函数（在user/user.h中被声明）来完成

/*
    sleep.c
*/

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

int main(int argc, char *argv[])
{
   
    if(argc != 2) {
   
        printf("error, usage: <sleep> <sleep_time>\n");
        exit(1);
    }
    int sleep_time = atoi(argv[1]);

    /* 调用sleep函数 */
    sleep(sleep_time);

    exit(0);
}

pingpong(easy)

使用系统调用在一对管道上的两个进程之间“乒乓”一个字节，每个方向一个。父进程应该向子进程发送一个字节；子进程应打印“＜pid＞：received ping”，其中＜pid＞是其进程ID，将管道上的字节写入父进程，然后退出；父进程应该读取子进程的字节，打印“＜pid＞：received-pong”，然后退出。

/*
    pingpong.c
*/

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

int main(int argc, char *argv[])
{
   
    if(argc != 1) {
   
        printf("error, usage: <pingpong>\n");
        exit(1);
    }
    int pid;
    /* create pipe */
    int fd[2];
    if(pipe(fd) == -1) exit(1);

    pid = fork();
    char buf[10];

    if(pid == 0) /* child process */
    {
   
        int pid_this = getpid();
        char *str = "pong";
        read(fd[0], buf, sizeof(buf)); // 阻塞，等待父进程发送
        printf("%d: received %s\n", pid_this, buf);
        write(fd[1], str, strlen(str));
        close(fd[1]);
    }
    else{
    /* parent process */
        int pid_this = getpid();
        char *str = "ping";
        write(fd[1], str, strlen(str));
        close(fd[1]);
        wait(0); //等待子进程退出，再去读取

        read(fd[0], buf, sizeof(buf));
        printf("%d: received %s\n", pid_this, buf);
    }
    exit(0);
}

primes (moderate)/(hard)

使用管道通信实现素数筛，求解35以内的素数。

此算法的核心如下：对于任何一级流水线而言，到达当前流水线级的最小数字一定是一个素数，因为在处理之前比它更小的数字时它没有被筛掉，在当前流水线下它也需要作为一个基数去筛掉它在现存数字中的所有倍数，将所有剩下来的数字送入下一级流水线，直到本级流水线只剩下一个数字时，整个筛法结束。

/*
    a concurrent version of prime sieve 并发版本的素数筛
    primes.c
*/

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

static const int N = 35;

int main(int argc, char *argv[])
{
   
    if(argc != 1) {
   
        printf("error, usage: <primes>\n");
        exit(1);
    }
    
    int left_fd[2];
    int right_fd[2];
    pipe(left_fd);
    int num = 2;
    for(num = 2; num <= N; num++) write(left_fd[1], &num, sizeof(num));

    while(1)
    {
      
        if(fork()) {
   
            close(left_fd[1]); // 必须关闭父进程的写端
            close(left_fd[0]);
            wait(0);
            exit(0);
        }
        else {
   
            close(left_fd[1]); // 注意这里，必须关闭子进程的写端，当管道的2个写端都被关闭，read不会发生阻塞，没有数据直接返回
            pipe(right_fd);
            int x = -1, base = -1, cnt = 0;
            while(read(left_fd[0], &x, sizeof(num))){
    // 子进程循环读入
                cnt++;
                if(base == -1){
   
                    base = x; // 第一个数必定是素数
                    printf("prime %d\n", base);
                }
                else{
   
                    if((x % base) != 0){
    // 晒不掉的送入下一层
                        write(right_fd[1], &x, sizeof(num)); 
                    }
                }
                // printf("%d ", x);
            }
            
            if(cnt == 1) exit(0);
            // 这一层与子进程之间的管道是下一层中与父进程之间的管道！
            left_fd[0] = right_fd[0];
            left_fd[1] = right_fd[1];
        }
    }
}

find (moderate)

它可以在指定的目录下寻找指定名称的文件并打印出来，在编写代码之前可以从ls.c例程中学习如何读取目录信息，当深入到嵌套的文件夹中寻找时，应该使用递归写法。

文件信息结构体：

// 文件信息结构体
// 其中type表明了文件的类型是：文件、目录还是设备
#define T_DIR     1   // Directory
#define T_FILE    2   // File
#define T_DEVICE  3   // Device

struct stat {
   
  int dev;     // File system's disk device
  uint ino;    // Inode number
  short type;  // Type of file
  short nlink; // Number of links to file
  uint64 size; // Size of file in bytes
};

目录结构体：

// Directory is a file containing a sequence of dirent structures.
// 所谓目录，就是一系列dirent结构组成的顺序序列
#define DIRSIZ 14

struct dirent {
   
  ushort inum;
  char name[DIRSIZ];
};

/*
    find.c
*/

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

// 递归查找
void find(char *path, char *name)
{
   
    int fd;
    //关键在下面这两个结构体里面
    struct stat st; // 获取某个文件的状态
    struct dirent de; //获取目录下的所有项
    if((fd = open(path, 0)) < 0) {
   
        printf("cannot open %s\n", path);
        exit(1);
    }
    if(fstat(fd, &st) < 0){
   
        printf("cannot stat %s\n", path);
        close(fd);
        exit(1);
    }
    char buf[256]; // 这个数组不能开太大
    char *p;
    if(st.type == T_DIR)
    {
   
        if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){
    // 防止路径太长
            printf("ls: path too long\n");
            exit(1);
        }
        strcpy(buf, path);
        p = buf + strlen(buf);
        *p++ = '/';
        while(read(fd, &de, sizeof(de)) == sizeof(de)) {
    //查找目录下的所有项
            if(de.inum == 0)
                continue;
            memmove(p, de.name, DIRSIZ); // 项的名字
            p[DIRSIZ] = 0;
            // 根据前面的path,buf,p组合成当前项的绝对路径，获取其属性
            if(stat(buf, &st) < 0){
   
                printf("ls: cannot stat %s\n", buf);
                continue;
            }
            if(st.type == T_FILE) {
    //当前项是文件，则判断
                if(strcmp(de.name, name) == 0) printf("%s\n", buf);
            }
            else{
   
                // 当前项还是目录，则递归查找
                if(strcmp(de.name, ".") && strcmp(de.name, "..")) // 防止一直递归
                {
   
                    find(buf, name);
                }
            }
        }
    }
}

int main(int argc, char *argv[])
{
   
    if(argc != 3){
   
        printf("error, usage:<find> <path> <name>\n");
        exit(1);
    }
    // read directories
    char path[512], name[512];
    memcpy(path, argv[1], strlen(argv[1]));
    memcpy(name, argv[2], strlen(argv[2]));
    // printf("debug: path = %s\n",path);
    // printf("debug: name = %s\n",name);
    
    // 调用函数find
    find(path, name);

    exit(0);
}

xargs (moderate)

xargs(extensive arguments)是Linux系统中的一个很重要的命令，它一般通过管道来和其他命令一起调用，来将额外的参数传递给命令，这个小问题就是实现自己版本的xargs命令。初次理解xargs命令时还是有点费解的，指导书中的一个例子如下：

$ echo hello too | xargs echo bye
  bye hello too
$

要理解这个例子就将echo hello too | xargs看作一个整体，它本质上是将hello too传递给了xargs，然后经过xagrs的逻辑处理，就会将这些额外传入的参数交给后面的echo命令。我们的任务就是实现这里所谓的xargs的处理逻辑。

/*
    xargs.c
*/
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/param.h"

char *g_argv[MAXARG];

int main(int argc, char *argv[])
{
   
    if(argc < 2) {
   
        printf("error, usage:<xargs> <program>\n");
        exit(1);
    }
    if(argc >= MAXARG) {
   
        printf("too much argv\n");
        exit(1);
    }
    char c;
    char buf[32];
     
    int i = 0, cnt = 0;
    for(; cnt < argc - 1; cnt++) {
    
        g_argv[cnt] = (char*)malloc(sizeof buf); // 要先分配内存，野指针的解引用是未定义的结果
        // g_argv[cnt] = 0;
        // strcpy会对时针进行解引用，然后拷贝
        g_argv[cnt] = strcpy(g_argv[cnt], argv[cnt + 1]);        
    }

    while(read(0, &c, sizeof(c))) // 以字符形式读取完毕
    {
   
        cnt = argc - 1;
        if(c == '\n' || c == ' '){
   
            buf[i] = '\0'; // 结束符
            // printf("read: %s\n", buf);
            g_argv[cnt] = (char*)malloc(sizeof buf); // 分配内存
            g_argv[cnt] = strcpy(g_argv[cnt], buf);
            
            cnt++;
            i = 0;
            if(c == '\n') // 说明读完一行命令了，要让子进程去执行
            {
      // 此时已经读取完标准输入的argv的
                if(cnt + (argc - 2) >= MAXARG - 1)
                {
   
                    printf("too much argv\n");
                    exit(1);
                }
                g_argv[cnt] = 0; // 最后一个命令必须为结束符
                if(fork())
                {
      // 父进程等待子进程结束，等待完处理下一条命令
                    wait(0);
                }
                else{
    // 子进程
                    exec(argv[1], g_argv);
                    exit(0);
                }
            }
        }
        else {
   
            buf[i++] = c; // 不是空格也不是换行符，那就读取字符
        }
    }
    
    exit(0);

}

调试方式

首先make qemu-gdb CPUS=1，启动gdb-server

然后在另一个终端中（启动gdb客户端）使用gdb-multiarch -q kernel/kernel（kernel/kernel表示要gdb的程序）

进入gdb后

• b：设置断点
• c：运行
• n：单步运行
• s：进入函数内部

使用gdb的layout split模式可以看到gdb要执行的下一条指令是什么，断点具体在什么位置

提交

创建time.txt，写入耗时

make grade

结果：

$ make qemu-gdb
sleep, no arguments: OK (2.8s) 
== Test sleep, returns == 
$ make qemu-gdb
sleep, returns: OK (0.4s) 
== Test sleep, makes syscall == 
$ make qemu-gdb
sleep, makes syscall: OK (1.0s) 
== Test pingpong == 
$ make qemu-gdb
pingpong: OK (1.0s) 
== Test primes == 
$ make qemu-gdb
primes: OK (1.1s) 
== Test find, in current directory == 
$ make qemu-gdb
find, in current directory: OK (1.0s) 
== Test find, recursive == 
$ make qemu-gdb
find, recursive: OK (1.1s) 
== Test xargs == 
$ make qemu-gdb
xargs: OK (1.1s) 
== Test time == 
time: OK 
Score: 100/100