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