1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/ipc/chromium/src/base/waitable_event_posix.cc Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,390 @@
1.4 +// Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
1.5 +// Use of this source code is governed by a BSD-style license that can be
1.6 +// found in the LICENSE file.
1.7 +
1.8 +#include "base/waitable_event.h"
1.9 +
1.10 +#include "base/condition_variable.h"
1.11 +#include "base/lock.h"
1.12 +#include "base/message_loop.h"
1.13 +
1.14 +// -----------------------------------------------------------------------------
1.15 +// A WaitableEvent on POSIX is implemented as a wait-list. Currently we don't
1.16 +// support cross-process events (where one process can signal an event which
1.17 +// others are waiting on). Because of this, we can avoid having one thread per
1.18 +// listener in several cases.
1.19 +//
1.20 +// The WaitableEvent maintains a list of waiters, protected by a lock. Each
1.21 +// waiter is either an async wait, in which case we have a Task and the
1.22 +// MessageLoop to run it on, or a blocking wait, in which case we have the
1.23 +// condition variable to signal.
1.24 +//
1.25 +// Waiting involves grabbing the lock and adding oneself to the wait list. Async
1.26 +// waits can be canceled, which means grabbing the lock and removing oneself
1.27 +// from the list.
1.28 +//
1.29 +// Waiting on multiple events is handled by adding a single, synchronous wait to
1.30 +// the wait-list of many events. An event passes a pointer to itself when
1.31 +// firing a waiter and so we can store that pointer to find out which event
1.32 +// triggered.
1.33 +// -----------------------------------------------------------------------------
1.34 +
1.35 +namespace base {
1.36 +
1.37 +// -----------------------------------------------------------------------------
1.38 +// This is just an abstract base class for waking the two types of waiters
1.39 +// -----------------------------------------------------------------------------
1.40 +WaitableEvent::WaitableEvent(bool manual_reset, bool initially_signaled)
1.41 + : kernel_(new WaitableEventKernel(manual_reset, initially_signaled)) {
1.42 +}
1.43 +
1.44 +WaitableEvent::~WaitableEvent() {
1.45 +}
1.46 +
1.47 +void WaitableEvent::Reset() {
1.48 + AutoLock locked(kernel_->lock_);
1.49 + kernel_->signaled_ = false;
1.50 +}
1.51 +
1.52 +void WaitableEvent::Signal() {
1.53 + AutoLock locked(kernel_->lock_);
1.54 +
1.55 + if (kernel_->signaled_)
1.56 + return;
1.57 +
1.58 + if (kernel_->manual_reset_) {
1.59 + SignalAll();
1.60 + kernel_->signaled_ = true;
1.61 + } else {
1.62 + // In the case of auto reset, if no waiters were woken, we remain
1.63 + // signaled.
1.64 + if (!SignalOne())
1.65 + kernel_->signaled_ = true;
1.66 + }
1.67 +}
1.68 +
1.69 +bool WaitableEvent::IsSignaled() {
1.70 + AutoLock locked(kernel_->lock_);
1.71 +
1.72 + const bool result = kernel_->signaled_;
1.73 + if (result && !kernel_->manual_reset_)
1.74 + kernel_->signaled_ = false;
1.75 + return result;
1.76 +}
1.77 +
1.78 +// -----------------------------------------------------------------------------
1.79 +// Synchronous waits
1.80 +
1.81 +// -----------------------------------------------------------------------------
1.82 +// This is an synchronous waiter. The thread is waiting on the given condition
1.83 +// variable and the fired flag in this object.
1.84 +// -----------------------------------------------------------------------------
1.85 +class SyncWaiter : public WaitableEvent::Waiter {
1.86 + public:
1.87 + SyncWaiter(ConditionVariable* cv, Lock* lock)
1.88 + : fired_(false),
1.89 + cv_(cv),
1.90 + lock_(lock),
1.91 + signaling_event_(NULL) {
1.92 + }
1.93 +
1.94 + bool Fire(WaitableEvent *signaling_event) {
1.95 + lock_->Acquire();
1.96 + const bool previous_value = fired_;
1.97 + fired_ = true;
1.98 + if (!previous_value)
1.99 + signaling_event_ = signaling_event;
1.100 + lock_->Release();
1.101 +
1.102 + if (previous_value)
1.103 + return false;
1.104 +
1.105 + cv_->Broadcast();
1.106 +
1.107 + // SyncWaiters are stack allocated on the stack of the blocking thread.
1.108 + return true;
1.109 + }
1.110 +
1.111 + WaitableEvent* signaled_event() const {
1.112 + return signaling_event_;
1.113 + }
1.114 +
1.115 + // ---------------------------------------------------------------------------
1.116 + // These waiters are always stack allocated and don't delete themselves. Thus
1.117 + // there's no problem and the ABA tag is the same as the object pointer.
1.118 + // ---------------------------------------------------------------------------
1.119 + bool Compare(void* tag) {
1.120 + return this == tag;
1.121 + }
1.122 +
1.123 + // ---------------------------------------------------------------------------
1.124 + // Called with lock held.
1.125 + // ---------------------------------------------------------------------------
1.126 + bool fired() const {
1.127 + return fired_;
1.128 + }
1.129 +
1.130 + // ---------------------------------------------------------------------------
1.131 + // During a TimedWait, we need a way to make sure that an auto-reset
1.132 + // WaitableEvent doesn't think that this event has been signaled between
1.133 + // unlocking it and removing it from the wait-list. Called with lock held.
1.134 + // ---------------------------------------------------------------------------
1.135 + void Disable() {
1.136 + fired_ = true;
1.137 + }
1.138 +
1.139 + private:
1.140 + bool fired_;
1.141 + ConditionVariable *const cv_;
1.142 + Lock *const lock_;
1.143 + WaitableEvent* signaling_event_; // The WaitableEvent which woke us
1.144 +};
1.145 +
1.146 +bool WaitableEvent::TimedWait(const TimeDelta& max_time) {
1.147 + const TimeTicks end_time(TimeTicks::Now() + max_time);
1.148 + const bool finite_time = max_time.ToInternalValue() >= 0;
1.149 +
1.150 + kernel_->lock_.Acquire();
1.151 + if (kernel_->signaled_) {
1.152 + if (!kernel_->manual_reset_) {
1.153 + // In this case we were signaled when we had no waiters. Now that
1.154 + // someone has waited upon us, we can automatically reset.
1.155 + kernel_->signaled_ = false;
1.156 + }
1.157 +
1.158 + kernel_->lock_.Release();
1.159 + return true;
1.160 + }
1.161 +
1.162 + Lock lock;
1.163 + lock.Acquire();
1.164 + ConditionVariable cv(&lock);
1.165 + SyncWaiter sw(&cv, &lock);
1.166 +
1.167 + Enqueue(&sw);
1.168 + kernel_->lock_.Release();
1.169 + // We are violating locking order here by holding the SyncWaiter lock but not
1.170 + // the WaitableEvent lock. However, this is safe because we don't lock @lock_
1.171 + // again before unlocking it.
1.172 +
1.173 + for (;;) {
1.174 + const TimeTicks current_time(TimeTicks::Now());
1.175 +
1.176 + if (sw.fired() || (finite_time && current_time >= end_time)) {
1.177 + const bool return_value = sw.fired();
1.178 +
1.179 + // We can't acquire @lock_ before releasing @lock (because of locking
1.180 + // order), however, inbetween the two a signal could be fired and @sw
1.181 + // would accept it, however we will still return false, so the signal
1.182 + // would be lost on an auto-reset WaitableEvent. Thus we call Disable
1.183 + // which makes sw::Fire return false.
1.184 + sw.Disable();
1.185 + lock.Release();
1.186 +
1.187 + kernel_->lock_.Acquire();
1.188 + kernel_->Dequeue(&sw, &sw);
1.189 + kernel_->lock_.Release();
1.190 +
1.191 + return return_value;
1.192 + }
1.193 +
1.194 + if (finite_time) {
1.195 + const TimeDelta max_wait(end_time - current_time);
1.196 + cv.TimedWait(max_wait);
1.197 + } else {
1.198 + cv.Wait();
1.199 + }
1.200 + }
1.201 +}
1.202 +
1.203 +bool WaitableEvent::Wait() {
1.204 + return TimedWait(TimeDelta::FromSeconds(-1));
1.205 +}
1.206 +
1.207 +// -----------------------------------------------------------------------------
1.208 +
1.209 +
1.210 +// -----------------------------------------------------------------------------
1.211 +// Synchronous waiting on multiple objects.
1.212 +
1.213 +static bool // StrictWeakOrdering
1.214 +cmp_fst_addr(const std::pair<WaitableEvent*, unsigned> &a,
1.215 + const std::pair<WaitableEvent*, unsigned> &b) {
1.216 + return a.first < b.first;
1.217 +}
1.218 +
1.219 +// static
1.220 +size_t WaitableEvent::WaitMany(WaitableEvent** raw_waitables,
1.221 + size_t count) {
1.222 + DCHECK(count) << "Cannot wait on no events";
1.223 +
1.224 + // We need to acquire the locks in a globally consistent order. Thus we sort
1.225 + // the array of waitables by address. We actually sort a pairs so that we can
1.226 + // map back to the original index values later.
1.227 + std::vector<std::pair<WaitableEvent*, size_t> > waitables;
1.228 + waitables.reserve(count);
1.229 + for (size_t i = 0; i < count; ++i)
1.230 + waitables.push_back(std::make_pair(raw_waitables[i], i));
1.231 +
1.232 + DCHECK_EQ(count, waitables.size());
1.233 +
1.234 + sort(waitables.begin(), waitables.end(), cmp_fst_addr);
1.235 +
1.236 + // The set of waitables must be distinct. Since we have just sorted by
1.237 + // address, we can check this cheaply by comparing pairs of consecutive
1.238 + // elements.
1.239 + for (size_t i = 0; i < waitables.size() - 1; ++i) {
1.240 + DCHECK(waitables[i].first != waitables[i+1].first);
1.241 + }
1.242 +
1.243 + Lock lock;
1.244 + ConditionVariable cv(&lock);
1.245 + SyncWaiter sw(&cv, &lock);
1.246 +
1.247 + const size_t r = EnqueueMany(&waitables[0], count, &sw);
1.248 + if (r) {
1.249 + // One of the events is already signaled. The SyncWaiter has not been
1.250 + // enqueued anywhere. EnqueueMany returns the count of remaining waitables
1.251 + // when the signaled one was seen, so the index of the signaled event is
1.252 + // @count - @r.
1.253 + return waitables[count - r].second;
1.254 + }
1.255 +
1.256 + // At this point, we hold the locks on all the WaitableEvents and we have
1.257 + // enqueued our waiter in them all.
1.258 + lock.Acquire();
1.259 + // Release the WaitableEvent locks in the reverse order
1.260 + for (size_t i = 0; i < count; ++i) {
1.261 + waitables[count - (1 + i)].first->kernel_->lock_.Release();
1.262 + }
1.263 +
1.264 + for (;;) {
1.265 + if (sw.fired())
1.266 + break;
1.267 +
1.268 + cv.Wait();
1.269 + }
1.270 + lock.Release();
1.271 +
1.272 + // The address of the WaitableEvent which fired is stored in the SyncWaiter.
1.273 + WaitableEvent *const signaled_event = sw.signaled_event();
1.274 + // This will store the index of the raw_waitables which fired.
1.275 + size_t signaled_index = 0;
1.276 +
1.277 + // Take the locks of each WaitableEvent in turn (except the signaled one) and
1.278 + // remove our SyncWaiter from the wait-list
1.279 + for (size_t i = 0; i < count; ++i) {
1.280 + if (raw_waitables[i] != signaled_event) {
1.281 + raw_waitables[i]->kernel_->lock_.Acquire();
1.282 + // There's no possible ABA issue with the address of the SyncWaiter here
1.283 + // because it lives on the stack. Thus the tag value is just the pointer
1.284 + // value again.
1.285 + raw_waitables[i]->kernel_->Dequeue(&sw, &sw);
1.286 + raw_waitables[i]->kernel_->lock_.Release();
1.287 + } else {
1.288 + signaled_index = i;
1.289 + }
1.290 + }
1.291 +
1.292 + return signaled_index;
1.293 +}
1.294 +
1.295 +// -----------------------------------------------------------------------------
1.296 +// If return value == 0:
1.297 +// The locks of the WaitableEvents have been taken in order and the Waiter has
1.298 +// been enqueued in the wait-list of each. None of the WaitableEvents are
1.299 +// currently signaled
1.300 +// else:
1.301 +// None of the WaitableEvent locks are held. The Waiter has not been enqueued
1.302 +// in any of them and the return value is the index of the first WaitableEvent
1.303 +// which was signaled, from the end of the array.
1.304 +// -----------------------------------------------------------------------------
1.305 +// static
1.306 +size_t WaitableEvent::EnqueueMany
1.307 + (std::pair<WaitableEvent*, size_t>* waitables,
1.308 + size_t count, Waiter* waiter) {
1.309 + if (!count)
1.310 + return 0;
1.311 +
1.312 + waitables[0].first->kernel_->lock_.Acquire();
1.313 + if (waitables[0].first->kernel_->signaled_) {
1.314 + if (!waitables[0].first->kernel_->manual_reset_)
1.315 + waitables[0].first->kernel_->signaled_ = false;
1.316 + waitables[0].first->kernel_->lock_.Release();
1.317 + return count;
1.318 + }
1.319 +
1.320 + const size_t r = EnqueueMany(waitables + 1, count - 1, waiter);
1.321 + if (r) {
1.322 + waitables[0].first->kernel_->lock_.Release();
1.323 + } else {
1.324 + waitables[0].first->Enqueue(waiter);
1.325 + }
1.326 +
1.327 + return r;
1.328 +}
1.329 +
1.330 +// -----------------------------------------------------------------------------
1.331 +
1.332 +
1.333 +// -----------------------------------------------------------------------------
1.334 +// Private functions...
1.335 +
1.336 +// -----------------------------------------------------------------------------
1.337 +// Wake all waiting waiters. Called with lock held.
1.338 +// -----------------------------------------------------------------------------
1.339 +bool WaitableEvent::SignalAll() {
1.340 + bool signaled_at_least_one = false;
1.341 +
1.342 + for (std::list<Waiter*>::iterator
1.343 + i = kernel_->waiters_.begin(); i != kernel_->waiters_.end(); ++i) {
1.344 + if ((*i)->Fire(this))
1.345 + signaled_at_least_one = true;
1.346 + }
1.347 +
1.348 + kernel_->waiters_.clear();
1.349 + return signaled_at_least_one;
1.350 +}
1.351 +
1.352 +// ---------------------------------------------------------------------------
1.353 +// Try to wake a single waiter. Return true if one was woken. Called with lock
1.354 +// held.
1.355 +// ---------------------------------------------------------------------------
1.356 +bool WaitableEvent::SignalOne() {
1.357 + for (;;) {
1.358 + if (kernel_->waiters_.empty())
1.359 + return false;
1.360 +
1.361 + const bool r = (*kernel_->waiters_.begin())->Fire(this);
1.362 + kernel_->waiters_.pop_front();
1.363 + if (r)
1.364 + return true;
1.365 + }
1.366 +}
1.367 +
1.368 +// -----------------------------------------------------------------------------
1.369 +// Add a waiter to the list of those waiting. Called with lock held.
1.370 +// -----------------------------------------------------------------------------
1.371 +void WaitableEvent::Enqueue(Waiter* waiter) {
1.372 + kernel_->waiters_.push_back(waiter);
1.373 +}
1.374 +
1.375 +// -----------------------------------------------------------------------------
1.376 +// Remove a waiter from the list of those waiting. Return true if the waiter was
1.377 +// actually removed. Called with lock held.
1.378 +// -----------------------------------------------------------------------------
1.379 +bool WaitableEvent::WaitableEventKernel::Dequeue(Waiter* waiter, void* tag) {
1.380 + for (std::list<Waiter*>::iterator
1.381 + i = waiters_.begin(); i != waiters_.end(); ++i) {
1.382 + if (*i == waiter && (*i)->Compare(tag)) {
1.383 + waiters_.erase(i);
1.384 + return true;
1.385 + }
1.386 + }
1.387 +
1.388 + return false;
1.389 +}
1.390 +
1.391 +// -----------------------------------------------------------------------------
1.392 +
1.393 +} // namespace base
