I'm trying to make a simple allocator that allocates and deallocates buffers from a fixed pool of buffers.
struct AllocatedMemory<'a> {
mem: &'a mut [u8],
next: Option<&'a mut AllocatedMemory<'a>>,
}
struct Alloc<'a> {
glob: Option<&'a mut AllocatedMemory<'a>>,
}
impl<'a> Alloc<'a> {
fn alloc_cell(mut self: &mut Alloc<'a>) -> &mut AllocatedMemory<'a> {
let rest: Option<&'a mut AllocatedMemory<'a>>;
match self.glob {
Some(ref mut root_cell) => {
rest = std::mem::replace(&mut root_cell.next, None);
}
None => rest = None,
}
match std::mem::replace(&mut self.glob, rest) {
Some(mut root_cell) => {
return root_cell;
}
None => panic!("OOM"),
}
}
fn free_cell(mut self: &mut Alloc<'a>, mut val: &'a mut AllocatedMemory<'a>) {
match std::mem::replace(&mut self.glob, None) {
Some(mut x) => {
let discard = std::mem::replace(&mut val.next, Some(x));
let rest: Option<&'a mut AllocatedMemory<'a>>;
}
None => {}
}
self.glob = Some(val);
}
}
fn main() {
let mut buffer0: [u8; 1024] = [0; 1024];
let mut buffer1: [u8; 1024] = [0; 1024];
{
let mut cell1: AllocatedMemory = AllocatedMemory {
mem: &mut buffer1[0..1024],
next: None,
};
let mut cell0: AllocatedMemory = AllocatedMemory {
mem: &mut buffer0[0..1024],
next: None,
};
let mut allocator = Alloc { glob: None };
allocator.free_cell(&mut cell1); //populate allocator with a cell
allocator.free_cell(&mut cell0); //populate allocator with another cell (why does this fail?)
let mut x = allocator.alloc_cell();
allocator.free_cell(x);
let mut y = allocator.alloc_cell();
let mut z = allocator.alloc_cell();
allocator.free_cell(y);
allocator.free_cell(z);
}
}
The error is
error: `cell0` does not live long enough
allocator.free_cell(&mut cell0); //populate allocator with another cell (why does this fail?)
when I simply remove cell0 and only have cell1 available to my cell pool then the following errors happens:
error: allocator does not live long enough
let mut x = allocator.alloc_cell();
^~~~~~~~~
note: reference must be valid for the block suffix following statement 0 at 46:69...
next: None};
let mut cell0 : AllocatedMemory = AllocatedMemory{mem: &mut buffer0[0..1024],
next: None};
let mut allocator = Alloc {glob : None};
allocator.free_cell(&mut cell1); //populate allocator with a cell
//allocator.free_cell(&mut cell0); //populate allocator with another cell (why does this fail?)
note: ...but borrowed value is only valid for the block suffix following statement 2 at 49:48
let mut allocator = Alloc {glob : None};
allocator.free_cell(&mut cell1); //populate allocator with a cell
//allocator.free_cell(&mut cell0); //populate allocator with another cell (why does this fail?)
let mut x = allocator.alloc_cell();
allocator.free_cell(x);
...
error: aborting due to previous error
Does anyone have a recommendation on how to fix this code so it compiles and may have 2+ items in the free list?
I want to populate a list of references to arrays and then be able to pop them - use them for a while and place the used/finished value back onto the freelist.
The motivation here is to build a library that uses the #![nostd] directive, so it needs an allocator interface to operate properly.
Thanks to starblue's pointer, I decided to force the lifetimes of the allocator and cells to be the same by placing them into a struct and putting that struct on the stack. The final result is here:
// This code is placed in the public domain
struct AllocatedMemory<'a> {
mem : &'a mut [u8],
next : Option<&'a mut AllocatedMemory <'a> >,
}
struct Alloc<'a> {
glob : Option<&'a mut AllocatedMemory <'a> >,
}
impl<'a> Alloc <'a> {
fn alloc_cell(self : &mut Alloc<'a>) -> &'a mut AllocatedMemory<'a> {
match self.glob {
Some(ref mut glob_next) => {
let rest : Option<&'a mut AllocatedMemory <'a> >;
match glob_next.next {
Some(ref mut root_cell) => {
rest = std::mem::replace(&mut root_cell.next, None);
},
None => rest = None,
}
match std::mem::replace(&mut glob_next.next, rest) {
Some(mut root_cell) =>
{
return root_cell;
},
None => panic!("OOM"),
}
},
None => panic!("Allocator not initialized"),
}
}
fn free_cell(self : &mut Alloc<'a>,
mut val : & 'a mut AllocatedMemory<'a>) {
match self.glob {
Some(ref mut glob_next) => {
match std::mem::replace(&mut glob_next.next ,None) {
Some(mut x) => {
let _discard = std::mem::replace(&mut val.next, Some(x));
},
None => {},
}
glob_next.next = Some(val);
},
None => panic!("Allocator not initialized"),
}
}
}
struct AllocatorGlobalState<'a>{
cell1 : AllocatedMemory<'a>,
cell0 : AllocatedMemory<'a>,
sentinel : AllocatedMemory<'a>,
allocator :Alloc<'a>,
}
fn main() {
let mut buffer0 : [u8; 1024] = [0; 1024];
let mut buffer1 : [u8; 1024] = [0; 1024];
let mut sentinel_buffer : [u8; 1] = [0];
let mut ags : AllocatorGlobalState = AllocatorGlobalState {
cell1 : AllocatedMemory{mem: &mut buffer1[0..1024],
next: None},
cell0 : AllocatedMemory{mem: &mut buffer0[0..1024],
next: None},
sentinel : AllocatedMemory{mem: &mut sentinel_buffer[0..1], next: None},
allocator : Alloc {glob : None},
};
ags.allocator.glob = Some(&mut ags.sentinel);
ags.allocator.free_cell(&mut ags.cell1);
ags.allocator.free_cell(&mut ags.cell0);
{
let mut x = ags.allocator.alloc_cell();
x.mem[0] = 4;
let mut y = ags.allocator.alloc_cell();
y.mem[0] = 4;
ags.allocator.free_cell(y);
let mut z = ags.allocator.alloc_cell();
z.mem[0] = 8;
//y.mem[0] = 5; // <-- this is an error (use after free)
}
}
I needed to add the sentinel struct to avoid double borrowing of ags.allocator when doing multiple allocations.
cell.rs:65:19: 65:32 help: run `rustc --explain E0499` to see a detailed explanation
cell.rs:62:19: 62:32 note: previous borrow of `ags.allocator` occurs here; the mutable borrow prevents subsequent moves, borrows, or modification of `ags.allocator` until the borrow ends
With the sentinel being stored in Alloc I can guarantee that I never modify glob after the function returns.