请选择 进入手机版 | 继续访问电脑版

Linux内核设计与实现——内核数据结构

[复制链接]
太阳神鹰 发表于 2021-1-1 10:32:49 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
主要内容



  • 链表
  • 队列
  • 映射
  • 二叉树
1. 链表



  • 单向链表、双向链表
  • 环形链表
linux内核中的链表使用方法和一般数据结构中界说的链表是有所差别的。
传统链表:

传统双向链表.png
传统的链表有个最大的缺点就是欠好共通化,因为每个node中的data1,data2等等都是不确定的(无论是个数照旧类型)。
linux中的链表巧妙的管理了这个问题,linux的链表不是将用户数据生存在链表节点中,而是将链表节点生存在用户数据中。
linux的链表节点只有2个指针(pre和next),这样的话,链表的节点将独立于用户数据之外,便于实现链表的共同操纵。
Linux内核链表:

linux内核双向链表.png
最大的问题在于,怎样通过链表的节点来取得用户数据?
答案是通过container_of()宏
  1. #define container_of(ptr, type, member) ({          \    const typeof(((type *)0)->member)*__mptr = (ptr);    \             (type *)((char *)__mptr - offsetof(type, member)); })
复制代码


  • type一般是个结构体,也就是包含用户数据和链表节点的结构体。
  • ptr是指向type中链表节点的指针
  • member则是type中界说链表节点是用的名字
比如:
  1. struct student{    int id;    char* name;    struct list_head list;};
复制代码


  • type是struct student
  • ptr是指向stuct list的指针,也就是指向member类型的指针
  • member就是 list
下面分析一下container_of宏:
  1. // 步调1:将数字0强制转型为type*,然后取得此中的member元素((type *)0)->member  // 相当于((struct student *)0)->list// 步调2:界说一个暂时变量__mptr,并将其也指向ptr所指向的链表节点const typeof(((type *)0)->member)*__mptr = (ptr);// 步调3:盘算member字段隔断type中第一个字段的隔断,也就是type地点和member地点之间的差// offset(type, member)也是一个宏,界说如下:#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)// 步调4:将__mptr的地点 - type地点和member地点之间的差// 其实也就是获取type的地点
复制代码
步调1,2,4比力容易明确,下面的图以sturct student为例进行说明步调3:

  • 首先需要知道 ((TYPE *)0) 体现将地点0转换为 TYPE 类型的地点
  • 由于TYPE的地点是0,所以((TYPE *)0)->MEMBER 也就是 MEMBER的地点和TYPE地点的差,如下图所示:

明确步调3.png
2. 队列

FIFO,没啥好说的


  • 队列的size在初始化时,始终设定为2的n次方
  • 使用队列之前将队列结构体中的锁(spinlock)释放
3. 映射

雷同于python里的字典
散列表是一种映射,但自平衡二叉树搜索树也能实现存储数据,比如C++中map就是红黑树嘛,在最坏情况下能有更好的体现
Linux内核中的映射叫idr,目标是映射一个位于id标识数UID到一个指针
4. 红黑树

5. 算法复杂度

大o符号代表上限(更差情况)
大θ符号代表最小上限
文末给各人分享几个Linux内核的视频解说:

1、linux内核,进程调理器的实现,完全公平调理器 CFS:https://www.bilibili.com/video/BV1hf4y1B7Yg/
2、 Linux内核丨红黑树 | 设计模式与算法:https://www.bilibili.com/video/BV1ig4y1v7So/
3、Linux内核学习视频来啦,这么学,才简朴:https://www.bilibili.com/video/BV1m54y127Mb/
附上一份Linux内核学习大纲:

 
 
 
 
 

来源:https://blog.csdn.net/Linuxhus/article/details/111936014
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )