Zip may call __iterator_get_unchecked twice with the same index

[SkiFire13]

Here __iterator_get_unchecked is called for potential side effects until self.index == self.a.size(), ignoring however that it could have already been called in next_back with those indexes.

rust/library/core/src/iter/adapters/zip.rs

Lines 200 to 208 in 0148b97

	} else if A::may_have_side_effect() && self.index < self.a.size() {
	let i = self.index;
	self.index += 1;
	// match the base implementation's potential side effects
	// SAFETY: we just checked that `i` < `self.a.len()`
	unsafe {
	self.a.__iterator_get_unchecked(i);
	}
	None

Playground link that demonstrates how this can be exploited to get two mutable references to the same data and cause an use-after-free bug.

[hameerabbasi]

Assigning P-critical as part of the WG-prioritization discussion on Zulip.

[the8472]

The gift that keeps on giving 🤣

Maybe it is time to get rid of TrustedRandomAccess as it exists today and replace it with a slightly safer (but still unsafe) variant? One that imposes the additional requirement on the caller that it must bring the iterator back into a safe state after it is done iterating.

The upside would be eliminating a lot of code in ZipImpl and enabling the same optimization for vec::IntoIter<T> where T: Drop and similar sources.
While the downside would be that external iteration (i.e. for loops and manual calls to next()) would cease to benefit from TrustedRandomAccess optimizations and only internal iteration methods (including for_each) would continue to do so.

[SkiFire13]

I don't know, I feel like that would just make more complex to upheld the invariants. IMO a good improvement over the current __iterator_get_unchecked would be separating forward and backward iteration, this way it becomes easier to keep track of the state and I think would also make it possible to implement them for vec::IntoIter<T> where T: Drop

[the8472]

I don't see how separating the forward and backward state would help with a drop implementation. The issue is that the source (IntoIter) currently does not have access to that state, instead the consumer drives the iteration by direct access through __iterator_get_unchecked and never informs the source about it.

[SkiFire13]

It would help because it allows the source iterator to keep track of its state by updating it when the method is called. Anyway, looks like someone already tried this approach back in 2016 and it resulted in worse optimizations, but maybe LLVM got better in the meantime, or maybe that implementation could have been better.

Anyway I don't think this is the right place to discuss this, a topic on zulip would probably be better.

[the8472]

a topic on zulip would probably be better.

https://rust-lang.zulipchat.com/#narrow/stream/219381-t-libs/topic/Improving.20TrustedRandomAccess.20and.20its.20Zip.20specialization/near/227088066