Linux 内核数据结构:双向链表

Linux 内核提供一套双向链表的实现,你可以在 include/linux/list.h 中找到。我们以双向链表着手开始介绍 Linux 内核中的数据结构 ,因为这个是在 Linux 内核中使用最为广泛的数据结构,具体你可以 查看 这里。

首先让我们看一下主要的结构体:

你可以看到其与常见的结构体实现有显著不同,比如 glib 中所使用到的双向链表实现。

通常来说,链表结构体要包括一个指向数据的指针,不过 Linux 内核的链表却不包含此实现。那么首要的疑问:链表是用什么方式存储数据的?。Linux 内核所实现的是一种被称为侵入式的链表(Intrusive list),这种链表并不在链表结构中包含数据,而仅提供用于维护前向与后向访问结构的指针。这种实现方式使得链表数据结构非常通用,因为它并不需要关注链表所维护的具体数据类型。

比如:

接下来让我们看一些内核使用 list_head 的具体例子。正如在前文所述的,Linux 内核中诸多模块都使用了 list_head。这里我们以内核杂项字符设备驱动(miscellaneous character drivers)部分实现为例。驱动的 API 在 drivers/char/misc.c 中,其实现了简单硬件外设以及虚拟设备的驱动,这个驱动共享主设备号(Major number):

每个设备有自己的次设备号,具体可以看这个列子:

现在我们看看设备驱动是如何使用链表维护设备列表的,首先,我们看一下 miscdevice 的 struct 定义:

可以看到 miscdevice 的第四个成员 list ,这个就是用于维护已注册设备链表的结构。在源代码文的首部,我们可以看到以下定义:

这个定义宏展开,可以看到是用于定义 list_head 类型变量:

LIST_HEAD_INIT 这个宏用于对定义的变量进行双向指针的初始化:

现在我看可以看一下函数 misc_register 是如何进行设备注册的。首先是用 INIT_LIST_HEADmiscdevice->list 成员变量进行初始化:

这个操作与 LIST_HEAD_INIT 宏一致:

接下来,在通过函数 device_create 进行设备创建,同时将设备添加到 Misc 设备列表中:

内核的 list.h 文件提供向链表添加节点的 API,这里是添加操作的实现:

函数实现很简单,就是入参转换为三个参数后调用内部 __list_add

  • new – 新节点;
  • head – 新节点插入的双向链表头;
  • head->next – 链表头的下一个节点;

_list_add 函数的实现更加简单:

这里设置了新添加结点的 prevnext 指针,通过这些操作,就将先前使用 LIST_HEAD_INIT 所定义的 misc 链表的双向指针与 miscdevice->list 结构关联起来。

这里还有一个问题,就是如何获取链表中的数据,list_head 提供了一个特殊的宏用于获取数据指针。

这里有三个参数

  • ptr:list_head 结构指针
  • type:数据对应的 struct 类型
  • member:数据中 list_head 成员对应的成员变量名

举例如下:

接下来我们就够访问 miscdevice 的各个成员,如 p->minorp->name 等等,我们看一下 list_entry 的实现:

其实现非常简单,就是使用入参调用 container_of 宏,宏的实现如下:

注意,宏使用了大括号表达式,对于大括号表达式,编译器会展开所有表达式,同时使用最后一个表达式的结果进行返回。

举个例子:

输出结果为 2

另一个关键是 typeof 关键字,这个非常简单,这个正如它的名字一样,这个关键字返回的结果是变量的类型。当我第一次看到这个宏时,最让我觉得奇怪的是表达式 ((type*)0) 中的 0 值,实际上,使用 0 值作为地址这个是成员变量取得 struct 内相对偏移地址的巧妙实现,我们再来看个例子:

输出结果为 0x5

还有一个专门用于获取结构体中某个成员变量偏移的宏,其实现与前面提到的宏非常类似:

这里对 container_of 宏做个综述,container_of 宏通过 struct 中的 list_head 成员返回 struct 对应数据的内存地址。在宏的第一行定义了指向 list_head 成员的指针 __mptr ,并将 ptr 地址赋给 __mptr 。从技术实现的角度来看,实际并不需要这一行定义,但这个对于类型检查而言非常有意义。这一行代码确保结构体( type )中存在 member 对应的成员。第二行使用 offsetoff 宏计算出包含 member 的结构体所对应的内存地址,就是这么简单。

当然 list_addlist_entry 并非是 <linux/list.h> 中的全部函数,对于双向链表 list_head ,内核还提供了以下的接口:

  • list_add
  • list_add_tail
  • list_del
  • list_replace
  • list_move
  • list_is_last
  • list_empty
  • list_cut_position
  • list_splice

未了,需要说的是,内核代码中并不仅仅只有上述这些接口。

1 4 收藏 1 评论

关于作者:Alick

这个码农很懒,啥也没有留下. 个人主页 · 我的文章 · 29 ·  

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部