c++ - 如何安全地实现 “Using Uninitialized Memory For Fun And Profit”？

Question

我想使用https://research.swtch.com/sparse中描述的技巧在C++中构建一个密集整数集。通过允许其自身读取未初始化的内存，此方法可实现良好的性能。

如何在不触发未定义行为且不运行诸如Valgrand或ASAN之类的工具的情况下实现此数据结构？

编辑:似乎响应者专注于“未初始化”一词，并在语言标准的上下文中对其进行解释。在我看来，这可能是一个较差的词选择-这里的“未初始化”仅意味着其值对于算法的正确运行并不重要。显然有可能安全地实现此数据结构(LLVM在SparseMultiSet中做到了)。我的问题是，最好，最高效的方法是什么？

Answer 1

我可以看到四种基本方法。它们不仅适用于C++，而且适用于大多数其他低级语言(例如C)，它们使未初始化的访问成为可能，但不允许，最后一种语言甚至适用于高级“安全”语言。

忽略标准，以通常的方式实现

这是律师疯狂讨厌的一招!不过，请不要害怕-遵循该解决方案的解决方案不会违反规则，因此，如果您属于规则贴纸的一类，则可以跳过此部分。

该标准充分利用了未定义的值，并且它允许的一些漏洞(例如，将一个未定义的值复制到另一个值)并不能真正给您足够的绳索来实际实现您想要的功能-即使在C中，限制也略小(例如，参见涵盖C11的this answer，它解释了访问indeterminiate值可能不会直接触发UB时，任何结果也是不确定的，并且该值实际上似乎在访问之间是偶然的。

因此，您只要知道当前大多数或所有编译器都会将其编译为预期的代码，并且知道您的代码不符合标准，便可以实现它。

至少在my test中，所有gcc，clang和icc都没有利用非法访问来做任何疯狂的事情。当然，该测试并不全面，即使您可以构建一个测试，其行为也可能在新版本的编译器中发生变化。

如果访问未初始化内存的方法的实现是在一个单独的编译单元中编译一次的，那将是最安全的-这可以很容易地检查它是否做对了(只需检查一下汇编)，并且几乎不可能( LTGC之外)，使编译器做任何棘手的事情，因为它无法证明是否正在访问未初始化的值。

不过，从理论上讲，这种方法还是不安全的，您应该非常仔细地检查编译后的输出，并采取其他措施。

如果采用这种方法，像valgrind这样的工具很可能会报告未初始化的读取错误。

现在这些工具可以在汇编级别运行，并且一些未初始化的读取可能很好(例如，参见快速标准库实现的下一项)，因此它们实际上并没有立即报告未初始化的读取，而是具有多种启发式以确定是否实际使用了无效值。例如，他们可以避免报告错误，直到他们确定未初始化的值用于确定条件跳转的方向，或者根据启发式方法无法跟踪/恢复的某些其他 Action 。您可能能够使编译器发出可读取未初始化内存的代码，但根据此启发式方法是安全的。

更有可能，您将无法执行此操作(由于此处的逻辑非常微妙，因为它依赖于两个数组中值的关系)，因此您可以在选择的工具中使用抑制选项来隐藏错误。例如，valgrind可以基于stack trace进行抑制-实际上，默认情况下已经有许多抑制条目用于隐藏各种标准库中的假阳性。

由于它基于堆栈跟踪工作，因此如果读取以内联代码进行，您可能会遇到困难，因为每个调用站点的堆栈顶部都会不同。您可以避免这种情况，以确保未内联函数。

使用组装

标准中定义不明确的内容通常在组装级别定义明确。这就是为什么编译器和标准库通常可以以比使用C或C++更快的方式实现事物的原因:用汇编语言编写的libc例程已经针对特定的体系结构，而不必担心代码中的各种警告。语言规范可以使事情在各种硬件上快速运行。

通常，在汇编中实现任何数量的代码都是一项昂贵的工作，但是在这里这只是少数，因此根据您要定位的平台数量，这可能是可行的。您甚至根本不需要自己编写方法-只需编译C++版本(或使用godbolt并复制程序集即可。is_member函数，例如example1，如下所示:

sparse_array::is_member(unsigned long):
        mov     rax, QWORD PTR [rdi+16]
        mov     rdx, QWORD PTR [rax+rsi*8]
        xor     eax, eax
        cmp     rdx, QWORD PTR [rdi]
        jnb     .L1
        mov     rax, QWORD PTR [rdi+8]
        cmp     QWORD PTR [rax+rdx*8], rsi
        sete    al

依靠 calloc魔术

如果使用 calloc 2，则从基础分配器显式请求零内存。现在，正确版本的 calloc可以简单地调用 malloc，然后将返回的内存清零，但是实际的实现依赖于以下事实:操作系统级别的内存分配例程( sbrk和 mmap，差不多)通常会在任何操作系统上将内存归零具有 protected 内存(即所有大内存)，以避免再次将内存清零。

实际上，对于大型分配，通常可以通过映射所有零的特殊零页来实现类似于匿名 mmap的调用来满足此要求。当(如果有的话)写入内存时，写时复制实际上会分配一个新页面。因此，由于操作系统已经需要将页面清零，因此可以免费分配较大的清零内存区域。

在这种情况下，在 calloc之上实现稀疏集可能与名义上未初始化的版本一样快，同时又安全又符合标准。

Calloc警告

当然，您应该进行测试以确保 calloc的行为符合预期。优化的行为通常仅在您的程序大约“预先”初始化大量长生命周期的归零内存时才会发生。也就是说，用于优化calloc的典型逻辑如下:

calloc(N)
  if (can satisfy a request for N bytes from allocated-then-freed memory)
    memset those bytes to zero and return them
  else
    ask the OS for memory, return it directly because it is zeroed

基本上， malloc基础结构(也是 new和 friend 的基础)有一个(可能为空)内存池，该内存池已从OS那里请求，通常尝试首先分配给该内存。这个池由来自操作系统的最后一个块请求的内存组成，但是没有分发(例如，因为用户请求了32个字节，但是分配的内存要求从OS中以1 MB的块为块，所以还剩下很多)，以及分配给进程但随后通过 free或 delete或其他方式返回的内存。该池中的内存具有任意值，并且如果可以从该池中满足 calloc的要求，那么就不会有魔力，因为必须进行零初始化。

另一方面，如果必须从OS分配内存，那么您会发现魔力。因此，这取决于您的用例:如果您经常创建和销毁 sparse_set对象，则通常只从内部 malloc池中提取内容，并将支付清零费用。如果您有一个生命周期很长的 sparse_set对象，它占用大量内存，则可能是通过询问操作系统来分配它们的，并且您几乎免费获得了调零功能。

好消息是，如果您不想依赖上面的 calloc行为(实际上，在您的OS上或使用分配器，甚至可能没有以这种方式进行优化)，通常可以通过手动映射 /dev/zero来复制行为供您分配。在提供此功能的操作系统上，这可以确保您获得“便宜”的行为。

使用延迟初始化

对于完全与平台无关的解决方案，您可以简单地使用另一个数组来跟踪该数组的初始化状态。

首先，选择一些颗粒，在该颗粒上您将跟踪初始化，并使用位图，其中每个位都跟踪 sparse数组中该颗粒的初始化状态。

例如，假设您选择颗粒为4个元素，并且数组中元素的大小为4个字节(例如 int32_t值):您需要1位来跟踪每4个元素* 4个字节/元素* 8位/byte，这在分配的内存中的开销不到1％3。

现在，您只需在访问 sparse之前检查此数组中的相应位即可。这会增加访问 sparse数组的少量开销，但不会改变整体复杂性，并且检查仍然相当快。

例如，您的 is_member函数现在为 looks like:

bool sparse_set::is_member(size_t i){
    bool init = is_init[i >> INIT_SHIFT] & (1UL << (i & INIT_MASK));
    return init && sparse[i] < n && dense[sparse[i]] == i;
}

在x86(gcc)上生成的程序集现在开始于:

mov     rax, QWORD PTR [rdi+24]
mov     rdx, rsi
shr     rdx, 8
mov     rdx, QWORD PTR [rax+rdx*8]
xor     eax, eax
bt      rdx, rsi
jnc     .L2
...

.L2:
退回

这些都与位图检查相关联。一切都将很快(并且由于它不是数据流的一部分，因此通常会走出关键路径)。

通常，此方法的成本取决于您的集合的密度以及您要调用的函数- is_member是该方法最差的情况，因为某些功能(例如 clear)根本不受影响，而其他功能(例如例如 iterate)可以批处理 is_init检查，并且每个 INIT_COVERAGE元素仅执行一次(这意味着示例值的开销将再次为〜1％)。

有时，这种方法比OP链接中建议的方法要快，尤其是当处理元素不在集合中时-在这种情况下， is_init检查将失败，并且通常会缩短其余代码，在这种情况下，您可以使用一个工作集它比 sparse数组的大小小得多(使用示例粒度为256倍)，因此可以大大减少DRAM或外部缓存级别的丢失。

对于这种方法，颗粒大小本身是重要的可调参数。直观地讲，较大的颗粒尺寸在首次访问该颗粒所覆盖的元素时会付出较大的初始化成本，但会节省内存和前期 is_init初始化成本。您可以想出一个公式，在简单的情况下可以找到最佳大小-但是行为也取决于值和其他因素的“聚类”。最后，在不同的工作负载下使用动态粒度来覆盖您的基础是完全合理的-但这是以可变类次为代价的。

真的很懒

值得注意的是， calloc和lazy init解决方案之间存在相似之处:两者都根据需要懒惰地初始化内存块，但是 calloc解决方案通过带有页表和TLB条目的MMU魔术在硬件中隐式地跟踪此内存块，而lazy init解决方案在软件中完成，并带有位图，该位图可明确跟踪已分配的颗粒。

硬件方法的优点是(在“命中”情况下)几乎是免费的，因为它使用CPU中始终存在的虚拟内存支持来检测未命中，但是软件案例的优点是可移植并允许精确控制颗粒大小等

您实际上可以结合使用这些方法，以形成一种不使用位图甚至根本不需要 dense数组的惰性方法:只需将 sparse数组与 mmap作为 PROT_NONE一起分配，因此每当您从 sparse数组中的未分配页面。您发现了故障，并在 sparse数组中为页面分配了一个指示每个元素“不存在”的标记值。

对于“热门”情况，这是最快的方法:您不再需要任何 ... && dense[sparse[i]] == i检查。

缺点是:

您的代码实际上是不可移植的，因为您需要实现故障处理逻辑，该逻辑通常是特定于平台的。

您无法控制颗粒大小:它必须为页面粒度(或其某些倍数)。如果您的集合非常稀疏(例如，占4096个元素中的少于1个)并且分布均匀，那么您最终将付出高昂的初始化成本，因为您需要处理错误并为每个元素初始化一整页的值。

Misses(即对设置不存在的元素的非插入访问)即使在该范围内不存在任何元素也需要分配页面，或者每次都会很慢(导致故障)。

1此实现没有“范围检查”-即，它不检查 i是否大于 MAX_ELEM-根据您的用例，您可能要检查一下。我的实现使用了 MAX_ELEM的模板参数，这可能会导致代码速度稍快，但也会导致膨胀，并且最好也将max size设为类成员。

2确实，您唯一需要使用的是在幕后调用 calloc或执行等效的零填充优化的条件，但是根据我的测试，更多惯用的C++方法(例如 new int[size]())只需要在分配之后加上 memset即可。 gcc确实优化了 malloc，然后将 memset转换为 calloc，但是如果您还是想避免使用C例程，那将没有用!

3精确地，您需要额外一位来跟踪 sparse数组的每128位。