blob: 520a379f4b80490dd9e897d48120d89aef86bc13 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/* rwsem.h: R/W semaphores implemented using XADD/CMPXCHG for i486+
2 *
3 * Written by David Howells (dhowells@redhat.com).
4 *
Dave Jones99122a32008-01-30 13:30:28 +01005 * Derived from asm-x86/semaphore.h
Linus Torvalds1da177e2005-04-16 15:20:36 -07006 *
7 *
8 * The MSW of the count is the negated number of active writers and waiting
9 * lockers, and the LSW is the total number of active locks
10 *
11 * The lock count is initialized to 0 (no active and no waiting lockers).
12 *
13 * When a writer subtracts WRITE_BIAS, it'll get 0xffff0001 for the case of an
14 * uncontended lock. This can be determined because XADD returns the old value.
15 * Readers increment by 1 and see a positive value when uncontended, negative
16 * if there are writers (and maybe) readers waiting (in which case it goes to
17 * sleep).
18 *
19 * The value of WAITING_BIAS supports up to 32766 waiting processes. This can
20 * be extended to 65534 by manually checking the whole MSW rather than relying
21 * on the S flag.
22 *
23 * The value of ACTIVE_BIAS supports up to 65535 active processes.
24 *
25 * This should be totally fair - if anything is waiting, a process that wants a
26 * lock will go to the back of the queue. When the currently active lock is
27 * released, if there's a writer at the front of the queue, then that and only
28 * that will be woken up; if there's a bunch of consequtive readers at the
29 * front, then they'll all be woken up, but no other readers will be.
30 */
31
32#ifndef _I386_RWSEM_H
33#define _I386_RWSEM_H
34
35#ifndef _LINUX_RWSEM_H
36#error "please don't include asm/rwsem.h directly, use linux/rwsem.h instead"
37#endif
38
39#ifdef __KERNEL__
40
41#include <linux/list.h>
42#include <linux/spinlock.h>
Ingo Molnar4ea21762006-07-03 00:24:53 -070043#include <linux/lockdep.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070044
45struct rwsem_waiter;
46
Ingo Molnard50efc62008-01-30 13:33:00 +010047extern asmregparm struct rw_semaphore *
48 rwsem_down_read_failed(struct rw_semaphore *sem);
49extern asmregparm struct rw_semaphore *
50 rwsem_down_write_failed(struct rw_semaphore *sem);
51extern asmregparm struct rw_semaphore *
52 rwsem_wake(struct rw_semaphore *);
53extern asmregparm struct rw_semaphore *
54 rwsem_downgrade_wake(struct rw_semaphore *sem);
Linus Torvalds1da177e2005-04-16 15:20:36 -070055
56/*
57 * the semaphore definition
58 */
59struct rw_semaphore {
60 signed long count;
61#define RWSEM_UNLOCKED_VALUE 0x00000000
62#define RWSEM_ACTIVE_BIAS 0x00000001
63#define RWSEM_ACTIVE_MASK 0x0000ffff
64#define RWSEM_WAITING_BIAS (-0x00010000)
65#define RWSEM_ACTIVE_READ_BIAS RWSEM_ACTIVE_BIAS
66#define RWSEM_ACTIVE_WRITE_BIAS (RWSEM_WAITING_BIAS + RWSEM_ACTIVE_BIAS)
67 spinlock_t wait_lock;
68 struct list_head wait_list;
Ingo Molnar4ea21762006-07-03 00:24:53 -070069#ifdef CONFIG_DEBUG_LOCK_ALLOC
70 struct lockdep_map dep_map;
71#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -070072};
73
Ingo Molnar4ea21762006-07-03 00:24:53 -070074#ifdef CONFIG_DEBUG_LOCK_ALLOC
75# define __RWSEM_DEP_MAP_INIT(lockname) , .dep_map = { .name = #lockname }
76#else
77# define __RWSEM_DEP_MAP_INIT(lockname)
78#endif
79
80
Linus Torvalds1da177e2005-04-16 15:20:36 -070081#define __RWSEM_INITIALIZER(name) \
Peter Zijlstra6cfd76a2006-12-06 20:37:22 -080082{ RWSEM_UNLOCKED_VALUE, __SPIN_LOCK_UNLOCKED((name).wait_lock), \
83 LIST_HEAD_INIT((name).wait_list) __RWSEM_DEP_MAP_INIT(name) }
Linus Torvalds1da177e2005-04-16 15:20:36 -070084
85#define DECLARE_RWSEM(name) \
86 struct rw_semaphore name = __RWSEM_INITIALIZER(name)
87
Ingo Molnar4ea21762006-07-03 00:24:53 -070088extern void __init_rwsem(struct rw_semaphore *sem, const char *name,
89 struct lock_class_key *key);
90
91#define init_rwsem(sem) \
92do { \
93 static struct lock_class_key __key; \
94 \
95 __init_rwsem((sem), #sem, &__key); \
96} while (0)
Linus Torvalds1da177e2005-04-16 15:20:36 -070097
98/*
99 * lock for reading
100 */
101static inline void __down_read(struct rw_semaphore *sem)
102{
103 __asm__ __volatile__(
104 "# beginning down_read\n\t"
105LOCK_PREFIX " incl (%%eax)\n\t" /* adds 0x00000001, returns the old value */
Andi Kleenadd659b2006-09-26 10:52:31 +0200106 " jns 1f\n"
107 " call call_rwsem_down_read_failed\n"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700108 "1:\n\t"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700109 "# ending down_read\n\t"
Linus Torvaldsb862f3b2006-07-08 15:24:18 -0700110 : "+m" (sem->count)
111 : "a" (sem)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700112 : "memory", "cc");
113}
114
115/*
116 * trylock for reading -- returns 1 if successful, 0 if contention
117 */
118static inline int __down_read_trylock(struct rw_semaphore *sem)
119{
120 __s32 result, tmp;
121 __asm__ __volatile__(
122 "# beginning __down_read_trylock\n\t"
123 " movl %0,%1\n\t"
124 "1:\n\t"
125 " movl %1,%2\n\t"
126 " addl %3,%2\n\t"
127 " jle 2f\n\t"
128LOCK_PREFIX " cmpxchgl %2,%0\n\t"
129 " jnz 1b\n\t"
130 "2:\n\t"
131 "# ending __down_read_trylock\n\t"
Linus Torvaldsb862f3b2006-07-08 15:24:18 -0700132 : "+m" (sem->count), "=&a" (result), "=&r" (tmp)
133 : "i" (RWSEM_ACTIVE_READ_BIAS)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700134 : "memory", "cc");
135 return result>=0 ? 1 : 0;
136}
137
138/*
139 * lock for writing
140 */
Ingo Molnar4ea21762006-07-03 00:24:53 -0700141static inline void __down_write_nested(struct rw_semaphore *sem, int subclass)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700142{
143 int tmp;
144
145 tmp = RWSEM_ACTIVE_WRITE_BIAS;
146 __asm__ __volatile__(
147 "# beginning down_write\n\t"
148LOCK_PREFIX " xadd %%edx,(%%eax)\n\t" /* subtract 0x0000ffff, returns the old value */
149 " testl %%edx,%%edx\n\t" /* was the count 0 before? */
Andi Kleenadd659b2006-09-26 10:52:31 +0200150 " jz 1f\n"
151 " call call_rwsem_down_write_failed\n"
152 "1:\n"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700153 "# ending down_write"
Linus Torvaldsb862f3b2006-07-08 15:24:18 -0700154 : "+m" (sem->count), "=d" (tmp)
155 : "a" (sem), "1" (tmp)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700156 : "memory", "cc");
157}
158
Ingo Molnar4ea21762006-07-03 00:24:53 -0700159static inline void __down_write(struct rw_semaphore *sem)
160{
161 __down_write_nested(sem, 0);
162}
163
Linus Torvalds1da177e2005-04-16 15:20:36 -0700164/*
165 * trylock for writing -- returns 1 if successful, 0 if contention
166 */
167static inline int __down_write_trylock(struct rw_semaphore *sem)
168{
169 signed long ret = cmpxchg(&sem->count,
170 RWSEM_UNLOCKED_VALUE,
171 RWSEM_ACTIVE_WRITE_BIAS);
172 if (ret == RWSEM_UNLOCKED_VALUE)
173 return 1;
174 return 0;
175}
176
177/*
178 * unlock after reading
179 */
180static inline void __up_read(struct rw_semaphore *sem)
181{
182 __s32 tmp = -RWSEM_ACTIVE_READ_BIAS;
183 __asm__ __volatile__(
184 "# beginning __up_read\n\t"
185LOCK_PREFIX " xadd %%edx,(%%eax)\n\t" /* subtracts 1, returns the old value */
Andi Kleenadd659b2006-09-26 10:52:31 +0200186 " jns 1f\n\t"
187 " call call_rwsem_wake\n"
188 "1:\n"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700189 "# ending __up_read\n"
Linus Torvaldsb862f3b2006-07-08 15:24:18 -0700190 : "+m" (sem->count), "=d" (tmp)
191 : "a" (sem), "1" (tmp)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700192 : "memory", "cc");
193}
194
195/*
196 * unlock after writing
197 */
198static inline void __up_write(struct rw_semaphore *sem)
199{
200 __asm__ __volatile__(
201 "# beginning __up_write\n\t"
202 " movl %2,%%edx\n\t"
203LOCK_PREFIX " xaddl %%edx,(%%eax)\n\t" /* tries to transition 0xffff0001 -> 0x00000000 */
Andi Kleenadd659b2006-09-26 10:52:31 +0200204 " jz 1f\n"
205 " call call_rwsem_wake\n"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700206 "1:\n\t"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700207 "# ending __up_write\n"
Linus Torvaldsb862f3b2006-07-08 15:24:18 -0700208 : "+m" (sem->count)
209 : "a" (sem), "i" (-RWSEM_ACTIVE_WRITE_BIAS)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700210 : "memory", "cc", "edx");
211}
212
213/*
214 * downgrade write lock to read lock
215 */
216static inline void __downgrade_write(struct rw_semaphore *sem)
217{
218 __asm__ __volatile__(
219 "# beginning __downgrade_write\n\t"
220LOCK_PREFIX " addl %2,(%%eax)\n\t" /* transitions 0xZZZZ0001 -> 0xYYYY0001 */
Andi Kleenadd659b2006-09-26 10:52:31 +0200221 " jns 1f\n\t"
222 " call call_rwsem_downgrade_wake\n"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700223 "1:\n\t"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700224 "# ending __downgrade_write\n"
Linus Torvaldsb862f3b2006-07-08 15:24:18 -0700225 : "+m" (sem->count)
226 : "a" (sem), "i" (-RWSEM_WAITING_BIAS)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700227 : "memory", "cc");
228}
229
230/*
231 * implement atomic add functionality
232 */
233static inline void rwsem_atomic_add(int delta, struct rw_semaphore *sem)
234{
235 __asm__ __volatile__(
236LOCK_PREFIX "addl %1,%0"
Linus Torvaldsb862f3b2006-07-08 15:24:18 -0700237 : "+m" (sem->count)
238 : "ir" (delta));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700239}
240
241/*
242 * implement exchange and add functionality
243 */
244static inline int rwsem_atomic_update(int delta, struct rw_semaphore *sem)
245{
246 int tmp = delta;
247
248 __asm__ __volatile__(
Linus Torvaldsb862f3b2006-07-08 15:24:18 -0700249LOCK_PREFIX "xadd %0,%1"
250 : "+r" (tmp), "+m" (sem->count)
251 : : "memory");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700252
253 return tmp+delta;
254}
255
Rik Van Rieleb92f4e2005-10-29 18:15:44 -0700256static inline int rwsem_is_locked(struct rw_semaphore *sem)
257{
258 return (sem->count != 0);
259}
260
Linus Torvalds1da177e2005-04-16 15:20:36 -0700261#endif /* __KERNEL__ */
262#endif /* _I386_RWSEM_H */