CN102521143B - 一种堆数据处理方法及装置 - Google Patents

Abstract

本发明公开了一种堆数据处理方法及装置，该方法包括：确定用户需要分配内存写入数据时，从堆区中选择空闲堆进行分配，并动态更新设定区域中与所分配的堆对应的堆元数据；或者，确定用户请求释放已分配堆时，释放用户请求的已分配堆，并动态更新设定区域中与所释放的堆对应的堆元数据；其中所有堆的堆元数据集中存储在所有堆所占区域外的内存中的设定区域中。本发明方法采用集中的方式把所有堆的堆元数据存储在一块安全的内存区域中，从存储形式上将堆元数据与堆中数据分离开来，用户的修改对象只能是堆中数据，不能修改堆元数据，可有效预防攻击者通过堆溢出来修改堆元数据的问题。

Description

一种堆数据处理方法及装置

技术领域

本发明涉及计算机技术领域，尤其涉及一种堆数据处理方法及装置。

背景技术

堆是一块地址连续的计算机内存区域，堆区内包括多个连续的堆，堆溢出是指当计算机程序向某个堆内填充的数据量超过了堆本身的容量时发生的数据长度超出该堆的存储边界的现象。当一个超长的数据输入到某个堆内时，超出部分就会被写入堆区内相邻的其他堆中，其他堆可能已经存放数据，如存放程序执行的下一条指令的指针，或者是其他程序的输出内容，因此这些内容可能全部或部分被覆盖或者破坏掉，如果覆盖或破坏掉的内容比较重要，则会影响后续的正常操作，可见一小部分数据或者一套指令的溢出就可能导致一个程序或者操作系统崩溃。

以Linux系统为例，整个堆区内的堆由于不断动态分配和回收，通常已分配堆和空闲堆交错分布，每个堆的存储结构为：包括连续存储的堆元数据和堆中数据，其中，已分配堆中的堆中数据为供用户程序所使用的各类应用数据，空闲堆中的堆中数据为初始化数据，如为全FF等；而堆元数据则记载了空闲堆或已分配堆的属性信息(例如当前堆的堆长度、前一空闲堆的堆长度、链接前一堆的指针、链接后一堆的指针等信息)，并且堆元数据是分配和回收堆的重要参数。

例如，目前Linux系统分配空闲堆的机制为：将空闲堆的堆元数据链接至被称为Bin的双向链表中，内存中有128个Bin双向链表，不同的Bin双向链表链接不同长度的空闲堆的堆元数据，一个Bin双向链表有可能链接同一长度的多个空闲堆的堆元数据；系统在分配空闲堆时，根据需要占用的内存长度及Bin双向链表所链接的堆元数据所在空闲堆的长度，寻找是否有一个堆长度与需要占用的内存长度相匹配的空闲堆供用户使用，如果有则将其分配给用户，如果没有则以堆区的高地址(堆区内存空间的使用为从低地址到高地址增长)作为起始位置，重新划分一个合适的空闲堆供用户使用，该过程中，系统采用最佳匹配算法寻找堆长度与需要占用的内存长度相匹配的空闲堆，即将查询到的第一个堆长度与需要占用的内存长度相匹配的空闲堆分配给用户。

然而，由于目前堆的存储结构为包括堆元数据和堆中数据，由于堆的动态分配和回收使得已分配堆与空闲堆交错分布，由于在存储数据的过程中也没有边界检查，这样攻击者就很容易通过输入大量的数据而造成堆溢出现象。而堆元数据一般位于堆的起始位置，因此堆元数据被覆盖的几率最大，而堆元数据相对来说又是比较重要的信息，因此如果攻击者恶意造成堆溢出，那就会给操作系统或计算机网络系统带来非常大的破坏。再者，分配堆过程中的最佳匹配算法具有明显的规律性，攻击者完全可以利用该算法去执行堆的分配。因此，堆元数据是攻击者的重要目标，保护堆元数据不受攻击者的破坏对于堆区的安全是非常重要的。

为此，提出一种安全而有效地保护堆元数据的堆溢出防范机制，是防止恶意攻击堆缓冲区溢出的重要手段之一。

发明内容

本发明提供一种堆数据处理方法及装置，用以克服现有技术中攻击者利用堆溢出现象来修改堆元数据，从而造成程序或者操作系统被破坏的问题。

本发明方法包括：

一种堆数据处理方法，包括：

确定用户需要分配内存写入数据时，从堆区中选择空闲堆进行分配，并动态更新设定区域中与所分配的堆对应的堆元数据；或者，

确定用户请求释放已分配堆时，释放用户请求的已分配堆，并动态更新设定区域中与所释放的堆对应的堆元数据；

其中所有堆的堆元数据集中存储在所有堆所占区域外的内存中的设定区域中。

一种堆数据处理装置，包括：

堆分配模块，用于确定用户需要分配内存写入数据时，从堆区中选择空闲堆进行分配；

第一堆元更新模块，用于动态更新设定区域中与所分配的堆对应的堆元数据；

堆释放模块，用于确定用户请求释放已分配堆时，释放用户请求的已分配堆；

第二堆元更新模块，用于动态更新设定区域中与所释放的堆对应的堆元数据；

其中所有堆的堆元数据集中存储在所有堆所占区域外的内存中的设定区域中。

本发明提供的一种堆数据处理方法及装置，采用集中的方式把所有堆的堆元数据存储在一块安全的内存区域中，从存储形式上将堆元数据与堆中数据分离开来，即将堆元数据从堆内部分离出来，集中存储于堆所占区域以外的设定区域，在这种结构下，堆元数据的写操作机制是完全不同于堆中数据的，因此堆元数据能被被很好的保护起来，能够有效预防攻击者通过堆溢出来修改堆元数据的问题，避免了因堆元数据受到攻击而导致系统不能正常的分配堆和回收堆。

附图说明

图1为本发明提供的一种堆数据处理方法的流程图；

图2为本发明提供的一种堆数据处理装置的结构示意图。

具体实施方式

下面结合附图和具体实施例，对本发明堆数据处理方法及装置的具体实施方式作进一步详细描述。

本发明提供一种堆数据处理方法，如图1所示，包括：

确定用户需要分配内存写入数据时，从堆区中选择空闲堆进行分配，并动态更新设定区域中与所分配的堆对应的堆元数据；或者，

确定用户请求释放已分配堆时，释放用户请求的已分配堆，并动态更新设定区域中与所释放的堆对应的堆元数据；

其中所有堆的堆元数据集中存储在所有堆所占区域外的内存中的设定区域中。

堆为用户程序在运行期间动态存储数据所使用的内存区域，由空闲堆和已分配堆组成整个堆区。每个空闲堆或已分配堆的内部都存储有堆元数据和堆中数据，其中，堆元数据则记载了空闲堆或已分配堆的使用和地址等信息，例如堆使用信息表示了对应堆为空闲状态还是已分配状态，堆地址信息则表示了对应堆的堆地址、堆长度、前一堆的堆地址、后一堆的堆地址等。

由于现有技术中，堆元数据被存储于对应的堆内部，使攻击者很容易利用堆溢出现象来修改堆元数据，造成不能正常的分配空闲堆或回收已分配堆，从而使程序或者操作系统崩溃。

本发明提供的堆数据处理方法，采用集中的方式把所有堆(空闲堆或已分配堆)的堆元数据存储在一块安全的内存区域中，从存储形式上将堆元数据与堆中数据分离开来，即将堆元数据从堆内部分离出来，集中存储于堆所占区域以外的设定区域，在这种结构下，堆元数据的写操作机制是完全不同于堆中数据的，因此堆元数据能被被很好的保护起来，能够有效预防攻击者通过堆溢出来修改堆元数据的问题，避免了因堆元数据受到攻击而导致系统不能正常的分配堆和回收堆。

现有技术中，攻击者常通过堆溢出的方式来破坏堆元数据，使系统不能正常的分配堆和回收堆，为了更好的保护堆元数据免受攻击，本发明可以进一步设定只有一定权限才可以对堆元数据进行修改，否则就不能修改，从而在根本上将管理堆与使用堆分离。本发明堆数据处理方法的执行主体为操作系统或其他后台程序，因此，可以设定只有操作系统或者其他后台程序才具有管理堆区的权限，才能够修改堆元数据，而用户程序则因不具有权限就不能对堆元数据进行操作。

为保护堆元数据不被攻击者修改，本发明需要把所有堆对应的堆元数据存储在一块连续的、受保护的、安全的内存区域中，鉴于堆区内的数据存储方式是由低地址到高地址增长的，以及堆区内空闲堆和已分配堆的交替连接方式，本发明方法可以从堆区的起始地址开始，开辟一定长度的空间作为设定区域。

本发明提供的堆数据处理方法中，用户首先在所分配的堆中写入数据，待所分配的堆写满数据且数据未写完时，将未写完的数据写入到所分配的堆之外的堆中。这样，用户(包括攻击者)只能在堆内部执行写操作，修改对象也只能是堆中数据，不能对堆元数据作修改，也就不会给分配堆和回收堆带来困难，可有效预防攻击者通过堆溢出来修改堆元数据的问题。

优选的，本发明提供的堆数据处理方法中，堆元数据包括其所对应堆的堆地址信息和堆使用信息，其中，堆地址信息为对应堆所占区域的地址信息，通过该信息，本方法在将堆元数据从堆内部分离出来之后，由堆元数据可以准确定位对应堆所占的区域，以及确定对应堆的堆长度；而堆使用信息为对应堆的空闲或者已分配等状态信息。

基于本发明中将堆元数据从堆本身中分离出来的思想，本发明堆数据处理方法中确定用户需要分配内存写入数据时，从堆区中选择空闲堆进行分配，并动态更新设定区域中与所分配的堆对应的堆元数据，具体包括：

确定请求分配的内存的长度L；在所述设定区域中查找第一匹配堆元数据，所述第一匹配堆元数据为堆使用信息为空闲、堆地址信息确定的堆长度与长度L相匹配的堆元数据；将所述第一匹配堆元数据对应的堆分配给用户，同时更新所述第一匹配堆元数据中的堆使用信息为已分配。

优选的，在确定不存在第一匹配堆元数据时，本发明的堆数据处理方法还包括：在当前所有堆所占区域和设定区域以外的内存空间中，划分一个新空闲堆进行分配，所述新空闲堆的堆长度与长度L相匹配；同时，在所述设定区域中创建对应所述新空闲堆的堆元数据。具体的，所述新空闲堆的堆长度可以与用户请求的堆长度L一致，也可以不一致，可根据实际需要设定阈值，在该阈值范围内的堆长度都属于匹配的堆长度。

现有的Linux系统中，堆分配过程采用的是最佳匹配算法，即将查询到的第一个满足堆使用者需求的空闲堆分配给堆使用者，由于这种算法具有明显的规律性，攻击者很容易利用该漏洞来进行攻击，为避免这种情况，本发明的堆分配过程采用的是随机匹配算法：确定第一匹配堆元数据至少有两个时，从所述至少两个第一匹配堆元数据中，随机选取一个第一匹配堆元数据，并将选取的第一匹配堆元数据对应的堆进行分配。由于这种随机匹配的算法具有很大的随机性，攻击者很难找到漏洞进行攻击，因此，具有更高的安全性。

为了在确定用户请求分配的内存长度后，能够迅速准确地找到合适的空闲堆进行分配，优选的，使用不同的链表链接堆长度不同的空闲堆的堆元数据；则查找第一匹配堆元数据，具体包括：查找第一匹配链表，所述第一匹配链表链接的是堆长度与长度L相匹配的空闲堆的堆元数据；确定所述第一匹配链表所链接的堆元数据为第一匹配堆元数据。这样，由于使用了不同的链表去链接对应堆长度不同的空闲堆的堆元数据，根据用户请求分配的内存长度，就可以定位对应的链表，这种方式容易地找到满足用户请求的空闲堆。

基于本发明中将堆元数据从堆本身中分离出来的思想，本发明堆数据处理方法中，确定用户请求释放已分配堆时，释放用户请求的已分配堆，并动态更新设定区域中与所释放的堆对应的堆元数据，具体包括：

根据请求释放的已分配堆的堆地址信息，在所述设定区域中查找第二匹配堆元数据，所述第二匹配堆元数据为堆使用信息为已分配、堆地址信息与请求释放已分配堆的堆地址信息一致的堆元数据；释放所述第二匹配堆元数据对应的已分配堆，同时更新所述第二匹配堆元数据中的堆使用信息为空闲。

本发明的堆数据处理方法需要动态更新设定区域中的堆元数据，因此在回收堆的同时，要对所述设定区域中的第二匹配堆元数据进行相应的修改，从而才能使得第二匹配堆元数据能够正确对应被释放后的堆。优选的，使用不同的链表对应链接堆长度不同的空闲堆的堆元数据，则本发明的堆数据处理方法在更新所述第二匹配堆元数据中的堆使用信息为空闲之后，还包括：根据所述第二匹配堆元数据中堆地址信息确定的堆长度，将所述第二匹配堆元数据链接至相应的链表。

由于堆区内一般为空闲堆与已分配堆交替连接，所以在将所述请求释放的已分配堆释放为空闲堆时，如果该堆的前一个堆或者后一个堆为空闲堆，则在释放的同时应将二者合并为一个较大的空闲堆。优选的，确定堆区中所述请求释放的已分配堆的相邻堆为空闲堆时，将所述请求释放的已分配堆与所述相邻堆合并成一个空闲堆；同时，执行以下步骤：

将所述设定区域中所述相邻堆的堆元数据删除，并将所述第二匹配堆元数据中的堆地址信息修改为合并后的空闲堆的堆地址信息；或者，将所述设定区域中的所述第二匹配堆元数据删除，并将所述相邻堆的堆元数据中的堆地址信息修改为合并后的空闲堆的堆地址信息；或者，将所述设定区域中的所述第二匹配堆元数据、以及所述相邻堆的堆元数据都删除，并在所述设定区域中创建合并后的空闲堆的堆元数据。

基于以上合并空闲堆的思想，本发明的堆数据处理方法还包括：

在将所述第二匹配堆元数据中堆地址信息修改为合并后的空闲堆的堆地址信息后，根据合并后的空闲堆的堆地址信息确定的堆长度，将所述第二匹配堆元数据链接至相应的链表；

在将所述相邻堆的堆元数据中堆地址信息修改为合并后的空闲堆的堆地址信息之后，根据合并后的空闲堆的堆地址信息确定的堆长度，将所述相邻堆的堆元数据链接至相应的链表；

在所述设定区域中创建合并后的空闲堆的堆元数据之后，根据合并后的空闲堆的堆地址信息确定的合并空闲堆的堆长度，将合并后空闲堆的堆元数据链接至相应的链表。

根据以上描述，本发明方法中多处使用到链表技术，这是由于链表是一种物理存储单元上非连续、非顺序的存储结构，相比于线性表顺序结构，链表的插入和删除操作都更方便，因此，利用链表链接空闲堆的堆元数据，可以根据堆空间中空闲堆的变化而方便地对相应的链表进行插入和删除等操作。链表分为单向链表和双向链表两种形式，其中，单向链表的链接方向是单向的，对单向链表的访问要通过顺序读取从头部开始；而双向链表的每个数据结点中都有两个指针，分别指向直接后继和直接前驱，所以从双向链表中的任意一个结点(链表中每一个元素称为结点)开始，都可以很方便地访问它的前驱结点和后继结点。为使本发明方法中查找链表的操作更便捷快速，优选的，本发明使用双向链表去链接空闲堆的堆元数据。

本发明提供一种堆数据处理方法的实施例，用于Linux系统内堆区的溢出防护，如下：

在堆区的低地址区域开辟一定长度的空间作为设定区域，用于存储堆元数据，并设置堆元数据的结构如下：

上述堆元数据结构中各字段的意义为：如果当前堆的前一堆为空闲堆，则prev_size字段存放了前一堆的堆长度；size字段包含了当前堆的堆长度及其他一些堆管理信息，其中，size字段的最低位表示前一堆是否为空闲堆，例如1表示为已分配堆，0表示为空闲堆，因此只需确定size字段的最低位是否为0就可确定前一堆是否为空闲堆；status字段表示当前堆为空闲堆还是已分配堆，例如1表示为已分配堆，0表示为空闲堆；指针md指向当前堆在内存中的地址(即堆地址)；指针bk指向下一堆的堆地址。其中，堆地址信息包括了prev_size字段、size字段、指针md和指针bk，堆使用信息由status字段表示。

本实施例的Linux系统中包含128个Bin双向链表，使用这些Bin双向链表链接堆区内特定长度空闲堆的堆元数据(由Bin双链表存储指向所述堆元数据的地址指针实现)，具体为：系统把所有空闲堆按照堆长度的大小分为大于512字节和小于512字节两个部分，使用前62个Bin双向链表链接小于512字节的空闲堆堆元数据，第一个Bin双向链表链接16字节大小的空闲堆堆元数据，第二个Bin双向链表链接24字节大小的空闲堆堆元数据，依此类推；使用后66个Bin双向链表链接大于512字节的空闲堆堆元数据；由此，将不同的Bin双向链表与不同堆长度的堆元数据一一对应起来，此处，本实施例使用预定位置的Bin双向链表链接包含预定堆长度的堆元数据。

当用户程序在运行期间请求分配对应S字节长度的空闲堆时，操作系统根据所申请的空闲堆长度S，对所有的Bin双向链表进行搜索，从而查找到第一匹配Bin双向链表，并由该匹配的Bin双向链表进一步链接到设定区域中的第一匹配堆元数据，最终由该第一匹配堆元数据中的md指针确定相应的空闲堆，将其分配给用户程序。相应的，操作系统要将设定区域中的第一匹配堆元数据的status字段修改为已分配堆标识1。

为用户分配了合适的堆之后，用户首先在所分配的堆中写入数据，待所分配的堆写满数据且数据未写完时，将未写完的数据写入到所分配的堆之外的堆中。这样，用户只能在堆内部执行写操作，即使是攻击者，其修改对象也只能是堆中数据，不会影响到堆元数据，因此可有效预防攻击者通过堆溢出来修改堆元数据的问题。

由于包含相同堆长度的堆元数据(这类堆元数据对应的空闲堆堆长度都相同)将被链接至同一Bin双向链表，因此，在上述堆分配过程中，如果操作系统通过搜索所有Bin双向链表，查找到的第一匹配Bin双向链表链接了N(N＞1)个匹配的堆元数据，则操作系统通过随机数制造机f(x)在所述N个匹配的堆元数据中，确定一个随机的匹配堆元数据进行使用。

此外，在上述分配过程中，如果操作系统通过搜索所有Bin双向链表，没有查找到第一匹配Bin双向链表，也就没有确定任何匹配的堆元数据，则在堆区内交替链接的空闲堆和已分配堆之后的高地址存储空间中，重新划分一个合适的堆空间分配给用户程序使用。

当用户程序在运行期间请求释放堆地址为add1的已分配堆时，操作系统在设定区域中查找包含所述堆地址add1的第二匹配堆元数据，将所述第二匹配堆元数据中的status字段修改为空闲堆标识0，同时根据所述第二匹配堆元数据中的md指针查找到对应的已分配堆，将其释放为空闲堆。

在上述回收过程中，如果所述请求释放已分配堆的相邻堆为空闲堆时，则操作系统将这两个空闲堆合并成一个较大的空闲堆。相应的，操作系统可以在设定区域中将所述相邻空闲堆的堆元数据删除，并将所述第二匹配堆元数据中包含的堆长度、堆地址分别修改为所述合并空闲堆的堆长度、堆地址；同时，操作系统还需要根据该合并后的空闲堆的堆长度，将所述第二匹配堆元数据链接至对应位置的Bin双向链表。

此外，本实施例在为用户程序分配堆时，还可以根据用户程序请求分配的堆长度，使用Bin双向链表索引指针去定位对应的Bin双向链表。具体的，将所有Bin双向链表的索引指针存放在一个数组中，在确定用户程序请求分配堆时，根据用户程序请求分配的堆长度，在该数组中查找到对应的Bin双向链表，进而可以链接到匹配的堆元数据，确定合适的空闲堆以分配给用户程序使用。

本发明实施例还提供一种堆数据处理装置，如图2所示，包括以下各部分：

堆分配模块201，用于确定用户需要分配内存写入数据时，从堆区中选择空闲堆进行分配；

第一堆元更新模块202，用于动态更新设定区域中与所分配的堆对应的堆元数据；

堆回收模块203，用于确定用户请求释放已分配堆时，释放用户请求的已分配堆；

第二堆元更新模块204，用于动态更新设定区域中与所释放的堆对应的堆元数据；

其中所有堆的堆元数据集中存储在所有堆所占区域外的内存中的设定区域中。

优选的，堆元数据包含了对应堆的堆地址信息和堆使用信息；

则所述堆分配模块201确定用户需要分配内存写入数据时，从堆区中选择空闲堆进行分配，具体包括：

确定请求分配的内存的长度L；在所述设定区域中查找第一匹配堆元数据，所述第一匹配堆元数据为堆使用信息为空闲、堆地址信息确定的堆长度与长度L相匹配的堆元数据；将所述第一匹配堆元数据对应的堆分配给用户；

并且，所述第一堆元更新模块202动态更新设定区域中与所分配的堆对应的堆元数据，具体包括：将所述第一匹配堆元数据中的堆使用信息更新为已分配。

优选的，所述堆分配模块201确定不存在第一匹配堆元数据时，还用于：在当前所有堆所占区域和设定区域以外的内存空间中，划分一个新空闲堆进行分配，所述新空闲堆的堆长度与长度L相匹配；

同时，所述第一堆元更新模块202在所述设定区域中创建对应所述新空闲堆的堆元数据。

优选的，所述堆分配模块201确定第一匹配堆元数据至少有两个时，从所述至少两个第一匹配堆元数据中，随机选取一个第一匹配堆元数据，并将选取的第一匹配堆元数据对应的堆分配给用户。

优选的，使用不同的链表链接堆长度不同的空闲堆的堆元数据；则所述堆分配模块203查找第一匹配堆元数据，具体包括：

查找第一匹配链表，所述第一匹配链表链接的是堆长度与长度L相匹配的空闲堆的堆元数据；确定所述第一匹配链表所链接的堆元数据为第一匹配堆元数据。

优选的，堆元数据包含了对应堆的堆地址信息和堆使用信息；

则所述堆回收模块203确定用户请求释放已分配堆时，释放用户请求的已分配堆，具体包括：

根据请求释放的已分配堆的堆地址信息，在所述设定区域中查找第二匹配堆元数据，所述第二匹配堆元数据为堆使用信息为已分配、堆地址信息与请求释放已分配堆的堆地址信息一致的堆元数据；释放所述第二匹配堆元数据对应的已分配堆；

并且，所述第二堆元更新模块204动态更新设定区域中与所释放的堆对应的堆元数据，具体包括：

将所述第二匹配堆元数据中的堆使用信息更新为空闲。

优选的，使用不同的链表对应链接堆长度不同的空闲堆的堆元数据，则所述第二堆元更新模块204将所述第二匹配堆元数据中的堆的使用信息更新为空闲之后，还用于：根据所述第二匹配堆元数据中堆地址信息确定的堆长度，将所述第二匹配堆元数据链接至相应的链表。

优选的，所述堆数据处理装置还包括：

合并模块205，用于确定堆区中所述请求释放的已分配堆的相邻堆为空闲堆时，将所述请求释放的已分配堆与所述相邻堆合并成一个空闲堆；

同时，所述第二堆元更新模块204执行以下步骤：

将所述设定区域中所述相邻堆的堆元数据删除，并将所述第二匹配堆元数据中的堆地址信息修改为合并后的空闲堆的堆地址信息；或者，

将所述设定区域中的所述第二匹配堆元数据删除，并将所述相邻堆的堆元数据中的堆地址信息修改为合并后的空闲堆的堆地址信息；或者，

将所述设定区域中的所述第二匹配堆元数据、以及所述相邻堆的堆元数据都删除，并在所述设定区域中创建合并后的空闲堆的堆元数据。

优选的，所述第二堆元更新模块204还用于：

在将所述第二匹配堆元数据中堆地址信息修改为合并后的空闲堆的堆地址信息后，根据合并后的空闲堆的堆地址信息确定的堆长度，将所述第二匹配堆元数据链接至相应的链表；

在将所述相邻堆的堆元数据中堆地址信息修改为合并后的空闲堆的堆地址信息之后，根据合并后的空闲堆的堆地址信息确定的堆长度，将所述相邻堆的堆元数据链接至相应的链表；

在所述设定区域中创建合并后的空闲堆的堆元数据之后，根据合并后的空闲堆的堆地址信息确定的合并空闲堆的堆长度，将合并后空闲堆的堆元数据链接至相应的链表。

所述堆数据处理装置各个模块的具体实现功能参见上述堆数据处理方法的具体实现过程，在此不再赘述。

显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。

Claims (19)

1.一种堆数据处理方法，其特征在于，包括：

确定用户需要分配内存写入数据时，从堆区中选择空闲堆进行分配，并动态更新设定区域中与所分配的堆对应的堆元数据；或者，

确定用户请求释放已分配堆时，释放用户请求的已分配堆，并动态更新设定区域中与所释放的堆对应的堆元数据；

其中所有堆的堆元数据集中存储在所有堆所占区域外的内存中的设定区域中，所述设定区域在为堆区的低地址区域开辟的一定长度的空间，所述堆元数据的结构包括prev_size字段、size字段、staus字段、指针md、指针bk，其中，prev_size字段表示存放前一堆的堆长度，size字段包含当前堆的堆长度及堆管理信息，所述堆管理信息包括前一堆是否为空闲堆，status字段表示当前堆为空闲堆或已分配堆，指针md指向当前堆在内存中的地址，指针bk指向下一堆的堆地址。

2.如权利要求1所述的方法，其特征在于，堆元数据包含了对应堆的堆地址信息和堆使用信息；

则确定用户需要分配内存写入数据时，从堆区中选择空闲堆进行分配，并动态更新设定区域中与所分配的堆对应的堆元数据，具体包括：

确定请求分配的内存的长度L；

在所述设定区域中查找第一匹配堆元数据，所述第一匹配堆元数据为堆使用信息为空闲、堆地址信息确定的堆长度与长度L相匹配的堆元数据；

将所述第一匹配堆元数据对应的堆分配给用户，同时更新所述第一匹配堆元数据中的堆使用信息为已分配。

3.如权利要求2所述的方法，其特征在于，确定不存在第一匹配堆元数据时，进一步包括：

在当前所有堆所占区域和设定区域以外的内存空间中，划分一个新空闲堆进行分配，所述新空闲堆的堆长度与长度L相匹配；同时，

在所述设定区域中创建对应所述新空闲堆的堆元数据。

4.如权利要求2所述的方法，其特征在于，确定第一匹配堆元数据至少有两个时，从所述至少两个第一匹配堆元数据中，随机选取一个第一匹配堆元数据，并将选取的第一匹配堆元数据对应的堆进行分配。

5.如权利要求2所述的方法，其特征在于，使用不同的链表链接堆长度不同的空闲堆的堆元数据；

则查找第一匹配堆元数据，具体包括：

查找第一匹配链表，所述第一匹配链表链接的是堆长度与长度L相匹配的空闲堆的堆元数据；

确定所述第一匹配链表所链接的堆元数据为第一匹配堆元数据。

6.如权利要求1所述的方法，其特征在于，堆元数据包含了对应堆的堆地址信息和堆使用信息；

则确定用户请求释放已分配堆时，释放用户请求的已分配堆，并动态更新设定区域中与所释放的堆对应的堆元数据，具体包括：

根据请求释放的已分配堆的堆地址信息，在所述设定区域中查找第二匹配堆元数据，所述第二匹配堆元数据为堆使用信息为已分配、堆地址信息与请求释放已分配堆的堆地址信息一致的堆元数据；

释放所述第二匹配堆元数据对应的已分配堆，同时更新所述第二匹配堆元数据中的堆使用信息为空闲。

7.如权利要求6所述的方法，其特征在于，使用不同的链表对应链接堆长度不同的空闲堆的堆元数据，则更新所述第二匹配堆元数据中的堆使用信息为空闲之后，还包括：

根据所述第二匹配堆元数据中堆地址信息确定的堆长度，将所述第二匹配堆元数据链接至相应的链表。

8.如权利要求6所述的方法，其特征在于，还包括：

确定堆区中所述请求释放的已分配堆的相邻堆为空闲堆时，将所述请求释 放的已分配堆与所述相邻堆合并成一个空闲堆；同时，执行以下步骤：

将所述设定区域中所述相邻堆的堆元数据删除，并将所述第二匹配堆元数据中的堆地址信息修改为合并后的空闲堆的堆地址信息；或者，

将所述设定区域中的所述第二匹配堆元数据删除，并将所述相邻堆的堆元数据中的堆地址信息修改为合并后的空闲堆的堆地址信息；或者，

将所述设定区域中的所述第二匹配堆元数据、以及所述相邻堆的堆元数据都删除，并在所述设定区域中创建合并后的空闲堆的堆元数据。

9.如权利要求8所述的方法，其特征在于，还包括：

在将所述第二匹配堆元数据中堆地址信息修改为合并后的空闲堆的堆地址信息后，根据合并后的空闲堆的堆地址信息确定的堆长度，将所述第二匹配堆元数据链接至相应的链表；

在将所述相邻堆的堆元数据中堆地址信息修改为合并后的空闲堆的堆地址信息之后，根据合并后的空闲堆的堆地址信息确定的堆长度，将所述相邻堆的堆元数据链接至相应的链表；

在所述设定区域中创建合并后的空闲堆的堆元数据之后，根据合并后的空闲堆的堆地址信息确定的合并空闲堆的堆长度，将合并后空闲堆的堆元数据链接至相应的链表。

10.如权利要求5或7或9任一所述的方法，其特征在于，所述链表为双向链表。

11.一种堆数据处理装置，其特征在于，包括：

堆分配模块，用于确定用户需要分配内存写入数据时，从堆区中选择空闲堆进行分配；

第一堆元更新模块，用于动态更新设定区域中与所分配的堆对应的堆元数据；

堆回收模块，用于确定用户请求释放已分配堆时，释放用户请求的已分配堆；

第二堆元更新模块，用于动态更新设定区域中与所释放的堆对应的堆元数据；

其中所有堆的堆元数据集中存储在所有堆所占区域外的内存中的设定区域中，所述设定区域在为堆区的低地址区域开辟的一定长度的空间，所述堆元数据的结构包括prev_size字段、size字段、staus字段、指针md、指针bk，其中，prev_size字段表示存放前一堆的堆长度，size字段包含当前堆的堆长度及其他一些堆管理信息，所述堆管理信息包括前一堆是否为空闲堆，status字段表示当前堆为空闲堆或已分配堆，指针md指向当前堆在内存中的地址，指针bk指向下一堆的堆地址。

12.如权利要求11所述的装置，其特征在于，堆元数据包含了对应堆的堆地址信息和堆使用信息；

则所述堆分配模块确定用户需要分配内存写入数据时，从堆区中选择空闲堆进行分配，具体包括：

确定请求分配的内存的长度L；

在所述设定区域中查找第一匹配堆元数据，所述第一匹配堆元数据为堆使用信息为空闲、堆地址信息确定的堆长度与长度L相匹配的堆元数据；

将所述第一匹配堆元数据对应的堆分配给用户；

并且，所述第一堆元更新模块动态更新设定区域中与所分配的堆对应的堆元数据，具体包括：

将所述第一匹配堆元数据中的堆使用信息更新为已分配。

13.如权利要求12所述的装置，其特征在于，

所述堆分配模块确定不存在第一匹配堆元数据时，还用于：在当前所有堆所占区域和设定区域以外的内存空间中，划分一个新空闲堆进行分配，所述新空闲堆的堆长度与长度L相匹配；

同时，所述第一堆元更新模块在所述设定区域中创建对应所述新空闲堆的堆元数据。

14.如权利要求12所述的装置，其特征在于，

所述堆分配模块确定第一匹配堆元数据至少有两个时，从所述至少两个第一匹配堆元数据中，随机选取一个第一匹配堆元数据，并将选取的第一匹配堆元数据对应的堆分配给用户。

15.如权利要求12所述的装置，其特征在于，使用不同的链表链接堆长度不同的空闲堆的堆元数据；

则所述堆分配模块查找第一匹配堆元数据，具体包括：

查找第一匹配链表，所述第一匹配链表链接的是堆长度与长度L相匹配的空闲堆的堆元数据；

确定所述第一匹配链表所链接的堆元数据为第一匹配堆元数据。

16.如权利要求11所述的装置，其特征在于，堆元数据包含了对应堆的堆地址信息和堆使用信息；

则所述堆回收模块确定用户请求释放已分配堆时，释放用户请求的已分配堆，具体包括：

根据请求释放的已分配堆的堆地址信息，在所述设定区域中查找第二匹配堆元数据，所述第二匹配堆元数据为堆使用信息为已分配、堆地址信息与请求释放已分配堆的堆地址信息一致的堆元数据；

释放所述第二匹配堆元数据对应的已分配堆；

并且，所述第二堆元更新模块动态更新设定区域中与所释放的堆对应的堆元数据，具体包括：

将所述第二匹配堆元数据中的堆使用信息更新为空闲。

17.如权利要求16所述的装置，其特征在于，使用不同的链表对应链接堆长度不同的空闲堆的堆元数据，则所述第二堆元更新模块将所述第二匹配堆元数据中的堆的使用信息更新为空闲之后，还用于：

根据所述第二匹配堆元数据中堆地址信息确定的堆长度，将所述第二匹配堆元数据链接至相应的链表。

18.如权利要求16所述的装置，其特征在于，还包括：

合并模块，用于确定堆区中所述请求释放的已分配堆的相邻堆为空闲堆时，将所述请求释放的已分配堆与所述相邻堆合并成一个空闲堆；

同时，所述第二堆元更新模块执行以下步骤：

将所述设定区域中所述相邻堆的堆元数据删除，并将所述第二匹配堆元数据中的堆地址信息修改为合并后的空闲堆的堆地址信息；或者，

将所述设定区域中的所述第二匹配堆元数据删除，并将所述相邻堆的堆元数据中的堆地址信息修改为合并后的空闲堆的堆地址信息；或者，

将所述设定区域中的所述第二匹配堆元数据、以及所述相邻堆的堆元数据都删除，并在所述设定区域中创建合并后的空闲堆的堆元数据。

19.如权利要求18所述的装置，其特征在于，所述第二堆元更新模块还用于：

在将所述第二匹配堆元数据中堆地址信息修改为合并后的空闲堆的堆地址信息后，根据合并后的空闲堆的堆地址信息确定的堆长度，将所述第二匹配堆元数据链接至相应的链表；

在将所述相邻堆的堆元数据中堆地址信息修改为合并后的空闲堆的堆地址信息之后，根据合并后的空闲堆的堆地址信息确定的堆长度，将所述相邻堆的堆元数据链接至相应的链表；

在所述设定区域中创建合并后的空闲堆的堆元数据之后，根据合并后的空闲堆的堆地址信息确定的合并空闲堆的堆长度，将合并后空闲堆的堆元数据链接至相应的链表。