include/asm-mips/bitops.h

   1 /*
   2  * This file is subject to the terms and conditions of the GNU General Public
   3  * License.  See the file "COPYING" in the main directory of this archive
   4  * for more details.
   5  *
   6  * Copyright (c) 1994 - 1997, 1999, 2000  Ralf Baechle (ralf@gnu.org)
   7  * Copyright (c) 1999, 2000  Silicon Graphics, Inc.
   8  */
   9 #ifndef _ASM_BITOPS_H
  10 #define _ASM_BITOPS_H
  11
  12 #include <linux/config.h>
  13 #include <linux/compiler.h>
  14 #include <linux/types.h>
  15 #include <asm/byteorder.h>              /* sigh ... */
  16
  17 #if (_MIPS_SZLONG == 32)
  18 #define SZLONG_LOG 5
  19 #define SZLONG_MASK 31UL
  20 #define __LL    "ll"
  21 #define __SC    "sc"
  22 #define cpu_to_lelongp(x) cpu_to_le32p((__u32 *) (x))
  23 #elif (_MIPS_SZLONG == 64)
  24 #define SZLONG_LOG 6
  25 #define SZLONG_MASK 63UL
  26 #define __LL    "lld"
  27 #define __SC    "scd"
  28 #define cpu_to_lelongp(x) cpu_to_le64p((__u64 *) (x))
  29 #endif
  30
  31 #ifdef __KERNEL__
  32
  33 #include <asm/sgidefs.h>
  34 #include <asm/system.h>
  35
  36 /*
  37  * clear_bit() doesn't provide any barrier for the compiler.
  38  */
  39 #define smp_mb__before_clear_bit()      smp_mb()
  40 #define smp_mb__after_clear_bit()       smp_mb()
  41
  42 /*
  43  * Only disable interrupt for kernel mode stuff to keep usermode stuff
  44  * that dares to use kernel include files alive.
  45  */
  46 #define __bi_flags                      unsigned long flags
  47 #define __bi_cli()                      local_irq_disable()
  48 #define __bi_save_flags(x)              local_save_flags(x)
  49 #define __bi_local_irq_save(x)          local_irq_save(x)
  50 #define __bi_local_irq_restore(x)       local_irq_restore(x)
  51 #else
  52 #define __bi_flags
  53 #define __bi_cli()
  54 #define __bi_save_flags(x)
  55 #define __bi_local_irq_save(x)
  56 #define __bi_local_irq_restore(x)
  57 #endif /* __KERNEL__ */
  58
  59 #ifdef CONFIG_CPU_HAS_LLSC
  60
  61 /*
  62  * These functions for MIPS ISA > 1 are interrupt and SMP proof and
  63  * interrupt friendly
  64  */
  65
  66 /*
  67  * set_bit - Atomically set a bit in memory
  68  * @nr: the bit to set
  69  * @addr: the address to start counting from
  70  *
  71  * This function is atomic and may not be reordered.  See __set_bit()
  72  * if you do not require the atomic guarantees.
  73  * Note that @nr may be almost arbitrarily large; this function is not
  74  * restricted to acting on a single-word quantity.
  75  */
  76 static inline void set_bit(unsigned long nr, volatile unsigned long *addr)
  77 {
  78         unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
  79         unsigned long temp;
  80
  81         __asm__ __volatile__(
  82                 "1:\t" __LL "\t%0, %1\t\t# set_bit\n\t"
  83                 "or\t%0, %2\n\t"
  84                 __SC "\t%0, %1\n\t"
  85                 "beqz\t%0, 1b"
  86                 : "=&r" (temp), "=m" (*m)
  87                 : "ir" (1UL << (nr & SZLONG_MASK)), "m" (*m));
  88 }
  89
  90 /*
  91  * __set_bit - Set a bit in memory
  92  * @nr: the bit to set
  93  * @addr: the address to start counting from
  94  *
  95  * Unlike set_bit(), this function is non-atomic and may be reordered.
  96  * If it's called on the same region of memory simultaneously, the effect
  97  * may be that only one operation succeeds.
  98  */
  99 static inline void __set_bit(unsigned long nr, volatile unsigned long * addr)
 100 {
 101         unsigned long * m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 102
 103         *m |= 1UL << (nr & SZLONG_MASK);
 104 }
 105
 106 /*
 107  * clear_bit - Clears a bit in memory
 108  * @nr: Bit to clear
 109  * @addr: Address to start counting from
 110  *
 111  * clear_bit() is atomic and may not be reordered.  However, it does
 112  * not contain a memory barrier, so if it is used for locking purposes,
 113  * you should call smp_mb__before_clear_bit() and/or smp_mb__after_clear_bit()
 114  * in order to ensure changes are visible on other processors.
 115  */
 116 static inline void clear_bit(unsigned long nr, volatile unsigned long *addr)
 117 {
 118         unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 119         unsigned long temp;
 120
 121         __asm__ __volatile__(
 122                 "1:\t" __LL "\t%0, %1\t\t# clear_bit\n\t"
 123                 "and\t%0, %2\n\t"
 124                 __SC "\t%0, %1\n\t"
 125                 "beqz\t%0, 1b\n\t"
 126                 : "=&r" (temp), "=m" (*m)
 127                 : "ir" (~(1UL << (nr & SZLONG_MASK))), "m" (*m));
 128 }
 129
 130 /*
 131  * __clear_bit - Clears a bit in memory
 132  * @nr: Bit to clear
 133  * @addr: Address to start counting from
 134  *
 135  * Unlike clear_bit(), this function is non-atomic and may be reordered.
 136  * If it's called on the same region of memory simultaneously, the effect
 137  * may be that only one operation succeeds.
 138  */
 139 static inline void __clear_bit(unsigned long nr, volatile unsigned long * addr)
 140 {
 141         unsigned long * m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 142
 143         *m &= ~(1UL << (nr & SZLONG_MASK));
 144 }
 145
 146 /*
 147  * change_bit - Toggle a bit in memory
 148  * @nr: Bit to change
 149  * @addr: Address to start counting from
 150  *
 151  * change_bit() is atomic and may not be reordered.
 152  * Note that @nr may be almost arbitrarily large; this function is not
 153  * restricted to acting on a single-word quantity.
 154  */
 155 static inline void change_bit(unsigned long nr, volatile unsigned long *addr)
 156 {
 157         unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 158         unsigned long temp;
 159
 160         __asm__ __volatile__(
 161                 "1:\t" __LL "\t%0, %1\t\t# change_bit\n\t"
 162                 "xor\t%0, %2\n\t"
 163                 __SC "\t%0, %1\n\t"
 164                 "beqz\t%0, 1b"
 165                 : "=&r" (temp), "=m" (*m)
 166                 : "ir" (1UL << (nr & SZLONG_MASK)), "m" (*m));
 167 }
 168
 169 /*
 170  * __change_bit - Toggle a bit in memory
 171  * @nr: the bit to change
 172  * @addr: the address to start counting from
 173  *
 174  * Unlike change_bit(), this function is non-atomic and may be reordered.
 175  * If it's called on the same region of memory simultaneously, the effect
 176  * may be that only one operation succeeds.
 177  */
 178 static inline void __change_bit(unsigned long nr, volatile unsigned long * addr)
 179 {
 180         unsigned long * m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 181
 182         *m ^= 1UL << (nr & SZLONG_MASK);
 183 }
 184
 185 /*
 186  * test_and_set_bit - Set a bit and return its old value
 187  * @nr: Bit to set
 188  * @addr: Address to count from
 189  *
 190  * This operation is atomic and cannot be reordered.
 191  * It also implies a memory barrier.
 192  */
 193 static inline int test_and_set_bit(unsigned long nr,
 194         volatile unsigned long *addr)
 195 {
 196         unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 197         unsigned long temp, res;
 198
 199         __asm__ __volatile__(
 200                 ".set\tnoreorder\t\t# test_and_set_bit\n"
 201                 "1:\t" __LL "\t%0, %1\n\t"
 202                 "or\t%2, %0, %3\n\t"
 203                 __SC "\t%2, %1\n\t"
 204                 "beqz\t%2, 1b\n\t"
 205                 " and\t%2, %0, %3\n\t"
 206 #ifdef CONFIG_SMP
 207                 "sync\n\t"
 208 #endif
 209                 ".set\treorder"
 210                 : "=&r" (temp), "=m" (*m), "=&r" (res)
 211                 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
 212                 : "memory");
 213
 214         return res != 0;
 215 }
 216
 217 /*
 218  * __test_and_set_bit - Set a bit and return its old value
 219  * @nr: Bit to set
 220  * @addr: Address to count from
 221  *
 222  * This operation is non-atomic and can be reordered.
 223  * If two examples of this operation race, one can appear to succeed
 224  * but actually fail.  You must protect multiple accesses with a lock.
 225  */
 226 static inline int __test_and_set_bit(unsigned long nr,
 227         volatile unsigned long *addr)
 228 {
 229         volatile unsigned long *a = addr;
 230         unsigned long mask;
 231         int retval;
 232
 233         a += nr >> SZLONG_LOG;
 234         mask = 1 << (nr & SZLONG_MASK);
 235         retval = (mask & *a) != 0;
 236         *a |= mask;
 237
 238         return retval;
 239 }
 240
 241 /*
 242  * test_and_clear_bit - Clear a bit and return its old value
 243  * @nr: Bit to clear
 244  * @addr: Address to count from
 245  *
 246  * This operation is atomic and cannot be reordered.
 247  * It also implies a memory barrier.
 248  */
 249 static inline int test_and_clear_bit(unsigned long nr,
 250         volatile unsigned long *addr)
 251 {
 252         unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 253         unsigned long temp, res;
 254
 255         __asm__ __volatile__(
 256                 ".set\tnoreorder\t\t# test_and_clear_bit\n"
 257                 "1:\t" __LL "\t%0, %1\n\t"
 258                 "or\t%2, %0, %3\n\t"
 259                 "xor\t%2, %3\n\t"
 260                 __SC "\t%2, %1\n\t"
 261                 "beqz\t%2, 1b\n\t"
 262                 " and\t%2, %0, %3\n\t"
 263 #ifdef CONFIG_SMP
 264                 "sync\n\t"
 265 #endif
 266                 ".set\treorder"
 267                 : "=&r" (temp), "=m" (*m), "=&r" (res)
 268                 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
 269                 : "memory");
 270
 271         return res != 0;
 272 }
 273
 274 /*
 275  * __test_and_clear_bit - Clear a bit and return its old value
 276  * @nr: Bit to clear
 277  * @addr: Address to count from
 278  *
 279  * This operation is non-atomic and can be reordered.
 280  * If two examples of this operation race, one can appear to succeed
 281  * but actually fail.  You must protect multiple accesses with a lock.
 282  */
 283 static inline int __test_and_clear_bit(unsigned long nr,
 284         volatile unsigned long * addr)
 285 {
 286         volatile unsigned long *a = addr;
 287         unsigned long mask;
 288         int retval;
 289
 290         a += (nr >> SZLONG_LOG);
 291         mask = 1UL << (nr & SZLONG_MASK);
 292         retval = ((mask & *a) != 0);
 293         *a &= ~mask;
 294
 295         return retval;
 296 }
 297
 298 /*
 299  * test_and_change_bit - Change a bit and return its old value
 300  * @nr: Bit to change
 301  * @addr: Address to count from
 302  *
 303  * This operation is atomic and cannot be reordered.
 304  * It also implies a memory barrier.
 305  */
 306 static inline int test_and_change_bit(unsigned long nr,
 307         volatile unsigned long *addr)
 308 {
 309         unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 310         unsigned long temp, res;
 311
 312         __asm__ __volatile__(
 313                 ".set\tnoreorder\t\t# test_and_change_bit\n"
 314                 "1:\t" __LL "\t%0, %1\n\t"
 315                 "xor\t%2, %0, %3\n\t"
 316                 __SC "\t%2, %1\n\t"
 317                 "beqz\t%2, 1b\n\t"
 318                 " and\t%2, %0, %3\n\t"
 319 #ifdef CONFIG_SMP
 320                 "sync\n\t"
 321 #endif
 322                 ".set\treorder"
 323                 : "=&r" (temp), "=m" (*m), "=&r" (res)
 324                 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
 325                 : "memory");
 326
 327         return res != 0;
 328 }
 329
 330 /*
 331  * __test_and_change_bit - Change a bit and return its old value
 332  * @nr: Bit to change
 333  * @addr: Address to count from
 334  *
 335  * This operation is non-atomic and can be reordered.
 336  * If two examples of this operation race, one can appear to succeed
 337  * but actually fail.  You must protect multiple accesses with a lock.
 338  */
 339 static inline int __test_and_change_bit(unsigned long nr,
 340         volatile unsigned long *addr)
 341 {
 342         volatile unsigned long *a = addr;
 343         unsigned long mask;
 344         int retval;
 345
 346         a += (nr >> SZLONG_LOG);
 347         mask = 1UL << (nr & SZLONG_MASK);
 348         retval = ((mask & *a) != 0);
 349         *a ^= mask;
 350
 351         return retval;
 352 }
 353
 354 #else /* MIPS I */
 355
 356 /*
 357  * set_bit - Atomically set a bit in memory
 358  * @nr: the bit to set
 359  * @addr: the address to start counting from
 360  *
 361  * This function is atomic and may not be reordered.  See __set_bit()
 362  * if you do not require the atomic guarantees.
 363  * Note that @nr may be almost arbitrarily large; this function is not
 364  * restricted to acting on a single-word quantity.
 365  */
 366 static inline void set_bit(unsigned long nr, volatile unsigned long * addr)
 367 {
 368         volatile unsigned long *a = addr;
 369         unsigned long mask;
 370         __bi_flags;
 371
 372         a += nr >> SZLONG_LOG;
 373         mask = 1 << (nr & SZLONG_MASK);
 374         __bi_local_irq_save(flags);
 375         *a |= mask;
 376         __bi_local_irq_restore(flags);
 377 }
 378
 379 /*
 380  * __set_bit - Set a bit in memory
 381  * @nr: the bit to set
 382  * @addr: the address to start counting from
 383  *
 384  * Unlike set_bit(), this function is non-atomic and may be reordered.
 385  * If it's called on the same region of memory simultaneously, the effect
 386  * may be that only one operation succeeds.
 387  */
 388 static inline void __set_bit(unsigned long nr, volatile unsigned long * addr)
 389 {
 390         volatile unsigned long *a = addr;
 391         unsigned long mask;
 392
 393         a += nr >> SZLONG_LOG;
 394         mask = 1 << (nr & SZLONG_MASK);
 395         *a |= mask;
 396 }
 397
 398 /*
 399  * clear_bit - Clears a bit in memory
 400  * @nr: Bit to clear
 401  * @addr: Address to start counting from
 402  *
 403  * clear_bit() is atomic and may not be reordered.  However, it does
 404  * not contain a memory barrier, so if it is used for locking purposes,
 405  * you should call smp_mb__before_clear_bit() and/or smp_mb__after_clear_bit()
 406  * in order to ensure changes are visible on other processors.
 407  */
 408 static inline void clear_bit(unsigned long nr, volatile unsigned long * addr)
 409 {
 410         volatile unsigned long *a = addr;
 411         unsigned long mask;
 412         __bi_flags;
 413
 414         a += nr >> SZLONG_LOG;
 415         mask = 1 << (nr & SZLONG_MASK);
 416         __bi_local_irq_save(flags);
 417         *a &= ~mask;
 418         __bi_local_irq_restore(flags);
 419 }
 420
 421 static inline void __clear_bit(unsigned long nr, volatile unsigned long * addr)
 422 {
 423         volatile unsigned long *a = addr;
 424         unsigned long mask;
 425
 426         a += nr >> SZLONG_LOG;
 427         mask = 1 << (nr & SZLONG_MASK);
 428         *a &= ~mask;
 429 }
 430
 431 /*
 432  * change_bit - Toggle a bit in memory
 433  * @nr: Bit to change
 434  * @addr: Address to start counting from
 435  *
 436  * change_bit() is atomic and may not be reordered.
 437  * Note that @nr may be almost arbitrarily large; this function is not
 438  * restricted to acting on a single-word quantity.
 439  */
 440 static inline void change_bit(unsigned long nr, volatile unsigned long * addr)
 441 {
 442         volatile unsigned long *a = addr;
 443         unsigned long mask;
 444         __bi_flags;
 445
 446         a += nr >> SZLONG_LOG;
 447         mask = 1 << (nr & SZLONG_MASK);
 448         __bi_local_irq_save(flags);
 449         *a ^= mask;
 450         __bi_local_irq_restore(flags);
 451 }
 452
 453 /*
 454  * __change_bit - Toggle a bit in memory
 455  * @nr: the bit to change
 456  * @addr: the address to start counting from
 457  *
 458  * Unlike change_bit(), this function is non-atomic and may be reordered.
 459  * If it's called on the same region of memory simultaneously, the effect
 460  * may be that only one operation succeeds.
 461  */
 462 static inline void __change_bit(unsigned long nr, volatile unsigned long * addr)
 463 {
 464         unsigned long * m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 465
 466         *m ^= 1UL << (nr & SZLONG_MASK);
 467 }
 468
 469 /*
 470  * test_and_set_bit - Set a bit and return its old value
 471  * @nr: Bit to set
 472  * @addr: Address to count from
 473  *
 474  * This operation is atomic and cannot be reordered.
 475  * It also implies a memory barrier.
 476  */
 477 static inline int test_and_set_bit(unsigned long nr,
 478         volatile unsigned long * addr)
 479 {
 480         volatile unsigned long *a = addr;
 481         unsigned long mask;
 482         int retval;
 483         __bi_flags;
 484
 485         a += nr >> SZLONG_LOG;
 486         mask = 1 << (nr & SZLONG_MASK);
 487         __bi_local_irq_save(flags);
 488         retval = (mask & *a) != 0;
 489         *a |= mask;
 490         __bi_local_irq_restore(flags);
 491
 492         return retval;
 493 }
 494
 495 /*
 496  * __test_and_set_bit - Set a bit and return its old value
 497  * @nr: Bit to set
 498  * @addr: Address to count from
 499  *
 500  * This operation is non-atomic and can be reordered.
 501  * If two examples of this operation race, one can appear to succeed
 502  * but actually fail.  You must protect multiple accesses with a lock.
 503  */
 504 static inline int __test_and_set_bit(unsigned long nr,
 505         volatile unsigned long *addr)
 506 {
 507         volatile unsigned long *a = addr;
 508         unsigned long mask;
 509         int retval;
 510
 511         a += nr >> SZLONG_LOG;
 512         mask = 1 << (nr & SZLONG_MASK);
 513         retval = (mask & *a) != 0;
 514         *a |= mask;
 515
 516         return retval;
 517 }
 518
 519 /*
 520  * test_and_clear_bit - Clear a bit and return its old value
 521  * @nr: Bit to clear
 522  * @addr: Address to count from
 523  *
 524  * This operation is atomic and cannot be reordered.
 525  * It also implies a memory barrier.
 526  */
 527 static inline int test_and_clear_bit(unsigned long nr,
 528         volatile unsigned long * addr)
 529 {
 530         volatile unsigned long *a = addr;
 531         unsigned long mask;
 532         int retval;
 533         __bi_flags;
 534
 535         a += nr >> SZLONG_LOG;
 536         mask = 1 << (nr & SZLONG_MASK);
 537         __bi_local_irq_save(flags);
 538         retval = (mask & *a) != 0;
 539         *a &= ~mask;
 540         __bi_local_irq_restore(flags);
 541
 542         return retval;
 543 }
 544
 545 /*
 546  * __test_and_clear_bit - Clear a bit and return its old value
 547  * @nr: Bit to clear
 548  * @addr: Address to count from
 549  *
 550  * This operation is non-atomic and can be reordered.
 551  * If two examples of this operation race, one can appear to succeed
 552  * but actually fail.  You must protect multiple accesses with a lock.
 553  */
 554 static inline int __test_and_clear_bit(unsigned long nr,
 555         volatile unsigned long * addr)
 556 {
 557         volatile unsigned long *a = addr;
 558         unsigned long mask;
 559         int retval;
 560
 561         a += (nr >> SZLONG_LOG);
 562         mask = 1UL << (nr & SZLONG_MASK);
 563         retval = ((mask & *a) != 0);
 564         *a &= ~mask;
 565
 566         return retval;
 567 }
 568
 569 /*
 570  * test_and_change_bit - Change a bit and return its old value
 571  * @nr: Bit to change
 572  * @addr: Address to count from
 573  *
 574  * This operation is atomic and cannot be reordered.
 575  * It also implies a memory barrier.
 576  */
 577 static inline int test_and_change_bit(unsigned long nr,
 578         volatile unsigned long * addr)
 579 {
 580         volatile unsigned long *a = addr;
 581         unsigned long mask, retval;
 582         __bi_flags;
 583
 584         a += nr >> SZLONG_LOG;
 585         mask = 1 << (nr & SZLONG_MASK);
 586         __bi_local_irq_save(flags);
 587         retval = (mask & *a) != 0;
 588         *a ^= mask;
 589         __bi_local_irq_restore(flags);
 590
 591         return retval;
 592 }
 593
 594 /*
 595  * __test_and_change_bit - Change a bit and return its old value
 596  * @nr: Bit to change
 597  * @addr: Address to count from
 598  *
 599  * This operation is non-atomic and can be reordered.
 600  * If two examples of this operation race, one can appear to succeed
 601  * but actually fail.  You must protect multiple accesses with a lock.
 602  */
 603 static inline int __test_and_change_bit(unsigned long nr,
 604         volatile unsigned long * addr)
 605 {
 606         volatile unsigned long *a = addr;
 607         unsigned long mask;
 608         int retval;
 609
 610         a += (nr >> SZLONG_LOG);
 611         mask = 1 << (nr & SZLONG_MASK);
 612         retval = (mask & *a) != 0;
 613         *a ^= mask;
 614
 615         return retval;
 616 }
 617
 618 #undef __bi_flags
 619 #undef __bi_cli
 620 #undef __bi_save_flags
 621 #undef __bi_local_irq_restore
 622
 623 #endif /* MIPS I */
 624
 625 /*
 626  * test_bit - Determine whether a bit is set
 627  * @nr: bit number to test
 628  * @addr: Address to start counting from
 629  */
 630 static inline int test_bit(unsigned long nr, const volatile unsigned long *addr)
 631 {
 632         return 1UL & (addr[nr >> SZLONG_LOG] >> (nr & SZLONG_MASK));
 633 }
 634
 635 /*
 636  * ffz - find first zero in word.
 637  * @word: The word to search
 638  *
 639  * Undefined if no zero exists, so code should check against ~0UL first.
 640  */
 641 static inline unsigned long ffz(unsigned long word)
 642 {
 643         int b = 0, s;
 644
 645         word = ~word;
 646 #ifdef CONFIG_MIPS32
 647         s = 16; if (word << 16 != 0) s = 0; b += s; word >>= s;
 648         s =  8; if (word << 24 != 0) s = 0; b += s; word >>= s;
 649         s =  4; if (word << 28 != 0) s = 0; b += s; word >>= s;
 650         s =  2; if (word << 30 != 0) s = 0; b += s; word >>= s;
 651         s =  1; if (word << 31 != 0) s = 0; b += s;
 652 #endif
 653 #ifdef CONFIG_MIPS64
 654         s = 32; if (word << 32 != 0) s = 0; b += s; word >>= s;
 655         s = 16; if (word << 48 != 0) s = 0; b += s; word >>= s;
 656         s =  8; if (word << 56 != 0) s = 0; b += s; word >>= s;
 657         s =  4; if (word << 60 != 0) s = 0; b += s; word >>= s;
 658         s =  2; if (word << 62 != 0) s = 0; b += s; word >>= s;
 659         s =  1; if (word << 63 != 0) s = 0; b += s;
 660 #endif
 661
 662         return b;
 663 }
 664
 665 /*
 666  * __ffs - find first bit in word.
 667  * @word: The word to search
 668  *
 669  * Undefined if no bit exists, so code should check against 0 first.
 670  */
 671 static inline unsigned long __ffs(unsigned long word)
 672 {
 673         return ffz(~word);
 674 }
 675
 676 /*
 677  * fls: find last bit set.
 678  */
 679
 680 #define fls(x) generic_fls(x)
 681
 682 /*
 683  * find_next_zero_bit - find the first zero bit in a memory region
 684  * @addr: The address to base the search on
 685  * @offset: The bitnumber to start searching at
 686  * @size: The maximum size to search
 687  */
 688 static inline unsigned long find_next_zero_bit(const unsigned long *addr,
 689         unsigned long size, unsigned long offset)
 690 {
 691         const unsigned long *p = addr + (offset >> SZLONG_LOG);
 692         unsigned long result = offset & ~SZLONG_MASK;
 693         unsigned long tmp;
 694
 695         if (offset >= size)
 696                 return size;
 697         size -= result;
 698         offset &= SZLONG_MASK;
 699         if (offset) {
 700                 tmp = *(p++);
 701                 tmp |= ~0UL >> (_MIPS_SZLONG-offset);
 702                 if (size < _MIPS_SZLONG)
 703                         goto found_first;
 704                 if (~tmp)
 705                         goto found_middle;
 706                 size -= _MIPS_SZLONG;
 707                 result += _MIPS_SZLONG;
 708         }
 709         while (size & ~SZLONG_MASK) {
 710                 if (~(tmp = *(p++)))
 711                         goto found_middle;
 712                 result += _MIPS_SZLONG;
 713                 size -= _MIPS_SZLONG;
 714         }
 715         if (!size)
 716                 return result;
 717         tmp = *p;
 718
 719 found_first:
 720         tmp |= ~0UL << size;
 721         if (tmp == ~0UL)                /* Are any bits zero? */
 722                 return result + size;   /* Nope. */
 723 found_middle:
 724         return result + ffz(tmp);
 725 }
 726
 727 #define find_first_zero_bit(addr, size) \
 728         find_next_zero_bit((addr), (size), 0)
 729
 730 /*
 731  * find_next_bit - find the next set bit in a memory region
 732  * @addr: The address to base the search on
 733  * @offset: The bitnumber to start searching at
 734  * @size: The maximum size to search
 735  */
 736 static inline unsigned long find_next_bit(const unsigned long *addr,
 737         unsigned long size, unsigned long offset)
 738 {
 739         const unsigned long *p = addr + (offset >> SZLONG_LOG);
 740         unsigned long result = offset & ~SZLONG_MASK;
 741         unsigned long tmp;
 742
 743         if (offset >= size)
 744                 return size;
 745         size -= result;
 746         offset &= SZLONG_MASK;
 747         if (offset) {
 748                 tmp = *(p++);
 749                 tmp &= ~0UL << offset;
 750                 if (size < _MIPS_SZLONG)
 751                         goto found_first;
 752                 if (tmp)
 753                         goto found_middle;
 754                 size -= _MIPS_SZLONG;
 755                 result += _MIPS_SZLONG;
 756         }
 757         while (size & ~SZLONG_MASK) {
 758                 if ((tmp = *(p++)))
 759                         goto found_middle;
 760                 result += _MIPS_SZLONG;
 761                 size -= _MIPS_SZLONG;
 762         }
 763         if (!size)
 764                 return result;
 765         tmp = *p;
 766
 767 found_first:
 768         tmp &= ~0UL >> (_MIPS_SZLONG - size);
 769         if (tmp == 0UL)                 /* Are any bits set? */
 770                 return result + size;   /* Nope. */
 771 found_middle:
 772         return result + __ffs(tmp);
 773 }
 774
 775 /*
 776  * find_first_bit - find the first set bit in a memory region
 777  * @addr: The address to start the search at
 778  * @size: The maximum size to search
 779  *
 780  * Returns the bit-number of the first set bit, not the number of the byte
 781  * containing a bit.
 782  */
 783 #define find_first_bit(addr, size) \
 784         find_next_bit((addr), (size), 0)
 785
 786 #ifdef __KERNEL__
 787
 788 /*
 789  * Every architecture must define this function. It's the fastest
 790  * way of searching a 140-bit bitmap where the first 100 bits are
 791  * unlikely to be set. It's guaranteed that at least one of the 140
 792  * bits is cleared.
 793  */
 794 static inline int sched_find_first_bit(const unsigned long *b)
 795 {
 796 #ifdef CONFIG_MIPS32
 797         if (unlikely(b[0]))
 798                 return __ffs(b[0]);
 799         if (unlikely(b[1]))
 800                 return __ffs(b[1]) + 32;
 801         if (unlikely(b[2]))
 802                 return __ffs(b[2]) + 64;
 803         if (b[3])
 804                 return __ffs(b[3]) + 96;
 805         return __ffs(b[4]) + 128;
 806 #endif
 807 #ifdef CONFIG_MIPS64
 808         if (unlikely(b[0]))
 809                 return __ffs(b[0]);
 810         if (unlikely(b[1]))
 811                 return __ffs(b[1]) + 64;
 812         return __ffs(b[2]) + 128;
 813 #endif
 814 }
 815
 816 /*
 817  * ffs - find first bit set
 818  * @x: the word to search
 819  *
 820  * This is defined the same way as
 821  * the libc and compiler builtin ffs routines, therefore
 822  * differs in spirit from the above ffz (man ffs).
 823  */
 824
 825 #define ffs(x) generic_ffs(x)
 826
 827 /*
 828  * hweightN - returns the hamming weight of a N-bit word
 829  * @x: the word to weigh
 830  *
 831  * The Hamming Weight of a number is the total number of bits set in it.
 832  */
 833
 834 #define hweight64(x)    generic_hweight64(x)
 835 #define hweight32(x)    generic_hweight32(x)
 836 #define hweight16(x)    generic_hweight16(x)
 837 #define hweight8(x)     generic_hweight8(x)
 838
 839 static inline int __test_and_set_le_bit(unsigned long nr, unsigned long *addr)
 840 {
 841         unsigned char   *ADDR = (unsigned char *) addr;
 842         int             mask, retval;
 843
 844         ADDR += nr >> 3;
 845         mask = 1 << (nr & 0x07);
 846         retval = (mask & *ADDR) != 0;
 847         *ADDR |= mask;
 848
 849         return retval;
 850 }
 851
 852 static inline int __test_and_clear_le_bit(unsigned long nr, unsigned long *addr)
 853 {
 854         unsigned char   *ADDR = (unsigned char *) addr;
 855         int             mask, retval;
 856
 857         ADDR += nr >> 3;
 858         mask = 1 << (nr & 0x07);
 859         retval = (mask & *ADDR) != 0;
 860         *ADDR &= ~mask;
 861
 862         return retval;
 863 }
 864
 865 static inline int test_le_bit(unsigned long nr, const unsigned long * addr)
 866 {
 867         const unsigned char     *ADDR = (const unsigned char *) addr;
 868         int                     mask;
 869
 870         ADDR += nr >> 3;
 871         mask = 1 << (nr & 0x07);
 872
 873         return ((mask & *ADDR) != 0);
 874 }
 875
 876 static inline unsigned long find_next_zero_le_bit(unsigned long *addr,
 877         unsigned long size, unsigned long offset)
 878 {
 879         unsigned long *p = ((unsigned long *) addr) + (offset >> SZLONG_LOG);
 880         unsigned long result = offset & ~SZLONG_MASK;
 881         unsigned long tmp;
 882
 883         if (offset >= size)
 884                 return size;
 885         size -= result;
 886         offset &= SZLONG_MASK;
 887         if (offset) {
 888                 tmp = cpu_to_lelongp(p++);
 889                 tmp |= ~0UL >> (_MIPS_SZLONG-offset); /* bug or feature ? */
 890                 if (size < _MIPS_SZLONG)
 891                         goto found_first;
 892                 if (~tmp)
 893                         goto found_middle;
 894                 size -= _MIPS_SZLONG;
 895                 result += _MIPS_SZLONG;
 896         }
 897         while (size & ~SZLONG_MASK) {
 898                 if (~(tmp = cpu_to_lelongp(p++)))
 899                         goto found_middle;
 900                 result += _MIPS_SZLONG;
 901                 size -= _MIPS_SZLONG;
 902         }
 903         if (!size)
 904                 return result;
 905         tmp = cpu_to_lelongp(p);
 906
 907 found_first:
 908         tmp |= ~0UL << size;
 909         if (tmp == ~0UL)                /* Are any bits zero? */
 910                 return result + size;   /* Nope. */
 911
 912 found_middle:
 913         return result + ffz(tmp);
 914 }
 915
 916 #define find_first_zero_le_bit(addr, size) \
 917         find_next_zero_le_bit((addr), (size), 0)
 918
 919 #define ext2_set_bit(nr,addr) \
 920         __test_and_set_le_bit((nr),(unsigned long*)addr)
 921 #define ext2_clear_bit(nr, addr) \
 922         __test_and_clear_le_bit((nr),(unsigned long*)addr)
 923  #define ext2_set_bit_atomic(lock, nr, addr)            \
 924 ({                                                      \
 925         int ret;                                        \
 926         spin_lock(lock);                                \
 927         ret = ext2_set_bit((nr), (addr));               \
 928         spin_unlock(lock);                              \
 929         ret;                                            \
 930 })
 931
 932 #define ext2_clear_bit_atomic(lock, nr, addr)           \
 933 ({                                                      \
 934         int ret;                                        \
 935         spin_lock(lock);                                \
 936         ret = ext2_clear_bit((nr), (addr));             \
 937         spin_unlock(lock);                              \
 938         ret;                                            \
 939 })
 940 #define ext2_test_bit(nr, addr) test_le_bit((nr),(unsigned long*)addr)
 941 #define ext2_find_first_zero_bit(addr, size) \
 942         find_first_zero_le_bit((unsigned long*)addr, size)
 943 #define ext2_find_next_zero_bit(addr, size, off) \
 944         find_next_zero_le_bit((unsigned long*)addr, size, off)
 945
 946 /*
 947  * Bitmap functions for the minix filesystem.
 948  *
 949  * FIXME: These assume that Minix uses the native byte/bitorder.
 950  * This limits the Minix filesystem's value for data exchange very much.
 951  */
 952 #define minix_test_and_set_bit(nr,addr) test_and_set_bit(nr,addr)
 953 #define minix_set_bit(nr,addr) set_bit(nr,addr)
 954 #define minix_test_and_clear_bit(nr,addr) test_and_clear_bit(nr,addr)
 955 #define minix_test_bit(nr,addr) test_bit(nr,addr)
 956 #define minix_find_first_zero_bit(addr,size) find_first_zero_bit(addr,size)
 957
 958 #endif /* __KERNEL__ */
 959
 960 #endif /* _ASM_BITOPS_H */