堆溢出研究一
環境windows2000目錄
- 堆內存概念的認識
- 堆內存與棧內存的對比
- 堆內存中數據結構的認識
1. 堆內存概念的認識
在計算機科學中, 動態內存分配（Dynamic memory allocation）又稱為堆內存分配，是指計算機程序在運行期中分配使用內存。它可以當成是一種分配有限內存資源所有權的方法。 動態分配的內存在被程序員明確釋放或被垃圾回收之前一直有效。與靜態內存分配的區別在于沒有一個固定的生存期。這樣被分配的對象稱之為有一個“動態生存期”。 《維基百科》堆內存棧內存的對比
堆內存申請，釋放，操作，特點：
1. 堆內存申請環境:堆內存需要程序員在程序中申請 ，動態分配，申請的大小有程序決定。
2. 堆內存申請方法：C語言中的malloc（） 函數 ， c++ 中的new（）函數。堆內存進行申請時候可能會申請失敗，申請成功與失敗與計算機性能，當前運行環境等有關。
3. 堆內存釋放：申請過后的堆內存不能由系統自動進行釋放，C語言中采用free（）函數，c++中采用 delete()函數進行釋放內存。
4. 堆內存操作：申請過后的內存，會返回指向堆內存的指針，后續對于內存的讀寫等操作需要通過此指針進行。
5. 堆內存特點：地址由低向高生長。 堆內存非線性，呈現無序狀態。
棧內存的申請，釋放，操作，特點：
1. 棧內存的申請是在程序中定義好的，包括棧的大小，包含的變量，（存儲局部變量，數組，棧幀，函數返回地址等）
2. 棧內存的釋放是有程序自身決定的不用掉用函數，當程序退出時，棧內存會自動銷毀，維持棧平衡，否則就會發生內存訪問錯誤。
3. 棧內存的操作，有兩種 push pop 只有這兩種操作。
4. 棧內存的特點：由高地址向低地址生長，呈現線性規劃。
堆內存中數據結構&&管理策略堆內存中數據結構
簡介：堆的數據結構主要分為堆塊和堆表兩類：
堆塊：
出于對性能的考慮，、堆區的內存按照不同大小的塊被組織起來，以字節為單位進行標識。
堆塊的結構：堆塊分為快首和塊身。
塊首的結構：塊首包含當前堆塊的主要信息例如：此堆塊的大小，是否是空閑態還是占用態等狀態表信息。
對塊首的識別：當連續進行內存申請的時候返回的指針地址是有差距的，兩個連續的指針之間的差距就是第二個塊身的塊首。
塊身的結構：塊身就是本堆塊存放數據的位置，即最終分配給用戶的數據區。
塊身位置 ：塊身位于塊首的后面緊挨著。
對塊身的操作:當申請堆區成功后返回的指針直接指向的塊身的首地址，對堆區的操作也就是對堆區的操作
堆表
- 堆表的意義：堆表用來索引堆塊。堆表中包含索引堆塊的大小，位置，狀態等信息。堆表的數據結構決定啦堆區的組織方式，是快速檢索空閑塊，保證堆分配效率的關鍵。堆表進行設計的時候會考慮二叉樹平衡策略，快速查找策略等。現代的操作系統中堆表的數據結構還不止一種。
2.在windows中，占用態的堆塊索引使用自己的程序索引，堆表只索引所有空閑態的堆塊。重要的堆表包含兩類：空閑雙向鏈表（簡稱空表），快速單向鏈表（塊表）。下面逐一對其要點進行分析。
空表
1.堆區空閑堆塊的塊首都包含一對指針，這對指針用于將空閑的堆塊組織成雙向鏈表，按照大小的不同，總共分為128條。
2.堆區一開始的堆表區，中有一個128項的指針數組，叫空表數組索引，該數組的每一項都包含兩個指針，用來標示一條空表。
3.空表的結構如下圖所示：
上圖重點知識：
- freelist[0]被稱為零號空表 并且是節點從第一個 1024bytes 逐漸增減1024的整數倍。第二個及以后的節點 >=1024 bytes
- 從第二個鏈表開始即：free list【1】 開始： free list【1】 此空閑鏈表中每個節點是八個字節。free list【2】 = 16bytes
即： 節點的字節數 = 下表 * 8
3.此處謹記零號空閑鏈表。在堆分配的時候很重要。 4.空表的特點：可以發生堆塊合并，分配的效率低
塊表
1.快速單項鏈表。塊表是windows加速堆塊分配的一種鏈表
2.快表特點：永遠處于占用態意味著不會發生合并，快表只包含四個節點。同樣的快表也是包含128條，組織結構跟空表很類似，塊表總是被初始化為空。
3.結構如下圖：
如上圖所示：最多為四個節點，鏈表編號為（0 ~ 127）
堆分配策略
堆塊的分配
堆塊的分配包括：空表的分配，快表的分配，零號空表的分配
- 快表的分配：包括尋找到精確匹配大小的空閑塊，將此空閑塊標注為占用狀態，從快表中卸下，返回指向堆塊塊身的指針供程序使用。
- 零號空表的分配：零號空表中所有的空閑塊是按照從小到大的順序排列的，因此在分配的時候先從最后的堆塊進行分配，看能否滿足要求，如果能滿足要求，則正向尋找最小能滿足要求的堆塊進行分配。
- 空表分配：普通空表進行分配時候，尋找最優解決方案，若不滿滿足最優解決方案，則采用次優解決方案進行分配。空表分配中存在找零錢的現象，即：當無法找到最有解決方案，次優解決方案的時候，就會從大的尾塊中進行割下一小快能夠滿足要求的堆塊，最后進行尾塊的塊首的狀態信息進行修改即可。
4.堆塊分配的特點：快表中只存在精確分配，不存在找零錢現象。空表中存在找零錢現象（不考慮堆緩存，碎片化等情況）
堆塊的釋放
堆表的釋放包括將講占用態該為空閑態，釋放的堆塊鏈入相應的堆表，所有釋放的都鏈入相應的表尾，分配的時候先從表尾進行分配。塊表只包含四個節點；堆塊的合并
經過反反復復的堆塊的分配與釋放，堆區會出新很多凌亂的碎片，這時候就需要用到堆塊的合并，堆塊的合并包括幾個動作：將堆塊從空表中卸下，合并堆塊，修改合并后的塊首，鏈接入新的璉表。（合并的時候還有一種操作叫內存緊縮）。 合并的時候之會合并相鄰的堆塊。 根據申請的內存大小的不同，分配和釋放算法分為三類
參考：《0day安全：軟件漏洞分析技術》
| 
