Archive

Archive for December, 2005

HeapAlloc内部算法

December 23rd, 2005 1 comment

大家都知道在VC中使用new操作符时(如果没有重载的话),其内部实际上调用了标准的malloc,而根据工程设置中选择的运行库的不同(是否多线程,是否调试,是否Dll等)调用了不同的malloc版本,多线程版malloc内部使用了Win32的关键区,而调试版会额外多申请一些内存用来保存调试信息,这些直接看VC附带的crt源码就可以看到。所有版本的malloc的共同点是最后都调用了Win32的API函数HeapAlloc。

关于HeapAlloc的算法记得很多年前一个后来去了微软的大牛给我讲过,但当时我还是个菜鸟(现在没那么菜了)没记住,于是决定自己研究一下。方法是用HeapCreate自己建一个堆,用HeapAlloc从里面申请内存,同时用VC的内存查看盯着heap所在内存区看,观察Alloc和Free的时候内存都发生了哪些变化。其间从网上找到的这篇文档帮助比较大,节省了不少时间。

Heap头的结构基本没搞明白(也不需要太关心),只知道在偏移地址0x28的位置记录的是剩余空间大小(单位是8字节),然后从0x178开始是一个free list 表(数组),一共128个单元,每个单元的数组下标代表这个链上每个节点(free chunk)是多大(包括chunk header所占空间,单位是8字节)。所以记录的是0~1024(128×8)大小的free chunk链,每个单元是一个循环链表,Flink和Plink指针共占用8个字节。第0号单元比较特殊,它维护的是大小>=1k的chunk的list,按chunk大小升序排列。 Read more…

Categories: 程序/算法 Tags: ,