[prev in list] [next in list] [prev in thread] [next in thread]
List: haiku-commits
Subject: [haiku-commits] haiku: hrev55671 - src/system/kernel
From: waddlesplash <waddlesplash () gmail ! com>
Date: 2021-11-30 2:18:30
Message-ID: 20211130021830.906CE400CE () turing ! freelists ! org
[Download RAW message or body]
hrev55671 adds 1 changeset to branch 'master'
old head: 7a855aa5c740b005e296803036efacbbad208c33
new head: 02077ffc4257b5c682270db4cd715a2610dcbb26
overview: https://git.haiku-os.org/haiku/log/?qt=range&q=02077ffc4257+%5E7a855aa5c740
----------------------------------------------------------------------------
02077ffc4257: kernel/condition_variable: Atomicize ConditionVariableEntry and drop the lock.
Before 2019, the entire ConditionVariable system was "giant"-locked:
that is, there was a single global lock that all ConditionVariable
and ConditionVariableEntry operations had to pass through. This of
course was not very performant on multicore systems and when
ConditionVariables see significant use, so I reworked it then to have
more granular locking.
Those patches took a number of attempts to get right, as having two
objects in separate threads that can each access the other not turn
into a deadlock or use-after-free is not easy to say the least,
and the ultimate solution I came up with erased most of the performance
gains I initially saw on the first (partially broken) patchsets.
So I have wanted to revisit this and see if there was a better way
even since then. Recently there have been a few reports of
ConditionVariable-related panics (apparently double unlocks),
notably #16894, and so that was reason enough to actually revisit
this code and see if a better solution could be found.
Well, I think I have come up with one: after this commit, Entries
no longer have their own lock, and instead accesses to Entry members
are almost always atomic; and there is now a case where we spin inside
Variable::_NotifyLocked as well as one in Entry::_RemoveFromVariable.
This leads to somewhat simpler code (no more lock/unlock dance in Notify),
though it is significantly more difficult to understand the nuances of it,
so I have left a sizable number of comments explaining the intricacies
of the new logic.
Note: I initially tried 1000 for "tries", but on a few instances I did see
the panic hit, strangely. I don't think the code that is waited on can
be reasonably reduced any further, so I have just increased the limit to
10000 (which is still well below what spinlocks use.) Hopefully this suffices.
Quick benchmark, x86, compiling HaikuDepot and the mime_db in VMware, 2 cores:
before:
real 0m23.627s
user 0m25.152s
sys 0m7.319s
after:
real 0m23.962s
user 0m25.229s
sys 0m7.330s
Though I occasionally I saw sys times as low as 7.171s, so this seems
to be at least not a regression if not a definitive improvement.
Change-Id: Id042947976885cd5c1433cc4290bdf41b01ed10e
Reviewed-on: https://review.haiku-os.org/c/haiku/+/4727
Tested-by: Commit checker robot <no-reply+buildbot@haiku-os.org>
Reviewed-by: Alex von Gluck IV <kallisti5@unixzen.com>
[ Augustin Cavalier <waddlesplash@gmail.com> ]
----------------------------------------------------------------------------
Revision: hrev55671
Commit: 02077ffc4257b5c682270db4cd715a2610dcbb26
URL: https://git.haiku-os.org/haiku/commit/?id=02077ffc4257
Author: Augustin Cavalier <waddlesplash@gmail.com>
Date: Tue Nov 23 22:20:18 2021 UTC
Committer: waddlesplash <waddlesplash@gmail.com>
Commit-Date: Tue Nov 30 02:18:27 2021 UTC
Ticket: https://dev.haiku-os.org/ticket/16894
----------------------------------------------------------------------------
2 files changed, 91 insertions(+), 49 deletions(-)
headers/private/kernel/condition_variable.h | 3 +-
src/system/kernel/condition_variable.cpp | 137 +++++++++++++++---------
----------------------------------------------------------------------------
diff --git a/headers/private/kernel/condition_variable.h b/headers/private/kernel/condition_variable.h
index da327f76ef..2a3d60545c 100644
--- a/headers/private/kernel/condition_variable.h
+++ b/headers/private/kernel/condition_variable.h
@@ -40,7 +40,6 @@ private:
void _RemoveFromVariable();
private:
- spinlock fLock;
ConditionVariable* fVariable;
Thread* fThread;
status_t fWaitStatus;
@@ -92,6 +91,8 @@ protected:
spinlock fLock;
EntryList fEntries;
+ int32 fEntriesCount;
+
ConditionVariable* fNext;
friend struct ConditionVariableEntry;
diff --git a/src/system/kernel/condition_variable.cpp b/src/system/kernel/condition_variable.cpp
index c26d1526e6..acd3be3d67 100644
--- a/src/system/kernel/condition_variable.cpp
+++ b/src/system/kernel/condition_variable.cpp
@@ -98,6 +98,8 @@ ConditionVariableEntry::ConditionVariableEntry()
ConditionVariableEntry::~ConditionVariableEntry()
{
+ // We can use an "unsafe" non-atomic access of fVariable here, since we only
+ // care whether it is non-NULL, not what its specific value is.
if (fVariable != NULL)
_RemoveFromVariable();
}
@@ -132,37 +134,60 @@ ConditionVariableEntry::_AddToLockedVariable(ConditionVariable* variable)
{
ASSERT(fVariable == NULL);
- B_INITIALIZE_SPINLOCK(&fLock);
fThread = thread_get_current_thread();
fVariable = variable;
fWaitStatus = STATUS_ADDED;
fVariable->fEntries.Add(this);
+ atomic_add(&fVariable->fEntriesCount, 1);
}
void
ConditionVariableEntry::_RemoveFromVariable()
{
+ // This section is critical because it can race with _NotifyLocked on the
+ // variable's thread, so we must not be interrupted during it.
InterruptsLocker _;
- SpinLocker entryLocker(fLock);
- if (fVariable != NULL) {
- SpinLocker conditionLocker(fVariable->fLock);
- if (fVariable->fEntries.Contains(this)) {
- fVariable->fEntries.Remove(this);
- } else {
- entryLocker.Unlock();
- // The variable's fEntries did not contain us, but we currently
- // have the variable's lock acquired. This must mean we are in
- // a race with the variable's Notify. It is possible we will be
- // destroyed immediately upon returning here, so we need to
- // spin until our fVariable member is unset by the Notify thread
- // and then re-acquire our own lock to avoid a use-after-free.
- while (atomic_pointer_get(&fVariable) != NULL) {}
- entryLocker.Lock();
+ ConditionVariable* variable = atomic_pointer_get(&fVariable);
+ if (atomic_pointer_get_and_set(&fThread, (Thread*)NULL) == NULL) {
+ // If fThread was already NULL, that means the variable is already
+ // in the process of clearing us out (or already has finished doing so.)
+ // We thus cannot access fVariable, and must spin until it is cleared.
+ int32 tries = 0;
+ while (atomic_pointer_get(&fVariable) != NULL) {
+ tries++;
+ if ((tries % 10000) == 0)
+ panic("variable pointer was not unset for a long time!");
+ }
+
+ return;
+ }
+
+ while (true) {
+ if (atomic_pointer_get(&fVariable) == NULL) {
+ // The variable must have cleared us out. Acknowledge this and return.
+ atomic_add(&variable->fEntriesCount, -1);
+ return;
}
- fVariable = NULL;
+
+ // There is of course a small race between checking the pointer and then
+ // the try_acquire in which the variable might clear out our fVariable.
+ // However, in the case where we were the ones to clear fThread, the
+ // variable will notice that and then wait for us to acknowledge the
+ // removal by decrementing fEntriesCount, as we do above; and until
+ // we do that, we may validly use our cached pointer to the variable.
+ if (try_acquire_spinlock(&variable->fLock))
+ break;
}
+
+ // We now hold the variable's lock. Remove ourselves.
+ if (fVariable->fEntries.Contains(this))
+ fVariable->fEntries.Remove(this);
+
+ atomic_pointer_set(&fVariable, (ConditionVariable*)NULL);
+ atomic_add(&variable->fEntriesCount, -1);
+ release_spinlock(&variable->fLock);
}
@@ -177,18 +202,25 @@ ConditionVariableEntry::Wait(uint32 flags, bigtime_t timeout)
}
#endif
- InterruptsLocker _;
- SpinLocker entryLocker(fLock);
-
- if (fVariable == NULL)
- return fWaitStatus;
+ // The race in-between get_and_set and (re)set is irrelevant, because
+ // if the status really is <= 0, we have already been or are about to
+ // be removed from the variable, and nothing else is going to set the status.
+ status_t waitStatus = atomic_get_and_set(&fWaitStatus, STATUS_WAITING);
+ if (waitStatus <= 0) {
+ fWaitStatus = waitStatus;
+ return waitStatus;
+ }
- thread_prepare_to_block(fThread, flags,
- THREAD_BLOCK_TYPE_CONDITION_VARIABLE, fVariable);
+ InterruptsLocker _;
- fWaitStatus = STATUS_WAITING;
+ thread_prepare_to_block(thread_get_current_thread(), flags,
+ THREAD_BLOCK_TYPE_CONDITION_VARIABLE, atomic_pointer_get(&fVariable));
- entryLocker.Unlock();
+ waitStatus = atomic_get(&fWaitStatus);
+ if (waitStatus <= 0) {
+ // We were just woken up! Unblock ourselves immediately.
+ thread_unblock(thread_get_current_thread(), waitStatus);
+ }
status_t error;
if ((flags & (B_RELATIVE_TIMEOUT | B_ABSOLUTE_TIMEOUT)) != 0)
@@ -222,6 +254,7 @@ ConditionVariable::Init(const void* object, const char* objectType)
fObject = object;
fObjectType = objectType;
new(&fEntries) EntryList;
+ fEntriesCount = 0;
B_INITIALIZE_SPINLOCK(&fLock);
T_SCHEDULING_ANALYSIS(InitConditionVariable(this, object, objectType));
@@ -238,6 +271,7 @@ ConditionVariable::Publish(const void* object, const char* objectType)
fObject = object;
fObjectType = objectType;
new(&fEntries) EntryList;
+ fEntriesCount = 0;
B_INITIALIZE_SPINLOCK(&fLock);
T_SCHEDULING_ANALYSIS(InitConditionVariable(this, object, objectType));
@@ -346,31 +380,38 @@ void
ConditionVariable::_NotifyLocked(bool all, status_t result)
{
// Dequeue and wake up the blocked threads.
- // We *cannot* hold our own lock while acquiring the Entry's lock,
- // as this leads to a (non-theoretical!) race between the Entry
- // entering Wait() and acquiring its own lock, and then acquiring ours.
while (ConditionVariableEntry* entry = fEntries.RemoveHead()) {
- release_spinlock(&fLock);
- acquire_spinlock(&entry->fLock);
-
- entry->fVariable = NULL;
-
- if (entry->fWaitStatus <= 0) {
- release_spinlock(&entry->fLock);
- acquire_spinlock(&fLock);
- continue;
- }
-
- if (entry->fWaitStatus == STATUS_WAITING) {
- SpinLocker _(entry->fThread->scheduler_lock);
- thread_unblock_locked(entry->fThread, result);
+ Thread* thread = atomic_pointer_get_and_set(&entry->fThread, (Thread*)NULL);
+ if (thread == NULL) {
+ // The entry must be in the process of trying to remove itself from us.
+ // Clear its variable and wait for it to acknowledge this in fEntriesCount,
+ // as it is the one responsible for decrementing that.
+ const int32 oldCount = atomic_get(&fEntriesCount);
+ atomic_pointer_set(&entry->fVariable, (ConditionVariable*)NULL);
+
+ // As fEntriesCount is only modified while our lock is held, nothing else
+ // will modify it while we are spinning, since we hold it at present.
+ int32 tries = 0;
+ while (atomic_get(&fEntriesCount) == oldCount) {
+ tries++;
+ if ((tries % 10000) == 0)
+ panic("entries count was not decremented for a long time!");
+ }
+ } else {
+ const status_t waitStatus = atomic_get_and_set(&entry->fWaitStatus, result);
+
+ // No matter what the thread is doing, as we were the ones to clear its
+ // fThread, so we are the ones responsible for decrementing fEntriesCount.
+ // (We may not validly access the entry once we unset its fVariable.)
+ atomic_pointer_set(&entry->fVariable, (ConditionVariable*)NULL);
+ atomic_add(&fEntriesCount, -1);
+
+ // Do this after unsetting fVariable, as in case the entry wakes up
+ // and tries to remove itself, it need not not have to wait for us.
+ if (waitStatus == STATUS_WAITING)
+ thread_unblock(thread, result);
}
- entry->fWaitStatus = result;
-
- release_spinlock(&entry->fLock);
- acquire_spinlock(&fLock);
-
if (!all)
break;
}
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic