# Linux 核心專題: TLSF 實作
> 執行人: cin-cout
> [專題解說錄影](https://youtu.be/FirarrsHwrg)
> GitHub:
> * [cin-cout/tlsf-bsd](https://github.com/cin-cout/tlsf-bsd)
> * [cin-cout/allocator_benchmark](https://github.com/cin-cout/allocator_benchmark)
## 任務簡述
重做[第 6 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz6)的測驗四，搭配第 5 週教材提及的 [tlsf-bsd](https://github.com/jserv/tlsf-bsd)，探討何以 $O(1)$ 時間複雜度可落實於記憶體配置器。
## 背景知識
建議把老師上課影片看完，要自己理解對齊以及 overhead 等實作其實蠻沒有效率的，原本嘗試自己理解看得我一頭霧水，浪費了不少時間。
[你所不知道的 C 語言：記憶體管理、對齊及硬體特性篇](https://hackmd.io/@sysprog/c-memory)
測驗五的第一題是一個基本的 first fit 記憶體配置器的實作，先理解完畢有助於更加了解記憶體配置器的程式，但第一題的程式碼存在不少問題。
[2023q1 第 5 週測驗題 - 第一題](https://hackmd.io/@sysprog/linux2023-quiz5)
以下是解釋非常不錯的同學們的開發紀錄：
[yanjiew](https://hackmd.io/@yanjiew/linux2023q1-quiz5)
[ItisCaleb](https://hackmd.io/@ItisCaleb/linux2023q1-quiz5)
[WangHanChi](https://hackmd.io/@wanghanchi/linux2023-quiz5#%E6%B8%AC%E9%A9%97%E4%B8%80)
## TODO:
1. 研讀教材並紀錄認知及問題
至少要涵蓋:
* [TLSF: a new dynamic memory allocator for real-time systems](http://www.gii.upv.es/tlsf/files/ecrts04_tlsf.pdf)
* [Benchmarking Malloc with Doom 3](https://www.forrestthewoods.com/blog/benchmarking-malloc-with-doom3/)
* TLSF: [Part 1: Background](https://brnz.org/hbr/?p=1735), [Part 2: The floating point](https://brnz.org/hbr/?p=1744)
2. 解讀和改進程式碼
重做[第 6 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz6)的測驗四，搭配上述來解釋何以 $O(1)$ 時間複雜度可落實於記憶體配置器，又如何改進實作。
3. Linux 核心一度具備同為 $O(1)$ 時間複雜度的 [xvmalloc](https://github.com/torvalds/linux/commit/644bf7b5983cf2540b57a5b25b775cb3c1e8e943)，不過隨後就被 [zsmalloc](https://www.kernel.org/doc/html/v5.0/vm/zsmalloc.html) 取代，請依據 git log 和 LWN 等第一手材料，探討核心開發者的考量因素。
在討論時，避免「舉燭」，應至少將 [xvmalloc](https://github.com/torvalds/linux/commit/644bf7b5983cf2540b57a5b25b775cb3c1e8e943) 移植到 userspace，搭配 [tlsf-bsd](https://github.com/jserv/tlsf-bsd) 的測試和效能評比框架，分析其效益。
## 研讀 [Benchmarking Malloc with Doom 3](https://www.forrestthewoods.com/blog/benchmarking-malloc-with-doom3/)
該文講解怎麼實作偵測 alloc time 的方式，並在自行開發的遊戲上比較不同 alloc 方法的效能差距，最後再特別討論 alloc 對於聲音的 latency 之影響。
在了解 tlsf 實作前，先了解不同 alloc 方法的效能差距。
比較幾種常用的記憶體配置器：
* crt: 全名 C Runtime，是 Windows 內建的記憶體配置器。
* rpmalloc: 由 Epic Games 員工開發出的 lock-free GPA (Global Page Allocator)。
* tlsf: 著名的 pool allocator，需要 pre-allcating pool 且只支援 single-threaded。
### alloc
<div style="display: flex;">
<img src="https://hackmd.io/_uploads/r1UFugCrn.png" width="50%" height="50%">
<img src="https://hackmd.io/_uploads/rJ5tdeRrh.png" width="50%" height="50%">
<img src="https://hackmd.io/_uploads/rJgcugCS2.png" width="50%" height="50%">
</div>
### free
<div style="display: flex;">
<img src="https://hackmd.io/_uploads/HyP6cxCrh.pn" width="50%" height="50%">
<img src="https://hackmd.io/_uploads/r1jAqgAB2.png" width="50%" height="50%">
<img src="https://hackmd.io/_uploads/HJBesl0B2.png" width="50%" height="50%">
</div>
可以看到無論在 alloc 或是 free 的部分，crt 相比於 rpmalloc 和 tlsf 的平均時間都還要大，而在 size 較大時花費的時間也遠大於 rpmalloc 和 tlsf 。而 rpmalloc 的大部分資料的平均時間比 tlsf 來的小，但是在 size 較大時 (worst case) 表現卻遠不如 tlsf，在 worst case 中， tlsf 的表現相當亮眼。
rpmalloc 的 lock-free 可以減少執行緒之間的競爭，提高多執行緒環境下的性能表現，所以在現代強調多處理器、平行運算的計算機領域非常受歡迎。而 tlsf 雖然需要 pre-allcating pool 且只支援 single-threaded，但是也因為這些限制，在 worst case 中表現亮眼，對於一些精確度要求高、需要即時反應、且硬體規格較簡單(單核)的系統中， tlsf 非常合適。
## TLSF 架構
### mapping 技術
TLSF 跟最基本的記憶體配置器不同，使用一個 free list 串接所有的 free block ，詳見[測驗五第一題](https://hackmd.io/@sysprog/linux2023-quiz5)，而是依照 free block 的大小，將每堆類似大小的 free block 建立一個 free list。所以每次在 alloc 一個新的空間時，都直接去最適合的大小的 free list 中尋找 free block，從而實現 good fit，而 **mapping 技術就是用來尋找最適合的 free list**。
TLSF (Two-Level Segregated Fit) 中使用二級的結構，加快記憶體存取速度並減少記憶體碎片化 (fragmentation)。
:::warning
a power of 2 的翻譯是「2 的冪」，不用加「次方」
:::
* 第一級：將記憶體劃分為 2 的冪大小的類別。例如，若第一級為 $2^6$，則將記憶體的範圍劃分為 $[2^6, 2^7)$。
* 第二級：將第一級所表示的範圍再劃分為 4 個等距離的區塊，從而善用記憶體空間
舉例來說，假設第一級為 $2^6$，表示記憶體的大小範圍為 $[64, 128)$。第二級會將這個範圍劃分為四個大小相等的區塊，每個區塊的大小為 16。這樣，第二級會將記憶體的大小範圍細分為 $[64, 80)$, $[80, 96)$, $[96, 112)$, $[112, 128)$。
> 注意： 這邊的意思不是用 fl 與 sl 將記憶體分 block ，它的意義是每一層 fl sl 都會儲存一個 free list，我們找到合適的 fl sl 是為了找大小最合適的 free list。
舉例：我們要 alloc 一個 size 為 $2^6 + 17$ 的空間，我們這邊先不加入提級層級的概念，後面會提到。mapping 會找到 fl sl (圖中 fl=2 sl=2)對應在 $2^6 + 17$ 的位置所記錄的 free list ，從這個 free list 中找 free block 分配空間。
<img src="https://hackmd.io/_uploads/HkgY6d1I3.png" width="70%" height="70%">
:::warning
注意用語，參見:
* [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
* [詞彙對照表](https://hackmd.io/@l10n-tw/glossaries)
:::
### 整體概念
這邊畫一張圖來講解運作中的 tlsf 可能會長怎樣，以便後續再講解程式碼時比較知道狀況。
```
+------------+
|其他管理TLSL | second level
|的參數 | / \
+------------+---------------------------> +-----------+ +-----------+ \
| block[][] | | fl 0 sl 3 | | fl 0 sl 0 |
+------------+----+(free list a)<---------- |對應大小 a~b| ... |對應大小 w~x| first
| free block |----|--+ +-----------+ +-----------+ level
| (size a~b) | | | .
+------------+ | | .
| blockA | | | .
+------------+----|--|----+(free list b)<-- +-----------+ +-----------+
| free block |<---|--|----|--+ |fl 32 sl 3 | |fl 32 sl 0 |
| (size c~d) | | | | | |對應大小 c~d| ... |對應大小 y~z|
+------------+ | | | | +-----------+ +-----------+ /
| blockB | | | | |
| | | | | |
+------------+<---|--|----+ |
| free block |----|--|-------+
| (size c~d) | | |
+------------+ | |
| blockC | | |
+------------+<---| |
| free block |-------+
| (size a~b) |
+------------+
```
## [TLSF](https://github.com/jserv/tlsf-bsd) 實作解析
以下將解析老師實作的 [jserv/tlsf](https://github.com/jserv/tlsf-bsd) 。
### 重要常數
64 位元系統對齊的 shift 為 3，亦即以 8 的倍數對齊，符合一個 word_size 大小。
32 位元系統對齊的 shift 為 2，亦即以 4 的倍數對齊，符合一個 word_size 大小。
```c
/* All allocation sizes and addresses are aligned. */
#define ALIGN_SIZE ((size_t) 1 << ALIGN_SHIFT)
#if __SIZE_WIDTH__ == 64
#define ALIGN_SHIFT 3
#else
#define ALIGN_SHIFT 2
#endif
```
```c
/* First level (FL) and second level (SL) counts */
/*表示使用 4 位元來表示 SL 索引的位移量。這意味著 SL 索引的範圍為 0 到 15。*/
/*通常這個值設定在 4 或 5 。*/
#define SL_SHIFT 4
/*每一層 FL 的 SL 數量*/
#define SL_COUNT (1U << SL_SHIFT)
/*FL 最大的 index ，與系統為 64 或 32 有關。*/
/*可以增加其大小，以來處理更大的記憶體配置。*/
#define FL_MAX _TLSF_FL_MAX
/*FL[1] 的位置，詳細解釋見下。*/
#define FL_SHIFT (SL_SHIFT + ALIGN_SHIFT)
/*FL 的數量，詳細解釋見下。*/
#define FL_COUNT (FL_MAX - FL_SHIFT + 1)
```
**以下以 32 位元的系統舉例：**
雖然最多可以支持 (1 << FL_INDEX_MAX) 位元的大小分配。 但是，因為要以 4 為倍數對齊，所以小於 `SL_INDEX_COUNT * 4` 的大小建立一級列表沒有意義 (根本無法劃分出足夠數量且又滿足對齊的 SL )。
`SL_INDEX_COUNT * 4` = `(1 << (SL_INDEX_COUNT_LOG2 + 2 ))`
= `(1 << (SL_INDEX_COUNT_LOG2 + 2 ))` = `(1 << (SL_INDEX_COUNT_LOG2 + ALIGN_SHIFT ))`
所以 FL_SHIFT = SL_SHIFT + ALIGN_SHIFT。
圖例：
```
以 ALIGN_SHIFT 為 2 ，SL_SHIFT 為 4 舉例。
┌─────────────────────┬─────────────┬──────────┬──────┐
│ ... | 256~128 | 64~128 | 0~64 |
└─────────────────────┴─────────────┴──────────┴──────┘
f[2] f[1] f[0]
若無此機制，f[0] 只會為 0~1，f[1] 為 1~2。
```
所以 FL_COUNT 的演算法為 FL_MAX - FL_SHIFT + 1，因為要扣掉前面 SHIFT (0~64) 的位元已經整合為 FL[0]， 加 1 則是把加上 FL[0]。
而由於 SHIFT (0~64) 的位元已經整合為 FL[0]，FL[0] 區段不能適用於通用的演算法，所以需要 alloc 在 FL[0] 要額外定義，在這個例子中，<64 bytes ，我們定義為 BLOCK_SIZE_SMALL ，小於 BLOCK_SIZE_SMALL 的大小，我們會直接 alloc 在 FL[0]。
```c
#define BLOCK_SIZE_SMALL ((size_t) 1 << FL_SHIFT)
```
### block 資料結構
先看 block 資料結構會比較理解前面一些關於 block 的常數。
#### block 的資料結構定義
這邊是對於記憶體配置器的概念的基本解釋，詳見[測驗五第一題](https://hackmd.io/@sysprog/linux2023-quiz5)，先不考慮 prev。
此段解釋參考 [yanjiew](https://hackmd.io/@yanjiew/linux2023q1-quiz5)。
alloc 的空間為系統由 size 和 payload 組成。malloc 會回傳 payload 部份的指標。payload 為可以利用的空間，size 的值即為 payload 的大小。
```
--------------------------------------------------
| size | payload |
--------------------------------------------------
```
未配置的空間除了 size 外，後面還會接續 prev 和 next 二個指標，分別指向上一個和下一個未配置空間，size 的值即為 prev + next + 空閒位置的大小。
```
--------------------------------------------------
| size | prev | next | .......... |
--------------------------------------------------
```
上述二種狀態都可用 tlsf_block 結構來表示。size 為已配置和未配置空間都會使用的欄位，而 prev 和 next 只會在未配置空間使用。
```c
typedef struct tlsf_block {
/* Points to the previous block.
* This field is only valid if the previous block is free and is actually
* stored at the end of the previous block.
*/
struct tlsf_block *prev;
/* Size and block bits */
size_t header;
/* Next and previous free blocks.
* These fields are only valid if the corresponding block is free.
*/
struct tlsf_block *next_free, *prev_free;
} tlsf_block_t;
```
跟一般記憶體配置器最大的差別在多了 prev 這個指標，用來指向實體上的前一個 block，但他的儲存位置很特別，見下圖，取自 [esp-idf 的記憶體管理: TLSF 演算法](https://blog.csdn.net/gzxb1995/article/details/124504705)。
<img src="https://hackmd.io/_uploads/ByoT05SI3.png" width="50%" height="50%">
這裡的 `prev_phys_block` 就是 prev，block 是可以找到 prev 的，但其實 prev 是儲存在實體上一個 block 內，當上一個 block 被 alloc 後寫入資料，是可能蓋掉 prev 的，因為 prev 只是作為未被配置的記憶體合併時使用。而空閒 tlsf_block 的 size 指的是 next_free + prev_free + 空的位置 + prev(實體上下一個 block 的 prev)。
再回來看上面的常數設定。
```c
/*一個 ptr 的大小。*/
#define BLOCK_OVERHEAD (sizeof(size_t))
/*一個 block 必須足夠大以存儲其標頭減去 prev 的大小(儲存在上一個 block)。*/
#define BLOCK_SIZE_MIN (sizeof(tlsf_block_t) - sizeof(tlsf_block_t *))
/*不能大於 FL_INDEX 的可尋找的最大位數*/
#define BLOCK_SIZE_MAX ((size_t) 1 << (FL_MAX - 1))
/*見上段*/
#define BLOCK_SIZE_SMALL ((size_t) 1 << FL_SHIFT)
```
最後如同[測驗三](https://hackmd.io/@IFhfI6MRSZSja7n1T2-DNg/quiz3)，因為現在電腦多數都是 32 bits (4 bytes) 以上，所以其位置二進位最後二位必為 0，不會使用到，所以 `block->header` 的第一個 bit 用來儲存目前的 block 是否為 free，第二個 bit 用來儲存前一個的 block 是否為 free。
```c
#define BLOCK_BIT_FREE ((size_t) 1)
#define BLOCK_BIT_PREV_FREE ((size_t) 2)
#define BLOCK_BITS (BLOCK_BIT_FREE | BLOCK_BIT_PREV_FREE)
```
`block_size`, `block_set_size`, `block_set_prev_free`, `block_set_free` 等函式都是對 header 作對應的 bitmask 操作，得到或更改想要的 bit ，實作很簡單，不一一解釋。
對幾個比較難懂的 block 操作做解釋：
#### payload 以及 block 位址互找
很直觀，見下圖，取自 [esp-idf 的記憶體管理: TLSF 演算法](https://blog.csdn.net/gzxb1995/article/details/124504705)。
<img src="https://hackmd.io/_uploads/SJCkqoSL2.png" width="50%" height="50%">
block + prev 的大小 + size 的大小 = payload 的位址，反之亦然。
offsetof 會獲取 `tlsf_block_t` 圖中 size (header) 成員相對於結構體起始地址的偏移量，即為 prev 的大小。
BLOCK_OVERHEAD 即為圖中 size (header) 的大小。
```c
INLINE char *block_payload(tlsf_block_t *block)
{
return (char *) block + offsetof(tlsf_block_t, header) + BLOCK_OVERHEAD;
}
...
INLINE tlsf_block_t *block_from_payload(void *ptr)
{
return to_block((char *) ptr - offsetof(tlsf_block_t, header) -
BLOCK_OVERHEAD);
}
```
#### prev / next block
找 block **實體上**前一個或後一個的 block。
> Note: 一直強調實體上，是跟 free list 內的前後 block 做對比。
block_prev 因為本來就有存 prev ，直接呼叫即可。
```c
/* Return location of previous block. */
INLINE tlsf_block_t *block_prev(const tlsf_block_t *block)
{
ASSERT(block_is_prev_free(block), "previous block must be free");
return block->prev;
}
```
示意圖如下：
```
+-----------+ <- block
| prev |
+-----------+
| header |
+-----------+ <- block_payload(block)
| next_free |
+-----------+
| prev_free |
+-----------+
| ... |
+-----------+ <- next (want we want)
| prev | } BLOCK_OVERHEAD
+-----------+ <- block_payload(block) + block_size(block)
| header |
+-----------+
| next_free |
+-----------+
| prev_free |
+-----------+
| ... |
+-----------+
```
要注意 `BLOCK_OVERHEAD` 表達的是一個 ptr 的大小，所以在上面對齊時當作 `header` 的大小，這邊則當作為 `prev` 的大小，可以將其替換成 `siezof(tlsf_block *)`。
```c
/* Return location of next existing block. */
INLINE tlsf_block_t *block_next(tlsf_block_t *block)
{
tlsf_block_t *next =
to_block(block_payload(block) + block_size(block) - BLOCK_OVERHEAD);
ASSERT(block_size(block), "block is last");
return next;
}
```
### tlsf_t 資料結構
接下來，介紹另一個重要的資料結構，名為 tlsf_t ，其意義為整個 tlsf memory pool 的 controller，以下用程式碼以及圖例會更好的理解。
```c
typedef struct {
uint32_t fl, sl[_TLSF_FL_COUNT];
struct tlsf_block *block[_TLSF_FL_COUNT][_TLSF_SL_COUNT];
size_t size;
} tlsf_t;
```
#### fl, sl[_TLSF_FL_COUNT]
fl 以及 sl 的 bitmap 用來記錄其對應的 sl 或 fl 是否存在 free block。 sl 中 1 表有 free block 0 表沒 free block，而在 fl 中 1 表所有此 fl 層中的 sl free block 0 表所有此 fl 層中的 sl 沒 free block 。
```
舉例：
fl 為 0........01：表示只有 fl 為 0 中存在有 sl 存在 free block。
sl[0] 為 0000000000000001 ： 表示 fl 為 0 中 sl 為 0 對應的 free block。
fl 為 0......0101：表示只有 fl 為 0 或 2 中存在有 sl 存在 free block。
sl[0] 為 0000000000000011 ： 表示 fl 為 0 中 sl 為 0 或 1 存在 free block。
```
#### block[_TLSF_FL_COUNT][_TLSF_SL_COUNT]
用來儲存每一個 fl sl 的 free list head。
```
舉例：
block[0][0] 為某個 ptr，則代表 fl 0 sl 0 的 free list 的第一個 block 位址為 ptr。
block[1][1] 為 NULL，則代表 fl 0 sl 0 的 free list 的為 empty。
```
用下圖來理解 tlsf_t 在 mem 中的儲存位置，詳細圖見上段 TLSF 架構：
```
+------------+ \
| |
| tlsf_t | ------------------> 函 bitmap blocks 等。
| |
+------------+ /
| block |
| |
+------------+
| free |
+------------+
| block |
+------------+
```
### mapping
如同上段 TLSF 架構所解釋，mapping 技術就是把 size 轉換為對應的 fl 以及 sl 值從而找到儲存在 `blocks[fl][sl]` 中最合適的 free list。
公式取自〈[TLSF: a New Dynamic Memory Allocator for Real-Time Systems](http://www.gii.upv.es/tlsf/files/ecrts04_tlsf.pdf)〉如下：
fl 很好理解，sl 的概念為 $size - 2^f$ 表示 size > 此層 fl 多少空間，$size - 2^f$ 除此 fl 層的 sl 大小為何即可得到對應的 sl。
$2^{SLI}$ 就是 `SL_COUNT`，$2^{f+1}-2^f/2^{SLI}$ 意思就是 fl 層的 sl 大小，$2^{f+1}-2^f/2^{SLI}$ 可化簡為 $\dfrac{2^f}{2^{SLI}}$，$size - 2^f$ 除 $2^f/2^{SLI}$ 則可表示為 $(size - 2^f) \times (\dfrac{2^{SLI}}{2^f})$。
下面程式碼只是將這個數學是換成用 bitwise 操作，以增加性能，解釋如下：
```c
INLINE void mapping(size_t size, uint32_t *fl, uint32_t *sl)
{
/*原因如同 block 資料結構中的解釋，且不會滿足上述 fl 的公式*/
if (size < BLOCK_SIZE_SMALL) {
/*太小的 block 會全部放入 fl 0 */
*fl = 0;
/*跟上述公式一模一樣，只是第一個 2^f 因為是起點所以為 0 */
/*第二個 2^f 的數學意義是此層 fl 的大小所以為 BLOCK_SIZE_SMALL*/
*sl = (uint32_t) size / (BLOCK_SIZE_SMALL / SL_COUNT);
} else {
uint32_t t = log2floor(size);
/*與公式相同*/
/*XOR 前可轉換成 size * 2^t / SL_COUNT */
/*XOR 代表減法，SL_COUNT 是把公式括號內的 2^f 提出運算之結果*/
*sl = (uint32_t) (size >> (t - SL_SHIFT)) ^ SL_COUNT;
/*原因如同上段 重要參數 解釋 FL_COUNT 一樣*/
*fl = t - FL_SHIFT + 1;
}
ASSERT(*fl < FL_COUNT, "wrong first level");
ASSERT(*sl < SL_COUNT, "wrong second level");
}
```
### insert remove free block 操作
#### block_remove block_insert
我們真實在 remove 以及 insert 時，只會知道要處理的 block 的位址，所以要先通過 mapping 尋找此大小的 block 對應的 fl sl，才會知道它存在哪個 free list (blocks[fl][sl])。在進行對於 list 的 node 操作。
```c
/* Remove a given block from the free list. */
INLINE void block_remove(tlsf_t *t, tlsf_block_t *block)
{
uint32_t fl, sl;
mapping(block_size(block), &fl, &sl);
remove_free_block(t, block, fl, sl);
}
/* Insert a given block into the free list. */
INLINE void block_insert(tlsf_t *t, tlsf_block_t *block)
{
uint32_t fl, sl;
mapping(block_size(block), &fl, &sl);
insert_free_block(t, block, fl, sl);
}
```
#### insert remove block in free list
對於已知 free list (blocks[fl][sl])，這兩個函式是把 block 給在對應的 free list (blocks[fl][sl]) 插入或是刪除，插入是直接插在 list 的最前端，作法就是基本的 linked list 操作，比較特別的是最後會去檢查 bitmap 需不需要更新。
```c
/* Remove a free block from the free list. */
INLINE void remove_free_block(tlsf_t *t,
tlsf_block_t *block,
uint32_t fl,
uint32_t sl)
{
ASSERT(fl < FL_COUNT, "wrong first level");
ASSERT(sl < SL_COUNT, "wrong second level");
tlsf_block_t *prev = block->prev_free;
tlsf_block_t *next = block->next_free;
if (next)
next->prev_free = prev;
if (prev)
prev->next_free = next;
/* If this block is the head of the free list, set new head. */
if (t->block[fl][sl] == block) {
t->block[fl][sl] = next;
/* If the new head is null, clear the bitmap. */
if (!next) {
t->sl[fl] &= ~(1U << sl);
/* If the second bitmap is now empty, clear the fl bitmap. */
if (!t->sl[fl])
t->fl &= ~(1U << fl);
}
}
}
/* Insert a free block into the free block list and mark the bitmaps. */
INLINE void insert_free_block(tlsf_t *t,
tlsf_block_t *block,
uint32_t fl,
uint32_t sl)
{
tlsf_block_t *current = t->block[fl][sl];
ASSERT(block, "cannot insert a null entry into the free list");
block->next_free = current;
block->prev_free = 0;
if (current)
current->prev_free = block;
t->block[fl][sl] = block;
t->fl |= 1U << fl;
t->sl[fl] |= 1U << sl;
}
```
### block 切割實作
這邊講解了 block 的各種切割實作，為甚麼需要切割在後續講解 `alloc` `free` 時會提到，或是直接參考[測驗五第一題](https://hackmd.io/@sysprog/linux2023-quiz5)。
#### block_can_split
檢查的 block 是否能分割 size 出來， 當然 block size 要大於等於 size ，加上 `sizeof(tlsf_block)
`要確保底部實體上下一個 block 的 prev 有地方儲存。
見下圖，取自 [esp-idf 的記憶體管理: TLSF 演算法](https://blog.csdn.net/gzxb1995/article/details/124504705)。
<img src="https://hackmd.io/_uploads/ByoT05SI3.png" width="50%" height="50%">
```c
INLINE bool block_can_split(tlsf_block_t *block, size_t size)
{
return block_size(block) >= sizeof(tlsf_block_t) + size;
}
```
#### block_rtrim_free block_rtrim_used block_ltrim_free
有三種不同的切割方式，取決於切割前 block 的狀態以及切割後想要 block 的狀態。
```c
/*把 free block 的頭部分割出指定的大小*/
/*尾部會剩下一個 free block*/
/*將分割完頭部的 free block 插入對應大小的 free list(blocks[fl][sl])*/
INLINE void block_rtrim_free(tlsf_t *t, tlsf_block_t *block, size_t size)
{
ASSERT(block_is_free(block), "block must be free");
/*先確定可否 split*/
if (!block_can_split(block, size))
return;
/*將一個 block 分割成兩塊，函式實作見後面*/
/*rest 代表尾部的 block*/
/*block 代表頭部的 block*/
tlsf_block_t *rest = block_split(block, size);
/*頭部的 block 因為後面的 block 變為新的 block*/
/*需要重新 link*/
block_link_next(block);
/*block 是 free 所以 rest 的 prev free 要設定為 true*/
block_set_prev_free(rest, true);
/*將分割完頭部的 free block 插入對應大小的 free list(blocks[fl][sl])*/
block_insert(t, rest);
}
/*把 use block 的頭部分割出指定的大小*/
/* 尾部會剩下一個 free block*/
/*將分割完尾部的 free block 插入對應大小的 free list(blocks[fl][sl])*/
INLINE void block_rtrim_used(tlsf_t *t, tlsf_block_t *block, size_t size)
{
ASSERT(!block_is_free(block), "block must be used");
/*先確定可否 split*/
if (!block_can_split(block, size))
return;
/*將一個 block 分割成兩塊，函式實作見後面*/
/*rest 代表尾部的 block*/
/*block 代表頭部的 block*/
tlsf_block_t *rest = block_split(block, size);
/*物理上前一個是 free block 才會在 merge 使用到 prev */
/*所以不需要 block_link_next(block) 來更新 next->prev*/
/*block 是 use 所以 rest 的 prev free 要設定為 false*/
block_set_prev_free(rest, false);
/*free block 與後面的 free block 合併(若存在)*/
/*在block_rtrim_free沒有這段，因為 free block 後不可能是 free block*/
/*在介紹到 free 實作時會說明這點*/
rest = block_merge_next(t, rest);
/*將分割完尾部的 free block 插入對應大小的 free list(blocks[fl][sl])*/
block_insert(t, rest);
}
/*把 free block 的頭部分割出指定的大小*/
/* 尾部會剩下一個 free block*/
/*將分割完頭部的 free block 插入對應大小的 free list(blocks[fl][sl])*/
/*return 尾部的 free block*/
/*使用於 aalloc*/
INLINE tlsf_block_t *block_ltrim_free(tlsf_t *t,
tlsf_block_t *block,
size_t size)
{
ASSERT(block_is_free(block), "block must be free");
ASSERT(block_can_split(block, size), "block is too small");
/*將一個 block 分割成兩塊，函式實作見後面*/
/*rest 代表尾部的 block*/
/*block 代表頭部的 block*/
/*BLOCK_OVERHEAD 是考量到 header*/
tlsf_block_t *rest = block_split(block, size - BLOCK_OVERHEAD);
/*block 是 free 所以 rest 的 prev free 要設定為 true*/
block_set_prev_free(rest, true);
/*頭部的 block 因為後面的 block 變為新的 block*/
/*需要重新 link*/
block_link_next(block);
/*將分割完頭部的 free block 插入對應大小的 free list(blocks[fl][sl])*/
block_insert(t, block);
/*return 尾部的 free block*/
return rest;
}
```
#### block_merge_prev block_merge_next
合併方式有兩種，注意這邊的合併是查找**物理上**的 block 來做合併，因為實際使用式合併 free block 所以一定要是 free block 才能實行此函式。
```c
/* 把前此 block 跟物理上前面的 block 合併，注意結果不會加到 free list
+------------+-------+
| free block | block |
+------------+-------+
*/
INLINE tlsf_block_t *block_merge_prev(tlsf_t *t, tlsf_block_t *block)
{
/*因為是用在 free block 合併，前一個一定要是 free block*/
if (block_is_prev_free(block)) {
tlsf_block_t *prev = block_prev(block);
ASSERT(prev, "prev block can't be null");
ASSERT(block_is_free(prev),
"prev block is not free though marked as such");
/*移除 prev 於 free list 中*/
block_remove(t, prev);
/*將前後合併*/
block = block_absorb(prev, block);
}
return block;
}
/* 把前此 block 跟物理上後面的 block 合併，注意結果不會加到 free list
+-------+------------+
| block | free block |
+-------+------------+
*/
INLINE tlsf_block_t *block_merge_next(tlsf_t *t, tlsf_block_t *block)
{
tlsf_block_t *next = block_next(block);
ASSERT(next, "next block can't be null");
if (block_is_free(next)) {
ASSERT(block_size(block), "previous block can't be last");
/*移除 next 於 free list 中*/
block_remove(t, next);
/*將前後合併*/
block = block_absorb(block, next);
}
return block;
}
```
#### block_split block_absorb
用來實現切割與合併。
```c
/*將給定 block 切 size 出來，並把剩下的空間定義一個新 block*/
/*並回傳 rest，注意這邊並未把 rest 放入 free list
+-----------+ <- block +-----------+ <- block
| prev | | prev |
+-----------+ +-----------+
| header | | header |
+-----------+ +-----------+ \
| next_free | | next_free |
+-----------+ +-----------+
| prev_free | | prev_free |
+-----------+ +-----------+ size
| ... | | ... |
| | before-------->after +-----------+ <- rest
| | | prev |
| | +-----------+ /
| | | header |
| | +-----------+
| | | next_free |
| | +-----------+
| | | prev_free |
| | +-----------+
| | | ... |
+-----------+ +-----------+
*/
INLINE tlsf_block_t *block_split(tlsf_block_t *block, size_t size)
{
/*扣掉的 BLOCK_OVERHEAD 是因為 rest 要指在 prev*/
tlsf_block_t *rest = to_block(block_payload(block) + size - BLOCK_OVERHEAD);
/*扣掉的 BLOCK_OVERHEAD 是因為要分 header 出來，header 不算在 size*/
size_t rest_size = block_size(block) - (size + BLOCK_OVERHEAD);
ASSERT(block_size(block) == rest_size + size + BLOCK_OVERHEAD,
"rest block size is wrong");
ASSERT(rest_size >= BLOCK_SIZE_MIN, "block split with invalid size");
/*新 block size 設定*/
rest->header = rest_size;
ASSERT(!(rest_size % ALIGN_SIZE), "invalid block size");
/*更新切下來以後的空間以及原本的 block*/
block_set_free(rest, true);
block_set_size(block, size);
return rest;
}
/* 合併前後 block，前 prev 後 block，示意圖為 split 的反向
+-----------+ <- prev +-----------+ <- prev
| prev | | prev |
+-----------+ +-----------+
| header | | header |
+-----------+ +-----------+
| next_free | | next_free |
+-----------+ +-----------+
| prev_free | | prev_free |
+-----------+ +-----------+
| ... | | ... |
| | after<--------before +-----------+ <- block
| | | prev |
| | +-----------+
| | | header |
| | +-----------+
| | | next_free |
| | +-----------+
| | | prev_free |
| | +-----------+
| | | ... |
+-----------+ +-----------+
*/
INLINE tlsf_block_t *block_absorb(tlsf_block_t *prev, tlsf_block_t *block)
{
ASSERT(block_size(prev), "previous block can't be last");
/*加上的 BLOCK_OVERHEAD 是因為要加 header 回來，header 不算原本的在 size*/
prev->header += block_size(block) + BLOCK_OVERHEAD;
block_link_next(prev);
return prev;
}
```
### tlsf init
在 [jserv/tlsf](https://github.com/jserv/tlsf-bsd) 中並未找到關於 tlsf pool 的初始化，但初始化的狀態可以大大幫助理解程式碼，這邊先使用 [esp-idf 的記憶體管理: TLSF 演算法](https://blog.csdn.net/gzxb1995/article/details/124504705) 這篇文章的概念，見下圖。
這是一個 TLSF 初始化完的狀態，有幾個重點：
1. tlsf_t 會分配在記憶體最上方的位置。
2. 一開始會將整個 memory pool 初始化為一個 free block，換句話說指會有一個 blocks[fl][sl] 有指向 free list (只有一個 free list)。
所以不難想像，一開始無論 alloc 的 size `mapping` 後的 fl sl 為何，在 `block_find_suitable` 後都會找到那個唯一有 free block 的 fl sl index。
[jserv/tlsf](https://github.com/jserv/tlsf-bsd) 並未有 init 函式 而是使用 `arena_grow` `arena_shrink` 代替。
```c
static bool arena_grow(tlsf_t *t, size_t size)
{
//找到新的 size
size_t req_size =
(t->size ? t->size + BLOCK_OVERHEAD : 2 * BLOCK_OVERHEAD) + size;
//可不可以給我這個 size
void *addr = tlsf_resize(t, req_size);
if (!addr)
return false;
ASSERT((size_t) addr % ALIGN_SIZE == 0, "wrong heap alignment address");
//找到增加空間後最新 block 的位置
tlsf_block_t *block =
to_block(t->size ? (char *) addr + t->size - 2 * BLOCK_OVERHEAD
: (char *) addr - BLOCK_OVERHEAD);
if (!t->size)
block->header = 0;
check_sentinel(block);
//設定新得到的 block
block->header |= size | BLOCK_BIT_FREE;
block = block_merge_prev(t, block);
block_insert(t, block);
//設定新的 sentinel
tlsf_block_t *sentinel = block_link_next(block);
sentinel->header = BLOCK_BIT_PREV_FREE;
t->size = req_size;
check_sentinel(sentinel);
return true;
}
static void arena_shrink(tlsf_t *t, tlsf_block_t *block)
{
//新的 free block 是最尾（下一個是 sentinel）就把空間還回去
check_sentinel(block_next(block));
size_t size = block_size(block);
ASSERT(t->size + BLOCK_OVERHEAD >= size, "invalid heap size before shrink");
//刪掉 free block 的 size
t->size = t->size - size - BLOCK_OVERHEAD;
//只剩 sentinel
if (t->size == BLOCK_OVERHEAD)
t->size = 0;
tlsf_resize(t, t->size);
//還有其他 block，設定新 sentinel
if (t->size) {
block->header = 0;
check_sentinel(block);
}
}
```
### malloc
討論完 init 後，我們來看如何 malloc，具體流程如下：
1. 先把 size 對齊，如果每個申請的 size 都申請 `ALIGN_SIZE` 的倍數，自然他們的 ptr 就會是對齊好的。
2. 找到此 size 最合適的 free list。
3. 從此 free list 中取出一個 free block 作為 alloc 的對象。
4. 將此 free block 從 list 中移除。
5. 將此 free block 切出 size 作為 use block。
6. 將切剩的 free block 放到對應合適大小的 free list。
`adjust_size`：1
`block_find_free`：2~4
`block_use`：5~6
```c
void *tlsf_malloc(tlsf_t *t, size_t size)
{
size = adjust_size(size, ALIGN_SIZE);
if (UNLIKELY(size > TLSF_MAX_SIZE))
return NULL;
tlsf_block_t *block = block_find_free(t, size);
if (UNLIKELY(!block))
return NULL;
return block_use(t, block, size);
}
```
接下來就可以看這些函式具體的實作：
#### adjust_size
呼叫 `align` 等對其函式，若對齊後比最小可以存在的 BLOCK 還小，就回傳`BLOCK_SIZE_MIN`。
```c
/* Adjust allocation size to be aligned, and no smaller than internal minimum.
*/
INLINE size_t adjust_size(size_t size, size_t align)
{
size = align_up(size, align);
return size < BLOCK_SIZE_MIN ? BLOCK_SIZE_MIN : size;
}
```
##### align
對齊的詳細概念以及意義見[你所不知道的 C 語言：記憶體管理、對齊及硬體特性篇](https://hackmd.io/@sysprog/c-memory)。 `align_ptr` 會呼叫 `align_up` 得到向上對齊後的位址 (例如 15 對齊 8 得到 16)，即找向上最接近 align 的倍數。因為 size_t align 會是二的次方，`align - 1` 後會是 0+1+ 的形式，做 | 的意義在於將 x 對 align 取餘數後為 align - 1，最後的 `+1` 自然就會得到向上最接近 align 的倍數，一開始做 `x-1` 是確保邊界狀況 (例如 16 對齊 8，所以先把 16 改成 15) 也會成立。
```c
INLINE size_t align_up(size_t x, size_t align)
{
ASSERT(!(align & (align - 1)), "must align to a power of two");
return (((x - 1) | (align - 1)) + 1);
}
INLINE char *align_ptr(char *p, size_t align)
{
return (char *) align_up((size_t) p, align);
}
```
#### `block_find_free`
總體用途上面已經解釋過了。
這邊需要特別提的是 `提級申請` 概念，就是會用高一層的 size，去做 mapping。舉例：原本 size 是落在 `blocks[1][1]`，但我們 mapping 完想要的 fl sl 反而是 `blocks[1][2]`。
原因很好理解，假如我們使用原本的 size 介於：
$[ 2^f, 2^f + N)$
`mapping` 後得到的 fl sl 的 free block 空間大小也會介於：
$[ 2^f, 2^f + N)$
所以找到的 free block 不一定比 size 大，遍例整個 free list 會浪費時間成本，所以我們做提級，確保找到的 free block 一定大於 size。
我們希望 `mapping` 後得到的 fl sl 的 free block 空間大小會介於：
$[ 2^f + N, 2^f + 2N)$
`round_block_size` 就是先把原本的 size 提到下一層的大小，讓我們最後得到的 fl sl 會提級。
```c
INLINE tlsf_block_t *block_find_free(tlsf_t *t, size_t size)
{
size_t rounded = round_block_size(size);
uint32_t fl, sl;
/*找到此 size 最合適的 free list*/
mapping(rounded, &fl, &sl);
tlsf_block_t *block = block_find_suitable(t, &fl, &sl);
if (UNLIKELY(!block)) {
if (!arena_grow(t, rounded))
return NULL;
block = block_find_suitable(t, &fl, &sl);
ASSERT(block, "no block found");
}
ASSERT(block_size(block) >= size, "insufficient block size");
/*從此 free list 中取出一個 free block 作為 alloc 的對象*/
/*將此 free block 從 list 中移除*/
remove_free_block(t, block, fl, sl);
return block;
}
```
##### round_block_size
$((size_t) 1 << (log2floor(size) - SL_SHIFT))$ 等價於，$2^f/SL\_COUNT$ 解釋 ，`mapping` 時講過了，就是這個 size 所屬 SL 層的大小。
$size + t$ 原本的 `size` 加上所屬 SL 層的大小，一定會變到下一個 SL 層區間。
`& ~t` 代表加上後多出來的餘數就算了。
```c
/* Round up to the next block size */
INLINE size_t round_block_size(size_t size)
{
size_t t = ((size_t) 1 << (log2floor(size) - SL_SHIFT)) - 1;
return size >= BLOCK_SIZE_SMALL ? (size + t) & ~t : size;
}
```
##### block_find_suitable
就算找到了儲存了最合適大小的 free block 的 free list 所對應的 fl sl，此 fl sl (blocks[fl][sl]) 也不一定有 node 在 free list 內，意即沒有此大小區間的 free block 存在 memeory 。這時就必須往找尋更大的 free block (更大的 fl sl)，來做為未來 alloc 的位址。
這邊也是使用 bitwise 操作，使得效率加快，都蠻容易理解的。
在查找時直接 bitmap ，不用使用遍例找到最合適的 fl sl ，所以搜尋時間為 O(1)。
```c
INLINE tlsf_block_t *block_find_suitable(tlsf_t *t, uint32_t *fl, uint32_t *sl)
{
ASSERT(*fl < FL_COUNT, "wrong first level");
ASSERT(*sl < SL_COUNT, "wrong second level");
/* 從 sl 的 bitmap 中將此 sl 對應的 bit 及更高位的 bit 都取出來 */
uint32_t sl_map = t->sl[*fl] & (~0U << *sl);
/*如果結果為 0，代表此 fl 沒有相應大小的 free block 了*/
if (!sl_map) {
/*去更大的 fl 尋找*/
/*取出 fl bitmap 中更高位的 bit*/
uint32_t fl_map = t->fl & (uint32_t) (~(uint64_t) 0 << (*fl + 1));
/*如果結果為 0，代表整個 memory pool 都沒有相應大小的 free block 了*/
if (UNLIKELY(!fl_map))
return NULL;
/*若不為 0，就從剛剛取出的更高位的 bit 中找最小那位*/
*fl = bitmap_ffs(fl_map);
ASSERT(*fl < FL_COUNT, "wrong first level");
/*取出此區間的 sl bitmap*/
sl_map = t->sl[*fl];
ASSERT(sl_map, "second level bitmap is null");
}
/*從 sl_map 中取出最低位的 bit 作為我們最後的 sl 層*/
/*因為確認過 fl bitmap 以及 sl bitmap，現在的 sl_map 一定不為 0*/
*sl = bitmap_ffs(sl_map);
ASSERT(*sl < SL_COUNT, "wrong second level");
return t->block[*fl][*sl];
}
```
#### block_use
作用如上面解釋，各個函式實作上面都介紹過了。
```c
INLINE void *block_use(tlsf_t *t, tlsf_block_t *block, size_t size)
{
/*將此 free block 切出 size*/
/*將切剩的 free block 放到對應合適大小的 free list*/
block_rtrim_free(t, block, size);
/*切出來的作為 use block*/
block_set_free(block, false);
/*malloc 最後回傳給 usr 是回傳 payload 的 ptr*/
return block_payload(block);
}
```
### free
在進到 free 前先講解 free 的基本運行流程，概念來自對[測驗五第一題](https://hackmd.io/@sysprog/linux2023-quiz5)的理解。
在記憶體管理中，當一個 block 要釋放時，我們會去檢查其物理上前後是否為 free block ，若為 free block 我們會將釋放以後的 block 跟前後的 free block 作合併，得到一個更大的 free block ，這樣我們未來在做 alloc 時就有一個更大的連續空間可以使用。
`merge` 的流程如下：
```
+------------+-------+------------+
| free block | block | free block |
+------------+-------+------------+
在 tlsf 的實作中，會先去跟前面的 free block 做 merge
+--------------------+------------+
| free block | free block |
+--------------------+------------+
然後再跟後面的 free block 做 merge 最後得到最大的 free block
+---------------------------------+
| free block |
+---------------------------------+
如果要釋放的 block 前或後不為 free block 怎麼辦?
這不用擔心，因為 merge_pre 跟 merge_next 在執行前都會先去檢查 pre 或 next
是不是 free block ，若不是 merge 將甚麼都不會做，最後還是會得到最大的 free block
```
我們每次 free 後，都會去做合併，所以在 memory pool 中，是不會存在兩個 free block 連在一起的狀況。
這邊要特別注意的是在 tlsf 在合併後，因為 free block 的大小改變了，所以要重新做 mapping 得到對應的 fl sl ，並將新的 free block 放入對應的 free list (blocks[fl][sl])。
```c
void tlsf_free(tlsf_t *t, void *mem)
{
if (UNLIKELY(!mem))
return;
/*usr 只會知道 payload 的位址*/
/*所以傳進來後，要先推回 block 的位址*/
tlsf_block_t *block = block_from_payload(mem);
ASSERT(!block_is_free(block), "block already marked as free");
/*把此 block 改為 free*/
block_set_free(block, true);
/*先跟前面做合併，若前面不為 free block 這個函式甚麼都不會做*/
block = block_merge_prev(t, block);
/*再跟後面做合併，若後面不為 free block 這個函式甚麼都不會做*/
block = block_merge_next(t, block);
if (UNLIKELY(!block_size(block_next(block))))
arena_shrink(t, block);
else
/*最後合併完成的新 free block 要放到對應的 free list (blocks[fl][sl])*/
block_insert(t, block);
}
```
最後，有一些比較延伸的函式還沒寫，未來有機會補上：
`tlsf_aalloc`、`tlsf_realloc`、`arena_shrink`、`arena_grow` 、`check_sentinel`、`block_rtrim_used`
## TLSF 效能分析與特性討論
> github [cin-cout/tlsf-bsd](https://github.com/cin-cout/tlsf-bsd)
### 前置設定
為了避免會影響的效能測量的因素，需要做前置設定。而每次開機都要重新輸入命令很不方便，所以將效能相關的前置設定與程式執行包成了一個 measure.sh 檔，細節參照 [fibdrv-開發紀錄](https://hackmd.io/uHe0dpXJRZ292NfIKWApag)。
```bash
#!/bin/bash
CPUID=5
ORIG_ASLR=`cat /proc/sys/kernel/randomize_va_space`
ORIG_GOV=`cat /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor`
ORIG_TURBO=`cat /sys/devices/system/cpu/intel_pstate/no_turbo`
ORIG_SMT=`cat /sys/devices/system/cpu/smt/control`
sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
sudo sh -c "echo performance > /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor"
sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
sudo sh -c "echo off > /sys/devices/system/cpu/smt/control"
make run
sudo sh -c "echo $ORIG_ASLR > /proc/sys/kernel/randomize_va_space"
sudo sh -c "echo $ORIG_GOV > /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor"
sudo sh -c "echo $ORIG_TURBO > /sys/devices/system/cpu/intel_pstate/no_turbo"
sudo sh -c "echo $ORIG_SMT > /sys/devices/system/cpu/smt/control"
```
### 實作 tlsf_init
在 [jserv/tlsf](https://github.com/jserv/tlsf-bsd) 中 tlsf 會在沒有合適的 free block 時動態的從 pre-allocating 的空間中拿取新的空間，但考慮到 pre-allocate 的空間在 tlsf 執行時是不會被 tlsf 外的資料所使用的，放著也只是閒置著，所以可以在 tlsf init 時就把所有 pre-allocte 的空間放入 tlsf 內，可以減少因不斷動態增加空間的成本。
想法參考 [mattconte/tlsf](https://github.com/mattconte/tlsf/blob/master/tlsf.c) 實作了另一種 tlsf init 的方式：
```c
static size_t align_down(size_t x, size_t align)
{
ASSERT(0 == (align & (align - 1)), "must align to a power of two");
return x - (x & (align - 1));
}
bool tlsf_add_pool(tlsf_t *t, void* mem, size_t mem_size)
{
tlsf_block_t * block;
tlsf_block_t * next;
const size_t pool_bytes = align_down(mem_size - 2*BLOCK_OVERHEAD, ALIGN_SIZE);
ASSERT((size_t) mem % ALIGN_SIZE == 0, "wrong heap alignment address");
block = to_block((char *) mem - BLOCK_OVERHEAD);
block->header |= pool_bytes | BLOCK_BIT_FREE;
block_insert(t, block);
next = block_link_next(block);
next->header = BLOCK_BIT_PREV_FREE;
t->size = mem_size;
return true;
}
void tlsf_init(tlsf_t *t, void* mem, size_t mem_size)
{
*t = TLSF_INIT;
tlsf_add_pool(t, mem, mem_size);
}
```
#### tlsf_init 效能比較
隨後對於原本的方法以及新的方法做比較。
x : 分配的 block size 大小（範圍），假如 x 為 2000，分配的 block min 為 2000，block max 為 2000 + 64，單位為 bytes 。
y : 平均 malloc + free 的時間，單位為 us。
藍色為使用 [jserv/tlsf](https://github.com/jserv/tlsf-bsd) arena grow/shrink 動態獲取 free block 的方法。
橘色為使用調整後的 tlsf_init 方法。
可以看出因為少了不斷動態增加空間的成本， tlsf_init 的方式效能有不小的提昇。而無論是哪種實作方式，平均 alloc 的 size 越大，所花的時間也會有略為的上升。
#### tlsf_init 效能比較（大範圍）
因為上張圖，每一項測資範圍區間僅有 64 bytes ，為了確認當申請的 block 範圍大一點時，是否有一樣的現象，所以又進行了測試。
x : 執行的 50 次相同的設定。
y : 平均 malloc + free 的時間，單位為 us。
左圖為使用 [jserv/tlsf](https://github.com/jserv/tlsf-bsd) arena grow/shrink 動態獲取 free block 的方法。
右圖為使用調整後的 tlsf_init 方法。
不同線代表不同 size range。
<div style="display: flex;">
<img src="https://hackmd.io/_uploads/SyVukDxP2.png" width="50%" height="50%">
<img src="https://hackmd.io/_uploads/HJEuJvgDn.png" width="50%" height="50%">
</div>
結果與上一種測試相同， tlsf_init 的方式效能有不小的提昇。而無論是哪種實作方式，平均 alloc 的 size 越大，所花的時間也會有略為的上升。
另外可以從這個測試看出，因為在測試時 block size 是 random 的，使用 [jserv/tlsf](https://github.com/jserv/tlsf-bsd) arena grow/shrink 動態獲取 free block 的方法，會因為每次測試 alloc 的 size 大小順序具有隨機性，所以會比較不穩定，較難預期結果。
### TLSF 特性討論
對 tlsf pre-allocating 以及 O(1) 的特性做討論。
#### pre-allocating
下圖物理性質見上段。
這邊可以看到在約接近 10000 ～ 10000 + 64 的 size 後出現了不如預期的結果。**這是因為在 tlsf pre-allocating 階段給的空間不足**，導致後期在測量大的 size 時， alloc 會失敗(回傳 NULL)，也因為這樣不須做後續的其他步驟，時間自然降下來。
所以在使用 tlsf 時要算清楚應事先分配多少空間，這個空間分配給 tlsf 後就不會給其他使用，分配太大可能會浪費記憶體的空間，太少可能會造成 tlsf alloc 時無空間可使用。
還有一點是 tlsf 在 alloc 時除了原本要求的 size ，還會需要一個 word 去除存 block->header，加上在使用 tlsf 的過程可能有碎片化的產生，剩餘的 free block 不連續，所以在 pre-allocating 時不能只分配剛剛好大小的。
#### O(1)
TLSF 的實作上沒有使用到遍歷，所以確實是 O(1)，但是從下圖可知，在要求的 size 越大時，雖然時間成長的幅度很小，需要的時間也會更多，這是因為更大 block alloc 可能會更容易觸發到一些 if 的條件，進而花費更多時間。
結論是，雖然 TLSF 在演算法的定義中是 O(1) ，但是當 alloc size 越大時，運行開銷更大的趨勢。
## xvmalloc 架構
如同 [xvMalloc](https://code.google.com/archive/p/compcache/wikis/xvMalloc.wiki) 所敘述，xvmalloc 是基於 TLSF 的記憶體配置器，大部分實作與 TLSF 相同，也使用二層索引的方式尋找最合適的 free list 而得到 free block ， block 方面也如同 TLSF 設計，有紀錄物理上前一個 block 的位置的 ptr 和前後 free block 的 ptr，與 TLSF 不同在於：
1. 考量到硬體的架構， xvmalloc 在 malloc 的時候會以 page 為單位，以減少在真正使用空間時，一個 data 橫跨兩個 page 增加 page fault 的機會。
2. 程式碼實作中有 lock 的機制，所以可以運行於多平行系統中。
## xvmalloc 實作解析
程式碼的部分參照 [linux/commit](https://github.com/torvalds/linux/commit/644bf7b5983cf2540b57a5b25b775cb3c1e8e943)。大部分與 TLSF 相同，此處特別講解考量 page 後的實作差異。
### 資料結構
`xv_pool` 等同於 `tlsf_t` 只是 free list 不是紀錄 block 的 ptr 而是 page 與 offset，page 以及 offset 意義後續會提到。
```c
struct freelist_entry {
struct page *page;
u16 offset;
u16 pad;
};
struct xv_pool {
ulong flbitmap;
ulong slbitmap[MAX_FLI];
spinlock_t lock;
struct freelist_entry freelist[NUM_FREE_LISTS];
/* stats */
u64 total_pages;
};
```
`block` 也與 TLSF 相同只是改為 page 和 offset。
```c
struct link_free {
struct page *prev_page;
struct page *next_page;
u16 prev_offset;
u16 next_offset;
};
struct block_header {
union {
/* This common header must be ALIGN bytes */
u8 common[XV_ALIGN];
struct {
u16 size;
u16 prev;
};
};
struct link_free link;
};
```
### 考量 page 實作後的程式碼
#### grow shrink pool
與 TLSF 的 `aerna_grow` 類似，在空間不足時會自動去增加空間。
`page = alloc_page(flags);` 可知，每次增加的空間就是一個 page 。
`insert_block(pool, page, 0, block);`會直接將這個 page 當成 free block 放入對應大小的 free list 中，由此可知對大的 free block 不會超過 `PAGE_SIZE`，所以不能 allocate 超過 `PAGE_SIZE` 的大小。
`get_ptr_atomic` 是將 page 映射到 process 的虛擬空間，對這個虛擬空間作操作才可以更改 page 儲存的內容。
`put_ptr_atomic` 使用完後要將其解除映射，無法同時映射多個 page。
```c
static int grow_pool(struct xv_pool *pool, gfp_t flags)
{
struct page *page;
struct block_header *block;
page = alloc_page(flags);
if (unlikely(!page))
return -ENOMEM;
stat_inc(&pool->total_pages);
spin_lock(&pool->lock);
block = get_ptr_atomic(page, 0, KM_USER0);
block->size = PAGE_SIZE - XV_ALIGN;
set_flag(block, BLOCK_FREE);
clear_flag(block, PREV_FREE);
set_blockprev(block, 0);
insert_block(pool, page, 0, block);
put_ptr_atomic(block, KM_USER0);
spin_unlock(&pool->lock);
return 0;
}
```
在 `xv_free` 有關於 shrink 的函式，就是如果 free 完後這個 page 沒有儲存任何資料，就將其釋放。
```c
/* No used objects in this page. Free it. */
if (block->size == PAGE_SIZE - XV_ALIGN) {
put_ptr_atomic(page_start, KM_USER0);
spin_unlock(&pool->lock);
__free_page(page);
stat_dec(&pool->total_pages);
return;
}
```
xvmalloc 的 grow 跟 shrink 比起 TLSF 更具有意義， TLSF 是在已經 pre-allocating 好的空間中做動態增加或減少空間，但是 pre-alocate 的空間就算沒有在 TLSF 中使用，也不會作為其他用途。而 xvmalloc 則是動態增加或減少 page ，沒在 xvmalloc 中使用的 page 是可以作為其他用途的。
### malloc free
最後看 `xv_malloc` 以及 `xv_free`。
大致上與 TLSF 相同，只是加入了 page 的限制。每次 malloc 的空間都一定會是在同一個 page，一個 block 只會在一個 page 中，一個 page 中可能被切成多個 block，不會存在一個 block 跨越兩個 page。offset 就是用來記錄 page 內的位置
#### malloc
`xv_malloc` 一樣會使用 mapping 的方式找到對應的 fl sl，並將其分配出去，然後再將這個 page 剩下還沒被使用的空間(用 offset 紀錄)放到對應的 fl sl，所以一個 freelist 儲存的 free block 可能是不同 page 的剩餘空間。
#### free
在 free 一塊空間時，會去看此空間所屬的 page 在此空間( offset )前後是否也沒被使用，若沒被使用，則合併，再將合併後的 block 儲存到對應的 free list。
## zsmalloc 架構
:::warning
:warning: 應闡述 zsmalloc 到底在解決什麼問題？開發動機是什麼？而非急著閱讀原始程式碼
:notes: jserv
:::
### 參考資料
程式碼：[zsmalloc.c](https://elixir.bootlin.com/linux/latest/source/mm/zsmalloc.c)
zsmalloc 的程式碼解析在網路上有很多了，所以這邊不特別對程式碼去做講解，只對基本架構去做解釋，有基本的的 allocator 知識再加上網路上的文章可以很快速的理解，以下是有用的網路文章：
1. [記憶體管理特性分析（一）：zsmalloc記憶體配置器分析](https://zhuanlan.zhihu.com/p/558763137)
程式碼乾淨整齊且有註解解釋，但解釋的很籠統。
2. [zsmalloc 配置器源码分析](https://toutiao.io/posts/1v6m59/preview)
解釋的較為詳細，但是程式碼排版不佳，圖片有些已經找不到了。
### 架構解析
zsmalloc 架構如下：
```
+-----------------------------------------+
|Zpool |
| +-----------------------------------+ |
| | zspage | |
| | +--------+ +--------+ | |
| | | object | | object | . . . | |
| | +--------+ +--------+ | |
| +-----------------------------------+ |
| |
| +-----------------------------------+ |
| | zspage | |
| +-----------------------------------+ |
| . |
| . |
| . |
| |
+-----------------------------------------+
```
如同上圖所示， zsmalloc 會有一個 pool ，裡面存著多個 zspage ，一個 zspage 由一致多個 page 組成，每個 zspage 裡面都會存放多個 object ，每一個 zspage 的 object size 有可能不同，有大有小，但是同一個 zspage 中 object size 都是一樣的， object size 不會超過 page size (不是 zspage size)，一個 object 相當於一個 block ，我們一次 alloc 的資料只會分配一個大小相近的 object 。
> 注意， zsmalloc 不是基於 TLSF 的機制，所以不會有 allocate 完將一個 object 剩下的空間放到別的 freelist ，就是一個蘿菠一個坑，一次 allocate 分一個 object 出去， zpage 用完會在動態新增，也會有 zpage 全空就 shrink 的機制。
## [xvmalloc](https://github.com/torvalds/linux/commit/644bf7b5983cf2540b57a5b25b775cb3c1e8e943) [zsmalloc](https://www.kernel.org/doc/html/v5.0/vm/zsmalloc.html) 效能比較
> github [cin-cout/allocator_benchmark](https://github.com/cin-cout/allocator_benchmark)
### 前置設定
#### zsmalloc config 設定
1. 先確認 linux 版本
```shell
$ uname -a
```
2. 移動到存放 config 的地方，/usr/src/`<linux version>`
```shell
$ cd /usr/src/linux-headers-5.4.0-146-generic
```
3. 編輯 .config
```shell
把 .config 從唯讀換成可寫
$ sudo chmod +w .config
$ vim .config
```
4. 更改 zsmalloc 所需的 config
```shell
CONFIG_ZSMALLOC=y
CONFIG_ZPOOL=y
CONFIG_ZBUD=y
CONFIG_Z3FOLD=y
CONFIG_ZRAM=y
# optional
CONFIG_ZSMALLOC_STAT=y
```
改成 m 也可以，但就是要額外自己掛載 module，而不是開機自動掛載。
掛載方式如下：
```shell
zram 換成想掛載的 module 名稱
$ sudo modprobe zram
```
5. 重新開機
```shell
$ sudo reboot
```
### zsmalloc vmalloc 效能分析實現
因為 linux kernel 已經有 `<linux/zsmalloc.h>` 想先測試 zsmalloc 在 kernel 的效能，bench 程式參考 [tlsf-bsd](https://github.com/jserv/tlsf-bsd) 的 bench.c ，程式很直觀，不細作解釋，只是改寫了部份，改成 kernel 端執行，使用 character device driver ，架構參考 [sysprog21/fibdrv](https://github.com/sysprog21/fibdrv) 。
#### kernel
用 write 作為 usr 呼叫 kernel module 執行效能運算程式，用 client 傳入的 size 決定要測量哪種 allocator。
```c
static ssize_t bench_write(struct file *file,
const char *buf,
size_t size,
loff_t *offset)
{
ktime_t kt;
size_t num_blks = 10000;
size_t loops = 10000000;
static unsigned long handle_array[10000];
memset(handle_array, 0, sizeof(handle_array));
static struct page *page_array[10000];
memset(page_array, 0, sizeof(page_array));
static u32 offset_array[10000];
memset(offset_array, 0, sizeof(offset_array));
switch (size) {
case 0:
zpool = zs_create_pool("mypool");
kt = ktime_get();
run_zsmalloc_benchmark(loops, *offset, *offset+32, handle_array, num_blks);
kt = ktime_sub(ktime_get(), kt);
zs_destroy_pool(zpool);
break;
case 1:
xpool = xv_create_pool();
kt = ktime_get();
run_xvmalloc_benchmark(loops, *offset, *offset+32, page_array, offset_array, num_blks);
kt = ktime_sub(ktime_get(), kt);
xv_destroy_pool(xpool);
break;
}
return (ssize_t) ktime_to_ns(kt);
}
```
##### get_random_block_size
```c
static size_t get_random_block_size(size_t blk_min, size_t blk_max)
{
if (blk_max > blk_min)
return blk_min + ((size_t) prandom_u32() % (blk_max - blk_min));
return blk_min;
}
```
`zsmalloc` 與 `vmalloc` 的差別在於在呼叫空間後， `zsmalloc` 會回傳一個 `unsigned long` 的 handle 作為呼叫空間的代號，若要取得可使用的地址需要再做 mapping，`vmalloc` 內部則會先做 mapping，所以直接會回傳 `void *`。
##### run_xvmalloc_benchmark
```c
static void run_xvmalloc_benchmark(size_t loops,
size_t blk_min,
size_t blk_max,
struct page **page_array,
u32 *offset_array,
size_t num_blks)
{
while (loops--) {
size_t next_idx = (size_t) prandom_u32() % num_blks;
size_t blk_size = get_random_block_size(blk_min, blk_max);
if (page_array[next_idx]) {
xv_free(xpool, page_array[next_idx], offset_array[next_idx]);
/* Insert the newly alloced block into the array at a random
* point.
*/
xv_malloc(xpool, blk_size, &page_array[next_idx], &offset_array[next_idx], __GFP_ZERO);
} else {
/* Insert the newly alloced block into the array at a random point.
*/
xv_malloc(xpool, blk_size, &page_array[next_idx], &offset_array[next_idx], __GFP_ZERO);
}
}
/* Free up all allocated blocks. */
for (size_t i = 0; i < num_blks; i++) {
if (page_array[i])
xv_free(xpool, page_array[i], offset_array[i]);
}
}
```
##### run_zsmalloc_benchmark
```c
static void run_zsmalloc_benchmark(size_t loops,
size_t blk_min,
size_t blk_max,
unsigned long *handle_array,
size_t num_blks)
{
while (loops--) {
size_t next_idx = (size_t) prandom_u32() % num_blks;
size_t blk_size = get_random_block_size(blk_min, blk_max);
if (handle_array[next_idx]) {
zs_free(zpool, handle_array[next_idx]);
/* Insert the newly alloced block into the array at a random
* point.
*/
handle_array[next_idx] = zs_malloc(zpool, blk_size, GFP_KERNEL);
} else {
/* Insert the newly alloced block into the array at a random point.
*/
handle_array[next_idx] = zs_malloc(zpool, blk_size, GFP_KERNEL);
}
}
/* Free up all allocated blocks. */
for (size_t i = 0; i < num_blks; i++) {
if (handle_array[i]){
zs_free(zpool, handle_array[i]);
}
}
}
```
#### user space
呼叫用 wirte 呼叫 kernel module，用 `offset` 決定要測試效能的 block size 區間，舉例 `offset` 為 0，測試 block min 即為 0 ，block max 為 0+32， write 最後一個參數用來控制要測試何種 allocator ， buf 目前沒有實質用途。
```c
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <unistd.h>
#define BENCH_DEV "/dev/bench"
#define MAX_OFFSET 16320
#define LOOPS 10000000
int main()
{
unsigned long long sz;
char write_buf[] = "testing writing";
int offset = MAX_OFFSET;
FILE *fptr_z;
FILE *fptr_v;
fptr_z = fopen("./txt/zsmalloc_bench.txt", "w");
fptr_v = fopen("./txt/xvmalloc_bench.txt", "w");
int fd = open(BENCH_DEV, O_RDWR);
if (fd < 0) {
perror("Failed to open character device");
exit(1);
}
for (int i = 0; i <= offset; i+=64) {
lseek(fd, i, SEEK_SET);
printf("now %d %d\n", i, i+64);
sz = write(fd, write_buf, 0);
printf("%d %d %.3f\n", i, i+64, sz * 1e-3/(double)LOOPS);
fprintf(fptr_v, "%d %d %.3f\n", i, i+64, sz * 1e-3/(double)LOOPS);
}
for (int i = 0; i <= offset; i+=64) {
lseek(fd, i, SEEK_SET);
printf("now %d %d\n", i, i+64);
sz = write(fd, write_buf, 1);
printf("%d %d %.3f\n", i, i+64, sz * 1e-3/(double)LOOPS);
fprintf(fptr_v, "%d %d %.3f\n", i, i+64, sz * 1e-3/(double)LOOPS);
}
fclose(fptr_z);
fclose(fptr_v);
close(fd);
return 0;
}
```
### 效能分析
#### 前置設定
為了避免會影響的效能測量的因素，需要做前置設定。而每次開機都要重新輸入命令很不方便，所以將效能相關的前置設定與程式執行包成了一個 measure.sh 檔，細節參照 [fibdrv-開發紀錄](https://hackmd.io/uHe0dpXJRZ292NfIKWApag)。
```bash
#!/bin/bash
CPUID=5
ORIG_ASLR=`cat /proc/sys/kernel/randomize_va_space`
ORIG_GOV=`cat /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor`
ORIG_TURBO=`cat /sys/devices/system/cpu/intel_pstate/no_turbo`
ORIG_SMT=`cat /sys/devices/system/cpu/smt/control`
sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
sudo sh -c "echo performance > /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor"
sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
sudo sh -c "echo off > /sys/devices/system/cpu/smt/control"
make run
sudo sh -c "echo $ORIG_ASLR > /proc/sys/kernel/randomize_va_space"
sudo sh -c "echo $ORIG_GOV > /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor"
sudo sh -c "echo $ORIG_TURBO > /sys/devices/system/cpu/intel_pstate/no_turbo"
sudo sh -c "echo $ORIG_SMT > /sys/devices/system/cpu/smt/control"
```
其中 make run 定義於 Makefile 中 ，Makefile 是用 [sysprog21/fibdrv](https://github.com/sysprog21/fibdrv) 去修改。
最後只須執行下面 shell ，即可完成效能測試。
```shell
這行只須執行一次
$ sudo chmod +x measure.sh
$ ./measure.sh
```
## zsmalloc xvmalloc 特性分析結論
### zsmalloc xvmalloc 效能比較
x : 分配的 block size 大小（範圍），假如 x 為 2000，分配的 block min 為 2000，block max 為 2000 + 64，單位為 bytes 。
y : 平均 malloc + free 的時間，單位為 us。
對於 xvmalloc ，如同 TLSF 在 size 越大時因越容易觸發一些 if 的判斷，所以時間上升。到約為 PAGE_SIZE 一半時有了大幅的成長，這是因為 xvmalloc block 是以 page 為單位，舉例當你今天要了 PAGE_SIZE/2 的空間，加上 OVERHEAD 後，此 page 剩餘的空間已經不足 PAGE_SIZE/2 ，所以當又一次 allocate PAGE_SIZE/2 的大小時，只能動態的重新要一個 page 來儲存，所以時間大幅上升，而原本的 page 剩下的空間就浪費了。至於大於 PAGE_SIZE 的 allocate 就不會成功，所以時間趨近於 0。
對於 zsmalloc 也相同，一樣會隨著 size 上升而時間上升，在約為 3000 時時間會大幅上升，這是因為當 allocate 的 size 靠近 PAGE_SIZE 時，會大幅增加動態新增 zspage 的機率。至於大於 PAGE_SIZE 的 allocate 就不會成功，所以時間趨近於 0。
至於兩個 allocator 的比較，可以看出除了 2000~3000 的區間外， zsmalloc 都比 xvmalloc 耗時還要久，這是因為雖然 zsmalloc 可以減少碎片化，但是其實作時新增 zspage 的成本會比 xvmalloc 新增一個 page 的代價還高。
至於 2000~3000 的區間，為甚麼可以遠低於 xvmalloc ，這是因為 zsmalloc 使用 zspage 的方式實現，一個 zsapge 橫跨多個 page ，所以不像 xvmalloc 那樣當 size 接近 PAGE_SIZE/2 時所在 page 剩下的空間就無法使用， zspage 橫跨多個 page 所以當又分配 PAGE_SIZE/2 的空間時還是有可以容納的 object 可使用。
**雖然時間成本較高，但卻大幅減少了在 xvmalloc 中嚴重的空間浪費 (碎片化) 問題， 所以 zsmalloc 漸漸取代了 xvmalloc ，最新的 linux 版本中，已經沒有 xvmalloc 了。**
### zsmalloc xvmalloc 效能比較（大範圍）
測試 block 範圍大時，有什麼樣的現象。
x : 執行的 50 次相同的設定。
y : 平均 malloc + free 的時間，單位為 us。
左圖為使用 zsmalloc 動態獲取 free block 的方法。
右圖為使用調整後的 xvmalloc 方法。
不同線代表不同 size range。
<div style="display: flex;">
<img src="https://hackmd.io/_uploads/H1fwH_Qdh.png" width="50%" height="50%">
<img src="https://hackmd.io/_uploads/rkMvBOX_3.png" width="50%" height="50%">
</div>
結果與上一種測試相同，無論是哪種實作方式，平均 alloc 的 size 越大，所花的時間也會上升。
測試環境的 PAGE_SIZE 為 4096。
0 ~ 2048 bytes ： 與上一種測試相同實作時新增 zspage 的成本會比 xvmalloc 新增一個 page 的代價還高。
0 ~ 4096 bytes ： 可以發現 xvmlloc 所花費的時間遠遠低於 zsmalloc ，這是因為 xvmalloc 基於 TLSF 的優點，每次 allocate 完剩下的空間，會重新加入 free list 中，給其他次 allocate 使用，而 zsmalloc 則是對應大小的 object 用完後，就必須動態新增 zspage，**這是 xvmalloc 的優勢**。
2048 ~ 4096 bytes：可以發現兩種 allocator 的耗費時間相近，可以從上一種測試發現，雖然 3000 ~ 4096 zsmalloc 的成本較高，但在 2048 ~ 3000 時成本卻遠低於 xvmalloc ，平均下來兩者花費的平均時間就會相近，而雖然從此圖看不出來，xvmalloc 其實浪費了大量的空間，**這是 zsmalloc 的優勢**。
## 其他 allocator 比較
### with kmalloc
小於 PAGE_SIZE/2 則是 xvmalloc 表現最為優異。
在 $PAGE\_SIZE/2 ～ PAGE\_SIZE*2/3$ zmalloc 表現最為優異。
超過 $PAGE\_SIZE*2/3$ 則是 kmalloc 表現最為優異。
超過 PAGE_SIZE 後只有 kmalloc 表現能成功運行。
### with vmalloc
要求超過 PAGE_SIZE 的空間在 kmalloc 以及 vmalloc 都有效，至於兩者差別還需要設計別的測試才可以知道。
參考資訊:
* [yvt/rlsf](https://github.com/yvt/rlsf)
* [xvMalloc](https://code.google.com/archive/p/compcache/wikis/xvMalloc.wiki)
* [AllocatorsComparison](https://code.google.com/archive/p/compcache/wikis/AllocatorsComparison.wiki)
* [War of allocators: TLSF in action](http://webkit.sed.hu/blog/20100324/war-allocators-tlsf-action)
* [mattconte/tlsf](https://github.com/mattconte/tlsf/blob/master/tlsf.c)
* [jserv/tlsf](https://github.com/jserv/tlsf-bsd)
Sign in with Wallet
Connect another wallet