# TLSF 概念與程式解析
> github [cin-cout/tlsf-bsd](https://github.com/cin-cout/tlsf-bsd)
## 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 大小。
64 位元系統對齊的 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`
Sign in with Wallet
Connect another wallet