1 // Copyright (c) 2006-2008 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 // ConditionVariable wraps pthreads condition variable synchronization or, on 6 // Windows, simulates it. This functionality is very helpful for having 7 // several threads wait for an event, as is common with a thread pool managed 8 // by a master. The meaning of such an event in the (worker) thread pool 9 // scenario is that additional tasks are now available for processing. It is 10 // used in Chrome in the DNS prefetching system to notify worker threads that 11 // a queue now has items (tasks) which need to be tended to. A related use 12 // would have a pool manager waiting on a ConditionVariable, waiting for a 13 // thread in the pool to announce (signal) that there is now more room in a 14 // (bounded size) communications queue for the manager to deposit tasks, or, 15 // as a second example, that the queue of tasks is completely empty and all 16 // workers are waiting. 17 // 18 // USAGE NOTE 1: spurious signal events are possible with this and 19 // most implementations of condition variables. As a result, be 20 // *sure* to retest your condition before proceeding. The following 21 // is a good example of doing this correctly: 22 // 23 // while (!work_to_be_done()) Wait(...); 24 // 25 // In contrast do NOT do the following: 26 // 27 // if (!work_to_be_done()) Wait(...); // Don't do this. 28 // 29 // Especially avoid the above if you are relying on some other thread only 30 // issuing a signal up *if* there is work-to-do. There can/will 31 // be spurious signals. Recheck state on waiting thread before 32 // assuming the signal was intentional. Caveat caller ;-). 33 // 34 // USAGE NOTE 2: Broadcast() frees up all waiting threads at once, 35 // which leads to contention for the locks they all held when they 36 // called Wait(). This results in POOR performance. A much better 37 // approach to getting a lot of threads out of Wait() is to have each 38 // thread (upon exiting Wait()) call Signal() to free up another 39 // Wait'ing thread. Look at condition_variable_unittest.cc for 40 // both examples. 41 // 42 // Broadcast() can be used nicely during teardown, as it gets the job 43 // done, and leaves no sleeping threads... and performance is less 44 // critical at that point. 45 // 46 // The semantics of Broadcast() are carefully crafted so that *all* 47 // threads that were waiting when the request was made will indeed 48 // get signaled. Some implementations mess up, and don't signal them 49 // all, while others allow the wait to be effectively turned off (for 50 // a while while waiting threads come around). This implementation 51 // appears correct, as it will not "lose" any signals, and will guarantee 52 // that all threads get signaled by Broadcast(). 53 // 54 // This implementation offers support for "performance" in its selection of 55 // which thread to revive. Performance, in direct contrast with "fairness," 56 // assures that the thread that most recently began to Wait() is selected by 57 // Signal to revive. Fairness would (if publicly supported) assure that the 58 // thread that has Wait()ed the longest is selected. The default policy 59 // may improve performance, as the selected thread may have a greater chance of 60 // having some of its stack data in various CPU caches. 61 // 62 // For a discussion of the many very subtle implementation details, see the FAQ 63 // at the end of condition_variable_win.cc. 64 65 #ifndef BASE_CONDITION_VARIABLE_H_ 66 #define BASE_CONDITION_VARIABLE_H_ 67 68 #include "build/build_config.h" 69 70 #if defined(OS_WIN) 71 #include <windows.h> 72 #elif defined(OS_POSIX) 73 #include <pthread.h> 74 #endif 75 76 #include "base/basictypes.h" 77 #include "base/lock.h" 78 79 namespace base { 80 class TimeDelta; 81 } 82 83 class ConditionVariable { 84 public: 85 // Construct a cv for use with ONLY one user lock. 86 explicit ConditionVariable(Lock* user_lock); 87 88 ~ConditionVariable(); 89 90 // Wait() releases the caller's critical section atomically as it starts to 91 // sleep, and the reacquires it when it is signaled. 92 void Wait(); 93 void TimedWait(const base::TimeDelta& max_time); 94 95 // Broadcast() revives all waiting threads. 96 void Broadcast(); 97 // Signal() revives one waiting thread. 98 void Signal(); 99 100 private: 101 102 #if defined(OS_WIN) 103 104 // Define Event class that is used to form circularly linked lists. 105 // The list container is an element with NULL as its handle_ value. 106 // The actual list elements have a non-zero handle_ value. 107 // All calls to methods MUST be done under protection of a lock so that links 108 // can be validated. Without the lock, some links might asynchronously 109 // change, and the assertions would fail (as would list change operations). 110 class Event { 111 public: 112 // Default constructor with no arguments creates a list container. 113 Event(); 114 ~Event(); 115 116 // InitListElement transitions an instance from a container, to an element. 117 void InitListElement(); 118 119 // Methods for use on lists. 120 bool IsEmpty() const; 121 void PushBack(Event* other); 122 Event* PopFront(); 123 Event* PopBack(); 124 125 // Methods for use on list elements. 126 // Accessor method. 127 HANDLE handle() const; 128 // Pull an element from a list (if it's in one). 129 Event* Extract(); 130 131 // Method for use on a list element or on a list. 132 bool IsSingleton() const; 133 134 private: 135 // Provide pre/post conditions to validate correct manipulations. 136 bool ValidateAsDistinct(Event* other) const; 137 bool ValidateAsItem() const; 138 bool ValidateAsList() const; 139 bool ValidateLinks() const; 140 141 HANDLE handle_; 142 Event* next_; 143 Event* prev_; 144 DISALLOW_COPY_AND_ASSIGN(Event); 145 }; 146 147 // Note that RUNNING is an unlikely number to have in RAM by accident. 148 // This helps with defensive destructor coding in the face of user error. 149 enum RunState { SHUTDOWN = 0, RUNNING = 64213 }; 150 151 // Internal implementation methods supporting Wait(). 152 Event* GetEventForWaiting(); 153 void RecycleEvent(Event* used_event); 154 155 RunState run_state_; 156 157 // Private critical section for access to member data. 158 Lock internal_lock_; 159 160 // Lock that is acquired before calling Wait(). 161 Lock& user_lock_; 162 163 // Events that threads are blocked on. 164 Event waiting_list_; 165 166 // Free list for old events. 167 Event recycling_list_; 168 int recycling_list_size_; 169 170 // The number of allocated, but not yet deleted events. 171 int allocation_counter_; 172 173 #elif defined(OS_POSIX) 174 175 pthread_cond_t condition_; 176 pthread_mutex_t* user_mutex_; 177 178 #endif 179 180 DISALLOW_COPY_AND_ASSIGN(ConditionVariable); 181 }; 182 183 #endif // BASE_CONDITION_VARIABLE_H_ 184