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 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 */ 83 static inline void ice_clear_bit_internal(u16 nr, ice_bitmap_t *bitmap) 84 { 85 *bitmap &= ~BIT(nr); 86 } 87 88 static inline void ice_set_bit_internal(u16 nr, ice_bitmap_t *bitmap) 89 { 90 *bitmap |= BIT(nr); 91 } 92 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 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 */ 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 */ 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 */ 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 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 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 */ 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 wit 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 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 wit 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 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 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 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 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 */ 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 */ 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 */ 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 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 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 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 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