Galex

Category: Kernel

zsmalloc分配器源码分析

背景

在内核中,slab分配器用于分配较小块内存,它将多个相同大小的对象放在同一个内存页中,但这些对象可能不能正好占满整个内存页,从而产生碎片造成浪费,于是内核尝试为对象分配多个物理连续内存页从而使碎片尽可能小,但在低内存设备上要分配多个连续内存页可能十分困难,特别在系统运行较长时间后,这变得几乎[......]

Read more

Linux内核中使用红黑树的扩展特性实现区间树(Interval tree)

阅读3.0版本以后的内核源代码就会发现,新版本内核中的红黑树的实现与之前有所不同。新的实现提供了增强特性,用户可以在红黑树结点中符加一些数据结构来提供更多的功能。区间树就是一种增强型的红黑树。《算法导论》中有关于区间树详细的介绍。下图是取自《算法导论》的一棵区间树:

区间树

Linux内核中[......]

Read more

Linux内核中红黑树的实现

红黑树(Red–black tree)是一种自平衡的二叉搜索树。一棵红黑树具有下列性质:

  1. 结点颜色要么是红色,要么是黑色
  2. 根节点是黑色
  3. 所有叶子结点(位于树最底层的NULL结点)都是黑色
  4. 红色结点的孩子必须是黑色
  5. 每个结点到以它为根的子树的所有叶节点的路径上都包含相同数目的黑[......]

Read more

Linux内核中hash链表的实现

上一篇中介绍了双链表的实现,现在来看下hash链表是如何实现的。注意这里所说的“hash链表”和“hash表”的不同,hash链表是指映射到hash表中同一位置的所有元素组成的溢出链表。

hash链表的结构和双链表一样,也是内嵌到需要作为hash链表表元素的结构中。不同的是,双链表的表头和表[......]

Read more

Linux内核中双链表的实现

双链表是最常用的数据结构之一,在Linux内核中也不例外。下图表示了双链表在内核中的实现:

Linux中的双链表

可以看出,链表的组织是循环的,即第一个元素的前一项是链表中的最后一项,最后一项的下一项是链表的第一项。

我们在用到双链表时,通常会这样定义结构体:
[crayon-5a3518856763c52[......]

Read more

Copyright © 2017 Galex

署名-非商业性使用-禁止演绎 3.0 | Creative Commons BY-NC-ND 3.0