如何实现确定性的malloc

Met*_*est 6 c linux malloc x86

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

现在,我希望所有内存分配和释放在两个进程中以完全相同的方式发生。最简单的方法是什么?写我自己的malloc和免费的吗?那么分配给其他功能(例如mmap)的内存又如何呢?

Syl*_*sne 4

我想知道你想实现什么目标。如果您的过程是确定性的,那么分配/释放的模式应该是相同的。

唯一可能的区别可能是返回的地址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;
}
Run Code Online (Sandbox Code Playgroud)

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

(编者注:MAP_FIXED可能不是您想要的。如果可能的buf_addr话,指定为提示而不是已经请求该地址。使用 时,将返回错误或您提供的地址。检查对于非大小写有意义,这赢得了不要替换代码或共享库或其他任何东西的现有映射。Linux 4.17 引入了它,您可以使用它使 mmap 返回错误,而不是您不想使用的错误地址处的内存。但仍然保留检查这样你的代码就可以在旧内核上运行。)NULLMAP_FIXEDmmapmalloc_buffer != (void*)but_addrFIXEDMAP_FIXED_NOREPLACE

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

假设您的 malloc / free 模式使用是确定性的。并且您不使用不确定的库。


然而,我认为一个更简单的解决方案是保持算法的确定性,而不是依赖于地址。这个有可能。我曾参与过一个大型项目,其中多台计算机必须确定性地更新状态(以便每个程序具有相同的状态,同时仅传输输入)。如果除了引用对象之外,您不使用指针来做其他事情(最重要的是永远不要将指针值用于任何事情,不是作为散列,不是作为映射中的键,...),那么您的状态将保持确定性。

除非您想要做的是能够对整个进程内存进行快照并进行二进制比较来发现差异。我认为这是一个坏主意,因为你怎么知道他们都在计算中达到了相同的点?比较输出,或者让进程能够计算状态的哈希并使用它来检查它们是否同步要容易得多,因为您可以控制何时完成(因此它也变得确定性,否则你的测量是不确定的)。