rpmalloc 探討

contributed by <workat60474,chasingfar>

系統環境

Ubuntu 16.04.2
 Linux version 4.8.0-36-generic

 gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.4)
* Architecture:          x86_64
* CPU 作業模式：    32-bit, 64-bit
* Byte Order:            Little Endian
* CPU(s):                4
* On-line CPU(s) list:   0-3
* 每核心執行緒數：2
* 每通訊端核心數：2
* Socket(s):             1
* NUMA 節點：         1
* 供應商識別號：  GenuineIntel
* CPU 家族：          6
* 型號：              61
* Model name:            Intel(R) Core(TM) i5-5257U CPU @ 2.70GHz
* 製程：              4
* CPU MHz：             1008.544
* CPU max MHz:           3100.0000
* CPU min MHz:           500.0000
* BogoMIPS:              5400.35
* 虛擬：              VT-x
* L1d 快取：          32K
* L1i 快取：          32K
* L2 快取：           256K
* L3 快取：           3072K
* NUMA node0 CPU(s):     0-3

預期目標

• 編譯和重現 rpmalloc 程式碼
• 比照 針對多執行緒環境設計的 Memory allocator 和 Malloc 對於多執行緒程式的效能影響 的方式，探究 rpmalloc 和 GNU glibc (以及其他 memory allocator) 效能差異

背景知識

記憶體管理機制

Address space

• 執行檔中的記憶體位址稱為邏輯位址 ( logic address )或者稱為虛擬位址（virtual address)，由這些 logic address 所形成的集合稱為 邏輯位址空間(logical address space)。

• 記憶體中每個儲存單元都有對應的位址，稱為實體位址 ( physical address )，邏輯位址所對應到的實體位址集合就稱為實體位址空間(physical address space)。

• 

• 在電腦中執行一個程式時，需要把指令與資料從硬碟等輔助記憶體中讀取出來到主記憶體（ main memory ) ，所以當 cpu 要將程式載入到主記憶體時，載入器（loader）便會依據主記憶體的使用情形，找一塊可供使用的記憶體空間把程式載入，並且透過 MMU(記憶體管理單元，Memory Management Unit) 來把 logical address 轉換成 physical address 。

• MMU 是一個硬體裝置，負責在程式執行時將邏輯位址轉換成實體位址，裝置內的基底暫存器(base register，或稱 relocation register)，存放著邏輯位址轉換成實體位址的基底值，所以當 CPU 將使用者的 process 所產生的邏輯位址傳送到 MMU 時，MMU 會將邏輯位址加上 base register 內的數值，以轉換成主記憶體的實體位址。

• 而保護的方法可以利用基底暫存器與界限暫存器 (bound register) 來達成，基底暫存器 (base register）存放著最小的記憶體實體位址，界線暫存器則存放邏輯位址範圍，每一個邏輯位址都必須小於 bound register 的邏輯位址範圍，邏輯位址再加上基底暫存器內的數值，就可以動態地轉換到記憶體的實體位址。

• 

分頁（Paging）

• 支援分頁的 OS 將載入的程式分割成固定大小的分頁 (pages)，主記憶體也分割成固定大小的頁框（ page frame ），其 page frame 的大小與分頁的大小相同，當要執行程式時，就把程式所有的分頁載入記憶體中任何可用的 page frame 中。

• 每個程式都具有一個分頁表 (page table) ， 分頁表中存有每個分頁在記憶體中的起始位址，當程式的分頁被載入到主記憶體中，必須在程式分頁表中記錄該分頁被載入至主記憶體的哪一個 page frame 中。

• 當然 OS 必須清楚知道主記憶體中哪些 page frame 被使用了，哪些 page frame 未被使用，以及系統中總共 page frame 數目有多少，這些資訊一般都被保存在稱為 frame table（頁框）的資料結構中。

• 

• CPU 所產生的 logic address 分成兩個部分 ： 分頁碼 (page number) 和 頁偏移（page offset）

  • 分頁碼 (page number): 指向分頁表的索引。
  • 頁偏移（page offset）： 用以表示與該分頁起始位址的距離。

• 

• 如上圖， page number p 被用來當成 page table 的索引，在 page table 中找到此分頁在 physical memory 中對應的基底位址 f 後，再和 page offset 組合定義出實體記憶體位址 (f,d)，由此可知 (p,d) 的邏輯位址透過分頁表查詢後，可以很容易得出實體記憶體位址（f,d） 。

TLB(Translation Look-aside Buffer)

• 存放 page table 的方法有很多種，如將 page table 儲存在主記憶體中，這樣一來要對記憶體某個位址存取的時候，首先經由一次的記憶體存取找到 page table 的紀錄，再與 page offset 相加產生 physical memory address 後，就可以存取記憶中的資料。
• 所以要存取一個資料或是指令，系統需要做最少兩次的記憶體存取，相當沒有效率，為了提升效率，可以將 page table 放在一種稱為 位址查閱緩衝 (Translation Look-aside Buffer，或稱關聯式記憶體)，的小型記憶體中。
• 

memory 與 disk

• 當虛擬記憶體地址的分頁不在實體記憶體中或已經被其他的資料佔有, 稱爲page fault
• 此時系統會到 disk 中相應的地方將磁碟分頁載入記憶體,然後重新執行該指令
• 

linux 內 process 的記憶體管理機制

• 透過上述的背景介紹，大致了解了 virtual memory 與 physical memeory 的互相映射機制，接著來看看實際上 process 的 memory 空間的管理機制。
• 
• 參考linux 記憶體的說明文件，可知：
  • User space 可用的空間為：0x0000000000000000 ~ 0x00007FFFFFFFFFFF
  • kernel space 可用的空間為：0xFFFF800000000000 ~ 0xFFFFFFFFFFFFFFFF
• 將 User space 放大來看可分成：
  • Stack:由高位置往低位置成長（向下成長），存放在函數中定義的變數（也就是所有在 function中宣告的非靜態變數，或者說區域變數） Automatic Variable，函式所傳回的資料等等。
  • Mapping Area: 提供給 mmap() 呼叫用的空間，詳細可參考：MMAP
  • Heap: 存放動態分配的記憶體空間，如呼叫 malloc() 所得到的空間，由低位址往高位址成長(向上成長)，當我們多次動態配置記憶體，新配置到的記憶體通常會出現在較高的位置，疊加在先前配置的記憶體上面，也是我們該次作業探討的重點。
  • BSS: 意為「僅由符號起始的區塊」(block started by symbol)，存放尚未初始化的 global variable 或 static variable，又稱 Uninitialized Data Segment，值得一提的是，儘管使用者並沒有手動初始化這些變數，這些變數都會被自動初始化為 0。
  • Data: 存放程式一執行就已經初始化（宣告時就順便賦值的初始化，事後自己賦值或者 memset 等等的並不算）的 global variable 或 static variable，又稱 Initialized Data Segment。
  • Code: 又稱為 Text Segment，這是整個 user space 的最低位址，存放的是程式編譯過的可執行的機器語言指令碼，，這些指令碼會形成最後的執行檔的一部分，並且在程式起跑時載入到記憶體中，存在 Code 區。值得一提的是，Code 區都會被系統設定為唯讀 (readonly)，以避免被使用者不小心或者刻意修改，形成恐怖的不可預期的致命錯誤。。
• 參考這張圖可以了解個區域的增長情形：
  

管理 Heap

• Unix 系統以往就有提供介面，可用於直接管理 data segment ，然而因為 malloc（）以及其他記憶體配置機制，比較容易使用且功能完備，一般人較少使用這些介面，然而對於想要自己實作基於 Heap-based 之分配機制的人，可參考以下介面：

#include <unistd.h>
    int brk(void *end);
    void *sbrk(intptr_t increment);

• heap 和 stack 之間的分界線叫做 break(轉折) 或 break point(轉折點)，在現代的電腦架構上，data segment 位於他自己的記憶體映射上，我們會將映射的結尾位址標記作 break point 。

• 

• brk(void *end) 可用於將上圖中的 break 指標，設定為 end 所指定的位址。

  • 執行成功時，傳回 0。
  • 執行失敗時，傳回 -1 並且把 errno 設為 ENOMEM。

• sbrk(intptr_t increment) 會將 break 分線移動 increment 大小的位移（其中 increment 可為正或負數），來修改 data segment 的結尾位址。

  • sbrk() 會傳回修改過的 break 位置 ，因此若 increment 為 0 ，則會傳回當前的 break。

• 雖然可以使用 brk 和 sbrk 來移動 heap 中 break 分線，藉此更改 heap 的大小，達到記憶體配置的效果，但是會產生記憶體破碎的問體，詳細可參考：Buddy memory allocation

匿名記憶體映射（anonymous memory mapping）

• 對於大型記憶體的配置申請，glib 並不會使用 heap 而是會建立一個 匿名記憶體映射（anonymous memory mapping）以滿足記憶體的分配要求。
  • 匿名記憶體映射只是一個大型，填滿零值的記憶體區塊，備妥以供使用。
  • 此類映射位於 heap 之外，所以他們不會造成 data segment 的碎裂問題。
  • 使用匿名記憶體映射的優點：
    • 不會有碎裂問題，當程式不再需要一個匿名記憶體映射時，映射會被解除，而且記憶體會被立即歸還給系統。
    • 匿名記憶體映射的尺寸是可調整的，具有可調整的存取權限。
    • 每個記憶體分配存在於獨立的記憶體映射中，不需要管理全域性的 heap。
  • 使用匿名記憶體映射的缺點(相對於 Heap)：
    • 每個記憶體映射的大小是 page size 的整數倍。因此，如果一個記憶體分配的大小不是頁面尺寸的整數倍，則會造成 slack space （slack space 係指內部碎裂所浪費的空間）的浪費。
    • 相較於從 HEAP 把記憶體釋回到 OS ，建立一個新的記憶體映射會需要比較多開銷，記憶體分配的規模越小，此現象越顯著。
  • 為了讓優點有發揮的空間，同時避開缺點， glibc 的 malloc 實作會使用 data segment 來滿足小型的分配需求，以及使用匿名記憶體映射來滿足大型的分配需求。
  • 將超過 128K 的記憶體分配使用匿名記憶體映射，而小於 128K 則使用來自 heap 的空間。
  • 可使用 mmap() 用於建立記憶體映射，而 munmap() 用於銷毀記憶體映射。

#include <sys/mman.h>
void *mmap(void     *start, 
           size_t   length,
           int      prot,
           int      flags,
           int      fd,
           off_t    offset
            );

• void * start: 第一個參數，代表映射的起始位址，通常被設為 null ，代表讓 kernel 自行決定映射的起始位址，當然也可以設為非 NULL，不過前提是得確保其能夠對齊 page，但這會對移植性造成限制，且鮮少有程式會在乎映射存在記憶體的何處。
• size_t length： 映射的長度，以 bytes 為單位。
• int prot: 映射區域的保護方式。可以為以下幾種方式的組合：
  • PROT_EXEC 映射區域可被執行
  • PROT_READ 映射區域可被讀取
  • PROT_WRITE 映射區域可被寫入
  • PROT_NONE 映射區域不能存取
• int flags :用以描述映射的類型，以及其行為：
  • MAP_FIXED: 要求 mmap() 把 addr 視為必要條件，如果 kernel 無法把映射擺在所指定的位址上，則此次呼叫會失敗。而如果位址和 length 參數與既有的映射重疊，則重疊的 page 會被新的映射取代和拋棄。因為使用這個選項需要充分了解 process 的位址空間，且移植性差，通常不鼓勵使用。
  • MAP_PRIVATE : 不予許與其他 process 共享此映射，且檔案的映射採取 copy on write 的操作方式，此 process 在記憶體上的任何改變，不會馬上反映在實際的檔案中。
  • MAP_SHARED :允許映射到相同檔案的其他所有 process 共用此記憶體映射，寫入該映射等效於寫入相對應的檔案。而讀取該映射也可以一併得知出其他 process 所做的改變。
  • MAP_ANONYMOUS ：代表此映射為匿名映射。此時會忽略參數 fd 和 offset，不過考慮到有些系統會預期 fd 值為 -1，考慮到移植性，應該把 -1 傳入 fd，且將 offset 設為 0。
• 若映射成功則返回映射區的起始位址，否則返回MAP_FAILED(-1)，並且把錯誤原因存於 errno 中。

#include<sys/mman.h>
     int
     munmap(void *addr,
            size_t len
           );

• 呼叫 munmap() 會將匿名映射所分配的記憶體釋回到 kernel 。

chunk

• 由於 brk/sbrk/mmap 屬於 system-call 如果每次都使用 system-call 來獲取記憶體，對系統負荷較高，除此之外，這樣獲取記憶體的方式由於造成碎裂，因為 Heap 是由低位址向高位址成長，若低位址的記憶體尚未被釋放，高位址的記憶體也無法回收。
• 因此，malloc 採用類似 memory-pool 的方式，先申請一大塊記憶體空間，接著將其分配成不同大小的區塊 (chunk)，等待 user 透過malloc 呼叫時，再從中選取一塊可用的 chunk 即可。
• 邏輯上 malloc 所分配的記憶體單位的最小單位為 chunk，定義如下：

struct malloc_chunk {
  INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      mchunk_size;       /* Size in bytes, including overhead. */
  struct malloc_chunk* fd;                /* double links -- used only if free. */
  struct malloc_chunk* bk;
  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

typedef struct malloc_chunk* mchunkptr;

• 未被使用到的 chunk (free chunks) 會使用 struct chunk *fd 和 struct chunk *bk 作為 doubly-linked-list 串接起來，而已經被使用的 chunk (allocated chunk ) 則不會用到那兩個 pointer ，而是直接將他們用來存放資料。

• 

• chunk的大小在32bit下最小16 bytes，對齊8 bytes；64bit下最小32 bytes，對齊16 bytes

  • 需要至少4個word作為free chunk時的field

• 位於 Heap segment 的 chunk 可分成以下四種類型：

  • Allocated chunk
  • Free chunk
  • Top chunk
  • Last Remainder chunk

• allocated chunk (一個正在使用中的 chunk ) :

  • 圖中的 chunk pointer 指向 chunk 的起始位址。
  • 圖中的 mem pointer 用來 return 給使用者告知其申請的記憶體空間的起始位址。
  • Size 用以表示此 chunk 的大小。
  • prev_size :若前一個 chunk 是使用中的，該欄位會被用以放置 user data，而若是前一個 chunk 是未使用的，該欄位會被用以紀錄前一個 chunk 之可用空間大小。
  • 最低位的 3 個 bits 為 status bits:
    • N: NON_MAIN_ARENA ，用以表明該 chunk 是否Dynamic created arena(或稱 thread arena 或 non-main-arena ) 的一部分。
    • M: 表 IS_MMAPPED ，用以表明是否為透過 mmap 映射來的記憶體區塊。
    • P：表 PREV_INUSE，用以表明其前一個 chunk 是否正在被使用。

• Free chunk (未被使用的 chunk )
  

  • fd 指標用來指向 binlist 中的下一個 chunk(並非連續記憶體中的 next chunk)

  • bk 指標用來指向 binlist 中的前一個 chunk(並非連續記憶體中的 previous chunk)

  • prev_size : 注意到，若有兩個 free chunk 在 bin 中互相連接，則會將其合併成單一個 free chunk （因此不會有兩個 free chunk 互相連接的情況出現），因此對某一個 free chunk 而言，其前一個 chunk 一定是使用中的 chunk (allocated chunk )，因此對該 free chunk 而言其 prev_size 永遠會被用來記錄其前一個 chunk 的 user data。

  • size: 記錄該 chunk 之可用空間大小。

• top chunk:

  • 在進行第一次 malloc 呼叫的時候，heap 會被切割成兩個區塊，分別是被分配出去的記憶體空間，以及剩下的空間，而剩下的空間則被稱為 top chunk。

  • top chunk 不隸屬於任何 bin

  • 被視為分配記憶體的最後防線，當沒辦法在 bins 或者 fastbin 中找到大於使用者的記憶體需求的 chunk 時，若幸運的 top chunk 的 size 大於使用者的記憶體需求，會將 top chunk 分成兩塊

    • 其中一塊大小為使用者的記憶體需求，用以 return 給 user。
    • 剩下的 remainder chunk，則作為新的 top chunk。

  • 若 top chunk 的大小仍然小於使用者的記憶體需求，則利用 sbrk 調整 main arena 或者利用 mmap 調整 thread arena ，來增加 top chunk 的大小。

• Last Remainder Chunk ：

  • 當 user 試圖要求一塊 small chunk 大小的空間，但是又沒辦法再 smallbin 和 unsortedbin 中找到超過該大小的空間時， binmaps 會試圖去更大的 bin 中尋找可用的 chunk，一旦找到後，會將該 chunk 分成兩部分：
    • user chunk: 用以回應 user request return 給 user。
    • remainder chunk: 其 size 為剩下的部分，除了將其加入 unsortedbin 之外(在下方 bin 會提到)，也會將其另為新的 last remainder chunk 。
  • 用以增進 locality of reference ：因為連續呼叫 malloc 要求 small chunk 大小的空間，可能會導致被配置的空間恰好彼此都相鄰。

bins

• 未被使用的 regular chunks 會以 linked-list 串連，並透過 bins 來管理。

• Bin 則是紀錄 free chunks 的資料結構 (freelist)，依據其大小和特性分成四種 Fast bin / unsorted bin / small bin / large bin 。

• glibc 實作裡，bins 依照其管理的記憶體大小分為四種

  • fastbin : 16B ≤ chunk size ≤ max_fast (default: 64B，可調整)

    • 

    • 當釋放 chunk 之記憶體空間時，如果 chunk size <= 72 bytes ，會被放進 fastbin 的 list 中。

    • 為 Singly linked list

    • 採取 Last-in-first-out，當有 memory request 時會優先使用 fastbin 串列中的第一個 chunk。

    • 沒有合併(coalesce)機制：不會取消 inuse bit，即不執行將兩個 freed chunk 合併成一個 ，，這麼做雖然會產生外部碎裂，但是可以加速釋放記憶體的過程。

    • 在 fastbin 中有共 10 個 bins，每個 bins 所管理（向下串連）的 chunk 都具有相同的 size，而這 10 個 bins 其所管理的 chunk size 依序為：16, 24, 32, 40, 48, 56, 64, 72, 80， 88 bytes（8 bytes 遞增）。

• bins: 以下陣列包含了 unsorted, small 以及 large bins. 總共包含了 126 個 bins。

• 

  • unsortedbin:
    • Number of bins – 1 個（Bin 1）
    • 採取 circular double linked list
    • 當small / large bin 中的 chunk 被釋放時（get freed ），並不會將這些 freed chuck 歸還至其所屬的 bin 串列中，而是將其加至 unsorted bin ，這麼做的目的是重複使用 chunks 以加速 allocation 和 deallocation。
    • 其存在目的類似記憶體中的 cache-layer。
    • size 不限，任何 chunk size 都屬於這裡。
  • smallbin : size ≤ 512B

    • Number of bins - 62 個 (Bin 2 to Bin 63 )。

    • 採取 circular doubly linked list

    • 採取 first-in-first-out，當有 memory request 時會優先使用 smallbins 串列中的最後一個 chunk。

    • samllbin 中各個 bin 其下所串接的 chunks 其 size 皆相同。

    • 有合併(coalesce)機制：不會有任兩個 freed chunk 彼此連接的狀況，任兩個 adjacent freed chunk 會被 合併成一個。

    • 當釋放 small chunk 時，會檢查其前一個或後一個 chunks 是否也已經被釋放(freed)，若是的話會啟動合併(coalesce)機制-將這兩個 chunks 從 smallbin 的 linked-list 中移除，並把這兩個 chunks 合併後的 chunk，加至 unsortedbin list的前端。

    • 因為 chunks size 都相同，malloc 時先找對應的 bin 裡有沒有可用的 chunk 即可。

  • largebin : size ≤ 128KB
    • Number of bins - 63 個 (Bin 64 to Bin 126 )。
    • 採取 circular doubly linked list
    • 可以從任何位置對 list 中的 chunks 做加入或移除。
    • largebin 中的各個 bin 其下所串接的 chunks 其 size 不全相同，但是有範圍限制，且範圍 size 為指數遞增：
      • largebin 中前 32 個 bin 採 64 bytes的 chunk size 遞增，(eg. largebin 中的第一個 bin- BIN 64 其 list 所包含的 chunks 之 size 為 512 bytes 到 568 bytes 之間, 而第二個 largebin - Bin 65 其 list 所包含的 chunks 之 size 為 576 bytes 到 632 bytes 之間 ，依此類推)。
      • largebin 中 第 33 - 48 個 bin 採 512 bytes 的 chunk size 遞增。
      • largebin 中 第 49 - 56 個 bin 採 4096 bytes 的 chunk size 遞增。
      • largebin 中 第 57 - 60 個 bin 採 32768 bytes 的 chunk size 遞增。
      • largebin 中 第 61 - 62 個 bin 採 262144 bytes 的 chunk size 遞增。
      • 而不在上述 chunk size 的範圍內的 chunk 會被放到 largebin 中最後一個 bin 裡。
    • 有合併(coalesce)機制，處理方式和 smallbin 相同。
    • 因為 bin 裡的 chunk 大小不一，會使用 sorted list 存，chunk 由小到大排列，並引進 fd_nextsize, bk_nextsize 等兩個 pointer 指向下一個大小不同的 chunk，用來加快 search。
    • 因為 largebin list 中 chunk size 不全相同，malloc 呼叫時會使用 best-fit 的策略，在一個range(bin)的list中尋找最合適大小的 chunk。
      • 一旦找到 chunk size 和 request 最接近的（當然是大於等於 request size ）chunk， 會將該 chunk 分成兩部分- user chunk 和 Remainder chunk ，將 user chunk 配置給 user （user chunk 的 size 等於 request size）而多出使用者需求的的記憶體則分至 Remainder chunk ，並把 Remainder chunk 加至 unsorted bin。
      • 如果在 largebin 中無法找到最合適（best-fit） 的 chunk，會使用 top-chunk 來配置記憶體給 user。

arena (分配區)

• arena 為邏輯上 malloc 用以管理記憶體區塊的最高單位。
• 透過區分 arena 如何從kernel 獲取記憶體的方式可分成以下兩種：
  • Main arena ： 管理 Heap 中 sbrk 和 brk 這兩個指標中間的記憶體空間。

    • created by main-thread

    • 當空間不足以滿足使用者需求時，會呼叫 brk 來擴展空間，每次預設最少分配 132Kb

    • 當透過 free 釋放記憶體後，被釋放的記憶體不會馬上歸還給 kernel 而是會把這些記憶體區塊歸還給 main arena bin ，而當下次 user 要求新的記憶體空間時，malloc 會先從 main arena bin 中尋找可用的 chunk，只有當 bin 中不存在可用的 chunk 時，才會透過 kernel 要求新的記憶體空間。

  • thread arena ( dynamically created arena)： 管理透過 mmap() 從 kernel 獲取的記憶體空間。
    • created by other-thread（eg. user thread）
    • 每個 thread 在呼叫 malloc()時會分配到一個 arena，但是 arena 和 thread 並不是在任何時候都是一一對應的， arena 的數目有其限制，只有在不超過限制的時候為一一對應
      • For 32 bit systems:
        Number of arena = 2 * number of cores.
        For 64 bit systems:
        Number of arena = 8 * number of cores.
    • 當空間不足以滿足使用者需求時，會呼叫 mmap() 來取得記憶體空間，每次預設大小為 1MB ，但是只有其中的 132Kb 會被設為 可讀寫（read-write）且這 132kb 會設為該thread 的 Heap memory 。
  • 當 user 要求的記憶體空間超過 128 KB (malloc(1321024)， 且 arena 內不具有這麼多可用空間的情況下，不管是 main arena 或是 thread arena 都會使用 mmap() 來進行空間配置，而不會使用 sbrk。
    *
  • Multiple Arena:
    • 當 main thread 呼叫 malloc 時，可以直接使用早已存在的 main arean。
    • 假若 thread 1 和 thread 2 第一次呼叫 malloc ， 且此時 arena number 尚未達到上限時，thread1 和 thread 2 會各自創造各自的 thread arena 並使用，直到此時 thread arena 和 thread 的數量還是一一對應。
    • 假若 thread 3 第一次呼叫 malloc，且此時 thread arena 的數目已達上限，會挑選 main thread 或者 thread arena 1 或 thread arena 2 其中之一給 thread 3 重複使用（reuse）。
      • 如何挑選 reuse 的 arena: 透過迴圈的方式走訪各個 arena，嘗試對走訪到的 arena 上鎖（lock that arena）
      • 如果成功上鎖了走訪到的 arena（只有當前未被使用的 arena 可以成功被上鎖） ，將該 arena 的記憶體配置給 user。
      • 如果走訪了一次仍然找不到閒置的 arena， 取自己的下一個 arena 並將其 blocked 等待該 arena 為 free 時可使用。
      • 詳細見下 code:

do
    {
      if (!mutex_trylock (&result->mutex))
        goto out;

      result = result->next;
    }
  while (result != next_to_use);

  /* Avoid AVOID_ARENA as we have already failed to allocate memory
     in that arena and it is currently locked.   */
  if (result == avoid_arena)
    result = result->next;

  /* No arena available.  Wait for the next in line.  */
  LIBC_PROBE (memory_arena_reuse_wait, 3, &result->mutex, result, avoid_arena);
  (void) mutex_lock (&result->mutex);

• Multiple Heaps:

• 在 glibc malloc 中有三種用來管理 Heap 的資料結構

1. heap_info:

typedef struct _heap_info
{
  mstate ar_ptr; /* Arena for this heap. */
  struct _heap_info *prev; /* Previous heap. */
  size_t size;   /* Current size in bytes. */
  size_t mprotect_size; /* Size in bytes that has been mprotected
                           PROT_READ|PROT_WRITE.  */
  /* Make sure the following data is properly aligned, particularly
     that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
     MALLOC_ALIGNMENT. */
  char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;

• 用以紀錄每個 heap 所屬的 arena(在 thread arena 中，每個arena 可能擁有超過一個 heap )
  • 紀錄前一個 heap 的資訊。
  • 尚未使用的 size
  • 已被使用的 size (mprotect_size)，已被設為可讀寫。

2. malloc_state

struct malloc_state
{
  /* Serialize access.  */
  mutex_t mutex;

  /* Flags (formerly in max_fast).  */
  int flags;

  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];

  /* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr top;

  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;

  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];

  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];

  /* Linked list */
  struct malloc_state *next;

  /* Linked list for free arenas.  */
  struct malloc_state *next_free;

  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

• 雖然一個 thread arena 可以擁有多個 heaps，但對所有 heaps 來說其只會屬於一個 arena header，而 malloc_stat 的功能相當於 arena header。
• malloc_state 用以紀錄 top-chunk / last-remainder chunk / bins / 下一個已被使用的 Arena Header 的資訊 / 下一個尚未被使用的 Arena Header 的資訊

3. malloc_chunk

struct malloc_chunk {

  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

• 作為 chunk-header ：一個 heap 可能根據 user 被切割成多個 chunks，而每個 chunk 都會有自己的 chunk header

取得統計資料

linux 所提供的 mallinfo() 可用於取得關於記憶體分配系統的統計資料

#include <malloc.h>
    struct mallinfo mallinfo(void) 

• mallinfo() 會傳回 mallinfo 結構中的統計資料，而此結構的傳回係透過值，而非指標，此結構的內容也定義於 <malloc.h>

 struct mallinfo {
               int arena;     /* Non-mmapped space allocated (bytes) */
               int ordblks;   /* Number of free chunks */
               int smblks;    /* Number of free fastbin blocks */
               int hblks;     /* Number of mmapped regions */
               int hblkhd;    /* Space allocated in mmapped regions (bytes) */
               int usmblks;   /* Maximum total allocated space (bytes) */
               int fsmblks;   /* Space in freed fastbin blocks (bytes) */
               int uordblks;  /* Total allocated space (bytes) */
               int fordblks;  /* Total free space (bytes) */
               int keepcost;  /* Top-most, releasable space (bytes) */
           };

其用法很簡單：

struct mallinfo m;
m = mallinfo();
printf("free chunk: %d\n",m.ordblks);

linux 還提供了 malloc_stats() 函式，此函式會把關於記憶體的統計資料印往 stderr

#include <malloc.h>
    void malloc_stats(void);

rpmalloc

概念介紹

• page alignment （可調整，預設為 64Kb) 以及 32 byte block alignment。

• Memory blocks 透過 size 被切割成 3 種，分別是

  • small blocks are [32, 2016] bytes
  • medium blocks (2016, 32720] bytes
  • large blocks (32720, 2097120] bytes
  • 上述三種不同大小的 block的大小 也被加細分割成不同大小的 size-class:
    • 在 small block 的大小中以 32 bytes 作為一個區隔尺寸建立一個 size-class，也就是說有 2016/32=63 個 buckets
    • 在 medium block 的大小中以 512 bytes 作為一個區隔尺寸建立一個 size-class，有 32720/512=60 個 buckets
    • 在 small block 的大小中以 span-size(預設是 64Kb) 作為一個區隔尺寸建立一個 size-class
  • 如果 span（span 是 allocator 用來分配記憶體的概念單位 ） 的 size 改變了，small block 所代表的 size-class 不變，但是 medium block 的大小改為 (2016, span size] bytes.

• 所有的空間需求都會對齊到 size class，例如：配置 42 bytes 的記憶體大小時，因為要對齊，所以會配置 64 bytes 大小的 block。

• Spans of pages can flow between threads when the thread cache overflows and are released to a global cache, or when the thread ends. Unlike tcmalloc, single blocks do not flow between threads, only entire spans of pages.

• 當該 thread cache overflow 且 該 span（memory pages） 將被釋放到 global cache 時或者是該 thread 終結時， span （memory pages）允許在 不同 thread 之間流動，但是只允許整個 page 流動，不可只流動一個 block。

• 不同 size-classes 的記憶體配置需求會由不同 memory pages 來提供，且每種 span 只會對應到一種 size class 。

• 所有 small medium class size 都有對應的 span configuration 用以描述 allocate 時需要多少 pages

• Larger blocks are mapped and unmapped directly.

• 為了減少呼叫 mmap/unmap 的次數，會將 small 和 medium blocks 分成 4 個 level ：

  • first level： 對每個 size-class 的 thread 都會有對應的 active-span
  • second level：對每個 size-class 的 thread 都會有對應的 list 紀錄空閑的 span。
  • third level：對各種 span 配置，會有一個 list 來紀錄各個 thread 中空閑的 span。
  • fourth level：對各種 span 配置，會有一個 global list 來紀錄空閑的 span。

• 每個 small 和 medium size-class 的 span 會紀錄追蹤有多少 block 是已配置/閒置的 ，不僅如此，各個 small 和 medium size-class 皆會以一個 list 來紀錄有多少可配置的 block。

• 為了避免死結，每個 span 都隸屬於分配自己的那個 thread (allocating thread)，且 cross-thread 的釋放動作會被推遲到 span 的 owner-thread 去執行。

• 對於 Large blocks 或者 super span 的 allocation 使用了兩層 cached 的機制，在 allocations 時會先檢查 thread 的 free list 有無可用的，再來會往 global 的 free list 尋找，當 free list 中找不到可用空間時，才會再跟記憶體要空間。

build 與 benchmark

• 在作者的 README 上有提示 build 的步驟，來將其編譯成為 static library ，我接著按照指示嘗試重新編譯。
• 使用 Ninja 來 build code 。
  • Ninja是什麼？Ninja 在其非常簡約的首頁這樣地描述著自己:它是絕佳的 make 替代品，因為速度飛快而且語法簡潔易懂。
• 首先當然是將整個專案 clone到本地端之後，進入 folder 利用：python configure.py -h 來進行 build 之前的 configure。
• 接著會出現以下的設定：

usage: configure.py [-h]
                    [-t {windows,linux,macos,bsd,ios,android,raspberrypi,pnacl,tizen}]
                    [--host {windows,linux,macos,bsd,ios,android,raspberrypi,pnacl,tizen}]
                    [--toolchain {msvc,gcc,clang,intel}]
                    [-c {debug,release,profile,deploy}]
                    [-a {x86,x86-64,ppc,ppc64,arm6,arm7,arm64,mips,mips64,generic}]
                    [-i INCLUDEPATH] [--monolithic] [--coverage]
                    [--subninja SUBNINJA]

Ninja build generator

optional arguments:
  -h, --help            show this help message and exit
  -t {windows,linux,macos,bsd,ios,android,raspberrypi,pnacl,tizen}, --target {windows,linux,macos,bsd,ios,android,raspberrypi,pnacl,tizen}
                        Target platform
  --host {windows,linux,macos,bsd,ios,android,raspberrypi,pnacl,tizen}
                        Host platform
  --toolchain {msvc,gcc,clang,intel}
                        Toolchain to use
  -c {debug,release,profile,deploy}, --config {debug,release,profile,deploy}
                        Build configuration
  -a {x86,x86-64,ppc,ppc64,arm6,arm7,arm64,mips,mips64,generic}, --arch {x86,x86-64,ppc,ppc64,arm6,arm7,arm64,mips,mips64,generic}
                        Add architecture
  -i INCLUDEPATH, --includepath INCLUDEPATH
                        Add include path
  --monolithic          Build monolithic test suite
  --coverage            Build with code coverage
  --subninja SUBNINJA   Build as subproject (exclude rules and pools) with the
                        given subpath

接著執行 ： python configure.py -t linux --toolchain gcc -a x86-64
利用 cat build.ninja 查看一下其內容如下：

ninja_required_version = 1.3

# configure.py arguments
configure_args = -t linux --toolchain gcc -a x86-64

# configure options
configure_target = linux
configure_host = linux
configure_toolchain = gcc
configure_archs = x86-64
configure_configs = 

buildpath = build/ninja/linux
target = linux
config = 
toolchain = 
cc = gcc
cxx = g++
ar = ar
link = gcc
includepaths = 
moreincludepaths = 
...
...

跑完後會在該資料夾生成 build.ninja 這個檔案
接著利用以下指令來 build ，

$ ninja

接著執行
$ sh runall.sh
就會針對 rpmalloc 跑所有的 benchmark

• benchmark

先來解釋 benchmark 的驗證方式：
* 指標一：每秒可以做幾次 malloc
* 指標二：memory overhead (會用到實際使用的 requested allocated memory 與 virtual memory size 做計算)
* 使用參數：

形式：

• benchmark <num threads> <mode> <distribution> <cross-thread rate> <loop count> <block count> <op count> <min size> <max size>
  * <num threads> 可以設定幾個 threads 來跑
  * <mode> 可以選擇是 random or fixed 來決定所分配到的 size 的分佈
  * 如果是 mode 選 random，那是要何種 distribution
  * 前一點 size 選擇的範圍會是 [<min size>,<max size>]
  * 會跑 <loop count> 次的迴圈做 allocate 動作
  * 每跑 <cross-thread rate> 次的迴圈會做一次 cross-thread deallocation (舉例來說就是從 threadA 做 allocation，會把這些 allocated memory 丟給 threadB 做 deallocation)
  * 目標分配 <block count> 個 blocks
  * 每次 loop iteration 會選其中的 <op count> 個 blocks 做 deallocation 再 allocation

使用方式

• rpmalloc_initialize : 在主程式開始時呼叫，以初始化rpmalloc
• rpmalloc_initialize_config : (可選)在程式開始時呼叫，以自訂記憶體映射等設定
• rpmalloc_finalize : 在主程式結束前呼叫，以清理rpmalloc
• rpmalloc_thread_initialize : 在執行緒開始時呼叫，以初始化執行緒的獨立資料
• rpmalloc_thread_finalize : 在執行緒結束前呼叫，以清理執行緒 cache
• rpmalloc_config : 取得當前設定

然後在程式中使用 rpmalloc 、 rpfree 、 rpcalloc 、 rprelloc 即可

閱讀原始碼

rpmalloc

RPMALLOC_RESTRICT void*
rpmalloc(size_t size) {
#if ENABLE_VALIDATE_ARGS
	if (size >= MAX_ALLOC_SIZE) {//檢查 size 是否合法
		errno = EINVAL;
		return 0;
	}
#endif
	_memory_guard_pre_alloc(size);//保護區塊
	void* block = _memory_allocate(size);
	_memory_guard_post_alloc(block, size);
	return block;
}

_memory_guard_pre_alloc 與 _memory_guard_post_alloc 是 macro ，
若有ENABLE_GUARDS 時會在前後各多 allocate 32 bytes 的防寫空間(guard_block)做保護(填滿MAGIC_GUARD值)

_memory_allocate 如下

//! Allocate a block of the given size
static void*
_memory_allocate(size_t size) {
	//如果 size 為中小型就從 thread_heap 裡 allocate
	if (size <= _memory_medium_size_limit)
		return _memory_allocate_from_heap(get_thread_heap(), size);
	else if (size <= LARGE_SIZE_LIMIT)
		return _memory_allocate_large_from_heap(get_thread_heap(), size);

	//Oversized, allocate pages directly
	//如果 size 過大就建立新的 page
	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 = _memory_map(num_pages * _memory_page_size, &align_offset);
	atomic_store32(&span->heap_id, 0);
	//Store page count in next_span
	span->next_span = (span_t*)((uintptr_t)num_pages);
	span->data.list.align_offset = (uint16_t)align_offset;

	return pointer_offset(span, SPAN_HEADER_SIZE);
}

rpfree

void rpfree(void* ptr) {
	_memory_guard_validate(ptr);
	//檢查guard_block是否為MAGIC_GUARD(未被覆寫、overflow)
	_memory_deallocate(ptr);
}

_memory_deallocate 如下

//! Deallocate the given block
static void
_memory_deallocate(void* p) {
	if (!p)return;//防止NULL pointer

	//Grab the span (always at start of span, using 64KiB alignment)
	//從 p 的開頭取得 span 指標，並從中取得 heap_id
	span_t* span = (void*)((uintptr_t)p & _memory_span_mask);
	int32_t heap_id = atomic_load32(&span->heap_id);
	heap_t* heap = get_thread_heap();
	//Check if block belongs to this heap or if deallocation should be deferred
	if (heap_id == heap->id) {//檢查 span 的 heap_id 是否與 thread_heap 的一致
		if (span->size_class < SIZE_CLASS_COUNT)
			_memory_deallocate_to_heap(heap, span, p);
		else
			_memory_deallocate_large_to_heap(heap, span);
	}
	else if (heap_id > 0) {//是否延遲操作
		_memory_deallocate_defer(heap_id, p);
	}
	else {
		//Oversized allocation, page count is stored in next_span
		size_t num_pages = (size_t)span->next_span;
		_memory_unmap(span, num_pages * _memory_page_size, span->data.list.align_offset, 1);
	}
}

Introduction to tpmalloc

參考資料：

Anatomy of Memory Managers
GLibc malloc internal (1): arena, bin, chunk and sub heap
Bins and Chunks
Some great articles to learn memory management