圖解 Linux 內存碎片整理

我們知道物理內存是以頁爲單位進行管理的，每個內存頁大小默認是 4K（大頁除外）。申請物理內存時，一般都是按順序分配的，但釋放內存的行爲是隨機的。隨着系統運行時間變長後，將會出現以下情況：

如上圖所示，當用戶需要申請地址連續的 3 個內存頁時，雖然系統中空閒的內存頁數量足夠，但由於空閒的內存頁相對分散，從而導致分配失敗。這些地址不連續的內存頁被稱爲：內存碎片。

要解決這個問題也比較簡單，只需要把空閒的內存塊移動到一起即可。如下圖所示：

網絡上有句很有名的話：理想很美好，現實很骨感。

內存整理也是這樣，看起來很簡單，但實現起來就不那麼簡單了。因爲在內存整理後，需要修正進程的虛擬內存與物理內存之間的映射關係。如下圖所示：

但由於 Linux 內核有個名爲 內存頁反向映射 的功能，所以內存整理就變得簡單起來。

接下來，我們將會分析內存碎片整理的原理與實現。

內存碎片整理原理

內存碎片整理的原理比較簡單：在內存碎片整理開始前，會在內存區的頭和尾各設置一個指針，頭指針從頭向尾掃描可移動的頁，而尾指針從尾向頭掃描空閒的頁，當他們相遇時終止整理。下面說說內存隨便整理的過程（原理參考了內核文檔）：

初始時內存狀態：

在上圖中，白色塊表示空閒的內存頁，而紅色塊表示已分配出去的內存頁。在初始狀態時，內存中存在多個碎片。如果此時要申請 3 個地址連續的內存頁，那麼將會申請失敗。

內存碎片整理掃描開始：

頭部指針從頭掃描可移動頁，而尾部指針從從尾掃描空閒頁。在整理時，將可移動頁的內容複製到空閒頁中。複製完成後，將可移動內存頁釋放即可。

最後結果：

經過內存碎片整理後，如果現在要申請 3 個地址連續的內存頁，就能申請成功了。

內存碎片整理實現

接下來，我們將會分析內存碎片整理的實現過程。

注：本文使用的是 Linux-2.6.36 版本的內存

1. 內存碎片整理時機

當要申請多個地址聯繫的內存頁時，如果申請失敗，將會進行內存碎片整理。其調用鏈如下：

alloc_pages_node()
└→ __alloc_pages()
   └→ __alloc_pages_nodemask()
      └→ __alloc_pages_slowpath()
         └→ __alloc_pages_direct_compact()

當調用 alloc_pages_node() 函數申請多個地址連續的內存頁失敗時，將會觸發調用 __alloc_pages_direct_compact() 函數來進行內存碎片整理。我們來看看 __alloc_pages_direct_compact() 函數的實現：

static struct page *
__alloc_pages_direct_compact(gfp_t gfp_mask, 
                             unsigned int order, 
                             struct zonelist *zonelist, 
                             enum zone_type high_zoneidx, 
                             nodemask_t *nodemask, 
                             int alloc_flags,
                             struct zone *preferred_zone,
                             int migratetype, 
                             unsigned long *did_some_progress)
{
    struct page *page;

    // 1. 如果申請一個內存頁，那麼就沒有整理碎片的必要（這說明是內存不足，而不是內存碎片導致）
    if (!order || compaction_deferred(preferred_zone))
        return NULL;

    // 2. 開始進行內存碎片整理
    *did_some_progress = try_to_compact_pages(zonelist, order, gfp_mask, nodemask);

    if (*did_some_progress != COMPACT_SKIPPED) {
        ...
        // 3. 整理完內存碎片後，繼續嘗試申請內存塊
        page = get_page_from_freelist(gfp_mask, nodemask, order, zonelist, 
                                      high_zoneidx, alloc_flags, preferred_zone, 
                                      migratetype);
        if (page) {
            ...
            return page;
        }
        ...
    }

    return NULL;
}

__alloc_pages_direct_compact() 函數是內存碎片整理的入口，其主要完成 3 個步驟：

先判斷申請的內存塊是否只有一個內存頁，如果是，那麼就沒有整理碎片的必要（這說明是內存不足，而不是內存碎片導致）。
如果需要進行內存碎片整理，那麼調用 try_to_compact_pages() 函數進行內存碎片整理。
整理完內存碎片後，調用 get_page_from_freelist() 函數繼續嘗試申請內存塊。

2. 內存碎片整理過程

由於內存碎片整理的具體實現在 try_to_compact_pages() 函數中進行，所以我們繼續來看看 try_to_compact_pages() 函數的實現：

unsigned long
try_to_compact_pages(struct zonelist *zonelist, int order, gfp_t gfp_mask,
                     nodemask_t *nodemask)
{
    ...
    // 1. 遍歷所有內存區（由於內核會把物理內存分成多個內存區進行管理）
    for_each_zone_zonelist_nodemask(zone, z, zonelist, high_zoneidx, nodemask) {
        ...
        // 2. 對內存區進行內存碎片整理
        status = compact_zone_order(zone, order, gfp_mask);
        ...
    }

    return rc;
}

可以看出，try_to_compact_pages() 函數最終會調用 compact_zone_order() 函數來進行內存碎片整理。我們只能進行來分析 compact_zone_order() 函數：

static unsigned long
compact_zone_order(struct zone *zone, int order, gfp_t gfp_mask)
{
    struct compact_control cc = {
        .nr_freepages = 0,
        .nr_migratepages = 0,
        .order = order,
        .migratetype = allocflags_to_migratetype(gfp_mask),
        .zone = zone,
    };
    INIT_LIST_HEAD(&cc.freepages);
    INIT_LIST_HEAD(&cc.migratepages);

    return compact_zone(zone, &cc);
}

到這裏，我們還沒有看到內存碎片整理的具體實現（調用鏈可真深啊 ^_^！），compact_zone_order() 函數也是構造了一些參數，然後繼續調用 compact_zone() 來進行內存碎片整理：

static int compact_zone(struct zone *zone, struct compact_control *cc)
{
    ...
    while ((ret = compact_finished(zone, cc)) == COMPACT_CONTINUE) {
        ...
        // 1. 收集可移動的內存頁列表
        if (!isolate_migratepages(zone, cc))
            continue;
        ...
        // 2. 將可移動的內存頁列表遷移到空閒列表中
        migrate_pages(&cc->migratepages, compaction_alloc, (unsigned long)cc, 0);
        ...
    }
    ...
    return ret;
}

在 compact_zone() 函數里，我們終於看到內存碎片整理的邏輯了。compact_zone() 函數主要完成 2 個步驟：

調用 isolate_migratepages() 函數收集可移動的內存頁列表。
調用 migrate_pages() 函數將可移動的內存頁列表遷移到空閒列表中。

這兩個函數非常重要，我們分別來分析它們是怎麼實現的。

isolate_migratepages() 函數

isolate_migratepages() 函數用於收集可移動的內存頁列表，我們來看看其實現：

static unsigned long
isolate_migratepages(struct zone *zone, struct compact_control *cc)
{
    unsigned long low_pfn, end_pfn;
    struct list_head *migratelist = &cc->migratepages;
    ...

    // 1. 掃描內存區所有的內存頁
    for (; low_pfn < end_pfn; low_pfn++) {
        struct page *page;
        ...

        // 2. 通過內存頁的編號獲取內存頁對象
        page = pfn_to_page(low_pfn);
       ...

        // 3. 判斷內存頁是否可移動內存頁，如果不是可移動內存頁，那麼就跳過
        if (__isolate_lru_page(page, ISOLATE_BOTH, 0) != 0)
            continue;

        // 4. 將內存頁從 LRU 隊列中刪除
        del_page_from_lru_list(zone, page, page_lru(page));

        // 5. 添加到可移動內存頁列表中
        list_add(&page->lru, migratelist); 
        ...
        cc->nr_migratepages++;
        ...
    }
    ...
    return cc->nr_migratepages;
}

isolate_migratepages() 函數主要完成 5 個步驟，分別是：

掃描內存區所有的內存頁（與內存碎片整理原理一致）。
通過內存頁的編號獲取內存頁對象。
判斷內存頁是否可移動內存頁，如果不是可移動內存頁，那麼就跳過。
將內存頁從 LRU 隊列中刪除，這樣可避免被其他進程回收這個內存頁。
添加到可移動內存頁列表中。

當完成這 5 個步驟後，內核就收集到可移動的內存頁列表。

migrate_pages() 函數

migrate_pages() 函數負責將可移動的內存頁列表遷移到空閒列表中，我們來分析一下其實現過程：

int migrate_pages(struct list_head *from, new_page_t get_new_page,
                  unsigned long private, int offlining)
{
    ...

    for (pass = 0; pass < 10 && retry; pass++) {
        retry = 0;

        // 1. 遍歷可移動內存頁列表
        list_for_each_entry_safe(page, page2, from, lru) {
            ...
            // 2. 將可移動內存頁遷移到空閒內存頁中
            rc = unmap_and_move(get_new_page, private, page, pass > 2, offlining);
            switch(rc) {
            case -ENOMEM:
                goto out;
            case -EAGAIN:
                retry++;
                break;
            case 0:
                break;
            default:
                nr_failed++;
                break;
            }
        }
    }
    ...
    return nr_failed + retry;
}

migrate_pages() 函數的邏輯很簡單，主要完成 2 個步驟：

遍歷可移動內存頁列表，這個列表就是通過 isolate_migratepages() 函數收集的可移動內存頁列表。
調用 unmap_and_move() 函數將可移動內存頁遷移到空閒內存頁中。

可以看出，具體的內存遷移過程在 unmap_and_move() 函數中實現。我們來看看 unmap_and_move() 函數的實現：

static int
unmap_and_move(new_page_t get_new_page, unsigned long private,
               struct page *page, int force, int offlining)
{
    ...
    // 1. 從內存區中找到一個空閒的內存頁
    struct page *newpage = get_new_page(page, private, &result);
    ...

    // 2. 解開所有使用了當前可移動內存頁的進程的虛擬內存映射（涉及到內存頁反向映射）
    try_to_unmap(page, TTU_MIGRATION|TTU_IGNORE_MLOCK|TTU_IGNORE_ACCESS);

skip_unmap:
    // 3. 將可移動內存頁的數據複製到空閒內存頁中
    if (!page_mapped(page))
        rc = move_to_new_page(newpage, page, remap_swapcache);
    ...
    return rc;
}

由於 unmap_and_move() 函數的實現比較複雜，所以我們對其進行了簡化。可以看出，unmap_and_move() 函數主要完成 3 個工作：

從內存區中找到一個空閒的內存頁。根據內存碎片整理算法，會從內存區最後開始掃描，找到合適的空閒內存頁。
由於將可移動內存頁遷移到空閒內存頁後，進程的虛擬內存映射將會發生變化。所以，這裏要調用 try_to_unmap() 函數來解開所有使用了當前可移動內存頁的映射。
調用 move_to_new_page() 函數將可移動內存頁的數據複製到空閒內存頁中。在 move_to_new_page() 函數中，還會重新建立進程的虛擬內存映射，這樣使用了當前可移動內存頁的進程就能夠正常運行。

至此，內存碎片整理的過程已經分析完畢。

不過細心的讀者可能發現，在文中並沒有分析重新構建虛擬內存映射的過程。是的，因爲重新構建虛擬內存映射要涉及到 內存頁反向映射 的知識點，後續的文章會介紹這個知識點，所以這裏就不作詳細分析了。

總結

從上面的分析可知，內存碎片整理 是爲了解決：在申請多個地址連續的內存頁時，空閒內存頁數量充足，但還是分配失敗的情況。

但由於內存碎片整理需要消耗大量的 CPU 時間，所以我們在申請內存時，可以通過指定 __GFP_WAIT 標誌位（不等待）來避免內存碎片整理過程。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/UigCRrFTIp59pcDbKegSdg