include/asm-ppc/bitops.h

   1 /*
   2  * bitops.h: Bit string operations on the ppc
   3  */
   4
   5 #ifdef __KERNEL__
   6 #ifndef _PPC_BITOPS_H
   7 #define _PPC_BITOPS_H
   8
   9 #include <linux/config.h>
  10 #include <linux/compiler.h>
  11 #include <asm/byteorder.h>
  12 #include <asm/atomic.h>
  13
  14 /*
  15  * The test_and_*_bit operations are taken to imply a memory barrier
  16  * on SMP systems.
  17  */
  18 #ifdef CONFIG_SMP
  19 #define SMP_WMB         "eieio\n"
  20 #define SMP_MB          "\nsync"
  21 #else
  22 #define SMP_WMB
  23 #define SMP_MB
  24 #endif /* CONFIG_SMP */
  25
  26 static __inline__ void set_bit(int nr, volatile unsigned long * addr)
  27 {
  28         unsigned long old;
  29         unsigned long mask = 1 << (nr & 0x1f);
  30         unsigned long *p = ((unsigned long *)addr) + (nr >> 5);
  31
  32         __asm__ __volatile__("\n\
  33 1:      lwarx   %0,0,%3 \n\
  34         or      %0,%0,%2 \n"
  35         PPC405_ERR77(0,%3)
  36 "       stwcx.  %0,0,%3 \n\
  37         bne-    1b"
  38         : "=&r" (old), "=m" (*p)
  39         : "r" (mask), "r" (p), "m" (*p)
  40         : "cc" );
  41 }
  42
  43 /*
  44  * non-atomic version
  45  */
  46 static __inline__ void __set_bit(int nr, volatile unsigned long *addr)
  47 {
  48         unsigned long mask = 1 << (nr & 0x1f);
  49         unsigned long *p = ((unsigned long *)addr) + (nr >> 5);
  50
  51         *p |= mask;
  52 }
  53
  54 /*
  55  * clear_bit doesn't imply a memory barrier
  56  */
  57 #define smp_mb__before_clear_bit()      smp_mb()
  58 #define smp_mb__after_clear_bit()       smp_mb()
  59
  60 static __inline__ void clear_bit(int nr, volatile unsigned long *addr)
  61 {
  62         unsigned long old;
  63         unsigned long mask = 1 << (nr & 0x1f);
  64         unsigned long *p = ((unsigned long *)addr) + (nr >> 5);
  65
  66         __asm__ __volatile__("\n\
  67 1:      lwarx   %0,0,%3 \n\
  68         andc    %0,%0,%2 \n"
  69         PPC405_ERR77(0,%3)
  70 "       stwcx.  %0,0,%3 \n\
  71         bne-    1b"
  72         : "=&r" (old), "=m" (*p)
  73         : "r" (mask), "r" (p), "m" (*p)
  74         : "cc");
  75 }
  76
  77 /*
  78  * non-atomic version
  79  */
  80 static __inline__ void __clear_bit(int nr, volatile unsigned long *addr)
  81 {
  82         unsigned long mask = 1 << (nr & 0x1f);
  83         unsigned long *p = ((unsigned long *)addr) + (nr >> 5);
  84
  85         *p &= ~mask;
  86 }
  87
  88 static __inline__ void change_bit(int nr, volatile unsigned long *addr)
  89 {
  90         unsigned long old;
  91         unsigned long mask = 1 << (nr & 0x1f);
  92         unsigned long *p = ((unsigned long *)addr) + (nr >> 5);
  93
  94         __asm__ __volatile__("\n\
  95 1:      lwarx   %0,0,%3 \n\
  96         xor     %0,%0,%2 \n"
  97         PPC405_ERR77(0,%3)
  98 "       stwcx.  %0,0,%3 \n\
  99         bne-    1b"
 100         : "=&r" (old), "=m" (*p)
 101         : "r" (mask), "r" (p), "m" (*p)
 102         : "cc");
 103 }
 104
 105 /*
 106  * non-atomic version
 107  */
 108 static __inline__ void __change_bit(int nr, volatile unsigned long *addr)
 109 {
 110         unsigned long mask = 1 << (nr & 0x1f);
 111         unsigned long *p = ((unsigned long *)addr) + (nr >> 5);
 112
 113         *p ^= mask;
 114 }
 115
 116 /*
 117  * test_and_*_bit do imply a memory barrier (?)
 118  */
 119 static __inline__ int test_and_set_bit(int nr, volatile unsigned long *addr)
 120 {
 121         unsigned int old, t;
 122         unsigned int mask = 1 << (nr & 0x1f);
 123         volatile unsigned int *p = ((volatile unsigned int *)addr) + (nr >> 5);
 124
 125         __asm__ __volatile__(SMP_WMB "\n\
 126 1:      lwarx   %0,0,%4 \n\
 127         or      %1,%0,%3 \n"
 128         PPC405_ERR77(0,%4)
 129 "       stwcx.  %1,0,%4 \n\
 130         bne     1b"
 131         SMP_MB
 132         : "=&r" (old), "=&r" (t), "=m" (*p)
 133         : "r" (mask), "r" (p), "m" (*p)
 134         : "cc", "memory");
 135
 136         return (old & mask) != 0;
 137 }
 138
 139 /*
 140  * non-atomic version
 141  */
 142 static __inline__ int __test_and_set_bit(int nr, volatile unsigned long *addr)
 143 {
 144         unsigned long mask = 1 << (nr & 0x1f);
 145         unsigned long *p = ((unsigned long *)addr) + (nr >> 5);
 146         unsigned long old = *p;
 147
 148         *p = old | mask;
 149         return (old & mask) != 0;
 150 }
 151
 152 static __inline__ int test_and_clear_bit(int nr, volatile unsigned long *addr)
 153 {
 154         unsigned int old, t;
 155         unsigned int mask = 1 << (nr & 0x1f);
 156         volatile unsigned int *p = ((volatile unsigned int *)addr) + (nr >> 5);
 157
 158         __asm__ __volatile__(SMP_WMB "\n\
 159 1:      lwarx   %0,0,%4 \n\
 160         andc    %1,%0,%3 \n"
 161         PPC405_ERR77(0,%4)
 162 "       stwcx.  %1,0,%4 \n\
 163         bne     1b"
 164         SMP_MB
 165         : "=&r" (old), "=&r" (t), "=m" (*p)
 166         : "r" (mask), "r" (p), "m" (*p)
 167         : "cc", "memory");
 168
 169         return (old & mask) != 0;
 170 }
 171
 172 /*
 173  * non-atomic version
 174  */
 175 static __inline__ int __test_and_clear_bit(int nr, volatile unsigned long *addr)
 176 {
 177         unsigned long mask = 1 << (nr & 0x1f);
 178         unsigned long *p = ((unsigned long *)addr) + (nr >> 5);
 179         unsigned long old = *p;
 180
 181         *p = old & ~mask;
 182         return (old & mask) != 0;
 183 }
 184
 185 static __inline__ int test_and_change_bit(int nr, volatile unsigned long *addr)
 186 {
 187         unsigned int old, t;
 188         unsigned int mask = 1 << (nr & 0x1f);
 189         volatile unsigned int *p = ((volatile unsigned int *)addr) + (nr >> 5);
 190
 191         __asm__ __volatile__(SMP_WMB "\n\
 192 1:      lwarx   %0,0,%4 \n\
 193         xor     %1,%0,%3 \n"
 194         PPC405_ERR77(0,%4)
 195 "       stwcx.  %1,0,%4 \n\
 196         bne     1b"
 197         SMP_MB
 198         : "=&r" (old), "=&r" (t), "=m" (*p)
 199         : "r" (mask), "r" (p), "m" (*p)
 200         : "cc", "memory");
 201
 202         return (old & mask) != 0;
 203 }
 204
 205 /*
 206  * non-atomic version
 207  */
 208 static __inline__ int __test_and_change_bit(int nr, volatile unsigned long *addr)
 209 {
 210         unsigned long mask = 1 << (nr & 0x1f);
 211         unsigned long *p = ((unsigned long *)addr) + (nr >> 5);
 212         unsigned long old = *p;
 213
 214         *p = old ^ mask;
 215         return (old & mask) != 0;
 216 }
 217
 218 static __inline__ int test_bit(int nr, __const__ volatile unsigned long *addr)
 219 {
 220         return ((addr[nr >> 5] >> (nr & 0x1f)) & 1) != 0;
 221 }
 222
 223 /* Return the bit position of the most significant 1 bit in a word */
 224 static __inline__ int __ilog2(unsigned long x)
 225 {
 226         int lz;
 227
 228         asm ("cntlzw %0,%1" : "=r" (lz) : "r" (x));
 229         return 31 - lz;
 230 }
 231
 232 static __inline__ int ffz(unsigned long x)
 233 {
 234         if ((x = ~x) == 0)
 235                 return 32;
 236         return __ilog2(x & -x);
 237 }
 238
 239 static inline int __ffs(unsigned long x)
 240 {
 241         return __ilog2(x & -x);
 242 }
 243
 244 /*
 245  * ffs: find first bit set. This is defined the same way as
 246  * the libc and compiler builtin ffs routines, therefore
 247  * differs in spirit from the above ffz (man ffs).
 248  */
 249 static __inline__ int ffs(int x)
 250 {
 251         return __ilog2(x & -x) + 1;
 252 }
 253
 254 /*
 255  * fls: find last (most-significant) bit set.
 256  * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.
 257  */
 258 static __inline__ int fls(unsigned int x)
 259 {
 260         int lz;
 261
 262         asm ("cntlzw %0,%1" : "=r" (lz) : "r" (x));
 263         return 32 - lz;
 264 }
 265
 266 /*
 267  * hweightN: returns the hamming weight (i.e. the number
 268  * of bits set) of a N-bit word
 269  */
 270
 271 #define hweight32(x) generic_hweight32(x)
 272 #define hweight16(x) generic_hweight16(x)
 273 #define hweight8(x) generic_hweight8(x)
 274
 275 /*
 276  * Find the first bit set in a 140-bit bitmap.
 277  * The first 100 bits are unlikely to be set.
 278  */
 279 static inline int sched_find_first_bit(const unsigned long *b)
 280 {
 281         if (unlikely(b[0]))
 282                 return __ffs(b[0]);
 283         if (unlikely(b[1]))
 284                 return __ffs(b[1]) + 32;
 285         if (unlikely(b[2]))
 286                 return __ffs(b[2]) + 64;
 287         if (b[3])
 288                 return __ffs(b[3]) + 96;
 289         return __ffs(b[4]) + 128;
 290 }
 291
 292 /**
 293  * find_next_bit - find the next set bit in a memory region
 294  * @addr: The address to base the search on
 295  * @offset: The bitnumber to start searching at
 296  * @size: The maximum size to search
 297  */
 298 static __inline__ unsigned long find_next_bit(const unsigned long *addr,
 299         unsigned long size, unsigned long offset)
 300 {
 301         unsigned int *p = ((unsigned int *) addr) + (offset >> 5);
 302         unsigned int result = offset & ~31UL;
 303         unsigned int tmp;
 304
 305         if (offset >= size)
 306                 return size;
 307         size -= result;
 308         offset &= 31UL;
 309         if (offset) {
 310                 tmp = *p++;
 311                 tmp &= ~0UL << offset;
 312                 if (size < 32)
 313                         goto found_first;
 314                 if (tmp)
 315                         goto found_middle;
 316                 size -= 32;
 317                 result += 32;
 318         }
 319         while (size >= 32) {
 320                 if ((tmp = *p++) != 0)
 321                         goto found_middle;
 322                 result += 32;
 323                 size -= 32;
 324         }
 325         if (!size)
 326                 return result;
 327         tmp = *p;
 328
 329 found_first:
 330         tmp &= ~0UL >> (32 - size);
 331         if (tmp == 0UL)        /* Are any bits set? */
 332                 return result + size; /* Nope. */
 333 found_middle:
 334         return result + __ffs(tmp);
 335 }
 336
 337 /**
 338  * find_first_bit - find the first set bit in a memory region
 339  * @addr: The address to start the search at
 340  * @size: The maximum size to search
 341  *
 342  * Returns the bit-number of the first set bit, not the number of the byte
 343  * containing a bit.
 344  */
 345 #define find_first_bit(addr, size) \
 346         find_next_bit((addr), (size), 0)
 347
 348 /*
 349  * This implementation of find_{first,next}_zero_bit was stolen from
 350  * Linus' asm-alpha/bitops.h.
 351  */
 352 #define find_first_zero_bit(addr, size) \
 353         find_next_zero_bit((addr), (size), 0)
 354
 355 static __inline__ unsigned long find_next_zero_bit(const unsigned long *addr,
 356         unsigned long size, unsigned long offset)
 357 {
 358         unsigned int * p = ((unsigned int *) addr) + (offset >> 5);
 359         unsigned int result = offset & ~31UL;
 360         unsigned int tmp;
 361
 362         if (offset >= size)
 363                 return size;
 364         size -= result;
 365         offset &= 31UL;
 366         if (offset) {
 367                 tmp = *p++;
 368                 tmp |= ~0UL >> (32-offset);
 369                 if (size < 32)
 370                         goto found_first;
 371                 if (tmp != ~0U)
 372                         goto found_middle;
 373                 size -= 32;
 374                 result += 32;
 375         }
 376         while (size >= 32) {
 377                 if ((tmp = *p++) != ~0U)
 378                         goto found_middle;
 379                 result += 32;
 380                 size -= 32;
 381         }
 382         if (!size)
 383                 return result;
 384         tmp = *p;
 385 found_first:
 386         tmp |= ~0UL << size;
 387         if (tmp == ~0UL)        /* Are any bits zero? */
 388                 return result + size; /* Nope. */
 389 found_middle:
 390         return result + ffz(tmp);
 391 }
 392
 393
 394 #define ext2_set_bit(nr, addr)  __test_and_set_bit((nr) ^ 0x18, (unsigned long *)(addr))
 395 #define ext2_set_bit_atomic(lock, nr, addr)  test_and_set_bit((nr) ^ 0x18, (unsigned long *)(addr))
 396 #define ext2_clear_bit(nr, addr) __test_and_clear_bit((nr) ^ 0x18, (unsigned long *)(addr))
 397 #define ext2_clear_bit_atomic(lock, nr, addr) test_and_clear_bit((nr) ^ 0x18, (unsigned long *)(addr))
 398
 399 static __inline__ int ext2_test_bit(int nr, __const__ void * addr)
 400 {
 401         __const__ unsigned char *ADDR = (__const__ unsigned char *) addr;
 402
 403         return (ADDR[nr >> 3] >> (nr & 7)) & 1;
 404 }
 405
 406 /*
 407  * This implementation of ext2_find_{first,next}_zero_bit was stolen from
 408  * Linus' asm-alpha/bitops.h and modified for a big-endian machine.
 409  */
 410
 411 #define ext2_find_first_zero_bit(addr, size) \
 412         ext2_find_next_zero_bit((addr), (size), 0)
 413
 414 static __inline__ unsigned long ext2_find_next_zero_bit(const void *addr,
 415         unsigned long size, unsigned long offset)
 416 {
 417         unsigned int *p = ((unsigned int *) addr) + (offset >> 5);
 418         unsigned int result = offset & ~31UL;
 419         unsigned int tmp;
 420
 421         if (offset >= size)
 422                 return size;
 423         size -= result;
 424         offset &= 31UL;
 425         if (offset) {
 426                 tmp = cpu_to_le32p(p++);
 427                 tmp |= ~0UL >> (32-offset);
 428                 if (size < 32)
 429                         goto found_first;
 430                 if (tmp != ~0U)
 431                         goto found_middle;
 432                 size -= 32;
 433                 result += 32;
 434         }
 435         while (size >= 32) {
 436                 if ((tmp = cpu_to_le32p(p++)) != ~0U)
 437                         goto found_middle;
 438                 result += 32;
 439                 size -= 32;
 440         }
 441         if (!size)
 442                 return result;
 443         tmp = cpu_to_le32p(p);
 444 found_first:
 445         tmp |= ~0U << size;
 446         if (tmp == ~0UL)        /* Are any bits zero? */
 447                 return result + size; /* Nope. */
 448 found_middle:
 449         return result + ffz(tmp);
 450 }
 451
 452 /* Bitmap functions for the minix filesystem.  */
 453 #define minix_test_and_set_bit(nr,addr) ext2_set_bit(nr,addr)
 454 #define minix_set_bit(nr,addr) ((void)ext2_set_bit(nr,addr))
 455 #define minix_test_and_clear_bit(nr,addr) ext2_clear_bit(nr,addr)
 456 #define minix_test_bit(nr,addr) ext2_test_bit(nr,addr)
 457 #define minix_find_first_zero_bit(addr,size) ext2_find_first_zero_bit(addr,size)
 458
 459 #endif /* _PPC_BITOPS_H */
 460 #endif /* __KERNEL__ */