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 BITOP_ADDR(x) "=m" (*(volatile long *) (x))
  27 #else
  28 #define BITOP_ADDR(x) "+m" (*(volatile long *) (x))
  29 #endif
  30
  31 #define ADDR                            BITOP_ADDR(addr)
  32
  33 /*
  34  * We do the locked ops that don't return the old value as
  35  * a mask operation on a byte.
  36  */
  37 #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))
  40
  41 /**
  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  */
  56 static inline void set_bit(unsigned int nr, volatile unsigned long *addr)
  57 {
  58         if (IS_IMMEDIATE(nr)) {
  59                 asm volatile(LOCK_PREFIX "orb %1,%0"
  60                         : CONST_MASK_ADDR(nr, addr)
  61                         : "iq" ((u8)CONST_MASK(nr))
  62                         : "memory");
  63         } else {
  64                 asm volatile(LOCK_PREFIX "bts %1,%0"
  65                         : BITOP_ADDR(addr) : "Ir" (nr) : "memory");
  66         }
  67 }
  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  */
  78 static inline void __set_bit(int nr, volatile unsigned long *addr)
  79 {
  80         asm volatile("bts %1,%0" : ADDR : "Ir" (nr) : "memory");
  81 }
  82
  83 /**
  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  */
  93 static inline void clear_bit(int nr, volatile unsigned long *addr)
  94 {
  95         if (IS_IMMEDIATE(nr)) {
  96                 asm volatile(LOCK_PREFIX "andb %1,%0"
  97                         : CONST_MASK_ADDR(nr, addr)
  98                         : "iq" ((u8)~CONST_MASK(nr)));
  99         } else {
 100                 asm volatile(LOCK_PREFIX "btr %1,%0"
 101                         : BITOP_ADDR(addr)
 102                         : "Ir" (nr));
 103         }
 104 }
 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  */
 114 static inline void clear_bit_unlock(unsigned nr, volatile unsigned long *addr)
 115 {
 116         barrier();
 117         clear_bit(nr, addr);
 118 }
 119
 120 static inline void __clear_bit(int nr, volatile unsigned long *addr)
 121 {
 122         asm volatile("btr %1,%0" : ADDR : "Ir" (nr));
 123 }
 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  */
 137 static inline void __clear_bit_unlock(unsigned nr, volatile unsigned long *addr)
 138 {
 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  */
 155 static inline void __change_bit(int nr, volatile unsigned long *addr)
 156 {
 157         asm volatile("btc %1,%0" : ADDR : "Ir" (nr));
 158 }
 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  */
 169 static inline void change_bit(int nr, volatile unsigned long *addr)
 170 {
 171         asm volatile(LOCK_PREFIX "btc %1,%0" : ADDR : "Ir" (nr));
 172 }
 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  */
 182 static inline int test_and_set_bit(int nr, volatile unsigned long *addr)
 183 {
 184         int oldbit;
 185
 186         asm volatile(LOCK_PREFIX "bts %2,%1\n\t"
 187                      "sbb %0,%0" : "=r" (oldbit), ADDR : "Ir" (nr) : "memory");
 188
 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  */
 199 static inline int test_and_set_bit_lock(int nr, volatile unsigned long *addr)
 200 {
 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  */
 213 static inline int __test_and_set_bit(int nr, volatile unsigned long *addr)
 214 {
 215         int oldbit;
 216
 217         asm("bts %2,%1\n\t"
 218             "sbb %0,%0"
 219             : "=r" (oldbit), ADDR
 220             : "Ir" (nr));
 221         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  */
 232 static inline int test_and_clear_bit(int nr, volatile unsigned long *addr)
 233 {
 234         int oldbit;
 235
 236         asm volatile(LOCK_PREFIX "btr %2,%1\n\t"
 237                      "sbb %0,%0"
 238                      : "=r" (oldbit), ADDR : "Ir" (nr) : "memory");
 239
 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  */
 252 static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr)
 253 {
 254         int oldbit;
 255
 256         asm volatile("btr %2,%1\n\t"
 257                      "sbb %0,%0"
 258                      : "=r" (oldbit), ADDR
 259                      : "Ir" (nr));
 260         return oldbit;
 261 }
 262
 263 /* WARNING: non atomic and it can be reordered! */
 264 static inline int __test_and_change_bit(int nr, volatile unsigned long *addr)
 265 {
 266         int oldbit;
 267
 268         asm volatile("btc %2,%1\n\t"
 269                      "sbb %0,%0"
 270                      : "=r" (oldbit), ADDR
 271                      : "Ir" (nr) : "memory");
 272
 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  */
 284 static inline int test_and_change_bit(int nr, volatile unsigned long *addr)
 285 {
 286         int oldbit;
 287
 288         asm volatile(LOCK_PREFIX "btc %2,%1\n\t"
 289                      "sbb %0,%0"
 290                      : "=r" (oldbit), ADDR : "Ir" (nr) : "memory");
 291
 292         return oldbit;
 293 }
 294
 295 static inline int constant_test_bit(int nr, const volatile unsigned long *addr)
 296 {
 297         return ((1UL << (nr % BITS_PER_LONG)) &
 298                 (((unsigned long *)addr)[nr / BITS_PER_LONG])) != 0;
 299 }
 300
 301 static inline int variable_test_bit(int nr, volatile const unsigned long *addr)
 302 {
 303         int oldbit;
 304
 305         asm volatile("bt %2,%1\n\t"
 306                      "sbb %0,%0"
 307                      : "=r" (oldbit)
 308                      : "m" (*(unsigned long *)addr), "Ir" (nr));
 309
 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  */
 319 static int test_bit(int nr, const volatile unsigned long *addr);
 320 #endif
 321
 322 #define test_bit(nr, addr)                      \
 323         (__builtin_constant_p((nr))             \
 324          ? constant_test_bit((nr), (addr))      \
 325          : variable_test_bit((nr), (addr)))
 326
 327 /**
 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  */
 333 static inline unsigned long __ffs(unsigned long word)
 334 {
 335         asm("bsf %1,%0"
 336                 : "=r" (word)
 337                 : "rm" (word));
 338         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  */
 347 static inline unsigned long ffz(unsigned long word)
 348 {
 349         asm("bsf %1,%0"
 350                 : "=r" (word)
 351                 : "r" (~word));
 352         return word;
 353 }
 354
 355 /*
 356  * __fls: find last set bit in word
 357  * @word: The word to search
 358  *
 359  * Undefined if no zero exists, so code should check against ~0UL first.
 360  */
 361 static inline unsigned long __fls(unsigned long word)
 362 {
 363         asm("bsr %1,%0"
 364             : "=r" (word)
 365             : "rm" (word));
 366         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  */
 381 static inline int ffs(int x)
 382 {
 383         int r;
 384 #ifdef CONFIG_X86_CMOV
 385         asm("bsfl %1,%0\n\t"
 386             "cmovzl %2,%0"
 387             : "=r" (r) : "rm" (x), "r" (-1));
 388 #else
 389         asm("bsfl %1,%0\n\t"
 390             "jnz 1f\n\t"
 391             "movl $-1,%0\n"
 392             "1:" : "=r" (r) : "rm" (x));
 393 #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  */
 408 static inline int fls(int x)
 409 {
 410         int r;
 411 #ifdef CONFIG_X86_CMOV
 412         asm("bsrl %1,%0\n\t"
 413             "cmovzl %2,%0"
 414             : "=&r" (r) : "rm" (x), "rm" (-1));
 415 #else
 416         asm("bsrl %1,%0\n\t"
 417             "jnz 1f\n\t"
 418             "movl $-1,%0\n"
 419             "1:" : "=r" (r) : "rm" (x));
 420 #endif
 421         return r + 1;
 422 }
 423 #endif /* __KERNEL__ */
 424
 425 #undef ADDR
 426
 427 static inline void set_bit_string(unsigned long *bitmap,
 428                 unsigned long i, int len)
 429 {
 430         unsigned long end = i + len;
 431         while (i < end) {
 432                 __set_bit(i, bitmap);
 433                 i++;
 434         }
 435 }
 436
 437 #ifdef __KERNEL__
 438
 439 #include <asm-generic/bitops/sched.h>
 440
 441 #define ARCH_HAS_FAST_MULTIPLIER 1
 442
 443 #include <asm-generic/bitops/hweight.h>
 444
 445 #endif /* __KERNEL__ */
 446
 447 #include <asm-generic/bitops/fls64.h>
 448
 449 #ifdef __KERNEL__
 450
 451 #include <asm-generic/bitops/ext2-non-atomic.h>
 452
 453 #define ext2_set_bit_atomic(lock, nr, addr)                     \
 454         test_and_set_bit((nr), (unsigned long *)(addr))
 455 #define ext2_clear_bit_atomic(lock, nr, addr)                   \
 456         test_and_clear_bit((nr), (unsigned long *)(addr))
 457
 458 #include <asm-generic/bitops/minix.h>
 459
 460 #endif /* __KERNEL__ */
 461 #endif  /* _ASM_X86_BITOPS_H */