1 // Copyright (c) 2006-2008 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 "base/waitable_event.h"
7 #include "base/condition_variable.h"
9 #include "base/message_loop.h"
11 // -----------------------------------------------------------------------------
12 // A WaitableEvent on POSIX is implemented as a wait-list. Currently we don't
13 // support cross-process events (where one process can signal an event which
14 // others are waiting on). Because of this, we can avoid having one thread per
15 // listener in several cases.
17 // The WaitableEvent maintains a list of waiters, protected by a lock. Each
18 // waiter is either an async wait, in which case we have a Task and the
19 // MessageLoop to run it on, or a blocking wait, in which case we have the
20 // condition variable to signal.
22 // Waiting involves grabbing the lock and adding oneself to the wait list. Async
23 // waits can be canceled, which means grabbing the lock and removing oneself
26 // Waiting on multiple events is handled by adding a single, synchronous wait to
27 // the wait-list of many events. An event passes a pointer to itself when
28 // firing a waiter and so we can store that pointer to find out which event
30 // -----------------------------------------------------------------------------
34 // -----------------------------------------------------------------------------
35 // This is just an abstract base class for waking the two types of waiters
36 // -----------------------------------------------------------------------------
37 WaitableEvent::WaitableEvent(bool manual_reset
, bool initially_signaled
)
38 : kernel_(new WaitableEventKernel(manual_reset
, initially_signaled
)) {
41 WaitableEvent::~WaitableEvent() {
44 void WaitableEvent::Reset() {
45 AutoLock
locked(kernel_
->lock_
);
46 kernel_
->signaled_
= false;
49 void WaitableEvent::Signal() {
50 AutoLock
locked(kernel_
->lock_
);
52 if (kernel_
->signaled_
)
55 if (kernel_
->manual_reset_
) {
57 kernel_
->signaled_
= true;
59 // In the case of auto reset, if no waiters were woken, we remain
62 kernel_
->signaled_
= true;
66 bool WaitableEvent::IsSignaled() {
67 AutoLock
locked(kernel_
->lock_
);
69 const bool result
= kernel_
->signaled_
;
70 if (result
&& !kernel_
->manual_reset_
)
71 kernel_
->signaled_
= false;
75 // -----------------------------------------------------------------------------
78 // -----------------------------------------------------------------------------
79 // This is a synchronous waiter. The thread is waiting on the given condition
80 // variable and the fired flag in this object.
81 // -----------------------------------------------------------------------------
82 class SyncWaiter
: public WaitableEvent::Waiter
{
86 signaling_event_(NULL
),
91 bool Fire(WaitableEvent
* signaling_event
) {
92 AutoLock
locked(lock_
);
98 signaling_event_
= signaling_event
;
102 // Unlike AsyncWaiter objects, SyncWaiter objects are stack-allocated on
103 // the blocking thread's stack. There is no |delete this;| in Fire. The
104 // SyncWaiter object is destroyed when it goes out of scope.
109 WaitableEvent
* signaling_event() const {
110 return signaling_event_
;
113 // ---------------------------------------------------------------------------
114 // These waiters are always stack allocated and don't delete themselves. Thus
115 // there's no problem and the ABA tag is the same as the object pointer.
116 // ---------------------------------------------------------------------------
117 bool Compare(void* tag
) {
121 // ---------------------------------------------------------------------------
122 // Called with lock held.
123 // ---------------------------------------------------------------------------
128 // ---------------------------------------------------------------------------
129 // During a TimedWait, we need a way to make sure that an auto-reset
130 // WaitableEvent doesn't think that this event has been signaled between
131 // unlocking it and removing it from the wait-list. Called with lock held.
132 // ---------------------------------------------------------------------------
141 ConditionVariable
* cv() {
147 WaitableEvent
* signaling_event_
; // The WaitableEvent which woke us
149 ConditionVariable cv_
;
152 bool WaitableEvent::TimedWait(const TimeDelta
& max_time
) {
153 const Time
end_time(Time::Now() + max_time
);
154 const bool finite_time
= max_time
.ToInternalValue() >= 0;
156 kernel_
->lock_
.Acquire();
157 if (kernel_
->signaled_
) {
158 if (!kernel_
->manual_reset_
) {
159 // In this case we were signaled when we had no waiters. Now that
160 // someone has waited upon us, we can automatically reset.
161 kernel_
->signaled_
= false;
164 kernel_
->lock_
.Release();
169 sw
.lock()->Acquire();
172 kernel_
->lock_
.Release();
173 // We are violating locking order here by holding the SyncWaiter lock but not
174 // the WaitableEvent lock. However, this is safe because we don't lock @lock_
175 // again before unlocking it.
178 const Time
current_time(Time::Now());
180 if (sw
.fired() || (finite_time
&& current_time
>= end_time
)) {
181 const bool return_value
= sw
.fired();
183 // We can't acquire @lock_ before releasing the SyncWaiter lock (because
184 // of locking order), however, in between the two a signal could be fired
185 // and @sw would accept it, however we will still return false, so the
186 // signal would be lost on an auto-reset WaitableEvent. Thus we call
187 // Disable which makes sw::Fire return false.
189 sw
.lock()->Release();
191 kernel_
->lock_
.Acquire();
192 kernel_
->Dequeue(&sw
, &sw
);
193 kernel_
->lock_
.Release();
199 const TimeDelta
max_wait(end_time
- current_time
);
200 sw
.cv()->TimedWait(max_wait
);
207 bool WaitableEvent::Wait() {
208 return TimedWait(TimeDelta::FromSeconds(-1));
211 // -----------------------------------------------------------------------------
214 // -----------------------------------------------------------------------------
215 // Synchronous waiting on multiple objects.
217 static bool // StrictWeakOrdering
218 cmp_fst_addr(const std::pair
<WaitableEvent
*, unsigned> &a
,
219 const std::pair
<WaitableEvent
*, unsigned> &b
) {
220 return a
.first
< b
.first
;
224 size_t WaitableEvent::WaitMany(WaitableEvent
** raw_waitables
,
226 DCHECK(count
) << "Cannot wait on no events";
228 // We need to acquire the locks in a globally consistent order. Thus we sort
229 // the array of waitables by address. We actually sort a pairs so that we can
230 // map back to the original index values later.
231 std::vector
<std::pair
<WaitableEvent
*, size_t> > waitables
;
232 waitables
.reserve(count
);
233 for (size_t i
= 0; i
< count
; ++i
)
234 waitables
.push_back(std::make_pair(raw_waitables
[i
], i
));
236 DCHECK_EQ(count
, waitables
.size());
238 sort(waitables
.begin(), waitables
.end(), cmp_fst_addr
);
240 // The set of waitables must be distinct. Since we have just sorted by
241 // address, we can check this cheaply by comparing pairs of consecutive
243 for (size_t i
= 0; i
< waitables
.size() - 1; ++i
) {
244 DCHECK(waitables
[i
].first
!= waitables
[i
+1].first
);
249 const size_t r
= EnqueueMany(&waitables
[0], count
, &sw
);
251 // One of the events is already signaled. The SyncWaiter has not been
252 // enqueued anywhere. EnqueueMany returns the count of remaining waitables
253 // when the signaled one was seen, so the index of the signaled event is
255 return waitables
[count
- r
].second
;
258 // At this point, we hold the locks on all the WaitableEvents and we have
259 // enqueued our waiter in them all.
260 sw
.lock()->Acquire();
261 // Release the WaitableEvent locks in the reverse order
262 for (size_t i
= 0; i
< count
; ++i
) {
263 waitables
[count
- (1 + i
)].first
->kernel_
->lock_
.Release();
272 sw
.lock()->Release();
274 // The address of the WaitableEvent which fired is stored in the SyncWaiter.
275 WaitableEvent
*const signaled_event
= sw
.signaling_event();
276 // This will store the index of the raw_waitables which fired.
277 size_t signaled_index
= 0;
279 // Take the locks of each WaitableEvent in turn (except the signaled one) and
280 // remove our SyncWaiter from the wait-list
281 for (size_t i
= 0; i
< count
; ++i
) {
282 if (raw_waitables
[i
] != signaled_event
) {
283 raw_waitables
[i
]->kernel_
->lock_
.Acquire();
284 // There's no possible ABA issue with the address of the SyncWaiter here
285 // because it lives on the stack. Thus the tag value is just the pointer
287 raw_waitables
[i
]->kernel_
->Dequeue(&sw
, &sw
);
288 raw_waitables
[i
]->kernel_
->lock_
.Release();
294 return signaled_index
;
297 // -----------------------------------------------------------------------------
298 // If return value == 0:
299 // The locks of the WaitableEvents have been taken in order and the Waiter has
300 // been enqueued in the wait-list of each. None of the WaitableEvents are
301 // currently signaled
303 // None of the WaitableEvent locks are held. The Waiter has not been enqueued
304 // in any of them and the return value is the index of the first WaitableEvent
305 // which was signaled, from the end of the array.
306 // -----------------------------------------------------------------------------
308 size_t WaitableEvent::EnqueueMany
309 (std::pair
<WaitableEvent
*, size_t>* waitables
,
310 size_t count
, Waiter
* waiter
) {
314 waitables
[0].first
->kernel_
->lock_
.Acquire();
315 if (waitables
[0].first
->kernel_
->signaled_
) {
316 if (!waitables
[0].first
->kernel_
->manual_reset_
)
317 waitables
[0].first
->kernel_
->signaled_
= false;
318 waitables
[0].first
->kernel_
->lock_
.Release();
322 const size_t r
= EnqueueMany(waitables
+ 1, count
- 1, waiter
);
324 waitables
[0].first
->kernel_
->lock_
.Release();
326 waitables
[0].first
->Enqueue(waiter
);
332 // -----------------------------------------------------------------------------
335 // -----------------------------------------------------------------------------
336 // Private functions...
338 // -----------------------------------------------------------------------------
339 // Wake all waiting waiters. Called with lock held.
340 // -----------------------------------------------------------------------------
341 bool WaitableEvent::SignalAll() {
342 bool signaled_at_least_one
= false;
344 for (std::list
<Waiter
*>::iterator
345 i
= kernel_
->waiters_
.begin(); i
!= kernel_
->waiters_
.end(); ++i
) {
346 if ((*i
)->Fire(this))
347 signaled_at_least_one
= true;
350 kernel_
->waiters_
.clear();
351 return signaled_at_least_one
;
354 // ---------------------------------------------------------------------------
355 // Try to wake a single waiter. Return true if one was woken. Called with lock
357 // ---------------------------------------------------------------------------
358 bool WaitableEvent::SignalOne() {
360 if (kernel_
->waiters_
.empty())
363 const bool r
= (*kernel_
->waiters_
.begin())->Fire(this);
364 kernel_
->waiters_
.pop_front();
370 // -----------------------------------------------------------------------------
371 // Add a waiter to the list of those waiting. Called with lock held.
372 // -----------------------------------------------------------------------------
373 void WaitableEvent::Enqueue(Waiter
* waiter
) {
374 kernel_
->waiters_
.push_back(waiter
);
377 // -----------------------------------------------------------------------------
378 // Remove a waiter from the list of those waiting. Return true if the waiter was
379 // actually removed. Called with lock held.
380 // -----------------------------------------------------------------------------
381 bool WaitableEvent::WaitableEventKernel::Dequeue(Waiter
* waiter
, void* tag
) {
382 for (std::list
<Waiter
*>::iterator
383 i
= waiters_
.begin(); i
!= waiters_
.end(); ++i
) {
384 if (*i
== waiter
&& (*i
)->Compare(tag
)) {
393 // -----------------------------------------------------------------------------