src/lock.c

   1 /*
   2  * Copyright (C) 2003, 2004, 2005, 2006, 2007
   3  * Robert Lougher <rob@lougher.org.uk>.
   4  *
   5  * This file is part of JamVM.
   6  *
   7  * This program is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation; either version 2,
  10  * or (at your option) any later version.
  11  *
  12  * This program is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program; if not, write to the Free Software
  19  * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  20  */
  21
  22 #include <stdio.h>
  23 #include <string.h>
  24 #include <errno.h>
  25 #include <stdlib.h>
  26 #include <sys/time.h>
  27 #include <limits.h>
  28
  29 #include "jam.h"
  30 #include "thread.h"
  31 #include "hash.h"
  32 #include "alloc.h"
  33 #include "lock.h"
  34
  35 /* Trace lock operations and inflation/deflation */
  36 #ifdef TRACELOCK
  37 #define TRACE(fmt, ...) jam_printf(fmt, ## __VA_ARGS__)
  38 #else
  39 #define TRACE(fmt, ...)
  40 #endif
  41
  42 #define UN_USED -1
  43
  44 #define HASHTABSZE 1<<5
  45 #define PREPARE(obj) allocMonitor(obj)
  46 #define HASH(obj) (getObjectHashcode(obj) >> LOG_OBJECT_GRAIN)
  47 #define COMPARE(obj, mon, hash1, hash2) hash1 == hash2 && mon->obj == obj
  48 #define FOUND(ptr)                                          \
  49 ({                                                          \
  50      LOCKWORD_COMPARE_AND_SWAP(&ptr->entering, UN_USED, 0); \
  51      ptr;                                                   \
  52 })
  53
  54 /* lockword format in "thin" mode
  55   31                                         0
  56    -------------------------------------------
  57   |              thread ID          | count |0|
  58    -------------------------------------------
  59                                              ^ shape bit
  60
  61   lockword format in "fat" mode
  62   31                                         0
  63    -------------------------------------------
  64   |                 Monitor*                |1|
  65    -------------------------------------------
  66                                              ^ shape bit
  67 */
  68
  69 #define SHAPE_BIT   0x1
  70 #define COUNT_SIZE  8
  71 #define COUNT_SHIFT 1
  72 #define COUNT_MASK  (((1<<COUNT_SIZE)-1)<<COUNT_SHIFT)
  73
  74 #define TID_SHIFT   (COUNT_SIZE+COUNT_SHIFT)
  75 #define TID_SIZE    (32-TID_SHIFT)
  76 #define TID_MASK    (((1<<TID_SIZE)-1)<<TID_SHIFT)
  77
  78 #define SCAVENGE(ptr)                                           \
  79 ({                                                              \
  80     Monitor *mon = (Monitor *)ptr;                              \
  81     char res = LOCKWORD_READ(&mon->entering) == UN_USED;        \
  82     if(res) {                                                   \
  83         TRACE("Scavenging monitor %p (obj %p)", mon, mon->obj); \
  84         mon->next = mon_free_list;                              \
  85         mon_free_list = mon;                                    \
  86     }                                                           \
  87     res;                                                        \
  88 })
  89
  90 static Monitor *mon_free_list = NULL;
  91 static HashTable mon_cache;
  92
  93 void monitorInit(Monitor *mon) {
  94     memset(mon, 0, sizeof(Monitor));
  95     pthread_mutex_init(&mon->lock, NULL);
  96 }
  97
  98 void waitSetAppend(Monitor *mon, Thread *thread) {
  99     if(mon->wait_set == NULL)
 100         mon->wait_set = thread->wait_prev = thread;
 101
 102     thread->wait_next = mon->wait_set;
 103     thread->wait_prev = mon->wait_set->wait_prev;
 104     thread->wait_prev->wait_next = mon->wait_set->wait_prev = thread;
 105
 106     thread->wait_id = mon->wait_count++;
 107 }
 108
 109 void waitSetUnlinkThread(Monitor *mon, Thread *thread) {
 110     if(mon->wait_set == thread)
 111         if((mon->wait_set = mon->wait_set->wait_next) == thread)
 112             mon->wait_set = NULL;
 113
 114     thread->wait_prev->wait_next = thread->wait_next;
 115     thread->wait_next->wait_prev = thread->wait_prev;
 116     thread->wait_prev = thread->wait_next = NULL;
 117 }
 118
 119 Thread *waitSetSignalNext(Monitor *mon) {
 120     Thread *thread = mon->wait_set;
 121
 122     if(thread != NULL) {
 123         waitSetUnlinkThread(mon, thread);
 124         pthread_cond_signal(&thread->wait_cv);
 125
 126         thread->notify_id = mon->wait_count;
 127     }
 128
 129     return thread;
 130 }
 131
 132 void monitorLock(Monitor *mon, Thread *self) {
 133     if(mon->owner == self)
 134         mon->count++;
 135     else {
 136         if(pthread_mutex_trylock(&mon->lock)) {
 137             disableSuspend(self);
 138
 139             self->blocked_mon = mon;
 140             self->blocked_count++;
 141             self->state = BLOCKED;
 142
 143             pthread_mutex_lock(&mon->lock);
 144
 145             self->state = RUNNING;
 146             self->blocked_mon = NULL;
 147
 148             enableSuspend(self);
 149         }
 150         mon->owner = self;
 151     }
 152 }
 153
 154 int monitorTryLock(Monitor *mon, Thread *self) {
 155     if(mon->owner == self)
 156         mon->count++;
 157     else {
 158         if(pthread_mutex_trylock(&mon->lock))
 159             return FALSE;
 160         mon->owner = self;
 161     }
 162
 163     return TRUE;
 164 }
 165
 166 void monitorUnlock(Monitor *mon, Thread *self) {
 167     if(mon->owner == self) {
 168         if(mon->count == 0) {
 169             mon->owner = NULL;
 170             pthread_mutex_unlock(&mon->lock);
 171         } else
 172             mon->count--;
 173     }
 174 }
 175
 176 int monitorWait0(Monitor *mon, Thread *self, long long ms, int ns, int locked) {
 177     char timed = (ms != 0) || (ns != 0);
 178     char interrupted = FALSE;
 179     char timeout = FALSE;
 180     struct timespec ts;
 181     int old_count;
 182
 183     if(mon->owner != self)
 184         return FALSE;
 185
 186     /* We own the monitor */
 187
 188     disableSuspend(self);
 189
 190     /* Unlock the monitor.  As it could be recursively
 191        locked remember the recursion count */
 192     old_count = mon->count;
 193     mon->count = 0;
 194     mon->owner = NULL;
 195
 196     /* Counter used in thin-lock deflation */
 197     mon->in_wait++;
 198
 199     self->wait_mon = mon;
 200
 201     if(timed) {
 202         struct timeval tv;
 203         long long seconds;
 204
 205         gettimeofday(&tv, 0);
 206
 207         seconds = tv.tv_sec + ms/1000;
 208         ts.tv_nsec = (tv.tv_usec + ((ms%1000)*1000))*1000 + ns;
 209
 210         if(ts.tv_nsec > 999999999L) {
 211             seconds++;
 212             ts.tv_nsec -= 1000000000L;
 213         }
 214
 215         /* If the number of seconds is too large just set
 216            it to the max value instead of truncating.
 217            Depending on result, we may not wait at all */
 218        ts.tv_sec = seconds > LONG_MAX ? LONG_MAX : seconds;
 219
 220        self->state = TIMED_WAITING;
 221     } else
 222        self->state = locked ? BLOCKED : WAITING;
 223
 224     if(self->interrupted && !locked)
 225         interrupted = TRUE;
 226     else {
 227         if(locked)
 228             self->blocked_count++;
 229         else
 230             self->waited_count++;
 231
 232         self->interrupting = FALSE;
 233
 234         /* Add the thread onto the end of the wait set */
 235         waitSetAppend(mon, self);
 236
 237         while(self->wait_next != NULL && !self->interrupting)
 238             if(timed) {
 239                 if((timeout = (pthread_cond_timedwait(&self->wait_cv, &mon->lock, &ts) == ETIMEDOUT)))
 240                     break;
 241
 242                 /* On Linux/i386 systems using LinuxThreads, pthread_cond_timedwait is
 243                  * implemented using sigjmp/longjmp.  This resets the fpu control word
 244                  * back to 64-bit precision.  The macro is empty for sane platforms. */
 245                 FPU_HACK;
 246
 247             } else
 248                 pthread_cond_wait(&self->wait_cv, &mon->lock);
 249     }
 250
 251     /* If we've been interrupted or timed-out, we will not have been
 252        removed from the wait set.  If we have, we must have been
 253        notified afterwards.  In this case, the notify has been lost,
 254        and we must signal another thread */
 255
 256     if(self->interrupting || timeout) {
 257         /* An interrupt after a timeout remains pending */
 258         interrupted = !(locked || timeout);
 259
 260         if(self->wait_next != NULL)
 261             waitSetUnlinkThread(mon, self);
 262         else {
 263             /* Notify lost.  Signal another thread only if it
 264                was on the wait set at the time of the notify */
 265             if(mon->wait_set != NULL && mon->wait_set->wait_id < self->notify_id) {
 266                 Thread *thread = waitSetSignalNext(mon);
 267                 thread->notify_id = self->notify_id;
 268             }
 269         }
 270     }
 271
 272     self->state = RUNNING;
 273     self->wait_mon = NULL;
 274
 275    /* Restore the monitor owner and recursion count */
 276
 277     mon->owner = self;
 278     mon->count = old_count;
 279     mon->in_wait--;
 280
 281     enableSuspend(self);
 282
 283     if(interrupted) {
 284         self->interrupted = FALSE;
 285         signalException("java/lang/InterruptedException", NULL);
 286     }
 287
 288     return TRUE;
 289 }
 290
 291 int monitorNotify(Monitor *mon, Thread *self) {
 292     if(mon->owner != self)
 293         return FALSE;
 294
 295     /* Signal the first thread in the wait set.  This
 296        is the thread which has been waiting the longest */
 297     waitSetSignalNext(mon);
 298
 299     return TRUE;
 300 }
 301
 302 int monitorNotifyAll(Monitor *mon, Thread *self) {
 303     if(mon->owner != self)
 304         return FALSE;
 305
 306     /* Signal all threads in the wait set */
 307     while(waitSetSignalNext(mon) != NULL);
 308
 309     return TRUE;
 310 }
 311
 312 Monitor *allocMonitor(Object *obj) {
 313     Monitor *mon;
 314
 315     if(mon_free_list != NULL) {
 316         mon = mon_free_list;
 317         mon_free_list = mon->next;
 318     } else {
 319         mon = (Monitor *)sysMalloc(sizeof(Monitor));
 320         monitorInit(mon);
 321     }
 322     mon->obj = obj;
 323     /* No need to wrap in LOCKWORD_WRITE as no thread should
 324      * be modifying it when it's on the free list */
 325     mon->entering = 0;
 326     return mon;
 327 }
 328
 329 Monitor *findMonitor(Object *obj) {
 330     uintptr_t lockword = LOCKWORD_READ(&obj->lock);
 331
 332     if(lockword & SHAPE_BIT)
 333         return (Monitor*) (lockword & ~SHAPE_BIT);
 334     else {
 335         Monitor *mon;
 336         /* Add if absent, scavenge, locked */
 337         findHashEntry(mon_cache, obj, mon, TRUE, TRUE, TRUE);
 338         return mon;
 339     }
 340 }
 341
 342 static void inflate(Object *obj, Monitor *mon, Thread *self) {
 343     TRACE("Thread %p is inflating obj %p...\n", self, obj);
 344     clearFlcBit(obj);
 345     monitorNotifyAll(mon, self);
 346     LOCKWORD_WRITE(&obj->lock, (uintptr_t) mon | SHAPE_BIT);
 347 }
 348
 349 void objectLock(Object *obj) {
 350     Thread *self = threadSelf();
 351     uintptr_t thin_locked = self->id<<TID_SHIFT;
 352     uintptr_t entering, lockword;
 353     Monitor *mon;
 354
 355     TRACE("Thread %p lock on obj %p...\n", self, obj);
 356
 357     if(LOCKWORD_COMPARE_AND_SWAP(&obj->lock, 0, thin_locked)) {
 358         /* This barrier is not needed for the thin-locking implementation --
 359            it's a requirement of the Java memory model. */
 360         JMM_LOCK_MBARRIER();
 361         return;
 362     }
 363
 364     lockword = LOCKWORD_READ(&obj->lock);
 365     if((lockword & (TID_MASK|SHAPE_BIT)) == thin_locked) {
 366         int count = lockword & COUNT_MASK;
 367
 368         if(count < (((1<<COUNT_SIZE)-1)<<COUNT_SHIFT))
 369             LOCKWORD_WRITE(&obj->lock, lockword + (1<<COUNT_SHIFT));
 370         else {
 371             mon = findMonitor(obj);
 372             monitorLock(mon, self);
 373             inflate(obj, mon, self);
 374             mon->count = 1<<COUNT_SIZE;
 375         }
 376         return;
 377     }
 378
 379 try_again:
 380     mon = findMonitor(obj);
 381
 382 try_again2:
 383     if((entering = LOCKWORD_READ(&mon->entering)) == UN_USED)
 384         goto try_again;
 385
 386     if(!(LOCKWORD_COMPARE_AND_SWAP(&mon->entering, entering, entering+1)))
 387         goto try_again2;
 388
 389     if(mon->obj != obj) {
 390         while(entering = LOCKWORD_READ(&mon->entering),
 391                         !(LOCKWORD_COMPARE_AND_SWAP(&mon->entering, entering, entering-1)));
 392         goto try_again;
 393     }
 394
 395     monitorLock(mon, self);
 396
 397     while(entering = LOCKWORD_READ(&mon->entering),
 398                     !(LOCKWORD_COMPARE_AND_SWAP(&mon->entering, entering, entering-1)));
 399
 400     while((LOCKWORD_READ(&obj->lock) & SHAPE_BIT) == 0) {
 401         setFlcBit(obj);
 402
 403         if(LOCKWORD_COMPARE_AND_SWAP(&obj->lock, 0, thin_locked))
 404             inflate(obj, mon, self);
 405         else
 406             monitorWait0(mon, self, 0, 0, TRUE);
 407     }
 408 }
 409
 410 void objectUnlock(Object *obj) {
 411     Thread *self = threadSelf();
 412     uintptr_t lockword = LOCKWORD_READ(&obj->lock);
 413     uintptr_t thin_locked = self->id<<TID_SHIFT;
 414
 415     TRACE("Thread %p unlock on obj %p...\n", self, obj);
 416
 417     if(lockword == thin_locked) {
 418         /* This barrier is not needed for the thin-locking implementation --
 419            it's a requirement of the Java memory model. */
 420         JMM_UNLOCK_MBARRIER();
 421         LOCKWORD_WRITE(&obj->lock, 0);
 422
 423         /* Required by thin-locking mechanism. */
 424         UNLOCK_MBARRIER();
 425
 426 retry:
 427         if(testFlcBit(obj)) {
 428             Monitor *mon = findMonitor(obj);
 429
 430             if(!monitorTryLock(mon, self)) {
 431                 threadYield(self);
 432                 goto retry;
 433             }
 434
 435             if(testFlcBit(obj) && (mon->obj == obj))
 436                 monitorNotify(mon, self);
 437
 438             monitorUnlock(mon, self);
 439         }
 440     } else {
 441         if((lockword & (TID_MASK|SHAPE_BIT)) == thin_locked)
 442             LOCKWORD_WRITE(&obj->lock, lockword - (1<<COUNT_SHIFT));
 443         else
 444             if((lockword & SHAPE_BIT) != 0) {
 445                 Monitor *mon = (Monitor*) (lockword & ~SHAPE_BIT);
 446
 447                 if((mon->count == 0) && (LOCKWORD_READ(&mon->entering) == 0) &&
 448                                 (mon->in_wait == 0)) {
 449                     TRACE("Thread %p is deflating obj %p...\n", self, obj);
 450
 451                     /* This barrier is not needed for the thin-locking implementation --
 452                        it's a requirement of the Java memory model. */
 453                     JMM_UNLOCK_MBARRIER();
 454
 455                     LOCKWORD_WRITE(&obj->lock, 0);
 456                     LOCKWORD_COMPARE_AND_SWAP(&mon->entering, 0, UN_USED);
 457                 }
 458
 459                 monitorUnlock(mon, self);
 460             }
 461     }
 462 }
 463
 464 void objectWait(Object *obj, long long ms, int ns) {
 465     uintptr_t lockword = LOCKWORD_READ(&obj->lock);
 466     Thread *self = threadSelf();
 467     Monitor *mon;
 468
 469     TRACE("Thread %p Wait on obj %p...\n", self, obj);
 470
 471     if((lockword & SHAPE_BIT) == 0) {
 472         int tid = (lockword&TID_MASK)>>TID_SHIFT;
 473         if(tid == self->id) {
 474             mon = findMonitor(obj);
 475             monitorLock(mon, self);
 476             inflate(obj, mon, self);
 477             mon->count = (lockword&COUNT_MASK)>>COUNT_SHIFT;
 478         } else
 479             goto not_owner;
 480     } else
 481         mon = (Monitor*) (lockword & ~SHAPE_BIT);
 482
 483     if(monitorWait(mon, self, ms, ns))
 484         return;
 485
 486 not_owner:
 487     signalException("java/lang/IllegalMonitorStateException", "thread not owner");
 488 }
 489
 490 void objectNotify(Object *obj) {
 491     uintptr_t lockword = LOCKWORD_READ(&obj->lock);
 492     Thread *self = threadSelf();
 493
 494     TRACE("Thread %p Notify on obj %p...\n", self, obj);
 495
 496     if((lockword & SHAPE_BIT) == 0) {
 497         int tid = (lockword&TID_MASK)>>TID_SHIFT;
 498         if(tid == self->id)
 499             return;
 500     } else {
 501         Monitor *mon = (Monitor*) (lockword & ~SHAPE_BIT);
 502         if(monitorNotify(mon, self))
 503             return;
 504     }
 505
 506     signalException("java/lang/IllegalMonitorStateException", "thread not owner");
 507 }
 508
 509 void objectNotifyAll(Object *obj) {
 510     uintptr_t lockword = LOCKWORD_READ(&obj->lock);
 511     Thread *self = threadSelf();
 512
 513     TRACE("Thread %p NotifyAll on obj %p...\n", self, obj);
 514
 515     if((lockword & SHAPE_BIT) == 0) {
 516         int tid = (lockword&TID_MASK)>>TID_SHIFT;
 517         if(tid == self->id)
 518             return;
 519     } else {
 520         Monitor *mon = (Monitor*) (lockword & ~SHAPE_BIT);
 521         if(monitorNotifyAll(mon, self))
 522             return;
 523     }
 524
 525     signalException("java/lang/IllegalMonitorStateException", "thread not owner");
 526 }
 527
 528 int objectLockedByCurrent(Object *obj) {
 529     uintptr_t lockword = LOCKWORD_READ(&obj->lock);
 530     Thread *self = threadSelf();
 531
 532     if((lockword & SHAPE_BIT) == 0) {
 533         int tid = (lockword&TID_MASK)>>TID_SHIFT;
 534         if(tid == self->id)
 535             return TRUE;
 536     } else {
 537         Monitor *mon = (Monitor*) (lockword & ~SHAPE_BIT);
 538         if(mon->owner == self)
 539             return TRUE;
 540     }
 541     return FALSE;
 542 }
 543
 544 void initialiseMonitor() {
 545     /* Init hash table, create lock */
 546     initHashTable(mon_cache, HASHTABSZE, TRUE);
 547 }
 548
 549 /* Heap compaction support */
 550
 551 #define ITERATE(ptr) {               \
 552     Monitor *mon = (Monitor*)ptr;    \
 553     if(isMarked(mon->obj))           \
 554          threadReference(&mon->obj); \
 555 }
 556
 557 void threadMonitorCache() {
 558    hashIterate(mon_cache);
 559 }