在linux内核中封装了一个通用的双向链表库,这个通用的链表库有很好的扩展性和封装性,它给我们提供了一个固定的指针域结构体,我们在使用的时候,只需要在我们定义的数据域结构体中包含这个指针域结构体就可以了,具体的实现、链接并不需要我们关心,只要调用提供给我们的相关接口就可以完成了。
在Linux内核中使用了大量的链表结构来组织数据,包括设备列表以及各种功能模块中的数据组织。这些链表大多采用在include/linux/list.h实现的一个相当精彩的链表数据结构。
在上期文章中,已经给大家分享过offsetof()和container_of两个宏函数,这两个宏函数在Linux内核链表里面有大量的应用,对于我们平时工作写代码有很大的帮助。下面是Linux内核链表的内容分享。
应要求分享一下内核链表结构,故写了本blog。本文对内核链表做一个简单介绍,以及引出内核中大量使用的分离思想和数据结构的定义。
/**************************************************************** 文件内容:内核之链队操作 版本V1.0 作者:HFL 时间:2013-12-22 说明:用户态中链表每个节点包含数据域和指针域,而内核态是每个数据中包含链表 因此内核态链表一般是嵌套在某个包含数据成员的结构体来实现。 内核的链表应用非常广泛:进程管理,定时器,工作队列,运行队列。总之 内核对于多个数据的组织和多个熟悉的描述都是通过链表串起来的。 *****************************************************************/ #include <linux/kernel.h> #include <linux/module.h> #include <linux/init.h> #include <linux/slab.h> #include <linux/list.h> MODULE_DESCRIPTION("My Module"); MODULE_ALIAS("My module"); MODULE_LICENSE("GPL"); MODULE_AUTHOR("HFL21014"); struct student { char name[100]; int counter; struct list_head list; }; struct student *Mystudent; struct student *Temp_student; struct list_head student_list; struct list_head *pos; int Kernel_list_init() { int j = 0; INIT_LIST_HEAD(&student_list); Mystudent = kmalloc(sizeof(struct student)*5,GFP_KERNEL); memset(Mystudent,0,sizeof(struct student)*5); for(j=0;j<5;j++) { sprintf(Mystudent[i].name,"Student%d",j+1); Mystudent[j].counter = j+1; list_add( &(Mystudent[j].list), &student_list); } list_for_each(pos,&student_list) //遍历整个内核链表,pos其实就是一个for循环标量。中间临时使用,既不输入也不输出 { Temp_student = list_entry(pos,struct student,list); printk("hello,my student %d name: %s\n",Temp_student->counter,Temp_student->name); } return 0; } void Kernel_list_exit() { int k ; /* 模块卸载是要删除链表,并释放内存 */ for(k=0;k<10;jk++) { list_del(&(Mystudent[k].list)); } kfree(Mystudent); } module_init(Kernel_list_init);
本系列是对 陈莉君 老师 Linux 内核分析与应用[1] 的学习与记录。讲的非常之好,推荐观看
在 Linux 内核中使用最多的数据结构就是链表了,其中就包含了许多高级思想。 比如面向对象、类似C++模板的实现、堆和栈的实现。
链表是一种常用的组织有序数据的数据结构,它通过指针将一系列数据节点连接成一条数据链,是线性表的一种重要实现方式。相对于数组,链表具有更好的动态性,建立链表时无需预先知道数据总量,可以随机分配空间,可以高效地在链表中的任意位置实时插入或删除数据。 通常链表数据结构至少应包含两个域:数据域和指针域,数据域用于存储数据,指针域用于建立与下一个节点的联系。按照指针域的组织以及各个节点之间的联系形式,链表又可以分为单链表、双链表、循环链表等多种类型,下面分别给出这几类常见链表类型的示意图:
一.双向循环链表 #include <stdio.h> #include <stdlib.h> // 双向循环链表数据节点 typedef struct node { int data; // 数据域 struct node *prev, *next; // 指针域(2个指针,前后指针) }node; // 添加新数据(头插法) void link_list_add(int new_data, node *head); // 添加新数据(尾插法) void link_list_add_tail(i
1.看源代码必须搞懂Android的数据结构。在init源代码中双向链表listnode使用非常多,它仅仅有prev和next两个指针,没有不论什么数据成员。这个和linux内核的list_head如出一辙,由此可见安卓深受linux内核的影响的。本来来分析一下这个listnode数据结构。
节点既包含了后续节点的指针,也包含了前趋节点的指针,而且一般都设计成循环,这样就可以非常方便地从链表的任意一个位置开始遍历整个链表。
本文对双向链表进行探讨,介绍的内容是Linux内核中双向链表的经典实现和用法。其中,也会涉及到Linux内核中非常常用的两个经典宏定义offsetof和container_of。内容包括: 1.Linux中的两个经典宏定义 2.Linux中双向链表的经典实现
晓查 发自 凹非寺 量子位 | 公众号 QbitAI 还在使用89年版C语言的Linux内核,现在终于要做出改变了。 今天,Linux开源社区宣布,未来会把内核C语言版本升级到C11,预计5.18版之后生效,也就是今年5月。 这个决定很突然,从发起问题到官方声明,不过才一个星期,要知道说服固执的Linux之父 Linus Torvalds可不是件容易的事。 事情的原因,说起来还有那么一点偶然的因素。 一个bug的连锁反应 问题的起源是来自上周的一次Linux社区讨论。 一位名叫Jakob Koschel的
大家好,我是程栩,一个专注于性能的大厂程序员,分享包括但不限于计算机体系结构、性能优化、云原生的知识。
在Linux 内核中,container_of 函数使用非常广,例如 Linux内核链表 list_head、工作队列work_struct中 在Linux 内核中有一个大名鼎鼎的宏container
本文转载自 : https://blog.csdn.net/rockhui/article/details/6304705
基于X86架构的Linux内核,在移植驱动的过程中,发现GPIO和I2C的device ID添加到pnp驱动框架后无法进入probe函数,后面找了下原因,因为pnp遵循的是ACPI规范,是由于如下Hardware ID字段是需要从BIOS中进行描述的,而目前的驱动匹配不到对应的字段,自然就不可能注册成功了。 PNP是什么东西?不是三极管的那个PNP啦,这个PNP表示的是:Plug-and-Play,译文为即插即用。 PNP的作用是自动配置底层计算机中的板卡和其他设备,然后告诉对应设备都做了什么。PnP的任务是把物理设备和软件设备驱动程序相配合,并操作设备,在每个设备和它的驱动程序之间建立通信信道。然后,PnP分配下列资源给设备和硬件:I/O地址、IRQ、DMA通道和内存段。即插即用设备配置的控制权将从系统BIOS传递到系统软件,所以驱动中一定会有代码进行描述,到时可以跟一下这部分的代码深入了解一下。由于PNP遵循ACPI的规范,那么既然是规范,那肯定要照着做了,规范怎么说,那就怎么做。 以下是关于ACPI Spec中对Hardware ID的描述,描述如下:
提到自旋锁那就必须要说链表,在上一篇《驱动开发:内核中的链表与结构体》文章中简单实用链表结构来存储进程信息列表,相信读者应该已经理解了内核链表的基本使用,本篇文章将讲解自旋锁的简单应用,自旋锁是为了解决内核链表读写时存在线程同步问题,解决多线程同步问题必须要用锁,通常使用自旋锁,自旋锁是内核中提供的一种高IRQL锁,用同步以及独占的方式访问某个资源。
免责声明:本文介绍的安全知识方法以及代码仅用于渗透测试及安全教学使用,禁止任何非法用途,后果自负 前言:作者最近在学习有关linux rootkit的原理与防范,在搜索资料中发现,在freebuf上,对rootkit进行介绍的文章并不是很多。在此我斗胆献丑,总结了下我最近的学习收获,打算发表一系列关于linux rootkit的文章在freebuf上,希望能够帮助到大家。 对于这个系列文章,我的规划如下:这一系列文章的重点集中在介绍linux rootkit中最讨论最多也是最受欢迎的一种:loadable
在Linux内核中,对于数据的管理,提供了2种类型的双向链表:一种是使用list_head结构体构成的环形双向链表;另一种是使用hlist_head和hlist_node2个结构体构成的具有表头的链型双向链表。
Linux内核实现了一批优雅而功能强大的双向循环列表操作宏,它们位于/usr/include/linux/list.h(请注意直接#include会报编译错误),这些宏可以直接扣出来,在需要时使用。
linux驱动程序一般工作在内核空间,但也可以工作在用户空间。下面我们将详细解析,什么是内核空间,什么是用户空间,以及如何判断他们。 Linux简化了分段机制,使得虚拟地址与线性地址总是一致,因此,Linux的虚拟地址空间也为0~4G。Linux内核将这4G字节的空间分为两部分。将最高的1G字节(从虚拟地址0xC0000000到0xFFFFFFFF),供内核使用,称为“内核空间”。而将较低的3G字节(从虚拟地址 0x00000000到0xBFFFFFFF),供各个进程使用,称为“用户空间)。因为每个进程可以通过系统调用进入内核,因此,Linux内核由系统内的所有进程共享。于是,从具体进程的角度来看,每个进程可以拥有4G字节的虚拟空间。 Linux使用两级保护机制:0级供内核使用,3级供用户程序使用。从图中可以看出(这里无法表示图),每个进程有各自的私有用户空间(0~3G),这个空间对系统中的其他进程是不可见的。最高的1GB字节虚拟内核空间则为所有进程以及内核所共享。 内核空间中存放的是内核代码和数据,而进程的用户空间中存放的是用户程序的代码和数据。不管是内核空间还是用户空间,它们都处于虚拟空间中。 虽然内核空间占据了每个虚拟空间中的最高1GB字节,但映射到物理内存却总是从最低地址(0x00000000)开始。对内核空间来说,其地址映射是很简单的线性映射,0xC0000000就是物理地址与线性地址之间的位移量,在Linux代码中就叫做PAGE_OFFSET。 内核空间和用户空间之间如何进行通讯? 内核空间和用户空间一般通过系统调用进行通信。 如何判断一个驱动是用户模式驱动还是内核模式驱动? 判断的标准是什么? 用户空间模式的驱动一般通过系统调用来完成对硬件的访问,如通过系统调用将驱动的io空间映射到用户空间等。因此,主要的判断依据就是系统调用。 内核空间和用户空间上不同太多了,说不完,比如用户态的链表和内核链表不一样;用户态用printf,内核态用printk;用户态每个应用程序空间是虚拟的,相对独立的,内核态中却不是独立的,所以编程要非常小心。等等。 还有用户态和内核态程序通讯的方法很多,不单单是系统调用,实际上系统调用是个不好的选择,因为需要系统调用号,这个需要统一分配。 可以通过ioctl、sysfs、proc等来完成。
之前负责过QQ音乐Android版的播放功能,对于Android音频系统有过一些了解,因此将这些内容整理成文。本文是Android音频系统的基础篇,主要介绍了匿名内存内部实现以及对外的接口。下篇文章将介绍Ashmem对外提供的接口以及MemoryBase+MemoryHeapBase实现进程间共享内存的原理。
很多人尤其是初学者在写代码的时候往往都是想一点写一点,最开始没有一个整体的规划,导致后面代码越写越乱,bug不断。
提到自旋锁那就必须要说链表,在上一篇《内核中的链表与结构体》文章中简单实用链表结构来存储进程信息列表,相信读者应该已经理解了内核链表的基本使用,本篇文章将讲解自旋锁的简单应用,自旋锁是为了解决内核链表读写时存在线程同步问题,解决多线程同步问题必须要用锁,通常使用自旋锁,自旋锁是内核中提供的一种高IRQL锁,用同步以及独占的方式访问某个资源。
上一篇我们讲到内核链表和普通链表的区别,就有小伙伴追问:内核链表是怎么通过指针域来访问数据域的呢?这篇文章我们就来解答这个问题。
未来是 AI 的时代,博主最近写代码都喜欢用 AI 写个草稿,修修改改就能用,大幅提高了工作效率。举个例子:
资料中,难免会有一些错误,有任何问题,都可以在github向我提交issue。文中的勘误,我都会更新在github中。点击阅读原文可以直达github。
网上看了很多的嵌入式学习路线,有的比较片面,有的为了博人眼球东拼西凑,几乎把整个行业用得着用不着的技术都写上去了,没有侧重点,简直是劝退指南,还有的纯粹是打广告卖板子招生。
wq = create_singlethread_workqueue("mydrv");
__init__宏:被修饰的函数会被链接器链接放入.init.text段中(本来默认情况下函数是被放入.text段中)。对内核而言是一种暗示,表示该函数仅在初始化期间使用,内核启动时统一会加载.init.text段中的这些模块安装函数,加载完后就会把这个段给释放掉以节省内存。 __exit__宏:被修饰的函数仅用于模块卸载,链接器会将其放入特殊的ELF段。如果模块被直接内嵌到内核中,或内核的配置不允许卸载模块,则被修饰的函数将被简单的丢弃。 prink函数:模块在被加载到内核后,它能调用的函数仅仅是由内核导出的那些函数。KERN_INFO是printk的打印级别,其实只是一个字符串(如<1>)。操作系统的命令行中也会有一个打印级别的设置(值为0-7),当前操作系统中执行printk的时候会去对比printk中的打印级别和操作系统命令行中设置的打印级别,小于命令行设置级别的信息会被打印出来,大于的会被拦截。 module_init宏:该宏声明的函数会在模块被装载到内核中调用。 module_exit宏:该宏声明的函数会在模块被卸载时调用。 MODULE_LICENSE宏:指定该代码所使用的许可证协议。 MODULE_AUTHOR:描述模块作者。
内核模块是Linux操作系统中一个比较独特的机制。通过这一章学习,希望能够理解Linux提出内核模块这个机制的意义;理解并掌握Linux实现内核模块机制的基本技术路线;运用Linux提供的工具和命令,掌握操作内核模块的方法。
Windows内核中是无法使用vector容器等数据结构的,当我们需要保存一个结构体数组时,就需要使用内核中提供的专用链表结构LIST_ENTRY通过一些列链表操作函数对结构体进行装入弹出等操作,如下代码是本人总结的内核中使用链表存储多个结构体的通用案例。
在Windows内核中,为了实现高效的数据结构操作,通常会使用链表和结构体相结合的方式进行数据存储和操作。内核提供了一个专门用于链表操作的数据结构LIST_ENTRY,可以用来描述一个链表中的每一个节点。
链表的主要意义就是将分散地址的数据域通过指针排列成有序的队列。因此数据域是链表不可或缺的一部分,但是在实际使用中需要不同类型的数据域,因此也就限制了链表的通用。Linux中在声明中抛弃了数据域,也就解决掉了这一问题。
要想看懂 FreeRTOS 源码并学习其原理,有一个东西绝对跑不了,那就是 FreeRTOS 的列表和列表项。列表和列表项是 FreeRTOS 的一个数据结构,FreeRTOS 大量使用到了列表和列表项, 它是 FreeRTOS 的基石。要想深入学习并理解 FreeRTOS,那么列表和列表项就必须首先掌握, 否则后面根本就没法进行。
1、在引入双链表之前,我们先来回忆之前为什么要引入单链表介绍:它是解决的数组的数组的大小比较死板不容易扩展的问题;使用堆内存来存储数据,将数据分散到各个节点之间,其各个节点在内存中可以不相连,节点之间通过指针进行单向链接。链表中的各个节点内存不相连,有利于利用碎片化的内存。但是单链表各个节点之间只由一个指针单向链接,这样实现有一些局限性。局限性主要体现在单链表只能经由指针单向移动(一旦指针移动过某个节点就无法再回来,如果要再次操作这个节点除非从头指针开始再次遍历一次),因此单链表的某些操作就比较麻烦(算法比较有局限)。这里可以看我之前写的单链表操作文章结合一下,就能非常好理解单链表的局限性了。
关于程序的三个部分前面已经说了很多次了,这里就不展开说明了,直接说一说我们要实现的功能:
注意除了用offsetof宏之外, printf(“%d\n“, &(((struct foo*)0)->c));也是一种办法
本文基于 Linux-2.4.16 内核版本 由于计算机的物理内存是有限的, 而进程对内存的使用是不确定的, 所以物理内存总有用完的可能性. 那么当系统的物理内存不足时, Linux内核使用什么方案来
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huangweiqing80/article/details/83088465
相比于select,epoll最大的好处在于它不会随着监听fd数目的增长而降低效率。因为在内核中的select实现中,它是采用轮询来处理的,轮询的fd数目越多,自然耗时越多。 并且,在linux/posix_types.h头文件有这样的声明: #define __FD_SETSIZE 1024 表示select最多同时监听1024个fd,当然,可以通过修改头文件再重编译内核来扩大这个数目,但这似乎并不治本。
链表是基本数据结构, 一开始学习数据结构时, 我一般这么定义, 对应实现从头或尾插入的处理函数,
除了原子操作,中断屏蔽,自旋锁以及自旋锁的衍生锁之外,在Linux内核中还存在着一些其他同步互斥的手段。
我是架构精进之路,点击上方“关注”,坚持每天为你分享技术干货,私信我回复“01”,送你一份程序员成长进阶大礼包。
领取专属 10元无门槛券
手把手带您无忧上云