blob: ee4b3ead6a438d8d68c626803031072f60a19060 [file] [log] [blame]
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +01001#ifndef _ASM_X86_BITOPS_H
2#define _ASM_X86_BITOPS_H
3
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. */
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +020026#define ADDR "=m" (*(volatile long *) addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +010027#else
28#define ADDR "+m" (*(volatile long *) addr)
29#endif
30
31/**
32 * set_bit - Atomically set a bit in memory
33 * @nr: the bit to set
34 * @addr: the address to start counting from
35 *
36 * This function is atomic and may not be reordered. See __set_bit()
37 * if you do not require the atomic guarantees.
38 *
39 * Note: there are no guarantees that this function will not be reordered
40 * on non x86 architectures, so if you are writing portable code,
41 * make sure not to rely on its reordering guarantees.
42 *
43 * Note that @nr may be almost arbitrarily large; this function is not
44 * restricted to acting on a single-word quantity.
45 */
Glauber de Oliveira Costa26996dd2008-01-30 13:31:31 +010046static inline void set_bit(int nr, volatile void *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +010047{
Joe Perches286275c2008-03-23 01:01:45 -070048 asm volatile(LOCK_PREFIX "bts %1,%0" : ADDR : "Ir" (nr) : "memory");
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +010049}
50
51/**
52 * __set_bit - Set a bit in memory
53 * @nr: the bit to set
54 * @addr: the address to start counting from
55 *
56 * Unlike set_bit(), this function is non-atomic and may be reordered.
57 * If it's called on the same region of memory simultaneously, the effect
58 * may be that only one operation succeeds.
59 */
Glauber de Oliveira Costa26996dd2008-01-30 13:31:31 +010060static inline void __set_bit(int nr, volatile void *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +010061{
Joe Perchesf19dcf42008-03-23 01:03:07 -070062 asm volatile("bts %1,%0" : ADDR : "Ir" (nr) : "memory");
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +010063}
64
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +010065/**
66 * clear_bit - Clears a bit in memory
67 * @nr: Bit to clear
68 * @addr: Address to start counting from
69 *
70 * clear_bit() is atomic and may not be reordered. However, it does
71 * not contain a memory barrier, so if it is used for locking purposes,
72 * you should call smp_mb__before_clear_bit() and/or smp_mb__after_clear_bit()
73 * in order to ensure changes are visible on other processors.
74 */
Glauber de Oliveira Costa26996dd2008-01-30 13:31:31 +010075static inline void clear_bit(int nr, volatile void *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +010076{
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +020077 asm volatile(LOCK_PREFIX "btr %1,%0" : ADDR : "Ir" (nr));
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +010078}
79
80/*
81 * clear_bit_unlock - Clears a bit in memory
82 * @nr: Bit to clear
83 * @addr: Address to start counting from
84 *
85 * clear_bit() is atomic and implies release semantics before the memory
86 * operation. It can be used for an unlock.
87 */
Glauber de Oliveira Costa26996dd2008-01-30 13:31:31 +010088static inline void clear_bit_unlock(unsigned nr, volatile void *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +010089{
90 barrier();
91 clear_bit(nr, addr);
92}
93
Glauber de Oliveira Costa26996dd2008-01-30 13:31:31 +010094static inline void __clear_bit(int nr, volatile void *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +010095{
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +020096 asm volatile("btr %1,%0" : ADDR : "Ir" (nr));
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +010097}
98
99/*
100 * __clear_bit_unlock - Clears a bit in memory
101 * @nr: Bit to clear
102 * @addr: Address to start counting from
103 *
104 * __clear_bit() is non-atomic and implies release semantics before the memory
105 * operation. It can be used for an unlock if no other CPUs can concurrently
106 * modify other bits in the word.
107 *
108 * No memory barrier is required here, because x86 cannot reorder stores past
109 * older loads. Same principle as spin_unlock.
110 */
Glauber de Oliveira Costa26996dd2008-01-30 13:31:31 +0100111static inline void __clear_bit_unlock(unsigned nr, volatile void *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100112{
113 barrier();
114 __clear_bit(nr, addr);
115}
116
117#define smp_mb__before_clear_bit() barrier()
118#define smp_mb__after_clear_bit() barrier()
119
120/**
121 * __change_bit - Toggle a bit in memory
122 * @nr: the bit to change
123 * @addr: the address to start counting from
124 *
125 * Unlike change_bit(), this function is non-atomic and may be reordered.
126 * If it's called on the same region of memory simultaneously, the effect
127 * may be that only one operation succeeds.
128 */
Glauber de Oliveira Costa26996dd2008-01-30 13:31:31 +0100129static inline void __change_bit(int nr, volatile void *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100130{
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +0200131 asm volatile("btc %1,%0" : ADDR : "Ir" (nr));
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100132}
133
134/**
135 * change_bit - Toggle a bit in memory
136 * @nr: Bit to change
137 * @addr: Address to start counting from
138 *
139 * change_bit() is atomic and may not be reordered.
140 * Note that @nr may be almost arbitrarily large; this function is not
141 * restricted to acting on a single-word quantity.
142 */
Glauber de Oliveira Costa26996dd2008-01-30 13:31:31 +0100143static inline void change_bit(int nr, volatile void *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100144{
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +0200145 asm volatile(LOCK_PREFIX "btc %1,%0" : ADDR : "Ir" (nr));
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100146}
147
148/**
149 * test_and_set_bit - Set a bit and return its old value
150 * @nr: Bit to set
151 * @addr: Address to count from
152 *
153 * This operation is atomic and cannot be reordered.
154 * It also implies a memory barrier.
155 */
Glauber de Oliveira Costa26996dd2008-01-30 13:31:31 +0100156static inline int test_and_set_bit(int nr, volatile void *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100157{
158 int oldbit;
159
160 asm volatile(LOCK_PREFIX "bts %2,%1\n\t"
Joe Perches286275c2008-03-23 01:01:45 -0700161 "sbb %0,%0" : "=r" (oldbit), ADDR : "Ir" (nr) : "memory");
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100162
163 return oldbit;
164}
165
166/**
167 * test_and_set_bit_lock - Set a bit and return its old value for lock
168 * @nr: Bit to set
169 * @addr: Address to count from
170 *
171 * This is the same as test_and_set_bit on x86.
172 */
Glauber de Oliveira Costa26996dd2008-01-30 13:31:31 +0100173static inline int test_and_set_bit_lock(int nr, volatile void *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100174{
175 return test_and_set_bit(nr, addr);
176}
177
178/**
179 * __test_and_set_bit - Set a bit and return its old value
180 * @nr: Bit to set
181 * @addr: Address to count from
182 *
183 * This operation is non-atomic and can be reordered.
184 * If two examples of this operation race, one can appear to succeed
185 * but actually fail. You must protect multiple accesses with a lock.
186 */
Glauber de Oliveira Costa26996dd2008-01-30 13:31:31 +0100187static inline int __test_and_set_bit(int nr, volatile void *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100188{
189 int oldbit;
190
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +0200191 asm("bts %2,%1\n\t"
192 "sbb %0,%0"
193 : "=r" (oldbit), ADDR
194 : "Ir" (nr));
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100195 return oldbit;
196}
197
198/**
199 * test_and_clear_bit - Clear a bit and return its old value
200 * @nr: Bit to clear
201 * @addr: Address to count from
202 *
203 * This operation is atomic and cannot be reordered.
204 * It also implies a memory barrier.
205 */
Glauber de Oliveira Costa26996dd2008-01-30 13:31:31 +0100206static inline int test_and_clear_bit(int nr, volatile void *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100207{
208 int oldbit;
209
210 asm volatile(LOCK_PREFIX "btr %2,%1\n\t"
211 "sbb %0,%0"
Joe Perches286275c2008-03-23 01:01:45 -0700212 : "=r" (oldbit), ADDR : "Ir" (nr) : "memory");
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100213
214 return oldbit;
215}
216
217/**
218 * __test_and_clear_bit - Clear a bit and return its old value
219 * @nr: Bit to clear
220 * @addr: Address to count from
221 *
222 * This operation is non-atomic and can be reordered.
223 * If two examples of this operation race, one can appear to succeed
224 * but actually fail. You must protect multiple accesses with a lock.
225 */
Glauber de Oliveira Costa26996dd2008-01-30 13:31:31 +0100226static inline int __test_and_clear_bit(int nr, volatile void *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100227{
228 int oldbit;
229
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +0200230 asm volatile("btr %2,%1\n\t"
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100231 "sbb %0,%0"
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +0200232 : "=r" (oldbit), ADDR
233 : "Ir" (nr));
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100234 return oldbit;
235}
236
237/* WARNING: non atomic and it can be reordered! */
Glauber de Oliveira Costa26996dd2008-01-30 13:31:31 +0100238static inline int __test_and_change_bit(int nr, volatile void *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100239{
240 int oldbit;
241
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +0200242 asm volatile("btc %2,%1\n\t"
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100243 "sbb %0,%0"
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +0200244 : "=r" (oldbit), ADDR
245 : "Ir" (nr) : "memory");
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100246
247 return oldbit;
248}
249
250/**
251 * test_and_change_bit - Change a bit and return its old value
252 * @nr: Bit to change
253 * @addr: Address to count from
254 *
255 * This operation is atomic and cannot be reordered.
256 * It also implies a memory barrier.
257 */
Glauber de Oliveira Costa26996dd2008-01-30 13:31:31 +0100258static inline int test_and_change_bit(int nr, volatile void *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100259{
260 int oldbit;
261
262 asm volatile(LOCK_PREFIX "btc %2,%1\n\t"
263 "sbb %0,%0"
Joe Perches286275c2008-03-23 01:01:45 -0700264 : "=r" (oldbit), ADDR : "Ir" (nr) : "memory");
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100265
266 return oldbit;
267}
268
Glauber de Oliveira Costa26996dd2008-01-30 13:31:31 +0100269static inline int constant_test_bit(int nr, const volatile void *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100270{
Glauber de Oliveira Costa26996dd2008-01-30 13:31:31 +0100271 return ((1UL << (nr % BITS_PER_LONG)) &
272 (((unsigned long *)addr)[nr / BITS_PER_LONG])) != 0;
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100273}
274
Glauber de Oliveira Costa26996dd2008-01-30 13:31:31 +0100275static inline int variable_test_bit(int nr, volatile const void *addr)
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100276{
277 int oldbit;
278
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +0200279 asm volatile("bt %2,%1\n\t"
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100280 "sbb %0,%0"
281 : "=r" (oldbit)
Simon Holm Thøgerseneb2b4e62008-05-05 15:45:28 +0200282 : "m" (*(unsigned long *)addr), "Ir" (nr));
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100283
284 return oldbit;
285}
286
287#if 0 /* Fool kernel-doc since it doesn't do macros yet */
288/**
289 * test_bit - Determine whether a bit is set
290 * @nr: bit number to test
291 * @addr: Address to start counting from
292 */
293static int test_bit(int nr, const volatile unsigned long *addr);
294#endif
295
Joe Perchesf19dcf42008-03-23 01:03:07 -0700296#define test_bit(nr, addr) \
297 (__builtin_constant_p((nr)) \
298 ? constant_test_bit((nr), (addr)) \
299 : variable_test_bit((nr), (addr)))
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100300
Alexander van Heukelum12d9c842008-03-15 13:04:42 +0100301/**
302 * __ffs - find first set bit in word
303 * @word: The word to search
304 *
305 * Undefined if no bit exists, so code should check against 0 first.
306 */
307static inline unsigned long __ffs(unsigned long word)
308{
Joe Perchesf19dcf42008-03-23 01:03:07 -0700309 asm("bsf %1,%0"
310 : "=r" (word)
311 : "rm" (word));
Alexander van Heukelum12d9c842008-03-15 13:04:42 +0100312 return word;
313}
314
315/**
316 * ffz - find first zero bit in word
317 * @word: The word to search
318 *
319 * Undefined if no zero exists, so code should check against ~0UL first.
320 */
321static inline unsigned long ffz(unsigned long word)
322{
Joe Perchesf19dcf42008-03-23 01:03:07 -0700323 asm("bsf %1,%0"
324 : "=r" (word)
325 : "r" (~word));
Alexander van Heukelum12d9c842008-03-15 13:04:42 +0100326 return word;
327}
328
329/*
330 * __fls: find last set bit in word
331 * @word: The word to search
332 *
333 * Undefined if no zero exists, so code should check against ~0UL first.
334 */
335static inline unsigned long __fls(unsigned long word)
336{
Joe Perchesf19dcf42008-03-23 01:03:07 -0700337 asm("bsr %1,%0"
338 : "=r" (word)
339 : "rm" (word));
Alexander van Heukelum12d9c842008-03-15 13:04:42 +0100340 return word;
341}
342
343#ifdef __KERNEL__
344/**
345 * ffs - find first set bit in word
346 * @x: the word to search
347 *
348 * This is defined the same way as the libc and compiler builtin ffs
349 * routines, therefore differs in spirit from the other bitops.
350 *
351 * ffs(value) returns 0 if value is 0 or the position of the first
352 * set bit if value is nonzero. The first (least significant) bit
353 * is at position 1.
354 */
355static inline int ffs(int x)
356{
357 int r;
358#ifdef CONFIG_X86_CMOV
Joe Perchesf19dcf42008-03-23 01:03:07 -0700359 asm("bsfl %1,%0\n\t"
360 "cmovzl %2,%0"
361 : "=r" (r) : "rm" (x), "r" (-1));
Alexander van Heukelum12d9c842008-03-15 13:04:42 +0100362#else
Joe Perchesf19dcf42008-03-23 01:03:07 -0700363 asm("bsfl %1,%0\n\t"
364 "jnz 1f\n\t"
365 "movl $-1,%0\n"
366 "1:" : "=r" (r) : "rm" (x));
Alexander van Heukelum12d9c842008-03-15 13:04:42 +0100367#endif
368 return r + 1;
369}
370
371/**
372 * fls - find last set bit in word
373 * @x: the word to search
374 *
375 * This is defined in a similar way as the libc and compiler builtin
376 * ffs, but returns the position of the most significant set bit.
377 *
378 * fls(value) returns 0 if value is 0 or the position of the last
379 * set bit if value is nonzero. The last (most significant) bit is
380 * at position 32.
381 */
382static inline int fls(int x)
383{
384 int r;
385#ifdef CONFIG_X86_CMOV
Joe Perchesf19dcf42008-03-23 01:03:07 -0700386 asm("bsrl %1,%0\n\t"
387 "cmovzl %2,%0"
388 : "=&r" (r) : "rm" (x), "rm" (-1));
Alexander van Heukelum12d9c842008-03-15 13:04:42 +0100389#else
Joe Perchesf19dcf42008-03-23 01:03:07 -0700390 asm("bsrl %1,%0\n\t"
391 "jnz 1f\n\t"
392 "movl $-1,%0\n"
393 "1:" : "=r" (r) : "rm" (x));
Alexander van Heukelum12d9c842008-03-15 13:04:42 +0100394#endif
395 return r + 1;
396}
397#endif /* __KERNEL__ */
398
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100399#undef ADDR
400
Alexander van Heukelumd66462f2008-04-04 20:49:30 +0200401static inline void set_bit_string(unsigned long *bitmap,
402 unsigned long i, int len)
403{
404 unsigned long end = i + len;
405 while (i < end) {
406 __set_bit(i, bitmap);
407 i++;
408 }
409}
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100410
Alexander van Heukelumd66462f2008-04-04 20:49:30 +0200411#ifdef __KERNEL__
412
413#include <asm-generic/bitops/sched.h>
414
415#define ARCH_HAS_FAST_MULTIPLIER 1
416
417#include <asm-generic/bitops/hweight.h>
418
419#endif /* __KERNEL__ */
420
421#include <asm-generic/bitops/fls64.h>
422
423#ifdef __KERNEL__
424
425#include <asm-generic/bitops/ext2-non-atomic.h>
426
427#define ext2_set_bit_atomic(lock, nr, addr) \
428 test_and_set_bit((nr), (unsigned long *)(addr))
429#define ext2_clear_bit_atomic(lock, nr, addr) \
430 test_and_clear_bit((nr), (unsigned long *)(addr))
431
432#include <asm-generic/bitops/minix.h>
433
434#endif /* __KERNEL__ */
Jeremy Fitzhardinge1c54d772008-01-30 13:30:55 +0100435#endif /* _ASM_X86_BITOPS_H */