合并：手寫malloc實(shí)驗(yàn)中的隱式鏈表與分離適配)
簡介這份資源圍繞《深入理解計(jì)算機(jī)系統(tǒng)》(CSAPP)中的malloc實(shí)驗(yàn)展開面向正在學(xué)習(xí)操作系統(tǒng)內(nèi)存管理、準(zhǔn)備完成課程實(shí)驗(yàn)的高校學(xué)生與自學(xué)者。內(nèi)容涵蓋內(nèi)存池管理、塊結(jié)構(gòu)設(shè)計(jì)、碎片處理、內(nèi)存對齊、free與realloc實(shí)現(xiàn)等核心知識點(diǎn)并配有實(shí)驗(yàn)分析文檔幫助讀者理解動態(tài)內(nèi)存分配的內(nèi)部機(jī)制與優(yōu)化思路。資源包共9個(gè)文件包含cpp與c源碼、可執(zhí)行程序、備份文件、演示文稿及圖片壓縮包約781KB體積輕便便于本地編譯調(diào)試與對照閱讀。目前已有963人學(xué)習(xí)下載適合作為實(shí)驗(yàn)參考與排錯對照材料。通過源碼與配套分析文檔讀者可梳理分配器設(shè)計(jì)流程、理解塊合并與碎片控制策略并借鑒性能優(yōu)化思路為獨(dú)立完成malloc實(shí)驗(yàn)提供可復(fù)用的參考框架。1. 從一次段錯誤說起為什么 malloc 實(shí)驗(yàn)值得反復(fù)拆很多人第一次跑那個(gè)內(nèi)存分配實(shí)驗(yàn)時(shí)都會遇到同一個(gè)場景代碼邏輯看著沒問題編譯也過了一運(yùn)行就給你一個(gè)冷冰冰的 Segmentation fault。你盯著mm_malloc里那幾行指針運(yùn)算心里想的是“不就是找塊空閑區(qū)域切一刀嗎”但程序就是不買賬。這個(gè)實(shí)驗(yàn)真正卡人的地方從來不是“怎么分配內(nèi)存”這個(gè)動作本身而是它逼你去面對一個(gè)平時(shí)被標(biāo)準(zhǔn)庫完全封裝起來的黑匣子——堆管理器到底怎么在一條連續(xù)的內(nèi)存里同時(shí)滿足對齊、吞吐、碎片和回收這四件互相打架的事。搞懂它價(jià)值不在于復(fù)現(xiàn)一個(gè)能跑通的分配器而在于你會第一次真正理解為什么free之后那塊內(nèi)存不會立刻還給操作系統(tǒng)為什么malloc(1)和malloc(1000)的代價(jià)可能差不多為什么一個(gè)看似無害的分配順序會讓后續(xù)所有請求全部翻車。這些問題的答案藏在隱式空閑鏈表、邊界標(biāo)記、分離適配和合并策略這幾層機(jī)制里。下面按“現(xiàn)象 → 機(jī)制 → 實(shí)現(xiàn)細(xì)節(jié)”的順序一層層拆開。2. 隱式空閑鏈表為什么空閑塊要靠頭部“自描述”2.1 一條連續(xù)內(nèi)存里怎么知道下一塊在哪堆本質(zhì)上就是一大段連續(xù)的虛擬地址空間分配器拿到它之后必須自己在這段空間里劃分出一個(gè)個(gè)塊。最樸素的做法是隱式空閑鏈表每個(gè)塊的開頭放一個(gè)頭部header記錄這個(gè)塊的大小和是否已分配塊的末尾再放一個(gè)腳部footer內(nèi)容和頭部一致。這樣整條堆就變成了一串首尾相連的塊從頭遍歷就能走完所有塊。頭部通常是一個(gè)字word32 位系統(tǒng) 4 字節(jié)64 位 8 字節(jié)。因?yàn)閴K大小總是對齊的比如 8 字節(jié)對齊所以大小的低 3 位永遠(yuǎn)是 0可以拿來存標(biāo)志位。最常見的做法是用最低位表示 allocated/free剩下高位存塊大小。這就是為什么你在代碼里會看到size ~0x7這種寫法——把標(biāo)志位抹掉拿到真實(shí)大小。// 頭部/腳部共用的讀寫宏假設(shè) 8 字節(jié)對齊 #define WSIZE 4 #define DSIZE 8 #define PACK(size, alloc) ((size) | (alloc)) // 讀一個(gè)字的無符號值 #define GET(p) (*(unsigned int *)(p)) // 寫一個(gè)字的無符號值 #define PUT(p, val) (*(unsigned int *)(p) (val)) // 從頭部/腳部取出塊大小抹掉低 3 位標(biāo)志 #define GET_SIZE(p) (GET(p) ~0x7) // 取出分配標(biāo)志最低位 #define GET_ALLOC(p) (GET(p) 0x1)這段宏是整個(gè)分配器的地基。PACK把大小和標(biāo)志位壓進(jìn)一個(gè)字GET_SIZE和GET_ALLOC再拆出來。注意~0x7抹掉的是低 3 位因?yàn)?8 字節(jié)對齊意味著低 3 位恒為 0正好騰出來放標(biāo)志。參數(shù)上WSIZE是字長DSIZE是雙字長塊的最小尺寸必須能放下頭部和腳部所以最小塊通常是 2 個(gè)字8 字節(jié)。2.2 邊界標(biāo)記合并時(shí)為什么不用從頭掃如果只有頭部釋放一個(gè)塊時(shí)想和前面的空閑塊合并就得從頭遍歷找到前驅(qū)代價(jià)是 O(n)。邊界標(biāo)記boundary tag就是為解決這個(gè)而生的在塊尾也放一份頭部信息當(dāng)腳部。這樣給定任意一個(gè)塊的指針往前讀一個(gè)字就是前一個(gè)塊的腳部立刻知道前驅(qū)是否空閑、多大。// 由當(dāng)前塊指針 bp 推出頭部、腳部、前驅(qū)、后繼 #define HDRP(bp) ((char *)(bp) - WSIZE) #define FTRP(bp) ((char *)(bp) GET_SIZE(HDRP(bp)) - DSIZE) #define NEXT_BLKP(bp) ((char *)(bp) GET_SIZE(((char *)(bp) - WSIZE))) #define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))HDRP從數(shù)據(jù)指針回退一個(gè)字拿到頭部FTRP用頭部里的大小算出腳部位置。NEXT_BLKP和PREV_BLKP分別靠當(dāng)前塊大小和前驅(qū)腳部里的大小跳到相鄰塊。這里的關(guān)鍵設(shè)計(jì)取舍是腳部多花了一個(gè)字的空間換來了 O(1) 的合并能力。對于小對象密集的場景這個(gè)空間開銷是值得的因?yàn)樗槠韼淼氖找孢h(yuǎn)大于那一個(gè)字。注意腳部只在空閑塊里是必需的已分配塊其實(shí)可以省掉腳部來節(jié)省空間但那樣合并邏輯會變復(fù)雜很多教學(xué)實(shí)現(xiàn)選擇統(tǒng)一保留。3. 放置策略與分離適配為什么“首次適配”會越跑越慢3.1 首次適配、下次適配、最佳適配的代價(jià)差異有了空閑鏈表下一個(gè)問題就是來了一個(gè)請求選哪塊空閑區(qū)域給它。首次適配first fit從頭掃遇到第一個(gè)夠大的就切下次適配next fit從上次結(jié)束的位置繼續(xù)掃最佳適配best fit掃完所有塊選最接近的。三者的差異不在單次分配而在長期碎片形態(tài)。首次適配的問題是它會在鏈表頭部不斷切割小塊留下大量小碎片導(dǎo)致后續(xù)大請求要掃很久才能找到合適塊。下次適配緩解了頭部堆積但會加速尾部大塊的消耗。最佳適配理論上碎片最少但每次都要全表掃描吞吐直接崩掉。這就是為什么真實(shí)分配器幾乎不用單一策略而是用分離適配segregated fit把空閑塊按大小分到不同鏈表里請求來了先算大小直接去對應(yīng)鏈表找。3.2 分離空閑鏈表的結(jié)構(gòu)與大小類劃分分離適配的核心是維護(hù)一個(gè)空閑鏈表數(shù)組每個(gè)槽位對應(yīng)一個(gè)大小類。比如 2^4 到 2^5 一個(gè)類2^5 到 2^6 一個(gè)類以此類推。分配時(shí)先算出請求大小對應(yīng)的類去那個(gè)鏈表找找不到就去更大的類。釋放時(shí)按大小插回對應(yīng)鏈表并嘗試與相鄰空閑塊合并。// 分離空閑鏈表每個(gè)大小類一個(gè)頭指針 #define LISTLIMIT 20 void *free_list[LISTLIMIT]; // 根據(jù)塊大小計(jì)算應(yīng)該放入哪個(gè)鏈表 int get_list_index(size_t size) { int index 0; while (index LISTLIMIT - 1 size 1) { size 1; // 每右移一次大小類翻倍 index; } return index; }get_list_index用不斷右移的方式把大小映射到對數(shù)區(qū)間。LISTLIMIT決定類的數(shù)量類越多每個(gè)鏈表越短查找越快但管理開銷越大。常見的實(shí)現(xiàn)思路是前幾個(gè)類用精確大小比如 16、32、48 字節(jié)各一個(gè)鏈表后面用區(qū)間。這樣小對象分配幾乎 O(1)大對象才需要遍歷。這里有個(gè)容易被忽略的細(xì)節(jié)插入空閑鏈表時(shí)用 LIFO 還是地址有序。LIFO 插入和刪除都是 O(1)但會讓碎片形態(tài)變差地址有序插入是 O(n)但合并時(shí)更容易找到相鄰塊。多數(shù)教學(xué)實(shí)現(xiàn)選 LIFO因?yàn)楹喜⒁呀?jīng)靠邊界標(biāo)記做到 O(1) 了不需要靠鏈表順序來找鄰居。4. 合并與分割free 之后那塊內(nèi)存到底發(fā)生了什么4.1 四種合并情況與常數(shù)時(shí)間實(shí)現(xiàn)釋放一個(gè)塊時(shí)分配器要檢查它的前驅(qū)和后繼是否空閑然后決定合并成多大的塊。一共四種情況前后都占用只和前驅(qū)合并只和后繼合并前后都合并。因?yàn)橛辛诉吔鐦?biāo)記這四種判斷和合并都能在常數(shù)時(shí)間內(nèi)完成。static void *coalesce(void *bp) { size_t prev_alloc GET_ALLOC(FTRP(PREV_BLKP(bp))); size_t next_alloc GET_ALLOC(HDRP(NEXT_BLKP(bp))); size_t size GET_SIZE(HDRP(bp)); if (prev_alloc next_alloc) { // 前后都占用 // 直接標(biāo)記為空閑插回鏈表 } else if (prev_alloc !next_alloc) { // 只合并后繼 size GET_SIZE(HDRP(NEXT_BLKP(bp))); // 更新頭部和腳部大小 } else if (!prev_alloc next_alloc) { // 只合并前驅(qū) size GET_SIZE(HDRP(PREV_BLKP(bp))); bp PREV_BLKP(bp); // 指針前移 } else { // 前后都合并 size GET_SIZE(HDRP(PREV_BLKP(bp))) GET_SIZE(HDRP(NEXT_BLKP(bp))); bp PREV_BLKP(bp); } // 統(tǒng)一寫回頭部和腳部插回空閑鏈表 return bp; }coalesce先用GET_ALLOC讀前驅(qū)腳部和后繼頭部判斷四種情況。合并時(shí)把大小累加寫回新的頭部和腳部。注意合并前驅(qū)時(shí)bp要前移到前驅(qū)位置因?yàn)楹喜⒑蟮膲K起點(diǎn)變了。這段代碼是整個(gè)分配器里最能體現(xiàn)邊界標(biāo)記價(jià)值的地方——沒有腳部PREV_BLKP就沒法 O(1) 拿到前驅(qū)大小。4.2 分割為什么不能把整塊都給出去如果找到的空閑塊比請求大很多直接整塊給出去會造成內(nèi)部碎片。所以分配器通常會分割切出請求需要的大小加上頭部腳部和對齊剩下的部分變成一個(gè)新的空閑塊。但分割不是無條件的——如果剩余部分小于最小塊尺寸就不分割整塊給出去避免產(chǎn)生無法管理的小碎片。// 分割如果剩余部分夠大切成兩塊 if (size - asize MINBLOCKSIZE) { PUT(HDRP(bp), PACK(asize, 1)); // 分配塊頭部 PUT(FTRP(bp), PACK(asize, 1)); // 分配塊腳部 void *next NEXT_BLKP(bp); PUT(HDRP(next), PACK(size - asize, 0)); // 剩余塊頭部 PUT(FTRP(next), PACK(size - asize, 0)); // 剩余塊腳部 // 把剩余塊插回空閑鏈表 }asize是請求大小向上對齊后的結(jié)果MINBLOCKSIZE是最小塊尺寸。判斷條件size - asize MINBLOCKSIZE保證剩余部分能獨(dú)立成塊。這里對齊很關(guān)鍵如果asize沒對齊后續(xù)所有塊的地址都會錯位GET_SIZE讀出來的值就是垃圾程序直接崩。這就是為什么實(shí)驗(yàn)里反復(fù)強(qiáng)調(diào)ALIGN宏。5. 避坑與排查那些讓實(shí)驗(yàn)反復(fù)翻車的細(xì)節(jié)5.1 現(xiàn)象free 之后程序崩潰報(bào)錯指向 GET_SIZE原因通常是腳部沒寫或者寫錯位置。FTRP依賴頭部里的大小來定位腳部如果頭部大小被覆蓋FTRP算出來的地址就是野指針。常見觸發(fā)點(diǎn)是在分割時(shí)只更新了頭部忘了腳部或者合并時(shí)腳部大小沒同步。解決每次修改塊大小后強(qiáng)制同時(shí)寫頭部和腳部并且用PACK統(tǒng)一打包。可以在coalesce和split之后加斷言檢查GET_SIZE(HDRP(bp)) GET_SIZE(FTRP(bp))。5.2 現(xiàn)象分配器能跑但吞吐隨請求數(shù)線性下降原因多半是空閑鏈表退化成一條長鏈每次分配都要遍歷大量節(jié)點(diǎn)。這通常是因?yàn)榇笮☆悇澐痔只蛘哚尫艜r(shí)沒有正確插回對應(yīng)鏈表全堆在一個(gè)類里。解決檢查get_list_index的映射邏輯確認(rèn)小對象落在精確類里?？梢栽诿看畏峙浜蟠蛴「麈湵黹L度如果某個(gè)鏈表長度持續(xù)增長說明該類劃分有問題。5.3 現(xiàn)象兩個(gè)空閑塊明明相鄰卻沒有合并原因是合并判斷讀錯了鄰居的分配標(biāo)志。PREV_BLKP依賴前驅(qū)腳部如果前驅(qū)是已分配塊且沒有腳部讀出來的就是數(shù)據(jù)區(qū)內(nèi)容標(biāo)志位隨機(jī)。解決統(tǒng)一所有塊都保留腳部或者至少保證空閑塊腳部一定有效。檢查coalesce里GET_ALLOC的讀取位置前驅(qū)讀腳部后繼讀頭部不能搞反。5.4 現(xiàn)象對齊后請求大小算錯偶爾越界原因是ALIGN宏沒有考慮頭部和腳部的開銷只對齊了請求本身。實(shí)際需要的大小是ALIGN(req) DSIZE再向上取到最小塊尺寸。解決把a(bǔ)size的計(jì)算封裝成一個(gè)函數(shù)先對齊請求再加頭部腳部最后和MINBLOCKSIZE取大。每次分配前打印asize和實(shí)際塊大小對比。5.5 現(xiàn)象重分配realloc后數(shù)據(jù)錯亂原因是realloc在塊變大時(shí)直接原地?cái)U(kuò)展覆蓋了后繼塊的數(shù)據(jù)。正確做法是如果后繼空閑且合并后夠大就合并否則分配新塊、拷貝、釋放舊塊。解決不要圖省事在realloc里直接改頭部大小。走完整的mallocmemcpyfree路徑雖然慢一點(diǎn)但不會踩內(nèi)存。6. 從實(shí)驗(yàn)到真實(shí)分配器設(shè)計(jì)取舍的邊界在哪把隱式鏈表、邊界標(biāo)記、分離適配和合并策略拼起來你已經(jīng)能得到一個(gè)能跑通實(shí)驗(yàn)的分配器。但它和真實(shí)生產(chǎn)環(huán)境里的分配器之間還隔著幾層關(guān)鍵的取舍。第一層是空間與時(shí)間的權(quán)衡。邊界標(biāo)記用腳部換 O(1) 合并分離鏈表用更多頭指針換更短查找路徑這些都是拿空間買時(shí)間。真實(shí)分配器會根據(jù)對象大小動態(tài)切換策略小對象走線程緩存tcache幾乎無鎖中等對象走分離鏈表大對象直接 mmap繞過堆管理。這個(gè)分層思路在實(shí)驗(yàn)里不會要求你實(shí)現(xiàn)但理解它你就明白為什么malloc(16)和malloc(1MB)的底層路徑完全不同。第二層是碎片與吞吐的權(quán)衡。首次適配吞吐高但碎片多最佳適配碎片少但吞吐低。真實(shí)分配器通常用近似最佳適配在大小類里找第一個(gè)夠大的找不到就去下一個(gè)類。這樣既避免了全表掃描又不會像純首次適配那樣在頭部堆積碎片。你可以把實(shí)驗(yàn)里的find_fit改成按類查找觀察吞吐和碎片形態(tài)的變化。第三層是并發(fā)與一致性的權(quán)衡。實(shí)驗(yàn)通常是單線程的但真實(shí)分配器必須處理多線程同時(shí)malloc。最簡單的做法是加一把大鎖但吞吐會崩。進(jìn)階做法是每個(gè)線程一個(gè)獨(dú)立堆a(bǔ)rena配合線程緩存只在跨線程釋放時(shí)才需要同步。這個(gè)思路的代價(jià)是內(nèi)存占用上升因?yàn)槊總€(gè) arena 都要預(yù)留空間。驗(yàn)證你的實(shí)現(xiàn)是否真的理解了這些取舍有個(gè)很直接的方法構(gòu)造一組分配釋放序列讓總請求量剛好超過堆容量觀察你的分配器是返回 NULL 還是能通過合并騰出空間。如果返回 NULL 但實(shí)際空閑總量夠說明合并或分割策略有漏洞。再構(gòu)造一組交替分配大小對象的序列統(tǒng)計(jì)最終空閑塊的數(shù)量和最大空閑塊尺寸這兩個(gè)數(shù)字直接反映碎片程度。我自己的習(xí)慣是每次改完coalesce或find_fit都強(qiáng)制跑一遍邊界用例全分配、全釋放、交替分配釋放、大塊夾小塊。這四組跑通基本不會再有玄學(xué)崩潰。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取 從段錯誤到O(1)合并：手寫malloc實(shí)驗(yàn)中的隱式鏈表與分離適配
簡介這份資源圍繞《深入理解計(jì)算機(jī)系統(tǒng)》(CSAPP)中的malloc實(shí)驗(yàn)展開面向正在學(xué)習(xí)操作系統(tǒng)內(nèi)存管理、準(zhǔn)備完成課程實(shí)驗(yàn)的高校學(xué)生與自學(xué)者。內(nèi)容涵蓋內(nèi)存池管理、塊結(jié)構(gòu)設(shè)計(jì)、碎片處理、內(nèi)存對齊、free與realloc實(shí)現(xiàn)等核心知識點(diǎn)并配有實(shí)驗(yàn)分析文檔幫助讀者理解動態(tài)內(nèi)存分配的內(nèi)部機(jī)制與優(yōu)化思路。資源包共9個(gè)文件包含cpp與c源碼、可執(zhí)行程序、備份文件、演示文稿及圖片壓縮包約781KB體積輕便便于本地編譯調(diào)試與對照閱讀。目前已有963人學(xué)習(xí)下載適合作為實(shí)驗(yàn)參考與排錯對照材料。通過源碼與配套分析文檔讀者可梳理分配器設(shè)計(jì)流程、理解塊合并與碎片控制策略并借鑒性能優(yōu)化思路為獨(dú)立完成malloc實(shí)驗(yàn)提供可復(fù)用的參考框架。1. 從一次段錯誤說起為什么 malloc 實(shí)驗(yàn)值得反復(fù)拆很多人第一次跑那個(gè)內(nèi)存分配實(shí)驗(yàn)時(shí)都會遇到同一個(gè)場景代碼邏輯看著沒問題編譯也過了一運(yùn)行就給你一個(gè)冷冰冰的 Segmentation fault。你盯著mm_malloc里那幾行指針運(yùn)算心里想的是“不就是找塊空閑區(qū)域切一刀嗎”但程序就是不買賬。這個(gè)實(shí)驗(yàn)真正卡人的地方從來不是“怎么分配內(nèi)存”這個(gè)動作本身而是它逼你去面對一個(gè)平時(shí)被標(biāo)準(zhǔn)庫完全封裝起來的黑匣子——堆管理器到底怎么在一條連續(xù)的內(nèi)存里同時(shí)滿足對齊、吞吐、碎片和回收這四件互相打架的事。搞懂它價(jià)值不在于復(fù)現(xiàn)一個(gè)能跑通的分配器而在于你會第一次真正理解為什么free之后那塊內(nèi)存不會立刻還給操作系統(tǒng)為什么malloc(1)和malloc(1000)的代價(jià)可能差不多為什么一個(gè)看似無害的分配順序會讓后續(xù)所有請求全部翻車。這些問題的答案藏在隱式空閑鏈表、邊界標(biāo)記、分離適配和合并策略這幾層機(jī)制里。下面按“現(xiàn)象 → 機(jī)制 → 實(shí)現(xiàn)細(xì)節(jié)”的順序一層層拆開。2. 隱式空閑鏈表為什么空閑塊要靠頭部“自描述”2.1 一條連續(xù)內(nèi)存里怎么知道下一塊在哪堆本質(zhì)上就是一大段連續(xù)的虛擬地址空間分配器拿到它之后必須自己在這段空間里劃分出一個(gè)個(gè)塊。最樸素的做法是隱式空閑鏈表每個(gè)塊的開頭放一個(gè)頭部header記錄這個(gè)塊的大小和是否已分配塊的末尾再放一個(gè)腳部footer內(nèi)容和頭部一致。這樣整條堆就變成了一串首尾相連的塊從頭遍歷就能走完所有塊。頭部通常是一個(gè)字word32 位系統(tǒng) 4 字節(jié)64 位 8 字節(jié)。因?yàn)閴K大小總是對齊的比如 8 字節(jié)對齊所以大小的低 3 位永遠(yuǎn)是 0可以拿來存標(biāo)志位。最常見的做法是用最低位表示 allocated/free剩下高位存塊大小。這就是為什么你在代碼里會看到size ~0x7這種寫法——把標(biāo)志位抹掉拿到真實(shí)大小。// 頭部/腳部共用的讀寫宏假設(shè) 8 字節(jié)對齊 #define WSIZE 4 #define DSIZE 8 #define PACK(size, alloc) ((size) | (alloc)) // 讀一個(gè)字的無符號值 #define GET(p) (*(unsigned int *)(p)) // 寫一個(gè)字的無符號值 #define PUT(p, val) (*(unsigned int *)(p) (val)) // 從頭部/腳部取出塊大小抹掉低 3 位標(biāo)志 #define GET_SIZE(p) (GET(p) ~0x7) // 取出分配標(biāo)志最低位 #define GET_ALLOC(p) (GET(p) 0x1)這段宏是整個(gè)分配器的地基。PACK把大小和標(biāo)志位壓進(jìn)一個(gè)字GET_SIZE和GET_ALLOC再拆出來。注意~0x7抹掉的是低 3 位因?yàn)?8 字節(jié)對齊意味著低 3 位恒為 0正好騰出來放標(biāo)志。參數(shù)上WSIZE是字長DSIZE是雙字長塊的最小尺寸必須能放下頭部和腳部所以最小塊通常是 2 個(gè)字8 字節(jié)。2.2 邊界標(biāo)記合并時(shí)為什么不用從頭掃如果只有頭部釋放一個(gè)塊時(shí)想和前面的空閑塊合并就得從頭遍歷找到前驅(qū)代價(jià)是 O(n)。邊界標(biāo)記boundary tag就是為解決這個(gè)而生的在塊尾也放一份頭部信息當(dāng)腳部。這樣給定任意一個(gè)塊的指針往前讀一個(gè)字就是前一個(gè)塊的腳部立刻知道前驅(qū)是否空閑、多大。// 由當(dāng)前塊指針 bp 推出頭部、腳部、前驅(qū)、后繼 #define HDRP(bp) ((char *)(bp) - WSIZE) #define FTRP(bp) ((char *)(bp) GET_SIZE(HDRP(bp)) - DSIZE) #define NEXT_BLKP(bp) ((char *)(bp) GET_SIZE(((char *)(bp) - WSIZE))) #define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))HDRP從數(shù)據(jù)指針回退一個(gè)字拿到頭部FTRP用頭部里的大小算出腳部位置。NEXT_BLKP和PREV_BLKP分別靠當(dāng)前塊大小和前驅(qū)腳部里的大小跳到相鄰塊。這里的關(guān)鍵設(shè)計(jì)取舍是腳部多花了一個(gè)字的空間換來了 O(1) 的合并能力。對于小對象密集的場景這個(gè)空間開銷是值得的因?yàn)樗槠韼淼氖找孢h(yuǎn)大于那一個(gè)字。注意腳部只在空閑塊里是必需的已分配塊其實(shí)可以省掉腳部來節(jié)省空間但那樣合并邏輯會變復(fù)雜很多教學(xué)實(shí)現(xiàn)選擇統(tǒng)一保留。3. 放置策略與分離適配為什么“首次適配”會越跑越慢3.1 首次適配、下次適配、最佳適配的代價(jià)差異有了空閑鏈表下一個(gè)問題就是來了一個(gè)請求選哪塊空閑區(qū)域給它。首次適配first fit從頭掃遇到第一個(gè)夠大的就切下次適配next fit從上次結(jié)束的位置繼續(xù)掃最佳適配best fit掃完所有塊選最接近的。三者的差異不在單次分配而在長期碎片形態(tài)。首次適配的問題是它會在鏈表頭部不斷切割小塊留下大量小碎片導(dǎo)致后續(xù)大請求要掃很久才能找到合適塊。下次適配緩解了頭部堆積但會加速尾部大塊的消耗。最佳適配理論上碎片最少但每次都要全表掃描吞吐直接崩掉。這就是為什么真實(shí)分配器幾乎不用單一策略而是用分離適配segregated fit把空閑塊按大小分到不同鏈表里請求來了先算大小直接去對應(yīng)鏈表找。3.2 分離空閑鏈表的結(jié)構(gòu)與大小類劃分分離適配的核心是維護(hù)一個(gè)空閑鏈表數(shù)組每個(gè)槽位對應(yīng)一個(gè)大小類。比如 2^4 到 2^5 一個(gè)類2^5 到 2^6 一個(gè)類以此類推。分配時(shí)先算出請求大小對應(yīng)的類去那個(gè)鏈表找找不到就去更大的類。釋放時(shí)按大小插回對應(yīng)鏈表并嘗試與相鄰空閑塊合并。// 分離空閑鏈表每個(gè)大小類一個(gè)頭指針 #define LISTLIMIT 20 void *free_list[LISTLIMIT]; // 根據(jù)塊大小計(jì)算應(yīng)該放入哪個(gè)鏈表 int get_list_index(size_t size) { int index 0; while (index LISTLIMIT - 1 size 1) { size 1; // 每右移一次大小類翻倍 index; } return index; }get_list_index用不斷右移的方式把大小映射到對數(shù)區(qū)間。LISTLIMIT決定類的數(shù)量類越多每個(gè)鏈表越短查找越快但管理開銷越大。常見的實(shí)現(xiàn)思路是前幾個(gè)類用精確大小比如 16、32、48 字節(jié)各一個(gè)鏈表后面用區(qū)間。這樣小對象分配幾乎 O(1)大對象才需要遍歷。這里有個(gè)容易被忽略的細(xì)節(jié)插入空閑鏈表時(shí)用 LIFO 還是地址有序。LIFO 插入和刪除都是 O(1)但會讓碎片形態(tài)變差地址有序插入是 O(n)但合并時(shí)更容易找到相鄰塊。多數(shù)教學(xué)實(shí)現(xiàn)選 LIFO因?yàn)楹喜⒁呀?jīng)靠邊界標(biāo)記做到 O(1) 了不需要靠鏈表順序來找鄰居。4. 合并與分割free 之后那塊內(nèi)存到底發(fā)生了什么4.1 四種合并情況與常數(shù)時(shí)間實(shí)現(xiàn)釋放一個(gè)塊時(shí)分配器要檢查它的前驅(qū)和后繼是否空閑然后決定合并成多大的塊。一共四種情況前后都占用只和前驅(qū)合并只和后繼合并前后都合并。因?yàn)橛辛诉吔鐦?biāo)記這四種判斷和合并都能在常數(shù)時(shí)間內(nèi)完成。static void *coalesce(void *bp) { size_t prev_alloc GET_ALLOC(FTRP(PREV_BLKP(bp))); size_t next_alloc GET_ALLOC(HDRP(NEXT_BLKP(bp))); size_t size GET_SIZE(HDRP(bp)); if (prev_alloc next_alloc) { // 前后都占用 // 直接標(biāo)記為空閑插回鏈表 } else if (prev_alloc !next_alloc) { // 只合并后繼 size GET_SIZE(HDRP(NEXT_BLKP(bp))); // 更新頭部和腳部大小 } else if (!prev_alloc next_alloc) { // 只合并前驅(qū) size GET_SIZE(HDRP(PREV_BLKP(bp))); bp PREV_BLKP(bp); // 指針前移 } else { // 前后都合并 size GET_SIZE(HDRP(PREV_BLKP(bp))) GET_SIZE(HDRP(NEXT_BLKP(bp))); bp PREV_BLKP(bp); } // 統(tǒng)一寫回頭部和腳部插回空閑鏈表 return bp; }coalesce先用GET_ALLOC讀前驅(qū)腳部和后繼頭部判斷四種情況。合并時(shí)把大小累加寫回新的頭部和腳部。注意合并前驅(qū)時(shí)bp要前移到前驅(qū)位置因?yàn)楹喜⒑蟮膲K起點(diǎn)變了。這段代碼是整個(gè)分配器里最能體現(xiàn)邊界標(biāo)記價(jià)值的地方——沒有腳部PREV_BLKP就沒法 O(1) 拿到前驅(qū)大小。4.2 分割為什么不能把整塊都給出去如果找到的空閑塊比請求大很多直接整塊給出去會造成內(nèi)部碎片。所以分配器通常會分割切出請求需要的大小加上頭部腳部和對齊剩下的部分變成一個(gè)新的空閑塊。但分割不是無條件的——如果剩余部分小于最小塊尺寸就不分割整塊給出去避免產(chǎn)生無法管理的小碎片。// 分割如果剩余部分夠大切成兩塊 if (size - asize MINBLOCKSIZE) { PUT(HDRP(bp), PACK(asize, 1)); // 分配塊頭部 PUT(FTRP(bp), PACK(asize, 1)); // 分配塊腳部 void *next NEXT_BLKP(bp); PUT(HDRP(next), PACK(size - asize, 0)); // 剩余塊頭部 PUT(FTRP(next), PACK(size - asize, 0)); // 剩余塊腳部 // 把剩余塊插回空閑鏈表 }asize是請求大小向上對齊后的結(jié)果MINBLOCKSIZE是最小塊尺寸。判斷條件size - asize MINBLOCKSIZE保證剩余部分能獨(dú)立成塊。這里對齊很關(guān)鍵如果asize沒對齊后續(xù)所有塊的地址都會錯位GET_SIZE讀出來的值就是垃圾程序直接崩。這就是為什么實(shí)驗(yàn)里反復(fù)強(qiáng)調(diào)ALIGN宏。5. 避坑與排查那些讓實(shí)驗(yàn)反復(fù)翻車的細(xì)節(jié)5.1 現(xiàn)象free 之后程序崩潰報(bào)錯指向 GET_SIZE原因通常是腳部沒寫或者寫錯位置。FTRP依賴頭部里的大小來定位腳部如果頭部大小被覆蓋FTRP算出來的地址就是野指針。常見觸發(fā)點(diǎn)是在分割時(shí)只更新了頭部忘了腳部或者合并時(shí)腳部大小沒同步。解決每次修改塊大小后強(qiáng)制同時(shí)寫頭部和腳部并且用PACK統(tǒng)一打包。可以在coalesce和split之后加斷言檢查GET_SIZE(HDRP(bp)) GET_SIZE(FTRP(bp))。5.2 現(xiàn)象分配器能跑但吞吐隨請求數(shù)線性下降原因多半是空閑鏈表退化成一條長鏈每次分配都要遍歷大量節(jié)點(diǎn)。這通常是因?yàn)榇笮☆悇澐痔只蛘哚尫艜r(shí)沒有正確插回對應(yīng)鏈表全堆在一個(gè)類里。解決檢查get_list_index的映射邏輯確認(rèn)小對象落在精確類里?？梢栽诿看畏峙浜蟠蛴「麈湵黹L度如果某個(gè)鏈表長度持續(xù)增長說明該類劃分有問題。5.3 現(xiàn)象兩個(gè)空閑塊明明相鄰卻沒有合并原因是合并判斷讀錯了鄰居的分配標(biāo)志。PREV_BLKP依賴前驅(qū)腳部如果前驅(qū)是已分配塊且沒有腳部讀出來的就是數(shù)據(jù)區(qū)內(nèi)容標(biāo)志位隨機(jī)。解決統(tǒng)一所有塊都保留腳部或者至少保證空閑塊腳部一定有效。檢查coalesce里GET_ALLOC的讀取位置前驅(qū)讀腳部后繼讀頭部不能搞反。5.4 現(xiàn)象對齊后請求大小算錯偶爾越界原因是ALIGN宏沒有考慮頭部和腳部的開銷只對齊了請求本身。實(shí)際需要的大小是ALIGN(req) DSIZE再向上取到最小塊尺寸。解決把a(bǔ)size的計(jì)算封裝成一個(gè)函數(shù)先對齊請求再加頭部腳部最后和MINBLOCKSIZE取大。每次分配前打印asize和實(shí)際塊大小對比。5.5 現(xiàn)象重分配realloc后數(shù)據(jù)錯亂原因是realloc在塊變大時(shí)直接原地?cái)U(kuò)展覆蓋了后繼塊的數(shù)據(jù)。正確做法是如果后繼空閑且合并后夠大就合并否則分配新塊、拷貝、釋放舊塊。解決不要圖省事在realloc里直接改頭部大小。走完整的mallocmemcpyfree路徑雖然慢一點(diǎn)但不會踩內(nèi)存。6. 從實(shí)驗(yàn)到真實(shí)分配器設(shè)計(jì)取舍的邊界在哪把隱式鏈表、邊界標(biāo)記、分離適配和合并策略拼起來你已經(jīng)能得到一個(gè)能跑通實(shí)驗(yàn)的分配器。但它和真實(shí)生產(chǎn)環(huán)境里的分配器之間還隔著幾層關(guān)鍵的取舍。第一層是空間與時(shí)間的權(quán)衡。邊界標(biāo)記用腳部換 O(1) 合并分離鏈表用更多頭指針換更短查找路徑這些都是拿空間買時(shí)間。真實(shí)分配器會根據(jù)對象大小動態(tài)切換策略小對象走線程緩存tcache幾乎無鎖中等對象走分離鏈表大對象直接 mmap繞過堆管理。這個(gè)分層思路在實(shí)驗(yàn)里不會要求你實(shí)現(xiàn)但理解它你就明白為什么malloc(16)和malloc(1MB)的底層路徑完全不同。第二層是碎片與吞吐的權(quán)衡。首次適配吞吐高但碎片多最佳適配碎片少但吞吐低。真實(shí)分配器通常用近似最佳適配在大小類里找第一個(gè)夠大的找不到就去下一個(gè)類。這樣既避免了全表掃描又不會像純首次適配那樣在頭部堆積碎片。你可以把實(shí)驗(yàn)里的find_fit改成按類查找觀察吞吐和碎片形態(tài)的變化。第三層是并發(fā)與一致性的權(quán)衡。實(shí)驗(yàn)通常是單線程的但真實(shí)分配器必須處理多線程同時(shí)malloc。最簡單的做法是加一把大鎖但吞吐會崩。進(jìn)階做法是每個(gè)線程一個(gè)獨(dú)立堆a(bǔ)rena配合線程緩存只在跨線程釋放時(shí)才需要同步。這個(gè)思路的代價(jià)是內(nèi)存占用上升因?yàn)槊總€(gè) arena 都要預(yù)留空間。驗(yàn)證你的實(shí)現(xiàn)是否真的理解了這些取舍有個(gè)很直接的方法構(gòu)造一組分配釋放序列讓總請求量剛好超過堆容量觀察你的分配器是返回 NULL 還是能通過合并騰出空間。如果返回 NULL 但實(shí)際空閑總量夠說明合并或分割策略有漏洞。再構(gòu)造一組交替分配大小對象的序列統(tǒng)計(jì)最終空閑塊的數(shù)量和最大空閑塊尺寸這兩個(gè)數(shù)字直接反映碎片程度。我自己的習(xí)慣是每次改完coalesce或find_fit都強(qiáng)制跑一遍邊界用例全分配、全釋放、交替分配釋放、大塊夾小塊。這四組跑通基本不會再有玄學(xué)崩潰。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取