lib/librte_sched/rte_bitmap.h

   1 /*-
   2  *   BSD LICENSE
   3  *
   4  *   Copyright(c) 2010-2013 Intel Corporation. All rights reserved.
   5  *   All rights reserved.
   6  *
   7  *   Redistribution and use in source and binary forms, with or without
   8  *   modification, are permitted provided that the following conditions
   9  *   are met:
  10  *
  11  *     * Redistributions of source code must retain the above copyright
  12  *       notice, this list of conditions and the following disclaimer.
  13  *     * Redistributions in binary form must reproduce the above copyright
  14  *       notice, this list of conditions and the following disclaimer in
  15  *       the documentation and/or other materials provided with the
  16  *       distribution.
  17  *     * Neither the name of Intel Corporation nor the names of its
  18  *       contributors may be used to endorse or promote products derived
  19  *       from this software without specific prior written permission.
  20  *
  21  *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  24  *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  25  *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  26  *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  27  *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  28  *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  29  *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  30  *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  31  *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32  *
  33  */
  34
  35 #ifndef __INCLUDE_RTE_BITMAP_H__
  36 #define __INCLUDE_RTE_BITMAP_H__
  37
  38 #ifdef __cplusplus
  39 extern "C" {
  40 #endif
  41
  42 /**
  43  * @file
  44  * RTE Bitmap
  45  *
  46  * The bitmap component provides a mechanism to manage large arrays of bits
  47  * through bit get/set/clear and bit array scan operations.
  48  *
  49  * The bitmap scan operation is optimized for 64-bit CPUs using 64-byte cache
  50  * lines. The bitmap is hierarchically organized using two arrays (array1 and
  51  * array2), with each bit in array1 being associated with a full cache line
  52  * (512 bits) of bitmap bits, which are stored in array2: the bit in array1 is
  53  * set only when there is at least one bit set within its associated array2
  54  * bits, otherwise the bit in array1 is cleared. The read and write operations
  55  * for array1 and array2 are always done in slabs of 64 bits.
  56  *
  57  * This bitmap is not thread safe. For lock free operation on a specific bitmap
  58  * instance, a single writer thread performing bit set/clear operations is
  59  * allowed, only the writer thread can do bitmap scan operations, while there
  60  * can be several reader threads performing bit get operations in parallel with
  61  * the writer thread. When the use of locking primitives is acceptable, the
  62  * serialization of the bit set/clear and bitmap scan operations needs to be
  63  * enforced by the caller, while the bit get operation does not require locking
  64  * the bitmap.
  65  *
  66  ***/
  67
  68 #include <rte_debug.h>
  69 #include <rte_memory.h>
  70 #include <rte_branch_prediction.h>
  71 #include <rte_prefetch.h>
  72
  73 #ifndef RTE_BITMAP_OPTIMIZATIONS
  74 #define RTE_BITMAP_OPTIMIZATIONS                         1
  75 #endif
  76 #if RTE_BITMAP_OPTIMIZATIONS
  77 #include <tmmintrin.h>
  78 #endif
  79
  80 /** Number of elements in array1. Each element in array1 is a 64-bit slab. */
  81 #ifndef RTE_BITMAP_ARRAY1_SIZE
  82 #define RTE_BITMAP_ARRAY1_SIZE                   16
  83 #endif
  84
  85 /* Slab */
  86 #define RTE_BITMAP_SLAB_BIT_SIZE                 64
  87 #define RTE_BITMAP_SLAB_BIT_SIZE_LOG2            6
  88 #define RTE_BITMAP_SLAB_BIT_MASK                 (RTE_BITMAP_SLAB_BIT_SIZE - 1)
  89
  90 /* Cache line (CL) */
  91 #define RTE_BITMAP_CL_BIT_SIZE                   (CACHE_LINE_SIZE * 8)
  92 #define RTE_BITMAP_CL_BIT_SIZE_LOG2              9
  93 #define RTE_BITMAP_CL_BIT_MASK                   (RTE_BITMAP_CL_BIT_SIZE - 1)
  94
  95 #define RTE_BITMAP_CL_SLAB_SIZE                  (RTE_BITMAP_CL_BIT_SIZE / RTE_BITMAP_SLAB_BIT_SIZE)
  96 #define RTE_BITMAP_CL_SLAB_SIZE_LOG2             3
  97 #define RTE_BITMAP_CL_SLAB_MASK                  (RTE_BITMAP_CL_SLAB_SIZE - 1)
  98
  99 /** Bitmap data structure */
 100 struct rte_bitmap {
 101         uint64_t array1[RTE_BITMAP_ARRAY1_SIZE]; /**< Bitmap array1 */
 102         uint64_t *array2;                        /**< Bitmap array2 */
 103         uint32_t array1_size;                    /**< Number of 64-bit slabs in array1 that are actually used */
 104         uint32_t array2_size;                    /**< Number of 64-bit slabs in array2 */
 105
 106         /* Context for the "scan next" operation */
 107         uint32_t index1;  /**< Bitmap scan: Index of current array1 slab */
 108         uint32_t offset1; /**< Bitmap scan: Offset of current bit within current array1 slab */
 109         uint32_t index2;  /**< Bitmap scan: Index of current array2 slab */
 110         uint32_t go2;     /**< Bitmap scan: Go/stop condition for current array2 cache line */
 111 } __rte_cache_aligned;
 112
 113 static inline void
 114 __rte_bitmap_index1_inc(struct rte_bitmap *bmp)
 115 {
 116         bmp->index1 = (bmp->index1 + 1) & (RTE_BITMAP_ARRAY1_SIZE - 1);
 117 }
 118
 119 static inline uint64_t
 120 __rte_bitmap_mask1_get(struct rte_bitmap *bmp)
 121 {
 122         return ((~1lu) << bmp->offset1);
 123 }
 124
 125 static inline void
 126 __rte_bitmap_index2_set(struct rte_bitmap *bmp)
 127 {
 128         bmp->index2 = (((bmp->index1 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2) + bmp->offset1) << RTE_BITMAP_CL_SLAB_SIZE_LOG2);
 129 }
 130
 131 #if RTE_BITMAP_OPTIMIZATIONS
 132
 133 static inline int
 134 rte_bsf64(uint64_t slab, uint32_t *pos)
 135 {
 136         if (likely(slab == 0)) {
 137                 return 0;
 138         }
 139
 140         *pos = __builtin_ctzll(slab);
 141         return 1;
 142 }
 143
 144 #else
 145
 146 static inline int
 147 rte_bsf64(uint64_t slab, uint32_t *pos)
 148 {
 149         uint64_t mask;
 150         uint32_t i;
 151
 152         if (likely(slab == 0)) {
 153                 return 0;
 154         }
 155
 156         for (i = 0, mask = 1; i < RTE_BITMAP_SLAB_BIT_SIZE; i ++, mask <<= 1) {
 157                 if (unlikely(slab & mask)) {
 158                         *pos = i;
 159                         return 1;
 160                 }
 161         }
 162
 163         return 0;
 164 }
 165
 166 #endif
 167
 168 static inline void
 169 __rte_bitmap_scan_init(struct rte_bitmap *bmp)
 170 {
 171         bmp->index1 = RTE_BITMAP_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 initialization
 181  *
 182  * @param bmp
 183  *   Handle to bitmap instance
 184  * @param array2
 185  *   Base address of pre-allocated array2
 186  * @param n_bits
 187  *   Number of pre-allocated bits in array2. Must be non-zero and multiple of 512.
 188  * @return
 189  *   0 upon success, error code otherwise
 190  */
 191 static inline int
 192 rte_bitmap_init(struct rte_bitmap *bmp, uint8_t *array2, uint32_t n_bits)
 193 {
 194         uint32_t array1_size, array2_size;
 195
 196         /* Check input arguments */
 197         if ((bmp == NULL) ||
 198             (array2 == NULL) || (((uintptr_t) array2) & CACHE_LINE_MASK) ||
 199                 (n_bits == 0) || (n_bits & RTE_BITMAP_CL_BIT_MASK)){
 200                 return -1;
 201         }
 202
 203         array2_size = n_bits / RTE_BITMAP_SLAB_BIT_SIZE;
 204         array1_size = ((n_bits / RTE_BITMAP_CL_BIT_SIZE) + (RTE_BITMAP_SLAB_BIT_SIZE - 1)) / RTE_BITMAP_SLAB_BIT_SIZE;
 205         if (array1_size > RTE_BITMAP_ARRAY1_SIZE){
 206                 return -1;
 207         }
 208
 209         /* Setup bitmap */
 210         memset(bmp, 0, sizeof(struct rte_bitmap));
 211         bmp->array2 = (uint64_t *) array2;
 212         bmp->array1_size = array1_size;
 213         bmp->array2_size = array2_size;
 214         __rte_bitmap_scan_init(bmp);
 215
 216         return 0;
 217 }
 218
 219 /**
 220  * Bitmap free
 221  *
 222  * @param bmp
 223  *   Handle to bitmap instance
 224  * @return
 225  *   0 upon success, error code otherwise
 226  */
 227 static inline int
 228 rte_bitmap_free(struct rte_bitmap *bmp)
 229 {
 230         /* Check input arguments */
 231         if (bmp == NULL) {
 232                 return -1;
 233         }
 234
 235         return 0;
 236 }
 237
 238 /**
 239  * Bitmap reset
 240  *
 241  * @param bmp
 242  *   Handle to bitmap instance
 243  */
 244 static inline void
 245 rte_bitmap_reset(struct rte_bitmap *bmp)
 246 {
 247         memset(bmp->array1, 0, sizeof(bmp->array1));
 248         memset(bmp->array2, 0, bmp->array2_size * sizeof(uint64_t));
 249         __rte_bitmap_scan_init(bmp);
 250 }
 251
 252 /**
 253  * Bitmap location prefetch into CPU L1 cache
 254  *
 255  * @param bmp
 256  *   Handle to bitmap instance
 257  * @param pos
 258  *   Bit position
 259  * @return
 260  *   0 upon success, error code otherwise
 261  */
 262 static inline void
 263 rte_bitmap_prefetch0(struct rte_bitmap *bmp, uint32_t pos)
 264 {
 265         uint64_t *slab2;
 266         uint32_t index2;
 267
 268         index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
 269         slab2 = bmp->array2 + index2;
 270         rte_prefetch0((void *) slab2);
 271 }
 272
 273 /**
 274  * Bitmap bit get
 275  *
 276  * @param bmp
 277  *   Handle to bitmap instance
 278  * @param pos
 279  *   Bit position
 280  * @return
 281  *   0 when bit is cleared, non-zero when bit is set
 282  */
 283 static inline uint64_t
 284 rte_bitmap_get(struct rte_bitmap *bmp, uint32_t pos)
 285 {
 286         uint64_t *slab2;
 287         uint32_t index2, offset2;
 288
 289         index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
 290         offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
 291         slab2 = bmp->array2 + index2;
 292         return ((*slab2) & (1lu << offset2));
 293 }
 294
 295 /**
 296  * Bitmap bit set
 297  *
 298  * @param bmp
 299  *   Handle to bitmap instance
 300  * @param pos
 301  *   Bit position
 302  */
 303 static inline void
 304 rte_bitmap_set(struct rte_bitmap *bmp, uint32_t pos)
 305 {
 306         uint64_t *slab1, *slab2;
 307         uint32_t index1, index2, offset1, offset2;
 308
 309         /* Set bit in array2 slab and set bit in array1 slab */
 310         index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
 311         offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
 312         index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
 313         offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
 314         slab2 = bmp->array2 + index2;
 315         slab1 = bmp->array1 + index1;
 316
 317         *slab2 |= 1lu << offset2;
 318         *slab1 |= 1lu << offset1;
 319 }
 320
 321 /**
 322  * Bitmap slab set
 323  *
 324  * @param bmp
 325  *   Handle to bitmap instance
 326  * @param pos
 327  *   Bit position identifying the array2 slab
 328  * @param slab
 329  *   Value to be assigned to the 64-bit slab in array2
 330  */
 331 static inline void
 332 rte_bitmap_set_slab(struct rte_bitmap *bmp, uint32_t pos, uint64_t slab)
 333 {
 334         uint64_t *slab1, *slab2;
 335         uint32_t index1, index2, offset1;
 336
 337         /* Set bits in array2 slab and set bit in array1 slab */
 338         index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
 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 |= slab;
 345         *slab1 |= 1lu << offset1;
 346 }
 347
 348 static inline uint64_t
 349 __rte_bitmap_line_not_empty(uint64_t *slab2)
 350 {
 351         uint64_t v1, v2, v3, v4;
 352
 353         v1 = slab2[0] | slab2[1];
 354         v2 = slab2[2] | slab2[3];
 355         v3 = slab2[4] | slab2[5];
 356         v4 = slab2[6] | slab2[7];
 357         v1 |= v2;
 358         v3 |= v4;
 359
 360         return (v1 | v3);
 361 }
 362
 363 /**
 364  * Bitmap bit clear
 365  *
 366  * @param bmp
 367  *   Handle to bitmap instance
 368  * @param pos
 369  *   Bit position
 370  */
 371 static inline void
 372 rte_bitmap_clear(struct rte_bitmap *bmp, uint32_t pos)
 373 {
 374         uint64_t *slab1, *slab2;
 375         uint32_t index1, index2, offset1, offset2;
 376
 377         /* Clear bit in array2 slab */
 378         index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
 379         offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
 380         slab2 = bmp->array2 + index2;
 381
 382         /* Return if array2 slab is not all-zeros */
 383         *slab2 &= ~(1lu << offset2);
 384         if (*slab2){
 385                 return;
 386         }
 387
 388         /* Check the entire cache line of array2 for all-zeros */
 389         index2 &= ~ RTE_BITMAP_CL_SLAB_MASK;
 390         slab2 = bmp->array2 + index2;
 391         if (__rte_bitmap_line_not_empty(slab2)) {
 392                 return;
 393         }
 394
 395         /* The array2 cache line is all-zeros, so clear bit in array1 slab */
 396         index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
 397         offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
 398         slab1 = bmp->array1 + index1;
 399         *slab1 &= ~(1lu << offset1);
 400
 401         return;
 402 }
 403
 404 static inline int
 405 __rte_bitmap_scan_search(struct rte_bitmap *bmp)
 406 {
 407         uint64_t value1;
 408         uint32_t i;
 409
 410         /* Check current array1 slab */
 411         value1 = bmp->array1[bmp->index1];
 412         value1 &= __rte_bitmap_mask1_get(bmp);
 413
 414         if (rte_bsf64(value1, &bmp->offset1)) {
 415                 return 1;
 416         }
 417
 418         __rte_bitmap_index1_inc(bmp);
 419         bmp->offset1 = 0;
 420
 421         /* Look for another array1 slab */
 422         for (i = 0; i < RTE_BITMAP_ARRAY1_SIZE; i ++, __rte_bitmap_index1_inc(bmp)) {
 423                 value1 = bmp->array1[bmp->index1];
 424
 425                 if (rte_bsf64(value1, &bmp->offset1)) {
 426                         return 1;
 427                 }
 428         }
 429
 430         return 0;
 431 }
 432
 433 static inline void
 434 __rte_bitmap_scan_read_init(struct rte_bitmap *bmp)
 435 {
 436         __rte_bitmap_index2_set(bmp);
 437         bmp->go2 = 1;
 438         rte_prefetch1((void *)(bmp->array2 + bmp->index2 + 8));
 439 }
 440
 441 static inline int
 442 __rte_bitmap_scan_read(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
 443 {
 444         uint64_t *slab2;
 445
 446         slab2 = bmp->array2 + bmp->index2;
 447         for ( ; bmp->go2 ; bmp->index2 ++, slab2 ++, bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK) {
 448                 if (*slab2) {
 449                         *pos = bmp->index2 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
 450                         *slab = *slab2;
 451
 452                         bmp->index2 ++;
 453                         slab2 ++;
 454                         bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK;
 455                         return 1;
 456                 }
 457         }
 458
 459         return 0;
 460 }
 461
 462 /**
 463  * Bitmap scan (with automatic wrap-around)
 464  *
 465  * @param bmp
 466  *   Handle to bitmap instance
 467  * @param pos
 468  *   When function call returns 1, pos contains the position of the next set
 469  *   bit, otherwise not modified
 470  * @param slab
 471  *   When function call returns 1, slab contains the value of the entire 64-bit
 472  *   slab where the bit indicated by pos is located. Slabs are always 64-bit
 473  *   aligned, so the position of the first bit of the slab (this bit is not
 474  *   necessarily set) is pos / 64. Once a slab has been returned by the bitmap
 475  *   scan operation, the internal pointers of the bitmap are updated to point
 476  *   after this slab, so the same slab will not be returned again if it
 477  *   contains more than one bit which is set. When function call returns 0,
 478  *   slab is not modified.
 479  * @return
 480  *   0 if there is no bit set in the bitmap, 1 otherwise
 481  */
 482 static inline int
 483 rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
 484 {
 485         /* Return data from current array2 line if available */
 486         if (__rte_bitmap_scan_read(bmp, pos, slab)) {
 487                 return 1;
 488         }
 489
 490         /* Look for non-empty array2 line */
 491         if (__rte_bitmap_scan_search(bmp)) {
 492                 __rte_bitmap_scan_read_init(bmp);
 493                 __rte_bitmap_scan_read(bmp, pos, slab);
 494                 return 1;
 495         }
 496
 497         /* Empty bitmap */
 498         return 0;
 499 }
 500
 501 #ifdef __cplusplus
 502 }
 503 #endif
 504
 505 #endif /* __INCLUDE_RTE_BITMAP_H__ */