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, 06  Ralf Baechle (ralf@linux-mips.org)
   7  * Copyright (c) 1999, 2000  Silicon Graphics, Inc.
   8  */
   9 #ifndef _ASM_BITOPS_H
  10 #define _ASM_BITOPS_H
  11
  12 #include <linux/compiler.h>
  13 #include <linux/irqflags.h>
  14 #include <linux/types.h>
  15 #include <asm/barrier.h>
  16 #include <asm/bug.h>
  17 #include <asm/byteorder.h>              /* sigh ... */
  18 #include <asm/cpu-features.h>
  19 #include <asm/sgidefs.h>
  20 #include <asm/war.h>
  21
  22 #if (_MIPS_SZLONG == 32)
  23 #define SZLONG_LOG 5
  24 #define SZLONG_MASK 31UL
  25 #define __LL            "ll     "
  26 #define __SC            "sc     "
  27 #elif (_MIPS_SZLONG == 64)
  28 #define SZLONG_LOG 6
  29 #define SZLONG_MASK 63UL
  30 #define __LL            "lld    "
  31 #define __SC            "scd    "
  32 #endif
  33
  34 /*
  35  * clear_bit() doesn't provide any barrier for the compiler.
  36  */
  37 #define smp_mb__before_clear_bit()      smp_mb()
  38 #define smp_mb__after_clear_bit()       smp_mb()
  39
  40 /*
  41  * set_bit - Atomically set a bit in memory
  42  * @nr: the bit to set
  43  * @addr: the address to start counting from
  44  *
  45  * This function is atomic and may not be reordered.  See __set_bit()
  46  * if you do not require the atomic guarantees.
  47  * Note that @nr may be almost arbitrarily large; this function is not
  48  * restricted to acting on a single-word quantity.
  49  */
  50 static inline void set_bit(unsigned long nr, volatile unsigned long *addr)
  51 {
  52         unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
  53         unsigned long temp;
  54
  55         if (cpu_has_llsc && R10000_LLSC_WAR) {
  56                 __asm__ __volatile__(
  57                 "       .set    mips3                                   \n"
  58                 "1:     " __LL "%0, %1                  # set_bit       \n"
  59                 "       or      %0, %2                                  \n"
  60                 "       " __SC  "%0, %1                                 \n"
  61                 "       beqzl   %0, 1b                                  \n"
  62                 "       .set    mips0                                   \n"
  63                 : "=&r" (temp), "=m" (*m)
  64                 : "ir" (1UL << (nr & SZLONG_MASK)), "m" (*m));
  65         } else if (cpu_has_llsc) {
  66                 __asm__ __volatile__(
  67                 "       .set    mips3                                   \n"
  68                 "1:     " __LL "%0, %1                  # set_bit       \n"
  69                 "       or      %0, %2                                  \n"
  70                 "       " __SC  "%0, %1                                 \n"
  71                 "       beqz    %0, 2f                                  \n"
  72                 "       .subsection 2                                   \n"
  73                 "2:     b       1b                                      \n"
  74                 "       .previous                                       \n"
  75                 "       .set    mips0                                   \n"
  76                 : "=&r" (temp), "=m" (*m)
  77                 : "ir" (1UL << (nr & SZLONG_MASK)), "m" (*m));
  78         } else {
  79                 volatile unsigned long *a = addr;
  80                 unsigned long mask;
  81                 unsigned long flags;
  82
  83                 a += nr >> SZLONG_LOG;
  84                 mask = 1UL << (nr & SZLONG_MASK);
  85                 local_irq_save(flags);
  86                 *a |= mask;
  87                 local_irq_restore(flags);
  88         }
  89 }
  90
  91 /*
  92  * clear_bit - Clears a bit in memory
  93  * @nr: Bit to clear
  94  * @addr: Address to start counting from
  95  *
  96  * clear_bit() is atomic and may not be reordered.  However, it does
  97  * not contain a memory barrier, so if it is used for locking purposes,
  98  * you should call smp_mb__before_clear_bit() and/or smp_mb__after_clear_bit()
  99  * in order to ensure changes are visible on other processors.
 100  */
 101 static inline void clear_bit(unsigned long nr, volatile unsigned long *addr)
 102 {
 103         unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 104         unsigned long temp;
 105
 106         if (cpu_has_llsc && R10000_LLSC_WAR) {
 107                 __asm__ __volatile__(
 108                 "       .set    mips3                                   \n"
 109                 "1:     " __LL "%0, %1                  # clear_bit     \n"
 110                 "       and     %0, %2                                  \n"
 111                 "       " __SC "%0, %1                                  \n"
 112                 "       beqzl   %0, 1b                                  \n"
 113                 "       .set    mips0                                   \n"
 114                 : "=&r" (temp), "=m" (*m)
 115                 : "ir" (~(1UL << (nr & SZLONG_MASK))), "m" (*m));
 116         } else if (cpu_has_llsc) {
 117                 __asm__ __volatile__(
 118                 "       .set    mips3                                   \n"
 119                 "1:     " __LL "%0, %1                  # clear_bit     \n"
 120                 "       and     %0, %2                                  \n"
 121                 "       " __SC "%0, %1                                  \n"
 122                 "       beqz    %0, 2f                                  \n"
 123                 "       .subsection 2                                   \n"
 124                 "2:     b       1b                                      \n"
 125                 "       .previous                                       \n"
 126                 "       .set    mips0                                   \n"
 127                 : "=&r" (temp), "=m" (*m)
 128                 : "ir" (~(1UL << (nr & SZLONG_MASK))), "m" (*m));
 129         } else {
 130                 volatile unsigned long *a = addr;
 131                 unsigned long mask;
 132                 unsigned long flags;
 133
 134                 a += nr >> SZLONG_LOG;
 135                 mask = 1UL << (nr & SZLONG_MASK);
 136                 local_irq_save(flags);
 137                 *a &= ~mask;
 138                 local_irq_restore(flags);
 139         }
 140 }
 141
 142 /*
 143  * change_bit - Toggle a bit in memory
 144  * @nr: Bit to change
 145  * @addr: Address to start counting from
 146  *
 147  * change_bit() is atomic and may not be reordered.
 148  * Note that @nr may be almost arbitrarily large; this function is not
 149  * restricted to acting on a single-word quantity.
 150  */
 151 static inline void change_bit(unsigned long nr, volatile unsigned long *addr)
 152 {
 153         if (cpu_has_llsc && R10000_LLSC_WAR) {
 154                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 155                 unsigned long temp;
 156
 157                 __asm__ __volatile__(
 158                 "       .set    mips3                           \n"
 159                 "1:     " __LL "%0, %1          # change_bit    \n"
 160                 "       xor     %0, %2                          \n"
 161                 "       " __SC  "%0, %1                         \n"
 162                 "       beqzl   %0, 1b                          \n"
 163                 "       .set    mips0                           \n"
 164                 : "=&r" (temp), "=m" (*m)
 165                 : "ir" (1UL << (nr & SZLONG_MASK)), "m" (*m));
 166         } else if (cpu_has_llsc) {
 167                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 168                 unsigned long temp;
 169
 170                 __asm__ __volatile__(
 171                 "       .set    mips3                           \n"
 172                 "1:     " __LL "%0, %1          # change_bit    \n"
 173                 "       xor     %0, %2                          \n"
 174                 "       " __SC  "%0, %1                         \n"
 175                 "       beqz    %0, 2f                          \n"
 176                 "       .subsection 2                           \n"
 177                 "2:     b       1b                              \n"
 178                 "       .previous                               \n"
 179                 "       .set    mips0                           \n"
 180                 : "=&r" (temp), "=m" (*m)
 181                 : "ir" (1UL << (nr & SZLONG_MASK)), "m" (*m));
 182         } else {
 183                 volatile unsigned long *a = addr;
 184                 unsigned long mask;
 185                 unsigned long flags;
 186
 187                 a += nr >> SZLONG_LOG;
 188                 mask = 1UL << (nr & SZLONG_MASK);
 189                 local_irq_save(flags);
 190                 *a ^= mask;
 191                 local_irq_restore(flags);
 192         }
 193 }
 194
 195 /*
 196  * test_and_set_bit - Set a bit and return its old value
 197  * @nr: Bit to set
 198  * @addr: Address to count from
 199  *
 200  * This operation is atomic and cannot be reordered.
 201  * It also implies a memory barrier.
 202  */
 203 static inline int test_and_set_bit(unsigned long nr,
 204         volatile unsigned long *addr)
 205 {
 206         if (cpu_has_llsc && R10000_LLSC_WAR) {
 207                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 208                 unsigned long temp, res;
 209
 210                 __asm__ __volatile__(
 211                 "       .set    mips3                                   \n"
 212                 "1:     " __LL "%0, %1          # test_and_set_bit      \n"
 213                 "       or      %2, %0, %3                              \n"
 214                 "       " __SC  "%2, %1                                 \n"
 215                 "       beqzl   %2, 1b                                  \n"
 216                 "       and     %2, %0, %3                              \n"
 217                 "       .set    mips0                                   \n"
 218                 : "=&r" (temp), "=m" (*m), "=&r" (res)
 219                 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
 220                 : "memory");
 221
 222                 return res != 0;
 223         } else if (cpu_has_llsc) {
 224                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 225                 unsigned long temp, res;
 226
 227                 __asm__ __volatile__(
 228                 "       .set    push                                    \n"
 229                 "       .set    noreorder                               \n"
 230                 "       .set    mips3                                   \n"
 231                 "1:     " __LL "%0, %1          # test_and_set_bit      \n"
 232                 "       or      %2, %0, %3                              \n"
 233                 "       " __SC  "%2, %1                                 \n"
 234                 "       beqz    %2, 2f                                  \n"
 235                 "        and    %2, %0, %3                              \n"
 236                 "       .subsection 2                                   \n"
 237                 "2:     b       1b                                      \n"
 238                 "        nop                                            \n"
 239                 "       .previous                                       \n"
 240                 "       .set    pop                                     \n"
 241                 : "=&r" (temp), "=m" (*m), "=&r" (res)
 242                 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
 243                 : "memory");
 244
 245                 return res != 0;
 246         } else {
 247                 volatile unsigned long *a = addr;
 248                 unsigned long mask;
 249                 int retval;
 250                 unsigned long flags;
 251
 252                 a += nr >> SZLONG_LOG;
 253                 mask = 1UL << (nr & SZLONG_MASK);
 254                 local_irq_save(flags);
 255                 retval = (mask & *a) != 0;
 256                 *a |= mask;
 257                 local_irq_restore(flags);
 258
 259                 return retval;
 260         }
 261
 262         smp_mb();
 263 }
 264
 265 /*
 266  * test_and_clear_bit - Clear a bit and return its old value
 267  * @nr: Bit to clear
 268  * @addr: Address to count from
 269  *
 270  * This operation is atomic and cannot be reordered.
 271  * It also implies a memory barrier.
 272  */
 273 static inline int test_and_clear_bit(unsigned long nr,
 274         volatile unsigned long *addr)
 275 {
 276         if (cpu_has_llsc && R10000_LLSC_WAR) {
 277                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 278                 unsigned long temp, res;
 279
 280                 __asm__ __volatile__(
 281                 "       .set    mips3                                   \n"
 282                 "1:     " __LL  "%0, %1         # test_and_clear_bit    \n"
 283                 "       or      %2, %0, %3                              \n"
 284                 "       xor     %2, %3                                  \n"
 285                 "       " __SC  "%2, %1                                 \n"
 286                 "       beqzl   %2, 1b                                  \n"
 287                 "       and     %2, %0, %3                              \n"
 288                 "       .set    mips0                                   \n"
 289                 : "=&r" (temp), "=m" (*m), "=&r" (res)
 290                 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
 291                 : "memory");
 292
 293                 return res != 0;
 294         } else if (cpu_has_llsc) {
 295                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 296                 unsigned long temp, res;
 297
 298                 __asm__ __volatile__(
 299                 "       .set    push                                    \n"
 300                 "       .set    noreorder                               \n"
 301                 "       .set    mips3                                   \n"
 302                 "1:     " __LL  "%0, %1         # test_and_clear_bit    \n"
 303                 "       or      %2, %0, %3                              \n"
 304                 "       xor     %2, %3                                  \n"
 305                 "       " __SC  "%2, %1                                 \n"
 306                 "       beqz    %2, 2f                                  \n"
 307                 "        and    %2, %0, %3                              \n"
 308                 "       .subsection 2                                   \n"
 309                 "2:     b       1b                                      \n"
 310                 "        nop                                            \n"
 311                 "       .previous                                       \n"
 312                 "       .set    pop                                     \n"
 313                 : "=&r" (temp), "=m" (*m), "=&r" (res)
 314                 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
 315                 : "memory");
 316
 317                 return res != 0;
 318         } else {
 319                 volatile unsigned long *a = addr;
 320                 unsigned long mask;
 321                 int retval;
 322                 unsigned long flags;
 323
 324                 a += nr >> SZLONG_LOG;
 325                 mask = 1UL << (nr & SZLONG_MASK);
 326                 local_irq_save(flags);
 327                 retval = (mask & *a) != 0;
 328                 *a &= ~mask;
 329                 local_irq_restore(flags);
 330
 331                 return retval;
 332         }
 333
 334         smp_mb();
 335 }
 336
 337 /*
 338  * test_and_change_bit - Change a bit and return its old value
 339  * @nr: Bit to change
 340  * @addr: Address to count from
 341  *
 342  * This operation is atomic and cannot be reordered.
 343  * It also implies a memory barrier.
 344  */
 345 static inline int test_and_change_bit(unsigned long nr,
 346         volatile unsigned long *addr)
 347 {
 348         if (cpu_has_llsc && R10000_LLSC_WAR) {
 349                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 350                 unsigned long temp, res;
 351
 352                 __asm__ __volatile__(
 353                 "       .set    mips3                                   \n"
 354                 "1:     " __LL  "%0, %1         # test_and_change_bit   \n"
 355                 "       xor     %2, %0, %3                              \n"
 356                 "       " __SC  "%2, %1                                 \n"
 357                 "       beqzl   %2, 1b                                  \n"
 358                 "       and     %2, %0, %3                              \n"
 359                 "       .set    mips0                                   \n"
 360                 : "=&r" (temp), "=m" (*m), "=&r" (res)
 361                 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
 362                 : "memory");
 363
 364                 return res != 0;
 365         } else if (cpu_has_llsc) {
 366                 unsigned long *m = ((unsigned long *) addr) + (nr >> SZLONG_LOG);
 367                 unsigned long temp, res;
 368
 369                 __asm__ __volatile__(
 370                 "       .set    push                                    \n"
 371                 "       .set    noreorder                               \n"
 372                 "       .set    mips3                                   \n"
 373                 "1:     " __LL  "%0, %1         # test_and_change_bit   \n"
 374                 "       xor     %2, %0, %3                              \n"
 375                 "       " __SC  "\t%2, %1                               \n"
 376                 "       beqz    %2, 2f                                  \n"
 377                 "        and    %2, %0, %3                              \n"
 378                 "       .subsection 2                                   \n"
 379                 "2:     b       1b                                      \n"
 380                 "        nop                                            \n"
 381                 "       .previous                                       \n"
 382                 "       .set    pop                                     \n"
 383                 : "=&r" (temp), "=m" (*m), "=&r" (res)
 384                 : "r" (1UL << (nr & SZLONG_MASK)), "m" (*m)
 385                 : "memory");
 386
 387                 return res != 0;
 388         } else {
 389                 volatile unsigned long *a = addr;
 390                 unsigned long mask, retval;
 391                 unsigned long flags;
 392
 393                 a += nr >> SZLONG_LOG;
 394                 mask = 1UL << (nr & SZLONG_MASK);
 395                 local_irq_save(flags);
 396                 retval = (mask & *a) != 0;
 397                 *a ^= mask;
 398                 local_irq_restore(flags);
 399
 400                 return retval;
 401         }
 402
 403         smp_mb();
 404 }
 405
 406 #include <asm-generic/bitops/non-atomic.h>
 407
 408 /*
 409  * Return the bit position (0..63) of the most significant 1 bit in a word
 410  * Returns -1 if no 1 bit exists
 411  */
 412 static inline int __ilog2(unsigned long x)
 413 {
 414         int lz;
 415
 416         if (sizeof(x) == 4) {
 417                 __asm__ (
 418                 "       .set    push                                    \n"
 419                 "       .set    mips32                                  \n"
 420                 "       clz     %0, %1                                  \n"
 421                 "       .set    pop                                     \n"
 422                 : "=r" (lz)
 423                 : "r" (x));
 424
 425                 return 31 - lz;
 426         }
 427
 428         BUG_ON(sizeof(x) != 8);
 429
 430         __asm__ (
 431         "       .set    push                                            \n"
 432         "       .set    mips64                                          \n"
 433         "       dclz    %0, %1                                          \n"
 434         "       .set    pop                                             \n"
 435         : "=r" (lz)
 436         : "r" (x));
 437
 438         return 63 - lz;
 439 }
 440
 441 #if defined(CONFIG_CPU_MIPS32) || defined(CONFIG_CPU_MIPS64)
 442
 443 /*
 444  * __ffs - find first bit in word.
 445  * @word: The word to search
 446  *
 447  * Returns 0..SZLONG-1
 448  * Undefined if no bit exists, so code should check against 0 first.
 449  */
 450 static inline unsigned long __ffs(unsigned long word)
 451 {
 452         return __ilog2(word & -word);
 453 }
 454
 455 /*
 456  * fls - find last bit set.
 457  * @word: The word to search
 458  *
 459  * This is defined the same way as ffs.
 460  * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.
 461  */
 462 static inline int fls(int word)
 463 {
 464         __asm__ ("clz %0, %1" : "=r" (word) : "r" (word));
 465
 466         return 32 - word;
 467 }
 468
 469 #if defined(CONFIG_64BIT) && defined(CONFIG_CPU_MIPS64)
 470 static inline int fls64(__u64 word)
 471 {
 472         __asm__ ("dclz %0, %1" : "=r" (word) : "r" (word));
 473
 474         return 64 - word;
 475 }
 476 #else
 477 #include <asm-generic/bitops/fls64.h>
 478 #endif
 479
 480 /*
 481  * ffs - find first bit set.
 482  * @word: The word to search
 483  *
 484  * This is defined the same way as
 485  * the libc and compiler builtin ffs routines, therefore
 486  * differs in spirit from the above ffz (man ffs).
 487  */
 488 static inline int ffs(int word)
 489 {
 490         if (!word)
 491                 return 0;
 492
 493         return fls(word & -word);
 494 }
 495
 496 #else
 497
 498 #include <asm-generic/bitops/__ffs.h>
 499 #include <asm-generic/bitops/ffs.h>
 500 #include <asm-generic/bitops/fls.h>
 501 #include <asm-generic/bitops/fls64.h>
 502
 503 #endif /*defined(CONFIG_CPU_MIPS32) || defined(CONFIG_CPU_MIPS64) */
 504
 505 #include <asm-generic/bitops/ffz.h>
 506 #include <asm-generic/bitops/find.h>
 507
 508 #ifdef __KERNEL__
 509
 510 #include <asm-generic/bitops/sched.h>
 511 #include <asm-generic/bitops/hweight.h>
 512 #include <asm-generic/bitops/ext2-non-atomic.h>
 513 #include <asm-generic/bitops/ext2-atomic.h>
 514 #include <asm-generic/bitops/minix.h>
 515
 516 #endif /* __KERNEL__ */
 517
 518 #endif /* _ASM_BITOPS_H */