个人备案域名可以做哪些网站,长沙招聘网最新招聘信息网,扬中论坛网官网,滕州建网站概述klist是list的线程安全版本#xff0c;他提供了整个链表的自旋锁#xff0c;查找链表节点#xff0c;对链表节点的插入和删除操作都要获得这个自旋锁。klist的节点数据结构是klist_node,klist_node引入引用计数#xff0c;只有点引用计数减到0时才允许该node从链表中移…概述klist是list的线程安全版本他提供了整个链表的自旋锁查找链表节点对链表节点的插入和删除操作都要获得这个自旋锁。klist的节点数据结构是klist_node,klist_node引入引用计数只有点引用计数减到0时才允许该node从链表中移除。当一个内核线程要移除一个node必须要等待到node的引用计数释放在此期间线程处于休眠状态为了方便线程等待klist引入等待移除节点者结构体klist_waiterklist-waiter组成klist_remove_waiters内核全局变量链表为保护klist_remove_waiters线程安全引入klist_remove_lock内核全局变量自旋锁。为方便遍历klist引入了迭代器klist_iter。其整体结构图如下 没有找到一个方便的画数据结构的工具图有空添加 用法定义klist常规定义struct klist myklist;
klist_init(myklist,get,put);便捷宏方式定义DEFINE_KLIST(myklist,get,put);//定义一个myklist并初始化插入节点struct klist_node mynode;
klist_add_tail(mynode,mylist);klist_add_xxx函数初始化node并插入链表插入链表后引用计数为1klist_add_tail向后插入klist_add_head向前插入kilst_add_after在某个节点的后面插入klist_add_before在某个节点的前面插入。删除节点klist_del(mynode);klist_del调用klist-put,减少引用计数并设dead标记当应用计数到0时自动调用klist_release,把节点从klist中删除。klist_remove(mynode);klist_remove把当前线程加入等待移除链表减少引用计数如果有其他内核线程占用引用计数把当前线程休眠。
推荐Linux内核源代码分析工具[ 凡是尝试做过内核分析的人都知道Linux的内核组织结构虽然非常有条理但是它毕竟是众人合作的结果在阅读代码的时候要将各个部分结合起来确实是件非常困难的事遍历klist klist没有像list一样定义一系列的list_for_each_xxx宏。klist提供专门的迭代器结构提klist_iter遍历前首先要初始化迭代器 klist_next()函数把当前迭代器向后移动并返回移动后的nodeklist_iter_init()klist_iter_init_node()都是迭代器初始化函数前者把迭代器当前位置设置为NULL,klist_next()自动从第一个node开始后者可以指定当前node迭代器指向node时会增加node的引用计数当迭代器不用时必须调用klist_iter_exit退出迭代器释放当前node的引用计数。分析klist_node有个dead字段联合在n_klist指针中n_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 (4)));4字节对齐意味着klist实例的地址低两位总是0所以这个低2位刚好可以作为其他用处对该指针解引用前只须与掉这2位来看源码#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);//与掉低2位
}static bool knode_dead(struct klist_node *knode)
{return (unsigned long)knode-n_klist KNODE_DEAD; //根据低2位判断
}那么为什么要引入这个dead标识呢如果一个内核线程要让某个node无效不能简单的从klist中把node摘下来只能减少node的引用计数但是由于其他内核线程也拥有该node的引用计数所以节点还是在klist链中遍历节点等操作时无法避开该node。引入这个标识后只要设置这个标识尽管该node还在klist链上但是迭代操作的时候通过这个标识避开dead的节点。这样在该节点上不会有新的操作通过链表遍历也无法获取到该节点当其他内核线程不引用该node后该node自动从klist链中移除。所以dead的作用是禁止再使用该node但是已经被人家在用了还是继续可以再用。调用klist_del()会标示该node为dead。我们来看迭代器移动操作函数klist_next()/*** 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);//如果迭代器当前指向一个nodeif (!klist_dec_and_del(last)) //如果引用计数减到0会调用put函数put NULL;} else //如果迭代器当前指向null,返回首个nodenext 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))) { //跳过dead的节点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是怎么迫使remove某个node的线程休眠的又是怎么唤醒的为了方便进程管理引入了 klist_waiter结构如下:struct klist_waiter {struct list_head list;struct klist_node *node;//等待删除的nodestruct task_struct *process;//进程或者线程指针int woken;//唤醒标记
};来看使线程进入休眠的代码,klist_remove函数/*** klist_remove - Decrement the refcount of node and wait for it to go away.* n: node were removing.*/
void klist_remove(struct klist_node *n)
{struct klist_waiter waiter; //创建一个waiterwaiter.node n;waiter.process current;waiter.woken 0;spin_lock(klist_remove_lock); //锁住klist_remove_lockklist_remove_lock专门是用来保护 //klist_remove_waiters的list_add(waiter.list, klist_remove_waiters);//把waiter加入到klist_remove_waiters中//这里把一个局部变量加入到一个全局的链表结构中//会不会引起内存越界后续讨论spin_unlock(klist_remove_lock);klist_del(n); //减小引用计数并判死刑for (;;) {set_current_state(TASK_UNINTERRUPTIBLE); //设置进程进入休眠状态if (waiter.woken)break;schedule(); //调度进程时当前进程进入休眠状态}__set_current_state(TASK_RUNNING);
}klist_del函数调用klist_put调用klist_dec_and_del调用kref_put,kref_put当引用计数减到0时回调到klist_release函数klist_release会释放等待者。进程的休眠是klist_remove和klist_release作用的结果我们来看klist_release的源码static void klist_release(struct kref *kref)
{struct klist_waiter *waiter, *tmp;struct klist_node *n container_of(kref, struct klist_node, n_ref);WARN_ON(!knode_dead(n));//要释放的节点一定是被判死刑的节点list_del(n-n_node); //把node从klist移除spin_lock(klist_remove_lock);//保护klist_remove_waiters,
/*遍历klist_remove_waiter*/list_for_each_entry_safe(waiter, tmp, klist_remove_waiters, list) {if (waiter-node ! n)continue;waiter-woken 1;//如果发现有等待该node的等待着设唤醒标示mb();wake_up_process(waiter-process);//唤醒该进程list_del(waiter-list);//把waiter结构体从klist_remove_waiters,移除}spin_unlock(klist_remove_lock);knode_set_klist(n, NULL);
}klist_remove函数把局部变量加入到全局链表中但是由于klist_remove会使线程休眠它返回前总是由klist_release把waiter从klist_remove_waiters移走所以不会导致崩溃。其实klist_remove_waiters的链表节点实际都是一些内核栈中的waiter结构这些线程都休眠在klist_remove中。
