在使用沒(méi)有垃圾回收的語(yǔ)言時(shí)（如 C/C++），可能由于忘記釋放內(nèi)存而導(dǎo)致內(nèi)存被耗盡，這叫?內(nèi)存泄漏。由于內(nèi)核也需要自己管理內(nèi)存，所以也可能出現(xiàn)內(nèi)存泄漏的情況。為了能夠找出導(dǎo)致內(nèi)存泄漏的地方，Linux 內(nèi)核開(kāi)發(fā)者開(kāi)發(fā)出 kmemleak 功能。

下面我們來(lái)詳細(xì)介紹一下 kmemleak 這個(gè)功能的原理與實(shí)現(xiàn)。

kmemleak 原理

首先來(lái)分析一下，什么情況會(huì)導(dǎo)致?內(nèi)存泄漏。

1. 造成內(nèi)存泄漏的原因

內(nèi)存泄漏的根本原因是由于用戶(hù)沒(méi)有釋放不再使用的動(dòng)態(tài)申請(qǐng)的內(nèi)存（在內(nèi)核中由?memblock_alloc、kmalloc、vmalloc、kmem_cache_alloc?等函數(shù)申請(qǐng)的內(nèi)存），那么哪些內(nèi)存是不再使用的呢？一般來(lái)說(shuō)，沒(méi)有被指針引用（指向）的內(nèi)存都是不再使用的內(nèi)存。因?yàn)檫@些內(nèi)存已經(jīng)丟失了其地址信息，從而導(dǎo)致內(nèi)核不能再使用這些內(nèi)存。

我們來(lái)看看下圖的事例：

如上圖所示，指針A原來(lái)指向內(nèi)存塊A，但后來(lái)指向新申請(qǐng)的內(nèi)存塊B，從而導(dǎo)致內(nèi)存塊A的內(nèi)存地址信息丟失。如果此時(shí)用戶(hù)沒(méi)有及時(shí)釋放掉內(nèi)存塊A，就會(huì)導(dǎo)致內(nèi)存泄漏。

當(dāng)然少量的內(nèi)存泄漏并不會(huì)造成很?chē)?yán)重的效果，但如果是頻發(fā)性的內(nèi)存泄漏，將會(huì)造成系統(tǒng)內(nèi)存資源耗盡，從而導(dǎo)致系統(tǒng)崩潰。

2. 內(nèi)核中的指針

既然沒(méi)有指針引用的內(nèi)存屬于泄漏的內(nèi)存，那么只需要找出系統(tǒng)是否存在沒(méi)有指針引用的內(nèi)存，就可以判斷系統(tǒng)是否存在內(nèi)存泄漏。

那么，怎么找到內(nèi)核中的所有指針呢？我們知道，指針一般存放在?內(nèi)核數(shù)據(jù)段、內(nèi)核棧?和?動(dòng)態(tài)申請(qǐng)的內(nèi)存塊?中。如下圖所示：

但內(nèi)核并沒(méi)有對(duì)指針進(jìn)行記錄，也就是說(shuō)內(nèi)核并不知道這些區(qū)域是否存在指針。那么內(nèi)核只能夠把這些區(qū)域當(dāng)成是由指針組成的，也就是說(shuō)把這些區(qū)域中的每個(gè)元素都當(dāng)成是一個(gè)指針。如下圖所示：

當(dāng)然，把所有元素都當(dāng)成是指針是一個(gè)假設(shè)，所以會(huì)存在誤判的情況。不過(guò)這也沒(méi)關(guān)系，因?yàn)?kmemleak?這個(gè)功能只是為了找到內(nèi)核中疑似內(nèi)存泄漏的地方。

3. 記錄動(dòng)態(tài)內(nèi)存塊

前面說(shuō)過(guò)，kmemleak 機(jī)制用于分析由?memblock_alloc、kmalloc、vmalloc、kmem_cache_alloc?等函數(shù)申請(qǐng)的內(nèi)存是否存在泄漏。

分析的依據(jù)是：掃描內(nèi)核中所有的指針，然后判斷這些指針是否指向了由?memblock_alloc、kmalloc、vmalloc、kmem_cache_alloc?等函數(shù)申請(qǐng)的內(nèi)存塊。如果存在沒(méi)有指針引用的內(nèi)存塊，那么就表示可能存在內(nèi)存泄漏。

所以，當(dāng)使用?memblock_alloc、kmalloc、vmalloc、kmem_cache_alloc?等函數(shù)申請(qǐng)內(nèi)存時(shí)，內(nèi)核會(huì)把申請(qǐng)到的內(nèi)存塊信息記錄下來(lái)，用于后續(xù)掃描時(shí)使用。內(nèi)核使用?kmemleak_object?對(duì)象來(lái)記錄這些內(nèi)存塊的信息，然后通過(guò)一棵紅黑樹(shù)把這些?kmemleak_object?對(duì)象組織起來(lái)（使用內(nèi)存塊的地址作為鍵），如下圖所示：

所以?xún)?nèi)存泄漏檢測(cè)的原理是：

遍歷內(nèi)核中所有的指針，然后從紅黑樹(shù)中查找是否存在對(duì)應(yīng)的內(nèi)存塊，如果存在就把內(nèi)存塊打上標(biāo)記。

所有指針掃描完畢后，再遍歷紅黑樹(shù)中所有?kmemleak_object?對(duì)象。如果發(fā)現(xiàn)沒(méi)有打上標(biāo)記的內(nèi)存塊，說(shuō)明存在內(nèi)存泄漏（也就是說(shuō)，存在沒(méi)有被指針引用的內(nèi)存塊），并且將對(duì)應(yīng)的內(nèi)存塊信息記錄下來(lái)。

kmemleak 實(shí)現(xiàn)

了解了 kmemleak 機(jī)制的原理后，現(xiàn)在我們來(lái)分析其代碼實(shí)現(xiàn)。

1. kmemleak_object 對(duì)象

上面介紹過(guò)，內(nèi)核通過(guò)?kmemleak_object?對(duì)象來(lái)記錄動(dòng)態(tài)內(nèi)存塊的信息，其定義如下：

?

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?對(duì)象的成員字段比較多，現(xiàn)在我們重點(diǎn)關(guān)注?rb_node?、pointer?和?size?這 3 個(gè)字段：

rb_node：此字段用于將?kmemleak_object?對(duì)象連接到紅黑樹(shù)中。

pointer：用于記錄內(nèi)存塊的起始地址。

size：用于記錄內(nèi)存塊的大小。

內(nèi)核就是通過(guò)這 3 個(gè)字段，把?kmemleak_object?對(duì)象連接到全局紅黑樹(shù)中。

例如利用?kmalloc?函數(shù)申請(qǐng)內(nèi)存時(shí)，最終會(huì)調(diào)用?create_object?來(lái)創(chuàng)建?kmemleak_object?對(duì)象，并且將其添加到全局紅黑樹(shù)中。我們來(lái)看看?create_obiect?函數(shù)的實(shí)現(xiàn)，如下：

?

...
//?紅黑樹(shù)的根節(jié)點(diǎn)
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;

????//?申請(qǐng)一個(gè)新的?kmemleak_object?對(duì)象
????object?=?kmem_cache_alloc(object_cache,?gfp_kmemleak_mask(gfp));
????...
????object->pointer?=?ptr;
????object->size?=?size;

????//?將新申請(qǐng)的?kmemleak_object?對(duì)象添加到全局紅黑樹(shù)中
????...
????link?=?&object_tree_root.rb_node;?//?紅黑樹(shù)根節(jié)點(diǎn)
????rb_parent?=?NULL;

???//?找到?kmemleak_object?對(duì)象插入的位置（參考平衡二叉樹(shù)的算法）
????while?(*link)?{
????????rb_parent?=?*link;
????????parent?=?rb_entry(rb_parent,?struct?kmemleak_object,?rb_node);
????????if?(ptr?+?size?<=?parent->pointer)
????????????link?=?&parent->rb_node.rb_left;
????????else?if?(parent->pointer?+?parent->size?<=?ptr)
????????????link?=?&parent->rb_node.rb_right;
????????else?{
????????????...
????????????goto?out;
????????}
????}

???//?將?kmemleak_object?對(duì)象插入到紅黑樹(shù)中
????rb_link_node(&object->rb_node,?rb_parent,?link);
????rb_insert_color(&object->rb_node,?&object_tree_root);

out:
????...
????return?object;
}

?

雖然?create_obiect?函數(shù)的代碼比較長(zhǎng)，但是邏輯卻很簡(jiǎn)單，主要完成 2 件事情：

申請(qǐng)一個(gè)新的?kmemleak_object?對(duì)象，并且初始化其各個(gè)字段。

將新申請(qǐng)的?kmemleak_object?對(duì)象添加到全局紅黑樹(shù)中。

將?kmemleak_object?對(duì)象插入到全局紅黑樹(shù)的算法與數(shù)據(jù)結(jié)構(gòu)中的平衡二叉樹(shù)算法是一致的，所以不了解的同學(xué)可以查閱相關(guān)的資料。

2. 內(nèi)存泄漏檢測(cè)

當(dāng)開(kāi)啟內(nèi)存泄漏檢測(cè)時(shí)，內(nèi)核將會(huì)創(chuàng)建一個(gè)名為?kmemleak?的內(nèi)核線程來(lái)進(jìn)行檢測(cè)。

在分析內(nèi)存檢測(cè)的實(shí)現(xiàn)之前，我們先來(lái)了解一下關(guān)于?kmemleak_object?對(duì)象的三個(gè)概念：

白色節(jié)點(diǎn)：表示此對(duì)象沒(méi)有被指針引用（count?字段少于?min_count?字段）。

灰色節(jié)點(diǎn)：表示此對(duì)象被一個(gè)或多個(gè)指針引用（count?字段大于或等于?min_count?字段）。

黑色節(jié)點(diǎn)：表示此對(duì)象不需要被掃描（min_count?字段等于 -1）。

接著我們來(lái)看看?kmemleak?內(nèi)核線程的實(shí)現(xiàn)：

?

static?int?kmemleak_scan_thread(void?*arg)
{
????...
????while?(!kthread_should_stop())?{
????????...
????????kmemleak_scan();?//?進(jìn)行內(nèi)存泄漏掃描
????????...
????}
????return?0;
}

?

可以看出?kmemleak?內(nèi)核線程主要通過(guò)調(diào)用?kmemleak_scan?函數(shù)來(lái)進(jìn)行內(nèi)存泄漏掃描。我們繼續(xù)來(lái)看看?kmemleak_scan?函數(shù)的實(shí)現(xiàn)：

?

static?void?kmemleak_scan(void)
{
????...
????//?1)?將所有?kmemleak_object?對(duì)象的?count?字段置0，表示開(kāi)始時(shí)全部是白色節(jié)點(diǎn)
????list_for_each_entry_rcu(object,?&object_list,?object_list)?{
????????...
????????object->count?=?0;
????????...
????}
????...

????//?2)?掃描數(shù)據(jù)段與未初始化數(shù)據(jù)段
????scan_block(_sdata,?_edata,?NULL,?1);
????scan_block(__bss_start,?__bss_stop,?NULL,?1);
????...

????//?3)?掃描所有內(nèi)存頁(yè)結(jié)構(gòu)，這是由于內(nèi)存頁(yè)結(jié)構(gòu)也可能引用其他內(nèi)存塊
????for_each_online_node(i)?{
????????...
????????for?(pfn?=?start_pfn;?pfn?

	?

	由于?kmemleak_scan?函數(shù)的代碼比較長(zhǎng)，所以我們對(duì)其進(jìn)行精簡(jiǎn)。精簡(jiǎn)后可以看出，kmemleak_scan?函數(shù)主要完成 5 件事情：

	將系統(tǒng)中所有?kmemleak_object?對(duì)象的?count?字段置 0，表示掃描開(kāi)始時(shí)，所有節(jié)點(diǎn)都是白色節(jié)點(diǎn)。

	調(diào)用?scan_block?函數(shù)掃描?數(shù)據(jù)段?與?未初始化數(shù)據(jù)段，因?yàn)檫@兩個(gè)區(qū)域可能存在指針。

	掃描所有?內(nèi)存頁(yè)結(jié)構(gòu)，這是因?yàn)閮?nèi)存頁(yè)結(jié)構(gòu)可能會(huì)引用其他內(nèi)存塊，所以也要對(duì)其進(jìn)行掃描。

	掃描所有?進(jìn)程內(nèi)核棧，由于進(jìn)程內(nèi)核?？赡艽嬖谥羔?，所以要對(duì)其進(jìn)行掃描。

	掃描所有?灰色節(jié)點(diǎn)，由于灰色節(jié)點(diǎn)也可能存在指針，所以要對(duì)其進(jìn)行掃描。

	掃描主要通過(guò)?scan_block?函數(shù)進(jìn)行，我們來(lái)看看?scan_block?函數(shù)的實(shí)現(xiàn)：

	?
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);

????//?對(duì)內(nèi)存區(qū)進(jìn)行掃描
????for?(ptr?=?start;?ptr?count++;

????????//?判斷當(dāng)前對(duì)象是否灰色節(jié)點(diǎn)，如果是將其添加到灰色節(jié)點(diǎn)鏈表中
????????if?(color_gray(object))?{
????????????list_add_tail(&object->gray_list,?&gray_list);
????????????...
????????????continue;
????????}
????????...
????}
}


	?

	scan_block?函數(shù)主要完成以下幾個(gè)步驟：

	遍歷內(nèi)存區(qū)所有指針。

	查找指針?biāo)玫膬?nèi)存塊是否存在于紅黑樹(shù)中，如果不存在就跳過(guò)處理此對(duì)象。

	如果?kmemleak_object?對(duì)象不是白色，說(shuō)明已經(jīng)有指針引用此內(nèi)存塊，跳過(guò)處理此對(duì)象。

	對(duì)?kmemleak_object?對(duì)象的?count?字段進(jìn)行加一操作，表示有指針引用此內(nèi)存塊。

	判斷當(dāng)前?kmemleak_object?對(duì)象是否是灰色節(jié)點(diǎn)（count?字段大于或等于?min_count?字段），如果是將其添加到灰色節(jié)點(diǎn)鏈表中。

	掃描完畢后，所有白色的節(jié)點(diǎn)就是可能存在內(nèi)存泄漏的內(nèi)存塊。

	　　審核編輯：湯梓紅