Linux内核源码分析-链表代码分析

Linux内核源码分析-链表代码分析
分析人：余旭
分析时间：2005年11月17日星期四 11:40:10 AM
雨 温度：10-11度
编号：1-4 类别：准备工作
Email：[e-mail]
时代背景：开始在 Linux内核技术论坛上面发贴，在网友的帮忙下，解决了一些问题。
版权声明：版权保留。本文用作其他用途当经作者本人同意,转载请注明作者姓名
All Rights Reserved. If for other use,must Agreed By the writer.Citing this text,please claim the writer's name.
Copyright (C) 2005 YuXu
**************************************************
-------------双向循环链表---------------------------
来源于：list.h
设计思想：尽可能的代码重用，化大堆的链表设计为单个链表。
链 表的构造：如果需要构造某类对象的特定列表，则在其结构中定义一个类型为list_head指针的成员，通过这个成员将这类对象连接起来，形成所需列表， 并通过通用链表函数对其进行操作。其优点是只需编写通用链表函数，即可构造和操作不同对象的列表，而无需为每类对象的每种列表编写专用函数，实现了代码的 重用。

如果想对某种类型创建链表，就把一个list_head类型的变量嵌入到该类型中，用list_head中的成员和相对应的处理函数来对链表进行遍历。如果想得到相应的结构的指针，使用list_entry可以算出来。
-------------防止重复包含同一个头文件---------------
#ifndef _LINUX_LIST_H
#define _LINUX_LIST_H
...
#endif
用于防止重复包含同一个list.h头文件
-----------struct list_head{}及初始化宏---------
struct list_head
{
struct list_head *next, *prev;
};
list_head从字面上理解，好像是头结点的意思。但从这里的代码来看却是普通结点的结构体。在后面的代码中将list_head当成普通的结点来处理。

--LIST_HEAD_INIT()--LIST_HEAD()--INIT_LIST_HEAD()------
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
分析：name当为结构体struct list_head{}的一个结构体变量，&(name)为该结构体变量的地址。用name结构体变量的始地址将该结构体变量进行初始化。

#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
1.ptr为一个结构体的指针，而name为一个结构体变量；
2.ptr使用时候，当用括号，(ptr);

------------__list_add()---list_add()-------------
static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next)
{
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
1.普通的在两个非空结点中插入一个结点，注意new,prev,next都不能是空值。
2.即：适用于中间结点插入。首结点和尾结点则由于指针为空，不能用此函数。
3.在prev指针和next指针所指向的结点之间插入new指针所指向的结点。

static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
在head和head->next两指针所指向的结点之间插入new所指向的结点。
即：在head指针后面插入new所指向的结点。此函数用于在头结点后面插入结点。
注意：对只有一个单个结点的链表，则head->next为空，list_add（）不能用。

-------------list_add_tail()-------------------
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
在头结点指针head所指向结点的前面插入new所指向的结点。也相当于在尾结点后面增加一个new所指向的结点。（条件是：head->prev当指向尾结点）
注意：
1.head->prev不能为空，即若head为头结点，其head->prev当指向一个数值，一般为指向尾结点，构成循环链表。
2.对只有单个结点的头结点调用此函数则会出错。

-----------__list_del()---list_del()--------------
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
在prev和next指针所指向的结点之间，两者互相所指。在后面会看到：prev为待删除的结点的前面一个结点，next为待删除的结点的后面一个结点。

static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
删除entry所指的结点，同时将entry所指向的结点指针域封死。
对LIST_POISON1,LIST_POISON2的解释说明：
Linux 内核中解释：These are non-NULL pointers that will result in page faults under normal circumstances, used to verify that nobody uses non-initialized list entries.
#define LIST_POISON1 ((void *) 0x00100100)
#define LIST_POISON2 ((void *) 0x00200200)
常规思想是：entry->next = NULL; entry->prev = NULL;
注意：Linux内核中的‘=’都与前后隔了一个空格，这样比紧靠前后要清晰。

---------------list_del_init()--------------------
static inline void list_del_init(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
INIT_LIST_HEAD(entry);
}
删除entry所指向的结点，同时将entry所指向的结点的next，prev指针域指向自身。

-----------list_move()--list_move_tail()----------
static inline void list_move(struct list_head *list, struct list_head *head)
{
__list_del(list->prev, list->next);
list_add(list, head);
}
将list结点前后两个结点互相指向彼此，删除list指针所指向的结点，再将此结点插入head，和head->next两个指针所指向的结点之间。
即：将list所指向的结点移动到head所指向的结点的后面。

static inline void list_move_tail(struct list_head *list, struct list_head *head)
{
__list_del(list->prev, list->next);
list_add_tail(list, head);
}
删除了list所指向的结点，将其插入到head所指向的结点的前面，如果head->prev指向链表的尾结点的话，就是将list所指向的结点插入到链表的结尾。

---------------------list_empty(）-------------
static inline int list_empty(const struct list_head *head)
{
return head->next == head;
}
注意：
1.如果是只有一个结点，head，head->next，head->prev都指向同一个结点，则这里会返回1，但链表却不为空，仍有一个头结点
2.return 后面不带括号，且为一个表达式。
3.测试链表是否为空,但这个空不是没有任何结点，而是只有一个头结点。

--------------------list_empty_careful(）---------
static inline int list_empty_careful(const struct list_head *head)
{
struct list_head *next = head->next;
return (next == head) && (next == head->prev);
}
分析：
1. 只有一个头结点head，这时head指向这个头结点，head->next,head->prev指向head， 即：head==head->next==head->prev，这时候list_empty_careful（）函数返回1。
2. 有两个结点，head指向头结点，head->next,head->prev均指向后面那个结点， 即：head->next==head->prev,而head!=head->next,head!=head->prev. 所以函数将返回0
3.有三个及三个以上的结点，这是一般的情况，自己容易分析了。
注意：这里empty list是指只有一个空的头结点，而不是毫无任何结点。并且该头结点必须其head->next==head->prev==head

---------------__list_splice()------------------
static inline void __list_splice(struct list_head *list, struct list_head *head)
{
struct list_head *first = list->next;
struct list_head *last = list->prev;
struct list_head *at = head->next;

first->prev = head;
head->next = first;

last->next = at;
at->prev = last;
}

--------------------list_splice()----------------
/**
* list_splice - join two lists
* @list: the new list to add.
* @head: the place to add it in the first list.
*/
static inline void list_splice(struct list_head *list, struct list_head *head)
{
if (!list_empty(list))
__list_splice(list, head);
}
分析：
情况1：
普遍的情况，每个链表都至少有3个以上的结点：

====>此处作者画了图，可显示不出来，郁闷！！！

========》待作者上传一个word文档，图在里面。
-------------------------------------------------------------------------------------------


这种情况会丢弃list所指向的结点，这是特意设计的，因为两个链表有两个头结点，要去掉一个头结点。只要一个头结点。


---------------------------------------------------------------------------------------------------------------

特殊情况1：
初始情况：


------------------------------------------------------------------------

特殊情况2：
初始情况：

--------------------list_splice_init()-----------------------------------
/**
* list_splice_init - join two lists and reinitialise the emptied list.
* @list: the new list to add.
* @head: the place to add it in the first list.
*
* The list at @list is reinitialised
*/
static inline void list_splice_init(struct list_head *list,
struct list_head *head)
{
if (!list_empty(list))
{
__list_splice(list, head);
INIT_LIST_HEAD(list);
}
}

--------------------\asm-i386\posix_types.h-------
typedef unsigned int __kernel_size_t;

------\linux\types.h---------size_t---------------
#ifndef _SIZE_T
#define _SIZE_T
typedef __kernel_size_t size_t;
#endif
-------------\linux\compiler-gcc4.h--------------
#define __compiler_offsetof(a,b) __builtin_offsetof(a,b)
分析准备：__compiler_offsetof(),为gcc编译器中的编译方面的参数，查阅gcc方面的文档:
--->gcc.pdf.Download from 。其中解释如下：
#define offsetof(type, member) __builtin_offsetof (type, member)

自 己分析：即：__builtin_offsetof(a,b)就是#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)。__builtin_offsetof(a,b)和offsetof(TYPE,MEMBER)本质一样的，只是 offsetof()宏是由程序员自己来设计(详见后面讲解)。而__builtin_offsetof()宏就是在编译器中已经设计好了的函数，直接调 用即可。明白了这个区别后，下面的代码很好理解。
-------\linux\stddef.h-----offsetof()-----------
#define __compiler_offsetof(a,b) __builtin_offsetof(a,b)
-------------------------------
#undef offsetof
#ifdef __compiler_offsetof
#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
#else
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif
1.对__compiler_offsetof()宏的分析：
__compiler_offsetof 来确认编译器中是否内建了功能同offsetof()宏一样的宏。若已经内建了这样的宏，则offsetof()就是使用这个内建宏 __compiler_offsetof()即：__builtin_offsetof()宏。如果没有定义__compiler_offsetof() 宏，则offsetof()宏就由程序员来设计之。

2.对offsetof()宏的分析：（以下引用论坛）---曾经的腾讯QQ的笔试题。
宿舍舍友参加qq笔试，回来讨论一道选择题，求结构中成员偏移。
想起Linux内核链表，数据节点携带链表节点，通过链表访问数据的方法，用到offsetof宏，今天把它翻了出来:
#define offsetof(TYPE, MEMBER) ((size_t) & ((TYPE *)0)->MEMBER )

一共4步
1. ( (TYPE *)0 ) 将零转型为TYPE类型指针;
2. ((TYPE *)0)->MEMBER 访问结构中的数据成员;
3. &( ( (TYPE *)0 )->MEMBER )取出数据成员的地址;
4.(size_t)(&(((TYPE*)0)->MEMBER))结果转换类型.巧妙之处在于将0转换成(TYPE*)，结构以内存空间首地址0作为起始地址，则成员地址自然为偏移地址；
举例说明：
#include
typedef struct _test
{
char i;
int j;
char k;
}Test;
int main()
{
Test *p = 0;
printf("%p\n", &(p->k));
}
自 己分析：这里使用的是一个利用编译器技术的小技巧，即先求得结构成员变量在结构体中的相对于结构体的首地址的偏移地址，然后根据结构体的首地址为0，从而 得出该偏移地址就是该结构体变量在该结构体中的偏移，即：该结构体成员变量距离结构体首的距离。在offsetof()中，这个member成员的地址实 际上就是type数据结构中member成员相对于结构变量的偏移量。对于给定一个结构，offsetof(type,member)是一个常 量，list_entry()正是利用这个不变的偏移量来求得链表数据项的变量地址。

---------------------typeof()--------------------
--->我开始不懂，源代码中也查不到，网上发贴请教。由liubo1977在上的Linux内核技术论坛上解答，QQ:84915771
答复：
unsigned int i;
typeof(i) x;
x=100;
printf("x:%d\n",x);
typeof() 是 gcc 的扩展，和 sizeof() 类似。

------------------------
container_of() 和offsetof()并不仅用于链表操作，这里最有趣的地方是 ((type *)0)->member，它将0地址强制 "转换" 为 type 结构的指针，再访问到 type 结构中的 member 成员。在 container_of 宏中，它用来给 typeof() 提供参数，以获得 member 成员的数据类型；

---------------container_of()--------------------
container_of() 来自\linux\kernel.h
内核中的注释：container_of - cast a member of a tructure out to the containing structure。
ptr: the pointer to the member.
type: the type of the container struct this is embedded in.
member:the name of the member within the truct.

#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
自己分析：
1.(type *)0->member为设计一个type类型的结构体，起始地址为0，编译器将结构体的起始的地址加上此结构体成员变量的偏移得到此结构体成员变 量的偏移地址，由于结构体起始地址为0，所以此结构体成员变量的偏移地址就等于其成员变量在结构体内的距离结构体开始部分的偏移量。即：& (type *)0->member就是取出其成员变量的偏移地址。而其等于其在结构体内的偏移量:即为：(size_t)(& ((type *)0)->member)经过size_t的强制类型转换后，其数值为结构体内的偏移量。该偏移量这里由offsetof()求出。

2.typeof( ( (type *)0)->member )为取出member成员的变量类型。用其定义__mptr指针.ptr为指向该成员变量的指针。__mptr为member数据类型的常量指针，其指向ptr所指向的变量处。

3.(char *)__mptr转换为字节型指针。(char *)__mptr - offsetof(type,member) )用来求出结构体起始地址（为char *型指针），然后(type *)( (char *)__mptr - offsetof(type,member) )在(type *)作用下进行将字节型的结构体起始指针转换为type *型的结构体起始指针。
这就是从结构体某成员变量指针来求出该结构体的首指针。指针类型从结构体某成员变量类型转换为该结构体类型。

-----------茶余饭后一点小资料----------------------
学辛苦了，看点收集的小东东：
以下文字摘自微软中国研究院前任院长，现微软高级副总裁李开复先生《一封写给中国学生的信》：
“ 我的老板 Rick室Rashid博士是目前微软公司主管研究的高级副总裁，他已经功成名就，却始终保持一颗学习和进取的心。现在，他每年仍然编写大约50,000 行程序。他认为：用最新的技术编程可以使他保持对计算机最前沿技术的敏感，使自己能够不断进步。今天，有些博士生带低年级的本科生和硕士生做项目，就自满 地认为自己已经没有必要再编程了。其实，这样的做法是很不明智的。”

--------------arch-v32\cache.h------------------
#ifndef _ASM_CRIS_ARCH_CACHE_H
#define _ASM_CRIS_ARCH_CACHE_H

/* A cache-line is 32 bytes. */
#define L1_CACHE_BYTES 32
#define L1_CACHE_SHIFT 5
#define L1_CACHE_SHIFT_MAX 5

#endif /* _ASM_CRIS_ARCH_CACHE_H */
分析：
也可用#define L1_CACHE_BYTES (1UL<
-------------asm-i386\cache.h--------------------

#ifndef __ARCH_I386_CACHE_H
#define __ARCH_I386_CACHE_H

/* L1 cache line size */
#define L1_CACHE_SHIFT (CONFIG_X86_L1_CACHE_SHIFT)
#define L1_CACHE_BYTES (1 << L1_CACHE_SHIFT)

//largest L1 which this arch supports
#define L1_CACHE_SHIFT_MAX 7

#endif
分析：cache行在32位平台上多为32字节，但在I386平台上也有128字节的。

----------\linux\prefetch.h--------------------
这里是内核中的解释：(含有自己的分析)
/*
prefetch(x) attempts to pre-emptively get the memory pointed to
by address "x" into the CPU L1 cache.
prefetch(x) should not cause any kind of exception, prefetch(0) is
specifically ok.

prefetch() should be defined by the architecture, if not, the
#define below provides a no-op define.
prefetch()当由体系结构来决定，否则就定义为空宏
有3类prefetch()宏：
There are 3 prefetch() macros:

prefetch(x) - prefetches the cacheline at "x" for read-->预取读
prefetchw(x) - prefetches the cacheline at "x" for write-->预取写
spin_lock_prefetch(x) - prefectches the spinlock *x for taking

there is also PREFETCH_STRIDE which is the architecure-prefered
"lookahead" size for prefetching streamed operations.
PREFETCH_STRIDE用于预取操作流。
These cannot be do{}while(0) macros.
*/
#define _LINUX_PREFETCH_H

#ifndef ARCH_HAS_PREFETCH
static inline void prefetch(const void *x) {;}
#endif

#ifndef ARCH_HAS_PREFETCHW
static inline void prefetchw(const void *x) {;}
#endif

#ifndef ARCH_HAS_SPINLOCK_PREFETCH
#define spin_lock_prefetch(x) prefetchw(x)
#endif

#ifndef PREFETCH_STRIDE
#define PREFETCH_STRIDE (4*L1_CACHE_BYTES)
#endif //PREFETCH_STRIDE

static inline void prefetch_range(void *addr, size_t len)
{
#ifdef ARCH_HAS_PREFETCH
char *cp;
char *end = addr + len;

for (cp = addr; cp < end; cp += PREFETCH_STRIDE)
prefetch(cp);
#endif //ARCH_HAS_PREFETCH
}

#endif //_LINUX_PREFETCH_H

-----asm-x86_64\processor.h---prefetch()---------
static inline void prefetch(void *x)
{
asm volatile("prefetcht0 %0" :: "m" (*(unsigned long *)x));
}
分析：
将x指针作强制类型转换为unsigned long *型，然后取出该内存操作数，送入高速缓存。

----------------list_for_each()------------------
#define list_for_each(pos, head) \
for (pos = (head)->next; prefetch(pos->next), pos != (head); \
pos = pos->next)

----------------__list_for_each()-----------------
Linux Kernel 2.6.14中的解释中的精华部分：
/**
* This variant differs from list_for_each() in that it's the simplest possible list iteration code, no prefetching is done.Use this for code that knows the list to be very short (empty or 1 entry) most of the time.
*/
#define __list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
list_for_each()有prefetch()用于复杂的表的遍历，而__list_for_each()无prefetch()用于简单的表的遍历.
注意：head在宏定义中用了括号将其括起来.

----------------list_for_each_prev()-------------
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
pos = pos->prev)
解释类似上面的list_for_each()。

----------------list_for_each_safe()--------------
内核中解释的精华部分：
/*
* list_for_each_safe - iterate over a list safe against removal of list entry
*/
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
这是说你可以边遍历边删除，这就叫safe。十分精彩。刚开始时，我也一直不理解safe的意思，后来在论坛上搜索list_for_each_safe找到了解答。

----------------list_entry()--------------------
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
分析：
list_entry()函数用于将指向某链表结点成员的指针调整到该链表的开始处，并指针转换为该链表结点的类型。

-------------list_for_each_entry()---------------
#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, t ypeof(*pos), member); \
prefetch(pos->member.next), &pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
分析：
1.杨沙洲--国防科技大学计算机学院--2004年8月指出：
大多数情况下，遍历链表的时候都需要获得链表节点数据项，也就是说list_for_each()和list_entry()总是同时使用。对此Linux给出了一个list_for_each_entry()宏。

2.这是用于嵌套的结构体中的宏：（这个程序例子来自：《Linux内核分析及编程》作者：倪继利 电子工业出版社）
struct example_struct
{
struct list_head list;
int priority;
... //其他结构体成员
};
struct example_struct *node = list_entry(ptr,struct example_struct,list);

自己分析：对比list_entry(ptr,type,member)可知有以下结果：
其 中list相当于member成员，struct example_struct相当于type成员，ptr相当于ptr成员。而list{}成员嵌套于example_struct{}里面。ptr指向 example_struct{}中的list成员变量的。在list_entry（）作用下，将ptr指针回转指向struct example_struct{}结构体的开始处。

3.pos当指向外层结构体，比如指向struct example_struct{}的结点，最开始时候，pos当指向第一个结点。而head开始时候也是指向第一个外层结点的里面的这个内嵌的链表结构体 struct list_head{}，(head)->next则指向后继的一个外层结点的内嵌的链表结点struct list_head{} list。member即是指出该list为其内嵌的结点。
思路：用pos指向外层结构体的结点，用head指向内 层嵌入的结构体的结点。用(head)->next,pos->member.next(即：ptr->list.next)来在内嵌 的结构体结点链表中遍历。每遍历一个结点，就用list_entry()将内嵌的pos->member.next指针回转为指向该结点外层结构体 起始处的指针，并将指针进行指针类型转换为外层结构体型pos。&pos->member! = (head)用pos外层指针引用member即：list成员，与内层嵌入的链表之头结点比较来为循环结束条件。

-------------list_for_each_entry_reverse()-------
#define list_for_each_entry_reverse(pos, head, member) \
for (pos = list_entry((head)->prev, typeof(*pos), m+ember); \
prefetch(pos->member.prev), &pos->member != (head); \
pos = list_entry(pos->member.prev, typeof(*pos), member))
分析类似上面。

---------------list_prepare_entry()---------------
1.函数背景：来自杨沙洲.国防科技大学计算机学院.2004年8月. Linux 内核技术论坛：
杨 在贴子中指出：如果遍历不是从链表头开始，而是从已知的某个pos结点开始，则可以使用 list_for_each_entry_continue(pos,head,member)。有时还会出现这种需求，即经过一系列计算后，如果pos 有值，则从pos开始遍历，如果没有，则从链表头开始，为此，Linux专门提供了一个 list_prepare_entry(pos,head,member)宏，将它的返回值作为 list_for_each_entry_continue()的pos参数，就可以满足这一要求。

2.内核中的list_prepare_entry()的注释及代码：
/**
* list_prepare_entry - prepare a pos entry for use as a start point in
* @pos: the type * to use as a start point
* @head: the head of the list
* @member: the name of the list_struct within the struct.
*/

内核源代码:
#define list_prepare_entry(pos, head, member) \
((pos) ? : list_entry(head, typeof(*pos), member))
分析：
:前面是个空值，即：若pos不为空，则pos为其自身。等效于：
(pos)? （pos）: list_entry(head,typeof(*pos),member)
注意内核格式：:前后都加了空格。

------------list_for_each_entry_continue()--------
3.内核中的list_for_each_entry_continue()的注释及代码：
/**
* list_for_each_entry_continue - iterate over list of given type
*continuing after existing point
* @pos: the type * to use as a loop counter.
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/

内核源代码：
#define list_for_each_entry_continue(pos, head, member) \
for (pos = list_entry(pos->member.next, typeof(*pos), member); \
prefetch(pos->member.next), &pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
分析见list_prepare_entry()中的函数背景。

-------------list_for_each_entry_safe()-----------
1.函数背景：来自杨沙洲.国防科技大学计算机学院.2004年8月. Linux 内核技术论坛：
杨在贴子中指出：list_for_each_entry_safe(pos, n, head,member)，它们要求调用者另外提供一个与pos同类型的指针n，在for循环中暂存pos下一个节点的地址，避免因pos节点被释放而造成的断链。

2.内核中的注释与源代码：
/**
* list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
* @pos: the type * to use as a loop counter.
* @n: another type * to use as temporary storage
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/

#define list_for_each_entry_safe(pos, n, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member), \
n = list_entry(pos->member.next, typeof(*pos), member); \
&pos->member != (head); \
pos = n, n = list_entry(n->member.next, typeof(*n), member))
分析类似上面。容易明白。

--------list_for_each_entry_safe_continue()-------
#define list_for_each_entry_safe_continue(pos, n, head, member) \
for (pos = list_entry(pos->member.next, typeof(*pos), member), \
n = list_entry(pos->member.next, typeof(*pos), member); \
&pos->member != (head); \
pos = n, n = list_entry(n->member.next, typeof(*n), member))