null
分类：
2006-01-24 15:03:33
Geoff Collyer
Department of Statistics
University of Toronto
Toronto, Ontario, Canada
M5S 1A1
utzoo!utstat!geoff
geoff@utstat.toronto.edu
译者声明：译者对译文不做任何担保，译者对译文不拥有任何权利并且不负担任何责任和义务。
原文：
我们最近完成了对 UNIX 命令解释器或 `shell' [Bourne1978a]的被拖延了的手术，使它用标准的 UNIX 内存分配器(malloc(3)和有关函数)用做内部内存管理而不再使用原来的方案(捕获它自己的内存故障，使用sbrk(2)系统调用来增长它的内存分配并重启故障指令)。我们还修正了一些缺陷、lint(1)的抱怨和不如意的性能。本文描述研习 shell 的内部工作的经验教训。很多这种信息都是口头传播的或者完全不被普遍知晓的，而且需要以坚决的努力去学习，但它们是正确理解和维护 shell 的根本。
UNIX 是 Bell 实验室的商标。
shell 的非常梗概描述是它把输入分析到一个分析树中，接着遍历这个树，通过建立管道，做 fork()，重定向 I/O 描述符，exec() 命令等等来执行树节点。与之混杂的是宏展开；引以为荣的引用；(通过信号)捕获键盘、闹钟和其他中断；和维持变量和函数。你可以认为 shell 是还能解释命令的宏处理器。
最初的第七版 shell 运行在很小的地址空间中(64k 字节的指令和 64k 字节的数据包括堆栈段)，但是对字符串或输入行的长度不加以专断的限制(这解释了代码中某些扭曲(contortion))。除了 eval 和引用是例外，它们未被完整规定，shell 的外在规定是简单的、合理的和清晰的。本文不做评论来毁誉这些成就。
shell 源代码在某种程度上是不透明的和注释不足的，这导致维护者只尝试做最小化的变更和修正。在最初的 UNIX 移植期间，shell 是移植到 Interdata 上的最后一个程序，[Johnson1978a] 因为得到正确的重启动故障指令细节的困难，这是第七版(也叫做 ``V7'')发布磁带包含 /bin/osh 第六版 shell 的原因。[Ritchie1987a] 关于最初的 shell 源代码的一个陈腐的抱怨是，它是用模仿 Algol 68 的 C 语言方言写成的，一旦习惯了这就不是问题了，特别是你有一些 Algol 68 知识的话。无论如何，新近的 System V shell 是用正常的 C 写成的。但是，这是最小的问题。
在尝试制作运行在 SunOS 3.x 下的 Sun-3 的第九版 shell(演化自 System V Release 2 shell)的时候，我们遭遇了 shell 奇特的内部内存管理的困扰。shell 经常以一种壮观和闹心的方式失败: 它增长堆栈段到最大的大小并接着转储(dump)核心。我们在转换 shell 去使用 malloc(3) 和相关函数的过程中发现了 shell 的很多没有正式说明的特征。由于缺乏更好的名字，在本文中这项工作被称为``新 shell''。 本文只讨论在使 shell 在 Sun-3 上正确工作的经过中见到那些部分；shell 的其余部分是相对直接了当的。
本文的余下部分由六节组成: 第 2 节描述旧 shell 的设计，第 3 节是在旧 shell 实现中的问题，第 4 节是我们在新 shell 中做的修正，第 5 节是我们的方法，第 6 节是我们的结论，第 7 节是致谢。只感兴趣旧 shell 内情的读者可以安全的跳过第 4 和 5 节。
大多数 shell 维护者遇到的第一个难以捉摸的问题是 shell 的内部内存管理，它被刻画为`极其幽雅，但一碰就塌'。shell 包含了它自己的内存分配器，它是第七版 malloc() 的变体，它维持两种不同的种类的存储: 堆存储，它有着无限的生存时间，是类似于普通的 malloc() 分配的内存；和``stak (栈)'' 存储(如此拼写是为了区别于 shell 的堆栈段)，它是按严格的后进先出次序分配和释放的。堆和 stak 存储块在数据段中是混杂着的。
shell 的基本抽象是一个 stak 存储的栈，其中在栈顶的单元(item)典型的是一个增长中的字符串。顶部单元可能随内存分配器方便而被转移，所以它只应当(在理论上而在实际上不总是)被 stak.h 内的函数和宏所引用；保存到顶部单元内部的私有指针是被禁止的。一旦顶部单元增长到它的最大长度，就把它变成持久的和不可移动的，并开始一个新的空顶部单元。
到 stak 存储操作器的接口 stak.h, 声明了一些例程和宏，特别是 pushstak(byte)，它添加 byte 到顶部单元并前进顶部越过它，它按需要从 UNIX 获得更多的内存。relstak() 生成顶部 stak 单元的顶部的整数偏移量，就是说，顶部单元的大小。absstak(offset) 生成到顶部单元的第 offset 字节的一个临时指针；这个指针一定不能保留。setstak(offset) 设置顶部单元的顶部为第 offset 字节。zerostak() 在顶部单元的顶部存储一个零但不移动顶部。curstak() 生成到顶部单元的顶部的一个临时指针；这个指针一定不能保留。usestak() 调用 locstak() 并忽略结果。fixstak() 用到顶部单元的顶部的指针调用 endstak()。
locstak() 返回到新顶部 stak 单元的底部的一个临时指针，它对于在 shell 中使用的所有结构都是足够大的(特别是 struct fileblk 或来自 io.c 的 2*CPYSIZ)；直到调用了 pushstak()、endstak() 或 fixstak() 之后才可以使用这个指针。endstak(argp) 在 argp 上用零字节终结顶部单元，使顶部单元持久，开始一个新的顶部单元，并返回这个被终结和现在持久的单元的地址。getstak(n) 通过增长当前顶部单元返回大小为 n 字节的一个持久单元。savstak() 断言(assert)顶部单元为空并返回顶部单元的底部的地址。tdystak(ptr) 删除由在 stak 上地址 ptr 处的结构所描述的临时文件(比如来自立即文档)，并弹出 stak 下至但不包括 ptr。stakchk() 在有可能时缩减数据断点。cpystak(string) 复制 string 到一个新的持久单元并返回它的地址。
内存分配器和旧 shell 的其他部分假定新分配的 stak 存储的地址大于所有其他仍然活跃的 stak 存储的地址。(这对于从任意的 malloc() 获得来的存储而言不是真的)。这个属性被一些窍门所利用，比如纪录一个单独的``水印''指针，用来在 stak 存储交织成的各个栈之内标记隔点，在其上面的数据可以被最终丢弃，此后通过弹出每个栈直到它的栈指针到达这个水印指针，或下降到它下面，来从栈中弹出顶部元素。
堆存储由 alloc() 分配(在旧 shell 中也被认作 malloc())。shell 在根本上假定 free() 将忽略尝试释放地址零(``null 指针'')，在 shell 的堆栈段中地址(自动变量，命令行参数，和环境变量)，和仍未制成持久和不可移动的 stak 存储的地址；这意味着 shell 的 free() 只释放堆存储和持久 stak 存储。
旧 shell 捕获它自己的内存故障(通过 SIGSEGV 信号，典型的由超越数据断点的堆分配，或超越数据断点的当前 stak 单元的增长所导致)，用 sbrk(2) 增长数据段 brkincr 个字节，并返回控制权，接着恢复故障指令。
shell 除了系统调用之外不使用 C 库，可能是因为在写 shell 的时候 C 库还没有开发好，可能是使 shell 自我包含，也可能避免在 shell、shell 的 malloc() 和 C 库、 C 库的 malloc(3) 之间危险的交互。效果是使 shell 比依靠 C 库更加脆弱和缺少可移植性。例如， shell 的内存分配器不能与 C 库共存，所以调用 directory(3) 目录读取例程是不安全的，它调用了malloc(3)。
在 blok.c 中的堆分配器(一个修改的 V7 malloc(3))，和在 stak.c 中的 stak 分配器在一起形成了 shell 的内存分配器。它们相互之间在内情上是不分彼此的，部分因为堆分配器在分配堆存储的时候必须移走在 stak 上的顶部单元，用来保持 stak 存储的顶部单元在数据段的顶部。
alloc() 在堆区域增长的时候，移走顶部 stak 单元到堆区域的新顶部的上面，链接在一起，并提升其他 stak 单元成为可释放的持久存储。blok.c 通过把要分配的字节数目与 brkincr-1 的反码做与运算来舍入它；这只在 brkincr 是 2 的幂的时候能正确工作，然而 stak.c 加 256 到 brkincr，就会开始于 512! 所以舍入的值就太大了，幸运的是这只损害性能。stak.c 可能应该双倍 brkincr。
shell 的分配器不能和某些 malloc() 实现共存，因为它假定只有它才分配存储，而某些 malloc() 也是这样。[Korn1985a] 进一步的，shell 包含 malloc() 和 free() 定义，但没有 realloc() 定义，所以使用 C 库的 realloc() 将被拖入 C 库的 realloc() 中, 它将引用错误的 malloc() 和 free()。 更加微妙的是，因为旧 shell 在它的数据断点2上面分配存储, 即使是一个宽容的 malloc(3)，尝试与通过 brk(2) 或 sbrk(2) 做自己的存储分配的程序协同操作，也会被误导并可能在它的数据断点上面踩踏旧 shell 的存储。可能部分因为这个问题，旧 shell 忍痛避免使用 C 库，除了系统调用之外，被迫重新发明其中的部分内容，特别是字符串函数。新 shell 放松了这个限制所以能自由的使用 C 库。
故障指令可以通过从适当的信号处理器返回而被重启的假定不是在所有机器上都成立的。特别是，Sun-2、Sun-3 [Shannon1988a] 和 Cray-1 内核-和-硬件的组合是不能正确的重启动故障指令的，这可能导致无法初始化内存，并因此使用地址零。进一步的，在 Sun-3 和其他不允许引用地址零的其他机器上，旧 shell 天真的假定增长堆会修复内存故障对到地址零的引用不成立，所以在每次内存故障时增长堆的策略只是无限的增长了堆，经常是直到对换或页空间被耗尽，此时旧 shell 的内存分配器缓慢的发出一个断言并转储核心。
不幸的是 stak.h 中的宏，特别是 pushstak(), 并没有在所有应当使用它的地方使用，而是在那些地方内嵌的书写了等价的代码，还有一些其他内部编程习惯是违规的。Cray Research 找到并修正了多数讨厌的 pushstak() 误用，这些休正现在都结合到第九版 shell 中了。我们找到并休正了余下的。
数据断点或断点是没有分配给 UNIX 进程的数据段最低编号字节的地址。在断点和堆栈段的底部之间是可访问的内存，但是接触它是讨厌的行为并会导致内存故障(``段违规'')。
立即文档从脚本向命令提供标准输入的一种方式，它用 `<<'来指示。
立即文档好象是在最后一刻才被增加到最初的第七版 shell 中的。代码是局部化的，但没有考虑错误检查和性能。立即文档是通过在分析期间从 shell 的输入把输入行复制到临时文件，直到见到只包含分界符的一行；此后在执行命令期间，如果分界符没有被引用，在处理宏(比如展开 $DMD)的时候把第一个临时文件复制到第二个临时文件。如果第二个临时文件建立了，它被作为命令的标准输入打开并被删除(unlink)，所以它不是必须以后删除的；否则把第一个临时文件将被作为命令的标准输入打开。在任何情况下，第一个临时文件都是必须被以后删除的，但是如果 shell 首先被杀死，或者包含带有立即文档的命令的批(block)被通过 exec 内置命令终止，它用命令替换了 shell，那么 shell 就没有机会了。
对第一个临时文件的 write() 系统调用是不经检查的，所以在持有 /tmp 的文件系统满了的时候建立立即文档会导致奇怪的行为，并且不能从旧 shell 中得到诊断信息。(write() 到第二个临时文件使用了更一般的机制，在 macro.c 中的 flush()，在新 shell 中仍然未被检查。 Oops!) 还有，在旧 shell 中，当复制输入到第一个临时文件的时候，行被收集直到提供了至少 CPYSIZ(512) 个字节，接着作为一整行写到磁盘上，所以一次写 CPYSIZ+ε 个字节，这导致 write() 与文件系统的块边界不对齐，并促使立即文档的缓慢和 shell ``包裹(bundle)''或``归档''的分拆的缓慢 [Kernighan1984a]。
第七版 shell 使用 read() 系统调用一次读取 16 字节并假定为第七版的目录格局，来读取目录并展开通配符(``生成文件名'')。第九版 (和推测中的 System V Release 2) shell 使用某种来自 C 库的 directory(3) 例程，但是使用其他函数的私有版本。这样做之后内存分配器就在 shell 私有的 opendir() 和 closedir() 的控制下。不幸的是，这要求 shell 知道在 directory(3) 例程中的缓冲区分配细节，而这些细节例如在 4BSD 和 SunOS 3.0 之间是不同的。(我们相信 4BSD 使用静态缓冲区而 SunOS 3.0 动态的分配缓冲区)。
当旧 shell 执行重定向的内置命令比如 set 的时候，它使用 dup2(2) 制作重复的描述符，把被重定向的描述符保存到一个固定的描述符 USERIO 上，它典型的是 10 并且超出 shell 的用户可访问的文件描述符范围(0-9)。不幸的是，旧 shell 没有准备处理内置命令的多个重定向符，所以 set /dev/null 导致 set 执行并接着导致旧 shell 读取 /etc/passwd (!)。
当我们对不管内置与否的任何命令提供 <'' 和 >'' 在旧 shell 中都没有效果。这好象是在 $* 和 $@ 之前的日子的遗迹。3
这个没有正式说明的错误特征是被一个天真的用户偶然发现的，他惊奇的发现在 shell 脚本中的 <$1 `不干正事'了，不论脚本调用时没有参数或有一个参数，他提出了这个问题。
遍历 $PATH 查找命令的代码比转换文件名字到 i 编号所需要的执行了更多的系统调用；在找到一个命令的时候，它会 access(2) 这个文件，接着 stat(2) 它。
在很多(在意图上所有的) UNIX 系统上，不使用标准 I/O 库(stdio)[Kernighan1979a]的程序将不会导致 stdio 的任何部分与它一起加载。这在 SunOS 3.0 上不是真的，比如，不使用的 stdio 的程序仍与有些 stdio 一起加载，因为 exit() 调用 fflush()，这依次导致某个 malloc() 被加载。Sun 的 malloc() 包含 8,192 字节的包含它初始空闲块头部的 BSS(未初始化数据段)。这好像太过分了，假定程序经常使用 malloc() 来保存记忆。
我们对内存分配器的最初修正，为了使它与 C 库共存并工作起来，删除 blok.c 来调用 malloc(3)，并从头重写 stak.c 去使用 malloc(3)。许久之后我们发现了一个可作为替代的，更少清晰性和健壮性的修正，那就是删除私有 directory(3) 函数，使 chkid() 拒绝零地址，并在 blok.c 中提供一个私有的 realloc()，它使用私有的 malloc() 和 free() 实现 realloc(3) 的语义，尽管在某些系统上你还必须增加 BRKINCR 和 BRKMAX 的值到至少页面的大小。很明显它是通过导致每次内存故障都增加数据段到足够大，含盖在 shell 内部正常的最大的内存分配需求而工作的。新 shell 不使用这种修正。
新 shell 在需要的地方使用 pushstak() 和其他接口宏和函数，并安排 pushstak() 按需要增长 stak 存储的顶部单元。性能影响没有测量，但是好象不严重；无论如何，这种检查是必须的。stak.c 已经被完全从头重写了(参见附录)。
我们现在通过对每个新 stak 单元在分配它的时候附加上到前面 stak 单元的一个指针，模拟到各个 stak 存储交织成的栈的单独指针，并为每个栈保留一个水印指针。
我们在 free(3) 顶上加了一层函数(shfree())，使用 #define free shfree 编译新 shell 而不需要旧 shell 的 #define alloc malloc，alloc 是堆分配器被调用的名字。shfree() 拒绝尝试释放地址零，和在堆栈段中或 stak 存储的地址；它使用 free(3) 直接释放 stak 存储。要区分堆存储和 stak 存储，新 shell 的分配把包含魔数的一个整数，对于堆和 stak 存储是不同的，附加到分配存储的每个单元。这消耗了一点内存，但是在 PDP-11 上的实验体现出这不是个严重的问题。
我们简单的使用 malloc(3) 和相关的函数，因而不需要重启故障指令的复杂机制。这有一个令人愉快的副作用就是使用粗野的指针的有缺陷的 shell 立即就转储核心了，不再增长它的堆栈段直到内核在几分钟之后杀死它(生成一个很多兆的内核转储)。
我们修理了两个立即文档缺陷，有一个缺少了些一般性: 立即文档分界符不能超出 CPYSIZ 字节。现在写 CPYSIZ 个字节到第一个临时文件上(直到读到文件结束)，并把剩余的零碎的行复制回到复制缓冲区的开始处，它是 2*CPYSIZ 字节长。
我们通过删除私有函数并只使用 C 库 directory(3) 函数来读取目录来解决读取目录的杂乱问题。修改 shell 调用新函数 openqdir() 而不直接调用 opendir()；openqdir() 向 opendir() 传递从每个字符剔除 0200 位后的文件名字复件，shell 内部用此位标记被引用的字符(比如，命令参数如 \?* 的第一个字符。)
我们还发现在旧 shell 中实现反字符类(比如 [!a-z])的代码是不正确的并且只是偶尔工作；Henry Spencer 把不正确的代码替换为健壮的可工作的代码。
4.4. I/O 重定向
新 shell 通过把多个标准描述符复制到在正常范围之上空闲的任何一个描述符来保存多个标准描述符。I/O 重定向现在象预期那样工作了: 因为空文件名字特指当前目录，<'' 在某些系统上将打开当前目录，而 >'' 将如希望的那样报告错误消息并失败。
4.5. 名字到 i 编号的转换
在 shell 中使用 access() 是不正确的，因为你希望检查 shell 的有效 id，和不需要的，因为你可以轻易的检查从 stat() 获得的权限位。这会更快的，因为接受文件名字作为参数的每个系统调用，如 access() 或 stat() 都必须把它转换成 UNIX 内部指称文件的(设备编号，i 编号)对。这个转换相对缓慢，因为这典型的需要磁盘访问，即使是在有 namei() 缓存的系统上。依次在每个文件上简单的尝试 exec(2) 并在此后检查 errno 会更快；但这对于 type(也叫做 whatis) 内置命令是不工作的，所以我们不这么做。
4.6. 退出
malloc() 在新 shell 不再是问题，但是不需要的静态 stdio 缓冲区占用了一些数据空间。定义 exit(n) { _exit(n); } 来避免 stdio 显著的能减少了 shell 的大小，因为也减少了 fork(2) 的时间需求而加速了命令执行。
调试 shell 比想象的要更加困难。最初的调试很大程度上依赖猜测的灵感和枯燥的实验，由于检查很多兆的核心转储的困难，无论如何它是不提供有用信息的。
一旦使 shell 停止捕获 SIGSEGV，就可能使用调试器来检查由有缺陷的 shell 生成的核心转储并生成栈跟踪，但是缺乏真正有用的调试器(比如 pi(9.1))，[Cargill1986a] 我们在要点上采用了某种方式来打印需要注意的变量(使用 shell 的 prs() 和 prn() ，而不是 printf(3))并思考获得的输出。另一个有用的技术是在每个有关的数据结构的每个实例建立的时候，在其中插入魔数，接着定期的检查这个数的存在，并在解构这个实例的时候清除这个数。这种简单技术通过尽早检查破损和混乱，在保持 shell 健全上很有帮助。我们还把 shell 与 Sun 提供的一个调试版本的 malloc() (/usr/lib/debug/malloc.o)连接在一起，它检查存储区域的一致性。
如果在旧 shell 中的假定被加以文档的话，调试就会容易多了；我们希望本文能够节约 shell 维护者很多个小时。新 shell 有很好的可移植性，已经可以运行在 V7 下的 DEC PDP-11、SunOS 3.x 下的 Sun-3、SunOS 4.0 下的 Sun-4 和 MIPS M/1000。
我们的新 shell 现在包含描述新发现的对旧 shell 中被隐藏了的很多假定的注释。
不幸的是，这个版本不是普遍可获得的，因为它演化自第九版代码。但是，新版本的 stak.c 不受许可的限制并再版在本文的附录中。
Toronto 大学动物学系的 Henry Spencer 雇用了作者进行了上述工作，评论了本文的草稿，当我们发现 shell 的未被描述的属性的时候，他在他的机器上把各种版本的新 shell 作为 /bin/sh 运行，并在找到和修正缺陷的时候很耐心。系部资助了这项工作。
Cray Research 在旧 shell 中找到了应当使用 pushstak() 的一些地方并修理了它们，并修正了 pushstak() 来使 shell 在 Cray 上运行，并摆出不能重启导致内存故障的指令的某些模型。
Dennis Ritchie 把 Cray 的修正结合到了第九版 shell 中，并鼓励作者继续尝试修正 shell 而不是抛出它和重新实现它。(他当然是正确的，部分因为获得正确详情比如引用和 eval 的微妙性。然而，通过使用在 C 库和其他地方能获得的更多的工具，可能包括 yacc 和 lex，shell 的进一步重新实现将会获益 。) Dennis 还对本文的草稿提出和非常有帮助的评论。
Ian Darwin、Beverly Erlebacher 和 Tom Glinos 校读了本文并贡献了有帮助的建议。
在本文中遗留的所有错误都由作者负责。
Bourne1978a.
S. R. Bourne, ``UNIX Time-Sharing System: The UNIX Shell,'' Bell Sys. Tech. J., vol. 57, no. 6, pp. 1971-1990, 1978.
Cargill1986a.
T. A. Cargill, ``The Feel of Pi,'' Proc. Winter Usenix Conf. 1986, 1986.
Johnson1978a.
S. C. Johnson and D. M. Ritchie, ``UNIX Time-Sharing System: Portability of C Programs and the UNIX System,'' Bell Sys. Tech. J., vol. 57, no. 6, pp. 2021-2048, 1978.
Kernighan1979a.
Brian W. Kernighan and Dennis M. Ritchie, ``UNIX Programming - Second Edition,''UNIX Programmer's Manual, Seventh Edition, January, 1979.
Kernighan1984a.
Brian W. Kernighan and Rob Pike, The UNIX Programming Environment, Prentice-Hall, 1984.
Korn1985a.
David G. Korn and Kiem-Phong Vo, ``In Search of a Better Malloc,'' Proc. Summer Usenix Conf. 1985, pp. 489-506, June 1985.
Ritchie1987a.
Dennis Ritchie, private communication, 1987.
Shannon1988a.
Bill Shannon, private communication, November, 1988.
