Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

VecDeque::shrink_to leads to UB if handle_alloc_error unwinds. #123369

Closed
Tracked by #43596
Sp00ph opened this issue Apr 2, 2024 · 10 comments · Fixed by #123803
Closed
Tracked by #43596

VecDeque::shrink_to leads to UB if handle_alloc_error unwinds. #123369

Sp00ph opened this issue Apr 2, 2024 · 10 comments · Fixed by #123803
Labels
C-bug Category: This is a bug. I-unsound Issue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness P-medium Medium priority T-libs Relevant to the library team, which will review and decide on the PR/issue.

Comments

@Sp00ph
Copy link
Member

Sp00ph commented Apr 2, 2024

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      
  1. shrink_to copies the head to just behind the tail:
[Foo(0), Foo(1), <uninit> * 13]
 ^       ^
last    head
  1. 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
  1. 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 Sp00ph added the C-bug Category: This is a bug. label Apr 2, 2024
@rustbot rustbot added the needs-triage This issue may need triage. Remove it if it has been sufficiently triaged. label Apr 2, 2024
@Sp00ph
Copy link
Member Author

Sp00ph commented Apr 2, 2024

@rustbot label +T-libs +I-unsound

@rustbot rustbot added I-unsound Issue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness T-libs Relevant to the library team, which will review and decide on the PR/issue. I-prioritize Issue: Indicates that prioritization has been requested for this issue. labels Apr 2, 2024
@oli-obk
Copy link
Contributor

oli-obk commented Apr 2, 2024

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
Copy link
Member

RalfJung commented Apr 2, 2024

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
Copy link
Member

Amanieu commented Apr 2, 2024

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

@Sp00ph
Copy link
Member Author

Sp00ph commented Apr 2, 2024

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
Copy link
Member

Amanieu commented Apr 2, 2024

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

@jieyouxu jieyouxu removed the needs-triage This issue may need triage. Remove it if it has been sufficiently triaged. label Apr 3, 2024
@Sp00ph
Copy link
Member Author

Sp00ph commented Apr 3, 2024

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
Copy link
Member Author

Sp00ph commented Apr 3, 2024

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.

@m-ou-se m-ou-se added P-medium Medium priority and removed I-prioritize Issue: Indicates that prioritization has been requested for this issue. labels Apr 3, 2024
@Amanieu
Copy link
Member

Amanieu commented Apr 4, 2024

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.

matthiaskrgr added a commit to matthiaskrgr/rust that referenced this issue Apr 14, 2024
…acrum

Fix `VecDeque::shrink_to` UB when `handle_alloc_error` unwinds.

Fixes rust-lang#123369

For `VecDeque` it's relatively simple to restore the buffer into a consistent state so this PR does just that.

Note that with its current implementation, `shrink_to` may change the internal arrangement of elements in the buffer, so e.g. `[D, <uninit>, A, B, C]` will become `[<uninit>, A, B, C, D]` and `[<uninit>, <uninit>, A, B, C]` may become `[B, C, <uninit>, <uninit>, A]` if `shrink_to` unwinds. This shouldn't be an issue though as we don't make any guarantees about the stability of the internal buffer arrangement (and this case is impossible to hit on stable anyways).

This PR also includes a test with code adapted from rust-lang#123369 which fails without the new `shrink_to` code. Does this suffice or do we maybe need more exhaustive tests like in rust-lang#108475?

cc `@Amanieu`

`@rustbot` label +T-libs
@RalfJung
Copy link
Member

RalfJung commented May 6, 2024

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

@bors bors closed this as completed in 7fb8122 May 26, 2024
rust-timer added a commit to rust-lang-ci/rust that referenced this issue May 26, 2024
Rollup merge of rust-lang#123803 - Sp00ph:shrink_to_fix, r=Mark-Simulacrum

Fix `VecDeque::shrink_to` UB when `handle_alloc_error` unwinds.

Fixes rust-lang#123369

For `VecDeque` it's relatively simple to restore the buffer into a consistent state so this PR does just that.

Note that with its current implementation, `shrink_to` may change the internal arrangement of elements in the buffer, so e.g. `[D, <uninit>, A, B, C]` will become `[<uninit>, A, B, C, D]` and `[<uninit>, <uninit>, A, B, C]` may become `[B, C, <uninit>, <uninit>, A]` if `shrink_to` unwinds. This shouldn't be an issue though as we don't make any guarantees about the stability of the internal buffer arrangement (and this case is impossible to hit on stable anyways).

This PR also includes a test with code adapted from rust-lang#123369 which fails without the new `shrink_to` code. Does this suffice or do we maybe need more exhaustive tests like in rust-lang#108475?

cc `@Amanieu`

`@rustbot` label +T-libs
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
C-bug Category: This is a bug. I-unsound Issue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness P-medium Medium priority T-libs Relevant to the library team, which will review and decide on the PR/issue.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

7 participants