堆表介绍:
空闲双向链表Freelist(空表)
空闲堆块的块首中包含一对重要的指针,这对指针用于将空闲堆块组织成双向链表。按照堆块大小的不同,空表总共被分为128条。
堆区一开始的堆表区中有一个128项的指针数组,被称作空表索引。该数组的每一项包括两个指针,用于标识一条空表。
除了空表索引的第一项外,其余空表的大小为:
空闲堆块的大小=索引项(ID)*8(字节)
空表索引的第一项所标识的空表相对比较特殊。这条双向链表链入了所有大于等于1024字节的堆块(小于512KB).这些堆块按照各自的大小在零号空表中升序地依次排列下去。
快速单向链表Lookaside(快表)
快表不会发生堆块合并(其中的空闲块块首被设置为占用态,用来防止堆块合并)
快表也有128条,结构和空表类似,只是其中的堆块按照单链表组织。每个快表最多只有4个结点。
堆的操作
堆块分配
快表分配:
寻找大小匹配的空闲堆块、将其状态修改为占用态、把它从堆表中“卸下”、最后返回一个指向堆块块身的指针给程序用。
普通空表:
首先寻找最优的空闲块分配,若失败,则寻找次优的空闲块分配,即最小的能满足的。
零号空表分配:
按照大小升序链着大小不同的空闲块,从free[0]反向查找最后一块(即表中最大块),如果能满足要求,再正向搜索最小能满足要求的空闲堆块进行分配。
“找零钱”现象:
当空表中无法找到“最优”堆块时,一个稍大些的块会被用于分配。这种次优分配发生时,会先从大块中按请求的大小精确地“割”出一块进行分配。然后给剩下的部分重新标注块首,链入空表。
堆块释放
所有的释放块都链入堆表的末尾,分配的时候也先从堆表末尾拿。
堆块合并
当堆管理系统发现两个空闲堆块彼此相邻的时候,就会进行堆块合并。
分配和释放算法图
注意点
1. 快表中的空闲块被设置为占用态,故不会发生堆块合并操作。
2. 快表只有精确匹配时才会分配,不存在“搜索次优解”和“找零钱”现象。
3. 快表是单链表,操作比双链表简单,插入删除都很少用很多命令。
4. 快表很快,故再分配和释放时总是优先使用快表,失败时才用空表。
5. 快表只有4项,很容易被填满,因此空表也是被频繁使用的。
实验
代码:
#include <stdio.h>
#include <windows.h>
void main()
{
HLOCAL h1;
HANDLE hp;
hp = HeapCreate(0,0x1000,0x10000);
__asm int 3
h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,16);
}
直接运行出错后选择取消进入od调试,现在的eax就是前面HeapCreate的返回地址,也就是创建堆的起始地址。 从3A0000开始包含的信息依次是段表索引,虚表索引,空表使用标识和空表索引区 跟进
参考链接
具体的实践:http://oldblog.giantbranch.cn/?p=437