引言
在 linux 上最常用的命令之一莫过于 cat 命令，用它来快速查看文件内容再合适不过了。
cat 命令也是 coreutils 包中的一个工具，coreutils 提供了一系列工具来操作文件，cat 是其中最基本的工具，相关的还有 tac, head, tail, nl, less, more。
如果想学习文件操作的相关知识，通过这几个工具的深入学习，完全可以学到想要的知识点。接下来会有一系列的文章来逐个分析上述工具，本文作为本系列的一个开篇，讲述 cat 的原理和源代码中的一些亮点。
本文源代码使用 cat (GNU coreutils) 8.21 版本。
原理
cat 命令的基本功能并不复杂，常用的场景是用 cat 将一个文件的内容输出到屏幕上，比如：
cat /etc/hosts
会在屏幕上得到该文件的内容。
基本原理是从标准输入读入要 cat 的文件列表，然后逐个打开，读入文件内容，再将内容输出到标准输出上。整个功能并不复杂，甚至C语言的初学者都可以实现出一个可用的版本。
基本功能
命令
cat --help
会得到它具体的命令行参数格式，通过不同的参数组合影响 cat 输出的格式，也可以说所有的命令行参数都是针对输出格式的，可能只有20%的情况下会使用这些参数，但针对这些参数的实现缺占据了几乎 80% 的代码量，二八定律在这里有惊人的准确。
这些参数里，常用的或者会影响到实现复杂度的参数有：
- -E 在输出的每行行尾显示$
- -n 在输出的每行开头显示行号
- -b 只对非空白行计算行号
- -s 忽略连续的空行
-
-v 显示不可打印的字符
这里比较复杂的是 -s 参数，因为它涉及到上下文的状态。后面可以看到针对这个参数有大量的代码实现。-v 参数的复杂度略低，它需要实现一个针对非打印字符到可打印字符的关系映射，但这个映射并没有上下文状态，所以还比较简单。
另外为了正确性和运行效率，程序还做了一些考虑，后面逐一会提到。
基本功能实现
如果只是一个最简单的 cat 程序，不考虑任何对输出格式的影响，那么程序实现出来应该是这样的：
- 打开输入文件 infile.
- 从 infile 里读一段数据存在 buffer 里.
- 将 buffer 里的数据写到 STDOUT_FILENO 里
-
重复上述过程直到 infile 的结尾
整个执行模式符合 unix 程序的功能单一的精神，从文件或者 STDIN_FILENO读入数据，向 STDOUT_FILENO 输出数据。
避免输入输出都指向同一个文件
STDIN_FILENO 和 STOUT_FILENO 都是 unix 平台的数据接口，他们通过重定向可以是任何文件。
因此在 cat 程序开头也会查看检查输入和输出文件的 inode 标号，看是否是同一个文件。cat 不允许输入和输出是同一个文件。但是对 STDIN_FILENO 留了例外，所以
cat >&1
竟然是合法的，我并没有想明白这样做的原因。
模拟实现
根据上面的思想，我们模拟实现一段核心代码：
// 课堂教学用的代码，不能用在生产环境。
int too_simple_cat(int infd)
{
char buf[1024 * 128];
size_t buf_size = sizeof(buf);
int n_read = 0;
do {
n_read = read(infd, buf, buf_size);
if (n_read == 0)
return 0;
else if (n_read == -1) {
perror("too_simple_cat() read error");
return -1;
}
else {
if (write(STDOUT_FILENO, buf, n_read) < 0) {
perror("too_simple_cat() write error");
return -1;
}
}
}
while (n_read > 0);
return 0;
} 这样的实现简单易懂，但其实强度不够，并不能用在生产环境中。
IO层面的问题
最大的问题是没有考虑到 read()/write() 有可能被 signal 中断的情况：比如常见的场景是用
ctrl-z
中断程序运行，稍后再执行
fg
恢复。恢复后read()/write() 既有可能还没读写数据，这时返回-1; 也有可能读写了一部分数据，这时返回已经读写的数据长度。所以在实现中面临了两个层次的问题：
- 返回 -1 但并不是出错，需要通过 errno 检查是否被 signal 中断。
- 成功返回，但有可能没有按照请求的大小写完全部数据。
解决之道：
针对上面的IO层面的两个问题，cat 有自己的解决办法：
- 是在 read()/write() 层做了一层safe_rw()的封装，解决了第一个问题：发现调用被 signal 中断的请求后继续重试。
- 在 safe_rw() 层之上又做了一层封装 full_write()/full_read()，发现没有写完数据就继续写，解决了第二个问题。
这其中还使用了一些宏定义的小技巧，减少重复代码。感兴趣的可以参阅 coreutils 的代码。
最后的 cat 代码如下，依然保持了简单直观：
static bool simple_cat (char *buf, size_t bufsize)
{
size_t n_read;
while (true)
{
n_read = safe_read (input_desc, buf, bufsize);
if (n_read == SAFE_READ_ERROR)
{
error (0, errno, "%s", infile);
return false;
}
if (n_read == 0)
return true;
{
size_t n = n_read;
if (full_write (STDOUT_FILENO, buf, n) != n)
error (EXIT_FAILURE, errno, _("write error"));
}
}
} 截至此，最基本的 cat 功能就已经实现了。但加入了输出格式的控制参数后，复杂度会大幅提升。
格式化输出带来的复杂度
cat 支持很多命令行参数来调整输出的格式，按照功能分为4类：
- 字符映射：将一个字符映射到一组字符。
- 添加修饰：比如
-E
$
- 行号：比如
-n
- 空行功能的开关：根据上下文状态调整输出或者计数，比如
-b
-s
要实现上述功能，直觉告诉我们，必须逐个遍历输入缓冲区内的字符了。这里使用变量 ch 存储当前刚从 inbuf 读出还未来得及写入 outbuf 的字符。
字符映射
要实现这个功能，就无法再简单的整页读写数据，中间需要再加一个处理的步骤：
- 按整页读出数据。
- 逐个字符的遍历输入缓冲区(inbuf)，转换字符，写到输出缓冲区(outbuf)中。
- 按整页写数据。
- 循环上述过程直到输入文件末位。
映射的细节需要参考 ASCII 编码，基本思路是根据当前字符 ch 的值，在可打印字符范围内的直接输出，不可打印字符则先根据预定的规则映射到一组可打印字符，在加一个前缀输出：
- [0, 32): ^M (ch + 64)，这一范围是控制字符，映射到 ch+64 的字符，并配上 ^ 前缀输出，比如
\r
\t
\n
- [32, 127): 这个范围的字符是可打印字符，直接输出即可。
- 127: 这个字符的意义是 del，映射成 ^?
- (127, 128 + 32): M-^(ch - 128 + 64)
- [128+32, 128 + 127): M-(ch-128)
- 128 + 127: M-^?
对于
\t
和
\n
则直接输出，由更底层的服务解析它们。
添加修饰
如果指定了 -E 参数，则在每行行尾多输出一个
$
。逻辑上，在每次输出
\n
前，先输出一个
$
，再输出
\n
就可以了，也不复杂。
行号
思路是用一个计数器计算
\n
的输出个数，默认从1开始。每次输出当前行之前，先输出一个行号。怎么确定当下是行首呢？两个条件：
- 文件一开始。
- 上一个输如字符是
\n
有趣的是 cat 并没用采用整数累加每次输出用 sprintf 的方式，而且用了一个定长的字符数组，从个位开始自己实现了一个加法的运算，效率上略优。
#define LINE_COUNTER_BUF_LEN 20
static char line_buf[LINE_COUNTER_BUF_LEN] =
{
' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ',
' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '0',
'\t', '\0'
};
static char *line_num_print = line_buf + LINE_COUNTER_BUF_LEN - 8;
/* Position of the first digit in 'line_buf'. */
static char *line_num_start = line_buf + LINE_COUNTER_BUF_LEN - 3;
/* Position of the last digit in 'line_buf'. */
static char *line_num_end = line_buf + LINE_COUNTER_BUF_LEN - 3;
static void next_line_num (void)
{
char *endp = line_num_end;
do
{
if ((*endp)++ < '9')
return;
*endp-- = '0';
}
while (endp >= line_num_start);
if (line_num_start > line_buf)
*--line_num_start = '1';
else
*line_buf = '>';
if (line_num_start < line_num_print)
line_num_print--;
} 18个数字的长度已经是天文数字了，不用担心溢出。
每次读行号的时候用
bpout = stpcpy (bpout, line_num_print);
把行号直接输出到 outbuf。
有心的同学可以试着自己实现以下这个算法。算法不复杂，但巧妙地实现也不容易，作为一个C语言的笔试题也是可以的。
空行的特殊处理
cat 通过 -s 参数跳过连续的空行：比如输入文件有连续3行的空行，但只输出一个空行。自如忽略的空行也就不计算行号了，行尾的
$
自然也不比输出了。可以看到 -s 参数的加入增加了整个程序的复杂性。
用一个整数表示状态
如果当前处理的字符 ch 是
\n
，如何区分这个字符是在空白行的行首出现的，还是在非空白行的行尾出现的呢？因为不同的位置对应了不同的处理方式。
cat 用了一个 int 型的变量 newlines 来记录状态：
- 刚打开文件时，初值设为0
- 遇到一个行首的 \n 就将 newlines + 1
- 遇到一个行尾的 \n 就将 newlines 置为 -1
当 newlines >= 0 的时候，遇到的
\n
就是在行首，视情况输出；否则当 newlines < 0 的时候，遇到的
\n
就是在行尾，铁定要输出的。
并且，将处理程序分为上下两部分，并使用一个 while 循环不同的执行这两部分：
- 上半部分读入数据，只处理行首的
\n
(即连续空行)
- 下半部分只处理非空行内的字符
额外的一个 \n
\n
cat 是按页从输入文件读入数据存入输入缓冲区 inbuf 的，inbuf 里的数据总有处理完的时候，怎么发现 inbuf 已经空了呢？
cat 的做法是每次读入一段数据到 inbuf 后，在 inbuf 后面再追加一个
\n
！这个
\n
并不是数据，是不能输出的，否则会破坏程序正确性。
那么怎么做呢？毕竟这个
\n
头上并没有写记号。cat 处理的相当巧妙：遇到这个
\n
时，inbuf 必然已经空了。那就和初始读入文件的场景共用一处逻辑。同样的这两种情况都不需要处理 ch：
- 初始读入文件时，因为还没有从 inbuf 中读出当前字符 ch。
- 遇到 inbuf 最后一个
\n
时，直接丢弃就对了，也不用处理 ch。
循环划分为上下两部分
因为能够区分
\n
的状态，所以自然的就可以把程序分为两部分：一部分负责读入数据，处理行首的
\n
；一部分处理行内的字符。
最终的 cat() 函数的代码非常精炼，抽象出来是下面的样子：
while (true) {
// 上半部分由一个 do-while 组成，只处理空行。
do {
将outbuf写磁盘
if (inbuf里没有数据)
从infile读数据到inbuf // 这里将额外添加的`\n`吃掉了
else
处理行尾和空行，处理是否合并空白行的输出
从 inbuf 中读一个字符赋给 ch
}
while (当前字符是\n，即当前行是空行)
打印非空白行的行号
// 下半部分只处理非空行中的字符。
if (显示非打印字符) {
while (true) {
根据字符的 ASCII 吗值，映射打印出的内容，逐个处理行内数据。
遇到 \n 跳出本层 while 循环。
}
}
else {
while (true) {
逐个打印字符
遇到 \n 跳出本层 while 循环。
}
}
} 在文件之间传递 newlines 的值
因为 cat 支持一次性传入多个文件作为输入文件，而命令行参数是对所有这些文件都有效的。每个文件就要调用一次 cat() 函数，newlines 的状态有理由在不同的文件的调用中保持，cat 的解决办法是用了一个全局变量 newlines2 保存每次调用 cat() 函数后的 newlines 的值。下次调用 cat() 函数时再把这个值读回来：
newlines = newlines2;
。
inbuf 和 outbuf 的大小
根据参数不同，会分别调用 simple_cat() 或者 cat()，给它们传的 buf 大小也不一样：
- 如果什么参数都不指定，那么将执行 simple_cat()，这个函数本文前面已经列出来了，它只需要一块缓存交换数据即可。
- 需要按照内存页面对齐，即缓存的地址必须也是一个页面的起始地址，前面不是整页的空间就不用了，是一种用空间换效率的方法：
// 取内存页面大小
size_t page_size = getpagesize ();
// 分配缓存给 simple_cat()
insize = MAX(insize, outsize);
inbuf = xmalloc(insize + pagesize - 1);
simple_cat(ptr_align(inbuf, insize), insize); - 但如果指定了复杂的参数，则缓存大小的计算会略复杂：
-
先决定 inbuf 的大小，才能决定 outbuf 的大小。
inbuf 的大小按照输入文件的 IO Block Size 再 + 1，来存放每次 read 后在数据结尾额外添加的
\n
- outbuf 的大小计算稍微复杂一些：
- 一个inbuf 里的字符，有可能最多向 outbuf 输出4个字符。
- 可能还需要输出行号，行号最长为 LINE_COUNTER_BUF_LEN。
- 又因为每次将 outbuf 写磁盘是按照 IO 页面大小 (outsize) 写入的，也不是写完全部数据，会留下一部分数据，这个数值最大会是 outsize - 1。
- 依然做内存页面对齐。
- 将上面的几个因素结合起来，最后的计算公式就是下面这样：
-
// 分配缓存给 cat()
insize = io_blksize(in_stat);
outsize = io_blksize(out_stat);
inbuf = xmalloc(insize + 1 + page_size - 1); // insize + 1 这里单独 + 1 是为了存 inbuf 结尾那个额外的 `\n`
outbuf = xmalloc(outsize - 1 + insize * 4 + LINE_COUNTER_BUF_LEN + pagesize - 1);
cat(ptr_align(inbuf, page_size), insize,
ptr_align(outbuf, page_size), outsize,
......); 其他
cat 为了性能提升做了很多努力：
- 读取文件时使用最优的 IO Block Size，经测定这个数值在 64k 以上 (详见 ioblksize.h)。
- 使用页面对齐的内存作为缓存，将访问集中在几个页面，减少页面 miss 的机会，能够显著加快程序执行。
- 使用 posix_fadvise() 设定内核使用有利于顺序读取的文件缓存策略。
总结
cat 的基本原理和实现并不复杂，从输入文件读入数据，再写到 STDOUT_FILENO 里。常用的基本功能函数20行代码就可以实现，主要的复杂度是在使用了组合参数后对输出格式的控制上，这部分功能可能并不常用。这里，二八定律得到了非常好的体现。
还有大量的实现细节可以通过阅读代码学习到，本文不一一列举了，有兴趣的同学可自行研究。
![linux-svn卸载与安装[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)