MIRI error, with `intrusive_collections` crate

help
1

I am not good at English. Sorry if there are any funny expressions.

MIRI reports an error in the code where it uses RBTree from intrusive_collections crate.
If I use the standard BTreeMap instead of RBTree, it doesn't cause an error.
I'm confused because it doesn't seem that whether it's intrusive or not affects error occurrence.
(I usually can't handle unsafe properly...:sob:)

Please give me some advice.

Code

This code has been minimized for error reproduction.
Datas are generated and dropped immediately.
So, it's not actually doing meaningful work.

/src/lib.rs

#![allow(dead_code)]
mod map_adapter;
mod test_rbtree;
mod test_btree_map;

/src/test_rbtree.rs

use intrusive_collections::{*, rbtree::*};
use crate::map_adapter::*;

#[test]
fn test_rbtree() {
    let mut map = RBTree::new(MapAdapter::new());
    drop(MyType::new(&mut map));
}

struct MyType<'a> {
    iter: Option<Iter<'a, MapAdapter>>,
    map: *mut RBTree<MapAdapter>,
}

impl<'a> MyType<'a> {
    pub fn new(map: &'a mut RBTree<MapAdapter>) -> Self {
        Self {
            map: map as *mut _,
            iter: Some(map.iter()),
        }
    }
}

impl Drop for MyType<'_> {
    fn drop(&mut self) {
        self.iter.take();
        let _ = unsafe { &mut *self.map }; // ❌ MIRI Error!
    }
}

/src/test_btree_map.rs

use std::collections::btree_map::{BTreeMap, Iter};

#[test]
fn test1() {
    let mut map = BTreeMap::<usize, i32>::new();
    drop(MyType::new(&mut map));
}

struct MyType<'a> {
    iter: Option<Iter<'a, usize, i32>>,
    map: *mut BTreeMap<usize, i32>,
}

impl<'a> MyType<'a> {
    pub fn new(map: &'a mut BTreeMap<usize, i32>) -> Self {
        Self {
            map: map as *mut _,
            iter: Some(map.iter()),
        }
    }
}

impl Drop for MyType<'_> {
    fn drop(&mut self) {
        self.iter.take();
        let _ = unsafe { &mut *self.map };  // 🤔 No MIRI Error!
    }
}

/src/map_adapter.rs

use intrusive_collections::*;

intrusive_adapter!(
    pub MapAdapter = Box<Node>: Node {
        link: RBTreeLink
    }
);

impl<'a> KeyAdapter<'a> for MapAdapter {
    type Key = usize;
    fn get_key(&self, x: &'a Node) -> usize {
        *x.key()
    }
}

pub struct Node {
    key: usize,
    _val: i32,
    pub(crate) link: RBTreeLink,
}

impl Node {
    pub fn key(&self) -> &usize {
        &self.key
    }
}

Error excerpt

test test_btree_map::test1 ... ok
test test_rbtree::test_rbtree ... error: Undefined Behavior: not granting access to tag <168217> because that would remove [SharedReadOnly for <168240>] which is strongly protected
  --> src\test_rbtree.rs:27:26
   |
27 |         let _ = unsafe { &mut *self.map };
   |                          ^^^^^^^^^^^^^^ Undefined Behavior occurred here
   |
   = help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows rules it violated are still experimental
   = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: <168217> was created by a SharedReadWrite retag at offsets [0x0..0x8]
  --> src\test_rbtree.rs:18:18
   |
18 |             map: map as *mut _,
   |                  ^^^
help: <168240> is this argument
  --> src\test_rbtree.rs:7:5
   |
 7 |     drop(MyType::new(&mut map));
2

What is the purpose of this? There's nothing to drop for a reference -- or were you really intending to do something more with that reference in your own drop?

2 Likes
3

I didn't run it, so this is just a guess based on the error and experience.

You should create the *mut _, and then create the iterator through the *mut _. In general when working with raw pointers, aspire to have one raw pointer which all accesses can map back to, until you are out of raw pointer land.

1 Like
4

In my actual code, I was deleting the entry from the map after this.

5

MIRI still throws errors, but is this kind of code better for now?
(My apologies if I've misunderstood).

impl<'a> MyType<'a> {
    pub fn new(map: &'a mut RBTree<MapAdapter>) -> Self {
        let map_ptr = map as *mut _;
        Self {
            map: map_ptr,
            iter: Some(unsafe { &*map_ptr }.iter()),
        }
    }
6

There may be other problems, but that is what I meant.

1 Like
7

I'll make this a habit in my future coding. Thanks. (Come to think of it, I was taught before that it's better not to mix pointers and references... but I've finally learned this time.)