Does this code invoke UB? Why or why not?

I have tried to write a tree type that allocates nodes from a bump arena, and frees them all when it is dropped.

This is just for learning purposes btw, not for anything practical, so I'm not looking for general design/coding advice -- I'm specifically asking about whether the code is sound.

#![feature(maybe_uninit_uninit_array)]
use rand::random;
use std::cell::RefCell;
use std::mem::MaybeUninit;

pub struct Node<'a> {
    pub left: Option<&'a RefCell<Node<'a>>>,
    pub right: Option<&'a RefCell<Node<'a>>>,
}
pub struct Tree<'a> {
    pub root: Option<&'a RefCell<Node<'a>>>,
    arena: [MaybeUninit<RefCell<Node<'a>>>; 11_000],
    idx: usize,
}
impl<'a> Tree<'a> {
    pub fn alloc(&mut self) -> &'a RefCell<Node<'a>> {
        self.arena[self.idx] = MaybeUninit::new(RefCell::new(Node {
            left: None,
            right: None,
        }));
        let p = self.arena[self.idx].as_ptr();
        self.idx += 1;
        unsafe { &*p }
    }
    pub fn new() -> Self {
        Self {
            root: None,
            arena: MaybeUninit::uninit_array(),
            idx: 0,
        }
    }
}

fn main() {
    let mut t = Tree::new();
    t.root = Some(t.alloc());
    let mut cur = t.root.unwrap().borrow_mut();
    for _ in 0..10 {
        let left = random();
        let next = if left { &mut cur.left } else { &mut cur.right };
        *next = Some(t.alloc());
        cur = next.unwrap().borrow_mut();
    }
    std::mem::drop(cur);

    let mut cur = t.root.unwrap().borrow();
    loop {
        if let Some(left) = cur.left {
            println!("Left");
            cur = left.borrow();
        } else if let Some(right) = cur.right {
            println!("Right");
            cur = right.borrow();
        } else {
            break;
        }
    }
}

I can't tell what I'm doing wrong, but running this with Miri gives the following error:

error: Miri evaluation error: no item granting write access to tag <39151> found in borrow stack.
  --> src/main.rs:40:9
   |
41 |         *next = Some(t.alloc());
   |         ^^^^^^^^^^^^^^^^^^^^^^^ no item granting write access to tag <39151> found in borrow stack.
   |
   = note: inside call to `main` at /home/brennan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:67:34
   = note: inside call to closure at /home/brennan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:52:73
   = note: inside call to closure at /home/brennan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/sys_common/backtrace.rs:129:5
   = note: inside call to `std::sys_common::backtrace::__rust_begin_short_backtrace::<[closure@DefId(1:6020 ~ std[5aa8]::rt[0]::lang_start_internal[0]::{{closure}}[0]::{{closure}}[0]) 0:&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe], i32>` at /home/brennan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:52:13
   = note: inside call to closure at /home/brennan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panicking.rs:303:40
   = note: inside call to `std::panicking::r#try::do_call::<[closure@DefId(1:6019 ~ std[5aa8]::rt[0]::lang_start_internal[0]::{{closure}}[0]) 0:&&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe], i32>` at /home/brennan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panicking.rs:281:13
   = note: inside call to `std::panicking::r#try::<i32, [closure@DefId(1:6019 ~ std[5aa8]::rt[0]::lang_start_internal[0]::{{closure}}[0]) 0:&&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe]>` at /home/brennan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panic.rs:394:14
   = note: inside call to `std::panic::catch_unwind::<[closure@DefId(1:6019 ~ std[5aa8]::rt[0]::lang_start_internal[0]::{{closure}}[0]) 0:&&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe], i32>` at /home/brennan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:51:25
   = note: inside call to `std::rt::lang_start_internal` at /home/brennan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:67:5
   = note: inside call to `std::rt::lang_start::<()>`

This is definitely undefined behaviour, from the assume_init docs:

It is up to the caller to guarantee that the MaybeUninit<T> really is in an initialized state. Calling this when the content is not yet fully initialized causes immediate undefined behavior.

1 Like

The authors of MaybeUninit use it in a similar way: https://doc.servo.org/src/core/mem/maybe_uninit.rs.html#306-308

I have updated my code to use that library function, and Miri gives the same error.

Actually, in the specific case of [MaybeUninit<_>; N], this is actually safe and (atm) idiomatic. This type doesn't need to be initialized to be valid.

This isn't tied to why this invocation is UB, but the API is definitely unsound as is; nothing keeps me from creating a Tree<'static> and making falsely 'static references with it. Any internal references will need to be gated behind having a Pin<&'a mut Tree> rather than just &mut Tree<'a>.

I think the issue is that you have both &mut [RefCell; N] and &RefCell live at the same time. This aliasing is before any UnsafeCell point, so this is (I think) invalid.

2 Likes

By the way, I came to this conclusion by observing you only used two instances of unsafe (one, now), so unsafe { &*p } must be what is at fault.

1 Like

The UB becomes clear if you write the call to alloc in the desugared way:

fn main() {
    let mut t = Tree::new();
    
    let a = Tree::alloc(&mut t);
    let b = Tree::alloc(&mut t); // Boom! UB!
    
    drop(a);
    drop(b);
}

In order to perform the second call, you must create a &mut t. This is a mutable reference to the entire Tree, thus it aliases with any immutable reference into that tree, including anything stored in the arena which is a field of Tree.

Basically the issue is that you have an (immutable) borrow of the tree without the tree being borrowed.

4 Likes

Thank you, this makes the issue very clear!

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.