# 針對多執行緒環境設計的 Memory allocator
contributed by <`TempoJiJi`>, <`tundergod`>,<`jeff60907`>,<`chenan00`>

## 預期目標
* 閱讀論文，研究 SuperMalloc
* 使用 Supermalloc 在之前的作業上，比較成果
* 嘗試理解 SuperMalloc 原理，知曉和 glibc 使用的 PTMalloc3 之間的設計差異
* 延續 SuperMalloc 成果，對比 Daniel Micay 的 allocator，並考慮 small/large/huge object 等情況
* 思考 aggressive load balancing 的效益，並且試圖延伸
>> 一併參考之前學生的研究 [Real-time Linux 研究: Memory Allocation](https://embedded2016.hackpad.com/Real-time-Linux-Memory-Allocation-kS5wHum1S54) [name=jserv]

## 開發環境

* Ubuntu 16.04 LTS
* L1d cache: 32K
* L1i cache: 32K
* L2 cache: 256K
* L3 cache: 3072K
* Architecture: x86_64
* CPU op-mode(s): 32-bit, 64-bit
* Byte Order: Little Endian
* CPU(s): 4
* Model name: Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz

---

## 論文閱讀
[SuperMalloc: A Super Fast Multithreaded Malloc for 64-bit Machines](http://supertech.csail.mit.edu/papers/Kuszmaul15.pdf)

## 背景知識與"gblic Malloc"原理
* reference:
* [Linux對記憶體管理深入分析(上半部)](https://zhuanlan.zhihu.com/p/24753861)
* [Linux對記憶體管理深入分析(下半部)](https://zhuanlan.zhihu.com/p/24790164)
* [malloc實現原理](http://luodw.cc/2016/02/17/malloc/)
* [論文:SuperMalloc: A Super Fast Multithreaded Malloc for 64-bit Machines](http://supertech.csail.mit.edu/papers/Kuszmaul15.pdf)
* [Supermalloc程式碼-github](https://github.com/kuszmaul/SuperMalloc)
* [Malloc in glibc-github](https://github.com/sploitfun/lsploits/tree/master/glibc?spm=a313e.7916648.0.0.HoLHCG)
* [Understanding glibc malloc](https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/comment-page-1/?spm=a313e.7916648.0.0.HoLHCG)

#### 虛擬記憶體位址與實體記憶體位址
>>中英文關鍵字請以空白隔開
>>請在分組頁面中補上 github 連結
>>[color=red][name=課程助教]

* 現代處理器在處理記憶體位址使用虛擬記憶體位址技術.即當在匯編程式層面處理有關記憶體位址操作時,都使用虛擬位址進行操作.使每一個進程都擁有2^N^(N爲系統位元)個虛擬位址空間.
* 當實際的程式碼設計到記憶體的存取動作,會經由一個叫 MMU(Memory Management Unit) 的硬件完成從虛擬空間到實體空間的轉換(映射)

#### 分頁和位址的構成
* 虛擬和實體記憶體位址都以分頁 (page) 進行管理,在 linux 中頁的大小固定爲4096byte
* 記憶體位址的操作可以分爲頁號和頁內的偏移量
* MMU映射單位同樣爲頁,並以 page table 來實現控制

#### 記憶體分頁與硬碟分頁
* 當虛擬記憶體地址的分頁不在實體記憶體中或已經有被別的數據佔有,稱爲page fault
* 此時系統會到磁碟中相應的地方將磁碟分頁載入記憶體,然後重新執行該指令
* 具體操作如下圖:

#### 記憶體排序
* 在64位元系統中,理論上可用位址空間爲0x0000000000000000 ~ 0xFFFFFFFFFFFFFFFF.
* 但是linux64位元僅用低47位作爲記憶體空間,高17位作爲擴展(?)
* 所以,實際上可用位址空間爲x0000000000000000 ~ 0x00007FFFFFFFFFFF(user space)和0xFFFF800000000000 ~ 0xFFFFFFFFFFFFFFFF(kernel space)
* 其中的heap和mapping area都屬於malloc的操作範圍,並通過heap目前最高上限的記錄指標break對heap進行操作

#include <unistd.h>
int brk( const void *addr )
void* sbrk ( intptr_t incr );

* brk的參數是新的break上限,成功返回0,失敗返回-1
* sbrk的參數是需要申請的記憶體大小,返回heap的新上界break的地址.(傳入0則是查看brk的地址)
* 利用sbrk/brk都是通過heap中break的移動(低到高)來實現的,但容易產生記憶體碎片
* 當申請大記憶體時,malloc使用mmap申請記憶體,使用mmap函數只是分配虛擬記憶體,只有到對這塊虛擬記憶體進行真實訪問後,才會因爲page fault的關係通過kernel正式分配實體記憶體

#include <sys/mman.h>
void *mmap(void *addr, size\_t length, int prot, 
		int flags, int fd, off\_t offset);
int munmap(void *addr, size_t length);

#### Arena簡介
* 在linux作業系統使用ptmalloc2(glibc malloc)之前,所使用的dlmalloc有一個非常大的缺陷,它不能處理同時爲兩個thread分配記憶體
* ptmalloc在當一個新的process被建立出來之後，讓系統分配一個arena（分配區)給它,如果該行程是主行程那我們稱arena爲main arena,每個arena默認分配64MiB的記憶體
* main arena可以通過sbrk和mmap進行分配而thread arena只能通過mmap來分配.在使用mmap進行記憶體空間映射時也會盡量使每一個arena的記憶體區塊相隔夠遠
* 這是爲了防止造成記憶體不連續(如果行程需要更大的記憶體空間,連續的arena分配會造成記憶體空間不連續)
* non-arena(子分配區)在64位元系統中每次申請64M的記憶體大小(有)
* arena的數量限制為：

			For 32 bit systems:
     			Number of arena = 2 * number of cores + 1.
			For 64 bit systems:
     			Number of arena = 8 * number of cores + 1.

* 當有16個thread,就會從arena中直接記憶體64x16 = 1GB的記憶體給child process使用

* 如果thread的數量超過arena的限制，會從main arena -> arena 1 -> arena 2開始找並嘗試lock它（如果arena沒在使用,heap就會被lock）
* 若都不能進行lock就對thread process的建立進行阻塞直到該thread再次發送malloc請求。
* malloc就從最靠近的arena開始找(每一個通過mmap進行arena空間的分配,所以他們都是隨機分布的)，如果有找到（例如找到arena 1），那麼新的thread就會和thread1共享arena1

> 在執行multi-thread運算時,當thread的數量到達一定程度程式的時間效能會非常差是不是跟arena的等待和建立有關? [name=lim wen sheng]

#### Heap 簡介
* ptmalloc2在heap的管理上主要使用以下三種不同的資料結構
* heap_info:因爲電腦核數的限制,當thread超過一定數量時,一個arena就會包含很多個thread在使用,而每一個thread都有一個heap,所以通過heap_info(heap header)去管理,當arena中的heap不夠用,系統會通過mmap分配更多的heap給arena

* malloc_state:也稱爲arena header,每個thread只有一個arena header,arena header包含 top chunk,bins,last remainder等信息(在malloc每一次被調用時會查看malloc_state是否爲空)

* malloc_chunk:就是chunk header,malloc在管理heap時會把heap切割成非常多大小不同的chunk,每一個chunk都有自己的chunk header記錄它的狀態等訊息(malloc chunk的結構參數會在下面介紹)

**main thread不會有很多個heap,所以也不會有heap_info的struct
main arena與thread arena不一樣,他的 malloc_state是一個全域變數(thread arana的是sbrk heap segment的一部分)**
從上圖可以看出，thread arena只含有一個malloc_state(即arena header)，卻有兩個heap_info(即heap header)。由於兩個heap segments是通過mmap分配的記憶體，兩者在記憶體分布上並不相鄰而是分屬於不同的記憶體區間，所以爲了便於管理，libc malloc將第二个heap_info結構體的prev成員指向了第一個heap_info結構提的起始位置（即ar_ptr成員），而第一個heap_info結構體的ar_ptr成員指向了malloc_state，這樣就構成了一個單鏈表，方便後續管理。

#### chunk簡介
* malloc將整個記憶體空間分成連續,大小不一的chunk.對於heap內的管理程序而言,chunk是最小的操作單位
* 分爲allocated chunk,free chunk,top chunk 和 last remainder
* brk,sbrk,mmap都是system call,會產生系統調用的開銷,又容易產生碎片
* 爲了解決以上問題,malloc使用一個memory pool的概念
* 先申請一大塊記憶體(成爲主分配區arena),將記憶體分割爲不同大小的記憶體塊,當user申請記憶體時直接從memory pool拿相近的記憶體
* malloc使用chunk來管理記憶體塊,可以說malloc就是由不同大小的chunk link list組成的
* chunk指標指向chunk開始的地方,mem指標指向返回給用戶的記憶體指標
1.最低位P=0表示前一個chunk空閒,prev_size儲存前一個chunk的大小,P=1反之,prev_size會是previous chunk的user data.(malloc的第一塊一定將P設爲1)
2.M表示當前的chunk是從哪一個記憶體得到的虛擬位址,1表示從mmap得到,0表示從heap得到
3.A=0表示該chunk屬於主分配區(arena),1則反之
* **allocated chunk**的用戶數據區存放用戶的資料
* **free chunk**是過戶資料區則存放4個指標
當chunk空閒,在用戶的數據區會有4個指標,分別指向前後空閒的chunk和其大小(fd,bk,fd_nextsize,bk_nextsize),malloc通過fd和bk形成雙向link list.在large bin中的空閒的chunk會通過fd_nextsize和bk_nextsize加快記憶體搜索
* 所以在 free chunk size時,其實際大小比整體大小小了16bytes(一個pointer = 4bytes)
* **top chunk** malloc在分配記憶體時會從比較小的chunk開始找,直到找到適合的.而top chunk就是"最後的防線",如果top chunk任然不符合用戶申請記憶體的需求,malloc就會調用sbrk或mapp分配記憶體
* **last remainder**是存放在unsorted bin中的亂序排放的chunk,malloc在尋找合適的chunk時若不能從last remainder中找到就必須到large bin裡找.

#### bin簡介
* malloc將記憶體分成了大小不同的chunk,並且通過bins來組織他們:
* malloc將大小相似的chunk利用雙向link list串起來
* malloc一共維護了126個bin,並使用一個array來儲存這些bin,第一個爲unsorted bin,接下來的前64個爲small bins,同一個small bin中的chunk大小相同,相鄰bin相差8bytes
* small後面跟着的是large bin，large bin的每個bin包含一個給定範圍內的chunk，每個large bin之間相差64bytes
>> TODO: 下圖改用 GraphViz 繪製 [name=jserv]
* 除了unsorted，small，large bin還有fast bin
* fast bin：
* 當程式在執行的時候時常需要申請or釋放較小的chunk，這些chunk就會放到 fast-bin的max_fast中（不改變P值，也不能合併）。每一次malloc在申請的時候都會先從max_fast中尋找相對應的記憶體空間，沒有再從unsorted bin之中尋找，如果unsorted bin也不能滿足malloc的要求，malloc就會把unsorted bin的chunk放入chunk（fast bin類似cache）
* 有fast bin就會有fast chunk,fast chunk的大小爲16-80bytes
* fast bin的結構爲單向link list,結構中只使用fd pointer因爲fast bin使用後入先出的演算法
* 每個fast bin相差8個bytes(16 -> 80)
* 不會對free chunk 進行合並,類似cache的使用
* 當malloc申請一個size的記憶體,實際大小爲該記憶體+16bytes.
* 在初始化的時候fast bin是空的,所以即使請求在fast chunk大小內的記憶體也會直接跑到small bin去處理
* fast bin的使用:
* 當第一次調用malloc(fast bin大小),系統執行_int_malloc發現fast bin爲0,small bin也是0,這個時候就調用malloc_consolidate 對 malloc_state(arena header)初始化:
* 判斷malloc_state是否真的爲空
* malloc_state的初始化由malloc_init_state(av)完成,它先對fast bin之外所有的bin初始化,再對fast bin初始化(因爲兩個的struct不同,fast bin是single link list,其他的是double)
* 再次執行就可以使用fast bin了
* 在得到地一個來自fast bin的chunk後,將chunk從fast bin中delete,並將地址返回給用戶
* free就是把chunk size傳入以獲得chunk的大小,在把它添加所對應的bin中
* 操作如下圖

* unsorted bin(free chunk):
* 當釋放較大或較小的記憶體,系統沒有把他們添加到bin中,就添加到unsorted bin
* 這麼做是因爲把unsorted bin當成第二層的cache來使用,加快malloc的速度
> unsorted bin中的chunk是怎麼排列的?[name=lim wen sheng]
>
> 在 `lsploits/glibc/malloc/malloc.c`中的`Unsorted chunks`註解，the unsorted_chunks list acts as a queue, with chunks being placed on it in free and malloc_consolidate, and taken off to be either used or placed in bins in malloc.
> 所以會直接排序成queue的方式等待再次被使用，或者排入bin內嗎? [name=陳致佑]
> 準確來說是以linked list的方式串在一起哦,unsorted bin中chunk的排列方式的是先來先排的.只有等到unsorted bin只有在把fast bin中的chunk和它合並了之後還是找不到適合大小的chunk才會被排入large bin中[name=lim wen sheng]

* small bin:
* 大小爲8 ~ 512bytes
* 先入先出(add在前,delete在後)
* 在所有small bin之中的chunk大小一樣,每個bin相差8bytes
* 當malloc時,fast bin和small bin都還沒有完成初始化,就會交給unsorted bin處理,再不可以就loop所有的bin,再不可以就交給top 出chunk處理,再不可以就使用heap對top chunk進行擴充
* 再次調用small bin時,如果不爲空則從small bin取得 small chunk
* **free**:釋放small chunk時會先判斷相鄰的chunk是否爲空,是就合並並丟到unsorted chunk
* large bin:
* 512bytes或更大,有63個
* 沒一個large bin中的大小可以不一樣
* large chunk可以添加/刪除在large bin的任何位置
* 前32個間隔64,之後16個間隔512,之後8個間隔4096,之後4個32768,之後2個262144,最後一個全部剩下的都給他
* 同一個large bin中的所有chunk的大小不一定相同,所以爲了加快搜索,chunk由大至小排列(大在前,小在後)
* malloc操作:初始化之前與small相似
* 在收到請求之後,若爲large bin範圍,尋找對應的bin並查看第一個chunk(最大)的size夠不夠,如果大於就往下找,小於就向後移動一個bin.如果找到最小的chunk還是比用戶請求的大,則分割出剛剛好大小的chunk出來給用戶,剩下的丟到unsorted bin.
* 因爲large bin的個數很多,一直找下去會引發很多的page fault,所以glibc malloc設計了binmap(能夠知道bin是否爲空的bin-by-bin algorithm)
* 當large bin都找完了還是找不到足夠的chunk就轉由top chunk處理
* 在特定的時候(free的時候如果相鄰爲空)malloc會把空閒的相鄰的bin進行合併並放在unsorted bin，然後把合併好的chunk放到對應的bin
* 除了以上幾種，malloc還有另外三種應付不同情況的記憶體區
* fast bin 和 bin 都不能滿足malloc，malloc會在top chunk中分配一塊記憶體給user（稱為mapped chunk）。
* top chunk是通過mapp()在map area中取得一塊較大的記憶體並擁有sup-heap的結構
>sup-heap是什麽?[name=lim wen sheng]

* 當fast-bin，bin，top chunk都不能滿足的時候，malloc直接運用mapp()在map area中直接映射一塊對應大小（剛剛好嗎？？？）的記憶體。這種記憶體空間在free的時候會直接被釋放並還給系統。
* last remainder：是當要分配small chunk卻找不到的時候，如果last rmainder中有足夠大小的chunk，last remainder會分割出足夠大小的chunk給malloc，剩下的變成新的last remainder

#### malloc實際操作
1.一開始brk和start_brk一樣，heap size為0
2.當用戶第一次申請malloc的大小小於mmap(1024kb)分配的大小，malloc會判斷malloc_state爲空,並調用malloc_init_state進行初始化(fast bin以外的 -> fast bin)
3.並申請(chunk size + 128kb)align 4kb大小的空間作為初始的heap
4.第二次malloc申請的時候，如果還是小於記憶體分配的大小，malloc會check fast-bin。還是不可以就找small bin，再不可以就把fast bin合併到unsorted bin，再不可以就把unsorted bin 合併到large bin.(large bin的查找會依照smalest-first,best-fit的規則)
5.還是不可以就是用top chunk，再不可以就使用mapp chunk，再不可以就使用mapp()，否則增加heap和top chunk去滿足

---

## Supermalloc
#### Abstract
* It allocates 2 MiB chunks which contain objects all the same size.
* It uses a simple array to transform chunk numbers to chunk metadata
* most of the size classes are a prime number of cache lines(block data)
* nonaligned huge accesses are randomly aligned within a page.
* SuperMalloc employs a 10-object per-thread cache

#### How Supermalloc work
* 只支持64位元的作業系統
* 每一個chunk都固定為 2 MiB的大小，且不會對chunk進行分割
* 在分配small object的時候把很多個small object都放到一個chunk之中
* 對於large object（可能會大過2MiB），會分配在不同的chunk之中
* 把請求記憶體的類別分為small，medium，large和huge
* 用一個512MiB的array去記錄bins
* 每一個array的元素是4bytes，在64位元中user space的記憶體空間有2^48^，之中chunk的entries為2^27^(2^27^ = 134217728, 134217728 / 1024 = (512/4 = 128) * 1024bytes),為131072bytes大小的array
* 一直秉持着64bit作業系統空間超級多又便宜可以亂用沒關系的規則

#### Small Object
* Small objects是 8 bytes 到 224 bytes大小的objects
* SuperMalloc 在分配small chunk的時候利用 fullest-fit algorithm.
* 在分配的時候會尋找還沒有滿而且足夠大的chunk
* SuperMalloc只會取消分頁和chunk的提取,不會取消映射或是改變chunk的size
* SuperMalloc在用戶申請更改分配空間時會植一塊更大的記憶體
* SuperMalloc對每一個object都使用heap-like的資料結構
* SuperMalloc simply maintains an array of length 65 containing linked lists of pages, along with a bitmap to indicate which sizes have nonempty linked lists.
* for page that containing 64bytes,it only have 65 different states(0 object free,1,2....)
* 以下為較早版本的bin的分配的程式碼:

int size_2_bin(size_ts)
{
    if (s <= 8) return 0;
    if (s <= 320) {
        // Number of leading zeros in s.
        int z = clz(s);
        // Round up to the relevant
        // power of 2.
        size_t r = s + (1ul<<(61-z)) -1;
        int y = clz(r);
        // y indicates which power of two.
        // r shifted and masked indicates
        //  what the low-order bits are.
        return 4 *(60-y)+ ((r>>(61-y))&3);
    }
    if (s <= 448) return 22;
    if (s <= 512) return 23;
    ...
    if (size <= 1044480) return 45;
    // the last bin save all of the less of meomory
    return 45 + ceil(size-1044480, 4096);
}

* 之後的SuperMalloc的bin改變爲只有2^N^ : 8,16,32...等

#### Medium Object
* Medium objects are all sized be a multiple of 64 (the cache line size).
* Medium objects的大小都會等於64bytes的倍數(2^N^)(相當於整數倍cache line的大小)和質數的倍數
* 最小的是 256 bytes, 最大的是14272 bytes
* 64bytes的倍數只用在當用戶申請的記憶體大小剛剛好跟它對齊,其他的都會使用質數的倍數
* 這樣可以降低cache的相關性(避免發生cache conflicts)
* Problem:
1. 當需要分配的空間大小是449bytes(7*64+1)和833bytes(13*64+1),在兩個質數直接按就有浪費很多的空間
* SuperMalloc使用多兩個bin(9和15)去解決這個問題
2. 當用戶請求的空間不是頁的整數倍,就會在也額後面留下很大的空間(例如:4個832bytes的chunk與4096bytes的page相差了768bytes,就浪費了768bytes的空間)
* SuperMalloc使用folio的更大的頁去解決以上問題
* folio在分配chunk的時候會根據cache-line數量,例如要分配832(13個cache-line),就利用fullest的演算法去找13個page分別分配64bytes的及一體,讓沒一個page都可以對齊

#### Large Object
* Large objects的大小從16KiB開始,最大可以到1MiB
* 每一個在SuperMalloc下定義的Large objects都是頁大小的整數倍(4096 bytes)
* 爲了更好的預防cache conflict,SuperMalloc在處理large object的時候都會增加一個隨機數量的cache line(0 -> 63).
* 例如:當用戶請求20000bytes的記憶體空間,如果SuperMalloc隨機到31這個數字,那麼它就會分配20000 + 31 x 64 = 21983bytes的空間給用戶
* 這個方法只會在當用戶沒有申請對齊大小的記憶體
* 這樣做的目的在於先把接下來連續的記憶體放到cache中,如果用戶在之後用到這塊記憶體就能夠非常快速的從cache拿到

#### Huge Object
* Huge objects 最小的size是1MiB(半個chunk)可以到很大
* 使用mmap()函數去分配記憶體空間給用戶但是不會使用unmap()取消這個映射空間
* 使用mmap()分配的時候會跟2^N^MiB對齊(2,4,8,16...)
* free()的時候不會把空間返回,會把chunk添加都SuperMalloc的link list後面(SuperMalloc通過link list去和chunk table連接起來所以不用去取消chunk/memory的提取)
* 在使用mmap時並不會真正的直接分配一塊記憶體給用戶(mmap映射的是邏輯地址),而會再調用madvise()讓kernel去把"huge page"分配給用戶
* huge page是在linux kernel最近才出現的2MiB的頁
* 當需要分配5MiB的記憶體,對因爲對齊而分配8MiB的空間給用戶.

---
## 使用SuperMalloc在之前的作業上比較成果

### phonebook-concurrent


### mergesort-concurrent

Mergesort的部分因爲512執行緒的落差太大，會導致前面的數據看不到，所以就只畫到256（執行緒）

由這兩個實驗結果可以看到執行緒數量越多的時候，Supermalloc的執行時間跟malloc比起來快很多。但執行緒很少的時候，Supermalloc的執行時間比malloc慢了一點

---

## Daniel Micay 的 allocator 研究

[thestinger/allocator](https://github.com/thestinger/allocator)

### Low-level memory management
* chunk 的實現是每塊記憶體區塊以 4Mib對齊
* 在 usersapce 管理chunk，降低 system call成本、記憶體破碎和同步問體，而不是透過 unmapping chunks
* 使用 address-ordered best-fit 管理free chunks，降低每種情況的時間複雜度並大幅地減少碎片問題
* 使用 node 代表 extent，一個樹用(size, address)進行分配，另一個樹用 address 進行合併。
* 一開始會先申請一大塊記憶體放着保留放在 userspace
* 在 userspace 使用 Red-Black Tree 來管理 chunk
* Red-Black Tree 優點可以在O(log n)時間內做尋找，插入和刪除，n為樹中元素的數目
* managing mappings (mmap, mprotect, munmap) in userspace，可以避免page fault 而且成本更便宜
* 使用自動對齊chunk的方法可以在 allocations 辨別更小或者更大的 chunk size，比從透過address來檢查chunk size更快速的O(1)找到metadata ，huge allocation 則需要O(log n)

### Decommit / purging
* 使用 lightweight purging 來解決overcommit enabled/disabled 問題
* Purging 目前實現在 chunk level and does not perform the work lazily
> 不表現在work lazily 是什麼意思?[name=陳致佑]
>> 原文是 "perform the work" "lazily"，也就是說，考慮到效能，不會立刻去處理記憶體配置的要求，而是實際需要時才作 [name=jserv]
>> 了解[name=陳致佑]
* The intention is to track dirty prefixes in free spans of memory, with lazy purging in FIFO order. 同樣方法可用在 small, large and chunk allocation.

* The address-ordered best-fit algorithm 適合應用在dirty prefixes，因為 spans with lower addresses are preferred.

* 盡量避免使用 first-fit 可能會增加更多的破碎

* 新的替代方案可以分割 clean 和 dirty 的記憶體，但可能會造成新的破碎方式，預期整體設計會更快，且不需要花費切割記憶體的成本。

* Tracking the dirty spans不用切割記憶體就能準確的完成，但是會更複雜的管理 metadata
### Rest of the implementation

* 主要分類：
* huge: chunk 總是對齊
* small/large: chunk 不會對齊
* arenas：
* 將chunk 分配到每個核心區
* pick a preferred arena with sched_getcpu and update it on contention
* 透過標頭flag區分small/large chunk
* per-arena cache 存放最近 free的chunk
* large allocations：
* allocation headers 用來釋放和合併
* 找到下一個 span 透過`addr + size` for forward coalescing
* 維持先前的 span 指標，for backward coalescing
* spans 必須是 header 的倍數，如 4x pointer-size
* headers act as spacers and prevent false sharing with 64-bit pointers and 64 byte cachelines
> header 當作間格來隔避免false sharing，不太懂false sharing是什麼?[name=陳致佑]
>> false sharing 可以參考 [並行與多執行緒程式設計：Atomics 操作](https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fconcurrency-atomics) [name=Ewing]

* intrusive tree keyed by (size, addr) for address-ordered best-fit
* the span headers 為 tree nodes
* 當free span 覆蓋過可使用的區域，chunk 就會被釋放
* small allocations：
* per-arena slab LIFO free lists:
* empty slabs
* partially filled slabs: doubly-linked list per size class
* empty slabs are returned to the empty slab list

### code 分析
* extent.c/extent.h

static int extent_ad_comp(struct extent_node *a, struct extent_node *b)
比較 address return 1,0,-1 

static int extent_szad_comp(struct extent_node *a, struct extent_node *b)
比較 size  a>b return 1，其他狀況return extent_ad_comp(a, b);

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)
rb_tree 在 rb.h 內，rb_proto()會去呼叫 rb_gen()並使用'##'連接和定義各個 prototypes

* bump.c/bump.h
handle alignment properly in the bump allocator
用來正確地控制 每塊記憶體區塊以 4Mib對齊

* arena.h
定義了 struct large/slot/slab/chunk/arena/thread_cache
* slot slab 用來處理small allocations
* arena 內有 slab,large,huge chunk (start,end)

* purge.c/purge.h

long int purge_ratio = -1;
COLD void purge_init(void) {
    char *ratio = secure_getenv("MALLOC_PURGE_RATIO");
    if (ratio) {
        purge_ratio = strtol(ratio, NULL, 10);
    }
}

>應用在alloc.c中，if (purge_ratio >= 0) {
memory_decommit(arena->free_chunk, CHUNK_SIZE);
}
一開始init 初始化 purge_ratio 不就 >0，之後進行也沒有更改過參數，不就都會成立? 還是 `secure_getenv("MALLOC_PURGE_RATIO")`會不同?
>> 請用 `export MALLOC_PURGE_RATIO=` 後面接不同的數值，再來執行測試程式，觀察效能表現 [name=jserv]

* chunk.c/chunk.h

---

## Question:

**ptmalloc2:**

* 第一次調用malloc時heap是否爲0?
* 是,但是第一次在使用malloc時並不是在用戶自己調用的malloc,
* 第一次malloc是不是會有freelist data structures的初始化，還是說有free了才有freelist data structures的出現？
* 在第一次malloc時如果malloc_state爲空,就會對freelist datastructure初始化,並直接把所有的chunk都分割排列好
* 如果一開始就有freelist data structures，那爲什麼要有freelist data structures？每次malloc時都需要進到freelist data structures裏尋找適合的地方不會很浪費時間嗎？
* 因爲在初始化freelist datastructures的時候是先從heap調用132kb的記憶體空間在初始化,後續分配的所有chunk的空間都是連續的,所以在每一次malloc時的執行時間就會比直接調用mmap快得多
* 在撰寫程式時常會用到realloc去手動分配記憶體空間(malloc的時候malloc很大的一塊),進行chunk的分配對realloc的速度會提升很多
* chunk在malloc_state初始化之後是不是全部都會被分配到bin?
* 是,初始化後malloc就會把分配到的132kb記憶體空間都分割成很多的chunk
* 如果被都會分到bin中,那麼之後調用malloc是不是就不用涉及到system call(如果有符合大小的chunk)
* 每一次malloc都是一個system call,差別只是在於對連續記憶體的存取效率
> malloc呼叫後，glibc會根據block的大小決定是透過brk()/sbrk()或mmap()去跟kernel要記憶體，所以會有system call的成本。但是這邊malloc實作是先劃出一塊132kb的記憶體空間切割成chunk，等待後來需要的大小從這段空間找出適合的chunk配對，這樣子之後呼叫還算system call嗎? [name=陳致佑]
> 使用chunk的方式還是會有system call的成本,他們之間速度的差異主要是因爲利用chunk的方式先把一大塊記憶體割出來分配之後malloc所申請的所有chunk記憶體都是連續的,而且釋放之後再次使用會達到cache hit的效果[name=Lim Wen Sheng]

* 什麼情況下會用mmap()、sbrk()，來分配memory給heap
* 分配較小記憶體或常用時使用sbrk
* 分配較大或只用數次的記憶體會使用mmap
* 從free list裏成功malloc後的block，會不會保留next ptr跟prev ptr？方便日後realloc可以使用到
* malloc_chunck代表chunck_header，每個allocated chunk,free chunck或top chunck都會有屬於自己的header，那bin底下內容都是在free chunk內嗎?
>可以這麼說,free chunk都會串接在bin底下方便malloc分配[name=Lim Wen Sheng]

---

## 相關資料與程式碼理解
* [Memory allocator by Daniel Micay](https://github.com/thestinger/allocator)
* 之前學生的研究 [Real-time Linux 研究: Memory Allocation](https://embedded2016.hackpad.com/Real-time-Linux-Memory-Allocation-kS5wHum1S54)
* [Benchmarks of the Lockless Memory Allocator](http://locklessinc.com/benchmarks_allocator.shtml)
* [memory 不錯參考的文章](http://reborn2266.blogspot.tw/search/label/memory)

### 針對不同allocater和不同大小object的測試圖標
* 16bytes
* 256bytes
* 512bytes
* 1kb
* 4kb
* 16kb
* 512kb
* 1mb
* 4mb
>> 在 1 MB 和 4 MB 的條件下，為何沒見到 "Allocator" 呢？ [name=jserv]

---

## 設計有效實驗
首先先不考慮 fragmentation 的情況，先做個基本的 multi threads malloc benchmark。
想法：benchmark 的設計大致上會分成兩個部分：
* 對不同大小的 size（small、large、huge) 做的benchmark
* 將所有不同的 size 整合在一起，對不同 malloc 的總體效能而做的benchmark

參考：https://github.com/jffrosen/fragbench
更改後自己的版本：https://github.com/TempoJiJi/malloc_benchmark
>> 這裡對他的 fragmentation實作有點疑問，fragmentation跟testalloc應該是不同的process，那為什麼fragmentation所造成的碎片會影響到testalloc？兩個不同的process應該是不同的heap才對？是因為shell script的關係所以其實它們兩個的資源跟shell script一起共用嗎？[name=TempoJiJi]

### 不同 size 之間的 benchmark

==想法==：對各個不同的 size 個別進行 benchmark，且會重復 allocate 加重成本，最後再各個執行緒所花的時間加總在一起。

這裡我將它的版本改成 malloc 指定的 size，而不是一個 page 的大小。考慮到多執行緒下 malloc size 太大跟太多次，記憶體會爆掉，所以同一個 size 同一個執行緒下只做了 20 次 malloc:

#define N_ALLOCS 20
for (int i = 0; i < N_ALLOCS; i++) {
    void *vptr = NULL;
    char *a = NULL;

    t.tick();
    vptr = malloc(SIZE);
    memset(vptr, rand(), SIZE); 
    t.tock();

    assert(!(reinterpret_cast<unsigned long long>(a) & 0xFFFFF));
			
    #if defined(__GNUC__)
        __builtin___clear_cache((void *) vptr, (void *) vptr + (SIZE));
    #endif
			
    times[id][i] = t.get_time();
    ptrs.push_back(a);
}

然後建立自動測試機制，size 的大小範圍從 $2^2$ 到 $2^{22}$，get_output 將所有資料整合在一起：

bench: $(EXEC) get_output
	for i in 1 2 4 8 16 32 64; do \
	    for j in `seq 2 1 22`; do \
		./sizebenchmark $$i $$j; \
	    done \
	done
	./get_output

---

### 整合所有 size 的 benchmark
==想法==： 不同的 size 之間不分開進行，也不重復 allocate，直接從 $2^2$ 到 $2^{22}$ bytes 進行 allocate。

// MAX_POW_SIZE = 22
for (int i = 2; i <= MAX_POW_SIZE; i++) {
    void *vptr = NULL;
    char *a = NULL;
    SIZE = pow(2,i);

    t.tick();
    vptr = malloc(SIZE);
    memset(vptr, rand(), SIZE); 
    t.tock();
    ...
    ...

測試結果發現在執行緒數量很高的時候，時間分布會非常不均勻。以下爲 "Allocator" 執行1000次的時間分布，可以看到時間跳動的區間在 `0.3 - 0.9` ：


這樣的結果會造成 benchmark 結果不精確，因此爲了解決這個部分的問題，決定模仿作業 `phonebook` 的做法，就是重復執行100次，然後計算出平均值，這樣得到的結果就會比較精確。
以下爲每100次取平均值，而得出的時間結果，可以看到時間跳動的區間在 `0.53 - 0.59` ，結果比之前的精確很多！

---

### 以下為結果圖：

實測不同 ptmalloc/supermalloc/allocator 的malloc 從 $2^2$ 到 $2^{22}$ bytes ，比較不同 malloc 效能

> supermalloc 在 thread 小於32 時，效能會比 ptmalloc 較差，而allocator 整體上效能都是比較好的。
> >目前是測試不同 malloc 的效能，所以不同thread 也是各自 malloc/free 沒有因為 thread 增加，加快分配記憶體效率。[name=陳致佑]

>> 中英文字間請用空白隔開
>> [name=課程助教][color=red]
>> 好的會多注意 謝謝助教[name=陳致佑]

---

### 考慮 fragmentation 的情況

###### tags: `TempoJiJi` `tundergod` `Supermalloc` `sysprog21`