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 <stddef.h> 6 7 #include <algorithm> 8 #include <limits> 9 #include <vector> 10 11 #include "base/debug/activity_tracker.h" 12 #include "base/logging.h" 13 #include "base/synchronization/condition_variable.h" 14 #include "base/synchronization/lock.h" 15 #include "base/synchronization/waitable_event.h" 16 #include "base/threading/thread_restrictions.h" 17 18 // ----------------------------------------------------------------------------- 19 // A WaitableEvent on POSIX is implemented as a wait-list. Currently we don't 20 // support cross-process events (where one process can signal an event which 21 // others are waiting on). Because of this, we can avoid having one thread per 22 // listener in several cases. 23 // 24 // The WaitableEvent maintains a list of waiters, protected by a lock. Each 25 // waiter is either an async wait, in which case we have a Task and the 26 // MessageLoop to run it on, or a blocking wait, in which case we have the 27 // condition variable to signal. 28 // 29 // Waiting involves grabbing the lock and adding oneself to the wait list. Async 30 // waits can be canceled, which means grabbing the lock and removing oneself 31 // from the list. 32 // 33 // Waiting on multiple events is handled by adding a single, synchronous wait to 34 // the wait-list of many events. An event passes a pointer to itself when 35 // firing a waiter and so we can store that pointer to find out which event 36 // triggered. 37 // ----------------------------------------------------------------------------- 38 39 namespace base { 40 41 // ----------------------------------------------------------------------------- 42 // This is just an abstract base class for waking the two types of waiters 43 // ----------------------------------------------------------------------------- 44 WaitableEvent::WaitableEvent(ResetPolicy reset_policy, 45 InitialState initial_state) 46 : kernel_(new WaitableEventKernel(reset_policy, initial_state)) {} 47 48 WaitableEvent::~WaitableEvent() = default; 49 50 void WaitableEvent::Reset() { 51 base::AutoLock locked(kernel_->lock_); 52 kernel_->signaled_ = false; 53 } 54 55 void WaitableEvent::Signal() { 56 base::AutoLock locked(kernel_->lock_); 57 58 if (kernel_->signaled_) 59 return; 60 61 if (kernel_->manual_reset_) { 62 SignalAll(); 63 kernel_->signaled_ = true; 64 } else { 65 // In the case of auto reset, if no waiters were woken, we remain 66 // signaled. 67 if (!SignalOne()) 68 kernel_->signaled_ = true; 69 } 70 } 71 72 bool WaitableEvent::IsSignaled() { 73 base::AutoLock locked(kernel_->lock_); 74 75 const bool result = kernel_->signaled_; 76 if (result && !kernel_->manual_reset_) 77 kernel_->signaled_ = false; 78 return result; 79 } 80 81 // ----------------------------------------------------------------------------- 82 // Synchronous waits 83 84 // ----------------------------------------------------------------------------- 85 // This is a synchronous waiter. The thread is waiting on the given condition 86 // variable and the fired flag in this object. 87 // ----------------------------------------------------------------------------- 88 class SyncWaiter : public WaitableEvent::Waiter { 89 public: 90 SyncWaiter() 91 : fired_(false), 92 signaling_event_(NULL), 93 lock_(), 94 cv_(&lock_) { 95 } 96 97 bool Fire(WaitableEvent* signaling_event) override { 98 base::AutoLock locked(lock_); 99 100 if (fired_) 101 return false; 102 103 fired_ = true; 104 signaling_event_ = signaling_event; 105 106 cv_.Broadcast(); 107 108 // Unlike AsyncWaiter objects, SyncWaiter objects are stack-allocated on 109 // the blocking thread's stack. There is no |delete this;| in Fire. The 110 // SyncWaiter object is destroyed when it goes out of scope. 111 112 return true; 113 } 114 115 WaitableEvent* signaling_event() const { 116 return signaling_event_; 117 } 118 119 // --------------------------------------------------------------------------- 120 // These waiters are always stack allocated and don't delete themselves. Thus 121 // there's no problem and the ABA tag is the same as the object pointer. 122 // --------------------------------------------------------------------------- 123 bool Compare(void* tag) override { return this == tag; } 124 125 // --------------------------------------------------------------------------- 126 // Called with lock held. 127 // --------------------------------------------------------------------------- 128 bool fired() const { 129 return fired_; 130 } 131 132 // --------------------------------------------------------------------------- 133 // During a TimedWait, we need a way to make sure that an auto-reset 134 // WaitableEvent doesn't think that this event has been signaled between 135 // unlocking it and removing it from the wait-list. Called with lock held. 136 // --------------------------------------------------------------------------- 137 void Disable() { 138 fired_ = true; 139 } 140 141 base::Lock* lock() { 142 return &lock_; 143 } 144 145 base::ConditionVariable* cv() { 146 return &cv_; 147 } 148 149 private: 150 bool fired_; 151 WaitableEvent* signaling_event_; // The WaitableEvent which woke us 152 base::Lock lock_; 153 base::ConditionVariable cv_; 154 }; 155 156 void WaitableEvent::Wait() { 157 bool result = TimedWaitUntil(TimeTicks::Max()); 158 DCHECK(result) << "TimedWait() should never fail with infinite timeout"; 159 } 160 161 bool WaitableEvent::TimedWait(const TimeDelta& wait_delta) { 162 // TimeTicks takes care of overflow including the cases when wait_delta 163 // is a maximum value. 164 return TimedWaitUntil(TimeTicks::Now() + wait_delta); 165 } 166 167 bool WaitableEvent::TimedWaitUntil(const TimeTicks& end_time) { 168 base::ThreadRestrictions::AssertWaitAllowed(); 169 // Record the event that this thread is blocking upon (for hang diagnosis). 170 base::debug::ScopedEventWaitActivity event_activity(this); 171 172 const bool finite_time = !end_time.is_max(); 173 174 kernel_->lock_.Acquire(); 175 if (kernel_->signaled_) { 176 if (!kernel_->manual_reset_) { 177 // In this case we were signaled when we had no waiters. Now that 178 // someone has waited upon us, we can automatically reset. 179 kernel_->signaled_ = false; 180 } 181 182 kernel_->lock_.Release(); 183 return true; 184 } 185 186 SyncWaiter sw; 187 sw.lock()->Acquire(); 188 189 Enqueue(&sw); 190 kernel_->lock_.Release(); 191 // We are violating locking order here by holding the SyncWaiter lock but not 192 // the WaitableEvent lock. However, this is safe because we don't lock @lock_ 193 // again before unlocking it. 194 195 for (;;) { 196 const TimeTicks current_time(TimeTicks::Now()); 197 198 if (sw.fired() || (finite_time && current_time >= end_time)) { 199 const bool return_value = sw.fired(); 200 201 // We can't acquire @lock_ before releasing the SyncWaiter lock (because 202 // of locking order), however, in between the two a signal could be fired 203 // and @sw would accept it, however we will still return false, so the 204 // signal would be lost on an auto-reset WaitableEvent. Thus we call 205 // Disable which makes sw::Fire return false. 206 sw.Disable(); 207 sw.lock()->Release(); 208 209 // This is a bug that has been enshrined in the interface of 210 // WaitableEvent now: |Dequeue| is called even when |sw.fired()| is true, 211 // even though it'll always return false in that case. However, taking 212 // the lock ensures that |Signal| has completed before we return and 213 // means that a WaitableEvent can synchronise its own destruction. 214 kernel_->lock_.Acquire(); 215 kernel_->Dequeue(&sw, &sw); 216 kernel_->lock_.Release(); 217 218 return return_value; 219 } 220 221 if (finite_time) { 222 const TimeDelta max_wait(end_time - current_time); 223 sw.cv()->TimedWait(max_wait); 224 } else { 225 sw.cv()->Wait(); 226 } 227 } 228 } 229 230 // ----------------------------------------------------------------------------- 231 // Synchronous waiting on multiple objects. 232 233 static bool // StrictWeakOrdering 234 cmp_fst_addr(const std::pair<WaitableEvent*, unsigned> &a, 235 const std::pair<WaitableEvent*, unsigned> &b) { 236 return a.first < b.first; 237 } 238 239 // static 240 size_t WaitableEvent::WaitMany(WaitableEvent** raw_waitables, 241 size_t count) { 242 base::ThreadRestrictions::AssertWaitAllowed(); 243 DCHECK(count) << "Cannot wait on no events"; 244 245 // Record an event (the first) that this thread is blocking upon. 246 base::debug::ScopedEventWaitActivity event_activity(raw_waitables[0]); 247 248 // We need to acquire the locks in a globally consistent order. Thus we sort 249 // the array of waitables by address. We actually sort a pairs so that we can 250 // map back to the original index values later. 251 std::vector<std::pair<WaitableEvent*, size_t> > waitables; 252 waitables.reserve(count); 253 for (size_t i = 0; i < count; ++i) 254 waitables.push_back(std::make_pair(raw_waitables[i], i)); 255 256 DCHECK_EQ(count, waitables.size()); 257 258 sort(waitables.begin(), waitables.end(), cmp_fst_addr); 259 260 // The set of waitables must be distinct. Since we have just sorted by 261 // address, we can check this cheaply by comparing pairs of consecutive 262 // elements. 263 for (size_t i = 0; i < waitables.size() - 1; ++i) { 264 DCHECK(waitables[i].first != waitables[i+1].first); 265 } 266 267 SyncWaiter sw; 268 269 const size_t r = EnqueueMany(&waitables[0], count, &sw); 270 if (r < count) { 271 // One of the events is already signaled. The SyncWaiter has not been 272 // enqueued anywhere. 273 return waitables[r].second; 274 } 275 276 // At this point, we hold the locks on all the WaitableEvents and we have 277 // enqueued our waiter in them all. 278 sw.lock()->Acquire(); 279 // Release the WaitableEvent locks in the reverse order 280 for (size_t i = 0; i < count; ++i) { 281 waitables[count - (1 + i)].first->kernel_->lock_.Release(); 282 } 283 284 for (;;) { 285 if (sw.fired()) 286 break; 287 288 sw.cv()->Wait(); 289 } 290 sw.lock()->Release(); 291 292 // The address of the WaitableEvent which fired is stored in the SyncWaiter. 293 WaitableEvent *const signaled_event = sw.signaling_event(); 294 // This will store the index of the raw_waitables which fired. 295 size_t signaled_index = 0; 296 297 // Take the locks of each WaitableEvent in turn (except the signaled one) and 298 // remove our SyncWaiter from the wait-list 299 for (size_t i = 0; i < count; ++i) { 300 if (raw_waitables[i] != signaled_event) { 301 raw_waitables[i]->kernel_->lock_.Acquire(); 302 // There's no possible ABA issue with the address of the SyncWaiter here 303 // because it lives on the stack. Thus the tag value is just the pointer 304 // value again. 305 raw_waitables[i]->kernel_->Dequeue(&sw, &sw); 306 raw_waitables[i]->kernel_->lock_.Release(); 307 } else { 308 // By taking this lock here we ensure that |Signal| has completed by the 309 // time we return, because |Signal| holds this lock. This matches the 310 // behaviour of |Wait| and |TimedWait|. 311 raw_waitables[i]->kernel_->lock_.Acquire(); 312 raw_waitables[i]->kernel_->lock_.Release(); 313 signaled_index = i; 314 } 315 } 316 317 return signaled_index; 318 } 319 320 // ----------------------------------------------------------------------------- 321 // If return value == count: 322 // The locks of the WaitableEvents have been taken in order and the Waiter has 323 // been enqueued in the wait-list of each. None of the WaitableEvents are 324 // currently signaled 325 // else: 326 // None of the WaitableEvent locks are held. The Waiter has not been enqueued 327 // in any of them and the return value is the index of the WaitableEvent which 328 // was signaled with the lowest input index from the original WaitMany call. 329 // ----------------------------------------------------------------------------- 330 // static 331 size_t WaitableEvent::EnqueueMany(std::pair<WaitableEvent*, size_t>* waitables, 332 size_t count, 333 Waiter* waiter) { 334 size_t winner = count; 335 size_t winner_index = count; 336 for (size_t i = 0; i < count; ++i) { 337 auto& kernel = waitables[i].first->kernel_; 338 kernel->lock_.Acquire(); 339 if (kernel->signaled_ && waitables[i].second < winner) { 340 winner = waitables[i].second; 341 winner_index = i; 342 } 343 } 344 345 // No events signaled. All locks acquired. Enqueue the Waiter on all of them 346 // and return. 347 if (winner == count) { 348 for (size_t i = 0; i < count; ++i) 349 waitables[i].first->Enqueue(waiter); 350 return count; 351 } 352 353 // Unlock in reverse order and possibly clear the chosen winner's signal 354 // before returning its index. 355 for (auto* w = waitables + count - 1; w >= waitables; --w) { 356 auto& kernel = w->first->kernel_; 357 if (w->second == winner) { 358 if (!kernel->manual_reset_) 359 kernel->signaled_ = false; 360 } 361 kernel->lock_.Release(); 362 } 363 364 return winner_index; 365 } 366 367 // ----------------------------------------------------------------------------- 368 369 370 // ----------------------------------------------------------------------------- 371 // Private functions... 372 373 WaitableEvent::WaitableEventKernel::WaitableEventKernel( 374 ResetPolicy reset_policy, 375 InitialState initial_state) 376 : manual_reset_(reset_policy == ResetPolicy::MANUAL), 377 signaled_(initial_state == InitialState::SIGNALED) {} 378 379 WaitableEvent::WaitableEventKernel::~WaitableEventKernel() = default; 380 381 // ----------------------------------------------------------------------------- 382 // Wake all waiting waiters. Called with lock held. 383 // ----------------------------------------------------------------------------- 384 bool WaitableEvent::SignalAll() { 385 bool signaled_at_least_one = false; 386 387 for (std::list<Waiter*>::iterator 388 i = kernel_->waiters_.begin(); i != kernel_->waiters_.end(); ++i) { 389 if ((*i)->Fire(this)) 390 signaled_at_least_one = true; 391 } 392 393 kernel_->waiters_.clear(); 394 return signaled_at_least_one; 395 } 396 397 // --------------------------------------------------------------------------- 398 // Try to wake a single waiter. Return true if one was woken. Called with lock 399 // held. 400 // --------------------------------------------------------------------------- 401 bool WaitableEvent::SignalOne() { 402 for (;;) { 403 if (kernel_->waiters_.empty()) 404 return false; 405 406 const bool r = (*kernel_->waiters_.begin())->Fire(this); 407 kernel_->waiters_.pop_front(); 408 if (r) 409 return true; 410 } 411 } 412 413 // ----------------------------------------------------------------------------- 414 // Add a waiter to the list of those waiting. Called with lock held. 415 // ----------------------------------------------------------------------------- 416 void WaitableEvent::Enqueue(Waiter* waiter) { 417 kernel_->waiters_.push_back(waiter); 418 } 419 420 // ----------------------------------------------------------------------------- 421 // Remove a waiter from the list of those waiting. Return true if the waiter was 422 // actually removed. Called with lock held. 423 // ----------------------------------------------------------------------------- 424 bool WaitableEvent::WaitableEventKernel::Dequeue(Waiter* waiter, void* tag) { 425 for (std::list<Waiter*>::iterator 426 i = waiters_.begin(); i != waiters_.end(); ++i) { 427 if (*i == waiter && (*i)->Compare(tag)) { 428 waiters_.erase(i); 429 return true; 430 } 431 } 432 433 return false; 434 } 435 436 // ----------------------------------------------------------------------------- 437 438 } // namespace base 439