1 /* SPDX-License-Identifier: BSD-3-Clause */ 2 /* Copyright (c) 2020, 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_find_next_bit - Find the index of the next set bit of a bitmap 291 * @bitmap: the bitmap to scan 292 * @size: the size in bits of the bitmap 293 * @offset: the offset to start at 294 * 295 * Scans the bitmap and returns the index of the first set bit which is equal 296 * to or after the specified offset. Will return size if no bits are set. 297 */ 298 static inline u16 299 ice_find_next_bit(const ice_bitmap_t *bitmap, u16 size, u16 offset) 300 { 301 u16 i, j; 302 303 if (offset >= size) 304 return size; 305 306 /* Since the starting position may not be directly on a chunk 307 * boundary, we need to be careful to handle the first chunk specially 308 */ 309 i = BIT_CHUNK(offset); 310 if (bitmap[i] != 0) { 311 u16 off = i * BITS_PER_CHUNK; 312 313 for (j = offset % BITS_PER_CHUNK; j < BITS_PER_CHUNK; j++) { 314 if (ice_is_bit_set(bitmap, off + j)) 315 return min(size, (u16)(off + j)); 316 } 317 } 318 319 /* Now we handle the remaining chunks, if any */ 320 for (i++; i < BITS_TO_CHUNKS(size); i++) { 321 if (bitmap[i] != 0) { 322 u16 off = i * BITS_PER_CHUNK; 323 324 for (j = 0; j < BITS_PER_CHUNK; j++) { 325 if (ice_is_bit_set(bitmap, off + j)) 326 return min(size, (u16)(off + j)); 327 } 328 } 329 } 330 return size; 331 } 332 333 /** 334 * ice_find_first_bit - Find the index of the first set bit of a bitmap 335 * @bitmap: the bitmap to scan 336 * @size: the size in bits of the bitmap 337 * 338 * Scans the bitmap and returns the index of the first set bit. Will return 339 * size if no bits are set. 340 */ 341 static inline u16 ice_find_first_bit(const ice_bitmap_t *bitmap, u16 size) 342 { 343 return ice_find_next_bit(bitmap, size, 0); 344 } 345 346 /** 347 * ice_is_any_bit_set - Return true of any bit in the bitmap is set 348 * @bitmap: the bitmap to check 349 * @size: the size of the bitmap 350 * 351 * Equivalent to checking if ice_find_first_bit returns a value less than the 352 * bitmap size. 353 */ 354 static inline bool ice_is_any_bit_set(ice_bitmap_t *bitmap, u16 size) 355 { 356 return ice_find_first_bit(bitmap, size) < size; 357 } 358 359 /** 360 * ice_cp_bitmap - copy bitmaps. 361 * @dst: bitmap destination 362 * @src: bitmap to copy from 363 * @size: Size of the bitmaps in bits 364 * 365 * This function copy bitmap from src to dst. Note that this function assumes 366 * it is operating on a bitmap declared using ice_declare_bitmap. It will copy 367 * the entire last chunk even if this contains bits beyond the size. 368 */ 369 static inline void ice_cp_bitmap(ice_bitmap_t *dst, ice_bitmap_t *src, u16 size) 370 { 371 ice_memcpy(dst, src, BITS_TO_CHUNKS(size) * sizeof(ice_bitmap_t), 372 ICE_NONDMA_TO_NONDMA); 373 } 374 375 /** 376 * ice_cmp_bitmaps - compares two bitmaps. 377 * @bmp1: the bitmap to compare 378 * @bmp2: the bitmap to compare with bmp1 379 * @size: Size of the bitmaps in bits 380 * 381 * This function compares two bitmaps, and returns result as true or false. 382 */ 383 static inline bool 384 ice_cmp_bitmap(ice_bitmap_t *bmp1, ice_bitmap_t *bmp2, u16 size) 385 { 386 ice_bitmap_t mask; 387 u16 i; 388 389 /* Handle all but last chunk*/ 390 for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++) 391 if (bmp1[i] != bmp2[i]) 392 return false; 393 394 /* We want to only compare bits within the size.*/ 395 mask = LAST_CHUNK_MASK(size); 396 if ((bmp1[i] & mask) != (bmp2[i] & mask)) 397 return false; 398 399 return true; 400 } 401 402 #undef BIT_CHUNK 403 #undef BIT_IN_CHUNK 404 #undef LAST_CHUNK_BITS 405 #undef LAST_CHUNK_MASK 406 407 #endif /* _ICE_BITOPS_H_ */ 408