Fix iOS build for XCode 4.6.
[chromium-blink-merge.git] / base / synchronization / waitable_event_posix.cc
blob714c111e1970cd0490483a3e5656e53b2efeaff8
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.
5 #include <algorithm>
6 #include <vector>
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"
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.
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.
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.
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 // -----------------------------------------------------------------------------
35 namespace base {
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)) {
44 WaitableEvent::~WaitableEvent() {
47 void WaitableEvent::Reset() {
48 base::AutoLock locked(kernel_->lock_);
49 kernel_->signaled_ = false;
52 void WaitableEvent::Signal() {
53 base::AutoLock locked(kernel_->lock_);
55 if (kernel_->signaled_)
56 return;
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;
69 bool WaitableEvent::IsSignaled() {
70 base::AutoLock locked(kernel_->lock_);
72 const bool result = kernel_->signaled_;
73 if (result && !kernel_->manual_reset_)
74 kernel_->signaled_ = false;
75 return result;
78 // -----------------------------------------------------------------------------
79 // Synchronous waits
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_) {
94 virtual bool Fire(WaitableEvent* signaling_event) OVERRIDE {
95 base::AutoLock locked(lock_);
97 if (fired_)
98 return false;
100 fired_ = true;
101 signaling_event_ = signaling_event;
103 cv_.Broadcast();
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.
109 return true;
112 WaitableEvent* signaling_event() const {
113 return signaling_event_;
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;
124 // ---------------------------------------------------------------------------
125 // Called with lock held.
126 // ---------------------------------------------------------------------------
127 bool fired() const {
128 return fired_;
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;
140 base::Lock* lock() {
141 return &lock_;
144 base::ConditionVariable* cv() {
145 return &cv_;
148 private:
149 bool fired_;
150 WaitableEvent* signaling_event_; // The WaitableEvent which woke us
151 base::Lock lock_;
152 base::ConditionVariable cv_;
155 void WaitableEvent::Wait() {
156 bool result = TimedWait(TimeDelta::FromSeconds(-1));
157 DCHECK(result) << "TimedWait() should never fail with infinite timeout";
160 bool WaitableEvent::TimedWait(const TimeDelta& max_time) {
161 base::ThreadRestrictions::AssertWaitAllowed();
162 const Time end_time(Time::Now() + max_time);
163 const bool finite_time = max_time.ToInternalValue() >= 0;
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;
173 kernel_->lock_.Release();
174 return true;
177 SyncWaiter sw;
178 sw.lock()->Acquire();
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.
186 for (;;) {
187 const Time current_time(Time::Now());
189 if (sw.fired() || (finite_time && current_time >= end_time)) {
190 const bool return_value = sw.fired();
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();
200 kernel_->lock_.Acquire();
201 kernel_->Dequeue(&sw, &sw);
202 kernel_->lock_.Release();
204 return return_value;
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();
216 // -----------------------------------------------------------------------------
217 // Synchronous waiting on multiple objects.
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;
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";
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));
239 DCHECK_EQ(count, waitables.size());
241 sort(waitables.begin(), waitables.end(), cmp_fst_addr);
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);
250 SyncWaiter sw;
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;
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();
269 for (;;) {
270 if (sw.fired())
271 break;
273 sw.cv()->Wait();
275 sw.lock()->Release();
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;
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;
297 return signaled_index;
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;
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;
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);
332 return r;
335 // -----------------------------------------------------------------------------
338 // -----------------------------------------------------------------------------
339 // Private functions...
341 WaitableEvent::WaitableEventKernel::WaitableEventKernel(bool manual_reset,
342 bool initially_signaled)
343 : manual_reset_(manual_reset),
344 signaled_(initially_signaled) {
347 WaitableEvent::WaitableEventKernel::~WaitableEventKernel() {
350 // -----------------------------------------------------------------------------
351 // Wake all waiting waiters. Called with lock held.
352 // -----------------------------------------------------------------------------
353 bool WaitableEvent::SignalAll() {
354 bool signaled_at_least_one = false;
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;
362 kernel_->waiters_.clear();
363 return signaled_at_least_one;
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;
375 const bool r = (*kernel_->waiters_.begin())->Fire(this);
376 kernel_->waiters_.pop_front();
377 if (r)
378 return true;
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);
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;
402 return false;
405 // -----------------------------------------------------------------------------
407 } // namespace base