C程序技术

linux内核链表整理

Posted by Dandan on October 21, 2022

前言

自从做了sdwan项目后，几乎每个项目都要和内核链表打交道。以往都是自己实现链表，用了两年内核链表后，觉得还是挺好用的，直接调用装好的接口：初始化、遍历、添加、删除等等。今儿就整理一下，其实链表的思想都大差不差，无非一个就是自己实现，或者用现成的，内核链表会用了，其他的也自然就会了（以下关于链表的基础知识就不详细介绍了，认为都有基本的数据结构知识）。

简介

链表初始化

内核链表一个双向链表，有指针prior、指针next:

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

初始化时将next、prev指针都指向自己，初始化方法如下：

#define LIST_HEAD_INIT(name) { &(name), &(name) }   //初始化， 前驱后继都指向自己
#undef LIST_HEAD
#define LIST_HEAD(name)	struct list_head name = LIST_HEAD_INIT(name)

static inline void
INIT_LIST_HEAD(struct list_head *list)
{
	list->next = list->prev = list;
}

上边上三种初始化链表的方法，选用其中一种就行。

添加节点

添加节点：分头插法、尾插法（关于双向链表的插入位置就不详细介绍了，认为都有数据结构基础。）

  • 头插法函数：list_add

  • 尾插法函数：list_add_tail
    二者就是插入的位置不同，一个是往链表的头部添加，一个是往链表的尾部添加。

  • 两种插入方法均调用_list_add：
static inline void
list_add(struct list_head *_new, struct list_head *head)
{
	_list_add(_new, head, head->next);
}

static inline void
list_add_tail(struct list_head *_new, struct list_head *head)
{
	_list_add(_new, head->prev, head);
}
  • _list_add函数 
    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;
}
  • 示例
#include <linux/list.h>

struct my_struct {
    int data;
    struct list_head list;
};

struct list_head my_list;  // 创建一个链表头部

struct my_struct new_element;
// 初始化新元素并添加到链表头部
list_add(&new_element.list, &my_list);

struct my_struct another_element;
// 初始化另一个新元素并添加到链表尾部
list_add_tail(&another_element.list, &my_list);

最终三个节点的位置：new_element.list my_list another_element.list

遍历节点

在我的应用中遍历链表通常使用list_for_each_entry函数，当然还有函数：list_for_each。

list_for_each_entry

 #define list_for_each_entry(p, h, field)				\
	for (p = list_first_entry(h, __typeof__(*p), field); &p->field != (h); \
	    p = list_entry(p->field.next, __typeof__(*p), field))

遍历得到每一个list，然后获取其宿主结构体地址,看着好别扭，整理一下：

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

 #define list_for_each_entry(p, h, field)				\
	for (
        p = list_entry(h->next, __typeof__(*p), field);         //for循环的初始化
        &p->field != (h);                                       //for循环执行的条件:用于检查是否已经遍历完整个链表
	    p = list_entry(p->field.next, __typeof__(*p), field)    //每循环一次执行
    )

进一步解析：

#define	list_entry(ptr, type, field)	container_of(ptr, type, field)

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

container_of

目的是从数据结构中的一个成员指针，反向计算出包含这个成员的结构体的指针。

  • const typeof(((type *)0)->member) *__mptr = (ptr);：
    这行代码定义了一个临时变量 __mptr，它的类型是结构体成员 member 的类型。这里使用 typeof 宏来获取成员的类型。((type *)0)->member 是一个技巧，它创建了一个类型为 type 的指针，然后通过 -> 运算符访问成员 member，这只是为了获取成员的类型而不会引发运行时错误。

  • (type *)((char *)__mptr - offsetof(type, member));：
    这是实际的操作，它计算出包含成员 member 的结构体的指针。让我们分解这个表达式：

    • __mptr 是指向成员的指针。
    • offsetof(type, member) 返回了成员在结构体中的偏移量（以字节为单位）。
    • (char *)__mptr 将 __mptr 转换为 char 指针，这是因为指针的算术运算通常是以字节为单位的。
    • ((char *)__mptr - offsetof(type, member)) 计算出结构体的起始地址，减去成员的偏移量，从而得到包含成员的结构体的地址。
    • 最后，(type *) 强制将结果转换回结构体指针的类型，从而得到最终的结果。

list_for_each

定义：

#define list_for_each(pos, head)                                               \
	for (pos = (head)->next; pos != (head); pos = pos->next)

二者区别：

1.list_for_each_entry 宏：

  • 用途：用于遍历包含特定数据结构的链表，通常用于迭代链表中的自定义结构体。
  • 示例：list_for_each_entry(pos, head, member)，其中 pos 是自定义结构体的指针，head 是链表头部指针，member 是自定义结构体中 struct list_head 成员的名称。
  • 行为：这个宏将遍历链表，从头到尾依次访问每个元素，然后你可以使用 pos 来访问链表元素中的自定义数据。它是一个适用于自定义结构体的高级迭代宏。

2.list_for_each 宏：

  • 用途：用于遍历链表，不需要访问链表中每个元素的自定义数据，只是用于迭代链表的指针。
  • 示例：list_for_each(pos, head)，其中 pos 是 struct list_head 结构体的指针，head 是链表头部指针。
  • 行为：这个宏将遍历链表，从头到尾依次访问每个 struct list_head 结构体，通常用于在不需要访问自定义数据的情况下，执行一些链表操作，如删除元素等。

3.示例：

  • 使用 list_for_each_entry 遍历包含自定义结构体的链表：
   struct my_struct {
    int data;
    struct list_head list;
};

struct list_head my_list;  // 创建一个链表头部

// 使用 list_for_each_entry 迭代自定义结构体链表
struct my_struct *pos;
list_for_each_entry(pos, &my_list, list) {
    // 这里可以访问自定义结构体中的数据
    printk("Data: %d\n", pos->data);
}
  • 使用 list_for_each 遍历链表，不需要访问自定义数据：
struct list_head my_list;  // 创建一个链表头部

// 使用 list_for_each 迭代链表，不需要访问自定义数据
struct list_head *pos;
list_for_each(pos, &my_list) {
    // 这里执行链表操作，不涉及自定义结构体的数据
}
  • 总结：list_for_each_entry 用于遍历包含自定义结构体的链表，并访问自定义数据，而 list_for_each 用于简单地遍历链表，不涉及自定义数据的访问。

删除

删除用的是list_del，当然还有其他-尾删等， 跟添加异曲同工，当删除用list_for_each_entry会报错，不够安全，这时候就用到了另一个函数：list_for_each_entry_safe,以避免在遍历过程中删除元素导致的错误。以下为其定义：

#define list_for_each_entry(p, h, field)				\
	for (p = list_first_entry(h, __typeof__(*p), field); &p->field != (h); \
	    p = list_entry(p->field.next, __typeof__(*p), field))

跟list_for_each_entry很相似；作用:
list_for_each_entry_safe 的主要作用是在遍历链表的同时，允许你安全地删除当前元素而不影响遍历的进行。这是因为它会在遍历的过程中使用 n 暂存下一个元素的位置，以便在删除 pos 后，仍然可以继续遍历链表。

示例：

#include <linux/list.h>

struct my_struct {
    int data;
    struct list_head list;
};

struct list_head my_list;  // 创建一个链表头部

// 使用 list_for_each_entry_safe 迭代自定义结构体链表，并安全删除元素
struct my_struct *pos, *n;
list_for_each_entry_safe(pos, n, &my_list, list) {
    // 这里可以访问自定义结构体中的数据
    printk("Data: %d\n", pos->data);

    // 在安全的情况下删除当前元素
    list_del(&pos->list);
    kfree(pos); // 释放内存
}

在上面的示例中，list_for_each_entry_safe 用于遍历自定义结构体链表，并安全地删除每个元素。n 用于临时存储下一个元素的位置，这允许在删除 pos 后继续遍历链表，而不会导致错误。这在内核编程中非常有用，因为删除元素可能会导致内存泄漏或访问无效内存地址，而 list_for_each_entry_safe 可以帮助避免这些问题。

CATALOG
    FEATURED TAGS
    C程序技术 Life Linux FAQ FRR openwrt 网络 VPN开发 VPP