How to implement deterministic malloc

Question

Let's say I have two instances of the application, with the same inputs and the same execution sequence. Therefore, one instance is redundant and is used to compare data in memory with another instance as a kind of error detection mechanism.

Now I want all memory allocations and memory deallocations to be done in exactly the same way in two processes. What is the easiest way to achieve this? Write your own malloc and free? What about memory allocated by other functions like mmap?

Answer 1

I wonder what you are trying to achieve. If your process is deterministic, then the distribution / release scheme should be the same.

The only possible difference could be the address returned by malloc . But you probably shouldn't depend on them (the easiest way is to not use pointers as a key map or other data structure). And even in this case, the difference should only be if the distribution is not performed via sbrk (glibc uses anonymous mmap for large allocations) or if you use mmap (since the address is selected by the kernel by default).

If you really want to have exactly the same address, one option is to have a large static buffer and write your own allocator that uses the memory from this buffer. This has a drawback that makes you know in advance the maximum amount of memory you will ever need. In the non-PIE executable ( gcc -fno-pie -no-pie ), the static buffer will always have the same address. For the PIE executable, you can disable the randomization of the kernel address space structure for loading programs. In a shared library, disabling ASLR and running the same program twice should cause the dynamic linker to make the same choice of library display location.

If you do not know in advance what maximum memory size you want to use, or if you do not want to recompile this increase in size each time, you can also use mmap to map a large anonymous buffer to a fixed address. Just pass the buffer size and address to use as a 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 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; } 

Using MAP_FIXED , we tell the kernel to replace any existing mappings that overlap with this new one in buf_addr .

(Editor's note: MAP_FIXED is probably not what you need . Specifying buf_addr as a hint instead of NULL already asks for this address, if possible. With MAP_FIXED mmap either return an error or the address you gave it. malloc_buffer != (void*)but_addr checking malloc_buffer != (void*)but_addr makes sense for the non- FIXED case, which does not replace the existing display of your code, shared library or anything else. In Linux 4.17, MAP_FIXED_NOREPLACE appeared MAP_FIXED_NOREPLACE which can be used so mmap returns an error instead of memory to the wrong address that you don’t want to use. But nevertheless, leave the checkbox selected so that your code runs on older kernels.)

If you use this block to implement your own malloc and do not use other non- deterministic operations in your code, you can completely control the pointer values.

This assumes that your use of the malloc / free pattern is deterministic. And that you do not use libraries that are non-deterministic.

---

However, I think a simpler solution is to keep your algorithms deterministic and not depend on addresses. It is possible. I worked on a large-scale project in which several computers had to determine the state in detail (so that each program had the same state, transmitting only the input data). If you do not use the pointer for anything other than a reference to objects (the most important thing is never to use the value of the pointer for anything other than a hash code, not as a key on the map, ...), then your state will remain deterministic ,

If you need to take a snapshot of the entire process memory and perform a binary analysis to determine the discrepancy. I think this is a bad idea, because how do you know that both of them have reached the same point in their calculations? It is much easier to compare the output, or so that the process can calculate the status hash and use it to check if it is synchronized, because you can control when it will be done (and thus it will become deterministic, otherwise your measurement will be non- deterministic )

Answer 2

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

You can disable it with

  echo 0 > /proc/sys/kernel/randomize_va_space 

as root, or through sysctl .

If you do not disable the randomization of address space allocation, you are stuck.

And you asked a similar question earlier , where I explained that your malloc -s will not always be deterministic.

I still think that for some practical applications, malloc cannot be deterministic. Suppose, for example, that a program that has a hash table is started using pid -s child processes. The collision in this table will not be the same in all your processes, etc.

So, I believe that you will not be able to make deterministic malloc in your sense, no matter what you try (if you do not limit yourself to a very narrow class of applications at the checkpoint, so narrow that your software will not be very useful )

Answer 3

Simply put, as others have argued: if the execution of your program instructions is deterministic, then the memory returned by malloc() will be deterministic. This assumes your system implementation does not have any random() call or anything like that. If you are not sure, read the code or documentation for your malloc system.

This is possible with the exception of ASLR, like others. If you do not have root privileges, you can disable it for each process through syscall personality(2) and the ADDR_NO_RANDOMIZE parameter. See here for more information on personalities.

Edit: I must also say, if you do not know: what you are doing is called bisimulation and is a well-studied technique. If you don’t know the terminology, this can help you find this search term.

Answer 4

When writing high-reliability code, a common practice is to avoid allocating malloc and other dynamic memory. Sometimes a trade-off is used that must perform all such distribution only during system initialization.

Answer 5

You can use shared memory to store your data. It will be available from both processes, and you can fill it in a deterministic way.