15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2012 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <algorithm> 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <vector> 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/logging.h" 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/synchronization/waitable_event.h" 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/synchronization/condition_variable.h" 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/synchronization/lock.h" 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/threading/thread_restrictions.h" 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A WaitableEvent on POSIX is implemented as a wait-list. Currently we don't 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// support cross-process events (where one process can signal an event which 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// others are waiting on). Because of this, we can avoid having one thread per 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// listener in several cases. 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The WaitableEvent maintains a list of waiters, protected by a lock. Each 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// waiter is either an async wait, in which case we have a Task and the 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// MessageLoop to run it on, or a blocking wait, in which case we have the 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// condition variable to signal. 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Waiting involves grabbing the lock and adding oneself to the wait list. Async 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// waits can be canceled, which means grabbing the lock and removing oneself 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// from the list. 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Waiting on multiple events is handled by adding a single, synchronous wait to 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the wait-list of many events. An event passes a pointer to itself when 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// firing a waiter and so we can store that pointer to find out which event 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// triggered. 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace base { 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This is just an abstract base class for waking the two types of waiters 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)WaitableEvent::WaitableEvent(bool manual_reset, bool initially_signaled) 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : kernel_(new WaitableEventKernel(manual_reset, initially_signaled)) { 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)WaitableEvent::~WaitableEvent() { 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void WaitableEvent::Reset() { 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::AutoLock locked(kernel_->lock_); 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kernel_->signaled_ = false; 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void WaitableEvent::Signal() { 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::AutoLock locked(kernel_->lock_); 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (kernel_->signaled_) 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (kernel_->manual_reset_) { 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SignalAll(); 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kernel_->signaled_ = true; 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // In the case of auto reset, if no waiters were woken, we remain 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // signaled. 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!SignalOne()) 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kernel_->signaled_ = true; 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool WaitableEvent::IsSignaled() { 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::AutoLock locked(kernel_->lock_); 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const bool result = kernel_->signaled_; 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (result && !kernel_->manual_reset_) 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kernel_->signaled_ = false; 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return result; 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Synchronous waits 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This is a synchronous waiter. The thread is waiting on the given condition 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// variable and the fired flag in this object. 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class SyncWaiter : public WaitableEvent::Waiter { 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SyncWaiter() 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : fired_(false), 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) signaling_event_(NULL), 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lock_(), 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) cv_(&lock_) { 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual bool Fire(WaitableEvent* signaling_event) OVERRIDE { 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::AutoLock locked(lock_); 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (fired_) 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fired_ = true; 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) signaling_event_ = signaling_event; 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) cv_.Broadcast(); 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Unlike AsyncWaiter objects, SyncWaiter objects are stack-allocated on 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the blocking thread's stack. There is no |delete this;| in Fire. The 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // SyncWaiter object is destroyed when it goes out of scope. 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WaitableEvent* signaling_event() const { 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return signaling_event_; 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // --------------------------------------------------------------------------- 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // These waiters are always stack allocated and don't delete themselves. Thus 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // there's no problem and the ABA tag is the same as the object pointer. 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // --------------------------------------------------------------------------- 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual bool Compare(void* tag) OVERRIDE { 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return this == tag; 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // --------------------------------------------------------------------------- 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Called with lock held. 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // --------------------------------------------------------------------------- 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool fired() const { 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return fired_; 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // --------------------------------------------------------------------------- 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // During a TimedWait, we need a way to make sure that an auto-reset 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // WaitableEvent doesn't think that this event has been signaled between 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // unlocking it and removing it from the wait-list. Called with lock held. 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // --------------------------------------------------------------------------- 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Disable() { 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fired_ = true; 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::Lock* lock() { 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return &lock_; 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::ConditionVariable* cv() { 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return &cv_; 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool fired_; 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WaitableEvent* signaling_event_; // The WaitableEvent which woke us 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::Lock lock_; 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::ConditionVariable cv_; 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void WaitableEvent::Wait() { 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool result = TimedWait(TimeDelta::FromSeconds(-1)); 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(result) << "TimedWait() should never fail with infinite timeout"; 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool WaitableEvent::TimedWait(const TimeDelta& max_time) { 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::ThreadRestrictions::AssertWaitAllowed(); 1624e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) const TimeTicks end_time(TimeTicks::Now() + max_time); 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const bool finite_time = max_time.ToInternalValue() >= 0; 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kernel_->lock_.Acquire(); 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (kernel_->signaled_) { 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!kernel_->manual_reset_) { 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // In this case we were signaled when we had no waiters. Now that 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // someone has waited upon us, we can automatically reset. 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kernel_->signaled_ = false; 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kernel_->lock_.Release(); 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SyncWaiter sw; 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sw.lock()->Acquire(); 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Enqueue(&sw); 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kernel_->lock_.Release(); 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We are violating locking order here by holding the SyncWaiter lock but not 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the WaitableEvent lock. However, this is safe because we don't lock @lock_ 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // again before unlocking it. 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (;;) { 1874e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) const TimeTicks current_time(TimeTicks::Now()); 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (sw.fired() || (finite_time && current_time >= end_time)) { 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const bool return_value = sw.fired(); 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We can't acquire @lock_ before releasing the SyncWaiter lock (because 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // of locking order), however, in between the two a signal could be fired 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // and @sw would accept it, however we will still return false, so the 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // signal would be lost on an auto-reset WaitableEvent. Thus we call 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Disable which makes sw::Fire return false. 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sw.Disable(); 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sw.lock()->Release(); 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2005f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // This is a bug that has been enshrined in the interface of 2015f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // WaitableEvent now: |Dequeue| is called even when |sw.fired()| is true, 2025f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // even though it'll always return false in that case. However, taking 2035f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // the lock ensures that |Signal| has completed before we return and 2045f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // means that a WaitableEvent can synchronise its own destruction. 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kernel_->lock_.Acquire(); 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kernel_->Dequeue(&sw, &sw); 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kernel_->lock_.Release(); 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return return_value; 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (finite_time) { 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const TimeDelta max_wait(end_time - current_time); 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sw.cv()->TimedWait(max_wait); 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sw.cv()->Wait(); 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Synchronous waiting on multiple objects. 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static bool // StrictWeakOrdering 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)cmp_fst_addr(const std::pair<WaitableEvent*, unsigned> &a, 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const std::pair<WaitableEvent*, unsigned> &b) { 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return a.first < b.first; 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// static 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)size_t WaitableEvent::WaitMany(WaitableEvent** raw_waitables, 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t count) { 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::ThreadRestrictions::AssertWaitAllowed(); 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(count) << "Cannot wait on no events"; 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We need to acquire the locks in a globally consistent order. Thus we sort 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the array of waitables by address. We actually sort a pairs so that we can 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // map back to the original index values later. 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<std::pair<WaitableEvent*, size_t> > waitables; 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) waitables.reserve(count); 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < count; ++i) 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) waitables.push_back(std::make_pair(raw_waitables[i], i)); 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_EQ(count, waitables.size()); 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sort(waitables.begin(), waitables.end(), cmp_fst_addr); 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The set of waitables must be distinct. Since we have just sorted by 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // address, we can check this cheaply by comparing pairs of consecutive 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // elements. 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < waitables.size() - 1; ++i) { 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(waitables[i].first != waitables[i+1].first); 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SyncWaiter sw; 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const size_t r = EnqueueMany(&waitables[0], count, &sw); 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (r) { 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // One of the events is already signaled. The SyncWaiter has not been 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // enqueued anywhere. EnqueueMany returns the count of remaining waitables 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // when the signaled one was seen, so the index of the signaled event is 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // @count - @r. 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return waitables[count - r].second; 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // At this point, we hold the locks on all the WaitableEvents and we have 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // enqueued our waiter in them all. 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sw.lock()->Acquire(); 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Release the WaitableEvent locks in the reverse order 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < count; ++i) { 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) waitables[count - (1 + i)].first->kernel_->lock_.Release(); 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (;;) { 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (sw.fired()) 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sw.cv()->Wait(); 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sw.lock()->Release(); 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The address of the WaitableEvent which fired is stored in the SyncWaiter. 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WaitableEvent *const signaled_event = sw.signaling_event(); 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This will store the index of the raw_waitables which fired. 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t signaled_index = 0; 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Take the locks of each WaitableEvent in turn (except the signaled one) and 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // remove our SyncWaiter from the wait-list 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < count; ++i) { 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (raw_waitables[i] != signaled_event) { 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) raw_waitables[i]->kernel_->lock_.Acquire(); 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // There's no possible ABA issue with the address of the SyncWaiter here 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // because it lives on the stack. Thus the tag value is just the pointer 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // value again. 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) raw_waitables[i]->kernel_->Dequeue(&sw, &sw); 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) raw_waitables[i]->kernel_->lock_.Release(); 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2985f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // By taking this lock here we ensure that |Signal| has completed by the 2995f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // time we return, because |Signal| holds this lock. This matches the 3005f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // behaviour of |Wait| and |TimedWait|. 3015f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) raw_waitables[i]->kernel_->lock_.Acquire(); 3025f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) raw_waitables[i]->kernel_->lock_.Release(); 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) signaled_index = i; 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return signaled_index; 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// If return value == 0: 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The locks of the WaitableEvents have been taken in order and the Waiter has 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// been enqueued in the wait-list of each. None of the WaitableEvents are 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// currently signaled 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// else: 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// None of the WaitableEvent locks are held. The Waiter has not been enqueued 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// in any of them and the return value is the index of the first WaitableEvent 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// which was signaled, from the end of the array. 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// static 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)size_t WaitableEvent::EnqueueMany 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (std::pair<WaitableEvent*, size_t>* waitables, 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t count, Waiter* waiter) { 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!count) 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) waitables[0].first->kernel_->lock_.Acquire(); 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (waitables[0].first->kernel_->signaled_) { 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!waitables[0].first->kernel_->manual_reset_) 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) waitables[0].first->kernel_->signaled_ = false; 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) waitables[0].first->kernel_->lock_.Release(); 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return count; 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const size_t r = EnqueueMany(waitables + 1, count - 1, waiter); 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (r) { 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) waitables[0].first->kernel_->lock_.Release(); 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) waitables[0].first->Enqueue(waiter); 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return r; 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Private functions... 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)WaitableEvent::WaitableEventKernel::WaitableEventKernel(bool manual_reset, 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool initially_signaled) 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : manual_reset_(manual_reset), 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) signaled_(initially_signaled) { 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)WaitableEvent::WaitableEventKernel::~WaitableEventKernel() { 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Wake all waiting waiters. Called with lock held. 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool WaitableEvent::SignalAll() { 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool signaled_at_least_one = false; 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (std::list<Waiter*>::iterator 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i = kernel_->waiters_.begin(); i != kernel_->waiters_.end(); ++i) { 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((*i)->Fire(this)) 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) signaled_at_least_one = true; 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kernel_->waiters_.clear(); 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return signaled_at_least_one; 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// --------------------------------------------------------------------------- 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Try to wake a single waiter. Return true if one was woken. Called with lock 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// held. 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// --------------------------------------------------------------------------- 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool WaitableEvent::SignalOne() { 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (;;) { 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (kernel_->waiters_.empty()) 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const bool r = (*kernel_->waiters_.begin())->Fire(this); 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kernel_->waiters_.pop_front(); 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (r) 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Add a waiter to the list of those waiting. Called with lock held. 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void WaitableEvent::Enqueue(Waiter* waiter) { 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kernel_->waiters_.push_back(waiter); 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Remove a waiter from the list of those waiting. Return true if the waiter was 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// actually removed. Called with lock held. 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool WaitableEvent::WaitableEventKernel::Dequeue(Waiter* waiter, void* tag) { 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (std::list<Waiter*>::iterator 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i = waiters_.begin(); i != waiters_.end(); ++i) { 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (*i == waiter && (*i)->Compare(tag)) { 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) waiters_.erase(i); 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------------- 4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace base 418