I am porting a project from C to Rust. The C project manages all memory allocation using chunk allocators. All memory is freed at the end. Another property of the implementation is that a memory reference to an object is never reused or changed, so that any code that is using the reference doesn't need to worry that the object they refer to will be somehow deleted and the reference will become invalid.
When porting to Rust, I had to decide whether to keep the existing model or adopt a different strategy where each allocation is freed as soon as it is not needed anymore. I decided in the end that I want to retain the existing design because freeing objects at intermediate stage is not only ineffficient, but it is also not always feasible.
In the interest of learning Rust I decided to implement my own allocators in Rust, mimicing how it works in the C code.
One of the first things I needed is a string allocator. In the C version a chunk allocator hands out slices of strings which are then used to cache all possible strings. I won't show the C code here, but it is quite straight forward implementation.
One key point here is that the string slices are guaranteed to be stable, i.e. they do not change or move around.
My first attempt to write this in Rust looked like this:
struct StringChunk {
chunk: [u8; 1024],
}
struct StringAllocator {
chunks: Vec>,
pos: usize
}
impl StringAllocator {
fn new() -> Self {
StringAllocator {
chunks : vec![Box::new(StringChunk{ chunk: [0; 1024] })],
pos: 0
}
}
fn alloc_string(&mut self, n: usize) -> &mut [u8] {
let cur = self.chunks.last_mut();
match cur {
None => {
self.chunks.push(Box::new(StringChunk{ chunk: [0; 1024] }));
}
Some(p) => {
if self.pos + n > p.chunk.len() {
self.chunks.push(Box::new(StringChunk{ chunk: [0; 1024] }));
self.pos = 0;
}
}
}
let i = self.chunks.len()-1;
let top = &mut self.chunks[i];
let pos = self.pos;
self.pos = self.pos + n;
&mut top.chunk[pos .. self.pos]
}
}
This version has the issue that strings are allocated only from the top most chunk. So even if space is available in previous chunks they are not used.
The allocator returns a slice into a byte array. To ensure that we never invalidate a reference, the vector in StringAllocator contains a pointer to a chunk of memory. Thus as the array grows, the references to the slices still remain valid.
One curiousity in Rust I discovered is this:
Box::new(StringChunk{ chunk: [0; 1024] })
Above seems to create the byte array of 1024 elements on the stack and then pass to Box::new() which presumably copies the array to
heap memory. There appears to be no placement new equivalent in Rust, although I think some library functions are available to work around this.
