1 : /*
2 : * Copyright (c) 2011 The Native Client Authors. All rights reserved.
3 : * Use of this source code is governed by a BSD-style license that can be
4 : * found in the LICENSE file.
5 : */
6 :
7 :
8 : // See header file for description of class.
9 : // There are numerous subtle implementation details in this class. See the FAQ
10 : // comments at the end of this file for that discussion.
11 :
12 : #include "native_client/src/include/portability.h"
13 : #include <stack>
14 :
15 : #include "native_client/src/shared/platform/nacl_sync.h"
16 : #include "native_client/src/include/nacl_macros.h"
17 : #include "native_client/src/shared/platform/nacl_log.h"
18 : #include "native_client/src/shared/platform/nacl_time.h"
19 : #include "native_client/src/shared/platform/win/time.h"
20 : #include "native_client/src/shared/platform/win/condition_variable.h"
21 : #include "native_client/src/shared/platform/win/lock.h"
22 : #include "native_client/src/trusted/service_runtime/include/sys/time.h"
23 :
24 :
25 : NaCl::ConditionVariable::ConditionVariable()
26 : : run_state_(RUNNING),
27 : allocation_counter_(0),
28 2 : recycling_list_size_(0) {
29 2 : }
30 :
31 2 : NaCl::ConditionVariable::~ConditionVariable() {
32 2 : AutoLock auto_lock(internal_lock_);
33 2 : run_state_ = SHUTDOWN; // Prevent any more waiting.
34 :
35 : // DCHECK(recycling_list_size_ == allocation_counter_) ;
36 2 : if (recycling_list_size_ != allocation_counter_) { // Rare shutdown problem.
37 : // User left threads Wait()ing, and is destructing us.
38 : // Note: waiting_list_ *might* be empty, but recycling is still pending.
39 0 : AutoUnlock auto_unlock(internal_lock_);
40 0 : Broadcast(); // Make sure all waiting threads have been signaled.
41 0 : Sleep(10); // Give threads a chance to grab internal_lock_.
42 : // All contained threads should be blocked on user_lock_ by now :-).
43 0 : } // Re-Acquire internal_lock_
44 :
45 : // DCHECK(recycling_list_size_ == allocation_counter_); //We couldn't fix it.
46 :
47 2 : while (!recycling_list_.IsEmpty()) {
48 : ConditionVariableEvent* cv_event;
49 2 : cv_event = recycling_list_.PopFront();
50 2 : recycling_list_size_--;
51 2 : delete cv_event;
52 2 : allocation_counter_--;
53 2 : }
54 : // DCHECK(0 == recycling_list_size_);
55 : // DCHECK(0 == allocation_counter_);
56 2 : }
57 :
58 : // Wait() atomically releases the caller's lock as it starts to Wait, and then
59 : // re-acquires it when it is signaled.
60 2 : int NaCl::ConditionVariable::TimedWaitRel(Lock& user_lock, TimeDelta max_time) {
61 : ConditionVariableEvent* waiting_event;
62 : HANDLE handle;
63 : DWORD result;
64 : { /* SCOPE */
65 2 : AutoLock auto_lock(internal_lock_);
66 2 : if (RUNNING != run_state_) return 0; // Destruction in progress.
67 2 : waiting_event = GetEventForWaiting();
68 2 : handle = waiting_event->handle();
69 : // DCHECK(0 != handle);
70 2 : } // Release internal_lock.
71 :
72 : { /* SCOPE */
73 2 : AutoUnlock unlock(user_lock); // Release caller's lock
74 : result = WaitForSingleObject(handle,
75 2 : static_cast<DWORD>(max_time.InMilliseconds()));
76 : // Minimize spurious signal creation window by recycling asap.
77 2 : AutoLock auto_lock(internal_lock_);
78 2 : RecycleEvent(waiting_event);
79 : // Release internal_lack_
80 2 : } // Re-Acquire callers lock to depth at entry.
81 2 : if (WAIT_OBJECT_0 == result)
82 2 : return 1; // the object was signaled
83 0 : return 0;
84 2 : }
85 :
86 0 : static NaCl::TimeTicks NaClWinUnixTimeBaseNow() {
87 : struct nacl_abi_timeval unix_time;
88 :
89 0 : (void) NaClGetTimeOfDay(&unix_time);
90 : return NaCl::TimeTicks(
91 : unix_time.nacl_abi_tv_sec * NaCl::Time::kMicrosecondsPerSecond
92 0 : + unix_time.nacl_abi_tv_usec);
93 0 : }
94 :
95 0 : int NaCl::ConditionVariable::TimedWaitAbs(Lock& user_lock, TimeTicks abs_time) {
96 : #if 0
97 : // Test the unit test
98 : TimeDelta relative_time = TimeDelta::FromDays(1);
99 : #else
100 0 : TimeDelta relative_time = abs_time - NaClWinUnixTimeBaseNow();
101 : #endif
102 : NaClLog(4,
103 : "TimedWaitAbs: req'd abs_time %" NACL_PRId64 " ticks (uS)\n",
104 0 : abs_time.ticks_for_testing());
105 : NaClLog(4,
106 : "TimedWaitAbs: relative_time %" NACL_PRId64 " ticks (uS)\n",
107 0 : relative_time.InMicroseconds());
108 0 : if (relative_time.InMicroseconds() < 0) {
109 0 : NaClLog(4, "TimedWaitAbs: time already passed!\n");
110 : // we check to see if the object has been signaled anyway
111 0 : relative_time = TimeDelta::FromMicroseconds(0);
112 : }
113 0 : return TimedWaitRel(user_lock, relative_time);
114 0 : }
115 :
116 : // Broadcast() is guaranteed to signal all threads that were waiting (i.e., had
117 : // a cv_event internally allocated for them) before Broadcast() was called.
118 0 : void NaCl::ConditionVariable::Broadcast() {
119 0 : std::stack<HANDLE> handles; // See FAQ-question-10.
120 : { /* SCOPE */
121 0 : AutoLock auto_lock(internal_lock_);
122 0 : if (waiting_list_.IsEmpty())
123 0 : return;
124 0 : while (!waiting_list_.IsEmpty())
125 : // This is not a leak from waiting_list_. See FAQ-question 12.
126 0 : handles.push(waiting_list_.PopBack()->handle());
127 0 : } // Release internal_lock_.
128 0 : while (handles.size() > 0) {
129 0 : SetEvent(handles.top());
130 0 : handles.pop();
131 0 : }
132 0 : }
133 :
134 : // Signal() will select one of the waiting threads, and signal it (signal its
135 : // cv_event). For better performance we signal the thread that went to sleep
136 : // most recently (LIFO). If we want fairness, then we wake the thread that has
137 : // been sleeping the longest (FIFO).
138 2 : void NaCl::ConditionVariable::Signal() {
139 : HANDLE handle;
140 : { /* SCOPE */
141 2 : AutoLock auto_lock(internal_lock_);
142 2 : if (waiting_list_.IsEmpty())
143 2 : return; // No one to signal.
144 :
145 : #ifndef FAIRNESS
146 : // Only performance option should be used.
147 : // This is not a leak from waiting_list. See FAQ-question 12.
148 2 : handle = waiting_list_.PopBack()->handle(); // LIFO.
149 : #else
150 : handle = waiting_list_.PopFront()->handle(); // FIFO.
151 : #endif // FAIRNESS
152 2 : } // Release internal_lock_.
153 2 : SetEvent(handle);
154 2 : }
155 :
156 : // GetEventForWaiting() provides a unique cv_event for any caller that needs to
157 : // wait. This means that (worst case) we may over time create as many cv_event
158 : // objects as there are threads simultaneously using this instance's Wait()
159 : // functionality .
160 2 : NaCl::ConditionVariableEvent* NaCl::ConditionVariable::GetEventForWaiting() {
161 : // We hold internal_lock, courtesy of Wait().
162 : ConditionVariableEvent* cv_event;
163 2 : if (0 == recycling_list_size_) {
164 : // DCHECK(recycling_list_.IsEmpty());
165 2 : cv_event = new ConditionVariableEvent(true);
166 : // CHECK(cv_event);
167 2 : allocation_counter_++;
168 : // CHECK(0 != cv_event->handle());
169 2 : } else {
170 2 : cv_event = recycling_list_.PopFront();
171 2 : recycling_list_size_--;
172 : }
173 2 : waiting_list_.PushBack(cv_event);
174 2 : return cv_event;
175 2 : }
176 :
177 : // RecycleEvent() takes a cv_event that was previously used for Wait()ing, and
178 : // recycles it for use in future Wait() calls for this or other threads.
179 : // Note that there is a tiny chance that the cv_event is still signaled when we
180 : // obtain it, and that can cause spurious signals (if/when we re-use the
181 : // cv_event), but such is quite rare (see FAQ-question-5).
182 2 : void NaCl::ConditionVariable::RecycleEvent(ConditionVariableEvent* used_event) {
183 : // We hold internal_lock, courtesy of Wait().
184 : // If the cv_event timed out, then it is necessary to remove it from
185 : // waiting_list_. If it was selected by Broadcast() or Signal(), then it is
186 : // already gone.
187 2 : used_event->Extract(); // Possibly redundant
188 2 : recycling_list_.PushBack(used_event);
189 2 : recycling_list_size_++;
190 2 : }
191 :
192 : /*
193 : FAQ On subtle implementation details:
194 :
195 : 1) What makes this problem subtle? Please take a look at "Strategies
196 : for Implementing POSIX Condition Variables on Win32" by Douglas
197 : C. Schmidt and Irfan Pyarali.
198 : http://www.cs.wustl.edu/~schmidt/win32-cv-1.html It includes
199 : discussions of numerous flawed strategies for implementing this
200 : functionality. I'm not convinced that even the final proposed
201 : implementation has semantics that are as nice as this implementation
202 : (especially with regard to Broadcast() and the impact on threads that
203 : try to Wait() after a Broadcast() has been called, but before all the
204 : original waiting threads have been signaled).
205 :
206 : 2) Why can't you use a single wait_event for all threads that call
207 : Wait()? See FAQ-question-1, or consider the following: If a single
208 : event were used, then numerous threads calling Wait() could release
209 : their cs locks, and be preempted just before calling
210 : WaitForSingleObject(). If a call to Broadcast() was then presented on
211 : a second thread, it would be impossible to actually signal all
212 : waiting(?) threads. Some number of SetEvent() calls *could* be made,
213 : but there could be no guarantee that those led to to more than one
214 : signaled thread (SetEvent()'s may be discarded after the first!), and
215 : there could be no guarantee that the SetEvent() calls didn't just
216 : awaken "other" threads that hadn't even started waiting yet (oops).
217 : Without any limit on the number of requisite SetEvent() calls, the
218 : system would be forced to do many such calls, allowing many new waits
219 : to receive spurious signals.
220 :
221 : 3) How does this implementation cause spurious signal events? The
222 : cause in this implementation involves a race between a signal via
223 : time-out and a signal via Signal() or Broadcast(). The series of
224 : actions leading to this are:
225 :
226 : a) Timer fires, and a waiting thread exits the line of code:
227 :
228 : WaitForSingleObject(waiting_event, max_time.InMilliseconds());
229 :
230 : b) That thread (in (a)) is randomly pre-empted after the above line,
231 : leaving the waiting_event reset (unsignaled) and still in the
232 : waiting_list_.
233 :
234 : c) A call to Signal() (or Broadcast()) on a second thread proceeds, and
235 : selects the waiting cv_event (identified in step (b)) as the event to revive
236 : via a call to SetEvent().
237 :
238 : d) The Signal() method (step c) calls SetEvent() on waiting_event (step b).
239 :
240 : e) The waiting cv_event (step b) is now signaled, but no thread is
241 : waiting on it.
242 :
243 : f) When that waiting_event (step b) is reused, it will immediately
244 : be signaled (spuriously).
245 :
246 :
247 : 4) Why do you recycle events, and cause spurious signals? First off,
248 : the spurious events are very rare. They can only (I think) appear
249 : when the race described in FAQ-question-3 takes place. This should be
250 : very rare. Most(?) uses will involve only timer expiration, or only
251 : Signal/Broadcast() actions. When both are used, it will be rare that
252 : the race will appear, and it would require MANY Wait() and signaling
253 : activities. If this implementation did not recycle events, then it
254 : would have to create and destroy events for every call to Wait().
255 : That allocation/deallocation and associated construction/destruction
256 : would be costly (per wait), and would only be a rare benefit (when the
257 : race was "lost" and a spurious signal took place). That would be bad
258 : (IMO) optimization trade-off. Finally, such spurious events are
259 : allowed by the specification of condition variables (such as
260 : implemented in Vista), and hence it is better if any user accommodates
261 : such spurious events (see usage note in condition_variable.h).
262 :
263 : 5) Why don't you reset events when you are about to recycle them, or
264 : about to reuse them, so that the spurious signals don't take place?
265 : The thread described in FAQ-question-3 step c may be pre-empted for an
266 : arbitrary length of time before proceeding to step d. As a result,
267 : the wait_event may actually be re-used *before* step (e) is reached.
268 : As a result, calling reset would not help significantly.
269 :
270 : 6) How is it that the callers lock is released atomically with the
271 : entry into a wait state? We commit to the wait activity when we
272 : allocate the wait_event for use in a given call to Wait(). This
273 : allocation takes place before the caller's lock is released (and
274 : actually before our internal_lock_ is released). That allocation is
275 : the defining moment when "the wait state has been entered," as that
276 : thread *can* now be signaled by a call to Broadcast() or Signal().
277 : Hence we actually "commit to wait" before releasing the lock, making
278 : the pair effectively atomic.
279 :
280 : 8) Why do you need to lock your data structures during waiting, as the
281 : caller is already in possession of a lock? We need to Acquire() and
282 : Release() our internal lock during Signal() and Broadcast(). If we tried
283 : to use a callers lock for this purpose, we might conflict with their
284 : external use of the lock. For example, the caller may use to consistently
285 : hold a lock on one thread while calling Signal() on another, and that would
286 : block Signal().
287 :
288 : 9) Couldn't a more efficient implementation be provided if you
289 : preclude using more than one external lock in conjunction with a
290 : single ConditionVariable instance? Yes, at least it could be viewed
291 : as a simpler API (since you don't have to reiterate the lock argument
292 : in each Wait() call). One of the constructors now takes a specific
293 : lock as an argument, and a there are corresponding Wait() calls that
294 : don't specify a lock now. It turns that the resulting implmentation
295 : can't be made more efficient, as the internal lock needs to be used by
296 : Signal() and Broadcast(), to access internal data structures. As a
297 : result, I was not able to utilize the user supplied lock (which is
298 : being used by the user elsewhere presumably) to protect the private
299 : member access.
300 :
301 : 9) Since you have a second lock, how can be be sure that there is no
302 : possible deadlock scenario? Our internal_lock_ is always the last
303 : lock acquired, and the first one released, and hence a deadlock (due
304 : to critical section problems) is impossible as a consequence of our
305 : lock.
306 :
307 : 10) When doing a Broadcast(), why did you copy all the events into
308 : an STL queue, rather than making a linked-loop, and iterating over it?
309 : The iterating during Broadcast() is done so outside the protection
310 : of the internal lock. As a result, other threads, such as the thread
311 : wherein a related event is waiting, could asynchronously manipulate
312 : the links around a cv_event. As a result, the link structure cannot
313 : be used outside a lock. Broadcast() could iterate over waiting
314 : events by cycling in-and-out of the protection of the internal_lock,
315 : but that appears more expensive than copying the list into an STL
316 : stack.
317 :
318 : 11) Why did the lock.h file need to be modified so much for this
319 : change? Central to a Condition Variable is the atomic release of a
320 : lock during a Wait(). This places Wait() functionality exactly
321 : mid-way between the two classes, Lock and Condition Variable. Given
322 : that there can be nested Acquire()'s of locks, and Wait() had to
323 : Release() completely a held lock, it was necessary to augment the Lock
324 : class with a recursion counter. Even more subtle is the fact that the
325 : recursion counter (in a Lock) must be protected, as many threads can
326 : access it asynchronously. As a positive fallout of this, there are
327 : now some DCHECKS to be sure no one Release()s a Lock more than they
328 : Acquire()ed it, and there is ifdef'ed functionality that can detect
329 : nested locks (legal under windows, but not under Posix).
330 :
331 : 12) Why is it that the cv_events removed from list in Broadcast() and Signal()
332 : are not leaked? How are they recovered?? The cv_events that appear to leak are
333 : taken from the waiting_list_. For each element in that list, there is currently
334 : a thread in or around the WaitForSingleObject() call of Wait(), and those
335 : threads have references to these otherwise leaked events. They are passed as
336 : arguments to be recycled just aftre returning from WaitForSingleObject().
337 :
338 : 13) Why did you use a custom container class (the linked list), when STL has
339 : perfectly good containers, such as an STL list? The STL list, as with any
340 : container, does not guarantee the utility of an iterator across manipulation
341 : (such as insertions and deletions) of the underlying container. The custom
342 : double-linked-list container provided that assurance. I don't believe any
343 : combination of STL containers provided the services that were needed at the same
344 : O(1) efficiency as the custom linked list. The unusual requirement
345 : for the container class is that a reference to an item within a container (an
346 : iterator) needed to be maintained across an arbitrary manipulation of the
347 : container. This requirement exposes itself in the Wait() method, where a
348 : waiting_event must be selected prior to the WaitForSingleObject(), and then it
349 : must be used as part of recycling to remove the related instance from the
350 : waiting_list. A hash table (STL map) could be used, but I was embarrased to
351 : use a complex and relatively low efficiency container when a doubly linked list
352 : provided O(1) performance in all required operations. Since other operations
353 : to provide performance-and/or-fairness required queue (FIFO) and list (LIFO)
354 : containers, I would also have needed to use an STL list/queue as well as an STL
355 : map. In the end I decided it would be "fun" to just do it right, and I
356 : put so many assertions (DCHECKs) into the container class that it is trivial to
357 : code review and validate its correctness.
358 :
359 : */
|
