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 /* MACROS                                                                     */
  66 /******************************************************************************/
  67
  68 /* number of lock records in the first pool allocated for a thread */
  69 #define INITIALLOCKRECORDS 8
  70
  71
  72 /* CAUTION: oldvalue is evaluated twice! */
  73 #define COMPARE_AND_SWAP_SUCCEEDS(address, oldvalue, newvalue) \
  74         (compare_and_swap((long *)(address), (long)(oldvalue), (long)(newvalue)) == (long)(oldvalue))
  75
  76
  77 /******************************************************************************/
  78 /* GLOBAL VARIABLES                                                           */
  79 /******************************************************************************/
  80
  81 /* global lock record pool list header */
  82 lock_record_pool_t *lock_global_pool;
  83
  84 /* mutex for synchronizing access to the global pool */
  85 pthread_mutex_t lock_global_pool_lock;
  86
  87
  88
  89 /*============================================================================*/
  90 /* INITIALIZATION OF DATA STRUCTURES                                          */
  91 /*============================================================================*/
  92
  93
  94 /* lock_init *******************************************************************
  95
  96    Initialize global data for locking.
  97
  98 *******************************************************************************/
  99
 100 void lock_init(void)
 101 {
 102         pthread_mutex_init(&lock_global_pool_lock, NULL);
 103 }
 104
 105
 106 /* lock_record_init ************************************************************
 107
 108    Initialize a lock record.
 109
 110    IN:
 111       r............the lock record to initialize
 112           t............will become the owner
 113
 114 *******************************************************************************/
 115
 116 static void lock_record_init(lock_record_t *r, threadobject *t)
 117 {
 118         r->owner = NULL;
 119         r->count = 0;
 120         r->waiters = NULL;
 121
 122 #if !defined(NDEBUG)
 123         r->nextfree = NULL;
 124 #endif
 125
 126         pthread_mutex_init(&(r->mutex), NULL);
 127 }
 128
 129
 130 /* lock_init_execution_env *****************************************************
 131
 132    Initialize the execution environment for a thread.
 133
 134    IN:
 135       thread.......the thread
 136
 137 *******************************************************************************/
 138
 139 void lock_init_execution_env(threadobject *thread)
 140 {
 141         thread->ee.firstfree = NULL;
 142         thread->ee.lockrecordpools = NULL;
 143         thread->ee.lockrecordcount = 0;
 144 }
 145
 146
 147
 148 /*============================================================================*/
 149 /* LOCK RECORD MANAGEMENT                                                     */
 150 /*============================================================================*/
 151
 152
 153 /* lock_record_alloc_new_pool **************************************************
 154
 155    Get a new lock record pool from the memory allocator.
 156
 157    IN:
 158       thread.......the thread that will own the lock records
 159           size.........number of lock records in the pool to allocate
 160
 161    RETURN VALUE:
 162       the new lock record pool, with initialized lock records
 163
 164 *******************************************************************************/
 165
 166 static lock_record_pool_t *lock_record_alloc_new_pool(threadobject *thread, int size)
 167 {
 168         int i;
 169         lock_record_pool_t *pool;
 170
 171         /* get the pool from the memory allocator */
 172
 173         pool = mem_alloc(sizeof(lock_record_pool_header_t)
 174                                    + sizeof(lock_record_t) * size);
 175
 176         /* initialize the pool header */
 177
 178         pool->header.size = size;
 179
 180         /* initialize the individual lock records */
 181
 182         for (i=0; i<size; i++) {
 183                 lock_record_init(&pool->lr[i], thread);
 184
 185                 pool->lr[i].nextfree = &pool->lr[i+1];
 186         }
 187
 188         /* terminate free list */
 189
 190         pool->lr[i-1].nextfree = NULL;
 191
 192         return pool;
 193 }
 194
 195
 196 /* lock_record_alloc_pool ******************************************************
 197
 198    Allocate a lock record pool. The pool is either taken from the global free
 199    list or requested from the memory allocator.
 200
 201    IN:
 202       thread.......the thread that will own the lock records
 203           size.........number of lock records in the pool to allocate
 204
 205    RETURN VALUE:
 206       the new lock record pool, with initialized lock records
 207
 208 *******************************************************************************/
 209
 210 static lock_record_pool_t *lock_record_alloc_pool(threadobject *t, int size)
 211 {
 212         pthread_mutex_lock(&lock_global_pool_lock);
 213
 214         if (lock_global_pool) {
 215                 int i;
 216                 lock_record_pool_t *pool;
 217
 218                 /* pop a pool from the global freelist */
 219
 220                 pool = lock_global_pool;
 221                 lock_global_pool = pool->header.next;
 222
 223                 pthread_mutex_unlock(&lock_global_pool_lock);
 224
 225                 /* re-initialize owner and freelist chaining */
 226
 227                 for (i=0; i < pool->header.size; i++) {
 228                         pool->lr[i].owner = NULL;
 229                         pool->lr[i].nextfree = &pool->lr[i+1];
 230                 }
 231                 pool->lr[i-1].nextfree = NULL;
 232
 233                 return pool;
 234         }
 235
 236         pthread_mutex_unlock(&lock_global_pool_lock);
 237
 238         /* we have to get a new pool from the allocator */
 239
 240         return lock_record_alloc_new_pool(t, size);
 241 }
 242
 243
 244 /* lock_record_free_pools ******************************************************
 245
 246    Free the lock record pools in the given linked list. The pools are inserted
 247    into the global freelist.
 248
 249    IN:
 250       pool.........list header
 251
 252 *******************************************************************************/
 253
 254 void lock_record_free_pools(lock_record_pool_t *pool)
 255 {
 256         lock_record_pool_header_t *last;
 257
 258         if (!pool)
 259                 return;
 260
 261         pthread_mutex_lock(&lock_global_pool_lock);
 262
 263         /* find the last pool in the list */
 264
 265         last = &pool->header;
 266         while (last->next)
 267                 last = &last->next->header;
 268
 269         /* chain it to the lock_global_pool freelist */
 270
 271         last->next = lock_global_pool;
 272
 273         /* insert the freed pools into the freelist */
 274
 275         lock_global_pool = pool;
 276
 277         pthread_mutex_unlock(&lock_global_pool_lock);
 278 }
 279
 280
 281 /* lock_record_alloc ***********************************************************
 282
 283    Allocate a lock record which is owned by the given thread.
 284
 285    IN:
 286       t............the thread
 287
 288 *******************************************************************************/
 289
 290 static lock_record_t *lock_record_alloc(threadobject *t)
 291 {
 292         lock_record_t *r;
 293
 294         assert(t);
 295         r = t->ee.firstfree;
 296
 297         if (!r) {
 298                 int poolsize;
 299                 lock_record_pool_t *pool;
 300
 301                 /* get a new pool */
 302
 303                 poolsize = t->ee.lockrecordcount ? t->ee.lockrecordcount * 2 : INITIALLOCKRECORDS;
 304                 pool = lock_record_alloc_pool(t, poolsize);
 305
 306                 /* add it to our per-thread pool list */
 307
 308                 pool->header.next = t->ee.lockrecordpools;
 309                 t->ee.lockrecordpools = pool;
 310                 t->ee.lockrecordcount += pool->header.size;
 311
 312                 /* take the first record from the pool */
 313                 r = &pool->lr[0];
 314         }
 315
 316         /* pop the record from the freelist */
 317
 318         t->ee.firstfree = r->nextfree;
 319 #ifndef NDEBUG
 320         r->nextfree = NULL; /* in order to find invalid uses of nextfree */
 321 #endif
 322         return r;
 323 }
 324
 325
 326 /* lock_record_recycle *********************************************************
 327
 328    Recycle the given lock record. It will be inserted in the appropriate
 329    free list.
 330
 331    IN:
 332       t............the owner
 333           r............lock record to recycle
 334
 335 *******************************************************************************/
 336
 337 static inline void lock_record_recycle(threadobject *t, lock_record_t *r)
 338 {
 339         assert(t);
 340         assert(r);
 341         assert(r->owner == NULL);
 342         assert(r->nextfree == NULL);
 343
 344         r->nextfree = t->ee.firstfree;
 345         t->ee.firstfree = r;
 346 }
 347
 348
 349
 350 /*============================================================================*/
 351 /* OBJECT LOCK INITIALIZATION                                                 */
 352 /*============================================================================*/
 353
 354
 355 /* lock_init_object_lock *******************************************************
 356
 357    Initialize the monitor pointer of the given object. The monitor gets
 358    initialized to an unlocked state.
 359
 360 *******************************************************************************/
 361
 362 void lock_init_object_lock(java_objectheader *o)
 363 {
 364         assert(o);
 365
 366         o->monitorPtr = NULL;
 367 }
 368
 369
 370 /* lock_get_initial_lock_word **************************************************
 371
 372    Returns the initial (unlocked) lock word. The pointer is
 373    required in the code generator to set up a virtual
 374    java_objectheader for code patch locking.
 375
 376 *******************************************************************************/
 377
 378 lock_record_t *lock_get_initial_lock_word(void)
 379 {
 380         return NULL;
 381 }
 382
 383
 384
 385 /*============================================================================*/
 386 /* LOCKING ALGORITHM                                                          */
 387 /*============================================================================*/
 388
 389
 390 /* lock_inflate ****************************************************************
 391
 392    Inflate the lock of the given object.
 393
 394    IN:
 395       t............the current thread
 396           o............the object of which to inflate the lock
 397
 398    RETURN VALUE:
 399       the new lock record of the object
 400
 401 *******************************************************************************/
 402
 403 static lock_record_t *lock_inflate(threadobject *t, java_objectheader *o)
 404 {
 405         lock_record_t *lr;
 406
 407         /* allocate a fat lock */
 408
 409         lr = lock_record_alloc(t);
 410
 411         /* We try to install this fat lock... */
 412
 413         if (COMPARE_AND_SWAP_SUCCEEDS(&(o->monitorPtr), NULL, lr))
 414                 return lr;
 415
 416         /* The CAS failed. That means another thread inflated the lock. */
 417         /* It won't change anymore, so we can read it in a relaxed way. */
 418
 419         lock_record_recycle(t, lr);
 420         return o->monitorPtr;
 421 }
 422
 423
 424 /* lock_monitor_enter **********************************************************
 425
 426    Acquire the monitor of the given object. If the current thread already
 427    owns the monitor, the lock counter is simply increased.
 428
 429    This function blocks until it can acquire the monitor.
 430
 431    IN:
 432       t............the current thread
 433           o............the object of which to enter the monitor
 434
 435    RETURN VALUE:
 436       the new lock record of the object when it has been entered
 437
 438 *******************************************************************************/
 439
 440 lock_record_t *lock_monitor_enter(threadobject *t, java_objectheader *o)
 441 {
 442         lock_record_t *lr;
 443
 444         /* get the lock record for this object       */
 445         /* inflate the lock if it is not already fat */
 446         if ((lr = o->monitorPtr) == NULL) {
 447                 lr = lock_inflate(t, o);
 448         }
 449
 450         /* check for recursive entering */
 451         /* We don't have to worry about stale values here, as any stale value */
 452         /* will be != t and thus fail this check.                             */
 453         if (lr->owner == t) {
 454                 lr->count++;
 455                 return lr;
 456         }
 457
 458         /* acquire the mutex of the lock record */
 459         pthread_mutex_lock(&(lr->mutex));
 460
 461         /* enter us as the owner */
 462         lr->owner = t;
 463
 464         assert(lr->count == 0);
 465
 466         return lr;
 467 }
 468
 469
 470 /* lock_monitor_exit *****************************************************************
 471
 472    Decrement the counter of a (currently owned) monitor. If the counter
 473    reaches zero, release the monitor.
 474
 475    If the current thread is not the owner of the monitor, an
 476    IllegalMonitorState exception is thrown.
 477
 478    IN:
 479       t............the current thread
 480           o............the object of which to exit the monitor
 481
 482    RETURN VALUE:
 483       true.........everything ok,
 484           false........an exception has been thrown
 485
 486 *******************************************************************************/
 487
 488 bool lock_monitor_exit(threadobject *t, java_objectheader *o)
 489 {
 490         lock_record_t *lr;
 491
 492         lr = o->monitorPtr;
 493
 494         /* check if we own this monitor */
 495         /* We don't have to worry about stale values here, as any stale value */
 496         /* will be != t and thus fail this check.                             */
 497
 498         if (!lr || lr->owner != t) {
 499                 *exceptionptr = new_illegalmonitorstateexception();
 500                 return false;
 501         }
 502
 503         /* { the current thread `t` owns the lock record `lr` on object `o` } */
 504
 505         if (lr->count != 0) {
 506                 /* we had locked this one recursively. just decrement, it will */
 507                 /* still be locked. */
 508                 lr->count--;
 509                 return true;
 510         }
 511
 512         /* unlock this lock record */
 513
 514         lr->owner = NULL;
 515         pthread_mutex_unlock(&(lr->mutex));
 516
 517         return true;
 518 }
 519
 520
 521 /* lock_record_remove_waiter *********************************************************
 522
 523    Remove a thread from the list of waiting threads of a lock record.
 524
 525    IN:
 526       lr...........the lock record
 527       t............the current thread
 528
 529    PRE-CONDITION:
 530       The current thread must be the owner of the lock record.
 531
 532 *******************************************************************************/
 533
 534 void lock_record_remove_waiter(lock_record_t *lr, threadobject *t)
 535 {
 536         lock_waiter_t **link;
 537         lock_waiter_t *w;
 538
 539         link = &(lr->waiters);
 540         while ((w = *link)) {
 541                 if (w->waiter == t) {
 542                         *link = w->next;
 543                         return;
 544                 }
 545
 546                 link = &(w->next);
 547         }
 548
 549         /* this should never happen */
 550         fprintf(stderr,"error: waiting thread not found in list of waiters\n");
 551         fflush(stderr);
 552         abort();
 553 }
 554
 555
 556 /* lock_monitor_wait *****************************************************************
 557
 558    Wait on an object for a given (maximum) amount of time.
 559
 560    IN:
 561       t............the current thread
 562           o............the object
 563           millis.......milliseconds of timeout
 564           nanos........nanoseconds of timeout
 565
 566    PRE-CONDITION:
 567       The current thread must be the owner of the object's monitor.
 568
 569 *******************************************************************************/
 570
 571 void lock_monitor_wait(threadobject *t, java_objectheader *o, s8 millis, s4 nanos)
 572 {
 573         lock_record_t *lr;
 574         lock_waiter_t *waiter;
 575         s4 lockcount;
 576         bool wasinterrupted;
 577
 578         lr = o->monitorPtr;
 579
 580         /* check if we own this monitor */
 581         /* We don't have to worry about stale values here, as any stale value */
 582         /* will be != t and thus fail this check.                             */
 583
 584         if (!lr || lr->owner != t) {
 585                 *exceptionptr = new_illegalmonitorstateexception();
 586                 return;
 587         }
 588
 589         /* { the thread t owns the lock record lr on the object o } */
 590
 591         /* register us as waiter for this object */
 592
 593         waiter = NEW(lock_waiter_t);
 594         waiter->waiter = t;
 595         waiter->next = lr->waiters;
 596         lr->waiters = waiter;
 597
 598         /* remember the old lock count */
 599
 600         lockcount = lr->count;
 601
 602         /* unlock this record */
 603
 604         lr->count = 0;
 605         lr->owner = NULL;
 606         pthread_mutex_unlock(&(lr->mutex));
 607
 608         /* wait until notified/interrupted/timed out */
 609
 610         wasinterrupted = threads_wait_with_timeout_relative(t, millis, nanos);
 611
 612         /* re-enter the monitor */
 613
 614         lr = lock_monitor_enter(t, o);
 615
 616         /* remove us from the list of waiting threads */
 617
 618         lock_record_remove_waiter(lr, t);
 619
 620         /* restore the old lock count */
 621
 622         lr->count = lockcount;
 623
 624         /* if we have been interrupted, throw the appropriate exception */
 625
 626         if (wasinterrupted)
 627                 *exceptionptr = new_exception(string_java_lang_InterruptedException);
 628 }
 629
 630
 631 /* lock_monitor_notify **************************************************************
 632
 633    Notify one thread or all threads waiting on the given object.
 634
 635    IN:
 636       t............the current thread
 637           o............the object
 638           one..........if true, only notify one thread
 639
 640    PRE-CONDITION:
 641       The current thread must be the owner of the object's monitor.
 642
 643 *******************************************************************************/
 644
 645 static void lock_monitor_notify(threadobject *t, java_objectheader *o, bool one)
 646 {
 647         lock_record_t *lr;
 648         lock_waiter_t *waiter;
 649         threadobject *waitingthread;
 650
 651         lr = o->monitorPtr;
 652
 653         /* check if we own this monitor */
 654         /* We don't have to worry about stale values here, as any stale value */
 655         /* will be != t and thus fail this check.                             */
 656
 657         if (!lr || lr->owner != t) {
 658                 *exceptionptr = new_illegalmonitorstateexception();
 659                 return;
 660         }
 661
 662         /* { the thread t owns the lock record lr on the object o } */
 663
 664         /* for each waiter: */
 665
 666         for (waiter = lr->waiters; waiter; waiter = waiter->next) {
 667
 668                 /* signal the waiting thread */
 669
 670                 waitingthread = waiter->waiter;
 671
 672                 pthread_mutex_lock(&waitingthread->waitmutex);
 673                 if (waitingthread->sleeping)
 674                         pthread_cond_signal(&waitingthread->waitcond);
 675                 waitingthread->signaled = true;
 676                 pthread_mutex_unlock(&waitingthread->waitmutex);
 677
 678                 /* if we should only wake one, we are done */
 679
 680                 if (one)
 681                         break;
 682         }
 683 }
 684
 685
 686
 687 /*============================================================================*/
 688 /* INQUIRY FUNCIONS                                                           */
 689 /*============================================================================*/
 690
 691
 692 /* lock_does_thread_hold_lock **************************************************
 693
 694    Return true if the given thread owns the monitor of the given object.
 695
 696    IN:
 697       t............the thread
 698           o............the object
 699
 700    RETURN VALUE:
 701       true, if the thread is locking the object
 702
 703 *******************************************************************************/
 704
 705 bool lock_does_thread_hold_lock(threadobject *t, java_objectheader *o)
 706 {
 707         lock_record_t *lr;
 708
 709         lr = o->monitorPtr;
 710
 711         return (lr && lr->owner == t);
 712 }
 713
 714
 715
 716 /*============================================================================*/
 717 /* WRAPPERS FOR OPERATIONS ON THE CURRENT THREAD                              */
 718 /*============================================================================*/
 719
 720
 721 /* lock_wait_for_object ********************************************************
 722
 723    Wait for the given object.
 724
 725    IN:
 726           o............the object
 727           millis.......milliseconds to wait
 728           nanos........nanoseconds to wait
 729
 730 *******************************************************************************/
 731
 732 void lock_wait_for_object(java_objectheader *o, s8 millis, s4 nanos)
 733 {
 734         threadobject *t = (threadobject*) THREADOBJECT;
 735         lock_monitor_wait(t, o, millis, nanos);
 736 }
 737
 738
 739 /* lock_notify_object **********************************************************
 740
 741    Notify one thread waiting on the given object.
 742
 743    IN:
 744           o............the object
 745
 746 *******************************************************************************/
 747
 748 void lock_notify_object(java_objectheader *o)
 749 {
 750         threadobject *t = (threadobject*) THREADOBJECT;
 751         lock_monitor_notify(t, o, true);
 752 }
 753
 754
 755 /* lock_notify_all_object ******************************************************
 756
 757    Notify all threads waiting on the given object.
 758
 759    IN:
 760           o............the object
 761
 762 *******************************************************************************/
 763
 764 void lock_notify_all_object(java_objectheader *o)
 765 {
 766         threadobject *t = (threadobject*) THREADOBJECT;
 767         lock_monitor_notify(t, o, false);
 768 }
 769
 770 /*
 771  * These are local overrides for various environment variables in Emacs.
 772  * Please do not remove this and leave it at the end of the file, where
 773  * Emacs will automagically detect them.
 774  * ---------------------------------------------------------------------
 775  * Local variables:
 776  * mode: c
 777  * indent-tabs-mode: t
 778  * c-basic-offset: 4
 779  * tab-width: 4
 780  * End:
 781  * vim:noexpandtab:sw=4:ts=4:
 782  */