blob: 451a74762bd4e95aa3fd1ba20c2c6230ced14c84 [file] [log] [blame]
Vegard Nossum77ef50a2008-06-18 17:08:48 +02001#ifndef ASM_X86__BITOPS_H
2#define ASM_X86__BITOPS_H
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +01003
4/*
5 * Copyright 1992, Linus Torvalds.
6 */
7
8#ifndef _LINUX_BITOPS_H
9#error only <linux/bitops.h> can be included directly
10#endif
11
12#include <linux/compiler.h>
13#include <asm/alternative.h>
14
15/*
16 * These have to be done with inline assembly: that way the bit-setting
17 * is guaranteed to be atomic. All bit operations return 0 if the bit
18 * was cleared before the operation and != 0 if it was not.
19 *
20 * bit 0 is the LSB of addr; bit 32 is the LSB of (addr+1).
21 */
22
23#if __GNUC__ < 4 || (__GNUC__ == 4 && __GNUC_MINOR__ < 1)
24/* Technically wrong, but this avoids compilation errors on some gcc
25 versions. */
Linus Torvalds1a750e02008-06-18 21:03:26 -070026#define BITOP_ADDR(x) "=m" (*(volatile long *) (x))
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +010027#else
Linus Torvalds1a750e02008-06-18 21:03:26 -070028#define BITOP_ADDR(x) "+m" (*(volatile long *) (x))
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +010029#endif
30
Ingo Molnar7dbceaf2008-06-20 07:28:24 +020031#define ADDR BITOP_ADDR(addr)
Linus Torvalds1a750e02008-06-18 21:03:26 -070032
33/*
34 * We do the locked ops that don't return the old value as
35 * a mask operation on a byte.
36 */
Ingo Molnar7dbceaf2008-06-20 07:28:24 +020037#define IS_IMMEDIATE(nr) (__builtin_constant_p(nr))
38#define CONST_MASK_ADDR(nr, addr) BITOP_ADDR((void *)(addr) + ((nr)>>3))
39#define CONST_MASK(nr) (1 << ((nr) & 7))
Linus Torvalds1a750e02008-06-18 21:03:26 -070040
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +010041/**
42 * set_bit - Atomically set a bit in memory
43 * @nr: the bit to set
44 * @addr: the address to start counting from
45 *
46 * This function is atomic and may not be reordered. See __set_bit()
47 * if you do not require the atomic guarantees.
48 *
49 * Note: there are no guarantees that this function will not be reordered
50 * on non x86 architectures, so if you are writing portable code,
51 * make sure not to rely on its reordering guarantees.
52 *
53 * Note that @nr may be almost arbitrarily large; this function is not
54 * restricted to acting on a single-word quantity.
55 */
Linus Torvalds1a750e02008-06-18 21:03:26 -070056static inline void set_bit(unsigned int nr, volatile unsigned long *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +010057{
Ingo Molnar7dbceaf2008-06-20 07:28:24 +020058 if (IS_IMMEDIATE(nr)) {
59 asm volatile(LOCK_PREFIX "orb %1,%0"
60 : CONST_MASK_ADDR(nr, addr)
Ingo Molnar437a0a52008-06-20 21:50:20 +020061 : "iq" ((u8)CONST_MASK(nr))
Ingo Molnar7dbceaf2008-06-20 07:28:24 +020062 : "memory");
63 } else {
64 asm volatile(LOCK_PREFIX "bts %1,%0"
65 : BITOP_ADDR(addr) : "Ir" (nr) : "memory");
66 }
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +010067}
68
69/**
70 * __set_bit - Set a bit in memory
71 * @nr: the bit to set
72 * @addr: the address to start counting from
73 *
74 * Unlike set_bit(), this function is non-atomic and may be reordered.
75 * If it's called on the same region of memory simultaneously, the effect
76 * may be that only one operation succeeds.
77 */
Andrew Morton5136dea2008-05-14 16:10:41 -070078static inline void __set_bit(int nr, volatile unsigned long *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +010079{
Joe Perchesf19dcf42008-03-23 01:03:07 -070080 asm volatile("bts %1,%0" : ADDR : "Ir" (nr) : "memory");
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +010081}
82
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +010083/**
84 * clear_bit - Clears a bit in memory
85 * @nr: Bit to clear
86 * @addr: Address to start counting from
87 *
88 * clear_bit() is atomic and may not be reordered. However, it does
89 * not contain a memory barrier, so if it is used for locking purposes,
90 * you should call smp_mb__before_clear_bit() and/or smp_mb__after_clear_bit()
91 * in order to ensure changes are visible on other processors.
92 */
Andrew Morton5136dea2008-05-14 16:10:41 -070093static inline void clear_bit(int nr, volatile unsigned long *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +010094{
Ingo Molnar7dbceaf2008-06-20 07:28:24 +020095 if (IS_IMMEDIATE(nr)) {
96 asm volatile(LOCK_PREFIX "andb %1,%0"
97 : CONST_MASK_ADDR(nr, addr)
Ingo Molnar437a0a52008-06-20 21:50:20 +020098 : "iq" ((u8)~CONST_MASK(nr)));
Ingo Molnar7dbceaf2008-06-20 07:28:24 +020099 } else {
100 asm volatile(LOCK_PREFIX "btr %1,%0"
101 : BITOP_ADDR(addr)
102 : "Ir" (nr));
103 }
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100104}
105
106/*
107 * clear_bit_unlock - Clears a bit in memory
108 * @nr: Bit to clear
109 * @addr: Address to start counting from
110 *
111 * clear_bit() is atomic and implies release semantics before the memory
112 * operation. It can be used for an unlock.
113 */
Andrew Morton5136dea2008-05-14 16:10:41 -0700114static inline void clear_bit_unlock(unsigned nr, volatile unsigned long *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100115{
116 barrier();
117 clear_bit(nr, addr);
118}
119
Andrew Morton5136dea2008-05-14 16:10:41 -0700120static inline void __clear_bit(int nr, volatile unsigned long *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100121{
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +0200122 asm volatile("btr %1,%0" : ADDR : "Ir" (nr));
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100123}
124
125/*
126 * __clear_bit_unlock - Clears a bit in memory
127 * @nr: Bit to clear
128 * @addr: Address to start counting from
129 *
130 * __clear_bit() is non-atomic and implies release semantics before the memory
131 * operation. It can be used for an unlock if no other CPUs can concurrently
132 * modify other bits in the word.
133 *
134 * No memory barrier is required here, because x86 cannot reorder stores past
135 * older loads. Same principle as spin_unlock.
136 */
Andrew Morton5136dea2008-05-14 16:10:41 -0700137static inline void __clear_bit_unlock(unsigned nr, volatile unsigned long *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100138{
139 barrier();
140 __clear_bit(nr, addr);
141}
142
143#define smp_mb__before_clear_bit() barrier()
144#define smp_mb__after_clear_bit() barrier()
145
146/**
147 * __change_bit - Toggle a bit in memory
148 * @nr: the bit to change
149 * @addr: the address to start counting from
150 *
151 * Unlike change_bit(), this function is non-atomic and may be reordered.
152 * If it's called on the same region of memory simultaneously, the effect
153 * may be that only one operation succeeds.
154 */
Andrew Morton5136dea2008-05-14 16:10:41 -0700155static inline void __change_bit(int nr, volatile unsigned long *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100156{
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +0200157 asm volatile("btc %1,%0" : ADDR : "Ir" (nr));
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100158}
159
160/**
161 * change_bit - Toggle a bit in memory
162 * @nr: Bit to change
163 * @addr: Address to start counting from
164 *
165 * change_bit() is atomic and may not be reordered.
166 * Note that @nr may be almost arbitrarily large; this function is not
167 * restricted to acting on a single-word quantity.
168 */
Andrew Morton5136dea2008-05-14 16:10:41 -0700169static inline void change_bit(int nr, volatile unsigned long *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100170{
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +0200171 asm volatile(LOCK_PREFIX "btc %1,%0" : ADDR : "Ir" (nr));
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100172}
173
174/**
175 * test_and_set_bit - Set a bit and return its old value
176 * @nr: Bit to set
177 * @addr: Address to count from
178 *
179 * This operation is atomic and cannot be reordered.
180 * It also implies a memory barrier.
181 */
Andrew Morton5136dea2008-05-14 16:10:41 -0700182static inline int test_and_set_bit(int nr, volatile unsigned long *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100183{
184 int oldbit;
185
186 asm volatile(LOCK_PREFIX "bts %2,%1\n\t"
Joe Perches286275c2008-03-23 01:01:45 -0700187 "sbb %0,%0" : "=r" (oldbit), ADDR : "Ir" (nr) : "memory");
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100188
189 return oldbit;
190}
191
192/**
193 * test_and_set_bit_lock - Set a bit and return its old value for lock
194 * @nr: Bit to set
195 * @addr: Address to count from
196 *
197 * This is the same as test_and_set_bit on x86.
198 */
Andrew Morton5136dea2008-05-14 16:10:41 -0700199static inline int test_and_set_bit_lock(int nr, volatile unsigned long *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100200{
201 return test_and_set_bit(nr, addr);
202}
203
204/**
205 * __test_and_set_bit - Set a bit and return its old value
206 * @nr: Bit to set
207 * @addr: Address to count from
208 *
209 * This operation is non-atomic and can be reordered.
210 * If two examples of this operation race, one can appear to succeed
211 * but actually fail. You must protect multiple accesses with a lock.
212 */
Andrew Morton5136dea2008-05-14 16:10:41 -0700213static inline int __test_and_set_bit(int nr, volatile unsigned long *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100214{
215 int oldbit;
216
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +0200217 asm("bts %2,%1\n\t"
218 "sbb %0,%0"
219 : "=r" (oldbit), ADDR
220 : "Ir" (nr));
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100221 return oldbit;
222}
223
224/**
225 * test_and_clear_bit - Clear a bit and return its old value
226 * @nr: Bit to clear
227 * @addr: Address to count from
228 *
229 * This operation is atomic and cannot be reordered.
230 * It also implies a memory barrier.
231 */
Andrew Morton5136dea2008-05-14 16:10:41 -0700232static inline int test_and_clear_bit(int nr, volatile unsigned long *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100233{
234 int oldbit;
235
236 asm volatile(LOCK_PREFIX "btr %2,%1\n\t"
237 "sbb %0,%0"
Joe Perches286275c2008-03-23 01:01:45 -0700238 : "=r" (oldbit), ADDR : "Ir" (nr) : "memory");
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100239
240 return oldbit;
241}
242
243/**
244 * __test_and_clear_bit - Clear a bit and return its old value
245 * @nr: Bit to clear
246 * @addr: Address to count from
247 *
248 * This operation is non-atomic and can be reordered.
249 * If two examples of this operation race, one can appear to succeed
250 * but actually fail. You must protect multiple accesses with a lock.
251 */
Andrew Morton5136dea2008-05-14 16:10:41 -0700252static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100253{
254 int oldbit;
255
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +0200256 asm volatile("btr %2,%1\n\t"
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100257 "sbb %0,%0"
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +0200258 : "=r" (oldbit), ADDR
259 : "Ir" (nr));
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100260 return oldbit;
261}
262
263/* WARNING: non atomic and it can be reordered! */
Andrew Morton5136dea2008-05-14 16:10:41 -0700264static inline int __test_and_change_bit(int nr, volatile unsigned long *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100265{
266 int oldbit;
267
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +0200268 asm volatile("btc %2,%1\n\t"
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100269 "sbb %0,%0"
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +0200270 : "=r" (oldbit), ADDR
271 : "Ir" (nr) : "memory");
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100272
273 return oldbit;
274}
275
276/**
277 * test_and_change_bit - Change a bit and return its old value
278 * @nr: Bit to change
279 * @addr: Address to count from
280 *
281 * This operation is atomic and cannot be reordered.
282 * It also implies a memory barrier.
283 */
Andrew Morton5136dea2008-05-14 16:10:41 -0700284static inline int test_and_change_bit(int nr, volatile unsigned long *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100285{
286 int oldbit;
287
288 asm volatile(LOCK_PREFIX "btc %2,%1\n\t"
289 "sbb %0,%0"
Joe Perches286275c2008-03-23 01:01:45 -0700290 : "=r" (oldbit), ADDR : "Ir" (nr) : "memory");
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100291
292 return oldbit;
293}
294
Andrew Morton5136dea2008-05-14 16:10:41 -0700295static inline int constant_test_bit(int nr, const volatile unsigned long *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100296{
Glauber de Oliveira Costa26996dd2008-01-30 13:31:31 +0100297 return ((1UL << (nr % BITS_PER_LONG)) &
298 (((unsigned long *)addr)[nr / BITS_PER_LONG])) != 0;
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100299}
300
Andrew Morton5136dea2008-05-14 16:10:41 -0700301static inline int variable_test_bit(int nr, volatile const unsigned long *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100302{
303 int oldbit;
304
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +0200305 asm volatile("bt %2,%1\n\t"
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100306 "sbb %0,%0"
307 : "=r" (oldbit)
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +0200308 : "m" (*(unsigned long *)addr), "Ir" (nr));
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100309
310 return oldbit;
311}
312
313#if 0 /* Fool kernel-doc since it doesn't do macros yet */
314/**
315 * test_bit - Determine whether a bit is set
316 * @nr: bit number to test
317 * @addr: Address to start counting from
318 */
319static int test_bit(int nr, const volatile unsigned long *addr);
320#endif
321
Joe Perchesf19dcf42008-03-23 01:03:07 -0700322#define test_bit(nr, addr) \
323 (__builtin_constant_p((nr)) \
324 ? constant_test_bit((nr), (addr)) \
325 : variable_test_bit((nr), (addr)))
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100326
Alexander van Heukelum12d9c842008-03-15 13:04:42 +0100327/**
328 * __ffs - find first set bit in word
329 * @word: The word to search
330 *
331 * Undefined if no bit exists, so code should check against 0 first.
332 */
333static inline unsigned long __ffs(unsigned long word)
334{
Joe Perchesf19dcf42008-03-23 01:03:07 -0700335 asm("bsf %1,%0"
336 : "=r" (word)
337 : "rm" (word));
Alexander van Heukelum12d9c842008-03-15 13:04:42 +0100338 return word;
339}
340
341/**
342 * ffz - find first zero bit in word
343 * @word: The word to search
344 *
345 * Undefined if no zero exists, so code should check against ~0UL first.
346 */
347static inline unsigned long ffz(unsigned long word)
348{
Joe Perchesf19dcf42008-03-23 01:03:07 -0700349 asm("bsf %1,%0"
350 : "=r" (word)
351 : "r" (~word));
Alexander van Heukelum12d9c842008-03-15 13:04:42 +0100352 return word;
353}
354
355/*
356 * __fls: find last set bit in word
357 * @word: The word to search
358 *
Alexander van Heukelum8450e852008-07-05 19:53:46 +0200359 * Undefined if no set bit exists, so code should check against 0 first.
Alexander van Heukelum12d9c842008-03-15 13:04:42 +0100360 */
361static inline unsigned long __fls(unsigned long word)
362{
Joe Perchesf19dcf42008-03-23 01:03:07 -0700363 asm("bsr %1,%0"
364 : "=r" (word)
365 : "rm" (word));
Alexander van Heukelum12d9c842008-03-15 13:04:42 +0100366 return word;
367}
368
369#ifdef __KERNEL__
370/**
371 * ffs - find first set bit in word
372 * @x: the word to search
373 *
374 * This is defined the same way as the libc and compiler builtin ffs
375 * routines, therefore differs in spirit from the other bitops.
376 *
377 * ffs(value) returns 0 if value is 0 or the position of the first
378 * set bit if value is nonzero. The first (least significant) bit
379 * is at position 1.
380 */
381static inline int ffs(int x)
382{
383 int r;
384#ifdef CONFIG_X86_CMOV
Joe Perchesf19dcf42008-03-23 01:03:07 -0700385 asm("bsfl %1,%0\n\t"
386 "cmovzl %2,%0"
387 : "=r" (r) : "rm" (x), "r" (-1));
Alexander van Heukelum12d9c842008-03-15 13:04:42 +0100388#else
Joe Perchesf19dcf42008-03-23 01:03:07 -0700389 asm("bsfl %1,%0\n\t"
390 "jnz 1f\n\t"
391 "movl $-1,%0\n"
392 "1:" : "=r" (r) : "rm" (x));
Alexander van Heukelum12d9c842008-03-15 13:04:42 +0100393#endif
394 return r + 1;
395}
396
397/**
398 * fls - find last set bit in word
399 * @x: the word to search
400 *
401 * This is defined in a similar way as the libc and compiler builtin
402 * ffs, but returns the position of the most significant set bit.
403 *
404 * fls(value) returns 0 if value is 0 or the position of the last
405 * set bit if value is nonzero. The last (most significant) bit is
406 * at position 32.
407 */
408static inline int fls(int x)
409{
410 int r;
411#ifdef CONFIG_X86_CMOV
Joe Perchesf19dcf42008-03-23 01:03:07 -0700412 asm("bsrl %1,%0\n\t"
413 "cmovzl %2,%0"
414 : "=&r" (r) : "rm" (x), "rm" (-1));
Alexander van Heukelum12d9c842008-03-15 13:04:42 +0100415#else
Joe Perchesf19dcf42008-03-23 01:03:07 -0700416 asm("bsrl %1,%0\n\t"
417 "jnz 1f\n\t"
418 "movl $-1,%0\n"
419 "1:" : "=r" (r) : "rm" (x));
Alexander van Heukelum12d9c842008-03-15 13:04:42 +0100420#endif
421 return r + 1;
422}
423#endif /* __KERNEL__ */
424
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100425#undef ADDR
426
Alexander van Heukelumd66462f2008-04-04 20:49:30 +0200427#ifdef __KERNEL__
428
429#include <asm-generic/bitops/sched.h>
430
431#define ARCH_HAS_FAST_MULTIPLIER 1
432
433#include <asm-generic/bitops/hweight.h>
434
435#endif /* __KERNEL__ */
436
437#include <asm-generic/bitops/fls64.h>
438
439#ifdef __KERNEL__
440
441#include <asm-generic/bitops/ext2-non-atomic.h>
442
443#define ext2_set_bit_atomic(lock, nr, addr) \
444 test_and_set_bit((nr), (unsigned long *)(addr))
445#define ext2_clear_bit_atomic(lock, nr, addr) \
446 test_and_clear_bit((nr), (unsigned long *)(addr))
447
448#include <asm-generic/bitops/minix.h>
449
450#endif /* __KERNEL__ */
Vegard Nossum77ef50a2008-06-18 17:08:48 +0200451#endif /* ASM_X86__BITOPS_H */