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;item=list_entry(link_ptr,structtask_item,link);

list_entry()底层使用container_of()，根据：

1. 成员link的地址；
2. 外层结构体类型；
3. 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(i=0;i<BUCKET_COUNT;i++)INIT_HLIST_HEAD(&table[i]);

实际内核代码也常使用DECLARE_HASHTABLE()、DEFINE_HASHTABLE()及hash_*系列宏。

插入

课程用取模演示如何选择桶：

unsignedintbucket=item->key%BUCKET_COUNT;INIT_HLIST_NODE(&item->node);hlist_add_head(&item->node,&table[bucket]);

真正的哈希函数需要尽量均匀地分散 key。大量数据落入同一桶会退化成长链表，使查询从接近 O(1) 退化到 O(n)。

查询、删除与清理

structhash_item*item;unsignedintbucket=key%BUCKET_COUNT;hlist_for_each_entry(item,&table[bucket],node){if(item->key==key)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_roottree=RB_ROOT;

插入分为“定位、链接、重新着色”三步

staticintinsert_item(structrb_root*root,structtree_item*item){structrb_node**link=&root->rb_node;structrb_node*parent=NULL;while(*link){structtree_item*current;parent=*link;current=rb_entry(parent,structtree_item,node);if(item->key<current->key)link=&parent->rb_left;elseif(item->key>current->key)link=&parent->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*node=root->rb_node;while(node){structtree_item*item=rb_entry(node,structtree_item,node);if(key<item->key)node=node->rb_left;elseif(key>item->key)node=node->rb_right;elsereturnitem;}returnNULL;}

有序遍历与释放

structrb_node*node;for(node=rb_first(&tree);node;node=rb_next(node)){structtree_item*item=rb_entry(node,structtree_item,node);pr_info("key=%d\n",item->key);}

释放时应先保存下一个节点，再删除和回收当前对象：

structrb_node*node=rb_first(&tree);while(node){structtree_item*item=rb_entry(node,structtree_item,node);node=rb_next(node);rb_erase(&item->node,&tree);kfree(item);}

四、如何在 Binder 驱动中识别这些结构

不同 Android 内核版本的字段会调整，但整体职责非常稳定：

阅读源码时，可以先把容器操作翻译成业务动作：

list_add_tail → 把工作排到队尾 list_del_init → 从当前队列摘除并恢复为空节点 rb_entry → 从索引节点找回 Binder 业务对象 rb_insert_color → 新对象加入可查询索引 rb_erase → 对象从索引移除 hlist_for_each... → 遍历某个全局或哈希集合

这样就不会陷在宏实现里，而能继续追踪“哪个事务进入了哪个队列”“某个句柄如何找到目标节点”。

三种结构怎么选

真正的内核对象常同时嵌入多个节点：一个节点负责进入工作队列，另一个rb_node负责按 ID 查询。理解“业务对象同时属于多个容器”，是继续阅读 Binder 驱动数据结构的关键。