linux内核数据结构之链表

数据结构中linklist的理解LinkList（链表）的理解。

在数据结构中，链表（LinkList）是一种基本的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

链表是一种线性数据结构，它可以用来表示一系列元素的顺序。

与数组不同，链表中的元素在内存中不是连续存储的，而是通过指针相互连接起来的。

这种特性使得链表具有一些独特的优势和应用场景。

链表的基本结构。

链表由节点组成，每个节点包含两部分，数据和指针。

数据部分用来存储元素的值，指针部分用来指向下一个节点。

链表的第一个节点称为头节点，最后一个节点称为尾节点，尾节点的指针指向空值（NULL）。

链表的分类。

链表可以分为单向链表、双向链表和循环链表三种基本类型。

单向链表，每个节点只包含一个指针，指向下一个节点。

双向链表，每个节点包含两个指针，分别指向前一个节点和后一个节点。

循环链表，尾节点的指针指向头节点，形成一个闭环。

不同类型的链表适用于不同的场景，选择合适的链表类型可以提高数据操作的效率。

链表的优势。

链表相对于数组有一些明显的优势：插入和删除操作高效，由于链表中的元素不是连续存储的，插入和删除操作可以在常数时间内完成，而数组中的插入和删除操作需要移动大量元素，时间复杂度为O(n)。

动态扩展，链表的大小可以动态调整，不需要预先分配固定大小的内存空间。

链表的应用场景。

由于链表的优势，它在一些特定的应用场景中得到了广泛的应用：LRU缓存，链表可以用来实现LRU（Least Recently Used）缓存淘汰算法，当缓存空间不足时，链表可以高效地删除最久未使用的元素。

大整数运算，链表可以用来表示大整数，实现大整数的加减乘除运算。

图论算法，在图论算法中，链表常常用来表示图的邻接表，用于表示图中的顶点和边的关系。

链表的实现。

链表的实现可以使用指针或者引用来表示节点之间的关系。

在C语言中，可以使用指针来表示节点之间的连接关系；在Java等语言中，可以使用引用来表示节点之间的连接关系。

linux内核hash表使用例程Linux内核中的hash表是一种常用的数据结构，用于快速查找和插入数据。

它是一种哈希表，通过将关键字映射到一个固定大小的数组中，并在数组中存储对应的值来实现高效的查找和插入操作。

在Linux内核中，hash表广泛应用于各个子系统中，比如网络子系统、文件系统、进程管理等。

这些子系统需要快速地查找和插入数据，而hash表正是为此而设计的。

hash表的实现方式多种多样，但在Linux内核中，一般采用的是拉链法（chaining）来处理冲突。

具体来说，每个数组元素都是一个链表的头指针，当多个关键字映射到同一个数组元素时，它们会被插入到链表中。

这样，当需要查找某个关键字时，只需要根据关键字的哈希值找到对应的数组元素，然后遍历链表即可。

为了提高查找效率，Linux内核中的hash表还采用了一些优化措施。

例如，为了减少冲突，每个数组元素都会被分成多个桶（bucket），每个桶中存放一条链表。

这样，即使多个关键字映射到同一个数组元素，它们也可以分布在不同的桶中，从而提高查找效率。

为了进一步提高查找效率，Linux内核中的hash表还采用了一种叫做“二次哈希”的技术。

具体来说，每个关键字的哈希值会经过一次次的哈希函数计算，得到一个新的哈希值，然后再根据这个新的哈希值找到对应的数组元素。

这样，即使多个关键字的哈希值相同，它们经过二次哈希后得到的新的哈希值也会不同，从而减少冲突，提高查找效率。

除了拉链法和二次哈希，Linux内核中的hash表还可以采用其他的冲突解决方法，比如开放定址法（open addressing）。

在开放定址法中，当发生冲突时，会根据一定的规则来寻找下一个可用的数组元素，直到找到一个空闲的位置或者遍历完整个数组。

虽然开放定址法的实现比较简单，但由于可能出现聚集现象，导致查找效率下降，因此在Linux内核中使用较少。

总的来说，Linux内核中的hash表是一种高效的数据结构，用于快速查找和插入数据。

Linux内核：RCU机制与使⽤Linux 内核：RCU机制与使⽤背景学习Linux源码的时候，发现很多熟悉的数据结构多了__rcu后缀，因此了解了⼀下这些内容。

介绍RCU（Read-Copy Update）是数据同步的⼀种⽅式，在当前的Linux内核中发挥着重要的作⽤。

RCU主要针对的数据对象是链表，⽬的是提⾼遍历读取数据的效率，为了达到⽬的使⽤RCU机制读取数据的时候不对链表进⾏耗时的加锁操作。

这样在同⼀时间可以有多个线程同时读取该链表，并且允许⼀个线程对链表进⾏修改（修改的时候，需要加锁）。

RCU适⽤于需要频繁的读取数据，⽽相应修改数据并不多的情景，例如在⽂件系统中，经常需要查找定位⽬录，⽽对⽬录的修改相对来说并不多，这就是RCU发挥作⽤的最佳场景。

RCU(Read-Copy Update)，是 Linux 中⽐较重要的⼀种同步机制。

顾名思义就是“读，拷贝更新”，再直⽩点是“随意读，但更新数据的时候，需要先复制⼀份副本，在副本上完成修改，再⼀次性地替换旧数据”。

这是 Linux 内核实现的⼀种针对“读多写少”的共享数据的同步机制。

RCU机制解决了什么在RCU的实现过程中，我们主要解决以下问题：1、在读取过程中，另外⼀个线程删除了⼀个节点。

删除线程可以把这个节点从链表中移除，但它不能直接销毁这个节点，必须等到所有的读取线程读取完成以后，才进⾏销毁操作。

RCU中把这个过程称为宽限期（Grace period）。

2、在读取过程中，另外⼀个线程插⼊了⼀个新节点，⽽读线程读到了这个节点，那么需要保证读到的这个节点是完整的。

这⾥涉及到了发布-订阅机制（Publish-Subscribe Mechanism）。

3、保证读取链表的完整性。

新增或者删除⼀个节点，不⾄于导致遍历⼀个链表从中间断开。

但是RCU并不保证⼀定能读到新增的节点或者不读到要被删除的节点。

RCU(Read-Copy Update)，顾名思义就是读-拷贝修改，它是基于其原理命名的。

list_head 用法list_head是Linux内核中用于表示链表节点的数据结构，它提供了一些方便的方法来操作链表。

在Linux操作系统中，list_head通常用于表示一个链表的头部，链表的每个节点包含一些数据，而list_head仅包含对链表中下一个节点的指针引用。

list_head的用法非常简单，它主要有以下几个常用的成员变量和方法：1.list_head的成员变量：成员变量包括list_head的next指针和前一个节点的指针prev。

当list_head指向链表的最后一个节点时，prev通常为NULL。

2.list_add方法：用于将一个节点添加到链表的末尾。

该方法需要传入要添加的节点和链表的头节点。

3.list_del方法：用于从链表中删除一个节点。

该方法需要传入要删除的节点。

4.list_empty方法：用于判断链表是否为空。

如果链表为空，则返回TRUE，否则返回FALSE。

5.list_entry方法：用于获取链表中指定索引的节点。

该方法需要传入索引号和头节点。

使用list_head可以方便地遍历链表中的所有节点，也可以方便地添加、删除和查找节点。

下面是一个简单的示例代码，演示了如何使用list_head：```c#include<linux/list_head.h>#include<linux/module.h>structnode{intdata;structlist_headlist;};intmain(void){structnode*node1=kmalloc(sizeof(structnode),GFP_KERNEL);structnode*node2=kmalloc(sizeof(structnode),GFP_KERNEL);structnode*head=NULL;unsignedinti;/*初始化链表头部*/list_add(&head->list,&node1->list);list_add(&node2->list,&head->list);node2->data=1;node1->data=2;/*遍历链表*/printk("Listhead:%p\n",head);printk("Listelements:\n");for(i=0;i<2;i++){printk("Node%d:%d\n",i,list_entry(head->list.next,structnode,list)->data);list_del(&head->list);/*删除头节点*/head=list_entry(head->list.next,structnode,list)->list;/*移动到下一个节点*/}printk("Afterdeletion:\n");printk("Node%d:%d\n",i,head->data);/*打印最后一个节点*/ kfree(node1);kfree(node2);return0;}```在上面的示例代码中，我们首先创建了一个链表，并使用list_add方法将两个节点添加到链表中。

struct list_head的定义struct list_head是Linux内核中一个非常重要的数据结构，其主要作用是实现双向链表，是Linux内核实现链表的基础。

本文将详细介绍struct list_head的定义、使用方法及其重要性。

一、struct list_head的定义struct list_head是一个重要的数据结构，它定义在include/linux/list.h文件中，其定义如下：struct list_head {struct list_head *prev, *next;};其中，prev和next分别表示前一个节点和后一个节点的指针，因此struct list_head可以实现双向链表。

二、struct list_head的使用struct list_head主要用于实现链表，其使用方法如下：1. 初始化链表初始化链表的方法是通过定义一个struct list_head类型的变量，然后将其prev和next指针都指向自己，代码如下：struct list_head my_list = LIST_HEAD_INIT(my_list);2. 插入节点在链表中插入一个节点的方法是通过list_add函数，该函数将新节点插入到链表头部，代码如下：list_add(&new_node->list, &my_list);其中，new_node为新节点的指针，&new_node->list为新节点的struct list_head成员，&my_list为链表头的struct list_head 成员。

3. 删除节点从链表中删除一个节点的方法是通过list_del函数，该函数将节点从链表中删除，代码如下：list_del(&node->list);其中，node为要删除的节点的指针，&node->list为节点的struct list_head成员。

list_for_each_safe的用法list_for_each_safe是Linux内核中的一个宏，用于在遍历一个双向链表时确保遍历过程中的链表修改不会导致出现问题。

在本文中，将详细讨论list_for_each_safe的使用方法以及相关的背景知识。

1. 引言（介绍链表和链表遍历的重要性）链表是计算机科学中常用的数据结构之一，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

链表的遍历是对链表中的每个元素进行操作或访问的过程。

在操作系统中，特别是在Linux内核中，链表的使用非常广泛。

因此，高效且线程安全的链表遍历方法变得至关重要。

2. 理解安全遍历的需求链表是一个动态数据结构，在遍历链表时，可能会有其他线程或处理器修改链表的结构，比如添加、删除或移动节点。

如果不采取措施来处理这种情况，就可能导致指针丢失或访问无效的节点。

这对于操作系统内核来说是一个严重的问题，因为它们需要保证数据的一致性和稳定性。

list_for_each_safe宏就是为了解决这个问题而设计的。

3. list_for_each_safe的定义和参数在Linux内核源代码中，list_for_each_safe的定义如下：c#define list_for_each_safe(pos, n, head) \for (pos = list_first_entry(head, typeof(*pos), member), \ n = list_next_entry(pos, member); \&pos->member != (head); \pos = n, n = list_next_entry(n, member))在这个宏中，pos表示当前遍历节点的指针，n表示pos的下一个节点的指针，head是链表的头节点。

4. list_for_each_safe的实现原理list_for_each_safe的实现原理非常巧妙。

linux 内核list使用
在Linux内核中，list是一种常用的数据结构，用于实现链表。

它在内核中被广泛使用，包括进程管理、文件系统、网络等多个方面。

在内核中使用list时，有几个常见的操作和用法需要注意：
1. 初始化list，在使用list之前，需要先对其进行初始化。

可以使用宏INIT_LIST_HEAD来初始化一个空的list。

2. 添加元素到list，使用list_add、list_add_tail等函数
可以将新元素添加到list中。

这些函数会在指定位置插入新元素，
并更新相关指针。

3. 遍历list，可以使用list_for_each、
list_for_each_entry等宏来遍历list中的元素。

这些宏会帮助我
们遍历整个list，并执行指定的操作。

4. 删除元素，使用list_del和list_del_init函数可以从
list中删除指定的元素。

需要注意的是，在删除元素之后，需要手
动释放相关资源，以避免内存泄漏。

除了上述基本操作外，list还支持一些高级操作，如合并两个list、反转list等。

在编写内核代码时，合理地使用list可以提高代码的可读性和性能。

总的来说，Linux内核中的list是一种非常灵活和强大的数据结构，合理地使用它可以帮助我们更好地管理和组织数据。

在实际编程中，需要根据具体的需求和场景来选择合适的list操作，以达到最佳的效果。

掌握数据结构中的链表和数组的应用场景链表和数组都是常用的数据结构，它们在不同的场景下有不同的应用。

一、链表的应用场景：1.链表适合动态插入和删除操作：链表的插入和删除操作非常高效，只需修改指针的指向，时间复杂度为O(1)。

因此，当需要频繁进行插入和删除操作时，链表是一个很好的选择。

-操作系统中的进程控制块（PCB）：操作系统需要频繁地创建、停止、销毁进程，使用链表存储这些PCB，可以方便地插入、删除和管理进程。

-聊天记录：在聊天应用中，新的消息会动态插入到聊天记录中，使用链表存储聊天记录可以方便地插入新消息。

2.链表节省内存空间：每个节点只需存储当前元素和指向下一个节点的指针，不需要像数组一样预分配一块连续的内存空间，因此链表对内存空间的利用更加灵活。

-操作系统中的内存管理：操作系统使用链表来管理空闲内存块和已分配的内存块，可有效节省内存空间。

3.链表支持动态扩展：链表的长度可以随时变化，可以动态地扩容和缩容。

-缓存淘汰算法：在缓存中，如果链表已满，当有新数据需要加入缓存时，可以通过删除链表头部的节点来腾出空间。

4.链表可以快速合并和拆分：将两个链表合并成一个链表只要调整指针的指向即可，时间复杂度为O(1)。

-链表排序：在排序算法中，链表归并排序利用链表快速合并的特性，使得归并排序在链表上更高效。

二、数组的应用场景：1.随机访问：数组可以根据索引快速访问元素，时间复杂度为O(1)。

-图像处理：图像通常以像素点的形式存储在数组中，可以通过索引快速访问某个特定像素点的颜色信息。

2.内存连续存储：数组的元素在内存中是连续存储的，可以利用硬件缓存机制提高访问效率。

-矩阵运算：矩阵可以通过二维数组来表示，利用矩阵的连续存储特性，可以高效地进行矩阵运算。

3.大数据存储：数组可以预先分配一块连续的内存空间，非常适合存储大量的数据。

-数据库中的数据表：数据库中的数据表通常使用数组来实现，可以快速存取和处理大量的数据。

142/**143*klist_add_after-Init a klist_node and add it after an existing node 144*@n:node we're adding.145*@pos:node to put@n after146*//*在节点pos后面插入节点n*/147void klist_add_after(struct klist_node*n,struct klist_node*pos)148{149struct klist*k=knode_klist(pos);150151klist_node_init(k,n);152spin_lock(&k->k_lock);153list_add(&n->n_node,&pos->n_node);154spin_unlock(&k->k_lock);155}156EXPORT_SYMBOL_GPL(klist_add_after);157158/**159*klist_add_before-Init a klist_node and add it before an existing node 160*@n:node we're adding.161*@pos:node to put@n after162*//*在节点pos前面插入节点n*/163void klist_add_before(struct klist_node*n,struct klist_node*pos)164{165struct klist*k=knode_klist(pos);166167klist_node_init(k,n);168spin_lock(&k->k_lock);169list_add_tail(&n->n_node,&pos->n_node);170spin_unlock(&k->k_lock);171}172EXPORT_SYMBOL_GPL(klist_add_before);173/*等待者结构体，用于删除节点，删除完成唤醒进程*/174struct klist_waiter{175struct list_head list;176struct klist_node*node;177struct task_struct*process;178int woken;179};180/*定义并初始化klist节点移除自旋锁*/181static DEFINE_SPINLOCK(klist_remove_lock);/*定义一个等待器的链表*/182static LIST_HEAD(klist_remove_waiters);183184static void klist_release(struct kref*kref)185{186struct klist_waiter*waiter,*tmp;187struct klist_node*n=container_of(kref,struct klist_node,n_ref);188189WARN_ON(!knode_dead(n));/*删除链表中的节点入口*/190list_del(&n->n_node);191spin_lock(&klist_remove_lock);/*内核链表操作宏include/linux/list.h，遍历klist节点移除等待链表*/192list_for_each_entry_safe(waiter,tmp,&klist_remove_waiters,list){/*是要删除链表节点的等待器*/193if(waiter->node!=n)194continue;195/*等待者唤醒标志*/196waiter->woken=1;197mb();/*唤醒等待进程*/198wake_up_process(waiter->process);/*删除链表入口*/199list_del(&waiter->list);200}201spin_unlock(&klist_remove_lock);/*设置节点n指向的klist为空*/202knode_set_klist(n,NULL);203}204/*减引用次数并删除节点*/205static int klist_dec_and_del(struct klist_node*n)206{/*n->nref减引用次数，若引用次数减完不为0，调用klist_release清除节点对象，返回1；为0，则返回0*/207return kref_put(&n->n_ref,klist_release);208}209/*带锁操作的节点删除，不判断是否成功，减引用次数*/210static void klist_put(struct klist_node*n,bool kill)211{/*获取节点的put方法*/212struct klist*k=knode_klist(n);213void(*put)(struct klist_node*)=k->put;214215spin_lock(&k->k_lock);/*“需要杀死节点”==*/216if(kill)217knode_kill(n);/*节点对象引用次数为0了，则不需要调用put方法*/218if(!klist_dec_and_del(n))219put=NULL;220spin_unlock(&k->k_lock);/*调用put方法*/221if(put)222put(n);223}224225/**226*klist_del-Decrement the reference count of node and try to remove. 227*@n:node we're deleting.228*//*删除节点“杀死死节点*/229void klist_del(struct klist_node*n)230{231klist_put(n,true);232}233EXPORT_SYMBOL_GPL(klist_del);234235/**236*klist_remove-Decrement the refcount of node and wait for it to go away. 237*@n:node we're removing.238*/239void klist_remove(struct klist_node*n)240{/*定义一个等待者，并加入等待者加入移除等待者链表*/241struct klist_waiter waiter;242243waiter.node=n;244waiter.process=current;245waiter.woken=0;246spin_lock(&klist_remove_lock);247list_add(&waiter.list,&klist_remove_waiters);248spin_unlock(&klist_remove_lock);249/*清除节点，并设置等待者*/330*First grab list lock.Decrement the reference count of the previous 331*node,if there was one.Grab the next node,increment its reference 332*count,drop the lock,and return that next node.333*//*“预下”链表中下一节点*/334struct klist_node*klist_next(struct klist_iter*i)335{336void(*put)(struct klist_node*)=i->i_klist->put;337struct klist_node*last=i->i_cur;338struct klist_node*next;339/*抢占锁*/340spin_lock(&i->i_klist->k_lock);341/*获取下一节点*/342if(last){343next=to_klist_node(last->n_node.next);/*减上一节点引用次数*/344if(!klist_dec_and_del(last))345put=NULL;346}else347next=to_klist_node(i->i_klist->k_list.next);348349i->i_cur=NULL;/*链表中有节点“没死”，增加引用次数*/350while(next!=to_klist_node(&i->i_klist->k_list)){351if(likely(!knode_dead(next))){352kref_get(&next->n_ref);353i->i_cur=next;354break;355}356next=to_klist_node(next->n_node.next);357}358/*丢弃锁*/359spin_unlock(&i->i_klist->k_lock);360361if(put&&last)362put(last);363return i->i_cur;364}365EXPORT_SYMBOL_GPL(klist_next);366----------------------/*使用迭代查找下一链表节点*/1124struct klist_node*n=klist_next(i);1125struct device*dev=NULL;1126struct device_private*p;11271128if(n){/*根据节点入口获取该节点上的设备*/1129p=to_device_private_parent(n);1130dev=p->device;1131}1132return dev;1133}/*-------------------------------------------------------------------------------*//*其中device_private是设备私有数据结构，一下代码不难看出*想要由链表节点迭代查找设备非常容易*/66/**67*struct device_private-structure to hold the private to the driver core portions of the device structure.68*69*@klist_children-klist containing all children of this device70*@knode_parent-node in sibling list71*@knode_driver-node in driver list72*@knode_bus-node in bus list73*@driver_data-private pointer for driver specific info.Will turn into a74*list soon.75*@device-pointer back to the struct class that this structure is76*associated with.77*78*Nothing outside of the driver core should ever touch these fields.79*/80struct device_private{81struct klist klist_children;82struct klist_node knode_parent;83struct klist_node knode_driver;84struct klist_node knode_bus;85void*driver_data;86struct device*device;87};88#define to_device_private_parent(obj)\89container_of(obj,struct device_private,knode_parent)90#define to_device_private_driver(obj)\91container_of(obj,struct device_private,knode_driver)92#define to_device_private_bus(obj)\93container_of(obj,struct device_private,knode_bus) 94driver_attach()函数driver_attach()函数2009-04-2114:39:03|分类：linux kernel|字号订阅最近在看一个mpc8315CPU上的驱动程序发现在使用spi_register注册完成后没有调用到相应的probe函数，分析后发现在driver_attach()函数执行时没有找到匹配的device，在网上狗狗后找到关于这部分的分析，引用如下：个浅析linux2.6.23驱动自动匹配设备driver_attach()函数文章来源:int driver_attach(struct device_driver*drv){return bus_for_each_dev(drv->bus,NULL,drv,__driver_attach);}调用该函数,那么drv驱动程式会和drv所在总线上连接了的物理设备进行一一匹配,再来看看下面:int bus_for_each_dev(struct bus_type*bus,struct device*start,void*data,int(*fn)(struct device*,void*)){struct klist_iter i;//专门用于遍历的链表结构体,其中i_cur是遍历移动的关键struct device*dev;int error=0;if(!bus)return-EINVAL;klist_iter_init_node(&bus->klist_devices,&i,(start?&start->knode_bus:NULL));//i->i_klist=&bus->klist_devices;//i->i_head=&bus->klist_devices.k_list;//i->i_cur=NULL;//表示从最前端开始遍历挂接到bus总线上的整个设备链条.while((dev=next_device(&i))&&!error)//dev为该bus总线链表上的一个设备,[就像一根藤条上的一朵小花gliethttp_20071025] //这些device设备把自己的&device->knode_bus链表单元链接到了bus->klist_devices 上//这也说明名字为knode_bus的list单元将是要被挂接到bus->klist_devices的链表上//同理&device->knode_driver将是这个device设备链接到drivers驱动上的list节点识别单元//见driver_bound()->klist_add_tail(&dev->knode_driver,&dev->driver->klist_devices);error=fn(dev,data);//调用__driver_attach函数,进行匹配运算klist_iter_exit(&i);return error;//成功匹配返回0}struct klist_iter{struct klist*i_klist;struct list_head*i_head;struct klist_node*i_cur;};void klist_iter_init_node(struct klist*k,struct klist_iter*i,struct klist_node*n){i->i_klist=k;//需要被遍历的klisti->i_head=&k->k_list;//开始的链表头i->i_cur=n;//当前位置对应的klist_node节点,next_device()会从当前n 开始一直搜索到//链表的结尾,也就是i_head->prev处停止if(n)kref_get(&n->n_ref);//引用计数加1}static struct device*next_device(struct klist_iter*i){struct klist_node*n=klist_next(i);return n?container_of(n,struct device,knode_bus):NULL;//因为n是device->knode_bus的指针,所以container_of将返回device的指针}struct klist_node*klist_next(struct klist_iter*i){struct list_head*next;struct klist_node*lnode=i->i_cur;struct klist_node*knode=NULL;//赋0,当next==i->i_head时用于退出void(*put)(struct klist_node*)=i->i_klist->put;spin_lock(&i->i_klist->k_lock);if(lnode){next=lnode->n_node.next;if(!klist_dec_and_del(lnode))//释放前一个i_cur对象的引用计数put=NULL;//klist_dec_and_del成功的对引用计数做了减1操作,那么失效用户定义put}elsenext=i->i_head->next;//如果lnode=0,那么从链表头开始,所以head->next指向第1个实际对象if(next!=i->i_head){//head并不链接设备,所以head无效//当next==i->i_head时,说明已遍历到了head牵头的链表的末尾,回环到了head, //所以knode将不会进行赋值,这时knode=0,while((dev=next_device(&i))&&!error)因为0而退出knode=to_klist_node(next);//调用container_of()获取klist_node->n_node中klist_node地址kref_get(&knode->n_ref);//对该node的引用计数加1}i->i_cur=knode;//记住当前遍历到的对象,当next==i->i_head时,knode=0spin_unlock(&i->i_klist->k_lock);if(put&&lnode)put(lnode);return knode;}static int klist_dec_and_del(struct klist_node*n){return kref_put(&n->n_ref,klist_release);//对该node的引用计数减1,如果引用计数到达0,那么调用klist_release}static void klist_release(struct kref*kref){struct klist_node*n=container_of(kref,struct klist_node,n_ref);list_del(&n->n_node);//从节点链表上摘掉该node节点complete(&n->n_removed);//n->n_klist=NULL;}void fastcall complete(struct completion*x){unsigned long flags;spin_lock_irqsave(&x->wait.lock,flags);//关闭中断,防止并发x->done++;//唤醒因为某些原因悬停在klist_node->n_removed等待队列上的task们//这种现象之一是:__device_release_driver()删除挂接在设备上的driver时,会出现//删除task小憩在node的wait上__wake_up_common(&x->wait,TASK_UNINTERRUPTIBLE|TASK_INTERRUPTIBLE,1,0,NULL);spin_unlock_irqrestore(&x->wait.lock,flags);//恢复中断}static void__wake_up_common(wait_queue_head_t*q,unsigned int mode,int nr_exclusive,int sync,void*key){struct list_head*tmp,*next;list_for_each_safe(tmp,next,&q->task_list){//遍历以head牵头的链表上的task们wait_queue_t*curr=list_entry(tmp,wait_queue_t,task_list);unsigned flags=curr->flags;if(curr->func(curr,mode,sync,key)&&//调用wait上准备好了的回调函数func (flags&WQ_FLAG_EXCLUSIVE)&&!--nr_exclusive)break;}}//抛开链表上的head,当最后一个post==head时,说明链表已遍历结束(gliethttp_20071025) #define list_for_each_safe(pos,n,head)＼for(pos=(head)->next,n=pos->next;pos!=(head);＼pos=n,n=pos->next)void klist_iter_exit(struct klist_iter*i){if(i->i_cur){//对于正常遍历的退出,i->i_cur会等于0,如果找到了匹配对象,提前退出了,那么就会在这里对引用进行释放klist_del(i->i_cur);i->i_cur=NULL;}}static int__driver_attach(struct device*dev,void*data){struct device_driver*drv=data;//data就是打算把自己匹配到bus上挂接的合适设备上的driver驱动if(dev->parent)down(&dev->parent->sem);//使用信号量保护下面的操作down(&dev->sem);if(!dev->driver)//如果当前这个dev设备还没有挂接一个driver驱动driver_probe_device(drv,dev);//那么尝试该dev是否适合被该drv驱动管理up(&dev->sem);if(dev->parent)up(&dev->parent->sem);return0;}int driver_probe_device(struct device_driver*drv,struct device*dev){int ret=0;if(!device_is_registered(dev))//设备是否已被bus总线认可return-ENODEV;if(drv->bus->match&&!drv->bus->match(dev,drv))//调用该driver驱动自定义的match函数,如:usb_device_match(),查看//这个设备是否符合自己,drv->bus->match()返回1,表示本drv认可该设备//否则,goto done,继续检测下一个device设备是否和本drv匹配goto done;pr_debug("%s:Matched Device%s with Driver%s＼n",drv->bus->name,dev->bus_id,drv->name);//这下来真的了,ret=really_probe(dev,drv);done:return ret;}static inline int device_is_registered(struct device*dev){return dev->is_registered;//当调用bus_attach_device()之后,is_registered=1}static int really_probe(struct device*dev,struct device_driver*drv){int ret=0;atomic_inc(&probe_count);pr_debug("%s:Probing driver%s with device%s＼n",drv->bus->name,drv->name,dev->bus_id);WARN_ON(!list_empty(&dev->devres_head));dev->driver=drv;//管理本dev的驱动指针指向drvif(driver_sysfs_add(dev)){//将driver和dev使用link,链接到一起,使他们真正相关printk(KERN_ERR"%s:driver_sysfs_add(%s)failed＼n",__FUNCTION__,dev->bus_id);goto probe_failed;}if(dev->bus->probe){//总线提供了设备探测函数ret=dev->bus->probe(dev);if(ret)goto probe_failed;}else if(drv->probe){//驱动自己提供了设备探测函数//因为drv驱动自己也不想管理那些意外的非法设备//所以一般drv都会提供这个功能,相反//比如:usb_bus_type没有提供probe,而usb驱动提供了usb_probe_interface//来确认我这个driver软件真的能够管理这个device设备ret=drv->probe(dev);if(ret)goto probe_failed;}driver_bound(dev);ret=1;pr_debug("%s:Bound Device%s to Driver%s＼n",drv->bus->name,dev->bus_id,drv->name);goto done;probe_failed:devres_release_all(dev);driver_sysfs_remove(dev);dev->driver=NULL;if(ret!=-ENODEV&&ret!=-ENXIO){printk(KERN_WARNING"%s:probe of%s failed with error%d＼n",drv->name,dev->bus_id,ret);}ret=0;done:atomic_dec(&probe_count);wake_up(&probe_waitqueue);return ret;}static void driver_bound(struct device*dev){if(klist_node_attached(&dev->knode_driver)){//本dev已挂到了某个driver驱动的klist_devices链条上了//感觉不应该发生printk(KERN_WARNING"%s:device%s already bound＼n",__FUNCTION__,kobject_name(&dev->kobj));return;}pr_debug("bound device’%s’to driver’%s’＼n",dev->bus_id,dev->driver->name);if(dev->bus)blocking_notifier_call_chain(&dev->bus->bus_notifier,BUS_NOTIFY_BOUND_DRIVER,dev);//将本dev的knode_driver链表结构体节点挂接到该driver->klist_devices上//这样driver所管理的device设备又多了1个,//也能说又多了1个device设备使用本driver驱动管理他自己(gilethttp_20071025).klist_add_tail(&dev->knode_driver,&dev->driver->klist_devices);}Linux内核中的klist分析分析的内核版本照样是2.6.38.5。

需要了解Linux内核通知链机制的原理及实现一、概念：大多数内核子系统都是相互独立的，因此某个子系统可能对其它子系统产生的事件感兴趣。

为了满足这个需求，也即是让某个子系统在发生某个事件时通知其它的子系统，Linux 内核提供了通知链的机制。

通知链表只能够在内核的子系统之间使用，而不能够在内核与用户空间之间进行事件的通知。

通知链表是一个函数链表，链表上的每一个节点都注册了一个函数。

当某个事情发生时，链表上所有节点对应的函数就会被执行。

所以对于通知链表来说有一个通知方与一个接收方。

在通知这个事件时所运行的函数由被通知方决定，实际上也即是被通知方注册了某个函数，在发生某个事件时这些函数就得到执行。

其实和系统调用signal的思想差不多。

二、数据结构：通知链有四种类型：原子通知链（ Atomic notifier chains ）：通知链元素的回调函数（当事件发生时要执行的函数）只能在中断上下文中运行，不允许阻塞。

对应的链表头结构：struct atomic_noTIfier_head{ spinlock_t lock; struct noTIfier_block *head;};可阻塞通知链（ Blocking noTIfier chains ）：通知链元素的回调函数在进程上下文中运行，允许阻塞。

对应的链表头：struct blocking_noTIfier_head{ struct rw_semaphore rwsem; struct notifier_block *head;}; 原始通知链（ Raw notifier chains ）：对通知链元素的回调函数没有任何限制，所有锁和保护机制都由调用者维护。

对应的链表头：struct raw_notifier_head{ struct notifier_block *head;};SRCU 通知链（ SRCU notifier chains ）：可阻塞通知链的一种变体。