Stack_box crate: put unsize stuff on stack

code review
1

Fancyflame/stack_box (github.com)
stack_box - crates.io: Rust Package Registry

Features are similar to smallbox and checked by Miri.
Interesting new features:

  • Unsize coercion is 100% in safe rust
  • A macro with which you can coerce a sized box into an unsized box by a simple call coerce!(your_stack_box) .
    (StackBox<T, Ctnr> -> StackBox<dyn Trait, Ctnr>)
  • A macro could easily make a StackBox type alias which could exactly contains some type.
    type StringBox<T> = FitStackBox!(T, String);
StringBox::new("a".to_string()); // always works
  • Static check if a value could be put into a StackBox, emit a compile time error if check is failed.

Please take a look at examples/basic.rs!

2 Likes
2

FYI your crate seems to be unsound when used with a type that has internal mutability (and smallbox too, which I just reported here).

Consider for example:

fn main() {
    use std::cell::Cell;
    type CellBox = stack_box::FitStackBox!(Cell<u32>, Cell<u32>);
    let cellbox = CellBox::new(Cell::new(0));
    cellbox.set(1);
}

MIRI complains with the following:

error: Undefined Behavior: trying to retag from <1431> for SharedReadWrite permission at alloc804[0x8], but that tag only grants SharedReadOnly permission for this location
   --> E:\Programmi\Rust\.cargo\registry\src\index.crates.io-6f17d22bba15001f\stack_box-1.1.0\src/lib.rs:114:18
    |
114 |         unsafe { &*with_metadata(self.container.as_ptr().cast(), self.reinterpreter) }
    |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |                  |
    |                  trying to retag from <1431> for SharedReadWrite permission at alloc804[0x8], but that tag only grants SharedReadOnly permission for this location
    |                  this error occurs as part of retag at alloc804[0x8..0xc]
    |
    = 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: <1431> was created by a SharedReadOnly retag at offsets [0x8..0xc]
   --> src/main.rs:5:5
    |
5   |     cellbox.set(1);
    |     ^^^^^^^^^^^^^^
    = note: BACKTRACE (of the first span):
    = note: inside `<stack_box::StackBox<std::cell::Cell<u32>, stack_box::container::Align4<4>> as std::ops::Deref>::deref` at E:\Programmi\Rust\.cargo\registry\src\index.crates.io-6f17d22bba15001f\stack_box-1.1.0\src/lib.rs:114:18: 114:85
note: inside `main`
   --> src/main.rs:5:5
    |
5   |     cellbox.set(1);
    |     ^^^^^^^^^^^^^^

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

This is because you effectively store it in a MaybeUninit<AlignN<[u8; SIZE]>>, which is not allowed to be mutated through a shared reference. This should be fixable by wrapping it in a UnsafeCell.

3 Likes
3

thanks a lot, I'll fix it later. :grinning:

4

Fixed, and I added an example to show internal mutability. The following code could pass Miri's check.

type CellBox<T> = FitStackBox!(RefCell<T>, RefCell<u32>);

fn main() {
    let cb = CellBox::new(RefCell::new(10u32)); // internal mutability
    let r1 = cb.borrow();
    let r2 = cb.borrow();
    drop((r1, r2));
    *cb.borrow_mut() = 99;
}
5

How does this crate compare to dungeon_cell, inline_dyn, and stackbox?

6

Downloads of these crates are too few, so I haven't gotten to know them in detail, I only read their readme and documentations roughly. The first thing to be clear about is that the point of using this type of tool is to do type erasure (via unsize type coercion), so we should focus on it.

  • dungeon_cell: this crate requires nightly compiler to perform unsize coercion while stack_box doesn't.
  • inline_dyn: this crate can only coerce boxes into exact some specified trait objects, while
    stack_box can coerce types into any unsized types as long as you can do this on std box.
  • stackbox: the same as above.

By contrast, smallbox is much more competitive than them. It can coerce types into any unsized type as well, and provides a macro to perform underlying unsafe operations. But with stack_box, type coercion is safe and using macro to perform unsize coercion is optional.

7

In coerce_unsized, you have a comment saying "we could not assume the returned checker is which we provide". Is there any actual way to cause returned_checker to be a different thing from checker, and therefore cause the panic? I can't figure it out.

8

It can't be produce for time being, but that is not guaranteed. Once the user get &'mut static UnsizeChecker somewhere by unknown means this function becomes dangerous.

It is physically exists, if we create a thread and block forever at coerce_unsized function, we could say that input &mut UnsizeChecker is 'static.

9

There is a deemed sound (but unsafe-using) API which here could allow to indeed swap the UnsizeCheckers:

enum Never {}
fn scoped_ad_infinitum<'unbounded, T : 'unbounded>(
    r: &mut T,
    scope: impl FnOnce(&'unbounded mut T) -> Never,
) -> !
{
    let yield_ = scope;
    ::scopeguard::defer_on_unwind! {
        loop {
            ::std::thread::sleep(::std::time::Duration::MAX);
        } // or just abort.
   }
   #[allow(unreachable_code)] { // False positive
       let unreachable = yield_(unsafe { &mut *&raw mut *r });
       match unreachable {}
   } // <- here we're either infinitely looping (fine), aborted (fine),
     //    or unwinding (not fine!)
} // <- if unwinding, our defer brings us back
  //    to one of the other two.

With it, you can scope two StackBox::coerce_unsized()s:

StackBox::coerce_unsized(first, |a| scoped_ad_infinitum(a, |a| {
    let bad = StackBox::coerce_unsized(second, |b| {
        a as _
    });
    /* use `bad`… */
    panic!("Too late to prevent unsoundness");
}));

Now, if the inner bad-yielding coerce_unsized() were not to detect this and panic, we would end up with a bad instance which on Deref would unsize the second value with the impl !Sized metadata of first. To see how that is very bad, consider, for instance:

  • if first: bool : Unsize<dyn AsRef<bool>>
  • and second: u8 = 0b10, then we'd end up with a bad: StackBox<dyn AsRef<bool>>, which, on .as_ref() use, would be trying to see its inner second = 0b10_u8 value as a bool, which is UB.

So that check is indeed paramount for soundness.

1 Like
10

On the other hand, @Fancyflame, the following is unsoundly relying on the layout of wide pointers:

Indeed, you are basically converting a &mut *mut impl ?Sized to a &mut *mut () (to then overwrite that part), i.e., your are transmuting assuming the following layout:

#[repr(C)]
union {
    wide_ptr: *mut impl ?Sized,
    thin_data_ptr: *mut (),
}

or, in clearer terms, you are assuming the following layout for *mut impl ?Sized:

#[repr(C)]
struct *mut impl ?Sized {
    data: *mut (),
    ...
}

wherein your

(&raw mut meta)
 // .byte_add(::core::mem::offset_of!(*mut impl ?Sized ,data))
    .cast::<*mut ()>()

would amount to doing:

&raw mut meta.data

Until the ::core::ptr::from_raw_parts{,_mut}() API gets stabilized, there is no sound way to construct what you want.

Right now the fix is probably gonna be to be calling the given "unsizer" on every deref.

  • First problem is then that in order to use it on shared references too, you'd:

    • either need another callback there,

    • or to have a raw-pointer-based unsizer callback, but that then would probably mean making .coerce_unsized() an unsafe fn;

Since you intended to be unsizing behind a macro, the latter point should not be that much of a problem, and with a trivial enough callback you can hope this stuff to be inlined, resulting in optimized codegen which will be equal to your manual ptr::from_raw_parts{,_mut}() shenanigans :slightly_smiling_face:

The following crate warrants a special mention, since it does look like you could defer to it to avoid NIH-reïnventing stuff, while also allowing centralized code review and fixes:

3 Likes
11

Thanks for code review. :grinning:

This code I was borrowed from smallbox, if this implementation has problem then so does that crate. Yes I realize what this code would do, but it is the only way I could found that make Miri won't complain (should it?).

Setting metadata or address both the ways could get a new valid unsize pointer. I tried copy the implementation from std::ptr::with_addr, it works but Miri say its provenance has been dropped so even with totally new memory address Miri still consider I have read the freed memory (I forgot the details and I'm on my phone so I couldn't get the full error msg right now).

Carrying a function pointer with box and do pointer casting everytime when dereferencing is a sound way, but since this crate is more of for fun for experiment, I wonder if there is a more aggressive way that both safe in the inner implementation and the exposed public function :smile:

12

(I didn't look beyond the with_metadata function, e.g. at the other mentioned crates or even the rest of that crate.)

With wrapping_byte_add, one can detect which half a wide pointer is the data pointer.

Is there other unsoundness here?

3 Likes
13

Woah, Miri didn't error in your sample even I applied metadata of a dangling pointer to a thin pointer. I'll study it later, thanks a lot :grinning:

14

Heh, didn't know we could do pointer arithmetic on wide pointers; that does sound that's a very crafty and original approach! I don't know the abstract machine semantics well enough to confidently state whether this is/will remain fine, so I'll start by cc-ing @InfernoDeity among the AM-savy people

2 Likes
15

For slices, there's no AM level reason such a transmute would be problematic (only down to layout, which is an input to the AM). For dyn, provided you got an actual vtable pointer from the same type, same deal.

2 Likes
16

I've read your code, you judge whether the pointer is 2-usize sized, then judge which part of it stores address, then modify that part. The key is to see if the "write address" operation actually changes the address of the fat pointer.

So I improved my implementation with extra memory layout checking:

fn with_metadata<T: ?Sized>(addr: *mut (), meta: *const T) -> *mut T {
    let mut meta_mut = meta as *mut T;

    // To assert the address of the metadata pointer is not equals to the given address,
    // or just return that metadata pointer directly
    if meta as *mut () == addr {
        return meta_mut;
    }

    // assume address part of a fat pointer is the leading usize-sized bytes
    let meta_ptr: *mut *mut () = (&raw mut meta_mut).cast();
    unsafe {
        meta_ptr.write(addr);
    }

    // to see whether we successfully changed the address
    if meta_mut as *mut () == addr {
        meta_mut
    } else {
        unimplemented!("cannot figure out memory layout of the unsize pointer");
    }
}

And for practical use, we could split the checking part and writing part to avoid unnecessary checks.

17

So, your last playground now panics if the data pointer isn't the first word, but is less robust in the sense that it can't handle 2-word wide pointers where the data pointer is the second word. It's adequate today AFAIK (but I don't think the robustness costs anything after optimization). And OTOH it probably handles hypothetical extra-wide pointers (3+ words), provided the data pointer is first. I guess one could have the best of both worlds by assuming and checking the first word in the case of extra-wide pointers.

Incidentally, for *const dyn Trait in particular, it was decided by FCP that their metadata pointer must always[1] be word-aligned (and non-null). Because of this, you can extract the metadata pointer and use the least-significant bit to record if it is the first or second part of the wide pointer.[2] That's an alternative, robust[3] way to avoid recalculating layout. However, you do have to do this per dyn Trait type.[4]

Here's my latest demonstration of such.

  1. even in unsafe ↩︎

  2. The first time I did this after the FCP, I would implement the trait in question for byte sized type as a way to get a data pointer at an odd address to distinguish from the metadata; since then we got wrapping_byte_add and it's no longer necessary. wrapping_byte_* can also be used to manipulate the least-significant bit of the metadata pointer with less grey area around provenance. ↩︎

  3. up to 2-word pointers ↩︎

  4. Different types can have different layouts, and there's no bound for "trait object" even if they were all guaranteed to have the same layout. ↩︎