When the RTC is adjusted, reevaluate sleep times that are based on the RTC

[vangyzen]

Summary

POSIX says this about sem_timedwait(3):

The timeout shall expire when the absolute time
specified by abstime passes, as measured by the clock
on which timeouts are based (that is, when the value
of that clock equals or exceeds abstime), ...

It says essentially the same about:

pthread_cond_timedwait(3)
pthread_mutex_timedlock(3)
pthread_rwlock_timedrdlock(3)
pthread_rwlock_timedwrlock(3)

When the real-time clock is adjusted, such as by clock_settime(3),
wake any sleeping threads whose sleep duration is based on that clock.
The sleep function will return a special errno that tells the caller
to reevaluate its sleep duration based on the new value of the clock.

Adopt the new POSIX-compliant behavior in the functions mentioned above
(and sem_clockwait_np(3)) when using CLOCK_REALTIME. Other functions
might need to do likewise.

[vangyzen]

Remove dead code from a different approach

[kib]

The approach might be fine, but I see at least one rough race which is not handled. Suppose that a thread calculated timeout based on the absolute time, but not yet managed to actually sleep, as seen by being owned by sq. Then, if the clock is set before the thread is finally put on sq, it will not be woken up.

sys/kern/kern_tc.c

1311

Why do you need enqueue_timeout() ? I do not quite understand why cannot you directly call sleepq_remove_matching() in the current context.

sys/kern/subr_sleepqueue.c

1113

I suggest to re-factor this code fragment from sleepq_broadcast() and reuse the call.

1126

It is enough to do one kick_proc0() after waking up all chains.

[vangyzen]

@kib: Well spotted. I'm still considering this race. For now, that's why I have the 10ms timeout taskqueue. That's an ugly hack that will probably be insufficient in some cases.

I'm currently considering a global rmlock. Sleepers will rlock it before reading the RTC. _sleep() will runlock it after sleepq_add if PRTCLK is passed. tc_setclock will wlock it. The taskqueue will not be used.

I don't like the asymmetry of the locking, but it's fairly reasonable, and it's the best idea I've had. I would appreciate your thoughts.

sys/kern/subr_sleepqueue.c

1113

Good idea. Done.

1126

I was wondering about that. Thanks.

[vangyzen]

Code review feedback

Rename sleepq_remove_matching() to sleepq_chains_remove_matching().
The former name is used for a new function that loops over threads
in a queue. It is refactored out of sleepq_broadcast() and called
from that function and sleepq_chains_remove_matching().

Kick proc0 once after waking up all chains.

[kib]

In D9791#202590, @vangyzen wrote:

I don't like the asymmetry of the locking, but it's fairly reasonable, and it's the best idea I've had. I would appreciate your thoughts.

Suppose that we have some 'generation' for the system clock value, which is incremented on each setclock(). Also suppose that we added some field td_umtx_agen to struct thread and store there the clock generation we used to calculate timeout for msleep(). Then sleepq code can refuse to put the thread to sleep if td_umtx_agen != current setclock generation.

The check in sleepq must happens quite late, somewhere in sleepq_switch() similar to TDF_TIMEOUT recheck. Then, either we note the generation bump on our own, or the setclock() wakeup would note that we are on sleepqueue and wakes us. This basically means that sleepqueue chain lock is used as interlock.

[vangyzen]

I like your idea. This is cleaner than the rmlock.

In D9791#202610, @kib wrote:

Then sleepq code can refuse to put the thread to sleep if td_umtx_agen != current setclock generation.

Since this read of the clock generation is not synchronized with the increment in setclock(), we would still need the setclock() wakeup. So, is this an optimization to avoid an unnecessary sleep (and immediate wake)?

The check in sleepq must happens quite late, somewhere in sleepq_switch() similar to TDF_TIMEOUT recheck.

That makes sense, but why do you say it? If this is an optimization, this would make it most optimal. Is that the reason?

[kib]

In D9791#202644, @vangyzen wrote:

I like your idea. This is cleaner than the rmlock.

In D9791#202610, @kib wrote:

Then sleepq code can refuse to put the thread to sleep if td_umtx_agen != current setclock generation.

Since this read of the clock generation is not synchronized with the increment in setclock(), we would still need the setclock() wakeup. So, is this an optimization to avoid an unnecessary sleep (and immediate wake)?

Sure we need to do the wakeup loop, same as it is done in the current patch. What I described is not an optimization, it is a measure to avoid the situation which I described in the first review message, namely, the problem where a thread calculates timeout with old clock, but does not make to sleep fast enough to be woken after setclock().

The check in sleepq must happens quite late, somewhere in sleepq_switch() similar to TDF_TIMEOUT recheck.

That makes sense, but why do you say it? If this is an optimization, this would make it most optimal. Is that the reason?

No, this is the 'interlock' to avoid lost wakeup, continued.

[vangyzen]

My apologies. That's blindingly obvious now. (Maybe I shouldn't work on this at home while my kids are around...)

[vangyzen]

Add an rtc_generation and use it to close the race,
instead of the 10ms timeout taskqueue.

Add test code (to be removed).

[vangyzen]

I think I can remove PRTCLK and TDF_SLEEPRTC, and just use td_rtcgen. I'm working on that now.

sys/kern/kern_umtx.c

839

This will be removed before commit.

[vangyzen]

• Remove PRTCLK and TDF_SLEEPRTC; just use td_rtcgen
• Remove test code
• Update locking comment
• Avoid superfluous clock re-read when not using RTC

[vangyzen]

(previous update included unrelated changes due to stale master branch)

[kib]

Please commit the grammar fixes for comments in subr_sleepqueue.c.

sys/kern/kern_synch.c

218 ↗

(On Diff #25826)

I think that the changes to _sleep() can be avoided at all. If we set td_rtcgen before msleep() call in umtxq_sleep() and get td_rtcgen == 0 after sleep, we are guaranteed that the thread was either aborted in sleeping_on_old_rtc(), or sleepq_switch() refused to put it on sleepq. So you can just test for td_rtcgen == 0 in umtxq_sleep() instead of ERELOOKUP.

sys/kern/kern_tc.c

1496

I think it is fine to increment generation in tc_setclock, after the tc_setclock_mtx spinlock is unlocked, right before remove_matching().

Also, the increment must be slightly more advanced, to avoid overflowing the value into zero.

sys/kern/kern_umtx.c

779

() are not needed.

[vangyzen]

sys/kern/kern_synch.c

218 ↗

(On Diff #25826)

I considered this, but I liked the fact that the result was communicated entirely by the return value. However, after a fresh look, I realize that testing td_rtcgen is fairly clean, especially since callers are already manipulating it.

I have reverted all changes in this file. (I hope Phabricator still shows these comments...)

sys/kern/kern_tc.c

1496

I agree about the location.

I figured overflow wouldn't happen in practice, but guaranteeing it is easy enough, so I will.

sys/kern/kern_umtx.c

779

True, but I like them. However, style(9) discourages them, so I'll remove them.

[vangyzen]

Revert all changes in kern_synch.c. Callers will test td_rtcgen instead
of the *sleep return value. They're already maintaining that field
anyway, so this is clean enough.

Bump rtc_generation in tc_setclock() instead of tc_windup().

Remove superfluous parens to adhere to style(9).

[kib]

sys/kern/kern_tc.c

1277

Blank line is not needed.

sys/kern/kern_umtx.c

850

I understand why this reading of rtc_generation needs acquire semantic: we ensure that if we see updated rtc_generation, then we also see the updated timehands.

But I do not quite see why other rtc_generation reads, in particular, in sleeping_on_old_rtc() and in sleepq_switch(), need the acquire. sleeping_on_old_rtc() happens in the same thread that incremented the variable. sleepq_switch() only needs the value of the variable, it does not order its read with other happenings in tc_windup() which did release write. Could you, please, explain your use of _acq there ?

884

Too many blank lines.

sys/kern/subr_sleepqueue.c

597

As I asked before, please commit the style and comment grammar fixes now.

935

I would prefer to remove special case for matcher == NULL and instead provided a trivial matcher always returning true there.

1118

No need in {}.

sys/sys/proc.h

151

This is too cryptic. My understanding is that owner of the field if curthread when running. When curthread is sleeping, the field is protected by the thread lock. I am not sure how to explain this shortly in the annotations, might be a longer comment in more appropriate place would be less confusing.

[kib]

sys/kern/subr_sleepqueue.c

566

I think this is a right place to provide some reasoning why the code correctly covers the race where tc_windup()->sleeping_on_old_rtc() missed us. Some note about sleepq lock used as interlock there is due, IMO.

[vangyzen]

sys/kern/kern_umtx.c

850

There is no good reason. I'm embarrassed to say, it was absent-minded. Of course, you're right that only this function needs the acquire semantic.

sys/kern/subr_sleepqueue.c

566

Will do.

1118

True, but I very strongly prefer using such braces.

sys/sys/proc.h

151

Yes, this deserves more explanation.

[vangyzen]

I will write the documentation in my next upload.

[vangyzen]

POSIX compliance; code review feedback

POSIX says that only absolute sleeps are affected by RTC adjustments.
Relative sleeps are immune. Make it so.

Use atomic acquire only where needed.

Change sleepq_remove_matching() to require a predicate.
Provide a constant function when called from sleepq_broadcast().

Remove unstylish blank lines.

[vangyzen]

Add documentation in all interesting places.

[vangyzen]

@kib, thank you for your thorough review and very helpful comments. When you started, the code was essentially just an example of an approach and not ready for such a review, so I realize that you have already spent a lot of time on it. I believe it is now ready, if you have the time.

[vangyzen]

Note to self: Update the description.

[kib]

I think that the code is fine as is. We might work on improving the comment in sleepq_switch() after the code is landed.

I suggest asking pho@ to test this, he would probably need specific instructions and might be a specific test programs from you. I also added jhb@ to the reviewers.

sys/kern/kern_tc.c

1274

By finding the thread on a sleepqueue and holding the lock ...

sys/kern/subr_sleepqueue.c

572

I think it is a prereq for the race that Ts is not put to sleep yet. In fact, there is very fine difference between TD_ON_SLEEPQ() which means that sleepq_add() was done, and TD_IS_SLEEPING(), which mean that the thread is really asleep. TD_IS_SLEEPING() condition is set as the last action in sleepq_switch() (this function) right before the call to mi_switch().

When I asked for the comment, I mean just mention this race and also to explain how the use of sleep chain spinlocks makes the td_rtcgen accesses correctly synchronized.

914

Style(9) requires a blank line after the '{' if no local vars is defined.

[jhb]

sys/kern/kern_tc.c

1311

My understanding of style(9) would require a blank line before the comment.

[vangyzen]

sys/kern/kern_tc.c

1274

That sounds better.

1311

I couldn't find the reference, but I like an extra line here anyway.

[vangyzen]

Polish comments; improve style(9).

Also merge from master so @pho can apply the patch to master.