1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2001-2020 Intel Corporation
8 /* Define the size of the bitmap chunk */
9 typedef u32 ice_bitmap_t;
11 /* Number of bits per bitmap chunk */
12 #define BITS_PER_CHUNK (BITS_PER_BYTE * sizeof(ice_bitmap_t))
13 /* Determine which chunk a bit belongs in */
14 #define BIT_CHUNK(nr) ((nr) / BITS_PER_CHUNK)
15 /* How many chunks are required to store this many bits */
16 #define BITS_TO_CHUNKS(sz) DIVIDE_AND_ROUND_UP((sz), BITS_PER_CHUNK)
17 /* Which bit inside a chunk this bit corresponds to */
18 #define BIT_IN_CHUNK(nr) ((nr) % BITS_PER_CHUNK)
19 /* How many bits are valid in the last chunk, assumes nr > 0 */
20 #define LAST_CHUNK_BITS(nr) ((((nr) - 1) % BITS_PER_CHUNK) + 1)
21 /* Generate a bitmask of valid bits in the last chunk, assumes nr > 0 */
22 #define LAST_CHUNK_MASK(nr) (((ice_bitmap_t)~0) >> \
23 (BITS_PER_CHUNK - LAST_CHUNK_BITS(nr)))
25 #define ice_declare_bitmap(A, sz) \
26 ice_bitmap_t A[BITS_TO_CHUNKS(sz)]
28 static inline bool ice_is_bit_set_internal(u16 nr, const ice_bitmap_t *bitmap)
30 return !!(*bitmap & BIT(nr));
34 * If atomic version of the bitops are required, each specific OS
35 * implementation will need to implement OS/platform specific atomic
36 * version of the functions below:
38 * ice_clear_bit_internal
39 * ice_set_bit_internal
40 * ice_test_and_clear_bit_internal
41 * ice_test_and_set_bit_internal
43 * and define macro ICE_ATOMIC_BITOPS to overwrite the default non-atomic
46 static inline void ice_clear_bit_internal(u16 nr, ice_bitmap_t *bitmap)
51 static inline void ice_set_bit_internal(u16 nr, ice_bitmap_t *bitmap)
56 static inline bool ice_test_and_clear_bit_internal(u16 nr,
59 if (ice_is_bit_set_internal(nr, bitmap)) {
60 ice_clear_bit_internal(nr, bitmap);
66 static inline bool ice_test_and_set_bit_internal(u16 nr, ice_bitmap_t *bitmap)
68 if (ice_is_bit_set_internal(nr, bitmap))
71 ice_set_bit_internal(nr, bitmap);
76 * ice_is_bit_set - Check state of a bit in a bitmap
77 * @bitmap: the bitmap to check
78 * @nr: the bit to check
80 * Returns true if bit nr of bitmap is set. False otherwise. Assumes that nr
81 * is less than the size of the bitmap.
83 static inline bool ice_is_bit_set(const ice_bitmap_t *bitmap, u16 nr)
85 return ice_is_bit_set_internal(BIT_IN_CHUNK(nr),
86 &bitmap[BIT_CHUNK(nr)]);
90 * ice_clear_bit - Clear a bit in a bitmap
91 * @bitmap: the bitmap to change
92 * @nr: the bit to change
94 * Clears the bit nr in bitmap. Assumes that nr is less than the size of the
97 static inline void ice_clear_bit(u16 nr, ice_bitmap_t *bitmap)
99 ice_clear_bit_internal(BIT_IN_CHUNK(nr), &bitmap[BIT_CHUNK(nr)]);
103 * ice_set_bit - Set a bit in a bitmap
104 * @bitmap: the bitmap to change
105 * @nr: the bit to change
107 * Sets the bit nr in bitmap. Assumes that nr is less than the size of the
110 static inline void ice_set_bit(u16 nr, ice_bitmap_t *bitmap)
112 ice_set_bit_internal(BIT_IN_CHUNK(nr), &bitmap[BIT_CHUNK(nr)]);
116 * ice_test_and_clear_bit - Atomically clear a bit and return the old bit value
117 * @nr: the bit to change
118 * @bitmap: the bitmap to change
120 * Check and clear the bit nr in bitmap. Assumes that nr is less than the size
124 ice_test_and_clear_bit(u16 nr, ice_bitmap_t *bitmap)
126 return ice_test_and_clear_bit_internal(BIT_IN_CHUNK(nr),
127 &bitmap[BIT_CHUNK(nr)]);
131 * ice_test_and_set_bit - Atomically set a bit and return the old bit value
132 * @nr: the bit to change
133 * @bitmap: the bitmap to change
135 * Check and set the bit nr in bitmap. Assumes that nr is less than the size of
139 ice_test_and_set_bit(u16 nr, ice_bitmap_t *bitmap)
141 return ice_test_and_set_bit_internal(BIT_IN_CHUNK(nr),
142 &bitmap[BIT_CHUNK(nr)]);
145 /* ice_zero_bitmap - set bits of bitmap to zero.
146 * @bmp: bitmap to set zeros
147 * @size: Size of the bitmaps in bits
149 * Set all of the bits in a bitmap to zero. Note that this function assumes it
150 * operates on an ice_bitmap_t which was declared using ice_declare_bitmap. It
151 * will zero every bit in the last chunk, even if those bits are beyond the
154 static inline void ice_zero_bitmap(ice_bitmap_t *bmp, u16 size)
156 ice_memset(bmp, 0, BITS_TO_CHUNKS(size) * sizeof(ice_bitmap_t),
161 * ice_and_bitmap - bitwise AND 2 bitmaps and store result in dst bitmap
162 * @dst: Destination bitmap that receive the result of the operation
163 * @bmp1: The first bitmap to intersect
164 * @bmp2: The second bitmap to intersect wit the first
165 * @size: Size of the bitmaps in bits
167 * This function performs a bitwise AND on two "source" bitmaps of the same size
168 * and stores the result to "dst" bitmap. The "dst" bitmap must be of the same
169 * size as the "source" bitmaps to avoid buffer overflows. This function returns
170 * a non-zero value if at least one bit location from both "source" bitmaps is
174 ice_and_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
175 const ice_bitmap_t *bmp2, u16 size)
177 ice_bitmap_t res = 0, mask;
180 /* Handle all but the last chunk */
181 for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++) {
182 dst[i] = bmp1[i] & bmp2[i];
186 /* We want to take care not to modify any bits outside of the bitmap
187 * size, even in the destination bitmap. Thus, we won't directly
188 * assign the last bitmap, but instead use a bitmask to ensure we only
189 * modify bits which are within the size, and leave any bits above the
192 mask = LAST_CHUNK_MASK(size);
193 dst[i] = (dst[i] & ~mask) | ((bmp1[i] & bmp2[i]) & mask);
194 res |= dst[i] & mask;
200 * ice_or_bitmap - bitwise OR 2 bitmaps and store result in dst bitmap
201 * @dst: Destination bitmap that receive the result of the operation
202 * @bmp1: The first bitmap to intersect
203 * @bmp2: The second bitmap to intersect wit the first
204 * @size: Size of the bitmaps in bits
206 * This function performs a bitwise OR on two "source" bitmaps of the same size
207 * and stores the result to "dst" bitmap. The "dst" bitmap must be of the same
208 * size as the "source" bitmaps to avoid buffer overflows.
211 ice_or_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
212 const ice_bitmap_t *bmp2, u16 size)
217 /* Handle all but last chunk */
218 for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
219 dst[i] = bmp1[i] | bmp2[i];
221 /* We want to only OR bits within the size. Furthermore, we also do
222 * not want to modify destination bits which are beyond the specified
223 * size. Use a bitmask to ensure that we only modify the bits that are
224 * within the specified size.
226 mask = LAST_CHUNK_MASK(size);
227 dst[i] = (dst[i] & ~mask) | ((bmp1[i] | bmp2[i]) & mask);
231 * ice_xor_bitmap - bitwise XOR 2 bitmaps and store result in dst bitmap
232 * @dst: Destination bitmap that receive the result of the operation
233 * @bmp1: The first bitmap of XOR operation
234 * @bmp2: The second bitmap to XOR with the first
235 * @size: Size of the bitmaps in bits
237 * This function performs a bitwise XOR on two "source" bitmaps of the same size
238 * and stores the result to "dst" bitmap. The "dst" bitmap must be of the same
239 * size as the "source" bitmaps to avoid buffer overflows.
242 ice_xor_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
243 const ice_bitmap_t *bmp2, u16 size)
248 /* Handle all but last chunk */
249 for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
250 dst[i] = bmp1[i] ^ bmp2[i];
252 /* We want to only XOR bits within the size. Furthermore, we also do
253 * not want to modify destination bits which are beyond the specified
254 * size. Use a bitmask to ensure that we only modify the bits that are
255 * within the specified size.
257 mask = LAST_CHUNK_MASK(size);
258 dst[i] = (dst[i] & ~mask) | ((bmp1[i] ^ bmp2[i]) & mask);
262 * ice_andnot_bitmap - bitwise ANDNOT 2 bitmaps and result in dst bitmap
263 * @dst: Destination bitmap that receive the result of the operation
264 * @bmp1: The first bitmap of ANDNOT operation
265 * @bmp2: The second bitmap to ANDNOT operation
266 * @size: Size of the bitmaps in bits
268 * This function performs a bitwise ANDNOT on two "source" bitmaps of the same
269 * size, and stores the result to "dst" bitmap. The "dst" bitmap must be of the
270 * same size as the "source" bitmaps to avoid buffer overflows.
273 ice_andnot_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
274 const ice_bitmap_t *bmp2, u16 size)
279 /* Handle all but last chunk */
280 for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
281 dst[i] = bmp1[i] & ~bmp2[i];
283 /* We want to only clear bits within the size. Furthermore, we also do
284 * not want to modify destination bits which are beyond the specified
285 * size. Use a bitmask to ensure that we only modify the bits that are
286 * within the specified size.
288 mask = LAST_CHUNK_MASK(size);
289 dst[i] = (dst[i] & ~mask) | ((bmp1[i] & ~bmp2[i]) & mask);
293 * ice_find_next_bit - Find the index of the next set bit of a bitmap
294 * @bitmap: the bitmap to scan
295 * @size: the size in bits of the bitmap
296 * @offset: the offset to start at
298 * Scans the bitmap and returns the index of the first set bit which is equal
299 * to or after the specified offset. Will return size if no bits are set.
302 ice_find_next_bit(const ice_bitmap_t *bitmap, u16 size, u16 offset)
309 /* Since the starting position may not be directly on a chunk
310 * boundary, we need to be careful to handle the first chunk specially
312 i = BIT_CHUNK(offset);
313 if (bitmap[i] != 0) {
314 u16 off = i * BITS_PER_CHUNK;
316 for (j = offset % BITS_PER_CHUNK; j < BITS_PER_CHUNK; j++) {
317 if (ice_is_bit_set(bitmap, off + j))
318 return min(size, (u16)(off + j));
322 /* Now we handle the remaining chunks, if any */
323 for (i++; i < BITS_TO_CHUNKS(size); i++) {
324 if (bitmap[i] != 0) {
325 u16 off = i * BITS_PER_CHUNK;
327 for (j = 0; j < BITS_PER_CHUNK; j++) {
328 if (ice_is_bit_set(bitmap, off + j))
329 return min(size, (u16)(off + j));
337 * ice_find_first_bit - Find the index of the first set bit of a bitmap
338 * @bitmap: the bitmap to scan
339 * @size: the size in bits of the bitmap
341 * Scans the bitmap and returns the index of the first set bit. Will return
342 * size if no bits are set.
344 static inline u16 ice_find_first_bit(const ice_bitmap_t *bitmap, u16 size)
346 return ice_find_next_bit(bitmap, size, 0);
349 #define ice_for_each_set_bit(_bitpos, _addr, _maxlen) \
350 for ((_bitpos) = ice_find_first_bit((_addr), (_maxlen)); \
351 (_bitpos) < (_maxlen); \
352 (_bitpos) = ice_find_next_bit((_addr), (_maxlen), (_bitpos) + 1))
355 * ice_is_any_bit_set - Return true of any bit in the bitmap is set
356 * @bitmap: the bitmap to check
357 * @size: the size of the bitmap
359 * Equivalent to checking if ice_find_first_bit returns a value less than the
362 static inline bool ice_is_any_bit_set(ice_bitmap_t *bitmap, u16 size)
364 return ice_find_first_bit(bitmap, size) < size;
368 * ice_cp_bitmap - copy bitmaps.
369 * @dst: bitmap destination
370 * @src: bitmap to copy from
371 * @size: Size of the bitmaps in bits
373 * This function copy bitmap from src to dst. Note that this function assumes
374 * it is operating on a bitmap declared using ice_declare_bitmap. It will copy
375 * the entire last chunk even if this contains bits beyond the size.
377 static inline void ice_cp_bitmap(ice_bitmap_t *dst, ice_bitmap_t *src, u16 size)
379 ice_memcpy(dst, src, BITS_TO_CHUNKS(size) * sizeof(ice_bitmap_t),
380 ICE_NONDMA_TO_NONDMA);
384 * ice_bitmap_set - set a number of bits in bitmap from a starting position
385 * @dst: bitmap destination
386 * @pos: first bit position to set
387 * @num_bits: number of bits to set
389 * This function sets bits in a bitmap from pos to (pos + num_bits) - 1.
390 * Note that this function assumes it is operating on a bitmap declared using
391 * ice_declare_bitmap.
394 ice_bitmap_set(ice_bitmap_t *dst, u16 pos, u16 num_bits)
398 for (i = pos; i < pos + num_bits; i++)
403 * ice_bitmap_hweight - hamming weight of bitmap
404 * @bm: bitmap pointer
405 * @size: size of bitmap (in bits)
407 * This function determines the number of set bits in a bitmap.
408 * Note that this function assumes it is operating on a bitmap declared using
409 * ice_declare_bitmap.
412 ice_bitmap_hweight(ice_bitmap_t *bm, u16 size)
417 while (size > (bit = ice_find_next_bit(bm, size, bit))) {
426 * ice_cmp_bitmaps - compares two bitmaps.
427 * @bmp1: the bitmap to compare
428 * @bmp2: the bitmap to compare with bmp1
429 * @size: Size of the bitmaps in bits
431 * This function compares two bitmaps, and returns result as true or false.
434 ice_cmp_bitmap(ice_bitmap_t *bmp1, ice_bitmap_t *bmp2, u16 size)
439 /* Handle all but last chunk */
440 for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
441 if (bmp1[i] != bmp2[i])
444 /* We want to only compare bits within the size */
445 mask = LAST_CHUNK_MASK(size);
446 if ((bmp1[i] & mask) != (bmp2[i] & mask))
452 #endif /* _ICE_BITOPS_H_ */