[数据结构与算法]【Linux】内核代码阅读 list_entry()

内核代码学习

list_entry()

作用：获取ptr所属结构体的首地址

#define list_entry(ptr, type, member) \
       ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
// ptr：指向list_node类型的指针
// type：一个结构体
// member：结构type中的一个域

使用示例

• ptr为head.member
• ptr所属结构体为numlist
  • 获取ptr所属结构体的首地址也就是获取head

// 链表
struct list_node
{
    struct list *prev,next;
}

struct numlist
{
     int num;
     struct list_node member;
};

// 使用
struct numlist head;

struct numlist *p = list_entry(head.member,struct numblist,member)
    
// p 的地址就是 head 的地址
p.num;//相当于head.num

为什么这么做？

• 因为遍历的时候是用head.member在遍历，此时是赋值给某个变量例如pos，而没有head的首地址，因为要取出num所以需要首地址

疑问

明明有head，为什么要用head.member去获得head的地址呢？

• 跟遍历链表有关
  • 遍历链表是在遍历member，而此时并没有head的地址，这时候要访问head中的其他地址时则需要先获得head的首地址

例子：Linux内核模块，用以创建、增加和遍历一个双向链表

// 涉及的数据结构和宏
struct list_head{
	struct list_head *next,*prev;
}

#define INIT_LIST_HEAD(name) {&(name),&(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_tail(struct list_head *new,struct list_head *head){
    __list_add(new,head.prev,head);
}

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

#include<linux/kernel.h>
#include<linux/module.h>
#include<linux/slab.h>
#include<linux/list.h>

MODULE_LICENSE("GPL");
MODULE_AUTHOR("X");
    
#define N 10 //链表节点数
struct numlist{
    int num; //数据
    struct list_head list; // 指向双向链表前后指针
}

struct numlist numhead; //头节点

static int __init doublelist_init(void){
    // 初始化头结点
    struct numlist *listnode;
    struct list_head *pos;
    struct numlist *p;
    int i;
    
    printk("doublelist is starting...\n");
    INIT_LIST_HEAD(&numhead.list);
    
    // 建立N个结点，依次加入到链表中
    for(i = 0; i < N; i++) {
        listnode = (struct numlist *)kmalloc(sizeof(struct numlist),GFP_KERNEL); //kmalloc()在内核空间申请内存，类似于malloc
        listnode.num = i +1;
        list_add_tail(&listnode.list,&numhead.list);
        printk("Node %d has added to the doublelist... \n",i+1);
    }
    
    // 遍历：list_entry()作用的体现
    list_for_each(pos,&numhead.list){
        // 在遍历过程中并没有获得numlist类型的地址，所以只能通过该函数来获得
        p = list_entry(pos,struct numlist,list);
        printk("Node %d's data %d\n",i,p->num);
        i++;
    }
}

解读代码

#define list_entry(ptr, type, member) \
       ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

list_entry(head.member,struct numblist,member)
// 即
((struct numblist *)((char *)(head.member)-(unsigned long)(&((struct numblist *)0)->member))) 

1.后面的减数

(unsigned long)(&((struct numblist *)0)->member)))
(struct numblist *)0)->member：member在struct numblist中的偏移地址

• 例如：struct numblist node，现在要访问该结构体的member地址
  • node.member
  • 或者 &(node + (struct numblist *)0)->member)
    • 即node + (struct numblist *)0)->member是偏移量

((struct numblist *)((char *)(head.member)-(unsigned long)(&((struct numblist *)0)->member)))

• 按上面的推导，即得到head.member所在的节点head的首地址