2011年3月28日 星期一

ibus-chewing 單純注音模式 - OSDC.tw 2011 Lightening Talk

Standard
為了注音輸入法,您是否長久以來也仍在使用 SCIM?每次裝好 Linux 的第一件事就是刪除系統預設輸入法,我們彷彿是外星人一般,一點都沒享有人權。感謝 OSDC.tw 2011(活動期間 3/26 ~ 3/27) 提供好吃的食物和舒適的場地,在活動這兩天筆者花了一點功夫做 patch,修掉了 ibus-chewing 單純注音模式的一些 Bugs,現在基本上 ibus-chewing 單純注音模式已經可用,我們可以丟掉 SCIM + 爛注音 Table 了!

以下是 Lightening Talk 的簡報檔:


後記
由於簡報格式的關係,暫時無法轉成 PDF 輸入,所以目前使用錄影的方式公開,待轉檔程式開發完成再來釋出 PDF 檔。

2011年3月18日 星期五

Linux Kernel Sendfile() 的提升 Server 效能之路

Standard
Apache 和 Samba 這類伺服器,主要以傳送檔案資料的工作為主,他們最常做的工作不外乎是開啟檔案(Open)、讀取(Read)、寫入網路連線(Write to Socket)。但是以 Kernel 的角度來說,這樣一個讀取檔案資料和傳送出去的流程相當繁複,並擁有最少兩次的 Kernel/User Space 資料搬移, 導致同一筆資料需要經過兩次多餘的複製。舉例來說,若一個檔案有 1MB,則 Linux Kernel 需要多做 2MB 的記憶體複製,使得效能經常消耗在這種地方,尤以 CPU 不夠快的平台上狀況特別明顯。

而過去曾有 khttpd 這樣的實作,讓 Linux Kernel 自成一個小型的 Web Server,提供一個極有效率方式的讀取靜態網站頁面和 Server 服務,其加速的方法,便是於 Kernel Space 讀取檔案並直接從網路連線送出資料,目的也在於減少 Kernel/User space 之間不必要的 context switch。

想瞭解 User Space 和 Kernel 的資料搬移狀況,我們可以來研究應用程式在讀取和傳送網路資料的流程,經簡化後大致上是(以下簡稱 User Space 為 US,Kernel Space 為 KS):
  1. [US] open()
  2. [KS] do_sys_open()
  3. [KS] do_filp_open() - 找到檔案,並從所在的檔案系統取得 struct file
  4. [KS] Return File Object
  5. [US] malloc() - 準備一塊記憶體當 buffer
  6. [US] read(file, buffer)
  7. [KS] vfs_read(file) - 標準 VFS 的檔案讀取 API
  8. [KS] file->f_op->read() - 使用資料所在的檔案系統(filesystem),其提供的低階 read 操作
  9. [KS] copy_to_user(buffer) - 將檔案資料從硬碟讀出來後,複製一份到 user space 的 buffer

接著是將讀到的資料透過網路傳送出去:
  1. [US] write(Socket, buffer) - 將 buffer 內資料傳送出去
  2. [KS] copy_from_user(buffer) - 將 user space 的 buffer 複製回 kernel space
  3. [kS] Send data - 送出資資料

通常,我們不可能學 khttpd,將 Server 都寫進 Kernel,但如果只是單純讀取並將資料透過網路傳送出去,Kernel 提供了 sendfile() system call,這是一種可行的手段以減少資料搬移,除 Linux 之外,其他作業系統也都有提供此 API。我們只要指定 socket file description 和將要送出去的檔案給 sendfile(),它便會幫我們在 Kernel Space 將檔案從硬碟讀取複製出來,不再經過任何多餘 Kernel/User Space copy,直接從 Socket 送出。

sendfile() 在 Linux Kernel 內的運作流程大致上為:
  1. sendfile()
  2. do_sendfile()
  3. do_splice_direct()
  4. file->f_open->file_splice_read()


有撰寫過 Filesystem Driver 應該都知道,file_splice_read() 是為了提供管線(Pipe)而存在的機制,使資料可以在管線中傳送(這部份因超過本文範疇,在此暫不多做討論)。而 sendfile() 的實作便利用了 pipe 機制,使檔案的資料能流入 Socket 的檔案中,不用做多餘的複製。

後記

這次為了某個案子,寫了一支 Filesystem Driver,而該 Filesystem 會被 Samba 存取。實際測試過程中,發現相較於其他常見的 Filesystem(如:FAT),我們的 Filesystem 讀取速度慢了約 27% 左右,後來才發現是 Samba 採用 sendfile(),但我們的 filesystem並未實作 file_splice_read() ,所以都使用一般的方式讀取檔案。補上相關實作後,速度就提升到與其他 filesystem 一樣了。

2011年3月5日 星期六

在 Linux Kernel 中取得目錄中的檔案清單

Standard
寫一支程式在 User Space 下列出目錄中的檔案清單相當容易,我們可以用 readdir() 去一項項取得檔案內容,事實上, readdir() 是由 Linux Kernel VFS(Virtual Filesystem) 所提供的 API,真正的實作在檔案系統的核心模組(Kernel Module)中。然而因為 Kernel readdir() 的相關實作牽涉到 Kernel/User space 的資料交換問題,所以如果我們是在撰寫 Kernel 的驅動程式,當然就不能使用這系列的 APIs。不過也因為所有的資訊都存在於 Kernel 的資料結構中,我們可以直接從記憶體中的 Linked list 中快速取得檔案清單。

在取得某個目錄下所有檔案資訊前,要先得到該目錄的敘述 struct dentry,VFS 用 struct dentry 的串聯組合來描述整個檔案系統的目錄結構,檔案清單則被保存在 dentry 中的 Double Linked List,因此其實只要知道如何使用 Kernel 提供的 Double Linked list,就能得到該目錄下所有的檔案資訊。而這邊要注意的是 Kernel 提供的一個通用 Linked list 結構(struct list_head),用來統一整個核心的 Linked list 操作機制,這檔案清單的 Double Linked List 就是使用這通用的結構。

這裡是 Linux Kernel 2.6.37 中 dentry 的資料結構(定義在 linux/dcache.h,其中較不重要的部份以『...』做省略,此外,某些定義與較早版本的 Kernel 有所差異,將在文章最後補上說明):
struct dentry {
...省略
    struct hlist_node d_hash;   /* lookup hash list */
    struct dentry *d_parent;    /* parent directory */
    struct qstr d_name;

    struct list_head d_lru;     /* LRU list */
    /*
     * d_child and d_rcu can share memory
     */
    union {
        struct list_head d_child;   /* child of parent list */
        struct rcu_head d_rcu;
    } d_u;
    struct list_head d_subdirs; /* our children */
    struct list_head d_alias;   /* inode alias list */
...省略
};

由 struct dentry 可以發現,利用讀取 d_u.d_child 這個 Linked List 就可以取得底下所有的檔案資訊。實際做法可以參考範例程式碼,此程式會列出某個目錄下所有的檔案名稱:
struct list_head *next;
    struct dentry *child_dentry;
    list_for_each(next, &file->f_path.dentry->d_u.d_child) {
        child_dentry = (struct dentry *)list_entry(next, struct dentry, d_u.d_child);
        printk("%s\n", child_dentry->d_name.name);
    }

於 dentry 裡保存檔案名稱的資料結構是 struct qst,其定義如下(定義與較早版本的 Kernel 有所差異,將在文章最後補上說明):
struct qstr {
    unsigned int hash;
    unsigned int len;
    const unsigned char *name;
};

後記

更多操作 struct list_head 請參考相關的書籍或網路文件,這部份很重要,因為在 Kernel 處處都會發現 struct list_head 的蹤影。

在較早的 Linux Kernel 版本中 dentry 的 d_child 並未使用 union d_u,是這樣被定義的(網路上找到的版本也多半是這樣):
struct dentry {
...省略
  struct dentry * d_parent;
  struct list_head d_hash;
  struct list_head d_lru;
  struct list_head d_child;
  struct list_head d_subdirs;
...省略
}

而早期的 struct qstr 是這樣定義:
struct qstr {
 const unsigned char * name;
 unsigned int len;
 unsigned int hash;
 char name_str[0];
};

由於 Kernel 版本數量太多,且定義會不斷被改變,若在實際撰寫時請參考 Linux 核心程式原始碼的『 include/linux/dcache.h』。