xv6-lab1 - Qiuarctica

xv6 lab1 实验记录，用于以一个初学者的视角分享一些小想法和记录实验过程，方便日后复习，同时记录一下某些标记为easy但实际上一点也不easy的问题.

1. do not print $ in files (moderate)#

这个问题实际上是要让shell知道我们执行的命令是从控制台中输入的还是从文件中输入的.在C语言中有isatty函数，man isatty可以看到其描述为:

The isatty() function tests whether fd is an open file descriptor referring to a terminal.

于是我们的任务便是简单实现一个isatty函数,并在每次sh输出前添加一个判断语句即可.

TTY(TeleTYperwrite)原指电传打印机，现主要指操作系统内核中的TTY driver,其中包含的line discipline能正确解读terminal中传入的信息并返回给terminal,在这里我们可以简单的把TTY看成终端.

观察xv6提供的stat.h文件

1
#define T_DIR     1   // Directory
2
#define T_FILE    2   // File
3
#define T_DEVICE  3   // Device
4

5
struct stat {
6
  int dev;     // File system's disk device
7
  uint ino;    // Inode number
8
  short type;  // Type of file
9
  short nlink; // Number of links to file
10
  uint64 size; // Size of file in bytes
11
};

我们可以通过检测stdin的stat的type字段来判断其来源是目录，文件还是设备，同时，如果是设备，我们希望其设备编号(dev)为1(stdin)于是我们有:

1
int isatty(int fd){
2
  struct stat st;
3
  if (fstat(fd, &st) < 0) {
4
    panic("Error to stat");
5
  }
6
  return st.type == T_DEVICE && st.dev == 1;
7
}

1
  getcmd(char *buf, int nbuf)
2
{
3
  if(isatty(0)){
4
    write(2, "$ ", 2);
5
  }
6
  ...
7
}

2. tab completion (easy?)#

难度诈骗，实际上实现tab补全需要非常仔细，并且需要修改内核代码,这给当时还是初学者的我带来了不小的打击.

想要实现一个tab补全功能首先需要让用户按的tab能被捕获，但是一般情况下，我们在termial的命令行中输入字符只有在按下回车后才会被整行传递给shell中的处理函数，我们在按下tab时无法让shell及时做出反应，因此我们需要阅读内核中负责键盘io的部分，添加相应逻辑，这一部分在xv6中的console.c中.

网络上有许多关于xv6代码的解读，这篇博客详细解读了console和uart的交互与实现，我在这里简单介绍一下console.c中的部分代码

首先是consoleintr函数，这个函数在键盘中断发生时被调用，用于解读键盘输入的数据存入cons.buf中，并且在回车到达时唤醒用户程序，将buf中的数据传递给用户程序

1
//
2
// the console input interrupt handler.
3
// uartintr() calls this for input character.
4
// do erase/kill processing, append to cons.buf,
5
// wake up consoleread() if a whole line has arrived.
6
//
7
void
8
consoleintr(int c)
9
{...}

接着是consoleread函数，这个函数在用户程序调用read函数时被调用，用于将buf中的数据传递给用户程序

1
// user read()s from the console go here.
2
// copy (up to) a whole input line to dst.
3
// user_dist indicates whether dst is a user
4
// or kernel address.
5
//
6
int
7
consoleread(int user_dst, uint64 dst, int n)
8
{...}

consolewrite函数在用户调用write时调用，用于将数据输出

1
//
2
// user write()s to the console go here.
3
//
4
int
5
consolewrite(int user_src, uint64 src, int n)
6
{...}

consputc函数用于将字符写入到console中，让用户可见

1
//
2
// send one character to the uart.
3
// called by printf(), and to echo input characters,
4
// but not from write().
5
//
6
void
7
consputc(int c)
8
{
9
  if(c == BACKSPACE){
10
    // if the user typed backspace, overwrite with a space.
11
    uartputc_sync('\b'); uartputc_sync(' '); uartputc_sync('\b');
12
  } else {
13
    uartputc_sync(c);
14
  }
15
}

consputc与consolewrite的最大区别在于consputc后的字符对用户而言是可修改的，而consolewrite后的字符是不可修改的，在接下来实现tab补全时非常重要.

首先我们需要实现在用户按下tab时，我们的shell能够捕获到这个事件并且做出反应，所以我们修改consoleintr函数，添加对tab的捕获.

1
// console.c  consoleintr()
2
  switch(c){
3
  case C('P'):  // Print process list.
4
    procdump();
5
    break;
6
  case C('U'):  // Kill line.
7
    while(cons.e != cons.w &&
8
          cons.buf[(cons.e-1) % INPUT_BUF_SIZE] != '\n'){
9
      cons.e--;
10
      consputc(BACKSPACE);
11
    }
12
    break;
13
  case C('H'): // Backspace
14
  case '\x7f': // Delete key
15
    if(cons.e != cons.w){
16
      cons.e--;
17
      consputc(BACKSPACE);
18
    }
19
    break;
20
  case '\t': // 添加对tab的捕获，在用户按下tab时将缓存区保存并返回到用户程序
21
    cons.buf[cons.e++ % INPUT_BUF_SIZE] = c;
22
    cons.w = cons.e;
23
    wakeup(&cons.r);
24
    break;
25
  default:
26
    if(c != 0 && cons.e-cons.r < INPUT_BUF_SIZE){
27
      c = (c == '\r') ? '\n' : c;
28

29
      // echo back to the user.
30
      consputc(c);
31

32
      // store for consumption by consoleread().
33
      cons.buf[cons.e++ % INPUT_BUF_SIZE] = c;
34

35
      if(c == '\n' || c == C('D') || cons.e-cons.r == INPUT_BUF_SIZE){
36
        // wake up consoleread() if a whole line (or end-of-file)
37
        // has arrived.
38
        cons.w = cons.e;
39
        wakeup(&cons.r);
40
      }
41
    }
42
    break;
43
  }

此时我们的console会在用户按下tab时返回到sh.c的getcmd函数，我们在getcmd函数中添加对tab的处理逻辑.

1
int
2
getcmd(char *buf, int nbuf)
3
{
4
  ...
5
  int i, cc;
6
  char c;
7

8
  for(i=0; i+1 < nbuf; ){
9
    cc = read(0, &c, 1);
10
    if(cc < 1)
11
      break;
12
    if(i != 0 && c == '\t' && (buf[i-1] != '\t' )){
13
      autocomplete(buf , &i);
14
      continue;
15
      ...
16
}

我们在已有输入时按下tab后调用autocomplete函数，将buf补全成当前目录下前缀相同的文件名，同时echoback到console上(非常重要),并且还要确保echoback到console上的字符是可修改的. 于是我们在consolewrite函数中添加一项逻辑，如果程序调用write时传入的第一个字符是\t，我们就开启autocomplete模式，将write的内容模拟成用户输入echo到console上.

1
//
2
// user write()s to the console go here.
3
//
4
int
5
consolewrite(int user_src, uint64 src, int n)
6
{
7
  int i;
8
  int tabcomplete = 0;
9
  for(i = 0; i < n; i++){
10
    char c;
11
    if(either_copyin(&c, user_src, src+i, 1) == -1)
12
      break;
13
    if(i == 0 && c == '\t'){
14
      tabcomplete = 1;
15
      continue;
16
    }
17
    if(tabcomplete){
18
      // 模拟用户输入
19
      consputc(c);
20
      cons.buf[cons.e++ % INPUT_BUF_SIZE] = c;
21
    }else{
22
    uartputc(c);
23
    }
24

25
  }
26

27
  return i;
28
}

同时添加writetostdin函数用于模拟用户输入的过程

1
void writetostdin(char * buf){
2
  char bufx[128];
3
  strcpy(bufx , "\t");
4
  strcpy(bufx+1 , buf);
5
  write(1, bufx , strlen(bufx));
6
}

并且封装一个writetofront函数用来把光标放在行首

1
void writetofront(char * buf){
2
    printf("\r$ ");
3
    writetostdin(buf);
4
}

于是我们便可以在autocomplete函数中调用writetofront函数，将补全的内容写入到console中(匹配前缀的部分写的非常丑陋就不放出来了，代码放在了github里可以自己查阅)

1
// sh.c  autocomplete
2
  if(nr == 1){
3
    //只有一个匹配项，直接补全
4
    char newbuf[128] ;
5
    strcpy(newbuf , buf);
6
    strcpy(newbuf + strlen(buf) , names[0] + strlen(prefix));
7
    writetofront(newbuf);
8
    strcpy(buf , newbuf);
9
    *index = 0;
10
  }else if(nr > 1){
11
    //有多个匹配项，打印出来
12
    printf("\n$ ");
13
    for(int i = 0 ; i < nr ; i++){
14
      printf("%s   " , names[i]);
15
    }
16
    printf("\n$ ");
17
    writeToSTDIN(buf);
18
    *index = 0;
19
  } else if (nr == 0){
20
    writetofront(buf);
21
    *index = 0;
22
  }

至此我们便还原了一个看起来有模有样的自动补全功能.

无论从什么方面来看，这个问题都不是一个easy的问题，本人在做的时候也查阅了非常多的资料踩了很多很多坑才非常丑陋的实现了这个功能，但可以说得上非常收益匪浅，了解了许多关于console,terminal,tty,pty的知识，总体来看还是非常推荐大家也去尝试一下这个问题

3.history of commands (moderate)#

在有了上一个问题的经验之后再去做这个问题就非常得心应手了，问题的核心便在于读取用户的上与下方向键，再将历史命令储存到环形数组中用于回溯.

首先是实现对上下(\e[A 与 \e[B)方向键捕获的支持，我们需要在consoleintr函数中添加状态机来捕获由三个字符组成的方向键输入

1
enum {
2
  NORMAL = 0,
3
  ESCAPE = 1,
4
  LBRACKET = 2,
5
} state = NORMAL;
6

7
void
8
consoleintr(int c)
9
{
10
  acquire(&cons.lock);
11

12
  switch (state) {
13
      case NORMAL:
14
        if(c == '\e'){
15
          state = ESCAPE;
16
        } else{
17
          normal_intr(c);
18
        }
19
        break;
20
      case ESCAPE:
21
        if(c == '['){
22
          state = LBRACKET;
23
        } else{
24
          state = NORMAL;
25
        }
26
        break;
27
      case LBRACKET:
28
        escape_intr(c);
29
        state = NORMAL;
30
        break;
31
  }
32
  release(&cons.lock);
33
}
34

35
void escape_intr(int c){ //处理 \e[ 类型的终端，需要引入状态机
36
  switch (c) {
37
    case 'A': // 上
38
    case 'B': // 下
39
      // 清空缓存区
40
      while(cons.e != cons.w){
41
        cons.e --;
42
        consputc(BACKSPACE);
43
      }
44
      // 把上下键返回给用户终端
45
    cons.buf[cons.e++ % INPUT_BUF_SIZE] = '\e';
46
    cons.buf[cons.e++ % INPUT_BUF_SIZE] = '[';
47
    cons.buf[cons.e++ % INPUT_BUF_SIZE] = c;
48
    cons.w = cons.e;
49
    wakeup(&cons.r);
50
  }
51

52
}

然后在shell中加入环形数组用于储存历史命令

1
#define HISTORY_MAX  21
2
static char history[HISTORY_MAX][100];
3
static int hst;
4
static int hend;
5
static int hpos;
6

7
void add_history(const char * cmd){
8
  int size = hend - hst;
9
  strcpy(history[hend] , cmd);
10
  history[hend][strlen(cmd) - 1] = '\0';
11
  hend = (hend + 1) % HISTORY_MAX;
12
  hpos = hend;
13
  if(size == -1){
14
    hst = (hst + 1) % HISTORY_MAX;
15
  }
16
}

处理上下键的逻辑

1
// sh.c getcmd
2
if(c == '\e'){
3
      char a , b;
4
      read(0 , &a , 1);
5
      read(0 , &b , 1);
6
      if(a != '[')
7
        continue;
8
      if(b == 'A'){
9
        // up
10
        if(hpos == hst){
11
          continue;
12
        }
13
        hpos = (hpos - 1 + HISTORY_MAX) % HISTORY_MAX;
14
        strcpy(buf , history[hpos]);
15
        writeToSTDIN(buf);
16
        i = 0;
17
        continue;
18
      }else if (b == 'B'){
19
        if(hpos == hend){
20
          continue;
21
        }
22
        hpos = (hpos + 1) % HISTORY_MAX;
23
        strcpy(buf , history[hpos]);
24
        writeToSTDIN(buf);
25
        i = 0;
26
        continue;
27
      }
28
    }

main 函数中添加对历史命令的处理

1
// sh.c main
2
  while(getcmd(buf, sizeof(buf)) >= 0){
3
    if(strlen(buf) > 1)  add_history(buf);
4
    ...
5
    }

至此便实现了一个简单的历史命令功能.

在认清生活的真相之后依然热爱生活

1. do not print $ in files (moderate)#

2. tab completion (easy?)#

3.history of commands (moderate)#