Linux 内核list_head 学习

简介: Linux 内核list_head 学习(一) http://www.cnblogs.com/zhuyp1015/archive/2012/06/02/2532240.html 在Linux内核中,提供了一个用来创建双向循环链表的结构 list_head。

Linux 内核list_head 学习(一)

http://www.cnblogs.com/zhuyp1015/archive/2012/06/02/2532240.html

Linux内核中,提供了一个用来创建双向循环链表的结构 list_head。虽然linux内核是用C语言写的,但是list_head的引入,使得内核数据结构也可以拥有面向对象的特性,通过使用操作list_head 的通用接口很容易实现代码的重用,有点类似于C++的继承机制(希望有机会写篇文章研究一下C语言的面向对象机制)。下面就是kernel中的list_head结构定义:

struct list_head {

  struct list_head *next, *prev;

};

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

需要注意的一点是,头结点head是不使用的,这点需要注意。

使用list_head组织的链表的结构如下图所示:

   

list_head这个结构看起来怪怪的,它竟没有数据域!所以看到这个结构的人第一反应就是我们怎么访问数据?

其实list_head不是拿来单独用的,它一般被嵌到其它结构中,如:

struct file_node{

  char c;

  struct list_head node;

};

此时list_head就作为它的父结构中的一个成员了,当我们知道list_head的地址(指针)时,我们可以通过list.c提供的宏 list_entry 来获得它的父结构的地址。下面我们来看看list_entry的实现:

#define list_entry(ptr,type,member)\

  container_of(ptr,type,member)

   

#define offsetof(TYPE,MEMBER) ((size_t)&((TYPE *)0)->MEMBER)

#define container_of(ptr,type,member) ( {\

  const typeof( ((type*)0)->member ) *__mptr=(ptr);\

  (type*)( (char*)__mptr - offsetof(type,member) );} )

   

这里涉及到三个宏,还是有点复杂的,我们一个一个来看:

#define offsetof(TYPE,MEMBER) ( (size_t)& ((TYPE *)0-> MEMBER )

我们知道 0 地址内容是不能访问的,但 0地址的地址我们还是可以访问的,这里用到一个取址运算符

(TYPE *)0 它表示将 0地址强制转换为TYPE类型,((TYPE *)0-> MEMBER 也就是从0址址找到TYPE 的成员MEMBER

我们结合上面的结构来看

struct file_node{

  char c;

  struct list_head node;

};

将实参代入 offset( struct file_node, node );最终将变成这样:

( (size_t) & ((struct file_node*)0-> node );这样看的还是不很清楚,我们再变变:

struct file_node *p = NULL;

& p->node;

这样应该比较清楚了,即求 p 的成员 node的地址,只不过p 0地址,从0地址开始算成员node的地址,也就是成员 node 在结构体 struct file_node中的偏移量。offset宏就是算MEMBERTYPE中的偏移量的。

我们再看第二个宏

#define container_of(ptr,type,member) ( {\

  const typeof( ((type*)0)->member ) *__mptr=(ptr);\

  (type*)( (char*)__mptr - offsetof(type,member) );} )

这个宏是由两个语句组成,最后container_of返回的结果就是第二个表达式的值。这里__mptr为中间变量,这就是list_head指针类型,它被初始化为ptr的值,而ptr就是当前所求的结构体中list_head节点的地址。为什么要用中间变量,这是考虑到安全性因素,如果传进来一个ptr++,所有ptr++放在一个表达式中会有副作用,像 (p++)+(p++)之类。

(char*)__mptr 之所以要强制类型转化为char是因为地址是以字节为单位的,而char的长度就是一个字节。

container_of的值是两个地址相减,

刚说了__mptr是结构体中list_head节点的地址,offset宏求的是list_head节点MEMBER在结构体TYPE中的偏移量,那么__mptr减去它所在结构体中的偏移量,就是结构体的地址。

所以list_entry(ptr,type,member)宏的功能就是,由结构体成员地址求结构体地址。其中ptr 是所求结构体中list_head成员指针,type是所求结构体类型,member是结构体list_head成员名。通过下图来总结一下:

   

   

继续列举一些双链表的常用操作:

双向链表的遍历——list_for_each

//注:这里prefetch gcc的一个优化选项,也可以不要

#define list_for_each(pos, head) \

         for (pos = (head)->next; prefetch(pos->next), pos != (head); \

                 pos = pos->next)

   

生成双向链表的头结点——LIST_HEAD()

LIST_HEAD() -- 生成一个名为name的双向链表头节点

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

  list->prev = list;

}

双向链表的插入操作 -- list_add()

new所代表的结构体插入head所管理的双向链表的头节点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;

}

list中删除结点——list_del()

static inline void list_del(struct list_head *entry)

{

  __list_del(entry->prev, entry->next);

  entry->next = LIST_POISON1;

  entry->prev = LIST_POISON2;

}

static inline void __list_del(struct list_head * prev, struct list_head * next)

{

  next->prev = prev;

  prev->next = next;

}

   

判断链表是否为空(如果双向链表head为空则返回真,否则为假)——list_empty()

static inline int list_empty(const struct list_head *head)

{

  return head->next == head;

}

   

make it simple, make it happen

 

nkbai
+关注
目录
打赏
0
0
0
0
8
分享
相关文章
|
26天前
|
零基础保姆级教程!手把手教你免费玩转Linux CentOS安装+学习环境搭建(附避坑指南)
本文详细介绍了在VMware虚拟机中安装CentOS 6.8的全过程。首先,需确保已安装VMware并开启V-CPU虚拟化功能,可通过BIOS设置或使用LeoMoon CPU-V工具检测。接着,下载CentOS镜像文件,并在VMware中新建虚拟机,配置CPU、内存、硬盘等参数。最后,加载ISO镜像启动虚拟机,按照提示完成CentOS的安装,包括语言、键盘、存储方式、地区、密码设置及硬盘分区等步骤。安装完成后,以root用户登录即可进入系统桌面,开始学习Linux命令和操作。
108 12
零基础保姆级教程!手把手教你免费玩转Linux CentOS安装+学习环境搭建(附避坑指南)
Linux 内核源码分析---proc 文件系统
`proc`文件系统是Linux内核中一个灵活而强大的工具,提供了一个与内核数据结构交互的接口。通过本文的分析,我们深入探讨了 `proc`文件系统的实现原理,包括其初始化、文件的创建与操作、动态内容生成等方面。通过对这些内容的理解,开发者可以更好地利用 `proc`文件系统来监控和调试内核,同时也为系统管理提供了便利的工具。
55 16
Intel Linux 内核测试套件-LKVS介绍 | 龙蜥大讲堂104期
《Intel Linux内核测试套件-LKVS介绍》(龙蜥大讲堂104期)主要介绍了LKVS的定义、使用方法、测试范围、典型案例及其优势。LKVS是轻量级、低耦合且高代码覆盖率的测试工具,涵盖20多个硬件和内核属性,已开源并集成到多个社区CICD系统中。课程详细讲解了如何使用LKVS进行CPU、电源管理和安全特性(如TDX、CET)的测试,并展示了其在实际应用中的价值。
Ubuntu20.04搭建嵌入式linux网络加载内核、设备树和根文件系统
使用上述U-Boot命令配置并启动嵌入式设备。如果配置正确,设备将通过TFTP加载内核和设备树,并通过NFS挂载根文件系统。
166 15
深入探索Linux内核的内存管理机制
本文旨在为读者提供对Linux操作系统内核中内存管理机制的深入理解。通过探讨Linux内核如何高效地分配、回收和优化内存资源,我们揭示了这一复杂系统背后的原理及其对系统性能的影响。不同于常规的摘要,本文将直接进入主题,不包含背景信息或研究目的等标准部分,而是专注于技术细节和实际操作。
Linux操作系统的内核优化与性能调优####
本文深入探讨了Linux操作系统内核的优化策略与性能调优方法,旨在为系统管理员和高级用户提供一套实用的指南。通过分析内核参数调整、文件系统选择、内存管理及网络配置等关键方面,本文揭示了如何有效提升Linux系统的稳定性和运行效率。不同于常规摘要仅概述内容的做法,本摘要直接指出文章的核心价值——提供具体可行的优化措施,助力读者实现系统性能的飞跃。 ####

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等