操作系统shell

OS-shell挑战性任务实验报告

前言

本次实验中要求对MOS LAB6中的shell进行增强，但是考虑到课程内实现的shell无内建指令，我在本次挑战性任务中直接重构了课程内部的shell实现，首先采用词法分析和递归下降语法分析进行指令的解析，得到一棵抽象的语法树（此处为二叉树），然后递归地执行该命令。

任务内容及实现方法

相对路径

当前路径维护

我在挑战性任务采用了在进程控制块中维护该进程的当前绝对路径以支持相对路径。

1
2
3
4
struct Env {
	// ......
	char path[MAX_PATH];
};

在创建进程（即调用env_create函数）时将被创建的进程的当前目录设置为根目录'/'，然后在父进程创建子进程（即调用syscall_exofork函数）时将子进程的当前目录设置为父进程的当前目录。

进程当前路径查询和修改

由于对于进程的操作应当由内核实现，因此此处我新增了两个系统调用以完成进程当前路径的查询和修改操作。

1
2
3
4
5
6
7
int sys_get_dir(u_int envid, char path[MAX_PATH]) {
	// ......
}

int sys_set_dir(u_int envid, char path[MAX_PATH]) {
	// ......
}

支持相对路径

现在我们已经能够通过系统调用实现进程当前路径的查询和修改，要支持相对路径，只需要将相对路径和进程的当前路径拼接即可得到给定的相对路径所对应的绝对路径，此后，只要需要用到路径，就将此路径与进程当前路径拼接后，将新路径作为需要作为函数传参的路径即可。

由此我实现了下面的功能函数：

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
void merge_path(char* now_path, char *path) {
    int len = strlen(now_path);
    if (path[0] == '/') { // 当前路径就是绝对路径，不需要进行拼接
        now_path[0] = '\0';
        strcpy(now_path, path);
    } else if (path[0] != '/' && now_path[len - 1] == '/') {
        strcpy(now_path + len, path);
    } else if (path[0] != '/' && now_path[len - 1] != '/') {
        now_path[len] = '/';
        now_path[len + 1] = '\0';
        strcpy(now_path + len + 1, path);
    }
    len = strlen(now_path);
    char cur_path[MAX_PATH] = {'\0'};
    cur_path[0] = '/';
    int len_cur = 1;
    for(int i = 0;now_path[i]!='\0';i++) { // 遍历当前路径，替换'.'和'..'
        // TODO
    }
    strcpy(now_path, cur_path);
    //debugf("merge:%s\n", now_path);
    len = strlen(now_path);
    if (now_path[len - 1] == '/' && len !=1) {
        now_path [len - 1] = '\0';
    }
}

此后，只需要将相对路径和当前路径用此函数进程拼接再交给文件系统处理即可实现支持相对路径。

环境变量

环境变量维护

与当前路径类似，在进程控制块中维护该进程的所有环境变量，为此需要再进程控制块中新增如下内容：

1
2
3
4
5
6
7
8
9
10
11
12
struct Declare {
	char name[20];
	char value[20];
	u_int is_environment;
	u_int read_only;
};

struct Env {
	// ......
	struct Declare declare[MAX_DECLARE];
	int declare_len; // 该进程的环境变量个数
};

需要注意，在父进程创建子进程时需要将父进程中的环境变量，即is_environment == 1的环境变量拷贝给子进程。

环境变量增加、删除和查询

与当前路径类似，新增如下系统调用：

1
2
3
4
5
6
7
8
9
10
11
int sys_set_declare(u_int envid, char *name, u_int is_environment, u_int read_only, char *value) {
	// TODO
}

int sys_get_declare(u_int envid, struct Declare declare[MAX_DECLARE], int *declare_len) {
	// TODO
}

int sys_remove_declare(u_int envid, char *name) {
	// TODO
}

支持环境变量输入

在执行指令前，对指令的每个参数采用'/'符号进行分割，对于分割后的每一个元素判断其首字符是否为'$'，如果是则查找当前进程的环境变量并替换。

进程执行返回值

此部分较为复杂，我在实现时参考了Lazyfish同学的实现思路，在进程控制块中维护进程执行的返回值，在子进程退出时，并不销毁此子进程的进程控制块，而是将其设置为一个特殊状态ENV_DEAD，在父进程等待的过程中，如果查询到对应子进程的状态为ENV_DEAD，则获取该进程的返回值，由父进程将其销毁（但是此过程可能导致僵尸进程的出现）。代码如下：

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
// libos.c
void exit(int exit_code) {
	// After fs is ready (lab5), all our open files should be closed before dying.
#if !defined(LAB) || LAB >= 5
	close_all();
#endif

	syscall_env_exit(0, exit_code);
	user_panic("unreachable code");
}

// wait.c
int wait(u_int envid) {
	const volatile struct Env *e;

	e = &envs[ENVX(envid)];
	while (e->env_id == envid) {
		if (e->env_status == ENV_FREE) {
			return 0;
		} else if(e->env_status == ENV_DEAD) {
			int exit_code;
			exit_code = e->exit_code;
			syscall_env_destroy(envid);
			return exit_code;
		}
		syscall_yield();
	}
	return 0;
}

指令的执行

递归地遍历解析得到的语法树并执行相应指令即可。

对于内建指令，直接实现相应相应的函数即可，对于外部指令，调用spawn函数进行执行。

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
int run_code(char **argv, int argc) {
    int exit_code;
    argv[argc]=NULL;
    int child = spawn(argv[0], argv);
	if (child >= 0) {
		exit_code = wait(child);
	} else {
		debugf("spawn %s: %d\n", argv[0], child);
	}
    return exit_code;
}

int do_command_run(char **argv, int argc) {
    // TODO:替换环境变量
    int exit_code;
    if(strcmp(argv[0], "cd") == 0) {
        exit_code = run_cd(argv, argc);
    } else if (strcmp(argv[0], "pwd") == 0) {
        exit_code = run_pwd(argv, argc);
    } else if (strcmp(argv[0], "exit") == 0) {
        exit_code = run_exit();
    } else if (strcmp(argv[0], "declare") == 0) {
        exit_code = run_declare(argv, argc);
    } else if (strcmp(argv[0], "unset") == 0) {
        exit_code = run_unset(argv, argc);
    } else if (strcmp(argv[0], "history") == 0) {
        exit_code = run_history();
    } else {
        exit_code = run_code(argv, argc);
    }
    return exit_code;
}

int run_shell_ast(ASTNode *root) {
    int exit_code;
    int r;
    if (!root) return 0;
    // printf("%d\n", root->type);
    switch (root->type) {
        case AST_COMMAND:
            exit_code = do_command_run(root->argv, root->argc);
            break;
        case AST_PIPE:
            // TODO:实现管道
            break;
        case AST_AND:
            // TODO:实现指令与条件执行
            break;
        case AST_OR:
            // TODO:实现指令或条件执行
            break;
        case AST_LIST:
            // TODO:实现多指令执行
            break;
        case AST_REDIR_IN:
            // TODO:实现输入重定向
			break;
        case AST_REDIR_OUT:
            // TODO:实现输出重定向
            break;
        case AST_REDIR_APP:
            // TODO:实现追加重定向
            break;
    }
    return exit_code;
}

新增指令

cd

将输入参数与当前进程的当前路径拼接得到需要跳转到的绝对路径，使用系统调用修改当前进程的当前路径为该新路径即可。

1
2
3
4
5
6
7
8
9
10
int run_cd(char **argv, int argc) {
    char path[MAX_PATH] = {'\0'};
    // TODO:判断参数合法性
    char now_path[MAX_PATH] = {'\0'};
    syscall_get_dir(0, now_path);
    merge_path(now_path, path);
    // TODO:判断路径合法性
    syscall_set_dir(0, now_path);
    return 0;
}

pwd

直接使用系统调用查询当前进程的当前目录即可。

declare与unset

直接使用系统调用新增或删除环境变量即可（注意环境变量是否具有只读性）。

history

读取.mos_history文件中的内容并输出即可。

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
int run_history() {
    int fd = open(HISTORY_PATH, O_RDONLY);
	if (fd < 0) {
		debugf("failed to open '%s'\n", HISTORY_PATH);
		exit(1);
	}
    int r;
	int index = 0;
    int num_cmd = 0;
    char history_cmd[20][50];
	while(1) {
		char c;
		r = read(fd, &c, 1);
		if(r != 1) {
			break;
		}
		if(c == '\n') {
            history_cmd[num_cmd][index] = '\0';
			num_cmd++;
			index = 0;
			continue;
		}
        
		history_cmd[num_cmd][index] = c;
		index++;
	}
    for(int i = 0;i < num_cmd;i++) {
        printf("%s\n", history_cmd[i]);
    }
    close(fd);
    return 0;
}

touch

为了实现创建文件的功能，需要对文件系统新增对于创建文件请求的处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// user/lib/file.c 用户调用此函数执行创建文件
int create(char *path, int is_dir) {
	char now_path[MAX_PATH] = {'\0'};
    syscall_get_dir(0, now_path);
    merge_path(now_path, path);
	return fsipc_create(now_path, is_dir);
}

// user/lib/fsipc.c 使用进程间通信向文件系统进程发送创建请求
int fsipc_create(char *path, int is_dir) {
	struct Fsreq_create *req = (struct Fsreq_create *)fsipcbuf;
	strcpy(req->req_path, path);
	req->is_dir = is_dir;
	return fsipc(FSREQ_CREATE, req, 0, 0);
}

// fs/serv.c 响应用户创建请求
void serve_create(u_int envid, struct Fsreq_create *rq) {
	int r;
	struct File *file;
	r = file_create(rq->req_path, &file, rq->is_dir);
	ipc_send(envid, r, 0, 0);
}

有了上述工具函数，只需要将输入参数与当前进程的当前目录拼接后得到需要创建的文件的绝对路径，调用create函数即可创建。

mkdir

对于没有-p参数的情况与touch中的处理大致相同，只需要将create的传入参数is_dir置一即可。

对于有-p参数的情况，需要递归地创建该目录，即创建目录前先查找其父目录是否存在，如果存在则直接创建，否则先创建其父目录。

1
2
3
4
5
6
7
8
9
10
11
int mkdirp(char *path) {
    // TODO:拼接路径
    char parent_path[MAX_PATH] = {'\0'};
    // TODO:得到父目录
    r = stat(parent_path, &s);
    if (r < 0) {
        mkdirp(parent_path);
    }
    create(now_path, 1);
    return 0;
}

rm

直接调用课程内已实现的remove函数即可，此处不再赘述。

exit

已在进程返回值处说明，此处不再赘述。

注释

在词法分析中，遇到'#'则直接退出即可实现注释功能。

一行多指令

递归下降解析过程中，遇到';'则继续递归解析，执行时采用中序遍历执行即可。

1
2
exit_code = run_shell_ast(root->left);
exit_code = run_shell_ast(root->right);

指令条件执行

  • 对于与而言，左侧指令执行成功则继续执行右侧指令，返回右侧指令执行结果，否则直接返回左侧指令执行结果。

    1
    2
    3
    4
    5
    exit_code = run_shell_ast(root->left);
    if(exit_code != 0) {
    	return exit_code;
    }
    exit_code = run_shell_ast(root->right);

  • 对于或而言，左侧指令执行失败则继续执行右侧指令，返回右侧指令执行结果，否则直接返回左侧指令执行结果。

    1
    2
    3
    4
    5
    exit_code = run_shell_ast(root->left);
    if(exit_code == 0) {
    	return exit_code;
    }
    exit_code = run_shell_ast(root->right);

重定向

为了重定向结束后的其他指令仍然能够地进行输入输出，需要在重定向开始之前将标准输入或标准输出进行备份，注意：受到Lazyfish同学的指正，如果使用课程内实现的fd_alloc函数得到一个空闲文件标识符，需要在下一次调用fd_alloc前就使用该文件标识符，否则两次fd_alloc将返回两个相同的文件标识符从而导致错误。

对于追加重定向，需要使用seek函数将当前文件操作的偏移指针移动到文件的末尾，从而实现追加。注意，打开文件时不能有O_TRUNC权限的设置，否则将清空该文件。

下面是以重定向输入为例的代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Fd *tmpin;
if ((r=fd_alloc(&tmpin))!=0) {
    return r;
}
int tmpin_fd = fd2num(tmpin);
dup(0, tmpin_fd);
int fd = open(root->filename, O_RDONLY);
if (fd < 0) {
	debugf("failed to open '%s'\n", root->filename);
	exit(1);
}
dup(fd,0);
close(fd);
exit_code = run_shell_ast(root->left);
dup(tmpin_fd,0);

管道

实现前需要明确的事实：管道左右两侧的指令无论是否是内建指令均需要创建子进程进行执行。

记当前进程为A，先使用fork创建一个子进程B用于执行管道，进程A调用wait等待进程B执行完毕，在进程B中，模仿课内原有的管道实现即可（即使用fork创建子进程C，进程B和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
25
26
27
28
r = fork();
if (r < 0) {
	debugf("fork: %d\n", r);
	exit(1);
}
if (r == 0) {
    int p[2];
    r = pipe(p);
    if (r != 0) {
        debugf("pipe: %d\n", r);
		exit(1);
	}
    r = fork();
	if (r < 0) {
		debugf("fork: %d\n", r);
		exit(1);
	}
    int rightpipe_p;
    rightpipe_p = r;
    if (r == 0) {
		// 执行管道左侧
	} else {
		// 执行管道右侧
    }
    exit(exit_code);
} else {
    exit_code = wait(r);
}

反引号

shell中反引号的功能为用反引号内指令的执行结果替换反引号部分的内容。

此处采用与管道类似的处理，在词法分析过程中，如果读到反引号，则使用管道进行处理，管道左侧执行反引号内部的命令，管道右侧将管道内容读出至一个字符串数组中，然后用该字符串替换原本反引号部分的内容，继续进行词法分析。示例代码如下：

1
2
3
4
5
6
7
8
char subout[256] = {'\0'};
char sub[256] = {'\0'};
strcpy(sub, input+start);
ASTNode *subast = parse_shell_command(sub);
if (subast) {
	// TODO:使用管道类似的方法运行subast指令，将其输出读入到subout中
}
// TODO:用subout的内容替换原有反引号部分

指令输入自由化

做到这一步其实离胜利已经不远了，后续的部分只是单纯量大而已。

在本次挑战性任务中，我们需要实现在当前光标位置进行字符串的增加和删除同时支持以下快捷键。

快捷键 行为
left-arrow 光标尝试向左移动，如果可以移动则移动
right-arrow 光标尝试向右移动，如果可以移动则移动
backspace 删除光标左侧 1 个字符并将光标向左移动 1 列；若已在行首则无动作
Ctrl-E 光标跳至最后
Ctrl-A 光标跳至最前
Ctrl-K 删除从当前光标处到最后的文本
Ctrl-U 删除从最开始到光标前的文本
Ctrl-W 向左删除最近一个 word：先越过空白(如果有)，再删除连续非空白字符
up-arrow 如果上一条指令存在则切换至上一条指令
down-arrow 如果下一条指令存在则切换至下一条指令

此部分不清楚的直接使用Bash进行参考即可。

注意：在控制台输出会直接将光标移动至最后一个输出字符后

对于输入缓冲的处理大体如下，此处仅对backspace和方向键进行详细解释，其余均可模仿backspace的实现方法，在加以一定的字符串处理进行实现：

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
void readline(char *buf, u_int n) {
	int r;
	int index = 0;
	int len = 0;
	int cmd_id = num_cmd;
	int cur_cmd_set = 0;
	for(int i = 0;i < 1024;i++) {
		buf[i] = '\0';
		cur_cmd[i] = '\0';
	}
	while(1) {
		char c;
		if ((r = read(0, &c, 1)) != 1) {
			if (r < 0) {
				debugf("read error: %d\n", r);
			}
			exit(1);
		}
		switch (c) {
			case '\b':
        	case 127: // Backspace
				if(index > 0) {
					index--;// 缓冲数组指针回退一个字节
					for(int i = index;i < len;i++) { // 将被删除的字符之后的部分向前移动。
						buf[i] = buf[i+1];
					}
					len--;// 缓冲大小减一
					buf[len] = '\0';
					printf("\e[D");// 控制台光标左移一位
					printf("\e[K");// 清空控制台光标之后的输出
					printf("%s", buf+index);// 输出被删除的字符之后的部分，从而使被删除字符不再显示于控制台
					for(int i = len;i > index;i--) { // 将光标移动到被删除字符之后
						printf("\e[D");
					}
				}
            	break;
        	case 1: // Ctrl-A
				// 模仿backspace进行实现即可
            	break;
        	case 5: // Ctrl-E
            	// 模仿backspace进行实现即可
            	break;
        	case 11: // Ctrl-K
				// 模仿backspace进行实现即可
                // 注意，在跳板机中按此快捷键会导致光标下移一行，因此应当在处理之前先让光标上移一行
            	break;
        	case 21: // Ctrl-U
            	// 模仿backspace进行实现即可
            	break;
        	case 23: // Ctrl-W
				// 模仿backspace进行实现即可
            	break;
        	case 27: { // ESC，可能是方向键
				char ch1;
				if ((r = read(0, &ch1, 1)) != 1) {
					if (r < 0) {
						debugf("read error: %d\n", r);
					}
					exit(1);
				}
            	if (ch1 == '[') {
                	char ch2;
					if ((r = read(0, &ch2, 1)) != 1) {
						if (r < 0) {
							debugf("read error: %d\n", r);
						}
						exit(1);
					}
                	switch (ch2) {
                    	case 'A':
                        	printf("\e[B"); // 此时光标已经上移了一行，为了保证光标始终在指令行需要下移一行
							if(cmd_id > 0) { // 存在历史指令
								cmd_id--;
								if(!cur_cmd_set) { // 此时还在当前指令，需要将当前指令保存，以便以后切换回当前指令
									if(len > 0) {
										buf[len] = '\0';
										strcpy(cur_cmd, buf);
									} else {
										cur_cmd[0] = '\0';
									}
									cur_cmd_set = 1;
								}
                                // 与backspace类似的修稿控制台显示内容
								for(int i = index;i > 0;i--) { 
									printf("\e[D");
								}
								printf("\e[K");
								strcpy(buf, history_cmd[cmd_id]);
								printf("%s", buf);
								index = strlen(buf);
								len = index;
							}
                        	break;
                    	case 'B':
							if(cmd_id < num_cmd) { // 存在下一条指令
								cmd_id++;
								if(cmd_id == num_cmd) { // 需要切换至当前指令
									strcpy(buf, cur_cmd);
                                    // 修改控制台显示内容
									for(int i = index;i > 0;i--) {
										printf("\e[D");
									}
									printf("\e[K");
									printf("%s", buf);
									index = strlen(buf);
									len = index;
									cur_cmd_set = 0;
								} else { // 切换至历史记录中的下一条指令
									strcpy(buf, history_cmd[cmd_id]);
                                    // 修改控制台显示内容
									for(int i = index;i > 0;i--) {
										printf("\e[D");
									}
									printf("\e[K");
									printf("%s", buf);
									index = strlen(buf);
									len = index;
								}
							}
                        	break;
                    	case 'C':
                        	if(index <= len) { // 缓冲数组下标同步右移
								index++;
							}
                        	break;
                    	case 'D':
                        	if(index >= 0) { // 缓冲数组下标同步左移
								index--;
							}
                        	break;
                    	default:
                        	printf("no such way: ESC [ %c\n", ch2);
							break;
                	}
            	} else {
                	printf("ESC\n");
            	}
            	break;
        	}
			case '\n':
			case '\r':
				index = len;
				buf[index] = '\0';
				index++;
				len++;
				if(strlen(buf) != 0){
					strcpy(cur_cmd, buf);
					insert_history(); // 将该指令存入历史指令中
				}
				return;
				break;
			default:
				if(index!=len) { // 实现字符的插入，同时保证控制台显示与缓冲数组内容一致
					for(int i = len;i > index;i--) {
						buf[i] = buf[i - 1];
					}
					buf[index] = c;
					index++;
					len++;
					buf[len] = '\0';
					printf("\e[K");
					printf("%s", buf + index);
					for(int i = len;i > index;i--) {
						printf("\e[D");
					}
				} else {
					buf[index] = c;
					index++;
					len++;
					buf[len] = '\0';
				}
				break;
		}
	}
	debugf("line too long\n");
	while ((r = read(0, buf, 1)) == 1 && buf[0] != '\r' && buf[0] != '\n') {
		;
	}
	buf[0] = 0;
}

实验体会

我一开始准备做swap挑战性任务，尝试了5天之后发现海量bug，于是转战shell，总体而言，shell主要在用户态做修改，bug的查找相对于内核修改而言较为容易，shell仅涉及少量简单的内核态函数修改，因此我在实现shell挑战性任务时并未感觉有较大的debug困难，而shell挑战性任务的主要难点在于代码量过于庞大，尤其是重构课程中已有的输入解析部分，最后，在鏖战5天后慢慢磨完了shell挑战性任务。下附一张代码修改量详情示意图。 differ

附录

参考博客：https://lazyfish-lc.github.io/2025/06/16/BUAA-OS-shell-challenge/