本文出現的內核代碼來自Linux4.19，如果有興趣，讀者可以配合代碼閱讀本文。

一、Linux物理內存外碎片化概述

什麼是Linux物理內存碎片化？Linux物理內存碎片化包括兩種：

1.物理內存內碎片：指分配給用戶的內存空間中未被使用的部分。

例如進程需要使用3K bytes物理內存，於是向系統申請了大小等於3Kbytes的內存，但是由於Linux內核夥伴系統算法最小顆粒是4K bytes，所以分配的是4Kbytes內存，那麼其中1K bytes未被使用的內存就是內存內碎片。

Linux物理內存內碎片

2.物理內存外碎片化：指系統中無法利用的小內存塊。

例如系統剩餘內存爲16K bytes，但是這16K bytes內存是由4個4K bytes的頁面組成，即16K內存物理頁幀號#1不連續。在系統剩餘16K bytes內存的情況下，系統卻無法成功分配大於4K的連續物理內存，該情況就是內存外碎片導致，本文中闡述的就是物理內存外碎片化。

注：#1物理頁幀號：Linux物理內存是通過頁面進行管理，並對每個頁面進行編號，稱爲頁幀號，如果是連續的兩個物理頁面，其頁幀號是連續的。

Linux物理內存外碎片

二、Linux物理內存管理框架

闡述物理內存外碎片化的來龍去脈前，先得明白Linux是如何管理物理內存的？Linux內核採用的是buddy system allocation，即著名的夥伴系統分配器。

1.設計思路

夥伴系統分配器的核心思路：將系統的空閒頁面分爲11個塊鏈表，每個塊鏈表分別管理着1,2,4,8,16,32,64,128,256,512和1024個物理頁幀號連續的頁面。每個頁面大小爲4K bytes，buddy管理的塊大小範圍從4K bytes到4M bytes，以2的倍數遞增。

Linux物理內存管理框架圖

2.管理邏輯

Linux對物理頁面管理的框架如上圖，由於本文闡述的是物理內存外碎片，所以關於夥伴系統本文只做簡單分析，不涉及具體的細節並不闡述關於per cpu pageset等內容，如果讀者有興趣，可以參考內核源碼。

Linux將物理內存分爲不同的node和zone來管理：

  • node：爲了支持NUMA結構，即CPU對不同內存簇的訪問速度不同，Linux設計了node結構，將物理內存分爲多個內存節點管理；對於UMA結構，只有一個node節點。

  • zone：爲兼容不同的平臺的硬件限制，例如80x86的體系結構的硬件總線訪問等問題，Linux將node節點下的內存分爲多個zone；目前在ARM平臺，多個zone管理已非必要。

zone管理單元下的內存通過free_area數組將內存分成11個塊鏈表進行管理：

free_area數組總共有11個索引，每個索引管理着不同大小的塊鏈表。

  • free_area[0]管理的內存單位爲2^0頁面，即4K byte內存；

  • free_area[1]管理的內存單位爲2^1的物理頁幀號連續頁面，即8K bytes內存；

  • 以此類推；

free_area管理的內存還細分爲各種類型，例如不可移動頁面和可移動頁面等，每種類型的頁面類型對應一個free_list鏈表，該鏈表就鏈接着頁面結構體。

當分配頁面時，夥伴系統拿頁面的步驟如下：（不考慮內存慢速路徑）

  • 根據分配頁面類型，找到對應的內存節點node和內存管理單元zone；

  • 根據分配頁面大小，找到的對應大小的free_area結構體；

  • 根據分配頁面類型，找到對應的free_list鏈表，分配頁面；

當向夥伴系統釋放頁面時，buddy釋放頁面的步驟如下：

  • 根據分配頁面類型，找到對應的內存節點node和內存管理單元zone；

  • 判斷是否有物理頁幀號相連的空閒內存塊，可以跟被釋放的內存塊合併成更大的塊內存，合併的條件：

  • 物理幀必須都是連續的；

  • 相同的類型和相同的大小；

  • 合併後塊內存的第一個頁面的物理地址滿足”2*塊大小*4K”的倍數。

  • 根據釋放頁面的大小或者合併的大小，找到的對應大小的free_area結構體；

  • 根據釋放頁面的類型，找到對應的free_list鏈表，釋放頁面；

三、Linux針對物理內存外碎片化的措施

從“二、Linux物理內存管理架構”，可以發現夥伴系統內存管理框架是可以有效改善物理內存外碎片的，因爲夥伴系統有如下兩個管理邏輯，可以減少了外碎片化的產生：

  • 小塊內存在小塊鏈表分配，減少大塊鏈表被污染的概率；

  • 內存釋放時會嘗試整合成大塊內存的邏輯，有助於大塊內存的合成；

除此之外，內核還支持以下措施改善物理內存外碎片化（只列舉主要的機制）：

1.memory compaction

（1）內存規整原理

Linux物理頁面規整機制，類似於磁盤整理，主要是應用了內核的頁面遷移機制，是一種將可移動頁面進行遷移後騰出連續物理內存的方法。

假設存在一個非常小的內存域如下：

藍色表示空閒的頁面，白色表示已經被分配的頁面，可以看到如上內存域的空閒頁面（藍色）非常零散，無法分配大於兩頁的連續物理內存。

下面演示一下內存規整的簡化工作原理，內核會運行兩個獨立的掃描動作：第一個掃描從內存域的底部開始，一邊掃描一邊將已分配的可移動（MOVABLE）頁面記錄到一個列表中：

另外第二掃描是從內存域的頂部開始，掃描可以作爲頁面遷移目標的空閒頁面位置，然後也記錄到一個列表裏面：

等兩個掃描在域中間相遇，意味着掃描結束，然後將左邊掃描得到的已分配的頁面遷移到右邊空閒的頁面中，左邊就形成了一段連續的物理內存，完成頁面規整。

（2）使用方法

如果想打開內存規整，內核需要打開相關的配置（默認爲y）

打開如上配置後，內存規整的觸發是自動的，觸發內存規整的途徑如下：當進程嘗試分配高階內存無法滿足並且完成direct_reclaim#1（暫不分析costly_order情況）後，系統會根據內存剩餘判斷是否觸發內存規整；

注：#1direct_reclaim：進程分配內存時發現內存不足從而啓動直接回收內存操作，這種模式下分配和回收是同步的關係，也就是說分配內存的進程會因爲等待內存回收而被阻塞。

內核也提供了接口給用戶觸發規整動作，接口如下：

/proc/sys/vm/compact_memory

只要往這個節點寫值即可觸發對系統所有node管理的內存做內存規整。

2.kcompactd

（1）kcompact設計原理

kcompactd是一個內核規整的後臺進程，它跟memory compaction的區別在於：

memory compaction的觸發途徑是內存分配進入direct_reclaim（暫不分析costly_order情況）後系統會根據內存剩餘判斷是否觸發內存規整，或者用戶手動觸發；

kcompactd在喚醒kswapd或者kswapd進入休眠時，主動觸發內存規整。

kcompactd的觸發路徑如下：主要有如下兩個途徑：

喚醒kswapd之前觸發規整，觸發的條件是：本次分配不支持direct_reclaim，node內存節點是平衡的，並且kswapd失敗的次數大於MAX_RECLAIM_RETRIES（默認16）。

kswapd即將進入睡眠時：

（2）使用方法

如果想打開內存規整，內核需要打開相關的配置（默認爲y）

3.其他優化的思路

內核經過不斷的優化，那爲何Linux爲何還有物理內存外碎片化呢？那是因爲物理內存外碎片化雖然是可以不斷優化的，但卻無法得到根除。目前的內核，我覺得導致物理外碎片化還有以下兩個主要原因：

  • 不可移動頁面污染了內存環境，導致頁面規整失敗；

  • 隨着系統不斷申請和釋放的頁面，導致夥伴系統分配的物理內存頁幀號越發隨機，從而導致內存被隔斷的概率越高，碎片化的程度越高，在3.2闡述。

針對以上兩個原因，以下的優化措施可能達到一定的優化效果：

（1）減少UNMOVABLE頁面污染內存環境

  • 限制不可以移動頁面偷頁行爲

Linux內存分配中支持fallback機制，又叫偷頁機制。該機制是爲了規避同個zone管理單位頁面類型剩餘不平衡的問題，例如同個zone，A頁面類型空閒內存較多，B頁面類型空閒內存卻非常緊缺，如果沒有偷頁機制，分配B頁面類型就會進入內存分配慢速路徑。有了偷頁機制，在同個zone管理單位，如果UNMOVABLE類型無空閒頁面，但是MOVABLE類型頁面還有空閒頁面，偷頁機制支持在list_head[UNMOVABLE]分配不到頁面的情況下，向list_head[MOVABLE]分配頁面。

以下數組明確了各種頁面類型可偷的頁面類型，例如第一行表示UNMOVABLE頁面可以偷RECLAIMABLE和MOVABLE類型的頁面，其他類似。

如果不可移動頁面頻繁的偷頁會導致不可移動頁面很快污染了內存環境，特別污染了可移動頁面的內存，對內存規整成功率的影響比較大。基於以上情況，可以在偷頁的機制上加上分配大小限制的判斷，不可移動頁面只有大塊內存分配才允許偷頁，以此減少不可移動頁面對內存環境的污染。

  • 不可移動類型頁面偷頁後主動償還

該方法主要是不可移動頁面偷頁後的一種補償方法。如果發生不可移動頁面偷頁後，我們將該頁面記錄到一個列表，等後續不可移動頁面類型存在空閒頁面時，將所偷的頁面遷移回不可移動頁面中，從而降低不可移動頁面的污染。

（2）降低分配頁幀號的隨機性

假設有一塊小內存域如下，以下兩種內存分配方式哪種會導致嚴重的內存碎片化？

  • 頁面從頭部開始分配，直到尾部；

  • 頁面隨機從任何位置分配。

明顯是第二種內存分配方式的對內存外碎片化更不友好，而這點也是夥伴系統目前沒有解決的問題。夥伴系統雖然將內存規劃成各種大小的內存塊，以讓小內存分配在小塊鏈表分配，儘量不污染大塊內存鏈表，但是卻沒辦法保證小塊內存具體是在物理內存的哪個頁幀範圍分配。隨着系統的運行越久，小塊內存的分配的物理頁幀號越發隨機，那麼其導致碎片化的概率就會越高。

  • 預留法

根據這種情況，可以通過預留的方式進行相應的優化。

預留一定的內存專門用於小塊內存分配，經過這個優化措施後，可以有效降低小塊內存分配的物理頁幀號的隨機性，從而降低小塊內存污染內存環境的概率。

預留一定的內存專門用於大塊內存分配，經過該優化措施後，預留的內存被小塊內存污染的概率就會降低，可以提升預留內存分配大塊內存的成功率。

另外關於降低夥伴系統分配頁幀號隨機性，還是存在很多優化的措施，後續根據需要會專門開展一篇闡述該部分優化的文章，如果讀者有興趣，到時可以查閱。

參考文獻

1、內核源代碼

2、http://tinylab.org/lwn-368869/

3、https://patchwork.kernel.org/patch/

長按關注

內核工匠微信

Linux 內核黑科技 | 技術文章 | 精選教程

相關文章