How to implement deterministic malloc

Question

Say I have two instances of an application, with the same inputs and same execution sequence. Therefore, one instance is a redundant one and is used for comparing data in memory with the other instance, as a kind of error detection mechanism.

Now, I want all memory allocations and deallocations to happen in exactly the same manner in the two processes. What is the easiest way to achieve that? Write my own malloc and free? And what about memories allocated with other functions such as mmap?

Answer 1

I'm wondering what you are trying to achieve. If your process is deterministic, then the pattern of allocation / deallocation should be the same.

The only possible difference could be the address returned by malloc. But you should probably not depend on them (the easiest way being not using pointers as key map or other data structure). And even then, there should only be difference if the allocation is not done through sbrk (the glibc use anonymous mmap for large allocations), or if you are using mmap (as by default the address is selected by the kernel).

If you really want to have exactly the same address, one option is to have a large static buffer and to write a custom allocator that does use memory from this buffer. This has the disadvantage of forcing you to know beforehand the maximum amount of memory you'll ever need. In a non-PIE executable (gcc -fno-pie -no-pie), a static buffer will have the same address every time. For a PIE executable you can disable the kernel's address space layout randomization for loading programs. In a shared library, disabling ASLR and running the same program twice should lead to the same choices by the dynamic linker for where to map libraries.

If you don't know before hand the maximum size of the memory you want to use, or if you don't want to recompile each time this size increase, you can also use mmap to map a large anonymous buffer at a fixed address. Simply pass the size of the buffer and the address to use as parameter to your process and use the returned memory to implement your own malloc on top of it.

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;
}

By using MAP_FIXED, we are telling the kernel to replace any existing mappings that overlap with this new one at buf_addr.

(Editor's note: MAP_FIXED is probably not what you want. Specifying buf_addr as a hint instead of NULL already requests that address if possible. With MAP_FIXED, mmap will either return an error or the address you gave it. The malloc_buffer != (void*)but_addr check makes sense for the non-FIXED case, which won't replace an existing mapping of your code or a shared library or anything else. Linux 4.17 introduced MAP_FIXED_NOREPLACE which you can use to make mmap return an error instead of memory at the wrong address you don't want to use. But still leave the check in so your code works on older kernels.)

If you use this block to implement your own malloc and don't use other non-deterministic operation in your code, you can have complete control of the pointer values.

This suppose that your pattern usage of malloc / free is deterministic. And that you don't use libraries that are non-deterministic.

---

However, I think a simpler solution is to keep your algorithms deterministic and not to depend on addresses to be. This is possible. I've worked on a large scale project were multiple computer had to update state deterministically (so that each program had the same state, while only transmitting inputs). If you don't use pointer for other things than referencing objects (most important things is to never use pointer value for anything, not as a hash, not as a key in a map, ...), then your state will stay deterministic.

Unless what you want to do is to be able to snapshot the whole process memory and do a binary diff to spot divergence. I think it's a bad idea, because how will you know that both of them have reached the same point in their computation? It is much more easier to compare the output, or to have the process be able to compute a hash of the state and use that to check that they are in sync because you can control when this is done (and thus it become deterministic too, otherwise your measurement is non-deterministic).

Answer 2

Simply put, as others have stated: if the execution of your program's instructions is deterministic, then memory returned by malloc() will be deterministic. That assumes your system's implementation doesn't have some call to random() or something to that effect. If you are unsure, read the code or documentation for your system's malloc.

This is with the possible exception of ASLR, as others have also stated. If you don't have root privileges, you can disable it per-process via the personality(2) syscall and the ADDR_NO_RANDOMIZE parameter. See here for more information on the personalities.

Edit: I should also say, if you are unaware: what you're doing is called bisimulation and is a well-studied technique. If you didn't know the terminology, it might help to have that keyword for searching.

Answer 3

What is not deterministic is not only malloc but mmap (the basic syscall to get more memory space; it is not a function, it is a system call so is elementary or atomic from the application's point of view; so you cannot rewrite it within the application) because of address space layout randomization on Linux.

You could disable it with

 echo 0 > /proc/sys/kernel/randomize_va_space

as root, or thru sysctl.

If you don't disable address space layout randomization you are stuck.

And you did ask a similar question previously, where I explained that your malloc-s won't always be deterministic.

I still think that for some practical applications, malloc cannot be deterministic. Imagine for instance a program having an hash-table keyed by the pid-s of the child processes it is launching. Collision in that table won't be the same in all your processes, etc.

So I believe you won't succeed in making malloc deterministic in your sense, whatever you'll try (unless you restrict yourself to a very narrow class of applications to checkpoint, so narrow that your software won't be very useful).