2 * Copyright (C) 1999, 2001, 02, 03 Ralf Baechle
4 * Heavily inspired by the Alpha implementation
6 #include <linux/config.h>
7 #include <linux/errno.h>
8 #include <linux/module.h>
9 #include <linux/sched.h>
11 #ifndef CONFIG_CPU_HAS_LLDSCD
13 * On machines without lld/scd we need a spinlock to make the manipulation of
14 * sem->count and sem->waking atomic. Scalability isn't an issue because
15 * this lock is used on UP only so it's just an empty variable.
17 spinlock_t semaphore_lock = SPIN_LOCK_UNLOCKED;
19 EXPORT_SYMBOL(semaphore_lock);
23 * Semaphores are implemented using a two-way counter: The "count" variable is
24 * decremented for each process that tries to sleep, while the "waking" variable
25 * is incremented when the "up()" code goes to wake up waiting processes.
27 * Notably, the inline "up()" and "down()" functions can efficiently test if
28 * they need to do any extra work (up needs to do something only if count was
29 * negative before the increment operation.
31 * waking_non_zero() must execute atomically.
33 * When __up() is called, the count was negative before incrementing it, and we
34 * need to wake up somebody.
36 * This routine adds one to the count of processes that need to wake up and
37 * exit. ALL waiting processes actually wake up but only the one that gets to
38 * the "waking" field first will gate through and acquire the semaphore. The
39 * others will go back to sleep.
41 * Note that these functions are only called when there is contention on the
42 * lock, and as such all this is the "non-critical" part of the whole semaphore
43 * business. The critical part is the inline stuff in <asm/semaphore.h> where
44 * we want to avoid any extra jumps and calls.
46 void __up_wakeup(struct semaphore *sem)
51 EXPORT_SYMBOL(__up_wakeup);
53 #ifdef CONFIG_CPU_HAS_LLSC
55 static inline int waking_non_zero(struct semaphore *sem)
60 "1: ll %1, %2 # waking_non_zero \n"
66 : "=r" (ret), "=r" (tmp), "+m" (sem->waking)
72 #else /* !CONFIG_CPU_HAS_LLSC */
74 static inline int waking_non_zero(struct semaphore *sem)
79 spin_lock_irqsave(&semaphore_lock, flags);
80 waking = atomic_read(&sem->waking);
82 atomic_set(&sem->waking, waking - 1);
85 spin_unlock_irqrestore(&semaphore_lock, flags);
90 #endif /* !CONFIG_CPU_HAS_LLSC */
93 * Perform the "down" function. Return zero for semaphore acquired, return
94 * negative for signalled out of the function.
96 * If called from down, the return is ignored and the wait loop is not
97 * interruptible. This means that a task waiting on a semaphore using "down()"
98 * cannot be killed until someone does an "up()" on the semaphore.
100 * If called from down_interruptible, the return value gets checked upon return.
101 * If the return value is negative then the task continues with the negative
102 * value in the return register (it can be tested by the caller).
104 * Either form may be used in conjunction with "up()".
107 void __down_failed(struct semaphore * sem)
109 struct task_struct *tsk = current;
112 init_waitqueue_entry(&wait, tsk);
113 __set_current_state(TASK_UNINTERRUPTIBLE);
114 add_wait_queue_exclusive(&sem->wait, &wait);
117 * Ok, we're set up. sem->count is known to be less than zero
120 * We can let go the lock for purposes of waiting.
121 * We re-acquire it after awaking so as to protect
122 * all semaphore operations.
124 * If "up()" is called before we call waking_non_zero() then
125 * we will catch it right away. If it is called later then
126 * we will have to go through a wakeup cycle to catch it.
128 * Multiple waiters contend for the semaphore lock to see
129 * who gets to gate through and who has to wait some more.
132 if (waking_non_zero(sem))
135 __set_current_state(TASK_UNINTERRUPTIBLE);
137 __set_current_state(TASK_RUNNING);
138 remove_wait_queue(&sem->wait, &wait);
141 EXPORT_SYMBOL(__down_failed);
143 #ifdef CONFIG_CPU_HAS_LLDSCD
146 * waking_non_zero_interruptible:
151 * We must undo the sem->count down_interruptible decrement
152 * simultaneously and atomically with the sem->waking adjustment,
153 * otherwise we can race with wake_one_more.
155 * This is accomplished by doing a 64-bit lld/scd on the 2 32-bit words.
157 * This is crazy. Normally it's strictly forbidden to use 64-bit operations
158 * in the 32-bit MIPS kernel. In this case it's however ok because if an
159 * interrupt has destroyed the upper half of registers sc will fail.
160 * Note also that this will not work for MIPS32 CPUs!
164 * If(sem->waking > 0) {
165 * Decrement(sem->waking)
167 * } else If(signal_pending(tsk)) {
168 * Increment(sem->count)
176 waking_non_zero_interruptible(struct semaphore *sem, struct task_struct *tsk)
180 __asm__ __volatile__(
181 " .set push # waking_non_zero_interruptible \n"
188 " daddiu %1, %1, -1 \n"
193 " dli $1, 0x0000000100000000 \n"
194 " daddu %1, %1, $1 \n"
198 : "=&r" (ret), "=&r" (tmp), "=m" (*sem)
199 : "r" (signal_pending(tsk)), "i" (-EINTR));
204 #else /* !CONFIG_CPU_HAS_LLDSCD */
206 static inline int waking_non_zero_interruptible(struct semaphore *sem,
207 struct task_struct *tsk)
209 int waking, pending, ret = 0;
212 pending = signal_pending(tsk);
214 spin_lock_irqsave(&semaphore_lock, flags);
215 waking = atomic_read(&sem->waking);
217 atomic_set(&sem->waking, waking - 1);
219 } else if (pending) {
220 atomic_set(&sem->count, atomic_read(&sem->count) + 1);
223 spin_unlock_irqrestore(&semaphore_lock, flags);
228 #endif /* !CONFIG_CPU_HAS_LLDSCD */
230 int __down_failed_interruptible(struct semaphore * sem)
232 struct task_struct *tsk = current;
236 init_waitqueue_entry(&wait, tsk);
237 __set_current_state(TASK_INTERRUPTIBLE);
238 add_wait_queue_exclusive(&sem->wait, &wait);
241 * Ok, we're set up. sem->count is known to be less than zero
244 * We can let go the lock for purposes of waiting.
245 * We re-acquire it after awaking so as to protect
246 * all semaphore operations.
248 * If "up()" is called before we call waking_non_zero() then
249 * we will catch it right away. If it is called later then
250 * we will have to go through a wakeup cycle to catch it.
252 * Multiple waiters contend for the semaphore lock to see
253 * who gets to gate through and who has to wait some more.
256 ret = waking_non_zero_interruptible(sem, tsk);
259 /* ret != 0 only if we get interrupted -arca */
264 __set_current_state(TASK_INTERRUPTIBLE);
266 __set_current_state(TASK_RUNNING);
267 remove_wait_queue(&sem->wait, &wait);
272 EXPORT_SYMBOL(__down_failed_interruptible);