In-place optimisation in IntoIterator can lead to memory leak

[Voultapher]

I tried this code:

fn main() {
    #[derive(Debug)]
    struct Old(i32);

    impl Drop for Old {
        fn drop(&mut self) {
            if self.0 == 44 {
                panic!();
            }

            println!("Dropped Old: {}", self.0);
        }
    }

    #[derive(Debug)]
    struct New(i32);

    impl Drop for New {
        fn drop(&mut self) {
            println!("Dropped New: {}", self.0);
        }
    }

    let vec: Vec<Old> = vec![Old(11), Old(22), Old(33), Old(44), Old(55)];
    let vec_ptr = vec.as_ptr();

    let mapped_vec: Vec<New> = vec.into_iter().map(|x| New(x.0)).take(2).collect();
    let mapped_vec_ptr = mapped_vec.as_ptr();

    println!("vec_ptr:    {vec_ptr:?}");
    println!("mapped_vec: {mapped_vec_ptr:?}");
    println!("{mapped_vec:?}");
}

I expected to see this happen:

The drop implementation for New(11) and New(22) is called.

Instead, this happened:

Everything that was mapped and the allocation was leaked.

Meta

rustc --version --verbose:

rustc 1.63.0 (4b91a6ea7 2022-08-08)
binary: rustc
commit-hash: 4b91a6ea7258a947e59c6522cd5898e7c0a6a88f
commit-date: 2022-08-08
host: aarch64-apple-darwin
release: 1.63.0
LLVM version: 14.0.5

I discovered this issue when I learned that IntoIterator re-uses a Vec allocation if possible. Which prompted me to read the code. Running the example with cargo miri run also reports the memory leak. And changing New(i32) to New(i64) no longer displays the memory leak. This is what I think happens:

[ 11| 22| 33| 44| 55] Values
[ 0 | 1 | 2 | 3 | 4 ] Indices

[Old|Old|Old|Old|Old] Start (default fn from_iter)

[New|Old|Old|Old|Old] Map [0] (fn collect_in_place)
[New|New|Old|Old|Old] Map [1] (fn collect_in_place)

[New|New|Drp|Old|Old] Drop [2] (fn forget_allocation_drop_remaining)
[New|New|Drp|Old|Old] Drop [3] (fn forget_allocation_drop_remaining) PANIC

While dropping [3] the ptr::drop_in_place(remaining) call in forget_allocation_drop_remaining panics.

Then [4] is being dropped, but honestly I don't really understand why. My understanding is that ptr::drop_in_place(remaining) should unwind. If anyone can explain this, please do so.

Then as part of unwinding collect_in_place IntoIter is dropped, but it has its fields set to an empty buffer of len 0, so it does nothing. Note, I suspect more optimal code gen could be achieved by using mem::forget to avoid generating code for the IntoIter drop that will never do anything after we cleared the fields.

The two created New will never get dropped, thus leading to the memory leak. Plus the main Vec allocation, previously owned by IntoIterator as stored in dst_buf will be leaked too. Because it was cleared in forget_allocation_drop_remaining and assumed to be taken over by let vec = unsafe { Vec::from_raw_parts(dst_buf, len, cap) }; but we never reached that point.

---

Proposed solution, a drop guard in collect_in_place that guards the forget_allocation_drop_remaining call and would drop the head in this case 0..2 and the backing allocation if forget_allocation_drop_remaining panics.

[Voultapher]

Tagging @steffahn because of your work on #85873 and the associated PRs.

[steffahn]

Nice find! Technically this is a regression. @rustbot label regression-from-stable-to-stable, T-libs. It works properly until 1.47, it double-frees Old(33) and then aborts (thread panicked while panicking; presumably because of double-freeing Old(44), too) in 1.48 through 1.51, and the current behavior is since 1.52 (all tested on godbolt, with the direct usage of variables in format strings fixed).

[steffahn]

I haven’t looked at the code yet myself to figure out what’s going on. In the meantime, I think that bisecting what changes were relevant for the regression 1.47 to 1.48 on one hand, and the point between 1.51 and 1.52 that appeared to have fixed the double-free (but introduced or kept (hard to tell with the abort) the memory leak) could be interesting. @rustbot label E-needs-bisection. ^^

[steffahn]

Doing the bisection. First one is nightly-2020-09-04

  commit[0] 2020-09-02UTC: Auto merge of #76160 - scileo:format-recovery, r=petrochenkov
  commit[1] 2020-09-02UTC: Auto merge of #76233 - cuviper:unhasher, r=Mark-Simulacrum
  commit[2] 2020-09-03UTC: Auto merge of #76265 - Dylan-DPC:rollup-j3i509l, r=Dylan-DPC
  commit[3] 2020-09-03UTC: Auto merge of #75971 - Amjad50:libstd-deny-unsafe_op_in_unsafe_fn, r=Mark-Simulacrum
  commit[4] 2020-09-03UTC: Auto merge of #76235 - jyn514:std-intra-links, r=poliorcetics
  commit[5] 2020-09-03UTC: Auto merge of #76283 - RalfJung:miri, r=RalfJung
  commit[6] 2020-09-03UTC: Auto merge of #73819 - euclio:rustdoc-summaries, r=jyn514,GuillaumeGomez
  commit[7] 2020-09-03UTC: Auto merge of #70793 - the8472:in-place-iter-collect, r=Amanieu

second one is nightly-2021-04-03

  commit[0] 2021-04-01UTC: Auto merge of #82780 - cjgillot:dep-stream, r=michaelwoerister
  commit[1] 2021-04-02UTC: Auto merge of #83663 - AngelicosPhosphoros:simplify_binary_and_to_get_better_asm, r=nagisa
  commit[2] 2021-04-02UTC: Auto merge of #80828 - SNCPlay42:opaque-projections, r=estebank
  commit[3] 2021-04-02UTC: Auto merge of #80965 - camelid:rename-doc-spotlight, r=jyn514
  commit[4] 2021-04-02UTC: Auto merge of #83207 - oli-obk:valtree2, r=lcnr
  commit[5] 2021-04-02UTC: Auto merge of #83781 - JohnTitor:rollup-1vm3dxo, r=JohnTitor
  commit[6] 2021-04-02UTC: Auto merge of #83468 - hi-rustin:rustin-patch-lint, r=nikomatsakis
  commit[7] 2021-04-02UTC: Auto merge of #76881 - hameerabbasi:issue-53325, r=oli-obk
  commit[8] 2021-04-02UTC: Auto merge of #83790 - Dylan-DPC:rollup-p6ep8jo, r=Dylan-DPC

@rustbot label -E-needs-bisection

[steffahn]

So that’s likely #70793 and #83629. Let me tag @the8472 who might be more familiar with the code at hand since they were involved with both PRs :-)

[steffahn]

I’m not sure if I’m reading the PR description of #83629 correctly as in that this leak might be intentional? (If it is intentional, I haven’t understood the rationale yet though…)

In the default implementation the source and the destination vec are separate objects, so they get dropped separately. Here they share an allocation and the latter only exists as a pointer into the former. So if dropping the former panics then this fix will leak more items than the default implementation would.

I mean… who knows, maybe this is talking about something entirely different than what this issue is about ^^

[Voultapher]

Looking at the code, this leak seems relatively easy to avoid. Assuming that dropping theNew elements while unwinding will itself not panic. I'm guessing the comment you reference relates to something else.

Also any idea why and how Old(55) gets dropped?

[SkiFire13]

The relevant piece of code seems to be this one:

rust/library/alloc/src/vec/in_place_collect.rs

Lines 201 to 203 in cedd26b

	src.forget_allocation_drop_remaining();
	let vec = unsafe { Vec::from_raw_parts(dst_buf, len, cap) };

Where forget_allocation_drop_remaining is defined here:

rust/library/alloc/src/vec/into_iter.rs

Lines 110 to 124 in cedd26b

	pub(super) fn forget_allocation_drop_remaining(&mut self) {
	let remaining = self.as_raw_mut_slice();
	// overwrite the individual fields instead of creating a new
	// struct and then overwriting &mut self.
	// this creates less assembly
	self.cap = 0;
	self.buf = unsafe { NonNull::new_unchecked(RawVec::NEW.ptr()) };
	self.ptr = self.buf.as_ptr();
	self.end = self.buf.as_ptr();
	unsafe {
	ptr::drop_in_place(remaining);
	}
	}

So what happens is:

• all the elements to collect have been written
• however there could be more element in the original Vec/vec::IntoIter
• moreover we want to give ownership of the allocation to the new Vec
• so we remove any reference to the original allocation from the vec::IntoIter
• and we drop the remaining elements
• finally, we create the Vec that logically owns both the New and the allocation

The problem is that a panic can occur while dropping the remaining elements, and in that case we didn't yet create the final Vec, so nothing is responsible for dropping the allocation (which was already removed from the vec::IntoIter) and the New`s.

The simpliest fix would be to create the Vec before dropping the remaining elements, however I'm not sure if that's correct with respect to aliasing/stacked borrows. For example if Vec is ever implemented using Box internally then it would claim unique access to the allocation, which invalidates the pointer used to drop the remaining elements. I think the most robust solution would be a drop guard that frees the allocation and the News on drop (and is forgotten before creating the actual Vec that's returned).

Also any idea why and how Old(55) gets dropped?

Dropping the old elements is done with ptr::drop_in_place which will try to drop all the elements even if one panics while being dropped. If another element's destructor panics then that's a panic while panicking and the program aborts.

[the8472]

Then [4] is being dropped, but honestly I don't really understand why. My understanding is that ptr::drop_in_place(remaining) should unwind. If anyone can explain this, please do so.

drop_in_place keeps going and then rethrows the panic. That's because it replicates the default drop behavior for slices.

I’m not sure if I’m reading the PR description of #83629 correctly as in that this leak might be intentional? (If it is intentional, I haven’t understood the rationale yet though…)

Yeah, to fix the double-drop in #83618, this was the simplest solution that didn't require any extra parts. And if you're panicing in drop then leaks are allowed behavior. Avoiding them is more a QoI thing.

[the8472]

The simpliest fix would be to create the Vec before dropping the remaining elements, however I'm not sure if that's correct with respect to aliasing/stacked borrows.

A bigger concern imo is... well... panic-safety. If the Vec and the IntoIter exist at the same time then you need to be really sure that panics can only occur after the IntoIter has given up the allocation. If a panic occurs between materializing the Vec and before calling forget_allocation_drop_remaining then you get double-frees again.

[SkiFire13]

If a panic occurs between materializing the Vec and before calling forget_allocation_drop_remaining then you get double-frees again.

The idea was to create it right before calling forget_allocation_drop_remaining

[the8472]

That could work. At least I'm not seeing anything that would go wrong with that given current implementations. The question is whether it's worth it adding yet another unsafe wrinkle to this goldberg machine.

[Voultapher]

I think the issue will be type confusion. Which is what I initially looked for. If dropping those remaining Old elements panics, it would drop Olds as News. I think a simpel drop guard before forget_ should do the trick.

…

On 10. Sep 2022, at 11:36, the8472 ***@***.***> wrote:  That could work. At least I'm not seeing anything that would go wrong with that given current implementations. The question is whether it's worth it adding yet another unsafe wrinkle to this goldberg machine. — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you authored the thread.