置疑: 我觉得在linux的slub分配器中，一个内存缓存的BUG

lin_style

对于SLUB不熟的同学可以先跳过了，涉及的东西比较细致。
简单来说SLUB的结构是N(CPU数)个kmem_cache_cpu，和一个kmem_cache_node组成。其中kmem_cache_cpu的目的是为了从技术层面上提高CPU命中缓存，以及在同一个页面上不出现一个脏的内存（即不同时被多个CPU持有）。我把这个实现机制手工在WINDOWS下实现了一套，在开启多个kmem_cache_cpu的时候出现了个问题：
1.在释放对象的时候，判断是否是当前kmem_cache_cpu页面所在
2.如果是，则直接插入
3.如果不是，释放到邻居节点

如果是单个kmem_cache_cpu肯定没问题，但是在多个kmem_cache_cpu下，很可能会把其中一个kmem_cache_cpu已经持有的页面释放到邻居节点。举个例子：

假设一个页面地址是0-9,
kmem_cache_cpu1，持有A页面，空闲的情况为A0-A5
kmem_cache_cpu2，持有B页面，
当轮到kmem_cache_cpu2执行的时候，一个A页面的地址A6释放，程序检测到非B页面，则直接释放到邻居节点。那么这个时候A页面已经被切割成两段，并且在公共的邻居节点中,其他的kmem_cache_cpu很容易就取到。这个时候反而是增加了内存的脏度

kouu

LZ的意思是这个A页面可能被cache到多个kmem_cache_cpu上面去，然后每个kmem_cache_cpu会cache这个page中的部分object，是吧？
仔细看了一下代码，貌似的确是这样子的……没有发现避免一个page被多个CPU cache的代码。

虽然多个CPU都cache了一个page（slub层面），但是它们cache的只是page中的一部分，并且每个CPU cache的部分互不相交。
不过由于CPU缓存跟object不是完全对齐的，CPU与CPU的缓存的确可能存在一定的交叉。从而导致一个CPU上的object写操作引起另一个CPU的缓存失效（这就是LZ所谓的“脏”吧？），尽管两个CPU使用的object不会交叉。

从这一点来看，确实应该避免一个page被两个CPU cache（slub层面）才对……


另外补充一点，我觉得kmem_cache_cpu这个东西除了提高CPU的缓存命中以外，还有一个很大的作用是在object分配与回收时，减少CPU之间的竞争。

lin_style

LZ的意思是这个A页面可能被cache到多个kmem_cache_cpu上面去，然后每个kmem_cache_cpu会cache这个page中的部 ...
kouu 发表于 2011-01-14 19:09

看来还是cu水平比csdn水平高。

加锁应该是每个kmem_cache_cpu有了自己的page后，并且访问这个函数的cpu_id一定只是唯一的。这可以保证吗？
比如2个CPU2个线程，执行分配的时候，进入一个函数体，会不会0号线程执行到get_kmem返回cpu_id为0,然后切换到1好2线程也get_kmem，这时候cpu_id还有可能是0？

kouu

加锁应该是每个kmem_cache_cpu有了自己的page后，并且访问这个函数的cpu_id一定只是唯一的。这可以保证吗？
比如2个CPU2个线程，执行分配的时候，进入一个函数体，会不会0号线程执行到get_kmem返回cpu_id为0,然后切换到1好2线程也get_kmem，这时候cpu_id还有可能是0？

可以看到，在slab_alloc函数里面，如果属于当前CPU的kmem_cache_cpu的freelist不为空，那么在这个list里面取object的时候是没有上锁的。

那么，如何避免两个线程因为内核抢占而交叉执行的情况呢（就是你所说的这种情况）？
在slab_alloc里面会有local_irq_save操作，禁止了本地中断。这样也就避免了当前CPU上的内核抢占。

lin_style

可以看到，在slab_alloc函数里面，如果属于当前CPU的kmem_cache_cpu的freelist不为空，那么在这个list里 ...
kouu 发表于 2011-01-15 23:00

    也就是说，这类东西必须系统底层去实现才能够发挥最大的效率。或者，因为现在硬件发展的规格不同，操作系统也势必可以放出一些接口。

lin_style

回来看看

embeddedlwp

回复 4# kouu


    在您baidu的博客中看到您写的《linux slub分配器浅析》，有这么一句：“page结构不仅代表了内存，结构里面还有一些union变量用来记录其对应内存的对象分配情况（仅当page被加入到SLUB分配器后有效，其他情况下这些变量有另外的解释）。”这里的“仅当page被加入到SLUB分配器后有效，其他情况下这些变量有另外的解释”是怎么看出来的阿？

kouu

又回想起这个问题...... 属于同一个page下的object, 可能被cache到不同CPU的kmem_cache_cpu.
现在想来, 这样貌似也是合理的.

首先, 初始状态下, page加入到slub之后, 属于该page的object都是空闲的, 都存在于page->freelist中;
然后, 这个page可能被某个CPU的kmem_cache_cpu所cache, 假设是CPU-0, 那么这个kmem_cache_cpu将得到属于该page的所有object. page->freelist将为空;
接下来, 这个page的一部分object可能在这个CPU-0上被分配出去;
再接着, 可能由于NUMA的node id不匹配, 这个page被deactivate, 脱离了CPU-0. 这时page->freelist将保存着那些未被分配出去的object(其他的object已经在CPU-0上被分配出去了);

这时, 属于page的一部分object正在CPU-0上被使用着, 另一部分object存在于page->freelist中.
那么, 现在就有两个选择:
1, 这个page不放回到partial list, 阻止其他CPU使用这个page;
2, 将这个page放回partial list, 允许其他CPU使用这个page;

对于第一种做法, 可以避免属于同一个page的object被cache到不同CPU. 但是这个page必须等到CPU-0再次cache它以后才能被继续使用; 或者等待CPU-0所使用的属于这个page的object都全部释放, 然后这个page才能被放回partial list或者直接被释放掉.
这样一来, 一个page尽管有空闲的object, 却可能在一定时间内处于不可用状态(极端情况是永远不可用). 这样实现的系统似乎不太可控...

而现在的slub选择了第二种做法, 将page放回partial list. 于是page马上就能被其他CPU使用起来. 那么也就不得不面临属于同一个page的object被cache到不同CPU的问题. 这也是没办法的事情...

seekhunter

回复 8# kouu

觉得楼上还忘了一点。
   

再接着, 可能由于NUMA的node id不匹配,

回复 8# kouu
    如果没有配置CONFIG_NUMA，这个条件不会被满足。

另外，当CPU2 free object的时候（object属于pageXXX）, 而pageXXX恰好被CPU1使用，那么object是直接被挂接到page->freelist.
（这前后会用localirq和spinlock保护）。
我看的是3.0的代码，在slab_free和__slab_free里。

seekhunter

回复 9# seekhunter


    当CPU2 free object的时候（object属于pageXXX）, 而pageXXX恰好不被被CPU2使用（可能被cpu1使用，也可能没有cpu使用），那么object是直接被挂接到page->freelist.
（这前后会用localirq和spinlock保护）。