Linux 核心專題: 實作高效記憶體配置器

執行人: WangHanChi
專題解說簡報
 專題解說影片

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

提問清單

由簡報第 18 頁的 rp (rpmalloc) 的 malloc-large 測試項目來看，為何 rp 的執行時間比 sys (glibc) 來得長？

目前經過幾個測試，發現到 rpmalloc 的執行時間在分配 2MB ~ 35 MB 的時候，配置的時間會比 sys 還要長，我認為可能的原因有以下幾個

rpmalloc 在面對超大空間 (2097120 bytes) 時，是從作業系統分配，而不是從 freelist 中尋找。因為 rpmalloc 專注在小空間的分配，所以它將三種尺寸的 size 都訂的比較小 (the small blocks are [16, 1024] bytes, medium blocks (1024, 32256] bytes, and large blocks (32256, 2097120] bytes. )，因此這個可能導致在配置時，所花費的時間變長。此外如果將分配的空間設定在 1MB ~ 2MB 時， rpmalloc 的執行時間就會比 sys 所花的時間要短; 而超過 35 MB 後，兩者所配置的時間就會相當接近

任務簡述

第 5 週測驗題、第 6 週測驗題、第 11 週測驗題提及逐步建構記憶體配置器 (memory allocator)，本任務針對 Linux 核心的機制，設計現代的高效記憶體配置器。

TODO: 記憶體配置器的雛形及改進

第 5 週測驗題、第 6 週測驗題、第 11 週測驗題提及逐步建構記憶體配置器 (memory allocator)，搭配閱讀 CS:APP 第 9 章，解讀原本程式碼原理、指出其不足處，並著手改進。此部分還不考慮 lock-free 設計，但應量化和分析 lock contention 的影響。

整理 rbtmalloc 開發紀錄

rbtmalloc 開發紀錄

目前已完成

用在處理小尺寸( < 512 bytes ) 的 memory pool 配置器
使用紅黑樹進行管理的大尺寸( >= 512 bytes )配置器
引入 list.h 仿造 linux 風格

待完成

將小尺寸的 memory pool 新增擴充 tab 的功能
減少記憶體的浪費
改用 lock-free (例如 atomic 操作)
量化目前的 lock contention 並分析

目前遇到問題

小尺寸的 memory pool 之 worst case 時間複雜度為
$O (n)$

開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.

$ lscpu | less
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Address sizes:                   48 bits physical, 48 bits virtual
Byte Order:                      Little Endian
CPU(s):                          12
On-line CPU(s) list:             0-11
Vendor ID:                       AuthenticAMD
Model name:                      AMD Ryzen 5 5600X 6-Core Processor
CPU family:                      25
Model:                           33
Thread(s) per core:              2
Core(s) per socket:              6
Socket(s):                       1
Stepping:                        0
Frequency boost:                 enabled
CPU max MHz:                     4650.2920
CPU min MHz:                     2200.0000
BogoMIPS:                        7385.75

目前打算先消除對 srbk / brk 系統呼叫的依賴，改用 mmap 系統呼叫。

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

目前小尺寸的配置採用鏈結串列，並引入 a1091150/2023q1_Homeworl6_quiz5 的 memory pool ，經過修改後進行使用

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

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 →

TODO: 解釋 perf 結果

以下列出 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

與 thestinger/allocator 的 perf 結果

allocator / 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% )

allocator / 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% )

經過上面的測試結果發現，我的 page fault 大約都是比 allocator 的多了 20% 左右，並且在 test_small 的 instructions 數量比起 allocator 多了非常多，也因為這樣，導致出現了 context-switches 的數量非常高。我的推測是我在小尺寸的配置器實作上，因為使用
linked-list 導致在搜尋的時候會因為 FIFO 或是 LIFO 的堆疊機制導致出現 worst case ，進而導致 instructions 的數量大增。

可以看到目前的 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

這幾種方式來改善效能。

TODO: 研究既有的記憶體配置器實作

至少涵蓋以下:

著重於以下考量因素:

如何解決並行環境的 lock contention 議題？是否因此提出 lock-free 的設計？
如何管理 free list？用哪些資料結構和手段？
運用到哪些系統呼叫和 Linux 核心機制？例如 madvise 及 Transparent Hugepage
如何測試及驗證？例如 mimalloc-bench 及 security benchmark

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 中找到

`memory.c` 與 `memory.h`

跟記憶體有關操作都會定義在這邊
首先先看到

`memory_init`

COLD void memory_init(void) {
    int overcommit = open("/proc/sys/vm/overcommit_memory", O_RDONLY|O_CLOEXEC);
    if (overcommit != -1) {
        char digit;
        int rc = TEMP_FAILURE_RETRY(read(overcommit, &digit, 1));
        if (rc == 1 && digit != '2') {
            reduce_commit_charge = false;
        }
        close(overcommit);
    }
}

這個函式主要是用來確認系統有沒有開啟 overcommit ，如果有開啟的話( digit == 2 )，就要將 reduce_commit_charge 這個旗標保持設定為 true。

這將影響到後面在配置記憶體的行為。

`memory_decommit`

void memory_decommit(void *addr, size_t size) {
    if (reduce_commit_charge) {
        mmap(addr, size, PROT_NONE, map_flags|MAP_FIXED, -1, 0);
    } else {
        madvise(addr, size, MADV_DONTNEED);
    }
}

可以看到根據 reduce_commit_charge 會有兩種不同的行為

reduce_commit_charge 為 true
- 使用 mmap 來標記這塊記憶體為 prot_none 代表著該區域既不可讀取、寫入，也不可執行，沒有任何操作權限，該記憶體區域的內容將無法被存取，同時也不佔用實際的實體記憶體。這種方式適用於需要完全釋放記憶體並不再使用的情況，例如釋放一個大型結構的記憶體。
- 而這塊的 prot 屬性也可以之後透過 mprotect 進行動態修改
reduce_commit_charge 為 false
- 這種策略使用 madvise 函式對指定的記憶體區域進行建議，告訴系統該區域的內容在未來可能不會被使用。使用 MADV_DONTNEED 參數，表示該區域的內容在未來可能不再需要，系統可以釋放或清除該內容。這種方式並不直接將記憶體設為無法存取，而是提供一個建議給系統，系統可以根據這個建議自行處理記憶體的釋放。這種方式適用於有可能再次使用該記憶體區域，但在目前情況下可以釋放其內容的情況，例如快取資料或臨時使用的記憶體。

`memory_commit`

bool memory_commit(void *addr, size_t size) {
    if (reduce_commit_charge) {
        return mprotect(addr, size, PROT_READ|PROT_WRITE);
    }
    return false;
}

可以看到這個函式跟上面的 memory_decommit 可以互相搭配，如果 reduce_commit_charge 為 true 的話，就會在需要 commit 的時候，使用 mprotect
命令將其的權限修改為 PROT_READ|PROT_WRITE ，即為可以進行操作。

`memory_map`

void *memory_map(void *hint, size_t size, bool commit) {
    int prot = !commit && reduce_commit_charge ? PROT_NONE : PROT_READ|PROT_WRITE;
    void *addr = mmap(hint, size, prot, map_flags, -1, 0);
    if (unlikely(addr == MAP_FAILED)) {
        return NULL;
    }
    return addr;
}

這邊是要用 mmap 來向作業系統取得配置的空間

`memory_remap_fixed`

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;
}

這邊使用 mremap 系統呼叫來重新映射記憶體區域的位置以及可以改變他的大小。
可以注意到它添加了 MREMAP_MAYMOVE 和 MREMAP_FIXED 這兩個參數

MREMAP_MAYMOVE 表示如果需要，系統可以將原始記憶體區域移動到新的位址。
MREMAP_FIXED 則表示新的位址是固定的，即必須使用提供的 new_addr 參數作為新的位址。

要特別注意的是如果重新映射成功，則返回 false，否則返回 true，表示重新映射失敗。

Lock 操作

在 allocator 中有 mutex.h 與 mutex.c ，看似是使用 mutex ，但是如果系統有支援 atomic 操作的話，就會切換成使用 atomic ，非常有意思！

先看到 mutex.h

#ifdef __linux__

#include <stdatomic.h>

#define MUTEX_INITIALIZER 0
typedef atomic_int mutex;

#else

#include <pthread.h>

#define MUTEX_INITIALIZER PTHREAD_MUTEX_INITIALIZER;
typedef pthread_mutex_t mutex;

#endif

假如偵測到了 linux 的環境的話，就會使用 C11 標準的 stdatomic 來進行資料的保護。
可以看到它將 atomic_int 重新 typedef 成 mutex 。

接下來看到 mutex.c ，也是透過一樣的手段來實作 lock 的，由於學生本身使用的是基於 linux 的 ubuntu 22.04 環境，所以主要以 atomic 進行筆記。

sys_futex

static int sys_futex(void *uaddr, int op, int val1, struct timespec *timeout, void *uaddr2,
                     int val3) {
    return syscall(SYS_futex, uaddr, op, val1, timeout, uaddr2, val3);
}

首先 Futex 是 Fast userspace muTexes 的縮寫

uaddr : 一個指向記憶體地址的指標，用來標示要進行操作的 futex 第一個變數
op : 用來傳遞操作選項的第一個值
timeout : 用來設定超時時間，如果是 NULL, 就代表不限時間
uaddr2 : 一個指向記憶體地址的指標，用來標示要進行操作的 futex 第二個變數
val13 : 用來傳遞操作的第三個變數

所以這個函數主要就是要去呼叫 futex 這個 system call 的。

mutex_init

bool mutex_init(mutex *m) {
    *m = 0;
    return false;
}

先將 lock 初始化為 0 ，並且回傳 false 。

mutex_try_lock

bool mutex_trylock(mutex *m) {
    int expected = 0;
    return !atomic_compare_exchange_strong_explicit(m, &expected, 1, memory_order_acquire,
                                                    memory_order_relaxed);
}

mutex_trylock 函式嘗試以非阻塞的方式執行 atomic_compare_exchange_strong_explicit 操作，將 mutex 的值從 0 更改為 1。

根據 atomic_compare_exchange_strong_explicit 的行為，如果期望值與 mutex 目前的值相同，則該操作會成功並回傳 true；反之，操作會失敗並回傳 false。

當 atomic_compare_exchange_strong_explicit 操作成功時，mutex 的值從預期的 0 被替換為 1，並回傳 false。然而，在 mutex_trylock 函式中，我們希望回傳 true 表示嘗試取得鎖失敗。

相反地，當 atomic_compare_exchange_strong_explicit 操作失敗時，表示 mutex 的值不是預期的 0，該操作會回傳 true。然而，我們希望回傳 false 表示嘗試取得鎖成功。

為此，在 return 後面加上 ! 操作的目的是將回傳值進行反轉。當 atomic_compare_exchange_strong_explicit 回傳 true 時，我們進行取反後得到 false，表示嘗試取得鎖成功；而當 atomic_compare_exchange_strong_explicit 回傳 false 時，我們進行取反後得到 true，表示嘗試取得鎖失敗。

因此，在 mutex_trylock 函式中，回傳值為 true 表示嘗試取得鎖失敗，回傳值為 false 表示嘗試取得鎖成功。透過使用 ! ，使得函式的回傳值與常用的習慣一致。

mutex_lock

void mutex_lock(mutex *m) {
    int expected = 0;
    if (unlikely(!atomic_compare_exchange_strong_explicit(m, &expected, 1, memory_order_acquire,
                                                          memory_order_relaxed))) {
        if (expected != 2) {
            expected = atomic_exchange_explicit(m, 2, memory_order_acquire);
        }
        while (expected) {
            sys_futex(m, FUTEX_WAIT_PRIVATE, 2, NULL, NULL, 0);
            expected = atomic_exchange_explicit(m, 2, memory_order_acquire);
        }
    }
}

這個函式一樣用到上面的概念，先設定預期的值為 0 ，接下來執行 atomic_compare_exchange_strong_explicit ，如果回傳的是 ture 的話，就代表有成功進行交換，並且回傳 true ，再經過 ! 的操作之後，就會變成 false 從而避免進入 if 判斷句; 如果回傳的是 false ，表沒有進行交換，也就是說它目前是被鎖定的，因此就會進入到 if 判斷句進行等待。

再來進到 if 敘述句中，會先檢查 exceoted 的值是否等於 2 ，如果不是 2 的話，就會用 atomic_exchange_explicit 來將 mutex 的值會變成 2 ，再將函式回傳值配置給 excepted 。

接下來檢查 excepted 的值是不是非零，如果的話，就會進到 while-loop 中，然後使用 sys_futex 來將 mutex 的值變成 2 ，然後在將函式回傳值配置給 excepted 。重複這個行為直到， excepted 變成 0 。

mutex_unlock

void mutex_unlock(mutex *m) {
    if (unlikely(atomic_fetch_sub_explicit(m, 1, memory_order_release) != 1)) {
        atomic_store_explicit(m, 0, memory_order_release);
        sys_futex(m, FUTEX_WAKE_PRIVATE, 1, NULL, NULL, 0);
    }
}

首先使用 atomic_fetch_sub_explicit 來對 mutex 進行減 1 的操作，接著檢查函是的回傳值是否為 1 ，若是相等於 1 的話，就是代表 mutex 本來就是鎖定的狀態，所以就可以不用進到 if 敘述句中; 若是原本不是鎖定的狀態，也就是回傳值不為 1 的時候，就會通過 atomic_store_explicit 來將 mutex 設定為 0 ，表示 mutex 目前為空閒的狀態。
接下來使用系統呼叫 sys_futex(m, FUTEX_WAKE_PRIVATE, 1, NULL, NULL, 0); 來將一個在等待 mutex 的執行緒喚醒，其中的參數 1 代表喚醒一個執行緒。
通過喚醒正在等待的執行緒，其他的執行緒就有機會獲取到 mutex 並進行操作。

這些雖用到 atomic 操作，但為 blocking 的同步機制 (mutex)，若要降低 lock contention，需要導入 lock-free 演算法

free list 設計

首先可以看到 free 的定義

EXPORT void free(void *ptr) {
    deallocate(&tcache, ptr);
}

便可以知道 free 的所有行為都在 deallocate 中完成，因此再去看到該函式

可以知道在釋放記憶體的時候分成了三種

huge_free
deallocate_small
large_free

可以看到只有在面對小尺寸的時候，是命名為 deallocate_small ，其他的卻都有 free ，是因為在設計的時候，將小尺寸的記憶體配置器設定為 memory pool 了，所以不會進行 munmap 的動作，只會去標記為已釋放。

首先先看到 huge_free

由於 huge size 的記憶體也是用紅黑樹進行管理的，所以移除的操作就會是以下

先透過傳入的指標 ptr 找到 node
再透過 ptr 找到對應的 arena
再來由於有可能找不到 arena 所以採用 maybe_lock_arena
接著在用該 arena 去找到 extent_tree
將 node 指定為搜索到的節點
再將 node 指定為要移除的節點
再把 node 加進要 free 的 list 中
再去釋放 arnea 的 lock
最後檢查是否要合併 chunk

再來看到 large_free
可以看到 large 與 huge 的管理策略就不太一樣了

先透過 size 的加減來獲得下一個 node 的地址
嘗試與下( next )一個 node 進行合併
嘗試與上( prev )一個 node 進行合併
檢查合併後的 self 的大小是否等於 CHUNK_SIZE - LARGE_CHUNK_HEADER，若是的話表示整個區域都是屬於它一整塊的，就進行釋放。
若是大小不等於的話，就把這個 node 插回到 large tree裡

再來看到最為複雜的 small_size

首先先透過 ptr 來取得 slot, slab, size, 與 bin
再來檢查 cache 是否為 dead 的狀態，若是的話
- 檢查是否為初始化
- 再次檢查是否為 dead ，若是的話，就找到該 chuck 並且釋放它
在對應的 cache->bin 中找到要釋放的 bin
檢查該塊 bin 所累積的大小是否已經超過的 CACHE_SIZE，若是
- 先把該塊 bin 的大小設置成 slab->size 的大小
- 再來進入迴圈直到 bin 的大小 > CACHE_SIZE/2 後為止
設定一個新的 slot 指標為 flush ，並且將其設置為 NULL
取得該塊 bin 所屬的 arena ，並且 lock 住
透過 slot 來去得到它所屬的 chunk
檢查 chunk 所屬的 arena 是否與當前處理的 arena 相同
- 若是:使用 slab_deallocate 釋放 slot 所在的空間
- 若不是:將 slot 的 next 設為 flush
unlock ，並且重複步驟 5 ~ 9 ，直到 flush 為 NULL 之後才結束

mimalloc-bench 學習筆記

建置環境

$ git clone https://github.com/daanx/mimalloc-bench.git
$ cd mimalloc-bench
$ ./build-bench-env.sh all no-lean no-gd no-ff no-fg no-lt no-lf no-hd no-tcg no-pa

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 →

在建置的過程中會要求我們輸入密碼

完成建置之後，就可以使用以下指令進行所有的配置器跑所有的測試

$ cd mimalloc-bench/out/bench
$ ../../bench.sh alla allt

或是也可以指定的配置器跑指定的測試，並且選定要使用的執行緒

$ ../../bench.sh --procs=6 mi rp cfrac larson lua

會得到以下這樣的結果輸出

...

results written to: /home/hanchi/linux2023/mimalloc-bench/out/bench/benchres.csv

#------------------------------------------------------------------
# test    alloc   time  rss    user  sys  page-faults page-reclaims
cfrac       mi    02.90 3300 2.89 0.00 0 376
cfrac       rp    02.93 4028 2.93 0.00 0 744
larsonN     mi    4.390 76352 29.87 0.16 0 18384
larsonN     rp    4.162 69284 29.94 0.08 0 16806
lua         mi    03.39 72596 3.22 0.16 0 147539
lua         rp    03.44 77124 3.17 0.26 0 202448

再來也可以用以下命令來將結果繪製成圖表

$ python3 graphs.py out/bench/benchres.csv

會得到像這樣的圖表(要注意的是原本是 svg 檔，需要轉成 png 才能上傳上來)

為了讓解讀便利，只要列出 sys, rpmalloc, mimalloc, tcmalloc (依據執行時間排序，由大到小) 以及自行增添的實作。

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 →

jserv

支援的記憶體配置器與測試

mimalloc-bench 目前僅支援類 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
等等的一系列測試

rpmalloc 學習筆記

這邊主要學習他的 atomic 操作

可以看到他的 atomic 參數如下

typedef volatile _Atomic(int32_t) atomic32_t;
typedef volatile _Atomic(int64_t) atomic64_t;
typedef volatile _Atomic(void*) atomicptr_t;

接著是把以上的變數不論是 32-bit 或是 64-bit 或是指標的型態帶入進函式中。

load

static FORCEINLINE int32_t atomic_load32(atomic32_t* src) { return atomic_load_explicit(src, memory_order_relaxed); }
static FORCEINLINE int64_t atomic_load64(atomic64_t* val) { return atomic_load_explicit(val, memory_order_relaxed); }
static FORCEINLINE void*   atomic_load_ptr(atomicptr_t* src) { return atomic_load_explicit(src, memory_order_relaxed); }

以上這三個函式都是透過指定的 32-bit, 64-bit 或是指標變數來進行 atomic_load_explicit 這個函式的。
並且使用了 memory_order_relaxed 這個來標記 memory_order 的 flag，使用這個 flag 可以保證最佳的性能與當前操作的不可分割性，但是不考慮執行緒之間的同步，其他執行緒可能讀到新值也有可能讀到舊值。

store

static FORCEINLINE void    atomic_store32(atomic32_t* dst, int32_t val) { atomic_store_explicit(dst, val, memory_order_relaxed); }
static FORCEINLINE void    atomic_store32_release(atomic32_t* dst, int32_t val) { atomic_store_explicit(dst, val, memory_order_release); }
static FORCEINLINE void    atomic_store_ptr(atomicptr_t* dst, void* val) { atomic_store_explicit(dst, val, memory_order_relaxed); }
static FORCEINLINE void    atomic_store_ptr_release(atomicptr_t* dst, void* val) { atomic_store_explicit(dst, val, memory_order_release); }

以上這三個函式都是透過指定的 32-bit, 64-bit 或是指標變數來進行 atomic_load_explicit 這個函式的。
但是不同的是有使用 memory_order_relaxed 也有 memory_order_release 這幾種不同的 flag 的。

memory_order_relaxed
- 保證最佳的性能與當前操作的不可分割性，但是不考慮執行緒之間的同步，其他執行緒可能讀到新值也有可能讀到舊值。
memory_order_release
- 可以理解為 mutex 的 unlock 操作
- 在使用了這個 release 旗標後，在這個程式碼前面的所有讀寫操作都不會因為 memory order 重排到這個操作之後。例如 : store-store 不能被重新排序成 load-store, store-load 及 load-load。
- 這個執行緒內的所有寫入操作，對於其他有對這個 atomic 變數進行 acquire 的執行緒是可見的
加減

static FORCEINLINE int32_t atomic_incr32(atomic32_t* val) { return atomic_fetch_add_explicit(val, 1, memory_order_relaxed) + 1; }
static FORCEINLINE int32_t atomic_decr32(atomic32_t* val) { return atomic_fetch_add_explicit(val, -1, memory_order_relaxed) - 1; }
static FORCEINLINE int32_t atomic_add32(atomic32_t* val, int32_t add) { return atomic_fetch_add_explicit(val, add, memory_order_relaxed) + add; }
static FORCEINLINE int64_t atomic_add64(atomic64_t* val, int64_t add) { return atomic_fetch_add_explicit(val, add, memory_order_relaxed) + add; }

以上四個函式都是通過了 atomic_fetch_add_explicit 這個 atomic 函式所進行的
可以看到它也是使用了 memory_order_relaxed 的這個 flag ，並且也在回傳值得時候，加上/減掉 add 的值。

交換

static FORCEINLINE int     atomic_cas32_acquire(atomic32_t* dst, int32_t val, int32_t ref) { return atomic_compare_exchange_weak_explicit(dst, &ref, val, memory_order_acquire, memory_order_relaxed); }
static FORCEINLINE void*   atomic_exchange_ptr_acquire(atomicptr_t* dst, void* val) { return atomic_exchange_explicit(dst, val, memory_order_acquire); }
static FORCEINLINE int     atomic_cas_ptr(atomicptr_t* dst, void* val, void* ref) { return atomic_compare_exchange_weak_explicit(dst, &ref, val, memory_order_relaxed, memory_order_relaxed); }

這邊用到的 atomic 操作共有兩種

atomic_compare_exchange_weak_explicit
- 將 dst 與 ref 的值進行相比，如果發現 dst 與 ref 相等的話，就把 val 的值指派到 dst ，並且回傳 true; 如果不相等的話，就把 dst 的值指派到 ref ，並且回傳 false。
- 可以看成以下的操作 (一氣呵成的執行，要不成功，要不失敗，沒有中間狀態)
```
if (memcmp(dst, ref, sizeof( *dst ) == 0)
    memcpy(dst, &val, sizeof( *dst));
else
    memcpy(ref, dst, sizeof( *dst));    
```
atomic_exchange_explicit
- 將 dst 的值用 val 來替換，並且回傳 dst 先前的值。

接著定義都是 atomic 變數的結構

#if ENABLE_ADAPTIVE_THREAD_CACHE || ENABLE_STATISTICS
struct span_use_t {
	//! Current number of spans used (actually used, not in cache)
	atomic32_t current;
	//! High water mark of spans used
	atomic32_t high;

    ...
};
typedef struct span_use_t span_use_t;
#endif

在 struct span_t 這個結構中也有定義了一個 atomic 指標，用來指向 free_list_deferred

struct span_t {
    ...
    //! Deferred free list
    atomicptr_t free_list_deferred;
    ...
};

在 struct heap_t 這個結構中也有定義了一個 atomic 指標，用來管理共享的變數

struct heap_t {
    ...
    //! List of deferred free spans (single linked list)
    atomicptr_t  span_free_deferred;
    ...
    //! Child count
    atomic32_t   child_count;
    ...
};

在 struct global_cache_t 也有定義 atomic 變數，並且把它命名為 lock

struct global_cache_t {
    ...
    //! Cache lock
    atomic32_t lock;
    ...
};

也有兩個全域變數使用了 atomic 定義

//! Heap ID counter
static atomic32_t _memory_heap_id;
//! Used to restrict access to mapping memory for huge pages
static atomic32_t _memory_global_lock;

閱讀程式碼筆記

首先先從配置記憶體的開始看

從 rpmalloc 開始看起

extern inline RPMALLOC_ALLOCATOR void*
rpmalloc(size_t size) {
#if ENABLE_VALIDATE_ARGS
	if (size >= MAX_ALLOC_SIZE) {
		errno = EINVAL;
		return 0;
	}
#endif
	heap_t* heap = get_thread_heap();
	return _rpmalloc_allocate(heap, size);
}

可以看到它會先檢查配置的 size ，再來透過 get_thread_heap() 來獲得目前的 thread heap。

接著可以看到在 rpmalloc 這個函式中的 get_thread_heap 這個函式的深層有用到一個比較特別的定義

//! Current thread heap
#if ((defined(__APPLE__) || defined(__HAIKU__)) && ENABLE_PRELOAD) || defined(__TINYC__)
static pthread_key_t _memory_thread_heap;
#else
#  ifdef _MSC_VER
#    define _Thread_local __declspec(thread)
#    define TLS_MODEL
#  else
#    ifndef __HAIKU__
#      define TLS_MODEL __attribute__((tls_model("initial-exec")))
#    else
#      define TLS_MODEL
#    endif
#    if !defined(__clang__) && defined(__GNUC__)
#      define _Thread_local __thread
#    endif
#  endif
static _Thread_local heap_t* _memory_thread_heap TLS_MODEL;
#endif

這邊可以看到使用了一個名為 TLS 的 model，__attribute__((tls_model("initial-exec"))) 代表者 _memory_thread_heap 這個變數會允許每個執行緒擁有自己的變數，而這些變數在不同執行緒之間是互不干擾的，因此，這種作法通常應用再多執行緒的環境中。

再看到 rpmalloc/CACHE.md 的這個說明

使用了 thread cache 的機制，是一種在多執行緒環境下用於記憶體配置的概念。當多個執行緒同時進記憶體配置的時候，他們可能會競爭存取共享的記憶體資源，從而導致性能下降。

因此為了避免這個問題， rpmalloc 為每個 thread 創造一個讀去的執行緒快取，可以用於儲存該執行緒所配置的記憶體 block 。這樣一來，就可以讓每個執行緒都可以在自己的執行緒快取中進行快速的配置以及釋放的操作，並且不會跟它執行緒競爭共享的資源，從而導致性能降低。

回到 rpmalloc/CACHE.md 可以看到性能的圖表顯示在不設置快取的情況， rpmalloc-nocache 使用了極低的記憶體開銷，甚至低於了 C Run time 的標準庫。
並且也可以從圖上得知，若是使用一般的 rpmalloc 或是 rpmalloc-unlimit 會可以讓 CPU 在一秒之內做出最多的操作。

再來看到 _rpmalloc_allocate

static void*
_rpmalloc_allocate(heap_t* heap, size_t size) {
	_rpmalloc_stat_add64(&_allocation_counter, 1);
    if (EXPECTED(size <= SMALL_SIZE_LIMIT))
        return _rpmalloc_allocate_small(heap, size);
    else if (size <= _memory_medium_size_limit)
        return _rpmalloc_allocate_medium(heap, size);
    else if (size <= LARGE_SIZE_LIMIT)
        return _rpmalloc_allocate_large(heap, size);
    return _rpmalloc_allocate_huge(heap, size);
}

可以發現他也是將要配置的空間分成了三個尺寸
從定義可以發現

small
medium
large

並且只要超過了 large 的上限的話，就會直接計算需要幾個 pages ，之後呼叫 mmap 系統呼叫直接配置。

然後設計預設了最常用到的會是 small size 的部份，所以將 small size 的 if 敘述句前面加上了 EXCEPTED ，來告訴編譯器這個是最常發生的，可以透過 Built-in Functions 來減少 branch 所帶來的 branch penalty。

_rpmalloc_allocate_small

可以看到設計者用了以下 bitwise 來確保配置的空間是 align 16 bit

const uint32_t class_idx = (uint32_t)((size + (SMALL_GRANULARITY - 1)) >> SMALL_GRANULARITY_SHIFT);

接著使用了 atomic 操作來對更新統計資料，包括了目前配置的數量與總共配置的數量
再來若 heap_size_class->free_list 不為 0 的話，就從 free_list 中 pop 第一個 block 出來並且回傳給使用者用。

若是 free_list 是空的話，就會去 heap 來配置空間。

_rpmalloc_allocate_medium

可以發現處理 medium 的方法與處理 small 的方法是大同小異的，不同的是處理 index 的方法

const uint32_t base_idx = (uint32_t)(SMALL_CLASS_COUNT + ((size - (SMALL_SIZE_LIMIT + 1)) >> MEDIUM_GRANULARITY_SHIFT));
const uint32_t class_idx = _memory_size_class[base_idx].class_idx;

而 base_idx 轉換公式為

(65 + (s i z e - 1025)) >> 9

_rpmalloc_allocate_large

可以看到它一樣是先計算所需要的大小

size += SPAN_HEADER_SIZE;
size_t span_count = size >> _memory_span_size_shift;
if (size & (_memory_span_size - 1))
    ++span_count;

接下來去取得空間的地址之後

span_t* span = _rpmalloc_heap_extract_new_span(heap, 0, span_count, SIZE_CLASS_LARGE);
if (!span)
    return span;

//Mark span as owned by this heap and set base data
rpmalloc_assert(span->span_count >= span_count, "Internal failure");
span->size_class = SIZE_CLASS_LARGE;
span->heap = heap;

確認是否有打開 FIRST_CLASS_HEAPS ，如果有的話，就會把它加入到 span 的 double linked list 裡面。

#if RPMALLOC_FIRST_CLASS_HEAPS
	_rpmalloc_span_double_link_list_add(&heap->large_huge_span, span);
#endif

最後回傳這個地址，特別注意要回傳的地址會是要從 span 偏移 header_size 的位址。

_rpmalloc_allocate_huge

這個函式也是先求出要用的 page size 之後，就用 mmap 來配置 huge 尺寸的空間

size += SPAN_HEADER_SIZE;
size_t num_pages = size >> _memory_page_size_shift;
if (size & (_memory_page_size - 1))
    ++num_pages;
size_t align_offset = 0;
span_t* span = (span_t*)_rpmalloc_mmap(num_pages * _memory_page_size, &align_offset);
if (!span)
    return span;

再來更新 span 的資訊，使用 atomic 操作 _rpmalloc_stat_add_peak 來確保資訊同步。

然後再把它加進管理 heap->large_huge_span 的 double linked list 中。

再來看到 rpfree ，就只有簡單的一行

extern inline void
rpfree(void* ptr) {
	_rpmalloc_deallocate(ptr);
}

接著在看到 _rpmalloc_deallocate ，
首先先用了一個 atomic 操作將 atomic 全域變數 _deallocation_counter 加 1 。

接著根據傳入的 p ，來尋找他是超大, 大, 中, 小其中的那一個。

再來因為 span 的預設大小是 64*1024 ，所以利用了 align span 的技巧搭配 _memory_span_mask 來找到這個指標是屬於哪個 span 的

//Grab the span (always at start of span, using span alignment)
	span_t* span = (span_t*)((uintptr_t)p & _memory_span_mask);

接著就可以依據 span 的資訊來找到他是哪個尺寸的

if (UNEXPECTED(!span))
    return;
if (EXPECTED(span->size_class < SIZE_CLASS_COUNT))
    _rpmalloc_deallocate_small_or_medium(span, p);
else if (span->size_class == SIZE_CLASS_LARGE)
    _rpmalloc_deallocate_large(span);
else
    _rpmalloc_deallocate_huge(span);

_rpmalloc_deallocate_small_or_medium

_rpmalloc_stat_inc_free(span->heap, span->size_class);

首先先用一個 atomic 操作，將 span->heap 中 alloc_current 減 1 ，再把 free_total 加 1 ，主要就是更新統計的資料。

if (span->flags & SPAN_FLAG_ALIGNED_BLOCKS) {
    //Realign pointer to block start
    void* blocks_start = pointer_offset(span, SPAN_HEADER_SIZE);
    uint32_t block_offset = (uint32_t)pointer_diff(p, blocks_start);
    p = pointer_offset(p, -(int32_t)(block_offset % span->block_size));
}

如果有 align 的話，就會先將指標的地址還原到 block start 的地方。

int defer = (span->heap->owner_thread && (span->heap->owner_thread != get_thread_id()) && !span->heap->finalize);

接著如果滿足以上三個條件的話，就要用 _rpmalloc_deallocate_defer_small_or_medium 來去釋放空間，不然就是用 _rpmalloc_deallocate_direct_small_or_medium

_rpmalloc_deallocate_direct_small_or_medium

首先檢查 span 內的記憶體空間是否是完全被用盡的，如果是的話，就會從 heap->full_span 中把該 span 移出，接著把它插入到 heap->size_class[span->size_class].partial_span 中，然後更新統計資料 --heap->full_span_count; 。

*((void**)block) = span->free_list;
--span->used_count;
span->free_list = block;

將 block 的指標轉換為 void** 型別，並將 span 的 free_list 賦值給該指標。這將把 block 加入到 span 的 free list 中。
再來減少 span->used_count 的值。
最後將 block 設置為 span 的新 free list 的開頭

在函式的最後檢查了是否有未使用的區塊，並且因為如果有未使用的區塊的話，就代表沒有其他的外部執行緒進行存取這個 span 。將 span 的 free_list_deferred 設定為 INVALID_POINTER ，且把它從 span 的雙向 linked list 中移除，並且加進 cache 中。

_rpmalloc_deallocate_defer_small_or_medium

// The memory ordering here is a bit tricky, to avoid having to ABA protect
// the deferred free list to avoid desynchronization of list and list size
// we need to have acquire semantics on successful CAS of the pointer to
// guarantee the list_size variable validity + release semantics on pointer store

在註解中有提到，這裡的 memory order 有點棘手，為了避免出現 ABA 問題，於是需要確保 deferred free list 不會出現 list 與 list size 不同步的問題，因此需要使用到 CAS 的 atomic 操作來完成。

ABA 問題是在多執行緒計算中，ABA 問題發生在同步過程中，當一個位置被讀取兩次，兩次讀取的值相同，兩次讀取的值相同被用來斷定中間沒有發生任何事情；然而，另一個執行緒可以在兩次讀取之間執行並更改值，做其他工作，然後將值改回原樣，從而使第一個執行緒認為沒有任何變化，即使第二個執行緒確實違反了該假設。

Wikipedia : ABA problem

void* free_list;
do {
    free_list = atomic_exchange_ptr_acquire(&span->free_list_deferred, INVALID_POINTER);
} while (free_list == INVALID_POINTER);

在這段程式碼中使用了 spinlock 的概念的完成這個部份，等待 free_list 變成一個有效的指標值，而不是 INVALID_POINTER ，在等待的期間會一直在自旋。

這邊感覺是一個可以進行改進的空間，例如使用 RCU 等等的

接下來看到 rpcalloc

可以看到先做了乘法是否溢位的檢查

#if PLATFORM_WINDOWS
int err = SizeTMult(num, size, &total);
if ((err != S_OK) || (total >= MAX_ALLOC_SIZE)) {
    errno = EINVAL;
    return 0;
}
#else
int err = __builtin_umull_overflow(num, size, &total);
if (err || (total >= MAX_ALLOC_SIZE)) {
    errno = EINVAL;
    return 0;
}
#endif
#else
total = num * size;
#endif

再來就是做了記憶體配置 rpaligned_alloc 後使用 memset(block, 0, total); 初始化為 0。

最後看到 _rprealloc

在 _rpmalloc_reallocate 的函式中可以看到也是分成了三個部分，分別是 small & medium , large 與更大的 size 的。

接下來可以看到這邊

if ((size_t)span->block_size >= size) {
    //Still fits in block, never mind trying to save memory, but preserve data if alignment changed
    if ((p != block) && !(flags & RPMALLOC_NO_PRESERVE))
        memmove(block, p, oldsize);
    return block;
}

確定 small / medium 記憶體 block 的位置和大小，然後檢查該記憶體 block 是否能夠容納新的大小 size。如果可以容納，則直接返回該記憶體 block 的指標，並且如果需要，將舊的數據移動到新的位置。

TODO
這邊的 flags 是什麼時候轉變成 0 / 1 的還沒有看懂

接下來的 large 與 huge size 記憶體 block 是相同的概念。

_rpmalloc_mmap_os

可以看到在這邊針對了很多不同的平台做了很多的區隔，但是我們只針對 x86-64 與 linux 的系統。

#  elif defined(MAP_HUGETLB)
	void* ptr = mmap(0, size + padding, PROT_READ | PROT_WRITE | PROT_MAX(PROT_READ | PROT_WRITE), (_memory_huge_pages ? MAP_HUGETLB : 0) | flags, -1, 0);
#    if defined(MADV_HUGEPAGE)
    // In some configurations, huge pages allocations might fail thus
    // we fallback to normal allocations and promote the region as transparent huge page
    if ((ptr == MAP_FAILED || !ptr) && _memory_huge_pages) {
        ptr = mmap(0, size + padding, PROT_READ | PROT_WRITE, flags, -1, 0);
        if (ptr && ptr != MAP_FAILED) {
            int prm = madvise(ptr, size + padding, MADV_HUGEPAGE);
            (void)prm;
            rpmalloc_assert((prm == 0), "Failed to promote the page to THP");
        }
    }
    #    endif
    _rpmalloc_set_name(ptr, size + padding);

可以看到先使用 mmap 配置空間給 ptr ，接著檢查是否回傳的值為 MAP_FAILED，如果是的話，就再使用 mmap 重新配置空間，並且使用 madvise 來給出這段記憶體空間的建議。

並且使用到了 prctl 這個系統呼叫來為 vma 命名

#if defined(__linux__) || defined(__ANDROID__)
    const char *name = _memory_huge_pages ? _memory_config.huge_page_name : _memory_config.page_name;
    if (address == MAP_FAILED || !name)
        return;
    // If the kernel does not support CONFIG_ANON_VMA_NAME or if the call fails
    // (e.g. invalid name) it is a no-op basically.
    (void)prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, (uintptr_t)address, size, (uintptr_t)name);

最後做了一些 address offset 後就可以回傳 ptr 。

_rpmalloc_unmap_os

這邊是先將 address 先 offset 回來之後，先做 munmap 之後，再做 madvise 的建議，而沒有直接的去 unmap 這段記憶體空間，讓作業系統決定記憶體的處理。

#else
    if (release) {
        if (munmap(address, release)) {
            rpmalloc_assert(0, "Failed to unmap virtual memory block");
        }
    } else {
#if defined(MADV_FREE_REUSABLE)
    int ret;
    while ((ret = madvise(address, size, MADV_FREE_REUSABLE)) == -1 && (errno == EAGAIN))
        errno = 0;
    if ((ret == -1) && (errno != 0)) {
#elif defined(MADV_DONTNEED)
    if (madvise(address, size, MADV_DONTNEED)) {
#elif defined(MADV_PAGEOUT)
    if (madvise(address, size, MADV_PAGEOUT)) {
#elif defined(MADV_FREE)
    if (madvise(address, size, MADV_FREE)) {
#else
    if (posix_madvise(address, size, POSIX_MADV_DONTNEED)) {
#endif
        rpmalloc_assert(0, "Failed to madvise virtual memory block as free");
        }
    }
#endif
#endif

test/main.c

可以看到它最了很多的測試，包括了 thread 或是 test_named_pages 等等的功能。

int
test_run(int argc, char** argv) {
	(void)sizeof(argc);
	(void)sizeof(argv);
	test_initialize();
	if (test_alloc())
		return -1;
	if (test_realloc())
		return -1;
	if (test_superalign())
		return -1;
	if (test_crossthread())
		return -1;
	if (test_threaded())
		return -1;
	if (test_threadspam())
		return -1;
	if (test_first_class_heaps())
		return -1;
	if (test_large_pages())
		return -1;
	if (test_named_pages())
		return -1;
	if (test_error())
		return -1;
	printf("All tests passed\n");
	return 0;
}

isoalloc 學習筆記

從 hankluo6 / 2021 年報告中可以看到在 isoalloc 使用了 MADV_POPULATE 這樣的機制來降低 page fault！

先 clone 下來後進行編譯測試

$ git clone https://github.com/struct/isoalloc.git
$ cd isoalloc/
$ make tests

可以得到這樣的輸出

...
Running unaligned_free test... Succeeded
Running incorrect_chunk_size_multiple test... Succeeded
Running big_canary_test test... Succeeded
Running zero_alloc test... Succeeded
Running sized_free test... Succeeded
17 Tests passed
0 Tests failed

一連測試了幾個方法都沒有出現 bug ，代表目前的版本應該沒什麼大問題!

可以看到這個專案的檔案結構很清楚，主要常用的應該是這幾個目錄

build : 用來存放 make library 後產生的 share object 執行檔的目錄
incude : 用來存放標頭檔的目錄
src : 用來存放原始程式碼的目錄
tests : 用來存放測試程式的目錄
utils : 存放 shell 腳本的地方

README.md

在這邊可以看到 isoalloc 只支援 64-bit 的系統，並且也是引入了跟其他配置器類似的 arena 的實作。

在每個 block 都會使用 2 個 bits 來作為狀態的顯示

00 代表空閒的 chunk
10 代表該 chunk 正在被使用
01 代表曾被使用過但是現在是空閒的
11 金絲雀 chunk (canary chunk)

除此之外， isoalloc 還有其他的特色

每個 chunk 都是 2 的冪，並且都是 align 8 個 bytes
可以在啟用 THREAD_SUPPORT 的時候，由 spinlock 或是 mutex 來達成 thread-safe 的目標
每個 chunk 都包含著 2 個 bits 的 bitmap
不論該 zone 所管理的 chunk 大小是多大，所有的 zone 都是 4 MB。
當有需要更大的配置或是這些預設的 zone 被用完的時候， zone 是可以再根據需求創建的

include

在 os 目錄中，有分別對應著各個平台的標頭檔。

可以看到在 android.h 中有使用 prctl 來為 VMA 設定他的 magic number，但是在 linux.h 中並沒有做這樣的 define; 相對應在 rpmalloc 有對這兩個平台做設定，不確定 iosalloc 為什麼沒有做設定

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 →

TODO: 提交 pull request

已提交 Commit

isoalloc / linux.h

#include <sys/prctl.h>
#include <byteswap.h>

#if defined(CPU_PIN) && defined(_GNU_SOURCE) && defined(__linux__)
#include <sched.h>
#endif

isoalloc / android.h

#include <sys/prctl.h>

/* This magic number is usually defined by Android Bionic:
 * https://android.googlesource.com/platform/bionic/+/263325d/libc/include/sys/prctl.h#42 */
#ifndef PR_SET_VMA
#define PR_SET_VMA 0x53564d41
#endif

#ifndef PR_SET_VMA_ANON_NAME
#define PR_SET_VMA_ANON_NAME 0

rpmalloc / rpmalloc.c

#  if defined(__linux__) || defined(__ANDROID__)
#    include <sys/prctl.h>
#    if !defined(PR_SET_VMA)
#      define PR_SET_VMA 0x53564d41
#      define PR_SET_VMA_ANON_NAME 0
#    endif
#  endif

接下來可以看到其他的 header，從檔名就可以大致知道每個檔案的用途。
特別看到 iso_alloc_ds.h 從這個 header 可以得到我們所使用的結構定義
iso_alloc_zone_t , iso_alloc_root 或是 zone_quarantine_t 等等的結構體。

src

首先先特別看到 iso_alloc_util.c 這個檔案中的 mmap_pages 這個函式

INTERNAL_HIDDEN ASSUME_ALIGNED void *mmap_pages(size_t size, bool populate, const char *name, int32_t prot) {
#if !ENABLE_ASAN
    /* Produce a random page address as a hint for mmap */
    uint64_t hint = ROUND_DOWN_PAGE(rand_uint64());
    hint &= 0x3FFFFFFFF000;
    void *p = (void *) hint;
#else
    void *p = NULL;
#endif
    size_t sz = ROUND_UP_PAGE(size);

    if(sz < size) {
        return NULL;
    }

    int32_t flags = (MAP_PRIVATE | MAP_ANONYMOUS);
    int fd = -1;

#if __linux__
#if PRE_POPULATE_PAGES
    if(populate == true) {
        flags |= MAP_POPULATE;
    }
#endif

#if MAP_HUGETLB && HUGE_PAGES
    /* If we are allocating pages for a user zone
     * then take advantage of the huge TLB */
    if(sz == ZONE_USER_SIZE || sz == (ZONE_USER_SIZE >> 1)) {
        flags |= MAP_HUGETLB;
    }
#endif
#elif __APPLE__
#if VM_FLAGS_SUPERPAGE_SIZE_2MB && HUGE_PAGES
    /* If we are allocating pages for a user zone
     * we are going to use the 2 MB superpage flag */
    if(sz == ZONE_USER_SIZE || sz == (ZONE_USER_SIZE >> 1)) {
        fd = VM_FLAGS_SUPERPAGE_SIZE_2MB;
    }
#endif
#endif

    p = mmap(p, sz, prot, flags, fd, 0);

    if(p == MAP_FAILED) {
        LOG_AND_ABORT("Failed to mmap rw pages");
    }

#if __linux__ && MAP_HUGETLB && HUGE_PAGES && MADV_HUGEPAGE
    if(sz == ZONE_USER_SIZE || sz == (ZONE_USER_SIZE >> 1)) {
        madvise(p, sz, MADV_HUGEPAGE);
    }
#endif

    /* All pages are mapped as if we will never need
     * them. This is to ensure RSS stays managable */
    dont_need_pages(p, sz);

    if(name != NULL) {
        name_mapping(p, sz, name);
    }

    return p;
}

可以看到這個函式針對 linux 的環境下使用到 MAP_POPULATE 這個 mmap 的參數。

先看到 madvise 的部分

從 man page 看起

$ man madvise

需要 include 的函式庫

#include <sys/mman.h>

語法

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

功能
提供給核心關於記憶體使用的建議，要特別注意還有另外一個實作是 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，用於指示核心應在映射期間立即將檔案中的所有內容讀入到新建的映射區域中。這樣可以提高後續對這些內容的存取速度，因為所有資料已經存在於頁面快取中，而不必等到實際存取這些頁面時才進行檔案存取。

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

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

接下來可以做個小實驗，把 map_populate 註解掉，然後藉由 Makefile 中的幾個測試，來觀察該 advise 對於系統的影響。

perf 結果	system malloc	isoalloc (有 map_populate)	isoalloc (無 map_populate)
context-switches	81	91	143
page-faults	433,117	200,698	202,752
cycles	2,736,496,520	3,895,062,512	3,940,056,221
instructions	5,163,961,202	5,166,597,836	5,188,067,947
branches	1,057,012,596	1,077,344,361	1,085,839,342
branch-misses	2,028,648	7,933,186	8,018,593
time elapsed	0.61596	0.87356	0.88456

可以看到有使用 map_populate 的情況下，確實有減少一些些的 page-faults ，但是相對的沒有增加太多的時間。

TODO: 針對上述實驗，提出適合使用 map_populate 的時機並落實在 rpmalloc (或自行實作的程式碼中)。

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 →

jserv

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 →

注意用語，參見:

避免濫用「通過」，可改為「藉由」，否則無法區分 "pass" 一詞。

根據 map_populate 的特性，我認為以下幾個是可以使用的時機

初始化一個大型的連續記憶體
- 當需要在使用 mmap 進行映射後馬上使用的記憶體 block
需要快速訪問的記憶體
- 不希望因為 page fault 而造成延遲的情況
減少 I/O 成本
- 使用 MAP_POPULATE 可以減少因為存取映射範圍而引起的 I/O 操作。這在需要連續存取大量資料的情況下，可以提高性能並減少 I/O 成本。

TODO: 針對並行環境設計高效記憶體配置器

檢討上述「記憶體配置器的雛形及改進」的實作，針對並行環境，設計高效率的記憶體配置器，可沿用自己的程式碼或改寫 rpmalloc (採用 public domain 形式發佈)，應特別考慮以下:

lock-free 的記憶體配置器設計
運用 MADV_POPULATE 一類的機制來降低 page fault，參見 2021 年報告
per-cpu vs. per-thread caching，參見 2022 年報告
在 Arm64 主機測試 (聯繫授課教師以取得存取權限): eMag 8180 及 Ampere Altra

使用 `MAP_POPULATE`

首先先針對上面的情境找出適合將 map_populate 加在 rpmalloc 的地方。

在 _rpmalloc_mmap_os 這個函式中找到設定 mmap 的 flags，

int flags = MAP_PRIVATE | MAP_ANONYMOUS | MAP_UNINITIALIZED;

接著可以在下面，設定條件決定是否要添加 MAP_POPULATE 這個 flag 。

if(size + padding > 1024*1024*8 || size + padding < SMALL_SIZE_LIMIT){
    flags = flags | MAP_POPULATE | MAP_NORESERVE;
}

目前先以小於 small size 的或是大於 8 MB 大小的記憶體的情況添加這個 flag

首先為了確定上面所提到的使用情境是正確的，會在配置不同尺寸的時候決定是否加上 flag ，並且可以用多個測試來進行比對。

原始版本 (rpmalloc-test)

 Performance counter stats for './rpmalloc-test' (5 runs):

        16,509,426      page-faults                                                   ( +-  0.11% )
        16,509,426      minor-faults                                                  ( +-  0.11% )
                 0      major-faults                                                
   553,975,362,094      instructions                                                  ( +-  0.68% )
           919,771      context-switches                                              ( +-  0.20% )

            68.613 +- 0.296 seconds time elapsed  ( +-  0.43% )

部份使用 MAP_POPULATE 的版本 (也就是使用上面的修改) (rpmalloc-test)

 Performance counter stats for './rpmalloc-test' (5 runs):

        16,185,547      page-faults                                                   ( +-  0.29% )
        16,185,547      minor-faults                                                  ( +-  0.29% )
                 0      major-faults                                                
   556,617,021,374      instructions                                                  ( +-  0.35% )
           911,142      context-switches                                              ( +-  0.21% )

            68.864 +- 0.247 seconds time elapsed  ( +-  0.36% )

全部使用 MAP_POPULATE (rpmalloc -test)

 Performance counter stats for './rpmalloc-test' (5 runs):

            12,993      page-faults                                                   ( +-  0.00% )
            12,993      minor-faults                                                  ( +-  0.00% )
                 0      major-faults                                                
 1,117,216,317,339      instructions                                                  ( +-  4.67% )
           737,240      context-switches                                              ( +-  0.33% )

            122.44 +- 4.10 seconds time elapsed  ( +-  3.35% )

從上面的結果可以看到，一般的情況都是 minor page fault ，並且使用了 MAP_POPULATE 這個 flag 確實可以降低 page fault 的數量，但是因為他要做額外的操作進而導致 instructions 的數量大幅的上升，讓執行的時間也到增加到了兩倍，這同樣的也代表著並不能夠任意的使用 MAP_POPULATE 。

而在配置記憶體的時候如果用上面的設置的話，可以減少大約 2% 左右的 page-fault 。

接著想要測試冷啟動時的 page fault
可以使用 sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches' 釋放 pagecache/dentries/inodes
接著再做一次測試

$ perf stat -e page-faults,minor-faults,major-faults,instructions,context-switches  ./rpmalloc-test

原始版本 (rpmalloc-test)

 Performance counter stats for './rpmalloc-test':

        16,585,121      page-faults                                                 
        16,585,116      minor-faults                                                
                 5      major-faults                                                
   569,581,393,755      instructions                                                
           908,074      context-switches                                            

      69.099672079 seconds time elapsed

     480.820388000 seconds user
      63.563367000 seconds sys

部份使用 MAP_POPULATE 的版本 (也就是使用上面的修改) (rpmalloc-test)

 Performance counter stats for './rpmalloc-test':

        16,079,175      page-faults                                                 
        16,079,171      minor-faults                                                
                 4      major-faults                                                
   557,578,740,402      instructions                                                
           910,770      context-switches                                            

      68.608629878 seconds time elapsed

     476.495534000 seconds user
      62.025617000 seconds sys

全部使用 MAP_POPULATE (rpmalloc -test)

 Performance counter stats for './rpmalloc-test':

            13,005      page-faults                                                 
            12,990      minor-faults                                                
                15      major-faults                                                
 1,009,650,134,500      instructions                                                
           736,523      context-switches                                            

     116.736806481 seconds time elapsed

     478.742738000 seconds user
      86.820077000 seconds sys

接著稍微改變了一下想法，將程式碼改成下面這樣

int flags = MAP_PRIVATE | MAP_ANONYMOUS | MAP_UNINITIALIZED;
if((size + padding > (LARGE_SIZE_LIMIT + 4096 * 36) || size + padding < MEDIUM_SIZE_LIMIT)){
    flags = flags | MAP_POPULATE | MAP_NORESERVE;
}

稍微放寬一些對於大尺寸進行 populate 的範圍

就可以得到以下這樣的結果

 Performance counter stats for './rpmalloc-test' (5 runs):

        15,565,320      page-faults                                                   ( +-  1.10% )
        15,565,320      minor-faults                                                  ( +-  1.10% )
                 0      major-faults                                                
   583,762,008,543      instructions                                                  ( +-  1.16% )
           933,827      context-switches                                              ( +-  0.18% )

            71.865 +- 0.727 seconds time elapsed  ( +-  1.01% )

可以看到的是他的 minor page fault 數值又下降了一些，並且也沒有將執行時間變得太長，影響性能。
接著用這樣的程式碼來進行 mimalloc-bench 的測試

詳細的測試結果可以看到 rpmalloc 測試結果中的 mimalloc-bench 測試 v1

從這三者的測試結果來看，可以發現部分使用 MAP_POPULATE 的版本在執行時間與原版本的差不多，並且在 xmalloc-testN 這項測試裡面的 page-fault 表現比原本的版本好! 而在 glibc-thread 這項的測試中，表現與原版本的差不多。

並且可以看到 rpmalloc 測試結果中的 mimalloc-bench 測試 v2

這個部份可以到使用了 MAP_POPULATE 這個 flag 確實減少了很多的 page fualt ，並且就算是部份使用也可以降低約 33% 的 page fault 。在這項測試中，就比較難發現出全部使用 MAP_POPULATE 所帶來的副作用，也就是執行時間只有小幅度的上升，並沒有像是上面的 rpmalloc-test 所造成的那麼嚴重。

假如將 rpmalloc-test 指定以一個 CPU 核心執行的話，可以明顯的觀察到 page-fault 的下降

$ taskset -c 0 perf stat -e page-faults,minor-faults,major-faults,instructions,context-switches  ./rpmalloc-test

...

 Performance counter stats for './rpmalloc-test':

         4,239,576      page-faults                                                 
         4,239,576      minor-faults                                                
                 0      major-faults                                                
   201,423,099,279      instructions                                                
           105,047      context-switches                                            

      46.926902575 seconds time elapsed

      25.090759000 seconds user
      10.509427000 seconds sys

這個就是 lock-contention 以及不同的 thread 在執行所造成的 page-fault 。
在 mimallic-bench 也會出現相同的問題

1 個 core

$ taskset -c 0 ../../bench.sh rp rp rp rp rp xmalloc-test glibc-thread
benchmarking on 1 cores.

...
#------------------------------------------------------------------
# test    alloc   time  rss    user  sys  page-faults page-reclaims
xmalloc-testN rp    1.456 17848 4.72 0.27 2 4223
xmalloc-testN rp    1.484 19260 4.72 0.27 0 4577
xmalloc-testN rp    1.484 19064 4.76 0.23 0 4527
xmalloc-testN rp    1.496 19064 4.70 0.30 0 4527
xmalloc-testN rp    1.490 19064 4.71 0.28 0 4526
glibc-thread rp    7.702 3656 2.00 0.00 0 762
glibc-thread rp    7.715 3656 2.00 0.00 0 762
glibc-thread rp    7.769 3656 2.00 0.00 0 762
glibc-thread rp    7.757 3656 2.00 0.00 0 761
glibc-thread rp    7.769 3656 2.00 0.00 0 761

12 個 core

../../bench.sh rp rp rp rp rp xmalloc-test glibc-thread
benchmarking on 12 cores.

...
#------------------------------------------------------------------
# test    alloc   time  rss    user  sys  page-faults page-reclaims
xmalloc-testN rp    0.524 72332 46.89 4.92 7 17901
xmalloc-testN rp    0.435 85520 44.02 4.40 3 21194
xmalloc-testN rp    0.493 78096 43.79 4.88 7 19340
xmalloc-testN rp    0.415 76304 44.04 4.42 1 18890
xmalloc-testN rp    0.476 86288 43.28 4.52 2 21389
glibc-thread rp    1.247 15164 21.77 0.01 8 3627
glibc-thread rp    1.249 15164 21.78 0.00 10 3630
glibc-thread rp    1.256 15168 21.80 0.00 9 3624
glibc-thread rp    1.250 15164 21.77 0.01 8 3625
glibc-thread rp    1.262 15164 21.76 0.04 9 3627

可以看到在不同的 CPU 數量執行下，結果也會不同。

而在 rpmalloc 的測試文件 test/main.c 中可以看到

static void
test_initialize(void) {
    cpu_set_t prevmask, testmask;
    CPU_ZERO(&prevmask);
    CPU_ZERO(&testmask);
    sched_getaffinity(0, sizeof(prevmask), &prevmask);     //Get current mask
    sched_setaffinity(0, sizeof(testmask), &testmask);     //Set zero mask
    sched_getaffinity(0, sizeof(testmask), &testmask);     //Get mask for all CPUs
    sched_setaffinity(0, sizeof(prevmask), &prevmask);     //Reset current mask
    int num = CPU_COUNT(&testmask);
    hardware_threads = (size_t)(num > 1 ? num : 1);
}

在這個函式取得了真實 CPU 中的 thread 數量，以我的電腦為例 (5600X)，有六個核心, 十二個執行緒，因此在這邊 hardware_threads 就是 12。

而在下面可以看到在不同的測試函式中，就會有設定 thread 的上下限制，但是通常是最多 16 或是 32 個執行緒，最少 2 個執行緒。

static int
test_thread_implementation(void) {
    uintptr_t thread[32];
    uintptr_t threadres[32];
    unsigned int i;
    size_t num_alloc_threads;
    allocator_thread_arg_t arg;

    num_alloc_threads = hardware_threads;
    if (num_alloc_threads < 2)
        num_alloc_threads = 2;
    if (num_alloc_threads > 32)
        num_alloc_threads = 32;
...

static int
test_crossthread(void) {
    uintptr_t thread[32];
    allocator_thread_arg_t arg[32];
    thread_arg targ[32];

    rpmalloc_initialize();

    size_t num_alloc_threads = hardware_threads;
    if (num_alloc_threads < 2)
        num_alloc_threads = 2;
    if (num_alloc_threads > 16)
        num_alloc_threads = 16;
...

per-cpu vs. per-thread caching

per-cpu 與 per-thread 都是兩種常見的優化技術，兩者的目的都是為了減少對共享資源的競爭，以提高效能和可擴展性

per-cpu

每個配置器實例僅由對應的 CPU 核使用，因此減少不同處理器核之間的競爭。這種方式適用於多核系統，其中多個處理器核可能同時進行記憶體配置和釋放操作。每個核心都擁有自己的配置器實例，可以獨立地進行操作，從而避免不必要的同步和競爭。這提高了整體的配置性能，減少鎖的使用，並改善可擴展性

per-thread

每個執行緒都擁有自己的配置器實例，用於該執行緒的記憶體配置和釋放操作。這種方式適用於多執行緒程式，其中多個執行緒可能同時進行記憶體配置和釋放操作。每個執行緒都有自己的配置器實例，可以獨立地進行操作，而不會干擾其他執行緒的配置操作。這樣做可以減少鎖的使用，減少競爭，並提高整體的配置性能和可擴展性

rpmalloc

在 rpmalloc 中的實作目前是 per-thread。

在 Performance Tuning TCMalloc 中有提到說目前 tcmalloc 的實作， per-cpu 的性能是比 per-thread 還要好的，也因此它成為預設的選項。

mstress
- 5600X 的 per-thread (不同的 thread number)
  
  在這邊可以到 thread 的數量越多，競爭所造成的結果也會越多，同時也造成時間呈線性的增長。
cache-scratch
- 5600X 的 per-thread (不同 object size)
  
  對於不同大小的 object 也可以看到呈現的是線性的增長。

ARM64 主機測試

先使用 M1 macbook (記憶體 8 G + 儲存空間 256 G) 來進行測試，由於剩餘的空間不足以分割磁碟灌雙系統，因此以下實驗使用 docker 來進行。

docker 的 image 可以在 Ubuntu:22.04 - linux; arm64 variant v8 中得到

然後我所配置給 docker 的資源為

CPU : 6 Cores
Memory : 6 GB
SWAP : 2 GB

接著就可以開始使用 docker，基本的命令可以從這邊查找 macOS macbook M1 使用 docker 虛擬 ubuntu ，為 ROS 做準備

$ docker start ubuntu
ubuntu
$ docker exec -it ubuntu bash
root@3d6c975773a7:/#
...

接著使用 uname -a 與 lscpu 來檢查規格

# uname -a
Linux 3d6c975773a7 5.15.49-linuxkit #1 SMP PREEMPT Tue Sep 13 07:51:32 UTC 2022 aarch64 aarch64 aarch64 GNU/Linux
# lscpu
Architecture:          aarch64
  CPU op-mode(s):      64-bit
  Byte Order:          Little Endian
CPU(s):                6
  On-line CPU(s) list: 0-5
Vendor ID:             0x00
  Model:               0
  Thread(s) per core:  1
  Core(s) per cluster: 6
  Socket(s):           -
  Cluster(s):          1
  Stepping:            0x0
...

從 htop 的資訊也可以看到記憶體與分配給他的資源一致。

接著就可以開始測試

在使用 mimalloc-bench 的時候，會遇到一些問題

docker 中的 perf 問題
- 可以用 Cannot run perf inside container on M1 Mac #6551 這邊所提到的方法 cp /usr/lib/linux-tools/5.15.0-49-generic/perf /usr/bin/perf 來解決 (其中 linux kernel 版本可能不同，自行更改成自己的版本即可)
bazel ARM64 版本
- 可以在這邊解決 install.sh
接著有些記憶體配置器在編譯時會出錯
- scudo
- sm

在 alloc-test 這個測試中，因為不是 apple 架構所以會進到 else 區域，但是又不是 x86 架構，所以沒辦法 #include <x86intrin.h> ，所以將其稍做修改

#include <time.h>
//#if defined(CLOCK_REALTIME) || defined(CLOCK_MONOTONIC)
static inline uint64_t get_timestamp(void) {
  struct timespec t;
  #ifdef CLOCK_MONOTONIC
  clock_gettime(CLOCK_MONOTONIC, &t);
  #else  
  clock_gettime(CLOCK_REALTIME, &t);
  #endif
  return ((uint64_t)t.tv_sec * 1000) + ((uint64_t)t.tv_nsec / 1000000);
}
#else
#include <x86intrin.h>
static inline uint64_t get_timestamp(void) {
    return __rdtsc();
}

修改的版本

//#include <x86intrin.h>
#include <time.h>
static inline uint64_t get_timestamp(void) {
  struct timespec t;
  #ifdef CLOCK_MONOTONIC
  clock_gettime(CLOCK_MONOTONIC, &t);
  #else
  clock_gettime(CLOCK_REALTIME, &t);
  #endif
  return ((uint64_t)t.tv_sec * 1000) + ((uint64_t)t.tv_nsec / 1000000);
}

這樣就可以正常的執行測試了

參見: https://github.com/DLTcollab/sse2neon/blob/master/sse2neon.h#L9168

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 →

jserv

經過老師的提醒，將上述修改成以下

...
#elif defined(__aarch64__) || defined(_M_ARM64)
static inline uint64_t get_timestamp(void){
    uint64_t val;
    __asm__ __volatile__("mrs %0, cntvct_el0" : "=r"(val));
    return val;
}
#else
#include <x86intrin.h>
static inline uint64_t get_timestamp(void) {
    return __rdtsc();
}
...

可以在 mimalloc-bench ( arm64 ) 結果這邊看到他與 system allocator 與 mimalloc, tcmalloc 的相比較。

mimalloc-bench 的測試工具是使用 time ，在 linux 的環境下面的可以用 man time 來查看使用的方法，而使用 macos 的環境下可以使用 gtime --help 這個指令來查看 man page 。

而 mimalloc-bench 幫我們列出了幾個資訊

%E : 該行程所執行的時間
%M : 該行程所持有的最大實體記憶體使用量 ( 單位 KB)
%U : 該行程在 User mode 使用 CPU 的總秒數
%S : 該行程在 Kernel mode 使用 CPU 的總秒數
%F : 該行程在執行時所產生的 major page fault
%R : 該行程在執行時所產生的 minor page fault

因此，透過以上的資訊以及 mimalloc-bench ( arm64 )，我們可以觀察出各個 memory allocator 的特性。

針對不同的情境設計記憶體配置器

以下是一些常見的記憶體配置器性能指標:

記憶體使用量 (Memory Usage)
評估記憶體配置器所使用的記憶體量，通常以位元組為單位。較低的記憶體使用量表示較高的效能，因為它可以減少記憶體浪費和碎片化。
配置和釋放速度 (Allocation and Deallocation Speed)
衡量記憶體配置器進行記憶體配置和釋放操作的速度。快速的配置和釋放速度可提高程式的效能。這可以用配置和釋放操作所需的時間或操作數量來評估。
記憶體碎片化 (Memory Fragmentation)
評估記憶體配置器在長時間運行後產生的記憶體碎片化程度。碎片化可能導致記憶體浪費和效能下降。常見的碎片化類型包括外部碎片（已配置區域之間的未使用空間）和內部碎片（已配置區域內部的未使用空間）。
內部和外部碎片的比例 (Ratio of Internal and External Fragmentation)
衡量內部碎片和外部碎片之間的比例。過高的比例可能表示記憶體配置器效能不佳。
配置和釋放的效能成本 (Allocation and Deallocation Overhead)
指記憶體配置器執行配置和釋放操作時所需的額外成本。這可能包括管理資料結構、同步機制、系統呼叫等。較低的效能成本意味著更高的效能。
記憶體洩漏 (Memory Leaks)
評估記憶體配置器是否存在記憶體洩漏問題，即已配置但未正確釋放的記憶體。記憶體洩漏可能導致記憶體資源浪費和系統穩定性問題。

可以使用 valgrind 這個工具來對記憶體的操作進行分析

分析的命令以及 massif 工具這些使用方法可以從這邊尋找 valgrind + 自動測試程式

可以進行改進的地方

使用組合語言直接執行 >> 操作
從 tcmalloc/sizemap.h 這邊看到可以在 x86-64 與 aarch64 的平台下使用組合語言來作右移的操作，並且可以降低 7% 的時間
在 aarch64 的架構上面使用 wfe 來取代 yield
在 mimalloc/atomic.h 這邊可以看到對於許多的硬體做了不同 spin 指令定義，而對於 aarch64 平台上使用 wfe 指令會比起使用 yield 好。
在 memcpy 的時候，運用 aarch64 的架構上的 NEON 指令

針對經常配置大頁面的設計

在 perf 測試 mimalloc-bench 的結果中可以看到 malloc-large 在進行了對大尺寸的記憶體配置改進後，雙平台 (x86-64 與 arm64) 都有減少了大量的 page-fault 數量，也有提昇了約 6~ 33 % 的執行時間; 這個改進也改善了 rpmalloc 在配置超大空間時弱勢的部份。

原本

#------------------------------------------------------------------
# test    alloc   time  rss    user  sys  page-faults page-reclaims
malloc-large sys   02.04 534076 1.47 0.57 0 510572
malloc-large rp    09.62 410752 0.85 8.77 0 7784586
malloc-large mi    01.71 780476 1.51 0.20 0 194394
malloc-large tc    01.71 573992 1.49 0.21 0 184554
malloc-large je    09.46 446420 0.97 8.47 0 7510863

修改 rpmalloc 結果

#------------------------------------------------------------------
# test    alloc   time  rss    user  sys  page-faults page-reclaims
malloc-large sys   02.04 534080 1.46 0.58 0 510569
malloc-large rp    05.99 412040 1.49 4.49 0 7816587
malloc-large mi    01.71 780520 1.48 0.23 0 194396
malloc-large tc    01.71 573996 1.49 0.21 0 184554
malloc-large je    09.32 446384 0.90 8.41 0 7510863

同時也可以看到，在不增加最大 RSS (Resident Set Size) 的情況下，執行的時間縮短了不少，同時也拉近了跟其他配置器的差距。

綜合上述使用 MAP_populate 這個章節，可以發現到適合使用 map_populate 的情境就是頻繁配置記憶體區塊的時候; 但是為了兼顧性能以及避免濫用，我設定在中小型或是極大尺寸的配置時才啟用 MAP_populate

已知造成的問題
- 有可能造成沒必要的預填充而 context-switches 與 instructions 數量增多
- 相容性問題，在 macos 上就沒有提供這樣的 flag
潛在的問題
- 記憶體佔用，若是分配的空間極大的話，可能會佔用大量記憶體，導致記憶體壓力增加，進而觸發 swapping
- 無形中的浪費資源，若是只須存取極大檔案中的一小部份，就會花費很多資源但沒運用到

目前打算設置三個等級的 flag ，

關閉 MAP_POPULATE
部份使用 MAP_POPULATE
全部使用 MAP_POPULATE

而預設會以 部份使用 MAP_POPULATE 為主

而使用者可以在前面的 define 自行決定該開啟哪種等級的

#if defined(__linux__)
#  include <linux/version.h>
#    if LINUX_VERSION_CODE >= KERNEL_VERSION(2, 6, 23)
#      define ENABLE_SMALL_MEDIUM_POPULATE 1
#      define ENABLE_HUGE_POPULATE 0
#      define ENABLE_ALL_POPULATE 0
#    endif
#endif

詳細程式碼 👉 commit

TODO:
實作根據配置各尺寸的頻率來自動調整是否開啟 MMAP_POPULATE

針對安全性所做的設計

接下來可以看到 security 這個測試中， rpmalloc 有幾個測試沒有通過

[late timeout] security/double_free_delayed_medium
[late timeout] security/double_free_delayed_small
[late timeout] security/double_free_interleaved_medium
[late timeout] security/double_free_interleaved_small
...
[late timeout] security/double_free_medium
...
[late crash]   security/impossibly_large_malloc_large
...
[late crash]   security/impossibly_large_malloc_large
...

從 Security benchmarks / README.md 可以發現開發者有說明到

double-free detection isn't necessarily worth it when you have types isolation.

以及 impossibly_large_malloc_xxxxx 系列沒有通過不一定是錯誤的，因為從測試原始碼看到測試的內容為

並且在 rpmalloc/README.md 中提到

All entry points assume the passed values are valid, for example passing an invalid pointer to free would most likely result in a segmentation fault. The library does not try to guard against errors!.

所以代表把無效的指標傳給 free() 是會造成出錯的，因為它假設了所有的值都是有效的!

int main(void) {
    char *p = malloc_noinline(-2);
    if (p != NULL) {
      NOT_CAUGHT();
    }
    free_noinline(p);
    return 0;
}

而 rpmalloc 所限制的最大分配空間為

#if ENABLE_VALIDATE_ARGS
//! Maximum allocation size to avoid integer overflow
#undef  MAX_ALLOC_SIZE
#define MAX_ALLOC_SIZE            (((size_t)-1) - _memory_span_size)
#endif

如果將 ENABLE_VALIDATE_ARGS 設為 1 ( 預設為 0 ) 即可通過這個 impossibly_large_malloc 測試

增加對於 double free 的檢查

在 rpmalloc 原本的實作中並沒有針對 double free 做檢查，雖然這個是作者原本所設定的，但是想到可以引入 isoalloc 中的 bitmap 來做檢查，也就是使用記憶體對齊的特性來將標記的 bit 塞入其中，如以下這樣設定

00 free chunk
10 currently in use
01 was used but is now free
11 canary chunk

以下這個簡單的程式碼做個測試

#include <stdlib.h>
#include <stdio.h>
int main()
{
    char *p = malloc(160);
    free(p);
    free(p);
    fprintf(stderr, "Nothing happen!\n");
    return 0;
}

可以看到不同記憶體配置器都有不同的反應

$ ./a.out 
free(): double free detected in tcache 2
Aborted (core dumped)

$ LD_PRELOAD=/home/hanchi/linux2023/mimalloc-bench/extern/iso/build/libisoalloc.so ./a.out 
[ABORTING][1423977](src/iso_alloc.c:1432 iso_free_chunk_from_zone()) Double free of chunk 0x99efcb25b00 detected from zone[4] dwords_to_bit_slot=253 bit_slot=16246

$ LD_PRELOAD=/home/hanchi/linux2023/mimalloc-bench/extern/mi/out/release/libmimalloc.so ./a.out
Nothing happen!

$ LD_PRELOAD=/home/hanchi/linux2023/mimalloc-bench/extern/rp/bin/linux/release/x86-64/librpmallocwrap.so ./a.out 
Nothing happen!
... (終端機卡死)

我認為透過這樣的方法可以用低成本的方式來檢查 double free 的問題。

針對快取以及分支所做的設計

參考自 2021 年報告在存取陣列的時候，針對下一個預期會取到的元素進行 prefetch ，如下所示

-for (size_t ispan = insert_count; ispan < count; ++ispan) {
+for (size_t ispan = insert_count; ispan < count; ) {
    span_t* current_span = span[ispan];
    // Keep master spans that has remaining subspans to avoid dangling them
    if ((current_span->flags & SPAN_FLAG_MASTER) &&
(atomic_load32(&current_span->remaining_spans) > (int32_t)current_span->span_count)) {
        current_span->next = keep;
        keep = current_span;
    } else {
        _rpmalloc_span_unmap(current_span);
    }
+    __builtin_prefetch(span[++], 0, 0);
}

在經過 perf 的結果 (Ryzen 5600x)

有預取

 Performance counter stats for './rpmalloc-test' (20 runs):

    19,016,402,909      cache-misses              #   21.814 % of all cache refs      ( +-  0.09% )
    87,671,540,969      cache-references                                              ( +-  0.13% )
   604,844,341,776      instructions              #    0.26  insn per cycle           ( +-  0.42% )
 2,343,257,502,027      cycles                                                        ( +-  0.15% )

            72.902 +- 0.272 seconds time elapsed  ( +-  0.37% )

無預取

 Performance counter stats for './rpmalloc-test' (20 runs):

    19,305,822,162      cache-misses              #   22.117 % of all cache refs      ( +-  0.07% )
    86,570,884,312      cache-references                                              ( +-  0.18% )
   585,581,019,359      instructions              #    0.25  insn per cycle           ( +-  0.54% )
 2,378,333,354,642      cycles                                                        ( +-  0.21% )

            72.828 +- 0.304 seconds time elapsed  ( +-  0.42% )

接著看到 ARM64 主機 (emag) 的測試

有預取

 Performance counter stats for './rpmalloc-test' (5 runs):

       81423634583      cache-misses              #   12.906 % of all cache refs      ( +-  0.11% )
      638238912242      cache-references                                              ( +-  0.29% )
     1322074731734      instructions              #    0.14  insn per cycle           ( +-  0.37% )
     9510725698958      cycles                                                        ( +-  0.34% )

            179.63 +- 2.02 seconds time elapsed  ( +-  1.12% )

無預取

 Performance counter stats for './rpmalloc-test' (5 runs):

       81399858302      cache-misses              #   12.857 % of all cache refs      ( +-  0.11% )
      630993412273      cache-references                                              ( +-  0.30% )
     1304157537462      instructions              #    0.14  insn per cycle           ( +-  0.34% )
     9497768685113      cycles                                                        ( +-  0.14% )

            182.06 +- 2.15 seconds time elapsed  ( +-  1.18% )

可以看到也許有提昇了一些些的性能，但是基本上算是微乎其微

成果 & 結論

因為在老師的 ARM64 主機建置 mimalloc-bench 需要 sudo 的密碼，因此，我寫了一個類似的 benchmark ，測試的內容也與 mimalloc-bench 相同 (扣除一些出現相容性問題的測試集)，並且可以將結果繪製成長條圖，詳情可以參見 allocator-bench

所以以下的結果都會是使用這個 benchmark 所跑出來的結果

下圖中的圖例

rpmalloc ：原始版本的 rpmalloc
my-rpmalloc ：經過改進過後的 rpmalloc

最後的 my-rpmalloc 是使用 commit 64d525c 這個版本的，整合了上面所有的改進。

x86-64 平台

time
major-faults
minor-faults
faults(total)
instructions
cycles

arm64 平台

time
major-faults
minor-faults
faults(total)
instructions
cycles

問題紀錄

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 個卻是可以正常執行的，不知道為何會這樣。

這個問題是源自於作業系統的 overcommit 所導致的
可以使用
$ cat /proc/sys/vm/overcommit_memory
0
來取得當前的設定值，總共有三個可以的值

0: heuristic overcommit (this is the default)

1: always overcommit, never check

2: always check, never overcommit

而之後測試的時候都應該關閉 overcommit
所以可以輸入
$ sudo sh -c 'echo 2 > /proc/sys/vm/overcommit_memory'
雖然這樣可能會導致電腦在使用的時候性能微微降低，但是可以在設計或是測試的時候更準確

allocator 中的結構命名

在 alloc.h 中有一個結構的命名為 thread_cache
他的定義如下

struct thread_cache {
    struct slot *bin[N_CLASS];
    size_t bin_size[N_CLASS];
    int arena_index; // -1 if uninitialized
    bool dead; // true if destroyed or uninitialized
};

雖然知道它與小尺寸的記憶體的配置有關，通過使用這個結構體可以在配置的時候加速，但是不確定為何前面要加上 thread ，也有可能是我還沒 get 到開發者的用意。

mimalloc-bench 編譯問題

照著 README.md 的指示，使用以下命令

$ git clone https://github.com/daanx/mimalloc-bench.git
$ cd mimalloc-bench
$ ./build-bench-env.sh all

會在 PartitionAlloc 的部份出現這樣的問題

...
________ running 'python3 partition_alloc_builder/tools/clang/scripts/update.py' in '/home/hanchi/mimalloc-bench/extern/pa'
Downloading https://commondatastorage.googleapis.com/chromium-browser-clang/Linux_x64/clang-llvmorg-17-init-10134-g3da83fba-1.tar.xz .......... Done.
Running hooks: 100% (7/7), done. 
Done. Made 26 targets from 60 files in 74ms
ninja: Entering directory `out/Default'
ninja: error: '../../buildtools/third_party/libc++/trunk/src/format.cpp', needed by 'obj/buildtools/third_party/libc++/libc++/format.o', missing and no known rule to make it

注意看 mimalloc-bench/blob/master/.github/workflows/all.yml 的使用方式:
./build-bench-env.sh all no-dh no-hd no-sm no-mesh no-nomesh no-pa no-gd no-fg no-lf no-lt no-tcg no-lp no-rp
也就是跳過某些記憶體配置器的實作，避免編譯錯誤。

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 →

jserv

經過老師的提醒之後，在這台 x86-64 架構與 ubuntu 22.04 的電腦已經可以正常的建置環境，所使用的命令為 mimalloc-bench/blob/master/.github/workflows/all.yml 中的 ubuntu 那段

$ ./build-bench-env.sh all no-lean no-gd no-ff no-fg no-lt no-lf no-hd no-tcg no-pa

同時也測試了 M1 macbook 的環境下能否順利建置。
MacOS 版本為 Ventura 13.2.1 的環境下，使用以下命令來完成環境的建置

$ ./build-bench-env.sh all no-lean no-gd no-ff no-fg no-pa no-tc

接下來就進入漫長的測試過程，若有錯誤會在進行更新!

mimalloc-bench 測試專案版本衝突

可以在 build-bench-env.sh 中看到 version_rocksdb 的版本設定是 8.1.1

build-bench-env.sh

# benchmark versions
readonly version_redis=6.2.7
readonly version_lean=v3.4.2
readonly version_rocksdb=8.1.1
readonly version_lua=v5.4.4

但是在執行測試的時候，腳本上面的是 7.3.1 版本

bench.sh

readonly version_redis=6.2.7
readonly version_rocksdb=7.3.1

這樣就會造成在測試的時候找不到該測試目錄夾，而沒有測試到
這時候只要將 bench.sh 的版本也更新到 8.1.1 就可以正常運作了。

已提交 pull request / commit

rpmalloc 在 macos 上編譯問題

在這台 arm64 的架構下進行編譯

$ python3 configure.py -t macos --toolchain clang -a arm64
$ ninja 
[1/16] CC rpmalloc/rpmalloc.c
FAILED: build/ninja/macos/debug/arm64/rpmalloc-32e30f9/rpmalloc-a2b50b2.o 
...
In file included from rpmalloc/rpmalloc.c:3597:
rpmalloc/malloc.c:268:1: error: no previous prototype for function 'reallocarray' [-Werror,-Wmissing-prototypes]
reallocarray(void* ptr, size_t count, size_t size) {
^
rpmalloc/malloc.c:267:8: note: declare 'static' if the function is not intended to be used outside of this translation unit
extern void* RPMALLOC_CDECL
       ^

會出現這樣的問題，而導致編譯失敗
我的解決方法是在 rpmalloc/malloc.c 的開頭添加了 reallocarray 的宣告

void* reallocarray(void* ptr, size_t count, size_t size);

這樣就可以正常編譯了

$ ninja 
[46/46] LIPO bin/macos/release/rpmalloc-test

在進行 rpmalloc-test 時也是一切正常。

這邊不確定是 rpmalloc 的問題還是我電腦的 xcode 的問題。

ThunderX2 - Cavium 上 rpmalloc-test 的問題

這台主機的套件較舊，以 eMag 主機為主。

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 →

jserv

在 ThunderX2 - Cavium 這個有兩個 numa 節點的電腦上，在編譯以及執行 rpmalloc-test 上有遇到兩個問題

unknown option after ‘#pragma GCC diagnostic

在 test/main-override.cc 這個檔案中有以下這個巨集

#if defined(__GNUC__)
#pragma GCC diagnostic ignored "-Wmismatched-new-delete"
#endif

在 ThunderX2 目前版本的 g++ (9.4.0)是無法被識別到的，於是為了能夠通過編譯，先將其註解。

在 How can I turn on (literally) ALL of GCC's warnings? 中有人提到

Some will not work on GCC 10.
…
-Wmismatched-new-delete (gcc 11, not in gcc 10)

因此判斷在目前 ThunderX2 的環境是無法處理這個問題的。

rpmalloc-test 發生 memory-leak 的問題

在執行 rpmalloc-test 的時候，會發生非預期的問題，

$ ./rpmalloc-test 
Memory allocation tests passed
Memory reallocation tests passed
Memory super aligned tests passed
Memory cross thread free tests passed
rpmalloc-test: rpmalloc/rpmalloc.c:3030: rpmalloc_finalize: Assertion `(atomic_load32(&_mapped_pages) == 0) && "Memory leak detected"' failed.
Aborted (core dumped)

目前在思考是否是因為 numa 節點所導致的問題，或是 gcc/g++ 版本的問題，因為在另外一台的 ARM 主機並沒有遇到這樣的問題

Linux 核心專題: 實作高效記憶體配置器

任務簡述

TODO: 記憶體配置器的雛形及改進

rbtmalloc 開發紀錄

TODO: 研究既有的記憶體配置器實作

thestinger/allocator 學習筆記

rb.h

test_small.c

test_large.c

test_huge.c

alloc.c

memory.c 與 memory.h

memory_init

memory_decommit

memory_commit

memory_map

memory_remap_fixed

Lock 操作

free list 設計

mimalloc-bench 學習筆記

建置環境

支援的記憶體配置器與測試

目前的測試

rpmalloc 學習筆記

閱讀程式碼筆記

_rpmalloc_allocate_small

_rpmalloc_allocate_medium

_rpmalloc_allocate_large

_rpmalloc_allocate_huge

_rpmalloc_deallocate_small_or_medium

_rpmalloc_deallocate_direct_small_or_medium

_rpmalloc_deallocate_defer_small_or_medium

_rpmalloc_mmap_os

_rpmalloc_unmap_os

test/main.c

isoalloc 學習筆記

README.md

include

src

TODO: 針對並行環境設計高效記憶體配置器

使用 MAP_POPULATE

per-cpu vs. per-thread caching

per-cpu

per-thread

rpmalloc

ARM64 主機測試

針對不同的情境設計記憶體配置器

可以進行改進的地方

針對經常配置大頁面的設計

針對安全性所做的設計

增加對於 double free 的檢查

針對快取以及分支所做的設計

成果 & 結論

x86-64 平台

arm64 平台

問題紀錄

thestinger/allocator 編譯失敗

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

allocator 中的結構命名

mimalloc-bench 編譯問題

mimalloc-bench 測試專案版本衝突

rpmalloc 在 macos 上編譯問題

ThunderX2 - Cavium 上 rpmalloc-test 的問題

unknown option after ‘#pragma GCC diagnostic

rpmalloc-test 發生 memory-leak 的問題

Reference Links

`rb.h`

`test_small.c`

`test_large.c`

`test_huge.c`

`alloc.c`

`memory.c` 與 `memory.h`

`memory_init`

`memory_decommit`

`memory_commit`

`memory_map`

`memory_remap_fixed`

使用 `MAP_POPULATE`