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