1 /* 2 * S390 version 3 * Copyright IBM Corp. 1999 4 * Author(s): Martin Schwidefsky (schwidefsky@de.ibm.com) 5 * 6 * Derived from "include/asm-i386/bitops.h" 7 * Copyright (C) 1992, Linus Torvalds 8 * 9 */ 10 11 #ifndef _S390_BITOPS_H 12 #define _S390_BITOPS_H 13 14 #ifndef _LINUX_BITOPS_H 15 #error only <linux/bitops.h> can be included directly 16 #endif 17 18 #include <linux/compiler.h> 19 20 /* 21 * 32 bit bitops format: 22 * bit 0 is the LSB of *addr; bit 31 is the MSB of *addr; 23 * bit 32 is the LSB of *(addr+4). That combined with the 24 * big endian byte order on S390 give the following bit 25 * order in memory: 26 * 1f 1e 1d 1c 1b 1a 19 18 17 16 15 14 13 12 11 10 \ 27 * 0f 0e 0d 0c 0b 0a 09 08 07 06 05 04 03 02 01 00 28 * after that follows the next long with bit numbers 29 * 3f 3e 3d 3c 3b 3a 39 38 37 36 35 34 33 32 31 30 30 * 2f 2e 2d 2c 2b 2a 29 28 27 26 25 24 23 22 21 20 31 * The reason for this bit ordering is the fact that 32 * in the architecture independent code bits operations 33 * of the form "flags |= (1 << bitnr)" are used INTERMIXED 34 * with operation of the form "set_bit(bitnr, flags)". 35 * 36 * 64 bit bitops format: 37 * bit 0 is the LSB of *addr; bit 63 is the MSB of *addr; 38 * bit 64 is the LSB of *(addr+8). That combined with the 39 * big endian byte order on S390 give the following bit 40 * order in memory: 41 * 3f 3e 3d 3c 3b 3a 39 38 37 36 35 34 33 32 31 30 42 * 2f 2e 2d 2c 2b 2a 29 28 27 26 25 24 23 22 21 20 43 * 1f 1e 1d 1c 1b 1a 19 18 17 16 15 14 13 12 11 10 44 * 0f 0e 0d 0c 0b 0a 09 08 07 06 05 04 03 02 01 00 45 * after that follows the next long with bit numbers 46 * 7f 7e 7d 7c 7b 7a 79 78 77 76 75 74 73 72 71 70 47 * 6f 6e 6d 6c 6b 6a 69 68 67 66 65 64 63 62 61 60 48 * 5f 5e 5d 5c 5b 5a 59 58 57 56 55 54 53 52 51 50 49 * 4f 4e 4d 4c 4b 4a 49 48 47 46 45 44 43 42 41 40 50 * The reason for this bit ordering is the fact that 51 * in the architecture independent code bits operations 52 * of the form "flags |= (1 << bitnr)" are used INTERMIXED 53 * with operation of the form "set_bit(bitnr, flags)". 54 */ 55 56 /* bitmap tables from arch/s390/kernel/bitmap.c */ 57 extern const char _oi_bitmap[]; 58 extern const char _ni_bitmap[]; 59 extern const char _zb_findmap[]; 60 extern const char _sb_findmap[]; 61 62 #ifndef CONFIG_64BIT 63 64 #define __BITOPS_OR "or" 65 #define __BITOPS_AND "nr" 66 #define __BITOPS_XOR "xr" 67 68 #define __BITOPS_LOOP(__old, __new, __addr, __val, __op_string) \ 69 asm volatile( \ 70 " l %0,%2\n" \ 71 "0: lr %1,%0\n" \ 72 __op_string " %1,%3\n" \ 73 " cs %0,%1,%2\n" \ 74 " jl 0b" \ 75 : "=&d" (__old), "=&d" (__new), \ 76 "=Q" (*(unsigned long *) __addr) \ 77 : "d" (__val), "Q" (*(unsigned long *) __addr) \ 78 : "cc"); 79 80 #else /* CONFIG_64BIT */ 81 82 #define __BITOPS_OR "ogr" 83 #define __BITOPS_AND "ngr" 84 #define __BITOPS_XOR "xgr" 85 86 #define __BITOPS_LOOP(__old, __new, __addr, __val, __op_string) \ 87 asm volatile( \ 88 " lg %0,%2\n" \ 89 "0: lgr %1,%0\n" \ 90 __op_string " %1,%3\n" \ 91 " csg %0,%1,%2\n" \ 92 " jl 0b" \ 93 : "=&d" (__old), "=&d" (__new), \ 94 "=Q" (*(unsigned long *) __addr) \ 95 : "d" (__val), "Q" (*(unsigned long *) __addr) \ 96 : "cc"); 97 98 #endif /* CONFIG_64BIT */ 99 100 #define __BITOPS_WORDS(bits) (((bits) + BITS_PER_LONG - 1) / BITS_PER_LONG) 101 102 #ifdef CONFIG_SMP 103 /* 104 * SMP safe set_bit routine based on compare and swap (CS) 105 */ 106 static inline void set_bit_cs(unsigned long nr, volatile unsigned long *ptr) 107 { 108 unsigned long addr, old, new, mask; 109 110 addr = (unsigned long) ptr; 111 /* calculate address for CS */ 112 addr += (nr ^ (nr & (BITS_PER_LONG - 1))) >> 3; 113 /* make OR mask */ 114 mask = 1UL << (nr & (BITS_PER_LONG - 1)); 115 /* Do the atomic update. */ 116 __BITOPS_LOOP(old, new, addr, mask, __BITOPS_OR); 117 } 118 119 /* 120 * SMP safe clear_bit routine based on compare and swap (CS) 121 */ 122 static inline void clear_bit_cs(unsigned long nr, volatile unsigned long *ptr) 123 { 124 unsigned long addr, old, new, mask; 125 126 addr = (unsigned long) ptr; 127 /* calculate address for CS */ 128 addr += (nr ^ (nr & (BITS_PER_LONG - 1))) >> 3; 129 /* make AND mask */ 130 mask = ~(1UL << (nr & (BITS_PER_LONG - 1))); 131 /* Do the atomic update. */ 132 __BITOPS_LOOP(old, new, addr, mask, __BITOPS_AND); 133 } 134 135 /* 136 * SMP safe change_bit routine based on compare and swap (CS) 137 */ 138 static inline void change_bit_cs(unsigned long nr, volatile unsigned long *ptr) 139 { 140 unsigned long addr, old, new, mask; 141 142 addr = (unsigned long) ptr; 143 /* calculate address for CS */ 144 addr += (nr ^ (nr & (BITS_PER_LONG - 1))) >> 3; 145 /* make XOR mask */ 146 mask = 1UL << (nr & (BITS_PER_LONG - 1)); 147 /* Do the atomic update. */ 148 __BITOPS_LOOP(old, new, addr, mask, __BITOPS_XOR); 149 } 150 151 /* 152 * SMP safe test_and_set_bit routine based on compare and swap (CS) 153 */ 154 static inline int 155 test_and_set_bit_cs(unsigned long nr, volatile unsigned long *ptr) 156 { 157 unsigned long addr, old, new, mask; 158 159 addr = (unsigned long) ptr; 160 /* calculate address for CS */ 161 addr += (nr ^ (nr & (BITS_PER_LONG - 1))) >> 3; 162 /* make OR/test mask */ 163 mask = 1UL << (nr & (BITS_PER_LONG - 1)); 164 /* Do the atomic update. */ 165 __BITOPS_LOOP(old, new, addr, mask, __BITOPS_OR); 166 barrier(); 167 return (old & mask) != 0; 168 } 169 170 /* 171 * SMP safe test_and_clear_bit routine based on compare and swap (CS) 172 */ 173 static inline int 174 test_and_clear_bit_cs(unsigned long nr, volatile unsigned long *ptr) 175 { 176 unsigned long addr, old, new, mask; 177 178 addr = (unsigned long) ptr; 179 /* calculate address for CS */ 180 addr += (nr ^ (nr & (BITS_PER_LONG - 1))) >> 3; 181 /* make AND/test mask */ 182 mask = ~(1UL << (nr & (BITS_PER_LONG - 1))); 183 /* Do the atomic update. */ 184 __BITOPS_LOOP(old, new, addr, mask, __BITOPS_AND); 185 barrier(); 186 return (old ^ new) != 0; 187 } 188 189 /* 190 * SMP safe test_and_change_bit routine based on compare and swap (CS) 191 */ 192 static inline int 193 test_and_change_bit_cs(unsigned long nr, volatile unsigned long *ptr) 194 { 195 unsigned long addr, old, new, mask; 196 197 addr = (unsigned long) ptr; 198 /* calculate address for CS */ 199 addr += (nr ^ (nr & (BITS_PER_LONG - 1))) >> 3; 200 /* make XOR/test mask */ 201 mask = 1UL << (nr & (BITS_PER_LONG - 1)); 202 /* Do the atomic update. */ 203 __BITOPS_LOOP(old, new, addr, mask, __BITOPS_XOR); 204 barrier(); 205 return (old & mask) != 0; 206 } 207 #endif /* CONFIG_SMP */ 208 209 /* 210 * fast, non-SMP set_bit routine 211 */ 212 static inline void __set_bit(unsigned long nr, volatile unsigned long *ptr) 213 { 214 unsigned long addr; 215 216 addr = (unsigned long) ptr + ((nr ^ (BITS_PER_LONG - 8)) >> 3); 217 asm volatile( 218 " oc %O0(1,%R0),%1" 219 : "+Q" (*(char *) addr) : "Q" (_oi_bitmap[nr & 7]) : "cc"); 220 } 221 222 static inline void 223 __constant_set_bit(const unsigned long nr, volatile unsigned long *ptr) 224 { 225 unsigned long addr; 226 227 addr = ((unsigned long) ptr) + ((nr ^ (BITS_PER_LONG - 8)) >> 3); 228 *(unsigned char *) addr |= 1 << (nr & 7); 229 } 230 231 #define set_bit_simple(nr,addr) \ 232 (__builtin_constant_p((nr)) ? \ 233 __constant_set_bit((nr),(addr)) : \ 234 __set_bit((nr),(addr)) ) 235 236 /* 237 * fast, non-SMP clear_bit routine 238 */ 239 static inline void 240 __clear_bit(unsigned long nr, volatile unsigned long *ptr) 241 { 242 unsigned long addr; 243 244 addr = (unsigned long) ptr + ((nr ^ (BITS_PER_LONG - 8)) >> 3); 245 asm volatile( 246 " nc %O0(1,%R0),%1" 247 : "+Q" (*(char *) addr) : "Q" (_ni_bitmap[nr & 7]) : "cc"); 248 } 249 250 static inline void 251 __constant_clear_bit(const unsigned long nr, volatile unsigned long *ptr) 252 { 253 unsigned long addr; 254 255 addr = ((unsigned long) ptr) + ((nr ^ (BITS_PER_LONG - 8)) >> 3); 256 *(unsigned char *) addr &= ~(1 << (nr & 7)); 257 } 258 259 #define clear_bit_simple(nr,addr) \ 260 (__builtin_constant_p((nr)) ? \ 261 __constant_clear_bit((nr),(addr)) : \ 262 __clear_bit((nr),(addr)) ) 263 264 /* 265 * fast, non-SMP change_bit routine 266 */ 267 static inline void __change_bit(unsigned long nr, volatile unsigned long *ptr) 268 { 269 unsigned long addr; 270 271 addr = (unsigned long) ptr + ((nr ^ (BITS_PER_LONG - 8)) >> 3); 272 asm volatile( 273 " xc %O0(1,%R0),%1" 274 : "+Q" (*(char *) addr) : "Q" (_oi_bitmap[nr & 7]) : "cc"); 275 } 276 277 static inline void 278 __constant_change_bit(const unsigned long nr, volatile unsigned long *ptr) 279 { 280 unsigned long addr; 281 282 addr = ((unsigned long) ptr) + ((nr ^ (BITS_PER_LONG - 8)) >> 3); 283 *(unsigned char *) addr ^= 1 << (nr & 7); 284 } 285 286 #define change_bit_simple(nr,addr) \ 287 (__builtin_constant_p((nr)) ? \ 288 __constant_change_bit((nr),(addr)) : \ 289 __change_bit((nr),(addr)) ) 290 291 /* 292 * fast, non-SMP test_and_set_bit routine 293 */ 294 static inline int 295 test_and_set_bit_simple(unsigned long nr, volatile unsigned long *ptr) 296 { 297 unsigned long addr; 298 unsigned char ch; 299 300 addr = (unsigned long) ptr + ((nr ^ (BITS_PER_LONG - 8)) >> 3); 301 ch = *(unsigned char *) addr; 302 asm volatile( 303 " oc %O0(1,%R0),%1" 304 : "+Q" (*(char *) addr) : "Q" (_oi_bitmap[nr & 7]) 305 : "cc", "memory"); 306 return (ch >> (nr & 7)) & 1; 307 } 308 #define __test_and_set_bit(X,Y) test_and_set_bit_simple(X,Y) 309 310 /* 311 * fast, non-SMP test_and_clear_bit routine 312 */ 313 static inline int 314 test_and_clear_bit_simple(unsigned long nr, volatile unsigned long *ptr) 315 { 316 unsigned long addr; 317 unsigned char ch; 318 319 addr = (unsigned long) ptr + ((nr ^ (BITS_PER_LONG - 8)) >> 3); 320 ch = *(unsigned char *) addr; 321 asm volatile( 322 " nc %O0(1,%R0),%1" 323 : "+Q" (*(char *) addr) : "Q" (_ni_bitmap[nr & 7]) 324 : "cc", "memory"); 325 return (ch >> (nr & 7)) & 1; 326 } 327 #define __test_and_clear_bit(X,Y) test_and_clear_bit_simple(X,Y) 328 329 /* 330 * fast, non-SMP test_and_change_bit routine 331 */ 332 static inline int 333 test_and_change_bit_simple(unsigned long nr, volatile unsigned long *ptr) 334 { 335 unsigned long addr; 336 unsigned char ch; 337 338 addr = (unsigned long) ptr + ((nr ^ (BITS_PER_LONG - 8)) >> 3); 339 ch = *(unsigned char *) addr; 340 asm volatile( 341 " xc %O0(1,%R0),%1" 342 : "+Q" (*(char *) addr) : "Q" (_oi_bitmap[nr & 7]) 343 : "cc", "memory"); 344 return (ch >> (nr & 7)) & 1; 345 } 346 #define __test_and_change_bit(X,Y) test_and_change_bit_simple(X,Y) 347 348 #ifdef CONFIG_SMP 349 #define set_bit set_bit_cs 350 #define clear_bit clear_bit_cs 351 #define change_bit change_bit_cs 352 #define test_and_set_bit test_and_set_bit_cs 353 #define test_and_clear_bit test_and_clear_bit_cs 354 #define test_and_change_bit test_and_change_bit_cs 355 #else 356 #define set_bit set_bit_simple 357 #define clear_bit clear_bit_simple 358 #define change_bit change_bit_simple 359 #define test_and_set_bit test_and_set_bit_simple 360 #define test_and_clear_bit test_and_clear_bit_simple 361 #define test_and_change_bit test_and_change_bit_simple 362 #endif 363 364 365 /* 366 * This routine doesn't need to be atomic. 367 */ 368 369 static inline int __test_bit(unsigned long nr, const volatile unsigned long *ptr) 370 { 371 unsigned long addr; 372 unsigned char ch; 373 374 addr = (unsigned long) ptr + ((nr ^ (BITS_PER_LONG - 8)) >> 3); 375 ch = *(volatile unsigned char *) addr; 376 return (ch >> (nr & 7)) & 1; 377 } 378 379 static inline int 380 __constant_test_bit(unsigned long nr, const volatile unsigned long *addr) { 381 return (((volatile char *) addr) 382 [(nr^(BITS_PER_LONG-8))>>3] & (1<<(nr&7))) != 0; 383 } 384 385 #define test_bit(nr,addr) \ 386 (__builtin_constant_p((nr)) ? \ 387 __constant_test_bit((nr),(addr)) : \ 388 __test_bit((nr),(addr)) ) 389 390 /* 391 * Optimized find bit helper functions. 392 */ 393 394 /** 395 * __ffz_word_loop - find byte offset of first long != -1UL 396 * @addr: pointer to array of unsigned long 397 * @size: size of the array in bits 398 */ 399 static inline unsigned long __ffz_word_loop(const unsigned long *addr, 400 unsigned long size) 401 { 402 typedef struct { long _[__BITOPS_WORDS(size)]; } addrtype; 403 unsigned long bytes = 0; 404 405 asm volatile( 406 #ifndef CONFIG_64BIT 407 " ahi %1,-1\n" 408 " sra %1,5\n" 409 " jz 1f\n" 410 "0: c %2,0(%0,%3)\n" 411 " jne 1f\n" 412 " la %0,4(%0)\n" 413 " brct %1,0b\n" 414 "1:\n" 415 #else 416 " aghi %1,-1\n" 417 " srag %1,%1,6\n" 418 " jz 1f\n" 419 "0: cg %2,0(%0,%3)\n" 420 " jne 1f\n" 421 " la %0,8(%0)\n" 422 " brct %1,0b\n" 423 "1:\n" 424 #endif 425 : "+&a" (bytes), "+&d" (size) 426 : "d" (-1UL), "a" (addr), "m" (*(addrtype *) addr) 427 : "cc" ); 428 return bytes; 429 } 430 431 /** 432 * __ffs_word_loop - find byte offset of first long != 0UL 433 * @addr: pointer to array of unsigned long 434 * @size: size of the array in bits 435 */ 436 static inline unsigned long __ffs_word_loop(const unsigned long *addr, 437 unsigned long size) 438 { 439 typedef struct { long _[__BITOPS_WORDS(size)]; } addrtype; 440 unsigned long bytes = 0; 441 442 asm volatile( 443 #ifndef CONFIG_64BIT 444 " ahi %1,-1\n" 445 " sra %1,5\n" 446 " jz 1f\n" 447 "0: c %2,0(%0,%3)\n" 448 " jne 1f\n" 449 " la %0,4(%0)\n" 450 " brct %1,0b\n" 451 "1:\n" 452 #else 453 " aghi %1,-1\n" 454 " srag %1,%1,6\n" 455 " jz 1f\n" 456 "0: cg %2,0(%0,%3)\n" 457 " jne 1f\n" 458 " la %0,8(%0)\n" 459 " brct %1,0b\n" 460 "1:\n" 461 #endif 462 : "+&a" (bytes), "+&a" (size) 463 : "d" (0UL), "a" (addr), "m" (*(addrtype *) addr) 464 : "cc" ); 465 return bytes; 466 } 467 468 /** 469 * __ffz_word - add number of the first unset bit 470 * @nr: base value the bit number is added to 471 * @word: the word that is searched for unset bits 472 */ 473 static inline unsigned long __ffz_word(unsigned long nr, unsigned long word) 474 { 475 #ifdef CONFIG_64BIT 476 if ((word & 0xffffffff) == 0xffffffff) { 477 word >>= 32; 478 nr += 32; 479 } 480 #endif 481 if ((word & 0xffff) == 0xffff) { 482 word >>= 16; 483 nr += 16; 484 } 485 if ((word & 0xff) == 0xff) { 486 word >>= 8; 487 nr += 8; 488 } 489 return nr + _zb_findmap[(unsigned char) word]; 490 } 491 492 /** 493 * __ffs_word - add number of the first set bit 494 * @nr: base value the bit number is added to 495 * @word: the word that is searched for set bits 496 */ 497 static inline unsigned long __ffs_word(unsigned long nr, unsigned long word) 498 { 499 #ifdef CONFIG_64BIT 500 if ((word & 0xffffffff) == 0) { 501 word >>= 32; 502 nr += 32; 503 } 504 #endif 505 if ((word & 0xffff) == 0) { 506 word >>= 16; 507 nr += 16; 508 } 509 if ((word & 0xff) == 0) { 510 word >>= 8; 511 nr += 8; 512 } 513 return nr + _sb_findmap[(unsigned char) word]; 514 } 515 516 517 /** 518 * __load_ulong_be - load big endian unsigned long 519 * @p: pointer to array of unsigned long 520 * @offset: byte offset of source value in the array 521 */ 522 static inline unsigned long __load_ulong_be(const unsigned long *p, 523 unsigned long offset) 524 { 525 p = (unsigned long *)((unsigned long) p + offset); 526 return *p; 527 } 528 529 /** 530 * __load_ulong_le - load little endian unsigned long 531 * @p: pointer to array of unsigned long 532 * @offset: byte offset of source value in the array 533 */ 534 static inline unsigned long __load_ulong_le(const unsigned long *p, 535 unsigned long offset) 536 { 537 unsigned long word; 538 539 p = (unsigned long *)((unsigned long) p + offset); 540 #ifndef CONFIG_64BIT 541 asm volatile( 542 " ic %0,%O1(%R1)\n" 543 " icm %0,2,%O1+1(%R1)\n" 544 " icm %0,4,%O1+2(%R1)\n" 545 " icm %0,8,%O1+3(%R1)" 546 : "=&d" (word) : "Q" (*p) : "cc"); 547 #else 548 asm volatile( 549 " lrvg %0,%1" 550 : "=d" (word) : "m" (*p) ); 551 #endif 552 return word; 553 } 554 555 /* 556 * The various find bit functions. 557 */ 558 559 /* 560 * ffz - find first zero in word. 561 * @word: The word to search 562 * 563 * Undefined if no zero exists, so code should check against ~0UL first. 564 */ 565 static inline unsigned long ffz(unsigned long word) 566 { 567 return __ffz_word(0, word); 568 } 569 570 /** 571 * __ffs - find first bit in word. 572 * @word: The word to search 573 * 574 * Undefined if no bit exists, so code should check against 0 first. 575 */ 576 static inline unsigned long __ffs (unsigned long word) 577 { 578 return __ffs_word(0, word); 579 } 580 581 /** 582 * ffs - find first bit set 583 * @x: the word to search 584 * 585 * This is defined the same way as 586 * the libc and compiler builtin ffs routines, therefore 587 * differs in spirit from the above ffz (man ffs). 588 */ 589 static inline int ffs(int x) 590 { 591 if (!x) 592 return 0; 593 return __ffs_word(1, x); 594 } 595 596 /** 597 * find_first_zero_bit - find the first zero bit in a memory region 598 * @addr: The address to start the search at 599 * @size: The maximum size to search 600 * 601 * Returns the bit-number of the first zero bit, not the number of the byte 602 * containing a bit. 603 */ 604 static inline unsigned long find_first_zero_bit(const unsigned long *addr, 605 unsigned long size) 606 { 607 unsigned long bytes, bits; 608 609 if (!size) 610 return 0; 611 bytes = __ffz_word_loop(addr, size); 612 bits = __ffz_word(bytes*8, __load_ulong_be(addr, bytes)); 613 return (bits < size) ? bits : size; 614 } 615 #define find_first_zero_bit find_first_zero_bit 616 617 /** 618 * find_first_bit - find the first set bit in a memory region 619 * @addr: The address to start the search at 620 * @size: The maximum size to search 621 * 622 * Returns the bit-number of the first set bit, not the number of the byte 623 * containing a bit. 624 */ 625 static inline unsigned long find_first_bit(const unsigned long * addr, 626 unsigned long size) 627 { 628 unsigned long bytes, bits; 629 630 if (!size) 631 return 0; 632 bytes = __ffs_word_loop(addr, size); 633 bits = __ffs_word(bytes*8, __load_ulong_be(addr, bytes)); 634 return (bits < size) ? bits : size; 635 } 636 #define find_first_bit find_first_bit 637 638 /* 639 * Big endian variant whichs starts bit counting from left using 640 * the flogr (find leftmost one) instruction. 641 */ 642 static inline unsigned long __flo_word(unsigned long nr, unsigned long val) 643 { 644 register unsigned long bit asm("2") = val; 645 register unsigned long out asm("3"); 646 647 asm volatile ( 648 " .insn rre,0xb9830000,%[bit],%[bit]\n" 649 : [bit] "+d" (bit), [out] "=d" (out) : : "cc"); 650 return nr + bit; 651 } 652 653 /* 654 * 64 bit special left bitops format: 655 * order in memory: 656 * 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 657 * 10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f 658 * 20 21 22 23 24 25 26 27 28 29 2a 2b 2c 2d 2e 2f 659 * 30 31 32 33 34 35 36 37 38 39 3a 3b 3c 3d 3e 3f 660 * after that follows the next long with bit numbers 661 * 40 41 42 43 44 45 46 47 48 49 4a 4b 4c 4d 4e 4f 662 * 50 51 52 53 54 55 56 57 58 59 5a 5b 5c 5d 5e 5f 663 * 60 61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f 664 * 70 71 72 73 74 75 76 77 78 79 7a 7b 7c 7d 7e 7f 665 * The reason for this bit ordering is the fact that 666 * the hardware sets bits in a bitmap starting at bit 0 667 * and we don't want to scan the bitmap from the 'wrong 668 * end'. 669 */ 670 static inline unsigned long find_first_bit_left(const unsigned long *addr, 671 unsigned long size) 672 { 673 unsigned long bytes, bits; 674 675 if (!size) 676 return 0; 677 bytes = __ffs_word_loop(addr, size); 678 bits = __flo_word(bytes * 8, __load_ulong_be(addr, bytes)); 679 return (bits < size) ? bits : size; 680 } 681 682 static inline int find_next_bit_left(const unsigned long *addr, 683 unsigned long size, 684 unsigned long offset) 685 { 686 const unsigned long *p; 687 unsigned long bit, set; 688 689 if (offset >= size) 690 return size; 691 bit = offset & (BITS_PER_LONG - 1); 692 offset -= bit; 693 size -= offset; 694 p = addr + offset / BITS_PER_LONG; 695 if (bit) { 696 set = __flo_word(0, *p & (~0UL >> bit)); 697 if (set >= size) 698 return size + offset; 699 if (set < BITS_PER_LONG) 700 return set + offset; 701 offset += BITS_PER_LONG; 702 size -= BITS_PER_LONG; 703 p++; 704 } 705 return offset + find_first_bit_left(p, size); 706 } 707 708 #define for_each_set_bit_left(bit, addr, size) \ 709 for ((bit) = find_first_bit_left((addr), (size)); \ 710 (bit) < (size); \ 711 (bit) = find_next_bit_left((addr), (size), (bit) + 1)) 712 713 /* same as for_each_set_bit() but use bit as value to start with */ 714 #define for_each_set_bit_left_cont(bit, addr, size) \ 715 for ((bit) = find_next_bit_left((addr), (size), (bit)); \ 716 (bit) < (size); \ 717 (bit) = find_next_bit_left((addr), (size), (bit) + 1)) 718 719 /** 720 * find_next_zero_bit - find the first zero bit in a memory region 721 * @addr: The address to base the search on 722 * @offset: The bitnumber to start searching at 723 * @size: The maximum size to search 724 */ 725 static inline int find_next_zero_bit (const unsigned long * addr, 726 unsigned long size, 727 unsigned long offset) 728 { 729 const unsigned long *p; 730 unsigned long bit, set; 731 732 if (offset >= size) 733 return size; 734 bit = offset & (BITS_PER_LONG - 1); 735 offset -= bit; 736 size -= offset; 737 p = addr + offset / BITS_PER_LONG; 738 if (bit) { 739 /* 740 * __ffz_word returns BITS_PER_LONG 741 * if no zero bit is present in the word. 742 */ 743 set = __ffz_word(bit, *p >> bit); 744 if (set >= size) 745 return size + offset; 746 if (set < BITS_PER_LONG) 747 return set + offset; 748 offset += BITS_PER_LONG; 749 size -= BITS_PER_LONG; 750 p++; 751 } 752 return offset + find_first_zero_bit(p, size); 753 } 754 #define find_next_zero_bit find_next_zero_bit 755 756 /** 757 * find_next_bit - find the first set bit in a memory region 758 * @addr: The address to base the search on 759 * @offset: The bitnumber to start searching at 760 * @size: The maximum size to search 761 */ 762 static inline int find_next_bit (const unsigned long * addr, 763 unsigned long size, 764 unsigned long offset) 765 { 766 const unsigned long *p; 767 unsigned long bit, set; 768 769 if (offset >= size) 770 return size; 771 bit = offset & (BITS_PER_LONG - 1); 772 offset -= bit; 773 size -= offset; 774 p = addr + offset / BITS_PER_LONG; 775 if (bit) { 776 /* 777 * __ffs_word returns BITS_PER_LONG 778 * if no one bit is present in the word. 779 */ 780 set = __ffs_word(0, *p & (~0UL << bit)); 781 if (set >= size) 782 return size + offset; 783 if (set < BITS_PER_LONG) 784 return set + offset; 785 offset += BITS_PER_LONG; 786 size -= BITS_PER_LONG; 787 p++; 788 } 789 return offset + find_first_bit(p, size); 790 } 791 #define find_next_bit find_next_bit 792 793 /* 794 * Every architecture must define this function. It's the fastest 795 * way of searching a 140-bit bitmap where the first 100 bits are 796 * unlikely to be set. It's guaranteed that at least one of the 140 797 * bits is cleared. 798 */ 799 static inline int sched_find_first_bit(unsigned long *b) 800 { 801 return find_first_bit(b, 140); 802 } 803 804 #include <asm-generic/bitops/fls.h> 805 #include <asm-generic/bitops/__fls.h> 806 #include <asm-generic/bitops/fls64.h> 807 808 #include <asm-generic/bitops/hweight.h> 809 #include <asm-generic/bitops/lock.h> 810 811 /* 812 * ATTENTION: intel byte ordering convention for ext2 and minix !! 813 * bit 0 is the LSB of addr; bit 31 is the MSB of addr; 814 * bit 32 is the LSB of (addr+4). 815 * That combined with the little endian byte order of Intel gives the 816 * following bit order in memory: 817 * 07 06 05 04 03 02 01 00 15 14 13 12 11 10 09 08 \ 818 * 23 22 21 20 19 18 17 16 31 30 29 28 27 26 25 24 819 */ 820 821 static inline int find_first_zero_bit_le(void *vaddr, unsigned int size) 822 { 823 unsigned long bytes, bits; 824 825 if (!size) 826 return 0; 827 bytes = __ffz_word_loop(vaddr, size); 828 bits = __ffz_word(bytes*8, __load_ulong_le(vaddr, bytes)); 829 return (bits < size) ? bits : size; 830 } 831 #define find_first_zero_bit_le find_first_zero_bit_le 832 833 static inline int find_next_zero_bit_le(void *vaddr, unsigned long size, 834 unsigned long offset) 835 { 836 unsigned long *addr = vaddr, *p; 837 unsigned long bit, set; 838 839 if (offset >= size) 840 return size; 841 bit = offset & (BITS_PER_LONG - 1); 842 offset -= bit; 843 size -= offset; 844 p = addr + offset / BITS_PER_LONG; 845 if (bit) { 846 /* 847 * s390 version of ffz returns BITS_PER_LONG 848 * if no zero bit is present in the word. 849 */ 850 set = __ffz_word(bit, __load_ulong_le(p, 0) >> bit); 851 if (set >= size) 852 return size + offset; 853 if (set < BITS_PER_LONG) 854 return set + offset; 855 offset += BITS_PER_LONG; 856 size -= BITS_PER_LONG; 857 p++; 858 } 859 return offset + find_first_zero_bit_le(p, size); 860 } 861 #define find_next_zero_bit_le find_next_zero_bit_le 862 863 static inline unsigned long find_first_bit_le(void *vaddr, unsigned long size) 864 { 865 unsigned long bytes, bits; 866 867 if (!size) 868 return 0; 869 bytes = __ffs_word_loop(vaddr, size); 870 bits = __ffs_word(bytes*8, __load_ulong_le(vaddr, bytes)); 871 return (bits < size) ? bits : size; 872 } 873 #define find_first_bit_le find_first_bit_le 874 875 static inline int find_next_bit_le(void *vaddr, unsigned long size, 876 unsigned long offset) 877 { 878 unsigned long *addr = vaddr, *p; 879 unsigned long bit, set; 880 881 if (offset >= size) 882 return size; 883 bit = offset & (BITS_PER_LONG - 1); 884 offset -= bit; 885 size -= offset; 886 p = addr + offset / BITS_PER_LONG; 887 if (bit) { 888 /* 889 * s390 version of ffz returns BITS_PER_LONG 890 * if no zero bit is present in the word. 891 */ 892 set = __ffs_word(0, __load_ulong_le(p, 0) & (~0UL << bit)); 893 if (set >= size) 894 return size + offset; 895 if (set < BITS_PER_LONG) 896 return set + offset; 897 offset += BITS_PER_LONG; 898 size -= BITS_PER_LONG; 899 p++; 900 } 901 return offset + find_first_bit_le(p, size); 902 } 903 #define find_next_bit_le find_next_bit_le 904 905 #include <asm-generic/bitops/le.h> 906 907 #include <asm-generic/bitops/ext2-atomic-setbit.h> 908 909 #endif /* _S390_BITOPS_H */ 910