[十月往昔]——Linux内核中的list.h浅谈

青旅半醒 2022-05-16 08:10 189阅读 0赞

为什么要叫做“十月往昔”呢，是为了纪念我的原博客。

不知道为什么，突然想来一个新的开始——而那个博客存活至今刚好十个月，也有十个月里的文档。

十月往昔，总有一些觉得珍贵的，所以搬迁到这里来。

而这篇文章是在09.04.10里写的。

终归是一家之谈。

Jason Lee

————————————–cut-line

### **/\*-------------------------------**    ###

### **include/linux/list.h -2.6.29** ###

**\*/**

该文件包含：

1\#ifndef \_LINUX\_LIST\_H 2\#define \_LINUX\_LIST\_H 3 4\#include <linux/stddef.h> 5\#include <linux/poison.h> 6\#include <linux/prefetch.h> 7\#include <asm/system.h>

链表的初始化

19struct list\_head \{ 20 struct list\_head \*next, \*prev; 21\}; 22 23\#define LIST\_HEAD\_INIT(name) \{ &(name), &(name) \} 24 25\#define LIST\_HEAD(name) / 26 struct list\_head name = LIST\_HEAD\_INIT(name) 27 28static inline void INIT\_LIST\_HEAD(struct list\_head \*list) 29\{ 30 list->next = list; 31 list->prev = list; 32\}

19-21 行定义了一个list\_head 结构，只有两个指向list\_head 结构的指针，一个next ，一个prev ，作用显而易见。

23 行的宏LIST\_HEAD\_INIT(name) 与25 行的宏LIST\_HEAD(name) 组合进行链表的初始化，即next 和prev 都指向自身。

25 行的静态内联函数INIT\_LIST\_HEAD(struct list\_head \*list) 同样是用来初始化链表，效果同上述一点。GNU 下的C 语言对C 进行了扩充，不再是ANSI C ，它里面增添了很多C++ 的特性，所以对内核进行编译只能选用相应的GCC 。

INIT\_LIST\_HEAD 在有的文献中是以宏的形式出现：

\#define INIT\_LIST\_HEAD(ptr) do \{ / (ptr)->next = (ptr); (ptr)->prev = (ptr); / \} while (0)

链表的插入

34/\* 35 \* Insert a new entry between two known consecutive entries. 36 \* 37 \* This is only for internal list manipulation where we know 38 \* the prev/next entries already! 39 \*/ 40\#ifndef CONFIG\_DEBUG\_LIST 41static inline void \_\_list\_add(struct list\_head \*new, 42 struct list\_head \*prev, 43 struct list\_head \*next) 44\{ 45 next->prev = new; 46 new->next = next; 47 new->prev = prev; 48 prev->next = new; 49\} 50\#else 51extern void \_\_list\_add(struct list\_head \*new, 52 struct list\_head \*prev, 53 struct list\_head \*next); 54\#endif

这段程序在两个已知的节点中间插入一个新节点。这里选择的是条件编译，如果没有对CONFIG\_DEBUG\_LIST 进行宏定义，则定义了\_\_list\_add 这个静态内联函数，便于以下两个函数使用。

56/\*\* 57 \* list\_add - add a new entry 58 \* @new: new entry to be added 59 \* @head: list head to add it after 60 \* 61 \* Insert a new entry after the specified head. 62 \* This is good for implementing stacks. 63 \*/ 64static inline void list\_add(struct list\_head \*new, struct list\_head \*head) 65\{ 66 \_\_list\_add(new, head, head->next); 67\}

该函数在指定的head 节点后面插入一个新节点new 。

70/\*\* 71 \* list\_add\_tail - add a new entry 72 \* @new: new entry to be added 73 \* @head: list head to add it before 74 \* 75 \* Insert a new entry before the specified head. 76 \* This is useful for implementing queues. 77 \*/ 78static inline void list\_add\_tail(struct list\_head \*new, struct list\_head \*head) 79\{ 80 \_\_list\_add(new, head->prev, head); 81\}

该函数将一个节点new 插在指定的节点head 之前。

链表的删除

83/\* 84 \* Delete a list entry by making the prev/next entries 85 \* point to each other. 86 \* 87 \* This is only for internal list manipulation where we know 88 \* the prev/next entries already! 89 \*/ 90static inline void \_\_list\_del(struct list\_head \* prev, struct list\_head \* next) 91\{ 92 next->prev = prev; 93 prev->next = next; 94\}

该函数通过设置prev 和next 指针指向彼此，实现了删除二者之间节点的功能。但是这里我有个疑惑，删除的指针的释放在哪里实现。

96/\*\* 97 \* list\_del - deletes entry from list. 98 \* @entry: the element to delete from the list. 99 \* Note: list\_empty() on entry does not return true after this, the entry is 100 \* in an undefined state. 101 \*/ 102\#ifndef CONFIG\_DEBUG\_LIST 103static inline void list\_del(struct list\_head \*entry) 104\{ 105 \_\_list\_del(entry->prev, entry->next); 106 entry->next = LIST\_POISON1; 107 entry->prev = LIST\_POISON2; 108\} 109\#else 110extern void list\_del(struct list\_head \*entry); 111\#endif

该函数通过调用上面的内联函数实现节点的删除，这里的LIST\_POISON1 和LIST\_POISON2 是在linux / poison . h 定义的。此处仍然是条件编译。

链表节点的置换

113/\*\* 114 \* list\_replace - replace old entry by new one 115 \* @old : the element to be replaced 116 \* @new : the new element to insert 117 \* 118 \* If @old was empty, it will be overwritten. 119 \*/ 120static inline void list\_replace(struct list\_head \*old, 121 struct list\_head \*new) 122\{ 123 new->next = old->next; 124 new->next->prev = new; 125 new->prev = old->prev; 126 new->prev->next = new; 127\} 128 129static inline void list\_replace\_init(struct list\_head \*old, 130 struct list\_head \*new) 131\{ 132 list\_replace(old, new); 133 INIT\_LIST\_HEAD(old); 134\}

静态内联函数list\_replace 接受两个参数：old 和new ，并通过new 替换old 。而list\_replace\_init 函数则是通过调用list\_replace 进行替换，之后调用INIT\_LIST\_HEAD 对被替换的old 进行链表初始化。

链表的移动

146/\*\* 147 \* list\_move - delete from one list and add as another’s head 148 \* @list: the entry to move 149 \* @head: the head that will precede our entry 150 \*/ 151static inline void list\_move(struct list\_head \*list, struct list\_head \*head) 152\{ 153 \_\_list\_del(list->prev, list->next); 154 list\_add(list, head); 155\}

List\_move 函数接受两个参数，第一个参数list 为想要移动的节点指针，第二个参数为目的地节点指针。该函数通过调用\_\_list\_del 函数实现list 节点的prev 和next 两个指针互指实现删除list 节点的效果，并且调用list\_add 将list 节点插入到head 之后。

157/\*\* 158 \* list\_move\_tail - delete from one list and add as another’s tail 159 \* @list: the entry to move 160 \* @head: the head that will follow our entry 161 \*/ 162static inline void list\_move\_tail(struct list\_head \*list, 163 struct list\_head \*head) 164\{ 165 \_\_list\_del(list->prev, list->next); 166 list\_add\_tail(list, head); 167\}

List\_move\_tail 函数将指定节点移到指定链表的尾部，成为尾节点。并且由于链表是循环的，所以移动的节点指向该链表head 节点。具体实现是通过目标节点的prev 和next 互指实现从原始链表中删除list 节点，之后通过调用list\_add\_tail 将list 节点插入到以head 为表首的链表尾部。

判断节点是否为链表的最后一个

169/\*\* 170 \* list\_is\_last - tests whether @list is the last entry in list @head 171 \* @list: the entry to test 172 \* @head: the head of the list 173 \*/ 174static inline int list\_is\_last(const struct list\_head \*list, 175 const struct list\_head \*head) 176\{ 177 return list->next == head; 178\}

通过判断节点的next 指向是否为表首来确定是否为last 。

判断链表是否为空

180/\*\* 181 \* list\_empty - tests whether a list is empty 182 \* @head: the list to test. 183 \*/ 184static inline int list\_empty(const struct list\_head \*head) 185\{ 186 return head->next == head; 187\}

通过判断head 节点是否指向自身来判断链表是否为空。

189/\*\* 190 \* list\_empty\_careful - tests whether a list is empty and not being modified 191 \* @head: the list to test 192 \* 193 \* Description: 194 \* tests whether a list is empty \_and\_ checks that no other CPU might be 195 \* in the process of modifying either member (next or prev) 196 \* 197 \* NOTE: using list\_empty\_careful() without synchronization 198 \* can only be safe if the only activity that can happen 199 \* to the list entry is list\_del\_init(). Eg. it cannot be used 200 \* if another CPU could re-list\_add() it. 201 \*/ 202static inline int list\_empty\_careful(const struct list\_head \*head) 203\{ 204 struct list\_head \*next = head->next; 205 return (next == head) && (next == head->prev); 206\}

此处函数的作用并不十分理解，对于绿色注释说明部分的Description 和NOTE 部分也是一知半解。单纯地翻一下NOTE 部分：如果没有经过同步化处理，那么如果要达到安全地使用list\_empty\_careful 这个函数必须限定当前能对指定节点发生的操作仅仅为list\_del\_init() ，比如当一个CPU 对它进行add 操作的时候不能使用该函数。

该函数能达到的效果是检查链表是否为空，并且检测是否有CPU 在修改当前指定节点的prev 和next 指针。

这里引用一段解释，来自杨沙洲：

“ **Linux** **链表另行提供了一个** **list\_empty\_careful()** **宏，它同时判断头指针的** **next** **和** **prev** **，仅当两者都指向自己时才返回真。这主要是为了应付另一个** **cpu** **正在处理同一个链表而造成** **next** **、** **prev** **不一致的情况。但代码注释也承认，这一安全保障能力有限：除非其他** **cpu** **的链表操作只有** **list\_del\_init()** **，否则仍然不能保证安全，也就是说，还是需要加锁保护。** **”**

判断链表是否只有唯一的一个节点

208/\*\* 209 \* list\_is\_singular - tests whether a list has just one entry. 210 \* @head: the list to test. 211 \*/ 212static inline int list\_is\_singular(const struct list\_head \*head) 213\{ 214 return !list\_empty(head) && (head->next == head->prev); 215\}

空表并不是一个节点都没有，唯一的节点也不是指只有一个节点，具体看函数代码我们便可以了解。当一个节点指针被执行LIST\_HEAD 了以后，它的prev 和next 指针都指向自身，这便称为空表；而如果它的prev 和next 指针都指向仅有的第二个节点，那么它便称为仅有一个节点。

链表的切割

217static inline void \_\_list\_cut\_position(struct list\_head \*list, 218 struct list\_head \*head, struct list\_head \*entry) 219\{ 220 struct list\_head \*new\_first = entry->next; 221 list->next = head->next; 222 list->next->prev = list; 223 list->prev = entry; 224 entry->next = list; 225 head->next = new\_first; 226 new\_first->prev = head; 227\} 228 229/\*\* 230 \* list\_cut\_position - cut a list into two 231 \* @list: a new list to add all removed entries 232 \* @head: a list with entries 233 \* @entry: an entry within head, could be the head itself 234 \* and if so we won’t cut the list 235 \* 236 \* This helper moves the initial part of @head, up to and 237 \* including @entry, from @head to @list. You should 238 \* pass on @entry an element you know is on @head. @list 239 \* should be an empty list or a list you do not care about 240 \* losing its data. 241 \* 242 \*/ 243static inline void list\_cut\_position(struct list\_head \*list, 244 struct list\_head \*head, struct list\_head \*entry) 245\{ 246 if (list\_empty(head)) 247 return; 248 if (list\_is\_singular(head) && 249 (head->next != entry && head != entry)) 250 return; 251 if (entry == head) 252 INIT\_LIST\_HEAD(list); 253 else 254 \_\_list\_cut\_position(list, head, entry); 255\}

这里有三个参数，list,head,entry 。

假设原先有链表：head <-> node1 <-> node2 <-> node3 <-> entry <-> node4 <-> head

那么最后会得到链表1 ：head <-> node4 <-> head  和链表2 ：list <-> node1 <-> node2 <-> node3 <-> entry <-> list 。

这里最好自己画图模拟一下。

链表的合并

257static inline void \_\_list\_splice(const struct list\_head \*list, 258 struct list\_head \*prev, 259 struct list\_head \*next) 260\{ 261 struct list\_head \*first = list->next; 262 struct list\_head \*last = list->prev; 263 264 first->prev = prev; 265 prev->next = first; 266 267 last->next = next; 268 next->prev = last; 269\}

假设有两条链表：head <-> node1 <-> node2 <-> node3 <-> head

和：last <-> list <-> first

那么合并的结果是取代了head ：last <-> list <-> first <-> node1 <-> node2 <-> node3 <-> last

271/\*\* 272 \* list\_splice - join two lists, this is designed for stacks 273 \* @list: the new list to add. 274 \* @head: the place to add it in the first list. 275 \*/ 276static inline void list\_splice(const struct list\_head \*list, 277 struct list\_head \*head) 278\{ 279 if (!list\_empty(list)) 280 \_\_list\_splice(list, head, head->next); 281\} 282 283/\*\* 284 \* list\_splice\_tail - join two lists, each list being a queue 285 \* @list: the new list to add. 286 \* @head: the place to add it in the first list. 287 \*/ 288static inline void list\_splice\_tail(struct list\_head \*list, 289 struct list\_head \*head) 290\{ 291 if (!list\_empty(list)) 292 \_\_list\_splice(list, head->prev, head); 293\} 294 295/\*\* 296 \* list\_splice\_init - join two lists and reinitialise the emptied list. 297 \* @list: the new list to add. 298 \* @head: the place to add it in the first list. 299 \* 300 \* The list at @list is reinitialised 301 \*/ 302static inline void list\_splice\_init(struct list\_head \*list, 303 struct list\_head \*head) 304\{ 305 if (!list\_empty(list)) \{ 306 \_\_list\_splice(list, head, head->next); 307 INIT\_LIST\_HEAD(list); 308 \} 309\} 310 311/\*\* 312 \* list\_splice\_tail\_init - join two lists and reinitialise the emptied list 313 \* @list: the new list to add. 314 \* @head: the place to add it in the first list. 315 \* 316 \* Each of the lists is a queue. 317 \* The list at @list is reinitialised 318 \*/ 319static inline void list\_splice\_tail\_init(struct list\_head \*list, 320 struct list\_head \*head) 321\{ 322 if (!list\_empty(list)) \{ 323 \_\_list\_splice(list, head->prev, head); 324 INIT\_LIST\_HEAD(list); 325 \} 326\}

以下的合并函数都是调用第一个合并内联函数\_\_list\_splice ，区别只在于合并取代的位置以及是否对空出来的head 进行初始化，即调用INIT\_LIST\_HEAD 等宏。