Linux內核基數樹應用分析

Linux內核基數樹應用分析——lvyilong316

基數樹(Radix tree)可看做是以二進制位串為關鍵字的trie樹，是一種多叉樹結構，同時又類似多層索引表，每個中間節點包含指向多個節點的指針數組，葉子節點包含指向實際對象的指針(由於對象不具備樹節點結構，因此將其父節點看做葉子節點)。

圖1是一個基數樹樣例，該基數樹的分叉為4(2^2)，樹高為4，樹的每個葉子結點用來快速定位8位文件內偏移，可以定位4x4x4x4=256(葉子節點的個數)頁，如：圖中虛線對應的兩個葉子結點的路徑組成值0x00000010和0x11111010，指向文件內相應偏移所對應的緩存頁。

圖1

在Linux內核中，基數樹用於將對象的句柄id或頁索引index映射轉化為指向對象的指針(具體來說是轉化為一些列有指針組成的路徑)，這是通過把id分段後作為各層節點的指針數組(以下將指針數組的項稱為slot)的索引而達到檢索的目的。分段通常使用將id右移指定位數後和指定長度的位掩碼相與獲得，如(id>>n)&IDR_MASK。比如一個32位的id值，按4位一分段的方法，可以化為8個位串(每個含4位)，從高位到低位分別作為1~8層節點的slot索引，通過上一層節點的slot索引得到指向下一層節點的指針，如此直到最後一層，此時索引指向最終對象。如圖2所示，為id為8位，按4位分一段的方法，可以構成一個2層的基數樹，最下層共有(2^4)*(2^4)=2^8=256個葉子節點，所以功能存放256個對象，並且對象的最大id為256-1=255(id從0開始)。

圖2

從這個角度講，基數樹中對象的檢索要比固定數組稍慢一些，但是其使用了時間換空間的思想．非常適用於節點數動態變化較大的場合，而它的時間復雜度也是可以接受的，達到O(log_2nN)，其中2ⁿ為每個節點的指針槽數，而n對應分段掩碼的位長。

1.基數樹在Linux內核中的應用

1.1 文件緩存頁管理

在較早版本的內核中(比如2.4.0)，文件頁緩存是通過共同的散列表page_hash_table組織的(根據緩存頁對應的index進行hash)，通過散列表是能較快地搜索到指定文件的指定頁，而且沒有太多的額外內存消耗，但是其弊端也是顯見的，因為所有訪問文件都通過同一個散列表緩存頁，而查詢時都通過自旋鎖pagecache_lock，因此就降低了多進程的並發訪問性能，在特定場合下是不可忍受的。因此，在2.6內核中用各文件地址空間自行管理緩存頁．從而使各文件的頁搜尋工作互不影響，提高了並發性能。“Linux2.6內核的文件頁是通過基數樹管理的，而頁索引決定了其在樹中的位置。文件地址空間對象的數據結構如下：

struct address_space{
struct inode *host; /*owner:inode,bIock_device*/
struct radix_tree_root pagetree;
)

其中page_tree即指向基數樹的根，該指針指向radix_tree_root結構。

struct radix_tree_root{
unsigned int height; //樹的高度
gfp_t  gfp_mask;
struct radix _tree_ node *rnode; //指向基數樹的根節點
};

rnode指向基數樹的根節點，根節點是一個radix_tree_node結構。

struct radix_tree_node{
unsigned int heigh; /*Height from the bottom*/
unsigned int count;
struct rcu_head  rcu_head;
void *slots[RADlX_TREE_MAP_SIZE];
unsigned Iong  tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};

height為節點的高度，count指示孩子節點數(也即非空槽位數)，slots為子節點指針數組(對於葉節點，則指向對應的頁結構)，tags數組使用位圖分別指示各子樹是否包含有對應標志的頁。這兩個標志分別是髒和寫回。

#definePAGECACHETAGDIRTY0

#definePAGECACHE1_AGVVRlTEBACK1

1.2 進程問通信ipc對象管理

較早內核(如2.6.11)中的ipc對象(比如共享內存對象shm)是用固定數組管理的(對象id為數組的下標)，這有一個缺陷，就是當對象數量劇增，原有數組對象數不夠時就要通過grow_ary()重新分配新的數組，然後是新舊數組間的內容拷貝，當對象數量變化較大時就要面臨數組的頻繁分配和釋放，這對性能是不利的，因此在2.6.24中ipc對象改用基數樹idr管理，雖然通過idr定位對象不像數組那麼直接(時間復雜度為樹的高度)，但是換取了很好的動態性能，增加對象時不會面臨大規模的內存分配，只需要創建一個或幾個(擴展樹時)樹節點，並且獲取空閒id的性能比數組要好，這直接影響了插入新對象的速度。idr結構用於管理包含ipc對象的基數樹，以對象id為索引：

struct idr{
struct idr_Iayer *top;
struct idr_Iayer *id_free;
int Iayers;
int id_free_ cnt;
spinlock_t  lock;
};

其中idr_layer是樹節點結構，top指向根節點，layers是樹的高度，id_free維護一個臨時的空閒節點鏈表，id_free_cnt指示空閒鏈表中的節點數。

2.代碼分析

2.1 Linux\lib\radix-tree.c

(1)樹高度和最大索引的轉換：

static  __init unsigned long__maxindex(unsigned int height)
{
unsigned int width=height*RADIX_TREE_MAP_SHlFT; // RADIX_TREE_MAP_SHlFT值為6時，表示每個結點有2^6＝64個slot，值為4時，表示有2^4=16個slot
int shift=RADlX_TREE_INDEX_BlTS-width：
if(shift<0)
return ~0UL;
if(shift>=BITS_PER_LONG)
return 0UL;
return~0UL>>shift;
}

先由高度(樹的層數)和每節點的索引位寬(RADIX_TREE_MAP_SHlFT用幾位做索引)得到總索引的位寬width，再由位寬轉化為最大索引(即葉子的個數)，比如32位的索引的最大值是2^32-1，4位雙層樹的最大索引是2^(2*4)-1。(4位數做索引，每個節點可以有2^4=16個分支(slot)，那麼第二層共有2^(2*4)個節點，從第二層最左端開始編號，最大索引為2^(2*4)-1)。通過循環調用這個函數可以得到各種高度的樹的最大索引值存放在一個靜態數組height_to_maxindex中。這是在初始化期間調用radix_tree_init()->radix_tree_init_maxindex()實現的。

(2)對象的插入

參數root指向根節點，index指示頁索引，item：

int radix_tree_insert (struct radix_tree_root *root，unsigned long index，void *item)
{
struct radix_tree_node*node=NULL，*sIot;
unsigned int height,shift;
int offset;
int error;
BUG_0N(radix_tree_is_indirect_ptr(item));
//如果當前索引超出樹的最大索引，必須調用radix_tree_extend()擴充樹的高度直至最大索引可容納參數中的索引值
if (index>radix_tree_maxindex(root->height)){
error=radix_tree_extend(root,index);
if(error)
return error;
)
sIot=radix_tree_indirect_to_ptr(root->rnode);
//取當前樹的高度he-ght，以及頁索引的初始右移位數shift
height=root->height;
shift=(height-1)*RADIX_TREE_MAP_SHIFT;
offset=0; /*uninitiaIised var warning*/
//按照索引循環從height層往下檢索，直到第1層節點為止(中間按需分配子樹結點)
whiIe(height>0){
//遇到sIot為空指針，則需要分配中間節點
if(sIot==NULL){
/*Have to add a chiId node．*/
if(!(slot=radjx_tree_node_alloc(root)))//調用SIab分配器分配新的節點
return –ENOMEM;
slot->height=height;//設置節點高度
//node非空，則新分配節點作為其子節點，否則新分配節點作為根節點
if(node){
//新分配節點指針放入node的指針數組中的offset槽位
rcu_assign_pointer(node->sIots[offset],slot);
node->count++;∥node的孩子節點數增1
}else
rcu_assign_pointer(root->rnode,radix_tree_ptr_to_indirect(sIot));
}
//調整索引，node、sIot向下走(sIot指向node的子節點),調整移位數,高度減1
offset=(index>>shift)&RADIX_TREE_MAP_MASK;// 根據數據項索引，計算當前層數據項應該的槽位，如索引為32位，采用4位做key，則該數據項在最頂層所在槽位即為前四位對應的槽位，第二層（從上到下）所對應的槽位為接下來4位對應的槽位
node=sIot;
sIot=node->sIots[offset];
shift-=RADIX_TREE_MAP_SHIFT;
height--;
)
/*第1層節點node的位索引。使set對應的槽位(數組項)指向item指示的對象，從而完成了對象的插入*/
if(node){
node->count++;
rcu_assign_pointer(node->sIots[offset],item);
…
}

(3)對象的刪除：

void *radi×_tree_deIete(struct radix_tree_root *root,unsignedIong index)
{
/*使用path數組存放搜索路徑沿途的節點指針和索引，數組長度為最大路徑長度(數的最大高度)+1，多出來的一項存放空指針(起哨兵作用)*/
struct radix_tree_path path[RADIX_TREE_MAX_PATH+1],*pathp=path;
struct radix_tree_node *slot=NULL;
struct radix_tree_node *to_free;
unsjgned int height,shift;
int tag;
int offset;
//height初始化為樹的高度
height=root->height：
//檢查待刪除對象的索引是否超出樹的范圍
if(index>radix_tree_maxindex(height))
goto out;
//sIot初始化指向根節點，在以下過程中slot始終指向一個中間節點
sIot=root->rnode;
//對於高度為0的空樹直接返回
if(height==0){
root_tag_clear_all(root);
root->rnode=NULL：
goto out;
}
slot=radix_tree_indirect_to_ptr(sIot);
//shift中保存索引當前需要移位的位數
shift=(height-1)*RADIX_TREE_MAP_SHIFT;
//path數組第0項的node置為空，作為指示哨用
pathp->node=NULL;
//這個循環自根節點向下遍歷id對應的對象，沿途節點和槽位存於pathp指向的數組中
do{
if(sIot==NULL)//途中遇到空指針(指定對象肯定不存在)，直接返回
goto out;
pathp++; //徑數組指針遞增pathp->node存放當前節點的槽索引，pathp->node存放當前節點
offset=(index>>shift)&RADIX_TREE_MAP_MASK;
pathp->offset=offset;
pathp->node=sIot;
//根據索引獲取下一個節點的指針，並調整移位數
sIot=slot->sIots[offset];
shift-=RADIX_TREE_MAP_SHIFT;
height--;
} whiIe(height>0);
if(sIot==NULL)
goto out;
...
to_free=NULL;
/*這個循環借助pathp數組的記錄，從待刪除對象的父節點沿途至根節點的方向進行遍歷，對應的槽位指針置空(底層節點槽位指針置空即從樹中刪除了對象)，子節點數遞減，釋放槽位全空的節點。兩種情況下循環終止：(1)已到達並處理完根節點(2)碰到了子節點數不為0的節點*/
while(pathp->node){
pathp->node->sIots[pathp->offset]=NULL;
pathp->node->count--;
/*Queue the node for deferred freeina after the last reference to it disappears(set NULL,above)*/
if(to_free)
radix_tree_node_free(to_free);
//碰到了子節點數不為0的節點，如果是根節點，調用radix-tree_shrink()嘗試收縮樹，然後退出循環
if(pathp->node->count){
if(pathp->node==radix_tree_indirect_to_ptr(root->rnode))
radix_tree_shrink(root)；
goto out;
}
//Node with zero slots in use so free it
to_free=pathp->node;
pathp--;
}
/*運行到此處表明樹不包含對象成為空樹，釋放掉to_free包含的根節點，樹高置為0，根指針置空*/
root_tag_clear_aIl(root);
root->height=0;
root->rnode=NULL;
if(to_free)
radix_tree_node_free(to_free);
out:
return sIot;
}

(4)樹的擴展：

statIc int radix_tree_extend (struct radix_tree_root *root,unsigned Iong index)
{
struct radix_tree_node *node;
unsigned int height;
int tag;
//高度增1
height=root->height+1;
∥循環比較樹的最大索引值和index．通過遞增高度最終使樹能夠容納指定索引的對象
while(index>radix_tree_maxindex(height))
height++;
//對於空樹，留待以後分配節點，這裡僅調整樹的高度
if(root->rnode==NULL){
root->height=height;
goto out;
}
通過在原根節點以上增加一段單支子樹．從而使樹高達到指定值，根節點被新增子樹的根取代，新增子樹的葉子節點指向原根/節點，新增的節點具有除槽位0的指針指向子節點外其余槽位都是空指針，也就是最左單支樹的特征．這種調整相當於在原id位串的高位增加了一串0，從而使原對象id值和其在新擴樹中的位置仍保持正確的對應關系。
do{
unsigned int newheight;
if(! (node=radix_tree_node_aIIoc(root)))
return -ENOMEM;
/*lncrease the height．*/
node->slots[0]=radix_tree_indirect_to_ptr(root->rnode);
/*Propagate the aggregated tag info into the new root*/
for(tag=0;tag
if(root_tag_get(root,tag))
tag_set(node,tag,0);
}
newheight=root->height+1;
node->height=newheight;
node->count=1;
node=radix_tree_ptr_to_indirect(node);
rcu_assign_pointer(root->rnode,node);
root->height=newheight;
}whiIe(height>root->height)：
out:
return 0;
}

(5) 樹的收縮。

從根節點開始向下檢查符合除第0個槽位外其他槽位指針都空的條件的節點，直至遇到第n層的節點不滿足這個條件，把1~n-1層的單支樹收縮，釋放沿途節點f返還給slab分配器)，然後把n層節點作為新的根節點：

static inIine void radix_tree_shrink (struct radix_tree_root *root)
{
/*try to shrink tree height*/
whiIe(root->height>0){
struct radix_tree_ node *to_ free=root->rnode;
void* newptr;
BUG_0N(!radix_free_is_indirect_ptr(to_free));
to_free=radix_tree_indirect_to_ptr(to_free);
//當前節點子節點數不等於1則退出循環
if(to_free->count!=1)
break;
//子節點不是第0槽位的指針指向也退出循環
if(!to_free->slots[0])
break;
//newptr存放to_free的唯一的子節點指針
newptr=to_free->slots[0];
if(root->height>1)
newptr=radix_free_ptr_to_indirect(newptr);
//子節點作為新的根節點
root->rnode=newptr;
root->height--;//樹的高度遞減
/*must only free zeroed nodes into the sIab*/
tag_clear(to_free,0,0);
tag_cIear(to_free,1,0);
∥釋放to_free節點
to_free->sIots[0]=NULL;
to_free->count=0;
radix_tree_node_free(to_free);
}
}

(6)根據頁索引index查詢對象：

void *radix_tree_lookup (struct radix_tree_root *root, unsigned long index)
{
unsigned int height,shift;
struct radix_tree_node *node,**slot;
node=rcu_dereference(root->rnode);
…
height=node->height;
if(index>radix_tree_maxindex(height))
return NULL;
//設置初始移位的位數
shlft=(height-1)*RADIX_TREE_MAP_SHlFT;
/*從頂向下循環逐層檢索，先由index、移位數shift和位掩碼獲取槽索引，再由當前節點node和槽索引獲取槽位sIot．然後node指向節點指針槽指示的下層節點，最後重新調整移位數shift和當前高度height，直至到達0層，此時node即指向了對象*/
do{
sIot=(struct radix_tree_node**)(node->sIots+((index>>shift)&RADIX_TREE_MAP_MASK));
node=rcu_dereference(*sIot);
if(node==NULL)
return NULL;
shift-=RADIX_TREE_MAP_SHlFT;
height--;
}whiIe(height>0);
return node;
}

2.2Linux\Iib\idr.c

idr機制基本上也是基數樹的一套方法．但是它又多了尋找空閒id的功能，所以不能完全照搬上面的機制。

具體代碼分析略。

3.外圍函數

3.1文件頁緩存

add_to_page_cache()函數調用radix_tree_insert()把指定頁插入指定的文件頁緩存基數樹的指定位置，find_get_page()在地址空間的基數樹中尋找指定索引的頁。這兩個函數都包含於Linux\mm\filemap.c。它們對基數樹的動作分別是寫和讀，由於radix_tree.c中的基數樹的函數本身沒有同步手段，因此要求調用它們的外圍函數包含同步措施．而這兩個外圍函數使用了地址空間的讀寫鎖，add_to_page_cache()在調用radix_tree_insert()前先調用write_lock_irq(&mapping->tree_lock);進行了寫鎖定，而find_get_page()則調用read_lock_irq(&mapping->tree_lock);進行讀鎖定。

3.2 ipc的idr機制

ipc_findkey()調用idr_find()由0開始遍歷基數樹，直至找到指定鍵值的對象；ipc_addid()調用idr_get_new()將對象加入idr樹並返回和位置對應的id；ipc_rmid()調用idr_remove()從idr樹刪除指定id的對象，這些函數包含於Linux\ipc\unic.c。它們的同步問題則由最外層的ipc函數使用讀寫信號量保證，比如ipc_rmid()的調用路徑為shm_close()->shm_destroy()->shm_rmid()->ipc_rmid()，shm_close()中使用down_write(&shm_ids(ns).rw_mutex);把共享內存的ids給鎖住了，這樣犧牲了一定的並發性，但保證了數據的一致性．以後的版本估計會使用更細粒度的鎖或並發性更好的機制。同理，ipc_addid()的調用路徑為sys_shmget()->ipcget()->ipcget_new()->newseg()->shm_addid()->ipc_addid()，在ipcget_new()中也使用down_write(&ids->rw_mutex)；寫鎖定了整個ids。

5.結語

對於根據id定位對象的數據結構，固定數組最直接，速度最快。而以邏輯運算加移位

操作的組合作為散列函數的散列表則次之。但是數組適用於對象數變化不大或者最大對象數不是很多的場合，非常不適於對象分布稀疏的場合，否則內存的浪費比較嚴重；而散列表在查詢和插入刪除時要求鎖住整個表，對於共享頻繁的場合會導致並發性能不佳，此外由於缺少數組那樣的位置和id的映射唯一性，從而不適用於需要自動生成id的場合。基數樹則取長補短，它的搜索性能在可接受范圍內，內存消耗也不大，又具有動態性，能按需收縮或者擴充。更重要的是它和數組一樣具有位置和id的唯一映射關系，從而很容易在加入新對象的同時生成id值，這是散列表所沒有的．此外系統中可以創建很多這樣的樹，因此也提高了並發性能。