4
\$\begingroup\$

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:

  1. 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.
  2. Any improvements on my general design?
  3. Any improvements on my rust code?
  4. 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.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ The log2 loop is oddly structured. And by not taking advantage of n.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 the unsafe footprint would be adding line-granularity "unsafe!" comments. // buddy_remove could write 0xdeadbeef. \$\endgroup\$
    – J_H
    Oct 27, 2023 at 18:57
  • \$\begingroup\$ Hey, could you explain what you mean with all the unsafe stuff and what you mean with buddy_remove could write 0xdeadbeef? \$\endgroup\$
    – Niclas
    Oct 29, 2023 at 19:52
  • 1
    \$\begingroup\$ (1.) I anticipate that some of the code could be evicted into helper(s) that are safe. It seems there's more work to explore how much flexibility we have there. I do not yet know exactly where to focus that. (2.) It's pretty standard to write (arbitrary) 0x55 bytes, or 0xDEADBEEF words, into deallocated memory. There's at least two advantages. An app that does reference-after-free will have a hard time passing its unit tests, since it reads back junk. And gdb debugger memory dumps become easier to read, showing free memory. \$\endgroup\$
    – J_H
    Oct 29, 2023 at 19:58
  • \$\begingroup\$ thank you! especially for the deadbeef advice - never heard of that \$\endgroup\$
    – Niclas
    Oct 29, 2023 at 20:11

1 Answer 1

3
\$\begingroup\$

Small Stuff

  1. As J_H mentioned, there are more efficient ways to compute log2 of a u32 - 31 - n.leading_zeros() should do.

  2. base.pow() with base = 2 should really be 1 << bits. Are you really intending to use another base value in the future?

  3. The two derive macros can be combined in one line and probably also should include Default - #[derive(Copy, Clone, Default)], then you can also write Node::default() instead of Node { expanded: false, filled: false }. Especially in case you add additional properties in the future this makes it easier.

  4. Consider using usize everywhere since your dealing with memory management anyway. Removes the need for a bunch of casts.

    Since usize type size depends on the platform, the improved log2 implementation would then have to be something like std::mem::size_of::<usize>() * 8 - 1 - (n.leading_zeros() as usize)

Regarding Professional Code

No I wouldn't accept this as a PR, mainly due to lack of useful documentation that will help the next developer to maintain this even if they don't know what the Buddy algorithm is.

  • Explain what the code does, ideally with a link to Wikipedia or wherever there is a good description of the algorithm (hopefully also one that's likely to be around for a while).
    • Make sure that your code terminology conforms to publicly available explanations - the terms buffer or management size don't really appear anywhere.
    • Also why is the number of nodes you manage dependent on BUFFER_SIZE?
  • Explain how the code implements the algorithm - i.e. what is your design, what are the trade-offs, limitations etc.
  • Document the invariants of the public methods - what do they expect, what will they return under different circumstances and why.

Other problematic things:

  1. Naming - when thinking about memory allocations from a user perspective one thinks about allocate and free - these two terms do not appear anywhere in your code.
  2. A better name for BUFFER_SIZE would be BLOCK_SIZE (to conform to generally available description of the algorithm) and MANAGEMENT_SIZE should be NUM_BLOCKS.

Rustiness

  1. While a sentinel value to indicate failure is a common programming tool, in Rust functions that can fail should return Result<> so that they can return an actual error and not pick some (more or less arbitrary value) as error indicator. Returning a proper error also let's you include additional details as to what the failure specifically is.

  2. The reason why you currently have unsafe is because you have a global static mutable array. The reason it's unsafe is because it's not thread-safe. Pretty sure that you can do away with it by using a combination of lazy_static (or apparently once_cell in newer compiler versions) and Mutex. The recursive nature of the implementation might be problematic though in this case.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.