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