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