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>

libroot: fix try functions for pthread_rwlock.

These should return EBUSY instead of EDEADLK, so move the check
for deadlock into _Wait(), where the timeout can be checked prior
to the deadlock check.

Fixes the issue introduced in hrev56698.

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

libroot: pthread_rwlock_[rd|wr]lock detect simple deadlocks.

Whilst these are "may fail" in POSIX, they're easy to detect,
so fail early instead of deadlocking.

Return EDEADLK when trying to obtain a read/write lock if the
current thread already has a write lock.

Fixes part of #17971.

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

POSIX: introduce pthread_rwlock_clockrdlock and pthread_rwlock_clockwrlock

will appear in the next version: https://www.opengroup.org/austin/docs/austin_1110.pdf

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

headers: Remove libroot_lock.h.

Not used (the one file that included it did not actually use it),
and no longer needed with the introduction of user_mutex.

pthread_rwlock: use a mutex for process-private locks.

* instead of a benaphore.
* define PTHREAD_RWLOCK_INITIALIZER.
* adjust Init(), Destroy(), StructureLock() and StructureUnlock().

* _user_unblock_thread[s]() also set the user thread's wait_status, now. This
makes them more convenient to use, since the caller doesn't need to know the
target threads' user thread structure.
* Adjusted the pthread rwlock implementation accordingly.


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

Some work on pthreads:
* Made the pthread_cond_t internals public. This is necessary to support
process shared condition variables. Fixed initializer macro.
* Made the pthread_rwlockattr_t structure opaque.
* pthread_t is no longer typedef'ed to int. It's the pointer to the
internal _pthread_thread structure.
* Removed __get_pthread(). pthread_self() can be used instead.
* No longer tunnel the pthread exit value through Haiku's thread exit
value. We do have a separate field in the _pthread_thread structure
for it, now.
* Handle detaching of threads correctly.
* pthread_rwlockattr_{g,s}etpshared() use the
PTHREAD_PROCESS_{SHARED,PRIVATE} constants, now.
* Commented out yet unsupported structures (barriers, spinlocks).
* Rebuilt APR optional package. The pthread changes weren't binary
compatible.


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

* reader_count was not incremented when a waiting reader was woken up.
* Added comment clarifying the use of reader_count and writer_count.


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

Added pthread rwlock support.


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

* _user_unblock_thread[s]() also set the user thread's wait_status, now. This
makes them more convenient to use, since the caller doesn't need to know the
target threads' user thread structure.
* Adjusted the pthread rwlock implementation accordingly.


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

Some work on pthreads:
* Made the pthread_cond_t internals public. This is necessary to support
process shared condition variables. Fixed initializer macro.
* Made the pthread_rwlockattr_t structure opaque.
* pthread_t is no longer typedef'ed to int. It's the pointer to the
internal _pthread_thread structure.
* Removed __get_pthread(). pthread_self() can be used instead.
* No longer tunnel the pthread exit value through Haiku's thread exit
value. We do have a separate field in the _pthread_thread structure
for it, now.
* Handle detaching of threads correctly.
* pthread_rwlockattr_{g,s}etpshared() use the
PTHREAD_PROCESS_{SHARED,PRIVATE} constants, now.
* Commented out yet unsupported structures (barriers, spinlocks).
* Rebuilt APR optional package. The pthread changes weren't binary
compatible.


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

* reader_count was not incremented when a waiting reader was woken up.
* Added comment clarifying the use of reader_count and writer_count.


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

Added pthread rwlock support.


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