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