当前位置:   article > 正文

【Linux内核链表】的原理及使用方式整理_linux内核链表的使用

linux内核链表的使用

本期主题:
讲清Linux内核链表的使用方式,包括:

  1. 双链表原理以及内核中双链表的使用方式
  2. 解析内核常用宏(offset_of、container_of)的原理
  3. 解析内核链表的使用方式(list_entry、list_for_each宏)

往期链接:



1.双链表定义

要解释双链表,可以先理解下单向链表,单向链表的定义如下:

链表由多个结点组成,结点不仅包含值,还包含到下一个结点的信息,所以通过这种方式,就将数据组合了起来,看起来就像一条链;

在这里插入图片描述

用C++的典型表示方式如下:

// Definition for singly-linked list.
struct SinglyListNode {
    int val;
    SinglyListNode *next;
    SinglyListNode(int x) : val(x), next(NULL) {}
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

结合单链表的基础,因此我们就可以很好理解双链表定义:

结点不仅包含了到下一个结点的信息,还包含着到上一个结点的信息(留下一个疑问,为什么这里不添加数据域的信息?只有指针域的信息)

代码展示:

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

2.内核双链表的差异

前面展示的双链表有个疑问:
为什么链表信息中只有前后两个结点的信息,而没有内容,并且内核中非常多这样的链表形式?

这是因为:

  • 内核中的一个结构体需要管理多个链表,如果每个链表都定义成一个带信息的结构体,非常冗余,所以把链表抽象了出来

看下面的例子,大家理解一下设计思想的差异:

//做一个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;
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

以上是两种设计结构体的方式,Linux内核需要管理非常多的硬件设计,如果按照方式1管理,内核中将会有无数的list,因为方式1的定义方式是和业务是强绑定的(person管理需要有一个person list,student管理需要有一个student list),所以Linux内核采用方式2的形式来进行管理。

但是方式2管理存在一个问题,怎么通过list来访问对应的person的数据呢?这里Linux内核提供了一个很好的思路:

通过 struct person 里的list结构体,来找到struct person结构体,因此就能访问到结构体中的其他数据了;

下面讲的两个内核中的宏就能解释这种用法。

3.内核常用宏(offsetof & container_of)

1.offsetof(type, memb)

#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
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

2.container_of(ptr, type, member)

/**
 * 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)); })
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

作用:

通过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
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

4.内核双向链表的使用

1.初始化双向链表

  • 双向链表的初始化,next和prev都指向自己,只是为了不会有空指针的情况存在
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)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

2.增加双向链表的元素

  • 在内核代码中带 __ 都是代表是内核调用的,不希望作为API开放出去,所以对外的接口是list_add 和 list_add_tail函数
  • __list_add函数 其实很好理解,就是把 entry节点插入 prev和next节点之间,即 prev->entry->next的关系
  • list_add函数 其实就是在head和head->next之间插入entry节点
  • list_add_tail函数 是在 head->prev和head之间插入结点,由于链表是双向的,所以其实这个就是在末尾添加节点
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
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52

3.遍历双向链表

在看代码之前,我们先设想一下如何应该遍历?

1.前面提到内核链表是放在结构体中,如果我们想访问内核中这个结构体的指针,我们肯定需要使用前面提到的container_of宏;
2.链表的起始条件应该是head->next;
3.由于链表是双向的,所以遍历完一圈的条件应该是当前pos = head了,这样就遍历完一圈了;

  • list_for_each(pos, head)宏,用pos遍历以Head为头的链表

因此有代码:

//下面例子中的方式1
#define list_for_each(pos, head) \
	for (pos = (head->next); pos != head; pos = pos->next)
  • 1
  • 2
  • 3

在实际的应用中,上面的宏只能遍历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
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • list_for_each_entry宏,一句句来分析:
  • pos为父结构体类型的指针, container_of就是返回 链表的头结点的下一个结点的父结构体指针
  • 循环的条件是 父结构体的链表 不等于 现在的head
  • 同第一条,container_of就是返回 链表的下一个结点的父结构体指针

看下面例子中的方式1和方式2,有助于理解前面的描述

4.简单的例子看上述情况

#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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108

5.内核中双向链表的使用思想

以misc驱动为例,看内核中双链表的使用:
个人理解有以下几个关键点:

  1. 在设备的结构体中需要设计双向链表;
  2. 设备的指针不应该对外开发,应该有一个静态的链表能够和前面的设备中的双向链表挂上关系

以下是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) {
	....//直接使用
		}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

还有一个例子更为完整:

#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);



  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/128073
推荐阅读
相关标签
  

闽ICP备14008679号