链表是基本数据结构， 一开始学习数据结构时， 我一般这么定义， 对应实现从头或尾插入的处理函数，
在linux内核中封装了一个通用的双向链表库，这个通用的链表库有很好的扩展性和封装性，它给我们提供了一个固定的指针域结构体，我们在使用的时候，只需要在我们定义的数据域结构体中包含这个指针域结构体就可以了，具体的实现、链接并不需要我们关心，只要调用提供给我们的相关接口就可以完成了。
在上期文章中，已经给大家分享过offsetof()和container_of两个宏函数，这两个宏函数在Linux内核链表里面有大量的应用，对于我们平时工作写代码有很大的帮助。下面是Linux内核链表的内容分享。
本文对双向链表进行探讨，介绍的内容是Linux内核中双向链表的经典实现和用法。其中，也会涉及到Linux内核中非常常用的两个经典宏定义offsetof和container_of。内容包括： 1.Linux中的两个经典宏定义 2.Linux中双向链表的经典实现
在 Linux 内核中使用最多的数据结构就是链表了，其中就包含了许多高级思想。 比如面向对象、类似C++模板的实现、堆和栈的实现。
list是新队列的head指针, 包括的元素从原head队列的第一个元素到entry, head队列仅包括余下的元素
链表的主要意义就是将分散地址的数据域通过指针排列成有序的队列。因此数据域是链表不可或缺的一部分，但是在实际使用中需要不同类型的数据域，因此也就限制了链表的通用。Linux中在声明中抛弃了数据域，也就解决掉了这一问题。
链表是一种常用的组织有序数据的数据结构，它通过指针将一系列数据节点连接成一条数据链，是线性表的一种重要实现方式。相对于数组，链表具有更好的动态性，建立链表时无需预先知道数据总量，可以随机分配空间，可以高效地在链表中的任意位置实时插入或删除数据。 通常链表数据结构至少应包含两个域：数据域和指针域，数据域用于存储数据，指针域用于建立与下一个节点的联系。按照指针域的组织以及各个节点之间的联系形式，链表又可以分为单链表、双链表、循环链表等多种类型，下面分别给出这几类常见链表类型的示意图：
在前面章节已经学习了数组的使用，数组的空间是连续空间，数组的大小恒定的，在很多动态数据存储的应用场景下，使用不方便；而这篇文章介绍的链表结构，支持动态增加节点，释放节点，比较适合存储动态数据的应用场景，而且链表的空间是存储在堆上面的，可以动态分配，释放。从效率上来讲，数组的空间是连续的，查询、读取数据数组占优势；链表的优势在于节点可以动态增加、动态删除，删除支持任意位置的节点删除。
伙伴系统是常用的内存分配算法，linux内核的底层页分配算法就是伙伴系统，伙伴系统的优点就是分配和回收速度快，减少外部碎片。算法描述:
应要求分享一下内核链表结构，故写了本blog。本文对内核链表做一个简单介绍，以及引出内核中大量使用的分离思想和数据结构的定义。
一.双向循环链表 #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
在Linux内核中，对于数据的管理，提供了2种类型的双向链表：一种是使用list_head结构体构成的环形双向链表；另一种是使用hlist_head和hlist_node2个结构体构成的具有表头的链型双向链表。
/**************************************************************** 文件内容:内核之链队操作 版本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);
最差匹配找不小于n的最大空闲分区。可以避免出现太多小碎片，但外部碎片较多，释放慢。
本文基于 Linux-2.4.16 内核版本 由于计算机的物理内存是有限的, 而进程对内存的使用是不确定的, 所以物理内存总有用完的可能性. 那么当系统的物理内存不足时, Linux内核使用什么方案来
#include <stdio.h> struct list_head { struct list_head *next; struct list_head *prev; }; struct score { int num; int math; struct list_head list; }; #define list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next) #de
在Linux内核中使用了大量的链表结构来组织数据，包括设备列表以及各种功能模块中的数据组织。这些链表大多采用在include/linux/list.h实现的一个相当精彩的链表数据结构。
1.看源代码必须搞懂Android的数据结构。在init源代码中双向链表listnode使用非常多，它仅仅有prev和next两个指针，没有不论什么数据成员。这个和linux内核的list_head如出一辙，由此可见安卓深受linux内核的影响的。本来来分析一下这个listnode数据结构。
在上一篇文章中，我们重点介绍了widget、path、route之间的关系及其widget的注册； http://www.cnblogs.com/linhaostudy/p/8509899.html 在最后一章中，我们已经简单介绍了snd_soc_dapm_new_controls函数用来创建widget。 实际上，这个函数只是创建widget的第一步，它为每一个widget分配内存，初始化； 要使widget之间具备连接能力，我们还需要第二个函数snd_soc_dapm_new_widgets：这个函数会
双向链表也是链表的一种，区别在于每个节点除了后继指针外，还有一个前驱指针，双向链表的节点长下面这样：
Linux内存管理是一个非常复杂的子系统，要完全说清的话估计要一本书的篇幅。但Linux内存管理可以划分成多个部分来阐述，这篇文章主要介绍slab算法。
我们知道OS提供很多机制保证内存的管理，而分配器则是空闲的内存以一定的数据结构组织起来，通过合适的算法进行分配；
📷 📷 #include <sys/mman.h> #include <fcntl.h> #include <unistd.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #define HEAD_INFO "学号\t姓名\t性别\t年龄\t语文\t数学\t英语\t体育\t总分\t平均分\n" #define HEAD_INFO2 "学号\t姓名\t性别\t年龄\t语文\t数学\t英语\t体育\n" // 定义学生信息数据
之前说过Google为了在user space阻止系统suspend，为Android设计出一套新的电源管理: wakelocks, early_suspend等。此机制修改了Linux原生的susupend流程，定义子自己的休眠接口。起初Android为了合入此patch和Linux内核开发者有一段时间的讨论。比如此地址：http://lwn.net/Articles/318611/
本文简介本文介绍Linux RCU的基本概念。这不是一篇单独的文章，这是《谢宝友：深入理解Linux RCU》系列的第3篇，前序文章：谢宝友： 深入理解Linux RCU之一——从硬件说起= 谢宝友：
Linux内核实现了一批优雅而功能强大的双向循环列表操作宏，它们位于/usr/include/linux/list.h（请注意直接#include会报编译错误），这些宏可以直接扣出来，在需要时使用。
注：SLAB,SLOB,SLUB都是内核提供的分配器，其前端接口都是一致的，其中SLAB是通用的分配器，SLOB针对微小的嵌入式系统，其算法较为简单（最先适配算法），SLUB是面向配备大量物理内存的大规模并行系统，通过也描述符中未使用的字段来管理页组，降低SLUB本身数据结构的内存开销。
此处承接前面未深入分析的页面释放部分，主要详细分析伙伴管理算法中页面释放的实现。页面释放的函数入口是__free_page()，其实则是一个宏定义。
lab2 会依赖 lab1 ，我们需要把做的 lab1 的代码填到 lab2 中缺失的位置上面。练习 0 就是一个工具的利用。这里我使用的是 Linux 下的系统已预装好的 Meld Diff Viewer 工具。具体操作流程如下图所示：
当进程要获取某些资源（例如从网卡读取数据）的时候，但资源并没有准备好（例如网卡还没接收到数据），这时候内核必须切换到其他进程运行，直到资源准备好再唤醒进程。
通过排序链表来保存定时器，由于链表是排序好的，所以获取最小（最早到期）的定时器的时间复杂度为 O(1)。但插入需要遍历整个链表，所以时间复杂度为 O(n)。如下图：
epoll 的实现比poll/select 复杂一些，这是因为： 1. epoll_wait, epoll_ctl 的调用完全独立开来,内核需要锁机制对这些操作进行保护，并且需要持久的维护添加到epoll的文件 2. epoll本身也是文件，也可以被poll/select/epoll监视，这可能导致epoll之间循环唤醒的问题 3. 单个文件的状态改变可能唤醒过多监听在其上的epoll，产生唤醒风暴
这是文件与之前的链表结合使用，可以从文件中看数据读出来，形成一条链表，同时也可以把链表的数据写入文件中
Linux 内核通常会使用 定时器 来做一些延时的操作，比如常用的 sleep() 系统调用就是使用定时器来实现的。
Linux驱动分为字符设备驱动、块设备驱动和网络设备驱动，而字符设备又包括很多种，内核使用主设备号来区分各个字符设备驱动，在include/linux/major.h文件中已经预先定义好了各类字符设备的主设备号，但是即便如此，仍然存在着大量字符设备无法准确归类，对于这些设备，内核提供了一种Misc（杂项）设备来安放它们的去处。
最近一直在研究glusterfs的源代码，自己也在上面做了一些小的改动。我最开始研究的是3.2.5这个版本，因为据同行和网上资料显示这个版本目前是最稳定的版本。glusterfs实现比较复杂，具体的设计思想和架构就不详细介绍了，网上有这方面的资料（CSDN博客里面就有很好介绍的文章）。 研究开源系统的一个好处就是可以充分了解它的实现，如果是看这方面的论文只能了解一些原理性的东西，但是我们真正做项目还需要实际的实现。很多开源系统可能本身不一定就很适合你的系统，但是如果可以改造那么利用
在Linux 内核笔记之高层中断处理一文中，介绍了ARM gic中断控制器对于硬中断的处理过程。gic的中断处理程序是从ack一个硬件中断开始的， 在gic的中断处理过程中，会根据中断的映射去寻找对应的虚拟中断号, 再去进行后续的中断处理。gic_handle_irq->handle_domain_irq
Android的休眠唤醒主要基于wake_lock机制，只要系统中存在任一有效的wake_lock，系统就不能进入深度休眠，但可以进行设备的浅度休眠操作。wake_lock一般在关闭lcd、tp但系统仍然需要正常运行的情况下使用，比如听歌、传输很大的文件等。本文主要分析driver层wake_lock的实现。
ASOC的出现是为了让Codec独立于CPU，减少和CPU之间的耦合，这样同一个Codec驱动无需修改就可以适用任何一款平台。还是以下图做参考例子:
本次分享将讲述如何在Python中对多个list的对应元素求和，前提是每个list的长度一样。比如：a=[1,2,3], b=[2,3,4], c=[3,4,5], 对a,b,c的对应元素求和，输出应为[6,9,12]. 方法一： 直接求解，按照对应元素相加的原则，可先定义一个函数。
在《Netfilter & iptables 原理》一文中，我们介绍了 Netfilter 和 iptables 的原理，而本文主要通过源码分析来介绍一下 Netfilter 与 iptables 的实现过程。
提示：公众号展示代码会自动折行，建议横屏阅读 摘要 本文（有码慎入）主要介绍Linux任务调度相关的发展历史和基本原理。多年以来，内核界的黑客们一直着力于寻找既能满足高负载后台任务资源充分利用，又能满足桌面系统良好交互性的调度方法，尽管截至到目前为止仍然没有一个完美的解决方案。本文希望通过介绍调度算法的发展历程，因为任务调度本身不是一个局限于操作系统的话题，包括数据库，程序语言实现等，都会与调度相关。本文在介绍过程中，会引用Linux的代码实现作为说明，同时阐述其中的一些趣闻轶事。 调度实体 进程任务通常包
NAND FLASH 原理以及操作详见:https://blog.csdn.net/qq_16933601/article/details/100001443
文章来源http://blog.sina.com.cn/s/blog_b2aa4e080102xw25.html
wait_on_page_locked_killable 在 systrace 上的提示是 IO block, 那到底是怎么阻塞法? 阻塞在谁? 这里是其调用流程图： wait_on_page_loc
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
