也谈谈这四年来对内核的研究

zhanglong71

回复  瀚海书香


第四个回答，太泛了，能不能详细一点，再深入一点，结合cache的结构来解答了？
chenrvmldd 发表于 2011-06-30 16:45

    也来发表下看法：

１。“块”，是硬件高速缓存中的可一次访问的最大存储区，以此存储区为单位将硬件高速缓存分成块，内存也同样以此存储区大小为单位分块。块的大小一般是几十字节到几百字节不等。
２。硬件高速缓存与内存之间可能的映射关系有多种，但不管哪种映射方式，都会存在多个不同的内存块映射到相同硬件高速缓存块中。
３。当频繁的大量访问存储的地址很整齐的数据(如物理地址的值是2的幂次方，或在某个对象的内的相同偏移)时，趋向于将相应的内存，映射到相同的硬件高速缓存空间。如果此时密集访问相同结构的不同数据时，会造成刚刚映射到硬件高速缓存中的内存数据，迅速被新的数据覆盖。当在很短的时间内再次访问时，会发生cache miss，不得不重新从内存读取。而重新从内存读取并写入此cache块，又会造成刚读入的其它同类型数据的的被覆盖，在很短时间内再次访问被此时覆盖的数据时，再次发生cache miss……如此，则硬件高速缓存将不能发挥应有的作用。系统性能将大打折扣。

        而slab着色正是为了使得存储在slab内的对象相对slab的偏移变得杂乱。这样可以大降低cache miss的概率。

xiaobo620_2011

动手验证 主要是验证些什么，具体讲下呗

chenrvmldd

早上刚到公司，在我理解的答案之前，首先回答几个兄弟的问题:
T-BAG兄弟和smalloc觉得内存管理复杂，这个我必须承认，在两年的时间里，我几乎天天在搞内存，可是里面还是有些东西还并不是特别的确定，还有smalloc兄弟说的懂内存管理的没几个人，这个“懂”就高深了呀，呵呵。其实对于内核来讲，我前面说过了，她不是洪水猛兽，你可以把她看成你未来的女朋友，我相信对于爷们来讲，想把自己心仪的女人变成自己的女朋友的那钟欲望和动力是无穷的，突然想到freud曾经说过，一切社会进步的根源就是Libido！看来这句话还真有道理啊！
再回答一下瀚海书香兄弟的问题，对于我们搞内核的人来讲：如果我作为面试官，我觉得对于硬件你必须要懂，我也必须要问，如果不懂，不可能设计出高效操作系统出来，就比如：Linux在设计进程却换这个问题的时候，曾经用了两种方法：其实也就10几行代码左右的样子，从这点可以看出内核设计之复杂，和之谨慎，对于进程切换，我会作为一个单独的问题在以后的问题中列出来！
回答xiaobo620_2011，关于动手，怎么去动手，这个问题其实只要你动手编过简单的代码，就应该知道如何去动手了，通过做实验去验证你自己一些简单的想法，比如：在我的第一个问题中还有，没有列出来的问题，slab既然作为碎片处理的一个算法，那么它提供的最大的块应该是多大，你可以简单的去验证一下啊！其实太多太多了。。。。
好了，我想我尽量找出10个基础而深刻的问题，可是我昨晚想了很久，发现确实太难了，如果10个基础而深刻的问题能概括Linux内核，那么她也不能成为Linux了，我想，估计Linus本人看到那位兄弟提的10个关于linux内核的问题，一定会“内牛满面”，这可是人家花了多少年，多少心血搞的东东，你10个问题来概括，呵呵！

wangzhen11aaa

cache和内存的映射分为全相联，，直接相联，组相联。slab就是根据划分的一一对应而着色，增加访问命中，要是说slab的缺点，我认为这是一个数学问题。怎么优化到最好，还要看具体的硬件设备的容量。

chenrvmldd

好了，下面我来公布一下我的理解：
第一个小问：slab是为了解决内部碎片提出的，还是外部碎片？
这个显然是内部碎片，ULK这本书上明确的提到了，可是解决内部碎片的方法有很多种，为什么会用slab这种算法了？这个在第二个小问会提到，其实我看到的任何书上都没有提到slab算法背后的理论支撑，据我的了解：windows，solaris都使用了slab算法，如果我没有记错的话，最早使用的应该是solaris首先使用的！
第二个小问：Slab算法的核心思想是什么？请简述
瀚海书香兄弟的回答是“ slab的核心思想是以对象的观点来管理内存”，我觉得这个回答非常的好，可是我不知道瀚海书香兄弟能不能理解“对象”这个观点了？那么为什么“对象”这个方法会高效了？这个我还希望大家继续去思考，那好，我来归纳一下这个问题：其实是在网上摘抄的别人的一个概括，我觉得概括的很全面，所以直接拿过来用了！
Linux 内核在运行过程中，常常会需要经常使用一些内核的数据结构（对象）。例如，当进程的某个线程第一次打开一个文件的时候，内核需要为该文件分配一个称为 file 的数据结构；当该文件被最终关闭的时候，内核必须释放此文件所关联的 file 数据结构。这些小块存储空间并不只在某个内核函数的内部使用，否则就可以使用当前线程的内核栈空间。同时，这些小块存储空间又是动态变化的，不可能像物理内存页面管理使用的 page 结构那样，有多大内存就有多少个 page 结构，形成一个静态长度的队列。而且由于内核无法预测运行中各种不同的内核对象对缓冲区的需求，因此不适合为每一种可能用到的对象建立一个“缓冲池”，因为那样的话很可能出现有些缓冲池已经耗尽而有些缓冲池中却又大量空闲缓冲区的现象。因此，内核只能采取更全局性的方法。
我们可以看出，内核对象的管理与用户进程中的堆管理比较相似，核心问题均是：如何高效地管理内存空间，使得可以快速地进行对象的分配和回收并减少内存碎片。但是内核不能简单地采用用户进程的基于堆的内存分配算法，这是因为内核对其对象的使用具有以下特殊性：
1.        内核使用的对象种类繁多，应该采用一种统一的高效管理方法。
2.        内核对某些对象（如 task_struct）的使用是非常频繁的，所以用户进程堆管理常用的基于搜索的分配算法比如First-Fit（在堆中搜索到的第一个满足请求的内存块）和 Best-Fit（使用堆中满足请求的最合适的内存块）并不直接适用，而应该采用某种缓冲区的机制。
3.        内核对象中相当一部分成员需要某些特殊的初始化（例如队列头部）而并非简单地清成全 0。如果能充分重用已被释放的对象使得下次分配时无需初始化，那么可以提高内核的运行效率。
4.        分配器对内核对象缓冲区的组织和管理必须充分考虑对硬件高速缓存的影响。
5.        随着共享内存的多处理器系统的普及，多处理器同时分配某种类型对象的现象时常发生，因此分配器应该尽量避免处理器间同步的开销，应采用某种 Lock-Free 的算法。
第三个问题：在什么情况下，会用到slab，请你举几个具体的例子！
其实这个问题，前面已经有兄弟回答了，我想问大家的是：既然你知道在什么情况下用slab，那么你用过slab提供的接口吗？你对这些接口的用法熟悉吗？
关于slab提供的接口，大家可以参考ULK这本书上提供的，其实我想说的，在我们驱动程序设计和内核模块设计的过程中，经常会用的kmalloc，可是对于kmalloc这个接口，大家
有没有测试过，如果你分配一些数据，slab是如何来管理你请求的内存了？
第四个小问：Slab中算法中提到了着色，请问着色问题，主要是解决什么的？
前面也有几个兄弟回答了这个问题，但是我感觉和书上阐述的差不多，或者换一个角度去阐述，个人感觉不是很深刻！
SLAB的着色问题，一般书上讲的都比较简单，就是说解决cache缓存行冲突的问题，那么为什么冲突了？着色有是如何解决冲突问题的了？，这就要看一下我们cache与主存块的工作结构！
、1．        全相联
任一主存块能映射到Cache中任意行(主存块的容量等于Cache行的容量）

优点：灵活，不易产生冲突；
缺点：比较电路难于实现，且效率低，速度慢。
2．        直接映射
某一主存块只能能映射到Cache的特定行


优点：硬件简单，成本低；
缺点：容易产生冲突，易"颠簸"，不能有效利用Cache空间
3.组相联

组间直接映射，组内全相联映射。
• 优点：结合上面两种的优点。
① 因为组内行数较少，比较器容易实现；
② 组内又有灵活性，冲突大大减少
看完这三种结构，下面就要阐述为什么会冲突，细心的朋友肯定会发现：在直接映射和组相联映射的工作结构下会产生冲突，我们的SLAB就是为了解决这样的冲突而提出来的，所以说SLAB着色问题对于全相联的工作结构的效率没有什么帮助，这一点大家要明白，那么冲突的原因是什么了？虽然从直接映射的那张图可以看出来，这里还是要举一个具体的例子来阐述一下，让我们看一下直接映射的图：
假设有两个一样的对象A1，A2,他们大小一样假设A1在主存第0区的偏移为1，也就是说在第个区的第一个块，A2在第1个区中，偏移也为1，这个时候假设A1在cache中，这个时候需要访问A2，那么A2必须要被掉入到CACHE的A1此时所在的位置，A1被调入到主存中，如果A2访问结束之后又要访问A1，那么A2又要被换出，极端情况下cache的工作效率就会很低。相信说到这，大家应该明白了冲突的原因了吧。
其实知道冲突的原因之后，我们要解决冲突就很简单了，我们首先想到的就是不让相同的对象在不同的区中有相同的偏移，其实着色就是的核心思想就是让相同的对象在不同区中的偏移不一样，所以在Linux的着色的实现的思想就是：给在不同区中的相同对象进行着色，着色的本质其实就是加填充一个偏移（一个缓存行），那么这就势必带来一个问题，浪费了一定的存储空间！试想一下如果同一类对象很多很多的情况下，那是不是有巨大的内存浪费了，这个问题在下一个问题中会阐述出来！

第五个小问：你觉得slab算法有什么缺点，如果让你来设计，你怎么去改进它的缺点？
如果看过slub算法的人会知道，slub就是对slab的改进，关于slub：
SLAB 分配器多年以来一直位于 Linux 内核的内存管理部分的核心地带，内核黑客们一般不愿意主动去更改它的代码，因为它实在是非常复杂，而且在大多数情况下，它的工作完成的相当不错。但是，随着大规模多处理器系统和 NUMA系统的广泛应用，SLAB 分配器逐渐暴露出自身的严重不足：
1.        较多复杂的队列管理。在 SLAB 分配器中存在众多的队列，例如针对处理器的本地对象缓存队列，slab 中空闲对象队列，每个 slab 处于一个特定状态的队列中，甚至缓冲区控制结构也处于一个队列之中。有效地管理这些不同的队列是一件费力且复杂的工作。
2.        slab 管理数据和队列的存储开销比较大。每个 slab 需要一个 struct slab 数据结构和一个管理所有空闲对象的 kmem_bufctl_t（4 字节的无符号整数）的数组。当对象体积较少时，kmem_bufctl_t 数组将造成较大的开销（比如对象大小为32字节时，将浪费 1/8 的空间）。为了使得对象在硬件高速缓存中对齐和使用着色策略，还必须浪费额外的内存。同时，缓冲区针对节点和处理器的队列也会浪费不少内存。测试表明在一个 1000 节点/处理器的大规模 NUMA 系统中，数 GB 内存被用来维护队列和对象的引用。
3.        缓冲区内存回收比较复杂。
4.        对 NUMA 的支持非常复杂。SLAB 对 NUMA 的支持基于物理页框分配器，无法细粒度地使用对象，因此不能保证处理器级缓存的对象来自同一节点。
5.        冗余的 Partial 队列。SLAB 分配器针对每个节点都有一个 Partial 队列，随着时间流逝，将有大量的 Partial slab 产生，不利于内存的合理使用。
6.        性能调优比较困难。针对每个 slab 可以调整的参数比较复杂，而且分配处理器本地缓存时，不得不使用自旋锁。
7.        调试功能比较难于使用。
为了解决以上 SLAB 分配器的不足之处，内核开发人员 Christoph Lameter 在 Linux 内核 2.6.22 版本中引入一种新的解决方案：SLUB 分配器。SLUB 分配器特点是简化设计理念，同时保留 SLAB 分配器的基本思想：每个缓冲区由多个小的 slab 组成，每个 slab 包含固定数目的对象。SLUB 分配器简化了kmem_cache，slab 等相关的管理数据结构，摒弃了SLAB 分配器中众多的队列概念，并针对多处理器、NUMA 系统进行优化，从而提高了性能和可扩展性并降低了内存的浪费。为了保证内核其它模块能够无缝迁移到 SLUB 分配器，SLUB 还保留了原有 SLAB 分配器所有的接口 API 函数。
上面的回答算的上是官方的回答了，在这里，其实slub本身，还是有继承了很多slab的问题，遗憾的是，我没有看到有兄弟提出这样的问题，其实slub本身还是有缺点的！
总结：slab算法很复杂，很强大！
参考：
深入理解Linux内核
Linux内核源码分析
计算机组成原理
有一篇关于slab算法的提出的论文，大家可以去google一下，这篇文章是当年大概1970-1980之间TOP1的文章
http://www.ibm.com/developerworks/cn/linux/l-cn-slub/

phoxia

佩服

VIP_fuck

cu大牛真多

asuka2001

感谢LZ对slab的精辟讲解，以前只有感性认识，现在总算理解了一点内幕了：）

chenrvmldd

回复 27# VIP_fuck

其实大牛谈不上，只是在内存管理比一般人下的功夫要多一点，自然理解也就比别人深刻一点

chenrvmldd

回复 28# asuka2001


其实，我希望通过我自己的理解，可以让更多的兄弟提出自己的理解，然后，去引导更多的人去思考，去思考多的问题