Try   HackMD

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

研讀 CSAPP Chapter 9

mmap

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

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

  • 每一個 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 查找觀察其他使用者在意的問題，嘗試能否重現問題，再研究改進的方法

參考資料

Last changed by 
 
Ralph Ou
0
466
Published on HackMD