lib/librte_eal/common/include/rte_bitmap.h

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2010-2014 Intel Corporation
   3  */
   4
   5 #ifndef __INCLUDE_RTE_BITMAP_H__
   6 #define __INCLUDE_RTE_BITMAP_H__
   7
   8 #ifdef __cplusplus
   9 extern "C" {
  10 #endif
  11
  12 /**
  13  * @file
  14  * RTE Bitmap
  15  *
  16  * The bitmap component provides a mechanism to manage large arrays of bits
  17  * through bit get/set/clear and bit array scan operations.
  18  *
  19  * The bitmap scan operation is optimized for 64-bit CPUs using 64/128 byte cache
  20  * lines. The bitmap is hierarchically organized using two arrays (array1 and
  21  * array2), with each bit in array1 being associated with a full cache line
  22  * (512/1024 bits) of bitmap bits, which are stored in array2: the bit in array1
  23  * is set only when there is at least one bit set within its associated array2
  24  * bits, otherwise the bit in array1 is cleared. The read and write operations
  25  * for array1 and array2 are always done in slabs of 64 bits.
  26  *
  27  * This bitmap is not thread safe. For lock free operation on a specific bitmap
  28  * instance, a single writer thread performing bit set/clear operations is
  29  * allowed, only the writer thread can do bitmap scan operations, while there
  30  * can be several reader threads performing bit get operations in parallel with
  31  * the writer thread. When the use of locking primitives is acceptable, the
  32  * serialization of the bit set/clear and bitmap scan operations needs to be
  33  * enforced by the caller, while the bit get operation does not require locking
  34  * the bitmap.
  35  *
  36  ***/
  37
  38 #include <string.h>
  39 #include <rte_common.h>
  40 #include <rte_debug.h>
  41 #include <rte_memory.h>
  42 #include <rte_branch_prediction.h>
  43 #include <rte_prefetch.h>
  44
  45 #ifndef RTE_BITMAP_OPTIMIZATIONS
  46 #define RTE_BITMAP_OPTIMIZATIONS                         1
  47 #endif
  48
  49 /* Slab */
  50 #define RTE_BITMAP_SLAB_BIT_SIZE                 64
  51 #define RTE_BITMAP_SLAB_BIT_SIZE_LOG2            6
  52 #define RTE_BITMAP_SLAB_BIT_MASK                 (RTE_BITMAP_SLAB_BIT_SIZE - 1)
  53
  54 /* Cache line (CL) */
  55 #define RTE_BITMAP_CL_BIT_SIZE                   (RTE_CACHE_LINE_SIZE * 8)
  56 #define RTE_BITMAP_CL_BIT_SIZE_LOG2              (RTE_CACHE_LINE_SIZE_LOG2 + 3)
  57 #define RTE_BITMAP_CL_BIT_MASK                   (RTE_BITMAP_CL_BIT_SIZE - 1)
  58
  59 #define RTE_BITMAP_CL_SLAB_SIZE                  (RTE_BITMAP_CL_BIT_SIZE / RTE_BITMAP_SLAB_BIT_SIZE)
  60 #define RTE_BITMAP_CL_SLAB_SIZE_LOG2             (RTE_BITMAP_CL_BIT_SIZE_LOG2 - RTE_BITMAP_SLAB_BIT_SIZE_LOG2)
  61 #define RTE_BITMAP_CL_SLAB_MASK                  (RTE_BITMAP_CL_SLAB_SIZE - 1)
  62
  63 /** Bitmap data structure */
  64 struct rte_bitmap {
  65         /* Context for array1 and array2 */
  66         uint64_t *array1;                        /**< Bitmap array1 */
  67         uint64_t *array2;                        /**< Bitmap array2 */
  68         uint32_t array1_size;                    /**< Number of 64-bit slabs in array1 that are actually used */
  69         uint32_t array2_size;                    /**< Number of 64-bit slabs in array2 */
  70
  71         /* Context for the "scan next" operation */
  72         uint32_t index1;  /**< Bitmap scan: Index of current array1 slab */
  73         uint32_t offset1; /**< Bitmap scan: Offset of current bit within current array1 slab */
  74         uint32_t index2;  /**< Bitmap scan: Index of current array2 slab */
  75         uint32_t go2;     /**< Bitmap scan: Go/stop condition for current array2 cache line */
  76
  77         /* Storage space for array1 and array2 */
  78         uint8_t memory[];
  79 };
  80
  81 static inline void
  82 __rte_bitmap_index1_inc(struct rte_bitmap *bmp)
  83 {
  84         bmp->index1 = (bmp->index1 + 1) & (bmp->array1_size - 1);
  85 }
  86
  87 static inline uint64_t
  88 __rte_bitmap_mask1_get(struct rte_bitmap *bmp)
  89 {
  90         return (~1lu) << bmp->offset1;
  91 }
  92
  93 static inline void
  94 __rte_bitmap_index2_set(struct rte_bitmap *bmp)
  95 {
  96         bmp->index2 = (((bmp->index1 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2) + bmp->offset1) << RTE_BITMAP_CL_SLAB_SIZE_LOG2);
  97 }
  98
  99 #if RTE_BITMAP_OPTIMIZATIONS
 100
 101 static inline int
 102 rte_bsf64(uint64_t slab, uint32_t *pos)
 103 {
 104         if (likely(slab == 0)) {
 105                 return 0;
 106         }
 107
 108         *pos = __builtin_ctzll(slab);
 109         return 1;
 110 }
 111
 112 #else
 113
 114 static inline int
 115 rte_bsf64(uint64_t slab, uint32_t *pos)
 116 {
 117         uint64_t mask;
 118         uint32_t i;
 119
 120         if (likely(slab == 0)) {
 121                 return 0;
 122         }
 123
 124         for (i = 0, mask = 1; i < RTE_BITMAP_SLAB_BIT_SIZE; i ++, mask <<= 1) {
 125                 if (unlikely(slab & mask)) {
 126                         *pos = i;
 127                         return 1;
 128                 }
 129         }
 130
 131         return 0;
 132 }
 133
 134 #endif
 135
 136 static inline uint32_t
 137 __rte_bitmap_get_memory_footprint(uint32_t n_bits,
 138         uint32_t *array1_byte_offset, uint32_t *array1_slabs,
 139         uint32_t *array2_byte_offset, uint32_t *array2_slabs)
 140 {
 141         uint32_t n_slabs_context, n_slabs_array1, n_cache_lines_context_and_array1;
 142         uint32_t n_cache_lines_array2;
 143         uint32_t n_bytes_total;
 144
 145         n_cache_lines_array2 = (n_bits + RTE_BITMAP_CL_BIT_SIZE - 1) / RTE_BITMAP_CL_BIT_SIZE;
 146         n_slabs_array1 = (n_cache_lines_array2 + RTE_BITMAP_SLAB_BIT_SIZE - 1) / RTE_BITMAP_SLAB_BIT_SIZE;
 147         n_slabs_array1 = rte_align32pow2(n_slabs_array1);
 148         n_slabs_context = (sizeof(struct rte_bitmap) + (RTE_BITMAP_SLAB_BIT_SIZE / 8) - 1) / (RTE_BITMAP_SLAB_BIT_SIZE / 8);
 149         n_cache_lines_context_and_array1 = (n_slabs_context + n_slabs_array1 + RTE_BITMAP_CL_SLAB_SIZE - 1) / RTE_BITMAP_CL_SLAB_SIZE;
 150         n_bytes_total = (n_cache_lines_context_and_array1 + n_cache_lines_array2) * RTE_CACHE_LINE_SIZE;
 151
 152         if (array1_byte_offset) {
 153                 *array1_byte_offset = n_slabs_context * (RTE_BITMAP_SLAB_BIT_SIZE / 8);
 154         }
 155         if (array1_slabs) {
 156                 *array1_slabs = n_slabs_array1;
 157         }
 158         if (array2_byte_offset) {
 159                 *array2_byte_offset = n_cache_lines_context_and_array1 * RTE_CACHE_LINE_SIZE;
 160         }
 161         if (array2_slabs) {
 162                 *array2_slabs = n_cache_lines_array2 * RTE_BITMAP_CL_SLAB_SIZE;
 163         }
 164
 165         return n_bytes_total;
 166 }
 167
 168 static inline void
 169 __rte_bitmap_scan_init(struct rte_bitmap *bmp)
 170 {
 171         bmp->index1 = bmp->array1_size - 1;
 172         bmp->offset1 = RTE_BITMAP_SLAB_BIT_SIZE - 1;
 173         __rte_bitmap_index2_set(bmp);
 174         bmp->index2 += RTE_BITMAP_CL_SLAB_SIZE;
 175
 176         bmp->go2 = 0;
 177 }
 178
 179 /**
 180  * Bitmap memory footprint calculation
 181  *
 182  * @param n_bits
 183  *   Number of bits in the bitmap
 184  * @return
 185  *   Bitmap memory footprint measured in bytes on success, 0 on error
 186  */
 187 static inline uint32_t
 188 rte_bitmap_get_memory_footprint(uint32_t n_bits) {
 189         /* Check input arguments */
 190         if (n_bits == 0) {
 191                 return 0;
 192         }
 193
 194         return __rte_bitmap_get_memory_footprint(n_bits, NULL, NULL, NULL, NULL);
 195 }
 196
 197 /**
 198  * Bitmap initialization
 199  *
 200  * @param mem_size
 201  *   Minimum expected size of bitmap.
 202  * @param mem
 203  *   Base address of array1 and array2.
 204  * @param n_bits
 205  *   Number of pre-allocated bits in array2. Must be non-zero and multiple of 512.
 206  * @return
 207  *   Handle to bitmap instance.
 208  */
 209 static inline struct rte_bitmap *
 210 rte_bitmap_init(uint32_t n_bits, uint8_t *mem, uint32_t mem_size)
 211 {
 212         struct rte_bitmap *bmp;
 213         uint32_t array1_byte_offset, array1_slabs, array2_byte_offset, array2_slabs;
 214         uint32_t size;
 215
 216         /* Check input arguments */
 217         if (n_bits == 0) {
 218                 return NULL;
 219         }
 220
 221         if ((mem == NULL) || (((uintptr_t) mem) & RTE_CACHE_LINE_MASK)) {
 222                 return NULL;
 223         }
 224
 225         size = __rte_bitmap_get_memory_footprint(n_bits,
 226                 &array1_byte_offset, &array1_slabs,
 227                 &array2_byte_offset, &array2_slabs);
 228         if (size < mem_size) {
 229                 return NULL;
 230         }
 231
 232         /* Setup bitmap */
 233         memset(mem, 0, size);
 234         bmp = (struct rte_bitmap *) mem;
 235
 236         bmp->array1 = (uint64_t *) &mem[array1_byte_offset];
 237         bmp->array1_size = array1_slabs;
 238         bmp->array2 = (uint64_t *) &mem[array2_byte_offset];
 239         bmp->array2_size = array2_slabs;
 240
 241         __rte_bitmap_scan_init(bmp);
 242
 243         return bmp;
 244 }
 245
 246 /**
 247  * Bitmap free
 248  *
 249  * @param bmp
 250  *   Handle to bitmap instance
 251  * @return
 252  *   0 upon success, error code otherwise
 253  */
 254 static inline int
 255 rte_bitmap_free(struct rte_bitmap *bmp)
 256 {
 257         /* Check input arguments */
 258         if (bmp == NULL) {
 259                 return -1;
 260         }
 261
 262         return 0;
 263 }
 264
 265 /**
 266  * Bitmap reset
 267  *
 268  * @param bmp
 269  *   Handle to bitmap instance
 270  */
 271 static inline void
 272 rte_bitmap_reset(struct rte_bitmap *bmp)
 273 {
 274         memset(bmp->array1, 0, bmp->array1_size * sizeof(uint64_t));
 275         memset(bmp->array2, 0, bmp->array2_size * sizeof(uint64_t));
 276         __rte_bitmap_scan_init(bmp);
 277 }
 278
 279 /**
 280  * Bitmap location prefetch into CPU L1 cache
 281  *
 282  * @param bmp
 283  *   Handle to bitmap instance
 284  * @param pos
 285  *   Bit position
 286  * @return
 287  *   0 upon success, error code otherwise
 288  */
 289 static inline void
 290 rte_bitmap_prefetch0(struct rte_bitmap *bmp, uint32_t pos)
 291 {
 292         uint64_t *slab2;
 293         uint32_t index2;
 294
 295         index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
 296         slab2 = bmp->array2 + index2;
 297         rte_prefetch0((void *) slab2);
 298 }
 299
 300 /**
 301  * Bitmap bit get
 302  *
 303  * @param bmp
 304  *   Handle to bitmap instance
 305  * @param pos
 306  *   Bit position
 307  * @return
 308  *   0 when bit is cleared, non-zero when bit is set
 309  */
 310 static inline uint64_t
 311 rte_bitmap_get(struct rte_bitmap *bmp, uint32_t pos)
 312 {
 313         uint64_t *slab2;
 314         uint32_t index2, offset2;
 315
 316         index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
 317         offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
 318         slab2 = bmp->array2 + index2;
 319         return (*slab2) & (1lu << offset2);
 320 }
 321
 322 /**
 323  * Bitmap bit set
 324  *
 325  * @param bmp
 326  *   Handle to bitmap instance
 327  * @param pos
 328  *   Bit position
 329  */
 330 static inline void
 331 rte_bitmap_set(struct rte_bitmap *bmp, uint32_t pos)
 332 {
 333         uint64_t *slab1, *slab2;
 334         uint32_t index1, index2, offset1, offset2;
 335
 336         /* Set bit in array2 slab and set bit in array1 slab */
 337         index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
 338         offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
 339         index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
 340         offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
 341         slab2 = bmp->array2 + index2;
 342         slab1 = bmp->array1 + index1;
 343
 344         *slab2 |= 1lu << offset2;
 345         *slab1 |= 1lu << offset1;
 346 }
 347
 348 /**
 349  * Bitmap slab set
 350  *
 351  * @param bmp
 352  *   Handle to bitmap instance
 353  * @param pos
 354  *   Bit position identifying the array2 slab
 355  * @param slab
 356  *   Value to be assigned to the 64-bit slab in array2
 357  */
 358 static inline void
 359 rte_bitmap_set_slab(struct rte_bitmap *bmp, uint32_t pos, uint64_t slab)
 360 {
 361         uint64_t *slab1, *slab2;
 362         uint32_t index1, index2, offset1;
 363
 364         /* Set bits in array2 slab and set bit in array1 slab */
 365         index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
 366         index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
 367         offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
 368         slab2 = bmp->array2 + index2;
 369         slab1 = bmp->array1 + index1;
 370
 371         *slab2 |= slab;
 372         *slab1 |= 1lu << offset1;
 373 }
 374
 375 static inline uint64_t
 376 __rte_bitmap_line_not_empty(uint64_t *slab2)
 377 {
 378         uint64_t v1, v2, v3, v4;
 379
 380         v1 = slab2[0] | slab2[1];
 381         v2 = slab2[2] | slab2[3];
 382         v3 = slab2[4] | slab2[5];
 383         v4 = slab2[6] | slab2[7];
 384         v1 |= v2;
 385         v3 |= v4;
 386
 387         return v1 | v3;
 388 }
 389
 390 /**
 391  * Bitmap bit clear
 392  *
 393  * @param bmp
 394  *   Handle to bitmap instance
 395  * @param pos
 396  *   Bit position
 397  */
 398 static inline void
 399 rte_bitmap_clear(struct rte_bitmap *bmp, uint32_t pos)
 400 {
 401         uint64_t *slab1, *slab2;
 402         uint32_t index1, index2, offset1, offset2;
 403
 404         /* Clear bit in array2 slab */
 405         index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
 406         offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
 407         slab2 = bmp->array2 + index2;
 408
 409         /* Return if array2 slab is not all-zeros */
 410         *slab2 &= ~(1lu << offset2);
 411         if (*slab2){
 412                 return;
 413         }
 414
 415         /* Check the entire cache line of array2 for all-zeros */
 416         index2 &= ~ RTE_BITMAP_CL_SLAB_MASK;
 417         slab2 = bmp->array2 + index2;
 418         if (__rte_bitmap_line_not_empty(slab2)) {
 419                 return;
 420         }
 421
 422         /* The array2 cache line is all-zeros, so clear bit in array1 slab */
 423         index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
 424         offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
 425         slab1 = bmp->array1 + index1;
 426         *slab1 &= ~(1lu << offset1);
 427
 428         return;
 429 }
 430
 431 static inline int
 432 __rte_bitmap_scan_search(struct rte_bitmap *bmp)
 433 {
 434         uint64_t value1;
 435         uint32_t i;
 436
 437         /* Check current array1 slab */
 438         value1 = bmp->array1[bmp->index1];
 439         value1 &= __rte_bitmap_mask1_get(bmp);
 440
 441         if (rte_bsf64(value1, &bmp->offset1)) {
 442                 return 1;
 443         }
 444
 445         __rte_bitmap_index1_inc(bmp);
 446         bmp->offset1 = 0;
 447
 448         /* Look for another array1 slab */
 449         for (i = 0; i < bmp->array1_size; i ++, __rte_bitmap_index1_inc(bmp)) {
 450                 value1 = bmp->array1[bmp->index1];
 451
 452                 if (rte_bsf64(value1, &bmp->offset1)) {
 453                         return 1;
 454                 }
 455         }
 456
 457         return 0;
 458 }
 459
 460 static inline void
 461 __rte_bitmap_scan_read_init(struct rte_bitmap *bmp)
 462 {
 463         __rte_bitmap_index2_set(bmp);
 464         bmp->go2 = 1;
 465         rte_prefetch1((void *)(bmp->array2 + bmp->index2 + 8));
 466 }
 467
 468 static inline int
 469 __rte_bitmap_scan_read(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
 470 {
 471         uint64_t *slab2;
 472
 473         slab2 = bmp->array2 + bmp->index2;
 474         for ( ; bmp->go2 ; bmp->index2 ++, slab2 ++, bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK) {
 475                 if (*slab2) {
 476                         *pos = bmp->index2 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
 477                         *slab = *slab2;
 478
 479                         bmp->index2 ++;
 480                         slab2 ++;
 481                         bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK;
 482                         return 1;
 483                 }
 484         }
 485
 486         return 0;
 487 }
 488
 489 /**
 490  * Bitmap scan (with automatic wrap-around)
 491  *
 492  * @param bmp
 493  *   Handle to bitmap instance
 494  * @param pos
 495  *   When function call returns 1, pos contains the position of the next set
 496  *   bit, otherwise not modified
 497  * @param slab
 498  *   When function call returns 1, slab contains the value of the entire 64-bit
 499  *   slab where the bit indicated by pos is located. Slabs are always 64-bit
 500  *   aligned, so the position of the first bit of the slab (this bit is not
 501  *   necessarily set) is pos / 64. Once a slab has been returned by the bitmap
 502  *   scan operation, the internal pointers of the bitmap are updated to point
 503  *   after this slab, so the same slab will not be returned again if it
 504  *   contains more than one bit which is set. When function call returns 0,
 505  *   slab is not modified.
 506  * @return
 507  *   0 if there is no bit set in the bitmap, 1 otherwise
 508  */
 509 static inline int
 510 rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
 511 {
 512         /* Return data from current array2 line if available */
 513         if (__rte_bitmap_scan_read(bmp, pos, slab)) {
 514                 return 1;
 515         }
 516
 517         /* Look for non-empty array2 line */
 518         if (__rte_bitmap_scan_search(bmp)) {
 519                 __rte_bitmap_scan_read_init(bmp);
 520                 __rte_bitmap_scan_read(bmp, pos, slab);
 521                 return 1;
 522         }
 523
 524         /* Empty bitmap */
 525         return 0;
 526 }
 527
 528 #ifdef __cplusplus
 529 }
 530 #endif
 531
 532 #endif /* __INCLUDE_RTE_BITMAP_H__ */