drivers/net/ice/base/ice_bitops.h

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2001-2020 Intel Corporation
   3  */
   4
   5 #ifndef _ICE_BITOPS_H_
   6 #define _ICE_BITOPS_H_
   7
   8 /* Define the size of the bitmap chunk */
   9 typedef u32 ice_bitmap_t;
  10
  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)))
  24
  25 #define ice_declare_bitmap(A, sz) \
  26         ice_bitmap_t A[BITS_TO_CHUNKS(sz)]
  27
  28 static inline bool ice_is_bit_set_internal(u16 nr, const ice_bitmap_t *bitmap)
  29 {
  30         return !!(*bitmap & BIT(nr));
  31 }
  32
  33 /*
  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:
  37  *
  38  * ice_clear_bit_internal
  39  * ice_set_bit_internal
  40  * ice_test_and_clear_bit_internal
  41  * ice_test_and_set_bit_internal
  42  *
  43  * and define macro ICE_ATOMIC_BITOPS to overwrite the default non-atomic
  44  * implementation.
  45  */
  46 static inline void ice_clear_bit_internal(u16 nr, ice_bitmap_t *bitmap)
  47 {
  48         *bitmap &= ~BIT(nr);
  49 }
  50
  51 static inline void ice_set_bit_internal(u16 nr, ice_bitmap_t *bitmap)
  52 {
  53         *bitmap |= BIT(nr);
  54 }
  55
  56 static inline bool ice_test_and_clear_bit_internal(u16 nr,
  57                                                    ice_bitmap_t *bitmap)
  58 {
  59         if (ice_is_bit_set_internal(nr, bitmap)) {
  60                 ice_clear_bit_internal(nr, bitmap);
  61                 return true;
  62         }
  63         return false;
  64 }
  65
  66 static inline bool ice_test_and_set_bit_internal(u16 nr, ice_bitmap_t *bitmap)
  67 {
  68         if (ice_is_bit_set_internal(nr, bitmap))
  69                 return true;
  70
  71         ice_set_bit_internal(nr, bitmap);
  72         return false;
  73 }
  74
  75 /**
  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
  79  *
  80  * Returns true if bit nr of bitmap is set. False otherwise. Assumes that nr
  81  * is less than the size of the bitmap.
  82  */
  83 static inline bool ice_is_bit_set(const ice_bitmap_t *bitmap, u16 nr)
  84 {
  85         return ice_is_bit_set_internal(BIT_IN_CHUNK(nr),
  86                                        &bitmap[BIT_CHUNK(nr)]);
  87 }
  88
  89 /**
  90  * ice_clear_bit - Clear a bit in a bitmap
  91  * @bitmap: the bitmap to change
  92  * @nr: the bit to change
  93  *
  94  * Clears the bit nr in bitmap. Assumes that nr is less than the size of the
  95  * bitmap.
  96  */
  97 static inline void ice_clear_bit(u16 nr, ice_bitmap_t *bitmap)
  98 {
  99         ice_clear_bit_internal(BIT_IN_CHUNK(nr), &bitmap[BIT_CHUNK(nr)]);
 100 }
 101
 102 /**
 103  * ice_set_bit - Set a bit in a bitmap
 104  * @bitmap: the bitmap to change
 105  * @nr: the bit to change
 106  *
 107  * Sets the bit nr in bitmap. Assumes that nr is less than the size of the
 108  * bitmap.
 109  */
 110 static inline void ice_set_bit(u16 nr, ice_bitmap_t *bitmap)
 111 {
 112         ice_set_bit_internal(BIT_IN_CHUNK(nr), &bitmap[BIT_CHUNK(nr)]);
 113 }
 114
 115 /**
 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
 119  *
 120  * Check and clear the bit nr in bitmap. Assumes that nr is less than the size
 121  * of the bitmap.
 122  */
 123 static inline bool
 124 ice_test_and_clear_bit(u16 nr, ice_bitmap_t *bitmap)
 125 {
 126         return ice_test_and_clear_bit_internal(BIT_IN_CHUNK(nr),
 127                                                &bitmap[BIT_CHUNK(nr)]);
 128 }
 129
 130 /**
 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
 134  *
 135  * Check and set the bit nr in bitmap. Assumes that nr is less than the size of
 136  * the bitmap.
 137  */
 138 static inline bool
 139 ice_test_and_set_bit(u16 nr, ice_bitmap_t *bitmap)
 140 {
 141         return ice_test_and_set_bit_internal(BIT_IN_CHUNK(nr),
 142                                              &bitmap[BIT_CHUNK(nr)]);
 143 }
 144
 145 /* ice_zero_bitmap - set bits of bitmap to zero.
 146  * @bmp: bitmap to set zeros
 147  * @size: Size of the bitmaps in bits
 148  *
 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
 152  * size.
 153  */
 154 static inline void ice_zero_bitmap(ice_bitmap_t *bmp, u16 size)
 155 {
 156         ice_memset(bmp, 0, BITS_TO_CHUNKS(size) * sizeof(ice_bitmap_t),
 157                    ICE_NONDMA_MEM);
 158 }
 159
 160 /**
 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
 166  *
 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
 171  * non-zero.
 172  */
 173 static inline int
 174 ice_and_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
 175                const ice_bitmap_t *bmp2, u16 size)
 176 {
 177         ice_bitmap_t res = 0, mask;
 178         u16 i;
 179
 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];
 183                 res |= dst[i];
 184         }
 185
 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
 190          * size value alone.
 191          */
 192         mask = LAST_CHUNK_MASK(size);
 193         dst[i] = (dst[i] & ~mask) | ((bmp1[i] & bmp2[i]) & mask);
 194         res |= dst[i] & mask;
 195
 196         return res != 0;
 197 }
 198
 199 /**
 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
 205  *
 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.
 209  */
 210 static inline void
 211 ice_or_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
 212               const ice_bitmap_t *bmp2, u16 size)
 213 {
 214         ice_bitmap_t mask;
 215         u16 i;
 216
 217         /* Handle all but last chunk */
 218         for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
 219                 dst[i] = bmp1[i] | bmp2[i];
 220
 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.
 225          */
 226         mask = LAST_CHUNK_MASK(size);
 227         dst[i] = (dst[i] & ~mask) | ((bmp1[i] | bmp2[i]) & mask);
 228 }
 229
 230 /**
 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
 236  *
 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.
 240  */
 241 static inline void
 242 ice_xor_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
 243                const ice_bitmap_t *bmp2, u16 size)
 244 {
 245         ice_bitmap_t mask;
 246         u16 i;
 247
 248         /* Handle all but last chunk */
 249         for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
 250                 dst[i] = bmp1[i] ^ bmp2[i];
 251
 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.
 256          */
 257         mask = LAST_CHUNK_MASK(size);
 258         dst[i] = (dst[i] & ~mask) | ((bmp1[i] ^ bmp2[i]) & mask);
 259 }
 260
 261 /**
 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
 267  *
 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.
 271  */
 272 static inline void
 273 ice_andnot_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
 274                   const ice_bitmap_t *bmp2, u16 size)
 275 {
 276         ice_bitmap_t mask;
 277         u16 i;
 278
 279         /* Handle all but last chunk */
 280         for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
 281                 dst[i] = bmp1[i] & ~bmp2[i];
 282
 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.
 287          */
 288         mask = LAST_CHUNK_MASK(size);
 289         dst[i] = (dst[i] & ~mask) | ((bmp1[i] & ~bmp2[i]) & mask);
 290 }
 291
 292 /**
 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
 297  *
 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.
 300  */
 301 static inline u16
 302 ice_find_next_bit(const ice_bitmap_t *bitmap, u16 size, u16 offset)
 303 {
 304         u16 i, j;
 305
 306         if (offset >= size)
 307                 return size;
 308
 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
 311          */
 312         i = BIT_CHUNK(offset);
 313         if (bitmap[i] != 0) {
 314                 u16 off = i * BITS_PER_CHUNK;
 315
 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));
 319                 }
 320         }
 321
 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;
 326
 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));
 330                         }
 331                 }
 332         }
 333         return size;
 334 }
 335
 336 /**
 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
 340  *
 341  * Scans the bitmap and returns the index of the first set bit. Will return
 342  * size if no bits are set.
 343  */
 344 static inline u16 ice_find_first_bit(const ice_bitmap_t *bitmap, u16 size)
 345 {
 346         return ice_find_next_bit(bitmap, size, 0);
 347 }
 348
 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))
 353
 354 /**
 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
 358  *
 359  * Equivalent to checking if ice_find_first_bit returns a value less than the
 360  * bitmap size.
 361  */
 362 static inline bool ice_is_any_bit_set(ice_bitmap_t *bitmap, u16 size)
 363 {
 364         return ice_find_first_bit(bitmap, size) < size;
 365 }
 366
 367 /**
 368  * ice_cp_bitmap - copy bitmaps.
 369  * @dst: bitmap destination
 370  * @src: bitmap to copy from
 371  * @size: Size of the bitmaps in bits
 372  *
 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.
 376  */
 377 static inline void ice_cp_bitmap(ice_bitmap_t *dst, ice_bitmap_t *src, u16 size)
 378 {
 379         ice_memcpy(dst, src, BITS_TO_CHUNKS(size) * sizeof(ice_bitmap_t),
 380                    ICE_NONDMA_TO_NONDMA);
 381 }
 382
 383 /**
 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
 388  *
 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.
 392  */
 393 static inline void
 394 ice_bitmap_set(ice_bitmap_t *dst, u16 pos, u16 num_bits)
 395 {
 396         u16 i;
 397
 398         for (i = pos; i < pos + num_bits; i++)
 399                 ice_set_bit(i, dst);
 400 }
 401
 402 /**
 403  * ice_bitmap_hweight - hamming weight of bitmap
 404  * @bm: bitmap pointer
 405  * @size: size of bitmap (in bits)
 406  *
 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.
 410  */
 411 static inline int
 412 ice_bitmap_hweight(ice_bitmap_t *bm, u16 size)
 413 {
 414         int count = 0;
 415         u16 bit = 0;
 416
 417         while (size > (bit = ice_find_next_bit(bm, size, bit))) {
 418                 count++;
 419                 bit++;
 420         }
 421
 422         return count;
 423 }
 424
 425 /**
 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
 430  *
 431  * This function compares two bitmaps, and returns result as true or false.
 432  */
 433 static inline bool
 434 ice_cmp_bitmap(ice_bitmap_t *bmp1, ice_bitmap_t *bmp2, u16 size)
 435 {
 436         ice_bitmap_t mask;
 437         u16 i;
 438
 439         /* Handle all but last chunk */
 440         for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
 441                 if (bmp1[i] != bmp2[i])
 442                         return false;
 443
 444         /* We want to only compare bits within the size */
 445         mask = LAST_CHUNK_MASK(size);
 446         if ((bmp1[i] & mask) != (bmp2[i] & mask))
 447                 return false;
 448
 449         return true;
 450 }
 451
 452 /**
 453  * ice_bitmap_from_array32 - copies u32 array source into bitmap destination
 454  * @dst: the destination bitmap
 455  * @src: the source u32 array
 456  * @size: size of the bitmap (in bits)
 457  *
 458  * This function copies the src bitmap stored in an u32 array into the dst
 459  * bitmap stored as an ice_bitmap_t.
 460  */
 461 static inline void
 462 ice_bitmap_from_array32(ice_bitmap_t *dst, u32 *src, u16 size)
 463 {
 464         u32 remaining_bits, i;
 465
 466 #define BITS_PER_U32    (sizeof(u32) * BITS_PER_BYTE)
 467         /* clear bitmap so we only have to set when iterating */
 468         ice_zero_bitmap(dst, size);
 469
 470         for (i = 0; i < (u32)(size / BITS_PER_U32); i++) {
 471                 u32 bit_offset = i * BITS_PER_U32;
 472                 u32 entry = src[i];
 473                 u32 j;
 474
 475                 for (j = 0; j < BITS_PER_U32; j++) {
 476                         if (entry & BIT(j))
 477                                 ice_set_bit((u16)(j + bit_offset), dst);
 478                 }
 479         }
 480
 481         /* still need to check the leftover bits (i.e. if size isn't evenly
 482          * divisible by BITS_PER_U32
 483          **/
 484         remaining_bits = size % BITS_PER_U32;
 485         if (remaining_bits) {
 486                 u32 bit_offset = i * BITS_PER_U32;
 487                 u32 entry = src[i];
 488                 u32 j;
 489
 490                 for (j = 0; j < remaining_bits; j++) {
 491                         if (entry & BIT(j))
 492                                 ice_set_bit((u16)(j + bit_offset), dst);
 493                 }
 494         }
 495 }
 496
 497 #endif /* _ICE_BITOPS_H_ */