Video在线视频

大家好 我们今天来讲一下Linux内核的源码入门-双链表

那么首先我们来看一下链表的演化

在C语言中一个基本的双向链表定义如下

这个链表画出图来的话是这样的它有前驱（prev）和后继（next)

那么这两个指针可以从两个方向来遍历链表

从而使得遍历链表的效率能提升

那么为什么说我们要把双链表作为一个重点的介绍呢

实际上如果对一个双链表我们减少一个指针域它自然就退化成为一个单链表

那么如果我们只能对链表的首尾进行插入或者删除操作呢

它就演变成一个队结构

如果只能对链表的头进行插入或删除操作它就退化为栈结构

如果前驱和后继表示左右孩子的话 它就演变为一颗二叉树

所以说呢Linux内核为什么把

循环双链表作为一个基本的类型

在Linux内核的源代码的很多的数据结构里头呢

都可以看到这个结构像整型一样来使用

那么在Linux内核中是如何对链表进行定义和使用的呢

内核中对链表的实现方式与众不同

它没有包含数据 具体的定义如下

那么这个链表结构常常被嵌入到其他结构中

比如说我们这样一个使用的方式

那么在这个结构中我们看到呢

list域隐藏了链表的指针特性

以struct list_head为基本的对象

内核对链表进行插入删除

合并以及遍历等等各种各样的操作

这些操作都位于内核的头文件list.h中

我们在这里主要地介绍

链表的一些基本的操作

首先来看一下链表的初始化

我们如何对链表进行初始化

struct list_head只定义了链表的头节点 并没有专门定义链表头

那么一个链表结构是如何建立起来呢

内核代码list.h中定义了两个宏

其中第一个宏是仅初始化

第二个宏声明并初始化

当我们调用LIST_HEAD()声明一个名为name的链表头时

它的前后指针都初始化为指向自己

这样我们就有了一个空的链表

那么如何判断一个链表为空

我们通过下面这个简单的函数就可以判断一个链表是否为空

那么内核中如何给链表插入一个结点

它的实现也比较特殊

我们刚才讲我们可以给链表的头部插入就成为一个栈

尾部插入它就成为一个队列结构

那么Linux代码中是不是分别实现了这两个函数呢

实际上呢它的实现也比较特殊

它没有去分别给它们写代码 而是抽象出了一个通用的插入函数

它叫做内部函数也就是说在函数名前加了两个下划线

我们看一下__list_add() 这个函数是如何实现的

在这个函数中分别有三个参数

一个参数就是新插入的节点

那么另外一个参数就是前指针 另外一个参数就是后指针

我们看这张图在前后指针之间插入一个新的节点呢

实际上是非常简单的

那么这个代码有四条语句都是赋值语句

就实现了一个把新节点插入到

前后两个节点中间

它们实现一个通用的插入函数以后呢

我们的头插和尾插就直接调用这个函数

这个通用的插入函数它有三个参数

我们这个头插和尾插呢

内核对外提供的一个接口

那么它是对这个通用函数的一个封装 变为了两个参数

这一点作为读者我们来仔细的来体会一下

在这个函数的前面我们看见有两个关键字static

static加在函数前表示这个函数是静态函数

什么是静态函数 实际上是对函数作用域的一种限制

也就是说函数的作用域仅限于本文件

所以说static 具有信息隐藏的作用

而关键字inline加在函数前说明这个函数对编译程序是可见的

也就是说编译程序在调用这个函数的时候就立即展开这个函数

那么 我们如何来遍历一个双链表呢

实际上内核代码中定义了如下的一个宏

看这个宏实际上是非常简单的

只要指针不断的向下走就可以了

当头尾相遇的时候我们的遍历就结束

但是这个链表只是找到一个节点在链表中的偏移位置

如图a所示

那么如何通过这个偏移获得节点的起始地址

从而引用节点中的各个域呢

内核中定义了晦涩难懂的list_entry这个宏

我们看这个宏是比较复杂

那么如何去理解这个宏 这个宏到底达到什么的目的 我们看图b

其中这个宏有三个参数

三个参数分别代表什么样的含义呢 第一个参数就是指针

那么这个指针它代表什么含义 它是成员member所在的位置

那么type代表这个结构体的类型

member是这个结构体的一个成员

那么通过这样一个宏达到什么目的呢

我们最后可以获得这个节点的起始地址

那么是如何达到呢

当我们把这个宏展开以后 我们看到它变得非常的清晰

在这个宏的外边是几个强制类型的转换

在里边实际上是一个减法操作

那么这个减法操作就是绝对值

减去这个偏移量得到的 就是这个节点的起始地址

那么具体来看它是怎么得到的呢

首先这个绝对值是怎么得到的呢

我们将ptr强制转换成一个char类型

实际上就是这个指针的绝对的位置

那么然后这个member成员我们求它的偏移量 怎么求它的偏移量呢

我们给它前面强制转换零 从零开始求它的位置

那么这样的话求出来一个是绝对值 一个是偏移量

二者一减的话我们就得到这个节点的起始地址

如何把Linux内核中的代码移植到用户空间

我们说Linux内核中不仅提供了双链表的各种接口函数

还提供了哈希表以及RCU锁的接口函数

大约有70个左右

这些接口进行适当改造后就可以移植到用户空间来使用

从而使得内核经典的设计理念和代码具有可移植性

更多函数的宏实现查看list.h中的代码

那么更多函数的分析可以查看内核之旅网站上的相关文章

当我们对Linux内核作一个基本的介绍以后呢 我们希望呢

能够真正的感受Linux

那么在我们Linux内核之旅网站上有一系列的文章

其中有一个栏目叫新手上路

它有一系列的入门文章

其中的“电子杂志”栏目是关于内核研究和学习的资料

其中第一期“走入Linux内核的世界”

涉猎了操作系统的来龙去脉 大家携手步入Linux的世界

怎么样去做呢 我们可以下载代码亲手搭建自己的实验系统

也许你希望自己从零开始写一个自己的操作系统

那么在我的学生中也有学生有这样的设想

所以他做一个毕业设计就叫X86架构的内核代码实现

其中不仅仅有代码而且有完整的文档

放在github上大家可以去参考并按着他的文档

一步步的感受一个操作系统

如何从0行代码到最后完成自己想要的功能

我们对Linux内核的学习做一个简单的指南

那么如何学习Linux内核呢

首先要和Linux交朋友

那怎么样去交朋友呢先使用Linux

然后呢产生疑问 比如说我创建了一个进程

那么这个进程到底是怎么创建的

创建以后Linux到底是怎么去调度的

这个时候呢就有看源码的愿望

但是这个源码也太庞大了 Linux的源码有几千万行代码

我怎么样入手呢 实际上我们先要

了解整个Linux内核的架构

然后找一个切入点

进入细节 但是Linux内核源码的版本非常的多

现在有近上千个内核版

到底该找哪一个版本呢 我们的建议呢

是通过低版本来理解原理 高版本呢理解实现

在这么多年的教学和科研中呢 我们积累了大量的资料

想把这个分享出来 所以我们建立了Linux内核之旅的微信平台

目前在这个平台上已经发布了700多篇文章

同时我们把《Linux操作系统原理应用》这本书呢

录成了全程的讲课视频

发布在蓝墨云版课上 开设了开放分享班391045

如果希望更多的通过视频了解的同学可以加入这个班

但是所有的教材 参考资料 网站上的东西仅仅是一种外援

只有你真正的去

动手实践并进行总结形成自己的智慧后才能

真正的进入Linux内核

谢谢大家