Heap Feng Shui in JavaScript

JavaScript中的堆风水

作者：Alexander Sotirov asotirov@determina.com

Introduction

导言

The exploitation of heap corruption vulnerabilities on the Windows platform has become increasingly more difficult since the introduction of XP SP2. Heap protection features such as safe unlinking and heap cookies have been successful in stopping most generic heap exploitation techniques. Methods for bypassing the heap protection exist, but they require a great degree of control over the allocation patterns of the vulnerable application.

自从WindowsXP SP2发布之后，Windows平台上的堆腐烂/堆破坏（heap corruption，本文中统一采用堆腐烂的译法）漏洞的利用难度是越来越高了。由于微软在堆中加入了诸如“safe unlink”以及“cookies”的堆保护功能，大多数传统的堆腐烂的利用技术几乎在一夜之间就全部败下阵来。当然，能绕过这些堆保护机制的exploit技术也不是没有，但是这些技术都需要我们能很好的控制存在漏洞的程序中堆分配的参数。

This paper introduces a new technique for precise manipulation of the browser heap layout using specific sequences of JavaScript allocations. We present a JavaScript library with functions for setting up the heap in a controlled state before triggering a heap corruption bug. This allows us to exploit very difficult heap corruption vulnerabilities with great reliability and precision.

本文介绍了一种全新的技术，它通过在JavaScript中执行一系列的堆分配和释放操作，精确的控制了浏览器的堆。另外我还提供了一个完成上述功能的JavaScript函数库，这样我们就能很可靠的，而且很精确的利用一些很难利用的堆腐烂漏洞了。

We will focus on Internet Explorer exploitation, but the general techniques presented here are potentially applicable to any other browser or scripting environment.

虽然本文是讨论IE中的exploit技术的，但是你也可以把这一技术引伸到其他的浏览器或者脚本执行环境中。

Previous work

预备作业

The most widely used browser heap exploitation technique is the heap spraying method developed by SkyLined for his Internet Explorer IFRAME exploit. This technique uses JavaScript to create multiple strings containing a NOP slide and shellcode. The JavaScript runtime stores the data for each string in a new block on the heap. Heap allocations usually start at the beginning of the address space and go up. After allocating 200MB of memory for the strings, any address between 50MB and 200MB is very likely to point at the NOP slide. Overwriting a return address or a function pointer with an address in this range will lead to a jump to the NOP slide and shellcode execution.

现在最流行的堆exploit技术是SkyLined为了利用Internet Explorer IFRAME漏洞而开发的堆喷射（heap spraying，本文中采用堆喷射的译法，呵呵比较形象，申请很多内存写上shellcode，有点象用水枪喷水，喷的到处都是水的样子J）技术。这一技术用JavaScript脚本创建了很多个string对象，在string对象中写入一个长长的NOP链以及紧接着NOP链的一小段shellcode。JavaScript runtime会把这些string对象都存储在堆中。由于堆中的数据是不断向内存高址增长的。在大约分配了200MB的内存给这些string对象之后，在50MB～200MB这段内存中，随意取出一个地址，上面写着的很可能就是NOP链中的一环。把某个返回地址覆盖掉，变成这个随意取出的地址之后，我们就能跳到这个NOP链上，最终执行Shellcode。

The following JavaScript code illustrates this technique:

下面是一段堆喷射技术的JavaScript的演示代码：

var nop = unescape("%u9090%u9090");

// Create a 1MB string of NOP instructions followed by shellcode:

//

// malloc header   string length   NOP slide   shellcode   NULL terminator

// 32 bytes        4 bytes         x bytes     y bytes     2 bytes

while (nop.length <= 0x100000/2) nop += nop;

nop = nop.substring(0, 0x100000/2 - 32/2 - 4/2 - shellcode.length - 2/2);

var x = new Array();

// Fill 200MB of memory with copies of the NOP slide and shellcode

for (var i = 0; i < 200; i++) {

    x[i] = nop + shellcode;

A slight variation of this technique can be used to exploit vtable and object pointer overwrites. If an object pointer is used for a virtual function call, the compiler generates code similar to the following:

对堆喷射技术的一个小小的改进是我们可以不改写函数的返回地址，而是去改写对象指针或者是对象的虚函数表。如果某个对象中使用了虚函数，那么当我们用这个对象的指针去调用这个对象的虚函数时，编译器一般会生成下面这段代码：

mov ecx, dword ptr [eax]    ; get the vtable address

push eax                    ; pass C++ this pointer as the first argument

call dword ptr [ecx+08h]    ; call the function at offset 0x8 in the vtable

The first four bytes of every C++ object contain a pointer to the vtable. To exploit an overwritten object pointer, we need to use an address that points to a fake object with a fake vtable that contains pointers to the shellcode. It turns out that setting up this kind of structure in memory is not as hard as it seems. The first step is to use a sequence of 0xC bytes for the NOP slide and overwrite the object pointer with an address that points to the slide. The virtual table pointer in the beginning of the fake object will be a dword from the NOP slide that points to 0x0C0C0C0C. The memory at this address will also contain 0xC bytes from the NOP slide, and all virtual function pointers in the fake vtable will point back to the slide at 0x0C0C0C0C. Calling any virtual function of the object will result in a call to the shellcode.

在每个C++对象的前4个直接中都存放了一个指向虚函数表的指针。要利用虚函数表进行exploit，我们需要把一个指向我们伪造的虚函数表的指针覆盖到对象的前4个字节，然后在我们伪造的虚函数表中写入一个指向shellcode的指针。看上去要完成这个任务还是比较简单的。首先，我们把一串（要偶数个）0x0C当成NOP链（译注：0x0C0C会被当成一条指令“or al, 0Ch”）。然后用指向这串NOP链的指针覆盖掉对象的指针。这样这个 “假冒的”对象的的虚函数表就成了在0x0C0C0C0C上的那张表，这时如果地址0x0C0C0C0C上也写上了0x0C组成的NOP链（这一点很容易做到，因为0x0C0C0C0C不算太高，大量分配string对象很容易就能“占领”这个地址），那么调用任何对象的虚函数都会绕回这串0x0C组成的NOP链，最终执行我们的shellcode。

The sequence of dereferences is show below:

如下图所示：

object pointer   -->   fake object   -->   fake vtable     -->     fake virtual function

addr: xxxx             addr: yyyy          addr: 0x0C0C0C0C        addr: 0x0C0C0C0C

data: yyyy             data: 0x0C0C0C0C    data: +0 0x0C0C0C0C     data: nop slide

                                                 +4 0x0C0C0C0C           shellcode

                                                 +8 0x0C0C0C0C

The key observation from SkyLined's technique is that the system heap is accessible from JavaScript code. This paper will take this idea even further and will explore ways to completely control the heap with JavaScript.

SkyLined的堆喷射方法之所以能够成功，关键的一点就在于在JavaScript中的脚本代码实际上是能够访问系统堆的。现在我们要走的更远一些，我们要利用JavaScript完全控制系统的堆。

Motivation

动机

The heap spraying technique described above is surprisingly effective, but it alone is not sufficient for reliable heap exploitation. There are two reasons for this.

堆喷射技术以其令人震惊的有效性而闻名于世，但出于下面这2个原因，我认为它还是不算很可靠。

On Windows XP SP2 and later systems it is easier to exploit heap corruption vulnerabilities by overwriting application data on the heap, rather than corrupting the internal malloc data structures. This is because the heap allocator performs additional verification of the malloc chunk headers and the doubly-linked lists of free blocks, which renders the standard heap exploitation methods ineffective. As a result, many exploits use the heap spraying technique to fill the address space with shellcode and then try to overwrite an object or vtable pointer on the heap. The heap protection in the operating system does not extend to the application data stored in memory. The state of the heap is hard to predict, however, and there is no guarantee that the overwritten memory will always contain the same data. In this case the exploit might fail.

对于Windows XP SP2之后的微软的操作系统来说，由于堆中内存空间的分配函数（HeapAlloc）在其分配的内存块（chunk）的管理头部中加入了cookie校验信息并且实现了空闲内存块的双向链表的安全删除技术，使得我们利用堆腐烂技术腐烂(或称破坏/覆盖)内存块的管理头部中的数据变得非常困难。这就使一些传统的堆腐烂技术一夜之间就全部落伍了。这样就迫使我们要想办法腐烂内存块中应用程序填写的数据，因为操作系统实际上是管不着应用程序到底要往chunk中写些什么，所以根本无法把现有的一些堆保护技术运用到chunk中的数据。这样做的结果是，有许多漏洞利用程序都使用了堆喷射技术：用shellcode填满很大的一个内存区域，然后试图覆盖堆中的一个对象或者虚函数表的指针。但是堆中内存的状态是很难预测的，也就是说，谁也不能保证，上一次成功利用时的堆的状态会在下一次利用时能重复出现。所以有时，使用堆喷射技术的利用会失败。

One example of this is the ie_webview_setslice exploit in the Metasploit Framework. It triggers a heap corruption vulnerability repeatedly, hoping to trash enough of the heap to cause a jump to random heap memory. It shouldn't come as a surprise that the exploit is not always successful.

这方面的一个例子就是Metasploit Framework 中的ie_webview_setslice漏洞的exploit。在这个exploit中我们不断地触发一个堆腐烂漏洞，希望以此来浪费掉足够多的堆中的空间，使程序能成功的跳到一个随机的堆中的地址。正如我们所见，这个exploit并不是每次都能成功的。

The second problem is the trade-off between the reliability of an exploit and the amount of system memory consumed by heap spraying. If an exploit fills the entire address space of the browser with shellcode, any random jump would be exploitable. Unfortunately, on systems with insufficient physical memory, heap spraying will result in heavy use of the paging file and slow system performance. If the user closes the browser before the heap spraying is complete, the exploit will fail.

堆喷射技术的另一个问题在于：你准备申请多少内存来写shellcode？答案当然是“韩信点兵，多多益善”罗。我们考虑一下比较极端的情况：如果我们把整个浏览器的内存地址空间中都写满shellcode，那么我随便跳到任何一个地方都能激活shellcodeJ但是你想过没有，要消耗多少系统物理内存资源？随之而来的页交换又将带来多少额外的开销，降低多少系统资源。老实说，我要是那个倒霉的被攻击用户，不等到你的shellcode运行，也许就已经先不耐烦而直接关闭浏览器了。这样的攻击又怎么可能成功呢？所以到底应该申请多少内存空间写shellcode就变成了一件很有讲究的事了。

This paper presents a solution to both of these problems, making reliable and precise exploitation possible.

本文为上述这2个问题提出一个解决方案，提出一种新的可靠而且精准的利用方法。

Internet Explorer heap internals

Overview

There are three main components of Internet Explorer that allocate memory typically corrupted by browser heap vulnerabilities. The first one is the MSHTML.DLL library, responsible for managing memory for HTML elements on the currently displayed page. It allocates memory during the initial rendering of the page, and during any subsequent DHTML manipulations. The memory is allocated from the default process heap and is freed when a page is closed or HTML elements are destroyed.

在IE中（本文中涉及的浏览器堆腐烂漏洞）担负分配内存任务的主要是3个组件。第一个是MSHTML.DLL这个动态链接库，它负责管理用于当前显示的页（以及随之而来的DHTML操作）中HTML元素的内存空间的分配和回收。这个DLL在进程默认堆中分配内存空间，并且在当前页面被关闭，或者HTML元素析构（destroy）时回收空间。

The second component that manages memory is the JavaScript engine in JSCRIPT.DLL. Memory for new JavaScript objects is allocated from a dedicated JavaScript heap, with the exception of strings, which are allocated from the default process heap. Unreferenced objects are destroyed by the garbage collector, which runs when the total memory consumption or the number of objects exceed a certain threshold. The garbage collector can also be triggered explicitly by calling the CollectGarbage() function.

第二个用于管理内存空间的组件是JSCRIPT.DLL中的JavaScript引擎。但我们new一个JavaScript对象时，这个对象将被分配到一个专门的JavaScript堆中。string对象除外，string对象是被分配到进程默认堆里去的。一旦某个对象不再被引用了，垃圾回收机制就会析构这个对象。这个垃圾回收机制会在2种情况下被激活，一种是在总的内存消耗或者对象的总数超过了某个极限的时候，再有就是我们显式的调用CollectGarbage()函数的时候。

The final component in most browser exploits is the ActiveX control that causes heap corruption. Some ActiveX controls use a dedicated heap, but most allocate and corrupt memory on the default process heap.

最后一个组件是ActiveX控制器，这个组件经常会出现堆腐烂的问题（至少在本文中漏洞是在ActiveX控制器中的）。有些ActiveX控制器会使用一个专用的堆，但是大多数ActiveX控制器则使用进程默认堆。

An important observation is that all three components of Internet Explorer use the same default process heap. This means that allocating and freeing memory with JavaScript changes the layout of the heap used by MSHTML and ActiveX controls, and a heap corruption bug in an ActiveX control can be used to overwrite memory allocated by the other two browser components.

我们必须注意到一个重要的事实：上述三个IE组件都是使用同一个进程默认堆的。这也就是说：在JavaScript中的一些堆分配动作会直接影响到MSHTML和ActiveX控制器所使用的堆的状况，而一个ActiveX控制器中的堆腐烂bug也可以用来覆盖分配给HTML元素或者JavaScript string对象的内存空间。

JavaScript strings

The JavaScript engine allocates most of its memory with the MSVCRT malloc() and new() functions, using a dedicated heap created during CRT initialization. One important exception is the data for JavaScript strings. They are stored as BSTR strings, a basic string type used by the COM interface. Their memory is allocated from the default process heap by the SysAllocString family of functions in OLEAUT32.DLL.

在JavaScript引擎中绝大多数的内存分配是使用MSVCRT中的malloc()和new()函数实现的。用这2个函数分配的空间都是位于CRT初始化时创建的一个专用的堆中的，但是一个比较重要的例外时JavaScript string对象。JavaScript的string对象是以BSTR string格式（一种用于COM接口的基本string类型）存储的，它所需的空间是用OLEAUT32.DLL中的SysAllocString系列函数分配到进程默认堆中的。

Here is a typical backtrace from a string allocation in JavaScript:

下面给出的是一个JavaScript中分配一个string对象的调用回溯关系：

ChildEBP RetAddr  Args to Child

0013d26c 77124b52 77606034 00002000 00037f48 ntdll!RtlAllocateHeap+0xeac

0013d280 77124c7f 00002000 00000000 0013d2a8 OLEAUT32!APP_DATA::AllocCachedMem+0x4f

0013d290 75c61dd0 00000000 00184350 00000000 OLEAUT32!SysAllocStringByteLen+0x2e

0013d2a8 75caa763 00001ffa 0013d660 00037090 jscript!PvarAllocBstrByteLen+0x2e

0013d31c 75caa810 00037940 00038178 0013d660 jscript!JsStrSubstrCore+0x17a

0013d33c 75c6212e 00037940 0013d4a8 0013d660 jscript!JsStrSubstr+0x1b

0013d374 75c558e1 0013d660 00000002 00038988 jscript!NatFncObj::Call+0x41

0013d408 75c5586e 00037940 00000000 00000003 jscript!NameTbl::InvokeInternal+0x218

0013d434 75c62296 00037940 00000000 00000003 jscript!VAR::InvokeByDispID+0xd4

0013d478 75c556c5 00037940 0013d498 00000003 jscript!VAR::InvokeByName+0x164

0013d4b8 75c54468 00037940 00000003 0013d660 jscript!VAR::InvokeDispName+0x43

0013d4dc 75c54d1a 00037940 00000000 00000003 jscript!VAR::InvokeByDispID+0xfb

0013d6d0 75c544fa 0013da80 00000000 0013d7ec jscript!CScriptRuntime::Run+0x18fb

To allocate a new string on the heap, we need to create a new JavaScript string object. We cannot simply assign string literal to a new variable, because this does not create a copy of the string data. Instead, we need to concatenate two strings or use the substr function. For example:

要在堆中分配一个string对象，我们当然首先要创建一个新的JavaScript string对象。但是简单的声明一个新的变量并不会在堆中分配一块空间出来，因为这并不会创建string的一份拷贝，要想达到我们的目的，我们需要连接2个string或者使用substr()函数，如下例：

var str1 = "AAAAAAAAAAAAAAAAAAAA";  // doesn't allocate a new string

var str2 = str1.substr(0, 10);      // allocates a new 10 character string

var str3 = str1 + str2;             // allocates a new 30 character string

BSTR strings are stored in memory as a structure containing a four-byte size field, followed by the string data as 16-bit wide characters, and a 16-bit null terminator. The str1 string from the example above will have the following representation in memory:

BSTR string在内存中的结构类似于一个结构体，它包括一个4字节的大小的域（表示string的长度），紧接着string的内容（每字符16-bit），最后以一个NULL结尾（16-bit）。如下图所示：

string size | string data                                                 | null terminator

4 bytes     | length / 2 bytes                                            | 2 bytes

            |                                                             |

14 00 00 00 | 41 00 41 00 41 00 41 00 41 00 41 00 41 00 41 00 41 00 41 00 | 00 00

We can use the following two formulas to calculate how many bytes will be allocated for a string, or how long a string must be to allocate a certain number of bytes:

下面给出2个公式，分别用于在已知string长度的情况下计算string将要被分配到的内存大小，以及在已知需要分配内存大小的情况下计算需要一个多长的string。

bytes = len * 2 + 6

len = (bytes - 6) / 2

The way strings are stored allows us to write a function that allocates a memory block of an arbitrary size by allocating a new string. The code will calculate the required string length using the len = (bytes-6)/2 formula, and call substr to allocate a new string of that length. The string will contain data copied from the padding string. If we want to put specific data into the new memory block, we just need to initialize the padding string with it beforehand.

知道了string的存储方式，我们就能写出一个函数来分配我们所希望的任意大小的内存块的函数了。我们可以用len = (bytes-6)/2这个公式计算出分配我们所需大小的内存块需要的string的长度，然后调用substr()函数来分配空间。当然一般情况下（比如下面这个示例），新分配到的内存空间会被padding的内容，也就是‘A’填充，如果我们需要控制内存块中的数据的话，我们也可以根据我们的需要去初始化padding。

// Build a long string with padding data

padding = "AAAA"

while (padding.length < MAX_ALLOCATION_LENGTH)

    padding = padding + padding;

// Allocate a memory block of a specified size in bytes

function alloc(bytes) {

    return padding.substr(0, (bytes-6)/2);

Garbage collection

垃圾收集机制

To manipulate the browser heap layout it is not enough to be able to allocate memory blocks of an arbitrary size, we also need a way to free them. The JavaScript runtime uses a simple mark-and-sweep garbage collector, the most detailed description of which is in a post on Eric Lippert's blog.

要完全控制浏览器的堆，光能随意分配任意大小的内存空间是不够的，我们还要能随意释放已分配到的内存空间。（不像C/C++语言中程序员是显式调用delete/free之类的函数）在JavaScript runtime中是使用一种简单的mark-and-sweep（不知道有没有标准的译名，古存疑，保留英语原文）的垃圾处理机制来释放已经不被使用的内存空间的，在Eric Lippert的blog里有详细的细节描述。

Garbage collection is triggered by various heuristics, such as the number of objects created since the last run. The mark-and-sweep algorithm identifies all unreferenced objects in the JavaScript runtime and destroys them. When a string object is destroyed, its data is freed by calling SysFreeString in OLEAUT32.DLL. This is a backtrace from the garbage collector:

（JavaScript中）垃圾处理机制可能会被各种不同的条件（比如可能是对象的数量太多了）所触发。mark-and-sweep算法会标识出JavaScript runtime所有已经不被引用了的对象，并且析构这些对象。当垃圾处理机制析构一个string对象的时候，垃圾处理机制会调用OLEAUT32.DLL中的SysFreeString 函数来释放string对象所占的内存空间。下面给出的是JavaScript中实现垃圾回收机制的函数调用的回溯关系：

ChildEBP RetAddr  Args to Child

0013d324 774fd004 00150000 00000000 001bae28 ntdll!RtlFreeHeap

0013d338 77124ac8 77606034 001bae28 00000008 ole32!CRetailMalloc_Free+0x1c

0013d358 77124885 00000006 00008000 00037f48 OLEAUT32!APP_DATA::FreeCachedMem+0xa0

0013d36c 77124ae3 02a8004c 00037cc8 00037f48 OLEAUT32!SysFreeString+0x56

0013d380 75c60f15 00037f48 00037f48 75c61347 OLEAUT32!VariantClear+0xbb

0013d38c 75c61347 00037cc8 000378a0 00036d40 jscript!VAR::Clear+0x5d

0013d3b0 75c60eba 000378b0 00000000 000378a0 jscript!GcAlloc::ReclaimGarbage+0x65

0013d3cc 75c61273 00000002 0013d40c 00037c10 jscript!GcContext::Reclaim+0x98

0013d3e0 75c99a27 75c6212e 00037940 0013d474 jscript!GcContext::Collect+0xa5

0013d3e4 75c6212e 00037940 0013d474 0013d40c jscript!JsCollectGarbage+0x10

To free one of the strings we've allocated, we need to delete all references to it and run the garbage collector. Fortunately, we don't have to wait for one of the heuristics to trigger it, because the JavaScript implementation in Internet Explorer provides a CollectGarbage() function which forces the garbage collector to run immediately. The use of this function is shown in the code below:

要释放掉某个string对象所占的内存空间，我们首先要删除掉所有对这个string对象的引用，然后运行垃圾处理机制。对我们来说幸运的是，我们不需要再去创建很多对象或者分配很多空间以构造一个能出发垃圾处理机制的情况。在IE的JavaScript实现中有一个CollectGarbage()函数，调用这个函数我们就能立即强制垃圾处理机制。如下面这段代码：

var str;

// We need to do the allocation and free in a function scope, otherwise the

// garbage collector will not free the string.

//我们必须在同一个函数的作用域中完成分配和释放string对象的动作，否则垃圾处理机制将不会释放string对象

function alloc_str(bytes) {

    str = padding.substr(0, (bytes-6)/2);

function free_str() {

    str = null;

    CollectGarbage();

alloc_str(0x10000);     // allocate memory block

free_str();             // free memory block

The code above allocates a 64KB memory block and frees it, demonstrating our ability to perform arbitrary allocations and frees on the default process heap. We can free only blocks that were allocated by us, but even with that restriction we still have a great degree of control over the heap layout.

上面这段代码将分配64KB的一个内存块，并且释放它。这段代码演示了如何在进程默认堆中分配任意大小的内存块并且按我们自己的意志释放它。现在我们已经能释放我们自己刚刚分配的空间了，即使加上一些限制（译注：大概是指上面要求的“必须在同一个函数的作用域中完成分配和释放string对象的动作”），我们仍然已经能在很大程度上控制堆的状态了。

OLEAUT32 memory allocator

OLEAUT32中内存的分配算法

Unfortunately, it turns out that a call to SysAllocString doesn't always result in an allocation from the system heap. The functions for allocating and freeing BSTR strings use a custom memory allocator, implemented in the APP_DATA class in OLEAUT32. This memory allocator maintains a cache of freed memory blocks, and reuses them for future allocations. This is similar to the lookaside lists maintained by the system memory allocator.

现在我们的问题是，不是每次我们调用SysAllocString函数，都会在堆中新分配一个内存空间供string对象使用的。BSTR string所需空间分配和释放的具体工作是有OLEAUT32中的APP_DATA类实现的，在这个类中使用了一个很普通的内存分配算法。堆中使用一个类似于系统的堆内存分配函数（如HeapAlloc函数）使用的Lookaside list的缓存，被释放的内存满足一定条件时（详见下一段）会被释放到这个缓存中（在这个缓存中的内存块实际上并没有被释放掉，也就是不会去执行任何内存块的合并操作），并且会在下一次应用程序申请内存时，优先分配出去。

The cache consists of 4 bins, each holding 6 blocks of a certain size range. When a block is freed with the APP_DATA::FreeCachedMem() function, it is stored in one of the bins. If the bin is full, the smallest block in the bin is freed with HeapFree() and is replaced with the new block. Blocks larger than 32767 bytes are not cached and are always freed directly.

（有关Lookaside list详见《Windows Heap Exploitation》为了保持表述的一致性，下面翻译时使属于术语尽量与Lookaside中的使用的术语一致）这个缓存由4个项组成，每个项中都能存放6个某一大小范围中的被释放的内存块。当我们释放一个内存块时，系统首先将要调用APP_DATA::FreeCachedMem()函数把这个内存块释放到缓存中相应的项中去，如果这个对应项中已经满了（也就是已经有了6个内存块），那么这7个内存块中最小的一个将会被HeapFree()函数释放掉，然后把新释放的这个块加进来（如果新释放的这个内存块不是7个内存块中最小的那一块的话）。当然如果被释放的内存块大于32767个字节的话，它就会被直接释放掉，而不会进入缓存。

When APP_DATA::AllocCachedMem() is called to allocate memory, it looks for a free block in the appropriate size bin. If a large enough block is found, it is removed from the cache and returned to the caller. Otherwise the function allocates new memory with HeapAlloc().

当应用程序调用APP_DATA::AllocCachedMem()函数时，它首先会检查缓存中相应的项中的6个内存块，从中找出最符合要求内存块，然后把这个内存块从缓存中释放出来，把它直接返回给应用程序。如果没有找到合适的内存块，它就会调用HeapAlloc()函数从堆中发配新的内存空间。

The decompiled code of the memory allocator is shown below:

下面是反汇编出来的APP_DATA::FreeCachedMem()和APP_DATA::AllocCachedMem()以及相应结构的代码：

// Each entry in the cache has a size and a pointer to the free block

struct CacheEntry

    unsigned int size;

    void* ptr;

// The cache consists of 4 bins, each holding 6 blocks of a certain size range

class APP_DATA

    CacheEntry bin_1_32     [6];    // blocks from 1 to 32 bytes

    CacheEntry bin_33_64    [6];    // blocks from 33 to 64 bytes

    CacheEntry bin_65_256   [6];    // blocks from 65 to 265 bytes

    CacheEntry bin_257_32768[6];    // blocks from 257 to 32768 bytes

    void* AllocCachedMem(unsigned long size);   // alloc function

    void FreeCachedMem(void* ptr);              // free function

};

//

// Allocate memory, reusing the blocks from the cache

//

void* APP_DATA::AllocCachedMem(unsigned long size)

    CacheEntry* bin;

    int i;

    if (g_fDebNoCache == TRUE)

        goto system_alloc;          // Use HeapAlloc if caching is disabled

    // Find the right cache bin for the block size

    if (size > 256)

        bin = &this->bin_257_32768;

    else if (size > 64)

        bin = &this->bin_65_256;

    else if (size > 32)

        bin = &this->bin_33_64;

    else

        bin = &this->bin_1_32;

    // Iterate through all entries in the bin

    for (i = 0; i < 6; i++) {

        // If the cached block is big enough, use it for this allocation

        if (bin[i].size >= size) {

            bin[i].size = 0;        // Size 0 means the cache entry is unused

            return bin[i].ptr;

system_alloc:

    // Allocate memory using the system memory allocator

    return HeapAlloc(GetProcessHeap(), 0, size);

//

// Free memory and keep freed blocks in the cache

//

void APP_DATA::Free