avoid violating `slice::from_raw_parts` safety contract in `Vec::extract_if`

[petrosagg]

The implementation of the Vec::extract_if iterator violates the safety contract adverized by slice::from_raw_parts by always constructing a mutable slice for the entire length of the vector even though that span of memory can contain holes from items already drained. The safety contract of slice::from_raw_parts requires that all elements must be properly initialized.

As an example we can look at the following code:

let mut v = vec![Box::new(0u64), Box::new(1u64)];
for item in v.extract_if(.., |x| **x == 0) {
    drop(item);
}

In the second iteration a &mut [Box<u64>] slice of length 2 will be constructed. The first slot of the slice contains the bitpattern of an already deallocated box, which is invalid.

This fixes the issue by only creating references to valid items and using pointer manipulation for the rest. I have also taken the liberty to remove the big unsafe blocks in place of targetted ones with a SAFETY comment. The approach closely mirrors the implementation of Vec::retain_mut.

Note to reviewers: The diff is easier to follow with whitespace hidden.

[rustbot]

r? @joboet

rustbot has assigned @joboet. They will have a look at your PR within the next two weeks and either review your PR or reassign to another reviewer.

Use r? to explicitly pick a reviewer

[petrosagg]

I was unable to trigger a miri failure with this. I seems to have something to do with how deeply value validity is checked because miri correctly flags this code:

let ptr = std::ptr::null_mut();
let b = unsafe { std::mem::transmute::<*mut u64, Box<u64>>(ptr) };

but doesn't detect UB in this code:

let mut ptr = std::ptr::null_mut();
let b = unsafe { std::mem::transmute::<&mut *mut u64, &mut Box<u64>>(&mut ptr) };

[petrosagg]

@RalfJung if you have any pointers for how to write a miri test for this PR I'm happy to have another go at it.

[rust-log-analyzer]

The job x86_64-gnu-llvm-19 failed! Check out the build log: (web) (plain)

Click to see the possible cause of the failure (guessed by this bot)

Runner name: 'ubuntu-24.04-16core-64gb_6222c5c835e7'
Machine name: 'pkrvmf6wy0o8zjz'
##[group]Operating System
Ubuntu
24.04.2
LTS
##[endgroup]
---
#18 exporting to docker image format
#18 sending tarball 21.2s done
#18 DONE 30.1s
##[endgroup]
Setting extra environment values for docker:  --env ENABLE_GCC_CODEGEN=1 --env GCC_EXEC_PREFIX=/usr/lib/gcc/
[CI_JOB_NAME=x86_64-gnu-llvm-19]
[CI_JOB_NAME=x86_64-gnu-llvm-19]
debug: `DISABLE_CI_RUSTC_IF_INCOMPATIBLE` configured.
---
sccache: Listening on address 127.0.0.1:4226
##[group]Configure the build
configure: processing command line
configure: 
configure: build.configure-args := ['--build=x86_64-unknown-linux-gnu', '--llvm-root=/usr/lib/llvm-19', '--enable-llvm-link-shared', '--set', 'rust.randomize-layout=true', '--set', 'rust.thin-lto-import-instr-limit=10', '--set', 'build.print-step-timings', '--enable-verbose-tests', '--set', 'build.metrics', '--enable-verbose-configure', '--enable-sccache', '--disable-manage-submodules', '--enable-locked-deps', '--enable-cargo-native-static', '--set', 'rust.codegen-units-std=1', '--set', 'dist.compression-profile=balanced', '--dist-compression-formats=xz', '--set', 'rust.lld=false', '--disable-dist-src', '--release-channel=nightly', '--enable-debug-assertions', '--enable-overflow-checks', '--enable-llvm-assertions', '--set', 'rust.verify-llvm-ir', '--set', 'rust.codegen-backends=llvm,cranelift,gcc', '--set', 'llvm.static-libstdcpp', '--set', 'gcc.download-ci-gcc=true', '--enable-new-symbol-mangling']
configure: build.build          := x86_64-unknown-linux-gnu
configure: target.x86_64-unknown-linux-gnu.llvm-config := /usr/lib/llvm-19/bin/llvm-config
configure: llvm.link-shared     := True
configure: rust.randomize-layout := True
configure: rust.thin-lto-import-instr-limit := 10
---
   Compiling compiler_builtins v0.1.159
[RUSTC-TIMING] build_script_build test:false 0.309

thread 'rustc' panicked at library/core/src/panicking.rs:225:5:
unsafe precondition(s) violated: ptr::copy_nonoverlapping requires that both pointer arguments are aligned and non-null and the specified memory ranges do not overlap

This indicates a bug in the program. This Undefined Behavior check is optional, and cannot be relied on for safety.
stack backtrace:
   0:     0x7effc6919fe4 - <<std[97575463abcf64a5]::sys::backtrace::BacktraceLock>::print::DisplayBacktrace as core[5399894434fbec0e]::fmt::Display>::fmt
   1:     0x7effc6974763 - core[5399894434fbec0e]::fmt::write
   2:     0x7effc690d9b9 - <std[97575463abcf64a5]::sys::stdio::unix::Stderr as std[97575463abcf64a5]::io::Write>::write_fmt
   3:     0x7effc6919e92 - <std[97575463abcf64a5]::sys::backtrace::BacktraceLock>::print
   4:     0x7effc691e459 - std[97575463abcf64a5]::panicking::default_hook::{closure#0}
   5:     0x7effc691e1f2 - std[97575463abcf64a5]::panicking::default_hook
   6:     0x7effc26124f5 - std[97575463abcf64a5]::panicking::update_hook::<alloc[55daa3099f06b8bf]::boxed::Box<rustc_driver_impl[3810b224b896a567]::install_ice_hook::{closure#1}>>::{closure#0}
   7:     0x7effc691efc3 - std[97575463abcf64a5]::panicking::rust_panic_with_hook
   8:     0x7effc691ebca - std[97575463abcf64a5]::panicking::begin_panic_handler::{closure#0}
   9:     0x7effc691a599 - std[97575463abcf64a5]::sys::backtrace::__rust_end_short_backtrace::<std[97575463abcf64a5]::panicking::begin_panic_handler::{closure#0}, !>
  10:     0x7effc691e806 - __rustc[764efdf202547135]::rust_begin_unwind
  11:     0x7effc25b708d - core[5399894434fbec0e]::panicking::panic_nounwind_fmt
  12:     0x7effc25b7122 - core[5399894434fbec0e]::panicking::panic_nounwind
  13:     0x7effc570e758 - <alloc[55daa3099f06b8bf]::vec::extract_if::ExtractIf<rustc_middle[343f04f986373764]::ty::predicate::Clause, rustc_trait_selection[351bb25b8d288d86]::traits::normalize_param_env_or_error::{closure#1}> as core[5399894434fbec0e]::iter::traits::iterator::Iterator>::next
  14:     0x7effc57370d8 - <alloc[55daa3099f06b8bf]::vec::Vec<rustc_middle[343f04f986373764]::ty::predicate::Clause> as alloc[55daa3099f06b8bf]::vec::spec_from_iter::SpecFromIter<rustc_middle[343f04f986373764]::ty::predicate::Clause, alloc[55daa3099f06b8bf]::vec::extract_if::ExtractIf<rustc_middle[343f04f986373764]::ty::predicate::Clause, rustc_trait_selection[351bb25b8d288d86]::traits::normalize_param_env_or_error::{closure#1}>>>::from_iter
  15:     0x7effc552e3a0 - rustc_trait_selection[351bb25b8d288d86]::traits::normalize_param_env_or_error
  16:     0x7effc49ee0cc - rustc_ty_utils[983e250615c5032e]::ty::param_env

[pitust]

@petrosagg miri reports the error if you run with MIRIFLAGS=-Zmiri-recursive-validation:

error: Undefined Behavior: constructing invalid value at .<deref>[0]: encountered a dangling box (use-after-free)
   --> /home/pitust/.rustup/toolchains/nightly-aarch64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/raw.rs:192:9
    |
192 |         &mut *ptr::slice_from_raw_parts_mut(data, len)
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ constructing invalid value at .<deref>[0]: encountered a dangling box (use-after-free)
    |
    = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior
    = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html for further information
    = note: BACKTRACE:
    = note: inside `std::slice::from_raw_parts_mut::<'_, std::boxed::Box<u64>>` at /home/pitust/.rustup/toolchains/nightly-aarch64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/raw.rs:192:9: 192:55
    = note: inside `<std::vec::ExtractIf<'_, std::boxed::Box<u64>, {closure@src/main.rs:100:34: 100:37}> as std::iter::Iterator>::next` at /home/pitust/.rustup/toolchains/nightly-aarch64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/vec/extract_if.rs:71:25: 71:87
note: inside `main`
   --> src/main.rs:100:17
    |
100 |     for item in v.extract_if(.., |x| **x == 0) {
    |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

[petrosagg]

oh, amazing! I will add a testcase

[RalfJung]

Note that that flag enables UB checks that are very strict, and goes beyond what we are sure will be UB.

[petrosagg]

I see. This particular test exercises very little code but I don't have a strong opinion either. If we want to avoid using this experimental feature until the validity UB rules become more established I can leave the PR as-is.

Any opinions as to whether a testcase for this would be useful to have?

[tgross35]

Cc @the8472 who I believe authored this.

Any opinions as to whether a testcase for this would be useful to have?

Something that exercises the UB with the current implementation would be great, even if it doesn't currently get flagged by default miri.

[rustbot]

These commits modify the Cargo.lock file. Unintentional changes to Cargo.lock can be introduced when switching branches and rebasing PRs.

If this was unintentional then you should revert the changes before this PR is merged. Otherwise, you can ignore this comment.

The Miri subtree was changed

cc @rust-lang/miri

[petrosagg]

@tgross35 great! Just added a miri testcase for this. I did pass the experimental flag, meaning that the test fails without the fix.

[the8472]

I only did some later modifications, this was originally introduced as drain_filter in #43245

In the second iteration a &mut [Box] slice of length 2 will be constructed. The first slot of the slice contains the bitpattern of an already deallocated box, causing UB.

The bytes are still initialized, we don't de-init the bytes when moving the value out. It happens to be the bytes of a pointer that points to a deallocated object.

AIUI validity requirements are still under discussion, but leaning no in this case: https://github.com/rust-lang/unsafe-code-guidelines/issues/412

That said, the slice construction is superfluous and if we can replace it with something that's easier to reason about that's fine.

[pitust]

Note that that flag enables UB checks that are very strict, and goes beyond what we are sure will be UB.

This is true. However, I would argue that the standard to which the standard library should be held to is "definitely not UB" and not "maybe UB or maybe not", especially if the fix is not particularly difficult and doesn't have a meaningful runtime impact.

[saethlin]

I do not think it makes sense to hold this one part of the library to a standard that the rest of it, let alone the compiler's output, does not come close to satisfying: https://github.com/rust-lang/unsafe-code-guidelines/issues/412#issuecomment-2264934201

[petrosagg]

In light of the discussion from the unsafe code guidelines repo it's clear that this PR is in a gray area as to whether it fixes UB or not. The current safety contract for slice::from_raw_parts clearly says it's UB. At the same time many people in the project think it shouldn't be. Let's not decide this in this PR.

I'd argue this PR is valuable on its own even if this behavior is not deemed UB in the future for two reasons:

1. It avoids violating Rust's own documented rules, leading to less confusion to people reading the code. This is how I ended up here in the first place.
2. It makes targeted and justified use of unsafe instead of big unsafe blocks.

I have removed the miri testcase that uses the experimental flag and have rephrased the commit and description of the PR to reflect this new framing.

[RalfJung]

There is no language UB here at the moment. There is library UB but this code is inside the same library, so that is not necessarily a problem -- it boils down to a matter of preference of the libs team:

• either add a comment saying that yes we are violating the library precondition here but we can rely on implementation details of from_raw_parts and hence it's okay (but it would not be okay to do the same outside the standard library)
• or change the code to avoid the library UB

Miri does not test for library UB, so you can't add a Miri test. I don't think it's worth having a test with -Zmiri-recursive-validation. However it'd still be worth adding the code that reproduces the issue to miri/tests/pass/vec.rs so that we ensure that there isn't language UB here in the future.

[alex-semenyuk]

@petrosagg Thanks for your contribution From wg-triage. Could you please handle suggestion from comment above

[Dylan-DPC]

@petrosagg any updates on this? thanks

[rustbot]

:warning: Warning :warning:

• This PR is based on an upstream commit that is older than 28 days.

  It's recommended to update your branch according to the rustc-dev-guide.

[petrosagg]

@Dylan-DPC I just addressed the review and rebased on top of current master. Let me know if you would like me to squash the review changes in the original commit

[RalfJung]

As I said before:

However it'd still be worth adding the code that reproduces the issue to miri/tests/pass/vec.rs so that we ensure that there isn't language UB here in the future.

Otherwise, once you think this is ready for review, please write @rustbot ready.

[RalfJung]

I am not sure how you misinterpreted what I said, but let me repeat the suggestion, with some parts in bold:

However it'd still be worth adding the code that reproduces the issue to miri/tests/pass/vec.rs so that we ensure that there isn't language UB here in the future.

Please read suggestions carefully. Review takes a lot more time and patience when we have to repeat ourselves.

[petrosagg]

@RalfJung I apologize, I reverted the miri test commit from the previous version of the PR and didn't notice the request for the different path. I moved it in its appropriate place now

[petrosagg]

@rustbot ready

[tgross35]

(please be sure to squash before merge)

[petrosagg]

@tgross35 commits are now squashed

[joboet]

While the old implementation wasn't unsound per-se, I much prefer the new one (it is also much better documented). Thank you (and everyone who participated) for your efforts!

@bors r+

[bors]

:pushpin: Commit e9b2c4f395673399b0445733c7e8d3955e42ff0c has been approved by joboet

It is now in the queue for this repository.