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/condition_variable.h" 6 7 #include <stack> 8 9 #include "base/lock.h" 10 #include "base/logging.h" 11 #include "base/time.h" 12 13 using base::TimeDelta; 14 15 ConditionVariable::ConditionVariable(Lock* user_lock) 16 : user_lock_(*user_lock), 17 run_state_(RUNNING), 18 allocation_counter_(0), 19 recycling_list_size_(0) { 20 DCHECK(user_lock); 21 } 22 23 ConditionVariable::~ConditionVariable() { 24 AutoLock auto_lock(internal_lock_); 25 run_state_ = SHUTDOWN; // Prevent any more waiting. 26 27 DCHECK_EQ(recycling_list_size_, allocation_counter_); 28 if (recycling_list_size_ != allocation_counter_) { // Rare shutdown problem. 29 // There are threads of execution still in this->TimedWait() and yet the 30 // caller has instigated the destruction of this instance :-/. 31 // A common reason for such "overly hasty" destruction is that the caller 32 // was not willing to wait for all the threads to terminate. Such hasty 33 // actions are a violation of our usage contract, but we'll give the 34 // waiting thread(s) one last chance to exit gracefully (prior to our 35 // destruction). 36 // Note: waiting_list_ *might* be empty, but recycling is still pending. 37 AutoUnlock auto_unlock(internal_lock_); 38 Broadcast(); // Make sure all waiting threads have been signaled. 39 Sleep(10); // Give threads a chance to grab internal_lock_. 40 // All contained threads should be blocked on user_lock_ by now :-). 41 } // Reacquire internal_lock_. 42 43 DCHECK_EQ(recycling_list_size_, allocation_counter_); 44 } 45 46 void ConditionVariable::Wait() { 47 // Default to "wait forever" timing, which means have to get a Signal() 48 // or Broadcast() to come out of this wait state. 49 TimedWait(TimeDelta::FromMilliseconds(INFINITE)); 50 } 51 52 void ConditionVariable::TimedWait(const TimeDelta& max_time) { 53 Event* waiting_event; 54 HANDLE handle; 55 { 56 AutoLock auto_lock(internal_lock_); 57 if (RUNNING != run_state_) return; // Destruction in progress. 58 waiting_event = GetEventForWaiting(); 59 handle = waiting_event->handle(); 60 DCHECK(handle); 61 } // Release internal_lock. 62 63 { 64 AutoUnlock unlock(user_lock_); // Release caller's lock 65 WaitForSingleObject(handle, static_cast<DWORD>(max_time.InMilliseconds())); 66 // Minimize spurious signal creation window by recycling asap. 67 AutoLock auto_lock(internal_lock_); 68 RecycleEvent(waiting_event); 69 // Release internal_lock_ 70 } // Reacquire callers lock to depth at entry. 71 } 72 73 // Broadcast() is guaranteed to signal all threads that were waiting (i.e., had 74 // a cv_event internally allocated for them) before Broadcast() was called. 75 void ConditionVariable::Broadcast() { 76 std::stack<HANDLE> handles; // See FAQ-question-10. 77 { 78 AutoLock auto_lock(internal_lock_); 79 if (waiting_list_.IsEmpty()) 80 return; 81 while (!waiting_list_.IsEmpty()) 82 // This is not a leak from waiting_list_. See FAQ-question 12. 83 handles.push(waiting_list_.PopBack()->handle()); 84 } // Release internal_lock_. 85 while (!handles.empty()) { 86 SetEvent(handles.top()); 87 handles.pop(); 88 } 89 } 90 91 // Signal() will select one of the waiting threads, and signal it (signal its 92 // cv_event). For better performance we signal the thread that went to sleep 93 // most recently (LIFO). If we want fairness, then we wake the thread that has 94 // been sleeping the longest (FIFO). 95 void ConditionVariable::Signal() { 96 HANDLE handle; 97 { 98 AutoLock auto_lock(internal_lock_); 99 if (waiting_list_.IsEmpty()) 100 return; // No one to signal. 101 // Only performance option should be used. 102 // This is not a leak from waiting_list. See FAQ-question 12. 103 handle = waiting_list_.PopBack()->handle(); // LIFO. 104 } // Release internal_lock_. 105 SetEvent(handle); 106 } 107 108 // GetEventForWaiting() provides a unique cv_event for any caller that needs to 109 // wait. This means that (worst case) we may over time create as many cv_event 110 // objects as there are threads simultaneously using this instance's Wait() 111 // functionality. 112 ConditionVariable::Event* ConditionVariable::GetEventForWaiting() { 113 // We hold internal_lock, courtesy of Wait(). 114 Event* cv_event; 115 if (0 == recycling_list_size_) { 116 DCHECK(recycling_list_.IsEmpty()); 117 cv_event = new Event(); 118 cv_event->InitListElement(); 119 allocation_counter_++; 120 // CHECK_NE is not defined in our codebase, so we have to use CHECK 121 CHECK(cv_event->handle()); 122 } else { 123 cv_event = recycling_list_.PopFront(); 124 recycling_list_size_--; 125 } 126 waiting_list_.PushBack(cv_event); 127 return cv_event; 128 } 129 130 // RecycleEvent() takes a cv_event that was previously used for Wait()ing, and 131 // recycles it for use in future Wait() calls for this or other threads. 132 // Note that there is a tiny chance that the cv_event is still signaled when we 133 // obtain it, and that can cause spurious signals (if/when we re-use the 134 // cv_event), but such is quite rare (see FAQ-question-5). 135 void ConditionVariable::RecycleEvent(Event* used_event) { 136 // We hold internal_lock, courtesy of Wait(). 137 // If the cv_event timed out, then it is necessary to remove it from 138 // waiting_list_. If it was selected by Broadcast() or Signal(), then it is 139 // already gone. 140 used_event->Extract(); // Possibly redundant 141 recycling_list_.PushBack(used_event); 142 recycling_list_size_++; 143 } 144 //------------------------------------------------------------------------------ 145 // The next section provides the implementation for the private Event class. 146 //------------------------------------------------------------------------------ 147 148 // Event provides a doubly-linked-list of events for use exclusively by the 149 // ConditionVariable class. 150 151 // This custom container was crafted because no simple combination of STL 152 // classes appeared to support the functionality required. The specific 153 // unusual requirement for a linked-list-class is support for the Extract() 154 // method, which can remove an element from a list, potentially for insertion 155 // into a second list. Most critically, the Extract() method is idempotent, 156 // turning the indicated element into an extracted singleton whether it was 157 // contained in a list or not. This functionality allows one (or more) of 158 // threads to do the extraction. The iterator that identifies this extractable 159 // element (in this case, a pointer to the list element) can be used after 160 // arbitrary manipulation of the (possibly) enclosing list container. In 161 // general, STL containers do not provide iterators that can be used across 162 // modifications (insertions/extractions) of the enclosing containers, and 163 // certainly don't provide iterators that can be used if the identified 164 // element is *deleted* (removed) from the container. 165 166 // It is possible to use multiple redundant containers, such as an STL list, 167 // and an STL map, to achieve similar container semantics. This container has 168 // only O(1) methods, while the corresponding (multiple) STL container approach 169 // would have more complex O(log(N)) methods (yeah... N isn't that large). 170 // Multiple containers also makes correctness more difficult to assert, as 171 // data is redundantly stored and maintained, which is generally evil. 172 173 ConditionVariable::Event::Event() : handle_(0) { 174 next_ = prev_ = this; // Self referencing circular. 175 } 176 177 ConditionVariable::Event::~Event() { 178 if (0 == handle_) { 179 // This is the list holder 180 while (!IsEmpty()) { 181 Event* cv_event = PopFront(); 182 DCHECK(cv_event->ValidateAsItem()); 183 delete cv_event; 184 } 185 } 186 DCHECK(IsSingleton()); 187 if (0 != handle_) { 188 int ret_val = CloseHandle(handle_); 189 DCHECK(ret_val); 190 } 191 } 192 193 // Change a container instance permanently into an element of a list. 194 void ConditionVariable::Event::InitListElement() { 195 DCHECK(!handle_); 196 handle_ = CreateEvent(NULL, false, false, NULL); 197 CHECK(handle_); 198 } 199 200 // Methods for use on lists. 201 bool ConditionVariable::Event::IsEmpty() const { 202 DCHECK(ValidateAsList()); 203 return IsSingleton(); 204 } 205 206 void ConditionVariable::Event::PushBack(Event* other) { 207 DCHECK(ValidateAsList()); 208 DCHECK(other->ValidateAsItem()); 209 DCHECK(other->IsSingleton()); 210 // Prepare other for insertion. 211 other->prev_ = prev_; 212 other->next_ = this; 213 // Cut into list. 214 prev_->next_ = other; 215 prev_ = other; 216 DCHECK(ValidateAsDistinct(other)); 217 } 218 219 ConditionVariable::Event* ConditionVariable::Event::PopFront() { 220 DCHECK(ValidateAsList()); 221 DCHECK(!IsSingleton()); 222 return next_->Extract(); 223 } 224 225 ConditionVariable::Event* ConditionVariable::Event::PopBack() { 226 DCHECK(ValidateAsList()); 227 DCHECK(!IsSingleton()); 228 return prev_->Extract(); 229 } 230 231 // Methods for use on list elements. 232 // Accessor method. 233 HANDLE ConditionVariable::Event::handle() const { 234 DCHECK(ValidateAsItem()); 235 return handle_; 236 } 237 238 // Pull an element from a list (if it's in one). 239 ConditionVariable::Event* ConditionVariable::Event::Extract() { 240 DCHECK(ValidateAsItem()); 241 if (!IsSingleton()) { 242 // Stitch neighbors together. 243 next_->prev_ = prev_; 244 prev_->next_ = next_; 245 // Make extractee into a singleton. 246 prev_ = next_ = this; 247 } 248 DCHECK(IsSingleton()); 249 return this; 250 } 251 252 // Method for use on a list element or on a list. 253 bool ConditionVariable::Event::IsSingleton() const { 254 DCHECK(ValidateLinks()); 255 return next_ == this; 256 } 257 258 // Provide pre/post conditions to validate correct manipulations. 259 bool ConditionVariable::Event::ValidateAsDistinct(Event* other) const { 260 return ValidateLinks() && other->ValidateLinks() && (this != other); 261 } 262 263 bool ConditionVariable::Event::ValidateAsItem() const { 264 return (0 != handle_) && ValidateLinks(); 265 } 266 267 bool ConditionVariable::Event::ValidateAsList() const { 268 return (0 == handle_) && ValidateLinks(); 269 } 270 271 bool ConditionVariable::Event::ValidateLinks() const { 272 // Make sure both of our neighbors have links that point back to us. 273 // We don't do the O(n) check and traverse the whole loop, and instead only 274 // do a local check to (and returning from) our immediate neighbors. 275 return (next_->prev_ == this) && (prev_->next_ == this); 276 } 277 278 279 /* 280 FAQ On subtle implementation details: 281 282 1) What makes this problem subtle? Please take a look at "Strategies 283 for Implementing POSIX Condition Variables on Win32" by Douglas 284 C. Schmidt and Irfan Pyarali. 285 http://www.cs.wustl.edu/~schmidt/win32-cv-1.html It includes 286 discussions of numerous flawed strategies for implementing this 287 functionality. I'm not convinced that even the final proposed 288 implementation has semantics that are as nice as this implementation 289 (especially with regard to Broadcast() and the impact on threads that 290 try to Wait() after a Broadcast() has been called, but before all the 291 original waiting threads have been signaled). 292 293 2) Why can't you use a single wait_event for all threads that call 294 Wait()? See FAQ-question-1, or consider the following: If a single 295 event were used, then numerous threads calling Wait() could release 296 their cs locks, and be preempted just before calling 297 WaitForSingleObject(). If a call to Broadcast() was then presented on 298 a second thread, it would be impossible to actually signal all 299 waiting(?) threads. Some number of SetEvent() calls *could* be made, 300 but there could be no guarantee that those led to to more than one 301 signaled thread (SetEvent()'s may be discarded after the first!), and 302 there could be no guarantee that the SetEvent() calls didn't just 303 awaken "other" threads that hadn't even started waiting yet (oops). 304 Without any limit on the number of requisite SetEvent() calls, the 305 system would be forced to do many such calls, allowing many new waits 306 to receive spurious signals. 307 308 3) How does this implementation cause spurious signal events? The 309 cause in this implementation involves a race between a signal via 310 time-out and a signal via Signal() or Broadcast(). The series of 311 actions leading to this are: 312 313 a) Timer fires, and a waiting thread exits the line of code: 314 315 WaitForSingleObject(waiting_event, max_time.InMilliseconds()); 316 317 b) That thread (in (a)) is randomly pre-empted after the above line, 318 leaving the waiting_event reset (unsignaled) and still in the 319 waiting_list_. 320 321 c) A call to Signal() (or Broadcast()) on a second thread proceeds, and 322 selects the waiting cv_event (identified in step (b)) as the event to revive 323 via a call to SetEvent(). 324 325 d) The Signal() method (step c) calls SetEvent() on waiting_event (step b). 326 327 e) The waiting cv_event (step b) is now signaled, but no thread is 328 waiting on it. 329 330 f) When that waiting_event (step b) is reused, it will immediately 331 be signaled (spuriously). 332 333 334 4) Why do you recycle events, and cause spurious signals? First off, 335 the spurious events are very rare. They can only (I think) appear 336 when the race described in FAQ-question-3 takes place. This should be 337 very rare. Most(?) uses will involve only timer expiration, or only 338 Signal/Broadcast() actions. When both are used, it will be rare that 339 the race will appear, and it would require MANY Wait() and signaling 340 activities. If this implementation did not recycle events, then it 341 would have to create and destroy events for every call to Wait(). 342 That allocation/deallocation and associated construction/destruction 343 would be costly (per wait), and would only be a rare benefit (when the 344 race was "lost" and a spurious signal took place). That would be bad 345 (IMO) optimization trade-off. Finally, such spurious events are 346 allowed by the specification of condition variables (such as 347 implemented in Vista), and hence it is better if any user accommodates 348 such spurious events (see usage note in condition_variable.h). 349 350 5) Why don't you reset events when you are about to recycle them, or 351 about to reuse them, so that the spurious signals don't take place? 352 The thread described in FAQ-question-3 step c may be pre-empted for an 353 arbitrary length of time before proceeding to step d. As a result, 354 the wait_event may actually be re-used *before* step (e) is reached. 355 As a result, calling reset would not help significantly. 356 357 6) How is it that the callers lock is released atomically with the 358 entry into a wait state? We commit to the wait activity when we 359 allocate the wait_event for use in a given call to Wait(). This 360 allocation takes place before the caller's lock is released (and 361 actually before our internal_lock_ is released). That allocation is 362 the defining moment when "the wait state has been entered," as that 363 thread *can* now be signaled by a call to Broadcast() or Signal(). 364 Hence we actually "commit to wait" before releasing the lock, making 365 the pair effectively atomic. 366 367 8) Why do you need to lock your data structures during waiting, as the 368 caller is already in possession of a lock? We need to Acquire() and 369 Release() our internal lock during Signal() and Broadcast(). If we tried 370 to use a callers lock for this purpose, we might conflict with their 371 external use of the lock. For example, the caller may use to consistently 372 hold a lock on one thread while calling Signal() on another, and that would 373 block Signal(). 374 375 9) Couldn't a more efficient implementation be provided if you 376 preclude using more than one external lock in conjunction with a 377 single ConditionVariable instance? Yes, at least it could be viewed 378 as a simpler API (since you don't have to reiterate the lock argument 379 in each Wait() call). One of the constructors now takes a specific 380 lock as an argument, and a there are corresponding Wait() calls that 381 don't specify a lock now. It turns that the resulting implmentation 382 can't be made more efficient, as the internal lock needs to be used by 383 Signal() and Broadcast(), to access internal data structures. As a 384 result, I was not able to utilize the user supplied lock (which is 385 being used by the user elsewhere presumably) to protect the private 386 member access. 387 388 9) Since you have a second lock, how can be be sure that there is no 389 possible deadlock scenario? Our internal_lock_ is always the last 390 lock acquired, and the first one released, and hence a deadlock (due 391 to critical section problems) is impossible as a consequence of our 392 lock. 393 394 10) When doing a Broadcast(), why did you copy all the events into 395 an STL queue, rather than making a linked-loop, and iterating over it? 396 The iterating during Broadcast() is done so outside the protection 397 of the internal lock. As a result, other threads, such as the thread 398 wherein a related event is waiting, could asynchronously manipulate 399 the links around a cv_event. As a result, the link structure cannot 400 be used outside a lock. Broadcast() could iterate over waiting 401 events by cycling in-and-out of the protection of the internal_lock, 402 but that appears more expensive than copying the list into an STL 403 stack. 404 405 11) Why did the lock.h file need to be modified so much for this 406 change? Central to a Condition Variable is the atomic release of a 407 lock during a Wait(). This places Wait() functionality exactly 408 mid-way between the two classes, Lock and Condition Variable. Given 409 that there can be nested Acquire()'s of locks, and Wait() had to 410 Release() completely a held lock, it was necessary to augment the Lock 411 class with a recursion counter. Even more subtle is the fact that the 412 recursion counter (in a Lock) must be protected, as many threads can 413 access it asynchronously. As a positive fallout of this, there are 414 now some DCHECKS to be sure no one Release()s a Lock more than they 415 Acquire()ed it, and there is ifdef'ed functionality that can detect 416 nested locks (legal under windows, but not under Posix). 417 418 12) Why is it that the cv_events removed from list in Broadcast() and Signal() 419 are not leaked? How are they recovered?? The cv_events that appear to leak are 420 taken from the waiting_list_. For each element in that list, there is currently 421 a thread in or around the WaitForSingleObject() call of Wait(), and those 422 threads have references to these otherwise leaked events. They are passed as 423 arguments to be recycled just aftre returning from WaitForSingleObject(). 424 425 13) Why did you use a custom container class (the linked list), when STL has 426 perfectly good containers, such as an STL list? The STL list, as with any 427 container, does not guarantee the utility of an iterator across manipulation 428 (such as insertions and deletions) of the underlying container. The custom 429 double-linked-list container provided that assurance. I don't believe any 430 combination of STL containers provided the services that were needed at the same 431 O(1) efficiency as the custom linked list. The unusual requirement 432 for the container class is that a reference to an item within a container (an 433 iterator) needed to be maintained across an arbitrary manipulation of the 434 container. This requirement exposes itself in the Wait() method, where a 435 waiting_event must be selected prior to the WaitForSingleObject(), and then it 436 must be used as part of recycling to remove the related instance from the 437 waiting_list. A hash table (STL map) could be used, but I was embarrased to 438 use a complex and relatively low efficiency container when a doubly linked list 439 provided O(1) performance in all required operations. Since other operations 440 to provide performance-and/or-fairness required queue (FIFO) and list (LIFO) 441 containers, I would also have needed to use an STL list/queue as well as an STL 442 map. In the end I decided it would be "fun" to just do it right, and I 443 put so many assertions (DCHECKs) into the container class that it is trivial to 444 code review and validate its correctness. 445 446 */ 447