内核链表介绍

菜菜cc

发布于 2022-11-15 21:34:49

2610

发布于 2022-11-15 21:34:49

文章被收录于专栏：菜菜的技术博客菜菜的技术博客

应要求分享一下内核链表结构，故写了本blog。本文对内核链表做一个简单介绍，以及引出内核中大量使用的分离思想和数据结构的定义。

传统链表的困境

内核中数据结构千变万化，采用传统的链表结构形式，需要为各种数据都定义出一个链表。

/* data1 */
struct data1_list_node {
    struct data1 data;
    struct data1_list_node *next;
    struct data1_list_node *prev;
}

/* data2 */
struct data2_list_node {
    struct data2 data;
    struct data2_list_node *next;
    struct data2_list_node *prev;
}

/* data3 */
/* ... */

以上会出现大量定义链表结构，而在c++的模板语法下，可以定义一个链表模板来解决这个问题

template <typename T>
struct list_node {
    T data;
    ListNode<T> *next;
    ListNode<T> *prev;
};

list_node<struct data1> data1_head;
list_node<struct data2> data2_head;
/* data3 */
/* ... */

数据和结构分离

问题的核心在于数据的千变万化，但是所要表述的结构却是统一的！那如果将统一的部分抽取出来呢？让一切的一切都尘归尘，土归土。

内核链表

内核链表正是采用了如上的思想进行设计的，内核链表位于内核代码的include/linux/list.h中，该链表定义为双向循环链表，所有的相关操作都定义在该头文件中，该文件中每个函数极为简洁。截取片段如下

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

#define LIST_HEAD_INIT(name) { &(name), &(name) }

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

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;
}

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

使用内核链表的方式，将链表节点嵌入到数据结构体中。如内核驱动中对misc设备的描述

struct miscdevice  {
    int minor;
    const char *name;
    const struct file_operations *fops;
    struct list_head list;    /* 用内核链表管理所有注册在内核中的misc设备 */
    struct device *parent;
    struct device *this_device;
    const char *nodename;
    mode_t mode;
};

核心问题：通过遍历所有的struct list_head即可拿到所有数据的list成员，而真正需要的是数据，那么如何从list成员获取到struct miscdevice, 最直接的做法是将list成员放置在struct miscdevice最开始处，只需指针强转即可获得，而如上所知该成员并未放到结构体的最开头，内核中的做法是可以放在任意位置，解析时使用了一个很强大的宏来进行获取。

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

#define container_of(ptr, type, member) ({	    \
	const typeof( ((type *)0)->member ) *__mptr = (ptr);    \ /* 1 */
	(type *)( (char *)__mptr - offsetof(type,member) );})     /* 2 */

/* 上面 typeof 为 GNU gcc 扩展语法，可用来获取一个变量的类型 */
/* 以上1代码去掉后，将2中的 __mptr替换为ptr也可正常工作。看似无用，实则用于编译期间类型检查 */
/*******************************************************************/
#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

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

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

/* 内核链表的遍历接口 */
#define list_for_each_entry(pos, head, member)				\
	for (pos = list_first_entry(head, typeof(*pos), member);	\
	     &pos->member != (head);					\
	     pos = list_next_entry(pos, member))

总结

内核中大量使用了该思想，凡是在物理内存中离散分布的结构，均采用此思想将结构嵌入到具体数据中实现数据的结构组织，例如在 epoll 底层和进程调度使用到的 rbtree 。

struct rb_node {
    unsigned long  __rb_parent_color;   /* 包含 parent 指针以及 color 信息 */
    struct rb_node *rb_right;
    struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

在总线设备驱动模型中，除了纵向的分层外还有横向的数据分离。包括设备和驱动的分离、主机和外设驱动的分离。