Stacked borrows Initiative

[uselessgoddess]

Now the experimental miri stacked borrows consider this as Undefined Behavior

error: Undefined Behavior: not granting access to tag <83023706> because incompatible item [Unique for <83025302>] is protected by call 27318525
   --> /home/runner/.rustup/toolchains/nightly-2022-07-29-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/non_null.rs:432:18
    |
432 |         unsafe { &mut *self.as_ptr() }
    |                  ^^^^^^^^^^^^^^^^^^^ not granting access to tag <83023706> because incompatible item [Unique for <83025302>] is protected by call 27318525
    |
    = 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: <83023706> was created by a retag at offsets [0x0..0x4000000]
   --> /home/runner/work/doublets-rs/doublets-rs/doublets/src/mem/unit/store.rs:85:19
    |
85  |         let mem = self.mem.alloc(capacity)?.leak();
    |                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
help: <83023706> was protected due to <83025299> which was created here
   --> /home/runner/work/doublets-rs/doublets-rs/doublets/src/mem/unit/store.rs:158:29
    |
158 |         self.sources.attach(&mut *root, index)
    |                             ^^^^^^^^^^

I find it very difficult to thread safety when multiple mutable pointers are stored in different places. I recommend using Yoda notation in regard to pointer storing.

# instead of 
struct DoubletsTree {
    # ha-ha i own this data
    ptr: Pointer*

    fn method(link: T) {
        # touch `ptr`
    }
}

# i recommend use 
struct DoubletsTree {
    # where is my data :(

    fn method(i_m_here: Pointer*, link: T) {
        # touch ptr
    }
}

This works well with stacked borrows:

#! before

# borrow data[x..y]:2
self.touch_first_tree(leak -> root_of_tree, link)
# borrow data[z..w]:3 
self.touch_second_tree(leak -> root_of_tree, link)
# [x..y] and [z..w] overlapping :(

#! after
data = self.get_data(...) # -- borrow data:1

# borrow data[x..y]:2 (not borrow self)
Tree::touch_first_tree(data, root_of_tree, link)
# unborrow data[z..w]:2

# borrow data[z..w]:2 (not borrow self)
Tree::touch_second_tree(data, root_of_tree, link)
# unborrow data[z..w]:2

# unborrow data:1 :)

[uselessgoddess]

To implement it, we need:

• [ ] Fix Szb trait from trees-rs to remove self parameter from all methods. Add explicit data argument (currently &mut [T])
• [ ] Remove all data fields from Szb trait implementors from doublets
• [ ] Rework all Store's functional to use new trees.

[Konard]

At the moment our tree implementations do not support thread safety. Can you make a benchmark of this proposal? Does it give any improvement in speed by itself?

[uselessgoddess]

Any code in Rust is always thread-safe, otherwise it's UB. Also, intentional violation of Stacked Borrows is also UB.

This code is works, but actually it's UB (later)

let mut data = 10;
let ref1 = &mut data;
let ref2 = ref1 as *mut _;
unsafe {
    *ref1 += 1;
    *ref2 += 2;
}

error: Undefined Behavior: attempting a read access using <untagged> at alloc2284[0x0], but that tag does not exist in the borrow stack for this location
 --> src\main.rs:8:9
  |
8 |         *ref2 += 2;
  |         ^^^^^^^^^^
  |         |
  |
4 |     let ref2 = ref1 as *mut _;
  |                ^^^^
help: tag was later invalidated at offsets [0x0..0x4]
 --> src\main.rs:7:9
  |
7 |         *ref1 += 1;
  |         ^^^^^^^^^^
  = note: inside `main` at src\main.rs:8:9

Since the compiler uses two rules for optimization:

• cannot borrow X as mutable more than once at a time
• cannot borrow X as mutable because it is also borrowed as immutable

[uselessgoddess]

Does it give any improvement in speed by itself?

I can only promise compiler optimizations and no UB

[Konard]

If Rust forces us to be not UB here, we should try to make code better.

[uselessgoddess]

It is my initiative, but it will help us to make the code better and without possible UB

[uselessgoddess]

Why is bad? Try to write this code It's actually the valid code, but the compiler isn't that smart:

let mut data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let monitor = &data[..5];
data[..5].copy_from_slice(&[10, 9, 8, 7, 6]);
println!("hey, i immutable: {monitor:?}");
println!("{data:?}");

error[E0502]: cannot borrow `data` as mutable because it is also borrowed as immutable
 --> src\main.rs:5:10
  |
4 |     let monitor = &data[..5];
  |                    ---- immutable borrow occurs here
5 |     &mut data[..5].copy_from_slice(&[10, 9, 8, 7, 6]);
  |          ^^^^ mutable borrow occurs here
6 |
7 |     println!("hey, i immutable: {monitor:?}");
  |                                  ------- immutable borrow later used here

Ok, unsafe time:

let mut data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let monitor = unsafe { from_raw_parts(data.as_ptr(), data.len()).get_unchecked(..5) };
data[..5].copy_from_slice(&[10, 9, 8, 7, 6]);
println!("hey, i immutable: {monitor:?}");
println!("{data:?}");

It works:

hey, i immutable: [10, 9, 8, 7, 6]
[10, 9, 8, 7, 6, 6, 7, 8, 9, 10]

But miri...

     |
2371 | fmt_refs! { Debug, Display, Octal, Binary, LowerHex, UpperHex, LowerExp, UpperExp }
     | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
     | |
     | trying to reborrow from <4390> for SharedReadOnly permission at alloc2110[0x0], but that tag does not exist in the borrow stack for this location
     | this error occurs as part of a reborrow at alloc2110[0x0..0x14]
     |

Hm. println! hinders us. Remove it:

let mut data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let monitor = unsafe { from_raw_parts(data.as_ptr(), data.len()).get_unchecked(..5) };
data[..5].copy_from_slice(&[10, 9, 8, 7, 6]);
let _ = monitor;

error: Undefined Behavior: trying to reborrow from <4390> for SharedReadOnly permission at alloc2102[0x0], but that tag does not exist in the borrow stack for this location
 --> src\main.rs:9:19
  |
9 |     let monitor = monitor;
  |                   ^^^^^^^
  |                   |
  |                   trying to reborrow from <4390> for SharedReadOnly permission at alloc2102[0x0], but that tag does not exist in the borrow stack for this location
  |                   this error occurs as part of a reborrow at alloc2102[0x0..0x14]
  |

Why are you doing that? from_raw_parts(data.as_ptr(), data.len()) borrow whole data. Miri think that we borrow data[0..10]. Let's rewrite the code:

let mut data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let monitor = unsafe { from_raw_parts(data.as_ptr().add(5), data.len() - 5) };
data[..5].copy_from_slice(&[10, 9, 8, 7, 6]);

Nice. Miri silent. I also recommend using a safe rust:

let mut data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let (monitor, hot) = data.split_at_mut(5);
hot.copy_from_slice(&[10, 9, 8, 7, 6]);

[uselessgoddess]

It's not exactly dangerous, but possible has potential bugs

[uselessgoddess]

Develompent in stacked-borrows-initiative branch