虚拟内存区域的查询、遍历方法及装置

摘要

本发明实施例公开了一种虚拟内存区域的查询、遍历方法及装置，其中，所述方法包括：确定与查询地址对应的虚拟内存区域vma是否在缓存vma的相邻范围内，所述缓存vma的相邻范围包括所述缓存vma的至少一个前相邻vma的地址范围和至少一个后相邻vma的地址范围；若是，则通过线索红黑树的节点上的线索查询所述vma，所述节点为所述缓存vma对应的节点，所述线索为指向所述线索红黑树上每个节点的前驱节点和后继节点的指针。本发明实施例还公开了一种虚拟内存区域的遍历方法，因为缓存vma的相邻范围的确认总能得到满足，提高了访问缓存的命中率，实现整个vma遍历的时间复杂度为O(n)，从而提高了vma的查询效率。

说明书

技术领域

本发明实施例涉及通信技术，尤其涉及一种虚拟内存区域的查询、遍 历方法及装置。

背景技术

目前，Linux技术通常采用红黑树形式查询虚拟内存区域(virtual  memory area，以下简称：vma)。

具体来说，对于查询第n个vma的过程来说，查询函数find_vma获 得内存描述信息(mm)读信号量，从地址m开始，确认地址m对应的vma 是否在缓存vma的地址范围内，若是，也即本次查询命中缓存，则通过访 问缓存vma来查询地址m对应的vma，并释放读信号量，若否，从根节 点开始通过常规方式遍历红黑树来查询地址m对应的vma，并释放读信号 量。

由于查询函数find_vma在没有命中缓存时，必须从根节点开始通过遍 历的方式查询vma，因此，现有技术的查询效率较低。

发明内容

本发明实施例提供一种虚拟内存区域的查询、遍历方法及装置，以提 高vma的查询效率。

本发明实施例提供了一种虚拟内存区域的查询方法，包括：

确定与查询地址对应的虚拟内存区域vma是否在缓存vma的相邻范 围内，所述缓存vma的相邻范围包括所述缓存vma的至少一个前相邻vma 的地址范围和至少一个后相邻vma的地址范围；

若是，则通过线索红黑树的节点上的线索查询所述vma，所述节点为 所述缓存vma对应的节点，所述线索为指向所述线索红黑树上每个节点的 前驱节点和后继节点的指针。

本发明实施例还提供了一种虚拟内存区域的遍历方法，包括：

获得内存描述信息mm的读信号量，确定查询地址n对应的vma是否 在缓存vma的相邻范围内，所述缓存vma的相邻范围包括所述缓存vma 的至少一个前相邻vma的地址范围和至少一个后相邻vma的地址范围；

若是，则通过线索红黑树的节点上的线索查询所述查询地址n对应的 vma，释放读信号量，所述节点为所述缓存vma对应的节点，所述线索为 指向所述线索红黑树上每个节点的前驱节点和后继节点的指针；

将当前的缓存vma的地址范围更新为所述查询地址n对应的vma的 地址范围(vma_start，vm_ end)，并将查询地址n+1更新为所述查询地址n 对应的vma的vma_end，其中，所述vma_start为所述查询地址n对应的 vma的的首地址，所述vma_end为所述查询地址n对应的vma的尾地址；

获得mm的读信号量，确定所述查询地址n+1对应的vma是当前的缓 存vma的后相邻vma，通过线索红黑树的节点上的线索查询所述当前缓存 vma的后继节点，并根据所述后继节点查询所述查询地址n+1对应的vma；

循环重复上述步骤，直到遍历至少一部分地址空间。

本发明实施例还提供了一种虚拟内存区域的查询装置，包括：

确定模块，用于确定与查询地址对应的虚拟内存区域vma是否在缓存 vma的相邻范围内，所述缓存vma的相邻范围包括所述缓存vma的至少 一个前相邻vma的地址范围和至少一个后相邻vma的地址范围；

线索查询模块，用于所述确定模块确定所述vma在所述缓存vma的 相邻范围内，则通过线索红黑树上的节点上的线索查询所述vma，所述节 点为所述缓存vma对应的节点，所述线索为指向所述线索红黑树上每个节 点的前驱节点和后继节点的指针。

本发明实施例还提供了一种虚拟内存区域的遍历装置，包括：

确定模块，用于确定与查询地址n对应的虚拟内存区域vma是否在缓 存vma的相邻范围内，所述缓存vma的相邻范围包括所述缓存vma的至 少一个前相邻vma的地址范围和至少一个后相邻vma的地址范围；

线索查询模块，用于所述确定模块确定所述vma在所述缓存vma的 相邻范围内，则通过线索红黑树的节点上的线索查询所述vma，所述节点 为所述缓存vma对应的节点，所述线索为指向所述线索红黑树上每个节点 的前驱节点和后继节点的指针；

缓存更新模块，用于根据所述线索查询模块查询的查询地址n对应的 vma，将当前的缓存vma更新为所述查询地址n对应的vma的地址范围 (vma_start，vma_end)，并将查询地址n+1更新为所述查询地址n对应的 vma的vma_end，其中，所述vma_start为所述查询地址n对应的vma的 的首地址，所述vma_end为所述查询地址n对应的vma的尾地址。

本发明实施例通过预先对地址空间中的vma设置vma相邻范围，将 原红黑树扩展为线索红黑树，在现有技术确认查询地址对应的vma是否是 缓存vma的基础上，增加了缓存vma的相邻范围的确认，采用本发明实 施例提供的遍历vma的方法可以保证在遍历地址空间时，相邻vma的确 认总能得到满足，也就是说，确定查询地址对应的vma总是是缓存vma 的相邻vma，通过线索红黑树的节点上的线索总能查询所述查询地址对应 的vma，因此，提高了vma查询的缓存命中率，提升了vma的查询效率。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对 实施例或现有技术描述中所需要使用的附图作一简单地介绍，显而易见 地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员 来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的 附图。

图1为本发明实施例一提供的虚拟内存区域的查询方法的流程图；

图2为本发明实施例二提供的虚拟内存区域的查询方法的流程图；

图3为本发明实施例二提供的vma相邻范围的结构示意图；

图4为本发明实施例二提供的线索红黑树的结构示意图；

图5为本发明实施例一提供的虚拟内存区域的遍历方法流程图；

图6为本发明实施例二提供的虚拟内存区域的遍历方法流程图；

图7为本发明实施例一提供的虚拟内存区域的查询装置结构示意图；

图8为本发明实施例二提供的虚拟内存区域的查询装置结构示意图；

图9为本发明实施例二提供的虚拟内存区域的遍历装置结构示意图；

图10为本发明实施例二提供的虚拟内存区域的遍历装置结构示意图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本 发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描 述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。 基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提 下所获得的所有其他实施例，都属于本发明保护的范围。

现有技术通常以红黑树查询方式查找指定地址对应的vma，下面以查 询地址0对应的vma为例具体说明现有技术所述的一种vma的查询方法， 具体包括：

确认地址0对应的vma是否在缓存的vma地址范围内；

若是，则通过访问缓存的vma查询地址0对应的vma；

若否，则从根节点开始通过常规方式遍历红黑树查询地址0对应的 vma。

若要遍历n个vma，即查询n个vma，则需要根据查询地址0对应的 vma更新当前的缓存vma，具体来说是将当前的缓存vma的地址范围更新 为地址0对应的vma的地址范围(vma_start，vma_end)，并将对地址1对 应的vma(下一个vma)的查询地址更新为地址0对应的vma(上一个vma) 的vma_end；因此，在确认地址1对应的vma是否是缓存的vma(地址0 对应的vma)时，肯定可以确认地址1对应的vma不在缓存的vma(地址0 对应的vma)地址范围内，依次类推，对于后续新的地址对应的vma的查 询，也可以确定后续新的地址对应的vma不在更新后的缓存的vma(上一 个vma)的地址范围内，也就是说缓存命中率几乎为0，因此，每一次都 需要从根节点通过常规方式去遍历红黑树的形式查询新的地址对应的 vma。

从上述现有技术公开的技术方案中可以看出，发明人认为现有技术中 至少存在如下问题：

现有技术使用红黑树查询方式遍历vma时，每一次查询新地址对应的 vma，都将当前缓存vma更新为上一个查询地址对应的vma，因此在查询 下一个新的vma时，可以确认下一个新的vma肯定不在更新后的缓存的 vma地址范围内，也就是说，对vma红黑树中的访问缓存命中率几乎为0， 若需要遍历n个vma，实际上就是n次从根节点通过常规方式查询红黑树 的方式查询vma的过程，由于每次从根节点通过常规方式遍历红黑树的形 式查询vma的时间复杂度是O(logn)，所以整个遍历的时间复杂度变成 O(nlogn)，无疑增加了遍历vma的时间复杂度，因此，现有技术现有技术 使用红黑树查询方式遍历vma的查询效率较低。

鉴于上述现有技术中所存在的问题，本发明实施例提供如下的技术方 案，可以提高访问缓存的命中率，从而提高vma的查询效率。

图1为本发明虚拟内存区域的查询方法实施例一的流程图，如图1所 示，本实施例的方法可以包括：

步骤101、确定与查询地址对应的虚拟内存区域vma是否在缓存vma 的相邻范围内；

其中，缓存vma的相邻范围包括缓存vma的至少一个前相邻vma的 地址范围和至少一个后相邻vma的地址范围。

步骤102、若是，则通过线索红黑树的节点上的线索查询所述vma；

其中，所述节点为所述缓存vma对应的节点，所述线索为指向所述线 索红黑树上每个节点的前驱节点和后继节点的指针。

在上述步骤中，若确定所述查询地址对应的vma刚好是缓存vma，则 直接访问缓存vma查询所述查询地址对应的vma；若不是，则进一步确认 所述查询地址对应的vma是否在缓存vma的相邻范围内，若确认所述查 询地址对应的vma是缓存vma的前相邻vma，则通过线索红黑树的节点 上的线索找到缓存vma的前驱节点，并根据所述前驱节点查询所述查询地 址对应的vma；若确认所述查询地址对应的vma是缓存vma的后相邻vma， 则通过线索红黑树的节点上的线索找到缓存vma的后继节点，并根据所述 后继节点查询所述查询地址对应的vma。

本实施例，通过缓存vma的相邻范围的确认并将原红黑树扩展为线索 红黑树，在现有技术确认查询地址对应的vma是否是缓存vma的基础上， 增加了缓存vma的相邻范围的确认，若确定查询地址对应的vma是缓存 vma的相邻vma，则通过线索红黑树的节点上的线索查找所述查询地址对 应的vma；相较于现有技术只通过缓存vma的确认的方法，在一定程度上 提高访问缓存的命中率，进而提高了vma的查询效率。

下面采用一个具体的实施例对上述图1所示技术方案进行详细说明。

图2为本发明虚拟内存区域的查询方法实施例二的流程图，图3为本 发明实施例二提供的vma相邻范围的结构示意图，图4为本发明实施例二 提供的线索红黑树的结构示意图，如图2～4所示，本实施例的方法可以 包括：

步骤201、获得内存描述信息(mm)的读信号量，确认地址n对应的 vma是否在缓存的vma的地址范围内，若是，则执行步骤202，若否，则 执行步骤203。

步骤202、通过访问缓存的vma直接查询所述地址n对应的vma，并 释放读信号量。

步骤203、确认地址n对应的vma是否在缓存vma的相邻vma范围 内，若是，则执行步骤204，若否，则执行步骤205。

在本步骤中，本发明实施例二提供的所述缓存vma的相邻范围包括所 述缓存vma的至少一个前相邻vma的地址范围和至少一个后相邻vma的 地址范围。所述缓存vma的相邻范围的示意图如图3所示，因为vma地 址范围的半包含性，即vma_end不在该vma的地址范围内，所以在设置 缓存vma的相邻范围时，将缓存vma的前相邻vma的前相邻vma的尾地 址作为该缓存vma相邻范围的起始地址，并将缓存vma的后相邻vma的 尾地址作为该缓存vma相邻范围的结束地址。

当需要确定与查询地址n对应的vma是否在缓存vma的相邻范围内 时，可以通过确认所述查询地址n是否在缓存vma的相邻vma的地址范 围内，若所述查询地址n是在缓存vma的的前相邻vma的前相邻vma的 尾地址和缓存vma的前相邻的尾地址之间，则确定所述查询地址n对应的 vma为缓存vma的前相邻vma；若所述查询地址n在缓存vma的尾地址 和缓存vma的后相邻的vma的尾地址之间，则确定所述查询地址n对应 的vma为缓存vma的后相邻vma。

这里需要指出，通过确认查询地址n是否在缓存vma的相邻vma的 地址范围内来确认缓存vma的相邻vma的方法只是其中的一个实现方案， 但缓存vma的相邻范围的确认并不局限于此方案。

步骤204、通过线索红黑树的节点上的线索查询所述地址n对应的 vma。

在本步骤中，本发明实施例二提供的所述线索红黑树的结构示意图如 图4所示，通过在原系统中的vma红黑树上的每一个vma节点处增加指 向其前驱节点和后继节点的的线索，将原红黑树扩展为线索红黑树，所述 线索为指向所述线索红黑树上每个节点的前驱节点和后继节点的指针。

若确定与查询地址n对应的vma是缓存vma的前相邻vma，则通过 线索红黑树的节点上的线索找到缓存的vma的前驱节点，并根据所述前驱 节点查询地址n对应的vma，并释放读信号量；若确定地址n对应的vma 是缓存的vma的后相邻，则通过线索红黑树的节点上的的线索找到缓存的 vma的后继节点，并根据所述后继节点查询地址n对应的vma，并释放读 信号量。

步骤205、从根节点通过常规方式遍历线索红黑树查询地址n对应的 vma，并释放读信号量。

本实施例，通过预先设置缓存vma的相邻范围并将原红黑树扩展为线 索红黑树，在现有技术确认查询地址对应的vma是否是缓存vma的基础 上，增加了缓存vma的相邻范围的确认，若确定查询地址对应的vma是 缓存vma的相邻vma，则通过线索红黑树的节点上的线索查找所述查询地 址对应的vma；相较于现有技术只通过缓存vma的确认的方法，在一定程 度上提高访问缓存的命中率，进而提高了vma的查询效率，同时，在本实 施例中，由于查询所述地址n对应的vma时要释放读信号量，因此，保证 了在查询vma时可以对所述vma进行读操作以外的其他操作，如对所述 vma可以修改。

图5为本发明虚拟内存区域的遍历方法实施例一的流程图，如图5所 示，本实施例的方法可以包括：

步骤501、获得内存描述信息mm的读信号量，确定查询地址n对应 的vma是否在缓存vma的相邻范围内。

其中，缓存vma的相邻范围包括缓存vma的至少一个前相邻vma的 地址范围和至少一个后相邻vma的地址范围。

步骤502、若是，则通过线索红黑树的节点上的线索查询所述查询地 址n对应的vma，释放读信号量，所述节点为所述缓存vma对应的节点， 所述线索为指向所述线索红黑树上每个节点的前驱节点和后继节点的指 针。

在本步骤中，若确定所述查询地址对应的vma刚好是缓存vma，则直 接访问缓存vma查询所述查询地址对应的vma；若不是，则进一步确认所 述查询地址n对应的vma是否在缓存vma的相邻范围内，若确认所述查 询地址n对应的vma是缓存vma的前相邻vma，则通过线索红黑树的节 点上的线索找到缓存vma的前驱节点，并根据所述前驱节点查询所述查询 地址n对应的vma；若确认所述查询地址n对应的vma是缓存vma的后 相邻vma，则通过线索红黑树的节点上的线索找到缓存vma的后继节点， 并根据所述后继节点查询所述查询地址n对应的vma。

步骤503、将当前的缓存vma的地址范围更新为所述查询地址n对应 的vma的地址范围(vma_start，vma_end)，并将地址n+1对应的vma的查 询地址更新为所述查询地址n对应的vma的vma_end，其中，所述vma_start 为所述查询地址n对应的vma的的首地址，所述vma_end为所述查询地 址n对应的vma的尾地址。

步骤504、获得mm的读信号量，确定所述查询地址n+1对应的vma 是当前的缓存vma的后相邻vma，通过线索红黑树的节点上的线索查询所 述当前缓存vma的后继节点，并根据所述后继节点查询所述查询地址n+1 对应的vma；

循环重复上述步骤，直到遍历至少一部分地址空间。

本实施例，通过预先设置缓存vma的相邻范围并将原红黑树扩展为线 索红黑树，在确定查询地址n对应的vma是缓存vma的相邻vma，通过 线索红黑树的节点上的线索查询所述查询地址n对应的vma，并将当前缓 存vma更新为所述地址n对应的vma，将对地址n+1对应的vma的查询 地址更新为更新后的缓存vma(地址n对应的vma)的地址范围，由于缓 存vma相邻范围的设置，毫无疑问，可以确定地址n+1对应的vma是缓 存vma(地址n对应vma)的后相邻vma，重复步骤505，依次类推，下 一个地址对应的vma总是缓存vma(上一个地址对应的vma)的后相邻 vma，因此，都可以通过线索红黑树的节点上的线索查询所述vma，相较 于现有技术对访问缓存命中率技术为0，本发明实施例提供的vma遍历 方法对访问缓存的命中率几乎为百分之百，因次，提高了vma遍历的效率。

另外，本发明实施例的应用不限于在遍历全部vma的时候，对于地址 空间中任意连续的地址，遍历其vma都可以通过本发明实施例提供的方 法，如预先对地址空间中连续的地址n+m对应的vma进行相邻vma范围 的设置，vma相邻范围的设置如上所述，这里不再赘述，在进行vma遍历 时，首先通过本发明实施例提供的技术方案查询所述地址n对应的vma， 然后更新访问缓存的vma和下一个地址对应vma的查找地址，由于下一 个地址对应的vma总是缓存vma(上一个vma)的后相邻vma，总是可以 通过线索红黑树的节点上的线索查询所述连续地址n+m对应的每一个 vma，直至对连续地址n+m对应的vma的遍历结束。

图6为本发明虚拟内存区域的遍历方法实施例二的流程图，如图6所 示，本实施例的方法可以包括：

步骤601、查询函数获得内存描述信息(mm)读信号量，从地址0 开始，确认地址0对应的vma是否在缓存的vma地址范围内，若是，执 行步骤602，若否，则执行步骤603。

步骤602、通过访问缓存vma直接查询地址0对应的vma，并释放读 信号量。

步骤603、确认地址0对应的vma是否在缓存的vma的相邻范围内， 若是，则执行步骤604，若否，则执行步骤605。

在本步骤中，本发明实施例二提供的所述缓存vma的相邻范围包括所 述缓存vma的至少一个前相邻vma的地址范围和至少一个后相邻vma的 地址范围，所述缓存vma的相邻范围的示意图如图3所示，这里不再赘述。

步骤604、通过线索红黑树的节点上的线索查询所述查询地址0对应 的vma。

在本步骤中，所使用的线索红黑树的结构示意图如图4所示，这里不 再赘述。

若确定与查询地址0对应的vma是缓存vma的前相邻vma，则通过 线索红黑树的节点上的线索找到缓存的vma的前驱节点，并根据所述前驱 节点查询地址0对应的vma，并释放读信号量；若确定地址0对应的vma 是缓存的vma的后相邻，则通过线索红黑树的节点上的的线索找到缓存的 vma的后继节点，并根据所述后继节点查询地址0对应的vma，并释放读 信号量。

步骤605、从根节点通过常规方式遍历线索红黑树查询地址0对应的 vma，并释放读信号量。

步骤606、将当前缓存的vma更新为地址0对应的vma，并更新地址 1对应的vma的查找地址，即将缓存vma地址范围更新为地址0对应的 vma的地址范围(vma_start，vma_end)，将地址1对应的vma的查找地址 更新为地址0对应的vma的vma_end。

步骤607、获得mm的读信号量，确定地址1对应的vma是当前的缓 存vma的后相邻vma。

步骤608、通过线索红黑树的节点上的线索查询缓存vma的后继节点， 并根据所述后继节点查询地址1对应的vma，释放读信号量。

循环重复上述步骤，直到遍历完整个地址空间。

从上述步骤可知，由于预先对地址空间中的vma设置了vma相邻范 围，并在线索红黑树上的每一个vma节点处增加线索，所述线索为指向所 述线索红黑树上每个节点的前驱节点和后继节点的指针，因此，在确认地 址1对应的vma是否是更新后的缓存vma的的相邻vma时，因为更新后 的缓存vma已经为地址0对应的vma，毫无疑问的可以确定，地址1对应 的vma是地址0对应的vma的后相邻，此时，通过线索红黑树的节点上 的线索找到缓存vma(地址0对应的vma)的后继节点，并通过该后继节 点查询地址1对应的vma；之后，根据地址1对应vma将访问缓存更新为 地址1对应的vma的地址范围，并对地址2对应的vma的查找地址更新 为地址1对应的vma的vma_end，进行地址2对应的vma的查询，依此类 推，若要遍历n个vma，由于vma相邻范围的设置和线索红黑树的扩展， 使得对缓存的vma的相邻vma的确认总能得到满足，并通过线索红黑树 的节点上的线索都可以查询下一个vma。

但是，现有技术在通过红黑树查询方式遍历vma时，只确认查询地址 对应的vma是否是缓存vma的地址范围，由于更新后的缓存vma总是查 询地址对应的vma的上一个vma，毫无疑问可以确认查询地址对应的vma 肯定不在更新后的缓存的vma地址范围内，也就是说，对vma红黑树中 的访问缓存命中率几乎为0，没有充分利用访问缓存的命中效率。若通过 红黑树形式遍历n个vma，由于访问缓存的命中率为0，因此，n个vma 的查询过程实际上是n次从根节点通过常规方式查询红黑树的形式查询 vma的过程，由于每次从根节点通过常规方式遍历红黑树的形式查询vma 的时间复杂度是O(logn)，所以整个遍历的时间复杂度变成O(nlogn)，无 疑增加了遍历vma的时间复杂度。

因此，应用本发明实施例提供虚拟内存的遍历方法在遍历地址空间 时，由于缓存的vma的相邻vma的确认总能得到满足，在缓存vma的整 个相邻范围内都可命中，通过线索红黑树的节点上的线索总是可以查找到 所述查询地址对应的vma，从而将整个遍历过程的时间复杂度降低到 O(n)，提升了vma的查询效率，同时，应用本发明实施例提供的方法在查 询每一个vma的过程中都要释放读信号量，由此也保证了在遍历过程中需 要对vma进行读操作以外的其他操作时，都可以用本发明实施例提供的方 法进行vma遍历。

图7为本发明虚拟内存区域的查询装置实施例一的结构示意图，如图 7所示，本实施例的装置可以包括：确定模块11、线索查询模块12，其中，

确定模块11，用于确定与查询地址对应的虚拟内存区域vma是否在 缓存vma的相邻范围内，缓存vma的相邻范围包括缓存vma的至少一个 前相邻vma的地址范围和至少一个后相邻vma的地址范围；

线索查询模块12，用于所述确定模块11确定所述vma在所述缓存vma 的相邻范围内，则通过线索红黑树的节点上的线索查询所述vma，所述节 点为所述缓存vma对应的节点，所述线索为指向所述线索红黑树上每个节 点的前驱节点和后继节点的指针。

本实施例的装置可以用于执行图1所示方法实施例的方法，其实现原 理和技术效果类似，此处不再赘述。

图8为本发明虚拟内存区域的查询装置实施例二的结构示意图，如图 8所示，本实施例的装置在图7所示装置的基础上，进一步地，还可以包 括：存储模块13，该存储模块13，用于存储所述缓存vma的相邻范围， 所述缓存vma的相邻范围的起始地址为所述缓存vma的前相邻vma的前 相邻vma的尾地址，所述相邻vma范围的结束地址为所述缓存vma的后 相邻vma的尾地址。确定模块11，可以具体包括：第一确定单元111和 第二确定单元112，其中，第一确定单元111，用于若所述查询地址在缓 存vma的前相邻vma的前相邻vma的尾地址和缓存vma的前相邻的尾地 址之间，则确定所述查询地址对应的vma为缓存vma的前相邻vma；第 二确定单元112，用于若所述查询地址在缓存vma的尾地址和缓存vma的 后相邻的vma的尾地址之间，则确定所述查询地址对应的vma为缓存vma 的后相邻vma。

线索查询模块12，可以具体包括：第一查询单元121和第二查询单元 122，其中，第一查询单元121，用于若所述第一确定单元确定与查询地址 对应的vma是前相邻vma，则根据所述线索红黑树的节点上的线索查找到 所述缓存vma的前驱节点，并根据所述前驱节点查找所述vma；第二查询 单元122，用于若所述第二确定单元确定与查询地址对应的vma是后相邻 vma，则根据所述线索红黑树的节点上的线索查找到所述缓存vma的后继 节点，并根据所述后继节点查找所述vma。

本实施例的装置可以用于执行图2所示方法实施例的方法，其实现原 理和技术效果类似，此处不再赘述。

图9为本发明虚拟内存区域的遍历装置实施例一的结构示意图，如图 9所示，本实施例的装置可以包括：确定模块21、线索查询模块22、缓存 更新模块23，其中

确定模块21，用于确定与查询地址n对应的虚拟内存区域vma是否 在缓存vma的相邻范围内，所述缓存vma的相邻范围包括所述缓存vma 的至少一个前相邻vma的地址范围和至少一个后相邻vma的地址范围；

线索查询模块22，用于所述确定模块21确定所述vma在所述缓存vma 的相邻范围内，则通过线索红黑树的节点上的线索查询所述vma，所述节 点为所述缓存vma对应的节点，所述线索为指向所述线索红黑树上每个节 点的前驱节点和后继节点的指针；

缓存更新模块23，用于根据所述线索查询模块22查询的查询地址n 对应的vma，将当前的缓存vma更新为所述查询地址n对应的vma的地 址范围(vma_start，vma_end)，并将查询地址n+1更新为所述查询地址n 对应的vma的vma_end，其中，所述vma_start为所述查询地址n对应的 vma的的首地址，所述vma_end为所述查询地址n对应的vma的尾地址。

本实施例的装置可以用于执行图5所示方法实施例的方法，其实现原 理和技术效果类似，此处不再赘述。

图10为本发明虚拟内存区域的遍历装置实施例二的结构示意图，如 图10所示，本实施例的装置在图9所示装置的基础上，进一步地，还可 以包括：存储模块24，该存储模块24，用于存储所述缓存vma的相邻范 围，所述缓存vma的相邻范围的起始地址为所述缓存vma的前相邻vma 的前相邻vma的尾地址，所述相邻vma范围的结束地址为所述缓存vma 的后相邻vma的尾地址。

确定模块21，具体进一步包括：第一确定单元211和第二确定单元 212，其中，所述第一确定单元211，用于若所述查询地址n在缓存vma 的前相邻vma的前相邻vma的尾地址和缓存vma的前相邻的尾地址之间， 则确定所述查询地址n对应的vma为缓存vma的前相邻vma；所述第二 确定单元212，用于若所述查询地址n在缓存vma的尾地址和缓存vma的 后相邻的vma的尾地址之间，则确定所述查询地址n对应的vma为缓存 vma的后相邻vma。

线索查询模块22，具体进一步包括：第一查询单元221和第二查询单 元222；其中，所述第一查询单元221，用于若所述第一确定单元211确 定与查询地址n对应的vma是前相邻vma，则根据所述线索红黑树的节点 上的线索查找到所述缓存vma的前驱节点，并根据所述前驱节点查找所述 vma。所述第二查询单元222，用于若所述第二确定单元212确定与查询 地址n对应的vma是后相邻vma，则根据所述线索红黑树的节点上的线索 查找到所述缓存vma的后继节点，并根据所述后继节点查找所述vma。

本实施例的装置可以具体用于执行图6所示方法实施例的方法，其实 现原理和技术效果类似，此处不再赘述。

最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对 其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通 技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修 改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不 使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。