sys/dev/ice/ice_bitops.h

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