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