rbtmalloc 開發紀錄

contributed by < WangHanChi >

rbtmalloc

問題紀錄

thestinger/allocator 編譯失敗

原本的程式碼 clone 下來進行編譯的時候會出現這個問題

$ make
cc -std=c11 -fPIC -D_GNU_SOURCE -fvisibility=hidden -Wall -Wextra -flto -O2 -DNDEBUG   -c -o purge.o purge.c
cc -std=c11 -fPIC -D_GNU_SOURCE -fvisibility=hidden -Wall -Wextra -flto -O2 -DNDEBUG -Wl,--as-needed -flto -O2 -shared alloc.o bump.o chunk.o extent.o huge.o memory.o mutex.o purge.o -lpthread -o alloc.so
/usr/bin/ld: huge.o (symbol from plugin): in function `purge_ratio':
(.text+0x0): multiple definition of `purge_ratio'; alloc.o (symbol from plugin):(.text+0x0): first defined here
/usr/bin/ld: purge.o (symbol from plugin): in function `purge_init':
(.text+0x0): multiple definition of `purge_ratio'; alloc.o (symbol from plugin):(.text+0x0): first defined here
collect2: error: ld returned 1 exit status
make: *** [Makefile:18: alloc.so] Error 1

後來詳細了解原因後發現是 purge_ratio 在 purge.h 定義，而 purge.h 又被 alloc.c 與 huge.c 所 include ，才導致出現變數重複的問題，因此稍微修改程式碼就可以正常編譯

修改的程式碼

purge.h

#ifndef PURGE_H
#define PURGE_H

- long int purge_ratio;
+ extern long int purge_ratio;
void purge_init(void);

#endif

這樣就可以正常編譯了

$ make
cc -std=c11 -fPIC -D_GNU_SOURCE -fvisibility=hidden -Wall -Wextra -flto -O2 -DNDEBUG   -c -o alloc.o alloc.c
alloc.c:850:13: warning: ‘cfree’ specifies less restrictive attributes than its target ‘free’: ‘leaf’, ‘nothrow’ [-Wmissing-attributes]
  850 | EXPORT void cfree(void *ptr) __attribute__((alias("free")));
      |             ^~~~~
In file included from alloc.c:11:
/usr/include/stdlib.h:555:13: note: ‘cfree’ target declared here
  555 | extern void free (void *__ptr) __THROW;
      |             ^~~~
cc -std=c11 -fPIC -D_GNU_SOURCE -fvisibility=hidden -Wall -Wextra -flto -O2 -DNDEBUG   -c -o bump.o bump.c
cc -std=c11 -fPIC -D_GNU_SOURCE -fvisibility=hidden -Wall -Wextra -flto -O2 -DNDEBUG   -c -o chunk.o chunk.c
cc -std=c11 -fPIC -D_GNU_SOURCE -fvisibility=hidden -Wall -Wextra -flto -O2 -DNDEBUG   -c -o extent.o extent.c
cc -std=c11 -fPIC -D_GNU_SOURCE -fvisibility=hidden -Wall -Wextra -flto -O2 -DNDEBUG   -c -o huge.o huge.c
cc -std=c11 -fPIC -D_GNU_SOURCE -fvisibility=hidden -Wall -Wextra -flto -O2 -DNDEBUG   -c -o memory.o memory.c
cc -std=c11 -fPIC -D_GNU_SOURCE -fvisibility=hidden -Wall -Wextra -flto -O2 -DNDEBUG   -c -o mutex.o mutex.c
cc -std=c11 -fPIC -D_GNU_SOURCE -fvisibility=hidden -Wall -Wextra -flto -O2 -DNDEBUG   -c -o purge.o purge.c
cc -std=c11 -fPIC -D_GNU_SOURCE -fvisibility=hidden -Wall -Wextra -flto -O2 -DNDEBUG -Wl,--as-needed -flto -O2 -shared alloc.o bump.o chunk.o extent.o huge.o memory.o mutex.o purge.o -lpthread -o alloc.so
cc -std=c11 -fPIC -D_GNU_SOURCE -fvisibility=hidden -Wall -Wextra -flto -O2 -DNDEBUG  -Wl,--as-needed -flto -O2  test_small.c alloc.o bump.o chunk.o extent.o huge.o memory.o mutex.o purge.o  -lpthread -o test_small
cc -std=c11 -fPIC -D_GNU_SOURCE -fvisibility=hidden -Wall -Wextra -flto -O2 -DNDEBUG  -Wl,--as-needed -flto -O2  test_large.c alloc.o bump.o chunk.o extent.o huge.o memory.o mutex.o purge.o  -lpthread -o test_large
cc -std=c11 -fPIC -D_GNU_SOURCE -fvisibility=hidden -Wall -Wextra -flto -O2 -DNDEBUG  -Wl,--as-needed -flto -O2  test_huge.c alloc.o bump.o chunk.o extent.o huge.o memory.o mutex.o purge.o  -lpthread -o test_huge

mmap 可以取用超過請求的空間

我們可以知道使用 mmap 系統呼叫的時候，所請求的尺寸會對齊 page 的大小，像是如果請求 4095 bytes 或是 30 bytes 都會返回一個 4096 bytes 的大小回來 (在我的設備上)，但是我做了一個小小的實驗，程式碼如下

程式碼

int main()
{
    long pageSize = sysconf(_SC_PAGESIZE);
    printf("Page size: %ld\n", pageSize);
    int *test = mmap(NULL, 5000, PROT_READ | PROT_WRITE,
                          MAP_SHARED | MAP_ANONYMOUS, -1, 0);
    if (test == MAP_FAILED) {
        perror("mmap");
        return 1;
    }
    long allocatedSize = pageSize * ((4097 + pageSize - 1) / pageSize);
    printf("Allocated size: %ld\n", allocatedSize);
    for(int i = 0 ; i < 2100; i++){
        // printf("%d ", i);
        test[i] = 5;
    }
    for(int i = 0 ; i < 2100; i++){
        // printf("%d / %d ", i, test[i]);
    }
    printf("\n");
    munmap(test, allocatedSize);
}

執行結果

$ gcc mmap.c 
$ ./a.out 
Page size: 4096
Allocated size: 8192

主要就是配置一個 8192 bytes 的空間，接著用 int 型別填滿它，原本預期是只能填入 2048
個 int ，但是如程式碼一樣填入了 2100 個卻是可以正常執行的，不知道為何會這樣。

記憶體概念筆記

memory_commit

使用 mmap 系統呼叫分配虛擬記憶體之後，這塊虛擬記憶體已經映射到進程的虛擬地址空間中了。但是，這個虛擬記憶體可能只是一個空的映射區域，實際的實體記憶體頁面還未分配或者還未初始化。所以，如果你想在這個虛擬記憶體中存儲數據，就需要使用 memory_commit 系統呼叫，讓作業系統為這個虛擬記憶體分配實體記憶體頁面，並將其初始化為 0 或其他的數據。

在 Linux 中，可以使用 mmap 系統呼叫分配一個虛擬記憶體區域，然後使用 mprotect 系統呼叫將這個區域設置為可讀可寫，最後使用 memory_commit 函數為這個區域分配實體記憶體頁面

void *addr = mmap(NULL, size, PROT_NONE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
mprotect(addr, size, PROT_READ | PROT_WRITE);
memset(addr, 0, size);

memory_decommit

在使用 munmap 系統呼叫釋放已經分配的虛擬記憶體時，通常不需要先使用 memory_decommit 函數取消映射區域的實體記憶體頁面。因為 munmap 函式會自動釋放該映射區域的實體頁面，並且會清空所有已經映射的內容。

事實上，memory_decommit 函數是一個專門用於取消映射區域的實體記憶體頁面的系統呼叫。如果你使用 memory_decommit 函數取消了映射區域的實體記憶體頁面，再使用 munmap 函數釋放虛擬記憶體時，系統可能會拋出錯誤或者行為不可預測。因此，在正常情況下，不需要在 munmap 前使用 memory_decommit。

// 將這個虛擬記憶體區域清空
memset(addr, 0, size);

// 使用 munmap 釋放虛擬記憶體區域
munmap(addr, size);

虛擬記憶體大小

在 Linux 64 位版本下，虛擬記憶體的大小是從 0x0000000000000000 到 0x7fffffffffff，也就是 128TB（2的47次方）。這個範圍被稱為「Canonic Virtual Address Space」（簡稱 CVA）。

Transparent Hugepage

可以透過以下命令來取得 HugePageSize 為 2 MB

$ cat /proc/meminfo | grep Hugepagesize
Hugepagesize:       2048 kB

並且透過以下命令來看到自己有沒有開始這個功能

$ cat /sys/kernel/mm/transparent_hugepage/enabled
always [madvise] never

可以看到 [ ] 在 madvise 的位置，代表者只在MADV_HUGEPAGE標記的 VMA 使用 THP

Huge Pages

Huge pages 是從 Linux Kernel 2.6 後被引入的，目的是通過使用大頁的記憶體來取代傳統的 4kb 記憶體頁，以適應越来越大的記憶體，讓作業系统可以支持现代硬體架構的大頁功能。
Huge pages 有两種格式大小： 2MB 和 1GB ， 2MB 頁的大小適合用於 GB 大小的記憶體 (Ex. 我們目前所使用的電腦)， 1GB 頁大小適合用於 TB 级别的記憶體； 2MB 是預設的大小。

Transparent Huge page

是一種在 Linux 作業系統中的記憶體管理機制，主要用於提高大型應用程式的性能。這種機制允許 kernel 自動管理大型記憶體頁（稱為“大頁”），這些頁比常規頁大許多。大頁的大小通常為 2MB 或1GB，相較於 4KB 的標準頁大小，可以減少記憶體管理的開銷和提高記憶體讀取/寫入的效率。

透明大頁支持機制允許 kernel 自動將一些散裝的標準頁合併為大頁，從而減少了管理頁表的開銷。這種機制還允許 kernel 自動將散裝的小頁轉換為大頁，從而減少記憶體碎片化的問題，並且可以更有效地利用記憶體。

透明大頁支持機制還有一個重要的優點是，它幾乎不需要應用程式的修改即可實現。這意味著應用程式可以繼續使用標準的記憶體分配和管理技術，而無需對程式碼進行修改。這種透明性使得大多數應用程式可以輕鬆地利用透明大頁支持機制，而不會帶來任何性能或兼容性問題。

並且由於 Huge pages 很難手動管理，而且通常需要對程式碼進行重大的更改才能有效的使用，因此 RHEL 6 開始引入了 Transparent Huge Pages （ THP ）， THP 是一個抽象層，能夠自動創建、管理和使用傳統大頁 (Huge pages)。

MADVISE 系統呼叫

從 man page 看起

$ man madvise

需要 include 的函式庫

#include <sys/mman.h>

語法

int madvise(void *addr, size_t length, int advice);

功能
提供給 kernel 關於記憶體使用的建議，要特別注意還有另外一個實作是 posix_madvise(3)

關於 advice 的引數有以下幾種

MADV_NORMAL
- 沒有特殊待遇。這是默認值。
MADV_RANDOM
- 期望頁面引用是隨機的。
MADV_SEQUENTIAL
- 期望頁面引用按順序排列。
MADV_WILLNEED
- 期望在不久的將來存取。
MADV_DONTNEED
- 不要指望在不久的將來存取。(目前，應用程序已在給定範圍內完成，因此內核可以釋放與其關聯的資源。)
MADV_HUGEPAGE
- 在地址和長度指定的範圍內的頁面上啟用透明大頁面(THP)。
MADV_NOHUGEPAGE
- 確保由addr和length指定的地址範圍內的內存不會被透明的大頁支持。

mmap & populate

map_populate 是 mmap() 系統呼叫的一個 flag，用於指示 kerenl 應在映射期間立即將文件中的所有內容讀入到新創建的映射區域中。這樣可以提高後續對這些內容的存取速度，因為所有資料已經存在於頁面快取中，而不必等到實際存取這些頁面時才進行disk I/O。

使用 map_populate 標誌可以顯著提高文件映射的性能，但需要額外的記憶體空間和 I/O 運算。因此，只有在確定需要快速且頻繁地存取整個映射區域的情況下才應使用 map_populate 標誌。

優點
- 使用 map_populate 可以讓程式在第一次存取新映射的記憶體時，避免因 page fault 產生的頁錯誤中斷，進而提高程式的運行效率。因為當 mmap 設置 MAP_POPULATE 標誌時， kernel 會在進行映射時將文件的內容直接讀取到物理頁中，這樣就可以避免第一次存取時因 page fault 而造成的缺頁中斷。
缺點
- 使用 map_populate 可能會導致一定程度上的性能下降。這是因為 kernel 在 mmap 函數調用時，需要在文件系統和文件快取之間進行多次的頁面交換，這會導致額外的 I/O 操作和 CPU 資源的消耗。此外，對於非常大的文件或共享記憶體區域，kernel 可能無法在 mmap 調用期間完成整個映射區域的填充，這樣可能會導致一些頁面在第一次存取時仍然需要進行缺頁中斷。

thestinger/allocator 學習筆記

`rb.h`

首先先看到 rb.h ，可以發現它與 quiz4 的 rb.h 是差不多的，因此這裡就不過多進行介紹
詳細的筆記可以參考 wanghanchi / linux2023-quiz4 與 wanghanchi / linux2023-tree

`test_small.c`

這段程式碼測試了程式在多執行緒情況下，能否正確地分配及收回記憶體。特別是在這種分配的記憶體數量是比較小 (16 Bytes) 且大量 (10000000個) 的情況下。

使用了 alloc_so 來進行測試，發現可以正常執行並且檢查回傳值也是 0

$ LD_PRELOAD=./alloc.so ./test_small
$ echo $?
0

`test_large.c`

在這段程式碼中，使用 malloc 來配置了一個大小為 4096 * 4 (16KB) 的記憶體區域，然後使用多次 realloc 來改變其大小。在每次 realloc 調用之後，我們都檢查返回的指標是否與原始指標相同，以確認是否發生了記憶體區域的移動。

可以從註解看到 // in-place shrink 與 // in-place expand 。如果需要重新分配的記憶體大小比先前的還要小的話，是會將已分配的記憶體空間縮小至指定的大小; 相對地，若是要重新分配的空間比原本的還要大的話，就會指向新分配的更大記憶體。

直接從 realloc 這個程式碼開始看!

首先先了解對於 small 與 large 的 size 定義

#define LARGE_ALIGN (sizeof(struct large))
#define LARGE_MASK (sizeof(struct large) - 1)
#define MIN_ALIGN 16
#define SLAB_SIZE (64 * 1024)
#define CACHE_SIZE (16 * 1024)
#define MAX_SMALL 512
#define LARGE_CHUNK_HEADER ((sizeof(struct chunk) + LARGE_MASK) & ~LARGE_MASK)
#define MAX_LARGE (CHUNK_SIZE - (LARGE_CHUNK_HEADER + sizeof(struct large)))

可以得知 MAX_SMALL 為 512 ，而 MAX_LARGE 為 ((4096 * 1024) - (32 + 32)) = 4194240

接著看到從 realloc 的其中一段程式碼看到原地縮小以及原地擴張的條件為 <= MAX_LARGE 還有 >= MAX_SMALL ，也就是說要 realloc 的大小在 512 ~ 4194240 之間就不會去改變記憶體的初始位置而只有改變大小

if (old_size <= MAX_LARGE && real_size <= MAX_LARGE &&
    old_size > MAX_SMALL && real_size > MAX_SMALL) {
    size_t real_size = (size + LARGE_MASK) & ~LARGE_MASK;
    if (!large_realloc_no_move(ptr, old_size, real_size)) {
        return ptr;
    }
}

接著一樣測試看看程式

$ LD_PRELOAD=./alloc.so ./test_large 
$ echo $?
0

回傳值為 0 ，代表沒有問題 !

`test_huge.c`

這段程式碼主要也是在測試 malloc 與 realloc 的一些行為，主要可以分成以下幾點

在沒有改變配置大小的情況下進行重新配置
進行縮小並釋放多餘的記憶體
使用 madvise 來進行告知作業系統關於記憶體的配置建議
當無法在原地進行擴張時，進行重新分配
當重新分配後記憶體位置改變時，檢查是否被移動到新的位置

首先，上面已知道 CHUNK_SIZE 為 4096 * 1024 = 4194304 ，因此只要分配了一個 CHUNK_SZIE 就會直接超出 MAX_LARGE 的大小

接著看到 realloc 的程式碼，可以看到如果超過了 MAX_LARGE 的大小之後，就會使用 huge_realloc

if (old_size > MAX_LARGE && size > MAX_LARGE) {
    return huge_realloc(cache, ptr, old_size, CHUNK_CEILING(size));
}

再來看到 huge_realloc 的程式碼

void *huge_realloc(struct thread_cache *cache, void *ptr, size_t old_size, size_t new_real_size) {
    if (new_real_size > old_size) {
        if (!huge_no_move_expand(ptr, old_size, new_real_size)) {
            return ptr;
        }
        return huge_move_expand(cache, ptr, old_size, new_real_size);
    } else if (new_real_size < old_size) {
        huge_no_move_shrink(ptr, old_size, new_real_size);
    }
    return ptr;
}

可以看到如果 new_real_size < old_size ，就會不改變原本這塊記憶體的初始位置，並且進行大小裁剪; 如果 new_real_size > old_size 的話就會先嘗試不改動初始位置進行配置，如果失敗的話才去重新分配一塊新的記憶體位置; 而至於位什麼不考慮 new_real_size == old_size 的情況是因為在 realloc 函式的一開始就有檢查兩個大小是否一樣，因此不會有這種情況發生。

接著繼續往下查看 huge_no_move_expand

static bool huge_no_move_expand(void *ptr, size_t old_size, size_t new_size) {
    bool failure = true;
    void *expand_addr = (char *)ptr + old_size;
    size_t expand_size = new_size - old_size;

    struct arena *arena = get_huge_arena(ptr);
    struct chunk_recycler *chunks = get_recycler(arena);
    maybe_lock_arena(arena);
    if (chunk_recycle(chunks, expand_addr, expand_size, CHUNK_SIZE)) {
        if (unlikely(memory_commit(expand_addr, expand_size))) {
            chunk_free(chunks, expand_addr, expand_size);
        } else {
            huge_update_size(arena, ptr, new_size);
            failure = false;
        }
    }
    maybe_unlock_arena(arena);
    return failure;
}

其中 memory_commit 的用處是將之前使用 mmap 分配的虛擬記憶體 page 實際分配到實體記憶體中。在 Linux 中，mmap 分配的虛擬記憶體 page 不會直接分配到實體記憶體中，而是分配到虛擬記憶體區域（Virtual Memory Area，VMA）中，當應用程式實際使用該 page 時，VMA 才會將其分配到實體記憶體中，這個過程也被稱為 page fault。

memory_commit 函式會呼叫 mprotect 函式，將指定的位址和大小的記憶體區域的保護權限設定為可讀可寫。由於在 Linux 中只有具有寫權限的頁才會被分配到實體記憶體中，因此透過將記憶體區域的保護權限設定為可讀可寫，就可以將之前分配的虛擬記憶體頁分配到實體記憶體中。

接著回去看到 huge_realloc 這個函式，可以看到如果有進到 huge_move_expand 這個函式的話，就會如同註解所說的用到 MREMAP 這個系統呼叫，從 man page 可以看到它會重新映射一個已經存在的虛擬記憶體區域，並且可以改變這個記憶體的大小。

接著看回 test_huge.c ，可以看到註解一段寫著 // madvise purge ，從 man page 可以知道他是要告知作業系統這塊記憶體不會被用到，可以進行釋放

從 huge_move_expand 這個函式中的 memory_decommit 函式中可以發現這個系統呼叫並且註明了使用 MADV_DONTNEED

接著就進行程式測試

$ LD_PRELOAD=./alloc.so ./test_huge 
$ echo $?
1

發現 main 的回傳值竟然不是 0 ，於是開始尋找哪個部份回傳 1 的，最後發現是在第 54 行的時候 return 的
















// mmap(NULL, CHUNK_SIZE * 16, ...)
    void *dest = malloc(CHUNK_SIZE * 16);
    if (!dest) return 1;

    // madvise purge
    free(dest);

    // moved via MREMAP_MAYMOVE|MREMAP_FIXED to dest
    //
    // the source is mapped back in (MREMAP_RETAIN landing would be nicer)
    p = realloc(p, CHUNK_SIZE * 16);
    if (p != dest) return 1;

    // madvise purge
    free(p);
    return 0;

可以用個簡單的實驗，將 54 行的回傳值修改成 10 ，並重新測試

$ echo $?
10

可以看到確實是這個部份進行回傳的，看來 p 跟 dest 並不會使用同一個記憶體地址

bool memory_remap_fixed(void *addr, size_t old_size, void *new_addr, size_t new_size) {
    return mremap(addr, old_size, new_size, MREMAP_MAYMOVE|MREMAP_FIXED, new_addr) == MAP_FAILED;
}

從 memory_remap_fixed 這個函式看到使用了 MREMAP_MAYMOVE|MREMAP_FIXED 這樣的 flags 給作業系統，代表可能在配置記憶體的過程中作業系統會幫我們尋找可配置的位置，並且不會與其他的重疊如果有找到的話就會進行移動，但是如果失敗就會留在原本的位置。

所以我認為這邊會進行 return 應該是正確的。

`alloc.c`

主要想要了解這個專案對於記憶體是如何進行管理的

可以看到從測試文件 test_small, test_large, test_huge 看到這個分配器應該是有針對三種尺寸的記憶體來進行分配的。

slab (小尺寸)

/* This struct is defined in arena.h */
struct slab {
    struct slab *next;
    struct slab *prev;

    size_t size;
    struct slot *next_slot;
    struct slot *end;

    uint16_t count;
    uint8_t data[];
};

large (大尺寸)

/* This struct is defined in arena.h */
struct large {
    size_t size;
    void *prev;
    rb_node(struct large) link_size_addr;
    max_align_t data[];
};

typedef rb_tree(struct large) large_tree;
rb_proto(, large_tree_size_addr_, large_tree, struct large)

huge (超大尺寸)

/* This struct is defined in extent.h */
struct extent_node {
    union {
        struct {
            void *addr;
            size_t size;
            rb_node(struct extent_node) link_size_addr;
            rb_node(struct extent_node) link_addr;
        };
        struct extent_node *next;
    };
};

typedef rb_tree(struct extent_node) extent_tree;
rb_proto(, extent_tree_szad_, extent_tree, struct extent_node)
rb_proto(, extent_tree_ad_, extent_tree, struct extent_node)

接著在用一個大的結構包住這三個記憶體管理器

/* This struct is defined in arena.h */
struct arena {
    alignas(CACHELINE) mutex mutex;

    // intrusive singly-linked list
    struct slab *free_slab;

    // intrusive circular doubly-linked list, with this sentinel node at both ends
    struct slab partial_slab[N_CLASS];

    large_tree large_size_addr;
    struct chunk *free_chunk;

    struct chunk_recycler chunks;
    void *chunks_start;
    void *chunks_end;

    struct extent_node *huge_nodes;
    extent_tree huge;
};

接著這些的初始化定義會是在 malloc_init 與 malloc_init_slow 這幾個函式

malloc_init_slow

/* This function is defines in alloc.c */
static bool malloc_init_slow(struct thread_cache *cache) {
    if (likely(atomic_load_explicit(&initialized, memory_order_consume))) {
        thread_init(cache);
        return false;
    }

    mutex_lock(&init_mutex);

    if (atomic_load_explicit(&initialized, memory_order_consume)) {
        mutex_unlock(&init_mutex);
        thread_init(cache);
        return false;
    }

    if (unlikely(init_failed)) {
        return true;
    }

    n_arenas = get_nprocs();
    arenas = bump_alloc(sizeof(struct arena) * n_arenas, alignof(struct arena));
    if (!arenas) {
        init_failed = true;
        mutex_unlock(&init_mutex);
        return true;
    }

    if (pthread_key_create(&tcache_key, tcache_destroy)) {
        init_failed = true;
        mutex_unlock(&init_mutex);
        return true;
    }

    memory_init();
    chunk_init();
    huge_init();
    purge_init();

    struct rlimit limit;
    void *reserved = NULL;
    arena_initial_va_log2 = size_log2(INITIAL_VA / n_arenas);
    size_t arena_initial_va = (size_t)1 << arena_initial_va_log2;
    size_t total_initial_va = arena_initial_va * n_arenas;
    if (arena_initial_va >= CHUNK_SIZE
        && !getrlimit(RLIMIT_AS, &limit) && limit.rlim_cur == RLIM_INFINITY) {
        reserved = memory_map_aligned(NULL, total_initial_va, CHUNK_SIZE, false);
        if (reserved) {
            reserved_start = reserved;
            reserved_end = (char *)reserved + total_initial_va;
        }
    }

    for (int i = 0; i < n_arenas; i++) {
        struct arena *arena = &arenas[i];
        if (mutex_init(&arena->mutex)) {
            init_failed = true;
            mutex_unlock(&init_mutex);
            return true;
        }
        for (size_t bin = 0; bin < N_CLASS; bin++) {
#ifndef NDEBUG
            arena->partial_slab[bin].prev = (struct slab *)0xdeadbeef;
#endif
            arena->partial_slab[bin].next = &arena->partial_slab[bin];
        }
        large_tree_size_addr_new(&arena->large_size_addr);
        extent_tree_ad_new(&arena->huge);

        chunk_recycler_init(&arena->chunks);
        if (reserved) {
            chunk_free(&arena->chunks, reserved, arena_initial_va);
            arena->chunks_start = reserved;
            reserved = arena->chunks_end = (char *)reserved + arena_initial_va;
        }
    }

    atomic_store_explicit(&initialized, true, memory_order_release);

    mutex_unlock(&init_mutex);
    thread_init(cache);
    return false;
}

malloc_init

static bool malloc_init(struct thread_cache *cache) {
    if (likely(cache->arena_index != -1)) {
        return false;
    }
    return malloc_init_slow(cache);
}

/* This section is in malloc_init_slow */
memory_init();
chunk_init();
huge_init();
purge_init();

透過這四個初始化函式來進行初始化

再來看到 allocate_small 這個函式，其中會用到 slab_first_alloc 與 slab_allocate 以及 struct slab

struct slot {
    struct slot *next;
    uint8_t data[];
};

struct slab {
    struct slab *next;
    struct slab *prev;

    size_t size;
    struct slot *next_slot;
    struct slot *end;

    uint16_t count;
    uint8_t data[];
};

首先先看到這兩個 struct

struct slot 是 memory pool 中最小單位的結構，每個 slot 能夠儲存一個固定大小的資料塊
struct slab 則是一個包含多個 slot 的大塊記憶體，用來儲存一定數量的相同大小的資料塊

struct slot 的 data 使用 uint8_t 的陣列型態 ([])，這是因為 uint8_t 是一個佔用一個 byte 的無號整數型態，所以使用 uint8_t data[] 的方式可以讓 data 陣列的大小動態指定為所需的大小，同時也讓資料塊的對齊方式更加靈活

struct slab 中的 data 也使用了類似的方式，用 uint8_t data[] 來表示一塊大小可變的記憶體。這樣的設計可以減少記憶體碎片，因為在記憶體池中，所有的資料塊大小都是固定的，所以如果每個 slab 中的 data 都使用固定大小的陣列，就可能會產生很多無法被利用的空間

更多關於 uint8_t *data 與 uint8_t data[] 的探討可以從課堂問答筆記 week 11 中找到

perf stat 效能

先做一點前置設定

$ sudo sh -c "echo -1 > /proc/sys/kernel/perf_event_paranoid"    # enable perf

另外這邊的 test_small 有下修 N 的數量為 30000。

test_small (O0)

$ perf stat --repeat 100 ./test_small

 Performance counter stats for './test_small' (100 runs):

              1.86 msec task-clock                #    0.852 CPUs utilized            ( +-  2.22% )
                 1      context-switches          #  503.220 /sec                     ( +-  4.19% )
                 0      cpu-migrations            #    0.000 /sec                   
               367      page-faults               #  184.682 K/sec                    ( +-  0.18% )
         6,230,105      cycles                    #    3.135 GHz                      ( +-  2.82% )
            19,569      stalled-cycles-frontend   #    0.37% frontend cycles idle     ( +-  2.55% )
            69,710      stalled-cycles-backend    #    1.32% backend cycles idle      ( +-  7.04% )
        15,503,852      instructions              #    2.93  insn per cycle         
                                                  #    0.00  stalled cycles per insn  ( +-  0.05% )
         1,994,684      branches                  #    1.004 G/sec                    ( +-  0.06% )
     <not counted>      branch-misses                                                 (0.00%)

         0.0021830 +- 0.0000441 seconds time elapsed  ( +-  2.02% )

test_large (O0)

$ perf stat --repeat 100 ./test_large

 Performance counter stats for './test_large' (100 runs):

              0.42 msec task-clock                #    0.971 CPUs utilized            ( +-  1.67% )
                 0      context-switches          #    0.000 /sec                   
                 0      cpu-migrations            #    0.000 /sec                   
                68      page-faults               #  276.417 K/sec                    ( +-  0.14% )
           928,501      cycles                    #    3.774 GHz                      ( +-  0.84% )
            15,764      stalled-cycles-frontend   #    2.04% frontend cycles idle     ( +-  1.23% )
            48,903      stalled-cycles-backend    #    6.34% backend cycles idle      ( +-  4.82% )
         1,144,867      instructions              #    1.48  insn per cycle         
                                                  #    0.02  stalled cycles per insn  ( +-  0.17% )
           214,619      branches                  #  872.416 M/sec                    ( +-  0.18% )
     <not counted>      branch-misses                                                 (0.00%)

         0.0004336 +- 0.0000125 seconds time elapsed  ( +-  2.88% )

test_huge (O0)

$ perf stat --repeat 100 ./test_huge

 Performance counter stats for './test_huge' (100 runs):

              0.18 msec task-clock                #    0.436 CPUs utilized            ( +-  3.65% )
                 0      context-switches          #    0.000 /sec                   
                 0      cpu-migrations            #    0.000 /sec                   
                62      page-faults               #  265.760 K/sec                    ( +-  0.15% )
           391,541      cycles                    #    1.678 GHz                      ( +-  2.80% )  (5.13%)
             6,009      stalled-cycles-frontend   #    0.84% frontend cycles idle     ( +-  3.14% )
                 0      stalled-cycles-backend    #    0.00% backend cycles idle    
         1,042,108      instructions              #    1.45  insn per cycle         
                                                  #    0.02  stalled cycles per insn  ( +-  0.13% )
           193,495      branches                  #  829.406 M/sec                    ( +-  0.15% )
             5,051      branch-misses             #    2.56% of all branches          ( +-  3.07% )  (94.87%)

         0.0004184 +- 0.0000128 seconds time elapsed  ( +-  3.05% )

test_small (O2)

$ perf stat --repeat 100 ./test_small

 Performance counter stats for './test_small' (100 runs):

              1.09 msec task-clock                #    0.936 CPUs utilized            ( +-  1.98% )
                 1      context-switches          #    1.035 K/sec                    ( +-  3.62% )
                 0      cpu-migrations            #    0.000 /sec                   
               368      page-faults               #  381.038 K/sec                    ( +-  0.17% )
         1,521,590      cycles                    #    1.575 GHz                      ( +-  4.21% )
            19,596      stalled-cycles-frontend   #    0.68% frontend cycles idle     ( +-  1.97% )
            61,946      stalled-cycles-backend    #    2.15% backend cycles idle      ( +-  9.62% )
         6,837,298      instructions              #    2.37  insn per cycle         
                                                  #    0.01  stalled cycles per insn  ( +-  0.10% )
         1,180,215      branches                  #    1.222 G/sec                    ( +-  0.09% )
             2,349      branch-misses             #    0.20% of all branches          ( +- 14.49% )  (48.52%)

         0.0011635 +- 0.0000281 seconds time elapsed  ( +-  2.41% )

test_large (O2)

$ perf stat --repeat 100 ./test_large

 Performance counter stats for './test_large' (100 runs):

              0.28 msec task-clock                #    0.608 CPUs utilized            ( +-  2.00% )
                 0      context-switches          #    0.000 /sec                   
                 0      cpu-migrations            #    0.000 /sec                   
                66      page-faults               #  256.536 K/sec                    ( +-  0.14% )
         1,262,378      cycles                    #    4.907 GHz                      ( +-  0.80% )
             8,261      stalled-cycles-frontend   #    1.10% frontend cycles idle     ( +-  1.94% )
           122,953      stalled-cycles-backend    #   16.38% backend cycles idle      ( +-  1.98% )
         1,117,157      instructions              #    1.49  insn per cycle         
                                                  #    0.02  stalled cycles per insn  ( +-  0.14% )
           210,696      branches                  #  818.957 M/sec                    ( +-  0.15% )
     <not counted>      branch-misses                                                 (0.00%)

         0.0004545 +- 0.0000105 seconds time elapsed  ( +-  2.31% )

test_huge (O2)

$ perf stat --repeat 100 ./test_huge

 Performance counter stats for './test_huge' (100 runs):

              0.30 msec task-clock                #    0.705 CPUs utilized            ( +-  1.97% )
                 0      context-switches          #    0.000 /sec                   
                 0      cpu-migrations            #    0.000 /sec                   
                63      page-faults               #  270.779 K/sec                    ( +-  0.15% )
           652,881      cycles                    #    2.806 GHz                      ( +-  0.83% )
             7,355      stalled-cycles-frontend   #    1.06% frontend cycles idle     ( +-  2.29% )
               595      stalled-cycles-backend    #    0.09% backend cycles idle      ( +-331.39% )
         1,015,332      instructions              #    1.46  insn per cycle         
                                                  #    0.02  stalled cycles per insn  ( +-  0.15% )
           190,556      branches                  #  819.026 M/sec                    ( +-  0.16% )
     <not counted>      branch-misses                                                 (0.00%)

         0.0004211 +- 0.0000109 seconds time elapsed  ( +-  2.60% )

可以看到有時候會偵測不到 branch-misses ，但是有時候又可以，不知為什麼會這樣，但是這並不是目前的重點，所以先忽略不看。先把重點放在 page-faults 與 context-switches 還有 instructions 的數量上面

struct/isoalloc 學習筆記

README.md

在 Design 這個篇章可以看到幾個重點

Default zones are created in the constructor for sizes: 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192 bytes.
The iso_alloc_root structure is thread safe and guarded by a mutex or spinlock when THREAD_SUPPORT is enabled.
All allocations larger than SMALL_SIZE_MAX live in big zones which have a size limitation of 4 GB. See PERFORMANCE.

在 Thread Safety 這個篇章有幾個重點

IsoAlloc 是 thread Safety 的，使用全域鎖保護最根本的結構 (root struct )，可以避免競爭問題。但是，因為每個 thread 都需要等待鎖才能分配或釋放記憶體，所以這樣的設計可能會影響多 thread 程式的性能。
IsoAlloc 可以在任何 thread 中分配或釋放記憶體，而不需要額外的複雜度。為了減少競爭，每個 thread 都有一個使用最近使用的區域的簡單快取，快取的大小默認為 8。此外，可以通過修改內部頭文件中的 ZONE_CACHE_SZ 定義來增加。
啟用 CPU_PIN 功能可以將一個區域的分配限制為創建該區域的 CPU 核心。這種模式適用於 Linux，可以在有或沒有 thread 支持的情況下使用。但這會對性能造成負面影響並可能增加記憶體使用量。優點是，它提供了一種基於 CPU 核心的隔離機制，而不需要額外的配置。

PERFORMANCE.md

Configuration and Optimizations

IsoAlloc 只支援 64 位元的架構，因此不必擔心移植到其他地方會降低效能。
IsoAlloc 使用簡單的 bitmap 來追蹤區塊狀態，以及由連續頁組成的區域，可以取得良好的效能，但會增加記憶體使用量。
當 PRE_POPULATE_PAGES 在 Makefile 全局 cache 中啟用時，將創建根本結構和區域 bitmap（但不包括保存用戶資料的頁面），指示 MAP_POPULATE kernel 預填充 page table ，從而減少頁面錯誤並提高性能
每個區塊的大小都是 2 的次方數，具有 SMALLEST_CHUNK_SZ(16 或是 64) 至 SMALL_SIZE_MAX (65535) 的最小值和最大值
啟用後將 USE_SPINLOCK 使用自旋鎖透過 ( atomic_flag ) 而不是 pthread 互斥鎖。IsoAlloc 的性能和負載測試表明自旋鎖比互斥鎖稍慢，因此它不是首選的默認選項。
IsoAlloc 預設會嘗試使用 Huge Pages 來進行 2 MB 的配置。
- 可以透過 $ cat /proc/meminfo | grep Hugepagesize 來取得 huge size 的大小

Caches and Memoization

IsoAlloc 設計了一些重要的快取技術，這些技術顯著提高了分配/釋放 hot path 的性能，並保持了設計的簡單性。

Zone Free List
- 每個區域都包含一個位槽數組，表示該區域中的空閒塊。分配熱路徑首先搜索此列表，尋找可以滿足分配請求的空閒塊。從此列表分配塊比遍歷區域位圖尋找空閒位槽要快得多。當列表低於某個閾值時，將重新填充此快取。釋放的塊在被隔離一段時間後，將被添加到此列表中。
MRU Zone Cache
- 此執行緒本地快取通過存儲TLS array 中最近使用的區域來進行優化。如果 block 到區域查找失敗，則會在 iso_find_zone_range 釋放路徑中檢查這些區域。
Zone Lookup Table
- 區域通過它們的 next_sz_index 成員鏈接在一起，該成員告訴分配器在 _root->zones 陣列中可以找到持有相同大小 chunks 的下一個區域。此查找表可幫助我們在 O(1) 時間內找到持有特定大小的第一個區域。這是通過將一個區域的索引值放置在該區域大小索引的位置上實現的，例如 zone_lookup_table[zone->size] = zone->index ，然後我們只需要使用下一個區域的索引成員，像單向 list 一樣走訪以找到該大小的其他區域

minalloc-bench 學習筆記

Mimalloc 目前僅支援類 Unix 的系統來作使用，像是 Ubuntu 就很適合。

其中支援了很多的記憶體配置器，像是

iso: The Isoalloc allocator, 基於隔離，旨在提供合理的安全級別而不犧牲太多性能
je: The jemalloc allocator，由 Jason Evans 開創，現在由 Meta 公司維護，廣泛應用於 FreeBSD, Android，及Firefox 等等場景。
rp: rpmalloc分配器使用 16 字節對齊分配，由 Epic Games 的Mattias Jansson開發，例如在Haiku中使用。
tc: 作為 Google 性能工具的一部分的tcmalloc分配器。
sys: 系統分配器。這裡我們通常使用glibc分配器（它最初是基於Ptmalloc2）

在 README.md 中還有更多的記憶體配置器介紹

目前的測試

可以分成兩種

真實有在使用的程式，或是一些模仿得很像的程式
壓力測試

其中壓力測試包括了

intensive allocation
passive-false sharing of cache lines
heap cache locality
large (several MiB) allocations
leak memory
allocating threads
等等的一系列測試

bench

rbtmalloc 開發紀錄

目前已完成

保留原本大尺寸的 linked-list 操作
用在處理小尺寸( < 512 bytes ) 的 memory pool 分配器
使用紅黑樹進行管理的大尺寸( >= 512 bytes )分配器
引入 list.h 與 rb.h 仿造 linux 風格

待完成

將小尺寸的 memory pool 新增擴充 tab 的功能
減少記憶體的浪費
統一結構體以保持整潔及維護性

目前遇到問題

思考在 free 的時候，如何僅憑引數的 ptr 來判斷要用那一種的 free

目前打算先移除掉 srbk / brk 這樣的系統呼叫，一律改用 mmap 系統呼叫。

小尺寸的記憶體部份使用 memory pool 來進行分配
大尺寸的記憶體則是用 mmap 系統呼叫搭配紅黑樹來進行分配
暫時不考慮 huge size

目前小尺寸的分配採用 linked-list 來進行
並且引入了 a1091150/2023q1_Homeworl6_quiz5 的 memory pool ，經過修改後進行使用

可以看到這個 commit 版本的程式碼在距離 allociator 還差得很遠

以下列出 test_small 與 test_large 的 perf performance

test_small

$ perf stat --repeat 10 ./test_small

 Performance counter stats for './test_small' (10 runs):

            524.09 msec task-clock                #    0.999 CPUs utilized            ( +-  0.26% )
                90      context-switches          #  171.994 /sec                     ( +-  7.11% )
                20      cpu-migrations            #   38.221 /sec                     ( +- 13.22% )
               473      page-faults               #  903.926 /sec                     ( +-  0.06% )
     2,375,562,203      cycles                    #    4.540 GHz                      ( +-  0.19% )  (83.24%)
         1,017,013      stalled-cycles-frontend   #    0.04% frontend cycles idle     ( +-137.18% )  (83.24%)
         1,041,311      stalled-cycles-backend    #    0.04% backend cycles idle      ( +-  9.08% )  (83.24%)
     2,720,616,149      instructions              #    1.14  insn per cycle         
                                                  #    0.00  stalled cycles per insn  ( +-  0.08% )  (83.24%)
       903,975,119      branches                  #    1.728 G/sec                    ( +-  0.11% )  (83.85%)
            50,316      branch-misses             #    0.01% of all branches          ( +-  5.49% )  (83.29%)

           0.52439 +- 0.00153 seconds time elapsed  ( +-  0.29% )

test_large

$ perf stat --repeat 100 ./test_large

 Performance counter stats for './test_large' (100 runs):

              0.30 msec task-clock                #    0.637 CPUs utilized            ( +-  1.30% )
                 0      context-switches          #    0.000 /sec                   
                 0      cpu-migrations            #    0.000 /sec                   
                82      page-faults               #  279.528 K/sec                    ( +-  0.11% )
           792,811      cycles                    #    2.703 GHz                      ( +-  0.47% )
             7,834      stalled-cycles-frontend   #    0.97% frontend cycles idle     ( +-  1.84% )
               522      stalled-cycles-backend    #    0.06% backend cycles idle      ( +-488.51% )
         1,248,432      instructions              #    1.55  insn per cycle         
                                                  #    0.03  stalled cycles per insn  ( +-  0.05% )
           229,582      branches                  #  782.617 M/sec                    ( +-  0.05% )
     <not counted>      branch-misses                                                 (0.00%)

        0.00047824 +- 0.00000661 seconds time elapsed  ( +-  1.38% )

Some events weren't counted. Try disabling the NMI watchdog:
	echo 0 > /proc/sys/kernel/nmi_watchdog
	perf stat ...
	echo 1 > /proc/sys/kernel/nmi_watchdog

可以看到目前的 test_large 的表現是還不錯的，但是還有一些需要改進的地方，像是記憶體的位置可能重新分配要盡量固定在原地等等的問題。

再來應該著手改善的是要進行小尺寸記憶體配置器的效能改善以及設計一個可以選擇要用小尺寸還是大尺寸的選擇器。

首先先用 perf graph 來看看究竟是哪個環節佔用了最多的時間

$ sudo perf record -g --call-graph dwarf ./test_small
$ sudo perf report --stdio -g graph,0.5,caller > temp.txt

可以得到以下結果

Perf Graph

# To display the perf.data header info, please use --header/--header-only options.
#
#
# Total Lost Samples: 0
#
# Samples: 2K of event 'cycles'
# Event count (approx.): 2384378402
#
# Children      Self  Command     Shared Object      Symbol                             
# ........  ........  ..........  .................  ...................................
#
    99.90%     0.00%  test_small  libc.so.6          [.] __clone3 (inlined)
            |
            ---__clone3 (inlined)
               start_thread
               do_work
               |          
                --99.74%--pool_free (inlined)
                          |          
                           --99.52%--get_loc_to_free

    99.90%     0.00%  test_small  libc.so.6          [.] start_thread
            |
            ---start_thread
               do_work
               |          
                --99.74%--pool_free (inlined)
                          |          
                           --99.52%--get_loc_to_free

    99.90%     0.00%  test_small  test_small         [.] do_work
            |
            ---do_work
               |          
                --99.74%--pool_free (inlined)
                          |          
                           --99.52%--get_loc_to_free

    99.74%     0.00%  test_small  test_small         [.] pool_free (inlined)
            |
            ---pool_free (inlined)
               |          
                --99.52%--get_loc_to_free

    99.52%    99.03%  test_small  test_small         [.] get_loc_to_free
            |          
             --99.03%--__clone3 (inlined)
                       start_thread
                       do_work
                       pool_free (inlined)
                       get_loc_to_free

可以看到大部份的時間都是在 pool_free 與 get_loc_to_free 這兩個函式之間，所以可能要再回去重新設計這兩個函式。

從 test_small.c 這個測試來看到它所測試的是 FIFO ，而我所進行的實作卻是 LIFO ，因此在面對到這樣的測試的時候，就會顯的特別的耗時

原本的實作

/* Search for a free space to place a new block */
comb_t *get_loc_to_place(struct list_head *head, int size)
{
    comb_t *node;
    list_for_each_entry (node, head, list) {
        if (node->size >= (size + header_size))
            return node;
    }
    return NULL;
}

test_small.c (片段)

void *do_work(void *ptr)
{
    void **p = malloc(N * sizeof(void *));

    for (size_t i = 0; i < N; i++) {
        p[i] = malloc(16);
        if (!p[i]) {
            exit(1);
        }
    }

    for (size_t i = 0; i < N; i++) {
        free(p[i]);
    }
    return ptr;
}

若是將 test_small.c 修改成從這個 array 的末端開始釋放的話，就可以看到他的性能明顯的提昇

$ perf stat --repeat 100 ./test_small

 Performance counter stats for './test_small' (100 runs):

              2.03 msec task-clock                #    0.917 CPUs utilized            ( +-  1.17% )
                 2      context-switches          #  992.712 /sec                     ( +-  2.20% )
                 0      cpu-migrations            #    0.000 /sec                   
               473      page-faults               #  234.776 K/sec                    ( +-  0.02% )
         5,641,299      cycles                    #    2.800 GHz                      ( +-  2.08% )
           103,834      stalled-cycles-frontend   #    2.13% frontend cycles idle     ( +-  0.29% )
               111      stalled-cycles-backend    #    0.00% backend cycles idle      ( +-12495.13% )
        14,020,883      instructions              #    2.88  insn per cycle         
                                                  #    0.01  stalled cycles per insn  ( +-  0.06% )
         3,212,126      branches                  #    1.594 G/sec                    ( +-  0.03% )
     <not counted>      branch-misses                                                 (0.00%)

         0.0022175 +- 0.0000259 seconds time elapsed  ( +-  1.17% )

但是這樣做並不是一個完美的解決方法，因此，可以將改為 tree 來進行，這樣就可以至少保證搜尋的時間會是

O (l o g N)

，詳見 Red–black tree 。

或是使用

bitmap
buddy system
hash table

這幾種方式來改善效能。

參考資料

注意用詞: "physical memory" 應翻譯為「實體記憶體」，以強調「虛擬記憶體」(virtual memory) 的相對。繁體中文措辭應當追求信達雅，避免受到躁進又在審查中閃躲的中國網路用語影響。

rbtmalloc 開發紀錄

問題紀錄

thestinger/allocator 編譯失敗

mmap 可以取用超過請求的空間

記憶體概念筆記

memory_commit

memory_decommit

虛擬記憶體大小

Transparent Hugepage

MADVISE 系統呼叫

mmap & populate

thestinger/allocator 學習筆記

rb.h

test_small.c

test_large.c

test_huge.c

alloc.c

perf stat 效能

test_small (O0)

test_large (O0)

test_huge (O0)

test_small (O2)

test_large (O2)

test_huge (O2)

struct/isoalloc 學習筆記

README.md

PERFORMANCE.md

Configuration and Optimizations

Caches and Memoization

minalloc-bench 學習筆記

目前的測試

bench

rbtmalloc 開發紀錄

參考資料

Read more

2023q1 Homework1 (lab0)

cm4hbm

2023q1 Homework3 (fibdrv)

2023q1 Homework6 (quiz5)

`rb.h`

`test_small.c`

`test_large.c`

`test_huge.c`

`alloc.c`