链表

Kernel newbie

数据结构

内核中有定义这样的数据结构用于实现链表

1
2
3
4

struct list_head {
    struct list_head* prev;
    struct list_head* next;
};

通过这个 struct 和一系列的宏与函数, 内核实现了链表 (双向, 循环). 实际上, 内核中链表的元素都是 list_head. 实际的链表中的元素是通过一个特别的宏从 list_head 得到的.

建立链表

如果需要某一个 struct 的链表, 给那个 struct 加上一个域 (不一定要在最开始)

1
2
3
4
5

struct some_struct {
    struct list_head* list_field;
    void* data;
    ...
};

之后初始化 struct 时,

1
2
3
4

struct some_struct elem = {
    .mylist = LIST_HEAD_INIT(first.mylist),
    .data = NULL
};

每一个链表都用它的头元素来表示. 头元素没有对应的 some_struct, 就是占位符.

1

LIST_HEAD(mylinkedlist) ;

插入元素

空链表是只有一个元素的 head, 此时

node prev next
head head head

调用

1

list_add(/*new=*/e1, /*head=*/head)

会调用内部函数 __list_add(/*new*/=e1, /*prev*/=head, /*next=*/head->next). 其中 head 是链表头, new 是我们要插入的元素 (的链表域), prev 和 next 是插入后 new 的前后元素. 调用完成后, 有

node prev next
head e1 e1
e1 head head

再继续插入 e2, (注意我们的 list_add 是加到链表头的) 得到

node prev next
head e1 e2
e2 head e1
e1 e2 head

遍历

为了遍历一个链表, 需要链表头 head, 以及一个迭代指针 pos, 以及链表元素中, list_head 所在域的名称. 之后可以如下

1
2
3
4
5

extern list_head * head;
struct some_struct * iter = NULL ; 
list_for_each_entry(iter, head, list_field) { 
    printk ("data = %p\n" , iter->data ); 
}

神奇的宏

container_of

已知 ptr 是 struct type 某个对象 obj 中的 member 域, 要从 ptr, type, member 得到 obj.

源代码 (kernel 4.17.3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// include/linux/kernel.h
/**
 * container_of - cast a member of a structure 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 struct.
 *
 */
#define container_of(ptr, type, member) ({				\
	void *__mptr = (void *)(ptr);					\
	BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) &&	\
			 !__same_type(*(ptr), void),			\
			 "pointer type mismatch in container_of()");	\
	((type *)(__mptr - offsetof(type, member))); })

// include/linux/stddef.h
#undef offsetof
#ifdef __compiler_offsetof
#define offsetof(TYPE, MEMBER)	__compiler_offsetof(TYPE, MEMBER)
#else
#define offsetof(TYPE, MEMBER)	((size_t)&((TYPE *)0)->MEMBER)
#endif

其使用了 GCC 的宏拓展. 展开后, 有三条语句

  1. 防止重复运算 ptr
  2. 检查类型是否匹配
  3. 计算 ptr 在 struct type 中的偏移量, 减去之后就得到了 obj 的地址.

向外暴露 const, 向内暴露是可修改

摘自 fs.h.

struct inode {
    ...
	/*
	 * Filesystems may only read i_nlink directly.  They shall use the
	 * following functions for modification:
	 *
	 *    (set|clear|inc|drop)_nlink
	 *    inode_(inc|dec)_link_count
	 */
	union {
		const unsigned int i_nlink;
		unsigned int __i_nlink;
	};
    ...
}