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