Re: [PATCH]: update tls and lock tests, gl_cond_t WIN32 implementation

[Bruno Haible]

Hi Yoann,

You wrote on 2008-09-18 
<http://lists.gnu.org/archive/html/bug-gnulib/2008-09/msg00194.html>
and 2008-10-02 
<http://lists.gnu.org/archive/html/bug-gnulib/2008-10/msg00027.html>:

> provide a working implementation of gl_cond_t for WIN32 platform
> (based on http://www.cs.wustl.edu/~schmidt/win32-cv-1.html).

Thanks a lot for this. Took me a long time, but I'm now committing a modified
version of your implementation. At first, I had overlooked your mail and tried
to produce an implementation by myself. But it did not pass the test_timedcond
test. Gladly I then took your implementation, because it passed all tests :-)

Nevertheless, I had to make many changes:
  - in cond.h, adding comments to the struct definition,
  - in cond.h, the generation count was of type 'int'. But when an 'int'
    wraps around, the program can crash, according to ISO C99. Making it of
    type 'unsigned int' avoids that.
  - added a dependency to the 'gettimeofday' module,
  - many whitespace changes, for GNU coding style,
  - glthread_cond_wait_func ignored the return value of glthread_lock_unlock
    and glthread_lock_lock.
  - glthread_cond_timedwait_func had a completely wrong handling of the
    timeout. The conversion from absolute time to milliseconds was only done
    once, at the beginning. But because some locks need to be taken - which
    can introduce delays - and because WaitForSingleObject is invoked in a loop,
    the conversion from absolute time to milliseconds must be done just
    before WaitForSingleObject, once in each loop iteration. Additionally,
    during this conversion an integer overflow could occur in at least 2 places
    (1. result->tv_sec = x->tv_sec - y->tv_sec
     2. (res.tv_sec * 1000) + (res.tv_usec / 1000)).
  - In glthread_cond_signal_func and glthread_cond_broadcast_func there is
    no need to force the initialization of the condition variable. According
    to POSIX, a return value EINVAL is fine in this case.
  - glthread_cond_destroy_func was not deleting the critical section object,
    possibly leaking system resources.

I haven't tested this modified version, but will, in a few days.

Bruno


2008-10-11  Yoann Vandoorselaere  <address@hidden>
            Bruno Haible  <address@hidden>

        Provide a Win32 implementation of the 'cond' module.
        * lib/glthread/cond.h [USE_WIN32]: New implementation.
        * lib/glthread/cond.c (glthread_cond_init_func,
        glthread_cond_wait_func, glthread_cond_timedwait_func,
        glthread_cond_signal_func, glthread_cond_broadcast_func,
        glthread_cond_destroy_func) [USE_WIN32]: New functions.
        * modules/cond (Dependencies): Add gettimeofday.

*** lib/glthread/cond.h.orig    2008-10-12 00:10:05.000000000 +0200
--- lib/glthread/cond.h 2008-10-11 21:37:48.000000000 +0200
***************
*** 269,275 ****
  
  /* ========================================================================= 
*/
  
! #if !(USE_POSIX_THREADS || USE_PTH_THREADS || USE_SOLARIS_THREADS)
  
  /* Provide dummy implementation if threads are not supported.  */
  
--- 269,332 ----
  
  /* ========================================================================= 
*/
  
! #if USE_WIN32_THREADS
! 
! # include <windows.h>
! 
! # ifdef __cplusplus
! extern "C" {
! # endif
! 
! /* -------------------------- gl_cond_t datatype -------------------------- */
! 
! typedef struct
!         {
!           gl_spinlock_t guard; /* protects the initialization */
!           CRITICAL_SECTION lock; /* protects the remaining fields */
!           HANDLE event; /* an event configured for manual reset */
!           unsigned int waiters_count; /* number of threads currently waiting 
*/
!           unsigned int release_count; /* number of threads that are currently
!                                          being notified but have not yet
!                                          acknowledged. Always
!                                          release_count <= waiters_count */
!           unsigned int wait_generation_count; /* incremented each time a 
signal
!                                                  or broadcast is performed */
!         }
!         gl_cond_t;
! # define gl_cond_define(STORAGECLASS, NAME) \
!     STORAGECLASS gl_cond_t NAME;
! # define gl_cond_define_initialized(STORAGECLASS, NAME) \
!     STORAGECLASS gl_cond_t NAME = gl_cond_initializer;
! # define gl_cond_initializer \
!     { { 0, -1 } }
! # define glthread_cond_init(COND) \
!     glthread_cond_init_func (COND)
! # define glthread_cond_wait(COND, LOCK) \
!     glthread_cond_wait_func (COND, LOCK)
! # define glthread_cond_timedwait(COND, LOCK, ABSTIME) \
!     glthread_cond_timedwait_func (COND, LOCK, ABSTIME)
! # define glthread_cond_signal(COND) \
!     glthread_cond_signal_func (COND)
! # define glthread_cond_broadcast(COND) \
!     glthread_cond_broadcast_func (COND)
! # define glthread_cond_destroy(COND) \
!     glthread_cond_destroy_func (COND)
! extern int glthread_cond_init_func (gl_cond_t *cond);
! extern int glthread_cond_wait_func (gl_cond_t *cond, gl_lock_t *lock);
! extern int glthread_cond_timedwait_func (gl_cond_t *cond, gl_lock_t *lock, 
struct timespec *abstime);
! extern int glthread_cond_signal_func (gl_cond_t *cond);
! extern int glthread_cond_broadcast_func (gl_cond_t *cond);
! extern int glthread_cond_destroy_func (gl_cond_t *cond);
! 
! # ifdef __cplusplus
! }
! # endif
! 
! #endif
! 
! /* ========================================================================= 
*/
! 
! #if !(USE_POSIX_THREADS || USE_PTH_THREADS || USE_SOLARIS_THREADS || 
USE_WIN32_THREADS)
  
  /* Provide dummy implementation if threads are not supported.  */
  
*** lib/glthread/cond.c.orig    2008-10-12 00:10:05.000000000 +0200
--- lib/glthread/cond.c 2008-10-12 00:08:06.000000000 +0200
***************
*** 15,21 ****
     along with this program; if not, write to the Free Software Foundation,
     Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  
! /* Written by Yoann Vandoorselaere <address@hidden>, 2008.  */
  
  #include <config.h>
  
--- 15,22 ----
     along with this program; if not, write to the Free Software Foundation,
     Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  
! /* Written by Yoann Vandoorselaere <address@hidden>, 2008,
!    and Bruno Haible <address@hidden>, 2008.  */
  
  #include <config.h>
  
***************
*** 71,73 ****
--- 72,381 ----
  #endif
  
  /* ========================================================================= 
*/
+ 
+ #if USE_WIN32_THREADS
+ 
+ #include <sys/time.h>
+ 
+ /* -------------------------- gl_cond_t datatype -------------------------- */
+ 
+ /* This implementation is based on the article
+    Douglas C. Schmidt, Irfan Pyarali
+    "Strategies for Implementing POSIX Condition Variables on Win32"
+    <http://www.cs.wustl.edu/~schmidt/win32-cv-1.html>  */
+ 
+ int
+ glthread_cond_init_func (gl_cond_t *cond)
+ {
+   InitializeCriticalSection (&cond->lock);
+   /* Create a manual-reset event.  */
+   cond->event = CreateEvent (NULL, TRUE, FALSE, NULL);
+   cond->waiters_count = 0;
+   cond->release_count = 0;
+   cond->wait_generation_count = 0;
+ 
+   cond->guard.done = 1;
+ 
+   return 0;
+ }
+ 
+ int
+ glthread_cond_wait_func (gl_cond_t *cond, gl_lock_t *lock)
+ {
+   if (!cond->guard.done)
+     {
+       if (InterlockedIncrement (&cond->guard.started) == 0)
+       /* This thread is the first one to need this condition variable.
+          Initialize it.  */
+       glthread_cond_init (cond);
+       else
+       /* Yield the CPU while waiting for another thread to finish
+          initializing this condition variable.  */
+       while (!cond->guard.done)
+         Sleep (0);
+     }
+ 
+   {
+     unsigned old_generation_count;
+     HANDLE event;
+ 
+     EnterCriticalSection (&cond->lock);
+     /* Increment waiters_count,
+        and get a copy of the current wait_generation_count.  */
+     cond->waiters_count++;
+     old_generation_count = cond->wait_generation_count;
+     event = cond->event;
+     LeaveCriticalSection (&cond->lock);
+ 
+     {
+       /* Now release the lock and let any other thread take it.  */
+       int err = glthread_lock_unlock (lock);
+       if (err != 0)
+       {
+         EnterCriticalSection (&cond->lock);
+         cond->waiters_count--;
+         LeaveCriticalSection (&cond->lock);
+         return err;
+       }
+ 
+       {
+       /* Wait until another thread signals this event.  */
+       DWORD result;
+ 
+       for (;;)
+         {
+           bool wait_done;
+ 
+           result = WaitForSingleObject (event, INFINITE);
+           if (result != WAIT_OBJECT_0)
+             break;
+           /* Distingish intended from spurious wakeups.  */
+           EnterCriticalSection (&cond->lock);
+           wait_done =
+             (cond->release_count > 0
+              && cond->wait_generation_count != old_generation_count);
+           LeaveCriticalSection (&cond->lock);
+           if (wait_done)
+             break;
+         }
+ 
+       /* Take the lock again.  */
+       err = glthread_lock_lock (lock);
+ 
+       /* Do the bookkeeping.  */
+       EnterCriticalSection (&cond->lock);
+       cond->waiters_count--;
+       if (result == WAIT_OBJECT_0)
+         {
+           /* The wait terminated because the event was signaled.
+              Acknowledge the receipt.  */
+           if (--cond->release_count == 0)
+             {
+               /* The last waiting thread to be notified has to reset
+                  the event.  */
+               ResetEvent (cond->event);
+             }
+         }
+       LeaveCriticalSection (&cond->lock);
+ 
+       return (err ? err :
+               ret == WAIT_OBJECT_0 ? 0 :
+               /* WAIT_FAILED shouldn't happen */ EAGAIN);
+       }
+     }
+   }
+ }
+ 
+ int
+ glthread_cond_timedwait_func (gl_cond_t *cond, gl_lock_t *lock, struct 
timespec *abstime)
+ {
+   struct timeval currtime;
+ 
+   gettimeofday (&currtime, NULL);
+   if (currtime.tv_sec > abstime->tv_sec
+       || (currtime.tv_sec == abstime->tv_sec
+         && currtime.tv_usec * 1000 >= abstime->tv_nsec))
+     return ETIMEDOUT;
+ 
+   if (!cond->guard.done)
+     {
+       if (InterlockedIncrement (&cond->guard.started) == 0)
+       /* This thread is the first one to need this condition variable.
+          Initialize it.  */
+       glthread_cond_init (cond);
+       else
+       /* Yield the CPU while waiting for another thread to finish
+          initializing this condition variable.  */
+       while (!cond->guard.done)
+         Sleep (0);
+     }
+ 
+   {
+     unsigned old_generation_count;
+     HANDLE event;
+ 
+     EnterCriticalSection (&cond->lock);
+     /* Increment waiters_count,
+        and get a copy of the current wait_generation_count.  */
+     cond->waiters_count++;
+     old_generation_count = cond->wait_generation_count;
+     event = cond->event;
+     LeaveCriticalSection (&cond->lock);
+ 
+     {
+       /* Now release the lock and let any other thread take it.  */
+       int err = glthread_lock_unlock (lock);
+       if (err != 0)
+       {
+         EnterCriticalSection (&cond->lock);
+         cond->waiters_count--;
+         LeaveCriticalSection (&cond->lock);
+         return err;
+       }
+ 
+       {
+       /* Wait until another thread signals this event or until the abstime
+          passes.  */
+       DWORD result;
+ 
+       for (;;)
+         {
+           DWORD timeout;
+           bool wait_done;
+ 
+           gettimeofday (&currtime, NULL);
+           if (currtime.tv_sec > abstime->tv_sec)
+             timeout = 0;
+           else
+             {
+               unsigned long seconds = abstime->tv_sec - currtime.tv_sec;
+               timeout = seconds * 1000;
+               if (timeout / 1000 != seconds) /* overflow? */
+                 timeout = INFINITE;
+               else
+                 {
+                   long milliseconds =
+                     abstime->tv_nsec / 1000000 - currtime.tv_usec / 1000;
+                   if (milliseconds >= 0)
+                     {
+                       timeout += milliseconds;
+                       if (timeout < milliseconds) /* overflow? */
+                         timeout = INFINITE;
+                     }
+                   else
+                     {
+                       if (timeout >= - milliseconds)
+                         timeout -= (- milliseconds);
+                       else
+                         timeout = 0;
+                     }
+                 }
+             }
+ 
+           result = WaitForSingleObject (event, timeout);
+           if (result != WAIT_OBJECT_0)
+             break;
+           /* Distingish intended from spurious wakeups.  */
+           EnterCriticalSection (&cond->lock);
+           wait_done =
+             (cond->release_count > 0
+              && cond->wait_generation_count != old_generation_count);
+           LeaveCriticalSection (&cond->lock);
+           if (wait_done)
+             break;
+         }
+ 
+       /* Take the lock again.  */
+       err = glthread_lock_lock (lock);
+ 
+       /* Do the bookkeeping.  */
+       EnterCriticalSection (&cond->lock);
+       cond->waiters_count--;
+       if (result == WAIT_OBJECT_0)
+         {
+           /* The wait terminated because the event was signaled.
+              Acknowledge the receipt.  */
+           if (--cond->release_count == 0)
+             {
+               /* The last waiting thread to be notified has to reset
+                  the event.  */
+               ResetEvent (cond->event);
+             }
+         }
+       LeaveCriticalSection (&cond->lock);
+ 
+       return (err ? err :
+               ret == WAIT_OBJECT_0 ? 0 :
+               ret == WAIT_TIMEOUT ? ETIMEDOUT :
+               /* WAIT_FAILED shouldn't happen */ EAGAIN);
+       }
+     }
+   }
+ }
+ 
+ int
+ glthread_cond_signal_func (gl_cond_t *cond)
+ {
+   if (!cond->guard.done)
+     return EINVAL;
+ 
+   EnterCriticalSection (&cond->lock);
+   /* POSIX says:
+       "The pthread_cond_broadcast() and pthread_cond_signal() functions shall
+        have no effect if there are no threads currently blocked on cond."
+      Also, if  waiters_count == release_count > 0, all blocked threads will
+      be unblocked soon anyway; do nothing in this case as well.  */
+   if (cond->waiters_count > cond->release_count)
+     {
+       /* Signal the manual-reset event.  */
+       SetEvent (cond->event);
+       /* ... and reset it is soon as one of the currently waiting threads has
+        acknowledged the receipt of the signal.  */
+       cond->release_count++;
+       cond->wait_generation_count++;
+     }
+   LeaveCriticalSection (&cond->lock);
+ 
+   return 0;
+ }
+ 
+ int
+ glthread_cond_broadcast_func (gl_cond_t *cond)
+ {
+   if (!cond->guard.done)
+     return EINVAL;
+ 
+   EnterCriticalSection (&cond->lock);
+   /* POSIX says:
+       "The pthread_cond_broadcast() and pthread_cond_signal() functions shall
+        have no effect if there are no threads currently blocked on cond."  */
+   if (cond->waiters_count > 0)
+     {
+       /* Signal the manual-reset event.  */
+       SetEvent (cond->event);
+       /* ... and reset it only after all currently waiting threads have
+        acknowledged the receipt of the signal.  */
+       cond->release_count = cond->waiters_count;
+       cond->wait_generation_count++;
+     }
+   LeaveCriticalSection (&cond->lock);
+ 
+   return 0;
+ }
+ 
+ int
+ glthread_cond_destroy_func (gl_cond_t *cond)
+ {
+   if (!cond->guard.done)
+     return EINVAL;
+   if (cond->waiters_count > 0)
+     return EBUSY;
+   CloseHandle (cond->event);
+   DeleteCriticalSection (&cond->lock);
+   cond->guard.done = 0;
+   return 0;
+ }
+ 
+ #endif
+ 
+ /* ========================================================================= 
*/
*** modules/cond.orig   2008-10-12 00:10:05.000000000 +0200
--- modules/cond        2008-10-11 20:31:26.000000000 +0200
***************
*** 12,17 ****
--- 12,18 ----
  errno
  stdbool
  time
+ gettimeofday
  
  configure.ac:
  gl_COND