Linux内核klist链表分析
1、前言
在Linux内核的源码中，除了简洁的list链表外，内核还有klist链表，它是list链表的线程安全版本，在结构体中提供了整个链表的自旋锁，对链表节点查找、插入和删除等操作，都需要先获得这个自旋锁，klist的链表节点数据结构klist_node引入了引用计数器，只有当节点的的引用计数为0时，才允许该节点从klist链表中移除。
2、klist链表相关结构
内核源码中，klist相关的头文件是include/linux/klist.h，实现的文件是lib/klist.c中，接下来分析klist链表头和klist链表节点的定义：
首先是klist链表头的定义，如下：
struct klist {
spinlock_t k_lock;
struct list_head k_list;
void (*get)(struct klist_node *);
void (*put)(struct klist_node *);
} __attribute__ ((aligned (sizeof(void *))));
成员分析：
k_lock：链接节点操作所需要的自旋锁；
k_list：嵌入的双向链表list；
get：函数指针，用于链表内的节点增加引用计数；
put：函数指针，用于链表内的节点减少引用计数。
需要注意的是，该struct klist结构体是sizeof(void *)字节对齐，假如是4字节对齐的话，说明klist链表的实例地址的最低位是0，并且在klist实例中，地址的最低位具有其它用处。
接下来是klist链表中的节点结构定义，结构体名为struct klist_node，该定义如下：
struct klist_node {
void *n_klist; /* never access directly */
struct list_head n_node;
struct kref n_ref;
};
成员分析：
n_klist：用于指向klist链表头；
n_node：嵌入的双向链表list；
n_ref：klist链表节点的引用计数器。
需要注意的是，n_klist指针是用来指向链表头的，它的最低位用来表示该节点是否已被请求删除，如果已经被请求删除的话，在klist链表中遍历是看不到该节点的。
这两个结构体形成的一个简单链表结构如下所示：
3、klist链表实现
接下来对klist链表的相关操作进行简单分析：
#define KLIST_INIT(_name, _get, _put) \
{ .k_lock = __SPIN_LOCK_UNLOCKED(_name.k_lock), \
.k_list = LIST_HEAD_INIT(_name.k_list), \
.get = _get, \
.put = _put, } #define DEFINE_KLIST(_name, _get, _put) \
struct klist _name = KLIST_INIT(_name, _get, _put) /**
* klist_init - Initialize a klist structure.
* @k: The klist we're initializing.
* @get: The get function for the embedding object (NULL if none)
* @put: The put function for the embedding object (NULL if none)
*
* Initialises the klist structure. If the klist_node structures are
* going to be embedded in refcounted objects (necessary for safe
* deletion) then the get/put arguments are used to initialise
* functions that take and release references on the embedding
* objects.
*/
void klist_init(struct klist *k, void (*get)(struct klist_node *),
void (*put)(struct klist_node *))
{
INIT_LIST_HEAD(&k->k_list); //双向链表初始化
spin_lock_init(&k->k_lock); //自旋锁初始化
k->get = get;
k->put = put;
}
KLIST_INIT()宏用于对klist的链表头进行初始化，包括自旋锁以及嵌入的双向链表初始化，DEFINE_KLIST()宏则是用来定义一个klist，并调用KLIST_INIT()宏进行初始化，klist_init()则是使用函数的方式对klist进行初始化。
/*
* Use the lowest bit of n_klist to mark deleted nodes and exclude
* dead ones from iteration.
*/
#define KNODE_DEAD 1LU
#define KNODE_KLIST_MASK ~KNODE_DEAD static struct klist *knode_klist(struct klist_node *knode)
{
return (struct klist *)
((unsigned long)knode->n_klist & KNODE_KLIST_MASK);//将指针的最低位清0，并返回指针
} static bool knode_dead(struct klist_node *knode)
{
return (unsigned long)knode->n_klist & KNODE_DEAD;//判断最低位
} static void knode_set_klist(struct klist_node *knode, struct klist *klist)
{
knode->n_klist = klist;
/* no knode deserves to start its life dead */
WARN_ON(knode_dead(knode));
} static void knode_kill(struct klist_node *knode)
{
/* and no knode should die twice ever either, see we're very humane */
WARN_ON(knode_dead(knode));
*(unsigned long *)&knode->n_klist |= KNODE_DEAD;//将指针的最低位置1
}
上面4个函数是内部的静态函数，用来辅助klist的API接口实现，knode_klist()函数用于从knode中寻找klist链表头，knode_dead()函数用于检查该节点是否已被请求删除，knode_set_klist()函数用于设置节点的klist链表头，knode_kill()则用于请求删除节点。
klist中为什么要引入dead这个标识呢？当一个线程要让某个klist_node无效时，不能简单地从klist中删除，因为有可能有其它线程还在使用这个节点，因此只能减少klist_node的引用计数，由于其它线程也拥有这个klist_node的引用计数，所以节点还在klist中，遍历的时候将无法避开这个节点，但引入dead这个标识后，当这个标志位被设置后，遍历的时候可以进行dead标志位判断，然后有效地避开某些被申请删除的节点，当其它线程不引用该节点后，引用计数为0，该节点将会自动从klist链表中移除。
static void add_head(struct klist *k, struct klist_node *n)
{
spin_lock(&k->k_lock);
list_add(&n->n_node, &k->k_list);//在链表头后面插入节点
spin_unlock(&k->k_lock);
} static void add_tail(struct klist *k, struct klist_node *n)
{
spin_lock(&k->k_lock);
list_add_tail(&n->n_node, &k->k_list);//在链表头前面插入节点
spin_unlock(&k->k_lock);
} static void klist_node_init(struct klist *k, struct klist_node *n)
{
INIT_LIST_HEAD(&n->n_node);//链表初始化
kref_init(&n->n_ref);//引用计数初始化
knode_set_klist(n, k);//klist_node设置头节点
if (k->get)
k->get(n);
}
接下来又是3个静态函数，add_head()函数用于在链表头后插入节点，add_tail()用于在链表尾部插入节点，需要注意的是，在对链表节点的操作之前需要获得自旋锁，klist_node_init()函数用于初始化klist_node节点，包括内部list链表、引用计数器和链表头指针的初始化。
/**
* klist_add_head - Initialize a klist_node and add it to front.
* @n: node we're adding.
* @k: klist it's going on.
*/
void klist_add_head(struct klist_node *n, struct klist *k)
{
klist_node_init(k, n);
add_head(k, n);
} /**
* klist_add_tail - Initialize a klist_node and add it to back.
* @n: node we're adding.
* @k: klist it's going on.
*/
void klist_add_tail(struct klist_node *n, struct klist *k)
{
klist_node_init(k, n);
add_tail(k, n);
}
上面两个函数中，klist_add_head()函数用于将节点进行初始化并添加到klist链表头，klist_add_tail()函数将节点进行初始化后并添加到klist尾部。
/**
* klist_add_behind - Init a klist_node and add it after an existing node
* @n: node we're adding.
* @pos: node to put @n after
*/
void klist_add_behind(struct klist_node *n, struct klist_node *pos)
{
struct klist *k = knode_klist(pos); klist_node_init(k, n);
spin_lock(&k->k_lock);
list_add(&n->n_node, &pos->n_node);//在某个节点后插入klist_node节点
spin_unlock(&k->k_lock);
} /**
* klist_add_before - Init a klist_node and add it before an existing node
* @n: node we're adding.
* @pos: node to put @n after
*/
void klist_add_before(struct klist_node *n, struct klist_node *pos)
{
struct klist *k = knode_klist(pos); klist_node_init(k, n);
spin_lock(&k->k_lock);
list_add_tail(&n->n_node, &pos->n_node);//在某个节点前插入klist_node节点
spin_unlock(&k->k_lock);
}
上面两个函数中，klist_add_behind()用于将新节点初始化，然后将节点插入到pos节点后面，其原理就是把klist链表的pos节点当成链表头，然后调用list_add()插入节点，klist_add_before()函数是相同的原理，用于将新节点插入到pos节点前面。
接下来，继续分析klist遍历相关的内容：
struct klist_waiter {
struct list_head list;
struct klist_node *node;
struct task_struct *process;
int woken;
};
static DEFINE_SPINLOCK(klist_remove_lock);//定义klist_remove_lock自旋锁
static LIST_HEAD(klist_remove_waiters);//定义klist_remove_waiters链表
static void klist_release(struct kref *kref)
{
struct klist_waiter *waiter, *tmp;
struct klist_node *n = container_of(kref, struct klist_node, n_ref);/*根据节点中kref指针获取节点首地址*/
WARN_ON(!knode_dead(n));
list_del(&n->n_node);//将嵌入的双向链表节点删除
spin_lock(&klist_remove_lock);//上锁
list_for_each_entry_safe(waiter, tmp, &klist_remove_waiters, list) { //链表遍历
if (waiter->node != n)
continue;
list_del(&waiter->list);//将睡眠的进程移除
waiter->woken = ; //唤醒标志位
mb();
wake_up_process(waiter->process); //将进程唤醒
}
spin_unlock(&klist_remove_lock);
knode_set_klist(n, NULL);
}
static int klist_dec_and_del(struct klist_node *n)
{
return kref_put(&n->n_ref, klist_release);//klist_node节点引用计数减1操作
}
static void klist_put(struct klist_node *n, bool kill)
{
struct klist *k = knode_klist(n);//获取klist链表头
void (*put)(struct klist_node *) = k->put;//获取引用计数减少函数指针
spin_lock(&k->k_lock);//上锁
if (kill)
knode_kill(n);//请求删除节点
if (!klist_dec_and_del(n))//判断节点的引用计数是否为0，是将调用klist_release移除
put = NULL;
spin_unlock(&k->k_lock);
if (put)
put(n);//节点的引用计数减1操作
}
/**
* klist_del - Decrement the reference count of node and try to remove.
* @n: node we're deleting.
*/
void klist_del(struct klist_node *n)
{
klist_put(n, true);
}
在前面的klist_node链表节点中，可以知道链表节点引入了一个引用计数器，使用kref实现了节点的动态删除，当引用计数器的值为0时，就会调用klist_release()函数将节点进行脱离，klist_dec_and_del()函数是kref_put()函数的进一步封装，用于减少引用计数操作，klist_del()用于释放引用计数，该函数调用了内部函数klist_put()，该函数会调用knode_kill()将链表节点设置为已请求删除，调用klist_dec_and_del()减少引用计数，并且有可能会调用put()函数。
在上面代码中，还引入了一个新的结构struct klist_waiter，用于链表删除时请求线程阻塞，当有线程申请删除某节点时，但是节点的引用计数还不为0，所以只能请求删除节点的线程阻塞，使用struct klist_waiter将线程阻塞在链表klist_remove_waiters上，因此，可以发现，klist_release()函数在调用时，还需要将阻塞的线程进行唤醒。
/**
* klist_remove - Decrement the refcount of node and wait for it to go away.
* @n: node we're removing.
*/
void klist_remove(struct klist_node *n)
{
struct klist_waiter waiter; waiter.node = n;
waiter.process = current;//当前进程
waiter.woken = ;
spin_lock(&klist_remove_lock);
list_add(&waiter.list, &klist_remove_waiters);//将节点插入klist_remove_waiters链表
spin_unlock(&klist_remove_lock); klist_del(n);//减少引用计数并尝试移除klist_node节点 for (;;) {
set_current_state(TASK_UNINTERRUPTIBLE);//睡眠，中断不可唤醒
if (waiter.woken)//判断唤醒标志是否置位
break;
schedule();//调度
}
__set_current_state(TASK_RUNNING);//设置进程为运行状态
}
而klist_remove()函数不仅会减少引用计数操作，还会将一直阻塞到节点移除，该函数才是请求删除节点的线程需要调用的。
/**
* klist_node_attached - Say whether a node is bound to a list or not.
* @n: Node that we're testing.
*/
int klist_node_attached(struct klist_node *n)
{
return (n->n_klist != NULL);
}
klist_node_attached()函数用来判断链表节点是否还在链表上，是通过判断节点中的n_klist指针来实现的。
struct klist_iter {
struct klist *i_klist;
struct klist_node *i_cur;
};
extern void klist_iter_init(struct klist *k, struct klist_iter *i);
extern void klist_iter_init_node(struct klist *k, struct klist_iter *i,
struct klist_node *n);
extern void klist_iter_exit(struct klist_iter *i);
extern struct klist_node *klist_prev(struct klist_iter *i);
extern struct klist_node *klist_next(struct klist_iter *i);
接下来是链表遍历的实现方法，klist的遍历需要引入迭代器struct klist_iter，因为需要考虑到遍历过程中节点删除的情况，还要考虑如何忽略哪些已被请求删除的节点，该结构定义如上代码所示。
/**
* klist_iter_init_node - Initialize a klist_iter structure.
* @k: klist we're iterating.
* @i: klist_iter we're filling.
* @n: node to start with.
*
* Similar to klist_iter_init(), but starts the action off with @n,
* instead of with the list head.
*/
void klist_iter_init_node(struct klist *k, struct klist_iter *i,
struct klist_node *n)
{
i->i_klist = k; //klist链表头赋值
i->i_cur = NULL; //klist_node指针赋值NULL
if (n && kref_get_unless_zero(&n->n_ref))//引用计数加1(引用计数不为0),返回非零值
i->i_cur = n; //将klist_node的值赋值给迭代器
} /**
* klist_iter_init - Iniitalize a klist_iter structure.
* @k: klist we're iterating.
* @i: klist_iter structure we're filling.
*
* Similar to klist_iter_init_node(), but start with the list head.
*/
void klist_iter_init(struct klist *k, struct klist_iter *i)
{
klist_iter_init_node(k, i, NULL); //从klist链表头开始
}
在上面的代码中，klist_iter_init_node()函数用于初始化一个struct klist_iter迭代器，它是从某个链表节点开始遍历的，而不是链表头，而klist_iter_init()函数则是进一步封装，它是从链表头开始遍历。
/**
* klist_iter_exit - Finish a list iteration.
* @i: Iterator structure.
*
* Must be called when done iterating over list, as it decrements the
* refcount of the current node. Necessary in case iteration exited before
* the end of the list was reached, and always good form.
*/
void klist_iter_exit(struct klist_iter *i)
{
if (i->i_cur) {
klist_put(i->i_cur, false); //将遍历的节点引用计数减1操作
i->i_cur = NULL;
}
}
EXPORT_SYMBOL_GPL(klist_iter_exit); static struct klist_node *to_klist_node(struct list_head *n)
{
return container_of(n, struct klist_node, n_node);/*根据klist_node内的链表指针获取结构体首地址*/
}
上面代码中，klist_iter_exit()函数用于完成一个链表的迭代操作，完成链表的遍历后需要进行调用，to_klist_node()函数则是将klist_node结构体的首地址进行返回。
/**
* klist_prev - Ante up prev node in list.
* @i: Iterator structure.
*
* First grab list lock. Decrement the reference count of the previous
* node, if there was one. Grab the prev node, increment its reference
* count, drop the lock, and return that prev node.
*/
struct klist_node *klist_prev(struct klist_iter *i)
{
void (*put)(struct klist_node *) = i->i_klist->put; //获取klist的put函数指针
struct klist_node *last = i->i_cur; //当前klist_node节点赋值
struct klist_node *prev; spin_lock(&i->i_klist->k_lock); //上锁 if (last) { //节点不为NULL，从某节点开始操作
prev = to_klist_node(last->n_node.prev);/*根据前一个klist_node的list指针获取结构体首地址*/
if (!klist_dec_and_del(last)) //引用计数减1操作
put = NULL;
} else
prev = to_klist_node(i->i_klist->k_list.prev);//从链表头开始遍历，获取前节点的地址 i->i_cur = NULL;
while (prev != to_klist_node(&i->i_klist->k_list)) {
if (likely(!knode_dead(prev))) { //跳过dead节点
kref_get(&prev->n_ref); //引用计数加1
i->i_cur = prev;
break;
}
prev = to_klist_node(prev->n_node.prev);//迭代前一个节点
} spin_unlock(&i->i_klist->k_lock); if (put && last)
put(last);
return i->i_cur;
} /**
* klist_next - Ante up next node in list.
* @i: Iterator structure.
*
* First grab list lock. Decrement the reference count of the previous
* node, if there was one. Grab the next node, increment its reference
* count, drop the lock, and return that next node.
*/
struct klist_node *klist_next(struct klist_iter *i)
{
void (*put)(struct klist_node *) = i->i_klist->put;
struct klist_node *last = i->i_cur;
struct klist_node *next; spin_lock(&i->i_klist->k_lock); if (last) {
next = to_klist_node(last->n_node.next);
if (!klist_dec_and_del(last))
put = NULL;
} else
next = to_klist_node(i->i_klist->k_list.next); i->i_cur = NULL;
while (next != to_klist_node(&i->i_klist->k_list)) {
if (likely(!knode_dead(next))) {
kref_get(&next->n_ref);
i->i_cur = next;
break;
}
next = to_klist_node(next->n_node.next);
} spin_unlock(&i->i_klist->k_lock); if (put && last)
put(last);
return i->i_cur;
}
在上面的代码中，klist_prev()函数用于迭代到链表的前一个节点，klist_next()用于迭代到链表的下一个节点，由函数注释可以知道，函数首先要拿到锁，然后减少前一个节点的引用计数，然后迭代到下一个节点，增加它的引用计数，并且解锁，将节点进行返回。需要注意的地方有两点，第一点是：对单个节点的操作不需要加锁，但是对影响整个链表的操作需要加锁处理，因为当前线程可能会没有引用计数，所以需要加锁，让情况固定，保护链表和节点，第二点是：要忽略链表中已被请求删除的节点，在减少前一个节点的引用计数时，可能会把前一个节点删除。
以上就是klist链表的节点添加、删除和遍历的实现操作方法，由于klist是的list的线程安全版本，因此，需要考虑的东西很多，实现也比较复杂，klist链表主要运用在Linux内核的设备驱动模型中，它是为了适应动态变化的设备和驱动而专门设计的链表。
4、小结
本文主要对Linux内核中klist链表的定义和实现做了简要分析，包括其链表节点的添加、删除和链表遍历等基本实现进行简单说明。
参考：
《LINUX设备驱动程序（第三版）》
http://www.itboth.com/d/aEfmUv/linux
https://blog.csdn.net/qb_2008/article/details/6845854
https://www.linuxidc.com/Linux/2011-05/36116.htm
最新文章
- LeetCode: Largest Rectangle in Histogram(直方图最大面积)
- Knockout 官网翻译
- 利用Access-Control-Allow-Origin响应头解决跨域请求
- [翻译]使用Swift在Xcode中创建自定义控件
- istView的项移除
- lintcode:格雷编码
- 给jdk写注释系列之jdk1.6容器(2)-LinkedList源码解析
- c++类型转换Type Cast)
- validator验证
- 使用LVS+keepalived实现mysql负载均衡的实践和总结
- C++ 安全单例模式总结
- python3 第十一章 - 数据类型之str（字符串）
- 在mac os10.12上安装mysql5.7.18
- 解决ERROR 1130: Host '192.168.11.1' is not allowed to connect to this MySQL
- Gogs 部署安装（windows）
- js jquery 数组的合并 对象的合并
- 牛客网练习赛t2（线段树）
- eaeyui-combobox实现组合查询（即实现多个值得搜索）
- MybatisUtil的使用，便于产生SqlSession
- Carrierwave 如何配置合理的上传文件名（转自李华顺）