src/threads/lock.cpp

   1 /* src/threads/lock.cpp - lock implementation
   2
   3    Copyright (C) 1996-2011
   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(java_handle_t *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                 Finalizer::attach_custom_finalizer(o, lock_record_finalizer, 0);
 469 #endif
 470
 471                 /* enter it in the hashtable */
 472
 473                 lr->hashlink             = lock_hashtable.ptr[slot];
 474                 lock_hashtable.ptr[slot] = lr;
 475                 lock_hashtable.entries++;
 476
 477                 /* check whether the hash should grow */
 478
 479                 if (lock_hashtable.entries * 3 > lock_hashtable.size * 4) {
 480                         lock_hashtable_grow();
 481                 }
 482         }
 483
 484         // Unlock the hashtable.
 485         lock_hashtable.mutex->unlock();
 486
 487         /* return the new lock record */
 488
 489         return lr;
 490 }
 491
 492 /* lock_hashtable_remove *******************************************************
 493
 494    Remove the lock record for the given object from the hashtable
 495    and free it afterwards.
 496
 497    IN:
 498        t....the current thread
 499        o....the object to look up
 500
 501 *******************************************************************************/
 502
 503 static void lock_hashtable_remove(threadobject *t, java_handle_t *o)
 504 {
 505         lock_record_t *lr;
 506         u4             slot;
 507         lock_record_t *tmplr;
 508
 509         // Lock the hashtable.
 510         lock_hashtable.mutex->lock();
 511
 512         /* get lock record */
 513
 514         uintptr_t lw_cache = *lock_lockword_get(o);
 515         Lockword lockword(lw_cache);
 516
 517         // Sanity check.
 518         assert(lockword.is_fat_lock());
 519
 520         lr = lockword.get_fat_lock();
 521
 522         /* remove the lock-record from the hashtable */
 523
 524         slot  = heap_hashcode(LLNI_DIRECT(o)) % lock_hashtable.size;
 525         tmplr = lock_hashtable.ptr[slot];
 526
 527         if (tmplr == lr) {
 528                 /* special handling if it's the first in the chain */
 529
 530                 lock_hashtable.ptr[slot] = lr->hashlink;
 531         }
 532         else {
 533                 for (; tmplr != NULL; tmplr = tmplr->hashlink) {
 534                         if (tmplr->hashlink == lr) {
 535                                 tmplr->hashlink = lr->hashlink;
 536                                 break;
 537                         }
 538                 }
 539
 540                 assert(tmplr != NULL);
 541         }
 542
 543         /* decrease entry count */
 544
 545         lock_hashtable.entries--;
 546
 547         // Unlock the hashtable.
 548         lock_hashtable.mutex->unlock();
 549
 550         /* free the lock record */
 551
 552         lock_record_free(lr);
 553 }
 554
 555
 556 /* lock_record_finalizer *******************************************************
 557
 558    XXX Remove me for exact GC.
 559
 560 *******************************************************************************/
 561
 562 static void lock_record_finalizer(java_handle_t *o, void *p)
 563 {
 564 #if !defined(NDEBUG)
 565         classinfo     *c;
 566
 567         LLNI_class_get(o, c);
 568
 569         if (opt_DebugFinalizer) {
 570                 log_start();
 571                 log_print("[finalizer lockrecord: o=%p p=%p class=", o, p);
 572                 class_print(c);
 573                 log_print("]");
 574                 log_finish();
 575         }
 576 #endif
 577
 578         /* remove the lock-record entry from the hashtable and free it */
 579
 580         lock_hashtable_remove(THREADOBJECT, o);
 581 }
 582
 583
 584 /*============================================================================*/
 585 /* LOCKING ALGORITHM                                                          */
 586 /*============================================================================*/
 587
 588
 589 /* lock_lockword_get ***********************************************************
 590
 591    Get the lockword for the given object.
 592
 593    IN:
 594       o............the object
 595
 596 *******************************************************************************/
 597
 598 static inline uintptr_t* lock_lockword_get(java_handle_t* o)
 599 {
 600 #if defined(ENABLE_GC_CACAO)
 601         // Sanity check.
 602         assert(GCCriticalSection::inside() == true);
 603 #endif
 604
 605         return &(LLNI_DIRECT(o)->lockword);
 606 }
 607
 608
 609 /* lock_record_enter ***********************************************************
 610
 611    Enter the lock represented by the given lock record.
 612
 613    IN:
 614       t.................the current thread
 615           lr................the lock record
 616
 617 *******************************************************************************/
 618
 619 static inline void lock_record_enter(threadobject *t, lock_record_t *lr)
 620 {
 621         lr->mutex->lock();
 622         lr->owner = t;
 623 }
 624
 625
 626 /* lock_record_exit ************************************************************
 627
 628    Release the lock represented by the given lock record.
 629
 630    IN:
 631       t.................the current thread
 632           lr................the lock record
 633
 634    PRE-CONDITION:
 635       The current thread must own the lock represented by this lock record.
 636           This is NOT checked by this function!
 637
 638 *******************************************************************************/
 639
 640 static inline void lock_record_exit(threadobject *t, lock_record_t *lr)
 641 {
 642         lr->owner = NULL;
 643         lr->mutex->unlock();
 644 }
 645
 646
 647 /* lock_inflate ****************************************************************
 648
 649    Inflate the lock of the given object. This may only be called by the
 650    owner of the monitor of the object.
 651
 652    IN:
 653           o............the object of which to inflate the lock
 654           lr...........the lock record to install. The current thread must
 655                        own the lock of this lock record!
 656
 657    PRE-CONDITION:
 658       The current thread must be the owner of this object's monitor AND
 659           of the lock record's lock!
 660
 661 *******************************************************************************/
 662
 663 static void lock_inflate(java_handle_t *o, lock_record_t *lr)
 664 {
 665         Lockword lockword(*lock_lockword_get(o));
 666         lockword.inflate(lr);
 667 }
 668
 669
 670 /* sable_flc_waiting ***********************************************************
 671
 672    Enqueue the current thread on another thread's FLC list. The function
 673    blocks until the lock has been inflated by the owning thread.
 674
 675    The algorithm used to be an almost literal copy from SableVM. The
 676    superfluous list traversal in the waiting loop has been removed since,
 677    though.
 678
 679    IN:
 680           lockword.....the object's lockword as seen at the first locking attempt
 681           t............the current thread
 682           o............the object of which to enter the monitor
 683
 684 *******************************************************************************/
 685
 686 static void sable_flc_waiting(uintptr_t lw_cache, threadobject *t, java_handle_t *o)
 687 {
 688         int32_t index;
 689         threadobject *t_other;
 690         int old_flc;
 691
 692         Lockword lockword(lw_cache);
 693         index = lockword.get_thin_lock_thread_index();
 694         t_other = ThreadList::get_thread_by_index(index);
 695
 696         // The lockword could have changed during our way here.  If the
 697         // thread index is zero, the lock got unlocked and we simply
 698         // return.
 699         if (t_other == NULL)
 700 /*              failure, TODO: add statistics */
 701                 return;
 702
 703         t_other->flc_lock->lock();
 704         old_flc = t_other->flc_bit;
 705         t_other->flc_bit = true;
 706
 707         DEBUGLOCKS(("thread %d set flc bit for lock-holding thread %d", t->index, t_other->index));
 708
 709         // Set FLC bit first, then read the lockword again.
 710         Atomic::memory_barrier();
 711
 712         lw_cache = *lock_lockword_get(o);
 713
 714         /* Lockword is still the way it was seen before */
 715         if (lockword.is_thin_lock() && (lockword.get_thin_lock_thread_index() == index))
 716         {
 717                 threadobject *f;
 718                 /* Add tuple (t, o) to the other thread's FLC list */
 719                 t->flc_object = o;
 720                 t->flc_next = t_other->flc_list;
 721                 t_other->flc_list = t;
 722                 if (t->flc_next == 0)
 723                         t_other->flc_tail = t;
 724                 f = t_other->flc_tail;
 725
 726                 // The other thread will clear flc_object.
 727                 while (t->flc_object)
 728                 {
 729                         // We are not cleared yet -- the other thread cannot have seen
 730                         // the FLC bit yet.
 731                         assert(t_other->flc_bit);
 732
 733                         // Wait until another thread sees the flc bit and notifies
 734                         // us of unlocking.
 735                         t->flc_cond->wait(t_other->flc_lock);
 736                 }
 737
 738                 t->flc_next = NULL;
 739         }
 740         else
 741                 t_other->flc_bit = old_flc;
 742
 743         t_other->flc_lock->unlock();
 744 }
 745
 746 /* notify_flc_waiters **********************************************************
 747
 748    Traverse the thread's FLC list and inflate all corresponding locks. Notify
 749    the associated threads as well.
 750
 751    IN:
 752           t............the current thread
 753           o............the object currently being unlocked
 754
 755 *******************************************************************************/
 756
 757 static void notify_flc_waiters(threadobject *t, java_handle_t *o)
 758 {
 759         threadobject *current;
 760
 761         t->flc_lock->lock();
 762
 763         current = t->flc_list;
 764         while (current)
 765         {
 766                 if (current->flc_object != o)
 767                 {
 768                         /* The object has to be inflated so the other threads can properly
 769                            block on it. */
 770
 771                         // Only if not already inflated.
 772                         Lockword lockword(*lock_lockword_get(current->flc_object));
 773                         if (lockword.is_thin_lock()) {
 774                                 lock_record_t *lr = lock_hashtable_get(current->flc_object);
 775                                 lock_record_enter(t, lr);
 776
 777                                 DEBUGLOCKS(("thread %d inflating lock of %p to lr %p",
 778                                                         t->index, (void*) current->flc_object, (void*) lr));
 779
 780                                 lock_inflate(current->flc_object, lr);
 781                         }
 782                 }
 783
 784                 // Wake the waiting threads.
 785                 current->flc_cond->broadcast();
 786                 current->flc_object = NULL;
 787
 788                 current = current->flc_next;
 789         }
 790
 791         t->flc_list = NULL;
 792         t->flc_bit = false;
 793
 794         t->flc_lock->unlock();
 795 }
 796
 797 /* lock_monitor_enter **********************************************************
 798
 799    Acquire the monitor of the given object. If the current thread already
 800    owns the monitor, the lock counter is simply increased.
 801
 802    This function blocks until it can acquire the monitor.
 803
 804    IN:
 805       t............the current thread
 806           o............the object of which to enter the monitor
 807
 808    RETURN VALUE:
 809       true.........the lock has been successfully acquired
 810           false........an exception has been thrown
 811
 812 *******************************************************************************/
 813
 814 bool lock_monitor_enter(java_handle_t *o)
 815 {
 816         // This function is inside a critical section.
 817         GCCriticalSection cs;
 818
 819         if (o == NULL) {
 820                 exceptions_throw_nullpointerexception();
 821                 return false;
 822         }
 823
 824         threadobject* t = thread_get_current();
 825
 826         uintptr_t thinlock = t->thinlock;
 827
 828 retry:
 829         // Most common case: try to thin-lock an unlocked object.
 830         uintptr_t *lw_ptr = lock_lockword_get(o);
 831         uintptr_t lw_cache = *lw_ptr;
 832         Lockword lockword(lw_cache);
 833         bool result = Lockword(*lw_ptr).lock(thinlock);
 834
 835         if (result == true) {
 836                 // Success, we locked it.
 837                 // NOTE: The Java Memory Model requires a memory barrier here.
 838 #if defined(CAS_PROVIDES_FULL_BARRIER) && CAS_PROVIDES_FULL_BARRIER
 839                 // On some architectures, the CAS (hidden in the
 840                 // lockword.lock call above), already provides this barrier,
 841                 // so we only need to inform the compiler.
 842                 Atomic::instruction_barrier();
 843 #else
 844                 Atomic::memory_barrier();
 845 #endif
 846                 return true;
 847         }
 848
 849         // Next common case: recursive lock with small recursion count.
 850         // NOTE: We don't have to worry about stale values here, as any
 851         // stale value will indicate another thread holding the lock (or
 852         // an inflated lock).
 853         if (lockword.get_thin_lock_without_count() == thinlock) {
 854                 // We own this monitor.  Check the current recursion count.
 855                 if (lockword.is_max_thin_lock_count() == false) {
 856                         // The recursion count is low enough.
 857                         Lockword(*lw_ptr).increase_thin_lock_count();
 858
 859                         // Success, we locked it.
 860                         return true;
 861                 }
 862                 else {
 863                         // Recursion count overflow.
 864                         lock_record_t* lr = lock_hashtable_get(o);
 865                         lock_record_enter(t, lr);
 866                         lock_inflate(o, lr);
 867                         lr->count++;
 868
 869                         notify_flc_waiters(t, o);
 870
 871                         return true;
 872                 }
 873         }
 874
 875         // The lock is either contented or fat.
 876         if (lockword.is_fat_lock()) {
 877                 lock_record_t* lr = lockword.get_fat_lock();
 878
 879                 // Check for recursive entering.
 880                 if (lr->owner == t) {
 881                         lr->count++;
 882                         return true;
 883                 }
 884
 885                 // Acquire the mutex of the lock record.
 886                 lock_record_enter(t, lr);
 887
 888                 // Sanity check.
 889                 assert(lr->count == 0);
 890                 return true;
 891         }
 892
 893         /****** inflation path ******/
 894
 895 #if defined(ENABLE_JVMTI)
 896         /* Monitor Contended Enter */
 897         jvmti_MonitorContendedEntering(false, o);
 898 #endif
 899
 900         sable_flc_waiting(lw_cache, t, o);
 901
 902 #if defined(ENABLE_JVMTI)
 903         /* Monitor Contended Entered */
 904         jvmti_MonitorContendedEntering(true, o);
 905 #endif
 906         goto retry;
 907 }
 908
 909
 910 /* lock_monitor_exit ***********************************************************
 911
 912    Decrement the counter of a (currently owned) monitor. If the counter
 913    reaches zero, release the monitor.
 914
 915    If the current thread is not the owner of the monitor, an
 916    IllegalMonitorState exception is thrown.
 917
 918    IN:
 919       t............the current thread
 920           o............the object of which to exit the monitor
 921
 922    RETURN VALUE:
 923       true.........everything ok,
 924           false........an exception has been thrown
 925
 926 *******************************************************************************/
 927
 928 bool lock_monitor_exit(java_handle_t* o)
 929 {
 930         // This function is inside a critical section.
 931         GCCriticalSection cs;
 932
 933         if (o == NULL) {
 934                 exceptions_throw_nullpointerexception();
 935                 return false;
 936         }
 937
 938         threadobject* t = thread_get_current();
 939
 940         uintptr_t thinlock = t->thinlock;
 941
 942         // We don't have to worry about stale values here, as any stale
 943         // value will indicate that we don't own the lock.
 944         uintptr_t *lw_ptr = lock_lockword_get(o);
 945         uintptr_t lw_cache = *lw_ptr;
 946         Lockword lockword(lw_cache);
 947
 948         // Most common case: we release a thin lock that we hold once.
 949         if (lockword.get_thin_lock() == thinlock) {
 950                 // Memory barrier for Java Memory Model.
 951                 Atomic::write_memory_barrier();
 952                 Lockword(*lw_ptr).unlock();
 953                 // Memory barrier for FLC bit testing.
 954                 Atomic::memory_barrier();
 955
 956                 /* check if there has been a flat lock contention on this object */
 957
 958                 if (t->flc_bit) {
 959                         DEBUGLOCKS(("thread %d saw flc bit", t->index));
 960
 961                         /* there has been a contention on this thin lock */
 962                         notify_flc_waiters(t, o);
 963                 }
 964
 965                 return true;
 966         }
 967
 968         // Next common case: we release a recursive lock, count > 0.
 969         if (lockword.get_thin_lock_without_count() == thinlock) {
 970                 Lockword(*lw_ptr).decrease_thin_lock_count();
 971                 return true;
 972         }
 973
 974         // Either the lock is fat, or we don't hold it at all.
 975         if (lockword.is_fat_lock()) {
 976                 lock_record_t* lr = lockword.get_fat_lock();
 977
 978                 // Check if we own this monitor.
 979                 // NOTE: We don't have to worry about stale values here, as
 980                 // any stale value will be != t and thus fail this check.
 981                 if (lr->owner != t) {
 982                         exceptions_throw_illegalmonitorstateexception();
 983                         return false;
 984                 }
 985
 986                 /* { the current thread `t` owns the lock record `lr` on object `o` } */
 987
 988                 if (lr->count != 0) {
 989                         // We had locked this one recursively.  Just decrement, it
 990                         // will still be locked.
 991                         lr->count--;
 992                         return true;
 993                 }
 994
 995                 // Unlock this lock record.
 996                 lock_record_exit(t, lr);
 997                 return true;
 998         }
 999
1000         // Legal thin lock cases have been handled above, so this is an
1001         // error.
1002         exceptions_throw_illegalmonitorstateexception();
1003
1004         return false;
1005 }
1006
1007
1008 /* lock_record_add_waiter ******************************************************
1009
1010    Add a thread to the list of waiting threads of a lock record.
1011
1012    IN:
1013       lr...........the lock record
1014       thread.......the thread to add
1015
1016 *******************************************************************************/
1017
1018 static void lock_record_add_waiter(lock_record_t *lr, threadobject* t)
1019 {
1020         // Add the thread as last entry to waiters list.
1021         lr->waiters->push_back(t);
1022
1023 #if defined(ENABLE_STATISTICS)
1024         if (opt_stat)
1025                 size_lock_waiter += sizeof(threadobject*);
1026 #endif
1027 }
1028
1029
1030 /* lock_record_remove_waiter ***************************************************
1031
1032    Remove a thread from the list of waiting threads of a lock record.
1033
1034    IN:
1035       lr...........the lock record
1036       t............the current thread
1037
1038    PRE-CONDITION:
1039       The current thread must be the owner of the lock record.
1040
1041 *******************************************************************************/
1042
1043 static void lock_record_remove_waiter(lock_record_t *lr, threadobject* t)
1044 {
1045         // Remove the thread from the waiters.
1046         lr->waiters->remove(t);
1047
1048 #if defined(ENABLE_STATISTICS)
1049         if (opt_stat)
1050                 size_lock_waiter -= sizeof(threadobject*);
1051 #endif
1052 }
1053
1054
1055 /* lock_record_wait ************************************************************
1056
1057    Wait on a lock record for a given (maximum) amount of time.
1058
1059    IN:
1060       t............the current thread
1061           lr...........the lock record
1062           millis.......milliseconds of timeout
1063           nanos........nanoseconds of timeout
1064
1065    RETURN VALUE:
1066       true.........we have been interrupted,
1067       false........everything ok
1068
1069    PRE-CONDITION:
1070       The current thread must be the owner of the lock record.
1071           This is NOT checked by this function!
1072
1073 *******************************************************************************/
1074
1075 static bool lock_record_wait(threadobject *thread, lock_record_t *lr, s8 millis, s4 nanos)
1076 {
1077         s4   lockcount;
1078         bool wasinterrupted = false;
1079
1080         DEBUGLOCKS(("[lock_record_wait  : lr=%p, t=%p, millis=%lld, nanos=%d]",
1081                                 lr, thread, millis, nanos));
1082
1083         /* { the thread t owns the fat lock record lr on the object o } */
1084
1085         /* register us as waiter for this object */
1086
1087         lock_record_add_waiter(lr, thread);
1088
1089         /* remember the old lock count */
1090
1091         lockcount = lr->count;
1092
1093         /* unlock this record */
1094
1095         lr->count = 0;
1096         lock_record_exit(thread, lr);
1097
1098         /* wait until notified/interrupted/timed out */
1099
1100         threads_wait_with_timeout_relative(thread, millis, nanos);
1101
1102         /* re-enter the monitor */
1103
1104         lock_record_enter(thread, lr);
1105
1106         /* remove us from the list of waiting threads */
1107
1108         lock_record_remove_waiter(lr, thread);
1109
1110         /* restore the old lock count */
1111
1112         lr->count = lockcount;
1113
1114         /* We can only be signaled OR interrupted, not both. If both flags
1115            are set, reset only signaled and leave the thread in
1116            interrupted state. Otherwise, clear both. */
1117
1118         if (!thread->signaled) {
1119                 wasinterrupted = thread->interrupted;
1120                 thread->interrupted = false;
1121         }
1122
1123         thread->signaled = false;
1124
1125         /* return if we have been interrupted */
1126
1127         return wasinterrupted;
1128 }
1129
1130
1131 /* lock_monitor_wait ***********************************************************
1132
1133    Wait on an object for a given (maximum) amount of time.
1134
1135    IN:
1136       t............the current thread
1137           o............the object
1138           millis.......milliseconds of timeout
1139           nanos........nanoseconds of timeout
1140
1141    PRE-CONDITION:
1142       The current thread must be the owner of the object's monitor.
1143
1144 *******************************************************************************/
1145
1146 static void lock_monitor_wait(threadobject *t, java_handle_t *o, s8 millis, s4 nanos)
1147 {
1148         lock_record_t *lr;
1149
1150         uintptr_t *lw_ptr = lock_lockword_get(o);
1151         uintptr_t lw_cache = *lw_ptr;
1152         Lockword lockword(lw_cache);
1153
1154         // Check if we own this monitor.
1155         // NOTE: We don't have to worry about stale values here, as any
1156         // stale value will fail this check.
1157         if (lockword.is_fat_lock()) {
1158                 lr = lockword.get_fat_lock();
1159
1160                 if (lr->owner != t) {
1161                         exceptions_throw_illegalmonitorstateexception();
1162                         return;
1163                 }
1164         }
1165         else {
1166                 // It's a thin lock.
1167                 if (lockword.get_thin_lock_without_count() != t->thinlock) {
1168                         exceptions_throw_illegalmonitorstateexception();
1169                         return;
1170                 }
1171
1172                 // Get the lock-record.
1173                 lr = lock_hashtable_get(o);
1174                 lock_record_enter(t, lr);
1175
1176                 // Inflate this lock.
1177                 Lockword(*lw_ptr).inflate(lr);
1178
1179                 notify_flc_waiters(t, o);
1180         }
1181
1182         /* { the thread t owns the fat lock record lr on the object o } */
1183
1184         if (lock_record_wait(t, lr, millis, nanos))
1185                 exceptions_throw_interruptedexception();
1186 }
1187
1188
1189 /* lock_record_notify **********************************************************
1190
1191    Notify one thread or all threads waiting on the given lock record.
1192
1193    IN:
1194       t............the current thread
1195           lr...........the lock record
1196           one..........if true, only notify one thread
1197
1198    PRE-CONDITION:
1199       The current thread must be the owner of the lock record.
1200           This is NOT checked by this function!
1201
1202 *******************************************************************************/
1203
1204 static void lock_record_notify(threadobject *t, lock_record_t *lr, bool one)
1205 {
1206 #if defined(ENABLE_GC_CACAO)
1207         // Sanity check.
1208         assert(GCCriticalSection::inside() == false);
1209 #endif
1210
1211         // { The thread t owns the fat lock record lr on the object o }
1212
1213         for (List<threadobject*>::iterator it = lr->waiters->begin(); it != lr->waiters->end(); it++) {
1214                 threadobject* waiter = *it;
1215
1216                 // We must skip threads which have already been notified. They
1217                 // will remove themselves from the list.
1218                 if (waiter->signaled)
1219                         continue;
1220
1221                 // Enter the wait-mutex.
1222                 waiter->waitmutex->lock();
1223
1224                 DEBUGLOCKS(("[lock_record_notify: lr=%p, t=%p, waitingthread=%p, one=%d]", lr, t, waiter, one));
1225
1226                 // Signal the waiter.
1227                 waiter->waitcond->signal();
1228
1229                 // Mark the thread as signaled.
1230                 waiter->signaled = true;
1231
1232                 // Leave the wait-mutex.
1233                 waiter->waitmutex->unlock();
1234
1235                 // If we should only wake one thread, we are done.
1236                 if (one)
1237                         break;
1238         }
1239 }
1240
1241
1242 /* lock_monitor_notify *********************************************************
1243
1244    Notify one thread or all threads waiting on the given object.
1245
1246    IN:
1247       t............the current thread
1248           o............the object
1249           one..........if true, only notify one thread
1250
1251    PRE-CONDITION:
1252       The current thread must be the owner of the object's monitor.
1253
1254 *******************************************************************************/
1255
1256 static void lock_monitor_notify(threadobject *t, java_handle_t *o, bool one)
1257 {
1258         lock_record_t* lr = NULL;
1259
1260         {
1261                 // This scope is inside a critical section.
1262                 GCCriticalSection cs;
1263
1264                 uintptr_t lw_cache = *lock_lockword_get(o);
1265                 Lockword lockword(lw_cache);
1266
1267                 // Check if we own this monitor.
1268                 // NOTE: We don't have to worry about stale values here, as any
1269                 // stale value will fail this check.
1270
1271                 if (lockword.is_fat_lock()) {
1272                         lr = lockword.get_fat_lock();
1273
1274                         if (lr->owner != t) {
1275                                 exceptions_throw_illegalmonitorstateexception();
1276                                 return;
1277                         }
1278                 }
1279                 else {
1280                         // It's a thin lock.
1281                         if (lockword.get_thin_lock_without_count() != t->thinlock) {
1282                                 exceptions_throw_illegalmonitorstateexception();
1283                                 return;
1284                         }
1285
1286                         // No thread can wait on a thin lock, so there's nothing to do.
1287                         return;
1288                 }
1289         }
1290
1291         // { The thread t owns the fat lock record lr on the object o }
1292         lock_record_notify(t, lr, one);
1293 }
1294
1295
1296
1297 /*============================================================================*/
1298 /* INQUIRY FUNCIONS                                                           */
1299 /*============================================================================*/
1300
1301
1302 /* lock_is_held_by_current_thread **********************************************
1303
1304    Return true if the current thread owns the monitor of the given object.
1305
1306    IN:
1307           o............the object
1308
1309    RETURN VALUE:
1310       true, if the current thread holds the lock of this object.
1311
1312 *******************************************************************************/
1313
1314 bool lock_is_held_by_current_thread(java_handle_t *o)
1315 {
1316         // This function is inside a critical section.
1317         GCCriticalSection cs;
1318
1319         // Check if we own this monitor.
1320         // NOTE: We don't have to worry about stale values here, as any
1321         // stale value will fail this check.
1322         threadobject* t = thread_get_current();
1323         uintptr_t lw_cache = *lock_lockword_get(o);
1324         Lockword lockword(lw_cache);
1325
1326         if (lockword.is_fat_lock()) {
1327                 // It's a fat lock.
1328                 lock_record_t* lr = lockword.get_fat_lock();
1329                 return (lr->owner == t);
1330         }
1331         else {
1332                 // It's a thin lock.
1333                 return (lockword.get_thin_lock_without_count() == t->thinlock);
1334         }
1335 }
1336
1337
1338
1339 /*============================================================================*/
1340 /* WRAPPERS FOR OPERATIONS ON THE CURRENT THREAD                              */
1341 /*============================================================================*/
1342
1343
1344 /* lock_wait_for_object ********************************************************
1345
1346    Wait for the given object.
1347
1348    IN:
1349           o............the object
1350           millis.......milliseconds to wait
1351           nanos........nanoseconds to wait
1352
1353 *******************************************************************************/
1354
1355 void lock_wait_for_object(java_handle_t *o, s8 millis, s4 nanos)
1356 {
1357         threadobject *thread;
1358
1359         thread = THREADOBJECT;
1360
1361         lock_monitor_wait(thread, o, millis, nanos);
1362 }
1363
1364
1365 /* lock_notify_object **********************************************************
1366
1367    Notify one thread waiting on the given object.
1368
1369    IN:
1370           o............the object
1371
1372 *******************************************************************************/
1373
1374 void lock_notify_object(java_handle_t *o)
1375 {
1376         threadobject *thread;
1377
1378         thread = THREADOBJECT;
1379
1380         lock_monitor_notify(thread, o, true);
1381 }
1382
1383
1384 /* lock_notify_all_object ******************************************************
1385
1386    Notify all threads waiting on the given object.
1387
1388    IN:
1389           o............the object
1390
1391 *******************************************************************************/
1392
1393 void lock_notify_all_object(java_handle_t *o)
1394 {
1395         threadobject *thread;
1396
1397         thread = THREADOBJECT;
1398
1399         lock_monitor_notify(thread, o, false);
1400 }
1401
1402
1403 /*
1404  * These are local overrides for various environment variables in Emacs.
1405  * Please do not remove this and leave it at the end of the file, where
1406  * Emacs will automagically detect them.
1407  * ---------------------------------------------------------------------
1408  * Local variables:
1409  * mode: c++
1410  * indent-tabs-mode: t
1411  * c-basic-offset: 4
1412  * tab-width: 4
1413  * End:
1414  * vim:noexpandtab:sw=4:ts=4:
1415  */