細(xì)說｜Linux內(nèi)存泄漏檢測(cè)實(shí)現(xiàn)原理與實(shí)現(xiàn)
在使用沒有垃圾回收的語言時(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)核開發(fā)者開發(fā)出 kmemleak 功能。
下面我們來詳細(xì)介紹一下 kmemleak 這個(gè)功能的原理與實(shí)現(xiàn)。
kmemleak 原理
首先來分析一下，什么情況會(huì)導(dǎo)致 內(nèi)存泄漏。
1. 造成內(nèi)存泄漏的原因
內(nè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)存是不再使用的呢？一般來說，沒有被指針引用（指向）的內(nèi)存都是不再使用的內(nèi)存。因?yàn)檫@些內(nèi)存已經(jīng)丟失了其地址信息，從而導(dǎo)致內(nèi)核不能再使用這些內(nèi)存。
我們來看看下圖的事例：
如上圖所示，指針A原來指向內(nèi)存塊A，但后來指向新申請(qǐng)的內(nèi)存塊B，從而導(dǎo)致內(nèi)存塊A的內(nèi)存地址信息丟失。如果此時(shí)用戶沒有及時(shí)釋放掉內(nèi)存塊A，就會(huì)導(dǎo)致內(nèi)存泄漏。
當(dāng)然少量的內(nèi)存泄漏并不會(huì)造成很嚴(yán)重的效果，但如果是頻發(fā)性的內(nèi)存泄漏，將會(huì)造成系統(tǒng)內(nèi)存資源耗盡，從而導(dǎo)致系統(tǒng)崩潰。
2. 內(nèi)核中的指針
既然沒有指針引用的內(nèi)存屬于泄漏的內(nèi)存，那么只需要找出系統(tǒng)是否存在沒有指針引用的內(nèi)存，就可以判斷系統(tǒng)是否存在內(nèi)存泄漏。
那么，怎么找到內(nèi)核中的所有指針呢？我們知道，指針一般存放在 內(nèi)核數(shù)據(jù)段、內(nèi)核棧 和 動(dòng)態(tài)申請(qǐng)的內(nèi)存塊 中。如下圖所示：
但內(nèi)核并沒有對(duì)指針進(jìn)行記錄，也就是說內(nèi)核并不知道這些區(qū)域是否存在指針。那么內(nèi)核只能夠把這些區(qū)域當(dāng)成是由指針組成的，也就是說把這些區(qū)域中的每個(gè)元素都當(dāng)成是一個(gè)指針。如下圖所示：
當(dāng)然，把所有元素都當(dāng)成是指針是一個(gè)假設(shè)，所以會(huì)存在誤判的情況。不過這也沒關(guān)系，因?yàn)?nbsp;kmemleak 這個(gè)功能只是為了找到內(nèi)核中疑似內(nèi)存泄漏的地方。
3. 記錄動(dòng)態(tài)內(nèi)存塊
前面說過，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)存塊。如果存在沒有指針引用的內(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)存塊信息記錄下來，用于后續(xù)掃描時(shí)使用。內(nèi)核使用 kmemleak_object 對(duì)象來記錄這些內(nèi)存塊的信息，然后通過一棵紅黑樹把這些 kmemleak_object 對(duì)象組織起來（使用內(nèi)存塊的地址作為鍵），如下圖所示：
所以內(nèi)存泄漏檢測(cè)的原理是：
遍歷內(nèi)核中所有的指針，然后從紅黑樹中查找是否存在對(duì)應(yīng)的內(nèi)存塊，如果存在就把內(nèi)存塊打上標(biāo)記。 所有指針掃描完畢后，再遍歷紅黑樹中所有 kmemleak_object對(duì)象。如果發(fā)現(xiàn)沒有打上標(biāo)記的內(nèi)存塊，說明存在內(nèi)存泄漏（也就是說，存在沒有被指針引用的內(nèi)存塊），并且將對(duì)應(yīng)的內(nèi)存塊信息記錄下來。
kmemleak 實(shí)現(xiàn)
了解了 kmemleak 機(jī)制的原理后，現(xiàn)在我們來分析其代碼實(shí)現(xiàn)。
1. kmemleak_object 對(duì)象
上面介紹過，內(nèi)核通過 kmemleak_object 對(duì)象來記錄動(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ì)象連接到紅黑樹中。pointer：用于記錄內(nèi)存塊的起始地址。size：用于記錄內(nèi)存塊的大小。
內(nèi)核就是通過這 3 個(gè)字段，把 kmemleak_object 對(duì)象連接到全局紅黑樹中。
例如利用 kmalloc 函數(shù)申請(qǐng)內(nèi)存時(shí)，最終會(huì)調(diào)用 create_object 來創(chuàng)建 kmemleak_object 對(duì)象，并且將其添加到全局紅黑樹中。我們來看看 create_obiect 函數(shù)的實(shí)現(xiàn)，如下：
...
// 紅黑樹的根節(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ì)象添加到全局紅黑樹中
...
link = &object_tree_root.rb_node; // 紅黑樹根節(jié)點(diǎn)
rb_parent = NULL;
// 找到 kmemleak_object 對(duì)象插入的位置（參考平衡二叉樹的算法）
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ì)象插入到紅黑樹中
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ì)象添加到全局紅黑樹中。
將
kmemleak_object對(duì)象插入到全局紅黑樹的算法與數(shù)據(jù)結(jié)構(gòu)中的平衡二叉樹算法是一致的，所以不了解的同學(xué)可以查閱相關(guān)的資料。
2. 內(nèi)存泄漏檢測(cè)
當(dāng)開啟內(nèi)存泄漏檢測(cè)時(shí)，內(nèi)核將會(huì)創(chuàng)建一個(gè)名為 kmemleak 的內(nèi)核線程來進(jìn)行檢測(cè)。
在分析內(nèi)存檢測(cè)的實(shí)現(xiàn)之前，我們先來了解一下關(guān)于 kmemleak_object 對(duì)象的三個(gè)概念：
白色節(jié)點(diǎn)：表示此對(duì)象沒有被指針引用（ count字段少于min_count字段）。灰色節(jié)點(diǎn)：表示此對(duì)象被一個(gè)或多個(gè)指針引用（ count字段大于或等于min_count字段）。黑色節(jié)點(diǎn)：表示此對(duì)象不需要被掃描（ min_count字段等于 -1）。
接著我們來看看 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)核線程主要通過調(diào)用 kmemleak_scan 函數(shù)來進(jìn)行內(nèi)存泄漏掃描。我們繼續(xù)來看看 kmemleak_scan 函數(shù)的實(shí)現(xiàn)：
static void kmemleak_scan(void)
{
...
// 1) 將所有 kmemleak_object 對(duì)象的 count 字段置0，表示開始時(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 < end_pfn; pfn++) {
...
page = pfn_to_page(pfn);
...
scan_block(page, page + 1, NULL, 1);
}
}
...
// 4) 掃描所有進(jìn)程的內(nèi)核棧
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) 掃描所有灰色節(jié)點(diǎn)
scan_gray_list();
...
}
由于 kmemleak_scan 函數(shù)的代碼比較長(zhǎng)，所以我們對(duì)其進(jìn)行精簡(jiǎn)。精簡(jiǎn)后可以看出，kmemleak_scan 函數(shù)主要完成 5 件事情：
將系統(tǒng)中所有 kmemleak_object對(duì)象的count字段置 0，表示掃描開始時(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)行掃描。
掃描主要通過 scan_block 函數(shù)進(jìn)行，我們來看看 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 < end; ptr++) {
struct kmemleak_object *object;
unsigned long flags;
unsigned long pointer;
...
pointer = *ptr;
// 查找指針?biāo)玫膬?nèi)存塊是否存在于紅黑樹中，如果不存在就跳過此指針
object = find_and_get_object(pointer, 1);
if (!object)
continue;
...
// 如果對(duì)象不是白色，說明此內(nèi)存塊已經(jīng)被指針引用
if (!color_white(object)) {
...
continue;
}
// 對(duì) kmemleak_object 對(duì)象的count字段進(jìn)行加一操作
object->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)存塊是否存在于紅黑樹中，如果不存在就跳過處理此對(duì)象。 如果 kmemleak_object對(duì)象不是白色，說明已經(jīng)有指針引用此內(nèi)存塊，跳過處理此對(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)存塊。