Linux 核心專題: TLSF 實作

執行人: cin-cout
專題解說錄影
GitHub:

• cin-cout/tlsf-bsd
• cin-cout/allocator_benchmark

任務簡述

重做第 6 週測驗題的測驗四，搭配第 5 週教材提及的 tlsf-bsd，探討何以

$O(1)$ 時間複雜度可落實於記憶體配置器。

背景知識

建議把老師上課影片看完，要自己理解對齊以及 overhead 等實作其實蠻沒有效率的，原本嘗試自己理解看得我一頭霧水，浪費了不少時間。
你所不知道的 C 語言：記憶體管理、對齊及硬體特性篇

測驗五的第一題是一個基本的 first fit 記憶體配置器的實作，先理解完畢有助於更加了解記憶體配置器的程式，但第一題的程式碼存在不少問題。
2023q1 第 5 週測驗題 - 第一題

以下是解釋非常不錯的同學們的開發紀錄：
yanjiew
ItisCaleb
WangHanChi

TODO:

1. 研讀教材並紀錄認知及問題
   至少要涵蓋:

• TLSF: a new dynamic memory allocator for real-time systems
• Benchmarking Malloc with Doom 3
• TLSF: Part 1: Background, Part 2: The floating point

2. 解讀和改進程式碼
   重做第 6 週測驗題的測驗四，搭配上述來解釋何以
   $O(1)$ 時間複雜度可落實於記憶體配置器，又如何改進實作。
3. Linux 核心一度具備同為
   $O(1)$ 時間複雜度的 xvmalloc，不過隨後就被 zsmalloc 取代，請依據 git log 和 LWN 等第一手材料，探討核心開發者的考量因素。

在討論時，避免「舉燭」，應至少將 xvmalloc 移植到 userspace，搭配 tlsf-bsd 的測試和效能評比框架，分析其效益。

研讀 Benchmarking Malloc with Doom 3

該文講解怎麼實作偵測 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

free

可以看到無論在 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 ，詳見測驗五第一題，而是依照 free block 的大小，將每堆類似大小的 free block 建立一個 free list。所以每次在 alloc 一個新的空間時，都直接去最適合的大小的 free list 中尋找 free block，從而實現 good fit，而 mapping 技術就是用來尋找最適合的 free list。

TLSF (Two-Level Segregated Fit) 中使用二級的結構，加快記憶體存取速度並減少記憶體碎片化 (fragmentation)。

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 分配空間。

注意用語，參見:

• 資訊科技詞彙翻譯
• 詞彙對照表

整體概念

這邊畫一張圖來講解運作中的 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 實作解析

以下將解析老師實作的 jserv/tlsf 。

重要常數

64 位元系統對齊的 shift 為 3，亦即以 8 的倍數對齊，符合一個 word_size 大小。
32 位元系統對齊的 shift 為 2，亦即以 4 的倍數對齊，符合一個 word_size 大小。

/* 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

/* 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]。

#define BLOCK_SIZE_SMALL ((size_t) 1 << FL_SHIFT)

block 資料結構

先看 block 資料結構會比較理解前面一些關於 block 的常數。

block 的資料結構定義

這邊是對於記憶體配置器的概念的基本解釋，詳見測驗五第一題，先不考慮 prev。
此段解釋參考 yanjiew。
alloc 的空間為系統由 size 和 payload 組成。malloc 會回傳 payload 部份的指標。payload 為可以利用的空間，size 的值即為 payload 的大小。

--------------------------------------------------
| size | payload                                 |
--------------------------------------------------

未配置的空間除了 size 外，後面還會接續 prev 和 next 二個指標，分別指向上一個和下一個未配置空間，size 的值即為 prev + next + 空閒位置的大小。

--------------------------------------------------
| size | prev | next | ..........                |
--------------------------------------------------

上述二種狀態都可用 tlsf_block 結構來表示。size 為已配置和未配置空間都會使用的欄位，而 prev 和 next 只會在未配置空間使用。

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 演算法。

這裡的 prev_phys_block 就是 prev，block 是可以找到 prev 的，但其實 prev 是儲存在實體上一個 block 內，當上一個 block 被 alloc 後寫入資料，是可能蓋掉 prev 的，因為 prev 只是作為未被配置的記憶體合併時使用。而空閒 tlsf_block 的 size 指的是 next_free + prev_free + 空的位置 + prev(實體上下一個 block 的 prev)。

再回來看上面的常數設定。

/*一個 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)

最後如同測驗三，因為現在電腦多數都是 32 bits (4 bytes) 以上，所以其位置二進位最後二位必為 0，不會使用到，所以 block->header 的第一個 bit 用來儲存目前的 block 是否為 free，第二個 bit 用來儲存前一個的 block 是否為 free。

#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 演算法。

block + prev 的大小 + size 的大小 = payload 的位址，反之亦然。
offsetof 會獲取 tlsf_block_t 圖中 size (header) 成員相對於結構體起始地址的偏移量，即為 prev 的大小。
BLOCK_OVERHEAD 即為圖中 size (header) 的大小。

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 ，直接呼叫即可。

/* 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 *)。

/* 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，以下用程式碼以及圖例會更好的理解。

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〉如下：

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}$ 可化簡為

${\displaystyle \frac{2^f}{2^{SLI}}}$，

$size-2^f$ 除

$2^f/2^{SLI}$ 則可表示為

$(size-2^f)\times ({\displaystyle \frac{2^{SLI}}{2^f}})$。

下面程式碼只是將這個數學是換成用 bitwise 操作，以增加性能，解釋如下：

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 操作。

/* 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 需不需要更新。

/* 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 時會提到，或是直接參考測驗五第一題。

block_can_split

檢查的 block 是否能分割 size 出來， 當然 block size 要大於等於 size ，加上 sizeof(tlsf_block) 要確保底部實體上下一個 block 的 prev 有地方儲存。

見下圖，取自 esp-idf 的記憶體管理: TLSF 演算法。

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 的狀態。

/*把 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 才能實行此函式。

/* 把前此 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

用來實現切割與合併。

/*將給定 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 中並未找到關於 tlsf pool 的初始化，但初始化的狀態可以大大幫助理解程式碼，這邊先使用 esp-idf 的記憶體管理: TLSF 演算法 這篇文章的概念，見下圖。

這是一個 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 並未有 init 函式 而是使用 arena_grow arena_shrink 代替。

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

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。

/* 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 語言：記憶體管理、對齊及硬體特性篇。 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) 也會成立。

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 會提級。

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

$((siz{e}_t)1<<(log2floor(size)-S{L}_{S}HIFT))$ 等價於，

$2^f/SL\mathrm{\_}COUNT$ 解釋 ，mapping 時講過了，就是這個 size 所屬 SL 層的大小。

$size+t$ 原本的 size 加上所屬 SL 層的大小，一定會變到下一個 SL 層區間。

& ~t 代表加上後多出來的餘數就算了。

/* 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)。

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

作用如上面解釋，各個函式實作上面都介紹過了。

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 的基本運行流程，概念來自對測驗五第一題的理解。

在記憶體管理中，當一個 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])。

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

前置設定

為了避免會影響的效能測量的因素，需要做前置設定。而每次開機都要重新輸入命令很不方便，所以將效能相關的前置設定與程式執行包成了一個 measure.sh 檔，細節參照 fibdrv-開發紀錄。

#!/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 中 tlsf 會在沒有合適的 free block 時動態的從 pre-allocating 的空間中拿取新的空間，但考慮到 pre-allocate 的空間在 tlsf 執行時是不會被 tlsf 外的資料所使用的，放著也只是閒置著，所以可以在 tlsf init 時就把所有 pre-allocte 的空間放入 tlsf 內，可以減少因不斷動態增加空間的成本。

想法參考 mattconte/tlsf 實作了另一種 tlsf init 的方式：

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 arena grow/shrink 動態獲取 free block 的方法。
橘色為使用調整後的 tlsf_init 方法。

可以看出因為少了不斷動態增加空間的成本， tlsf_init 的方式效能有不小的提昇。而無論是哪種實作方式，平均 alloc 的 size 越大，所花的時間也會有略為的上升。

tlsf_init 效能比較（大範圍）

因為上張圖，每一項測資範圍區間僅有 64 bytes ，為了確認當申請的 block 範圍大一點時，是否有一樣的現象，所以又進行了測試。
x : 執行的 50 次相同的設定。
y : 平均 malloc + free 的時間，單位為 us。
左圖為使用 jserv/tlsf arena grow/shrink 動態獲取 free block 的方法。
右圖為使用調整後的 tlsf_init 方法。
不同線代表不同 size range。

結果與上一種測試相同， tlsf_init 的方式效能有不小的提昇。而無論是哪種實作方式，平均 alloc 的 size 越大，所花的時間也會有略為的上升。

另外可以從這個測試看出，因為在測試時 block size 是 random 的，使用 jserv/tlsf 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 所敘述，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。大部分與 TLSF 相同，此處特別講解考量 page 後的實作差異。

資料結構

xv_pool 等同於 tlsf_t 只是 free list 不是紀錄 block 的 ptr 而是 page 與 offset，page 以及 offset 意義後續會提到。

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。

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。

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 沒有儲存任何資料，就將其釋放。

	/* 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 架構

應闡述 zsmalloc 到底在解決什麼問題？開發動機是什麼？而非急著閱讀原始程式碼

jserv

參考資料

程式碼：zsmalloc.c

zsmalloc 的程式碼解析在網路上有很多了，所以這邊不特別對程式碼去做講解，只對基本架構去做解釋，有基本的的 allocator 知識再加上網路上的文章可以很快速的理解，以下是有用的網路文章：

1. 記憶體管理特性分析（一）：zsmalloc記憶體配置器分析
   程式碼乾淨整齊且有註解解釋，但解釋的很籠統。
2. zsmalloc 配置器源码分析
   解釋的較為詳細，但是程式碼排版不佳，圖片有些已經找不到了。

架構解析

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 zsmalloc 效能比較

github cin-cout/allocator_benchmark

前置設定

zsmalloc config 設定

1. 先確認 linux 版本

$ uname -a

2. 移動到存放 config 的地方，/usr/src/<linux version>

$ cd /usr/src/linux-headers-5.4.0-146-generic

3. 編輯 .config

把 .config 從唯讀換成可寫
$ sudo chmod +w .config
$ vim .config

4. 更改 zsmalloc 所需的 config

CONFIG_ZSMALLOC=y
CONFIG_ZPOOL=y
CONFIG_ZBUD=y
CONFIG_Z3FOLD=y
CONFIG_ZRAM=y

# optional
CONFIG_ZSMALLOC_STAT=y

改成 m 也可以，但就是要額外自己掛載 module，而不是開機自動掛載。
掛載方式如下：

zram 換成想掛載的 module 名稱
$ sudo modprobe zram

5. 重新開機

$ sudo reboot

zsmalloc vmalloc 效能分析實現

因為 linux kernel 已經有 <linux/zsmalloc.h> 想先測試 zsmalloc 在 kernel 的效能，bench 程式參考 tlsf-bsd 的 bench.c ，程式很直觀，不細作解釋，只是改寫了部份，改成 kernel 端執行，使用 character device driver ，架構參考 sysprog21/fibdrv 。

kernel

用 write 作為 usr 呼叫 kernel module 執行效能運算程式，用 client 傳入的 size 決定要測量哪種 allocator。

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

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

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

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 目前沒有實質用途。

#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-開發紀錄。

#!/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 去修改。

最後只須執行下面 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。

結果與上一種測試相同，無論是哪種實作方式，平均 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\mathrm{\_}SIZE/2～PAGE\mathrm{\_}SIZE\ast 2/3$ zmalloc 表現最為優異。
超過

$PAGE\mathrm{\_}SIZE\ast 2/3$ 則是 kmalloc 表現最為優異。
超過 PAGE_SIZE 後只有 kmalloc 表現能成功運行。

with vmalloc

要求超過 PAGE_SIZE 的空間在 kmalloc 以及 vmalloc 都有效，至於兩者差別還需要設計別的測試才可以知道。

參考資訊:

• yvt/rlsf
• xvMalloc
• AllocatorsComparison
• War of allocators: TLSF in action
• mattconte/tlsf
• jserv/tlsf