linux设备驱动之更强的链表klist

《linux设备驱动之更强的链表klist》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、前面我们说到过list_head，这是linux中通用的链表形式，双向循环链表，功能强大，实现简单优雅。可如果您认为list_head就是链表的极致，应该在linux链表界一统天下，那可就错了。据我所知，linux内核代码中至少还有两种链表能占有一席之地。一种就是hlist，一种就是本节要介绍的klist。虽然三者不同，但hlist和klist都可以看成是从list_head中发展出来的，用于特殊的链表使用情景。hlist是用于哈希表中。众所周知，哈希表主要就是一个哈希数组，为了解决映射冲突的问题，

2、常常把哈希数组的每一项做成一个链表，这样有多少重复的都可以链进去。但哈希数组的项很多，list_head的话每个链表头都需要两个指针的空间，在稀疏的哈希表中实在是一种浪费，于是就发明了hlist。hlist有两大特点，一是它的链表头只需要一个指针，二是它的每一项都可以找到自己的前一节点，也就是说它不再循环，但仍是双向。令人不解的是，hlist的实现太绕了，比如它明明可以直接指向前一节点，却偏偏指向指针地址，还是前一节点中指向后一节点的指针地址。即使这种设计在实现时占便宜，但它理解上带来的不便已经远远

3、超过实现上带来的小小便利。   同hlist一样，klist也是为了适应某类特殊情形的要求。考虑一个被简化的情形，假设一些设备被链接在设备链表中，一个线程命令卸载某设备，即将其从设备链表中删除，但这时该设备正在使用中，这时就出现了冲突。当前可以设置临界区并加锁，但因为使用一个设备而锁住整个设备链表显然是不对的；又或者可以从设备本身做文章，让线程阻塞，这当然也可以。但我们上节了解了kref，就该知道linux对待这种情况的风格，给它一个引用计数kref，等计数为零就删除。klist就是这么干的，它把k

4、ref直接保存在了链表节点上。之前说到有线程要求删除设备，之前的使用仍存在，所以不能实际删除，但不应该有新的应用访问到该设备。klist就提供了一种让节点在链表上隐身的方法。下面还是来看实际代码吧。   klist的头文件是include/linux/klist.h，实现在lib/klist.c。[cpp] viewplaincopyprint?1.struct klist_node;  2.struct klist {  3.    spinlock_t      k_lock;  4.    s

5、truct list_head    k_list;  5.    void            (*get)(struct klist_node *);  6.    void            (*put)(struct klist_node *);  7.} __attribute__ ((aligned (4)));  8.  9.#define KLIST_INIT(_name, _get, _put)                     10.    { .k_lock   

6、= __SPIN_LOCK_UNLOCKED(_name.k_lock),         11.      .k_list   = LIST_HEAD_INIT(_name.k_list),           12.      .get      = _get,                       1.      .put      = _put, }  2.  3.#define DEFINE_KLIST(_name, _get, _put)                  

7、 4.    struct klist _name = KLIST_INIT(_name, _get, _put)  5.  6.extern void klist_init(struct klist *k, void (*get)(struct klist_node *),  7.               void (*put)(struct klist_node *));  8.  9.struct klist_node {  10.    void            *n_klist;

8、   /* never access directly */  11.    struct list_head    n_node;  12.    struct kref     n_ref;  13.};  可以看到，klist的链表头是structklist结构，链表节点是structklist_node结构。先看structklist，除了包含链表需要的k_list，还有用于加锁的k_lock。剩余的get()和put()函数是用于structklist_no