File: /usr/src/linux/arch/alpha/kernel/semaphore.c
1 /*
2 * Alpha semaphore implementation.
3 *
4 * (C) Copyright 1996 Linus Torvalds
5 * (C) Copyright 1999, 2000 Richard Henderson
6 */
7
8 #include <linux/sched.h>
9
10
11 /*
12 * Semaphores are implemented using a two-way counter:
13 *
14 * The "count" variable is decremented for each process that tries to sleep,
15 * while the "waking" variable is incremented when the "up()" code goes to
16 * wake up waiting processes.
17 *
18 * Notably, the inline "up()" and "down()" functions can efficiently test
19 * if they need to do any extra work (up needs to do something only if count
20 * was negative before the increment operation.
21 *
22 * waking_non_zero() (from asm/semaphore.h) must execute atomically.
23 *
24 * When __up() is called, the count was negative before incrementing it,
25 * and we need to wake up somebody.
26 *
27 * This routine adds one to the count of processes that need to wake up and
28 * exit. ALL waiting processes actually wake up but only the one that gets
29 * to the "waking" field first will gate through and acquire the semaphore.
30 * The others will go back to sleep.
31 *
32 * Note that these functions are only called when there is contention on the
33 * lock, and as such all this is the "non-critical" part of the whole
34 * semaphore business. The critical part is the inline stuff in
35 * <asm/semaphore.h> where we want to avoid any extra jumps and calls.
36 */
37
38 /*
39 * Perform the "down" function. Return zero for semaphore acquired,
40 * return negative for signalled out of the function.
41 *
42 * If called from down, the return is ignored and the wait loop is
43 * not interruptible. This means that a task waiting on a semaphore
44 * using "down()" cannot be killed until someone does an "up()" on
45 * the semaphore.
46 *
47 * If called from down_interruptible, the return value gets checked
48 * upon return. If the return value is negative then the task continues
49 * with the negative value in the return register (it can be tested by
50 * the caller).
51 *
52 * Either form may be used in conjunction with "up()".
53 */
54
55 void
56 __down_failed(struct semaphore *sem)
57 {
58 DECLARE_WAITQUEUE(wait, current);
59
60 #if DEBUG_SEMAPHORE
61 printk("%s(%d): down failed(%p)\n",
62 current->comm, current->pid, sem);
63 #endif
64
65 current->state = TASK_UNINTERRUPTIBLE;
66 wmb();
67 add_wait_queue_exclusive(&sem->wait, &wait);
68
69 /* At this point we know that sem->count is negative. In order
70 to avoid racing with __up, we must check for wakeup before
71 going to sleep the first time. */
72
73 while (1) {
74 long ret, tmp;
75
76 /* An atomic conditional decrement of sem->waking. */
77 __asm__ __volatile__(
78 "1: ldl_l %1,%2\n"
79 " blt %1,2f\n"
80 " subl %1,1,%0\n"
81 " stl_c %0,%2\n"
82 " beq %0,3f\n"
83 "2:\n"
84 ".subsection 2\n"
85 "3: br 1b\n"
86 ".previous"
87 : "=r"(ret), "=&r"(tmp), "=m"(sem->waking)
88 : "0"(0));
89
90 if (ret)
91 break;
92
93 schedule();
94 set_task_state(current, TASK_UNINTERRUPTIBLE);
95 }
96
97 remove_wait_queue(&sem->wait, &wait);
98 current->state = TASK_RUNNING;
99
100 #if DEBUG_SEMAPHORE
101 printk("%s(%d): down acquired(%p)\n",
102 current->comm, current->pid, sem);
103 #endif
104 }
105
106 int
107 __down_failed_interruptible(struct semaphore *sem)
108 {
109 DECLARE_WAITQUEUE(wait, current);
110 long ret;
111
112 #if DEBUG_SEMAPHORE
113 printk("%s(%d): down failed(%p)\n",
114 current->comm, current->pid, sem);
115 #endif
116
117 current->state = TASK_INTERRUPTIBLE;
118 wmb();
119 add_wait_queue_exclusive(&sem->wait, &wait);
120
121 while (1) {
122 long tmp, tmp2, tmp3;
123
124 /* We must undo the sem->count down_interruptible decrement
125 simultaneously and atomicly with the sem->waking
126 adjustment, otherwise we can race with __up. This is
127 accomplished by doing a 64-bit ll/sc on two 32-bit words.
128
129 "Equivalent" C. Note that we have to do this all without
130 (taken) branches in order to be a valid ll/sc sequence.
131
132 do {
133 tmp = ldq_l;
134 ret = 0;
135 if (tmp >= 0) { // waking >= 0
136 tmp += 0xffffffff00000000; // waking -= 1
137 ret = 1;
138 }
139 else if (pending) {
140 // count += 1, but since -1 + 1 carries into the
141 // high word, we have to be more careful here.
142 tmp = (tmp & 0xffffffff00000000)
143 | ((tmp + 1) & 0x00000000ffffffff);
144 ret = -EINTR;
145 }
146 tmp = stq_c = tmp;
147 } while (tmp == 0);
148 */
149
150 __asm__ __volatile__(
151 "1: ldq_l %1,%4\n"
152 " lda %0,0\n"
153 " cmovne %5,%6,%0\n"
154 " addq %1,1,%2\n"
155 " and %1,%7,%3\n"
156 " andnot %2,%7,%2\n"
157 " cmovge %1,1,%0\n"
158 " or %3,%2,%2\n"
159 " addq %1,%7,%3\n"
160 " cmovne %5,%2,%1\n"
161 " cmovge %2,%3,%1\n"
162 " stq_c %1,%4\n"
163 " beq %1,3f\n"
164 "2:\n"
165 ".subsection 2\n"
166 "3: br 1b\n"
167 ".previous"
168 : "=&r"(ret), "=&r"(tmp), "=&r"(tmp2),
169 "=&r"(tmp3), "=m"(*sem)
170 : "r"(signal_pending(current)), "r"(-EINTR),
171 "r"(0xffffffff00000000));
172
173 /* At this point we have ret
174 1 got the lock
175 0 go to sleep
176 -EINTR interrupted */
177 if (ret != 0)
178 break;
179
180 schedule();
181 set_task_state(current, TASK_INTERRUPTIBLE);
182 }
183
184 remove_wait_queue(&sem->wait, &wait);
185 current->state = TASK_RUNNING;
186 wake_up(&sem->wait);
187
188 #if DEBUG_SEMAPHORE
189 printk("%s(%d): down %s(%p)\n",
190 current->comm, current->pid,
191 (ret < 0 ? "interrupted" : "acquired"), sem);
192 #endif
193
194 /* Convert "got the lock" to 0==success. */
195 return (ret < 0 ? ret : 0);
196 }
197
198 void
199 __up_wakeup(struct semaphore *sem)
200 {
201 wake_up(&sem->wait);
202 }
203
204 void
205 down(struct semaphore *sem)
206 {
207 #if WAITQUEUE_DEBUG
208 CHECK_MAGIC(sem->__magic);
209 #endif
210 #if DEBUG_SEMAPHORE
211 printk("%s(%d): down(%p) <count=%d> from %p\n",
212 current->comm, current->pid, sem,
213 atomic_read(&sem->count), __builtin_return_address(0));
214 #endif
215 __down(sem);
216 }
217
218 int
219 down_interruptible(struct semaphore *sem)
220 {
221 #if WAITQUEUE_DEBUG
222 CHECK_MAGIC(sem->__magic);
223 #endif
224 #if DEBUG_SEMAPHORE
225 printk("%s(%d): down(%p) <count=%d> from %p\n",
226 current->comm, current->pid, sem,
227 atomic_read(&sem->count), __builtin_return_address(0));
228 #endif
229 return __down_interruptible(sem);
230 }
231
232 int
233 down_trylock(struct semaphore *sem)
234 {
235 int ret;
236
237 #if WAITQUEUE_DEBUG
238 CHECK_MAGIC(sem->__magic);
239 #endif
240
241 ret = __down_trylock(sem);
242
243 #if DEBUG_SEMAPHORE
244 printk("%s(%d): down_trylock %s from %p\n",
245 current->comm, current->pid,
246 ret ? "failed" : "acquired",
247 __builtin_return_address(0));
248 #endif
249
250 return ret;
251 }
252
253 void
254 up(struct semaphore *sem)
255 {
256 #if WAITQUEUE_DEBUG
257 CHECK_MAGIC(sem->__magic);
258 #endif
259 #if DEBUG_SEMAPHORE
260 printk("%s(%d): up(%p) <count=%d> from %p\n",
261 current->comm, current->pid, sem,
262 atomic_read(&sem->count), __builtin_return_address(0));
263 #endif
264 __up(sem);
265 }
266