[dpdk-dev] [PATCH 1/2] eal: move bitmap from lib sched

[dpdk-dev] [PATCH 1/2] eal: move bitmap from lib sched

[Pavan Nikhilesh]

The librte_sched uses rte_bitmap to manage large arrays of bits in an
optimized method so, moving it to eal/common would allow other libraries
and applications to use it.

Signed-off-by: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
---
 lib/librte_eal/common/Makefile                     |   1 +
 .../common/include}/rte_bitmap.h                   | 100 +++++++++++++--------
 lib/librte_sched/Makefile                          |   5 +-
 lib/librte_sched/rte_sched.c                       |   2 +-
 4 files changed, 70 insertions(+), 38 deletions(-)
 rename lib/{librte_sched => librte_eal/common/include}/rte_bitmap.h (85%)

diff --git a/lib/librte_eal/common/Makefile b/lib/librte_eal/common/Makefile
index e8fd67a..c2c6a7f 100644
--- a/lib/librte_eal/common/Makefile
+++ b/lib/librte_eal/common/Makefile
@@ -42,6 +42,7 @@ INC += rte_hexdump.h rte_devargs.h rte_bus.h rte_dev.h rte_vdev.h
 INC += rte_pci_dev_feature_defs.h rte_pci_dev_features.h
 INC += rte_malloc.h rte_keepalive.h rte_time.h
 INC += rte_service.h rte_service_component.h
+INC += rte_bitmap.h
 
 GENERIC_INC := rte_atomic.h rte_byteorder.h rte_cycles.h rte_prefetch.h
 GENERIC_INC += rte_spinlock.h rte_memcpy.h rte_cpuflags.h rte_rwlock.h
diff --git a/lib/librte_sched/rte_bitmap.h b/lib/librte_eal/common/include/rte_bitmap.h
similarity index 85%
rename from lib/librte_sched/rte_bitmap.h
rename to lib/librte_eal/common/include/rte_bitmap.h
index 010d752..0938c63 100644
--- a/lib/librte_sched/rte_bitmap.h
+++ b/lib/librte_eal/common/include/rte_bitmap.h
@@ -65,6 +65,7 @@ extern "C" {
  ***/
 
 #include <string.h>
+
 #include <rte_common.h>
 #include <rte_debug.h>
 #include <rte_memory.h>
@@ -72,36 +73,46 @@ extern "C" {
 #include <rte_prefetch.h>
 
 #ifndef RTE_BITMAP_OPTIMIZATIONS
-#define RTE_BITMAP_OPTIMIZATIONS		         1
+#define RTE_BITMAP_OPTIMIZATIONS        1
 #endif
 
 /* Slab */
-#define RTE_BITMAP_SLAB_BIT_SIZE                 64
-#define RTE_BITMAP_SLAB_BIT_SIZE_LOG2            6
-#define RTE_BITMAP_SLAB_BIT_MASK                 (RTE_BITMAP_SLAB_BIT_SIZE - 1)
+#define RTE_BITMAP_SLAB_BIT_SIZE        64
+#define RTE_BITMAP_SLAB_BIT_SIZE_LOG2   6
+#define RTE_BITMAP_SLAB_BIT_MASK        (RTE_BITMAP_SLAB_BIT_SIZE - 1)
 
 /* Cache line (CL) */
-#define RTE_BITMAP_CL_BIT_SIZE                   (RTE_CACHE_LINE_SIZE * 8)
-#define RTE_BITMAP_CL_BIT_SIZE_LOG2              (RTE_CACHE_LINE_SIZE_LOG2 + 3)
-#define RTE_BITMAP_CL_BIT_MASK                   (RTE_BITMAP_CL_BIT_SIZE - 1)
+#define RTE_BITMAP_CL_BIT_SIZE          (RTE_CACHE_LINE_SIZE * 8)
+#define RTE_BITMAP_CL_BIT_SIZE_LOG2     (RTE_CACHE_LINE_SIZE_LOG2 + 3)
+#define RTE_BITMAP_CL_BIT_MASK          (RTE_BITMAP_CL_BIT_SIZE - 1)
 
-#define RTE_BITMAP_CL_SLAB_SIZE                  (RTE_BITMAP_CL_BIT_SIZE / RTE_BITMAP_SLAB_BIT_SIZE)
-#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)
+#define RTE_BITMAP_CL_SLAB_SIZE         \
+	(RTE_BITMAP_CL_BIT_SIZE / RTE_BITMAP_SLAB_BIT_SIZE)
+#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)
 
 /** Bitmap data structure */
 struct rte_bitmap {
 	/* Context for array1 and array2 */
-	uint64_t *array1;                        /**< Bitmap array1 */
-	uint64_t *array2;                        /**< Bitmap array2 */
-	uint32_t array1_size;                    /**< Number of 64-bit slabs in array1 that are actually used */
-	uint32_t array2_size;                    /**< Number of 64-bit slabs in array2 */
+	uint64_t *array1;
+	/**< Bitmap array1 */
+	uint64_t *array2;
+	/**< Bitmap array2 */
+	uint32_t array1_size;
+	/**< Number of 64-bit slabs in array1 that are actually used */
+	uint32_t array2_size;
+	/**< Number of 64-bit slabs in array2 */
 
 	/* Context for the "scan next" operation */
-	uint32_t index1;  /**< Bitmap scan: Index of current array1 slab */
-	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 */
+	uint32_t index1;
+	/**< Bitmap scan: Index of current array1 slab */
+	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 */
 
 	/* Storage space for array1 and array2 */
 	uint8_t memory[];
@@ -122,7 +133,8 @@ __rte_bitmap_mask1_get(struct rte_bitmap *bmp)
 static inline void
 __rte_bitmap_index2_set(struct rte_bitmap *bmp)
 {
-	bmp->index2 = (((bmp->index1 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2) + bmp->offset1) << RTE_BITMAP_CL_SLAB_SIZE_LOG2);
+	bmp->index2 = (((bmp->index1 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2) +
+				bmp->offset1) << RTE_BITMAP_CL_SLAB_SIZE_LOG2);
 }
 
 #if RTE_BITMAP_OPTIMIZATIONS
@@ -171,12 +183,18 @@ __rte_bitmap_get_memory_footprint(uint32_t n_bits,
 	uint32_t n_cache_lines_array2;
 	uint32_t n_bytes_total;
 
-	n_cache_lines_array2 = (n_bits + RTE_BITMAP_CL_BIT_SIZE - 1) / RTE_BITMAP_CL_BIT_SIZE;
-	n_slabs_array1 = (n_cache_lines_array2 + RTE_BITMAP_SLAB_BIT_SIZE - 1) / RTE_BITMAP_SLAB_BIT_SIZE;
+	n_cache_lines_array2 = (n_bits + RTE_BITMAP_CL_BIT_SIZE - 1) /
+		RTE_BITMAP_CL_BIT_SIZE;
+	n_slabs_array1 = (n_cache_lines_array2 + RTE_BITMAP_SLAB_BIT_SIZE - 1) /
+		RTE_BITMAP_SLAB_BIT_SIZE;
 	n_slabs_array1 = rte_align32pow2(n_slabs_array1);
-	n_slabs_context = (sizeof(struct rte_bitmap) + (RTE_BITMAP_SLAB_BIT_SIZE / 8) - 1) / (RTE_BITMAP_SLAB_BIT_SIZE / 8);
-	n_cache_lines_context_and_array1 = (n_slabs_context + n_slabs_array1 + RTE_BITMAP_CL_SLAB_SIZE - 1) / RTE_BITMAP_CL_SLAB_SIZE;
-	n_bytes_total = (n_cache_lines_context_and_array1 + n_cache_lines_array2) * RTE_CACHE_LINE_SIZE;
+	n_slabs_context = (sizeof(struct rte_bitmap) +
+			(RTE_BITMAP_SLAB_BIT_SIZE / 8) - 1) /
+		(RTE_BITMAP_SLAB_BIT_SIZE / 8);
+	n_cache_lines_context_and_array1 = (n_slabs_context + n_slabs_array1 +
+			RTE_BITMAP_CL_SLAB_SIZE - 1) / RTE_BITMAP_CL_SLAB_SIZE;
+	n_bytes_total = (n_cache_lines_context_and_array1 +
+			n_cache_lines_array2) * RTE_CACHE_LINE_SIZE;
 
 	if (array1_byte_offset) {
 		*array1_byte_offset = n_slabs_context * (RTE_BITMAP_SLAB_BIT_SIZE / 8);
@@ -185,7 +203,8 @@ __rte_bitmap_get_memory_footprint(uint32_t n_bits,
 		*array1_slabs = n_slabs_array1;
 	}
 	if (array2_byte_offset) {
-		*array2_byte_offset = n_cache_lines_context_and_array1 * RTE_CACHE_LINE_SIZE;
+		*array2_byte_offset = n_cache_lines_context_and_array1 *
+			RTE_CACHE_LINE_SIZE;
 	}
 	if (array2_slabs) {
 		*array2_slabs = n_cache_lines_array2 * RTE_BITMAP_CL_SLAB_SIZE;
@@ -210,6 +229,7 @@ __rte_bitmap_scan_init(struct rte_bitmap *bmp)
  *
  * @param n_bits
  *   Number of bits in the bitmap
+ *
  * @return
  *   Bitmap memory footprint measured in bytes on success, 0 on error
  */
@@ -226,12 +246,14 @@ rte_bitmap_get_memory_footprint(uint32_t n_bits) {
 /**
  * Bitmap initialization
  *
- * @param mem_size
- *   Minimum expected size of bitmap.
+ * @param n_bits
+ *   Number of pre-allocated bits in array2. Must be non-zero and multiple of
+ *   512.
  * @param mem
  *   Base address of array1 and array2.
- * @param n_bits
- *   Number of pre-allocated bits in array2. Must be non-zero and multiple of 512.
+ * @param mem_size
+ *   Minimum expected size of bitmap.
+ *
  * @return
  *   Handle to bitmap instance.
  */
@@ -277,6 +299,7 @@ rte_bitmap_init(uint32_t n_bits, uint8_t *mem, uint32_t mem_size)
  *
  * @param bmp
  *   Handle to bitmap instance
+ *
  * @return
  *   0 upon success, error code otherwise
  */
@@ -312,6 +335,7 @@ rte_bitmap_reset(struct rte_bitmap *bmp)
  *   Handle to bitmap instance
  * @param pos
  *   Bit position
+ *
  * @return
  *   0 upon success, error code otherwise
  */
@@ -333,6 +357,7 @@ rte_bitmap_prefetch0(struct rte_bitmap *bmp, uint32_t pos)
  *   Handle to bitmap instance
  * @param pos
  *   Bit position
+ *
  * @return
  *   0 when bit is cleared, non-zero when bit is set
  */
@@ -365,7 +390,8 @@ rte_bitmap_set(struct rte_bitmap *bmp, uint32_t pos)
 	/* Set bit in array2 slab and set bit in array1 slab */
 	index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
 	offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
-	index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
+	index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 +
+			RTE_BITMAP_CL_BIT_SIZE_LOG2);
 	offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
 	slab2 = bmp->array2 + index2;
 	slab1 = bmp->array1 + index1;
@@ -392,7 +418,8 @@ rte_bitmap_set_slab(struct rte_bitmap *bmp, uint32_t pos, uint64_t slab)
 
 	/* Set bits in array2 slab and set bit in array1 slab */
 	index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
-	index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
+	index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 +
+			RTE_BITMAP_CL_BIT_SIZE_LOG2);
 	offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
 	slab2 = bmp->array2 + index2;
 	slab1 = bmp->array1 + index1;
@@ -449,7 +476,8 @@ rte_bitmap_clear(struct rte_bitmap *bmp, uint32_t pos)
 	}
 
 	/* The array2 cache line is all-zeros, so clear bit in array1 slab */
-	index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
+	index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 +
+			RTE_BITMAP_CL_BIT_SIZE_LOG2);
 	offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
 	slab1 = bmp->array1 + index1;
 	*slab1 &= ~(1lu << offset1);
@@ -500,7 +528,8 @@ __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 ; bmp->index2 ++, slab2 ++,
+			bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK) {
 		if (*slab2) {
 			*pos = bmp->index2 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
 			*slab = *slab2;
@@ -520,10 +549,10 @@ __rte_bitmap_scan_read(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
  *
  * @param bmp
  *   Handle to bitmap instance
- * @param pos
+ * @param[out] pos
  *   When function call returns 1, pos contains the position of the next set
  *   bit, otherwise not modified
- * @param slab
+ * @param[out] 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
@@ -532,6 +561,7 @@ __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.
+ *
  * @return
  *   0 if there is no bit set in the bitmap, 1 otherwise
  */
diff --git a/lib/librte_sched/Makefile b/lib/librte_sched/Makefile
index 18274e7..072cd63 100644
--- a/lib/librte_sched/Makefile
+++ b/lib/librte_sched/Makefile
@@ -55,7 +55,8 @@ SRCS-$(CONFIG_RTE_LIBRTE_SCHED) += rte_sched.c rte_red.c rte_approx.c
 SRCS-$(CONFIG_RTE_LIBRTE_SCHED) += rte_reciprocal.c
 
 # install includes
-SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include := rte_sched.h rte_bitmap.h rte_sched_common.h rte_red.h rte_approx.h
-SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include += rte_reciprocal.h
+SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include := rte_sched.h
+SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include += rte_sched_common.h rte_red.h
+SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include += rte_approx.h
 
 include $(RTE_SDK)/mk/rte.lib.mk
diff --git a/lib/librte_sched/rte_sched.c b/lib/librte_sched/rte_sched.c
index b7cba11..b3e0d4f 100644
--- a/lib/librte_sched/rte_sched.c
+++ b/lib/librte_sched/rte_sched.c
@@ -34,6 +34,7 @@
 #include <stdio.h>
 #include <string.h>
 
+#include <rte_bitmap.h>
 #include <rte_common.h>
 #include <rte_log.h>
 #include <rte_memory.h>
@@ -44,7 +45,6 @@
 #include <rte_mbuf.h>
 
 #include "rte_sched.h"
-#include "rte_bitmap.h"
 #include "rte_sched_common.h"
 #include "rte_approx.h"
 #include "rte_reciprocal.h"
-- 
2.7.4

[dpdk-dev] [PATCH 2/2] test: add test for bitmap operations

[Pavan Nikhilesh]

This patch adds a test for verifying the bitmap operations.

Signed-off-by: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
---
 test/test/Makefile      |   1 +
 test/test/test_bitmap.c | 192 ++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 193 insertions(+)
 create mode 100644 test/test/test_bitmap.c

diff --git a/test/test/Makefile b/test/test/Makefile
index 42d9a49..2fda8d9 100644
--- a/test/test/Makefile
+++ b/test/test/Makefile
@@ -94,6 +94,7 @@ SRCS-y += test_cycles.c
 SRCS-y += test_spinlock.c
 SRCS-y += test_memory.c
 SRCS-y += test_memzone.c
+SRCS-y += test_bitmap.c
 
 SRCS-y += test_ring.c
 SRCS-y += test_ring_perf.c
diff --git a/test/test/test_bitmap.c b/test/test/test_bitmap.c
new file mode 100644
index 0000000..5c9eee9
--- /dev/null
+++ b/test/test/test_bitmap.c
@@ -0,0 +1,192 @@
+/*
+ *   BSD LICENSE
+ *
+ *   Copyright (C) Cavium, Inc. 2017.
+ *
+ *   Redistribution and use in source and binary forms, with or without
+ *   modification, are permitted provided that the following conditions
+ *   are met:
+ *
+ *     * Redistributions of source code must retain the above copyright
+ *       notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above copyright
+ *       notice, this list of conditions and the following disclaimer in
+ *       the documentation and/or other materials provided with the
+ *       distribution.
+ *     * Neither the name of Cavium, Inc nor the names of its
+ *       contributors may be used to endorse or promote products derived
+ *       from this software without specific prior written permission.
+ *
+ *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <inttypes.h>
+
+#include <rte_common.h>
+#include <rte_bitmap.h>
+#include <rte_malloc.h>
+
+#include "test.h"
+
+#define MAX_BITS 1000
+
+static int
+test_bitmap_scan_operations(struct rte_bitmap *bmp)
+{
+	uint32_t pos = 0;
+	uint64_t slab1_magic = 0xBADC0FFEEBADF00D;
+	uint64_t slab2_magic = 0xFEEDDEADDEADF00D;
+	uint64_t out_slab = 0;
+
+	rte_bitmap_reset(bmp);
+
+	rte_bitmap_set_slab(bmp, pos, slab1_magic);
+	rte_bitmap_set_slab(bmp, pos + RTE_BITMAP_SLAB_BIT_SIZE, slab2_magic);
+
+	if (!rte_bitmap_scan(bmp, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab1_magic != out_slab) {
+		printf("Scan operation sanity failed.\n");
+		return TEST_FAILED;
+	}
+
+	if (!rte_bitmap_scan(bmp, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab2_magic != out_slab) {
+		printf("Scan operation sanity failed.\n");
+		return TEST_FAILED;
+	}
+
+	/* Wrap around */
+	if (!rte_bitmap_scan(bmp, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab1_magic != out_slab) {
+		printf("Scan operation wrap around failed.\n");
+		return TEST_FAILED;
+	}
+
+	/* Scan reset check. */
+	__rte_bitmap_scan_init(bmp);
+
+	if (!rte_bitmap_scan(bmp, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab1_magic != out_slab) {
+		printf("Scan reset operation failed.\n");
+		return TEST_FAILED;
+	}
+
+	return TEST_SUCCESS;
+}
+
+static int
+test_bitmap_slab_set_get(struct rte_bitmap *bmp)
+{
+	uint32_t pos = 0;
+	uint64_t slab_magic = 0xBADC0FFEEBADF00D;
+	uint64_t out_slab = 0;
+
+	rte_bitmap_reset(bmp);
+	rte_bitmap_set_slab(bmp, pos, slab_magic);
+
+	if (!rte_bitmap_scan(bmp, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap.\n");
+		return TEST_FAILED;
+	}
+
+
+	if (slab_magic != out_slab) {
+		printf("Invalid slab in bitmap.\n");
+		return TEST_FAILED;
+	}
+
+
+	return TEST_SUCCESS;
+}
+
+static int
+test_bitmap_set_get_clear(struct rte_bitmap *bmp)
+{
+	int i;
+
+	rte_bitmap_reset(bmp);
+	for (i = 0; i < MAX_BITS; i++)
+		rte_bitmap_set(bmp, i);
+
+	for (i = 0; i < MAX_BITS; i++) {
+		if (!rte_bitmap_get(bmp, i)) {
+			printf("Failed to get set bit.\n");
+			return TEST_FAILED;
+		}
+	}
+
+	for (i = 0; i < MAX_BITS; i++)
+		rte_bitmap_clear(bmp, i);
+
+	for (i = 0; i < MAX_BITS; i++) {
+		if (rte_bitmap_get(bmp, i)) {
+			printf("Failed to clear set bit.\n");
+			return TEST_FAILED;
+		}
+	}
+
+	return TEST_SUCCESS;
+}
+
+static int
+test_bitmap(void)
+{
+	void *mem;
+	uint32_t bmp_size;
+	struct rte_bitmap *bmp;
+
+	bmp_size =
+		rte_bitmap_get_memory_footprint(MAX_BITS);
+
+	mem = rte_zmalloc("test_bmap", bmp_size, RTE_CACHE_LINE_SIZE);
+	if (mem == NULL) {
+		printf("Failed to allocate memory for bitmap\n");
+		return TEST_FAILED;
+	}
+
+	bmp = rte_bitmap_init(MAX_BITS, mem, bmp_size);
+	if (bmp == NULL) {
+		printf("Failed to init bitmap\n");
+		return TEST_FAILED;
+	}
+
+	if (test_bitmap_set_get_clear(bmp) < 0)
+		return TEST_FAILED;
+
+	if (test_bitmap_slab_set_get(bmp) < 0)
+		return TEST_FAILED;
+
+	if (test_bitmap_scan_operations(bmp) < 0)
+		return TEST_FAILED;
+
+	return TEST_SUCCESS;
+}
+
+REGISTER_TEST_COMMAND(bitmap_test, test_bitmap);
-- 
2.7.4

Re: [dpdk-dev] [PATCH 1/2] eal: move bitmap from lib sched

[Dumitrescu, Cristian]

> -----Original Message-----
> From: Pavan Nikhilesh [mailto:pbhagavatula@caviumnetworks.com]
> Sent: Thursday, September 7, 2017 3:40 PM
> To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>;
> stephen@networkplumber.org
> Cc: dev@dpdk.org; Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
> Subject: [dpdk-dev] [PATCH 1/2] eal: move bitmap from lib sched
> 
> The librte_sched uses rte_bitmap to manage large arrays of bits in an
> optimized method so, moving it to eal/common would allow other libraries
> and applications to use it.
> 
> Signed-off-by: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
> ---
>  lib/librte_eal/common/Makefile                     |   1 +
>  .../common/include}/rte_bitmap.h                   | 100 +++++++++++++--------
>  lib/librte_sched/Makefile                          |   5 +-
>  lib/librte_sched/rte_sched.c                       |   2 +-
>  4 files changed, 70 insertions(+), 38 deletions(-)
>  rename lib/{librte_sched => librte_eal/common/include}/rte_bitmap.h
> (85%)
> 
> diff --git a/lib/librte_eal/common/Makefile
> b/lib/librte_eal/common/Makefile
> index e8fd67a..c2c6a7f 100644
> --- a/lib/librte_eal/common/Makefile
> +++ b/lib/librte_eal/common/Makefile
> @@ -42,6 +42,7 @@ INC += rte_hexdump.h rte_devargs.h rte_bus.h
> rte_dev.h rte_vdev.h
>  INC += rte_pci_dev_feature_defs.h rte_pci_dev_features.h
>  INC += rte_malloc.h rte_keepalive.h rte_time.h
>  INC += rte_service.h rte_service_component.h
> +INC += rte_bitmap.h
> 
>  GENERIC_INC := rte_atomic.h rte_byteorder.h rte_cycles.h rte_prefetch.h
>  GENERIC_INC += rte_spinlock.h rte_memcpy.h rte_cpuflags.h rte_rwlock.h
> diff --git a/lib/librte_sched/rte_bitmap.h
> b/lib/librte_eal/common/include/rte_bitmap.h
> similarity index 85%
> rename from lib/librte_sched/rte_bitmap.h
> rename to lib/librte_eal/common/include/rte_bitmap.h
> index 010d752..0938c63 100644
> --- a/lib/librte_sched/rte_bitmap.h
> +++ b/lib/librte_eal/common/include/rte_bitmap.h
> @@ -65,6 +65,7 @@ extern "C" {
>   ***/
> 
>  #include <string.h>
> +
>  #include <rte_common.h>
>  #include <rte_debug.h>
>  #include <rte_memory.h>
> @@ -72,36 +73,46 @@ extern "C" {
>  #include <rte_prefetch.h>
> 
>  #ifndef RTE_BITMAP_OPTIMIZATIONS
> -#define RTE_BITMAP_OPTIMIZATIONS		         1
> +#define RTE_BITMAP_OPTIMIZATIONS        1
>  #endif
> 
>  /* Slab */
> -#define RTE_BITMAP_SLAB_BIT_SIZE                 64
> -#define RTE_BITMAP_SLAB_BIT_SIZE_LOG2            6
> -#define RTE_BITMAP_SLAB_BIT_MASK
> (RTE_BITMAP_SLAB_BIT_SIZE - 1)
> +#define RTE_BITMAP_SLAB_BIT_SIZE        64
> +#define RTE_BITMAP_SLAB_BIT_SIZE_LOG2   6
> +#define RTE_BITMAP_SLAB_BIT_MASK        (RTE_BITMAP_SLAB_BIT_SIZE -
> 1)
> 
>  /* Cache line (CL) */
> -#define RTE_BITMAP_CL_BIT_SIZE                   (RTE_CACHE_LINE_SIZE * 8)
> -#define RTE_BITMAP_CL_BIT_SIZE_LOG2
> (RTE_CACHE_LINE_SIZE_LOG2 + 3)
> -#define RTE_BITMAP_CL_BIT_MASK                   (RTE_BITMAP_CL_BIT_SIZE -
> 1)
> +#define RTE_BITMAP_CL_BIT_SIZE          (RTE_CACHE_LINE_SIZE * 8)
> +#define RTE_BITMAP_CL_BIT_SIZE_LOG2     (RTE_CACHE_LINE_SIZE_LOG2
> + 3)
> +#define RTE_BITMAP_CL_BIT_MASK          (RTE_BITMAP_CL_BIT_SIZE - 1)
> 
> -#define RTE_BITMAP_CL_SLAB_SIZE                  (RTE_BITMAP_CL_BIT_SIZE /
> RTE_BITMAP_SLAB_BIT_SIZE)
> -#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)
> +#define RTE_BITMAP_CL_SLAB_SIZE         \
> +	(RTE_BITMAP_CL_BIT_SIZE / RTE_BITMAP_SLAB_BIT_SIZE)
> +#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)
> 
>  /** Bitmap data structure */
>  struct rte_bitmap {
>  	/* Context for array1 and array2 */
> -	uint64_t *array1;                        /**< Bitmap array1 */
> -	uint64_t *array2;                        /**< Bitmap array2 */
> -	uint32_t array1_size;                    /**< Number of 64-bit slabs in array1
> that are actually used */
> -	uint32_t array2_size;                    /**< Number of 64-bit slabs in array2
> */
> +	uint64_t *array1;
> +	/**< Bitmap array1 */
> +	uint64_t *array2;
> +	/**< Bitmap array2 */
> +	uint32_t array1_size;
> +	/**< Number of 64-bit slabs in array1 that are actually used */
> +	uint32_t array2_size;
> +	/**< Number of 64-bit slabs in array2 */
> 
>  	/* Context for the "scan next" operation */
> -	uint32_t index1;  /**< Bitmap scan: Index of current array1 slab */
> -	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 */
> +	uint32_t index1;
> +	/**< Bitmap scan: Index of current array1 slab */
> +	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 */
> 
>  	/* Storage space for array1 and array2 */
>  	uint8_t memory[];
> @@ -122,7 +133,8 @@ __rte_bitmap_mask1_get(struct rte_bitmap *bmp)
>  static inline void
>  __rte_bitmap_index2_set(struct rte_bitmap *bmp)
>  {
> -	bmp->index2 = (((bmp->index1 <<
> RTE_BITMAP_SLAB_BIT_SIZE_LOG2) + bmp->offset1) <<
> RTE_BITMAP_CL_SLAB_SIZE_LOG2);
> +	bmp->index2 = (((bmp->index1 <<
> RTE_BITMAP_SLAB_BIT_SIZE_LOG2) +
> +				bmp->offset1) <<
> RTE_BITMAP_CL_SLAB_SIZE_LOG2);
>  }
> 
>  #if RTE_BITMAP_OPTIMIZATIONS
> @@ -171,12 +183,18 @@ __rte_bitmap_get_memory_footprint(uint32_t
> n_bits,
>  	uint32_t n_cache_lines_array2;
>  	uint32_t n_bytes_total;
> 
> -	n_cache_lines_array2 = (n_bits + RTE_BITMAP_CL_BIT_SIZE - 1) /
> RTE_BITMAP_CL_BIT_SIZE;
> -	n_slabs_array1 = (n_cache_lines_array2 +
> RTE_BITMAP_SLAB_BIT_SIZE - 1) / RTE_BITMAP_SLAB_BIT_SIZE;
> +	n_cache_lines_array2 = (n_bits + RTE_BITMAP_CL_BIT_SIZE - 1) /
> +		RTE_BITMAP_CL_BIT_SIZE;
> +	n_slabs_array1 = (n_cache_lines_array2 +
> RTE_BITMAP_SLAB_BIT_SIZE - 1) /
> +		RTE_BITMAP_SLAB_BIT_SIZE;
>  	n_slabs_array1 = rte_align32pow2(n_slabs_array1);
> -	n_slabs_context = (sizeof(struct rte_bitmap) +
> (RTE_BITMAP_SLAB_BIT_SIZE / 8) - 1) / (RTE_BITMAP_SLAB_BIT_SIZE / 8);
> -	n_cache_lines_context_and_array1 = (n_slabs_context +
> n_slabs_array1 + RTE_BITMAP_CL_SLAB_SIZE - 1) /
> RTE_BITMAP_CL_SLAB_SIZE;
> -	n_bytes_total = (n_cache_lines_context_and_array1 +
> n_cache_lines_array2) * RTE_CACHE_LINE_SIZE;
> +	n_slabs_context = (sizeof(struct rte_bitmap) +
> +			(RTE_BITMAP_SLAB_BIT_SIZE / 8) - 1) /
> +		(RTE_BITMAP_SLAB_BIT_SIZE / 8);
> +	n_cache_lines_context_and_array1 = (n_slabs_context +
> n_slabs_array1 +
> +			RTE_BITMAP_CL_SLAB_SIZE - 1) /
> RTE_BITMAP_CL_SLAB_SIZE;
> +	n_bytes_total = (n_cache_lines_context_and_array1 +
> +			n_cache_lines_array2) * RTE_CACHE_LINE_SIZE;
> 
>  	if (array1_byte_offset) {
>  		*array1_byte_offset = n_slabs_context *
> (RTE_BITMAP_SLAB_BIT_SIZE / 8);
> @@ -185,7 +203,8 @@ __rte_bitmap_get_memory_footprint(uint32_t
> n_bits,
>  		*array1_slabs = n_slabs_array1;
>  	}
>  	if (array2_byte_offset) {
> -		*array2_byte_offset = n_cache_lines_context_and_array1 *
> RTE_CACHE_LINE_SIZE;
> +		*array2_byte_offset = n_cache_lines_context_and_array1 *
> +			RTE_CACHE_LINE_SIZE;
>  	}
>  	if (array2_slabs) {
>  		*array2_slabs = n_cache_lines_array2 *
> RTE_BITMAP_CL_SLAB_SIZE;
> @@ -210,6 +229,7 @@ __rte_bitmap_scan_init(struct rte_bitmap *bmp)
>   *
>   * @param n_bits
>   *   Number of bits in the bitmap
> + *
>   * @return
>   *   Bitmap memory footprint measured in bytes on success, 0 on error
>   */
> @@ -226,12 +246,14 @@ rte_bitmap_get_memory_footprint(uint32_t
> n_bits) {
>  /**
>   * Bitmap initialization
>   *
> - * @param mem_size
> - *   Minimum expected size of bitmap.
> + * @param n_bits
> + *   Number of pre-allocated bits in array2. Must be non-zero and multiple
> of
> + *   512.
>   * @param mem
>   *   Base address of array1 and array2.
> - * @param n_bits
> - *   Number of pre-allocated bits in array2. Must be non-zero and multiple of
> 512.
> + * @param mem_size
> + *   Minimum expected size of bitmap.
> + *
>   * @return
>   *   Handle to bitmap instance.
>   */
> @@ -277,6 +299,7 @@ rte_bitmap_init(uint32_t n_bits, uint8_t *mem,
> uint32_t mem_size)
>   *
>   * @param bmp
>   *   Handle to bitmap instance
> + *
>   * @return
>   *   0 upon success, error code otherwise
>   */
> @@ -312,6 +335,7 @@ rte_bitmap_reset(struct rte_bitmap *bmp)
>   *   Handle to bitmap instance
>   * @param pos
>   *   Bit position
> + *
>   * @return
>   *   0 upon success, error code otherwise
>   */
> @@ -333,6 +357,7 @@ rte_bitmap_prefetch0(struct rte_bitmap *bmp,
> uint32_t pos)
>   *   Handle to bitmap instance
>   * @param pos
>   *   Bit position
> + *
>   * @return
>   *   0 when bit is cleared, non-zero when bit is set
>   */
> @@ -365,7 +390,8 @@ rte_bitmap_set(struct rte_bitmap *bmp, uint32_t
> pos)
>  	/* Set bit in array2 slab and set bit in array1 slab */
>  	index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
>  	offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
> -	index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 +
> RTE_BITMAP_CL_BIT_SIZE_LOG2);
> +	index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 +
> +			RTE_BITMAP_CL_BIT_SIZE_LOG2);
>  	offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) &
> RTE_BITMAP_SLAB_BIT_MASK;
>  	slab2 = bmp->array2 + index2;
>  	slab1 = bmp->array1 + index1;
> @@ -392,7 +418,8 @@ rte_bitmap_set_slab(struct rte_bitmap *bmp,
> uint32_t pos, uint64_t slab)
> 
>  	/* Set bits in array2 slab and set bit in array1 slab */
>  	index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
> -	index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 +
> RTE_BITMAP_CL_BIT_SIZE_LOG2);
> +	index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 +
> +			RTE_BITMAP_CL_BIT_SIZE_LOG2);
>  	offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) &
> RTE_BITMAP_SLAB_BIT_MASK;
>  	slab2 = bmp->array2 + index2;
>  	slab1 = bmp->array1 + index1;
> @@ -449,7 +476,8 @@ rte_bitmap_clear(struct rte_bitmap *bmp, uint32_t
> pos)
>  	}
> 
>  	/* The array2 cache line is all-zeros, so clear bit in array1 slab */
> -	index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 +
> RTE_BITMAP_CL_BIT_SIZE_LOG2);
> +	index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 +
> +			RTE_BITMAP_CL_BIT_SIZE_LOG2);
>  	offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) &
> RTE_BITMAP_SLAB_BIT_MASK;
>  	slab1 = bmp->array1 + index1;
>  	*slab1 &= ~(1lu << offset1);
> @@ -500,7 +528,8 @@ __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 ; bmp->index2 ++, slab2 ++,
> +			bmp->go2 = bmp->index2 &
> RTE_BITMAP_CL_SLAB_MASK) {
>  		if (*slab2) {
>  			*pos = bmp->index2 <<
> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
>  			*slab = *slab2;
> @@ -520,10 +549,10 @@ __rte_bitmap_scan_read(struct rte_bitmap *bmp,
> uint32_t *pos, uint64_t *slab)
>   *
>   * @param bmp
>   *   Handle to bitmap instance
> - * @param pos
> + * @param[out] pos
>   *   When function call returns 1, pos contains the position of the next set
>   *   bit, otherwise not modified
> - * @param slab
> + * @param[out] 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
> @@ -532,6 +561,7 @@ __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.
> + *
>   * @return
>   *   0 if there is no bit set in the bitmap, 1 otherwise
>   */
> diff --git a/lib/librte_sched/Makefile b/lib/librte_sched/Makefile
> index 18274e7..072cd63 100644
> --- a/lib/librte_sched/Makefile
> +++ b/lib/librte_sched/Makefile
> @@ -55,7 +55,8 @@ SRCS-$(CONFIG_RTE_LIBRTE_SCHED) += rte_sched.c
> rte_red.c rte_approx.c
>  SRCS-$(CONFIG_RTE_LIBRTE_SCHED) += rte_reciprocal.c
> 
>  # install includes
> -SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include := rte_sched.h
> rte_bitmap.h rte_sched_common.h rte_red.h rte_approx.h
> -SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include += rte_reciprocal.h
> +SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include := rte_sched.h
> +SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include += rte_sched_common.h
> rte_red.h
> +SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include += rte_approx.h
> 
>  include $(RTE_SDK)/mk/rte.lib.mk
> diff --git a/lib/librte_sched/rte_sched.c b/lib/librte_sched/rte_sched.c
> index b7cba11..b3e0d4f 100644
> --- a/lib/librte_sched/rte_sched.c
> +++ b/lib/librte_sched/rte_sched.c
> @@ -34,6 +34,7 @@
>  #include <stdio.h>
>  #include <string.h>
> 
> +#include <rte_bitmap.h>
>  #include <rte_common.h>
>  #include <rte_log.h>
>  #include <rte_memory.h>
> @@ -44,7 +45,6 @@
>  #include <rte_mbuf.h>
> 
>  #include "rte_sched.h"
> -#include "rte_bitmap.h"
>  #include "rte_sched_common.h"
>  #include "rte_approx.h"
>  #include "rte_reciprocal.h"
> --
> 2.7.4

Hi Pavan,

I think moving rte_bitmap.h to a common code area is a good idea, as it allows easier reuse by libs and apps.

A few asks from my side:
1. Please do not do any cosmetic changes on rte_bitmap.h, it adds a lot of code churn that makes review very difficult while adding no real value. This way, your patch will be very short and we don't need to worry about any bug introduction.
2. I want to retain maintainership of rte_bitmap.h, so please add a section in MANTAINERS file under EAL:

Bitmap
M: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
F: lib/librte_eal/common/include/rte_bitmap.h
F: test/test/test_bitmap.c

Regards,
Cristian

Re: [dpdk-dev] [PATCH 1/2] eal: move bitmap from lib sched

[Pavan Nikhilesh Bhagavatula]

On Wed, Sep 20, 2017 at 01:27:41PM +0000, Dumitrescu, Cristian wrote:
> > -----Original Message-----
> > From: Pavan Nikhilesh [mailto:pbhagavatula@caviumnetworks.com]
> > Sent: Thursday, September 7, 2017 3:40 PM
> > To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>;
> > stephen@networkplumber.org
> > Cc: dev@dpdk.org; Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
> > Subject: [dpdk-dev] [PATCH 1/2] eal: move bitmap from lib sched
> >
> > The librte_sched uses rte_bitmap to manage large arrays of bits in an
> > optimized method so, moving it to eal/common would allow other libraries
> > and applications to use it.
> >
> > Signed-off-by: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
> > ---
> >  lib/librte_eal/common/Makefile                     |   1 +
> >  .../common/include}/rte_bitmap.h                   | 100 +++++++++++++--------
> >  lib/librte_sched/Makefile                          |   5 +-
> >  lib/librte_sched/rte_sched.c                       |   2 +-
> >  4 files changed, 70 insertions(+), 38 deletions(-)
> >  rename lib/{librte_sched => librte_eal/common/include}/rte_bitmap.h
> > (85%)
> >
> > diff --git a/lib/librte_eal/common/Makefile
> > b/lib/librte_eal/common/Makefile
> > index e8fd67a..c2c6a7f 100644
> > --- a/lib/librte_eal/common/Makefile
> > +++ b/lib/librte_eal/common/Makefile
> > @@ -42,6 +42,7 @@ INC += rte_hexdump.h rte_devargs.h rte_bus.h
> > rte_dev.h rte_vdev.h
> >  INC += rte_pci_dev_feature_defs.h rte_pci_dev_features.h
> >  INC += rte_malloc.h rte_keepalive.h rte_time.h
> >  INC += rte_service.h rte_service_component.h
> > +INC += rte_bitmap.h
> >
> >  GENERIC_INC := rte_atomic.h rte_byteorder.h rte_cycles.h rte_prefetch.h
> >  GENERIC_INC += rte_spinlock.h rte_memcpy.h rte_cpuflags.h rte_rwlock.h
> > diff --git a/lib/librte_sched/rte_bitmap.h
> > b/lib/librte_eal/common/include/rte_bitmap.h
> > similarity index 85%
> > rename from lib/librte_sched/rte_bitmap.h
> > rename to lib/librte_eal/common/include/rte_bitmap.h
> > index 010d752..0938c63 100644
> > --- a/lib/librte_sched/rte_bitmap.h
> > +++ b/lib/librte_eal/common/include/rte_bitmap.h
> > @@ -65,6 +65,7 @@ extern "C" {
> >   ***/
> >
> >  #include <string.h>
> > +
> >  #include <rte_common.h>
> >  #include <rte_debug.h>
> >  #include <rte_memory.h>
> > @@ -72,36 +73,46 @@ extern "C" {
> >  #include <rte_prefetch.h>
> >
> >  #ifndef RTE_BITMAP_OPTIMIZATIONS
> > -#define RTE_BITMAP_OPTIMIZATIONS		         1
> > +#define RTE_BITMAP_OPTIMIZATIONS        1
> >  #endif
> >
> >  /* Slab */
> > -#define RTE_BITMAP_SLAB_BIT_SIZE                 64
> > -#define RTE_BITMAP_SLAB_BIT_SIZE_LOG2            6
> > -#define RTE_BITMAP_SLAB_BIT_MASK
> > (RTE_BITMAP_SLAB_BIT_SIZE - 1)
> > +#define RTE_BITMAP_SLAB_BIT_SIZE        64
> > +#define RTE_BITMAP_SLAB_BIT_SIZE_LOG2   6
> > +#define RTE_BITMAP_SLAB_BIT_MASK        (RTE_BITMAP_SLAB_BIT_SIZE -
> > 1)
> >
> >  /* Cache line (CL) */
> > -#define RTE_BITMAP_CL_BIT_SIZE                   (RTE_CACHE_LINE_SIZE * 8)
> > -#define RTE_BITMAP_CL_BIT_SIZE_LOG2
> > (RTE_CACHE_LINE_SIZE_LOG2 + 3)
> > -#define RTE_BITMAP_CL_BIT_MASK                   (RTE_BITMAP_CL_BIT_SIZE -
> > 1)
> > +#define RTE_BITMAP_CL_BIT_SIZE          (RTE_CACHE_LINE_SIZE * 8)
> > +#define RTE_BITMAP_CL_BIT_SIZE_LOG2     (RTE_CACHE_LINE_SIZE_LOG2
> > + 3)
> > +#define RTE_BITMAP_CL_BIT_MASK          (RTE_BITMAP_CL_BIT_SIZE - 1)
> >
> > -#define RTE_BITMAP_CL_SLAB_SIZE                  (RTE_BITMAP_CL_BIT_SIZE /
> > RTE_BITMAP_SLAB_BIT_SIZE)
> > -#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)
> > +#define RTE_BITMAP_CL_SLAB_SIZE         \
> > +	(RTE_BITMAP_CL_BIT_SIZE / RTE_BITMAP_SLAB_BIT_SIZE)
> > +#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)
> >
> >  /** Bitmap data structure */
> >  struct rte_bitmap {
> >  	/* Context for array1 and array2 */
> > -	uint64_t *array1;                        /**< Bitmap array1 */
> > -	uint64_t *array2;                        /**< Bitmap array2 */
> > -	uint32_t array1_size;                    /**< Number of 64-bit slabs in array1
> > that are actually used */
> > -	uint32_t array2_size;                    /**< Number of 64-bit slabs in array2
> > */
> > +	uint64_t *array1;
> > +	/**< Bitmap array1 */
> > +	uint64_t *array2;
> > +	/**< Bitmap array2 */
> > +	uint32_t array1_size;
> > +	/**< Number of 64-bit slabs in array1 that are actually used */
> > +	uint32_t array2_size;
> > +	/**< Number of 64-bit slabs in array2 */
> >
> >  	/* Context for the "scan next" operation */
> > -	uint32_t index1;  /**< Bitmap scan: Index of current array1 slab */
> > -	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 */
> > +	uint32_t index1;
> > +	/**< Bitmap scan: Index of current array1 slab */
> > +	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 */
> >
> >  	/* Storage space for array1 and array2 */
> >  	uint8_t memory[];
> > @@ -122,7 +133,8 @@ __rte_bitmap_mask1_get(struct rte_bitmap *bmp)
> >  static inline void
> >  __rte_bitmap_index2_set(struct rte_bitmap *bmp)
> >  {
> > -	bmp->index2 = (((bmp->index1 <<
> > RTE_BITMAP_SLAB_BIT_SIZE_LOG2) + bmp->offset1) <<
> > RTE_BITMAP_CL_SLAB_SIZE_LOG2);
> > +	bmp->index2 = (((bmp->index1 <<
> > RTE_BITMAP_SLAB_BIT_SIZE_LOG2) +
> > +				bmp->offset1) <<
> > RTE_BITMAP_CL_SLAB_SIZE_LOG2);
> >  }
> >
> >  #if RTE_BITMAP_OPTIMIZATIONS
> > @@ -171,12 +183,18 @@ __rte_bitmap_get_memory_footprint(uint32_t
> > n_bits,
> >  	uint32_t n_cache_lines_array2;
> >  	uint32_t n_bytes_total;
> >
> > -	n_cache_lines_array2 = (n_bits + RTE_BITMAP_CL_BIT_SIZE - 1) /
> > RTE_BITMAP_CL_BIT_SIZE;
> > -	n_slabs_array1 = (n_cache_lines_array2 +
> > RTE_BITMAP_SLAB_BIT_SIZE - 1) / RTE_BITMAP_SLAB_BIT_SIZE;
> > +	n_cache_lines_array2 = (n_bits + RTE_BITMAP_CL_BIT_SIZE - 1) /
> > +		RTE_BITMAP_CL_BIT_SIZE;
> > +	n_slabs_array1 = (n_cache_lines_array2 +
> > RTE_BITMAP_SLAB_BIT_SIZE - 1) /
> > +		RTE_BITMAP_SLAB_BIT_SIZE;
> >  	n_slabs_array1 = rte_align32pow2(n_slabs_array1);
> > -	n_slabs_context = (sizeof(struct rte_bitmap) +
> > (RTE_BITMAP_SLAB_BIT_SIZE / 8) - 1) / (RTE_BITMAP_SLAB_BIT_SIZE / 8);
> > -	n_cache_lines_context_and_array1 = (n_slabs_context +
> > n_slabs_array1 + RTE_BITMAP_CL_SLAB_SIZE - 1) /
> > RTE_BITMAP_CL_SLAB_SIZE;
> > -	n_bytes_total = (n_cache_lines_context_and_array1 +
> > n_cache_lines_array2) * RTE_CACHE_LINE_SIZE;
> > +	n_slabs_context = (sizeof(struct rte_bitmap) +
> > +			(RTE_BITMAP_SLAB_BIT_SIZE / 8) - 1) /
> > +		(RTE_BITMAP_SLAB_BIT_SIZE / 8);
> > +	n_cache_lines_context_and_array1 = (n_slabs_context +
> > n_slabs_array1 +
> > +			RTE_BITMAP_CL_SLAB_SIZE - 1) /
> > RTE_BITMAP_CL_SLAB_SIZE;
> > +	n_bytes_total = (n_cache_lines_context_and_array1 +
> > +			n_cache_lines_array2) * RTE_CACHE_LINE_SIZE;
> >
> >  	if (array1_byte_offset) {
> >  		*array1_byte_offset = n_slabs_context *
> > (RTE_BITMAP_SLAB_BIT_SIZE / 8);
> > @@ -185,7 +203,8 @@ __rte_bitmap_get_memory_footprint(uint32_t
> > n_bits,
> >  		*array1_slabs = n_slabs_array1;
> >  	}
> >  	if (array2_byte_offset) {
> > -		*array2_byte_offset = n_cache_lines_context_and_array1 *
> > RTE_CACHE_LINE_SIZE;
> > +		*array2_byte_offset = n_cache_lines_context_and_array1 *
> > +			RTE_CACHE_LINE_SIZE;
> >  	}
> >  	if (array2_slabs) {
> >  		*array2_slabs = n_cache_lines_array2 *
> > RTE_BITMAP_CL_SLAB_SIZE;
> > @@ -210,6 +229,7 @@ __rte_bitmap_scan_init(struct rte_bitmap *bmp)
> >   *
> >   * @param n_bits
> >   *   Number of bits in the bitmap
> > + *
> >   * @return
> >   *   Bitmap memory footprint measured in bytes on success, 0 on error
> >   */
> > @@ -226,12 +246,14 @@ rte_bitmap_get_memory_footprint(uint32_t
> > n_bits) {
> >  /**
> >   * Bitmap initialization
> >   *
> > - * @param mem_size
> > - *   Minimum expected size of bitmap.
> > + * @param n_bits
> > + *   Number of pre-allocated bits in array2. Must be non-zero and multiple
> > of
> > + *   512.
> >   * @param mem
> >   *   Base address of array1 and array2.
> > - * @param n_bits
> > - *   Number of pre-allocated bits in array2. Must be non-zero and multiple of
> > 512.
> > + * @param mem_size
> > + *   Minimum expected size of bitmap.
> > + *
> >   * @return
> >   *   Handle to bitmap instance.
> >   */
> > @@ -277,6 +299,7 @@ rte_bitmap_init(uint32_t n_bits, uint8_t *mem,
> > uint32_t mem_size)
> >   *
> >   * @param bmp
> >   *   Handle to bitmap instance
> > + *
> >   * @return
> >   *   0 upon success, error code otherwise
> >   */
> > @@ -312,6 +335,7 @@ rte_bitmap_reset(struct rte_bitmap *bmp)
> >   *   Handle to bitmap instance
> >   * @param pos
> >   *   Bit position
> > + *
> >   * @return
> >   *   0 upon success, error code otherwise
> >   */
> > @@ -333,6 +357,7 @@ rte_bitmap_prefetch0(struct rte_bitmap *bmp,
> > uint32_t pos)
> >   *   Handle to bitmap instance
> >   * @param pos
> >   *   Bit position
> > + *
> >   * @return
> >   *   0 when bit is cleared, non-zero when bit is set
> >   */
> > @@ -365,7 +390,8 @@ rte_bitmap_set(struct rte_bitmap *bmp, uint32_t
> > pos)
> >  	/* Set bit in array2 slab and set bit in array1 slab */
> >  	index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
> >  	offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK;
> > -	index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 +
> > RTE_BITMAP_CL_BIT_SIZE_LOG2);
> > +	index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 +
> > +			RTE_BITMAP_CL_BIT_SIZE_LOG2);
> >  	offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) &
> > RTE_BITMAP_SLAB_BIT_MASK;
> >  	slab2 = bmp->array2 + index2;
> >  	slab1 = bmp->array1 + index1;
> > @@ -392,7 +418,8 @@ rte_bitmap_set_slab(struct rte_bitmap *bmp,
> > uint32_t pos, uint64_t slab)
> >
> >  	/* Set bits in array2 slab and set bit in array1 slab */
> >  	index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
> > -	index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 +
> > RTE_BITMAP_CL_BIT_SIZE_LOG2);
> > +	index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 +
> > +			RTE_BITMAP_CL_BIT_SIZE_LOG2);
> >  	offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) &
> > RTE_BITMAP_SLAB_BIT_MASK;
> >  	slab2 = bmp->array2 + index2;
> >  	slab1 = bmp->array1 + index1;
> > @@ -449,7 +476,8 @@ rte_bitmap_clear(struct rte_bitmap *bmp, uint32_t
> > pos)
> >  	}
> >
> >  	/* The array2 cache line is all-zeros, so clear bit in array1 slab */
> > -	index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 +
> > RTE_BITMAP_CL_BIT_SIZE_LOG2);
> > +	index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 +
> > +			RTE_BITMAP_CL_BIT_SIZE_LOG2);
> >  	offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) &
> > RTE_BITMAP_SLAB_BIT_MASK;
> >  	slab1 = bmp->array1 + index1;
> >  	*slab1 &= ~(1lu << offset1);
> > @@ -500,7 +528,8 @@ __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 ; bmp->index2 ++, slab2 ++,
> > +			bmp->go2 = bmp->index2 &
> > RTE_BITMAP_CL_SLAB_MASK) {
> >  		if (*slab2) {
> >  			*pos = bmp->index2 <<
> > RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
> >  			*slab = *slab2;
> > @@ -520,10 +549,10 @@ __rte_bitmap_scan_read(struct rte_bitmap *bmp,
> > uint32_t *pos, uint64_t *slab)
> >   *
> >   * @param bmp
> >   *   Handle to bitmap instance
> > - * @param pos
> > + * @param[out] pos
> >   *   When function call returns 1, pos contains the position of the next set
> >   *   bit, otherwise not modified
> > - * @param slab
> > + * @param[out] 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
> > @@ -532,6 +561,7 @@ __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.
> > + *
> >   * @return
> >   *   0 if there is no bit set in the bitmap, 1 otherwise
> >   */
> > diff --git a/lib/librte_sched/Makefile b/lib/librte_sched/Makefile
> > index 18274e7..072cd63 100644
> > --- a/lib/librte_sched/Makefile
> > +++ b/lib/librte_sched/Makefile
> > @@ -55,7 +55,8 @@ SRCS-$(CONFIG_RTE_LIBRTE_SCHED) += rte_sched.c
> > rte_red.c rte_approx.c
> >  SRCS-$(CONFIG_RTE_LIBRTE_SCHED) += rte_reciprocal.c
> >
> >  # install includes
> > -SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include := rte_sched.h
> > rte_bitmap.h rte_sched_common.h rte_red.h rte_approx.h
> > -SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include += rte_reciprocal.h
> > +SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include := rte_sched.h
> > +SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include += rte_sched_common.h
> > rte_red.h
> > +SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include += rte_approx.h
> >
> >  include $(RTE_SDK)/mk/rte.lib.mk
> > diff --git a/lib/librte_sched/rte_sched.c b/lib/librte_sched/rte_sched.c
> > index b7cba11..b3e0d4f 100644
> > --- a/lib/librte_sched/rte_sched.c
> > +++ b/lib/librte_sched/rte_sched.c
> > @@ -34,6 +34,7 @@
> >  #include <stdio.h>
> >  #include <string.h>
> >
> > +#include <rte_bitmap.h>
> >  #include <rte_common.h>
> >  #include <rte_log.h>
> >  #include <rte_memory.h>
> > @@ -44,7 +45,6 @@
> >  #include <rte_mbuf.h>
> >
> >  #include "rte_sched.h"
> > -#include "rte_bitmap.h"
> >  #include "rte_sched_common.h"
> >  #include "rte_approx.h"
> >  #include "rte_reciprocal.h"
> > --
> > 2.7.4
>
> Hi Pavan,
>
> I think moving rte_bitmap.h to a common code area is a good idea, as it allows easier reuse by libs and apps.
>
> A few asks from my side:
> 1. Please do not do any cosmetic changes on rte_bitmap.h, it adds a lot of code churn that makes review very difficult while adding no real value. This way, your patch will be very short and we don't need to worry about any bug introduction.
> 2. I want to retain maintainership of rte_bitmap.h, so please add a section in MANTAINERS file under EAL:
>
> Bitmap
> M: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
> F: lib/librte_eal/common/include/rte_bitmap.h
> F: test/test/test_bitmap.c
>
> Regards,
> Cristian
>
Sure will spin up a v2.

Thanks,
Pavan

[dpdk-dev] [PATCH v2 1/3] eal: move bitmap from lib sched

[Pavan Nikhilesh]

From: Pavan Bhagavatula <pbhagavatula@caviumnetworks.com>

The librte_sched uses rte_bitmap to manage large arrays of bits in an
optimized method so, moving it to eal/common would allow other libraries
and applications to use it.

Signed-off-by: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
---

v2 changes:
 - undo rte_bitmap.h cosmetic changes
 - update maintainer info

 lib/librte_eal/common/Makefile                               | 1 +
 lib/{librte_sched => librte_eal/common/include}/rte_bitmap.h | 0
 lib/librte_sched/Makefile                                    | 5 +++--
 lib/librte_sched/rte_sched.c                                 | 2 +-
 4 files changed, 5 insertions(+), 3 deletions(-)
 rename lib/{librte_sched => librte_eal/common/include}/rte_bitmap.h (100%)

diff --git a/lib/librte_eal/common/Makefile b/lib/librte_eal/common/Makefile
index e8fd67a..c2c6a7f 100644
--- a/lib/librte_eal/common/Makefile
+++ b/lib/librte_eal/common/Makefile
@@ -42,6 +42,7 @@ INC += rte_hexdump.h rte_devargs.h rte_bus.h rte_dev.h rte_vdev.h
 INC += rte_pci_dev_feature_defs.h rte_pci_dev_features.h
 INC += rte_malloc.h rte_keepalive.h rte_time.h
 INC += rte_service.h rte_service_component.h
+INC += rte_bitmap.h

 GENERIC_INC := rte_atomic.h rte_byteorder.h rte_cycles.h rte_prefetch.h
 GENERIC_INC += rte_spinlock.h rte_memcpy.h rte_cpuflags.h rte_rwlock.h
diff --git a/lib/librte_sched/rte_bitmap.h b/lib/librte_eal/common/include/rte_bitmap.h
similarity index 100%
rename from lib/librte_sched/rte_bitmap.h
rename to lib/librte_eal/common/include/rte_bitmap.h
diff --git a/lib/librte_sched/Makefile b/lib/librte_sched/Makefile
index 18274e7..9a28a9e 100644
--- a/lib/librte_sched/Makefile
+++ b/lib/librte_sched/Makefile
@@ -55,7 +55,8 @@ SRCS-$(CONFIG_RTE_LIBRTE_SCHED) += rte_sched.c rte_red.c rte_approx.c
 SRCS-$(CONFIG_RTE_LIBRTE_SCHED) += rte_reciprocal.c

 # install includes
-SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include := rte_sched.h rte_bitmap.h rte_sched_common.h rte_red.h rte_approx.h
-SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include += rte_reciprocal.h
+SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include := rte_sched.h rte_sched_common.h
+SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include += rte_reciprocal.h rte_red.h
+SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include += rte_approx.h

 include $(RTE_SDK)/mk/rte.lib.mk
diff --git a/lib/librte_sched/rte_sched.c b/lib/librte_sched/rte_sched.c
index b7cba11..b3e0d4f 100644
--- a/lib/librte_sched/rte_sched.c
+++ b/lib/librte_sched/rte_sched.c
@@ -34,6 +34,7 @@
 #include <stdio.h>
 #include <string.h>

+#include <rte_bitmap.h>
 #include <rte_common.h>
 #include <rte_log.h>
 #include <rte_memory.h>
@@ -44,7 +45,6 @@
 #include <rte_mbuf.h>

 #include "rte_sched.h"
-#include "rte_bitmap.h"
 #include "rte_sched_common.h"
 #include "rte_approx.h"
 #include "rte_reciprocal.h"
--
2.7.4

[dpdk-dev] [PATCH v2 2/3] test: add test for bitmap operations

[Pavan Nikhilesh]

From: Pavan Bhagavatula <pbhagavatula@caviumnetworks.com>

This patch adds a test for verifying the bitmap operations.

Signed-off-by: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
---
 test/test/Makefile      |   1 +
 test/test/test_bitmap.c | 192 ++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 193 insertions(+)
 create mode 100644 test/test/test_bitmap.c

diff --git a/test/test/Makefile b/test/test/Makefile
index 42d9a49..2fda8d9 100644
--- a/test/test/Makefile
+++ b/test/test/Makefile
@@ -94,6 +94,7 @@ SRCS-y += test_cycles.c
 SRCS-y += test_spinlock.c
 SRCS-y += test_memory.c
 SRCS-y += test_memzone.c
+SRCS-y += test_bitmap.c
 
 SRCS-y += test_ring.c
 SRCS-y += test_ring_perf.c
diff --git a/test/test/test_bitmap.c b/test/test/test_bitmap.c
new file mode 100644
index 0000000..5c9eee9
--- /dev/null
+++ b/test/test/test_bitmap.c
@@ -0,0 +1,192 @@
+/*
+ *   BSD LICENSE
+ *
+ *   Copyright (C) Cavium, Inc. 2017.
+ *
+ *   Redistribution and use in source and binary forms, with or without
+ *   modification, are permitted provided that the following conditions
+ *   are met:
+ *
+ *     * Redistributions of source code must retain the above copyright
+ *       notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above copyright
+ *       notice, this list of conditions and the following disclaimer in
+ *       the documentation and/or other materials provided with the
+ *       distribution.
+ *     * Neither the name of Cavium, Inc nor the names of its
+ *       contributors may be used to endorse or promote products derived
+ *       from this software without specific prior written permission.
+ *
+ *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <inttypes.h>
+
+#include <rte_common.h>
+#include <rte_bitmap.h>
+#include <rte_malloc.h>
+
+#include "test.h"
+
+#define MAX_BITS 1000
+
+static int
+test_bitmap_scan_operations(struct rte_bitmap *bmp)
+{
+	uint32_t pos = 0;
+	uint64_t slab1_magic = 0xBADC0FFEEBADF00D;
+	uint64_t slab2_magic = 0xFEEDDEADDEADF00D;
+	uint64_t out_slab = 0;
+
+	rte_bitmap_reset(bmp);
+
+	rte_bitmap_set_slab(bmp, pos, slab1_magic);
+	rte_bitmap_set_slab(bmp, pos + RTE_BITMAP_SLAB_BIT_SIZE, slab2_magic);
+
+	if (!rte_bitmap_scan(bmp, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab1_magic != out_slab) {
+		printf("Scan operation sanity failed.\n");
+		return TEST_FAILED;
+	}
+
+	if (!rte_bitmap_scan(bmp, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab2_magic != out_slab) {
+		printf("Scan operation sanity failed.\n");
+		return TEST_FAILED;
+	}
+
+	/* Wrap around */
+	if (!rte_bitmap_scan(bmp, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab1_magic != out_slab) {
+		printf("Scan operation wrap around failed.\n");
+		return TEST_FAILED;
+	}
+
+	/* Scan reset check. */
+	__rte_bitmap_scan_init(bmp);
+
+	if (!rte_bitmap_scan(bmp, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab1_magic != out_slab) {
+		printf("Scan reset operation failed.\n");
+		return TEST_FAILED;
+	}
+
+	return TEST_SUCCESS;
+}
+
+static int
+test_bitmap_slab_set_get(struct rte_bitmap *bmp)
+{
+	uint32_t pos = 0;
+	uint64_t slab_magic = 0xBADC0FFEEBADF00D;
+	uint64_t out_slab = 0;
+
+	rte_bitmap_reset(bmp);
+	rte_bitmap_set_slab(bmp, pos, slab_magic);
+
+	if (!rte_bitmap_scan(bmp, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap.\n");
+		return TEST_FAILED;
+	}
+
+
+	if (slab_magic != out_slab) {
+		printf("Invalid slab in bitmap.\n");
+		return TEST_FAILED;
+	}
+
+
+	return TEST_SUCCESS;
+}
+
+static int
+test_bitmap_set_get_clear(struct rte_bitmap *bmp)
+{
+	int i;
+
+	rte_bitmap_reset(bmp);
+	for (i = 0; i < MAX_BITS; i++)
+		rte_bitmap_set(bmp, i);
+
+	for (i = 0; i < MAX_BITS; i++) {
+		if (!rte_bitmap_get(bmp, i)) {
+			printf("Failed to get set bit.\n");
+			return TEST_FAILED;
+		}
+	}
+
+	for (i = 0; i < MAX_BITS; i++)
+		rte_bitmap_clear(bmp, i);
+
+	for (i = 0; i < MAX_BITS; i++) {
+		if (rte_bitmap_get(bmp, i)) {
+			printf("Failed to clear set bit.\n");
+			return TEST_FAILED;
+		}
+	}
+
+	return TEST_SUCCESS;
+}
+
+static int
+test_bitmap(void)
+{
+	void *mem;
+	uint32_t bmp_size;
+	struct rte_bitmap *bmp;
+
+	bmp_size =
+		rte_bitmap_get_memory_footprint(MAX_BITS);
+
+	mem = rte_zmalloc("test_bmap", bmp_size, RTE_CACHE_LINE_SIZE);
+	if (mem == NULL) {
+		printf("Failed to allocate memory for bitmap\n");
+		return TEST_FAILED;
+	}
+
+	bmp = rte_bitmap_init(MAX_BITS, mem, bmp_size);
+	if (bmp == NULL) {
+		printf("Failed to init bitmap\n");
+		return TEST_FAILED;
+	}
+
+	if (test_bitmap_set_get_clear(bmp) < 0)
+		return TEST_FAILED;
+
+	if (test_bitmap_slab_set_get(bmp) < 0)
+		return TEST_FAILED;
+
+	if (test_bitmap_scan_operations(bmp) < 0)
+		return TEST_FAILED;
+
+	return TEST_SUCCESS;
+}
+
+REGISTER_TEST_COMMAND(bitmap_test, test_bitmap);
-- 
2.7.4

[dpdk-dev] [PATCH v2 3/3] maintainers: add maintainer for bitmap

[Pavan Nikhilesh]

Signed-off-by: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
---
 MAINTAINERS | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/MAINTAINERS b/MAINTAINERS
index a0cd75e..3522497 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -143,6 +143,11 @@ F: lib/librte_eal/common/rte_service.c
 F: doc/guides/prog_guide/service_cores.rst
 F: test/test/test_service_cores.c
 
+Bitmap
+M: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
+F: lib/librte_eal/common/include/rte_bitmap.h
+F: test/test/test_bitmap.c
+
 ARM v7
 M: Jan Viktorin <viktorin@rehivetech.com>
 M: Jianbo Liu <jianbo.liu@linaro.org>
-- 
2.7.4

Re: [dpdk-dev] [PATCH v2 1/3] eal: move bitmap from lib sched

[Dumitrescu, Cristian]

> -----Original Message-----
> From: Pavan Nikhilesh [mailto:pbhagavatula@caviumnetworks.com]
> Sent: Wednesday, September 20, 2017 4:37 PM
> To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>;
> stephen@networkplumber.org
> Cc: dev@dpdk.org; Pavan Bhagavatula
> <pbhagavatula@caviumnetworks.com>
> Subject: [dpdk-dev] [PATCH v2 1/3] eal: move bitmap from lib sched
> 
> From: Pavan Bhagavatula <pbhagavatula@caviumnetworks.com>
> 
> The librte_sched uses rte_bitmap to manage large arrays of bits in an
> optimized method so, moving it to eal/common would allow other libraries
> and applications to use it.
> 
> Signed-off-by: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
> ---
> 
> v2 changes:
>  - undo rte_bitmap.h cosmetic changes
>  - update maintainer info
> 
>  lib/librte_eal/common/Makefile                               | 1 +
>  lib/{librte_sched => librte_eal/common/include}/rte_bitmap.h | 0
>  lib/librte_sched/Makefile                                    | 5 +++--
>  lib/librte_sched/rte_sched.c                                 | 2 +-
>  4 files changed, 5 insertions(+), 3 deletions(-)
>  rename lib/{librte_sched => librte_eal/common/include}/rte_bitmap.h
> (100%)
> 

You say (in the change log) that you did it, but you forgot to add MAINTAINERS file changes to your patch

Re: [dpdk-dev] [PATCH v2 1/3] eal: move bitmap from lib sched

[Pavan Nikhilesh Bhagavatula]

On Wed, Sep 20, 2017 at 03:40:46PM +0000, Dumitrescu, Cristian wrote:
>
>
> > -----Original Message-----
> > From: Pavan Nikhilesh [mailto:pbhagavatula@caviumnetworks.com]
> > Sent: Wednesday, September 20, 2017 4:37 PM
> > To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>;
> > stephen@networkplumber.org
> > Cc: dev@dpdk.org; Pavan Bhagavatula
> > <pbhagavatula@caviumnetworks.com>
> > Subject: [dpdk-dev] [PATCH v2 1/3] eal: move bitmap from lib sched
> >
> > From: Pavan Bhagavatula <pbhagavatula@caviumnetworks.com>
> >
> > The librte_sched uses rte_bitmap to manage large arrays of bits in an
> > optimized method so, moving it to eal/common would allow other libraries
> > and applications to use it.
> >
> > Signed-off-by: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
> > ---
> >
> > v2 changes:
> >  - undo rte_bitmap.h cosmetic changes
> >  - update maintainer info
> >
> >  lib/librte_eal/common/Makefile                               | 1 +
> >  lib/{librte_sched => librte_eal/common/include}/rte_bitmap.h | 0
> >  lib/librte_sched/Makefile                                    | 5 +++--
> >  lib/librte_sched/rte_sched.c                                 | 2 +-
> >  4 files changed, 5 insertions(+), 3 deletions(-)
> >  rename lib/{librte_sched => librte_eal/common/include}/rte_bitmap.h
> > (100%)
> >
>
> You say (in the change log) that you did it, but you forgot to add MAINTAINERS file changes to your patch

addressed in the 3rd patch of the patchset http://dpdk.org/dev/patchwork/patch/29037/

Re: [dpdk-dev] [PATCH v2 1/3] eal: move bitmap from lib sched

[Dumitrescu, Cristian]

> -----Original Message-----
> From: Pavan Nikhilesh Bhagavatula
> [mailto:pbhagavatula@caviumnetworks.com]
> Sent: Wednesday, September 20, 2017 4:45 PM
> To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>;
> stephen@networkplumber.org
> Cc: dev@dpdk.org
> Subject: Re: [dpdk-dev] [PATCH v2 1/3] eal: move bitmap from lib sched
> 
> On Wed, Sep 20, 2017 at 03:40:46PM +0000, Dumitrescu, Cristian wrote:
> >
> >
> > > -----Original Message-----
> > > From: Pavan Nikhilesh [mailto:pbhagavatula@caviumnetworks.com]
> > > Sent: Wednesday, September 20, 2017 4:37 PM
> > > To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>;
> > > stephen@networkplumber.org
> > > Cc: dev@dpdk.org; Pavan Bhagavatula
> > > <pbhagavatula@caviumnetworks.com>
> > > Subject: [dpdk-dev] [PATCH v2 1/3] eal: move bitmap from lib sched
> > >
> > > From: Pavan Bhagavatula <pbhagavatula@caviumnetworks.com>
> > >
> > > The librte_sched uses rte_bitmap to manage large arrays of bits in an
> > > optimized method so, moving it to eal/common would allow other
> libraries
> > > and applications to use it.
> > >
> > > Signed-off-by: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
> > > ---
> > >
> > > v2 changes:
> > >  - undo rte_bitmap.h cosmetic changes
> > >  - update maintainer info
> > >
> > >  lib/librte_eal/common/Makefile                               | 1 +
> > >  lib/{librte_sched => librte_eal/common/include}/rte_bitmap.h | 0
> > >  lib/librte_sched/Makefile                                    | 5 +++--
> > >  lib/librte_sched/rte_sched.c                                 | 2 +-
> > >  4 files changed, 5 insertions(+), 3 deletions(-)
> > >  rename lib/{librte_sched => librte_eal/common/include}/rte_bitmap.h
> > > (100%)
> > >
> >
> > You say (in the change log) that you did it, but you forgot to add
> MAINTAINERS file changes to your patch
> 
> addressed in the 3rd patch of the patchset
> http://dpdk.org/dev/patchwork/patch/29037/

Oh, yes, you're right, sorry.

Re: [dpdk-dev] [PATCH v2 1/3] eal: move bitmap from lib sched

[Pavan Nikhilesh Bhagavatula]

On Wed, Sep 20, 2017 at 04:39:22PM +0000, Dumitrescu, Cristian wrote:
>
>
> > -----Original Message-----
> > From: Pavan Nikhilesh Bhagavatula
> > [mailto:pbhagavatula@caviumnetworks.com]
> > Sent: Wednesday, September 20, 2017 4:45 PM
> > To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>;
> > stephen@networkplumber.org
> > Cc: dev@dpdk.org
> > Subject: Re: [dpdk-dev] [PATCH v2 1/3] eal: move bitmap from lib sched
> >
> > On Wed, Sep 20, 2017 at 03:40:46PM +0000, Dumitrescu, Cristian wrote:
> > >
> > >
> > > > -----Original Message-----
> > > > From: Pavan Nikhilesh [mailto:pbhagavatula@caviumnetworks.com]
> > > > Sent: Wednesday, September 20, 2017 4:37 PM
> > > > To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>;
> > > > stephen@networkplumber.org
> > > > Cc: dev@dpdk.org; Pavan Bhagavatula
> > > > <pbhagavatula@caviumnetworks.com>
> > > > Subject: [dpdk-dev] [PATCH v2 1/3] eal: move bitmap from lib sched
> > > >
> > > > From: Pavan Bhagavatula <pbhagavatula@caviumnetworks.com>
> > > >
> > > > The librte_sched uses rte_bitmap to manage large arrays of bits in an
> > > > optimized method so, moving it to eal/common would allow other
> > libraries
> > > > and applications to use it.
> > > >
> > > > Signed-off-by: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
> > > > ---
> > > >
> > > > v2 changes:
> > > >  - undo rte_bitmap.h cosmetic changes
> > > >  - update maintainer info
> > > >
> > > >  lib/librte_eal/common/Makefile                               | 1 +
> > > >  lib/{librte_sched => librte_eal/common/include}/rte_bitmap.h | 0
> > > >  lib/librte_sched/Makefile                                    | 5 +++--
> > > >  lib/librte_sched/rte_sched.c                                 | 2 +-
> > > >  4 files changed, 5 insertions(+), 3 deletions(-)
> > > >  rename lib/{librte_sched => librte_eal/common/include}/rte_bitmap.h
> > > > (100%)
> > > >
> > >
> > > You say (in the change log) that you did it, but you forgot to add
> > MAINTAINERS file changes to your patch
> >
> > addressed in the 3rd patch of the patchset
> > http://dpdk.org/dev/patchwork/patch/29037/
>
> Oh, yes, you're right, sorry.
>

No problem! :)

Re: [dpdk-dev] [PATCH v2 1/3] eal: move bitmap from lib sched

[Dumitrescu, Cristian]

Hi Pavan,

Thank you, just a couple of minor issues below:

> -----Original Message-----
> From: Pavan Nikhilesh [mailto:pbhagavatula@caviumnetworks.com]
> Sent: Wednesday, September 20, 2017 4:37 PM
> To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>;
> stephen@networkplumber.org
> Cc: dev@dpdk.org; Pavan Bhagavatula
> <pbhagavatula@caviumnetworks.com>
> Subject: [dpdk-dev] [PATCH v2 1/3] eal: move bitmap from lib sched
> 
> From: Pavan Bhagavatula <pbhagavatula@caviumnetworks.com>
> 
> The librte_sched uses rte_bitmap to manage large arrays of bits in an
> optimized method so, moving it to eal/common would allow other libraries
> and applications to use it.
> 
> Signed-off-by: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
> ---
> 
> v2 changes:
>  - undo rte_bitmap.h cosmetic changes
>  - update maintainer info
> 
>  lib/librte_eal/common/Makefile                               | 1 +
>  lib/{librte_sched => librte_eal/common/include}/rte_bitmap.h | 0
>  lib/librte_sched/Makefile                                    | 5 +++--
>  lib/librte_sched/rte_sched.c                                 | 2 +-
>  4 files changed, 5 insertions(+), 3 deletions(-)
>  rename lib/{librte_sched => librte_eal/common/include}/rte_bitmap.h
> (100%)
> 
> diff --git a/lib/librte_eal/common/Makefile
> b/lib/librte_eal/common/Makefile
> index e8fd67a..c2c6a7f 100644
> --- a/lib/librte_eal/common/Makefile
> +++ b/lib/librte_eal/common/Makefile
> @@ -42,6 +42,7 @@ INC += rte_hexdump.h rte_devargs.h rte_bus.h
> rte_dev.h rte_vdev.h
>  INC += rte_pci_dev_feature_defs.h rte_pci_dev_features.h
>  INC += rte_malloc.h rte_keepalive.h rte_time.h
>  INC += rte_service.h rte_service_component.h
> +INC += rte_bitmap.h
> 
>  GENERIC_INC := rte_atomic.h rte_byteorder.h rte_cycles.h rte_prefetch.h
>  GENERIC_INC += rte_spinlock.h rte_memcpy.h rte_cpuflags.h rte_rwlock.h
> diff --git a/lib/librte_sched/rte_bitmap.h
> b/lib/librte_eal/common/include/rte_bitmap.h
> similarity index 100%
> rename from lib/librte_sched/rte_bitmap.h
> rename to lib/librte_eal/common/include/rte_bitmap.h
> diff --git a/lib/librte_sched/Makefile b/lib/librte_sched/Makefile
> index 18274e7..9a28a9e 100644
> --- a/lib/librte_sched/Makefile
> +++ b/lib/librte_sched/Makefile
> @@ -55,7 +55,8 @@ SRCS-$(CONFIG_RTE_LIBRTE_SCHED) += rte_sched.c
> rte_red.c rte_approx.c
>  SRCS-$(CONFIG_RTE_LIBRTE_SCHED) += rte_reciprocal.c
> 
>  # install includes
> -SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include := rte_sched.h
> rte_bitmap.h rte_sched_common.h rte_red.h rte_approx.h
> -SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include += rte_reciprocal.h
> +SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include := rte_sched.h
> rte_sched_common.h
> +SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include += rte_reciprocal.h
> rte_red.h
> +SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include += rte_approx.h
> 

These changes are not required, please just remove the rte_bitmap.h from this list with no other changes.

>  include $(RTE_SDK)/mk/rte.lib.mk
> diff --git a/lib/librte_sched/rte_sched.c b/lib/librte_sched/rte_sched.c
> index b7cba11..b3e0d4f 100644
> --- a/lib/librte_sched/rte_sched.c
> +++ b/lib/librte_sched/rte_sched.c
> @@ -34,6 +34,7 @@
>  #include <stdio.h>
>  #include <string.h>
> 
> +#include <rte_bitmap.h>

Please #include <rte_bitmap.h> at the end of the #include <rte_*.h> list.

>  #include <rte_common.h>
>  #include <rte_log.h>
>  #include <rte_memory.h>
> @@ -44,7 +45,6 @@
>  #include <rte_mbuf.h>
> 
>  #include "rte_sched.h"
> -#include "rte_bitmap.h"
>  #include "rte_sched_common.h"
>  #include "rte_approx.h"
>  #include "rte_reciprocal.h"
> --
> 2.7.4

Regards,
Cristian

Re: [dpdk-dev] [PATCH v2 1/3] eal: move bitmap from lib sched

[Pavan Nikhilesh Bhagavatula]

On Thu, Sep 21, 2017 at 10:25:18AM +0000, Dumitrescu, Cristian wrote:
Hi Cristian,
> Hi Pavan,
>
> Thank you, just a couple of minor issues below:
>
Sure will spin up a v3 with the mentioned changes.

Thanks,
Pavan
> > -----Original Message-----
> > From: Pavan Nikhilesh [mailto:pbhagavatula@caviumnetworks.com]
> > Sent: Wednesday, September 20, 2017 4:37 PM
> > To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>;
> > stephen@networkplumber.org
> > Cc: dev@dpdk.org; Pavan Bhagavatula
> > <pbhagavatula@caviumnetworks.com>
> > Subject: [dpdk-dev] [PATCH v2 1/3] eal: move bitmap from lib sched
> >
> > From: Pavan Bhagavatula <pbhagavatula@caviumnetworks.com>
> >
> > The librte_sched uses rte_bitmap to manage large arrays of bits in an
> > optimized method so, moving it to eal/common would allow other libraries
> > and applications to use it.
> >
> > Signed-off-by: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
> > ---
> >
> > v2 changes:
> >  - undo rte_bitmap.h cosmetic changes
> >  - update maintainer info
> >
> >  lib/librte_eal/common/Makefile                               | 1 +
> >  lib/{librte_sched => librte_eal/common/include}/rte_bitmap.h | 0
> >  lib/librte_sched/Makefile                                    | 5 +++--
> >  lib/librte_sched/rte_sched.c                                 | 2 +-
> >  4 files changed, 5 insertions(+), 3 deletions(-)
> >  rename lib/{librte_sched => librte_eal/common/include}/rte_bitmap.h
> > (100%)
> >
> > diff --git a/lib/librte_eal/common/Makefile
> > b/lib/librte_eal/common/Makefile
> > index e8fd67a..c2c6a7f 100644
> > --- a/lib/librte_eal/common/Makefile
> > +++ b/lib/librte_eal/common/Makefile
> > @@ -42,6 +42,7 @@ INC += rte_hexdump.h rte_devargs.h rte_bus.h
> > rte_dev.h rte_vdev.h
> >  INC += rte_pci_dev_feature_defs.h rte_pci_dev_features.h
> >  INC += rte_malloc.h rte_keepalive.h rte_time.h
> >  INC += rte_service.h rte_service_component.h
> > +INC += rte_bitmap.h
> >
> >  GENERIC_INC := rte_atomic.h rte_byteorder.h rte_cycles.h rte_prefetch.h
> >  GENERIC_INC += rte_spinlock.h rte_memcpy.h rte_cpuflags.h rte_rwlock.h
> > diff --git a/lib/librte_sched/rte_bitmap.h
> > b/lib/librte_eal/common/include/rte_bitmap.h
> > similarity index 100%
> > rename from lib/librte_sched/rte_bitmap.h
> > rename to lib/librte_eal/common/include/rte_bitmap.h
> > diff --git a/lib/librte_sched/Makefile b/lib/librte_sched/Makefile
> > index 18274e7..9a28a9e 100644
> > --- a/lib/librte_sched/Makefile
> > +++ b/lib/librte_sched/Makefile
> > @@ -55,7 +55,8 @@ SRCS-$(CONFIG_RTE_LIBRTE_SCHED) += rte_sched.c
> > rte_red.c rte_approx.c
> >  SRCS-$(CONFIG_RTE_LIBRTE_SCHED) += rte_reciprocal.c
> >
> >  # install includes
> > -SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include := rte_sched.h
> > rte_bitmap.h rte_sched_common.h rte_red.h rte_approx.h
> > -SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include += rte_reciprocal.h
> > +SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include := rte_sched.h
> > rte_sched_common.h
> > +SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include += rte_reciprocal.h
> > rte_red.h
> > +SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include += rte_approx.h
> >
>
> These changes are not required, please just remove the rte_bitmap.h from this list with no other changes.
>
> >  include $(RTE_SDK)/mk/rte.lib.mk
> > diff --git a/lib/librte_sched/rte_sched.c b/lib/librte_sched/rte_sched.c
> > index b7cba11..b3e0d4f 100644
> > --- a/lib/librte_sched/rte_sched.c
> > +++ b/lib/librte_sched/rte_sched.c
> > @@ -34,6 +34,7 @@
> >  #include <stdio.h>
> >  #include <string.h>
> >
> > +#include <rte_bitmap.h>
>
> Please #include <rte_bitmap.h> at the end of the #include <rte_*.h> list.
>
> >  #include <rte_common.h>
> >  #include <rte_log.h>
> >  #include <rte_memory.h>
> > @@ -44,7 +45,6 @@
> >  #include <rte_mbuf.h>
> >
> >  #include "rte_sched.h"
> > -#include "rte_bitmap.h"
> >  #include "rte_sched_common.h"
> >  #include "rte_approx.h"
> >  #include "rte_reciprocal.h"
> > --
> > 2.7.4
>
> Regards,
> Cristian
>

[dpdk-dev] [PATCH v3 1/3] eal: move bitmap from lib sched

[Pavan Nikhilesh]

From: Pavan Bhagavatula <pbhagavatula@caviumnetworks.com>

The librte_sched uses rte_bitmap to manage large arrays of bits in an
optimized method so, moving it to eal/common would allow other libraries
and applications to use it.

Signed-off-by: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
---

v3 changes:
 - address review comments

v2 changes:
 - undo rte_bitmap.h cosmetic changes
 - update maintainer info

 lib/librte_eal/common/Makefile                               | 1 +
 lib/{librte_sched => librte_eal/common/include}/rte_bitmap.h | 0
 lib/librte_sched/Makefile                                    | 2 +-
 lib/librte_sched/rte_sched.c                                 | 2 +-
 4 files changed, 3 insertions(+), 2 deletions(-)
 rename lib/{librte_sched => librte_eal/common/include}/rte_bitmap.h (100%)

diff --git a/lib/librte_eal/common/Makefile b/lib/librte_eal/common/Makefile
index e8fd67a..c2c6a7f 100644
--- a/lib/librte_eal/common/Makefile
+++ b/lib/librte_eal/common/Makefile
@@ -42,6 +42,7 @@ INC += rte_hexdump.h rte_devargs.h rte_bus.h rte_dev.h rte_vdev.h
 INC += rte_pci_dev_feature_defs.h rte_pci_dev_features.h
 INC += rte_malloc.h rte_keepalive.h rte_time.h
 INC += rte_service.h rte_service_component.h
+INC += rte_bitmap.h

 GENERIC_INC := rte_atomic.h rte_byteorder.h rte_cycles.h rte_prefetch.h
 GENERIC_INC += rte_spinlock.h rte_memcpy.h rte_cpuflags.h rte_rwlock.h
diff --git a/lib/librte_sched/rte_bitmap.h b/lib/librte_eal/common/include/rte_bitmap.h
similarity index 100%
rename from lib/librte_sched/rte_bitmap.h
rename to lib/librte_eal/common/include/rte_bitmap.h
diff --git a/lib/librte_sched/Makefile b/lib/librte_sched/Makefile
index 18274e7..e509447 100644
--- a/lib/librte_sched/Makefile
+++ b/lib/librte_sched/Makefile
@@ -55,7 +55,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_SCHED) += rte_sched.c rte_red.c rte_approx.c
 SRCS-$(CONFIG_RTE_LIBRTE_SCHED) += rte_reciprocal.c

 # install includes
-SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include := rte_sched.h rte_bitmap.h rte_sched_common.h rte_red.h rte_approx.h
+SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include := rte_sched.h rte_sched_common.h rte_red.h rte_approx.h
 SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include += rte_reciprocal.h

 include $(RTE_SDK)/mk/rte.lib.mk
diff --git a/lib/librte_sched/rte_sched.c b/lib/librte_sched/rte_sched.c
index b7cba11..a2d0d68 100644
--- a/lib/librte_sched/rte_sched.c
+++ b/lib/librte_sched/rte_sched.c
@@ -42,9 +42,9 @@
 #include <rte_prefetch.h>
 #include <rte_branch_prediction.h>
 #include <rte_mbuf.h>
+#include <rte_bitmap.h>

 #include "rte_sched.h"
-#include "rte_bitmap.h"
 #include "rte_sched_common.h"
 #include "rte_approx.h"
 #include "rte_reciprocal.h"
--
2.7.4

[dpdk-dev] [PATCH v3 2/3] test: add test for bitmap operations

[Pavan Nikhilesh]

From: Pavan Bhagavatula <pbhagavatula@caviumnetworks.com>

This patch adds a test for verifying the bitmap operations.

Signed-off-by: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
---
 test/test/Makefile      |   1 +
 test/test/test_bitmap.c | 192 ++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 193 insertions(+)
 create mode 100644 test/test/test_bitmap.c

diff --git a/test/test/Makefile b/test/test/Makefile
index 42d9a49..2fda8d9 100644
--- a/test/test/Makefile
+++ b/test/test/Makefile
@@ -94,6 +94,7 @@ SRCS-y += test_cycles.c
 SRCS-y += test_spinlock.c
 SRCS-y += test_memory.c
 SRCS-y += test_memzone.c
+SRCS-y += test_bitmap.c
 
 SRCS-y += test_ring.c
 SRCS-y += test_ring_perf.c
diff --git a/test/test/test_bitmap.c b/test/test/test_bitmap.c
new file mode 100644
index 0000000..5c9eee9
--- /dev/null
+++ b/test/test/test_bitmap.c
@@ -0,0 +1,192 @@
+/*
+ *   BSD LICENSE
+ *
+ *   Copyright (C) Cavium, Inc. 2017.
+ *
+ *   Redistribution and use in source and binary forms, with or without
+ *   modification, are permitted provided that the following conditions
+ *   are met:
+ *
+ *     * Redistributions of source code must retain the above copyright
+ *       notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above copyright
+ *       notice, this list of conditions and the following disclaimer in
+ *       the documentation and/or other materials provided with the
+ *       distribution.
+ *     * Neither the name of Cavium, Inc nor the names of its
+ *       contributors may be used to endorse or promote products derived
+ *       from this software without specific prior written permission.
+ *
+ *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <inttypes.h>
+
+#include <rte_common.h>
+#include <rte_bitmap.h>
+#include <rte_malloc.h>
+
+#include "test.h"
+
+#define MAX_BITS 1000
+
+static int
+test_bitmap_scan_operations(struct rte_bitmap *bmp)
+{
+	uint32_t pos = 0;
+	uint64_t slab1_magic = 0xBADC0FFEEBADF00D;
+	uint64_t slab2_magic = 0xFEEDDEADDEADF00D;
+	uint64_t out_slab = 0;
+
+	rte_bitmap_reset(bmp);
+
+	rte_bitmap_set_slab(bmp, pos, slab1_magic);
+	rte_bitmap_set_slab(bmp, pos + RTE_BITMAP_SLAB_BIT_SIZE, slab2_magic);
+
+	if (!rte_bitmap_scan(bmp, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab1_magic != out_slab) {
+		printf("Scan operation sanity failed.\n");
+		return TEST_FAILED;
+	}
+
+	if (!rte_bitmap_scan(bmp, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab2_magic != out_slab) {
+		printf("Scan operation sanity failed.\n");
+		return TEST_FAILED;
+	}
+
+	/* Wrap around */
+	if (!rte_bitmap_scan(bmp, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab1_magic != out_slab) {
+		printf("Scan operation wrap around failed.\n");
+		return TEST_FAILED;
+	}
+
+	/* Scan reset check. */
+	__rte_bitmap_scan_init(bmp);
+
+	if (!rte_bitmap_scan(bmp, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab1_magic != out_slab) {
+		printf("Scan reset operation failed.\n");
+		return TEST_FAILED;
+	}
+
+	return TEST_SUCCESS;
+}
+
+static int
+test_bitmap_slab_set_get(struct rte_bitmap *bmp)
+{
+	uint32_t pos = 0;
+	uint64_t slab_magic = 0xBADC0FFEEBADF00D;
+	uint64_t out_slab = 0;
+
+	rte_bitmap_reset(bmp);
+	rte_bitmap_set_slab(bmp, pos, slab_magic);
+
+	if (!rte_bitmap_scan(bmp, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap.\n");
+		return TEST_FAILED;
+	}
+
+
+	if (slab_magic != out_slab) {
+		printf("Invalid slab in bitmap.\n");
+		return TEST_FAILED;
+	}
+
+
+	return TEST_SUCCESS;
+}
+
+static int
+test_bitmap_set_get_clear(struct rte_bitmap *bmp)
+{
+	int i;
+
+	rte_bitmap_reset(bmp);
+	for (i = 0; i < MAX_BITS; i++)
+		rte_bitmap_set(bmp, i);
+
+	for (i = 0; i < MAX_BITS; i++) {
+		if (!rte_bitmap_get(bmp, i)) {
+			printf("Failed to get set bit.\n");
+			return TEST_FAILED;
+		}
+	}
+
+	for (i = 0; i < MAX_BITS; i++)
+		rte_bitmap_clear(bmp, i);
+
+	for (i = 0; i < MAX_BITS; i++) {
+		if (rte_bitmap_get(bmp, i)) {
+			printf("Failed to clear set bit.\n");
+			return TEST_FAILED;
+		}
+	}
+
+	return TEST_SUCCESS;
+}
+
+static int
+test_bitmap(void)
+{
+	void *mem;
+	uint32_t bmp_size;
+	struct rte_bitmap *bmp;
+
+	bmp_size =
+		rte_bitmap_get_memory_footprint(MAX_BITS);
+
+	mem = rte_zmalloc("test_bmap", bmp_size, RTE_CACHE_LINE_SIZE);
+	if (mem == NULL) {
+		printf("Failed to allocate memory for bitmap\n");
+		return TEST_FAILED;
+	}
+
+	bmp = rte_bitmap_init(MAX_BITS, mem, bmp_size);
+	if (bmp == NULL) {
+		printf("Failed to init bitmap\n");
+		return TEST_FAILED;
+	}
+
+	if (test_bitmap_set_get_clear(bmp) < 0)
+		return TEST_FAILED;
+
+	if (test_bitmap_slab_set_get(bmp) < 0)
+		return TEST_FAILED;
+
+	if (test_bitmap_scan_operations(bmp) < 0)
+		return TEST_FAILED;
+
+	return TEST_SUCCESS;
+}
+
+REGISTER_TEST_COMMAND(bitmap_test, test_bitmap);
-- 
2.7.4

[dpdk-dev] [PATCH v3 3/3] maintainers: add maintainer for bitmap

[Pavan Nikhilesh]

From: Pavan Bhagavatula <pbhagavatula@caviumnetworks.com>

Signed-off-by: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
---
 MAINTAINERS | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/MAINTAINERS b/MAINTAINERS
index a0cd75e..3522497 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -143,6 +143,11 @@ F: lib/librte_eal/common/rte_service.c
 F: doc/guides/prog_guide/service_cores.rst
 F: test/test/test_service_cores.c
 
+Bitmap
+M: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
+F: lib/librte_eal/common/include/rte_bitmap.h
+F: test/test/test_bitmap.c
+
 ARM v7
 M: Jan Viktorin <viktorin@rehivetech.com>
 M: Jianbo Liu <jianbo.liu@linaro.org>
-- 
2.7.4

Re: [dpdk-dev] [PATCH v3 1/3] eal: move bitmap from lib sched

[Dumitrescu, Cristian]

> -----Original Message-----
> From: Pavan Nikhilesh [mailto:pbhagavatula@caviumnetworks.com]
> Sent: Thursday, September 21, 2017 12:50 PM
> To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>;
> stephen@networkplumber.org
> Cc: dev@dpdk.org; Pavan Bhagavatula
> <pbhagavatula@caviumnetworks.com>
> Subject: [dpdk-dev] [PATCH v3 1/3] eal: move bitmap from lib sched
> 
> From: Pavan Bhagavatula <pbhagavatula@caviumnetworks.com>
> 
> The librte_sched uses rte_bitmap to manage large arrays of bits in an
> optimized method so, moving it to eal/common would allow other libraries
> and applications to use it.
> 
> Signed-off-by: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
> ---
> 
> v3 changes:
>  - address review comments
> 
> v2 changes:
>  - undo rte_bitmap.h cosmetic changes
>  - update maintainer info
> 
>  lib/librte_eal/common/Makefile                               | 1 +
>  lib/{librte_sched => librte_eal/common/include}/rte_bitmap.h | 0
>  lib/librte_sched/Makefile                                    | 2 +-
>  lib/librte_sched/rte_sched.c                                 | 2 +-
>  4 files changed, 3 insertions(+), 2 deletions(-)
>  rename lib/{librte_sched => librte_eal/common/include}/rte_bitmap.h
> (100%)
> 

Thanks very much, Pavan!

Series Acked-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>

Re: [dpdk-dev] [PATCH v3 1/3] eal: move bitmap from lib sched

[Thomas Monjalon]

> > From: Pavan Bhagavatula <pbhagavatula@caviumnetworks.com>
> > 
> > The librte_sched uses rte_bitmap to manage large arrays of bits in an
> > optimized method so, moving it to eal/common would allow other libraries
> > and applications to use it.
> > 
> > Signed-off-by: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
> 
> Thanks very much, Pavan!
> 
> Series Acked-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>

Applied, thanks