Back out the following revisions on behalf of core:

sys/sys/lwp.h: revision 1.228
sys/sys/pipe.h: revision 1.40
sys/kern/uipc_socket.c: revision 1.306
sys/kern/kern_sleepq.c: revision 1.84
sys/rump/librump/rumpkern/locks_up.c: revision 1.13
sys/kern/sys_pipe.c: revision 1.165
usr.bin/fstat/fstat.c: revision 1.119
sys/rump/librump/rumpkern/locks.c: revision 1.87
sys/ddb/db_xxx.c: revision 1.78
sys/ddb/db_command.c: revision 1.187
sys/sys/condvar.h: revision 1.18
sys/ddb/db_interface.h: revision 1.42
sys/sys/socketvar.h: revision 1.166
sys/kern/uipc_syscalls.c: revision 1.209
sys/kern/kern_condvar.c: revision 1.60

Add cv_fdrestart() [...]
Use cv_fdrestart() to implement fo_restart.
Simplify/streamline pipes a little bit [...]

This changes have caused regressions and need to be debugged.
The cv_fdrestart() addition needs more discussion.

kern_condvar.c: Sort includes. No functional change intended.

sys/lwp.h: Nix sys/syncobj.h dependency.

Remove it in ddb/db_syncobj.h too.

New sys/wchan.h defines wchan_t so that users need not pull in
sys/syncobj.h to get it.

Sprinkle #include <sys/syncobj.h> in .c files where it is now needed.

Add cv_fdrestart() (better name suggestions welcome):

Like cv_broadcast(), but make any LWPs that share the same file descriptor
table as the caller return ERESTART when resuming. Used to dislodge LWPs
waiting for I/O that prevent a file descriptor from being closed, without
upsetting access to the file (not descriptor) made from another direction.

Comments.

Ensure that an LWP that has taken a legitimate wakeup never produces an
error code from sleepq_block(). Then, it's possible to make cv_signal()
work as expected and only ever wake a singular LWP.

Eliminate l->l_biglocks. Originally I think it had a use but these days a
local variable will do.

- Simplify how priority boost for blocking in kernel is handled. Rather
than setting it up at each site where we block, make it a property of
syncobj_t. Then, do not hang onto the priority boost until userret(),
drop it as soon as the LWP is out of the run queue and onto a CPU.
Holding onto it longer is of questionable benefit.

- This allows two members of lwp_t to be deleted, and mi_userret() to be
simplified a lot (next step: trim it down to a single conditional).

- While here, constify syncobj_t and de-inline a bunch of small functions
like lwp_lock() which turn out not to be small after all (I don't know
why, but atomic_*_relaxed() seem to provoke a compiler shitfit above and
beyond what volatile does).

kern: New struct syncobj::sobj_name member for diagnostics.

XXX potential kernel ABI change -- not sure any modules actually use
struct syncobj but it's hard to rule that out because sys/syncobj.h
leaks into sys/lwp.h

sleepq(9): Pass syncobj through to sleepq_block.

Previously the usage pattern was:

sleepq_enter(sq, l, lock); // locks l
...
sleepq_enqueue(sq, ..., sobj, ...); // assumes l locked, sets l_syncobj
... (*)
sleepq_block(...); // unlocks l

As long as l remains locked from sleepq_enter to sleepq_block,
l_syncobj is stable, and sleepq_block uses it via ktrcsw to determine
whether the sleep is on a mutex in order to avoid creating ktrace
context-switch records (which involves allocation which is forbidden
in softint context, while taking and even sleeping for a mutex is
allowed).

However, in turnstile_block, the logic at (*) also involves
turnstile_lendpri, which sometimes unlocks and relocks l. At that
point, another thread can swoop in and sleepq_remove l, which sets
l_syncobj to sched_syncobj. If that happens, ktrcsw does what is
forbidden -- tries to allocate a ktrace record for the context
switch.

As an optimization, sleepq_block or turnstile_block could stop early
if it detects that l_syncobj doesn't match -- we've already been
requested to wake up at this point so there's no need to mi_switch.
(And then it would be unnecessary to pass the syncobj through
sleepq_block, because l_syncobj would remain stable.) But I'll leave
that to another change.

Reported-by: syzbot+8b9d7b066c32dbcdc63b@syzkaller.appspotmail.com

PR/55664: Ruslan Nikolaev: Split out sleepq guts and turnstiles not used
in rump into a separate header file. Add a sleepq_destroy() empty hook.

branches: 1.52.2;
Remove timedwaitclock.

This did not fix the bug I hoped it would fix in futex, and needs
more design thought. Might redo it somewhat differently later.

New timedwaitclock_setup.

C99 initializers would have been nice, but part of the struct is
explicit parameters and part of the struct is implicit state, and
-Wmissing-field-initializers can't discriminate between them
(although for some reason it doesn't always fire!).

Instead, just do:

struct timedwaitclock T;

timedwaitclock_setup(&T, timeout, clockid, flags, epsilon);
while (...) {
error = timedwaitclock_begin(&T, &timo);
if (error)
...
error = waitwhatever(timo);
timedwaitclock_end(&T);
...
}

Move timedwaitclock_begin() and timedwaitclock_end() to subr_time.c
so they can be used by other things.

New cv_timedwaitclock, cv_timedwaitclock_sig.

Usage: given a struct timespec timeout copied from userland, along
with a clockid and TIMER_* flags,

error = cv_timedwaitclock(cv, lock, timeout, clockid, flags,
DEFAULT_TIMEOUT_EPSILON);
if (error)
/* fail */

If flags is relative (i.e., (flags & TIMER_ABSTIME) == 0), then this
deducts the time spent waiting from timeout, so you can run it in a
loop:

struct timespec timeout;

error = copyin(SCARG(uap, timeout), &timeout, sizeof timeout);
if (error)
return error;

mutex_enter(lock);
while (!ready()) {
error = cv_timedwaitclock_sig(cv, lock, &timeout,
SCARG(uap, clockid), SCARG(uap, flags),
DEFAULT_TIMEOUT_EPSILON);
if (error)
break;
}
mutex_exit(lock);

CAVEAT: If the system call is interrupted by a signal with SA_RESTART
so cv_timedwaitclock_sig fails with ERESTART, then the system call
will be restarted with the _original_ relative timeout, not counting
the time that was already spent waiting. This is a problem but it's
not a problem I want to deal with at the moment.

Fix edge cases in cv_timedwaitbt, cv_timedwaitbt_sig.

- If the timeout is exactly zero, fail immediately with EWOULDBLOCK.

- If the timeout is just so small it would be rounded to zero ticks,
make sure to wait at least one tick.

- Make sure we never return with a negative timeout left.

Set LW_SINTR earlier so it doesn't pose a problem for doing interruptable
waits with turnstiles (not currently done).

hardclock_ticks -> getticks()

- Make this needed sequence always work for condvars, by not touching the CV
again after wakeup. Previously it could panic because cv_signal() could
be called by cv_wait_sig() + others:

cv_broadcast(cv);
cv_destroy(cv);

- In support of the above, if an LWP doing a timed wait is awoken by
cv_broadcast() or cv_signal(), don't return an error if the timer
fires after the fact, i.e. either succeed or fail, not both.

- Remove LOCKDEBUG code for CVs which never worked properly and is of
questionable use.

branches: 1.44.2;
Change sleepq_t from a TAILQ to a LIST and remove SOBJ_SLEEPQ_FIFO. Only
select/poll used the FIFO method and that was for collisions which rarely
occur. Shrinks sleep_t and condvar_t.

- List all of the syncobjs in syncobj.h.
- Update a comment.

branches: 1.42.2;
- Put back a microoptimisation that was accidentally removed.
- Comments.

branches: 1.41.4;
Apply C99-style struct initialization to syncobj_t

Apply C99-style struct initialization to lockops_t

Apply same treatment to cv_timedwaitbt.

Clarify interpretation of timeout/epsilon in cv_timedwaitbt.

Add cv_timedwaitbt, cv_timedwaitbt_sig.

Takes struct bintime maximum delay, and decrements it in place so
that you can use it in a loop in case of spurious wakeup.

Discussed on tech-kern a couple years ago:

https://mail-index.netbsd.org/tech-kern/2015/03/23/msg018557.html

Added a parameter for expressing desired precision -- not currently
interpreted, but intended for a future tickless kernel with a choice
of high-resolution timers.

allow cv_signal() immediately followed by cv_destroy().
this sequence is used by ZFS in a couple places and by supporting it
natively we can undo our local ZFS changes that avoided it.
note that this is only legal when all of the waiters use cv_wait()
and not any of the other variations, and lockdebug will catch
any violations of this rule.

branches: 1.35.10;
o Don't include sys/sched.h. Scheduler-related operation is done by
sleepq(9) via SOBJ_SLEEPQ_SORTED.

o Include sys/lwp.h instead of sys/proc.h.

branches: 1.34.6;
Mark a diagnostic-only variable

nodebug is only used with LOCKDEBUG

branches: 1.32.6;
also comment on the meaning of timo=0 for cv_timedwait_sig.

Add comments saying that a cv_timedwait and sleepq_block interpret
timo = 0 as an infinite timeout. This is already documented in the
cv_timedwait(9) man page, and there is no sleeq_block(9) man page.

branches: 1.30.2; 1.30.12;
These don't need uvm/uvm_extern.h.

Typo fix.

branches: 1.28.4; 1.28.6;
tsleep() on lbolt is now illegal. Convert cv_wakeup(&lbolt) to
cv_broadcast(&lbolt) and get rid of the prior.

Remove uarea swap-out functionality:

- Addresses the issue described in PR/38828.
- Some simplification in threading and sleepq subsystems.
- Eliminates pmap_collect() and, as a side note, allows pmap optimisations.
- Eliminates XS_CTL_DATA_ONSTACK in scsipi code.
- Avoids few scans on LWP list and thus potentially long holds of proc_lock.
- Cuts ~1.5k lines of code. Reduces amd64 kernel size by ~4k.
- Removes __SWAP_BROKEN cases.

Tested on x86, mips, acorn32 (thanks <mpumford>) and partly tested on
acorn26 (thanks to <bjh21>).

Discussed on <tech-kern>, reviewed by <ad>.

Make condvars really opaque -- hide the wait message member from consumers
of the API.

branches: 1.25.4;
PR kern/38761: new (?) race in buffer cache code

Back out the workaround from cv_has_waiters(), which is not longer needed.
Removal was missed earlier.

PR kern/38761: new (?) race in buffer cache code

- Back out the previous workaround now that the sleep queue code has
been changed to never let the queue become empty if there are valid
waiters.
- Use sleepq_hashlock() to improve clarity.
- Sprinkle some assertions.

Fix for biowait hangs, and possibly other condvar hangs. Also should fix
PR kern/38761.

The condvar must access the sleepq with the sleepq lock held, doing so
is causing inconsistent sleepq state to be read.

This is because some accesses to the sleepq don't come via the cv code,
but are call directly into sleepq_changepri and sleepq_lendpri, which take
the sleepq lock, and removes then re-inserts lwps into the sleepq.

Running a build.sh with -j8 now completes on my quad-core, also tested by
Simon@ on a 8-core server and matt@ on a quad-core.

I believe there is room to be more efficient with this, as we now take the
sleepq lock for all cv_broadcast and cv_signal calls. I'll look into this
and post a diff to tech-kern.

branches: 1.22.2;
Disable the wakeup assertion for the time being because the tty code
triggers it.

Fix wmesg for !LOCKDEBUG.

- Give each condition variable its own sleep queue head. Helps the system
to scale more gracefully when there are thousands of active threads.
Proposed on tech-kern@.

- Use LOCKDEBUG to catch some errors in the use of condition variables:

freeing an active CV
re-initializing an active CV
using multiple distinct mutexes during concurrent waits
not holding the interlocking mutex when calling cv_broadcast/cv_signal
waking waiters and destroying the CV before they run and exit it

Broken assertion.

Take the mutex pointer and waiters count out of sleepq_t: the values can
be or are maintained elsewhere. Now a sleepq_t is just a TAILQ_HEAD.

branches: 1.17.2;
Remove clause 3 and 4 from TNF licenses

branches: 1.16.2; 1.16.4;
Add a boolean parameter to syncobj_t::sobj_unsleep. If true we want the
existing behaviour: the unsleep method unlocks and wakes the swapper if
needs be. If false, the caller is doing a batch operation and will take
care of that later. This is kind of ugly, but it's difficult for the caller
to know which lock to release in some situations.

- Add cv_is_valid(), for use in assertions. Performs basic sanity checks.
- Add more assertions.

branches: 1.14.10; 1.14.14;
Merge scheduler changes from the vmlocking branch. All discussed on
tech-kern:

- Invert priority space so that zero is the lowest priority. Rearrange
number and type of priority levels into bands. Add new bands like
'kernel real time'.
- Ignore the priority level passed to tsleep. Compute priority for
sleep dynamically.
- For SCHED_4BSD, make priority adjustment per-LWP, not per-process.

branches: 1.13.2; 1.13.4;
Merge from vmlocking: relax an assertion if panicstr != NULL.

branches: 1.12.2; 1.12.4; 1.12.6; 1.12.8;
cv_wakeup: the entire queue has to be searched, as we can't know how many
waiters there are.

Ressurect cv_wakeup() and use it on lbolt. Should fix PR kern/36714.
(background/foreground signal lossage in -current with various programs).

Improve assertions slightly. When awakening assert that the CV has not
been destroyed.

branches: 1.9.2;
Merge some of the less invasive changes from the vmlocking branch:

- kthread, callout, devsw API changes
- select()/poll() improvements
- miscellaneous MT safety improvements

merge yamt-idlelwp branch. asked by core@. some ports still needs work.

from doc/BRANCHES:

idle lwp, and some changes depending on it.

1. separate context switching and thread scheduling.
(cf. gmcgarry_ctxsw)
2. implement idle lwp.
3. clean up related MD/MI interfaces.
4. make scheduler(s) modular.

Make cv_has_waiters() return type bool.

- cv_wakeup: remove this. There are ~zero situations where it's useful.
- cv_wait and friends: after resuming execution, check to see if we have
been restarted as a result of cv_signal. If we have, but cannot take
the wakeup (because of eg a pending Unix signal or timeout) then try to
ensure that another LWP sees it. This is necessary because there may
be multiple waiters, and at least one should take the wakeup if possible.
Prompted by a discussion with pooka@.
- typedef struct lwp lwp_t;
- int -> bool, struct lwp -> lwp_t in a few places.

branches: 1.5.2; 1.5.4; 1.5.6;
typedef pri_t and use it instead of int and u_char.

implement priority inheritance.

branches: 1.3.2; 1.3.4;
unwrap short lines.

Merge newlock2 to head.

branches: 1.1.2;
file kern_condvar.c was initially added on branch newlock2.

kern_condvar.c: Sort includes. No functional change intended.

sys/lwp.h: Nix sys/syncobj.h dependency.

Remove it in ddb/db_syncobj.h too.

New sys/wchan.h defines wchan_t so that users need not pull in
sys/syncobj.h to get it.

Sprinkle #include <sys/syncobj.h> in .c files where it is now needed.

Add cv_fdrestart() (better name suggestions welcome):

Like cv_broadcast(), but make any LWPs that share the same file descriptor
table as the caller return ERESTART when resuming. Used to dislodge LWPs
waiting for I/O that prevent a file descriptor from being closed, without
upsetting access to the file (not descriptor) made from another direction.

Comments.

Ensure that an LWP that has taken a legitimate wakeup never produces an
error code from sleepq_block(). Then, it's possible to make cv_signal()
work as expected and only ever wake a singular LWP.

Eliminate l->l_biglocks. Originally I think it had a use but these days a
local variable will do.

- Simplify how priority boost for blocking in kernel is handled. Rather
than setting it up at each site where we block, make it a property of
syncobj_t. Then, do not hang onto the priority boost until userret(),
drop it as soon as the LWP is out of the run queue and onto a CPU.
Holding onto it longer is of questionable benefit.

- This allows two members of lwp_t to be deleted, and mi_userret() to be
simplified a lot (next step: trim it down to a single conditional).

- While here, constify syncobj_t and de-inline a bunch of small functions
like lwp_lock() which turn out not to be small after all (I don't know
why, but atomic_*_relaxed() seem to provoke a compiler shitfit above and
beyond what volatile does).

kern: New struct syncobj::sobj_name member for diagnostics.

XXX potential kernel ABI change -- not sure any modules actually use
struct syncobj but it's hard to rule that out because sys/syncobj.h
leaks into sys/lwp.h

sleepq(9): Pass syncobj through to sleepq_block.

Previously the usage pattern was:

sleepq_enter(sq, l, lock); // locks l
...
sleepq_enqueue(sq, ..., sobj, ...); // assumes l locked, sets l_syncobj
... (*)
sleepq_block(...); // unlocks l

As long as l remains locked from sleepq_enter to sleepq_block,
l_syncobj is stable, and sleepq_block uses it via ktrcsw to determine
whether the sleep is on a mutex in order to avoid creating ktrace
context-switch records (which involves allocation which is forbidden
in softint context, while taking and even sleeping for a mutex is
allowed).

However, in turnstile_block, the logic at (*) also involves
turnstile_lendpri, which sometimes unlocks and relocks l. At that
point, another thread can swoop in and sleepq_remove l, which sets
l_syncobj to sched_syncobj. If that happens, ktrcsw does what is
forbidden -- tries to allocate a ktrace record for the context
switch.

As an optimization, sleepq_block or turnstile_block could stop early
if it detects that l_syncobj doesn't match -- we've already been
requested to wake up at this point so there's no need to mi_switch.
(And then it would be unnecessary to pass the syncobj through
sleepq_block, because l_syncobj would remain stable.) But I'll leave
that to another change.

Reported-by: syzbot+8b9d7b066c32dbcdc63b@syzkaller.appspotmail.com

PR/55664: Ruslan Nikolaev: Split out sleepq guts and turnstiles not used
in rump into a separate header file. Add a sleepq_destroy() empty hook.

branches: 1.52.2;
Remove timedwaitclock.

This did not fix the bug I hoped it would fix in futex, and needs
more design thought. Might redo it somewhat differently later.

New timedwaitclock_setup.

C99 initializers would have been nice, but part of the struct is
explicit parameters and part of the struct is implicit state, and
-Wmissing-field-initializers can't discriminate between them
(although for some reason it doesn't always fire!).

Instead, just do:

struct timedwaitclock T;

timedwaitclock_setup(&T, timeout, clockid, flags, epsilon);
while (...) {
error = timedwaitclock_begin(&T, &timo);
if (error)
...
error = waitwhatever(timo);
timedwaitclock_end(&T);
...
}

Move timedwaitclock_begin() and timedwaitclock_end() to subr_time.c
so they can be used by other things.

New cv_timedwaitclock, cv_timedwaitclock_sig.

Usage: given a struct timespec timeout copied from userland, along
with a clockid and TIMER_* flags,

error = cv_timedwaitclock(cv, lock, timeout, clockid, flags,
DEFAULT_TIMEOUT_EPSILON);
if (error)
/* fail */

If flags is relative (i.e., (flags & TIMER_ABSTIME) == 0), then this
deducts the time spent waiting from timeout, so you can run it in a
loop:

struct timespec timeout;

error = copyin(SCARG(uap, timeout), &timeout, sizeof timeout);
if (error)
return error;

mutex_enter(lock);
while (!ready()) {
error = cv_timedwaitclock_sig(cv, lock, &timeout,
SCARG(uap, clockid), SCARG(uap, flags),
DEFAULT_TIMEOUT_EPSILON);
if (error)
break;
}
mutex_exit(lock);

CAVEAT: If the system call is interrupted by a signal with SA_RESTART
so cv_timedwaitclock_sig fails with ERESTART, then the system call
will be restarted with the _original_ relative timeout, not counting
the time that was already spent waiting. This is a problem but it's
not a problem I want to deal with at the moment.

Fix edge cases in cv_timedwaitbt, cv_timedwaitbt_sig.

- If the timeout is exactly zero, fail immediately with EWOULDBLOCK.

- If the timeout is just so small it would be rounded to zero ticks,
make sure to wait at least one tick.

- Make sure we never return with a negative timeout left.

Set LW_SINTR earlier so it doesn't pose a problem for doing interruptable
waits with turnstiles (not currently done).

hardclock_ticks -> getticks()

- Make this needed sequence always work for condvars, by not touching the CV
again after wakeup. Previously it could panic because cv_signal() could
be called by cv_wait_sig() + others:

cv_broadcast(cv);
cv_destroy(cv);

- In support of the above, if an LWP doing a timed wait is awoken by
cv_broadcast() or cv_signal(), don't return an error if the timer
fires after the fact, i.e. either succeed or fail, not both.

- Remove LOCKDEBUG code for CVs which never worked properly and is of
questionable use.

branches: 1.44.2;
Change sleepq_t from a TAILQ to a LIST and remove SOBJ_SLEEPQ_FIFO. Only
select/poll used the FIFO method and that was for collisions which rarely
occur. Shrinks sleep_t and condvar_t.

- List all of the syncobjs in syncobj.h.
- Update a comment.

branches: 1.42.2;
- Put back a microoptimisation that was accidentally removed.
- Comments.

branches: 1.41.4;
Apply C99-style struct initialization to syncobj_t

Apply C99-style struct initialization to lockops_t

Apply same treatment to cv_timedwaitbt.

Clarify interpretation of timeout/epsilon in cv_timedwaitbt.

Add cv_timedwaitbt, cv_timedwaitbt_sig.

Takes struct bintime maximum delay, and decrements it in place so
that you can use it in a loop in case of spurious wakeup.

Discussed on tech-kern a couple years ago:

https://mail-index.netbsd.org/tech-kern/2015/03/23/msg018557.html

Added a parameter for expressing desired precision -- not currently
interpreted, but intended for a future tickless kernel with a choice
of high-resolution timers.

allow cv_signal() immediately followed by cv_destroy().
this sequence is used by ZFS in a couple places and by supporting it
natively we can undo our local ZFS changes that avoided it.
note that this is only legal when all of the waiters use cv_wait()
and not any of the other variations, and lockdebug will catch
any violations of this rule.

branches: 1.35.10;
o Don't include sys/sched.h. Scheduler-related operation is done by
sleepq(9) via SOBJ_SLEEPQ_SORTED.

o Include sys/lwp.h instead of sys/proc.h.

branches: 1.34.6;
Mark a diagnostic-only variable

nodebug is only used with LOCKDEBUG

branches: 1.32.6;
also comment on the meaning of timo=0 for cv_timedwait_sig.

Add comments saying that a cv_timedwait and sleepq_block interpret
timo = 0 as an infinite timeout. This is already documented in the
cv_timedwait(9) man page, and there is no sleeq_block(9) man page.

branches: 1.30.2; 1.30.12;
These don't need uvm/uvm_extern.h.

Typo fix.

branches: 1.28.4; 1.28.6;
tsleep() on lbolt is now illegal. Convert cv_wakeup(&lbolt) to
cv_broadcast(&lbolt) and get rid of the prior.

Remove uarea swap-out functionality:

- Addresses the issue described in PR/38828.
- Some simplification in threading and sleepq subsystems.
- Eliminates pmap_collect() and, as a side note, allows pmap optimisations.
- Eliminates XS_CTL_DATA_ONSTACK in scsipi code.
- Avoids few scans on LWP list and thus potentially long holds of proc_lock.
- Cuts ~1.5k lines of code. Reduces amd64 kernel size by ~4k.
- Removes __SWAP_BROKEN cases.

Tested on x86, mips, acorn32 (thanks <mpumford>) and partly tested on
acorn26 (thanks to <bjh21>).

Discussed on <tech-kern>, reviewed by <ad>.

Make condvars really opaque -- hide the wait message member from consumers
of the API.

branches: 1.25.4;
PR kern/38761: new (?) race in buffer cache code

Back out the workaround from cv_has_waiters(), which is not longer needed.
Removal was missed earlier.

PR kern/38761: new (?) race in buffer cache code

- Back out the previous workaround now that the sleep queue code has
been changed to never let the queue become empty if there are valid
waiters.
- Use sleepq_hashlock() to improve clarity.
- Sprinkle some assertions.

Fix for biowait hangs, and possibly other condvar hangs. Also should fix
PR kern/38761.

The condvar must access the sleepq with the sleepq lock held, doing so
is causing inconsistent sleepq state to be read.

This is because some accesses to the sleepq don't come via the cv code,
but are call directly into sleepq_changepri and sleepq_lendpri, which take
the sleepq lock, and removes then re-inserts lwps into the sleepq.

Running a build.sh with -j8 now completes on my quad-core, also tested by
Simon@ on a 8-core server and matt@ on a quad-core.

I believe there is room to be more efficient with this, as we now take the
sleepq lock for all cv_broadcast and cv_signal calls. I'll look into this
and post a diff to tech-kern.

branches: 1.22.2;
Disable the wakeup assertion for the time being because the tty code
triggers it.

Fix wmesg for !LOCKDEBUG.

- Give each condition variable its own sleep queue head. Helps the system
to scale more gracefully when there are thousands of active threads.
Proposed on tech-kern@.

- Use LOCKDEBUG to catch some errors in the use of condition variables:

freeing an active CV
re-initializing an active CV
using multiple distinct mutexes during concurrent waits
not holding the interlocking mutex when calling cv_broadcast/cv_signal
waking waiters and destroying the CV before they run and exit it

Broken assertion.

Take the mutex pointer and waiters count out of sleepq_t: the values can
be or are maintained elsewhere. Now a sleepq_t is just a TAILQ_HEAD.

branches: 1.17.2;
Remove clause 3 and 4 from TNF licenses

branches: 1.16.2; 1.16.4;
Add a boolean parameter to syncobj_t::sobj_unsleep. If true we want the
existing behaviour: the unsleep method unlocks and wakes the swapper if
needs be. If false, the caller is doing a batch operation and will take
care of that later. This is kind of ugly, but it's difficult for the caller
to know which lock to release in some situations.

- Add cv_is_valid(), for use in assertions. Performs basic sanity checks.
- Add more assertions.

branches: 1.14.10; 1.14.14;
Merge scheduler changes from the vmlocking branch. All discussed on
tech-kern:

- Invert priority space so that zero is the lowest priority. Rearrange
number and type of priority levels into bands. Add new bands like
'kernel real time'.
- Ignore the priority level passed to tsleep. Compute priority for
sleep dynamically.
- For SCHED_4BSD, make priority adjustment per-LWP, not per-process.

branches: 1.13.2; 1.13.4;
Merge from vmlocking: relax an assertion if panicstr != NULL.

branches: 1.12.2; 1.12.4; 1.12.6; 1.12.8;
cv_wakeup: the entire queue has to be searched, as we can't know how many
waiters there are.

Ressurect cv_wakeup() and use it on lbolt. Should fix PR kern/36714.
(background/foreground signal lossage in -current with various programs).

Improve assertions slightly. When awakening assert that the CV has not
been destroyed.

branches: 1.9.2;
Merge some of the less invasive changes from the vmlocking branch:

- kthread, callout, devsw API changes
- select()/poll() improvements
- miscellaneous MT safety improvements

merge yamt-idlelwp branch. asked by core@. some ports still needs work.

from doc/BRANCHES:

idle lwp, and some changes depending on it.

1. separate context switching and thread scheduling.
(cf. gmcgarry_ctxsw)
2. implement idle lwp.
3. clean up related MD/MI interfaces.
4. make scheduler(s) modular.

Make cv_has_waiters() return type bool.

- cv_wakeup: remove this. There are ~zero situations where it's useful.
- cv_wait and friends: after resuming execution, check to see if we have
been restarted as a result of cv_signal. If we have, but cannot take
the wakeup (because of eg a pending Unix signal or timeout) then try to
ensure that another LWP sees it. This is necessary because there may
be multiple waiters, and at least one should take the wakeup if possible.
Prompted by a discussion with pooka@.
- typedef struct lwp lwp_t;
- int -> bool, struct lwp -> lwp_t in a few places.

branches: 1.5.2; 1.5.4; 1.5.6;
typedef pri_t and use it instead of int and u_char.

implement priority inheritance.

branches: 1.3.2; 1.3.4;
unwrap short lines.

Merge newlock2 to head.

branches: 1.1.2;
file kern_condvar.c was initially added on branch newlock2.

Add cv_fdrestart() (better name suggestions welcome):

Like cv_broadcast(), but make any LWPs that share the same file descriptor
table as the caller return ERESTART when resuming. Used to dislodge LWPs
waiting for I/O that prevent a file descriptor from being closed, without
upsetting access to the file (not descriptor) made from another direction.

Comments.

Ensure that an LWP that has taken a legitimate wakeup never produces an
error code from sleepq_block(). Then, it's possible to make cv_signal()
work as expected and only ever wake a singular LWP.

Eliminate l->l_biglocks. Originally I think it had a use but these days a
local variable will do.

- Simplify how priority boost for blocking in kernel is handled. Rather
than setting it up at each site where we block, make it a property of
syncobj_t. Then, do not hang onto the priority boost until userret(),
drop it as soon as the LWP is out of the run queue and onto a CPU.
Holding onto it longer is of questionable benefit.

- This allows two members of lwp_t to be deleted, and mi_userret() to be
simplified a lot (next step: trim it down to a single conditional).

- While here, constify syncobj_t and de-inline a bunch of small functions
like lwp_lock() which turn out not to be small after all (I don't know
why, but atomic_*_relaxed() seem to provoke a compiler shitfit above and
beyond what volatile does).

kern: New struct syncobj::sobj_name member for diagnostics.

XXX potential kernel ABI change -- not sure any modules actually use
struct syncobj but it's hard to rule that out because sys/syncobj.h
leaks into sys/lwp.h

sleepq(9): Pass syncobj through to sleepq_block.

Previously the usage pattern was:

sleepq_enter(sq, l, lock); // locks l
...
sleepq_enqueue(sq, ..., sobj, ...); // assumes l locked, sets l_syncobj
... (*)
sleepq_block(...); // unlocks l

As long as l remains locked from sleepq_enter to sleepq_block,
l_syncobj is stable, and sleepq_block uses it via ktrcsw to determine
whether the sleep is on a mutex in order to avoid creating ktrace
context-switch records (which involves allocation which is forbidden
in softint context, while taking and even sleeping for a mutex is
allowed).

However, in turnstile_block, the logic at (*) also involves
turnstile_lendpri, which sometimes unlocks and relocks l. At that
point, another thread can swoop in and sleepq_remove l, which sets
l_syncobj to sched_syncobj. If that happens, ktrcsw does what is
forbidden -- tries to allocate a ktrace record for the context
switch.

As an optimization, sleepq_block or turnstile_block could stop early
if it detects that l_syncobj doesn't match -- we've already been
requested to wake up at this point so there's no need to mi_switch.
(And then it would be unnecessary to pass the syncobj through
sleepq_block, because l_syncobj would remain stable.) But I'll leave
that to another change.

Reported-by: syzbot+8b9d7b066c32dbcdc63b@syzkaller.appspotmail.com

PR/55664: Ruslan Nikolaev: Split out sleepq guts and turnstiles not used
in rump into a separate header file. Add a sleepq_destroy() empty hook.

branches: 1.52.2;
Remove timedwaitclock.

This did not fix the bug I hoped it would fix in futex, and needs
more design thought. Might redo it somewhat differently later.

New timedwaitclock_setup.

C99 initializers would have been nice, but part of the struct is
explicit parameters and part of the struct is implicit state, and
-Wmissing-field-initializers can't discriminate between them
(although for some reason it doesn't always fire!).

Instead, just do:

struct timedwaitclock T;

timedwaitclock_setup(&T, timeout, clockid, flags, epsilon);
while (...) {
error = timedwaitclock_begin(&T, &timo);
if (error)
...
error = waitwhatever(timo);
timedwaitclock_end(&T);
...
}

Move timedwaitclock_begin() and timedwaitclock_end() to subr_time.c
so they can be used by other things.

New cv_timedwaitclock, cv_timedwaitclock_sig.

Usage: given a struct timespec timeout copied from userland, along
with a clockid and TIMER_* flags,

error = cv_timedwaitclock(cv, lock, timeout, clockid, flags,
DEFAULT_TIMEOUT_EPSILON);
if (error)
/* fail */

If flags is relative (i.e., (flags & TIMER_ABSTIME) == 0), then this
deducts the time spent waiting from timeout, so you can run it in a
loop:

struct timespec timeout;

error = copyin(SCARG(uap, timeout), &timeout, sizeof timeout);
if (error)
return error;

mutex_enter(lock);
while (!ready()) {
error = cv_timedwaitclock_sig(cv, lock, &timeout,
SCARG(uap, clockid), SCARG(uap, flags),
DEFAULT_TIMEOUT_EPSILON);
if (error)
break;
}
mutex_exit(lock);

CAVEAT: If the system call is interrupted by a signal with SA_RESTART
so cv_timedwaitclock_sig fails with ERESTART, then the system call
will be restarted with the _original_ relative timeout, not counting
the time that was already spent waiting. This is a problem but it's
not a problem I want to deal with at the moment.

Fix edge cases in cv_timedwaitbt, cv_timedwaitbt_sig.

- If the timeout is exactly zero, fail immediately with EWOULDBLOCK.

- If the timeout is just so small it would be rounded to zero ticks,
make sure to wait at least one tick.

- Make sure we never return with a negative timeout left.

Set LW_SINTR earlier so it doesn't pose a problem for doing interruptable
waits with turnstiles (not currently done).

hardclock_ticks -> getticks()

- Make this needed sequence always work for condvars, by not touching the CV
again after wakeup. Previously it could panic because cv_signal() could
be called by cv_wait_sig() + others:

cv_broadcast(cv);
cv_destroy(cv);

- In support of the above, if an LWP doing a timed wait is awoken by
cv_broadcast() or cv_signal(), don't return an error if the timer
fires after the fact, i.e. either succeed or fail, not both.

- Remove LOCKDEBUG code for CVs which never worked properly and is of
questionable use.

branches: 1.44.2;
Change sleepq_t from a TAILQ to a LIST and remove SOBJ_SLEEPQ_FIFO. Only
select/poll used the FIFO method and that was for collisions which rarely
occur. Shrinks sleep_t and condvar_t.

- List all of the syncobjs in syncobj.h.
- Update a comment.

branches: 1.42.2;
- Put back a microoptimisation that was accidentally removed.
- Comments.

branches: 1.41.4;
Apply C99-style struct initialization to syncobj_t

Apply C99-style struct initialization to lockops_t

Apply same treatment to cv_timedwaitbt.

Clarify interpretation of timeout/epsilon in cv_timedwaitbt.

Add cv_timedwaitbt, cv_timedwaitbt_sig.

Takes struct bintime maximum delay, and decrements it in place so
that you can use it in a loop in case of spurious wakeup.

Discussed on tech-kern a couple years ago:

https://mail-index.netbsd.org/tech-kern/2015/03/23/msg018557.html

Added a parameter for expressing desired precision -- not currently
interpreted, but intended for a future tickless kernel with a choice
of high-resolution timers.

allow cv_signal() immediately followed by cv_destroy().
this sequence is used by ZFS in a couple places and by supporting it
natively we can undo our local ZFS changes that avoided it.
note that this is only legal when all of the waiters use cv_wait()
and not any of the other variations, and lockdebug will catch
any violations of this rule.

branches: 1.35.10;
o Don't include sys/sched.h. Scheduler-related operation is done by
sleepq(9) via SOBJ_SLEEPQ_SORTED.

o Include sys/lwp.h instead of sys/proc.h.

branches: 1.34.6;
Mark a diagnostic-only variable

nodebug is only used with LOCKDEBUG

branches: 1.32.6;
also comment on the meaning of timo=0 for cv_timedwait_sig.

Add comments saying that a cv_timedwait and sleepq_block interpret
timo = 0 as an infinite timeout. This is already documented in the
cv_timedwait(9) man page, and there is no sleeq_block(9) man page.

branches: 1.30.2; 1.30.12;
These don't need uvm/uvm_extern.h.

Typo fix.

branches: 1.28.4; 1.28.6;
tsleep() on lbolt is now illegal. Convert cv_wakeup(&lbolt) to
cv_broadcast(&lbolt) and get rid of the prior.

Remove uarea swap-out functionality:

- Addresses the issue described in PR/38828.
- Some simplification in threading and sleepq subsystems.
- Eliminates pmap_collect() and, as a side note, allows pmap optimisations.
- Eliminates XS_CTL_DATA_ONSTACK in scsipi code.
- Avoids few scans on LWP list and thus potentially long holds of proc_lock.
- Cuts ~1.5k lines of code. Reduces amd64 kernel size by ~4k.
- Removes __SWAP_BROKEN cases.

Tested on x86, mips, acorn32 (thanks <mpumford>) and partly tested on
acorn26 (thanks to <bjh21>).

Discussed on <tech-kern>, reviewed by <ad>.

Make condvars really opaque -- hide the wait message member from consumers
of the API.

branches: 1.25.4;
PR kern/38761: new (?) race in buffer cache code

Back out the workaround from cv_has_waiters(), which is not longer needed.
Removal was missed earlier.

PR kern/38761: new (?) race in buffer cache code

- Back out the previous workaround now that the sleep queue code has
been changed to never let the queue become empty if there are valid
waiters.
- Use sleepq_hashlock() to improve clarity.
- Sprinkle some assertions.

Fix for biowait hangs, and possibly other condvar hangs. Also should fix
PR kern/38761.

The condvar must access the sleepq with the sleepq lock held, doing so
is causing inconsistent sleepq state to be read.

This is because some accesses to the sleepq don't come via the cv code,
but are call directly into sleepq_changepri and sleepq_lendpri, which take
the sleepq lock, and removes then re-inserts lwps into the sleepq.

Running a build.sh with -j8 now completes on my quad-core, also tested by
Simon@ on a 8-core server and matt@ on a quad-core.

I believe there is room to be more efficient with this, as we now take the
sleepq lock for all cv_broadcast and cv_signal calls. I'll look into this
and post a diff to tech-kern.

branches: 1.22.2;
Disable the wakeup assertion for the time being because the tty code
triggers it.

Fix wmesg for !LOCKDEBUG.

- Give each condition variable its own sleep queue head. Helps the system
to scale more gracefully when there are thousands of active threads.
Proposed on tech-kern@.

- Use LOCKDEBUG to catch some errors in the use of condition variables:

freeing an active CV
re-initializing an active CV
using multiple distinct mutexes during concurrent waits
not holding the interlocking mutex when calling cv_broadcast/cv_signal
waking waiters and destroying the CV before they run and exit it

Broken assertion.

Take the mutex pointer and waiters count out of sleepq_t: the values can
be or are maintained elsewhere. Now a sleepq_t is just a TAILQ_HEAD.

branches: 1.17.2;
Remove clause 3 and 4 from TNF licenses

branches: 1.16.2; 1.16.4;
Add a boolean parameter to syncobj_t::sobj_unsleep. If true we want the
existing behaviour: the unsleep method unlocks and wakes the swapper if
needs be. If false, the caller is doing a batch operation and will take
care of that later. This is kind of ugly, but it's difficult for the caller
to know which lock to release in some situations.

- Add cv_is_valid(), for use in assertions. Performs basic sanity checks.
- Add more assertions.

branches: 1.14.10; 1.14.14;
Merge scheduler changes from the vmlocking branch. All discussed on
tech-kern:

- Invert priority space so that zero is the lowest priority. Rearrange
number and type of priority levels into bands. Add new bands like
'kernel real time'.
- Ignore the priority level passed to tsleep. Compute priority for
sleep dynamically.
- For SCHED_4BSD, make priority adjustment per-LWP, not per-process.

branches: 1.13.2; 1.13.4;
Merge from vmlocking: relax an assertion if panicstr != NULL.

branches: 1.12.2; 1.12.4; 1.12.6; 1.12.8;
cv_wakeup: the entire queue has to be searched, as we can't know how many
waiters there are.

Ressurect cv_wakeup() and use it on lbolt. Should fix PR kern/36714.
(background/foreground signal lossage in -current with various programs).

Improve assertions slightly. When awakening assert that the CV has not
been destroyed.

branches: 1.9.2;
Merge some of the less invasive changes from the vmlocking branch:

- kthread, callout, devsw API changes
- select()/poll() improvements
- miscellaneous MT safety improvements

merge yamt-idlelwp branch. asked by core@. some ports still needs work.

from doc/BRANCHES:

idle lwp, and some changes depending on it.

1. separate context switching and thread scheduling.
(cf. gmcgarry_ctxsw)
2. implement idle lwp.
3. clean up related MD/MI interfaces.
4. make scheduler(s) modular.

Make cv_has_waiters() return type bool.

- cv_wakeup: remove this. There are ~zero situations where it's useful.
- cv_wait and friends: after resuming execution, check to see if we have
been restarted as a result of cv_signal. If we have, but cannot take
the wakeup (because of eg a pending Unix signal or timeout) then try to
ensure that another LWP sees it. This is necessary because there may
be multiple waiters, and at least one should take the wakeup if possible.
Prompted by a discussion with pooka@.
- typedef struct lwp lwp_t;
- int -> bool, struct lwp -> lwp_t in a few places.

branches: 1.5.2; 1.5.4; 1.5.6;
typedef pri_t and use it instead of int and u_char.

implement priority inheritance.

branches: 1.3.2; 1.3.4;
unwrap short lines.

Merge newlock2 to head.

branches: 1.1.2;
file kern_condvar.c was initially added on branch newlock2.

Ensure that an LWP that has taken a legitimate wakeup never produces an
error code from sleepq_block(). Then, it's possible to make cv_signal()
work as expected and only ever wake a singular LWP.

Eliminate l->l_biglocks. Originally I think it had a use but these days a
local variable will do.

- Simplify how priority boost for blocking in kernel is handled. Rather
than setting it up at each site where we block, make it a property of
syncobj_t. Then, do not hang onto the priority boost until userret(),
drop it as soon as the LWP is out of the run queue and onto a CPU.
Holding onto it longer is of questionable benefit.

- This allows two members of lwp_t to be deleted, and mi_userret() to be
simplified a lot (next step: trim it down to a single conditional).

- While here, constify syncobj_t and de-inline a bunch of small functions
like lwp_lock() which turn out not to be small after all (I don't know
why, but atomic_*_relaxed() seem to provoke a compiler shitfit above and
beyond what volatile does).

kern: New struct syncobj::sobj_name member for diagnostics.

XXX potential kernel ABI change -- not sure any modules actually use
struct syncobj but it's hard to rule that out because sys/syncobj.h
leaks into sys/lwp.h

sleepq(9): Pass syncobj through to sleepq_block.

Previously the usage pattern was:

sleepq_enter(sq, l, lock); // locks l
...
sleepq_enqueue(sq, ..., sobj, ...); // assumes l locked, sets l_syncobj
... (*)
sleepq_block(...); // unlocks l

As long as l remains locked from sleepq_enter to sleepq_block,
l_syncobj is stable, and sleepq_block uses it via ktrcsw to determine
whether the sleep is on a mutex in order to avoid creating ktrace
context-switch records (which involves allocation which is forbidden
in softint context, while taking and even sleeping for a mutex is
allowed).

However, in turnstile_block, the logic at (*) also involves
turnstile_lendpri, which sometimes unlocks and relocks l. At that
point, another thread can swoop in and sleepq_remove l, which sets
l_syncobj to sched_syncobj. If that happens, ktrcsw does what is
forbidden -- tries to allocate a ktrace record for the context
switch.

As an optimization, sleepq_block or turnstile_block could stop early
if it detects that l_syncobj doesn't match -- we've already been
requested to wake up at this point so there's no need to mi_switch.
(And then it would be unnecessary to pass the syncobj through
sleepq_block, because l_syncobj would remain stable.) But I'll leave
that to another change.

Reported-by: syzbot+8b9d7b066c32dbcdc63b@syzkaller.appspotmail.com

PR/55664: Ruslan Nikolaev: Split out sleepq guts and turnstiles not used
in rump into a separate header file. Add a sleepq_destroy() empty hook.

branches: 1.52.2;
Remove timedwaitclock.

This did not fix the bug I hoped it would fix in futex, and needs
more design thought. Might redo it somewhat differently later.

New timedwaitclock_setup.

C99 initializers would have been nice, but part of the struct is
explicit parameters and part of the struct is implicit state, and
-Wmissing-field-initializers can't discriminate between them
(although for some reason it doesn't always fire!).

Instead, just do:

struct timedwaitclock T;

timedwaitclock_setup(&T, timeout, clockid, flags, epsilon);
while (...) {
error = timedwaitclock_begin(&T, &timo);
if (error)
...
error = waitwhatever(timo);
timedwaitclock_end(&T);
...
}

Move timedwaitclock_begin() and timedwaitclock_end() to subr_time.c
so they can be used by other things.

New cv_timedwaitclock, cv_timedwaitclock_sig.

Usage: given a struct timespec timeout copied from userland, along
with a clockid and TIMER_* flags,

error = cv_timedwaitclock(cv, lock, timeout, clockid, flags,
DEFAULT_TIMEOUT_EPSILON);
if (error)
/* fail */

If flags is relative (i.e., (flags & TIMER_ABSTIME) == 0), then this
deducts the time spent waiting from timeout, so you can run it in a
loop:

struct timespec timeout;

error = copyin(SCARG(uap, timeout), &timeout, sizeof timeout);
if (error)
return error;

mutex_enter(lock);
while (!ready()) {
error = cv_timedwaitclock_sig(cv, lock, &timeout,
SCARG(uap, clockid), SCARG(uap, flags),
DEFAULT_TIMEOUT_EPSILON);
if (error)
break;
}
mutex_exit(lock);

CAVEAT: If the system call is interrupted by a signal with SA_RESTART
so cv_timedwaitclock_sig fails with ERESTART, then the system call
will be restarted with the _original_ relative timeout, not counting
the time that was already spent waiting. This is a problem but it's
not a problem I want to deal with at the moment.

Fix edge cases in cv_timedwaitbt, cv_timedwaitbt_sig.

- If the timeout is exactly zero, fail immediately with EWOULDBLOCK.

- If the timeout is just so small it would be rounded to zero ticks,
make sure to wait at least one tick.

- Make sure we never return with a negative timeout left.

Set LW_SINTR earlier so it doesn't pose a problem for doing interruptable
waits with turnstiles (not currently done).

hardclock_ticks -> getticks()

- Make this needed sequence always work for condvars, by not touching the CV
again after wakeup. Previously it could panic because cv_signal() could
be called by cv_wait_sig() + others:

cv_broadcast(cv);
cv_destroy(cv);

- In support of the above, if an LWP doing a timed wait is awoken by
cv_broadcast() or cv_signal(), don't return an error if the timer
fires after the fact, i.e. either succeed or fail, not both.

- Remove LOCKDEBUG code for CVs which never worked properly and is of
questionable use.

branches: 1.44.2;
Change sleepq_t from a TAILQ to a LIST and remove SOBJ_SLEEPQ_FIFO. Only
select/poll used the FIFO method and that was for collisions which rarely
occur. Shrinks sleep_t and condvar_t.

- List all of the syncobjs in syncobj.h.
- Update a comment.

branches: 1.42.2;
- Put back a microoptimisation that was accidentally removed.
- Comments.

branches: 1.41.4;
Apply C99-style struct initialization to syncobj_t

Apply C99-style struct initialization to lockops_t

Apply same treatment to cv_timedwaitbt.

Clarify interpretation of timeout/epsilon in cv_timedwaitbt.

Add cv_timedwaitbt, cv_timedwaitbt_sig.

Takes struct bintime maximum delay, and decrements it in place so
that you can use it in a loop in case of spurious wakeup.

Discussed on tech-kern a couple years ago:

https://mail-index.netbsd.org/tech-kern/2015/03/23/msg018557.html

Added a parameter for expressing desired precision -- not currently
interpreted, but intended for a future tickless kernel with a choice
of high-resolution timers.

allow cv_signal() immediately followed by cv_destroy().
this sequence is used by ZFS in a couple places and by supporting it
natively we can undo our local ZFS changes that avoided it.
note that this is only legal when all of the waiters use cv_wait()
and not any of the other variations, and lockdebug will catch
any violations of this rule.

branches: 1.35.10;
o Don't include sys/sched.h. Scheduler-related operation is done by
sleepq(9) via SOBJ_SLEEPQ_SORTED.

o Include sys/lwp.h instead of sys/proc.h.

branches: 1.34.6;
Mark a diagnostic-only variable

nodebug is only used with LOCKDEBUG

branches: 1.32.6;
also comment on the meaning of timo=0 for cv_timedwait_sig.

Add comments saying that a cv_timedwait and sleepq_block interpret
timo = 0 as an infinite timeout. This is already documented in the
cv_timedwait(9) man page, and there is no sleeq_block(9) man page.

branches: 1.30.2; 1.30.12;
These don't need uvm/uvm_extern.h.

Typo fix.

branches: 1.28.4; 1.28.6;
tsleep() on lbolt is now illegal. Convert cv_wakeup(&lbolt) to
cv_broadcast(&lbolt) and get rid of the prior.

Remove uarea swap-out functionality:

- Addresses the issue described in PR/38828.
- Some simplification in threading and sleepq subsystems.
- Eliminates pmap_collect() and, as a side note, allows pmap optimisations.
- Eliminates XS_CTL_DATA_ONSTACK in scsipi code.
- Avoids few scans on LWP list and thus potentially long holds of proc_lock.
- Cuts ~1.5k lines of code. Reduces amd64 kernel size by ~4k.
- Removes __SWAP_BROKEN cases.

Tested on x86, mips, acorn32 (thanks <mpumford>) and partly tested on
acorn26 (thanks to <bjh21>).

Discussed on <tech-kern>, reviewed by <ad>.

Make condvars really opaque -- hide the wait message member from consumers
of the API.

branches: 1.25.4;
PR kern/38761: new (?) race in buffer cache code

Back out the workaround from cv_has_waiters(), which is not longer needed.
Removal was missed earlier.

PR kern/38761: new (?) race in buffer cache code

- Back out the previous workaround now that the sleep queue code has
been changed to never let the queue become empty if there are valid
waiters.
- Use sleepq_hashlock() to improve clarity.
- Sprinkle some assertions.

Fix for biowait hangs, and possibly other condvar hangs. Also should fix
PR kern/38761.

The condvar must access the sleepq with the sleepq lock held, doing so
is causing inconsistent sleepq state to be read.

This is because some accesses to the sleepq don't come via the cv code,
but are call directly into sleepq_changepri and sleepq_lendpri, which take
the sleepq lock, and removes then re-inserts lwps into the sleepq.

Running a build.sh with -j8 now completes on my quad-core, also tested by
Simon@ on a 8-core server and matt@ on a quad-core.

I believe there is room to be more efficient with this, as we now take the
sleepq lock for all cv_broadcast and cv_signal calls. I'll look into this
and post a diff to tech-kern.

branches: 1.22.2;
Disable the wakeup assertion for the time being because the tty code
triggers it.

Fix wmesg for !LOCKDEBUG.

- Give each condition variable its own sleep queue head. Helps the system
to scale more gracefully when there are thousands of active threads.
Proposed on tech-kern@.

- Use LOCKDEBUG to catch some errors in the use of condition variables:

freeing an active CV
re-initializing an active CV
using multiple distinct mutexes during concurrent waits
not holding the interlocking mutex when calling cv_broadcast/cv_signal
waking waiters and destroying the CV before they run and exit it

Broken assertion.

Take the mutex pointer and waiters count out of sleepq_t: the values can
be or are maintained elsewhere. Now a sleepq_t is just a TAILQ_HEAD.

branches: 1.17.2;
Remove clause 3 and 4 from TNF licenses

branches: 1.16.2; 1.16.4;
Add a boolean parameter to syncobj_t::sobj_unsleep. If true we want the
existing behaviour: the unsleep method unlocks and wakes the swapper if
needs be. If false, the caller is doing a batch operation and will take
care of that later. This is kind of ugly, but it's difficult for the caller
to know which lock to release in some situations.

- Add cv_is_valid(), for use in assertions. Performs basic sanity checks.
- Add more assertions.

branches: 1.14.10; 1.14.14;
Merge scheduler changes from the vmlocking branch. All discussed on
tech-kern:

- Invert priority space so that zero is the lowest priority. Rearrange
number and type of priority levels into bands. Add new bands like
'kernel real time'.
- Ignore the priority level passed to tsleep. Compute priority for
sleep dynamically.
- For SCHED_4BSD, make priority adjustment per-LWP, not per-process.

branches: 1.13.2; 1.13.4;
Merge from vmlocking: relax an assertion if panicstr != NULL.

branches: 1.12.2; 1.12.4; 1.12.6; 1.12.8;
cv_wakeup: the entire queue has to be searched, as we can't know how many
waiters there are.

Ressurect cv_wakeup() and use it on lbolt. Should fix PR kern/36714.
(background/foreground signal lossage in -current with various programs).

Improve assertions slightly. When awakening assert that the CV has not
been destroyed.

branches: 1.9.2;
Merge some of the less invasive changes from the vmlocking branch:

- kthread, callout, devsw API changes
- select()/poll() improvements
- miscellaneous MT safety improvements

merge yamt-idlelwp branch. asked by core@. some ports still needs work.

from doc/BRANCHES:

idle lwp, and some changes depending on it.

1. separate context switching and thread scheduling.
(cf. gmcgarry_ctxsw)
2. implement idle lwp.
3. clean up related MD/MI interfaces.
4. make scheduler(s) modular.

Make cv_has_waiters() return type bool.

- cv_wakeup: remove this. There are ~zero situations where it's useful.
- cv_wait and friends: after resuming execution, check to see if we have
been restarted as a result of cv_signal. If we have, but cannot take
the wakeup (because of eg a pending Unix signal or timeout) then try to
ensure that another LWP sees it. This is necessary because there may
be multiple waiters, and at least one should take the wakeup if possible.
Prompted by a discussion with pooka@.
- typedef struct lwp lwp_t;
- int -> bool, struct lwp -> lwp_t in a few places.

branches: 1.5.2; 1.5.4; 1.5.6;
typedef pri_t and use it instead of int and u_char.

implement priority inheritance.

branches: 1.3.2; 1.3.4;
unwrap short lines.

Merge newlock2 to head.

branches: 1.1.2;
file kern_condvar.c was initially added on branch newlock2.

Eliminate l->l_biglocks. Originally I think it had a use but these days a
local variable will do.

- Simplify how priority boost for blocking in kernel is handled. Rather
than setting it up at each site where we block, make it a property of
syncobj_t. Then, do not hang onto the priority boost until userret(),
drop it as soon as the LWP is out of the run queue and onto a CPU.
Holding onto it longer is of questionable benefit.

- This allows two members of lwp_t to be deleted, and mi_userret() to be
simplified a lot (next step: trim it down to a single conditional).

- While here, constify syncobj_t and de-inline a bunch of small functions
like lwp_lock() which turn out not to be small after all (I don't know
why, but atomic_*_relaxed() seem to provoke a compiler shitfit above and
beyond what volatile does).

kern: New struct syncobj::sobj_name member for diagnostics.

XXX potential kernel ABI change -- not sure any modules actually use
struct syncobj but it's hard to rule that out because sys/syncobj.h
leaks into sys/lwp.h

sleepq(9): Pass syncobj through to sleepq_block.

Previously the usage pattern was:

sleepq_enter(sq, l, lock); // locks l
...
sleepq_enqueue(sq, ..., sobj, ...); // assumes l locked, sets l_syncobj
... (*)
sleepq_block(...); // unlocks l

As long as l remains locked from sleepq_enter to sleepq_block,
l_syncobj is stable, and sleepq_block uses it via ktrcsw to determine
whether the sleep is on a mutex in order to avoid creating ktrace
context-switch records (which involves allocation which is forbidden
in softint context, while taking and even sleeping for a mutex is
allowed).

However, in turnstile_block, the logic at (*) also involves
turnstile_lendpri, which sometimes unlocks and relocks l. At that
point, another thread can swoop in and sleepq_remove l, which sets
l_syncobj to sched_syncobj. If that happens, ktrcsw does what is
forbidden -- tries to allocate a ktrace record for the context
switch.

As an optimization, sleepq_block or turnstile_block could stop early
if it detects that l_syncobj doesn't match -- we've already been
requested to wake up at this point so there's no need to mi_switch.
(And then it would be unnecessary to pass the syncobj through
sleepq_block, because l_syncobj would remain stable.) But I'll leave
that to another change.

Reported-by: syzbot+8b9d7b066c32dbcdc63b@syzkaller.appspotmail.com

PR/55664: Ruslan Nikolaev: Split out sleepq guts and turnstiles not used
in rump into a separate header file. Add a sleepq_destroy() empty hook.

branches: 1.52.2;
Remove timedwaitclock.

This did not fix the bug I hoped it would fix in futex, and needs
more design thought. Might redo it somewhat differently later.

New timedwaitclock_setup.

C99 initializers would have been nice, but part of the struct is
explicit parameters and part of the struct is implicit state, and
-Wmissing-field-initializers can't discriminate between them
(although for some reason it doesn't always fire!).

Instead, just do:

struct timedwaitclock T;

timedwaitclock_setup(&T, timeout, clockid, flags, epsilon);
while (...) {
error = timedwaitclock_begin(&T, &timo);
if (error)
...
error = waitwhatever(timo);
timedwaitclock_end(&T);
...
}

Move timedwaitclock_begin() and timedwaitclock_end() to subr_time.c
so they can be used by other things.

New cv_timedwaitclock, cv_timedwaitclock_sig.

Usage: given a struct timespec timeout copied from userland, along
with a clockid and TIMER_* flags,

error = cv_timedwaitclock(cv, lock, timeout, clockid, flags,
DEFAULT_TIMEOUT_EPSILON);
if (error)
/* fail */

If flags is relative (i.e., (flags & TIMER_ABSTIME) == 0), then this
deducts the time spent waiting from timeout, so you can run it in a
loop:

struct timespec timeout;

error = copyin(SCARG(uap, timeout), &timeout, sizeof timeout);
if (error)
return error;

mutex_enter(lock);
while (!ready()) {
error = cv_timedwaitclock_sig(cv, lock, &timeout,
SCARG(uap, clockid), SCARG(uap, flags),
DEFAULT_TIMEOUT_EPSILON);
if (error)
break;
}
mutex_exit(lock);

CAVEAT: If the system call is interrupted by a signal with SA_RESTART
so cv_timedwaitclock_sig fails with ERESTART, then the system call
will be restarted with the _original_ relative timeout, not counting
the time that was already spent waiting. This is a problem but it's
not a problem I want to deal with at the moment.

Fix edge cases in cv_timedwaitbt, cv_timedwaitbt_sig.

- If the timeout is exactly zero, fail immediately with EWOULDBLOCK.

- If the timeout is just so small it would be rounded to zero ticks,
make sure to wait at least one tick.

- Make sure we never return with a negative timeout left.

Set LW_SINTR earlier so it doesn't pose a problem for doing interruptable
waits with turnstiles (not currently done).

hardclock_ticks -> getticks()

- Make this needed sequence always work for condvars, by not touching the CV
again after wakeup. Previously it could panic because cv_signal() could
be called by cv_wait_sig() + others:

cv_broadcast(cv);
cv_destroy(cv);

- In support of the above, if an LWP doing a timed wait is awoken by
cv_broadcast() or cv_signal(), don't return an error if the timer
fires after the fact, i.e. either succeed or fail, not both.

- Remove LOCKDEBUG code for CVs which never worked properly and is of
questionable use.

branches: 1.44.2;
Change sleepq_t from a TAILQ to a LIST and remove SOBJ_SLEEPQ_FIFO. Only
select/poll used the FIFO method and that was for collisions which rarely
occur. Shrinks sleep_t and condvar_t.

- List all of the syncobjs in syncobj.h.
- Update a comment.

branches: 1.42.2;
- Put back a microoptimisation that was accidentally removed.
- Comments.

branches: 1.41.4;
Apply C99-style struct initialization to syncobj_t

Apply C99-style struct initialization to lockops_t

Apply same treatment to cv_timedwaitbt.

Clarify interpretation of timeout/epsilon in cv_timedwaitbt.

Add cv_timedwaitbt, cv_timedwaitbt_sig.

Takes struct bintime maximum delay, and decrements it in place so
that you can use it in a loop in case of spurious wakeup.

Discussed on tech-kern a couple years ago:

https://mail-index.netbsd.org/tech-kern/2015/03/23/msg018557.html

Added a parameter for expressing desired precision -- not currently
interpreted, but intended for a future tickless kernel with a choice
of high-resolution timers.

allow cv_signal() immediately followed by cv_destroy().
this sequence is used by ZFS in a couple places and by supporting it
natively we can undo our local ZFS changes that avoided it.
note that this is only legal when all of the waiters use cv_wait()
and not any of the other variations, and lockdebug will catch
any violations of this rule.

branches: 1.35.10;
o Don't include sys/sched.h. Scheduler-related operation is done by
sleepq(9) via SOBJ_SLEEPQ_SORTED.

o Include sys/lwp.h instead of sys/proc.h.

branches: 1.34.6;
Mark a diagnostic-only variable

nodebug is only used with LOCKDEBUG

branches: 1.32.6;
also comment on the meaning of timo=0 for cv_timedwait_sig.

Add comments saying that a cv_timedwait and sleepq_block interpret
timo = 0 as an infinite timeout. This is already documented in the
cv_timedwait(9) man page, and there is no sleeq_block(9) man page.

branches: 1.30.2; 1.30.12;
These don't need uvm/uvm_extern.h.

Typo fix.

branches: 1.28.4; 1.28.6;
tsleep() on lbolt is now illegal. Convert cv_wakeup(&lbolt) to
cv_broadcast(&lbolt) and get rid of the prior.

Remove uarea swap-out functionality:

- Addresses the issue described in PR/38828.
- Some simplification in threading and sleepq subsystems.
- Eliminates pmap_collect() and, as a side note, allows pmap optimisations.
- Eliminates XS_CTL_DATA_ONSTACK in scsipi code.
- Avoids few scans on LWP list and thus potentially long holds of proc_lock.
- Cuts ~1.5k lines of code. Reduces amd64 kernel size by ~4k.
- Removes __SWAP_BROKEN cases.

Tested on x86, mips, acorn32 (thanks <mpumford>) and partly tested on
acorn26 (thanks to <bjh21>).

Discussed on <tech-kern>, reviewed by <ad>.

Make condvars really opaque -- hide the wait message member from consumers
of the API.

branches: 1.25.4;
PR kern/38761: new (?) race in buffer cache code

Back out the workaround from cv_has_waiters(), which is not longer needed.
Removal was missed earlier.

PR kern/38761: new (?) race in buffer cache code

- Back out the previous workaround now that the sleep queue code has
been changed to never let the queue become empty if there are valid
waiters.
- Use sleepq_hashlock() to improve clarity.
- Sprinkle some assertions.

Fix for biowait hangs, and possibly other condvar hangs. Also should fix
PR kern/38761.

The condvar must access the sleepq with the sleepq lock held, doing so
is causing inconsistent sleepq state to be read.

This is because some accesses to the sleepq don't come via the cv code,
but are call directly into sleepq_changepri and sleepq_lendpri, which take
the sleepq lock, and removes then re-inserts lwps into the sleepq.

Running a build.sh with -j8 now completes on my quad-core, also tested by
Simon@ on a 8-core server and matt@ on a quad-core.

I believe there is room to be more efficient with this, as we now take the
sleepq lock for all cv_broadcast and cv_signal calls. I'll look into this
and post a diff to tech-kern.

branches: 1.22.2;
Disable the wakeup assertion for the time being because the tty code
triggers it.

Fix wmesg for !LOCKDEBUG.

- Give each condition variable its own sleep queue head. Helps the system
to scale more gracefully when there are thousands of active threads.
Proposed on tech-kern@.

- Use LOCKDEBUG to catch some errors in the use of condition variables:

freeing an active CV
re-initializing an active CV
using multiple distinct mutexes during concurrent waits
not holding the interlocking mutex when calling cv_broadcast/cv_signal
waking waiters and destroying the CV before they run and exit it

Broken assertion.

Take the mutex pointer and waiters count out of sleepq_t: the values can
be or are maintained elsewhere. Now a sleepq_t is just a TAILQ_HEAD.

branches: 1.17.2;
Remove clause 3 and 4 from TNF licenses

branches: 1.16.2; 1.16.4;
Add a boolean parameter to syncobj_t::sobj_unsleep. If true we want the
existing behaviour: the unsleep method unlocks and wakes the swapper if
needs be. If false, the caller is doing a batch operation and will take
care of that later. This is kind of ugly, but it's difficult for the caller
to know which lock to release in some situations.

- Add cv_is_valid(), for use in assertions. Performs basic sanity checks.
- Add more assertions.

branches: 1.14.10; 1.14.14;
Merge scheduler changes from the vmlocking branch. All discussed on
tech-kern:

- Invert priority space so that zero is the lowest priority. Rearrange
number and type of priority levels into bands. Add new bands like
'kernel real time'.
- Ignore the priority level passed to tsleep. Compute priority for
sleep dynamically.
- For SCHED_4BSD, make priority adjustment per-LWP, not per-process.

branches: 1.13.2; 1.13.4;
Merge from vmlocking: relax an assertion if panicstr != NULL.

branches: 1.12.2; 1.12.4; 1.12.6; 1.12.8;
cv_wakeup: the entire queue has to be searched, as we can't know how many
waiters there are.

Ressurect cv_wakeup() and use it on lbolt. Should fix PR kern/36714.
(background/foreground signal lossage in -current with various programs).

Improve assertions slightly. When awakening assert that the CV has not
been destroyed.

branches: 1.9.2;
Merge some of the less invasive changes from the vmlocking branch:

- kthread, callout, devsw API changes
- select()/poll() improvements
- miscellaneous MT safety improvements

merge yamt-idlelwp branch. asked by core@. some ports still needs work.

from doc/BRANCHES:

idle lwp, and some changes depending on it.

1. separate context switching and thread scheduling.
(cf. gmcgarry_ctxsw)
2. implement idle lwp.
3. clean up related MD/MI interfaces.
4. make scheduler(s) modular.

Make cv_has_waiters() return type bool.

- cv_wakeup: remove this. There are ~zero situations where it's useful.
- cv_wait and friends: after resuming execution, check to see if we have
been restarted as a result of cv_signal. If we have, but cannot take
the wakeup (because of eg a pending Unix signal or timeout) then try to
ensure that another LWP sees it. This is necessary because there may
be multiple waiters, and at least one should take the wakeup if possible.
Prompted by a discussion with pooka@.
- typedef struct lwp lwp_t;
- int -> bool, struct lwp -> lwp_t in a few places.

branches: 1.5.2; 1.5.4; 1.5.6;
typedef pri_t and use it instead of int and u_char.

implement priority inheritance.

branches: 1.3.2; 1.3.4;
unwrap short lines.

Merge newlock2 to head.

branches: 1.1.2;
file kern_condvar.c was initially added on branch newlock2.

- Simplify how priority boost for blocking in kernel is handled. Rather
than setting it up at each site where we block, make it a property of
syncobj_t. Then, do not hang onto the priority boost until userret(),
drop it as soon as the LWP is out of the run queue and onto a CPU.
Holding onto it longer is of questionable benefit.

- This allows two members of lwp_t to be deleted, and mi_userret() to be
simplified a lot (next step: trim it down to a single conditional).

- While here, constify syncobj_t and de-inline a bunch of small functions
like lwp_lock() which turn out not to be small after all (I don't know
why, but atomic_*_relaxed() seem to provoke a compiler shitfit above and
beyond what volatile does).

kern: New struct syncobj::sobj_name member for diagnostics.

XXX potential kernel ABI change -- not sure any modules actually use
struct syncobj but it's hard to rule that out because sys/syncobj.h
leaks into sys/lwp.h

sleepq(9): Pass syncobj through to sleepq_block.

Previously the usage pattern was:

sleepq_enter(sq, l, lock); // locks l
...
sleepq_enqueue(sq, ..., sobj, ...); // assumes l locked, sets l_syncobj
... (*)
sleepq_block(...); // unlocks l

As long as l remains locked from sleepq_enter to sleepq_block,
l_syncobj is stable, and sleepq_block uses it via ktrcsw to determine
whether the sleep is on a mutex in order to avoid creating ktrace
context-switch records (which involves allocation which is forbidden
in softint context, while taking and even sleeping for a mutex is
allowed).

However, in turnstile_block, the logic at (*) also involves
turnstile_lendpri, which sometimes unlocks and relocks l. At that
point, another thread can swoop in and sleepq_remove l, which sets
l_syncobj to sched_syncobj. If that happens, ktrcsw does what is
forbidden -- tries to allocate a ktrace record for the context
switch.

As an optimization, sleepq_block or turnstile_block could stop early
if it detects that l_syncobj doesn't match -- we've already been
requested to wake up at this point so there's no need to mi_switch.
(And then it would be unnecessary to pass the syncobj through
sleepq_block, because l_syncobj would remain stable.) But I'll leave
that to another change.

Reported-by: syzbot+8b9d7b066c32dbcdc63b@syzkaller.appspotmail.com

PR/55664: Ruslan Nikolaev: Split out sleepq guts and turnstiles not used
in rump into a separate header file. Add a sleepq_destroy() empty hook.

branches: 1.52.2;
Remove timedwaitclock.

This did not fix the bug I hoped it would fix in futex, and needs
more design thought. Might redo it somewhat differently later.

New timedwaitclock_setup.

C99 initializers would have been nice, but part of the struct is
explicit parameters and part of the struct is implicit state, and
-Wmissing-field-initializers can't discriminate between them
(although for some reason it doesn't always fire!).

Instead, just do:

struct timedwaitclock T;

timedwaitclock_setup(&T, timeout, clockid, flags, epsilon);
while (...) {
error = timedwaitclock_begin(&T, &timo);
if (error)
...
error = waitwhatever(timo);
timedwaitclock_end(&T);
...
}

Move timedwaitclock_begin() and timedwaitclock_end() to subr_time.c
so they can be used by other things.

New cv_timedwaitclock, cv_timedwaitclock_sig.

Usage: given a struct timespec timeout copied from userland, along
with a clockid and TIMER_* flags,

error = cv_timedwaitclock(cv, lock, timeout, clockid, flags,
DEFAULT_TIMEOUT_EPSILON);
if (error)
/* fail */

If flags is relative (i.e., (flags & TIMER_ABSTIME) == 0), then this
deducts the time spent waiting from timeout, so you can run it in a
loop:

struct timespec timeout;

error = copyin(SCARG(uap, timeout), &timeout, sizeof timeout);
if (error)
return error;

mutex_enter(lock);
while (!ready()) {
error = cv_timedwaitclock_sig(cv, lock, &timeout,
SCARG(uap, clockid), SCARG(uap, flags),
DEFAULT_TIMEOUT_EPSILON);
if (error)
break;
}
mutex_exit(lock);

CAVEAT: If the system call is interrupted by a signal with SA_RESTART
so cv_timedwaitclock_sig fails with ERESTART, then the system call
will be restarted with the _original_ relative timeout, not counting
the time that was already spent waiting. This is a problem but it's
not a problem I want to deal with at the moment.

Fix edge cases in cv_timedwaitbt, cv_timedwaitbt_sig.

- If the timeout is exactly zero, fail immediately with EWOULDBLOCK.

- If the timeout is just so small it would be rounded to zero ticks,
make sure to wait at least one tick.

- Make sure we never return with a negative timeout left.

Set LW_SINTR earlier so it doesn't pose a problem for doing interruptable
waits with turnstiles (not currently done).

hardclock_ticks -> getticks()

- Make this needed sequence always work for condvars, by not touching the CV
again after wakeup. Previously it could panic because cv_signal() could
be called by cv_wait_sig() + others:

cv_broadcast(cv);
cv_destroy(cv);

- In support of the above, if an LWP doing a timed wait is awoken by
cv_broadcast() or cv_signal(), don't return an error if the timer
fires after the fact, i.e. either succeed or fail, not both.

- Remove LOCKDEBUG code for CVs which never worked properly and is of
questionable use.

branches: 1.44.2;
Change sleepq_t from a TAILQ to a LIST and remove SOBJ_SLEEPQ_FIFO. Only
select/poll used the FIFO method and that was for collisions which rarely
occur. Shrinks sleep_t and condvar_t.

- List all of the syncobjs in syncobj.h.
- Update a comment.

branches: 1.42.2;
- Put back a microoptimisation that was accidentally removed.
- Comments.

branches: 1.41.4;
Apply C99-style struct initialization to syncobj_t

Apply C99-style struct initialization to lockops_t

Apply same treatment to cv_timedwaitbt.

Clarify interpretation of timeout/epsilon in cv_timedwaitbt.

Add cv_timedwaitbt, cv_timedwaitbt_sig.

Takes struct bintime maximum delay, and decrements it in place so
that you can use it in a loop in case of spurious wakeup.

Discussed on tech-kern a couple years ago:

https://mail-index.netbsd.org/tech-kern/2015/03/23/msg018557.html

Added a parameter for expressing desired precision -- not currently
interpreted, but intended for a future tickless kernel with a choice
of high-resolution timers.

allow cv_signal() immediately followed by cv_destroy().
this sequence is used by ZFS in a couple places and by supporting it
natively we can undo our local ZFS changes that avoided it.
note that this is only legal when all of the waiters use cv_wait()
and not any of the other variations, and lockdebug will catch
any violations of this rule.

branches: 1.35.10;
o Don't include sys/sched.h. Scheduler-related operation is done by
sleepq(9) via SOBJ_SLEEPQ_SORTED.

o Include sys/lwp.h instead of sys/proc.h.

branches: 1.34.6;
Mark a diagnostic-only variable

nodebug is only used with LOCKDEBUG

branches: 1.32.6;
also comment on the meaning of timo=0 for cv_timedwait_sig.

Add comments saying that a cv_timedwait and sleepq_block interpret
timo = 0 as an infinite timeout. This is already documented in the
cv_timedwait(9) man page, and there is no sleeq_block(9) man page.

branches: 1.30.2; 1.30.12;
These don't need uvm/uvm_extern.h.

Typo fix.

branches: 1.28.4; 1.28.6;
tsleep() on lbolt is now illegal. Convert cv_wakeup(&lbolt) to
cv_broadcast(&lbolt) and get rid of the prior.

Remove uarea swap-out functionality:

- Addresses the issue described in PR/38828.
- Some simplification in threading and sleepq subsystems.
- Eliminates pmap_collect() and, as a side note, allows pmap optimisations.
- Eliminates XS_CTL_DATA_ONSTACK in scsipi code.
- Avoids few scans on LWP list and thus potentially long holds of proc_lock.
- Cuts ~1.5k lines of code. Reduces amd64 kernel size by ~4k.
- Removes __SWAP_BROKEN cases.

Tested on x86, mips, acorn32 (thanks <mpumford>) and partly tested on
acorn26 (thanks to <bjh21>).

Discussed on <tech-kern>, reviewed by <ad>.

Make condvars really opaque -- hide the wait message member from consumers
of the API.

branches: 1.25.4;
PR kern/38761: new (?) race in buffer cache code

Back out the workaround from cv_has_waiters(), which is not longer needed.
Removal was missed earlier.

PR kern/38761: new (?) race in buffer cache code

- Back out the previous workaround now that the sleep queue code has
been changed to never let the queue become empty if there are valid
waiters.
- Use sleepq_hashlock() to improve clarity.
- Sprinkle some assertions.

Fix for biowait hangs, and possibly other condvar hangs. Also should fix
PR kern/38761.

The condvar must access the sleepq with the sleepq lock held, doing so
is causing inconsistent sleepq state to be read.

This is because some accesses to the sleepq don't come via the cv code,
but are call directly into sleepq_changepri and sleepq_lendpri, which take
the sleepq lock, and removes then re-inserts lwps into the sleepq.

Running a build.sh with -j8 now completes on my quad-core, also tested by
Simon@ on a 8-core server and matt@ on a quad-core.

I believe there is room to be more efficient with this, as we now take the
sleepq lock for all cv_broadcast and cv_signal calls. I'll look into this
and post a diff to tech-kern.

branches: 1.22.2;
Disable the wakeup assertion for the time being because the tty code
triggers it.

Fix wmesg for !LOCKDEBUG.

- Give each condition variable its own sleep queue head. Helps the system
to scale more gracefully when there are thousands of active threads.
Proposed on tech-kern@.

- Use LOCKDEBUG to catch some errors in the use of condition variables:

freeing an active CV
re-initializing an active CV
using multiple distinct mutexes during concurrent waits
not holding the interlocking mutex when calling cv_broadcast/cv_signal
waking waiters and destroying the CV before they run and exit it

Broken assertion.

Take the mutex pointer and waiters count out of sleepq_t: the values can
be or are maintained elsewhere. Now a sleepq_t is just a TAILQ_HEAD.

branches: 1.17.2;
Remove clause 3 and 4 from TNF licenses

branches: 1.16.2; 1.16.4;
Add a boolean parameter to syncobj_t::sobj_unsleep. If true we want the
existing behaviour: the unsleep method unlocks and wakes the swapper if
needs be. If false, the caller is doing a batch operation and will take
care of that later. This is kind of ugly, but it's difficult for the caller
to know which lock to release in some situations.

- Add cv_is_valid(), for use in assertions. Performs basic sanity checks.
- Add more assertions.

branches: 1.14.10; 1.14.14;
Merge scheduler changes from the vmlocking branch. All discussed on
tech-kern:

- Invert priority space so that zero is the lowest priority. Rearrange
number and type of priority levels into bands. Add new bands like
'kernel real time'.
- Ignore the priority level passed to tsleep. Compute priority for
sleep dynamically.
- For SCHED_4BSD, make priority adjustment per-LWP, not per-process.

branches: 1.13.2; 1.13.4;
Merge from vmlocking: relax an assertion if panicstr != NULL.

branches: 1.12.2; 1.12.4; 1.12.6; 1.12.8;
cv_wakeup: the entire queue has to be searched, as we can't know how many
waiters there are.

Ressurect cv_wakeup() and use it on lbolt. Should fix PR kern/36714.
(background/foreground signal lossage in -current with various programs).

Improve assertions slightly. When awakening assert that the CV has not
been destroyed.

branches: 1.9.2;
Merge some of the less invasive changes from the vmlocking branch:

- kthread, callout, devsw API changes
- select()/poll() improvements
- miscellaneous MT safety improvements

merge yamt-idlelwp branch. asked by core@. some ports still needs work.

from doc/BRANCHES:

idle lwp, and some changes depending on it.

1. separate context switching and thread scheduling.
(cf. gmcgarry_ctxsw)
2. implement idle lwp.
3. clean up related MD/MI interfaces.
4. make scheduler(s) modular.

Make cv_has_waiters() return type bool.

- cv_wakeup: remove this. There are ~zero situations where it's useful.
- cv_wait and friends: after resuming execution, check to see if we have
been restarted as a result of cv_signal. If we have, but cannot take
the wakeup (because of eg a pending Unix signal or timeout) then try to
ensure that another LWP sees it. This is necessary because there may
be multiple waiters, and at least one should take the wakeup if possible.
Prompted by a discussion with pooka@.
- typedef struct lwp lwp_t;
- int -> bool, struct lwp -> lwp_t in a few places.

branches: 1.5.2; 1.5.4; 1.5.6;
typedef pri_t and use it instead of int and u_char.

implement priority inheritance.

branches: 1.3.2; 1.3.4;
unwrap short lines.

Merge newlock2 to head.

branches: 1.1.2;
file kern_condvar.c was initially added on branch newlock2.

kern: New struct syncobj::sobj_name member for diagnostics.

XXX potential kernel ABI change -- not sure any modules actually use
struct syncobj but it's hard to rule that out because sys/syncobj.h
leaks into sys/lwp.h

sleepq(9): Pass syncobj through to sleepq_block.

Previously the usage pattern was:

sleepq_enter(sq, l, lock); // locks l
...
sleepq_enqueue(sq, ..., sobj, ...); // assumes l locked, sets l_syncobj
... (*)
sleepq_block(...); // unlocks l

As long as l remains locked from sleepq_enter to sleepq_block,
l_syncobj is stable, and sleepq_block uses it via ktrcsw to determine
whether the sleep is on a mutex in order to avoid creating ktrace
context-switch records (which involves allocation which is forbidden
in softint context, while taking and even sleeping for a mutex is
allowed).

However, in turnstile_block, the logic at (*) also involves
turnstile_lendpri, which sometimes unlocks and relocks l. At that
point, another thread can swoop in and sleepq_remove l, which sets
l_syncobj to sched_syncobj. If that happens, ktrcsw does what is
forbidden -- tries to allocate a ktrace record for the context
switch.

As an optimization, sleepq_block or turnstile_block could stop early
if it detects that l_syncobj doesn't match -- we've already been
requested to wake up at this point so there's no need to mi_switch.
(And then it would be unnecessary to pass the syncobj through
sleepq_block, because l_syncobj would remain stable.) But I'll leave
that to another change.

Reported-by: syzbot+8b9d7b066c32dbcdc63b@syzkaller.appspotmail.com

PR/55664: Ruslan Nikolaev: Split out sleepq guts and turnstiles not used
in rump into a separate header file. Add a sleepq_destroy() empty hook.

branches: 1.52.2;
Remove timedwaitclock.

This did not fix the bug I hoped it would fix in futex, and needs
more design thought. Might redo it somewhat differently later.

New timedwaitclock_setup.

C99 initializers would have been nice, but part of the struct is
explicit parameters and part of the struct is implicit state, and
-Wmissing-field-initializers can't discriminate between them
(although for some reason it doesn't always fire!).

Instead, just do:

struct timedwaitclock T;

timedwaitclock_setup(&T, timeout, clockid, flags, epsilon);
while (...) {
error = timedwaitclock_begin(&T, &timo);
if (error)
...
error = waitwhatever(timo);
timedwaitclock_end(&T);
...
}

Move timedwaitclock_begin() and timedwaitclock_end() to subr_time.c
so they can be used by other things.

New cv_timedwaitclock, cv_timedwaitclock_sig.

Usage: given a struct timespec timeout copied from userland, along
with a clockid and TIMER_* flags,

error = cv_timedwaitclock(cv, lock, timeout, clockid, flags,
DEFAULT_TIMEOUT_EPSILON);
if (error)
/* fail */

If flags is relative (i.e., (flags & TIMER_ABSTIME) == 0), then this
deducts the time spent waiting from timeout, so you can run it in a
loop:

struct timespec timeout;

error = copyin(SCARG(uap, timeout), &timeout, sizeof timeout);
if (error)
return error;

mutex_enter(lock);
while (!ready()) {
error = cv_timedwaitclock_sig(cv, lock, &timeout,
SCARG(uap, clockid), SCARG(uap, flags),
DEFAULT_TIMEOUT_EPSILON);
if (error)
break;
}
mutex_exit(lock);

CAVEAT: If the system call is interrupted by a signal with SA_RESTART
so cv_timedwaitclock_sig fails with ERESTART, then the system call
will be restarted with the _original_ relative timeout, not counting
the time that was already spent waiting. This is a problem but it's
not a problem I want to deal with at the moment.

Fix edge cases in cv_timedwaitbt, cv_timedwaitbt_sig.

- If the timeout is exactly zero, fail immediately with EWOULDBLOCK.

- If the timeout is just so small it would be rounded to zero ticks,
make sure to wait at least one tick.

- Make sure we never return with a negative timeout left.

Set LW_SINTR earlier so it doesn't pose a problem for doing interruptable
waits with turnstiles (not currently done).

hardclock_ticks -> getticks()