如何实现确定性malloc

Question

我有两个应用程序实例，输入和执行顺序相同。因此，其中一个实例是冗余的，并用于将内存中的数据与另一个实例进行比较，作为一种错误检测机制。

现在，我希望在这两个进程中，所有内存分配和释放都以完全相同的方式发生。最简单的方法是什么？编写自己的malloc和free函数吗？那么使用其他函数（如mmap）分配的内存怎么办？

- MetallicPriest

---

你是说，完全一样的方式吗？我记得你说过它们有"相同的执行顺序"。 - buddhabrot

你可能需要第三个实例来确定哪些不同的结果是正确的。 - Alexey Frunze

执行顺序是相同的，但是由于malloc是不确定的，它的地址可能会不同。 - MetallicPriest

malloc是确定性的，就像每个计算机算法一样。由于设计原因，计算机在生成非确定性（随机数）值方面表现非常糟糕。可能不确定的是匿名mmap返回的内存。 - Sylvain Defresne

@MetallicPriest 从glibc实现的malloc源代码（http://sourceware.org/git/?p=glibc.git;a=blob;f=malloc/malloc.c;h=8608083adbe65c530a0d8ac3bbf547d85586b678;hb=HEAD）来看，该算法似乎是确定性的（不是随机的，也不会读取未初始化的内存）。但是，对于大块分配，它确实调用了`mmap`，这部分是不确定性的。 - Sylvain Defresne

Answer 1

不确定性的不仅是，还有mmap（获取更多内存空间的基本系统调用；它不是函数，而是系统调用，因此从应用程序的角度来看，它是基本或原子级别的；因此你不能在应用程序中重写它），这是因为Linux上的地址空间布局随机化。

您可以通过以下方式禁用它：

 echo 0 > /proc/sys/kernel/randomize_va_space

作为root用户，或通过sysctl。

如果您不禁用地址空间布局随机化，则无法进行操作。

您之前曾问过类似的问题（链接），在那里我解释了您的malloc并不总是确定性的。

我仍然认为对于某些实际应用，malloc无法是确定性的。例如，想象一下一个程序具有哈希表，以其正在启动的子进程的pid为键。该表中的冲突在所有进程中都不同等等。

因此，我认为您无法使malloc在您的意义上是确定性的，无论您尝试什么（除非您将自己限制在一个非常狭窄的可检查点应用程序类别中，那么这样的软件将不会非常实用）。

- Basile Starynkevitch

---

你说它只是由于ASLR而变得不确定，否则它是确定的？你确定吗？这适用于sbrk和mmap吗？如果没有管理员权限，如何禁用ASLR？ - MetallicPriest

我不知道sbrk，但我相信是的。据我所知，ASLR需要禁用root权限（否则这是一个巨大的安全漏洞）。 - Basile Starynkevitch

但是我在某个地方读到，可以使用setarch x86_64 -R来进行会话。 - MetallicPriest

我不理解通过pid索引哈希表会如何使malloc不确定性。这将使进程在使用malloc时不确定性，但该函数本身仍然是确定性的。我曾经参与了一个需要确定性的项目，只要注意不从外部引入非确定性（如你所说的来自其他进程的pid或使用指针的哈希），并且不使用x87 FPU（而是使用SSE），那么你的程序就可以是确定性的。 - Sylvain Defresne

Answer 2

简而言之，如其他人所述：如果您的程序指令的执行是确定性的，则由malloc()返回的内存将是确定性的，这假设您的系统实现不具有某种调用random()或类似功能的方式。如果您不确定，请阅读您的系统malloc的代码或文档。

这可能有个例外，就是ASLR，正如其他人也所说的那样。如果您没有根特权，您可以通过personality(2)系统调用和ADDR_NO_RANDOMIZE参数禁用它。有关个性化的更多信息，请参见此处。

编辑：我还应该说一下，如果您不知道，您正在进行的操作称为双向模拟，这是一种经过充分研究的技术。如果您不知道这个术语，可以使用该关键字进行搜索。

- tdenniston

Answer 3

我想知道你想要实现什么。如果你的过程是确定性的，那么分配/释放的模式应该是相同的。 唯一可能的区别可能是由malloc返回的地址。但你应该不依赖它们（最简单的方法是不使用指针作为键映射或其他数据结构）。即使这样，只有在分配不是通过sbrk进行的情况下（glibc对大型分配使用匿名mmap），或者如果你正在使用mmap时才会有差异（因为默认情况下地址是由内核选择的）。

如果您真的想要完全相同的地址，一种选择是使用一个大的静态缓冲区，并编写一个自定义分配器来使用该缓冲区中的内存。这样做的缺点是强制您事先知道所需的最大内存量。在非 PIE 可执行文件（gcc -fno-pie -no-pie）中，静态缓冲区每次都会具有相同的地址。对于 PIE 可执行文件，您可以禁用内核的地址空间布局随机化以加载程序。在共享库中，禁用 ASLR 并两次运行相同的程序应该导致动态链接器对映射库的位置做出相同的选择。

如果您不知道要使用的内存的最大大小，或者如果您不希望每次增加此大小时重新编译，您还可以使用mmap将大型匿名缓冲区映射到固定地址。只需将缓冲区的大小和要使用的地址作为参数传递给进程，并使用返回的内存在其上实现自己的malloc即可。

static void* malloc_buffer = NULL;
static size_t malloc_buffer_len = 0;

void* malloc(size_t size) {
    // Use malloc_buffer & malloc_buffer_len to implement your
    // own allocator. If you don't read uninitialized memory,
    // it can be deterministic.
    return memory;
}

int main(int argc, char** argv) {
    size_t buf_size = 0;
    uintptr_t buf_addr = 0;
    for (int i = 0; i < argv; ++i) {
        if (strcmp(argv[i], "--malloc-size") == 0) {
            buf_size = atoi(argv[++i]);
        }
        if (strcmp(argv[i], "--malloc-addr") == 0) {
            buf_addr = atoi(argv[++i]);
        }
    }

    malloc_buffer = mmap((void*)buf_addr, buf_size, PROT_WRITE|PROT_READ,
                         MAP_FIXED|MAP_PRIVATE, 0, 0);
    // editor's note: omit MAP_FIXED since you're checking the result anyway
    if (malloc_buffer == MAP_FAILED || malloc_buffer != (void*)but_addr) {
        // Could not get requested memory block, fail.
        exit(1);
    }

    malloc_size = buf_size;
}

通过使用MAP_FIXED，我们告诉内核替换与buf_addr重叠的任何现有映射。

（编辑注：MAP_FIXED可能不是您想要的。将buf_addr指定为提示而不是NULL已经请求该地址（如果可能）。使用MAP_FIXED，mmap将返回错误或您提供的地址。 malloc_buffer！=（void *）but_addr 检查对于非FIXED情况是有意义的，它不会替换代码或共享库或其他任何东西的现有映射。Linux 4.17引入了MAP_FIXED_NOREPLACE，您可以使用它使mmap返回错误而不是在您不想使用的错误地址上分配内存。但仍然保留检查，以便您的代码适用于旧内核。）

如果您使用此块来实现自己的malloc并且在代码中不使用其他非确定性操作，则可以完全控制指针值。

这意味着您对malloc/free的使用模式是确定性的，并且您不使用非确定性的库。

---

然而，我认为一个更简单的解决方案是使您的算法具有确定性并且不依赖于地址。这是可能的。我曾经参与过一个大型项目，在该项目中，多台计算机必须以确定性方式更新状态（以便每个程序具有相同的状态，同时只传输输入）。如果您不使用指针来引用对象之外的其他内容（最重要的是永远不要将指针值用于任何事情，不要用作哈希，不要用作地图中的键等），那么您的状态将保持确定性。

除非您想要能够快照整个进程内存并进行二进制差异比较以检测差异。我认为这是一个坏主意，因为你如何知道它们两个在计算中是否到达了相同的点？比较输出或使进程能够计算状态的哈希并使用它来检查它们是否同步要容易得多，因为您可以控制何时执行此操作（因此它也变得具有确定性，否则您的测量结果就是不确定的）。

- Sylvain Defresne

---

如果你真的想要完全相同的地址，一个选项是拥有一个大的静态缓冲区，并编写一个自定义分配器来使用这个缓冲区中的内存。这正是我一直在做的，但现在我想转向更通用的方法。 - MetallicPriest

@Sylvain。显然，MetallicPriest想要创建一些检查点机制。但他非常保密。 - Basile Starynkevitch

不仅内核决定是否使用ASLR：可执行文件也必须支持它。如果您希望静态地址每次都相同，只需使用**gcc -fno-pie -no-pie**构建非PIE可执行文件。(现代发行版的GCC默认使用PIE)。请参见32位绝对地址在x86-64 Linux中不再允许？。但是，如果您的代码在共享库中，则需要使用内核sysctl或其他方法禁用ASLR。我认为动态链接只是使用mmap，内核本身并不知道正在映射的是库。 - Peter Cordes

Answer 4

在编写高可靠性代码时，通常的做法是避免使用malloc和其他动态内存分配。有时候采用的折衷方案是仅在系统初始化期间进行所有这些分配。

- Martin Thompson

Answer 5

你可以使用共享内存来存储数据。这样两个进程都可以访问它，而且你可以以确定性的方式填充数据。

- puikos

---

-1，噢，请在写之前先考虑一下。执行冗余操作的整个目的是能够比较两个进程在它们自己的地址空间中执行时的内存。 - MetallicPriest