Unix考古记：一个“遗失”的shell

        作者：Leo

        谨以此文纪念伟大的计算机科学巨匠 Ken Thompson 和 Dennis Ritchie，并同时向其他所有为 Unix 发展做出贡献的黑客致敬。

        历史的尘埃

        Unix 作为一个举世闻名的操作系统已有 40 余年的历史，围绕着这个古老的操作系统的发展又衍生出了一系列外围软件生态群，其中一个非常重要的组件就是 shell。它是操作系统最外层的接口，负责直接面向用户交互并提供内核服务，包括命令行接口(CLI)或图形界面接口(GUI)两种形式。以 CLI 为例，它提供一套命令规范，是一种解释性语言，将用户输入经过解释器(interpreter)输出使其转化成真正的系统调用，实现人机交互的功能。

        和操作系统一样，shell 也经历了一个漫长的演变史。如今大部分资料讲述最古老的 shell 都是从 1977 年的 Bourne Shell 说起的，它最初移植到 Unix V7上，被追认整个 shell 家族成员的鼻祖，后来的种群都是从其身上分支出来的。

        对于 1977 年之前的历史很多资料大多一笔带过或略过不提。事实上，第一个移植到 Unix 上的 shell 却不是 Steve Bourne 写的，早在 1975 年 5 月，贝尔实验室就对外发布了第一个广泛传播的 Unix 版本——Unix V6（之前开发的版本只供内部研究之用），其根目录下的/bin/sh 是第一个 Unix 自带的 shell，由 Ken Thompson 写的，因此也被称为 Thompson Shell。甚至，更早可以追溯到 1971 年的时候，Thompson Shell 就作为一个独立于内核的应用程序而实现了，只不过从 1975 年正式问世到 1977 年被取代，短短两年的寿命使得它很少为大多数人所认识。

        关于 Thompson Shell 被取代的原因在后文中会给出说明，这里着重介绍一下该 shell 本身的一些技术细节。坦白讲，关于 Thompson Shell 的资料有点稀缺，但至少还能从网上找到源代码和在线文档。Thompson Shell 本身是由一个不足 900 行代码的解释器和一些外部命令工具组件(utilities)构成，用K&R C 写成，下面给出各个组件的相关源码和文档链接。

• 解释器 sh：解析各种 shell 命令，包括内置命令和外部命令；源码 sh.c；安装路径/bin/sh；手册 sh (1)。
• 内置命令手册包括 chdir (1)，login (1)，newgrp (1)，shift (1)，wait (1)。

        下面是外部命令：

• exit 命令：退出一个文件；源码 exit.c；安装路径/bin/exit；手册 exit (1)。
• goto 命令：在一个文件内跳转 shell 控制流程；源码 goto.c；安装路径/bin/goto；手册 goto (1)。
• if 命令：条件判断表达式，是 test 命令的前身；源码 if.c；安装路径/bin/if)， 手册 if (1)。
• glob 命令：扩展命令参数通配符；源码 glob.c；安装路径/etc/glob；手册 glob (8)。

        命令结构和规范

        尽管后来遭“埋汰”，Thompson Shell 仍有着不容否认的历史地位，其最大的价值在于它奠定了 shell 命令语言结构和规范的基础，而且其解释器具有跨平台的可移植性，并影响到了后来包括 Bourne Shell 在内的各种脚本语言设计实现。下面我们就以其中 5 个特性重温一些大家已经耳熟能详的命令规范，你也可以通过 sh (1)手册查看原始资料。

• 过滤器/管道线(filter/pipeline)。这绝对是要载入 Unix 史册的发明，创立者是 Douglas McIlroy，Thompson Shell 引入并实现了这个伟大的概念——一个或多个命令组成一根过滤器的链条，由’'或’^'符号分隔。除最后一个命令之外，每个命令的标准输出都被作为下一个命 令的标准输入。这样每个命令都作为一个独立的进程来运行，并通过管道与邻近的进程相连接。圆括弧内的命令序列整体上可以替代单个命令作为过滤器实现，比如 用户可以输入”(A;B)C”。
• 命令序列和后台进程。分号’;'指示多个命令序列化执行。’&’符号指示该命令在后台异步执行，使得前面的管道线不必等待其终止，仅仅报告一个进程 id，这样用户以后可以通过 kill 命令与它通信。有益于进程管理。
• I/O重定向。它利用了 Unix 设计上的一个重要特性——一切皆文件，用三个符号表示：”重定向输出，如果文件不存在则创建它，如果文件存在则截断它；’>>’追加模式重定向输出，如果文件不存在则创建它，如果文件存在则追加输出至末尾处。
• 通配符扩展(globbing)。通配符的概念源自于正则表达式，使得解释器智能地处理用户不完全输入，比如 记不清文件名、一次性输入多个文件等。’?'匹配任意单一字符；’*'匹配任意字符串（包括空串）；成对’['和']‘定义了字符集合一个类，可匹配方括 号内任意成员，用’-'两端可指定一系列连续字符匹配范围。
• 参数传递。这里主要引入了位置参数和选项参数的概念：’$n’指示 shell 调用的第n个参数替代；还定义了两个选项参数’-t’和’-c’，前者用于交互，导致 shell 从标准输入中读入一行作为用户执行的系统命令，后者指示 shell 将附带的下一个参数作为命令执行（可正确处理换行符），是对’-t’的补充，特别是调用者已经读取了命令其中某些字符的情况下。如果不带选项参数则直接读 取文件名

        解释器的原理与实现

        接下来马上要进入核心部分了，为了搞懂 shell 解释器原理，我们要对其整个工作流程做个描述（这里给出一份带注解的 sh.c 源码剖析）。读过《编译原理》的同学知道，解释器的实现跟编译器差不多，只不过省略了生成目标代码这一步，直接将用户输入（shell 命令）转化成输出（系统调用）。软件前端是一致的，包括预处理、词法扫描、语法分析和语义分析，最后还要附加一个进程管理。当 然相较于现代编译器，Thompson Shell 解释器在算法和规模上都要简单得多，不过原理上是相通的，何况年代上要比 Lex & Yacc 还要早。麻雀虽小，五脏俱全，对于初学者来说，从 Thompson Shell 去入手编译原理或许不失为一种好选择。

        预处理(preprocessor)

        同C预处理器需要事先将源代码中包含的宏和头文件展开一样，Thompson Shell 首先需要处理命令中的选项参数和位置参数。选项参数有两种’-t’和’-c’，决定了 shell 从标准输入还是参数缓存中读取字符（见 sh (1)）。此外字符序列中还要处理反斜杠’\’，判断是转义字符还是行接续符，前者对下一个字符设置引用标识，表明做普通字符处理，后者将紧邻其后换行符过滤掉。

        位置参数是美元符号’$’打头的，后带一个数字，如’$n’，预处理器对 shell 命令参数从头开始计数，返回数字n指定的参数位置。如果遇上 double’$$’，则表示当前的进程标识，调用 getpid ()获取。

        注意到预处理器需要一次读取多个字符，这样就会多读一个不必要的字符。对此解释器提供了一种预读(peek)方式，即每次从输入流读取一个字符时，放入一个预读缓存里（只有一个 int 大小的堆栈），也叫回退(push back)。此后先从预读缓存中读取，如果缓存被读完，则从输入流中读取。

        词法扫描(lexical scanning)

        经过预处理后的字符序列将被切割成为一系列词法记号(token)，安置在 token 列表中，扫描器将对以下几类字符做如下处理。

• 空格和 tab：简单过滤。
• 引号：需要成对出现，字符本身被过滤，一对引号之间所有字符都被设置引用标识，作为一个 token。
• 元字符：如’&’，’'等，字符本身作为一个单独 token。
• 其他字符：一律填充 token，直到碰上以上字符分隔为止。

        举一个例子，当我们输入命令”(ls; cat tail) >junk”，那么 token 列表映像将是这样的：

        语法分析(syntax parser)

        语法分析就是将 token 列表中的元素作为表达式(expression)并以节点为单位构建语法树， 简单命令是一个表达式，而复合命令以及命令序列是多个表达式的组合。Thompson Shell 中以简单数组作为语法树的容器，实际上这是结构体的一种变形，只不过每个成员字段大小都一样（都是 sizeof int）而已。一个语法树节点最多有 6 个字段（大小根据类型可变），分别是

• DTYP（节点类型）：每个节点都有唯一的类型，又分为四种——TCOM（简单命令）、TPAR（复合命令）、TFIL（过滤器/管道线）、TLST（命令序列）。
• DLEF（左子树节点）：相当于链表指针，根据 DTYP 定义有所不同。如过滤器类型左子树节点为前一个命令的输出重定向文件，右子树节点为后一个命令的输入重定向文件。
• DRIG（右子树节点）：同上。
• DFLG（节点属性）：这是个标志位(flag)，决定该节点包含命令的属性以及以什么样的状态执行。
• DSPR（子命令）：两重含义，对于简单命令，该字段为空；对于复合命令，该字段指向子语法树节点。
• DCOM（命令字符）：引用命令字符序列。

        语法树节点生成顺序根据 token 列表中每个元素的优先级(priority)而定，首先遍历整个列表，找到优先级最高的 token 作为根节点，再分别生成左右子树，这是一种最简单的自顶向下(top-down)解决方案。各个 token 优先级视 DTYP 字段而定

        执行命令(Executor)

        当前面一系列步骤之后，如果错误计数为0，则解释器从语法树的根节点开始，深度优先遍历所有节点，并根据前面语法和语义分析得到的类型和属性，一一执行所包含的命令，以生成最后的系统调用。

        对于命令序列(TLST)节点，从左至右顺序执行子树节点命令。

        对于过滤器(TFIL)节点，创建管道文件句柄，作为左右子树的重定向文件。

        对于简单命令(TCOM)和复合命令(TPAR)节点，首先筛选出系统内置命令(built-in)，对于剩下的外部命令则 fork 一个子进程执行它。如果是复合命令中最后一个子命令，那么仍在原来的进程上执行而不必创建新进程。可执行文件路径按先后顺序搜索：①本地路径；②/bin；③/usr/bin。

        多进程环境下，特别要注意文件句柄管理。命令间共享标准输入输出设备之外，还会重定向到管道线，而父进程在 fork 之后子进程会获取一份文件句柄拷贝，所以父进程必须在 fork 之后立即关闭闲置的管道线句柄（如果有的话）以免造成资源泄漏，子进程也将在重定向之后关闭管道线句柄。

        对于后台命令需要打印 pid，但不需要响应中断信号，父进程也不必等待子进程终止。其余进程命令执行中可捕获中断信号，并转入相应的处理函数。

        解释器用内置的 errno 全局变量保存进程终止状态，并生成终止报告(termination report)，系统调用 wait ()用于返回终止进程的 pid 并输出报告消息索引。

        孰优孰劣

        尽管 Thompson Shell 是一款优秀的命令解释器，还产生了多项历史创举，但遗憾的是依然得不到命运女神的垂青，这要归咎于其自身的缺陷——功能单一、命令分散、控制流过于简单，尚无法用来编写脚本(script)。随着 Unix 日益壮大，它已经无法应付趋于繁杂的编程项目了。那时还出现了一个叫 John Mashey 的人写的 PWB Shell（又 叫做 Mashey Shell），基于 Thompson Shell 做了些改进，扩展了命令集，增加了 shell 变量，还增加了 if-then-else-endif，for，while 等控制逻辑。不幸的是它比 Thompson Shell 更短命，因为 1977 年它遇上了一个强劲的对手。

        没错，那就是 Bourne Shell，它的主要优点是真正实现了结构化脚本编程，比之前的 shell 实现得都要好，更要命的是它与前两个 shell 都不兼容，于是一场标准化的论战开始了。在 David G. Korn（ksh 作者）写的“ksh – An Extensible High Level Language”一 文中提及，Steve Bourne 和 John Mashey 在三次连续的 Unix 用户组集会上争论他们各自的理由。在这些集会之间，各自增进他们的 shell 来拥有对方的功能。还设立了一个委员会来选择标准 shell，最终还是选择了 Bourne shell 作为标准。

        于是从 Unix V7 开始就有了前面所说的”Bourne Shell Family”。然而历史上没有完美的技术，随着八、九十年代操作系统迅猛发展，针对 Bourne Shell 的诟病也越来越多了。在解释器本身实现上，我看到网上一个对其评价是“universally considered to be one of the most horrible C code ever written”，至于原因去看一下 mac.h 就知道了，包括基本运算符、关键字在内的大量宏定义使得整个代码看上去简直不是C写的，也许 Bourne 是想把解释器打造成自己独特的风格吧，也难怪后来的 bash 以“born again”命名就是对其祖先的戏谑性调侃。另外内存管理上的一些毛病带来平台可移植性问题，至于其中的技术细节有点高级，超出本文范畴。

        Thompson Again Shell?

        虽然历史没有给 Thompson Shell 一个机会，但它并非就此同 Unix V6 那样一同沦为开源博物馆上的古老“化石”。作为出自顶级黑客之手的作品，作为伴随 Unix 那样伟大操作系统一同曾经流行计算机的产物，至今仍受国内外程序员的缅怀，或将其改写，或为其作注。比如国外一个站点 v6shell.org 上就实现了一个免费开源的可移植性 shell，它兼容并扩充原来的 Thompson Shell 并且可用来做脚本编程。再比如中国程序员寒蝉退士在其个人博客上发布了一个注解版，并对原版做了一些改写，主要是将K&R C转为ANSI C，并且符合POSIX 规范，使原本晦涩难懂的源码变得清晰易读起来。正是因为接触到他的版本激起了我对老 Unix 的考古兴趣，才有了这篇“考古笔记”。我在想不知今后会不会像 bash 那样，出一个 tash 来呢？

        一些感想

        本来全文应该就此结束了，但此时此刻不禁想多说几句。这篇笔记当初并非有意而为之，在 hacking 源码的过程中感想积累多了也就逐渐成章了。看代码、作注解、查资料、写此文，前后历经四个多礼拜，是在繁杂的工作中“挤乳沟”挤出来的零散时间片拼凑起来 的，虽然文字不长但也算耗费了一番心血，酸甜苦辣心中自明，体会到踏上社会之后潜下心做研究之艰难。如今面对这样一份不到 900 行写成的，没有一行多余的代码，简洁(clarity)、干净(clean)、快速(fast)，这就是 Pure C 的魅力，我深为这种厚重的编程功力所折服，正所谓“大道至简”吧。虽然要完全弄懂它需要很多时间，但我相信这种代价却是值得的。

        最后再八卦一下，2011 年 Dennis Ritchie 去世了，有人生前问过他“学C需要多久才能成为熟练开发者并写出重要产品代码？”，Ritchie 回答“我不知道，我从没去学过C。”(I don’t know. I never had to learn C.)其实这里已经给出了答案——那就是没有比去阅读 Unix 源代码更好的选择了，某种意义上C语言就是为 Unix 而生的。

        参考资料

        The Unix Heritage Society：Unix 社区遗产，上面有 v6 和 v7 以及其它一些衍生版本的操作系统源代码。

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

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

        寒蝉退士的博客：Thompson Shell 的一个注解版。

        Evolution of shells in Linux：简述 Linux Shell 演变史。

        附录一个中文注释的 shell 源码