Zerovec DST construction fails miri (Zerovec should use pointer metadata APIs)

[DarthB]

Miri is complaining on CaseMapper::fold_string. It says that it is an experimental rule; nonetheless, this ruins confidence.

• Did someone use CaseMapper::fold_string() on many data points and has therefore more confidence?
• As far as I understand this is related to zerocopy with zerovec maybe there have been similar issues?

How to reproduce

When running the code below with icu 2.0.0 with miri: cargo +nightly miri run. You'll get the attached error description.

use icu::casemap::CaseMapper;
fn main() {
    let cm = CaseMapper::new();
    let result = cm.fold_string("Test");
    println!("{}", result);
}

error: Undefined Behavior: trying to retag from <7066> for SharedReadOnly permission at alloc735[0x31b], but that tag does not exist in the borrow stack for this location
  --> /Users/darthb/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/icu_casemap-2.0.0/src/provider/exceptions.rs:89:1
   |
89 | #[zerovec::make_varule(ExceptionULE)]
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   | |
   | trying to retag from <7066> for SharedReadOnly permission at alloc735[0x31b], but that tag does not exist in the borrow stack for this location
   | this error occurs as part of retag at alloc735[0x318..0x31d]
   |
   = 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: <7066> was created by a SharedReadOnly retag at offsets [0x318..0x31b]
  --> src/main.rs:11:18
   |
11 |     let result = cm.fold_string("Test");
   |                  ^^^^^^^^^^^^^^^^^^^^^^
   = note: BACKTRACE (of the first span):
   = note: inside `<icu::icu_casemap::provider::exceptions::ExceptionULE as zerovec::ule::VarULE>::from_bytes_unchecked` at /Users/darthb/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/icu_casemap-2.0.0/src/provider/exceptions.rs:89:1: 89:38
   = note: inside `zerovec::varzerovec::components::VarZeroVecComponents::<'_, icu::icu_casemap::provider::exceptions::ExceptionULE, zerovec::varzerovec::components::Index16>::get_unchecked` at /Users/darthb/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/zerovec-0.11.2/src/varzerovec/components.rs:394:9: 394:46
   = note: inside `zerovec::varzerovec::components::VarZeroVecComponents::<'_, icu::icu_casemap::provider::exceptions::ExceptionULE, zerovec::varzerovec::components::Index16>::get` at /Users/darthb/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/zerovec-0.11.2/src/varzerovec/components.rs:383:23: 383:46
   = note: inside `zerovec::varzerovec::slice::VarZeroSlice::<icu::icu_casemap::provider::exceptions::ExceptionULE>::get` at /Users/darthb/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/zerovec-0.11.2/src/varzerovec/slice.rs:202:9: 202:38
   = note: inside `icu::icu_casemap::provider::exceptions::CaseMapExceptions::<'_>::get` at /Users/darthb/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/icu_casemap-2.0.0/src/provider/exceptions.rs:53:25: 53:56
   = note: inside `icu::icu_casemap::internals::<impl icu::icu_casemap::provider::CaseMap<'_>>::full_helper::<false, writeable::to_string_or_borrow::SliceOrString<'_>>` at /Users/darthb/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/icu_casemap-2.0.0/src/internals.rs:343:29: 343:53
   = note: inside `<icu::icu_casemap::internals::FullCaseWriteable<'_, '_, false> as writeable::Writeable>::write_to::<writeable::to_string_or_borrow::SliceOrString<'_>>` at /Users/darthb/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/icu_casemap-2.0.0/src/internals.rs:71:13: 72:92
   = note: inside `writeable::to_string_or_borrow::to_string_or_borrow::<icu::icu_casemap::internals::FullCaseWriteable<'_, '_, false>>` at /Users/darthb/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/writeable-0.6.1/src/to_string_or_borrow.rs:208:13: 208:42
   = note: inside `icu::icu_casemap::CaseMapperBorrowed::<'_>::fold_string` at /Users/darthb/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/icu_casemap-2.0.0/src/casemapper.rs:401:9: 401:72
note: inside `main`
  --> src/main.rs:11:18
   |
11 |     let result = cm.fold_string("Test");
   |                  ^^^^^^^^^^^^^^^^^^^^^^
   = note: this error originates in the attribute macro `zerovec::make_varule` (in Nightly builds, run with -Z macro-backtrace for more info)

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

error: aborting due to 1 previous error

[sffc]

Old open issue about catching miri warnings in CI: #1259

[sffc]

My guess: <T as VarULE>::from_bytes_unchecked usually involves core::slice::from_raw_parts and some pointer casting*, which is documented as a limitation on Stacked Borrows.

* This may be improved if Rust adds better utility around constructing DST references: rust-lang/rust#81513

[Manishearth]

Yes, that's most likely it.

We also fail miri here:

icu4x/utils/zerovec/src/ule/encode.rs

Line 104 in 66769be

let ptr: *mut T = T::from_bytes_unchecked(&boxed) as *const T as *mut T;

which is in similar DST-construction code, where we call from_bytes_unchecked to eventually make an owned Box<T>, which is a bit more clearly illegal in the stacked borrows model. There aren't really any better ways to do this, and this would have to be fixed for stacked/tree borrows to stabilize.

I should open a thread upstream to ensure this gets tracked.

[Manishearth]

Here's a minimal example:

#[repr(C, packed)]
struct MyDst(u8, [u8]);

#[inline]
unsafe fn from_bytes_unchecked(bytes: &[u8]) -> &MyDst {
    unsafe {
        // just the unsized part
        // Safety: The invariants of this function allow us to assume bytes is valid, and
        // having at least #ule_size bytes is a validity constraint for the ULE type.
        let unsized_bytes = bytes.get_unchecked(1..);
        // We should use the pointer metadata APIs here when they are stable: https://github.com/rust-lang/rust/issues/81513
        // For now we rely on all DST metadata being a usize to extract it via a fake slice pointer
        let (_ptr, metadata): (usize, usize) = ::core::mem::transmute(unsized_bytes);
        let entire_struct_as_slice: *const [u8] = ::core::slice::from_raw_parts(bytes.as_ptr(), metadata);
        &*(entire_struct_as_slice as *const MyDst)
    }
}

fn main() {
    let x = unsafe { from_bytes_unchecked(&[2, 4, 6, 7, 8]) };
    println!("{:?}", x.0);
    println!("{:?}", &x.1);
}

[Manishearth]

And it works with the new pointer metadata APIs

#![feature(ptr_metadata)]

#[repr(C, packed)]
struct MyDst(u8, [u8]);

#[inline]
unsafe fn from_bytes_unchecked(bytes: &[u8]) -> &MyDst {
    unsafe {
        let unsized_bytes = bytes.get_unchecked(1..);
        let metadata = core::ptr::metadata(unsized_bytes);
        &*core::ptr::from_raw_parts::<MyDst>(bytes as *const [u8] as *const u8, metadata)
    }
}

fn main() {
    let x = unsafe { from_bytes_unchecked(&[2, 4, 6, 7, 8]) };
    println!("{:?}", x.0);
    println!("{:?}", &x.1);
}

[Manishearth]

Unfortunately with ICU4X we're in a couple situations where we're doing something unsound according to draft rules for Rust safety, but there's no sound way of doing that thing yet (and it will likely be added before those rules stabilize). #2095 is another one.

[Manishearth]

A thing we could do is enable these APIs under cfg(miri), which somewhat feels like cheating, but it would make us have clean miri results which is actually a great benefit.

... except that won't work since the custom derive can't enable features in the target crate. But it would work for the box thing!

[Manishearth]

The owning APIs can be fixed similarly:

VarULE::to_boxed:

            // Get the pointer representation
            let ptr = Self::from_bytes_unchecked(&bytesvec) as *const Self;
            let metadata = core::ptr::metadata(ptr);
            // Transmute the pointer to an owned pointer
            Box::from_raw(core::ptr::from_raw_parts_mut(Box::into_raw(bytesvec) as *mut [u8] as *mut u8, metadata))

encode_varule_to_box:

        // Safety: `ptr` is a box, and `T` is a VarULE which guarantees it has the same memory layout as `[u8]`
        // and can be recouped via from_bytes_unchecked()
        let ptr =  T::from_bytes_unchecked(&boxed) as *const T;
        let metadata = core::ptr::metadata(ptr);

        // Safety: we can construct an owned version since we have mem::forgotten the older owner
        Box::from_raw(core::ptr::from_raw_parts_mut(Box::into_raw(boxed) as *mut [u8] as *mut u8, metadata))

[RalfJung]

In rust-lang/rust#81513 you said that this is a problem with both Stacked Borrows and Tree Borrows. For SB that sounds right, but for TB that is a surprise to me -- is this really UB in Tree Borrows? What does the error look like?