Lab1 Xv6 and Unix utilities

Lab1 Xv6 and Unix utilities

目的是为了熟悉xv6和一些它的系统调用函数

Boot xv6(easy)

1.环境

环境我是用的vscode配置的wsl，系统是ubuntu 20.04。用虚拟机、云服务器都感觉差不多。

网上看到Ubuntu 22.04 版本不适用于20年的课程，在根据20年课程提示进行依赖安装时会出错。脑阔秃，我用的wsl就是22.04的，然后网上找帖子看wsl如何更换操作系统版本，最后换成20.04的了。

2.资源和依赖

输入以下指令获得xv6的资源和一些查看相关信息的命令

$ git clone git://g.csail.mit.edu/xv6-labs-2020
$ cd xv6-labs-2020
$ git checkout util
$ git log

然后是相关依赖，原话是“For this class you’ll need the RISC-V versions of a couple different tools: QEMU 5.1, GDB 8.3, GCC, and Binutils.”。来自6.S081 / Fall 2020 (mit.edu)，里面是不同方式的配置。我是Installing via APT (Debian/Ubuntu)。

$ sudo apt-get install git build-essential gdb-multiarch qemu-system-misc gcc-riscv64-linux-gnu binutils-riscv64-linux-gnu

安装验证

$ riscv64-unknown-elf-gcc --version
...
$ qemu-system-riscv64 --version

然后进入xv6的文件夹里，执行make qemu

# in the xv6 directory
$ make qemu
# ... lots of output ...
init: starting sh
$

关闭: 先同时按Ctrl-a，然后再按x.

补充：qemu-system-misc fix

$ sudo apt-get remove qemu-system-misc
$ sudo apt-get install qemu-system-misc=1:4.2-3ubuntu6

3.浅浅地操作

①

获取 xv6 源代码以用于实验（就是git clone,前面已经做了），并切换到 util 分支

$ cd xv6-labs-2020
$ git checkout util
Branch 'util' set up to track remote branch 'util' from 'origin'.
Switched to a new branch 'util'

xv6-labs-2020 仓库与书中的 xv6-riscv 略有不同，主要增加了一些文件。可以查看 git 日志：

$ git log

上述命令切换到一个专门为本实验定制的分支。

②

Build and run xv6:

$ make qemu
...(一长串内容)
$

尝试敲入命令ls

$ ls
.              1 1 1024
..             1 1 1024
README         2 2 2059
xargstest.sh   2 3 93
cat            2 4 24256
echo           2 5 23080
forktest       2 6 13272
grep           2 7 27560
init           2 8 23816
kill           2 9 23024
ln             2 10 22880
ls             2 11 26448
mkdir          2 12 23176
rm             2 13 23160
sh             2 14 41976
stressfs       2 15 24016
usertests      2 16 148456
grind          2 17 38144
wc             2 18 25344
zombie         2 19 22408
console        3 20 0

这些是 mkfs 包含在初始文件系统中的文件；大多数都是可以运行的程序。你刚刚运行了其中一个：ls。

xv6 没有 ps 命令，但是，如果你按下 Ctrl-p，内核会打印每个进程的信息。如果你现在尝试这个，你会看到两行：一行是 init，另一行是 sh。

要退出 qemu，可以按 Ctrl-a x。

sleep(easy)

目的

你的任务是为 xv6 实现一个 sleep 程序，该程序应根据用户指定的时间（以 ticks 为单位）暂停执行。tick 是 xv6 内核定义的一个时间概念，表示来自定时器芯片的两个中断之间的时间。

你的解决方案应放在文件 user/sleep.c 中。

提示

• 在开始写代码之前，把xv6 book的第一章读完。
• 查看 user/ 中的一些其他程序（例如 user/echo.c、user/grep.c 和 user/rm.c），以了解如何获取传递给程序的命令行参数。
• 如果用户忘记传递参数，sleep 应该打印错误消息。命令行参数以字符串形式传递；你可以使用 atoi 将其转换为整数（见 user/ulib.c）。
• 查看 kernel/sysproc.c 中实现 sleep 系统调用的代码（查找 sys_sleep），user/user.h 中可从用户程序调用的 sleep 的 C 定义，以及 user/usys.S 中从用户代码跳转到内核的汇编代码。
• 确保 main 调用 exit() 以退出程序。
• 在 Makefile 中将你的 sleep 程序添加到 UPROGS 中；完成后，运行 make qemu 编译你的程序，然后可以在 xv6 shell 中运行它。

做法

（当前以退出模拟器）

进入user目录下，发现没有sleep.c，就要自己创建

cd user/
vi sleep.c

我是用vscode直接打开文件夹，然后编写代码。其实从0开始，确实有点摸不着头脑，但前面提示就很nice。

我们的目标就是编写像你在linux shell中用的sleep命令。看了第一章的xv6材料意识到终端打开就是运行/user/sh.c文件，然后里面输入命令就相当于fork一个子进程然后用exec装载相关命令的.c文件。这里也就是我们要编辑的sleep.c文件。

然后看user/echo.c、user/grep.c ,其实就知道怎么写了。另外，注意导包，user.h提供函数，types.h提供变量类型

最后，要用exit退出。代码如下

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

int
main(int argc,char* argv[])
{
    if(argc!=2)
    {
        fprintf(2, "too less or too more argument.");
        exit(1);
    }

    int t = atoi(argv[1]);
    sleep(t);
    exit(1);
}

测试

要先修改makefile，在UPROGS后加入$U/_sleep\

然后在xv6 shell里面run

$ make qemu
...
init: starting sh
$ sleep 10
(nothing happens for a little while)
$

然后尝试评分，直接make grade会run所有的test，下面纸测试sleep。

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

然后中途系统没有找到 python 命令(如果没报错忽略这条)，/usr/bin/env: ‘python’: Permission denied

sudo ln -s /usr/bin/python3 /usr/bin/python

pingpong(easy)

目的

编写一个程序，使用 UNIX 系统调用通过一对管道在两个进程之间“ping-pong”传输一个字节。父进程应该向子进程发送一个字节；子进程应打印“: received ping”，其中 <pid> 是它的进程 ID，然后将字节写入管道返回给父进程，并退出；父进程应从子进程读取字节，打印“: received pong”，然后退出。你的解决方案应放在文件 user/pingpong.c 中。

做法

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

int 
main(int argc,char *argv[])
{
    if(argc>=2)
    {
        fprintf(2,"too many arguments.");
        exit(1);
    }

    // 先ping再pong
    int p2c[2];
    int c2p[2];
    pipe(p2c);
    pipe(c2p);

    int pid = fork();
    char buf[10];
    if(pid>0)
    {
        close(p2c[0]);
        close(c2p[1]);

        write(p2c[1],"ping",4);
        read(c2p[0],buf,sizeof(buf));
        printf("%d: received %s\n",getpid(),buf);
    
    }else if(pid==0)
    {
        close(p2c[1]);
        close(c2p[0]);

        read(p2c[0],buf,sizeof(buf));
        printf("%d: received %s\n",getpid(),buf);
        write(c2p[1],"pong",4);
    }

    exit(0);
}

测试

跟前面一样，只是将sleep换成pingpong，也记得修改makefile。之后就不写测试了。只写目的和做法了

primes(moderate)/(hard)

目的

编写一个使用管道的并发素数筛选器。这个想法源于Doug McIlroy，他是Unix管道的发明者。页面中间的图片及其周围的文字解释了如何实现。你的解决方案应该放在文件user/primes.c中。

你的目标是使用管道和分叉来建立管道。第一个进程将数字2到35输入管道。对于每一个素数，你需要创建一个进程，从它左侧的邻居读取数据，通过另一个管道写入到右侧的邻居。由于xv6有有限的文件描述符和进程，首个进程可以在35时停止。

提示

• 小心关闭进程不需要的文件描述符，否则你的程序会在第一个进程到达 35 之前耗尽 xv6 的资源。

• 一旦第一个进程到达 35，它应该等待整个管道终止，包括所有子进程、孙进程等。因此，主质数进程应该在所有输出都打印后，以及所有其他质数进程退出后再退出。

• 提示：当管道的写入端关闭时，read 返回零。

• 直接将 32 位（4 字节）整数写入管道比使用格式化 ASCII 输入/输出更简单。

• 仅在需要时创建管道中的进程。

• 将程序添加到 Makefile 的 UPROGS 中。

代码

可能最开始有点懵，但看了对应材料应该还好。Bell Labs and CSP Threads (swtch.com)，核心就是下图

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

void filter(int listenfd)
{
    int d;
    int ret = read(listenfd,&d,sizeof(d));
    if (ret != sizeof(d)) return;
    printf("prime %d\n",d);

    int pp[2];
    pipe(pp);

    int pid = fork();
    if(pid>0)
    {
        close(pp[0]);

        int v;
        while(read(listenfd,&v,sizeof(v))>0)
        {
            if(v%d!=0)
                write(pp[1],&v,sizeof(v));
        }

        close(pp[1]);
        close(listenfd);
        wait(0);
        close(pp[0]);

    }else if(pid==0)
    {
        close(pp[1]);
        filter(pp[0]);
    }
}

int main() {
    
    int p[2];
    pipe(p);

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

    filter(p[0]);
    wait(0);
    
    exit(0);
}

想了还是有点久，虽说思路简单，就是个递归，但写的时候有点麻烦。最开始main里面直接fork然后用filter发现重复很多代码，然后想着filter里fork，又发现主进程就有点麻烦。虽然写出来了，提示：当管道的写入端关闭时，read 返回零。这一条好像没用上，而且递归退出我我感觉怪怪的。但能过。

find(moderate)

目的

编写一个简单版本的UNIX find程序：在目录树中查找所有具有特定名称的文件。你的解决方案应放在文件 user/find.c 中

提示

• 查看 user/ls.c，了解如何读取目录。
• 使用递归允许 find 进入子目录。
• 不要递归进入 "." 和 ".."。
• 文件系统的更改在 qemu 的运行之间是持久的；要获取干净的文件系统，请运行 make clean 然后运行 make qemu。
• 你需要使用 C 字符串。可以参考 K&R（C 语言书），例如第 5.5 节。
• 注意，在 C 语言中 == 并不像 Python 那样比较字符串。请使用 strcmp()。
• 将程序添加到 Makefile 的 UPROGS 中。

代码

就按照ls.c模仿写。但是要注意“.”和“…”。

#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;
  for (p = path + strlen(path); p >= path && *p != '/';p--);
  p++;
  if (strlen(p) >= DIRSIZ) return p;
  memmove(buf, p, strlen(p));
  memset(buf+strlen(p), ' ', DIRSIZ-strlen(p));
  buf[strlen(p)] = 0;
  return buf;
}

void find(char *path, char *fileName) {
  char buf[512], *p;
  int fd;
  struct stat st;
  struct dirent de;
  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_FILE:
    if (strcmp(fmtname(path), fileName) == 0) {
      printf("%s\n", path);
    }
    break;
  case T_DIR:
    if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf) {
      printf("find: path too long\n");
      break;
    }
    strcpy(buf, path);
    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;
      find(buf, fileName);
    }
    break;
  }
  close(fd);
}
int main(int argc,char *argv[])
{
    if(argc!=3)
    {
        fprintf(3,"too few or too more arguments\n");
        exit(1);
    }

    char *path = argv[1];
    char *file = argv[2];

    find(path,file);

    exit(0);
}

xargs(moderate)

目的

编写一个简单版本的 UNIX xargs 程序：从标准输入读取行，并为每一行运行一个命令，将该行作为命令的参数。你的解决方案应放在文件 user/xargs.c 中。

提示

• 使用 fork 和 exec 在每一行输入上执行命令。在父进程中使用 wait 等待子进程完成命令。
• 为了逐行读取输入，可以一个字符一个字符地读取，直到出现换行符（\n）。
• kernel/param.h 中声明了 MAXARG，如果需要声明 argv 数组，这可能会很有用。
• 将该程序添加到 Makefile 的 UPROGS 中。
• 对文件系统的更改在 qemu 的多次运行中会持久化；要获得一个干净的文件系统，请运行 make clean，然后再运行 make qemu。

代码

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

int main(int argc, char *argv[]) {
    char* cmd[MAXARG];
    int i;
    for (i = 0; i < argc - 1; i++)
        cmd[i] = argv[i + 1];

    char line[1024];
    int n;

    while ((n = read(0, line, sizeof(line))) > 0) {
        int arg_pos = i;  
        int char_pos = 0;
        cmd[arg_pos] = malloc(1024); 

        for (int k = 0; k < n; k++) {
            if (line[k] == '\n') {
                cmd[arg_pos][char_pos] = '\0';  
                arg_pos++;  
                cmd[arg_pos] = '\0'; 

                if (fork() == 0) {
                    exec(cmd[0], cmd); 
                    fprintf(2, "exec %s failed\n", cmd[0]);
                    exit(1);  
                }

                wait(0);  
                char_pos = 0;  
                arg_pos = i;  

            } else if (line[k] == ' ') {
                cmd[arg_pos][char_pos] = '\0'; 
                arg_pos++; 
                char_pos = 0;
                cmd[arg_pos] = malloc(1024);  

            } else {
                cmd[arg_pos][char_pos++] = line[k]; 
            }
        }
    }

    exit(0);
}

还有optional的练习，肝痛。这个就花了七八个小时了。先放放。而且现在刚好九月，想按照那个课表来，但前面落了些进度，就不做optinal了。