blob: 041906f3c6df73375abda597ba38e63922ffb542 [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 *
5 * Derived from asm-i386/semaphore.h
6 *
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
47extern struct rw_semaphore *FASTCALL(rwsem_down_read_failed(struct rw_semaphore *sem));
48extern struct rw_semaphore *FASTCALL(rwsem_down_write_failed(struct rw_semaphore *sem));
49extern struct rw_semaphore *FASTCALL(rwsem_wake(struct rw_semaphore *));
50extern struct rw_semaphore *FASTCALL(rwsem_downgrade_wake(struct rw_semaphore *sem));
51
52/*
53 * the semaphore definition
54 */
55struct rw_semaphore {
56 signed long count;
57#define RWSEM_UNLOCKED_VALUE 0x00000000
58#define RWSEM_ACTIVE_BIAS 0x00000001
59#define RWSEM_ACTIVE_MASK 0x0000ffff
60#define RWSEM_WAITING_BIAS (-0x00010000)
61#define RWSEM_ACTIVE_READ_BIAS RWSEM_ACTIVE_BIAS
62#define RWSEM_ACTIVE_WRITE_BIAS (RWSEM_WAITING_BIAS + RWSEM_ACTIVE_BIAS)
63 spinlock_t wait_lock;
64 struct list_head wait_list;
Ingo Molnar4ea21762006-07-03 00:24:53 -070065#ifdef CONFIG_DEBUG_LOCK_ALLOC
66 struct lockdep_map dep_map;
67#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -070068};
69
Ingo Molnar4ea21762006-07-03 00:24:53 -070070#ifdef CONFIG_DEBUG_LOCK_ALLOC
71# define __RWSEM_DEP_MAP_INIT(lockname) , .dep_map = { .name = #lockname }
72#else
73# define __RWSEM_DEP_MAP_INIT(lockname)
74#endif
75
76
Linus Torvalds1da177e2005-04-16 15:20:36 -070077#define __RWSEM_INITIALIZER(name) \
Peter Zijlstra6cfd76a2006-12-06 20:37:22 -080078{ RWSEM_UNLOCKED_VALUE, __SPIN_LOCK_UNLOCKED((name).wait_lock), \
79 LIST_HEAD_INIT((name).wait_list) __RWSEM_DEP_MAP_INIT(name) }
Linus Torvalds1da177e2005-04-16 15:20:36 -070080
81#define DECLARE_RWSEM(name) \
82 struct rw_semaphore name = __RWSEM_INITIALIZER(name)
83
Ingo Molnar4ea21762006-07-03 00:24:53 -070084extern void __init_rwsem(struct rw_semaphore *sem, const char *name,
85 struct lock_class_key *key);
86
87#define init_rwsem(sem) \
88do { \
89 static struct lock_class_key __key; \
90 \
91 __init_rwsem((sem), #sem, &__key); \
92} while (0)
Linus Torvalds1da177e2005-04-16 15:20:36 -070093
94/*
95 * lock for reading
96 */
97static inline void __down_read(struct rw_semaphore *sem)
98{
99 __asm__ __volatile__(
100 "# beginning down_read\n\t"
101LOCK_PREFIX " incl (%%eax)\n\t" /* adds 0x00000001, returns the old value */
Andi Kleenadd659b2006-09-26 10:52:31 +0200102 " jns 1f\n"
103 " call call_rwsem_down_read_failed\n"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700104 "1:\n\t"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700105 "# ending down_read\n\t"
Linus Torvaldsb862f3b2006-07-08 15:24:18 -0700106 : "+m" (sem->count)
107 : "a" (sem)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700108 : "memory", "cc");
109}
110
111/*
112 * trylock for reading -- returns 1 if successful, 0 if contention
113 */
114static inline int __down_read_trylock(struct rw_semaphore *sem)
115{
116 __s32 result, tmp;
117 __asm__ __volatile__(
118 "# beginning __down_read_trylock\n\t"
119 " movl %0,%1\n\t"
120 "1:\n\t"
121 " movl %1,%2\n\t"
122 " addl %3,%2\n\t"
123 " jle 2f\n\t"
124LOCK_PREFIX " cmpxchgl %2,%0\n\t"
125 " jnz 1b\n\t"
126 "2:\n\t"
127 "# ending __down_read_trylock\n\t"
Linus Torvaldsb862f3b2006-07-08 15:24:18 -0700128 : "+m" (sem->count), "=&a" (result), "=&r" (tmp)
129 : "i" (RWSEM_ACTIVE_READ_BIAS)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700130 : "memory", "cc");
131 return result>=0 ? 1 : 0;
132}
133
134/*
135 * lock for writing
136 */
Ingo Molnar4ea21762006-07-03 00:24:53 -0700137static inline void __down_write_nested(struct rw_semaphore *sem, int subclass)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700138{
139 int tmp;
140
141 tmp = RWSEM_ACTIVE_WRITE_BIAS;
142 __asm__ __volatile__(
143 "# beginning down_write\n\t"
144LOCK_PREFIX " xadd %%edx,(%%eax)\n\t" /* subtract 0x0000ffff, returns the old value */
145 " testl %%edx,%%edx\n\t" /* was the count 0 before? */
Andi Kleenadd659b2006-09-26 10:52:31 +0200146 " jz 1f\n"
147 " call call_rwsem_down_write_failed\n"
148 "1:\n"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700149 "# ending down_write"
Linus Torvaldsb862f3b2006-07-08 15:24:18 -0700150 : "+m" (sem->count), "=d" (tmp)
151 : "a" (sem), "1" (tmp)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700152 : "memory", "cc");
153}
154
Ingo Molnar4ea21762006-07-03 00:24:53 -0700155static inline void __down_write(struct rw_semaphore *sem)
156{
157 __down_write_nested(sem, 0);
158}
159
Linus Torvalds1da177e2005-04-16 15:20:36 -0700160/*
161 * trylock for writing -- returns 1 if successful, 0 if contention
162 */
163static inline int __down_write_trylock(struct rw_semaphore *sem)
164{
165 signed long ret = cmpxchg(&sem->count,
166 RWSEM_UNLOCKED_VALUE,
167 RWSEM_ACTIVE_WRITE_BIAS);
168 if (ret == RWSEM_UNLOCKED_VALUE)
169 return 1;
170 return 0;
171}
172
173/*
174 * unlock after reading
175 */
176static inline void __up_read(struct rw_semaphore *sem)
177{
178 __s32 tmp = -RWSEM_ACTIVE_READ_BIAS;
179 __asm__ __volatile__(
180 "# beginning __up_read\n\t"
181LOCK_PREFIX " xadd %%edx,(%%eax)\n\t" /* subtracts 1, returns the old value */
Andi Kleenadd659b2006-09-26 10:52:31 +0200182 " jns 1f\n\t"
183 " call call_rwsem_wake\n"
184 "1:\n"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700185 "# ending __up_read\n"
Linus Torvaldsb862f3b2006-07-08 15:24:18 -0700186 : "+m" (sem->count), "=d" (tmp)
187 : "a" (sem), "1" (tmp)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700188 : "memory", "cc");
189}
190
191/*
192 * unlock after writing
193 */
194static inline void __up_write(struct rw_semaphore *sem)
195{
196 __asm__ __volatile__(
197 "# beginning __up_write\n\t"
198 " movl %2,%%edx\n\t"
199LOCK_PREFIX " xaddl %%edx,(%%eax)\n\t" /* tries to transition 0xffff0001 -> 0x00000000 */
Andi Kleenadd659b2006-09-26 10:52:31 +0200200 " jz 1f\n"
201 " call call_rwsem_wake\n"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700202 "1:\n\t"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700203 "# ending __up_write\n"
Linus Torvaldsb862f3b2006-07-08 15:24:18 -0700204 : "+m" (sem->count)
205 : "a" (sem), "i" (-RWSEM_ACTIVE_WRITE_BIAS)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700206 : "memory", "cc", "edx");
207}
208
209/*
210 * downgrade write lock to read lock
211 */
212static inline void __downgrade_write(struct rw_semaphore *sem)
213{
214 __asm__ __volatile__(
215 "# beginning __downgrade_write\n\t"
216LOCK_PREFIX " addl %2,(%%eax)\n\t" /* transitions 0xZZZZ0001 -> 0xYYYY0001 */
Andi Kleenadd659b2006-09-26 10:52:31 +0200217 " jns 1f\n\t"
218 " call call_rwsem_downgrade_wake\n"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700219 "1:\n\t"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700220 "# ending __downgrade_write\n"
Linus Torvaldsb862f3b2006-07-08 15:24:18 -0700221 : "+m" (sem->count)
222 : "a" (sem), "i" (-RWSEM_WAITING_BIAS)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700223 : "memory", "cc");
224}
225
226/*
227 * implement atomic add functionality
228 */
229static inline void rwsem_atomic_add(int delta, struct rw_semaphore *sem)
230{
231 __asm__ __volatile__(
232LOCK_PREFIX "addl %1,%0"
Linus Torvaldsb862f3b2006-07-08 15:24:18 -0700233 : "+m" (sem->count)
234 : "ir" (delta));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700235}
236
237/*
238 * implement exchange and add functionality
239 */
240static inline int rwsem_atomic_update(int delta, struct rw_semaphore *sem)
241{
242 int tmp = delta;
243
244 __asm__ __volatile__(
Linus Torvaldsb862f3b2006-07-08 15:24:18 -0700245LOCK_PREFIX "xadd %0,%1"
246 : "+r" (tmp), "+m" (sem->count)
247 : : "memory");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700248
249 return tmp+delta;
250}
251
Rik Van Rieleb92f4e2005-10-29 18:15:44 -0700252static inline int rwsem_is_locked(struct rw_semaphore *sem)
253{
254 return (sem->count != 0);
255}
256
Linus Torvalds1da177e2005-04-16 15:20:36 -0700257#endif /* __KERNEL__ */
258#endif /* _I386_RWSEM_H */