1 /* SPDX-License-Identifier: GPL-2.0 */
15 #include <linux/bitmap-str.h>
39  * compile-time and at most BITS_PER_LONG.
84  *  bitmap_get_value8(map, start)               Get 8bit value from map at start
85  *  bitmap_set_value8(map, value, start)        Set 8bit value to map at start
86  *  bitmap_read(map, start, nbits)              Read an nbits-sized value from
87  *                                              map at start
88  *  bitmap_write(map, value, start, nbits)      Write an nbits-sized value to
89  *                                              map at start
107  *  test_and_set_bit(bit, addr)         Set bit and return old value
108  *  test_and_clear_bit(bit, addr)       Clear bit and return old value
109  *  test_and_change_bit(bit, addr)      Change bit and return old value
125  * contain all bit positions from 0 to 'bits' - 1.
184 void __bitmap_set(unsigned long *map, unsigned int start, int len);
185 void __bitmap_clear(unsigned long *map, unsigned int start, int len);
189 					     unsigned long start,
195  * bitmap_find_next_zero_area - find a contiguous aligned zero area
198  * @start: The bitnumber to start searching at
209 					 unsigned long start,  in bitmap_find_next_zero_area()  argument
213 	return bitmap_find_next_zero_area_off(map, size, start, nr,  in bitmap_find_next_zero_area()
226 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))  argument
227 #define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
281 		to[copy - 1] &= BITMAP_LAST_WORD_MASK(count);  in bitmap_copy_and_extend()
282 	memset(to + copy, 0, bitmap_size(size) - copy * sizeof(long));  in bitmap_copy_and_extend()
286  * On 32-bit systems bitmaps are represented as u32 arrays internally. On LE64
290  * to out-of-bound access. To avoid that, both LE and BE variants of 64-bit
308  * On 64-bit systems bitmaps are represented as u64 arrays internally. So,
373 #define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1)
387  * bitmap_or_equal - Check whether the or of two bitmaps is equal to a third
468 void bitmap_set(unsigned long *map, unsigned int start, unsigned int nbits)  in bitmap_set()  argument
471 		__set_bit(start, map);  in bitmap_set()
472 	else if (small_const_nbits(start + nbits))  in bitmap_set()
473 		*map |= GENMASK(start + nbits - 1, start);  in bitmap_set()
474 	else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&  in bitmap_set()
475 		 IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&  in bitmap_set()
478 		memset((char *)map + start / 8, 0xff, nbits / 8);  in bitmap_set()
480 		__bitmap_set(map, start, nbits);  in bitmap_set()
484 void bitmap_clear(unsigned long *map, unsigned int start, unsigned int nbits)  in bitmap_clear()  argument
487 		__clear_bit(start, map);  in bitmap_clear()
488 	else if (small_const_nbits(start + nbits))  in bitmap_clear()
489 		*map &= ~GENMASK(start + nbits - 1, start);  in bitmap_clear()
490 	else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&  in bitmap_clear()
491 		 IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&  in bitmap_clear()
494 		memset((char *)map + start / 8, 0, nbits / 8);  in bitmap_clear()
496 		__bitmap_clear(map, start, nbits);  in bitmap_clear()
533  * bitmap_scatter - Scatter a bitmap according to the given mask
554  *	         +------+|||||
555  *	         |  +----+||||
556  *	         |  |+----+|||
557  *	         |  ||   +-+||
581  * bitmap_gather - Gather a bitmap according to given mask
605  *	         |  |+--> 1010
606  *	         |  +--> 11010
607  *	         +----> 011010
622  * bitmap_scatter(res, result, mask, n) will lead to the same res value.
646  * bitmap_release_region - release allocated bitmap region
661  * bitmap_allocate_region - allocate bitmap region
668  * Returns: 0 on success, or %-EBUSY if specified region wasn't
677 		return -EBUSY;  in bitmap_allocate_region()
683  * bitmap_find_free_region - find a contiguous aligned mem region
694  * or -errno on failure.
705 	return -ENOMEM;  in bitmap_find_free_region()
709  * BITMAP_FROM_U64() - Represent u64 value in the format suitable for bitmap.
710  * @n: u64 value
712  * Linux bitmaps are internally arrays of unsigned longs, i.e. 32-bit
713  * integers in 32-bit environment, and 64-bit integers in 64-bit one.
718  * On 64-bit kernels 64-bit LE and BE numbers are naturally ordered in
721  * On 32-bit kernels 32-bit LE ABI orders lo word of 64-bit number in memory
722  * prior to hi, and 32-bit BE orders hi word prior to lo. The bitmap on the
723  * other hand is represented as an array of 32-bit words and the position of
726  * It matches 32-bit LE ABI, and we can simply let the compiler store 64-bit
742  * bitmap_from_u64 - Check and swap words within u64.
746  * In 32-bit Big Endian kernel, when using ``(u32 *)(&val)[*]``
749  * but we expect the lower 32-bits of u64.
757  * bitmap_read - read a value of n-bits from the memory region
759  * @start: bit offset of the n-bit value
760  * @nbits: size of value in bits, nonzero, up to BITS_PER_LONG
762  * Returns: value of @nbits bits located at the @start bit offset within the
764  * value is undefined.
767 unsigned long bitmap_read(const unsigned long *map, unsigned long start, unsigned long nbits)  in bitmap_read()  argument
769 	size_t index = BIT_WORD(start);  in bitmap_read()
770 	unsigned long offset = start % BITS_PER_LONG;  in bitmap_read()
771 	unsigned long space = BITS_PER_LONG - offset;  in bitmap_read()
780 	value_low = map[index] & BITMAP_FIRST_WORD_MASK(start);  in bitmap_read()
781 	value_high = map[index + 1] & BITMAP_LAST_WORD_MASK(start + nbits);  in bitmap_read()
786  * bitmap_write - write n-bit value within a memory region
788  * @value: value to write, clamped to nbits
789  * @start: bit offset of the n-bit value
790  * @nbits: size of value in bits, nonzero, up to BITS_PER_LONG.
792  * bitmap_write() behaves as-if implemented as @nbits calls of __assign_bit(),
796  *           __assign_bit(start + bit, bitmap, val & BIT(bit));
801 void bitmap_write(unsigned long *map, unsigned long value,  in bitmap_write()  argument
802 		  unsigned long start, unsigned long nbits)  in bitmap_write()  argument
814 	value &= mask;  in bitmap_write()
815 	offset = start % BITS_PER_LONG;  in bitmap_write()
816 	space = BITS_PER_LONG - offset;  in bitmap_write()
818 	index = BIT_WORD(start);  in bitmap_write()
820 	map[index] &= (fit ? (~(mask << offset)) : ~BITMAP_FIRST_WORD_MASK(start));  in bitmap_write()
821 	map[index] |= value << offset;  in bitmap_write()
825 	map[index + 1] &= BITMAP_FIRST_WORD_MASK(start + nbits);  in bitmap_write()
826 	map[index + 1] |= (value >> space);  in bitmap_write()
829 #define bitmap_get_value8(map, start)			\  argument
830 	bitmap_read(map, start, BITS_PER_BYTE)
831 #define bitmap_set_value8(map, value, start)		\  argument
832 	bitmap_write(map, value, start, BITS_PER_BYTE)