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

contributed by < kevinzxc1217 >

解說影片

TODO:高效記憶體配置器: 閱讀論文 "LLFree: Scalable and Optionally-Persistent Page-Frame Allocation" ( https://github.com/luhsra/llfree-c ) 重現實驗並紀錄問題

搭配: https://hackmd.io/@sysprog/c-function (malloc/free 本質上就是 heap 的管理器)
要解決的問題是多核處理器中，allocator 會面臨大量的 lock contention，若要有更好的 scalability，就需要 lock-free 的實作
https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-lockfree : lock-free 指 只要執行足夠長的時間，至少會有一個執行緒會有進展 (progress)

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，評估其對負載的穩定性和效能影響。

LLFREE vs Linux frame allocator

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

---

架構

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

• 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。
• Counter
  記錄該結構中剩餘可用記憶體的 frame 數量。
• Flag
  每個結構都有一個 Flag，紀錄該空間是否被某個 CPU 保留，當 r = 1 時，表示該 tree 已被某個 CPU 保留，避免其他 CPU 進行訪問，減少多 CPU 同時訪問同一 tree 時可能造成的 False Sharing 問題； r = 0 反之。
• Preferred Tree
  在初始化時，每個 CPU 會選擇一個 Preferred tree，當 CPU 需要分配記憶體空間時，會在自己的 Preferred tree 中進行搜尋和分配，避免多個 CPU 之間的競爭，提升分配效率。
• Last Tree
  用於記錄該 CPU 最近一次釋放記憶體空間的 tree，助於優化記憶體重新分配的效率。當 Preferred tree 空間不足時，會優先查找 Last tree。
• Frame size
  • base frame： 實體記憶體切割成 4 KB 的 Block
  • huge frame： 實體記憶體切割成 2 MB 的 Block
  • giant frame： 實體記憶體切割成 1 GB 的 Block

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;

• 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 的指標。

---

策略方法

名詞解釋

allocated tree：大多數 frame 都被佔用（cU < 12.5 %）
free tree：大多數 frame 都是空閒的（cU > 87.5 %）
partial tree：介於兩者之間
cP：CPU Preferred tree 內的 Local Counter
cU：Upper Level 中 Trees 內的 Global Counter

策略

• 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 次以上的釋放時，LLFREE 將把該 tree 標記為 CPU1 的 Preferred tree。這意味著即使後來將該 tree 被分配給了另一個 CPU2 ，或者該釋放操作是由其他 CPU3 觸發的，釋放時然優先返回到 CPU1 的 Preferred tree 中。

---

分配/釋放記憶體流程

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

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

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

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

這裡測試了三種 List 的配置器並評估其性能：

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

TODO:理解 https://github.com/luhsra/llfree-c 內建測試程式的目的，並分類解釋 (有可能會遇到編譯/執行的錯誤，善用 GitHub 提交 issue / pull request)

llfree-c/tests 該測試程式主要是測試 llfree-c/src 內的所有函式功能是否正確，使用 declare_test 去進行測試，每個函式測試內部都分成 actual 和 expect ，來判斷 actual 經過指定函式後，產生出來的值是否和 expect 相同。

bitfield test

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…，由此可見函式的正確性。

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。

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

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;
}

這裡是測試 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 和 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 能夠有效地管理有限的記憶體資源，並減少碎片化，使得它在嵌入式系統中經常被拿來使用。
  3. 高效能要求：TLSF 通過其分區和鏈表結構，能夠快速進行記憶體塊的分配和釋放，並且具有較低的記憶體碎片化，使得它特別適合於需要高效能和低延遲的應用中。
• LLFREE
  1. 多核系統：LLFREE 透過使用樹狀結構來管理記憶體，可以避免多核 CPU 之間的競爭，提高系統的整體效能。
  2. False sharing：LLFREE 的每個 CPU 固定一個 Preferred tree，這樣每個 CPU 對其 tree 的分配釋放操作局部化，減少了 False sharing 的問題發生。

總結
LLFREE 和 TLSF 都是高效的記憶體配置器，它們都透過分級管理來實現快速分配和釋放操作，並儘量減少記憶體碎片。但它們在資料結構、應對策略上有著不同的方法。
選擇哪種記憶體配置器，取決於具體應用和系統需求。如果需要在多核心系統中高效管理內存，LLFREE　的設計更有優勢；而對於即時系統，TLSF　也是一個成熟且高效的選擇。