Rust : pointer being freed was not allocated

Question

I learn how to write linklists from https://rust-unofficial.github.io/too-many-lists/sixth-random-bits.html, and I try to write an AvlTree with what I learned from it , but when I write a bit code, I'm stuck with this exception:

hello-rust(23862,0x204488600) malloc: *** error for object 0x600003b79140: pointer being freed was not allocated
hello-rust(23862,0x204488600) malloc: *** set a breakpoint in malloc_error_break to debug

I dont't know where should I change the code to make it right. Here's my all code:

use std::ptr::NonNull;

type Link<T> = Option<NonNull<Node<T>>>;

#[derive(Debug)]
pub struct Node<T> {
    elem: T,
    parent: Link<T>,
    left: Link<T>,
    right: Link<T>,
    bf: i8,
}

impl<T> Node<T> {
    pub fn new_with_elem(elem: T) -> Node<T> {
        Node {
            elem,
            parent: None,
            left: None,
            right: None,
            bf: 0,
        }
    }
}

#[derive(Debug)]
pub struct AvlTree<T> {
    root: Link<T>,
    count: usize,
}

impl<T: PartialEq + Eq + std::cmp::PartialOrd + Clone+std::fmt::Display> AvlTree<T> {
    pub fn new() -> AvlTree<T> {
        AvlTree { root: None, count: 0 }
    }

    pub fn insert(&mut self, elem: T) {
        let elem_clone = elem.clone();
        let mut new_node = Node::new_with_elem(elem);
        if self.count == 0 {
            self.root = new_link_with_node(new_node);
            self.count += 1;
            return;
        }
        let mut bf = 0;
        let mut parent: Link<T> = None;
        let mut n = self.root;
        while n.is_some() {
            n.map(|node| {
                unsafe {
                    println!("elem={}", &elem_clone);
                    let box_node = Box::from_raw(node.clone().as_ptr());
                    if elem_clone == box_node.elem {
                        return;
                    }
                    parent = n;
                    bf <<= 1;
                    if elem_clone < box_node.elem {
                        n = box_node.left;
                    } else {
                        n = box_node.right;
                        bf |= 1;
                    }
                }
            });
        }

    }
}

impl<T: std::fmt::Display> std::fmt::Display for Node<T> {
    fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
        write!(fmt, " elem:{},bf:{} | ", self.elem, self.bf)
    }
}

impl<T: std::fmt::Display> std::fmt::Display for AvlTree<T> {
    fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
        if self.root.is_none() {
            write!(fmt, " empty tree! ")
        } else {
            show_node(&self.root);
            write!(fmt, " print over ")
        }
    }
}

fn show_node<T: std::fmt::Display>(node: &Link<T>) {
    node.map(|n| {
        unsafe {
            let box_node = Box::from_raw(n.as_ptr());
            println!("{}", box_node);
            if box_node.left.is_some() {
                show_node(&box_node.left)
            }
            if box_node.right.is_some() {
                show_node(&box_node.right)
            }
        }
    });
}

fn new_link_with_node<T: PartialEq + Eq + std::cmp::PartialOrd + Clone>(node: Node<T>) -> Link<T> {
    NonNull::new(Box::into_raw(Box::new(node)))
}

Answer 1

The issue very likely comes from the fact that you are misusing Rust boxes. Boxes are, from an ownership point of view, owned pointers, that is, a pointer with the additional constraint that whomever owns it also owns the pointed data. This means that, whenever you create a box from an existing pointer, you "take" that data (which is why it's an unsafe operation). This implies that, whenever the box is dropped (at the end of the scope), the pointed data is also dropped.

In particular, this means that your show_node function actually "destroys" any node it takes as an argument (and by destroying I mean something much worse than freeing: it leads to UB).

If you are a beginner with Rust, I would advice against using unsafe blocks. Instead, you should try to solve your issue in a safe way, which is probably the idiomatic way of doing.