* src/threads/native/threads.c: The Big Thread Cleanup. No functional changes,
[cacao.git] / 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
29    Changes: Christian Thalinger
30                         Edwin Steiner
31
32    $Id: threads.c 4903 2006-05-11 12:48:43Z edwin $
33
34 */
35
36
37 #include "config.h"
38
39 /* XXX cleanup these includes */
40
41 #include <stdlib.h>
42 #include <string.h>
43 #include <assert.h>
44 #include <sys/types.h>
45 #include <unistd.h>
46 #include <signal.h>
47 #include <sys/time.h>
48 #include <time.h>
49 #include <errno.h>
50
51 #include <pthread.h>
52 #include <semaphore.h>
53
54 #include "vm/types.h"
55
56 #include "arch.h"
57
58 #ifndef USE_MD_THREAD_STUFF
59 #include "machine-instr.h"
60 #else
61 #include "threads/native/generic-primitives.h"
62 #endif
63
64 #include "mm/boehm.h"
65 #include "mm/memory.h"
66 #include "native/native.h"
67 #include "native/include/java_lang_Object.h"
68 #include "native/include/java_lang_Throwable.h"
69 #include "native/include/java_lang_Thread.h"
70 #include "native/include/java_lang_ThreadGroup.h"
71 #include "native/include/java_lang_VMThread.h"
72 #include "threads/native/threads.h"
73 #include "toolbox/avl.h"
74 #include "toolbox/logging.h"
75 #include "vm/builtin.h"
76 #include "vm/exceptions.h"
77 #include "vm/global.h"
78 #include "vm/loader.h"
79 #include "vm/options.h"
80 #include "vm/stringlocal.h"
81 #include "vm/vm.h"
82 #include "vm/jit/asmpart.h"
83
84 #if !defined(__DARWIN__)
85 #if defined(__LINUX__)
86 #define GC_LINUX_THREADS
87 #elif defined(__MIPS__)
88 #define GC_IRIX_THREADS
89 #endif
90 #include "boehm-gc/include/gc.h"
91 #endif
92
93 #ifdef USE_MD_THREAD_STUFF
94 pthread_mutex_t _atomic_add_lock = PTHREAD_MUTEX_INITIALIZER;
95 pthread_mutex_t _cas_lock = PTHREAD_MUTEX_INITIALIZER;
96 pthread_mutex_t _mb_lock = PTHREAD_MUTEX_INITIALIZER;
97 #endif
98
99
100 /******************************************************************************/
101 /* MACROS                                                                     */
102 /******************************************************************************/
103
104 #define INITIALLOCKRECORDS 8
105
106 #define GRAB_LR(lr,t) \
107     if (lr->owner != t) { \
108                 lr = lr->incharge; \
109         }
110
111 #define CHECK_MONITORSTATE(lr,t,mo,a) \
112     if (lr->o != mo || lr->owner != t) { \
113                 *exceptionptr = new_illegalmonitorstateexception(); \
114                 a; \
115         }
116
117
118 /******************************************************************************/
119 /* GLOBAL VARIABLES                                                           */
120 /******************************************************************************/
121
122 /* unlocked dummy record - avoids NULL checks */
123 static lock_record_t *dummyLR;
124
125 pthread_mutex_t lock_global_pool_lock;
126 lock_record_pool_t *lock_global_pool;
127
128
129 /* lock_init *******************************************************************
130
131    Initialize global data for locking.
132
133 *******************************************************************************/
134
135 void lock_init(void)
136 {
137         pthread_mutex_init(&lock_global_pool_lock, NULL);
138
139         /* Every newly created object's monitorPtr points here so we save
140            a check against NULL */
141
142         dummyLR = NEW(lock_record_t);
143         dummyLR->o = NULL;
144         dummyLR->owner = NULL;
145         dummyLR->waiting = NULL;
146         dummyLR->incharge = dummyLR;
147 }
148
149
150 /* lock_record_init ************************************************************
151
152    Initialize a lock record.
153
154    IN:
155       r............the lock record to initialize
156           t............will become the owner
157
158 *******************************************************************************/
159
160 static void lock_record_init(lock_record_t *r, threadobject *t)
161 {
162         r->lockCount = 1;
163         r->owner = t;
164         r->queuers = 0;
165         r->o = NULL;
166         r->waiter = NULL;
167         r->incharge = (lock_record_t *) &dummyLR;
168         r->waiting = NULL;
169         threads_sem_init(&r->queueSem, 0, 0);
170         pthread_mutex_init(&r->resolveLock, NULL);
171         pthread_cond_init(&r->resolveWait, NULL);
172 }
173
174
175 /* lock_init_thread_lock_record_pool *******************************************
176
177    Initialize the lock record pool(s) for a thread.
178
179    IN:
180       thread.......the thread
181
182 *******************************************************************************/
183
184 void lock_init_thread_lock_record_pool(threadobject *thread)
185 {
186         thread->ee.firstLR = NULL;
187         thread->ee.lrpool = NULL;
188         thread->ee.numlr = 0;
189 }
190
191
192 /* lock_record_alloc_new_pool **************************************************
193
194    Get a new lock record pool from the memory allocator.
195
196    IN:
197       thread.......the thread that will own the lock records
198           size.........number of lock records in the pool to allocate
199
200    RETURN VALUE:
201       the new lock record pool, with initialized lock records
202
203 *******************************************************************************/
204
205 static lock_record_pool_t *lock_record_alloc_new_pool(threadobject *thread, int size)
206 {
207         lock_record_pool_t *p = mem_alloc(sizeof(lock_record_pool_header_t) 
208                                                                                 + sizeof(lock_record_t) * size);
209         int i;
210
211         p->header.size = size;
212         for (i=0; i<size; i++) {
213                 lock_record_init(&p->lr[i], thread);
214                 p->lr[i].nextFree = &p->lr[i+1];
215         }
216         p->lr[i-1].nextFree = NULL;
217         return p;
218 }
219
220
221 /* lock_record_alloc_pool ******************************************************
222
223    Allocate a lock record pool. The pool is either taken from the global free
224    list or requested from the memory allocator.
225
226    IN:
227       thread.......the thread that will own the lock records
228           size.........number of lock records in the pool to allocate
229
230    RETURN VALUE:
231       the new lock record pool, with initialized lock records
232
233 *******************************************************************************/
234
235 static lock_record_pool_t *lock_record_alloc_pool(threadobject *t, int size)
236 {
237         pthread_mutex_lock(&lock_global_pool_lock);
238         if (lock_global_pool) {
239                 int i;
240                 lock_record_pool_t *pool = lock_global_pool;
241                 lock_global_pool = pool->header.next;
242                 pthread_mutex_unlock(&lock_global_pool_lock);
243
244                 for (i=0; i < pool->header.size; i++) {
245                         pool->lr[i].owner = t;
246                         pool->lr[i].nextFree = &pool->lr[i+1];
247                 }
248                 pool->lr[i-1].nextFree = NULL;
249
250                 return pool;
251         }
252         pthread_mutex_unlock(&lock_global_pool_lock);
253
254         return lock_record_alloc_new_pool(t, size);
255 }
256
257
258 /* lock_record_free_pools ******************************************************
259
260    Free the lock record pools in the given linked list.
261
262    IN:
263       pool.........list header
264
265 *******************************************************************************/
266
267 void lock_record_free_pools(lock_record_pool_t *pool)
268 {
269         lock_record_pool_header_t *last;
270         pthread_mutex_lock(&lock_global_pool_lock);
271         last = &pool->header;
272         while (last->next)
273                 last = &last->next->header;
274         last->next = lock_global_pool;
275         lock_global_pool = pool;
276         pthread_mutex_unlock(&lock_global_pool_lock);
277 }
278
279
280 /* lock_record_alloc ***********************************************************
281
282    Allocate a lock record which is owned by the given thread.
283
284    IN:
285       t............the thread 
286
287 *******************************************************************************/
288
289 static lock_record_t *lock_record_alloc(threadobject *t)
290 {
291         lock_record_t *r;
292
293         assert(t);
294         r = t->ee.firstLR;
295
296         if (!r) {
297                 int poolsize = t->ee.numlr ? t->ee.numlr * 2 : INITIALLOCKRECORDS;
298                 lock_record_pool_t *pool = lock_record_alloc_pool(t, poolsize);
299                 pool->header.next = t->ee.lrpool;
300                 t->ee.lrpool = pool;
301                 r = &pool->lr[0];
302                 t->ee.numlr += pool->header.size;
303         }
304
305         t->ee.firstLR = r->nextFree;
306 #ifndef NDEBUG
307         r->nextFree = NULL; /* in order to find invalid uses of nextFree */
308 #endif
309         return r;
310 }
311
312
313 /* lock_record_recycle *********************************************************
314
315    Recycle the given lock record. It will be inserted in the appropriate
316    free list.
317
318    IN:
319       t............the owner
320           r............lock record to recycle
321
322 *******************************************************************************/
323
324 static inline void lock_record_recycle(threadobject *t, lock_record_t *r)
325 {
326         assert(t);
327         assert(r);
328         assert(r->owner == t);
329         assert(r->nextFree == NULL);
330
331         r->nextFree = t->ee.firstLR;
332         t->ee.firstLR = r;
333 }
334
335
336 /* lock_init_object_lock *******************************************************
337
338    Initialize the monitor pointer of the given object. The monitor gets
339    initialized to an unlocked state.
340
341 *******************************************************************************/
342
343 void lock_init_object_lock(java_objectheader *o)
344 {
345         assert(o);
346
347         o->monitorPtr = dummyLR;
348 }
349
350
351 /* lock_get_initial_lock_word **************************************************
352
353    Returns the global dummy monitor lock record. The pointer is
354    required in the code generator to set up a virtual
355    java_objectheader for code patch locking.
356
357 *******************************************************************************/
358
359 lock_record_t *lock_get_initial_lock_word(void)
360 {
361         return dummyLR;
362 }
363
364
365 /* lock_queue_on_lock_record ***************************************************
366
367    Suspend the current thread and queue it on the given lock record.
368
369 *******************************************************************************/
370
371 static void lock_queue_on_lock_record(lock_record_t *lr, java_objectheader *o)
372 {
373         atomic_add(&lr->queuers, 1);
374         MEMORY_BARRIER_AFTER_ATOMIC();
375
376         if (lr->o == o)
377                 threads_sem_wait(&lr->queueSem);
378
379         atomic_add(&lr->queuers, -1);
380 }
381
382
383 /* lock_record_release *********************************************************
384
385    Release the lock held by the given lock record. Threads queueing on the
386    semaphore of the record will be woken up.
387
388 *******************************************************************************/
389
390 static void lock_record_release(lock_record_t *lr)
391 {
392         int q;
393         lr->o = NULL;
394         MEMORY_BARRIER();
395         q = lr->queuers;
396         while (q--)
397                 threads_sem_post(&lr->queueSem);
398 }
399
400
401 static inline void lock_handle_waiter(lock_record_t *newlr,
402                                                                           lock_record_t *curlr,
403                                                                           java_objectheader *o)
404 {
405         /* if the current lock record is used for waiting on the object */
406         /* `o`, then record it as a waiter in the new lock record       */
407
408         if (curlr->waiting == o)
409                 newlr->waiter = curlr;
410 }
411
412
413 /* lock_monitor_enter ****************************************************************
414
415    Acquire the monitor of the given object. If the current thread already
416    owns the monitor, the lock counter is simply increased.
417
418    This function blocks until it can acquire the monitor.
419
420    IN:
421       t............the current thread
422           o............the object of which to enter the monitor
423
424    RETURN VALUE:
425       the new lock record of the object when it has been entered
426
427 *******************************************************************************/
428
429 lock_record_t *lock_monitor_enter(threadobject *t, java_objectheader *o)
430 {
431         for (;;) {
432                 lock_record_t *lr = o->monitorPtr;
433                 if (lr->o != o) {
434                         /* the lock record does not lock this object */
435                         lock_record_t *nlr;
436                         lock_record_t *mlr;
437                    
438                         /* allocate a new lock record for this object */
439                         mlr     = lock_record_alloc(t);
440                         mlr->o = o;
441
442                         /* check if it is the same record the object refered to earlier */
443                         if (mlr == lr) {
444                                 MEMORY_BARRIER();
445                                 nlr = o->monitorPtr;
446                                 if (nlr == lr) {
447                                         /* the object still refers to the same lock record */
448                                         /* got it! */
449                                         lock_handle_waiter(mlr, lr, o);
450                                         return mlr;
451                                 }
452                         } 
453                         else {
454                                 /* no, it's another lock record */
455                                 /* if we don't own the old record, set incharge XXX */
456                                 if (lr->owner != t)
457                                         mlr->incharge = lr;
458
459                                 /* if the object still refers to lr, replace it by the new mlr */
460                                 MEMORY_BARRIER_BEFORE_ATOMIC();
461                                 nlr = (lock_record_t *) compare_and_swap((long*) &o->monitorPtr, (long) lr, (long) mlr);
462                         }
463
464                         if (nlr == lr) {
465                                 /* we swapped the new record in successfully */
466                                 if (mlr == lr || lr->o != o) {
467                                         /* the old lock record is the same as the new one, or */
468                                         /* it locks another object.                           */
469                                         /* got it! */
470                                         lock_handle_waiter(mlr, lr, o);
471                                         return mlr;
472                                 }
473                                 /* lr locks the object, we have to wait */
474                                 while (lr->o == o)
475                                         lock_queue_on_lock_record(lr, o);
476
477                                 /* got it! */
478                                 lock_handle_waiter(mlr, lr, o);
479                                 return mlr;
480                         }
481
482                         /* forget this mlr lock record, wait on nlr and try again */
483                         lock_record_release(mlr);
484                         lock_record_recycle(t, mlr);
485                         lock_queue_on_lock_record(nlr, o);
486                 } 
487                 else {
488                         /* the lock record is for the object we want */
489
490                         if (lr->owner == t) {
491                                 /* we own it already, just recurse */
492                                 lr->lockCount++;
493                                 return lr;
494                         }
495
496                         /* it's locked. we wait and then try again */
497                         lock_queue_on_lock_record(lr, o);
498                 }
499         }
500 }
501
502
503 /* lock_wake_waiters ********************************************************
504
505    For each lock record in the given waiter list, post the queueSem
506    once for each queuer of the lock record.
507
508    IN:
509       lr...........the head of the waiter list
510
511 *******************************************************************************/
512
513 static void lock_wake_waiters(lock_record_t *lr)
514 {
515         lock_record_t *tmplr;
516         s4 q;
517
518         /* move it to a local variable (Stefan commented this especially.
519          * Might be important somehow...) */
520
521         tmplr = lr;
522
523         do {
524                 q = tmplr->queuers;
525
526                 while (q--)
527                         threads_sem_post(&tmplr->queueSem);
528
529                 tmplr = tmplr->waiter;
530         } while (tmplr != NULL && tmplr != lr); /* this breaks cycles to lr */
531 }
532
533
534 /* lock_monitor_exit *****************************************************************
535
536    Decrement the counter of a (currently owned) monitor. If the counter
537    reaches zero, release the monitor.
538
539    If the current thread is not the owner of the monitor, an 
540    IllegalMonitorState exception is thrown.
541
542    IN:
543       t............the current thread
544           o............the object of which to exit the monitor
545
546    RETURN VALUE:
547       true.........everything ok,
548           false........an exception has been thrown
549
550 *******************************************************************************/
551
552 bool lock_monitor_exit(threadobject *t, java_objectheader *o)
553 {
554         lock_record_t *lr;
555
556         lr = o->monitorPtr;
557         GRAB_LR(lr, t);
558         CHECK_MONITORSTATE(lr, t, o, return false);
559
560         /* { the current thread `t` owns the lock record `lr` on object `o` } */
561
562         if (lr->lockCount > 1) {
563                 /* we had locked this one recursively. just decrement, it will */
564                 /* still be locked. */
565                 lr->lockCount--;
566                 return true;
567         }
568
569         /* we are going to unlock and recycle this lock record */
570
571         if (lr->waiter) {
572                 lock_record_t *wlr = lr->waiter;
573                 if (o->monitorPtr != lr ||
574                         (void*) compare_and_swap((long*) &o->monitorPtr, (long) lr, (long) wlr) != lr)
575                 {
576                         lock_record_t *nlr = o->monitorPtr;
577                         assert(nlr->waiter == NULL);
578                         nlr->waiter = wlr; /* XXX is it ok to overwrite the nlr->waiter field like that? */
579                         STORE_ORDER_BARRIER();
580                 }
581                 else {
582                         lock_wake_waiters(wlr);
583                 }
584                 lr->waiter = NULL;
585         }
586
587         /* unlock and throw away this lock record */
588         lock_record_release(lr);
589         lock_record_recycle(t, lr);
590         return true;
591 }
592
593
594 /* lock_record_remove_waiter *******************************************************
595
596    Remove a waiter lock record from the waiter list of the given lock record
597
598    IN:
599       lr...........the lock record holding the waiter list
600           toremove.....the record to remove from the list
601
602 *******************************************************************************/
603
604 static void lock_record_remove_waiter(lock_record_t *lr,
605                                                                           lock_record_t *toremove)
606 {
607         do {
608                 if (lr->waiter == toremove) {
609                         lr->waiter = toremove->waiter;
610                         break;
611                 }
612                 lr = lr->waiter;
613         } while (lr); /* XXX need to break cycle? */
614 }
615
616
617 /* lock_monitor_wait *****************************************************************
618
619    Wait on an object for a given (maximum) amount of time.
620
621    IN:
622       t............the current thread
623           o............the object
624           millis.......milliseconds of timeout
625           nanos........nanoseconds of timeout
626
627    PRE-CONDITION:
628       The current thread must be the owner of the object's monitor.
629    
630 *******************************************************************************/
631
632 void lock_monitor_wait(threadobject *t, java_objectheader *o, s8 millis, s4 nanos)
633 {
634         bool wasinterrupted;
635         lock_record_t *newlr;
636         lock_record_t *lr;
637
638         lr = o->monitorPtr;
639         GRAB_LR(lr, t);
640         CHECK_MONITORSTATE(lr, t, o, return);
641
642         /* { the thread t owns the lock record lr on the object o } */
643
644         /* wake threads waiting on this record XXX why? */
645
646         if (lr->waiter)
647                 lock_wake_waiters(lr->waiter);
648
649         /* mark the lock record as "waiting on object o" */
650
651         lr->waiting = o;
652         STORE_ORDER_BARRIER();
653
654         /* unlock this record */
655
656         lock_record_release(lr);
657
658         /* wait until notified/interrupted/timed out */
659
660         wasinterrupted = threads_wait_with_timeout_relative(t, millis, nanos);
661
662         /* re-enter the monitor */
663
664         newlr = lock_monitor_enter(t, o);
665
666         /* we are no longer waiting */
667
668         lock_record_remove_waiter(newlr, lr);
669         newlr->lockCount = lr->lockCount;
670
671         /* recylce the old lock record */
672
673         lr->lockCount = 1;
674         lr->waiting = NULL;
675         lr->waiter = NULL;
676         lock_record_recycle(t, lr);
677
678         /* if we have been interrupted, throw the appropriate exception */
679
680         if (wasinterrupted)
681                 *exceptionptr = new_exception(string_java_lang_InterruptedException);
682 }
683
684
685 /* lock_monitor_notify **************************************************************
686
687    Notify one thread or all threads waiting on the given object.
688
689    IN:
690       t............the current thread
691           o............the object
692           one..........if true, only notify one thread
693
694    PRE-CONDITION:
695       The current thread must be the owner of the object's monitor.
696    
697 *******************************************************************************/
698
699 static void lock_monitor_notify(threadobject *t, java_objectheader *o, bool one)
700 {
701         lock_record_t *lr;
702         lock_record_t *wlr;
703         threadobject *wthread;
704
705         lr = o->monitorPtr;
706         GRAB_LR(lr, t);
707         CHECK_MONITORSTATE(lr, t, o, return);
708
709         /* { the thread t owns the lock record lr on the object o } */
710
711         /* for each waiter: */
712
713         for (wlr = lr->waiter; wlr; wlr = wlr->waiter) {
714
715                 /* signal the waiting thread */
716
717                 wthread = wlr->owner;
718                 pthread_mutex_lock(&wthread->waitLock);
719                 if (wthread->isSleeping)
720                         pthread_cond_signal(&wthread->waitCond);
721                 wthread->signaled = true;
722                 pthread_mutex_unlock(&wthread->waitLock);
723
724                 /* if we should only wake one, we are done */
725
726                 if (one)
727                         break;
728         }
729 }
730
731
732 /* lock_does_thread_hold_lock **************************************************
733
734    Return true if the given thread owns the monitor of the given object.
735
736    IN:
737       t............the thread
738           o............the object
739    
740    RETURN VALUE:
741       true, if the thread is locking the object
742
743 *******************************************************************************/
744
745 bool lock_does_thread_hold_lock(threadobject *t, java_objectheader *o)
746 {
747         lock_record_t *lr;
748
749         lr = o->monitorPtr;
750         GRAB_LR(lr, t);
751
752         return (lr->o == o) && (lr->owner == t);
753 }
754
755
756 /* lock_wait_for_object ********************************************************
757
758    Wait for the given object.
759
760    IN:
761           o............the object
762           millis.......milliseconds to wait
763           nanos........nanoseconds to wait
764    
765 *******************************************************************************/
766
767 void lock_wait_for_object(java_objectheader *o, s8 millis, s4 nanos)
768 {
769         threadobject *t = (threadobject*) THREADOBJECT;
770         lock_monitor_wait(t, o, millis, nanos);
771 }
772
773
774 /* lock_notify_object **********************************************************
775
776    Notify one thread waiting on the given object.
777
778    IN:
779           o............the object
780    
781 *******************************************************************************/
782
783 void lock_notify_object(java_objectheader *o)
784 {
785         threadobject *t = (threadobject*) THREADOBJECT;
786         lock_monitor_notify(t, o, true);
787 }
788
789
790 /* lock_notify_all_object ******************************************************
791
792    Notify all threads waiting on the given object.
793
794    IN:
795           o............the object
796    
797 *******************************************************************************/
798
799 void lock_notify_all_object(java_objectheader *o)
800 {
801         threadobject *t = (threadobject*) THREADOBJECT;
802         lock_monitor_notify(t, o, false);
803 }
804
805 /*
806  * These are local overrides for various environment variables in Emacs.
807  * Please do not remove this and leave it at the end of the file, where
808  * Emacs will automagically detect them.
809  * ---------------------------------------------------------------------
810  * Local variables:
811  * mode: c
812  * indent-tabs-mode: t
813  * c-basic-offset: 4
814  * tab-width: 4
815  * End:
816  * vim:noexpandtab:sw=4:ts=4:
817  */