include/asm-x86/bitops.h

   1 #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. */
  26 #define ADDR "=m" (*(volatile long *)addr)
  27 #define BIT_ADDR "=m" (((volatile int *)addr)[nr >> 5])
  28 #else
  29 #define ADDR "+m" (*(volatile long *) addr)
  30 #define BIT_ADDR "+m" (((volatile int *)addr)[nr >> 5])
  31 #endif
  32 #define BASE_ADDR "m" (*(volatile int *)addr)
  33
  34 /**
  35  * set_bit - Atomically set a bit in memory
  36  * @nr: the bit to set
  37  * @addr: the address to start counting from
  38  *
  39  * This function is atomic and may not be reordered.  See __set_bit()
  40  * if you do not require the atomic guarantees.
  41  *
  42  * Note: there are no guarantees that this function will not be reordered
  43  * on non x86 architectures, so if you are writing portable code,
  44  * make sure not to rely on its reordering guarantees.
  45  *
  46  * Note that @nr may be almost arbitrarily large; this function is not
  47  * restricted to acting on a single-word quantity.
  48  */
  49 static inline void set_bit(int nr, volatile void *addr)
  50 {
  51         asm volatile(LOCK_PREFIX "bts %1,%0" : ADDR : "Ir" (nr) : "memory");
  52 }
  53
  54 /**
  55  * __set_bit - Set a bit in memory
  56  * @nr: the bit to set
  57  * @addr: the address to start counting from
  58  *
  59  * Unlike set_bit(), this function is non-atomic and may be reordered.
  60  * If it's called on the same region of memory simultaneously, the effect
  61  * may be that only one operation succeeds.
  62  */
  63 static inline void __set_bit(int nr, volatile void *addr)
  64 {
  65         asm volatile("bts %1,%0" : ADDR : "Ir" (nr) : "memory");
  66 }
  67
  68 /**
  69  * clear_bit - Clears a bit in memory
  70  * @nr: Bit to clear
  71  * @addr: Address to start counting from
  72  *
  73  * clear_bit() is atomic and may not be reordered.  However, it does
  74  * not contain a memory barrier, so if it is used for locking purposes,
  75  * you should call smp_mb__before_clear_bit() and/or smp_mb__after_clear_bit()
  76  * in order to ensure changes are visible on other processors.
  77  */
  78 static inline void clear_bit(int nr, volatile void *addr)
  79 {
  80         asm volatile(LOCK_PREFIX "btr %1,%2" : BIT_ADDR : "Ir" (nr), BASE_ADDR);
  81 }
  82
  83 /*
  84  * clear_bit_unlock - Clears a bit in memory
  85  * @nr: Bit to clear
  86  * @addr: Address to start counting from
  87  *
  88  * clear_bit() is atomic and implies release semantics before the memory
  89  * operation. It can be used for an unlock.
  90  */
  91 static inline void clear_bit_unlock(unsigned nr, volatile void *addr)
  92 {
  93         barrier();
  94         clear_bit(nr, addr);
  95 }
  96
  97 static inline void __clear_bit(int nr, volatile void *addr)
  98 {
  99         asm volatile("btr %1,%2" : BIT_ADDR : "Ir" (nr), BASE_ADDR);
 100 }
 101
 102 /*
 103  * __clear_bit_unlock - Clears a bit in memory
 104  * @nr: Bit to clear
 105  * @addr: Address to start counting from
 106  *
 107  * __clear_bit() is non-atomic and implies release semantics before the memory
 108  * operation. It can be used for an unlock if no other CPUs can concurrently
 109  * modify other bits in the word.
 110  *
 111  * No memory barrier is required here, because x86 cannot reorder stores past
 112  * older loads. Same principle as spin_unlock.
 113  */
 114 static inline void __clear_bit_unlock(unsigned nr, volatile void *addr)
 115 {
 116         barrier();
 117         __clear_bit(nr, addr);
 118 }
 119
 120 #define smp_mb__before_clear_bit()      barrier()
 121 #define smp_mb__after_clear_bit()       barrier()
 122
 123 /**
 124  * __change_bit - Toggle a bit in memory
 125  * @nr: the bit to change
 126  * @addr: the address to start counting from
 127  *
 128  * Unlike change_bit(), this function is non-atomic and may be reordered.
 129  * If it's called on the same region of memory simultaneously, the effect
 130  * may be that only one operation succeeds.
 131  */
 132 static inline void __change_bit(int nr, volatile void *addr)
 133 {
 134         asm volatile("btc %1,%2" : BIT_ADDR : "Ir" (nr), BASE_ADDR);
 135 }
 136
 137 /**
 138  * change_bit - Toggle a bit in memory
 139  * @nr: Bit to change
 140  * @addr: Address to start counting from
 141  *
 142  * change_bit() is atomic and may not be reordered.
 143  * Note that @nr may be almost arbitrarily large; this function is not
 144  * restricted to acting on a single-word quantity.
 145  */
 146 static inline void change_bit(int nr, volatile void *addr)
 147 {
 148         asm volatile(LOCK_PREFIX "btc %1,%2" : BIT_ADDR : "Ir" (nr), BASE_ADDR);
 149 }
 150
 151 /**
 152  * test_and_set_bit - Set a bit and return its old value
 153  * @nr: Bit to set
 154  * @addr: Address to count from
 155  *
 156  * This operation is atomic and cannot be reordered.
 157  * It also implies a memory barrier.
 158  */
 159 static inline int test_and_set_bit(int nr, volatile void *addr)
 160 {
 161         int oldbit;
 162
 163         asm volatile(LOCK_PREFIX "bts %2,%1\n\t"
 164                      "sbb %0,%0" : "=r" (oldbit), ADDR : "Ir" (nr) : "memory");
 165
 166         return oldbit;
 167 }
 168
 169 /**
 170  * test_and_set_bit_lock - Set a bit and return its old value for lock
 171  * @nr: Bit to set
 172  * @addr: Address to count from
 173  *
 174  * This is the same as test_and_set_bit on x86.
 175  */
 176 static inline int test_and_set_bit_lock(int nr, volatile void *addr)
 177 {
 178         return test_and_set_bit(nr, addr);
 179 }
 180
 181 /**
 182  * __test_and_set_bit - Set a bit and return its old value
 183  * @nr: Bit to set
 184  * @addr: Address to count from
 185  *
 186  * This operation is non-atomic and can be reordered.
 187  * If two examples of this operation race, one can appear to succeed
 188  * but actually fail.  You must protect multiple accesses with a lock.
 189  */
 190 static inline int __test_and_set_bit(int nr, volatile void *addr)
 191 {
 192         int oldbit;
 193
 194         asm volatile("bts %2,%3\n\t"
 195                      "sbb %0,%0"
 196                      : "=r" (oldbit), BIT_ADDR : "Ir" (nr), BASE_ADDR);
 197         return oldbit;
 198 }
 199
 200 /**
 201  * test_and_clear_bit - Clear a bit and return its old value
 202  * @nr: Bit to clear
 203  * @addr: Address to count from
 204  *
 205  * This operation is atomic and cannot be reordered.
 206  * It also implies a memory barrier.
 207  */
 208 static inline int test_and_clear_bit(int nr, volatile void *addr)
 209 {
 210         int oldbit;
 211
 212         asm volatile(LOCK_PREFIX "btr %2,%1\n\t"
 213                      "sbb %0,%0"
 214                      : "=r" (oldbit), ADDR : "Ir" (nr) : "memory");
 215
 216         return oldbit;
 217 }
 218
 219 /**
 220  * __test_and_clear_bit - Clear a bit and return its old value
 221  * @nr: Bit to clear
 222  * @addr: Address to count from
 223  *
 224  * This operation is non-atomic and can be reordered.
 225  * If two examples of this operation race, one can appear to succeed
 226  * but actually fail.  You must protect multiple accesses with a lock.
 227  */
 228 static inline int __test_and_clear_bit(int nr, volatile void *addr)
 229 {
 230         int oldbit;
 231
 232         asm volatile("btr %2,%3\n\t"
 233                      "sbb %0,%0"
 234                      : "=r" (oldbit), BIT_ADDR : "Ir" (nr), BASE_ADDR);
 235         return oldbit;
 236 }
 237
 238 /* WARNING: non atomic and it can be reordered! */
 239 static inline int __test_and_change_bit(int nr, volatile void *addr)
 240 {
 241         int oldbit;
 242
 243         asm volatile("btc %2,%3\n\t"
 244                      "sbb %0,%0"
 245                      : "=r" (oldbit), BIT_ADDR : "Ir" (nr), BASE_ADDR);
 246
 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  */
 258 static inline int test_and_change_bit(int nr, volatile void *addr)
 259 {
 260         int oldbit;
 261
 262         asm volatile(LOCK_PREFIX "btc %2,%1\n\t"
 263                      "sbb %0,%0"
 264                      : "=r" (oldbit), ADDR : "Ir" (nr) : "memory");
 265
 266         return oldbit;
 267 }
 268
 269 static inline int constant_test_bit(int nr, const volatile void *addr)
 270 {
 271         return ((1UL << (nr % BITS_PER_LONG)) &
 272                 (((unsigned long *)addr)[nr / BITS_PER_LONG])) != 0;
 273 }
 274
 275 static inline int variable_test_bit(int nr, volatile const void *addr)
 276 {
 277         int oldbit;
 278
 279         asm volatile("bt %2,%3\n\t"
 280                      "sbb %0,%0"
 281                      : "=r" (oldbit)
 282                      : "m" (((volatile const int *)addr)[nr >> 5]),
 283                        "Ir" (nr), BASE_ADDR);
 284
 285         return oldbit;
 286 }
 287
 288 #if 0 /* Fool kernel-doc since it doesn't do macros yet */
 289 /**
 290  * test_bit - Determine whether a bit is set
 291  * @nr: bit number to test
 292  * @addr: Address to start counting from
 293  */
 294 static int test_bit(int nr, const volatile unsigned long *addr);
 295 #endif
 296
 297 #define test_bit(nr, addr)                      \
 298         (__builtin_constant_p((nr))             \
 299          ? constant_test_bit((nr), (addr))      \
 300          : variable_test_bit((nr), (addr)))
 301
 302 /**
 303  * __ffs - find first set bit in word
 304  * @word: The word to search
 305  *
 306  * Undefined if no bit exists, so code should check against 0 first.
 307  */
 308 static inline unsigned long __ffs(unsigned long word)
 309 {
 310         asm("bsf %1,%0"
 311                 : "=r" (word)
 312                 : "rm" (word));
 313         return word;
 314 }
 315
 316 /**
 317  * ffz - find first zero bit in word
 318  * @word: The word to search
 319  *
 320  * Undefined if no zero exists, so code should check against ~0UL first.
 321  */
 322 static inline unsigned long ffz(unsigned long word)
 323 {
 324         asm("bsf %1,%0"
 325                 : "=r" (word)
 326                 : "r" (~word));
 327         return word;
 328 }
 329
 330 /*
 331  * __fls: find last set bit in word
 332  * @word: The word to search
 333  *
 334  * Undefined if no zero exists, so code should check against ~0UL first.
 335  */
 336 static inline unsigned long __fls(unsigned long word)
 337 {
 338         asm("bsr %1,%0"
 339             : "=r" (word)
 340             : "rm" (word));
 341         return word;
 342 }
 343
 344 #ifdef __KERNEL__
 345 /**
 346  * ffs - find first set bit in word
 347  * @x: the word to search
 348  *
 349  * This is defined the same way as the libc and compiler builtin ffs
 350  * routines, therefore differs in spirit from the other bitops.
 351  *
 352  * ffs(value) returns 0 if value is 0 or the position of the first
 353  * set bit if value is nonzero. The first (least significant) bit
 354  * is at position 1.
 355  */
 356 static inline int ffs(int x)
 357 {
 358         int r;
 359 #ifdef CONFIG_X86_CMOV
 360         asm("bsfl %1,%0\n\t"
 361             "cmovzl %2,%0"
 362             : "=r" (r) : "rm" (x), "r" (-1));
 363 #else
 364         asm("bsfl %1,%0\n\t"
 365             "jnz 1f\n\t"
 366             "movl $-1,%0\n"
 367             "1:" : "=r" (r) : "rm" (x));
 368 #endif
 369         return r + 1;
 370 }
 371
 372 /**
 373  * fls - find last set bit in word
 374  * @x: the word to search
 375  *
 376  * This is defined in a similar way as the libc and compiler builtin
 377  * ffs, but returns the position of the most significant set bit.
 378  *
 379  * fls(value) returns 0 if value is 0 or the position of the last
 380  * set bit if value is nonzero. The last (most significant) bit is
 381  * at position 32.
 382  */
 383 static inline int fls(int x)
 384 {
 385         int r;
 386 #ifdef CONFIG_X86_CMOV
 387         asm("bsrl %1,%0\n\t"
 388             "cmovzl %2,%0"
 389             : "=&r" (r) : "rm" (x), "rm" (-1));
 390 #else
 391         asm("bsrl %1,%0\n\t"
 392             "jnz 1f\n\t"
 393             "movl $-1,%0\n"
 394             "1:" : "=r" (r) : "rm" (x));
 395 #endif
 396         return r + 1;
 397 }
 398 #endif /* __KERNEL__ */
 399
 400 #undef BASE_ADDR
 401 #undef BIT_ADDR
 402 #undef ADDR
 403
 404 static inline void set_bit_string(unsigned long *bitmap,
 405                 unsigned long i, int len)
 406 {
 407         unsigned long end = i + len;
 408         while (i < end) {
 409                 __set_bit(i, bitmap);
 410                 i++;
 411         }
 412 }
 413
 414 #ifdef __KERNEL__
 415
 416 #include <asm-generic/bitops/sched.h>
 417
 418 #define ARCH_HAS_FAST_MULTIPLIER 1
 419
 420 #include <asm-generic/bitops/hweight.h>
 421
 422 #endif /* __KERNEL__ */
 423
 424 #include <asm-generic/bitops/fls64.h>
 425
 426 #ifdef __KERNEL__
 427
 428 #include <asm-generic/bitops/ext2-non-atomic.h>
 429
 430 #define ext2_set_bit_atomic(lock, nr, addr)                     \
 431         test_and_set_bit((nr), (unsigned long *)(addr))
 432 #define ext2_clear_bit_atomic(lock, nr, addr)                   \
 433         test_and_clear_bit((nr), (unsigned long *)(addr))
 434
 435 #include <asm-generic/bitops/minix.h>
 436
 437 #endif /* __KERNEL__ */
 438 #endif  /* _ASM_X86_BITOPS_H */