C++ multithreading: yet another Win32 condvar implementation
Sergey P. Derevyago
was a simple Win32 implementation of cond_var interface
http://ders.stml.net/cpp/mtprog/doc/thread_8hpp-source.html
So here it is:
http://ders.stml.net/cpp/mtprog/doc/win32_2mt__threadimpl_8cpp-source.html
P.S. The code lives here: http://ders.stml.net/cpp/mtprog/code.zip You
can (indirectly) test win_cond_var with mtprog\derslib\tst\tst_bar.cpp
--
With all respect, Sergey. http://ders.stml.net/
mailto : ders at skeptik.net
Dmitriy V'jukov
wrote:
> One of the tutorialhttp://ders.stml.net/cpp/mtprog/mtprog.htmlissues
> was a simple Win32 implementation of cond_var interfacehttp://ders.stml.net/cpp/mtprog/doc/thread_8hpp-source.html
>
> So here it is:http://ders.stml.net/cpp/mtprog/doc/win32_2mt__threadimpl_8cpp-source...
>
> P.S. The code lives here:http://ders.stml.net/cpp/mtprog/code.zipYou
> can (indirectly) test win_cond_var with mtprog\derslib\tst\tst_bar.cpp
It seems that you assume that notify()/notify_all() functions will be
called under mutex. Right?
Dmitriy V'jukov
Sergey P. Derevyago
> It seems that you assume that notify()/notify_all() functions will be
> called under mutex. Right?
>
P.S. Sorry, no time for good dox ;(
Chris M. Thomasson
news:48a18ec5$0$90270$1472...@news.sunsite.dk...
> One of the tutorial http://ders.stml.net/cpp/mtprog/mtprog.html issues was
> a simple Win32 implementation of cond_var interface
> http://ders.stml.net/cpp/mtprog/doc/thread_8hpp-source.html
>
> So here it is:
> http://ders.stml.net/cpp/mtprog/doc/win32_2mt__threadimpl_8cpp-source.html
>
> P.S. The code lives here: http://ders.stml.net/cpp/mtprog/code.zip You can
> (indirectly) test win_cond_var with mtprog\derslib\tst\tst_bar.cpp
What if I wanted to reuse the condvar instead of destroying it, and have it
wait on a different mutex? This is complete legitimate. Also, you seem to
assume that a mutex will be held during calls to your notification
functions. You can call a notification function without the mutex held. One
other point, your only going to get SCHED_OTHER with this setup because your
constructing the wait-queue yourself. Also, in your event_cache object...
What happens if I return a signaled event to the cache? You should probably
do something like:
void event_cache::returnEvent(HANDLE ev)
00171 {
00172 assert(ev!=0);
ResetEvent(ev);
00173 try { evs.push_back(ev); }
00174 catch (...) {
00175 CloseHandle(ev);
00176 throw;
00177 }
00178 }
to ensure its reset before putting it back into the queue. Do you document
that its okay to return signaled event to event_cache?
You should probablly change the class to:
struct win_cond_var : public cond_var {
00069 mutex pm;
00070 event_cache evc;
00071 vector<HANDLE> wts;
00072
00073 win_cond_var(mutex& mtx);
00074 ~win_cond_var();
00075
00076 virtual bool wait(mutex& um, long timeout);
00077 virtual void notify();
00078 virtual void notify_all();
00079
00080 virtual void destroy(mem_pool& mp2) { destroy_this(this,
mp2); }
00081 };
and do something like:
bool win_cond_var::wait(mutex& m, long timeout)
00191 {
bool status = true;
pm.lock();
00192 HANDLE ev=evc.getEvent();
00193 try { wts.push_back(ev); }
00194 catch (...) {
00195 CloseHandle(ev);
00196 throw;
00197 }
pm.unlock();
00198
00199 m.unlock();
00200
00201 DWORD rcd=WaitForSingleObject(ev, (timeout==infinite) ? timeout :
INFINITE);
00202 hard_assert(rcd==WAIT_OBJECT_0 || rcd==WAIT_TIMEOUT);
00203
00204 m.lock();
pm.lock();
00205
00206 if (rcd==WAIT_TIMEOUT) {
00207 vector<HANDLE>::iterator it=find(wts.begin(), wts.end(), ev);
00208 if (it==wts.end()) {
00209 BOOL rc=ResetEvent(ev);
00210 hard_assert(rc!=0);
00211 }
00212 else wts.erase(it);
status = false;
00213 }
00214
00215 evc.returnEvent(ev);
pm.unlock();
return status;
00216 }
00218 void win_cond_var::notify()
00219 {
pm.lock();
00220 if (wts.size()==0) { pm.unlock(); return; }
00221
00222 HANDLE ev=wts.back();
00223 wts.pop_back();
00224
00225 BOOL rc=SetEvent(ev);
00226 hard_assert(rc!=0);
pm.unlock();
00227 }
void win_cond_var::notify_all()
00230 {
pm.lock();
00231 if (wts.size()==0) { pm.unlock(); return; }
00232
00233 for (int i=0, end=wts.size(); i<end; i++) {
00234 BOOL rc=SetEvent(wts[i]);
00235 hard_assert(rc!=0);
00236 }
00237
00238 wts.clear();
pm.unlock();
00239 }
Other than that, well, it should work fine; SCHED_OTHER aside of course...
;^)
Sergey P. Derevyago
> What if I wanted to reuse the condvar instead of destroying it, and have
> it wait on a different mutex?
>
> This is complete legitimate.
>
Not with _this_ interface.
I'm talking about an implementation of particular cond_var interface.
It was created for this tutorial.
> Also, you
> seem to assume that a mutex will be held during calls to your
> notification functions. You can call a notification function without the
> mutex held.
>
Not with this interface.
> Also, in
> your event_cache object... What happens if I return a signaled event to
> the cache?
>
How can this be possible?
Chris M. Thomasson
> Chris M. Thomasson wrote:
>> What if I wanted to reuse the condvar instead of destroying it, and have
>> it wait on a different mutex?
> Then you're out of luck :)
>
> > This is complete legitimate.
> >
> Not with _this_ interface.
> I'm talking about an implementation of particular cond_var interface. It
> was created for this tutorial.
I see.
>> Also, you seem to assume that a mutex will be held during calls to your
>> notification functions. You can call a notification function without the
>> mutex held.
> >
> Not with this interface.
Well, AFAICT, your condvar will work fine, you just cannot use to for a
pthread implementation...
>> Also, in your event_cache object... What happens if I return a signaled
>> event to the cache?
> How can this be possible?
event_cache evc;
HANDLE h = evc.getEvent();
SetEvent(h);
evc.returnEvent(h);
[...];
I assume that you can use event_cache in other places besides just condvar,
or it its use bound to the library detail you ensure that no handle will
ever be put into the cache if it is signaled?
Sergey P. Derevyago
> Well, AFAICT, your condvar will work fine, you just cannot use to for a
> pthread implementation...
>
> I assume that you can use event_cache in other places besides just
> condvar,
>
Impossible, it's defined in unnamed namespace.
Chris M. Thomasson
> Chris M. Thomasson wrote:
>> Well, AFAICT, your condvar will work fine, you just cannot use to for a
>> pthread implementation...
>>
> There was no point, I don't like the cancellation very much ;)
I was never very fond of it as well!
;^)
>> I assume that you can use event_cache in other places besides just
>> condvar,
> >
> Impossible, it's defined in unnamed namespace.
Okay. I totally miss that point. Well, it will work fine for your condvar.
Chris M. Thomasson
news:g7t9a8$24n$1...@hoshi.visyn.net...
> That's my implementation I wrote some years ago.
Well, IMHO, Sergey implementation's is a heck of a lot cleaner, simpler and
more straightforward.
> That's not the full code (some includes missing)
> but you can see how it is working.
[...]
Chris M. Thomasson
news:g7t9a8$24n$1...@hoshi.visyn.net...
> That's my implementation I wrote some years ago.
> but you can see how it is working.
[...]
I must be totally missing something, but, can you please explain how this
condvar enforces correct wake-up generations? Sergey's implementation has
correct wakeup semantics by using per-thread events and explicitly
constructing the waitset. I don't know for sure but it seems like you have a
problem in your broadcasting technique such that a thread that is part of a
subsequent wait-generation can sneak in and steal a wakeup from the previous
generation. If I am dead wrong on this, then how are you preventing the
condition from occurring? Or, do you just not care about enforcing proper
wait-generation wakeup semantics?
Chris M. Thomasson
> Chris M. Thomasson wrote:
>> What if I wanted to reuse the condvar instead of destroying it, and have
>> it wait on a different mutex?
> Then you're out of luck :)
[...]
;^)
Okay. One final nit-pick... I notice that your code-base allows for a
timeout parameter in your wait function... However, the function as-is
returns void... Well, how does user-code response to timeouts? Please
correct me.
Sergey P. Derevyago
> Okay. One final nit-pick... I notice that your code-base allows for a
> timeout parameter in your wait function... However, the function as-is
> returns void... Well, how does user-code response to timeouts? Please
> correct me.
>
The tutorial code doesn't need to check for the timeouts so this
particular issue was postponed.
Chris M. Thomasson
> Chris M. Thomasson schrieb:
>
>> I must be totally missing something, but, can you please explain
>> how this condvar enforces correct wake-up generations? Sergey's
>> implementation has correct wakeup semantics by using per-thread
>
> Read the code!
Can you post some high-level pseudo-code? I take it that `0x80000000u' is a
waiters-bit correct?
> It's exactly the same semantics like the condvars
> in Java (unordered wakeup).
So it does not support POSIX wake-up semantics; okay. However, did you know
that there are some algorihtms which will break if proper wait-generations
are not honored? When you broadcast, and there are waiters, that group of
waiters are bound to a wait-generation in progress so-to-speak. Any
subsequent waiters must not be allowed to return from the wait function
until the prior wait-generation is completed. If a new subsequent waiter is
allowed to "steal" a signal from the prior generation, well, this can lead
to deadlock in certain algorihtms...
> And Sergey's code isn't cleaner ...
IMVHO, its a heck of a lot smaller which tends to make the code cleaner and
easier to read. I knew know that Sergey's algorithm will work and I know it
honors POSIX wake-up semantics' by looking at the code for only about 5
minutes. Yours is a lot more complicated because you are constructing your
own mutex logic from scratch. One side effect of doing that is that I can't
use your condvar with a CRITICAL_SECTION, a process wide mutex or a custom
mutex...
David Schwartz
wrote:
> Read the code! It's exactly the same semantics like the condvars
> in Java (unordered wakeup). And Sergey's code isn't cleaner ...
I think you are missing the issue. When a thread calls cond_wait, as
soon as it releases the mutex, but has not reacquired it, it is in a
known state -- waiting for the condvar. It is critical to the
semantics of a condvar that the 'broadcast' operation wake every
thread currently waiting for the condvar.
The scenario you must avoid is this:
1) 8 threads are waiting for the condvar, 1, 2, 3, 4, 5, 6, 7, 8.
2) Thread 9 broadcasts the condvar. (Generating 8 wakeups.)
3) Threads 1, 2, 3, and 4 wake. (Consuming 4 wakeups.)
4) Thread 10 blocks on the condvar.
5) Threads 6, 7, 8, and 10 wake. (Consuming the remaining 4 wakeups.)
6) Thread 5 either does not wakeup or wakes up, sees no remaining
wakeups, and goes back to sleep.
Your implementation may now think it has done its job -- since 8
threads were blocked on the condvar and 8 threads were woken. However,
the semantics of broadcast is that *every* thread is unblocked, and
you didn't unblock thread 5.
You cannot implement condvar semantics with a wakeup count unless you
also have a wakeup generation (thus generating 8 wakeups for this
generation and blocking thread 10 on a different generation so it
cannot consume the wakeup thread 5 needs).
Failure to do this means you are *not* implementing a condvar at all.
This is fundamentally part of what it means for something to be a
condvar.
DS
Chris M. Thomasson
> David Schwartz schrieb:
>
>> Your implementation may now think it has done its job -- since
>> 8 threads were blocked on the condvar and 8 threads were woken.
>> However, the semantics of broadcast is that *every* thread is
>> unblocked, and you didn't unblock thread 5.
>
> phore decides which threads to wake up when it is called and not
> asynchronously. m_dwWaitingForSignal is guarded by the mutex in
> my code.
One question... If wait-generation A is broadcasted to, can a subsequent
waiter be signaled before said generation is completed? AFAICT, you coed
simply does not honor proper wait generation semantics...
>> You cannot implement condvar semantics with a wakeup count unless
>> you also have a wakeup generation (thus generating 8 wakeups for
>> this generation and blocking thread 10 on a different generation
>> so it cannot consume the wakeup thread 5 needs).
>
> No, it's possible exactly the way I did it.
Ummm, are you sure you understand MS synchronization objects well? Listen,
there are many caveats. For instance... Well, read ALL:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/75e96ade96038553
A manual reset windows event is NOT GUARANTEED to ATOMICALLY release all
CURRENTLY WAITING threads in response to a call to SetEvent. AFAICT, your
code does not enforce wait-generations at all. Please take a long look at
pthread win32 impl.
I asked you to post high-level pseudo-code. DO IT! If you want me to do it,
well, how much $$$ are you going to pay me for doing your job for you?
Chris M. Thomasson
"Chris M. Thomasson" <n...@spam.invalid> wrote in message
news:Ztdpk.24190$1N1....@newsfe07.iad...
> "Elcaro Nosille" <Elcaro....@googlemail.com> wrote in message
> news:g83mp0$idr$1...@hoshi.visyn.net...
>> David Schwartz schrieb:
>>
>>> Your implementation may now think it has done its job -- since
>>> 8 threads were blocked on the condvar and 8 threads were woken.
>>> However, the semantics of broadcast is that *every* thread is
>>> unblocked, and you didn't unblock thread 5.
>>
>> No, it does wake every of the eight threads because ReleaseSema-
>> phore decides which threads to wake up when it is called and not
>> asynchronously. m_dwWaitingForSignal is guarded by the mutex in
>> my code.
>
> One question... If wait-generation A is broadcasted to, can a subsequent
> waiter be signaled before said generation is completed? AFAICT, you coed
> simply does not honor proper wait generation semantics...
If I am wrong. Well, I love to learn new things... As far as condvars and
POSIX are concerned, well, I have been there and done that... Perhaps I can
help you out Elcaro.
[...]
Chris M. Thomasson
"Chris M. Thomasson" <n...@spam.invalid> wrote in message
news:Ztdpk.24190$1N1....@newsfe07.iad...
Please understand the semantics of semaphore as well... This sync primitive
used within the context of condvar is just asking for trouble. IMVHO, your
code seems to bite the dust in the arena. Please consult phtread win32 impl.
Alex Terekhov has a good impl in there...
> I asked you to post high-level pseudo-code. DO IT! If you want me to do
> it, well, how much $$$ are you going to pay me for doing your job for you?
?
David Schwartz
wrote:
> David Schwartz schrieb:
>
> > Your implementation may now think it has done its job -- since
> > 8 threads were blocked on the condvar and 8 threads were woken.
> > However, the semantics of broadcast is that *every* thread is
> > unblocked, and you didn't unblock thread 5.
> No, it does wake every of the eight threads because ReleaseSema-
> phore decides which threads to wake up when it is called and not
> asynchronously. m_dwWaitingForSignal is guarded by the mutex in
> my code.
Sadly, that doesn't save you. Even if it does choose those 8 threads
to wake, nothing stops another thread from consuming the wakeups.
Consider:
1) Threads 1, 2, 3, and 4 are blocked on the semaphore.
2) Thread 3 is borrowed by a kernel APC.
3) Thread 5 broadcasts the condvar. You queue 4 wakeups that go to 1,
2, 3, and 4.
4) Thread 5 blocks on the condvar, consuming 3's wakeup.
5) Thread 3 returns from the APC but goes to sleep since the semaphore
has no wakeups left.
It is not sufficient to wake the correct threads. You must ensure they
actually consume the sempahore count. See, you successfully made sure
thread 3 was not blocked, but didn't get it to consume a wakeup, so it
just went back to sleep.
> > You cannot implement condvar semantics with a wakeup count unless
> > you also have a wakeup generation (thus generating 8 wakeups for
> > this generation and blocking thread 10 on a different generation
> > so it cannot consume the wakeup thread 5 needs).
> No, it's possible exactly the way I did it.
It's not. You do not ensure the threads that got the wakeups are
actually the ones that consume the semaphore count. You are confusing
two notions of wakeups:
1) A wakeup is when a blocked thread is unblocked. You get these
right.
2) A wakeup is when an unblocked that that is ready-to-run manages to
take a count from the sempahore. You get these wrong.
Sorry, it is not as simple as you think it is.
DS
Dmitriy V'jukov
> It's not. You do not ensure the threads that got the wakeups are
> actually the ones that consume the semaphore count. You are confusing
> two notions of wakeups:
>
> 1) A wakeup is when a blocked thread is unblocked. You get these
> right.
>
> 2) A wakeup is when an unblocked that that is ready-to-run manages to
> take a count from the sempahore. You get these wrong.
>
> Sorry, it is not as simple as you think it is.
Ok, let's see.
I rewrite the code for Relacy Race Detector:
http://groups.google.com/group/relacy/web
1:#include "stdafx.h"
2:#include "../../relacy/relacy_std.hpp"
3:
4:class CondVar
5:{
6:public:
7: CondVar();
8: ~CondVar();
9: void Enter();
10: void Wait();
11: void Release();
12: void ReleaseAll();
13: void Leave();
14:
15:private:
16: std::atomic<int> m_lMutex;
17: std::atomic<unsigned> m_dwWaitingForSignal;
18: rl::HANDLE m_xhEvtEnter;
19: rl::HANDLE m_xhSemRelease;
20:};
21:
22:CondVar::CondVar() :
23: m_xhEvtEnter(rl::CreateEvent( NULL, FALSE, FALSE, NULL, $) ),
24: m_xhSemRelease(rl::CreateSemaphore( NULL, 0, 0x7FFFFFFF, NULL,
$) )
25:{
26: m_lMutex($) = 0;
27: m_dwWaitingForSignal($) = 0;
28:}
29:
30:CondVar::~CondVar()
31:{
32: rl::CloseHandle(m_xhEvtEnter, $);
33: rl::CloseHandle(m_xhSemRelease, $);
34:}
35:
36:void CondVar::Enter()
37:{
38: int lMutex = m_lMutex($).load(std::memory_order_seq_cst);
39: for (;;)
40: {
41: if( lMutex >= 0 )
42: {
43: if (m_lMutex($).compare_swap(lMutex, lMutex |
0x80000000u))
44: break;
45: }
46: else
47: {
48: if (false == m_lMutex($).compare_swap(lMutex, lMutex + 1))
49: continue;
50: rl::WaitForSingleObject(m_xhEvtEnter, rl::RL_INFINITE, $);
51: RL_ASSERT(m_lMutex($).load(std::memory_order_seq_cst) < 0);
52: break;
53: }
54: }
55:}
56:
57:void CondVar::Wait()
58:{
59: unsigned dwWaitingForSignal =
m_dwWaitingForSignal($).load(std::memory_order_seq_cst);
60: m_dwWaitingForSignal($).store(dwWaitingForSignal + 1,
std::memory_order_seq_cst);
61: RL_ASSERT(m_lMutex($).load(std::memory_order_seq_cst) < 0);
62:
63: int lMutex = m_lMutex($).load(std::memory_order_seq_cst);
64: for (;;)
65: {
66: unsigned dwWaitingToOwn = lMutex & 0x7FFFFFFFu;
67: RL_ASSERT(dwWaitingToOwn >= dwWaitingForSignal);
68: if (dwWaitingToOwn == dwWaitingForSignal)
69: {
70: if (m_lMutex($).compare_swap(lMutex, dwWaitingToOwn +
1))
71: break;
72: }
73: else
74: {
75: rl::SetEvent(m_xhEvtEnter, $);
76: break;
77: }
78: }
79:
80: rl::WaitForSingleObject(m_xhSemRelease, rl::RL_INFINITE, $);
81: rl::WaitForSingleObject(m_xhEvtEnter, rl::RL_INFINITE, $);
82:
83: RL_ASSERT(m_lMutex($).load(std::memory_order_seq_cst) < 0);
84:}
85:
86:void CondVar::Release()
87:{
88: RL_ASSERT(m_lMutex($).load(std::memory_order_seq_cst) < 0);
89: unsigned dwWaitingForSignal =
m_dwWaitingForSignal($).load(std::memory_order_seq_cst);
90: if (dwWaitingForSignal != 0)
91: {
92: m_dwWaitingForSignal($).store(dwWaitingForSignal - 1,
std::memory_order_seq_cst);
93: rl::ReleaseSemaphore(m_xhSemRelease, 1, 0, $);
94: }
95:}
96:
97:void CondVar::ReleaseAll()
98:{
99: RL_ASSERT(m_lMutex($).load(std::memory_order_seq_cst) < 0);
100: unsigned dwWaitingForSignal =
m_dwWaitingForSignal($).load(std::memory_order_seq_cst);
101: if (dwWaitingForSignal != 0)
102: {
103: m_dwWaitingForSignal($).store(0,
std::memory_order_seq_cst);
104: rl::ReleaseSemaphore(m_xhSemRelease, dwWaitingForSignal,
0, $);
105: }
106:}
107:
108:void CondVar::Leave()
109:{
110: int lMutex = m_lMutex($).load(std::memory_order_seq_cst);
111: RL_ASSERT(lMutex < 0);
112: for (;;)
113: {
114: unsigned dwWaitingToOwn = lMutex & 0x7FFFFFFFu;
115: unsigned dwWaitingForSignal =
m_dwWaitingForSignal($).load(std::memory_order_seq_cst);
116: RL_ASSERT(dwWaitingToOwn >= dwWaitingForSignal);
117: if (dwWaitingToOwn == dwWaitingForSignal)
118: {
119: if (m_lMutex($).compare_swap(lMutex, lMutex &
0x7FFFFFFF))
120: break;
121: }
122: else
123: {
124: if (false == m_lMutex($).compare_swap(lMutex, lMutex -
1))
125: continue;
126: rl::SetEvent(m_xhEvtEnter, $);
127: break;
128: }
129: }
130:}
131:
And here is simple unit-test:
132:struct CondVarTest : rl::test_suite<CondVarTest, 4>
133:{
134: rl::var<int> stage;
135: CondVar cv;
136:
137: void before()
138: {
139: stage($) = 0;
140: }
141:
142: void thread(unsigned index)
143: {
144: if (0 == index || 1 == index)
145: {
146: cv.Enter();
147: stage($) += 1;
148: cv.ReleaseAll();
149: while (stage($) != 3)
150: cv.Wait();
151: cv.Leave();
152: }
153: else if (2 == index)
154: {
155: cv.Enter();
156: while (stage($) != 2)
157: cv.Wait();
158: stage($) += 1;
159: cv.ReleaseAll();
160: cv.Leave();
161: }
162: else if (3 == index)
163: {
164: cv.Enter();
165: while (stage($) != 3)
166: cv.Wait();
167: cv.Leave();
168: }
169: }
170:};
171:
172:int main()
173:{
174: rl::simulate<CondVarTest>();
175:}
176:
Here is output of Relacy Race Detector:
struct CondVarTest
DEADLOCK (deadlock detected)
iteration: 3
Hmmm... It has detected deadlock on iteration 3...
Here is execution history:
[0] 3: [CTOR BEGIN], in rl::context_impl<struct CondVarTest,class
rl::random_scheduler<4> >::fiber_proc_impl, context.hpp(383)
[1] 3: memory allocation: addr=00369A18, size=12, in CondVar::CondVar,
condvar.cpp(23)
[2] 3: memory allocation: addr=00366B50, size=12, in CondVar::CondVar,
condvar.cpp(24)
[3] 3: <00366780> atomic store, value=0, (prev value=0),
order=seq_cst, in CondVar::CondVar, condvar.cpp(26)
[4] 3: <003667A4> atomic store, value=0, (prev value=0),
order=seq_cst, in CondVar::CondVar, condvar.cpp(27)
[5] 3: [CTOR END], in rl::context_impl<struct CondVarTest,class
rl::random_scheduler<4> >::fiber_proc_impl, context.hpp(383)
[6] 3: [BEFORE BEGIN], in rl::context_impl<struct CondVarTest,class
rl::random_scheduler<4> >::fiber_proc_impl, context.hpp(383)
[7] 3: <00366770> store, value=0, in CondVarTest::before,
condvar.cpp(139)
[8] 3: [BEFORE END], in rl::context_impl<struct CondVarTest,class
rl::random_scheduler<4> >::fiber_proc_impl, context.hpp(383)
[9] 1: <00366780> atomic load, value=0, order=seq_cst, in
CondVar::Enter, condvar.cpp(38)
[10] 3: <00366780> atomic load, value=0, order=seq_cst, in
CondVar::Enter, condvar.cpp(38)
[11] 0: <00366780> atomic load, value=0, order=seq_cst, in
CondVar::Enter, condvar.cpp(38)
[12] 3: <00366780> CAS fail [SPURIOUSLY] orig=0, cmp=0,
xchg=-2147483648, order=seq_cst, in CondVar::Enter, condvar.cpp(43)
[13] 2: <00366780> atomic load, value=0, order=seq_cst, in
CondVar::Enter, condvar.cpp(38)
[14] 2: <00366780> CAS succ orig=0, cmp=0, xchg=-2147483648,
order=seq_cst, in CondVar::Enter, condvar.cpp(43)
[15] 2: <00366770> load, value=0, in CondVarTest::thread,
condvar.cpp(156)
[16] 1: <00366780> CAS fail orig=-2147483648, cmp=0, xchg=-2147483648,
order=seq_cst, in CondVar::Enter, condvar.cpp(43)
[17] 1: <00366780> CAS succ orig=-2147483648, cmp=-2147483648,
xchg=-2147483647, order=seq_cst, in CondVar::Enter, condvar.cpp(48)
[18] 0: <00366780> CAS fail orig=-2147483647, cmp=0, xchg=-2147483648,
order=seq_cst, in CondVar::Enter, condvar.cpp(43)
[19] 1: blocking current thread, in CondVar::Enter, condvar.cpp(50)
[20] 3: <00366780> CAS fail orig=-2147483647, cmp=0, xchg=-2147483648,
order=seq_cst, in CondVar::Enter, condvar.cpp(43)
[21] 2: <003667A4> atomic load, value=0, order=seq_cst, in
CondVar::Wait, condvar.cpp(59)
[22] 3: <00366780> CAS succ orig=-2147483647, cmp=-2147483647,
xchg=-2147483646, order=seq_cst, in CondVar::Enter, condvar.cpp(48)
[23] 0: <00366780> CAS fail orig=-2147483646, cmp=-2147483647,
xchg=-2147483646, order=seq_cst, in CondVar::Enter, condvar.cpp(48)
[24] 3: blocking current thread, in CondVar::Enter, condvar.cpp(50)
[25] 0: <00366780> CAS succ orig=-2147483646, cmp=-2147483646,
xchg=-2147483645, order=seq_cst, in CondVar::Enter, condvar.cpp(48)
[26] 2: <003667A4> atomic store, value=1, (prev value=0),
order=seq_cst, in CondVar::Wait, condvar.cpp(60)
[27] 2: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(61)
[28] 0: blocking current thread, in CondVar::Enter, condvar.cpp(50)
[29] 2: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(63)
[30] 2: unblocking thread 0, in CondVar::Wait, condvar.cpp(75)
[31] 2: <0036B298> event: set initial_state=0 final_state=0
unblocked=1, in CondVar::Wait, condvar.cpp(75)
[32] 2: blocking current thread, in CondVar::Wait, condvar.cpp(80)
[33] 0: <0036B298> event: wait succeeded initial_state=0
final_state=0, in CondVar::Enter, condvar.cpp(50)
[34] 0: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Enter, condvar.cpp(51)
[35] 0: <00366770> load, value=0, in CondVarTest::thread,
condvar.cpp(147)
[36] 0: <00366770> store, value=1, in CondVarTest::thread,
condvar.cpp(147)
[37] 0: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::ReleaseAll, condvar.cpp(99)
[38] 0: <003667A4> atomic load, value=1, order=seq_cst, in
CondVar::ReleaseAll, condvar.cpp(100)
[39] 0: <003667A4> atomic store, value=0, (prev value=1),
order=seq_cst, in CondVar::ReleaseAll, condvar.cpp(103)
[40] 0: unblocking thread 2, in CondVar::ReleaseAll, condvar.cpp(104)
[41] 0: <0036CAF8> semaphore: post value=1 new_count=1 unblocked=1, in
CondVar::ReleaseAll, condvar.cpp(104)
[42] 0: <00366770> load, value=1, in CondVarTest::thread,
condvar.cpp(149)
[43] 0: <003667A4> atomic load, value=0, order=seq_cst, in
CondVar::Wait, condvar.cpp(59)
[44] 0: <003667A4> atomic store, value=1, (prev value=0),
order=seq_cst, in CondVar::Wait, condvar.cpp(60)
[45] 2: <0036CAF8> semaphore: wait succeeded new_count=0, in
CondVar::Wait, condvar.cpp(80)
[46] 2: blocking current thread, in CondVar::Wait, condvar.cpp(81)
[47] 0: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(61)
[48] 0: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(63)
[49] 0: unblocking thread 2, in CondVar::Wait, condvar.cpp(75)
[50] 0: <0036B298> event: set initial_state=0 final_state=0
unblocked=1, in CondVar::Wait, condvar.cpp(75)
[51] 0: blocking current thread, in CondVar::Wait, condvar.cpp(80)
[52] 2: <0036B298> event: wait succeeded initial_state=0
final_state=0, in CondVar::Wait, condvar.cpp(81)
[53] 2: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(83)
[54] 2: <00366770> load, value=1, in CondVarTest::thread,
condvar.cpp(156)
[55] 2: <003667A4> atomic load, value=1, order=seq_cst, in
CondVar::Wait, condvar.cpp(59)
[56] 2: <003667A4> atomic store, value=2, (prev value=1),
order=seq_cst, in CondVar::Wait, condvar.cpp(60)
[57] 2: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(61)
[58] 2: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(63)
[59] 2: unblocking thread 3, in CondVar::Wait, condvar.cpp(75)
[60] 2: <0036B298> event: set initial_state=0 final_state=0
unblocked=1, in CondVar::Wait, condvar.cpp(75)
[61] 2: blocking current thread, in CondVar::Wait, condvar.cpp(80)
[62] 3: <0036B298> event: wait succeeded initial_state=0
final_state=0, in CondVar::Enter, condvar.cpp(50)
[63] 3: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Enter, condvar.cpp(51)
[64] 3: <00366770> load, value=1, in CondVarTest::thread,
condvar.cpp(165)
[65] 3: <003667A4> atomic load, value=2, order=seq_cst, in
CondVar::Wait, condvar.cpp(59)
[66] 3: <003667A4> atomic store, value=3, (prev value=2),
order=seq_cst, in CondVar::Wait, condvar.cpp(60)
[67] 3: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(61)
[68] 3: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(63)
[69] 3: unblocking thread 1, in CondVar::Wait, condvar.cpp(75)
[70] 3: <0036B298> event: set initial_state=0 final_state=0
unblocked=1, in CondVar::Wait, condvar.cpp(75)
[71] 1: <0036B298> event: wait succeeded initial_state=0
final_state=0, in CondVar::Enter, condvar.cpp(50)
[72] 1: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Enter, condvar.cpp(51)
[73] 1: <00366770> load, value=1, in CondVarTest::thread,
condvar.cpp(147)
[74] 1: <00366770> store, value=2, in CondVarTest::thread,
condvar.cpp(147)
[75] 3: blocking current thread, in CondVar::Wait, condvar.cpp(80)
[76] 1: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::ReleaseAll, condvar.cpp(99)
[77] 1: <003667A4> atomic load, value=3, order=seq_cst, in
CondVar::ReleaseAll, condvar.cpp(100)
[78] 1: <003667A4> atomic store, value=0, (prev value=3),
order=seq_cst, in CondVar::ReleaseAll, condvar.cpp(103)
[79] 1: unblocking thread 3, in CondVar::ReleaseAll, condvar.cpp(104)
[80] 1: unblocking thread 2, in CondVar::ReleaseAll, condvar.cpp(104)
[81] 1: unblocking thread 0, in CondVar::ReleaseAll, condvar.cpp(104)
[82] 1: <0036CAF8> semaphore: post value=3 new_count=3 unblocked=3, in
CondVar::ReleaseAll, condvar.cpp(104)
[83] 1: <00366770> load, value=2, in CondVarTest::thread,
condvar.cpp(149)
[84] 1: <003667A4> atomic load, value=0, order=seq_cst, in
CondVar::Wait, condvar.cpp(59)
[85] 1: <003667A4> atomic store, value=1, (prev value=0),
order=seq_cst, in CondVar::Wait, condvar.cpp(60)
[86] 1: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(61)
[87] 0: <0036CAF8> semaphore: wait succeeded new_count=2, in
CondVar::Wait, condvar.cpp(80)
[88] 1: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(63)
[89] 3: <0036CAF8> semaphore: wait succeeded new_count=1, in
CondVar::Wait, condvar.cpp(80)
[90] 1: <0036B298> event: set initial_state=0 final_state=1
unblocked=0, in CondVar::Wait, condvar.cpp(75)
[91] 1: <0036CAF8> semaphore: wait succeeded new_count=0, in
CondVar::Wait, condvar.cpp(80)
[92] 1: <0036B298> event: wait succeeded initial_state=1
final_state=0, in CondVar::Wait, condvar.cpp(81)
[93] 0: blocking current thread, in CondVar::Wait, condvar.cpp(81)
[94] 3: blocking current thread, in CondVar::Wait, condvar.cpp(81)
[95] 1: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(83)
[96] 1: <00366770> load, value=2, in CondVarTest::thread,
condvar.cpp(149)
[97] 2: blocking current thread, in CondVar::Wait, condvar.cpp(80)
[98] 1: <003667A4> atomic load, value=1, order=seq_cst, in
CondVar::Wait, condvar.cpp(59)
[99] 1: <003667A4> atomic store, value=2, (prev value=1),
order=seq_cst, in CondVar::Wait, condvar.cpp(60)
[100] 1: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(61)
[101] 1: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(63)
[102] 1: unblocking thread 3, in CondVar::Wait, condvar.cpp(75)
[103] 1: <0036B298> event: set initial_state=0 final_state=0
unblocked=1, in CondVar::Wait, condvar.cpp(75)
[104] 3: <0036B298> event: wait succeeded initial_state=0
final_state=0, in CondVar::Wait, condvar.cpp(81)
[105] 3: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(83)
[106] 3: <00366770> load, value=2, in CondVarTest::thread,
condvar.cpp(165)
[107] 3: <003667A4> atomic load, value=2, order=seq_cst, in
CondVar::Wait, condvar.cpp(59)
[108] 1: blocking current thread, in CondVar::Wait, condvar.cpp(80)
[109] 3: <003667A4> atomic store, value=3, (prev value=2),
order=seq_cst, in CondVar::Wait, condvar.cpp(60)
[110] 3: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(61)
[111] 3: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(63)
[112] 3: unblocking thread 0, in CondVar::Wait, condvar.cpp(75)
[113] 3: <0036B298> event: set initial_state=0 final_state=0
unblocked=1, in CondVar::Wait, condvar.cpp(75)
[114] 0: <0036B298> event: wait succeeded initial_state=0
final_state=0, in CondVar::Wait, condvar.cpp(81)
[115] 0: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(83)
[116] 0: <00366770> load, value=2, in CondVarTest::thread,
condvar.cpp(149)
[117] 3: blocking current thread, in CondVar::Wait, condvar.cpp(80)
[118] 0: <003667A4> atomic load, value=3, order=seq_cst, in
CondVar::Wait, condvar.cpp(59)
[119] 0: <003667A4> atomic store, value=4, (prev value=3),
order=seq_cst, in CondVar::Wait, condvar.cpp(60)
[120] 0: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(61)
[121] 0: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(63)
[122] 0: <00366780> CAS succ orig=-2147483645, cmp=-2147483645,
xchg=4, order=seq_cst, in CondVar::Wait, condvar.cpp(70)
[123] 0: blocking current thread, in CondVar::Wait, condvar.cpp(80)
[124] 0: DEADLOCK (deadlock detected), in CondVar::Wait,
condvar.cpp(80)
And here is per thread execution history:
thread 0:
[11] 0: <00366780> atomic load, value=0, order=seq_cst, in
CondVar::Enter, condvar.cpp(38)
[18] 0: <00366780> CAS fail orig=-2147483647, cmp=0, xchg=-2147483648,
order=seq_cst, in CondVar::Enter, condvar.cpp(43)
[23] 0: <00366780> CAS fail orig=-2147483646, cmp=-2147483647,
xchg=-2147483646, order=seq_cst, in CondVar::Enter, condvar.cpp(48)
[25] 0: <00366780> CAS succ orig=-2147483646, cmp=-2147483646,
xchg=-2147483645, order=seq_cst, in CondVar::Enter, condvar.cpp(48)
[28] 0: blocking current thread, in CondVar::Enter, condvar.cpp(50)
[33] 0: <0036B298> event: wait succeeded initial_state=0
final_state=0, in CondVar::Enter, condvar.cpp(50)
[34] 0: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Enter, condvar.cpp(51)
[35] 0: <00366770> load, value=0, in CondVarTest::thread,
condvar.cpp(147)
[36] 0: <00366770> store, value=1, in CondVarTest::thread,
condvar.cpp(147)
[37] 0: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::ReleaseAll, condvar.cpp(99)
[38] 0: <003667A4> atomic load, value=1, order=seq_cst, in
CondVar::ReleaseAll, condvar.cpp(100)
[39] 0: <003667A4> atomic store, value=0, (prev value=1),
order=seq_cst, in CondVar::ReleaseAll, condvar.cpp(103)
[40] 0: unblocking thread 2, in CondVar::ReleaseAll, condvar.cpp(104)
[41] 0: <0036CAF8> semaphore: post value=1 new_count=1 unblocked=1, in
CondVar::ReleaseAll, condvar.cpp(104)
[42] 0: <00366770> load, value=1, in CondVarTest::thread,
condvar.cpp(149)
[43] 0: <003667A4> atomic load, value=0, order=seq_cst, in
CondVar::Wait, condvar.cpp(59)
[44] 0: <003667A4> atomic store, value=1, (prev value=0),
order=seq_cst, in CondVar::Wait, condvar.cpp(60)
[47] 0: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(61)
[48] 0: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(63)
[49] 0: unblocking thread 2, in CondVar::Wait, condvar.cpp(75)
[50] 0: <0036B298> event: set initial_state=0 final_state=0
unblocked=1, in CondVar::Wait, condvar.cpp(75)
[51] 0: blocking current thread, in CondVar::Wait, condvar.cpp(80)
[87] 0: <0036CAF8> semaphore: wait succeeded new_count=2, in
CondVar::Wait, condvar.cpp(80)
[93] 0: blocking current thread, in CondVar::Wait, condvar.cpp(81)
[114] 0: <0036B298> event: wait succeeded initial_state=0
final_state=0, in CondVar::Wait, condvar.cpp(81)
[115] 0: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(83)
[116] 0: <00366770> load, value=2, in CondVarTest::thread,
condvar.cpp(149)
[118] 0: <003667A4> atomic load, value=3, order=seq_cst, in
CondVar::Wait, condvar.cpp(59)
[119] 0: <003667A4> atomic store, value=4, (prev value=3),
order=seq_cst, in CondVar::Wait, condvar.cpp(60)
[120] 0: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(61)
[121] 0: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(63)
[122] 0: <00366780> CAS succ orig=-2147483645, cmp=-2147483645,
xchg=4, order=seq_cst, in CondVar::Wait, condvar.cpp(70)
[123] 0: blocking current thread, in CondVar::Wait, condvar.cpp(80)
[124] 0: DEADLOCK (deadlock detected), in CondVar::Wait,
condvar.cpp(80)
thread 1:
[9] 1: <00366780> atomic load, value=0, order=seq_cst, in
CondVar::Enter, condvar.cpp(38)
[16] 1: <00366780> CAS fail orig=-2147483648, cmp=0, xchg=-2147483648,
order=seq_cst, in CondVar::Enter, condvar.cpp(43)
[17] 1: <00366780> CAS succ orig=-2147483648, cmp=-2147483648,
xchg=-2147483647, order=seq_cst, in CondVar::Enter, condvar.cpp(48)
[19] 1: blocking current thread, in CondVar::Enter, condvar.cpp(50)
[71] 1: <0036B298> event: wait succeeded initial_state=0
final_state=0, in CondVar::Enter, condvar.cpp(50)
[72] 1: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Enter, condvar.cpp(51)
[73] 1: <00366770> load, value=1, in CondVarTest::thread,
condvar.cpp(147)
[74] 1: <00366770> store, value=2, in CondVarTest::thread,
condvar.cpp(147)
[76] 1: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::ReleaseAll, condvar.cpp(99)
[77] 1: <003667A4> atomic load, value=3, order=seq_cst, in
CondVar::ReleaseAll, condvar.cpp(100)
[78] 1: <003667A4> atomic store, value=0, (prev value=3),
order=seq_cst, in CondVar::ReleaseAll, condvar.cpp(103)
[79] 1: unblocking thread 3, in CondVar::ReleaseAll, condvar.cpp(104)
[80] 1: unblocking thread 2, in CondVar::ReleaseAll, condvar.cpp(104)
[81] 1: unblocking thread 0, in CondVar::ReleaseAll, condvar.cpp(104)
[82] 1: <0036CAF8> semaphore: post value=3 new_count=3 unblocked=3, in
CondVar::ReleaseAll, condvar.cpp(104)
[83] 1: <00366770> load, value=2, in CondVarTest::thread,
condvar.cpp(149)
[84] 1: <003667A4> atomic load, value=0, order=seq_cst, in
CondVar::Wait, condvar.cpp(59)
[85] 1: <003667A4> atomic store, value=1, (prev value=0),
order=seq_cst, in CondVar::Wait, condvar.cpp(60)
[86] 1: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(61)
[88] 1: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(63)
[90] 1: <0036B298> event: set initial_state=0 final_state=1
unblocked=0, in CondVar::Wait, condvar.cpp(75)
[91] 1: <0036CAF8> semaphore: wait succeeded new_count=0, in
CondVar::Wait, condvar.cpp(80)
[92] 1: <0036B298> event: wait succeeded initial_state=1
final_state=0, in CondVar::Wait, condvar.cpp(81)
[95] 1: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(83)
[96] 1: <00366770> load, value=2, in CondVarTest::thread,
condvar.cpp(149)
[98] 1: <003667A4> atomic load, value=1, order=seq_cst, in
CondVar::Wait, condvar.cpp(59)
[99] 1: <003667A4> atomic store, value=2, (prev value=1),
order=seq_cst, in CondVar::Wait, condvar.cpp(60)
[100] 1: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(61)
[101] 1: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(63)
[102] 1: unblocking thread 3, in CondVar::Wait, condvar.cpp(75)
[103] 1: <0036B298> event: set initial_state=0 final_state=0
unblocked=1, in CondVar::Wait, condvar.cpp(75)
[108] 1: blocking current thread, in CondVar::Wait, condvar.cpp(80)
thread 2:
[13] 2: <00366780> atomic load, value=0, order=seq_cst, in
CondVar::Enter, condvar.cpp(38)
[14] 2: <00366780> CAS succ orig=0, cmp=0, xchg=-2147483648,
order=seq_cst, in CondVar::Enter, condvar.cpp(43)
[15] 2: <00366770> load, value=0, in CondVarTest::thread,
condvar.cpp(156)
[21] 2: <003667A4> atomic load, value=0, order=seq_cst, in
CondVar::Wait, condvar.cpp(59)
[26] 2: <003667A4> atomic store, value=1, (prev value=0),
order=seq_cst, in CondVar::Wait, condvar.cpp(60)
[27] 2: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(61)
[29] 2: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(63)
[30] 2: unblocking thread 0, in CondVar::Wait, condvar.cpp(75)
[31] 2: <0036B298> event: set initial_state=0 final_state=0
unblocked=1, in CondVar::Wait, condvar.cpp(75)
[32] 2: blocking current thread, in CondVar::Wait, condvar.cpp(80)
[45] 2: <0036CAF8> semaphore: wait succeeded new_count=0, in
CondVar::Wait, condvar.cpp(80)
[46] 2: blocking current thread, in CondVar::Wait, condvar.cpp(81)
[52] 2: <0036B298> event: wait succeeded initial_state=0
final_state=0, in CondVar::Wait, condvar.cpp(81)
[53] 2: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(83)
[54] 2: <00366770> load, value=1, in CondVarTest::thread,
condvar.cpp(156)
[55] 2: <003667A4> atomic load, value=1, order=seq_cst, in
CondVar::Wait, condvar.cpp(59)
[56] 2: <003667A4> atomic store, value=2, (prev value=1),
order=seq_cst, in CondVar::Wait, condvar.cpp(60)
[57] 2: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(61)
[58] 2: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(63)
[59] 2: unblocking thread 3, in CondVar::Wait, condvar.cpp(75)
[60] 2: <0036B298> event: set initial_state=0 final_state=0
unblocked=1, in CondVar::Wait, condvar.cpp(75)
[61] 2: blocking current thread, in CondVar::Wait, condvar.cpp(80)
[97] 2: blocking current thread, in CondVar::Wait, condvar.cpp(80)
thread 3:
[0] 3: [CTOR BEGIN], in rl::context_impl<struct CondVarTest,class
rl::random_scheduler<4> >::fiber_proc_impl, context.hpp(383)
[1] 3: memory allocation: addr=00369A18, size=12, in CondVar::CondVar,
condvar.cpp(23)
[2] 3: memory allocation: addr=00366B50, size=12, in CondVar::CondVar,
condvar.cpp(24)
[3] 3: <00366780> atomic store, value=0, (prev value=0),
order=seq_cst, in CondVar::CondVar, condvar.cpp(26)
[4] 3: <003667A4> atomic store, value=0, (prev value=0),
order=seq_cst, in CondVar::CondVar, condvar.cpp(27)
[5] 3: [CTOR END], in rl::context_impl<struct CondVarTest,class
rl::random_scheduler<4> >::fiber_proc_impl, context.hpp(383)
[6] 3: [BEFORE BEGIN], in rl::context_impl<struct CondVarTest,class
rl::random_scheduler<4> >::fiber_proc_impl, context.hpp(383)
[7] 3: <00366770> store, value=0, in CondVarTest::before,
condvar.cpp(139)
[8] 3: [BEFORE END], in rl::context_impl<struct CondVarTest,class
rl::random_scheduler<4> >::fiber_proc_impl, context.hpp(383)
[10] 3: <00366780> atomic load, value=0, order=seq_cst, in
CondVar::Enter, condvar.cpp(38)
[12] 3: <00366780> CAS fail [SPURIOUSLY] orig=0, cmp=0,
xchg=-2147483648, order=seq_cst, in CondVar::Enter, condvar.cpp(43)
[20] 3: <00366780> CAS fail orig=-2147483647, cmp=0, xchg=-2147483648,
order=seq_cst, in CondVar::Enter, condvar.cpp(43)
[22] 3: <00366780> CAS succ orig=-2147483647, cmp=-2147483647,
xchg=-2147483646, order=seq_cst, in CondVar::Enter, condvar.cpp(48)
[24] 3: blocking current thread, in CondVar::Enter, condvar.cpp(50)
[62] 3: <0036B298> event: wait succeeded initial_state=0
final_state=0, in CondVar::Enter, condvar.cpp(50)
[63] 3: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Enter, condvar.cpp(51)
[64] 3: <00366770> load, value=1, in CondVarTest::thread,
condvar.cpp(165)
[65] 3: <003667A4> atomic load, value=2, order=seq_cst, in
CondVar::Wait, condvar.cpp(59)
[66] 3: <003667A4> atomic store, value=3, (prev value=2),
order=seq_cst, in CondVar::Wait, condvar.cpp(60)
[67] 3: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(61)
[68] 3: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(63)
[69] 3: unblocking thread 1, in CondVar::Wait, condvar.cpp(75)
[70] 3: <0036B298> event: set initial_state=0 final_state=0
unblocked=1, in CondVar::Wait, condvar.cpp(75)
[75] 3: blocking current thread, in CondVar::Wait, condvar.cpp(80)
[89] 3: <0036CAF8> semaphore: wait succeeded new_count=1, in
CondVar::Wait, condvar.cpp(80)
[94] 3: blocking current thread, in CondVar::Wait, condvar.cpp(81)
[104] 3: <0036B298> event: wait succeeded initial_state=0
final_state=0, in CondVar::Wait, condvar.cpp(81)
[105] 3: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(83)
[106] 3: <00366770> load, value=2, in CondVarTest::thread,
condvar.cpp(165)
[107] 3: <003667A4> atomic load, value=2, order=seq_cst, in
CondVar::Wait, condvar.cpp(59)
[109] 3: <003667A4> atomic store, value=3, (prev value=2),
order=seq_cst, in CondVar::Wait, condvar.cpp(60)
[110] 3: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(61)
[111] 3: <00366780> atomic load, value=-2147483645, order=seq_cst, in
CondVar::Wait, condvar.cpp(63)
[112] 3: unblocking thread 0, in CondVar::Wait, condvar.cpp(75)
[113] 3: <0036B298> event: set initial_state=0 final_state=0
unblocked=1, in CondVar::Wait, condvar.cpp(75)
[117] 3: blocking current thread, in CondVar::Wait, condvar.cpp(80)
Let's take a closer look at execution history. We can see that on
steps 79-82 thread 1 unblocks threads 0, 2 and 3 and sets semaphore
count to 3. Let's see what threads consume semaphore values. We see
that thread 0 consume semaphore value on step 87. Then thread 3
consume semaphore value on step 89. And finaly thread 1 consume last
semaphore value on step 91. Thread 2 stay without semaphore value, and
effectively doesn't notified by RelaseAll() function. BANG! DEADLOCK!
It takes around 20 minutes to rewrite code for Relacy Race Detector,
construct simple unit-test, and analyse execution history. And note
that it was purely 'mechanical' work, I didn't thinking about how all
those API works, I just translate code and run the program. That is
all.
--
Dmitriy V'jukov
Relacy Race Detector: Make your synchronization correct!
http://groups.google.ru/group/relacy/web
Chris M. Thomasson
"Dmitriy V'jukov" <dvy...@gmail.com> wrote in message
news:507a4b1d-d855-48a0...@c65g2000hsa.googlegroups.com...
> On Aug 15, 5:25 pm, David Schwartz <dav...@webmaster.com> wrote:
>
>> It's not. You do not ensure the threads that got the wakeups are
>> actually the ones that consume the semaphore count. You are confusing
>> two notions of wakeups:
>>
>> 1) A wakeup is when a blocked thread is unblocked. You get these
>> right.
>>
>> 2) A wakeup is when an unblocked that that is ready-to-run manages to
>> take a count from the sempahore. You get these wrong.
>>
>> Sorry, it is not as simple as you think it is.
>
>
> Ok, let's see.
> I rewrite the code for Relacy Race Detector:
> http://groups.google.com/group/relacy/web
BANG! Relacy kicks a$$! I have personally used it for some commercial and
private algorithms of mine. However, I cannot post ANY results because it
was used in conjunction with some patented algorithms; shi% happens! Perhaps
I ask for commercial license!!! Everybody, well, think about it for a
moment... Luckily, I just know some my stuff works...
=^D
Dmitriy V'jukov
wrote:
> > Sadly, that doesn't save you. Even if it does choose those
> > 8 threads to wake, nothing stops another thread from consuming
> > the wakeups. ...
>
> Read the code!
> The scenario you describe couldn't happen with my code.
>
> > It's not. You do not ensure the threads that got the wakeups
> > are actually the ones that consume the semaphore count. ...
>
> This couldn't happen because you can register for wakeup only
> if you are holding the internal semaphore; i.e. m_dwWaitingFor
> Signal is guarded by m_lMutex & 0x80000000u.
Can you comment on this:
http://groups.google.com/group/comp.programming.threads/msg/30c2ec41c4d498a2
Why execution history provided by Relacy is not possible?
Thread 1 executes ReleaseAll() and wake-ups 3 threads. Then, not
releasing mutex, executes Wait(), in Wait() it executes
SetEvent(m_xhEvtEnter), then WaitForSingleObject(m_xhSemRelease,
INFINITE), thus consuming 1 wake-up.
Dmitriy V'jukov
Chris M. Thomasson
> David Schwartz schrieb:
>
>> Sadly, that doesn't save you. Even if it does choose those
>> 8 threads to wake, nothing stops another thread from consuming
>
> Read the code!
> The scenario you describe couldn't happen with my code.
>
>
> This couldn't happen because you can register for wakeup only
> if you are holding the internal semaphore; i.e. m_dwWaitingFor
> Signal is guarded by m_lMutex & 0x80000000u.
Ummm... You don't seem to understand your own code. You need another bit in
there to define a wait-generation. Sorry.
>> Sorry, it is not as simple as you think it is.
>
> It is that simple and I'll bet it isn't possible to write a
> simpler convar-implementation than that.
WRONG! Did you actually look at Sergey's code? Per-Thread manual waitset
construction is as simple as you can possibly get!
Chris M. Thomasson
> "Elcaro Nosille" <Elcaro....@googlemail.com> wrote in message
> news:g84eef$mqe$1...@hoshi.visyn.net...
>> David Schwartz schrieb:
>>
>>> Sadly, that doesn't save you. Even if it does choose those
>>> 8 threads to wake, nothing stops another thread from consuming
>>> the wakeups. ...
>>
>> Read the code!
>> The scenario you describe couldn't happen with my code.
>>
>>> It's not. You do not ensure the threads that got the wakeups
>>> are actually the ones that consume the semaphore count. ...
>>
>> This couldn't happen because you can register for wakeup only
>> if you are holding the internal semaphore; i.e. m_dwWaitingFor
>> Signal is guarded by m_lMutex & 0x80000000u.
>
> Ummm... You don't seem to understand your own code. You need another bit
> in there to define a wait-generation. Sorry.
An then some... How would you like to correct the code? I have some ideas,
but they are probably infested with race-conditions. Well, back to
square/race one.
[...]
Chris M. Thomasson
> Chris M. Thomasson schrieb:
>
>> An then some... How would you like to correct the code?
>
> until all objects become singalled that the thread is waiting on so
> that the situation David mentioned could happen. But that's not a
> deal for me because I'm using this condvar in situations where all
> threads waiting on the singal are exchangeable (I think's that the
> most usual case).
The type of algorihtms that I see which can deadlock if wait-generations are
honored usually go something like:
contrived example indeed!
_________________________________________________________________
static queue<item> g_start_queue;
static int g_count = 0;
static mutex g_mutex;
static condvar g_condvar;
thread_a {
bool posted = false;
mutex::guard lock(g_mutex);
while (g_count != 2) {
if (! posted) {
g_start_queue.push(new item);
g_start_queue.push(new item);
g_condvar.broadcast();
posted = true;
}
g_condvar.wait(lock)
}
}
threads_b_c {
item* i;
mutex::guard lock(g_mutex);
while (! (i = g_start_queue.trypop())) {
g_condvar.wait(lock);
}
++g_count;
delete i;
g_condvar.broadcast();
}
_________________________________________________________________
Imagine if thread_b_c are "just about to block" on the condvar internal
semaphore. That is they are just about to execute the following line of
code:
while( ::WaitForMultipleObjects( 2, ahWait, TRUE, INFINITE ) !=
WAIT_OBJECT_0 )
assert(false);
The internal wait-count is two; I think that would be the
`m_dwWaitingForSignal' variable. Then thread_a enqueues two messages meant
for threads_b_c and broadcasts the condvar which would increment the
semaphore by two. Then before threads_b_c even get a chance to actually wait
on the semaphore, thread_a enters the wait function and waits on the
semaphore thus consuming a signal and spins back around on its predicate and
waits again thereby consuming another semaphore signal... Finally,
thread_b_c go to block on the semaphore which is now zero; they end up
waiting forever. The basic scenario is that thread_a consumed its own
signals which were meant for threads_b_c...
The simplest and most straightforward method to solve this is to do
something like Sergey code which assigns a event per-thread and build your
own wait-set. However, there is a caveat... Your only going to get
SCHED_OTHER...
> I think I rename the class to document this special behaviour and
> if I ever need a different behaviour, I'll implement a new class.
That should work out just fine.
David Schwartz
> The simplest and most straightforward method to solve this is to do
> something like Sergey code which assigns a event per-thread and build your
> own wait-set. However, there is a caveat... Your only going to get
> SCHED_OTHER...
Isn't it orders of magnitude simpler just to not use a wake count? If
a thread unblocks, then let it return from the condvar wait. Spurious
wakeups are specifically allowed precisely because it so darned hard
to avoid them. Wait generations and wake counts are only needed to
avoid spurious wakeups.
DS