5 * include/asm-s390/bitops.h
8 * Copyright (C) 1999 IBM Deutschland Entwicklung GmbH, IBM Corporation
9 * Author(s): Martin Schwidefsky (schwidefsky@de.ibm.com)
11 * Derived from "include/asm-i386/bitops.h"
12 * Copyright (C) 1992, Linus Torvalds
18 #ifndef _LINUX_BITOPS_H
19 #error only <linux/bitops.h> can be included directly
22 #include <linux/compiler.h>
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
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)".
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
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)".
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
[];
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"
74 #define __BITOPS_LOOP(__old, __new, __addr, __val, __op_string) \
78 __op_string " %1,%3\n" \
81 : "=&d" (__old), "=&d" (__new), \
82 "=Q" (*(unsigned long *) __addr) \
83 : "d" (__val), "Q" (*(unsigned long *) __addr) \
88 #define __BITOPS_ALIGN 7
89 #define __BITOPS_WORDSIZE 64
90 #define __BITOPS_OR "ogr"
91 #define __BITOPS_AND "ngr"
92 #define __BITOPS_XOR "xgr"
94 #define __BITOPS_LOOP(__old, __new, __addr, __val, __op_string) \
98 __op_string " %1,%3\n" \
101 : "=&d" (__old), "=&d" (__new), \
102 "=Q" (*(unsigned long *) __addr) \
103 : "d" (__val), "Q" (*(unsigned long *) __addr) \
106 #endif /* __s390x__ */
108 #define __BITOPS_WORDS(bits) (((bits)+__BITOPS_WORDSIZE-1)/__BITOPS_WORDSIZE)
109 #define __BITOPS_BARRIER() asm volatile("" : : : "memory")
113 * SMP safe set_bit routine based on compare and swap (CS)
115 static inline void set_bit_cs(unsigned long nr
, volatile unsigned long *ptr
)
117 unsigned long addr
, old
, new, mask
;
119 addr
= (unsigned long) ptr
;
120 /* calculate address for CS */
121 addr
+= (nr
^ (nr
& (__BITOPS_WORDSIZE
- 1))) >> 3;
123 mask
= 1UL << (nr
& (__BITOPS_WORDSIZE
- 1));
124 /* Do the atomic update. */
125 __BITOPS_LOOP(old
, new, addr
, mask
, __BITOPS_OR
);
129 * SMP safe clear_bit routine based on compare and swap (CS)
131 static inline void clear_bit_cs(unsigned long nr
, volatile unsigned long *ptr
)
133 unsigned long addr
, old
, new, mask
;
135 addr
= (unsigned long) ptr
;
136 /* calculate address for CS */
137 addr
+= (nr
^ (nr
& (__BITOPS_WORDSIZE
- 1))) >> 3;
139 mask
= ~(1UL << (nr
& (__BITOPS_WORDSIZE
- 1)));
140 /* Do the atomic update. */
141 __BITOPS_LOOP(old
, new, addr
, mask
, __BITOPS_AND
);
145 * SMP safe change_bit routine based on compare and swap (CS)
147 static inline void change_bit_cs(unsigned long nr
, volatile unsigned long *ptr
)
149 unsigned long addr
, old
, new, mask
;
151 addr
= (unsigned long) ptr
;
152 /* calculate address for CS */
153 addr
+= (nr
^ (nr
& (__BITOPS_WORDSIZE
- 1))) >> 3;
155 mask
= 1UL << (nr
& (__BITOPS_WORDSIZE
- 1));
156 /* Do the atomic update. */
157 __BITOPS_LOOP(old
, new, addr
, mask
, __BITOPS_XOR
);
161 * SMP safe test_and_set_bit routine based on compare and swap (CS)
164 test_and_set_bit_cs(unsigned long nr
, volatile unsigned long *ptr
)
166 unsigned long addr
, old
, new, mask
;
168 addr
= (unsigned long) ptr
;
169 /* calculate address for CS */
170 addr
+= (nr
^ (nr
& (__BITOPS_WORDSIZE
- 1))) >> 3;
171 /* make OR/test mask */
172 mask
= 1UL << (nr
& (__BITOPS_WORDSIZE
- 1));
173 /* Do the atomic update. */
174 __BITOPS_LOOP(old
, new, addr
, mask
, __BITOPS_OR
);
176 return (old
& mask
) != 0;
180 * SMP safe test_and_clear_bit routine based on compare and swap (CS)
183 test_and_clear_bit_cs(unsigned long nr
, volatile unsigned long *ptr
)
185 unsigned long addr
, old
, new, mask
;
187 addr
= (unsigned long) ptr
;
188 /* calculate address for CS */
189 addr
+= (nr
^ (nr
& (__BITOPS_WORDSIZE
- 1))) >> 3;
190 /* make AND/test mask */
191 mask
= ~(1UL << (nr
& (__BITOPS_WORDSIZE
- 1)));
192 /* Do the atomic update. */
193 __BITOPS_LOOP(old
, new, addr
, mask
, __BITOPS_AND
);
195 return (old
^ new) != 0;
199 * SMP safe test_and_change_bit routine based on compare and swap (CS)
202 test_and_change_bit_cs(unsigned long nr
, volatile unsigned long *ptr
)
204 unsigned long addr
, old
, new, mask
;
206 addr
= (unsigned long) ptr
;
207 /* calculate address for CS */
208 addr
+= (nr
^ (nr
& (__BITOPS_WORDSIZE
- 1))) >> 3;
209 /* make XOR/test mask */
210 mask
= 1UL << (nr
& (__BITOPS_WORDSIZE
- 1));
211 /* Do the atomic update. */
212 __BITOPS_LOOP(old
, new, addr
, mask
, __BITOPS_XOR
);
214 return (old
& mask
) != 0;
216 #endif /* CONFIG_SMP */
219 * fast, non-SMP set_bit routine
221 static inline void __set_bit(unsigned long nr
, volatile unsigned long *ptr
)
225 addr
= (unsigned long) ptr
+ ((nr
^ (__BITOPS_WORDSIZE
- 8)) >> 3);
228 : "=Q" (*(char *) addr
) : "Q" (_oi_bitmap
[nr
& 7]) : "cc" );
232 __constant_set_bit(const unsigned long nr
, volatile unsigned long *ptr
)
236 addr
= ((unsigned long) ptr
) + ((nr
^ (__BITOPS_WORDSIZE
- 8)) >> 3);
237 *(unsigned char *) addr
|= 1 << (nr
& 7);
240 #define set_bit_simple(nr,addr) \
241 (__builtin_constant_p((nr)) ? \
242 __constant_set_bit((nr),(addr)) : \
243 __set_bit((nr),(addr)) )
246 * fast, non-SMP clear_bit routine
249 __clear_bit(unsigned long nr
, volatile unsigned long *ptr
)
253 addr
= (unsigned long) ptr
+ ((nr
^ (__BITOPS_WORDSIZE
- 8)) >> 3);
256 : "=Q" (*(char *) addr
) : "Q" (_ni_bitmap
[nr
& 7]) : "cc" );
260 __constant_clear_bit(const unsigned long nr
, volatile unsigned long *ptr
)
264 addr
= ((unsigned long) ptr
) + ((nr
^ (__BITOPS_WORDSIZE
- 8)) >> 3);
265 *(unsigned char *) addr
&= ~(1 << (nr
& 7));
268 #define clear_bit_simple(nr,addr) \
269 (__builtin_constant_p((nr)) ? \
270 __constant_clear_bit((nr),(addr)) : \
271 __clear_bit((nr),(addr)) )
274 * fast, non-SMP change_bit routine
276 static inline void __change_bit(unsigned long nr
, volatile unsigned long *ptr
)
280 addr
= (unsigned long) ptr
+ ((nr
^ (__BITOPS_WORDSIZE
- 8)) >> 3);
283 : "=Q" (*(char *) addr
) : "Q" (_oi_bitmap
[nr
& 7]) : "cc" );
287 __constant_change_bit(const unsigned long nr
, volatile unsigned long *ptr
)
291 addr
= ((unsigned long) ptr
) + ((nr
^ (__BITOPS_WORDSIZE
- 8)) >> 3);
292 *(unsigned char *) addr
^= 1 << (nr
& 7);
295 #define change_bit_simple(nr,addr) \
296 (__builtin_constant_p((nr)) ? \
297 __constant_change_bit((nr),(addr)) : \
298 __change_bit((nr),(addr)) )
301 * fast, non-SMP test_and_set_bit routine
304 test_and_set_bit_simple(unsigned long nr
, volatile unsigned long *ptr
)
309 addr
= (unsigned long) ptr
+ ((nr
^ (__BITOPS_WORDSIZE
- 8)) >> 3);
310 ch
= *(unsigned char *) addr
;
313 : "=Q" (*(char *) addr
) : "Q" (_oi_bitmap
[nr
& 7])
315 return (ch
>> (nr
& 7)) & 1;
317 #define __test_and_set_bit(X,Y) test_and_set_bit_simple(X,Y)
320 * fast, non-SMP test_and_clear_bit routine
323 test_and_clear_bit_simple(unsigned long nr
, volatile unsigned long *ptr
)
328 addr
= (unsigned long) ptr
+ ((nr
^ (__BITOPS_WORDSIZE
- 8)) >> 3);
329 ch
= *(unsigned char *) addr
;
332 : "=Q" (*(char *) addr
) : "Q" (_ni_bitmap
[nr
& 7])
334 return (ch
>> (nr
& 7)) & 1;
336 #define __test_and_clear_bit(X,Y) test_and_clear_bit_simple(X,Y)
339 * fast, non-SMP test_and_change_bit routine
342 test_and_change_bit_simple(unsigned long nr
, volatile unsigned long *ptr
)
347 addr
= (unsigned long) ptr
+ ((nr
^ (__BITOPS_WORDSIZE
- 8)) >> 3);
348 ch
= *(unsigned char *) addr
;
351 : "=Q" (*(char *) addr
) : "Q" (_oi_bitmap
[nr
& 7])
353 return (ch
>> (nr
& 7)) & 1;
355 #define __test_and_change_bit(X,Y) test_and_change_bit_simple(X,Y)
358 #define set_bit set_bit_cs
359 #define clear_bit clear_bit_cs
360 #define change_bit change_bit_cs
361 #define test_and_set_bit test_and_set_bit_cs
362 #define test_and_clear_bit test_and_clear_bit_cs
363 #define test_and_change_bit test_and_change_bit_cs
365 #define set_bit set_bit_simple
366 #define clear_bit clear_bit_simple
367 #define change_bit change_bit_simple
368 #define test_and_set_bit test_and_set_bit_simple
369 #define test_and_clear_bit test_and_clear_bit_simple
370 #define test_and_change_bit test_and_change_bit_simple
375 * This routine doesn't need to be atomic.
378 static inline int __test_bit(unsigned long nr
, const volatile unsigned long *ptr
)
383 addr
= (unsigned long) ptr
+ ((nr
^ (__BITOPS_WORDSIZE
- 8)) >> 3);
384 ch
= *(volatile unsigned char *) addr
;
385 return (ch
>> (nr
& 7)) & 1;
389 __constant_test_bit(unsigned long nr
, const volatile unsigned long *addr
) {
390 return (((volatile char *) addr
)
391 [(nr
^(__BITOPS_WORDSIZE
-8))>>3] & (1<<(nr
&7))) != 0;
394 #define test_bit(nr,addr) \
395 (__builtin_constant_p((nr)) ? \
396 __constant_test_bit((nr),(addr)) : \
397 __test_bit((nr),(addr)) )
400 * Optimized find bit helper functions.
404 * __ffz_word_loop - find byte offset of first long != -1UL
405 * @addr: pointer to array of unsigned long
406 * @size: size of the array in bits
408 static inline unsigned long __ffz_word_loop(const unsigned long *addr
,
411 typedef struct { long _
[__BITOPS_WORDS(size
)]; } addrtype
;
412 unsigned long bytes
= 0;
428 "0: cg %2,0(%0,%3)\n"
434 : "+&a" (bytes
), "+&d" (size
)
435 : "d" (-1UL), "a" (addr
), "m" (*(addrtype
*) addr
)
441 * __ffs_word_loop - find byte offset of first long != 0UL
442 * @addr: pointer to array of unsigned long
443 * @size: size of the array in bits
445 static inline unsigned long __ffs_word_loop(const unsigned long *addr
,
448 typedef struct { long _
[__BITOPS_WORDS(size
)]; } addrtype
;
449 unsigned long bytes
= 0;
465 "0: cg %2,0(%0,%3)\n"
471 : "+&a" (bytes
), "+&a" (size
)
472 : "d" (0UL), "a" (addr
), "m" (*(addrtype
*) addr
)
478 * __ffz_word - add number of the first unset bit
479 * @nr: base value the bit number is added to
480 * @word: the word that is searched for unset bits
482 static inline unsigned long __ffz_word(unsigned long nr
, unsigned long word
)
485 if ((word
& 0xffffffff) == 0xffffffff) {
490 if ((word
& 0xffff) == 0xffff) {
494 if ((word
& 0xff) == 0xff) {
498 return nr
+ _zb_findmap
[(unsigned char) word
];
502 * __ffs_word - add number of the first set bit
503 * @nr: base value the bit number is added to
504 * @word: the word that is searched for set bits
506 static inline unsigned long __ffs_word(unsigned long nr
, unsigned long word
)
509 if ((word
& 0xffffffff) == 0) {
514 if ((word
& 0xffff) == 0) {
518 if ((word
& 0xff) == 0) {
522 return nr
+ _sb_findmap
[(unsigned char) word
];
527 * __load_ulong_be - load big endian unsigned long
528 * @p: pointer to array of unsigned long
529 * @offset: byte offset of source value in the array
531 static inline unsigned long __load_ulong_be(const unsigned long *p
,
532 unsigned long offset
)
534 p
= (unsigned long *)((unsigned long) p
+ offset
);
539 * __load_ulong_le - load little endian unsigned long
540 * @p: pointer to array of unsigned long
541 * @offset: byte offset of source value in the array
543 static inline unsigned long __load_ulong_le(const unsigned long *p
,
544 unsigned long offset
)
548 p
= (unsigned long *)((unsigned long) p
+ offset
);
552 " icm %0,2,%O1+1(%R1)\n"
553 " icm %0,4,%O1+2(%R1)\n"
554 " icm %0,8,%O1+3(%R1)"
555 : "=&d" (word
) : "Q" (*p
) : "cc");
559 : "=d" (word
) : "m" (*p
) );
565 * The various find bit functions.
569 * ffz - find first zero in word.
570 * @word: The word to search
572 * Undefined if no zero exists, so code should check against ~0UL first.
574 static inline unsigned long ffz(unsigned long word
)
576 return __ffz_word(0, word
);
580 * __ffs - find first bit in word.
581 * @word: The word to search
583 * Undefined if no bit exists, so code should check against 0 first.
585 static inline unsigned long __ffs (unsigned long word
)
587 return __ffs_word(0, word
);
591 * ffs - find first bit set
592 * @x: the word to search
594 * This is defined the same way as
595 * the libc and compiler builtin ffs routines, therefore
596 * differs in spirit from the above ffz (man ffs).
598 static inline int ffs(int x
)
602 return __ffs_word(1, x
);
606 * find_first_zero_bit - find the first zero bit in a memory region
607 * @addr: The address to start the search at
608 * @size: The maximum size to search
610 * Returns the bit-number of the first zero bit, not the number of the byte
613 static inline unsigned long find_first_zero_bit(const unsigned long *addr
,
616 unsigned long bytes
, bits
;
620 bytes
= __ffz_word_loop(addr
, size
);
621 bits
= __ffz_word(bytes
*8, __load_ulong_be(addr
, bytes
));
622 return (bits
< size
) ? bits
: size
;
624 #define find_first_zero_bit find_first_zero_bit
627 * find_first_bit - find the first set bit in a memory region
628 * @addr: The address to start the search at
629 * @size: The maximum size to search
631 * Returns the bit-number of the first set bit, not the number of the byte
634 static inline unsigned long find_first_bit(const unsigned long * addr
,
637 unsigned long bytes
, bits
;
641 bytes
= __ffs_word_loop(addr
, size
);
642 bits
= __ffs_word(bytes
*8, __load_ulong_be(addr
, bytes
));
643 return (bits
< size
) ? bits
: size
;
645 #define find_first_bit find_first_bit
648 * find_next_zero_bit - find the first zero bit in a memory region
649 * @addr: The address to base the search on
650 * @offset: The bitnumber to start searching at
651 * @size: The maximum size to search
653 static inline int find_next_zero_bit (const unsigned long * addr
,
655 unsigned long offset
)
657 const unsigned long *p
;
658 unsigned long bit
, set
;
662 bit
= offset
& (__BITOPS_WORDSIZE
- 1);
665 p
= addr
+ offset
/ __BITOPS_WORDSIZE
;
668 * __ffz_word returns __BITOPS_WORDSIZE
669 * if no zero bit is present in the word.
671 set
= __ffz_word(bit
, *p
>> bit
);
673 return size
+ offset
;
674 if (set
< __BITOPS_WORDSIZE
)
676 offset
+= __BITOPS_WORDSIZE
;
677 size
-= __BITOPS_WORDSIZE
;
680 return offset
+ find_first_zero_bit(p
, size
);
682 #define find_next_zero_bit find_next_zero_bit
685 * find_next_bit - find the first set bit in a memory region
686 * @addr: The address to base the search on
687 * @offset: The bitnumber to start searching at
688 * @size: The maximum size to search
690 static inline int find_next_bit (const unsigned long * addr
,
692 unsigned long offset
)
694 const unsigned long *p
;
695 unsigned long bit
, set
;
699 bit
= offset
& (__BITOPS_WORDSIZE
- 1);
702 p
= addr
+ offset
/ __BITOPS_WORDSIZE
;
705 * __ffs_word returns __BITOPS_WORDSIZE
706 * if no one bit is present in the word.
708 set
= __ffs_word(0, *p
& (~0UL << bit
));
710 return size
+ offset
;
711 if (set
< __BITOPS_WORDSIZE
)
713 offset
+= __BITOPS_WORDSIZE
;
714 size
-= __BITOPS_WORDSIZE
;
717 return offset
+ find_first_bit(p
, size
);
719 #define find_next_bit find_next_bit
722 * Every architecture must define this function. It's the fastest
723 * way of searching a 140-bit bitmap where the first 100 bits are
724 * unlikely to be set. It's guaranteed that at least one of the 140
727 static inline int sched_find_first_bit(unsigned long *b
)
729 return find_first_bit(b
, 140);
732 #include <asm-generic/bitops/fls.h>
733 #include <asm-generic/bitops/__fls.h>
734 #include <asm-generic/bitops/fls64.h>
736 #include <asm-generic/bitops/hweight.h>
737 #include <asm-generic/bitops/lock.h>
740 * ATTENTION: intel byte ordering convention for ext2 and minix !!
741 * bit 0 is the LSB of addr; bit 31 is the MSB of addr;
742 * bit 32 is the LSB of (addr+4).
743 * That combined with the little endian byte order of Intel gives the
744 * following bit order in memory:
745 * 07 06 05 04 03 02 01 00 15 14 13 12 11 10 09 08 \
746 * 23 22 21 20 19 18 17 16 31 30 29 28 27 26 25 24
749 static inline int find_first_zero_bit_le(void *vaddr
, unsigned int size
)
751 unsigned long bytes
, bits
;
755 bytes
= __ffz_word_loop(vaddr
, size
);
756 bits
= __ffz_word(bytes
*8, __load_ulong_le(vaddr
, bytes
));
757 return (bits
< size
) ? bits
: size
;
759 #define find_first_zero_bit_le find_first_zero_bit_le
761 static inline int find_next_zero_bit_le(void *vaddr
, unsigned long size
,
762 unsigned long offset
)
764 unsigned long *addr
= vaddr
, *p
;
765 unsigned long bit
, set
;
769 bit
= offset
& (__BITOPS_WORDSIZE
- 1);
772 p
= addr
+ offset
/ __BITOPS_WORDSIZE
;
775 * s390 version of ffz returns __BITOPS_WORDSIZE
776 * if no zero bit is present in the word.
778 set
= __ffz_word(bit
, __load_ulong_le(p
, 0) >> bit
);
780 return size
+ offset
;
781 if (set
< __BITOPS_WORDSIZE
)
783 offset
+= __BITOPS_WORDSIZE
;
784 size
-= __BITOPS_WORDSIZE
;
787 return offset
+ find_first_zero_bit_le(p
, size
);
789 #define find_next_zero_bit_le find_next_zero_bit_le
791 static inline unsigned long find_first_bit_le(void *vaddr
, unsigned long size
)
793 unsigned long bytes
, bits
;
797 bytes
= __ffs_word_loop(vaddr
, size
);
798 bits
= __ffs_word(bytes
*8, __load_ulong_le(vaddr
, bytes
));
799 return (bits
< size
) ? bits
: size
;
801 #define find_first_bit_le find_first_bit_le
803 static inline int find_next_bit_le(void *vaddr
, unsigned long size
,
804 unsigned long offset
)
806 unsigned long *addr
= vaddr
, *p
;
807 unsigned long bit
, set
;
811 bit
= offset
& (__BITOPS_WORDSIZE
- 1);
814 p
= addr
+ offset
/ __BITOPS_WORDSIZE
;
817 * s390 version of ffz returns __BITOPS_WORDSIZE
818 * if no zero bit is present in the word.
820 set
= __ffs_word(0, __load_ulong_le(p
, 0) & (~0UL << bit
));
822 return size
+ offset
;
823 if (set
< __BITOPS_WORDSIZE
)
825 offset
+= __BITOPS_WORDSIZE
;
826 size
-= __BITOPS_WORDSIZE
;
829 return offset
+ find_first_bit_le(p
, size
);
831 #define find_next_bit_le find_next_bit_le
833 #include <asm-generic/bitops/le.h>
835 #define ext2_set_bit_atomic(lock, nr, addr) \
836 test_and_set_bit_le(nr, addr)
837 #define ext2_clear_bit_atomic(lock, nr, addr) \
838 test_and_clear_bit_le(nr, addr)
841 #endif /* __KERNEL__ */
843 #endif /* _S390_BITOPS_H */