1 /* SPDX-License-Identifier: BSD-3-Clause */
2 /* Copyright (c) 2024, Intel Corporation
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 *
15 * 3. Neither the name of the Intel Corporation nor the names of its
16 * contributors may be used to endorse or promote products derived from
17 * this software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
23 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 #ifndef _ICE_BITOPS_H_
33 #define _ICE_BITOPS_H_
34
35 #include "ice_defs.h"
36 #include "ice_osdep.h"
37
38 /* Define the size of the bitmap chunk */
39 typedef u32 ice_bitmap_t;
40
41 /* NOTE!
42 * Do not use any of the functions declared in this file
43 * on memory that was not declared with ice_declare_bitmap.
44 * Not following this rule might cause issues like split
45 * locks.
46 */
47
48 /* Number of bits per bitmap chunk */
49 #define BITS_PER_CHUNK (BITS_PER_BYTE * sizeof(ice_bitmap_t))
50 /* Determine which chunk a bit belongs in */
51 #define BIT_CHUNK(nr) ((nr) / BITS_PER_CHUNK)
52 /* How many chunks are required to store this many bits */
53 #define BITS_TO_CHUNKS(sz) (((sz) + BITS_PER_CHUNK - 1) / BITS_PER_CHUNK)
54 /* Which bit inside a chunk this bit corresponds to */
55 #define BIT_IN_CHUNK(nr) ((nr) % BITS_PER_CHUNK)
56 /* How many bits are valid in the last chunk, assumes nr > 0 */
57 #define LAST_CHUNK_BITS(nr) ((((nr) - 1) % BITS_PER_CHUNK) + 1)
58 /* Generate a bitmask of valid bits in the last chunk, assumes nr > 0 */
59 #define LAST_CHUNK_MASK(nr) (((ice_bitmap_t)~0) >> \
60 (BITS_PER_CHUNK - LAST_CHUNK_BITS(nr)))
61
62 #define ice_declare_bitmap(A, sz) \
63 ice_bitmap_t A[BITS_TO_CHUNKS(sz)]
64
ice_is_bit_set_internal(u16 nr,const ice_bitmap_t * bitmap)65 static inline bool ice_is_bit_set_internal(u16 nr, const ice_bitmap_t *bitmap)
66 {
67 return !!(*bitmap & BIT(nr));
68 }
69
70 /*
71 * If atomic version of the bitops are required, each specific OS
72 * implementation will need to implement OS/platform specific atomic
73 * version of the functions below:
74 *
75 * ice_clear_bit_internal
76 * ice_set_bit_internal
77 * ice_test_and_clear_bit_internal
78 * ice_test_and_set_bit_internal
79 *
80 * and define macro ICE_ATOMIC_BITOPS to overwrite the default non-atomic
81 * implementation.
82 */
ice_clear_bit_internal(u16 nr,ice_bitmap_t * bitmap)83 static inline void ice_clear_bit_internal(u16 nr, ice_bitmap_t *bitmap)
84 {
85 *bitmap &= ~BIT(nr);
86 }
87
ice_set_bit_internal(u16 nr,ice_bitmap_t * bitmap)88 static inline void ice_set_bit_internal(u16 nr, ice_bitmap_t *bitmap)
89 {
90 *bitmap |= BIT(nr);
91 }
92
ice_test_and_clear_bit_internal(u16 nr,ice_bitmap_t * bitmap)93 static inline bool ice_test_and_clear_bit_internal(u16 nr,
94 ice_bitmap_t *bitmap)
95 {
96 if (ice_is_bit_set_internal(nr, bitmap)) {
97 ice_clear_bit_internal(nr, bitmap);
98 return true;
99 }
100 return false;
101 }
102
ice_test_and_set_bit_internal(u16 nr,ice_bitmap_t * bitmap)103 static inline bool ice_test_and_set_bit_internal(u16 nr, ice_bitmap_t *bitmap)
104 {
105 if (ice_is_bit_set_internal(nr, bitmap))
106 return true;
107
108 ice_set_bit_internal(nr, bitmap);
109 return false;
110 }
111
112 /**
113 * ice_is_bit_set - Check state of a bit in a bitmap
114 * @bitmap: the bitmap to check
115 * @nr: the bit to check
116 *
117 * Returns true if bit nr of bitmap is set. False otherwise. Assumes that nr
118 * is less than the size of the bitmap.
119 */
ice_is_bit_set(const ice_bitmap_t * bitmap,u16 nr)120 static inline bool ice_is_bit_set(const ice_bitmap_t *bitmap, u16 nr)
121 {
122 return ice_is_bit_set_internal(BIT_IN_CHUNK(nr),
123 &bitmap[BIT_CHUNK(nr)]);
124 }
125
126 /**
127 * ice_clear_bit - Clear a bit in a bitmap
128 * @bitmap: the bitmap to change
129 * @nr: the bit to change
130 *
131 * Clears the bit nr in bitmap. Assumes that nr is less than the size of the
132 * bitmap.
133 */
ice_clear_bit(u16 nr,ice_bitmap_t * bitmap)134 static inline void ice_clear_bit(u16 nr, ice_bitmap_t *bitmap)
135 {
136 ice_clear_bit_internal(BIT_IN_CHUNK(nr), &bitmap[BIT_CHUNK(nr)]);
137 }
138
139 /**
140 * ice_set_bit - Set a bit in a bitmap
141 * @bitmap: the bitmap to change
142 * @nr: the bit to change
143 *
144 * Sets the bit nr in bitmap. Assumes that nr is less than the size of the
145 * bitmap.
146 */
ice_set_bit(u16 nr,ice_bitmap_t * bitmap)147 static inline void ice_set_bit(u16 nr, ice_bitmap_t *bitmap)
148 {
149 ice_set_bit_internal(BIT_IN_CHUNK(nr), &bitmap[BIT_CHUNK(nr)]);
150 }
151
152 /**
153 * ice_test_and_clear_bit - Atomically clear a bit and return the old bit value
154 * @nr: the bit to change
155 * @bitmap: the bitmap to change
156 *
157 * Check and clear the bit nr in bitmap. Assumes that nr is less than the size
158 * of the bitmap.
159 */
160 static inline bool
ice_test_and_clear_bit(u16 nr,ice_bitmap_t * bitmap)161 ice_test_and_clear_bit(u16 nr, ice_bitmap_t *bitmap)
162 {
163 return ice_test_and_clear_bit_internal(BIT_IN_CHUNK(nr),
164 &bitmap[BIT_CHUNK(nr)]);
165 }
166
167 /**
168 * ice_test_and_set_bit - Atomically set a bit and return the old bit value
169 * @nr: the bit to change
170 * @bitmap: the bitmap to change
171 *
172 * Check and set the bit nr in bitmap. Assumes that nr is less than the size of
173 * the bitmap.
174 */
175 static inline bool
ice_test_and_set_bit(u16 nr,ice_bitmap_t * bitmap)176 ice_test_and_set_bit(u16 nr, ice_bitmap_t *bitmap)
177 {
178 return ice_test_and_set_bit_internal(BIT_IN_CHUNK(nr),
179 &bitmap[BIT_CHUNK(nr)]);
180 }
181
182 /* ice_zero_bitmap - set bits of bitmap to zero.
183 * @bmp: bitmap to set zeros
184 * @size: Size of the bitmaps in bits
185 *
186 * Set all of the bits in a bitmap to zero. Note that this function assumes it
187 * operates on an ice_bitmap_t which was declared using ice_declare_bitmap. It
188 * will zero every bit in the last chunk, even if those bits are beyond the
189 * size.
190 */
ice_zero_bitmap(ice_bitmap_t * bmp,u16 size)191 static inline void ice_zero_bitmap(ice_bitmap_t *bmp, u16 size)
192 {
193 ice_memset(bmp, 0, BITS_TO_CHUNKS(size) * sizeof(ice_bitmap_t),
194 ICE_NONDMA_MEM);
195 }
196
197 /**
198 * ice_and_bitmap - bitwise AND 2 bitmaps and store result in dst bitmap
199 * @dst: Destination bitmap that receive the result of the operation
200 * @bmp1: The first bitmap to intersect
201 * @bmp2: The second bitmap to intersect with the first
202 * @size: Size of the bitmaps in bits
203 *
204 * This function performs a bitwise AND on two "source" bitmaps of the same size
205 * and stores the result to "dst" bitmap. The "dst" bitmap must be of the same
206 * size as the "source" bitmaps to avoid buffer overflows. This function returns
207 * a non-zero value if at least one bit location from both "source" bitmaps is
208 * non-zero.
209 */
210 static inline int
ice_and_bitmap(ice_bitmap_t * dst,const ice_bitmap_t * bmp1,const ice_bitmap_t * bmp2,u16 size)211 ice_and_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
212 const ice_bitmap_t *bmp2, u16 size)
213 {
214 ice_bitmap_t res = 0, mask;
215 u16 i;
216
217 /* Handle all but the last chunk */
218 for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++) {
219 dst[i] = bmp1[i] & bmp2[i];
220 res |= dst[i];
221 }
222
223 /* We want to take care not to modify any bits outside of the bitmap
224 * size, even in the destination bitmap. Thus, we won't directly
225 * assign the last bitmap, but instead use a bitmask to ensure we only
226 * modify bits which are within the size, and leave any bits above the
227 * size value alone.
228 */
229 mask = LAST_CHUNK_MASK(size);
230 dst[i] = (dst[i] & ~mask) | ((bmp1[i] & bmp2[i]) & mask);
231 res |= dst[i] & mask;
232
233 return res != 0;
234 }
235
236 /**
237 * ice_or_bitmap - bitwise OR 2 bitmaps and store result in dst bitmap
238 * @dst: Destination bitmap that receive the result of the operation
239 * @bmp1: The first bitmap to intersect
240 * @bmp2: The second bitmap to intersect with the first
241 * @size: Size of the bitmaps in bits
242 *
243 * This function performs a bitwise OR on two "source" bitmaps of the same size
244 * and stores the result to "dst" bitmap. The "dst" bitmap must be of the same
245 * size as the "source" bitmaps to avoid buffer overflows.
246 */
247 static inline void
ice_or_bitmap(ice_bitmap_t * dst,const ice_bitmap_t * bmp1,const ice_bitmap_t * bmp2,u16 size)248 ice_or_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
249 const ice_bitmap_t *bmp2, u16 size)
250 {
251 ice_bitmap_t mask;
252 u16 i;
253
254 /* Handle all but last chunk */
255 for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
256 dst[i] = bmp1[i] | bmp2[i];
257
258 /* We want to only OR bits within the size. Furthermore, we also do
259 * not want to modify destination bits which are beyond the specified
260 * size. Use a bitmask to ensure that we only modify the bits that are
261 * within the specified size.
262 */
263 mask = LAST_CHUNK_MASK(size);
264 dst[i] = (dst[i] & ~mask) | ((bmp1[i] | bmp2[i]) & mask);
265 }
266
267 /**
268 * ice_xor_bitmap - bitwise XOR 2 bitmaps and store result in dst bitmap
269 * @dst: Destination bitmap that receive the result of the operation
270 * @bmp1: The first bitmap of XOR operation
271 * @bmp2: The second bitmap to XOR with the first
272 * @size: Size of the bitmaps in bits
273 *
274 * This function performs a bitwise XOR on two "source" bitmaps of the same size
275 * and stores the result to "dst" bitmap. The "dst" bitmap must be of the same
276 * size as the "source" bitmaps to avoid buffer overflows.
277 */
278 static inline void
ice_xor_bitmap(ice_bitmap_t * dst,const ice_bitmap_t * bmp1,const ice_bitmap_t * bmp2,u16 size)279 ice_xor_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
280 const ice_bitmap_t *bmp2, u16 size)
281 {
282 ice_bitmap_t mask;
283 u16 i;
284
285 /* Handle all but last chunk */
286 for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
287 dst[i] = bmp1[i] ^ bmp2[i];
288
289 /* We want to only XOR bits within the size. Furthermore, we also do
290 * not want to modify destination bits which are beyond the specified
291 * size. Use a bitmask to ensure that we only modify the bits that are
292 * within the specified size.
293 */
294 mask = LAST_CHUNK_MASK(size);
295 dst[i] = (dst[i] & ~mask) | ((bmp1[i] ^ bmp2[i]) & mask);
296 }
297
298 /**
299 * ice_andnot_bitmap - bitwise ANDNOT 2 bitmaps and result in dst bitmap
300 * @dst: Destination bitmap that receive the result of the operation
301 * @bmp1: The first bitmap of ANDNOT operation
302 * @bmp2: The second bitmap to ANDNOT operation
303 * @size: Size of the bitmaps in bits
304 *
305 * This function performs a bitwise ANDNOT on two "source" bitmaps of the same
306 * size, and stores the result to "dst" bitmap. The "dst" bitmap must be of the
307 * same size as the "source" bitmaps to avoid buffer overflows.
308 */
309 static inline void
ice_andnot_bitmap(ice_bitmap_t * dst,const ice_bitmap_t * bmp1,const ice_bitmap_t * bmp2,u16 size)310 ice_andnot_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
311 const ice_bitmap_t *bmp2, u16 size)
312 {
313 ice_bitmap_t mask;
314 u16 i;
315
316 /* Handle all but last chunk */
317 for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
318 dst[i] = bmp1[i] & ~bmp2[i];
319
320 /* We want to only clear bits within the size. Furthermore, we also do
321 * not want to modify destination bits which are beyond the specified
322 * size. Use a bitmask to ensure that we only modify the bits that are
323 * within the specified size.
324 */
325 mask = LAST_CHUNK_MASK(size);
326 dst[i] = (dst[i] & ~mask) | ((bmp1[i] & ~bmp2[i]) & mask);
327 }
328
329 /**
330 * ice_find_next_bit - Find the index of the next set bit of a bitmap
331 * @bitmap: the bitmap to scan
332 * @size: the size in bits of the bitmap
333 * @offset: the offset to start at
334 *
335 * Scans the bitmap and returns the index of the first set bit which is equal
336 * to or after the specified offset. Will return size if no bits are set.
337 */
338 static inline u16
ice_find_next_bit(const ice_bitmap_t * bitmap,u16 size,u16 offset)339 ice_find_next_bit(const ice_bitmap_t *bitmap, u16 size, u16 offset)
340 {
341 u16 i, j;
342
343 if (offset >= size)
344 return size;
345
346 /* Since the starting position may not be directly on a chunk
347 * boundary, we need to be careful to handle the first chunk specially
348 */
349 i = BIT_CHUNK(offset);
350 if (bitmap[i] != 0) {
351 u16 off = i * BITS_PER_CHUNK;
352
353 for (j = offset % BITS_PER_CHUNK; j < BITS_PER_CHUNK; j++) {
354 if (ice_is_bit_set(bitmap, off + j))
355 return min(size, (u16)(off + j));
356 }
357 }
358
359 /* Now we handle the remaining chunks, if any */
360 for (i++; i < BITS_TO_CHUNKS(size); i++) {
361 if (bitmap[i] != 0) {
362 u16 off = i * BITS_PER_CHUNK;
363
364 for (j = 0; j < BITS_PER_CHUNK; j++) {
365 if (ice_is_bit_set(bitmap, off + j))
366 return min(size, (u16)(off + j));
367 }
368 }
369 }
370 return size;
371 }
372
373 /**
374 * ice_find_first_bit - Find the index of the first set bit of a bitmap
375 * @bitmap: the bitmap to scan
376 * @size: the size in bits of the bitmap
377 *
378 * Scans the bitmap and returns the index of the first set bit. Will return
379 * size if no bits are set.
380 */
ice_find_first_bit(const ice_bitmap_t * bitmap,u16 size)381 static inline u16 ice_find_first_bit(const ice_bitmap_t *bitmap, u16 size)
382 {
383 return ice_find_next_bit(bitmap, size, 0);
384 }
385
386 #define ice_for_each_set_bit(_bitpos, _addr, _maxlen) \
387 for ((_bitpos) = ice_find_first_bit((_addr), (_maxlen)); \
388 (_bitpos) < (_maxlen); \
389 (_bitpos) = ice_find_next_bit((_addr), (_maxlen), (_bitpos) + 1))
390
391 /**
392 * ice_is_any_bit_set - Return true of any bit in the bitmap is set
393 * @bitmap: the bitmap to check
394 * @size: the size of the bitmap
395 *
396 * Equivalent to checking if ice_find_first_bit returns a value less than the
397 * bitmap size.
398 */
ice_is_any_bit_set(ice_bitmap_t * bitmap,u16 size)399 static inline bool ice_is_any_bit_set(ice_bitmap_t *bitmap, u16 size)
400 {
401 return ice_find_first_bit(bitmap, size) < size;
402 }
403
404 /**
405 * ice_cp_bitmap - copy bitmaps
406 * @dst: bitmap destination
407 * @src: bitmap to copy from
408 * @size: Size of the bitmaps in bits
409 *
410 * This function copy bitmap from src to dst. Note that this function assumes
411 * it is operating on a bitmap declared using ice_declare_bitmap. It will copy
412 * the entire last chunk even if this contains bits beyond the size.
413 */
ice_cp_bitmap(ice_bitmap_t * dst,ice_bitmap_t * src,u16 size)414 static inline void ice_cp_bitmap(ice_bitmap_t *dst, ice_bitmap_t *src, u16 size)
415 {
416 ice_memcpy(dst, src, BITS_TO_CHUNKS(size) * sizeof(ice_bitmap_t),
417 ICE_NONDMA_TO_NONDMA);
418 }
419
420 /**
421 * ice_bitmap_set - set a number of bits in bitmap from a starting position
422 * @dst: bitmap destination
423 * @pos: first bit position to set
424 * @num_bits: number of bits to set
425 *
426 * This function sets bits in a bitmap from pos to (pos + num_bits) - 1.
427 * Note that this function assumes it is operating on a bitmap declared using
428 * ice_declare_bitmap.
429 */
430 static inline void
ice_bitmap_set(ice_bitmap_t * dst,u16 pos,u16 num_bits)431 ice_bitmap_set(ice_bitmap_t *dst, u16 pos, u16 num_bits)
432 {
433 u16 i;
434
435 for (i = pos; i < pos + num_bits; i++)
436 ice_set_bit(i, dst);
437 }
438
439 /**
440 * ice_bitmap_hweight - hamming weight of bitmap
441 * @bm: bitmap pointer
442 * @size: size of bitmap (in bits)
443 *
444 * This function determines the number of set bits in a bitmap.
445 * Note that this function assumes it is operating on a bitmap declared using
446 * ice_declare_bitmap.
447 */
448 static inline u16
ice_bitmap_hweight(ice_bitmap_t * bm,u16 size)449 ice_bitmap_hweight(ice_bitmap_t *bm, u16 size)
450 {
451 u16 count = 0;
452 u16 bit = 0;
453
454 while (size > (bit = ice_find_next_bit(bm, size, bit))) {
455 count++;
456 bit++;
457 }
458
459 return count;
460 }
461
462 /**
463 * ice_cmp_bitmap - compares two bitmaps
464 * @bmp1: the bitmap to compare
465 * @bmp2: the bitmap to compare with bmp1
466 * @size: Size of the bitmaps in bits
467 *
468 * This function compares two bitmaps, and returns result as true or false.
469 */
470 static inline bool
ice_cmp_bitmap(ice_bitmap_t * bmp1,ice_bitmap_t * bmp2,u16 size)471 ice_cmp_bitmap(ice_bitmap_t *bmp1, ice_bitmap_t *bmp2, u16 size)
472 {
473 ice_bitmap_t mask;
474 u16 i;
475
476 /* Handle all but last chunk */
477 for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
478 if (bmp1[i] != bmp2[i])
479 return false;
480
481 /* We want to only compare bits within the size */
482 mask = LAST_CHUNK_MASK(size);
483 if ((bmp1[i] & mask) != (bmp2[i] & mask))
484 return false;
485
486 return true;
487 }
488
489 /**
490 * ice_bitmap_from_array32 - copies u32 array source into bitmap destination
491 * @dst: the destination bitmap
492 * @src: the source u32 array
493 * @size: size of the bitmap (in bits)
494 *
495 * This function copies the src bitmap stored in an u32 array into the dst
496 * bitmap stored as an ice_bitmap_t.
497 */
498 static inline void
ice_bitmap_from_array32(ice_bitmap_t * dst,u32 * src,u16 size)499 ice_bitmap_from_array32(ice_bitmap_t *dst, u32 *src, u16 size)
500 {
501 u32 remaining_bits, i;
502
503 #define BITS_PER_U32 (sizeof(u32) * BITS_PER_BYTE)
504 /* clear bitmap so we only have to set when iterating */
505 ice_zero_bitmap(dst, size);
506
507 for (i = 0; i < (u32)(size / BITS_PER_U32); i++) {
508 u32 bit_offset = i * BITS_PER_U32;
509 u32 entry = src[i];
510 u32 j;
511
512 for (j = 0; j < BITS_PER_U32; j++) {
513 if (entry & BIT(j))
514 ice_set_bit((u16)(j + bit_offset), dst);
515 }
516 }
517
518 /* still need to check the leftover bits (i.e. if size isn't evenly
519 * divisible by BITS_PER_U32
520 **/
521 remaining_bits = size % BITS_PER_U32;
522 if (remaining_bits) {
523 u32 bit_offset = i * BITS_PER_U32;
524 u32 entry = src[i];
525 u32 j;
526
527 for (j = 0; j < remaining_bits; j++) {
528 if (entry & BIT(j))
529 ice_set_bit((u16)(j + bit_offset), dst);
530 }
531 }
532 }
533
534 #undef BIT_CHUNK
535 #undef BIT_IN_CHUNK
536 #undef LAST_CHUNK_BITS
537 #undef LAST_CHUNK_MASK
538
539 #endif /* _ICE_BITOPS_H_ */
540