# mimalloc 共筆
contributed by ` Julian Fang ` ` afcidk `
[avoid divisions](https://hackmd.io/@hPMCWajOS-ORQdEEAQ04-w/BkssztrgH)
[Brief History of free list sharding](https://hackmd.io/@hPMCWajOS-ORQdEEAQ04-w/HJbeisVNB)
based on ` microsoft ` [mimalloc](https://github.com/microsoft/mimalloc)
## 檢查事項
1. 理解 `madvise` 用法，和 `mimalloc` 如何使用
2. 如何儘量避免 atomics 卻能正確地實作 malloc/free
3. 理解 per-thread block pools, free lists 等意義
4. 量化分析數據: 重現實驗 (`mimalloc-bench` 程式碼似乎有欠缺，要再等等)
5. Watch `mimalloc` 的 GitHub 頁面，從開發者的討論中學習
6. `mimalloc` 的 Worst-Case Allocation Time (wcat) 如何確保？又如何透過 `z3` 定理證明器證明呢?
## ` mimalloc ` 論文回顧(1)
[paper itself](https://www.microsoft.com/en-us/research/uploads/prod/2019/06/mimalloc-tr-v1.pdf)
### The Allocation Free List
#### spatial locality issue
> To improve the spatial locality of allocation, mimalloc use free list sharding where the heap is divided into pages with a free list per page.
* 筆者提到一般的 function style programming 多使用 ` single free list ` 會導致很糟糕的 spatial locality 。
* 因此在這邊使用 ` free list sharding ` 這個方法來實做。將整個 heap 分成一個一個 page ，每個 page 中都有一個小的 free list 。
* 這個問題之所以在 allocator 探討是因為 static allocation 分配到的位置是在 stack 上，而且是連續的。他想要改善 dynamic allocation 的 spatial locality，減少讀取 structure 的資料時的 cache miss。
### No Bump Pointer
#### what is Bump-pointer allocation
[refernece](https://the.gregor.institute/t/5n/842/slides/3.pdf)
To wit, ` sequential allocation `!
按照順序一個一個堆到最後面。
advantages:
* easy and fast
* No wasted space during ` allocation `
* only requires 2 pointers per pool, ` unallocated ` and ` end `
disadvantages:
* only makes sense for big free regions
#### No Bump poiter allocation
這邊使用的方法，為在每個分割好的 page 中找尋下一個可以使用的 block。
如果沒有下一個可用的 block 則重新分配一個 page。
### The Local Free List
purpose:
* To bound the ` worst-case allocation ` and ` free time `
> When free a lagre data structures, the number of recursive free calls need to limited.
How to do?
* use a simple limit counter
* push the remaining pointers on a ` deferred decrement list `
So ... when to free again from the ` deferred decrement list `?
* cooperate with allocator!
* Since the best time to do this is when the allocator is finding more space.
* Calls a user defined ` deferred_free `
* In the implementation, ` deferred_free ` is called when ` free_list ` is empty.
purpose 2:
* To guarentee that the generic routine is called regularly.
> Why do we need to generic routine to be called regularly? To establish temporal cadence (like heartbeat)
How to do?
* Shard the free list (free -> free | local_free )
* We allocate from free list, and free to local_free list, so it is guaranteed that free list will become empty after a fixed number of operations.
### The Thread Free List
purpose:
* Avoid lock for thread-local free
How to do?
* Atomic push freed object to thread free list
* Wait for generic routine to collect thread free list (and local free list as well) to free list
## Madvise
` madvise ` 讓我們給 kernel 一段記憶體空間分配上的建議。
Function prototype
`int madvise(void *addr, size_t length, int advice);`
addr 和 length 可以指定一個記憶體區段。advice 有提供[很多選項](http://man7.org/linux/man-pages/man2/madvise.2.html)來使用，這邊解釋一下 mimalloc 使用到的 advice 就好 (`MADV_FREE`)。
### MADV_FREE
`MADV_FREE` 在 Linux 4.5 之後被提出，意思是告訴 kernel 這段區間已經不需要被使用到了，可以釋放，但是 free 的動作會延遲到等到出現 memory pressure（空間不夠用）時再釋放就好。
設定 `MAD_FREE` 後，kernel 在遇到 memory pressure 時隨時可以釋放空間，但是一旦在釋放前又對記憶體區段寫入資料，釋放的動作就會被取消掉。
`MAD_FREE` 只能作用在 private anonymous page。
*在 Linux v4.12 以前，在 swapless system 中使用 `MADV_FREE` 釋放 page 會被直接釋放掉而不會延遲到 memory pressure 再釋放*
### MADV_DONTNEED
告訴 kernel 這段記憶體區間未來不會使用到。在使用 `MADV_DONTNEED` 之後，我們還是可以存取到該區間的 page，但是拿到的內容可能是
* mmap 的檔案內容 (對於 shared file mappings, shared anonymous mappings, shmem-based memory segments)
* zero-fill-on-demand pages (對於 private anonymous page)
*`MADV_DONTNEED` 可能不會馬上釋放空間，kernel 會決定一個**合適的**時間來釋放*
`madvise` 實際上被用到的地方是當 `mi_options_cache_reset` 或是 `mi_options_page_reset` 時，需要告訴 kernel 這段記憶體區間應該被釋放掉，但是之後可能還會用到，所以不需要立刻釋放，在 `_mi_os_reset` 被使用到，和 `_mi_os_free` 直接釋放略為不同。
## z3 Prover
[z3-guide](https://rise4fun.com/z3/tutorial)
[z3-github](https://github.com/Z3Prover/z3)
input format:
```
(declare-const a Int)
(declare-fun f (Int Bool) Int)
(assert (> a 10))
(assert (< (f a true) 100))
(check-sat)
```
* An extension of [SMT-LIB2.0](http://smtlib.cs.uiowa.edu/)
* 令用 assert 添加一些 ` 明確肯定 ` 的限制，到 ` stack ` 中。
* script 在 ` check-sat ` 後，回傳 ` sat ` 則表示滿足。
在 ` mimalloc-bench ` 中:
```
(declare-fun x () (_ BitVec 16))
(declare-fun y () (_ BitVec 16))
(declare-fun z () (_ BitVec 16))
(declare-fun GCD () (_ BitVec 16))
(assert (= (bvmul ((_ zero_extend 16) x) ((_ zero_extend 16) GCD)) (_ bv300 32)))
(assert (= (bvmul ((_ zero_extend 16) y) ((_ zero_extend 16) GCD)) (_ bv900 32)))
(assert (= (bvmul ((_ zero_extend 16) z) ((_ zero_extend 16) GCD)) (_ bv333 32)))
(maximize GCD)
(check-sat)
(get-model)
```
###### tags: `Cprogramming`
Sign in with Wallet
Connect another wallet