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