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