Implementing MESH - A randomized memory compacting allocator for C/C++

I've been wanting to implement MESH as an allocator lib for Rust.
The issue that I've find is that MESH is a randomized allocator. And when there's no randomization, the allocation patterns that usually we can pre-cunt with don't exist anymore. Therefore the algorithm isn't that effective.

My question is how is it possible in Rust to have an allocator which is randomized? Since the randomness has to come from the OS mostly. But I'm not sure we can call it inside the allocator code. Neither what happens if the OS is not one of the typical ones.

Thanks in advance,

References:

Mesh paper

rand is the de facto standard crate for randomness in Rust.

I don't understand what is being asked here. It's perfectly fine to call into a PRNG inside an allocator. An allocator is just a hook that gets called when some data structure requests a memory region; it is not otherwise special in what is and isn't allowed to be called inside the allocation algorithm itself.

I was under the impression that an allocator lib must be no_std and so, rand is no longer a viable option unless you seed it or something similar with different seeds on each run.

An allocator doesn't have to be no_std. A quick experiment confirms this: I was able to create a custom allocator that depends on rand and uses rand::rngs::SmallRng::from_entropy() for seeding it with OS-provided entropy, and then calls libc::malloc() to perform the actual allocation (thus, definitely calling out to the OS). A crate using this dummy allocator for creating a Vec compiled and ran successfully.

3 Likes

Thanks a lot! I was under wrong assumptions.