1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright(c) 2023 Ericsson AB 3 */ 4 5 #ifndef _RTE_BITSET_H_ 6 #define _RTE_BITSET_H_ 7 8 /** 9 * @file 10 * RTE Bitset 11 * 12 * This file provides functions and macros for querying and 13 * manipulating sets of bits kept in arrays of @c uint64_t-sized 14 * elements. 15 * 16 * The bits in a bitset are numbered from 0 to @c size - 1, with the 17 * lowest index being the least significant bit. 18 * 19 * The bitset array must be properly aligned. 20 * 21 * For optimal performance, the @c size parameter, required by 22 * many of the API's functions, should be a compile-time constant. 23 * 24 * For large bitsets, the rte_bitmap.h API may be more appropriate. 25 * 26 * @warning 27 * All functions modifying a bitset may overwrite any unused bits of 28 * the last word. Such unused bits are ignored by all functions reading 29 * bits. 30 * 31 */ 32 33 #include <limits.h> 34 #include <stdbool.h> 35 #include <stddef.h> 36 #include <stdint.h> 37 38 #include <rte_bitops.h> 39 #include <rte_branch_prediction.h> 40 #include <rte_common.h> 41 #include <rte_compat.h> 42 #include <rte_debug.h> 43 #include <rte_memcpy.h> 44 45 #ifdef __cplusplus 46 extern "C" { 47 #endif 48 49 /** 50 * The size (in bytes) of each element in the array used to represent 51 * a bitset. 52 */ 53 #define RTE_BITSET_WORD_SIZE (sizeof(uint64_t)) 54 55 /** 56 * The size (in bits) of each element in the array used to represent 57 * a bitset. 58 */ 59 #define RTE_BITSET_WORD_BITS (RTE_BITSET_WORD_SIZE * CHAR_BIT) 60 61 /** 62 * Computes the number of words required to store @c size bits. 63 */ 64 #define RTE_BITSET_NUM_WORDS(size) \ 65 ((size + RTE_BITSET_WORD_BITS - 1) / RTE_BITSET_WORD_BITS) 66 67 /** 68 * Computes the amount of memory (in bytes) required to fit a bitset 69 * holding @c size bits. 70 */ 71 #define RTE_BITSET_SIZE(size) \ 72 ((size_t)(RTE_BITSET_NUM_WORDS(size) * RTE_BITSET_WORD_SIZE)) 73 74 #define __RTE_BITSET_WORD_IDX(bit_num) ((bit_num) / RTE_BITSET_WORD_BITS) 75 #define __RTE_BITSET_BIT_OFFSET(bit_num) ((bit_num) % RTE_BITSET_WORD_BITS) 76 #define __RTE_BITSET_UNUSED(size) \ 77 ((RTE_BITSET_NUM_WORDS(size) * RTE_BITSET_WORD_BITS) - (size)) 78 #define __RTE_BITSET_USED_MASK(size) \ 79 (UINT64_MAX >> __RTE_BITSET_UNUSED(size)) 80 81 #define __RTE_BITSET_DELEGATE_N(fun, bitset, bit_num, ...) \ 82 fun(&(bitset)[__RTE_BITSET_WORD_IDX(bit_num)], __RTE_BITSET_BIT_OFFSET(bit_num), \ 83 __VA_ARGS__) 84 85 /* MSVC doesn't have ##__VA_ARGS__, so argument-less -> special case */ 86 #define __RTE_BITSET_DELEGATE(fun, bitset, bit_num) \ 87 fun(&(bitset)[__RTE_BITSET_WORD_IDX(bit_num)], __RTE_BITSET_BIT_OFFSET(bit_num)) 88 89 /** 90 * @warning 91 * @b EXPERIMENTAL: this API may change without prior notice. 92 * 93 * Declare a bitset. 94 * 95 * Declare (e.g., as a struct field) or define (e.g., as a stack 96 * variable) a bitset of the specified size. 97 * 98 * @param size 99 * The number of bits the bitset must be able to represent. Must be 100 * a compile-time constant. 101 * @param name 102 * The field or variable name of the resulting definition. 103 */ 104 #define RTE_BITSET_DECLARE(name, size) \ 105 uint64_t name[RTE_BITSET_NUM_WORDS(size)] 106 107 #define __RTE_BITSET_FOREACH_LEFT(var, size, start_bit, len) \ 108 ((len) - 1 - ((var) >= (start_bit) ? (var) - (start_bit) : (size) - (start_bit) + (var))) 109 110 #define __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, flags) \ 111 for ((var) = __rte_bitset_find(bitset, size, start_bit, len, flags); \ 112 (var) != -1; \ 113 (var) = __RTE_BITSET_FOREACH_LEFT(var, size, start_bit, len) > 0 ? \ 114 __rte_bitset_find(bitset, size, ((var) + 1) % (size), \ 115 __RTE_BITSET_FOREACH_LEFT(var, size, start_bit, len), flags) : -1) 116 117 /** 118 * @warning 119 * @b EXPERIMENTAL: this API may change without prior notice. 120 * 121 * Iterate over all bits set. 122 * 123 * This macro iterates over all bits set (i.e., all ones) in the 124 * bitset, in the forward direction (i.e., starting with the least 125 * significant '1'). 126 * 127 * @param var 128 * An iterator variable of type @c ssize_t. For each successive 129 * iteration, this variable will hold the bit index of a set bit. 130 * @param bitset 131 * A <tt>const uint64_t *</tt> pointer to the bitset array. 132 * @param size 133 * The size of the bitset (in bits). 134 */ 135 #define RTE_BITSET_FOREACH_SET(var, bitset, size) \ 136 __RTE_BITSET_FOREACH(var, bitset, size, 0, size, 0) 137 138 /** 139 * @warning 140 * @b EXPERIMENTAL: this API may change without prior notice. 141 * 142 * Iterate over all bits cleared. 143 * 144 * This macro iterates over all bits cleared in the bitset, in the 145 * forward direction (i.e., starting with the lowest-indexed set bit). 146 * 147 * @param var 148 * An iterator variable of type @c ssize_t. For each successive iteration, 149 * this variable will hold the bit index of a cleared bit. 150 * @param bitset 151 * A <tt>const uint64_t *</tt> pointer to the bitset array. 152 * @param size 153 * The size of the bitset (in bits). 154 */ 155 #define RTE_BITSET_FOREACH_CLEAR(var, bitset, size) \ 156 __RTE_BITSET_FOREACH(var, bitset, size, 0, size, __RTE_BITSET_FIND_FLAG_FIND_CLEAR) 157 158 /** 159 * @warning 160 * @b EXPERIMENTAL: this API may change without prior notice. 161 * 162 * Iterate over all bits set within a range. 163 * 164 * This macro iterates over all bits set (i.e., all ones) in the 165 * specified range, in the forward direction (i.e., starting with the 166 * least significant '1'). 167 * 168 * @param var 169 * An iterator variable of type @c ssize_t. For each successive iteration, 170 * this variable will hold the bit index of a set bit. 171 * @param bitset 172 * A <tt>const uint64_t *</tt> pointer to the bitset array. 173 * @param size 174 * The size of the bitset (in bits). 175 * @param start_bit 176 * The index of the first bit to check. Must be less than @c size. 177 * @param len 178 * The length (in bits) of the range. @c start_bit + @c len must be less 179 * than or equal to @c size. 180 */ 181 #define RTE_BITSET_FOREACH_SET_RANGE(var, bitset, size, start_bit, len) \ 182 __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, 0) 183 184 /** 185 * @warning 186 * @b EXPERIMENTAL: this API may change without prior notice. 187 * 188 * Iterate over all cleared bits within a range. 189 * 190 * This macro iterates over all bits cleared (i.e., all zeroes) in the 191 * specified range, in the forward direction (i.e., starting with the 192 * least significant '0'). 193 * 194 * @param var 195 * An iterator variable of type @c ssize_t. For each successive iteration, 196 * this variable will hold the bit index of a set bit. 197 * @param bitset 198 * A <tt>const uint64_t *</tt> pointer to the bitset array. 199 * @param size 200 * The size of the bitset (in bits). 201 * @param start_bit 202 * The index of the first bit to check. Must be less than @c size. 203 * @param len 204 * The length (in bits) of the range. @c start_bit + @c len must be less 205 * than or equal to @c size. 206 */ 207 #define RTE_BITSET_FOREACH_CLEAR_RANGE(var, bitset, size, start_bit, len) \ 208 __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, __RTE_BITSET_FIND_FLAG_FIND_CLEAR) 209 210 #define RTE_BITSET_FOREACH_SET_WRAP(var, bitset, size, start_bit, len) \ 211 __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, __RTE_BITSET_FIND_FLAG_WRAP) 212 213 #define RTE_BITSET_FOREACH_CLEAR_WRAP(var, bitset, size, start_bit, len) \ 214 __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, \ 215 __RTE_BITSET_FIND_FLAG_WRAP | __RTE_BITSET_FIND_FLAG_FIND_CLEAR) 216 217 /** 218 * @warning 219 * @b EXPERIMENTAL: this API may change without prior notice. 220 * 221 * Initializes a bitset. 222 * 223 * All bits are cleared. 224 * 225 * In case all words in the bitset array are already set to zero by 226 * other means (e.g., at the time of memory allocation), this function 227 * need not be called. 228 * 229 * @param bitset 230 * A pointer to the array of bitset 64-bit words. 231 * @param size 232 * The size of the bitset (in bits). 233 */ 234 __rte_experimental 235 static inline void 236 rte_bitset_init(uint64_t *bitset, size_t size) 237 { 238 memset(bitset, 0, RTE_BITSET_SIZE(size)); 239 } 240 241 /** 242 * @warning 243 * @b EXPERIMENTAL: this API may change without prior notice. 244 * 245 * Test if a bit is set. 246 * 247 * @param bitset 248 * A pointer to the array of words making up the bitset. 249 * @param bit_num 250 * Index of the bit to test. Index 0 is the least significant bit. 251 * @return 252 * Returns true if the bit is '1', and false if the bit is '0'. 253 */ 254 __rte_experimental 255 static inline bool 256 rte_bitset_test(const uint64_t *bitset, size_t bit_num) 257 { 258 #ifdef ALLOW_EXPERIMENTAL_API 259 return __RTE_BITSET_DELEGATE(rte_bit_test, bitset, bit_num); 260 #else 261 RTE_SET_USED(bitset); 262 RTE_SET_USED(bit_num); 263 RTE_VERIFY(false); 264 #endif 265 } 266 267 /** 268 * @warning 269 * @b EXPERIMENTAL: this API may change without prior notice. 270 * 271 * Set a bit in the bitset. 272 * 273 * Bits are numbered from 0 to (size - 1) (inclusive). 274 * 275 * The operation is not guaranteed to be atomic. 276 * 277 * @param bitset 278 * A pointer to the array of words making up the bitset. 279 * @param bit_num 280 * The index of the bit to be set. 281 */ 282 __rte_experimental 283 static inline void 284 rte_bitset_set(uint64_t *bitset, size_t bit_num) 285 { 286 #ifdef ALLOW_EXPERIMENTAL_API 287 __RTE_BITSET_DELEGATE(rte_bit_set, bitset, bit_num); 288 #else 289 RTE_SET_USED(bitset); 290 RTE_SET_USED(bit_num); 291 RTE_VERIFY(false); 292 #endif 293 } 294 295 /** 296 * @warning 297 * @b EXPERIMENTAL: this API may change without prior notice. 298 * 299 * Clear a bit in the bitset. 300 * 301 * Bits are numbered 0 to (size - 1) (inclusive). 302 * 303 * The operation is not guaranteed to be atomic. 304 * 305 * @param bitset 306 * A pointer to the array of words making up the bitset. 307 * @param bit_num 308 * The index of the bit to be cleared. 309 */ 310 __rte_experimental 311 static inline void 312 rte_bitset_clear(uint64_t *bitset, size_t bit_num) 313 { 314 #ifdef ALLOW_EXPERIMENTAL_API 315 __RTE_BITSET_DELEGATE(rte_bit_clear, bitset, bit_num); 316 #else 317 RTE_SET_USED(bitset); 318 RTE_SET_USED(bit_num); 319 RTE_VERIFY(false); 320 #endif 321 } 322 323 /** 324 * @warning 325 * @b EXPERIMENTAL: this API may change without prior notice. 326 * 327 * Set or clear a bit in the bitset. 328 * 329 * Bits are numbered 0 to (size - 1) (inclusive). 330 * 331 * The operation is not guaranteed to be atomic. 332 * 333 * @param bitset 334 * A pointer to the array of words making up the bitset. 335 * @param bit_num 336 * The index of the bit to be set or cleared. 337 * @param bit_value 338 * Control if the bit should be set or cleared. 339 */ 340 __rte_experimental 341 static inline void 342 rte_bitset_assign(uint64_t *bitset, size_t bit_num, bool bit_value) 343 { 344 #ifdef ALLOW_EXPERIMENTAL_API 345 __RTE_BITSET_DELEGATE_N(rte_bit_assign, bitset, bit_num, bit_value); 346 #else 347 RTE_SET_USED(bitset); 348 RTE_SET_USED(bit_num); 349 RTE_SET_USED(bit_value); 350 RTE_VERIFY(false); 351 #endif 352 } 353 354 /** 355 * @warning 356 * @b EXPERIMENTAL: this API may change without prior notice. 357 * 358 * Change the value of a bit in the bitset. 359 * 360 * Bits are numbered 0 to (size - 1) (inclusive). 361 * 362 * The operation is not guaranteed to be atomic. 363 * 364 * @param bitset 365 * A pointer to the array of words making up the bitset. 366 * @param bit_num 367 * The index of the bit to be flipped. 368 */ 369 __rte_experimental 370 static inline void 371 rte_bitset_flip(uint64_t *bitset, size_t bit_num) 372 { 373 #ifdef ALLOW_EXPERIMENTAL_API 374 __RTE_BITSET_DELEGATE(rte_bit_flip, bitset, bit_num); 375 #else 376 RTE_SET_USED(bitset); 377 RTE_SET_USED(bit_num); 378 RTE_VERIFY(false); 379 #endif 380 } 381 382 /** 383 * @warning 384 * @b EXPERIMENTAL: this API may change without prior notice. 385 * 386 * Atomically test if a bit is set. 387 * 388 * Atomically test if a bit in a bitset is set with the specified 389 * memory ordering. 390 * 391 * @param bitset 392 * A pointer to the array of words making up the bitset. 393 * @param bit_num 394 * Index of the bit to test. Index 0 is the least significant bit. 395 * @param memory_order 396 * The memory order to use. 397 * @return 398 * Returns true if the bit is '1', and false if the bit is '0'. 399 */ 400 __rte_experimental 401 static inline bool 402 rte_bitset_atomic_test(const uint64_t *bitset, size_t bit_num, int memory_order) 403 { 404 #ifdef ALLOW_EXPERIMENTAL_API 405 return __RTE_BITSET_DELEGATE_N(rte_bit_atomic_test, bitset, bit_num, memory_order); 406 #else 407 RTE_SET_USED(bitset); 408 RTE_SET_USED(bit_num); 409 RTE_SET_USED(memory_order); 410 RTE_VERIFY(false); 411 #endif 412 } 413 414 /** 415 * @warning 416 * @b EXPERIMENTAL: this API may change without prior notice. 417 * 418 * Atomically set a bit in the bitset. 419 * 420 * Set a bit in a bitset as an atomic operation, with the specified 421 * memory ordering. 422 * 423 * rte_bitset_atomic_set() is multi-thread safe, provided all threads 424 * acting in parallel on the same bitset does so through 425 * @c rte_bitset_atomic_*() functions. 426 * 427 * Bits are numbered from 0 to (size - 1) (inclusive). 428 * 429 * @param bitset 430 * A pointer to the array of words making up the bitset. 431 * @param bit_num 432 * The index of the bit to be set. 433 * @param memory_order 434 * The memory order to use. 435 */ 436 __rte_experimental 437 static inline void 438 rte_bitset_atomic_set(uint64_t *bitset, size_t bit_num, int memory_order) 439 { 440 #ifdef ALLOW_EXPERIMENTAL_API 441 __RTE_BITSET_DELEGATE_N(rte_bit_atomic_set, bitset, bit_num, memory_order); 442 #else 443 RTE_SET_USED(bitset); 444 RTE_SET_USED(bit_num); 445 RTE_SET_USED(memory_order); 446 RTE_VERIFY(false); 447 #endif 448 } 449 450 /** 451 * @warning 452 * @b EXPERIMENTAL: this API may change without prior notice. 453 * 454 * Atomically clear a bit in the bitset. 455 * 456 * Clear a bit in a bitset as an atomic operation, with the specified 457 * memory ordering. 458 * 459 * rte_bitset_atomic_clear() is multi-thread safe, provided all 460 * threads acting in parallel on the same bitset does so through @c 461 * rte_bitset_atomic_*() functions. 462 * 463 * Bits are numbered from 0 to (size - 1) (inclusive). 464 * 465 * @param bitset 466 * A pointer to the array of words making up the bitset. 467 * @param bit_num 468 * The index of the bit to be cleared. 469 * @param memory_order 470 * The memory order to use. 471 */ 472 __rte_experimental 473 static inline void 474 rte_bitset_atomic_clear(uint64_t *bitset, size_t bit_num, int memory_order) 475 { 476 #ifdef ALLOW_EXPERIMENTAL_API 477 __RTE_BITSET_DELEGATE_N(rte_bit_atomic_clear, bitset, bit_num, memory_order); 478 #else 479 RTE_SET_USED(bitset); 480 RTE_SET_USED(bit_num); 481 RTE_SET_USED(memory_order); 482 RTE_VERIFY(false); 483 #endif 484 } 485 486 /** 487 * @warning 488 * @b EXPERIMENTAL: this API may change without prior notice. 489 * 490 * Atomically set or clear a bit in the bitset. 491 * 492 * Assign a value to a bit in a bitset as an atomic operation, with 493 * the specified memory ordering. 494 * 495 * rte_bitset_atomic_assign() is multi-thread safe, provided all 496 * threads acting in parallel on the same bitset does so through 497 * @c rte_bitset_atomic_*() functions. 498 * 499 * Bits are numbered from 0 to (size - 1) (inclusive). 500 * 501 * @param bitset 502 * A pointer to the array of words making up the bitset. 503 * @param bit_num 504 * The index of the bit to be set or cleared. 505 * @param bit_value 506 * Control if the bit should be set or cleared. 507 * @param memory_order 508 * The memory order to use. 509 */ 510 __rte_experimental 511 static inline void 512 rte_bitset_atomic_assign(uint64_t *bitset, size_t bit_num, bool bit_value, int memory_order) 513 { 514 #ifdef ALLOW_EXPERIMENTAL_API 515 __RTE_BITSET_DELEGATE_N(rte_bit_atomic_assign, bitset, bit_num, bit_value, memory_order); 516 #else 517 RTE_SET_USED(bitset); 518 RTE_SET_USED(bit_num); 519 RTE_SET_USED(bit_value); 520 RTE_SET_USED(memory_order); 521 RTE_VERIFY(false); 522 #endif 523 } 524 525 /** 526 * @warning 527 * @b EXPERIMENTAL: this API may change without prior notice. 528 * 529 * Atomically change the value of a bit in the bitset. 530 * 531 * Flip a bit in a bitset as an atomic operation, with the specified 532 * memory ordering. 533 * 534 * rte_bitset_atomic_flip() is multi-thread safe, provided all threads 535 * acting in parallel on the same bitset does so through 536 * @c rte_bitset_atomic_*() functions. 537 * 538 * Bits are numbered from 0 to (size - 1) (inclusive). 539 * 540 * @param bitset 541 * A pointer to the array of words making up the bitset. 542 * @param bit_num 543 * The index of the bit to be flipped. 544 * @param memory_order 545 * The memory order to use. 546 */ 547 __rte_experimental 548 static inline void 549 rte_bitset_atomic_flip(uint64_t *bitset, size_t bit_num, int memory_order) 550 { 551 #ifdef ALLOW_EXPERIMENTAL_API 552 __RTE_BITSET_DELEGATE_N(rte_bit_atomic_flip, bitset, bit_num, memory_order); 553 #else 554 RTE_SET_USED(bitset); 555 RTE_SET_USED(bit_num); 556 RTE_SET_USED(memory_order); 557 RTE_VERIFY(false); 558 #endif 559 } 560 561 /** 562 * @warning 563 * @b EXPERIMENTAL: this API may change without prior notice. 564 * 565 * Set all bits in the bitset. 566 * 567 * @param bitset 568 * A pointer to the array of words making up the bitset. 569 * @param size 570 * The size of the bitset (in bits). 571 */ 572 __rte_experimental 573 static inline void 574 rte_bitset_set_all(uint64_t *bitset, size_t size) 575 { 576 memset(bitset, 0xFF, RTE_BITSET_SIZE(size)); 577 } 578 579 /** 580 * @warning 581 * @b EXPERIMENTAL: this API may change without prior notice. 582 * 583 * Clear all bits in the bitset. 584 * 585 * @param bitset 586 * A pointer to the array of words making up the bitset. 587 * @param size 588 * The size of the bitset (in bits). 589 */ 590 __rte_experimental 591 static inline void 592 rte_bitset_clear_all(uint64_t *bitset, size_t size) 593 { 594 #ifdef ALLOW_EXPERIMENTAL_API 595 rte_bitset_init(bitset, size); 596 #else 597 RTE_SET_USED(bitset); 598 RTE_SET_USED(size); 599 RTE_VERIFY(false); 600 #endif 601 } 602 603 /** 604 * @warning 605 * @b EXPERIMENTAL: this API may change without prior notice. 606 * 607 * Count all set bits (also known as the @e weight). 608 * 609 * @param bitset 610 * A pointer to the array of words making up the bitset. 611 * @param size 612 * The size of the bitset (in bits). 613 * @return 614 * Returns the number of '1' bits in the bitset. 615 */ 616 __rte_experimental 617 static inline size_t 618 rte_bitset_count_set(const uint64_t *bitset, size_t size) 619 { 620 size_t i; 621 size_t total = 0; 622 623 /* 624 * Unused bits in a rte_bitset are always '0', and thus are 625 * not included in this count. 626 */ 627 for (i = 0; i < RTE_BITSET_NUM_WORDS(size) - 1; i++) 628 total += rte_popcount64(bitset[i]); 629 630 total += rte_popcount64(bitset[i] & __RTE_BITSET_USED_MASK(size)); 631 632 return total; 633 } 634 635 /** 636 * @warning 637 * @b EXPERIMENTAL: this API may change without prior notice. 638 * 639 * Count all cleared bits. 640 * 641 * @param bitset 642 * A pointer to the array of words making up the bitset. 643 * @param size 644 * The size of the bitset (in bits). 645 * @return 646 * Returns the number of '0' bits in the bitset. 647 */ 648 __rte_experimental 649 static inline size_t 650 rte_bitset_count_clear(const uint64_t *bitset, size_t size) 651 { 652 #ifdef ALLOW_EXPERIMENTAL_API 653 return size - rte_bitset_count_set(bitset, size); 654 #else 655 RTE_SET_USED(bitset); 656 RTE_SET_USED(size); 657 RTE_VERIFY(false); 658 #endif 659 } 660 661 #define __RTE_BITSET_FIND_FLAG_FIND_CLEAR (1U << 0) 662 #define __RTE_BITSET_FIND_FLAG_WRAP (1U << 1) 663 664 __rte_experimental 665 static inline ssize_t 666 __rte_bitset_find_nowrap(const uint64_t *bitset, size_t __rte_unused size, size_t start_bit, 667 size_t len, bool find_clear) 668 { 669 size_t word_idx; 670 size_t offset; 671 size_t end_bit = start_bit + len; 672 673 RTE_ASSERT(end_bit <= size); 674 675 if (unlikely(len == 0)) 676 return -1; 677 678 word_idx = __RTE_BITSET_WORD_IDX(start_bit); 679 offset = __RTE_BITSET_BIT_OFFSET(start_bit); 680 681 while (word_idx <= __RTE_BITSET_WORD_IDX(end_bit - 1)) { 682 uint64_t word; 683 684 word = bitset[word_idx]; 685 if (find_clear) 686 word = ~word; 687 688 word >>= offset; 689 690 if (word != 0) { 691 size_t ffs = start_bit + rte_bsf64(word); 692 693 /* 694 * Check if set bit were among the last, 695 * unused bits, in the last word. 696 */ 697 if (unlikely(ffs >= end_bit)) 698 return -1; 699 700 return ffs; 701 } 702 703 start_bit += (RTE_BITSET_WORD_BITS - offset); 704 word_idx++; 705 offset = 0; 706 } 707 708 return -1; 709 710 } 711 712 __rte_experimental 713 static inline ssize_t 714 __rte_bitset_find(const uint64_t *bitset, size_t size, size_t start_bit, size_t len, 715 unsigned int flags) 716 { 717 #ifdef ALLOW_EXPERIMENTAL_API 718 bool find_clear = flags & __RTE_BITSET_FIND_FLAG_FIND_CLEAR; 719 bool may_wrap = flags & __RTE_BITSET_FIND_FLAG_WRAP; 720 bool does_wrap = (start_bit + len) > size; 721 ssize_t rc; 722 723 RTE_ASSERT(len <= size); 724 if (!may_wrap) 725 RTE_ASSERT(!does_wrap); 726 727 if (may_wrap && does_wrap) { 728 size_t len0 = size - start_bit; 729 size_t len1 = len - len0; 730 731 rc = __rte_bitset_find_nowrap(bitset, size, start_bit, len0, find_clear); 732 if (rc < 0) 733 rc = __rte_bitset_find_nowrap(bitset, size, 0, len1, find_clear); 734 } else 735 rc = __rte_bitset_find_nowrap(bitset, size, start_bit, len, find_clear); 736 737 return rc; 738 #else 739 RTE_SET_USED(bitset); 740 RTE_SET_USED(size); 741 RTE_SET_USED(start_bit); 742 RTE_SET_USED(len); 743 RTE_SET_USED(flags); 744 RTE_VERIFY(false); 745 #endif 746 } 747 748 /** 749 * @warning 750 * @b EXPERIMENTAL: this API may change without prior notice. 751 * 752 * Find first bit set. 753 * 754 * Scans the bitset in the forward direction (i.e., starting at the 755 * least significant bit), and returns the index of the first '1'. 756 * 757 * @param bitset 758 * A pointer to the array of words making up the bitset. 759 * @param size 760 * The size of the bitset (in bits). 761 * @return 762 * Returns the index of the least significant '1', or -1 if all 763 * bits are '0'. 764 */ 765 __rte_experimental 766 static inline ssize_t 767 rte_bitset_find_first_set(const uint64_t *bitset, size_t size) 768 { 769 #ifdef ALLOW_EXPERIMENTAL_API 770 return __rte_bitset_find(bitset, size, 0, size, 0); 771 #else 772 RTE_SET_USED(bitset); 773 RTE_SET_USED(size); 774 RTE_VERIFY(false); 775 #endif 776 } 777 778 /** 779 * @warning 780 * @b EXPERIMENTAL: this API may change without prior notice. 781 * 782 * Find first bit set at offset. 783 * 784 * Scans the bitset in the forward direction (i.e., starting at the 785 * least significant bit), starting at an offset @c start_bit into the 786 * bitset, and returns the index of the first '1' encountered. 787 * 788 * @param bitset 789 * A pointer to the array of words making up the bitset. 790 * @param size 791 * The size of the bitset (in bits). 792 * @param start_bit 793 * The index of the first bit to check. Must be less than @c size. 794 * @param len 795 * The number of bits to scan. @c start_bit + @c len must be less 796 * than or equal to @c size. 797 * @return 798 * Returns the index of the least significant '1', or -1 if all 799 * bits are '0'. 800 */ 801 __rte_experimental 802 static inline ssize_t 803 rte_bitset_find_set(const uint64_t *bitset, size_t size, size_t start_bit, size_t len) 804 { 805 #ifdef ALLOW_EXPERIMENTAL_API 806 return __rte_bitset_find(bitset, size, start_bit, len, 0); 807 #else 808 RTE_SET_USED(bitset); 809 RTE_SET_USED(size); 810 RTE_SET_USED(start_bit); 811 RTE_SET_USED(len); 812 RTE_VERIFY(false); 813 #endif 814 } 815 816 /** 817 * @warning 818 * @b EXPERIMENTAL: this API may change without prior notice. 819 * 820 * Find first bit set at offset, with wrap-around. 821 * 822 * Scans the bitset in the forward direction (i.e., starting at the 823 * least significant bit), starting at an offset @c start_bit into the 824 * bitset. If no '1' is encountered before the end of the bitset, the search 825 * will continue at index 0. 826 * 827 * @param bitset 828 * A pointer to the array of words making up the bitset. 829 * @param size 830 * The size of the bitset (in bits). 831 * @param start_bit 832 * The index of the first bit to check. Must be less than @c size. 833 * @param len 834 * The number of bits to scan. @c start_bit + @c len must be less 835 * than or equal to @c size. 836 * @return 837 * Returns the index of the least significant '1', or -1 if all 838 * bits are '0'. 839 */ 840 __rte_experimental 841 static inline ssize_t 842 rte_bitset_find_set_wrap(const uint64_t *bitset, size_t size, size_t start_bit, size_t len) 843 { 844 #ifdef ALLOW_EXPERIMENTAL_API 845 return __rte_bitset_find(bitset, size, start_bit, len, __RTE_BITSET_FIND_FLAG_WRAP); 846 #else 847 RTE_SET_USED(bitset); 848 RTE_SET_USED(size); 849 RTE_SET_USED(start_bit); 850 RTE_SET_USED(len); 851 RTE_VERIFY(false); 852 #endif 853 } 854 855 /** 856 * @warning 857 * @b EXPERIMENTAL: this API may change without prior notice. 858 * 859 * Find first cleared bit. 860 * 861 * Scans the bitset in the forward direction (i.e., starting at the 862 * least significant bit), and returns the index of the first '0'. 863 * 864 * @param bitset 865 * A pointer to the array of words making up the bitset. 866 * @param size 867 * The size of the bitset (in bits). 868 * @return 869 * Returns the index of the least significant '0', or -1 if all 870 * bits are '1'. 871 */ 872 __rte_experimental 873 static inline ssize_t 874 rte_bitset_find_first_clear(const uint64_t *bitset, size_t size) 875 { 876 #ifdef ALLOW_EXPERIMENTAL_API 877 return __rte_bitset_find(bitset, size, 0, size, __RTE_BITSET_FIND_FLAG_FIND_CLEAR); 878 #else 879 RTE_SET_USED(bitset); 880 RTE_SET_USED(size); 881 RTE_VERIFY(false); 882 #endif 883 } 884 885 /** 886 * @warning 887 * @b EXPERIMENTAL: this API may change without prior notice. 888 * 889 * Find first cleared bit at offset. 890 * 891 * Scans the bitset in the forward direction (i.e., starting at the 892 * least significant bit), starting at an offset @c start_bit into the 893 * bitset, and returns the index of the first '0' encountered. 894 * 895 * @param bitset 896 * A pointer to the array of words making up the bitset. 897 * @param size 898 * The size of the bitset (in bits). 899 * @param start_bit 900 * The index of the first bit to check. Must be less than @c size. 901 * @param len 902 * The number of bits to scan. @c start_bit + @c len must be less 903 * than or equal to @c size. 904 * @return 905 * Returns the index of the least significant '0', or -1 if all 906 * bits are '1'. 907 */ 908 __rte_experimental 909 static inline ssize_t 910 rte_bitset_find_clear(const uint64_t *bitset, size_t size, size_t start_bit, size_t len) 911 { 912 #ifdef ALLOW_EXPERIMENTAL_API 913 return __rte_bitset_find(bitset, size, start_bit, len, __RTE_BITSET_FIND_FLAG_FIND_CLEAR); 914 #else 915 RTE_SET_USED(bitset); 916 RTE_SET_USED(size); 917 RTE_SET_USED(start_bit); 918 RTE_SET_USED(len); 919 RTE_VERIFY(false); 920 #endif 921 } 922 923 /** 924 * @warning 925 * @b EXPERIMENTAL: this API may change without prior notice. 926 * 927 * Find first cleared bit at offset, with wrap-around. 928 * 929 * Scans the bitset in the forward direction (i.e., starting at the 930 * least significant bit), starting at an offset @c start_bit into the 931 * bitset. If no '0' is encountered before the end of the bitset, the 932 * search will continue at index 0. 933 * 934 * @param bitset 935 * A pointer to the array of words making up the bitset. 936 * @param size 937 * The size of the bitset (in bits). 938 * @param start_bit 939 * The index of the first bit to check. Must be less than @c size. 940 * @param len 941 * The number of bits to scan. @c start_bit + @c len must be less 942 * than or equal to @c size. 943 * @return 944 * Returns the index of the least significant '0', or -1 if all 945 * bits are '1'. 946 */ 947 __rte_experimental 948 static inline ssize_t 949 rte_bitset_find_clear_wrap(const uint64_t *bitset, size_t size, size_t start_bit, size_t len) 950 { 951 #ifdef ALLOW_EXPERIMENTAL_API 952 return __rte_bitset_find(bitset, size, start_bit, len, 953 __RTE_BITSET_FIND_FLAG_FIND_CLEAR | __RTE_BITSET_FIND_FLAG_WRAP); 954 #else 955 RTE_SET_USED(bitset); 956 RTE_SET_USED(size); 957 RTE_SET_USED(start_bit); 958 RTE_SET_USED(len); 959 RTE_VERIFY(false); 960 #endif 961 } 962 963 /** 964 * @warning 965 * @b EXPERIMENTAL: this API may change without prior notice. 966 * 967 * Copy bitset. 968 * 969 * Copy the bits of the @c src_bitset to the @c dst_bitset. 970 * 971 * The bitsets may not overlap and must be of equal size. 972 * 973 * @param dst_bitset 974 * A pointer to the array of words making up the bitset. 975 * @param src_bitset 976 * A pointer to the array of words making up the bitset. 977 * @param size 978 * The size of the bitsets (in bits). 979 */ 980 __rte_experimental 981 static inline void 982 rte_bitset_copy(uint64_t *__rte_restrict dst_bitset, const uint64_t *__rte_restrict src_bitset, 983 size_t size) 984 { 985 rte_memcpy(dst_bitset, src_bitset, RTE_BITSET_SIZE(size)); 986 } 987 988 /** 989 * @warning 990 * @b EXPERIMENTAL: this API may change without prior notice. 991 * 992 * Bitwise or two bitsets. 993 * 994 * Perform a bitwise OR operation on all bits in the two equal-size 995 * bitsets @c src_bitset0 and @c src_bitset1, and store the results in 996 * @c dst_bitset. 997 * 998 * @param dst_bitset 999 * A pointer to the destination bitset. 1000 * @param src_bitset0 1001 * A pointer to the first source bitset. 1002 * @param src_bitset1 1003 * A pointer to the second source bitset. 1004 * @param size 1005 * The size of the bitsets (in bits). 1006 */ 1007 __rte_experimental 1008 static inline void 1009 rte_bitset_or(uint64_t *dst_bitset, const uint64_t *src_bitset0, const uint64_t *src_bitset1, 1010 size_t size) 1011 { 1012 size_t i; 1013 1014 for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++) 1015 dst_bitset[i] = src_bitset0[i] | src_bitset1[i]; 1016 } 1017 1018 /** 1019 * @warning 1020 * @b EXPERIMENTAL: this API may change without prior notice. 1021 * 1022 * Bitwise and two bitsets. 1023 * 1024 * Perform a bitwise AND operation on all bits in the two equal-size 1025 * bitsets @c src_bitset0 and @c src_bitset1, and store the result in 1026 * @c dst_bitset. 1027 * 1028 * @param dst_bitset 1029 * A pointer to the destination bitset. 1030 * @param src_bitset0 1031 * A pointer to the first source bitset. 1032 * @param src_bitset1 1033 * A pointer to the second source bitset. 1034 * @param size 1035 * The size of the bitsets (in bits). 1036 */ 1037 __rte_experimental 1038 static inline void 1039 rte_bitset_and(uint64_t *dst_bitset, const uint64_t *src_bitset0, const uint64_t *src_bitset1, 1040 size_t size) 1041 { 1042 size_t i; 1043 1044 for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++) 1045 dst_bitset[i] = src_bitset0[i] & src_bitset1[i]; 1046 } 1047 1048 /** 1049 * @warning 1050 * @b EXPERIMENTAL: this API may change without prior notice. 1051 * 1052 * Bitwise xor two bitsets. 1053 * 1054 * Perform a bitwise XOR operation on all bits in the two equal-size 1055 * bitsets @c src_bitset0 and @c src_bitset1, and store the result in 1056 * @c dst_bitset. 1057 * 1058 * @param dst_bitset 1059 * A pointer to the destination bitset. 1060 * @param src_bitset0 1061 * A pointer to the first source bitset. 1062 * @param src_bitset1 1063 * A pointer to the second source bitset. 1064 * @param size 1065 * The size of the bitsets (in bits). 1066 */ 1067 __rte_experimental 1068 static inline void 1069 rte_bitset_xor(uint64_t *dst_bitset, const uint64_t *src_bitset0, const uint64_t *src_bitset1, 1070 size_t size) 1071 { 1072 size_t i; 1073 1074 for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++) 1075 dst_bitset[i] = src_bitset0[i] ^ src_bitset1[i]; 1076 } 1077 1078 /** 1079 * @warning 1080 * @b EXPERIMENTAL: this API may change without prior notice. 1081 * 1082 * Compute the bitwise complement of a bitset. 1083 * 1084 * Flip every bit in the @c src_bitset, and store the result in @c 1085 * dst_bitset. 1086 * 1087 * @param dst_bitset 1088 * A pointer to the destination bitset. 1089 * @param src_bitset 1090 * A pointer to the source bitset. 1091 * @param size 1092 * The size of the bitsets (in bits). 1093 */ 1094 __rte_experimental 1095 static inline void 1096 rte_bitset_complement(uint64_t *dst_bitset, const uint64_t *src_bitset, size_t size) 1097 { 1098 size_t i; 1099 1100 for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++) 1101 dst_bitset[i] = ~src_bitset[i]; 1102 } 1103 1104 /** 1105 * @warning 1106 * @b EXPERIMENTAL: this API may change without prior notice. 1107 * 1108 * Shift bitset left. 1109 * 1110 * Perform a logical shift left of (multiply) @c src_bitset, and store 1111 * the result in @c dst_bitset. 1112 * 1113 * @param dst_bitset 1114 * A pointer to the destination bitset. 1115 * @param src_bitset 1116 * A pointer to the source bitset. 1117 * @param size 1118 * The size of the bitsets (in bits). 1119 * @param shift_bits 1120 * The number of bits to shift the bitset. 1121 */ 1122 __rte_experimental 1123 static inline void 1124 rte_bitset_shift_left(uint64_t *dst_bitset, const uint64_t *src_bitset, size_t size, 1125 size_t shift_bits) 1126 { 1127 const int src_word_offset = shift_bits / RTE_BITSET_WORD_BITS; 1128 const int src_bit_offset = shift_bits % RTE_BITSET_WORD_BITS; 1129 unsigned int dst_idx; 1130 1131 for (dst_idx = 0; dst_idx < RTE_BITSET_NUM_WORDS(size); dst_idx++) { 1132 int src_high_idx = dst_idx - src_word_offset; 1133 uint64_t low_bits = 0; 1134 uint64_t high_bits = 0; 1135 1136 if (src_high_idx >= 0) { 1137 int src_low_idx = src_high_idx - 1; 1138 1139 high_bits = src_bitset[src_high_idx] << src_bit_offset; 1140 1141 if (src_bit_offset > 0 && src_low_idx >= 0) 1142 low_bits = src_bitset[src_low_idx] >> 1143 (RTE_BITSET_WORD_BITS - src_bit_offset); 1144 } 1145 dst_bitset[dst_idx] = low_bits | high_bits; 1146 } 1147 } 1148 1149 /** 1150 * @warning 1151 * @b EXPERIMENTAL: this API may change without prior notice. 1152 * 1153 * Shift bitset right. 1154 * 1155 * Perform a logical shift right of (divide) @c src_bitset, and store 1156 * the result in @c dst_bitset. 1157 * 1158 * @param dst_bitset 1159 * A pointer to the destination bitset. 1160 * @param src_bitset 1161 * A pointer to the source bitset. 1162 * @param size 1163 * The size of the bitsets (in bits). 1164 * @param shift_bits 1165 * The number of bits to shift the bitset. 1166 */ 1167 __rte_experimental 1168 static inline void 1169 rte_bitset_shift_right(uint64_t *dst_bitset, const uint64_t *src_bitset, size_t size, 1170 size_t shift_bits) 1171 { 1172 const int num_words = RTE_BITSET_NUM_WORDS(size); 1173 const uint64_t used_mask = __RTE_BITSET_USED_MASK(size); 1174 const int src_word_offset = shift_bits / RTE_BITSET_WORD_BITS; 1175 const int src_bit_offset = shift_bits % RTE_BITSET_WORD_BITS; 1176 int dst_idx; 1177 1178 for (dst_idx = 0; dst_idx < num_words; dst_idx++) { 1179 int src_low_idx = src_word_offset + dst_idx; 1180 int src_high_idx = src_low_idx + 1; 1181 uint64_t src_low_word_bits = 0; 1182 uint64_t src_high_word_bits = 0; 1183 1184 if (src_low_idx < num_words) { 1185 src_low_word_bits = src_bitset[src_low_idx]; 1186 1187 if (src_low_idx == (num_words - 1)) 1188 src_low_word_bits &= used_mask; 1189 1190 src_low_word_bits >>= src_bit_offset; 1191 1192 if (src_bit_offset > 0 && src_high_idx < num_words) { 1193 src_high_word_bits = src_bitset[src_high_idx]; 1194 1195 if (src_high_idx == (num_words - 1)) 1196 src_high_word_bits &= used_mask; 1197 1198 src_high_word_bits <<= (RTE_BITSET_WORD_BITS - src_bit_offset); 1199 } 1200 } 1201 dst_bitset[dst_idx] = src_low_word_bits | src_high_word_bits; 1202 } 1203 } 1204 1205 /** 1206 * @warning 1207 * @b EXPERIMENTAL: this API may change without prior notice. 1208 * 1209 * Compare two bitsets. 1210 * 1211 * Compare two bitsets for equality. 1212 * 1213 * @param bitset_a 1214 * A pointer to the destination bitset. 1215 * @param bitset_b 1216 * A pointer to the source bitset. 1217 * @param size 1218 * The size of the bitsets (in bits). 1219 */ 1220 __rte_experimental 1221 static inline bool 1222 rte_bitset_equal(const uint64_t *bitset_a, const uint64_t *bitset_b, size_t size) 1223 { 1224 size_t i; 1225 uint64_t last_a, last_b; 1226 1227 for (i = 0; i < RTE_BITSET_NUM_WORDS(size) - 1; i++) 1228 if (bitset_a[i] != bitset_b[i]) 1229 return false; 1230 1231 last_a = bitset_a[i] << __RTE_BITSET_UNUSED(size); 1232 last_b = bitset_b[i] << __RTE_BITSET_UNUSED(size); 1233 1234 return last_a == last_b; 1235 } 1236 1237 /** 1238 * @warning 1239 * @b EXPERIMENTAL: this API may change without prior notice. 1240 * 1241 * Converts a bitset to a string. 1242 * 1243 * This function prints a string representation of the bitstring to 1244 * the supplied buffer. 1245 * 1246 * Each bit is represented either by '0' or '1' in the output, with 1247 * the first (left-most) character in the output being the most 1248 * significant bit. The resulting string is NUL terminated. 1249 * 1250 * @param bitset 1251 * A pointer to the array of bitset 64-bit words. 1252 * @param size 1253 * The number of bits the bitset represent. 1254 * @param buf 1255 * A buffer to hold the output. 1256 * @param capacity 1257 * The size of the buffer. Must be @c size + 1 or larger. 1258 * @return 1259 * Returns the number of bytes written (i.e., @c size + 1), or -EINVAL 1260 * in case the buffer capacity was too small. 1261 */ 1262 __rte_experimental 1263 ssize_t 1264 rte_bitset_to_str(const uint64_t *bitset, size_t size, char *buf, size_t capacity); 1265 1266 #ifdef __cplusplus 1267 } 1268 #endif 1269 1270 #endif /* _RTE_BITSET_H_ */ 1271