kernel/user_mutex: Fix unset of locked flag if no entries were notified.

It turns out this code actually is possible to trigger, e.g. using
Git checkouts, where EINTR due to signals happens quite often.
However, even with this commit, it still does not work quite right,
due to an oversight in condition-variable notify accounting. That
will be addressed in the next commit.

kernel & libroot: Implement per-team unnamed semaphores.

This requires breaking syscall ABI to add the "flags" parameter
to _kern_mutex_sem_release.

Resolves a TODO.

kernel/user_mutex: Check that a thread was actually unblocked during handoff.

Otherwise, we will deadlock.

I don't know that this has ever actually occurred; it is very unlikely
due to the write-lock acquisition before unblocking. It could only
occur if a SIGINT was delivered or timeout+wakeup occurred at just
the right moment.

kernel/user_mutex: Fix race in user_mutex_sem_release.

We need to be sure nothing will start waiting before marking the
semaphore as uncontended.

Fixes a deadlock observed in libuv.

user_mutex: Add "user_mutex" KDL command to dump user-mutex information.

It takes one parameter to specify a thread that is blocked on such
a user mutex.

Change-Id: I513ce130137a327cbaf305d2945e6cfe3c09879e
Reviewed-on: https://review.haiku-os.org/c/haiku/+/6606
Tested-by: Commit checker robot <no-reply+buildbot@haiku-os.org>
Reviewed-by: waddlesplash <waddlesplash@gmail.com>

user_mutex: Use unwired virtual addresses when possible.

This requires the use of fault handlers in the atomics.

GLTeapot now runs in the range of 590-610 FPS on my VM. However, it still
isn't using anywhere near 100% CPU usage. Some of that may be waiting for
app_server to respond to draw requests, but a lot of it still isn't.

Change-Id: I7be87d10cb1b00f07b055d9094b77837b49c5055
Reviewed-on: https://review.haiku-os.org/c/haiku/+/6603
Tested-by: Commit checker robot <no-reply+buildbot@haiku-os.org>
Reviewed-by: waddlesplash <waddlesplash@gmail.com>

user_mutex: Per-team contexts.

This requires the introduction of the flag B_USER_MUTEX_SHARED, and then
actually using the SHARED flags in pthread structures to determine when
it should be passed through.

This commit still uses wired memory even for per-team contexts.
That will change in the next commit.

GLTeapot FPS seems about the same.

Change-Id: I749a00dcea1531e113a65299b6d6610f57511fcc
Reviewed-on: https://review.haiku-os.org/c/haiku/+/6602
Reviewed-by: waddlesplash <waddlesplash@gmail.com>
Tested-by: Commit checker robot <no-reply+buildbot@haiku-os.org>

user_mutex: Granularize locking.

Now the table is locked with a rw_lock, and individual entries have
each their own rw_locks also.

This improves the "contention" benchmark I have here (2 locks, 6 threads,
acquire & release one lock 50,000 times per thread) mentioned in the last
commit down to under 4s consistently, around 3.45s with the system idle
and around 3.9s when moving windows around. Before this commit, it was
around 6.7s in the best case and 7.0s in the worst, and before that,
it couldn't break 3.8s in the best case.

This does make GLTeapot just slightly worse: it is now down to 310-330
(with occasional dips to 300-310) from 320-340. But the following commits
will improve that substantially.

Change-Id: Ie029a2510746f876f4d4c74d7e878fdadf3cf590
Reviewed-on: https://review.haiku-os.org/c/haiku/+/6601
Reviewed-by: waddlesplash <waddlesplash@gmail.com>
Tested-by: Commit checker robot <no-reply+buildbot@haiku-os.org>

kernel/user_mutex: Refactor around ConditionVariable features.

* Get rid of the multiple entries/condition-variables system.
Instead, allocate one structure per variable and do not add/remove
it from the hash until all waiters are gone.

* Get rid of "locked". All wait wakeups of B_OK mean "locked". All
nonzero values mean "not locked." This mirrors what the kernel mutex
implementation does (however, that also tracks the owning thread,
for assertion's sake.)

* Remove "lastWaiter" logic (for now.) As we no longer hold a lock
after wakeup, we cannot reliably check and act on it outside the
"wait" function. This means that interrupted or timed-out waits
will cause a potentially unnecessary syscall on next unblock,
but that will be resolved in the next commit.

Due to the single global lock, user mutex acquisition is an extremely
"noisy" process that can take shorter or longer depending on what is
going on elsewhere on the system, so performance is hard to measure.

With one benchmark that acquires mutexes as fast as possible with
lots of contention, most runs came in as being around the same amount
of time both before and after this change (around 4.25s real). Moving
Terminal's window around while running the test caused runtime to go
up to around 6.7s before this change, and about 7.0s after.

GLTeapot seems to go from 350-380 FPS before this change and 320-340
after. It still spends the vast majority of its time waiting for address
space and cache locks, however.

It is expected that the next commits will build on this change to
improve performance beyond even the "before" numbers above.

Change-Id: I6581a6f7cb0ca0513ea639f8499a1c0c8596c026
Reviewed-on: https://review.haiku-os.org/c/haiku/+/6490
Reviewed-by: waddlesplash <waddlesplash@gmail.com>
Reviewed-by: Adrien Destugues <pulkomandy@pulkomandy.tk>
Tested-by: Commit checker robot <no-reply+buildbot@haiku-os.org>

user_mutex: Adjust semantics of B_USER_MUTEX_UNBLOCK_ALL.

No longer is it required that the mutex be unlocked.
This was the case before the recent refactor, though it
wasn't noted anywhere. Now it is the case once more.

Should fix #18445.

user_mutex: Fix potential race in switch_lock.

We need to set the "to" mutex as locked+waiting before performing
the unlock of the first mutex, otherwise something in userland could
unset the "locked" flag but never call the kernel because "waiting"
had not yet been set.

In practice, the one consumer of this API (pthread_cond) could not,
at present, wind up in that situation, as far as I can tell, so this
race was entirely theoretical.

user_mutex: Refactor locking and unblocking mechanism.

Suppose the following scenario:

1. Thread A holds a mutex.

2. Thread B goes to acquire the mutex, winds up in kernel waiting.

3. Thread A unlocks; first unsets the LOCKED flag.
As WAITING is set, it calls the kernel; but instead of processing
this immediately, the thread is suspended for any reason (locks,
reschedule, etc.)

4. Thread B hits a timeout, or a signal. It then unblocks in the kernel,
which causes the WAITING flag to be unset.

5. Thread C goes to acquire the lock. It sets the LOCKED flag.
It sees the WAITING flag is not set, so it returns at once,
having successfully acquired the lock.

6. Thread A, suspended back in step 3, resumes.

Now we encounter the problem. Under the previous code, the following
would occur.

7. Thread A sees that no threads are waiting. It thus unsets the LOCKED
flag, and returns from the kernel. Now we have a mutex theoretically
held by thread C but which (illegally) has no LOCKED flag set!

8. Some other thread tries to acquire the lock, and succeeds, for LOCKED
is not set. We now have one lock owned by two separate threads.
That's very bad!

The solution, in this commit, is to (1) switch from using "atomic_or"
to lock mutexes, to using "atomic_test_and_set", and (2) mandate that
_kern_unblock_mutex must be invoked with the mutex already unlocked.

Trying to solve the problem with (2) but without (1) produces other
complications and would overall be more complicated. For instance,
all existing userland code expected that it would set LOCKED, but then
check LOCKED|WAITING. If _kern_mutex_unlock does not unset LOCKED,
then whichever thread sets LOCKED when it was previously unset is
now the mutex's undisputed owner, and if it fails to notice this,
would deadlock.

That could have been solved with extra checks at all lock points, but
then that would mean locks would not be acquired "fairly": it would
be possible for any thread to race with an unlocking thread, and
acquire the lock before the kernel had a chance to wake anyone up.

Given how fast atomics can be, and how slow invoking the kernel is
comparatively, that would probably make our mutexes extremely "unfair."
This would not violate the POSIX specification, but it does seem like
a dangerous choice to make in implementing these APIs.

Linux's "futex" API, which our API bears some similarities to, requires
at least one atomic test-and-set for an uncontended acquisition,
and multiple atomics more for even the simplest case of contended
acquisition. If it works for them, it should work for us, too.

Fixes #18436.

Change-Id: Ib8c28acf04ce03234fe738e41aa0969ca1917540
Reviewed-on: https://review.haiku-os.org/c/haiku/+/6537
Tested-by: Commit checker robot <no-reply+buildbot@haiku-os.org>
Reviewed-by: Adrien Destugues <pulkomandy@pulkomandy.tk>
Reviewed-by: waddlesplash <waddlesplash@gmail.com>

kernel/user_mutex: Fix another instance of addr_t.

Spotted by korli.

kernel/user_mutex: Use phys_addr_t for hash keys.

This could fix address collisions on 32-bit systems with PAE.

Fixes #18435.

kernel/user_mutex: Create utility functions for the user_atomics.

In the future, these should be moved to another file (and fault handlers
used), but at least this de-clutters the code a bit for now.

kernel: Make use of the new ConditionVariable lock-switching APIs in a few places.

kernel: support for Intel SMAP and SMEP on x86_64.

SMAP will generated page faults when the kernel tries to access user pages unless overriden.
If SMAP is enabled, the override instructions are written where needed in memory with
binary "altcodepatches".
Support is enabled by default, might be disabled per safemode setting.

Change-Id: Ife26cd765056aeaf65b2ffa3cadd0dcf4e273a96

Reimplement unnamed POSIX semaphores using user_mutex

* Fixes sharing semantics, so non-shared semaphores in non-shared
memory do not become shared after a fork.
* Adds two new system calls: _user_mutex_sem_acquire/release(),
which reuse the user_mutex address-hashed wait mechanism.
* Named semaphores continue to use traditional sem_id semaphores.

user mutex: dequeue waiters when waking them up

* This prevents the same waiter being woken multiple times, before it
has a chance to run and dequeue itself.

Remove remaining unnecessary 'volatile' qualifiers

* remove_user_mutex_entry(): The next entry wasn't removed from its own list.
* user_mutex_unlock_locked(): Set or clear the locked flag depending on whether
we wake up a waiter.
* _user_mutex_switch_lock(): The syscall cannot be restartable.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@36319 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

Reimplement unnamed POSIX semaphores using user_mutex

* Fixes sharing semantics, so non-shared semaphores in non-shared
memory do not become shared after a fork.
* Adds two new system calls: _user_mutex_sem_acquire/release(),
which reuse the user_mutex address-hashed wait mechanism.
* Named semaphores continue to use traditional sem_id semaphores.

user mutex: dequeue waiters when waking them up

* This prevents the same waiter being woken multiple times, before it
has a chance to run and dequeue itself.

Remove remaining unnecessary 'volatile' qualifiers

* remove_user_mutex_entry(): The next entry wasn't removed from its own list.
* user_mutex_unlock_locked(): Set or clear the locked flag depending on whether
we wake up a waiter.
* _user_mutex_switch_lock(): The syscall cannot be restartable.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@36319 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