selph
selph
发布于 2022-03-22 / 328 阅读
0
0

漏洞学习--堆基础知识

堆和栈的区别

堆内存栈内存
典型用例动态增长的链表等结构函数局部数组
申请方式使用函数申请,通过指针使用直接声明
释放方式使用函数释放系统回收
管理方式使用者管理系统管理
所处位置变化范围大相对固定
增长方向低向高排列高向低增加

堆的数据结构与管理策略

堆块

堆块:出于性能的考虑,堆区的内存按不同大小组织成块,以堆块为单位进行标识,而不是传统的按字节标识。一个堆块包括两个部分:块首和块身。块首是一个堆块头部的几个字节, 用来标识这个堆块自身的信息(本块的大小、本块空闲还是占用等信息),块身是紧跟在块首后面的部分,也是最终分配给用户使用的数据区。

堆表并不索引所有的堆块。在Windows系统中:

  • 处于占用态的堆块由正在使用它的程序索引
  • 处于空闲态的堆块由堆表索引。

空闲的堆块大小不一,而且其使用频率不定。可能较小的堆块的使用频率更高,较大的使用频率较低,这需要对这两种情况进行不同的索引方式以提高效率。该问题主要通过不同类型的堆表进行解决,其中,最重要的堆表有两种:空闲双向链表Freelist和快速单向链表Lookaside。

image-20220220191443793

堆表

堆表一般位于堆区的起始位置,用于索引堆区中所有堆块的重要信息,包括堆块的位置、堆块的大小、空闲还是占用等。堆表里有很多信息:段表索引,虚表索引,空表使用标识,空表索引区

空表

空闲堆块的堆首有一对链表指针,空闲堆块之间组成双向链表--空表:

  • 双向链表共有128条
  • free[1]开始,每个链表保存的堆块大小依次+8字节
  • free[0]保存大于1024字节的堆块(小于512KB)

image-20220220191646590

快表

快表是Windows加速堆块分配采用的堆表:

  • 不会出现堆块合并(因为其中的空闲堆块被设置为占用态,不会发生合并,大大提高堆块分配速度)
  • 快表只有在精确匹配的时候才会分配(分割或合并后的堆块)
  • 有128条,组织结构和空表类似,但是单链表
  • 初始化的时候会初始化为空,每条快表有4个节点
  • 单链表操作比双链表简单,快表速度快

image-20220223114245951

堆操作

堆操作:

  • 堆块分配:
    • 快表,找到大小匹配空闲的堆块,修改一下堆块状态,从堆表中取出,返回一个指针给程序使用
    • 普通空表,寻找最优的空闲堆块,找不到则找次优的
    • 0号空表,从后往前寻找合适的堆块(满足条件的最小堆块)
  • 堆块释放:将堆块修改为空闲状态,然后插入相应的链表末尾
  • 堆块合并(内存紧缩):为了减少内存碎片,当两个堆块相邻且空闲时,堆管理系统就会进行堆块合并操作:将两个堆块断链,合并堆块,调整合并后的堆块头信息,将合并后的堆块插入合适的链表

堆根据内存大小不同可以分为三类:小块(size<1kb),大块(1KB<=size<512KB),大大块(512KB<=size)

分配与释放算法

分配释放
小块分配顺序:快表,空表,堆缓存,0号空表,内存紧缩后重试,如果还不行就返回NULL优先插入快表(上限4个)如果快表满了就插入空表
大块堆缓存分配,失败则使用0号空表的大块分配优先插入堆缓存,如果满了则插入0号空表
巨块虚分配直接释放

堆分配函数调用关系

Windows下堆管理结构如下:

img

Windows中很多堆相关的管理函数的调用关系如图,最终都会到同一个函数RtlAllocHeap():

img

参考资料


评论