cat 指令原理及源代碼分析

引言

在 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 程式，不考慮任何對輸出格式的影響，那麼程式實作出來應該是這樣的：

1. 打開輸入檔案 infile.
2. 從 infile 裡讀一段資料存在 buffer 裡.
3. 将 buffer 裡的資料寫到 STDOUT_FILENO 裡

4. 重複上述過程直到 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. 傳回 -1 但并不是出錯，需要通過 errno 檢查是否被 signal 中斷。
2. 成功傳回，但有可能沒有按照請求的大小寫完全部資料。

解決之道：

針對上面的IO層面的兩個問題，cat 有自己的解決辦法：

1. 是在 read()/write() 層做了一層safe_rw()的封裝，解決了第一個問題：發現調用被 signal 中斷的請求後繼續重試。
2. 在 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類：

1. 字元映射：将一個字元映射到一組字元。
2. 添加修飾：比如

   -E

   在行尾添加

   $

   。
3. 行号：比如

   -n

   參數，在每行行首輸出行号。
4. 空行功能的開關：根據上下文狀态調整輸出或者計數，比如

   -b

   不對空行計算行号，

   -s

   跳過連續的空行。

要實作上述功能，直覺告訴我們，必須逐個周遊輸入緩沖區内的字元了。這裡使用變量 ch 存儲目前剛從 inbuf 讀出還未來得及寫入 outbuf 的字元。

字元映射

要實作這個功能，就無法再簡單的整頁讀寫資料，中間需要再加一個處理的步驟：

1. 按整頁讀出資料。
2. 逐個字元的周遊輸入緩沖區(inbuf)，轉換字元，寫到輸出緩沖區(outbuf)中。
3. 按整頁寫資料。
4. 循環上述過程直到輸入檔案末位。

映射的細節需要參考 ASCII 編碼，基本思路是根據目前字元 ch 的值，在可列印字元範圍内的直接輸出，不可列印字元則先根據預定的規則映射到一組可列印字元，在加一個字首輸出：

• [0, 32): ^M (ch + 64)，這一範圍是控制字元，映射到 ch+64 的字元，并配上 ^ 字首輸出，比如

  \r

  對應的 ASCII 碼是13，顯示出來就是 ^M，M的 ASCII碼是 13 + 64 = 77。隻有

  \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開始。每次輸出目前行之前，先輸出一個行号。怎麼确定當下是行首呢？兩個條件：

1. 檔案一開始。
2. 上一個輸如字元是

   \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

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行代碼就可以實作，主要的複雜度是在使用了組合參數後對輸出格式的控制上，這部分功能可能并不常用。這裡，二八定律得到了非常好的展現。

還有大量的實作細節可以通過閱讀代碼學習到，本文不一一列舉了，有興趣的同學可自行研究。