浅析 Win2K 中堆(Heap)的实现

类别:VC语言 点击:0 评论:0 推荐:

浅析 Win2K 中堆(Heap)的实现

作者: JIURL

                 主页: http://jiurl.yeah.net/

    日期: 2003-5-23

    第一 前言

    关于Win2k堆的实现和里面的数据结构,没有任何的官方描述(差不多可以这么说吧),非官方的东西也只要几篇关于堆溢出的文章提到了一点,还充满了错误(差不错可以这么说吧)。本文通过分析,试验和猜测,来获得知识,同样可能充满了错误,大家多保重。我最近在学习Windows系统,如果有哪位有兴趣,有时间,也有能力的话非常非常欢迎和我联系,或许能互相帮助。本文只是半成品,很多地方没有力求详尽,也非常非常欢迎大家对本文进行补充,设计更多的测试,对于堆有更多的了解,一定也告诉我。发现错误也一定告诉我。

欢迎大家来这里看看 http://jiurl.cosoft.org.cn/forum/ http://jiurl.yeah.net/  

    第二 对于堆的简介

    程序中动态的内存申请和释放是在堆(heap)上实现的,比如C的malloc,free,C++的new,delete等。一个进程可以有多个堆,每个进程都有一个默认的堆,叫进程堆(可以用 GetProcessHeap 活得这个堆的句柄,这个句柄就是这个堆开始处的线性地址)。在可执行文件(也就是PE文件,PE是windows下的可执行文件格式)的PE Header中的OptionalHeader中我们也可以看到关于进程堆的两个域 SizeOfHeapReserve SizeOfHeapCommit,SizeOfHeapReserve 表示了为进程堆保留的地址空间,SizeOfHeapCommit 表示了为进程堆开始提交的实际物理内存。下面看一个堆在使用中会遇到的问题。

某个程序在某个时候动态申请了几块大小不等的内存,堆中情况如图1所示。过了一段儿时间,该程序又释放了其中几块申请的内存,于是堆中情况如图2所示(白色部分表示释放的空闲内存,蓝色部分表示申请使用的)。可以看到图2中的堆出现了一些小块的空闲内存。如果又要动态申请内存,那么情况会怎么样呢?2,4,5现在是空闲块儿,如果大小能满足需要的话,就可以用来满足申请。为了能够有比较大的连续块儿,4,5那样的连续的空闲块儿还应该被合并成一块。为了使用那些空闲块,必须要知道他们的位置,以及大小。为了能有比较大的空闲块儿,紧挨着的空闲块儿还需要被合并。然后申请的时候,找每个空闲块儿,并判断大小能否满足,一旦可以满足就立刻提供使用。上面的这些问题决定了堆的实现方式。从上面的描述我们可以发现堆的一个问题,就是堆上的内存的申请和释放比较慢,比较费时间(这是相对于堆栈(stack)之类上的内存使用而言的),而且也比较没准。比如释放内存的时候,就说不定需要合并内存块儿。而申请的时候有可能一次就找到合适的空闲块儿一次就完成申请了,也有可能找到第一个空闲块,发现大小不合适,于是找下一个空闲块,发现大小又不合适,就这样找了49次,才找到合适的空闲块。可以看到画的时间多么没准,也许是1次,也许是49次。下面我们来浅析一下Win2k中堆的实现。

    第三 浅析Win2k中堆的实现

   调试环境 Win2k VC6 Softice

    注意以debug编译的程序的heap中的结构和以release编译的程序的heap中的结构是不一样的。我们这里只分析release程序的heap的情况。

    思路是这样的,先用 HeapCreate 创建一个堆,这个时候堆还没有任何动态申请的内容。然后把这个时候的堆中的内容保存下来。然后对这个堆进行一些操作,申请几块内存,然后释放几块。再把这时的堆的内容保存下来进行比较。

   使用程序如下

#include <windows.h>
#include <stdio.h>
#include <conio.h>

#define N_BUF 8

void main()
{
HANDLE hHeap;

hHeap=HeapCreate(NULL,0x1000,0x10000); 
//getch(); //首先使用第一个getch()使程序停在 HeapCreate 之后,然后使用softice保存堆内容。


char *buf[N_BUF];

char str[14] = "AAAAAAAAAAAAA";

int i;
for(i=0;i<N_BUF;i++)
{
buf[i]=(char*)HeapAlloc(hHeap, 0, 16);
strcpy(buf[i],str);
//printf("%s\n",buf[i]);
}

for(i=1;i<N_BUF;i+=2)
{
HeapFree(hHeap, 0, buf[i]);
}

getch();//第二个getch()使程序使程序停在对堆进行设计好的操作之后,然后用softice保存堆内容。

HeapDestroy(hHeap);

}

首先使用第一个getch()使程序停在 HeapCreate 之后,然后使用softice保存堆内容。第二个getch()使程序使程序停在对堆进行设计好的操作之后,然后用softice保存堆内容。这个程序会动态申请8个16字节大小的内存(分别是0,1,2,3,4,5,6,7)。然后释放其中的第1,3,5,7块。

该程序名叫JiurlHeap,所以进程名也叫JiurlHeap,句柄 hHeap 就是该堆的线性地址。当每次用getch()停住之后,ctrl+d打开softice,使用addr JiurlHeap,切换到该进程的地址空间,然后d 该堆的地址,就可以看到这个堆的内容。

HeapCreate之后,内容如下:

0010:00520000 000000C8 00000100 EEFFEEFF 00001000 ................
0010:00520010 00000000 0000FE00 00100000 00002000 ............. ..
0010:00520020 00000200 00002000 00000130 7FFDEFFF ..... ..0......
0010:00520030 06080004 00000000 00000000 00000000 ................
0010:00520040 00000000 00520598 0000000F FFFFFFF8 ......R.........
0010:00520050 00520050 00520050 00520640 00000000 [email protected].....
0010:00520060 00000000 00000000 00000000 00000000 ................
0010:00520070 00000000 00000000 00000000 00000000 ................
0010:00520080 00000000 00000000 00000000 00000000 ................
0010:00520090 00000000 00000000 00000000 00000000 ................
0010:005200A0 00000000 00000000 00000000 00000000 ................
0010:005200B0 00000000 00000000 00000000 00000000 ................
0010:005200C0 00000000 00000000 00000000 00000000 ................
0010:005200D0 00000000 00000000 00000000 00000000 ................
0010:005200E0 00000000 00000000 00000000 00000000 ................
0010:005200F0 00000000 00000000 00000000 00000000 ................
0010:00520100 00000000 00000000 00000000 00000000 ................
0010:00520110 00000000 00000000 00000000 00000000 ................
0010:00520120 00000000 00000000 00000000 00000000 ................
0010:00520130 00000000 00000000 00000000 00000000 ................
0010:00520140 00000000 00000000 00000000 00000000 ................
0010:00520150 00000000 00000000 00000000 00000000 ................
0010:00520160 00000000 00000000 0000FFFF 00000000 ................
0010:00520170 00000000 00000000 00520688 00520688 ..........R...R.
0010:00520180 00520180 00520180 00520188 00520188 ..R...R...R...R.
0010:00520190 00520190 00520190 00520198 00520198 ..R...R...R...R.
0010:005201A0 005201A0 005201A0 005201A8 005201A8 ..R...R...R...R.
0010:005201B0 005201B0 005201B0 005201B8 005201B8 ..R...R...R...R.
0010:005201C0 005201C0 005201C0 005201C8 005201C8 ..R...R...R...R.
0010:005201D0 005201D0 005201D0 005201D8 005201D8 ..R...R...R...R.
0010:005201E0 005201E0 005201E0 005201E8 005201E8 ..R...R...R...R.
0010:005201F0 005201F0 005201F0 005201F8 005201F8 ..R...R...R...R.
0010:00520200 00520200 00520200 00520208 00520208 ..R...R...R...R.
0010:00520210 00520210 00520210 00520218 00520218 ..R...R...R...R.
0010:00520220 00520220 00520220 00520228 00520228 .R. .R.(.R.(.R.
0010:00520230 00520230 00520230 00520238 00520238 0.R.0.R.8.R.8.R.
0010:00520240 00520240 00520240 00520248 00520248 @[email protected].
0010:00520250 00520250 00520250 00520258 00520258 P.R.P.R.X.R.X.R.
0010:00520260 00520260 00520260 00520268 00520268 `.R.`.R.h.R.h.R.
0010:00520270 00520270 00520270 00520278 00520278 p.R.p.R.x.R.x.R.
0010:00520280 00520280 00520280 00520288 00520288 ..R...R...R...R.
0010:00520290 00520290 00520290 00520298 00520298 ..R...R...R...R.
0010:005202A0 005202A0 005202A0 005202A8 005202A8 ..R...R...R...R.
0010:005202B0 005202B0 005202B0 005202B8 005202B8 ..R...R...R...R.
0010:005202C0 005202C0 005202C0 005202C8 005202C8 ..R...R...R...R.
0010:005202D0 005202D0 005202D0 005202D8 005202D8 ..R...R...R...R.
0010:005202E0 005202E0 005202E0 005202E8 005202E8 ..R...R...R...R.
0010:005202F0 005202F0 005202F0 005202F8 005202F8 ..R...R...R...R.
0010:00520300 00520300 00520300 00520308 00520308 ..R...R...R...R.
0010:00520310 00520310 00520310 00520318 00520318 ..R...R...R...R.
0010:00520320 00520320 00520320 00520328 00520328 .R. .R.(.R.(.R.
0010:00520330 00520330 00520330 00520338 00520338 0.R.0.R.8.R.8.R.
0010:00520340 00520340 00520340 00520348 00520348 @[email protected].
0010:00520350 00520350 00520350 00520358 00520358 P.R.P.R.X.R.X.R.
0010:00520360 00520360 00520360 00520368 00520368 `.R.`.R.h.R.h.R.
0010:00520370 00520370 00520370 00520378 00520378 p.R.p.R.x.R.x.R.
0010:00520380 00520380 00520380 00520388 00520388 ..R...R...R...R.
0010:00520390 00520390 00520390 00520398 00520398 ..R...R...R...R.
0010:005203A0 005203A0 005203A0 005203A8 005203A8 ..R...R...R...R.
0010:005203B0 005203B0 005203B0 005203B8 005203B8 ..R...R...R...R.
0010:005203C0 005203C0 005203C0 005203C8 005203C8 ..R...R...R...R.
0010:005203D0 005203D0 005203D0 005203D8 005203D8 ..R...R...R...R.
0010:005203E0 005203E0 005203E0 005203E8 005203E8 ..R...R...R...R.
0010:005203F0 005203F0 005203F0 005203F8 005203F8 ..R...R...R...R.
0010:00520400 00520400 00520400 00520408 00520408 ..R...R...R...R.
0010:00520410 00520410 00520410 00520418 00520418 ..R...R...R...R.
0010:00520420 00520420 00520420 00520428 00520428 .R. .R.(.R.(.R.
0010:00520430 00520430 00520430 00520438 00520438 0.R.0.R.8.R.8.R.
0010:00520440 00520440 00520440 00520448 00520448 @[email protected].
0010:00520450 00520450 00520450 00520458 00520458 P.R.P.R.X.R.X.R.
0010:00520460 00520460 00520460 00520468 00520468 `.R.`.R.h.R.h.R.
0010:00520470 00520470 00520470 00520478 00520478 p.R.p.R.x.R.x.R.
0010:00520480 00520480 00520480 00520488 00520488 ..R...R...R...R.
0010:00520490 00520490 00520490 00520498 00520498 ..R...R...R...R.
0010:005204A0 005204A0 005204A0 005204A8 005204A8 ..R...R...R...R.
0010:005204B0 005204B0 005204B0 005204B8 005204B8 ..R...R...R...R.
0010:005204C0 005204C0 005204C0 005204C8 005204C8 ..R...R...R...R.
0010:005204D0 005204D0 005204D0 005204D8 005204D8 ..R...R...R...R.
0010:005204E0 005204E0 005204E0 005204E8 005204E8 ..R...R...R...R.
0010:005204F0 005204F0 005204F0 005204F8 005204F8 ..R...R...R...R.
0010:00520500 00520500 00520500 00520508 00520508 ..R...R...R...R.
0010:00520510 00520510 00520510 00520518 00520518 ..R...R...R...R.
0010:00520520 00520520 00520520 00520528 00520528 .R. .R.(.R.(.R.
0010:00520530 00520530 00520530 00520538 00520538 0.R.0.R.8.R.8.R.
0010:00520540 00520540 00520540 00520548 00520548 @[email protected].
0010:00520550 00520550 00520550 00520558 00520558 P.R.P.R.X.R.X.R.
0010:00520560 00520560 00520560 00520568 00520568 `.R.`.R.h.R.h.R.
0010:00520570 00520570 00520570 00520608 00000000 p.R.p.R...R.....
0010:00520580 00000000 00000000 00000000 00521000 ..............R.
0010:00520590 0000F000 00000000 005205A8 00000000 ..........R.....
0010:005205A0 00000000 00000000 005205B8 00000000 ..........R.....
0010:005205B0 00000000 00000000 005205C8 00000000 ..........R.....
0010:005205C0 00000000 00000000 005205D8 00000000 ..........R.....
0010:005205D0 00000000 00000000 005205E8 00000000 ..........R.....
0010:005205E0 00000000 00000000 005205F8 00000000 ..........R.....
0010:005205F0 00000000 00000000 00000000 00000000 ................
0010:00520600 00000000 00000000 77FCD640 FFFFFFFF [email protected]....
0010:00520610 00000000 00000000 00000030 00000000 ........0.......
0010:00520620 00000000 00000000 00000000 00000000 ................
0010:00520630 00000000 00000000 00000000 00000000 ................
0010:00520640 00C80008 00000100 FFEEFFEE 00000000 ................
0010:00520650 00520000 0000F000 00520000 00000010 ..R.......R.....
0010:00520660 00520680 00530000 0000000F 00000001 ..R...S.........
0010:00520670 00520588 00000000 00520680 00000000 ..R.......R.....
0010:00520680 00080130 00001000 00520178 00520178 0.......x.R.x.R.
0010:00520690 00000000 00000000 00000000 00000000 ................
0010:005206A0 00000000 00000000 00000000 00000000 ................
0010:005206B0 00000000 00000000 00000000 00000000 ................
0010:005206C0 00000000 00000000 00000000 00000000 ................
0010:005206D0 00000000 00000000 00000000 00000000 ................
0010:005206E0 00000000 00000000 00000000 00000000 ................
0010:005206F0 00000000 00000000 00000000 00000000 ................
0010:00520700 00000000 00000000 00000000 00000000 ................
0010:00520710 00000000 00000000 00000000 00000000 ................
0010:00520720 00000000 00000000 00000000 00000000 ................
0010:00520730 00000000 00000000 00000000 00000000 ................
0010:00520740 00000000 00000000 00000000 00000000 ................
0010:00520750 00000000 00000000 00000000 00000000 ................
0010:00520760 00000000 00000000 00000000 00000000 ................
0010:00520770 00000000 00000000 00000000 00000000 ................
0010:00520780 00000000 00000000 00000000 00000000 ................
0010:00520790 00000000 00000000 00000000 00000000 ................
0010:005207A0 00000000 00000000 00000000 00000000 ................
0010:005207B0 00000000 00000000 00000000 00000000 ................
0010:005207C0 00000000 00000000 00000000 00000000 ................
0010:005207D0 00000000 00000000 00000000 00000000 ................
0010:005207E0 00000000 00000000 00000000 00000000 ................
0010:005207F0 00000000 00000000 00000000 00000000 ................
0010:00520800 00000000 00000000 00000000 00000000 ................
0010:00520810 00000000 00000000 00000000 00000000 ................
0010:00520820 00000000 00000000 00000000 00000000 ................
0010:00520830 00000000 00000000 00000000 00000000 ................
0010:00520840 00000000 00000000 00000000 00000000 ................
0010:00520850 00000000 00000000 00000000 00000000 ................
0010:00520860 00000000 00000000 00000000 00000000 ................
0010:00520870 00000000 00000000 00000000 00000000 ................
0010:00520880 00000000 00000000 00000000 00000000 ................
0010:00520890 00000000 00000000 00000000 00000000 ................
0010:005208A0 00000000 00000000 00000000 00000000 ................
0010:005208B0 00000000 00000000 00000000 00000000 ................
0010:005208C0 00000000 00000000 00000000 00000000 ................
0010:005208D0 00000000 00000000 00000000 00000000 ................
0010:005208E0 00000000 00000000 00000000 00000000 ................
0010:005208F0 00000000 00000000 00000000 00000000 ................
0010:00520900 00000000 00000000 00000000 00000000 ................
0010:00520910 00000000 00000000 00000000 00000000 ................
0010:00520920 00000000 00000000 00000000 00000000 ................
0010:00520930 00000000 00000000 00000000 00000000 ................
0010:00520940 00000000 00000000 00000000 00000000 ................
0010:00520950 00000000 00000000 00000000 00000000 ................
0010:00520960 00000000 00000000 00000000 00000000 ................
0010:00520970 00000000 00000000 00000000 00000000 ................
0010:00520980 00000000 00000000 00000000 00000000 ................
0010:00520990 00000000 00000000 00000000 00000000 ................
0010:005209A0 00000000 00000000 00000000 00000000 ................
0010:005209B0 00000000 00000000 00000000 00000000 ................
0010:005209C0 00000000 00000000 00000000 00000000 ................
0010:005209D0 00000000 00000000 00000000 00000000 ................
0010:005209E0 00000000 00000000 00000000 00000000 ................
0010:005209F0 00000000 00000000 00000000 00000000 ................
0010:00520A00 00000000 00000000 00000000 00000000 ................
0010:00520A10 00000000 00000000 00000000 00000000 ................
0010:00520A20 00000000 00000000 00000000 00000000 ................
0010:00520A30 00000000 00000000 00000000 00000000 ................
0010:00520A40 00000000 00000000 00000000 00000000 ................
0010:00520A50 00000000 00000000 00000000 00000000 ................
0010:00520A60 00000000 00000000 00000000 00000000 ................
0010:00520A70 00000000 00000000 00000000 00000000 ................
0010:00520A80 00000000 00000000 00000000 00000000 ................
0010:00520A90 00000000 00000000 00000000 00000000 ................
0010:00520AA0 00000000 00000000 00000000 00000000 ................
0010:00520AB0 00000000 00000000 00000000 00000000 ................
0010:00520AC0 00000000 00000000 00000000 00000000 ................
0010:00520AD0 00000000 00000000 00000000 00000000 ................
0010:00520AE0 00000000 00000000 00000000 00000000 ................
0010:00520AF0 00000000 00000000 00000000 00000000 ................
0010:00520B00 00000000 00000000 00000000 00000000 ................
0010:00520B10 00000000 00000000 00000000 00000000 ................
0010:00520B20 00000000 00000000 00000000 00000000 ................
0010:00520B30 00000000 00000000 00000000 00000000 ................
0010:00520B40 00000000 00000000 00000000 00000000 ................
0010:00520B50 00000000 00000000 00000000 00000000 ................
0010:00520B60 00000000 00000000 00000000 00000000 ................
0010:00520B70 00000000 00000000 00000000 00000000 ................
0010:00520B80 00000000 00000000 00000000 00000000 ................
0010:00520B90 00000000 00000000 00000000 00000000 ................
0010:00520BA0 00000000 00000000 00000000 00000000 ................
0010:00520BB0 00000000 00000000 00000000 00000000 ................
0010:00520BC0 00000000 00000000 00000000 00000000 ................
0010:00520BD0 00000000 00000000 00000000 00000000 ................
0010:00520BE0 00000000 00000000 00000000 00000000 ................
0010:00520BF0 00000000 00000000 00000000 00000000 ................
0010:00520C00 00000000 00000000 00000000 00000000 ................
0010:00520C10 00000000 00000000 00000000 00000000 ................
0010:00520C20 00000000 00000000 00000000 00000000 ................
0010:00520C30 00000000 00000000 00000000 00000000 ................
0010:00520C40 00000000 00000000 00000000 00000000 ................
0010:00520C50 00000000 00000000 00000000 00000000 ................
0010:00520C60 00000000 00000000 00000000 00000000 ................
0010:00520C70 00000000 00000000 00000000 00000000 ................
0010:00520C80 00000000 00000000 00000000 00000000 ................
0010:00520C90 00000000 00000000 00000000 00000000 ................
0010:00520CA0 00000000 00000000 00000000 00000000 ................
0010:00520CB0 00000000 00000000 00000000 00000000 ................
0010:00520CC0 00000000 00000000 00000000 00000000 ................
0010:00520CD0 00000000 00000000 00000000 00000000 ................
0010:00520CE0 00000000 00000000 00000000 00000000 ................
0010:00520CF0 00000000 00000000 00000000 00000000 ................
0010:00520D00 00000000 00000000 00000000 00000000 ................
0010:00520D10 00000000 00000000 00000000 00000000 ................
0010:00520D20 00000000 00000000 00000000 00000000 ................
0010:00520D30 00000000 00000000 00000000 00000000 ................
0010:00520D40 00000000 00000000 00000000 00000000 ................
0010:00520D50 00000000 00000000 00000000 00000000 ................
0010:00520D60 00000000 00000000 00000000 00000000 ................
0010:00520D70 00000000 00000000 00000000 00000000 ................
0010:00520D80 00000000 00000000 00000000 00000000 ................
0010:00520D90 00000000 00000000 00000000 00000000 ................
0010:00520DA0 00000000 00000000 00000000 00000000 ................
0010:00520DB0 00000000 00000000 00000000 00000000 ................
0010:00520DC0 00000000 00000000 00000000 00000000 ................
0010:00520DD0 00000000 00000000 00000000 00000000 ................
0010:00520DE0 00000000 00000000 00000000 00000000 ................
0010:00520DF0 00000000 00000000 00000000 00000000 ................
0010:00520E00 00000000 00000000 00000000 00000000 ................
0010:00520E10 00000000 00000000 00000000 00000000 ................
0010:00520E20 00000000 00000000 00000000 00000000 ................
0010:00520E30 00000000 00000000 00000000 00000000 ................
0010:00520E40 00000000 00000000 00000000 00000000 ................
0010:00520E50 00000000 00000000 00000000 00000000 ................
0010:00520E60 00000000 00000000 00000000 00000000 ................
0010:00520E70 00000000 00000000 00000000 00000000 ................
0010:00520E80 00000000 00000000 00000000 00000000 ................
0010:00520E90 00000000 00000000 00000000 00000000 ................
0010:00520EA0 00000000 00000000 00000000 00000000 ................
0010:00520EB0 00000000 00000000 00000000 00000000 ................
0010:00520EC0 00000000 00000000 00000000 00000000 ................
0010:00520ED0 00000000 00000000 00000000 00000000 ................
0010:00520EE0 00000000 00000000 00000000 00000000 ................
0010:00520EF0 00000000 00000000 00000000 00000000 ................
0010:00520F00 00000000 00000000 00000000 00000000 ................
0010:00520F10 00000000 00000000 00000000 00000000 ................
0010:00520F20 00000000 00000000 00000000 00000000 ................
0010:00520F30 00000000 00000000 00000000 00000000 ................
0010:00520F40 00000000 00000000 00000000 00000000 ................
0010:00520F50 00000000 00000000 00000000 00000000 ................
0010:00520F60 00000000 00000000 00000000 00000000 ................
0010:00520F70 00000000 00000000 00000000 00000000 ................
0010:00520F80 00000000 00000000 00000000 00000000 ................
0010:00520F90 00000000 00000000 00000000 00000000 ................
0010:00520FA0 00000000 00000000 00000000 00000000 ................
0010:00520FB0 00000000 00000000 00000000 00000000 ................
0010:00520FC0 00000000 00000000 00000000 00000000 ................
0010:00520FD0 00000000 00000000 00000000 00000000 ................
0010:00520FE0 00000000 00000000 00000000 00000000 ................
0010:00520FF0 00000000 00000000 00000000 00000000 ................

做了一些申请和释放之后,内容如下

0010:00520000 000000C8 00000100 EEFFEEFF 00001000 ................
0010:00520010 00000000 0000FE00 00100000 00002000 ............. ..
0010:00520020 00000200 00002000 00000124 7FFDEFFF ..... ..$......
0010:00520030 06080004 00000000 00000000 00000000 ................
0010:00520040 00000000 00520598 0000000F FFFFFFF8 ......R.........
0010:00520050 00520050 00520050 00520640 00000000 [email protected].....
0010:00520060 00000000 00000000 00000000 00000000 ................
0010:00520070 00000000 00000000 00000000 00000000 ................
0010:00520080 00000000 00000000 00000000 00000000 ................
0010:00520090 00000000 00000000 00000000 00000000 ................
0010:005200A0 00000000 00000000 00000000 00000000 ................
0010:005200B0 00000000 00000000 00000000 00000000 ................
0010:005200C0 00000000 00000000 00000000 00000000 ................
0010:005200D0 00000000 00000000 00000000 00000000 ................
0010:005200E0 00000000 00000000 00000000 00000000 ................
0010:005200F0 00000000 00000000 00000000 00000000 ................
0010:00520100 00000000 00000000 00000000 00000000 ................
0010:00520110 00000000 00000000 00000000 00000000 ................
0010:00520120 00000000 00000000 00000000 00000000 ................
0010:00520130 00000000 00000000 00000000 00000000 ................
0010:00520140 00000000 00000000 00000000 00000000 ................
0010:00520150 00000000 00000000 00000008 00000000 ................
0010:00520160 00000000 00000000 0000FFFF 00000000 ................
0010:00520170 00000000 00000000 00520730 00520730 ........0.R.0.R.
0010:00520180 00520180 00520180 00520188 00520188 ..R...R...R...R.
0010:00520190 005206A0 00520700 00520198 00520198 ..R...R...R...R.
0010:005201A0 005201A0 005201A0 005201A8 005201A8 ..R...R...R...R.
0010:005201B0 005201B0 005201B0 005201B8 005201B8 ..R...R...R...R.
0010:005201C0 005201C0 005201C0 005201C8 005201C8 ..R...R...R...R.
0010:005201D0 005201D0 005201D0 005201D8 005201D8 ..R...R...R...R.
0010:005201E0 005201E0 005201E0 005201E8 005201E8 ..R...R...R...R.
0010:005201F0 005201F0 005201F0 005201F8 005201F8 ..R...R...R...R.
0010:00520200 00520200 00520200 00520208 00520208 ..R...R...R...R.
0010:00520210 00520210 00520210 00520218 00520218 ..R...R...R...R.
0010:00520220 00520220 00520220 00520228 00520228 .R. .R.(.R.(.R.
0010:00520230 00520230 00520230 00520238 00520238 0.R.0.R.8.R.8.R.
0010:00520240 00520240 00520240 00520248 00520248 @[email protected].
0010:00520250 00520250 00520250 00520258 00520258 P.R.P.R.X.R.X.R.
0010:00520260 00520260 00520260 00520268 00520268 `.R.`.R.h.R.h.R.
0010:00520270 00520270 00520270 00520278 00520278 p.R.p.R.x.R.x.R.
0010:00520280 00520280 00520280 00520288 00520288 ..R...R...R...R.
0010:00520290 00520290 00520290 00520298 00520298 ..R...R...R...R.
0010:005202A0 005202A0 005202A0 005202A8 005202A8 ..R...R...R...R.
0010:005202B0 005202B0 005202B0 005202B8 005202B8 ..R...R...R...R.
0010:005202C0 005202C0 005202C0 005202C8 005202C8 ..R...R...R...R.
0010:005202D0 005202D0 005202D0 005202D8 005202D8 ..R...R...R...R.
0010:005202E0 005202E0 005202E0 005202E8 005202E8 ..R...R...R...R.
0010:005202F0 005202F0 005202F0 005202F8 005202F8 ..R...R...R...R.
0010:00520300 00520300 00520300 00520308 00520308 ..R...R...R...R.
0010:00520310 00520310 00520310 00520318 00520318 ..R...R...R...R.
0010:00520320 00520320 00520320 00520328 00520328 .R. .R.(.R.(.R.
0010:00520330 00520330 00520330 00520338 00520338 0.R.0.R.8.R.8.R.
0010:00520340 00520340 00520340 00520348 00520348 @[email protected].
0010:00520350 00520350 00520350 00520358 00520358 P.R.P.R.X.R.X.R.
0010:00520360 00520360 00520360 00520368 00520368 `.R.`.R.h.R.h.R.
0010:00520370 00520370 00520370 00520378 00520378 p.R.p.R.x.R.x.R.
0010:00520380 00520380 00520380 00520388 00520388 ..R...R...R...R.
0010:00520390 00520390 00520390 00520398 00520398 ..R...R...R...R.
0010:005203A0 005203A0 005203A0 005203A8 005203A8 ..R...R...R...R.
0010:005203B0 005203B0 005203B0 005203B8 005203B8 ..R...R...R...R.
0010:005203C0 005203C0 005203C0 005203C8 005203C8 ..R...R...R...R.
0010:005203D0 005203D0 005203D0 005203D8 005203D8 ..R...R...R...R.
0010:005203E0 005203E0 005203E0 005203E8 005203E8 ..R...R...R...R.
0010:005203F0 005203F0 005203F0 005203F8 005203F8 ..R...R...R...R.
0010:00520400 00520400 00520400 00520408 00520408 ..R...R...R...R.
0010:00520410 00520410 00520410 00520418 00520418 ..R...R...R...R.
0010:00520420 00520420 00520420 00520428 00520428 .R. .R.(.R.(.R.
0010:00520430 00520430 00520430 00520438 00520438 0.R.0.R.8.R.8.R.
0010:00520440 00520440 00520440 00520448 00520448 @[email protected].
0010:00520450 00520450 00520450 00520458 00520458 P.R.P.R.X.R.X.R.
0010:00520460 00520460 00520460 00520468 00520468 `.R.`.R.h.R.h.R.
0010:00520470 00520470 00520470 00520478 00520478 p.R.p.R.x.R.x.R.
0010:00520480 00520480 00520480 00520488 00520488 ..R...R...R...R.
0010:00520490 00520490 00520490 00520498 00520498 ..R...R...R...R.
0010:005204A0 005204A0 005204A0 005204A8 005204A8 ..R...R...R...R.
0010:005204B0 005204B0 005204B0 005204B8 005204B8 ..R...R...R...R.
0010:005204C0 005204C0 005204C0 005204C8 005204C8 ..R...R...R...R.
0010:005204D0 005204D0 005204D0 005204D8 005204D8 ..R...R...R...R.
0010:005204E0 005204E0 005204E0 005204E8 005204E8 ..R...R...R...R.
0010:005204F0 005204F0 005204F0 005204F8 005204F8 ..R...R...R...R.
0010:00520500 00520500 00520500 00520508 00520508 ..R...R...R...R.
0010:00520510 00520510 00520510 00520518 00520518 ..R...R...R...R.
0010:00520520 00520520 00520520 00520528 00520528 .R. .R.(.R.(.R.
0010:00520530 00520530 00520530 00520538 00520538 0.R.0.R.8.R.8.R.
0010:00520540 00520540 00520540 00520548 00520548 @[email protected].
0010:00520550 00520550 00520550 00520558 00520558 P.R.P.R.X.R.X.R.
0010:00520560 00520560 00520560 00520568 00520568 `.R.`.R.h.R.h.R.
0010:00520570 00520570 00520570 00520608 00000000 p.R.p.R...R.....
0010:00520580 00000000 00000000 00000000 00521000 ..............R.
0010:00520590 0000F000 00000000 005205A8 00000000 ..........R.....
0010:005205A0 00000000 00000000 005205B8 00000000 ..........R.....
0010:005205B0 00000000 00000000 005205C8 00000000 ..........R.....
0010:005205C0 00000000 00000000 005205D8 00000000 ..........R.....
0010:005205D0 00000000 00000000 005205E8 00000000 ..........R.....
0010:005205E0 00000000 00000000 005205F8 00000000 ..........R.....
0010:005205F0 00000000 00000000 00000000 00000000 ................
0010:00520600 00000000 00000000 77FCD640 FFFFFFFF [email protected]....
0010:00520610 00000000 00000000 00000030 00000000 ........0.......
0010:00520620 00000000 00000000 00000000 00000000 ................
0010:00520630 00000000 00000000 00000000 00000000 ................
0010:00520640 00C80008 00000100 FFEEFFEE 00000000 ................
0010:00520650 00520000 0000F000 00520000 00000010 ..R.......R.....
0010:00520660 00520680 00530000 0000000F 00000001 ..R...S.........
0010:00520670 00520588 00000000 00520728 00000000 ..R.....(.R.....
0010:00520680 00080003 00080100 41414141 41414141 ........AAAAAAAA
0010:00520690 41414141 00000041 00030003 00080000 AAAAA...........
0010:005206A0 005206D0 00520190 41414141 00000041 ..R...R.AAAAA...
0010:005206B0 00030003 00080100 41414141 41414141 ........AAAAAAAA
0010:005206C0 41414141 00000041 00030003 00080000 AAAAA...........
0010:005206D0 00520700 005206A0 41414141 00000041 ..R...R.AAAAA...
0010:005206E0 00030003 00080100 41414141 41414141 ........AAAAAAAA
0010:005206F0 41414141 00000041 00030003 00080000 AAAAA...........
0010:00520700 00520190 005206D0 41414141 00000041 ..R...R.AAAAA...
0010:00520710 00030003 00080100 41414141 41414141 ........AAAAAAAA
0010:00520720 41414141 00000041 0003011B 00081000 AAAAA...........
0010:00520730 00520178 00520178 41414141 00000041 x.R.x.R.AAAAA...
0010:00520740 00030118 00001000 00520178 00520178 ........x.R.x.R.
0010:00520750 00000000 00000000 00000000 00000000 ................
0010:00520760 00000000 00000000 00000000 00000000 ................
0010:00520770 00000000 00000000 00000000 00000000 ................
0010:00520780 00000000 00000000 00000000 00000000 ................
0010:00520790 00000000 00000000 00000000 00000000 ................
0010:005207A0 00000000 00000000 00000000 00000000 ................
0010:005207B0 00000000 00000000 00000000 00000000 ................
0010:005207C0 00000000 00000000 00000000 00000000 ................
0010:005207D0 00000000 00000000 00000000 00000000 ................
0010:005207E0 00000000 00000000 00000000 00000000 ................
0010:005207F0 00000000 00000000 00000000 00000000 ................
0010:00520800 00000000 00000000 00000000 00000000 ................
0010:00520810 00000000 00000000 00000000 00000000 ................
0010:00520820 00000000 00000000 00000000 00000000 ................
0010:00520830 00000000 00000000 00000000 00000000 ................
0010:00520840 00000000 00000000 00000000 00000000 ................
0010:00520850 00000000 00000000 00000000 00000000 ................
0010:00520860 00000000 00000000 00000000 00000000 ................
0010:00520870 00000000 00000000 00000000 00000000 ................
0010:00520880 00000000 00000000 00000000 00000000 ................
0010:00520890 00000000 00000000 00000000 00000000 ................
0010:005208A0 00000000 00000000 00000000 00000000 ................
0010:005208B0 00000000 00000000 00000000 00000000 ................
0010:005208C0 00000000 00000000 00000000 00000000 ................
0010:005208D0 00000000 00000000 00000000 00000000 ................
0010:005208E0 00000000 00000000 00000000 00000000 ................
0010:005208F0 00000000 00000000 00000000 00000000 ................
0010:00520900 00000000 00000000 00000000 00000000 ................
0010:00520910 00000000 00000000 00000000 00000000 ................
0010:00520920 00000000 00000000 00000000 00000000 ................
0010:00520930 00000000 00000000 00000000 00000000 ................
0010:00520940 00000000 00000000 00000000 00000000 ................
0010:00520950 00000000 00000000 00000000 00000000 ................
0010:00520960 00000000 00000000 00000000 00000000 ................
0010:00520970 00000000 00000000 00000000 00000000 ................
0010:00520980 00000000 00000000 00000000 00000000 ................
0010:00520990 00000000 00000000 00000000 00000000 ................
0010:005209A0 00000000 00000000 00000000 00000000 ................
0010:005209B0 00000000 00000000 00000000 00000000 ................
0010:005209C0 00000000 00000000 00000000 00000000 ................
0010:005209D0 00000000 00000000 00000000 00000000 ................
0010:005209E0 00000000 00000000 00000000 00000000 ................
0010:005209F0 00000000 00000000 00000000 00000000 ................
0010:00520A00 00000000 00000000 00000000 00000000 ................
0010:00520A10 00000000 00000000 00000000 00000000 ................
0010:00520A20 00000000 00000000 00000000 00000000 ................
0010:00520A30 00000000 00000000 00000000 00000000 ................
0010:00520A40 00000000 00000000 00000000 00000000 ................
0010:00520A50 00000000 00000000 00000000 00000000 ................
0010:00520A60 00000000 00000000 00000000 00000000 ................
0010:00520A70 00000000 00000000 00000000 00000000 ................
0010:00520A80 00000000 00000000 00000000 00000000 ................
0010:00520A90 00000000 00000000 00000000 00000000 ................
0010:00520AA0 00000000 00000000 00000000 00000000 ................
0010:00520AB0 00000000 00000000 00000000 00000000 ................
0010:00520AC0 00000000 00000000 00000000 00000000 ................
0010:00520AD0 00000000 00000000 00000000 00000000 ................
0010:00520AE0 00000000 00000000 00000000 00000000 ................
0010:00520AF0 00000000 00000000 00000000 00000000 ................
0010:00520B00 00000000 00000000 00000000 00000000 ................
0010:00520B10 00000000 00000000 00000000 00000000 ................
0010:00520B20 00000000 00000000 00000000 00000000 ................
0010:00520B30 00000000 00000000 00000000 00000000 ................
0010:00520B40 00000000 00000000 00000000 00000000 ................
0010:00520B50 00000000 00000000 00000000 00000000 ................
0010:00520B60 00000000 00000000 00000000 00000000 ................
0010:00520B70 00000000 00000000 00000000 00000000 ................
0010:00520B80 00000000 00000000 00000000 00000000 ................
0010:00520B90 00000000 00000000 00000000 00000000 ................
0010:00520BA0 00000000 00000000 00000000 00000000 ................
0010:00520BB0 00000000 00000000 00000000 00000000 ................
0010:00520BC0 00000000 00000000 00000000 00000000 ................
0010:00520BD0 00000000 00000000 00000000 00000000 ................
0010:00520BE0 00000000 00000000 00000000 00000000 ................
0010:00520BF0 00000000 00000000 00000000 00000000 ................
0010:00520C00 00000000 00000000 00000000 00000000 ................
0010:00520C10 00000000 00000000 00000000 00000000 ................
0010:00520C20 00000000 00000000 00000000 00000000 ................
0010:00520C30 00000000 00000000 00000000 00000000 ................
0010:00520C40 00000000 00000000 00000000 00000000 ................
0010:00520C50 00000000 00000000 00000000 00000000 ................
0010:00520C60 00000000 00000000 00000000 00000000 ................
0010:00520C70 00000000 00000000 00000000 00000000 ................
0010:00520C80 00000000 00000000 00000000 00000000 ................
0010:00520C90 00000000 00000000 00000000 00000000 ................
0010:00520CA0 00000000 00000000 00000000 00000000 ................
0010:00520CB0 00000000 00000000 00000000 00000000 ................
0010:00520CC0 00000000 00000000 00000000 00000000 ................
0010:00520CD0 00000000 00000000 00000000 00000000 ................
0010:00520CE0 00000000 00000000 00000000 00000000 ................
0010:00520CF0 00000000 00000000 00000000 00000000 ................
0010:00520D00 00000000 00000000 00000000 00000000 ................
0010:00520D10 00000000 00000000 00000000 00000000 ................
0010:00520D20 00000000 00000000 00000000 00000000 ................
0010:00520D30 00000000 00000000 00000000 00000000 ................
0010:00520D40 00000000 00000000 00000000 00000000 ................
0010:00520D50 00000000 00000000 00000000 00000000 ................
0010:00520D60 00000000 00000000 00000000 00000000 ................
0010:00520D70 00000000 00000000 00000000 00000000 ................
0010:00520D80 00000000 00000000 00000000 00000000 ................
0010:00520D90 00000000 00000000 00000000 00000000 ................
0010:00520DA0 00000000 00000000 00000000 00000000 ................
0010:00520DB0 00000000 00000000 00000000 00000000 ................
0010:00520DC0 00000000 00000000 00000000 00000000 ................
0010:00520DD0 00000000 00000000 00000000 00000000 ................
0010:00520DE0 00000000 00000000 00000000 00000000 ................
0010:00520DF0 00000000 00000000 00000000 00000000 ................
0010:00520E00 00000000 00000000 00000000 00000000 ................
0010:00520E10 00000000 00000000 00000000 00000000 ................
0010:00520E20 00000000 00000000 00000000 00000000 ................
0010:00520E30 00000000 00000000 00000000 00000000 ................
0010:00520E40 00000000 00000000 00000000 00000000 ................
0010:00520E50 00000000 00000000 00000000 00000000 ................
0010:00520E60 00000000 00000000 00000000 00000000 ................
0010:00520E70 00000000 00000000 00000000 00000000 ................
0010:00520E80 00000000 00000000 00000000 00000000 ................
0010:00520E90 00000000 00000000 00000000 00000000 ................
0010:00520EA0 00000000 00000000 00000000 00000000 ................
0010:00520EB0 00000000 00000000 00000000 00000000 ................
0010:00520EC0 00000000 00000000 00000000 00000000 ................
0010:00520ED0 00000000 00000000 00000000 00000000 ................
0010:00520EE0 00000000 00000000 00000000 00000000 ................
0010:00520EF0 00000000 00000000 00000000 00000000 ................
0010:00520F00 00000000 00000000 00000000 00000000 ................
0010:00520F10 00000000 00000000 00000000 00000000 ................
0010:00520F20 00000000 00000000 00000000 00000000 ................
0010:00520F30 00000000 00000000 00000000 00000000 ................
0010:00520F40 00000000 00000000 00000000 00000000 ................
0010:00520F50 00000000 00000000 00000000 00000000 ................
0010:00520F60 00000000 00000000 00000000 00000000 ................
0010:00520F70 00000000 00000000 00000000 00000000 ................
0010:00520F80 00000000 00000000 00000000 00000000 ................
0010:00520F90 00000000 00000000 00000000 00000000 ................
0010:00520FA0 00000000 00000000 00000000 00000000 ................
0010:00520FB0 00000000 00000000 00000000 00000000 ................
0010:00520FC0 00000000 00000000 00000000 00000000 ................
0010:00520FD0 00000000 00000000 00000000 00000000 ................
0010:00520FE0 00000000 00000000 00000000 00000000 ................
0010:00520FF0 00000000 00000000 00000000 00000000 ................

整个堆可以分为两部分,首先是一个巨大的Header,从00520000一直到00520680(这么说是因为从00520680开始处就已经是用来动态申请和释放的内存和它的结构了,这样分并不一定正确),最开始的部分是各种信息吧。从00520178开始是一个很大的结构数组,这个结构数组大约有128个数组元素。每个数组元素长8个字节,是一个结构。这个结构由两部分组成。可以这样定义它:

struct _free_memory_link_node
{
_free_memory_link_node* pNextFreeMemLinkNode;
_free_memory_link_node* pPrevFreeMemLinkNode;
};
这个结构由2个指针组成,用来指向空闲的内存块。后面会有更详细的描述。这128个这种结构,是用来指向128种不同大小范围的空闲内存块,以加速寻找。这个很大的结构数组之后,又是些不知道是什么的东西。头部就是这些。

接着是用于动态申请和释放的内存部分了,这些内存有两种结构,

第一种,是被分配使用的,

+-----------------------------------------------------------+ 
| 8 byte   |                buf                             | 
+-----------------------------------------------------------+ 
|信息和标志 |                用户内存                        |

首先是8个字节的信息和标志,具体内容不明。之后的内存就是HeapAlloc返回的内存地址。

第二种,是空闲的内存,

+-----------------------------------------------------------+ 
| 8 bytes  |  8 bytes  |     buf                            | 
+-----------------------------------------------------------+ 
|信息和标志 | 双指针结构 |    用户内存                        |

首先仍是8个字节的信息和标志,(很有可能有标志表明是否空闲,我看到很象,但还不确定)
接着是8个字节的双指针结构,就是前面所说的 _free_memory_link_node 结构。注意的是后面的内存如果是被释放的,里面的内容并没有被清零,不要被迷惑。每个空闲的内存根据它的大小会和Heap Header 中的空闲链表头所开始的一个链表连在一起,这是一个双向循环链表,根据上面所给的第二次getch()后softice中的内容,可以很容易构造出这个链表来。太费时间了,我就不配插图了。当 Heap Header 中的某个空闲块大小范围的空闲链表头的那个节点的两个指针指向自己时,说明这个这个大小范围的空闲块为0。这也就是为什么刚开始我们看到大片大片的两个指针,指向自己的8个字节,只因为刚开始还是一整块空闲内存,没有什么小块的空闲内存,各个范围的链表都没有节点。

空闲块是需要使用链表连起来的,这样才能找到每个空闲块,以用来再申请的时候使用。可以估计到,每次释放一个内存块时,系统(这么叫合适吗?)还需要判断是否适合临近的空闲块紧挨着,如果是的话,会进行合并。释放时系统还需要根据大小把这个空闲块插入相应大小范围的双向链表中的合适位置。使用的内存块儿是不需要指针链接起来的,因为他们在分配时给程序返回了地址,程序使用这个地址的内存。没有理由要把他们链接起来。从中我们也可以看出,堆上的内存的一些必要的处理确实比较麻烦,会导致相对较慢。

再看一下那128个链表,各自的空闲块的大小范围吧。

为了测试不同大小范围的空闲块,会链接到128个中的哪个链表上,我写了下面的小程序。

程序的原理我就不解释了,你输入指定大小,程序申请,并释放这个大小的内存块,形成一个这个大小的空闲内存块,然后根据结构的位置,得到指针,然后看指向何处。

#include <windows.h> 
#include <stdio.h> 
#include <conio.h>

void main()
{
Start:
HANDLE hHeap;

hHeap=HeapCreate(NULL,0x1000,0x10000); 

int size;
printf("Type HeapAlloc Size (HEX): ");
scanf("%x",&size);
printf("\nSize (HEX): %x Byte\n",size);

printf("\n(%x-1)/8 *8= %08x\n",size,((size-1)/8*8));

char * buf1,*buf2;

buf1 = (char*)HeapAlloc(hHeap, 0, size); 

buf2 = (char*)HeapAlloc(hHeap, 0, 16);

HeapFree(hHeap, 0, buf1);

int* addr;
addr = (int*)buf1;
printf("Pointer: %08x\n",*addr);

HeapFree(hHeap, 0, buf2);

HeapDestroy(hHeap);

printf("\n\n");

goto Start;

}

经过测试,释放1-8个字节形成的空闲内存块,指向 00520188 所开始的那个双向链表。
9-16个字节的空闲内存块,指向 00520190,17-24个字节的空闲内存块,指向 00520198,
25-32个字节的空闲内存块,指向 005201a0...依此类推,每个都是8个字节的范围,
直到0x3e9-0x3f0(1001-1008)个字节的空闲内存块。0x3e9-0x3f0 指向 00520570。
符合这一规则(8个字节一个范围段)的从1-8开始直到1001-1008,共126项。
凡是超过1008个字节的空闲内存块,将链接到一个特殊的双向链表,这个双向链表的开始在 00520178。也就刚开始就会注意到的一个地址。(只因为刚开始一大块的时候,超过了1008个字节)。这样就有127项我们知道这个双向链表所链内存的大小范围了。还有一个00520180处的没有仔细观察。

还有要说的一点就是,比如你申请了5个字节的内存,那么系统会给你8个字节的内存,比如你放AAAAA,那么实际放了AAAA A000 ,这样做的理由是我们使用的是32bit cpu 以4个字节为单位是有理由的。但是根据前面的8个字节的范围,会不会是以8个字节为单位使用内存,我没去试,这个并不难,设计个小试验吧。

基本就是这些了。

    第四 还有很多工作没有做

    本文只是大概介绍了堆中的一些结构,还有很多东西可以去试。设计一些试验,来了解各种结构中的内容和它的意义。比如设计试验测试哪些是标志位,以及不同值表示的含义,这个试验就很容易设计。 对堆如果有什么更多的了解,请您受累也告诉我,salute。

    关于Win2k堆的实现和里面的数据结构,没有任何的官方描述(差不多可以这么说吧),非官方的东西也只要几篇关于堆溢出的文章提到了一点,还充满了错误(差不错可以这么说吧)。本文通过分析,试验和猜测,来获得知识,同样可能充满了错误,大家多保重。我最近在学习Windows系统,如果有哪位有兴趣,有时间,也有能力的话非常非常欢迎和我联系,或许能互相帮助。本文只是半成品,很多地方没有力求详尽,也非常非常欢迎大家对本文进行补充,设计更多的测试,对于堆有更多的了解,一定也告诉我。发现错误也一定告诉我,欢迎大家指导,多谢观赏。

欢迎大家来这里看看 http://jiurl.cosoft.org.cn/forum/ http://jiurl.yeah.net/

 

本文地址:http://com.8s8s.com/it/it1747.htm