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: // ConditionVariable wraps pthreads condition variable synchronization or, on michael@0: // Windows, simulates it. This functionality is very helpful for having michael@0: // several threads wait for an event, as is common with a thread pool managed michael@0: // by a master. The meaning of such an event in the (worker) thread pool michael@0: // scenario is that additional tasks are now available for processing. It is michael@0: // used in Chrome in the DNS prefetching system to notify worker threads that michael@0: // a queue now has items (tasks) which need to be tended to. A related use michael@0: // would have a pool manager waiting on a ConditionVariable, waiting for a michael@0: // thread in the pool to announce (signal) that there is now more room in a michael@0: // (bounded size) communications queue for the manager to deposit tasks, or, michael@0: // as a second example, that the queue of tasks is completely empty and all michael@0: // workers are waiting. michael@0: // michael@0: // USAGE NOTE 1: spurious signal events are possible with this and michael@0: // most implementations of condition variables. As a result, be michael@0: // *sure* to retest your condition before proceeding. The following michael@0: // is a good example of doing this correctly: michael@0: // michael@0: // while (!work_to_be_done()) Wait(...); michael@0: // michael@0: // In contrast do NOT do the following: michael@0: // michael@0: // if (!work_to_be_done()) Wait(...); // Don't do this. michael@0: // michael@0: // Especially avoid the above if you are relying on some other thread only michael@0: // issuing a signal up *if* there is work-to-do. There can/will michael@0: // be spurious signals. Recheck state on waiting thread before michael@0: // assuming the signal was intentional. Caveat caller ;-). michael@0: // michael@0: // USAGE NOTE 2: Broadcast() frees up all waiting threads at once, michael@0: // which leads to contention for the locks they all held when they michael@0: // called Wait(). This results in POOR performance. A much better michael@0: // approach to getting a lot of threads out of Wait() is to have each michael@0: // thread (upon exiting Wait()) call Signal() to free up another michael@0: // Wait'ing thread. Look at condition_variable_unittest.cc for michael@0: // both examples. michael@0: // michael@0: // Broadcast() can be used nicely during teardown, as it gets the job michael@0: // done, and leaves no sleeping threads... and performance is less michael@0: // critical at that point. michael@0: // michael@0: // The semantics of Broadcast() are carefully crafted so that *all* michael@0: // threads that were waiting when the request was made will indeed michael@0: // get signaled. Some implementations mess up, and don't signal them michael@0: // all, while others allow the wait to be effectively turned off (for michael@0: // a while while waiting threads come around). This implementation michael@0: // appears correct, as it will not "lose" any signals, and will guarantee michael@0: // that all threads get signaled by Broadcast(). michael@0: // michael@0: // This implementation offers support for "performance" in its selection of michael@0: // which thread to revive. Performance, in direct contrast with "fairness," michael@0: // assures that the thread that most recently began to Wait() is selected by michael@0: // Signal to revive. Fairness would (if publicly supported) assure that the michael@0: // thread that has Wait()ed the longest is selected. The default policy michael@0: // may improve performance, as the selected thread may have a greater chance of michael@0: // having some of its stack data in various CPU caches. michael@0: // michael@0: // For a discussion of the many very subtle implementation details, see the FAQ michael@0: // at the end of condition_variable_win.cc. michael@0: michael@0: #ifndef BASE_CONDITION_VARIABLE_H_ michael@0: #define BASE_CONDITION_VARIABLE_H_ michael@0: michael@0: #include "base/lock.h" michael@0: michael@0: namespace base { michael@0: class TimeDelta; michael@0: } michael@0: michael@0: class ConditionVariable { michael@0: public: michael@0: // Construct a cv for use with ONLY one user lock. michael@0: explicit ConditionVariable(Lock* user_lock); michael@0: michael@0: ~ConditionVariable(); michael@0: michael@0: // Wait() releases the caller's critical section atomically as it starts to michael@0: // sleep, and the reacquires it when it is signaled. michael@0: void Wait(); michael@0: void TimedWait(const base::TimeDelta& max_time); michael@0: michael@0: // Broadcast() revives all waiting threads. michael@0: void Broadcast(); michael@0: // Signal() revives one waiting thread. michael@0: void Signal(); michael@0: michael@0: private: michael@0: michael@0: #if defined(OS_WIN) michael@0: michael@0: // Define Event class that is used to form circularly linked lists. michael@0: // The list container is an element with NULL as its handle_ value. michael@0: // The actual list elements have a non-zero handle_ value. michael@0: // All calls to methods MUST be done under protection of a lock so that links michael@0: // can be validated. Without the lock, some links might asynchronously michael@0: // change, and the assertions would fail (as would list change operations). michael@0: class Event { michael@0: public: michael@0: // Default constructor with no arguments creates a list container. michael@0: Event(); michael@0: ~Event(); michael@0: michael@0: // InitListElement transitions an instance from a container, to an element. michael@0: void InitListElement(); michael@0: michael@0: // Methods for use on lists. michael@0: bool IsEmpty() const; michael@0: void PushBack(Event* other); michael@0: Event* PopFront(); michael@0: Event* PopBack(); michael@0: michael@0: // Methods for use on list elements. michael@0: // Accessor method. michael@0: HANDLE handle() const; michael@0: // Pull an element from a list (if it's in one). michael@0: Event* Extract(); michael@0: michael@0: // Method for use on a list element or on a list. michael@0: bool IsSingleton() const; michael@0: michael@0: private: michael@0: // Provide pre/post conditions to validate correct manipulations. michael@0: bool ValidateAsDistinct(Event* other) const; michael@0: bool ValidateAsItem() const; michael@0: bool ValidateAsList() const; michael@0: bool ValidateLinks() const; michael@0: michael@0: HANDLE handle_; michael@0: Event* next_; michael@0: Event* prev_; michael@0: DISALLOW_COPY_AND_ASSIGN(Event); michael@0: }; michael@0: michael@0: // Note that RUNNING is an unlikely number to have in RAM by accident. michael@0: // This helps with defensive destructor coding in the face of user error. michael@0: enum RunState { SHUTDOWN = 0, RUNNING = 64213 }; michael@0: michael@0: // Internal implementation methods supporting Wait(). michael@0: Event* GetEventForWaiting(); michael@0: void RecycleEvent(Event* used_event); michael@0: michael@0: RunState run_state_; michael@0: michael@0: // Private critical section for access to member data. michael@0: Lock internal_lock_; michael@0: michael@0: // Lock that is acquired before calling Wait(). michael@0: Lock& user_lock_; michael@0: michael@0: // Events that threads are blocked on. michael@0: Event waiting_list_; michael@0: michael@0: // Free list for old events. michael@0: Event recycling_list_; michael@0: int recycling_list_size_; michael@0: michael@0: // The number of allocated, but not yet deleted events. michael@0: int allocation_counter_; michael@0: michael@0: #elif defined(OS_POSIX) michael@0: michael@0: pthread_cond_t condition_; michael@0: pthread_mutex_t* user_mutex_; michael@0: michael@0: #endif michael@0: michael@0: DISALLOW_COPY_AND_ASSIGN(ConditionVariable); michael@0: }; michael@0: michael@0: #endif // BASE_CONDITION_VARIABLE_H_