Linux 核心專題: TLSF 實作

執行人: a1091150

專題錄影與 GitHub 連結

:question: 提問清單

任務簡述

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

O (1)

時間複雜度可落實於記憶體配置器

TODO: 研讀教材並紀錄認知及問題

至少要涵蓋:

研讀教材

研讀論文 TLSF

在即時系統例如 RTOS (Real-Time Operating Systems) 下，每項操作或同種操作都需要在一定時間內回應。動態記憶體配置 (DSA; Dynamic storage allocation) 相關方法，在多數情況下有良好的回應時間，但是在 worst case 上可能超出時間。因此，在記憶體配置與釋放的操作上，TLSF 限定在

θ (1)

時間複雜度。

在論文中假設的應用場景：一定時間內回應、低程度的記憶體碎片、在有限或固定的記憶體配置上操作

TLSF 核心機制

在論文中主要介紹：

使用兩層去紀錄 free block
mapping 機制將要求的記憶體大小轉換到指定的層

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

TLSF 使用兩層位元，紀錄擁有的 free block

第一層(First level)：將 free block 以 2 的冪分類，使用對應位置的位元表示是否有 free block
第二層(Second level)：再將 free block 分成 4 個區間，分別用位元紀錄，透過串列去串接每個區間內的 free block

當程式要求記憶體 size 時，透過 size 計算分別對應第一層的位元與第二層位元，即可查詢是否有 free block。若在該位元沒有 free block，也可透過位元操作查詢鄰近的 free block。整個操作皆在

θ (1)

時間複雜度內。

在論文中，使用mapping 機制轉換 size 成為指定第一層與第二層位元，以 size = 460 為例：

s i z e = 460_{10} = 0000 000 \overset{f l = 8}{\overset{⏞}{1}} \underset{s l = 12}{\underset{⏟}{1100}} 1100_{2}

第一層的位元透過 find least set(fls) 計算取得
第二層的位元取第一層的位元之後 4 個位元

研讀教材 Part 1: Background and Part 2: The floating point

參考 Part 1: Background 文中的mapping_insert 程式碼，該程式碼引用自 GitHub - mattconte/tlsf

void mapping_insert(size_t size, int* fli, int* sli)
{ 
  int fl, sl;
  if (size < 256)
  {
    fl = 0;
    sl = (int)size / 8;
  }
  else
  {
    fl = fls(size);
    sl = (int)(size >> (fl - 5)) ^ 0x20;
    fl -= 7;
  }
  *fli = fl;
  *sli = sl;
}

計算第一層 fl 數值上，取 fls 數值
計算第二層 sl 數值上，與前述取得第一層位元的後 4 個位元相同，透過 ^ 0x20 移除第一層的位元。

這裡有個特別的 fl -= 7 的程式碼，根據 Part 2: The floating point 文中敘述，可以將此 mapping_insert 當作把整數轉換程浮點數中 exponent 減去 bias 的過程，唯此轉換前後一定是正數。

研讀 tlsf-bsd

tlsf-bsd 依照 TLSF 論文實作 mapping 機制，這裡來查看記憶體是如何被操作。

了解 `struct tlsf_block` 結構體

查看結構體 struct tlsf_block

/* Block status bits are stored in the least significant bits (LSB) of the
 * size field.
 */
#define BLOCK_BIT_FREE ((size_t) 1)
#define BLOCK_BIT_PREV_FREE ((size_t) 2)
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;

size_t header;：
- 表示此 free block 的大小
- 透過記憶體對齊的特性，最低位元用來此 block 表示為 in-use block or free block，以 BLOCK_BIT_FREE 設定
- 透過記憶體對齊的特性，最低第二位元用來表示前一個 block 為 in-use block or free block，以 BLOCK_BIT_PREV_FREE 設定
struct tlsf_block *next_free, *prev_free;：透過串列串接擁有相近大小的 free block
struct tlsf_block *prev;：除了串列串接相近大小的 free block 外，每個 free block 的最後一個元素被指派此 free block 的起始位址，讓下個 free block 可以透過此元素直接取得 free block 以合併。
當兩個 free block 合併前，參考下圖，block2->prev 指向 block 的最後一個元素，該元素有 block1 的記憶體位址。若把 block1 size 當作 block1 的一部分，可以認為這兩個 block 重疊。

                       +--------+ <--- block1
                       |        |
                       +--------+ <--- block1->header
                       |        |
                    +- +--------+ <--- block1->next_free
                    |  |        |
                    |  |        |
             size --+  |        |
                    |  |        |
                    |  +--------+ <--- block2->prev
                    +- +--------+ <--- block2->header
                       |        |
                       +--------+

當 free block 轉為 in-use block 時，struct block_t 經由 *block_payload() 計算 payload，回傳指定位址，以圖片區分 in-use block 與 free block 使用差異：

                 in-use block      free block

        block ───► ┌───────┐       ┌───────┐ ◄─── block
                   │       │       │       │
block->header ───► ├───────┤       ├───────┤ ◄─── block->header
                   │       │       │       │
      payload ───► ├───────┤       ├───────┤ ◄─── block->next_free
                   │       │       │       │
                   │       │       ├───────┤ ◄─── block->prev_free
                   │ space │       │ space │
                   │       │       │       │
                   └───────┘       └───────┘

透過 `tlsf_malloc` 了解 `struct tlsf_block` 結構體位址計算

參考 Makefile 檔案，分別在 test.c 與 bench.c 以 tlsf_resize() 函式，向系統取得固定的記憶體空間。這裡解說 gcc test.c tlsf.c 編譯後的程式。

透過修改 test.c 的 main() 函式，觀察其行為

// test.c
int main(void)
{
    PAGE = (size_t) sysconf(_SC_PAGESIZE); // 4096
    MAX_PAGES = 20 * TLSF_MAX_SIZE / PAGE;
    tlsf_t t = TLSF_INIT;
    const size_t page_size = PAGE;
    void *p1 = tlsf_malloc(&t, (1 << 10) + 1);
    void *p2 = tlsf_malloc(&t, page_size - 1);
    tlsf_free(&t, p1);
    tlsf_free(&t, p2);
}

// tlsf.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);
}

要求記憶體時 void *p1 = tlsf_malloc(&t, (1 << 10) + 1);，會經由

tlsf_malloc(size)：取得記憶體位址，將 size 透過 adjust_size(size) 進位到鄰近的 ALIGN_SIZE = 1 << 3 的倍數
block_find_free()：取得 free block 記憶體位址，但沒有找到 free block
arena_grow()：申請的記憶體空間，並作為 free block 加入到 tlsf level 中
tlsf_resize()：透過 mmap 申請固定大小記憶體空間
再度透過 block_find_free() 取得 free block

觀察 arena_grow 中 block 的記憶體位址計算，來了解 struct tlsf_block 的每個成員作用：

INLINE tlsf_block_t *to_block(void *ptr)
{
    tlsf_block_t *block = (tlsf_block_t *) ptr;
    return block;
}

#define BLOCK_OVERHEAD (sizeof(size_t))
static bool arena_grow(tlsf_t *t, size_t size)
{
    size_t req_size =
        (t->size ? t->size + BLOCK_OVERHEAD : 2 * BLOCK_OVERHEAD) + size;
    void *addr = tlsf_resize(t, req_size);
    if (!addr)
        return false;
    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->header |= size | BLOCK_BIT_FREE;
    block = block_merge_prev(t, block);
    block_insert(t, block);
    tlsf_block_t *sentinel = block_link_next(block);
    sentinel->header = BLOCK_BIT_PREV_FREE;
    t->size = req_size;
    check_sentinel(sentinel);
    return true;
}

第一次要求記憶體配置 tlsf_malloc(&t, (1 << 10) + 1)：

req_size = 2 * BLOCK_OVERHEAD + size
block->header |= size | BLOCK_BIT_FREE;，並加入到 tlsf level 中
block_link_next() 連結下一個的 block，相當於指派 sentinel->prev = block
sentinel 表示記憶體中最後一個 block

在 to_block() 轉換成 free block 的位址計算，最後以圖表列出 block 與 sentinel 分別指向的位址

                       +--------+ <--- block
                       |        |
     mmap of addr ---> +--------+ <--- block->header
                       |  1088  |
                    +- +--------+ <--- block->next_free
                    |  |        |
                    |  |        |
             size --+  |        |
                    |  |        |
                    |  +--------+ <--- sentinel->prev
                    +- +--------+ <--- sentinel->header
      sizeof(size_t)|  |        |
End of address ---> +- +--------+

block 指向不可寫入的記憶位址，但是可以指派 block->header； sentinel 記錄最高位址，以重疊的區塊 sentinel->prev 紀錄 block 位址。
最終透過 block_find_free() 與 block_use() 回傳 payload 記憶體位址。

TODO: 解讀和改進程式碼

重做第 6 週測驗題的測驗四，搭配上述來解釋何以

O (1)

時間複雜度可落實於記憶體配置器，又如何改進實作。

此 heap allocator 與 tlsf-bsd 實作不同之處在於

Level 設計差異：
- TLSF 採取 first level 與 second level，first level 以位元位置跟 2 的冪區分、再以 second level 分成 4 個區間
- heap allocator 以一維陣列表示，對應成員 headsbits 陣列，陣列中的每個位元位置對應一種 base size。在此程式碼實作與命名中，每 15 個位元視為同個 level。
Metadata 儲存方式差異：
- TLSF 使用 tlsf_block 儲存該記憶體空間的 metadata，並以記憶體位址做減法以回推 tlsf_block
- heap allocator 將 metadata 分離儲存，不能藉由記憶體做減法回推 metadata：
  - 利用 Linux 提供的 posix_memalign 使得記憶體對齊，將記憶體位址計算求出對應的 headsbits 與 bitfield
  - 成員 bitfield 用於紀錄鄰近記憶體空間的狀態，可視為二維陣列，若取其中的一維陣列的元素，可表示同個 level 下，該鄰近空間的使用情況。

解讀程式碼

透過修改程式碼，並搭配 GDB 檢查變數數值、部分函式寫成 Python 程式碼，藉此觀察 struct heap 每個成員的作用。

#define BASE_SIZE_MIN (0x00000010U)
#define BASE_SIZE_MAX (0xF0000000U)
#define BASE_SIZES_COUNT (105)
#define MAIN_BASE_SIZE_COUNT (7U)
#define HEADS_BITS_SIZE (((BASE_SIZES_COUNT + 31) >> 5))
struct heap {
    uint32_t headsbits[HEADS_BITS_SIZE]; // 4
    uint32_t *bitfield[MAIN_BASE_SIZE_COUNT]; // 7
    uint8_t *hdata;
    uint32_t hsize;
    uint32_t hdcnt;
    uint32_t bscnt;
    chunk_t *heads[0];
};

uint32_t headsbits[HEADS_BITS_SIZE];：某個位元對應的 base size 是否有 free block
uint32_t *bitfield[MAIN_BASE_SIZE_COUNT]：用於記錄該多個記憶體區塊的使用情況
uint8_t *hdata;：傳入記憶體起始位址
uint32_t hdcnt;：bitfield 陣列元素數量
chunk_t *heads[0];：用於串接 free block。 free block 的記憶體空間會被用於串接每個 chunk_t 資料

`main()` 函式

將 SIZE 修改成較小的 SIZE，藉由引入與修改巨集數值 #define BC 5 來測試 headsbits 陣列數值。
每個位元代表不同的 base size

#define BC 5
int main(int argc, char *argv[])
{
    const uint32_t SIZE = (1 << 4) << BC;
    void *data = memalign(SIZE, SIZE);
    /* ... */
    return 0;
}

void *data = memalign(SIZE, SIZE); 使用 posix_memalign()，取得的記憶體位址與 SIZE 對齊。可參考 man posix_memalign 說明

int posix_memalign(void **memptr, size_t alignment, size_t size);
The address of the allocated memory will be a multiple of alignment, which must be a power of two and a multiple of sizeof(void *).

因此 SIZE 具有以下特性：

與 void * 對齊
只有一個位元被設定且為最高位
是 base size

解讀 `headsbits[HEADS_BITS_SIZE]` 成員

H1->headbits 是用來表示此 heap 以被設定的位元，此位元對應一種 base size，來表示擁有的 free block

解讀方法

初始化 headsbits 使用到 closest_base_size(SIZE), base_size_to_index(used_size) 與 base_size_from_index(index) 函式

closest_base_size(SIZE) 函式將 SIZE 轉換成大於等於 SIZE 的 base size，由於 SIZE 對齊的特性，轉換前後數值相同
base_size_to_index(SIZE) 函式將 SIZE 轉換為 base size 的索引值
base_size_from_index(index) 函式為 base_size_to_index(SIZE) 的反函式

觀察函式 base_size_from_index 的輸出：

index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
對應 base size	16	32	48	64	80	96	112	128	144	160	176	192	208	224	240	256	512	768	1024	1280	1536	1792	2048	2304	2560	2816	3072	3328	3584	3840	4096	8192

從以上可以推得一個規律，每 15 位元視為同個 level，一共 7 個 level：

第 00 ～ 14 位元：鄰近位元對應的 base size 之間相差一個
$16^{1}$
第 15 ～ 29 位元：鄰近位元對應的 base size 之間相差一個
$16^{2}$ ，第 15 位元為第 14 位元的 2 倍
第 30 ～ 44 位元：鄰近位元對應的 base size 之間相差一個
$16^{3}$ ，第 30 位元為第 29 位元的 2 倍

在 heap_create() 函式中，透過 populate_heads() 函式設定指定的位元。

heap_t *heap_create(uint8_t *const address, uint32_t const size)
{
    /* ... */
    new_heap->headsbits[0] = 0;
    new_heap->headsbits[1] = 0;
    new_heap->headsbits[2] = 0;
    new_heap->headsbits[3] = 0x007FFFFFU;
    populate_heads(new_heap, address, size);
    /* ... */
}

static void populate_heads(heap_t *const h,
                           void const *const data,
                           uint32_t const size)
{
    /* ... */
    uint32_t used_size = closest_base_size(size);
    uint32_t i = base_size_to_index(used_size);
    h->headsbits[i >> 5] |= 0x80000000U >> (i & 31);
}

h->headsbits[i >> 5] |= 0x80000000U >> (i & 31); 將設定指定的位元，來表示 heap 中擁有的 free block。

解讀 `bitfield[MAIN_BASE_SIZE_COUNT]` 成員

用來記錄每個 free block 使用的情形，利用 chunk_status_t ，以兩個位元表示對應的記憶體位置的區塊使用情況

typedef enum {
    STATUS_FREE = 0x02U,
    STATUS_ALLOC = 0x00U,
    STATUS_ALLOC_HEAD = 0x01U,
    STATUS_SPLIT = 0x03U,
} chunk_status_t;

其中可以利用或修改以下函式，來查看對應的 bitfield 數值，或使用經由 heap_alloc 取得的記憶體位址，檢查該對應的 chunk_status_t 數值

static chunk_status_t chunk_get_status(uint32_t const *const bf, uint32_t const idx);
static uint32_t heap_get_address_status_priv(...)
chunk_status_t heap_get_address_status(heap_t const *const h, void const *const a)

解讀方法

觀察 heap_create() 函式中藉由 total_bitfield_count 取得所有 bitfield 需要的記憶體空間，利用 needed_bitfield_count 計算分配給每個區域需要多少空間，set_bf_ptr() 初始化每個 bitfield 的數值。

heap_t *heap_create(uint8_t *const address, uint32_t const size)
{
    /* ... */
    uint32_t const tot_bf_count = total_bitfield_count(size);
    void *const mem_bf = malloc(tot_bf_count * sizeof(uint32_t));
    /* ... */
    for (uint32_t i = 0, start = 0; i < MAIN_BASE_SIZE_COUNT; ++i) {
        uint32_t const nbc = needed_bitfield_count(size, i);
        set_bf_ptr(i, nbc, new_heap, start, mem_bf, size);
        start += nbc;
    }
    /* ... */
}

仿照 needed_bitfield_count() 函式撰寫成 Python 程式碼觀察其數量

def needed_bitfield_count(size: int, index: int):
    count = size >> ((index + 1) << 2)
    return (count + 15) // 16
def show_need_bitfield_each_alloc(i: int):
    size = 1 << i
    xx = [needed_bitfield_count(size, x) for x in range(7)]
    return xx

輸入參數SIZE = 1 << i 來表示原本 SIZE = 1 << 4 << BC 的輸入，輸出指標陣列中 bitfield[MAIN_BASE_SIZE_COUNT] 每個陣列的元素數量。

In [3]: show_need_bitfield_each_alloc(4) # SIZE = 1 << 4
Out[3]: [1, 0, 0, 0, 0, 0, 0]

In [4]: show_need_bitfield_each_alloc(5) # SIZE = 1 << 5
Out[4]: [1, 0, 0, 0, 0, 0, 0]

In [5]: show_need_bitfield_each_alloc(6) # SIZE = 1 << 6
Out[5]: [1, 0, 0, 0, 0, 0, 0]

In [6]: show_need_bitfield_each_alloc(7) # SIZE = 1 << 7
Out[6]: [1, 0, 0, 0, 0, 0, 0]

In [7]: show_need_bitfield_each_alloc(8)
Out[7]: [1, 1, 0, 0, 0, 0, 0]

In [8]: show_need_bitfield_each_alloc(9)
Out[8]: [2, 1, 0, 0, 0, 0, 0]

In [10]: show_need_bitfield_each_alloc(10)
Out[10]: [4, 1, 0, 0, 0, 0, 0]

In [11]: show_need_bitfield_each_alloc(11)
Out[11]: [8, 1, 0, 0, 0, 0, 0]

In [12]: show_need_bitfield_each_alloc(12)
Out[12]: [16, 1, 1, 0, 0, 0, 0]

In [13]: show_need_bitfield_each_alloc(13)
Out[13]: [32, 2, 1, 0, 0, 0, 0]

**bitfield 型態為 uint32_t，以兩個位元表示 chunk_status_t 狀態，因此一個 **bitfield 元素可以表示 16 個記憶體區塊的狀態。

以 SIZE = 1024 = 1 << 10 = 1 << 4 << 6 為例，一次最小配置的記憶體是 16 位元組：

若全部皆以 heap_alloc(H1, 16) 取得記憶體位址，則需要
$2^{6}$ 個 chunk_status_t 去記錄狀態，可用
$2^{6} / 16 = 2^{2} = 4$ 個 uint32_t，符合 Python 程式輸出
若全部皆以 heap_alloc(H1, 256) 取得記憶體位址，則需要
$2^{2}$ 個 chunk_status_t 去記錄狀態，可用
$⌈ 2^{2} / 16 ⌉ = 1 = 1$ 個 uint32_t，符合 Python 程式輸出

觀察 `bitfield` 數值狀態

透過修改 chunk_get_status() 函式中，新增 printf("%u %x\n", idx >> 4, bf[idx >> 4]); 觀察 bitfield 數值變化。

static chunk_status_t chunk_get_status(uint32_t const *const bf,
                                       uint32_t const idx)
{
    uint32_t const sub = ~idx & 15u;
    printf("%u %x\n", idx >> 4, bf[idx >> 4]);
    return (bf[idx >> 4] >> (sub << 1)) & 0x03U;
}
/* ... */
#define BC 4
int main(int argc, char *argv[])
{
    const uint32_t SIZE = (1 << 4) << BC;
    /* ... */
    void *foo[(1 << BC)];
    for (int i = 0; i < (1 << BC); i++) {
        foo[i] = heap_alloc(H1, 16);
        printf("%02d ", i);
        chunk_status_t cs = heap_get_address_status(H1, foo[i]);
    }
    return 0;
}

每行 heap_alloc 函式依序輸出 foo 索引值、bitfield 索引值、該 bitfield 數值，單一行heap_free 函式輸出bitfield 索引值、該 bitfield 數值

00 0 aaaaaaa9
01 0 aaaaaaa5
02 0 aaaaaa95
03 0 aaaaaa55
04 0 aaaaa955
05 0 aaaaa555
06 0 aaaa9555
07 0 aaaa5555
08 0 aaa95555
09 0 aaa55555
10 0 aa955555
11 0 aa555555
12 0 a9555555
13 0 a5555555
14 0 95555555
15 0 55555555

觀察 heap_alloc() 函式輸出情況，以第一行 00 0 aaaaaaa9 為例，最低十六進制的數值為

9_{10} = 1001_{2}

，取最低兩個位元，得到 chunk_status_t 狀態為 STATUS_ALLOC_HEAD = 0x01U

解讀 `chunk_t *heads[0];` 成員

*heads[0]; 可參考 GNU Zero Length 說明，GNU Extension 支援

在前述 headsbits 的位元用來表示是否有 free block， chunk_t *heads[0]; 則用來串接每個 free block 的記憶體位址。

typedef struct chunk {
    struct chunk *prev, *next;
} chunk_t;

解讀方法

觀察 heap_create() 初始化的方式與使用 heap_alloc 時候其使用的 chunk_t 的方式

heap_t *heap_create(uint8_t *const address, uint32_t const size)
{
    /* ... */
    uint32_t const cs = CLZ(size) & 0x1CU;
    uint32_t const hd_cnt = ((24 - cs) >> 2) * 15 + ((size >> (28 - cs)) & 0x0FU);
    heap_t *new_heap = malloc(sizeof(*new_heap) + (hd_cnt * sizeof(chunk_t *)));
    populate_heads(new_heap, address, size);
}

static void populate_heads(heap_t *const h,
                           void const *const data,
                           uint32_t const size)
{
    uint32_t used_size = closest_base_size(size);
    uint32_t i = base_size_to_index(used_size);

    h->heads[i] = (chunk_t *) data;
    h->heads[i]->prev = NULL;
    h->heads[i]->next = NULL;
    /* ... */
}

在 heap_create() 中，hd_cnt 的實際數值剛好是 base_size_to_index(size) + 1。例如 SIZE = 1 << 28， hd_cnt = 91 且 base_size_to_index(SIZE) = 90，在 populate_heads 函式中，剛好是指定 h->heads[90] 陣列中擁有 free block

經過多個 heap_alloc() 與 heap_free() 交錯執行後，該 free block 的記憶體空間會被轉換成並用於 chunk_t

解讀 `heap_alloc()` 函式

經過前述 heap_t 結構體成員的每個作用，多少可以推得 O(1) 如何的運作模式。
來解讀 heap_alloc(heap_t *const h, uint32_t const sz) 函式實作，主要有以下步驟：

經由 next_available_head_index() 函式取得，尋找符合 needed_sz 的 free block。
在符合的 free block 中，取得符合 needed_sz 的 free block，並將剩餘 free block 切割並加入至對應大小的 h->heads 中

以 SIZE = 1 << 16 = 65536 為例，查看其中一種程式碼行為：











































#define BC 12
int main(int argc, char *argv[])
{
    const uint32_t SIZE = (1 << 4) << BC;
    void *data = memalign(SIZE, SIZE);
    heap_t *H1 = heap_create(data, SIZE);
    void *foo = heap_alloc(H1, 16);
    /* ... */
    return 0;
}

void *heap_alloc(heap_t *const h, uint32_t const sz)
{
    /* ... */
    uint32_t const index = next_available_head_index(h, needed_sz);
    chunk_t *c = h->heads[index];
    uint32_t const extra_sz = found_sz - needed_sz;
    
    /* the combined number of iterations for both 'for' loops in this
     * function is 7 max, hence the 0(1) complexity */
    for (;; --bs_level, shift -= 4) {
        uint32_t const lvl_remain_sz = (extra_sz >> shift) & 0x0FU;

        if (0 != lvl_remain_sz) {
            uint32_t const head =
                (bs_level << 4) - bs_level + lvl_remain_sz - 1;
            chunk_t *const hd = h->heads[head];
            update_next(h, c, hd);
            update_prev(h, c, NULL);
            update_head(h, head, c);
            if (hd) {
                update_prev(h, hd, c);
            }
            c = (chunk_t *) ((uint8_t *) c + (lvl_remain_sz << shift));
        }
        lvl_needed_sz = needed_sz >> shift;
        if (0 != lvl_needed_sz)
            break;
        uint32_t const split = ((uint32_t) c - base) >> shift;
        bf_set_split(h->bitfield[bs_level], split);
    }
    /* ... */
}

當 heap_alloc(H1, 16) 時

chunk_t *c 變數為回傳的記憶體位址
next_available_head_index 取得 index = 45 對應原本 SIZE = 65536 的 free block
65536 - 16 = 65520，可以預期將 65520 分割成不同的 base size：65520 = 61440 + 3840 + 240
- 61440 對應 base size index 為 44
- 3840 對應 base size index 為 29
- 240 對應 base size index 為 14
在第 20 行程式碼，先將剩餘的 free block 將入到 base size 對應的 h->heads[head] 之中，再計算 c 的記憶體位址

根據註釋

/* the combined number of iterations for both 'for' loops in this
     * function is 7 max, hence the 0(1) complexity */

可以設想最多的執行次數的 worst case，例如 SIZE = 1 << 31 並且 heap_alloc(H1, 16) 取最小單位的空間，最終在所有 7 個 level 中，都放置一個 free block

#define BC 27
int main(int argc, char *argv[])
{
    const uint32_t SIZE = (1 << 4) << BC;
    void *data = memalign(SIZE, SIZE);
    heap_t *H1 = heap_create(data, SIZE);
    void *foo = heap_alloc(H1, 16);
    /* ... */
    return 0;
}

TODO: 研究 Linux 核心的 xvmalloc 和 zsmalloc

Linux 核心一度具備同為

O (1)

時間複雜度的 xvmalloc，不過隨後就被 zsmalloc 取代，請依據 git log 和 LWN 等第一手材料，探討核心開發者的考量因素。

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

參考資訊:

xvmalloc: 探討核心開發者的考量的因素

在 git log 中未有標注原因，在 LWN.net 搜尋 xvmalloc，有以下描述：
節錄自 LWN.net: In-kernel memory compression, The zsmalloc allocator

To improve density, the xvmalloc allocator was written, based on the two-level sequential fit (TLSF) algorithm.
Xvmalloc provided high density for some workloads and was the initial default allocator for zram and for the frontswap-driven portion of the initial zcache.
It was found, however, that the high density led to poor fragmentation characteristics, especially for zsize distributions that skewed fat.
Xvmalloc has since been discarded (though remnants of it survive through Linux 3.8.)

The "zsmalloc" allocator, proposed by Seth Jennings, is aimed at a specific use case.
The slab allocators work by packing multiple objects into each page of memory; that works well when the objects are small, but can be problematic as they get larger.
In the worst case, if a kernel subsystem routinely needs allocations that are just larger than PAGE_SIZE/2, only one object will fit within a page.

staging: zsmalloc: memory allocator for compressed pages
This patchset introduces a new memory allocation library named
zsmalloc. zsmalloc was designed to fulfill the needs
of users where:

Memory is constrained, preventing contiguous page allocations
larger than order 0(single page) and

Allocations are all/commonly greater than half a page.

在 xvmalloc 實作中，如果絕大多數的要求記憶體空間，接近並大於 PAGE_SIZE / 2，則該 page 只會有一個物件，形成嚴重的記憶體浪費。 zsmalloc 主要解決此使用情境。

:warning: 應闡述什麼場景特別重視上述的記憶體運用方式。
:notes: jserv

移植 xvmalloc

Github: xvmalloc

xvmalloc 與前面 TLSF-bsd 實作上不同：

記憶體配置 xv_malloc(... size) 只能要求小於一個 page size(Linux 上 page size = 4096)
size 會進位成 8 的倍數，包含本身 4 位元組的 block 開銷，最大配置大小為 4088 位元組(4096 - 8)

在移植 xvmalloc 的時候，考量以上特性，把 tlsf-bsd 中的測試流程修改成 xvmalloc 的應用情境

解說移植後程式碼

目前的程式碼可以在 macOS 與 Ubuntu Linux 22.04 上運作。

在移植的方式上，盡量不更動 xvmalloc 程式碼，透過撰寫缺少的函式、結構體。

xv_malloc.c, xv_malloc.h 與 xv_malloc_int.h：移植後的程式碼主體
types.h：移植必要的巨集
test_page.h：移植 linux module header 的函式的標頭檔
test.c：主要撰寫 main() 函式與 benchmark

在原本的 xvmalloc 中，每次空間不足時，透過 alloc_page() 向系統申請一個 page，使用 xv_malloc() 會取得 page 結構體與 offset，以此取得記憶體位址。

來查看真如 LWN 敘述的記憶體浪費的情形。在 test.c 透過配置兩組指定記憶體大小，大於 page size / 2 與 4，並限制總體 page 數量，即可發現記憶體配置失敗，符合 LWN 敘述的記憶體浪費：

int main(int argc, char **argv)
{
    MAX_PAGES = 1; // Only one page can be required
    /* ... */
    test_alloc();
    /* ... */
}

void test_alloc()
{
    struct xv_pool *pool = xv_create_pool();
    struct page *page;
    u32 offset;
    const u32 size = XV_MAX_ALLOC_SIZE / 2 + 1;
    int x1 = xv_malloc(pool, size, &page, &offset);
    int x2 = xv_malloc(pool, 4, &page2, &offset2); // Fail to acquire memory
    /* ... */
}

benchmark

使用測量環境

5.19.0-43-generic

Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  4
  On-line CPU(s) list:   0-3
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-4250U CPU @ 1.30GHz

gcc (Ubuntu 11.3.0-1ubuntu1~22.04.1) 11.3.0

依照 tlsf-bsd 中的測試方式：

若已取得記憶體，低機率 realloc() 或高機率 tlsf_free()
若無記憶體空間，要求記憶體 tlsf_malloc()

static void run_alloc_benchmark()
{
    while (loops--) {
        size_t next_idx = (size_t) rand() % num_blks;
        size_t blk_size = get_random_block_size(blk_min, blk_max);

        if (blk_array[next_idx]) {
            if (rand() % 10 == 0) {
                blk_array[next_idx] =
                    tlsf_realloc(&t, blk_array[next_idx], blk_size);
            } else {
                tlsf_free(&t, blk_array[next_idx]);
                blk_array[next_idx] = tlsf_malloc(&t, blk_size);
            }
        } else {
            blk_array[next_idx] = tlsf_malloc(&t, blk_size);
        }
        if (clear)
            memset(blk_array[next_idx], 0, blk_size);
    }

    /* Free up all allocated blocks. */
    for (size_t i = 0; i < num_blks; i++) {
        if (blk_array[i])
            tlsf_free(&t, blk_array[i]);
    }
}

在 xvmalloc 中沒有 realloc 函式，直接移除 realloc 函式，限制記憶體配置範圍 32 ~ 4088。

static void run_alloc_benchmark()
{
    struct xv_pool *pool = xv_create_pool();
    assert(pool);
    while (loops--) {
        size_t next_idx = (size_t) rand() % num_blks;
        size_t blk_size = get_random_block_size(blk_min, blk_max);
        if (blk_array[next_idx]) {
            struct page *page = blk_array[next_idx];
            u32 offset = blk_offset_array[next_idx];
            xv_free(pool, page, offset);
            blk_array[next_idx] = NULL;
            blk_offset_array[next_idx] = 0;
        } else {
            struct page *page;
            u32 offset;
            int r = xv_malloc(pool, blk_size, &page, &offset);
            if (!r) {
                blk_array[next_idx] = page;
                blk_offset_array[next_idx] = offset;
            }
        }

        if (clear && blk_array[next_idx]) {
            char *addr = blk_array[next_idx];
            u32 offset = blk_offset_array[next_idx];
            memset(addr + offset, 0, blk_size);
        }
    }
    /* ... */
}

獲得輸出：

$ gcc xvmalloc.c test.c
$ ./a.out
blk_min=512 to blk_max=512
512:512:10000000:0:87900160:0.703468: took 0.703468 s for 10000000 malloc/free
benchmark loops of 512-512 bytes.  ~0.070 us per loop

./a.out -s 32:4088
blk_min=32 to blk_max=4088
32:4088:10000000:0:96399360:1.237614: took 1.237614 s for 10000000 malloc/free
benchmark loops of 32-4088 bytes.  ~0.124 us per loop

./a.out -s 32:4088 -c
blk_min=32 to blk_max=4088
32:4088:10000000:1:96399360:1.592345: took 1.592345 s for 10000000 malloc/free
benchmark loops of 32-4088 bytes.  ~0.159 us per loop

與 tlsf-bsd 對比

$ ./build/bench
blk_min=512 to blk_max=512
512:512:10000000:0:6025216:0.480467: took 0.480467 s for 10000000 malloc/free
benchmark loops of 512-512 bytes.  ~0.048 us per loop

$ ./build/bench -s 32
blk_min=32 to blk_max=512
32:512:10000000:0:3923968:0.611649: took 0.611649 s for 10000000 malloc/free
benchmark loops of 32-512 bytes.  ~0.061 us per loop

$ ./build/bench -s 10:12345
blk_min=10 to blk_max=12345
10:12345:10000000:0:68145152:1.400485: took 1.400485 s for 10000000 malloc/free
benchmark loops of 10-12345 bytes.  ~0.140 us per loop

用 perf stat --repeat 100 ./a.out -s 32:4088 去測量

 Performance counter stats for './a.out -s 32:4088' (100 runs):

          2,666.90 msec task-clock                #    1.000 CPUs utilized            ( +-  0.18% )
                22      context-switches          #    8.333 /sec                     ( +-  5.54% )
                 2      cpu-migrations            #    0.758 /sec                     ( +- 25.99% )
            23,383      page-faults               #    8.857 K/sec                    ( +-  0.00% )
     6,884,795,731      cycles                    #    2.608 GHz                      ( +-  0.10% )
     7,809,646,003      instructions              #    1.15  insn per cycle           ( +-  0.00% )
     1,003,886,833      branches                  #  380.259 M/sec                    ( +-  0.00% )
        24,409,076      branch-misses             #    2.43% of all branches          ( +-  0.02% )

           2.66722 +- 0.00591 seconds time elapsed  ( +-  0.22% )

用 perf stat --repeat 100 ./a.out -s 32:4088 -c 測量，-c 參數會將取得的記憶體空間指派 0。

 Performance counter stats for './a.out -s 32:4088 -c' (100 runs):

          3,740.16 msec task-clock                #    1.014 CPUs utilized            ( +-  0.18% )
                26      context-switches          #    7.100 /sec                     ( +-  4.53% )
                 0      cpu-migrations            #    0.000 /sec                   
            23,384      page-faults               #    6.385 K/sec                    ( +-  0.00% )
     9,560,078,934      cycles                    #    2.610 GHz                      ( +-  0.15% )
     8,235,466,240      instructions              #    0.87  insn per cycle           ( +-  0.00% )
     1,068,148,108      branches                  #  291.669 M/sec                    ( +-  0.00% )
        28,288,702      branch-misses             #    2.65% of all branches          ( +-  0.09% )

           3.68915 +- 0.00996 seconds time elapsed  ( +-  0.27% )

使用

$ perf record -g --call-graph dwarf ./a.out -s 32:4088 -c
$ perf report --stdio -g graph,0.5,caller > foo.txt

得到以下結果

Perf Graph

main
|          
|--93.41%--bench_main
|          |          
|           --93.33%--run_alloc_benchmark
|                     |          
|                     |--29.72%--xv_free
|                     |          |          
|                     |          |--5.65%--test_flag
|                     |          |          
|                     |          |--4.58%--insert_block
|                     |          |          |          
|                     |          |           --1.27%--__set_bit
|                     |          |          
|                     |          |--2.52%--remove_block
|                     |          |          |          
|                     |          |           --0.66%--get_ptr_atomic
|                     |          |          
|                     |          |--1.15%--set_flag
|                     |          |          
|                     |          |--0.93%--get_ptr_atomic
|                     |          |          
|                     |           --0.75%--BLOCK_NEXT
|                     |          
|                     |--28.92%--xv_malloc
|                     |          |          
|                     |          |--5.59%--remove_block_head
|                     |          |          |          
|                     |          |           --0.70%--__clear_bit
|                     |          |          
|                     |          |--5.01%--find_block
|                     |          |          |          
|                     |          |          |--0.75%--get_index
|                     |          |          |          
|                     |          |           --0.56%--test_bit
|                     |          |          
|                     |          |--3.54%--set_flag
|                     |          |          
|                     |          |--3.52%--grow_pool
|                     |          |          |          
|                     |          |          |--1.77%--alloc_page
|                     |          |          |          |          
|                     |          |          |           --1.33%--find_page_unused
|                     |          |          |          
|                     |          |           --0.55%--set_flag
|                     |          |          
|                     |          |--2.50%--insert_block
|                     |          |          |          
|                     |          |           --0.68%--__set_bit
|                     |          |          
|                     |          |--0.84%--get_ptr_atomic
|                     |          |          
|                     |          |--0.80%--clear_flag
|                     |          |          
|                     |          |--0.69%--set_blockprev
|                     |          |          
|                     |           --0.51%--put_ptr_atomic
|                     |          
|                     |--11.96%--rand
|                     |          |          
|                     |           --11.87%--__random
|                     |                     |          
|                     |                      --1.26%--__random_r
|                     |          
|                     |--7.33%--__memset_avx2_unaligned_erms
|                     |          
|                     |--6.78%--get_random_block_size
|                     |          |          
|                     |           --4.55%--rand
|                     |                     __random
|                     |                     |          
|                     |                      --2.68%--__random_r
|                     |          
|                      --1.59%--0x55b65b21a214

附錄 RLSF

可參考官方文件 Rust Doc RLSF
GitHub RLSF

我剛開始學習 Rust，因此可能部分環節有誤。

在有之前 TLSF 的認識之後，來了解如何使用 Rust 去實作，參考 RLSF 範例。

fn main() {
    let mut pool = [MaybeUninit::uninit(); 65536];
    let mut tlsf: Tlsf<'_, u16, u16, 12, 16> = Tlsf::new();
    tlsf.insert_free_block(&mut pool);
}

先來了解 Rust 語法跟其作用：

MaybeUninit，可參考 Rust Doc: MaybeUninit
A wrapper type to construct uninitialized instances of T
建立一變數，Rust 會初始化該數值，例如 let x: i32 會自動初始化為 0。
透過 MaybeUninit 取得未初始化的記憶體空間。

[type; length] 語法糖：建立一組陣列 Rust Vec
A contiguous growable array type with heap-allocated contents, written Vec
在記憶體空間上為連續。

pool 變數取得的連續記憶體空間，相當於 C 語言的 void *pool = malloc(65536) ，作為 block 加入至 tlsf allocator 中。

pub struct Tlsf<'pool, FLBitmap, SLBitmap, const FLLEN: usize, const SLLEN: usize> {
    fl_bitmap: FLBitmap,
    /// `sl_bitmap[fl].get_bit(sl)` is set iff `first_free[fl][sl].is_some()`
    sl_bitmap: [SLBitmap; FLLEN],
    first_free: [[Option<NonNull<FreeBlockHdr>>; SLLEN]; FLLEN],
    _phantom: PhantomData<&'pool ()>,
}

依據 Rust Doc: Generic Type 特性，可在編譯時期決定該型態：

FLBitmap 成員：First level 的位元對應的 Rust 整數型態
SLBitmap 成員：Second level 的位元對應的 Rust 整數型態
FLLEN 成員：First level 用到的位元數量
SLLEN 成員：Second level 用到的位元數量
_phantom 成員：根據 Rust Doc: PhantomData: Zero-sized type used to mark things that “act like” they own that data type. Rust 強調所有權(Ownership)，這裡假裝擁有資料的所有權。
'pool 語法可參考 Rust by Example: Explicit annotation，表示在 TLSF 結構體執行時間，pool 的生命週期夠長（活得夠久）

根據註釋，此實作版本的 RLSF 最低配置 16 位元組

First level
                                                                   "FLLEN = 8"
                           ╭─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────╮
    "fl_bitmap: FLBitmap ="│  0  │  0  │  0  │  1  │  0  │  0  │  0  │  0  │
                           ├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
                 "min size"│ 2¹¹ │ 2¹⁰ │  2⁹ │  2⁸ │  2⁷ │  2⁶ │  2⁵ │  2⁴ │
                           ╰─────┴─────┴─────┴──┬──┴─────┴─────┴─────┴─────╯

將 pool 當作 free block 加入到 TLSF 中

pub fn insert_free_block(&mut self, block: &'pool mut [MaybeUninit<u8>]) -> impl Send + Sync {
        // Safety: `block` is a mutable reference, which guarantees the absence
        // of aliasing references. Being `'pool` means it will outlive `self`.
        unsafe { self.insert_free_block_ptr(NonNull::new(block as *mut [_] as _).unwrap()) };
    }

參考 The Rust Programming Guide: unsafe，使用 unsafe 去操作與 C 語言實作中相同的記憶體位址計算：

To switch to unsafe Rust, use the unsafe keyword and then start a new block that holds the unsafe code.
You can take five actions in unsafe Rust that you can’t in safe Rust, which we call unsafe superpowers.
Those superpowers include the ability to:

Dereference a raw pointer

Call an unsafe function or method

Access or modify a mutable static variable

Implement an unsafe trait

Access fields of unions

透過 Rust raw pointer，將該 block 的記憶體位址取出。

透過文件查詢，可以使用內建的函式 core::ptr::addr_of 取得記憶體位址。
在 Rust Playground 實驗下，可獲得一樣的輸出

fn main() {
    let a = 42;
    let memory_location = &a as *const i32 as usize;
    let mf = core::ptr::addr_of!(a) as usize;
    println!("{}", memory_location); // 140723548430676
    println!("{}", mf); // // 140723548430676
    
}

NonNull 可當作是支援 raw pointer 的結構體，參考 Rust Doc: NonNull

This is often the correct thing to use when building data structures using raw pointers, but is ultimately more dangerous to use because of its additional properties.
If you’re not sure if you should use NonNull<T>, just use *mut T!

Linux 核心專題: TLSF 實作

專題錄影與 GitHub 連結

任務簡述

TODO: 研讀教材並紀錄認知及問題

研讀教材

研讀論文 TLSF

TLSF 核心機制

研讀教材 Part 1: Background and Part 2: The floating point

研讀 tlsf-bsd

了解 struct tlsf_block 結構體

透過 tlsf_malloc 了解 struct tlsf_block 結構體位址計算

TODO: 解讀和改進程式碼

解讀程式碼

main() 函式

解讀 headsbits[HEADS_BITS_SIZE] 成員

解讀方法

解讀 bitfield[MAIN_BASE_SIZE_COUNT] 成員

解讀方法

觀察 bitfield 數值狀態

解讀 chunk_t *heads[0]; 成員

解讀方法

解讀 heap_alloc() 函式

TODO: 研究 Linux 核心的 xvmalloc 和 zsmalloc

xvmalloc: 探討核心開發者的考量的因素

移植 xvmalloc

解說移植後程式碼

benchmark

附錄 RLSF

了解 `struct tlsf_block` 結構體

透過 `tlsf_malloc` 了解 `struct tlsf_block` 結構體位址計算

`main()` 函式

解讀 `headsbits[HEADS_BITS_SIZE]` 成員

解讀 `bitfield[MAIN_BASE_SIZE_COUNT]` 成員

觀察 `bitfield` 數值狀態

解讀 `chunk_t *heads[0];` 成員

解讀 `heap_alloc()` 函式