Data structure for a toy memory allocator?

help
1

Hi!

I'm working on a basic memory allocator for a toy virtual machine (Universal Machine from a past ICFP contest). That VM operates on unsigned 32-bit numbers, the memory allocator should support the following operations:

- alloc(size: u32) -> u32 // returns VM address
- free(addr: u32)
- read(addr: u32, offset: u32) -> u32
- write(addr: u32, offset: u32, val: u32)

I'm using Rust vectors for mapping between VM addresses and real addresses of blocks of memory (which I also represent as vectors, even though they can't be resized after allocated). I also use a min priority queue for tracking free cells, so that VM addresses can be reused when they are freed.

So, basically my memory allocator data structure is like this:

struct Mem {
    data: Vec<Option<Vec<u32>>>,
    free_pq: BinaryHeap<Reverse<u32>>,
}

I use Option<> to represent "holes" in VM address space (after "free" operation). Internal Vec represents the allocated memory block.

The full code and implementation of the operations is here: Github gist

Question: Could you please let me know if this is a good choice of the data structure in Rust? Will it work as expected or there are some leaks/inefficiencies which I am not seeing now? I am a Rust beginner (this is basically my first program), so general comments about style/idioms are also welcome.

I know that Vector of Vectors has bad cache performance for obvious reasons (vectors for allocated blocks will be all over the place in memory), but since the allocated blocks can be of any size and there can be "holes" in VM address space (after "free" operations) it's not trivial to keep VM memory in contiguous space while keeping free/alloc operations efficient. But probably possible, I'm thinking about that :slight_smile:

Thank you!