timeout: add TIMEOUT_MPSAFE flag

Add a TIMEOUT_MPSAFE flag to signal that a timeout is safe to run
without the kernel lock. Currently, TIMEOUT_MPSAFE requires
TIMEOUT_PROC. When the softclock() is unlocked in the future this
dependency will be removed.

On MULTIPROCESSOR kernels, softclock() now shunts TIMEOUT_MPSAFE
timeouts to a dedicated "timeout_proc_mp" bucket for processing by the
dedicated softclock_thread_mp() kthread. Unlike softclock_thread(),
softclock_thread_mp() is not pinned to any CPU and runs run at IPL_NONE.

Prompted by bluhm@. Lots of input from bluhm@. Joint work with mvs@.

Prompt: https://marc.info/?l=openbsd-tech&m=169646019109736&w=2
Thread: https://marc.info/?l=openbsd-tech&m=169652212131109&w=2

ok mvs@

timeout.9: document new interfaces, miscellaneous rewrites and cleanup

- Document timeout_abs_ts(9).
- Add the kclock arguments to timeout_set_flags(9) and
TIMEOUT_INITIALIZER_FLAGS(9).
- Document KCLOCK_NONE and KCLOCK_UPTIME.
- Mention the static initialization macros alongside timeout_set(9) etc.;
keep relevant information adjacent.
- Mention timeout_add_sec(9) etc. alongside timeout_add(9); keep
relevant information adjacent.

... plus many other cleanups, rewrites, and rearrangements.

Prompted by mvs@ and many others. With input from jmc@, mvs@, kn@,
schwarze@, and probably a few others I have forgotten.

v1: https://marc.info/?l=openbsd-tech&m=162449274513068&w=2
v2: https://marc.info/?l=openbsd-tech&m=165851505627764&w=2
v3: https://marc.info/?l=openbsd-tech&m=167250339811308&w=2

ok jmc@ mvs@ schwarze@

Document a locking constraint that applies to barriers.

OK cheloha@

man pages: add missing commas between subordinate and main clauses

jmc@ dislikes a comma before "then" in a conditional, so leave those
untouched.

ok jmc@

timeout_barrier(9), timeout_del_barrier(9): remove kernel lock

In timeout_barrier(9) we take/release the kernel lock to ensure that the
given timeout has finished running (if it had been running at all).

This approach is inefficient. If we put a barrier timeout on the
queue and wait for it to run in cond_wait(9) we can block instead of
spinning for the kernel lock. We already do this for process-context
timeouts in timeout_barrier(9) anyway.

Discussed with dlg@, visa@, and mpi@.

ok dlg@

Add missing timeout_set_proc() description.

ok jmc@

timeout(9): remove unused interfaces: timeout_add_ts(9), timeout_add_bt(9)

These two interfaces have been entirely unused since introduction.
Remove them and thin the "timeout" namespace a bit.

Discussed with mpi@ and ratchov@ almost a year ago, though I blocked
the change at that time. Also discussed with visa@.

ok visa@, mpi@

timeout(9): Add timeout_set_flags(9) and TIMEOUT_INITIALIZER_FLAGS(9)

These allow the caller to initialize timeouts with arbitrary flags. We
only have one flag at the moment, TIMEOUT_PROC, but experimenting with
other flags is easier if these interfaces are available in-tree.

With input from bluhm@, guenther@, and visa@.

"makes sense to me" bluhm@, ok visa@

Revert "timeout(9): switch to tickless backend"

It appears to have caused major performance regressions all over the
network stack.

Reported by bluhm@

ok deraadt@

timeout(9): switch to tickless backend

Rebase the timeout wheel on the system uptime clock. Timeouts are now
set to run at or after an absolute time as returned by nanouptime(9).
Timeouts are thus "tickless": they expire at a real time on that clock
instead of at a particular value of the global "ticks" variable.

To facilitate this change the timeout struct's .to_time member becomes a
timespec. Hashing timeouts into a bucket on the wheel changes slightly:
we build a 32-bit hash with 25 bits of seconds (.tv_sec) and 7 bits of
subseconds (.tv_nsec). 7 bits of subseconds means the width of the
lowest wheel level is now 2 seconds on all platforms and each bucket in
that lowest level corresponds to 1/128 seconds on the uptime clock.
These values were chosen to closely align with the current 100hz
hardclock(9) typical on almost all of our platforms. At 100hz a bucket
is currently ~1/100 seconds wide on the lowest level and the lowest
level itself is ~2.56 seconds wide. Not a huge change, but a change
nonetheless.

Because a bucket no longer corresponds to a single tick more than one
bucket may be dumped during an average timeout_hardclock_update() call.
On 100hz platforms you now dump ~2 buckets. On 64hz machines (sh) you
dump ~4 buckets. On 1024hz machines (alpha) you dump only 1 bucket,
but you are doing extra work in softclock() to reschedule timeouts
that aren't due yet.

To avoid changing current behavior all timeout_add*(9) interfaces
convert their timeout interval into ticks, compute an equivalent
timespec interval, and then add that interval to the timestamp of
the most recent timeout_hardclock_update() call to determine an
absolute deadline. So all current timeouts still "use" ticks,
but the ticks are faked in the timeout layer.

A new interface, timeout_at_ts(9), is introduced here to bypass this
backwardly compatible behavior. It will be used in subsequent diffs
to add absolute timeout support for userland and to clean up some of
the messier parts of kernel timekeeping, especially at the syscall
layer.

Because timeouts are based against the uptime clock they are subject to
NTP adjustment via adjtime(2) and adjfreq(2). Unless you have a crazy
adjfreq(2) adjustment set this will not change the expiration behavior
of your timeouts.

Tons of design feedback from mpi@, visa@, guenther@, and kettenis@.
Additional amd64 testing from anton@ and visa@. Octeon testing from visa@.
macppc testing from me.

Positive feedback from deraadt@, ok visa@

timeout.9: cite 1997 Varghese/Lauck timeout wheel paper; ok jmc@ schwarze@

Add lock order checking for timeouts

The caller of timeout_barrier() must not hold locks that could prevent
timeout handlers from making progress. The system could deadlock
otherwise.

This patch makes witness(4) able to detect barrier locking errors.
This is done by introducing a pseudo-lock that couples the lock chains
of barrier callers to the lock chains of timeout handlers.

In order to find these errors faster, this diff adds a synchronous
version of cancelling timeouts, timeout_del_barrier(9). As the
synchronous intent is explicit, this interface can check lock order
immediately instead of waiting for the potentially rare occurrence of
timeout_barrier(9).

OK dlg@ mpi@

add timeout_barrier, which is like intr_barrier and taskq_barrier.

if you're trying to free something that a timeout is using, you
have to wait for that timeout to finish running before doing the
free. timeout_del can stop a timeout from running in the future,
but it doesn't know if a timeout has finished being scheduled and
is now running.

previously you could know that timeouts are not running by simply
masking softclock interrupts on the cpu running the kernel. however,
code is now running outside the kernel lock, and timeouts can run
in a thread instead of softclock.

timeout_barrier solves the first problem by taking the kernel lock
and then masking softclock interrupts. that is enough to ensure
that any further timeout processing is waiting for those resources
to run again.

the second problem is solved by having timeout_barrier insert work
into the thread. when that work runs, that means all previous work
running in that thread has completed.

fixes and ok visa@, who thinks this will be useful for his work
too.

Introduce a new 'softclock' thread that will be used to execute timeout
callbacks needing a process context.

The function timeout_set_proc(9) has to be used instead of timeout_set(9)
when a timeout callback needs a process context.

Note that if such a timeout is waiting, understand sleeping, for a non
negligible amount of time it might delay other timeouts needing a process
context.

dlg@ agrees with this as a temporary solution.

Manpage tweaks from jmc@

ok kettenis@, bluhm@, mikeb@

Prevent a round to zero in the timeout_add_...() functions. Getting
an immediate timeout if a positive value is specified is unexpected
behavior. Defer calling the handler for at least one tick. Do not
change that timeout_add(0) gives you an immediate timeout.
OK millert@ uebayasi@ tedu@

add missing NAME entries;
feedback/ok schwarze

Remove useless quoting from .Fo and .Fn function names, to prevent
development of a cargo cult in case people look at existing files
for examples. This achieves a consistent .Fo and .Fn quoting style
across the whole tree.

Remove hzto(9) manual pages and references; OK dlg

describe the context the callback runs at in the CONTEXT section.

add TIMEOUT_INITIALIZER for initting timeout declaractions.

similar to TASK_INITIALIZER and all the queue _INITIALIZER things.

ok deraadt@

revery -r1.34's addition of spl(9) to SEE ALSO: we already have splclock(9)
in there, and they're one and the same page;

wrap long lines

document the timeout_add and timeout_del return values in the RETURN VALUES
section.

im not sure what to do with the macros yet.

document the contexts you can call this api from out into its own section

make timeout_add and its wrappers return whether the timeout was scheduled
in this call by returning 1, or a previous call by returning 0. this makes
it easy to refcount the stuff we're scheduling a timeout for, and brings
the api in line with what task_add(9) provides.

ok mpi@ matthew@ mikeb@ guenther@

Replace old-fashioned .Fd by new-fangled .In for #include lines.
Diff from Jan Klemkow <j dot klemkow at wemelug dot de> on tech@.
No objection from jmc@ against this type of change.

timeout_del now returns an int.

this could probably be explained a bit better :/

the api that these timeouts replaced doesnt exist in our tree anymore, so
dont talk about it.

ok krw@, millert@, miod@

Document timeout_add_msec().

oga pointed out that it was undocumented, which caused me to find out
that I had this diff in my tree.

`fine' deraadt

In the .Fn entries for timeout_add_usec/nsec, don't call the parameter
``sec''. Instead, use usec/nsec.

Agreed with/no opposition from blambert.

Add timeout_add_sec() etc. to .Nm and, on jmc's request, tweak
some other stuff.

ok art jmc blambert

Document the new timeout_add_* functions.

sleep(9) was removed aeons ago according to miod, so remove references
to it. Because man pages are named after functions (at least they
should be) and sleep(9) doesn't exist anymore, sleep.9 is renamed to
tsleep.9.

Input and reminders from jmc and ratchov.

convert to new .Dd format;

add timeout_triggered to .Nm;

Note: i am not touching MLINK for untimeout(9), ugly though that word is,
since it seems to have a historical basis...

`Ns' implies `No', so `Ns No' -> `Ns'; (even simpler in adduser(8))
discussed with todd@

license cleaning.

typos;

ok tedu@

Reword to get rid of second person.

Xr tvtohz.

New scalable implementation with constant time add and delete. ok deraadt@

The old timeout API is gone.

Change references to hardclock to .Xr where it seem appropriate

Various man page fixes and improvements from gluk@

Document timeout_triggered

Add function types.

General man page cleanups, mostly to remove trailing whitespace, hard
sentence breaks, and other such things.

While I'm reading this, complete the NAME section and fix a typo.

Err, make it splclock(9), so it's more clear to the reader.

Xr spl(9)

Various fixes.
From millert@

fix typo preapared -> prepared

Better explaination, various fixes.

Document timeout_pending and timeout_initialized.

Document the new timeout API.

Minor fusses: OpenBSD tag, misused macros, codes references path.

Import some documentation from NetBSD, after checking that details match.

hz.9 and hzto.9 from scratch

timeout.9: document new interfaces, miscellaneous rewrites and cleanup

- Document timeout_abs_ts(9).
- Add the kclock arguments to timeout_set_flags(9) and
TIMEOUT_INITIALIZER_FLAGS(9).
- Document KCLOCK_NONE and KCLOCK_UPTIME.
- Mention the static initialization macros alongside timeout_set(9) etc.;
keep relevant information adjacent.
- Mention timeout_add_sec(9) etc. alongside timeout_add(9); keep
relevant information adjacent.

... plus many other cleanups, rewrites, and rearrangements.

Prompted by mvs@ and many others. With input from jmc@, mvs@, kn@,
schwarze@, and probably a few others I have forgotten.

v1: https://marc.info/?l=openbsd-tech&m=162449274513068&w=2
v2: https://marc.info/?l=openbsd-tech&m=165851505627764&w=2
v3: https://marc.info/?l=openbsd-tech&m=167250339811308&w=2

ok jmc@ mvs@ schwarze@

Document a locking constraint that applies to barriers.

OK cheloha@

man pages: add missing commas between subordinate and main clauses

jmc@ dislikes a comma before "then" in a conditional, so leave those
untouched.

ok jmc@

timeout_barrier(9), timeout_del_barrier(9): remove kernel lock

In timeout_barrier(9) we take/release the kernel lock to ensure that the
given timeout has finished running (if it had been running at all).

This approach is inefficient. If we put a barrier timeout on the
queue and wait for it to run in cond_wait(9) we can block instead of
spinning for the kernel lock. We already do this for process-context
timeouts in timeout_barrier(9) anyway.

Discussed with dlg@, visa@, and mpi@.

ok dlg@

Add missing timeout_set_proc() description.

ok jmc@

timeout(9): remove unused interfaces: timeout_add_ts(9), timeout_add_bt(9)

These two interfaces have been entirely unused since introduction.
Remove them and thin the "timeout" namespace a bit.

Discussed with mpi@ and ratchov@ almost a year ago, though I blocked
the change at that time. Also discussed with visa@.

ok visa@, mpi@

timeout(9): Add timeout_set_flags(9) and TIMEOUT_INITIALIZER_FLAGS(9)

These allow the caller to initialize timeouts with arbitrary flags. We
only have one flag at the moment, TIMEOUT_PROC, but experimenting with
other flags is easier if these interfaces are available in-tree.

With input from bluhm@, guenther@, and visa@.

"makes sense to me" bluhm@, ok visa@

Revert "timeout(9): switch to tickless backend"

It appears to have caused major performance regressions all over the
network stack.

Reported by bluhm@

ok deraadt@

timeout(9): switch to tickless backend

Rebase the timeout wheel on the system uptime clock. Timeouts are now
set to run at or after an absolute time as returned by nanouptime(9).
Timeouts are thus "tickless": they expire at a real time on that clock
instead of at a particular value of the global "ticks" variable.

To facilitate this change the timeout struct's .to_time member becomes a
timespec. Hashing timeouts into a bucket on the wheel changes slightly:
we build a 32-bit hash with 25 bits of seconds (.tv_sec) and 7 bits of
subseconds (.tv_nsec). 7 bits of subseconds means the width of the
lowest wheel level is now 2 seconds on all platforms and each bucket in
that lowest level corresponds to 1/128 seconds on the uptime clock.
These values were chosen to closely align with the current 100hz
hardclock(9) typical on almost all of our platforms. At 100hz a bucket
is currently ~1/100 seconds wide on the lowest level and the lowest
level itself is ~2.56 seconds wide. Not a huge change, but a change
nonetheless.

Because a bucket no longer corresponds to a single tick more than one
bucket may be dumped during an average timeout_hardclock_update() call.
On 100hz platforms you now dump ~2 buckets. On 64hz machines (sh) you
dump ~4 buckets. On 1024hz machines (alpha) you dump only 1 bucket,
but you are doing extra work in softclock() to reschedule timeouts
that aren't due yet.

To avoid changing current behavior all timeout_add*(9) interfaces
convert their timeout interval into ticks, compute an equivalent
timespec interval, and then add that interval to the timestamp of
the most recent timeout_hardclock_update() call to determine an
absolute deadline. So all current timeouts still "use" ticks,
but the ticks are faked in the timeout layer.

A new interface, timeout_at_ts(9), is introduced here to bypass this
backwardly compatible behavior. It will be used in subsequent diffs
to add absolute timeout support for userland and to clean up some of
the messier parts of kernel timekeeping, especially at the syscall
layer.

Because timeouts are based against the uptime clock they are subject to
NTP adjustment via adjtime(2) and adjfreq(2). Unless you have a crazy
adjfreq(2) adjustment set this will not change the expiration behavior
of your timeouts.

Tons of design feedback from mpi@, visa@, guenther@, and kettenis@.
Additional amd64 testing from anton@ and visa@. Octeon testing from visa@.
macppc testing from me.

Positive feedback from deraadt@, ok visa@

timeout.9: cite 1997 Varghese/Lauck timeout wheel paper; ok jmc@ schwarze@

Add lock order checking for timeouts

The caller of timeout_barrier() must not hold locks that could prevent
timeout handlers from making progress. The system could deadlock
otherwise.

This patch makes witness(4) able to detect barrier locking errors.
This is done by introducing a pseudo-lock that couples the lock chains
of barrier callers to the lock chains of timeout handlers.

In order to find these errors faster, this diff adds a synchronous
version of cancelling timeouts, timeout_del_barrier(9). As the
synchronous intent is explicit, this interface can check lock order
immediately instead of waiting for the potentially rare occurrence of
timeout_barrier(9).

OK dlg@ mpi@

add timeout_barrier, which is like intr_barrier and taskq_barrier.

if you're trying to free something that a timeout is using, you
have to wait for that timeout to finish running before doing the
free. timeout_del can stop a timeout from running in the future,
but it doesn't know if a timeout has finished being scheduled and
is now running.

previously you could know that timeouts are not running by simply
masking softclock interrupts on the cpu running the kernel. however,
code is now running outside the kernel lock, and timeouts can run
in a thread instead of softclock.

timeout_barrier solves the first problem by taking the kernel lock
and then masking softclock interrupts. that is enough to ensure
that any further timeout processing is waiting for those resources
to run again.

the second problem is solved by having timeout_barrier insert work
into the thread. when that work runs, that means all previous work
running in that thread has completed.

fixes and ok visa@, who thinks this will be useful for his work
too.

Introduce a new 'softclock' thread that will be used to execute timeout
callbacks needing a process context.

The function timeout_set_proc(9) has to be used instead of timeout_set(9)
when a timeout callback needs a process context.

Note that if such a timeout is waiting, understand sleeping, for a non
negligible amount of time it might delay other timeouts needing a process
context.

dlg@ agrees with this as a temporary solution.

Manpage tweaks from jmc@

ok kettenis@, bluhm@, mikeb@

Prevent a round to zero in the timeout_add_...() functions. Getting
an immediate timeout if a positive value is specified is unexpected
behavior. Defer calling the handler for at least one tick. Do not
change that timeout_add(0) gives you an immediate timeout.
OK millert@ uebayasi@ tedu@

add missing NAME entries;
feedback/ok schwarze

Remove useless quoting from .Fo and .Fn function names, to prevent
development of a cargo cult in case people look at existing files
for examples. This achieves a consistent .Fo and .Fn quoting style
across the whole tree.

Remove hzto(9) manual pages and references; OK dlg

describe the context the callback runs at in the CONTEXT section.

add TIMEOUT_INITIALIZER for initting timeout declaractions.

similar to TASK_INITIALIZER and all the queue _INITIALIZER things.

ok deraadt@

revery -r1.34's addition of spl(9) to SEE ALSO: we already have splclock(9)
in there, and they're one and the same page;

wrap long lines

document the timeout_add and timeout_del return values in the RETURN VALUES
section.

im not sure what to do with the macros yet.

document the contexts you can call this api from out into its own section

make timeout_add and its wrappers return whether the timeout was scheduled
in this call by returning 1, or a previous call by returning 0. this makes
it easy to refcount the stuff we're scheduling a timeout for, and brings
the api in line with what task_add(9) provides.

ok mpi@ matthew@ mikeb@ guenther@

Replace old-fashioned .Fd by new-fangled .In for #include lines.
Diff from Jan Klemkow <j dot klemkow at wemelug dot de> on tech@.
No objection from jmc@ against this type of change.

timeout_del now returns an int.

this could probably be explained a bit better :/

the api that these timeouts replaced doesnt exist in our tree anymore, so
dont talk about it.

ok krw@, millert@, miod@

Document timeout_add_msec().

oga pointed out that it was undocumented, which caused me to find out
that I had this diff in my tree.

`fine' deraadt

In the .Fn entries for timeout_add_usec/nsec, don't call the parameter
``sec''. Instead, use usec/nsec.

Agreed with/no opposition from blambert.

Add timeout_add_sec() etc. to .Nm and, on jmc's request, tweak
some other stuff.

ok art jmc blambert

Document the new timeout_add_* functions.

sleep(9) was removed aeons ago according to miod, so remove references
to it. Because man pages are named after functions (at least they
should be) and sleep(9) doesn't exist anymore, sleep.9 is renamed to
tsleep.9.

Input and reminders from jmc and ratchov.

convert to new .Dd format;

add timeout_triggered to .Nm;

Note: i am not touching MLINK for untimeout(9), ugly though that word is,
since it seems to have a historical basis...

`Ns' implies `No', so `Ns No' -> `Ns'; (even simpler in adduser(8))
discussed with todd@

license cleaning.

typos;

ok tedu@

Reword to get rid of second person.

Xr tvtohz.

New scalable implementation with constant time add and delete. ok deraadt@

The old timeout API is gone.

Change references to hardclock to .Xr where it seem appropriate

Various man page fixes and improvements from gluk@

Document timeout_triggered

Add function types.

General man page cleanups, mostly to remove trailing whitespace, hard
sentence breaks, and other such things.

While I'm reading this, complete the NAME section and fix a typo.

Err, make it splclock(9), so it's more clear to the reader.

Xr spl(9)

Various fixes.
From millert@

fix typo preapared -> prepared

Better explaination, various fixes.

Document timeout_pending and timeout_initialized.

Document the new timeout API.

Minor fusses: OpenBSD tag, misused macros, codes references path.

Import some documentation from NetBSD, after checking that details match.

hz.9 and hzto.9 from scratch

Document a locking constraint that applies to barriers.

OK cheloha@

man pages: add missing commas between subordinate and main clauses

jmc@ dislikes a comma before "then" in a conditional, so leave those
untouched.

ok jmc@

timeout_barrier(9), timeout_del_barrier(9): remove kernel lock

In timeout_barrier(9) we take/release the kernel lock to ensure that the
given timeout has finished running (if it had been running at all).

This approach is inefficient. If we put a barrier timeout on the
queue and wait for it to run in cond_wait(9) we can block instead of
spinning for the kernel lock. We already do this for process-context
timeouts in timeout_barrier(9) anyway.

Discussed with dlg@, visa@, and mpi@.

ok dlg@

Add missing timeout_set_proc() description.

ok jmc@

timeout(9): remove unused interfaces: timeout_add_ts(9), timeout_add_bt(9)

These two interfaces have been entirely unused since introduction.
Remove them and thin the "timeout" namespace a bit.

Discussed with mpi@ and ratchov@ almost a year ago, though I blocked
the change at that time. Also discussed with visa@.

ok visa@, mpi@

timeout(9): Add timeout_set_flags(9) and TIMEOUT_INITIALIZER_FLAGS(9)

These allow the caller to initialize timeouts with arbitrary flags. We
only have one flag at the moment, TIMEOUT_PROC, but experimenting with
other flags is easier if these interfaces are available in-tree.

With input from bluhm@, guenther@, and visa@.

"makes sense to me" bluhm@, ok visa@

Revert "timeout(9): switch to tickless backend"

It appears to have caused major performance regressions all over the
network stack.

Reported by bluhm@

ok deraadt@

timeout(9): switch to tickless backend

Rebase the timeout wheel on the system uptime clock. Timeouts are now
set to run at or after an absolute time as returned by nanouptime(9).
Timeouts are thus "tickless": they expire at a real time on that clock
instead of at a particular value of the global "ticks" variable.

To facilitate this change the timeout struct's .to_time member becomes a
timespec. Hashing timeouts into a bucket on the wheel changes slightly:
we build a 32-bit hash with 25 bits of seconds (.tv_sec) and 7 bits of
subseconds (.tv_nsec). 7 bits of subseconds means the width of the
lowest wheel level is now 2 seconds on all platforms and each bucket in
that lowest level corresponds to 1/128 seconds on the uptime clock.
These values were chosen to closely align with the current 100hz
hardclock(9) typical on almost all of our platforms. At 100hz a bucket
is currently ~1/100 seconds wide on the lowest level and the lowest
level itself is ~2.56 seconds wide. Not a huge change, but a change
nonetheless.

Because a bucket no longer corresponds to a single tick more than one
bucket may be dumped during an average timeout_hardclock_update() call.
On 100hz platforms you now dump ~2 buckets. On 64hz machines (sh) you
dump ~4 buckets. On 1024hz machines (alpha) you dump only 1 bucket,
but you are doing extra work in softclock() to reschedule timeouts
that aren't due yet.

To avoid changing current behavior all timeout_add*(9) interfaces
convert their timeout interval into ticks, compute an equivalent
timespec interval, and then add that interval to the timestamp of
the most recent timeout_hardclock_update() call to determine an
absolute deadline. So all current timeouts still "use" ticks,
but the ticks are faked in the timeout layer.

A new interface, timeout_at_ts(9), is introduced here to bypass this
backwardly compatible behavior. It will be used in subsequent diffs
to add absolute timeout support for userland and to clean up some of
the messier parts of kernel timekeeping, especially at the syscall
layer.

Because timeouts are based against the uptime clock they are subject to
NTP adjustment via adjtime(2) and adjfreq(2). Unless you have a crazy
adjfreq(2) adjustment set this will not change the expiration behavior
of your timeouts.

Tons of design feedback from mpi@, visa@, guenther@, and kettenis@.
Additional amd64 testing from anton@ and visa@. Octeon testing from visa@.
macppc testing from me.

Positive feedback from deraadt@, ok visa@

timeout.9: cite 1997 Varghese/Lauck timeout wheel paper; ok jmc@ schwarze@

Add lock order checking for timeouts

The caller of timeout_barrier() must not hold locks that could prevent
timeout handlers from making progress. The system could deadlock
otherwise.

This patch makes witness(4) able to detect barrier locking errors.
This is done by introducing a pseudo-lock that couples the lock chains
of barrier callers to the lock chains of timeout handlers.

In order to find these errors faster, this diff adds a synchronous
version of cancelling timeouts, timeout_del_barrier(9). As the
synchronous intent is explicit, this interface can check lock order
immediately instead of waiting for the potentially rare occurrence of
timeout_barrier(9).

OK dlg@ mpi@

add timeout_barrier, which is like intr_barrier and taskq_barrier.

if you're trying to free something that a timeout is using, you
have to wait for that timeout to finish running before doing the
free. timeout_del can stop a timeout from running in the future,
but it doesn't know if a timeout has finished being scheduled and
is now running.

previously you could know that timeouts are not running by simply
masking softclock interrupts on the cpu running the kernel. however,
code is now running outside the kernel lock, and timeouts can run
in a thread instead of softclock.

timeout_barrier solves the first problem by taking the kernel lock
and then masking softclock interrupts. that is enough to ensure
that any further timeout processing is waiting for those resources
to run again.

the second problem is solved by having timeout_barrier insert work
into the thread. when that work runs, that means all previous work
running in that thread has completed.

fixes and ok visa@, who thinks this will be useful for his work
too.

Introduce a new 'softclock' thread that will be used to execute timeout
callbacks needing a process context.

The function timeout_set_proc(9) has to be used instead of timeout_set(9)
when a timeout callback needs a process context.

Note that if such a timeout is waiting, understand sleeping, for a non
negligible amount of time it might delay other timeouts needing a process
context.

dlg@ agrees with this as a temporary solution.

Manpage tweaks from jmc@

ok kettenis@, bluhm@, mikeb@

Prevent a round to zero in the timeout_add_...() functions. Getting
an immediate timeout if a positive value is specified is unexpected
behavior. Defer calling the handler for at least one tick. Do not
change that timeout_add(0) gives you an immediate timeout.
OK millert@ uebayasi@ tedu@

add missing NAME entries;
feedback/ok schwarze

Remove useless quoting from .Fo and .Fn function names, to prevent
development of a cargo cult in case people look at existing files
for examples. This achieves a consistent .Fo and .Fn quoting style
across the whole tree.

Remove hzto(9) manual pages and references; OK dlg

describe the context the callback runs at in the CONTEXT section.

add TIMEOUT_INITIALIZER for initting timeout declaractions.

similar to TASK_INITIALIZER and all the queue _INITIALIZER things.

ok deraadt@

revery -r1.34's addition of spl(9) to SEE ALSO: we already have splclock(9)
in there, and they're one and the same page;

wrap long lines

document the timeout_add and timeout_del return values in the RETURN VALUES
section.

im not sure what to do with the macros yet.

document the contexts you can call this api from out into its own section

make timeout_add and its wrappers return whether the timeout was scheduled
in this call by returning 1, or a previous call by returning 0. this makes
it easy to refcount the stuff we're scheduling a timeout for, and brings
the api in line with what task_add(9) provides.

ok mpi@ matthew@ mikeb@ guenther@

Replace old-fashioned .Fd by new-fangled .In for #include lines.
Diff from Jan Klemkow <j dot klemkow at wemelug dot de> on tech@.
No objection from jmc@ against this type of change.

timeout_del now returns an int.

this could probably be explained a bit better :/

the api that these timeouts replaced doesnt exist in our tree anymore, so
dont talk about it.

ok krw@, millert@, miod@

Document timeout_add_msec().

oga pointed out that it was undocumented, which caused me to find out
that I had this diff in my tree.

`fine' deraadt

In the .Fn entries for timeout_add_usec/nsec, don't call the parameter
``sec''. Instead, use usec/nsec.

Agreed with/no opposition from blambert.

Add timeout_add_sec() etc. to .Nm and, on jmc's request, tweak
some other stuff.

ok art jmc blambert

Document the new timeout_add_* functions.

sleep(9) was removed aeons ago according to miod, so remove references
to it. Because man pages are named after functions (at least they
should be) and sleep(9) doesn't exist anymore, sleep.9 is renamed to
tsleep.9.

Input and reminders from jmc and ratchov.

convert to new .Dd format;

add timeout_triggered to .Nm;

Note: i am not touching MLINK for untimeout(9), ugly though that word is,
since it seems to have a historical basis...

`Ns' implies `No', so `Ns No' -> `Ns'; (even simpler in adduser(8))
discussed with todd@

license cleaning.

typos;

ok tedu@

Reword to get rid of second person.

Xr tvtohz.

New scalable implementation with constant time add and delete. ok deraadt@

The old timeout API is gone.

Change references to hardclock to .Xr where it seem appropriate

Various man page fixes and improvements from gluk@

Document timeout_triggered

Add function types.

General man page cleanups, mostly to remove trailing whitespace, hard
sentence breaks, and other such things.

While I'm reading this, complete the NAME section and fix a typo.

Err, make it splclock(9), so it's more clear to the reader.

Xr spl(9)

Various fixes.
From millert@

fix typo preapared -> prepared

Better explaination, various fixes.

Document timeout_pending and timeout_initialized.

Document the new timeout API.

Minor fusses: OpenBSD tag, misused macros, codes references path.

Import some documentation from NetBSD, after checking that details match.

hz.9 and hzto.9 from scratch

man pages: add missing commas between subordinate and main clauses

jmc@ dislikes a comma before "then" in a conditional, so leave those
untouched.

ok jmc@

timeout_barrier(9), timeout_del_barrier(9): remove kernel lock

In timeout_barrier(9) we take/release the kernel lock to ensure that the
given timeout has finished running (if it had been running at all).

This approach is inefficient. If we put a barrier timeout on the
queue and wait for it to run in cond_wait(9) we can block instead of
spinning for the kernel lock. We already do this for process-context
timeouts in timeout_barrier(9) anyway.

Discussed with dlg@, visa@, and mpi@.

ok dlg@

Add missing timeout_set_proc() description.

ok jmc@

timeout(9): remove unused interfaces: timeout_add_ts(9), timeout_add_bt(9)

These two interfaces have been entirely unused since introduction.
Remove them and thin the "timeout" namespace a bit.

Discussed with mpi@ and ratchov@ almost a year ago, though I blocked
the change at that time. Also discussed with visa@.

ok visa@, mpi@

timeout(9): Add timeout_set_flags(9) and TIMEOUT_INITIALIZER_FLAGS(9)

These allow the caller to initialize timeouts with arbitrary flags. We
only have one flag at the moment, TIMEOUT_PROC, but experimenting with
other flags is easier if these interfaces are available in-tree.

With input from bluhm@, guenther@, and visa@.

"makes sense to me" bluhm@, ok visa@

Revert "timeout(9): switch to tickless backend"

It appears to have caused major performance regressions all over the
network stack.

Reported by bluhm@

ok deraadt@

timeout(9): switch to tickless backend

Rebase the timeout wheel on the system uptime clock. Timeouts are now
set to run at or after an absolute time as returned by nanouptime(9).
Timeouts are thus "tickless": they expire at a real time on that clock
instead of at a particular value of the global "ticks" variable.

To facilitate this change the timeout struct's .to_time member becomes a
timespec. Hashing timeouts into a bucket on the wheel changes slightly:
we build a 32-bit hash with 25 bits of seconds (.tv_sec) and 7 bits of
subseconds (.tv_nsec). 7 bits of subseconds means the width of the
lowest wheel level is now 2 seconds on all platforms and each bucket in
that lowest level corresponds to 1/128 seconds on the uptime clock.
These values were chosen to closely align with the current 100hz
hardclock(9) typical on almost all of our platforms. At 100hz a bucket
is currently ~1/100 seconds wide on the lowest level and the lowest
level itself is ~2.56 seconds wide. Not a huge change, but a change
nonetheless.

Because a bucket no longer corresponds to a single tick more than one
bucket may be dumped during an average timeout_hardclock_update() call.
On 100hz platforms you now dump ~2 buckets. On 64hz machines (sh) you
dump ~4 buckets. On 1024hz machines (alpha) you dump only 1 bucket,
but you are doing extra work in softclock() to reschedule timeouts
that aren't due yet.

To avoid changing current behavior all timeout_add*(9) interfaces
convert their timeout interval into ticks, compute an equivalent
timespec interval, and then add that interval to the timestamp of
the most recent timeout_hardclock_update() call to determine an
absolute deadline. So all current timeouts still "use" ticks,
but the ticks are faked in the timeout layer.

A new interface, timeout_at_ts(9), is introduced here to bypass this
backwardly compatible behavior. It will be used in subsequent diffs
to add absolute timeout support for userland and to clean up some of
the messier parts of kernel timekeeping, especially at the syscall
layer.

Because timeouts are based against the uptime clock they are subject to
NTP adjustment via adjtime(2) and adjfreq(2). Unless you have a crazy
adjfreq(2) adjustment set this will not change the expiration behavior
of your timeouts.

Tons of design feedback from mpi@, visa@, guenther@, and kettenis@.
Additional amd64 testing from anton@ and visa@. Octeon testing from visa@.
macppc testing from me.

Positive feedback from deraadt@, ok visa@

timeout.9: cite 1997 Varghese/Lauck timeout wheel paper; ok jmc@ schwarze@

Add lock order checking for timeouts

The caller of timeout_barrier() must not hold locks that could prevent
timeout handlers from making progress. The system could deadlock
otherwise.

This patch makes witness(4) able to detect barrier locking errors.
This is done by introducing a pseudo-lock that couples the lock chains
of barrier callers to the lock chains of timeout handlers.

In order to find these errors faster, this diff adds a synchronous
version of cancelling timeouts, timeout_del_barrier(9). As the
synchronous intent is explicit, this interface can check lock order
immediately instead of waiting for the potentially rare occurrence of
timeout_barrier(9).

OK dlg@ mpi@

add timeout_barrier, which is like intr_barrier and taskq_barrier.

if you're trying to free something that a timeout is using, you
have to wait for that timeout to finish running before doing the
free. timeout_del can stop a timeout from running in the future,
but it doesn't know if a timeout has finished being scheduled and
is now running.

previously you could know that timeouts are not running by simply
masking softclock interrupts on the cpu running the kernel. however,
code is now running outside the kernel lock, and timeouts can run
in a thread instead of softclock.

timeout_barrier solves the first problem by taking the kernel lock
and then masking softclock interrupts. that is enough to ensure
that any further timeout processing is waiting for those resources
to run again.

the second problem is solved by having timeout_barrier insert work
into the thread. when that work runs, that means all previous work
running in that thread has completed.

fixes and ok visa@, who thinks this will be useful for his work
too.

Introduce a new 'softclock' thread that will be used to execute timeout
callbacks needing a process context.

The function timeout_set_proc(9) has to be used instead of timeout_set(9)
when a timeout callback needs a process context.

Note that if such a timeout is waiting, understand sleeping, for a non
negligible amount of time it might delay other timeouts needing a process
context.

dlg@ agrees with this as a temporary solution.

Manpage tweaks from jmc@

ok kettenis@, bluhm@, mikeb@

Prevent a round to zero in the timeout_add_...() functions. Getting
an immediate timeout if a positive value is specified is unexpected
behavior. Defer calling the handler for at least one tick. Do not
change that timeout_add(0) gives you an immediate timeout.
OK millert@ uebayasi@ tedu@

add missing NAME entries;
feedback/ok schwarze

Remove useless quoting from .Fo and .Fn function names, to prevent
development of a cargo cult in case people look at existing files
for examples. This achieves a consistent .Fo and .Fn quoting style
across the whole tree.

Remove hzto(9) manual pages and references; OK dlg

describe the context the callback runs at in the CONTEXT section.

add TIMEOUT_INITIALIZER for initting timeout declaractions.

similar to TASK_INITIALIZER and all the queue _INITIALIZER things.

ok deraadt@

revery -r1.34's addition of spl(9) to SEE ALSO: we already have splclock(9)
in there, and they're one and the same page;

wrap long lines

document the timeout_add and timeout_del return values in the RETURN VALUES
section.

im not sure what to do with the macros yet.

document the contexts you can call this api from out into its own section

make timeout_add and its wrappers return whether the timeout was scheduled
in this call by returning 1, or a previous call by returning 0. this makes
it easy to refcount the stuff we're scheduling a timeout for, and brings
the api in line with what task_add(9) provides.

ok mpi@ matthew@ mikeb@ guenther@

Replace old-fashioned .Fd by new-fangled .In for #include lines.
Diff from Jan Klemkow <j dot klemkow at wemelug dot de> on tech@.
No objection from jmc@ against this type of change.

timeout_del now returns an int.

this could probably be explained a bit better :/

the api that these timeouts replaced doesnt exist in our tree anymore, so
dont talk about it.

ok krw@, millert@, miod@

Document timeout_add_msec().

oga pointed out that it was undocumented, which caused me to find out
that I had this diff in my tree.

`fine' deraadt

In the .Fn entries for timeout_add_usec/nsec, don't call the parameter
``sec''. Instead, use usec/nsec.

Agreed with/no opposition from blambert.

Add timeout_add_sec() etc. to .Nm and, on jmc's request, tweak
some other stuff.

ok art jmc blambert

Document the new timeout_add_* functions.

sleep(9) was removed aeons ago according to miod, so remove references
to it. Because man pages are named after functions (at least they
should be) and sleep(9) doesn't exist anymore, sleep.9 is renamed to
tsleep.9.

Input and reminders from jmc and ratchov.

convert to new .Dd format;

add timeout_triggered to .Nm;

Note: i am not touching MLINK for untimeout(9), ugly though that word is,
since it seems to have a historical basis...

`Ns' implies `No', so `Ns No' -> `Ns'; (even simpler in adduser(8))
discussed with todd@

license cleaning.

typos;

ok tedu@

Reword to get rid of second person.

Xr tvtohz.

New scalable implementation with constant time add and delete. ok deraadt@

The old timeout API is gone.

Change references to hardclock to .Xr where it seem appropriate

Various man page fixes and improvements from gluk@

Document timeout_triggered

Add function types.

General man page cleanups, mostly to remove trailing whitespace, hard
sentence breaks, and other such things.

While I'm reading this, complete the NAME section and fix a typo.

Err, make it splclock(9), so it's more clear to the reader.

Xr spl(9)

Various fixes.
From millert@

fix typo preapared -> prepared

Better explaination, various fixes.

Document timeout_pending and timeout_initialized.

Document the new timeout API.

Minor fusses: OpenBSD tag, misused macros, codes references path.

Import some documentation from NetBSD, after checking that details match.

hz.9 and hzto.9 from scratch

timeout_barrier(9), timeout_del_barrier(9): remove kernel lock

In timeout_barrier(9) we take/release the kernel lock to ensure that the
given timeout has finished running (if it had been running at all).

This approach is inefficient. If we put a barrier timeout on the
queue and wait for it to run in cond_wait(9) we can block instead of
spinning for the kernel lock. We already do this for process-context
timeouts in timeout_barrier(9) anyway.

Discussed with dlg@, visa@, and mpi@.

ok dlg@

Add missing timeout_set_proc() description.

ok jmc@

timeout(9): remove unused interfaces: timeout_add_ts(9), timeout_add_bt(9)

These two interfaces have been entirely unused since introduction.
Remove them and thin the "timeout" namespace a bit.

Discussed with mpi@ and ratchov@ almost a year ago, though I blocked
the change at that time. Also discussed with visa@.

ok visa@, mpi@

timeout(9): Add timeout_set_flags(9) and TIMEOUT_INITIALIZER_FLAGS(9)

These allow the caller to initialize timeouts with arbitrary flags. We
only have one flag at the moment, TIMEOUT_PROC, but experimenting with
other flags is easier if these interfaces are available in-tree.

With input from bluhm@, guenther@, and visa@.

"makes sense to me" bluhm@, ok visa@

Revert "timeout(9): switch to tickless backend"

It appears to have caused major performance regressions all over the
network stack.

Reported by bluhm@

ok deraadt@

timeout(9): switch to tickless backend

Rebase the timeout wheel on the system uptime clock. Timeouts are now
set to run at or after an absolute time as returned by nanouptime(9).
Timeouts are thus "tickless": they expire at a real time on that clock
instead of at a particular value of the global "ticks" variable.

To facilitate this change the timeout struct's .to_time member becomes a
timespec. Hashing timeouts into a bucket on the wheel changes slightly:
we build a 32-bit hash with 25 bits of seconds (.tv_sec) and 7 bits of
subseconds (.tv_nsec). 7 bits of subseconds means the width of the
lowest wheel level is now 2 seconds on all platforms and each bucket in
that lowest level corresponds to 1/128 seconds on the uptime clock.
These values were chosen to closely align with the current 100hz
hardclock(9) typical on almost all of our platforms. At 100hz a bucket
is currently ~1/100 seconds wide on the lowest level and the lowest
level itself is ~2.56 seconds wide. Not a huge change, but a change
nonetheless.

Because a bucket no longer corresponds to a single tick more than one
bucket may be dumped during an average timeout_hardclock_update() call.
On 100hz platforms you now dump ~2 buckets. On 64hz machines (sh) you
dump ~4 buckets. On 1024hz machines (alpha) you dump only 1 bucket,
but you are doing extra work in softclock() to reschedule timeouts
that aren't due yet.

To avoid changing current behavior all timeout_add*(9) interfaces
convert their timeout interval into ticks, compute an equivalent
timespec interval, and then add that interval to the timestamp of
the most recent timeout_hardclock_update() call to determine an
absolute deadline. So all current timeouts still "use" ticks,
but the ticks are faked in the timeout layer.

A new interface, timeout_at_ts(9), is introduced here to bypass this
backwardly compatible behavior. It will be used in subsequent diffs
to add absolute timeout support for userland and to clean up some of
the messier parts of kernel timekeeping, especially at the syscall
layer.

Because timeouts are based against the uptime clock they are subject to
NTP adjustment via adjtime(2) and adjfreq(2). Unless you have a crazy
adjfreq(2) adjustment set this will not change the expiration behavior
of your timeouts.

Tons of design feedback from mpi@, visa@, guenther@, and kettenis@.
Additional amd64 testing from anton@ and visa@. Octeon testing from visa@.
macppc testing from me.

Positive feedback from deraadt@, ok visa@

timeout.9: cite 1997 Varghese/Lauck timeout wheel paper; ok jmc@ schwarze@

Add lock order checking for timeouts

The caller of timeout_barrier() must not hold locks that could prevent
timeout handlers from making progress. The system could deadlock
otherwise.

This patch makes witness(4) able to detect barrier locking errors.
This is done by introducing a pseudo-lock that couples the lock chains
of barrier callers to the lock chains of timeout handlers.

In order to find these errors faster, this diff adds a synchronous
version of cancelling timeouts, timeout_del_barrier(9). As the
synchronous intent is explicit, this interface can check lock order
immediately instead of waiting for the potentially rare occurrence of
timeout_barrier(9).

OK dlg@ mpi@

add timeout_barrier, which is like intr_barrier and taskq_barrier.

if you're trying to free something that a timeout is using, you
have to wait for that timeout to finish running before doing the
free. timeout_del can stop a timeout from running in the future,
but it doesn't know if a timeout has finished being scheduled and
is now running.

previously you could know that timeouts are not running by simply
masking softclock interrupts on the cpu running the kernel. however,
code is now running outside the kernel lock, and timeouts can run
in a thread instead of softclock.

timeout_barrier solves the first problem by taking the kernel lock
and then masking softclock interrupts. that is enough to ensure
that any further timeout processing is waiting for those resources
to run again.

the second problem is solved by having timeout_barrier insert work
into the thread. when that work runs, that means all previous work
running in that thread has completed.

fixes and ok visa@, who thinks this will be useful for his work
too.

Introduce a new 'softclock' thread that will be used to execute timeout
callbacks needing a process context.

The function timeout_set_proc(9) has to be used instead of timeout_set(9)
when a timeout callback needs a process context.

Note that if such a timeout is waiting, understand sleeping, for a non
negligible amount of time it might delay other timeouts needing a process
context.

dlg@ agrees with this as a temporary solution.

Manpage tweaks from jmc@

ok kettenis@, bluhm@, mikeb@

Prevent a round to zero in the timeout_add_...() functions. Getting
an immediate timeout if a positive value is specified is unexpected
behavior. Defer calling the handler for at least one tick. Do not
change that timeout_add(0) gives you an immediate timeout.
OK millert@ uebayasi@ tedu@

add missing NAME entries;
feedback/ok schwarze

Remove useless quoting from .Fo and .Fn function names, to prevent
development of a cargo cult in case people look at existing files
for examples. This achieves a consistent .Fo and .Fn quoting style
across the whole tree.

Remove hzto(9) manual pages and references; OK dlg

describe the context the callback runs at in the CONTEXT section.

add TIMEOUT_INITIALIZER for initting timeout declaractions.

similar to TASK_INITIALIZER and all the queue _INITIALIZER things.

ok deraadt@

revery -r1.34's addition of spl(9) to SEE ALSO: we already have splclock(9)
in there, and they're one and the same page;

wrap long lines

document the timeout_add and timeout_del return values in the RETURN VALUES
section.

im not sure what to do with the macros yet.

document the contexts you can call this api from out into its own section

make timeout_add and its wrappers return whether the timeout was scheduled
in this call by returning 1, or a previous call by returning 0. this makes
it easy to refcount the stuff we're scheduling a timeout for, and brings
the api in line with what task_add(9) provides.

ok mpi@ matthew@ mikeb@ guenther@

Replace old-fashioned .Fd by new-fangled .In for #include lines.
Diff from Jan Klemkow <j dot klemkow at wemelug dot de> on tech@.
No objection from jmc@ against this type of change.

timeout_del now returns an int.

this could probably be explained a bit better :/

the api that these timeouts replaced doesnt exist in our tree anymore, so
dont talk about it.

ok krw@, millert@, miod@

Document timeout_add_msec().

oga pointed out that it was undocumented, which caused me to find out
that I had this diff in my tree.

`fine' deraadt

In the .Fn entries for timeout_add_usec/nsec, don't call the parameter
``sec''. Instead, use usec/nsec.

Agreed with/no opposition from blambert.

Add timeout_add_sec() etc. to .Nm and, on jmc's request, tweak
some other stuff.

ok art jmc blambert

Document the new timeout_add_* functions.

sleep(9) was removed aeons ago according to miod, so remove references
to it. Because man pages are named after functions (at least they
should be) and sleep(9) doesn't exist anymore, sleep.9 is renamed to
tsleep.9.

Input and reminders from jmc and ratchov.

convert to new .Dd format;

add timeout_triggered to .Nm;

Note: i am not touching MLINK for untimeout(9), ugly though that word is,
since it seems to have a historical basis...

`Ns' implies `No', so `Ns No' -> `Ns'; (even simpler in adduser(8))
discussed with todd@

license cleaning.

typos;

ok tedu@

Reword to get rid of second person.

Xr tvtohz.

New scalable implementation with constant time add and delete. ok deraadt@

The old timeout API is gone.

Change references to hardclock to .Xr where it seem appropriate

Various man page fixes and improvements from gluk@

Document timeout_triggered

Add function types.

General man page cleanups, mostly to remove trailing whitespace, hard
sentence breaks, and other such things.

While I'm reading this, complete the NAME section and fix a typo.

Err, make it splclock(9), so it's more clear to the reader.

Xr spl(9)

Various fixes.
From millert@

fix typo preapared -> prepared

Better explaination, various fixes.

Document timeout_pending and timeout_initialized.

Document the new timeout API.

Minor fusses: OpenBSD tag, misused macros, codes references path.

Import some documentation from NetBSD, after checking that details match.

hz.9 and hzto.9 from scratch

Add missing timeout_set_proc() description.

ok jmc@

timeout(9): remove unused interfaces: timeout_add_ts(9), timeout_add_bt(9)

These two interfaces have been entirely unused since introduction.
Remove them and thin the "timeout" namespace a bit.

Discussed with mpi@ and ratchov@ almost a year ago, though I blocked
the change at that time. Also discussed with visa@.

ok visa@, mpi@

timeout(9): Add timeout_set_flags(9) and TIMEOUT_INITIALIZER_FLAGS(9)

These allow the caller to initialize timeouts with arbitrary flags. We
only have one flag at the moment, TIMEOUT_PROC, but experimenting with
other flags is easier if these interfaces are available in-tree.

With input from bluhm@, guenther@, and visa@.

"makes sense to me" bluhm@, ok visa@

Revert "timeout(9): switch to tickless backend"

It appears to have caused major performance regressions all over the
network stack.

Reported by bluhm@

ok deraadt@

timeout(9): switch to tickless backend

Rebase the timeout wheel on the system uptime clock. Timeouts are now
set to run at or after an absolute time as returned by nanouptime(9).
Timeouts are thus "tickless": they expire at a real time on that clock
instead of at a particular value of the global "ticks" variable.

To facilitate this change the timeout struct's .to_time member becomes a
timespec. Hashing timeouts into a bucket on the wheel changes slightly:
we build a 32-bit hash with 25 bits of seconds (.tv_sec) and 7 bits of
subseconds (.tv_nsec). 7 bits of subseconds means the width of the
lowest wheel level is now 2 seconds on all platforms and each bucket in
that lowest level corresponds to 1/128 seconds on the uptime clock.
These values were chosen to closely align with the current 100hz
hardclock(9) typical on almost all of our platforms. At 100hz a bucket
is currently ~1/100 seconds wide on the lowest level and the lowest
level itself is ~2.56 seconds wide. Not a huge change, but a change
nonetheless.

Because a bucket no longer corresponds to a single tick more than one
bucket may be dumped during an average timeout_hardclock_update() call.
On 100hz platforms you now dump ~2 buckets. On 64hz machines (sh) you
dump ~4 buckets. On 1024hz machines (alpha) you dump only 1 bucket,
but you are doing extra work in softclock() to reschedule timeouts
that aren't due yet.

To avoid changing current behavior all timeout_add*(9) interfaces
convert their timeout interval into ticks, compute an equivalent
timespec interval, and then add that interval to the timestamp of
the most recent timeout_hardclock_update() call to determine an
absolute deadline. So all current timeouts still "use" ticks,
but the ticks are faked in the timeout layer.

A new interface, timeout_at_ts(9), is introduced here to bypass this
backwardly compatible behavior. It will be used in subsequent diffs
to add absolute timeout support for userland and to clean up some of
the messier parts of kernel timekeeping, especially at the syscall
layer.

Because timeouts are based against the uptime clock they are subject to
NTP adjustment via adjtime(2) and adjfreq(2). Unless you have a crazy
adjfreq(2) adjustment set this will not change the expiration behavior
of your timeouts.

Tons of design feedback from mpi@, visa@, guenther@, and kettenis@.
Additional amd64 testing from anton@ and visa@. Octeon testing from visa@.
macppc testing from me.

Positive feedback from deraadt@, ok visa@

timeout.9: cite 1997 Varghese/Lauck timeout wheel paper; ok jmc@ schwarze@

Add lock order checking for timeouts

The caller of timeout_barrier() must not hold locks that could prevent
timeout handlers from making progress. The system could deadlock
otherwise.

This patch makes witness(4) able to detect barrier locking errors.
This is done by introducing a pseudo-lock that couples the lock chains
of barrier callers to the lock chains of timeout handlers.

In order to find these errors faster, this diff adds a synchronous
version of cancelling timeouts, timeout_del_barrier(9). As the
synchronous intent is explicit, this interface can check lock order
immediately instead of waiting for the potentially rare occurrence of
timeout_barrier(9).

OK dlg@ mpi@

add timeout_barrier, which is like intr_barrier and taskq_barrier.

if you're trying to free something that a timeout is using, you
have to wait for that timeout to finish running before doing the
free. timeout_del can stop a timeout from running in the future,
but it doesn't know if a timeout has finished being scheduled and
is now running.

previously you could know that timeouts are not running by simply
masking softclock interrupts on the cpu running the kernel. however,
code is now running outside the kernel lock, and timeouts can run
in a thread instead of softclock.

timeout_barrier solves the first problem by taking the kernel lock
and then masking softclock interrupts. that is enough to ensure
that any further timeout processing is waiting for those resources
to run again.

the second problem is solved by having timeout_barrier insert work
into the thread. when that work runs, that means all previous work
running in that thread has completed.

fixes and ok visa@, who thinks this will be useful for his work
too.

Introduce a new 'softclock' thread that will be used to execute timeout
callbacks needing a process context.

The function timeout_set_proc(9) has to be used instead of timeout_set(9)
when a timeout callback needs a process context.

Note that if such a timeout is waiting, understand sleeping, for a non
negligible amount of time it might delay other timeouts needing a process
context.

dlg@ agrees with this as a temporary solution.

Manpage tweaks from jmc@

ok kettenis@, bluhm@, mikeb@

Prevent a round to zero in the timeout_add_...() functions. Getting
an immediate timeout if a positive value is specified is unexpected
behavior. Defer calling the handler for at least one tick. Do not
change that timeout_add(0) gives you an immediate timeout.
OK millert@ uebayasi@ tedu@

add missing NAME entries;
feedback/ok schwarze

Remove useless quoting from .Fo and .Fn function names, to prevent
development of a cargo cult in case people look at existing files
for examples. This achieves a consistent .Fo and .Fn quoting style
across the whole tree.

Remove hzto(9) manual pages and references; OK dlg

describe the context the callback runs at in the CONTEXT section.

add TIMEOUT_INITIALIZER for initting timeout declaractions.

similar to TASK_INITIALIZER and all the queue _INITIALIZER things.

ok deraadt@

revery -r1.34's addition of spl(9) to SEE ALSO: we already have splclock(9)
in there, and they're one and the same page;

wrap long lines

document the timeout_add and timeout_del return values in the RETURN VALUES
section.

im not sure what to do with the macros yet.

document the contexts you can call this api from out into its own section

make timeout_add and its wrappers return whether the timeout was scheduled
in this call by returning 1, or a previous call by returning 0. this makes
it easy to refcount the stuff we're scheduling a timeout for, and brings
the api in line with what task_add(9) provides.

ok mpi@ matthew@ mikeb@ guenther@

Replace old-fashioned .Fd by new-fangled .In for #include lines.
Diff from Jan Klemkow <j dot klemkow at wemelug dot de> on tech@.
No objection from jmc@ against this type of change.

timeout_del now returns an int.

this could probably be explained a bit better :/

the api that these timeouts replaced doesnt exist in our tree anymore, so
dont talk about it.

ok krw@, millert@, miod@

Document timeout_add_msec().

oga pointed out that it was undocumented, which caused me to find out
that I had this diff in my tree.

`fine' deraadt

In the .Fn entries for timeout_add_usec/nsec, don't call the parameter
``sec''. Instead, use usec/nsec.

Agreed with/no opposition from blambert.

Add timeout_add_sec() etc. to .Nm and, on jmc's request, tweak
some other stuff.

ok art jmc blambert

Document the new timeout_add_* functions.

sleep(9) was removed aeons ago according to miod, so remove references
to it. Because man pages are named after functions (at least they
should be) and sleep(9) doesn't exist anymore, sleep.9 is renamed to
tsleep.9.

Input and reminders from jmc and ratchov.

convert to new .Dd format;

add timeout_triggered to .Nm;

Note: i am not touching MLINK for untimeout(9), ugly though that word is,
since it seems to have a historical basis...

`Ns' implies `No', so `Ns No' -> `Ns'; (even simpler in adduser(8))
discussed with todd@

license cleaning.

typos;

ok tedu@

Reword to get rid of second person.

Xr tvtohz.

New scalable implementation with constant time add and delete. ok deraadt@

The old timeout API is gone.

Change references to hardclock to .Xr where it seem appropriate

Various man page fixes and improvements from gluk@

Document timeout_triggered

Add function types.

General man page cleanups, mostly to remove trailing whitespace, hard
sentence breaks, and other such things.

While I'm reading this, complete the NAME section and fix a typo.

Err, make it splclock(9), so it's more clear to the reader.

Xr spl(9)

Various fixes.
From millert@

fix typo preapared -> prepared

Better explaination, various fixes.

Document timeout_pending and timeout_initialized.

Document the new timeout API.

Minor fusses: OpenBSD tag, misused macros, codes references path.

Import some documentation from NetBSD, after checking that details match.

hz.9 and hzto.9 from scratch

timeout(9): remove unused interfaces: timeout_add_ts(9), timeout_add_bt(9)

These two interfaces have been entirely unused since introduction.
Remove them and thin the "timeout" namespace a bit.

Discussed with mpi@ and ratchov@ almost a year ago, though I blocked
the change at that time. Also discussed with visa@.

ok visa@, mpi@

timeout(9): Add timeout_set_flags(9) and TIMEOUT_INITIALIZER_FLAGS(9)

These allow the caller to initialize timeouts with arbitrary flags. We
only have one flag at the moment, TIMEOUT_PROC, but experimenting with
other flags is easier if these interfaces are available in-tree.

With input from bluhm@, guenther@, and visa@.

"makes sense to me" bluhm@, ok visa@

Revert "timeout(9): switch to tickless backend"

It appears to have caused major performance regressions all over the
network stack.

Reported by bluhm@

ok deraadt@

timeout(9): switch to tickless backend

Rebase the timeout wheel on the system uptime clock. Timeouts are now
set to run at or after an absolute time as returned by nanouptime(9).
Timeouts are thus "tickless": they expire at a real time on that clock
instead of at a particular value of the global "ticks" variable.

To facilitate this change the timeout struct's .to_time member becomes a
timespec. Hashing timeouts into a bucket on the wheel changes slightly:
we build a 32-bit hash with 25 bits of seconds (.tv_sec) and 7 bits of
subseconds (.tv_nsec). 7 bits of subseconds means the width of the
lowest wheel level is now 2 seconds on all platforms and each bucket in
that lowest level corresponds to 1/128 seconds on the uptime clock.
These values were chosen to closely align with the current 100hz
hardclock(9) typical on almost all of our platforms. At 100hz a bucket
is currently ~1/100 seconds wide on the lowest level and the lowest
level itself is ~2.56 seconds wide. Not a huge change, but a change
nonetheless.

Because a bucket no longer corresponds to a single tick more than one
bucket may be dumped during an average timeout_hardclock_update() call.
On 100hz platforms you now dump ~2 buckets. On 64hz machines (sh) you
dump ~4 buckets. On 1024hz machines (alpha) you dump only 1 bucket,
but you are doing extra work in softclock() to reschedule timeouts
that aren't due yet.

To avoid changing current behavior all timeout_add*(9) interfaces
convert their timeout interval into ticks, compute an equivalent
timespec interval, and then add that interval to the timestamp of
the most recent timeout_hardclock_update() call to determine an
absolute deadline. So all current timeouts still "use" ticks,
but the ticks are faked in the timeout layer.

A new interface, timeout_at_ts(9), is introduced here to bypass this
backwardly compatible behavior. It will be used in subsequent diffs
to add absolute timeout support for userland and to clean up some of
the messier parts of kernel timekeeping, especially at the syscall
layer.

Because timeouts are based against the uptime clock they are subject to
NTP adjustment via adjtime(2) and adjfreq(2). Unless you have a crazy
adjfreq(2) adjustment set this will not change the expiration behavior
of your timeouts.

Tons of design feedback from mpi@, visa@, guenther@, and kettenis@.
Additional amd64 testing from anton@ and visa@. Octeon testing from visa@.
macppc testing from me.

Positive feedback from deraadt@, ok visa@

timeout.9: cite 1997 Varghese/Lauck timeout wheel paper; ok jmc@ schwarze@

Add lock order checking for timeouts

The caller of timeout_barrier() must not hold locks that could prevent
timeout handlers from making progress. The system could deadlock
otherwise.

This patch makes witness(4) able to detect barrier locking errors.
This is done by introducing a pseudo-lock that couples the lock chains
of barrier callers to the lock chains of timeout handlers.

In order to find these errors faster, this diff adds a synchronous
version of cancelling timeouts, timeout_del_barrier(9). As the
synchronous intent is explicit, this interface can check lock order
immediately instead of waiting for the potentially rare occurrence of
timeout_barrier(9).

OK dlg@ mpi@

add timeout_barrier, which is like intr_barrier and taskq_barrier.

if you're trying to free something that a timeout is using, you
have to wait for that timeout to finish running before doing the
free. timeout_del can stop a timeout from running in the future,
but it doesn't know if a timeout has finished being scheduled and
is now running.

previously you could know that timeouts are not running by simply
masking softclock interrupts on the cpu running the kernel. however,
code is now running outside the kernel lock, and timeouts can run
in a thread instead of softclock.

timeout_barrier solves the first problem by taking the kernel lock
and then masking softclock interrupts. that is enough to ensure
that any further timeout processing is waiting for those resources
to run again.

the second problem is solved by having timeout_barrier insert work
into the thread. when that work runs, that means all previous work
running in that thread has completed.

fixes and ok visa@, who thinks this will be useful for his work
too.

Introduce a new 'softclock' thread that will be used to execute timeout
callbacks needing a process context.

The function timeout_set_proc(9) has to be used instead of timeout_set(9)
when a timeout callback needs a process context.

Note that if such a timeout is waiting, understand sleeping, for a non
negligible amount of time it might delay other timeouts needing a process
context.

dlg@ agrees with this as a temporary solution.

Manpage tweaks from jmc@

ok kettenis@, bluhm@, mikeb@

Prevent a round to zero in the timeout_add_...() functions. Getting
an immediate timeout if a positive value is specified is unexpected
behavior. Defer calling the handler for at least one tick. Do not
change that timeout_add(0) gives you an immediate timeout.
OK millert@ uebayasi@ tedu@

add missing NAME entries;
feedback/ok schwarze

Remove useless quoting from .Fo and .Fn function names, to prevent
development of a cargo cult in case people look at existing files
for examples. This achieves a consistent .Fo and .Fn quoting style
across the whole tree.

Remove hzto(9) manual pages and references; OK dlg

describe the context the callback runs at in the CONTEXT section.

add TIMEOUT_INITIALIZER for initting timeout declaractions.

similar to TASK_INITIALIZER and all the queue _INITIALIZER things.

ok deraadt@

revery -r1.34's addition of spl(9) to SEE ALSO: we already have splclock(9)
in there, and they're one and the same page;

wrap long lines

document the timeout_add and timeout_del return values in the RETURN VALUES
section.

im not sure what to do with the macros yet.

document the contexts you can call this api from out into its own section

make timeout_add and its wrappers return whether the timeout was scheduled
in this call by returning 1, or a previous call by returning 0. this makes
it easy to refcount the stuff we're scheduling a timeout for, and brings
the api in line with what task_add(9) provides.

ok mpi@ matthew@ mikeb@ guenther@

Replace old-fashioned .Fd by new-fangled .In for #include lines.
Diff from Jan Klemkow <j dot klemkow at wemelug dot de> on tech@.
No objection from jmc@ against this type of change.

timeout_del now returns an int.

this could probably be explained a bit better :/

the api that these timeouts replaced doesnt exist in our tree anymore, so
dont talk about it.

ok krw@, millert@, miod@

Document timeout_add_msec().

oga pointed out that it was undocumented, which caused me to find out
that I had this diff in my tree.

`fine' deraadt

In the .Fn entries for timeout_add_usec/nsec, don't call the parameter
``sec''. Instead, use usec/nsec.

Agreed with/no opposition from blambert.

Add timeout_add_sec() etc. to .Nm and, on jmc's request, tweak
some other stuff.

ok art jmc blambert

Document the new timeout_add_* functions.

sleep(9) was removed aeons ago according to miod, so remove references
to it. Because man pages are named after functions (at least they
should be) and sleep(9) doesn't exist anymore, sleep.9 is renamed to
tsleep.9.

Input and reminders from jmc and ratchov.

convert to new .Dd format;

add timeout_triggered to .Nm;

Note: i am not touching MLINK for untimeout(9), ugly though that word is,
since it seems to have a historical basis...

`Ns' implies `No', so `Ns No' -> `Ns'; (even simpler in adduser(8))
discussed with todd@

license cleaning.

typos;

ok tedu@

Reword to get rid of second person.

Xr tvtohz.

New scalable implementation with constant time add and delete. ok deraadt@

The old timeout API is gone.

Change references to hardclock to .Xr where it seem appropriate

Various man page fixes and improvements from gluk@

Document timeout_triggered

Add function types.

General man page cleanups, mostly to remove trailing whitespace, hard
sentence breaks, and other such things.

While I'm reading this, complete the NAME section and fix a typo.

Err, make it splclock(9), so it's more clear to the reader.

Xr spl(9)

Various fixes.
From millert@

fix typo preapared -> prepared

Better explaination, various fixes.

Document timeout_pending and timeout_initialized.

Document the new timeout API.

Minor fusses: OpenBSD tag, misused macros, codes references path.

Import some documentation from NetBSD, after checking that details match.

hz.9 and hzto.9 from scratch

timeout(9): Add timeout_set_flags(9) and TIMEOUT_INITIALIZER_FLAGS(9)

These allow the caller to initialize timeouts with arbitrary flags. We
only have one flag at the moment, TIMEOUT_PROC, but experimenting with
other flags is easier if these interfaces are available in-tree.

With input from bluhm@, guenther@, and visa@.

"makes sense to me" bluhm@, ok visa@

Revert "timeout(9): switch to tickless backend"

It appears to have caused major performance regressions all over the
network stack.

Reported by bluhm@

ok deraadt@

timeout(9): switch to tickless backend

Rebase the timeout wheel on the system uptime clock. Timeouts are now
set to run at or after an absolute time as returned by nanouptime(9).
Timeouts are thus "tickless": they expire at a real time on that clock
instead of at a particular value of the global "ticks" variable.

To facilitate this change the timeout struct's .to_time member becomes a
timespec. Hashing timeouts into a bucket on the wheel changes slightly:
we build a 32-bit hash with 25 bits of seconds (.tv_sec) and 7 bits of
subseconds (.tv_nsec). 7 bits of subseconds means the width of the
lowest wheel level is now 2 seconds on all platforms and each bucket in
that lowest level corresponds to 1/128 seconds on the uptime clock.
These values were chosen to closely align with the current 100hz
hardclock(9) typical on almost all of our platforms. At 100hz a bucket
is currently ~1/100 seconds wide on the lowest level and the lowest
level itself is ~2.56 seconds wide. Not a huge change, but a change
nonetheless.

Because a bucket no longer corresponds to a single tick more than one
bucket may be dumped during an average timeout_hardclock_update() call.
On 100hz platforms you now dump ~2 buckets. On 64hz machines (sh) you
dump ~4 buckets. On 1024hz machines (alpha) you dump only 1 bucket,
but you are doing extra work in softclock() to reschedule timeouts
that aren't due yet.

To avoid changing current behavior all timeout_add*(9) interfaces
convert their timeout interval into ticks, compute an equivalent
timespec interval, and then add that interval to the timestamp of
the most recent timeout_hardclock_update() call to determine an
absolute deadline. So all current timeouts still "use" ticks,
but the ticks are faked in the timeout layer.

A new interface, timeout_at_ts(9), is introduced here to bypass this
backwardly compatible behavior. It will be used in subsequent diffs
to add absolute timeout support for userland and to clean up some of
the messier parts of kernel timekeeping, especially at the syscall
layer.

Because timeouts are based against the uptime clock they are subject to
NTP adjustment via adjtime(2) and adjfreq(2). Unless you have a crazy
adjfreq(2) adjustment set this will not change the expiration behavior
of your timeouts.

Tons of design feedback from mpi@, visa@, guenther@, and kettenis@.
Additional amd64 testing from anton@ and visa@. Octeon testing from visa@.
macppc testing from me.

Positive feedback from deraadt@, ok visa@