1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
3 * ***** BEGIN LICENSE BLOCK *****
4 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
6 * The contents of this file are subject to the Mozilla Public License Version
7 * 1.1 (the "License"); you may not use this file except in compliance with
8 * the License. You may obtain a copy of the License at
9 * http://www.mozilla.org/MPL/
11 * Software distributed under the License is distributed on an "AS IS" basis,
12 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
13 * for the specific language governing rights and limitations under the
16 * The Original Code is Mozilla Communicator client code, released
19 * The Initial Developer of the Original Code is
20 * Netscape Communications Corporation.
21 * Portions created by the Initial Developer are Copyright (C) 1998
22 * the Initial Developer. All Rights Reserved.
26 * Alternatively, the contents of this file may be used under the terms of
27 * either of the GNU General Public License Version 2 or later (the "GPL"),
28 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
29 * in which case the provisions of the GPL or the LGPL are applicable instead
30 * of those above. If you wish to allow use of your version of this file only
31 * under the terms of either the GPL or the LGPL, and not to allow others to
32 * use your version of this file under the terms of the MPL, indicate your
33 * decision by deleting the provisions above and replace them with the notice
34 * and other provisions required by the GPL or the LGPL. If you do not delete
35 * the provisions above, a recipient may use your version of this file under
36 * the terms of any one of the MPL, the GPL or the LGPL.
38 * ***** END LICENSE BLOCK ***** */
60 #define ReadWord(W) (W)
62 #if !defined(__GNUC__)
64 # define __volatile__ volatile
67 /* Implement NativeCompareAndSwap. */
69 #if defined(_MSC_VER) && defined(_M_IX86)
70 #pragma warning( disable : 4035 )
73 _InterlockedCompareExchange(long *volatile dest
, long exchange
, long comp
);
75 #pragma intrinsic(_InterlockedCompareExchange)
77 JS_STATIC_ASSERT(sizeof(jsword
) == sizeof(long));
79 static JS_ALWAYS_INLINE
int
80 NativeCompareAndSwapHelper(volatile jsword
*w
, jsword ov
, jsword nv
)
82 _InterlockedCompareExchange((long*) w
, nv
, ov
);
88 static JS_ALWAYS_INLINE
int
89 NativeCompareAndSwap(volatile jsword
*w
, jsword ov
, jsword nv
)
91 return (NativeCompareAndSwapHelper(w
, ov
, nv
) & 1);
94 #elif defined(_MSC_VER) && (defined(_M_AMD64) || defined(_M_X64))
96 extern long long __cdecl
97 _InterlockedCompareExchange64(long long *volatile dest
, long long exchange
, long long comp
);
99 #pragma intrinsic(_InterlockedCompareExchange64)
101 static JS_ALWAYS_INLINE
int
102 NativeCompareAndSwap(volatile jsword
*w
, jsword ov
, jsword nv
)
104 return _InterlockedCompareExchange64((long long *volatile)w
, nv
, ov
) == ov
;
107 #elif defined(XP_MACOSX) || defined(DARWIN)
109 #include <libkern/OSAtomic.h>
111 static JS_ALWAYS_INLINE
int
112 NativeCompareAndSwap(volatile jsword
*w
, jsword ov
, jsword nv
)
114 /* Details on these functions available in the manpage for atomic */
115 return OSAtomicCompareAndSwapPtrBarrier(reinterpret_cast<void *>(ov
),
116 reinterpret_cast<void *>(nv
),
117 reinterpret_cast<void * volatile *>(w
));
120 #elif defined(__i386) && (defined(__GNUC__) || defined(__SUNPRO_CC))
122 /* Note: This fails on 386 cpus, cmpxchgl is a >= 486 instruction */
123 static JS_ALWAYS_INLINE
int
124 NativeCompareAndSwap(volatile jsword
*w
, jsword ov
, jsword nv
)
128 __asm__
__volatile__ (
130 "cmpxchgl %2, (%1)\n"
135 /* Different code for Sun Studio because of a bug of SS12U1 */
136 : "c" (w
), "d" (nv
), "a" (ov
)
138 : "r" (w
), "r" (nv
), "a" (ov
)
143 #elif defined(__x86_64) && (defined(__GNUC__) || defined(__SUNPRO_CC))
145 static JS_ALWAYS_INLINE
int
146 NativeCompareAndSwap(volatile jsword
*w
, jsword ov
, jsword nv
)
150 __asm__
__volatile__ (
152 "cmpxchgq %2, (%1)\n"
154 "movzbl %%al, %%eax\n"
156 : "r" (w
), "r" (nv
), "a" (ov
)
161 #elif defined(__sparc)
162 #if defined(__GNUC__)
164 static JS_ALWAYS_INLINE
int
165 NativeCompareAndSwap(volatile jsword
*w
, jsword ov
, jsword nv
)
169 __asm__
__volatile__ (
170 "membar #StoreLoad | #LoadLoad\n"
171 #if JS_BITS_PER_WORD == 32
176 "membar #StoreLoad | #LoadLoad\n"
183 : "r" (w
), "r" (ov
), "r" (nv
));
187 #elif defined(__SUNPRO_CC)
189 /* Implementation in lock_sparc*.il */
191 NativeCompareAndSwap(volatile jsword
*w
, jsword ov
, jsword nv
);
197 #include <sys/atomic_op.h>
199 static JS_ALWAYS_INLINE
int
200 NativeCompareAndSwap(volatile jsword
*w
, jsword ov
, jsword nv
)
203 JS_STATIC_ASSERT(sizeof(jsword
) == sizeof(long));
205 res
= compare_and_swaplp((atomic_l
)w
, &ov
, nv
);
211 #elif defined(USE_ARM_KUSER)
213 /* See https://bugzilla.mozilla.org/show_bug.cgi?id=429387 for a
214 * description of this ABI; this is a function provided at a fixed
215 * location by the kernel in the memory space of each process.
217 typedef int (__kernel_cmpxchg_t
)(int oldval
, int newval
, volatile int *ptr
);
218 #define __kernel_cmpxchg (*(__kernel_cmpxchg_t *)0xffff0fc0)
220 JS_STATIC_ASSERT(sizeof(jsword
) == sizeof(int));
222 static JS_ALWAYS_INLINE
int
223 NativeCompareAndSwap(volatile jsword
*w
, jsword ov
, jsword nv
)
225 volatile int *vp
= (volatile int *) w
;
228 /* Loop until a __kernel_cmpxchg succeeds. See bug 446169 */
230 failed
= __kernel_cmpxchg(ov
, nv
, vp
);
231 } while (failed
&& *vp
== ov
);
235 #elif JS_HAS_NATIVE_COMPARE_AND_SWAP
237 #error "JS_HAS_NATIVE_COMPARE_AND_SWAP should be 0 if your platform lacks a compare-and-swap instruction."
239 #endif /* arch-tests */
241 #if JS_HAS_NATIVE_COMPARE_AND_SWAP
244 js_CompareAndSwap(volatile jsword
*w
, jsword ov
, jsword nv
)
246 return !!NativeCompareAndSwap(w
, ov
, nv
);
249 #elif defined(NSPR_LOCK)
252 # warning "js_CompareAndSwap is implemented using NSPR lock"
256 js_CompareAndSwap(volatile jsword
*w
, jsword ov
, jsword nv
)
259 static PRLock
*CompareAndSwapLock
= JS_NEW_LOCK();
261 JS_ACQUIRE_LOCK(CompareAndSwapLock
);
265 JS_RELEASE_LOCK(CompareAndSwapLock
);
269 #else /* !defined(NSPR_LOCK) */
271 #error "NSPR_LOCK should be on when the platform lacks native compare-and-swap."
276 js_AtomicSetMask(volatile jsword
*w
, jsword mask
)
283 } while (!js_CompareAndSwap(w
, ov
, nv
));
287 js_AtomicClearMask(volatile jsword
*w
, jsword mask
)
294 } while (!js_CompareAndSwap(w
, ov
, nv
));
307 typedef struct JSFatLockTable
{
312 #define GLOBAL_LOCK_INDEX(id) (((uint32)(jsuword)(id)>>2) & global_locks_mask)
315 js_Dequeue(JSThinLock
*);
317 static PRLock
**global_locks
;
318 static uint32 global_lock_count
= 1;
319 static uint32 global_locks_log2
= 0;
320 static uint32 global_locks_mask
= 0;
323 js_LockGlobal(void *id
)
325 uint32 i
= GLOBAL_LOCK_INDEX(id
);
326 PR_Lock(global_locks
[i
]);
330 js_UnlockGlobal(void *id
)
332 uint32 i
= GLOBAL_LOCK_INDEX(id
);
333 PR_Unlock(global_locks
[i
]);
336 #endif /* !NSPR_LOCK */
339 js_InitLock(JSThinLock
*tl
)
343 tl
->fat
= (JSFatLock
*)JS_NEW_LOCK();
350 js_FinishLock(JSThinLock
*tl
)
353 tl
->owner
= 0xdeadbeef;
355 JS_DESTROY_LOCK(((JSLock
*)tl
->fat
));
357 JS_ASSERT(tl
->owner
== 0);
358 JS_ASSERT(tl
->fat
== NULL
);
367 JSFatLock
*fl
= (JSFatLock
*)js_malloc(sizeof(JSFatLock
)); /* for now */
368 if (!fl
) return NULL
;
372 fl
->slock
= PR_NewLock();
373 fl
->svar
= PR_NewCondVar(fl
->slock
);
378 DestroyFatlock(JSFatLock
*fl
)
380 PR_DestroyLock(fl
->slock
);
381 PR_DestroyCondVar(fl
->svar
);
386 ListOfFatlocks(int listc
)
393 m0
= m
= NewFatlock();
394 for (i
=1; i
<listc
; i
++) {
395 m
->next
= NewFatlock();
402 DeleteListOfFatlocks(JSFatLock
*m
)
411 static JSFatLockTable
*fl_list_table
= NULL
;
412 static uint32 fl_list_table_len
= 0;
413 static uint32 fl_list_chunk_len
= 0;
420 uint32 i
= GLOBAL_LOCK_INDEX(id
);
421 if (fl_list_table
[i
].free
== NULL
) {
423 if (fl_list_table
[i
].taken
)
424 printf("Ran out of fat locks!\n");
426 fl_list_table
[i
].free
= ListOfFatlocks(fl_list_chunk_len
);
428 m
= fl_list_table
[i
].free
;
429 fl_list_table
[i
].free
= m
->next
;
431 m
->next
= fl_list_table
[i
].taken
;
432 m
->prevp
= &fl_list_table
[i
].taken
;
433 if (fl_list_table
[i
].taken
)
434 fl_list_table
[i
].taken
->prevp
= &m
->next
;
435 fl_list_table
[i
].taken
= m
;
440 PutFatlock(JSFatLock
*m
, void *id
)
446 /* Unlink m from fl_list_table[i].taken. */
449 m
->next
->prevp
= m
->prevp
;
451 /* Insert m in fl_list_table[i].free. */
452 i
= GLOBAL_LOCK_INDEX(id
);
453 m
->next
= fl_list_table
[i
].free
;
454 fl_list_table
[i
].free
= m
;
457 #endif /* !NSPR_LOCK */
460 js_SetupLocks(int listc
, int globc
)
468 if (listc
> 10000 || listc
< 0) /* listc == fat lock list chunk length */
469 printf("Bad number %d in js_SetupLocks()!\n", listc
);
470 if (globc
> 100 || globc
< 0) /* globc == number of global locks */
471 printf("Bad number %d in js_SetupLocks()!\n", listc
);
473 global_locks_log2
= JS_CeilingLog2(globc
);
474 global_locks_mask
= JS_BITMASK(global_locks_log2
);
475 global_lock_count
= JS_BIT(global_locks_log2
);
476 global_locks
= (PRLock
**) js_malloc(global_lock_count
* sizeof(PRLock
*));
479 for (i
= 0; i
< global_lock_count
; i
++) {
480 global_locks
[i
] = PR_NewLock();
481 if (!global_locks
[i
]) {
482 global_lock_count
= i
;
487 fl_list_table
= (JSFatLockTable
*) js_malloc(i
* sizeof(JSFatLockTable
));
488 if (!fl_list_table
) {
492 fl_list_table_len
= global_lock_count
;
493 for (i
= 0; i
< global_lock_count
; i
++)
494 fl_list_table
[i
].free
= fl_list_table
[i
].taken
= NULL
;
495 fl_list_chunk_len
= listc
;
496 #endif /* !NSPR_LOCK */
507 for (i
= 0; i
< global_lock_count
; i
++)
508 PR_DestroyLock(global_locks
[i
]);
509 js_free(global_locks
);
511 global_lock_count
= 1;
512 global_locks_log2
= 0;
513 global_locks_mask
= 0;
516 for (i
= 0; i
< fl_list_table_len
; i
++) {
517 DeleteListOfFatlocks(fl_list_table
[i
].free
);
518 fl_list_table
[i
].free
= NULL
;
519 DeleteListOfFatlocks(fl_list_table
[i
].taken
);
520 fl_list_table
[i
].taken
= NULL
;
522 js_free(fl_list_table
);
523 fl_list_table
= NULL
;
524 fl_list_table_len
= 0;
526 #endif /* !NSPR_LOCK */
531 static JS_ALWAYS_INLINE
void
532 ThinLock(JSThinLock
*tl
, jsword me
)
534 JS_ACQUIRE_LOCK((JSLock
*) tl
->fat
);
538 static JS_ALWAYS_INLINE
void
539 ThinUnlock(JSThinLock
*tl
, jsword
/*me*/)
542 JS_RELEASE_LOCK((JSLock
*) tl
->fat
);
548 * Fast locking and unlocking is implemented by delaying the allocation of a
549 * system lock (fat lock) until contention. As long as a locking thread A
550 * runs uncontended, the lock is represented solely by storing A's identity in
551 * the object being locked.
553 * If another thread B tries to lock the object currently locked by A, B is
554 * enqueued into a fat lock structure (which might have to be allocated and
555 * pointed to by the object), and suspended using NSPR conditional variables
556 * (wait). A wait bit (Bacon bit) is set in the lock word of the object,
557 * signalling to A that when releasing the lock, B must be dequeued and
560 * The basic operation of the locking primitives (js_Lock, js_Unlock,
561 * js_Enqueue, and js_Dequeue) is compare-and-swap. Hence, when locking into
562 * the word pointed at by p, compare-and-swap(p, 0, A) success implies that p
563 * is unlocked. Similarly, when unlocking p, if compare-and-swap(p, A, 0)
564 * succeeds this implies that p is uncontended (no one is waiting because the
565 * wait bit is not set).
567 * When dequeueing, the lock is released, and one of the threads suspended on
568 * the lock is notified. If other threads still are waiting, the wait bit is
569 * kept (in js_Enqueue), and if not, the fat lock is deallocated.
571 * The functions js_Enqueue, js_Dequeue, js_SuspendThread, and js_ResumeThread
572 * are serialized using a global lock. For scalability, a hashtable of global
573 * locks is used, which is indexed modulo the thin lock pointer.
578 * (i) global lock is held
582 js_SuspendThread(JSThinLock
*tl
)
588 fl
= tl
->fat
= GetFatlock(tl
);
591 JS_ASSERT(fl
->susp
>= 0);
595 stat
= PR_WaitCondVar(fl
->svar
, PR_INTERVAL_NO_TIMEOUT
);
596 JS_ASSERT(stat
!= PR_FAILURE
);
597 PR_Unlock(fl
->slock
);
604 return tl
->fat
== NULL
;
608 * (i) global lock is held
612 js_ResumeThread(JSThinLock
*tl
)
614 JSFatLock
*fl
= tl
->fat
;
617 JS_ASSERT(fl
!= NULL
);
618 JS_ASSERT(fl
->susp
> 0);
621 stat
= PR_NotifyCondVar(fl
->svar
);
622 JS_ASSERT(stat
!= PR_FAILURE
);
623 PR_Unlock(fl
->slock
);
627 js_Enqueue(JSThinLock
*tl
, jsword me
)
633 o
= ReadWord(tl
->owner
);
635 if (o
!= 0 && NativeCompareAndSwap(&tl
->owner
, o
, n
)) {
636 if (js_SuspendThread(tl
))
637 me
= Thin_RemoveWait(me
);
639 me
= Thin_SetWait(me
);
641 else if (NativeCompareAndSwap(&tl
->owner
, 0, me
)) {
649 js_Dequeue(JSThinLock
*tl
)
654 o
= ReadWord(tl
->owner
);
655 JS_ASSERT(Thin_GetWait(o
) != 0);
656 JS_ASSERT(tl
->fat
!= NULL
);
657 if (!NativeCompareAndSwap(&tl
->owner
, o
, 0)) /* release it */
662 static JS_ALWAYS_INLINE
void
663 ThinLock(JSThinLock
*tl
, jsword me
)
665 JS_ASSERT(CURRENT_THREAD_IS_ME(me
));
666 if (NativeCompareAndSwap(&tl
->owner
, 0, me
))
668 if (Thin_RemoveWait(ReadWord(tl
->owner
)) != me
)
676 static JS_ALWAYS_INLINE
void
677 ThinUnlock(JSThinLock
*tl
, jsword me
)
679 JS_ASSERT(CURRENT_THREAD_IS_ME(me
));
682 * Since we can race with the NativeCompareAndSwap in js_Enqueue, we need
683 * to use a C_A_S here as well -- Arjan van de Ven 30/1/08
685 if (NativeCompareAndSwap(&tl
->owner
, me
, 0))
688 JS_ASSERT(Thin_GetWait(tl
->owner
));
689 if (Thin_RemoveWait(ReadWord(tl
->owner
)) == me
)
693 JS_ASSERT(0); /* unbalanced unlock */
697 #endif /* !NSPR_LOCK */
700 js_Lock(JSContext
*cx
, JSThinLock
*tl
)
702 ThinLock(tl
, CX_THINLOCK_ID(cx
));
706 js_Unlock(JSContext
*cx
, JSThinLock
*tl
)
708 ThinUnlock(tl
, CX_THINLOCK_ID(cx
));
712 js_LockRuntime(JSRuntime
*rt
)
716 rt
->rtLockOwner
= js_CurrentThreadId();
721 js_UnlockRuntime(JSRuntime
*rt
)
724 rt
->rtLockOwner
= NULL
;
726 PR_Unlock(rt
->rtLock
);
731 js_IsRuntimeLocked(JSRuntime
*rt
)
733 return js_CurrentThreadId() == rt
->rtLockOwner
;
736 #endif /* JS_THREADSAFE */