1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2001-2019
8 /* Define the size of the bitmap chunk */
9 typedef u32 ice_bitmap_t;
12 /* Number of bits per bitmap chunk */
13 #define BITS_PER_CHUNK (BITS_PER_BYTE * sizeof(ice_bitmap_t))
14 /* Determine which chunk a bit belongs in */
15 #define BIT_CHUNK(nr) ((nr) / BITS_PER_CHUNK)
16 /* How many chunks are required to store this many bits */
17 #define BITS_TO_CHUNKS(sz) DIVIDE_AND_ROUND_UP((sz), BITS_PER_CHUNK)
18 /* Which bit inside a chunk this bit corresponds to */
19 #define BIT_IN_CHUNK(nr) ((nr) % BITS_PER_CHUNK)
20 /* How many bits are valid in the last chunk, assumes nr > 0 */
21 #define LAST_CHUNK_BITS(nr) ((((nr) - 1) % BITS_PER_CHUNK) + 1)
22 /* Generate a bitmask of valid bits in the last chunk, assumes nr > 0 */
23 #define LAST_CHUNK_MASK(nr) (((ice_bitmap_t)~0) >> \
24 (BITS_PER_CHUNK - LAST_CHUNK_BITS(nr)))
26 #define ice_declare_bitmap(A, sz) \
27 ice_bitmap_t A[BITS_TO_CHUNKS(sz)]
29 static inline bool ice_is_bit_set_internal(u16 nr, const ice_bitmap_t *bitmap)
31 return !!(*bitmap & BIT(nr));
35 * If atomic version of the bitops are required, each specific OS
36 * implementation will need to implement OS/platform specific atomic
37 * version of the functions below:
39 * ice_clear_bit_internal
40 * ice_set_bit_internal
41 * ice_test_and_clear_bit_internal
42 * ice_test_and_set_bit_internal
44 * and define macro ICE_ATOMIC_BITOPS to overwrite the default non-atomic
47 static inline void ice_clear_bit_internal(u16 nr, ice_bitmap_t *bitmap)
52 static inline void ice_set_bit_internal(u16 nr, ice_bitmap_t *bitmap)
57 static inline bool ice_test_and_clear_bit_internal(u16 nr,
60 if (ice_is_bit_set_internal(nr, bitmap)) {
61 ice_clear_bit_internal(nr, bitmap);
67 static inline bool ice_test_and_set_bit_internal(u16 nr, ice_bitmap_t *bitmap)
69 if (ice_is_bit_set_internal(nr, bitmap))
72 ice_set_bit_internal(nr, bitmap);
77 * ice_is_bit_set - Check state of a bit in a bitmap
78 * @bitmap: the bitmap to check
79 * @nr: the bit to check
81 * Returns true if bit nr of bitmap is set. False otherwise. Assumes that nr
82 * is less than the size of the bitmap.
84 static inline bool ice_is_bit_set(const ice_bitmap_t *bitmap, u16 nr)
86 return ice_is_bit_set_internal(BIT_IN_CHUNK(nr),
87 &bitmap[BIT_CHUNK(nr)]);
91 * ice_clear_bit - Clear a bit in a bitmap
92 * @bitmap: the bitmap to change
93 * @nr: the bit to change
95 * Clears the bit nr in bitmap. Assumes that nr is less than the size of the
98 static inline void ice_clear_bit(u16 nr, ice_bitmap_t *bitmap)
100 ice_clear_bit_internal(BIT_IN_CHUNK(nr), &bitmap[BIT_CHUNK(nr)]);
104 * ice_set_bit - Set a bit in a bitmap
105 * @bitmap: the bitmap to change
106 * @nr: the bit to change
108 * Sets the bit nr in bitmap. Assumes that nr is less than the size of the
111 static inline void ice_set_bit(u16 nr, ice_bitmap_t *bitmap)
113 ice_set_bit_internal(BIT_IN_CHUNK(nr), &bitmap[BIT_CHUNK(nr)]);
117 * ice_test_and_clear_bit - Atomically clear a bit and return the old bit value
118 * @nr: the bit to change
119 * @bitmap: the bitmap to change
121 * Check and clear the bit nr in bitmap. Assumes that nr is less than the size
125 ice_test_and_clear_bit(u16 nr, ice_bitmap_t *bitmap)
127 return ice_test_and_clear_bit_internal(BIT_IN_CHUNK(nr),
128 &bitmap[BIT_CHUNK(nr)]);
132 * ice_test_and_set_bit - Atomically set a bit and return the old bit value
133 * @nr: the bit to change
134 * @bitmap: the bitmap to change
136 * Check and set the bit nr in bitmap. Assumes that nr is less than the size of
140 ice_test_and_set_bit(u16 nr, ice_bitmap_t *bitmap)
142 return ice_test_and_set_bit_internal(BIT_IN_CHUNK(nr),
143 &bitmap[BIT_CHUNK(nr)]);
146 /* ice_zero_bitmap - set bits of bitmap to zero.
147 * @bmp: bitmap to set zeros
148 * @size: Size of the bitmaps in bits
150 * Set all of the bits in a bitmap to zero. Note that this function assumes it
151 * operates on an ice_bitmap_t which was declared using ice_declare_bitmap. It
152 * will zero every bit in the last chunk, even if those bits are beyond the
155 static inline void ice_zero_bitmap(ice_bitmap_t *bmp, u16 size)
157 ice_memset(bmp, 0, BITS_TO_CHUNKS(size) * sizeof(ice_bitmap_t),
162 * ice_and_bitmap - bitwise AND 2 bitmaps and store result in dst bitmap
163 * @dst: Destination bitmap that receive the result of the operation
164 * @bmp1: The first bitmap to intersect
165 * @bmp2: The second bitmap to intersect wit the first
166 * @size: Size of the bitmaps in bits
168 * This function performs a bitwise AND on two "source" bitmaps of the same size
169 * and stores the result to "dst" bitmap. The "dst" bitmap must be of the same
170 * size as the "source" bitmaps to avoid buffer overflows. This function returns
171 * a non-zero value if at least one bit location from both "source" bitmaps is
175 ice_and_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
176 const ice_bitmap_t *bmp2, u16 size)
178 ice_bitmap_t res = 0, mask;
181 /* Handle all but the last chunk */
182 for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++) {
183 dst[i] = bmp1[i] & bmp2[i];
187 /* We want to take care not to modify any bits outside of the bitmap
188 * size, even in the destination bitmap. Thus, we won't directly
189 * assign the last bitmap, but instead use a bitmask to ensure we only
190 * modify bits which are within the size, and leave any bits above the
193 mask = LAST_CHUNK_MASK(size);
194 dst[i] = (dst[i] & ~mask) | ((bmp1[i] & bmp2[i]) & mask);
195 res |= dst[i] & mask;
201 * ice_or_bitmap - bitwise OR 2 bitmaps and store result in dst bitmap
202 * @dst: Destination bitmap that receive the result of the operation
203 * @bmp1: The first bitmap to intersect
204 * @bmp2: The second bitmap to intersect wit the first
205 * @size: Size of the bitmaps in bits
207 * This function performs a bitwise OR on two "source" bitmaps of the same size
208 * and stores the result to "dst" bitmap. The "dst" bitmap must be of the same
209 * size as the "source" bitmaps to avoid buffer overflows.
212 ice_or_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
213 const ice_bitmap_t *bmp2, u16 size)
218 /* Handle all but last chunk*/
219 for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
220 dst[i] = bmp1[i] | bmp2[i];
222 /* We want to only OR bits within the size. Furthermore, we also do
223 * not want to modify destination bits which are beyond the specified
224 * size. Use a bitmask to ensure that we only modify the bits that are
225 * within the specified size.
227 mask = LAST_CHUNK_MASK(size);
228 dst[i] = (dst[i] & ~mask) | ((bmp1[i] | bmp2[i]) & mask);
232 * ice_find_next_bit - Find the index of the next set bit of a bitmap
233 * @bitmap: the bitmap to scan
234 * @size: the size in bits of the bitmap
235 * @offset: the offset to start at
237 * Scans the bitmap and returns the index of the first set bit which is equal
238 * to or after the specified offset. Will return size if no bits are set.
241 ice_find_next_bit(const ice_bitmap_t *bitmap, u16 size, u16 offset)
248 /* Since the starting position may not be directly on a chunk
249 * boundary, we need to be careful to handle the first chunk specially
251 i = BIT_CHUNK(offset);
252 if (bitmap[i] != 0) {
253 u16 off = i * BITS_PER_CHUNK;
255 for (j = offset % BITS_PER_CHUNK; j < BITS_PER_CHUNK; j++) {
256 if (ice_is_bit_set(bitmap, off + j))
257 return min(size, (u16)(off + j));
261 /* Now we handle the remaining chunks, if any */
262 for (i++; i < BITS_TO_CHUNKS(size); i++) {
263 if (bitmap[i] != 0) {
264 u16 off = i * BITS_PER_CHUNK;
266 for (j = 0; j < BITS_PER_CHUNK; j++) {
267 if (ice_is_bit_set(bitmap, off + j))
268 return min(size, (u16)(off + j));
276 * ice_find_first_bit - Find the index of the first set bit of a bitmap
277 * @bitmap: the bitmap to scan
278 * @size: the size in bits of the bitmap
280 * Scans the bitmap and returns the index of the first set bit. Will return
281 * size if no bits are set.
283 static inline u16 ice_find_first_bit(const ice_bitmap_t *bitmap, u16 size)
285 return ice_find_next_bit(bitmap, size, 0);
289 * ice_is_any_bit_set - Return true of any bit in the bitmap is set
290 * @bitmap: the bitmap to check
291 * @size: the size of the bitmap
293 * Equivalent to checking if ice_find_first_bit returns a value less than the
296 static inline bool ice_is_any_bit_set(ice_bitmap_t *bitmap, u16 size)
298 return ice_find_first_bit(bitmap, size) < size;
302 * ice_cp_bitmap - copy bitmaps.
303 * @dst: bitmap destination
304 * @src: bitmap to copy from
305 * @size: Size of the bitmaps in bits
307 * This function copy bitmap from src to dst. Note that this function assumes
308 * it is operating on a bitmap declared using ice_declare_bitmap. It will copy
309 * the entire last chunk even if this contains bits beyond the size.
311 static inline void ice_cp_bitmap(ice_bitmap_t *dst, ice_bitmap_t *src, u16 size)
313 ice_memcpy(dst, src, BITS_TO_CHUNKS(size) * sizeof(ice_bitmap_t),
314 ICE_NONDMA_TO_NONDMA);
318 * ice_cmp_bitmaps - compares two bitmaps.
319 * @bmp1: the bitmap to compare
320 * @bmp2: the bitmap to compare with bmp1
321 * @size: Size of the bitmaps in bits
323 * This function compares two bitmaps, and returns result as true or false.
326 ice_cmp_bitmap(ice_bitmap_t *bmp1, ice_bitmap_t *bmp2, u16 size)
331 /* Handle all but last chunk*/
332 for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
333 if (bmp1[i] != bmp2[i])
336 /* We want to only compare bits within the size.*/
337 mask = LAST_CHUNK_MASK(size);
338 if ((bmp1[i] & mask) != (bmp2[i] & mask))
345 #endif /* _ICE_BITOPS_H_ */