Unsound use after free using only safe code (and this crate)

Note, to pass some checks (cause I didn't feel like understanding it all) I turned off debug assertions for this example:

use std::hash::Hash;

use riddance::{
    id::{Id64, IdTrait},
    state::State,
    Registry,
};

struct MyId<T> {
    inner: Id64<T>,
    malicious: bool,
}
impl<T> Hash for MyId<T> {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.inner.hash(state);
    }
}
impl<T> Eq for MyId<T> {}
impl<T> PartialEq for MyId<T> {
    fn eq(&self, other: &Self) -> bool {
        self.inner == other.inner
    }
}
impl<T> Clone for MyId<T> {
    fn clone(&self) -> Self {
        *self
    }
}
impl<T> Copy for MyId<T> {}

impl<T> IdTrait for MyId<T> {
    type IndexBits = <Id64<T> as IdTrait>::IndexBits;
    type GenerationBits = <Id64<T> as IdTrait>::GenerationBits;

    fn new(index: usize, generation: u32) -> Self {
        Self {
            inner: Id64::new(index, generation),
            malicious: index == 19 && generation == 1,
        }
    }

    fn index(&self) -> usize {
        if self.malicious {
            return 1;
        }
        self.inner.index()
    }

    fn generation(&self) -> u32 {
        self.inner.generation()
    }

    fn matching_state(&self) -> riddance::state::State<Self::GenerationBits> {
        if self.malicious {
            return State::new(2);
        }
        self.inner.matching_state()
    }

    fn null() -> Self {
        Self {
            inner: Id64::null(),
            malicious: false,
        }
    }

    fn is_null(&self) -> bool {
        false
    }
}

fn main() {
    let mut r = Registry::<Vec<u32>, MyId<i64>>::with_id_type();
    let mut adds = Vec::new();
    for i in 0..20 {
        adds.push(r.insert(vec![1, 2, 3]));
    }
    for x in adds {
        r.remove(x);
    }

    let id = r.insert(vec![2, 3, 4]);
    println!("{:?}", r.get(id));
}

try: cargo +nightly miri test to get a use after free:

What this does is it allocates and frees some elements, and after 20 it triggers the "malicious" path in the index which returns a weird ID (1). This is a super contrived example (took me a bit to get it to work haha) but essentially what it means is that there's a safety contract to implementing IdTrait, and it should probably be an unsafe trait to implement. That'd mean that all your implementations of IdTrait are sound, and all users' implementations are sound provided that they implement IdTrait correctly, which involves not doing something stupid like I did here :P

oconnor663 / riddance

Unsound use after free using only safe code (and this crate) #6