一、概述
Linux radix樹最廣泛的用途是用於內存管理，結構address_space通過radix樹跟蹤綁定到地址映射上的核心頁，該radix樹允許內存管理代碼快速查找標識為dirty或writeback的頁。Linux radix樹的API函數在lib/radix-tree.c中實現。
Linux基數樹（radix tree）是將指針與long整數鍵值相關聯的機制，它存儲有效率，並且可快速查詢，用於指針與整數值的映射（如：IDR機制）、內存管理等。
上圖顯示了一個有3級結點的radix樹，每個數據條目（item）可用3個6位的鍵值（key）進行索引，鍵值從左到右分別代表第1~3層結點位置。沒有孩子的結點在圖中不出現。因此，radix樹為稀疏樹提供了有效的存儲，代替固定尺寸數組提供了鍵值到指針的快速查找。
以index=0x5BFB68為例，化為二進制，每6位為一組：10110(22,第一層編號) 111111(63第二次編號) 101101(45第三層編號) 101000(40第四層編號)
二、基本數據結構
struct radix_tree_root {
unsigned int height;
gfp_t gfp_mask;
struct radix_tree_node *rnode;/*間接指針指向結點而非數據條目，通過設置root->rnode的低位表示是否是間指針*/
};
struct radix_tree_node {
unsigned int height; /* 從葉子向上計算的樹高度 */
unsigned int count; /*非葉子結點含有一個count域，表示出現在該結點的孩子的數量*/
struct rcu_head rcu_head;
void *slots[RADIX_TREE_MAP_SIZE]; //64個指針，每層64個子節點
unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
//2X2數組，每個成員都為32位，
在結點結構radix_tree_node中，tags域是一個二維數組，每個slot用2位標識，這是一個典型的用空間換時間的應用。tags域用於記錄該結點下面的子結點有沒有相應的標志位。
//結點標簽數組=每個slot需要的最大標簽位數*slot數所需的long類型變量數
/*tag[0]64位，2個long類型，每一位代表一個slot，表示其PG_dirty
tag[0]64位，2個long類型，每一位代表一個slot，表示其PG_Writeback
如果當前節點的tags[0]值為1，那麼它的子樹節點就存在PAGE_CACHE_DIRTY節點，否則這個子樹分枝就不存在著這樣的節點，就不必再查找這個子樹了。比如在查找PG_dirty的頁面時，就不需要遍歷整個樹，而可以跳過那些tags[0]為0值的子樹，這樣就提高了查找效率*/
};
Ubuntu 13.10 (Saucy Salamander) 內核已升級至 Linux Kernel 3.10 RC5 http://www.linuxidc.com/Linux/2013-06/86110.htm
Linux Kernel 3.4.62 LTS 現已經提供下載 http://www.linuxidc.com/Linux/2013-09/90368.htm
如何在Ubuntu 13.10上安裝Linux內核 3.12 http://www.linuxidc.com/Linux/2013-11/92930.htm
三、全局定義
#define RADIX_TREE_MAP_SHIFT 6
/*值為6時，表示每個結點有2^6＝64個slot，值為4時，表示有2^4=16個slot*/
#define RADIX_TREE_MAP_SIZE (1UL <<RADIX_TREE_MAP_SHIFT) //1000000,2^6=64
/*表示1個葉子結點可映射的頁數，如：1<<6=64，表示可映射64個slot映射64頁*/
#define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1) //111111
#define RADIX_TREE_TAG_LONGS \
((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) /BITS_PER_LONG) //(64+32-1)/32=2
#define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsignedlong)) //32
#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
RADIX_TREE_MAP_SHIFT)) //(32+6-1)/6=6
#define RADIX_TREE_MAX_TAGS 2
/*定義slot數占用的long類型長度個數，每個slot用位圖1位進行標記，如：64個slot時，值為2*/
static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1]
// 全局數組，在32位機器上，這個數組大小是7，表示每一層的最大有多少個slot
height=0:maxindex=0， 第一層只有一個radix_tree_node
height=1:maxindex=2^6-1, 第二層最多63個
height=2:maxindex=2^12-1,
height=3:maxindex=2^18-1,
height=4:maxindex=2^24-1, 若每個slot為4k，則表示支持64G
height=5:maxindex=2^30-1,
height=6:maxindex=2^32-1, 16T
四、初始化函數
初始化一個名字是name的樹根。mask是gfp相關的掩碼，在內存管理的時候用到。
#define RADIX_TREE(name, mask)
struct radix_tree_root my_tree;
INIT_RADIX_TREE(my_tree, gfp_mask);
248 void __init radix_tree_init(void)
1249 {
1250 radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
1251 sizeof(struct radix_tree_node), 0, SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
1253 radix_tree_node_ctor);
1254 radix_tree_init_maxindex();//初始化全局數組height_to_maxindex
1255 hotcpu_notifier(radix_tree_callback, 0);
1256 }
五、插入條目
int radix_tree_insert(struct radix_tree_root *root, unsigned long, void *item);
函數radix_tree_insert插入條目item到樹root中，如果插入條目中內存分配錯誤，將返回錯誤-ENOMEM。該函數不能覆蓋寫正存在的條目。如果索引鍵值index已存在於樹中，返回錯誤-EEXIST。插入操作成功返回0。
對於插入條目操作失敗將引起嚴重問題的場合，下面的一對函數可避免插入操作失敗：
int radix_tree_preload(gfp_t gfp_mask);
void radix_tree_preload_end(void);
函數radix_tree_preload嘗試用給定的gfp_mask分配足夠的內存，保證下一個插入操作不會失敗。在調用插入操作函數之前調用此函數，分配的結構將存放在每CPU變量中。函數radix_tree_preload操作成功後，將完畢內核搶占。因此，在插入操作完成之後，用戶應調用函數radix_tree_preload_end打開內核搶占。
六、刪除條目
void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
函數radix_tree_delete刪除與索引鍵值index相關的條目，如果刪除條目在樹中，返回該條目的指針，否則返回NULL。
七、查詢條目
/*在樹中查找指定鍵值的條目，查找成功，返回該條目的指針，否則，返回NULL*/
void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index);
/*返回指向slot的指針，該slot含有指向查找到條目的指針*/
void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index);
/*多鍵值查找，max_items為需要查找的item個數，results表示查詢結果。查詢時鍵值索引從first_index開始*/
radix_tree_gang_lookup(struct radix_tree_root *root, void **results, unsigned long first_index, unsigned int max_items);
八、標簽操作
/*將鍵值index對應的條目設置標簽tag，返回值為設置標簽的條目*/
void *radix_tree_tag_set(struct radix_tree_root *root, unsigned long index, unsigned int tag);
/*從鍵值index對應的條目清除標簽tag，返回值為清除標簽的條目*/
void *radix_tree_tag_clear(struct radix_tree_root *root, unsigned long index, unsigned int tag);
/*檢查鍵值index對應的條目tag是否設置。tag參數為0或者1，表示Dirty位或者WB位
如果鍵值不存在，返回0，如果鍵值存在，但標簽未設置，返回-1；如果鍵值存在，且標簽已設置，返回1*/
int radix_tree_tag_get(struct radix_tree_root *root, unsigned long index, unsigned int tag);
/*從first_index起查詢樹root中標簽值為tag的條目，在results中返回*/
unsigned int radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, unsigned long first_index, unsigned int max_items, unsigned int tag);
/*如果樹root中有任何條目使用tag標簽，返回鍵值*/
int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag);
更多詳情見請繼續閱讀下一頁的精彩內容： http://www.linuxidc.com/Linux/2014-09/107015p2.htm
