list

发表于   |   分类于   |     |   阅读次数

内核数据结构 通用链表 list

Linux kernel: 3.10.67

Linux内核使用一种双向循环链表 list_head 作为通用链表

include/linux/types.h中定义 list_head 的数据结构，
include/linux/list.h中定义 list_head 的操作函数，其全部实现为inline函数

数据结构

1
2
3
struct list_head {
	struct list_head *next, *prev;
};

链表的表头和节点均用 list_head 结构表示，
list_head 结构包含两个list_head指针，分别指向链表的前一节点和后一节点

空链表只包含一个表头，其prev、next指针均指向表头自身；
表头的next指针指向链表的头节点，prev指针指向链表的尾节点；
头节点的prev指针指向表头，尾节点的next指针指向表头

linux_kernel_double_linked_list-c500

操作函数

init

LIST_HEAD
1
2
#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

静态声明并初始化链表头/链表节点

LIST_HEAD_INIT/INIT_LIST_HEAD
1
2
3
4
5
6
7
#define LIST_HEAD_INIT(name) { &(name), &(name) }

static inline void INIT_LIST_HEAD(struct list_head *list)
{
	list->next = list;
	list->prev = list;
}

动态初始化链表头/链表节点，刚刚初始化的链表头/链表节点的prev、next指针均指向链表头/链表节点自身

add

1
2
3
4
5
6
7
8
9
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;
}

在prev、next节点之间添加new节点

list_add
1
2
3
4
static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}

在head链表的头部添加new节点（在head节点之后添加new节点）

list_add_tail
1
2
3
4
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}

在head链表的尾部添加new节点（在head节点之前添加new节点）

delete

1
2
3
4
5
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	prev->next = next;
}

删除prev、next链表节点之间的节点

1
2
3
4
static inline void __list_del_entry(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
}

删除entry链表节点

list_del
1
2
3
4
5
6
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的prev、next指针的值为LIST_POISON1、LIST_POISON2

include/linux/poison.h中定义

1
2
3
4
5
6
7
8
9
10
11
12
13
#ifdef CONFIG_ILLEGAL_POINTER_VALUE
# define POISON_POINTER_DELTA _AC(CONFIG_ILLEGAL_POINTER_VALUE, UL)
#else
# define POISON_POINTER_DELTA 0
#endif

/*
 * 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 + POISON_POINTER_DELTA)
#define LIST_POISON2  ((void *) 0x00200200 + POISON_POINTER_DELTA)

list corruption 包括以下几种情形

  1. 声明 list_head 类型的变量但未对其初始化，因而其prev、next指针的值为0（即NULL，static storage duration）或不确定（automatic storage duration）
  2. 使用bad pointer为prev、next指针赋值，从而导致prev、next指针的值为NULL
  3. 调用list_del()删除该链表节点，未对该链表节点重新初始化时再次引用该节点，此时prev、next指针的值为LIST_POISON1、LIST_POISON2，这种链表节点称为use-after-free

LIST_POISON1、LIST_POISON2实际为特殊的内存地址，主要用于调试，使用LIST_POISON1、LIST_POISON2的目的是 more easily detect different classes of list corruption，即将上述的错误3与其他错误区分开来，从而便于调试

list_del_init
1
2
3
4
5
static inline void list_del_init(struct list_head *entry)
{
	__list_del_entry(entry);
	INIT_LIST_HEAD(entry);
}

删除entry链表节点，并初始化该链表节点，即将该链表节点的prev、next指针指向自身

replace

list_replace
1
2
3
4
5
6
7
static inline void list_replace(struct list_head *old, struct list_head *new)
{
	new->next = old->next;
	new->next->prev = new;
	new->prev = old->prev;
	new->prev->next = new;
}

以new节点替换old节点

linux_list_head-list_replace-c600

list_replace_init
1
2
3
4
5
6
static inline void list_replace_init(struct list_head *old,
					struct list_head *new)
{
	list_replace(old, new);
	INIT_LIST_HEAD(old);
}

以new节点替换old节点，并初始化old节点

linux_list_head-replace_init-c600

move

list_move
1
2
3
4
5
static inline void list_move(struct list_head *list, struct list_head *head)
{
	__list_del_entry(list);
	list_add(list, head);
}

将list链表节点从原链表中移除，并添加到新链表head的头部

list_move_tail
1
2
3
4
5
static inline void list_move_tail(struct list_head *list, struct list_head *head)
{
	__list_del_entry(list);
	list_add_tail(list, head);
}

将list链表节点从原链表中移除，并添加到新链表head的尾部

list_rotate_left
1
2
3
4
5
6
7
8
9
static inline void list_rotate_left(struct list_head *head)
{
	struct list_head *first;

	if (!list_empty(head)) {
		first = head->next;
		list_move_tail(first, head);
	}
}

将head链表的头节点移到链表的尾部

linux_list_head-rotate_left-c600

judge

list_is_last
1
2
3
4
5
static inline int list_is_last(const struct list_head *list,
				const struct list_head *head)
{
	return list->next == head;
}

判断list节点是否为链表的尾节点，其中head是该链表的表头

list_empty
1
2
3
4
static inline int list_empty(const struct list_head *head)
{
	return head->next == head;
}

判断head链表是否为空链表，即链表只包含一个表头

list_empty_careful
1
2
3
4
5
static inline int list_empty_careful(const struct list_head *head)
{
	struct list_head *next = head->next;
	return (next == head) && (next == head->prev);
}

判断链表head是否为空链表，同时当前没有其他CPU修改该链表节点的prev、next成员

list_is_singular
1
2
3
4
static inline int list_is_singular(const struct list_head *head)
{
	return !list_empty(head) && (head->next == head->prev);
}

判断head链表中除了链表头，是否只有一个节点

cut

1
2
3
4
5
6
7
8
9
10
11
static inline void __list_cut_position(struct list_head *list,
		struct list_head *head, struct list_head *entry)
{
	struct list_head *new_first = entry->next;
	list->next = head->next;
	list->next->prev = list;
	list->prev = entry;
	entry->next = list;
	head->next = new_first;
	new_first->prev = head;
}

将head链表中从head至entry的一段链表节点（不包括head，但包括entry）剪切出来，并添加到list链表的头部

linux_list_head-cut_position

list_cut_position
1
2
3
4
5
6
7
8
9
10
11
12
13
static inline void list_cut_position(struct list_head *list,
		struct list_head *head, struct list_head *entry)
{
	if (list_empty(head))
		return;
	if (list_is_singular(head) &&
		(head->next != entry && head != entry))
		return;
	if (entry == head)
		INIT_LIST_HEAD(list);
	else
		__list_cut_position(list, head, entry);
}

将head链表中从head至entry的一段链表节点剪切出来，并添加到list链表的头部，同时对参数的有效性进行检查

  • 若head链表为空，则直接返回
  • 若head链表只有一个链表节点，同时该节点不为entry，即entry节点不在head链表中，则函数直接返回
  • 若链表头head与链表节点entry相等，则直接初始化list链表，此时会丢失list链表中的信息

splice

1
2
3
4
5
6
7
8
9
10
11
12
13
static inline void __list_splice(const struct list_head *list,
				 struct list_head *prev,
				 struct list_head *next)
{
	struct list_head *first = list->next;
	struct list_head *last = list->prev;

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

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

将list链表（不包括list链表头）添加到prev、next链表节点之间

linux_list_head_splice-c

list_splice
1
2
3
4
5
6
static inline void list_splice(const struct list_head *list,
				struct list_head *head)
{
	if (!list_empty(list))
		__list_splice(list, head, head->next);
}

将list链表（不包括list链表头）添加到head链表的头部

linux_list_head_splice_head-c

list_splice_tail
1
2
3
4
5
6
static inline void list_splice_tail(struct list_head *list,
				struct list_head *head)
{
	if (!list_empty(list))
		__list_splice(list, head->prev, head);
}

将list链表（不包括list链表头）添加到head链表的尾部

linux_list_head_splice_tai-c

list_splice_init
1
2
3
4
5
6
7
8
static inline void list_splice_init(struct list_head *list,
				    struct list_head *head)
{
	if (!list_empty(list)) {
		__list_splice(list, head, head->next);
		INIT_LIST_HEAD(list);
	}
}

将list链表（不包括list链表头）添加到head链表的头部，同时初始化list链表头

linux_list_head_splice_head_init-c

list_splice_tail_init
1
2
3
4
5
6
7
8
static inline void list_splice_tail_init(struct list_head *list,
					 struct list_head *head)
{
	if (!list_empty(list)) {
		__list_splice(list, head->prev, head);
		INIT_LIST_HEAD(list);
	}
}

将list链表（不包括list链表头）添加到head链表的尾部，同时初始化list链表头

linux_list_head_splice_tail_init-c

get the entry

head_list结构内嵌入type数据结构，约定该数据结构称为数据节点，该数据结构组成的链表称为数据链表

list_entry
1
2
#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

head_list结构内嵌入type结构，当已知head_list的地址时，获取包含该head_list的数据节点的地址

@ptr 该head_list的地址
@member type数据结构中该head_list成员的名称
@type 该head_list所在的数据结构

list_first_entry
1
2
#define list_first_entry(ptr, type, member) \
	list_entry((ptr)->next, type, member)

返回包含ptr链表的头节点的type类型的数据节点，list_head在该数据结构中的成员名称为member

list_first_entry_or_null
1
2
#define list_first_entry_or_null(ptr, type, member) \
	(!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL)

ptr链表非空时，返回包含ptr链表的头节点的type类型的数据节点，list_head在该数据结构中的成员名称为member；否则返回NULL

list_next_entry
1
2
#define list_next_entry(pos, member) \
	list_entry((pos)->member.next, typeof(*(pos)), member)

返回包含ptr链表节点的下一个链表节点的数据节点，list_head在该数据结构中的成员名称为member

list_prev_entry
1
2
#define list_prev_entry(pos, member) \
	list_entry((pos)->member.prev, typeof(*(pos)), member)

返回包含ptr链表节点的上一个链表节点的数据节点，list_head在该数据结构中的成员名称为member

list_safe_reset_next
1
2
#define list_safe_reset_next(pos, n, member) \
	n = list_entry(pos->member.next, typeof(*pos), member)

返回pos数据节点的下一节点，并保存在n中，list_head在该数据结构中的成员名称为member

iterate the list

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

顺序遍历链表head，pos用来存储当前的链表节点

1
2
#define __list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)

顺序遍历链表head，pos用来存储当前的链表节点，与list_for_each()完全相同

list_for_each_prev
1
2
#define list_for_each_prev(pos, head) \
	for (pos = (head)->prev; pos != (head); pos = pos->prev)

逆序遍历链表head，pos用来存储当前的链表节点

list_for_each_safe
1
2
3
#define list_for_each_safe(pos, n, head) \
	for (pos = (head)->next, n = pos->next; pos != (head); \
		pos = n, n = pos->next)

顺序遍历链表head

@pos 存储当前的链表节点
@n 备份当前链表节点的下一个节点，因而该函数在当前链表节点被移除时也能正常遍历整个链表

list_for_each_prev_safe
1
2
3
4
#define list_for_each_prev_safe(pos, n, head) \
	for (pos = (head)->prev, n = pos->prev; \
	     pos != (head); \
	     pos = n, n = pos->prev)

逆序遍历链表head

@pos 存储当前的链表节点
@n 备份当前链表节点的上一个节点，因而该函数在当前链表节点被移除时也能正常遍历整个链表

iterate the entry

list_for_each_entry
1
2
3
4
#define list_for_each_entry(pos, head, member) \
	for (pos = list_entry((head)->next, typeof(*pos), member); \
	     &pos->member != (head); \
	     pos = list_entry(pos->member.next, typeof(*pos), member))

由链表头开始顺序遍历数据链表

@pos 存储当前的数据节点
@head 链表头
@member list_head在该数据结构中的名称

list_for_each_entry_reverse
1
2
3
4
#define list_for_each_entry_reverse(pos, head, member) \
	for (pos = list_entry((head)->prev, typeof(*pos), member); \
	     &pos->member != (head); \
	     pos = list_entry(pos->member.prev, typeof(*pos), member))

由链表头开始逆序遍历数据链表

@pos 存储当前的数据节点
@head 链表头
@member list_head在该数据结构中的名称

list_prepare_entry
1
2
#define list_prepare_entry(pos, head, member) \
	((pos) ? : list_entry(head, typeof(*pos), member))

用于准备list_for_each_entry_continue()中的pos指针

pos为开始遍历的数据节点，若pos存在定义，则直接返回pos；否则返回包含head链表头的数据节点，即此时遍历实际由链表头开始

list_for_each_entry_continue
1
2
3
4
#define list_for_each_entry_continue(pos, head, member) \
	for (pos = list_entry(pos->member.next, typeof(*pos), member); \
	     &pos->member != (head); \
	     pos = list_entry(pos->member.next, typeof(*pos), member))

由特定数据节点pos之后开始顺序遍历数据链表，即实际由pos数据节点的下一节点开始遍历

@pos 由特定数据节点pos之后开始遍历数据链表，同时pos用于存储当前的数据节点
@head 链表头
@member list_head在该数据结构中的名称

list_for_each_entry_continue_reverse
1
2
3
4
#define list_for_each_entry_continue_reverse(pos, head, member) \
	for (pos = list_entry(pos->member.prev, typeof(*pos), member); \
	     &pos->member != (head); \
	     pos = list_entry(pos->member.prev, typeof(*pos), member))

由特定数据节点pos之前开始逆序遍历数据链表，即实际由pos数据节点的上一节点开始遍历

@pos 由特定数据节点pos之前开始遍历数据链表,同时pos用于存储当前的数据节点
@head 链表头
@member list_head在该数据结构中的名称

list_for_each_entry_from
1
2
3
#define list_for_each_entry_from(pos, head, member) \
	for (; &pos->member != (head); \
	     pos = list_entry(pos->member.next, typeof(*pos), member))

由特定数据节点pos开始顺序遍历数据链表

@pos 由特定数据节点pos开始遍历数据链表，同时pos用于存储当前的数据节点
@head 链表头
@member list_head在该数据结构中的名称

list_for_each_entry_safe
1
2
3
4
5
#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))

由链表头开始顺序遍历数据链表

@pos 存储当前的数据节点
@head 链表头
@member list_head在该数据结构中的名称
@n 备份当前数据节点的下一节点

list_for_each_entry_safe_continue
1
2
3
4
5
#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))

由特定数据节点pos之后开始顺序遍历数据链表，即实际由pos数据节点的下一节点开始遍历

@pos 由特定数据节点pos之后开始遍历数据链表，同时pos用于存储当前的数据节点
@head 链表头
@member list_head在该数据结构中的名称
@n 备份当前数据节点的下一个数据节点

list_for_each_entry_safe_from
1
2
3
4
#define list_for_each_entry_safe_from(pos, n, head, member) \
	for (n = list_entry(pos->member.next, typeof(*pos), member); \
	     &pos->member != (head); \
	     pos = n, n = list_entry(n->member.next, typeof(*n), member))

由特定数据节点pos开始顺序遍历数据链表
@pos 由特定数据节点pos开始遍历数据链表，同时pos用于存储当前的数据节点
@head 链表头
@member list_head在该数据结构中的名称
@n 备份当前数据节点的下一个数据节点

list_for_each_entry_safe_reverse
1
2
3
4
5
#define list_for_each_entry_safe_reverse(pos, n, head, member) \
	for (pos = list_entry((head)->prev, typeof(*pos), member), \
		n = list_entry(pos->member.prev, typeof(*pos), member); \
	     &pos->member != (head); \
	     pos = n, n = list_entry(n->member.prev, typeof(*n), member))

由特定数据节点pos之前开始逆序遍历数据链表，即实际由pos数据节点的上一节点开始遍历

@pos 由特定数据节点pos之前开始遍历数据链表 ，同时pos用于存储当前的数据节点
@head 链表头
@member list_head在该数据结构中的名称
@n 备份当前数据节点的下一个数据节点