VecDeque::shrink_to leads to UB if handle_alloc_error unwinds.

[Sp00ph]

I tried this code:
https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=a2e4bd9f59882c88c4f232379cbb0001

I expected to see this happen:
shrink_to_fit causes an alloc error, the thread unwinds, Foo(0) and Foo(1) are dropped in some order.

Instead, this happened:

thread 'main' panicked at src/main.rs:37:30:
alloc error
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Dropping Foo(1)
Dropping Foo(3472329422384804195)

(the exact value printed differs between runs, which makes sense if it's reading uninit memory)

This occurs because of the way VecDeque::shrink_to is implemented: It first moves the memory around to fit the new capacity, then calls RawVec::shrink_to_fit(new_capacity) with no regards to potential unwinding. Specifically, this would look something like this:

1. After initialization, the deque buffer looks like this:

[Foo(0), <uninit> * 13, Foo(1)]
 ^                      ^
last                   head      

2. shrink_to copies the head to just behind the tail:

[Foo(0), Foo(1), <uninit> * 13]
 ^       ^
last    head

3. shrink_to calls RawVec::shrink_to_fit calls Allocator::shrink which returns an alloc error, the error handler unwinds, leaving the buffer looking like this:

[Foo(0), Foo(1), <uninit>, <uninit> * 12]
         ^       ^
        head    last

4. The Drop impl of VecDeque drops its elements, reading the uninit memory.

Meta

While this specific setup requires nightly to manually set the alloc error handle hook and to trigger the alloc error in shrink, this same bug could occur on stable if shrink OOMs. The docs for handle_alloc_error also explicitly state that it may either abort or unwind.

I'm not sure what would be the best way to fix this. Maybe just catch_unwind the call to RawVec::shrink_to_fit and manually abort the process would work well enough?

[Sp00ph]

@rustbot label +T-libs +I-unsound

[oli-obk]

And we can't even run it in miri (cc @rust-lang/miri):

error: unsupported operation: can't call (diverging) foreign function: __rust_alloc_error_handler
   --> /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/alloc.rs:385:13
    |
385 |             __rust_alloc_error_handler(layout.size(), layout.align());
    |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ can't call (diverging) foreign function: __rust_alloc_error_handler
    |
    = help: this is likely not a bug in the program; it indicates that the program performed an operation that the interpreter does not support
    = note: BACKTRACE:
    = note: inside `std::alloc::handle_alloc_error::rt_error` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/alloc.rs:385:13: 385:70
    = note: inside `std::alloc::handle_alloc_error` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/alloc.rs:391:9: 391:75
    = note: inside `alloc::raw_vec::handle_error` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/raw_vec.rs:583:38: 583:64
    = note: inside `alloc::raw_vec::RawVec::<Foo, BadAlloc>::shrink_to_fit` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/raw_vec.rs:423:13: 423:30
    = note: inside `std::collections::VecDeque::<Foo, BadAlloc>::shrink_to` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/collections/vec_deque/mod.rs:1033:9: 1033:43
    = note: inside `std::collections::VecDeque::<Foo, BadAlloc>::shrink_to_fit` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/collections/vec_deque/mod.rs:939:9: 939:26
note: inside `main`
   --> src/main.rs:41:5
    |
41  |     v.shrink_to_fit();
    |     ^^^^^^^^^^^^^^^^^

[RalfJung]

Yeah the Miri allocator never fails so we never even tried running the alloc_error_handler... filed rust-lang/miri#3439 to track that.

[Amanieu]

This is nightly-only since it requires an unstable flag -Z oom=panic.

[Sp00ph]

Could there hypothetically be a scenario (on stable) where you're not linking against std, but you still have an unwinding panic handler? In that case I think this UB could still occur (because handle_alloc_error panics when not linked against std).

[Amanieu]

No, all of the machinery related to unwinding depends on unstable implementation details.

[Sp00ph]

In that case, would it be possible to just back out of allowing handle_alloc_error to unwind? It seems that it always aborts on stable (which evidently programs rely on), and allowing it to unwind feels like just another unsafe footgun to me.

[Sp00ph]

Looks like the docs were changed to allow unwinding in #115007 based on the arguments in #114898 that the custom alloc error hook is allowed to unwind and that 1.68 release notes stated that future versions of std may choose to call the panic handler on OOM. To me these points don't seem mutually exclusive to handle_alloc_error always aborting; even if either a custom handler or the default handler panics and unwinds, we could just catch those unwinds and abort unconditionally.

[Amanieu]

Unwinding on OOM was introduced in RFC 2116 (tracking issue), and unsafe code not handling this correct was a known issue. I think we should keep this feature as unstable until we have at least audited the entire standard library for incorrect handling of unwinds on OOM.

[RalfJung]

Running this in Miri works now, and does report "Undefined Behavior: using uninitialized data, but this operation requires initialized memory".