最近看了glibc的ptmaoolc，Goolge的tcmalloc和jemalloc，順便做了一點(diǎn)記錄。可能有些地方理解地不太對(duì)，如有發(fā)現(xiàn)還請(qǐng)大神指出。

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

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

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

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

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

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

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

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

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

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

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

 
Tcmalloc

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

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

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

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

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

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

    Jemalloc 把內(nèi)存分配分為了三個(gè)部分，第一部分類(lèi)似tcmalloc，是分別以8字節(jié)、16字節(jié)、64字節(jié)等分隔開(kāi)的small class；第二部分以分頁(yè)為單位，等差間隔開(kāi)的large class；然后就是huge class。內(nèi)存塊的管理也通過(guò)一種chunk進(jìn)行，一個(gè)chunk的大小是2^k (默認(rèn)4 MB)。通過(guò)這種分配實(shí)現(xiàn)常數(shù)時(shí)間地分配small和large對(duì)象，對(duì)數(shù)時(shí)間地查詢(xún)huge對(duì)象的meta（使用紅黑樹(shù)）。
    默認(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）來(lái)維護(hù)內(nèi)存。線程按第一次分配small或者large內(nèi)存請(qǐng)求的順序Round-Robin地選擇一個(gè)分配區(qū)。每個(gè)分配區(qū)都維護(hù)了一系列分頁(yè)，來(lái)提供small和large的內(nèi)存分配請(qǐng)求。并且從一個(gè)分配區(qū)分配出去的內(nèi)存塊，在釋放的時(shí)候一定會(huì)回到該分配區(qū)。

內(nèi)存分配

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

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

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