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