新星市网站建设_网站建设公司_服务器部署_seo优化

klist链表

1. 概述

klist是 Linux 内核中基于list_head扩展的链表结构，提供了引用计数和线程安全的遍历机制。

1.1 设计目的

klist的设计目标是解决以下问题：

1. 安全遍历：允许在遍历过程中安全地修改链表（插入、删除节点）
2. 引用计数：通过kref机制管理节点的生命周期
3. 延迟删除：节点被标记删除后，只有在引用计数为 0 时才真正移除
4. 线程安全：使用自旋锁保护链表操作

1.2 核心特性

• 基于list_head的双向循环链表
• 每个节点包含引用计数（kref）
• 支持在遍历过程中安全删除节点
• 提供get/put回调函数用于管理嵌入对象的引用计数

2. 数据结构定义

klist它表示的是一个对象的集合，本质上是一个带锁，带引用保护的双向链表。

structklist{spinlock_tk_lock;// 保护链表的自旋锁structlist_headk_list;// 实际的链表头void(*get)(structklist_node*);// 获取节点时的回调void(*put)(structklist_node*);// 释放节点时的回调}__attribute__((aligned(sizeof(void*))));

klist_node被挂到klist中的“某个对象”，是链表里的一个成员。

structklist_node{void*n_klist;// 指向所属的 klist（低位用作删除标记）structlist_headn_node;// 链表节点，用于链入链表structkrefn_ref;// 引用计数，当计数为0时节点被真正的删除};

klist_iter用来表示一次klist遍历过程的状态上下文

structklist_iter{structklist*i_klist;// 正在遍历的 kliststructklist_node*i_cur;// 当前所在的节点};

klist_waiter用来等待某个节点引用计数归0

structklist_waiter{structlist_headlist;/* 链表节点，用于插入到klist_remove_waiters全局链表 */structklist_node*node;/* 等待的节点 */structtask_struct*process;/* 保存当前运行的进程，用于后续被唤醒 */intwoken;};

3. 核心操作函数源码分析

3.1 初始化

klist_init初始化整个klist容器，get和put是获取和释放节点时的回调函数。

voidklist_init(structklist*k,void(*get)(structklist_node*),void(*put)(structklist_node*)){INIT_LIST_HEAD(&k->k_list);spin_lock_init(&k->k_lock);k->get=get;k->put=put;}

初始化klist某个节点，它会初始化该对象的kref->refcount引用计数为1，然后将klist_node绑定到指定的klist，并且如果get存在的话则触发回调函数。

staticvoidklist_node_init(structklist*k,structklist_node*n){INIT_LIST_HEAD(&n->n_node);kref_init(&n->n_ref);knode_set_klist(n,k);if(k->get)k->get(n);}

3.2 添加节点

klist_add_head在链表头部添加节点，实现调用klist_node_init初始化改节点，然后调用add_head将其添加到链表头。

voidklist_add_head(structklist_node*n,structklist*k){klist_node_init(k,n);add_head(k,n);}

klist_add_tail在链表尾部添加节点，逻辑和klist_add_head一样，只是节点插入的位置不一样。

voidklist_add_tail(structklist_node*n,structklist*k){klist_node_init(k,n);add_tail(k,n);}

klist_add_behind/klist_add_before在指定节点后/前添加节点，逻辑也和上面一样，只是节点插入的位置不一样。

voidklist_add_behind(structklist_node*n,structklist_node*pos){structklist*k=knode_klist(pos);klist_node_init(k,n);spin_lock(&k->k_lock);list_add(&n->n_node,&pos->n_node);spin_unlock(&k->k_lock);}voidklist_add_before(structklist_node*n,structklist_node*pos){structklist*k=knode_klist(pos);klist_node_init(k,n);spin_lock(&k->k_lock);list_add_tail(&n->n_node,&pos->n_node);spin_unlock(&k->k_lock);}

3.3 删除节点

klist_del标记节点为删除状态并递减引用计数，他不会立即从链表中移除节点，只是标记节点为删除状态（设置KNODE_DEAD标志），递减引用计数，当计数为 0 时才真正删除，knode_kill函数核心作用是将knode所绑定n_klist指针设置为KNODE_DEAD。klist_dec_and_del函数内部会递减链表节点的引用计数，当计数到0时会触发klist_release函数的调用。

voidklist_del(structklist_node*n){klist_put(n,true);}staticvoidklist_put(structklist_node*n,bool kill){structklist*k=knode_klist(n);/* 获取所属的klist */void(*put)(structklist_node*)=k->put;spin_lock(&k->k_lock);if(kill)knode_kill(n);if(!klist_dec_and_del(n))put=NULL;spin_unlock(&k->k_lock);if(put)put(n);/* 如果有put函数，则触发 */}

klist_release函数从klist中删除指定的klist_node节点，然后唤醒对应的等待进程，klist_remove_waiters是一个全局链表，保存所有正在等待某个klist_node彻底释放的klist_waiter，当对接节点被释放时就换唤醒对应klist_waiter保存的等待进程。

staticvoidklist_release(structkref*kref){structklist_waiter*waiter,*tmp;/* 找到对应的klist_node节点 */structklist_node*n=container_of(kref,structklist_node,n_ref);WARN_ON(!knode_dead(n));list_del(&n->n_node);/* 删除链表节点 */spin_lock(&klist_remove_lock);/* 找到等待当前klist_node的waiter*/list_for_each_entry_safe(waiter,tmp,&klist_remove_waiters,list){if(waiter->node!=n)continue;/* 将该waiter节点从waiter链表中删除，然后唤醒对应的等待进程 */list_del(&waiter->list);waiter->woken=1;mb();wake_up_process(waiter->process);}spin_unlock(&klist_remove_lock);/* 将已删除的kist_node的绑定的n_klist设置为NULL */knode_set_klist(n,NULL);}

klist_remove删除节点并等待其真正被移除，调用klist_del标记删除，阻塞等待直到节点引用计数为0并被真正移除，适用于需要确保节点完全移除的场景。

voidklist_remove(structklist_node*n){structklist_waiterwaiter;waiter.node=n;/* 保存当前要删除的节点 */waiter.process=current;/* 保存当前运行的进程 */waiter.woken=0;/* 将klist_waiter节点插入到全局等待链表 */spin_lock(&klist_remove_lock);list_add(&waiter.list,&klist_remove_waiters);spin_unlock(&klist_remove_lock);klist_del(n);/* 引用计数-1 *//* 让出CPU，当节点被删除时会被唤醒 */for(;;){set_current_state(TASK_UNINTERRUPTIBLE);if(waiter.woken)break;schedule();}/* 恢复运行态 */__set_current_state(TASK_RUNNING);}

3.4 遍历操作

klist_iter_init用于初始化遍历器，将i_klist指向k，因为还未开始遍历，c_cur设置为NULL。

voidklist_iter_init(structklist*k,structklist_iter*i){klist_iter_init_node(k,i,NULL);}

klist_iter_init_node初始化遍历器，从指定节点开始遍历

voidklist_iter_init_node(structklist*k,structklist_iter*i,structklist_node*n){i->i_klist=k;i->i_cur=NULL;/* 引用计数不为0，则增加节点的引用计数，遍历器的当前遍历节点指向n */if(n&&kref_get_unless_zero(&n->n_ref))i->i_cur=n;}

klist_next获取下一个节点，to_klist_node函数通过链表成员找到对应的klist_node节点。通过调用knode_dead来检查节点是否被标记为了KNODE_DEAD，如果是则遍历器跳过该节点，如果不是则返回该节点。klist_prev获取前一个节点（实现机制类似klist_next）。

structklist_node*klist_next(structklist_iter*i){void(*put)(structklist_node*)=i->i_klist->put;structklist_node*last=i->i_cur;structklist_node*next;spin_lock(&i->i_klist->k_lock);if(last){/* 找到下一个klist_node节点 */next=to_klist_node(last->n_node.next);if(!klist_dec_and_del(last))/* 引用计数-1 */put=NULL;/* 对象仍在使用 */}else/* 当遍历器没有当前节点last时，从链表头获取第一个节点 */next=to_klist_node(i->i_klist->k_list.next);i->i_cur=NULL;/* 遍历到链表头则循环终止*/while(next!=to_klist_node(&i->i_klist->k_list)){/* 节点被标记了KNODE_DEAD时条件不成立 */if(likely(!knode_dead(next))){/* 引用计数+1，返回该节点 */kref_get(&next->n_ref);i->i_cur=next;break;}/* 找到下一个klist_node节点 */next=to_klist_node(next->n_node.next);}spin_unlock(&i->i_klist->k_lock);/* 如果put存在则对上一个节点调用put */if(put&&last)put(last);returni->i_cur;}

klist_iter_exit结束遍历，释放当前节点的引用计数，必须调用此函数来正确释放引用计数。

voidklist_iter_exit(structklist_iter*i){if(i->i_cur){/* 内部会递减该节点的引用计数 */klist_put(i->i_cur,false);i->i_cur=NULL;}}

3.5 查询操作

klist_node_attached检查节点是否已附加到某个klist

intklist_node_attached(structklist_node*n){return(n->n_klist!=NULL);}