Double free in Vec::dedup_by when T's drop panics

[Qwaz]

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

Lines 1608 to 1637 in d8af907

	let mut gap = FillGapOnDrop { read: 1, write: 1, vec: self };
	let ptr = gap.vec.as_mut_ptr();
	/* Drop items while going through Vec, it should be more efficient than
	* doing slice partition_dedup + truncate */
	/* SAFETY: Because of the invariant, read_ptr, prev_ptr and write_ptr
	* are always in-bounds and read_ptr never aliases prev_ptr */
	unsafe {
	while gap.read < len {
	let read_ptr = ptr.add(gap.read);
	let prev_ptr = ptr.add(gap.write.wrapping_sub(1));
	if same_bucket(&mut *read_ptr, &mut *prev_ptr) {
	/* We have found duplicate, drop it in-place */
	ptr::drop_in_place(read_ptr);
	} else {
	let write_ptr = ptr.add(gap.write);
	/* Because `read_ptr` can be equal to `write_ptr`, we either
	* have to use `copy` or conditional `copy_nonoverlapping`.
	* Looks like the first option is faster. */
	ptr::copy(read_ptr, write_ptr, 1);
	/* We have filled that place, so go further */
	gap.write += 1;
	}
	gap.read += 1;
	}

gap.read is not updated (line 1636) when drop_in_place (line 1623) panics. This lets FillGapOnDrop's Drop implementation to retain the already dropped element.

The bug was introduced in #82191 and affects stable Rust versions >= 1.52. Here is the playground link that demonstrates the double free without using unsafe Rust code.

Meta

rustc --version --verbose:

rustc 1.52.1 (9bc8c42bb 2021-05-09)
binary: rustc
commit-hash: 9bc8c42bb2f19e745a63f3445f1ac248fb015e53
commit-date: 2021-05-09
host: x86_64-unknown-linux-gnu
release: 1.52.1
LLVM version: 12.0.0

[steffahn]

@rustbot label regression-from-stable-to-stable

[hameerabbasi]

Assigning P-critical as discussed by WG-prioritization on Zulip and removing I-prioritize.

@rustbot modify labels +P-critical -I-prioritize

[SkiFire13]

Interestingly there was a test for this, but it is wrong.

rust/library/alloc/tests/vec.rs

Lines 2234 to 2285 in d8af907

	#[test]
	fn test_vec_dedup_panicking() {
	#[derive(Debug)]
	struct Panic {
	drop_counter: &'static AtomicU32,
	value: bool,
	index: usize,
	}
	impl PartialEq for Panic {
	fn eq(&self, other: &Self) -> bool {
	self.value == other.value
	}
	}
	impl Drop for Panic {
	fn drop(&mut self) {
	let x = self.drop_counter.fetch_add(1, Ordering::SeqCst);
	assert!(x != 4);
	}
	}
	static DROP_COUNTER: AtomicU32 = AtomicU32::new(0);
	let expected = [
	Panic { drop_counter: &DROP_COUNTER, value: false, index: 0 },
	Panic { drop_counter: &DROP_COUNTER, value: false, index: 5 },
	Panic { drop_counter: &DROP_COUNTER, value: true, index: 6 },
	Panic { drop_counter: &DROP_COUNTER, value: true, index: 7 },
	];
	let mut vec = vec![
	Panic { drop_counter: &DROP_COUNTER, value: false, index: 0 },
	// these elements get deduplicated
	Panic { drop_counter: &DROP_COUNTER, value: false, index: 1 },
	Panic { drop_counter: &DROP_COUNTER, value: false, index: 2 },
	Panic { drop_counter: &DROP_COUNTER, value: false, index: 3 },
	Panic { drop_counter: &DROP_COUNTER, value: false, index: 4 },
	// here it panics
	Panic { drop_counter: &DROP_COUNTER, value: false, index: 5 },
	Panic { drop_counter: &DROP_COUNTER, value: true, index: 6 },
	Panic { drop_counter: &DROP_COUNTER, value: true, index: 7 },
	];
	let _ = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
	vec.dedup();
	}));
	let ok = vec.iter().zip(expected.iter()).all(|(x, y)| x.index == y.index);
	if !ok {
	panic!("expected: {:?}\ngot: {:?}\n", expected, vec);
	}
	}

The expected vec contains the index=5, even though it is the item that panics in its drop implementation. I guess the author of this test thought that fetch_add returned the new value instead of the old value?

[Soveu]

Learning about a double-free I introduced, a year later... 👀
And honestly, I can clearly remember that when the test was first written, it caught the bug, but I just assumed it was an off-by-one error in the testing code itself, yikes