Unix考古記：一個“遺失”的shell

歷史的塵埃

Unix作為一個舉世聞名的操作系統(tǒng)已有40余年的歷史，圍繞著這個古老的操作系統(tǒng)的發(fā)展又衍生出了一系列外圍軟件生態(tài)群，其中一個非常重要的組件就是shell。它是操作系統(tǒng)最外層的接口，負(fù)責(zé)直接面向用戶交互并提供內(nèi)核服務(wù)，包括命令行接口(CLI)或圖形界面接口(GUI)兩種形式。以CLI為例，它提供一套命令規(guī)范，是一種解釋性語言，將用戶輸入經(jīng)過解釋器(interpreter)輸出使其轉(zhuǎn)化成真正的系統(tǒng)調(diào)用，實(shí)現(xiàn)人機(jī)交互的功能。

和操作系統(tǒng)一樣，shell也經(jīng)歷了一個漫長的演變史。如今大部分資料講述最古老的shell都是從1977年的Bourne Shell說起的，它最初移植到Unix V7上，被追認(rèn)整個shell家族成員的鼻祖，后來的種群都是從其身上分支出來的。

對于1977年之前的歷史很多資料大多一筆帶過或略過不提。事實(shí)上，第一個移植到Unix上的shell卻不是Steve Bourne寫的，早在1975年5月，貝爾實(shí)驗(yàn)室就對外發(fā)布了第一個廣泛傳播的Unix版本——Unix V6（之前開發(fā)的版本只供內(nèi)部研究之用），其根目錄下的/bin/sh是第一個Unix自帶的shell，由Ken Thompson寫的，因此也被稱為Thompson Shell。甚至，更早可以追溯到1971年的時(shí)候，Thompson Shell就作為一個獨(dú)立于內(nèi)核的應(yīng)用程序而實(shí)現(xiàn)了，只不過從1975年正式問世到1977年被取代，短短兩年的壽命使得它很少為大多數(shù)人所認(rèn)識。

關(guān)于Thompson Shell被取代的原因在后文中會給出說明，這里著重介紹一下該shell本身的一些技術(shù)細(xì)節(jié)。坦白講，關(guān)于Thompson Shell的資料有點(diǎn)稀缺，但至少還能從網(wǎng)上找到源代碼和在線文檔。Thompson Shell本身是由一個不足900行代碼的解釋器和一些外部命令工具組件(utilities)構(gòu)成，用K&R C寫成，下面給出各個組件的相關(guān)源碼和文檔鏈接。

• 解釋器sh：解析各種shell命令，包括內(nèi)置命令和外部命令；源碼sh.c；安裝路徑/bin/sh；手冊sh(1)。

• 內(nèi)置命令手冊包括chdir(1)，login(1)，newgrp(1)，shift(1)，wait(1)。

下面是外部命令：

• exit命令：退出一個文件；源碼exit.c；安裝路徑/bin/exit；手冊exit(1)。

• goto命令：在一個文件內(nèi)跳轉(zhuǎn)shell控制流程；源碼goto.c；安裝路徑/bin/goto；手冊goto(1)。

• if命令：條件判斷表達(dá)式，是test命令的前身；源碼if.c；安裝路徑/bin/if), 手冊if(1)。

• glob命令：擴(kuò)展命令參數(shù)通配符；源碼glob.c；安裝路徑/etc/glob；手冊glob(8)。

命令結(jié)構(gòu)和規(guī)范

盡管后來遭“埋汰”，Thompson Shell仍有著不容否認(rèn)的歷史地位，其最大的價(jià)值在于它奠定了shell命令語言結(jié)構(gòu)和規(guī)范的基礎(chǔ)，而且其解釋器具有跨平臺的可移植性，并影響到了后來包括Bourne Shell在內(nèi)的各種腳本語言設(shè)計(jì)實(shí)現(xiàn)。下面我們就以其中5個特性重溫一些大家已經(jīng)耳熟能詳?shù)拿钜?guī)范，你也可以通過sh(1)手冊查看原始資料。

• 過濾器/管道線(filter/pipeline)。這絕對是要載入U(xiǎn)nix史冊的發(fā)明，創(chuàng)立者是Douglas McIlroy，Thompson Shell引入并實(shí)現(xiàn)了這個偉大的概念——一個或多個命令組成一根過濾器的鏈條，由’|'或’^'符號分隔。除最后一個命令之外，每個命令的標(biāo)準(zhǔn)輸出都被作為下一個命令的標(biāo)準(zhǔn)輸入。這樣每個命令都作為一個獨(dú)立的進(jìn)程來運(yùn)行，并通過管道與鄰近的進(jìn)程相連接。圓括弧內(nèi)的命令序列整體上可以替代單個命令作為過濾器實(shí)現(xiàn)，比如用戶可以輸入”(A;B)|C”。

• 命令序列和后臺進(jìn)程。分號’;'指示多個命令序列化執(zhí)行。’&’符號指示該命令在后臺異步執(zhí)行，使得前面的管道線不必等待其終止，僅僅報(bào)告一個進(jìn)程id，這樣用戶以后可以通過kill命令與它通信。有益于進(jìn)程管理。

• I/O重定向。它利用了Unix設(shè)計(jì)上的一個重要特性——一切皆文件，用三個符號表示：”重定向輸出，如果文件不存在則創(chuàng)建它，如果文件存在則截?cái)嗨弧?gt;>’追加模式重定向輸出，如果文件不存在則創(chuàng)建它，如果文件存在則追加輸出至末尾處。

• 通配符擴(kuò)展(globbing)。通配符的概念源自于正則表達(dá)式，使得解釋器智能地處理用戶不完全輸入，比如記不清文件名、一次性輸入多個文件等。’?'匹配任意單一字符；’*'匹配任意字符串（包括空串）；成對’['和']‘定義了字符集合一個類，可匹配方括號內(nèi)任意成員，用’-'兩端可指定一系列連續(xù)字符匹配范圍。

• 參數(shù)傳遞。這里主要引入了位置參數(shù)和選項(xiàng)參數(shù)的概念：’$n’指示shell調(diào)用的第n個參數(shù)替代；還定義了兩個選項(xiàng)參數(shù)’-t’和’-c’，前者用于交互，導(dǎo)致shell從標(biāo)準(zhǔn)輸入中讀入一行作為用戶執(zhí)行的系統(tǒng)命令，后者指示shell將附帶的下一個參數(shù)作為命令執(zhí)行（可正確處理換行符），是對’-t’的補(bǔ)充，特別是調(diào)用者已經(jīng)讀取了命令其中某些字符的情況下。如果不帶選項(xiàng)參數(shù)則直接讀取文件名

解釋器的原理與實(shí)現(xiàn)

接下來馬上要進(jìn)入核心部分了，為了搞懂shell解釋器原理，我們要對其整個工作流程做個描述（這里給出一份帶注解的sh.c源碼剖析）。讀過《編譯原理》的同學(xué)知道，解釋器的實(shí)現(xiàn)跟編譯器差不多，只不過省略了生成目標(biāo)代碼這一步，直接將用戶輸入（shell命令）轉(zhuǎn)化成輸出（系統(tǒng)調(diào)用）。軟件前端是一致的，包括預(yù)處理、詞法掃描、語法分析和語義分析，最后還要附加一個進(jìn)程管理。當(dāng)然相較于現(xiàn)代編譯器，Thompson Shell解釋器在算法和規(guī)模上都要簡單得多，不過原理上是相通的，何況年代上要比Lex & Yacc還要早。麻雀雖小，五臟俱全，對于初學(xué)者來說，從Thompson Shell去入手編譯原理或許不失為一種好選擇。

預(yù)處理(preprocessor)

同C預(yù)處理器需要事先將源代碼中包含的宏和頭文件展開一樣，Thompson Shell首先需要處理命令中的選項(xiàng)參數(shù)和位置參數(shù)。選項(xiàng)參數(shù)有兩種’-t’和’-c’，決定了shell從標(biāo)準(zhǔn)輸入還是參數(shù)緩存中讀取字符（見sh(1)）。此外字符序列中還要處理反斜杠’\’，判斷是轉(zhuǎn)義字符還是行接續(xù)符，前者對下一個字符設(shè)置引用標(biāo)識，表明做普通字符處理，后者將緊鄰其后換行符過濾掉。

位置參數(shù)是美元符號’$’打頭的，后帶一個數(shù)字，如’$n’，預(yù)處理器對shell命令參數(shù)從頭開始計(jì)數(shù)，返回?cái)?shù)字n指定的參數(shù)位置。如果遇上double’$$’，則表示當(dāng)前的進(jìn)程標(biāo)識，調(diào)用getpid()獲取。

注意到預(yù)處理器需要一次讀取多個字符，這樣就會多讀一個不必要的字符。對此解釋器提供了一種預(yù)讀(peek)方式，即每次從輸入流讀取一個字符時(shí)，放入一個預(yù)讀緩存里（只有一個int大小的堆棧），也叫回退(push back)。此后先從預(yù)讀緩存中讀取，如果緩存被讀完，則從輸入流中讀取。

詞法掃描(lexical scanning)

經(jīng)過預(yù)處理后的字符序列將被切割成為一系列詞法記號(token)，安置在token列表中，掃描器將對以下幾類字符做如下處理。

• 空格和tab：簡單過濾。

• 引號：需要成對出現(xiàn)，字符本身被過濾，一對引號之間所有字符都被設(shè)置引用標(biāo)識，作為一個token。

• 元字符：如’&’，’|'等，字符本身作為一個單獨(dú)token。

• 其他字符：一律填充token，直到碰上以上字符分隔為止。

舉一個例子，當(dāng)我們輸入命令”(ls; cat tail) >junk”，那么token列表映像將是這樣的：

語法分析(syntax parser)

語法分析就是將token列表中的元素作為表達(dá)式(expression)并以節(jié)點(diǎn)為單位構(gòu)建語法樹，簡單命令是一個表達(dá)式，而復(fù)合命令以及命令序列是多個表達(dá)式的組合。Thompson Shell中以簡單數(shù)組作為語法樹的容器，實(shí)際上這是結(jié)構(gòu)體的一種變形，只不過每個成員字段大小都一樣（都是sizeof int）而已。一個語法樹節(jié)點(diǎn)最多有6個字段（大小根據(jù)類型可變），分別是

• DTYP（節(jié)點(diǎn)類型）：每個節(jié)點(diǎn)都有唯一的類型，又分為四種——TCOM（簡單命令）、TPAR（復(fù)合命令）、TFIL（過濾器/管道線）、TLST（命令序列）。

• DLEF（左子樹節(jié)點(diǎn)）：相當(dāng)于鏈表指針，根據(jù)DTYP定義有所不同。如過濾器類型左子樹節(jié)點(diǎn)為前一個命令的輸出重定向文件，右子樹節(jié)點(diǎn)為后一個命令的輸入重定向文件。

• DRIG（右子樹節(jié)點(diǎn)）：同上。

• DFLG（節(jié)點(diǎn)屬性）：這是個標(biāo)志位(flag)，決定該節(jié)點(diǎn)包含命令的屬性以及以什么樣的狀態(tài)執(zhí)行。

• DSPR（子命令）：兩重含義，對于簡單命令，該字段為空；對于復(fù)合命令，該字段指向子語法樹節(jié)點(diǎn)。

• DCOM（命令字符）：引用命令字符序列。

語法樹節(jié)點(diǎn)生成順序根據(jù)token列表中每個元素的優(yōu)先級(priority)而定，首先遍歷整個列表，找到優(yōu)先級最高的token作為根節(jié)點(diǎn)，再分別生成左右子樹，這是一種最簡單的自頂向下(top-down)解決方案。各個token優(yōu)先級視DTYP字段而定

語法樹的構(gòu)建過程中還使用了一種基于“有限狀態(tài)機(jī)(finite-state machine)”的動態(tài)規(guī)劃算法，其實(shí)現(xiàn)是將整個邏輯流程劃分為四個狀態(tài)：syntax、syn1、syn2、syn3，對應(yīng)于上面token優(yōu)先級，程序在每個狀態(tài)下都生成一個相應(yīng)類型的節(jié)點(diǎn)，同時(shí)還生成四種策略，以決議下一步將轉(zhuǎn)移到何種狀態(tài)（根據(jù)優(yōu)先級搜索對應(yīng)的token）。這個四種策略分別是

• 生成左子樹：左邊token列表遞進(jìn)到下層狀態(tài)。

• 生成右子樹：右邊token列表并回溯到上層狀態(tài)或遞歸調(diào)用。

• 找不到對應(yīng)token：保持原有token列表遞進(jìn)到下層狀態(tài)。

• 生成節(jié)點(diǎn)：直接返回節(jié)點(diǎn)。

當(dāng)我們遍歷完整個token列表后，程序總是能返回最初的調(diào)用點(diǎn)，即根節(jié)點(diǎn)上，從而生成一棵完整的語法樹。這種算法的好處是程序員不必關(guān)注具體實(shí)現(xiàn)的每個細(xì)枝末節(jié)，只要關(guān)注相應(yīng)的狀態(tài)并制定對應(yīng)的轉(zhuǎn)移策略即可。還值得一提的是每個轉(zhuǎn)移策略都是發(fā)生在賦值語句或返回語句上，并使用函數(shù)實(shí)參保存臨時(shí)變量，這樣就避免了調(diào)用次數(shù)過多導(dǎo)致堆棧溢出。

依舊舉兩個個例子，比如命令”A & ; B | C”對應(yīng)的語法樹

命令”(A ; B) | C”對應(yīng)的語法樹：

語義分析(Semantic Analyzer)

語法分析僅僅停留在token表達(dá)式合法性層面上，它并不知道該表達(dá)式是否有意義，比如哪些命令是要后臺運(yùn)行，哪些命令的I/O被重定向到管道線上，通配符該如何擴(kuò)展等等，這時(shí)候要靠語義分析了。這里的“語義”體現(xiàn)在對特殊字符的動態(tài)處理以及語法樹節(jié)點(diǎn)的字段設(shè)置，根據(jù)上下文(context)而定。比如對于元字符’>’，我們要判斷輸出重定向到哪個文件，是截?cái)噙€是追加。對于通配符’?'、’*'和’[...]‘，我們要決定對哪些字符進(jìn)行擴(kuò)展，這些在/etc/glob中專門處理。對于語法樹節(jié)點(diǎn)，除了自身固有屬性之外，還需要繼承上層節(jié)點(diǎn)的屬性，以及下推屬性到下層子樹節(jié)點(diǎn)，下面列了一張表格說明。

執(zhí)行命令(Executor)

當(dāng)前面一系列步驟之后，如果錯誤計(jì)數(shù)為0，則解釋器從語法樹的根節(jié)點(diǎn)開始，深度優(yōu)先遍歷所有節(jié)點(diǎn)，并根據(jù)前面語法和語義分析得到的類型和屬性，一一執(zhí)行所包含的命令，以生成最后的系統(tǒng)調(diào)用。

對于命令序列(TLST)節(jié)點(diǎn)，從左至右順序執(zhí)行子樹節(jié)點(diǎn)命令。

對于過濾器(TFIL)節(jié)點(diǎn)，創(chuàng)建管道文件句柄，作為左右子樹的重定向文件。

對于簡單命令(TCOM)和復(fù)合命令(TPAR)節(jié)點(diǎn)，首先篩選出系統(tǒng)內(nèi)置命令(built-in)，對于剩下的外部命令則fork一個子進(jìn)程執(zhí)行它。如果是復(fù)合命令中最后一個子命令，那么仍在原來的進(jìn)程上執(zhí)行而不必創(chuàng)建新進(jìn)程?？蓤?zhí)行文件路徑按先后順序搜索：①本地路徑；②/bin；③/usr/bin。

多進(jìn)程環(huán)境下，特別要注意文件句柄管理。命令間共享標(biāo)準(zhǔn)輸入輸出設(shè)備之外，還會重定向到管道線，而父進(jìn)程在fork之后子進(jìn)程會獲取一份文件句柄拷貝，所以父進(jìn)程必須在fork之后立即關(guān)閉閑置的管道線句柄（如果有的話）以免造成資源泄漏，子進(jìn)程也將在重定向之后關(guān)閉管道線句柄。

對于后臺命令需要打印pid，但不需要響應(yīng)中斷信號，父進(jìn)程也不必等待子進(jìn)程終止。其余進(jìn)程命令執(zhí)行中可捕獲中斷信號，并轉(zhuǎn)入相應(yīng)的處理函數(shù)。

解釋器用內(nèi)置的errno全局變量保存進(jìn)程終止?fàn)顟B(tài)，并生成終止報(bào)告(termination report)，系統(tǒng)調(diào)用wait()用于返回終止進(jìn)程的pid并輸出報(bào)告消息索引。

孰優(yōu)孰劣

盡管Thompson Shell是一款優(yōu)秀的命令解釋器，還產(chǎn)生了多項(xiàng)歷史創(chuàng)舉，但遺憾的是依然得不到命運(yùn)女神的垂青，這要?dú)w咎于其自身的缺陷——功能單一、命令分散、控制流過于簡單，尚無法用來編寫腳本(script)。隨著Unix日益壯大，它已經(jīng)無法應(yīng)付趨于繁雜的編程項(xiàng)目了。那時(shí)還出現(xiàn)了一個叫John Mashey的人寫的PWB Shell（又叫做Mashey Shell），基于Thompson Shell做了些改進(jìn)，擴(kuò)展了命令集，增加了shell變量，還增加了if-then-else-endif，for，while等控制邏輯。不幸的是它比Thompson Shell更短命，因?yàn)?977年它遇上了一個強(qiáng)勁的對手。

沒錯，那就是Bourne Shell，它的主要優(yōu)點(diǎn)是真正實(shí)現(xiàn)了結(jié)構(gòu)化腳本編程，比之前的shell實(shí)現(xiàn)得都要好，更要命的是它與前兩個shell都不兼容，于是一場標(biāo)準(zhǔn)化的論戰(zhàn)開始了。在David G. Korn（ksh作者）寫的“ksh – An Extensible High Level Language”一文中提及，Steve Bourne和John Mashey在三次連續(xù)的Unix用戶組集會上爭論他們各自的理由。在這些集會之間，各自增進(jìn)他們的shell來擁有對方的功能。還設(shè)立了一個委員會來選擇標(biāo)準(zhǔn)shell，最終還是選擇了Bourne shell作為標(biāo)準(zhǔn)。

于是從Unix V7開始就有了前面所說的”Bourne Shell Family”。然而歷史上沒有完美的技術(shù)，隨著八、九十年代操作系統(tǒng)迅猛發(fā)展，針對Bourne Shell的詬病也越來越多了。在解釋器本身實(shí)現(xiàn)上，我看到網(wǎng)上一個對其評價(jià)是“universally considered to be one of the most horrible C code ever written”，至于原因去看一下mac.h就知道了，包括基本運(yùn)算符、關(guān)鍵字在內(nèi)的大量宏定義使得整個代碼看上去簡直不是C寫的，也許Bourne是想把解釋器打造成自己獨(dú)特的風(fēng)格吧，也難怪后來的bash以“born again”命名就是對其祖先的戲謔性調(diào)侃。另外內(nèi)存管理上的一些毛病帶來平臺可移植性問題，至于其中的技術(shù)細(xì)節(jié)有點(diǎn)高級，超出本文范疇。

Thompson Again Shell?

雖然歷史沒有給Thompson Shell一個機(jī)會，但它并非就此同Unix V6那樣一同淪為開源博物館上的古老“化石”。作為出自頂級***之手的作品，作為伴隨Unix那樣偉大操作系統(tǒng)一同曾經(jīng)流行計(jì)算機(jī)的產(chǎn)物，至今仍受國內(nèi)外程序員的緬懷，或?qū)⑵涓膶?，或?yàn)槠渥髯ⅰ１热鐕庖粋€站點(diǎn)v6shell.org上就實(shí)現(xiàn)了一個免費(fèi)開源的可移植性shell，它兼容并擴(kuò)充原來的Thompson Shell并且可用來做腳本編程。再比如中國程序員寒蟬退士在其個人博客上發(fā)布了一個注解版，并對原版做了一些改寫，主要是將K&R C轉(zhuǎn)為ANSI C，并且符合POSIX規(guī)范，使原本晦澀難懂的源碼變得清晰易讀起來。正是因?yàn)榻佑|到他的版本激起了我對老Unix的考古興趣，才有了這篇“考古筆記”。我在想不知今后會不會像bash那樣，出一個tash來呢？

一些感想

本來全文應(yīng)該就此結(jié)束了，但此時(shí)此刻不禁想多說幾句。這篇筆記當(dāng)初并非有意而為之，在hacking源碼的過程中感想積累多了也就逐漸成章了。看代碼、作注解、查資料、寫此文，前后歷經(jīng)四個多礼拜，是在繁雜的工作中“擠乳溝”擠出來的零散時(shí)間片拼湊起來的，雖然文字不長但也算耗費(fèi)了一番心血，酸甜苦辣心中自明，體會到踏上社會之后潛下心做研究之艱難。如今面對這樣一份不到900行寫成的，沒有一行多余的代碼，簡潔(clarity)、干凈(clean)、快速(fast)，這就是Pure C的魅力，我深為這種厚重的編程功力所折服，正所謂“大道至簡”吧。雖然要完全弄懂它需要很多時(shí)間，但我相信這種代價(jià)卻是值得的。

最后再八卦一下，2011年Dennis Ritchie去世了，有人生前問過他“學(xué)C需要多久才能成為熟練開發(fā)者并寫出重要產(chǎn)品代碼？”，Ritchie回答“我不知道，我從沒去學(xué)過C?！?I don’t know. I never had to learn C.)其實(shí)這里已經(jīng)給出了答案——那就是沒有比去閱讀Unix源代碼更好的選擇了，某種意義上C語言就是為Unix而生的。

參考資料

The Unix Heritage Society：Unix社區(qū)遺產(chǎn)，上面有v6和v7以及其它一些衍生版本的操作系統(tǒng)源代碼。

The Traditional Bourne Shell Family：Bourne Shell家族簡史。

v6shell：osh，一個基于Thompson Shell的開源可移植性old shell。

寒蟬退士的博客：Thompson Shell的一個注解版。

Evolution of shells in Linux：簡述Linux Shell演變史。

附錄一個中文注釋的 shell源碼