Lost wakeups in threadpool

[carllerche]

It has been reported (rust-lang/futures-rs#1170) that there have been lost wake ups.

Downgrading to threadpool 0.1.4 reportedly solves the problem. #459 is the only meaningful change.

[carllerche]

After thinking a bunch about the description of the problem, I don't believe that the bug being fixed is real. From the PR:

When unparking a worker thread, we do the following steps:

1. Try transitioning IDLE -> NOTIFY.
2. Lock the mutex.
3. Try transitioning SLEEP -> NOTIFY and wakeup on success.

The problem occurs if the thread transitions from SLEEP to IDLE between steps 1 and 2. In that case, step 3 will fail to transition and simply return from unpark.

However, this case would not be a problem as the sleeping thread that transitions from SLEEP -> IDLE will establish a happens before relationship with the notifying thread (due to the SeqCst ordering). So, when the sleeping thread wakes up, it is guaranteed to see the change that the notifying thread is notifying for. This requires SeqCst and would not be true w/ acquire / release.

That said, that doesn't mean the PR introduced a bug...

[carllerche]

This line is suspicious to me now... it isn't acquiring anything from notifier threads...

It probably should be a swap.

Edit: This line too:

tokio/tokio-threadpool/src/park/default_park.rs

Line 138 in 0490280

self.state.store(IDLE, SeqCst);

This line is suspicious to me now... it isn't acquiring anything from notifier threads...

Well, it's consuming the notification and going back to the IDLE state. The worst that could happen is a spurious wakeup. std::thread::park has the same store operation.

Edit: This line too:

std::thread::park uses a cmpxchg operation here, but again - the worst case scenario is just a spurious wakeup.

[carllerche]

@stjepang that isn't the issue. The issue is that there is no acquire ordering established with this line.

Acquire is needed to get access to the change that the unpark thread is notifying for.

[carllerche]

That said, on x86 assuming mfence is used it would be ok...

[jsgf]

This code should be arch-independent which makes it hard to analyze. On x86 locked stores are totally ordered WRT locked stores and loads from the same location, so it's reasonably easy to get right.

I'm assuming that because everything is SeqCst then that also applies to other architectures with weaker ordering rules.

(The heavy use of compare_and_swap makes me wonder whether the "check state outside of the lock" is actually worthwhile - how often do the "park when already notified" and "unpark while not sleeping" cases get hit? Depending on how mutex is implemented, the cmpxchg might be more expensive, esp if the lock is not contended.)

[carllerche]

@jsgf I understand that it should be arch dependent... however, I'm trying to figure out if there currently is a bug on x86.

Either way, the issues pointed out here should be fixed.

[remexre]

Getting a possibly-relevant deadlock in https://github.com/remexre/garlichat ; cd garlichat && cargo run, the first character typed prints in the top region (as it should), but further characters are lost. (Note: the terminal is put into raw mode, so it's necessary to kill the garlichat process.)

eprintln!() shows the getch-ing thread receives additional characters on keypresses, but the event loop doesn't get woken up.

---

EDIT: unbounded_send is here, corresponding poll is here.

[carllerche]

I am debugging this case.

[carllerche]

It is looking like the issue in garlichat is not related :(

[hawkw]

I believe I have a potential reproduction for this issue: https://github.com/hawkw/tokio-deadlock-repro. I've written a simple program which spawns a task that sends numbers into an MPSC, and then repeatedly blocks on reading values out of the channel. After a varying number of calls to Runtime::block_on, this program will hang. This occurs with both the current master, and tokio 0.1.7.

I've tested this reproduction on macOS 10.12.6 with rustc 1.28.0.

[carllerche]

@stjepang Are you able to investigate this repro? ^^