| // Copyright 2017 The Fuchsia Authors |
| // |
| // Use of this source code is governed by a MIT-style |
| // license that can be found in the LICENSE file or at |
| // https://opensource.org/licenses/MIT |
| #include "kernel/semaphore.h" |
| |
| #include <lib/fit/defer.h> |
| #include <lib/kconcurrent/chainlock.h> |
| #include <lib/kconcurrent/chainlock_transaction.h> |
| #include <zircon/compiler.h> |
| #include <zircon/errors.h> |
| #include <zircon/types.h> |
| |
| #include <kernel/auto_preempt_disabler.h> |
| |
| // Every call to this method must wake one waiter unless the queue is empty. |
| // |
| // When leaving this method, we must have either |
| // - incremented a non-negative count or |
| // - unblocked one thread and |
| // - left an empty queue with a count of zero or |
| // - left a non-empty queue with negative count |
| void Semaphore::Post() { |
| // When calling post, we know we cannot be holding any chain locks (since we |
| // demand that there be no transaction in process). In addition, if they are |
| // holding any spinlocks, they need to have disabled local preemption outside |
| // of the outer-most scope of the spin-lock(s) they hold. Otherwise, posting |
| // to the semaphore might result in a local preemption while a spin-lock is |
| // held, something which cannot be permitted. |
| DEBUG_ASSERT_MSG(!Thread::Current::preemption_state().PreemptIsEnabled() || |
| (READ_PERCPU_FIELD(num_spinlocks) == 0), |
| "Preemption %d Num Spinlocks %u\n", |
| Thread::Current::preemption_state().PreemptIsEnabled(), |
| READ_PERCPU_FIELD(num_spinlocks)); |
| |
| for (bool finished = false; !finished;) { |
| // Is the count greater than or equal to zero? If so, increment and return. |
| // Take care to not increment a negative count. |
| int64_t old_count = count_.load(ktl::memory_order_relaxed); |
| while (old_count >= 0) { |
| if (count_.compare_exchange_weak(old_count, old_count + 1, ktl::memory_order_release, |
| ktl::memory_order_relaxed)) { |
| return; |
| } |
| } |
| |
| // The fast-path has failed, looks like we are going to need to obtain some |
| // locks in order to proceed. Create the CLT we will need to do so now. |
| ChainLockTransactionPreemptDisableAndIrqSave clt{CLT_TAG("Semaphore::Wait")}; |
| auto finalize_clt = fit::defer([&clt]() TA_NO_THREAD_SAFETY_ANALYSIS { clt.Finalize(); }); |
| for (;; clt.Relax()) { |
| // We observed a negative count and have not yet incremented it. There might |
| // be waiters waiting. We'll need to acquire the lock and check. |
| UnconditionalChainLockGuard guard{waitq_.get_lock()}; |
| |
| // Because we hold the lock we know that no other thread can transition the |
| // count from non-negative to negative or vice versa. If the count is |
| // non-negative, then there must be no waiters so just increment and return. |
| old_count = count_.load(ktl::memory_order_relaxed); |
| if (old_count >= 0) { |
| [[maybe_unused]] uint32_t q; |
| DEBUG_ASSERT_MSG((q = waitq_.Count()) == 0, "q=%u old_count=%ld\n", q, old_count); |
| count_.fetch_add(1, ktl::memory_order_release); |
| return; |
| } |
| |
| // Because we hold the lock we know the number of waiters cannot change out |
| // from under us. At this point we know the count is negative, and it cannot become |
| // non-negative without holding our queue's lock. Check for waiters to wake. |
| const uint32_t num_in_queue = waitq_.Count(); |
| if (num_in_queue == 0) { |
| // There are no waiters to wake. They must have timed out or been |
| // interrupted. Reset the count and perform our increment. |
| count_.store(1, ktl::memory_order_release); |
| return; |
| } |
| |
| // At this point we know there's at least one waiter waiting. We're committed |
| // to waking. However, we need to determine what the count should be when |
| // drop the lock and return. After we wake, if there are no waiters left, the |
| // count should be reset to zero, otherwise it should remain negative. |
| // |
| // Try to wake one of the threads in the queue, but be ready for it to fail |
| // because of a backoff error. |
| ktl::optional<bool> wake_result = waitq_.WakeOneLocked(ZX_OK); |
| if (!wake_result.has_value()) { |
| continue; // Drop all of the locks and start again. |
| } |
| DEBUG_ASSERT(wake_result.value()); |
| |
| // Cancel our deferred finalize action. WakeOneLocked has "finalize upon |
| // success" semantics. Basically, if it succeeds in obtaining all of the |
| // required locks, it will finalize the existing transaction-in-process |
| // using the CLT's static method. If it fails, it will keep the |
| // transaction un-finalized so we continue to consider the time spent |
| // acquiring locks so far as part of the total transaction |
| // lock-acquisition time. |
| // |
| // TODO(johngro): Another option here would be to skip the fit::defer and |
| // just use a manual clt.Finalize() before each of the successful |
| // early-return paths above. I'm not certain which one is the proper |
| // balance of safe, easy to maintain, and easy to understand, right now. |
| finalize_clt.cancel(); |
| |
| // If we just woke the last thread from the queue, set the negative count |
| // back to zero. We know that this is safe because we are still holding the |
| // queue's lock. Signaling threads cannot increment the count because it is |
| // currently negative, and they cannot transition from negative to |
| // non-negative without holding the queue's lock. Likewise, Waiting threads |
| // cannot decrement the count (again, because it is negative) without first |
| // obtaining the queue's lock. This holds true even if the thread we just |
| // woke starts running on another CPU and attempts to alter the count |
| // with either a post or a wait operation. |
| if (num_in_queue == 1) { |
| count_.store(0, ktl::memory_order_release); |
| } |
| return; |
| } |
| } |
| } |
| |
| // Handling failed waits -- Waits can fail due to timeout or thread signal. |
| // When a Wait fails, the caller cannot proceed to the resource guarded by the |
| // semaphore. It's as if the waiter gave up and left. We want to ensure failed |
| // waits do not impact other waiters. While it seems like a failed wait should |
| // simply "undo" its decrement, it is not safe to do so in Wait. Instead, we |
| // "fix" the count in subsequent call to Post. |
| // |
| // To understand why we can't simply fix the count in Wait after returning from |
| // Block, let's look at an alternative (buggy) implementation of Post and Wait. |
| // In this hypothetical implementation, Post increments and Wait decrements |
| // before Block, but also increments if Block returns an error. With this |
| // hypothetical implementation in mind, consider the following sequence of |
| // operations: |
| // |
| // Q C |
| // 0 0 |
| // 1W 1 -1 B |
| // 1T 0 -1 |
| // 2P 0 0 |
| // 3W 1 -1 B |
| // 1R 1 0 |
| // |
| // The way to read the sequence above is that the wait queue (Q) starts empty |
| // and the count (C) starts at zero. Thread1 calls Wait (1W) and blocks (B). |
| // Thread1's times out (1T) and is removed from the queue, but has not yet |
| // resumed execution. Thread2 calls Post (2P), but does not unblock any threads |
| // because it finds an empty queue. Thread3 calls Wait (3W) and blocks (B). |
| // Thread1 returns from Block, resumes execution (1R), and increments the count. |
| // At this point Thread3 is blocked as it should be (two Posts and one failed |
| // Wait), however, a subsequent call to Post will not unblock it. We have a |
| // "lost wakeup". |
| zx_status_t Semaphore::Wait(const Deadline& deadline) { |
| // Is the count greater than zero? If so, decrement and return. Take care to |
| // not decrement zero or a negative value. |
| int64_t old_count = count_.load(ktl::memory_order_relaxed); |
| while (old_count > 0) { |
| if (count_.compare_exchange_weak(old_count, old_count - 1, ktl::memory_order_acquire, |
| ktl::memory_order_relaxed)) { |
| return ZX_OK; |
| } |
| } |
| |
| // We either observed that count is zero or negative. We have not |
| // decremented yet. We may or may not need to block, but we need to hold |
| // our queue's lock before proceeding. |
| ChainLockTransactionIrqSave clt{CLT_TAG("Semaphore::Wait")}; |
| auto finalize_clt = fit::defer([&clt]() TA_NO_THREAD_SAFETY_ANALYSIS { clt.Finalize(); }); |
| waitq_.get_lock().AcquireUnconditionally(); |
| |
| // Because we hold the lock we know that no other thread can transition the |
| // count from non-negative to negative or vice versa. If we can decrement a |
| // positive count, then we're done and don't need to block. |
| old_count = count_.fetch_sub(1, ktl::memory_order_acquire); |
| if (old_count > 0) { |
| waitq_.get_lock().Release(); |
| return ZX_OK; |
| } |
| |
| // We either decremented zero or a negative value. We must block. Grab our |
| // thread's lock and do so. |
| // |
| // TODO(johngro): Is it safe to simply grab the thread's lock |
| // unconditionally here? I cannot (currently) think of a way that we might |
| // need to encounter a scenario where we might need to legitimately back off |
| // (even if we encounter a Backoff error), but if one _could_ exist, we |
| // should be prepared to do so. |
| // |
| // Currently, this is the best argument I have for why this is safe. |
| // 1) Our queue is a normal WaitQueue, not an OwnedWaitQueue. Because of |
| // this, it must always be the target node of any PI graph it is involved |
| // in. |
| // 2) The current thread is running (by definition), therefore it must also be |
| // the target node of any PI graph it is involved in. |
| // 3) No one else can be involved in any operation which would add an edge |
| // from the current thread to another wait queue (only threads can block |
| // themselves in wait queues). |
| // |
| // We already have our queue's lock. If there is another operation in flight |
| // which currently held the thread's lock, it would also need to involve |
| // holding our queue's lock in order to produce a scenario where the backoff |
| // protocol was needed. By the above arguments, the only such operation would |
| // be blocking the current thread in this queue, which cannot happen because |
| // of #3 (we are the current thread). |
| // |
| // Will this reasoning always hold, however? For example, what if (some day) |
| // there was an operation which wanted to globally hold all thread locks at |
| // the same time as all wait queue locks? While this does not seem likely, |
| // I'm not sure how to effectively stop someone from accidentally making a |
| // mistake like this. |
| // |
| Thread* const current_thread = Thread::Current::Get(); |
| UnconditionalChainLockGuard guard{current_thread->get_lock()}; |
| finalize_clt.call(); |
| return waitq_.Block(current_thread, deadline, Interruptible::Yes); |
| } |