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