Add kqueue1() system call

kqueue1() takes the flags argument. This lets the kqueue file descriptor
be opened with O_CLOEXEC. Adapted from NetBSD.

OK guenther@

kevent: Add precision and abstimer flags for EVFILT_TIMER

Add timer precision flags NOTE_SECONDS, NOTE_MSECONDS, NOTE_USECONDS
and NOTE_NSECONDS for EVFILT_TIMER. Also, add an initial implementation
of NOTE_ABSTIME timers.

Similar kevent(2) flags exist on FreeBSD, NetBSD and XNU.

Initial diff by and OK aisha@
OK mpi@

Adjust knote(9) API

Make knote(9) lock the knote list internally, and add knote_locked(9)
for the typical situation where the list is already locked.

Remove the KNOTE(9) macro to simplify the API.

Manual page OK jmc@
OK mpi@ mvs@

Move the rest of common socket initialization within soalloc().

ok visa@

Move knote_processexit() call from exit1() to the reaper().
This fixes a problem where NOTE_EXIT could be received before
the process was officially a zombie and thus not immediately
waitable. OK deraadt@ visa@

Add helper functions for f_modify and f_process to condense code

These new functions, knote_modify() and knote_process(), implement
the logic that is common to most f_modify and f_process instances.

The code is inlined so as to not add yet another call frame on the
already towering stack of kqueue functions. Also, the _fn versions
allow direct calling of an event function when there is only one
filter type to handle.

Rename knote_modify() to knote_assign()

This avoids verb overlap with f_modify.

Check klist emptiness instead of NULL pointer in KNOTE()

All callers of KNOTE() supply a non-NULL klist argument. Replace the
NULL pointer check with klist emptiness check as a small optimization.

OK mpi@

Inline klist_empty() for more economic machine code.

OK mpi@

poll(2): Switch to kqueue backend

Implement the poll(2) system call on top of the kqueue subsystem.
This obsoletes the old, non-MP-safe poll backend.

On entering poll(2), the new code translates each pollfd array entry
into a set of knotes. When these knotes receive events through kqueue,
the events are translated back to pollfd format.

Entries in the pollfd array can refer to the same file descriptor with
overlapping event masks. To allow such overlap with knotes, use an extra
kn_pollid key that separates knotes of different pollfd entries.

Adapted from DragonFly BSD, initial implementation by mpi@.

Tested in snaps for three weeks.

OK mpi@

Clarify usage of __EV_POLL and __EV_SELECT

Make __EV_POLL specific to kqueue-based poll(2), to remove overlap
with __EV_SELECT that only select(2) uses.

OK millert@ mpi@

Fix select(2) exceptfds handling of FIFOs and pipes

Prevent select(2) from indicating an exceptional condition when the
other end of a FIFO or pipe is closed.

Originally, select(2) returned an exceptfds event only with a pty or
socket that has out-of-band data pending. millert@ says that OpenBSD
diverged from this by accident when poll(2) and select(2) were changed
to use the same backend code in year 2003.

OK millert@

kqueue: Revise badfd knote handling

When closing a file descriptor and converting the poll/select knotes
into badfd knotes, keep the knotes attached to the by-fd table. This
should prevent kqueue_purge() from returning before the kqueue has
become quiescent. This in turn should fix a
KASSERT(TAILQ_EMPTY(&kq->kq_head)) panic in KQRELE() that bluhm@ has
reported.

The badfd conversion is only needed when a poll/select scan is ongoing.
The system can skip the conversion if the knote is not part of the
active event set.

The code of this commit skips the conversion when the fd is closed by
the same thread that has done the fd polling. This can be improved but
should already cover typical fd usage patterns.

As badfd knotes now hold slots in the by-fd table, kqueue_register()
clears them. poll/select use kqueue_register() to set up a new scan;
any found fd close notification is a leftover from the previous scan.

The new badfd handling should be free of accidental knote accumulation.
This obsoletes kqpoll_dequeue() and lowers kqpoll_init() overhead.

Re-enable lazy removal of poll/select knotes because the panic should
no longer happen.

OK mpi@

Keep knotes between poll/select systems calls

Reduce the time overhead of kqueue-based poll(2) and select(2) by
keeping knotes registered between the system calls. It is expected that
the set of monitored file descriptors is relatively unchanged between
consecutive iterations of these system calls. By keeping the knotes,
the system saves the effort of repeated knote unregistering and
re-registering.

To avoid receiving events from file descriptors that are no longer in
the monitored set, each poll/select knote is assigned an increasing
serial number. Every iteration of poll/select uses a previously unused
range of serials for its knotes. In the setup stage, kqueue_register()
updates the serials of any existing knotes in the currently monitored
set. Function kqueue_scan() delivers only the events whose serials are
recent enough; expired knotes are dropped. When the serial range is
about to wrap around, all the knotes in the kqueue backend are dropped.

This change is a space-time tradeoff. Memory usage is increased somewhat
because of the retained knotes. The increase is limited by the number
of open file descriptors and active threads.

Idea from DragonFly BSD, initial patch by mpi@, kqueue_scan()-based
approach by me.

Tested by anton@ and mpi@
OK mpi@

Set klist lock for sockets to make socket event filters MP-safe

The filterops instances already provide f_modify and f_process
callbacks with proper internal locking. Locking of socket klists
has been the missing detail for MP-safety.

OK mpi@

kqueue: kq_lock is needed when updating kn_status

The kn_status field of struct knote is part of kqueue's internal state.
When kn_status is being updated, kq_lock has to be locked. This is true
even with MP-unsafe event filters.

OK mpi@

Enable pool cache on knote pool

Use the pool cache to reduce the overhead of memory management in
function kqueue_register().

When EV_ADD is given, kqueue_register() pre-allocates a knote to avoid
potential sleeping in the middle of the critical section that spans
from knote lookup to insertion. However, the pre-allocation is useless
if the lookup finds a matching knote.

The cost of knote allocation will become significant with kqueue-based
poll(2) and select(2) because the frequency of allocation will increase.
Most of the cost appears to come from the locking inside the pool.
The pool cache amortizes it by using CPU-local caches of free knotes
as buffers.

OK dlg@ mpi@

kqueue: Revise filterops interface

Extend kqueue's filterops interface with new callbacks so that it
becomes easier to use with fine-grained locking. The new interface
delegates the serialization of kn_event access to event sources. Now
kqueue uses filterops callbacks to read or write kn_event. This hides
event sources' locking patterns from kqueue, and allows clean
implementation of atomic read-and-clear for EV_CLEAR, for instance.

There are so many existing filterops instances that converting all of
them in one go is tricky. This patch adds a wrapper mechanism that
kqueue uses when the new callbacks are missing.

The new filterops interface has been influenced by XNU's kqueue.

OK mpi@ semarie@

kqueue: Revise fd close notification

Deliver file descriptor close notification for __EV_POLL knotes through
struct kevent that kqueue_scan() returns. This replaces the previous way
of returning EBADF from kqueue_scan(), making it easier to determine
what exactly has changed.

When a file descriptor is closed, its __EV_POLL knotes are turned into
one-shot events and queued for delivery. These knotes are "unregistered"
as they are reachable only through the queue of active events. This
reduces interference with the normal workings of kqueue. However, more
care is needed to avoid leaking knotes. In addition, the unregistering
removes a limit on the number of issued knotes. To prevent accumulation
of pending fd close notifications, kqpoll_init() flushes the active
queue at the start of a kqpoll scan.

OK mpi@

Refactor klist insertion and removal

Rename klist_{insert,remove}() to klist_{insert,remove}_locked().
These functions assume that the caller has locked the klist. The current
state of locking remains intact because the kernel lock is still used
with all klists.

Add new functions klist_insert() and klist_remove() that lock the klist
internally. This allows some code simplification.

OK mpi@

Introduce klistops

This patch extends struct klist with a callback descriptor and
an argument. The main purpose of this is to let the kqueue subsystem
assert when a klist should be locked, and operate the klist lock
in klist_invalidate().

Access to a knote list of a kqueue-monitored object has to be
serialized somehow. Because the object often has a lock for protecting
its state, and because the object often acquires this lock at the latest
in its f_event callback function, it makes sense to use this lock also
for the knote lists. The existing uses of NOTE_SUBMIT already show
a pattern that is likely to become more prevalent.

There could be an embedded lock in klist. However, such a lock would be
redundant in many cases. The code cannot rely on a single lock type
(mutex, rwlock, something else) because the needs of monitored objects
vary. In addition, an embedded lock would introduce new lock order
constraints. Note that the patch does not rule out use of dedicated
klist locks.

The patch introduces a way to associate lock operations with a klist.
The caller can provide a custom implementation, or use a ready-made
interface with a mutex or rwlock.

For compatibility with old code, the new code falls back to using the
kernel lock if no specific klist initialization has been done. The
existing code already relies on implicit initialization of klist.

Sadly, this change increases the size of struct klist. dlg@ thinks this
is not fatal, though.

OK mpi@

Make knote_{activate,remove}() internal to kern_event.c.

OK mpi@

Add kernel-only per-thread kqueue & helpers to initialize and free it.

This will soon be used by select(2) and poll(2).

ok anton@, visa@

Refactor kqueue_scan() so it can be used by other syscalls.

Stop iterating in the function and instead copy the returned events to
userland after every call.

ok visa@

Change kqueue_scan() to keep track of collected events in the given context.

It is now possible to call the function multiple times to collect events.
For that, the end marker has to be preserved between calls because otherwise
the scan might collect an event more than once. If a collected event gets
reactivated during scanning, it will be added at the tail of the queue,
out of reach because of the end marker.

This is required to implement select(2) and poll(2) on top of kqueue_scan().

Done & originally committed by visa@ in r1.143, in snap for more than 2 weeks.

ok visa@, anton@

Refactor kqueue_scan() to use a context: a "kqueue_scan_state struct".

The struct keeps track of the end point of an event queue scan by
persisting the end marker. This will be needed when kqueue_scan() is
called repeatedly to complete a scan in a piecewise fashion.

Extracted from a previous diff from visa@.

ok visa@, anton@

Allow userland to use EVFILT_EXCEPT.

ok mvs@, visa@

Extend kqueue interface with EVFILT_EXCEPT filter.

This filter, already implemented in macOS and Dragonfly BSD, returns
exceptional conditions like the reception of out-of-band data.

The functionnality is similar to poll(2)'s POLLPRI & POLLRDBAND and
it can be used by the kqfilter-based poll & select implementation.

ok millert@ on a previous version, ok visa@

Implement a simple kqfilter for deadfs matching its poll handler.

ok visa@, millert@

Set __EV_HUP when the conditions matching poll(2)'s POLLUP are found.

This is only done in poll-compatibility mode, when __EV_POLL is set.

ok visa@, millert@

Revert addition of double underbars for filter-specific flag.

Port breakages reported by naddy@

Rename poll-compatibility flag to better reflect what it is.

While here prefix kernel-only EV flags with two underbars.

Suggested by kettenis@, ok visa@

Use a new EV_OLDAPI flag to match the behavior of poll(2) and select(2).

Adapt FS kqfilters to always return true when the flag is set and bypass
the polling mechanism of the NFS thread.

While here implement a write filter for NFS.

ok visa@

Revert "Add kqueue_scan_state struct"

sthen@ has reported that the patch might be causing hangs with X.

Add kqueue_scan_state struct

The struct keeps track of the end point of an event queue scan by
persisting the end marker. This will be needed when kqueue_scan() is
called repeatedly to complete a scan in a piecewise fashion. The end
marker has to be preserved between calls because otherwise the scan
might collect an event more than once. If a collected event gets
reactivated during scanning, it will be added at the tail of the queue,
out of reach because of the end marker.

OK mpi@

Use a double-underscore prefix for local variables declared in macros
that have arguments. Document this requirement/recommendation in style(9)

prompted by mpi@
ok deraadt@

Abstract the head of knote lists. This allows extending the lists,
for example, with locking assertions.

OK mpi@, anton@

Prevent shadowing of local variable by the EV_SET() macro.

Use two underbars to start the locally defined variable, as suggested by
guenther@. The other option to avoid namespace conflict would be to start
the identifier with an underbar and a capital.

ok beck@, guenther@

Replace field f_isfd with field f_flags in struct filterops to allow
adding more filter properties without cluttering the struct.

OK mpi@, anton@

Use C99 designated initializers with struct filterops. In addition,
make the structs const so that the data are put in .rodata.

OK mpi@, deraadt@, anton@, bluhm@

Allow sleeping inside kqueue event filters.

In kqueue_scan(), threads have to get an exclusive access to a knote
before processing by calling knote_acquire(). This prevents the knote
from being destroyed while it is still in use. knote_acquire() also
blocks other threads from processing the knote. Once knote processing
has finished, the thread has to call knote_release().

The kqueue subsystem is still serialized by the kernel lock. If an event
filter sleeps, the kernel lock is released and another thread might
enter kqueue_scan(). kqueue_scan() uses start and end markers to keep
track of the scan's progress and it has to be aware of other threads'
markers.

This patch is a revised version of mpi@'s work derived
from DragonFly BSD. kqueue_check() has been adapted from NetBSD.

Tested by anton@, sashan@
OK mpi@, anton@, sashan@

introduce a filter called EVFILT_DEVICE that can be used to notify
listeners of device state changes.
currently only supports NOTE_CHANGE that will be used by drm(4)

ok kettenis@

Expand u_short and u_int to unsigned short and unsigned int
respectively to avoid compilation errors when one of the POSIX or
X/OPEN version macros is defined. Also sync the field descriptions
with kqueue.2. OK deraadt@

Revert support for multiple threads to enter kqueue_scan() in parallel.

It is not clear if this change is responsible for the lockups experienced
by dhill@ and jcs@ but since we're no longer grabbing the socket lock in
kqueue(2) filters there's no need for this change.

Make it possible for multiple threads to enter kqueue_scan() in parallel.

This is a requirement to use a sleeping lock inside kqueue filters.
It is now possible, but not recommended, to sleep inside ``f_event''.

Threads iterating over the list of pending events are now recognizing
and skipping other threads' markers. knote_acquire() and knote_release()
must be used to "own" a knote to make sure no other thread is sleeping
with a reference on it.

Acquire and marker logic taken from DragonFly but the KERNEL_LOCK()
is still serializing the execution of the kqueue code.

This also enable the NET_LOCK() in socket filters.

Tested by abieber@ & juanfra@, run by naddy@ in a bulk, ok visa@, bluhm@

Assert that the corresponding socket is locked when manipulating socket
buffers.

This is one step towards unlocking TCP input path. Note that all the
functions asserting for the socket lock are not necessarilly MP-safe.
All the fields of 'struct socket' aren't protected.

Introduce a new kernel-only kqueue hint, NOTE_SUBMIT, to be able to
tell when a filter needs to lock the underlying data structures. Logic
and name taken from NetBSD.

Tested by Hrvoje Popovski.

ok claudio@, bluhm@, mikeb@

Add support for EV_RECEIPT and EV_DISPATCH flags

From FreeBSD via Jan Schreiber <jes at posteo ! de>, thanks!
OK tedu, bluhm

make a copy of the first EV_SET argument to prevent multiple evaluation.
matches freebsd, fixes lldb. from Kamil Rytarowski at NetBSD.
while here, make the same change to KNOTE. ok deraadt

move knhash size to event.h, use it for hashfree. from Mathieu -
ok guenther

modern interfaces should use modern speelings, so spell quad_t as int64_t.

struct knote's kn_sdata needs to be the same type as struct kevent's data

ok deraadt@

knote_processexit() needs the thread to pass down to FRELE(), so pass it
the exiting thread instead of assuming that that's ps_mainproc.
Also, panic no matter which thread of init takes it down.

ok tedu@

Switch time_t, ino_t, clock_t, and struct kevent's ident and data
members to 64bit types. Assign new syscall numbers for (almost
all) the syscalls that involve the affected types, including anything
with time_t, timeval, itimerval, timespec, rusage, dirent, stat,
or kevent arguments. Add a d_off member to struct dirent and replace
getdirentries() with getdents(), thus immensely simplifying and
accelerating telldir/seekdir. Build perl with -DBIG_TIME.

Bump the major on every single base library: the compat bits included
here are only good enough to make the transition; the T32 compat
option will be burned as soon as we've reached the new world are
are happy with the snapshots for all architectures.

DANGER: ABI incompatibility. Updating to this kernel requires extra
work or you won't be able to login: install a snapshot instead.

Much assistance in fixing userland issues from deraadt@ and tedu@
and build assistance from todd@ and otto@

When a ucom(4) is removed, it frees the tty with ttyfree(). However if
anyone is waiting with kqueue their knotes may still have a reference to
the tty and later try to use it in the filt_tty* functions.

To avoid this, walk the knotes in ttyfree(), remove them from the tty's
list and invalidate them by setting kn_hook to NODEV. The filter
functions can then check for this and safely ignore the knotes.

ok tedu matthieu

Missed a comment in the proc->process change

EVFILT_SIGNAL and EVFILT_PROC events need to track the process they're
attached to and not just the thread, which can go away.

Problem observed by jsg@; ok jsg@ matthew@

Fix knote handling for exiting processes: when triggering a NOTE_EXIT
knote, remove it from the process's klist; after handling those,
remove and drop any remaining knotes from the process's klist. Ban
attaching knotes to processes that have started exiting or attaching
them via the pid of a thread other than the main thread.

ok tedu@, deraadt@

Add a dummy kqueue filter similar to seltrue and use it for anything
using seltrue for poll. Based on code from NetBSD.

Also remove a stray duplicate lpt entry from loongson, from deraadt.

ok tedu deraadt

wrap use of KNOTE macro arguments in () to prevent potential strange
expansion.

requested by otto@

wrap an if statement in a macro up with do { } while (0) so it is safe to
use in other if/else blocks.

"yeah" deraadt@

add a new kevent filter type for timers. this allows processes to create
a series of oneshot or periodic timers. capped to a global limit.
from freebsd via brad.
ok art pedro

Change sys/select.h -> sys/selinfo.h in comment.

klist_invalidate to help clean up when the backend disappears, tested by mpf@

add NOTE_EOF (return on EOF) and NOTE_TRUNCATE (vnode was truncated)
to kqueue
from marius@monkey tested by brad@

void *, not caddr_t. missed in last commit. thanks Marco Peereboom

filter event that simulates seltrue(). From NetBSD

filterops doesn't need to change, so we can make it const
ok deraadt@

First round of __P removal in sys

branches: 1.3.4; 1.3.8;
port kqueue changes from freebsd, plus all required openbsd glue.
okay deraadt@, millert@
from jlemon@freebsd.org:
extend kqueue down to the device layer, backwards compatible approach
suggested by peter@freebsd.org

rcsid; lots of bad tabs and spaces

support kernel event queues, from FreeBSD by Jonathan Lemon,
okay art@, millert@

kevent: Add precision and abstimer flags for EVFILT_TIMER

Add timer precision flags NOTE_SECONDS, NOTE_MSECONDS, NOTE_USECONDS
and NOTE_NSECONDS for EVFILT_TIMER. Also, add an initial implementation
of NOTE_ABSTIME timers.

Similar kevent(2) flags exist on FreeBSD, NetBSD and XNU.

Initial diff by and OK aisha@
OK mpi@

Adjust knote(9) API

Make knote(9) lock the knote list internally, and add knote_locked(9)
for the typical situation where the list is already locked.

Remove the KNOTE(9) macro to simplify the API.

Manual page OK jmc@
OK mpi@ mvs@

Move the rest of common socket initialization within soalloc().

ok visa@

Move knote_processexit() call from exit1() to the reaper().
This fixes a problem where NOTE_EXIT could be received before
the process was officially a zombie and thus not immediately
waitable. OK deraadt@ visa@

Add helper functions for f_modify and f_process to condense code

These new functions, knote_modify() and knote_process(), implement
the logic that is common to most f_modify and f_process instances.

The code is inlined so as to not add yet another call frame on the
already towering stack of kqueue functions. Also, the _fn versions
allow direct calling of an event function when there is only one
filter type to handle.

Rename knote_modify() to knote_assign()

This avoids verb overlap with f_modify.

Check klist emptiness instead of NULL pointer in KNOTE()

All callers of KNOTE() supply a non-NULL klist argument. Replace the
NULL pointer check with klist emptiness check as a small optimization.

OK mpi@

Inline klist_empty() for more economic machine code.

OK mpi@

poll(2): Switch to kqueue backend

Implement the poll(2) system call on top of the kqueue subsystem.
This obsoletes the old, non-MP-safe poll backend.

On entering poll(2), the new code translates each pollfd array entry
into a set of knotes. When these knotes receive events through kqueue,
the events are translated back to pollfd format.

Entries in the pollfd array can refer to the same file descriptor with
overlapping event masks. To allow such overlap with knotes, use an extra
kn_pollid key that separates knotes of different pollfd entries.

Adapted from DragonFly BSD, initial implementation by mpi@.

Tested in snaps for three weeks.

OK mpi@

Clarify usage of __EV_POLL and __EV_SELECT

Make __EV_POLL specific to kqueue-based poll(2), to remove overlap
with __EV_SELECT that only select(2) uses.

OK millert@ mpi@

Fix select(2) exceptfds handling of FIFOs and pipes

Prevent select(2) from indicating an exceptional condition when the
other end of a FIFO or pipe is closed.

Originally, select(2) returned an exceptfds event only with a pty or
socket that has out-of-band data pending. millert@ says that OpenBSD
diverged from this by accident when poll(2) and select(2) were changed
to use the same backend code in year 2003.

OK millert@

kqueue: Revise badfd knote handling

When closing a file descriptor and converting the poll/select knotes
into badfd knotes, keep the knotes attached to the by-fd table. This
should prevent kqueue_purge() from returning before the kqueue has
become quiescent. This in turn should fix a
KASSERT(TAILQ_EMPTY(&kq->kq_head)) panic in KQRELE() that bluhm@ has
reported.

The badfd conversion is only needed when a poll/select scan is ongoing.
The system can skip the conversion if the knote is not part of the
active event set.

The code of this commit skips the conversion when the fd is closed by
the same thread that has done the fd polling. This can be improved but
should already cover typical fd usage patterns.

As badfd knotes now hold slots in the by-fd table, kqueue_register()
clears them. poll/select use kqueue_register() to set up a new scan;
any found fd close notification is a leftover from the previous scan.

The new badfd handling should be free of accidental knote accumulation.
This obsoletes kqpoll_dequeue() and lowers kqpoll_init() overhead.

Re-enable lazy removal of poll/select knotes because the panic should
no longer happen.

OK mpi@

Keep knotes between poll/select systems calls

Reduce the time overhead of kqueue-based poll(2) and select(2) by
keeping knotes registered between the system calls. It is expected that
the set of monitored file descriptors is relatively unchanged between
consecutive iterations of these system calls. By keeping the knotes,
the system saves the effort of repeated knote unregistering and
re-registering.

To avoid receiving events from file descriptors that are no longer in
the monitored set, each poll/select knote is assigned an increasing
serial number. Every iteration of poll/select uses a previously unused
range of serials for its knotes. In the setup stage, kqueue_register()
updates the serials of any existing knotes in the currently monitored
set. Function kqueue_scan() delivers only the events whose serials are
recent enough; expired knotes are dropped. When the serial range is
about to wrap around, all the knotes in the kqueue backend are dropped.

This change is a space-time tradeoff. Memory usage is increased somewhat
because of the retained knotes. The increase is limited by the number
of open file descriptors and active threads.

Idea from DragonFly BSD, initial patch by mpi@, kqueue_scan()-based
approach by me.

Tested by anton@ and mpi@
OK mpi@

Set klist lock for sockets to make socket event filters MP-safe

The filterops instances already provide f_modify and f_process
callbacks with proper internal locking. Locking of socket klists
has been the missing detail for MP-safety.

OK mpi@

kqueue: kq_lock is needed when updating kn_status

The kn_status field of struct knote is part of kqueue's internal state.
When kn_status is being updated, kq_lock has to be locked. This is true
even with MP-unsafe event filters.

OK mpi@

Enable pool cache on knote pool

Use the pool cache to reduce the overhead of memory management in
function kqueue_register().

When EV_ADD is given, kqueue_register() pre-allocates a knote to avoid
potential sleeping in the middle of the critical section that spans
from knote lookup to insertion. However, the pre-allocation is useless
if the lookup finds a matching knote.

The cost of knote allocation will become significant with kqueue-based
poll(2) and select(2) because the frequency of allocation will increase.
Most of the cost appears to come from the locking inside the pool.
The pool cache amortizes it by using CPU-local caches of free knotes
as buffers.

OK dlg@ mpi@

kqueue: Revise filterops interface

Extend kqueue's filterops interface with new callbacks so that it
becomes easier to use with fine-grained locking. The new interface
delegates the serialization of kn_event access to event sources. Now
kqueue uses filterops callbacks to read or write kn_event. This hides
event sources' locking patterns from kqueue, and allows clean
implementation of atomic read-and-clear for EV_CLEAR, for instance.

There are so many existing filterops instances that converting all of
them in one go is tricky. This patch adds a wrapper mechanism that
kqueue uses when the new callbacks are missing.

The new filterops interface has been influenced by XNU's kqueue.

OK mpi@ semarie@

kqueue: Revise fd close notification

Deliver file descriptor close notification for __EV_POLL knotes through
struct kevent that kqueue_scan() returns. This replaces the previous way
of returning EBADF from kqueue_scan(), making it easier to determine
what exactly has changed.

When a file descriptor is closed, its __EV_POLL knotes are turned into
one-shot events and queued for delivery. These knotes are "unregistered"
as they are reachable only through the queue of active events. This
reduces interference with the normal workings of kqueue. However, more
care is needed to avoid leaking knotes. In addition, the unregistering
removes a limit on the number of issued knotes. To prevent accumulation
of pending fd close notifications, kqpoll_init() flushes the active
queue at the start of a kqpoll scan.

OK mpi@

Refactor klist insertion and removal

Rename klist_{insert,remove}() to klist_{insert,remove}_locked().
These functions assume that the caller has locked the klist. The current
state of locking remains intact because the kernel lock is still used
with all klists.

Add new functions klist_insert() and klist_remove() that lock the klist
internally. This allows some code simplification.

OK mpi@

Introduce klistops

This patch extends struct klist with a callback descriptor and
an argument. The main purpose of this is to let the kqueue subsystem
assert when a klist should be locked, and operate the klist lock
in klist_invalidate().

Access to a knote list of a kqueue-monitored object has to be
serialized somehow. Because the object often has a lock for protecting
its state, and because the object often acquires this lock at the latest
in its f_event callback function, it makes sense to use this lock also
for the knote lists. The existing uses of NOTE_SUBMIT already show
a pattern that is likely to become more prevalent.

There could be an embedded lock in klist. However, such a lock would be
redundant in many cases. The code cannot rely on a single lock type
(mutex, rwlock, something else) because the needs of monitored objects
vary. In addition, an embedded lock would introduce new lock order
constraints. Note that the patch does not rule out use of dedicated
klist locks.

The patch introduces a way to associate lock operations with a klist.
The caller can provide a custom implementation, or use a ready-made
interface with a mutex or rwlock.

For compatibility with old code, the new code falls back to using the
kernel lock if no specific klist initialization has been done. The
existing code already relies on implicit initialization of klist.

Sadly, this change increases the size of struct klist. dlg@ thinks this
is not fatal, though.

OK mpi@

Make knote_{activate,remove}() internal to kern_event.c.

OK mpi@

Add kernel-only per-thread kqueue & helpers to initialize and free it.

This will soon be used by select(2) and poll(2).

ok anton@, visa@

Refactor kqueue_scan() so it can be used by other syscalls.

Stop iterating in the function and instead copy the returned events to
userland after every call.

ok visa@

Change kqueue_scan() to keep track of collected events in the given context.

It is now possible to call the function multiple times to collect events.
For that, the end marker has to be preserved between calls because otherwise
the scan might collect an event more than once. If a collected event gets
reactivated during scanning, it will be added at the tail of the queue,
out of reach because of the end marker.

This is required to implement select(2) and poll(2) on top of kqueue_scan().

Done & originally committed by visa@ in r1.143, in snap for more than 2 weeks.

ok visa@, anton@

Refactor kqueue_scan() to use a context: a "kqueue_scan_state struct".

The struct keeps track of the end point of an event queue scan by
persisting the end marker. This will be needed when kqueue_scan() is
called repeatedly to complete a scan in a piecewise fashion.

Extracted from a previous diff from visa@.

ok visa@, anton@

Allow userland to use EVFILT_EXCEPT.

ok mvs@, visa@

Extend kqueue interface with EVFILT_EXCEPT filter.

This filter, already implemented in macOS and Dragonfly BSD, returns
exceptional conditions like the reception of out-of-band data.

The functionnality is similar to poll(2)'s POLLPRI & POLLRDBAND and
it can be used by the kqfilter-based poll & select implementation.

ok millert@ on a previous version, ok visa@

Implement a simple kqfilter for deadfs matching its poll handler.

ok visa@, millert@

Set __EV_HUP when the conditions matching poll(2)'s POLLUP are found.

This is only done in poll-compatibility mode, when __EV_POLL is set.

ok visa@, millert@

Revert addition of double underbars for filter-specific flag.

Port breakages reported by naddy@

Rename poll-compatibility flag to better reflect what it is.

While here prefix kernel-only EV flags with two underbars.

Suggested by kettenis@, ok visa@

Use a new EV_OLDAPI flag to match the behavior of poll(2) and select(2).

Adapt FS kqfilters to always return true when the flag is set and bypass
the polling mechanism of the NFS thread.

While here implement a write filter for NFS.

ok visa@

Revert "Add kqueue_scan_state struct"

sthen@ has reported that the patch might be causing hangs with X.

Add kqueue_scan_state struct

The struct keeps track of the end point of an event queue scan by
persisting the end marker. This will be needed when kqueue_scan() is
called repeatedly to complete a scan in a piecewise fashion. The end
marker has to be preserved between calls because otherwise the scan
might collect an event more than once. If a collected event gets
reactivated during scanning, it will be added at the tail of the queue,
out of reach because of the end marker.

OK mpi@

Use a double-underscore prefix for local variables declared in macros
that have arguments. Document this requirement/recommendation in style(9)

prompted by mpi@
ok deraadt@

Abstract the head of knote lists. This allows extending the lists,
for example, with locking assertions.

OK mpi@, anton@

Prevent shadowing of local variable by the EV_SET() macro.

Use two underbars to start the locally defined variable, as suggested by
guenther@. The other option to avoid namespace conflict would be to start
the identifier with an underbar and a capital.

ok beck@, guenther@

Replace field f_isfd with field f_flags in struct filterops to allow
adding more filter properties without cluttering the struct.

OK mpi@, anton@

Use C99 designated initializers with struct filterops. In addition,
make the structs const so that the data are put in .rodata.

OK mpi@, deraadt@, anton@, bluhm@

Allow sleeping inside kqueue event filters.

In kqueue_scan(), threads have to get an exclusive access to a knote
before processing by calling knote_acquire(). This prevents the knote
from being destroyed while it is still in use. knote_acquire() also
blocks other threads from processing the knote. Once knote processing
has finished, the thread has to call knote_release().

The kqueue subsystem is still serialized by the kernel lock. If an event
filter sleeps, the kernel lock is released and another thread might
enter kqueue_scan(). kqueue_scan() uses start and end markers to keep
track of the scan's progress and it has to be aware of other threads'
markers.

This patch is a revised version of mpi@'s work derived
from DragonFly BSD. kqueue_check() has been adapted from NetBSD.

Tested by anton@, sashan@
OK mpi@, anton@, sashan@

introduce a filter called EVFILT_DEVICE that can be used to notify
listeners of device state changes.
currently only supports NOTE_CHANGE that will be used by drm(4)

ok kettenis@

Expand u_short and u_int to unsigned short and unsigned int
respectively to avoid compilation errors when one of the POSIX or
X/OPEN version macros is defined. Also sync the field descriptions
with kqueue.2. OK deraadt@

Revert support for multiple threads to enter kqueue_scan() in parallel.

It is not clear if this change is responsible for the lockups experienced
by dhill@ and jcs@ but since we're no longer grabbing the socket lock in
kqueue(2) filters there's no need for this change.

Make it possible for multiple threads to enter kqueue_scan() in parallel.

This is a requirement to use a sleeping lock inside kqueue filters.
It is now possible, but not recommended, to sleep inside ``f_event''.

Threads iterating over the list of pending events are now recognizing
and skipping other threads' markers. knote_acquire() and knote_release()
must be used to "own" a knote to make sure no other thread is sleeping
with a reference on it.

Acquire and marker logic taken from DragonFly but the KERNEL_LOCK()
is still serializing the execution of the kqueue code.

This also enable the NET_LOCK() in socket filters.

Tested by abieber@ & juanfra@, run by naddy@ in a bulk, ok visa@, bluhm@

Assert that the corresponding socket is locked when manipulating socket
buffers.

This is one step towards unlocking TCP input path. Note that all the
functions asserting for the socket lock are not necessarilly MP-safe.
All the fields of 'struct socket' aren't protected.

Introduce a new kernel-only kqueue hint, NOTE_SUBMIT, to be able to
tell when a filter needs to lock the underlying data structures. Logic
and name taken from NetBSD.

Tested by Hrvoje Popovski.

ok claudio@, bluhm@, mikeb@

Add support for EV_RECEIPT and EV_DISPATCH flags

From FreeBSD via Jan Schreiber <jes at posteo ! de>, thanks!
OK tedu, bluhm

make a copy of the first EV_SET argument to prevent multiple evaluation.
matches freebsd, fixes lldb. from Kamil Rytarowski at NetBSD.
while here, make the same change to KNOTE. ok deraadt

move knhash size to event.h, use it for hashfree. from Mathieu -
ok guenther

modern interfaces should use modern speelings, so spell quad_t as int64_t.

struct knote's kn_sdata needs to be the same type as struct kevent's data

ok deraadt@

knote_processexit() needs the thread to pass down to FRELE(), so pass it
the exiting thread instead of assuming that that's ps_mainproc.
Also, panic no matter which thread of init takes it down.

ok tedu@

Switch time_t, ino_t, clock_t, and struct kevent's ident and data
members to 64bit types. Assign new syscall numbers for (almost
all) the syscalls that involve the affected types, including anything
with time_t, timeval, itimerval, timespec, rusage, dirent, stat,
or kevent arguments. Add a d_off member to struct dirent and replace
getdirentries() with getdents(), thus immensely simplifying and
accelerating telldir/seekdir. Build perl with -DBIG_TIME.

Bump the major on every single base library: the compat bits included
here are only good enough to make the transition; the T32 compat
option will be burned as soon as we've reached the new world are
are happy with the snapshots for all architectures.

DANGER: ABI incompatibility. Updating to this kernel requires extra
work or you won't be able to login: install a snapshot instead.

Much assistance in fixing userland issues from deraadt@ and tedu@
and build assistance from todd@ and otto@

When a ucom(4) is removed, it frees the tty with ttyfree(). However if
anyone is waiting with kqueue their knotes may still have a reference to
the tty and later try to use it in the filt_tty* functions.

To avoid this, walk the knotes in ttyfree(), remove them from the tty's
list and invalidate them by setting kn_hook to NODEV. The filter
functions can then check for this and safely ignore the knotes.

ok tedu matthieu

Missed a comment in the proc->process change

EVFILT_SIGNAL and EVFILT_PROC events need to track the process they're
attached to and not just the thread, which can go away.

Problem observed by jsg@; ok jsg@ matthew@

Fix knote handling for exiting processes: when triggering a NOTE_EXIT
knote, remove it from the process's klist; after handling those,
remove and drop any remaining knotes from the process's klist. Ban
attaching knotes to processes that have started exiting or attaching
them via the pid of a thread other than the main thread.

ok tedu@, deraadt@

Add a dummy kqueue filter similar to seltrue and use it for anything
using seltrue for poll. Based on code from NetBSD.

Also remove a stray duplicate lpt entry from loongson, from deraadt.

ok tedu deraadt

wrap use of KNOTE macro arguments in () to prevent potential strange
expansion.

requested by otto@

wrap an if statement in a macro up with do { } while (0) so it is safe to
use in other if/else blocks.

"yeah" deraadt@

add a new kevent filter type for timers. this allows processes to create
a series of oneshot or periodic timers. capped to a global limit.
from freebsd via brad.
ok art pedro

Change sys/select.h -> sys/selinfo.h in comment.

klist_invalidate to help clean up when the backend disappears, tested by mpf@

add NOTE_EOF (return on EOF) and NOTE_TRUNCATE (vnode was truncated)
to kqueue
from marius@monkey tested by brad@

void *, not caddr_t. missed in last commit. thanks Marco Peereboom

filter event that simulates seltrue(). From NetBSD

filterops doesn't need to change, so we can make it const
ok deraadt@

First round of __P removal in sys

branches: 1.3.4; 1.3.8;
port kqueue changes from freebsd, plus all required openbsd glue.
okay deraadt@, millert@
from jlemon@freebsd.org:
extend kqueue down to the device layer, backwards compatible approach
suggested by peter@freebsd.org

rcsid; lots of bad tabs and spaces

support kernel event queues, from FreeBSD by Jonathan Lemon,
okay art@, millert@

Adjust knote(9) API

Make knote(9) lock the knote list internally, and add knote_locked(9)
for the typical situation where the list is already locked.

Remove the KNOTE(9) macro to simplify the API.

Manual page OK jmc@
OK mpi@ mvs@

Move the rest of common socket initialization within soalloc().

ok visa@

Move knote_processexit() call from exit1() to the reaper().
This fixes a problem where NOTE_EXIT could be received before
the process was officially a zombie and thus not immediately
waitable. OK deraadt@ visa@

Add helper functions for f_modify and f_process to condense code

These new functions, knote_modify() and knote_process(), implement
the logic that is common to most f_modify and f_process instances.

The code is inlined so as to not add yet another call frame on the
already towering stack of kqueue functions. Also, the _fn versions
allow direct calling of an event function when there is only one
filter type to handle.

Rename knote_modify() to knote_assign()

This avoids verb overlap with f_modify.

Check klist emptiness instead of NULL pointer in KNOTE()

All callers of KNOTE() supply a non-NULL klist argument. Replace the
NULL pointer check with klist emptiness check as a small optimization.

OK mpi@

Inline klist_empty() for more economic machine code.

OK mpi@

poll(2): Switch to kqueue backend

Implement the poll(2) system call on top of the kqueue subsystem.
This obsoletes the old, non-MP-safe poll backend.

On entering poll(2), the new code translates each pollfd array entry
into a set of knotes. When these knotes receive events through kqueue,
the events are translated back to pollfd format.

Entries in the pollfd array can refer to the same file descriptor with
overlapping event masks. To allow such overlap with knotes, use an extra
kn_pollid key that separates knotes of different pollfd entries.

Adapted from DragonFly BSD, initial implementation by mpi@.

Tested in snaps for three weeks.

OK mpi@

Clarify usage of __EV_POLL and __EV_SELECT

Make __EV_POLL specific to kqueue-based poll(2), to remove overlap
with __EV_SELECT that only select(2) uses.

OK millert@ mpi@

Fix select(2) exceptfds handling of FIFOs and pipes

Prevent select(2) from indicating an exceptional condition when the
other end of a FIFO or pipe is closed.

Originally, select(2) returned an exceptfds event only with a pty or
socket that has out-of-band data pending. millert@ says that OpenBSD
diverged from this by accident when poll(2) and select(2) were changed
to use the same backend code in year 2003.

OK millert@

kqueue: Revise badfd knote handling

When closing a file descriptor and converting the poll/select knotes
into badfd knotes, keep the knotes attached to the by-fd table. This
should prevent kqueue_purge() from returning before the kqueue has
become quiescent. This in turn should fix a
KASSERT(TAILQ_EMPTY(&kq->kq_head)) panic in KQRELE() that bluhm@ has
reported.

The badfd conversion is only needed when a poll/select scan is ongoing.
The system can skip the conversion if the knote is not part of the
active event set.

The code of this commit skips the conversion when the fd is closed by
the same thread that has done the fd polling. This can be improved but
should already cover typical fd usage patterns.

As badfd knotes now hold slots in the by-fd table, kqueue_register()
clears them. poll/select use kqueue_register() to set up a new scan;
any found fd close notification is a leftover from the previous scan.

The new badfd handling should be free of accidental knote accumulation.
This obsoletes kqpoll_dequeue() and lowers kqpoll_init() overhead.

Re-enable lazy removal of poll/select knotes because the panic should
no longer happen.

OK mpi@

Keep knotes between poll/select systems calls

Reduce the time overhead of kqueue-based poll(2) and select(2) by
keeping knotes registered between the system calls. It is expected that
the set of monitored file descriptors is relatively unchanged between
consecutive iterations of these system calls. By keeping the knotes,
the system saves the effort of repeated knote unregistering and
re-registering.

To avoid receiving events from file descriptors that are no longer in
the monitored set, each poll/select knote is assigned an increasing
serial number. Every iteration of poll/select uses a previously unused
range of serials for its knotes. In the setup stage, kqueue_register()
updates the serials of any existing knotes in the currently monitored
set. Function kqueue_scan() delivers only the events whose serials are
recent enough; expired knotes are dropped. When the serial range is
about to wrap around, all the knotes in the kqueue backend are dropped.

This change is a space-time tradeoff. Memory usage is increased somewhat
because of the retained knotes. The increase is limited by the number
of open file descriptors and active threads.

Idea from DragonFly BSD, initial patch by mpi@, kqueue_scan()-based
approach by me.

Tested by anton@ and mpi@
OK mpi@

Set klist lock for sockets to make socket event filters MP-safe

The filterops instances already provide f_modify and f_process
callbacks with proper internal locking. Locking of socket klists
has been the missing detail for MP-safety.

OK mpi@

kqueue: kq_lock is needed when updating kn_status

The kn_status field of struct knote is part of kqueue's internal state.
When kn_status is being updated, kq_lock has to be locked. This is true
even with MP-unsafe event filters.

OK mpi@

Enable pool cache on knote pool

Use the pool cache to reduce the overhead of memory management in
function kqueue_register().

When EV_ADD is given, kqueue_register() pre-allocates a knote to avoid
potential sleeping in the middle of the critical section that spans
from knote lookup to insertion. However, the pre-allocation is useless
if the lookup finds a matching knote.

The cost of knote allocation will become significant with kqueue-based
poll(2) and select(2) because the frequency of allocation will increase.
Most of the cost appears to come from the locking inside the pool.
The pool cache amortizes it by using CPU-local caches of free knotes
as buffers.

OK dlg@ mpi@

kqueue: Revise filterops interface

Extend kqueue's filterops interface with new callbacks so that it
becomes easier to use with fine-grained locking. The new interface
delegates the serialization of kn_event access to event sources. Now
kqueue uses filterops callbacks to read or write kn_event. This hides
event sources' locking patterns from kqueue, and allows clean
implementation of atomic read-and-clear for EV_CLEAR, for instance.

There are so many existing filterops instances that converting all of
them in one go is tricky. This patch adds a wrapper mechanism that
kqueue uses when the new callbacks are missing.

The new filterops interface has been influenced by XNU's kqueue.

OK mpi@ semarie@

kqueue: Revise fd close notification

Deliver file descriptor close notification for __EV_POLL knotes through
struct kevent that kqueue_scan() returns. This replaces the previous way
of returning EBADF from kqueue_scan(), making it easier to determine
what exactly has changed.

When a file descriptor is closed, its __EV_POLL knotes are turned into
one-shot events and queued for delivery. These knotes are "unregistered"
as they are reachable only through the queue of active events. This
reduces interference with the normal workings of kqueue. However, more
care is needed to avoid leaking knotes. In addition, the unregistering
removes a limit on the number of issued knotes. To prevent accumulation
of pending fd close notifications, kqpoll_init() flushes the active
queue at the start of a kqpoll scan.

OK mpi@

Refactor klist insertion and removal

Rename klist_{insert,remove}() to klist_{insert,remove}_locked().
These functions assume that the caller has locked the klist. The current
state of locking remains intact because the kernel lock is still used
with all klists.

Add new functions klist_insert() and klist_remove() that lock the klist
internally. This allows some code simplification.

OK mpi@

Introduce klistops

This patch extends struct klist with a callback descriptor and
an argument. The main purpose of this is to let the kqueue subsystem
assert when a klist should be locked, and operate the klist lock
in klist_invalidate().

Access to a knote list of a kqueue-monitored object has to be
serialized somehow. Because the object often has a lock for protecting
its state, and because the object often acquires this lock at the latest
in its f_event callback function, it makes sense to use this lock also
for the knote lists. The existing uses of NOTE_SUBMIT already show
a pattern that is likely to become more prevalent.

There could be an embedded lock in klist. However, such a lock would be
redundant in many cases. The code cannot rely on a single lock type
(mutex, rwlock, something else) because the needs of monitored objects
vary. In addition, an embedded lock would introduce new lock order
constraints. Note that the patch does not rule out use of dedicated
klist locks.

The patch introduces a way to associate lock operations with a klist.
The caller can provide a custom implementation, or use a ready-made
interface with a mutex or rwlock.

For compatibility with old code, the new code falls back to using the
kernel lock if no specific klist initialization has been done. The
existing code already relies on implicit initialization of klist.

Sadly, this change increases the size of struct klist. dlg@ thinks this
is not fatal, though.

OK mpi@

Make knote_{activate,remove}() internal to kern_event.c.

OK mpi@

Add kernel-only per-thread kqueue & helpers to initialize and free it.

This will soon be used by select(2) and poll(2).

ok anton@, visa@

Refactor kqueue_scan() so it can be used by other syscalls.

Stop iterating in the function and instead copy the returned events to
userland after every call.

ok visa@

Change kqueue_scan() to keep track of collected events in the given context.

It is now possible to call the function multiple times to collect events.
For that, the end marker has to be preserved between calls because otherwise
the scan might collect an event more than once. If a collected event gets
reactivated during scanning, it will be added at the tail of the queue,
out of reach because of the end marker.

This is required to implement select(2) and poll(2) on top of kqueue_scan().

Done & originally committed by visa@ in r1.143, in snap for more than 2 weeks.

ok visa@, anton@

Refactor kqueue_scan() to use a context: a "kqueue_scan_state struct".

The struct keeps track of the end point of an event queue scan by
persisting the end marker. This will be needed when kqueue_scan() is
called repeatedly to complete a scan in a piecewise fashion.

Extracted from a previous diff from visa@.

ok visa@, anton@

Allow userland to use EVFILT_EXCEPT.

ok mvs@, visa@

Extend kqueue interface with EVFILT_EXCEPT filter.

This filter, already implemented in macOS and Dragonfly BSD, returns
exceptional conditions like the reception of out-of-band data.

The functionnality is similar to poll(2)'s POLLPRI & POLLRDBAND and
it can be used by the kqfilter-based poll & select implementation.

ok millert@ on a previous version, ok visa@

Implement a simple kqfilter for deadfs matching its poll handler.

ok visa@, millert@

Set __EV_HUP when the conditions matching poll(2)'s POLLUP are found.

This is only done in poll-compatibility mode, when __EV_POLL is set.

ok visa@, millert@

Revert addition of double underbars for filter-specific flag.

Port breakages reported by naddy@

Rename poll-compatibility flag to better reflect what it is.

While here prefix kernel-only EV flags with two underbars.

Suggested by kettenis@, ok visa@

Use a new EV_OLDAPI flag to match the behavior of poll(2) and select(2).

Adapt FS kqfilters to always return true when the flag is set and bypass
the polling mechanism of the NFS thread.

While here implement a write filter for NFS.

ok visa@

Revert "Add kqueue_scan_state struct"

sthen@ has reported that the patch might be causing hangs with X.

Add kqueue_scan_state struct

The struct keeps track of the end point of an event queue scan by
persisting the end marker. This will be needed when kqueue_scan() is
called repeatedly to complete a scan in a piecewise fashion. The end
marker has to be preserved between calls because otherwise the scan
might collect an event more than once. If a collected event gets
reactivated during scanning, it will be added at the tail of the queue,
out of reach because of the end marker.

OK mpi@

Use a double-underscore prefix for local variables declared in macros
that have arguments. Document this requirement/recommendation in style(9)

prompted by mpi@
ok deraadt@

Abstract the head of knote lists. This allows extending the lists,
for example, with locking assertions.

OK mpi@, anton@

Prevent shadowing of local variable by the EV_SET() macro.

Use two underbars to start the locally defined variable, as suggested by
guenther@. The other option to avoid namespace conflict would be to start
the identifier with an underbar and a capital.

ok beck@, guenther@

Replace field f_isfd with field f_flags in struct filterops to allow
adding more filter properties without cluttering the struct.

OK mpi@, anton@

Use C99 designated initializers with struct filterops. In addition,
make the structs const so that the data are put in .rodata.

OK mpi@, deraadt@, anton@, bluhm@

Allow sleeping inside kqueue event filters.

In kqueue_scan(), threads have to get an exclusive access to a knote
before processing by calling knote_acquire(). This prevents the knote
from being destroyed while it is still in use. knote_acquire() also
blocks other threads from processing the knote. Once knote processing
has finished, the thread has to call knote_release().

The kqueue subsystem is still serialized by the kernel lock. If an event
filter sleeps, the kernel lock is released and another thread might
enter kqueue_scan(). kqueue_scan() uses start and end markers to keep
track of the scan's progress and it has to be aware of other threads'
markers.

This patch is a revised version of mpi@'s work derived
from DragonFly BSD. kqueue_check() has been adapted from NetBSD.

Tested by anton@, sashan@
OK mpi@, anton@, sashan@

introduce a filter called EVFILT_DEVICE that can be used to notify
listeners of device state changes.
currently only supports NOTE_CHANGE that will be used by drm(4)

ok kettenis@

Expand u_short and u_int to unsigned short and unsigned int
respectively to avoid compilation errors when one of the POSIX or
X/OPEN version macros is defined. Also sync the field descriptions
with kqueue.2. OK deraadt@

Revert support for multiple threads to enter kqueue_scan() in parallel.

It is not clear if this change is responsible for the lockups experienced
by dhill@ and jcs@ but since we're no longer grabbing the socket lock in
kqueue(2) filters there's no need for this change.

Make it possible for multiple threads to enter kqueue_scan() in parallel.

This is a requirement to use a sleeping lock inside kqueue filters.
It is now possible, but not recommended, to sleep inside ``f_event''.

Threads iterating over the list of pending events are now recognizing
and skipping other threads' markers. knote_acquire() and knote_release()
must be used to "own" a knote to make sure no other thread is sleeping
with a reference on it.

Acquire and marker logic taken from DragonFly but the KERNEL_LOCK()
is still serializing the execution of the kqueue code.

This also enable the NET_LOCK() in socket filters.

Tested by abieber@ & juanfra@, run by naddy@ in a bulk, ok visa@, bluhm@

Assert that the corresponding socket is locked when manipulating socket
buffers.

This is one step towards unlocking TCP input path. Note that all the
functions asserting for the socket lock are not necessarilly MP-safe.
All the fields of 'struct socket' aren't protected.

Introduce a new kernel-only kqueue hint, NOTE_SUBMIT, to be able to
tell when a filter needs to lock the underlying data structures. Logic
and name taken from NetBSD.

Tested by Hrvoje Popovski.

ok claudio@, bluhm@, mikeb@

Add support for EV_RECEIPT and EV_DISPATCH flags

From FreeBSD via Jan Schreiber <jes at posteo ! de>, thanks!
OK tedu, bluhm

make a copy of the first EV_SET argument to prevent multiple evaluation.
matches freebsd, fixes lldb. from Kamil Rytarowski at NetBSD.
while here, make the same change to KNOTE. ok deraadt

move knhash size to event.h, use it for hashfree. from Mathieu -
ok guenther

modern interfaces should use modern speelings, so spell quad_t as int64_t.

struct knote's kn_sdata needs to be the same type as struct kevent's data

ok deraadt@

knote_processexit() needs the thread to pass down to FRELE(), so pass it
the exiting thread instead of assuming that that's ps_mainproc.
Also, panic no matter which thread of init takes it down.

ok tedu@

Switch time_t, ino_t, clock_t, and struct kevent's ident and data
members to 64bit types. Assign new syscall numbers for (almost
all) the syscalls that involve the affected types, including anything
with time_t, timeval, itimerval, timespec, rusage, dirent, stat,
or kevent arguments. Add a d_off member to struct dirent and replace
getdirentries() with getdents(), thus immensely simplifying and
accelerating telldir/seekdir. Build perl with -DBIG_TIME.

Bump the major on every single base library: the compat bits included
here are only good enough to make the transition; the T32 compat
option will be burned as soon as we've reached the new world are
are happy with the snapshots for all architectures.

DANGER: ABI incompatibility. Updating to this kernel requires extra
work or you won't be able to login: install a snapshot instead.

Much assistance in fixing userland issues from deraadt@ and tedu@
and build assistance from todd@ and otto@

When a ucom(4) is removed, it frees the tty with ttyfree(). However if
anyone is waiting with kqueue their knotes may still have a reference to
the tty and later try to use it in the filt_tty* functions.

To avoid this, walk the knotes in ttyfree(), remove them from the tty's
list and invalidate them by setting kn_hook to NODEV. The filter
functions can then check for this and safely ignore the knotes.

ok tedu matthieu

Missed a comment in the proc->process change

EVFILT_SIGNAL and EVFILT_PROC events need to track the process they're
attached to and not just the thread, which can go away.

Problem observed by jsg@; ok jsg@ matthew@

Fix knote handling for exiting processes: when triggering a NOTE_EXIT
knote, remove it from the process's klist; after handling those,
remove and drop any remaining knotes from the process's klist. Ban
attaching knotes to processes that have started exiting or attaching
them via the pid of a thread other than the main thread.

ok tedu@, deraadt@

Add a dummy kqueue filter similar to seltrue and use it for anything
using seltrue for poll. Based on code from NetBSD.

Also remove a stray duplicate lpt entry from loongson, from deraadt.

ok tedu deraadt

wrap use of KNOTE macro arguments in () to prevent potential strange
expansion.

requested by otto@

wrap an if statement in a macro up with do { } while (0) so it is safe to
use in other if/else blocks.

"yeah" deraadt@

add a new kevent filter type for timers. this allows processes to create
a series of oneshot or periodic timers. capped to a global limit.
from freebsd via brad.
ok art pedro

Change sys/select.h -> sys/selinfo.h in comment.

klist_invalidate to help clean up when the backend disappears, tested by mpf@

add NOTE_EOF (return on EOF) and NOTE_TRUNCATE (vnode was truncated)
to kqueue
from marius@monkey tested by brad@

void *, not caddr_t. missed in last commit. thanks Marco Peereboom

filter event that simulates seltrue(). From NetBSD

filterops doesn't need to change, so we can make it const
ok deraadt@

First round of __P removal in sys

branches: 1.3.4; 1.3.8;
port kqueue changes from freebsd, plus all required openbsd glue.
okay deraadt@, millert@
from jlemon@freebsd.org:
extend kqueue down to the device layer, backwards compatible approach
suggested by peter@freebsd.org

rcsid; lots of bad tabs and spaces

support kernel event queues, from FreeBSD by Jonathan Lemon,
okay art@, millert@

Move the rest of common socket initialization within soalloc().

ok visa@

Move knote_processexit() call from exit1() to the reaper().
This fixes a problem where NOTE_EXIT could be received before
the process was officially a zombie and thus not immediately
waitable. OK deraadt@ visa@

Add helper functions for f_modify and f_process to condense code

These new functions, knote_modify() and knote_process(), implement
the logic that is common to most f_modify and f_process instances.

The code is inlined so as to not add yet another call frame on the
already towering stack of kqueue functions. Also, the _fn versions
allow direct calling of an event function when there is only one
filter type to handle.

Rename knote_modify() to knote_assign()

This avoids verb overlap with f_modify.

Check klist emptiness instead of NULL pointer in KNOTE()

All callers of KNOTE() supply a non-NULL klist argument. Replace the
NULL pointer check with klist emptiness check as a small optimization.

OK mpi@

Inline klist_empty() for more economic machine code.

OK mpi@

poll(2): Switch to kqueue backend

Implement the poll(2) system call on top of the kqueue subsystem.
This obsoletes the old, non-MP-safe poll backend.

On entering poll(2), the new code translates each pollfd array entry
into a set of knotes. When these knotes receive events through kqueue,
the events are translated back to pollfd format.

Entries in the pollfd array can refer to the same file descriptor with
overlapping event masks. To allow such overlap with knotes, use an extra
kn_pollid key that separates knotes of different pollfd entries.

Adapted from DragonFly BSD, initial implementation by mpi@.

Tested in snaps for three weeks.

OK mpi@

Clarify usage of __EV_POLL and __EV_SELECT

Make __EV_POLL specific to kqueue-based poll(2), to remove overlap
with __EV_SELECT that only select(2) uses.

OK millert@ mpi@

Fix select(2) exceptfds handling of FIFOs and pipes

Prevent select(2) from indicating an exceptional condition when the
other end of a FIFO or pipe is closed.

Originally, select(2) returned an exceptfds event only with a pty or
socket that has out-of-band data pending. millert@ says that OpenBSD
diverged from this by accident when poll(2) and select(2) were changed
to use the same backend code in year 2003.

OK millert@

kqueue: Revise badfd knote handling

When closing a file descriptor and converting the poll/select knotes
into badfd knotes, keep the knotes attached to the by-fd table. This
should prevent kqueue_purge() from returning before the kqueue has
become quiescent. This in turn should fix a
KASSERT(TAILQ_EMPTY(&kq->kq_head)) panic in KQRELE() that bluhm@ has
reported.

The badfd conversion is only needed when a poll/select scan is ongoing.
The system can skip the conversion if the knote is not part of the
active event set.

The code of this commit skips the conversion when the fd is closed by
the same thread that has done the fd polling. This can be improved but
should already cover typical fd usage patterns.

As badfd knotes now hold slots in the by-fd table, kqueue_register()
clears them. poll/select use kqueue_register() to set up a new scan;
any found fd close notification is a leftover from the previous scan.

The new badfd handling should be free of accidental knote accumulation.
This obsoletes kqpoll_dequeue() and lowers kqpoll_init() overhead.

Re-enable lazy removal of poll/select knotes because the panic should
no longer happen.

OK mpi@

Keep knotes between poll/select systems calls

Reduce the time overhead of kqueue-based poll(2) and select(2) by
keeping knotes registered between the system calls. It is expected that
the set of monitored file descriptors is relatively unchanged between
consecutive iterations of these system calls. By keeping the knotes,
the system saves the effort of repeated knote unregistering and
re-registering.

To avoid receiving events from file descriptors that are no longer in
the monitored set, each poll/select knote is assigned an increasing
serial number. Every iteration of poll/select uses a previously unused
range of serials for its knotes. In the setup stage, kqueue_register()
updates the serials of any existing knotes in the currently monitored
set. Function kqueue_scan() delivers only the events whose serials are
recent enough; expired knotes are dropped. When the serial range is
about to wrap around, all the knotes in the kqueue backend are dropped.

This change is a space-time tradeoff. Memory usage is increased somewhat
because of the retained knotes. The increase is limited by the number
of open file descriptors and active threads.

Idea from DragonFly BSD, initial patch by mpi@, kqueue_scan()-based
approach by me.

Tested by anton@ and mpi@
OK mpi@

Set klist lock for sockets to make socket event filters MP-safe

The filterops instances already provide f_modify and f_process
callbacks with proper internal locking. Locking of socket klists
has been the missing detail for MP-safety.

OK mpi@

kqueue: kq_lock is needed when updating kn_status

The kn_status field of struct knote is part of kqueue's internal state.
When kn_status is being updated, kq_lock has to be locked. This is true
even with MP-unsafe event filters.

OK mpi@

Enable pool cache on knote pool

Use the pool cache to reduce the overhead of memory management in
function kqueue_register().

When EV_ADD is given, kqueue_register() pre-allocates a knote to avoid
potential sleeping in the middle of the critical section that spans
from knote lookup to insertion. However, the pre-allocation is useless
if the lookup finds a matching knote.

The cost of knote allocation will become significant with kqueue-based
poll(2) and select(2) because the frequency of allocation will increase.
Most of the cost appears to come from the locking inside the pool.
The pool cache amortizes it by using CPU-local caches of free knotes
as buffers.

OK dlg@ mpi@

kqueue: Revise filterops interface

Extend kqueue's filterops interface with new callbacks so that it
becomes easier to use with fine-grained locking. The new interface
delegates the serialization of kn_event access to event sources. Now
kqueue uses filterops callbacks to read or write kn_event. This hides
event sources' locking patterns from kqueue, and allows clean
implementation of atomic read-and-clear for EV_CLEAR, for instance.

There are so many existing filterops instances that converting all of
them in one go is tricky. This patch adds a wrapper mechanism that
kqueue uses when the new callbacks are missing.

The new filterops interface has been influenced by XNU's kqueue.

OK mpi@ semarie@

kqueue: Revise fd close notification

Deliver file descriptor close notification for __EV_POLL knotes through
struct kevent that kqueue_scan() returns. This replaces the previous way
of returning EBADF from kqueue_scan(), making it easier to determine
what exactly has changed.

When a file descriptor is closed, its __EV_POLL knotes are turned into
one-shot events and queued for delivery. These knotes are "unregistered"
as they are reachable only through the queue of active events. This
reduces interference with the normal workings of kqueue. However, more
care is needed to avoid leaking knotes. In addition, the unregistering
removes a limit on the number of issued knotes. To prevent accumulation
of pending fd close notifications, kqpoll_init() flushes the active
queue at the start of a kqpoll scan.

OK mpi@

Refactor klist insertion and removal

Rename klist_{insert,remove}() to klist_{insert,remove}_locked().
These functions assume that the caller has locked the klist. The current
state of locking remains intact because the kernel lock is still used
with all klists.

Add new functions klist_insert() and klist_remove() that lock the klist
internally. This allows some code simplification.

OK mpi@

Introduce klistops

This patch extends struct klist with a callback descriptor and
an argument. The main purpose of this is to let the kqueue subsystem
assert when a klist should be locked, and operate the klist lock
in klist_invalidate().

Access to a knote list of a kqueue-monitored object has to be
serialized somehow. Because the object often has a lock for protecting
its state, and because the object often acquires this lock at the latest
in its f_event callback function, it makes sense to use this lock also
for the knote lists. The existing uses of NOTE_SUBMIT already show
a pattern that is likely to become more prevalent.

There could be an embedded lock in klist. However, such a lock would be
redundant in many cases. The code cannot rely on a single lock type
(mutex, rwlock, something else) because the needs of monitored objects
vary. In addition, an embedded lock would introduce new lock order
constraints. Note that the patch does not rule out use of dedicated
klist locks.

The patch introduces a way to associate lock operations with a klist.
The caller can provide a custom implementation, or use a ready-made
interface with a mutex or rwlock.

For compatibility with old code, the new code falls back to using the
kernel lock if no specific klist initialization has been done. The
existing code already relies on implicit initialization of klist.

Sadly, this change increases the size of struct klist. dlg@ thinks this
is not fatal, though.

OK mpi@

Make knote_{activate,remove}() internal to kern_event.c.

OK mpi@

Add kernel-only per-thread kqueue & helpers to initialize and free it.

This will soon be used by select(2) and poll(2).

ok anton@, visa@

Refactor kqueue_scan() so it can be used by other syscalls.

Stop iterating in the function and instead copy the returned events to
userland after every call.

ok visa@

Change kqueue_scan() to keep track of collected events in the given context.

It is now possible to call the function multiple times to collect events.
For that, the end marker has to be preserved between calls because otherwise
the scan might collect an event more than once. If a collected event gets
reactivated during scanning, it will be added at the tail of the queue,
out of reach because of the end marker.

This is required to implement select(2) and poll(2) on top of kqueue_scan().

Done & originally committed by visa@ in r1.143, in snap for more than 2 weeks.

ok visa@, anton@

Refactor kqueue_scan() to use a context: a "kqueue_scan_state struct".

The struct keeps track of the end point of an event queue scan by
persisting the end marker. This will be needed when kqueue_scan() is
called repeatedly to complete a scan in a piecewise fashion.

Extracted from a previous diff from visa@.

ok visa@, anton@

Allow userland to use EVFILT_EXCEPT.

ok mvs@, visa@

Extend kqueue interface with EVFILT_EXCEPT filter.

This filter, already implemented in macOS and Dragonfly BSD, returns
exceptional conditions like the reception of out-of-band data.

The functionnality is similar to poll(2)'s POLLPRI & POLLRDBAND and
it can be used by the kqfilter-based poll & select implementation.

ok millert@ on a previous version, ok visa@

Implement a simple kqfilter for deadfs matching its poll handler.

ok visa@, millert@

Set __EV_HUP when the conditions matching poll(2)'s POLLUP are found.

This is only done in poll-compatibility mode, when __EV_POLL is set.

ok visa@, millert@

Revert addition of double underbars for filter-specific flag.

Port breakages reported by naddy@

Rename poll-compatibility flag to better reflect what it is.

While here prefix kernel-only EV flags with two underbars.

Suggested by kettenis@, ok visa@

Use a new EV_OLDAPI flag to match the behavior of poll(2) and select(2).

Adapt FS kqfilters to always return true when the flag is set and bypass
the polling mechanism of the NFS thread.

While here implement a write filter for NFS.

ok visa@

Revert "Add kqueue_scan_state struct"

sthen@ has reported that the patch might be causing hangs with X.

Add kqueue_scan_state struct

The struct keeps track of the end point of an event queue scan by
persisting the end marker. This will be needed when kqueue_scan() is
called repeatedly to complete a scan in a piecewise fashion. The end
marker has to be preserved between calls because otherwise the scan
might collect an event more than once. If a collected event gets
reactivated during scanning, it will be added at the tail of the queue,
out of reach because of the end marker.

OK mpi@

Use a double-underscore prefix for local variables declared in macros
that have arguments. Document this requirement/recommendation in style(9)

prompted by mpi@
ok deraadt@

Abstract the head of knote lists. This allows extending the lists,
for example, with locking assertions.

OK mpi@, anton@

Prevent shadowing of local variable by the EV_SET() macro.

Use two underbars to start the locally defined variable, as suggested by
guenther@. The other option to avoid namespace conflict would be to start
the identifier with an underbar and a capital.

ok beck@, guenther@

Replace field f_isfd with field f_flags in struct filterops to allow
adding more filter properties without cluttering the struct.

OK mpi@, anton@

Use C99 designated initializers with struct filterops. In addition,
make the structs const so that the data are put in .rodata.

OK mpi@, deraadt@, anton@, bluhm@

Allow sleeping inside kqueue event filters.

In kqueue_scan(), threads have to get an exclusive access to a knote
before processing by calling knote_acquire(). This prevents the knote
from being destroyed while it is still in use. knote_acquire() also
blocks other threads from processing the knote. Once knote processing
has finished, the thread has to call knote_release().

The kqueue subsystem is still serialized by the kernel lock. If an event
filter sleeps, the kernel lock is released and another thread might
enter kqueue_scan(). kqueue_scan() uses start and end markers to keep
track of the scan's progress and it has to be aware of other threads'
markers.

This patch is a revised version of mpi@'s work derived
from DragonFly BSD. kqueue_check() has been adapted from NetBSD.

Tested by anton@, sashan@
OK mpi@, anton@, sashan@

introduce a filter called EVFILT_DEVICE that can be used to notify
listeners of device state changes.
currently only supports NOTE_CHANGE that will be used by drm(4)

ok kettenis@

Expand u_short and u_int to unsigned short and unsigned int
respectively to avoid compilation errors when one of the POSIX or
X/OPEN version macros is defined. Also sync the field descriptions
with kqueue.2. OK deraadt@

Revert support for multiple threads to enter kqueue_scan() in parallel.

It is not clear if this change is responsible for the lockups experienced
by dhill@ and jcs@ but since we're no longer grabbing the socket lock in
kqueue(2) filters there's no need for this change.

Make it possible for multiple threads to enter kqueue_scan() in parallel.

This is a requirement to use a sleeping lock inside kqueue filters.
It is now possible, but not recommended, to sleep inside ``f_event''.

Threads iterating over the list of pending events are now recognizing
and skipping other threads' markers. knote_acquire() and knote_release()
must be used to "own" a knote to make sure no other thread is sleeping
with a reference on it.

Acquire and marker logic taken from DragonFly but the KERNEL_LOCK()
is still serializing the execution of the kqueue code.

This also enable the NET_LOCK() in socket filters.

Tested by abieber@ & juanfra@, run by naddy@ in a bulk, ok visa@, bluhm@

Assert that the corresponding socket is locked when manipulating socket
buffers.

This is one step towards unlocking TCP input path. Note that all the
functions asserting for the socket lock are not necessarilly MP-safe.
All the fields of 'struct socket' aren't protected.

Introduce a new kernel-only kqueue hint, NOTE_SUBMIT, to be able to
tell when a filter needs to lock the underlying data structures. Logic
and name taken from NetBSD.

Tested by Hrvoje Popovski.

ok claudio@, bluhm@, mikeb@

Add support for EV_RECEIPT and EV_DISPATCH flags

From FreeBSD via Jan Schreiber <jes at posteo ! de>, thanks!
OK tedu, bluhm

make a copy of the first EV_SET argument to prevent multiple evaluation.
matches freebsd, fixes lldb. from Kamil Rytarowski at NetBSD.
while here, make the same change to KNOTE. ok deraadt

move knhash size to event.h, use it for hashfree. from Mathieu -
ok guenther

modern interfaces should use modern speelings, so spell quad_t as int64_t.

struct knote's kn_sdata needs to be the same type as struct kevent's data

ok deraadt@

knote_processexit() needs the thread to pass down to FRELE(), so pass it
the exiting thread instead of assuming that that's ps_mainproc.
Also, panic no matter which thread of init takes it down.

ok tedu@

Switch time_t, ino_t, clock_t, and struct kevent's ident and data
members to 64bit types. Assign new syscall numbers for (almost
all) the syscalls that involve the affected types, including anything
with time_t, timeval, itimerval, timespec, rusage, dirent, stat,
or kevent arguments. Add a d_off member to struct dirent and replace
getdirentries() with getdents(), thus immensely simplifying and
accelerating telldir/seekdir. Build perl with -DBIG_TIME.

Bump the major on every single base library: the compat bits included
here are only good enough to make the transition; the T32 compat
option will be burned as soon as we've reached the new world are
are happy with the snapshots for all architectures.

DANGER: ABI incompatibility. Updating to this kernel requires extra
work or you won't be able to login: install a snapshot instead.

Much assistance in fixing userland issues from deraadt@ and tedu@
and build assistance from todd@ and otto@

When a ucom(4) is removed, it frees the tty with ttyfree(). However if
anyone is waiting with kqueue their knotes may still have a reference to
the tty and later try to use it in the filt_tty* functions.

To avoid this, walk the knotes in ttyfree(), remove them from the tty's
list and invalidate them by setting kn_hook to NODEV. The filter
functions can then check for this and safely ignore the knotes.

ok tedu matthieu

Missed a comment in the proc->process change

EVFILT_SIGNAL and EVFILT_PROC events need to track the process they're
attached to and not just the thread, which can go away.

Problem observed by jsg@; ok jsg@ matthew@

Fix knote handling for exiting processes: when triggering a NOTE_EXIT
knote, remove it from the process's klist; after handling those,
remove and drop any remaining knotes from the process's klist. Ban
attaching knotes to processes that have started exiting or attaching
them via the pid of a thread other than the main thread.

ok tedu@, deraadt@

Add a dummy kqueue filter similar to seltrue and use it for anything
using seltrue for poll. Based on code from NetBSD.

Also remove a stray duplicate lpt entry from loongson, from deraadt.

ok tedu deraadt

wrap use of KNOTE macro arguments in () to prevent potential strange
expansion.

requested by otto@

wrap an if statement in a macro up with do { } while (0) so it is safe to
use in other if/else blocks.

"yeah" deraadt@

add a new kevent filter type for timers. this allows processes to create
a series of oneshot or periodic timers. capped to a global limit.
from freebsd via brad.
ok art pedro

Change sys/select.h -> sys/selinfo.h in comment.

klist_invalidate to help clean up when the backend disappears, tested by mpf@

add NOTE_EOF (return on EOF) and NOTE_TRUNCATE (vnode was truncated)
to kqueue
from marius@monkey tested by brad@

void *, not caddr_t. missed in last commit. thanks Marco Peereboom

filter event that simulates seltrue(). From NetBSD

filterops doesn't need to change, so we can make it const
ok deraadt@

First round of __P removal in sys

branches: 1.3.4; 1.3.8;
port kqueue changes from freebsd, plus all required openbsd glue.
okay deraadt@, millert@
from jlemon@freebsd.org:
extend kqueue down to the device layer, backwards compatible approach
suggested by peter@freebsd.org

rcsid; lots of bad tabs and spaces

support kernel event queues, from FreeBSD by Jonathan Lemon,
okay art@, millert@

Move knote_processexit() call from exit1() to the reaper().
This fixes a problem where NOTE_EXIT could be received before
the process was officially a zombie and thus not immediately
waitable. OK deraadt@ visa@

Add helper functions for f_modify and f_process to condense code

These new functions, knote_modify() and knote_process(), implement
the logic that is common to most f_modify and f_process instances.

The code is inlined so as to not add yet another call frame on the
already towering stack of kqueue functions. Also, the _fn versions
allow direct calling of an event function when there is only one
filter type to handle.

Rename knote_modify() to knote_assign()

This avoids verb overlap with f_modify.

Check klist emptiness instead of NULL pointer in KNOTE()

All callers of KNOTE() supply a non-NULL klist argument. Replace the
NULL pointer check with klist emptiness check as a small optimization.

OK mpi@

Inline klist_empty() for more economic machine code.

OK mpi@

poll(2): Switch to kqueue backend

Implement the poll(2) system call on top of the kqueue subsystem.
This obsoletes the old, non-MP-safe poll backend.

On entering poll(2), the new code translates each pollfd array entry
into a set of knotes. When these knotes receive events through kqueue,
the events are translated back to pollfd format.

Entries in the pollfd array can refer to the same file descriptor with
overlapping event masks. To allow such overlap with knotes, use an extra
kn_pollid key that separates knotes of different pollfd entries.

Adapted from DragonFly BSD, initial implementation by mpi@.

Tested in snaps for three weeks.

OK mpi@

Clarify usage of __EV_POLL and __EV_SELECT

Make __EV_POLL specific to kqueue-based poll(2), to remove overlap
with __EV_SELECT that only select(2) uses.

OK millert@ mpi@

Fix select(2) exceptfds handling of FIFOs and pipes

Prevent select(2) from indicating an exceptional condition when the
other end of a FIFO or pipe is closed.

Originally, select(2) returned an exceptfds event only with a pty or
socket that has out-of-band data pending. millert@ says that OpenBSD
diverged from this by accident when poll(2) and select(2) were changed
to use the same backend code in year 2003.

OK millert@

kqueue: Revise badfd knote handling

When closing a file descriptor and converting the poll/select knotes
into badfd knotes, keep the knotes attached to the by-fd table. This
should prevent kqueue_purge() from returning before the kqueue has
become quiescent. This in turn should fix a
KASSERT(TAILQ_EMPTY(&kq->kq_head)) panic in KQRELE() that bluhm@ has
reported.

The badfd conversion is only needed when a poll/select scan is ongoing.
The system can skip the conversion if the knote is not part of the
active event set.

The code of this commit skips the conversion when the fd is closed by
the same thread that has done the fd polling. This can be improved but
should already cover typical fd usage patterns.

As badfd knotes now hold slots in the by-fd table, kqueue_register()
clears them. poll/select use kqueue_register() to set up a new scan;
any found fd close notification is a leftover from the previous scan.

The new badfd handling should be free of accidental knote accumulation.
This obsoletes kqpoll_dequeue() and lowers kqpoll_init() overhead.

Re-enable lazy removal of poll/select knotes because the panic should
no longer happen.

OK mpi@

Keep knotes between poll/select systems calls

Reduce the time overhead of kqueue-based poll(2) and select(2) by
keeping knotes registered between the system calls. It is expected that
the set of monitored file descriptors is relatively unchanged between
consecutive iterations of these system calls. By keeping the knotes,
the system saves the effort of repeated knote unregistering and
re-registering.

To avoid receiving events from file descriptors that are no longer in
the monitored set, each poll/select knote is assigned an increasing
serial number. Every iteration of poll/select uses a previously unused
range of serials for its knotes. In the setup stage, kqueue_register()
updates the serials of any existing knotes in the currently monitored
set. Function kqueue_scan() delivers only the events whose serials are
recent enough; expired knotes are dropped. When the serial range is
about to wrap around, all the knotes in the kqueue backend are dropped.

This change is a space-time tradeoff. Memory usage is increased somewhat
because of the retained knotes. The increase is limited by the number
of open file descriptors and active threads.

Idea from DragonFly BSD, initial patch by mpi@, kqueue_scan()-based
approach by me.

Tested by anton@ and mpi@
OK mpi@

Set klist lock for sockets to make socket event filters MP-safe

The filterops instances already provide f_modify and f_process
callbacks with proper internal locking. Locking of socket klists
has been the missing detail for MP-safety.

OK mpi@

kqueue: kq_lock is needed when updating kn_status

The kn_status field of struct knote is part of kqueue's internal state.
When kn_status is being updated, kq_lock has to be locked. This is true
even with MP-unsafe event filters.

OK mpi@

Enable pool cache on knote pool

Use the pool cache to reduce the overhead of memory management in
function kqueue_register().

When EV_ADD is given, kqueue_register() pre-allocates a knote to avoid
potential sleeping in the middle of the critical section that spans
from knote lookup to insertion. However, the pre-allocation is useless
if the lookup finds a matching knote.

The cost of knote allocation will become significant with kqueue-based
poll(2) and select(2) because the frequency of allocation will increase.
Most of the cost appears to come from the locking inside the pool.
The pool cache amortizes it by using CPU-local caches of free knotes
as buffers.

OK dlg@ mpi@

kqueue: Revise filterops interface

Extend kqueue's filterops interface with new callbacks so that it
becomes easier to use with fine-grained locking. The new interface
delegates the serialization of kn_event access to event sources. Now
kqueue uses filterops callbacks to read or write kn_event. This hides
event sources' locking patterns from kqueue, and allows clean
implementation of atomic read-and-clear for EV_CLEAR, for instance.

There are so many existing filterops instances that converting all of
them in one go is tricky. This patch adds a wrapper mechanism that
kqueue uses when the new callbacks are missing.

The new filterops interface has been influenced by XNU's kqueue.

OK mpi@ semarie@

kqueue: Revise fd close notification

Deliver file descriptor close notification for __EV_POLL knotes through
struct kevent that kqueue_scan() returns. This replaces the previous way
of returning EBADF from kqueue_scan(), making it easier to determine
what exactly has changed.

When a file descriptor is closed, its __EV_POLL knotes are turned into
one-shot events and queued for delivery. These knotes are "unregistered"
as they are reachable only through the queue of active events. This
reduces interference with the normal workings of kqueue. However, more
care is needed to avoid leaking knotes. In addition, the unregistering
removes a limit on the number of issued knotes. To prevent accumulation
of pending fd close notifications, kqpoll_init() flushes the active
queue at the start of a kqpoll scan.

OK mpi@

Refactor klist insertion and removal

Rename klist_{insert,remove}() to klist_{insert,remove}_locked().
These functions assume that the caller has locked the klist. The current
state of locking remains intact because the kernel lock is still used
with all klists.

Add new functions klist_insert() and klist_remove() that lock the klist
internally. This allows some code simplification.

OK mpi@

Introduce klistops

This patch extends struct klist with a callback descriptor and
an argument. The main purpose of this is to let the kqueue subsystem
assert when a klist should be locked, and operate the klist lock
in klist_invalidate().

Access to a knote list of a kqueue-monitored object has to be
serialized somehow. Because the object often has a lock for protecting
its state, and because the object often acquires this lock at the latest
in its f_event callback function, it makes sense to use this lock also
for the knote lists. The existing uses of NOTE_SUBMIT already show
a pattern that is likely to become more prevalent.

There could be an embedded lock in klist. However, such a lock would be
redundant in many cases. The code cannot rely on a single lock type
(mutex, rwlock, something else) because the needs of monitored objects
vary. In addition, an embedded lock would introduce new lock order
constraints. Note that the patch does not rule out use of dedicated
klist locks.

The patch introduces a way to associate lock operations with a klist.
The caller can provide a custom implementation, or use a ready-made
interface with a mutex or rwlock.

For compatibility with old code, the new code falls back to using the
kernel lock if no specific klist initialization has been done. The
existing code already relies on implicit initialization of klist.

Sadly, this change increases the size of struct klist. dlg@ thinks this
is not fatal, though.

OK mpi@

Make knote_{activate,remove}() internal to kern_event.c.

OK mpi@

Add kernel-only per-thread kqueue & helpers to initialize and free it.

This will soon be used by select(2) and poll(2).

ok anton@, visa@

Refactor kqueue_scan() so it can be used by other syscalls.

Stop iterating in the function and instead copy the returned events to
userland after every call.

ok visa@

Change kqueue_scan() to keep track of collected events in the given context.

It is now possible to call the function multiple times to collect events.
For that, the end marker has to be preserved between calls because otherwise
the scan might collect an event more than once. If a collected event gets
reactivated during scanning, it will be added at the tail of the queue,
out of reach because of the end marker.

This is required to implement select(2) and poll(2) on top of kqueue_scan().

Done & originally committed by visa@ in r1.143, in snap for more than 2 weeks.

ok visa@, anton@

Refactor kqueue_scan() to use a context: a "kqueue_scan_state struct".

The struct keeps track of the end point of an event queue scan by
persisting the end marker. This will be needed when kqueue_scan() is
called repeatedly to complete a scan in a piecewise fashion.

Extracted from a previous diff from visa@.

ok visa@, anton@

Allow userland to use EVFILT_EXCEPT.

ok mvs@, visa@

Extend kqueue interface with EVFILT_EXCEPT filter.

This filter, already implemented in macOS and Dragonfly BSD, returns
exceptional conditions like the reception of out-of-band data.

The functionnality is similar to poll(2)'s POLLPRI & POLLRDBAND and
it can be used by the kqfilter-based poll & select implementation.

ok millert@ on a previous version, ok visa@

Implement a simple kqfilter for deadfs matching its poll handler.

ok visa@, millert@

Set __EV_HUP when the conditions matching poll(2)'s POLLUP are found.

This is only done in poll-compatibility mode, when __EV_POLL is set.

ok visa@, millert@

Revert addition of double underbars for filter-specific flag.

Port breakages reported by naddy@

Rename poll-compatibility flag to better reflect what it is.

While here prefix kernel-only EV flags with two underbars.

Suggested by kettenis@, ok visa@

Use a new EV_OLDAPI flag to match the behavior of poll(2) and select(2).

Adapt FS kqfilters to always return true when the flag is set and bypass
the polling mechanism of the NFS thread.

While here implement a write filter for NFS.

ok visa@

Revert "Add kqueue_scan_state struct"

sthen@ has reported that the patch might be causing hangs with X.

Add kqueue_scan_state struct

The struct keeps track of the end point of an event queue scan by
persisting the end marker. This will be needed when kqueue_scan() is
called repeatedly to complete a scan in a piecewise fashion. The end
marker has to be preserved between calls because otherwise the scan
might collect an event more than once. If a collected event gets
reactivated during scanning, it will be added at the tail of the queue,
out of reach because of the end marker.

OK mpi@

Use a double-underscore prefix for local variables declared in macros
that have arguments. Document this requirement/recommendation in style(9)

prompted by mpi@
ok deraadt@

Abstract the head of knote lists. This allows extending the lists,
for example, with locking assertions.

OK mpi@, anton@

Prevent shadowing of local variable by the EV_SET() macro.

Use two underbars to start the locally defined variable, as suggested by
guenther@. The other option to avoid namespace conflict would be to start
the identifier with an underbar and a capital.

ok beck@, guenther@

Replace field f_isfd with field f_flags in struct filterops to allow
adding more filter properties without cluttering the struct.

OK mpi@, anton@

Use C99 designated initializers with struct filterops. In addition,
make the structs const so that the data are put in .rodata.

OK mpi@, deraadt@, anton@, bluhm@

Allow sleeping inside kqueue event filters.

In kqueue_scan(), threads have to get an exclusive access to a knote
before processing by calling knote_acquire(). This prevents the knote
from being destroyed while it is still in use. knote_acquire() also
blocks other threads from processing the knote. Once knote processing
has finished, the thread has to call knote_release().

The kqueue subsystem is still serialized by the kernel lock. If an event
filter sleeps, the kernel lock is released and another thread might
enter kqueue_scan(). kqueue_scan() uses start and end markers to keep
track of the scan's progress and it has to be aware of other threads'
markers.

This patch is a revised version of mpi@'s work derived
from DragonFly BSD. kqueue_check() has been adapted from NetBSD.

Tested by anton@, sashan@
OK mpi@, anton@, sashan@

introduce a filter called EVFILT_DEVICE that can be used to notify
listeners of device state changes.
currently only supports NOTE_CHANGE that will be used by drm(4)

ok kettenis@

Expand u_short and u_int to unsigned short and unsigned int
respectively to avoid compilation errors when one of the POSIX or
X/OPEN version macros is defined. Also sync the field descriptions
with kqueue.2. OK deraadt@

Revert support for multiple threads to enter kqueue_scan() in parallel.

It is not clear if this change is responsible for the lockups experienced
by dhill@ and jcs@ but since we're no longer grabbing the socket lock in
kqueue(2) filters there's no need for this change.

Make it possible for multiple threads to enter kqueue_scan() in parallel.

This is a requirement to use a sleeping lock inside kqueue filters.
It is now possible, but not recommended, to sleep inside ``f_event''.

Threads iterating over the list of pending events are now recognizing
and skipping other threads' markers. knote_acquire() and knote_release()
must be used to "own" a knote to make sure no other thread is sleeping
with a reference on it.

Acquire and marker logic taken from DragonFly but the KERNEL_LOCK()
is still serializing the execution of the kqueue code.

This also enable the NET_LOCK() in socket filters.

Tested by abieber@ & juanfra@, run by naddy@ in a bulk, ok visa@, bluhm@

Assert that the corresponding socket is locked when manipulating socket
buffers.

This is one step towards unlocking TCP input path. Note that all the
functions asserting for the socket lock are not necessarilly MP-safe.
All the fields of 'struct socket' aren't protected.

Introduce a new kernel-only kqueue hint, NOTE_SUBMIT, to be able to
tell when a filter needs to lock the underlying data structures. Logic
and name taken from NetBSD.

Tested by Hrvoje Popovski.

ok claudio@, bluhm@, mikeb@

Add support for EV_RECEIPT and EV_DISPATCH flags

From FreeBSD via Jan Schreiber <jes at posteo ! de>, thanks!
OK tedu, bluhm

make a copy of the first EV_SET argument to prevent multiple evaluation.
matches freebsd, fixes lldb. from Kamil Rytarowski at NetBSD.
while here, make the same change to KNOTE. ok deraadt

move knhash size to event.h, use it for hashfree. from Mathieu -
ok guenther

modern interfaces should use modern speelings, so spell quad_t as int64_t.

struct knote's kn_sdata needs to be the same type as struct kevent's data

ok deraadt@

knote_processexit() needs the thread to pass down to FRELE(), so pass it
the exiting thread instead of assuming that that's ps_mainproc.
Also, panic no matter which thread of init takes it down.

ok tedu@

Switch time_t, ino_t, clock_t, and struct kevent's ident and data
members to 64bit types. Assign new syscall numbers for (almost
all) the syscalls that involve the affected types, including anything
with time_t, timeval, itimerval, timespec, rusage, dirent, stat,
or kevent arguments. Add a d_off member to struct dirent and replace
getdirentries() with getdents(), thus immensely simplifying and
accelerating telldir/seekdir. Build perl with -DBIG_TIME.

Bump the major on every single base library: the compat bits included
here are only good enough to make the transition; the T32 compat
option will be burned as soon as we've reached the new world are
are happy with the snapshots for all architectures.

DANGER: ABI incompatibility. Updating to this kernel requires extra
work or you won't be able to login: install a snapshot instead.

Much assistance in fixing userland issues from deraadt@ and tedu@
and build assistance from todd@ and otto@

When a ucom(4) is removed, it frees the tty with ttyfree(). However if
anyone is waiting with kqueue their knotes may still have a reference to
the tty and later try to use it in the filt_tty* functions.

To avoid this, walk the knotes in ttyfree(), remove them from the tty's
list and invalidate them by setting kn_hook to NODEV. The filter
functions can then check for this and safely ignore the knotes.

ok tedu matthieu

Missed a comment in the proc->process change

EVFILT_SIGNAL and EVFILT_PROC events need to track the process they're
attached to and not just the thread, which can go away.

Problem observed by jsg@; ok jsg@ matthew@

Fix knote handling for exiting processes: when triggering a NOTE_EXIT
knote, remove it from the process's klist; after handling those,
remove and drop any remaining knotes from the process's klist. Ban
attaching knotes to processes that have started exiting or attaching
them via the pid of a thread other than the main thread.

ok tedu@, deraadt@

Add a dummy kqueue filter similar to seltrue and use it for anything
using seltrue for poll. Based on code from NetBSD.

Also remove a stray duplicate lpt entry from loongson, from deraadt.

ok tedu deraadt

wrap use of KNOTE macro arguments in () to prevent potential strange
expansion.

requested by otto@

wrap an if statement in a macro up with do { } while (0) so it is safe to
use in other if/else blocks.

"yeah" deraadt@

add a new kevent filter type for timers. this allows processes to create
a series of oneshot or periodic timers. capped to a global limit.
from freebsd via brad.
ok art pedro

Change sys/select.h -> sys/selinfo.h in comment.

klist_invalidate to help clean up when the backend disappears, tested by mpf@

add NOTE_EOF (return on EOF) and NOTE_TRUNCATE (vnode was truncated)
to kqueue
from marius@monkey tested by brad@

void *, not caddr_t. missed in last commit. thanks Marco Peereboom

filter event that simulates seltrue(). From NetBSD

filterops doesn't need to change, so we can make it const
ok deraadt@

First round of __P removal in sys

branches: 1.3.4; 1.3.8;
port kqueue changes from freebsd, plus all required openbsd glue.
okay deraadt@, millert@
from jlemon@freebsd.org:
extend kqueue down to the device layer, backwards compatible approach
suggested by peter@freebsd.org

rcsid; lots of bad tabs and spaces

support kernel event queues, from FreeBSD by Jonathan Lemon,
okay art@, millert@

Add helper functions for f_modify and f_process to condense code

These new functions, knote_modify() and knote_process(), implement
the logic that is common to most f_modify and f_process instances.

The code is inlined so as to not add yet another call frame on the
already towering stack of kqueue functions. Also, the _fn versions
allow direct calling of an event function when there is only one
filter type to handle.

Rename knote_modify() to knote_assign()

This avoids verb overlap with f_modify.

Check klist emptiness instead of NULL pointer in KNOTE()

All callers of KNOTE() supply a non-NULL klist argument. Replace the
NULL pointer check with klist emptiness check as a small optimization.

OK mpi@

Inline klist_empty() for more economic machine code.

OK mpi@

poll(2): Switch to kqueue backend

Implement the poll(2) system call on top of the kqueue subsystem.
This obsoletes the old, non-MP-safe poll backend.

On entering poll(2), the new code translates each pollfd array entry
into a set of knotes. When these knotes receive events through kqueue,
the events are translated back to pollfd format.

Entries in the pollfd array can refer to the same file descriptor with
overlapping event masks. To allow such overlap with knotes, use an extra
kn_pollid key that separates knotes of different pollfd entries.

Adapted from DragonFly BSD, initial implementation by mpi@.

Tested in snaps for three weeks.

OK mpi@

Clarify usage of __EV_POLL and __EV_SELECT

Make __EV_POLL specific to kqueue-based poll(2), to remove overlap
with __EV_SELECT that only select(2) uses.

OK millert@ mpi@

Fix select(2) exceptfds handling of FIFOs and pipes

Prevent select(2) from indicating an exceptional condition when the
other end of a FIFO or pipe is closed.

Originally, select(2) returned an exceptfds event only with a pty or
socket that has out-of-band data pending. millert@ says that OpenBSD
diverged from this by accident when poll(2) and select(2) were changed
to use the same backend code in year 2003.

OK millert@

kqueue: Revise badfd knote handling

When closing a file descriptor and converting the poll/select knotes
into badfd knotes, keep the knotes attached to the by-fd table. This
should prevent kqueue_purge() from returning before the kqueue has
become quiescent. This in turn should fix a
KASSERT(TAILQ_EMPTY(&kq->kq_head)) panic in KQRELE() that bluhm@ has
reported.

The badfd conversion is only needed when a poll/select scan is ongoing.
The system can skip the conversion if the knote is not part of the
active event set.

The code of this commit skips the conversion when the fd is closed by
the same thread that has done the fd polling. This can be improved but
should already cover typical fd usage patterns.

As badfd knotes now hold slots in the by-fd table, kqueue_register()
clears them. poll/select use kqueue_register() to set up a new scan;
any found fd close notification is a leftover from the previous scan.

The new badfd handling should be free of accidental knote accumulation.
This obsoletes kqpoll_dequeue() and lowers kqpoll_init() overhead.

Re-enable lazy removal of poll/select knotes because the panic should
no longer happen.

OK mpi@