search

rust-lang / miri

An interpreter for Rust's mid-level intermediate representation
Apache License 2.0
4.65k stars 348 forks source link

Randomize thread unblocking operation #4032

Open tiif opened 2 weeks ago

tiif commented 2 weeks ago

In eventfd, we would unblock multiple threads in a deterministic sequence. In epoll, we always choose the thread id from the end of the list if multiple threads are blocked on the same epoll instance. We could randomize these operation depending on the seed.

Related FIXME: https://github.com/rust-lang/miri/blob/9d9da34f49562bbe78e09213ee6e8aa9b9db1cce/src/shims/unix/linux/eventfd.rs#L226-L229 https://github.com/rust-lang/miri/blob/9d9da34f49562bbe78e09213ee6e8aa9b9db1cce/src/shims/unix/linux/epoll.rs#L549-L555

Side note: Blocking socketpair #3665 would need to use this too.

tiif commented 2 weeks ago

@rustbot label +C-enhancement +A-concurrency

@rustbot claim

oli-obk commented 2 weeks ago

Do real systems randomize? It may cause starvation, which is usually attempted to be avoided by having some order

RalfJung commented 2 weeks ago

Generally we should be unblocking the thread that had waited the longest. Not sure what real systems do here, maybe we should ping some tokio folks who might know?

RalfJung commented 2 weeks ago

@rustbot label +A-shims

oli-obk commented 2 weeks ago

I wonder if the rules here are just the usual scheduler rules. Because at least on linux, according to https://www.man7.org/linux/man-pages/man7/sched.7.html the answer seems to be "unblock all threads and run them according to the normal scheduler rules"

tiif commented 2 weeks ago

For epoll (edge-triggered), since it can only wake up one thread, I think which thread the kernel choose to unblock might be implementation specific (I suspect the kernel has a wakeup queue too).

For eventfd, since we are waking up all threads, would it makes sense to randomize the unblocking sequence, while still prioritizing threads that have been waiting the longest?

I am still not sure what is the behaviour of actual system, though.

oli-obk commented 2 weeks ago

If we can pull out the "pick next thread to resume from a list of thread ids" logic into a function, we can reuse it here. I'd like them to be the same logic, so if we change one, the other changes, too

discord9 commented 1 week ago

It would seems for epoll the order of waking up depend on how scheduler decide? Correct me if I'm wrong, but seems here use schedule_hrtimeout_range which wait a given time and may return early if a signal is delivered to the current task(which is determined by scheduler?). eventpoll itself also have a wait queue but it doesn't seem to affect unblocking order it seems?