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