include/asm-i386/bitops.h

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