[PATCH 1/2] eal/bitmap: support bitmap reverse scanning

[Vivek Sharma <vivek.sharma@caviumnetworks.com>]

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.sharma@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