How to share &mut via unsafe code if uniqueness is guaranteed otherwise

help
1

I would like to provide mutable "views" to disjunct parts of a large struct. I am guaranteeing through static or dynamic checks that my views will never access the same data. Below is a toy example.

What is the proper way to "multiplex" the &mut? I guess that my current approach below is not the right way to do this. Is it maybe even UB? Note that the split methods guarantees that mutable references inside the views are only ever accessing disjunct parts of Data and are not used to do any mutations or reads which conflict with each other.

#[derive(Debug)]
struct Data {
    x: i32,
    y: i32,
}

impl Data {
    pub fn split<'a>(&'a mut self) -> (View<'a>, View<'a>) {
        unsafe {(
            View { bck: &mut *(self as *mut Data), kind: ViewKind::X },
            View { bck: &mut *(self as *mut Data), kind: ViewKind::Y },
        )}
    }
}

struct View<'a> {
    bck: &'a mut Data,
    kind: ViewKind,
}

enum ViewKind { X, Y }

impl View<'_> {
    pub fn write(&mut self, v: i32) {
        match self.kind {
            ViewKind::X => self.bck.x = v,
            ViewKind::Y => self.bck.y = v,
        }
    }
}

fn main() {
    let mut bck = Data { x: 0, y: 0 };
    let (mut vx, mut vy) = bck.split();
    vx.write(2);
    vy.write(4);
    println!("{:?}", bck);
}
2

Yes, and that’s fortunately very easy to confirm. Just paste your code into the playground and click "Tools"->"Miri":

   Compiling playground v0.0.1 (/playground)
    Finished dev [unoptimized + debuginfo] target(s) in 0.31s
     Running `/playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/cargo-miri runner target/miri/x86_64-unknown-linux-gnu/debug/playground`
error: Undefined Behavior: trying to retag from <2715> for Unique permission at alloc1453[0x0], but that tag does not exist in the borrow stack for this location
  --> src/main.rs:34:10
   |
34 |     let (mut vx, mut vy) = bck.split();
   |          ^^^^^^
   |          |
   |          trying to retag from <2715> for Unique permission at alloc1453[0x0], but that tag does not exist in the borrow stack for this location
   |          this error occurs as part of retag at alloc1453[0x0..0x8]
   |
   = 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: <2715> was created by a Unique retag at offsets [0x0..0x8]
  --> src/main.rs:10:13
   |
10 |             View { bck: &mut *(self as *mut Data), kind: ViewKind::X },
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
help: <2715> was later invalidated at offsets [0x0..0x8] by a Unique retag
  --> src/main.rs:11:25
   |
11 |             View { bck: &mut *(self as *mut Data), kind: ViewKind::Y },
   |                         ^^^^^^^^^^^^^^^^^^^^^^^^^
   = note: BACKTRACE (of the first span):
   = note: inside `main` at src/main.rs:34:10: 34:16

note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace

error: aborting due to previous error
2 Likes
3

The relevant rule for &mut T is not that you must never access the same data at the same time trough different mutable references, but you must never have access to the same data at the same time through different mutable references.

The way to save this could be to have View contain a raw *mut Data pointer instead:

use std::marker::PhantomData;

#[derive(Debug)]
struct Data {
    x: i32,
    y: i32,
}

impl Data {
    pub fn split<'a>(&'a mut self) -> (View<'a>, View<'a>) {
        let bck: *mut Data = self;
        (
            View { bck, kind: ViewKind::X, _marker: PhantomData },
            View { bck, kind: ViewKind::Y, _marker: PhantomData },
        )
    }
}

struct View<'a> {
    bck: *mut Data,
    kind: ViewKind,
    _marker: PhantomData<&'a mut Data>,
    // marker field, so the lifetime 'a gets used
}

enum ViewKind { X, Y }

impl View<'_> {
    pub fn write(&mut self, v: i32) {
        unsafe {
            match self.kind {
                ViewKind::X => (*self.bck).x = v,
                ViewKind::Y => (*self.bck).y = v,
            }
        }
    }
}

fn main() {
    let mut bck = Data { x: 0, y: 0 };
    let (mut vx, mut vy) = bck.split();
    vx.write(2);
    vy.write(4);
    println!("{:?}", bck);
}

Rust Playground

This approach will have the compiler possibly put an unnecessarily strict !Sync and !Send bound on your type. If your logic that ensures disjoint access is thread-safe (which in this toy example it is), you could further life those bounds manually if needed.

4 Likes
4

If your use case is simple enough to segment your data structure, just do that without unsafe.

If it's not, ... @steffahn was faster, but basically create one *mut at the top (from a &mut that covers everything you need) and then never leave the world of raw pointers until the lifetime expires.

2 Likes
5

You don't need any unsafe for this.

1 Like
6

The toy example might have been a bit too simple.. Unfortunately in my use case the views are more complicated and I cannot do that simple field-based split.

7

Is "raw pointer" the only/preferred option or are there other methods?

8

One possible disadvantage of this approach is that now all view operations have to be unsafe although the heart of the unsafe code is the split method which multiplexes the &mut and needs to guarantee that the views it generates are disjunct.

9

I disagree. This is an advantage, not a disadvantage. If the split function does not create Views that inherently have only disjoint access to begin with, then the assessment that every (implementation of a) view operation is inherently unsafe is accurate, as it must ensure the disjoint access pattern manually, e.g. in this case by interpreting the meaning of the ViewKind data correctly and strictly following it, in order to avoid undefined behavior.

3 Likes
10

The safe demonstrations are sometimes an option. More complicated "view structs" are sometimes another safe option. Cells are sometimes an option. Refactoring your data structures to explicitly accommodate shared mutation (Mutex, RefCell, ...) is sometims an option.

If there's not a way to construct it in safe code, &mut usually isn't an option because of the aforementioned constraints. [1]

  1. I'm sure there are exceptions but they'd be situation specific. ↩︎

4 Likes
11

Then please show the actual use-case that you need this for.

1 Like
12

Note that there are no contradiction between what @steffahn said and what @danvil said: yes, it's obvious disadvantage that you have to mark all view operations unsafe, but if you can not guarantee that your view windows are disjoint then they are inheritanly unsafe and should be marked as such. And if they are marked as such then obviously use of raw pointers is not a problem.

Shared mutability is only achievable via pointers. That's what Rustonomicon says about that:

  • Transmuting an & to &mut is Undefined Behavior. While certain usages may appear safe, note that the Rust optimizer is free to assume that a shared reference won't change through its lifetime and thus such transmutation will run afoul of those assumptions. So:
    • Transmuting an & to &mut is always Undefined Behavior.
    • No you can't do it.
    • No you're not special.
1 Like
13

I tried a more realistic "minimal" example below. This uses the "*mut pointer" approach. Note that so far I could only make it work by making FilterView cloneable, which really is not a good thing.

trait Filter {
    // Self and Complement must be disjunct, i.e.
    //   self.allowed(x) => !complement.allowed(x)
    type Complement;

    // checks if element passes filter
    fn allowed(&self, x: usize) -> bool;

    // creates the complement of the filter
    fn complement(&self) -> Self::Complement;
}

// Only indices which are explicitly allowed pass
#[derive(Clone)]
struct RequireListFilter {
    indices: Vec<usize>,
}

impl Filter for RequireListFilter {
    type Complement = ForbidListFilter;
    fn allowed(&self, x: usize) -> bool {
        self.indices.contains(&x)
    }
    fn complement(&self) -> Self::Complement {
        ForbidListFilter { indices: self.indices.clone() } // TODO avoid clone
    }
}

// All indices which are not explicitly forbidden pass
#[derive(Clone)]
struct ForbidListFilter {
    indices: Vec<usize>,
}

impl Filter for ForbidListFilter {
    type Complement = RequireListFilter;
    fn allowed(&self, x: usize) -> bool {
        !self.indices.contains(&x)
    }
    fn complement(&self) -> Self::Complement {
        RequireListFilter { indices: self.indices.clone() } // TODO avoid clone
    }
}

// Only event indices pass
#[derive(Clone)]
struct EvenFilter;

impl Filter for EvenFilter {
    type Complement = OddFilter;
    fn allowed(&self, x: usize) -> bool { x % 2 == 0 }
    fn complement(&self) -> Self::Complement {
        OddFilter
    }
}

// Only odd indices pass
#[derive(Clone)]
struct OddFilter;

impl Filter for OddFilter {
    type Complement = EvenFilter;
    fn allowed(&self, x: usize) -> bool { x % 2 == 1 }
    fn complement(&self) -> Self::Complement {
        EvenFilter
    }
}

trait View {
    fn try_get(&self, x: usize) -> Option<&f32>;
    fn try_get_mut(&self, x: usize) -> Option<&mut f32>;
    fn split<F: Filter>(self, filter: F) -> (FilterView<Self, F>, FilterView<Self, F::Complement>)
        where Self: Clone;

    fn get(&self, x: usize) -> &f32 { self.try_get(x).unwrap() }
    fn get_mut(&self, x: usize) -> &mut f32 { self.try_get_mut(x).unwrap() }
}

#[derive(Clone)]  // FIXME should not be Clone
struct FilterView<B, F> {
    base: B,
    filter: F,
}

impl<B: View, F: Filter> View for FilterView<B, F> {
    fn try_get(&self, x: usize) -> Option<&f32> {
        if !self.filter.allowed(x) {
            None
        } else {
            self.base.try_get(x)
        }
    }

    fn try_get_mut(&self, x: usize) -> Option<&mut f32> {
        if !self.filter.allowed(x) {
            None
        } else {
            self.base.try_get_mut(x)
        }
    }

    fn split<F2: Filter>(self, filter: F2) -> (
        FilterView<Self, F2>,
        FilterView<Self, F2::Complement>
    )
        where Self: Clone
    {
        let complement = filter.complement();
        (
            FilterView {
                base: self.clone(),
                filter,
            },
            FilterView {
                base: self,
                filter: complement,
            },
        )
    }
}

#[derive(Clone)]  // FIXME should not be Clone
struct UnsafeDataView<'b> {
    ptr: *mut Data,
    marker: core::marker::PhantomData<&'b mut Data>,
}

impl<'d> View for UnsafeDataView<'d> {
    fn try_get(&self, x: usize) -> Option<&f32> {
        unsafe { (*self.ptr).data.get(x) }
    }

    fn try_get_mut(&self, x: usize) -> Option<&mut f32> {
        if x < unsafe { (*self.ptr).data.len() } {
            unsafe { (*self.ptr).data.get_mut(x) }
        } else {
            None
        }
    }

    fn split<F2: Filter>(self, filter: F2) -> (
        FilterView<Self, F2>,
        FilterView<Self, F2::Complement>
    ) {
        let complement = filter.complement();
        (
            FilterView {
                base: self.clone(),
                filter,
            },
            FilterView {
                base: self,
                filter: complement,
            },
        )
    }
}

struct Data {
    data: Vec<f32>,
}

impl Data {
    // Note: Unlike `View` we cannot use `self` to prevent multiple splits as we
    // cannot consume Data. Instead we use &mut self.
    fn split<'d, F: Filter>(&'d mut self, filter: F) -> (
        FilterView<UnsafeDataView<'d>, F>,
        FilterView<UnsafeDataView<'d>, F::Complement>
    ) {
        let ptr = self as *mut Data;
        let complement = filter.complement();
        (
            FilterView {
                base: UnsafeDataView { ptr, marker: core::marker::PhantomData },
                filter,
            },
            FilterView {
                base: UnsafeDataView { ptr, marker: core::marker::PhantomData },
                filter: complement,
            },
        )
    }
}

fn main() {
    let mut data = Data { data: vec![1.0,2.0,3.0,4.0,5.0,6.0,7.0] };
    let (vl, vr) = data.split(EvenFilter);
    let (vrl, vrr) = vr.split(ForbidListFilter { indices: vec![3] });
    
    // data.data[3] = 0.0; -- not allowed as views capture data

    println!("Before:");
    for i in 0..10 {
        println!("{i} | {:<10}| {:<10}| {:<10}",
            format!("{:?}", vl.try_get(i)),
            format!("{:?}", vrl.try_get(i)),
            format!("{:?}", vrr.try_get(i)));
    }
    
    *vl.get_mut(2) = 0.1;
    *vrl.get_mut(1) = 0.2;
    *vrr.get_mut(3) = 0.3;

    println!("After:");
    for i in 0..10 {
        println!("{i} | {:<10}| {:<10}| {:<10}",
            format!("{:?}", vl.try_get(i)),
            format!("{:?}", vrl.try_get(i)),
            format!("{:?}", vrr.try_get(i)));
    }

}
14

The fact that you're trying to stack multiple FilterViews on top of each other is going to make this very hard.

15

Yes, the goal is to be able to build non-trivial views while guaranteeing that all views access disjunct parts of the underlying data. This allows the user to have mutable access to sub-sections of the data concurrently without violating Rusts ownership rules.

16

This is arbitrary disjunction at runtime, which I'm pretty sure is not possible without unsafe. Furthermore, your example is unsound unless Filter is guaranteed to not have any other implementations:

#[derive(Clone)]
struct BadFilter;

impl Filter for BadFilter {
    type Complement = Self;
    fn allowed(&self, x: usize) -> bool {
        // 1. This has to be forbidden. I choose SystemTime
        // because it needs no external dependencies,
        // but any non-pure function will do.
        SystemTime::now()
            .duration_since(SystemTime::UNIX_EPOCH)
            .unwrap_or(false)
    }
    fn complement(&self) -> Self::Complement {
        self // 2. This also has to be forbidden.
    }
}

At least you could fix the unsoundness by

  1. memoizing allowed, and
  2. using ComplementFilter<F: Filter> instead of the Complement associated type.
17

By that you mean any implementations which violate that the sets of inputs allowed by Self and Complement are not disjunct?

All filters I have so far, like RequireListFilter and ForbidListFilter, do that by allowing values based on some kind of immutable cache or "hermetic" function.

Could you explain more what you mean by that? I put Complement as an associate type because the implementer of a specific filter would know best what the appropriate choice for the complement is.

18

You can't control what an implementation you didn't write does, so for the code to be sound without instead adding memoization and guaranteed complements, you have to somehow prohibit other crates from writing implementations of Filter (by making the trait private, or “sealed” if it is public).

Like Reverse in std::cmp - Rust — instead of permitting or requiring each filter to implement a complement, you write a generic wrapper that wraps any Filter and negates the answer.

2 Likes
19

I think you didn't say what you meant with the double negation. Anyway, the proposed fix is here: Playground(edit: fixed split being &self)

There is the third option of making Filter an unsafe trait. However, having too much unsafe can be detrimental to robustness. Whether this option makes sense depends on your goals.

20

For a filter to be properly implemented it must guarantee that the set of inputs allowed by Self and Self::Complement are disjunct. If an implementation of a filter violates this constraint then multiple mutable references to the same data field could be handed out. I am not sure I understood why this is "unsound". Or are you saying that if an implementation violates this constraint, then it is unsound?