Home | History | Annotate | Download | only in synchronization
      1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include <algorithm>
      6 #include <vector>
      7 
      8 #include "base/logging.h"
      9 #include "base/synchronization/waitable_event.h"
     10 #include "base/synchronization/condition_variable.h"
     11 #include "base/synchronization/lock.h"
     12 #include "base/threading/thread_restrictions.h"
     13 
     14 // -----------------------------------------------------------------------------
     15 // A WaitableEvent on POSIX is implemented as a wait-list. Currently we don't
     16 // support cross-process events (where one process can signal an event which
     17 // others are waiting on). Because of this, we can avoid having one thread per
     18 // listener in several cases.
     19 //
     20 // The WaitableEvent maintains a list of waiters, protected by a lock. Each
     21 // waiter is either an async wait, in which case we have a Task and the
     22 // MessageLoop to run it on, or a blocking wait, in which case we have the
     23 // condition variable to signal.
     24 //
     25 // Waiting involves grabbing the lock and adding oneself to the wait list. Async
     26 // waits can be canceled, which means grabbing the lock and removing oneself
     27 // from the list.
     28 //
     29 // Waiting on multiple events is handled by adding a single, synchronous wait to
     30 // the wait-list of many events. An event passes a pointer to itself when
     31 // firing a waiter and so we can store that pointer to find out which event
     32 // triggered.
     33 // -----------------------------------------------------------------------------
     34 
     35 namespace base {
     36 
     37 // -----------------------------------------------------------------------------
     38 // This is just an abstract base class for waking the two types of waiters
     39 // -----------------------------------------------------------------------------
     40 WaitableEvent::WaitableEvent(bool manual_reset, bool initially_signaled)
     41     : kernel_(new WaitableEventKernel(manual_reset, initially_signaled)) {
     42 }
     43 
     44 WaitableEvent::~WaitableEvent() {
     45 }
     46 
     47 void WaitableEvent::Reset() {
     48   base::AutoLock locked(kernel_->lock_);
     49   kernel_->signaled_ = false;
     50 }
     51 
     52 void WaitableEvent::Signal() {
     53   base::AutoLock locked(kernel_->lock_);
     54 
     55   if (kernel_->signaled_)
     56     return;
     57 
     58   if (kernel_->manual_reset_) {
     59     SignalAll();
     60     kernel_->signaled_ = true;
     61   } else {
     62     // In the case of auto reset, if no waiters were woken, we remain
     63     // signaled.
     64     if (!SignalOne())
     65       kernel_->signaled_ = true;
     66   }
     67 }
     68 
     69 bool WaitableEvent::IsSignaled() {
     70   base::AutoLock locked(kernel_->lock_);
     71 
     72   const bool result = kernel_->signaled_;
     73   if (result && !kernel_->manual_reset_)
     74     kernel_->signaled_ = false;
     75   return result;
     76 }
     77 
     78 // -----------------------------------------------------------------------------
     79 // Synchronous waits
     80 
     81 // -----------------------------------------------------------------------------
     82 // This is a synchronous waiter. The thread is waiting on the given condition
     83 // variable and the fired flag in this object.
     84 // -----------------------------------------------------------------------------
     85 class SyncWaiter : public WaitableEvent::Waiter {
     86  public:
     87   SyncWaiter()
     88       : fired_(false),
     89         signaling_event_(NULL),
     90         lock_(),
     91         cv_(&lock_) {
     92   }
     93 
     94   virtual bool Fire(WaitableEvent* signaling_event) OVERRIDE {
     95     base::AutoLock locked(lock_);
     96 
     97     if (fired_)
     98       return false;
     99 
    100     fired_ = true;
    101     signaling_event_ = signaling_event;
    102 
    103     cv_.Broadcast();
    104 
    105     // Unlike AsyncWaiter objects, SyncWaiter objects are stack-allocated on
    106     // the blocking thread's stack.  There is no |delete this;| in Fire.  The
    107     // SyncWaiter object is destroyed when it goes out of scope.
    108 
    109     return true;
    110   }
    111 
    112   WaitableEvent* signaling_event() const {
    113     return signaling_event_;
    114   }
    115 
    116   // ---------------------------------------------------------------------------
    117   // These waiters are always stack allocated and don't delete themselves. Thus
    118   // there's no problem and the ABA tag is the same as the object pointer.
    119   // ---------------------------------------------------------------------------
    120   virtual bool Compare(void* tag) OVERRIDE {
    121     return this == tag;
    122   }
    123 
    124   // ---------------------------------------------------------------------------
    125   // Called with lock held.
    126   // ---------------------------------------------------------------------------
    127   bool fired() const {
    128     return fired_;
    129   }
    130 
    131   // ---------------------------------------------------------------------------
    132   // During a TimedWait, we need a way to make sure that an auto-reset
    133   // WaitableEvent doesn't think that this event has been signaled between
    134   // unlocking it and removing it from the wait-list. Called with lock held.
    135   // ---------------------------------------------------------------------------
    136   void Disable() {
    137     fired_ = true;
    138   }
    139 
    140   base::Lock* lock() {
    141     return &lock_;
    142   }
    143 
    144   base::ConditionVariable* cv() {
    145     return &cv_;
    146   }
    147 
    148  private:
    149   bool fired_;
    150   WaitableEvent* signaling_event_;  // The WaitableEvent which woke us
    151   base::Lock lock_;
    152   base::ConditionVariable cv_;
    153 };
    154 
    155 void WaitableEvent::Wait() {
    156   bool result = TimedWait(TimeDelta::FromSeconds(-1));
    157   DCHECK(result) << "TimedWait() should never fail with infinite timeout";
    158 }
    159 
    160 bool WaitableEvent::TimedWait(const TimeDelta& max_time) {
    161   base::ThreadRestrictions::AssertWaitAllowed();
    162   const TimeTicks end_time(TimeTicks::Now() + max_time);
    163   const bool finite_time = max_time.ToInternalValue() >= 0;
    164 
    165   kernel_->lock_.Acquire();
    166   if (kernel_->signaled_) {
    167     if (!kernel_->manual_reset_) {
    168       // In this case we were signaled when we had no waiters. Now that
    169       // someone has waited upon us, we can automatically reset.
    170       kernel_->signaled_ = false;
    171     }
    172 
    173     kernel_->lock_.Release();
    174     return true;
    175   }
    176 
    177   SyncWaiter sw;
    178   sw.lock()->Acquire();
    179 
    180   Enqueue(&sw);
    181   kernel_->lock_.Release();
    182   // We are violating locking order here by holding the SyncWaiter lock but not
    183   // the WaitableEvent lock. However, this is safe because we don't lock @lock_
    184   // again before unlocking it.
    185 
    186   for (;;) {
    187     const TimeTicks current_time(TimeTicks::Now());
    188 
    189     if (sw.fired() || (finite_time && current_time >= end_time)) {
    190       const bool return_value = sw.fired();
    191 
    192       // We can't acquire @lock_ before releasing the SyncWaiter lock (because
    193       // of locking order), however, in between the two a signal could be fired
    194       // and @sw would accept it, however we will still return false, so the
    195       // signal would be lost on an auto-reset WaitableEvent. Thus we call
    196       // Disable which makes sw::Fire return false.
    197       sw.Disable();
    198       sw.lock()->Release();
    199 
    200       kernel_->lock_.Acquire();
    201       kernel_->Dequeue(&sw, &sw);
    202       kernel_->lock_.Release();
    203 
    204       return return_value;
    205     }
    206 
    207     if (finite_time) {
    208       const TimeDelta max_wait(end_time - current_time);
    209       sw.cv()->TimedWait(max_wait);
    210     } else {
    211       sw.cv()->Wait();
    212     }
    213   }
    214 }
    215 
    216 // -----------------------------------------------------------------------------
    217 // Synchronous waiting on multiple objects.
    218 
    219 static bool  // StrictWeakOrdering
    220 cmp_fst_addr(const std::pair<WaitableEvent*, unsigned> &a,
    221              const std::pair<WaitableEvent*, unsigned> &b) {
    222   return a.first < b.first;
    223 }
    224 
    225 // static
    226 size_t WaitableEvent::WaitMany(WaitableEvent** raw_waitables,
    227                                size_t count) {
    228   base::ThreadRestrictions::AssertWaitAllowed();
    229   DCHECK(count) << "Cannot wait on no events";
    230 
    231   // We need to acquire the locks in a globally consistent order. Thus we sort
    232   // the array of waitables by address. We actually sort a pairs so that we can
    233   // map back to the original index values later.
    234   std::vector<std::pair<WaitableEvent*, size_t> > waitables;
    235   waitables.reserve(count);
    236   for (size_t i = 0; i < count; ++i)
    237     waitables.push_back(std::make_pair(raw_waitables[i], i));
    238 
    239   DCHECK_EQ(count, waitables.size());
    240 
    241   sort(waitables.begin(), waitables.end(), cmp_fst_addr);
    242 
    243   // The set of waitables must be distinct. Since we have just sorted by
    244   // address, we can check this cheaply by comparing pairs of consecutive
    245   // elements.
    246   for (size_t i = 0; i < waitables.size() - 1; ++i) {
    247     DCHECK(waitables[i].first != waitables[i+1].first);
    248   }
    249 
    250   SyncWaiter sw;
    251 
    252   const size_t r = EnqueueMany(&waitables[0], count, &sw);
    253   if (r) {
    254     // One of the events is already signaled. The SyncWaiter has not been
    255     // enqueued anywhere. EnqueueMany returns the count of remaining waitables
    256     // when the signaled one was seen, so the index of the signaled event is
    257     // @count - @r.
    258     return waitables[count - r].second;
    259   }
    260 
    261   // At this point, we hold the locks on all the WaitableEvents and we have
    262   // enqueued our waiter in them all.
    263   sw.lock()->Acquire();
    264     // Release the WaitableEvent locks in the reverse order
    265     for (size_t i = 0; i < count; ++i) {
    266       waitables[count - (1 + i)].first->kernel_->lock_.Release();
    267     }
    268 
    269     for (;;) {
    270       if (sw.fired())
    271         break;
    272 
    273       sw.cv()->Wait();
    274     }
    275   sw.lock()->Release();
    276 
    277   // The address of the WaitableEvent which fired is stored in the SyncWaiter.
    278   WaitableEvent *const signaled_event = sw.signaling_event();
    279   // This will store the index of the raw_waitables which fired.
    280   size_t signaled_index = 0;
    281 
    282   // Take the locks of each WaitableEvent in turn (except the signaled one) and
    283   // remove our SyncWaiter from the wait-list
    284   for (size_t i = 0; i < count; ++i) {
    285     if (raw_waitables[i] != signaled_event) {
    286       raw_waitables[i]->kernel_->lock_.Acquire();
    287         // There's no possible ABA issue with the address of the SyncWaiter here
    288         // because it lives on the stack. Thus the tag value is just the pointer
    289         // value again.
    290         raw_waitables[i]->kernel_->Dequeue(&sw, &sw);
    291       raw_waitables[i]->kernel_->lock_.Release();
    292     } else {
    293       signaled_index = i;
    294     }
    295   }
    296 
    297   return signaled_index;
    298 }
    299 
    300 // -----------------------------------------------------------------------------
    301 // If return value == 0:
    302 //   The locks of the WaitableEvents have been taken in order and the Waiter has
    303 //   been enqueued in the wait-list of each. None of the WaitableEvents are
    304 //   currently signaled
    305 // else:
    306 //   None of the WaitableEvent locks are held. The Waiter has not been enqueued
    307 //   in any of them and the return value is the index of the first WaitableEvent
    308 //   which was signaled, from the end of the array.
    309 // -----------------------------------------------------------------------------
    310 // static
    311 size_t WaitableEvent::EnqueueMany
    312     (std::pair<WaitableEvent*, size_t>* waitables,
    313      size_t count, Waiter* waiter) {
    314   if (!count)
    315     return 0;
    316 
    317   waitables[0].first->kernel_->lock_.Acquire();
    318     if (waitables[0].first->kernel_->signaled_) {
    319       if (!waitables[0].first->kernel_->manual_reset_)
    320         waitables[0].first->kernel_->signaled_ = false;
    321       waitables[0].first->kernel_->lock_.Release();
    322       return count;
    323     }
    324 
    325     const size_t r = EnqueueMany(waitables + 1, count - 1, waiter);
    326     if (r) {
    327       waitables[0].first->kernel_->lock_.Release();
    328     } else {
    329       waitables[0].first->Enqueue(waiter);
    330     }
    331 
    332     return r;
    333 }
    334 
    335 // -----------------------------------------------------------------------------
    336 
    337 
    338 // -----------------------------------------------------------------------------
    339 // Private functions...
    340 
    341 WaitableEvent::WaitableEventKernel::WaitableEventKernel(bool manual_reset,
    342                                                         bool initially_signaled)
    343     : manual_reset_(manual_reset),
    344       signaled_(initially_signaled) {
    345 }
    346 
    347 WaitableEvent::WaitableEventKernel::~WaitableEventKernel() {
    348 }
    349 
    350 // -----------------------------------------------------------------------------
    351 // Wake all waiting waiters. Called with lock held.
    352 // -----------------------------------------------------------------------------
    353 bool WaitableEvent::SignalAll() {
    354   bool signaled_at_least_one = false;
    355 
    356   for (std::list<Waiter*>::iterator
    357        i = kernel_->waiters_.begin(); i != kernel_->waiters_.end(); ++i) {
    358     if ((*i)->Fire(this))
    359       signaled_at_least_one = true;
    360   }
    361 
    362   kernel_->waiters_.clear();
    363   return signaled_at_least_one;
    364 }
    365 
    366 // ---------------------------------------------------------------------------
    367 // Try to wake a single waiter. Return true if one was woken. Called with lock
    368 // held.
    369 // ---------------------------------------------------------------------------
    370 bool WaitableEvent::SignalOne() {
    371   for (;;) {
    372     if (kernel_->waiters_.empty())
    373       return false;
    374 
    375     const bool r = (*kernel_->waiters_.begin())->Fire(this);
    376     kernel_->waiters_.pop_front();
    377     if (r)
    378       return true;
    379   }
    380 }
    381 
    382 // -----------------------------------------------------------------------------
    383 // Add a waiter to the list of those waiting. Called with lock held.
    384 // -----------------------------------------------------------------------------
    385 void WaitableEvent::Enqueue(Waiter* waiter) {
    386   kernel_->waiters_.push_back(waiter);
    387 }
    388 
    389 // -----------------------------------------------------------------------------
    390 // Remove a waiter from the list of those waiting. Return true if the waiter was
    391 // actually removed. Called with lock held.
    392 // -----------------------------------------------------------------------------
    393 bool WaitableEvent::WaitableEventKernel::Dequeue(Waiter* waiter, void* tag) {
    394   for (std::list<Waiter*>::iterator
    395        i = waiters_.begin(); i != waiters_.end(); ++i) {
    396     if (*i == waiter && (*i)->Compare(tag)) {
    397       waiters_.erase(i);
    398       return true;
    399     }
    400   }
    401 
    402   return false;
    403 }
    404 
    405 // -----------------------------------------------------------------------------
    406 
    407 }  // namespace base
    408