sysprog
主講人: jserv / 課程討論區: 2016 年系統軟體課程
動態記憶體分配對Realtime System的影響
Glibc malloc()分配記憶體的方式
keywords: anonymous memory, break point, buddy memory allocation
參考文件: glibc 記憶體管理行為, Linux system programming Ch.8
Glibc有兩種分配記憶體方式,依照malloc()記憶體需求參數的大小決定使用哪種(default threshold = 128 KB,可調整)
brk()
或sbrk()
) => small allocationsmmap()
) => large allocations相較於file mapping而言,anonymous memory是指沒有對應檔案系統的記憶體區塊,如process的heap和stack
Heap的結束位址(頂端)稱作break point,可利用brk()
或sbrk()
系統呼叫,改變此位址來擴展或縮減heap的大小
brk()
調整heap size,造成internal fragmentation,影響效能membroker
System-wide Memory Management for Linux Embedded Systems
What is anonymous memory?
brk() is bad for other realtime threads
down_write(current->mm->**mmap_sem**)
會造成indefinite waiting
Glibc cannot shrink heap until highest allocated object is freed
常用的動態記憶體分配演算法
Sequential fit(First fit)
增進locality of reference
Segregated Free Lists
Buddy System
Indexed Fit
Bitmap Fit
TLSF(Two Level Segregated Fit)
Dynamic Storage Allocation A Survey and Critical Review 這篇論文整理了1961-1995關於記憶體分配的研究
結合Segregated Free Lists和Bitmap Fit
TLSF讓動態記憶體的分配和回收(allocation & deallocation)複雜度能達到Θ(1),同時也減少fragmentation的大小
特性
The first-level array divides free blocks in classes that are a power of two apart (16, 32, 64, 128, etc.); and the second-level sub-divides each first-level class linearly.
TLSF特性的比較
dlmalloc / ptmalloc2
immediate coalescing
在ptmalloc中,fast bin是不立即合併的,此可以增加tiny request的處理速度,省下分割block的時間。TLSF立即合併可減少fragmentation,但降低效能。
size streagy
在ptmalloc中,不同size使用不同的結構,fast與small bin在有block時速度快;但large包含segregated best fit與sorting,可能無法保證worst case。ptmalloc考慮到large request通常並不多,為在有限的free list下減少fragmentation而設計。TLSF則為了保證worst case並降低複雜度而使用相同策略。
block header
兩者的block基本上相同,皆包含size、free list pointer與previous block。但在TLSF中previous block使用pointer而非size,且不會被用於data。
free list
ptmalloc使用segregated free lists,並在512bytes以下的bin間距採最小間距,但在large block的覆蓋率相對較小(故需要sort & find)。TLSF為了能使large block保持O(1),故採用現今的雙層結構,增加bin的數量,並利用bitmap降低搜尋所需時間(clz),但在small block則較慢(雙層reference、需要分割)。
在An Improvement of TLSF Algorithm中,作者提議在small block也使用最小間距。
last remainder / unsorted
為ptmalloc為利用caching / 提高平均效率所設計,TLSF沒有類似功能。
ptmalloc不適合real time之處
在malloc中,若small /fast沒有exact fit,或large request,ptmalloc會進入consolidate fastbin -> unsorted bin loop -> find best fit的過程,其worst case是無法保證的。
scalloc
O(1) allocation
兩者皆有segregated的特性,並皆不包含seearch best fit的成份。TLSF miss時,往上找good fit,並使用clz等加速;scalloc在沒有hot與reusable時,進span-pool找新span,在span-pool miss時,需要loop span-pool。兩者的list大小皆不變,故皆為O(1),worst case則推估為TLSF較佳。
memory assumption
TLSF可以在沒有MMU、paging的環境下使用,在有的情況下則可memlock以減少latency。scalloc依賴demand paging運作,幾乎所有的fragmentation都由paging處理。
Understanding glibc malloc (ptmalloc2)
Memory request size
arena and thread
arena即為malloc從系統取得的連續記憶體區域,分為main arena與thread arena兩種。
每個thread在呼叫malloc()時會分配到一個arena,在開始時thread與arena是一對一的(per-thread arena),但arena的總數有限制,超過時threads會開始共用arena:
此設計是為了減少多threads記憶體浪費,但也因此glibc malloc不是lockless allocator,對於有許多threads的server端程式來說,很有可能影響效能
Heap data structures
Main arena vs Thread arena :
multiple heap Thread arena :
Chunks
Allocated chunk :
_Free Chunk _:
prev_size : 因兩個free chunk會合併,只會出現在fast bin的情況下
fast bin的chunk在free時不會做合併,只有在malloc步驟中的consolidate fastbin(fast /small bin miss)才會合併
下一個chunk的PREV_INUSE flag平時是不set的
fd(Forward pointer) : 指向在同一個bin中的下一個chunk
bk(Backward pointer) : 指向在同一個bin中的上一個chunk
Bins
bins是紀錄free chunks的資料結構(freelist),依據其大小和特性分成4種 :
(以下的數值為32bit系統,64bit *2)
_Fast Bin _:
_Unsorted Bin _:
_Small Bin _:
_Large Bin _:
Top chunk
在arena邊界的chunk,若所有bin皆無法allocate則由這裡取得,若仍不夠則用brk / mmap延展
Last Remainder Chunk
最近一次分割的large chunk,被用來滿足small request所剩下的部分
malloc流程
free流程
檢查 : 檢查pointer位址、alignment、flag等等,以確認是可free的memory
合併(consolidate)
ref : allocation過程
簡單測試 : malloc(40 * sizeof(int));
malloc_stats()
Arena 0:
system bytes = 135168
in use bytes = 176
Total (incl. mmap):
system bytes = 135168
in use bytes = 176
max mmap regions = 0
max mmap bytes = 0
mallinfo() example
Total non-mmapped bytes (arena): 135168
Bytes in mapped regions (hblkhd): 0
Max. total allocated space (usmblks): 0
Free bytes held in fastbins (fsmblks): 0
Total allocated space (uordblks): 176
Total free space (fordblks): 134992
Topmost releasable block (keepcost): 134992
malloc_info(int options, FILE *stream)
Introduction to Scalloc
簡介
scalloc的設計強調在concurrent環境下的表現,尤其是在thread / core增加時的performance (secaling),並且保持一定的記憶體效率。其設計仰賴64-bit的記憶體空間與linux demand paging的特性,包含了 :
Real Spans & Virtual Spans
span是allocator用來分配記憶體的概念單位,scalloc使用雙層(real & virtual) span作為分割記憶體的單位。記憶體區段(arena)先分割成virtual span,其內再分成real span,於real span內進行allocation。
Real span & size class
每個real span內依size class被分為相同大小的blocks,real span有29種size class,但real span本身只有9種大小。size class 1-16分別為16bytes至256bytes,每個class相差16bytes(與tcmalloc相同),它們的real span皆有相同的size;17-29分別為512bytes至2MB,每個class相差2倍。>1MB的allocation則直接以mmap處理。
Virtual span
在scalloc初始化時,會進行一次32TB的mmap,此區段稱為arena,其空間被分成以2MB size , 2MB aligned的區塊,即為virtual span。每個使用中的virtual span包含一個real span,virtual span的size class即為該real span的size class,通常real span的size會比virtual span小許多。virtual span有以下特性 :
當virtual span清空後,會放入free list(即span pool),為限制physical fragmentation,若real span大於一定大小,會以madvise釋放空間。
addressable memory : 一個2MB的virtual span最小只會有16KB real span,故整個32TB空間addressable的最小只有(2^45 / 2^21)=256GB
可以看出scalloc的設計假設virtual address近乎無限,若在32bit架構下只有(4GB / 128)=32MB
Backend: Span-Pool
span-pool是一個global資料結構,由stack-like pools的array組成,array以size class為單位。stack-like pools在單thread情形下即為stack。
size class的分割以pre-allocated array的index達成,每個entry內又有一個pre-allocated array(pool array),其entry內含lock-free的Treiber stack,index則為執行時的core number。Treiber stack由元素的singly linked list組成,push與pop以對top pointer的atomic compare-and-swap實作。為避免ABA問題,實作中使用包含在top pointer中的16-bit ABA counter。
以下是Span-pool的pseudo code :
put
thread會先取得real-span index與core index並放入對應的pool : 在放入之前,若其real-span size > MADVISE_THRESHOLD,則用madvise釋放記憶體。MADVISE_THRESHOLD預設為32KB,即size class增加方式的分界(512bytes)的real-span size。
get
先試由所屬real-span / core index取得span(fast path);若失敗,則搜尋整個pool,試取得空span;若仍失敗,由arena取得新的virtual span。
Frontend: Allocation and Deallocation
span可以有幾種不同的狀態 :
span可以是以下其中之一 : expected, free, hot, floating, reusable。
其他3種狀態皆在frontend,且span此時有所屬的span size
每個span在frontend時,都會被分配到一個local-allocation buffer (LAB),LAB可以調整為thread-local(TLAB)或core-local(CLAB)模式,分別由每thread / core擁有一個。 LAB內包含每size class一個的hot span,與一些也以size class分類的reusable span。
span內的free若是其他thread進行的稱為remote free,自身thread進行的為local free。malloc皆是由local hot span進行。針對remote free的fragmentation問題,scalloc使用兩個free list將local與remote free分開處理。
Allocation
thread先嘗試LAB的hot span,在對應hot span內的local free list取得block (fast path)。
若沒有對應的hot span : 試由resuable span取得新的hot span;若仍失敗,由span-pool取得。
若有hot span但local free list為空 : 若remote free list相對reusability threshold有一定比值,thread將所有remote block移至local,並進行fast patch;若沒有,同上一點方式取得新hot span。
將remote block移至local的條件判斷為減少lock的效能考量
Deallocation
Operation Complexity
allocation
只考慮hot span且不進行任何cleanup,在沒有contention的情形下 :
有contention情形下,因同步進行的deallocation,可能需要考慮1個以上的reusable span,但至少有1個thread可以以constant-time執行
deallocation
只考慮block所在的span :
插入至local free list為constant-time
remote free list為constant-time modulo synchronization(remote free list為lock-free)
不太清楚remote的constant-time modulo synchronization所指為何
推測是至少有1個thread可以以constant-time進行?
span改為reusable為constant-time modulo synchronization (放入reusable set為lock-based)
Span-pool
為constant-time modulo synchronization (span-pool整體為lock-free)
Implementation Details
Real Span
link : 在span-pool或set內時,用來link其他span
epoch : 用以紀錄span的life cycle狀態。word的上部用來紀錄states,下半為一個ABA counter,因free block + state轉換並非atomic。若沒有ABA counter :
thread A | thread B | |
old = epoch | ||
free(last block) | span現在是empty but reusable ,A準備mark free | |
get reusable span -> hot | ||
hot->floating->reusable | span現在是reusable (not empty) | |
compare-and-swap(epoch,old,FREE) | 雖然span內還有block ,但因epoch == old (reusable) ,span被mark free |
Owner : 一個identifier (16 bits)用來分別owning LAB + reference (48 bits)指向該LAB,整個word可以以compare-and-swap atomic更新。當使用LAB的最後一個thread結束,owner會被設為TERMINATED,等到下次LAB重新使用時,owner會有新的identifier,但reference不變(仍是同一個LAB)。
Remote f-list : 實作一個Treiber stack,並同時記錄top pointer與block count (放在同一個word)。若要get所有block,只需要將top改為NULL (atomic),此動作同時set block count=0。
Auxiliary structures and methods
get_lab : 利用owner field取得對應LAB。
is_oprhan : 檢查該span所屬的LAB,其對應thread是否全部結束。
try_mark_* : 嘗試對epoch進行compare-and-swap,同時更改ABA counter (atomic)。
try_refill_from_remotes : 若remote free list大於一定數量(相對於reusability threshold),將所有block移至local。
try_adopt : 更改is_oprhan span的owner (atomic)。
Set : 用來維持reusable span的紀錄
Frontend
Thread Termination
由於LAB沒有對所有span的reference (例如floating span),要找出orphaned,必須比較span的owner與LAB的owner,兩者不同或owner==TERMINATED皆是orphaned span。orphaned皆為floating,於deallocate時由新的LAB adopt。
Handling Large Objects
大於1M直接使用mmap。
fragmentation testing
主要策略
測量最大可用的block(freemax)相對於所有可用空間(free)的比率,freemax相對越小就表示連續的的block越小,即fragmentation 變大。
ptmalloc2 mallinfo : 沒有抓最大可用block的機制,測量可能有困難
從utilization的結果觀察
allocated相對於總記憶體使用的比率,剩下的空間即是浪費掉的空間,可能的來源有overhead、fragmentation等。
fragmentation 可能造成新的allocation無法使用已經free的記憶體,造成總使用空間增加,utilization下降。 若一個process的memory utilization因為fragmentation持續降低,最後可能因為使用空間太大而OOM。
實例 (paper)
facebook-jemalloc : 看 active memory vs RAM usage 長時間比率穩定度(fragmentation 不造成RAM無限消耗)
OOPSLA15-Scalloc : 測量memory consumption時使用Resident Set Size(RSS) sample的平均值,sample rate隨使用的benchmark而不同 (每個benchmark+thread數為一個資料點)
Scalable Memory Allocation : max heap use in benchmark (只有一個值)
Small Block Sizes in rt Embedded Systems : max allocated live memory vs max used memory(原理與facebook類似), 利用在allocator內加code的方式(instrumentation),maximum以最高address計算,並加入implementation overhead的觀察(未詳細說明)。比較4個benchmark pattern,隨allocation / free做graph (profiling)。
The Memory Fragmentation Problem: Solved? : 提到四種數值化模式 :
vs | at (time point) | 缺點 | |
used | requesed | across all point in time (average) | 看不到spike |
used | max requesed | max live(requesed) memory | fragmentation可能還會成長 |
max used | requesed | max memory usage | 可能有極高的fragmentation |
max used | max requesed | not same point in time | 可能低估 |
考慮到implementation overhead,在malloc時的size內減去(ex : malloc(20) , overhead=4 改成malloc(16))。
used memory使用system call追蹤,因allocator只能以page為單位請求記憶體,觀察會有誤差。
更清楚的解釋上述四種數值化模式 https://paper.dropbox.com/doc/Fragmentation-4v9zRLIanLfNw1BoiZ0VH
實驗考量
implementation overhead
考慮到實驗的目的是避免OOM和提高space efficiency,overhead也會影響這兩項的結果,故我認為應該可以只看總消耗量,而不必分開overhead與fragmentation。(還可以減少所需的工作量)
Resident Set Size
實驗平台要求real-time,且盡量減少(或說沒有)swap,且Resident受系統的其他部分影響(由系統管理),故我認為測驗應該基於real(virtual) size,尤其在有swap的情形下,swap in/out會造成程式失去real-time特性。
測量方式
由於實驗包含如tlsf等不會自動map memory(paging)的allocator,故無法由系統判別消耗的RAM數量(利用如ps等),測量需要在allocator本身的code裡進行。
(可能的)測量方法
取得total size
測量時間點
在profiling時,於每次malloc / free前後,並應該與timing / preformance實驗分開做(加入的code可能影響preformance)。
Multithread test
理論上,total size應該以per-thread的方式記錄,但實際運作方式可能依allocator的不同而改變,方法應允許malloc/free可以(嘗試)平行執行。
Memory allocator研究 - jemalloc
設計上重視cache locality勝於減少working set pages使用數目,減少記憶體的使用量可以達到此目的;因為temporal locality通常也意味著spatial locality,所以也盡可能分配連續的記憶體
(同樣地)提到false cache sharing對效能的衝擊
**ROBUST MEMORY MANAGEMENT USING REAL TIME CONCEPTS **
Understanding glibc malloc
https://github.com/jacky6016/malloc-benchmark
實驗測量方向
Tips of malloc & free Making your own malloc library for troubleshooting 重點摘錄
cat /proc/self/maps
Use probability distribution generate 10000 or more random variables( these random variable are allocated size patterns, and it will follow the distribution).
先用exponential distribution產生random number, 程式裡的mean_size = 1 / lambda
memory random size generator finish, Please follow (5/20 done)
這支程式還有支援gamma, normal, Erlang 等分配,可以改CODE試試
random.c是用moment generating function 去刻出來的code
下一步是把產生的radom size餵 給malloc_count 去測試
https://github.com/whosyourdadd/RandMalloc/blob/master/MemSize_Generator/main.cc
應該要先討論畫什麼圖表(i.e 想要看到什麼樣的分析圖),x軸和y軸要放什麼,這樣才知道如何設計實驗流程,才有辦法數學分析,最後再導入網路應用的packet size pattern。
lwip memory allocate mem.c.
[ source ]
Buddy System 是種記憶體配置 (memory allocator) 演算法,先將記憶體分成很多size,最小的單位即是一個 page,這個方式會減少 external fragmentation,因為這個機制就是典型的你有多大就放再那一個適合大小櫃子裡,再來還是會有internal fragmentation 的問題,因位我們已經把一個基本單位規定成一個 Page ,而假如一個 Page 是 64K,那麼假如只要儲存一個52K的東西,那麼就會有12K是空的,這個的好處就是可以分的很清楚,哪個page是誰的,就我認知,解決external fragment會是比較好的選擇,因位假如發生的話單位都是以page來算,internal 可能是用byte來算的。
實例解釋:
現在我們有4個東西要儲存 A , B , C , D, 首先我們第一個要儲存的是 A,而A是佔了 64KB的空間(也可能是基本單位 page size),所以我們開始作對折的動作,step 1
開始,step 2.1
開始做第一次對折,發現空間還是大於他很多,所以我又再切step 2.2
,一直切到step 2.5
才終於剛剛好放下,再來是放 B ,他佔了 264KB,然後我發現我剛好有對的地方所以直接放下去step 3
,再來換C,而C的流程跟B一樣,就是D了,他佔了 264KB,但觀察step 4
和‵step 5.1
其實是沒有剛好放的下D的空間,所以他又再切它,最後這些A B C D 總有用完的時候,就可以將他回收成原本的memory樣式 step 9.1
開始。
由 University of Salzburg, Austria 發展的 scalloc 提供了若干組 memory allocator 的 benchmark suite: scalloc-artifact
編譯與測試
git clone https://github.com/cksystemsgroup/scalloc-artifact.git
cd scalloc-artifact
export BASE_PATH=pwd
tools/make_deps.sh
tools/create_env.sh
找了一圈才發現scalloc-artifact提供的benchmark tools已經是最完整的
Scalloc-artifact test suite測試數據
重現 note-about-madvise 部落格文章上,測試madvise的程式碼。並且在進行修改之後,開了一個新專案放到github上面,照著README操作就可以重現該篇文章上使用madvise帶來效能上的改進。
https://github.com/enginec/madviseBench
目前我的想法是透過分析一個程式的memory usage pattern,例如可能是頻繁的小區塊分配與釋放、或是每次索取的記憶體大小差異g很大等,產生對應的benchmark,之後就可以利用這個benchmark來比較不同memory allocator的效能差異。
原本的想法是參考malloc_count,透過動態連結malloc到測試程式,得知每次malloc呼叫大小和順序,並用這個資料去產生benchmark。
但這種作法的盲點在,假設我們要分析的程式是multi-threaded,那麼光是紀錄每次呼叫malloc的大小和順序是不夠的。我們必須要能夠模擬出每個thread使用malloc/free的大小和時間點,用於建立對應的benchmark,再拿這個benchmark去測試各種malloc實作才有意義。因為有些malloc實作支援multithread,要這樣做才能真正測出各種malloc實作的差異。
目前下幾個關鍵字搜尋,找到兩個商用軟體好像能分析thread等級的memory usage情況。
Memory Management Reference: a resource for programmers and computer scientists interested in memory management and garbage collection.
重現實驗
將來不見得要重新實作,可能只需要做修改/調整參數
SuperMalloc: A Super Fast Multithreaded malloc() for 64-bit Machines
Xenomai 3 內建 TLSF: lib/boilerplate/tlsf/tlsf.c
reddit: Github got 30% better performance using TCMalloc with MySQL
注意細節 : lock(smp environment) , memory leak , fragmention / buddy system實作
這篇使用的硬體沒有MMU
How Memory Allocation Affects Performance in Multithreaded Programs
A Study on Dynamic Memory Allocation Mechanisms for Small Block Sizes in Real-Time Embedded Systems (2012)
Super Allocator for Open Collaborative/Community Runtime (OCR)
Implementations
Benchmarks
Tools