Prep work for win7-specific condition variable

base/synchronization/condition_variable_win.cc

 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "base/synchronization/condition_variable.h"
 
+#include <windows.h>
 #include <stack>
 
+#include "base/compiler_specific.h"
 #include "base/logging.h"
 #include "base/synchronization/lock.h"
 #include "base/time.h"
 
 namespace base {
+// Abstract class of the pimpl, idiom. TODO(cpu): create the
+// WinVistaCondVar once the WinXPCondVar lands.
+class ConditionVarImpl {
+ public:
+  virtual ~ConditionVarImpl() {};
+  virtual void Wait() = 0;
+  virtual void TimedWait(const TimeDelta& max_time) = 0;
+  virtual void Broadcast() = 0;
+  virtual void Signal() = 0;
+};
 
-ConditionVariable::ConditionVariable(Lock* user_lock)
+class WinXPCondVar : public ConditionVarImpl {
+ public:
+  WinXPCondVar(Lock* user_lock);
+  ~WinXPCondVar();
+  // Overridden from ConditionVarImpl.

[brettw, 2011/12/06 23:44:54]

Can you put a blank line above this?

+  virtual void Wait() OVERRIDE;
+  virtual void TimedWait(const TimeDelta& max_time) OVERRIDE;
+  virtual void Broadcast() OVERRIDE;
+  virtual void Signal() OVERRIDE;
+
+  // Define Event class that is used to form circularly linked lists.
+  // The list container is an element with NULL as its handle_ value.
+  // The actual list elements have a non-zero handle_ value.
+  // All calls to methods MUST be done under protection of a lock so that links
+  // can be validated.  Without the lock, some links might asynchronously
+  // change, and the assertions would fail (as would list change operations).
+  class Event {
+   public:
+    // Default constructor with no arguments creates a list container.
+    Event();
+    ~Event();
+
+    // InitListElement transitions an instance from a container, to an element.
+    void InitListElement();
+
+    // Methods for use on lists.
+    bool IsEmpty() const;
+    void PushBack(Event* other);
+    Event* PopFront();
+    Event* PopBack();
+
+    // Methods for use on list elements.
+    // Accessor method.
+    HANDLE handle() const;
+    // Pull an element from a list (if it's in one).
+    Event* Extract();
+
+    // Method for use on a list element or on a list.
+    bool IsSingleton() const;
+
+   private:
+    // Provide pre/post conditions to validate correct manipulations.
+    bool ValidateAsDistinct(Event* other) const;
+    bool ValidateAsItem() const;
+    bool ValidateAsList() const;
+    bool ValidateLinks() const;
+
+    HANDLE handle_;
+    Event* next_;
+    Event* prev_;
+    DISALLOW_COPY_AND_ASSIGN(Event);
+  };
+
+  // Note that RUNNING is an unlikely number to have in RAM by accident.
+  // This helps with defensive destructor coding in the face of user error.
+  enum RunState { SHUTDOWN = 0, RUNNING = 64213 };
+
+  // Internal implementation methods supporting Wait().
+  Event* GetEventForWaiting();
+  void RecycleEvent(Event* used_event);
+
+  RunState run_state_;
+
+  // Private critical section for access to member data.
+  base::Lock internal_lock_;
+
+  // Lock that is acquired before calling Wait().
+  base::Lock& user_lock_;
+
+  // Events that threads are blocked on.
+  Event waiting_list_;
+
+  // Free list for old events.
+  Event recycling_list_;
+  int recycling_list_size_;
+
+  // The number of allocated, but not yet deleted events.
+  int allocation_counter_;
+};
+
+WinXPCondVar::WinXPCondVar(Lock* user_lock)
     : user_lock_(*user_lock),
       run_state_(RUNNING),
       allocation_counter_(0),
       recycling_list_size_(0) {
   DCHECK(user_lock);
 }
 
-ConditionVariable::~ConditionVariable() {
+WinXPCondVar::~WinXPCondVar() {
   AutoLock auto_lock(internal_lock_);
   run_state_ = SHUTDOWN;  // Prevent any more waiting.
 
   DCHECK_EQ(recycling_list_size_, allocation_counter_);
   if (recycling_list_size_ != allocation_counter_) {  // Rare shutdown problem.
     // There are threads of execution still in this->TimedWait() and yet the
     // caller has instigated the destruction of this instance :-/.
     // A common reason for such "overly hasty" destruction is that the caller
     // was not willing to wait for all the threads to terminate.  Such hasty
     // actions are a violation of our usage contract, but we'll give the
     // waiting thread(s) one last chance to exit gracefully (prior to our
     // destruction).
     // Note: waiting_list_ *might* be empty, but recycling is still pending.
     AutoUnlock auto_unlock(internal_lock_);
     Broadcast();  // Make sure all waiting threads have been signaled.
     Sleep(10);  // Give threads a chance to grab internal_lock_.
     // All contained threads should be blocked on user_lock_ by now :-).
   }  // Reacquire internal_lock_.
 
   DCHECK_EQ(recycling_list_size_, allocation_counter_);
 }
 
-void ConditionVariable::Wait() {
+void WinXPCondVar::Wait() {
   // Default to "wait forever" timing, which means have to get a Signal()
   // or Broadcast() to come out of this wait state.
   TimedWait(TimeDelta::FromMilliseconds(INFINITE));
 }
 
-void ConditionVariable::TimedWait(const TimeDelta& max_time) {
+void WinXPCondVar::TimedWait(const TimeDelta& max_time) {
   Event* waiting_event;
   HANDLE handle;
   {
     AutoLock auto_lock(internal_lock_);
     if (RUNNING != run_state_) return;  // Destruction in progress.
     waiting_event = GetEventForWaiting();
     handle = waiting_event->handle();
     DCHECK(handle);
   }  // Release internal_lock.
 
   {
     AutoUnlock unlock(user_lock_);  // Release caller's lock
     WaitForSingleObject(handle, static_cast<DWORD>(max_time.InMilliseconds()));
     // Minimize spurious signal creation window by recycling asap.
     AutoLock auto_lock(internal_lock_);
     RecycleEvent(waiting_event);
     // Release internal_lock_
   }  // Reacquire callers lock to depth at entry.
 }
 
 // Broadcast() is guaranteed to signal all threads that were waiting (i.e., had
 // a cv_event internally allocated for them) before Broadcast() was called.
-void ConditionVariable::Broadcast() {
+void WinXPCondVar::Broadcast() {
   std::stack<HANDLE> handles;  // See FAQ-question-10.
   {
     AutoLock auto_lock(internal_lock_);
     if (waiting_list_.IsEmpty())
       return;
     while (!waiting_list_.IsEmpty())
       // This is not a leak from waiting_list_.  See FAQ-question 12.
       handles.push(waiting_list_.PopBack()->handle());
   }  // Release internal_lock_.
   while (!handles.empty()) {
     SetEvent(handles.top());
     handles.pop();
   }
 }
 
 // Signal() will select one of the waiting threads, and signal it (signal its
 // cv_event).  For better performance we signal the thread that went to sleep
 // most recently (LIFO).  If we want fairness, then we wake the thread that has
 // been sleeping the longest (FIFO).
-void ConditionVariable::Signal() {
+void WinXPCondVar::Signal() {
   HANDLE handle;
   {
     AutoLock auto_lock(internal_lock_);
     if (waiting_list_.IsEmpty())
       return;  // No one to signal.
     // Only performance option should be used.
     // This is not a leak from waiting_list.  See FAQ-question 12.
      handle = waiting_list_.PopBack()->handle();  // LIFO.
   }  // Release internal_lock_.
   SetEvent(handle);
 }
 
 // GetEventForWaiting() provides a unique cv_event for any caller that needs to
 // wait.  This means that (worst case) we may over time create as many cv_event
 // objects as there are threads simultaneously using this instance's Wait()
 // functionality.
-ConditionVariable::Event* ConditionVariable::GetEventForWaiting() {
+WinXPCondVar::Event* WinXPCondVar::GetEventForWaiting() {
   // We hold internal_lock, courtesy of Wait().
   Event* cv_event;
   if (0 == recycling_list_size_) {
     DCHECK(recycling_list_.IsEmpty());
     cv_event = new Event();
     cv_event->InitListElement();
     allocation_counter_++;
     DCHECK(cv_event->handle());
   } else {
     cv_event = recycling_list_.PopFront();
     recycling_list_size_--;
   }
   waiting_list_.PushBack(cv_event);
   return cv_event;
 }
 
 // RecycleEvent() takes a cv_event that was previously used for Wait()ing, and
 // recycles it for use in future Wait() calls for this or other threads.
 // Note that there is a tiny chance that the cv_event is still signaled when we
 // obtain it, and that can cause spurious signals (if/when we re-use the
 // cv_event), but such is quite rare (see FAQ-question-5).
-void ConditionVariable::RecycleEvent(Event* used_event) {
+void WinXPCondVar::RecycleEvent(Event* used_event) {
   // We hold internal_lock, courtesy of Wait().
   // If the cv_event timed out, then it is necessary to remove it from
   // waiting_list_.  If it was selected by Broadcast() or Signal(), then it is
   // already gone.
   used_event->Extract();  // Possibly redundant
   recycling_list_.PushBack(used_event);
   recycling_list_size_++;
 }
 //------------------------------------------------------------------------------
 // The next section provides the implementation for the private Event class.
@@ skipping 17 matching lines @@
 // certainly don't provide iterators that can be used if the identified
 // element is *deleted* (removed) from the container.
 
 // It is possible to use multiple redundant containers, such as an STL list,
 // and an STL map, to achieve similar container semantics.  This container has
 // only O(1) methods, while the corresponding (multiple) STL container approach
 // would have more complex O(log(N)) methods (yeah... N isn't that large).
 // Multiple containers also makes correctness more difficult to assert, as
 // data is redundantly stored and maintained, which is generally evil.
 
-ConditionVariable::Event::Event() : handle_(0) {
+WinXPCondVar::Event::Event() : handle_(0) {
   next_ = prev_ = this;  // Self referencing circular.
 }
 
-ConditionVariable::Event::~Event() {
+WinXPCondVar::Event::~Event() {
   if (0 == handle_) {
     // This is the list holder
     while (!IsEmpty()) {
       Event* cv_event = PopFront();
       DCHECK(cv_event->ValidateAsItem());
       delete cv_event;
     }
   }
   DCHECK(IsSingleton());
   if (0 != handle_) {
     int ret_val = CloseHandle(handle_);
     DCHECK(ret_val);
   }
 }
 
 // Change a container instance permanently into an element of a list.
-void ConditionVariable::Event::InitListElement() {
+void WinXPCondVar::Event::InitListElement() {
   DCHECK(!handle_);
   handle_ = CreateEvent(NULL, false, false, NULL);
   DCHECK(handle_);
 }
 
 // Methods for use on lists.
-bool ConditionVariable::Event::IsEmpty() const {
+bool WinXPCondVar::Event::IsEmpty() const {
   DCHECK(ValidateAsList());
   return IsSingleton();
 }
 
-void ConditionVariable::Event::PushBack(Event* other) {
+void WinXPCondVar::Event::PushBack(Event* other) {
   DCHECK(ValidateAsList());
   DCHECK(other->ValidateAsItem());
   DCHECK(other->IsSingleton());
   // Prepare other for insertion.
   other->prev_ = prev_;
   other->next_ = this;
   // Cut into list.
   prev_->next_ = other;
   prev_ = other;
   DCHECK(ValidateAsDistinct(other));
 }
 
-ConditionVariable::Event* ConditionVariable::Event::PopFront() {
+WinXPCondVar::Event* WinXPCondVar::Event::PopFront() {
   DCHECK(ValidateAsList());
   DCHECK(!IsSingleton());
   return next_->Extract();
 }
 
-ConditionVariable::Event* ConditionVariable::Event::PopBack() {
+WinXPCondVar::Event* WinXPCondVar::Event::PopBack() {
   DCHECK(ValidateAsList());
   DCHECK(!IsSingleton());
   return prev_->Extract();
 }
 
 // Methods for use on list elements.
 // Accessor method.
-HANDLE ConditionVariable::Event::handle() const {
+HANDLE WinXPCondVar::Event::handle() const {
   DCHECK(ValidateAsItem());
   return handle_;
 }
 
 // Pull an element from a list (if it's in one).
-ConditionVariable::Event* ConditionVariable::Event::Extract() {
+WinXPCondVar::Event* WinXPCondVar::Event::Extract() {
   DCHECK(ValidateAsItem());
   if (!IsSingleton()) {
     // Stitch neighbors together.
     next_->prev_ = prev_;
     prev_->next_ = next_;
     // Make extractee into a singleton.
     prev_ = next_ = this;
   }
   DCHECK(IsSingleton());
   return this;
 }
 
 // Method for use on a list element or on a list.
-bool ConditionVariable::Event::IsSingleton() const {
+bool WinXPCondVar::Event::IsSingleton() const {
   DCHECK(ValidateLinks());
   return next_ == this;
 }
 
 // Provide pre/post conditions to validate correct manipulations.
-bool ConditionVariable::Event::ValidateAsDistinct(Event* other) const {
+bool WinXPCondVar::Event::ValidateAsDistinct(Event* other) const {
   return ValidateLinks() && other->ValidateLinks() && (this != other);
 }
 
-bool ConditionVariable::Event::ValidateAsItem() const {
+bool WinXPCondVar::Event::ValidateAsItem() const {
   return (0 != handle_) && ValidateLinks();
 }
 
-bool ConditionVariable::Event::ValidateAsList() const {
+bool WinXPCondVar::Event::ValidateAsList() const {
   return (0 == handle_) && ValidateLinks();
 }
 
-bool ConditionVariable::Event::ValidateLinks() const {
+bool WinXPCondVar::Event::ValidateLinks() const {
   // Make sure both of our neighbors have links that point back to us.
   // We don't do the O(n) check and traverse the whole loop, and instead only
   // do a local check to (and returning from) our immediate neighbors.
   return (next_->prev_ == this) && (prev_->next_ == this);
 }
 
 
 /*
-FAQ On subtle implementation details:
+FAQ On WinXPCondVar subtle implementation details:
 
 1) What makes this problem subtle?  Please take a look at "Strategies
 for Implementing POSIX Condition Variables on Win32" by Douglas
 C. Schmidt and Irfan Pyarali.
 http://www.cs.wustl.edu/~schmidt/win32-cv-1.html It includes
 discussions of numerous flawed strategies for implementing this
 functionality.  I'm not convinced that even the final proposed
 implementation has semantics that are as nice as this implementation
 (especially with regard to Broadcast() and the impact on threads that
 try to Wait() after a Broadcast() has been called, but before all the
@@ skipping 147 matching lines @@
 use a complex and relatively low efficiency container when a doubly linked list
 provided O(1) performance in all required operations.  Since other operations
 to provide performance-and/or-fairness required queue (FIFO) and list (LIFO)
 containers, I would also have needed to use an STL list/queue as well as an STL
 map.  In the end I decided it would be "fun" to just do it right, and I
 put so many assertions (DCHECKs) into the container class that it is trivial to
 code review and validate its correctness.
 
 */
 
+ConditionVariable::ConditionVariable(Lock* user_lock)
+    : impl_(new WinXPCondVar(user_lock)) {
+}
+
+ConditionVariable::~ConditionVariable() {
+  delete impl_;
+}
+
+void ConditionVariable::Wait() {
+  impl_->Wait();
+}
+
+void ConditionVariable::TimedWait(const TimeDelta& max_time) {
+  impl_->TimedWait(max_time);
+}
+
+void ConditionVariable::Broadcast() {
+  impl_->Broadcast();
+}
+
+void ConditionVariable::Signal() {
+  impl_->Signal();
+}
+
 }  // namespace base