Binder 驅(qū)動(dòng)需要同時(shí)管理進(jìn)程、線程、節(jié)點(diǎn)、引用和待處理事務(wù)。源碼中大量出現(xiàn)list_head、hlist_node與rb_node。閱讀時(shí)如果只看到一堆宏和指針很容易失去業(yè)務(wù)主線。本文以“怎么識(shí)別、怎么遍歷、為什么使用”為目標(biāo)梳理這三類結(jié)構(gòu)。先理解內(nèi)核的“侵入式容器”設(shè)計(jì)普通集合通常由容器保存業(yè)務(wù)對(duì)象的指針Linux 內(nèi)核反過(guò)來(lái)讓業(yè)務(wù)結(jié)構(gòu)體嵌入鏈表或樹(shù)節(jié)點(diǎn)structtask_item{intvalue;structlist_headlink;};struct list_head不保存value只負(fù)責(zé)連接關(guān)系。這樣做有幾個(gè)好處不需要為容器節(jié)點(diǎn)額外分配一次內(nèi)存一個(gè)業(yè)務(wù)對(duì)象可以嵌入多個(gè)不同用途的節(jié)點(diǎn)避免使用void *類型轉(zhuǎn)換集中在統(tǒng)一宏中刪除、移動(dòng)節(jié)點(diǎn)時(shí)不需要復(fù)制業(yè)務(wù)對(duì)象。代價(jià)是源碼初看不直觀手中經(jīng)常只有l(wèi)ist_head *或rb_node *需要借助container_of找回外層業(yè)務(wù)對(duì)象。一、循環(huán)雙向鏈表list_head內(nèi)核鏈表節(jié)點(diǎn)的核心定義可以簡(jiǎn)化為structlist_head{structlist_head*next;structlist_head*prev;};它是循環(huán)雙向鏈表空鏈表的next和prev都指向頭節(jié)點(diǎn)自己而不是NULL。┌──────────────────────────────┐ ↓ │ head ? node A ? node B ? node C ─────┘這種設(shè)計(jì)讓頭、尾和中間節(jié)點(diǎn)的插入刪除可以使用相同邏輯減少特殊分支。初始化靜態(tài)聲明并初始化LIST_HEAD(todo_list);嵌入對(duì)象中的節(jié)點(diǎn)通常在運(yùn)行時(shí)初始化INIT_LIST_HEAD(item-link);兩者最終都會(huì)形成“自己指向自己”的空鏈表狀態(tài)。頭插與尾插list_add(item-link,todo_list);/* 插到 head 之后 */list_add_tail(item-link,todo_list);/* 插到 head 之前也就是尾部 */list_add()適合棧式處理新加入的節(jié)點(diǎn)最先被看到list_add_tail()適合隊(duì)列式處理保持先進(jìn)先出順序。Binder 的工作隊(duì)列需要關(guān)注插入位置因?yàn)樗苯佑绊懯聞?wù)處理順序。從連接節(jié)點(diǎn)找回業(yè)務(wù)對(duì)象structtask_item*item;itemlist_entry(link_ptr,structtask_item,link);list_entry()底層使用container_of()根據(jù)成員link的地址外層結(jié)構(gòu)體類型link在結(jié)構(gòu)體中的偏移反推出struct task_item的起始地址?？梢园阉斫鉃橥鈱訉?duì)象地址 成員地址 - 成員在結(jié)構(gòu)體中的偏移遍歷與安全刪除只需要list_head *structlist_head*pos;list_for_each(pos,todo_list){/* pos 指向每個(gè)連接節(jié)點(diǎn) */}直接得到業(yè)務(wù)對(duì)象structtask_item*item;list_for_each_entry(item,todo_list,link){pr_info(value%d\n,item-value);}如果遍歷過(guò)程中會(huì)刪除當(dāng)前項(xiàng)應(yīng)使用_safe版本預(yù)先保存下一個(gè)節(jié)點(diǎn)structtask_item*item;structtask_item*next;list_for_each_entry_safe(item,next,todo_list,link){list_del(item-link);kfree(item);}刪除后繼續(xù)使用原節(jié)點(diǎn)或者在普通遍歷中釋放當(dāng)前對(duì)象都會(huì)造成 use-after-free 或鏈表?yè)p壞。二、哈希桶使用的hlist內(nèi)核哈希表常使用hlist_head作為桶頭、hlist_node作為節(jié)點(diǎn)structhlist_head{structhlist_node*first;};structhlist_node{structhlist_node*next;structhlist_node**pprev;};hlist不是普通的循環(huán)雙向鏈表。桶頭只有一個(gè)first指針節(jié)點(diǎn)的pprev指向“前一個(gè)位置中保存當(dāng)前節(jié)點(diǎn)指針的字段”。對(duì)于第一個(gè)節(jié)點(diǎn)pprev直接指向桶頭的first對(duì)于后續(xù)節(jié)點(diǎn)則指向前一節(jié)點(diǎn)的next。bucket.first ──→ A.next ──→ B.next ──→ C ↑ ↑ ↑ A.pprev B.pprev C.pprev這種設(shè)計(jì)既節(jié)省桶頭空間又讓任意節(jié)點(diǎn)能夠在不知道前驅(qū)對(duì)象類型的情況下完成 O(1) 刪除。定義業(yè)務(wù)節(jié)點(diǎn)與桶數(shù)組#defineBUCKET_COUNT256structhash_item{intkey;intvalue;structhlist_nodenode;};staticstructhlist_headtable[BUCKET_COUNT];初始化inti;for(i0;iBUCKET_COUNT;i)INIT_HLIST_HEAD(table[i]);實(shí)際內(nèi)核代碼也常使用DECLARE_HASHTABLE()、DEFINE_HASHTABLE()及hash_*系列宏。插入課程用取模演示如何選擇桶unsignedintbucketitem-key%BUCKET_COUNT;INIT_HLIST_NODE(item-node);hlist_add_head(item-node,table[bucket]);真正的哈希函數(shù)需要盡量均勻地分散 key。大量數(shù)據(jù)落入同一桶會(huì)退化成長(zhǎng)鏈表使查詢從接近 O(1) 退化到 O(n)。查詢、刪除與清理structhash_item*item;unsignedintbucketkey%BUCKET_COUNT;hlist_for_each_entry(item,table[bucket],node){if(item-keykey)returnitem;}邊遍歷邊刪除同樣要使用安全版本structhash_item*item;structhlist_node*tmp;hlist_for_each_entry_safe(item,tmp,table[bucket],node){hlist_del(item-node);kfree(item);}kmalloc分配的內(nèi)存必須由kfree釋放。把節(jié)點(diǎn)從 hlist 中摘除只修改連接關(guān)系并不會(huì)自動(dòng)釋放外層業(yè)務(wù)對(duì)象。三、紅黑樹(shù)rbtree紅黑樹(shù)是一棵自動(dòng)保持近似平衡的二叉搜索樹(shù)。它的核心特點(diǎn)是查找、插入和刪除的復(fù)雜度穩(wěn)定在 O(log n)中序遍歷天然按 key 排序不需要像哈希表那樣預(yù)先選擇桶數(shù)量相比哈希表能高效完成按范圍或按順序訪問(wèn)。內(nèi)核只提供樹(shù)結(jié)構(gòu)和平衡操作不替業(yè)務(wù)代碼決定“key 是什么、如何比較”。節(jié)點(diǎn)同樣嵌入業(yè)務(wù)對(duì)象structtree_item{intkey;structrb_nodenode;};staticstructrb_roottreeRB_ROOT;插入分為“定位、鏈接、重新著色”三步staticintinsert_item(structrb_root*root,structtree_item*item){structrb_node**linkroot-rb_node;structrb_node*parentNULL;while(*link){structtree_item*current;parent*link;currentrb_entry(parent,structtree_item,node);if(item-keycurrent-key)linkparent-rb_left;elseif(item-keycurrent-key)linkparent-rb_right;elsereturn-EEXIST;}rb_link_node(item-node,parent,link);rb_insert_color(item-node,root);return0;}rb_link_node()只把節(jié)點(diǎn)放入搜索樹(shù)位置rb_insert_color()才負(fù)責(zé)旋轉(zhuǎn)和著色、恢復(fù)紅黑樹(shù)約束。漏掉第二步會(huì)得到一棵可能逐漸失衡的樹(shù)。查詢staticstructtree_item*find_item(structrb_root*root,intkey){structrb_node*noderoot-rb_node;while(node){structtree_item*itemrb_entry(node,structtree_item,node);if(keyitem-key)nodenode-rb_left;elseif(keyitem-key)nodenode-rb_right;elsereturnitem;}returnNULL;}有序遍歷與釋放structrb_node*node;for(noderb_first(tree);node;noderb_next(node)){structtree_item*itemrb_entry(node,structtree_item,node);pr_info(key%d\n,item-key);}釋放時(shí)應(yīng)先保存下一個(gè)節(jié)點(diǎn)再刪除和回收當(dāng)前對(duì)象structrb_node*noderb_first(tree);while(node){structtree_item*itemrb_entry(node,structtree_item,node);noderb_next(node);rb_erase(item-node,tree);kfree(item);}四、如何在 Binder 驅(qū)動(dòng)中識(shí)別這些結(jié)構(gòu)不同 Android 內(nèi)核版本的字段會(huì)調(diào)整但整體職責(zé)非常穩(wěn)定Binder 對(duì)象關(guān)系常見(jiàn)結(jié)構(gòu)原因進(jìn)程或線程的待處理事務(wù)list_head經(jīng)常按隊(duì)列順序取出等待線程、異步任務(wù)list_head插入、摘除頻繁全局 Binder 進(jìn)程/設(shè)備集合hlist桶頭或全局頭開(kāi)銷小、刪除方便按線程 ID 查找binder_threadrb_root/rb_node查找穩(wěn)定且無(wú)需固定桶數(shù)按節(jié)點(diǎn)指針查找binder_noderb_root/rb_node需要根據(jù)有序 key 快速定位按句柄或節(jié)點(diǎn)查找引用多棵紅黑樹(shù)同一對(duì)象需要支持不同 key 的索引閱讀源碼時(shí)可以先把容器操作翻譯成業(yè)務(wù)動(dòng)作list_add_tail → 把工作排到隊(duì)尾 list_del_init → 從當(dāng)前隊(duì)列摘除并恢復(fù)為空節(jié)點(diǎn) rb_entry → 從索引節(jié)點(diǎn)找回 Binder 業(yè)務(wù)對(duì)象 rb_insert_color → 新對(duì)象加入可查詢索引 rb_erase → 對(duì)象從索引移除 hlist_for_each... → 遍歷某個(gè)全局或哈希集合這樣就不會(huì)陷在宏實(shí)現(xiàn)里而能繼續(xù)追蹤“哪個(gè)事務(wù)進(jìn)入了哪個(gè)隊(duì)列”“某個(gè)句柄如何找到目標(biāo)節(jié)點(diǎn)”。三種結(jié)構(gòu)怎么選需求更合適的結(jié)構(gòu)按加入順序處理、頻繁移動(dòng)節(jié)點(diǎn)雙向鏈表通過(guò) key 做精確查詢?cè)试S預(yù)設(shè)桶哈希表查詢性能穩(wěn)定還需要有序遍歷紅黑樹(shù)真正的內(nèi)核對(duì)象常同時(shí)嵌入多個(gè)節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)負(fù)責(zé)進(jìn)入工作隊(duì)列另一個(gè)rb_node負(fù)責(zé)按 ID 查詢。理解“業(yè)務(wù)對(duì)象同時(shí)屬于多個(gè)容器”是繼續(xù)閱讀 Binder 驅(qū)動(dòng)數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵。