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 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 int find_first_bit(const unsigned long *addr, unsigned size)
 336 {
 337         int 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 /*
 371  * fls: find last bit set.
 372  */
 373
 374 #define fls(x) generic_fls(x)
 375 #define fls64(x)   generic_fls64(x)
 376
 377 #ifdef __KERNEL__
 378
 379 /*
 380  * Every architecture must define this function. It's the fastest
 381  * way of searching a 140-bit bitmap where the first 100 bits are
 382  * unlikely to be set. It's guaranteed that at least one of the 140
 383  * bits is cleared.
 384  */
 385 static inline int sched_find_first_bit(const unsigned long *b)
 386 {
 387         if (unlikely(b[0]))
 388                 return __ffs(b[0]);
 389         if (unlikely(b[1]))
 390                 return __ffs(b[1]) + 32;
 391         if (unlikely(b[2]))
 392                 return __ffs(b[2]) + 64;
 393         if (b[3])
 394                 return __ffs(b[3]) + 96;
 395         return __ffs(b[4]) + 128;
 396 }
 397
 398 /**
 399  * ffs - find first bit set
 400  * @x: the word to search
 401  *
 402  * This is defined the same way as
 403  * the libc and compiler builtin ffs routines, therefore
 404  * differs in spirit from the above ffz (man ffs).
 405  */
 406 static inline int ffs(int x)
 407 {
 408         int r;
 409
 410         __asm__("bsfl %1,%0\n\t"
 411                 "jnz 1f\n\t"
 412                 "movl $-1,%0\n"
 413                 "1:" : "=r" (r) : "rm" (x));
 414         return r+1;
 415 }
 416
 417 /**
 418  * hweightN - returns the hamming weight of a N-bit word
 419  * @x: the word to weigh
 420  *
 421  * The Hamming Weight of a number is the total number of bits set in it.
 422  */
 423
 424 #define hweight32(x) generic_hweight32(x)
 425 #define hweight16(x) generic_hweight16(x)
 426 #define hweight8(x) generic_hweight8(x)
 427
 428 #endif /* __KERNEL__ */
 429
 430 #ifdef __KERNEL__
 431
 432 #define ext2_set_bit(nr,addr) \
 433         __test_and_set_bit((nr),(unsigned long*)addr)
 434 #define ext2_set_bit_atomic(lock,nr,addr) \
 435         test_and_set_bit((nr),(unsigned long*)addr)
 436 #define ext2_clear_bit(nr, addr) \
 437         __test_and_clear_bit((nr),(unsigned long*)addr)
 438 #define ext2_clear_bit_atomic(lock,nr, addr) \
 439                 test_and_clear_bit((nr),(unsigned long*)addr)
 440 #define ext2_test_bit(nr, addr)      test_bit((nr),(unsigned long*)addr)
 441 #define ext2_find_first_zero_bit(addr, size) \
 442         find_first_zero_bit((unsigned long*)addr, size)
 443 #define ext2_find_next_zero_bit(addr, size, off) \
 444         find_next_zero_bit((unsigned long*)addr, size, off)
 445
 446 /* Bitmap functions for the minix filesystem.  */
 447 #define minix_test_and_set_bit(nr,addr) __test_and_set_bit(nr,(void*)addr)
 448 #define minix_set_bit(nr,addr) __set_bit(nr,(void*)addr)
 449 #define minix_test_and_clear_bit(nr,addr) __test_and_clear_bit(nr,(void*)addr)
 450 #define minix_test_bit(nr,addr) test_bit(nr,(void*)addr)
 451 #define minix_find_first_zero_bit(addr,size) \
 452         find_first_zero_bit((void*)addr,size)
 453
 454 #endif /* __KERNEL__ */
 455
 456 #endif /* _I386_BITOPS_H */