blob: 750f2a3542b3931044e77835dceac28457bbece8 [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 */
Joe Perches6e5609a2008-03-23 01:03:21 -070059
Linus Torvalds1da177e2005-04-16 15:20:36 -070060#define RWSEM_UNLOCKED_VALUE 0x00000000
61#define RWSEM_ACTIVE_BIAS 0x00000001
62#define RWSEM_ACTIVE_MASK 0x0000ffff
63#define RWSEM_WAITING_BIAS (-0x00010000)
64#define RWSEM_ACTIVE_READ_BIAS RWSEM_ACTIVE_BIAS
65#define RWSEM_ACTIVE_WRITE_BIAS (RWSEM_WAITING_BIAS + RWSEM_ACTIVE_BIAS)
Joe Perches6e5609a2008-03-23 01:03:21 -070066
67struct rw_semaphore {
68 signed long count;
Linus Torvalds1da177e2005-04-16 15:20:36 -070069 spinlock_t wait_lock;
70 struct list_head wait_list;
Ingo Molnar4ea21762006-07-03 00:24:53 -070071#ifdef CONFIG_DEBUG_LOCK_ALLOC
72 struct lockdep_map dep_map;
73#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -070074};
75
Ingo Molnar4ea21762006-07-03 00:24:53 -070076#ifdef CONFIG_DEBUG_LOCK_ALLOC
77# define __RWSEM_DEP_MAP_INIT(lockname) , .dep_map = { .name = #lockname }
78#else
79# define __RWSEM_DEP_MAP_INIT(lockname)
80#endif
81
82
Joe Perches6e5609a2008-03-23 01:03:21 -070083#define __RWSEM_INITIALIZER(name) \
84{ \
85 RWSEM_UNLOCKED_VALUE, __SPIN_LOCK_UNLOCKED((name).wait_lock), \
86 LIST_HEAD_INIT((name).wait_list) __RWSEM_DEP_MAP_INIT(name) \
87}
Linus Torvalds1da177e2005-04-16 15:20:36 -070088
Joe Perches6e5609a2008-03-23 01:03:21 -070089#define DECLARE_RWSEM(name) \
Linus Torvalds1da177e2005-04-16 15:20:36 -070090 struct rw_semaphore name = __RWSEM_INITIALIZER(name)
91
Ingo Molnar4ea21762006-07-03 00:24:53 -070092extern void __init_rwsem(struct rw_semaphore *sem, const char *name,
93 struct lock_class_key *key);
94
95#define init_rwsem(sem) \
96do { \
97 static struct lock_class_key __key; \
98 \
99 __init_rwsem((sem), #sem, &__key); \
100} while (0)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700101
102/*
103 * lock for reading
104 */
105static inline void __down_read(struct rw_semaphore *sem)
106{
Joe Perches6e5609a2008-03-23 01:03:21 -0700107 asm volatile("# beginning down_read\n\t"
108 LOCK_PREFIX " incl (%%eax)\n\t"
109 /* adds 0x00000001, returns the old value */
110 " jns 1f\n"
111 " call call_rwsem_down_read_failed\n"
112 "1:\n\t"
113 "# ending down_read\n\t"
114 : "+m" (sem->count)
115 : "a" (sem)
116 : "memory", "cc");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700117}
118
119/*
120 * trylock for reading -- returns 1 if successful, 0 if contention
121 */
122static inline int __down_read_trylock(struct rw_semaphore *sem)
123{
124 __s32 result, tmp;
Joe Perches6e5609a2008-03-23 01:03:21 -0700125 asm volatile("# beginning __down_read_trylock\n\t"
126 " movl %0,%1\n\t"
127 "1:\n\t"
128 " movl %1,%2\n\t"
129 " addl %3,%2\n\t"
130 " jle 2f\n\t"
131 LOCK_PREFIX " cmpxchgl %2,%0\n\t"
132 " jnz 1b\n\t"
133 "2:\n\t"
134 "# ending __down_read_trylock\n\t"
135 : "+m" (sem->count), "=&a" (result), "=&r" (tmp)
136 : "i" (RWSEM_ACTIVE_READ_BIAS)
137 : "memory", "cc");
138 return result >= 0 ? 1 : 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700139}
140
141/*
142 * lock for writing
143 */
Ingo Molnar4ea21762006-07-03 00:24:53 -0700144static inline void __down_write_nested(struct rw_semaphore *sem, int subclass)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700145{
146 int tmp;
147
148 tmp = RWSEM_ACTIVE_WRITE_BIAS;
Joe Perches6e5609a2008-03-23 01:03:21 -0700149 asm volatile("# beginning down_write\n\t"
150 LOCK_PREFIX " xadd %%edx,(%%eax)\n\t"
151 /* subtract 0x0000ffff, returns the old value */
152 " testl %%edx,%%edx\n\t"
153 /* was the count 0 before? */
154 " jz 1f\n"
155 " call call_rwsem_down_write_failed\n"
156 "1:\n"
157 "# ending down_write"
158 : "+m" (sem->count), "=d" (tmp)
159 : "a" (sem), "1" (tmp)
160 : "memory", "cc");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700161}
162
Ingo Molnar4ea21762006-07-03 00:24:53 -0700163static inline void __down_write(struct rw_semaphore *sem)
164{
165 __down_write_nested(sem, 0);
166}
167
Linus Torvalds1da177e2005-04-16 15:20:36 -0700168/*
169 * trylock for writing -- returns 1 if successful, 0 if contention
170 */
171static inline int __down_write_trylock(struct rw_semaphore *sem)
172{
173 signed long ret = cmpxchg(&sem->count,
Joe Perches6e5609a2008-03-23 01:03:21 -0700174 RWSEM_UNLOCKED_VALUE,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700175 RWSEM_ACTIVE_WRITE_BIAS);
176 if (ret == RWSEM_UNLOCKED_VALUE)
177 return 1;
178 return 0;
179}
180
181/*
182 * unlock after reading
183 */
184static inline void __up_read(struct rw_semaphore *sem)
185{
186 __s32 tmp = -RWSEM_ACTIVE_READ_BIAS;
Joe Perches6e5609a2008-03-23 01:03:21 -0700187 asm volatile("# beginning __up_read\n\t"
188 LOCK_PREFIX " xadd %%edx,(%%eax)\n\t"
189 /* subtracts 1, returns the old value */
190 " jns 1f\n\t"
191 " call call_rwsem_wake\n"
192 "1:\n"
193 "# ending __up_read\n"
194 : "+m" (sem->count), "=d" (tmp)
195 : "a" (sem), "1" (tmp)
196 : "memory", "cc");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700197}
198
199/*
200 * unlock after writing
201 */
202static inline void __up_write(struct rw_semaphore *sem)
203{
Joe Perches6e5609a2008-03-23 01:03:21 -0700204 asm volatile("# beginning __up_write\n\t"
205 " movl %2,%%edx\n\t"
206 LOCK_PREFIX " xaddl %%edx,(%%eax)\n\t"
207 /* tries to transition
208 0xffff0001 -> 0x00000000 */
209 " jz 1f\n"
210 " call call_rwsem_wake\n"
211 "1:\n\t"
212 "# ending __up_write\n"
213 : "+m" (sem->count)
214 : "a" (sem), "i" (-RWSEM_ACTIVE_WRITE_BIAS)
215 : "memory", "cc", "edx");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700216}
217
218/*
219 * downgrade write lock to read lock
220 */
221static inline void __downgrade_write(struct rw_semaphore *sem)
222{
Joe Perches6e5609a2008-03-23 01:03:21 -0700223 asm volatile("# beginning __downgrade_write\n\t"
224 LOCK_PREFIX " addl %2,(%%eax)\n\t"
225 /* transitions 0xZZZZ0001 -> 0xYYYY0001 */
226 " jns 1f\n\t"
227 " call call_rwsem_downgrade_wake\n"
228 "1:\n\t"
229 "# ending __downgrade_write\n"
230 : "+m" (sem->count)
231 : "a" (sem), "i" (-RWSEM_WAITING_BIAS)
232 : "memory", "cc");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700233}
234
235/*
236 * implement atomic add functionality
237 */
238static inline void rwsem_atomic_add(int delta, struct rw_semaphore *sem)
239{
Joe Perches6e5609a2008-03-23 01:03:21 -0700240 asm volatile(LOCK_PREFIX "addl %1,%0"
241 : "+m" (sem->count)
242 : "ir" (delta));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700243}
244
245/*
246 * implement exchange and add functionality
247 */
248static inline int rwsem_atomic_update(int delta, struct rw_semaphore *sem)
249{
250 int tmp = delta;
251
Joe Perches6e5609a2008-03-23 01:03:21 -0700252 asm volatile(LOCK_PREFIX "xadd %0,%1"
253 : "+r" (tmp), "+m" (sem->count)
254 : : "memory");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700255
Joe Perches6e5609a2008-03-23 01:03:21 -0700256 return tmp + delta;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700257}
258
Rik Van Rieleb92f4e2005-10-29 18:15:44 -0700259static inline int rwsem_is_locked(struct rw_semaphore *sem)
260{
261 return (sem->count != 0);
262}
263
Linus Torvalds1da177e2005-04-16 15:20:36 -0700264#endif /* __KERNEL__ */
265#endif /* _I386_RWSEM_H */