前言最近在研究Binder驱动的binder_work时，发现了如下结构：structbinder_work{structlist_headentry;枚举{...}类型；发现引入了list_head链表节点，这样binder_work类型也可以看成是一个链表。那么binder_work也可以加入到链表中。以binder_enqueue_work_ilocked方法为例：BUG_ON(work->entry.next&&!list_empty(&work->entry));list_add_tail(&work->entry,target_list);//将binder_work的entry成员添加到target_list中}所以先熟悉一下list在内核中的实现和常用方法，对学习Binder内容有帮助。1.内核链表初始化1.1创建初始化#defineLIST_HEAD_INIT(name){&(name),&(name)}#defineLIST_HEAD(name)\structlist_headname=LIST_HEAD_INIT(name)这种构造方法很巧妙，当调用LIST_HEAD(name)时，是structlist_headname={&(name),&(name)}由于list_head结构的定义是：structlist_head{structlist_head*next,*prev;};即next、prev都指向自己。1.2初始化方式个人觉得这种方式比较好理解：staticinlinevoidINIT_LIST_HEAD(structlist_head*list){WRITE_ONCE(list->next,list);//相当于list->net=list;list->prev=list;}INIT_LIST_HEAD初始化链表时，实际上是将头节点的next和prev指向自己。至于我第一次看到WRITE_ONCE，stackoverflow的解释是：1.Read/write"tearing":用许多更小的内存访问替换单个内存访问。GCC可能（并且确实！）在某些情况下会替换p=0x01020304之类的内容；使用两个16位立即存储指令-而不是大概将常量放在寄存器中，然后进行内存访问，等等。WRITE_ONCE允许我们对GCC说，“不要那样做”，就像这样：WRITE_ONCE(p,0x01020304);编译器可能会将读写操作分成多条指令，WRITE_ONCE可以保证这些操作只有一次。2.C编译器已停止保证字访问是原子的。任何非无竞争的程序都可能被错误编译并产生惊人的结果。不仅如此，编译器可能会决定不在循环内的寄存器中保留某些值，从而导致多个引用会像这样弄乱代码：C的编译器无法保证对单词的访问是原子的。凡是能引起多线程竞争的程序，都可能因编译而产生不同的结果。详细内容请参考READ_ONCE和WRITE_ONCE。简而言之，有以下三个好处：使代码更容易理解代码规范的要求和能够检测数据竞争（datarace）2.常见的内核操作：2.1list_addlist_add(structlist_headnew,structlist_headhead);将节点插入链表的头部staticinlinevoid__list_add(structlist_head*new,structlist_head*prev,structlist_head*next){if(!__list_add_valid(new,prev,next))return;下一个->上一个=新的；新->下一个=下一个；新->上一个=上一个；WRITE_ONCE(prev->next,new);}staticinlinevoidlist_add(structlist_head*new,structlist_head*head){__list_add(new,head,head->next);}2.2list_add_taillist_add_tail(structlist_headnew,structlist_headhead);将节点插入链表的末尾staticinlinevoidlist_add_tail(structlist_head*new,structlist_head*head){__list_add(new,head->prev,head);}__list_add方法用于在末尾添加节点和在头部添加节点。__list_add参数可以理解为：第一个是要添加的节点，两个都是新的；第二个是要添加的位置的priv，在头部添加节点的参数为head，在尾部添加节点的参数为head->priv；第三个是需要添加的位置，头部添加节点的参数为head->next，尾部添加节点的位置为head2.3list_dellist_del(structlist_head*entry);删除一个节点并添加其指针clear0staticinlinevoidlist_del(structlist_head*entry){__list_del_entry(entry);entry->next=LIST_POISON1;//LIST_POISINO1和LIST_POISON2是两个无效地址区__list_del(entry->prev,entry->next);}staticinlinebool__list_del_entry_valid(structlist_head*entry){returntrue;}staticinlinevoid__list_del(structlist_head*prev,structlist_head*next){next->prev=上一个；WRITE_ONCE(prev->next,next);}2.4list_del_initlist_del_init(structlist_head*entry);删除一个节点并将其指针再次指向自身staticinlinevoidlist_del_init(structlist_head*entry){__list_del_entry(entry);在里面_LIST_HEAD(entry);}2.5list_replacelist_replace(structlist_head*old,structlist_head*new);替换链表中的一个节点，old需要替换节点，new新节点staticinlinevoidlist_replace(structlist_head*old,structlist_head*new){new->next=old->next;新的->下一个->上一个=新的；new->prev=old->prev;new->prev->next=new;}2.6list_replace_initlist_replace_init(structlist_head*old,structlist_head*new);与上面不同的是替换后的旧节点被初始化staticinlinevoidlist_replace_init(structlist_head*old,structlist_head*new){list_replace(old,new);INIT_LIST_HEAD(old);}2.7list_is_lastintlist_is_last(conststructlist_head*list,conststructlist_head*head);测试一个节点是否为链表的尾节点，list为待测试节点，head为链表头staticinlineintlist_is_last(conststructlist_head*list,conststructlist_head*head){returnlist->next==head;}??2.8list_emptyintlist_empty(conststructlist_head*head);测试链表是否为空staticinlineintlist_empty(conststructlist_head*head){returnREAD_ONCE(head->next)==head;}
