# 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) ```c 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` 用來關閉指定區域的記憶體映射 ```c int munmap(void *addr, size_t length); ``` ### [madvise](https://man7.org/linux/man-pages/man2/madvise.2.html) ```c 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)
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up