1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/ipc/chromium/src/base/condition_variable_win.cc Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,446 @@
1.4 +// Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
1.5 +// Use of this source code is governed by a BSD-style license that can be
1.6 +// found in the LICENSE file.
1.7 +
1.8 +#include "base/condition_variable.h"
1.9 +
1.10 +#include <stack>
1.11 +
1.12 +#include "base/lock.h"
1.13 +#include "base/logging.h"
1.14 +#include "base/time.h"
1.15 +
1.16 +using base::TimeDelta;
1.17 +
1.18 +ConditionVariable::ConditionVariable(Lock* user_lock)
1.19 + : user_lock_(*user_lock),
1.20 + run_state_(RUNNING),
1.21 + allocation_counter_(0),
1.22 + recycling_list_size_(0) {
1.23 + DCHECK(user_lock);
1.24 +}
1.25 +
1.26 +ConditionVariable::~ConditionVariable() {
1.27 + AutoLock auto_lock(internal_lock_);
1.28 + run_state_ = SHUTDOWN; // Prevent any more waiting.
1.29 +
1.30 + DCHECK_EQ(recycling_list_size_, allocation_counter_);
1.31 + if (recycling_list_size_ != allocation_counter_) { // Rare shutdown problem.
1.32 + // There are threads of execution still in this->TimedWait() and yet the
1.33 + // caller has instigated the destruction of this instance :-/.
1.34 + // A common reason for such "overly hasty" destruction is that the caller
1.35 + // was not willing to wait for all the threads to terminate. Such hasty
1.36 + // actions are a violation of our usage contract, but we'll give the
1.37 + // waiting thread(s) one last chance to exit gracefully (prior to our
1.38 + // destruction).
1.39 + // Note: waiting_list_ *might* be empty, but recycling is still pending.
1.40 + AutoUnlock auto_unlock(internal_lock_);
1.41 + Broadcast(); // Make sure all waiting threads have been signaled.
1.42 + Sleep(10); // Give threads a chance to grab internal_lock_.
1.43 + // All contained threads should be blocked on user_lock_ by now :-).
1.44 + } // Reacquire internal_lock_.
1.45 +
1.46 + DCHECK_EQ(recycling_list_size_, allocation_counter_);
1.47 +}
1.48 +
1.49 +void ConditionVariable::Wait() {
1.50 + // Default to "wait forever" timing, which means have to get a Signal()
1.51 + // or Broadcast() to come out of this wait state.
1.52 + TimedWait(TimeDelta::FromMilliseconds(INFINITE));
1.53 +}
1.54 +
1.55 +void ConditionVariable::TimedWait(const TimeDelta& max_time) {
1.56 + Event* waiting_event;
1.57 + HANDLE handle;
1.58 + {
1.59 + AutoLock auto_lock(internal_lock_);
1.60 + if (RUNNING != run_state_) return; // Destruction in progress.
1.61 + waiting_event = GetEventForWaiting();
1.62 + handle = waiting_event->handle();
1.63 + DCHECK(handle);
1.64 + } // Release internal_lock.
1.65 +
1.66 + {
1.67 + AutoUnlock unlock(user_lock_); // Release caller's lock
1.68 + WaitForSingleObject(handle, static_cast<DWORD>(max_time.InMilliseconds()));
1.69 + // Minimize spurious signal creation window by recycling asap.
1.70 + AutoLock auto_lock(internal_lock_);
1.71 + RecycleEvent(waiting_event);
1.72 + // Release internal_lock_
1.73 + } // Reacquire callers lock to depth at entry.
1.74 +}
1.75 +
1.76 +// Broadcast() is guaranteed to signal all threads that were waiting (i.e., had
1.77 +// a cv_event internally allocated for them) before Broadcast() was called.
1.78 +void ConditionVariable::Broadcast() {
1.79 + std::stack<HANDLE> handles; // See FAQ-question-10.
1.80 + {
1.81 + AutoLock auto_lock(internal_lock_);
1.82 + if (waiting_list_.IsEmpty())
1.83 + return;
1.84 + while (!waiting_list_.IsEmpty())
1.85 + // This is not a leak from waiting_list_. See FAQ-question 12.
1.86 + handles.push(waiting_list_.PopBack()->handle());
1.87 + } // Release internal_lock_.
1.88 + while (!handles.empty()) {
1.89 + SetEvent(handles.top());
1.90 + handles.pop();
1.91 + }
1.92 +}
1.93 +
1.94 +// Signal() will select one of the waiting threads, and signal it (signal its
1.95 +// cv_event). For better performance we signal the thread that went to sleep
1.96 +// most recently (LIFO). If we want fairness, then we wake the thread that has
1.97 +// been sleeping the longest (FIFO).
1.98 +void ConditionVariable::Signal() {
1.99 + HANDLE handle;
1.100 + {
1.101 + AutoLock auto_lock(internal_lock_);
1.102 + if (waiting_list_.IsEmpty())
1.103 + return; // No one to signal.
1.104 + // Only performance option should be used.
1.105 + // This is not a leak from waiting_list. See FAQ-question 12.
1.106 + handle = waiting_list_.PopBack()->handle(); // LIFO.
1.107 + } // Release internal_lock_.
1.108 + SetEvent(handle);
1.109 +}
1.110 +
1.111 +// GetEventForWaiting() provides a unique cv_event for any caller that needs to
1.112 +// wait. This means that (worst case) we may over time create as many cv_event
1.113 +// objects as there are threads simultaneously using this instance's Wait()
1.114 +// functionality.
1.115 +ConditionVariable::Event* ConditionVariable::GetEventForWaiting() {
1.116 + // We hold internal_lock, courtesy of Wait().
1.117 + Event* cv_event;
1.118 + if (0 == recycling_list_size_) {
1.119 + DCHECK(recycling_list_.IsEmpty());
1.120 + cv_event = new Event();
1.121 + cv_event->InitListElement();
1.122 + allocation_counter_++;
1.123 + // CHECK_NE is not defined in our codebase, so we have to use CHECK
1.124 + CHECK(cv_event->handle());
1.125 + } else {
1.126 + cv_event = recycling_list_.PopFront();
1.127 + recycling_list_size_--;
1.128 + }
1.129 + waiting_list_.PushBack(cv_event);
1.130 + return cv_event;
1.131 +}
1.132 +
1.133 +// RecycleEvent() takes a cv_event that was previously used for Wait()ing, and
1.134 +// recycles it for use in future Wait() calls for this or other threads.
1.135 +// Note that there is a tiny chance that the cv_event is still signaled when we
1.136 +// obtain it, and that can cause spurious signals (if/when we re-use the
1.137 +// cv_event), but such is quite rare (see FAQ-question-5).
1.138 +void ConditionVariable::RecycleEvent(Event* used_event) {
1.139 + // We hold internal_lock, courtesy of Wait().
1.140 + // If the cv_event timed out, then it is necessary to remove it from
1.141 + // waiting_list_. If it was selected by Broadcast() or Signal(), then it is
1.142 + // already gone.
1.143 + used_event->Extract(); // Possibly redundant
1.144 + recycling_list_.PushBack(used_event);
1.145 + recycling_list_size_++;
1.146 +}
1.147 +//------------------------------------------------------------------------------
1.148 +// The next section provides the implementation for the private Event class.
1.149 +//------------------------------------------------------------------------------
1.150 +
1.151 +// Event provides a doubly-linked-list of events for use exclusively by the
1.152 +// ConditionVariable class.
1.153 +
1.154 +// This custom container was crafted because no simple combination of STL
1.155 +// classes appeared to support the functionality required. The specific
1.156 +// unusual requirement for a linked-list-class is support for the Extract()
1.157 +// method, which can remove an element from a list, potentially for insertion
1.158 +// into a second list. Most critically, the Extract() method is idempotent,
1.159 +// turning the indicated element into an extracted singleton whether it was
1.160 +// contained in a list or not. This functionality allows one (or more) of
1.161 +// threads to do the extraction. The iterator that identifies this extractable
1.162 +// element (in this case, a pointer to the list element) can be used after
1.163 +// arbitrary manipulation of the (possibly) enclosing list container. In
1.164 +// general, STL containers do not provide iterators that can be used across
1.165 +// modifications (insertions/extractions) of the enclosing containers, and
1.166 +// certainly don't provide iterators that can be used if the identified
1.167 +// element is *deleted* (removed) from the container.
1.168 +
1.169 +// It is possible to use multiple redundant containers, such as an STL list,
1.170 +// and an STL map, to achieve similar container semantics. This container has
1.171 +// only O(1) methods, while the corresponding (multiple) STL container approach
1.172 +// would have more complex O(log(N)) methods (yeah... N isn't that large).
1.173 +// Multiple containers also makes correctness more difficult to assert, as
1.174 +// data is redundantly stored and maintained, which is generally evil.
1.175 +
1.176 +ConditionVariable::Event::Event() : handle_(0) {
1.177 + next_ = prev_ = this; // Self referencing circular.
1.178 +}
1.179 +
1.180 +ConditionVariable::Event::~Event() {
1.181 + if (0 == handle_) {
1.182 + // This is the list holder
1.183 + while (!IsEmpty()) {
1.184 + Event* cv_event = PopFront();
1.185 + DCHECK(cv_event->ValidateAsItem());
1.186 + delete cv_event;
1.187 + }
1.188 + }
1.189 + DCHECK(IsSingleton());
1.190 + if (0 != handle_) {
1.191 + int ret_val = CloseHandle(handle_);
1.192 + DCHECK(ret_val);
1.193 + }
1.194 +}
1.195 +
1.196 +// Change a container instance permanently into an element of a list.
1.197 +void ConditionVariable::Event::InitListElement() {
1.198 + DCHECK(!handle_);
1.199 + handle_ = CreateEvent(NULL, false, false, NULL);
1.200 + CHECK(handle_);
1.201 +}
1.202 +
1.203 +// Methods for use on lists.
1.204 +bool ConditionVariable::Event::IsEmpty() const {
1.205 + DCHECK(ValidateAsList());
1.206 + return IsSingleton();
1.207 +}
1.208 +
1.209 +void ConditionVariable::Event::PushBack(Event* other) {
1.210 + DCHECK(ValidateAsList());
1.211 + DCHECK(other->ValidateAsItem());
1.212 + DCHECK(other->IsSingleton());
1.213 + // Prepare other for insertion.
1.214 + other->prev_ = prev_;
1.215 + other->next_ = this;
1.216 + // Cut into list.
1.217 + prev_->next_ = other;
1.218 + prev_ = other;
1.219 + DCHECK(ValidateAsDistinct(other));
1.220 +}
1.221 +
1.222 +ConditionVariable::Event* ConditionVariable::Event::PopFront() {
1.223 + DCHECK(ValidateAsList());
1.224 + DCHECK(!IsSingleton());
1.225 + return next_->Extract();
1.226 +}
1.227 +
1.228 +ConditionVariable::Event* ConditionVariable::Event::PopBack() {
1.229 + DCHECK(ValidateAsList());
1.230 + DCHECK(!IsSingleton());
1.231 + return prev_->Extract();
1.232 +}
1.233 +
1.234 +// Methods for use on list elements.
1.235 +// Accessor method.
1.236 +HANDLE ConditionVariable::Event::handle() const {
1.237 + DCHECK(ValidateAsItem());
1.238 + return handle_;
1.239 +}
1.240 +
1.241 +// Pull an element from a list (if it's in one).
1.242 +ConditionVariable::Event* ConditionVariable::Event::Extract() {
1.243 + DCHECK(ValidateAsItem());
1.244 + if (!IsSingleton()) {
1.245 + // Stitch neighbors together.
1.246 + next_->prev_ = prev_;
1.247 + prev_->next_ = next_;
1.248 + // Make extractee into a singleton.
1.249 + prev_ = next_ = this;
1.250 + }
1.251 + DCHECK(IsSingleton());
1.252 + return this;
1.253 +}
1.254 +
1.255 +// Method for use on a list element or on a list.
1.256 +bool ConditionVariable::Event::IsSingleton() const {
1.257 + DCHECK(ValidateLinks());
1.258 + return next_ == this;
1.259 +}
1.260 +
1.261 +// Provide pre/post conditions to validate correct manipulations.
1.262 +bool ConditionVariable::Event::ValidateAsDistinct(Event* other) const {
1.263 + return ValidateLinks() && other->ValidateLinks() && (this != other);
1.264 +}
1.265 +
1.266 +bool ConditionVariable::Event::ValidateAsItem() const {
1.267 + return (0 != handle_) && ValidateLinks();
1.268 +}
1.269 +
1.270 +bool ConditionVariable::Event::ValidateAsList() const {
1.271 + return (0 == handle_) && ValidateLinks();
1.272 +}
1.273 +
1.274 +bool ConditionVariable::Event::ValidateLinks() const {
1.275 + // Make sure both of our neighbors have links that point back to us.
1.276 + // We don't do the O(n) check and traverse the whole loop, and instead only
1.277 + // do a local check to (and returning from) our immediate neighbors.
1.278 + return (next_->prev_ == this) && (prev_->next_ == this);
1.279 +}
1.280 +
1.281 +
1.282 +/*
1.283 +FAQ On subtle implementation details:
1.284 +
1.285 +1) What makes this problem subtle? Please take a look at "Strategies
1.286 +for Implementing POSIX Condition Variables on Win32" by Douglas
1.287 +C. Schmidt and Irfan Pyarali.
1.288 +http://www.cs.wustl.edu/~schmidt/win32-cv-1.html It includes
1.289 +discussions of numerous flawed strategies for implementing this
1.290 +functionality. I'm not convinced that even the final proposed
1.291 +implementation has semantics that are as nice as this implementation
1.292 +(especially with regard to Broadcast() and the impact on threads that
1.293 +try to Wait() after a Broadcast() has been called, but before all the
1.294 +original waiting threads have been signaled).
1.295 +
1.296 +2) Why can't you use a single wait_event for all threads that call
1.297 +Wait()? See FAQ-question-1, or consider the following: If a single
1.298 +event were used, then numerous threads calling Wait() could release
1.299 +their cs locks, and be preempted just before calling
1.300 +WaitForSingleObject(). If a call to Broadcast() was then presented on
1.301 +a second thread, it would be impossible to actually signal all
1.302 +waiting(?) threads. Some number of SetEvent() calls *could* be made,
1.303 +but there could be no guarantee that those led to to more than one
1.304 +signaled thread (SetEvent()'s may be discarded after the first!), and
1.305 +there could be no guarantee that the SetEvent() calls didn't just
1.306 +awaken "other" threads that hadn't even started waiting yet (oops).
1.307 +Without any limit on the number of requisite SetEvent() calls, the
1.308 +system would be forced to do many such calls, allowing many new waits
1.309 +to receive spurious signals.
1.310 +
1.311 +3) How does this implementation cause spurious signal events? The
1.312 +cause in this implementation involves a race between a signal via
1.313 +time-out and a signal via Signal() or Broadcast(). The series of
1.314 +actions leading to this are:
1.315 +
1.316 +a) Timer fires, and a waiting thread exits the line of code:
1.317 +
1.318 + WaitForSingleObject(waiting_event, max_time.InMilliseconds());
1.319 +
1.320 +b) That thread (in (a)) is randomly pre-empted after the above line,
1.321 +leaving the waiting_event reset (unsignaled) and still in the
1.322 +waiting_list_.
1.323 +
1.324 +c) A call to Signal() (or Broadcast()) on a second thread proceeds, and
1.325 +selects the waiting cv_event (identified in step (b)) as the event to revive
1.326 +via a call to SetEvent().
1.327 +
1.328 +d) The Signal() method (step c) calls SetEvent() on waiting_event (step b).
1.329 +
1.330 +e) The waiting cv_event (step b) is now signaled, but no thread is
1.331 +waiting on it.
1.332 +
1.333 +f) When that waiting_event (step b) is reused, it will immediately
1.334 +be signaled (spuriously).
1.335 +
1.336 +
1.337 +4) Why do you recycle events, and cause spurious signals? First off,
1.338 +the spurious events are very rare. They can only (I think) appear
1.339 +when the race described in FAQ-question-3 takes place. This should be
1.340 +very rare. Most(?) uses will involve only timer expiration, or only
1.341 +Signal/Broadcast() actions. When both are used, it will be rare that
1.342 +the race will appear, and it would require MANY Wait() and signaling
1.343 +activities. If this implementation did not recycle events, then it
1.344 +would have to create and destroy events for every call to Wait().
1.345 +That allocation/deallocation and associated construction/destruction
1.346 +would be costly (per wait), and would only be a rare benefit (when the
1.347 +race was "lost" and a spurious signal took place). That would be bad
1.348 +(IMO) optimization trade-off. Finally, such spurious events are
1.349 +allowed by the specification of condition variables (such as
1.350 +implemented in Vista), and hence it is better if any user accommodates
1.351 +such spurious events (see usage note in condition_variable.h).
1.352 +
1.353 +5) Why don't you reset events when you are about to recycle them, or
1.354 +about to reuse them, so that the spurious signals don't take place?
1.355 +The thread described in FAQ-question-3 step c may be pre-empted for an
1.356 +arbitrary length of time before proceeding to step d. As a result,
1.357 +the wait_event may actually be re-used *before* step (e) is reached.
1.358 +As a result, calling reset would not help significantly.
1.359 +
1.360 +6) How is it that the callers lock is released atomically with the
1.361 +entry into a wait state? We commit to the wait activity when we
1.362 +allocate the wait_event for use in a given call to Wait(). This
1.363 +allocation takes place before the caller's lock is released (and
1.364 +actually before our internal_lock_ is released). That allocation is
1.365 +the defining moment when "the wait state has been entered," as that
1.366 +thread *can* now be signaled by a call to Broadcast() or Signal().
1.367 +Hence we actually "commit to wait" before releasing the lock, making
1.368 +the pair effectively atomic.
1.369 +
1.370 +8) Why do you need to lock your data structures during waiting, as the
1.371 +caller is already in possession of a lock? We need to Acquire() and
1.372 +Release() our internal lock during Signal() and Broadcast(). If we tried
1.373 +to use a callers lock for this purpose, we might conflict with their
1.374 +external use of the lock. For example, the caller may use to consistently
1.375 +hold a lock on one thread while calling Signal() on another, and that would
1.376 +block Signal().
1.377 +
1.378 +9) Couldn't a more efficient implementation be provided if you
1.379 +preclude using more than one external lock in conjunction with a
1.380 +single ConditionVariable instance? Yes, at least it could be viewed
1.381 +as a simpler API (since you don't have to reiterate the lock argument
1.382 +in each Wait() call). One of the constructors now takes a specific
1.383 +lock as an argument, and a there are corresponding Wait() calls that
1.384 +don't specify a lock now. It turns that the resulting implmentation
1.385 +can't be made more efficient, as the internal lock needs to be used by
1.386 +Signal() and Broadcast(), to access internal data structures. As a
1.387 +result, I was not able to utilize the user supplied lock (which is
1.388 +being used by the user elsewhere presumably) to protect the private
1.389 +member access.
1.390 +
1.391 +9) Since you have a second lock, how can be be sure that there is no
1.392 +possible deadlock scenario? Our internal_lock_ is always the last
1.393 +lock acquired, and the first one released, and hence a deadlock (due
1.394 +to critical section problems) is impossible as a consequence of our
1.395 +lock.
1.396 +
1.397 +10) When doing a Broadcast(), why did you copy all the events into
1.398 +an STL queue, rather than making a linked-loop, and iterating over it?
1.399 +The iterating during Broadcast() is done so outside the protection
1.400 +of the internal lock. As a result, other threads, such as the thread
1.401 +wherein a related event is waiting, could asynchronously manipulate
1.402 +the links around a cv_event. As a result, the link structure cannot
1.403 +be used outside a lock. Broadcast() could iterate over waiting
1.404 +events by cycling in-and-out of the protection of the internal_lock,
1.405 +but that appears more expensive than copying the list into an STL
1.406 +stack.
1.407 +
1.408 +11) Why did the lock.h file need to be modified so much for this
1.409 +change? Central to a Condition Variable is the atomic release of a
1.410 +lock during a Wait(). This places Wait() functionality exactly
1.411 +mid-way between the two classes, Lock and Condition Variable. Given
1.412 +that there can be nested Acquire()'s of locks, and Wait() had to
1.413 +Release() completely a held lock, it was necessary to augment the Lock
1.414 +class with a recursion counter. Even more subtle is the fact that the
1.415 +recursion counter (in a Lock) must be protected, as many threads can
1.416 +access it asynchronously. As a positive fallout of this, there are
1.417 +now some DCHECKS to be sure no one Release()s a Lock more than they
1.418 +Acquire()ed it, and there is ifdef'ed functionality that can detect
1.419 +nested locks (legal under windows, but not under Posix).
1.420 +
1.421 +12) Why is it that the cv_events removed from list in Broadcast() and Signal()
1.422 +are not leaked? How are they recovered?? The cv_events that appear to leak are
1.423 +taken from the waiting_list_. For each element in that list, there is currently
1.424 +a thread in or around the WaitForSingleObject() call of Wait(), and those
1.425 +threads have references to these otherwise leaked events. They are passed as
1.426 +arguments to be recycled just aftre returning from WaitForSingleObject().
1.427 +
1.428 +13) Why did you use a custom container class (the linked list), when STL has
1.429 +perfectly good containers, such as an STL list? The STL list, as with any
1.430 +container, does not guarantee the utility of an iterator across manipulation
1.431 +(such as insertions and deletions) of the underlying container. The custom
1.432 +double-linked-list container provided that assurance. I don't believe any
1.433 +combination of STL containers provided the services that were needed at the same
1.434 +O(1) efficiency as the custom linked list. The unusual requirement
1.435 +for the container class is that a reference to an item within a container (an
1.436 +iterator) needed to be maintained across an arbitrary manipulation of the
1.437 +container. This requirement exposes itself in the Wait() method, where a
1.438 +waiting_event must be selected prior to the WaitForSingleObject(), and then it
1.439 +must be used as part of recycling to remove the related instance from the
1.440 +waiting_list. A hash table (STL map) could be used, but I was embarrased to
1.441 +use a complex and relatively low efficiency container when a doubly linked list
1.442 +provided O(1) performance in all required operations. Since other operations
1.443 +to provide performance-and/or-fairness required queue (FIFO) and list (LIFO)
1.444 +containers, I would also have needed to use an STL list/queue as well as an STL
1.445 +map. In the end I decided it would be "fun" to just do it right, and I
1.446 +put so many assertions (DCHECKs) into the container class that it is trivial to
1.447 +code review and validate its correctness.
1.448 +
1.449 +*/
