应要求分享一下内核链表结构,故写了本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))));
在总线设备驱动模型中,除了纵向的分层外还有横向的数据分离。包括设备和驱动的分离、主机和外设驱动的分离。
本文作者: Ifan Tsai (菜菜)
本文链接: https://cloud.tencent.com/developer/article/2164599
版权声明: 本文采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!