kernel: Add event queue implementation to wait for objects efficiently.

Based on hamishm's original patch from 2015, but heavily modified,
refactored, and reworked.

From the original commit message:

> When an object is deleted, a B_EVENT_INVALID event is delivered,
> and the object is unregistered from the queue.
>
> The special event flag B_EVENT_ONE_SHOT can be passed in when adding
> an object so that the object is automatically unregistered when an
> event is delivered.

Modifications to the original change include:

* Removed the public interface (syscalls remain private for the moment)

* Event list queueing/dequeueing almost entirely rewritten, including:
- Clear events field when dequeueing.

- Have B_EVENT_QUEUED actually indicate whether the event has been
appended to the linked list (or not), based around lock state.
The previous logic was prone to races and double-insertions.

- "Modify" is now just "Deselect + Select" performed at once;
previously it could cause use-after-frees.

- Unlock for deselect only once at the end of dequeue.

- Handle INVALID events still in the queue upon destruction,
fixing memory leaks.

* Deduplified code with wait_for_objects.

* Use of C++ virtual dispatch instead of C-style enum + function calls,
and BReferenceable plus destructors for teardown.

* Removed select/modify/delete flags. Select/Modify are now the same
operation on the syscall interface, and "Delete" is done when 0
is passed for "events". Additionally, the events selected can be fetched
by passing -1 for "events".

* Implemented level-triggered mode.

* Use of BStackOrHeapArray and other convenience routines in syscalls.

Change-Id: I1d2f094fd981c95215a59adbc087523c7bbbe40b
Reviewed-on: https://review.haiku-os.org/c/haiku/+/6745
Tested-by: Commit checker robot <no-reply+buildbot@haiku-os.org>
Reviewed-by: Jérôme Duval <jerome.duval@gmail.com>

kernel: remove incorrect inline and static keywords for syscalls.

Fix various 64 bit related warnings

Mostly printf() format strings and signed-unsigned comparisons.
Fixes the x86_64 build.

Merged signals-merge branch into trunk with the following changes:
* Reorganized the kernel locking related to threads and teams.
* We now discriminate correctly between process and thread signals. Signal
handlers have been moved to teams. Fixes #5679.
* Implemented real-time signal support, including signal queuing, SA_SIGINFO
support, sigqueue(), sigwaitinfo(), sigtimedwait(), waitid(), and the addition
of the real-time signal range. Closes #1935 and #2695.
* Gave SIGBUS a separate signal number. Fixes #6704.
* Implemented <time.h> clock and timer support, and fixed/completed alarm() and
[set]itimer(). Closes #5682.
* Implemented support for thread cancellation. Closes #5686.
* Moved send_signal() from <signal.h> to <OS.h>. Fixes #7554.
* Lots over smaller more or less related changes.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@42116 a95241bf-73f2-0310-859d-f6bbb57e9c96

Merged the signals branch into trunk, with these changes:
* The team and thread kernel structures have been renamed to Team and Thread
respectively and moved into the new BKernel namespace.
* Several (kernel add-on) sources have been converted from C to C++ since
private kernel headers are included that are no longer C compatible.

Changes after merging:
* Fixed gcc 2 build (warnings mainly in the scary firewire bus manager).


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@40196 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Building with syscall tracing obviously needs this header now.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@37326 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Moved created subdirectory src/system/kernel/lock.cpp to new subdirectory
locks.
* Added syscalls for a new kind of mutex. A mutex consists only of an int32 and
doesn't require any kernel resources. So it's initialization cannot fail
(it consists only of setting the mutex value to 0). An uncontended lock or
unlock operation can basically consist of an atomic_*() in userland. The
syscalls (when the mutex is contended) are a bit more expensive than semaphore
operations, though.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@36158 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Moved the VM headers into subdirectory vm/.
* Renamed vm_cache.h/vm_address_space.h to VMCache.h/VMAddressSpace.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34449 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Use a condition variable when waiting for a syscall to be done calling.
* Use C++ DoublyLinkedList class instead of the struct list.
* Note, this code is untested yet, but I will test it now (Qemu doesn't work
on Haiku anymore for some reason) :-)


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34382 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Introduced a flag to decide whether it's still okay to call a certain
syscall.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34238 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Cleanup, no functional change.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34237 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Added a use counter for the syscalls, so that they are no longer removed
while a hook is called.
* This closes ticket #5027.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34233 a95241bf-73f2-0310-859d-f6bbb57e9c96

The kernel side of a new system-wide sampling-based profiling mechanism.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@30127 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Implemented a (private for now) get_system_info_etc() call, that can retrieve
various system information.
* Implemented retrieving some VM stats via this call.
* The VM now maintains a page fault counter, and sets system_info::page_faults
accordingly.
* Added a (pretty simple) "vmstat" command line app.
* Minor cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@27597 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Adding msg{rcv,snd,get,ctl} syscalls to the system
* Add message queue init function call to main.cpp


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@27417 a95241bf-73f2-0310-859d-f6bbb57e9c96

First patch by Salvatore to implement XSI semaphores with a few changes
by myself:
* renamed xsi_do_undo() to xsi_sem_undo() (there is more to XSI than sems).
* Fixed coding style issues in sys/sem.h and xsi_sem.cpp.
* Added _kern_*() syscall prototypes to syscalls.h.
* Added a TODO in xsi_sem.cpp and xsi_semaphore.h about moving union semun to
a shared header.
* Made the team::xsi_sem_undo_requests int32 - due to padding, it would have
needed 4 bytes anyway; please always use specific types over int/short/long.
* xsi_sem_undo() now checks if it needs to do anything - the calls in team.cpp
no longer needs to do this.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@26676 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Initialize all static mutexes in the kernel through a MUTEX_INITIALIZER()
and remove the then unneeded mutex_init() for them.
* Remove the workaround for allowing uninitialized mutexes on kernel startup.
As they are all initialized statically through the MUTEX_INITIALIZER() now
this is not needed anymore.
* An uninitialized mutex will now cause a panic when used to find possibly
remaining cases.
* Remove now unnecessary driver_settings_init_post_sem() function.

git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@25812 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Moved realtime_sem.{cpp,h} into new posix subdirectory.
* Renamed the old kernel_posix[_arch...].o to kernel_lib_posix...


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@25336 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added support for POSIX semaphores (the ones from the XSI extension
Realtime option group). The implementation should be complete, but is
totally untested yet.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@25326 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Removed old mutex implementation and renamed cutex to mutex.
* Trivial adjustments of code using mutexes. Mostly removing the
mutex_init() return value check.
* Added mutex_lock_threads_locked(), which is called with the threads
spinlock being held. The spinlock is released while waiting, of
course. This function is useful in cases where the existence of the
mutex object is ensured by holding the threads spinlock.
* Changed the two instances in the VFS code where an IO context of
another team needs to be locked to use mutex_lock_threads_locked().
Before it required a semaphore-based mutex implementation.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@25283 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Changed macros that enable tracing for individual components from
defined/undefined to numeric values (0 for undefined). This allows for
trace levels.
* Set SYSCALL_TRACING_IGNORE_KTRACE_OUTPUT default to 1, since this is
what one usually wants.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@25213 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added "straced" debugger command which basically works like "traced",
but also prints post syscall entries not matching the filter, if the
respective pre syscall entry matched. This way one also sees the syscall
return values. Works only in forward direction ATM.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@25095 a95241bf-73f2-0310-859d-f6bbb57e9c96

Removed unused _kern_socket() dummy.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@24907 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added new macro SYSCALL_TRACING_IGNORE_KTRACE_OUTPUT to disable tracing
for the _kern_ktrace_output() syscall.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@24392 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Added real, effective and saved set- user and group IDs to the team
structure. They are properly inherited and updated on
fork(), load_image(), and exec().
* Implemented the get[e]{u,g}id(), set[[r]e]{u,g}id() family for real.
* getgroups() also calls the kernel now, but only returns the effective
group ID. Supplementary groups support is still missing.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@24359 a95241bf-73f2-0310-859d-f6bbb57e9c96

Also check the syscall number to avoid problems.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@23920 a95241bf-73f2-0310-859d-f6bbb57e9c96

Debug code. From time to time I still see 64 bit return values when they
should be 32 bit only.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@23917 a95241bf-73f2-0310-859d-f6bbb57e9c96

Syscall tracing no longer fetches the string parameter of the
_kern_ktrace_output() syscall, since it will be stored in a separate
entry anyway.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@23807 a95241bf-73f2-0310-859d-f6bbb57e9c96

Renamed syscall_parameters_info structure to extended_syscall_info (and
kSyscallParametersInfos to kExtendedSyscallInfos) and added "name"
field. Now the classes for syscall kernel tracing don't need to lookup
the syscall function symbol anymore, which speeds up printing/filtering
of those entries dramatically.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@23687 a95241bf-73f2-0310-859d-f6bbb57e9c96

Moved tracing macro definitions into separate tracing_config.h header.
So now there's a central place to enable tracing in general and for
individual components.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@23645 a95241bf-73f2-0310-859d-f6bbb57e9c96

TraceBuffer simplifies things a bit.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@23623 a95241bf-73f2-0310-859d-f6bbb57e9c96

Kernel tracing of syscalls uses more information about the syscall
parameters, now. We print 64 bit values correctly, and also fetch
strings from userland and print them.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@23620 a95241bf-73f2-0310-859d-f6bbb57e9c96

* syscalls.c -> syscalls.cpp
* With post syscall debugging enabled, the x86 syscall handling didn't
remove all parameters from the stack after calling the respective user
debugger hook. Should have been harmless though, since the following
code didn't rely on the stack being in order.
* Added syscall pre/post (kernel) tracing functions
trace_{pre,post}_syscall(). They are generic, but need to be invoked
by the architecture specific syscall code. Currently only done for
x86.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@23600 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fix various 64 bit related warnings

Mostly printf() format strings and signed-unsigned comparisons.
Fixes the x86_64 build.

Merged signals-merge branch into trunk with the following changes:
* Reorganized the kernel locking related to threads and teams.
* We now discriminate correctly between process and thread signals. Signal
handlers have been moved to teams. Fixes #5679.
* Implemented real-time signal support, including signal queuing, SA_SIGINFO
support, sigqueue(), sigwaitinfo(), sigtimedwait(), waitid(), and the addition
of the real-time signal range. Closes #1935 and #2695.
* Gave SIGBUS a separate signal number. Fixes #6704.
* Implemented <time.h> clock and timer support, and fixed/completed alarm() and
[set]itimer(). Closes #5682.
* Implemented support for thread cancellation. Closes #5686.
* Moved send_signal() from <signal.h> to <OS.h>. Fixes #7554.
* Lots over smaller more or less related changes.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@42116 a95241bf-73f2-0310-859d-f6bbb57e9c96

Merged the signals branch into trunk, with these changes:
* The team and thread kernel structures have been renamed to Team and Thread
respectively and moved into the new BKernel namespace.
* Several (kernel add-on) sources have been converted from C to C++ since
private kernel headers are included that are no longer C compatible.

Changes after merging:
* Fixed gcc 2 build (warnings mainly in the scary firewire bus manager).


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@40196 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Building with syscall tracing obviously needs this header now.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@37326 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Moved created subdirectory src/system/kernel/lock.cpp to new subdirectory
locks.
* Added syscalls for a new kind of mutex. A mutex consists only of an int32 and
doesn't require any kernel resources. So it's initialization cannot fail
(it consists only of setting the mutex value to 0). An uncontended lock or
unlock operation can basically consist of an atomic_*() in userland. The
syscalls (when the mutex is contended) are a bit more expensive than semaphore
operations, though.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@36158 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Moved the VM headers into subdirectory vm/.
* Renamed vm_cache.h/vm_address_space.h to VMCache.h/VMAddressSpace.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34449 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Use a condition variable when waiting for a syscall to be done calling.
* Use C++ DoublyLinkedList class instead of the struct list.
* Note, this code is untested yet, but I will test it now (Qemu doesn't work
on Haiku anymore for some reason) :-)


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34382 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Introduced a flag to decide whether it's still okay to call a certain
syscall.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34238 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Cleanup, no functional change.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34237 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Added a use counter for the syscalls, so that they are no longer removed
while a hook is called.
* This closes ticket #5027.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34233 a95241bf-73f2-0310-859d-f6bbb57e9c96

The kernel side of a new system-wide sampling-based profiling mechanism.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@30127 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Implemented a (private for now) get_system_info_etc() call, that can retrieve
various system information.
* Implemented retrieving some VM stats via this call.
* The VM now maintains a page fault counter, and sets system_info::page_faults
accordingly.
* Added a (pretty simple) "vmstat" command line app.
* Minor cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@27597 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Adding msg{rcv,snd,get,ctl} syscalls to the system
* Add message queue init function call to main.cpp


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@27417 a95241bf-73f2-0310-859d-f6bbb57e9c96

First patch by Salvatore to implement XSI semaphores with a few changes
by myself:
* renamed xsi_do_undo() to xsi_sem_undo() (there is more to XSI than sems).
* Fixed coding style issues in sys/sem.h and xsi_sem.cpp.
* Added _kern_*() syscall prototypes to syscalls.h.
* Added a TODO in xsi_sem.cpp and xsi_semaphore.h about moving union semun to
a shared header.
* Made the team::xsi_sem_undo_requests int32 - due to padding, it would have
needed 4 bytes anyway; please always use specific types over int/short/long.
* xsi_sem_undo() now checks if it needs to do anything - the calls in team.cpp
no longer needs to do this.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@26676 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Initialize all static mutexes in the kernel through a MUTEX_INITIALIZER()
and remove the then unneeded mutex_init() for them.
* Remove the workaround for allowing uninitialized mutexes on kernel startup.
As they are all initialized statically through the MUTEX_INITIALIZER() now
this is not needed anymore.
* An uninitialized mutex will now cause a panic when used to find possibly
remaining cases.
* Remove now unnecessary driver_settings_init_post_sem() function.

git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@25812 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Moved realtime_sem.{cpp,h} into new posix subdirectory.
* Renamed the old kernel_posix[_arch...].o to kernel_lib_posix...


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@25336 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added support for POSIX semaphores (the ones from the XSI extension
Realtime option group). The implementation should be complete, but is
totally untested yet.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@25326 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Removed old mutex implementation and renamed cutex to mutex.
* Trivial adjustments of code using mutexes. Mostly removing the
mutex_init() return value check.
* Added mutex_lock_threads_locked(), which is called with the threads
spinlock being held. The spinlock is released while waiting, of
course. This function is useful in cases where the existence of the
mutex object is ensured by holding the threads spinlock.
* Changed the two instances in the VFS code where an IO context of
another team needs to be locked to use mutex_lock_threads_locked().
Before it required a semaphore-based mutex implementation.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@25283 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Changed macros that enable tracing for individual components from
defined/undefined to numeric values (0 for undefined). This allows for
trace levels.
* Set SYSCALL_TRACING_IGNORE_KTRACE_OUTPUT default to 1, since this is
what one usually wants.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@25213 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added "straced" debugger command which basically works like "traced",
but also prints post syscall entries not matching the filter, if the
respective pre syscall entry matched. This way one also sees the syscall
return values. Works only in forward direction ATM.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@25095 a95241bf-73f2-0310-859d-f6bbb57e9c96

Removed unused _kern_socket() dummy.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@24907 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added new macro SYSCALL_TRACING_IGNORE_KTRACE_OUTPUT to disable tracing
for the _kern_ktrace_output() syscall.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@24392 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Added real, effective and saved set- user and group IDs to the team
structure. They are properly inherited and updated on
fork(), load_image(), and exec().
* Implemented the get[e]{u,g}id(), set[[r]e]{u,g}id() family for real.
* getgroups() also calls the kernel now, but only returns the effective
group ID. Supplementary groups support is still missing.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@24359 a95241bf-73f2-0310-859d-f6bbb57e9c96

Also check the syscall number to avoid problems.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@23920 a95241bf-73f2-0310-859d-f6bbb57e9c96

Debug code. From time to time I still see 64 bit return values when they
should be 32 bit only.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@23917 a95241bf-73f2-0310-859d-f6bbb57e9c96

Syscall tracing no longer fetches the string parameter of the
_kern_ktrace_output() syscall, since it will be stored in a separate
entry anyway.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@23807 a95241bf-73f2-0310-859d-f6bbb57e9c96

Renamed syscall_parameters_info structure to extended_syscall_info (and
kSyscallParametersInfos to kExtendedSyscallInfos) and added "name"
field. Now the classes for syscall kernel tracing don't need to lookup
the syscall function symbol anymore, which speeds up printing/filtering
of those entries dramatically.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@23687 a95241bf-73f2-0310-859d-f6bbb57e9c96

Moved tracing macro definitions into separate tracing_config.h header.
So now there's a central place to enable tracing in general and for
individual components.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@23645 a95241bf-73f2-0310-859d-f6bbb57e9c96

TraceBuffer simplifies things a bit.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@23623 a95241bf-73f2-0310-859d-f6bbb57e9c96

Kernel tracing of syscalls uses more information about the syscall
parameters, now. We print 64 bit values correctly, and also fetch
strings from userland and print them.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@23620 a95241bf-73f2-0310-859d-f6bbb57e9c96

* syscalls.c -> syscalls.cpp
* With post syscall debugging enabled, the x86 syscall handling didn't
remove all parameters from the stack after calling the respective user
debugger hook. Should have been harmless though, since the following
code didn't rely on the stack being in order.
* Added syscall pre/post (kernel) tracing functions
trace_{pre,post}_syscall(). They are generic, but need to be invoked
by the architecture specific syscall code. Currently only done for
x86.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@23600 a95241bf-73f2-0310-859d-f6bbb57e9c96