| OLD | NEW |
|---|
| (Empty) |
| 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. | |
| 4 | |
| 5 #include <algorithm> | |
| 6 #include <vector> | |
| 7 | |
| 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" | |
| 13 | |
| 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. | |
| 19 // | |
| 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. | |
| 24 // | |
| 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. | |
| 28 // | |
| 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 // ----------------------------------------------------------------------------- | |
| 34 | |
| 35 namespace base { | |
| 36 | |
| 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)) { | |
| 42 } | |
| 43 | |
| 44 WaitableEvent::~WaitableEvent() { | |
| 45 } | |
| 46 | |
| 47 void WaitableEvent::Reset() { | |
| 48 base::AutoLock locked(kernel_->lock_); | |
| 49 kernel_->signaled_ = false; | |
| 50 } | |
| 51 | |
| 52 void WaitableEvent::Signal() { | |
| 53 base::AutoLock locked(kernel_->lock_); | |
| 54 | |
| 55 if (kernel_->signaled_) | |
| 56 return; | |
| 57 | |
| 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; | |
| 66 } | |
| 67 } | |
| 68 | |
| 69 bool WaitableEvent::IsSignaled() { | |
| 70 base::AutoLock locked(kernel_->lock_); | |
| 71 | |
| 72 const bool result = kernel_->signaled_; | |
| 73 if (result && !kernel_->manual_reset_) | |
| 74 kernel_->signaled_ = false; | |
| 75 return result; | |
| 76 } | |
| 77 | |
| 78 // ----------------------------------------------------------------------------- | |
| 79 // Synchronous waits | |
| 80 | |
| 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_) { | |
| 92 } | |
| 93 | |
| 94 bool Fire(WaitableEvent* signaling_event) override { | |
| 95 base::AutoLock locked(lock_); | |
| 96 | |
| 97 if (fired_) | |
| 98 return false; | |
| 99 | |
| 100 fired_ = true; | |
| 101 signaling_event_ = signaling_event; | |
| 102 | |
| 103 cv_.Broadcast(); | |
| 104 | |
| 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. | |
| 108 | |
| 109 return true; | |
| 110 } | |
| 111 | |
| 112 WaitableEvent* signaling_event() const { | |
| 113 return signaling_event_; | |
| 114 } | |
| 115 | |
| 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 bool Compare(void* tag) override { return this == tag; } | |
| 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 base::Lock* lock() { | |
| 139 return &lock_; | |
| 140 } | |
| 141 | |
| 142 base::ConditionVariable* cv() { | |
| 143 return &cv_; | |
| 144 } | |
| 145 | |
| 146 private: | |
| 147 bool fired_; | |
| 148 WaitableEvent* signaling_event_; // The WaitableEvent which woke us | |
| 149 base::Lock lock_; | |
| 150 base::ConditionVariable cv_; | |
| 151 }; | |
| 152 | |
| 153 void WaitableEvent::Wait() { | |
| 154 bool result = TimedWait(TimeDelta::FromSeconds(-1)); | |
| 155 DCHECK(result) << "TimedWait() should never fail with infinite timeout"; | |
| 156 } | |
| 157 | |
| 158 bool WaitableEvent::TimedWait(const TimeDelta& max_time) { | |
| 159 base::ThreadRestrictions::AssertWaitAllowed(); | |
| 160 const TimeTicks end_time(TimeTicks::Now() + max_time); | |
| 161 const bool finite_time = max_time.ToInternalValue() >= 0; | |
| 162 | |
| 163 kernel_->lock_.Acquire(); | |
| 164 if (kernel_->signaled_) { | |
| 165 if (!kernel_->manual_reset_) { | |
| 166 // In this case we were signaled when we had no waiters. Now that | |
| 167 // someone has waited upon us, we can automatically reset. | |
| 168 kernel_->signaled_ = false; | |
| 169 } | |
| 170 | |
| 171 kernel_->lock_.Release(); | |
| 172 return true; | |
| 173 } | |
| 174 | |
| 175 SyncWaiter sw; | |
| 176 sw.lock()->Acquire(); | |
| 177 | |
| 178 Enqueue(&sw); | |
| 179 kernel_->lock_.Release(); | |
| 180 // We are violating locking order here by holding the SyncWaiter lock but not | |
| 181 // the WaitableEvent lock. However, this is safe because we don't lock @lock_ | |
| 182 // again before unlocking it. | |
| 183 | |
| 184 for (;;) { | |
| 185 const TimeTicks current_time(TimeTicks::Now()); | |
| 186 | |
| 187 if (sw.fired() || (finite_time && current_time >= end_time)) { | |
| 188 const bool return_value = sw.fired(); | |
| 189 | |
| 190 // We can't acquire @lock_ before releasing the SyncWaiter lock (because | |
| 191 // of locking order), however, in between the two a signal could be fired | |
| 192 // and @sw would accept it, however we will still return false, so the | |
| 193 // signal would be lost on an auto-reset WaitableEvent. Thus we call | |
| 194 // Disable which makes sw::Fire return false. | |
| 195 sw.Disable(); | |
| 196 sw.lock()->Release(); | |
| 197 | |
| 198 // This is a bug that has been enshrined in the interface of | |
| 199 // WaitableEvent now: |Dequeue| is called even when |sw.fired()| is true, | |
| 200 // even though it'll always return false in that case. However, taking | |
| 201 // the lock ensures that |Signal| has completed before we return and | |
| 202 // means that a WaitableEvent can synchronise its own destruction. | |
| 203 kernel_->lock_.Acquire(); | |
| 204 kernel_->Dequeue(&sw, &sw); | |
| 205 kernel_->lock_.Release(); | |
| 206 | |
| 207 return return_value; | |
| 208 } | |
| 209 | |
| 210 if (finite_time) { | |
| 211 const TimeDelta max_wait(end_time - current_time); | |
| 212 sw.cv()->TimedWait(max_wait); | |
| 213 } else { | |
| 214 sw.cv()->Wait(); | |
| 215 } | |
| 216 } | |
| 217 } | |
| 218 | |
| 219 // ----------------------------------------------------------------------------- | |
| 220 // Synchronous waiting on multiple objects. | |
| 221 | |
| 222 static bool // StrictWeakOrdering | |
| 223 cmp_fst_addr(const std::pair<WaitableEvent*, unsigned> &a, | |
| 224 const std::pair<WaitableEvent*, unsigned> &b) { | |
| 225 return a.first < b.first; | |
| 226 } | |
| 227 | |
| 228 // static | |
| 229 size_t WaitableEvent::WaitMany(WaitableEvent** raw_waitables, | |
| 230 size_t count) { | |
| 231 base::ThreadRestrictions::AssertWaitAllowed(); | |
| 232 DCHECK(count) << "Cannot wait on no events"; | |
| 233 | |
| 234 // We need to acquire the locks in a globally consistent order. Thus we sort | |
| 235 // the array of waitables by address. We actually sort a pairs so that we can | |
| 236 // map back to the original index values later. | |
| 237 std::vector<std::pair<WaitableEvent*, size_t> > waitables; | |
| 238 waitables.reserve(count); | |
| 239 for (size_t i = 0; i < count; ++i) | |
| 240 waitables.push_back(std::make_pair(raw_waitables[i], i)); | |
| 241 | |
| 242 DCHECK_EQ(count, waitables.size()); | |
| 243 | |
| 244 sort(waitables.begin(), waitables.end(), cmp_fst_addr); | |
| 245 | |
| 246 // The set of waitables must be distinct. Since we have just sorted by | |
| 247 // address, we can check this cheaply by comparing pairs of consecutive | |
| 248 // elements. | |
| 249 for (size_t i = 0; i < waitables.size() - 1; ++i) { | |
| 250 DCHECK(waitables[i].first != waitables[i+1].first); | |
| 251 } | |
| 252 | |
| 253 SyncWaiter sw; | |
| 254 | |
| 255 const size_t r = EnqueueMany(&waitables[0], count, &sw); | |
| 256 if (r) { | |
| 257 // One of the events is already signaled. The SyncWaiter has not been | |
| 258 // enqueued anywhere. EnqueueMany returns the count of remaining waitables | |
| 259 // when the signaled one was seen, so the index of the signaled event is | |
| 260 // @count - @r. | |
| 261 return waitables[count - r].second; | |
| 262 } | |
| 263 | |
| 264 // At this point, we hold the locks on all the WaitableEvents and we have | |
| 265 // enqueued our waiter in them all. | |
| 266 sw.lock()->Acquire(); | |
| 267 // Release the WaitableEvent locks in the reverse order | |
| 268 for (size_t i = 0; i < count; ++i) { | |
| 269 waitables[count - (1 + i)].first->kernel_->lock_.Release(); | |
| 270 } | |
| 271 | |
| 272 for (;;) { | |
| 273 if (sw.fired()) | |
| 274 break; | |
| 275 | |
| 276 sw.cv()->Wait(); | |
| 277 } | |
| 278 sw.lock()->Release(); | |
| 279 | |
| 280 // The address of the WaitableEvent which fired is stored in the SyncWaiter. | |
| 281 WaitableEvent *const signaled_event = sw.signaling_event(); | |
| 282 // This will store the index of the raw_waitables which fired. | |
| 283 size_t signaled_index = 0; | |
| 284 | |
| 285 // Take the locks of each WaitableEvent in turn (except the signaled one) and | |
| 286 // remove our SyncWaiter from the wait-list | |
| 287 for (size_t i = 0; i < count; ++i) { | |
| 288 if (raw_waitables[i] != signaled_event) { | |
| 289 raw_waitables[i]->kernel_->lock_.Acquire(); | |
| 290 // There's no possible ABA issue with the address of the SyncWaiter here | |
| 291 // because it lives on the stack. Thus the tag value is just the pointer | |
| 292 // value again. | |
| 293 raw_waitables[i]->kernel_->Dequeue(&sw, &sw); | |
| 294 raw_waitables[i]->kernel_->lock_.Release(); | |
| 295 } else { | |
| 296 // By taking this lock here we ensure that |Signal| has completed by the | |
| 297 // time we return, because |Signal| holds this lock. This matches the | |
| 298 // behaviour of |Wait| and |TimedWait|. | |
| 299 raw_waitables[i]->kernel_->lock_.Acquire(); | |
| 300 raw_waitables[i]->kernel_->lock_.Release(); | |
| 301 signaled_index = i; | |
| 302 } | |
| 303 } | |
| 304 | |
| 305 return signaled_index; | |
| 306 } | |
| 307 | |
| 308 // ----------------------------------------------------------------------------- | |
| 309 // If return value == 0: | |
| 310 // The locks of the WaitableEvents have been taken in order and the Waiter has | |
| 311 // been enqueued in the wait-list of each. None of the WaitableEvents are | |
| 312 // currently signaled | |
| 313 // else: | |
| 314 // None of the WaitableEvent locks are held. The Waiter has not been enqueued | |
| 315 // in any of them and the return value is the index of the first WaitableEvent | |
| 316 // which was signaled, from the end of the array. | |
| 317 // ----------------------------------------------------------------------------- | |
| 318 // static | |
| 319 size_t WaitableEvent::EnqueueMany | |
| 320 (std::pair<WaitableEvent*, size_t>* waitables, | |
| 321 size_t count, Waiter* waiter) { | |
| 322 if (!count) | |
| 323 return 0; | |
| 324 | |
| 325 waitables[0].first->kernel_->lock_.Acquire(); | |
| 326 if (waitables[0].first->kernel_->signaled_) { | |
| 327 if (!waitables[0].first->kernel_->manual_reset_) | |
| 328 waitables[0].first->kernel_->signaled_ = false; | |
| 329 waitables[0].first->kernel_->lock_.Release(); | |
| 330 return count; | |
| 331 } | |
| 332 | |
| 333 const size_t r = EnqueueMany(waitables + 1, count - 1, waiter); | |
| 334 if (r) { | |
| 335 waitables[0].first->kernel_->lock_.Release(); | |
| 336 } else { | |
| 337 waitables[0].first->Enqueue(waiter); | |
| 338 } | |
| 339 | |
| 340 return r; | |
| 341 } | |
| 342 | |
| 343 // ----------------------------------------------------------------------------- | |
| 344 | |
| 345 | |
| 346 // ----------------------------------------------------------------------------- | |
| 347 // Private functions... | |
| 348 | |
| 349 WaitableEvent::WaitableEventKernel::WaitableEventKernel(bool manual_reset, | |
| 350 bool initially_signaled) | |
| 351 : manual_reset_(manual_reset), | |
| 352 signaled_(initially_signaled) { | |
| 353 } | |
| 354 | |
| 355 WaitableEvent::WaitableEventKernel::~WaitableEventKernel() { | |
| 356 } | |
| 357 | |
| 358 // ----------------------------------------------------------------------------- | |
| 359 // Wake all waiting waiters. Called with lock held. | |
| 360 // ----------------------------------------------------------------------------- | |
| 361 bool WaitableEvent::SignalAll() { | |
| 362 bool signaled_at_least_one = false; | |
| 363 | |
| 364 for (std::list<Waiter*>::iterator | |
| 365 i = kernel_->waiters_.begin(); i != kernel_->waiters_.end(); ++i) { | |
| 366 if ((*i)->Fire(this)) | |
| 367 signaled_at_least_one = true; | |
| 368 } | |
| 369 | |
| 370 kernel_->waiters_.clear(); | |
| 371 return signaled_at_least_one; | |
| 372 } | |
| 373 | |
| 374 // --------------------------------------------------------------------------- | |
| 375 // Try to wake a single waiter. Return true if one was woken. Called with lock | |
| 376 // held. | |
| 377 // --------------------------------------------------------------------------- | |
| 378 bool WaitableEvent::SignalOne() { | |
| 379 for (;;) { | |
| 380 if (kernel_->waiters_.empty()) | |
| 381 return false; | |
| 382 | |
| 383 const bool r = (*kernel_->waiters_.begin())->Fire(this); | |
| 384 kernel_->waiters_.pop_front(); | |
| 385 if (r) | |
| 386 return true; | |
| 387 } | |
| 388 } | |
| 389 | |
| 390 // ----------------------------------------------------------------------------- | |
| 391 // Add a waiter to the list of those waiting. Called with lock held. | |
| 392 // ----------------------------------------------------------------------------- | |
| 393 void WaitableEvent::Enqueue(Waiter* waiter) { | |
| 394 kernel_->waiters_.push_back(waiter); | |
| 395 } | |
| 396 | |
| 397 // ----------------------------------------------------------------------------- | |
| 398 // Remove a waiter from the list of those waiting. Return true if the waiter was | |
| 399 // actually removed. Called with lock held. | |
| 400 // ----------------------------------------------------------------------------- | |
| 401 bool WaitableEvent::WaitableEventKernel::Dequeue(Waiter* waiter, void* tag) { | |
| 402 for (std::list<Waiter*>::iterator | |
| 403 i = waiters_.begin(); i != waiters_.end(); ++i) { | |
| 404 if (*i == waiter && (*i)->Compare(tag)) { | |
| 405 waiters_.erase(i); | |
| 406 return true; | |
| 407 } | |
| 408 } | |
| 409 | |
| 410 return false; | |
| 411 } | |
| 412 | |
| 413 // ----------------------------------------------------------------------------- | |
| 414 | |
| 415 } // namespace base | |
| OLD | NEW |
|---|
Chromium Code Reviews
