概述

??? klist是list的線程安全版本，他提供了整個鏈表的自旋鎖，查找鏈表節點，對鏈表節點的插入和刪除操作都要獲得這個自旋鎖。klist的節點數據結構是klist_node,klist_node引入引用計數，只有點引用計數減到0時才允許該node從鏈表中移除。當一個內核線程要移除一個node，必須要等待到node的引用計數釋放，在此期間線程處于休眠狀態，為了方便線程等待，klist引入等待移除節點者結構體klist_waiter，klist-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，并插入鏈表，插入鏈表后，引用計數為1

klist_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()函數把當前迭代器向后移動，并返回移動后的node，klist_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 we're 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_lock，klist_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中。

總結

以上是生活随笔為你收集整理的linux内核源代码分析----内核基础设施之klist的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。