src/threads/lock.cpp

   1 /* src/threads/lock.cpp - lock implementation
   2
   3    Copyright (C) 1996-2005, 2006, 2007, 2008, 2010
   4    CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
   5
   6    This file is part of CACAO.
   7
   8    This program is free software; you can redistribute it and/or
   9    modify it under the terms of the GNU General Public License as
  10    published by the Free Software Foundation; either version 2, or (at
  11    your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful, but
  14    WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16    General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  21    02110-1301, USA.
  22
  23 */
  24
  25
  26 #include "config.h"
  27
  28 #include <assert.h>
  29 #include <stdint.h>
  30 #include <stdio.h>
  31 #include <stdlib.h>
  32 #include <sys/time.h>
  33
  34 #include "vm/types.h"
  35
  36 #include "mm/memory.hpp"
  37
  38 #include "native/llni.h"
  39
  40 #include "threads/atomic.hpp"
  41 #include "threads/lock.hpp"
  42 #include "threads/mutex.hpp"
  43 #include "threads/threadlist.hpp"
  44 #include "threads/thread.hpp"
  45
  46 #include "toolbox/list.hpp"
  47
  48 #include "vm/exceptions.hpp"
  49 #include "vm/finalizer.hpp"
  50 #include "vm/global.h"
  51 #include "vm/options.h"
  52 #include "vm/string.hpp"
  53 #include "vm/vm.hpp"
  54
  55 #if defined(ENABLE_STATISTICS)
  56 # include "vm/statistics.h"
  57 #endif
  58
  59 #if defined(ENABLE_VMLOG)
  60 #include <vmlog_cacao.h>
  61 #endif
  62
  63 #if defined(ENABLE_JVMTI)
  64 #include "native/jvmti/cacaodbg.h"
  65 #endif
  66
  67 #if defined(ENABLE_GC_BOEHM)
  68 # include "mm/boehm-gc/include/gc.h"
  69 #endif
  70
  71
  72 /* debug **********************************************************************/
  73
  74 #if !defined(NDEBUG)
  75 # define DEBUGLOCKS(format) \
  76     do { \
  77         if (opt_DebugLocks) { \
  78             log_println format; \
  79         } \
  80     } while (0)
  81 #else
  82 # define DEBUGLOCKS(format)
  83 #endif
  84
  85
  86 /******************************************************************************/
  87 /* MACROS                                                                     */
  88 /******************************************************************************/
  89
  90 /* number of lock records in the first pool allocated for a thread */
  91 #define LOCK_INITIAL_LOCK_RECORDS 8
  92
  93 #define LOCK_INITIAL_HASHTABLE_SIZE  1613  /* a prime in the middle between 1024 and 2048 */
  94
  95
  96 /******************************************************************************/
  97 /* MACROS FOR THIN/FAT LOCKS                                                  */
  98 /******************************************************************************/
  99
 100 /* We use a variant of the tasuki locks described in the paper
 101  *
 102  *     Tamiya Onodera, Kiyokuni Kawachiya
 103  *     A Study of Locking Objects with Bimodal Fields
 104  *     Proceedings of the ACM OOPSLA '99, pp. 223-237
 105  *     1999
 106  *
 107  * The underlying thin locks are a variant of the thin locks described in
 108  *
 109  *     Bacon, Konuru, Murthy, Serrano
 110  *     Thin Locks: Featherweight Synchronization for Java
 111  *         Proceedings of the ACM Conference on Programming Language Design and
 112  *         Implementation (Montreal, Canada), SIGPLAN Notices volume 33, number 6,
 113  *         June 1998
 114  *
 115  * In thin lock mode the lockword looks like this:
 116  *
 117  *     ,----------------------,-----------,---,
 118  *     |      thread ID       |   count   | 0 |
 119  *     `----------------------'-----------'---'
 120  *
 121  *     thread ID......the 'index' of the owning thread, or 0
 122  *     count..........number of times the lock has been entered minus 1
 123  *     0..............the shape bit is 0 in thin lock mode
 124  *
 125  * In fat lock mode it is basically a lock_record_t *:
 126  *
 127  *     ,----------------------------------,---,
 128  *     |    lock_record_t * (without LSB) | 1 |
 129  *     `----------------------------------'---'
 130  *
 131  *     1..............the shape bit is 1 in fat lock mode
 132  */
 133
 134 /* global variables ***********************************************************/
 135
 136 /* hashtable mapping objects to lock records */
 137 static lock_hashtable_t lock_hashtable;
 138
 139
 140 /******************************************************************************/
 141 /* PROTOTYPES                                                                 */
 142 /******************************************************************************/
 143
 144 static void lock_hashtable_init(void);
 145
 146 static inline uintptr_t* lock_lockword_get(java_handle_t* o);
 147 static void lock_record_enter(threadobject *t, lock_record_t *lr);
 148 static void lock_record_exit(threadobject *t, lock_record_t *lr);
 149 static bool lock_record_wait(threadobject *t, lock_record_t *lr, s8 millis, s4 nanos);
 150 static void lock_record_notify(threadobject *t, lock_record_t *lr, bool one);
 151
 152
 153 /*============================================================================*/
 154 /* INITIALIZATION OF DATA STRUCTURES                                          */
 155 /*============================================================================*/
 156
 157
 158 /* lock_init *******************************************************************
 159
 160    Initialize global data for locking.
 161
 162 *******************************************************************************/
 163
 164 void lock_init(void)
 165 {
 166         /* initialize lock hashtable */
 167
 168         lock_hashtable_init();
 169
 170 #if defined(ENABLE_VMLOG)
 171         vmlog_cacao_init_lock();
 172 #endif
 173 }
 174
 175
 176 /* lock_record_new *************************************************************
 177
 178    Allocate a lock record.
 179
 180 *******************************************************************************/
 181
 182 static lock_record_t *lock_record_new(void)
 183 {
 184         lock_record_t *lr;
 185
 186         /* allocate the data structure on the C heap */
 187
 188         lr = NEW(lock_record_t);
 189
 190 #if defined(ENABLE_STATISTICS)
 191         if (opt_stat)
 192                 size_lock_record += sizeof(lock_record_t);
 193 #endif
 194
 195         /* initialize the members */
 196
 197         lr->object  = NULL;
 198         lr->owner   = NULL;
 199         lr->count   = 0;
 200         lr->waiters = new List<threadobject*>();
 201
 202 #if defined(ENABLE_GC_CACAO)
 203         /* register the lock object as weak reference with the GC */
 204
 205         gc_weakreference_register(&(lr->object), GC_REFTYPE_LOCKRECORD);
 206 #endif
 207
 208         // Initialize the mutex.
 209         lr->mutex = new Mutex();
 210
 211         DEBUGLOCKS(("[lock_record_new   : lr=%p]", (void *) lr));
 212
 213         return lr;
 214 }
 215
 216
 217 /* lock_record_free ************************************************************
 218
 219    Free a lock record.
 220
 221    IN:
 222        lr....lock record to free
 223
 224 *******************************************************************************/
 225
 226 static void lock_record_free(lock_record_t *lr)
 227 {
 228         DEBUGLOCKS(("[lock_record_free  : lr=%p]", (void *) lr));
 229
 230         // Destroy the mutex.
 231         delete lr->mutex;
 232
 233 #if defined(ENABLE_GC_CACAO)
 234         /* unregister the lock object reference with the GC */
 235
 236         gc_weakreference_unregister(&(lr->object));
 237 #endif
 238
 239         // Free the waiters list.
 240         delete lr->waiters;
 241
 242         /* Free the data structure. */
 243
 244         FREE(lr, lock_record_t);
 245
 246 #if defined(ENABLE_STATISTICS)
 247         if (opt_stat)
 248                 size_lock_record -= sizeof(lock_record_t);
 249 #endif
 250 }
 251
 252
 253 /*============================================================================*/
 254 /* HASHTABLE MAPPING OBJECTS TO LOCK RECORDS                                  */
 255 /*============================================================================*/
 256
 257 /* lock_hashtable_init *********************************************************
 258
 259    Initialize the global hashtable mapping objects to lock records.
 260
 261 *******************************************************************************/
 262
 263 static void lock_hashtable_init(void)
 264 {
 265         lock_hashtable.mutex   = new Mutex();
 266
 267         lock_hashtable.size    = LOCK_INITIAL_HASHTABLE_SIZE;
 268         lock_hashtable.entries = 0;
 269         lock_hashtable.ptr     = MNEW(lock_record_t *, lock_hashtable.size);
 270
 271 #if defined(ENABLE_STATISTICS)
 272         if (opt_stat)
 273                 size_lock_hashtable += sizeof(lock_record_t *) * lock_hashtable.size;
 274 #endif
 275
 276         MZERO(lock_hashtable.ptr, lock_record_t *, lock_hashtable.size);
 277 }
 278
 279
 280 /* lock_hashtable_grow *********************************************************
 281
 282    Grow the lock record hashtable to about twice its current size and
 283    rehash the entries.
 284
 285 *******************************************************************************/
 286
 287 /* must be called with hashtable mutex locked */
 288 static void lock_hashtable_grow(void)
 289 {
 290         u4 oldsize;
 291         u4 newsize;
 292         lock_record_t **oldtable;
 293         lock_record_t **newtable;
 294         lock_record_t *lr;
 295         lock_record_t *next;
 296         u4 i;
 297         u4 h;
 298         u4 newslot;
 299
 300         /* allocate a new table */
 301
 302         oldsize = lock_hashtable.size;
 303         newsize = oldsize*2 + 1; /* XXX should use prime numbers */
 304
 305         DEBUGLOCKS(("growing lock hashtable to size %d", newsize));
 306
 307         oldtable = lock_hashtable.ptr;
 308         newtable = MNEW(lock_record_t *, newsize);
 309
 310 #if defined(ENABLE_STATISTICS)
 311         if (opt_stat)
 312                 size_lock_hashtable += sizeof(lock_record_t *) * newsize;
 313 #endif
 314
 315         MZERO(newtable, lock_record_t *, newsize);
 316
 317         /* rehash the entries */
 318
 319         for (i = 0; i < oldsize; i++) {
 320                 lr = oldtable[i];
 321                 while (lr) {
 322                         next = lr->hashlink;
 323
 324                         h = heap_hashcode(lr->object);
 325                         newslot = h % newsize;
 326
 327                         lr->hashlink = newtable[newslot];
 328                         newtable[newslot] = lr;
 329
 330                         lr = next;
 331                 }
 332         }
 333
 334         /* replace the old table */
 335
 336         lock_hashtable.ptr  = newtable;
 337         lock_hashtable.size = newsize;
 338
 339         MFREE(oldtable, lock_record_t *, oldsize);
 340
 341 #if defined(ENABLE_STATISTICS)
 342         if (opt_stat)
 343                 size_lock_hashtable -= sizeof(lock_record_t *) * oldsize;
 344 #endif
 345 }
 346
 347
 348 /* lock_hashtable_cleanup ******************************************************
 349
 350    Removes (and frees) lock records which have a cleared object reference
 351    from the hashtable. The locked object was reclaimed by the GC.
 352
 353 *******************************************************************************/
 354
 355 #if defined(ENABLE_GC_CACAO)
 356 void lock_hashtable_cleanup(void)
 357 {
 358         threadobject  *t;
 359         lock_record_t *lr;
 360         lock_record_t *prev;
 361         lock_record_t *next;
 362         int i;
 363
 364         t = THREADOBJECT;
 365
 366         /* lock the hashtable */
 367
 368         Mutex_lock(lock_hashtable.mutex);
 369
 370         /* search the hashtable for cleared references */
 371
 372         for (i = 0; i < lock_hashtable.size; i++) {
 373                 lr = lock_hashtable.ptr[i];
 374                 prev = NULL;
 375
 376                 while (lr) {
 377                         next = lr->hashlink;
 378
 379                         /* remove lock records with cleared references */
 380
 381                         if (lr->object == NULL) {
 382
 383                                 /* unlink the lock record from the hashtable */
 384
 385                                 if (prev == NULL)
 386                                         lock_hashtable.ptr[i] = next;
 387                                 else
 388                                         prev->hashlink = next;
 389
 390                                 /* free the lock record */
 391
 392                                 lock_record_free(lr);
 393
 394                         } else {
 395                                 prev = lr;
 396                         }
 397
 398                         lr = next;
 399                 }
 400         }
 401
 402         /* unlock the hashtable */
 403
 404         Mutex_unlock(lock_hashtable.mutex);
 405 }
 406 #endif
 407
 408
 409 /* lock_hashtable_get **********************************************************
 410
 411    Find the lock record for the given object.  If it does not exists,
 412    yet, create it and enter it in the hashtable.
 413
 414    IN:
 415           o....the object to look up
 416
 417    RETURN VALUE:
 418       the lock record to use for this object
 419
 420 *******************************************************************************/
 421
 422 #if defined(ENABLE_GC_BOEHM)
 423 static void lock_record_finalizer(void *object, void *p);
 424 #endif
 425
 426 static lock_record_t *lock_hashtable_get(java_handle_t* o)
 427 {
 428         // This function is inside a critical section.
 429         GCCriticalSection cs;
 430
 431         u4             slot;
 432         lock_record_t *lr;
 433
 434         // lw_cache is used throughout this file because the lockword can change at
 435         // any time, unless it is absolutely certain that we are holding the lock.
 436         // We don't do deflation, so we would also not expect a fat lockword to
 437         // change, but for the sake of uniformity, lw_cache is used even in this
 438         // case.
 439         uintptr_t lw_cache = *lock_lockword_get(o);
 440         Lockword lockword(lw_cache);
 441
 442         if (lockword.is_fat_lock())
 443                 return lockword.get_fat_lock();
 444
 445         // Lock the hashtable.
 446         lock_hashtable.mutex->lock();
 447
 448         /* lookup the lock record in the hashtable */
 449
 450         slot = heap_hashcode(LLNI_DIRECT(o)) % lock_hashtable.size;
 451         lr   = lock_hashtable.ptr[slot];
 452
 453         for (; lr != NULL; lr = lr->hashlink) {
 454                 if (lr->object == LLNI_DIRECT(o))
 455                         break;
 456         }
 457
 458         if (lr == NULL) {
 459                 /* not found, we must create a new one */
 460
 461                 lr = lock_record_new();
 462
 463                 lr->object = LLNI_DIRECT(o);
 464
 465 #if defined(ENABLE_GC_BOEHM)
 466                 /* register new finalizer to clean up the lock record */
 467
 468                 GC_finalization_proc ofinal = 0;
 469                 GC_REGISTER_FINALIZER_UNREACHABLE(LLNI_DIRECT(o), lock_record_finalizer, 0, &ofinal, 0);
 470
 471                 /* There was a finalizer -- reinstall it. We do not want to disrupt the
 472                    normal finalizer operation. We hold the monitor on this object, so
 473                    this is thread-safe. */
 474                 if (ofinal)
 475                         GC_REGISTER_FINALIZER_NO_ORDER(LLNI_DIRECT(o), ofinal, 0, 0, 0);
 476 #endif
 477
 478                 /* enter it in the hashtable */
 479
 480                 lr->hashlink             = lock_hashtable.ptr[slot];
 481                 lock_hashtable.ptr[slot] = lr;
 482                 lock_hashtable.entries++;
 483
 484                 /* check whether the hash should grow */
 485
 486                 if (lock_hashtable.entries * 3 > lock_hashtable.size * 4) {
 487                         lock_hashtable_grow();
 488                 }
 489         }
 490
 491         // Unlock the hashtable.
 492         lock_hashtable.mutex->unlock();
 493
 494         /* return the new lock record */
 495
 496         return lr;
 497 }
 498
 499 /* lock_schedule_lockrecord_removal ********************************************
 500
 501    Gives the locking system a chance to schedule the removal of an unused lock
 502    record. This function is called after an object's finalizer has run.
 503
 504    IN:
 505           o....the object which has been finalized
 506
 507 *******************************************************************************/
 508
 509 #if defined(ENABLE_GC_BOEHM)
 510 void lock_schedule_lockrecord_removal(java_handle_t *o)
 511 {
 512         Lockword lockword(*lock_lockword_get(o));
 513         if (!lockword.is_fat_lock())
 514                 /* there is no lock record */
 515                 return;
 516
 517         /* register new finalizer to clean up the lock record */
 518         GC_REGISTER_FINALIZER_UNREACHABLE(LLNI_DIRECT(o), lock_record_finalizer, 0, 0, 0);
 519 }
 520 #endif
 521
 522
 523 /* lock_hashtable_remove *******************************************************
 524
 525    Remove the lock record for the given object from the hashtable
 526    and free it afterwards.
 527
 528    IN:
 529        t....the current thread
 530        o....the object to look up
 531
 532 *******************************************************************************/
 533
 534 static void lock_hashtable_remove(threadobject *t, java_handle_t *o)
 535 {
 536         lock_record_t *lr;
 537         u4             slot;
 538         lock_record_t *tmplr;
 539
 540         // Lock the hashtable.
 541         lock_hashtable.mutex->lock();
 542
 543         /* get lock record */
 544
 545         uintptr_t lw_cache = *lock_lockword_get(o);
 546         Lockword lockword(lw_cache);
 547
 548         // Sanity check.
 549         assert(lockword.is_fat_lock());
 550
 551         lr = lockword.get_fat_lock();
 552
 553         /* remove the lock-record from the hashtable */
 554
 555         slot  = heap_hashcode(LLNI_DIRECT(o)) % lock_hashtable.size;
 556         tmplr = lock_hashtable.ptr[slot];
 557
 558         if (tmplr == lr) {
 559                 /* special handling if it's the first in the chain */
 560
 561                 lock_hashtable.ptr[slot] = lr->hashlink;
 562         }
 563         else {
 564                 for (; tmplr != NULL; tmplr = tmplr->hashlink) {
 565                         if (tmplr->hashlink == lr) {
 566                                 tmplr->hashlink = lr->hashlink;
 567                                 break;
 568                         }
 569                 }
 570
 571                 assert(tmplr != NULL);
 572         }
 573
 574         /* decrease entry count */
 575
 576         lock_hashtable.entries--;
 577
 578         // Unlock the hashtable.
 579         lock_hashtable.mutex->unlock();
 580
 581         /* free the lock record */
 582
 583         lock_record_free(lr);
 584 }
 585
 586
 587 /* lock_record_finalizer *******************************************************
 588
 589    XXX Remove me for exact GC.
 590
 591 *******************************************************************************/
 592
 593 static void lock_record_finalizer(void *object, void *p)
 594 {
 595         java_handle_t *o;
 596         classinfo     *c;
 597
 598         o = (java_handle_t *) object;
 599
 600 #if !defined(ENABLE_GC_CACAO) && defined(ENABLE_HANDLES)
 601         /* XXX this is only a dirty hack to make Boehm work with handles */
 602
 603         o = LLNI_WRAP((java_object_t *) o);
 604 #endif
 605
 606         LLNI_class_get(o, c);
 607
 608 #if !defined(NDEBUG)
 609         if (opt_DebugFinalizer) {
 610                 log_start();
 611                 log_print("[finalizer lockrecord: o=%p p=%p class=", object, p);
 612                 class_print(c);
 613                 log_print("]");
 614                 log_finish();
 615         }
 616 #endif
 617
 618         /* remove the lock-record entry from the hashtable and free it */
 619
 620         lock_hashtable_remove(THREADOBJECT, o);
 621 }
 622
 623
 624 /*============================================================================*/
 625 /* LOCKING ALGORITHM                                                          */
 626 /*============================================================================*/
 627
 628
 629 /* lock_lockword_get ***********************************************************
 630
 631    Get the lockword for the given object.
 632
 633    IN:
 634       o............the object
 635
 636 *******************************************************************************/
 637
 638 static inline uintptr_t* lock_lockword_get(java_handle_t* o)
 639 {
 640 #if defined(ENABLE_GC_CACAO)
 641         // Sanity check.
 642         assert(GCCriticalSection::inside() == true);
 643 #endif
 644
 645         return &(LLNI_DIRECT(o)->lockword);
 646 }
 647
 648
 649 /* lock_record_enter ***********************************************************
 650
 651    Enter the lock represented by the given lock record.
 652
 653    IN:
 654       t.................the current thread
 655           lr................the lock record
 656
 657 *******************************************************************************/
 658
 659 static inline void lock_record_enter(threadobject *t, lock_record_t *lr)
 660 {
 661         lr->mutex->lock();
 662         lr->owner = t;
 663 }
 664
 665
 666 /* lock_record_exit ************************************************************
 667
 668    Release the lock represented by the given lock record.
 669
 670    IN:
 671       t.................the current thread
 672           lr................the lock record
 673
 674    PRE-CONDITION:
 675       The current thread must own the lock represented by this lock record.
 676           This is NOT checked by this function!
 677
 678 *******************************************************************************/
 679
 680 static inline void lock_record_exit(threadobject *t, lock_record_t *lr)
 681 {
 682         lr->owner = NULL;
 683         lr->mutex->unlock();
 684 }
 685
 686
 687 /* lock_inflate ****************************************************************
 688
 689    Inflate the lock of the given object. This may only be called by the
 690    owner of the monitor of the object.
 691
 692    IN:
 693           o............the object of which to inflate the lock
 694           lr...........the lock record to install. The current thread must
 695                        own the lock of this lock record!
 696
 697    PRE-CONDITION:
 698       The current thread must be the owner of this object's monitor AND
 699           of the lock record's lock!
 700
 701 *******************************************************************************/
 702
 703 static void lock_inflate(java_handle_t *o, lock_record_t *lr)
 704 {
 705         Lockword lockword(*lock_lockword_get(o));
 706         lockword.inflate(lr);
 707 }
 708
 709
 710 /* sable_flc_waiting ***********************************************************
 711
 712    Enqueue the current thread on another thread's FLC list. The function
 713    blocks until the lock has been inflated by the owning thread.
 714
 715    The algorithm used to be an almost literal copy from SableVM. The
 716    superfluous list traversal in the waiting loop has been removed since,
 717    though.
 718
 719    IN:
 720           lockword.....the object's lockword as seen at the first locking attempt
 721           t............the current thread
 722           o............the object of which to enter the monitor
 723
 724 *******************************************************************************/
 725
 726 static void sable_flc_waiting(uintptr_t lw_cache, threadobject *t, java_handle_t *o)
 727 {
 728         int32_t index;
 729         threadobject *t_other;
 730         int old_flc;
 731
 732         Lockword lockword(lw_cache);
 733         index = lockword.get_thin_lock_thread_index();
 734         t_other = ThreadList::get_thread_by_index(index);
 735
 736         // The lockword could have changed during our way here.  If the
 737         // thread index is zero, the lock got unlocked and we simply
 738         // return.
 739         if (t_other == NULL)
 740 /*              failure, TODO: add statistics */
 741                 return;
 742
 743         t_other->flc_lock->lock();
 744         old_flc = t_other->flc_bit;
 745         t_other->flc_bit = true;
 746
 747         DEBUGLOCKS(("thread %d set flc bit for lock-holding thread %d", t->index, t_other->index));
 748
 749         // Set FLC bit first, then read the lockword again.
 750         Atomic::memory_barrier();
 751
 752         lw_cache = *lock_lockword_get(o);
 753
 754         /* Lockword is still the way it was seen before */
 755         if (lockword.is_thin_lock() && (lockword.get_thin_lock_thread_index() == index))
 756         {
 757                 threadobject *f;
 758                 /* Add tuple (t, o) to the other thread's FLC list */
 759                 t->flc_object = o;
 760                 t->flc_next = t_other->flc_list;
 761                 t_other->flc_list = t;
 762                 if (t->flc_next == 0)
 763                         t_other->flc_tail = t;
 764                 f = t_other->flc_tail;
 765
 766                 // The other thread will clear flc_object.
 767                 while (t->flc_object)
 768                 {
 769                         // We are not cleared yet -- the other thread cannot have seen
 770                         // the FLC bit yet.
 771                         assert(t_other->flc_bit);
 772
 773                         // Wait until another thread sees the flc bit and notifies
 774                         // us of unlocking.
 775                         t->flc_cond->wait(t_other->flc_lock);
 776                 }
 777
 778                 t->flc_next = NULL;
 779         }
 780         else
 781                 t_other->flc_bit = old_flc;
 782
 783         t_other->flc_lock->unlock();
 784 }
 785
 786 /* notify_flc_waiters **********************************************************
 787
 788    Traverse the thread's FLC list and inflate all corresponding locks. Notify
 789    the associated threads as well.
 790
 791    IN:
 792           t............the current thread
 793           o............the object currently being unlocked
 794
 795 *******************************************************************************/
 796
 797 static void notify_flc_waiters(threadobject *t, java_handle_t *o)
 798 {
 799         threadobject *current;
 800
 801         t->flc_lock->lock();
 802
 803         current = t->flc_list;
 804         while (current)
 805         {
 806                 if (current->flc_object != o)
 807                 {
 808                         /* The object has to be inflated so the other threads can properly
 809                            block on it. */
 810
 811                         // Only if not already inflated.
 812                         Lockword lockword(*lock_lockword_get(current->flc_object));
 813                         if (lockword.is_thin_lock()) {
 814                                 lock_record_t *lr = lock_hashtable_get(current->flc_object);
 815                                 lock_record_enter(t, lr);
 816
 817                                 DEBUGLOCKS(("thread %d inflating lock of %p to lr %p",
 818                                                         t->index, (void*) current->flc_object, (void*) lr));
 819
 820                                 lock_inflate(current->flc_object, lr);
 821                         }
 822                 }
 823
 824                 // Wake the waiting threads.
 825                 current->flc_cond->broadcast();
 826                 current->flc_object = NULL;
 827
 828                 current = current->flc_next;
 829         }
 830
 831         t->flc_list = NULL;
 832         t->flc_bit = false;
 833
 834         t->flc_lock->unlock();
 835 }
 836
 837 /* lock_monitor_enter **********************************************************
 838
 839    Acquire the monitor of the given object. If the current thread already
 840    owns the monitor, the lock counter is simply increased.
 841
 842    This function blocks until it can acquire the monitor.
 843
 844    IN:
 845       t............the current thread
 846           o............the object of which to enter the monitor
 847
 848    RETURN VALUE:
 849       true.........the lock has been successfully acquired
 850           false........an exception has been thrown
 851
 852 *******************************************************************************/
 853
 854 bool lock_monitor_enter(java_handle_t *o)
 855 {
 856         // This function is inside a critical section.
 857         GCCriticalSection cs;
 858
 859         if (o == NULL) {
 860                 exceptions_throw_nullpointerexception();
 861                 return false;
 862         }
 863
 864         threadobject* t = thread_get_current();
 865
 866         uintptr_t thinlock = t->thinlock;
 867
 868 retry:
 869         // Most common case: try to thin-lock an unlocked object.
 870         uintptr_t *lw_ptr = lock_lockword_get(o);
 871         uintptr_t lw_cache = *lw_ptr;
 872         Lockword lockword(lw_cache);
 873         bool result = Lockword(*lw_ptr).lock(thinlock);
 874
 875         if (result == true) {
 876                 // Success, we locked it.
 877                 // NOTE: The Java Memory Model requires a memory barrier here.
 878 #if defined(CAS_PROVIDES_FULL_BARRIER) && CAS_PROVIDES_FULL_BARRIER
 879                 // On some architectures, the CAS (hidden in the
 880                 // lockword.lock call above), already provides this barrier,
 881                 // so we only need to inform the compiler.
 882                 Atomic::instruction_barrier();
 883 #else
 884                 Atomic::memory_barrier();
 885 #endif
 886                 return true;
 887         }
 888
 889         // Next common case: recursive lock with small recursion count.
 890         // NOTE: We don't have to worry about stale values here, as any
 891         // stale value will indicate another thread holding the lock (or
 892         // an inflated lock).
 893         if (lockword.get_thin_lock_without_count() == thinlock) {
 894                 // We own this monitor.  Check the current recursion count.
 895                 if (lockword.is_max_thin_lock_count() == false) {
 896                         // The recursion count is low enough.
 897                         Lockword(*lw_ptr).increase_thin_lock_count();
 898
 899                         // Success, we locked it.
 900                         return true;
 901                 }
 902                 else {
 903                         // Recursion count overflow.
 904                         lock_record_t* lr = lock_hashtable_get(o);
 905                         lock_record_enter(t, lr);
 906                         lock_inflate(o, lr);
 907                         lr->count++;
 908
 909                         notify_flc_waiters(t, o);
 910
 911                         return true;
 912                 }
 913         }
 914
 915         // The lock is either contented or fat.
 916         if (lockword.is_fat_lock()) {
 917                 lock_record_t* lr = lockword.get_fat_lock();
 918
 919                 // Check for recursive entering.
 920                 if (lr->owner == t) {
 921                         lr->count++;
 922                         return true;
 923                 }
 924
 925                 // Acquire the mutex of the lock record.
 926                 lock_record_enter(t, lr);
 927
 928                 // Sanity check.
 929                 assert(lr->count == 0);
 930                 return true;
 931         }
 932
 933         /****** inflation path ******/
 934
 935 #if defined(ENABLE_JVMTI)
 936         /* Monitor Contended Enter */
 937         jvmti_MonitorContendedEntering(false, o);
 938 #endif
 939
 940         sable_flc_waiting(lw_cache, t, o);
 941
 942 #if defined(ENABLE_JVMTI)
 943         /* Monitor Contended Entered */
 944         jvmti_MonitorContendedEntering(true, o);
 945 #endif
 946         goto retry;
 947 }
 948
 949
 950 /* lock_monitor_exit ***********************************************************
 951
 952    Decrement the counter of a (currently owned) monitor. If the counter
 953    reaches zero, release the monitor.
 954
 955    If the current thread is not the owner of the monitor, an
 956    IllegalMonitorState exception is thrown.
 957
 958    IN:
 959       t............the current thread
 960           o............the object of which to exit the monitor
 961
 962    RETURN VALUE:
 963       true.........everything ok,
 964           false........an exception has been thrown
 965
 966 *******************************************************************************/
 967
 968 bool lock_monitor_exit(java_handle_t* o)
 969 {
 970         // This function is inside a critical section.
 971         GCCriticalSection cs;
 972
 973         if (o == NULL) {
 974                 exceptions_throw_nullpointerexception();
 975                 return false;
 976         }
 977
 978         threadobject* t = thread_get_current();
 979
 980         uintptr_t thinlock = t->thinlock;
 981
 982         // We don't have to worry about stale values here, as any stale
 983         // value will indicate that we don't own the lock.
 984         uintptr_t *lw_ptr = lock_lockword_get(o);
 985         uintptr_t lw_cache = *lw_ptr;
 986         Lockword lockword(lw_cache);
 987
 988         // Most common case: we release a thin lock that we hold once.
 989         if (lockword.get_thin_lock() == thinlock) {
 990                 // Memory barrier for Java Memory Model.
 991                 Atomic::write_memory_barrier();
 992                 Lockword(*lw_ptr).unlock();
 993                 // Memory barrier for FLC bit testing.
 994                 Atomic::memory_barrier();
 995
 996                 /* check if there has been a flat lock contention on this object */
 997
 998                 if (t->flc_bit) {
 999                         DEBUGLOCKS(("thread %d saw flc bit", t->index));
1000
1001                         /* there has been a contention on this thin lock */
1002                         notify_flc_waiters(t, o);
1003                 }
1004
1005                 return true;
1006         }
1007
1008         // Next common case: we release a recursive lock, count > 0.
1009         if (lockword.get_thin_lock_without_count() == thinlock) {
1010                 Lockword(*lw_ptr).decrease_thin_lock_count();
1011                 return true;
1012         }
1013
1014         // Either the lock is fat, or we don't hold it at all.
1015         if (lockword.is_fat_lock()) {
1016                 lock_record_t* lr = lockword.get_fat_lock();
1017
1018                 // Check if we own this monitor.
1019                 // NOTE: We don't have to worry about stale values here, as
1020                 // any stale value will be != t and thus fail this check.
1021                 if (lr->owner != t) {
1022                         exceptions_throw_illegalmonitorstateexception();
1023                         return false;
1024                 }
1025
1026                 /* { the current thread `t` owns the lock record `lr` on object `o` } */
1027
1028                 if (lr->count != 0) {
1029                         // We had locked this one recursively.  Just decrement, it
1030                         // will still be locked.
1031                         lr->count--;
1032                         return true;
1033                 }
1034
1035                 // Unlock this lock record.
1036                 lock_record_exit(t, lr);
1037                 return true;
1038         }
1039
1040         // Legal thin lock cases have been handled above, so this is an
1041         // error.
1042         exceptions_throw_illegalmonitorstateexception();
1043
1044         return false;
1045 }
1046
1047
1048 /* lock_record_add_waiter ******************************************************
1049
1050    Add a thread to the list of waiting threads of a lock record.
1051
1052    IN:
1053       lr...........the lock record
1054       thread.......the thread to add
1055
1056 *******************************************************************************/
1057
1058 static void lock_record_add_waiter(lock_record_t *lr, threadobject* t)
1059 {
1060         // Add the thread as last entry to waiters list.
1061         lr->waiters->push_back(t);
1062
1063 #if defined(ENABLE_STATISTICS)
1064         if (opt_stat)
1065                 size_lock_waiter += sizeof(threadobject*);
1066 #endif
1067 }
1068
1069
1070 /* lock_record_remove_waiter ***************************************************
1071
1072    Remove a thread from the list of waiting threads of a lock record.
1073
1074    IN:
1075       lr...........the lock record
1076       t............the current thread
1077
1078    PRE-CONDITION:
1079       The current thread must be the owner of the lock record.
1080
1081 *******************************************************************************/
1082
1083 static void lock_record_remove_waiter(lock_record_t *lr, threadobject* t)
1084 {
1085         // Remove the thread from the waiters.
1086         lr->waiters->remove(t);
1087
1088 #if defined(ENABLE_STATISTICS)
1089         if (opt_stat)
1090                 size_lock_waiter -= sizeof(threadobject*);
1091 #endif
1092 }
1093
1094
1095 /* lock_record_wait ************************************************************
1096
1097    Wait on a lock record for a given (maximum) amount of time.
1098
1099    IN:
1100       t............the current thread
1101           lr...........the lock record
1102           millis.......milliseconds of timeout
1103           nanos........nanoseconds of timeout
1104
1105    RETURN VALUE:
1106       true.........we have been interrupted,
1107       false........everything ok
1108
1109    PRE-CONDITION:
1110       The current thread must be the owner of the lock record.
1111           This is NOT checked by this function!
1112
1113 *******************************************************************************/
1114
1115 static bool lock_record_wait(threadobject *thread, lock_record_t *lr, s8 millis, s4 nanos)
1116 {
1117         s4   lockcount;
1118         bool wasinterrupted = false;
1119
1120         DEBUGLOCKS(("[lock_record_wait  : lr=%p, t=%p, millis=%lld, nanos=%d]",
1121                                 lr, thread, millis, nanos));
1122
1123         /* { the thread t owns the fat lock record lr on the object o } */
1124
1125         /* register us as waiter for this object */
1126
1127         lock_record_add_waiter(lr, thread);
1128
1129         /* remember the old lock count */
1130
1131         lockcount = lr->count;
1132
1133         /* unlock this record */
1134
1135         lr->count = 0;
1136         lock_record_exit(thread, lr);
1137
1138         /* wait until notified/interrupted/timed out */
1139
1140         threads_wait_with_timeout_relative(thread, millis, nanos);
1141
1142         /* re-enter the monitor */
1143
1144         lock_record_enter(thread, lr);
1145
1146         /* remove us from the list of waiting threads */
1147
1148         lock_record_remove_waiter(lr, thread);
1149
1150         /* restore the old lock count */
1151
1152         lr->count = lockcount;
1153
1154         /* We can only be signaled OR interrupted, not both. If both flags
1155            are set, reset only signaled and leave the thread in
1156            interrupted state. Otherwise, clear both. */
1157
1158         if (!thread->signaled) {
1159                 wasinterrupted = thread->interrupted;
1160                 thread->interrupted = false;
1161         }
1162
1163         thread->signaled = false;
1164
1165         /* return if we have been interrupted */
1166
1167         return wasinterrupted;
1168 }
1169
1170
1171 /* lock_monitor_wait ***********************************************************
1172
1173    Wait on an object for a given (maximum) amount of time.
1174
1175    IN:
1176       t............the current thread
1177           o............the object
1178           millis.......milliseconds of timeout
1179           nanos........nanoseconds of timeout
1180
1181    PRE-CONDITION:
1182       The current thread must be the owner of the object's monitor.
1183
1184 *******************************************************************************/
1185
1186 static void lock_monitor_wait(threadobject *t, java_handle_t *o, s8 millis, s4 nanos)
1187 {
1188         lock_record_t *lr;
1189
1190         uintptr_t *lw_ptr = lock_lockword_get(o);
1191         uintptr_t lw_cache = *lw_ptr;
1192         Lockword lockword(lw_cache);
1193
1194         // Check if we own this monitor.
1195         // NOTE: We don't have to worry about stale values here, as any
1196         // stale value will fail this check.
1197         if (lockword.is_fat_lock()) {
1198                 lr = lockword.get_fat_lock();
1199
1200                 if (lr->owner != t) {
1201                         exceptions_throw_illegalmonitorstateexception();
1202                         return;
1203                 }
1204         }
1205         else {
1206                 // It's a thin lock.
1207                 if (lockword.get_thin_lock_without_count() != t->thinlock) {
1208                         exceptions_throw_illegalmonitorstateexception();
1209                         return;
1210                 }
1211
1212                 // Get the lock-record.
1213                 lr = lock_hashtable_get(o);
1214                 lock_record_enter(t, lr);
1215
1216                 // Inflate this lock.
1217                 Lockword(*lw_ptr).inflate(lr);
1218
1219                 notify_flc_waiters(t, o);
1220         }
1221
1222         /* { the thread t owns the fat lock record lr on the object o } */
1223
1224         if (lock_record_wait(t, lr, millis, nanos))
1225                 exceptions_throw_interruptedexception();
1226 }
1227
1228
1229 /* lock_record_notify **********************************************************
1230
1231    Notify one thread or all threads waiting on the given lock record.
1232
1233    IN:
1234       t............the current thread
1235           lr...........the lock record
1236           one..........if true, only notify one thread
1237
1238    PRE-CONDITION:
1239       The current thread must be the owner of the lock record.
1240           This is NOT checked by this function!
1241
1242 *******************************************************************************/
1243
1244 static void lock_record_notify(threadobject *t, lock_record_t *lr, bool one)
1245 {
1246 #if defined(ENABLE_GC_CACAO)
1247         // Sanity check.
1248         assert(GCCriticalSection::inside() == false);
1249 #endif
1250
1251         // { The thread t owns the fat lock record lr on the object o }
1252
1253         for (List<threadobject*>::iterator it = lr->waiters->begin(); it != lr->waiters->end(); it++) {
1254                 threadobject* waiter = *it;
1255
1256                 // We must skip threads which have already been notified. They
1257                 // will remove themselves from the list.
1258                 if (waiter->signaled)
1259                         continue;
1260
1261                 // Enter the wait-mutex.
1262                 waiter->waitmutex->lock();
1263
1264                 DEBUGLOCKS(("[lock_record_notify: lr=%p, t=%p, waitingthread=%p, one=%d]", lr, t, waiter, one));
1265
1266                 // Signal the waiter.
1267                 waiter->waitcond->signal();
1268
1269                 // Mark the thread as signaled.
1270                 waiter->signaled = true;
1271
1272                 // Leave the wait-mutex.
1273                 waiter->waitmutex->unlock();
1274
1275                 // If we should only wake one thread, we are done.
1276                 if (one)
1277                         break;
1278         }
1279 }
1280
1281
1282 /* lock_monitor_notify *********************************************************
1283
1284    Notify one thread or all threads waiting on the given object.
1285
1286    IN:
1287       t............the current thread
1288           o............the object
1289           one..........if true, only notify one thread
1290
1291    PRE-CONDITION:
1292       The current thread must be the owner of the object's monitor.
1293
1294 *******************************************************************************/
1295
1296 static void lock_monitor_notify(threadobject *t, java_handle_t *o, bool one)
1297 {
1298         lock_record_t* lr = NULL;
1299
1300         {
1301                 // This scope is inside a critical section.
1302                 GCCriticalSection cs;
1303
1304                 uintptr_t lw_cache = *lock_lockword_get(o);
1305                 Lockword lockword(lw_cache);
1306
1307                 // Check if we own this monitor.
1308                 // NOTE: We don't have to worry about stale values here, as any
1309                 // stale value will fail this check.
1310
1311                 if (lockword.is_fat_lock()) {
1312                         lr = lockword.get_fat_lock();
1313
1314                         if (lr->owner != t) {
1315                                 exceptions_throw_illegalmonitorstateexception();
1316                                 return;
1317                         }
1318                 }
1319                 else {
1320                         // It's a thin lock.
1321                         if (lockword.get_thin_lock_without_count() != t->thinlock) {
1322                                 exceptions_throw_illegalmonitorstateexception();
1323                                 return;
1324                         }
1325
1326                         // No thread can wait on a thin lock, so there's nothing to do.
1327                         return;
1328                 }
1329         }
1330
1331         // { The thread t owns the fat lock record lr on the object o }
1332         lock_record_notify(t, lr, one);
1333 }
1334
1335
1336
1337 /*============================================================================*/
1338 /* INQUIRY FUNCIONS                                                           */
1339 /*============================================================================*/
1340
1341
1342 /* lock_is_held_by_current_thread **********************************************
1343
1344    Return true if the current thread owns the monitor of the given object.
1345
1346    IN:
1347           o............the object
1348
1349    RETURN VALUE:
1350       true, if the current thread holds the lock of this object.
1351
1352 *******************************************************************************/
1353
1354 bool lock_is_held_by_current_thread(java_handle_t *o)
1355 {
1356         // This function is inside a critical section.
1357         GCCriticalSection cs;
1358
1359         // Check if we own this monitor.
1360         // NOTE: We don't have to worry about stale values here, as any
1361         // stale value will fail this check.
1362         threadobject* t = thread_get_current();
1363         uintptr_t lw_cache = *lock_lockword_get(o);
1364         Lockword lockword(lw_cache);
1365
1366         if (lockword.is_fat_lock()) {
1367                 // It's a fat lock.
1368                 lock_record_t* lr = lockword.get_fat_lock();
1369                 return (lr->owner == t);
1370         }
1371         else {
1372                 // It's a thin lock.
1373                 return (lockword.get_thin_lock_without_count() == t->thinlock);
1374         }
1375 }
1376
1377
1378
1379 /*============================================================================*/
1380 /* WRAPPERS FOR OPERATIONS ON THE CURRENT THREAD                              */
1381 /*============================================================================*/
1382
1383
1384 /* lock_wait_for_object ********************************************************
1385
1386    Wait for the given object.
1387
1388    IN:
1389           o............the object
1390           millis.......milliseconds to wait
1391           nanos........nanoseconds to wait
1392
1393 *******************************************************************************/
1394
1395 void lock_wait_for_object(java_handle_t *o, s8 millis, s4 nanos)
1396 {
1397         threadobject *thread;
1398
1399         thread = THREADOBJECT;
1400
1401         lock_monitor_wait(thread, o, millis, nanos);
1402 }
1403
1404
1405 /* lock_notify_object **********************************************************
1406
1407    Notify one thread waiting on the given object.
1408
1409    IN:
1410           o............the object
1411
1412 *******************************************************************************/
1413
1414 void lock_notify_object(java_handle_t *o)
1415 {
1416         threadobject *thread;
1417
1418         thread = THREADOBJECT;
1419
1420         lock_monitor_notify(thread, o, true);
1421 }
1422
1423
1424 /* lock_notify_all_object ******************************************************
1425
1426    Notify all threads waiting on the given object.
1427
1428    IN:
1429           o............the object
1430
1431 *******************************************************************************/
1432
1433 void lock_notify_all_object(java_handle_t *o)
1434 {
1435         threadobject *thread;
1436
1437         thread = THREADOBJECT;
1438
1439         lock_monitor_notify(thread, o, false);
1440 }
1441
1442
1443 /*
1444  * These are local overrides for various environment variables in Emacs.
1445  * Please do not remove this and leave it at the end of the file, where
1446  * Emacs will automagically detect them.
1447  * ---------------------------------------------------------------------
1448  * Local variables:
1449  * mode: c++
1450  * indent-tabs-mode: t
1451  * c-basic-offset: 4
1452  * tab-width: 4
1453  * End:
1454  * vim:noexpandtab:sw=4:ts=4:
1455  */