Unsound Unsafe Implementation for BlockPtr and BranchPtr

[MinisculeGirraffe]

A NonNull stores a *mut T. By creating a mutable pointer from a non-mutable reference, any mutations through that pointer would be UB.

In BlockPtr and BranchPtr a mutable pointer is created from an immutable reference.

y-crdt/yrs/src/block.rs

Lines 524 to 529 in dac997a

	impl<'a> From<&'a Box<Block>> for BlockPtr {
	fn from(block: &'a Box<Block>) -> Self {
	BlockPtr(unsafe { NonNull::new_unchecked(block.as_ref() as *const Block as *mut Block) })
	}
	}

y-crdt/yrs/src/types/mod.rs

Lines 165 to 180 in dac997a

	impl<'a> From<&'a Box<Branch>> for BranchPtr {
	fn from(branch: &'a Box<Branch>) -> Self {
	let b: &Branch = &*branch;
	let ptr = unsafe { NonNull::new_unchecked(b as *const Branch as *mut Branch) };
	BranchPtr(ptr)
	}
	}
	impl<'a> From<&'a Branch> for BranchPtr {
	fn from(branch: &'a Branch) -> Self {
	let ptr = unsafe { NonNull::new_unchecked(branch as *const Branch as *mut Branch) };
	BranchPtr(ptr)
	}
	}

Running the tests through Miri confirm that a stacked borrow violation occurs from this.

BlockPtr:

test alt::test::merge_updates_compatibility_v1_2 ... error: Undefined Behavior: trying to retag from <413228> for Unique permission at alloc173031[0x0], but that tag only grants SharedReadOnly permission for this location
   --> /Users/daniel/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/core/src/ptr/non_null.rs:436:18
    |
436 |         unsafe { &mut *self.as_ptr() }
    |                  ^^^^^^^^^^^^^^^^^^^
    |                  |
    |                  trying to retag from <413228> for Unique permission at alloc173031[0x0], but that tag only grants SharedReadOnly permission for this location
    |                  this error occurs as part of retag at alloc173031[0x0..0xa8]
    |
    = 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: <413228> was created by a SharedReadOnly retag at offsets [0x0..0xa8]
   --> yrs/src/block.rs:526:50
    |
526 |         BlockPtr(unsafe { NonNull::new_unchecked(block.as_ref() as *const Block as *mut Block) })
    |                                                  ^^^^^^^^^^^^^^
    = note: BACKTRACE:
    = note: inside `std::ptr::NonNull::<block::Block>::as_mut::<'_>` at /Users/daniel/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/core/src/ptr/non_null.rs:436:18: 436:37
note: inside `<block::BlockPtr as std::ops::DerefMut>::deref_mut`
   --> yrs/src/block.rs:514:18
    |
514 |         unsafe { self.0.as_mut() }
    |                  ^^^^^^^^^^^^^^^
note: inside `block::BlockPtr::try_squash`
   --> yrs/src/block.rs:465:34
    |
465 |         match (self.deref_mut(), other.deref_mut()) {
    |                                  ^^^^^^^^^^^^^^^^^
note: inside `update::BlockCarrier::try_squash`
   --> yrs/src/update.rs:812:17
    |
812 |                 BlockPtr::from(a).try_squash(BlockPtr::from(b))
    |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `update::Update::merge_updates::<std::vec::Vec<update::Update>>`
   --> yrs/src/update.rs:627:41
    |
627 | ...                   if !curr_write_block.try_squash(&curr_block) {
    |                           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `alt::merge_updates_v1`
   --> yrs/src/alt.rs:14:8
    |
14  |     Ok(Update::merge_updates(merge).encode_v1())
    |        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `alt::test::merge_updates_compatibility_v1_2`
   --> yrs/src/alt.rs:95:22
    |
95  |         let actual = merge_updates_v1(&[a, b]).unwrap();
    |                      ^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside closure
   --> yrs/src/alt.rs:83:43
    |
82  |     #[test]
    |     ------- in this procedural macro expansion
83  |     fn merge_updates_compatibility_v1_2() {
    |                                           ^

BranchPtr:

test compatibility_tests::negative_zero_decoding_v2 ... error: Undefined Behavior: trying to retag from <1206487> for Unique permission at alloc563277[0x0], but that tag does not exist in the borrow stack for this location
   --> /Users/daniel/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/core/src/ptr/non_null.rs:436:18
    |
436 |         unsafe { &mut *self.as_ptr() }
    |                  ^^^^^^^^^^^^^^^^^^^
    |                  |
    |                  trying to retag from <1206487> for Unique permission at alloc563277[0x0], but that tag does not exist in the borrow stack for this location
    |                  this error occurs as part of retag at alloc563277[0x0..0x90]
    |
    = 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: <1206487> was created by a SharedReadWrite retag at offsets [0x0..0x90]
   --> yrs/src/types/mod.rs:160:19
    |
160 |         let ptr = NonNull::from(branch.as_mut());
    |                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
help: <1206487> was later invalidated at offsets [0x0..0x90] by a Unique retag
   --> yrs/src/store.rs:106:26
    |
106 |                 e.insert(branch);
    |                          ^^^^^^
    = note: BACKTRACE:
    = note: inside `std::ptr::NonNull::<types::Branch>::as_mut::<'_>` at /Users/daniel/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/core/src/ptr/non_null.rs:436:18: 436:37
note: inside `<types::BranchPtr as std::ops::DerefMut>::deref_mut`
   --> yrs/src/types/mod.rs:154:18
    |
154 |         unsafe { self.0.as_mut() }
    |                  ^^^^^^^^^^^^^^^
note: inside `doc::Doc::get_or_insert_map`
   --> yrs/src/doc.rs:144:9
    |
144 |         c.store = Some(self.store.weak_ref());
    |         ^^^^^^^
note: inside `compatibility_tests::negative_zero_decoding_v2`
   --> yrs/src/compatibility_tests.rs:385:16
    |
385 |     let root = doc.get_or_insert_map("root");
    |                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside closure
   --> yrs/src/compatibility_tests.rs:383:32
    |
382 | #[test]
    | ------- in this procedural macro expansion
383 | fn negative_zero_decoding_v2() {
    |                                ^
    = note: this error originates in the attribute macro `test` (in Nightly builds, run with -Z macro-backtrace for more info)

[MinisculeGirraffe]

I hacked around the code a bit, and was able to fix the BlockPtr stacked borrow violations by removing the impl From<&'a Box<Block>> and using a mutex some places where BlockPtr was being created from an immutable block reference.

All the tests passed, but in some of the benches it's a -25% performance regression. Assuming that there's probably a better way to solve it without having to use locks. However i'm not an advanced enough Rust Programmer to figure out how that would work.

I can send a PR over of my changes, but it's probably not good enough to merge.

[Horusiath]

@MinisculeGirraffe Mutexes are no-go in the core lib, since it's used in variety of different contexts eg. WASM, rust, async rust with M:N green threads, whatever threading model the language binding (Python, Ruby etc.) provides.

Currently we didn't have any known undefined behaviour bugs caused by ref-mut block casting. In the future we may want to adopt different way of working with blocks with more respect regarding borrow checker rules, but currently priority was compatibility with Yjs.