基本概念
- 堆块:堆区内存的基本单位
- 包括两个部分:块首,块身
- 块首:标识这个堆块自身的信息:如大小,是否被占用等
- 块身:分配给用户使用的数据区
- 堆表:一般位于堆区的起始位置,用于索引堆区所有堆块的信息,包括大小,是否被占用等.
- 占用态的堆块被使用它的程序索引,堆表只索引所有空闲态的堆块.
- 堆表分为空闲双向链表Freelist(空表),快速单向链表Lookaside(块表)
- 空表
- 块首:包含一对用于将空闲堆块组织成双向链表的指针
- 空表被分为128条,按照大小区分
- 结构如下free[0]中存放的为不小于1024bytes的堆块链表指针,其余为index*8
- 堆中的操作:堆块分配,堆块释放,堆块合并
- 块表结构:单向链表
- 块表不会发生堆块合并
- 块表总被初始化为空
- 最多四个结点
堆块中的操作
堆块分配:块表分配,普通空表分配和零号空表(Free[0])分配
块表分配:
- 寻找到大小合适的空闲堆块
- 修改其状态为占用态
- 从堆表中"卸下"
- 返回一个指向堆块的指针
普通空表分配
- 寻找最优的空闲块分配,若失败寻找次优的空闲块(最小的能满足要求的空闲块)
零号空表:
- 先查找free[0]最后一个块(尾块),看能否满足需求
- 若能,再正向搜索最小的能满足要求的空闲堆块分配
找零钱现象:
- 无最优的堆块时,会分配一个稍大的
- 会先从大块中精确割除一块进行分配
- 给剩下的部分重新标注块首,链入空表
(快表无此现象)
堆块释放:
- 将块首中堆块的状态信息改为空闲
- 链入相应的堆表(末尾)
堆块合并:
- 两个空闲堆块彼此相邻时会进行合并操作
- 从空闲链表中卸下
- 合并堆块
- 调整合并后的块首信息
- 将新块链入空表
RtlAllocateHeap()
位于ntdll.dll,堆分配的鼻祖
所有的堆分配函数最终都会调用他