epoll-wait induces too much synchronization

[RalfJung]

Let's consider the following testcase:

• We have two pipes, A and B, and some global static mut S
• The main thead sets up an epoll for both of these pipes' read ends
• We spawn a sub-thread that writes to pipe A, then mutates S, then writes to pipe B
• The main thread yields, and we have miri-preemption-rate=0, so this will fully run the sub-thread
• The main thread waits on both pipes with epoll, but only wants to receive a single event
• The main thread asserts that it was informed about pipe A, not B
• Then the main thread reads from S

This should report UB due to a data race.

However, I think what will happen here is that the main thread will receive the notification for pipe A, but because we call acquire_clock on the ready_list.clock, we acquire the clock for all events. This means we miss the UB as the main thread read of S seems to happen-after the sub-thread write of S.

[RalfJung]

@FrankReh any chance you could try to turn this test case sketch into code? :)

[FrankReh]

Yes, there's a good chance. Doing it means I learn more. But you usually are very precise so I want to double-check your concern: in your descriptions and at the end of the problem description here, you say "we acquire the clock for all events". I don't think it is true that the system now groups all the machine's events into one ready_list. The ready_list is per epoll, so we acquire the clock from all the events that were added to that epoll. But if that is a problem, it should be possible to make the clock per event of interest, just moving the clock logic into lower iterations.

[RalfJung]

Yes, "all events for this epoll instance ready list" is what I meant.

[FrankReh]

I agree with your concern now. I had overlooked the impact of the maxevents argument.

[tiif]

On a related note, I had a concern on release_clock here #3928 (comment). The problem that I am considering is we might accidentally release clock even though the thread is not unblocked. From what I understand, we want to synchronise between operation that actually unblocked thread and the unblock callback.

I have tried generating test case for this, but it doesn't work out. So it might not be a valid concern after all. :)

What I have tried is triggering check_and_update_readiness without unblocking any thread, then let another thread unblock due to timeout instead of actually receiving epoll notfication.

[FrankReh]

On a related note, I had a concern on release_clock here #3928 (comment). The problem that I am considering is we might accidentally release clock even though the thread is not unblocked. From what I understand, we want to synchronise between operation that actually unblocked thread and the unblock callback.

I will let you and @RalfJung work that concern out as I already responded to your comment and didn't see a further clarification. To state my confusion to your question another way, you use "release clock" as a verb and I take it as a noun: the release clock, like the release option to an atomic operation. (Just background to my earlier comment and I didn't want you to feel ignored on your initial comment or this one.)

[FrankReh]

@RalfJung I have the test case you sketched out and of course it doesn't report UB. But I agree it should. Sigh... I'll create a PR.

Is it the norm to put a test that passes into the fail_deps set when it is supposed to fail? Or is there a marker that says this line should have triggered a UB?

[tiif]

(Just background to my earlier comment and I didn't want you to feel ignored on your initial comment or this one.)

Yup I understand, thanks for the response :) Yea this is more like a concern that I am not sure if it is even valid, I didn't reply because I am waiting for someone to give an answer.

[RalfJung]

The problem that I am considering is we might accidentally release clock even though the thread is not unblocked.

I don't see the problem. If thread A triggers an event that is observed by thread B, that should establish a happens-before link, i.e. the release clock of thread A should be acquired by thread B. This is true even if thread B wasn't blocked. Consider that we have clocks for socketpair and eventfd even though those don't even support blocking yet!

[RalfJung]

Is it the norm to put a test that passes into the fail_deps set when it is supposed to fail? Or is there a marker that says this line should have triggered a UB?

Yes please put this in tests/fail-dep/libc/, and add a //~ERROR annotation in the line where the UB should be. Check any of the other tests to see what this looks like.

[tiif]

@RalfJung also I wonder if the test case should actually report data race. This is what I imagine happening

Subthread:
1.1 Write to pipe A
1.2 Mutates S
1.3 Write to pipe B

Main thread:
2.1 epoll_wait and get unblocked by event generated by pipe A
2.2 Read from S

Under miri-preemption-rate=0 and the assumption of subthread is fully run, 2.2 read from S seems to always happens after 1.2 Mutates S because
1.1 must happen right before 1.2, 1.2 must happen right before 1.3 (because subthread is fully run)
2.1 must happen before 2.2
2.1 must happen after 1.1 (1.1 provides notification, 2.1 receives notification)
Hence, 2.2 must happen after 1.2.

I am not sure what have I missed here, also sorry for the long post.

[RalfJung]

seems to always happens after

"happen after" has a more complicated definition than what you are using here. Please find some online tutorial on the C++11 memory model, data races, relaxed accesses, release-acquire synchronization and all that... that's really beyond the scope of this issue to explain it. I can recommend https://marabos.nl/atomics/ but it's a full book, so it'll take a while to read through it all. ;)

[FrankReh]

Is there a way I can force the clock to advance in the sub thread between the pipe write and the static write? I have changed the plumbing of the epoll clock sync and it should now cause the test to report UB but it doesn’t. It only reports UB if I comment out any part of the new clock sync chain.

I don’t think I should have to artificially move the clock forward but I can’t think of what else to cause this. I could try to print out the clocks to see if that sheds light on what’s going on.

I understand my own code or test code is the most suspect. Just wondering if someone knows a way to force the clock forward beyond writing to a static.

[RalfJung]

Calling release_clock does move the clock forwards.