I wrote my first code in Rust and decided to recall the buddy algorithm, which I suggested at work for our embedded software.
I hope you can give me some advise on things like:
- How to make it safe (not use unsafe-keyword), while keeping in mind that the purpose of this algorithm is to managing someone static heap in some sense.
- Any improvements on my general design?
- Any improvements on my rust code?
- If this would be professional code, what would I have to do so that you would consider accepting a PR including the internal functions of my code? (Except for much better testing, which I outrageously did not do)
#[derive(Clone)]
#[derive(Copy)]
struct Node {
expanded : bool,
filled : bool
}
const BUFFER_SIZE: u32 = 65536; //16777216;
const MANAGEMENT_SIZE : u32 = BUFFER_SIZE*log2(BUFFER_SIZE);
static mut NODES : [Node; MANAGEMENT_SIZE as usize] = [Node {expanded: false, filled: false}; MANAGEMENT_SIZE as usize];
const INVALID: u32 = 0xffffffff;
const fn _get_lhs_index(index: u32) -> u32{
return index*2;
}
const fn _get_rhs_index(index: u32) -> u32{
return index*2 + 1;
}
const fn log2 (mut n: u32) -> u32 {
let mut step = 0;
loop {
if n / 2 >= 1 {
step += 1;
n = n / 2;
continue;
}
return step;
}
}
fn _internal_buddy_get(size:u32, index : u32, offset: u32) -> u32 {
unsafe {
let node : &mut Node = &mut NODES[(index - 1) as usize];
let base : u32 = 2;
let node_size = if index == 0 { BUFFER_SIZE } else { BUFFER_SIZE / base.pow(log2(index)) };
/*
** This should not happen,
** but someone might try to allocate more than we can give him
**/
if size > node_size {
return INVALID;
}
//if the node is filled we cannot possibly have more space
if node.filled {
return INVALID;
}
/* If the size is more than half, this is the right node to fill
** We have to check if it not already expanded */
if size > ((node_size / 2) + 1) {
if node.expanded == false {
node.filled = true;
return offset;
}
return INVALID;
}
//The amount of memory is too small for this node, we pass the problem
node.expanded = true; //the node must be expanded
let result : u32 = _internal_buddy_get(size, _get_lhs_index(index), offset); //to the lhs
if result != INVALID {
return result;
}
return _internal_buddy_get(size, _get_rhs_index(index), offset + node_size / 2); //to the rhs
}
}
fn _internal_buddy_remove(index: u32, node_index: u32, offset: u32) -> bool {
unsafe {
let node : &mut Node = &mut NODES[(node_index - 1) as usize];
let base : u32 = 2;
let node_size = if node_index == 0 { BUFFER_SIZE } else { BUFFER_SIZE / base.pow(log2(node_index)) };
//if node is filled & offset equals index -> that is the node we are looking for
if node.filled {
if offset == index {
node.filled = false;
return true;
} else {
return false;
}
}
//if node is expanded -> check kids
if node.expanded {
let success: bool;
if index < offset + node_size/2 {
success = _internal_buddy_remove(index, _get_lhs_index(node_index), offset);
} else {
success = _internal_buddy_remove(index, _get_rhs_index(node_index), offset+node_size/2);
}
if success == false {
return false;
}
let lhs : &mut Node = &mut NODES[(_get_lhs_index(node_index)-1) as usize];
let rhs : &mut Node = &mut NODES[(_get_rhs_index(node_index)-1) as usize];
//check if the child are still expanded or filled; if not, reduce node
if lhs.expanded == false && lhs.filled == false && rhs.filled == false && rhs.expanded == false
{
node.expanded = false;
}
return true;
}
return false;
}
}
fn buddy_get(size: u32) -> u32 {
_internal_buddy_get(size, 1, 0)
}
fn buddy_remove(index: u32) -> bool {
_internal_buddy_remove(index, 1, 0)
}
fn main() {
let base : u32 = 2;
assert!(BUFFER_SIZE / base.pow(log2(1)) == BUFFER_SIZE);
assert!(BUFFER_SIZE / base.pow(log2(2)) == BUFFER_SIZE / 2);
assert!(BUFFER_SIZE / base.pow(log2(3)) == BUFFER_SIZE / 2);
assert!((BUFFER_SIZE & (BUFFER_SIZE - 1)) == 0); //assert that the BUFFER_SIZE is a power of 2.
let a : u32 = buddy_get(16);
assert!(buddy_remove(a)==true);
let b : u32 = buddy_get(128);
assert!(b==0);
let c : u32 = buddy_get(333);
assert!(buddy_remove(b)==true);
let d : u32 = buddy_get(68);
assert!(buddy_remove(d)==true);
let e : u32 = buddy_get(2000);
let c : u32 = buddy_get(30019);
assert!(buddy_remove(e)==true);
assert!(buddy_remove(1010001) == false);
println!("{}", a);
println!("{}", b);
println!("{}", c);
println!("{}", d);
println!("{}", e);
}
Edit: Better tested & bugfixed stuff.
log2loop is oddly structured. And by not taking advantage ofn.leading_zeros()it is reinventing the wheel. // A comment describing the memory layout is needed, so e.g. a maintainer can figure out if something is an OBOB. Consider citing a reference -- the wiki entry uses different terminology from what this code uses. // First step in extracting helpers to reduce theunsafefootprint would be adding line-granularity "unsafe!" comments. // buddy_remove could write 0xdeadbeef. \$\endgroup\$