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