60行C程式碼實現一個shell

• 2019 年 10 月 4 日
• 筆記

我們來看看如何60行C程式碼實現一個shell！

在實現它之前，先看看這樣做的意義。

美是有目共睹的。Unix之美，稍微體會，便能得到。

1969年，Unix初始，沒有fork，沒有exec，沒有pipe，沒有 「一切皆文件」 ，但是那時它已經是Unix了。它簡單，可塑。

Melvin Conway在1963年的論文中敘述fork思想時就解釋說並行路徑要用結果來交互，也就是在匯合的join點來同步結果。這個同步點所得到的，就是一個並行進程的 輸出 。

在此之外，Unix還有另一個原則，就是 組合小程式！

Unix把一系列功能單一的小程式組合成一個複雜的邏輯，這個原則有以下優勢：

• 每一個小程式都很容易編寫。
• 每一個小程式可以分別完成。
• 每一個小程式可以分別迭代修復。
• 多個小程式可以自由組合。
• …

這是典型的模組化思想，小到統籌佐餐燒飯，大到組成生命的嘌呤嘧啶，都不自覺地和這種模組化思想相契機，原來這就是真理。 程式盡量小，只做一件事並且做好它。

Unix程式在自身的邏輯之外對外暴露的只有輸入和輸出。那麼 用輸出連接另一個程式輸入 就是一種好的方法。所謂Conway的join點對於Unix進程指的就是輸出。

對外暴露的越少，程式越內聚。這是一種範式，類似RISC處理器也是抽象出僅有的load和store來和記憶體交互。

簡單來講，Unix程式通過輸入和輸出來彼此連接。下面是一幅來自Wiki的圖示：

詳見Pipeline (Unix)： https://en.wikipedia.org/wiki/Pipeline_(Unix)

Unix的另一個原則，即著名的 「一切皆文件！」 連接輸出和輸入的那個管道在Unix中被實現為Pipe，顯然，它也是文件，一個FIFO文件。

說實話，協作幾個小程式形成一個大邏輯的思想還是來自於Convey，在Convey的論文里，他稱為 協程， Pile可以說是直接實現了 Convey協程 之間的交互。有關這段歷史，請看： http://www.softpanorama.org/Scripting/Piporama/history.shtml

用Pipe連接作為輸出和輸入連接Unix進程可以做成什麼事情呢？讓我們去感受一個再熟悉不過的實例，即數學式子：

我們把運算符加號，乘號，除號(暫不考慮括弧，稍後解釋為什麼)這些看作是程式(事實上它們也真的是)，那麼類似數字3，5，7，6就是這些程式的輸入了，這個式子最終需要一個輸出，獲得這個輸出的過程如下：

1. 數字3，5是加號程式的輸入，3+5執行，它獲得輸出8.
2. 第1步中的輸出8連同數字7作為乘號程式的輸入，8 × 7執行，獲得輸出56.
3. 第2步中的輸出56連同數字6作為除號的輸入，…

這個數學式子的求值過程和pipe連接的Unix程式組合獲得最終結果的過程完全一致。

如果你相信數學可以描述整個世界，那麼Pipe連同Unix程式同樣是描述這個世界的語言 。

在數學領域，程式 就是所有的運算符，加號，減號，乘號，除號，乘方，開方，求和，積分，求導…它們無一例外， 只做一件事。

在Unix看來也同樣。它做的事情和下面的應該差不多，而且更多：

寫出上面的式子中每一個數學運算符的程式並不困難，比如加號程式：

// plus.c  #include <stdio.h>  int main(int argc, char **argv)  {  	int a, b;    	a = atoi(argv[1]);  	b = atoi(argv[2]);    	a = a + b;  	printf("%dn", a);  }  

同樣，我們可以寫出除法，直到偏導的程式。然後我們通過pipe就能將它們組合成任意的數學式子。

現在談談Unix組合程式的具體寫法，如果我們要化簡薛定諤方程，我們應該如何用Unix命令寫出與上述式子等價的組合程式命令行呢？我們無法像數學家手寫那樣隨意使用括弧，顯然，電腦並不認識它。我們能夠使用的只有兩個符號：

1. 代表具體Unix小程式的命令。
2. Pipe符號"|"。

換句話說，我們需要寫出一個 鏈式組合表達式。 這時就要用到前綴表達式了。

數學式子里的括弧，其實它無關緊要，括弧只是給人看的，它規定一些運算的優先順序順序，這叫 中綴表達式 ，一個中綴表達式可以輕鬆被轉換為 前綴表達式，後綴表達式 ，從而消除括弧。事實上，Unix的Pipe最初也面臨過這樣的問題，到底是中綴好呢，還是前/後綴好呢？

我們現在使用的Unix/Linux命令，以cp舉例：

cp $in $out  

這是一個典型的前綴表達式，但是當pipe的發明者McIlroy最初引入pipe試圖組合各個程式時，最初上面的命令行被建議成：

$in cp $out  

就像我們的(3 + 5) × 8 一樣。但是這非常不適合電腦處理的風格，電腦不得不首先掃描解析這個式子，試圖：

1. 理解 「括弧括起來的要優先處理」 這句複雜的話；
2. 區分哪些是輸入，哪些是操作符…

對於式子(3 + 5) × 8 的求值，電腦更適合用一種在簡單規則下非常直接的方式去 順序執行 求解，這就是前綴表達式的優勢。

× 8 + 35就是(3 + 5) × 8 的前綴表達式，可以看到，沒有了括弧。對於pipe組合程式而言，同樣適用於這個原則。於是前綴命令成了pipe組合命令的首選，現如今，我們可以用：

pro1 $stdin|pro2|pro3|pro4|...|proX $stdout  

輕鬆組合成任意複雜的邏輯。

Pipe協同組合程式的Unix原則是一個創舉，程式就是一個加工過濾器，它把一系列的輸入經過自己的程式邏輯生成了一系列的輸出，該輸出又可以作為其它程式的輸入。

在Unix/Linux中，各種shell本身就實現了這樣的功能，但是為了徹底理解這種處理方式的本質，只能自己寫一個才行。來寫一個微小的shell吧。

再次看上面提到的Unix Pipe的處理序列：

pro1 $stdin|pro2|pro3|pro4|...|proX $stdout  

如果讓一個shell處理以上組合命令，要想程式碼量少，典型方案就是遞歸，然後用Pipe把這些遞歸調用過程給串起來，基本邏輯如下：

int exec_cmd(CMD *cmd, PIPE pipe)  {      // 持續解析命令行，以pipe符號|分割每一個命令      while (cmd->next) {          PIPE pp = pipe_create();          if (fork() > 0) {              // 父進程遞歸解析下一個              exec_cmd(cmd->next, pp);              return 0;          }          // 子進程執行          dup_in_out(pp);          exec(cmd->cmdline);      }      if (fork() > 0) {          wait_all_child();          return 0;      } else {          dup_in_out(pp);          exec(cmd->cmdline);      }  }  

按照上面的思路實現出來，大概60行左右程式碼就可以：

// tinysh.c  // gcc tinysh.c -o tinysh  #include <stdio.h>  #include <stdlib.h>  #include <unistd.h>  #include <sys/wait.h>    #define CMD_BUF_LEN	512  char cmd[CMD_BUF_LEN] = {0};    void fork_and_exec(char *cmd, int pin, int pout)  {      if (fork() == 0) {          if (pin != -1) {              dup2 (pin, 0);              close(pin);          }          if (pout != -1) {              dup2 (pout, 1);              close(pout);          }          system(cmd);          exit(0);      }  	if (pin != -1)  		close(pin);  	if (pout != -1)  		close(pout);  }    int execute_cmd(char *cmd, int in)  {  	int status;  	char *p = cmd;  	int pipefd[2];    	while (*p) {  		switch (*p) {  		case '|':  			*p++ = 0;  			pipe(pipefd);  			fork_and_exec(cmd, in, pipefd[1]);  			execute_cmd(p, pipefd[0]);  			return 0;  		default:  			p++;  		}  	}  	fork_and_exec(cmd, in, -1);  	while(waitpid(-1, &status, WNOHANG) != -1);  	return 0;  }    int main(int argc, char **argv)  {  	while (1) {  		printf("tiny sh>>");  		gets(cmd);  		if (!strcmp(cmd, "q")) {  			exit(0);  		} else {  			execute_cmd(cmd, -1);  		}  	}  	return 0;  }  

下面是執行tinysh的結果：

[root@10 test]# ls -l  總用量 28  -rw-r--r-- 1 root root    0 9月   1 05:39 a  -rwxr-xr-x 1 root root 9000 9月   1 05:38 a.out  -rw-r--r-- 1 root root    0 9月   1 05:39 b  -rw-r--r-- 1 root root    0 9月   1 05:39 c  -rw-r--r-- 1 root root    0 9月   1 05:39 d  -rw-r--r-- 1 root root    0 9月   1 05:39 e  -rwxr-xr-x 1 root root 9000 9月   1 05:38 tinysh  -rw-r--r-- 1 root root 1167 9月   1 05:38 tinysh.c  [root@10 test]# ./tinysh  tiny sh>>ls -l |wc -l  9  tiny sh>>cat /etc/inittab |grep init  # inittab is no longer used when using systemd.  tiny sh>>cat /etc/inittab |grep init|wc -l  1  tiny sh>>q  [root@10 test]#  

遞歸解析的過程中fork/exec，一氣呵成，這就是一個最簡單shell實現。它可完成組合程式的執行並給出結果。

這個tiny shell命令解析器的邏輯可以表示如下：

現在，讓我們用上面的tiny shell來實現式子

的計算，我需要寫表示四則混合運算符的Unix程式，首先看加號運算符程式，將上文中plus.c改成從標準輸入讀取加數即可：

// plus.c  // gcc plus.c -o plus  #include <stdio.h>  #include <stdlib.h>    int main(int argc, char **argv)  {  	float a, b;    	a = atof(argv[1]);  	scanf("%f", &b);    	b = b + a;  	printf("%fn", b);  }  

再看減法運算符程式程式碼：

// sub.c  // gcc sub.c -o sub  #include <stdio.h>  #include <stdio.h>    int main(int argc, char **argv)  {  	float a, b;    	a = atof(argv[1]);  	scanf("%f", &b);    	b = b - a;  	printf("%fn", b);  }  

接下來是乘法和除法的程式碼：

// times.c  // gcc times.c -o times  #include <stdio.h>  #include <stdio.h>    int main(int argc, char **argv)  {  	float a, b;    	a = atof(argv[1]);  	scanf("%f", &b);    	b = b*a;  	printf("%fn", b);  }  

// div.c  // gcc div.c -o div  #include <stdio.h>  #include <stdio.h>    int main(int argc, char **argv)  {  	int a, b;    	a = atof(argv[1]);  	scanf("%d", &b);    	b = b/a;  	printf("%dn", b);  }  

可以看到，這些都是非常簡單的程式，但是任意組合它們便可以實現任意四則運算，我們看看

這個如何組合。

首先在標準的Linux bash中我們試一下：

[root@10 test]# ./plus 5|./times 7|./sub 20|./div 6  3  6.000000  [root@10 test]#  

計算結果顯然是正確的。現在我在自己實現的tinysh中去做類似的事情：

[root@10 test]# ./tinysh  tiny sh>>./plus 5|./times 7|./sub 20|./div 6  3  6.000000  tiny sh>>q  [root@10 test]#  

可以看到，tinysh的行為和標準Linux bash的行為是一致的。

簡單吧，簡單！無聊吧，無聊！Pipe連接了若干小程式，每一個小程式只做一件事。

如果我們的系統中沒有任何shell程式，比如我們沒有bash，我們只有tinysh，加上以上這4個程式，一共5個程式，就可以完成任意算式的四則混合運算。

現在我們用以上的組合Unix程式的方法試試計算下面的式子：

根號怎麼辦？

按照非Unix的編程風格，就要在程式里寫函數計算開根號，但是用Unix的風格，則只需要再加個開根號的程式即可：

// sqrt.c  // gcc sqrt.c -lm -o sqrt  #include <stdio.h>  #include <stdlib.h>  #include <math.h>    int main(int argc, char *argv[])  {  	float b;    	scanf("%f", &b);    	b = sqrt(b);  	printf("%fn", b);  }  

有了這個開根號的程式，結合已經有的四則運算程式，讓我們的tinysh用pipe將它們串起來，就成了。好了，現在讓我們計算上面的式子：

./tinysh  tiny sh>>./sqrt |./plus 3|./div 2  9  3.000000  tiny sh>>q  

本文該結束了，後面要寫的應該就是關於經典Unix IPC的內容了，是的，自從Pipe之後，Unix便開啟了IPC，System V開始稱為標準並持續引領著未來，但這是另一篇文章的話題了。

最後，來自Unix初創者之一Dennis M. Ritchie關於Unix的滿滿回憶，非常感人：

原文來自 The Evolution of the Unix Time-sharing System ： http://www.read.seas.harvard.edu/~kohler/class/aosref/ritchie84evolution.pdf

（完）