Linux 内核通用链表学习小结

Z时代
2024-01-10
分类：综合

描述

在linux内核中封装了一个通用的双向链表库，这个通用的链表库有很好的扩展性和封装性，它给我们提供了一个固定的指针域结构体，我们在使用的时候，只需要在我们定义的数据域结构体中包含这个指针域结构体就可以了，具体的实现、链接并不需要我们关心，只要调用提供给我们的相关接口就可以完成了。

传统的链表结构


struct node{
  int key;
  int val;
  node* prev;
  node* next;
 }

linux 内核通用链表库结构

提供给我们的指针域结构体：


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

我们只需要包含它就可以：


struct node{
  int val;
  int key;
  struct list_head* head;
}

可以看到通过这个 list_head 结构就把我们的数据层跟驱动层分开了，而内核提供的各种操作方法接口也只关心 list_head 这个结构，也就是具体链接的时候也只链接这个list_head 结构，并不关心你数据层定义了什么类型.

一些接口宏定义


//初始化头指针
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
  struct list_head name = LIST_HEAD_INIT(name)
//遍历链表
#define __list_for_each(pos, head) \
  for (pos = (head)->next; pos != (head); pos = pos->next)
//获取节点首地址(不是list_head地址，是数据层节点首地址)
#define list_entry(ptr, type, member) \
  container_of(ptr, type, member)
//container_of在Linux内核中是一个常用的宏，用于从包含在某个
//结构中的指针获得结构本身的指针，通俗地讲就是通过结构体变
//量中某个成员的首地址进而获得整个结构体变量的首地址
#define container_of(ptr, type, member) ({     \
    const typeof( ((type *)0)->member ) *__mptr = (ptr);  \
    (type *)( (char *)__mptr - offsetof(type,member) );})
#define offsetof(s,m) (size_t)&(((s *)0)->m)

使用方式


typedef struct node{
  int val;
  int key;
  struct list_head* list;
}node;
//初始化头指针
LIST_HEAD(head);
//创建节点
node* a = malloc(sizeof(node));
node* b = malloc(sizeof(node));
//插入链表 方式一
list_add(&a->list,&head);
list_add(&b->list,&head);
//插入链表 方式二
list_add_tail(&a->list,&head);
list_add_tail(&b->list,&head);
//遍历链表  
struct list_head* p;
struct node* n;
__list_for_each(p,head){
  //返回list_head地址，然后再通过list_head地址反推
  //节点结构体首地址.
  n = list_entry(pos,struct node,list);
}

list_add 接口，先入后出原则，有点类似于栈

list_add-先入后出模式

list_add_tail 接口，先入先出原则，有点类似于fifo

list_add-先入先出模式

我们的链表节点，实际在内存中的展示形态

节点描述

可以看到最终的形态是，通过指向每个结构体里面的 list_head 类型指针，然后把它们串联起来的

list_entry 接口，通过结构体变量某个成员的地址，反推结构体首地址，就像 __list_for_each 接口只返回 list_head 地址，所以我们要通过这个成员地址在去获取它本身的结构体首地址，底层实现方法 container_of 宏

反推结构体首地址

举个例子

这个例子包括简单的增、删、遍历


#include <linux/kernel.h> 
#include <linux/module.h> 
#include <linux/init.h> 
#include <linux/slab.h> 
#include <linux/list.h> 
MODULE_LICENSE("GPL"); 
MODULE_AUTHOR("David Xie"); 
MODULE_DESCRIPTION("List Module"); 
MODULE_ALIAS("List module"); 
struct student //代表一个实际节点的结构 
{ 
  char name[100]; 
  int num; 
  struct list_head list;  //内核链表里的节点结构 
}; 
struct student *pstudent;    
struct student *tmp_student; 
struct list_head student_list;  
struct list_head *pos; 
int mylist_init(void) 
{ 
  int i = 0; 
  //初始化一个链表，其实就是把student_list的prev和next指向自身 
  INIT_LIST_HEAD(&student_list);  
  pstudent = kmalloc(sizeof(struct student)*5,GFP_KERNEL);//向内核申请5个student结构空间 
  memset(pstudent,0,sizeof(struct student)*5); //清空，这两个函数可以由kzalloc单独做到 
  for(i=0;i<5;i++) 
  { //为结构体属性赋值 
    sprintf(pstudent[i].name,"Student%d",i+1); 
    pstudent[i].num = i+1;  
    //加入链表节点，list_add的话是在表头插入，list_add_tail是在表尾插入 
    list_add( &(pstudent[i].list), &student_list);//参数1是要插入的节点地址，参数2是链表头地址 
  }  
  list_for_each(pos,&student_list) //list_for_each用来遍历链表，这是个宏定义 
                   //pos在上面有定义 
  { 
    //list_entry用来提取出内核链表节点对应的实际结构节点，即根据struct list_head来提取struct student 
    //第三个参数list就是student结构定义里的属性list 
    //list_entry的原理有点复杂，也是linux内核的一个经典实现，这个在上面那篇链接文章里也有讲解 
    tmp_student = list_entry(pos,struct student,list); 
    //打印一些信息，以备验证结果 
    printk("<0>student %d name: %s/n",tmp_student->num,tmp_student->name); 
  } 
  return 0; 
} 
void mylist_exit(void) 
{   
  int i ; 
  /* 实验：将for换成list_for_each来遍历删除结点，观察要发生的现象，并考虑解决办法 */ 
  for(i=0;i<5;i++) 
  { 
    //额，删除节点，只要传个内核链表节点就行了 
    list_del(&(pstudent[i].list));    
  } 
  //释放空间 
  kfree(pstudent); 
} 
module_init(mylist_init); 
module_exit(mylist_exit);