michael@0: // Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
michael@0: // Use of this source code is governed by a BSD-style license that can be
michael@0: // found in the LICENSE file.
michael@0: 
michael@0: #include "base/condition_variable.h"
michael@0: 
michael@0: #include <stack>
michael@0: 
michael@0: #include "base/lock.h"
michael@0: #include "base/logging.h"
michael@0: #include "base/time.h"
michael@0: 
michael@0: using base::TimeDelta;
michael@0: 
michael@0: ConditionVariable::ConditionVariable(Lock* user_lock)
michael@0:   : user_lock_(*user_lock),
michael@0:     run_state_(RUNNING),
michael@0:     allocation_counter_(0),
michael@0:     recycling_list_size_(0) {
michael@0:   DCHECK(user_lock);
michael@0: }
michael@0: 
michael@0: ConditionVariable::~ConditionVariable() {
michael@0:   AutoLock auto_lock(internal_lock_);
michael@0:   run_state_ = SHUTDOWN;  // Prevent any more waiting.
michael@0: 
michael@0:   DCHECK_EQ(recycling_list_size_, allocation_counter_);
michael@0:   if (recycling_list_size_ != allocation_counter_) {  // Rare shutdown problem.
michael@0:     // There are threads of execution still in this->TimedWait() and yet the
michael@0:     // caller has instigated the destruction of this instance :-/.
michael@0:     // A common reason for such "overly hasty" destruction is that the caller
michael@0:     // was not willing to wait for all the threads to terminate.  Such hasty
michael@0:     // actions are a violation of our usage contract, but we'll give the
michael@0:     // waiting thread(s) one last chance to exit gracefully (prior to our
michael@0:     // destruction).
michael@0:     // Note: waiting_list_ *might* be empty, but recycling is still pending.
michael@0:     AutoUnlock auto_unlock(internal_lock_);
michael@0:     Broadcast();  // Make sure all waiting threads have been signaled.
michael@0:     Sleep(10);  // Give threads a chance to grab internal_lock_.
michael@0:     // All contained threads should be blocked on user_lock_ by now :-).
michael@0:   }  // Reacquire internal_lock_.
michael@0: 
michael@0:   DCHECK_EQ(recycling_list_size_, allocation_counter_);
michael@0: }
michael@0: 
michael@0: void ConditionVariable::Wait() {
michael@0:   // Default to "wait forever" timing, which means have to get a Signal()
michael@0:   // or Broadcast() to come out of this wait state.
michael@0:   TimedWait(TimeDelta::FromMilliseconds(INFINITE));
michael@0: }
michael@0: 
michael@0: void ConditionVariable::TimedWait(const TimeDelta& max_time) {
michael@0:   Event* waiting_event;
michael@0:   HANDLE handle;
michael@0:   {
michael@0:     AutoLock auto_lock(internal_lock_);
michael@0:     if (RUNNING != run_state_) return;  // Destruction in progress.
michael@0:     waiting_event = GetEventForWaiting();
michael@0:     handle = waiting_event->handle();
michael@0:     DCHECK(handle);
michael@0:   }  // Release internal_lock.
michael@0: 
michael@0:   {
michael@0:     AutoUnlock unlock(user_lock_);  // Release caller's lock
michael@0:     WaitForSingleObject(handle, static_cast<DWORD>(max_time.InMilliseconds()));
michael@0:     // Minimize spurious signal creation window by recycling asap.
michael@0:     AutoLock auto_lock(internal_lock_);
michael@0:     RecycleEvent(waiting_event);
michael@0:     // Release internal_lock_
michael@0:   }  // Reacquire callers lock to depth at entry.
michael@0: }
michael@0: 
michael@0: // Broadcast() is guaranteed to signal all threads that were waiting (i.e., had
michael@0: // a cv_event internally allocated for them) before Broadcast() was called.
michael@0: void ConditionVariable::Broadcast() {
michael@0:   std::stack<HANDLE> handles;  // See FAQ-question-10.
michael@0:   {
michael@0:     AutoLock auto_lock(internal_lock_);
michael@0:     if (waiting_list_.IsEmpty())
michael@0:       return;
michael@0:     while (!waiting_list_.IsEmpty())
michael@0:       // This is not a leak from waiting_list_.  See FAQ-question 12.
michael@0:       handles.push(waiting_list_.PopBack()->handle());
michael@0:   }  // Release internal_lock_.
michael@0:   while (!handles.empty()) {
michael@0:     SetEvent(handles.top());
michael@0:     handles.pop();
michael@0:   }
michael@0: }
michael@0: 
michael@0: // Signal() will select one of the waiting threads, and signal it (signal its
michael@0: // cv_event).  For better performance we signal the thread that went to sleep
michael@0: // most recently (LIFO).  If we want fairness, then we wake the thread that has
michael@0: // been sleeping the longest (FIFO).
michael@0: void ConditionVariable::Signal() {
michael@0:   HANDLE handle;
michael@0:   {
michael@0:     AutoLock auto_lock(internal_lock_);
michael@0:     if (waiting_list_.IsEmpty())
michael@0:       return;  // No one to signal.
michael@0:     // Only performance option should be used.
michael@0:     // This is not a leak from waiting_list.  See FAQ-question 12.
michael@0:      handle = waiting_list_.PopBack()->handle();  // LIFO.
michael@0:   }  // Release internal_lock_.
michael@0:   SetEvent(handle);
michael@0: }
michael@0: 
michael@0: // GetEventForWaiting() provides a unique cv_event for any caller that needs to
michael@0: // wait.  This means that (worst case) we may over time create as many cv_event
michael@0: // objects as there are threads simultaneously using this instance's Wait()
michael@0: // functionality.
michael@0: ConditionVariable::Event* ConditionVariable::GetEventForWaiting() {
michael@0:   // We hold internal_lock, courtesy of Wait().
michael@0:   Event* cv_event;
michael@0:   if (0 == recycling_list_size_) {
michael@0:     DCHECK(recycling_list_.IsEmpty());
michael@0:     cv_event = new Event();
michael@0:     cv_event->InitListElement();
michael@0:     allocation_counter_++;
michael@0:     // CHECK_NE is not defined in our codebase, so we have to use CHECK
michael@0:     CHECK(cv_event->handle());
michael@0:   } else {
michael@0:     cv_event = recycling_list_.PopFront();
michael@0:     recycling_list_size_--;
michael@0:   }
michael@0:   waiting_list_.PushBack(cv_event);
michael@0:   return cv_event;
michael@0: }
michael@0: 
michael@0: // RecycleEvent() takes a cv_event that was previously used for Wait()ing, and
michael@0: // recycles it for use in future Wait() calls for this or other threads.
michael@0: // Note that there is a tiny chance that the cv_event is still signaled when we
michael@0: // obtain it, and that can cause spurious signals (if/when we re-use the
michael@0: // cv_event), but such is quite rare (see FAQ-question-5).
michael@0: void ConditionVariable::RecycleEvent(Event* used_event) {
michael@0:   // We hold internal_lock, courtesy of Wait().
michael@0:   // If the cv_event timed out, then it is necessary to remove it from
michael@0:   // waiting_list_.  If it was selected by Broadcast() or Signal(), then it is
michael@0:   // already gone.
michael@0:   used_event->Extract();  // Possibly redundant
michael@0:   recycling_list_.PushBack(used_event);
michael@0:   recycling_list_size_++;
michael@0: }
michael@0: //------------------------------------------------------------------------------
michael@0: // The next section provides the implementation for the private Event class.
michael@0: //------------------------------------------------------------------------------
michael@0: 
michael@0: // Event provides a doubly-linked-list of events for use exclusively by the
michael@0: // ConditionVariable class.
michael@0: 
michael@0: // This custom container was crafted because no simple combination of STL
michael@0: // classes appeared to support the functionality required.  The specific
michael@0: // unusual requirement for a linked-list-class is support for the Extract()
michael@0: // method, which can remove an element from a list, potentially for insertion
michael@0: // into a second list.  Most critically, the Extract() method is idempotent,
michael@0: // turning the indicated element into an extracted singleton whether it was
michael@0: // contained in a list or not.  This functionality allows one (or more) of
michael@0: // threads to do the extraction.  The iterator that identifies this extractable
michael@0: // element (in this case, a pointer to the list element) can be used after
michael@0: // arbitrary manipulation of the (possibly) enclosing list container.  In
michael@0: // general, STL containers do not provide iterators that can be used across
michael@0: // modifications (insertions/extractions) of the enclosing containers, and
michael@0: // certainly don't provide iterators that can be used if the identified
michael@0: // element is *deleted* (removed) from the container.
michael@0: 
michael@0: // It is possible to use multiple redundant containers, such as an STL list,
michael@0: // and an STL map, to achieve similar container semantics.  This container has
michael@0: // only O(1) methods, while the corresponding (multiple) STL container approach
michael@0: // would have more complex O(log(N)) methods (yeah... N isn't that large).
michael@0: // Multiple containers also makes correctness more difficult to assert, as
michael@0: // data is redundantly stored and maintained, which is generally evil.
michael@0: 
michael@0: ConditionVariable::Event::Event() : handle_(0) {
michael@0:   next_ = prev_ = this;  // Self referencing circular.
michael@0: }
michael@0: 
michael@0: ConditionVariable::Event::~Event() {
michael@0:   if (0 == handle_) {
michael@0:     // This is the list holder
michael@0:     while (!IsEmpty()) {
michael@0:       Event* cv_event = PopFront();
michael@0:       DCHECK(cv_event->ValidateAsItem());
michael@0:       delete cv_event;
michael@0:     }
michael@0:   }
michael@0:   DCHECK(IsSingleton());
michael@0:   if (0 != handle_) {
michael@0:     int ret_val = CloseHandle(handle_);
michael@0:     DCHECK(ret_val);
michael@0:   }
michael@0: }
michael@0: 
michael@0: // Change a container instance permanently into an element of a list.
michael@0: void ConditionVariable::Event::InitListElement() {
michael@0:   DCHECK(!handle_);
michael@0:   handle_ = CreateEvent(NULL, false, false, NULL);
michael@0:   CHECK(handle_);
michael@0: }
michael@0: 
michael@0: // Methods for use on lists.
michael@0: bool ConditionVariable::Event::IsEmpty() const {
michael@0:   DCHECK(ValidateAsList());
michael@0:   return IsSingleton();
michael@0: }
michael@0: 
michael@0: void ConditionVariable::Event::PushBack(Event* other) {
michael@0:   DCHECK(ValidateAsList());
michael@0:   DCHECK(other->ValidateAsItem());
michael@0:   DCHECK(other->IsSingleton());
michael@0:   // Prepare other for insertion.
michael@0:   other->prev_ = prev_;
michael@0:   other->next_ = this;
michael@0:   // Cut into list.
michael@0:   prev_->next_ = other;
michael@0:   prev_ = other;
michael@0:   DCHECK(ValidateAsDistinct(other));
michael@0: }
michael@0: 
michael@0: ConditionVariable::Event* ConditionVariable::Event::PopFront() {
michael@0:   DCHECK(ValidateAsList());
michael@0:   DCHECK(!IsSingleton());
michael@0:   return next_->Extract();
michael@0: }
michael@0: 
michael@0: ConditionVariable::Event* ConditionVariable::Event::PopBack() {
michael@0:   DCHECK(ValidateAsList());
michael@0:   DCHECK(!IsSingleton());
michael@0:   return prev_->Extract();
michael@0: }
michael@0: 
michael@0: // Methods for use on list elements.
michael@0: // Accessor method.
michael@0: HANDLE ConditionVariable::Event::handle() const {
michael@0:   DCHECK(ValidateAsItem());
michael@0:   return handle_;
michael@0: }
michael@0: 
michael@0: // Pull an element from a list (if it's in one).
michael@0: ConditionVariable::Event* ConditionVariable::Event::Extract() {
michael@0:   DCHECK(ValidateAsItem());
michael@0:   if (!IsSingleton()) {
michael@0:     // Stitch neighbors together.
michael@0:     next_->prev_ = prev_;
michael@0:     prev_->next_ = next_;
michael@0:     // Make extractee into a singleton.
michael@0:     prev_ = next_ = this;
michael@0:   }
michael@0:   DCHECK(IsSingleton());
michael@0:   return this;
michael@0: }
michael@0: 
michael@0: // Method for use on a list element or on a list.
michael@0: bool ConditionVariable::Event::IsSingleton() const {
michael@0:   DCHECK(ValidateLinks());
michael@0:   return next_ == this;
michael@0: }
michael@0: 
michael@0: // Provide pre/post conditions to validate correct manipulations.
michael@0: bool ConditionVariable::Event::ValidateAsDistinct(Event* other) const {
michael@0:   return ValidateLinks() && other->ValidateLinks() && (this != other);
michael@0: }
michael@0: 
michael@0: bool ConditionVariable::Event::ValidateAsItem() const {
michael@0:   return (0 != handle_) && ValidateLinks();
michael@0: }
michael@0: 
michael@0: bool ConditionVariable::Event::ValidateAsList() const {
michael@0:   return (0 == handle_) && ValidateLinks();
michael@0: }
michael@0: 
michael@0: bool ConditionVariable::Event::ValidateLinks() const {
michael@0:   // Make sure both of our neighbors have links that point back to us.
michael@0:   // We don't do the O(n) check and traverse the whole loop, and instead only
michael@0:   // do a local check to (and returning from) our immediate neighbors.
michael@0:   return (next_->prev_ == this) && (prev_->next_ == this);
michael@0: }
michael@0: 
michael@0: 
michael@0: /*
michael@0: FAQ On subtle implementation details:
michael@0: 
michael@0: 1) What makes this problem subtle?  Please take a look at "Strategies
michael@0: for Implementing POSIX Condition Variables on Win32" by Douglas
michael@0: C. Schmidt and Irfan Pyarali.
michael@0: http://www.cs.wustl.edu/~schmidt/win32-cv-1.html It includes
michael@0: discussions of numerous flawed strategies for implementing this
michael@0: functionality.  I'm not convinced that even the final proposed
michael@0: implementation has semantics that are as nice as this implementation
michael@0: (especially with regard to Broadcast() and the impact on threads that
michael@0: try to Wait() after a Broadcast() has been called, but before all the
michael@0: original waiting threads have been signaled).
michael@0: 
michael@0: 2) Why can't you use a single wait_event for all threads that call
michael@0: Wait()?  See FAQ-question-1, or consider the following: If a single
michael@0: event were used, then numerous threads calling Wait() could release
michael@0: their cs locks, and be preempted just before calling
michael@0: WaitForSingleObject().  If a call to Broadcast() was then presented on
michael@0: a second thread, it would be impossible to actually signal all
michael@0: waiting(?) threads.  Some number of SetEvent() calls *could* be made,
michael@0: but there could be no guarantee that those led to to more than one
michael@0: signaled thread (SetEvent()'s may be discarded after the first!), and
michael@0: there could be no guarantee that the SetEvent() calls didn't just
michael@0: awaken "other" threads that hadn't even started waiting yet (oops).
michael@0: Without any limit on the number of requisite SetEvent() calls, the
michael@0: system would be forced to do many such calls, allowing many new waits
michael@0: to receive spurious signals.
michael@0: 
michael@0: 3) How does this implementation cause spurious signal events?  The
michael@0: cause in this implementation involves a race between a signal via
michael@0: time-out and a signal via Signal() or Broadcast().  The series of
michael@0: actions leading to this are:
michael@0: 
michael@0: a) Timer fires, and a waiting thread exits the line of code:
michael@0: 
michael@0:     WaitForSingleObject(waiting_event, max_time.InMilliseconds());
michael@0: 
michael@0: b) That thread (in (a)) is randomly pre-empted after the above line,
michael@0: leaving the waiting_event reset (unsignaled) and still in the
michael@0: waiting_list_.
michael@0: 
michael@0: c) A call to Signal() (or Broadcast()) on a second thread proceeds, and
michael@0: selects the waiting cv_event (identified in step (b)) as the event to revive
michael@0: via a call to SetEvent().
michael@0: 
michael@0: d) The Signal() method (step c) calls SetEvent() on waiting_event (step b).
michael@0: 
michael@0: e) The waiting cv_event (step b) is now signaled, but no thread is
michael@0: waiting on it.
michael@0: 
michael@0: f) When that waiting_event (step b) is reused, it will immediately
michael@0: be signaled (spuriously).
michael@0: 
michael@0: 
michael@0: 4) Why do you recycle events, and cause spurious signals?  First off,
michael@0: the spurious events are very rare.  They can only (I think) appear
michael@0: when the race described in FAQ-question-3 takes place.  This should be
michael@0: very rare.  Most(?)  uses will involve only timer expiration, or only
michael@0: Signal/Broadcast() actions.  When both are used, it will be rare that
michael@0: the race will appear, and it would require MANY Wait() and signaling
michael@0: activities.  If this implementation did not recycle events, then it
michael@0: would have to create and destroy events for every call to Wait().
michael@0: That allocation/deallocation and associated construction/destruction
michael@0: would be costly (per wait), and would only be a rare benefit (when the
michael@0: race was "lost" and a spurious signal took place). That would be bad
michael@0: (IMO) optimization trade-off.  Finally, such spurious events are
michael@0: allowed by the specification of condition variables (such as
michael@0: implemented in Vista), and hence it is better if any user accommodates
michael@0: such spurious events (see usage note in condition_variable.h).
michael@0: 
michael@0: 5) Why don't you reset events when you are about to recycle them, or
michael@0: about to reuse them, so that the spurious signals don't take place?
michael@0: The thread described in FAQ-question-3 step c may be pre-empted for an
michael@0: arbitrary length of time before proceeding to step d.  As a result,
michael@0: the wait_event may actually be re-used *before* step (e) is reached.
michael@0: As a result, calling reset would not help significantly.
michael@0: 
michael@0: 6) How is it that the callers lock is released atomically with the
michael@0: entry into a wait state?  We commit to the wait activity when we
michael@0: allocate the wait_event for use in a given call to Wait().  This
michael@0: allocation takes place before the caller's lock is released (and
michael@0: actually before our internal_lock_ is released).  That allocation is
michael@0: the defining moment when "the wait state has been entered," as that
michael@0: thread *can* now be signaled by a call to Broadcast() or Signal().
michael@0: Hence we actually "commit to wait" before releasing the lock, making
michael@0: the pair effectively atomic.
michael@0: 
michael@0: 8) Why do you need to lock your data structures during waiting, as the
michael@0: caller is already in possession of a lock?  We need to Acquire() and
michael@0: Release() our internal lock during Signal() and Broadcast().  If we tried
michael@0: to use a callers lock for this purpose, we might conflict with their
michael@0: external use of the lock.  For example, the caller may use to consistently
michael@0: hold a lock on one thread while calling Signal() on another, and that would
michael@0: block Signal().
michael@0: 
michael@0: 9) Couldn't a more efficient implementation be provided if you
michael@0: preclude using more than one external lock in conjunction with a
michael@0: single ConditionVariable instance?  Yes, at least it could be viewed
michael@0: as a simpler API (since you don't have to reiterate the lock argument
michael@0: in each Wait() call).  One of the constructors now takes a specific
michael@0: lock as an argument, and a there are corresponding Wait() calls that
michael@0: don't specify a lock now.  It turns that the resulting implmentation
michael@0: can't be made more efficient, as the internal lock needs to be used by
michael@0: Signal() and Broadcast(), to access internal data structures.  As a
michael@0: result, I was not able to utilize the user supplied lock (which is
michael@0: being used by the user elsewhere presumably) to protect the private
michael@0: member access.
michael@0: 
michael@0: 9) Since you have a second lock, how can be be sure that there is no
michael@0: possible deadlock scenario?  Our internal_lock_ is always the last
michael@0: lock acquired, and the first one released, and hence a deadlock (due
michael@0: to critical section problems) is impossible as a consequence of our
michael@0: lock.
michael@0: 
michael@0: 10) When doing a Broadcast(), why did you copy all the events into
michael@0: an STL queue, rather than making a linked-loop, and iterating over it?
michael@0: The iterating during Broadcast() is done so outside the protection
michael@0: of the internal lock. As a result, other threads, such as the thread
michael@0: wherein a related event is waiting, could asynchronously manipulate
michael@0: the links around a cv_event.  As a result, the link structure cannot
michael@0: be used outside a lock.  Broadcast() could iterate over waiting
michael@0: events by cycling in-and-out of the protection of the internal_lock,
michael@0: but that appears more expensive than copying the list into an STL
michael@0: stack.
michael@0: 
michael@0: 11) Why did the lock.h file need to be modified so much for this
michael@0: change?  Central to a Condition Variable is the atomic release of a
michael@0: lock during a Wait().  This places Wait() functionality exactly
michael@0: mid-way between the two classes, Lock and Condition Variable.  Given
michael@0: that there can be nested Acquire()'s of locks, and Wait() had to
michael@0: Release() completely a held lock, it was necessary to augment the Lock
michael@0: class with a recursion counter. Even more subtle is the fact that the
michael@0: recursion counter (in a Lock) must be protected, as many threads can
michael@0: access it asynchronously.  As a positive fallout of this, there are
michael@0: now some DCHECKS to be sure no one Release()s a Lock more than they
michael@0: Acquire()ed it, and there is ifdef'ed functionality that can detect
michael@0: nested locks (legal under windows, but not under Posix).
michael@0: 
michael@0: 12) Why is it that the cv_events removed from list in Broadcast() and Signal()
michael@0: are not leaked?  How are they recovered??  The cv_events that appear to leak are
michael@0: taken from the waiting_list_.  For each element in that list, there is currently
michael@0: a thread in or around the WaitForSingleObject() call of Wait(), and those
michael@0: threads have references to these otherwise leaked events. They are passed as
michael@0: arguments to be recycled just aftre returning from WaitForSingleObject().
michael@0: 
michael@0: 13) Why did you use a custom container class (the linked list), when STL has
michael@0: perfectly good containers, such as an STL list?  The STL list, as with any
michael@0: container, does not guarantee the utility of an iterator across manipulation
michael@0: (such as insertions and deletions) of the underlying container.  The custom
michael@0: double-linked-list container provided that assurance.  I don't believe any
michael@0: combination of STL containers provided the services that were needed at the same
michael@0: O(1) efficiency as the custom linked list.  The unusual requirement
michael@0: for the container class is that a reference to an item within a container (an
michael@0: iterator) needed to be maintained across an arbitrary manipulation of the
michael@0: container.  This requirement exposes itself in the Wait() method, where a
michael@0: waiting_event must be selected prior to the WaitForSingleObject(), and then it
michael@0: must be used as part of recycling to remove the related instance from the
michael@0: waiting_list.  A hash table (STL map) could be used, but I was embarrased to
michael@0: use a complex and relatively low efficiency container when a doubly linked list
michael@0: provided O(1) performance in all required operations.  Since other operations
michael@0: to provide performance-and/or-fairness required queue (FIFO) and list (LIFO)
michael@0: containers, I would also have needed to use an STL list/queue as well as an STL
michael@0: map.  In the end I decided it would be "fun" to just do it right, and I
michael@0: put so many assertions (DCHECKs) into the container class that it is trivial to
michael@0: code review and validate its correctness.
michael@0: 
michael@0: */