Isn't indirect mutable aliasing also undefined behavior?

[lokegustafsson]

Consider the following program

use elsa::FrozenMap;
use std::cell::UnsafeCell;

fn main() {
    with_elsa();
    manual();
}

fn with_elsa() {
    // Within the second `insert` call, we are at the same time holding
    // - `&usize`
    // - `&mut HashMap<u8, Box<usize>>` (when calling entry() in insert impl)
    // Seems like UB?
    let v: FrozenMap<u8, Box<usize>> = Default::default();
    let a = v.insert(1, Box::new(1));
    let b = v.insert(2, Box::new(2));
    println!("{a} {b}");
}

fn manual() {
    // This is basically what is happening inside FrozenMap.
    let target: UnsafeCell<Box<u32>> = UnsafeCell::new(Box::new(1));
    let x = get_x(&target);
    let mut y = get_y(&target);
    // `x` and `y` are now (indirectly in the case of `y`) aliasing!
    // And `y` is mutable. Seems like UB?
    println!("{x} {y}");
    // Although `y` is short lived and the Box is never dereferenced.
    // Maybe this saves us from UB?
    let _ = y;
    let _ = x;
}

fn get_x<'a>(target: &'a UnsafeCell<Box<u32>>) -> &'a u32 {
    unsafe { &**target.get() }
}

fn get_y<'a>(target: &'a UnsafeCell<Box<u32>>) -> &'a mut Box<u32> {
    unsafe { &mut *target.get() }
}

This is totally fine according to miri but to my understanding of the aliasing rules it seems like basically every program using elsa has UB.

This could be avoided by using an inner hashmap that has a *mut self parameter rather than &mut self for its member methods (for example map.entry(key)). But I guess this is purely theoretical UB anyway, not causing miscompilations (or failing miri) in practice.

EDIT: I guess UnsafeCell<HashMap<K, UnsafeCell<V>>> could work, but maybe that has performance implications 🤷

[Manishearth]

No, the aliasing rules do not travel through indirection. In other words, these two:

    // - `&usize`
    // - `&mut HashMap<u8, Box<usize>>` (when calling entry() in insert impl)

are safe to hold concurrently, as long as you never use the hashmap to materialize an &mut usize.

There are some discussions about this:

• Aliasing rules for Vec<T> and other standard containers rust-lang/unsafe-code-guidelines#262
• What are the uniqueness guarantees of Box and Vec? rust-lang/unsafe-code-guidelines#326

We were recently talking about something similar in thomcc/rust-typed-arena#62; generally UCG doesn't want to make this kind of thing happen all too often.

So I do think that this is sound.

That said, I'm considering hiding the internal representation anyway, in which case wrapping in UnsafeCell might be a fine way to harden it.

Thanks for reporting though, examples like this are useful to have!

[RalfJung]

the aliasing rules do not travel through indirection

FWIW, that is not something we have T-lang FCP on, let alone an RFC. But it is the general direction I currently prefer, and T-opsem seems to be of the same mind.

[Manishearth]

Yeah, I'm operating in the realm of "the rules that are likely to exist" not "the rules that actually exist" because enough is unspecified that it is not possible to currently write much definitely-sound unsafe code under the "rules that actually exist".

[RalfJung]

Not the kind of code you are writing, no. ;)