題目是一個典型 《Effective C++》 的風格。
事情是這樣的，我大致說一下。
我在開發一個Netfilter模塊，在PREROUTING匹配一些數據包，顯而易見，都能想到使用哈希表hlist作為數據結構的容器，其中裝有下面的結構體：
<code>struct item { struct hlist_node hnode; char padding[16];};/<code>生成item的時候，我先用 kmalloc 接口分配內存：
<code>item_nd = (struct item *)kmalloc(sizeof(struct item), GFP_KERNEL);/<code>
然後我用hlist_add/del接口將分配好的結構體插入到hlist中。
僅僅為了測試是否會宕機，所以我的所有的數據結構的hash值均是一樣的，這樣插入200個項的話，它們會hash衝突，從而僅僅添加到同一個hlist鏈表中，這樣整個匹配過程就退化成了遍歷200個項的鏈表。
雖然是萬惡的遍歷操作，但200個項一切還OK，性能幾乎是無損的，無論是吞吐，還是pps。
這個時候，我想擴充一些功能，於是乎為item結構體增加了一個字段：
<code>struct item { struct hlist_node hnode; char padding[16]; void *private;};/<code>僅僅增加了一個private，其它均和之前完全一致，同樣的200個項插入同一條hlist，同樣遍歷，吞吐和pps下降達到15%～20%！
為什麼增加了一個指針變量，就出現瞭如此巨大的性能差異？！
事情的端倪就隱藏在kmalloc接口中！
事情的真相是，在不添加private指針時，item結構的大小是32，添加一個指針，其大小變成了40，別小看這8個字節：
- 32字節大小的所有200個item在內存中幾乎都是連續的。
- 40字節大小的所有200個item在內存中幾乎都是不連續的。
為什麼會造成這個結果？32和40有什麼特殊性嗎？
我們還要繼續向下看。
kmalloc的背後其實是一系列的kmem_cache：
- 8字節的kmem_cache
- 16字節的kmem_cache
- 32字節的kmem_cache
- 64字節的kmem_cache
- 92字節的kmem_cache
- 128字節的kmem_cache
- ...
我們從/proc/slabinfo裡可以一窺究竟：
<code>[root@localhost test]# cat /proc/slabinfo |grep ^kmallockmalloc-8192 52 52 8192 4 8 : tunables 0 0 0 : slabdata 13 13 0kmalloc-4096 274 288 4096 8 8 : tunables 0 0 0 : slabdata 36 36 0kmalloc-2048 578 608 2048 16 8 : tunables 0 0 0 : slabdata 38 38 0kmalloc-1024 1105 1120 1024 16 4 : tunables 0 0 0 : slabdata 70 70 0kmalloc-512 1466 1584 512 16 2 : tunables 0 0 0 : slabdata 99 99 0kmalloc-256 2289 2560 256 16 1 : tunables 0 0 0 : slabdata 160 160 0kmalloc-192 1630 1785 192 21 1 : tunables 0 0 0 : slabdata 85 85 0kmalloc-128 1632 1632 128 32 1 : tunables 0 0 0 : slabdata 51 51 0kmalloc-96 1344 1344 96 42 1 : tunables 0 0 0 : slabdata 32 32 0kmalloc-64 25408 25408 64 64 1 : tunables 0 0 0 : slabdata 397 397 0kmalloc-32 3072 3072 32 128 1 : tunables 0 0 0 : slabdata 24 24 0kmalloc-16 3072 3072 16 256 1 : tunables 0 0 0 : slabdata 12 12 0kmalloc-8 5120 5120 8 512 1 : tunables 0 0 0 : slabdata 10 10 0/<code>
當你調用 kmalloc(size, flags) 申請內存時，系統會根據你的size向上尋找一個最接近的kmem_cache，然後在其中為你分配所需的內存。
我們知道kmemcache是針對特定數據結構的獨享內存池子，它以 *最小化碎片* 的原則為特定的場合提供 *可高效訪問* 的內存，比如sock，skbuff這些。
然而kmalloc接口所依託的kmem_cache則是全局(同一個NUMA node)共享的內存池子，它並不針對特定場合，僅僅針對特定大小！也即是說， 最小化碎片 是針對所有調用kmalloc接口的線程的。
我們回頭看上面的slabinfo，可以注意到，64字節大小的kmem_cache，即kmalloc-64已經包含了非常多的object，因此如果你調用kmalloc申請40字節的內存，其實你是在kmalloc-64裡分配。
其實32和40沒有什麼特殊性，32字節大小的item之所以還可以保持連續，那是因為kmalloc-32幾乎沒有被重度使用，而kmalloc-64則已經被其它使用者打散。
我們可以試一下，看看分別申請32字節和40字節的效果：
<code>#include <linux>struct stub32 { unsigned char m[32];};struct stub40 { unsigned char m[40];};#define SIZE 20struct stub32 *array32[SIZE] = {NULL};struct stub40 *array40[SIZE] = {NULL};%}function alloc_test()%{ int i; for (i = 0; i < SIZE; i ++) { array32[i] = kmalloc(sizeof(struct stub32), GFP_KERNEL); printk("32bytes [%d]:%p ", i, array32[i]); if (i > 0) { unsigned long hi = (unsigned long)array32[i]; unsigned long lo = (unsigned long)array32[i - 1]; signed long delta = hi - lo; if (delta < 0) delta = lo - hi; printk("delta [%lx] \\n", delta); } else printk("delta [0] \\n"); } printk("------------------\\n"); for (i = 0; i < SIZE; i ++) { array40[i] = kmalloc(sizeof(struct stub40), GFP_KERNEL); printk("40bytes [%d]:%p ", i, array40[i]); if (i > 0) { unsigned long hi = (unsigned long)array40[i]; unsigned long lo = (unsigned long)array40[i - 1]; signed long delta = hi - lo; if (delta < 0) delta = lo - hi; printk("delta [%lx] \\n", delta); } else printk("delta [0] \\n"); } for (i = 0; i < SIZE; i ++) { kfree(array32[i]); kfree(array40[i]); }%}probe begin{ alloc_test(); exit(); // oneshot模式}/<linux>/<code>以下是結果：
<code>[ 466.933100] 32bytes [1]:ffff881f9649caa0 delta [20][ 466.938206] 32bytes [2]:ffff881f9649cac0 delta [20][ 466.943314] 32bytes [3]:ffff881f9649cae0 delta [20][ 466.948586] 32bytes [4]:ffff881f9649cb00 delta [20][ 466.953732] 32bytes [5]:ffff881f9649cb20 delta [20][ 466.958863] 32bytes [6]:ffff881f9649cb40 delta [20][ 466.963977] 32bytes [7]:ffff881f9649cb60 delta [20][ 466.969095] 32bytes [8]:ffff881f9649cb80 delta [20][ 466.974222] 32bytes [9]:ffff881f9649cba0 delta [20][ 466.979329] 32bytes [10]:ffff881f9649cbc0 delta [20][ 466.984731] 32bytes [11]:ffff881f9649cbe0 delta [20][ 466.990124] 32bytes [12]:ffff881f9649cc00 delta [20][ 466.995510] 32bytes [13]:ffff881f9649cc20 delta [20][ 467.000907] 32bytes [14]:ffff881f9649cc40 delta [20][ 467.006294] 32bytes [15]:ffff881f9649cc60 delta [20][ 467.011685] 32bytes [16]:ffff881f9649cc80 delta [20][ 467.017086] 32bytes [17]:ffff881f9649cca0 delta [20][ 467.022483] 32bytes [18]:ffff881f9649ccc0 delta [20][ 467.027881] 32bytes [19]:ffff881f9649cce0 delta [20][ 467.033286] ------------------[ 467.036610] 40bytes [0]:ffff881d0c904d40 delta [0][ 467.041828] 40bytes [1]:ffff881d0c904680 delta [6c0][ 467.047216] 40bytes [2]:ffff881d0c904140 delta [540][ 467.052607] 40bytes [3]:ffff881d0c904d00 delta [bc0][ 467.058001] 40bytes [4]:ffff881d0c9043c0 delta [940][ 467.063399] 40bytes [5]:ffff881d0c904940 delta [580][ 467.068801] 40bytes [6]:ffff881d0c9048c0 delta [80][ 467.074107] 40bytes [7]:ffff881d0c904e80 delta [5c0][ 467.079496] 40bytes [8]:ffff881d0c904200 delta [c80][ 467.084888] 40bytes [9]:ffff881d0c904980 delta [780][ 467.090282] 40bytes [10]:ffff881fcd725dc0 delta [2c0e21440][ 467.096280] 40bytes [11]:ffff881fcd7250c0 delta [d00][ 467.101763] 40bytes [12]:ffff881fcd725440 delta [380][ 467.107235] 40bytes [13]:ffff881fcd725340 delta [100][ 467.112722] 40bytes [14]:ffff881f8398ee80 delta [49d964c0][ 467.118633] 40bytes [15]:ffff881f8398ecc0 delta [1c0][ 467.124110] 40bytes [16]:ffff881f8398e100 delta [bc0][ 467.129589] 40bytes [17]:ffff881f8398ed40 delta [c40][ 467.135062] 40bytes [18]:ffff881f8398efc0 delta [280][ 467.140542] 40bytes [19]:ffff881f8398e700 delta [8c0]/<code>
我們可以看到，32字節的結構體，kmalloc分配的完全都是連續的，而40字節的結構體，完全就散亂碎片化了。
如果以上的這些地址是需要在網絡協議棧的Netfilter hook中被遍歷的，可想而知，如果地址非連續且佈局無跡可尋，cache miss將會非常高。
值得一提的是，並不是說32字節的結構體分配就一定會獲得連續的內存，而64字節的就不會， 這完全取決於你的系統當前的整體kmalloc使用情況。
kmalloc並不適合快速路徑的內存分配，它只適合穩定的，離散的管理結構體的內存分配。
大家之所以普遍喜歡用kmalloc，因為它簡單，快捷，少了kmem_cache的create和destroy的維護操作。
kmalloc有個副作用，就是它只有固定的大小，比如你分配一個24字節大小的結構體，事實上系統會給你32字節。具體的細節就參考kmalloc的kmem_cache數組吧。
在諸如網絡協議棧處理這種相對快速的路徑中，比如skbuff，sock，nfconntrack等結構體均是在自行維護的獨享kmem_cache中被管理的，這保證了內存分配的 儘可能的連續性，儘可能的最少碎片。
這是通過kmem_cache的 棧式管理 實現的：
- kmem_cache的obj可以隨意釋放。
- kmem_cache的obj按照釋放的逆序進行分配。
- kmem_cache的free相當於push操作，而alloc相當於pop操作。
我再用例子給出直觀的效果，依然採用專家模式的stap：
<code>// alloc_free.stp%{#include <linux>struct stub { unsigned char m[40];};%}function kmemcache_stack_test()%{ int i; struct kmem_cache *memcache; struct stub *array[10]; struct stub *new[10] = {NULL}; memcache = kmem_cache_create("test_", sizeof(struct stub), 0, 0, NULL); if (!memcache) return; for (i = 0; i < 10; i ++) { array[i] = kmem_cache_alloc(memcache, GFP_KERNEL); STAP_PRINTF("[%d]:%llx \\n", i, array[i]); } STAP_PRINTF("Let's play\\n"); kmem_cache_free(memcache, array[4]); STAP_PRINTF("free [4]:%llx \\n", array[4]); array[4] = NULL; new[0] = kmem_cache_alloc(memcache, GFP_KERNEL); STAP_PRINTF("new [x]:%llx \\n", new[0]); kmem_cache_free(memcache, array[1]); STAP_PRINTF("free [1]:%llx \\n", array[1]); array[1] = NULL; kmem_cache_free(memcache, array[8]); STAP_PRINTF("free [8]:%llx \\n", array[8]); array[8] = NULL; new[1] = kmem_cache_alloc(memcache, GFP_KERNEL); STAP_PRINTF("new [x]:%llx \\n", new[1]); new[2] = kmem_cache_alloc(memcache, GFP_KERNEL); STAP_PRINTF("new [x]:%llx \\n", new[2]); for (i = 0; i < 10; i++) { if (new[i]) { kmem_cache_free(memcache, new[i]); new[i] = NULL; } } STAP_PRINTF("Batch free\\n"); for (i = 0; i < 10; i++) { if (array[i]) { kmem_cache_free(memcache, array[i]); STAP_PRINTF("free [i]:%llx \\n", array[i]); array[i] = NULL; } } STAP_PRINTF("Batch alloc\\n"); for (i = 0; i < 10; i++) { new[i] = kmem_cache_alloc(memcache, GFP_KERNEL); STAP_PRINTF("new [%d]:%llx \\n", i, new[i]); } for (i = 0; i < 10; i++) { if (new[i]) { kmem_cache_free(memcache, new[i]); new[i] = NULL; } } kmem_cache_destroy(memcache);%}probe begin{ kmemcache_stack_test(); exit(); // oneshot模式}/<linux>/<code>很簡單的實驗，就是分配，釋放的操作，我們運行一下：
<code>[root@localhost test]# stap -g ./alloc_free.stp[0]:ffff88003bc4bf28[1]:ffff88003bc4bf00[2]:ffff88003bc4beb0[3]:ffff88003bc4be38[4]:ffff88003bc4be88[5]:ffff88003bc4be60[6]:ffff88003bc4bdc0[7]:ffff88003bc4be10[8]:ffff88003bc4bde8[9]:ffff88003bc4bd48Let's playfree [4]:ffff88003bc4be88new [x]:ffff88003bc4be88free [1]:ffff88003bc4bf00free [8]:ffff88003bc4bde8new [x]:ffff88003bc4bde8new [x]:ffff88003bc4bf00Batch freefree [i]:ffff88003bc4bf28free [i]:ffff88003bc4beb0free [i]:ffff88003bc4be38free [i]:ffff88003bc4be60free [i]:ffff88003bc4bdc0free [i]:ffff88003bc4be10free [i]:ffff88003bc4bd48Batch allocnew [0]:ffff88003bc4bd48new [1]:ffff88003bc4be10new [2]:ffff88003bc4bdc0new [3]:ffff88003bc4be60new [4]:ffff88003bc4be38new [5]:ffff88003bc4beb0new [6]:ffff88003bc4bf28new [7]:ffff88003bc4bf00new [8]:ffff88003bc4bde8new [9]:ffff88003bc4be88[root@localhost test]#/<code>
從地址上可以看出， kmem_cache就是按照一個棧的形式進行管理的，即便由於隨機的free操作造成了空洞，後續的alloc會盡快將其填充。 這樣的結果如下：
- 儘可能節省內存，保持內存的緊湊。
- 提高CPU dcache的命中率，最大化preload效果。
即便我們使用自行維護的kmem_cache slab，當從中分配的對象插入鏈表時，也要儘量按照其內存地址的升序插入鏈表確定的位置，這樣在遍歷鏈表時可以達到最大化預取的效果。實測過程這裡從略。
一個事實是：
- 在連續的內存上進行遍歷，其性能遠超在離散的內存上進行遍歷！
這是因為CPU在訪問內存地址P時，會把一個cacheline的數據預取到cache，在連續的內存上，隨著遍歷的進行，鏈表項的訪問和預取將形成一個流水化作業，這個流水線只要不被打斷，遍歷就好像在cache中進行一樣。
我建議，根據slab對象的內存使用hlistaddbefore[rcu]，hlistaddbebind[rcu]將對象插入hlist的特定位置，而不是簡單使用hlistaddhead。
閱讀更多 linux內核 的文章
