Binder 驱动需要同时管理进程、线程、节点、引用和待处理事务。源码中大量出现list_head、hlist_node与rb_node。阅读时如果只看到一堆宏和指针很容易失去业务主线。本文以“怎么识别、怎么遍历、为什么使用”为目标梳理这三类结构。先理解内核的“侵入式容器”设计普通集合通常由容器保存业务对象的指针Linux 内核反过来让业务结构体嵌入链表或树节点structtask_item{intvalue;structlist_headlink;};struct list_head不保存value只负责连接关系。这样做有几个好处不需要为容器节点额外分配一次内存一个业务对象可以嵌入多个不同用途的节点避免使用void *类型转换集中在统一宏中删除、移动节点时不需要复制业务对象。代价是源码初看不直观手中经常只有list_head *或rb_node *需要借助container_of找回外层业务对象。一、循环双向链表list_head内核链表节点的核心定义可以简化为structlist_head{structlist_head*next;structlist_head*prev;};它是循环双向链表空链表的next和prev都指向头节点自己而不是NULL。┌──────────────────────────────┐ ↓ │ head ⇄ node A ⇄ node B ⇄ node C ─────┘这种设计让头、尾和中间节点的插入删除可以使用相同逻辑减少特殊分支。初始化静态声明并初始化LIST_HEAD(todo_list);嵌入对象中的节点通常在运行时初始化INIT_LIST_HEAD(item-link);两者最终都会形成“自己指向自己”的空链表状态。头插与尾插list_add(item-link,todo_list);/* 插到 head 之后 */list_add_tail(item-link,todo_list);/* 插到 head 之前也就是尾部 */list_add()适合栈式处理新加入的节点最先被看到list_add_tail()适合队列式处理保持先进先出顺序。Binder 的工作队列需要关注插入位置因为它直接影响事务处理顺序。从连接节点找回业务对象structtask_item*item;itemlist_entry(link_ptr,structtask_item,link);list_entry()底层使用container_of()根据成员link的地址外层结构体类型link在结构体中的偏移反推出struct task_item的起始地址。可以把它理解为外层对象地址 成员地址 - 成员在结构体中的偏移遍历与安全删除只需要list_head *structlist_head*pos;list_for_each(pos,todo_list){/* pos 指向每个连接节点 */}直接得到业务对象structtask_item*item;list_for_each_entry(item,todo_list,link){pr_info(value%d\n,item-value);}如果遍历过程中会删除当前项应使用_safe版本预先保存下一个节点structtask_item*item;structtask_item*next;list_for_each_entry_safe(item,next,todo_list,link){list_del(item-link);kfree(item);}删除后继续使用原节点或者在普通遍历中释放当前对象都会造成 use-after-free 或链表损坏。二、哈希桶使用的hlist内核哈希表常使用hlist_head作为桶头、hlist_node作为节点structhlist_head{structhlist_node*first;};structhlist_node{structhlist_node*next;structhlist_node**pprev;};hlist不是普通的循环双向链表。桶头只有一个first指针节点的pprev指向“前一个位置中保存当前节点指针的字段”。对于第一个节点pprev直接指向桶头的first对于后续节点则指向前一节点的next。bucket.first ──→ A.next ──→ B.next ──→ C ↑ ↑ ↑ A.pprev B.pprev C.pprev这种设计既节省桶头空间又让任意节点能够在不知道前驱对象类型的情况下完成 O(1) 删除。定义业务节点与桶数组#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]);真正的哈希函数需要尽量均匀地分散 key。大量数据落入同一桶会退化成长链表使查询从接近 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释放。把节点从 hlist 中摘除只修改连接关系并不会自动释放外层业务对象。三、红黑树rbtree红黑树是一棵自动保持近似平衡的二叉搜索树。它的核心特点是查找、插入和删除的复杂度稳定在 O(log n)中序遍历天然按 key 排序不需要像哈希表那样预先选择桶数量相比哈希表能高效完成按范围或按顺序访问。内核只提供树结构和平衡操作不替业务代码决定“key 是什么、如何比较”。节点同样嵌入业务对象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()只把节点放入搜索树位置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);}释放时应先保存下一个节点再删除和回收当前对象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 内核版本的字段会调整但整体职责非常稳定Binder 对象关系常见结构原因进程或线程的待处理事务list_head经常按队列顺序取出等待线程、异步任务list_head插入、摘除频繁全局 Binder 进程/设备集合hlist桶头或全局头开销小、删除方便按线程 ID 查找binder_threadrb_root/rb_node查找稳定且无需固定桶数按节点指针查找binder_noderb_root/rb_node需要根据有序 key 快速定位按句柄或节点查找引用多棵红黑树同一对象需要支持不同 key 的索引阅读源码时可以先把容器操作翻译成业务动作list_add_tail → 把工作排到队尾 list_del_init → 从当前队列摘除并恢复为空节点 rb_entry → 从索引节点找回 Binder 业务对象 rb_insert_color → 新对象加入可查询索引 rb_erase → 对象从索引移除 hlist_for_each... → 遍历某个全局或哈希集合这样就不会陷在宏实现里而能继续追踪“哪个事务进入了哪个队列”“某个句柄如何找到目标节点”。三种结构怎么选需求更合适的结构按加入顺序处理、频繁移动节点双向链表通过 key 做精确查询允许预设桶哈希表查询性能稳定还需要有序遍历红黑树真正的内核对象常同时嵌入多个节点一个节点负责进入工作队列另一个rb_node负责按 ID 查询。理解“业务对象同时属于多个容器”是继续阅读 Binder 驱动数据结构的关键。