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 */ 39typedef 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 65static 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 */ 83static inline void ice_clear_bit_internal(u16 nr, ice_bitmap_t *bitmap) 84{ 85 *bitmap &= ~BIT(nr); 86} 87 88static inline void ice_set_bit_internal(u16 nr, ice_bitmap_t *bitmap) 89{ 90 *bitmap |= BIT(nr); 91} 92 93static 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 103static 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 */ 120static 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 */ 134static 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 */ 147static 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 */ 160static inline bool 161ice_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 */ 175static inline bool 176ice_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 */ 191static 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 */ 210static inline int 211ice_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 */ 247static inline void 248ice_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 */ 278static inline void 279ice_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 */ 309static inline void 310ice_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 */ 338static inline u16 339ice_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 */ 381static 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 */ 399static 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 */ 414static 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 */ 430static inline void 431ice_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 */ 448static inline int 449ice_bitmap_hweight(ice_bitmap_t *bm, u16 size) 450{ 451 int 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 */ 470static inline bool 471ice_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 */ 498static inline void 499ice_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