跳到主要內容

中文試譯:Red-black Trees (rbtree) in Linux

原文作者:Rob Landley
原文連結:http://lxr.linux.no/linux+v3.2.1/Documentation/rbtree.txt

red-black tree是什麼?它們有什麼用?
red-black tree是一種self-balancing binary search tree,用來儲存可被排序的key/value資料組合。與radix trees不同(用來有效地儲存sparse arrays,所以會用長整數的索引來安插/存取/刪除節點),也與hash tables不同(沒有保持在有序的狀態,所以無法輕易地以有序的方式巡訪,並且必須以特定的大小與hash function來微調效能,而rbtresss則可以優雅地擴展並儲存任意的key值)。
(譯註:雖然是很基本的觀念,但小弟還是要囉唆一下。資料結構的選用是因時制宜的。千萬不要以為rbtrees比上述兩種結構好,rbtrees基本上算是對各種操作最四平八穩的結構,但應用時,往往可以挑選更佳的資料結構。舉例來說,如果我們只需要安插/搜尋節點,那麼幾乎沒有什麼資料結構比hash table更合適了,複雜度只要O(1)。)


red-black tree跟AVL trees很像,不過為最糟狀況下的安插與刪除提供了較佳的時間表現(個別最多兩次旋轉與三次旋轉便可讓tree恢復平衡),不過對於搜尋會有一點點的損失(不過還是保持在O(logn))。

引用自Linux Weekly News:

在kernel中有許多red-black trees的應用。deadline與CFQ I/O排程器用rbtrees追蹤請求;ext3檔案系統使用rbtrees紀錄directory entries。Virtual memory areas (VMAs) 也是以rbtrees追蹤、epoll的檔案描述器、密碼學用的key值、以及在"階層式token bucket"的網路封包。

這份文件涵蓋Linux rbtress的使用方式。更多有關red-black tree的原理與實作資訊可參考:

    Linux Weekly News上的文章
    http://lwn.net/Articles/184495/
    維基百科上關於red-black trees的條目
    http://en.wikipedia.org/wiki/Red-black_tree

Linux的red-black trees實作
Linux裡的rbtree實作位於"lib/rbtree.c"。使用之前,請"#include <linux/rbtree.h>"。
Linux的rbtree實作針對效能作了最佳化,並且相較於典型的tree的實作,使用了較少的間接層(為了好的cache locality)。每一個struct rb_node的instance都會被嵌入它要處理的資料結構中,而不是透過pointer去區分rb_node與資料結構。使用者也被要求撰寫它們專屬的搜尋與安插functions,而不是使用一個比較的callback function。上鎖的機制也需由rbtree的使用者完成。

建立一個新的rbtree
在rbtree中的資料節點就是那些包含struct rb_node的結構:
  
   struct mytype {
        struct rb_node node;
        char *keystring;

當處理一個指向struct rn_node的pointer時,這個資料節點可以透過標準的container_of巨集來存取。另外,每一個資料欄位也可以透過rb_entry(node, type, member)來存取。
在每個rbtree的根部,是一個rb_root的結構,可以透過下列方式完成初始化:

  struct rb_root mytree = RB_ROOT;

在rbtree中尋找一個值
為你的tree寫一個搜尋動作是很直覺的:從root開始,比較每一個值,然後依狀況從左分支或右分支往下走。範例:
  struct mytype *my_search(struct rb_root *root, char *string)
  {
        struct rb_node *node = root->rb_node;


        while (node) {
                struct mytype *data = container_of(node, struct mytype, node);
                int result;


                result = strcmp(string, data->keystring);


                if (result < 0)
                        node = node->rb_left;
                else if (result > 0)
                        node = node->rb_right;
                else
                        return data;
        }
        return NULL;
  }


將資料安插進rbtree
將資料安插進tree中需要先為新資料搜尋安插的位置,然後安插該節點,然後再平衡("重新上色")tree。
安插部份的搜尋與前面的搜尋不同,需要找到要嫁接的節點位址的pointer。新的節點也需要一個指向其parent的link來完成平衡。
範例:
  int my_insert(struct rb_root *root, struct mytype *data)
  {
        struct rb_node **new = &(root->rb_node), *parent = NULL;


        /* Figure out where to put new node */
        while (*new) {
                struct mytype *this = container_of(*new, struct mytype, node);
                int result = strcmp(data->keystring, this->keystring);


                parent = *new;
                if (result < 0)
                        new = &((*new)->rb_left);
                else if (result > 0)
                        new = &((*new)->rb_right);
                else
                        return FALSE;
        }


        /* Add new node and rebalance tree. */
        rb_link_node(&data->node, parent, new);
        rb_insert_color(&data->node, root);


        return TRUE;
  }

移除或替換既有的rbtree資料
要從tree移除既有節點,可呼叫:

  void rb_erase(struct rb_node *victim, struct rb_root *tree);

範例:
  struct mytype *data = mysearch(&mytree, "walrus");

  if (data) {
        rb_erase(&data->node, &mytree);
        myfree(data);
  }

要用一個有一樣key值的節點替換既有節點,請呼叫:


  void rb_replace_node(struct rb_node *old, struct rb_node *new,
                        struct rb_root *tree);


以這種方式替換節點無須將tree重新排序:如果新節點沒有與舊節點一樣的key值,該rbtree很有可能會損壞。


巡訪rbtree中的元素(以有序的方式)
有四個functions可以有序的方式迭代一顆rbtree。這可以用在任何的trees,而不需要任何的包裝(除了上鎖以外):

  struct rb_node *rb_first(struct rb_root *tree);
  struct rb_node *rb_last(struct rb_root *tree);
  struct rb_node *rb_next(struct rb_node *node);
  struct rb_node *rb_prev(struct rb_node *node);

要開始迭代,請呼叫rb_first()或rb_last(),並將指向root的pointer傳入,結果會回傳tree中的第一個或最後一個節點的pointer。接下來,透過呼叫rb_next()或rb_prev()以獲取目前節點的下一個或前一個節點。當沒有節點時,有可能會回傳NULL。
這些迭代functions回傳被嵌入資料節點的struct rb_node的poniter,所以需用container_of巨集去獲取資料節點,而資料節點的每個欄位可藉由
範例:

  struct rb_node *node;
  for (node = rb_first(&mytree); node; node = rb_next(node))
        printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring);

對Augmented rbtrees的支援
Augmented rbtree是一種在每個節點有"一些"額外資訊儲存的rbtree。這種資訊可以用來為rbtree增進新功能。Augmented rbtree是建立在基本rbtree上的可選用功能。想要此功能的rbtree使用者必須在安插與移除時呼叫augmentation functions,並提供augmentation callback。
當安插時,使用者必須在節點已經就定位後呼叫rb_augment_insert()。這會使得augmentation callback在新節點與root之間的每個曾受影響的節點都被喚起。
當要移除節點時,使用者必須先呼叫rb_augment_erase_begin()以獲取在重新平衡後的路徑上的最深節點。然後,在移除該節點後,呼叫rb_augment_erase_end(),並傳進先前獲去的最深節點。這會令augmentation function在每一個被影響的節點被喚起,從最深的節點到root為止。
Interval tree是augmented rbtree的一個例子。可參考"Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein。interval trees的更多細節:
典型的rbtree有一單一的key值,無法直接拿來存一個範圍,像是[lo:hi]。所以無法快速地確認任何的lo:hi是否有重疊,也無法確認是否有一個匹配的lo:hi。
然而,rbtree可以被增強,以有校的方式儲存這樣的區間資訊,使得快速的搜尋與匹配動作變得可能。
這個存於每個節點的"額外資訊"是節點的所有後代的最大hi值。這個資訊可以透過該節點以及它的立即後代(譯註:就是只往下一層的後代)來獲得。這可以用來以O(log n)的效率獲得最低匹配(在所有匹配中,有最低的起始位址),像這樣:

find_lowest_match(lo, hi, node)
{
        lowest_match = NULL;
        while (node) {
                if (max_hi(node->left) > lo) {
                        // Lowest overlap if any must be on left side
                        node = node->left;
                } else if (overlap(lo, hi, node)) {
                        lowest_match = node;
                        break;
                } else if (lo > node->lo) {
                        // Lowest overlap if any must be on right side
                        node = node->right;
                } else {
                        break;
                }
        }
        return lowest_match;
}
要找到絕對匹配,可以先找到最低匹配,然後沿著接下來的節點來尋找,直到一個節點的起始位址超出了我們要找的hi值。
(譯註:1. augmented tree的實作可以參考./arch/x86/mm/pat_rbtree.c, 2. rbtree的作者同時也是Linux VM的主要實作者,這邊有他的訪談錄

留言

張貼留言

這個網誌中的熱門文章

誰在呼叫我?不同的backtrace實作說明好文章

今天下班前一個同事問到:如何在Linux kernel的function中主動印出backtrace以方便除錯? 寫過kernel module的人都知道,基本上就是用dump_stack()之類的function就可以作到了。但是dump_stack()的功能是如何作到的呢?概念上其實並不難,慣用手法就是先觀察stack在function call時的變化(一般OS或計組教科書都有很好的說明,如果不想翻書,可以參考 這篇 ),然後將對應的return address一層一層找出來後,再將對應的function名稱印出即可(透過執行檔中的section去讀取函式名稱即可,所以要將KALLSYM選項打開)。在userspace的實作可參考Jserv介紹過的 whocallme 或對岸好手實作過的 backtrace() ,都是針對x86架構的很好說明文章。 不過從前面兩篇文章可以知道,只要知道編譯器的calling convention,就可以實作出backtrace,所以是否GCC有提供現成的機制呢?Yes, that is what __builtin_return_address() for!! 可以參考這篇 文章 。該篇文章還提到了其他可以拿來實作功能更齊全的backtrace的 程式庫 ,在了解了運作原理後,用那些東西還蠻方便的。 OK,那Linux kernel是怎麼做的呢?就是用頭兩篇文章的方式啦~ 每個不同的CPU架構各自手工實作一份dump_stack()。 為啥不用GCC的機制?畢竟...嗯,我猜想,除了backtrace以外,開發者還會想看其他register的值,還有一些有的沒的,所以光是GCC提供的介面是很難印出全部所要的資訊,與其用半套GCC的機制,不如全都自己來~ arm的實作 大致上長這樣,可以看到基本上就只是透過迭代fp, lr, pc來完成: 352 void unwind_backtrace (struct pt_regs * regs , struct task_struct *tsk) 353 { 354 struct stackframe frame ; 355 register unsigned long current_sp asm ( "

淺讀Linux root file system初始化流程

在Unix的世界中,file system佔據一個極重要的抽象化地位。其中,/ 所代表的rootfs更是所有後續新增file system所必須依賴前提條件。以Linux為例,黑客 Jserv 就曾經詳細說明過 initramfs的背後設計考量 。本篇文章不再重複背景知識,主要將追蹤rootfs初始化的流程作點整理,免得自己日後忘記。 :-) file system與特定CPU架構無關,所以我觀察的起點從init/main.c的start_kernel()開始,這是Linux作完基本CPU初始化後首先跳進的C function(我閱讀的版本為 3.12 )。跟root file system有關的流程羅列如下: start_kernel()         -> vfs_caches_init_early()         -> vfs_caches_init()                 -> mnt_init()                         -> init_rootfs()                         -> init_mount_tree()         -> rest_init()                 -> kernel_thread(kernel_init,...) 其中比較重要的是mnt_int()中的init_rootfs()與init_mout_tree()。init_rootfs()實作如下: int __init init_rootfs(void) {         int err = register_filesystem(&rootfs_fs_type);         if (err)                 return err;         if (IS_ENABLED(CONFIG_TMPFS) && !saved_root_name[0] &&                 (!root_fs_names || strstr(root_fs_names, "tmpfs"))) {          

kernel panic之後怎麼辦?

今天同事在處理一個陌生的模組時遇到kernel panic,Linux印出了backtrace,同事大致上可以知道是在哪個function中,但該function的長度頗長,短時間無法定位在哪個位置,在這種情況下,要如何收斂除錯範圍呢?更糟的是,由於加入printk會改變模組行為,所以printk基本上無法拿來檢查參數的值是否正常。 一般這樣的問題會backtrace的資訊來著手。從這個資訊我們可以知道在function中的多少offset發生錯誤,以x86為例(從 LDD3 借來的例子): Unable to handle kernel NULL pointer dereference at virtual address 00000000 printing eip: d083a064 Oops: 0002 [#1] SMP CPU:    0 EIP:    0060:[<d083a064>]    Not tainted EFLAGS: 00010246   (2.6.6) EIP is at faulty_write+0x4/0x10 [faulty] eax: 00000000   ebx: 00000000   ecx: 00000000   edx: 00000000 esi: cf8b2460   edi: cf8b2480   ebp: 00000005   esp: c31c5f74 ds: 007b   es: 007b   ss: 0068 Process bash (pid: 2086, threadinfo=c31c4000 task=cfa0a6c0) Stack: c0150558 cf8b2460 080e9408 00000005 cf8b2480 00000000 cf8b2460 cf8b2460        fffffff7 080e9408 c31c4000 c0150682 cf8b2460 080e9408 00000005 cf8b2480        00000000 00000001 00000005 c0103f8f 00000001 080e9408 00000005 00000005 Call Trace:  [<c0150558>] vfs