未加星标

Linux 内核通用链表学习小结

字体大小 | |
[运维安全 所属分类 运维安全 | 发布者 店小二04 | 时间 | 作者 红领巾 ] 0人收藏点击收藏

描述

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 接口,先入后出原则,有点类似于栈

Linux 内核通用链表学习小结
list_add-先入后出模式

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

Linux 内核通用链表学习小结
list_add-先入先出模式

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

Linux 内核通用链表学习小结
节点描述

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

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

Linux 内核通用链表学习小结
反推结构体首地址
举个例子

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

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

结束

linux 内核提供的这个通用链表库里面还有很多其他的接口,这里没有详细的一一举例,有兴趣的可以自己去看看,在源码包 include/linux/list.h 文件里面,不过通过阅读一些源代码确实对我们也有很大的提高,可以看看高手是如何去设计并实现,还可以学到一些技巧以及对代码细节的掌握~~.

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。

本文运维安全相关术语:linux服务器代维 linux服务器搭建 运维管理 运维工程师 企业安全文章 企业安全管理 cf安全系统检测到游戏数据异常

主题: LinuxLinux内核DU数据供给删除AUUTAUTTI
分页:12
转载请注明
本文标题:Linux 内核通用链表学习小结
本站链接:http://www.codesec.net/view/568302.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 运维安全 | 评论(0) | 阅读(17)