os_challenge_shell

|

lab6_challenge_shell

我选择做相对有趣且有大量前人经验可参考的shell。

主要实现步骤有：

  • 语法分析
  • 相对路径
  • 拓展指令
  • 环境变量
  • 输入优化
  • 历史指令
  • 反引号、追加重定向与条件执行。

总共6个部分内容，我将在下面一一展开描述我的实现。

语法分析

因为mos的初始代码写的不是很好，在经过一段的时间的深思熟虑后，决定进行重构，搭建自己的语法树。由于这部分内容和oo的第一单元很类似，再加上ai的帮助，最后也没有花很长时间就完成了。

词法分析

首先是词法分析部分，类型申明如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 词法分析相关 */
typedef enum {
    T_WORD, T_PIPE, T_SEMI, T_AND, T_OR,
    T_REDIR_IN, T_REDIR_OUT, T_REDIR_APP,
    T_BACKQUOTE_OPEN,T_BACKQUOTE_CLOSE,T_EOF
} TokenType;

typedef struct {
    TokenType type;
    char *value;
} Token;

typedef struct {
    char *input;
    size_t pos;
} LexerState;

LexerState lexer;

在shell中需要实现一行多指令、重定向、管道、条件执行和反引号，所以就先定义了WORD，PIPE,SEMI等Token种类，用以语法分析的时候区分不同的Token。

使用的时候先初始化lexer：

1
2
3
4
void init_lexer(const char *input) {
	lexer.input = input;
	lexer.pos = 0;
}

然后在语法分析的时候每一次取一个Token出来分析：

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
// 获取下一个 token，消费它；返回 Token 结构（value 若是 WORD 需 strdup，调用者负责 free）
void get_next_token(Token* t) {
	while (strchr(WHITESPACE, *(lexer.input + lexer.pos))) {
		lexer.pos ++ ;
	} // 跳过空白符
	if (lexer.pos == strlen(lexer.input)) {
		t->type = T_EOF;
		t->value = NULL;
		return;
	} //读到EOF
	char c = lexer.input[lexer.pos];
	if (isWord(c)) {
		char value[MAX_COMMAND_LEN];
		int len = handleLetter(value);
		t->type = T_WORD;
		t->value = alloc_string(value);
		lexer.pos += len;
	} else if (c == '<') {
		char value[2];
		strcpy(value, "<");
		t->type = T_REDIR_IN;
		t->value = alloc_string(value);
		lexer.pos += 1;
	} else if (c == '>') {
		char nc = lexer.input[lexer.pos + 1];
		if (nc == '>') {
			char value[3];
			strcpy(value, ">>");
			t->type = T_REDIR_APP;
			t->value = alloc_string(value);
			lexer.pos += 2;
		} else {
			char value[2];
			strcpy(value, ">");
			t->type = T_REDIR_OUT;
			t->value = alloc_string(value);
			lexer.pos += 1;
		}
	} else if (c == '|') {
		char nc = lexer.input[lexer.pos + 1];
		if (nc == '|') {
			char value[3];
			strcpy(value, "||");
			t->type = T_OR;
			t->value = alloc_string(value);
			lexer.pos += 2;
		} else {
			char value[2];
			strcpy(value, "|");
			t->type = T_PIPE;
			t->value = alloc_string(value);
			lexer.pos += 1;
		}
	} else if (c == ';') {
		char value[2];
		strcpy(value, ";");
		t->type = T_SEMI;
		t->value = alloc_string(value);
		lexer.pos += 1;
	} else if (c == '&') {
		char value[3];
		strcpy(value, "&&");
		t->type = T_AND;
		t->value = alloc_string(value);
		lexer.pos += 2;
	} else if (c == '=') {
		char value[2];
		strcpy(value, "=");
		t->type = T_WORD;
		t->value = alloc_string(value);
		lexer.pos += 1;
	} else if (c == '`') {
        char value[2];
		strcpy(value, "`");
        if (backquote_num%2 == 0) {
            t->type = T_BACKQUOTE_OPEN;
        } else {
            t->type = T_BACKQUOTE_CLOSE;
        }
        backquote_num++;
		t->value = alloc_string(value);
		lexer.pos += 1;
        //debugf("backquote!\n");
    } else {
		debugf("not defined token!: %c\n", c);
	}

	return t;
}

词法分析的主要内容就是这些，主要是方便语法分析时把注意力放在Token上而不是字符上，这也是比较标准的做法。

语法分析

首先我们定义好要用的节点数据结构：

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
// === AST 结构及节点类型声明 ===

// AST 节点类型
typedef enum {
    NODE_COMMAND,    // 基本命令
    NODE_REDIR_IN,   // 重定向 <
    NODE_REDIR_OUT,  // 重定向 >
    NODE_REDIR_APP,  // 重定向 >>
    NODE_PIPE,       // 管道 |
    NODE_AND,        // &&
    NODE_OR,         // ||
    NODE_SEQUENCE,   // 分号 ; （语句序列）
    NODE_BACKQUOTE,  // 反引号 `
    // 若将来支持后台 '&'、子 Shell (…)、条件判断等，可继续扩展枚举
} ASTNodeType;

// AST 节点结构
typedef struct ASTNode {
    ASTNodeType type;
    union {
        // 对于命令节点
        struct {
            char *argv[MAXARGS];  // argv 数组，大小 argc+1，最后一个为 NULL
            int argc;
            struct ASTNode *backquote;
            int backquote_index;
        } command;
        // 对于重定向节点（child 表示要重定向的命令或子结构）
        struct {
            struct ASTNode *child;
            char *filename; // malloc 保存的文件名
            int mode;       // open() 时的 flags，如 O_RDONLY、O_WRONLY|O_CREAT|O_TRUNC、O_WRONLY|O_CREAT|O_APPEND
        } redirect;
        // 对于二元操作：PIPE, AND, OR, SEQUENCE
        struct {
            struct ASTNode *left;
            struct ASTNode *right;
        } binary;
    };
} ASTNode;

可以看到同样定义了节点种类，不同的种类在union中取不同的元素，同时又保持了统一性，个人认为是一个比较优雅的实现。

我们先明确一下语法树会长什么样子，下面是语法：

1
2
3
4
5
6
7
// 根据 EBNF:
// line     ::= list
// list     ::= and_or ( ";" and_or )*
// and_or   ::= pipeline ( ( "&&" | "||" ) pipeline )*
// pipeline ::= command ( "|" command )*
// command  ::= WORD ( WORD | redirect )*
// redirect ::= "<" WORD | ">" WORD | ">>" WORD

一行指令由一个list组成；

一个list由若干and_or和;组成；

and_or由若干pipeline和||或者&&组成；

pipeline由若干command和|组成；

command里面又可能存在重定向符号然后command的参数可能存在反引号。

所以我们根据在树中的结构简单的将可能的节点种类划分为了三类，分别是重定向、指令和二元节点。

然后是parse指令部分，根据语法和上面划分好的结构，我们自定向下的建树，第一层是parse_list:

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
Token current_token;

void next_token() {
    get_next_token(&current_token);
}

ASTNode *parse_line() {
    next_token();
    return parse_list();
}

int accept_token(TokenType expect) {
    if (current_token.type == expect) {
        next_token();
        return 1;
    }
    return 0;
}

// 解析 list: 可能含分号
ASTNode *parse_list() {
    ASTNode *left = parse_and_or();
    while (accept_token(T_SEMI)) {
        ASTNode *right = parse_and_or();
        left = new_binary_node(NODE_SEQUENCE, left, right);
    }
    return left;
}

根据分号的间隔解析成若干个and_or节点，并分别放到左节点和右节点。

比如：ls;pwd;exit 就解析成：

1
2
3
4
5
      root
     /    \ 
  binary  exit 
 /      \
ls      pwd

分号的下一层是条件执行，由||和&&分隔。

1
2
3
4
5
6
7
8
9
10
11
// 解析 and_or：处理 && 和 ||
ASTNode *parse_and_or() {
    ASTNode *left = parse_pipeline();
    while (current_token.type == T_AND || current_token.type == T_OR) {
        ASTNodeType op = (current_token.type == T_AND) ? NODE_AND : NODE_OR;
        next_token();
        ASTNode *right = parse_pipeline();
        left = new_binary_node(op, left, right);
    }
    return left;
}

和分号都是binary节点，所以解析的步骤是一样的，只是分隔符不一样（while循环条件）。

条件执行的下一层是管道，和上面步骤也是一致的：

1
2
3
4
5
6
7
8
9
// 解析 pipeline：处理管道 |
ASTNode *parse_pipeline() {
    ASTNode *left = parse_command();
    while (accept_token(T_PIPE)) {
        ASTNode *right = parse_command();
        left = new_binary_node(NODE_PIPE, left, right);
    }
    return left;
}

管道下一层就是指令了，先看代码：

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
// 解析单一 command（命令和其参数、重定向）
ASTNode *parse_command() {
    if (current_token.type != T_WORD) {
        debugf("UnExpected command : %d, value : %s\n", current_token.type, current_token.value);
    }

    char *argv[MAXARGS]; // 固定最大参数数
    int argc = 0;
    ASTNode *backquote_ast = NULL;
    int backquote_index = -1;

    while (current_token.type == T_WORD || current_token.type == T_BACKQUOTE_OPEN) {
        if (current_token.type == T_WORD) {
            argv[argc++] = current_token.value;
            next_token();   
        } else {
            next_token();
            backquote_ast = parse_list();
            if (!accept_token(T_BACKQUOTE_CLOSE)) {
                debugf("parse back quote wrong!\n");
                exit();
            }
            backquote_index = argc;
            argc++;
        }
    }
    argv[argc] = NULL;

    ASTNode *node = new_command_node(argv, argc, backquote_ast, backquote_index);

    // 处理重定向
    while (current_token.type == T_REDIR_IN ||
           current_token.type == T_REDIR_OUT ||
           current_token.type == T_REDIR_APP) {
        node = parse_redirect(node);
    }

    return node;
}

// 解析重定向，前提当前 token 是 "<", ">", ">>"
ASTNode *parse_redirect(ASTNode *prev_cmd_node) {
    ASTNodeType rtype;
    int mode;
    if (accept_token(T_REDIR_IN)) {
        rtype = NODE_REDIR_IN;
        mode = O_RDONLY;
    } else if (accept_token(T_REDIR_OUT)) {
        rtype = NODE_REDIR_OUT;
        mode = O_WRONLY | O_CREAT | O_TRUNC;
    } else if (accept_token(T_REDIR_APP)) {
        rtype = NODE_REDIR_APP;
        mode = O_WRONLY | O_CREAT | O_APPEND;
    } else {
        return prev_cmd_node; // 非重定向
    }
    if (current_token.type != T_WORD) {
        debugf("Expected filename after redirection\n");
    }
    char *filename = current_token.value;
    next_token();
    return new_redirect_node(rtype, prev_cmd_node, filename, mode);
}

对于command的解析，此时已经处于解析的最底层，所以通过是否是Word来取出对应的Token，然后放进argv数组里，若此时出现了反引号Backquote_OPEN，则重新进入parse list， 解析出一条完整的指令后标记好后续应该放入argv的index。

然后处理重定向部分，判断下一个Token是不是重定向符号，若是则进入parse_redirect部分。

就这样，通过递归下降法，我们一层一层的剥离了一行指令的结构，构造好了自己的语法树。

然后还有一个小技巧需要说明一下，由于mos没有实现动态内存分配，但是我们的树和字符串又需要动态申请，怎么办呢？

针对这个问题我使用的方法是现在sh.c里静态申请好一个长字符串和足够数量的AST树节点，然后写了对应的分配函数，当需要的时候就取出空闲的部分，不用的时候释放即可。下面是关键代码部分：

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
\\======= 字符串申请==========\\
static char pool[STRING_POOL_SIZE];
static int used[STRING_POOL_SIZE];  // 标记每个字节是否被使用

void reset_string_pool() {
    memset(pool, 0, sizeof(pool));
    memset(used, 0, sizeof(used));
}

char *alloc_string(const char *src) {
    int len = strlen(src) + 1;  // 包括 '\0'
    if (len > STRING_MAX_LEN) return NULL;

    for (int i = 0; i <= STRING_POOL_SIZE - len; ++i) {
        int found = 1;
        for (int j = 0; j < len; ++j) {
            if (used[i + j]) {
                found = 0;
                i += j;  // 跳过当前已使用区
                break;
            }
        }
        if (found) {
            // 找到足够连续空间
            memcpy(&pool[i], src, len);
            for (int j = 0; j < len; ++j) {
                used[i + j] = 1;
            }
            return &pool[i];
        }
    }

    return NULL;  // 空间不足
}

\\========== AST 节点申请 ===========\\
static ASTNode nodes[MAX_NODES];
static uint8_t bitmap[MAX_NODES / 8];  // 1024 bits = 128 bytes

// 设置 bitmap 中的第 i 位为 1
void set_bit(int i) {
    bitmap[i / 8] |= (1 << (i % 8));
}

// 设置 bitmap 中的第 i 位为 0
void clear_bit(int i) {
    bitmap[i / 8] &= ~(1 << (i % 8));
}

// 检查 bitmap 中的第 i 位是否为 1（已分配）
int is_allocated(int i) {
    return (bitmap[i / 8] >> (i % 8)) & 1;
}

// 自定义 malloc: 分配一个空闲的 ASTNode
ASTNode* alloc_ast_node() {
    for (int i = 0; i < MAX_NODES; ++i) {
        if (!is_allocated(i)) {
            set_bit(i);
            return &nodes[i];
        }
    }
    return NULL;  // 没有空闲节点
}

// 自定义 free: 回收指定的 ASTNode
void free_ast_node(ASTNode* node) {
    int index = node - nodes;
    if (index >= 0 && index < MAX_NODES) {
        clear_bit(index);
    }
}

// 释放 AST 节点（递归释放子节点、argv 中字符串等）
void free_ast(ASTNode *node) {
    if (!node) return;

    switch (node->type) {
        case NODE_COMMAND:
            // 不释放 argv[i] 或 argv，只释放节点
            break;

        case NODE_REDIR_IN:
        case NODE_REDIR_OUT:
        case NODE_REDIR_APP:
            free_ast(node->redirect.child); // 递归释放子节点
            break;

        case NODE_PIPE:
        case NODE_AND:
        case NODE_OR:
        case NODE_SEQUENCE:
            free_ast(node->binary.left);
            free_ast(node->binary.right);
            break;

        default:
            break;
    }

    // 释放当前节点到池中
    free_ast_node(node);
}

ASTNode *new_command_node(char **argv, int argc, ASTNode* backquote, int backquote_index) {
    ASTNode *node = alloc_ast_node();
    node->type = NODE_COMMAND;
	int i;
    for(i = 0; argv[i] != NULL; i++) {
		node->command.argv[i] = argv[i];
	}
	node->command.argv[i] = NULL;
    node->command.argc = argc;
    node->command.backquote = backquote;
    node->command.backquote_index = backquote_index;
    return node;
}

ASTNode *new_redirect_node(ASTNodeType type, ASTNode *child, char *filename, int mode) {
    ASTNode *node = alloc_ast_node();
    node->type = type;
    node->redirect.child = child;
    node->redirect.filename = filename;
    node->redirect.mode = mode;
    return node;
}

ASTNode *new_binary_node(ASTNodeType type, ASTNode *left, ASTNode *right) {
    ASTNode *node = alloc_ast_node();
    node->type = type;
    node->binary.left = left;
    node->binary.right = right;
    return node;
}

可以看出我用的是位图法进行的空闲部分的管理，在申请的时候置位位图，在释放的时候置零位图即可。

语法树执行

经过上面的折腾，我们已经按执行优先级解析完了我们指令的结构，下一步就是执行了，我们用深度优先搜索的方法对整棵树进行遍历即可，下面是关键代码：

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
// 执行 AST，返回子命令退出状态或整体状态
int execute_ast(ASTNode *node, int in_subshell) {
    if (!node) return 0;
    switch (node->type) {
        case NODE_COMMAND:
            return exec_command_node(node, in_subshell);
        case NODE_PIPE:
            return exec_pipe_node(node, in_subshell);
        case NODE_AND:
            return exec_and_node(node, in_subshell);
        case NODE_OR:
            return exec_or_node(node, in_subshell);
        case NODE_SEQUENCE:
            return exec_sequence_node(node, in_subshell);
        case NODE_REDIR_IN:
        case NODE_REDIR_OUT:
        case NODE_REDIR_APP:
            return exec_redirection_node(node, in_subshell);
        default:
            debugf("Unsupported AST node type %d\n", node->type);
            return 1;
    }
}
//分派函数
int exec_command_node(ASTNode *node, int in_subshell) {
    char **argv = node->command.argv;
    if (argv[0] == NULL) return 0;
    //处理反引号
    handleBackquote(node);
	//处理变量
	for (int i = 0; argv[i] != NULL; i++) {
    	replace_vars(argv[i]);
		if (strlen(argv[i]) == 0) {
			for(int j = i; argv[j] != NULL; j++) {
				argv[j] = argv[j+1];
			}
			i-=1;
		}
	}
    if (is_builtin(argv[0])) {
        return run_builtin(argv);
    } else {
        int child = spawn(argv[0], argv);
		if (child >= 0) {
			wait(child);
		} else {
			debugf("spawn %s: %d\n", argv[0], child);
		}
        int r = syscall_get_last_call();
        return r;
	}

	return 0;
}

int exec_pipe_node(ASTNode *node, int in_subshell) {
    int fds[2];
	int r;
    if (r = pipe(fds) < 0) {
        user_panic("pipe : %d", r);
    }
    int pid_left = fork();
    if (pid_left < 0) {
        user_panic("fork : %d", pid_left);
        close(fds[0]); 
		close(fds[1]);
        return 1;
    }
    if (pid_left == 0) {
        // 左侧子进程
        close(fds[0]);
        if (dup(fds[1], STDOUT_FILENO) < 0) {
            user_panic("dup"); 
			exit();
        }
        close(fds[1]);
        // 在子进程中执行左子 AST
        execute_ast(node->binary.left, 1);
        exit();
    }
    int pid_right = fork();
    int result = 0;
    if (pid_right < 0) {
        user_panic("fork");
        // 关闭并等待左
        close(fds[0]); 
		close(fds[1]);
        wait(pid_left);
        return 1;
    }
    if (pid_right == 0) {
        // 右侧子进程
        close(fds[1]);
        if (dup(fds[0], STDIN_FILENO) < 0) {
            user_panic("dup");
			exit();
        }
        close(fds[0]);
        int result = execute_ast(node->binary.right, 1);
        exit();
    }
    // 父进程
    close(fds[0]); 
	close(fds[1]);
    wait(pid_left);
	wait(pid_right);
    
    return result;
}

int exec_sequence_node(ASTNode *node, int in_subshell) {
    // 左侧执行，忽略或记录状态
    execute_ast(node->binary.left, in_subshell);
    return execute_ast(node->binary.right, in_subshell);
}

int exec_redirection_node(ASTNode *node, int in_subshell) {
    int fd;
    handleBackquote(node->redirect.child);
    if (node->type == NODE_REDIR_IN) {
        fd = open(node->redirect.filename, O_RDONLY);
        if (fd < 0) { 
			debugf("failed to open : %s\n", node->redirect.filename); 
			return 1; 
		}
        if (dup(fd, STDIN_FILENO) < 0) { 
			debugf("dup error\n"); 
			close(fd); 
			return 1; 
		}
        close(fd);
    } else if (node->type == NODE_REDIR_OUT) {
        fd = open(node->redirect.filename, O_WRONLY | O_CREAT | O_TRUNC);
        if (fd < 0) { 
			debugf("open wrong : %s\n", node->redirect.filename); 
			return 1; 
		}
        if (dup(fd, STDOUT_FILENO) < 0) { 
			debugf("dup error"); 
			close(fd); 
            return 1; 
		}
        close(fd);
    } else if (node->type == NODE_REDIR_APP) {
        fd = open(node->redirect.filename, O_WRONLY | O_CREAT | O_APPEND);
        if (fd < 0) { 
			debugf("open wrong : %s\n", node->redirect.filename); 
			return 1; 
		}
        if (dup(fd, STDOUT_FILENO) < 0) { 
			debugf("dup eooro\n"); 
			close(fd); 
			return 1; 
		}
        close(fd);
    } else {
        // 不应到达
        debugf("Unknown redirection type %d\n", node->type);
        return 1;
    }
    // 设置完成后执行子节点
    return execute_ast(node->redirect.child, in_subshell);
}

int exec_and_node(ASTNode *node, int in_subshell) {
    int status = execute_ast(node->binary.left, in_subshell);
    if (status == 0) {
        return execute_ast(node->binary.right, in_subshell);
    }
    return status;
}

int exec_or_node(ASTNode *node, int in_subshell) {
    int status = execute_ast(node->binary.left, in_subshell);
    if (status != 0) {
        return execute_ast(node->binary.right, in_subshell);
    }
    return status;
}

对于任意一个节点AST我们都按照统一的流程进行处理，首先由execute_ast判断当前节点类型进行分派。

如果是sequence_node（分号），先执行左子节点后执行右子节点，实现一行多指令效果，同时左侧指令先于右侧指令执行。

如果是and_node或者or_node（条件执行），先执行左子节点，同时获取左子节点的返回值，再以此判断是否执行右子节点，如何获取返回值在后续会具体展开回答。

如果是pipe_node（管道），开两个子进程，并将标准输入输出重定向到管道实现参数传递，由于在子进程执行，所以不影响shell进程的标准输入输出。

如果是redirection_node（重定向），先打开对应文件，并根据重定向类型选择标准输入或者输出重定向到对应文件描述符，然后执行指令即可。

如果是command_node（指令），则判断是内建指令还是外部指令，内建指令进入run_builtin,外部指令按lab6流程来，如下图：

img.png

进入spawn函数处理流程。

至此我们就完整的重构好了lab6的指令分析和执行部分的内容，这位我们后面的工作带来了很大的便利，事实上，我们在重构的过程中已经实现很多指令优化部分的内容了，这就是语法树的强大所在。

让我们进入真正的shell拓展内容：

相对路径支持

open remove

在原始的mos里只支持绝对路径，所以要想支持相对路径最简单快捷的办法就是更改文件系统里的代码。

我们只需要在文件open、remove的时候将rq->path改为绝对路径即可，关键代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
\\user/lib/file.c open
	if (has_relative_component(path)) {
		strcpy(buf, path);
		normalize_path_inplace1(curwd, buf);
		path = buf;
		//debugf("normalize path: %s\n", path);
	} else if (path[0] != '/'){
		if (!str_eq1(curwd, "/")) {
			strcpy(curwd + strlen(curwd), "/");
		}
		strcpy(curwd + strlen(curwd), path);
		path = curwd;
		//debugf("cat path: %s\n", path);
	}
\\user/lib/file.c remove
    char curwd[1024];
	syscall_get_cwd(curwd);
	char buf[1024];
	strcpy(buf, path);
	normalize_path_inplace1(curwd, buf);
	path = buf;

其中normalize_path_inplace1是将buf依据当前工作路径进行拓展，这样就能支持参数里的相对路径了。

cd、pwd和当前工作目录

下一步我们需要实现两个内建指令cd和pwd

cd指令的实现本次挑战性任务最难的部分，因为cd需要更改当前shell的工作目录，而这部分与进程强相关，在mos中是先fork一个子进程然后再执行run_cmd的，因为这样的操作可以避免一些恶意的操作直接导致shell本身被破坏，比如标准输入输出被修改了等等。

但是这也给我们实现cd带来一个难题，那就是我们如何保证cd能让shell的进程的工作目录被修改呢？

经过长时间的思考和讨论，我和室友最终采取了一个算是比较轻便的方法，但是不够优雅，对于这次挑战性任务却足够了。

首先，我们在进程控制块Env中添加一个char cwd[1024]的工作路径属性，用来标记当前shell的工作目录。

进程创建时，子进程继承父进程的工作目录，若是第一个被创建的进程，cwd被初始化为根目录/。

然后实现两个系统调用syscall_get_cwd()和syscall_change_cwd(char* path),其中关键的是syscall_change_cwd的实现，在该函数的内核态部分，我们取出当前进程curenv的父进程，并将其父进程的cwd修改为cd的路径，因为cd一定是在runcmd进程或者其子进程中执行的，并且若是在其子进程中执行则不影响shell的工作目录，这一点和bash的行为一致，所以我们只需要修改父进程的cwd即可，而不需要在意更深层的影响。

关键代码如下：

1
2
3
4
5
6
7
\\内核态部分
void sys_change_cwd(char* s) {
	struct Env* parent_env;
	envid2env(curenv->env_parent_id, &parent_env, 0);
	strcpy(curenv->cwd, s);
	strcpy(parent_env->cwd, s);
}

在cd之前，我们对于路径的合法性也需要检验，并判断是否是目录，同时也需要支持相对路径（和上面一样）

然后对于pwd的实现就很简单了，只需要取出当前进程的cwd然后输出即可。

拓展指令

这部分我们需要实现 mkdir， rm， touch 和exit。

对于前三个指令，我主要参考了zyt学长的代码，在此感谢zyt学长！！！(学长的代码)

同时为了方便实现条件执行，我做了相应的返回值修改

以下是关键代码：

mkdir:

实现思路分-p和无-p两部分，有-p则忽视父目录不存在的情况，若不存在则创建。

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
#include <lib.h>

int flag;

int mkdir(char *path) {
    int fd;
    int result = 0;
    if (flag) {
        if ((fd = open(path, O_RDONLY)) >= 0) {
            close(fd);
            return;
        }
        int i = 0;
        char str[1024];
        for (int i = 0; path[i] != '\0'; ++i) {
            if (path[i] == '/') {
                str[i] = '\0';
                if ((fd = open(path, O_RDONLY)) >= 0) {
                    close(fd);
                } else {
                    break;
                } 
            }
            str[i] = path[i];
        }
        for (; path[i] != '\0'; ++i) {
            if (path[i] == '/') {
                str[i] = '\0';
                //debugf("path : %s\n", str);
                fd = open(str, O_RDONLY);
                if (fd >= 0) {
                    close(fd);
                } else {
                    fd = open(str, O_MKDIR);
                    if (fd >= 0) {
                        close(fd);
                    } else {
                        debugf("error when mkdir\n");
                        result = 1;
                    }
                }
            }
            str[i] = path[i];
        }
        str[i] = '\0';
        fd = open(str, O_MKDIR);
        if (fd >= 0) {
            close(fd);
        } else {
            printf("other error when mkdir %s, error code is %d\n", path, fd);
            result = 1;
        }
    } else {
        if ((fd = open(path, O_RDONLY)) >= 0) {
            close(fd);
            printf("mkdir: cannot create directory '%s': File exists\n", path);
            result = 1;
            return;
        }
        fd = open(path, O_MKDIR);
        if (fd == -10) {
            printf("mkdir: cannot create directory '%s': No such file or directory\n", path);
            result = 1;
        } else if (fd < 0) {
            printf("other error when mkdir %s, error code is %d\n", path, fd);
            result = 1;
        } else {
            close(fd);
        }
    }
    return result;
}

int main(int argc, char **argv) {
    char s[5] = "-p";
    int result = 0;
    for (int i = 1; i < argc; i++) {
        if (strcmp(argv[i], s) == 0) {
            argv[i] = 0;
            flag = 1;
            break;
        }
    }    

    if (argc < 2) {
        user_panic("nothing to mkdir\n");
    } else {
        for (int i = 1; i < argc; ++i) {
            if (argv[i] == 0) {
                continue;
            }
            int r = mkdir(argv[i]);
            if (r != 0) {
                result = 1;
            }
        }
    }
    return result;
}

rm:

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
#include <lib.h>

int flag_r;
int flag_f;

int rm(char *path) {
    int fd;
    struct Stat st;
    if ((fd = open(path, O_RDONLY)) < 0) {
        if (!flag_f) {
            printf("rm: cannot remove '%s': No such file or directory\n", path);
        }
        return 1;
    }
    close(fd);
    stat(path, &st);
    if (st.st_isdir && !flag_r) {
        printf("rm: cannot remove '%s': Is a directory\n", path);
        return 1;
    }
    remove(path);
    
    return 0;
}

int main(int argc, char **argv) {
    char s_r[5] = "-r";
    char s_rf[5] = "-rf";
    int result = 0;
    for (int i = 1; i < argc; i++) {
        if (strcmp(argv[i], s_r) == 0) {
            argv[i] = 0;
            flag_r = 1;
        } else if (strcmp(argv[i], s_rf) == 0) {
            argv[i] = 0;
            flag_f = 1;
            flag_r = 1;
        }
    }

    if (argc < 2) {
        printf("nothing to rm\n");
    } else {
        for (int i = 1; i < argc; ++i) {
            if (argv[i] == 0) {
                continue;
            }
            int r = rm(argv[i]);
            if (r != 0) {
                result = 1;
            }
        }
    }

    return result;
}

touch:
实现思路就是先判断文件和父目录是否存在，若父目录不存在则抛出错误，并返回非0值，若文件不存在则创建一个新的文件。

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
#include <lib.h>

int touch(char *path) {
    int fd;
    int flag = 0;
    if ((fd = open(path, O_RDONLY)) >= 0) {
        close(fd);
        return;
    }
    fd = open(path, O_CREAT);
    if (fd == -10) {
        printf("touch: cannot touch '%s': No such file or directory\n", path);
        flag = 1;
    } else if (fd < 0) {
        printf("other error when touch %s, error code is %d\n", path, fd);
        flag = 1;
    } else {
        close(fd);
    }
    return flag;
}

int main(int argc, char **argv) {
    int flag = 0;
    if (argc < 2) {
        printf("nothing to touch\n");
    } else {
        for (int i = 1; i < argc; ++i) {
            int r = touch(argv[i]);
            if (r != 0) {
                flag = 1;
            }
        }
    }

    return flag;
}

exit:

这个指令则是每次readline后特判是不是exit，若是的话则直接执行exit()即可。

环境变量

熟悉了工作目录更改的那一套系统调用流程后，这一部分就好多了，我们继续利用万能的进程控制块和系统调用来实现这这一部分内容。

首先我们在进程控制块里增添新的内容：

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
struct variable {
	char key[17];
	char value[17];
	int mode; //0为全局， 1为局部
	int perm; //0为可读可写， 1为只读
};

// Control block of an environment (process).
struct Env {
	struct Trapframe env_tf;	 // saved context (registers) before switching
	LIST_ENTRY(Env) env_link;	 // intrusive entry in 'env_free_list'
	u_int env_id;			 // unique environment identifier
	u_int env_asid;			 // ASID of this env
	u_int env_parent_id;		 // env_id of this env's parent
	u_int env_status;		 // status of this env
	Pde *env_pgdir;			 // page directory
	TAILQ_ENTRY(Env) env_sched_link; // intrusive entry in 'env_sched_list'
	u_int env_pri;			 // schedule priority

	// Lab 4 IPC
	u_int env_ipc_value;   // the value sent to us
	u_int env_ipc_from;    // envid of the sender
	u_int env_ipc_recving; // whether this env is blocked receiving
	u_int env_ipc_dstva;   // va at which the received page should be mapped
	u_int env_ipc_perm;    // perm in which the received page should be mapped

	// Lab 4 fault handling
	u_int env_user_tlb_mod_entry; // userspace TLB Mod handler

	// Lab 6 scheduler counts
	u_int env_runs; // number of times we've been env_run'ed

	// lab 6_shell
	char cwd[1024];
	struct variable var[32];
	int var_num;
	int last_call;
};

然后继续按cd那一套来，增添4个系统调用，分别用来设置环境变量，取消环境变量，查询环境变量以及打印环境变量。

同理，这四个系统调用也是针对的父进程的环境控制块进行的操作。

输入优化

指令自由输入

这一部分我们修改readline的内容，保证readline能处理左右方向键和Backspace.

先设置好当前输入长度和光标位置变量。

识别当前字符是左右键时就移动光标到相应位置，相对对应的，输入字符时就让光标右边的字符整体右移一格，然后在光标处设置为当前字符，然后光标自增1。

识别当前字符是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
int len = 0;         // 实际输入长度
int cursor = 0;      // 当前光标位置
int r;
char c;

    else if (c == 0x7f || c == '\b') {  // Backspace
        if (cursor > 0) {
            // 1. 删除缓冲区字符
            for (int i = cursor - 1; i < len - 1; i++)
                buf[i] = buf[i + 1];
            len--;
            cursor--;
            // 2. 打印从当前位置到结尾的字符（覆盖旧内容）
            putchar('\b');               // 移动光标到被删字符位置
            for (int i = cursor; i < len; i++)
                putchar(buf[i]);
            putchar(' ');                     // 清除旧的最后一个字符
            // 3. 把光标移回原位
            for (int i = cursor; i <= len; i++)
                putchar('\b');
        }
    } else if (c == '\x1b') {  // Escape sequence
        char seq[2];
        if (read(0, &seq[0], 1) != 1) continue;
        if (read(0, &seq[1], 1) != 1) continue;
        if (seq[0] == '[') {
            if (seq[1] == 'D') {  // Left arrow
                if (cursor > 0) {
                    cursor--;
                }
            } else if (seq[1] == 'C') {  // Right arrow
                if (cursor < len) {
                    cursor++;
                } else {
                    
                }
            }

不带 .b 后缀指令

这一点只需要修改spawn就行，当当前文件打不开时就在文件路径后面加.b再打开以此即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int open_again_with_b(char *prog) {
	char temp[256];
	int i;
	for (i = 0; prog[i] != '\0'; ++i) {
		temp[i] = prog[i];
	}
	temp[i++] = '.';
	temp[i++] = 'b';
	temp[i] = '\0';
	return open(temp, O_RDONLY);
}

if (((fd = open(prog, O_RDONLY)) < 0) && ((fd = open_again_with_b(prog)) < 0)) {
		return fd;
}

快捷键

同理也只需要修改readline即可

代码大致如下：

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
else if (c == CTRL('A')) {  // Ctrl-A: Move to beginning
    while (cursor > 0) {
        putchar('\b');
        cursor--;
    }
} else if (c == CTRL('E')) {  // Ctrl-E: Move to end
    while (cursor < len) {
        putchar('\033[C');
        cursor++;
    }
} else if (c == CTRL('K')) {  // Ctrl-K: Kill to end
    for (int i = cursor; i < len; i++) {
        buf[i] = '\0';
        putchar(' ');
    }
    for (int i = cursor; i < len; i++) {
        putchar('\b');
    }
    len = cursor;
} else if (c == CTRL('U')) {  // Ctrl-U: Kill from start to cursor
    for (int i = 0; i < cursor; i++) {
        putchar('\b');
    }
    for (int i = 0; i < cursor; i++) {
        putchar(' ');
    }
    for (int i = 0; i < cursor; i++) {
        putchar('\b');
    }
    for (int i = 0; i + cursor < len; i++) {
        buf[i] = buf[i + cursor];
    }
    len -= cursor;
    cursor = 0;
} else if (c == CTRL('W')) {  // Ctrl-W: Delete previous word
    int original = cursor;
    // 删除空白
    while (cursor > 0 && (buf[cursor - 1] == ' ' || buf[cursor - 1] == '\t')) {
        for (int i = cursor - 1; i < len - 1; i++)
            buf[i] = buf[i + 1];
        len--;
        cursor--;
        putchar('\b'); 
        putchar(' '); 
        putchar('\b');
    }
    // 删除非空白
    while (cursor > 0 && buf[cursor - 1] != ' ' && buf[cursor - 1] != '\t') {
        for (int i = cursor - 1; i < len - 1; i++)
    buf[i] = buf[i + 1];
        len--;
        cursor--;
        putchar('\b'); 
        putchar(' '); 
        putchar('\b');
    }
}

实现注释功能

这部分内容比较简单，只需要在runcmd之前遍历一遍指令内容，遇到#就替换为\0即可。

实现一行多指令

得益于语法树的强大，这部分内容已经在语法树执行过程中完成了。

历史指令

题目要求我们把指令存在根目录的.mos_history里。

那我们就按照题目要求，在shell创建之初就先打开.mos_history，若不存在就创建一个，若存在则用于初始化内存中的history数组。

同时设立一个全局变量history数组用于在内存中存储最近的20条history。

每当从readline读取一行指令时，就更新一次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
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
else if (c == '\x1b') {  // Escape sequence
    char seq[2];
    if (read(0, &seq[0], 1) != 1) continue;
    if (read(0, &seq[1], 1) != 1) continue;
    if (seq[0] == '[') {
        if (seq[1] == 'D') {  // Left arrow
            if (cursor > 0) {
                cursor--;
            }
        } else if (seq[1] == 'C') {  // Right arrow
            if (cursor < len) {
                cursor++;
            } else {
                
            }
        }  else if (seq[1] == 'A') {  // Up arrow: prev history
            if (index > 0) {
                printf("\033[E");  // Move cursor to beginning of next line
                if (index == num) {
                    buf[len] = '\0';
                    strcpy(has_typed_in, buf);
                }
                index--;
                // 清除当前行
                while (cursor > 0) { putchar('\b'); cursor--; }
                for (int i = 0; i < len; i++) putchar(' ');
                for (int i = 0; i < len; i++) putchar('\b');
                // 复制历史到 buf
                strcpy(buf, history[index]);
                buf[strlen(buf) - 1] = '\0';//消去历史中的\n 
                len = strlen(buf);
                cursor = len;
                // 打印历史命令
                putchar('$');
                putchar(' ');
                for (int i = 0; i < len; i++) putchar(buf[i]);
            }
        } else if (seq[1] == 'B') {  // Down arrow: next history
            if (index < num) {
                index++;
                // 清除当前行
                while (cursor > 0) { putchar('\b'); cursor--; }
                for (int i = 0; i < len; i++) putchar(' ');
                for (int i = 0; i < len; i++) putchar('\b');
                // 如果还在历史中，加载，否则加载has_typed_in;
                if (index < num) {
                    strcpy(buf, history[index]);
                    buf[strlen(buf) - 1] = '\0'; //消去历史中的\n 
                    len = strlen(buf);
                } else {
                    strcpy(buf, has_typed_in);
                    len = strlen(buf);
                }
                cursor = len;
                // 打印当前内容
            
                for (int i = 0; i < len; i++) putchar(buf[i]);
            }
        }
    }
}

反引号、追加重定向和条件执行

这部分是实验cd后第二个比较难的部分

反引号

我们发现，这部分内容也在语法树中得到了解决.

首先是词法分析，当我们已经偶数次遇到反引号时，我们就将下一次遇见的反引号的Token类型记为T_Backquote_Open,否则记为T_Backquote_Close

然后是语法分析，当我遇见T_Backquote_Open时，进入parse_list的循环调用中，解析一个完整的指令并返回根节点，存储在command节点中。

然后是执行部分，在重定向和command执行前，均先检查是否存在反引号未解析，如果有，则开管道和子进程，先让反引号里的指令执行并输出到管道中，然后从管道中取出输出填补到command的已经标记好的index处。

关键代码如下：

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
\\词法：
    else if (c == '`') {
        char value[2];
		strcpy(value, "`");
        if (backquote_num%2 == 0) {
            t->type = T_BACKQUOTE_OPEN;
        } else {
            t->type = T_BACKQUOTE_CLOSE;
        }
        backquote_num++;
		t->value = alloc_string(value);
		lexer.pos += 1;
        //debugf("backquote!\n");
    }
\\语法 （parse_command（）函数）
    while (current_token.type == T_WORD || current_token.type == T_BACKQUOTE_OPEN) {
        if (current_token.type == T_WORD) {
            argv[argc++] = current_token.value;
            next_token();   
        } else {
            next_token();
            backquote_ast = parse_list();
            if (!accept_token(T_BACKQUOTE_CLOSE)) {
                debugf("parse back quote wrong!\n");
                exit();
            }
            backquote_index = argc;
            argc++;
        }
    }
    
\\ 执行
void handleBackquote(ASTNode *node) {
    char **argv = node->command.argv;
    if (node->command.backquote_index >= 0) {
        int p[2];
        if(pipe(p) < 0) {
            debugf("failed to create pipe\n");
            exit();
        }
        int backquote = fork();
        if (backquote < 0) {
            debugf("failed to fork in sh.c\n");
            exit();
        } else if (backquote == 0) { // 子进程执行反引号部分
            close(p[0]);
            dup(p[1], 1);
            close(p[1]);
            execute_ast(node->command.backquote, 0);
            exit();		
        } else { // 父进程处理argv
            close(p[1]);
            char outbuf[1024];
            memset(outbuf, 0, sizeof(outbuf));
            int offset = 0;
            int read_num = 0;
            while((read_num = read(p[0], outbuf + offset, sizeof(outbuf) - offset - 5)) > 0) {
                offset += read_num;
            }
            if (read_num < 0) {
                debugf("error in `\n");
                exit();
            }
            close(p[0]);
            for (int i = strlen(outbuf) - 1; i >= 0; i--) {
                if (outbuf[i] == ' ' || outbuf[i] == '\n') {
                    outbuf[i] = '\0';
                } else {
                    break;
                }
            }
            argv[node->command.backquote_index] = alloc_string(outbuf);
        }
        node->command.backquote_index = -1;
    }
}

int exec_command_node(ASTNode *node, int in_subshell) {
    char **argv = node->command.argv;
    if (argv[0] == NULL) return 0;
    //处理反引号
    handleBackquote(node);
	
int exec_redirection_node(ASTNode *node, int in_subshell) {
    int fd;
    handleBackquote(node->redirect.child);

追加重定向

这部分内容也很简单，新增文件打开类型O_APPEEND，，同时在serve_open里支持O_APPEND,将文件的偏移设置为文件大小即可。

1
2
3
4
if (rq->req_omode & O_APPEND) {
    	ff->f_fd.fd_offset = ff->f_file.f_size;
    	// debugf("offset: %d\n", ff->f_fd.fd_offset);
	}

条件执行

这部分内容也和语法树紧密关联，可以看出来，在语法树执行阶段，每一层的执行函数都有返回值，其实这就是我为条件执行留下的通道。

每一层返回子层的返回值，归根结底，最初的返回值就落到了内建指令和外部指令中了。

内建指令部分处理起来比较简单，返回值可以立马得到。

但是外部指令是调用了spawn，开了子进程运行的，所以我们需要在子进程结束前通过某种方式让父进程知道子进程的运行状况。

我们再次利用上万能的进程控制块Env,在控制块里新增属性last_call。

然后新增两个系统调用syscall_set_lastcall和syscall_get_lastcall。

外部指令最终都会在libos.c中的libmain里exit，所以我们做如下修改：

1
2
3
4
5
6
7
8
9
10
11
void libmain(int argc, char **argv) {
	// set env to point at our env structure in envs[].
	env = &envs[ENVX(syscall_getenvid())];

	// call user main routine
	int r = main(argc, argv);
	// exit gracefully
	//向父进程发送结果。
	syscall_set_last_call(r);
	exit();
}

然后在exec_command_node中捕获返回值并返回即可：

1
2
3
4
5
6
7
8
9
10
11
12
   if (is_builtin(argv[0])) {
       return run_builtin(argv);
   } else {
       int child = spawn(argv[0], argv);
	if (child >= 0) {
		wait(child);
	} else {
		debugf("spawn %s: %d\n", argv[0], child);
	}
       int r = syscall_get_last_call();
       return r;
}

这样我们就完成了这次挑战性任务的所有内容！！！！（完结撒花

总结

一学期的os就这样刷的一下过去了，从最初的懵懵懂懂到写完自己的shell，感觉自己对操作系统的运作流程有了质的飞跃（系统调用和Env获得了MVP!!

在通过自己一点一点的努力下，看到自己的shell成功的运行了起来，内心是无比的开心的，shell的挑战性任务不算简单，但是也是很艰难的完成的，花了很长时间去构想怎么在现有的代码架构上达到新的需求呢，到最后也是选择了重构，收获很多。

至此，经过co和os的拷打，自己也算是体验过了手搓一台具有交互能力的现代计算机了。

最后，感谢老师和助教一学期的辛苦工作！感谢这学期帮助过我的同学以及学长学姐的播客！感谢有os这门课！