lab1-Utils

Lab 1：Unix utilities

课程地址：https://pdos.csail.mit.edu/6.828/2020/schedule.html
Lab 地址：https://pdos.csail.mit.edu/6.828/2020/labs/util.html
代码仓库：https://github.com/ajackchan/my-xv6-riscv/tree/util

sleep
pingpong
primes
find
xargs

sleep

编写一个 sleep 程序，让它在 xv6 系统中根据用户指定的时间暂停运行，时间单位为系统时钟的周期数。

代码实现如下：

#include "kernel/types.h"  
#include "kernel/stat.h"  
#include "user/user.h"  
      
#ifndef STDERR  
#define STDERR 2  
#endif  
      
int main(int argc,char *argv[])  
{     
    if(argc != 2){  
        fprintf(STDERR,"usage: sleep <second>\n");  
        exit(1);  
    }  
      
    //字符串转整数  
    int time = atoi(argv[1]);  
      
    // 检查 atoi 返回值是否为0，且参数不是"0"  
    if(time == 0 && argv[1][0] != '0'){  
        fprintf(STDERR,"Invalid number: %s\n",argv[1]);  
        exit(1);  
    }  
      
    //调用 sleep 系统调用  
    sleep(time);  
    exit(0);  
}

1. 引入必要的头文件

1
2
3

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

这些头文件包含了基本的数据类型、状态定义和用户级系统调用的声明，如 exit 和 sleep。

2. 定义 STDERR 宏

1
2
3

#ifdef STDERR  
#define STDERR 2  
#endif

这个部分定义了 STDERR 为值为 2 的宏。2 是标注错误输出的文件描述符。

3. main 函数的定义

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

main 函数接受两个参数：
- argc：命令行参数的数量。
- argv：一个字符串数组。包含命令行传入的参数。

4. 参数数量检查

if (argc != 2) {  
    fprintf(STDERR, "usage: sleep <second>\n");  
    exit(1);  
}

如果传递的参数数量不等于 2（即程序名称和一个时间参数），程序会向标准错误输出 usage: sleep 提示用户正确的用法，然后使用 exit(1) 退出程序，表示程序异常结束。

5. 将字符串转换为整数

1	int time = atoi(argv[1]);

使用 atoi 函数将字符串参数转换为整数，argv[1] 是用户输入的时间值。

6. 检查转换后的整数值是否有效

if (time == 0 && argv[1][0] != '0') {  
    fprintf(STDERR, "Invalid number: %s\n", argv[1]);  
    exit(1);  
}

检查转换后的时间值是否为 0。如果 time 等于 0 且输入的字符串不是 “0”，程序会认为用户输入了无效的数字，并输出错误信息，然后退出。

pingpong

编写一个程序，通过一对管道在父进程和子进程之间传递一个字节数据，实现类似“乒乓”的效果。父进程发送一个字节给子进程，子进程收到后打印消息并将字节返回给父进程，父进程再打印接收到的消息，最后两个进程都退出。

使用 fork() 复制本进程创建子进程，创建两个管道，分别用于父子之间两个方向的数据传输。

代码实现如下：

#include "kernel/types.h"
#include "user/user.h"
  
//REC、SND 分别代表管道的读取端和写入端
enum PIPE_END {REC = 0, SND = 1};

int main(int argc, char* argv[]) {
    if(argc != 1) {
        fprintf(2,"usage: pingpong (no parameter)\n");
        exit(1);
    }

    int p1[2]; // 父到子
    int p2[2]; // 子到父
    pipe(p1);
    pipe(p2);

    int pid = fork();

    if(pid == 0) { // 子进程
        close(p1[SND]);
        close(p2[REC]);

        char buf;
        
        if(read(p1[REC], &buf, 1) > 0) {
            printf("%d: recevied ping\n", getpid());
        }

        write(p2[SND], "p", 1);

        close(p1[REC]);
        close(p2[SND]);
        
        exit(0);
    }
    else if(pid > 0) { // 父进程
        close(p1[REC]);
        close(p2[SND]);

        write(p1[SND], "p", 1);

        char buf;
        if(read(p2[REC], &buf, 1) > 0) {
            printf("%d: received pong\n",getpid());
        }

        close(p1[SND]);
        close(p2[REC]);
        wait(0);
        exit(0);
    }
    else {
        fprintf(2, "failed to fork\n");
        exit(1);
    }

    exit(0);
}

1. 定义枚举

1	enum PIPE_END {REC = 0, SND = 1};

枚举定义 REC 和 SND，分别代表管道的读取端（REC = 0）和写入端（SND = 1）

2. 创建两个管道

int p1[2]; // 父到子  
int p2[2]; // 子到父  
pipe(p1);  
pipe(p2);

- p1和p2是两个管道。每个管道是一个长度为2的整数数组，pipe(p) 会分别为 p[0] 和 p[1] 赋值，表示读取端和写入端的文件描述符。
- p1 用于父进程向子进程发送消息。
- p2 用于子进程向父进程返回消息。

3.创建子进程

1	int pid = fork();

- fork() 系统调用用于创建一个子进程。pid 变量存储返回值:
    - pid == 0，表示当前进程是子进程。
    - pid > 0,表示当前进程是父进程，并且 pid 是子进程的 PID。
    - pid < 0,表示 fork() 失败

4. 子进程逻辑

if (pid == 0) { // 子进程  
    close(p1[SND]);  
    close(p2[REC]);  
      
    char buf;  
    if (read(p1[REC], &buf, 1) > 0) {  
        printf("%d: received ping\n", getpid());  
    }  
      
    write(p2[SND], "P", 1);  
    close(p1[REC]);  
    close(p2[SND]);  
    exit(0);  
}

- 关闭未使用的管道端口
    - 子进程不需要使用 p1 的写入端（SND）和 p2 的读取端（REC），所以关闭这些端口。
- 读取消息
    - 使用 read() 从 p1[REC] 读取一个字节（buf），这将阻塞子进程，直到有数据可读。
    - 如果读取成功，打印 <pid>: received ping，其中 <pid> 是子进程的进程 ID。
- 发送消息
    - 使用 write() 向 p2[SND] 写入一个字节 “P“，这表示子进程将消息发送回父进程。
- 关闭剩余的管道端口
    - 关闭 p1[REC] 和 p2[SND]，然后子进程正常退出。

5. 父进程逻辑

else if (pid > 0) { // 父进程  
    close(p1[REC]);  
    close(p2[SND]);  
      
    write(p1[SND], "P", 1);  
      
    char buf;  
    if (read(p2[REC], &buf, 1) > 0) {  
        printf("%d: received pong\n", getpid());  
    }  
      
    close(p1[SND]);  
    close(p2[REC]);  
    wait(0);  
    exit(0);  
}

- 关闭未使用的管道端口
    - 父进程不需要使用 p1 的读取端（REC）和 p2 的写入端（SND），所以关闭这些端口。
- 发送消息
    - 使用 write() 向 p1[SND] 写入一个字节 “P“，这将启动子进程的读取操作。
- 等待并读取子进程的响应
    - 使用 read() 从 p2[REC] 读取一个字节（buf），这将阻塞父进程，直到子进程写入数据。
    - 如果读取成功，打印 <pid>: received pong，其中 <pid> 是父进程的进程 ID。
- 关闭剩余的管道端口
    - 关闭 p1[SND] 和 p2[REC]，等待子进程结束（wait(0)），然后父进程正常退出。

primes

实现一个经典的”埃拉托斯特尼筛法”（Sieve of Eratosthenes）的多进程版本，使用 pipe 和 fork 创建进程链，每个进程从前一个进程接收数字并筛选出素数，直到处理完从2到35之间的所有数字。

代码实现如下：

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

enum PIPE_END {REC = 0,SND = 1};

//执行素数筛选
void sieve(int pleft[2]) {
    int p;

    // 读取当前管道中的第一个数，即素数
    if(read(pleft[REC], &p, sizeof(p)) == 0 || p == -1) {
        // 如果读取失败或遇到哨兵值-1，则退出
        close(pleft[REC]);
        exit(0);
    }

    printf("prime %d\n", p);

    int pright[2];
    pipe(pright);   // 创建用于传递给下一个筛子的管道

    if(fork() == 0) {
        // 子进程，处理下一个筛子阶段
        close(pright[SND]);
        close(pleft[REC]);

        sieve(pright);  // 递归调用 sieve 处理下一个筛子阶段
    }
    else {
        // 父进程，负责筛选和传递数据
        close(pright[REC]);

        int buf;
        while(read(pleft[REC], &buf, sizeof(buf)) > 0 && buf != -1) {
            if(buf % p != 0) {
                write(pright[SND], &buf, sizeof(buf));
            }
        }

        close(pleft[REC]);
        close(pright[SND]);

        wait(0);
    }

    exit(0);
}

int main(int argc, char* argv[]) {
    int input_pipe[2];
    pipe(input_pipe); // 创建主进程的输入管道

    if(fork() == 0) {
        // 子进程，执行筛选
        close(input_pipe[SND]);  // 关闭子进程不需要的写入端
        sieve(input_pipe);
    }
    else {
        // 主进程，生成数列并传递给子进程
        close(input_pipe[REC]);

        for(int i = 2;i <= 35;i++) {
            write(input_pipe[SND], &i, sizeof(i));
        }

        int sentinel = -1;
        write(input_pipe[SND], &sentinel, sizeof(sentinel)); // 写入哨兵值表示结束
        close(input_pipe[SND]);   // 关闭写入端

        wait(0);  // 等待子进程完成
    }

    exit(0);
}

主函数 main
负责初始化程序，创建并输入数列，然后启动第一个筛选阶段

创建输入管道并启动子进程

int input_pipe[2];
pipe(input_pipe); // 创建主进程的输入管道

if(fork() == 0) {
    // 子进程，执行筛选
    close(input_pipe[SND]);  // 关闭子进程不需要的写入端
    sieve(input_pipe);
}

子进程 负责处理数列筛选，执行 sieve 函数。
父进程 生成数列，并将其通过 input_pipe 传递给子进程。

生成数列并传递给子进程

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

int sentinel = -1;
write(input_pipe[1], &sentinel, sizeof(sentinel));
close(input_pipe[1]);

wait(0);
exit(0);

主进程生成 [2, 35] 之间的数字，并通过管道 input_pipe 传递给子进程。
sentinel 哨兵值 -1 被传入管道，标识数列的结束。
关闭管道的写入端，等待子进程完成后退出程序。

sieve 函数

pleft[2] 是从前一个进程传入的管道，通过它，当前进程接收一系列数字，并筛掉可被某个素数整除的数字，然后将剩下的数字传给下一个进程。

读取素数并输出

if (read(pleft[0], &p, sizeof(p)) == 0 || p == -1) {
    close(pleft[0]);
    exit(0);
}
printf("prime %d\n", p);

创建管道和子进程

int pright[2];
pipe(pright);

if (fork() == 0) {
    close(pright[1]);
    close(pleft[0]);
    sieve(pright);
}

pipe(pright)：为下一层进程创建一个新的管道 pright。
fork() 创建一个新的子进程：
- 子进程，处理下一个筛子阶段
- 父进程，负责筛选和传递数据

筛选并传递剩余数字

int buf;
while (read(pleft[0], &buf, sizeof(buf)) > 0 && buf != -1) {
    if (buf % p != 0) {
        write(pright[1], &buf, sizeof(buf));
    }
}

父进程不断从 pleft 读取数字，并筛选掉那些可以被当前素数 p 整除的数字。
将剩余的数字写入到 pright 管道，传递给下一个进程进行处理。

find

编写一个简单的 UNIX find 程序版本，用于在目录树中查找具有特定名称的所有文件。

该功能的基本原理与 ls 命令类似，实际上可以通过对 ls.c 代码进行修改来实现。

代码实现如下：

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

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

    // 打开路径
    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(path + strlen(path) - strlen(target), target) == 0) {
            printf("%s\n", path);
        }

        break;

    case T_DIR:
        if(strlen(path) + 1 + DIRSIZ + 1 > sizeof(buf)) {
            fprintf(2, "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) {
                continue;
            }

            memmove(p, de.name, DIRSIZ);
            p[DIRSIZ] = 0;

            if(stat(buf, &st) < 0) {
                fprintf(2, "find: cannot stat %s\n",buf);
                continue;
            }

            //跳过 '.' 和 '..'
            if(strcmp(de.name, ".") != 0 && strcmp(de.name, "..") != 0) {
                find(buf,target);
            }
        }

        break;
    }

    close(fd);
}

int main(int argc, char* argv[]) {
    if (argc != 3) {
        fprintf(2, "Usage: find <directory> <filename>\n");
        exit(1);
    }

    find(argv[1], argv[2]);

    exit(0);
}

find(char* path, char* target)

这是一个递归函数，接受两个参数：

path：需要搜索的目录路径。
target：要查找的目标文件名。

函数的作用是遍历目录下的所有文件和子目录，查找与 target 文件名匹配的文件。

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;
}

open(path, 0)：以只读模式打开目录或文件，返回文件描述符 fd，如果无法打开，打印错误信息。
fstat(fd, &st)：获取文件或目录的元数据信息（存储在 st 结构体中），用于判断它是文件还是目录。

判断文件类型

switch (st.type) {
    case T_FILE:
        if(strcmp(path + strlen(path) - strlen(target), target) == 0) {
            printf("%s\n", path);
        }
        break;
    ...

如果 st.type 为 T_FILE（文件），判断当前文件的名称是否与 target 相同。如果相同，就打印文件的路径。
strcmp(path + strlen(path) - strlen(target), target) == 0)：通过比较路径末尾的文件名和目标文件名来确定是否匹配。

如果是递归，继续递归

case T_DIR:
    if(strlen(path) + 1 + DIRSIZ + 1 > sizeof(buf)) {
        fprintf(2, "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) {
            continue;
        }
        memmove(p, de.name, DIRSIZ);
        p[DIRSIZ] = 0;
        if(stat(buf, &st) < 0) {
            fprintf(2, "find: cannot stat %s\n", buf);
            continue;
        }
        if(strcmp(de.name, ".") != 0 && strcmp(de.name, "..") != 0) {
            find(buf, target);
        }
    }
    break;

如果当前文件是 T_DIR（目录），将其路径保存在 buf 中，并开始读取目录内容。
while(read(fd, &de, sizeof(de)) == sizeof(de))：逐个读取目录中的文件或子目录项。
如果 de.inum == 0，表示这个目录项为空，跳过。
使用 memmove 将目录项的名称移动到缓冲区 buf，构建完整的路径名。
跳过 . 和 .. 这两个特殊目录（当前目录和父目录），然后递归调用 find(buf, target)，继续在子目录中查找。

xargs

编写一个简单版本的 xargs 程序，从标准输入读取行并为每行运行一个命令，将行内容作为命令的参数。

代码实现如下：

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

#define BUF_SIZE 2048
#define MAX_ARGS MAXARG

// 带参数列表，执行某个程序
void run(char* program, char** args) {
    if(fork() == 0) {
        exec(program, args);
        fprintf(2, "exec %s failed\n", program);
        exit(1);
    }
}

// 处理读入的参数并执行
void execute_command(char* program, char** argsbuf, char** pa) {
    *pa = 0;    // 参数列表末尾用 null 标识列表结束
    run(program, argsbuf);  // 执行命令
}

int main(int argc, char* argv[]) {
    char buf[BUF_SIZE]; // 读入时使用的内存池
    char *p = buf, *last_p = buf;   // 当前参数的结束、开始指针
    char *argsbuf[MAX_ARGS];    //全部参数列表，包含 argv 传进来的参数和 stdin 读入的参数
    char **args = argsbuf;  // 指向 argsbuf 中第一个从 stdin 读入的参数

    // 将 argv 提供的参数加入到最终的列表中
    for(int i = 1; i < argc; i++) {
        if(args - argsbuf >= MAX_ARGS - 1) {
            //fprintf(2, "too many arguments\n");
            exit(1);
        }

        *args++ = argv[i];
    }

    char **pa = args;
    int n;

    while((n = read(0, p, 1)) > 0) {
        if(*p == ' ' || *p == '\n') {
            *p = '\0';  // 将空格或换行替换为 '\0'，分割开各个参数
            *pa++ = last_p;

            if(pa - argsbuf >= MAX_ARGS - 1) {
                fprintf(2, "too many arguments\n");
                exit(1);
            }

            last_p = p + 1;

            if(*p == '\n') {
                execute_command(argv[1], argsbuf, pa);
                pa = args;
            }
        }

        p++;
        if(p - buf >= BUF_SIZE) {
            fprintf(2, "input line too long\n");
            exit(1);
        }
    }

    if(n < 0) {
        fprintf(2, "read error\n");
        exit(1);
    }

    if(pa != args) {    // 如果最后一行不是空行
        *p = '\0';
        *pa++ = last_p;
        execute_command(argv[1], argsbuf, pa);      
    }

    while(wait(0) != -1) {};    // 循环等待所有子进程完成
    exit(0);
}

run 函数 —— 执行程序

void run(char* program, char** args) {
    if(fork() == 0) {
        exec(program, args);
        fprintf(2, "exec %s failed\n", program);
        exit(1);
    }
}

功能:
- run 函数用于执行一个指定的程序。程序路径通过 program 传递，参数通过 args 列表传递。
逻辑:
- fork(): 创建一个子进程。在子进程中，fork() 返回 0。
- 如果 fork() 成功返回 0，子进程使用 exec(program, args) 替换当前进程映像为指定的程序。如果 exec 失败，程序会输出错误信息并调用 exit(1) 退出子进程。
总结:
- 子进程调用 exec 来执行指定命令。如果执行失败，则输出错误信息，并退出子进程。

execute_command 函数 —— 构造参数列表并调用 run

void execute_command(char* program, char** argsbuf, char** pa) {
    *pa = 0;    // 参数列表末尾用 null 标识列表结束
    run(program, argsbuf);  // 执行命令
}

功能:
- 该函数负责构造命令的参数列表并调用 run 来执行指定的命令。
逻辑:
- *pa = 0: 将当前参数列表的末尾置为 NULL，这在 exec 函数中用来标识参数列表的结束。
- 然后调用 run(program, argsbuf)，将程序名和参数传递给 run 执行。

主函数 —— 读取标准输入并构建参数列表

int main(int argc, char* argv[]) {
    char buf[BUF_SIZE]; // 读入时使用的内存池
    char *p = buf, *last_p = buf;   // 当前参数的结束、开始指针
    char *argsbuf[MAX_ARGS];    // 全部参数列表，包含 argv 传进来的参数和 stdin 读入的参数
    char **args = argsbuf;  // 指向 argsbuf 中第一个从 stdin 读入的参数

初始化:

buf[BUF_SIZE]: 定义一个缓冲区用于从标准输入中读取数据，大小为 BUF_SIZE（2048 字节）。
p 和 last_p: p 用于遍历缓冲区，last_p 记录每个参数的起始位置。
argsbuf: 定义了一个指针数组，用于存储命令的参数列表，包括命令行传入的参数和从标准输入中读取的参数。
args: 初始化为 argsbuf，它用于指向下一个要存储参数的位置。

for(int i = 1; i < argc; i++) {
    if(args - argsbuf >= MAX_ARGS - 1) {
        exit(1);
    }
    *args++ = argv[i];
}

命令行参数处理:

通过遍历命令行参数，将每个参数（从 argv[1] 开始）添加到 argsbuf 中。
每存储一个参数，args 会指向下一个空位。
如果参数数量超过 MAX_ARGS - 1，程序会提前退出以避免数组溢出。

读取标准输入并执行命令

char **pa = args;
int n;

while((n = read(0, p, 1)) > 0) {
    if(*p == ' ' || *p == '\n') {
        *p = '\0';  // 将空格或换行替换为 '\0'，分割开各个参数
        *pa++ = last_p;

        if(pa - argsbuf >= MAX_ARGS - 1) {
            exit(1);
        }

        last_p = p + 1;

        if(*p == '\n') {
            execute_command(argv[1], argsbuf, pa);
            pa = args;
        }
    }

    p++;
    if(p - buf >= BUF_SIZE) {
        exit(1);
    }
}

读取输入:
- read(0, p, 1): 每次从标准输入读取一个字符。
- 当遇到空格 ' ' 或换行符 '\n' 时，将其替换为 '\0'，这样每个参数字符串以 '\0' 结束，便于处理。
- 每当检测到一个参数结束（空格或换行），将该参数的起始位置 last_p 存入 argsbuf 中。
换行符处理:
- 遇到换行符 '\n' 表示该行输入结束，调用 execute_command 来执行命令，将收集到的参数列表传入执行。执行后将 pa 重置为指向第一个参数的位置 args，准备处理下一行输入。

错误处理与最后的命令执行

    if(n < 0) {
        exit(1);
    }

    if(pa != args) {    // 如果最后一行不是空行
        *p = '\0';
        *pa++ = last_p;
        execute_command(argv[1], argsbuf, pa);       
    }

    while(wait(0) != -1) {};    // 循环等待所有子进程完成
    exit(0);
}

错误处理:
- 如果 read 函数返回负值，表示读取发生错误，程序会退出。
最后的命令执行:
- 如果最后一行没有换行符但包含输入，则执行 execute_command 来处理这最后的命令。
等待子进程:
- while(wait(0) != -1): 等待所有子进程结束。wait 返回 -1 表示没有更多的子进程需要等待。