Ganliber's Home
0%

MIT 6.S081 lab1 utilities

Posted on Edited on In Disqus:
MIT 6.S081 Lab1

Preparation

In WSL2, I have to move ubuntu-18.04 from C disk to D disk, by using tool LxRunOffline, everything seems easier.

1
2
3
4
5
6
7
8
9
10
11
12
# 查看所有的WSL系统
❯ .\LxRunOffline.exe list
Ubuntu-18.04
# 查看所在文件目录
❯ .\LxRunOffline.exe get-dir -n Ubuntu-18.04
E:\WSL\ubuntu1804
# 查看windows_user_name
❯ whoami
# 添加权限
❯ icacls E:\WSL\ubuntu2004\ /grant "windows_user_name:(OI)(CI)(F)"
# 移动目录
❯ .\LxRunOffline.exe move -n Ubuntu-18.04 -d E:\WSL\ubuntu1804

Install dependencies:

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

problems

The version of QEMU on “buster” is too old, so you’d have to get that separately.

qemu-system-misc fix

At this moment in time, it seems that the package qemu-system-misc has received an update that breaks its compatibility with our kernel. If you run make qemu and the script appears to hang after

1
qemu-system-riscv64 -machine virt -bios none -kernel kernel/kernel -m 128M -smp 3 -nographic -drive file=fs.img,if=none,format=raw,id=x0 -device virtio-blk-device,drive=x0,bus=virtio-mmio-bus.0

you’ll need to uninstall that package and install an older version:

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

IF YOU ARE WORKING ON UBUNTU 20.04, THERE WILL NOT BE SO MANY ERRORS, THROW AWAY YOUR UBUNTU 18.04 AND UBUNTU 22.04!!!

lab 1

Xv6 and Unix utilities

  • system call provided by xv6

  • file descriptor

    On a Unix-like operating system, the first three file descriptors, by default, are STDIN, STDOUT, and STDERR.

    Name File descriptor Description Abbreviation
    Standard input 0 The default data stream for input, for example in a command pipeline. In the terminal, this defaults to keyboard input from the user. stdin
    Standard output 1 The default data stream for output, for example when a command prints text. In the terminal, this defaults to the user’s screen. stdout
    Standard error 2 The default data stream for output that relates to an error occurring. In the terminal, this defaults to the user’s screen. stderr

sleep

  • create a file : user/sleep.c

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

    int
    main(int argc, char *argv[])
    {
        if(argc < 2){
            //If the user forgets to pass an argument, sleep should print an error message.
            fprintf(2, "usage: sleep [number]\n");
            exit(1);
        }
        if (argc == 2)
        {
            /* code */
            int interval = atoi(argv[1]);
            printf("(nothing happens for a little while)\n");
            sleep(interval);
        } else {
            fprintf(2, "Too many arguments!\n");
            exit(1);
        }
        exit(0);
    }

  • Add line $U/_sleep\ behind the UPROGS in Makefile

  • Compile 

    1
    make qemu

  • Testing for grade

    1
    2
    3
    4
    5
    $ ./grade-lab-util sleep   
    make: 'kernel/kernel' is up to date.
    == Test sleep, no arguments == sleep, no arguments: OK (0.8s) 
    == Test sleep, returns == sleep, returns: OK (0.8s) 
    == Test sleep, makes syscall == sleep, makes syscall: OK (1.1s)

  • Pay attention!

    No Error

    1
    2
    3
    #include "kernel/types.h"
    #include "kernel/stat.h"
    #include "user/user.h"

    Errors !

    1
    2
    3
    #include "user/user.h"
    #include "kernel/types.h"
    #include "kernel/stat.h"

    Errors are as follows : “user/user.h” are lack of the definitions of uint because you include “user/user.h” before the “kernel/types.h” where uint is defined as unsigned int.

    1
    2
    3
    4
    5
    6
    ./user/user.h:42:36: error: unknown type name ‘uint’; did you mean ‘int’?
       42 | void *memcpy(void *, const void *, uint);
          |                                    ^~~~
          |                                    int
    cc1: all warnings being treated as errors
    make: *** [<builtin>: user/sleep.o] Error 1

pingpong

  • Same as above

    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
    int main(int argc, char const *argv[])
    {
        int p1[2]; int p2[2]; // create a pipe
        pipe(p1); pipe(p2); // create a pipe and return its fds in p, dp[0]=>read; dp[1]=>write
        if (fork()==0) {
            // child process
            close(0); // close stdin and bind it to pipe
            dup(p1[0]); //子进程将管道的读端口拷贝在描述符0上，关闭 p1中的描述符
            			// 从小到大找没开的文件描述符, 此时是0(前面stdin关了)
            close(p1[0]);
            close(p1[1]);
            char buffer_ch[2];
            read(0, buffer_ch, 1);// read(fd, buf, n) fd -> buf (n bytes upmost)
            printf("%d: received ping\n", getpid());

            write(p2[1],buffer_ch, 1);// send back
            close(p2[0]);
            close(p2[1]);
            exit(0); // Indispensable, u can't miss this line!
        } else {
            // father process
            write(p1[1],"ccc",1); // write(fd, buf) buf -> fd (n bytes upmost)
            close(p1[0]);
            close(p1[1]);

            close(0);
            dup(p2[0]);
            close(p2[0]);
            close(p2[0]);
            char buffer_fa[2];
            read(0, buffer_fa, 1);
            printf("%d: received pong\n",getpid());
            exit(0); // u can't miss this line!
        }
        return 0;
    }

  • For simplifying:

    No need to borrow fd from the stdin(0), stdout(1), stderr(0)

    You can take up 0 or 2, but not 1, because you need to print out the right result.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int p1[2]; // create a pipe
    int p2[2];
    pipe(p1); // create a pipe and return its fds in p, p[0]=>read pipe; p[1]=>write pipe
    pipe(p2);
    if (fork()==0) {
        char buffer_ch[2];
        read(p1[0], buffer_ch, 1);// read(fd, buf, n) fd -> buf (n bytes upmost)
        printf("%d: received ping\n", getpid());
        write(p2[1],buffer_ch, 1);// send back
        exit(0); // Indispensable, u can't miss this line!
    } else {
        write(p1[1],"ccc",1); // write(fd, buf) buf -> fd (n bytes upmost)
            				// 向管道写 c
        char buffer_fa[2];
        read(p2[0], buffer_fa, 1);
        printf("%d: received pong\n",getpid());
        exit(0); // u can't miss this line!
    }

  • For the other perspective:

    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
    if (fork()==0) {
        // child process
        close(2); // close stdin and bind it to pipe
        dup(p1[0]); // 子进程将管道的读端口拷贝在描述符0上,关闭 p1中的描述符
        close(p1[0]);
        close(p1[1]);
        char buffer_ch[2];
        read(2, buffer_ch, 1);// read(fd, buf, n) fd -> buf (n bytes upmost)
        printf("%d: received ping\n", getpid());
      
        write(p2[1],buffer_ch, 1);// send back
        close(p2[0]);
        close(p2[1]);
        exit(0); // Indispensable, u can't miss this line!
    } else {
        // father process
      
        write(p1[1],"ccc",1); // write(fd, buf) buf -> fd (n bytes upmost)
        close(p1[0]);
        close(p1[1]);
        
        close(2); <-- 关stderr也行
        dup(p2[0]);
        close(p2[0]);
        close(p2[0]);
        char buffer_fa[2];
        read(2, buffer_fa, 1);
        printf("%d: received pong\n",getpid());
        exit(0); // u can't miss this line!
    }

  • Testing and grade

    1
    2
    3
    $ ./grade-lab-util pingpong
    make: 'kernel/kernel' is up to date.
    == Test pingpong == pingpong: OK (1.6s)

primes

  • Schematic

  • pseudocode

    1
    2
    3
    4
    5
    6
    p = get a number from left neighbor
    print p
    loop:
        n = get a number from left neighbor
        if (p does not divide n)
            send n to right neighbor

  • AC code

    1. 管道用来过滤第一个质数的倍数（筛法）
    2. 父进程需要调用wait(0)等待子进程结束，否则会导致执行流混乱
    3. fd不够用，所以对于子进程，每次写完过滤好的数据之后，需要关闭和父进程共享的pipe的读端口，也要关闭和子进程共享的pipe的写端口
    4. 由于read会阻塞，因此每次多写入一个-1表示所有数据已经传递完成跳出循环，子进程同时把pipe的读端口给关闭了
    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
    int p[35][2];
    int index = 0; // children fd number
    int main(int argc, char const *argv[])
    {
        pipe(p[index]); // create pipe for child
        printf("prime 2\n");
        int i;
        for (i=3; i<=35; i++) {
            if(i%2 != 0){
                write(p[index][1], &i, 4);
            }
        }
        i = -1;
        write(p[index][1], &i, 4); // 终止信号
        close(p[index][1]);
        if (fork()==0) {
            child_process_handler(index);
            exit(0);
        } else {
            wait(0);//等待子进程结束
            exit(0);
        }
        return 0;
    }

    void child_process_handler(int index) {
        int number;
        int flw_num; // following numbers
        read(p[index][0], &number, 4);
                 // read returns zero when the write-side of a pipe is closed.
                 // 4 bytes -> integer
        if (number == -1) {
            //已经全部结束
            return;
        }
        printf("prime %d\n", number);

        pipe(p[index+1]);//不要放到判断 number==-1上面
        while(read(p[index][0], &flw_num, 4)!=-1) {
            // not closed by that pipe, but it will block.
            if (flw_num == -1) {
                break;
            }
            if (flw_num%number != 0) {
                write(p[index+1][1], &flw_num, 4);
            }
        }
        flw_num = -1;
        write(p[index+1][1], &flw_num, 4);// 终止信号

        close(p[index][0]);//关闭上一个读的
        close(p[index+1][1]);//关闭下一个写的

        if (fork()==0) {
            child_process_handler(index+1);
            exit(0);
        } else {
            wait(0);//等待子进程结束
            exit(0);
        }
        return;
    }

find

  • fmtname

    1
    fmtname(path) return single-filename

  • fstat : fstat 可以获取一个文件描述符指向的文件的信息, 同一个文件（称为 inode）可能有多个名字，称为连接 (links)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    #define T_DIR  1
    #define T_FILE 2
    #define T_DEV  3
    // Directory
    // File
    // Device
    struct stat {
           short type;  // Type of file
           int dev;     // File system’s disk device
           uint ino;    // Inode number
           short nlink; // Number of links to file
           uint size;   // Size of file in bytes
    };

  • dir struct

    1
    2
    3
    4
    5
    #define DIRSIZ 14
    struct dirent {
      ushort inum;
      char name[DIRSIZ];
    };

  • memmove

    1
    C 库函数 void *memmove(void *str1, const void *str2, size_t n) 从 str2 复制 n 个字符到 str1，但是在重叠内存块这方面，memmove() 是比 memcpy() 更安全的方法

  • find

    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
    void find(char *path, char *fname) {
        struct dirent de;
        struct stat st;
        int fd;
        char buf[512], *new_path; // new path pointer
        if ((fd = open(path, 0))<0) {
            fprintf(2, "find: path '%s' doesn't exist.\n", path);
            return;
        }
        if (fstat(fd, &st) < 0) {
            fprintf(2, "find: cannot stat %s\n", path);
            close(fd);
            return;
        }
        char *pname;
        char *pp;
        switch (st.type)
        {
        case T_FILE:
            pname = fmtname(path);
            pp = pname;
            //printf("pname %s?\n", pp);
            while(1) {
                if (*pp == 32) break;
                if (*pp == 0) break;
                //printf("%d ", *pp);
                pp++;
            }
            *pp = 0;
            //printf("pname %s? fname %s?\n", path, fname);
            if (strcmp(pname, fname) == 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);
            new_path = buf + strlen(buf);
            *new_path++ = '/';
            while(read(fd, &de, sizeof(de)) == sizeof(de)) {
                if (de.inum == 0) { // 文件夹下的没有文件
                    continue;
                }
                memmove(new_path, de.name, DIRSIZ);
                new_path[DIRSIZ] = 0;
                if (stat(buf, &st) < 0) {
                    printf("find: cannot stat %s\n", buf);
                    continue;
                }
                char * fn = fmtname(buf);
                //清除DIRSIZ的空格
                char * p = fn;
                while(*p != ' ' && *p != '\0') {
                    p++;
                }
                *p = '\0';
                if (strcmp(fn, ".") == 0 || strcmp(fn, "..") == 0) {
                    continue;
                } else {
                    find(buf, fname);
                }
            }
            break;
        }
        close(fd);
        return;
    }

xargs

hints:

  • Use fork and exec to invoke the command on each line of input. Use wait in the parent to wait for the child to complete the command.
  • To read individual lines of input, read a character at a time until a newline (‘\n’) appears.
  • kernel/param.h declares MAXARG, which may be useful if you need to declare an argv array.
  • Add the program to UPROGS in Makefile.
  • Changes to the file system persist across runs of qemu; to get a clean file system run make clean and then make qemu.
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
int main(int argc, char *argv[]) {
    if (argc < 2) {
        fprintf(2, "miss arguments!\n");
        exit(0);
    } else {
        //printf("\ninit arguments :\n");

        child_argv[0] = argv[1];

        for( int j = 1; j < argc; j++) {
            //printf("> %s\n", argv[j]);
            child_argv[j-1] = argv[j]; 
                // copy initial arguments
                // 这些不是在堆区申请的因此后来不能 free
        }
        char input[512]; 
            // following argv for xargs cmd
            // find . b | xargs grep hello, every line output by "find . b" will be
            // feeded to "grep hellp ./b" for example 
        char *p = (char *)malloc(1);
        int i = 0;
        int child_argc = argc-1;
        // find . b | ... 通过管道把标准输出的内容变为 stdin 给 xargs
        while(1) {
            int ret = read(0, p, 1);
            //printf("> read return value is %d\n", ret);
            if(ret <= 0) {
                exit(0);
            }
            if (*p == ' ') {
                input[i] = '\0';
                if (child_argc >= MAXARG) {
                    fprintf(2, "too much arguments!\n");
                    exit(0);
                }
                child_argv[child_argc] = (char*)malloc(MAXLENGTH);
                strcpy(child_argv[child_argc], input);
                child_argc++;
                //准备接收下一个参数
                i = 0;
                memset(input, '\0', sizeof(input));
            } else if (*p == '\n') {
                input[i] = '\0';
                if (child_argc >= MAXARG) {
                    fprintf(2, "too much arguments!\n");
                    exit(0);
                }
                child_argv[child_argc] = (char*)malloc(MAXLENGTH);
                strcpy(child_argv[child_argc], input);
                child_argc ++;
                child_argv[child_argc] = 0;
                //准备执行
                if (fork()==0) {
                    // child process
                    exec(argv[1], child_argv);
                    exit(0);
                } else {
                    // parent process
                    wait((int *)0); //等待子进程结束
                    //释放堆区
                    //printf("argc-1: %d\tchild argc: %d\n", argc-1, child_argc);
                    for (int x = argc-1; x < child_argc; x++) {
                        //printf("To be freed: %s\n", child_argv[x]);
                        free(child_argv[x]);
                    }
                    //准备接收第二行
                    child_argc = argc - 1;
                    input[i] = '\0';
                    i = 0;
                    continue;
                }                            
            } else {
                input[i] = *p;
                i ++;
            }
        }
        
        free(p);
    }
    return 0;
}

Addition

concurrency

  • CSP : communicating sequential processes

reference