linux设备驱动之更强的链表klistWord文档格式.docx

linux设备驱动之更强的链表klistWord文档格式.docx

《linux设备驱动之更强的链表klistWord文档格式.docx》由会员分享，可在线阅读，更多相关《linux设备驱动之更强的链表klistWord文档格式.docx（16页珍藏版）》请在冰点文库上搜索。

（*put）（struct 

7.} 

__attribute__ 

（（aligned 

（4）））;

8. 

9.#define 

KLIST_INIT（_name, 

_get, 

_put） 

\ 

10. 

.k_lock 

= 

__SPIN_LOCK_UNLOCKED（_name.k_lock）, 

11. 

.k_list 

LIST_HEAD_INIT（_name.k_list）, 

12. 

.get 

13. 

.put 

_put, 

} 

14. 

15.#define 

DEFINE_KLIST（_name, 

16. 

_name 

17. 

18.extern 

klist_init（struct 

*k, 

*）, 

19. 

*））;

20. 

21.struct 

22. 

*n_klist;

/* 

never 

access 

directly 

*/ 

23. 

n_node;

24. 

kref 

n_ref;

25.};

可以看到，klist的链表头是structklist结构，链表节点是structklist_node结构。

先看structklist，除了包含链表需要的k_list，还有用于加锁的k_lock。

剩余的get（）和put（）函数是用于structklist_node嵌入在更大的结构中，这样在节点初始时调用get（），在节点删除时调用put（），以表示链表中存在对结构的引用。

再看structklist_node，除了链表需要的n_node，还有一个引用计数n_ref。

还有一个比较特殊的指针n_klist，n_klist是指向链表头structklist的，但它的第0位用来表示是否该节点已被请求删除，如果已被请求删除则在链表循环时是看不到这一节点的，循环函数将其略过。

现在你明白为什么非要在structklist的定义后加上__attribute__（（aligned（4）））。

不过说实话这样在x86下仍然不太保险，但linux选择了相信gcc，毕竟是多年的战友和兄弟了，相互知根知底。

看过这两个结构，想必大家已经较为清楚了，下面就来看看它们的实现。

1./* 

2. 

* 

Use 

the 

lowest 

bit 

of 

n_klist 

to 

mark 

deleted 

nodes 

and 

exclude 

dead 

ones 

from 

iteration. 

5.#define 

KNODE_DEAD 

1LU 

6.#define 

KNODE_KLIST_MASK 

~KNODE_DEAD 

7. 

8.static 

*knode_klist（struct 

*knode） 

9.{ 

return 

（struct 

*） 

（（unsigned 

long）knode->

&

KNODE_KLIST_MASK）;

12.} 

14.static 

bool 

knode_dead（struct 

15.{ 

（unsigned 

KNODE_DEAD;

17.} 

18. 

19.static 

knode_set_klist（struct 

*knode, 

*klist） 

20.{ 

21. 

knode->

klist;

no 

knode 

deserves 

start 

its 

life 

WARN_ON（knode_dead（knode））;

24.} 

25. 

26.static 

knode_kill（struct 

27.{ 

28. 

should 

die 

twice 

ever 

either, 

see 

we'

re 

very 

humane 

29. 

30. 

*（unsigned 

long 

*）&

|= 

31.} 

前面的四个函数都是内部静态函数，帮助API实现的。

knode_klist（）是从节点找到链表头。

knode_dead（）是检查该节点是否已被请求删除。

knode_set_klist设置节点的链表头。

knode_kill将该节点请求删除。

细心的话大家会发现这四个函数是对称的，而且都是操作节点的内部函数。

1.void 

*）） 

3.{ 

INIT_LIST_HEAD（&

k->

k_list）;

spin_lock_init（&

k_lock）;

get 

get;

put 

put;

8.} 

klist_init，初始化klist。

1.static 

add_head（struct 

*n） 

2.{ 

spin_lock（&

list_add（&

n->

n_node, 

spin_unlock（&

6.} 

add_tail（struct 

list_add_tail（&

13.} 

15.static 

klist_node_init（struct 

16.{ 

n_node）;

kref_init（&

n_ref）;

knode_set_klist（n, 

k）;

if 

（k->

get） 

get（n）;

22.} 

又是三个内部函数，add_head（）将节点加入链表头，add_tail（）将节点加入链表尾，klist_node_init（）是初始化节点。

注意在节点的引用计数初始化时，因为引用计数变为1，所以也要调用相应的get（）函数。

klist_add_head（struct 

*n, 

*k） 

klist_node_init（k, 

n）;

add_head（k, 

5.} 

7.void 

klist_add_tail（struct 

8.{ 

9. 

add_tail（k, 

11.} 

klist_add_head（）将节点初始化，并加入链表头。

klist_add_tail（）将节点初始化，并加入链表尾。

它们正是用上面的三个内部函数实现的，可见linux内核中对函数复用有很强的执念，其实这里add_tail和add_head是不用的，纵观整个文件，也只有klist_add_head（）和klist_add_tail（）对它们进行了调用。

klist_add_after（struct 

*pos） 

*k 

knode_klist（pos）;

pos->

9.} 

11.void 

klist_add_before（struct 

12.{ 

15. 

19.} 

klist_add_after（）将节点加到指定节点后面。

klist_add_before（）将节点加到指定节点前面。

这两个函数都是对外提供的API。

在list_head中都没有看到有这种API，所以说需求决定了接口。

虽说只有一步之遥，klist也不愿让外界介入它的内部实现。

之前出现的API都太常见了，既没有使用引用计数，又没有跳过请求删除的节点。

所以klist的亮点在下面，klist链表的遍历。

klist_iter 

*i_klist;

*i_cur;

4.};

7.extern 

klist_iter_init（struct 

*i）;

8.extern 

klist_iter_init_node（struct 

*i, 

*n）;

10.extern 

klist_iter_exit（struct 

11.extern 

*klist_next（struct 

以上就是链表遍历需要的辅助结构structklist_iter，和遍历用到的四个函数。

klist_waiter 

list;

*node;

task_struct 

*process;

int 

woken;

6.};

DEFINE_SPINLOCK（klist_remove_lock）;

9.static 

LIST_HEAD（klist_remove_waiters）;

11.static 

klist_release（struct 

*kref） 

*waiter, 

*tmp;

*n 

container_of（kref, 

klist_node, 

WARN_ON（!

knode_dead（n））;

list_del（&

klist_remove_lock）;

list_for_each_entry_safe（waiter, 

tmp, 

klist_remove_waiters, 

list） 

（waiter->

node 

!

n） 

continue;

waiter->

woken 

1;

mb（）;

wake_up_process（waiter->

process）;

26. 

list）;

27. 

NULL）;

30.} 

31. 

32.static 

klist_dec_and_del（struct 

33.{ 

34. 

kref_put（&

n_ref, 

klist_release）;

35.} 

36. 

37.static 

klist_put（struct 

kill） 

38.{ 

39. 

knode_klist（n）;

40. 

41. 

42. 

43. 

（kill） 

44. 

knode_kill（n）;

45. 

（!

klist_dec_and_del（n）） 

46. 

NULL;

47. 

48. 

（put） 

49. 

put（n）;

50.} 

51. 

52./** 

53. 

klist_del 

- 

Decrement 

reference 

count 

try 

remove. 

54. 

@n:

deleting. 

55. 

56.void 

klist_del（struct 

57.{ 

58. 

klist_put（n, 

true）;

59.} 

以上的内容乍一看很难理解，其实都是klist实现必须的。

因为使用kref动态删除，自然需要一个计数降为零时调用的函数klist_release。

klist_dec_and_del（）就是对kref_put（）的包装，起到减少节点引用计数的功能。

至于为什么会出现一个新的结构structklist_waiter，也很简单。

之前说有线程申请删除某节点，但节点的引用计数仍在，所以只能把请求删除的线程阻塞，就是用structklist_waiter阻塞在klist_remove_waiters上。

所以在klist_release（）调用时还要将阻塞的线程唤醒。

knode_kill（）将节点设为已请求删除。

而且还会调用put（）函数。

释放引用计数是调用klist_del（），它通过内部函数klist_put（）完成所需操作：

用knode_kill（）设置节点为已请求删除，用klist_dec_and_del（）释放引用，调用可能的put（）函数。

1./** 

klist_remove 

refcount 

wait 

for 

it 

go 

away. 

removing. 

5.void 

klist_remove（struct 

6.{ 

waiter;

waiter.node 

n;

waiter.process 

current;

waiter.woken 

0;

waiter.list, 

klist_remove_waiters）;

klist_del（n）;

（;

;

） 

set_current_state（TASK_UNINTERRUPTIBLE）;

（waiter.woken） 

break;

schedule（）;

__set_current_state（TASK_RUNNING）;

25.} 

klist_remove（）不但会调用klist_del（）减少引用计数，还会一直阻塞到节点被删除。

这个函数才是请求删除节点的线程应该调用的。

1.int 

klist_node_attached（struct 

（n->

4.} 

klist_node_attached（）检查节点是否被包含在某链表中。

以上是klist的链表初始化，节点加入，节点删除函数。

下面是klist链表遍历函数。

[cpp