?nedmalloc是一個跨平臺的高性能多線程內存分配庫，很多庫都使用它，例如:OGRE.現在我們來看看nedmalloc的實現(以WIN32部分為例)
???
位操作小技巧；
（1）、獲取最低位的出現位置的掩碼；x&(-x)
（2） 、判斷值為2的冪：x& (x-1) == 0
（3） 、獲取從最低的值為1的位開始到左邊MSB的掩碼:x | (-x)
（4） 、字節對齊；(x+ 2^m) &( 2^m -1)

nedmalloc設計的數據結構和使用方法有幾個有趣的地方：
1、從操作系統得到的內存后分了3層，內存塊=>簡單內存描述結構(數據節點)=>內存數據節點鏈(面向開發者)
2、內存塊處理流程：
?創建線程共享內存池(多個線程通過這個“池”來向系統申請/復用內存，這里需要互斥)
??????|-->釋放內存時將內存放到各線程自己的數據結構中（TLS），對于小塊內存用簡單數組鏈表來保存，
??????????對于大塊的內存就用過“樹”來保存（設計上應該是考慮小塊的內存使用頻率較高，簡單鏈表訪問
??????????時間相對快）??
?線程請求內存時，首先從線程自己維護的空閑內存查找，然后再從線程內存池中查找。

3、內存是按照"塊"對齊的形式分配的，而且用戶得到的可用內存是真正內存塊的"一部分"，由于塊的大小是對齊的，表示塊大小的字節的最低3位用于表示塊的使用標志。

========================================================

??現在我們具體看看Win32平臺下nedmalloc：
1、分配流程
??nedpmalloc(nedpool *p, size_t size)
?????|
??從線程的獨立數據中查詢空閑的內存
??GetThreadCache(&p, &threadcache,&mymspace, &size)
?????|???|------>檢查申請大小，如果小于sizeof(threadcacheblk)，用sizeof(threadcacheblk)代替
?????|???|???????因為在該塊內存"釋放"時需要放到空閑鏈表中，注意threadcacheblk的內存布局和malloc_chunk
?????|???|???????是一樣的，雖然它們的含義有區別。
?????|???|???????????????|
?????|???|???????對于首次調用來說，需要初始化全局內存池
?????|???|???????InitPool(&syspool, 0, -1)
?????|???|????????????|--------->檢查全局參數并初始化ensure_initialization
?????|???|???????????????????????初始化內存池的鎖和設置TLS
?????|???|???????????????????????INITIAL_LOCK(&p->mutex)
?????|???|???????????????????????TlsAlloc(syspool->mycache)
?????|???|?????????????????????????????|
?????|???|???????????????????????創建線程池的空間
?????|???|???????????????????????create_mspace(capacity, 1)
?????|???|?????????????????????????????|
?????|???|????????????????????計算"實際"分配的大小：
?????|???|?????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結構和malloc_segment
?????|??? |? 結構， 這里多個數據結構都是分別計算塊對齊的（這里分結構對齊的目的一方面為了訪問結構的時候可
?????|??? |? 以從塊對 齊的位置開始，這樣在存儲的時候會快一些，但最主要的是為了使地址低位的bit"空閑"，用于 ?? ? ?|???|? 表 示其他的含義）
?????|???|?????????????????????????????|
?????|???|??????????????????初始化malloc_state結構
?????|???|??????????????????init_user_mstate(tbase, tsize)
?????|???|?????????????????????????????||
?????|???|?????????????????這個函數中需要注意幾個細節：
?????|??? |? ? ?? ? ?（1）指針計算：
?????|???|??????????????????mchunkptr msp = align_as_chunk(tbase); ?? ? | ??| ? ?? ? ?? ? ??計算對齊偏移，align_as_chunk中會有chunk2mem的調用。 ?????|???|??????????????????mstate m = (mstate)(chunk2mem(msp)); ?? ?|??? |? ? ?? ? ?? ???malloc_state的位置比對塊其后的malloc_chunk偏移8個字節(32Bit計算)。
?????|??? |? ? ?? ? ??（2）大小計算：
?????|???|???????????? ? ?msp->head = (pad_request(sizeof(structmalloc_state)) | PINUSE_BIT | CINUSE_BIT)
?????|???|?????????????????malloc_chunk的大小只計算了malloc_state，而不是可用空間的大小，可用空間大小是在
?????|???|?????????????????malloc_state中設置的
?????|???|?????????????????????????
?????|???|?????????????????m->seg.base = m->least_addr =tbase;
?????|???|?????????????????m->seg.size = m->footprint =m->max_footprint = tsize;
?????|???|??????????????????????
?????|??? |? ? ?? ? ??（3）內存塊鏈表的初始化
?????|???|??????????????????init_bins(m);
?????|???|??????????????????malloc_state結構中smallbins是一個malloc_chunk的指針數組，特別需要注意它的定義和使 ? ? ?|??? |? ? ?? ? ?? ???用。
?????|???|??????????????????smallbins[(NSMALLBINS+1)*2]
?????|???|??????????????????這里一共分配了 sizeof(malloc_chunk*) * (NSMALLBINS+1) * 2個字節
?????|???|??????????????????在使用的時候是通過smallbin_at來獲取對應的指針，這個宏返回的地址實際上是smallbins中
?????|??? |? ? ?? ? ?? ? ?元素的地址，并將這個地址強制轉換為malloc_chunk類型變量，也就是說如果通過這個
?????|??? |? ? ?? ? ?? ? ?指針訪問/修改變量，實際上修改的是smallbins的內容，而且
?????|???|??????????????????p = smallbin_at(m, i)得到的p和smallbins對應關系是：
?????|???|??????????????????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才是用于維護后面連續的內存塊的
?????|???|????????????????next_chunk(mem2chunk(m))
?????|???|????????????????初始化空閑內存塊的信息
?????|???|????????????????init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) -TOP_FOOT_SIZE)???
?????|???|????????????????這個函數做兩件事:
?????|???|????????????????i、設置malloc_state真正的開始分配位置和可用到小；
?????|???|???????????????ii、設置"最后"一個malloc_chunk(末尾的塊，不用特殊用途)的大小，這個塊的是沒有使用的標 ? ? ?|??? |? ? ?? ? ?? ? ?? ?志位的。
?????|???|---->分配線程緩存AllocCache(nedpool* p)
?????|??????????????|-->分配新的threadcache結構
?????|??????????????tc=p->caches[n]=(threadcache *)mspace_calloc(p->m[0], 1,sizeof(threadcache))
?????|??????????????mspace_malloc(此函數中的邏輯分支較多，需要結合內存釋放來分析，后面我們再詳細看)，由于
?????|??????????????threadcache比較小，
?????|??????????????所以這里大小會調整為MIN_CHUNK_SIZE，并且內存會在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，并設置線程的TLS
?????|?????????TlsSetValue(p->mycache, (void *)(size_t)(n+1))?
?????|?????????需要注意的是：這里用的值是n+1，另外tc->mymspace =tc->threadid % end(這里求余實際上是為了減少碰撞)
?????|??????????(事實上thread_cache結構是用于維護內存申請者內存塊信息的中間結構)
如果返回的內存緩存thread_cache結構有效，而且調整后的大小，那么請求的內存從cache中分配threadcache_malloc(p,tc, &size)
?????|???|-->分配內存的時候是按照塊對齊的(8,16,20...)字節，所以這里首先計算能滿足用戶需求的最小的塊大小
?????|?????(threadcache有一個在使用上和malloc_state的smallbins非常相似的結構設計成員bins,它是threadcacheblk的指
?????|??????針數組，但是在使用上，它們有所不同)
?????|???????????|
?????|?????獲取對應塊大小對齊的指針binsptr=&tc->bins[idx*2](這里是對指針數組成員取了地址),如果當前的鏈表信息為
?????|????空，或者空間不足，那么檢查下一個塊，這里只檢查下一個大小的塊，是為了減少損失的內存使用。如果得
?????|?????到的塊非空，那么將當前的塊從鏈表中分離出來返回（這里每個鏈包含兩個指針，應該是首，尾指針）
?????|
?如果從線程各自的緩存中分配失敗，那么就從malloc_state中分配
? mstatepms = GetMSpace(p, &tc, mymspace,size)
?????|???????????|->根據myspace獲取malloc_state(注意，獲取的malloc_state并不一定是當前線程創建的)，
?????|??????????????如果該malloc_state不能鎖定，那么歷遍其他的malloc_state看能否鎖定，如果失敗，只要沒有超過內
?????|??????????????存池允許的上限， 那么創建一個。這里有個細節
?????|??????????????if(tc)
?????|?????????????????tc->mymspace=n;
?????|?????????????else
?????|?????????????{
?????|?????????????????if(TLSSET(p->mycache, (void *)(size_t)(-(n+1))))abort();
?????|?????????????}
?????|?????????????如果在首次初始化線程緩存thread_cache的時候失敗，TLS的值將會是-1,而后面會到達GetMSpace，假
?????|?????????????設這時候創建成功，那么TLS會變成-2,這樣在下次GetThreadCache的時候會重新myspace為1，這樣它
?????|?????????????不會進行Allocache的調用;如果這時創建失敗，那么會等待上一次使用的malloc_state空閑，這是TLS會
?????|?????????????保持-1, 最后會將myspace設置為0。
?在獲取的malloc_state上分配空間mspace_malloc(pms, size)
??
??
2、內存釋放流程
?nedpfree(nedpool *p, void* mem)
????|
?計算當前線程使用的cache信息
?GetThreadCache(&p, &tc,&mymspace,0)(線程對應的cache確定(分配成功)后是不會改變的)
????|
?如果內存塊比較小，而且thread_cache成功，那么將內存塊放到cache中
?threadcache_free(p, tc, mymspace, mem, memsize)
????????|->將mem轉變為threadcacheblk*,并根據mem對應內存塊的實際大小（申請者使用的部分只是
???????????真實內存塊的一部分）鏈入到thread_cache的bin成員中（有需要的話調整首尾指針）
???????????如果cache中的內存塊總大小超過特定上限時將cache中的內存返回到malloc_state中
???????????ReleaseFreeInCache->根據加入到cache的先后順序將threadcacheblk釋放到malloc_state
????????????????|
???????????RemoveCacheEntries->從cache的尾指針開始歷遍threadcacheblk鏈，將"時間"過長的塊釋放
???????????mspace_free(0, f)
????????????????|--->獲取malloc_state?
??????????????????這里需要先描述一下malloc_trunk結構的含義：
??????????????????struct malloc_chunk {
?????????????????????size_t??????????????prev_foot;?
?????????????????????size_t??????????????head;??????
?????????????????????struct malloc_chunk*fd;????????
?????????????????????struct malloc_chunk* bk;
???????????????????};
??????????????????如果當前malloc_chunk被使用，那么下一個malloc_chunk的head的pinuse位會被置位，而且它（下一個
??????????????????chunk）的prev_foot = malloc_state ^ mparams.magic.如果當前塊未被使用，那么它（當前塊）的
??????????????????prev_foot是上一個塊的大小，而且下一個塊的pinuse不會被置位，而且它（下一個chunk）的prev_foot表
??????????????????示上一塊的大小。????????????????????
???????????????????（prev_foot的最低位是用于表示該塊是否為操作系統的真正分配的內存）
???????????????????
???????????????????根據malloc_chunk的狀態進行不同的"釋放"處理:
???????????????????i.如果當前塊是從操作系統中分配，那么返還給操作系統HeapFree
???????????????????ii.[向前合并]如果當前塊的前一塊空閑，那么將這兩塊（不可能同時出現3塊同時空閑，而且但前塊在最
??????????????????????后一塊"FFN"）一起處理
??????????????????????a.如果首塊地址不同于malloc_state的dv(它的作用是保存連續空間中中間釋放的連續塊，對于先申請
?????????????????????????先釋放的應用來說，這種處理方式會有好處，因為在分配的時候會先檢查dv是否能滿足需求),那么
?????????????????????????根據塊的大小分別是"存放"到不同的地方等待復用unlink_chunk
??????????????????????b.如果下一塊正在被使用，那么修改下一塊的prev_foot和pinuse標志位
???????????????????iii.[向后合并]如果下一個塊空閑，那么將當前塊和下一塊合并處理
??????????????????????a.如果下一個塊已經是top(末尾的空閑塊)，那么更新top的指向（擴容）
??????????????????????b.如果下一個塊是dv，那么將當前塊合并到dv中
??????????????????????c.如果都不是，那么簡單地釋放下一個塊，并修改下一塊地prev_foot,pinuse
????????????????????????unlink_chunk(fm, next, nsize);
????????????????????????set_size_and_pinuse_of_free_chunk(p, psize);
???????????????????iv.如果下一塊正在使用，那么簡單修改下一塊的標志set_free_with_pinuse(p, psize,next)
???????????????????
???????????????????對于沒有合并到"空閑"空間中的塊，根據塊的大小，掛接到不同的鏈表(樹)中
???????????????????if (is_small(psize)) {
??????????????????????insert_small_chunk(fm, p, psize);
???????????????????}
???????????????????else {
??????????????????????tchunkptr tp = (tchunkptr)p;
??????????????????????insert_large_chunk(fm, tp, psize);
???????????????????}
???????????????????
???????????????????這里需要補充一下malloc_state的smallbins成員的使用：
???????????????????所有"釋放"到malloc_state的空閑內存塊會連成雙向鏈表，而smallbins中pref_foot和head是不直接使用
???????????????????的，smallbins的大小是為了訪問fd和bk兩個指針而設計的。smallbins實際上是將鏈表中按照內存塊的的
???????????????????大小分段保存鏈表的指針，方便在分配時查找。
???????????????????(理解了這個，那么insert_small_chunk的處理流程就比較簡單了)
???????????????????
???????????????????現在看看比較大的內存塊的處理思想：
???????????????????"大塊"內存的"釋放"是放到"樹中的，樹的結構根據內存塊的大小(256為單位)按照類似"哈夫曼"編碼的的
?????????????形式劃分到二叉樹中，樹的每個節點是一個雙向鏈表，保存了大小相同的塊的指針。（思路清楚了，加
?????????????入、刪除節點的代碼比較容易理解，這里不再展開）需要注意的是這里malloc_stat的treebins成員保存的是
?????????????樹（塊區域大小）的開始指針（很簡單的使用方式），它的用法和smallbins的"似結構體非結構體"的特殊用
?????????????法不同。????????????????????
???
3、擴展分配nedprealloc函數
????這個函數是nedpmalloc -> memcpy ->nedpfree的組合，這里不展開了，需要注意的是，如果新申請的空間比原來的空間小，那么是直接返回原來的空間的。?????

?現在，我們再看看內存分配最終的入口mspace_malloc的實現（對著mspace_free來看，比較容易理解）
4、內存分配邏輯
???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));
?????注意，為了提高重用成功率，這里允許使用使用比實際請求大小大一階（下一個塊對齊大小）的塊
?????????|(如果分配不成功)
?????如果請求的塊大于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()
??????????????????????????????|
????????????????????根據請求大小計算樹的根(開始查找最小匹配塊的根)
????????????????????compute_bit2idx(leastbit, i);
????????????????????v = t = *treebin_at(m, i);
??????????????????????????????|
????????????????????查找最小的匹配塊while ((t = leftmost_child(t)) != 0){...}
????????????????????并將分配后留下的空閑塊設置到dv中
????????????????????unlink_large_chunk(m, v);
????????????????????replace_dv(m, r, rsize);
??ii.如果申請大小大于MAX_REQUEST,實際上會失敗
??iii.計算塊對齊大小pad_request(bytes)，并從樹中分配
???????tmalloc_large(ms, nb)
??????????|
???????tmalloc_large和tmalloc_small的主要不同是：
???????a.tmalloc_large首先根據大小計算"最接近"的節點，并從該節點開始計算"最小的"滿足需求的節點
???????b.如果"最接近節點"為空，tmalloc_large允許擴展一階大小來尋找"最小的"滿足需求大的節點
???????(結合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.從系統空間中分配sys_alloc(ms, nb);
?????sys_alloc兼容了多個平臺分配機制，通過不同宏來開關對應的代碼段，對于Win32來說，最終會調用HeapAlloc
?????sys_alloc流程：
?????按照塊對齊和附加內存管理結構（如malloc_state）計算內存塊的大小
?????-->不同平臺下使用不同的系統函數分配"物理內存"(系統內存)，并將得到的內存
????????????|(這里主要不同宏控制的代碼，比較簡單，不展開了)
????????????|
?????如果malloc_state不含有真正的可用內存（top為空），那么初始化它init_bins,init_top
?????如果malloc_state已經初始化，那么檢查是否可以將top中剩下的空間合并到新分配的空間中（只有在可連續分配擴展的
?????情況下才有效），并重新初始化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.某一個現有的分快緊接著新分配的塊，這時需要將原來的塊合并到新分配的塊prepend_alloc
???????c.a和b都不滿足的情況下，將新塊加入到塊鏈表add_segment(m, tbase, tsize,mmap_flag)，并重新設置top
?????????|
?????????|
??????從top中分配內存
??????
??
??好了，現在我們對nedmalloc的處理思想和算法實現都比較清楚了(在*nix平臺下還有一些細節這里沒有列處理，可以查看代碼),下面概括一下：
???1、使用連續的內存分段思想管理大片的連續內存
???2、從1的內存塊中以塊對齊方式分配內存，小的內存分塊放到線程的TLS指定的cache雙向鏈表中，大的分塊放到樹結構中
???3、樹結構是以類似哈夫曼編碼的方式組織的（以塊大小編碼），每個內部節點是一個雙向鏈表
???4、外部內存申請：threadcache->線程公用內存池;釋放：線程cache鏈表->內存節點樹

總結

以上是生活随笔為你收集整理的nedmalloc结构分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。