include/asm-mips64/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, 95, 96, 97, 98, 99, 2000  Ralf Baechle
   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/types.h>
  14 #include <asm/byteorder.h>              /* sigh ... */
  15
  16 #ifndef __KERNEL__
  17 #error "Don't do this, sucker ..."
  18 #endif
  19
  20 #include <asm/system.h>
  21 #include <asm/sgidefs.h>
  22
  23 /*
  24  * set_bit - Atomically set a bit in memory
  25  * @nr: the bit to set
  26  * @addr: the address to start counting from
  27  *
  28  * This function is atomic and may not be reordered.  See __set_bit()
  29  * if you do not require the atomic guarantees.
  30  * Note that @nr may be almost arbitrarily large; this function is not
  31  * restricted to acting on a single-word quantity.
  32  */
  33 static inline void set_bit(unsigned long nr, volatile void *addr)
  34 {
  35         unsigned long *m = ((unsigned long *) addr) + (nr >> 6);
  36         unsigned long temp;
  37
  38         __asm__ __volatile__(
  39                 "1:\tlld\t%0, %1\t\t# set_bit\n\t"
  40                 "or\t%0, %2\n\t"
  41                 "scd\t%0, %1\n\t"
  42                 "beqz\t%0, 1b"
  43                 : "=&r" (temp), "=m" (*m)
  44                 : "ir" (1UL << (nr & 0x3f)), "m" (*m)
  45                 : "memory");
  46 }
  47
  48 /*
  49  * __set_bit - Set a bit in memory
  50  * @nr: the bit to set
  51  * @addr: the address to start counting from
  52  *
  53  * Unlike set_bit(), this function is non-atomic and may be reordered.
  54  * If it's called on the same region of memory simultaneously, the effect
  55  * may be that only one operation succeeds.
  56  */
  57 static inline void __set_bit(int nr, volatile void * addr)
  58 {
  59         unsigned long * m = ((unsigned long *) addr) + (nr >> 6);
  60
  61         *m |= 1UL << (nr & 0x3f);
  62 }
  63
  64 /*
  65  * clear_bit - Clears a bit in memory
  66  * @nr: Bit to clear
  67  * @addr: Address to start counting from
  68  *
  69  * clear_bit() is atomic and may not be reordered.  However, it does
  70  * not contain a memory barrier, so if it is used for locking purposes,
  71  * you should call smp_mb__before_clear_bit() and/or smp_mb__after_clear_bit()
  72  * in order to ensure changes are visible on other processors.
  73  */
  74 static inline void clear_bit(unsigned long nr, volatile void *addr)
  75 {
  76         unsigned long *m = ((unsigned long *) addr) + (nr >> 6);
  77         unsigned long temp;
  78
  79         __asm__ __volatile__(
  80                 "1:\tlld\t%0, %1\t\t# clear_bit\n\t"
  81                 "and\t%0, %2\n\t"
  82                 "scd\t%0, %1\n\t"
  83                 "beqz\t%0, 1b\n\t"
  84                 : "=&r" (temp), "=m" (*m)
  85                 : "ir" (~(1UL << (nr & 0x3f))), "m" (*m));
  86 }
  87
  88 #define smp_mb__before_clear_bit()      smp_mb()
  89 #define smp_mb__after_clear_bit()       smp_mb()
  90
  91 /*
  92  * change_bit - Toggle a bit in memory
  93  * @nr: Bit to clear
  94  * @addr: Address to start counting from
  95  *
  96  * change_bit() is atomic and may not be reordered.
  97  * Note that @nr may be almost arbitrarily large; this function is not
  98  * restricted to acting on a single-word quantity.
  99  */
 100 static inline void change_bit(unsigned long nr, volatile void *addr)
 101 {
 102         unsigned long *m = ((unsigned long *) addr) + (nr >> 6);
 103         unsigned long temp;
 104
 105         __asm__ __volatile__(
 106                 "1:\tlld\t%0, %1\t\t# change_bit\n\t"
 107                 "xor\t%0, %2\n\t"
 108                 "scd\t%0, %1\n\t"
 109                 "beqz\t%0, 1b"
 110                 :"=&r" (temp), "=m" (*m)
 111                 :"ir" (1UL << (nr & 0x3f)), "m" (*m));
 112 }
 113
 114 /*
 115  * __change_bit - Toggle a bit in memory
 116  * @nr: the bit to set
 117  * @addr: the address to start counting from
 118  *
 119  * Unlike change_bit(), this function is non-atomic and may be reordered.
 120  * If it's called on the same region of memory simultaneously, the effect
 121  * may be that only one operation succeeds.
 122  */
 123 static inline void __change_bit(int nr, volatile void * addr)
 124 {
 125         unsigned long * m = ((unsigned long *) addr) + (nr >> 6);
 126
 127         *m ^= 1UL << (nr & 0x3f);
 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 also implies a memory barrier.
 137  */
 138 static inline unsigned long test_and_set_bit(unsigned long nr,
 139                                              volatile void *addr)
 140 {
 141         unsigned long *m = ((unsigned long *) addr) + (nr >> 6);
 142         unsigned long temp, res;
 143
 144         __asm__ __volatile__(
 145                 ".set\tnoreorder\t\t# test_and_set_bit\n"
 146                 "1:\tlld\t%0, %1\n\t"
 147                 "or\t%2, %0, %3\n\t"
 148                 "scd\t%2, %1\n\t"
 149                 "beqz\t%2, 1b\n\t"
 150                 " and\t%2, %0, %3\n\t"
 151 #ifdef CONFIG_SMP
 152                 "sync\n\t"
 153 #endif
 154                 ".set\treorder"
 155                 : "=&r" (temp), "=m" (*m), "=&r" (res)
 156                 : "r" (1UL << (nr & 0x3f)), "m" (*m)
 157                 : "memory");
 158
 159         return res != 0;
 160 }
 161
 162 /*
 163  * __test_and_set_bit - Set a bit and return its old value
 164  * @nr: Bit to set
 165  * @addr: Address to count from
 166  *
 167  * This operation is non-atomic and can be reordered.
 168  * If two examples of this operation race, one can appear to succeed
 169  * but actually fail.  You must protect multiple accesses with a lock.
 170  */
 171 static inline int __test_and_set_bit(int nr, volatile void *addr)
 172 {
 173         unsigned long mask, retval;
 174         long *a = (unsigned long *) addr;
 175
 176         a += (nr >> 6);
 177         mask = 1UL << (nr & 0x3f);
 178         retval = ((mask & *a) != 0);
 179         *a |= mask;
 180
 181         return retval;
 182 }
 183
 184 /*
 185  * test_and_clear_bit - Clear a bit and return its old value
 186  * @nr: Bit to set
 187  * @addr: Address to count from
 188  *
 189  * This operation is atomic and cannot be reordered.
 190  * It also implies a memory barrier.
 191  */
 192 static inline unsigned long test_and_clear_bit(unsigned long nr,
 193                                                volatile void *addr)
 194 {
 195         unsigned long *m = ((unsigned long *) addr) + (nr >> 6);
 196         unsigned long temp, res;
 197
 198         __asm__ __volatile__(
 199                 ".set\tnoreorder\t\t# test_and_clear_bit\n"
 200                 "1:\tlld\t%0, %1\n\t"
 201                 "or\t%2, %0, %3\n\t"
 202                 "xor\t%2, %3\n\t"
 203                 "scd\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 & 0x3f)), "m" (*m)
 212                 : "memory");
 213
 214         return res != 0;
 215 }
 216
 217 /*
 218  * __test_and_clear_bit - Clear 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_clear_bit(int nr, volatile void * addr)
 227 {
 228         unsigned long mask, retval;
 229         unsigned long *a = (unsigned long *) addr;
 230
 231         a += (nr >> 6);
 232         mask = 1UL << (nr & 0x3f);
 233         retval = ((mask & *a) != 0);
 234         *a &= ~mask;
 235
 236         return retval;
 237 }
 238
 239 /*
 240  * test_and_change_bit - Change a bit and return its new value
 241  * @nr: Bit to set
 242  * @addr: Address to count from
 243  *
 244  * This operation is atomic and cannot be reordered.
 245  * It also implies a memory barrier.
 246  */
 247 static inline unsigned long test_and_change_bit(unsigned long nr,
 248                                                 volatile void *addr)
 249 {
 250         unsigned long *m = ((unsigned long *) addr) + (nr >> 6);
 251         unsigned long temp, res;
 252
 253         __asm__ __volatile__(
 254                 ".set\tnoreorder\t\t# test_and_change_bit\n"
 255                 "1:\tlld\t%0, %1\n\t"
 256                 "xor\t%2, %0, %3\n\t"
 257                 "scd\t%2, %1\n\t"
 258                 "beqz\t%2, 1b\n\t"
 259                 " and\t%2, %0, %3\n\t"
 260 #ifdef CONFIG_SMP
 261                 "sync\n\t"
 262 #endif
 263                 ".set\treorder"
 264                 : "=&r" (temp), "=m" (*m), "=&r" (res)
 265                 : "r" (1UL << (nr & 0x3f)), "m" (*m)
 266                 : "memory");
 267
 268         return res != 0;
 269 }
 270
 271 /*
 272  * __test_and_change_bit - Change a bit and return its old value
 273  * @nr: Bit to set
 274  * @addr: Address to count from
 275  *
 276  * This operation is non-atomic and can be reordered.
 277  * If two examples of this operation race, one can appear to succeed
 278  * but actually fail.  You must protect multiple accesses with a lock.
 279  */
 280 static inline int __test_and_change_bit(int nr, volatile void *addr)
 281 {
 282         unsigned long mask, retval;
 283         unsigned long *a = (unsigned long *) addr;
 284
 285         a += (nr >> 6);
 286         mask = 1UL << (nr & 0x3f);
 287         retval = ((mask & *a) != 0);
 288         *a ^= mask;
 289
 290         return retval;
 291 }
 292 /*
 293  * test_bit - Determine whether a bit is set
 294  * @nr: bit number to test
 295  * @addr: Address to start counting from
 296  */
 297 static inline unsigned long test_bit(int nr, volatile void * addr)
 298 {
 299         return 1UL & (((volatile unsigned long *) addr)[nr >> 6] >> (nr & 0x3f));
 300 }
 301
 302 #ifndef __MIPSEB__
 303
 304 /* Little endian versions. */
 305
 306 /*
 307  * find_first_zero_bit - find the first zero bit in a memory region
 308  * @addr: The address to start the search at
 309  * @size: The maximum size to search
 310  *
 311  * Returns the bit-number of the first zero bit, not the number of the byte
 312  * containing a bit.
 313  */
 314 static inline int find_first_zero_bit (void *addr, unsigned size)
 315 {
 316         unsigned long dummy;
 317         int res;
 318
 319         if (!size)
 320                 return 0;
 321
 322         __asm__ (".set\tnoreorder\n\t"
 323                 ".set\tnoat\n"
 324                 "1:\tsubu\t$1,%6,%0\n\t"
 325                 "blez\t$1,2f\n\t"
 326                 "lw\t$1,(%5)\n\t"
 327                 "addiu\t%5,4\n\t"
 328 #if (_MIPS_ISA == _MIPS_ISA_MIPS2 ) || (_MIPS_ISA == _MIPS_ISA_MIPS3 ) || \
 329     (_MIPS_ISA == _MIPS_ISA_MIPS4 ) || (_MIPS_ISA == _MIPS_ISA_MIPS5 ) || \
 330     (_MIPS_ISA == _MIPS_ISA_MIPS32) || (_MIPS_ISA == _MIPS_ISA_MIPS64)
 331                 "beql\t%1,$1,1b\n\t"
 332                 "addiu\t%0,32\n\t"
 333 #else
 334                 "addiu\t%0,32\n\t"
 335                 "beq\t%1,$1,1b\n\t"
 336                 "nop\n\t"
 337                 "subu\t%0,32\n\t"
 338 #endif
 339                 "li\t%1,1\n"
 340                 "1:\tand\t%2,$1,%1\n\t"
 341                 "beqz\t%2,2f\n\t"
 342                 "sll\t%1,%1,1\n\t"
 343                 "bnez\t%1,1b\n\t"
 344                 "add\t%0,%0,1\n\t"
 345                 ".set\tat\n\t"
 346                 ".set\treorder\n"
 347                 "2:"
 348                 : "=r" (res), "=r" (dummy), "=r" (addr)
 349                 : "0" ((signed int) 0), "1" ((unsigned int) 0xffffffff),
 350                   "2" (addr), "r" (size));
 351
 352         return res;
 353 }
 354
 355 /*
 356  * find_next_zero_bit - find the first zero bit in a memory region
 357  * @addr: The address to base the search on
 358  * @offset: The bitnumber to start searching at
 359  * @size: The maximum size to search
 360  */
 361 static inline int find_next_zero_bit (void * addr, int size, int offset)
 362 {
 363         unsigned int *p = ((unsigned int *) addr) + (offset >> 5);
 364         int set = 0, bit = offset & 31, res;
 365         unsigned long dummy;
 366
 367         if (bit) {
 368                 /*
 369                  * Look for zero in first byte
 370                  */
 371                 __asm__(".set\tnoreorder\n\t"
 372                         ".set\tnoat\n"
 373                         "1:\tand\t$1,%4,%1\n\t"
 374                         "beqz\t$1,1f\n\t"
 375                         "sll\t%1,%1,1\n\t"
 376                         "bnez\t%1,1b\n\t"
 377                         "addiu\t%0,1\n\t"
 378                         ".set\tat\n\t"
 379                         ".set\treorder\n"
 380                         "1:"
 381                         : "=r" (set), "=r" (dummy)
 382                         : "0" (0), "1" (1 << bit), "r" (*p));
 383                 if (set < (32 - bit))
 384                         return set + offset;
 385                 set = 32 - bit;
 386                 p++;
 387         }
 388         /*
 389          * No zero yet, search remaining full bytes for a zero
 390          */
 391         res = find_first_zero_bit(p, size - 32 * (p - (unsigned int *) addr));
 392         return offset + set + res;
 393 }
 394
 395 #endif /* !(__MIPSEB__) */
 396
 397 /*
 398  * ffz - find first zero in word.
 399  * @word: The word to search
 400  *
 401  * Undefined if no zero exists, so code should check against ~0UL first.
 402  */
 403 static __inline__ unsigned long ffz(unsigned long word)
 404 {
 405         int b = 0, s;
 406
 407         word = ~word;
 408         s = 32; if (word << 32 != 0) s = 0; b += s; word >>= s;
 409         s = 16; if (word << 48 != 0) s = 0; b += s; word >>= s;
 410         s =  8; if (word << 56 != 0) s = 0; b += s; word >>= s;
 411         s =  4; if (word << 60 != 0) s = 0; b += s; word >>= s;
 412         s =  2; if (word << 62 != 0) s = 0; b += s; word >>= s;
 413         s =  1; if (word << 63 != 0) s = 0; b += s;
 414
 415         return b;
 416 }
 417
 418 #ifdef __KERNEL__
 419
 420
 421 /*
 422  * ffs - find first bit set
 423  * @x: the word to search
 424  *
 425  * This is defined the same way as
 426  * the libc and compiler builtin ffs routines, therefore
 427  * differs in spirit from the above ffz (man ffs).
 428  */
 429
 430 #define ffs(x) generic_ffs(x)
 431
 432 /*
 433  * hweightN - returns the hamming weight of a N-bit word
 434  * @x: the word to weigh
 435  *
 436  * The Hamming Weight of a number is the total number of bits set in it.
 437  */
 438
 439 #define hweight32(x) generic_hweight32(x)
 440 #define hweight16(x) generic_hweight16(x)
 441 #define hweight8(x)  generic_hweight8(x)
 442
 443 #endif /* __KERNEL__ */
 444
 445 #ifdef __MIPSEB__
 446
 447 /*
 448  * find_next_zero_bit - find the first zero bit in a memory region
 449  * @addr: The address to base the search on
 450  * @offset: The bitnumber to start searching at
 451  * @size: The maximum size to search
 452  */
 453 static inline unsigned long find_next_zero_bit(void *addr, unsigned long size,
 454                                                unsigned long offset)
 455 {
 456         unsigned long *p = ((unsigned long *) addr) + (offset >> 6);
 457         unsigned long result = offset & ~63UL;
 458         unsigned long tmp;
 459
 460         if (offset >= size)
 461                 return size;
 462         size -= result;
 463         offset &= 63UL;
 464         if (offset) {
 465                 tmp = *(p++);
 466                 tmp |= ~0UL >> (64-offset);
 467                 if (size < 64)
 468                         goto found_first;
 469                 if (~tmp)
 470                         goto found_middle;
 471                 size -= 64;
 472                 result += 64;
 473         }
 474         while (size & ~63UL) {
 475                 if (~(tmp = *(p++)))
 476                         goto found_middle;
 477                 result += 64;
 478                 size -= 64;
 479         }
 480         if (!size)
 481                 return result;
 482         tmp = *p;
 483
 484 found_first:
 485         tmp |= ~0UL << size;
 486 found_middle:
 487         return result + ffz(tmp);
 488 }
 489
 490 #define find_first_zero_bit(addr, size) \
 491         find_next_zero_bit((addr), (size), 0)
 492
 493 #endif /* (__MIPSEB__) */
 494
 495 #ifdef __KERNEL__
 496
 497 /* Now for the ext2 filesystem bit operations and helper routines. */
 498
 499 #ifdef __MIPSEB__
 500
 501 static inline int ext2_set_bit(int nr,void * addr)
 502 {
 503         int             mask, retval, flags;
 504         unsigned char   *ADDR = (unsigned char *) addr;
 505
 506         ADDR += nr >> 3;
 507         mask = 1 << (nr & 0x07);
 508         save_and_cli(flags);
 509         retval = (mask & *ADDR) != 0;
 510         *ADDR |= mask;
 511         restore_flags(flags);
 512         return retval;
 513 }
 514
 515 static inline int ext2_clear_bit(int nr, void * addr)
 516 {
 517         int             mask, retval, flags;
 518         unsigned char   *ADDR = (unsigned char *) addr;
 519
 520         ADDR += nr >> 3;
 521         mask = 1 << (nr & 0x07);
 522         save_and_cli(flags);
 523         retval = (mask & *ADDR) != 0;
 524         *ADDR &= ~mask;
 525         restore_flags(flags);
 526         return retval;
 527 }
 528
 529 static inline int ext2_test_bit(int nr, const void * addr)
 530 {
 531         int                     mask;
 532         const unsigned char     *ADDR = (const unsigned char *) addr;
 533
 534         ADDR += nr >> 3;
 535         mask = 1 << (nr & 0x07);
 536         return ((mask & *ADDR) != 0);
 537 }
 538
 539 #define ext2_find_first_zero_bit(addr, size) \
 540         ext2_find_next_zero_bit((addr), (size), 0)
 541
 542 static inline unsigned int ext2_find_next_zero_bit(void *addr,
 543                                                    unsigned long size,
 544                                                    unsigned long offset)
 545 {
 546         unsigned int *p = ((unsigned int *) addr) + (offset >> 5);
 547         unsigned int result = offset & ~31UL;
 548         unsigned int tmp;
 549
 550         if (offset >= size)
 551                 return size;
 552         size -= result;
 553         offset &= 31UL;
 554         if(offset) {
 555                 /* We hold the little endian value in tmp, but then the
 556                  * shift is illegal. So we could keep a big endian value
 557                  * in tmp, like this:
 558                  *
 559                  * tmp = __swab32(*(p++));
 560                  * tmp |= ~0UL >> (32-offset);
 561                  *
 562                  * but this would decrease preformance, so we change the
 563                  * shift:
 564                  */
 565                 tmp = *(p++);
 566                 tmp |= __swab32(~0UL >> (32-offset));
 567                 if(size < 32)
 568                         goto found_first;
 569                 if(~tmp)
 570                         goto found_middle;
 571                 size -= 32;
 572                 result += 32;
 573         }
 574         while(size & ~31UL) {
 575                 if(~(tmp = *(p++)))
 576                         goto found_middle;
 577                 result += 32;
 578                 size -= 32;
 579         }
 580         if(!size)
 581                 return result;
 582         tmp = *p;
 583
 584 found_first:
 585         /* tmp is little endian, so we would have to swab the shift,
 586          * see above. But then we have to swab tmp below for ffz, so
 587          * we might as well do this here.
 588          */
 589         return result + ffz(__swab32(tmp) | (~0UL << size));
 590 found_middle:
 591         return result + ffz(__swab32(tmp));
 592 }
 593 #else /* !(__MIPSEB__) */
 594
 595 /* Native ext2 byte ordering, just collapse using defines. */
 596 #define ext2_set_bit(nr, addr) test_and_set_bit((nr), (addr))
 597 #define ext2_clear_bit(nr, addr) test_and_clear_bit((nr), (addr))
 598 #define ext2_test_bit(nr, addr) test_bit((nr), (addr))
 599 #define ext2_find_first_zero_bit(addr, size) find_first_zero_bit((addr), (size))
 600 #define ext2_find_next_zero_bit(addr, size, offset) \
 601                 find_next_zero_bit((addr), (size), (offset))
 602
 603 #endif /* !(__MIPSEB__) */
 604
 605 /*
 606  * Bitmap functions for the minix filesystem.
 607  * FIXME: These assume that Minix uses the native byte/bitorder.
 608  * This limits the Minix filesystem's value for data exchange very much.
 609  */
 610 #define minix_test_and_set_bit(nr,addr) test_and_set_bit(nr,addr)
 611 #define minix_set_bit(nr,addr) set_bit(nr,addr)
 612 #define minix_test_and_clear_bit(nr,addr) test_and_clear_bit(nr,addr)
 613 #define minix_test_bit(nr,addr) test_bit(nr,addr)
 614 #define minix_find_first_zero_bit(addr,size) find_first_zero_bit(addr,size)
 615
 616 #endif /* __KERNEL__ */
 617
 618 #endif /* _ASM_BITOPS_H */