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