Linux 核心專題: 高效記憶體配置器

執行人: kevinzxc1217
專題解說錄影

Reviewed by popo8712

在你的實驗中，有提到 LLFree 在多核系統中的效能提升主要來自於使用了 tree reservation 系統，避免了多核 CPU 之間的記憶體競爭。請問在這種情況下，如果多個 CPU 需要同一個 memory block，tree reservation 系統是如何有效地管理和調度記憶體資源，避免因為過多的 reservation 而導致的 memory fragmentation 問題的呢？

kevinzxc1217
透過 CPU-Local Tree Roots 方法，可以有效避免多個 CPU 競爭相同記憶體位址的問題，主要操作是當某個 CPU 決定要 reserve tree 時，它會將該 tree 的 cU 移動到 Local CPU 的 cP 中，同時將對應 Globel Counter 的 cU 設置為 0。

Reviewed by LindaTing0106

提到 LLFree 其中之一的優點為抗碎片化，想請問原因是？

kevinzxc1217
LLfree 配置和釋放時，只會針對固定大小的 Frame（4KB）進行管理，避免產生大小不一的記憶體區塊，減少碎片化的發生。

Reviewed by hugo0406

Preferred Tree
在初始化時，每個 CPU 會選擇一個 Preferred tree，當 CPU 需要配置記憶體空間時，會在自己的 Preferred tree 中進行搜尋和配置，避免多個 CPU 之間的競爭，提升配置效率。

Preferred Tree 是為了避免初期 CPU 競爭而配置的初始化記憶體區塊，想問是以什麼樣的方式去做不衝突的分派呢?是採取完全隨機配置嗎?若是使用在 hash 發生衝突的解決方式是否可以有效避免碰撞產生?

kevinzxc1217
初起 CPU 做配置時，會依照 Allocation Strategies 方式去進行 tree 的分配，後續會在依照 Reserve-on-Free 策略去分配 CPU 的 Preferred Tree，即其中一個 CPU 對同一 tree 連續進行 4 次以上的釋放時，將把該 tree 標記為該 CPU 的 Preferred tree。

Reviewed by yinghuaxia

Last Tree
用於記錄該 CPU 最近一次釋放記憶體空間的 tree，助於優化記憶體重新配置的效率。當 Preferred tree 空間不足時，會優先查找 Last tree。

此段落中提到 Last Tree 會負責記錄上一次 CPU 剛釋放的記憶體空間，若發生同時多個 CPU 的 Last Tree 記錄到同一記憶體位置的情形，此時產生的衝突該如何解決？

kevinzxc1217
每個 CPU 會透過 atomic 的操作去 reserve tree，若 CPU1 先拿走被共同記錄的 Last tree，則 CPU2 需去尋找額外的 free tree 或 partial tree 來做使用。

Reviewed by st10740

被配置的 frame 大小有分為 4 KB、2 MB 和 1 GB，請問選擇這些大小的原因是什麼呢?

kevinzxc1217
記憶體管理單位（MMU）通常是根據特定標準設計的，這些標準在不同的硬體平台之間保持一致性，以便系統能夠跨平台運行，這裡 Frame 大小的設置採用是採用 AMD64 MMU 的框架大小（4 KiB、2 MiB、1 GiB）進行討論。

任務簡介

探討高效的記憶體配置器如何設計和實作。

開發環境

$ gcc --version
gcc (Ubuntu 13.2.0-23ubuntu4) 13.2.0

$ lscpu
+Architecture:             x86_64
  CPU op-mode(s):         32-bit, 64-bit
  Address sizes:          46 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   36
  On-line CPU(s) list:    0-35
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) i9-10980XE CPU @ 3.00GHz
    CPU family:           6
    Model:                85
    Thread(s) per core:   2
    Core(s) per socket:   18
    Socket(s):            1
    Stepping:             7
    CPU(s) scaling MHz:   28%
    CPU max MHz:          4800.0000
    CPU min MHz:          1200.0000
    BogoMIPS:             6000.00

$ uname -r
6.8.0-35-generic

TODO: 閱讀論文 LLFree: Scalable and Optionally-Persistent Page-Frame Allocation 重現實驗並記錄問題

理解高效的記憶體配置器如何設計和實作。
補強對應的背景知識，回顧課程教材。
如何解決多核處理器中，allocator 會面臨大量的 lock contention 呢？
若要有更好的 scalability，就需要 lock-free 的實作

LLFree（Lock and Log–Free Pageframe allocator）

Lock-free
以系統的觀點來看，只要執行足夠長的時間，至少會有一個執行緒會有進展 (progress)。在 LLFree 配置器中，lock-free 技術被用來實現頁框配置和釋放的操作，確保在並行環境下能夠高效地管理記憶體。
Log-free
在執行某些操作時，不使用傳統的 log 來記錄狀態變更，可以減少 log 記錄和處理的開銷，透過 Atomic 操作來取代 log 記錄，可以提高系統性能。

介紹

不要濫用「具體」ㄧ詞，查閱教育部重編國語詞典「具體」的釋義：

• 大體完備
• 有實體存在，不抽象、籠統

本處就算刪去「具體」，只說「目標包括」也文意通順。使用「具體」該有明確的理由，特別是對比「籠統」和「不完備」的語境。改進你的漢語表達，才能讓溝通更有效率。

已改進，謝謝提點

LLFree 是一種新型記憶體配置器，使用 Rust 語言撰寫，目的是提高記憶體管理的安全性和效能，目標包括：

• 記憶體管理安全性：透過 Rust 語言的安全特性，LLFree 力圖避免常見的記憶體錯誤，如 buffer overflows 和使用未初始化的記憶體。
• 效能改進：設計一種高效能配置和釋放演算法，以提高整體系統的效能。
• 與 Linux 整合：探討如何將 LLFree 配置器整合到 Linux 核心中，並替換現有 Linux 內的 Buddy Allocator，評估其對負載的穩定性和效能影響。

注意用語：

• algorithm 是「演算法」，而非「算法」(the way to calculate)

務必詳閱 https://hackmd.io/@sysprog/it-vocabulary 和下方的詞彙對照表

已改進

LLFree vs Linux frame allocator

• Linux
  • 在多核系統上的擴展性較差
  • 有很高的記憶體開銷
  • Huge-frame fragmentation 問題
  • 使用 Global Lock 導致資源競爭
• LLFree
  • 提供 Lock and Log-free 配置器設計
  • 多核系統上擴展性好，記憶體佔用小
  • 較抗碎片化

策略方法

名詞解釋

提供更完整的解釋，特別是同類型詞彙和選擇之間的比較。

已更新

• Counter
  不同類型的 Counter 記錄不同結構內所含的 free frame
  • cP：CPU Preferred tree 內的 Local Counter，用來計數該 tree 內的 free frame 有多少
  • cU：Upper Level 中 Tree 內的 Global Counter，用來計數該 tree 內的 free frame 有多少
  • cL：Child 內的 Counter，用來計數該結構內的 free frame 有多少
• Tree
  區分不同類型的 tree 可以更有效地找到 CPU 所需空間
  • allocated tree：該 tree 內大多數 frame 都被佔用（cU < 12.5 %）
  • free tree：該 tree 內大多數 frame 都是空閒的（cU > 87.5 %）
  • partial tree：該 tree 內的 free frame 數量介於 allocated tree 和 free tree 之間
• Frame size
  Frame 是記憶體配置器中分配和釋放空間的基本單位，這裡分成三種不同的大小：
  • base frame： 實體記憶體切割成 4 KB 的 Block
  • huge frame： 實體記憶體切割成 2 MB 的 Block
  • giant frame： 實體記憶體切割成 1 GB 的 Block
• Frame 分割與分類
  • 分割（Segmentation）
    指的是將主記憶體分成不同大小的連續區域，每個區域都是固定大小的 Frame，讓系統能夠有效地管理和分配記憶體給不同的任務。
  • 分類（Classification）：
    指的是將記憶體中的 Frame 分類為已分配和未分配兩類，這裡是透過 bitfield 上每個 bit 顯示的 0 和 1 來表示該 Frame 為已分配或未分配。

解釋 frame 在通用的記憶體配置器和論文中的作用，特別是分割和分類的策略差異。

已完成

關鍵策略

• Lower Level - Allocation Mechanisms

  • base frame allocation：
    當需要配置一個 base frame 時，先使用 atomic 的方式對 cL 進行減少，確保了同時只有一個 CPU 可以成功地找到並配置最後一個 free frame，避免 race condition 發生。接下來，系統會在 BitFields 中搜索一個空閒的 frame ，即將值為 0 的位元設置為 1。
  • huge frame allocation：
    對於 huge frame 的配置，系統會透過 CAS 操作來將 cL 計數器從 512 減少到 0，同時將其 flag 設置為 1，表示該 bitfield 已配置為 huge frame。 配置操作僅通過改變 counter 和 flag 來完成，而不需要修改 bitfield，保持高效性和 atomic。
  • 效率和性能優化：
    cache line 最小化：配置和釋放 base frame 時，低階配置器通常僅需觸碰兩個 cache line（Child 和 BitFields）；而配置和釋放 huge frame 時，僅需改變一個 cache line（Child），這樣設計確保了操作的效率和最小的系統資源消耗。

• Upper Level - Allocation Strategies

  1. 該策略系統會搜索與當前 CPU tree 相鄰的區域，這裡定義為同一個 cache line 上的其他 31 個 tree root，找到 partial trees 則優先使用。
  2. 如果找不到 partial tree，系統接下來會再次進行搜索，這次目標是找到 free tree 或者是 allocated tee。
  3. 如果前面的步驟都沒有成功，這時系統會 unreserve 其他 CPU 已經預留但尚未使用的 tree，將這些 tree 重新配置給當前需要空間的 CPU 使用，這樣能夠更有效地利用系統中其他 CPU 的資源，以滿足當前 CPU 的記憶體配置需求。

• CPU-Local Tree Roots:
  具有多個 CPU 的系統，當某個 CPU 決定要 reserve tree 時，它會將該 tree 的 cU 移動到 Local CPU 的 cP 中，同時將對應 Globel Counter 的 cU 設置為 0。之後該 CPU 的配置和釋放操作只會影響 Local Counter 的 cP，而其他 CPU 則無法對此 Tree 再進行配置。但是，其他 CPU 先前有保留該 tree 部分 Frame 的話，仍可以對該 tree 進行釋放，這時只會增加 Globel Counter cU，而不會影響 CPU 記錄的 cP。這樣可以確保在多個 CPU 同時操作 tree 時，不會產生 False sharing 的問題。

• Reserve-on-Free:
  具有多個 CPU 的系統中，當其中一個 CPU1 對同一 tree 連續進行 4 次以上的釋放時，
  將把該 tree 標記為 CPU1 的 Preferred tree。這意味著即使後來將該 tree 被配置給了另一個 CPU2 ，或者該釋放操作是由其他 CPU3 觸發的，釋放時然優先返回到 CPU1 的 Preferred tree 中。

架構

整體架構分成 Upper Level 和 Lower Level ，其中 Uppper Level 包含 Tree ，而 Lower Level 包含 Children 和 Bit Fields。

在介紹個別欄位和程式碼之前，你該論述何以 LLFree 能解決其宣稱的問題。也就是該先介紹關鍵操作、突破手法，然後才深究細節。

好的，已調整內文順序

• LLFree 結構
  • Frame
    每個 frame (bits) 的大小為 4KB。
  • Bitfield
    每個 bitfield 大小為 512 個 frame (bits)。
    每個 bitfield 由 512 個 4KB 的 frame 組成，即 2MB。
  • Child
    每個 child 管理一個 bitfield，即 2MB。
  • Tree
    每個 tree 包含 32 個 child。
    每個 tree 由 32 個 2MB 的 child 組成，即 64MB。

使用 Bitfield 的好處是：

• 高效管理記憶體：Bitfield 用少量記憶體空間記錄每個 frame 的使用狀態。
• 快速操作：位元運算能迅速檢查和更新 frame 的狀態，加速配置和釋放操作。
• 對齊方便：記憶體區塊按照 2 的冪對齊，方便運算。
• 避免競爭：使用 CAS 的 atomic 操作，確保多核系統中的配置與釋放進行。

• CPU 內部記錄
  • Preferred Tree
    在初始化時，每個 CPU 會選擇一個 Preferred tree，當 CPU 需要配置記憶體空間時，會在自己的 Preferred tree 中進行搜尋和配置，避免多個 CPU 之間的競爭，提升配置效率。
  • Last Tree
    用於記錄該 CPU 最近一次釋放記憶體空間的 tree，助於優化記憶體重新配置的效率。當 Preferred tree 空間不足時，會優先查找 Last tree。
• Counter
  記錄該結構中剩餘可用記憶體的 frame 數量。
• Flag
  每個結構都有一個 Flag，記錄該空間是否被某個 CPU 保留，當 r = 1 時，表示該 tree 已被某個 CPU 保留，避免其他 CPU 進行存取 ，減少多 CPU 同時存取 同一 tree 時可能造成的 False Sharing 問題； r = 0 反之。

注意用語：

• access 是「存取」，而非「訪問」(visit)

務必使用本課程教材規範的術語。

typedef struct tree {
    /// Number of free frames in this tree
    treeF_t free : LLFREE_TREE_ORDER + 1;
    /// Whether this tree has been reserved
    bool reserved : 1;
    /// The kind of pages this tree contains
    uint8_t kind : 2;
} tree_t;

說明此處使用 bit field 的必要。

已補充說明

結構分析

• tree

  • free：表示該 tree 中存在尚未配置的可用 frame 數量。
  • reserved：表示該 tree 是否已被 reserve，即已被某個 CPU 鎖定。
  • kind：表示該 tree 的類型，可以是 FIXED、MOVABLE、HUGE，有助於管理配置優先權，其中 FIXED 優先順序最高， HUGE 優先順序最低。

typedef struct child {
    /// Counter for free base frames in this region
    uint16_t free : 14;
    /// Whether this has been allocated as a single huge page
    bool huge : 1;
    /// Hint for the guest that this region has been reclaimed and potentially been unmapped
    bool reclaimed : 1;
} child_t;

• child
  • free：追蹤每個 child 中可用的 frame。
  • huge：記錄該 child 是否被配置為 huge frame。
  • reclaimed：該 child 被回收時會設成 True，可被再次配置時會設成 False。

typedef struct reserved {
    /// Number of free frames in the tree
    treeF_t free : LLFREE_TREE_ORDER + 1;
    /// Bitfield row index of reserved tree,
    /// used for identifying the reserved tree and as starting point
    /// for the next allocation
    uint64_t start_row : 62 - LLFREE_TREE_ORDER;
    /// true if there is a reserved tree
    bool present : 1;
} reserved_t;

/// Counts last frees in same tree
typedef struct local_history {
    /// Index of the last tree where a frame was freed
    uint64_t idx : 48;
    /// Number of frees in the same tree
    uint16_t frees : 16;
} local_history_t;

/// This represents the local CPU data
typedef struct __attribute__((aligned(LLFREE_CACHE_SIZE))) local {
    /// Counts last frees in same tree
    _Atomic(local_history_t) last;
    /// Reserved trees
    _Atomic(reserved_t) reserved[TREE_KINDS];
} local_t;

• local
  • last
    • idx：記錄了上一個釋放 tree 的 index。
    • frees：記錄了在同 tree 中連續進行的釋放次數，有助於判斷是否需要進行 reserve。
  • reserved
    • free：記錄了 reserve Tree 中可用的 frame 數量。
    • start_row：記錄了 reserve Tree 的 index，用於識別 reseve tree 並作為下一個配置的起始點。
    • present：表示目前 CPU 是否有 reserve tree，如果有，則該欄位為 true；否則為 false。

typedef struct bitfield {
    _Atomic(uint64_t) rows[FIELD_N]
        ll_align(LLFREE_CACHE_SIZE);
} bitfield_t;

• bitfield
  • rows： 用於追蹤 frame 的配置狀態，每個 bitfield 共有 8 個 rows ，每個 rows 有 64 bits ，總共有 512 個 bits 可以記錄 512 個 frame ，當 frame 被配置時，對應的位元被設定為 1，未被配置時，對應的位元被設定為 0。
  • ll_align： 確保 bitfield 在記憶體中按照 LLFREE_CACHE_SIZE 的大小對齊。這樣做可以提高記憶體存取效率，特別是在多核處理器上，可以減少因 cache 不對齊而造成的效能損失。

typedef struct lower {
    /// number of managed frames
    size_t frames;
    /// bitfields storing the allocation states of the pages
    bitfield_t *fields;
    /// index per bitfield
    children_t *children;
} lower_t;

• lower
  • frames： 記錄被使用的 frame 數量。
  • fields： 指向 field 的指標，用於儲存 frame 的配置狀態。
  • children： 指向 child 的指標。

---

配置/釋放記憶體流程

這是剛開始的記憶體配置，64 MiB Entries 對應為 Upper Level 中的 Tree 結構，而 2 MiB Entries 對應為 Lower Level 中的 Child 結構， 512 bit 對應為 Bitfeild 結構。其中 Free Counter 記錄該結構下所剩餘的 Free Frame 數量，Bit Flag 用來追蹤哪些區塊可用於合併，1 代表可以，0 代表不行。

CPU 0 reserve 了有著 7 個 Frame 的 Tree，而 CPU 1 reserve 了有著 5 個 Frame 的 Tree，將原先 Tree 上的 Global counter 歸 0，將值自行記錄在各 CPU 的 Local counter 上，使得其他 CPU 要在借用時會因為看到 Global counter 為 0 而無法使用。

當 CPU 0 使用了 reserve 的空間，第一步會將 local counter 從 7 變成 6 ；第二步會修正 2 MiB Entries（Child）內的值，優先使用已 allocated 的 frame ，從 3 變成 2 ；第三步把對應的 512 bit（Bitfiled） 內的 0 轉成 1 。

重現實驗

指標

• benchmarks
  • bulk benchmark：所有核一次性配置一半可用記憶體，然後重複釋放。
  • random benchmark：所有記憶體以隨機順序釋放 frame
  • repeat benchmark：重複地配置和釋放 frame
• Frame size
  • base frame： 4 KB
  • huge frame： 2 MB
  • giant frame： 1 GB
• Order
  • Order 0: 表示
    $2^0$ = 1 個 frame，每個 frame 為 4 KiB，表示 4 KiB 的記憶體空間。
  • Order 1: 表示
    $2^1$ = 2 個 frame，表示 8 KiB 的記憶體空間。
    …
  • Order 9: 表示
    $2^9$ = 512 個 frame，表示 512 KiB 的記憶體空間。
  • Order 10: 表示
    $2^{10}$ = 1024 個 frame，表示 1024 KiB 的記憶體空間。

實驗

補上實驗硬體和相關實驗流程，讓其他人也可重現。

已補充說明

本實驗主要參考 llfree-bench 的效能評估程式

$ ./run.py bench alloc -m <MEM_IN_G> -c <CORES>

• 其中 alloc 可以用以下取代，用來測試不同的 Benchmark
  • alloc：在 userspace 使用 LLFree 配置器執行 bulk、rand 和 repeat 的 Benchmarks
  • list：在 userspace 使用 List 配置器執行 bulk、rand 和 repeat 的 Benchmarks
  • kernel：在 kernel space 使用 buddy 和 LLFree 配置器執行 bulk、rand 和 repeat 的 Benchmarks
  • frag：在 kernel space 使用 buddy 和 LLFree 配置器執行 frag 的 Benchmarks
• <MEM_IN_G>：填入希望測試的記憶體空間（單位：GiB）
• <CORES>：表示希望測試的核數量。

這裡主要是測試 LLFree 和 Linux Buddy allocator 的性能，在 Bulk 和 Rand 測試中，LLFree 相較於 Linux buddy allocator 速度明顯快許多，在 Repeat 測試中，即相同 frame 被反覆重新配置的情況下，由於 Linux 將 Cache 擴展到 order 1-3 和 order 9，使得 Linux buddy allocator 在特定大小的記憶體配置釋放上比 LLFree 速度更快。

這裡是測試 LLFree 在不同核數量上的速度比較，在 Bulk 和 Repeat 的 userspace 基準測試中，我們可以觀察到 LLFree 的操作時間幾乎保持不變，不受核數量影響，是因為 LLFree 的配置和釋放有了 reservation 系統，而減少了大多數的共享所需花費的時間。
只有在 Rand 測試時，由於 Cache 失效和 child counters 的更新頻繁，我們才會看到越多核的影響速度越慢。但這裡即使有 8 個並行請求 frame 的核， 最多時間花費也不到 170 ns。

這裡是測試 LLFree 不同 Order 數量時的速度比較，在 Bulk 和 Repeat 測試時，每個操作的時間都少於 100 ns；而 Random 操作成本較高，因為會發生 cache-miss 和 cache invalidations 而最高需要 190 ns。

這裡不清楚為什麼 Order8 相較於 Order9 和 Order10 花費更多的時間?

這個實驗是你做的嗎？如何解讀？
倘若你只是作論文的「懶人包」，卻沒有重現實驗、指出裡頭的錯誤和不足，那我們直接用 AI 工具來摘錄就好，不是嗎？人就該做到 AI 做不到的事！

好的沒問題，論文上該實驗共比較 26 核，這裡是我重現實驗共使用了 9 核，目前也在嘗試使用其他方法呈現效能評估中。

這裡測試了三種 List-based 配置器和 LLFree 配置器做比較，並評估其性能：

注意用語！

已改進

• ListLocked：當多個 CPU 同時存取 singly-linked list 時（如 Windows 和 Darwin），他們必須彼此競爭資源不能同時存取，而因為高強度的 lock 競爭，效能表現最差。
• ListCAS：使用 lock-free 的 LIFO 列表，將 lock 替換為 CAS 的 atomic 操作，在多核系統上，性能比 ListLocked 要好。
• ListLocal：僅維護每個核的 local 資源，不需要任何保護機制來防止 Race Condition 的發生（理想情況）。但即使是理想情況下，也在 9 核的 Bulk 測試中比 LLFree 慢些。
• LLFree 在多核系統上的性能優於 ListLocked 和 ListCAS，LLFree 使用 bitmap 來管理記憶體配置，相比之下基於鏈節的設計，由於鏈結特性導致較多的 cache misses ，所以速度較慢。

這裡我使用了 9 核（可自訂）進行比較，在 Bulk 測試中，隨著更多核的測試，LLFree 花費時間皆和論文呈現相同的平緩成長，而 ListCAS 呈現明顯的向上趨勢。論文使用 26 核進行實驗，在 20 核以後 ListCAS 更是明顯的超過 LLFree 所花費的時間。

對比論文和你重現的實驗，解說其中異同處。

已補充說明

TODO: 理解 llfree-c 內建測試程式的作用

分類解釋 (有可能會遇到編譯/執行的錯誤，善用 GitHub 提交 issue / pull request)
llfree-c/tests 該測試程式主要是測試 llfree-c/src 內的所有函式功能是否正確，使用 declare_test 去進行測試，每個函式測試內部都分成 actual 和 expect ，來判斷 actual 經過指定函式後，產生出來的值是否和 expect 相同。

...
tests/test.c:65: alloc a=64 1280
Running test 'atomicity'
Running test 'tree_atomic'
Running test 'tree_init'
Running test 'tree_reserve'
Running test 'tree_unreserve'
Running test 'tree_inc'
Running test 'for_offsetted'
----------------SUCCESS----------------

若測試程式成功運行，會如上呈現。

bitfield test

注意書寫規範：

• 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致，也就是偏好 4 個空白字元，而非 tab。

已更正

declare_test(bitfield_set_bit)
{
    bool success = true;

    actual = bf(0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0);
    expected = bf(0x3, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0);

    ret = field_set_next(&actual, 0, 0);
    check_equal("lu", ret.frame, 1lu);
    check_equal_bitfield(actual, expected);

    return success;
}

這裡主要是測試 field_set_next 是否正常運作，field_set_next 該函式功能為設置 bitfield 中第一個為 0 的 bit 轉為 1，用來配置原本空閒的 frame 做使用，可以看到測試程式原先 bf（bitfield）記錄的是 0x1…，經過 field_set_next 函式後將原本 0x1 的下個 0 改為 1 ，則變成 0x3…，由此可見函式的正確性。

注意書寫規範：

• 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致，也就是偏好 4 個空白字元，而非 tab。

已更正

declare_test(bitfield_reset_bit)
{
    bool success = true;

    actual = bf(0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0);
    expect = bf(0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0);
    pos = 0;

    ret = field_toggle(&actual, pos, 0, true);
    check_equal("lu", ret.frame, 0lu);
    check_equal_bitfield_m(actual, expect, "first one should be set to 0");


    return success;
}

field_toggle 將位元欄位中指定位置的位元值進行翻轉，其中 &actual 為指向 bitfield 的指標； pos 為該 bitfield 上的指定位置； 0 這裡的數字表示

$2^0$ ，看需要連續多少位元進行翻轉；true 這裡表示要配置或釋放 frame ， true 為配置指定 frame ，即位元從 1 變 0， 而 false 為釋出指定 frame ，即位元從 0 變 1。由此測試程式可以看到 actual 內的 bf 其 0x1 經過 field_toggle 函式後有成功翻轉成 0x0。

注意書寫規範：

• 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致，也就是偏好 4 個空白字元，而非 tab。

已更正

declare_test(bitfield_count_bits)
{
    bool success = true;

    bitfield_t actual = bf(0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0);
    bitfield_t expect = bf(0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0);

    size_t ret = field_count_ones(&actual);
    check_equal_m("zu", ret, 0lu, "no bits set");
    check_equal_bitfield_m(actual, expect, "no change!");

    actual = bf(0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x8000000000000000);
    expect = bf(0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x8000000000000000);

    ret = field_count_ones(&actual);
    check_equal_m("zu", ret, 2lu, "first and last bit set");
    check_equal_bitfield_m(actual, expect, "no change!");

    return success;
}

field_count_ones 用於計算 bitfield 中值為 1 的位元數量，第一次測試 actual 經過函式應該要回傳 0，透過 check_equal_m 來判斷 ret 是否為 0；第二次測試 actual 經過函式應該要回傳 2 ，同樣也檢查 ret 是否為 2。主要測試了計算結果是否正確以及位元經過函式後是否有被修改。

child test

注意書寫規範：

• 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致，也就是偏好 4 個空白字元，而非 tab。

已更正

declare_test(child_counter_inc)
{
    bool success = true;
    bool ret = false;

    child_t actual = child_new(0x200, true, false);
    ret = child_inc(&actual, 0);
    check_m(!ret, "out of range");

    actual = child_new(5, false, false);
    child_t expect = child_new(6, false, false);
    ret = child_inc(&actual, 0);
    check(ret);

    check_equal("u", actual.free, expect.free);
    check_equal("u", actual.huge, expect.huge);
    
    ...

    return success;
}

這段程式主要是去測試 child_inc 該函式是否正確執行，第一次建立大小為 0x200 的 actual ，由於是 huge 型態，所以無法新增空閒 frame 。第二次建立大小為 5 的 actual ，由於沒有超出最大限制且非 huge 型態，所以經過 child_inc 函式後有成功新增一個 frame ，變成 6 。

declare_test(child_counter_dec)
{
    bool success = true;
    bool ret = false;

    child_t actual = child_new(0, false, false);
    ret = child_dec(&actual, 0, false);
    check_m(!ret, "out of range");
    ...
    return success;
}

這裡類似前述 child_counter_inc 函式的操作，不過是相反的，這裡是減少指定 frame 數量，可以看到原本建立的 actual 為 0 個 frame，所以經過 child_dec 函式後會回傳 false ，因 0 本身是最小值了，無法再減少。

llfree test

declare_test(llfree_init)
{
    bool success = true;

    lldrop llfree_t upper = llfree_new(4, 1 << 20, LLFREE_INIT_FREE);
    check(llfree_frames(&upper) == 1 << 20);
    check(llfree_free_frames(&upper) == 1 << 20);

    llfree_validate(&upper);

    return success;
}

注意用語：

• (OS) kernel 是「核心」
• (processor) core 是「核」

二者的語境不同。

已更正

這裡是測試 llfree_init 函式是否有成功初始化，llfree_new 建立一個 1 GiB 的 frame 和 4 核 CPU，透過 llfree_frames 計算建立的 upper 內是否為 1 MiB，以及透過 llfree_free_frames 計算空閒的 frame 是否為 1 MiB，最後再使用 llfree_validate 函式進行驗證整體是否正確。
其中值得注意的是當 llfree_new 最後傳入的參數為 LLFREE_INIT_FREE 表示建立 frame 皆為空閒的，若是 LLFREE_INIT_ALLOC 則表示建立的 frame 皆為被使用的。

declare_test(llfree_init_alloc)
{
    bool success = true;

    const size_t FRAMES = (1 << 30) / LLFREE_FRAME_SIZE;

    lldrop llfree_t upper = llfree_new(4, FRAMES, LLFREE_INIT_ALLOC);
    check(llfree_frames(&upper) == FRAMES);
    check(llfree_free_frames(&upper) == 0);

    for (size_t hp = 0; hp < (FRAMES >> LLFREE_HUGE_ORDER) - 1; hp++) {
        check(llfree_is_ok(llfree_put(&upper, 0,
                          hp << LLFREE_HUGE_ORDER,
                          llflags(LLFREE_HUGE_ORDER))));
    }
    for (size_t page = FRAMES - (1 << LLFREE_HUGE_ORDER); page < FRAMES;
         page++) {
        check(llfree_is_ok(llfree_put(&upper, 0, page, llflags(0))));
    }
    check(llfree_free_frames(&upper) == FRAMES);

    llflags_t llf = llflags(0);
    llf.movable = true;
    check(llfree_is_ok(llfree_get(&upper, 0, llf)));
    check(llfree_is_ok(llfree_get(&upper, 0, llflags(0))));
    check(llfree_is_ok(llfree_get(&upper, 0, llf)));

    llfree_validate(&upper);

    return success;
}

首先 llfree_new 建立一個 1 GiB 的 frame 和 4 核 CPU，由於建立時是使用 LLFREE_INIT_ALLOC 當作參數，表示會將所有建立的 frame 當作已被配置。再透過 llfree_frames 以及 llfree_free_frames 來檢查是否有正確的 frames 和 free_frames 數量， 並且分別測試大型記憶體區塊和小型記憶體區塊使用 llfree_put 和 llfree_get 函式時功能是否正常，llfree_put 用於將 frame 釋放為空閒，而 llfree_get 用於配置空閒中的 frame。

test lower

declare_test(lower_get)
{
    bool success = true;
    llfree_result_t ret;

    size_t frames = 1360;
    lower_t actual = lower_new(frames, LLFREE_INIT_FREE);

    size_t order = 0;

    ret = lower_get(&actual, 0, order);
    check_equal("lu", ret.frame, 0lu);
    check_equal_bitfield(
        actual.fields[0],
        ((bitfield_t){ { 0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0 } }));
    return success;
}

建立一個 lower 型態的 actual，再透過 lower_get 函式去配置一個空閒的 frame 給它，若該函式運行正確，其返回的 ret 應會將指定位址的 frame 拿去使用，即對應位元的 0 變成 1。這裡一開始建立的是全部空閒的 frame，經過 lower_get 後會將首個位元設置為 1，透過heck_equal_bitfield 函式比較後可以發現結果如預期。

tree test

declare_test(tree_reserve)
{
    int success = true;
    bool ret = false;

    tree_t actual = tree_new(764, false, TREE_FIXED);
    tree_t expect = tree_new(0, true, TREE_FIXED);

    ret = tree_reserve(&actual, 0, (1 << LLFREE_TREE_ORDER), TREE_FIXED);
    check(ret);
    equal_trees(actual, expect);

    return success;
}

建立一個 counter 為 764 的 tree，經過 tree_reserve 後，由於該 tree 上的 frame 都被保留了，所以 counter 會變為 0，且回傳 true。搭配 assert，可以從程式執行過程中判斷是否符合預期，若有錯誤，則產生錯誤資訊。

TODO: 比較其他的實作

依據論文 LLFree: Scalable and Optionally-Persistent Page-Frame Allocation 的陳述，嘗試比較上述實作和其他記憶體配置器的表現。
這裡比較 LLFree 和 TLSF 的實作，並說明 TLSF 的做法是什麼，也可以參考去年 Linux 核心專題: TLSF 實作 有詳細的介紹。

TLSF

TLSF（Two-Level Segregated Fit）是一個高效的動態記憶體配置器，專為即時系統設計。它的主要目標是提供時間複雜度（O(1)）的配置和釋放操作，同時將記憶體碎片最小化。

• First level
  依 2 的冪分類記憶體區塊，以上圖為例第一個區塊記錄的記憶體可用範圍為
  $[2^4,2^5)$ 即 16 Byte ~ 31 Byte，第二個區塊
  的記憶體可用範圍為
  $[2^5,2^6)$，即 32 Byte ~ 63 Byte 等等。
• Second level
  將 First level 內的每個區塊分成四等份，舉例來說
  $[2^4,2^5)$ 會被切成
  $[16,20)$,
  $[20,24)$,
  $[24,28)$,
  $[28,32)$。
• Free List
  鏈結串列結構，其中每個節點表示一個空閒的記憶體區塊，每個節點包含一個指向下一個空閒區塊的指標，用於記錄較大的記憶體空間。
• Bitmap Index
  其中每個位元表示記憶體中的一個固定大小的區塊，位元的值（0 或 1）表示該區塊是空閒的還是已使用，用於記錄較小的記憶體空間。

比較

結構

• TLSF：採用兩級分段機制。一級分段依冪次分類記憶體區塊，二級分段在一級分段內進一步細分。
• LLFree：採用樹狀結構。每個 tree 包含多個 children，每個 children 對應一個 512 位元的 bitfield 來管理記憶體區塊的配置和釋放。

記憶體配置

• TLSF：Bitmap Index 負責記錄較小且統一的記憶體空間，list free 負責記錄較大的記憶體空間。
• LLFree：分成 base frame 和 huge frame ，其中每個 base frame 為 4KB， huge frame 為 2MB。

策略方法

• TLSF
  1. Segregated Fit：TLSF 將記憶體區域分為多個固定大小的分區（classes），每個分區管理特定大小範圍的記憶體區塊。每個分區內部使用 doubly linked list 來管理空閒的記憶體區塊，這些鏈表會根據記憶體區塊的大小分類，以便快速找到適合大小的空閒區塊。
  2. Quick Merge：TLSF 通常會採用快速合併策略來減少記憶體碎片化，當一個空閒區塊鄰接另一個空閒區塊時，TLSF 可以快速將它們合併為一個更大的區塊，以提供更大的連續空間。
  3. 高效搜尋和配置：TLSF 使用分區和鏈結串列來實現快速的空閒塊搜尋和配置，當需要配置一個記憶體塊時，TLSF 可以快速定位到適合大小的空閒塊，而無需從頭遍歷整個記憶體。
  4. 動態調整 classes 大小：TLSF 允許根據應用程序的需求動態調整每個分區的大小範圍，使得 TLSF 在面對不同大小的記憶體配置需求時能夠有效地進行優化。
• LLFree
  1. CPU-Local Tree Roots：LLFree 允許每個 CPU 固定一個 Preferred tree，用於管理 Local CPU 的記憶體配置和釋放，這樣做可以減少跨 CPU 之間的記憶體共享問題，從而提升整體效能。
  2. Reserve-on-Free：當一個 CPU reserve 了 tree 來進行記憶體配置時，它會將 Global Counter 設置為零，這樣其他 CPU 就無法配置這個 tree 的空間。這種策略確保了在多 CPU 系統中配置操作的 atomic 和效率。
  3. Lower Level：在 base frame 配置時，透過 atomic 操作減少計數器 cL。huge frame 配置則使用 CAS 操作將 cL 從 512 減至 0，同時設置 flag 為 1，表示該 bitfield 已配置為 huge frame。
  4. Upper Leve：配置策略優先搜索當前 CPU tree 相鄰的 partial trees，若無則搜索 free 或 allocated trees。若仍無法滿足需求，則會 unreserve 其他 CPU 預留但未使用的 trees，重新配置以滿足需求。

主要應用

• TLSF
  1. 即時系統：TLSF 的兩級分段和自由列表結構使得它能夠快速找到合適大小的記憶體區塊，適合於即時系統中對記憶體配置時間有嚴格要求的應用。
  2. 嵌入式系統：TLSF 能夠有效地管理有限的記憶體資源，並減少碎片化，使得它在嵌入式系統中經常被拿來使用。
• LLFree
  1. 多核系統：LLFree 透過使用樹狀結構來管理記憶體，可以避免多核 CPU 之間的競爭，提高系統的整體效能。

限制

• TLSF
  1. 占用記憶體：需要維護 Bitmap 和 List Free，以及額外空間去追蹤記錄體記憶體配置狀態和位置。
  2. 碎片問題：由於 TLSF 將記憶體區塊對齊到固定大小的分區上，在處理大小變化較大的記憶體請求時，可能會導致內部碎片化發生。
  3. 不支持多核心並行：在多核心環境中使用時，需要額外的同步機制來避免競爭。
• LLFree
  1. 初始記憶體配置
     LLFree 配置器需要初始化其內部結構，包括設置初始值、建立 tree 、 child 和 bitfield 等資料結構，這些操作都需要大量的時間和記憶體空間。
  2. reserve 記憶體空間
     為了避免在記憶體配置過程中發生競爭，LLFree 配置器在初始化時會 reserve 一部分記憶體區塊，也增加了初始化時的成本。

總結

LLFree 和 TLSF 都是高效的記憶體配置器，它們都透過分級管理來實現快速配置和釋放操作，但在資料結構、應對策略上有著不同的方法，選擇哪種記憶體配置器，取決於具體應用和系統需求，也要考量其限制。

上述總結過於武斷，且沒有闡述 TLSF 的限制，特別是其實作手法。
LLFree 也有限制，例如其初始化的成本，應予以探討。

已更正