Merge git://git.kernel.org/pub/scm/linux/kernel/git/mason/btrfs-unstable
[linux-2.6] / arch / x86 / include / asm / rwsem.h
1 /* 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-x86/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 _ASM_X86_RWSEM_H
33 #define _ASM_X86_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>
43 #include <linux/lockdep.h>
44
45 struct rwsem_waiter;
46
47 extern asmregparm struct rw_semaphore *
48  rwsem_down_read_failed(struct rw_semaphore *sem);
49 extern asmregparm struct rw_semaphore *
50  rwsem_down_write_failed(struct rw_semaphore *sem);
51 extern asmregparm struct rw_semaphore *
52  rwsem_wake(struct rw_semaphore *);
53 extern asmregparm struct rw_semaphore *
54  rwsem_downgrade_wake(struct rw_semaphore *sem);
55
56 /*
57  * the semaphore definition
58  */
59
60 #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)
66
67 struct rw_semaphore {
68         signed long             count;
69         spinlock_t              wait_lock;
70         struct list_head        wait_list;
71 #ifdef CONFIG_DEBUG_LOCK_ALLOC
72         struct lockdep_map dep_map;
73 #endif
74 };
75
76 #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
83 #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 }
88
89 #define DECLARE_RWSEM(name)                                     \
90         struct rw_semaphore name = __RWSEM_INITIALIZER(name)
91
92 extern void __init_rwsem(struct rw_semaphore *sem, const char *name,
93                          struct lock_class_key *key);
94
95 #define init_rwsem(sem)                                         \
96 do {                                                            \
97         static struct lock_class_key __key;                     \
98                                                                 \
99         __init_rwsem((sem), #sem, &__key);                      \
100 } while (0)
101
102 /*
103  * lock for reading
104  */
105 static inline void __down_read(struct rw_semaphore *sem)
106 {
107         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");
117 }
118
119 /*
120  * trylock for reading -- returns 1 if successful, 0 if contention
121  */
122 static inline int __down_read_trylock(struct rw_semaphore *sem)
123 {
124         __s32 result, tmp;
125         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;
139 }
140
141 /*
142  * lock for writing
143  */
144 static inline void __down_write_nested(struct rw_semaphore *sem, int subclass)
145 {
146         int tmp;
147
148         tmp = RWSEM_ACTIVE_WRITE_BIAS;
149         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");
161 }
162
163 static inline void __down_write(struct rw_semaphore *sem)
164 {
165         __down_write_nested(sem, 0);
166 }
167
168 /*
169  * trylock for writing -- returns 1 if successful, 0 if contention
170  */
171 static inline int __down_write_trylock(struct rw_semaphore *sem)
172 {
173         signed long ret = cmpxchg(&sem->count,
174                                   RWSEM_UNLOCKED_VALUE,
175                                   RWSEM_ACTIVE_WRITE_BIAS);
176         if (ret == RWSEM_UNLOCKED_VALUE)
177                 return 1;
178         return 0;
179 }
180
181 /*
182  * unlock after reading
183  */
184 static inline void __up_read(struct rw_semaphore *sem)
185 {
186         __s32 tmp = -RWSEM_ACTIVE_READ_BIAS;
187         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");
197 }
198
199 /*
200  * unlock after writing
201  */
202 static inline void __up_write(struct rw_semaphore *sem)
203 {
204         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");
216 }
217
218 /*
219  * downgrade write lock to read lock
220  */
221 static inline void __downgrade_write(struct rw_semaphore *sem)
222 {
223         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");
233 }
234
235 /*
236  * implement atomic add functionality
237  */
238 static inline void rwsem_atomic_add(int delta, struct rw_semaphore *sem)
239 {
240         asm volatile(LOCK_PREFIX "addl %1,%0"
241                      : "+m" (sem->count)
242                      : "ir" (delta));
243 }
244
245 /*
246  * implement exchange and add functionality
247  */
248 static inline int rwsem_atomic_update(int delta, struct rw_semaphore *sem)
249 {
250         int tmp = delta;
251
252         asm volatile(LOCK_PREFIX "xadd %0,%1"
253                      : "+r" (tmp), "+m" (sem->count)
254                      : : "memory");
255
256         return tmp + delta;
257 }
258
259 static inline int rwsem_is_locked(struct rw_semaphore *sem)
260 {
261         return (sem->count != 0);
262 }
263
264 #endif /* __KERNEL__ */
265 #endif /* _ASM_X86_RWSEM_H */