在使用沒有垃圾回收的語言（例如c/c++）時，由于忘記釋放內存而導致內存耗盡的情況可能會發生，這被稱為內存泄漏。即使內核也需要管理內存，內存泄漏的情況也可能發生。為了找出引起內存泄漏的位置，linux內核開發者開發了kmemleak功能。
接下來我們將詳細介紹kmemleak功能的原理和實現細節。
kmemleak原理
首先讓我們分析一下，什么情況會導致內存泄漏。
1. 導致內存泄漏的原因
內存泄漏的根本原因是用戶未釋放不再使用的動態分配內存（通過memblock_alloc、kmalloc、vmalloc、kmem_cache_alloc等函數在內核中分配的內存）。那么，哪些內存屬于不再使用的呢？一般來說，沒有被指針引用的內存都屬于不再使用的內存。因為這些內存已經丟失了地址信息，因此內核無法再使用這些內存。
讓我們看一下下圖的示例：
如上圖所示，指針A原來指向內存塊A，但后來指向新申請的內存塊B，從而導致內存塊A的內存地址信息丟失。如果此時用戶沒有及時釋放掉內存塊A，就會導致內存泄漏。
當然少量的內存泄漏并不會造成很嚴重的效果，但如果是頻發性的內存泄漏，將會造成系統內存資源耗盡，從而導致系統崩潰。
2. 內核中的指針
既然沒有指針引用的內存屬于泄漏的內存，那么只需要找出系統是否存在沒有指針引用的內存，就可以判斷系統是否存在內存泄漏。
那么，怎么找到內核中的所有指針呢？我們知道，指針一般存放在 內核數據段、內核棧 和 動態申請的內存塊 中。如下圖所示：
但內核并沒有對指針進行記錄，也就是說內核并不知道這些區域是否存在指針。那么內核只能夠把這些區域當成是由指針組成的，也就是說把這些區域中的每個元素都當成是一個指針。如下圖所示：
當然，把所有元素都當成是指針是一個假設，所以會存在誤判的情況。不過這也沒關系，因為 kmemleak 這個功能只是為了找到內核中疑似內存泄漏的地方。
3. 記錄動態內存塊
前面說過，kmemleak 機制用于分析由 memblock_alloc、kmalloc、vmalloc、kmem_cache_alloc 等函數申請的內存是否存在泄漏。
分析的依據是：掃描內核中所有的指針，然后判斷這些指針是否指向了由 memblock_alloc、kmalloc、vmalloc、kmem_cache_alloc 等函數申請的內存塊。如果存在沒有指針引用的內存塊，那么就表示可能存在內存泄漏。
所以，當使用 memblock_alloc、kmalloc、vmalloc、kmem_cache_alloc 等函數申請內存時，內核會把申請到的內存塊信息記錄下來，用于后續掃描時使用。內核使用 kmemleak_object 對象來記錄這些內存塊的信息，然后通過一棵紅黑樹把這些 kmemleak_object 對象組織起來（使用內存塊的地址作為鍵），如下圖所示：
所以內存泄漏檢測的原理是：
- 遍歷內核中所有的指針，然后從紅黑樹中查找是否存在對應的內存塊，如果存在就把內存塊打上標記。
- 所有指針掃描完畢后，再遍歷紅黑樹中所有 kmemleak_object 對象。如果發現沒有打上標記的內存塊，說明存在內存泄漏（也就是說，存在沒有被指針引用的內存塊），并且將對應的內存塊信息記錄下來。
kmemleak 實現
了解了 kmemleak 機制的原理后，現在我們來分析其代碼實現。
1. kmemleak_object 對象
上面介紹過，內核通過 kmemleak_object 對象來記錄動態內存塊的信息，其定義如下：
struct?kmemleak_object?{ ????spinlock_t?lock; ????unsigned?long?flags;????????/*?object?status?flags?*/ ????struct?list_head?object_list; ????struct?list_head?gray_list; ????struct?rb_node?rb_node; ????... ????atomic_t?use_count; ????unsigned?long?pointer; ????size_t?size; ????int?min_count; ????int?count; ????... ????pid_t?pid;??????????????????/*?pid?of?the?current?task?*/ ????char?comm[TASK_COMM_LEN];???/*?executable?name?*/ };
kmemleak_object 對象的成員字段比較多，現在我們重點關注 rb_node 、pointer 和 size 這 3 個字段：
- rb_node：此字段用于將 kmemleak_object 對象連接到紅黑樹中。
- pointer：用于記錄內存塊的起始地址。
- size：用于記錄內存塊的大小。
內核就是通過這 3 個字段，把 kmemleak_object 對象連接到全局紅黑樹中。
例如利用 kmalloc 函數申請內存時，最終會調用 create_object 來創建 kmemleak_object 對象，并且將其添加到全局紅黑樹中。我們來看看 create_obiect 函數的實現，如下：
... //?紅黑樹的根節點 static?struct?rb_root?object_tree_root?=?RB_ROOT; ... static?struct?kmemleak_object?* create_object(unsigned?long?ptr,?size_t?size,?int?min_count,?gfp_t?gfp) { ????unsigned?long?flags; ????struct?kmemleak_object?*object,?*parent; ????struct?rb_node?**link,?*rb_parent; ????//?申請一個新的?kmemleak_object?對象 ????object?=?kmem_cache_alloc(object_cache,?gfp_kmemleak_mask(gfp)); ????... ????object->pointer?=?ptr; ????object->size?=?size; ????//?將新申請的?kmemleak_object?對象添加到全局紅黑樹中 ????... ????link?=?&object_tree_root.rb_node;?//?紅黑樹根節點 ????rb_parent?=?NULL; ???//?找到?kmemleak_object?對象插入的位置（參考平衡二叉樹的算法） ????while?(*link)?{ ????????rb_parent?=?*link; ????????parent?=?rb_entry(rb_parent,?struct?kmemleak_object,?rb_node); ????????if?(ptr?+?size?pointer) ????????????link?=?&parent->rb_node.rb_left; ????????else?if?(parent->pointer?+?parent->size?rb_node.rb_right; ????????else?{ ????????????... ????????????goto?out; ????????} ????} ???//?將?kmemleak_object?對象插入到紅黑樹中 ????rb_link_node(&object->rb_node,?rb_parent,?link); ????rb_insert_color(&object->rb_node,?&object_tree_root); out: ????... ????return?object; }
雖然 create_obiect 函數的代碼比較長，但是邏輯卻很簡單，主要完成 2 件事情：
- 申請一個新的 kmemleak_object 對象，并且初始化其各個字段。
- 將新申請的 kmemleak_object 對象添加到全局紅黑樹中。
?
將 kmemleak_object 對象插入到全局紅黑樹的算法與數據結構中的平衡二叉樹算法是一致的，所以不了解的同學可以查閱相關的資料。
2. 內存泄漏檢測
當開啟內存泄漏檢測時，內核將會創建一個名為 kmemleak 的內核線程來進行檢測。
在分析內存檢測的實現之前，我們先來了解一下關于 kmemleak_object 對象的三個概念：
- 白色節點：表示此對象沒有被指針引用（count 字段少于 min_count 字段）。
- 灰色節點：表示此對象被一個或多個指針引用（count 字段大于或等于 min_count 字段）。
- 黑色節點：表示此對象不需要被掃描（min_count 字段等于 -1）。
接著我們來看看 kmemleak 內核線程的實現：
static?int?kmemleak_scan_thread(void?*arg) { ????... ????while?(!kthread_should_stop())?{ ????????... ????????kmemleak_scan();?//?進行內存泄漏掃描 ????????... ????} ????return?0; }
可以看出 kmemleak 內核線程主要通過調用 kmemleak_scan 函數來進行內存泄漏掃描。我們繼續來看看 kmemleak_scan 函數的實現：
static?void?kmemleak_scan(void) { ????... ????//?1)?將所有?kmemleak_object?對象的?count?字段置0，表示開始時全部是白色節點 ????list_for_each_entry_rcu(object,?&object_list,?object_list)?{ ????????... ????????object->count?=?0; ????????... ????} ????... ????//?2)?掃描數據段與未初始化數據段 ????scan_block(_sdata,?_edata,?NULL,?1); ????scan_block(__bss_start,?__bss_stop,?NULL,?1); ????... ????//?3)?掃描所有內存頁結構，這是由于內存頁結構也可能引用其他內存塊 ????for_each_online_node(i)?{ ????????... ????????for?(pfn?=?start_pfn;?pfn?if?(kmemleak_stack_scan)?{ ????????... ????????do_each_thread(g,?p)?{ ????????????scan_block(task_stack_page(p),?task_stack_page(p)?+?THREAD_SIZE,?NULL,?0); ????????}?while_each_thread(g,?p); ????????... ????} ????//?5)?掃描所有灰色節點 ????scan_gray_list(); ????... }
由于 kmemleak_scan 函數的代碼比較長，所以我們對其進行精簡。精簡后可以看出，kmemleak_scan 函數主要完成 5 件事情：
- 將系統中所有 kmemleak_object 對象的 count 字段置 0，表示掃描開始時，所有節點都是白色節點。
- 調用 scan_block 函數掃描 數據段 與 未初始化數據段，因為這兩個區域可能存在指針。
- 掃描所有 內存頁結構，這是因為內存頁結構可能會引用其他內存塊，所以也要對其進行掃描。
- 掃描所有 進程內核棧，由于進程內核棧可能存在指針，所以要對其進行掃描。
- 掃描所有 灰色節點，由于灰色節點也可能存在指針，所以要對其進行掃描。
掃描主要通過 scan_block 函數進行，我們來看看 scan_block 函數的實現：
static?void scan_block(void?*_start,?void?*_end,?struct?kmemleak_object?*scanned, ???????????int?allow_resched) { ????unsigned?long?*ptr; ????unsigned?long?*start?=?PTR_ALIGN(_start,?BYTES_PER_POINTER); ????unsigned?long?*end?=?_end?-?(BYTES_PER_POINTER?-?1); ????//?對內存區進行掃描 ????for?(ptr?=?start;?ptr?if?(!object) ????????????continue; ????????... ????????//?如果對象不是白色，說明此內存塊已經被指針引用 ????????if?(!color_white(object))?{ ????????????... ????????????continue; ????????} ????????//?對?kmemleak_object?對象的count字段進行加一操作 ????????object->count++; ????????//?判斷當前對象是否灰色節點，如果是將其添加到灰色節點鏈表中 ????????if?(color_gray(object))?{ ????????????list_add_tail(&object->gray_list,?&gray_list); ????????????... ????????????continue; ????????} ????????... ????} }
scan_block 函數主要完成以下幾個步驟：
- 遍歷內存區所有指針。
- 查找指針所引用的內存塊是否存在于紅黑樹中，如果不存在就跳過處理此對象。
- 如果 kmemleak_object 對象不是白色，說明已經有指針引用此內存塊，跳過處理此對象。
- 對 kmemleak_object 對象的 count 字段進行加一操作，表示有指針引用此內存塊。
- 判斷當前 kmemleak_object 對象是否是灰色節點（count 字段大于或等于 min_count 字段），如果是將其添加到灰色節點鏈表中。
掃描完畢后，所有白色的節點就是可能存在內存泄漏的內存塊。
