Linux编程——经典链表list_head

1. 关于list_head

struct list_head是Linux内核定义的双向链表，包含一个指向前驱节点和后继节点的指针的结构体。其定义如下：

struct list_head {
    struct list_head *next, *prev; //双向链表，指向节点的指针
};

1.1 链表的定义和初始化

有两种方式来定义和初始化链表头：

• 方法一：利用宏LIST_HEAD定义并初始化
• 方法二：先定义，再利用宏INIT_LIST_HEAD初始化

//方法1：利用LIST_HEAD定义并初始化链表
static LIST_HEAD(registered_llhw); 

//方法2：先定义再初始化链表
struct list_head registered_llhw;  //定义一个链表（注册链路层hardware）
INIT_LIST_HEAD(&registered_llhw);  //初始化链表

//相关宏定义如下：
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)

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

//即初始化后链表的nexth和prev都指向自己。
#define INIT_LIST_HEAD(ptr) do { \
    (ptr)->next = (ptr); \
    (ptr)->prev = (ptr); \
}while(0)

1.2 链表节点增/删

使用list_add/list_add_tail来添加链表节点。

list_add(&entry, &ListHead);

//在head之后添加
static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

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

//添加到head之前，即链表的尾部增加
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}

#ifdef CONFIG_ILLEGAL_POINTER_VALUE
# define POISON_POINTER_DELTA _AC(CONFIG_ILLEGAL_POINTER_VALUE, UL)
#else
# define POISON_POINTER_DELTA 0
#endif

// 定义两个特殊的宏，将已经释放的节点指向这个位置，避免重复删除一个已经被释放的节点，避免出现潜在的漏洞。
// 实际上还起到用于标记已经删除节点的意义。
#define LIST_POISON1  ((void *) 0x00100100 + POISON_POINTER_DELTA)
#define LIST_POISON2  ((void *) 0x00200200 + POISON_POINTER_DELTA)

// 从双向链表中删除一个节点
static inline void list_del(struct list_head *entry)
{
    __list_del_entry(entry);
    entry->next = LIST_POISON1;
    entry->prev = LIST_POISON2;
    //为什么不直接指向空指针NULL？在正常环境下，这个非空指针将会引起页错误。
    //可被用来验证没有初始化的链表节点。可以区分是被list删除的还是本身没有初始化的，便于调试。
}

static inline void __list_del(struct list_head *prev, struct list_head *next)
{
    next->prev = prev;
    WRITE_ONCE(prev->next, next);
}

static inline __list_del_entry(struct list_head *entry)
{
    if(!__list_del_entry_valid(entry))
        return;
    
    __list_del(entry->prev, entry->next);
}

1.3 遍历链表中节点

list_for_each_entry宏实际上是一个for循环，利用传入的pos作为循环变量，从表头head开始，逐项向后（next）移动pos，直到又回到head。

/**
 * list_for_each_entry - iterate over list of given type
 * @pos: the type * to use as a loop cursor
 * @head: the head for your list.
 * @member: the name of the list_struct within the struct
 */
#define list_for_each_entry(pos, head, member) \
    for(pos = list_entry((head)->next, typeof(*pos), member); \
        prefetch(pos->member.netx), &pos->member != (head); \
        pos = list_entry(pos->member.next, typeof(*pos), member))

// prefetch是告诉CPU哪些元素有可能马上要用到，预取一下，可以提高速度，用于预期以提高遍历速度

// 从指针ptr中获取所在结构体类型type，并返回结构体指针。
// member是结构体中双向链表节点的成员名。注意，不能用于空链表和未初始化的链表。
/**
 * list_entry - get the struct for this entry
 * @ptr:  the &struct list_head pointer
 * @type: the type of the struct this is embeded in
 * @member: the name of the list_struct within the struct 
 */
#define list_entry(ptr, type, member) container_of(ptr, type, member)

//container_of用于根据一个结构体变量中的一个域成员变量的指针来获取指向整个结构体变量的指针

/**
 * container_of - cast a member of a structrue out to the containing structure
 * @ptr:    the pointer to the member
 * @type:   the type of the container struct this is embeded 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型指针，指针指向的地址为0，也就是从0开始的一块存储空间映射为TYPE对象
//然后对MEMBER进行取地址，由于起始地址为0，也就获得MEMBER成员在TYPE中的偏移量，强制无符号整型
#define offsetof(TYPE, MEMBER)  ((size_t)&((TYPE *)0)->MEMBER)

提示：对于container_of，offsetof宏，是Linux中常用的两个宏，用来处理结构体与结构体成员之间的指针转化。可以多加熟练与使用，在很多场景都可以得到应用。需要包含头文件<stddef.h>。