lib/windows-timedrwlock.c

   1 /* Timed read-write locks (native Windows implementation).
   2    Copyright (C) 2005-2020 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, see <https://www.gnu.org/licenses/>.  */
  16
  17 /* Written by Bruno Haible <bruno@clisp.org>, 2019.  */
  18
  19 #include <config.h>
  20
  21 /* Specification.  */
  22 #include "windows-timedrwlock.h"
  23
  24 #include <errno.h>
  25 #include <stdbool.h>
  26 #include <stdlib.h>
  27 #include <sys/time.h>
  28
  29 /* In this file, the waitqueues are implemented as linked lists.  */
  30 #define glwthread_waitqueue_t glwthread_clinked_waitqueue_t
  31
  32 /* All links of a circular list, except the anchor, are of this type, carrying
  33    a payload.  */
  34 struct glwthread_waitqueue_element
  35 {
  36   struct glwthread_waitqueue_link link; /* must be the first field! */
  37   HANDLE event; /* Waiting thread, represented by an event.
  38                    This field is immutable once initialized. */
  39 };
  40
  41 static void
  42 glwthread_waitqueue_init (glwthread_waitqueue_t *wq)
  43 {
  44   wq->wq_list.wql_next = &wq->wq_list;
  45   wq->wq_list.wql_prev = &wq->wq_list;
  46   wq->count = 0;
  47 }
  48
  49 /* Enqueues the current thread, represented by an event, in a wait queue.
  50    Returns NULL if an allocation failure occurs.  */
  51 static struct glwthread_waitqueue_element *
  52 glwthread_waitqueue_add (glwthread_waitqueue_t *wq)
  53 {
  54   struct glwthread_waitqueue_element *elt;
  55   HANDLE event;
  56
  57   /* Allocate the memory for the waitqueue element on the heap, not on the
  58      thread's stack.  If the thread exits unexpectedly, we prefer to leak
  59      some memory rather than to access unavailable memory and crash.  */
  60   elt =
  61     (struct glwthread_waitqueue_element *)
  62     malloc (sizeof (struct glwthread_waitqueue_element));
  63   if (elt == NULL)
  64     /* No more memory.  */
  65     return NULL;
  66
  67   /* Whether the created event is a manual-reset one or an auto-reset one,
  68      does not matter, since we will wait on it only once.  */
  69   event = CreateEvent (NULL, TRUE, FALSE, NULL);
  70   if (event == INVALID_HANDLE_VALUE)
  71     {
  72       /* No way to allocate an event.  */
  73       free (elt);
  74       return NULL;
  75     }
  76   elt->event = event;
  77   /* Insert elt at the end of the circular list.  */
  78   (elt->link.wql_prev = wq->wq_list.wql_prev)->wql_next = &elt->link;
  79   (elt->link.wql_next = &wq->wq_list)->wql_prev = &elt->link;
  80   wq->count++;
  81   return elt;
  82 }
  83
  84 /* Removes the current thread, represented by a
  85    'struct glwthread_waitqueue_element *', from a wait queue.
  86    Returns true if is was found and removed, false if it was not present.  */
  87 static bool
  88 glwthread_waitqueue_remove (glwthread_waitqueue_t *wq,
  89                             struct glwthread_waitqueue_element *elt)
  90 {
  91   if (elt->link.wql_next != NULL && elt->link.wql_prev != NULL)
  92     {
  93       /* Remove elt from the circular list.  */
  94       struct glwthread_waitqueue_link *prev = elt->link.wql_prev;
  95       struct glwthread_waitqueue_link *next = elt->link.wql_next;
  96       prev->wql_next = next;
  97       next->wql_prev = prev;
  98       elt->link.wql_next = NULL;
  99       elt->link.wql_prev = NULL;
 100       wq->count--;
 101       return true;
 102     }
 103   else
 104     return false;
 105 }
 106
 107 /* Notifies the first thread from a wait queue and dequeues it.  */
 108 static void
 109 glwthread_waitqueue_notify_first (glwthread_waitqueue_t *wq)
 110 {
 111   if (wq->wq_list.wql_next != &wq->wq_list)
 112     {
 113       struct glwthread_waitqueue_element *elt =
 114         (struct glwthread_waitqueue_element *) wq->wq_list.wql_next;
 115       struct glwthread_waitqueue_link *prev;
 116       struct glwthread_waitqueue_link *next;
 117
 118       /* Remove elt from the circular list.  */
 119       prev = &wq->wq_list; /* = elt->link.wql_prev; */
 120       next = elt->link.wql_next;
 121       prev->wql_next = next;
 122       next->wql_prev = prev;
 123       elt->link.wql_next = NULL;
 124       elt->link.wql_prev = NULL;
 125       wq->count--;
 126
 127       SetEvent (elt->event);
 128       /* After the SetEvent, this thread cannot access *elt any more, because
 129          the woken-up thread will quickly call  free (elt).  */
 130     }
 131 }
 132
 133 /* Notifies all threads from a wait queue and dequeues them all.  */
 134 static void
 135 glwthread_waitqueue_notify_all (glwthread_waitqueue_t *wq)
 136 {
 137   struct glwthread_waitqueue_link *l;
 138
 139   for (l = wq->wq_list.wql_next; l != &wq->wq_list; )
 140     {
 141       struct glwthread_waitqueue_element *elt =
 142         (struct glwthread_waitqueue_element *) l;
 143       struct glwthread_waitqueue_link *prev;
 144       struct glwthread_waitqueue_link *next;
 145
 146       /* Remove elt from the circular list.  */
 147       prev = &wq->wq_list; /* = elt->link.wql_prev; */
 148       next = elt->link.wql_next;
 149       prev->wql_next = next;
 150       next->wql_prev = prev;
 151       elt->link.wql_next = NULL;
 152       elt->link.wql_prev = NULL;
 153       wq->count--;
 154
 155       SetEvent (elt->event);
 156       /* After the SetEvent, this thread cannot access *elt any more, because
 157          the woken-up thread will quickly call  free (elt).  */
 158
 159       l = next;
 160     }
 161   if (!(wq->wq_list.wql_next == &wq->wq_list
 162         && wq->wq_list.wql_prev == &wq->wq_list
 163         && wq->count == 0))
 164     abort ();
 165 }
 166
 167 void
 168 glwthread_timedrwlock_init (glwthread_timedrwlock_t *lock)
 169 {
 170   InitializeCriticalSection (&lock->lock);
 171   glwthread_waitqueue_init (&lock->waiting_readers);
 172   glwthread_waitqueue_init (&lock->waiting_writers);
 173   lock->runcount = 0;
 174   lock->guard.done = 1;
 175 }
 176
 177 int
 178 glwthread_timedrwlock_rdlock (glwthread_timedrwlock_t *lock)
 179 {
 180   if (!lock->guard.done)
 181     {
 182       if (InterlockedIncrement (&lock->guard.started) == 0)
 183         /* This thread is the first one to need this lock.  Initialize it.  */
 184         glwthread_timedrwlock_init (lock);
 185       else
 186         {
 187           /* Don't let lock->guard.started grow and wrap around.  */
 188           InterlockedDecrement (&lock->guard.started);
 189           /* Yield the CPU while waiting for another thread to finish
 190              initializing this lock.  */
 191           while (!lock->guard.done)
 192             Sleep (0);
 193         }
 194     }
 195   EnterCriticalSection (&lock->lock);
 196   /* Test whether only readers are currently running, and whether the runcount
 197      field will not overflow, and whether no writer is waiting.  The latter
 198      condition is because POSIX recommends that "write locks shall take
 199      precedence over read locks", to avoid "writer starvation".  */
 200   if (!(lock->runcount + 1 > 0 && lock->waiting_writers.count == 0))
 201     {
 202       /* This thread has to wait for a while.  Enqueue it among the
 203          waiting_readers.  */
 204       struct glwthread_waitqueue_element *elt =
 205         glwthread_waitqueue_add (&lock->waiting_readers);
 206       if (elt != NULL)
 207         {
 208           HANDLE event = elt->event;
 209           DWORD result;
 210           LeaveCriticalSection (&lock->lock);
 211           /* Wait until another thread signals this event.  */
 212           result = WaitForSingleObject (event, INFINITE);
 213           if (result == WAIT_FAILED || result == WAIT_TIMEOUT)
 214             abort ();
 215           CloseHandle (event);
 216           free (elt);
 217           /* The thread which signalled the event already did the bookkeeping:
 218              removed us from the waiting_readers, incremented lock->runcount.  */
 219           if (!(lock->runcount > 0))
 220             abort ();
 221           return 0;
 222         }
 223       else
 224         {
 225           /* Allocation failure.  Weird.  */
 226           do
 227             {
 228               LeaveCriticalSection (&lock->lock);
 229               Sleep (1);
 230               EnterCriticalSection (&lock->lock);
 231             }
 232           while (!(lock->runcount + 1 > 0));
 233         }
 234     }
 235   lock->runcount++;
 236   LeaveCriticalSection (&lock->lock);
 237   return 0;
 238 }
 239
 240 int
 241 glwthread_timedrwlock_wrlock (glwthread_timedrwlock_t *lock)
 242 {
 243   if (!lock->guard.done)
 244     {
 245       if (InterlockedIncrement (&lock->guard.started) == 0)
 246         /* This thread is the first one to need this lock.  Initialize it.  */
 247         glwthread_timedrwlock_init (lock);
 248       else
 249         {
 250           /* Don't let lock->guard.started grow and wrap around.  */
 251           InterlockedDecrement (&lock->guard.started);
 252           /* Yield the CPU while waiting for another thread to finish
 253              initializing this lock.  */
 254           while (!lock->guard.done)
 255             Sleep (0);
 256         }
 257     }
 258   EnterCriticalSection (&lock->lock);
 259   /* Test whether no readers or writers are currently running.  */
 260   if (!(lock->runcount == 0))
 261     {
 262       /* This thread has to wait for a while.  Enqueue it among the
 263          waiting_writers.  */
 264       struct glwthread_waitqueue_element *elt =
 265         glwthread_waitqueue_add (&lock->waiting_writers);
 266       if (elt != NULL)
 267         {
 268           HANDLE event = elt->event;
 269           DWORD result;
 270           LeaveCriticalSection (&lock->lock);
 271           /* Wait until another thread signals this event.  */
 272           result = WaitForSingleObject (event, INFINITE);
 273           if (result == WAIT_FAILED || result == WAIT_TIMEOUT)
 274             abort ();
 275           CloseHandle (event);
 276           free (elt);
 277           /* The thread which signalled the event already did the bookkeeping:
 278              removed us from the waiting_writers, set lock->runcount = -1.  */
 279           if (!(lock->runcount == -1))
 280             abort ();
 281           return 0;
 282         }
 283       else
 284         {
 285           /* Allocation failure.  Weird.  */
 286           do
 287             {
 288               LeaveCriticalSection (&lock->lock);
 289               Sleep (1);
 290               EnterCriticalSection (&lock->lock);
 291             }
 292           while (!(lock->runcount == 0));
 293         }
 294     }
 295   lock->runcount--; /* runcount becomes -1 */
 296   LeaveCriticalSection (&lock->lock);
 297   return 0;
 298 }
 299
 300 int
 301 glwthread_timedrwlock_tryrdlock (glwthread_timedrwlock_t *lock)
 302 {
 303   if (!lock->guard.done)
 304     {
 305       if (InterlockedIncrement (&lock->guard.started) == 0)
 306         /* This thread is the first one to need this lock.  Initialize it.  */
 307         glwthread_timedrwlock_init (lock);
 308       else
 309         {
 310           /* Don't let lock->guard.started grow and wrap around.  */
 311           InterlockedDecrement (&lock->guard.started);
 312           /* Yield the CPU while waiting for another thread to finish
 313              initializing this lock.  */
 314           while (!lock->guard.done)
 315             Sleep (0);
 316         }
 317     }
 318   /* It's OK to wait for this critical section, because it is never taken for a
 319      long time.  */
 320   EnterCriticalSection (&lock->lock);
 321   /* Test whether only readers are currently running, and whether the runcount
 322      field will not overflow, and whether no writer is waiting.  The latter
 323      condition is because POSIX recommends that "write locks shall take
 324      precedence over read locks", to avoid "writer starvation".  */
 325   if (!(lock->runcount + 1 > 0 && lock->waiting_writers.count == 0))
 326     {
 327       /* This thread would have to wait for a while.  Return instead.  */
 328       LeaveCriticalSection (&lock->lock);
 329       return EBUSY;
 330     }
 331   lock->runcount++;
 332   LeaveCriticalSection (&lock->lock);
 333   return 0;
 334 }
 335
 336 int
 337 glwthread_timedrwlock_trywrlock (glwthread_timedrwlock_t *lock)
 338 {
 339   if (!lock->guard.done)
 340     {
 341       if (InterlockedIncrement (&lock->guard.started) == 0)
 342         /* This thread is the first one to need this lock.  Initialize it.  */
 343         glwthread_timedrwlock_init (lock);
 344       else
 345         {
 346           /* Don't let lock->guard.started grow and wrap around.  */
 347           InterlockedDecrement (&lock->guard.started);
 348           /* Yield the CPU while waiting for another thread to finish
 349              initializing this lock.  */
 350           while (!lock->guard.done)
 351             Sleep (0);
 352         }
 353     }
 354   /* It's OK to wait for this critical section, because it is never taken for a
 355      long time.  */
 356   EnterCriticalSection (&lock->lock);
 357   /* Test whether no readers or writers are currently running.  */
 358   if (!(lock->runcount == 0))
 359     {
 360       /* This thread would have to wait for a while.  Return instead.  */
 361       LeaveCriticalSection (&lock->lock);
 362       return EBUSY;
 363     }
 364   lock->runcount--; /* runcount becomes -1 */
 365   LeaveCriticalSection (&lock->lock);
 366   return 0;
 367 }
 368
 369 int
 370 glwthread_timedrwlock_timedrdlock (glwthread_timedrwlock_t *lock,
 371                                    const struct timespec *abstime)
 372 {
 373   if (!lock->guard.done)
 374     {
 375       if (InterlockedIncrement (&lock->guard.started) == 0)
 376         /* This thread is the first one to need this lock.  Initialize it.  */
 377         glwthread_timedrwlock_init (lock);
 378       else
 379         {
 380           /* Don't let lock->guard.started grow and wrap around.  */
 381           InterlockedDecrement (&lock->guard.started);
 382           /* Yield the CPU while waiting for another thread to finish
 383              initializing this lock.  */
 384           while (!lock->guard.done)
 385             Sleep (0);
 386         }
 387     }
 388   EnterCriticalSection (&lock->lock);
 389   /* Test whether only readers are currently running, and whether the runcount
 390      field will not overflow, and whether no writer is waiting.  The latter
 391      condition is because POSIX recommends that "write locks shall take
 392      precedence over read locks", to avoid "writer starvation".  */
 393   if (!(lock->runcount + 1 > 0 && lock->waiting_writers.count == 0))
 394     {
 395       /* This thread has to wait for a while.  Enqueue it among the
 396          waiting_readers.  */
 397       struct glwthread_waitqueue_element *elt =
 398         glwthread_waitqueue_add (&lock->waiting_readers);
 399       if (elt != NULL)
 400         {
 401           HANDLE event = elt->event;
 402           struct timeval currtime;
 403           DWORD timeout;
 404           DWORD result;
 405           int retval;
 406
 407           LeaveCriticalSection (&lock->lock);
 408
 409           gettimeofday (&currtime, NULL);
 410
 411           /* Wait until another thread signals this event or until the
 412              abstime passes.  */
 413           if (currtime.tv_sec > abstime->tv_sec)
 414             timeout = 0;
 415           else
 416             {
 417               unsigned long seconds = abstime->tv_sec - currtime.tv_sec;
 418               timeout = seconds * 1000;
 419               if (timeout / 1000 != seconds) /* overflow? */
 420                 timeout = INFINITE;
 421               else
 422                 {
 423                   long milliseconds =
 424                     abstime->tv_nsec / 1000000 - currtime.tv_usec / 1000;
 425                   if (milliseconds >= 0)
 426                     {
 427                       timeout += milliseconds;
 428                       if (timeout < milliseconds) /* overflow? */
 429                         timeout = INFINITE;
 430                     }
 431                   else
 432                     {
 433                       if (timeout >= - milliseconds)
 434                         timeout -= (- milliseconds);
 435                       else
 436                         timeout = 0;
 437                     }
 438                 }
 439             }
 440           if (timeout != 0)
 441             {
 442               /* WaitForSingleObject
 443                  <https://docs.microsoft.com/en-us/windows/desktop/api/synchapi/nf-synchapi-waitforsingleobject> */
 444               result = WaitForSingleObject (event, timeout);
 445               if (result == WAIT_FAILED)
 446                 abort ();
 447               if (result != WAIT_TIMEOUT)
 448                 {
 449                   CloseHandle (event);
 450                   free (elt);
 451                   /* The thread which signalled the event already did the
 452                      bookkeeping: removed us from the waiting_readers,
 453                      incremented lock->runcount.  */
 454                   if (!(lock->runcount > 0))
 455                     abort ();
 456                   return 0;
 457                 }
 458             }
 459           EnterCriticalSection (&lock->lock);
 460           /* Remove ourselves from the waiting_readers.  */
 461           if (glwthread_waitqueue_remove (&lock->waiting_readers, elt))
 462             retval = ETIMEDOUT;
 463           else
 464             /* The event was signalled just now.  */
 465             retval = 0;
 466           LeaveCriticalSection (&lock->lock);
 467           CloseHandle (event);
 468           free (elt);
 469           if (retval == 0)
 470             /* Same assertion as above.  */
 471             if (!(lock->runcount > 0))
 472               abort ();
 473           return retval;
 474         }
 475       else
 476         {
 477           /* Allocation failure.  Weird.  */
 478           do
 479             {
 480               LeaveCriticalSection (&lock->lock);
 481               Sleep (1);
 482               EnterCriticalSection (&lock->lock);
 483             }
 484           while (!(lock->runcount + 1 > 0));
 485         }
 486     }
 487   lock->runcount++;
 488   LeaveCriticalSection (&lock->lock);
 489   return 0;
 490 }
 491
 492 int
 493 glwthread_timedrwlock_timedwrlock (glwthread_timedrwlock_t *lock,
 494                                    const struct timespec *abstime)
 495 {
 496   if (!lock->guard.done)
 497     {
 498       if (InterlockedIncrement (&lock->guard.started) == 0)
 499         /* This thread is the first one to need this lock.  Initialize it.  */
 500         glwthread_timedrwlock_init (lock);
 501       else
 502         {
 503           /* Don't let lock->guard.started grow and wrap around.  */
 504           InterlockedDecrement (&lock->guard.started);
 505           /* Yield the CPU while waiting for another thread to finish
 506              initializing this lock.  */
 507           while (!lock->guard.done)
 508             Sleep (0);
 509         }
 510     }
 511   EnterCriticalSection (&lock->lock);
 512   /* Test whether no readers or writers are currently running.  */
 513   if (!(lock->runcount == 0))
 514     {
 515       /* This thread has to wait for a while.  Enqueue it among the
 516          waiting_writers.  */
 517       struct glwthread_waitqueue_element *elt =
 518         glwthread_waitqueue_add (&lock->waiting_writers);
 519       if (elt != NULL)
 520         {
 521           HANDLE event = elt->event;
 522           struct timeval currtime;
 523           DWORD timeout;
 524           DWORD result;
 525           int retval;
 526
 527           LeaveCriticalSection (&lock->lock);
 528
 529           gettimeofday (&currtime, NULL);
 530
 531           /* Wait until another thread signals this event or until the
 532              abstime passes.  */
 533           if (currtime.tv_sec > abstime->tv_sec)
 534             timeout = 0;
 535           else
 536             {
 537               unsigned long seconds = abstime->tv_sec - currtime.tv_sec;
 538               timeout = seconds * 1000;
 539               if (timeout / 1000 != seconds) /* overflow? */
 540                 timeout = INFINITE;
 541               else
 542                 {
 543                   long milliseconds =
 544                     abstime->tv_nsec / 1000000 - currtime.tv_usec / 1000;
 545                   if (milliseconds >= 0)
 546                     {
 547                       timeout += milliseconds;
 548                       if (timeout < milliseconds) /* overflow? */
 549                         timeout = INFINITE;
 550                     }
 551                   else
 552                     {
 553                       if (timeout >= - milliseconds)
 554                         timeout -= (- milliseconds);
 555                       else
 556                         timeout = 0;
 557                     }
 558                 }
 559             }
 560           if (timeout != 0)
 561             {
 562               /* WaitForSingleObject
 563                  <https://docs.microsoft.com/en-us/windows/desktop/api/synchapi/nf-synchapi-waitforsingleobject> */
 564               result = WaitForSingleObject (event, timeout);
 565               if (result == WAIT_FAILED)
 566                 abort ();
 567               if (result != WAIT_TIMEOUT)
 568                 {
 569                   CloseHandle (event);
 570                   free (elt);
 571                   /* The thread which signalled the event already did the
 572                      bookkeeping: removed us from the waiting_writers, set
 573                      lock->runcount = -1.  */
 574                   if (!(lock->runcount == -1))
 575                     abort ();
 576                   return 0;
 577                 }
 578             }
 579           EnterCriticalSection (&lock->lock);
 580           /* Remove ourselves from the waiting_writers.  */
 581           if (glwthread_waitqueue_remove (&lock->waiting_writers, elt))
 582             retval = ETIMEDOUT;
 583           else
 584             /* The event was signalled just now.  */
 585             retval = 0;
 586           LeaveCriticalSection (&lock->lock);
 587           CloseHandle (event);
 588           free (elt);
 589           if (retval == 0)
 590             /* Same assertion as above.  */
 591             if (!(lock->runcount == -1))
 592               abort ();
 593           return retval;
 594         }
 595       else
 596         {
 597           /* Allocation failure.  Weird.  */
 598           do
 599             {
 600               LeaveCriticalSection (&lock->lock);
 601               Sleep (1);
 602               EnterCriticalSection (&lock->lock);
 603             }
 604           while (!(lock->runcount == 0));
 605         }
 606     }
 607   lock->runcount--; /* runcount becomes -1 */
 608   LeaveCriticalSection (&lock->lock);
 609   return 0;
 610 }
 611
 612 int
 613 glwthread_timedrwlock_unlock (glwthread_timedrwlock_t *lock)
 614 {
 615   if (!lock->guard.done)
 616     return EINVAL;
 617   EnterCriticalSection (&lock->lock);
 618   if (lock->runcount < 0)
 619     {
 620       /* Drop a writer lock.  */
 621       if (!(lock->runcount == -1))
 622         abort ();
 623       lock->runcount = 0;
 624     }
 625   else
 626     {
 627       /* Drop a reader lock.  */
 628       if (!(lock->runcount > 0))
 629         {
 630           LeaveCriticalSection (&lock->lock);
 631           return EPERM;
 632         }
 633       lock->runcount--;
 634     }
 635   if (lock->runcount == 0)
 636     {
 637       /* POSIX recommends that "write locks shall take precedence over read
 638          locks", to avoid "writer starvation".  */
 639       if (lock->waiting_writers.count > 0)
 640         {
 641           /* Wake up one of the waiting writers.  */
 642           lock->runcount--;
 643           glwthread_waitqueue_notify_first (&lock->waiting_writers);
 644         }
 645       else
 646         {
 647           /* Wake up all waiting readers.  */
 648           lock->runcount += lock->waiting_readers.count;
 649           glwthread_waitqueue_notify_all (&lock->waiting_readers);
 650         }
 651     }
 652   LeaveCriticalSection (&lock->lock);
 653   return 0;
 654 }
 655
 656 int
 657 glwthread_timedrwlock_destroy (glwthread_timedrwlock_t *lock)
 658 {
 659   if (!lock->guard.done)
 660     return EINVAL;
 661   if (lock->runcount != 0)
 662     return EBUSY;
 663   DeleteCriticalSection (&lock->lock);
 664   lock->guard.done = 0;
 665   return 0;
 666 }