OLD | NEW |
(Empty) | |
| 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. |
| 4 |
| 5 #include "base/waitable_event.h" |
| 6 |
| 7 #include "base/condition_variable.h" |
| 8 #include "base/lock.h" |
| 9 #include "base/message_loop.h" |
| 10 |
| 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. |
| 16 // |
| 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. |
| 21 // |
| 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 |
| 24 // from the list. |
| 25 // |
| 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 |
| 29 // triggered. |
| 30 // ----------------------------------------------------------------------------- |
| 31 |
| 32 namespace base { |
| 33 |
| 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 : signaled_(false), |
| 39 manual_reset_(manual_reset) { |
| 40 DCHECK(!initially_signaled) << "Not implemented"; |
| 41 } |
| 42 |
| 43 WaitableEvent::~WaitableEvent() { |
| 44 DCHECK(waiters_.empty()) << "Deleting WaitableEvent with listeners!"; |
| 45 } |
| 46 |
| 47 void WaitableEvent::Reset() { |
| 48 AutoLock locked(lock_); |
| 49 signaled_ = false; |
| 50 } |
| 51 |
| 52 void WaitableEvent::Signal() { |
| 53 AutoLock locked(lock_); |
| 54 |
| 55 if (signaled_) |
| 56 return; |
| 57 |
| 58 if (manual_reset_) { |
| 59 SignalAll(); |
| 60 signaled_ = true; |
| 61 } else { |
| 62 // In the case of auto reset, if no waiters were woken, we remain |
| 63 // signaled. |
| 64 if (!SignalOne()) |
| 65 signaled_ = true; |
| 66 } |
| 67 } |
| 68 |
| 69 bool WaitableEvent::IsSignaled() { |
| 70 AutoLock locked(lock_); |
| 71 |
| 72 const bool result = signaled_; |
| 73 if (result && !manual_reset_) |
| 74 signaled_ = false; |
| 75 return result; |
| 76 } |
| 77 |
| 78 // ----------------------------------------------------------------------------- |
| 79 // Synchronous waits |
| 80 |
| 81 // ----------------------------------------------------------------------------- |
| 82 // This is an 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(ConditionVariable* cv, Lock* lock) |
| 88 : fired_(false), |
| 89 cv_(cv), |
| 90 lock_(lock), |
| 91 signaling_event_(NULL) { } |
| 92 |
| 93 bool Fire(WaitableEvent *signaling_event) { |
| 94 lock_->Acquire(); |
| 95 const bool previous_value = fired_; |
| 96 fired_ = true; |
| 97 if (!previous_value) |
| 98 signaling_event_ = signaling_event; |
| 99 lock_->Release(); |
| 100 |
| 101 if (previous_value) |
| 102 return false; |
| 103 |
| 104 cv_->Broadcast(); |
| 105 |
| 106 // SyncWaiters are stack allocated on the stack of the blocking thread. |
| 107 return true; |
| 108 } |
| 109 |
| 110 WaitableEvent* signaled_event() const { |
| 111 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 bool Compare(void* tag) { |
| 119 return this == tag; |
| 120 } |
| 121 |
| 122 // --------------------------------------------------------------------------- |
| 123 // Called with lock held. |
| 124 // --------------------------------------------------------------------------- |
| 125 bool fired() const { |
| 126 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 void Disable() { |
| 135 fired_ = true; |
| 136 } |
| 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 bool WaitableEvent::TimedWait(const TimeDelta& max_time) { |
| 146 const Time end_time(Time::Now() + max_time); |
| 147 |
| 148 lock_.Acquire(); |
| 149 if (signaled_) { |
| 150 if (!manual_reset_) { |
| 151 // In this case we were signaled when we had no waiters. Now that |
| 152 // someone has waited upon us, we can automatically reset. |
| 153 signaled_ = false; |
| 154 } |
| 155 |
| 156 lock_.Release(); |
| 157 return true; |
| 158 } |
| 159 |
| 160 Lock lock; |
| 161 lock.Acquire(); |
| 162 ConditionVariable cv(&lock); |
| 163 SyncWaiter sw(&cv, &lock); |
| 164 |
| 165 Enqueue(&sw); |
| 166 lock_.Release(); |
| 167 // We are violating locking order here by holding the SyncWaiter lock but not |
| 168 // the WaitableEvent lock. However, this is safe because we don't lock @lock_ |
| 169 // again before unlocking it. |
| 170 |
| 171 for (;;) { |
| 172 if (sw.fired()) { |
| 173 lock.Release(); |
| 174 return true; |
| 175 } |
| 176 |
| 177 if (max_time.ToInternalValue() < 0) { |
| 178 cv.Wait(); |
| 179 } else { |
| 180 const Time current_time(Time::Now()); |
| 181 if (current_time >= end_time) { |
| 182 // We can't acquire @lock_ before releasing @lock (because of locking |
| 183 // order), however, inbetween the two a signal could be fired and @sw |
| 184 // would accept it, however we will still return false, so the signal |
| 185 // would be lost on an auto-reset WaitableEvent. Thus we call Disable |
| 186 // which makes sw::Fire return false. |
| 187 sw.Disable(); |
| 188 lock.Release(); |
| 189 |
| 190 lock_.Acquire(); |
| 191 Dequeue(&sw, &sw); |
| 192 lock_.Release(); |
| 193 return false; |
| 194 } |
| 195 const TimeDelta max_wait(end_time - current_time); |
| 196 |
| 197 cv.TimedWait(max_wait); |
| 198 } |
| 199 } |
| 200 } |
| 201 |
| 202 bool WaitableEvent::Wait() { |
| 203 return TimedWait(TimeDelta::FromSeconds(-1)); |
| 204 } |
| 205 |
| 206 // ----------------------------------------------------------------------------- |
| 207 |
| 208 |
| 209 // ----------------------------------------------------------------------------- |
| 210 // Synchronous waiting on multiple objects. |
| 211 |
| 212 static bool // StrictWeakOrdering |
| 213 cmp_fst_addr(const std::pair<WaitableEvent*, unsigned> &a, |
| 214 const std::pair<WaitableEvent*, unsigned> &b) { |
| 215 return a.first < b.first; |
| 216 } |
| 217 |
| 218 // static |
| 219 size_t WaitableEvent::WaitMany(WaitableEvent** raw_waitables, |
| 220 size_t count) { |
| 221 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 std::vector<std::pair<WaitableEvent*, size_t> > waitables; |
| 227 waitables.reserve(count); |
| 228 for (size_t i = 0; i < count; ++i) |
| 229 waitables.push_back(std::make_pair(raw_waitables[i], i)); |
| 230 |
| 231 DCHECK_EQ(count, waitables.size()); |
| 232 |
| 233 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 for (size_t i = 0; i < waitables.size() - 1; ++i) { |
| 239 DCHECK(waitables[i].first != waitables[i+1].first); |
| 240 } |
| 241 |
| 242 Lock lock; |
| 243 ConditionVariable cv(&lock); |
| 244 SyncWaiter sw(&cv, &lock); |
| 245 |
| 246 const size_t r = EnqueueMany(&waitables[0], count, &sw); |
| 247 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 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 lock.Acquire(); |
| 258 // Release the WaitableEvent locks in the reverse order |
| 259 for (size_t i = 0; i < count; ++i) { |
| 260 waitables[count - (1 + i)].first->lock_.Release(); |
| 261 } |
| 262 |
| 263 for (;;) { |
| 264 if (sw.fired()) |
| 265 break; |
| 266 |
| 267 cv.Wait(); |
| 268 } |
| 269 lock.Release(); |
| 270 |
| 271 // The address of the WaitableEvent which fired is stored in the SyncWaiter. |
| 272 WaitableEvent *const signaled_event = sw.signaled_event(); |
| 273 // This will store the index of the raw_waitables which fired. |
| 274 size_t signaled_index; |
| 275 |
| 276 // Take the locks of each WaitableEvent in turn (except the signaled one) and |
| 277 // remove our SyncWaiter from the wait-list |
| 278 for (size_t i = 0; i < count; ++i) { |
| 279 if (raw_waitables[i] != signaled_event) { |
| 280 raw_waitables[i]->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 raw_waitables[i]->Dequeue(&sw, &sw); |
| 285 raw_waitables[i]->lock_.Release(); |
| 286 } else { |
| 287 signaled_index = i; |
| 288 } |
| 289 } |
| 290 |
| 291 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 unsigned WaitableEvent::EnqueueMany |
| 306 (std::pair<WaitableEvent*, unsigned>* waitables, |
| 307 unsigned count, Waiter* waiter) { |
| 308 if (!count) |
| 309 return 0; |
| 310 |
| 311 waitables[0].first->lock_.Acquire(); |
| 312 if (waitables[0].first->signaled_) { |
| 313 if (!waitables[0].first->manual_reset_) |
| 314 waitables[0].first->signaled_ = false; |
| 315 waitables[0].first->lock_.Release(); |
| 316 return count; |
| 317 } |
| 318 |
| 319 const unsigned r = EnqueueMany(waitables + 1, count - 1, waiter); |
| 320 if (r) { |
| 321 waitables[0].first->lock_.Release(); |
| 322 } else { |
| 323 waitables[0].first->Enqueue(waiter); |
| 324 } |
| 325 |
| 326 return r; |
| 327 } |
| 328 |
| 329 // ----------------------------------------------------------------------------- |
| 330 |
| 331 |
| 332 // ----------------------------------------------------------------------------- |
| 333 // Private functions... |
| 334 |
| 335 // ----------------------------------------------------------------------------- |
| 336 // Wake all waiting waiters. Called with lock held. |
| 337 // ----------------------------------------------------------------------------- |
| 338 bool WaitableEvent::SignalAll() { |
| 339 bool signaled_at_least_one = false; |
| 340 |
| 341 for (std::list<Waiter*>::iterator |
| 342 i = waiters_.begin(); i != waiters_.end(); ++i) { |
| 343 if ((*i)->Fire(this)) |
| 344 signaled_at_least_one = true; |
| 345 } |
| 346 |
| 347 waiters_.clear(); |
| 348 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 bool WaitableEvent::SignalOne() { |
| 356 for (;;) { |
| 357 if (waiters_.empty()) |
| 358 return false; |
| 359 |
| 360 const bool r = (*waiters_.begin())->Fire(this); |
| 361 waiters_.pop_front(); |
| 362 if (r) |
| 363 return true; |
| 364 } |
| 365 } |
| 366 |
| 367 // ----------------------------------------------------------------------------- |
| 368 // Add a waiter to the list of those waiting. Called with lock held. |
| 369 // ----------------------------------------------------------------------------- |
| 370 void WaitableEvent::Enqueue(Waiter* waiter) { |
| 371 waiters_.push_back(waiter); |
| 372 } |
| 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 bool WaitableEvent::Dequeue(Waiter* waiter, void* tag) { |
| 379 for (std::list<Waiter*>::iterator |
| 380 i = waiters_.begin(); i != waiters_.end(); ++i) { |
| 381 if (*i == waiter && (*i)->Compare(tag)) { |
| 382 waiters_.erase(i); |
| 383 return true; |
| 384 } |
| 385 } |
| 386 |
| 387 return false; |
| 388 } |
| 389 |
| 390 // ----------------------------------------------------------------------------- |
| 391 |
| 392 } // namespace base |
OLD | NEW |