1 /* SPDX-License-Identifier: GPL-2.0 */
23  * specific are in various include/asm-<arch>/bitops.h headers
36  * compile-time and at most BITS_PER_LONG.
57  *  bitmap_find_next_zero_area(buf, len, pos, n, mask)  Find bit free area
58  *  bitmap_find_next_zero_area_off(buf, len, pos, n, mask, mask_off)  as above
62  *  bitmap_replace(dst, old, new, mask, nbits)  *dst = (*old & ~(*mask)) | (*new & *mask)
63  *  bitmap_remap(dst, src, old, new, nbits)     *dst = map(old, new)(src)
64  *  bitmap_bitremap(oldbit, old, new, nbits)    newbit = map(old, new)(oldbit)
78  *  bitmap_get_value8(map, start)               Get 8bit value from map at start
79  *  bitmap_set_value8(map, value, start)        Set 8bit value to map at start
115  * contain all bit positions from 0 to 'bits' - 1.
122 unsigned long *bitmap_alloc(unsigned int nbits, gfp_t flags);
123 unsigned long *bitmap_zalloc(unsigned int nbits, gfp_t flags);
124 unsigned long *bitmap_alloc_node(unsigned int nbits, gfp_t flags, int node);
125 unsigned long *bitmap_zalloc_node(unsigned int nbits, gfp_t flags, int node);
130 				 unsigned int nbits, gfp_t flags);
132 				  unsigned int nbits, gfp_t flags);
139 		    const unsigned long *bitmap2, unsigned int nbits);
143 			      unsigned int nbits);
145 			 unsigned int nbits);
147 			  unsigned int shift, unsigned int nbits);
149 			 unsigned int shift, unsigned int nbits);
151 		unsigned int first, unsigned int cut, unsigned int nbits);
153 		 const unsigned long *bitmap2, unsigned int nbits);
155 		 const unsigned long *bitmap2, unsigned int nbits);
157 		  const unsigned long *bitmap2, unsigned int nbits);
159 		    const unsigned long *bitmap2, unsigned int nbits);
162 		      const unsigned long *mask, unsigned int nbits);
164 			 const unsigned long *bitmap2, unsigned int nbits);
166 		     const unsigned long *bitmap2, unsigned int nbits);
167 unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int nbits);
168 unsigned int __bitmap_weight_and(const unsigned long *bitmap1,
169 				 const unsigned long *bitmap2, unsigned int nbits);
170 void __bitmap_set(unsigned long *map, unsigned int start, int len);
171 void __bitmap_clear(unsigned long *map, unsigned int start, int len);
173 unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
176 					     unsigned int nr,
181  * bitmap_find_next_zero_area - find a contiguous aligned zero area
182  * @map: The address to base the search on
186  * @align_mask: Alignment mask for zero area
193 bitmap_find_next_zero_area(unsigned long *map,  in bitmap_find_next_zero_area()  argument
196 			   unsigned int nr,  in bitmap_find_next_zero_area()
199 	return bitmap_find_next_zero_area_off(map, size, start, nr,  in bitmap_find_next_zero_area()
203 int bitmap_parse(const char *buf, unsigned int buflen,
204 			unsigned long *dst, int nbits);
205 int bitmap_parse_user(const char __user *ubuf, unsigned int ulen,
206 			unsigned long *dst, int nbits);
207 int bitmap_parselist(const char *buf, unsigned long *maskp,
208 			int nmaskbits);
209 int bitmap_parselist_user(const char __user *ubuf, unsigned int ulen,
210 			unsigned long *dst, int nbits);
212 		const unsigned long *old, const unsigned long *new, unsigned int nbits);
213 int bitmap_bitremap(int oldbit,
214 		const unsigned long *old, const unsigned long *new, int bits);
216 		const unsigned long *relmap, unsigned int bits);
218 		unsigned int sz, unsigned int nbits);
219 int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order);
220 void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order);
221 int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order);
224 void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits);
228 int bitmap_print_to_pagebuf(bool list, char *buf,
229 				   const unsigned long *maskp, int nmaskbits);
231 extern int bitmap_print_bitmask_to_buf(char *buf, const unsigned long *maskp,
232 				      int nmaskbits, loff_t off, size_t count);
234 extern int bitmap_print_list_to_buf(char *buf, const unsigned long *maskp,
235 				      int nmaskbits, loff_t off, size_t count);
237 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
238 #define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
240 static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)  in bitmap_zero()
242 	unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);  in bitmap_zero()
250 static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)  in bitmap_fill()
252 	unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);  in bitmap_fill()
261 			unsigned int nbits)  in bitmap_copy()
263 	unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);  in bitmap_copy()
275 		const unsigned long *src, unsigned int nbits)  in bitmap_copy_clear_tail()
283  * On 32-bit systems bitmaps are represented as u32 arrays internally. On LE64
287  * to out-of-bound access. To avoid that, both LE and BE variants of 64-bit
292 							unsigned int nbits);
294 							unsigned int nbits);
305  * On 64-bit systems bitmaps are represented as u64 arrays internally. So,
309 void bitmap_from_arr64(unsigned long *bitmap, const u64 *buf, unsigned int nbits);
310 void bitmap_to_arr64(u64 *buf, const unsigned long *bitmap, unsigned int nbits);
319 			const unsigned long *src2, unsigned int nbits)  in bitmap_and()
327 			const unsigned long *src2, unsigned int nbits)  in bitmap_or()
336 			const unsigned long *src2, unsigned int nbits)  in bitmap_xor()
345 			const unsigned long *src2, unsigned int nbits)  in bitmap_andnot()
353 			unsigned int nbits)  in bitmap_complement()
366 #define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1)
369 				const unsigned long *src2, unsigned int nbits)  in bitmap_equal()
380  * bitmap_or_equal - Check whether the or of two bitmaps is equal to a third
391 				   unsigned int nbits)  in bitmap_or_equal()
401 				     unsigned int nbits)  in bitmap_intersects()
410 				 const unsigned long *src2, unsigned int nbits)  in bitmap_subset()
426 static inline bool bitmap_full(const unsigned long *src, unsigned int nbits)  in bitmap_full()
435 unsigned int bitmap_weight(const unsigned long *src, unsigned int nbits)  in bitmap_weight()
444 				const unsigned long *src2, unsigned int nbits)  in bitmap_weight_and()
451 static __always_inline void bitmap_set(unsigned long *map, unsigned int start,  in bitmap_set()  argument
452 		unsigned int nbits)  in bitmap_set()
455 		__set_bit(start, map);  in bitmap_set()
457 		*map |= GENMASK(start + nbits - 1, start);  in bitmap_set()
462 		memset((char *)map + start / 8, 0xff, nbits / 8);  in bitmap_set()
464 		__bitmap_set(map, start, nbits);  in bitmap_set()
467 static __always_inline void bitmap_clear(unsigned long *map, unsigned int start,  in bitmap_clear()  argument
468 		unsigned int nbits)  in bitmap_clear()
471 		__clear_bit(start, map);  in bitmap_clear()
473 		*map &= ~GENMASK(start + nbits - 1, start);  in bitmap_clear()
478 		memset((char *)map + start / 8, 0, nbits / 8);  in bitmap_clear()
480 		__bitmap_clear(map, start, nbits);  in bitmap_clear()
484 				unsigned int shift, unsigned int nbits)  in bitmap_shift_right()
493 				unsigned int shift, unsigned int nbits)  in bitmap_shift_left()
504 				  const unsigned long *mask,  in bitmap_replace()  argument
505 				  unsigned int nbits)  in bitmap_replace()
508 		*dst = (*old & ~(*mask)) | (*new & *mask);  in bitmap_replace()
510 		__bitmap_replace(dst, old, new, mask, nbits);  in bitmap_replace()
514 					  unsigned int *rs, unsigned int *re,  in bitmap_next_set_region()
515 					  unsigned int end)  in bitmap_next_set_region()
522  * BITMAP_FROM_U64() - Represent u64 value in the format suitable for bitmap.
525  * Linux bitmaps are internally arrays of unsigned longs, i.e. 32-bit
526  * integers in 32-bit environment, and 64-bit integers in 64-bit one.
531  * On 64-bit kernels 64-bit LE and BE numbers are naturally ordered in
534  * On 32-bit kernels 32-bit LE ABI orders lo word of 64-bit number in memory
535  * prior to hi, and 32-bit BE orders hi word prior to lo. The bitmap on the
536  * other hand is represented as an array of 32-bit words and the position of
539  * It matches 32-bit LE ABI, and we can simply let the compiler store 64-bit
555  * bitmap_from_u64 - Check and swap words within u64.
556  *  @mask: source bitmap
559  * In 32-bit Big Endian kernel, when using ``(u32 *)(&val)[*]``
560  * to read u64 mask, we will get the wrong word.
562  * but we expect the lower 32-bits of u64.
564 static inline void bitmap_from_u64(unsigned long *dst, u64 mask)  in bitmap_from_u64()  argument
566 	bitmap_from_arr64(dst, &mask, 64);  in bitmap_from_u64()
570  * bitmap_get_value8 - get an 8-bit value within a memory region
571  * @map: address to the bitmap memory region
572  * @start: bit offset of the 8-bit value; must be a multiple of 8
574  * Returns the 8-bit value located at the @start bit offset within the @src
577 static inline unsigned long bitmap_get_value8(const unsigned long *map,  in bitmap_get_value8()  argument
583 	return (map[index] >> offset) & 0xFF;  in bitmap_get_value8()
587  * bitmap_set_value8 - set an 8-bit value within a memory region
588  * @map: address to the bitmap memory region
589  * @value: the 8-bit value; values wider than 8 bits may clobber bitmap
590  * @start: bit offset of the 8-bit value; must be a multiple of 8
592 static inline void bitmap_set_value8(unsigned long *map, unsigned long value,  in bitmap_set_value8()  argument
598 	map[index] &= ~(0xFFUL << offset);  in bitmap_set_value8()
599 	map[index] |= value << offset;  in bitmap_set_value8()