sync: fix racy UnsafeCell access on a closed oneshot

[hawkw]

Motivation

Issue #4225 describes a potential race condition in the oneshot
channel in tokio-sync. The race occurs when the oneshot is closed, and
then a thread calls oneshot::Sender::send while another thread is
calling oneshot::Receiver::try_recv or awaiting the reciever. The call
to send puts the sent value in the cell. Then, it sets the
VALUE_SENT (completed) bit, returning a snapshot of the state. If the
state is closed, the sender takes the sent value back out of the cell.
Receiving from the channel also loads the state. The reciever first
checks if the channel is completed, and takes the value out of the cell
if the completed bit is set. This is racy, because if a call to recv
loads the state after the completed bit has been set, it will no longer
treat the channel as closed, and will try to take the value out of the
cell. This results in both threads accessing the cell concurrently.

Solution

This branch adds two loom tests reproducing the race, for try_recv
and for awaiting a Receiver. Both of these tests fail with a causality
violation when accessing the UnsafeCell on master.

I fixed the race condition by changing State::set_completed to not set
the VALUE_SENT bit if the CLOSED bit has already been set. This way,
if the channel is closed before send is called, we won't set the bit
that tells the receiver that it's okay to access the UnsafeCell, and
we the sender can take the value back out without the risk of the
receiver also concurrently accessing the UnsafeCell.

This required changing State::set_completed from a simple fetch-or to
a compare-and-swap loop, which is slightly a bummer, as it's less
efficient than a single fetch-or. However, as far as I can tell,
changing this to a CAS loop is the only solution to the race that
doesn't also change the oneshot's behavior. We currently have tests
asserting that if the channel is closed after a value is sent, the
value is still received. A simpler solution to this problem would be
changing poll_recv and try_recv to check if the channel is closed
first, and only check if the channel is completed and take the value
out if it is not closed. This fixes the race, since the receiver will no
longer try to access the UnsafeCell if the channel has been closed.
But, this would break the existing tests asserting that calling close
after a value has been sent still results in the value being received.
Changing that behavior seems undesirable, so I thought this was worth
the CAS loop.

Fixes: #4225

[hawkw]

I also considered writing this as

Suggested change

	loop {
	if State(state).is_closed() {
	break;
	}
	while !State(state).is_closed() {

but i had a vague memory of @carllerche saying that he doesn't like the use of while loops for compare-and-swap loops... :)

[Darksonn]

I think the way it's written here with a loop is perfectly readable, so let's just keep it.

[Darksonn]

The oneshot code is honestly pretty bad now that I look at it - there are very few safety justifications in the code. What you are doing here sounds reasonable, but I'd need to read the entire implementation to be confident that it solves the problem.

[Darksonn]

I think the way it's written here with a loop is perfectly readable, so let's just keep it.

[hawkw]

The oneshot code is honestly pretty bad now that I look at it - there are very few safety justifications in the code.

Yeah, I was also thinking about trying to clean up more of the existing implementation (maybe in a follow-up...). But, I'm pretty confident that this change fixes the specific crash in question.

[Darksonn]

This seems safer.

Suggested change

	let mut state = cell.load(Ordering::Relaxed);
	let mut state = cell.load(Ordering::Acquire);

[hawkw]

I don't think it's necessary; the compare_exchange has an Acquire failure ordering, so when we actually go to set the value, we will always perform an Acquire operation, and if the initial Relaxed load is stale, the CAS will fail, and we'll loop again with a value that was accessed with an Acquire ordering. So, making the initial load Relaxed really just serves to avoid an unnecessary Acquire in the case that we're the only thread writing to the state; if it's contended and the Relaxed load is stale, we will always perform an Acquire on subsequent iterations.

Other CAS loops elsewhere in Tokio follow a similar pattern:

tokio/tokio/src/time/driver/entry.rs

Lines 167 to 192 in 03969cd

	// Quick initial debug check to see if the timer is already fired. Since
	// firing the timer can only happen with the driver lock held, we know
	// we shouldn't be able to "miss" a transition to a fired state, even
	// with relaxed ordering.
	let mut cur_state = self.state.load(Ordering::Relaxed);
	loop {
	debug_assert!(cur_state < STATE_MIN_VALUE);
	if cur_state > not_after {
	break Err(cur_state);
	}
	match self.state.compare_exchange(
	cur_state,
	STATE_PENDING_FIRE,
	Ordering::AcqRel,
	Ordering::Acquire,
	) {
	Ok(_) => {
	break Ok(());
	}
	Err(actual_state) => {
	cur_state = actual_state;
	}
	}

However, I'm happy to change this if you prefer.

[hawkw]

As a note, I can run my repro from #4225 (comment) with this branch for over 40 minutes without seeing any segfaults or mangled strings.

[hawkw]

The oneshot code is honestly pretty bad now that I look at it - there are very few safety justifications in the code.

Yeah, I was also thinking about trying to clean up more of the existing implementation (maybe in a follow-up...). But, I'm pretty confident that this change fixes the specific crash in question.

#4229 should help make some of the oneshot implementation's invariants a bit clearer, I hope!

[cynecx]

I think loom has partial support for fences iiuc (tokio-rs/loom#220), so technically this comment isn't correct anymore :D.

[hawkw]

Yeah, I think there might be a couple other places in Tokio where we also can implement some things nicer now that loom supports fences. I didn't want to actually change that aspect of the implementation in the bugfix branch, though. Might be worth doing in a subsequent one!

[Arnavion]

Is there any plan to backport this to 0.1.x ?

[Darksonn]

We don't have any plans, no.

[Arnavion]

Okay, thanks.