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