src/threads/native/lock.c

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