lib/windows-timedrwlock.c

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