# mimalloc
contributed by < `oucs638` >

## 討論紀錄

- 使用 free list 目的
- 減少 fragmentation 以獲得更好的 spatial locality
- best-fit
- 優先 alloc 最小且符合 requirement 的記憶體空間
- 可能會剩下太小、無法使用的 fragmentation
- worst-fit
- 優先 alloc 最大的記憶體空間
- 降低產生過小的記憶體空間
- 如果後續有需要更大記憶體空間的 requirements，會無法 alloc
- memory 的配置、紀錄
- mmap
- sbrk
- mimalloc 論文
- lock free
- mimalloc-bench
- 效能
- 正確性
- isolloc 注重 security，而 mimalloc 注重concurrency performance
- Chrome's PartitionAlloc
- lab0-c
- isoalloc
- Canaries are unique and are composed of a 64 bit secret value xor'd by the address of the chunk itself.
- mmap 迎射
- CSAPP Chapter 9
- man page
- mmap, madvise
- PER_POPULATE_PAGES
- MAP_POPULATE
- Hugepagesize
- page size 預設 4 kb x86_64 => 2 MB huge page
- 兩個不同方式管理
- release vs. debug build
- cmake

## TODO

- [x] 研讀 [CSAPP Chapter 9](https://hackmd.io/@sysprog/CSAPP-ch9)
- [x] 研讀 [Mimalloc: Free List Sharding in Action](https://www.microsoft.com/en-us/research/uploads/prod/2019/06/mimalloc-tr-v1.pdf)

---

## 研讀 [CSAPP Chapter 9](https://hackmd.io/@sysprog/CSAPP-ch9)

### [mmap](https://man7.org/linux/man-pages/man2/mmap.2.html)

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

- 映射檔案內容到 process 的虛擬位址空間
- 如 `addr` 值為 `NULL`，系統會自動在 process 的位址空間選定適合的位址映射；如有給定 `addr` 的值，系統會在給定的位址之後選定合適的位址進行映射；建立映射後，會回傳實際的映射位址
- 參數 `length` 表示要映射多長的檔案內容
- 參數 `prot` 設定映射區域的存取權限
- `PROT_EXEC` 映射區域可被執行
- `PROT_READ` 映射區域可被讀取
- `PROT_WRITE` 映射區域可被寫入
- `PROT_NONE` 映射區域不能存取
- 參數 `flags` 設定映射區域的特性
- `MAP_SHARED` 和其他映射相同檔案的 process 共享，對映射的更新其他 process 可見，且更新會寫入原檔案
- `MAP_PRIVATE` 不與其他映射相同檔案的 process 共享，對映射的更新其他 process 不可見；更新會產生一個 copy-on-write 的映射，且不會寫入原檔案
- `MAP_POPULATE` 預先為映射產生頁表，對於檔案的映射相當於預讀的作用，會減少訪問映射區域時因 page faults 產生的 blocking
- 參數 `fd` 是要映射的檔案的檔案描述符
- 當 flags 設定 `MAP_ANONYMOUS` 使用匿名映射時，`fd` 設為 `-1`
- 參數 `offset` 表示檔案映射起始處的偏移量
- 必須是 page 大小的整數倍
- `munmap` 用來關閉指定區域的記憶體映射

int munmap(void *addr, size_t length);

### [madvise](https://man7.org/linux/man-pages/man2/madvise.2.html)

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

- 建議或指示系統核心指定的位址區域應遵循的使用模式
- 參數 `addr` 指定區域的起始位址
- 參數 `length` 指定區域的長度範圍
- 參數 `advice` 表示指定區域應遵循的使用模式
- `MADV_DONTFORK` 表示在執行完 `fork` 後，不允許 child process 使用指定區域的 page；這樣做的目的是避免 parent process 在執行完 `fork` 後，嘗試寫入時因為 copt-on-write 機制而更動到 page 的物理位置
- `MADV_MERGEABLE` 表示指定區域內的 page 啟用 KSM (Kernel Samepage Merging)，kernel 會定期掃描 user memory 被標記可合併的區域，將相同內容的 page 合併為一個 writed-protected page，稍後要更新此頁面時會發生 copy-on-write 操作；KSM 只用於 private anonymous pages
- `MADV_HUGEPAGE` 表示指定區域內的 page 啟用 THP (Transparent Huge Pages)；目前 THP 只適用於 private anonymous pages；kernel 會定期掃描被標記為 huge page 候選的區域，然後替換成 huge pages；當區域自然對齊 huge page 大小時，kernel 也會直接 allocate huge pages

---

## 研讀 [Mimalloc: Free List Sharding in Action](https://www.microsoft.com/en-us/research/uploads/prod/2019/06/mimalloc-tr-v1.pdf)

- 每一個 mimalloc page 都有一個自己的 freelist，以確保 spatial locality，因為系統會優先 allocate 同一個 page 的空間，直到該 page 已滿
- 使用單獨的 thread-free lists 處理其他 thread 的釋放，以避免在 fast path 使用 atomic operation；這些 lists 會定期一次 atomically 移動到 local free list，有效的批次處理遠端釋放
- 每個 page 再使用第三個 local-free list 處理 thread-local 的釋放，當 allocation free list 為空，local-free list 成為新的 free list；這個設計確保在固定數量的 allocations 後，generic allocation path 會被執行；這樣的設計可以分攤成本比較高的 operations 的成本

- 為了增進 allocation 的 spatial licality，mimallaoc 使用 free list sharding，將 heap 分成數個 pages，且每個 page 分配有獨立的 free list
- 在 local allocation 使用變數 `used` 以判斷一個 page 中 object 的使用狀況；這樣的設計不需要使用 bump pointer，只要直接從 page local list 中 pop 空間；且這樣的設計在 fast path 上只需要一個條件判斷和一個 pop，但這樣的條件不好預測，增加了 free list 的隨機性，也對 security 有好處
- 對每一個 page 新增一個 shared local free list，從 regular free list 進行 allocate，並將已釋放的 objects 放到 local free list；這樣的設計確保在一定數量的 allocation 後，free list 會為空

- 在 mimalloc 的設計中，pages 屬於 thread-local heap，且 allocation 總是在 local heap 中進行；這樣的設計在 thread local allocation 時，不需要使用 locks
- 而對於 non-local free，則使用 atomic operation 將 freed object 放到 thread free list
- 使用 shared thread free list，也可以減少 threads 之間的競爭，因為不同 pages 的釋放不需用競爭資源；且沒有競爭的 atomic operations 比較有效率

- 要 allocate 一個 object，mimalloc 首先會取得一個指向 thread local heap 的 pointer (tlb)；對於小於 1KB 的 objects，heap 有一個 direct array 存指向第一個可使用的 page 的 pointer
- 一個 segment 的大小是 4MB；對於小於 8KB 的 object，一個 segment 會有 64 個 64KB 的 pages；對於 8KB ~ 512 KB 的 object，一個 segment 就是一個 page 的大小；對於超過 512KB 的 object，allocater 會另外 allocate 所需大小的 page；這樣的設計簡化了 data structure，也減少了程式碼的大小和複雜度

- 因為 mimalloc 的設計 segment 會對齊 4MB 大小的 boundary，可以藉由 mask pointer 的 lower bits，來找到包含該 pointer 的 segment
- 如果是其他 thread 要釋放，object 會被 atomically pushed 到 thread free list；如果是 local 的釋放，object 會被 pushed 到 local free list

- mimalloc 設計有一個 generic allocation routine `malloc_generic`，是保證一段時間就會被執行的 slow path；藉由這個設計 mimalloc 可以將 operation cost 分散到數個 allocations，因此可以做更多 expensive operations，也可視為 garbage collector

- 綜合上述的 mimalloc 設計對大多數 benchmark 都有不錯的表現，但對 SpecMark gcc benchmark 卻有 30% 的 slowdown，原因是 mimalloc 會產生過多的 full pages，且每次執行 generic allocation routine 時會全部拜訪過一次
- 對應的解決方法是將所有 full pages 蒐集到一個獨立的 full list，當 page 中有 freed object 再移回 regular page lists；雖然這個方法解決了 SpecMark gcc benchmark 的問題，但也顯著的增加了 multi-thread case 的複雜度
- 利用 thread free list 的 2 least significant bits 分成三個 state，對應不同的 non-local free 處理方式
1. NORMAL：將 non-local free push 到 local thread free list
2. DELAYED：當有 page 要被移動到 full list，設置成 DELAYED state，表示 non-local free 應該要被 push 到 owning heap delayed free list
3. DELAYING：進行前個狀態的 non-local free 處理時，暫時會設置成 DELAYING state，以確保如果 owning thread 終止， owning heap struct 可以保持 valid

---

## 被關注的 ISSUE

> 不急著立即作出程式碼貢獻，而是使用熟悉的 keyword 查找觀察其他使用者在意的問題，嘗試能否重現問題，再研究改進的方法

- [microsoft/mimalloc issue#53](https://github.com/microsoft/mimalloc/issues/53)

---

## 參考資料

- [microsoft/mimalloc](https://github.com/microsoft/mimalloc)
- [Brief History of Free List Sharding](https://hackmd.io/@hPMCWajOS-ORQdEEAQ04-w/HJbeisVNB)
- [IsoAlloc Performance
](https://github.com/struct/isoalloc/blob/master/PERFORMANCE.md)
- [2021 開發紀錄](https://hackmd.io/@hankluo6/mimalloc)
- [CSAPP Chapter 9](https://hackmd.io/@sysprog/CSAPP-ch9)
- [Mimalloc: Free List Sharding in Action](https://www.microsoft.com/en-us/research/uploads/prod/2019/06/mimalloc-tr-v1.pdf)