Re: QUEUE_WaitBits race condition
Ulrich Weigand wrote: Ove, could you try whether this solves your deadlock? Bye, Ulrich ChangeLog: * include/queue.h windows/queue.c windows/message.c Protect queue-wakeBits/changeBits/wakeBits by critical section. Any reason this hasn't been checked into CVS yet? It seems to solve that deadlock issue, according to Ove. -Gav -- Gavriel State, CEO TransGaming Technologies Inc. http://www.transgaming.com [EMAIL PROTECTED]
Re: QUEUE_WaitBits race condition
On Wed, 3 Jan 2001, Ulrich Weigand wrote: Ove, could you try whether this solves your deadlock? Well, these things aren't exactly easy to reproduce. The hang appeared after about half an hour or more of heavy starcraft playing... so to be reasonably sure I would have to play through a complete mission without hangs... oh well... [4 hours later] Phew... testing is exhausting. Well, at least it never hung while I was playing... (somehow it crashed somewhere in the middle of the video sequence after it, but that's probably not related)
Re: QUEUE_WaitBits race condition
Ove Kaaven [EMAIL PROTECTED] writes: OK, this code may look all fine and dandy, even for sendmessages. But what happens when an optimizing C compiler like gcc gets run on it? Well, it figures that the changeBits are tested at [2], so when it gets to [3], it sees no change, and optimizes [3] out... so, instant race condition. It does not make any difference whether the compiler optimizes it out or not, you still have the same race. And adding volatile doesn't help, the bits can always be changed after they are tested (volatile is almost always the wrong fix for a race condition anyway). All the wake bits handling is broken IMO, this will be revisited when I get around to implement inter-process SendMessage(). -- Alexandre Julliard [EMAIL PROTECTED]
Re: QUEUE_WaitBits race condition
On 3 Jan 2001, Alexandre Julliard wrote: Ove Kaaven [EMAIL PROTECTED] writes: OK, this code may look all fine and dandy, even for sendmessages. But what happens when an optimizing C compiler like gcc gets run on it? Well, it figures that the changeBits are tested at [2], so when it gets to [3], it sees no change, and optimizes [3] out... so, instant race condition. It does not make any difference whether the compiler optimizes it out or not, you still have the same race. No? Ok, let me recheck my understanding... on the left the various stages of WaitBits, on the right what SetWakeBit would do if it was invoked at that stage of WaitBits... WaitBits SetWakeBit -- starts (no wakeMask) set changeBits, return tests changeBits set changeBits, return [X] tests wakeBits for sendmessage set changeBits, return [X] sets wakeMask set changeBits, resets wakeMask, wakes tests changeBits (optimized out) set changeBits, resets wakeMask, wakes waits for wake returns to start The two spots marked [X] would be handled fine if the second test wasn't optimized out (well, a wake would probably be signaled, and WaitBits would never wait for that wake, which isn't elegant, but that would at least be erring on the safe side). None of the other spots would be problematic, as far as I can see. And adding volatile doesn't help, the bits can always be changed after they are tested (volatile is almost always the wrong fix for a race condition anyway). But if the bits are changed after the wakeMask is set, then SetWakeBit signals the queue, so it would get out of the following wait anyway? Or what? As far as I can see, the code handles all likely conditions... the "volatile" just protects the important checks from being optimized out, it doesn't have much to do with the race condition itself... Of course, I'm not going to stop you from fixing the unlikely conditions too, but I wanted this to work reliably now, and when this fix appeared simple and correct enough...
Re: QUEUE_WaitBits race condition
Alexandre Julliard wrote: Ove Kaaven [EMAIL PROTECTED] writes: OK, this code may look all fine and dandy, even for sendmessages. But what happens when an optimizing C compiler like gcc gets run on it? Well, it figures that the changeBits are tested at [2], so when it gets to [3], it sees no change, and optimizes [3] out... so, instant race condition. It does not make any difference whether the compiler optimizes it out or not, you still have the same race. And adding volatile doesn't help, the bits can always be changed after they are tested (volatile is almost always the wrong fix for a race condition anyway). But in this case, I think Ove is basically right: you have only one race between QUEUE_SetWakeBit and QUEUE_WaitBits. QUEUE_SetWakeBit does basically: queue-changeBits |= bit; if (queue-wakeMask bit) server_call( REQ_WAKE_QUEUE ); and QUEUE_WaitBits does: queue-wakeMask = bits | QS_SENDMESSAGE; if (!(queue-changeBits bits)) WaitForSingleObject( queue-server_queue, timeout ); To avoid the race, we must guarantee that if QUEUE_WaitBits runs into WaitForSingleObject, then QUEUE_SetWakeBits must either have already run into REQ_WAKE_QUEUE or will run into REQ_WAKE_QUEUE (this is of course also a race, but of no importance, as the queue remembers its 'signalled' state). So, the only important thing is that QUEUE_SetWakeBits sets the changeBits *before* it tests the wakeMask, and that QUEUE_WaitBits sets the wakeMask *before* it tests the changeBits. However, I don't think that just making the 'queue' volatile fixes the problem completely, as the accesses to the queue need also be atomic (the ... |= bits for example). I think we should just protect access to the wakeMask by the queue critical section. Then we need not care about volatile access or not, we can even remove the second check ... What do you think about this patch, for example? (Untested ...) --- wine-cvs/windows/queue.cMon Nov 6 22:24:21 2000 +++ wine-uw/windows/queue.c Wed Jan 3 21:20:00 2001 @@ -628,6 +628,8 @@ TRACE_(msg)("queue = %04x (wm=%04x), bit = %04x\n", queue-self, queue-wakeMask, bit ); +EnterCriticalSection( queue-cSection ); + if (bit QS_MOUSE) pMouseQueue = queue; if (bit QS_KEY) pKbdQueue = queue; queue-changeBits |= bit; @@ -655,6 +657,8 @@ SERVER_END_REQ; } } + +LeaveCriticalSection( queue-cSection ); } @@ -693,27 +697,29 @@ for (;;) { +EnterCriticalSection( queue-cSection ); + if (queue-changeBits bits) { /* One of the bits is set; we can return */ queue-wakeMask = 0; + +LeaveCriticalSection( queue-cSection ); QUEUE_Unlock( queue ); return 1; } if (queue-wakeBits QS_SENDMESSAGE) { /* Process the sent message immediately */ - queue-wakeMask = 0; + +LeaveCriticalSection( queue-cSection ); QUEUE_ReceiveMessage( queue ); continue; /* nested sm crux */ } queue-wakeMask = bits | QS_SENDMESSAGE; -if(queue-changeBits bits) -{ -continue; -} +LeaveCriticalSection( queue-cSection ); TRACE_(msg)("%04x) wakeMask is %04x, waiting\n", queue-self, queue-wakeMask); Bye, Ulrich -- Dr. Ulrich Weigand [EMAIL PROTECTED]
Re: QUEUE_WaitBits race condition
Ulrich Weigand [EMAIL PROTECTED] writes: But in this case, I think Ove is basically right: you have only one race between QUEUE_SetWakeBit and QUEUE_WaitBits. Well, yes of course, the race is between testing and setting the bits, but the race not only happens if the compiler optimizes out the second test, it can happen for a number of reasons (like reordering of the assignments, two threads setting bits at the same time, etc.) My point was that this second test buys nothing at all, no matter if it's optimized out or not, since it cannot possibly avoid the race. A critical section would work, but in this case as you noted you don't need the second test eiter. What do you think about this patch, for example? (Untested ...) That seems reasonable yes. -- Alexandre Julliard [EMAIL PROTECTED]
Re: QUEUE_WaitBits race condition
Alexandre Julliard wrote: Ulrich Weigand [EMAIL PROTECTED] writes: But in this case, I think Ove is basically right: you have only one race between QUEUE_SetWakeBit and QUEUE_WaitBits. Well, yes of course, the race is between testing and setting the bits, but the race not only happens if the compiler optimizes out the second test, it can happen for a number of reasons (like reordering of the assignments, two threads setting bits at the same time, etc.) Well, volatile prevents reordering of assignments. But nevertheless I agree, volatile helps only if you have atomic operations in the first place ... (On Intel, load/store to an aligned dword is atomic, so the only problem is the |=. Of course, on other architectures, not even that is necessarily guaranteed.) What do you think about this patch, for example? (Untested ...) That seems reasonable yes. Well, that quick patch contained a potential deadlock due to lock order inversion :-( Furthermore, it really only makes sense if *all* accesses to wakeBits/changeBits/wakeMask are protected ... The following patch is a more complete implementation of this idea; it is also somewhat tested (at least the Borland Thread Sorting Demo, my old stress test case for inter-thread messages, still runs ;-). Ove, could you try whether this solves your deadlock? Bye, Ulrich ChangeLog: * include/queue.h windows/queue.c windows/message.c Protect queue-wakeBits/changeBits/wakeBits by critical section. diff -ur wine-cvs/include/queue.h wine-uw/include/queue.h --- wine-cvs/include/queue.hWed Jan 3 22:51:30 2001 +++ wine-uw/include/queue.h Wed Jan 3 23:10:28 2001 @@ -159,7 +159,8 @@ extern MESSAGEQUEUE *QUEUE_GetSysQueue(void); extern void QUEUE_SetWakeBit( MESSAGEQUEUE *queue, WORD bit ); extern void QUEUE_ClearWakeBit( MESSAGEQUEUE *queue, WORD bit ); -extern void QUEUE_ReceiveMessage( MESSAGEQUEUE *queue ); +extern WORD QUEUE_TestWakeBit( MESSAGEQUEUE *queue, WORD bit ); +extern BOOL QUEUE_ReceiveMessage( MESSAGEQUEUE *queue ); extern int QUEUE_WaitBits( WORD bits, DWORD timeout ); extern void QUEUE_IncPaintCount( HQUEUE16 hQueue ); extern void QUEUE_DecPaintCount( HQUEUE16 hQueue ); diff -ur wine-cvs/windows/message.c wine-uw/windows/message.c --- wine-cvs/windows/message.c Wed Jan 3 22:51:35 2001 +++ wine-uw/windows/message.c Wed Jan 3 23:12:58 2001 @@ -1123,7 +1123,7 @@ static BOOL MSG_PeekMessage( int type, LPMSG msg, HWND hwnd, DWORD first, DWORD last, WORD flags, BOOL peek ) { -int mask; +int changeBits, mask; MESSAGEQUEUE *msgQueue; HQUEUE16 hQueue; POINT16 pt16; @@ -1159,12 +1159,15 @@ WIN_RestoreWndsLock(iWndsLocks); return FALSE; } + +EnterCriticalSection( msgQueue-cSection ); msgQueue-changeBits = 0; +LeaveCriticalSection( msgQueue-cSection ); /* First handle a message put by SendMessage() */ - while (msgQueue-wakeBits QS_SENDMESSAGE) -QUEUE_ReceiveMessage( msgQueue ); +while ( QUEUE_ReceiveMessage( msgQueue ) ) +; /* Now handle a WM_QUIT message */ @@ -1183,7 +1186,7 @@ /* Now find a normal message */ retry: -if (((msgQueue-wakeBits mask) QS_POSTMESSAGE) +if ((QUEUE_TestWakeBit(msgQueue, mask QS_POSTMESSAGE)) ((qmsg = QUEUE_FindMsg( msgQueue, hwnd, first, last )) != 0)) { /* Try to convert message to requested type */ @@ -1206,7 +1209,10 @@ break; } -msgQueue-changeBits |= MSG_JournalPlayBackMsg(); +changeBits = MSG_JournalPlayBackMsg(); +EnterCriticalSection( msgQueue-cSection ); +msgQueue-changeBits |= changeBits; +LeaveCriticalSection( msgQueue-cSection ); /* Now find a hardware event */ @@ -1222,12 +1228,12 @@ /* Check again for SendMessage */ - while (msgQueue-wakeBits QS_SENDMESSAGE) -QUEUE_ReceiveMessage( msgQueue ); +while ( QUEUE_ReceiveMessage( msgQueue ) ) +; /* Now find a WM_PAINT message */ - if ((msgQueue-wakeBits mask) QS_PAINT) + if (QUEUE_TestWakeBit(msgQueue, mask QS_PAINT)) { WND* wndPtr; msg-hwnd = WIN_FindWinToRepaint( hwnd , hQueue ); @@ -1263,10 +1269,11 @@ if (!(flags PM_NOYIELD)) { UserYield16(); -while (msgQueue-wakeBits QS_SENDMESSAGE) -QUEUE_ReceiveMessage( msgQueue ); +while ( QUEUE_ReceiveMessage( msgQueue ) ) +; } - if ((msgQueue-wakeBits mask) QS_TIMER) + + if (QUEUE_TestWakeBit(msgQueue, mask QS_TIMER)) { if (TIMER_GetTimerMsg(msg, hwnd, hQueue, flags PM_REMOVE)) break; } @@ -1279,7 +1286,7 @@ WIN_RestoreWndsLock(iWndsLocks); return FALSE; } -