現在的 Linux 內核和 Linux 2.6 的內核有多大區別？

12-30

現在已經是4.X了，但是據說2.6升到3.0，以及3.19升到4.0這之間都沒什麼太大的原因。那麼現在的內核2.6時代區別有多大？

----------------------------------------------------------------------------------------------------------------

因研究興趣轉移, 個人時間，精力，能力有限等原因, 本人不會再有更新, 請見諒。

本人放棄本文版權。並歡迎有更多志於 Linux 內核開源/希望學習內核知識的朋友,

能以社區合作的方式擴充維護本文。本人願意提供綿薄之力參與其中, 提供一點幫助。

有問題歡迎指出，交流。

-----------------------------------------------------------------------------------------------------------------

這個問題挺大的。

2.6 時代跨度非常大，從2.6.0 (2003年12月發布[36]) 到 2.6.39(2011年5月發布), 跨越了 40 個大版本。

3.0(原計劃的 2.6.40, 2011年7月發布) 到 3.19（2015年2月發布）。

4.0（2015年4月發布）到4.2（2015年8月底發布）。

總的來說，從進入2.6之後，每個大版本跨度開發時間大概是 2 - 3 個月。2.6.x , 3.x, 4.x，數字的遞進並沒有非常根本性，非常非常非常引人注目的大變化，但每個大版本中都有一些或大或小的功能改變。主版本號只是一個數字而已。不過要直接從 2.6.x 升級到 3.x, 乃至 4.x，隨著時間間隔增大，出問題的機率當然大很多。

個人覺得 Linux 真正走入嚴肅級別的高穩定性，高可用性，高可伸縮性的工業級別內核大概是在 2003 年後吧。一是隨著互聯網的更迅速普及，更多的人使用、參與開發。二也是社區經過11年發展，已經慢慢摸索出一套很穩定的協同開發模式，一個重要的特點是社區開始使用版本管理工具進入管理，脫離了之前純粹手工（或一些輔助的簡陋工具）處理代碼郵件的方式，大大加快了開發的速度和力度。

因此，我匯總分析一下從 2.6.12 (2005年6月發布，也就是社區開始使用 git 進行管理後的第一個大版本），到 4.2 (2015年8月發布)這中間共 51個大版本，時間跨度10年的主要大模塊的一些重要的變革。

(感謝知友 @costa 提供無水印題圖 )

預計內容目錄：

調度子系統(scheduling) [已完成]
內存管理子系統(memory management) [已完成]
中斷與異常子系統(interrupt exception)[填坑中]
時間子系統(timer timekeeping)
同步機制子系統(synchronization)
塊層(block layer)
文件子系統(Linux 通用文件系統層VFS, various fs)
網路子系統(networking)
調試和追蹤子系統(debugging, tracing)
虛擬化子系統(kvm)
控制組(cgroup)

============== 海量正文分割線 ==============

調度子系統(scheduling)

概述：Linux 是一個遵循 POSIX 標準的類 Unix 操作系統(然而它並不是 Unix 系統[1])，POSIX 1003.1b 定義了調度相關的一個功能集合和 API 介面[2]。調度器的任務是分配 CPU 運算資源，並以協調效率和公平為目的。效率可從兩方面考慮: 1) 吞吐量(throughput) 2)延時(latency)。不做精確定義，這兩個有相互矛盾的衡量標準主要體現為兩大類進程：一是 CPU 密集型，少量 IO 操作，少量或無與用戶交互操作的任務（強調吞吐量，對延時不敏感，如高性能計算任務 HPC), 另一則是 IO 密集型, 大量與用戶交互操作的任務(強調低延時，對吞吐量無要求，如桌面程序)。公平在於有區分度的公平，多媒體任務和數值計算任務對延時和限定性的完成時間的敏感度顯然是不同的。

為此， POSIX 規定了操作系統必須實現以下調度策略(scheduling policies), 以針對上述任務進行區分調度：

- SCHED_FIFO

- SCHED_RR

這兩個調度策略定義了對實時任務，即對延時和限定性的完成時間的高敏感度的任務。前者提

供 FIFO 語義，相同優先順序的任務先到先服務，高優先順序的任務可以搶佔低優先順序的任務；後者提供 Round-Robin 語義，採用時間片，相同優先順序的任務當用完時間片會被放到隊列尾

部，以保證公平性，同樣，高優先順序的任務可以搶佔低優先順序的任務。不同要求的實時任務可

以根據需要用 sched_setscheduler() API 設置策略。

- SCHED_OTHER

此調度策略包含除上述實時進程之外的其他進程，亦稱普通進程。採用分時策略，根據動態優

先級(可用 nice() API設置），分配 CPU 運算資源。 注意：這類進程比上述兩類實時進程優先

級低，換言之，在有實時進程存在時，實時進程優先調度。

Linux 除了實現上述策略，還額外支持以下策略：

- SCHED_IDLE 優先順序最低，在系統空閑時才跑這類進程(如利用閑散計算機資源跑地外文明搜索，蛋白質結構分析等任務，是此調度策略的適用者）

- SCHED_BATCH 是 SCHED_OTHER 策略的分化，與 SCHED_OTHER 策略一樣，但針對吞吐量優化

- SCHED_DEADLINE 是新支持的實時進程調度策略，針對突髮型計算，且對延遲和完成時間高度敏感的任務適用。

除了完成以上基本任務外，Linux 調度器還應提供高性能保障，對吞吐量和延時的均衡要有好的優化；要提供高可擴展性(scalability)保障，保障上千節點的性能穩定；對於廣泛作為伺服器領域操作系統來說，它還提供豐富的組策略調度和節能調度的支持。

-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*　重要功能和時間點　-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*

目錄:

1 搶佔支持(preemption)

2 普通進程調度器(SCHED_OTHER)之糾極進化史

3 有空時再跑 SCHED_IDLE

4 吭哧吭哧跑計算 SCHED_BATCH

5 十萬火急，限期完成 SCHED_DEADLINE

6 普通進程的組調度支持(Fair Group Scheduling)

7 實時進程的組調度支持(RT Group Scheduling)

8 組調度帶寬控制(CFS bandwidth control)

9 極大提高體驗的自動組調度(Auto Group Scheduling)

10 基於調度域的負載均衡

11 更精確的調度時鐘(HRTICK)

12 自動 NUMA 均衡(Automatic NUMA balancing)

13 CPU 調度與節能

-*-*-*-*-*-*-*-*-*-*-*-*-*-*-* 正文 -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*

1 搶佔支持(preemption): 2.6 時代開始支持(首次在2.5.4版本引入[37], 感謝知友 @costa 考證! 關於 Linux 版本規則，可看我文章[4]).

可搶佔性，對一個系統的調度延時具有重要意義。2.6 之前，一個進程進入內核態後，別的進程無法搶佔，只能等其完成或退出內核態時才能搶佔, 這帶來嚴重的延時問題，2.6 開始支持內核態搶佔。

2 普通進程調度器(SCHED_OTHER)之糾極進化史:

Linux 一開始，普通進程和實時進程都是基於優先順序的一個調度器, 實時進程支持 100 個優先順序，普通進程是優先順序小於實時進程的一個靜態優先順序，所有普通進程創建時都是默認此優先順序，但可通過 nice() 介面調整動態優先順序(共40個). 實時進程的調度器比較簡單，而普通進程的調度器，則歷經變遷[5]:

2.1 O(1) 調度器: 2.6 時代開始支持(2002年引入)。顧名思義，此調度器為O(1)時間複雜度。該調度器修正之前的O(n) 時間複雜度調度器，以解決擴展性問題。為每一個動態優先順序維護隊列，從而能在常數時間內選舉下一個進程來執行。

2.2 夭折的 RSDL(The Rotating Staircase Deadline Scheduler)調度器, 2007 年 4 月提出，預期進入 2.6.2２, 後夭折。

O(1) 調度器存在一個比較嚴重的問題: 複雜的交互進程識別啟發式演算法 - 為了識別交互性的和批處理型的兩大類進程，該啟發式演算法融入了睡眠時間作為考量的標準，但對於一些特殊的情況，經常判斷不準，而且是改完一種情況又發現一種情況。

Con Kolivas (八卦：這傢伙白天是個麻醉醫生)為解決這個問題提出RSDL（The Rotating Staircase Deadline Scheduler)演算法。該演算法的亮點是對公平概念的重新思考: 互動式(A)和批量式(B)進程應該是被完全公平對待的，對於兩個動態優先順序完全一樣的 A, B 進程，它們應該被同等地對待，至於它們是互動式與否(互動式的應該被更快調度),　應該從他們對分配給他們的時間片的使用自然地表現出來，而不是應該由調度器自作高明地根據他們的睡眠時間去猜測。這個演算法的核心是Rotating Staircase, 是一種衰減式的優先順序調整，不同進程的時間片使用方式不同，會讓它們以不同的速率衰減(在優先順序隊列數組中一級一級下降，這是下樓梯這名字的由來), 從而自然地區分開來進程是互動式的(間歇性的少量使用時間片)和批量式的(密集的使用時間片)。具體演算法細節可看這篇文章:The Rotating Staircase Deadline Scheduler [LWN.net]

2.3 完全公平的調度器(CFS), 2.6.23(2007年10月發布)

Con Kolivas 的完全公平的想法啟發了原 O(1)調度器作者 Ingo Molnar, 他重新實現了一個新的調度器，叫 CFS(Completely Fair Scheduler)。新調度器的核心同樣是完全公平性, 即平等地看待所有普通進程，讓它們自身行為彼此區分開來，從而指導調度器進行下一個執行進程的選舉。

具體說來，此演算法基於一個理想模型。想像你有一台無限個相同計算力的 CPU, 那麼完全公平很容易，每個 CPU 上跑一個進程即可。但是，現實的機器 CPU 個數是有限的，超過 CPU 個數的進程數不可能完全同時運行。因此，演算法為每個進程維護一個理想的運行時間，及實際的運行時間，這兩個時間差值大的，說明受到了不公平待遇，更應得到執行。

至於這種演算法如何區分互動式進程和批量式進程，很簡單。互動式的進程大部分時間在睡眠，因此它的實際運行時間很小，而理想運行時間是隨著時間的前進而增加的，所以這兩個時間的差值會變大。與之相反，批量式進程大部分時間在運行，它的實際運行時間和理想運行時間的差距就較小。因此，這兩種進程被區分開來。

CFS 的測試性能比 RSDS 好，並得到更多的開發者支持，所以它最終替代了 RSDL 在 2.6.23 進入內核，一直使用到現在。可以八卦的是，Con Kolivas 因此離開了社區，不過他本人否認是因為此事而心生齟齬。後來，2009 年，他對越來越龐雜的 CFS 不滿意，認為 CFS 過分注重對大規模機器，而大部分人都是使用少 CPU 的小機器，開發了 BFS 調度器[6], 這個在 Android 中有使用，沒進入 Linux 內核。

3 有空時再跑 SCHED_IDLE, 2.6.23(2007年10月發布)

此調度策略和 CFS 調度器在同一版本引入。系統在空閑時，每個 CPU 都有一個 idle 線程在跑，它什麼也不做，就是把 CPU 放入硬體睡眠狀態以節能(需要特定CPU的driver支持), 並等待新的任務到來，以把 CPU 從睡眠狀態中喚醒。如果你有任務想在 CPU 完全 idle 時才執行，就可以用sched_setscheduler() API 設置此策略。

4 吭哧吭哧跑計算 SCHED_BATCH, 2.6.16(2006年3月發布)

概述中講到 SCHED_BATCH 並非 POSIX 標準要求的調度策略，而是 Linux 自己額外支持的。

它是從 SCHED_OTHER 中分化出來的, 和 SCHED_OTHER 一樣，不過該調度策略會讓採用策略的進程比 SCHED_OTHER 更少受到調度器的重視。因此，它適合非交互性的，CPU 密集運算型的任務。如果你事先知道你的任務屬於該類型，可以用 sched_setscheduler() API 設置此策略。

在引入該策略後，原來的 SCHED_OTHER 被改名為 SCHED_NORMAL, 不過它的值不變，因此保持 API 兼容，之前的 SCHED_OTHER 自動成為 SCHED_NORMAL, 除非你設置 SCHED_BATCH。

5 十萬火急，限期完成 SCHED_DEADLINE, 3.14(2014年3月發布)

此策略支持的是一種實時任務。對於某些實時任務，具有陣發性(sporadic),　它們陣發性地醒來執行任務，且任務有 deadline 要求，因此要保證在 deadline 時間到來前完成。為了完成此目標，採用該 SCHED_DEADLINE 的任務是系統中最高優先順序的，它們醒來時可以搶佔任何進程。

如果你有任務屬於該類型，可以用 sched_setscheduler() 或 sched_setattr() API 設置此策略。

更多可參看此文章：Deadline scheduling: coming soon? [LWN.net]

6 普通進程的組調度支持(Fair Group Scheduling), 2.6.24(2008年１月發布)

2.6.23 引入的 CFS 調度器對所有進程完全公平對待。但這有個問題，設想當前機器有２個用戶，有一個用戶跑著 9個進程，還都是 CPU 密集型進程；另一個用戶只跑著一個 X 進程，這是交互性進程。從 CFS 的角度看，它將平等對待這 10 個進程，結果導致的是跑 X 進程的用戶受到不公平對待，他只能得到約 10% 的 CPU 時間，讓他的體驗相當差。

基於此，組調度的概念被引入[6]。CFS 處理的不再是一個進程的概念，而是調度實體(sched entity), 一個調度實體可以只包含一個進程，也可以包含多個進程。因此，上述例子的困境可以這麼解決：分別為每個用戶建立一個組，組裡放該用戶所有進程，從而保證用戶間的公平性。

該功能是基於控制組(control group, cgroup)的概念，需要內核開啟 CGROUP 的支持才可使用。關於 CGROUP ，以後可能會寫。

7 實時進程的組調度支持(RT Group Scheduling), 2.6.25(2008年4月發布)

該功能同普通進程的組調度功能一樣，只不過是針對實時進程的。

8 組調度帶寬控制(CFS bandwidth control) , 3.2(2012年1月發布)

組調度的支持，對實現多租戶系統的管理是十分方便的，在一台機器上，可以方便對多用戶進行 CPU 均分．然後，這還不足夠，組調度只能保證用戶間的公平，但若管理員想控制一個用戶使用的最大 CPU 資源，則需要帶寬控制．3.2 針對 CFS組調度，引入了此功能[8], 該功能可以讓管理員控制在一段時間內一個組可以使用 CPU 的最長時間．

9 極大提高體驗的自動組調度(Auto Group Scheduling), 2.6.38(2011年3月發布)

試想，你在終端里熟練地敲擊命令，編譯一個大型項目的代碼，如 Linux內核，然後在編譯的同時悠閑地看著電影等待，結果電腦卻非常卡，體驗一定很不爽．

2.6.38 引入了一個針對桌面用戶體驗的改進，叫做自動組調度．短短400多行代碼[9], 就很大地提高了上述情形中桌面使用者體驗，引起不小轟動．

其實原理不複雜，它是基於之前支持的組調度的一個延伸．Unix 世界裡，有一個會話(session) 的概念，即跟某一項任務相關的所有進程，可以放在一個會話里，統一管理．比如你登錄一個系統，在終端里敲入用戶名，密碼，然後執行各種操作，這所有進程，就被規劃在一個會話里．

因此，在上述例子里，編譯代碼和終端進程在一個會話里，你的瀏覽器則在另一個會話里．自動組調度的工作就是，把這些不同會話自動分成不同的調度組，從而利用組調度的優勢，使瀏覽器會話不會過多地受到終端會話的影響，從而提高體驗．

該功能可以手動關閉．

10 基於調度域的負載均衡, 2.6.7(2004年6月發布)

計算機依靠並行度來突破性能瓶頸，CPU個數也是與日俱增。最早的是 SMP(對稱多處理), 所以 CPU共享內存，並訪問速度一致。隨著 CPU 個數的增加，這種做法不適應了，因為 CPU 個數的增多，增加了匯流排訪問衝突，這樣 CPU 增加的並行度被訪問內存匯流排的瓶頸給抵消了，於是引入了 NUMA(非一致性內存訪問)的概念。機器分為若干個node, 每個node(其實一般就是一個 socket)有本地可訪問的內存，也可以通過 interconnect 中介機構訪問別的 node 的內存，但是訪問速度降低了，所以叫非一致性內存訪問。Linux 2.5版本時就開始了對 NUMA 的支持[7]。

而在調度器領域，調度器有一個重要任務就是做負載均衡。當某個 CPU 出現空閑，就要從別的 CPU 上調整任務過來執行; 當創建新進程時，調度器也會根據當前負載狀況分配一個最適合的 CPU 來執行。然後，這些概念是大大簡化了實際情形。

在一個 NUMA 機器上，存在下列層級：

1. 每一個 NUMA node 是一個 CPU socket(你看主板上CPU位置上那一塊東西就是一個 socket).
2. 每一個socket上，可能存在兩個核，甚至四個核。
3. 每一個核上，可以打開硬體多純程(HyperThread)。

如果一個機器上同時存在這三人層級，則對調度器來說，它所見的一個邏輯 CPU其實是一人 HyperThread．處理同一個core 中的CPU , 可以共享L1, 乃至 L2 緩存，不同的 core 間，可以共享 L3 緩存(如果存在的話)．

基於此，負載均衡不能簡單看不同 CPU 上的任務個數，還要考慮緩存，內存訪問速度．所以，2.6.7 引入了調度域(sched domain) 的概念，把 CPU 按上述層級劃分為不同的層級，構建成一棵樹，葉子節點是每個邏輯 CPU, 往上一層，是屬於 core 這個域，再往上是屬於 socket 這個域，再往上是 NUMA 這個域，包含所有 CPU.

當進行負載均衡時，將從最低一級域往上看，如果能在 core 這個層級進行均衡，那最好；否則往上一級，能在socket 一級進行均衡也還湊合；最後是在 NUMA node 之間進行均衡，這是代價非常大的，因為跨 node 的內存訪問速度會降低，也許會得不償失，很少在這一層進行均衡．

這種分層的做法不僅保證了均衡與性能的平衡，還提高了負載均衡的效率．

關於這方面，可以看這篇文章：Scheduling domains [LWN.net]

11 更精確的調度時鐘(HRTICK), 2.6.25(2008年4月發布)

CPU的周期性調度，和基於時間片的調度，是要基於時鐘中斷來觸發的．一個典型的 1000 HZ 機器，每秒鐘產生 1000 次時間中斷，每次中斷到來後，調度器會看看是否需要調度．

然而，對於調度時間粒度為微秒(10^-6)級別的精度來說，這每秒 1000 次的粒度就顯得太粗糙了．

2.6.25引入了所謂的高清嘀噠(High Resolution Tick), 以提供更精確的調度時鐘中斷．這個功能是基於高精度時鐘(High Resolution Timer)框架，這個框架讓內核支持可以提供納秒級別的精度的硬體時鐘(將會在時鐘子系統里講).

12 自動 NUMA 均衡(Automatic NUMA balancing), 3.8(2013年2月發布)

NUMA 機器一個重要特性就是不同 node 之間的內存訪問速度有差異，訪問本地 node 很快，訪問別的 node 則很慢．所以進程分配內存時，總是優先分配所在 node 上的內存．然而，前面說過，調度器的負載均衡是可能把一個進程從一個 node 遷移到另一個 node 上的，這樣就造成了跨 node 的內存訪問；Linux 支持 CPU 熱插拔，當一個 CPU 下線時，它上面的進程會被遷移到別的 CPU 上，也可能出現這種情況．

調度者和內存領域的開發者一直致力於解決這個問題．由於兩大系統都非常複雜，找一個通用的可靠的解決方案不容易，開發者中提出兩套解決方案，各有優劣，一直未能達成一致意見．3.8內核中，內存領域的知名黑客 Mel Gorman 基於此情況，引入一個叫自動 NUMA 均衡的框架，以期存在的兩套解決方案可以在此框架上進行整合; 同時，他在此框架上實現了簡單的策略：每當發現有跨 node 訪問內存的情況時，就馬上把該內存頁面遷移到當前 node 上．

不過到 4.2 ，似乎也沒發現之前的兩套方案有任意一個遷移到這個框架上，倒是，在前述的簡單策略上進行更多改進．

如果需要研究此功能的話，可參考以下幾篇文章：

－介紹 3.8 前兩套競爭方案的文章：A potential NUMA scheduling solution [LWN.net]

- 介紹 3.8 自動 NUMA 均衡框架的文章：NUMA in a hurry [LWN.net]

- 介紹 3.8 後進展的兩篇文章，細節較多，建議對調度／內存代碼有研究後才研讀：

NUMA scheduling progress [LWN.net]

NUMA placement problems [LWN.net]

13 CPU 調度與節能

從節能角度講，如果能維持更多的 CPU 處於深睡眠狀態，僅保持必要數目的 CPU 執行任務，就能更好地節約電量，這對筆記本電腦來說，尤其重要．然而這不是一個簡單的工作，這涉及到負載均衡，調度器，節能模塊的並互，Linux 調度器中曾經有相關的代碼，但後來發現問題，在3.5, 3.6 版本中，已經把相關代碼刪除．整個問題需要重新思考．

在前不久，一個新的 patch 被提交到 Linux 內核開發郵件列表，這個問題也許有了新的眉目，到時再來更新此小節．可閱讀此文章：Steps toward power-aware scheduling [LWN.net]

========== 調度子系統結束分割線　==========

內存管理子系統(memory management)

概述：內存管理子系統，作為 kernel 核心中的核心，是承接所有系統活動的舞台，也是 Linux kernel 中最為龐雜的子系統, 沒有之一．截止 4.2 版本，內存管理子系統(下簡稱 MM)所有平台獨立的核心代碼(C文件和頭文件)達到11萬6千多行，這還不包括平台相關的 C 代碼, 及一些彙編代碼；與之相比，調度子系統的平台獨立的核心代碼才2萬８千多行．

現代操作系統的 MM 提供的一個重要功能就是為每個進程提供獨立的虛擬地址空間抽象，為用戶呈現一個平坦的進程地址空間，提供安全高效的進程隔離，隱藏所有細節，使得用戶可以簡單可移植的庫介面訪問／管理內存，大大解放程序員生產力．

在繼續往下之前，先介紹一些 Linux 內核中內存管理的基本原理和術語，方便後文討論．

- 物理地址(Physical Address): 這就是內存 DIMM 上的一個一個存儲區間的物理編址，以位元組為單位．

- 虛擬地址(Virtual Address): 技術上來講，用戶或內核用到的地址就是虛擬地址，需要 MMU (內存管理單元，一個用於支持虛擬內存的 CPU 片內機構) 翻譯為物理地址．在 CPU 的技術規範中，可能還有虛擬地址和線性地址的區別，但在這不重要．

- NUMA(Non-Uniform Memory Access): 非一致性內存訪問．NUMA 概念的引入是為了解決隨著 CPU 個數的增長而出現的內存訪問瓶頸問題，非一致性內存意為每個 NUMA 節點都有本地內存，提供高訪問速度；也可以訪問跨節點的內存，但要遭受較大的性能損耗．所以儘管整個系統的內存對任何進程來說都是可見的，但卻存在訪問速度差異，這一點對內存分配／內存回收都有著非常大的影響．Linux 內核於2.5版本引入對 NUMA的支持[7].

- NUMA node(NUMA節點)： NUMA 體系下，一個 node 一般是一個CPU socket(一個 socket 里可能有多個核）及它可訪問的本地內存的整體．

- zone(內存區): 一個 NUMA node 里的物理內存又被分為幾個內存區(zone), 一個典型的 node 的內存區劃分如下:

可以看到每個node里，隨著物理內存地址的增加，典型地分為三個區：

1. ZONE_DMA: 這個區的存在有歷史原因，古老的 ISA 匯流排外設，它們進行 DMA操作[10] 時，只能訪問內存物理空間低 16MB 的範圍．所以故有這一區，用於給這些設備分配內存時使用．
2. ZONE_NORMAL: 這是 32位 CPU時代產物，很多內核態的內存分配都是在這個區間(用戶態內存也可以在這部分分配，但優先在ZONE_HIGH中分配），但這部分的大小一般就只有 896 MiB, 所以比較局限． 64位 CPU 情況下，內存的訪問空間增大，這部分空間就增大了很多．關於為何這部分區間這麼局限，且內核態內存分配在這個區間，感興趣的可以看我之間一個回答[11].
3. ZONE_HIGH: 典型情況下，這個區間覆蓋系統所有剩餘物理內存．這個區間叫做高端內存區(不是高級的意思，是地址區間高的意思). 這部分主要是用戶態和部分內核態內存分配所處的區間．

- 內存頁/頁面(page): 現代虛擬內存管理／分配的單位是一個物理內存頁, 大小是 4096(4KB) 位元組. 當然，很多 CPU 提供多種尺寸的物理內存頁支持(如 X86, 除了4KB, 還有 2MB, 1GB頁支持），但 Linux 內核中的默認頁尺寸就是 4KB．內核初始化過程中，會對每個物理內存頁分配一個描述符(struct page), 後文描述中可能多次提到這個描述符，它是 MM 內部，也是 MM 與其他子系統交互的一個介面描述符．

- 頁表(page table): 從一個虛擬地址翻譯為物理地址時，其實就是從一個稀疏哈希表中查找的過程，這個哈希表就是頁表．

- 交換(swap): 內存緊缺時, MM 可能會把一些暫時不用的內存頁轉移到訪問速度較慢的次級存儲設備中(如磁碟, SSD), 以騰出空間,這個操作叫交換, 相應的存儲設備叫交換設備或交換空間.

- 文件緩存頁(PageCache Page): 內核會利用空閑的內存, 事先讀入一些文件頁, 以期不久的將來會用到, 從而避免在要使用時再去啟動緩慢的外設(如磁碟)讀入操作. 這些有後備存儲介質的頁面, 可以在內存緊缺時輕鬆丟棄, 等到需要時再次從外設讀入. 典型的代表有可執行代碼, 文件系統里的文件.

- 匿名頁(Anonymous Page): 這種頁面的內容都是在內存中建立的,沒有後備的外設, 這些頁面在回收時不能簡單的丟棄, 需要寫入到交換設備中. 典型的代表有進程的棧, 使用 malloc() 分配的內存所在的頁等 .

-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*　重要功能和時間點　-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*

下文將按此目錄分析 Linux 內核中 MM 的重要功能和引入版本:

目錄:

1 內存分配

2 內存去碎片化

3 頁表管理

4 頁面回收

5 頁面寫回

6 頁面預讀

7 大內存頁支持

8 內存控制組(Memory Cgroup)支持

9 內存熱插拔支持

10 超然內存(Transcendent Memory)支持

11 非易失性內存 (NVDIMM, Non-Volatile DIMM) 支持

12 內存管理調試支持

13 雜項

-*-*-*-*-*-*-*-*-*-*-*-*-*-*-* 正文 -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*

1 內存分配

1.1 頁分配器: 夥伴分配器[12] , 古老, 具體時間難考 , 應該是生而有之. orz...

內存頁分配器, 是 MM 的一個重大任務, 將內存頁分配給內核或用戶使用. 內核把內存頁分配粒度定為 11 個層次, 叫做階(order). 第0階就是 2^0 個(即1個)連續物理頁面, 第 1 階就是 2^1 個(即2個)連續物理頁面, ..., 以此類推, 所以最大是一次可以分配 2^10(= 1024) 個連續物理頁面.

所以, MM 將所有空閑的物理頁面以下列鏈表數組組織進來:

(圖片來自Physical Page Allocation)

那夥伴(buddy)的概念從何體現? 體現在釋放的時候, 當釋放某個頁面(組)時, MM 如果發現同一個階中如果有某個頁面(組) 跟這個要釋放的頁面(組) 是物理連續的, 那就把它們合併, 並升入下一階(如: 兩個 0 階的頁面, 合併後, 變為連續的2頁面(組), 即一個1階頁面). 兩個頁面(組) 手拉手升階, 所以叫夥伴.

關於NUMA 支持: Linux 內核中, 每個 zone 都有上述的鏈表數組, 從而提供精確到某個 node 的某個 zone 的夥伴分配需求.

1.2 對象分配器: 內核級別的 malloc 分配器

內核中常見的是經常分配某種固定大小尺寸的對象, 並且對象都需要一定的初始化操作, 這個初始化操作有時比分配操作還要費時, 因此, 一個解決方法是用緩存池把這些對象管理起來, 把第一次分配作初始化; 釋放時析構為這個初始狀態, 這樣能提高效率. 此外, 增加一個緩存池, 把不同大小的對象分類管理起來, 這樣能更高效地使用內存 - 試想用固定尺寸的頁分配器來分配給對象使用, 則不可避免會出現大量內部碎片. 因此, Linux 內核在頁分配器的基礎上, 實現了一個對象分配器: slab.

1.2.1 SLAB, 2.0 版本時代(1996年引入)

這是最早引入的對象分配器, SLAB 基於頁分配器分配而來的頁面(組), 實現自己的對象緩存管理. 它提供預定尺寸的對象緩存, 也支持用戶自定義對象緩存, 維護著每個 CPU , 每個 NUMA node 的緩存隊列層級, 可以提供高效的對象分配. 同時, 還支持硬體緩存對齊和著色，所謂著色, 就是把不同對象地址, 以緩存行對單元錯開, 從而使不同對象佔用不同的緩存行，從而提高緩存的利用率並獲得更好的性能。

1.2.2 SLUB, 2.6.22(2007年7月發布)

這是第二個對象分配器實現. 引入這個新的實現的原因是 SLAB 存在的一些問題. 比如 NUMA 的支持, SLAB 引入時內核還沒支持 NUMA, 因此, 一開始就沒把 NUMA 的需求放在設計理念里, 結果導致後來的對 NUMA 的支持比較臃腫奇怪, 一個典型的問題是, SLAB 為追蹤這些緩存, 在每個 CPU, 每個 node, 上都維護著對象隊列. 同時, 為了滿足 NUMA 分配的局部性, 每個 node 上還維護著所有其他 node 上的隊列, 這樣導致 SLAB 內部為維護這些隊列就得花費大量的內存空間, 並且是O(n^2) 級別的. 這在大規模的 NUMA 機器上, 浪費的內存相當可觀[13]. 同時, 還有別的一些使用上的問題, 導致開發者對其不滿, 因而引入了新的實現.

SLUB 在解決了上述的問題之上, 提供與 SLAB 完全一樣的介面, 所以用戶可以無縫切換, 而且, 還提供了更好的調試支持. 早在幾年前, 各大發行版中的對象分配器就已經切換為 SLUB了.

關於性能, 前陣子為公司的系統切換 SLUB, 做過一些性能測試, 在一台兩個 NUMA node, 32 個邏輯 CPU , 252 GB 內存的機器上, 在相同的 workload 測試下, SLUB 綜合來說，體現出了比 SLAB 更好的性能和吞吐量.

1.2.3 SLOB, 2.6.16(2006年3月發布)

這是第三個對象分配器, 提供同樣的介面, 它是為適用於嵌入式小內存小機器的環境而引入的, 所以實現上很精簡, 大大減小了內存 footprint, 能在小機器上提供很不錯的性能.

1.3 連續內存分配器(CMA), 3.5(2012年7月發布)

顧名思義,這是一個分配連續物理內存頁面的分配器. 也許你會疑惑夥伴分配器不是也能分配連續物理頁面嗎? 誠然, 但是一個系統在運行若干時間後, 可能很難再找到一片足夠大的連續內存了, 夥伴系統在這種情況下會分配失敗. 但連續物理內存的分配需求是剛需: 一些比較低端的 DMA 設備只能訪問連續的物理內存; 還有下面會講的透明大頁的支持, 也需要連續的物理內存.

一個解決辦法就是在系統啟動時,在內存還很充足的時候, 先預留一部分連續物理內存頁面, 留作後用. 但這有個代價, 這部分內存就無法被作其他使用了, 為了可能的分配需求, 預留這麼一大塊內存, 不是一個明智的方法.

CMA 的做法也是啟動時預留, 但不同的是, 它允許這部分內存被正常使用, 在有連續內存分配需求時, 把這部分內存里的頁面遷移走, 從而空出位置來作分配 .

2 內存去碎片化

前面講了運行較長時間的系統存在的內存碎片化問題, Linux 內核也不能倖免, 因此有開發者陸續提出若干種方法.

2.1 成塊回收(Lumpy Reclaim) 2.6.23引入(2007年7月), 3.5移除(2012年7月)

這不是一個完整的解決方案, 它只是緩解這一問題. 所謂回收是指 MM 在分配內存遇到內存緊張時, 會把一部分內存頁面回收. 而成塊回收[14], 就是嘗試成塊回收目標回收頁相鄰的頁面，以形成一塊滿足需求的高階連續頁塊。這種方法有其局限性，就是成塊回收時沒有考慮被連帶回收的頁面可能是「熱頁」，即被高強度使用的頁，這對系統性能是損傷。

2.2 基於頁面可移動性的頁面聚類(Page Clustering by Page Mobility) 2.6.23(2007年7月發布)

這個名字是我造的, 有點拗口. 所謂可移動性, 是基於對下列事實的思考: 在去碎片化時，需要移動或回收頁面，以騰出連續的物理頁面，但可能一顆「老鼠屎就壞了整鍋粥」——由於某個頁面無法移動或回收，導致整個區域無法組成一個足夠大的連續頁面塊。這種頁面通常是內核使用的頁面，因為內核使用的頁面的地址是直接映射(即物理地址加個偏移就映射到內核空間中)，這種做法不用經過頁表翻譯，提高了效率，卻也在此時成了攔路虎。

長年致力於解決內存碎片化的內存領域黑客 Mel Gorman 觀察到這個事實, 在經過28個版本[15]的修改後, 他的解決方案進入內核.

Mel Gorman觀察到，所有使用的內存頁有三種情形：

1.容易回收的(easily reclaimable): 這種頁面可以在系統需要時回收，比如文件緩存頁，們可以輕易的丟棄掉而不會有問題(有需要時再從後備文件系統中讀取); 又比如一些生命周期短的內核使用的頁，如DMA緩存區。
2.難回收的(non-reclaimable): 這種頁面得內核主動釋放，很難回收，內核使用的很多內存頁就歸為此類，比如為模塊分配的區域，比如一些常駐內存的重要內核結構所佔的頁面。
3. 可移動的(movable): 用戶空間分配的頁面都屬於這種類型，因為用戶態的頁地址是由頁表翻譯的，移動頁後只要修改頁表映射就可以(這也從另一面應證了內核態的頁為什麼不能移動，因為它們採取直接映射)。

因此, 他修改了夥伴分配器和分配 API, 使得在分配時告知夥伴分配器頁面的可移動性: 回收時, 把相同移動性的頁面聚類; 分配時, 根據移動性, 從相應的聚類中分配.

聚類的好處是, 結合上述的成塊回收方案, 回收頁面時，就能保證回收同一類型的; 或者在遷移頁面時(migrate page), 就能移動可移動類型的頁面，從而騰出連續的頁面塊，以滿足高階的連續物理頁面分配。

關於細節, 可看我之前寫的文章:Linux內核中避免內存碎片的方法(1)

2.3 內存緊緻化(Memory Compaction) 2.6.35(2010年8月發布)

2.2中講到頁面聚類, 它把相當可移動性的頁面聚集在一起: 可移動的在一起, 可回收的在一起, 不可移動的也在一起. 它作為去碎片化的基礎. 然後, 利用成塊回收, 在回收時, 把可回收的一起回收, 把可移動的一起移動, 從而能空出大量連續物理頁面. 這個作為去碎片化的策略.

2.6.35 里, Mel Gorman 又實現了一種新的去碎片化的策略[16], 叫內存緊緻化. 不同於成塊回收回收相臨頁面, 內存緊緻化則是更徹底, 它在回收頁面時被觸發, 它會在一個 zone 里掃描, 把已分配的頁記錄下來, 然後把所有這些頁移動到 zone 的一端, 這樣這把一個可能已經七零八落的 zone 給緊緻化成一段完全未分配的區間和一段已經分配的區間, 這樣就又騰出大塊連續的物理頁面了.

它後來替代了成塊回收, 使得後者在3.5中被移除.

3 頁表管理

3.1 四級頁表 2.6.11(2005年3月發布)

頁表實質上是一個虛擬地址到物理地址的映射表, 但由於程序的局部性, 某時刻程序的某一部分才需要被映射, 換句話說, 這個映射表是相當稀疏的, 因此在內存中維護一個一維的映射表太浪費空間, 也不現實. 因此, 硬體層次支持的頁表就是一個多層次的映射表.

Linux 一開始是在一台i386上的機器開發的, i386 的硬體頁表是2級的(頁目錄項 -&> 頁表項), 所以, 一開始 Linux 支持的軟體頁表也是2級的; 後來, 為了支持 PAE (Physical Address Extension), 擴展為3級; 後來, 64位 CPU 的引入, 3級也不夠了, 於是, 2.6.11 引入了四級的通用頁表.

關於四級頁表是如何適配 i386 的兩級頁表的, 很簡單, 就是虛設兩級頁表. 類比下, 北京市(省)北京市海淀區東升鎮, 就是為了適配4級行政區規劃而引入的一種表示法. 這種通用抽象的軟體工程做法在內核中不乏例子.

關於四級頁表演進的細節, 可看我以前文章: Linux內核4級頁表的演進

3.2 延遲頁表緩存沖刷 (Lazy-TLB flushing), 極早引入, 時間難考

有個硬體機構叫 TLB, 用來緩存頁表查尋結果, 根據程序局部性, 即將訪問的數據或代碼很可能與剛訪問過的在一個頁面, 有了 TLB 緩存, 頁表查找很多時候就大大加快了. 但是, 內核在切換進程時, 需要切換頁表, 同時 TLB 緩存也失效了, 需要衝刷掉. 內核引入的一個優化是, 當切換到內核線程時, 由於內核線程不使用用戶態空間, 因此切換用戶態的頁表是不必要, 自然也不需要衝刷 TLB. 所以引入了 Lazy-TLB 模式, 以提高效率. 關於細節, 可參考[17]

4. 頁面回收

/* 從用戶角度來看, 這一節對了解 Linux 內核發展幫助不大，可跳過不讀; 但對於技術人員來說, 本節可以展現教材理論模型到工程實現的一些思考與折衷, 還有軟體工程實踐中由簡單粗糙到複雜精細的演變過程 */

當 MM 遭遇內存分配緊張時, 會回收頁面. 頁框替換演算法(Page Frame Replacement Algorithm, 下稱PFRA) 的實現好壞對性能影響很大: 如果選中了頻繁或將馬上要用的頁, 將會出現 Swap Thrashing 現象, 即剛換出的頁又要換回來, 現象就是系統響應非常慢.

4.1 增強的LRU演算法 (2.6前引入, 具體時間難考)

教科書式的 PFRA 會提到要用 LRU (Least-Recently-Used) 演算法, 該演算法思想基於: 最近很少使用的頁, 在緊接著的未來應該也很少使用, 因此, 它可以被當作替換掉的候選頁.

但現實中, 要跟蹤每個頁的使用情況, 開銷不是一般的大, 尤其是內存大的系統. 而且, 還有一個問題, LRU 考量的是近期的歷史, 卻沒能體現頁面的使用頻率 - 假設有一個頁面會被多次訪問, 最近一次訪問稍久點了, 這時湧入了很多只會使用一次的頁(比如在播放電影), 那麼按照 LRU 語義，很可能被驅逐的是前者, 而不是後者這些不會再用的頁面.

為此, Linux 引入了兩個鏈表, 一個 active list, 一個 inactive list , 這兩個鏈表如此工作:

1. inactive list 鏈表尾的頁將作為候選頁, 在需要時被替換出系統.
2. 對於文件緩存頁, 當第一次被讀入時, 將置於 inactive list 鏈表頭。如果它被再次訪問, 就把它提升到 active list 鏈表尾; 否則, 隨著新的頁進入, 它會被慢慢推到 inactive list 尾巴; 如果它再一次訪問, 就把它提升到 active list 鏈表頭.
3. 對於匿名頁, 當第一次被讀入時, 將置於 active list 鏈表尾(對匿名頁的優待是因為替換它出去要寫入交換設備, 不能直接丟棄, 代價更大); 如果它被再次訪問, 就把它提升到 active list 鏈表頭,
4. 在需要換頁時, MM 會從 active 鏈表尾開始掃描, 把足夠量頁面降級到 inactive 鏈表頭, 同樣, 默認文件緩存頁會受到優待(用戶可通過 swappiness 這個用戶介面設置權重)。

如上, 上述兩個鏈表按照使用的熱度構成了四個層級:

active 頭(熱烈使用中) &> active 尾 &> inactive 頭 &> inactive 尾(被驅逐者)

這種增強版的 LRU 同時考慮了 LRU 的語義: 更近被使用的頁在鏈表頭;

又考慮了使用頻度: 還是考慮前面的例子, 一個頻繁訪問的頁, 它極有可能在 active 鏈表頭, 或者次一點, 在 active 鏈表尾, 此時湧入的大量一次性文件緩存頁, 只會被放在 inactive 鏈表頭, 因而它們會更優先被替換出去.

4.2 active 與 inactive 鏈表拆分, 2.6.28(2008年12月)

4.1 中描述過一個用戶可配置的介面 : swappiness. 這是一個百分比數(取值 0 -100, 默認60), 當值越靠近100, 表示更傾向替換匿名頁; 當值越靠近0, 表示更傾向替換文件緩存頁. 這在不同的工作負載下允許管理員手動配置.

4.1 中規則 4)中說在需要換頁時, MM 會從 active 鏈表尾開始掃描, 如果有一台機器的 swappiness 被設置為 0, 意為完全不替換匿名頁, 則 MM 在掃描中要跳過很多匿名頁, 如果有很多匿名頁(在一台把 swappiness 設為0的機器上很可能是這樣的), 則容易出現性能問題.

解決方法就是把鏈表拆分為匿名頁鏈表和文件緩存頁鏈表[18][19]，現在 active 鏈表分為 active 匿名頁鏈表和 active 文件緩存頁鏈表了；inactive 鏈表也如此。所以, 當 swappiness 為0時，只要掃描 active 文件緩存頁鏈表就夠了。

4.3 再拆分出被鎖頁的鏈表, 2.6.28(2008年12月)

雖然現在拆分出4個鏈表了, 但還有一個問題, 有些頁被"釘"在內存里(比如實時演算法, 或出於安全考慮, 不想含有敏感信息的內存頁被交換出去等原因，用戶通過 mlock()等系統調用把內存頁鎖住在內存里). 當這些頁很多時, 掃描這些頁同樣是徒勞的.

所以解決辦法是把這些頁獨立出來, 放一個獨立鏈表. 現在就有5個鏈表了, 不過有一個鏈表不會被掃描. [20][21]

4.4 讓代碼文件緩存頁多待一會, 2.6.31(2009年9月發布)

試想, 當你在拷貝一個非常大的文件時, 你發現突然電腦變得反應慢了, 那麼可能發生的事情是:

突然湧入的大量文件緩存頁讓內存告急, 於是 MM 開始掃描前面說的鏈表, 如果系統的設置是傾向替換文件頁的話(swappiness 靠近0), 那麼很有可能, 某個 C 庫代碼所在代碼要在這個內存吃緊的時間點(意味掃描 active list 會比較凶)被挑中, 給扔掉了, 那麼程序執行到了該代碼, 要把該頁重新換入, 這就是發生了前面說的 Swap Thrashing 現象了。這體驗自然就差了.

解決方法是在掃描這些在使用中的代碼文件緩存頁時, 跳過它, 讓它有多一點時間待在 active 鏈表上, 從而避免上述問題. [22][23]

4.5 工作集大小的探測, 3.15(2014年6月發布)

一個文件緩存頁(代碼)一開始進入 inactive 鏈表表頭, 如果它沒被再次訪問, 它將被慢慢推到 inactive 鏈表表尾, 最後在回收時被回收走; 而如果有再次訪問, 它會被提升到 active 鏈表尾, 再再次訪問, 提升到 active 鏈表頭. 因此, 可以定義一個概念: 訪問距離, 它指該頁面第一次進入內存到被踢出的間隔, 顯然至少是 inactive 鏈表的長度.

那麼問題來了: 這個 inactive 鏈表的長度得多長? 才能保護該代碼頁在第二次訪問前盡量不被踢出, 以避免 Swap Thrashing 現象.

在這之前內核僅僅簡單保證 active 鏈表不會大於 inactive 鏈表. 如果進一步思考, 這個問題跟工作集大小相關. 所謂工作集, 就是維持系統所有活動的所需內存頁面的最小量. 如果工作集小於等於 inactive 鏈表長度, 即訪問距離, 則是安全的; 如果工作集大於 inactive 鏈表長度, 即訪問距離, 則不可避免有些頁要被踢出去.

3.15 就引入了一種演算法, 它通過估算訪問距離, 來測定工作集的大小, 從而維持 inactive 鏈表在一個合適長度.[24]

5 頁面寫回

當進程改寫了文件緩存頁, 此時內存中的內容與後備存儲設備(backing device)的內容便處於不一致狀態, 此時這種頁面叫做臟頁(dirty page). 內核會把這些臟頁寫回到後備設備中. 這裡存在一個折衷: 寫得太頻繁(比如每有一個臟頁就寫一次)會影響吞吐量; 寫得太遲(比如積累了很多個臟頁才寫回)又可能帶來不一致的問題, 假設在寫之前系統崩潰, 則這些數據將丟失, 此外, 太多的臟頁會佔據太多的可用內存. 因此, 內核採取了幾種手段來寫回:

1) 設一個後台門檻(background threshold), 當系統臟頁數量超過這個數值, 用後台線程寫回, 這是非同步寫回.

2) 設一個全局門檻(global threshold), 這個數值比後台門檻高. 這是以防系統突然生成大量臟頁, 寫回跟不上, 此時系統將扼制(throttle)生成臟頁的進程, 讓其開始同步寫回.

5.1 由全局的臟頁門檻到每設備臟頁門檻 2.6.24(2008年1月發布)

內核採取的第2個手段看起來很高明 - 扼制生成臟頁的進程, 使其停止生成, 反而開始寫回臟頁, 這一進一退中, 就能把全局的臟頁數量拉低到全局門檻下. 但是, 這存在幾個微妙的問題:

1. 有可能這大量的臟頁是要寫回某個後備設備A的, 但被扼制的進程寫的臟頁則是要寫回另一個後備設備B的. 這樣, 一個不相干的設備的臟頁影響到了另一個(可能很重要的)設備, 這是不公平的.
2. 還有一個更嚴重的問題出現在棧式設備上. 所謂的棧式設備(stacked device)是指多個物理設備組成的邏輯設備, 如 LVM 或 software RAID 設備上. 操作在這些邏輯設備上的進程只能感知到這些邏輯設備. 假設某個進程生成了大量臟頁, 於是, 在邏輯設備這一層, 臟頁到達門檻了, 進程被扼制並讓其寫回臟頁, 由於進程只能感知到邏輯設備這一層, 所以它覺得臟頁已經寫下去了. 但是, 這些臟頁分配到底下的物理設備這一層時, 可能每個物理設備都還沒到達門檻, 那麼在這一層, 是不會真正往下寫臟頁的. 於是, 這種極端局面造成了死鎖: 邏輯設備這一層以為臟頁寫下去了; 而物理設備這一層還在等更多的臟頁以到達寫回的門檻.

2.6.24 引入了一個新的改進[25], 就是把全局的臟頁門檻替換為每設備的門檻. 這樣第1個問題自然就解決了. 第2個問題其實也解決了. 因為現在是每個設備一個門檻, 所以在物理設備這一層, 這個門檻是會比之前的全局門檻低很多的, 於是出現上述問題的可能性也不存在了.

那麼問題來了, 每個設備的門檻怎麼確定? 設備的寫回能力有強有弱(SSD 的寫回速度比硬碟快多了), 一個合理的做法是根據當前設備的寫回速度分配給等比例的帶寬(門檻). 這種動態根據速度調整的想法在數學上就是指數衰減[26]的理念:某個量的下降速度和它的值成比例. 所以, 在這個改進里, 作者引入了一個叫"浮動比例"的庫, 它的本質就是一個根據寫回速度進行指數衰減的級數. (這個庫跟內核具體的細節無關, 感興趣的可以研究這個代碼: [PATCH 19/23] lib: floating proportions [LWN.net]). 然後, 使用這個庫, 就可以"實時地"計算出每個設備的帶寬(門檻).

5.2 引入更具體擴展性的回寫線程 2.6.32(2009年12月發布)

Linux 內核在臟頁數量到達一定門檻時, 或者用戶在命令行輸入 sync 命令時, 會啟用後台線程來寫回臟頁, 線程的數量會根據寫回的工作量在2個到8個之間調整. 這些寫回線程是面向臟頁的, 而不是面向後備設備的. 換句話說, 每個回寫線程都是在認領系統全局範圍內的臟頁來寫回, 而這些臟頁是可能屬於不同後備設備的, 所以回寫線程不是專註於某一個設備.

不過隨著時間的推移, 這種看似靈巧的方案暴露出弊端.

1. 由於每個回寫線程都是可以服務所有後備設備的, 在有多個後備設備, 且回寫工作量大時, 線程間的衝突就變得明顯了(畢竟, 一個設備同一時間內只允許一個線程寫回), 當一個設備有線程佔據, 別的線程就得等, 或者去先寫別的設備. 這種衝突對性能是有影響的.
2. 線程寫回時, 把臟頁組成一個個寫回請求, 掛在設備的請求隊列上, 由設備去處理. 顯然,每個設備的處理請求能力是有限的, 即隊列長度是有限的. 當一個設備的隊列被線程A佔滿, 新來的線程B就得不到請求位置了. 由於線程是負責多個設備的, 線程B不能在這設備上乾等, 就先去忙別的, 以期這邊儘快有請求空位空出來. 但如果線程A寫回壓力大, 一直占著請求隊列不放, 那麼A就及飢餓了, 時間太久就會出問題.

針對這種情況, 2.6.32為每個後備設備引入了專屬的寫回線程[27], 換言之, 現在的寫回線程是面向設備的. 在寫回臟頁時, 系統會根據其所屬的後備設備, 派發給專門的線程去寫回, 從而避免上述問題.

5.3 動態的臟頁生成扼制和寫回扼制演算法 3.1(2011年11月發布), 3.2(2012年1月發布)

本節一開始說的寫回扼制演算法, 其核心就是誰污染誰治理: 生成臟頁多的進程會被懲罰, 讓其停止生產, 責成其進行義務勞動, 把系統臟頁寫回. 在5.1小節里, 已經解決了這個方案的針對於後備設備門檻的一些問題. 但還存在一些別的問題.

1. 寫回的臟頁的破碎性導致的性能問題. 破碎性這個詞是我造的, 大概的意思是, 由於被罰的線程是同步寫回臟頁到後備設備上的. 這些臟頁在後備設備上的分布可能是很散亂的, 這就會造成頻繁的磁碟磁頭移動, 對性能影響非常大. 而 Linux 存在的一個塊層(block layer, 倒數第2個子系統會講)本來就是要解決這種問題, 而現在寫回機制是相當於繞過它了.
2. 系統根據當前可用內存狀況決定一個臟頁數量門檻, 一到這個門檻值就開始扼制臟頁生成. 這種做法太粗野了點. 有時啟動一個占內存大的程序(比如一個 kvm), 臟頁門檻就會被急劇降低, 就會導致粗暴的臟頁生成扼制.
3. 從長遠看, 整個系統生成的臟頁數量應該與所有後備設備的寫回能力相一致. 在這個方針指導下, 對於那些過度生產臟頁的進程, 給它一些限制, 扼制其生成臟頁的速度. 內核於是設置了一個定點, 在這個定點之下, 內核對進程生成臟頁的速度不做限制; 但一超過定點就開始粗暴地限制.

3.1, 3.2 版本中, 來自 Intel 中國的吳峰光博士針對上述問題, 引入了動態的臟頁生成扼制和寫回扼制演算法[27][28]. 其主要核心就是, 不再讓受罰的進程同步寫回臟頁了, 而是罰它睡覺; 至於臟頁寫回, 會委派給專門的寫回線程, 這樣就能利用塊層的合併機制, 儘可能把磁碟上連續的臟頁合併再寫回, 以減少磁頭的移動時間.

至於標題中的"動態"的概念, 主要有下:

1. 決定受罰者睡多久. 他的演算法中, 動態地去估算後備設備的寫回速度, 再結合當前要寫的臟頁量, 從而動態地去決定被罰者要睡的時間.
2. 平緩地修改扼制的門檻. 之前進程被罰的門檻會隨著一個重量級進程的啟動而走人驟降, 在吳峰光的演算法中, 增加了對全局內存壓力的評估, 從而平滑地修改這一門檻.
3. 在進程生成臟頁的扼制方面, 吳峰光同樣採取反饋調節的做法, 針對寫回工作量和寫回速度, 平緩地(盡量)把系統的臟頁生成控制在定點附近.

6 頁面預讀

系統在讀取文件頁時, 如果發現存在著順序讀取的模式時, 就會預先把後面的頁也讀進內存, 以期之後的訪問可以快速地訪問到這些頁, 而不用再啟動快速的磁碟讀寫.

6.1 原始的預讀方案 (時間很早, 未可考)

一開始, 內核的預讀方案如你所想, 很簡單. 就是在內核發覺可能在做順序讀操作時, 就把後面的 128 KB 的頁面也讀進來.

6.2 按需預讀(On-demand Readahead) 2.6.23(2007年10月發布)

這種固定的128 KB預讀方案顯然不是最優的. 它沒有考慮系統內存使用狀況和進程讀取情況. 當內存緊張時, 過度的預讀其實是浪費, 預讀的頁面可能還沒被訪問就被踢出去了. 還有, 進程如果訪問得兇猛的話, 且內存也足夠寬裕的話, 128KB又顯得太小家子氣了.

2.6.23的內核引入了在這個領域耕耘許久的吳峰光的一個按需預讀的演算法[29]. 所謂的按需預讀, 就是內核在讀取某頁不在內存時, 同步把頁從外設讀入內存, 並且, 如果發現是順序讀取的話, 還會把後續若干頁一起讀進來, 這些預讀的頁叫預讀窗口; 當內核讀到預讀窗口裡的某一頁時, 如果發現還是順序讀取的模式, 會再次啟動預讀, 非同步地讀入下一個預讀窗口.

該演算法關鍵就在於適當地決定這個預讀窗口的大小,和哪一頁做為非同步預讀的開始. 它的啟發式邏輯也非常簡單, 但取得不了錯的效果. 此外, 對於兩個進程在同一個文件上的交替預讀, 2.6.24 增強了該演算法, 使其能很好地偵測這一行為.

7 大內存頁支持

我們知道現代操作系統都是以頁面(page)的方式管理內存的. 一開始, 頁面的大小就是4K, 在那個時代, 這是一個相當大的數目了. 所以眾多操作系統, 包括 Linux , 深深植根其中的就是一個頁面是4K大小這種認知, 儘管現代的CPU已經支持更大尺寸的頁面(X86體系能支持2MB, 1GB).

我們知道虛擬地址的翻譯要經過頁表的翻譯, CPU為了支持快速的翻譯操作, 引入了TLB的概念, 它本質就是一個頁表翻譯地址結果的緩存, 每次頁表翻譯後的結果會緩存其中, 下一次翻譯時會優先查看TLB, 如果存在, 則稱為TLB hit; 否則稱為TLB miss, 就要從訪問內存, 從頁表中翻譯. 由於這是一個CPU內機構, 決定了它的尺寸是有限的, 好在由於程序的局部性原理, TLB 中緩存的結果很大可能又會在近期使用.

但是, 過去幾十年, 物理內存的大小翻了幾番, 但 TLB 空間依然局限, 4KB大小的頁面就顯得捉襟見肘了. 當運行內存需求量大的程序時, 這樣就存在更大的機率出現 TLB miss, 從而需要訪問內存進入頁表翻譯. 此外, 訪問更多的內存, 意味著更多的缺頁中斷. 這兩方面, 都對程序性能有著顯著的影響.

7.1 HUGETLB支持 (2.6前引入)

如果能使用更大的頁面, 則能很好地解決上述問題. 試想如果使用2MB的頁(一個頁相當於512個連續的4KB 頁面), 則所需的 TLB 表項由原來的 512個變成1個, 這將大大提高 TLB hit 的機率; 缺頁中斷也由原來的512次變為1次, 這對性能的提升是不言而喻的.

然而, 前面也說了 Linux 對4KB大小的頁面認知是根植其中的, 想要支持更大的頁面, 需要對非常多的核心的代碼進行大改動, 這是不現實的. 於是, 為了支持大頁面, 有了一個所謂 HUGETLB 的實現.

它的實現是在系統啟動時, 按照用戶指定需求的最大大頁個數, 每個頁的大小. 預留如此多個數的大. . 用戶在程序中可以使用 mmap() 系統調用或共享內存的方式訪問這些大頁, 例子網上很多, 或者參考官方文檔:hugetlbpage.txt [LWN.net] . 當然, 現在也存在一些用戶態工具, 可以幫助用戶更便捷地使用. 具體可參考此文章: Huge pages part 2: Interfaces [LWN.net]

這一功能的主要使用者是資料庫程序.

7.2 透明大頁的支持 2.6.38(2011年3月發布)

7.1 介紹的這種使用大頁的方式看起來是挺怪異的, 需要用戶程序做出很多修改. 而且, 內部實現中, 也需要系統預留一大部分內存. 基於此, 2.6.38 引入了一種叫透明大頁的實現[30]. 如其名字所示, 這種大頁的支持對用戶程序來說是透明的.

它的實現原理如下. 在缺頁中斷中, 內核會嘗試分配一個大頁, 如果失敗(比如找不到這麼大一片連續物理頁面), 就還是回退到之前的做法: 分配一個小頁. 在系統內存緊張需要交換出頁面時, 由於前面所說的根植內核的4KB頁面大小的因, MM 會透明地把大頁分割成小頁再交換出去.

用戶態程序現在可以完成無修改就使用大頁支持了. 用戶還可以通過 madvice() 系統調用給予內核指示, 優化內核對大頁的使用. 比如, 指示內核告知其你希望進程空間的某部分要使用大頁支持, 內核會儘可能地滿足你.

8 內存控制組(Memory Cgroup)支持 2.6.25(2008年4月發布)

在Linux輕量級虛擬化的實現 container 中(比如現在挺火的Docker, 就是基於container), 一個重要的功能就是做資源隔離. Linux 在 2.6.24中引入了cgroup(control group, 控制組)的資源隔離基礎框架(將在最後一個部分詳述), 提供了資源隔離的基礎.

在2.6.25 中, 內核在此基礎上支持了內存資源隔離, 叫內存控制組. 它使用可以在不同的控制組中, 實施內存資源控制, 如分配, 內存用量, 交換等方面的控制.

9 內存熱插拔支持

內存熱插拔, 也許對於第一次聽說的人來說, 覺得不可思議: 一個系統的核心組件, 為何要支持熱插拔? 用處有以下幾點.

1. 大規模集群中, 動態的物理容量增減, 可以實現更好地支持資源集約和均衡.
2. 大規模集群中, 物理內存出錯的機會大大增多, 內存熱插拔技術對提高高可用性至關重要.
3. 在虛擬化環境中, 客戶機(Guest OS)間的高效內存使用也對熱插拔技術提出要求

當然, 作為一個核心組件, 內存的熱插拔對從系統固件,到軟體(操作系統)的要求, 跟普通的外設熱插拔的要求, 不可同日而語. 這也是為什麼 Linux 內核對內存熱插拔的完全支持一直到近兩年才基本完成.

總的來說, 內存熱插拔分為兩個階段, 即物理熱插拔階段和邏輯熱插拔階段:

物理熱插拔階段: 這一階段是內存條插入/拔出主板的過程. 這一過程必須要涉及到固件的支持(如 ACPI 的支持), 以及內核的相關支持, 如為新插入的內存分配管理元數據進行管理. 我們可以把這一階段分別稱為 hot-add / hot-remove.
邏輯熱插拔階段: 這一階段是從使用者視角, 啟用/關閉這部分內存. 這部分的主要從內存分配器方面做的一些準備工作. 我們可以把這一階段分別稱為 online / offline.

邏輯上來講, 內存插和拔是一個互為逆操作, 內核應該做的事是對稱的, 但是, 拔的過程需要關注的技術難點卻比插的過程多, 因為, 從無到有容易, 從有到無麻煩:在使用的內存頁應該被妥善安置, 就如同安置拆遷戶一樣, 這是一件棘手的事情. 所以內核對 hot-remove 的完全支持一直推遲到 2013 年.[31]

9.1 內存熱插入支持 2.6.15(2006年1月發布)

這提供了最基本的內存熱插入支持(包括物理/邏輯階段). 注意, 此時熱拔除還不支持.

9.2 初步的內存邏輯熱拔除支持 2.6.24(2008年1月發布)

此版本提供了部分的邏輯熱拔除階段的支持, 即 offline. Offline 時, 內核會把相關的部分內存隔離開來, 使得該部分內存不可被其他任何人使用, 然後再把此部分內存頁, 用前面章節說過的內存頁遷移功能轉移到別的內存上. 之所以說部分支持, 是因為該工作只提供了一個 offline 的功能. 但是, 不是所有的內存頁都可以遷移的. 考慮"遷移"二字的含義, 這意味著物理內存地址會變化, 而內存熱拔除應該是對使用者透明的, 這意味著, 用戶見到的虛擬內存地址不能變化, 所以這中間必須存在一種機制, 可以修改這種因遷移而引起的映射變化. 所有通過頁表訪問的內存頁就沒問題了, 只要修改頁表映射即可; 但是, 內核自己用的內存, 由於是繞過尋常的逐級頁表機制, 採用直接映射(提高了效率), 內核內存頁的虛擬地址會隨著物理內存地址變動, 因此, 這部分內存頁是無法輕易遷移的. 所以說, 此版本的邏輯熱拔除功能只是部分完成.

注意, 此版本中, 物理熱拔除是還完全未實現. 一句話, 此版本的熱拔除功能還不能用.

9.3 完善的內存邏輯熱拔除支持 3.8(2013年2月發布)

針對9.2中的問題, 此版本引入了一個解決方案. 9.2 中的核心問題在於不可遷移的頁會導致內存無法被拔除. 解決問題的思路是使可能被熱拔除的內存不包含這種不可遷移的頁. 這種信息應該在內存初始化/內存插入時被傳達, 所以, 此版本中, 引入一個 movable_node 的概念. 在此概念中, 一個被 movable_node 節點的所有內存, 在初始化/插入後, 內核確保它們之上不會被分配有不可遷移的頁, 所以當熱拔除需求到來時, 上面的內存頁都可以被遷移, 從而使內存可以被拔除.

9.4 物理熱拔除的支持 3.9(2013年4月支持)

此版本支持了物理熱拔除, 這包括對內存管理元數據的刪除, 跟固件(如ACPI) 相關功能的實現等比較底層瑣碎的細節, 不詳談.

在完成這一步之後, 內核已經可以提供基本的內存熱插拔支持. 值得一提的是, 內存熱插拔的工作, Fujitsu 中國這邊的內核開放者貢獻了很多 patch. 謝謝他們!

10 超然內存(Transcendent Memory)支持

超然內存(Transcendent Memory), 對很多第一次聽見這個概念的人來說, 是如此的奇怪和陌生. 這個概念是在 Linux 內核開發者社區中首次被提出的[32]. 超然內存(後文一律簡稱為tmem)之於普通內存, 不同之處在於以下幾點:

1 tmem 的大小對內核來說是未知的, 它甚至是可變的; 與之相比, 普通內存在系統初始化就可被內核探測並枚舉, 並且大小是固定的(不考慮熱插拔情形).
2 tmem 可以是穩定的, 也可以是不穩定的, 對於後者, 這意味著, 放入其中的數據, 在之後的訪問中可能發現不見了; 與之相比, 普通內存在系統加電狀態下一直是穩定的, 你不用擔心寫入的數據之後訪問不到(不考慮內存硬體故障問題).
3 基於以上兩個原因, tmem 無法被內核直接訪問, 必須通過定義良好的 API 來訪問 tmem 中的內存; 與之相比, 普通內存可以通過內存地址被內核直接訪問.

初看之下, tmem 這三點奇異的特性, 似乎增加了不必要的複雜性, 尤其是第二條, 更是詭異無用處.

計算機界有句名言: 計算機科學領域的任何問題都可以通過增加一個間接的中間層來解決. tmem 增加的這些間接特性正是為了解決某些問題.

考慮虛擬化環境下, 虛擬機管理器(hypervisor) 需要管理維護各個虛擬客戶機(Guest OS)的內存使用. 在常見的使用環境中, 我們新建一台虛擬機時, 總要事先配置其可用的內存大小. 然而這並不十分明智, 我們很難事先確切知道每台虛擬機的內存需求情況, 這難免造成有些虛擬機內存富餘, 而有些則捉襟見肘. 如果能平衡這些資源就好了. 事實上, 存在這樣的技術, hypervisor 維護一個內存池子, 其中存放的就是這些所謂的 tmem, 它能動態地平衡各個虛擬機的盈餘內存, 更高效地使用. 這是 tmem 概念提出的最初來由.

再考慮另一種情形, 當一台機器內存使用緊張時, 它會把一些精心選擇的內存頁面寫到交換外設中以騰出空間. 然而外設與內存存在著顯著的讀寫速度差異, 這對性能是一個不利的影響. 如果在一個超高速網路相連的集群中, 網路訪問速度比外設訪問速度快, 可不可以有別的想法? tmem 又可以扮演一個重要的中間角色, 它可以把集群中所有節點的內存管理在一個池子里, 從而動態平衡各節點的內存使用, 當某一節點內存緊張時, 寫到交換設備頁其實是被寫到另一節點的內存里...

還有一種情形, 旨在提高內存使用效率.. 比如大量內容相同的頁面(全0頁面)在池子里可以只保留一份; 或者, tmem 可以考慮對這些頁面進行壓縮, 從而增加有效內存的使用.

Linux 內核從 3.X 系列開始陸續加入 tmem 相關的基礎設施支持, 並逐步加入了關於內存壓縮的功能. 進一步討論內核中的實現前, 需要對這一問題再進一步細化, 以方便討論細節.

前文說了內核需要通過 API 訪問 tmem, 那麼進一步, 可以細化為兩個問題.

1. 內核的哪些部分內存可以被 tmem 管理呢? 有兩大類, 即前面提到過的文件緩存頁和匿名頁.
2. tmem 如何管理其池子中的內存. 針對前述三種情形, 有不同的策略. Linux 現在的主要解決方案是針對內存壓縮, 提高內存使用效率.

針對這兩個問題, 可以把內核對於 tmem 的支持分別分為前端和後端. 前端是內核與 tmem 通訊的介面; 而後端則實現 tmem 的管理策略.

10.1 前端介面之 CLEANCACHE 3.0(2011年7月發布)

前面章節提到過, 內核會利用空閑內存緩存後備外設中的內容, 以期在近期將要使用時不用從緩慢的外設讀取. 這些內容叫文件緩存頁. 它的特點就是只要是頁是乾淨的(沒有被寫過), 那麼在系統需要內存時, 隨時可以直接丟棄這些頁面以騰出空間(因為它隨時可以從後備文件系統中讀取).

然而, 下次內核需要這些文件緩存頁時, 又得從外設讀取. 這時, tmem 可以起作用了. 內核丟棄時,假如這些頁面被 tmem 接收並管理起來, 等內核需要的時候, tmem 把它歸還, 這樣就省去了讀寫磁碟的操作, 提高了性能. 3.0 引入的 CLEANCACHE, 作為 tmem 前端介面, hook 進了內核丟棄這些乾淨文件頁的地方, 把這些頁面截獲了, 放進 tmem 後端管理(後方講). 從內核角度看, 這個 CLEANCACHE 就像一個魔盒的入口, 它丟棄的頁面被吸入這個魔盒, 在它需要時, 內核嘗試從這個魔盒中找, 如果找得到, 搞定; 否則, 它再去外設讀取. 至於為何被吸入魔盒的頁面為什麼會找不到, 這跟前文說過的 tmem 的特性有關. 後文講 tmem 後端時再說.

10.2 前端介面之 FRONTSWAP 3.5(2012年7月發布)

除了文件緩存頁, 另一大類內存頁面就是匿名頁. 在系統內存緊張時, 內核必須要把這些頁面寫出到外設的交換設備或交換分區中, 而不能簡單丟棄(因為這些頁面沒有後備文件系統). 同樣, 涉及到讀寫外設, 又有性能考量了, 此時又是 tmem 起作用的時候了.

同樣, FRONTSWAP 這個前端介面, 正如其名字一樣, 在內核 swap 路徑的前面, 截獲了這些頁面, 放入 tmem 後端管理. 如果後端還有空閑資源的話, 這些頁面被接收, 在內核需要這些頁面時, 再把它們吐出來; 如果後端沒有空閑資源了, 那麼內核還是會把這些頁面按原來的走 swap 路徑寫到交換設備中.

10.3 後端之 ZCACHE (沒能進入內核主線)

講完了兩個前端介面, 接下來說後端的管理策略. 對應於 CLEANCACHE, 一開始是有一個專門的後端叫 zcache[34], 不過最後被刪除了. 它的做法就是把這些被內核逐出的文件緩存頁壓縮, 並存放在內存中. 所以, zcache 相當於把內存頁從內存中的一個地方移到另一個地方, 這乍一看, 感覺很奇怪, 但這正是 tmem 的靈活性所在. 它允許後端有不同的管理策略, 比如在這個情況下, 它把內存頁壓縮後仍然放在內存中, 這提高了內存的使用. 當然, 畢竟 zcache 會佔用一部分物理內存, 導致可用的內存減小. 因此, 這需要有一個權衡. 高效(壓縮比, 壓縮時間)的壓縮演算法的使用, 從而使更多的文件頁待在內存中, 使得其帶來的避免磁碟讀寫的優勢大於減少的這部分內存的代價. 不過, 也因為如此, 它的實現過於複雜, 以至最終沒能進入內核主線. 開發者在開始重新實現一個新的替代品, 不過截止至 4.2 , 還沒有看到成果.

10.4後端之 ZRAM 3.14(2014年3月發布)

FRONTSWAP 對應的一個後端叫 ZRAM. 值得一提的是, 雖然這個後端實現在 3.14 才進入內核主線, 但其實它早在 2.6.33(2010年2月發布)時就已經進入內核的 staging 分支了, 經過4年的開發優化, 終於成功進入主線. Staging 分支[33] 是在內核源碼中的一個子目錄, 它是一個獨立的分支, 主要維護著獨立的 driver 或文件系統, 這些代碼未來可能也可能不進入主線.

ZRAM 是一個在內存中的塊設備(塊設備相對於字元設備而言, 信息存放於固定大小的塊中, 支持隨機訪問, 磁碟就是典型的塊設備, 更多將在塊層子系統中講), 因此, 內核可以復用已有的 swap 設備設施, 把這個塊設備格式化為 swap 設備. 因此, 被交換出去的頁面, 將通過 FRONTSWAP 前端進入到 ZRAM 這個偽 swap 設備中, 並被壓縮存放! 當然, 這個ZRAM 空間有限, 因此, 頁面可能不被 ZRAM 接受. 如果這種情形發生, 內核就回退到用真正的磁碟交換設備.

10.5 後端之 ZSWAP 3.11(2013年9月發布)

FRONTSWAP 對應的另一個後端叫 ZSWAP[35]. ZSWAP 的做法其實也是嘗試把內核交換出去的頁面壓縮存放到一個內存池子中. 當然, ZSWAP 空間也是有限的. 但同 ZRAM 不同的是, ZSWAP 會智能地把其中一些它認為近期不會使用的頁面解壓縮, 寫回到真正的磁碟外設中. 因此, 大部分情況下, 它能避免磁碟寫操作, 這比 ZRAM 不知高明到哪去了.

10.6 一些細節

這一章基本說完了, 但牽涉到後端, 其實還有一些細節可以談, 比如對於壓縮的效率的考量, 會影響到後端實現的選擇, 比如不同的內存頁面的壓縮效果不同(全0頁和某種壓縮文件佔據的內存頁的壓縮效果顯然差距很大)對壓縮演算法的選擇; 壓縮後頁面的存放策略也很重要, 因為以上後端都存在特殊情況要把頁面解壓縮寫回到磁碟外設, 寫回頁面的選擇與頁面的存放策略關係很大. 但從用戶角度講, 以上內容足以, 就不多寫了.

關於 tmem, lwn 上的兩篇文章值得關注技術細節的人一讀:

Transcendent memory in a nutshell [LWN.net]

In-kernel memory compression [LWN.net]

11 非易失性內存 (NVDIMM, Non-Volatile DIMM) 支持

計算機的存儲層級是一個金字塔體系, 從塔尖到塔基, 訪問速度遞減, 而存儲容量遞增. 從訪問速度考量, 內存(DRAM)與磁碟(HHD)之間, 存在著顯著的差異(可達到10^5級別[38]). 因此, 基於內存的緩存技術一直都是系統軟體或資料庫軟體的重中之重. 即使近些年出現的新興的最快的基於PCIe匯流排的SSD, 這中間依然存在著鴻溝.

另一方面, 非可易失性內存也並不是新鮮產物. 然而實質要麼是一塊DRAM, 後端加上一塊 NAND FLASH 快閃記憶體, 以及一個超級電容, 以在系統斷電時的提供保護; 要麼就是一塊簡單的 NAND FLASH, 提供類似 SSD 一樣的存儲特性. 所有這些, 從訪問速度上看, 都談不上真正的內存, 並且, NAND FLASH 的物理特性, 使其免不了磨損(wear out); 並且在長時間使用後, 存在寫性能下降的問題.

2015年算得上快閃記憶體技術革命年. 3D NAND FLASH 技術的創新, 以及 Intel 在醞釀的完全不同於NAND 快閃記憶體技術的 3D XPoint 內存, 都將預示著填充上圖這個性能鴻溝的時刻的臨近. 它們不僅能提供更在的容量(TB級別), 更快的訪問速度(3D XPoint 按 Intel 說法能提供 ~1000倍快於傳統的 NAND FLASH, 5 - 8倍慢於 DRAM 的訪問速度), 更持久的壽命.

相應的, Linux 內核也在進行相應的功能支持.

11.1 NVDIMM 支持框架: libnvdimm 4.2(2015年8月30日發布)

2015年4月發布的ACPI 6.0規範[39], 定義了NVDIMM Firmware Interface Table (NFIT), 詳細地規定了 NVDIMM 的訪問模式, 介面數據規範等細節. 在 Linux 4.2 中, 內核開始支持一個叫 libnvdimm 的子系統, 它實現了 NFIT 的語義, 提供了對 NVDIMM 兩種基本訪問模式的支持, 一種即內核所稱之的 PMEM 模式, 即把 NVDIMM 設備當作持久性的內存來訪問; 另一種則提供了塊設備模式的訪問. 開始奠定 Linux 內核對這一新興技術的支持.

11.2 DAX 4.0(2015年4月發布)

與這一技術相關的還有另外一個特性值得一提, 那就是 DAX(Direct Access, 直接訪問, X 無實義, 只是為了酷).

傳統的基於磁碟的文件系統, 在被訪問時, 內核總會把頁面通過前面所提的文件緩存頁(page cache)的緩存機制, 把文件系統頁從磁碟中預先載入到內存中, 以提速訪問. 然後, 對於新興的 NVDIMM 設備, 基於它的非易失特性, 內核應該能直接訪問基於此設備之上的文件系統的內容, 它使得這一拷貝到內存的操作變得不必要. 4.0 開始引入的 DAX 就是提供這一支持. 截至 4.3, 內核中已經有 XFS, EXT2, EXT4 這幾個文件系統實現這一特性.

12 內存管理調試支持

由前面所述, 內存管理相當複雜, 代碼量巨大, 而它又是如此重要的一個的子系統, 所以代碼質量也要求非常高. 另一方面, 系統各個組件都是內存管理子系統的使用者, 而如果缺乏合理有效的約束, 不正當的內存使用(如內存泄露, 內存覆寫)都將引起系統的崩潰, 以至於數據損壞. 基於此, 內存管理子系統引入了一些調試支持工具, 方便開發者/用戶追蹤,調試內存管理及內存使用中的問題. 本章介紹內存管理子系統中幾個重要的調試工具.

12.1 頁分配的調試支持 2.5(2003年7月之後發布)

前面提到過, 內核自己用的內存, 由於是繞過尋常的逐級頁表機制, 採用直接映射(提高了效率), 即虛擬地址與頁面實際的物理地址存在著一一線性映射的關係. 另一方面, 內核使用的內存又是出於各種重要管理目的, 比如驅動, 模塊, 文件系統, 甚至 SLAB 子系統也是構建於頁分配器之上. 以上二個事實意味著, 相鄰的頁, 可能被用於完全不同的目的, 而這兩個頁由於是直接映射, 它們的虛擬地址也是連續的. 如果某個使用者子系統的編碼有 bug, 那麼它的對其內存頁的寫操作造成對相鄰頁的覆寫可能性相當大, 又或者不小心讀了一個相鄰頁的數據. 這些操作可能不一定馬上引起問題, 而是在之後的某個地方才觸發, 導致數據損壞乃至系統崩潰.

為此, 2.5中, 針對 Intel 的 i386 平台, 內核引入了一個 CONFIG_DEBUG_PAGEALLOC 開關, 它在頁分配的路徑上插入鉤子, 並利用 i386 CPU 可以對頁屬性進行修改的特性, 通過修改未分配的頁的頁表項的屬性, 把該頁置為"隱藏". 因此, 一旦不小心訪問該頁(讀或寫), 都將引起處理器的缺頁異常, 內核將進入缺頁處理過程, 因而有了一個可以檢查捕捉這種內存破壞問題的機會.

在2.6.30中, 又增加了對無法作處理器級別的頁屬性修改的體系的支持. 對於這種體系, 該特性是將未分配的頁毒化(POISON), 寫入特定模式的值, 因而一旦被無意地訪問(讀或寫), 都將可能在之後的某個時間點被發現. 注意, 這種通用的方法就無法像前面的有處理器級別支持的方法有立刻捕捉的機會.

當然, 這個特性是有性能代價的, 所以生產系統中可別用哦.

12.2 SLAB 子系統的調試支持

SLAB 作為一個相對獨立的子模塊, 一直有自己完善的調試支持, 包括有:

- 對已分配對象寫的邊界超出的檢查

- 對未初始化對象寫的檢查

- 對內存泄漏或多次釋放的檢查

- 對上一次分配者進行記錄的支持等

12.3 錯誤注入機制 2.6.20(2007年2月發布)

內核有著極強的健壯性, 能對各種錯誤異常情況進行合理的處理. 然而, 畢竟有些錯誤實在是極小可能發生, 測試對這種小概率異常情況的處理的代碼實在是不方便. 所以, 2.6.20中內核引入了錯誤注入機制, 其中跟 MM 相關的有兩個, 一個是對頁分配器的失敗注入, 一個是對 SLAB 對象分配器的失敗注入. 這兩個注入機制, 可以觸發內存分配失敗, 以測試極端情況下(如內存不足)系統的處理情況.

12.4 KMEMCHECK - 內存非法訪問檢測工具 2.6.31(2009年9月發布)

對內存的非法訪問, 如訪問未分配的內存, 或訪問分配了但未初始化的內存, 或訪問了已釋放了的內存, 會引起很多讓人頭痛的問題, 比如程序因數據損壞而在某個地方莫名崩潰, 排查非常困難. 在用戶態內存檢測工具 valgrind 中, 有一個 Memcheck 插件可以檢測此類問題. 2.6.31, Linux 內核也引進了內核態的對應工具, 叫 KMEMCHECK.

它是一個內核態工具, 檢測的是內核態的內存訪問. 主要針對以下問題:

1. 對已分配的但未初始化的頁面的訪問
2. 對 SLAB 系統中未分配的對象的訪問
3. 對 SLAB 系統中已釋放的對象的訪問

為了實現該功能, 內核引入一個叫影子頁(shadow page)的概念, 與被檢測的正常數據頁一一相對. 這也意味著啟用該功能, 不僅有速度開銷, 還有很大的內存開銷.

在分配要被追蹤的數據頁的同時, 內核還會分配等量的影子頁, 並通過數據頁的管理數據結構中的一個 shadow 欄位指向該影子頁. 分配後, 數據頁的頁表中的 present 標記會被清除, 並且標記為被 KMEMCHECK 跟蹤. 在第一次訪問時, 由於 present 標記被清除, 將觸發缺頁異常. 在缺頁異常處理程序中, 內核將會檢查此次訪問是不是正常. 如果發生上述的非法訪問, 內核將會記錄下該地址, 錯誤類型, 寄存器, 和棧的回溯, 並根據配置的值大小, 把該地址附近的數據頁和影子頁的對應內容, 一併保存到一個緩衝區中. 並設定一個稍後處理的軟中斷任務, 把這些內容報告給上層. 所有這些之後, 將 CPU 標誌寄存器 TF (Trap Flag)置位, 於是在缺頁異常後, CPU 又能重新訪問這條指令, 走正常的執行流程.

這裡面有個問題是, present 標記在第一次缺頁異常後將被置位, 之後如果再次訪問, KMEMCHECK 如何再次利用該機制來檢測呢? 答案是內核在上述處理後還打開了單步調試功能, 所以 CPU 接著執行下一條指令前, 又陷入了調試陷阱(debug trap, 詳情請查看 CPU 文檔), 在處理程序中, 內核又會把該頁的 present 標記會清除.

12.4 KMEMLEAK - 內存泄漏檢測工具 2.6.31(2009年9月發布)

內存漏洞一直是 C 語言用戶面臨的一個問題, 內核開發也不例外. 2.6.31 中, 內核引入了 KMEMLEAK 工具[41], 用以檢測內存泄漏. 它採用了標記-清除的垃圾收集演算法, 對通過 SLAB 子系統分配的對象, 或通過 vmalloc 介面分配的連續虛擬地址的對象, 或分配的per-CPU對象(per-CPU對象是指每個 CPU 有一份拷貝的全局對象, 每個 CPU 訪問修改本地拷貝, 以提高性能)進行追蹤, 把指向對象起始的指針, 對象大小, 分配時的棧蹤跡(stack trace) 保存在一個紅黑樹里(便於之後的查找, 同時還會把對象加入一個全局鏈表中). 之後, KMEMLEAK 會啟動一個每10分鐘運行一次的內核線程, 或在用戶的指令下, 對整個內存進行掃描. 如果某個對象從其起始地址到終末地址內沒有別的指針指向它, 那麼該對象就被當成是泄漏了. KMEMLEAK 會把相關信息報告給用戶.

掃描的大致演算法如下:

1. 首先會把全局鏈表中的對象加入一個所謂的白名單中, 這是所有待查對象. 然後 , 依次掃描數據區(data段, bss段), per-CPU區, 還有針對每個 NUMA 節點的所有頁. 另外, 如果用戶有指定, 還會描掃所有線程的棧區(之所以這個不是強制掃描, 是因為棧區是函數的活動記錄, 變動迅速, 引用可能稍縱即逝). 掃描過程中, 與之前存的紅黑樹中的對象進行比對, 一旦發現有指針指向紅黑樹中的對象, 說明該對象仍有人引用 , 沒被泄漏, 把它加入一個所謂的灰名單中.
2. 然後, 再掃描一遍灰名單, 即已經被確認有引用的對象, 找出這些對象可能引用的別的所有對象, 也加入灰名單中.
3. 最後剩下的, 在白名單中的, 就是被 KMEMLEAK 認為是泄漏了的對象.

由於內存的引用情況各異, 存在很多特殊情況, 可能存在誤報或漏報的情況, 所以 KMEMLEAK 還提供了一些介面, 方便使用者告知 KMEMLEAK 某些對象不是泄露, 某些對象不用檢查,等等.

這個工具當然也存在著顯著的影響系統性能的問題, 所以也只是作為調試使用.

12.5 KASan - 內核地址凈化器 4.0(2015年4月發布)

4.0引入的這個工具[42]可以看作是 KMEMCHECK 工具的替代器, 它的目的也是為了檢測諸如釋放後訪問(use-after-free), 訪問越界(out-of-bouds)等非法訪問問題. 它比後者更快, 因為它利用了編譯器的 Instrument 功能, 也即編譯器會在訪問內存前插入探針, 執行用戶指定的操作, 這通常用在性能剖析中. 在內存的使用上, KASan 也比 KMEMCHECK 有優勢: 相比後者1:1的內存使用 , 它只要1:1/8.

總的來說, 它利用了 GCC 5.0的新特性, 可對內核內存進行 Instrumentaion, 編譯器可以在訪問內存前插入指令, 從而檢測該次訪問是否合法. 對比前述的 KMEMCHECK 要用到 CPU 的陷阱指令處理和單步調試功能, KASan 是在編譯時加入了探針, 因此它的性能更快.

13 雜項

這是最後一章, 講幾個 Linux 內存管理方面的屬於錦上添花性質的功能, 它們使 Linux 成為一個更強大, 更好用的操作系統.

13.1 KSM - 內存去重 2.6.32(2009年12月發布)

現代操作系統已經使用了不少共享內存的技術, 比如共享庫, 創建新進程時子進程共享父進程地址空間. 而 KSM(Kernel SamePage Merging, 內存同頁合併, 又稱內存去重), 可以看作是存儲領域去重(de-duplication)技術在內存使用上的延伸, 它是為了解決伺服器虛擬化領域的內存去重方案. 想像在一個數據中心, 一台物理伺服器上可能同時跑著多個虛擬客戶機(Guest OS), 並且這些虛擬機運行著很多相同的程序, 如果在物理內存上, 這些程序文本(text)只有一份拷貝, 將會節省相當可觀的內存. 而客戶機間是相對獨立的, 缺乏相互的認知, 所以 KSM 運作在監管機(hypervisor)上.

原理上簡單地說, KSM 依賴一個內核線程, 定期地或可手動啟動地, 掃描物理頁面(通常穩定不修改的頁面是合併的候選者, 比如包含執行程序的頁面. 用戶也可通過一個系統調用給予指導, 告知 KSM 進程的某部份區間適合合併, 見[43]]), 尋找相同的頁面併合並, 多餘的頁面即可釋放回系統另為它用. 而剩下的唯一的頁面, 會被標為只讀, 當有進程要寫該頁面, 該會為其分配新的頁面.

值得一提的是, 在匹配相同頁面時, 一種常規的演算法是對頁面進行哈希, 放入哈希列表, 用哈希值來進行匹配. 最開始 KSM 確定是用這種方法, 不過 VMWare 公司擁有跟該做法很相近的演算法專利, 所以後來採用了另一種演算法, 用紅黑樹代替哈希表, 把頁面內容當成一個字元串來做內容比對, 以代替哈希比對. 由於在紅黑樹中也是以該"字元串值"大小作為鍵, 因此查找兩個匹配的頁面速度並不慢, 因為大部分比較只要比較開始若干位即可. 關於演算法細節, 感興趣者可以參考這兩篇文章:[43], [44].

13.2 HWPoison - 內存頁錯誤的處理 2.6.32(2009年12月發布)

[一開始想把這節放在第12章"內存管理調試支持"中, 不過後來覺得這並非用於主動調試的功能, 所以還是放在此章. ]

隨著內存顆粒密度的增大和內存大小的增加, 內存出錯的概率也隨之增大. 尤其是數據中心或雲服務商, 系統內存大(幾百 GB 甚至上 TB 級別), 又要提供高可靠的服務(RAS), 不能隨隨便便宕機; 然而, 內存出錯時, 特別是出現多於 ECC(Error Correcting Codes) 內存條所支持的可修復 bit 位數的錯誤時, 此時硬體也愛莫能助, 將會觸發一個 MCE(Machine Check Error) 異常, 而通常操作系統對於這種情況的做法就是 panic (操作系統選擇 go die). 但是, 這種粗暴的做法顯然是 over kill, 比如出錯的頁面是一個文件緩存頁(page cache), 那麼操作系統完全可以把它廢棄掉(隨後它可以從後備文件系統重新把該頁內容讀出), 把該頁隔離開來不用即是.

這種需求在 Intel 的 Xeon 處理器中得到實現. Intel Xeon 處理器引入了一個所謂 MCA(Machine Check Abort)架構, 它支持包括內存出錯的的毒化(Poisoning)在內的硬體錯誤恢復機制. 當硬體檢測到一個無法修復的內存錯誤時,會把該數據標誌為損壞(poisoned); 當之後該數據被讀或消費時, 將會觸發機器檢查(Machine Check), 不同的時, 不再是簡單地產生 MCE 異常, 而是調用操作系統定義的處理程序, 針對不同的情況進行細緻的處理.

2.6.32 引入的 HWPoison 的 patch, 就是這個操作系統定義的處理程序, 它對錯誤數據的處理是以頁為單位, 針對該錯誤頁是匿名頁還是文件緩存頁, 是系統頁還是進程頁, 等等, 多種細緻情況採取不同的措施. 關於此類細節, 可看此文章: [45]

13.3 Cross Memory Attach - 進程間快速消息傳遞 3.2(2012年1月發布)

這一節相對於其他本章內容是獨立的. MPI(Message Passing Interface, 消息傳遞介面) [46] 是一個定義並行編程模型下用於進程間消息傳遞的一個高性能, 可擴展, 可移植的介面規範(注意這只是一個標準, 有多個實現). 之前的 MPI 程序在進程間共享信息是用到共享內存(shared memory)方式, 進程間的消息傳遞需要 2 次內存拷貝. 而 3.2 版本引入的 "Cross Memory Attach" 的 patch, 引入兩個新的系統調用介面. 借用這兩個介面, MPI 程序可以只使用一次拷貝, 從而提升性能.

相關的文章介紹: [47].

========== 內存管理子系統結束分割線　==========

中斷與異常子系統(interrupt exception)
時間子系統(timer timekeeping)
同步機制子系統(synchronization)
塊層(block layer)
文件子系統(Linux 通用文件系統層 VFS, various fs)
網路子系統(networking)
調試和追蹤子系統(debugging, tracing)
虛擬化子系統(kvm)
控制組(cgroup)

---

引用：

[1] Single UNIX Specification

[2] POSIX 關於調度規範的文檔: http://nicolas.navet.eu/publi/SlidesPosixKoblenz.pdf

[3]Towards Linux 2.6

[4]Linux內核發布模式與開發組織模式(1)

[5] IBM developworks 上有一篇綜述文章，值得一讀 :Linux 調度器發展簡述

[6]CFS group scheduling [LWN.net]

[7]http://lse.sourceforge.net/numa/

[8]CFS bandwidth control [LWN.net]

[9]kernel/git/torvalds/linux.git

[10]DMA模式_百度百科

[11]進程的虛擬地址和內核中的虛擬地址有什麼關係？ - 詹健宇的回答

[12]Physical Page Allocation

[13]The SLUB allocator [LWN.net]

[14]Lumpy Reclaim V3 [LWN.net]

[15]Group pages of related mobility together to reduce external fragmentation v28 [LWN.net]

[16]Memory compaction [LWN.net]

[17]kernel 3.10內核源碼分析--TLB相關--TLB概念、flush、TLB lazy模式-humjb_1983-ChinaUnix博客

[18]Toward improved page replacement [LWN.net]

[19]kernel/git/torvalds/linux.git

[20]The state of the pageout scalability patches [LWN.net]

[21]kernel/git/torvalds/linux.git

[22]Being nicer to executable pages [LWN.net]

[23]kernel/git/torvalds/linux.git

[24]Better active/inactive list balancing [LWN.net]

[25]Smarter write throttling [LWN.net]

[26]https://zh.wikipedia.org/wiki/%E6%8C%87%E6%95%B0%E8%A1%B0%E5%87%8F

[27]Flushing out pdflush [LWN.net]

[28]Dynamic writeback throttling [LWN.net]

[29]On-demand readahead [LWN.net]

[30]Transparent huge pages in 2.6.38 [LWN.net]

[31]https://events.linuxfoundation.org/sites/events/files/lcjp13_ishimatsu.pdf

[32]transcendent memory for Linux [LWN.net]

[33]linux kernel monkey log

[34]zcache: a compressed page cache [LWN.net]

[35]The zswap compressed swap cache [LWN.net]

[36]Linux-Kernel Archive: Linux 2.6.0

[37]搶佔支持的引入時間: https://www.kernel.org/pub/linux/kernel/v2.5/ChangeLog-2.5.4

[38]RAM is 100 Thousand Times Faster than Disk for Database Access

[39] http://www.uefi.org/sites/default/files/resources/ACPI_6.0.pdf

[40]Injecting faults into the kernel [LWN.net]

[41]Detecting kernel memory leaks [LWN.net]

[42]The kernel address sanitizer [LWN.net]

[43]Linux Kernel Shared Memory 剖析

[44]KSM tries again [LWN.net]

[45]HWPOISON [LWN.net]

[46]https://www.mcs.anl.gov/research/projects/mpi/

[47]Fast interprocess messaging [LWN.net]

---8&<---

更新日誌:

- 2015.9.12

o 完成調度器子系統的初次更新, 從早上10點開始寫，寫了近７小時, 比較累，後面更新得慢的話大家不要怪我(對手指

- 2015.9.19

o 完成內存管理子系統的前4章更新。同樣是寫了一天，內容太多，沒能寫完......

- 2015.9.21

o 完成內存管理子系統的第5章"頁面寫回"的第1小節的更新。

- 2015.9.25

o 更改一些排版和個別文字描述。接下來周末兩天繼續。

- 2015.9.26

o 完成內存管理子系統的第5, 6, 7, 8章的更新。

- 2015.10.14

o 國慶離網10來天, 未更新。今天完成了內存管理子系統的第9章的更新。

- 2015.10.16

o 完成內存管理子系統的第10章的更新。

- 2015.11.22

o 這個月在出差和休假, 一直未更新.抱歉! 根據知友 @costa 提供的無水印圖片和考證資料, 進行了一些小更新和修正. 特此感謝 !

o 完成內存管理子系統的第11章關於 NVDIMM 內容的更新。

- 2016.1.2

o 中斷許久, 今天完成了內存管理子系統的第11章關於調試支持內容的更新。

- 2016.2.23

o 又中斷許久, 因為懶癌發作Orz... 完成了第二個子系統的所有章節。

每一個release具體做了什麼改動, 請看這裡:

LinuxVersions

我要開始搬運了:

2.6.39與3.0兩個版本的發布間隔了64天. 那麼到底發生了什麼?

1. Prominent features

1.1. Btrfs: Automatic defragmentation, scrubbing, performance improvements

Automatic defragmentation
COW (copy-on-write) filesystems have many
advantages, but they also have some disadvantages, for example
fragmentation. Btrfs lays out the data sequentially when files are
written to the disk for first time, but a COW design implies that any
subsequent modification to the file must not be written on top of the
old data, but be placed in a free block, which will cause fragmentation
(RPM databases are a common case of this problem). Aditionally, it
suffers the fragmentation problems common to all filesystems.
Btrfs already offers alternatives to fight this
problem: First, it supports online defragmentation using the command
"btrfs filesystem defragment". Second, it has a mount option, -o
nodatacow, that disables COW for data. Now btrfs adds a third option,
the -o autodefrag mount option. This mechanism detects small random
writes into files and queues them up for an automatic defrag process, so
the filesystem will defragment itself while it"s used. It isn"t suited
to virtualization or big database workloads yet, but works well for
smaller files such as rpm, SQLite or bdb databases. Code: (commit)
Scrub
"Scrubbing" is the process of checking the
integrity of the data in the filesystem. This initial implementation of
scrubbing will check the checksums of all the extents in the filesystem.
If an error occurs (checksum or IO error), a good copy is searched for.
If one is found, the bad copy will be rewritten. Code: (commit 1, 2)
Other improvements
-File creation/deletion speedup: The performance
of file creation and deletion on btrfs was very poor. The reason is that
for each creation or deletion, btrfs must do a lot of b+ tree
insertions, such as inode item, directory name item, directory name
index and so on. Now btrfs can do some delayed b+ tree insertions or
deletions, which allows to batch these modifications. Microbenchmarks of
file creation have been speed up by ~15%, and file deletion by ~20%.
Code: (commit)
-Do not flush csum items of
unchanged file data: speeds up fsync. A sysbench workload doing "random
write + fsync" went from 112.75 requests/sec to 1216 requests/sec. Code:
(commit)
-Quasi-round-robin for space
allocation in multidevice setups: the chunk allocator currently always
allocates space on the devices in the same order. This leads to a very
uneven distribution, especially with RAID1 or RAID10 and an uneven
number of devices. Now Btrfs always sorts the devices before allocating,
and allocates the stripes on the devices with the most available space.
Code: (commit)

1.2. sendmmsg(): batching of sendmsg() calls

Recvmsg() and sendmsg() are the syscalls used to receive/send data to the network. In 2.6.33, Linux added recvmmsg(),
a syscall that allows to receive in a single call data that would need
multiple recvmsg() calls, improving throughput and latency for a number
of scenarios. Now, a equivalent sendmmsg() syscall has been added. A
microbenchmark saw a 20% improvement in throughput on UDP send and 30%
on raw socket send
Code: (commit)

1.3. XEN dom0 support

Finally, Linux has got Xen dom0 support

1.4. Cleancache

Recommended LWN article: Cleancache and Frontswap
Cleancache is an optional feature that can
potentially increases page cache performance. It could be described as a
memcached-like system, but for cache memory pages. It provides memory
storage not directly accessible or addressable by the kernel, and it
does not guarantee that the data will not vanish. It can be used by
virtualization software to improve memory handling for guests, but it
can also be useful to implement things like a compressed cache.
Code: (commit), (commit)

1.5. Berkeley Packet Filter just-in-time filtering

Recommended LWN article: A JIT for packet filters
The Berkeley Packet Filter filtering
capabilities, used by tools like libpcap/tcpdump, are normally handled
by an interpreter. This release adds a simple JIT that generates native
code when filter is loaded in memory (something already done by other
OSes, like FreeBSD). Admin need to enable this feature writting "1" to /proc/sys/net/core/bpf_jit_enable
Code: (commit)

1.6. Wake on WLAN support

Wake on Wireless is a feature
to allow the system to go into a low-power state (e.g. ACPI S3 suspend)
while the wireless NIC remains active and does varying things for the
host, e.g. staying connected to an AP or searching for networks. The
802.11 stack has added support for it.
Code: (commit 1, 2)

1.7. Unprivileged ICMP_ECHO messages

Recommended LWN article: ICMP sockets
This release makes it possible to send ICMP_ECHO
messages (ping) and receive the corresponding ICMP_ECHOREPLY messages
without any special privileges, similar to what is implemented in Mac OS X.
In other words, the patch makes it possible to implement setuid-less
and CAP_NET_RAW-less /bin/ping. Initially this functionality was written
for Linux 2.4.32, but unfortunately it was never made public. The new
functionality is disabled by default, and is enabled at bootup by
supporting Linux distributions, optionally with restriction to a group
or a group range.
Code: (commit)

1.8. setns() syscall: better namespace handling

Recommended LWN article: Namespace file descriptors
Linux supports different namespaces for many of
the resources its handles; for example, lightweight forms of
virtualization such as containers or systemd-nspaw
show to the virtualized processes a virtual PID different from the real
PID. The same thing can be done with the filesystem directory
structure, network resources, IPC, etc. The only way to set different
namespace configurations was using different flags in the clone()
syscall, but that system didn"t do things like allow to one processes to
access to other process" namespace. The setns() syscall solves that
problem-
Code: (commit 1, 2, 3, 4, 5, 6)

1.9. Alarm-timers

Recommended LWN article: Waking systems from suspend
Alarm-timers are a hybrid style timer, similar to
high-resolution timers, but when the system is suspended, the RTC
device is set to fire and wake the system for when the soonest
alarm-timer expires. The concept for Alarm-timers was inspired by the
Android Alarm driver, and the interface to userland uses the POSIX clock
and timers interface, using two new clockids:CLOCK_REALTIME_ALARM and
CLOCK_BOOTTIME_ALARM.
Code: (commit 1, 2)

2. Driver and architecture-specific changes

All the driver and architecture-specific changes can be found in the Linux_3.0_DriverArch page

3. VFS

Cache xattr security drop check for write: benchmarking on btrfs
showed that a major scaling bottleneck on large systems on btrfs is
currently the xattr lookup on every write, which causes an additional
tree walk, hitting some per file system locks and quite bad scalability.
This is also a problem in ext4, where it hits the global mbcache lock.
Caching this check solves the problem (commit)

4. Process scheduler

Increase SCHED_LOAD_SCALE resolution: With this extra resolution,
the scheduler can handle deeper cgroup hiearchies and do better shares
distribution and load balancing on larger systems (especially for low
weight task groups) (commit), (commit)

Move the second half of ttwu() to the remote CPU: avoids having
to take rq-&>lock and doing the task enqueue remotely, saving lots on
cacheline transfers. A semaphore benchmark goes from 647278 worker burns
per second to 816715 (commit)

Next buddy hint on sleep and preempt path: a worst-case benchmark
consisting of 2 tbench client processes with 2 threads each running on a
single CPU changed from 105.84 MB/sec to 112.42 MB/sec (commit)

5. Memory management

Make mmu_gather preempemtible (commit)

Batch activate_page() calls to reduce zone-&>lru_lock contention (commit)

tmpfs: implement generic xattr support (commit)

Memory cgroup controller:

Add memory.numastat API for NUMA statistics (commit)

Add the pagefault count into memcg stats (commit)

Reclaim memory from nodes in round-robin order (commit)

Remove the deprecated noswapaccount kernel parameter (commit)

6. Networking

Allow setting the network namespace by fd (commit)

Wireless

Add the ability to advertise possible interface combinations (commit)

Add support for scheduled scans (commit)

Add userspace authentication flag to mesh setup (commit)

New notification to discover mesh peer candidates. (commit)

Allow ethtool to set interface in loopback mode. (commit)

Allow no-cache copy from user on transmit (commit)

ipset: SCTP, UDPLITE support added (commit)

sctp: implement socket option SCTP_GET_ASSOC_ID_LIST (commit), implement event notification SCTP_SENDER_DRY_EVENT (commit)

bridge: allow creating bridge devices with netlink (commit), allow creating/deleting fdb entries via netlink (commit)

batman-adv: multi vlan support for bridge loop detection (commit)

pkt_sched: QFQ - quick fair queue scheduler (commit)

RDMA: Add netlink infrastructure that allows for registration of RDMA clients (commit)

7. File systems

BLOCK LAYER

Submit discard bio in batches in blkdev_issue_discard() - makes discarding data faster (commit)

EXT4

Enable "punch hole" functionality (recommended LWN article) (commit), (commit)

Add support for multiple mount protection (commit)

CIFS

Add support for mounting Windows 2008 DFS shares (commit)

Convert cifs_writepages to use async writes (commit), (commit)

Add rwpidforward mount option that enables a mode when CIFS
forwards pid of a process who opened a file to any read and write
operation (commit)

OCFS2

SSD trimming support (commit), (commit)

Support for moving extents (commit), (commit)

NILFS2

Implement resize ioctl (commit)

XFS

Add online discard support (commit)

8. Crypto

caam - Add support for the Freescale SEC4/CAAM (commit)

padlock - Add SHA-1/256 module for VIA Nano (commit)

s390: add System z hardware support for CTR mode (commit), add System z hardware support for GHASH (commit), add System z hardware support for XTS mode (commit)

s5p-sss - add S5PV210 advanced crypto engine support (commit)

9. Virtualization

User-mode Linux: add earlyprintk support (commit), add ucast Ethernet transport (commit)

xen: add blkback support (commit)

10. Security

Allow the application of capability limits to usermode helpers (commit)

SELinux

add /sys/fs/selinux mount point to put selinuxfs (commit)

Make SELinux cache VFS RCU walks safe (improves VFS performance) (commit)

11. Tracing/profiling

perf stat: Add -d -d and -d -d -d options to show more CPU events (commit), (commit)

perf stat: Add --sync/-S option (commit)

12. Various core changes

rcu: priority boosting for TREE_PREEMPT_RCU (commit)

ulimit: raise default hard ulimit on number of files to 4096 (commit)

cgroups

remove the Namespace cgroup subsystem. It has been replaced by a
compatibility flag "clone_children", where a newly created cgroup will
copy the parent cgroup values. The userspace has to manually create a
cgroup and add a task to the "tasks" file (commit)

Make "procs" file writable (commit)

kbuild: implement several W= levels (commit)

PM/Hibernate: Add sysfs knob to control size of memory for drivers (commit)

posix-timers: RCU conversion (commit)

coredump: add support for exe_file in core name (commit)

3.19到4.0間隔了63天, 期間究竟發生了什麼?:

1. Prominent features

1.1. Arbitrary version change

This release increases the
version to 4.0. This switch from 3.x to 4.0 version numbers is, however,
entirely meaningless and it should not be associated to any important
changes in the kernel. This release could have been 3.20, but Linus
Torvalds just got tired of the old number, made a poll, and changed it. Yes, it is frivolous. The less you think about it, the better.

1.2. Live patching

This release introduces
"livepatch", a feature for live patching the kernel code, aimed
primarily at systems who want to get security updates without needing to
reboot. This feature has been born as result of merging kgraft and
kpatch, two attempts by SuSE and Red Hat that where started to replace
the now propietary ksplice. It"s relatively simple and minimalistic, as
it"s making use of existing kernel infrastructure (namely ftrace) as
much as possible. It"s also self-contained and it doesn"t hook itself in
any other kernel subsystems.
In this release livepatch is not feature
complete, yet it provides a basic infrastructure for function "live
patching" (i.e. code redirection), including API for kernel modules
containing the actual patches, and API/ABI for userspace to be able to
operate on the patches (look up what patches are applied, enable/disable
them, etc). Most CVEs should be safe to apply this way. Only the x86
architecture is supported in this release, others will follow.
For more details see the merge commit
Sample live patching module: commit
Code commit

1.3. DAX - Direct Access, for persistent memory storage

Before being read by
programs, files are usually first copied from the disk to the kernel
caches, kept in RAM. But the possible advent of persistent non-volatile
memory that would be also be used as disk changes radically the way the
kernel deals with this process: the kernel cache would become unnecesary
overhead.
Linux has had, in fact, support for this kind of setups since 2.6.13.
But the code wasn"t maintaned and only supported ext2. In this release,
Linux adds DAX (Direct Access, the X is for eXciting). DAX removes the
extra copy incurred by the buffer by performing reads and writes
directly to the persistent-memory storage device. For file mappings, the
storage device is mapped directly into userspace. Support for ext4 has
been added.
Recommended LWN article: Supporting filesystems in persistent memory
Code: commit, commit, commit, commit, commit, commit, commit, commit, commit, commit, commit, commit, commit

1.4. kasan, kernel address sanitizer

Kernel Address sanitizer
(KASan) is a dynamic memory error detector. It provides fast and
comprehensive solution for finding use-after-free and out-of-bounds
bugs. Linux already has the kmemcheck feature, but unlike kmemcheck,
KASan uses compile-time instrumentation, which makes it significantly
faster than kmemcheck.
The main idea of KASAN is to use shadow memory to
record whether each byte of memory is safe to access or not, and use
compiler"s instrumentation to check the shadow memory on each memory
access. Address sanitizer uses 1/8 of the memory addressable in kernel
for shadow memory and uses direct mapping with a scale and offset to
translate a memory address to its corresponding shadow address.
Code: commit, commit, commit, commit, commit

1.5. "lazytime" option for better update of file timestamps

Unix filesystems keep track
of information about files, such as the last time a file was accessed or
modified. Keeping track of this information is very expensive,
specially the time when a file was accessed ("atime"), which encourages
many people to disable it with the mount option "noatime". To alleviate
this problem, the "relatime" mount option was added, the atime is only
updated if the previous value is earlier than the modification time, or
if the file was last accessed more than 24 hours ago. This behaviour,
however, breaks some programs that rely on accurate access time tracking
to work, and it"s also against the POSIX standard.
In this release, Linux adds another alternative:
"lazytime". Lazytime causes access, modified and changed time updates to
only be made in the cache. The times will only be written to the disk
if the inode needs to be updated anyway for some non-time related
change, if fsync(), syncfs() or sync() are called, or just before an
undeleted inode is evicted from memory. This is POSIX compliant, while
at the same time improving the performance.
Recommended LWN article: Introducing lazytime
Code: commit, commit, commit

1.6. Multiple lower layers in overlayfs

In overlayfs, multiple lower
layers can now be given using the the colon (":") as a separator
character between the directory names. For example:

mount -t overlay overlay -olowerdir=/lower1:/lower2:/lower3 /merged

The specified lower directories will be stacked beginning from the
rightmost one and going left. In the above example lower1 will be the
top, lower2 the middle and lower3 the bottom layer. "upperdir=" and
"workdir=" may be omitted, in that case the overlay will be read-only.
Code: commit, commit

1.7. Support Parallel NFS server, default to NFS v4.2

Parallel NFS (pNFS) is a part
of the NFS v4.1 standard that allows compute clients to access storage
devices directly and in parallel. The pNFS architecture eliminates the
scalability and performance issues associated with NFS servers deployed
today. This is achieved by the separation of data and metadata, and
moving the metadata server out of the data path.
This release adds support for pNFS server, and
drivers for the block layout with XFS support to use XFS filesystems as a
block layout target, and the flexfiles layout.
Also, in this release the NFS server defaults to NFS v4.2.
Code: commit, commit, commit, commit, commit, commit

1.8. dm-crypt scalability improvements

This release significantly
increases the dm-crypt CPU scalability performance thanks to changes
that enable effective use of an unbound workqueue across all available
CPUs. A large battery of tests were performed to validate these changes,
summary of results is available here
Merge: commit

2. File systems

XFS

Adds support for sys_renameat2() commit

Remove deprecated sysctls xfsbufd_centisecs and age_buffer_centisecs commit

EXT4

Support "readonly" filesystem flag to mark a FS image as
read-only, tunable with tune2fs. It prevents the kernel and e2fsprogs
from changing the image commit

Btrfs

Add code to support file creation time commit

NFSv4.1

Allow parallel LOCK/LOCKU calls commit

Allow parallel OPEN/OPEN_DOWNGRADE/CLOSE commit

UBIFS

Add security.* XATTR support for the UBIFS commit

Add xattr support for symlinks commit

OCFS2

Add a mount option journal_async_commit on ocfs2 filesystem. When
this feature is opened, journal commit block can be written to disk
without waiting for descriptor blocks, which can improve journal commit
performance. Using the fs_mark benchmark, using journal_async_commit
shows a 50% improvement commit

Currently in case of append O_DIRECT write (block not allocated
yet), ocfs2 will fall back to buffered I/O. This has some
disadvantages. In this version, the direct I/O write doesn"t fallback to
buffer I/O write any more because the allocate blocks are enabled in
direct I/O now commit, commit, commit

F2FS

Introduce a batched trim commit

Support "norecovery" mount option, which is mostly same as
"disable_roll_forward". The only difference is that "norecovery" should
be activated with read-only mount option. This can be used when user
wants to check whether f2fs is mountable or not without any recovery
process commit

Add F2FS_IOC_GETVERSION ioctl for getting i_generation from
inode, after that, users can list file"s generation number by using
"lsattr -v commit

3. Block

Ported to blk-multiqueue

loop: Add blk-mq support, which greatly improves performance for sequential and random reads commit

Device-mapper commit

rbd commit

UBI commit

blk-multiqueue: Add support for tag allocation policies and make libata use this blk-mq tagging, instead of rolling their own commit, commit

UBI: Implement UBI_METAONLY, a new open mode for UBI volumes, it indicates that only meta data is being changed commit

4. Core (various)

pstore: Add pmsg - user-space accessible pstore object commit

rcu: Optionally run grace-period kthreads at real-time priority.
Recent testing has shown that under heavy load, running RCU"s
grace-period kthreads at real-time priority can improve performance and
reduce the incidence of RCU CPU stall warnings commit

GDB scripts for debugging the kernel. If you load vmlinux into
gdb with the option enabled, the helper scripts will be automatically
imported by gdb as well, and additional functions are available to
analyze a Linux kernel instance. See Documentation/gdb-kernel-debugging.txt for further details commit

Remove CONFIG_INIT_FALLBACK commit

5. Memory management

cgroups: Per memory cgroup slab shrinkers commit

slub: optimize memory alloc/free fastpath by removing preemption on/off commit

Add KPF_ZERO_PAGE flag for zero_page, so that userspace processes
can detect zero_page in /proc/kpageflags, and then do memory analysis
more accurately commit

Make /dev/mem an optional device commit

Add support for resetting peak RSS, which can be retrieved from
the VmHWM field in /proc/pid/status, by writing "5" to
/proc/pid/clear_refs commit

Show page size in /proc/&
/numa_maps as
"kernelpagesize_kB" field to help identifying the size of pages that are
backing memory areas mapped by a given task. This is specially useful
to help differentiating between HUGE and GIGANTIC page backed VMAs commit

geneve: Add Geneve GRO support commit

zsmalloc: add statistics support commit

Incorporate read-only pages into transparent huge pages commit

memcontrol cgroup: Introduce the basic control files to account,
partition, and limit memory using cgroups in default hierarchy mode. The
old interface will be maintained, but a clearer model and improved
workload performance should encourage existing users to switch over to
the new one eventually commit

Replace remap_file_pages() syscall with emulation commit

6. Virtualization

KVM: Add generic support for page modification logging, a new
feature in Intel "Broadwell" Xeon CPUs that speeds up dirty page
tracking commit

vfio: Add device request interface indicating that the device should be released commit

vmxnet3: Make Rx ring 2 size configurable by adjusting rx-jumbo parameter of ethtool -G commit

virtio_net: add software timestamp support commit

virtio_pci: modern driver commit, add an options to disable legacy driver commit, commit

7. Cryptography

aesni: Add support for 192 256 bit keys to AES-NI RFC4106 commit

algif_rng: add random number generator support commit

octeon: add MD5 module commit

qat: add support for CBC(AES) ablkcipher commit

8. Security

SELinux : Add security hooks to the Android Binder that enable
security modules such as SELinux to implement controls over Binder IPC.
The security hooks include support for controlling what process can
become the Binder context manager, invoke a binder transaction/IPC to
another process, transfer a binder reference to another process ,
transfer an open file to another process. These hooks have been included
in the Android kernel trees since Android 4.3 (commit).

SMACK: secmark support for netfilter (commit).

TPM 2.0 support (commits: 1, 2, 3).

Device class for TPM, sysfs files are moved from /sys/class/misc/tpmX/device/ to /sys/class/tpm/tpmX/device/ (commit).

9. Tracing perf

perf mem: Enable sampling loads and stores simultaneously, it
could only do one or the other before yet there was no hardware
restriction preventing simultaneous collection commit

perf tools: Support parameterized and symbolic events. See links for documentation commit, commit

AMD range breakpoints support: breakpoints are
extended to support address range through perf event with initial
backend support for AMD extended breakpoints. For example set write
breakpoint from 0x1000 to 0x1200 (0x1000 + 512): perf record -e
mem:0x1000/512:w commit, commit

10. Networking

TCP: Add the possibility to define a per route/destination
congestion control algorithm. This opens up the possibility for a
machine with different links to enforce specific congestion control
algorithms with optimal strategies for each of them based on their
network characteristics commit

Mitigate TCP "ACK loop" DoS scenarios by rate-limiting outgoing
duplicate ACKs sent in response to incoming "out of window" segments.
For more details, see merge. Code: commit, commit, commit, commit

udpv6: Add lockless sendmsg() support, thus allowing multiple threads to send to a single socket more efficiently commit

ipv4: Automatically bring up DSA master network devices, which
allows DSA slave network devices to be used as valid interfaces for e.g:
NFS root booting by allowing kernel IP auto-configuration to succeed on
these interfaces commit

ipv6: Add sysctl entry(accept_ra_mtu) to disable MTU updates from router advertisements commit

vxlan: Implement supports for the Group Policy VXLAN extension
to provide a lightweight and simple security label mechanism across
network peers based on VXLAN. It allows further mapping to a SELinux
context using SECMARK, to implement ACLs directly with nftables,
iptables, OVS, tc, etc commit

vxlan: Add support for remote checksum offload in VXLAN. It is described here. commit

net: openvswitch: Support masked set actions. commit

Infiniband: Add support for extensible query device capabilities verb to allow adding new features commit

Layer 2 Tunneling Protocol (l2tp): multicast notification to the
registered listeners when the tunnels/sessions are
created/modified/deleted commit

SUNRPC: Set SO_REUSEPORT socket option for TCP
connections to bind multiple TCP connections to the same source
address+port combination commit

tipc: involve namespace infrastructure commit

802.15.4: introduce support for cca settings commit

Wireless

Add new GCMP, GCMP-256, CCMP-256, BIP-GMAC-128, BIP-GMAC-256, and
BIP-CMAC-256 cipher suites. These new cipher suites were defined in
IEEE Std 802.11ac-2013 commit, commit, commit, commit, commit

New NL80211_ATTR_NETNS_FD which allows to set namespace via nl80211 by fd commit

Support per-TID station statistics commit

Allow including station info in delete event commit, commit

Allow usermode to query wiphy specific regdom commit

bridge

offload bridge port attributes to switch ASIC if feature flag set commit

Support for allowing userspace to pack multiple vlans and VLAN ranges in setlink and dellink requests for improved performance commit

Add ability to enable TSO commit

Near Field Communication (NFC)

HCI over NCI protocol support (Some secure elements only understand HCI and thus we need to send them HCI frames) commit

NCI NFCEE (NFC Execution Environment, typically an embedded or
external secure element) discovery and enabling/disabling support commit, commit, commit, commit, commit, commit, commit

NFC_EVT_TRANSACTION userspace API addition, it is sent through
netlink in order for a specific application running on a secure element
to notify userspace of an event commit

Tx timestamps are looped onto the error queue on top of an skb.
This mechanism leaks packet headers to processes unless the no-payload
options SOF_TIMESTAMPING_OPT_TSONLY is set. A new sysctl
(tstamp_allow_data) optionally drops looped timestamp with data. This
only affects processes without CAP_NET_RAW commit, commit, commit

Bluetooth

Enable LE Data Length Extension feature from Bluetooth 4.2 specification commit

Expose information in debugfs: Secure Simple Pairing commit, debug keys usage setting commit, hardware error code commit, remote OOB information commit

HCI Read Stored Link Keys commit, commit

HCI Delete Stored Link Key commit, commit

Support static address when BR/EDR has been disabled commit

tc: add BPF-based action. This action provides a possibility to execute custom BPF code commit

net: sched: Introduce connmark action commit

Add Transparent Ethernet Bridging GRO support commit

netdev: introduce new NETIF_F_HW_SWITCH_OFFLOAD feature flag for switch device offloads commit

netfilter: nft_compat: add ebtables support commit

network namespace: Add rtnl cmd to add and get peer netns ids. A
user can define an id for a peer netns by providing a FD or a PID. These
ids are local to the netns where it is added (i.e. valid only into this
netns) commit, commit

openvswitch: Add support for checksums on UDP tunnels. commit

openvswitch: Support VXLAN Group Policy extension commit

每一個release具體做了什麼改動, 請看這裡:

LinuxVersions

說到細節，這兩個版本之間的差異那是過於巨大，沒有大量篇幅是無法說清楚的。但是如果從設計上，或許能夠管中窺豹，有一個框架性的把握。

（1）代碼/目錄架構優化。這個讓層次更為清晰，對於這種超大項目後續的演進是十分有利的。

（2）動態化。還記得2.4版本，在/dev目錄下創建幾千個設備節點的情形嗎？給開發/應用帶來很大的困擾。所謂動態化，就是很多設計思想慢慢的沉澱在內核設計中，並且不斷的發展、優化。比如，設備（Device）與驅動（Driver）嚴格分離，使得架構更為清晰，可擴展性更強。如，net_device_ops與net_device結構體，在新版本中分離出來；這種改進有很多。系統擴展性要求複雜性，而設計複雜性確確實實就帶來良好的可擴展性（不提易用/易理解，實際上現在內核實現封裝度大大增加，光走讀代碼是無法貫穿整個內核處理流程的，甚至連部分也難以達到）。如果真要用一些現在軟體方法來描述內核實現，我們可以這麼說：內核實現高度面向對象（Object-Oriented，見驅動-設備分離演化），採用了極多的設計模式，如創建模式（kmem_cache_create等），結構模式（組合模式net_device{wireless_dev}，裝飾模式VFS，橋接/適配模式platform_bus/platform_driver/platform_device），行為模式（模板方法struct list_head, rb_node; 職責鏈request_irq中斷處理等等）。當然，這些設計方法不能說在2.4時代沒有，有些可以認為是硬套用設計模式，但是不得不說，在現在的內核中體現這些設計得更為精緻，生命力更為強大。

2016/07/07

還記得當年走讀內核2.4版本代碼，其中一大及其不方便的就是所有體系架構相關的頭文件都是放在include目錄下，形成一個巨無霸目錄；十多個asm-x86/asm-ppc/asm-ppc等目錄，這對當年希望針對一種體系架構代碼進行走讀研究的我，感覺不太爽。當年其實是缺乏如eclipse這樣強大的工具，不能對代碼目錄進行過濾，用原始編輯器去追蹤源簡直是亂入。現在體系相關的頭文件都置於arch/ARCH(arm,x86)/include/asm之下，結構清晰很多。另外不要小看這種調整，一點改進可提升眾人的接受度，效益其實是巨大的。

另外一個改進是體系架構代碼的混亂；比如，以前2.4到2.6早期版本，arch目錄下即有ppc目錄，又有powerpc目錄；而且很多源碼文件同時包含asm-ppc和asp-powerpc下的頭文件，分析、修改都頗讓人頭疼。在後續都合併；此外典型的還有x86與x64_64兩個目錄的合併，都讓不同內核體系架構支持更為簡潔、明確，見著都爽心多了。

ARM體系架構最近幾年大火，各個廠商都合入了大量的處理器、開發板支持代碼，各種硬編碼的實現讓ARM體系架構代碼顯得雜亂臃腫不堪；這個也是讓Linus幾次FUCKING的事情，確實太難看了一些。自從大神FUCK了之後，開源社區迅速跟進，大量引入使用OpenFirmware/DTS使得狀況大為改觀，現在的ARM架構代碼清爽了很多了（應該說是自2.6.32版本之後）。

有時間再更新一下設計上的改進。

還有好多，待更新

今天還不斷有「大神」給新人安利 ldd3

可是ldd3上的例子，需要密密麻麻的修改，才可能在最新的內核上執行。

史上最大謎團:

linux 2.6到4.2到底經過了幾個版本？

namespace和cgroup吧，docker的實現就是基於這些。