1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
|
// Copyright (c) 2006-2008 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/condition_variable.h"
#include <stack>
#include "base/lock.h"
#include "base/logging.h"
#include "base/time.h"
using base::TimeDelta;
ConditionVariable::ConditionVariable(Lock* user_lock)
: user_lock_(*user_lock),
run_state_(RUNNING),
allocation_counter_(0),
recycling_list_size_(0) {
DCHECK(user_lock);
}
ConditionVariable::~ConditionVariable() {
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() {
// 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) {
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() {
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() {
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() {
// 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_++;
// CHECK_NE is not defined in our codebase, so we have to use CHECK
CHECK(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) {
// 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.
//------------------------------------------------------------------------------
// Event provides a doubly-linked-list of events for use exclusively by the
// ConditionVariable class.
// This custom container was crafted because no simple combination of STL
// classes appeared to support the functionality required. The specific
// unusual requirement for a linked-list-class is support for the Extract()
// method, which can remove an element from a list, potentially for insertion
// into a second list. Most critically, the Extract() method is idempotent,
// turning the indicated element into an extracted singleton whether it was
// contained in a list or not. This functionality allows one (or more) of
// threads to do the extraction. The iterator that identifies this extractable
// element (in this case, a pointer to the list element) can be used after
// arbitrary manipulation of the (possibly) enclosing list container. In
// general, STL containers do not provide iterators that can be used across
// modifications (insertions/extractions) of the enclosing containers, and
// 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) {
next_ = prev_ = this; // Self referencing circular.
}
ConditionVariable::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() {
DCHECK(!handle_);
handle_ = CreateEvent(NULL, false, false, NULL);
CHECK(handle_);
}
// Methods for use on lists.
bool ConditionVariable::Event::IsEmpty() const {
DCHECK(ValidateAsList());
return IsSingleton();
}
void ConditionVariable::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() {
DCHECK(ValidateAsList());
DCHECK(!IsSingleton());
return next_->Extract();
}
ConditionVariable::Event* ConditionVariable::Event::PopBack() {
DCHECK(ValidateAsList());
DCHECK(!IsSingleton());
return prev_->Extract();
}
// Methods for use on list elements.
// Accessor method.
HANDLE ConditionVariable::Event::handle() const {
DCHECK(ValidateAsItem());
return handle_;
}
// Pull an element from a list (if it's in one).
ConditionVariable::Event* ConditionVariable::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 {
DCHECK(ValidateLinks());
return next_ == this;
}
// Provide pre/post conditions to validate correct manipulations.
bool ConditionVariable::Event::ValidateAsDistinct(Event* other) const {
return ValidateLinks() && other->ValidateLinks() && (this != other);
}
bool ConditionVariable::Event::ValidateAsItem() const {
return (0 != handle_) && ValidateLinks();
}
bool ConditionVariable::Event::ValidateAsList() const {
return (0 == handle_) && ValidateLinks();
}
bool ConditionVariable::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:
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
original waiting threads have been signaled).
2) Why can't you use a single wait_event for all threads that call
Wait()? See FAQ-question-1, or consider the following: If a single
event were used, then numerous threads calling Wait() could release
their cs locks, and be preempted just before calling
WaitForSingleObject(). If a call to Broadcast() was then presented on
a second thread, it would be impossible to actually signal all
waiting(?) threads. Some number of SetEvent() calls *could* be made,
but there could be no guarantee that those led to to more than one
signaled thread (SetEvent()'s may be discarded after the first!), and
there could be no guarantee that the SetEvent() calls didn't just
awaken "other" threads that hadn't even started waiting yet (oops).
Without any limit on the number of requisite SetEvent() calls, the
system would be forced to do many such calls, allowing many new waits
to receive spurious signals.
3) How does this implementation cause spurious signal events? The
cause in this implementation involves a race between a signal via
time-out and a signal via Signal() or Broadcast(). The series of
actions leading to this are:
a) Timer fires, and a waiting thread exits the line of code:
WaitForSingleObject(waiting_event, max_time.InMilliseconds());
b) That thread (in (a)) is randomly pre-empted after the above line,
leaving the waiting_event reset (unsignaled) and still in the
waiting_list_.
c) A call to Signal() (or Broadcast()) on a second thread proceeds, and
selects the waiting cv_event (identified in step (b)) as the event to revive
via a call to SetEvent().
d) The Signal() method (step c) calls SetEvent() on waiting_event (step b).
e) The waiting cv_event (step b) is now signaled, but no thread is
waiting on it.
f) When that waiting_event (step b) is reused, it will immediately
be signaled (spuriously).
4) Why do you recycle events, and cause spurious signals? First off,
the spurious events are very rare. They can only (I think) appear
when the race described in FAQ-question-3 takes place. This should be
very rare. Most(?) uses will involve only timer expiration, or only
Signal/Broadcast() actions. When both are used, it will be rare that
the race will appear, and it would require MANY Wait() and signaling
activities. If this implementation did not recycle events, then it
would have to create and destroy events for every call to Wait().
That allocation/deallocation and associated construction/destruction
would be costly (per wait), and would only be a rare benefit (when the
race was "lost" and a spurious signal took place). That would be bad
(IMO) optimization trade-off. Finally, such spurious events are
allowed by the specification of condition variables (such as
implemented in Vista), and hence it is better if any user accommodates
such spurious events (see usage note in condition_variable.h).
5) Why don't you reset events when you are about to recycle them, or
about to reuse them, so that the spurious signals don't take place?
The thread described in FAQ-question-3 step c may be pre-empted for an
arbitrary length of time before proceeding to step d. As a result,
the wait_event may actually be re-used *before* step (e) is reached.
As a result, calling reset would not help significantly.
6) How is it that the callers lock is released atomically with the
entry into a wait state? We commit to the wait activity when we
allocate the wait_event for use in a given call to Wait(). This
allocation takes place before the caller's lock is released (and
actually before our internal_lock_ is released). That allocation is
the defining moment when "the wait state has been entered," as that
thread *can* now be signaled by a call to Broadcast() or Signal().
Hence we actually "commit to wait" before releasing the lock, making
the pair effectively atomic.
8) Why do you need to lock your data structures during waiting, as the
caller is already in possession of a lock? We need to Acquire() and
Release() our internal lock during Signal() and Broadcast(). If we tried
to use a callers lock for this purpose, we might conflict with their
external use of the lock. For example, the caller may use to consistently
hold a lock on one thread while calling Signal() on another, and that would
block Signal().
9) Couldn't a more efficient implementation be provided if you
preclude using more than one external lock in conjunction with a
single ConditionVariable instance? Yes, at least it could be viewed
as a simpler API (since you don't have to reiterate the lock argument
in each Wait() call). One of the constructors now takes a specific
lock as an argument, and a there are corresponding Wait() calls that
don't specify a lock now. It turns that the resulting implmentation
can't be made more efficient, as the internal lock needs to be used by
Signal() and Broadcast(), to access internal data structures. As a
result, I was not able to utilize the user supplied lock (which is
being used by the user elsewhere presumably) to protect the private
member access.
9) Since you have a second lock, how can be be sure that there is no
possible deadlock scenario? Our internal_lock_ is always the last
lock acquired, and the first one released, and hence a deadlock (due
to critical section problems) is impossible as a consequence of our
lock.
10) When doing a Broadcast(), why did you copy all the events into
an STL queue, rather than making a linked-loop, and iterating over it?
The iterating during Broadcast() is done so outside the protection
of the internal lock. As a result, other threads, such as the thread
wherein a related event is waiting, could asynchronously manipulate
the links around a cv_event. As a result, the link structure cannot
be used outside a lock. Broadcast() could iterate over waiting
events by cycling in-and-out of the protection of the internal_lock,
but that appears more expensive than copying the list into an STL
stack.
11) Why did the lock.h file need to be modified so much for this
change? Central to a Condition Variable is the atomic release of a
lock during a Wait(). This places Wait() functionality exactly
mid-way between the two classes, Lock and Condition Variable. Given
that there can be nested Acquire()'s of locks, and Wait() had to
Release() completely a held lock, it was necessary to augment the Lock
class with a recursion counter. Even more subtle is the fact that the
recursion counter (in a Lock) must be protected, as many threads can
access it asynchronously. As a positive fallout of this, there are
now some DCHECKS to be sure no one Release()s a Lock more than they
Acquire()ed it, and there is ifdef'ed functionality that can detect
nested locks (legal under windows, but not under Posix).
12) Why is it that the cv_events removed from list in Broadcast() and Signal()
are not leaked? How are they recovered?? The cv_events that appear to leak are
taken from the waiting_list_. For each element in that list, there is currently
a thread in or around the WaitForSingleObject() call of Wait(), and those
threads have references to these otherwise leaked events. They are passed as
arguments to be recycled just aftre returning from WaitForSingleObject().
13) Why did you use a custom container class (the linked list), when STL has
perfectly good containers, such as an STL list? The STL list, as with any
container, does not guarantee the utility of an iterator across manipulation
(such as insertions and deletions) of the underlying container. The custom
double-linked-list container provided that assurance. I don't believe any
combination of STL containers provided the services that were needed at the same
O(1) efficiency as the custom linked list. The unusual requirement
for the container class is that a reference to an item within a container (an
iterator) needed to be maintained across an arbitrary manipulation of the
container. This requirement exposes itself in the Wait() method, where a
waiting_event must be selected prior to the WaitForSingleObject(), and then it
must be used as part of recycling to remove the related instance from the
waiting_list. A hash table (STL map) could be used, but I was embarrased to
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.
*/
|