{"thread":{"id":"24030","subject":"[RFT PATCH 0/2] win32: optimize emulation of condition variables","startedAt":"2010-06-07T13:38:10Z","lastAt":"2010-06-13T10:16:52Z","messageCount":9,"participants":["Paolo Bonzini","Johannes Sixt"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"143157","messageId":"1275917892-16437-1-git-send-email-bonzini@gnu.org","threadId":"24030","inReplyTo":null,"subject":"[RFT PATCH 0/2] win32: optimize emulation of condition variables","fromName":"Paolo Bonzini","fromEmail":"bonzini@gnu.org","sentAt":"2010-06-07T13:38:10Z","receivedAt":"2010-06-07T13:38:10Z","isPatch":true,"sender":{"key":"bonzini@gnu.org","avatar":"https://avatars.githubusercontent.com/u/42082?v=4"},"body":"I recently looked at git's condvar implementation for use in another\nproject, and found a couple of simple optimization opportunities.\nWe can drop the waiters_lock, and we can make broadcast asynchronous\nif it is waking up only one thread.\n\nI made two simple tests:\n\n- 1 thread sending a broadcast every 10 msec, 10 threads calling\n  pthread_cond_wait every 100 msec.  Timings are (average of three runs):\n\n  before     2.094 us/wait      4.015 us/broadcast\n  after      2.064 us/wait      2.883 us/broadcast\n\n  i.e. most broadcasts and waits hit the fast path, the few that don't\n  likely avoid the rendez-vous after the patch.  In this case the\n  waiters_lock is always hitting its own fast path.  The speedup is\n  mostly in broadcast, and comes mostly from the second patch.\n\n- 1 thread sending a broadcast every 100 msec, 10 threads calling\n  pthread_cond_wait every 10 msec.  Timings are:\n\n  before     17.59 us/wait      192.2 us/broadcast\n  after      8.959 us/wait      141.1 us/broadcast\n\n  i.e. most broadcasts hit the slow path, and there will be also high\n  contention on waiters_lock after the broadcast.  In this case the\n  speedup comes from avoiding locks in the first patch.\n\n\nI have tested this patch quite thoroughly outside git, but not as part\nof it.  So help with that would be appreciated.\n\nThanks,\n\nPaolo\n\nPaolo Bonzini (2):\n  win32: optimize condition variable implementation\n  win32: optimize pthread_cond_broadcast\n\n compat/win32/pthread.c |   71 +++++++++++++++++++++++++----------------------\n compat/win32/pthread.h |    1 -\n 2 files changed, 38 insertions(+), 34 deletions(-)\n"},{"id":"143158","messageId":"1275917892-16437-2-git-send-email-bonzini@gnu.org","threadId":"24030","inReplyTo":"1275917892-16437-1-git-send-email-bonzini@gnu.org","subject":"[RFT PATCH 1/2] win32: optimize condition variable implementation","fromName":"Paolo Bonzini","fromEmail":"bonzini@gnu.org","sentAt":"2010-06-07T13:38:11Z","receivedAt":"2010-06-07T13:38:11Z","isPatch":true,"sender":{"key":"bonzini@gnu.org","avatar":"https://avatars.githubusercontent.com/u/42082?v=4"},"body":"The fact that the condition variable mutex must be held\n(in this implementation) at the time of pthread_cond_signal\nand pthread_cond_broadcast means that most of the time the\nwaiters_lock is useless.  There is exactly one place where\nthe mutex is not held, and an atomic decrement suffices\nthere.\n\nSigned-off-by: Paolo Bonzini <bonzini@gnu.org>\n---\n compat/win32/pthread.c |   54 +++++++++++++++++++++++++----------------------\n compat/win32/pthread.h |    1 -\n 2 files changed, 29 insertions(+), 26 deletions(-)\n\ndiff --git a/compat/win32/pthread.c b/compat/win32/pthread.c\nindex 010e875..1a38981 100644\n--- a/compat/win32/pthread.c\n+++ b/compat/win32/pthread.c\n@@ -61,7 +61,6 @@ int pthread_cond_init(pthread_cond_t *cond, const void *unused)\n {\n \tcond->waiters = 0;\n \tcond->was_broadcast = 0;\n-\tInitializeCriticalSection(&cond->waiters_lock);\n \n \tcond->sema = CreateSemaphore(NULL, 0, LONG_MAX, NULL);\n \tif (!cond->sema)\n@@ -81,17 +80,17 @@ int pthread_cond_destroy(pthread_cond_t *cond)\n {\n \tCloseHandle(cond->sema);\n \tCloseHandle(cond->continue_broadcast);\n-\tDeleteCriticalSection(&cond->waiters_lock);\n \treturn 0;\n }\n \n int pthread_cond_wait(pthread_cond_t *cond, CRITICAL_SECTION *mutex)\n {\n-\tint last_waiter;\n+\tint num_waiters;\n \n-\tEnterCriticalSection(&cond->waiters_lock);\n+\t/*\n+\t * This access is protected under the mutex.\n+\t */\n \tcond->waiters++;\n-\tLeaveCriticalSection(&cond->waiters_lock);\n \n \t/*\n \t * Unlock external mutex and wait for signal.\n@@ -105,17 +104,17 @@ int pthread_cond_wait(pthread_cond_t *cond, CRITICAL_SECTION *mutex)\n \tWaitForSingleObject(cond->sema, INFINITE);\n \n \t/*\n-\t * Decrease waiters count. If we are the last waiter, then we must\n+\t * Decrease waiters count.  The mutex prevents concurrent increments,\n+\t * so doing this decrement atomically is enough.\n+\t */\n+\tnum_waiters = InterlockedDecrement(&cond->waiters);\n+\n+\t/* If we are the last waiter, then we must\n \t * notify the broadcasting thread that it can continue.\n \t * But if we continued due to cond_signal, we do not have to do that\n \t * because the signaling thread knows that only one waiter continued.\n \t */\n-\tEnterCriticalSection(&cond->waiters_lock);\n-\tcond->waiters--;\n-\tlast_waiter = cond->was_broadcast && cond->waiters == 0;\n-\tLeaveCriticalSection(&cond->waiters_lock);\n-\n-\tif (last_waiter) {\n+\tif (num_waiters == 0 && cond->was_broadcast) {\n \t\t/*\n \t\t * cond_broadcast was issued while mutex was held. This means\n \t\t * that all other waiters have continued, but are contending\n@@ -145,16 +144,17 @@ int pthread_cond_wait(pthread_cond_t *cond, CRITICAL_SECTION *mutex)\n  */\n int pthread_cond_signal(pthread_cond_t *cond)\n {\n-\tint have_waiters;\n-\n-\tEnterCriticalSection(&cond->waiters_lock);\n-\thave_waiters = cond->waiters > 0;\n-\tLeaveCriticalSection(&cond->waiters_lock);\n-\n \t/*\n-\t * Signal only when there are waiters\n+\t * Signal only when there are waiters.  cond->waiters is\n+\t * incremented by pthread_cond_wait under the external lock,\n+\t * so we are safe about that.\n+\t *\n+\t * Waiting threads decrement it outside the external lock, but\n+\t * only if another thread is executing pthread_cond_signal or\n+\t * pthread_cond_broadcast---which means it also cannot be\n+\t * decremented concurrently with this particular access.\n \t */\n-\tif (have_waiters)\n+\tif (cond->waiters > 0)\n \t\treturn ReleaseSemaphore(cond->sema, 1, NULL) ?\n \t\t\t0 : err_win_to_posix(GetLastError());\n \telse\n@@ -168,12 +168,18 @@ int pthread_cond_signal(pthread_cond_t *cond)\n  */\n int pthread_cond_broadcast(pthread_cond_t *cond)\n {\n-\tEnterCriticalSection(&cond->waiters_lock);\n+\t/*\n+\t * As in pthread_cond_signal, access to cond->waiters and\n+\t * cond->was_broadcast is locked via the external mutex.\n+\t */\n \n \tif ((cond->was_broadcast = cond->waiters > 0)) {\n+\t\tBOOLEAN result;\n \t\t/* wake up all waiters */\n-\t\tReleaseSemaphore(cond->sema, cond->waiters, NULL);\n-\t\tLeaveCriticalSection(&cond->waiters_lock);\n+\t\tresult = ReleaseSemaphore(cond->sema, cond->waiters, NULL);\n+\t\tif (!result)\n+\t\t\treturn err_win_to_posix(GetLastError());\n+\n \t\t/*\n \t\t * At this point all waiters continue. Each one takes its\n \t\t * slice of the semaphor. Now it's our turn to wait: Since\n@@ -189,8 +195,6 @@ int pthread_cond_broadcast(pthread_cond_t *cond)\n \t\t * without cond->waiters_lock held.\n \t\t */\n \t\tcond->was_broadcast = 0;\n-\t} else {\n-\t\tLeaveCriticalSection(&cond->waiters_lock);\n \t}\n \treturn 0;\n }\ndiff --git a/compat/win32/pthread.h b/compat/win32/pthread.h\nindex 2e20548..f38c556 100644\n--- a/compat/win32/pthread.h\n+++ b/compat/win32/pthread.h\n@@ -40,7 +40,6 @@ typedef int pthread_mutexattr_t;\n typedef struct {\n \tLONG waiters;\n \tint was_broadcast;\n-\tCRITICAL_SECTION waiters_lock;\n \tHANDLE sema;\n \tHANDLE continue_broadcast;\n } pthread_cond_t;\n-- \n1.7.0.1\n"},{"id":"143159","messageId":"1275917892-16437-3-git-send-email-bonzini@gnu.org","threadId":"24030","inReplyTo":"1275917892-16437-1-git-send-email-bonzini@gnu.org","subject":"[RFT PATCH 2/2] win32: optimize pthread_cond_broadcast","fromName":"Paolo Bonzini","fromEmail":"bonzini@gnu.org","sentAt":"2010-06-07T13:38:12Z","receivedAt":"2010-06-07T13:38:12Z","isPatch":true,"sender":{"key":"bonzini@gnu.org","avatar":"https://avatars.githubusercontent.com/u/42082?v=4"},"body":"If there is a single waiting thread, pthread_cond_signal is the\nsame as pthread_cond_broadcast and no extra synchronization is\nnecessary.\n\nSigned-off-by: Paolo Bonzini <bonzini@gnu.org>\n---\n compat/win32/pthread.c |   19 ++++++++++---------\n 1 files changed, 10 insertions(+), 9 deletions(-)\n\ndiff --git a/compat/win32/pthread.c b/compat/win32/pthread.c\nindex 1a38981..d46a51c 100644\n--- a/compat/win32/pthread.c\n+++ b/compat/win32/pthread.c\n@@ -172,9 +172,10 @@ int pthread_cond_broadcast(pthread_cond_t *cond)\n \t * As in pthread_cond_signal, access to cond->waiters and\n \t * cond->was_broadcast is locked via the external mutex.\n \t */\n-\n-\tif ((cond->was_broadcast = cond->waiters > 0)) {\n+\tif (cond->waiters > 0) {\n \t\tBOOLEAN result;\n+\t\tcond->was_broadcast = cond->waiters > 1;\n+\n \t\t/* wake up all waiters */\n \t\tresult = ReleaseSemaphore(cond->sema, cond->waiters, NULL);\n \t\tif (!result)\n@@ -187,14 +188,14 @@ int pthread_cond_broadcast(pthread_cond_t *cond)\n \t\t * yet. For this reason, we can be sure that no thread gets\n \t\t * a chance to eat *more* than one slice. OTOH, it means\n \t\t * that the last waiter must send us a wake-up.\n+\t\t *\n+\t\t * As an optimization, when there was exactly one waiter\n+\t\t * broadcast is the same as signal and we can skip this step.\n \t\t */\n-\t\tWaitForSingleObject(cond->continue_broadcast, INFINITE);\n-\t\t/*\n-\t\t * Since the external mutex is held, no thread can enter\n-\t\t * cond_wait, and, hence, it is safe to reset this flag\n-\t\t * without cond->waiters_lock held.\n-\t\t */\n-\t\tcond->was_broadcast = 0;\n+\t\tif (cond->was_broadcast) {\n+\t\t\tWaitForSingleObject(cond->continue_broadcast, INFINITE);\n+\t\t\tcond->was_broadcast = 0;\n+\t\t}\n \t}\n \treturn 0;\n }\n-- \n1.7.0.1\n"},{"id":"143246","messageId":"4C0E6CC2.1080605@viscovery.net","threadId":"24030","inReplyTo":"1275917892-16437-2-git-send-email-bonzini@gnu.org","subject":"Re: [RFT PATCH 1/2] win32: optimize condition variable implementation","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2010-06-08T16:16:02Z","receivedAt":"2010-06-08T16:16:02Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 07.06.2010 15:38, schrieb Paolo Bonzini:\n>   int pthread_cond_wait(pthread_cond_t *cond, CRITICAL_SECTION *mutex)\n>   {\n> -\tint last_waiter;\n> +\tint num_waiters;\n>\n> -\tEnterCriticalSection(&cond->waiters_lock);\n> +\t/*\n> +\t * This access is protected under the mutex.\n> +\t */\n>   \tcond->waiters++;\n> -\tLeaveCriticalSection(&cond->waiters_lock);\n>\n>   \t/*\n>   \t * Unlock external mutex and wait for signal.\n> @@ -105,17 +104,17 @@ int pthread_cond_wait(pthread_cond_t *cond, CRITICAL_SECTION *mutex)\n>   \tWaitForSingleObject(cond->sema, INFINITE);\n>\n>   \t/*\n> -\t * Decrease waiters count. If we are the last waiter, then we must\n> +\t * Decrease waiters count.  The mutex prevents concurrent increments,\n> +\t * so doing this decrement atomically is enough.\n> +\t */\n> +\tnum_waiters = InterlockedDecrement(&cond->waiters);\n> +\n> +\t/* If we are the last waiter, then we must\n>   \t * notify the broadcasting thread that it can continue.\n>   \t * But if we continued due to cond_signal, we do not have to do that\n>   \t * because the signaling thread knows that only one waiter continued.\n>   \t */\n> -\tEnterCriticalSection(&cond->waiters_lock);\n> -\tcond->waiters--;\n> -\tlast_waiter = cond->was_broadcast&&  cond->waiters == 0;\n> -\tLeaveCriticalSection(&cond->waiters_lock);\n> -\n> -\tif (last_waiter) {\n> +\tif (num_waiters == 0&&  cond->was_broadcast) {\n>   \t\t/*\n>   \t\t * cond_broadcast was issued while mutex was held. This means\n>   \t\t * that all other waiters have continued, but are contending\n\nThis is not correct. While it is not possible that two threads increment \nwaiters at the same time due to the external mutex, it is still possible \nthat on thread increments, and a different one decrements. You lost all \nprovisions to avoid that.\n\nFurthermore, waiters_lock not only protects waiters, but also the combined \nstate of waiters and was_broadcast. You break this protection. See also here:\n\n> @@ -168,12 +168,18 @@ int pthread_cond_signal(pthread_cond_t *cond)\n>    */\n>   int pthread_cond_broadcast(pthread_cond_t *cond)\n>   {\n> -\tEnterCriticalSection(&cond->waiters_lock);\n> +\t/*\n> +\t * As in pthread_cond_signal, access to cond->waiters and\n> +\t * cond->was_broadcast is locked via the external mutex.\n> +\t */\n>\n>   \tif ((cond->was_broadcast = cond->waiters>  0)) {\n> +\t\tBOOLEAN result;\n>   \t\t/* wake up all waiters */\n> -\t\tReleaseSemaphore(cond->sema, cond->waiters, NULL);\n> -\t\tLeaveCriticalSection(&cond->waiters_lock);\n> +\t\tresult = ReleaseSemaphore(cond->sema, cond->waiters, NULL);\n> +\t\tif (!result)\n> +\t\t\treturn err_win_to_posix(GetLastError());\n> +\n>   \t\t/*\n>   \t\t * At this point all waiters continue. Each one takes its\n>   \t\t * slice of the semaphor. Now it's our turn to wait: Since\n\n-- Hannes\n"},{"id":"143247","messageId":"4C0E6F5C.6050809@gnu.org","threadId":"24030","inReplyTo":"4C0E6CC2.1080605@viscovery.net","subject":"Re: [RFT PATCH 1/2] win32: optimize condition variable implementation","fromName":"Paolo Bonzini","fromEmail":"bonzini@gnu.org","sentAt":"2010-06-08T16:27:08Z","receivedAt":"2010-06-08T16:27:08Z","isPatch":true,"sender":{"key":"bonzini@gnu.org","avatar":"https://avatars.githubusercontent.com/u/42082?v=4"},"body":"On 06/08/2010 06:16 PM, Johannes Sixt wrote:\n> This is not correct. While it is not possible that two threads increment\n> waiters at the same time due to the external mutex, it is still possible\n> that on thread increments, and a different one decrements. You lost all\n> provisions to avoid that.\n\nActually, the patch is only relying more widely on the preexisting \nassumptions of the code:\n\n/*\n  * IMPORTANT: This implementation requires that pthread_cond_signal\n  * is called while the mutex is held that is used in the corresponding\n  * pthread_cond_wait calls!\n  */\n\n/*\n  * IMPORTANT: This implementation requires that pthread_cond_broadcast\n  * is called while the mutex is held that is used in the corresponding\n  * pthread_cond_wait calls!\n  */\n\nDuring the locked decrements, but then the external mutex is held by the \nthread executing pthread_cond_signal/pthread_cond_broadcast, so that \nsection of the code is still protected against increments.\n\n> Furthermore, waiters_lock not only protects waiters, but also the\n> combined state of waiters and was_broadcast.\n\nConcurrent pthread_cond_broadcast are protected by the external mutex, \nand was_broadcast is similarly protected against increments of waiters.\n\nFuthermore, access to was_broadcast is serialized between \npthread_cond_wait and pthread_cond_broadcast through the semaphore and \nthe event.  was_broadcast may change from 0 to 1 while pthread_cond_wait \nis not holding the external mutex, but then pthread_cond_wait is \nsleeping on the semaphore or will go to sleep very soon.  And it can \nchange from 1 to 0 only after pthread_cond_wait has signaled the event, \nwhich means pthread_cond_wait will be waiting to reacquire the external \nmutex.\n\nPaolo\n"},{"id":"143249","messageId":"4C0E7015.8030504@viscovery.net","threadId":"24030","inReplyTo":"1275917892-16437-3-git-send-email-bonzini@gnu.org","subject":"Re: [RFT PATCH 2/2] win32: optimize pthread_cond_broadcast","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2010-06-08T16:30:13Z","receivedAt":"2010-06-08T16:30:13Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 07.06.2010 15:38, schrieb Paolo Bonzini:\n> @@ -172,9 +172,10 @@ int pthread_cond_broadcast(pthread_cond_t *cond)\n>   \t * As in pthread_cond_signal, access to cond->waiters and\n>   \t * cond->was_broadcast is locked via the external mutex.\n>   \t */\n> -\n> -\tif ((cond->was_broadcast = cond->waiters>  0)) {\n> +\tif (cond->waiters>  0) {\n>   \t\tBOOLEAN result;\n> +\t\tcond->was_broadcast = cond->waiters>  1;\n> +\n\nIt is possible that you set was_broadcast to 1 here, while another thread \nstill sees was_broadcast == 0 in cond_wait. As a consequence, this thread \nWaitsForSingleObject(), which will never arrive because the other thread \ndoes not call SetEvent(). But this is more a problem of your first patch, \nnot of this one, so you better fix the first one first before you go \nfurther into this one.\n\nThat said, as long as this series buys performance only at the expense of \nclarity, I'm rather opposed to it because we do not call cond_wait and \ncond_broadcast in time-critical paths.\n\n-- Hannes\n"},{"id":"143254","messageId":"4C0E71B2.1060904@gnu.org","threadId":"24030","inReplyTo":"4C0E7015.8030504@viscovery.net","subject":"Re: [RFT PATCH 2/2] win32: optimize pthread_cond_broadcast","fromName":"Paolo Bonzini","fromEmail":"bonzini@gnu.org","sentAt":"2010-06-08T16:37:06Z","receivedAt":"2010-06-08T16:37:06Z","isPatch":true,"sender":{"key":"bonzini@gnu.org","avatar":"https://avatars.githubusercontent.com/u/42082?v=4"},"body":"On 06/08/2010 06:30 PM, Johannes Sixt wrote:\n> Am 07.06.2010 15:38, schrieb Paolo Bonzini:\n>> @@ -172,9 +172,10 @@ int pthread_cond_broadcast(pthread_cond_t *cond)\n>> * As in pthread_cond_signal, access to cond->waiters and\n>> * cond->was_broadcast is locked via the external mutex.\n>> */\n>> -\n>> - if ((cond->was_broadcast = cond->waiters> 0)) {\n>> + if (cond->waiters> 0) {\n>> BOOLEAN result;\n>> + cond->was_broadcast = cond->waiters> 1;\n>> +\n>\n> It is possible that you set was_broadcast to 1 here, while another\n> thread still sees was_broadcast == 0 in cond_wait.\n\nThat still cannot happen, because pthread_cond_wait will be locked on \nthe semaphore until the ReleaseSemaphore.  The only race that exists is \nbetween broadcast/signal's ReleaseSemaphore and wait's \nWaitForSingleObject.  This is benign, and exists before my patch.  But \nin all cases the code before ReleaseSemaphore is serialized WRT to the \ncode after wait's WaitForSingleObject.\n\n> That said, as long as this series buys performance only at the expense\n> of clarity, I'm rather opposed to it because we do not call cond_wait\n> and cond_broadcast in time-critical paths.\n\nYes, it is less clear indeed.  I tried to compensate with comments but \nthat was not enough apparently.  As I said I did this patch for another \nproject where condvars are used in time-critical paths; if you do not \nwant to keep it, that's not a problem.\n\nPaolo\n"},{"id":"143263","messageId":"4C0E8FF9.7020500@viscovery.net","threadId":"24030","inReplyTo":"4C0E71B2.1060904@gnu.org","subject":"Re: [RFT PATCH 2/2] win32: optimize pthread_cond_broadcast","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2010-06-08T18:46:17Z","receivedAt":"2010-06-08T18:46:17Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 08.06.2010 18:37, schrieb Paolo Bonzini:\n> On 06/08/2010 06:30 PM, Johannes Sixt wrote:\n>> Am 07.06.2010 15:38, schrieb Paolo Bonzini:\n>>> @@ -172,9 +172,10 @@ int pthread_cond_broadcast(pthread_cond_t *cond)\n>>> * As in pthread_cond_signal, access to cond->waiters and\n>>> * cond->was_broadcast is locked via the external mutex.\n>>> */\n>>> -\n>>> - if ((cond->was_broadcast = cond->waiters> 0)) {\n>>> + if (cond->waiters> 0) {\n>>> BOOLEAN result;\n>>> + cond->was_broadcast = cond->waiters> 1;\n>>> +\n>>\n>> It is possible that you set was_broadcast to 1 here, while another\n>> thread still sees was_broadcast == 0 in cond_wait.\n>\n> That still cannot happen, because pthread_cond_wait will be locked on\n> the semaphore until the ReleaseSemaphore. The only race that exists is\n> between broadcast/signal's ReleaseSemaphore and wait's\n> WaitForSingleObject. This is benign, and exists before my patch. But in\n> all cases the code before ReleaseSemaphore is serialized WRT to the code\n> after wait's WaitForSingleObject.\n\nI think I've stared at the code long enough now to see that you are right. \nAll counterexamples that I thought I could make up to disprove you didn't \ndo it :-)\n\n-- Hannes\n"},{"id":"143602","messageId":"1276424212-13634-1-git-send-email-bonzini@gnu.org","threadId":"24030","inReplyTo":"1275917892-16437-1-git-send-email-bonzini@gnu.org","subject":"[PATCH 3/2] fix race in win32 pthread_cond_signal causing spurious wakeups","fromName":"Paolo Bonzini","fromEmail":"bonzini@gnu.org","sentAt":"2010-06-13T10:16:52Z","receivedAt":"2010-06-13T10:16:52Z","isPatch":true,"sender":{"key":"bonzini@gnu.org","avatar":"https://avatars.githubusercontent.com/u/42082?v=4"},"body":"This patch fixes a bug in the win32 condvar implementation.  The bug\nexisted originally in pthread_cond_signal before my other recent patches;\nhowever, my patches extended the bug to pthread_cond_broadcast because\nthey made it behave exactly like pthread_cond_signal when there is only\none waiter.\n\nThe bug causes spurious wakeups in pthread_cond_wait.  These are explicitly\nallowed by POSIX, but it's better to prevent them in the first place.\nIt occurs if pthread_cond_signal is called two times with only one waiter,\nand the waiter is not scheduled between the two calls.  In this case, the\nsecond call will find cond->num_waiters == 1 and ReleaseSemaphore will\nmake the semaphore's count positive, thus causing a spurious wakeup on\nthe next pthread_cond_wait.\n\nThe solution is to decrease cond->waiters in pthread_cond_signal.  This\nmaintains the invariant that _before_ the external mutex is unlocked\ncond->num_waiters matches the waiters count of the semaphore.  This\ninvariant holds for all three functions.\n\nBroadcasting does not have the problem and uses the same algorithm as\nbefore.\n\nSigned-off-by: Paolo Bonzini <bonzini@gnu.org>\n---\n        I numbered this patch 3/2 because it's on top of the other two,\n        but it can be backported to master pretty easily.\n\n compat/win32/pthread.c |   68 ++++++++++++++++++++++++------------------------\n 1 files changed, 34 insertions(+), 34 deletions(-)\n\ndiff --git a/compat/win32/pthread.c b/compat/win32/pthread.c\nindex d46a51c..9aaac89 100644\n--- a/compat/win32/pthread.c\n+++ b/compat/win32/pthread.c\n@@ -103,32 +103,27 @@ int pthread_cond_wait(pthread_cond_t *cond, CRITICAL_SECTION *mutex)\n \tWaitForSingleObject(cond->sema, INFINITE);\n \n \t/*\n-\t * Decrease waiters count.  The mutex is not taken, so we have to\n-\t * do this atomically.\n-\t */\n-\tnum_waiters = InterlockedDecrement(&cond->waiters);\n-\n-\t/* If we are the last waiter, then we must\n-\t * notify the broadcasting thread that it can continue.\n-\t * But if we continued due to cond_signal, we do not have to do that\n-\t * because the signaling thread knows that only one waiter continued.\n+\t * If the condvar was broadcast, then waiters cooperate to notify\n+\t * the broadcasting thread that they have woken, so that it can\n+\t * continue.  For cond_signal we do not have to do that because the\n+\t * signaling thread knows that only one waiter continued.  Also,\n+\t * cond_signal will decrement num_waiters itself, to ensure it is\n+\t * always a faithful reproduction of the semaphore's state.\n \t */\n-\tif (num_waiters == 0 && cond->was_broadcast) {\n+\tif (cond->was_broadcast) {\n \t\t/*\n-\t\t * cond_broadcast was issued while mutex was held. This means\n-\t\t * that all other waiters have continued, but are contending\n-\t\t * for the mutex at the end of this function because the\n-\t\t * broadcasting thread did not leave cond_broadcast, yet.\n-\t\t * (This is so that it can be sure that each waiter has\n-\t\t * consumed exactly one slice of the semaphor.)\n-\t\t * The last waiter must tell the broadcasting thread that it\n-\t\t * can go on.\n-\t\t */\n-\t\tSetEvent(cond->continue_broadcast);\n-\t\t/*\n-\t\t * Now we go on to contend with all other waiters for\n-\t\t * the mutex. Auf in den Kampf!\n+\t\t * Decrease waiters count.  The mutex is not taken, so we have\n+\t\t * to do this atomically.\n+\t\t *\n+\t\t * cond_broadcast was issued while mutex was held, so all\n+\t\t * waiters contend for the mutex at the end of this function\n+\t\t * until the broadcasting thread relinquishes it.  To ensure\n+\t\t * each waiter consumes exactly one slice of the semaphore,\n+\t\t * the broadcasting thread stops until it is told by the last\n+\t\t * waiter that it can go on.\n \t\t */\n+\t\tif (InterlockedDecrement(&cond->waiters) == 0)\n+\t\t\tSetEvent(cond->continue_broadcast);\n \t}\n \t/* lock external mutex again */\n \tEnterCriticalSection(mutex);\n@@ -150,14 +144,15 @@ int pthread_cond_signal(pthread_cond_t *cond)\n \t * so we are safe about that.\n \t *\n \t * Waiting threads decrement it outside the external lock, but\n-\t * only if another thread is executing pthread_cond_signal or\n-\t * pthread_cond_broadcast---which means it also cannot be\n-\t * decremented concurrently with this particular access.\n+\t * only if another thread is executing pthread_cond_broadcast.\n+\t * So, it also cannot be decremented concurrently with this\n+\t * particular access.\n \t */\n-\tif (cond->waiters > 0)\n+\tif (cond->waiters > 0) {\n+\t\tcond->waiters--;\n \t\treturn ReleaseSemaphore(cond->sema, 1, NULL) ?\n \t\t\t0 : err_win_to_posix(GetLastError());\n-\telse\n+\t} else\n \t\treturn 0;\n }\n \n@@ -174,7 +169,15 @@ int pthread_cond_broadcast(pthread_cond_t *cond)\n \t */\n \tif (cond->waiters > 0) {\n \t\tBOOLEAN result;\n-\t\tcond->was_broadcast = cond->waiters > 1;\n+\t\t/*\n+\t\t * As an optimization, when there was exactly one waiter\n+\t\t * broadcast is the same as signal, so we use the asynchronous\n+\t\t * algorithm that signal uses.\n+\t\t */\n+\t\tif (cond->waiters == 1)\n+\t\t\tcond->waiters = 0;\n+\t\telse\n+\t\t\tcond->was_broadcast = 1;\n \n \t\t/* wake up all waiters */\n \t\tresult = ReleaseSemaphore(cond->sema, cond->waiters, NULL);\n@@ -183,14 +186,11 @@ int pthread_cond_broadcast(pthread_cond_t *cond)\n \n \t\t/*\n \t\t * At this point all waiters continue. Each one takes its\n-\t\t * slice of the semaphor. Now it's our turn to wait: Since\n+\t\t * slice of the semaphore. Now it's our turn to wait: Since\n \t\t * the external mutex is held, no thread can leave cond_wait,\n \t\t * yet. For this reason, we can be sure that no thread gets\n \t\t * a chance to eat *more* than one slice. OTOH, it means\n \t\t * that the last waiter must send us a wake-up.\n-\t\t *\n-\t\t * As an optimization, when there was exactly one waiter\n-\t\t * broadcast is the same as signal and we can skip this step.\n \t\t */\n \t\tif (cond->was_broadcast) {\n \t\t\tWaitForSingleObject(cond->continue_broadcast, INFINITE);\n-- \n1.7.0.1\n"}]}