堆溢出研究一
环境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安全：软件漏洞分析技术》