include/asm-x86_64/bitops.h

   1 #ifndef _X86_64_BITOPS_H
   2 #define _X86_64_BITOPS_H
   3
   4 /*
   5  * Copyright 1992, Linus Torvalds.
   6  */
   7
   8 #include <linux/config.h>
   9
  10 #ifdef CONFIG_SMP
  11 #define LOCK_PREFIX "lock ; "
  12 #else
  13 #define LOCK_PREFIX ""
  14 #endif
  15
  16 #define ADDR (*(volatile long *) addr)
  17
  18 /**
  19  * set_bit - Atomically set a bit in memory
  20  * @nr: the bit to set
  21  * @addr: the address to start counting from
  22  *
  23  * This function is atomic and may not be reordered.  See __set_bit()
  24  * if you do not require the atomic guarantees.
  25  * Note that @nr may be almost arbitrarily large; this function is not
  26  * restricted to acting on a single-word quantity.
  27  */
  28 static __inline__ void set_bit(long nr, volatile void * addr)
  29 {
  30         __asm__ __volatile__( LOCK_PREFIX
  31                 "btsq %1,%0"
  32                 :"=m" (ADDR)
  33                 :"dIr" (nr) : "memory");
  34 }
  35
  36 /**
  37  * __set_bit - Set a bit in memory
  38  * @nr: the bit to set
  39  * @addr: the address to start counting from
  40  *
  41  * Unlike set_bit(), this function is non-atomic and may be reordered.
  42  * If it's called on the same region of memory simultaneously, the effect
  43  * may be that only one operation succeeds.
  44  */
  45 static __inline__ void __set_bit(int nr, volatile void * addr)
  46 {
  47         __asm__ volatile(
  48                 "btsl %1,%0"
  49                 :"=m" (ADDR)
  50                 :"dIr" (nr) : "memory");
  51 }
  52
  53 /**
  54  * clear_bit - Clears a bit in memory
  55  * @nr: Bit to clear
  56  * @addr: Address to start counting from
  57  *
  58  * clear_bit() is atomic and may not be reordered.  However, it does
  59  * not contain a memory barrier, so if it is used for locking purposes,
  60  * you should call smp_mb__before_clear_bit() and/or smp_mb__after_clear_bit()
  61  * in order to ensure changes are visible on other processors.
  62  */
  63 static __inline__ void clear_bit(int nr, volatile void * addr)
  64 {
  65         __asm__ __volatile__( LOCK_PREFIX
  66                 "btrl %1,%0"
  67                 :"=m" (ADDR)
  68                 :"dIr" (nr));
  69 }
  70
  71 static __inline__ void __clear_bit(int nr, volatile void * addr)
  72 {
  73         __asm__ __volatile__(
  74                 "btrl %1,%0"
  75                 :"=m" (ADDR)
  76                 :"dIr" (nr));
  77 }
  78
  79 #define smp_mb__before_clear_bit()      barrier()
  80 #define smp_mb__after_clear_bit()       barrier()
  81
  82 /**
  83  * __change_bit - Toggle a bit in memory
  84  * @nr: the bit to change
  85  * @addr: the address to start counting from
  86  *
  87  * Unlike change_bit(), this function is non-atomic and may be reordered.
  88  * If it's called on the same region of memory simultaneously, the effect
  89  * may be that only one operation succeeds.
  90  */
  91 static __inline__ void __change_bit(int nr, volatile void * addr)
  92 {
  93         __asm__ __volatile__(
  94                 "btcl %1,%0"
  95                 :"=m" (ADDR)
  96                 :"dIr" (nr));
  97 }
  98
  99 /**
 100  * change_bit - Toggle a bit in memory
 101  * @nr: Bit to change
 102  * @addr: Address to start counting from
 103  *
 104  * change_bit() is atomic and may not be reordered.
 105  * Note that @nr may be almost arbitrarily large; this function is not
 106  * restricted to acting on a single-word quantity.
 107  */
 108 static __inline__ void change_bit(int nr, volatile void * addr)
 109 {
 110         __asm__ __volatile__( LOCK_PREFIX
 111                 "btcl %1,%0"
 112                 :"=m" (ADDR)
 113                 :"dIr" (nr));
 114 }
 115
 116 /**
 117  * test_and_set_bit - Set a bit and return its old value
 118  * @nr: Bit to set
 119  * @addr: Address to count from
 120  *
 121  * This operation is atomic and cannot be reordered.
 122  * It also implies a memory barrier.
 123  */
 124 static __inline__ int test_and_set_bit(int nr, volatile void * addr)
 125 {
 126         int oldbit;
 127
 128         __asm__ __volatile__( LOCK_PREFIX
 129                 "btsl %2,%1\n\tsbbl %0,%0"
 130                 :"=r" (oldbit),"=m" (ADDR)
 131                 :"dIr" (nr) : "memory");
 132         return oldbit;
 133 }
 134
 135 /**
 136  * __test_and_set_bit - Set a bit and return its old value
 137  * @nr: Bit to set
 138  * @addr: Address to count from
 139  *
 140  * This operation is non-atomic and can be reordered.
 141  * If two examples of this operation race, one can appear to succeed
 142  * but actually fail.  You must protect multiple accesses with a lock.
 143  */
 144 static __inline__ int __test_and_set_bit(int nr, volatile void * addr)
 145 {
 146         int oldbit;
 147
 148         __asm__(
 149                 "btsl %2,%1\n\tsbbl %0,%0"
 150                 :"=r" (oldbit),"=m" (ADDR)
 151                 :"dIr" (nr));
 152         return oldbit;
 153 }
 154
 155 /**
 156  * test_and_clear_bit - Clear a bit and return its old value
 157  * @nr: Bit to clear
 158  * @addr: Address to count from
 159  *
 160  * This operation is atomic and cannot be reordered.
 161  * It also implies a memory barrier.
 162  */
 163 static __inline__ int test_and_clear_bit(int nr, volatile void * addr)
 164 {
 165         int oldbit;
 166
 167         __asm__ __volatile__( LOCK_PREFIX
 168                 "btrl %2,%1\n\tsbbl %0,%0"
 169                 :"=r" (oldbit),"=m" (ADDR)
 170                 :"dIr" (nr) : "memory");
 171         return oldbit;
 172 }
 173
 174 /**
 175  * __test_and_clear_bit - Clear a bit and return its old value
 176  * @nr: Bit to clear
 177  * @addr: Address to count from
 178  *
 179  * This operation is non-atomic and can be reordered.
 180  * If two examples of this operation race, one can appear to succeed
 181  * but actually fail.  You must protect multiple accesses with a lock.
 182  */
 183 static __inline__ int __test_and_clear_bit(int nr, volatile void * addr)
 184 {
 185         int oldbit;
 186
 187         __asm__(
 188                 "btrl %2,%1\n\tsbbl %0,%0"
 189                 :"=r" (oldbit),"=m" (ADDR)
 190                 :"dIr" (nr));
 191         return oldbit;
 192 }
 193
 194 /* WARNING: non atomic and it can be reordered! */
 195 static __inline__ int __test_and_change_bit(int nr, volatile void * addr)
 196 {
 197         int oldbit;
 198
 199         __asm__ __volatile__(
 200                 "btcl %2,%1\n\tsbbl %0,%0"
 201                 :"=r" (oldbit),"=m" (ADDR)
 202                 :"dIr" (nr) : "memory");
 203         return oldbit;
 204 }
 205
 206 /**
 207  * test_and_change_bit - Change a bit and return its old value
 208  * @nr: Bit to change
 209  * @addr: Address to count from
 210  *
 211  * This operation is atomic and cannot be reordered.
 212  * It also implies a memory barrier.
 213  */
 214 static __inline__ int test_and_change_bit(int nr, volatile void * addr)
 215 {
 216         int oldbit;
 217
 218         __asm__ __volatile__( LOCK_PREFIX
 219                 "btcl %2,%1\n\tsbbl %0,%0"
 220                 :"=r" (oldbit),"=m" (ADDR)
 221                 :"dIr" (nr) : "memory");
 222         return oldbit;
 223 }
 224
 225 #if 0 /* Fool kernel-doc since it doesn't do macros yet */
 226 /**
 227  * test_bit - Determine whether a bit is set
 228  * @nr: bit number to test
 229  * @addr: Address to start counting from
 230  */
 231 static int test_bit(int nr, const volatile void * addr);
 232 #endif
 233
 234 static __inline__ int constant_test_bit(int nr, const volatile void * addr)
 235 {
 236         return ((1UL << (nr & 31)) & (((const volatile unsigned int *) addr)[nr >> 5])) != 0;
 237 }
 238
 239 static __inline__ int variable_test_bit(int nr, volatile const void * addr)
 240 {
 241         int oldbit;
 242
 243         __asm__ __volatile__(
 244                 "btl %2,%1\n\tsbbl %0,%0"
 245                 :"=r" (oldbit)
 246                 :"m" (ADDR),"dIr" (nr));
 247         return oldbit;
 248 }
 249
 250 #define test_bit(nr,addr) \
 251 (__builtin_constant_p(nr) ? \
 252  constant_test_bit((nr),(addr)) : \
 253  variable_test_bit((nr),(addr)))
 254
 255 #undef ADDR
 256
 257 /**
 258  * find_first_zero_bit - find the first zero bit in a memory region
 259  * @addr: The address to start the search at
 260  * @size: The maximum size to search
 261  *
 262  * Returns the bit-number of the first zero bit, not the number of the byte
 263  * containing a bit.
 264  */
 265 static __inline__ int find_first_zero_bit(const unsigned long * addr, unsigned size)
 266 {
 267         int d0, d1, d2;
 268         int res;
 269
 270         if (!size)
 271                 return 0;
 272         __asm__ __volatile__(
 273                 "movl $-1,%%eax\n\t"
 274                 "xorl %%edx,%%edx\n\t"
 275                 "repe; scasl\n\t"
 276                 "je 1f\n\t"
 277                 "xorl -4(%%rdi),%%eax\n\t"
 278                 "subq $4,%%rdi\n\t"
 279                 "bsfl %%eax,%%edx\n"
 280                 "1:\tsubq %%rbx,%%rdi\n\t"
 281                 "shlq $3,%%rdi\n\t"
 282                 "addq %%rdi,%%rdx"
 283                 :"=d" (res), "=&c" (d0), "=&D" (d1), "=&a" (d2)
 284                 :"1" ((size + 31) >> 5), "2" (addr), "b" (addr) : "memory");
 285         return res;
 286 }
 287
 288 /**
 289  * find_next_zero_bit - find the first zero bit in a memory region
 290  * @addr: The address to base the search on
 291  * @offset: The bitnumber to start searching at
 292  * @size: The maximum size to search
 293  */
 294 static __inline__ int find_next_zero_bit (const unsigned long * addr, int size, int offset)
 295 {
 296         unsigned long * p = ((unsigned long *) addr) + (offset >> 6);
 297         unsigned long set = 0;
 298         unsigned long res, bit = offset&63;
 299
 300         if (bit) {
 301                 /*
 302                  * Look for zero in first word
 303                  */
 304                 __asm__("bsfq %1,%0\n\t"
 305                         "cmoveq %2,%0"
 306                         : "=r" (set)
 307                         : "r" (~(*p >> bit)), "r"(64L));
 308                 if (set < (64 - bit))
 309                         return set + offset;
 310                 set = 64 - bit;
 311                 p++;
 312         }
 313         /*
 314          * No zero yet, search remaining full words for a zero
 315          */
 316         res = find_first_zero_bit ((const unsigned long *)p, size - 64 * (p - (unsigned long *) addr));
 317         return (offset + set + res);
 318 }
 319
 320
 321 /**
 322  * find_first_bit - find the first set bit in a memory region
 323  * @addr: The address to start the search at
 324  * @size: The maximum size to search
 325  *
 326  * Returns the bit-number of the first set bit, not the number of the byte
 327  * containing a bit.
 328  */
 329 static __inline__ int find_first_bit(const unsigned long * addr, unsigned size)
 330 {
 331         int d0, d1;
 332         int res;
 333
 334         /* This looks at memory. Mark it volatile to tell gcc not to move it around */
 335         __asm__ __volatile__(
 336                 "xorl %%eax,%%eax\n\t"
 337                 "repe; scasl\n\t"
 338                 "jz 1f\n\t"
 339                 "leaq -4(%%rdi),%%rdi\n\t"
 340                 "bsfl (%%rdi),%%eax\n"
 341                 "1:\tsubq %%rbx,%%rdi\n\t"
 342                 "shll $3,%%edi\n\t"
 343                 "addl %%edi,%%eax"
 344                 :"=a" (res), "=&c" (d0), "=&D" (d1)
 345                 :"1" ((size + 31) >> 5), "2" (addr), "b" (addr) : "memory");
 346         return res;
 347 }
 348
 349 /**
 350  * find_next_bit - find the first set bit in a memory region
 351  * @addr: The address to base the search on
 352  * @offset: The bitnumber to start searching at
 353  * @size: The maximum size to search
 354  */
 355 static __inline__ int find_next_bit(const unsigned long * addr, int size, int offset)
 356 {
 357         const unsigned long * p = addr + (offset >> 6);
 358         unsigned long set = 0, bit = offset & 63, res;
 359
 360         if (bit) {
 361                 /*
 362                  * Look for nonzero in the first 64 bits:
 363                  */
 364                 __asm__("bsfq %1,%0\n\t"
 365                         "cmoveq %2,%0\n\t"
 366                         : "=r" (set)
 367                         : "r" (*p >> bit), "r" (64L));
 368                 if (set < (64 - bit))
 369                         return set + offset;
 370                 set = 64 - bit;
 371                 p++;
 372         }
 373         /*
 374          * No set bit yet, search remaining full words for a bit
 375          */
 376         res = find_first_bit (p, size - 64 * (p - addr));
 377         return (offset + set + res);
 378 }
 379
 380 /*
 381  * Find string of zero bits in a bitmap. -1 when not found.
 382  */
 383 extern unsigned long
 384 find_next_zero_string(unsigned long *bitmap, long start, long nbits, int len);
 385
 386 static inline void set_bit_string(unsigned long *bitmap, unsigned long i,
 387                                   int len)
 388 {
 389         unsigned long end = i + len;
 390         while (i < end) {
 391                 __set_bit(i, bitmap);
 392                 i++;
 393         }
 394 }
 395
 396 static inline void __clear_bit_string(unsigned long *bitmap, unsigned long i,
 397                                     int len)
 398 {
 399         unsigned long end = i + len;
 400         while (i < end) {
 401                 __clear_bit(i, bitmap);
 402                 i++;
 403         }
 404 }
 405
 406 /**
 407  * ffz - find first zero in word.
 408  * @word: The word to search
 409  *
 410  * Undefined if no zero exists, so code should check against ~0UL first.
 411  */
 412 static __inline__ unsigned long ffz(unsigned long word)
 413 {
 414         __asm__("bsfq %1,%0"
 415                 :"=r" (word)
 416                 :"r" (~word));
 417         return word;
 418 }
 419
 420 /**
 421  * __ffs - find first bit in word.
 422  * @word: The word to search
 423  *
 424  * Undefined if no bit exists, so code should check against 0 first.
 425  */
 426 static __inline__ unsigned long __ffs(unsigned long word)
 427 {
 428         __asm__("bsfq %1,%0"
 429                 :"=r" (word)
 430                 :"rm" (word));
 431         return word;
 432 }
 433
 434 #ifdef __KERNEL__
 435
 436 static inline int sched_find_first_bit(const unsigned long *b)
 437 {
 438         if (b[0])
 439                 return __ffs(b[0]);
 440         if (b[1])
 441                 return __ffs(b[1]) + 64;
 442         if (b[2])
 443                 return __ffs(b[2]) + 128;
 444 }
 445
 446 /**
 447  * ffs - find first bit set
 448  * @x: the word to search
 449  *
 450  * This is defined the same way as
 451  * the libc and compiler builtin ffs routines, therefore
 452  * differs in spirit from the above ffz (man ffs).
 453  */
 454 static __inline__ int ffs(int x)
 455 {
 456         int r;
 457
 458         __asm__("bsfl %1,%0\n\t"
 459                 "cmovzl %2,%0"
 460                 : "=r" (r) : "rm" (x), "r" (-1));
 461         return r+1;
 462 }
 463
 464 /**
 465  * hweightN - returns the hamming weight of a N-bit word
 466  * @x: the word to weigh
 467  *
 468  * The Hamming Weight of a number is the total number of bits set in it.
 469  */
 470
 471 #define hweight64(x) generic_hweight64(x)
 472 #define hweight32(x) generic_hweight32(x)
 473 #define hweight16(x) generic_hweight16(x)
 474 #define hweight8(x) generic_hweight8(x)
 475
 476 #endif /* __KERNEL__ */
 477
 478 #ifdef __KERNEL__
 479
 480 #define ext2_set_bit(nr,addr) \
 481         __test_and_set_bit((nr),(unsigned long*)addr)
 482 #define ext2_set_bit_atomic(lock,nr,addr) \
 483                 test_and_set_bit((nr),(unsigned long*)addr)
 484 #define ext2_clear_bit(nr, addr) \
 485         __test_and_clear_bit((nr),(unsigned long*)addr)
 486 #define ext2_clear_bit_atomic(lock,nr,addr) \
 487                 test_and_clear_bit((nr),(unsigned long*)addr)
 488 #define ext2_test_bit(nr, addr)      test_bit((nr),(unsigned long*)addr)
 489 #define ext2_find_first_zero_bit(addr, size) \
 490         find_first_zero_bit((unsigned long*)addr, size)
 491 #define ext2_find_next_zero_bit(addr, size, off) \
 492         find_next_zero_bit((unsigned long*)addr, size, off)
 493
 494 /* Bitmap functions for the minix filesystem.  */
 495 #define minix_test_and_set_bit(nr,addr) __test_and_set_bit(nr,(void*)addr)
 496 #define minix_set_bit(nr,addr) __set_bit(nr,(void*)addr)
 497 #define minix_test_and_clear_bit(nr,addr) __test_and_clear_bit(nr,(void*)addr)
 498 #define minix_test_bit(nr,addr) test_bit(nr,(void*)addr)
 499 #define minix_find_first_zero_bit(addr,size) \
 500         find_first_zero_bit((void*)addr,size)
 501
 502 /* find last set bit */
 503 #define fls(x) generic_fls(x)
 504
 505 #define ARCH_HAS_ATOMIC_UNSIGNED 1
 506
 507 #endif /* __KERNEL__ */
 508
 509 #endif /* _X86_64_BITOPS_H */