OS lab6 challenge

lab6的challenge是要求实现一个更加强大、功能更完善的命令行（MOS shell，mosh）相比lab6完成的简易shell，挑战性任务中的shell更具有交互性和逻辑性，也越来越贴近于用户正常使用命令行的习惯。

任务拆解与排序

在开始coding之前，我先将需要完成的任务进行一个列举，因为我感觉有些任务简单、有些任务复杂，而且他们之间可能还有相互的依赖性，比如实现.b的省略貌似就比较简单，而实现引号可能就会和行内注释、单行多命令等等有联系，因此一个正确的顺序能够使得任务效率和整体质量大大提升。

根据指导书的表面内容，初步将功能需求排序如下

• 实现不带.b命令的支持
• 实现touch、mkdir、rm命令（编写用户程序）
• 实现引号""、反引号``、行内注释#和一行多指令(也就是;)，并处理好优先级问题
• 追加重定向>>
• 条件执行：&& 和 ||
• 历史指令（上下键和bash history）
• 前后台任务fg, kill, jobs

具体实现

一、.b后缀的省略

之所以第一个完成这个任务，是因为这个相对简单，而且不涉及到其他前置需求，而且如果实现好了对于后面的测试也会方便一些（少打一堆.b）。

在我们Lab6中shell的实现中，对于指令的执行是在user/sh.c中，先解析再执行，执行的时候调用了user/lib/spawn.c中的spawn函数，该函数直接调用open函数试图打开参数prog代表的文件。

因此为了增加.b支持，同时保留完整输入带.b命令的正常功能，可以在打开的时候，如果打开失败且后面没有.b后缀，尝试拼接一个.b再试试。

具体的，在spawn函数中修改为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

if ((fd = open(prog, O_RDONLY)) < 0) {
    // failed, try to add ".b"
    int n = strlen(prog);
    if (n < 2 || prog[n-2] != '.'){ // not a ".*" cmd
        char s[MAXPATHLEN];
        strcpy(s, prog);
        s[n] = '.';
        s[n+1] = 'b';
        s[n+2] = '\0';
        if ((fd = open(s, O_RDONLY))<0){ // try again with cmd.b
            return fd;
        }
    }else {
        return fd;
    }
}

二、三个文件相关的指令：touch、mkdir、rm

这三个指令，都和文件系统有密不可分的关系，touch和mkdir分别是试图创建新文件/文件夹，rm是删除文件/文件夹。这些功能的实现需要依赖MOS中的文件系统，而我们在lab5中的文件系统中，对于创建还没有进行实现，但是已经有了remove操作，因此先实现相对简单的rm，然后再实现创建。

1. rm命令

指导书中对于要实现的rm功能描述如下：

• rm <file>：若文件存在则删除 <file>，否则输出 rm: cannot remove '<file>': No such file or directory。
• rm <dir>：命令行输出: rm: cannot remove '<dir>': Is a directory。
• rm -r <dir>|<file>：若文件或文件夹存在则删除，否则输出 rm: cannot remove '<dir>|<file>': No such file or directory。
• rm -rf <dir>|<file>：如果对应文件或文件夹存在则删除，否则直接退出。

总结下来就是带上-r可以删目录，带上-f保持静默。可以看出，在rm的过程中需要判断相关文件是文件还是目录、是否存在。

对于文件类型，可以直接根据File中的f_type判断，也可以参考ls中使用stat以后的st_isdir判断，这里使用第二种。这样-r和-f的功能实质上都在用户端完成，文件系统只需要直接进行删除。

原本的file_remove应该是对于一个文件的remove，因此并没有考虑文件还是目录什么的，而真正对目录的删除应该实现递归删除（否则目录下的文件实际上就是找不到但是白白浪费空间），因此理论上对file_remove进行一些修改，或者新增一个专门删除目录的函数，但是不写也能通过评测。

至于命令实现，除了一些选项的判断外，直接在rm.c中调用remove函数即可。

2. mkdir & touch

这两个指令都是对文件/目录的创建，而在mos中，二者的区别只是在于f_type不同，本质上都是File，所以通过对文件系统进行create支持（事实上只有fsipc、serv、file需要写create相关接口，fs里已经实现了create的底层执行），对于type，可以在serve_create的时候对一下传回来的File*指针的f_type进行赋值即可，就不需要修改file_create函数了。

touch的实现比较简单，这里展示一下mkdir的实现，忽略了main函数对参数的处理，那部分参考了user/ls.c的实现。对于-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

void mkdir(char *path){
	int r;
	if ((r = create(path, FTYPE_DIR)) < 0) {
		if (r == -E_FILE_EXISTS){
			if(!flag['p']) printf("mkdir: cannot create directory '%s': File exists\n",path);
			return;
		} else if(r == -E_NOT_FOUND){
			if (!flag['p']) printf("mkdir: cannot create directory '%s': No such file or directory\n",path);
			else {
				// recursively create dir
				char spath[MAXPATHLEN];
				int i = 0;
				while(*path != '\0'){
					spath[i++] = *path;
					if(*path == '/'){
						spath[i] = '\0';
						debugf("recursive mkdir:%s\n",spath);
						create(spath, FTYPE_DIR);
					}
					path++;
				}
				if (spath[i-1] != '/'){
					spath[i]='\0';
					create(spath, FTYPE_DIR);// in case cmd like: mkdir /123/123/123
				}
			}
		} else {
			user_panic("mkdir: %s, %d\n",path,r);
		}
	}
}

三、注释、引号

1. 注释的实现

行内注释最简单了，只需要读到#字符的时候按照0处理（结束）即可，只需注意出现在引号里的#不要被错误当做注释，不过后面实现保证了这一点（尤其是引号不会嵌套，所以要考虑的情况非常少了）

2. 引号

由于不会嵌套，所以直接读到第一个引号后，一直读取到最后一个引号，当做’w’读即可。

3. 反引号

理论上，应该把反引号里面的内容作为命令运行，并且获得其结果，作为echo的参数。所以一开始我的想法是：对于反引号的内容，类似引号的方式读入后，使用重定向将命令执行结果输入到某个临时文件中，随后再读取文件内容作为echo的输入（重定向），也就是人为地把 echo instruction拆为了instruction > tmp和 cat tmp < echo两行命令。

想了想可以实现，就是有点麻烦，感觉费半天劲给了个echo，后来想想好像其他命令也可以这样实现，但是题目只要求一个echo诶，而且反引号和引号没有嵌套（如果我理解没有错的话，就是这一行出现了一对反引号，那就只有这一对反引号），于是想出了一个tricky的实现：直接把反引号里的命令作为读到的命令然后给他执行了。

贴一下这三个的实现，因为都在同一个函数中修改的（sh.c中的_gettoken()）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

if (*s == 0 || *s == '#') { // add # as ending signal.
    return 0;
}

if (*s == '\"'){ // normal quote
    *s++ = 0;
    *p1 = s;
    while(*s != 0 && *s != '\"') s++;
    *s++ = 0;

    *p2 = s;
    return 'w';
}

if(*s == '`'){ // tricky ones
    *s++ = 0;
    *p1 = s;
    while(*s!=0 && *s!='`')s++;
    *s++ = 0;
    runcmd(*p1);//这里后面发生了变化：history在runcmd中记录，因此增加了一个是否需要记录history的参数
    *p2 = s; // actually, no need to care p2...
    return 0;
}

4. 多命令

最开始觉得，既然这个功能就是把多行放到了一行，我当然也可以反过来把一行变成多行指令。于是试图改readline，读取分号的时候直接return，剩下留着下次读，发现这样好像一行指令没输完就运行了，不合理。（不过倒是发现只要记录了读取引号状态，行内注释#的实现可以在这里完成）（看完history的要求，发现这里也不能简单地抛弃#后面的内容，啧）。

然后尝试了在main中的循环里解析，发现样例里面反引号里面带;就会出问题，于是只能放弃这种实现。

仔细想想，实际上多命令就是实现一个不需要通信、保证有序执行的类似管道的东西，无非也是fork一个子进程，把当前读到的（分号前）给运行了，为了保证顺序，父进程等子进程结束后再继续parse。

1
2
3
4
5
6
7
8
9
10

case ';':
    r = fork();
    if(r == 0){//child, 
        return argc;
    } else {
        wait(r);// father, have to wait
        *rightpipe = 0;
        return parsecmd(argv, rightpipe);
    }
    break;

四、追加重定向

一个>是覆盖输出，而两个>应该是在文件末尾追加写入，追加写入其实好实现，就是在打开的时候把offset直接设置为文件大小（因为打开以后只需要写），这样写的时候是直接在末尾开始写。

在user/include/lib.h中增加O_APPEND模式，fs/serv.c的open中，新增一行写offset的语句

1
2
3

#define O_APPEND 0x000b  // 8 + 3 (3 for O_ACC, WR+RD)
// fs/serv.c
if ((rq->req_omode & O_APPEND) == O_APPEND) ff->f_fd.fd_offset = ff->f_file.f_size;

下面就需要考虑如何识别是>还是>>，毕竟我们的gettoken中对于symbol集合的字符是一个一个读取的，如果在case '>'后面再调用gettoken判断是否还是>，会产生错误（因为gettoken函数里面的几个指针位置就变了），于是只能在_gettoken()里面特判修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

if (strchr(SYMBOLS, *s)) { // is one of symbol.
    int t = *s;
    *p1 = s;
    if(*s == '>'){
        if(*(s+1)=='>'){
            append=1;
            *s++=0;//跳过这一位，同时保持p1,p2不动（>> 被视为一个token）
        }
        else append = 0;

    }
    *s++ = 0;
    *p2 = s;
    return t;
}

五、历史命令

这个地方有一点点麻烦，主要在于：上下按键控制（以及乱飞的光标）、history的存储和读取、以及要实现为内部命令。

1. 上下按键控制

一开始我搜上下的ASCII试图捕捉，发现大概C语言控制台和shell不一样？ 于是参考了一下往年学长的博客，发现其实 上 是"%c[A"，其中那个char c = 27，于是在readline函数里面增加对上下按键的判断，其中有一行输出，是因为如果在MOS的shell里面按上，光标真的会跑到上一行，输出一个下，就可以保持它不会飞走，而下的情况不需要大概是Linux的命令行保证了不会因为↓而额外多出一行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

if (buf[i] == 27){ // UP ARROW
    char ch;
    read(0, &ch, 1);
    read(0, &ch, 1);
    switch(ch){
        case 'A':
            printf("%c[B",27);// keep cursor inline
            // do something
            break;
        case 'B':
            // do something
            break;
    }
} 

2. 内部命令

看到要求实现为built-in命令，我一时没想起怎么写内置命令——在Lab6根本没有内置命令的实现，甚至连内部命令的接口都没给留…要不是思考题在那里我都不知道内置命令是什么…

是执行内置命令/外部命令 实际上还是在解析以后、执行命令的时候判断的，也就是应该在调用spawn之前看看有没有内置命令，于是修改runcmd函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// sh.c  runcmd()
int r;
if((r=isInside(argv[0])) >= 0){ // 判断是否为内置命令，并返回命令编号
    void (*func)(u_int, char**);//argc argv; 
    func = inside_table[r];
    func(argc, argv);
} else {
    int child = spawn(argv[0], argv);
    close_all();
    if (child >= 0) {
        wait(child);
    } else {
        debugf("spawn %s: %d\n", argv[0], child);
    }
}

而对于内置命令，我的理解是就写在了sh.c里（或者如果更优雅一些，写一个库函数然后include进来？），我这里优雅地使用了OS里学到的函数指针表的写法，增加了可读性和可扩展性：

1
2
3
4
5
6
7
8
9
10
11

enum {
	HISTORY,
	FG,
	KILL,
	JOBS,
	MAX_INSIDECMD,
};
void *inside_table[MAX_INSIDECMD] = { // 内置命令函数表
	[HISTORY] = history, [FG] = fg, [KILL] = kill, 
	[JOBS] = jobs,
};

3. history的存储和读取

history命令非常简单，只是一个history命令，然后输出最近20条。可以通过判断换行次数来判断已经读了多少行指令，然后倒序的读入再倒序读出，非常感谢舍友的思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void history(int argc, char** argv){
	int fd = open("/.mosh_history", O_RDONLY | O_CREAT);
	if (fd < 0){
		user_panic("failed to open mosh_his:%d",fd);
	}
	char buff[20485];// 20480 = 1024 * 20 maxlen
	char print[20485];
	int len = 0;
	int line = 21;
	int r = read(fd,buff, 20480);
	if (r < 0){
		user_panic("read history error:%d",r);
	}
	for (int i = r-1; i >= 0; i--){
		if(buff[i] == '\n' || buff[i] == '\r'){
			if(--line == 0)break;
		}
		print[len++] = buff[i];
	}
	for(int i = len-1;i >= 0;i--){
		printf("%c",print[i]);
	}
	close(fd);
}

而存储history，我的实现是直接在.mosh_history文件后追加写入，对于20条的限制在我的history和hisGet里面实现，也就是说，如果有1000条命令的历史记录，我就会存储1000条命令。

相关函数一览

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

//sh.c
void hisRecord(char*);//record history, call when a new line comes.
void hisGet(u_int, char*, u_int);// get history cmd


void hisRecord(char *cmd){
	int fd = open("/.mosh_history", O_APPEND | O_CREAT);
	if (fd < 0) user_panic("failed to write his:%d",fd);
	int len = strlen(cmd);
	cmd[len] = '\n'; //这里有一个坑，必须先记录len以后用固定的len
	cmd[len+1] = '\0'; //如果用cmd[strlen(cmd)]这样，history下一行是his的话
    					// 这个时候cmd实际上是 his\0ory，
    					// 把\n加到\0位置以后，len就变成了his\nory的len了！
	write(fd, cmd, strlen(cmd));
	close(fd);
}
int now;// from which "\n", begin read;   n-history, n+1 means begin
void hisGet(u_int dir, char *cmd, u_int first){// dir:  0, before; 1, next
	if(first) now = 1;//reset pointer at every new line
	if (dir == 0){
		now++;
	} else {
		now = now > 1 ? now - 1 :now;
	}
	int fd = open("/.mosh_history", O_RDONLY | O_CREAT);
	if (fd < 0){
		user_panic("failed to open mosh_his:%d",fd);
	}
	char buff[20485];
	int len = 0;
	int r = read(fd,buff, 20480);
	if (r < 0){
		user_panic("read history error:%d",r);
	}
	int line = now;
	int i;
	for (i = r-1; i >= 0; i--){
		if(buff[i] == '\n' || buff[i] == '\r'){
			if(--line == 0)break;
		}

		if(i == 0 && line != 1){
			now--;// remedy for bad now++
		}
	}
	i++;
	while(buff[i] != '\n' && buff[i]!='\r' && buff[i]){
		*cmd = buff[i];
		cmd++;
		i++;
	}
	*cmd = 0;
	close(fd);
}

六、条件执行

条件执行，也就是实现&& ||逻辑，而且是从左到右的简单逻辑，自然地联想到了 “|” 、“;” 这些操作，只不过这里需要把命令运行是否成功return 0作为消息传递到后面，决定是否继续执行。指导书给出的提示是在exit处处理，查看 user/lib/libos.c，发现libmain函数中先获取的env，然后调用了main函数，最后main结束后exit，于是自然地想到（其实是和同学交流的时候别人说的）可以从这里获取main的返回值r随后使用ipc传递给父进程。（事实上设置一个env参数也可以）

要想弄明白到底要怎么实现，必须搞清楚执行一个命令到底有多少个进程、有几层。这个问题本应该在lab6弄明白，但是我这里又犯迷糊了，于是记录一下。

sh.c的主进程（main里面一直readline然后fork调用runcmd的进程）——runcmd进程——spawn打开.b执行命令；如果有管道就更多了，需要fork一个子进程执行到目前为止的左侧的语句。

sh.c → runcmd进程 ，parsecmd时读到 || ——根据ipc_recv决定是否继续

​ ↓

​ fork()子进程（用于运行左命令），调用spawn → exofork()装载、执行

所以如果想要传递这个return值给真正的runcmd，需要两级传递，main结束后传给fork的进程（左命令的runcmd），fork的进程接受到后再传给它的父进程（真正的解析执行这行语句的runcmd进程），然后由runcmd进程控制逻辑。注意runcmd就不要再传给sh了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//parsecmd  case '|'
if (twoor){ // condition
    int forkr = fork();
    if(forkr == 0){
        return argc; // let children to run, then send to parent.
    }else{
        r = ipc_recv(0, 0, 0);// the real runcmd get the return value.
        wait(forkr);
        if(r == 0){
            while((c = gettoken(0, &t)) != 0 && !(c=='&' && twoand));
            // instructions that no need to run.
            if(c == 0)return argc;
            else {
                // &&  need to run
                return parsecmd(argv, rightpipe);
                break;
            }
        } else 
            return parsecmd(argv, rightpipe);	
    }
    break;
}

七、 前后台任务管理

这部分主要有

1. &结尾实现后台运行
2. fg、jobs、kill

1. &结尾后台运行

考虑让命令后台运行，也就是说fork以后子进程runcmd，父进程（shell）此时不需要等待即可处理后面的输入。

因此只需要稍微修改一下main函数的逻辑：

1
2
3
4
5
6
7
8
9
10

if (r == 0) {
    runcmd(buf, 1);
    exit();
} else {
    if(buf[strlen(buf)-1] == '&'){ //这里实现比较粗糙，过了评测我就没管了，更精细的实现应当把末尾WHITESPACE字符过滤
        save_job(buf, r);//save jobs information
    } else {
        wait(r);
    }
}

2. jobs记录

jobs、kill、fg都是内部命令，按照之前的history的实现方法，补充函数表即可。而对于jobs的具体记录，可以记录在一个结构体数组中，记录了job_id, envid, cmd，jobs的时候读取相应进程的status即可。

1
2
3
4
5
6

struct Job {
	char cmd[1024];
	int eid;
	int jobid;
} jobs_save[1000];
int jobs_cnt;

对于status，写一个系统调用/直接通过envs数组找到对应env块都可以（后者需要判断一下这个env是否还是那个进程的id，可能free以后分配给别人了），我实现了系统调用，比较简单这里就略过了。

但是比较关键的一点是对于status的判断，什么时候是jobs指令中的Running，什么时候是Done，非常有趣的问题。

3. fg命令

fg实际上就是把后台命令重新搬回来，直接通过我们jobs记录的envid，让当前进程wait那个env，就实现了阻塞。

(注意这时候fg因为是非后台命令，所以实际上当前进程wait后台指令等价于shell进程等待后台指令那如果这里fg如果是fg&会怎样呢？)

4. kill命令

本来想通过把env_status设置为NOT_RUNNABLE的方式，后来发现我的实现这样会产生问题，根本不起效果（具体看下一节对status的描述），于是采用了更加暴力的方法：syscall_env_destroy，不过这个系统调用要求只有父进程才能destory子进程，是通过在envid2env调用时候的第三个参数鉴权的，因此把它改成0。

这样就可以直接实现kill命令，但是非常有趣的是，其实这种实现有一个bug（具体还是看下一节）

，但是还是通过了评测，呃呃这个评测相对较弱（或者有什么神奇的点我没理解到），感谢助教们不杀之恩。

5. 关于env_status和status

jobs命令中需要输出status（Running or Done），而可能得env_status是0，1，2，分别代表FREE、RUNNABLE、NOT_RUNNABLE，而如果env无效（比如重新分配给了别的进程，envid!= e.env_id以及status==FREE）可能还会再系统调用中抽出-2，显然-2是Done，0也是Done，1肯定是Running，那么2呢？

NOT_RUNNABLE，一般都是阻塞了才会进入的状态，或者进程还没设置好（fork过程中）等等，在我的实现中，我一开始发现我的所有进程都要么是2要么是-2，百思不得其解，后来发现其实是因为：在runcmd和真正执行外部命令的进程之间，我使用ipc通信，ipc_recv会把当前进程设置为NOT_RUNNABLE阻塞掉，子进程没完成、返回之前，runcmd进程当然就是2。

这也是为什么我不能像其他同学的实现一样，直接把status设置为NOT_RUNNABLE即可（因为不会有人再改为RUNNABLE，相当于僵尸进程，不会释放也不会被调度），但是这样env资源没有被释放，其实是不太好的实现方法。

至于刚刚说到的bug（或者说我没弄明白的地方），其实是如果我kill了runcmd进程，子进程ipc send的时候就会一直失败，最后产生user_panic；另外kill的和jobs记录的进程id其实都是runcmd进程，我觉得更合理的应该是那个spawn的时候fork出来的进程，否则kill掉runcmd进程，但是真正的命令没有死，理论上是不是还会再被调度呢？（好像不会，不知道为什么，甚至结束了以后连释放env的输出都没有）

记录和传递这个id有点麻烦，加上时间有限，好不容易过了评测我就不管他了。

结束语

完成了shell的任务，代码量大概在500行上下，在此感谢我的舍友以及讨论区的各位同学为我的debug带来的帮助，思路对了，实现就相对简单多了（但是调试很烦人，到最后我也不会用远程gdb调试lab6这种交互式的程序），也感谢助教带来的challenge评测，看的往届学长学姐博客里面的一些实现很明显是有bug难以通过评测的，这次评测也是保证了我的最低代码质量。

这下OS课算是真正结束了，在这次challenge中，我进一步地加深了对MOS的理解，从顶层设计到底层实现，一次又一次地感受到了操作系统的精妙之处。

• ← Previous Post
• Next Post →