michael@0: // Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
michael@0: // Use of this source code is governed by a BSD-style license that can be
michael@0: // found in the LICENSE file.
michael@0: 
michael@0: #include "base/waitable_event.h"
michael@0: 
michael@0: #include "base/condition_variable.h"
michael@0: #include "base/lock.h"
michael@0: #include "base/message_loop.h"
michael@0: 
michael@0: // -----------------------------------------------------------------------------
michael@0: // A WaitableEvent on POSIX is implemented as a wait-list. Currently we don't
michael@0: // support cross-process events (where one process can signal an event which
michael@0: // others are waiting on). Because of this, we can avoid having one thread per
michael@0: // listener in several cases.
michael@0: //
michael@0: // The WaitableEvent maintains a list of waiters, protected by a lock. Each
michael@0: // waiter is either an async wait, in which case we have a Task and the
michael@0: // MessageLoop to run it on, or a blocking wait, in which case we have the
michael@0: // condition variable to signal.
michael@0: //
michael@0: // Waiting involves grabbing the lock and adding oneself to the wait list. Async
michael@0: // waits can be canceled, which means grabbing the lock and removing oneself
michael@0: // from the list.
michael@0: //
michael@0: // Waiting on multiple events is handled by adding a single, synchronous wait to
michael@0: // the wait-list of many events. An event passes a pointer to itself when
michael@0: // firing a waiter and so we can store that pointer to find out which event
michael@0: // triggered.
michael@0: // -----------------------------------------------------------------------------
michael@0: 
michael@0: namespace base {
michael@0: 
michael@0: // -----------------------------------------------------------------------------
michael@0: // This is just an abstract base class for waking the two types of waiters
michael@0: // -----------------------------------------------------------------------------
michael@0: WaitableEvent::WaitableEvent(bool manual_reset, bool initially_signaled)
michael@0:     : kernel_(new WaitableEventKernel(manual_reset, initially_signaled)) {
michael@0: }
michael@0: 
michael@0: WaitableEvent::~WaitableEvent() {
michael@0: }
michael@0: 
michael@0: void WaitableEvent::Reset() {
michael@0:   AutoLock locked(kernel_->lock_);
michael@0:   kernel_->signaled_ = false;
michael@0: }
michael@0: 
michael@0: void WaitableEvent::Signal() {
michael@0:   AutoLock locked(kernel_->lock_);
michael@0: 
michael@0:   if (kernel_->signaled_)
michael@0:     return;
michael@0: 
michael@0:   if (kernel_->manual_reset_) {
michael@0:     SignalAll();
michael@0:     kernel_->signaled_ = true;
michael@0:   } else {
michael@0:     // In the case of auto reset, if no waiters were woken, we remain
michael@0:     // signaled.
michael@0:     if (!SignalOne())
michael@0:       kernel_->signaled_ = true;
michael@0:   }
michael@0: }
michael@0: 
michael@0: bool WaitableEvent::IsSignaled() {
michael@0:   AutoLock locked(kernel_->lock_);
michael@0: 
michael@0:   const bool result = kernel_->signaled_;
michael@0:   if (result && !kernel_->manual_reset_)
michael@0:     kernel_->signaled_ = false;
michael@0:   return result;
michael@0: }
michael@0: 
michael@0: // -----------------------------------------------------------------------------
michael@0: // Synchronous waits
michael@0: 
michael@0: // -----------------------------------------------------------------------------
michael@0: // This is an synchronous waiter. The thread is waiting on the given condition
michael@0: // variable and the fired flag in this object.
michael@0: // -----------------------------------------------------------------------------
michael@0: class SyncWaiter : public WaitableEvent::Waiter {
michael@0:  public:
michael@0:   SyncWaiter(ConditionVariable* cv, Lock* lock)
michael@0:       : fired_(false),
michael@0:         cv_(cv),
michael@0:         lock_(lock),
michael@0:         signaling_event_(NULL) {
michael@0:   }
michael@0: 
michael@0:   bool Fire(WaitableEvent *signaling_event) {
michael@0:     lock_->Acquire();
michael@0:       const bool previous_value = fired_;
michael@0:       fired_ = true;
michael@0:       if (!previous_value)
michael@0:         signaling_event_ = signaling_event;
michael@0:     lock_->Release();
michael@0: 
michael@0:     if (previous_value)
michael@0:       return false;
michael@0: 
michael@0:     cv_->Broadcast();
michael@0: 
michael@0:     // SyncWaiters are stack allocated on the stack of the blocking thread.
michael@0:     return true;
michael@0:   }
michael@0: 
michael@0:   WaitableEvent* signaled_event() const {
michael@0:     return signaling_event_;
michael@0:   }
michael@0: 
michael@0:   // ---------------------------------------------------------------------------
michael@0:   // These waiters are always stack allocated and don't delete themselves. Thus
michael@0:   // there's no problem and the ABA tag is the same as the object pointer.
michael@0:   // ---------------------------------------------------------------------------
michael@0:   bool Compare(void* tag) {
michael@0:     return this == tag;
michael@0:   }
michael@0: 
michael@0:   // ---------------------------------------------------------------------------
michael@0:   // Called with lock held.
michael@0:   // ---------------------------------------------------------------------------
michael@0:   bool fired() const {
michael@0:     return fired_;
michael@0:   }
michael@0: 
michael@0:   // ---------------------------------------------------------------------------
michael@0:   // During a TimedWait, we need a way to make sure that an auto-reset
michael@0:   // WaitableEvent doesn't think that this event has been signaled between
michael@0:   // unlocking it and removing it from the wait-list. Called with lock held.
michael@0:   // ---------------------------------------------------------------------------
michael@0:   void Disable() {
michael@0:     fired_ = true;
michael@0:   }
michael@0: 
michael@0:  private:
michael@0:   bool fired_;
michael@0:   ConditionVariable *const cv_;
michael@0:   Lock *const lock_;
michael@0:   WaitableEvent* signaling_event_;  // The WaitableEvent which woke us
michael@0: };
michael@0: 
michael@0: bool WaitableEvent::TimedWait(const TimeDelta& max_time) {
michael@0:   const TimeTicks end_time(TimeTicks::Now() + max_time);
michael@0:   const bool finite_time = max_time.ToInternalValue() >= 0;
michael@0: 
michael@0:   kernel_->lock_.Acquire();
michael@0:     if (kernel_->signaled_) {
michael@0:       if (!kernel_->manual_reset_) {
michael@0:         // In this case we were signaled when we had no waiters. Now that
michael@0:         // someone has waited upon us, we can automatically reset.
michael@0:         kernel_->signaled_ = false;
michael@0:       }
michael@0: 
michael@0:       kernel_->lock_.Release();
michael@0:       return true;
michael@0:     }
michael@0: 
michael@0:     Lock lock;
michael@0:     lock.Acquire();
michael@0:     ConditionVariable cv(&lock);
michael@0:     SyncWaiter sw(&cv, &lock);
michael@0: 
michael@0:     Enqueue(&sw);
michael@0:   kernel_->lock_.Release();
michael@0:   // We are violating locking order here by holding the SyncWaiter lock but not
michael@0:   // the WaitableEvent lock. However, this is safe because we don't lock @lock_
michael@0:   // again before unlocking it.
michael@0: 
michael@0:   for (;;) {
michael@0:     const TimeTicks current_time(TimeTicks::Now());
michael@0: 
michael@0:     if (sw.fired() || (finite_time && current_time >= end_time)) {
michael@0:       const bool return_value = sw.fired();
michael@0: 
michael@0:       // We can't acquire @lock_ before releasing @lock (because of locking
michael@0:       // order), however, inbetween the two a signal could be fired and @sw
michael@0:       // would accept it, however we will still return false, so the signal
michael@0:       // would be lost on an auto-reset WaitableEvent. Thus we call Disable
michael@0:       // which makes sw::Fire return false.
michael@0:       sw.Disable();
michael@0:       lock.Release();
michael@0: 
michael@0:       kernel_->lock_.Acquire();
michael@0:         kernel_->Dequeue(&sw, &sw);
michael@0:       kernel_->lock_.Release();
michael@0: 
michael@0:       return return_value;
michael@0:     }
michael@0: 
michael@0:     if (finite_time) {
michael@0:       const TimeDelta max_wait(end_time - current_time);
michael@0:       cv.TimedWait(max_wait);
michael@0:     } else {
michael@0:       cv.Wait();
michael@0:     }
michael@0:   }
michael@0: }
michael@0: 
michael@0: bool WaitableEvent::Wait() {
michael@0:   return TimedWait(TimeDelta::FromSeconds(-1));
michael@0: }
michael@0: 
michael@0: // -----------------------------------------------------------------------------
michael@0: 
michael@0: 
michael@0: // -----------------------------------------------------------------------------
michael@0: // Synchronous waiting on multiple objects.
michael@0: 
michael@0: static bool  // StrictWeakOrdering
michael@0: cmp_fst_addr(const std::pair<WaitableEvent*, unsigned> &a,
michael@0:              const std::pair<WaitableEvent*, unsigned> &b) {
michael@0:   return a.first < b.first;
michael@0: }
michael@0: 
michael@0: // static
michael@0: size_t WaitableEvent::WaitMany(WaitableEvent** raw_waitables,
michael@0:                                size_t count) {
michael@0:   DCHECK(count) << "Cannot wait on no events";
michael@0: 
michael@0:   // We need to acquire the locks in a globally consistent order. Thus we sort
michael@0:   // the array of waitables by address. We actually sort a pairs so that we can
michael@0:   // map back to the original index values later.
michael@0:   std::vector<std::pair<WaitableEvent*, size_t> > waitables;
michael@0:   waitables.reserve(count);
michael@0:   for (size_t i = 0; i < count; ++i)
michael@0:     waitables.push_back(std::make_pair(raw_waitables[i], i));
michael@0: 
michael@0:   DCHECK_EQ(count, waitables.size());
michael@0: 
michael@0:   sort(waitables.begin(), waitables.end(), cmp_fst_addr);
michael@0: 
michael@0:   // The set of waitables must be distinct. Since we have just sorted by
michael@0:   // address, we can check this cheaply by comparing pairs of consecutive
michael@0:   // elements.
michael@0:   for (size_t i = 0; i < waitables.size() - 1; ++i) {
michael@0:     DCHECK(waitables[i].first != waitables[i+1].first);
michael@0:   }
michael@0: 
michael@0:   Lock lock;
michael@0:   ConditionVariable cv(&lock);
michael@0:   SyncWaiter sw(&cv, &lock);
michael@0: 
michael@0:   const size_t r = EnqueueMany(&waitables[0], count, &sw);
michael@0:   if (r) {
michael@0:     // One of the events is already signaled. The SyncWaiter has not been
michael@0:     // enqueued anywhere. EnqueueMany returns the count of remaining waitables
michael@0:     // when the signaled one was seen, so the index of the signaled event is
michael@0:     // @count - @r.
michael@0:     return waitables[count - r].second;
michael@0:   }
michael@0: 
michael@0:   // At this point, we hold the locks on all the WaitableEvents and we have
michael@0:   // enqueued our waiter in them all.
michael@0:   lock.Acquire();
michael@0:     // Release the WaitableEvent locks in the reverse order
michael@0:     for (size_t i = 0; i < count; ++i) {
michael@0:       waitables[count - (1 + i)].first->kernel_->lock_.Release();
michael@0:     }
michael@0: 
michael@0:     for (;;) {
michael@0:       if (sw.fired())
michael@0:         break;
michael@0: 
michael@0:       cv.Wait();
michael@0:     }
michael@0:   lock.Release();
michael@0: 
michael@0:   // The address of the WaitableEvent which fired is stored in the SyncWaiter.
michael@0:   WaitableEvent *const signaled_event = sw.signaled_event();
michael@0:   // This will store the index of the raw_waitables which fired.
michael@0:   size_t signaled_index = 0;
michael@0: 
michael@0:   // Take the locks of each WaitableEvent in turn (except the signaled one) and
michael@0:   // remove our SyncWaiter from the wait-list
michael@0:   for (size_t i = 0; i < count; ++i) {
michael@0:     if (raw_waitables[i] != signaled_event) {
michael@0:       raw_waitables[i]->kernel_->lock_.Acquire();
michael@0:         // There's no possible ABA issue with the address of the SyncWaiter here
michael@0:         // because it lives on the stack. Thus the tag value is just the pointer
michael@0:         // value again.
michael@0:         raw_waitables[i]->kernel_->Dequeue(&sw, &sw);
michael@0:       raw_waitables[i]->kernel_->lock_.Release();
michael@0:     } else {
michael@0:       signaled_index = i;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   return signaled_index;
michael@0: }
michael@0: 
michael@0: // -----------------------------------------------------------------------------
michael@0: // If return value == 0:
michael@0: //   The locks of the WaitableEvents have been taken in order and the Waiter has
michael@0: //   been enqueued in the wait-list of each. None of the WaitableEvents are
michael@0: //   currently signaled
michael@0: // else:
michael@0: //   None of the WaitableEvent locks are held. The Waiter has not been enqueued
michael@0: //   in any of them and the return value is the index of the first WaitableEvent
michael@0: //   which was signaled, from the end of the array.
michael@0: // -----------------------------------------------------------------------------
michael@0: // static
michael@0: size_t WaitableEvent::EnqueueMany
michael@0:     (std::pair<WaitableEvent*, size_t>* waitables,
michael@0:      size_t count, Waiter* waiter) {
michael@0:   if (!count)
michael@0:     return 0;
michael@0: 
michael@0:   waitables[0].first->kernel_->lock_.Acquire();
michael@0:     if (waitables[0].first->kernel_->signaled_) {
michael@0:       if (!waitables[0].first->kernel_->manual_reset_)
michael@0:         waitables[0].first->kernel_->signaled_ = false;
michael@0:       waitables[0].first->kernel_->lock_.Release();
michael@0:       return count;
michael@0:     }
michael@0: 
michael@0:     const size_t r = EnqueueMany(waitables + 1, count - 1, waiter);
michael@0:     if (r) {
michael@0:       waitables[0].first->kernel_->lock_.Release();
michael@0:     } else {
michael@0:       waitables[0].first->Enqueue(waiter);
michael@0:     }
michael@0: 
michael@0:     return r;
michael@0: }
michael@0: 
michael@0: // -----------------------------------------------------------------------------
michael@0: 
michael@0: 
michael@0: // -----------------------------------------------------------------------------
michael@0: // Private functions...
michael@0: 
michael@0: // -----------------------------------------------------------------------------
michael@0: // Wake all waiting waiters. Called with lock held.
michael@0: // -----------------------------------------------------------------------------
michael@0: bool WaitableEvent::SignalAll() {
michael@0:   bool signaled_at_least_one = false;
michael@0: 
michael@0:   for (std::list<Waiter*>::iterator
michael@0:        i = kernel_->waiters_.begin(); i != kernel_->waiters_.end(); ++i) {
michael@0:     if ((*i)->Fire(this))
michael@0:       signaled_at_least_one = true;
michael@0:   }
michael@0: 
michael@0:   kernel_->waiters_.clear();
michael@0:   return signaled_at_least_one;
michael@0: }
michael@0: 
michael@0: // ---------------------------------------------------------------------------
michael@0: // Try to wake a single waiter. Return true if one was woken. Called with lock
michael@0: // held.
michael@0: // ---------------------------------------------------------------------------
michael@0: bool WaitableEvent::SignalOne() {
michael@0:   for (;;) {
michael@0:     if (kernel_->waiters_.empty())
michael@0:       return false;
michael@0: 
michael@0:     const bool r = (*kernel_->waiters_.begin())->Fire(this);
michael@0:     kernel_->waiters_.pop_front();
michael@0:     if (r)
michael@0:       return true;
michael@0:   }
michael@0: }
michael@0: 
michael@0: // -----------------------------------------------------------------------------
michael@0: // Add a waiter to the list of those waiting. Called with lock held.
michael@0: // -----------------------------------------------------------------------------
michael@0: void WaitableEvent::Enqueue(Waiter* waiter) {
michael@0:   kernel_->waiters_.push_back(waiter);
michael@0: }
michael@0: 
michael@0: // -----------------------------------------------------------------------------
michael@0: // Remove a waiter from the list of those waiting. Return true if the waiter was
michael@0: // actually removed. Called with lock held.
michael@0: // -----------------------------------------------------------------------------
michael@0: bool WaitableEvent::WaitableEventKernel::Dequeue(Waiter* waiter, void* tag) {
michael@0:   for (std::list<Waiter*>::iterator
michael@0:        i = waiters_.begin(); i != waiters_.end(); ++i) {
michael@0:     if (*i == waiter && (*i)->Compare(tag)) {
michael@0:       waiters_.erase(i);
michael@0:       return true;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   return false;
michael@0: }
michael@0: 
michael@0: // -----------------------------------------------------------------------------
michael@0: 
michael@0: }  // namespace base