nyyyddddn

xv6_and_unix_utilities

misc
2024/05/23

Xv6 and Unix utilities

好哦，完成 mit 6.1810 2023 中 lab :Xv6 and Unix utilities了，准备开始下一章的学习了，xv6还是挺好玩的

sleep

根据题目描述，和 user/ 中的其他程序的逻辑可以发现 命令行参数传递是通过 main的argc 和argv去传递的，其中argc 中存储着参数的个数，argv存储着参数名，没有参数的时候argc = 1，argv[0] = program_name。
然后在 “user/user.h” 中有sleep 函数
所以 只需要直接调用sleep函数就好了, 把time上限也做一个设置（防止睡死过去了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int main(int argc, char *argv[]){
    
    int time = 0;

    if (argc == 1 || argc > 2){
        printf("Error: Please provide the number of seconds to sleep\n e.g. sleep 5\n");
        exit(1);
    }

    time = atoi(argv[1]);
    if (time > 0 && time < 0x1000){
        printf("Zzzzzzzzz.....\n");
        sleep(time);
    }
    exit(0);
}

然后在Makefile中 添加 sleep这个文件 就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
UPROGS=\
	$U/_cat\
	$U/_echo\
	$U/_forktest\
	$U/_grep\
	$U/_init\
	$U/_kill\
	$U/_ln\
	$U/_ls\
	$U/_mkdir\
	$U/_rm\
	$U/_sh\
	$U/_stressfs\
	$U/_usertests\
	$U/_grind\
	$U/_wc\
	$U/_zombie\
	$U/_sleep\

pingpong

通过阅读资料可以发现，pingpong 可以分解为两个问题，分别是 如何创建子进程，父子进程之间如何通信
创建子进程可以使用 fork() 函数创建，进程之间通信可以使用pipe 这个函数去创建一个管道，管道的本质就是内存共享，不同进程可以共享同一块内存
管道是单向的，其中 int pN[2] = pipe() 这段代码中，pN[0] 是 读端，pN[1] 是写端，所以 两个进程互相通信 需要两个管道

那 如何判断父子进程呢？ 可以通过 fork的返回值来判断，为了保证执行顺序按照 ping - > pong 这个顺序去执行，在 ping 后 父进程应该等待子进程 senddata过来 才输出pong，这时候可以使用wait函数来解决这个问题

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
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

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

    // pN[0] read pN[1] write
    int p1[2]; // pipe from parent to child 
    int p2[2]; // pipe from child to parent
    
    pipe(p1);
    pipe(p2);

    
    int pid = fork();
    if (pid > 0){
        char byte = 'A';
        write(p1[1],&byte,1);

        wait(0); // wait child process exit
        read(p2[0],&byte,1);

        if(byte == 'B'){
            printf("%d: received pong\n", getpid());
        }

        close(p1[1]);
        close(p2[0]);
        exit(0);
    }
    else if (pid == 0){
        char buf;
        read(p1[0],&buf,1);

        if(buf == 'A'){
            printf("%d: received ping\n", getpid());
            buf = 'B';
            write(p2[1],&buf,1);
        }
        close(p1[0]);
        close(p2[1]);
        exit(0);
    }
    else{
        printf("Error: fork error!\n");
        close(p1[0]);
        close(p1[1]);
        close(p2[0]);
        close(p2[1]);
        exit(0);
    }
}

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
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

void sieve(int read_fd) {
    int p;
    
    if (read(read_fd, &p, sizeof(int)) == 0) {
        close(read_fd);
        exit(0);
    }
    printf("prime %d\n", p);

    int next_read_fd[2];
    pipe(next_read_fd);

    if (fork() == 0) {
        close(next_read_fd[1]);
        sieve(next_read_fd[0]);
    } else {
        close(next_read_fd[0]);
        int num;
        while (read(read_fd, &num, sizeof(int)) != 0) {
            if (num % p != 0) {
                write(next_read_fd[1], &num, sizeof(int));
            }
        }
        close(next_read_fd[1]);
        close(read_fd);
        wait(0);
        exit(0);
    }
}

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

    int nums[34];
    for (int i = 0; i < 34; i++) {
        nums[i] = i + 2;
    }

    int initial_fd[2];
    pipe(initial_fd);

    if (fork() == 0) {
        close(initial_fd[1]);
        sieve(initial_fd[0]);
    } else {
        close(initial_fd[0]);
        for (int i = 0; i < 34; i++) {
            write(initial_fd[1], &nums[i], sizeof(int));
        }
        close(initial_fd[1]);
        wait(0);
        exit(0);
    }

    return 0;
}

find

find，想到的搜索策略是bfs？从传过来的path判断 path里每个项的类型，如果是dir就递归下去，如果是file就判断file name是不是要find的目标，如果是. ..就跳过，所以能得到几个新的问题，怎么样获取path里的条目有什么，这些条目的类型是什么

ls.c source code

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
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"
#include "kernel/fcntl.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
ls(char *path)
{
  char buf[512], *p;
  int fd;
  struct dirent de;
  struct stat st;

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

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

  switch(st.type){
  case T_DEVICE:
  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 > sizeof buf){
      printf("ls: 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)
        continue;
      memmove(p, de.name, DIRSIZ);
      p[DIRSIZ] = 0;
      if(stat(buf, &st) < 0){
        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);
}

有两个 比较关键的函数和结构体
stat 和 fstat 这两个函数

嗯，通过阅读ls.c可以发现想要获得一个条目是目录 还是文件，可以通过 int fd = open(“current_dir”,0);struct stat st; fstat(fd,&st); 来获得
这是struct stat的定义

1
2
3
4
5
6
7
8
9
10
11
12
#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
};

只需要判断 stat.type就能知道条目的类型是 directory 还是file 还是 Device
可以通过读fd的方式来获得条目的信息，用struct dirent 去存储条目的信息

1
2
3
4
5
6
7
8
9
10
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) {
            fprintf(2, "Error: findcannot stat %s\n", buf);
            continue;
        }

struct dirent的定义

1
2
3
4
5
6
7
// Directory is a file containing a sequence of dirent structures.
#define DIRSIZ 14

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

通过 dirent.name 可以获得条目的名字

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
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"
#include "kernel/fcntl.h"

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

    // open path
    if((fd = open(path, 0)) < 0) {
        fprintf(2, "Error: find cannot open %s\n", path);
        return;
    }

    // get directory statistics
    if(fstat(fd, &st) < 0) {
        fprintf(2, "Error: find cannot stat %s\n", path);
        close(fd);
        return;
    }

    // ensure it is a directory
    if(st.type != T_DIR) {
        fprintf(2, "Error: find %s is not a directory\n", path);
        close(fd);
        return;
    }

    // read the directory entries
    strcpy(buf, path);
    p = buf + strlen(buf);
    *p++ = '/';
    
    // get each item
    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) {
            fprintf(2, "Error: findcannot stat %s\n", buf);
            continue;
        }
        // Skip "." and ".."
        if(strcmp(de.name, ".") == 0 || strcmp(de.name, "..") == 0)
            continue;
        if(st.type == T_DIR) {
            // find sub directory
            find(buf, filename);
        } else if(st.type == T_FILE) {
            // find the file
            if(strcmp(de.name, filename) == 0) {
                printf("%s\n", buf);
            }
        }
    }
    close(fd);
}

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

    if(argc < 3) {
        fprintf(2, "e.g. find <path> <filename>\n");
        exit(1);
    }
    find(argv[1], argv[2]);

    exit(0);
}

xargs

通过分析他给的样例加搜索可以发现 xargs是一个批处理 args的命令，其作用是从 前一个进程的输出中args，每个arg以 ‘ ‘ ‘\n’分割，批量的处理这些arg
| 符号在shell中可以做到将前一个进程的 fd 1 重定向到后一个进程的fd 0中，本质上是通过dup 通过交换进程的文件描述符实现的

所以处理的策略是，从标准输入中读取数据，读到\n或者 ‘ ‘表示读完一个arg了，用fork去创建一个子进程，将args传递过去执行

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
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"
#include "kernel/fcntl.h"

#define MAXARGS 0x20
#define BUFSIZE 0x500

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

    char buf[BUFSIZE];
    int input_data_len = 0;
    char *args[MAXARGS];
    int i;

    if (argc == 1) {
        fprintf(2, "e.g. find . | xargs file\n");
        exit(1);
    }

    if (argc > MAXARGS - 5) {
        fprintf(2, "Error: too many arguments\n");
        exit(1);
    }

    for (i = 0; i < argc; i++) {
        args[i] = argv[i];
    }

    while (read(0, buf + input_data_len, 1) == 1) {

        if (buf[input_data_len] == '\n' || buf[input_data_len] == ' ') {
            buf[input_data_len] = 0;
            args[argc] = buf;
            args[argc + 1] = 0;

            if (fork() == 0) {
                exec(argv[1], args + 1);
                fprintf(2, "exec failed\n");
                exit(1);
            } else {
                wait(0);
            }

            input_data_len = 0;
        } else {
            input_data_len++;
            if (input_data_len >= BUFSIZE - 1) {
                fprintf(2, "Error: input too long\n");
                exit(1);
            }
        }
    }

    if (input_data_len > 0) {
        buf[input_data_len] = 0;
        args[argc] = buf;
        args[argc + 1] = 0;

        if (fork() == 0) {
            exec(argv[1], args);
            fprintf(2, "exec failed\n");
            exit(1);
        } else {
            wait(0);
        }
    }

    exit(0);
}

Author：nyyyddddn

Link：https://nyyyddddn.github.io/2024/05/23/xv6-and-unix-utilities/

Publish date：May 23rd 2024, 2:47:51 am

Update date：August 25th 2024, 1:07:01 am

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. Xv6 and Unix utilities
    1. 1.1. sleep
    2. 1.2. pingpong
    3. 1.3. primes
      1. 1.3.1.
    4. 1.4. find
    5. 1.5. xargs
Total : 58
2024
2023
Invalid date
2023
ctf writeup misc