?

7.2? 內(nèi)存池的核心邏輯—內(nèi)存棧

在內(nèi)存池中，首先要有一個內(nèi)存塊管理的核心模塊，來負責所有內(nèi)存塊的申請、分發(fā)、回收和釋放工作，經(jīng)過設(shè)計，筆者是使用“棧”來完成的這個模塊，因此，筆者將其定名為“內(nèi)存棧”（Memory Stack）。下面我們將詳細討論其設(shè)計細節(jié)。

7.2.1? 內(nèi)存管理的數(shù)學模型

內(nèi)存塊如果要提升可重用性，必須對內(nèi)存塊尺寸進行取模，否則的話，很容易因為幾個Bytes的偏差，導致內(nèi)存塊無法重用，被迫向系統(tǒng)頻繁申請新的內(nèi)存空間，那意義就不大了。

取模的主要目的，是減少內(nèi)存塊的種類，以有限幾個尺寸的內(nèi)存塊，應對絕大多數(shù)內(nèi)存使用要求。

筆者看過STL的內(nèi)存管理模塊源代碼，對其內(nèi)存塊的取模機制深表欽佩，因此，在筆者自己的內(nèi)存池中，也是按照這種方式取模。

提示：32位系統(tǒng)，有個字節(jié)對齊問題，即一個程序變量單元，如一個結(jié)構(gòu)體，一個內(nèi)存塊，如果其尺寸不是4Bytes的整倍數(shù)，操作系統(tǒng)會按照比它大的整倍數(shù)分配內(nèi)存，這其實也是操作系統(tǒng)在取模。比如我們的一個結(jié)構(gòu)體為7Bytes，操作系統(tǒng)分配時會分配8Bytes，一個14Bytes的內(nèi)存塊，操作系統(tǒng)會分配16Bytes，這主要是簡化內(nèi)存地址運算，以一定的內(nèi)存消耗，來提升程序的運行速度。

我們對內(nèi)存的取模也是這個原理，當然，我們不可能像操作系統(tǒng)那樣，機械地以4Bytes為模數(shù)，那樣，內(nèi)存塊種類還是太多，管理起來壓力很大，內(nèi)存池的效率也不高。

筆者仿造STL的取模方式，在內(nèi)存池中按照如下邏輯取模，簡單說來，就是從16Bytes開始，以兩倍方式遞增模數(shù)。直到4G內(nèi)存為止。當然，實際使用時，超過1M的內(nèi)存塊，一般應用很少，即使有，基本上也屬于應用程序永久緩沖區(qū)，很少會中途頻繁釋放，因此，筆者的內(nèi)存池管理，一般模數(shù)為16Bytes~1M即可。

序號	內(nèi)存塊大小模數(shù)（Bytes）	應對申請需求（Bytes）
1	16	1~16
2	32	17~32
3	64	33~64
4	128	65~128
5	256	129~256
6	512	257~512
7	1k	513~1k
8	2k	1k+1~2k
9	4k	2k+1~4k
10	8k	4k+1~8k
11	16k	8k+1~16k
12	32k	16k+1~32k
13	64k	32k+1~64k
14	128k	64k+1~128k
15	256k	128k+1~256k
16	512k	256k+1~512k
17	1M	512k+1~1M

圖7.1：內(nèi)存模數(shù)表

?

如表7.1所示，內(nèi)存池實際上是一個樹型數(shù)據(jù)結(jié)構(gòu)在管理，每一種類型的內(nèi)存塊，構(gòu)成一個鏈表，形成樹的“右枝”，而所有右枝的鏈頭，又是以一個鏈表在管理，形成樹的“左枝”。請注意，這并不是二叉樹，還是一顆普通的樹結(jié)構(gòu)。如下圖所示：

? 圖7.2：內(nèi)存管理樹模型

?

?

我們舉個例子，當應用程序申請一塊57Bytes的內(nèi)存塊，程序邏輯會沿著樹的左枝，從頭到尾比對，首先是16Bytes的的管理鏈，由于57>16，因此，無法在這根右枝進行管理，因此繼續(xù)往下，32Bytes也不行，64Bytes，比57要大，可以使用，因此，就在64Bytes這根右枝實現(xiàn)內(nèi)存塊管理。

管理原則：分配時，首先在合適的右枝尋找可用的內(nèi)存塊，如果有，則直接分配給應用程序重用該塊，如果沒有，則向系統(tǒng)申請一塊64Bytes的內(nèi)存塊，分配給應用程序使用。而當應用程序釋放時，內(nèi)存塊本身是64Bytes的，因此，可以直接掛回到64Bytes這根右枝，等待下次重用。

提示：這里面有一個隱含的推論，如果一個應用程序，需要一塊57Bytes的內(nèi)存塊，那么，我們分配一塊比它大的內(nèi)存塊，比如64Bytes的內(nèi)存塊，是完全可以的，應用程序不關(guān)心自己實際獲得的內(nèi)存塊大小，同時，這種稍稍超大的分配機制，也不回引發(fā)任何的內(nèi)存溢出bug，反而更安全，因此，這種內(nèi)存取模分配的思路，是完全可行的。

7.2.2? 管理模型的優(yōu)化

雖然上文我們討論的是以鏈表方式管理，不過，在實做中，筆者發(fā)現(xiàn)一個問題，即鏈表效率不高，原因很簡單，筆者的鏈表是以隊列方式管理，每次從右枝取出內(nèi)存塊，是從鏈表頭取出，但釋放時，將內(nèi)存塊推回右枝，需要循環(huán)遍歷到鏈表尾部進行掛鏈操作。這在高速的內(nèi)存申請和釋放時，會嚴重影響鏈表的效率。

筆者經(jīng)過思考，發(fā)現(xiàn)一個問題，當一個內(nèi)存塊被推回一個右枝，其實已經(jīng)是無屬性的，比如，64Bytes這個右枝上，掛的都是64Bytes大小的內(nèi)存塊，應用程序申請時，使用任何一塊都是可以的，無需考慮這塊是在鏈頭還是鏈尾，同時，申請的內(nèi)存塊，都是需要初始化的，應用程序也不關(guān)心這塊內(nèi)存塊是否剛剛被使用完，還是已經(jīng)空閑很久了。筆者理解這個內(nèi)存樹的右枝，其實已經(jīng)是前文所說的“被動池”邏輯了。

我們知道，在“推”入和“提取”這個邏輯上，“棧”的效率遠高于“隊列”，通常我們不使用棧的唯一原因，主要是棧是“后進先出”邏輯，而隊列是“先進先出”邏輯，而我們常見的應用模型，一般都有數(shù)據(jù)順序要求，因此，隊列的使用場合，遠多于棧結(jié)構(gòu)。

但此處既然我們已經(jīng)明確論證了，內(nèi)存塊無順序需求，那么，我們完全可以使用棧模型來管理內(nèi)存樹的右枝，以提高效率。

這在實做時非常簡單，當應用程序釋放一塊內(nèi)存，我們需要推回右枝時，直接將其掛接到鏈頭即可，取消了無意義的循環(huán)遍歷鏈尾的操作，雖然，下次申請時，最后釋放的一塊內(nèi)存會被最先分配使用，但這又有什么關(guān)系呢？

這個優(yōu)化看似很小，但實做時威力驚人，經(jīng)筆者測試，內(nèi)存塊的申請和釋放吞吐量，在“隊列”管理方式下，每秒僅5萬次左右，一旦使用“棧”方式管理，迅速提升到40~50萬次，提升了整整一個數(shù)量級。

正因為如此，筆者才將內(nèi)存池最核心的內(nèi)存管理模塊，定名為內(nèi)存棧（Memory Stack）。

提示：在進行程序開發(fā)時，很多時候，需要針對業(yè)務(wù)需求進行分析，實現(xiàn)針對性優(yōu)化，很多時候，很小的一點優(yōu)化，都可以大幅度提升程序的性能。反過來說，通用的優(yōu)化其實不存在，只有深刻理解了業(yè)務(wù)需求之后，才有可能實施有效的優(yōu)化方案。

提示：原則上，程序開發(fā)應該遵循“先實現(xiàn)，后優(yōu)化”的原則，筆者常說的“先解決有無問題，再解決好壞問題”，也是這個意思，本章在此先討論優(yōu)化，是因為筆者這個內(nèi)存池在實踐中已經(jīng)經(jīng)過了多次優(yōu)化，有條件討論此事，并不意味著可以再程序?qū)崿F(xiàn)前實施優(yōu)化，請各位讀者關(guān)注這個細節(jié)。事實上，本書展示的內(nèi)存池，已經(jīng)是筆者第19個版本，中間經(jīng)過了十幾次優(yōu)化的結(jié)果。

7.2.3? 關(guān)于鏈表管理的思考

討論完上面的問題，我們再來討論一下基本數(shù)據(jù)結(jié)構(gòu)管理的問題。我們知道，雖然我們的內(nèi)存池是樹結(jié)構(gòu)管理，但具體到每個右枝上，還是鏈表，而鏈表元素是動態(tài)申請的，依賴內(nèi)部指向下一元素的指針，實現(xiàn)鏈接關(guān)系。

具體到我們內(nèi)存塊管理上，我們發(fā)現(xiàn)一個基本的鏈表元素，至少需要定義成如下形式：

typedef struct _CHAIN_TOKEN_ { ??? struct _CHAIN_TOKEN_* m_pNext;? //指向下一鏈表元素的指針 ??? char* m_pBuffer;??????????????? //指向真實內(nèi)存塊的指針 }SChainToken;

這就帶來一個問題，鏈表的元素，應該分為兩部分，一部分是實現(xiàn)鏈表管理的邏輯數(shù)據(jù)，如：m_pNext，另一部分，是業(yè)務(wù)相關(guān)的數(shù)據(jù)，如m_pBuffer，這樣的數(shù)據(jù)結(jié)構(gòu)，造成程序開發(fā)非常麻煩。

比如一個簡單的內(nèi)存申請和釋放動作，以上述數(shù)據(jù)結(jié)構(gòu)管理，其基本邏輯如下：

內(nèi)存申請： 1、檢查鏈表有無空閑內(nèi)存單元 2、如果有，提取其中的m_pBuffer，準備返回給應用程序使用 3、從鏈表中卸載已經(jīng)為空的鏈表管理元素，直接釋放給系統(tǒng)（注意，無管控的內(nèi)存塊釋放，內(nèi)存碎片的隱患） 內(nèi)存釋放： 1、尋找合適的鏈，準備做掛鏈操作 2、申請一個鏈表管理單元，將內(nèi)存塊的指針放入其中的m_pBuffer 3、執(zhí)行掛鏈操作，填充m_pBext指針

大家注意到?jīng)]有，我們本意是內(nèi)存管理，減小內(nèi)存碎片，但是，為了實現(xiàn)鏈表的管理，反而中間引入了一個多余的鏈表單元申請和釋放邏輯，反而增加了內(nèi)存碎片的產(chǎn)生可能，這種方法當然不可取。

另外，這里還有一個隱患，我們分配給應用程序的內(nèi)存塊，其中所有的內(nèi)存單元，都是對應用程序透明的，應用程序可以任意使用，這說明，這塊內(nèi)存塊中，沒有存儲任何關(guān)于內(nèi)存塊尺寸的信息，當應用程序釋放指針時，我們面臨一個問題，就是怎么確定這根指針指向的內(nèi)存塊，究竟有多大，應該掛在哪個右枝上，等待下次使用。

這個問題不解決，上述的內(nèi)存釋放邏輯的第一步，尋找合適的鏈，根本無法完成。

因此，為了記錄內(nèi)存塊的尺寸信息，我們必須內(nèi)部再建立一個映射表，將我們管理的每根內(nèi)存塊指針，在申請時的具體尺寸，都記錄下來，等釋放時，需要根據(jù)指針，逆查其對應的長度數(shù)據(jù)，才能完成功能。

筆者做開發(fā)有個原則：“簡單的程序才是好程序”，上述邏輯雖然最終也能完成功能，但無論怎么看，都太復雜了，不是好的解決方案。

為此，筆者經(jīng)過了較長時間的思考，發(fā)現(xiàn)所有問題的核心焦點，無非只有兩條：

1、如何使鏈表的管理數(shù)據(jù)，不要發(fā)生新的動態(tài)內(nèi)存分配。 2、如何使分配出去的指針，能夠攜帶相關(guān)的緩沖區(qū)尺寸信息，避免額外的存儲和查詢壓力。

經(jīng)過分析，筆者突發(fā)奇想，既然我們內(nèi)存池管理的就是內(nèi)存塊，就有存儲能力，為什么我們不能利用內(nèi)存塊做一點自己的管理數(shù)據(jù)存儲呢？大不了這個內(nèi)存塊實際可用內(nèi)存，比我們從操作系統(tǒng)申請的，要小一點，但這又有什么關(guān)系呢？應用程序需要的只是自己需要的內(nèi)存塊，這個內(nèi)存塊原來有多大？能給應用程序使用的又有多大？應用程序并不關(guān)心。

經(jīng)過考慮，筆者做了如下一個結(jié)構(gòu)體：

typedef struct _TONY_MEM_BLOCK_HEAD_ { ??? ULONG m_ulBlockSize;??????????????????????? //內(nèi)存塊的尺寸 ??? struct _TONY_MEM_BLOCK_HEAD_* m_pNext;????? //指向下一鏈表元素的指針 }STonyMemoryBlockHead; //本結(jié)構(gòu)體的長度，經(jīng)過計算，恒定為8Bytes const ULONG STonyMemoryBlockHeadSize=sizeof(STonyMemoryBlockHead);

上述結(jié)構(gòu)體，包含了內(nèi)存塊尺寸信息，來滿足釋放時查找的需求，同時，包含了指向下一元素的指針，這個指針，在分配給應用程序使用時，是無效的，只有當這個內(nèi)存塊掛接在鏈表中時，才有意義。

筆者這么思考，當我們向系統(tǒng)申請一個內(nèi)存塊，比如說64Bytes，我們內(nèi)存池占用其中最開始的8Bytes來存儲上述信息，也就是說，實際能給應用程序使用的，只有56Bytes。如圖7.3：

圖7.3：內(nèi)存塊組織結(jié)構(gòu)

?

我們假定這個內(nèi)存塊的真實尺寸為N Bytes，我們從系統(tǒng)申請的首指針為p0，那么，我們占用8Bytes作為管理使用，當應用程序申請時，我們真實分配給應用程序的指針為p1=(p0+8)。這樣，當應用程序釋放時，我們只需要執(zhí)行p0=（p1-8），即可求出原始首地址，并以此獲得所有的管理信息。當最后向系統(tǒng)釋放內(nèi)存時，我們只要記得釋放p0即可。

提示：此處可能出于業(yè)務(wù)考慮，有點違背C和C++無錯化程序設(shè)計方法中，關(guān)于指針不得參與四則運算的原則，不過，沒辦法，需求如此，只有這條路走了。因此，違背就違背一點了。

唯一需要我們注意的細節(jié)，是我們在分析應用程序的內(nèi)存申請需求時，不能以申請的內(nèi)存塊的真實尺寸進行比對，而應該比對減去8Bytes之后的數(shù)據(jù)。即64Bytes這個右枝上提供的內(nèi)存，只有56Bytes大小，如果超過這個值，請找下一鏈，即到128 Bytes這個右枝處理，當然，此時的128 Byte的右枝，也僅能提供120 Bytes的內(nèi)存塊，以此類推。

有鑒于此，筆者做了如下的宏定義，來界定所有的計算行為：

//根據(jù)一個應用程序數(shù)據(jù)塊的長度，計算一個內(nèi)存塊的真實大小，即n+8 #define TONY_MEM_BLOCK_SIZE(nDataLength) \ ??? ?(nDataLength+STonyMemoryBlockHeadSize) //根據(jù)向系統(tǒng)申請的內(nèi)存塊，計算其應用程序數(shù)據(jù)內(nèi)存的真實大小，即n-8 #define TONY_MEM_BLOCK_DATA_SIZE(nBlockSize) \ ??? ?(nBlockSize-STonyMemoryBlockHeadSize) //根據(jù)應用程序釋放的指針，逆求真實的內(nèi)存塊指針，即p0=p1-8 #define TONY_MEM_BLOCK_HEAD(pData) \ ??? ?((STonyMemoryBlockHead*)(((char*)pData)-STonyMemoryBlockHeadSize)) //根據(jù)一個內(nèi)存塊的真實指針，求數(shù)據(jù)內(nèi)存塊的指針，即p1=p0+8 #define TONY_MEM_BLOCK_DATA(pHead) \ ??? ?(((char*)pHead)+STonyMemoryBlockHeadSize) //最小內(nèi)存塊長度，16 Bytes，由于我們管理占用8 Bytes，這個最小長度不能再小了， //否則無意義，即使這樣，我們最小的內(nèi)存塊，能分配給應用程序使用的，僅有8 Bytes。 #define TONY_XIAO_MEMORY_STACK_BLOCK_MIN 16 //這是管理的最大內(nèi)存塊長度，1M，如前文表中所示，超過此限制，內(nèi)存池停止服務(wù) //改為直接向系統(tǒng)申請和釋放。 #define TONY_XIAO_MEMORY_STACK_MAX_SAVE_BLOCK_SIZE (1*1024*1024)

---

?

?

總結(jié)

以上是生活随笔為你收集整理的《0bug-C/C++商用工程之道》节选01--内存栈-1的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。