src/threads/native/lock.c

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