赞
踩
本期主题:
讲清Linux内核链表的使用方式,包括:
往期链接:
要解释双链表,可以先理解下单向链表,单向链表的定义如下:
链表由多个结点组成,结点不仅包含值,还包含到下一个结点的信息,所以通过这种方式,就将数据组合了起来,看起来就像一条链;
用C++的典型表示方式如下:
// Definition for singly-linked list.
struct SinglyListNode {
int val;
SinglyListNode *next;
SinglyListNode(int x) : val(x), next(NULL) {}
};
结合单链表的基础,因此我们就可以很好理解双链表定义:
结点
不仅包含了到下一个结点的信息,还包含着到上一个结点的信息
,(留下一个疑问,为什么这里不添加数据域的信息?只有指针域的信息)
代码展示:
struct list_head {
struct list_head *next, *prev;
}
前面展示的双链表有个疑问:
为什么链表信息中只有前后两个结点的信息,而没有内容,并且内核中非常多这样的链表形式?
这是因为:
内核中的一个结构体需要管理多个链表
,如果每个链表都定义成一个带信息的结构体,非常冗余,所以把链表抽象了出来;
看下面的例子,大家理解一下设计思想的差异:
//做一个person的管理系统,person包含了age和name //方式1: struct person_list { int age; char *name; struct person_list *next, *prev; }; //方式2: struct list_head { struct list_head *next, *prev; }; struct person { int age; char *name; struct list_head list; };
以上是两种设计结构体的方式,Linux内核需要管理非常多的硬件设计,如果按照方式1管理,内核中将会有无数的list,因为方式1的定义方式是和业务是强绑定的(person管理需要有一个person list,student管理需要有一个student list),所以Linux内核采用方式2的形式来进行管理。
但是方式2管理存在一个问题,怎么通过list来访问对应的person的数据呢?这里Linux内核提供了一个很好的思路:
通过 struct person 里的list结构体,来找到struct person结构体,因此就能访问到结构体中的其他数据了;
下面讲的两个内核中的宏就能解释这种用法。
#define offsetof(type, memb) (unsigned long)(&((type *)0)->memb)
作用:
该宏是返回在type结构体中memb成员相当于结构体指针的offset位置
看例子返回结构体中元素b的offset
#include <stdio.h> #define offsetof(type, memb) (unsigned long)(&((type *)0)->memb) //定义一个双向链表 struct list_head { struct list_head *next, *prev; }; struct test_str { int a; int b; int c; }; int main(void) { struct test_str test; printf("test ptr: 0x%p, test.b ptr: 0x%p\n", &test, &test.b); //返回b在struct test_str中的位置 printf("offsetof val: 0x%lx\n", offsetof(struct test_str, b)); return 0; } //测试结果: $ ./a.out test ptr: 0x0x7ffd9d56ae4c, test.b ptr: 0x0x7ffd9d56ae50 offsetof val: 0x4
/**
* 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) ({ \
const typeof(((type *)0)->member)*__mptr = (ptr); \
(type *)((char *)__mptr - offsetof(type, member)); })
作用:
通过type类型中的member和member的指针ptr,返回type类型的指针(也就是地址)
对着代码解释:
第一句只是把ptr赋值给mptr,mptr是strcut中member的指针
第二句是把mptr指针减去offsetof的值,那么就是返回这个struct的指针值(也就是地址)
接着刚才的例子继续:
#include <stdio.h> #define offsetof(type, memb) (unsigned long)(&((type *)0)->memb) #define container_of(ptr, type, member) ({ \ const typeof(((type *)0)->member)*__mptr = (ptr); \ (type *)((char *)__mptr - offsetof(type, member)); }) //定义一个双向链表 struct list_head { struct list_head *next, *prev; }; struct test_str { int a; int b; int c; }; int main(void) { struct test_str test; printf("test ptr: 0x%p, test.b ptr: 0x%p\n", &test, &test.b); printf("offsetof val: 0x%lx\n", offsetof(struct test_str, b)); //通过test_str中的b指针,来返回test_str结构体指针 printf("container_of: 0x%p\n", container_of(&test.b, struct test_str, b)); return 0; } //测试结果: $ ./a.out test ptr: 0x0x7ffdda9915ec, test.b ptr: 0x0x7ffdda9915f0 offsetof val: 0x4 container_of: 0x0x7ffdda9915ec
static inline void
INIT_LIST_HEAD(struct list_head *list)
{
list->next = list->prev = list;
}
//linux内核中定义了一些宏来实现初始化
#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 *entry, struct list_head *prev, struct list_head *next) { next->prev = entry; entry->next = next; entry->prev = prev; prev->next = entry; } /** * Insert a new element after the given list head. The new element does not * need to be initialised as empty list. * The list changes from: * head → some element → ... * to * head → new element → older element → ... * * Example: * struct foo *newfoo = malloc(...); * list_add(&newfoo->entry, &bar->list_of_foos); * * @param entry The new element to prepend to the list. * @param head The existing list. */ static inline void list_add(struct list_head *entry, struct list_head *head) { __list_add(entry, head, head->next); } /** * Append a new element to the end of the list given with this list head. * * The list changes from: * head → some element → ... → lastelement * to * head → some element → ... → lastelement → new element * * Example: * struct foo *newfoo = malloc(...); * list_add_tail(&newfoo->entry, &bar->list_of_foos); * * @param entry The new element to prepend to the list. * @param head The existing list. */ static inline void list_add_tail(struct list_head *entry, struct list_head *head) { __list_add(entry, head->prev, head); }
在看代码之前,我们先设想一下如何应该遍历?
1.前面提到内核链表是放在结构体中,如果我们想访问内核中这个结构体的指针,我们肯定需要使用前面提到的container_of宏;
2.链表的起始条件应该是head->next;
3.由于链表是双向的,所以遍历完一圈的条件应该是当前pos = head了,这样就遍历完一圈了;
因此有代码:
//下面例子中的方式1
#define list_for_each(pos, head) \
for (pos = (head->next); pos != head; pos = pos->next)
在实际的应用中,上面的宏只能遍历list, 其实我们还希望能够通过list去访问到包括了list的这个结构体
//@ param pos: 需要遍历的包含了list的父结构体类型的指针
//@ head: 需要遍历的list结构体的head
//@ member: 这个需要遍历的list结构体在父结构体中的定义
//下面例子中的方式2
#define list_for_each_entry(pos, head, member) \
for (pos = container_of((head)->next, typeof(*pos), member); \
&pos->member != (head); \
pos = container_of(pos->member.next, typeof(*pos), member))
看下面例子中的方式1和方式2,有助于理解前面的描述
#include <stdio.h> #include <stdlib.h> #define offsetof(type, memb) (unsigned long)(&((type *)0)->memb) #define container_of(ptr, type, member) ({ \ const typeof(((type *)0)->member)*__mptr = (ptr); \ (type *)((char *)__mptr - offsetof(type, member)); }) #define list_for_each_entry(pos, head, member) \ for (pos = container_of((head)->next, typeof(*pos), member); \ &pos->member != (head); \ pos = container_of(pos->member.next, typeof(*pos), member)) //定义一个双向链表 struct list_head { struct list_head *next, *prev; }; struct test_str { int a; int b; int c; struct list_head list; }; //链表操作 static inline void __list_add(struct list_head *entry, struct list_head *prev, struct list_head *next) { next->prev = entry; entry->next = next; entry->prev = prev; prev->next = entry; } //在head之后插入节点 static inline void list_add(struct list_head *entry, struct list_head *head) { __list_add(entry, head, head->next); } //在尾部添加节点 static inline void list_add_tail(struct list_head *entry, struct list_head *head) { __list_add(entry, head->prev, head); } //初始化链表 static inline void INIT_LIST_HEAD(struct list_head *list) { list->next = list->prev = list; } //遍历链表 #define list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next) int main(void) { struct test_str test_head; struct test_str *test; struct list_head *pos, *next; int i; INIT_LIST_HEAD(&test_head.list); for (i = 0; i < 5; i++) { test = (struct test_str *)malloc(sizeof(struct test_str)); test->a = i; //把新节点添加到末尾 list_add_tail(&(test->list), &test_head.list); } //方式1:先遍历链表的元素再用container_of,然后访问其他元素 printf("------------------DEBUG1------------------\n"); list_for_each(pos, &test_head.list) { //这里的pos是test_head.list的指针,我们想访问test_head指针,所以用container_of test = container_of(pos, struct test_str, list); printf("val is %d\n", test->a); } printf("------------------DEBUG2------------------\n"); // 方式2:把container_of放至宏中,直接访问其他元素 list_for_each_entry(test, &test_head.list, list) { printf("val is %d\n", test->a); } return 0; } //测试结果: $ ./a.out ------------------DEBUG1------------------ val is 0 val is 1 val is 2 val is 3 val is 4 ------------------DEBUG2------------------ val is 0 val is 1 val is 2 val is 3 val is 4
以misc驱动为例,看内核中双链表的使用:
个人理解有以下几个关键点:
- 在设备的结构体中需要设计双向链表;
- 设备的指针不应该对外开发,应该有一个静态的链表能够和前面的设备中的双向链表挂上关系
以下是misc驱动的设计:
//misdevice.h struct miscdevice { int minor; const char *name; const struct file_operations *fops; struct list_head list; //这个链表是核心 struct device *parent; struct device *this_device; const struct attribute_group **groups; const char *nodename; umode_t mode; }; //misc.c /* * Head entry for the doubly linked miscdevice list */ //设计了一个静态的链表,并初始化 static LIST_HEAD(misc_list); int misc_register(struct miscdevice * misc) { .... //初始化了Misc结构体中的链表 INIT_LIST_HEAD(&misc->list); .... //添加misc->list到misc_list后面,这样misc_list就有所有的miscdevice信息 list_add(&misc->list, &misc_list); } //直接使用misc_list的信息就能获取到miscdevice指针 static int misc_open(struct inode * inode, struct file * file) { int minor = iminor(inode); struct miscdevice *c; int err = -ENODEV; const struct file_operations *new_fops = NULL; mutex_lock(&misc_mtx); list_for_each_entry(c, &misc_list, list) { ....//直接使用 } }
还有一个例子更为完整:
#include <linux/module.h> #include <linux/kernel.h> #include <linux/list.h> #include <linux/slab.h> struct device { int id; // 其他设备相关的数据 struct list_head list; // 链表节点 }; // 定义链表头节点 static LIST_HEAD(device_list); // 初始化设备列表 static int init_device_list(void) { int i; struct device *dev; for (i = 0; i < 5; i++) { dev = kmalloc(sizeof(struct device), GFP_KERNEL); dev->id = i; // 初始化设备数据 // 将设备节点插入链表尾部 list_add_tail(&dev->list, &device_list); } return 0; } // 遍历设备列表并处理每个设备 static void process_device_list(void) { struct device *dev; // 遍历链表 list_for_each_entry(dev, &device_list, list) { // 处理设备 printk("Processing device %d\n", dev->id); } } // 清理设备列表 static void cleanup_device_list(void) { struct device *dev, *next; // 遍历链表并释放每个设备 list_for_each_entry_safe(dev, next, &device_list, list) { list_del(&dev->list); kfree(dev); } } // 模块加载函数 static int __init my_module_init(void) { printk("Initializing device driver module\n"); // 初始化设备列表 init_device_list(); // 处理设备列表 process_device_list(); return 0; } // 模块卸载函数 static void __exit my_module_exit(void) { printk("Cleaning up device driver module\n"); // 清理设备列表 cleanup_device_list(); } module_init(my_module_init); module_exit(my_module_exit);
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。