概要 本文对双向链表进行探讨，介绍的内容是Linux内核中双向链表的经典实现和用法。其中，也会涉及到Linux内核中非常常用的两个经典宏定义offsetof和container_of。...内容包括： 1.Linux中的两个经典宏定义 2.Linux中双向链表的经典实现 Linux中的两个经典宏定义 倘若你查看过Linux Kernel的源码，那么你对 offsetof 和 container_of...这两个宏最初是极客写出的，后来在Linux内核中被推广使用。...在linux内核的include/linux/kernel.h中定义。...Linux中双向链表的经典实现 1.Linux中双向链表介绍 Linux双向链表的定义主要涉及到两个文件： include/linux/types.h include/linux/list.h Linux
/******************** * 内核中链表的应用 ********************/ (1)介绍 在Linux内核中使用了大量的链表结构来组织数据，包括设备列表以及各种功能模块中的数据组织...这些链表大多采用在include/linux/list.h实现的一个相当精彩的链表数据结构。...和next，内核的数据结构通常组织成双循环链表。...和以前介绍的双链表结构模型不同，这里的list_head没有数据域。在Linux内核链表中，不是在链表结构中包含数据，而是在数据结构中包含链表节点。...内核提供了一组函数来操作链表。
linux kernel中的list估计已经被各位前辈们写烂了,但是我还是想在这里记录一下; linux kernel里的很多数据结构都很经典, list链表就是其中之一 本篇要介绍的内容: list...的定义 list提供的操作方法 注意事项 使用实例 ---- List 所在文件: List的所有操作可以在 include/linux/list.h找到; List head的定义可以在 include.../linux/types.h找到; 定义 实际上这就是一个双向循环链表, 且有一个头指针 list head的定义: struct list_head { struct list_head *next...思想很巧妙, 对用户定义的数据结构侵入性很小, 实现了c++中std::List模板的功能; 虽然这个定义是叫head, 但其实嵌入到用户定义的数据结构中的也是这个....list->next, list); list->prev = list; } 插入操作 将一个元素插入到两个元素之间, 即将 new插入到prev和next中, 这个函数是下面在头部和尾部插入的实现基础
printf("num = %d, math = %d\n", temp->num, temp->math); } printf("\n"); return 0; } 运行效果： 内核双链表效果图...： 大体的效果图就是如此，增加一个节点，删除一个节点都是基于这个模型展开的。...读者可以手动画画增加和删除的操作。 其实关于内核中链表的操作还有很多的函数，目前就分析这几个。其余留给自己尝试。
描述 在linux内核中封装了一个通用的双向链表库，这个通用的链表库有很好的扩展性和封装性，它给我们提供了一个固定的指针域结构体，我们在使用的时候，只需要在我们定义的数据域结构体中包含这个指针域结构体就可以了...，具体的实现、链接并不需要我们关心，只要调用提供给我们的相关接口就可以完成了。...传统的链表结构 struct node{ int key; int val; node* prev; node* next; } linux 内核通用链表库结构 提供给我们的指针域结构体...list就是student结构定义里的属性list //list_entry的原理有点复杂，也是linux内核的一个经典实现，这个在上面那篇链接文章里也有讲解 tmp_student...内核提供的这个通用链表库里面还有很多其他的接口，这里没有详细的一一举例，有兴趣的可以自己去看看，在源码包 include/linux/list.h 文件里面，不过通过阅读一些源代码确实对我们也有很大的提高
前言： 在上期文章中，已经给大家分享过offsetof()和container_of两个宏函数，这两个宏函数在Linux内核链表里面有大量的应用，对于我们平时工作写代码有很大的帮助。...下面是Linux内核链表的内容分享。...做内核驱动开发经常会使用linux内核最经典的双向链表 list_head， 以及它的拓展接口(或者宏定义)： list_add , list_add_tail, list_del , list_entry...; }; 然后就开始围绕这个结构开始构建链表，然后插入、删除节点 ，遍历整个链表等等，其实内核已经提供好了现成的接口，接下来就让我们进入 kernel/include/linux/list.h中： 一...那接下来让我们揭开她的面纱：此宏在内核代码 kernel/include/linux/kernel.h中定义（此处kernel版本为3.10；新版本4.13之后此宏定义改变，但实现思想保持一致） /**
目前Linux内核主线不支持软实时，而是使用下面2个仓库存放和Linux内核主线的版本对应的实时内核的源代码。...(3)如果使用内核线程执行中断处理函数，那么原来禁止硬中断的临界区不需要禁止硬中断，为了兼顾非实时内核和实时内核，引入本地锁，非实时内核把本地锁映射到禁止内核抢占和禁止硬中断，实时内核把本地锁映射到基于实时互斥锁实现的自旋锁...(3)在实时内核中大多数禁止内核抢占的临界区可以变成可抢占的，为了兼顾非实时内核和实时内核，引入本地锁，非实时内核把本地锁映射到禁止内核抢占和禁止硬中断，实时内核把本地锁映射到使用实时互斥锁实现的自旋锁...为了能够合并到内核主线（Linux是通用操作系统，需要满足不同场合的需求），软实时Linux内核采用非常灵活的策略，划分了5种内核抢占模型，如下。...14.参考文档 (1)A realtime preemption overview，https://lwn.net/Articles/146861/，（说明：Linux内核没有完全按照这篇文档实现） (
，而在main.c函数的后面直接调用了printf函数，我们可以看下printf函数的参数是如何使用的。...和NR_BUFFERS*BLOCK_SIZE都为int类型； 以前已经分析过可变参数的一系列实现函数va函数。...我们先不管write函数的实现，首先来看vsprint。...str-buf;//返回值为字符串的长度 142 这样我们就实现了根据fmt中的格式转换符将可变参数转换到相应的格式，利用write函数进行输出的目的。...分析同上 而write函数跟fork函数一样是由_syscall*来实现的，内嵌汇编就不多解释了，直接展开就行 write.c _syscall3(int,write,int,fd,const char
ECMP在不同版本的Linux内核实现方式不一样，总体上可分为4个阶段。 内核版本ECMP功能< Pre kernel v2.2无ECMP。...kernel 3.5.7 图1是内核里L3（网络层）核心流程框架，展示了接收IP报文的、发送IP报文、选取IP报文转发的下一跳和转发IP报文的流程。...那3.6到4.4之间的版本就不能实现Per-packet类型的ECMP吗？也不是不可能，使用iptables对“同一类IP报文”打上mark，配合ip-route的标签功能也能实现。.... */ res->nh_sel = 0; } ``` ECMP在Linux内核的实现的关键变更历史。...时间：1997.11 版本：Pre kernel v2.2 事件：“IPV4 ECMP”实现被加入内核。
应要求分享一下内核链表结构，故写了本blog。本文对内核链表做一个简单介绍，以及引出内核中大量使用的分离思想和数据结构的定义。...传统链表的困境 内核中数据结构千变万化，采用传统的链表结构形式，需要为各种数据都定义出一个链表。...内核链表 内核链表正是采用了如上的思想进行设计的，内核链表位于内核代码的include/linux/list.h中，该链表定义为双向循环链表，所有的相关操作都定义在该头文件中，该文件中每个函数极为简洁。...*fops; struct list_head list; /* 用内核链表管理所有注册在内核中的misc设备 */ struct device *parent; struct...= (head); \ pos = list_next_entry(pos, member)) 总结 内核中大量使用了该思想，凡是在物理内存中离散分布的结构，均采用此思想将结构嵌入到具体数据中实现数据的结构组织
在 Linux 内核中使用最多的数据结构就是链表了，其中就包含了许多高级思想。 比如面向对象、类似C++模板的实现、堆和栈的实现。 1....链表简介 链表是一种常用的组织有序数据的数据结构，它通过指针将一系列数据节点连接成一条数据链，是线性表的一种重要实现方式。...如果去掉前驱指针，就是单循环链表。 ? 2. 内核链表 在Linux内核中使用了大量的链表结构来组织数据，包括设备列表以及各种功能模块中的数据组织。...这些链表大多采用在[include/linux/list.h]实现的一个相当精彩的链表数据结构。事实上，内核链表就是采用双循环链表机制。 内核链表有别于传统链表就在节点本身不包含数据域，只包含指针域。...总结 本文详细分析了 linux 内核 中的双链表结构，以图文的方式旨在帮助大家理解。
在实际的工作中，我们可能会经常使用链表结构来存储数据，特别是嵌入式开发，经常会使用linux内核最经典的双向链表 list_head。...本篇文章详细介绍了Linux内核的通用链表是如何实现的，对于经常使用的函数都给出了详细的说明和测试用例，并且移植了Linux内核的链表结构，在任意平台都可以方便的调用内核已经写好的函数。...Linux内核中的链表 上面介绍了普通链表的实现方式，可以看到数据域都是包裹在节点指针中的，通过节点指针访问下一组数据。...但是 Linux内核的链表实现可以说比较特殊，只有前驱和后继指针，而没有数据域。链表的头文件是在include/list.h（Linux2.6内核）下。...链表删除节点 内核实现 //原来内核设置的删除链表后的指向位置 // # define POISON_POINTER_DELTA 0 // #define LIST_POISON1 ((void *)
，并且实现了 unix的api linux没有直接使用unix的源代码，但完整表达了unix的设计目标并保证编程接口一致 2....每个线程拥有独立的程序计数器，进程栈和一组进程寄存器 内核调度的对象是线程，而不是进程 linux的线程实现非常特别，并不特别区分线程和进程 进程提供两种虚拟机制：虚拟处理器和虚拟内存 同一个进程内的线程可以共享虚拟内存...线程在linux中的实现 4.1 liunx线程概述 一组线程共享进程内的内存地址空间，打开的文件和其他资源 线程机制支持并发程序设计技术，多处理器上保证真正的并行处理 linux实现线程的机制非常独特...，从内核角度看，没有线程的概念 linux把所有线程都当做进程来实现，内核没有特别的调度算法或数据结构来表征线程，被视为一个使用某些共享资源的进程 每个线程有自己的task_struct，就像一个普通的进程...调度算法 3.1 概述 linux调度程序定义与kernel/sched.c 2.5版本内核重写调度算法，和以前版本区别很大，实现以下目标 充分实现O（1）调度，不管多少进程或什么输入，每个算法能在恒定时间内完成
EPOLL_CTL_DEL EPOLL_CTL_DEL 的实现调用的是 ep_remove 函数，函数只是清除ADD时， 添加的各种结构，EPOLL_CTL_MOD 的实现调用的是ep_modify...，在ep_modify中用新的事件掩码调用f_ops->poll，检测事件是否已可用，如果可用就直接唤醒epoll，这两个的实现与EPOLL_CTL_ADD 类似，代码上比较清晰，这里就不具体分析了。...wait_queue_t wait; ktime_t expires, *to = NULL; if (timeout > 0) { // 转换为内核时间...mutex_lock_nested(&ep->mtx, depth); spin_lock_irqsave(&ep->lock, flags); // 移动rdllist 到新的链表...，采用的是一种类UML图，希望对理解epoll的内部实现有所帮助。
前言：之前的文章介绍了基于 tracepoint 静态追踪技术的实现，本文再介绍基于 kprobe 的动态追踪即使的实现。同样，动态追踪也是排查问题的利器。...kprobe 是内核提供的动态追踪技术机制，它允许动态安装内核模块的方式安装系统钩子，非常强大。下面先看一个内核中的例子。...#include #include #include #define MAX_SYMBOL_LEN...总结：内核通过劫持的方式实现了 kprobe，基于 kprobe 的动态追踪技术可谓是非常复杂而强大，我们可以利用这个机制，动态修改逻辑，收集信息。...不过实现过于复杂，涉及到对 CPU 架构和内存模型的了解，本文也是大致分析了一下流程，有兴趣的同学可以自行查看源码。
而这些方向往往都涉及到底层的东西，所以就自然需要去了解内核提供的一些技术，内核提供的能力，经过多年的发展，可谓是百花齐放，而且非常复杂。本文简单分享一下内核的静态追踪技术的实现。...下面来通过一个例子看一下 Tracepoint 的使用和实现（例子来自内核文档 tracepoints.rst）。分析之前先看一下两个非常重要的宏。第一个是 DECLARE_TRACE。...2 trace event 有了 Tracepoint 机制后，我们就可以写模块加载到内核中实现自己的插桩点。但是内核也为我们内置提供了非常多的插桩点。具体是通过 trace event 来实现的。...我们可以看到插桩的这种机制是一种静态的机制，我们通常需要依赖当前版本的内核所支持的桩，从而获得对应的信息，但其实内核也提供了动态追踪的能力，可以实现热插拔获取信息的能力。...总的来说，Linux 下的追踪技术多种多样，虽然非常复杂，但是上层也提供了各种更方便的工具，这些能力是我们深入排查问题的利器。
链表是基本数据结构， 一开始学习数据结构时， 我一般这么定义， 对应实现从头或尾插入的处理函数， struct int_node_old { int val; struct int_node_old...想起前段时间， 看到FreeRTOS提供的链表处理方式（《 FreeRTOS 任务调度 List 组织 》）， 将链表结构定义和实际使用时具体节点数据内容分开定义， 供系统各个模块使用。...查看linux的源码， 发现linux中也为我们提供了相似的实现（源码）, 把一些共性统一起来。 类是 python 中for_each处理，有些意思。...linux 下的链表定义在文件 include/linux/types.h， 采用的是双向列表 struct list_head { struct list_head *next, *prev;...list 利用这个定义， 我定义了一个自己的list数据结构， 并copy了一些接口实现，感受下，linux 是如何管理链表的。
“恩恩，最简单的线性数据组织……” “装逼，知道它的优缺点吗” “恩恩，插入删除快速，遍历比较慢，而且……” “行了，知道内核链表吗” “恩恩，传统链表没有实现逻辑分离，因此操作接口……” “喂！...“你，明天过来找人事部的张小姐签……” “签你妹！每次打断我说话，滚！” “……”一脸懵逼的面试官 废话少讲，传统链表如下： ?...特点： 节点既包含了后续节点的指针，也包含了前趋节点的指针，而且一般都设计成循环，这样就可以非常方便地从链表的任意一个位置开始遍历整个链表。 内核链表如下： ?...特点： 把传统链表中的“链”抽象出来，使之成为一条只包含前后指针的纯粹的双循环链表，这样的链表由于不含有特殊的数据，因此它实质上就是链表的抽象。最后将这样的标准链表镶嵌到具体节点里面。...内核链表通过将数据与逻辑分离，实现了统一管理Linux内核中成千上万种节点的操作，这种抽象方法在内核各个子系统中都有应用，比如设备模型管理，比如网络子系统等。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
即时通信 IM
腾讯会议
