[linux-block.git] / include / linux / bitops.h

/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _LINUX_BITOPS_H
#define _LINUX_BITOPS_H

#include <asm/types.h>
#include <linux/bits.h>
#include <linux/typecheck.h>

#include <uapi/linux/kernel.h>

/* Set bits in the first 'n' bytes when loaded from memory */
#ifdef __LITTLE_ENDIAN
#  define aligned_byte_mask(n) ((1UL << 8*(n))-1)
#else
#  define aligned_byte_mask(n) (~0xffUL << (BITS_PER_LONG - 8 - 8*(n)))
#endif

#define BITS_PER_TYPE(type)	(sizeof(type) * BITS_PER_BYTE)
#define BITS_TO_LONGS(nr)	__KERNEL_DIV_ROUND_UP(nr, BITS_PER_TYPE(long))
#define BITS_TO_U64(nr)		__KERNEL_DIV_ROUND_UP(nr, BITS_PER_TYPE(u64))
#define BITS_TO_U32(nr)		__KERNEL_DIV_ROUND_UP(nr, BITS_PER_TYPE(u32))
#define BITS_TO_BYTES(nr)	__KERNEL_DIV_ROUND_UP(nr, BITS_PER_TYPE(char))

extern unsigned int __sw_hweight8(unsigned int w);
extern unsigned int __sw_hweight16(unsigned int w);
extern unsigned int __sw_hweight32(unsigned int w);
extern unsigned long __sw_hweight64(__u64 w);

/*
 * Include this here because some architectures need generic_ffs/fls in
 * scope
 */
#include <asm/bitops.h>

#define for_each_set_bit(bit, addr, size) \
	for ((bit) = find_first_bit((addr), (size));		\
	     (bit) < (size);					\
	     (bit) = find_next_bit((addr), (size), (bit) + 1))

/* same as for_each_set_bit() but use bit as value to start with */
#define for_each_set_bit_from(bit, addr, size) \
	for ((bit) = find_next_bit((addr), (size), (bit));	\
	     (bit) < (size);					\
	     (bit) = find_next_bit((addr), (size), (bit) + 1))

#define for_each_clear_bit(bit, addr, size) \
	for ((bit) = find_first_zero_bit((addr), (size));	\
	     (bit) < (size);					\
	     (bit) = find_next_zero_bit((addr), (size), (bit) + 1))

/* same as for_each_clear_bit() but use bit as value to start with */
#define for_each_clear_bit_from(bit, addr, size) \
	for ((bit) = find_next_zero_bit((addr), (size), (bit));	\
	     (bit) < (size);					\
	     (bit) = find_next_zero_bit((addr), (size), (bit) + 1))

/**
 * for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits
 * @start: bit offset to start search and to store the current iteration offset
 * @clump: location to store copy of current 8-bit clump
 * @bits: bitmap address to base the search on
 * @size: bitmap size in number of bits
 */
#define for_each_set_clump8(start, clump, bits, size) \
	for ((start) = find_first_clump8(&(clump), (bits), (size)); \
	     (start) < (size); \
	     (start) = find_next_clump8(&(clump), (bits), (size), (start) + 8))

static inline int get_bitmask_order(unsigned int count)
{
	int order;

	order = fls(count);
	return order;	/* We could be slightly more clever with -1 here... */
}

static __always_inline unsigned long hweight_long(unsigned long w)
{
	return sizeof(w) == 4 ? hweight32(w) : hweight64((__u64)w);
}

/**
 * rol64 - rotate a 64-bit value left
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u64 rol64(__u64 word, unsigned int shift)
{
	return (word << (shift & 63)) | (word >> ((-shift) & 63));
}

/**
 * ror64 - rotate a 64-bit value right
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u64 ror64(__u64 word, unsigned int shift)
{
	return (word >> (shift & 63)) | (word << ((-shift) & 63));
}

/**
 * rol32 - rotate a 32-bit value left
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u32 rol32(__u32 word, unsigned int shift)
{
	return (word << (shift & 31)) | (word >> ((-shift) & 31));
}

/**
 * ror32 - rotate a 32-bit value right
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u32 ror32(__u32 word, unsigned int shift)
{
	return (word >> (shift & 31)) | (word << ((-shift) & 31));
}

/**
 * rol16 - rotate a 16-bit value left
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u16 rol16(__u16 word, unsigned int shift)
{
	return (word << (shift & 15)) | (word >> ((-shift) & 15));
}

/**
 * ror16 - rotate a 16-bit value right
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u16 ror16(__u16 word, unsigned int shift)
{
	return (word >> (shift & 15)) | (word << ((-shift) & 15));
}

/**
 * rol8 - rotate an 8-bit value left
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u8 rol8(__u8 word, unsigned int shift)
{
	return (word << (shift & 7)) | (word >> ((-shift) & 7));
}

/**
 * ror8 - rotate an 8-bit value right
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u8 ror8(__u8 word, unsigned int shift)
{
	return (word >> (shift & 7)) | (word << ((-shift) & 7));
}

/**
 * sign_extend32 - sign extend a 32-bit value using specified bit as sign-bit
 * @value: value to sign extend
 * @index: 0 based bit index (0<=index<32) to sign bit
 *
 * This is safe to use for 16- and 8-bit types as well.
 */
static __always_inline __s32 sign_extend32(__u32 value, int index)
{
	__u8 shift = 31 - index;
	return (__s32)(value << shift) >> shift;
}

/**
 * sign_extend64 - sign extend a 64-bit value using specified bit as sign-bit
 * @value: value to sign extend
 * @index: 0 based bit index (0<=index<64) to sign bit
 */
static __always_inline __s64 sign_extend64(__u64 value, int index)
{
	__u8 shift = 63 - index;
	return (__s64)(value << shift) >> shift;
}

static inline unsigned fls_long(unsigned long l)
{
	if (sizeof(l) == 4)
		return fls(l);
	return fls64(l);
}

static inline int get_count_order(unsigned int count)
{
	if (count == 0)
		return -1;

	return fls(--count);
}

/**
 * get_count_order_long - get order after rounding @l up to power of 2
 * @l: parameter
 *
 * it is same as get_count_order() but with long type parameter
 */
static inline int get_count_order_long(unsigned long l)
{
	if (l == 0UL)
		return -1;
	return (int)fls_long(--l);
}

/**
 * __ffs64 - find first set bit in a 64 bit word
 * @word: The 64 bit word
 *
 * On 64 bit arches this is a synonym for __ffs
 * The result is not defined if no bits are set, so check that @word
 * is non-zero before calling this.
 */
static inline unsigned long __ffs64(u64 word)
{
#if BITS_PER_LONG == 32
	if (((u32)word) == 0UL)
		return __ffs((u32)(word >> 32)) + 32;
#elif BITS_PER_LONG != 64
#error BITS_PER_LONG not 32 or 64
#endif
	return __ffs((unsigned long)word);
}

/**
 * assign_bit - Assign value to a bit in memory
 * @nr: the bit to set
 * @addr: the address to start counting from
 * @value: the value to assign
 */
static __always_inline void assign_bit(long nr, volatile unsigned long *addr,
				       bool value)
{
	if (value)
		set_bit(nr, addr);
	else
		clear_bit(nr, addr);
}

static __always_inline void __assign_bit(long nr, volatile unsigned long *addr,
					 bool value)
{
	if (value)
		__set_bit(nr, addr);
	else
		__clear_bit(nr, addr);
}

/**
 * __ptr_set_bit - Set bit in a pointer's value
 * @nr: the bit to set
 * @addr: the address of the pointer variable
 *
 * Example:
 *	void *p = foo();
 *	__ptr_set_bit(bit, &p);
 */
#define __ptr_set_bit(nr, addr)                         \
	({                                              \
		typecheck_pointer(*(addr));             \
		__set_bit(nr, (unsigned long *)(addr)); \
	})

/**
 * __ptr_clear_bit - Clear bit in a pointer's value
 * @nr: the bit to clear
 * @addr: the address of the pointer variable
 *
 * Example:
 *	void *p = foo();
 *	__ptr_clear_bit(bit, &p);
 */
#define __ptr_clear_bit(nr, addr)                         \
	({                                                \
		typecheck_pointer(*(addr));               \
		__clear_bit(nr, (unsigned long *)(addr)); \
	})

/**
 * __ptr_test_bit - Test bit in a pointer's value
 * @nr: the bit to test
 * @addr: the address of the pointer variable
 *
 * Example:
 *	void *p = foo();
 *	if (__ptr_test_bit(bit, &p)) {
 *	        ...
 *	} else {
 *		...
 *	}
 */
#define __ptr_test_bit(nr, addr)                       \
	({                                             \
		typecheck_pointer(*(addr));            \
		test_bit(nr, (unsigned long *)(addr)); \
	})

#ifdef __KERNEL__

#ifndef set_mask_bits
#define set_mask_bits(ptr, mask, bits)	\
({								\
	const typeof(*(ptr)) mask__ = (mask), bits__ = (bits);	\
	typeof(*(ptr)) old__, new__;				\
								\
	do {							\
		old__ = READ_ONCE(*(ptr));			\
		new__ = (old__ & ~mask__) | bits__;		\
	} while (cmpxchg(ptr, old__, new__) != old__);		\
								\
	old__;							\
})
#endif

#ifndef bit_clear_unless
#define bit_clear_unless(ptr, clear, test)	\
({								\
	const typeof(*(ptr)) clear__ = (clear), test__ = (test);\
	typeof(*(ptr)) old__, new__;				\
								\
	do {							\
		old__ = READ_ONCE(*(ptr));			\
		new__ = old__ & ~clear__;			\
	} while (!(old__ & test__) &&				\
		 cmpxchg(ptr, old__, new__) != old__);		\
								\
	!(old__ & test__);					\
})
#endif

#endif /* __KERNEL__ */
#endif
Commit	Line	Data
b2441318	1	/* SPDX-License-Identifier: GPL-2.0 */
1da177e4 LT	2	#ifndef _LINUX_BITOPS_H
1da177e4 LT	3	#define _LINUX_BITOPS_H
aa6159ab	4
1da177e4	5	#include <asm/types.h>
8bd9cb51	6	#include <linux/bits.h>
cb0f8003	7	#include <linux/typecheck.h>
1da177e4	8
aa6159ab AS	9	#include <uapi/linux/kernel.h>
aa6159ab AS	10
f5a1a536 AS	11	/* Set bits in the first 'n' bytes when loaded from memory */
	12	#ifdef __LITTLE_ENDIAN
	13	# define aligned_byte_mask(n) ((1UL << 8*(n))-1)
	14	#else
	15	# define aligned_byte_mask(n) (~0xffUL << (BITS_PER_LONG - 8 - 8*(n)))
	16	#endif
	17
0bddc1bd	18	#define BITS_PER_TYPE(type) (sizeof(type) * BITS_PER_BYTE)
aa6159ab AS	19	#define BITS_TO_LONGS(nr) __KERNEL_DIV_ROUND_UP(nr, BITS_PER_TYPE(long))
	20	#define BITS_TO_U64(nr) __KERNEL_DIV_ROUND_UP(nr, BITS_PER_TYPE(u64))
	21	#define BITS_TO_U32(nr) __KERNEL_DIV_ROUND_UP(nr, BITS_PER_TYPE(u32))
	22	#define BITS_TO_BYTES(nr) __KERNEL_DIV_ROUND_UP(nr, BITS_PER_TYPE(char))
10ef6b0d	23
4677d4a5 BP	24	extern unsigned int __sw_hweight8(unsigned int w);
	25	extern unsigned int __sw_hweight16(unsigned int w);
	26	extern unsigned int __sw_hweight32(unsigned int w);
	27	extern unsigned long __sw_hweight64(__u64 w);
	28
1da177e4 LT	29	/*
	30	* Include this here because some architectures need generic_ffs/fls in
	31	* scope
	32	*/
	33	#include <asm/bitops.h>
	34
984b3f57	35	#define for_each_set_bit(bit, addr, size) \
1e2ad28f RR	36	for ((bit) = find_first_bit((addr), (size)); \
	37	(bit) < (size); \
	38	(bit) = find_next_bit((addr), (size), (bit) + 1))
	39
	40	/* same as for_each_set_bit() but use bit as value to start with */
307b1cd7	41	#define for_each_set_bit_from(bit, addr, size) \
1e2ad28f RR	42	for ((bit) = find_next_bit((addr), (size), (bit)); \
1e2ad28f RR	43	(bit) < (size); \
3e037454 SN	44	(bit) = find_next_bit((addr), (size), (bit) + 1))
3e037454 SN	45
03f4a822 AM	46	#define for_each_clear_bit(bit, addr, size) \
	47	for ((bit) = find_first_zero_bit((addr), (size)); \
	48	(bit) < (size); \
	49	(bit) = find_next_zero_bit((addr), (size), (bit) + 1))
	50
	51	/* same as for_each_clear_bit() but use bit as value to start with */
	52	#define for_each_clear_bit_from(bit, addr, size) \
	53	for ((bit) = find_next_zero_bit((addr), (size), (bit)); \
	54	(bit) < (size); \
	55	(bit) = find_next_zero_bit((addr), (size), (bit) + 1))
	56
169c474f WBG	57	/**
	58	* for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits
	59	* @start: bit offset to start search and to store the current iteration offset
	60	* @clump: location to store copy of current 8-bit clump
	61	* @bits: bitmap address to base the search on
	62	* @size: bitmap size in number of bits
	63	*/
	64	#define for_each_set_clump8(start, clump, bits, size) \
	65	for ((start) = find_first_clump8(&(clump), (bits), (size)); \
	66	(start) < (size); \
	67	(start) = find_next_clump8(&(clump), (bits), (size), (start) + 8))
	68
1a1d48a4	69	static inline int get_bitmask_order(unsigned int count)
1da177e4 LT	70	{
1da177e4 LT	71	int order;
9f41699e	72
1da177e4 LT	73	order = fls(count);
	74	return order; /* We could be slightly more clever with -1 here... */
	75	}
	76
1a1d48a4	77	static __always_inline unsigned long hweight_long(unsigned long w)
1da177e4	78	{
bd93f003	79	return sizeof(w) == 4 ? hweight32(w) : hweight64((__u64)w);
1da177e4 LT	80	}
1da177e4 LT	81
f2ea0f5f AD	82	/**
	83	* rol64 - rotate a 64-bit value left
	84	* @word: value to rotate
	85	* @shift: bits to roll
	86	*/
	87	static inline __u64 rol64(__u64 word, unsigned int shift)
	88	{
ef4d6f6b	89	return (word << (shift & 63)) \| (word >> ((-shift) & 63));
f2ea0f5f AD	90	}
	91
	92	/**
	93	* ror64 - rotate a 64-bit value right
	94	* @word: value to rotate
	95	* @shift: bits to roll
	96	*/
	97	static inline __u64 ror64(__u64 word, unsigned int shift)
	98	{
ef4d6f6b	99	return (word >> (shift & 63)) \| (word << ((-shift) & 63));
f2ea0f5f AD	100	}
f2ea0f5f AD	101
45f8bde0	102	/**
1da177e4	103	* rol32 - rotate a 32-bit value left
1da177e4 LT	104	* @word: value to rotate
	105	* @shift: bits to roll
	106	*/
	107	static inline __u32 rol32(__u32 word, unsigned int shift)
	108	{
ef4d6f6b	109	return (word << (shift & 31)) \| (word >> ((-shift) & 31));
1da177e4 LT	110	}
1da177e4 LT	111
45f8bde0	112	/**
1da177e4	113	* ror32 - rotate a 32-bit value right
1da177e4 LT	114	* @word: value to rotate
	115	* @shift: bits to roll
	116	*/
	117	static inline __u32 ror32(__u32 word, unsigned int shift)
	118	{
ef4d6f6b	119	return (word >> (shift & 31)) \| (word << ((-shift) & 31));
1da177e4 LT	120	}
1da177e4 LT	121
3afe3925 HH	122	/**
	123	* rol16 - rotate a 16-bit value left
	124	* @word: value to rotate
	125	* @shift: bits to roll
	126	*/
	127	static inline __u16 rol16(__u16 word, unsigned int shift)
	128	{
ef4d6f6b	129	return (word << (shift & 15)) \| (word >> ((-shift) & 15));
3afe3925 HH	130	}
	131
	132	/**
	133	* ror16 - rotate a 16-bit value right
	134	* @word: value to rotate
	135	* @shift: bits to roll
	136	*/
	137	static inline __u16 ror16(__u16 word, unsigned int shift)
	138	{
ef4d6f6b	139	return (word >> (shift & 15)) \| (word << ((-shift) & 15));
3afe3925 HH	140	}
	141
	142	/**
	143	* rol8 - rotate an 8-bit value left
	144	* @word: value to rotate
	145	* @shift: bits to roll
	146	*/
	147	static inline __u8 rol8(__u8 word, unsigned int shift)
	148	{
ef4d6f6b	149	return (word << (shift & 7)) \| (word >> ((-shift) & 7));
3afe3925 HH	150	}
	151
	152	/**
	153	* ror8 - rotate an 8-bit value right
	154	* @word: value to rotate
	155	* @shift: bits to roll
	156	*/
	157	static inline __u8 ror8(__u8 word, unsigned int shift)
	158	{
ef4d6f6b	159	return (word >> (shift & 7)) \| (word << ((-shift) & 7));
3afe3925	160	}
7919a57b AH	161
	162	/**
	163	* sign_extend32 - sign extend a 32-bit value using specified bit as sign-bit
	164	* @value: value to sign extend
	165	* @index: 0 based bit index (0<=index<32) to sign bit
e2eb53aa MK	166	*
e2eb53aa MK	167	* This is safe to use for 16- and 8-bit types as well.
7919a57b	168	*/
f80ac98a	169	static __always_inline __s32 sign_extend32(__u32 value, int index)
7919a57b AH	170	{
	171	__u8 shift = 31 - index;
	172	return (__s32)(value << shift) >> shift;
	173	}
3afe3925	174
48e203e2 MK	175	/**
	176	* sign_extend64 - sign extend a 64-bit value using specified bit as sign-bit
	177	* @value: value to sign extend
	178	* @index: 0 based bit index (0<=index<64) to sign bit
	179	*/
f80ac98a	180	static __always_inline __s64 sign_extend64(__u64 value, int index)
48e203e2 MK	181	{
	182	__u8 shift = 63 - index;
	183	return (__s64)(value << shift) >> shift;
	184	}
	185
962749af AM	186	static inline unsigned fls_long(unsigned long l)
	187	{
	188	if (sizeof(l) == 4)
	189	return fls(l);
	190	return fls64(l);
	191	}
	192
252e5c6e	193	static inline int get_count_order(unsigned int count)
252e5c6e	194	{
004fba1a WY	195	if (count == 0)
004fba1a WY	196	return -1;
252e5c6e	197
004fba1a	198	return fls(--count);
252e5c6e	199	}
	200
	201	/**
	202	* get_count_order_long - get order after rounding @l up to power of 2
	203	* @l: parameter
	204	*
	205	* it is same as get_count_order() but with long type parameter
	206	*/
	207	static inline int get_count_order_long(unsigned long l)
	208	{
	209	if (l == 0UL)
	210	return -1;
a9eb6370	211	return (int)fls_long(--l);
252e5c6e	212	}
252e5c6e	213
952043ac SW	214	/**
	215	* __ffs64 - find first set bit in a 64 bit word
	216	* @word: The 64 bit word
	217	*
4945cca2	218	* On 64 bit arches this is a synonym for __ffs
952043ac SW	219	* The result is not defined if no bits are set, so check that @word
	220	* is non-zero before calling this.
	221	*/
	222	static inline unsigned long __ffs64(u64 word)
	223	{
	224	#if BITS_PER_LONG == 32
	225	if (((u32)word) == 0UL)
	226	return __ffs((u32)(word >> 32)) + 32;
	227	#elif BITS_PER_LONG != 64
	228	#error BITS_PER_LONG not 32 or 64
	229	#endif
	230	return __ffs((unsigned long)word);
	231	}
	232
5307e2ad LW	233	/**
	234	* assign_bit - Assign value to a bit in memory
	235	* @nr: the bit to set
	236	* @addr: the address to start counting from
	237	* @value: the value to assign
	238	*/
	239	static __always_inline void assign_bit(long nr, volatile unsigned long *addr,
	240	bool value)
	241	{
	242	if (value)
	243	set_bit(nr, addr);
	244	else
	245	clear_bit(nr, addr);
	246	}
	247
	248	static __always_inline void __assign_bit(long nr, volatile unsigned long *addr,
	249	bool value)
	250	{
	251	if (value)
	252	__set_bit(nr, addr);
	253	else
	254	__clear_bit(nr, addr);
	255	}
	256
cb0f8003 KKD	257	/**
	258	* __ptr_set_bit - Set bit in a pointer's value
	259	* @nr: the bit to set
	260	* @addr: the address of the pointer variable
	261	*
	262	* Example:
	263	* void *p = foo();
	264	* __ptr_set_bit(bit, &p);
	265	*/
	266	#define __ptr_set_bit(nr, addr) \
	267	({ \
	268	typecheck_pointer(*(addr)); \
	269	__set_bit(nr, (unsigned long *)(addr)); \
	270	})
	271
	272	/**
	273	* __ptr_clear_bit - Clear bit in a pointer's value
	274	* @nr: the bit to clear
	275	* @addr: the address of the pointer variable
	276	*
	277	* Example:
	278	* void *p = foo();
	279	* __ptr_clear_bit(bit, &p);
	280	*/
	281	#define __ptr_clear_bit(nr, addr) \
	282	({ \
	283	typecheck_pointer(*(addr)); \
	284	__clear_bit(nr, (unsigned long *)(addr)); \
	285	})
	286
	287	/**
	288	* __ptr_test_bit - Test bit in a pointer's value
	289	* @nr: the bit to test
	290	* @addr: the address of the pointer variable
	291	*
	292	* Example:
	293	* void *p = foo();
	294	* if (__ptr_test_bit(bit, &p)) {
	295	* ...
	296	* } else {
	297	* ...
	298	* }
	299	*/
	300	#define __ptr_test_bit(nr, addr) \
	301	({ \
	302	typecheck_pointer(*(addr)); \
	303	test_bit(nr, (unsigned long *)(addr)); \
	304	})
	305
64970b68	306	#ifdef __KERNEL__
77b9bd9c	307
00a1a053	308	#ifndef set_mask_bits
18127429	309	#define set_mask_bits(ptr, mask, bits) \
00a1a053	310	({ \
18127429 MS	311	const typeof(*(ptr)) mask__ = (mask), bits__ = (bits); \
18127429 MS	312	typeof(*(ptr)) old__, new__; \
00a1a053 TT	313	\
00a1a053 TT	314	do { \
18127429 MS	315	old__ = READ_ONCE(*(ptr)); \
	316	new__ = (old__ & ~mask__) \| bits__; \
	317	} while (cmpxchg(ptr, old__, new__) != old__); \
00a1a053	318	\
1db604f6	319	old__; \
00a1a053 TT	320	})
	321	#endif
	322
85ad1d13	323	#ifndef bit_clear_unless
edfa8728	324	#define bit_clear_unless(ptr, clear, test) \
85ad1d13	325	({ \
edfa8728 MS	326	const typeof(*(ptr)) clear__ = (clear), test__ = (test);\
edfa8728 MS	327	typeof(*(ptr)) old__, new__; \
85ad1d13 GJ	328	\
85ad1d13 GJ	329	do { \
edfa8728 MS	330	old__ = READ_ONCE(*(ptr)); \
	331	new__ = old__ & ~clear__; \
	332	} while (!(old__ & test__) && \
	333	cmpxchg(ptr, old__, new__) != old__); \
85ad1d13	334	\
edfa8728	335	!(old__ & test__); \
85ad1d13 GJ	336	})
	337	#endif
	338
64970b68	339	#endif /* __KERNEL__ */
1da177e4	340	#endif