2 * Copyright (c) 2000-2009 Apple Inc. All rights reserved.
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
33 * File: kern/sync_lock.c
34 * Author: Joseph CaraDonna
36 * Contains RT distributed lock synchronization services.
39 #include <mach/mach_types.h>
40 #include <mach/lock_set_server.h>
41 #include <mach/task_server.h>
43 #include <kern/misc_protos.h>
44 #include <kern/kalloc.h>
45 #include <kern/sync_lock.h>
46 #include <kern/sched_prim.h>
47 #include <kern/ipc_kobject.h>
48 #include <kern/ipc_sync.h>
49 #include <kern/thread.h>
50 #include <kern/task.h>
52 #include <ipc/ipc_port.h>
53 #include <ipc/ipc_space.h>
54 #include <libkern/OSAtomic.h>
57 * Ulock ownership MACROS
59 * Assumes: ulock internal lock is held
62 #define ulock_ownership_set(ul, th) \
64 thread_mtx_lock(th); \
65 enqueue (&th->held_ulocks, (queue_entry_t) (ul)); \
66 thread_mtx_unlock(th); \
70 #define ulock_ownership_clear(ul) \
75 thread_mtx_lock(th); \
76 remqueue((queue_entry_t) (ul)); \
77 thread_mtx_unlock(th); \
79 remqueue((queue_entry_t) (ul)); \
81 (ul)->holder = THREAD_NULL; \
85 * Lock set ownership MACROS
88 #define lock_set_ownership_set(ls, t) \
91 enqueue_head(&(t)->lock_set_list, (queue_entry_t) (ls));\
92 (t)->lock_sets_owned++; \
97 #define lock_set_ownership_clear(ls, t) \
100 remqueue((queue_entry_t) (ls)); \
101 (t)->lock_sets_owned--; \
105 unsigned int lock_set_event
;
106 #define LOCK_SET_EVENT CAST_EVENT64_T(&lock_set_event)
108 unsigned int lock_set_handoff
;
109 #define LOCK_SET_HANDOFF CAST_EVENT64_T(&lock_set_handoff)
112 lck_attr_t lock_set_attr
;
113 lck_grp_t lock_set_grp
;
114 static lck_grp_attr_t lock_set_grp_attr
;
119 * ROUTINE: lock_set_init [private]
121 * Initialize the lock_set subsystem.
126 lck_grp_attr_setdefault(&lock_set_grp_attr
);
127 lck_grp_init(&lock_set_grp
, "lock_set", &lock_set_grp_attr
);
128 lck_attr_setdefault(&lock_set_attr
);
133 * ROUTINE: lock_set_create [exported]
135 * Creates a lock set.
136 * The port representing the lock set is returned as a parameter.
141 lock_set_t
*new_lock_set
,
145 lock_set_t lock_set
= LOCK_SET_NULL
;
150 *new_lock_set
= LOCK_SET_NULL
;
152 if (task
== TASK_NULL
|| n_ulocks
<= 0 || policy
> SYNC_POLICY_MAX
)
153 return KERN_INVALID_ARGUMENT
;
155 if ((VM_MAX_ADDRESS
- sizeof(struct lock_set
))/sizeof(struct ulock
) < (unsigned)n_ulocks
)
156 return KERN_RESOURCE_SHORTAGE
;
158 size
= sizeof(struct lock_set
) + (sizeof(struct ulock
) * (n_ulocks
-1));
159 lock_set
= (lock_set_t
) kalloc (size
);
161 if (lock_set
== LOCK_SET_NULL
)
162 return KERN_RESOURCE_SHORTAGE
;
165 lock_set_lock_init(lock_set
);
166 lock_set
->n_ulocks
= n_ulocks
;
167 lock_set
->ref_count
= (task
== kernel_task
) ? 1 : 2; /* one for kernel, one for port */
170 * Create and initialize the lock set port
172 lock_set
->port
= ipc_port_alloc_kernel();
173 if (lock_set
->port
== IP_NULL
) {
174 kfree(lock_set
, size
);
175 return KERN_RESOURCE_SHORTAGE
;
178 ipc_kobject_set (lock_set
->port
,
179 (ipc_kobject_t
) lock_set
,
183 * Initialize each ulock in the lock set
186 for (x
=0; x
< n_ulocks
; x
++) {
187 ulock
= (ulock_t
) &lock_set
->ulock_list
[x
];
188 ulock_lock_init(ulock
);
189 ulock
->lock_set
= lock_set
;
190 ulock
->holder
= THREAD_NULL
;
191 ulock
->blocked
= FALSE
;
192 ulock
->unstable
= FALSE
;
193 ulock
->ho_wait
= FALSE
;
194 ulock
->accept_wait
= FALSE
;
195 wait_queue_init(&ulock
->wait_queue
, policy
);
198 lock_set_ownership_set(lock_set
, task
);
200 lock_set
->active
= TRUE
;
201 *new_lock_set
= lock_set
;
207 * ROUTINE: lock_set_destroy [exported]
209 * Destroys a lock set. This call will only succeed if the
210 * specified task is the SAME task name specified at the lock set's
214 * - All threads currently blocked on the lock set's ulocks are awoken.
215 * - These threads will return with the KERN_LOCK_SET_DESTROYED error.
218 lock_set_destroy (task_t task
, lock_set_t lock_set
)
223 if (task
== TASK_NULL
|| lock_set
== LOCK_SET_NULL
)
224 return KERN_INVALID_ARGUMENT
;
226 if (lock_set
->owner
!= task
)
227 return KERN_INVALID_RIGHT
;
229 lock_set_lock(lock_set
);
230 if (!lock_set
->active
) {
231 lock_set_unlock(lock_set
);
232 return KERN_LOCK_SET_DESTROYED
;
236 * Deactivate lock set
238 lock_set
->active
= FALSE
;
241 * If a ulock is currently held in the target lock set:
243 * 1) Wakeup all threads blocked on the ulock (if any). Threads
244 * may be blocked waiting normally, or waiting for a handoff.
245 * Blocked threads will return with KERN_LOCK_SET_DESTROYED.
247 * 2) ulock ownership is cleared.
248 * The thread currently holding the ulock is revoked of its
251 for (i
= 0; i
< lock_set
->n_ulocks
; i
++) {
252 ulock
= &lock_set
->ulock_list
[i
];
256 if (ulock
->accept_wait
) {
257 ulock
->accept_wait
= FALSE
;
258 wait_queue_wakeup64_one(&ulock
->wait_queue
,
264 if (ulock
->blocked
) {
265 ulock
->blocked
= FALSE
;
266 wait_queue_wakeup64_all(&ulock
->wait_queue
,
270 if (ulock
->ho_wait
) {
271 ulock
->ho_wait
= FALSE
;
272 wait_queue_wakeup64_one(&ulock
->wait_queue
,
276 ulock_ownership_clear(ulock
);
282 lock_set_unlock(lock_set
);
283 lock_set_ownership_clear(lock_set
, task
);
286 * Drop the lock set reference given to the containing task,
287 * which inturn destroys the lock set structure if the reference
288 * count goes to zero.
290 lock_set_dereference(lock_set
);
296 lock_acquire (lock_set_t lock_set
, int lock_id
)
300 if (lock_set
== LOCK_SET_NULL
)
301 return KERN_INVALID_ARGUMENT
;
303 if (lock_id
< 0 || lock_id
>= lock_set
->n_ulocks
)
304 return KERN_INVALID_ARGUMENT
;
307 lock_set_lock(lock_set
);
308 if (!lock_set
->active
) {
309 lock_set_unlock(lock_set
);
310 return KERN_LOCK_SET_DESTROYED
;
313 ulock
= (ulock_t
) &lock_set
->ulock_list
[lock_id
];
315 lock_set_unlock(lock_set
);
318 * Block the current thread if the lock is already held.
321 if (ulock
->holder
!= THREAD_NULL
) {
324 if (ulock
->holder
== current_thread()) {
326 return KERN_LOCK_OWNED_SELF
;
329 ulock
->blocked
= TRUE
;
330 wait_result
= wait_queue_assert_wait64(&ulock
->wait_queue
,
332 THREAD_ABORTSAFE
, 0);
336 * Block - Wait for lock to become available.
338 if (wait_result
== THREAD_WAITING
)
339 wait_result
= thread_block(THREAD_CONTINUE_NULL
);
342 * Check the result status:
344 * Check to see why thread was woken up. In all cases, we
345 * already have been removed from the queue.
347 switch (wait_result
) {
348 case THREAD_AWAKENED
:
349 /* lock transitioned from old locker to us */
350 /* he already made us owner */
351 return (ulock
->unstable
) ? KERN_LOCK_UNSTABLE
:
354 case THREAD_INTERRUPTED
:
358 goto retry
; /* probably a dead lock_set */
361 panic("lock_acquire\n");
366 * Assign lock ownership
368 ulock_ownership_set(ulock
, current_thread());
371 return (ulock
->unstable
) ? KERN_LOCK_UNSTABLE
: KERN_SUCCESS
;
375 lock_release (lock_set_t lock_set
, int lock_id
)
379 if (lock_set
== LOCK_SET_NULL
)
380 return KERN_INVALID_ARGUMENT
;
382 if (lock_id
< 0 || lock_id
>= lock_set
->n_ulocks
)
383 return KERN_INVALID_ARGUMENT
;
385 ulock
= (ulock_t
) &lock_set
->ulock_list
[lock_id
];
387 return (ulock_release_internal(ulock
, current_thread()));
391 lock_try (lock_set_t lock_set
, int lock_id
)
396 if (lock_set
== LOCK_SET_NULL
)
397 return KERN_INVALID_ARGUMENT
;
399 if (lock_id
< 0 || lock_id
>= lock_set
->n_ulocks
)
400 return KERN_INVALID_ARGUMENT
;
403 lock_set_lock(lock_set
);
404 if (!lock_set
->active
) {
405 lock_set_unlock(lock_set
);
406 return KERN_LOCK_SET_DESTROYED
;
409 ulock
= (ulock_t
) &lock_set
->ulock_list
[lock_id
];
411 lock_set_unlock(lock_set
);
414 * If the lock is already owned, we return without blocking.
416 * An ownership status is returned to inform the caller as to
417 * whether it already holds the lock or another thread does.
420 if (ulock
->holder
!= THREAD_NULL
) {
421 lock_set_unlock(lock_set
);
423 if (ulock
->holder
== current_thread()) {
425 return KERN_LOCK_OWNED_SELF
;
429 return KERN_LOCK_OWNED
;
433 * Add the ulock to the lock set's held_ulocks list.
436 ulock_ownership_set(ulock
, current_thread());
439 return (ulock
->unstable
) ? KERN_LOCK_UNSTABLE
: KERN_SUCCESS
;
443 lock_make_stable (lock_set_t lock_set
, int lock_id
)
448 if (lock_set
== LOCK_SET_NULL
)
449 return KERN_INVALID_ARGUMENT
;
451 if (lock_id
< 0 || lock_id
>= lock_set
->n_ulocks
)
452 return KERN_INVALID_ARGUMENT
;
455 lock_set_lock(lock_set
);
456 if (!lock_set
->active
) {
457 lock_set_unlock(lock_set
);
458 return KERN_LOCK_SET_DESTROYED
;
461 ulock
= (ulock_t
) &lock_set
->ulock_list
[lock_id
];
463 lock_set_unlock(lock_set
);
465 if (ulock
->holder
!= current_thread()) {
467 return KERN_INVALID_RIGHT
;
470 ulock
->unstable
= FALSE
;
477 * ROUTINE: lock_make_unstable [internal]
479 * Marks the lock as unstable.
482 * - All future acquisitions of the lock will return with a
483 * KERN_LOCK_UNSTABLE status, until the lock is made stable again.
486 lock_make_unstable (ulock_t ulock
, thread_t thread
)
490 lock_set
= ulock
->lock_set
;
491 lock_set_lock(lock_set
);
492 if (!lock_set
->active
) {
493 lock_set_unlock(lock_set
);
494 return KERN_LOCK_SET_DESTROYED
;
498 lock_set_unlock(lock_set
);
500 if (ulock
->holder
!= thread
) {
502 return KERN_INVALID_RIGHT
;
505 ulock
->unstable
= TRUE
;
512 * ROUTINE: ulock_release_internal [internal]
514 * Releases the ulock.
515 * If any threads are blocked waiting for the ulock, one is woken-up.
519 ulock_release_internal (ulock_t ulock
, thread_t thread
)
523 if ((lock_set
= ulock
->lock_set
) == LOCK_SET_NULL
)
524 return KERN_INVALID_ARGUMENT
;
526 lock_set_lock(lock_set
);
527 if (!lock_set
->active
) {
528 lock_set_unlock(lock_set
);
529 return KERN_LOCK_SET_DESTROYED
;
532 lock_set_unlock(lock_set
);
534 if (ulock
->holder
!= thread
) {
536 return KERN_INVALID_RIGHT
;
540 * If we have a hint that threads might be waiting,
541 * try to transfer the lock ownership to a waiting thread
544 if (ulock
->blocked
) {
545 wait_queue_t wq
= &ulock
->wait_queue
;
551 wqthread
= wait_queue_wakeup64_identity_locked(wq
,
555 /* wait_queue now unlocked, thread locked */
557 if (wqthread
!= THREAD_NULL
) {
558 thread_unlock(wqthread
);
562 * Transfer ulock ownership
563 * from the current thread to the acquisition thread.
565 ulock_ownership_clear(ulock
);
566 ulock_ownership_set(ulock
, wqthread
);
571 ulock
->blocked
= FALSE
;
579 ulock_ownership_clear(ulock
);
586 lock_handoff (lock_set_t lock_set
, int lock_id
)
592 if (lock_set
== LOCK_SET_NULL
)
593 return KERN_INVALID_ARGUMENT
;
595 if (lock_id
< 0 || lock_id
>= lock_set
->n_ulocks
)
596 return KERN_INVALID_ARGUMENT
;
599 lock_set_lock(lock_set
);
601 if (!lock_set
->active
) {
602 lock_set_unlock(lock_set
);
603 return KERN_LOCK_SET_DESTROYED
;
606 ulock
= (ulock_t
) &lock_set
->ulock_list
[lock_id
];
608 lock_set_unlock(lock_set
);
610 if (ulock
->holder
!= current_thread()) {
612 return KERN_INVALID_RIGHT
;
616 * If the accepting thread (the receiver) is already waiting
617 * to accept the lock from the handoff thread (the sender),
618 * then perform the hand-off now.
621 if (ulock
->accept_wait
) {
622 wait_queue_t wq
= &ulock
->wait_queue
;
627 * See who the lucky devil is, if he is still there waiting.
631 thread
= wait_queue_wakeup64_identity_locked(
636 /* wait queue unlocked, thread locked */
639 * Transfer lock ownership
641 if (thread
!= THREAD_NULL
) {
643 * The thread we are transferring to will try
644 * to take the lock on the ulock, and therefore
645 * will wait for us complete the handoff even
646 * through we set the thread running.
648 thread_unlock(thread
);
651 ulock_ownership_clear(ulock
);
652 ulock_ownership_set(ulock
, thread
);
653 ulock
->accept_wait
= FALSE
;
659 * OOPS. The accepting thread must have been aborted.
660 * and is racing back to clear the flag that says is
661 * waiting for an accept. He will clear it when we
662 * release the lock, so just fall thru and wait for
663 * the next accept thread (that's the way it is
671 * Indicate that there is a hand-off thread waiting, and then wait
672 * for an accepting thread.
674 ulock
->ho_wait
= TRUE
;
675 wait_result
= wait_queue_assert_wait64(&ulock
->wait_queue
,
677 THREAD_ABORTSAFE
, 0);
680 if (wait_result
== THREAD_WAITING
)
681 wait_result
= thread_block(THREAD_CONTINUE_NULL
);
684 * If the thread was woken-up via some action other than
685 * lock_handoff_accept or lock_set_destroy (i.e. thread_terminate),
686 * then we need to clear the ulock's handoff state.
688 switch (wait_result
) {
691 case THREAD_AWAKENED
:
693 * we take the ulock lock to syncronize with the
694 * thread that is accepting ownership.
697 assert(ulock
->holder
!= current_thread());
701 case THREAD_INTERRUPTED
:
703 assert(ulock
->holder
== current_thread());
704 ulock
->ho_wait
= FALSE
;
712 panic("lock_handoff");
717 lock_handoff_accept (lock_set_t lock_set
, int lock_id
)
723 if (lock_set
== LOCK_SET_NULL
)
724 return KERN_INVALID_ARGUMENT
;
726 if (lock_id
< 0 || lock_id
>= lock_set
->n_ulocks
)
727 return KERN_INVALID_ARGUMENT
;
730 lock_set_lock(lock_set
);
731 if (!lock_set
->active
) {
732 lock_set_unlock(lock_set
);
733 return KERN_LOCK_SET_DESTROYED
;
736 ulock
= (ulock_t
) &lock_set
->ulock_list
[lock_id
];
738 lock_set_unlock(lock_set
);
741 * If there is another accepting thread that beat us, just
742 * return with an error.
744 if (ulock
->accept_wait
) {
746 return KERN_ALREADY_WAITING
;
749 if (ulock
->holder
== current_thread()) {
751 return KERN_LOCK_OWNED_SELF
;
755 * If the handoff thread (the sender) is already waiting to
756 * hand-off the lock to the accepting thread (the receiver),
757 * then perform the hand-off now.
759 if (ulock
->ho_wait
) {
760 wait_queue_t wq
= &ulock
->wait_queue
;
763 * See who the lucky devil is, if he is still there waiting.
765 assert(ulock
->holder
!= THREAD_NULL
);
767 if (wait_queue_wakeup64_thread(wq
,
770 THREAD_AWAKENED
) == KERN_SUCCESS
) {
772 * Holder thread was still waiting to give it
773 * away. Take over ownership.
775 ulock_ownership_clear(ulock
);
776 ulock_ownership_set(ulock
, current_thread());
777 ulock
->ho_wait
= FALSE
;
779 return (ulock
->unstable
) ? KERN_LOCK_UNSTABLE
:
784 * OOPS. The owner was aborted out of the handoff.
785 * He will clear his own flag when he gets back.
786 * in the meantime, we will wait as if we didn't
787 * even see his flag (by falling thru).
791 ulock
->accept_wait
= TRUE
;
792 wait_result
= wait_queue_assert_wait64(&ulock
->wait_queue
,
794 THREAD_ABORTSAFE
, 0);
797 if (wait_result
== THREAD_WAITING
)
798 wait_result
= thread_block(THREAD_CONTINUE_NULL
);
801 * If the thread was woken-up via some action other than
802 * lock_handoff_accept or lock_set_destroy (i.e. thread_terminate),
803 * then we need to clear the ulock's handoff state.
805 switch (wait_result
) {
807 case THREAD_AWAKENED
:
809 * Take the lock to synchronize with the thread handing
810 * off the lock to us. We don't want to continue until
811 * they complete the handoff.
814 assert(ulock
->accept_wait
== FALSE
);
815 assert(ulock
->holder
== current_thread());
819 case THREAD_INTERRUPTED
:
821 ulock
->accept_wait
= FALSE
;
829 panic("lock_handoff_accept");
834 * Routine: lock_set_reference
836 * Take out a reference on a lock set. This keeps the data structure
837 * in existence (but the lock set may be deactivated).
840 lock_set_reference(lock_set_t lock_set
)
842 OSIncrementAtomic(&((lock_set
)->ref_count
));
846 * Routine: lock_set_dereference
848 * Release a reference on a lock set. If this is the last reference,
849 * the lock set data structure is deallocated.
852 lock_set_dereference(lock_set_t lock_set
)
856 if (1 == OSDecrementAtomic(&((lock_set
)->ref_count
))) {
857 ipc_port_dealloc_kernel(lock_set
->port
);
858 size
= (int)(sizeof(struct lock_set
) +
859 (sizeof(struct ulock
) * (lock_set
->n_ulocks
- 1)));
860 kfree(lock_set
, size
);
870 while (!queue_empty(&thread
->held_ulocks
)) {
871 ulock
= (ulock_t
)queue_first(&thread
->held_ulocks
);
872 lock_make_unstable(ulock
, thread
);
873 ulock_release_internal(ulock
, thread
);