最近看了glibc的ptmaoolc，Goolge的tcmalloc和jemalloc，順便做了一點記錄?？赡苡行┑胤嚼斫獾夭惶珜?，如有發(fā)現(xiàn)還請大神指出。

 
操作系統(tǒng)內(nèi)存布局
    各種malloc的內(nèi)存分配管理方式離不開操作系統(tǒng)的內(nèi)存布局策略。

32位經(jīng)典內(nèi)存布局

    32位系統(tǒng)下經(jīng)典內(nèi)存布局如上，程序起始的1GB地址為內(nèi)核空間，接下來是向下增長的棧空間和由0×40000000向上增長的mmap地址。而堆地址是從底部開始，去除ELF、數(shù)據(jù)段、代碼段、常量段之后的地址并向上增長。但是這種布局有幾個問題，首先是容易遭受溢出攻擊；其次是，堆地址空間只有不到1G有木有？如果mmap內(nèi)存比較少地址很浪費有木有？所以后來就有了另一種內(nèi)存布局。
 

32位默認(rèn)內(nèi)存布局

    這幅圖描述地比較清楚也比較完整。首先是加入了幾種Random offset隨機偏移，導(dǎo)致內(nèi)存溢出攻擊不那么容易了，其次是堆仍然向上，但是mmap向下增長。但是這樣的話?？臻g就不是動態(tài)增長的了，所以現(xiàn)在的操作系統(tǒng)都有棧大小限制來著（Windows好像默認(rèn)是2MB對吧？Linux可以ulimit –s查看）。這種內(nèi)存布局地址利用度比較高。
 
64位內(nèi)存布局

    64位系統(tǒng)的尋址空間比較大，所以仍然沿用了32位的經(jīng)典布局，但是加上了隨機的mmap起始地址，以防止溢出攻擊。反正一時半會是用不了這么大的內(nèi)存地址了，所以至少N多年不會變了（話說要生產(chǎn)出40TB+的內(nèi)存條，把堆內(nèi)存地址用光，一時半會也搞不定吧）。

總結(jié)
    縱觀各種內(nèi)存布局，對于大內(nèi)存各種malloc基本上都是直接mmap的。而對于小數(shù)據(jù)，則通過向操作系統(tǒng)申請擴大堆頂，這時候操作系統(tǒng)會把需要的內(nèi)存分頁映射過來，然后再由這些malloc管理這些堆內(nèi)存塊，減少系統(tǒng)調(diào)用。而在free內(nèi)存的時候，不同的malloc有不同的策略，不一定會把內(nèi)存真正地還給系統(tǒng)，所以很多時候，如果訪問了free掉的內(nèi)存，并不會立即Run Time Error，只有訪問的地址沒有對應(yīng)的內(nèi)存分頁，才會崩掉。
 

Ptmalloc
    Ptmalloc采用主-從分配區(qū)的模式，當(dāng)一個線程需要分配資源的時候，從鏈表中找到一個沒加鎖的分配區(qū)，在進行內(nèi)存分配。
 
小內(nèi)存分配
    在ptmalloc內(nèi)部，內(nèi)存塊采用chunk管理，并且將大小相似的chunk用鏈表管理，一個鏈表被稱為一個bin。前64個bin里，相鄰的bin內(nèi)的chunk大小相差8字節(jié)，稱為small bin，后面的是large bin，large bin里的chunk按先大小，再最近使用的順序排列，每次分配都找一個最小的能夠使用的chunk。

    Chunk的結(jié)構(gòu)如上所示，A位表示是不是在主分配區(qū)，M表示是不是mmap出來滴，P表示上一個內(nèi)存緊鄰的chunk是否在使用，如果沒在使用，則size of previous chunk是上一個chunk的大小，否則無意義（而且被用作被分配出去的內(nèi)存了），正式根據(jù)P標(biāo)記位和size of previous chunk在free內(nèi)存塊的時候來進行chunk合并的。當(dāng)然，如果chunk空閑，mem里還記錄了一些指針用于索引臨近大小的chunk的，實現(xiàn)原理就不復(fù)述了，知道大致作用就行。
 
    在free的時候，ptmalloc會檢查附近的chunk，并嘗試把連續(xù)空閑的chunk合并成一個大的chunk，放到unstored bin里。但是當(dāng)很小的chunk釋放的時候，ptmalloc會把它并入fast bin中。同樣，某些時候，fast bin里的連續(xù)內(nèi)存塊會被合并并加入到一個unsorted bin里，然后再才進入普通bin里。所以malloc小內(nèi)存的時候，是先查找fast bin，再查找unsorted bin，最后查找普通的bin，如果unsorted bin里的chunk不合適，則會把它扔到bin里。
 

歡迎中小企業(yè)的老板加入“中小企業(yè)發(fā)展之道”討論中小企業(yè)發(fā)展

1. Ptmalloc默認(rèn)后分配內(nèi)存先釋放，因為內(nèi)存回收是從top chunk開始的。
2. 避免多線程頻繁分配和釋放內(nèi)存，會造成頻繁加解鎖。
3. 不要分配長生命周期的內(nèi)存塊，容易造成內(nèi)碎片，影響內(nèi)存回收。 

 
Tcmalloc

    Ptmalloc在性能上還是存在一些問題的，比如不同分配區(qū)（arena）的內(nèi)存不能交替使用，比如每個內(nèi)存塊分配都要浪費8字節(jié)內(nèi)存等等，所以一般傾向于使用第三方的malloc。
    Tcmalloc是Google gperftools里的組件之一。全名是 thread cache malloc（線程緩存分配器）其內(nèi)存管理分為線程內(nèi)存和中央堆兩部分。

 
小內(nèi)存分配
    對于小塊內(nèi)存分配，其內(nèi)部維護了60個不同大小的分配器（實際源碼中看到的是86個），和ptmalloc不同的是，它的每個分配器的大小差是不同的，依此按8字節(jié)、16字節(jié)、32字節(jié)等間隔開。在內(nèi)存分配的時候，會找到最小復(fù)合條件的，比如833字節(jié)到1024字節(jié)的內(nèi)存分配請求都會分配一個1024大小的內(nèi)存塊。如果這些分配器的剩余內(nèi)存不夠了，會向中央堆申請一些內(nèi)存，打碎以后填入對應(yīng)分配器中。同樣，如果中央堆也沒內(nèi)存了，就向中央內(nèi)存分配器申請內(nèi)存。
 

    在線程緩存內(nèi)的60個分配器（文檔上說60個，但是我在2.0的代碼里看到得是86個）分別維護了一個大小固定的自由空間鏈表，直接由這些鏈表分配內(nèi)存的時候是不加鎖的。但是中央堆是所有線程共享的，在由其分配內(nèi)存的時候會加自旋鎖(spin lock)。
 
    在線程內(nèi)存池每次從中央堆申請內(nèi)存的時候，分配多少內(nèi)存也直接影響分配性能。申請地太少會導(dǎo)致頻繁訪問中央堆，也就會頻繁加鎖，而申請地太多會導(dǎo)致內(nèi)存浪費。在tcmalloc里，這個每次申請的內(nèi)存量是動態(tài)調(diào)整的，調(diào)整方式使用了類似把tcp窗口反過來用的慢啟動（slow start）算法調(diào)整max_length， 每次申請內(nèi)存是申請max_length和每個分配器對應(yīng)的num_objects_to_move中取小的值的個數(shù)的內(nèi)存塊。
 
    num_objects_to_move取值比較簡單，是以64K為基準(zhǔn)，并且最小不低于2，最大不高于32的值。也就是說，對于大于等于32K的分配器這個值為2（好像沒有這樣的分配器 class），對于小于2K的分配器，統(tǒng)一為32。其他的會把數(shù)據(jù)調(diào)整到64K / size 的個數(shù)。（可能是經(jīng)驗數(shù)值，目前2.0版本里的代碼是這么寫的）
 
    對于max_length就比較復(fù)雜了，而且其更多是用于釋放內(nèi)存。max_length由1開始，在其小于num_objects_to_move的時候每次累加1，大于等于的時候累加num_objects_to_move。釋放內(nèi)存的時候，首先max_length會對齊到num_objects_to_move，然后在大于num_objects_to_move的釋放次數(shù)超過一定閥值，則會按num_objects_to_move縮減大小。
 
 
大內(nèi)存分配
    對于大內(nèi)存分配(大于8個分頁, 即32K)，tcmalloc直接在中央堆里分配。中央堆的內(nèi)存管理是以分頁為單位的，同樣按大小維護了256個空閑空間鏈表，前255個分別是1個分頁、2個分頁到255個分頁的空閑空間，最后一個是更多分頁的小的空間。這里的空間如果不夠用，就會直接從系統(tǒng)申請了。

 
分頁管理 – span
    Tcmalloc使用一種叫span的東東來管理內(nèi)存分頁，一個span可以包含幾個連續(xù)分頁。一個span的狀態(tài)只有未分配(這時候在空閑鏈表中)，作為大對象分配，或作為小對象分配（這時候span內(nèi)記錄了小對象的class size）。
    在32位系統(tǒng)中，span分為兩級由中央分配器管理。第一級有2^5個節(jié)點，第二級是2^15個。32位總共只能有2^20個分頁（每個分頁4KB = 2^12）。(騙紙，我在代碼里明明看到的是2^7和2^13，定義了TCMALLOC_LARGE_PAGES宏之后才是 2^5和2^15，可是所有的代碼或者編輯腳本里都沒定義這個宏，可能是文檔沒更新)
在64為系統(tǒng)中，有三級。
 
    在資源釋放的時候，首先計算其分頁編號，然后再查找出它對應(yīng)的span，如果它是一個小對象，則直接歸入小對象分配器的空閑鏈表。等到空閑空間足夠大以后劃入中央堆。如果是大對象，則會把物理地址連續(xù)的前后的span也找出來，如果空閑則合并，并歸入中央堆中。
 
    而線程緩存內(nèi)的分配器，會根據(jù)max_length、num_objects_to_move和上一次垃圾收集到現(xiàn)在為止的最小鏈表長度，按一定的策略回收資源到中央堆中，具體的算法不再復(fù)述tcmalloc的文檔寫得比較清楚。同樣可以在需要時減少某一個線程的max_length來轉(zhuǎn)移內(nèi)存，但是要等到那個線程下一次執(zhí)行free，觸發(fā)垃圾回收之后才會真正把內(nèi)存返還中央堆。
 
簡而言之，就是： 
小內(nèi)存： 線程緩存隊列 -> 中央堆 -> 中央頁分配器（從系統(tǒng)分配）
大內(nèi)存： 中央堆 -> 向系統(tǒng)請求
    Tcmalloc的管理策略和ptmalloc有很大區(qū)別，理論上性能提高的主要原因在線程緩存不加鎖和少量操作的自旋鎖上。不過按照它的實現(xiàn)方式，不適合多線程頻繁分配大于8個分頁（32KB）的內(nèi)存。否則自旋鎖爭用會相當(dāng)厲害，不過這種情況也比較少。而減少和中央堆交互又依賴于他的線程緩存長度自適應(yīng)算法。
    還有就是它使用了外部的數(shù)據(jù)結(jié)構(gòu)來管理span list，這樣不會每次分配內(nèi)存都要浪費header的長度。但是他的對齊操作又比ptmalloc多浪費了一些內(nèi)存。（有點空間換時間的意思）
    所以無論是ptmalloc還是tcmalloc都應(yīng)該盡量減少大內(nèi)存的分配和釋放。盡量先分配、后釋放。
 
 
Jemalloc

    最后來看看第三個神器，jemalloc。這是FreeBSD、NetBSD和Firefox的默認(rèn)malloc。據(jù)作者說，在高CPU核心數(shù)的情況下比tcmalloc性能還好。
    Jemalloc的設(shè)計目標(biāo)是：

1. 快速分配和回收
2. 低內(nèi)存碎片
3. 支持堆性能分析

    Jemalloc 把內(nèi)存分配分為了三個部分，第一部分類似tcmalloc，是分別以8字節(jié)、16字節(jié)、64字節(jié)等分隔開的small class；第二部分以分頁為單位，等差間隔開的large class；然后就是huge class。內(nèi)存塊的管理也通過一種chunk進行，一個chunk的大小是2^k (默認(rèn)4 MB)。通過這種分配實現(xiàn)常數(shù)時間地分配small和large對象，對數(shù)時間地查詢huge對象的meta（使用紅黑樹）。
    默認(rèn)64位系統(tǒng)的劃分方式如下：
    Small: [8], [16, 32, 48, ..., 128], [192, 256, 320, ..., 512], [768, 1024, 1280, ..., 3840]
    Large: [4 KiB, 8 KiB, 12 KiB, ..., 4072 KiB]
    Huge: [4 MiB, 8 MiB, 12 MiB, ...] 

    Jemalloc也使用了分配區(qū)（arena）來維護內(nèi)存。線程按第一次分配small或者large內(nèi)存請求的順序Round-Robin地選擇一個分配區(qū)。每個分配區(qū)都維護了一系列分頁，來提供small和large的內(nèi)存分配請求。并且從一個分配區(qū)分配出去的內(nèi)存塊，在釋放的時候一定會回到該分配區(qū)。

內(nèi)存分配

    每個分配區(qū)內(nèi)都會包含meta信息，記錄了其對應(yīng)的chunk列表，每個chunk的頭部都記錄了chunk的分配信息。在使用某一個chunk的時候，會把它分割成很多個run，并記錄到bin中。不同size的class對應(yīng)著不同的bin，這點和前面兩種分配器一樣。在bin里，都會有一個紅黑樹來維護空閑的run，并且在run里，使用了bitmap來記錄了分配狀態(tài)。
    和前面兩種分配器不同的是，分配區(qū)會同時維護兩組run的紅黑樹，一組是未被分配過內(nèi)存（clean區(qū)域），另一組是回收的內(nèi)存（dirty區(qū)域）。而且不是前面那兩種分配器所使用的鏈表。
    同樣，每次分配，都是選取最小且符合條件的內(nèi)存塊。但是優(yōu)先從dirty區(qū)域查找。
    由于分配區(qū)的設(shè)計和ptmalloc差不多。在訪問分配區(qū)的時候需要對其加鎖，或者對某一個size的bin加粒度更小的鎖。為了減少鎖征用，這里又參照tcmalloc引入了線程緩存。并且其線程緩存的垃圾回收機制和tcmalloc一樣，也是基于分配請求的頻率自動調(diào)整的。
    線程緩存的結(jié)構(gòu)就像一個簡化版的arena，加了一些垃圾回收的控制信息。

簡而言之，就是： 
小內(nèi)存（small class）： 線程緩存bin -> 分配區(qū)bin(bin加鎖) -> 問系統(tǒng)要
中型內(nèi)存（large class）：分配區(qū)bin(bin加鎖) -> 問系統(tǒng)要
大內(nèi)存（huge class）： 直接mmap組織成N個chunk+全局huge紅黑樹維護(帶緩存)
 
總結(jié)
    Jemalloc設(shè)計上比前兩個復(fù)雜地多，其內(nèi)部使用了紅黑樹管理分頁和內(nèi)存塊。并且對內(nèi)存分配粒度分類地更細(xì)。這導(dǎo)致一方面比ptmalloc的鎖爭用要少，另一方面很多索引和查找都能回歸到指數(shù)級別，方便了很多復(fù)雜功能的實現(xiàn)。而且在大內(nèi)存分配上，內(nèi)存碎片也會比tcmalloc少。但是也正是因為他的結(jié)構(gòu)比較復(fù)雜，記錄了很多meta，所以在分配很多小內(nèi)存的時候記錄meta數(shù)據(jù)的空間會略微多于tcmalloc。但是又不像ptmalloc那樣每一個內(nèi)存塊都有一個header，而采用全局的bitmap記錄狀態(tài)，所以大量小內(nèi)存的時候，會比ptmalloc消耗的額外內(nèi)存小。
 

大總結(jié)
    看這些個分配器的分配機制，可見這些內(nèi)存管理機制都是針對小內(nèi)存分配和管理。對大塊內(nèi)存還是直接用了系統(tǒng)調(diào)用。所以在程序中應(yīng)該盡量避免大內(nèi)存的malloc/new、free/delete操作。另外這個分配器的最小粒度都是以8字節(jié)為單位的，所以頻繁分配小內(nèi)存，像int啊bool啊什么的，仍然會浪費空間。經(jīng)過測試無論是對bool、int、short進行new的時候，實際消耗的內(nèi)存在ptmalloc和tcmalloc下64位系統(tǒng)地址間距都是32個字節(jié)。大量new測試的時候，ptmalloc平均每次new消耗32字節(jié)，tcmalloc消耗8字節(jié)（我想說ptmalloc弱爆啦，而且tcmalloc）。所以大量使用這些數(shù)據(jù)的時候不妨用數(shù)組自己維護一個內(nèi)存池，可以減少很多的內(nèi)存浪費。（原來STL的map和set一個節(jié)點要消耗近80個字節(jié)有這么多浪費在這里了?。?br>    而多線程下對于比較大的數(shù)據(jù)結(jié)構(gòu)，為了減少分配時的鎖爭用，最好是自己維護內(nèi)存池。單線程的話無所謂了，呵呵。不過自己維護內(nèi)存池是增加代碼復(fù)雜度，減少內(nèi)存管理復(fù)雜度。但是我覺得，255個分頁以下（1MB）的內(nèi)存話，tcmalloc的分配和管理機制已經(jīng)相當(dāng)nice，沒太大必要自己另寫一個。
    另外，Windows下內(nèi)存分配方式不知道，不同類型(int、short和bool)連續(xù)new的地址似乎是隔開的，可能是內(nèi)部實現(xiàn)的粒度更小，不同size的class更多。測試10M次new的時候，debug模式下明顯卡頓了一下，平均每次new的內(nèi)存消耗是52字節(jié)（32位）和72字節(jié)（64位）[header更復(fù)雜?]。但是Release模式下很快，并且平均每次new的內(nèi)存消耗是20字節(jié)（32位）和24字節(jié)（64位）?？梢圆聹yVC的malloc的debug模式還含有挺大的debug信息。是不是可以得出他的header里，Release版本只有1個指針，Debug里有5個指針呢？