Linux内核代码中常用的数据结构

Linux内核代码中广泛使用了数据结构和算法,其中最常用的两个是链表和红黑树。

链表

Linux内核代码大量使用了链表这种数据结构。链表是在解决数组不能动态扩展这个缺陷而产生的一种数据结构。链表所包含的元素可以动态创建并插入和删除。

链表的每个元素都是离散存放的,因此不需要占用连续的内存。链表通常由若干节点组成,每个节点的结构都是一样的,由有效数据区和指针区两部分组成。有效数据区用来存储有效数据信息,而指针区用来指向链表的前继节点或者后继节点。因此,链表就是利用指针将各个节点串联起来的一种存储结构。

(1)单向链表

单向链表的指针区只包含一个指向下一个节点的指针,因此会形成一个单一方向的链表,如下代码所示。

struct list {int data;   /*有效数据*/struct list *next; /*指向下一个元素的指针*/
};

如图所示,单向链表具有单向移动性,也就是只能访问当前的节点的后继节点,而无法访问当前节点的前继节点,因此在实际项目中运用得比较少。

单向链表示意图

(2)双向链表

如图所示,双向链表和单向链表的区别是指针区包含了两个指针,一个指向前继节点,另一个指向后继节点,如下代码所示。

struct list {int data;   /*有效数据*/struct list *next; /*指向下一个元素的指针*/struct list *prev; /*指向上一个元素的指针*/
};

双向链表示意图(链表头应该是next指向节点)

(3)Linux内核链表实现

单向链表和双向链表在实际使用中有一些局限性,如数据区必须是固定数据,而实际需求是多种多样的。这种方法无法构建一套通用的链表,因为每个不同的数据区需要一套链表。

为此,Linux内核把所有链表操作方法的共同部分提取出来,把不同的部分留给代码编程者自己去处理。

Linux内核实现了一套纯链表的封装,链表节点数据结构只有指针区而没有数据区,另外还封装了各种操作函数,如创建节点函数、插入节点函数、删除节点函数、遍历节点函数等。

Linux内核链表使用 struct list_head 数据结构来描述。

<include/linux/types.h>struct list_head {struct list_head *next, *prev;
};

struct list_head数据结构不包含链表节点的数据区,通常是嵌入其他数据结构,如struct page数据结构中嵌入了一个lru链表节点,通常是把page数据结构挂入LRU链表。

<include/linux/mm_types.h>struct page {...struct list_head lru;...
}

链表头的初始化有两种方法,一种是静态初始化,另一种动态初始化。

把next和prev指针都初始化并指向自己,这样便初始化了一个带头节点的空链表。

<include/linux/list.h>/*静态初始化*/
#define LIST_HEAD_INIT(name) { &(name), &(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()是把一个节点添加到表头,list_add_tail()是插入表尾。

<include/linux/list.h>void list_add(struct list_head *new, struct list_head *head)
list_add_tail(struct list_head *new, struct list_head *head)

遍历节点的接口函数。

#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)

这个宏只是遍历一个一个节点的当前位置,那么如何获取节点本身的数据结构呢?这里还需要使用list_entry()宏。

#define list_entry(ptr, type, member) \container_of(ptr, type, member)
//container_of()宏的定义在kernel.h头文件中。
#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)

其中offsetof()宏是通过把0地址转换为type类型的指针,然后去获取该结构体中member成员的指针,也就是获取了member在type结构体中的偏移量。最后用指针ptr减去offset,就得到type结构体的真实地址了。

下面是遍历链表的一个例子。

<drivers/block/osdblk.c>static ssize_t class_osdblk_list(struct class *c,struct class_attribute *attr,char *data)
{int n = 0;struct list_head *tmp;list_for_each(tmp, &osdblkdev_list) {struct osdblk_device *osdev;osdev = list_entry(tmp, struct osdblk_device, node);n += sprintf(data+n, "%d %d %llu %llu %s\n",osdev->id,osdev->major,osdev->obj.partition,osdev->obj.id,osdev->osd_path);}return n;
}

红黑树

红黑树(Red Black Tree)被广泛应用在内核的内存管理和进程调度中,用于将排序的元素组织到树中。红黑树被广泛应用在计算机科学的各个领域中,它在速度和实现复杂度之间提供一个很好的平衡。

红黑树是具有以下特征的二叉树:

  • 每个节点或红或黑。
  • 每个叶节点是黑色的。
  • 如果结点都是红色,那么两个子结点都是黑色。
  • 从一个内部结点到叶结点的简单路径上,对所有叶节点来说,黑色结点的数目都是相同的。

红黑树的一个优点是,所有重要的操作(例如插入、删除、搜索)都可以在O(log n)时间内完成,n为树中元素的数目。

经典的算法教科书都会讲解红黑树的实现,这里只是列出一个内核中使用红黑树的例子,供读者在实际的驱动和内核编程中参考。这个例子可以在内核代码的documentation/Rbtree.txt文件中找到。

#include <linux/init.h>
#include <linux/list.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/slab.h>
#include <linux/mm.h>
#include <linux/rbtree.h>MODULE_AUTHOR("figo.zhang");
MODULE_DESCRIPTION(" ");
MODULE_LICENSE("GPL");struct mytype { struct rb_node node;int key; 
};/*红黑树根节点*/struct rb_root mytree = RB_ROOT;
/*根据key来查找节点*/
struct mytype *my_search(struct rb_root *root, int new){struct rb_node *node = root->rb_node;while (node) {struct mytype *data = container_of(node, struct mytype, node);if (data->key > new)node = node->rb_left;else if (data->key < new)node = node->rb_right;elsereturn data;}return NULL;}/*插入一个元素到红黑树中*/int my_insert(struct rb_root *root, struct mytype *data){struct rb_node **new = &(root->rb_node), *parent=NULL;/* 寻找可以添加新节点的地方 */while (*new) {struct mytype *this = container_of(*new, struct mytype, node);parent = *new;if (this->key > data->key)new = &((*new)->rb_left);else if (this->key < data->key) {new = &((*new)->rb_right);} elsereturn -1;}/* 添加一个新节点 */rb_link_node(&data->node, parent, new);rb_insert_color(&data->node, root);return 0;}static int __init my_init(void)
{int i;struct mytype *data;struct rb_node *node;/*插入元素*/for (i =0; i < 20; i+=2) {data = kmalloc(sizeof(struct mytype), GFP_KERNEL);data->key = i;my_insert(&mytree, data);}/*遍历红黑树,打印所有节点的key值*/for (node = rb_first(&mytree); node; node = rb_next(node)) printk("key=%d\n", rb_entry(node, struct mytype, node)->key);return 0;
}static void __exit my_exit(void)
{struct mytype *data;struct rb_node *node;for (node = rb_first(&mytree); node; node = rb_next(node)) {data = rb_entry(node, struct mytype, node);if (data) {rb_erase(&data->node, &mytree);kfree(data);}}
}
module_init(my_init);
module_exit(my_exit);

mytree是红黑树的根节点,my_insert()实现插入一个元素到红黑树中,my_search()根据key来查找节点。内核大量使用红黑树,如虚拟地址空间VMA的管理。

   资料直通车:Linux内核源码技术学习路线+视频教程内核源码

学习直通车:Linuxc/c++高级开发【直播公开课】

零声白金VIP体验卡:零声白金VIP体验卡(含基础架构/高性能存储/golang/QT/音视频/Linux内核)

无锁环形缓冲区

生产者和消费者模型是计算机编程中最常见的一种模型。生产者产生数据,而消费者消耗数据,如一个网络设备,硬件设备接收网络包,然后应用程序读取网络包。

环形缓冲区是实现生产者和消费者模型的经典算法。环形缓冲区通常有一个读指针和一个写指针。读指针指向环形缓冲区中可读的数据,写指针指向环形缓冲区可写的数据。通过移动读指针和写指针实现缓冲区数据的读取和写入。

在Linux内核中,KFIFO是采用无锁环形缓冲区的实现。FIFO的全称是“First In First Out”,即先进先出的数据结构,它采用环形缓冲区的方法来实现,并提供一个无边界的字节流服务。

采用环形缓冲区的好处是,当一个数据元素被消耗之后,其余数据元素不需要移动其存储位置,从而减少复制,提高效率

(1)创建KFIFO

在使用KFIFO之前需要进行初始化,这里有静态初始化和动态初始化两种方式。

<include/linux/kfifo.h>int kfifo_alloc(fifo, size, gfp_mask)

该函数创建并分配一个大小为size的KFIFO环形缓冲区。第一个参数fifo是指向该环形缓冲区的struct kfifo数据结构;第二个参数size是指定缓冲区元素的数量;第三个参数gfp_mask表示分配KFIFO元素使用的分配掩码。

静态分配可以使用如下的宏。

#define DEFINE_KFIFO(fifo, type, size)
#define INIT_KFIFO(fifo)

(2)入列

把数据写入KFIFO环形缓冲区可以使用kfifo_in()函数接口。

int kfifo_in(fifo, buf, n)

该函数把buf指针指向的n个数据复制到KFIFO环形缓冲区中。第一个参数fifo指的是KFIFO环形缓冲区;第二个参数buf指向要复制的数据的buffer;第三个数据是要复制数据元素的数量。

(3)出列

从KFIFO环形缓冲区中列出或者摘取数据可以使用kfifo_out()函数接口。

#define    kfifo_out(fifo, buf, n)

该函数是从fifo指向的环形缓冲区中复制n个数据元素到buf指向的缓冲区中。如果KFIFO环形缓冲区的数据元素小于n个,那么复制出去的数据元素小于n个。

(4)获取缓冲区大小

KFIFO提供了几个接口函数来查询环形缓冲区的状态。

#define kfifo_size(fifo)
#define kfifo_len(fifo)
#define kfifo_is_empty(fifo)
#define kfifo_is_full(fifo)

kfifo_size()用来获取环形缓冲区的大小,也就是最大可以容纳多少个数据元素。kfifo_len()用来获取当前环形缓冲区中有多少个有效数据元素。kfifo_is_empty()判断环形缓冲区是否为空。kfifo_is_full()判断环形缓冲区是否为满。

(5)与用户空间数据交互

KFIFO还封装了两个函数与用户空间数据交互。

#define    kfifo_from_user(fifo, from, len, copied)
#define    kfifo_to_user(fifo, to, len, copied)

kfifo_from_user()是把from指向的用户空间的len个数据元素复制到KFIFO中,最后一个参数copied表示成功复制了几个数据元素。

kfifo_to_user()则相反,把KFIFO的数据元素复制到用户空间。这两个宏结合了copy_to_user()copy_from_user()以及KFIFO的机制,给驱动开发者提供了方便。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/172175.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

el-table添加固定高度height后高度自适应

0 效果 1 添加自定义指令 新建目录src/directive/el-table 在el-table目录下新建文件adaptive.js import { addResizeListener, removeResizeListener } from element-ui/src/utils/resize-event// 设置表格高度const doResize async(el, binding, vnode) > {// 获取表格…

S32K144芯片焊接完成后使用S32DS初次下载无法下载解决方法

一、问题现象如下&#xff0c;S32DS Debug下报错 二、原因&#xff0c;原厂芯片出厂时的FLASH Memory的安全机制是激活的&#xff0c;仿真器是可以连上&#xff0c;但是没法读取Flash Memory的内容 三、解决方法 参考图示&#xff0c;解锁后即可正常Debug

深入理解Java中的转义字符

最近在学习《两周自制脚本语言》这本书&#xff0c;在词法分析的一些复杂的正则中用到了大量的转义字符’\&#xff0c;比如正则字符串中包含了这个部分\\\\\"你知道它是匹配什么的么&#xff1f; 反斜杠在字符串和正则表达式中都有特殊作用。今天让我们来深入理解一下Ja…

数据分享 I 地级市人口和土地使用面积基本情况

数据地址&#xff1a; 地级市人口和土地使用面积基本情况https://www.xcitybox.com/datamarketview/#/Productpage?id394 基本信息. 数据名称: 地级市人口和土地使用面积基本情况 数据格式: ShpExcel 数据时间: 2021年 数据几何类型: 面 数据坐标系: WGS84坐标系 数据…

【计算机毕设经典案例】基于微信小程序的图书管理系统

前言&#xff1a;我是IT源码社&#xff0c;从事计算机开发行业数年&#xff0c;专注Java领域&#xff0c;专业提供程序设计开发、源码分享、技术指导讲解、定制和毕业设计服务 &#x1f449;IT源码社-SpringBoot优质案例推荐&#x1f448; &#x1f449;IT源码社-小程序优质案例…

『力扣刷题本』:移除链表元素

一、题目 给你一个链表的头节点 head 和一个整数 val &#xff0c;请你删除链表中所有满足 Node.val val 的节点&#xff0c;并返回 新的头节点 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,6,3,4,5,6], val 6 输出&#xff1a;[1,2,3,4,5]示例 2&#xff1a; 输入&a…

在spring boot+vue项目中@CrossOrigin 配置了允许跨域但是依然报错跨域,解决跨域请求的一次残酷经历

首先&#xff0c;说一下我们的项目情况&#xff0c;我们项目中后端有一个过滤器&#xff0c;如果必须要登录的接口路径会被拦下来检查&#xff0c;前端要传一个token&#xff0c;然后后端根据这个token来判断redis中这个用户是否已经登录。 if (request.getMethod().equals(&qu…

css 三栏布局的实现?

目录 前言 用法 代码 理解 高质量图片 1. 左侧栏 - 导航菜单 2. 中间栏 - 主要内容 3. 右侧栏 - 小部件和广告 布局的响应式设计 三栏布局在前端页面设计中是一个常见的布局方式&#xff0c;通常包含左侧、中间和右侧三个部分。这种布局方式在多种场景中都很受欢迎&am…

解决Windows出现找不到mfcm90u.dll无法打开软件程序的方法

今天&#xff0c;我非常荣幸能够在这里与大家分享关于mfc90u.dll丢失的5种解决方法。在我们日常使用电脑的过程中&#xff0c;可能会遇到一些软件或系统错误&#xff0c;其中之一就是mfc90u.dll丢失。那么&#xff0c;mfc90u.dll究竟是什么文件呢&#xff1f;接下来&#xff0c…

【表面缺陷检测】钢轨表面缺陷检测数据集介绍(2类,含xml标签文件)

一、介绍 钢轨表面缺陷检测是指通过使用各种技术手段和设备&#xff0c;对钢轨表面进行检查和测量&#xff0c;以确定是否存在裂纹、掉块、剥离、锈蚀等缺陷的过程。这些缺陷可能会对铁路运输的安全和稳定性产生影响&#xff0c;因此及时进行检测和修复非常重要。钢轨表面缺陷…

spring boot利用redis作为缓存

一、缓存介绍 在 Spring Boot 中&#xff0c;可以使用 Spring Cache abstraction 来实现缓存功能。Spring Cache abstraction 是 Spring 框架提供的一个抽象层&#xff0c;它对底层缓存实现&#xff08;如 Redis、Ehcache、Caffeine 等&#xff09;进行了封装&#xff0c;使得在…

微服务-Feign

文章目录 Feign介绍Feign的基本使用自定义Feign的配置Feign性能优化Feign最佳实践 Feign介绍 RestTemplate远程调用存在的问题&#xff1a;代码可读性差&#xff0c;java代码中夹杂url&#xff1b;参数复杂很难维护 String url "http://userservice/user/" order.g…

有一个带头结点的单链表L,设计一个算法使其元素递增有序

有一个带头结点的单链表L&#xff0c;设计一个算法使其元素递增有序 代码思路&#xff1a; 我这里懒得搞那个指针了&#xff0c;直接遍历一遍链表&#xff0c;把链表的元素复制到数组arr里面 对数组A进行一下排序&#xff0c;排完之后再把元素复制到L里面。 至于排序你用啥算…

1820_ChibiOS中的同步消息

全部学习汇总&#xff1a; GreyZhang/g_ChibiOS: I found a new RTOS called ChibiOS and it seems interesting! (github.com) 1. 看到这里提到的这个模型&#xff0c;我在想是不是我一直没有搞定的多核可以利用这个机制来解决。如果是多核&#xff0c;ChibiOS的这种机制是否依…

【java学习—十】捕获异常(2)

文章目录 1. 什么是异常2. 异常处理机制3. 捕获异常总结3.1. try 和 catch3.2. 捕获异常的有关信息&#xff1a;3.3. finally 1. 什么是异常 如果程序运行时&#xff0c;某一行出现异常&#xff0c;将会使程序中断&#xff0c;不在继续执行&#xff0c;举个例子如下&#xff1…

二进制部署kubernetes集群的推荐方式

软件版本&#xff1a; 软件版本containerdv1.6.5etcdv3.5.0kubernetesv1.24.0 一、系统环境 1.1 环境准备 角色IP服务k8s-master01192.168.10.10etcd、containerd、kube-apiserver、kube-scheduler、kube-controller-manager、kubele、kube-proxyk8s-node01后续etcd、conta…

ARM 汇编指令 orreq 的使用

orreq 阅读代码时&#xff0c;发现有个【组合指令】 orreq&#xff0c; orr 一般是 OR&#xff0c;也就是或操作&#xff0c;后面加个 eq 表示什么呢&#xff1f; 比如下面的代码&#xff1a;前面一个操作&#xff0c; tst&#xff0c;好像没做实际的操作&#xff0c;可能影响…

[AutoSAR系列] 1.3 AutoSar 架构

依AutoSAR及经验辛苦整理&#xff0c;原创保护&#xff0c;禁止转载。 专栏 《深入浅出AutoSAR》 1. 整体架构 ​ 图片来源&#xff1a; AutoSar 官网 从官往图中可以看出autosar作为汽车ECU软件架构&#xff0c;是通过分层来实现软硬件隔离。就像大多数操作系统一样&#xff…

Docker swarm集群之compose启动多服务

Docker swarm集群之compose启动多服务 本篇文章是在搭建过Swarm集群基础上进行的&#xff0c;如未搭建过请移步 &#xff1a; [Docker swarm 集群搭建 - Wanwan’s Blog (wanwancloud.cn)] 环境信息 主机名IP主机配置master10.10.10.32c2gnode0110.10.10.42c2gnode0210.10.…

项目中拖拽元素,可以使用html的draggable属性,当然也可以用第三方插件interact

项目中拖拽元素&#xff0c;可以使用html的draggable属性&#xff0c;当然也可以用第三方插件interact 一、安装二、引用三、使用 一、安装 npm install interactjs二、引用 import interact from interactjs三、使用 <div class"drag_box"> &…