nedmalloc結(jié)構(gòu)分析
nedmalloc是一個跨平臺的高性能多線程內(nèi)存分配庫，很多庫都使用它，例如:OGRE.現(xiàn)在我們來看看nedmalloc的實(shí)現(xiàn) (以WIN32部分為例)
位操作小技巧；
i.獲取最低位的出現(xiàn)位置的掩碼；x&(-x)
ii.判斷值為2的冪：x & (x-1) == 0
iii.獲取從最低的值為1的位開始到左邊MSB的掩碼: x | (-x)
iv.字節(jié)對齊；(x + 2^m) &( 2^m -1)
nedmalloc設(shè)計的數(shù)據(jù)結(jié)構(gòu)和使用方法有幾個有趣的地方：
1.從操作系統(tǒng)得到的內(nèi)存后分了3層，內(nèi)存塊=>簡單內(nèi)存描述結(jié)構(gòu)(數(shù)據(jù)節(jié)點(diǎn))=>內(nèi)存數(shù)據(jù)節(jié)點(diǎn)鏈(面向開發(fā)者)
2.內(nèi)存塊處理流程：
創(chuàng)建線程共享內(nèi)存池(多個線程通過這個”池”來向系統(tǒng)申請/復(fù)用內(nèi)存，這里需要互斥)
|-->釋放內(nèi)存時將內(nèi)存放到各線程自己的數(shù)據(jù)結(jié)構(gòu)中（TLS），對于小塊內(nèi)存用簡單數(shù)組鏈表來保存，
對于大塊的內(nèi)存就用過“樹”來保存（設(shè)計上應(yīng)該是考慮小塊的內(nèi)存使用頻率較高，簡單鏈表訪問
時間相對快）
線程請求內(nèi)存時，首先從線程自己的維護(hù)的空閑內(nèi)存查找，然后再從線程內(nèi)存池中查找。
3.內(nèi)存是按照"塊"對齊的形式分配的，而且用戶得到的可用內(nèi)存是真正內(nèi)存塊的"一部分"，由于塊的大小是對齊的，
表示塊大小字節(jié)的最低3位用于表示塊的使用標(biāo)志。
現(xiàn)在我們具體看看Win32平臺下nedmalloc
1.分配流程
nedpmalloc(nedpool *p, size_t size)
|
從線程的獨(dú)立數(shù)據(jù)中查詢空閑的內(nèi)存
GetThreadCache(&p, &threadcache, &mymspace, &size)
| |------>檢查申請大小，如果小于sizeof(threadcacheblk)，用sizeof(threadcacheblk)代替
| | 因?yàn)樵谠搲K內(nèi)存"釋放"時需要放到空閑鏈表中，注意threadcacheblk的內(nèi)存布局和malloc_chunk
| | 是一樣的，雖然它們的含義有區(qū)別。
| | |
| | 對于首次調(diào)用來說，需要初始化全局內(nèi)存池
| | InitPool(&syspool, 0, -1)
| | |--------->檢查全局參數(shù)并初始化ensure_initialization
| | 初始化內(nèi)存池的鎖和設(shè)置TLS
| | INITIAL_LOCK(&p->mutex)
| | TlsAlloc(syspool->mycache)
| | |
| | 創(chuàng)建線程池的空間
| | create_mspace(capacity, 1)
| | |
| | 計算"實(shí)際"分配的大小：
| | capacity + pad_request(sizeof(struct malloc_state)) + { align_offset(chunk2mem(0))
| | pad_request(sizeof(struct malloc_segment)) + ((MCHUNK_SIZE + CHUNK_ALIGN_MASK) &
| | ~CHUNK_ALIGN_MASK)}
| |
| | 從大小的計算可以知道，在沒有被"外部接口"使用時，至少會包含malloc_state結(jié)構(gòu)和malloc_segment結(jié)構(gòu)
| | 這里多個數(shù)據(jù)結(jié)構(gòu)都是分別計算塊對齊的（這里分結(jié)構(gòu)對齊的目的一方面為了訪問結(jié)構(gòu)的時候可以從塊對
| | 齊的位置開始,這樣在存儲的時候會快一些,但最主要的是為了使地址低位的bit"空閑",用于表示其他的含義）
| | |
| | 初始化malloc_state結(jié)構(gòu)
| | init_user_mstate(tbase, tsize)
| | ||
| | 這個函數(shù)中需要注意幾個細(xì)節(jié)：
| | 1.指針計算：
| | mchunkptr msp = align_as_chunk(tbase); 計算對齊偏移，align_as_chunk中會有chunk2mem的調(diào)用
| | mstate m = (mstate)(chunk2mem(msp));malloc_state的位置比對塊其后的malloc_chunk偏移8個字
| | 節(jié)(32Bit計算)
| | 2.大小計算：
| | msp->head = (pad_request(sizeof(struct malloc_state))|PINUSE_BIT|CINUSE_BIT)
| | malloc_chunk的大小只計算了malloc_state，而不是可用空間的大小，可用空間大小是在
| | malloc_state中設(shè)置的
| |
| | m->seg.base = m->least_addr = tbase;
| | m->seg.size = m->footprint = m->max_footprint = tsize;
| |
| | 3. 內(nèi)存塊鏈表的初始化
| | init_bins(m);
| | malloc_state結(jié)構(gòu)中smallbins是一個malloc_chunk的指針數(shù)組，特別需要注意它的定義和使用
| | smallbins[(NSMALLBINS+1)*2]
| | 這里一共分配了 sizeof(malloc_chunk*) * (NSMALLBINS+1)*2 個字節(jié)
| | 在使用的時候是通過smallbin_at來獲取對應(yīng)的指針，這個宏返回的地址實(shí)際上是smallbins中
| | 元素的地址，并將這個地址強(qiáng)制轉(zhuǎn)換為malloc_chunk類型變量，也就是說如果通過這個
| | 指針訪問/修改變量，實(shí)際上修改的是smallbins的內(nèi)容，而且
| | p = smallbin_at(m, i)得到的p和smallbins對應(yīng)關(guān)系是：
| | p->prev_foot <==> smallbins[i*2]
| | p->head <==> smallbins[i*2 + 1]
| | p->fd <==> smallbins[i*2 + 1 + 1] == smallbins[(i＋1)*2]， smallbin_at(i+1)的返回值
| | 4. 計算下一個malloc_chunk的位置，這個malloc_chunk才是用于維護(hù)后面連續(xù)的內(nèi)存塊的
| | next_chunk(mem2chunk(m))
| | 初始化空閑內(nèi)存塊的信息
| | init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) - TOP_FOOT_SIZE)
| | 這個函數(shù)做兩件事:
| | i.設(shè)置malloc_state真正的開始分配位置和可用到小;
| | ii.設(shè)置"最后"一個malloc_chunk(末尾的塊，不用特殊用途)的大小，這個塊的是沒有使用的標(biāo)志位的
| |---->分配線程緩存AllocCache(nedpool* p)
| |-->分配新的threadcache結(jié)構(gòu)
| tc=p->caches[n]=(threadcache *) mspace_calloc(p->m[0], 1, sizeof(threadcache))
| mspace_malloc(這個函數(shù)中的邏輯分支比較多，需要結(jié)合內(nèi)存釋放來分析，后面我們再詳細(xì)看),由于
| threadcache比較小，
| 所以這里大小會調(diào)整為MIN_CHUNK_SIZE，并且內(nèi)存會在malloc_state的top中分配
| size_t rsize = ms->topsize -= nb;
| mchunkptr p = ms->top;
| mchunkptr r = ms->top = chunk_plus_offset(p, nb);
| r->head = rsize | PINUSE_BIT;
| |
| |
| 初始化thread_cache，并設(shè)置線程的TLS
| TlsSetValue(p->mycache, (void *)(size_t)(n+1))
| 需要注意的是:這里用的值是n+1, 另外tc->mymspace=tc->threadid % end(這里求余實(shí)際上是為了減少碰撞)
| (事實(shí)上thread_cache結(jié)構(gòu)是用于維護(hù)內(nèi)存申請者內(nèi)存塊信息的中間結(jié)構(gòu))
如果返回的內(nèi)存緩存thread_cache結(jié)構(gòu)有效，而且調(diào)整后的大小，那么請求的內(nèi)存從cache中分配threadcache_malloc(p, tc, &size)
| |-->分配內(nèi)存的時候是按照塊對齊的(8,16,20...)字節(jié)，所以這里首先計算能滿足用戶需求的最小的塊大小
| (threadcache有一個在使用上和malloc_state的smallbins非常相似的結(jié)構(gòu)設(shè)計成員bins,它是threadcacheblk的指
| 針數(shù)組，但是在使用上，它們有所不同)
| |
| 獲取對應(yīng)塊大小對齊的指針binsptr=&tc->bins[idx*2](這里是對指針數(shù)組成員取了地址),如果當(dāng)前的鏈表信息為
| 空，或者空間不足，那么檢查下一個塊，這里只檢查下一個大小的塊，是為了減少損失的內(nèi)存使用。如果得
| 到的塊非空，那么將當(dāng)前的塊從鏈表中分離出來返回（這里每個鏈包含兩個指針，應(yīng)該是首，尾指針）
|
如果從線程各自的緩存中分配失敗，那么就從malloc_state中分配
mstate pms = GetMSpace(p, &tc, mymspace, size)
| |->根據(jù)myspace獲取malloc_state(注意，獲取的malloc_state并不一定是當(dāng)前線程創(chuàng)建的)，
| 如果該malloc_state不能鎖定，那么歷遍其他的malloc_state看能否鎖定，如果失敗，只要沒有超過內(nèi)
| 存池允許的上限， 那么創(chuàng)建一個。這里有個細(xì)節(jié)
| if(tc)
| tc->mymspace=n;
| else
| {
| if(TLSSET(p->mycache, (void *)(size_t)(-(n+1)))) abort();
| }
| 如果在首次初始化線程緩存thread_cache的時候失敗，TLS的值將會是-1, 而后面會到達(dá)GetMSpace，假
| 設(shè)這時候創(chuàng)建成功，那么TLS會變成-2,這樣在下次GetThreadCache的時候會重新myspace為1，這樣它
| 不會進(jìn)行Allocache的調(diào)用;如果這時創(chuàng)建失敗，那么會等待上一次使用的malloc_state空閑，這是TLS會
| 保持-1, 最后會將myspace設(shè)置為0。
在獲取的malloc_state上分配空間mspace_malloc(pms, size)
2.內(nèi)存釋放流程
nedpfree(nedpool *p, void* mem)
|
計算當(dāng)前線程使用的cache信息
GetThreadCache(&p, &tc, &mymspace, 0)(線程對應(yīng)的cache確定(分配成功)后是不會改變的)
|
如果內(nèi)存塊比較小，而且thread_cache成功，那么將內(nèi)存塊放到cache中
threadcache_free(p, tc, mymspace, mem, memsize)
|->將mem轉(zhuǎn)變?yōu)閠hreadcacheblk*,并根據(jù)mem對應(yīng)內(nèi)存塊的實(shí)際大小（申請者使用的部分只是
真實(shí)內(nèi)存塊的一部分）鏈入到thread_cache的bin成員中（有需要的話調(diào)整首尾指針）
如果cache中的內(nèi)存塊總大小超過特定上限時將cache中的內(nèi)存返回到malloc_state中
ReleaseFreeInCache->根據(jù)加入到cache的先后順序?qū)hreadcacheblk釋放到malloc_state
|
RemoveCacheEntries->從cache的尾指針開始?xì)v遍threadcacheblk鏈，將"時間"過長的塊釋放
mspace_free(0, f)
|--->獲取malloc_state
這里需要先描述一下malloc_trunk結(jié)構(gòu)的含義：
struct malloc_chunk {
size_t prev_foot; /* Size of previous chunk (if free). */
size_t head; /* Size and inuse bits. */
struct malloc_chunk* fd; /* double links -- used only if free. */
struct malloc_chunk* bk;
};
如果當(dāng)前malloc_chunk被使用，那么下一個malloc_chunk的head的pinuse位會被置位，而且它（下一個
chunk）的prev_foot = malloc_state ^ mparams.magic. 如果當(dāng)前塊未被使用，那么它（當(dāng)前塊）的
prev_foot是上一個塊的大小，而且下一個塊的pinuse不會被置位，而且它（下一個chunk）的prev_foot表
示上一塊的大小。
（prev_foot的最低位是用于表示該塊是否為操作系統(tǒng)的真正分配的內(nèi)存）
根據(jù)malloc_chunk的狀態(tài)進(jìn)行不同的"釋放"處理:
i.如果當(dāng)前塊是從操作系統(tǒng)中分配，那么返還給操作系統(tǒng)HeapFree
ii.[向前合并]如果當(dāng)前塊的前一塊空閑，那么將這兩塊（不可能同時出現(xiàn)3塊同時空閑，而且但前塊在最
后一塊"FFN"）一起處理
a.如果首塊地址不同于malloc_state的dv(它的作用是保存連續(xù)空間中中間釋放的連續(xù)塊，對于先申請
先釋放的應(yīng)用來說，這種處理方式會有好處，因?yàn)樵诜峙涞臅r候會先檢查dv是否能滿足需求),那么
根據(jù)塊的大小分別是"存放"到不同的地方等待復(fù)用unlink_chunk
b.如果下一塊正在被使用，那么修改下一塊的prev_foot和pinuse標(biāo)志位
iii.[向后合并]如果下一個塊空閑，那么將當(dāng)前塊和下一塊合并處理
a.如果下一個塊已經(jīng)是top(末尾的空閑塊)，那么更新top的指向（擴(kuò)容）
b.如果下一個塊是dv，那么將當(dāng)前塊合并到dv中
c.如果都不是，那么簡單地釋放下一個塊，并修改下一塊地prev_foot,pinuse
unlink_chunk(fm, next, nsize);
set_size_and_pinuse_of_free_chunk(p, psize);
iv.如果下一塊正在使用，那么簡單修改下一塊的標(biāo)志set_free_with_pinuse(p, psize, next)
對于沒有合并到"空閑"空間中的塊，根據(jù)塊的大小，掛接到不同的鏈表(樹)中
if (is_small(psize)) {
insert_small_chunk(fm, p, psize);
}
else {
tchunkptr tp = (tchunkptr)p;
insert_large_chunk(fm, tp, psize);
}
這里需要補(bǔ)充一下malloc_state的smallbins成員的使用：
所有"釋放"到malloc_state的空閑內(nèi)存塊會連成雙向鏈表，而smallbins中pref_foot和head是不直接使用
的，smallbins的大小是為了訪問fd和bk兩個指針而設(shè)計的。smallbins實(shí)際上是將鏈表中按照內(nèi)存塊的的
大小分段保存鏈表的指針，方便在分配時查找。
(理解了這個，那么insert_small_chunk的處理流程就比較簡單了)
現(xiàn)在看看比較大的內(nèi)存塊的處理思想：
"大塊"內(nèi)存的"釋放"是放到"樹中的，樹的結(jié)構(gòu)根據(jù)內(nèi)存塊的大小(256為單位)按照類似"哈夫曼"編碼的的
形式劃分到二叉樹中，樹的每個節(jié)點(diǎn)是一個雙向鏈表，保存了大小相同的塊的指針。（思路清楚了，加
入、刪除節(jié)點(diǎn)的代碼比較容易理解，這里不再展開）需要注意的是這里malloc_stat的treebins成員保存的是
樹（塊區(qū)域大小）的開始指針（很簡單的使用方式），它的用法和smallbins的"似結(jié)構(gòu)體非結(jié)構(gòu)體"的特殊用
法不同。
3.擴(kuò)展分配nedprealloc函數(shù)
這個函數(shù)是nedpmalloc -> memcpy -> nedpfree的組合，這里不展開了，需要注意的是，如果新申請的空間比原來的空間小，那么是直接返回原來的空間的。
現(xiàn)在，我們再看看內(nèi)存分配最終的入口mspace_malloc的實(shí)現(xiàn)（對著mspace_free來看，比較容易理解）
4.內(nèi)存分配邏輯
mspace_malloc
|
i.如果請求的塊小于MAX_SMALL_REQUEST，首先嘗試在smallbins中分配
b = smallbin_at(ms, idx);
p = b->fd;
unlink_first_small_chunk(ms, b, p, idx);
set_inuse_and_pinuse(ms, p, small_index2size(idx));
注意，為了提高重用成功率，這里允許使用使用比實(shí)際請求大小大一階（下一個塊對齊大小）的塊
|(如果分配不成功)
如果請求的塊大于malloc_state的dvsize（上一個空洞塊留下的空隙）:
i.smallbin非空，那么在smallbin中分配后檢查是否可以替換原來的dv塊
if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE){...}
else{... replace_dv(ms, r, rsize);}
ii.從treebin中分配tmalloc_small()
|
根據(jù)請求大小計算樹的根(開始查找最小匹配塊的根)
compute_bit2idx(leastbit, i);
v = t = *treebin_at(m, i);
|
查找最小的匹配塊while ((t = leftmost_child(t)) != 0){...}
并將分配后留下的空閑塊設(shè)置到dv中
unlink_large_chunk(m, v);
replace_dv(m, r, rsize);
ii.如果申請大小大于MAX_REQUEST,實(shí)際上會失敗
iii.計算塊對齊大小pad_request(bytes)，并從樹中分配
tmalloc_large(ms, nb)
|
tmalloc_large和tmalloc_small的主要不同是：
a.tmalloc_large首先根據(jù)大小計算"最接近"的節(jié)點(diǎn)，并從該節(jié)點(diǎn)開始計算"最小的"滿足需求的節(jié)點(diǎn)
b.如果"最接近節(jié)點(diǎn)"為空，tmalloc_large允許擴(kuò)展一階大小來尋找"最小的"滿足需求大的節(jié)點(diǎn)
(結(jié)合malloc_tree_chunk和塊的組織方式，代碼比較容易理解)
iv.如果請求大小小于dvsize，那么從dv中分配
mchunkptr p = ms->dv;
mchunkptr r = ms->dv = chunk_plus_offset(p, nb);
ms->dvsize = rsize;
v.如果請求大小小于topsize，那么從malloc_state的top塊中分配
vi.從系統(tǒng)空間中分配sys_alloc(ms, nb);
sys_alloc兼容了多個平臺分配機(jī)制，通過不同宏來開關(guān)對應(yīng)的代碼段，對于Win32來說，最終會調(diào)用HeapAlloc
sys_alloc流程：
按照塊對齊和附加內(nèi)存管理結(jié)構(gòu)（如malloc_state）計算內(nèi)存塊的大小
-->不同平臺下使用不同的系統(tǒng)函數(shù)分配"物理內(nèi)存"(系統(tǒng)內(nèi)存)，并將得到的內(nèi)存
|(這里主要不同宏控制的代碼，比較簡單，不展開了)
|
如果malloc_state不含有真正的可用內(nèi)存（top為空），那么初始化它init_bins,init_top
如果malloc_state已經(jīng)初始化，那么檢查是否可以將top中剩下的空間合并到新分配的空間中（只有在可連續(xù)分配擴(kuò)展的
情況下才有效），并重新初始化init_top, 這里合并分了兩種情況：
a.新分配的塊在某個分快后，并和前一個分塊在地址空間上相連，而且前一分塊空間包含top
while (sp != 0 && tbase != sp->base + sp->size)
sp = (NO_SEGMENT_TRAVERSAL) ? 0 : sp->next;
segment_holds(sp, m->top)
b.某一個現(xiàn)有的分快緊接著新分配的塊，這時需要將原來的塊合并到新分配的塊prepend_alloc
c.a和b都不滿足的情況下，將新塊加入到塊鏈表add_segment(m, tbase, tsize, mmap_flag)，并重新設(shè)置top
|
|
從top中分配內(nèi)存
好了，現(xiàn)在我們對nedmalloc的處理思想和算法實(shí)現(xiàn)都比較清楚了(在*nix平臺下還有一些細(xì)節(jié)這里沒有列處理，可以查看代碼),下面概括一下：
1.使用連續(xù)的內(nèi)存分段思想管理大片的連續(xù)內(nèi)存
2.從1的內(nèi)存塊中以塊對齊方式分配內(nèi)存，小的內(nèi)存分塊放到線程的TLS指定的cache雙向鏈表中，大的分塊放到樹結(jié)構(gòu)中
3.樹結(jié)構(gòu)是以類似哈夫曼編碼的方式組織的（以塊大小編碼），每個內(nèi)部節(jié)點(diǎn)是一個雙向鏈表
4.外部內(nèi)存申請：thread cache->線程公用內(nèi)存池; 釋放：線程cache鏈表->內(nèi)存節(jié)點(diǎn)樹