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