Line data Source code
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 : // -----------------------------------------------------------------------------
39 72 : WaitableEvent::WaitableEvent(bool manual_reset, bool initially_signaled)
40 72 : : kernel_(new WaitableEventKernel(manual_reset, initially_signaled)) {
41 72 : }
42 :
43 9 : WaitableEvent::~WaitableEvent() {
44 9 : }
45 :
46 0 : void WaitableEvent::Reset() {
47 0 : AutoLock locked(kernel_->lock_);
48 0 : kernel_->signaled_ = false;
49 0 : }
50 :
51 853 : void WaitableEvent::Signal() {
52 1663 : AutoLock locked(kernel_->lock_);
53 :
54 853 : if (kernel_->signaled_)
55 43 : return;
56 :
57 810 : if (kernel_->manual_reset_) {
58 0 : SignalAll();
59 0 : kernel_->signaled_ = true;
60 : } else {
61 : // In the case of auto reset, if no waiters were woken, we remain
62 : // signaled.
63 810 : if (!SignalOne())
64 557 : kernel_->signaled_ = true;
65 : }
66 : }
67 :
68 0 : bool WaitableEvent::IsSignaled() {
69 0 : AutoLock locked(kernel_->lock_);
70 :
71 0 : const bool result = kernel_->signaled_;
72 0 : if (result && !kernel_->manual_reset_)
73 0 : kernel_->signaled_ = false;
74 0 : return result;
75 : }
76 :
77 : // -----------------------------------------------------------------------------
78 : // Synchronous waits
79 :
80 : // -----------------------------------------------------------------------------
81 : // This is an synchronous waiter. The thread is waiting on the given condition
82 : // variable and the fired flag in this object.
83 : // -----------------------------------------------------------------------------
84 : class SyncWaiter : public WaitableEvent::Waiter {
85 : public:
86 777 : SyncWaiter(ConditionVariable* cv, Lock* lock)
87 777 : : fired_(false),
88 : cv_(cv),
89 : lock_(lock),
90 777 : signaling_event_(NULL) {
91 777 : }
92 :
93 253 : bool Fire(WaitableEvent *signaling_event) {
94 253 : lock_->Acquire();
95 253 : const bool previous_value = fired_;
96 253 : fired_ = true;
97 253 : if (!previous_value)
98 253 : signaling_event_ = signaling_event;
99 253 : lock_->Release();
100 :
101 253 : if (previous_value)
102 0 : return false;
103 :
104 253 : cv_->Broadcast();
105 :
106 : // SyncWaiters are stack allocated on the stack of the blocking thread.
107 253 : return true;
108 : }
109 :
110 0 : WaitableEvent* signaled_event() const {
111 0 : return signaling_event_;
112 : }
113 :
114 : // ---------------------------------------------------------------------------
115 : // These waiters are always stack allocated and don't delete themselves. Thus
116 : // there's no problem and the ABA tag is the same as the object pointer.
117 : // ---------------------------------------------------------------------------
118 523 : bool Compare(void* tag) {
119 523 : return this == tag;
120 : }
121 :
122 : // ---------------------------------------------------------------------------
123 : // Called with lock held.
124 : // ---------------------------------------------------------------------------
125 2333 : bool fired() const {
126 2333 : return fired_;
127 : }
128 :
129 : // ---------------------------------------------------------------------------
130 : // During a TimedWait, we need a way to make sure that an auto-reset
131 : // WaitableEvent doesn't think that this event has been signaled between
132 : // unlocking it and removing it from the wait-list. Called with lock held.
133 : // ---------------------------------------------------------------------------
134 776 : void Disable() {
135 776 : fired_ = true;
136 776 : }
137 :
138 : private:
139 : bool fired_;
140 : ConditionVariable *const cv_;
141 : Lock *const lock_;
142 : WaitableEvent* signaling_event_; // The WaitableEvent which woke us
143 : };
144 :
145 1338 : bool WaitableEvent::TimedWait(const TimeDelta& max_time) {
146 1338 : const TimeTicks end_time(TimeTicks::Now() + max_time);
147 1338 : const bool finite_time = max_time.ToInternalValue() >= 0;
148 :
149 1338 : kernel_->lock_.Acquire();
150 1338 : if (kernel_->signaled_) {
151 557 : if (!kernel_->manual_reset_) {
152 : // In this case we were signaled when we had no waiters. Now that
153 : // someone has waited upon us, we can automatically reset.
154 557 : kernel_->signaled_ = false;
155 : }
156 :
157 557 : kernel_->lock_.Release();
158 557 : return true;
159 : }
160 :
161 1557 : Lock lock;
162 781 : lock.Acquire();
163 1557 : ConditionVariable cv(&lock);
164 778 : SyncWaiter sw(&cv, &lock);
165 :
166 778 : Enqueue(&sw);
167 781 : kernel_->lock_.Release();
168 : // We are violating locking order here by holding the SyncWaiter lock but not
169 : // the WaitableEvent lock. However, this is safe because we don't lock @lock_
170 : // again before unlocking it.
171 :
172 : for (;;) {
173 1557 : const TimeTicks current_time(TimeTicks::Now());
174 :
175 1557 : if (sw.fired() || (finite_time && current_time >= end_time)) {
176 776 : const bool return_value = sw.fired();
177 :
178 : // We can't acquire @lock_ before releasing @lock (because of locking
179 : // order), however, inbetween the two a signal could be fired and @sw
180 : // would accept it, however we will still return false, so the signal
181 : // would be lost on an auto-reset WaitableEvent. Thus we call Disable
182 : // which makes sw::Fire return false.
183 776 : sw.Disable();
184 776 : lock.Release();
185 :
186 776 : kernel_->lock_.Acquire();
187 776 : kernel_->Dequeue(&sw, &sw);
188 776 : kernel_->lock_.Release();
189 :
190 776 : return return_value;
191 : }
192 :
193 781 : if (finite_time) {
194 527 : const TimeDelta max_wait(end_time - current_time);
195 527 : cv.TimedWait(max_wait);
196 : } else {
197 254 : cv.Wait();
198 : }
199 776 : }
200 : }
201 :
202 288 : bool WaitableEvent::Wait() {
203 288 : return TimedWait(TimeDelta::FromSeconds(-1));
204 : }
205 :
206 : // -----------------------------------------------------------------------------
207 :
208 :
209 : // -----------------------------------------------------------------------------
210 : // Synchronous waiting on multiple objects.
211 :
212 : static bool // StrictWeakOrdering
213 0 : cmp_fst_addr(const std::pair<WaitableEvent*, unsigned> &a,
214 : const std::pair<WaitableEvent*, unsigned> &b) {
215 0 : return a.first < b.first;
216 : }
217 :
218 : // static
219 0 : size_t WaitableEvent::WaitMany(WaitableEvent** raw_waitables,
220 : size_t count) {
221 0 : DCHECK(count) << "Cannot wait on no events";
222 :
223 : // We need to acquire the locks in a globally consistent order. Thus we sort
224 : // the array of waitables by address. We actually sort a pairs so that we can
225 : // map back to the original index values later.
226 0 : std::vector<std::pair<WaitableEvent*, size_t> > waitables;
227 0 : waitables.reserve(count);
228 0 : for (size_t i = 0; i < count; ++i)
229 0 : waitables.push_back(std::make_pair(raw_waitables[i], i));
230 :
231 0 : DCHECK_EQ(count, waitables.size());
232 :
233 0 : sort(waitables.begin(), waitables.end(), cmp_fst_addr);
234 :
235 : // The set of waitables must be distinct. Since we have just sorted by
236 : // address, we can check this cheaply by comparing pairs of consecutive
237 : // elements.
238 0 : for (size_t i = 0; i < waitables.size() - 1; ++i) {
239 0 : DCHECK(waitables[i].first != waitables[i+1].first);
240 : }
241 :
242 0 : Lock lock;
243 0 : ConditionVariable cv(&lock);
244 0 : SyncWaiter sw(&cv, &lock);
245 :
246 0 : const size_t r = EnqueueMany(&waitables[0], count, &sw);
247 0 : if (r) {
248 : // One of the events is already signaled. The SyncWaiter has not been
249 : // enqueued anywhere. EnqueueMany returns the count of remaining waitables
250 : // when the signaled one was seen, so the index of the signaled event is
251 : // @count - @r.
252 0 : return waitables[count - r].second;
253 : }
254 :
255 : // At this point, we hold the locks on all the WaitableEvents and we have
256 : // enqueued our waiter in them all.
257 0 : lock.Acquire();
258 : // Release the WaitableEvent locks in the reverse order
259 0 : for (size_t i = 0; i < count; ++i) {
260 0 : waitables[count - (1 + i)].first->kernel_->lock_.Release();
261 : }
262 :
263 : for (;;) {
264 0 : if (sw.fired())
265 0 : break;
266 :
267 0 : cv.Wait();
268 : }
269 0 : lock.Release();
270 :
271 : // The address of the WaitableEvent which fired is stored in the SyncWaiter.
272 0 : WaitableEvent *const signaled_event = sw.signaled_event();
273 : // This will store the index of the raw_waitables which fired.
274 0 : size_t signaled_index = 0;
275 :
276 : // Take the locks of each WaitableEvent in turn (except the signaled one) and
277 : // remove our SyncWaiter from the wait-list
278 0 : for (size_t i = 0; i < count; ++i) {
279 0 : if (raw_waitables[i] != signaled_event) {
280 0 : raw_waitables[i]->kernel_->lock_.Acquire();
281 : // There's no possible ABA issue with the address of the SyncWaiter here
282 : // because it lives on the stack. Thus the tag value is just the pointer
283 : // value again.
284 0 : raw_waitables[i]->kernel_->Dequeue(&sw, &sw);
285 0 : raw_waitables[i]->kernel_->lock_.Release();
286 : } else {
287 0 : signaled_index = i;
288 : }
289 : }
290 :
291 0 : return signaled_index;
292 : }
293 :
294 : // -----------------------------------------------------------------------------
295 : // If return value == 0:
296 : // The locks of the WaitableEvents have been taken in order and the Waiter has
297 : // been enqueued in the wait-list of each. None of the WaitableEvents are
298 : // currently signaled
299 : // else:
300 : // None of the WaitableEvent locks are held. The Waiter has not been enqueued
301 : // in any of them and the return value is the index of the first WaitableEvent
302 : // which was signaled, from the end of the array.
303 : // -----------------------------------------------------------------------------
304 : // static
305 0 : size_t WaitableEvent::EnqueueMany
306 : (std::pair<WaitableEvent*, size_t>* waitables,
307 : size_t count, Waiter* waiter) {
308 0 : if (!count)
309 0 : return 0;
310 :
311 0 : waitables[0].first->kernel_->lock_.Acquire();
312 0 : if (waitables[0].first->kernel_->signaled_) {
313 0 : if (!waitables[0].first->kernel_->manual_reset_)
314 0 : waitables[0].first->kernel_->signaled_ = false;
315 0 : waitables[0].first->kernel_->lock_.Release();
316 0 : return count;
317 : }
318 :
319 0 : const size_t r = EnqueueMany(waitables + 1, count - 1, waiter);
320 0 : if (r) {
321 0 : waitables[0].first->kernel_->lock_.Release();
322 : } else {
323 0 : waitables[0].first->Enqueue(waiter);
324 : }
325 :
326 0 : return r;
327 : }
328 :
329 : // -----------------------------------------------------------------------------
330 :
331 :
332 : // -----------------------------------------------------------------------------
333 : // Private functions...
334 :
335 : // -----------------------------------------------------------------------------
336 : // Wake all waiting waiters. Called with lock held.
337 : // -----------------------------------------------------------------------------
338 0 : bool WaitableEvent::SignalAll() {
339 0 : bool signaled_at_least_one = false;
340 :
341 0 : for (std::list<Waiter*>::iterator
342 0 : i = kernel_->waiters_.begin(); i != kernel_->waiters_.end(); ++i) {
343 0 : if ((*i)->Fire(this))
344 0 : signaled_at_least_one = true;
345 : }
346 :
347 0 : kernel_->waiters_.clear();
348 0 : return signaled_at_least_one;
349 : }
350 :
351 : // ---------------------------------------------------------------------------
352 : // Try to wake a single waiter. Return true if one was woken. Called with lock
353 : // held.
354 : // ---------------------------------------------------------------------------
355 810 : bool WaitableEvent::SignalOne() {
356 : for (;;) {
357 810 : if (kernel_->waiters_.empty())
358 557 : return false;
359 :
360 253 : const bool r = (*kernel_->waiters_.begin())->Fire(this);
361 253 : kernel_->waiters_.pop_front();
362 253 : if (r)
363 253 : return true;
364 0 : }
365 : }
366 :
367 : // -----------------------------------------------------------------------------
368 : // Add a waiter to the list of those waiting. Called with lock held.
369 : // -----------------------------------------------------------------------------
370 778 : void WaitableEvent::Enqueue(Waiter* waiter) {
371 778 : kernel_->waiters_.push_back(waiter);
372 781 : }
373 :
374 : // -----------------------------------------------------------------------------
375 : // Remove a waiter from the list of those waiting. Return true if the waiter was
376 : // actually removed. Called with lock held.
377 : // -----------------------------------------------------------------------------
378 776 : bool WaitableEvent::WaitableEventKernel::Dequeue(Waiter* waiter, void* tag) {
379 1552 : for (std::list<Waiter*>::iterator
380 1552 : i = waiters_.begin(); i != waiters_.end(); ++i) {
381 523 : if (*i == waiter && (*i)->Compare(tag)) {
382 523 : waiters_.erase(i);
383 523 : return true;
384 : }
385 : }
386 :
387 253 : return false;
388 : }
389 :
390 : // -----------------------------------------------------------------------------
391 :
392 : } // namespace base
|
