1/*
2 * i386 semaphore implementation.
3 *
4 * (C) Copyright 1999 Linus Torvalds
5 *
6 * Portions Copyright 1999 Red Hat, Inc.
7 *
8 *	This program is free software; you can redistribute it and/or
9 *	modify it under the terms of the GNU General Public License
10 *	as published by the Free Software Foundation; either version
11 *	2 of the License, or (at your option) any later version.
12 *
13 * rw semaphores implemented November 1999 by Benjamin LaHaise <bcrl@redhat.com>
14 */
15#include <linux/config.h>
16#include <linux/sched.h>
17#include <asm/semaphore.h>
18#include <asm/kernprof.h>
19
20/*
21 * Semaphores are implemented using a two-way counter:
22 * The "count" variable is decremented for each process
23 * that tries to acquire the semaphore, while the "sleeping"
24 * variable is a count of such acquires.
25 *
26 * Notably, the inline "up()" and "down()" functions can
27 * efficiently test if they need to do any extra work (up
28 * needs to do something only if count was negative before
29 * the increment operation.
30 *
31 * "sleeping" and the contention routine ordering is
32 * protected by the semaphore spinlock.
33 *
34 * Note that these functions are only called when there is
35 * contention on the lock, and as such all this is the
36 * "non-critical" part of the whole semaphore business. The
37 * critical part is the inline stuff in <asm/semaphore.h>
38 * where we want to avoid any extra jumps and calls.
39 */
40
41/*
42 * Logic:
43 *  - only on a boundary condition do we need to care. When we go
44 *    from a negative count to a non-negative, we wake people up.
45 *  - when we go from a non-negative count to a negative do we
46 *    (a) synchronize with the "sleeper" count and (b) make sure
47 *    that we're on the wakeup list before we synchronize so that
48 *    we cannot lose wakeup events.
49 */
50
51void __up(struct semaphore *sem)
52{
53	wake_up(&sem->wait);
54}
55
56static spinlock_t semaphore_lock = SPIN_LOCK_UNLOCKED;
57
58void __down(struct semaphore * sem)
59{
60	struct task_struct *tsk = current;
61	DECLARE_WAITQUEUE(wait, tsk);
62	tsk->state = TASK_UNINTERRUPTIBLE;
63	add_wait_queue_exclusive(&sem->wait, &wait);
64
65	spin_lock_irq(&semaphore_lock);
66	sem->sleepers++;
67	for (;;) {
68		int sleepers = sem->sleepers;
69
70		/*
71		 * Add "everybody else" into it. They aren't
72		 * playing, because we own the spinlock.
73		 */
74		if (!atomic_add_negative(sleepers - 1, &sem->count)) {
75			sem->sleepers = 0;
76			break;
77		}
78		sem->sleepers = 1;	/* us - see -1 above */
79		spin_unlock_irq(&semaphore_lock);
80
81		schedule();
82		tsk->state = TASK_UNINTERRUPTIBLE;
83		spin_lock_irq(&semaphore_lock);
84	}
85	spin_unlock_irq(&semaphore_lock);
86	remove_wait_queue(&sem->wait, &wait);
87	tsk->state = TASK_RUNNING;
88	wake_up(&sem->wait);
89}
90
91int __down_interruptible(struct semaphore * sem)
92{
93	int retval = 0;
94	struct task_struct *tsk = current;
95	DECLARE_WAITQUEUE(wait, tsk);
96	tsk->state = TASK_INTERRUPTIBLE;
97	add_wait_queue_exclusive(&sem->wait, &wait);
98
99	spin_lock_irq(&semaphore_lock);
100	sem->sleepers ++;
101	for (;;) {
102		int sleepers = sem->sleepers;
103
104		/*
105		 * With signals pending, this turns into
106		 * the trylock failure case - we won't be
107		 * sleeping, and we* can't get the lock as
108		 * it has contention. Just correct the count
109		 * and exit.
110		 */
111		if (signal_pending(current)) {
112			retval = -EINTR;
113			sem->sleepers = 0;
114			atomic_add(sleepers, &sem->count);
115			break;
116		}
117
118		/*
119		 * Add "everybody else" into it. They aren't
120		 * playing, because we own the spinlock. The
121		 * "-1" is because we're still hoping to get
122		 * the lock.
123		 */
124		if (!atomic_add_negative(sleepers - 1, &sem->count)) {
125			sem->sleepers = 0;
126			break;
127		}
128		sem->sleepers = 1;	/* us - see -1 above */
129		spin_unlock_irq(&semaphore_lock);
130
131		schedule();
132		tsk->state = TASK_INTERRUPTIBLE;
133		spin_lock_irq(&semaphore_lock);
134	}
135	spin_unlock_irq(&semaphore_lock);
136	tsk->state = TASK_RUNNING;
137	remove_wait_queue(&sem->wait, &wait);
138	wake_up(&sem->wait);
139	return retval;
140}
141
142/*
143 * Trylock failed - make sure we correct for
144 * having decremented the count.
145 *
146 * We could have done the trylock with a
147 * single "cmpxchg" without failure cases,
148 * but then it wouldn't work on a 386.
149 */
150int __down_trylock(struct semaphore * sem)
151{
152	int sleepers;
153	unsigned long flags;
154
155	spin_lock_irqsave(&semaphore_lock, flags);
156	sleepers = sem->sleepers + 1;
157	sem->sleepers = 0;
158
159	/*
160	 * Add "everybody else" and us into it. They aren't
161	 * playing, because we own the spinlock.
162	 */
163	if (!atomic_add_negative(sleepers, &sem->count))
164		wake_up(&sem->wait);
165
166	spin_unlock_irqrestore(&semaphore_lock, flags);
167	return 1;
168}
169
170
171/*
172 * The semaphore operations have a special calling sequence that
173 * allow us to do a simpler in-line version of them. These routines
174 * need to convert that sequence back into the C sequence when
175 * there is contention on the semaphore.
176 *
177 * %ecx contains the semaphore pointer on entry. Save the C-clobbered
178 * registers (%eax, %edx and %ecx) except %eax when used as a return
179 * value..
180 */
181asm(
182".text\n"
183".align 4\n"
184".globl __down_failed\n"
185"__down_failed:\n\t"
186	MCOUNT_STEXT_LOCK"\n\t"
187#if defined(CONFIG_FRAME_POINTER)
188	"pushl %ebp\n\t"
189	"movl  %esp,%ebp\n\t"
190#endif
191	"pushl %eax\n\t"
192	"pushl %edx\n\t"
193	"pushl %ecx\n\t"
194	"call __down\n\t"
195	"popl %ecx\n\t"
196	"popl %edx\n\t"
197	"popl %eax\n\t"
198#if defined(CONFIG_FRAME_POINTER)
199	"movl %ebp,%esp\n\t"
200	"popl %ebp\n\t"
201#endif
202	"ret"
203);
204
205asm(
206".text\n"
207".align 4\n"
208".globl __down_failed_interruptible\n"
209"__down_failed_interruptible:\n\t"
210	MCOUNT_STEXT_LOCK"\n\t"
211#if defined(CONFIG_FRAME_POINTER)
212	"pushl %ebp\n\t"
213	"movl  %esp,%ebp\n\t"
214#endif
215	"pushl %edx\n\t"
216	"pushl %ecx\n\t"
217	"call __down_interruptible\n\t"
218	"popl %ecx\n\t"
219	"popl %edx\n\t"
220#if defined(CONFIG_FRAME_POINTER)
221	"movl %ebp,%esp\n\t"
222	"popl %ebp\n\t"
223#endif
224	"ret"
225);
226
227asm(
228".text\n"
229".align 4\n"
230".globl __down_failed_trylock\n"
231"__down_failed_trylock:\n\t"
232	MCOUNT_STEXT_LOCK"\n\t"
233#if defined(CONFIG_FRAME_POINTER)
234	"pushl %ebp\n\t"
235	"movl  %esp,%ebp\n\t"
236#endif
237	"pushl %edx\n\t"
238	"pushl %ecx\n\t"
239	"call __down_trylock\n\t"
240	"popl %ecx\n\t"
241	"popl %edx\n\t"
242#if defined(CONFIG_FRAME_POINTER)
243	"movl %ebp,%esp\n\t"
244	"popl %ebp\n\t"
245#endif
246	"ret"
247);
248
249asm(
250".text\n"
251".align 4\n"
252".globl __up_wakeup\n"
253"__up_wakeup:\n\t"
254	MCOUNT_STEXT_LOCK"\n\t"
255	"pushl %eax\n\t"
256	"pushl %edx\n\t"
257	"pushl %ecx\n\t"
258	"call __up\n\t"
259	"popl %ecx\n\t"
260	"popl %edx\n\t"
261	"popl %eax\n\t"
262	"ret"
263);
264
265/*
266 * rw spinlock fallbacks
267 */
268#if defined(CONFIG_SMP)
269asm(
270".text\n"
271".align	4\n"
272".globl	__write_lock_failed\n"
273"__write_lock_failed:\n\t"
274	LOCK "addl	$" RW_LOCK_BIAS_STR ",(%eax)\n"
275"1:	rep; nop\n\t"
276	"cmpl	$" RW_LOCK_BIAS_STR ",(%eax)\n\t"
277	"jne	1b\n\t"
278	LOCK "subl	$" RW_LOCK_BIAS_STR ",(%eax)\n\t"
279	"jnz	__write_lock_failed\n\t"
280	"ret"
281);
282
283asm(
284".text\n"
285".align	4\n"
286".globl	__read_lock_failed\n"
287"__read_lock_failed:\n\t"
288	LOCK "incl	(%eax)\n"
289"1:	rep; nop\n\t"
290	"cmpl	$1,(%eax)\n\t"
291	"js	1b\n\t"
292	LOCK "decl	(%eax)\n\t"
293	"js	__read_lock_failed\n\t"
294	"ret"
295);
296#endif
297