Currently bitmap supports only forward scanning starting from zero bit position. This patch implements reverse scanning starting from highest bit position towards zero bit position.
Signed-off-by: Vivek Sharma <vivek.sha...@caviumnetworks.com> --- Prerequisite: * Note that this patchset is dependent on patch: 'http://patches.dpdk.org/patch/45307/' lib/librte_eal/common/include/rte_bitmap.h | 164 +++++++++++++++++++++++++---- 1 file changed, 143 insertions(+), 21 deletions(-) diff --git a/lib/librte_eal/common/include/rte_bitmap.h b/lib/librte_eal/common/include/rte_bitmap.h index 7a36ce7..4b3437e 100644 --- a/lib/librte_eal/common/include/rte_bitmap.h +++ b/lib/librte_eal/common/include/rte_bitmap.h @@ -61,6 +61,11 @@ extern "C" { #define RTE_BITMAP_CL_SLAB_SIZE_LOG2 (RTE_BITMAP_CL_BIT_SIZE_LOG2 - RTE_BITMAP_SLAB_BIT_SIZE_LOG2) #define RTE_BITMAP_CL_SLAB_MASK (RTE_BITMAP_CL_SLAB_SIZE - 1) +enum rte_scan_dir { + RTE_BITMAP_REV_SCAN = -1, + RTE_BITMAP_FWD_SCAN = 1 +}; + /** Bitmap data structure */ struct rte_bitmap { /* Context for array1 and array2 */ @@ -74,6 +79,7 @@ struct rte_bitmap { uint32_t offset1; /**< Bitmap scan: Offset of current bit within current array1 slab */ uint32_t index2; /**< Bitmap scan: Index of current array2 slab */ uint32_t go2; /**< Bitmap scan: Go/stop condition for current array2 cache line */ + enum rte_scan_dir dir; /**< Bitmap scan: Current scan direction */ /* Storage space for array1 and array2 */ uint8_t memory[]; @@ -82,13 +88,16 @@ struct rte_bitmap { static inline void __rte_bitmap_index1_inc(struct rte_bitmap *bmp) { - bmp->index1 = (bmp->index1 + 1) & (bmp->array1_size - 1); + bmp->index1 = (bmp->index1 + bmp->dir) & (bmp->array1_size - 1); } static inline uint64_t __rte_bitmap_mask1_get(struct rte_bitmap *bmp) { - return (~1llu) << bmp->offset1; + if (bmp->dir == RTE_BITMAP_FWD_SCAN) + return (~1llu) << bmp->offset1; + else + return (~0llu) ^ ((~0llu) << bmp->offset1); } static inline void @@ -110,6 +119,16 @@ rte_bsf64(uint64_t slab, uint32_t *pos) return 1; } +static inline int +rte_bsl64(uint64_t slab, uint32_t *pos) +{ + if (likely(!slab)) + return 0; + + *pos = RTE_BITMAP_SLAB_BIT_SIZE - 1 - __builtin_clzll(slab); + return 1; +} + #else static inline int @@ -132,6 +151,25 @@ rte_bsf64(uint64_t slab, uint32_t *pos) return 0; } +static inline int +rte_bsl64(uint64_t slab, uint32_t *pos) +{ + uint64_t mask; + int i; + + if (likely(!slab)) + return 0; + + for (i = RTE_BITMAP_SLAB_BIT_SIZE - 1, mask = 1; i >= 0; i--) { + if (unlikely(slab & (mask << i))) { + *pos = i; + return 1; + } + } + + return 0; +} + #endif static inline uint32_t @@ -167,16 +205,29 @@ __rte_bitmap_get_memory_footprint(uint32_t n_bits, } static inline void -__rte_bitmap_scan_init(struct rte_bitmap *bmp) +__rte_bitmap_scan_init_generic(struct rte_bitmap *bmp, enum rte_scan_dir dir) { - bmp->index1 = bmp->array1_size - 1; - bmp->offset1 = RTE_BITMAP_SLAB_BIT_SIZE - 1; - __rte_bitmap_index2_set(bmp); - bmp->index2 += RTE_BITMAP_CL_SLAB_SIZE; - + if (dir == RTE_BITMAP_FWD_SCAN) { + bmp->index1 = bmp->array1_size - 1; + bmp->offset1 = RTE_BITMAP_SLAB_BIT_SIZE - 1; + __rte_bitmap_index2_set(bmp); + bmp->index2 += RTE_BITMAP_CL_SLAB_SIZE; + bmp->dir = RTE_BITMAP_FWD_SCAN; + } else { + bmp->index1 = 0; + bmp->offset1 = 0; + bmp->index2 = 0; + bmp->dir = RTE_BITMAP_REV_SCAN; + } bmp->go2 = 0; } +static inline void +__rte_bitmap_scan_init(struct rte_bitmap *bmp) +{ + __rte_bitmap_scan_init_generic(bmp, RTE_BITMAP_FWD_SCAN); +} + /** * Bitmap memory footprint calculation * @@ -439,19 +490,32 @@ __rte_bitmap_scan_search(struct rte_bitmap *bmp) value1 = bmp->array1[bmp->index1]; value1 &= __rte_bitmap_mask1_get(bmp); - if (rte_bsf64(value1, &bmp->offset1)) { - return 1; + if (bmp->dir == RTE_BITMAP_FWD_SCAN) { + if (rte_bsf64(value1, &bmp->offset1)) + return 1; + } else { + if (rte_bsl64(value1, &bmp->offset1)) + return 1; } __rte_bitmap_index1_inc(bmp); - bmp->offset1 = 0; + + if (bmp->dir == RTE_BITMAP_FWD_SCAN) + bmp->offset1 = 0; + else + bmp->offset1 = RTE_BITMAP_SLAB_BIT_SIZE - 1; /* Look for another array1 slab */ - for (i = 0; i < bmp->array1_size; i ++, __rte_bitmap_index1_inc(bmp)) { + for (i = 0; i < bmp->array1_size; + i++, __rte_bitmap_index1_inc(bmp)) { value1 = bmp->array1[bmp->index1]; - if (rte_bsf64(value1, &bmp->offset1)) { - return 1; + if (bmp->dir == RTE_BITMAP_FWD_SCAN) { + if (rte_bsf64(value1, &bmp->offset1)) + return 1; + } else { + if (rte_bsl64(value1, &bmp->offset1)) + return 1; } } @@ -462,8 +526,12 @@ static inline void __rte_bitmap_scan_read_init(struct rte_bitmap *bmp) { __rte_bitmap_index2_set(bmp); + + if (bmp->dir == RTE_BITMAP_REV_SCAN) + bmp->index2 += RTE_BITMAP_CL_SLAB_SIZE - 1; + bmp->go2 = 1; - rte_prefetch1((void *)(bmp->array2 + bmp->index2 + 8)); + rte_prefetch1((void *)(bmp->array2 + bmp->index2 + 8 * bmp->dir)); } static inline int @@ -472,23 +540,42 @@ __rte_bitmap_scan_read(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab) uint64_t *slab2; slab2 = bmp->array2 + bmp->index2; - for ( ; bmp->go2 ; bmp->index2 ++, slab2 ++, bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK) { + + for ( ; bmp->go2; ) { if (*slab2) { *pos = bmp->index2 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2; *slab = *slab2; - bmp->index2 ++; - slab2 ++; - bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK; + bmp->index2 += bmp->dir; + slab2 += bmp->dir; + + if (bmp->dir == RTE_BITMAP_FWD_SCAN) + bmp->go2 = + bmp->index2 & RTE_BITMAP_CL_SLAB_MASK; + else + /* stop once index2 crosses zero while + * decreasing. + */ + bmp->go2 = (bmp->index2 ^ (~0)); return 1; } + + bmp->index2 += bmp->dir; + slab2 += bmp->dir; + + if (bmp->dir == RTE_BITMAP_FWD_SCAN) + bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK; + else + bmp->go2 = (bmp->index2 ^ (~0)); + + bmp->index2 &= RTE_BITMAP_CL_SLAB_MASK; } return 0; } /** - * Bitmap scan (with automatic wrap-around) + * Bitmap scan generic (with automatic wrap-around) * * @param bmp * Handle to bitmap instance @@ -504,12 +591,20 @@ __rte_bitmap_scan_read(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab) * after this slab, so the same slab will not be returned again if it * contains more than one bit which is set. When function call returns 0, * slab is not modified. + * @param dir + * Scanning direction, whether in forward/positive(increasing bit index) + * or reverse/backward/negative(decreasing bit index) direction. * @return * 0 if there is no bit set in the bitmap, 1 otherwise */ static inline int -rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab) +rte_bitmap_scan_generic(struct rte_bitmap *bmp, uint32_t *pos, + uint64_t *slab, enum rte_scan_dir dir) { + /* Init scan parameters as per requested scan direction */ + if (unlikely(bmp->dir != dir)) + __rte_bitmap_scan_init_generic(bmp, dir); + /* Return data from current array2 line if available */ if (__rte_bitmap_scan_read(bmp, pos, slab)) { return 1; @@ -526,6 +621,33 @@ rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab) return 0; } +/** + * Bitmap scan (with automatic wrap-around) + * + * @param bmp + * Handle to bitmap instance + * @param pos + * When function call returns 1, pos contains the position of the next set + * bit, otherwise not modified + * @param slab + * When function call returns 1, slab contains the value of the entire 64-bit + * slab where the bit indicated by pos is located. Slabs are always 64-bit + * aligned, so the position of the first bit of the slab (this bit is not + * necessarily set) is pos / 64. Once a slab has been returned by the bitmap + * scan operation, the internal pointers of the bitmap are updated to point + * after this slab, so the same slab will not be returned again if it + * contains more than one bit which is set. When function call returns 0, + * slab is not modified. + * @return + * 0 if there is no bit set in the bitmap, 1 otherwise + */ +static inline int +rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, + uint64_t *slab) +{ + return rte_bitmap_scan_generic(bmp, pos, slab, RTE_BITMAP_FWD_SCAN); +} + #ifdef __cplusplus } #endif -- 2.7.4
