65.9K
CodeProject 正在变化。 阅读更多。
Home

一个受监控、内存映射的 std::allocator，用于 STL 容器中的海量数据存储

stefan stammberger
starIconstarIconstarIconstarIconstarIcon

5.00/5 (10投票s)

2020 年 5 月 18 日

CPOL

7分钟阅读

viewsIcon

26921

downloadIcon

296

一种新颖的分配器实现，用于管理 Windows 操作系统上 STL 的 std:: 容器中的海量数据

引言

当涉及到处理应用程序地址空间中的大量数据时，已安装的交换文件大小会构成自然限制。达到此限制时，操作系统将开始无条件终止正在运行的进程，最终终止您的工作进程。此外，这表明如果内存分配过于仓促，系统就会陷入麻烦，将数据从工作集推送到页面文件。这会导致系统本身开始“颠簸”（thrashing），变得迟缓，最终完全停止响应输入。

这些效应已在独立的 Windows 8 和 Windows 10 安装上得到验证。

通过以下小程序，应该可以轻松重现所述行为。请在执行此操作之前小心，因为它将导致您的系统停止工作，您可能需要重新启动。

//
// Sample illustrating the observed effect
//

int main()
{
    for (size_t iter = 0; iter < 1000000000; ++iter)
    {
        void* ptr = malloc(1024);
    }
}

使用 ProcessExplorer 并运行此代码，可以观察到进程内存的快速增长，直到达到最大工作集级别。此时，系统停止运行。过多的分配似乎使 Windows 虚拟内存管理过载，系统拒绝进一步的用户输入。

查阅相关文献，建议使用 SetProcessWorkingSetSize API 调用或 Windows 作业对象。
前者似乎对实际限制进程工作集没有影响，而后者则受到用户需要额外权限的限制——这使得它难以用于通用安装。

为了克服这个问题，还验证了直接内存映射。在这种情况下，ProcessExplorer 显示正在执行的进程的工作集级别保持较低。尽管如此，系统范围消耗的工作空间级别仍在不断增长，最终我们陷入了相同的场景。

接下来，我们将讨论如何克服内存限制并控制分配频率。

控制分配频率

为了控制进程发生的分配速率，有必要建立一些监控。由于调用 malloc 是直接的 API 调用，因此有必要用可被检测的版本替换它们。另一方面，替换函数应对正在执行的进程性能的影响尽可能小。

在我们的方法中，我们通过引入第二个线程——称为“观察线程”来实现这一点。其目标是测量和控制在给定时间段内发生的分配速率。然后，该线程在需要时减慢主线程的速度。

为了能够访问 malloc 函数，我们只需用一个全局函数指针变量替换它，形式如下：

// Replacing default malloc by a controlled version

#define malloc(a) (*mallocfct)(a);

请注意，mallocfct 是一个全局的非 const 变量，可以在运行时修改。

在我们的方法中，我们使用了 mallocfct 的三种不同实现。使用哪种实现取决于进程当前消耗内存的状态。

//
// Different specifications of the mallocfct
//

DWORD sleepCount=100;
void* sloppymalloc(size_t size_p)
{
    Sleep(sleepCount);
    return malloc(size_p);
}

bool stopMallocs = false;
void* stopmalloc(size_t size_p)
{
    while (stopMallocs)
        Sleep(0);
    return malloc(size_p);
}

void* speedymalloc(size_t size_p)
{
    return malloc(size_p);
}

为了测量进程消耗的内存，观察线程会定期调用 GlobalMemoryStatusEx 以及由此提供的 status.ullAvailPhys 属性。

通常，分配函数设置为 speedymalloc，它类似于常规的 malloc，没有时间延迟。一旦达到工作区限制，就会注入 sloppymalloc 方法。在刷新期间，stopmalloc 函数处于活动状态，这将阻止主线程进行进一步的分配。

通过此扩展，我们能够解除进程对工作区限制的限制，并充分利用 pagefile 空间。重要的是要理解，这种处理不会影响主进程的实现，并且还允许同时控制多个线程。缺点是，需要额外的一个核心来运行观察者代码。

依赖足够的页面文件大小仍然存在可用空间的限制。此外，pagefile 空间并非仅供工作进程使用，并且与同一时间执行的其他系统上的进程竞争。运行交换空间不足，系统开始随机终止进程，最终终止用户进程。无法在正常运行期间增加页面文件大小，需要重新启动系统。

因此，下一节将讨论如何消除系统交换文件限制。

动态扩展进程地址空间

为了扩展进程可用的虚拟地址空间，文件内存映射被证明是首选技术。它允许在运行时动态地创建和添加进程的交换空间，而无需进行系统重新配置。每个内存映射文件都会提供一个新的虚拟地址空间段，可以直接访问。请注意，内存映射文件对于 x64 应用程序效率最高，它们提供了几乎无限的虚拟内存地址空间。

因此，我们实现了一个简单的内存管理器，它挂接到前面提到的 mallocfct 例程，并允许跨越多个内存映射区域。新创建的交换文件会在需要时添加到进程虚拟内存空间。实现保持非常简单，并使用首次适应（first fit）来重新分配内存空间。

//
// mallocfct extended to call the file mapped memory manager
//

void* sloppymalloc(size_t size_p)
{
    Sleep(sleepCount);
    return Heap_g.allocateNextMemBlock(size_p);
}

bool stopMallocs = false;
void* stopmalloc(size_t size_p)
{
    while (stopMallocs)
        Sleep(0);
    return Heap_g.allocateNextMemBlock(size_p);
}

void* speedymalloc(size_t size_p)
{
    return Heap_g.allocateNextMemBlock(size_p);
}

void movetofree(void* p)
{
    char* p_ = (char*)p;
    Heap_g.freeMemBlock( (__s_block*)(p_ - BLOCK_SIZE) );
}

这种方法理论上消除了任何内存限制，但在实践中表明，消耗工作空间仍然会导致系统不稳定。通过监控进程，观察到正在执行的进程的工作空间级别保持较低，而整个系统内存被消耗。同样，一旦达到最大工作空间级别，系统就会开始减速并最终停止响应。

解决此问题的方法是，观察线程在达到允许的工作空间限制时，通过调用 Windows API 函数 SetProcessWorkingSetSize(HANDLE, -1, -1) 来显式查询系统刷新。在我们的测试中，这被设置为低于可用物理内存 1 Gbyte。

还观察到，不同版本的 Windows 行为不同。在 Windows XP/7 和 Wine 中，调用 VirtualUnlock 可以释放工作集中的映射，而 Windows 8 和 10 则需要完全 EmptyWorkingSet 来释放映射的页面。

 

图 1：随时间推移消耗的系统工作空间

在最后一步，将上述技术集成到 std::allocator 模型模板中，以便方便使用。

集成到 std 模板库模型中

将观察到的 malloc 和内存映射文件管理功能集成到 std::allocator 中，可以将上述概念限制在标准容器的特定、内存消耗实例的范围内。其他数据结构和容器将不受影响。

为了使分配器模型使用内存映射堆，allocate 和 deallocate 的例程已按以下方式实现：

  // Allocate memory
  pointer allocate(size_type count, const_pointer /* hint */ = 0)
  {
      if(count > max_size()){throw std::bad_alloc();}
          return static_cast<pointer>(oheap::get()->malloc(count * sizeof(type)));
  }

  // Delete memory
  void deallocate(pointer ptr, size_type /* count */)
  {
      oheap::get()->free(ptr);
  }

该项目提供了实现所需的组件，包括：

  • 观察线程 (oheap.cpp)
  • 内存管理器 (vheap.cpp)
  • 文件内存映射 (mmap.cpp)
  • STL 分配器接口 (allocator.h)

如果您想在应用程序中普遍使用观察到的 malloc 例程，则需要实现全局 new 和 delete 运算符。

void * operator new(std::size_t n)
{
    return mallocfct(n);
}
void operator delete(void * p) throw()
{
    movetofree(p);
}

void *operator new[](std::size_t s)
{
    return mallocfct(s);
}
void operator delete[](void *p) throw()
{
    movetofree(p);
}

背景

本文的读者应具备 C++11 的基础知识，了解 STL 容器模板库的使用，并理解线程原理。

Using the Code

std::allocator 可以作为标准容器参数列表中的额外参数简单使用。堆模板参数指的是观察到的内存管理器。

//
// std::multiset sample
//

#include <allocator.h>
#include <set>

int main()
{
    std::multiset<Example, std::less<Example>, allocator<Example, heap<Example> > > foo;

    for (int iter = 0; iter < 1000000000; ++iter)
    {
        foo.insert(Example(iter + 3));
        foo.insert(Example(iter + 1));
        foo.insert(Example(iter + 4));
        foo.insert(Example(iter + 2));
    }

    for (std::multiset<Example, std::less<Example>, 
         allocator<Example, heap<Example> > >::const_iterator iter(foo.begin()); 
         iter != foo.end(); ++iter)
    {
        ;
    }

    return 0;
}

为了在本地安装，请确保将 VFILE_NAME #define 设置为指向您系统上一个可写且足够大的文件夹。最大可分配内存块由 VFILE_SIZE #define 定义。请注意，在当前实现中，没有进行内存对齐。

附带的项目提供了所需的 mmapallocator.dll 库。

特别鸣谢

  1. Dr. Thomas Chust - 文件内存映射层和基本内存管理行为的分析
  2. Pritam Zope - 提供了 sbrk 内存管理器实现的基本框架
  3. Joe Ruether - std::allocator 的复杂模板实现

关注点

近期版本的 Windows 在处理高内存消耗进程的虚拟内存管理方面存在重大限制。

历史

  • 2020 年 5 月 18 日：初始版本
  • 2020 年 5 月 21 日：观察线程修复
  • 2020 年 5 月 24 日：动态放大 vmmap 文件大小
© . All rights reserved.