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