第一次寫進(jìn)程創(chuàng)建的時(shí)候我使用的內(nèi)核版本還是 3.10 的版本。在這個(gè)版本里已分配的進(jìn)程 pid 號(hào)是用 bitmap 來存儲(chǔ)的。但在 5.4 和 6.1 版本里，發(fā)現(xiàn)進(jìn)程 pid 號(hào)管理實(shí)現(xiàn)已經(jīng)從 bitmap 替換成了基數(shù)樹（radix-tree）。后來翻了下版本更新歷史，原來自從 Linux 4.15 之后，內(nèi)核就已經(jīng)將 bitmap 換掉了。

所以今天我來給大家聊聊為什么 Linux 內(nèi)核要將 bitmap 替換成基數(shù)樹，最后也看看這次替換的性能效果。

一、舊的 bitmap 方式管理 pid

內(nèi)核需要為每一個(gè)進(jìn)程/線程都分配一個(gè)進(jìn)程號(hào)。

如果每個(gè)使用過的進(jìn)程號(hào)如果使用傳統(tǒng)的 int 變量來存儲(chǔ)的話會(huì)消耗很大的內(nèi)存。假如內(nèi)核要支持最大 65535 個(gè)進(jìn)程，那存儲(chǔ)這些進(jìn)程號(hào)需要 65535*4 字節(jié) = 262,140字節(jié) ≈ 260 KB。

bitmap 可以極大地壓縮整數(shù)的存儲(chǔ)。如果使用 bitmap 來存儲(chǔ)使用過的進(jìn)程號(hào)，用一個(gè) bit 表示對(duì)應(yīng)的 pid 是否被使用過了。最大支持 65535 個(gè)進(jìn)程的話，只需要 65535 / 8 = 8 KB 的內(nèi)存就夠用了。相比上面的 260 KB，內(nèi)存節(jié)約的非常的多。

占用內(nèi)存小還有一個(gè)特別大的優(yōu)勢(shì)，那就是遍歷的時(shí)候，由于局部性特別好，CPU 緩存命中率特別的高，遍歷的時(shí)候性能就會(huì)特別好。所以，之前很長的一段時(shí)間里，內(nèi)核都是使用 bitmap 來管理所有的進(jìn)程 pid。

內(nèi)核中創(chuàng)建進(jìn)程時(shí)申請(qǐng) pid 的核心函數(shù)是 alloc_pid。在 3.10 版本中的時(shí)候，分配 pid 調(diào)用 pidmap 的接口函數(shù) alloc_pidmap 來完成。它的源碼是下面這個(gè)樣子的：

如前面所述，bitmap 的最大好處是節(jié)約內(nèi)存。但其也有個(gè)比較大的缺點(diǎn)，分配一個(gè)新的 pid 時(shí)的計(jì)算復(fù)雜度比較高。如果在進(jìn)程數(shù)量比較多的，幾乎需要把整個(gè) bitmap 中的每一個(gè) bit 位都遍歷一遍才行。

在最近幾年的業(yè)界發(fā)展中，服務(wù)器的內(nèi)存越來越大，服務(wù)器上幾百 GB 的內(nèi)存都很常見。另外隨著這幾年輕量化容器云的發(fā)展，服務(wù)器上運(yùn)行的進(jìn)程數(shù)越來越多。傳統(tǒng)的基于 bitmap 來管理分配的 pid 的節(jié)約內(nèi)存的優(yōu)勢(shì)越來越顯得沒有價(jià)值，而它分配新 pid 時(shí)占用的 CPU 資源較高這一缺點(diǎn)越來越明顯。

二、使用基數(shù)樹管理 pid

在 2017 年的時(shí)候，Gargi Sharma 提交了一個(gè)名為 “Replace PID bitmap allocation with IDR AP” 的 patch，在這個(gè)提交里 bitmap 被開始替換成了基數(shù)樹。并最終被并入到了 Linux 4.15 的版本中。關(guān)于這個(gè)提交的詳情參見https://lwn.net/Articles/735675/?或?https://lore.kernel.org/lkml/f5104f457ed581e0ac032a68af03c5ba5cb94755.1506342921.git.gs051095@gmail.com/

樹相關(guān)的數(shù)據(jù)結(jié)構(gòu)是變體最多的，基數(shù)樹就是樹數(shù)據(jù)結(jié)構(gòu)的其中一種。它有最明顯的特點(diǎn)是它的每一層只管理一個(gè) 6 bit 的分段。所以它的分叉數(shù)基本是固定的 64（2^6=64）（根節(jié)點(diǎn)除外），層數(shù)也是固定的。

基數(shù)樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義中，有幾個(gè)非常重要的字段，分別是 shift、slots 和 tags。

shift 表示了自己在數(shù)字中表示第幾段數(shù)字。在Linux 中默認(rèn)的基數(shù)大小為 6。這種情況下最低一層的內(nèi)部節(jié)點(diǎn)，shift 為 0，倒數(shù)第二層 shift 為 6。再上一層節(jié)點(diǎn)的 shift 為 12。以此類推，shift 從低往高， 逐層遞增 6。

slots 是一個(gè)指針數(shù)組，存儲(chǔ)的是其指向的子節(jié)點(diǎn)的指針。內(nèi)核中默認(rèn)情況下 XA_CHUNK_SIZE 是 64，也就是是一個(gè) *slots[64]。每個(gè)元素都指向下一級(jí)的樹節(jié)點(diǎn)，沒有下一級(jí)子節(jié)點(diǎn)的話指針指向 null。

tags 用來記錄 slog 數(shù)組中每一個(gè)下標(biāo)的存儲(chǔ)狀態(tài)?？梢杂脕肀硎久恳粋€(gè) slot 是否已經(jīng)分配出去的狀態(tài)。它是一個(gè) long 類型的數(shù)組，一個(gè) long 類型的變量是 8 個(gè)字節(jié)，正好有 64 個(gè) bit 位。

上面的過程描述有點(diǎn)抽象。為了更好地理解，我們?cè)偈褂靡粋€(gè)簡單的例子來看一下基數(shù)樹在內(nèi)存中的樣子。

內(nèi)核中的基數(shù)樹是用于管理 32 bit 位的 整數(shù) ID 的，但為了舉例更簡單清晰，我們用 16 bit 的整數(shù)組成的基數(shù)樹來舉例。

16 bit 的無符號(hào)整數(shù)的表示范圍是 0 - 65536。假設(shè)有一個(gè)由已經(jīng)分配出去的 100、1000、10000、50000、60000 的整數(shù) ID。我們把這幾個(gè)數(shù)組來組成的基數(shù)樹。

首先把上述各個(gè)整數(shù)的二進(jìn)制形式轉(zhuǎn)化出來如下，

• 100: 0000,000001,100100

• 1000: 0000,001111,101000

• 10000: 0010,011100,010000

• 50000: 1100,001101,010000

• 60000: 1110,101001,100000

在表示方式上，從尾部開始，按照 6 bit 為一組來表示。這樣，每一個(gè) 16 bit 位的數(shù)字可以拆分表示為一個(gè)三段的數(shù)字。

在基數(shù)樹中，根節(jié)點(diǎn)用來存儲(chǔ)的每個(gè)數(shù)字的第一段。如果其中某一個(gè)數(shù)字已占用，那就把 slot 對(duì)應(yīng)的下標(biāo)的指針指向其子節(jié)點(diǎn)。否則為空。在計(jì)算機(jī)中計(jì)算的時(shí)候，是通過將每個(gè)值右移 shift 這么多位，根節(jié)點(diǎn)的 shift 為 12，那就右移 12 位取得其結(jié)果。

對(duì)于整數(shù) 100、1000、10000、50000 和 60000 來說，它們的第一段分別是二進(jìn)制 0000、0000、0010、1100 和 1110，轉(zhuǎn)化成 10 進(jìn)制后是 0、0、2、12 和 14。

再下面一層節(jié)點(diǎn)的 slot 下標(biāo)是每個(gè)值中間 6 個(gè) bit 位的值，其 shift 為 6。第一層樹的節(jié)點(diǎn)的 slot 是每個(gè)值最后 6 個(gè) bit 的值，其 shift 為 0。我們?cè)賹⑸鲜雒恳粋€(gè)整數(shù)按照 6 bit 為分段，表示成 10 進(jìn)制如下：

• 100: 0,1,36

• 1000: 0,15,40

• 10000: 2,28,16

• 50000: 12,13,16

• 60000: 14,41,32

那么 100、1000、10000、50000、60000 這幾個(gè)數(shù)組成的基數(shù)樹的結(jié)構(gòu)如下圖所示。

拿整數(shù) 100 舉例，按每 6 bit 一段分表示后為 ?0, 1, 36。其第一段是 0 ，那就在基數(shù)樹的根節(jié)點(diǎn)的 slots 的 0 號(hào)下標(biāo)存儲(chǔ)其子節(jié)點(diǎn)指針。其第 2 分段為 1 ，那就在其第二層節(jié)點(diǎn)的 slots 的 1 號(hào)下標(biāo)存儲(chǔ)其子節(jié)點(diǎn)指針。在第三層節(jié)點(diǎn)的 slots 的 36 號(hào)下標(biāo)存儲(chǔ)最終的值 100。

基數(shù)樹就這樣建立好了。

在這個(gè)樹的基礎(chǔ)上判斷一個(gè)整數(shù)值是否存在，或者是從這個(gè)樹中分配一個(gè)新的未使用過的整數(shù) ID 出來的時(shí)候，只需要分別對(duì) 3 層的樹節(jié)點(diǎn)進(jìn)行遍歷，分別查看每一層中的 tag 狀態(tài)位，看 slots 對(duì)應(yīng)的下標(biāo)是否已經(jīng)占用即可。不像 bitmap 需要遍歷整個(gè) bit 數(shù)組。計(jì)算復(fù)雜度得到大大降低。

內(nèi)核和上面例子的區(qū)別是其基數(shù)樹存儲(chǔ)的是 32 bit 位的整數(shù)。樹的層次也就需要 6 層節(jié)點(diǎn)來存儲(chǔ)。

使用了基數(shù)樹后，內(nèi)核源碼也就發(fā)生了變化。在比較新的 6.1 版本的內(nèi)核中，alloc_pid 變成了下面這個(gè)樣子，通過調(diào)用 idr_alloc 來申請(qǐng)一個(gè)未使用過的進(jìn)程 ID 出來。

其申請(qǐng)的核心過程是 idr_get_free，主要就是遍歷這顆基數(shù)樹的若干節(jié)點(diǎn)，并根據(jù)每個(gè)節(jié)點(diǎn)的 tag、slot 等字段找出還未被占用的整數(shù) ID。

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【749907784】整理了一些個(gè)人覺得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書、實(shí)戰(zhàn)項(xiàng)目及代碼)? ?

三、基數(shù)樹的性能效果

原理我們講完了，我們?cè)賮砜聪率褂没鶖?shù)樹替代 bitmap 后的性能表現(xiàn)如何。這里我們直接引用該 patch 的提交者 Gargi Sharma 提供的實(shí)驗(yàn)數(shù)據(jù)。來自 https://lwn.net/Articles/735675/。

Gargi Sharma 在 10000 個(gè)進(jìn)程的情況下分別統(tǒng)計(jì)了 ps、pstree 的耗時(shí)情況。

可見，在使用了基數(shù)樹后，ps 和 pstree 命令的耗時(shí)都縮短了不少，性能大約提升了有 50%

原文作者：開發(fā)內(nèi)功修煉