mono/metadata/monitor.c

   1 /*
   2  * monitor.c:  Monitor locking functions
   3  *
   4  * Author:
   5  *      Dick Porter (dick@ximian.com)
   6  *
   7  * (C) 2003 Ximian, Inc.
   8  */
   9
  10 #include <config.h>
  11 #include <glib.h>
  12
  13 #include <mono/metadata/monitor.h>
  14 #include <mono/metadata/threads-types.h>
  15 #include <mono/metadata/exception.h>
  16 #include <mono/metadata/threads.h>
  17 #include <mono/io-layer/io-layer.h>
  18 #include <mono/metadata/object-internals.h>
  19 #include <mono/metadata/gc-internal.h>
  20
  21 /*#define LOCK_DEBUG(a) do { a; } while (0)*/
  22 #define LOCK_DEBUG(a)
  23
  24 /*
  25  * The monitor implementation here is based on
  26  * http://www.usenix.org/events/jvm01/full_papers/dice/dice.pdf and
  27  * http://www.research.ibm.com/people/d/dfb/papers/Bacon98Thin.ps
  28  *
  29  * The Dice paper describes a technique for saving lock record space
  30  * by returning records to a free list when they become unused.  That
  31  * sounds like unnecessary complexity to me, though if it becomes
  32  * clear that unused lock records are taking up lots of space or we
  33  * need to shave more time off by avoiding a malloc then we can always
  34  * implement the free list idea later.  The timeout parameter to
  35  * try_enter voids some of the assumptions about the reference count
  36  * field in Dice's implementation too.  In his version, the thread
  37  * attempting to lock a contended object will block until it succeeds,
  38  * so the reference count will never be decremented while an object is
  39  * locked.
  40  *
  41  * Bacon's thin locks have a fast path that doesn't need a lock record
  42  * for the common case of locking an unlocked or shallow-nested
  43  * object, but the technique relies on encoding the thread ID in 15
  44  * bits (to avoid too much per-object space overhead.)  Unfortunately
  45  * I don't think it's possible to reliably encode a pthread_t into 15
  46  * bits. (The JVM implementation used seems to have a 15-bit
  47  * per-thread identifier available.)
  48  *
  49  * This implementation then combines Dice's basic lock model with
  50  * Bacon's simplification of keeping a lock record for the lifetime of
  51  * an object.
  52  */
  53
  54 struct _MonoThreadsSync
  55 {
  56         gsize owner;                    /* thread ID */
  57         guint32 nest;
  58         volatile guint32 entry_count;
  59         HANDLE entry_sem;
  60         GSList *wait_list;
  61         void *data;
  62 };
  63
  64 typedef struct _MonitorArray MonitorArray;
  65
  66 struct _MonitorArray {
  67         MonitorArray *next;
  68         int num_monitors;
  69         MonoThreadsSync monitors [MONO_ZERO_LEN_ARRAY];
  70 };
  71
  72 static CRITICAL_SECTION monitor_mutex;
  73 static MonoThreadsSync *monitor_freelist;
  74 static MonitorArray *monitor_allocated;
  75 static int array_size = 16;
  76
  77 void
  78 mono_monitor_init (void)
  79 {
  80         InitializeCriticalSection (&monitor_mutex);
  81 }
  82
  83 /* LOCKING: this is called with monitor_mutex held */
  84 static void
  85 mon_finalize (MonoThreadsSync *mon)
  86 {
  87         LOCK_DEBUG (g_message (G_GNUC_PRETTY_FUNCTION ": Finalizing sync %p", mon));
  88
  89         if (mon->entry_sem != NULL) {
  90                 CloseHandle (mon->entry_sem);
  91                 mon->entry_sem = NULL;
  92         }
  93         /* If this isn't empty then something is seriously broken - it
  94          * means a thread is still waiting on the object that owned
  95          * this lock, but the object has been finalized.
  96          */
  97         g_assert (mon->wait_list == NULL);
  98
  99         mon->entry_count = 0;
 100         /* owner and nest are set in mon_new, no need to zero them out */
 101
 102         mon->data = monitor_freelist;
 103         monitor_freelist = mon;
 104 }
 105
 106 /* LOCKING: this is called with monitor_mutex held */
 107 static MonoThreadsSync *
 108 mon_new (gsize id)
 109 {
 110         MonoThreadsSync *new;
 111
 112         if (!monitor_freelist) {
 113                 MonitorArray *marray;
 114                 int i;
 115                 /* see if any sync block has been collected */
 116                 new = NULL;
 117                 for (marray = monitor_allocated; marray; marray = marray->next) {
 118                         for (i = 0; i < marray->num_monitors; ++i) {
 119                                 if (marray->monitors [i].data == NULL) {
 120                                         new = &marray->monitors [i];
 121                                         new->data = monitor_freelist;
 122                                         monitor_freelist = new;
 123                                 }
 124                         }
 125                         /* small perf tweak to avoid scanning all the blocks */
 126                         if (new)
 127                                 break;
 128                 }
 129                 /* need to allocate a new array of monitors */
 130                 if (!monitor_freelist) {
 131                         MonitorArray *last;
 132                         LOCK_DEBUG (g_message (G_GNUC_PRETTY_FUNCTION ": allocating more monitors: %d", array_size));
 133                         marray = g_malloc0 (sizeof (MonoArray) + array_size * sizeof (MonoThreadsSync));
 134                         marray->num_monitors = array_size;
 135                         array_size *= 2;
 136                         /* link into the freelist */
 137                         for (i = 0; i < marray->num_monitors - 1; ++i) {
 138                                 marray->monitors [i].data = &marray->monitors [i + 1];
 139                         }
 140                         marray->monitors [i].data = NULL; /* the last one */
 141                         monitor_freelist = &marray->monitors [0];
 142                         /* we happend the marray instead of prepending so that
 143                          * the collecting loop above will need to scan smaller arrays first
 144                          */
 145                         if (!monitor_allocated) {
 146                                 monitor_allocated = marray;
 147                         } else {
 148                                 last = monitor_allocated;
 149                                 while (last->next)
 150                                         last = last->next;
 151                                 last->next = marray;
 152                         }
 153                 }
 154         }
 155
 156         new = monitor_freelist;
 157         monitor_freelist = new->data;
 158
 159         new->owner = id;
 160         new->nest = 1;
 161
 162         return new;
 163 }
 164
 165 /* If allow_interruption==TRUE, the method will be interrumped if abort or suspend
 166  * is requested. In this case it returns -1.
 167  */
 168 static gint32
 169 mono_monitor_try_enter_internal (MonoObject *obj, guint32 ms, gboolean allow_interruption)
 170 {
 171         MonoThreadsSync *mon;
 172         gsize id = GetCurrentThreadId ();
 173         HANDLE sem;
 174         guint32 then = 0, now, delta;
 175         guint32 waitms;
 176         guint32 ret;
 177
 178         LOCK_DEBUG (g_message(G_GNUC_PRETTY_FUNCTION
 179                   ": (%d) Trying to lock object %p (%d ms)", id, obj, ms));
 180
 181 retry:
 182         mon = obj->synchronisation;
 183
 184         /* If the object has never been locked... */
 185         if (mon == NULL) {
 186                 EnterCriticalSection (&monitor_mutex);
 187                 mon = mon_new (id);
 188                 if (InterlockedCompareExchangePointer ((gpointer*)&obj->synchronisation, mon, NULL) == NULL) {
 189                         mono_gc_weak_link_add (&mon->data, obj);
 190                         LeaveCriticalSection (&monitor_mutex);
 191                         /* Successfully locked */
 192                         return 1;
 193                 } else {
 194                         mon_finalize (mon);
 195                         LeaveCriticalSection (&monitor_mutex);
 196                         goto retry;
 197                 }
 198         }
 199
 200         /* If the object is currently locked by this thread... */
 201         if (mon->owner == id) {
 202                 mon->nest++;
 203                 return 1;
 204         }
 205
 206         /* If the object has previously been locked but isn't now... */
 207
 208         /* This case differs from Dice's case 3 because we don't
 209          * deflate locks or cache unused lock records
 210          */
 211         if (mon->owner == 0) {
 212                 /* Try to install our ID in the owner field, nest
 213                  * should have been left at 1 by the previous unlock
 214                  * operation
 215                  */
 216                 if (InterlockedCompareExchangePointer ((gpointer *)&mon->owner, (gpointer)id, 0) == 0) {
 217                         /* Success */
 218                         g_assert (mon->nest == 1);
 219                         return 1;
 220                 } else {
 221                         /* Trumped again! */
 222                         goto retry;
 223                 }
 224         }
 225
 226         /* The object must be locked by someone else... */
 227
 228         /* If ms is 0 we don't block, but just fail straight away */
 229         if (ms == 0) {
 230                 LOCK_DEBUG (g_message (G_GNUC_PRETTY_FUNCTION ": (%d) timed out, returning FALSE", id));
 231                 return 0;
 232         }
 233
 234         /* The slow path begins here.  We need to make sure theres a
 235          * semaphore handle (creating it if necessary), and block on
 236          * it
 237          */
 238         if (mon->entry_sem == NULL) {
 239                 /* Create the semaphore */
 240                 sem = CreateSemaphore (NULL, 0, 0x7fffffff, NULL);
 241                 if (InterlockedCompareExchangePointer ((gpointer*)&mon->entry_sem, sem, NULL) != NULL) {
 242                         /* Someone else just put a handle here */
 243                         CloseHandle (sem);
 244                 }
 245         }
 246
 247         /* If we need to time out, record a timestamp and adjust ms,
 248          * because WaitForSingleObject doesn't tell us how long it
 249          * waited for.
 250          *
 251          * Don't block forever here, because theres a chance the owner
 252          * thread released the lock while we were creating the
 253          * semaphore: we would not get the wakeup.  Using the event
 254          * handle technique from pulse/wait would involve locking the
 255          * lock struct and therefore slowing down the fast path.
 256          */
 257         if (ms != INFINITE) {
 258                 then = GetTickCount ();
 259                 if (ms < 100) {
 260                         waitms = ms;
 261                 } else {
 262                         waitms = 100;
 263                 }
 264         } else {
 265                 waitms = 100;
 266         }
 267
 268         InterlockedIncrement (&mon->entry_count);
 269         ret = WaitForSingleObjectEx (mon->entry_sem, waitms, allow_interruption);
 270         InterlockedDecrement (&mon->entry_count);
 271
 272         if (ms != INFINITE) {
 273                 now = GetTickCount ();
 274
 275                 if (now < then) {
 276                         /* The counter must have wrapped around */
 277                         LOCK_DEBUG (g_message (G_GNUC_PRETTY_FUNCTION
 278                                    ": wrapped around! now=0x%x then=0x%x", now, then));
 279
 280                         now += (0xffffffff - then);
 281                         then = 0;
 282
 283                         LOCK_DEBUG (g_message (G_GNUC_PRETTY_FUNCTION ": wrap rejig: now=0x%x then=0x%x delta=0x%x", now, then, now-then));
 284                 }
 285
 286                 delta = now - then;
 287                 if (delta >= ms) {
 288                         ms = 0;
 289                 } else {
 290                         ms -= delta;
 291                 }
 292
 293                 if ((ret == WAIT_TIMEOUT || (ret == WAIT_IO_COMPLETION && !allow_interruption)) && ms > 0) {
 294                         /* More time left */
 295                         goto retry;
 296                 }
 297         } else {
 298                 if (ret == WAIT_TIMEOUT || (ret == WAIT_IO_COMPLETION && !allow_interruption)) {
 299                         /* Infinite wait, so just try again */
 300                         goto retry;
 301                 }
 302         }
 303
 304         if (ret == WAIT_OBJECT_0) {
 305                 /* retry from the top */
 306                 goto retry;
 307         }
 308
 309         /* We must have timed out */
 310         LOCK_DEBUG (g_message (G_GNUC_PRETTY_FUNCTION ": (%d) timed out waiting, returning FALSE", id));
 311
 312         if (ret == WAIT_IO_COMPLETION)
 313                 return -1;
 314         else
 315                 return 0;
 316 }
 317
 318 gboolean
 319 mono_monitor_enter (MonoObject *obj)
 320 {
 321         return mono_monitor_try_enter_internal (obj, INFINITE, FALSE) == 1;
 322 }
 323
 324 gboolean
 325 mono_monitor_try_enter (MonoObject *obj, guint32 ms)
 326 {
 327         return mono_monitor_try_enter_internal (obj, ms, FALSE) == 1;
 328 }
 329
 330 void
 331 mono_monitor_exit (MonoObject *obj)
 332 {
 333         MonoThreadsSync *mon;
 334         guint32 nest;
 335
 336         LOCK_DEBUG (g_message (G_GNUC_PRETTY_FUNCTION ": (%d) Unlocking %p", GetCurrentThreadId (), obj));
 337
 338         mon = obj->synchronisation;
 339
 340         if (mon == NULL) {
 341                 /* No one ever used Enter. Just ignore the Exit request as MS does */
 342                 return;
 343         }
 344         if (mon->owner != GetCurrentThreadId ()) {
 345                 return;
 346         }
 347
 348         nest = mon->nest - 1;
 349         if (nest == 0) {
 350                 LOCK_DEBUG (g_message (G_GNUC_PRETTY_FUNCTION
 351                           ": (%d) Object %p is now unlocked", GetCurrentThreadId (), obj));
 352
 353                 /* object is now unlocked, leave nest==1 so we don't
 354                  * need to set it when the lock is reacquired
 355                  */
 356                 mon->owner = 0;
 357
 358                 /* Do the wakeup stuff.  It's possible that the last
 359                  * blocking thread gave up waiting just before we
 360                  * release the semaphore resulting in a futile wakeup
 361                  * next time there's contention for this object, but
 362                  * it means we don't have to waste time locking the
 363                  * struct.
 364                  */
 365                 if (mon->entry_count > 0) {
 366                         ReleaseSemaphore (mon->entry_sem, 1, NULL);
 367                 }
 368         } else {
 369                 LOCK_DEBUG (g_message (G_GNUC_PRETTY_FUNCTION
 370                           ": (%d) Object %p is now locked %d times", GetCurrentThreadId (), obj, nest));
 371                 mon->nest = nest;
 372         }
 373 }
 374
 375 gboolean
 376 ves_icall_System_Threading_Monitor_Monitor_try_enter (MonoObject *obj, guint32 ms)
 377 {
 378         gint32 res;
 379
 380         do {
 381                 res = mono_monitor_try_enter_internal (obj, ms, TRUE);
 382                 if (res == -1)
 383                         mono_thread_interruption_checkpoint ();
 384         } while (res == -1);
 385
 386         return res == 1;
 387 }
 388
 389 void
 390 ves_icall_System_Threading_Monitor_Monitor_exit (MonoObject *obj)
 391 {
 392         mono_monitor_exit (obj);
 393 }
 394
 395 gboolean
 396 ves_icall_System_Threading_Monitor_Monitor_test_owner (MonoObject *obj)
 397 {
 398         MonoThreadsSync *mon;
 399
 400         LOCK_DEBUG (g_message (G_GNUC_PRETTY_FUNCTION
 401                   ": Testing if %p is owned by thread %d", obj, GetCurrentThreadId()));
 402
 403         mon = obj->synchronisation;
 404         if (mon == NULL) {
 405                 return FALSE;
 406         }
 407
 408         if(mon->owner==GetCurrentThreadId ()) {
 409                 return(TRUE);
 410         }
 411
 412         return(FALSE);
 413 }
 414
 415 gboolean
 416 ves_icall_System_Threading_Monitor_Monitor_test_synchronised (MonoObject *obj)
 417 {
 418         MonoThreadsSync *mon;
 419
 420         LOCK_DEBUG (g_message(G_GNUC_PRETTY_FUNCTION
 421                   ": (%d) Testing if %p is owned by any thread", GetCurrentThreadId (), obj));
 422
 423         mon = obj->synchronisation;
 424         if (mon == NULL) {
 425                 return FALSE;
 426         }
 427
 428         if (mon->owner != 0) {
 429                 return TRUE;
 430         }
 431
 432         return FALSE;
 433 }
 434
 435 /* All wait list manipulation in the pulse, pulseall and wait
 436  * functions happens while the monitor lock is held, so we don't need
 437  * any extra struct locking
 438  */
 439
 440 void
 441 ves_icall_System_Threading_Monitor_Monitor_pulse (MonoObject *obj)
 442 {
 443         MonoThreadsSync *mon;
 444
 445         LOCK_DEBUG (g_message (G_GNUC_PRETTY_FUNCTION ": (%d) Pulsing %p",
 446                 GetCurrentThreadId (), obj));
 447
 448         mon = obj->synchronisation;
 449         if (mon == NULL) {
 450                 mono_raise_exception (mono_get_exception_synchronization_lock ("Not locked"));
 451                 return;
 452         }
 453         if (mon->owner != GetCurrentThreadId ()) {
 454                 mono_raise_exception (mono_get_exception_synchronization_lock ("Not locked by this thread"));
 455                 return;
 456         }
 457
 458         LOCK_DEBUG (g_message (G_GNUC_PRETTY_FUNCTION ": (%d) %d threads waiting",
 459                   GetCurrentThreadId (), g_slist_length (mon->wait_list)));
 460
 461         if (mon->wait_list != NULL) {
 462                 LOCK_DEBUG (g_message (G_GNUC_PRETTY_FUNCTION
 463                           ": (%d) signalling and dequeuing handle %p",
 464                           GetCurrentThreadId (), mon->wait_list->data));
 465
 466                 SetEvent (mon->wait_list->data);
 467                 mon->wait_list = g_slist_remove (mon->wait_list, mon->wait_list->data);
 468         }
 469 }
 470
 471 void
 472 ves_icall_System_Threading_Monitor_Monitor_pulse_all (MonoObject *obj)
 473 {
 474         MonoThreadsSync *mon;
 475
 476         LOCK_DEBUG (g_message(G_GNUC_PRETTY_FUNCTION ": (%d) Pulsing all %p",
 477                   GetCurrentThreadId (), obj));
 478
 479         mon = obj->synchronisation;
 480         if (mon == NULL) {
 481                 mono_raise_exception (mono_get_exception_synchronization_lock ("Not locked"));
 482                 return;
 483         }
 484         if (mon->owner != GetCurrentThreadId ()) {
 485                 mono_raise_exception (mono_get_exception_synchronization_lock ("Not locked by this thread"));
 486                 return;
 487         }
 488
 489         LOCK_DEBUG (g_message (G_GNUC_PRETTY_FUNCTION ": (%d) %d threads waiting",
 490                   GetCurrentThreadId (), g_slist_length (mon->wait_list)));
 491
 492         while (mon->wait_list != NULL) {
 493                 LOCK_DEBUG (g_message (G_GNUC_PRETTY_FUNCTION
 494                           ": (%d) signalling and dequeuing handle %p",
 495                           GetCurrentThreadId (), mon->wait_list->data));
 496
 497                 SetEvent (mon->wait_list->data);
 498                 mon->wait_list = g_slist_remove (mon->wait_list, mon->wait_list->data);
 499         }
 500 }
 501
 502 gboolean
 503 ves_icall_System_Threading_Monitor_Monitor_wait (MonoObject *obj, guint32 ms)
 504 {
 505         MonoThreadsSync *mon;
 506         HANDLE event;
 507         guint32 nest;
 508         guint32 ret;
 509         gboolean success = FALSE;
 510         gint32 regain;
 511         MonoThread *thread = mono_thread_current ();
 512
 513         LOCK_DEBUG (g_message (G_GNUC_PRETTY_FUNCTION
 514                   ": (%d) Trying to wait for %p with timeout %dms",
 515                   GetCurrentThreadId (), obj, ms));
 516
 517         mon = obj->synchronisation;
 518         if (mon == NULL) {
 519                 mono_raise_exception (mono_get_exception_synchronization_lock ("Not locked"));
 520                 return FALSE;
 521         }
 522         if (mon->owner != GetCurrentThreadId ()) {
 523                 mono_raise_exception (mono_get_exception_synchronization_lock ("Not locked by this thread"));
 524                 return FALSE;
 525         }
 526
 527         event = CreateEvent (NULL, FALSE, FALSE, NULL);
 528         if (event == NULL) {
 529                 mono_raise_exception (mono_get_exception_synchronization_lock ("Failed to set up wait event"));
 530                 return FALSE;
 531         }
 532
 533         LOCK_DEBUG (g_message (G_GNUC_PRETTY_FUNCTION ": (%d) queuing handle %p",
 534                   GetCurrentThreadId (), event));
 535
 536         mono_monitor_enter (thread->synch_lock);
 537         thread->state |= ThreadState_WaitSleepJoin;
 538         mono_monitor_exit (thread->synch_lock);
 539
 540         mon->wait_list = g_slist_append (mon->wait_list, event);
 541
 542         /* Save the nest count, and release the lock */
 543         nest = mon->nest;
 544         mon->nest = 1;
 545         mono_monitor_exit (obj);
 546
 547         LOCK_DEBUG (g_message (G_GNUC_PRETTY_FUNCTION ": (%d) Unlocked %p lock %p",
 548                   GetCurrentThreadId (), obj, mon));
 549
 550         /* There's no race between unlocking mon and waiting for the
 551          * event, because auto reset events are sticky, and this event
 552          * is private to this thread.  Therefore even if the event was
 553          * signalled before we wait, we still succeed.
 554          */
 555         ret = WaitForSingleObjectEx (event, ms, TRUE);
 556
 557         /* Reset the thread state fairly early, so we don't have to worry
 558          * about the monitor error checking
 559          */
 560         mono_monitor_enter (thread->synch_lock);
 561         thread->state &= ~ThreadState_WaitSleepJoin;
 562         mono_monitor_exit (thread->synch_lock);
 563
 564         if (mono_thread_interruption_requested ()) {
 565                 CloseHandle (event);
 566                 return FALSE;
 567         }
 568
 569         /* Regain the lock with the previous nest count */
 570         do {
 571                 regain = mono_monitor_try_enter_internal (obj, INFINITE, TRUE);
 572                 if (regain == -1)
 573                         mono_thread_interruption_checkpoint ();
 574         } while (regain == -1);
 575
 576         if (regain == 0) {
 577                 /* Something went wrong, so throw a
 578                  * SynchronizationLockException
 579                  */
 580                 CloseHandle (event);
 581                 mono_raise_exception (mono_get_exception_synchronization_lock ("Failed to regain lock"));
 582                 return FALSE;
 583         }
 584
 585         mon->nest = nest;
 586
 587         LOCK_DEBUG (g_message (G_GNUC_PRETTY_FUNCTION ": (%d) Regained %p lock %p",
 588                   GetCurrentThreadId (), obj, mon));
 589
 590         if (ret == WAIT_TIMEOUT) {
 591                 /* Poll the event again, just in case it was signalled
 592                  * while we were trying to regain the monitor lock
 593                  */
 594                 ret = WaitForSingleObjectEx (event, 0, FALSE);
 595         }
 596
 597         /* Pulse will have popped our event from the queue if it signalled
 598          * us, so we only do it here if the wait timed out.
 599          *
 600          * This avoids a race condition where the thread holding the
 601          * lock can Pulse several times before the WaitForSingleObject
 602          * returns.  If we popped the queue here then this event might
 603          * be signalled more than once, thereby starving another
 604          * thread.
 605          */
 606
 607         if (ret == WAIT_OBJECT_0) {
 608                 LOCK_DEBUG (g_message (G_GNUC_PRETTY_FUNCTION ": (%d) Success",
 609                           GetCurrentThreadId ()));
 610                 success = TRUE;
 611         } else {
 612                 LOCK_DEBUG (g_message (G_GNUC_PRETTY_FUNCTION ": (%d) Wait failed, dequeuing handle %p",
 613                           GetCurrentThreadId (), event));
 614                 /* No pulse, so we have to remove ourself from the
 615                  * wait queue
 616                  */
 617                 mon->wait_list = g_slist_remove (mon->wait_list, event);
 618         }
 619         CloseHandle (event);
 620
 621         return success;
 622 }
 623