XV6 Lab

Lab1: Xv6 and Unix utilities

xv6的安装以及启动网络上有很详细全面的教程，我就不在此赘述

1.sleep(难度：Easy)

实现xv6的UNIX程序sleep：您的sleep应该暂停到用户指定的计时数。一个滴答(tick)是由xv6内核定义的时间概念，即来自定时器芯片的两个中断之间的时间。

实验中需要将编写好的c语言sleep程序添加到 Makefile 中的UPROGS中；完成之后，make qemu将编译您的程序，并且您可以从xv6的shell运行它。

在c语言中 argc参数代表shell接收到的参数个数，argv就是接收到的具体参数

注意c语言中的头文件引入很可能有互相的依赖，所以引入的顺序是一定的，使用clang需要关闭自动按字母排序的选项

记得make qemu

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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 [time]/n");
		exit(1);
	}
	int time=atoi(argv[1]);
	sleep(time);
	exit(0);
}

2.pingpong（难度：Easy）

编写一个使用UNIX系统调用的程序来在两个进程之间“ping-pong”一个字节，请使用两个管道，每个方向一个。父进程应该向子进程发送一个字节;子进程应该打印“<pid>: received ping”，其中<pid>是进程ID，并在管道中写入字节发送给父进程，然后退出;父级应该从读取从子进程而来的字节，打印“<pid>: received pong”，然后退出。

管道的概念：

管道是一种最基本的IPC机制，作用于有血缘关系的进程之间，完成数据传递。调用pipe系统函数即可创建一个管道。有如下特质：

  1. 其本质是一个文件(实为内核缓冲区)
  2. 由两个文件描述符引用，一个表示读端，一个表示写端。
  3. 规定数据从管道的写端流入管道，从读端流出。

管道的原理: 管道实为内核使用环形队列机制，借助内核缓冲区(4k)实现。

管道的局限性：

① 数据自己读不能自己写。

② 数据一旦被读走，便不在管道中存在，不可反复读取。

③ 由于管道采用半双工通信方式。因此，数据只能在一个方向上流动。

④ 只能在有公共祖先的进程间使用管道。

1
2
3
4
5
6
7
8
9
#include<unistd.h>

/* @param fd,经参数fd返回的两个文件描述符
 * fd[0]为读而打开，fd[1]为写而打开
 * fd[1]的输出是fd[0]的输入
 * @return 若成功，返回0；若出错，返回-1并设置errno(Linux中系统调用的错误)
 */
int pipe(int fd[2]);
int getpid()用来取得目前进程的进程识别码

linux下创建管道可以通过函数pipe来完成。该函数如果调用成功，数组中将包含两个新的文件描述符。

管道两端可分别用描述符fd[0] 以及fd[1]来描述。需要注意的是，管道两端的任务是固定的，一端只能用于读，由描述符fd[0]表示，称其为管道读端；

另一端只能用于写，由描述符fd[1]来表示，称其为管道写端。如果试图从管道写端读数据，或者向管道读端写数据都将导致出错。

管道是一种文件，因此对文件操作的I/O函数都可以用于管道，如read，write等。

管道一旦创建成功，就可以作为一般的文件来使用，对一般文件进行操作的I/O函数也适用于管道文件。

管道的一般用法是，进程在使用fork函数创建子进程前先创建一个管道，该管道用于在父子进程间通信，然后创建子进程，之后父进程关闭管道的读端，子进程关闭管道的写端。父进程负责向管道写数据而子进程负责读数据。当然父进程可以关闭管道的写端而子进程关闭管道的读端。这样管道就可以用于父子进程间的通信，也可以用于兄弟进程间的通信。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int main(int argc, char *argv[]) {
    int p2c[2];
    int c2p[2];
    if (pipe(p2c) < 0) {
        printf("pipe");
        exit(-1);
    }
    if (pipe(c2p) < 0) {
        printf("pipe");
        exit(-1);
    }
    int pid = fork();
    if (pid == 0) {
        // child
        char buf[10];
        read(p2c[0], buf, 10);
        printf("%d: received ping\n", getpid());
        write(c2p[1], "pong", 5);
    } else if (pid > 0) {
        // parent
        write(p2c[1], "ping", 5);
        char buf[10];
        read(c2p[0], buf, 10);
        printf("%d: received pong\n", getpid());
    }
    close(p2c[0]);
    close(p2c[1]);
    close(c2p[0]);
    close(c2p[1]);
    exit(0);
}

3.Primes(素数，难度：Moderate/Hard)

使用管道编写prime sieve(筛选素数)的并发版本

实验前置知识中文翻译

提示：当管道的write端关闭时，read返回零

“当管道的write端关闭时，read返回零”，这指的是当管道的写入端（write端）被关闭后，任何试图从管道的读取端（read端）读取数据的操作如果已经没有更多的数据可读，则会返回0。这里的0并不是表示读到了什么数据，而是表示文件结束（EOF，End Of File）状态。

primes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

void prime(int rd) {
    int n;
    read(
        rd, &n,
        4); // 实验提示：最简单的方法是直接将32位（4字节）int写入管道，而不是使用格式化的ASCII的I/O的体现
    printf("prime %d\n", n);
    int created = 0; // 是否已经创建了管道
    int fd[2]; // 注意实验要求及时关闭文件描述符，因为xv6的系统资源较少
    int num;
    while (read(rd, &num, 4) == 4) {
        if (created == 0) {
            if (pipe(fd) < 0) {
                fprintf(2, "create pipe failed");
                exit(-1);
            };
            created = 1;
            int pid = fork();
            if (pid == 0) {
                close(fd[1]); // 子进程只读
                prime(fd[0]); // 从父进程处读取
                return;
            } else {
                close(fd[0]); // 父进程只写
            }
        }
        if (num % n != 0) {
            if (write(fd[1], &num, 4) < 0) {
                fprintf(2, "write wrong");
                exit(-1);
            };
        }
    }
    // 释放资源
    close(rd);
    close(fd[1]);
    wait(0);
    return;
}

int main(int argc, char *argv[]) {
    int fd[2];
    if (pipe(fd) < 0) {
        fprintf(2, "create pipe failed");
        exit(-1);
    };
    int pid = fork();
    if (pid < 0) {
        fprintf(2, "fork failed");
        exit(-1);
    }
    if (pid != 0) {
        // first
        close(fd[0]);
        for (int i = 2; i <= 35; i++) {
            if (write(fd[1], &i, 4) < 0) {
                fprintf(2, "write wrong");
                exit(-1);
            };
        }
        close(fd[1]);
        wait(0);
        /*
        父进程一旦调用了wait就立即阻塞自己，由wait自动分析是否当前进程的某个子进程已经退出，如果让它找到了这样一个已经变成僵尸的子进程，wait就会收集这个子进程的信息，并把它彻底销毁后返回；如果没有找到这样一个子进程，wait就会一直阻塞在这里，直到有一个出现为止。
        所以在这里父进程会等待子进程结束后一起返回
        wait() 要与fork()配套出现,如果在使用fork()
        之前调用wait(),wait()的返回值则为 - 1,正常情况下wait()
        的返回值为子进程的PID
        如果参数status的值不是NULL，wait就会把子进程退出时的状态取出并存入其中，这是一个整数值（int），指出了子进程是正常退出还是被非正常结束的，以及正常结束时的返回值，或被哪一个信号结束的等信息。
        */
    } else {
        close(fd[1]);
        prime(fd[0]);
        close(fd[0]);
    }
    exit(0);
}

4.find（难度：Moderate）

  • 不要在“.”和“..”目录中递归

  • 注意在C语言中不能像python一样使用“==”对字符串进行比较，而应当使用strcmp()

首先我们需要对ls函数源码进行阅读和学习

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"

char*
fmtname(char *path)//char *是字符串常量的首地址
{
  static char buf[DIRSIZ+1];//DIRSIZ=14是定义在fs.h中文件名的长度
  char *p;

  // Find first character after last slash.
  for(p=path+strlen(path); p >= path && *p != '/'; p--)
    ;
  p++;
	//e.g. local/se/chy在这里获取到的就会是chy,非常好理解
  // Return blank-padded name.
  if(strlen(p) >= DIRSIZ)
    return p;
  memmove(buf, p, strlen(p));
  /*C 库函数 void *memmove(void *str1, const void *str2, size_t n) 从 str2 复制 n 个字符到 str1，但是在重叠内存块这方面，memmove() 是比 memcpy() 更安全的方法。如果目标区域和源区域有重叠的话，memmove() 能够保证源串在被覆盖之前将重叠区域的字节拷贝到目标区域中，复制后源区域的内容会被更改。如果目标区域与源区域没有重叠，则和 memcpy() 函数功能相同。
  原型：void *memmove(void *str1, const void *str2, size_t n)
  */
  memset(buf+strlen(p), ' ', DIRSIZ-strlen(p));//将剩下的位置用空格填充，便于对齐
    /*e.g.
    conf    grade-lab-util  kernel   Makefile  README
    fs.img  gradelib.py     LICENSE  mkfs      user
    */
  return buf;
}

void
ls(char *path)
{
  char buf[512], *p;
  int fd;
  struct dirent de;
  /*
  定义于fs.h中，为目录项
      struct dirent {
      ushort inum;        ->文件的inode编号
      (inode是文件系统中用来存储文件元数据的数据结构，它包含了文件的大小、权限、所有者等信息。			  inode编号是文件在文件系统内部的唯一标识符。)
      char name[DIRSIZ];  ->文件的名字
    };
  */
  struct stat st;
  /*
      struct stat {
        int dev;     // 文件所在文件系统的磁盘设备号
        uint ino;    // 文件的inode编号
        short type;  // 文件类型
        short nlink; // 文件的硬链接数
        uint64 size; // 文件的大小（以字节为单位）
    };
  */
  if((fd = open(path, 0)) < 0){    //0这里是只读模式
    /*
    int open(const char *pathname, int flags);
    int open(const char *pathname, int flags, mode_t mode);
	在open函数中第一个参数pathname是指向想要打开的文件路径名，或者文件名。我们需要注意的是，这个路径名是绝对路径名。文件名则是在当前路径下的。
	flags参数表示打开文件所采用的操作，我们需要注意的是：必须指定以下三个常量的一种，且只允许指定一个
    O_RDONLY：只读模式
    O_WRONLY：只写模式
    O_RDWR：可读可写
    还有其他的参数可以与以上三个参数用 | 进行连接表示更多的模式信息
    mode参数表示设置文件访问权限的初始值，和用户掩码umask有关，比如0644表示-rw-r–r–，也可以用 
    S_IRUSR、S_IWUSR等宏定义按位或起来表示，详见open(2)的Man Page。
    要注意的是，有以下几点
	文件权限由open的mode参数和当前进程的umask掩码共同决定。
    第三个参数是在第二个参数中有O_CREAT时才作用，如果没有，则第三个参数可以忽略
    */
    fprintf(2, "ls: cannot open %s\n", path);
    //文件描述符: 1是标准输出（stdout）, 2是标准错误输出（stderr）, 0是标准输入（stdin）
    return;
  }

  if(fstat(fd, &st) < 0){
      /*
      int fstat (int filedes, struct *buf);
      fstat() 用来将参数filedes 所指向的文件状态复制到参数buf 所指向的结构中(struct stat), fstat() 		与stat() 作用完全相同，不同之处在于传入的参数为已打开的文件描述符。
      执行成功返回0，失败返回-1，错误代码保存在errno中
      */
    fprintf(2, "ls: cannot stat %s\n", path);
    close(fd);
    return;
  }

  switch(st.type){
  case T_FILE:  //文件
    printf("%s %d %d %l\n", fmtname(path), st.type, st.ino, st.size);
    break;

  case T_DIR:  //文件夹
    if(strlen(path) + 1(->"/") + DIRSIZ + 1(->"\0") > sizeof buf){
      printf("ls: path too long\n");
      break;
    }
    strcpy(buf, path);
    p = buf+strlen(buf);
    *p++ = '/';
    // e.g. home -> home/
    //上面三行代码将是把路径格式化，变为path/，接着while(read(fd, &de, sizeof(de)) == sizeof(de))循环读取DIR文件的内容，并且将DIR文件每一个结构体格式化到buf里面：      
    while(read(fd, &de, sizeof(de)) == sizeof(de)){  //记得父子进程共享文件描述符
      if(de.inum == 0)
        continue;
      memmove(p, de.name, DIRSIZ);
      p[DIRSIZ] = 0;
      if(stat(buf, &st) < 0){
        /*
        定义函数:    int stat(const char *file_name, struct stat *buf);
		函数说明:    通过文件名filename获取文件信息，并保存在buf所指的结构体stat中
		返回值:      执行成功则返回0，失败返回-1，错误代码存于errno
        */
        printf("ls: cannot stat %s\n", buf);
        continue;
      }
      printf("%s %d %d %d\n", fmtname(buf), st.type, st.ino, st.size);
    }
    break;
  }
  close(fd);
}

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

  if(argc < 2){
    ls(".");
    exit(0);
  }
  for(i=1; i<argc; i++)
    ls(argv[i]);
  exit(0);
}

struct dinode定义描述了存储在磁盘上的inode结构。inode（节点索引）是文件系统中的一个重要概念，用于存储文件的元数据。下面是对这个结构的详细解释：

1
2
3
4
5
6
7
8
struct dinode {
    short type;           // 文件类型
    short major;          // 设备类型的主要编号（仅对于设备文件）
    short minor;          // 设备类型的次要编号（仅对于设备文件）
    short nlink;          // 文件系统中指向该inode的链接数量
    uint size;            // 文件的大小（以字节为单位）
    uint addrs[NDIRECT+1];   // 数据块地址数组
};

结构成员解释

  1. short type：

    • 类型：short

    • 含义：文件的类型。通常是一个枚举值，表示文件是普通文件、目录、符号链接、块设备文件、字符设备文件等。例如：

      1
      2
      3
      4
      5
      #define T_FILE 1
      #define T_DIR 2
      #define T_SYMLINK 3
      #define T_BLOCKDEV 4
      #define T_CHARDEV 5

  2. short major 和 short minor：

    • 类型：short
    • 含义：设备的主要编号和次要编号。这些字段只在文件类型为设备文件（如块设备或字符设备）时有效。主要编号和次要编号一起唯一地标识了一个硬件设备。

  3. short nlink：

    • 类型：short
    • 含义：指向该inode的硬链接数量。如果一个文件有多个名字（即在不同的目录中有多个指向同一inode的链接），则nlink字段的值会相应增加。

  4. uint size：

    • 类型：uint
    • 含义：文件的大小（以字节为单位）。这对于普通文件、符号链接等有意义，而对于目录或其他特殊文件，这个字段可能有不同的意义。

  5. uint addrs[NDIRECT+1]：

    • 类型：uint 数组
    • 含义：数据块地址数组。这个数组包含了指向文件数据的实际磁盘块地址。NDIRECT通常定义为一个具体的数值，表示直接块的数量。数组中最后一个元素（addrs[NDIRECT]）通常用于指向间接块（单级、多级间接块等），以支持更大的文件。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"

void search(char *path, char *target);

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), 0, DIRSIZ - strlen(p)); //此处放0为了方便后面比较并且可以大部分复用ls的代码
    return buf;
}
int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(2, "Usage:find <pathname> <filename>\n");
        exit(1);
    }
    search(argv[1], argv[2]);
    exit(0);
}
void search(char *path, char *target) {
    char *p;
    int fd;
    struct dirent de;
    struct stat st;
    if ((fd = open(path, 0)) < 0) {
        fprintf(2, "open err\n");
        exit(1);
    }
    if (fstat(fd, &st) < 0) {
        fprintf(2, "fstat err\n");
        exit(1);
    }

    switch (st.type) {
    case T_FILE:
        if (!strcmp(target, fmtname(path))) { // strcmp到任何一个字符串为0处就停止，所以不会越界
            printf("%s\n", path);
        }
        break;
    case T_DIR:
        p = path + strlen(path); //p指向path最后一个字符--也就是0
        *p++ = '/';
        while (read(fd, &de, sizeof(de)) == sizeof(de)) {
            if (de.inum == 0)
                continue;
            memmove(p, de.name, DIRSIZ);
            p[DIRSIZ] = 0;
            if (strcmp(p, ".") && strcmp(p, "..")) //防止在./..中进行递归导致递归没有终结
                search(path, target);
            memset(p, 0, DIRSIZ); //复用
        }
    }
    close(fd);
}

理解了ls的代码就会发现find的代码非常容易编写，其实就是ls加上了一点点比较就可以实现

5.xargs（难度：Moderate）

既然我们要仿照实现一个xargs，我们就先看看linux中的args是什么样的

xargs 命令教程

Linux xargs 命令

命令行参数和标准输入的区别

一般来说，向程序传递数据可以采用参数传递的方式，在调用的同时将数据一并传递；或者使用标准输入，在程序启动后通过控制台键入等方式输入数据。下面我们通过一个简单的例子说明二者的区别。我们实现一个简单的 echo 命令，分别采用参数传递和标准输入两种传递数据的方式，接受一个字符串并打印。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// echo1.c Argument passing
#include <stdin.h>
int main(int argc, char* argv[])
{
	printf("%s\n", argv[1]);
	return 0;
}

// echo2.c Standard input
#include <stdio.h>
int main(int argc, char* argv[])
{
	char str[128];
	scanf("%s", str);
	printf("%s\n", str);
	return 0;
}

要注意这两个程序有不同的启动方式。

1
2
3
4
5
~ % ./echo1 tauyoung	# 启动的同时一并传递参数
tauyoung				# 打印传递的参数值
~ % ./echo2				# 启动时不接受任何参数
tauyoung				# 在控制台通过键盘输入
tauyoung				# 打印输入的数据

在大部分情况下我们可以采用任意一种方式传递数据，只要程序能够正常运行。但是，在配合其他程序或者脚本使用时，也应该采用相应的方式启动。例如，我们希望通过我们实现的 echo 输出当前用户，下面是这两个程序的正确启动方式：

1
2
3
4
~ % ./echo1 $(whoami)	# 将用户名作为参数传递给 echo1
tauyoung
~ % whoami | ./echo2	# 通过管道将用户名传递给 echo2 的标准输入
tauyoung
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/param.h"

int readline(char *new_argv[32], int curr_argc) {
    char buf[1024];
    int n = 0;
    while (read(0, buf + n, 1) == 1) {
        if (n == 1023) {
            fprintf(2, "argument is too long\n");
            exit(-1);
        }
        if (buf[n] == '\n') {
            break;
        }
        n++;
    }
    buf[n] = 0;
    if (n == 0)
        return 0;
    int offset = 0;
    while (offset < n) {
        new_argv[curr_argc++] = buf + offset;
        while (buf[offset] != ' ' && offset < n) {
            offset++;
        }
        while (buf[offset] == ' ' && offset < n) {
            buf[offset++] = 0;
        }
    }
    return curr_argc;
}

int main(int argc, char const *argv[]) {
    if (argc < 2) {
        printf("Usage: xargs [command]\n");
        exit(-1);
    }
    char *command = malloc(strlen(argv[1]) + 1);
    char *new_argv[MAXARG];
    strcpy(command, argv[1]);
    for (int i = 1; i < argc; ++i) {
        new_argv[i - 1] = malloc(strlen(argv[i]) + 1);
        strcpy(new_argv[i - 1], argv[i]);
    }

    int curr_argc;
    while ((curr_argc = readline(new_argv, argc - 1)) != 0) {
        new_argv[curr_argc] = 0;
        int pid = fork();
        if (pid < 0) {
            fprintf(2, "fork failed\n");
            exit(-1);
        }
        //printf("%d\n", pid);
        if (pid == 0) {
            exec(command, new_argv); // 保证每个进程都只有一个子进程，所以不会产生僵尸进程
            fprintf(2, "exec failed\n");
            exit(-1);
        }
        wait(0);
    }
    for (int i = 0; i < curr_argc; ++i) {
        free(new_argv[i]);
    }
    free(command);
    exit(0);
}