[PATCH] bitmap: add scan init at given position

[PATCH] bitmap: add scan init at given position

[Volodymyr Fialko]

Currently, in the case when we search for a bit set after a particular
value, the bitmap has to be scanned from the beginning and
rte_bitmap_scan() has to be called multiple times until we hit the value.

Add a new __rte_bitmap_scan_init_at() function to initialize scan state at
the given position, this will allow getting the next bit set after some
value within one rte_bitmap_scan() call.

Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
---
 app/test/test_bitmap.c       | 23 +++++++++++++++++++++++
 lib/eal/include/rte_bitmap.h | 22 ++++++++++++++++++++++
 2 files changed, 45 insertions(+)

diff --git a/app/test/test_bitmap.c b/app/test/test_bitmap.c
index e9c61590ae..69ff7262f3 100644
--- a/app/test/test_bitmap.c
+++ b/app/test/test_bitmap.c
@@ -71,6 +71,29 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp)
 		return TEST_FAILED;
 	}
 
+	/* Scan reset with count check. */
+	__rte_bitmap_scan_init_at(bmp, pos + RTE_BITMAP_SLAB_BIT_SIZE);
+	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 init at operation failed.\n");
+		return TEST_FAILED;
+	}
+
+	__rte_bitmap_scan_init_at(bmp, pos + 2 * RTE_BITMAP_SLAB_BIT_SIZE);
+	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 init at operation failed.\n");
+		return TEST_FAILED;
+	}
+
 	/* Test scan when a cline is half full */
 	rte_bitmap_reset(bmp);
 	for (i = 0; i < MAX_BITS; i++)
diff --git a/lib/eal/include/rte_bitmap.h b/lib/eal/include/rte_bitmap.h
index 27ee3d18a4..54a986aa8f 100644
--- a/lib/eal/include/rte_bitmap.h
+++ b/lib/eal/include/rte_bitmap.h
@@ -137,6 +137,28 @@ __rte_bitmap_scan_init(struct rte_bitmap *bmp)
 	bmp->go2 = 0;
 }
 
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Bitmap initialize internal scan pointers at the given position for the scan function.
+ * @see rte_bitmap_scan()
+ *
+ * @param bmp
+ *   Handle to bitmap instance
+ * @param pos
+ *   Bit position to start scan
+ */
+__rte_experimental
+static inline void
+__rte_bitmap_scan_init_at(struct rte_bitmap *bmp, uint32_t pos)
+{
+	bmp->index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
+	bmp->offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
+	bmp->index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
+	bmp->go2 = 1;
+}
+
 /**
  * Bitmap memory footprint calculation
  *
-- 
2.34.1

Re: [PATCH] bitmap: add scan init at given position

[Thomas Monjalon]

Cristian, please could you review this patch?

14/04/2023 10:39, Volodymyr Fialko:
> Currently, in the case when we search for a bit set after a particular
> value, the bitmap has to be scanned from the beginning and
> rte_bitmap_scan() has to be called multiple times until we hit the value.
> 
> Add a new __rte_bitmap_scan_init_at() function to initialize scan state at
> the given position, this will allow getting the next bit set after some
> value within one rte_bitmap_scan() call.
> 
> Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
[...]
> +__rte_experimental
> +static inline void
> +__rte_bitmap_scan_init_at(struct rte_bitmap *bmp, uint32_t pos)
> +{
> +	bmp->index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
> +	bmp->offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
> +	bmp->index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
> +	bmp->go2 = 1;
> +}

It is supposed to be an internal (inlined) function
but it is not used.

RE: [PATCH] bitmap: add scan init at given position

[Dumitrescu, Cristian]

Hi Volodymyr,

Thanks for your patch, comments below under your code:

> -----Original Message-----
> From: Thomas Monjalon <thomas@monjalon.net>
> Sent: Thursday, June 1, 2023 4:26 PM
> To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>; Volodymyr Fialko
> <vfialko@marvell.com>
> Cc: dev@dpdk.org; jerinj@marvell.com; anoobj@marvell.com
> Subject: Re: [PATCH] bitmap: add scan init at given position
> 
> Cristian, please could you review this patch?
> 
> 14/04/2023 10:39, Volodymyr Fialko:
> > Currently, in the case when we search for a bit set after a particular
> > value, the bitmap has to be scanned from the beginning and
> > rte_bitmap_scan() has to be called multiple times until we hit the value.
> >
> > Add a new __rte_bitmap_scan_init_at() function to initialize scan state at
> > the given position, this will allow getting the next bit set after some
> > value within one rte_bitmap_scan() call.
> >
> > Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
> [...]
> > +__rte_experimental
> > +static inline void
> > +__rte_bitmap_scan_init_at(struct rte_bitmap *bmp, uint32_t pos)
> > +{
> > +	bmp->index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 +
> RTE_BITMAP_CL_BIT_SIZE_LOG2);
> > +	bmp->offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) &
> RTE_BITMAP_SLAB_BIT_MASK;
> > +	bmp->index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
> > +	bmp->go2 = 1;
> > +}
> 
> It is supposed to be an internal (inlined) function
> but it is not used.
> 

My understanding is your proposed procedure for scanning starting at an offset is:
1. Call the new function: __rte_bitmap_scan_init_at()
2. Call the regular function: rte_bitmap_scan()

I think this procedure is not ideal, therefore I suggest we create a new API function which has an additional offset argument:

	rte_bitmap_scan_from_offset(struct rte_bitmap *bmp, uint32_t offset, uint32_t *pos, uint64_t *slab).

Under the hood, the new API should call an internal function similar to yours to start the scan at a given offset (while aborting any scan that might be in progress). Makes sense?

BTW, do we need to declare the experimental functions defined in a header file to the library map file? I don't see this in the patch, but the patch seems to compile and link fine ...

Regards,
Cristian 

Re: [PATCH] bitmap: add scan init at given position

[Bruce Richardson]

On Thu, Jun 08, 2023 at 02:20:13PM +0000, Dumitrescu, Cristian wrote:
> Hi Volodymyr,
> 
> Thanks for your patch, comments below under your code:
> 
> > -----Original Message-----
> > From: Thomas Monjalon <thomas@monjalon.net>
> > Sent: Thursday, June 1, 2023 4:26 PM
> > To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>; Volodymyr Fialko
> > <vfialko@marvell.com>
> > Cc: dev@dpdk.org; jerinj@marvell.com; anoobj@marvell.com
> > Subject: Re: [PATCH] bitmap: add scan init at given position
> > 
> > Cristian, please could you review this patch?
> > 
> > 14/04/2023 10:39, Volodymyr Fialko:
> > > Currently, in the case when we search for a bit set after a particular
> > > value, the bitmap has to be scanned from the beginning and
> > > rte_bitmap_scan() has to be called multiple times until we hit the value.
> > >
> > > Add a new __rte_bitmap_scan_init_at() function to initialize scan state at
> > > the given position, this will allow getting the next bit set after some
> > > value within one rte_bitmap_scan() call.
> > >
> > > Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
> > [...]
> > > +__rte_experimental
> > > +static inline void
> > > +__rte_bitmap_scan_init_at(struct rte_bitmap *bmp, uint32_t pos)
> > > +{
> > > +	bmp->index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 +
> > RTE_BITMAP_CL_BIT_SIZE_LOG2);
> > > +	bmp->offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) &
> > RTE_BITMAP_SLAB_BIT_MASK;
> > > +	bmp->index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
> > > +	bmp->go2 = 1;
> > > +}
> > 
> > It is supposed to be an internal (inlined) function
> > but it is not used.
> > 
> 
> My understanding is your proposed procedure for scanning starting at an offset is:
> 1. Call the new function: __rte_bitmap_scan_init_at()
> 2. Call the regular function: rte_bitmap_scan()
> 
> I think this procedure is not ideal, therefore I suggest we create a new API function which has an additional offset argument:
> 
> 	rte_bitmap_scan_from_offset(struct rte_bitmap *bmp, uint32_t offset, uint32_t *pos, uint64_t *slab).
> 
> Under the hood, the new API should call an internal function similar to yours to start the scan at a given offset (while aborting any scan that might be in progress). Makes sense?
> 
> BTW, do we need to declare the experimental functions defined in a header file to the library map file? I don't see this in the patch, but the patch seems to compile and link fine ...
> 
Inline functions in headers are not real "functions" in the output code, as
they get inlined into the caller. Therefore, they have no entries in the
version.map file, since they don't exist in the compiled object code.

/Bruce

RE: [PATCH] bitmap: add scan init at given position

[Volodymyr Fialko]

Hi Cristian,

<snip>
> 
> My understanding is your proposed procedure for scanning starting at an offset is:
> 1. Call the new function: __rte_bitmap_scan_init_at() 2. Call the regular function: rte_bitmap_scan()
> 
> I think this procedure is not ideal, therefore I suggest we create a new API function which has an
> additional offset argument:
> 
> 	rte_bitmap_scan_from_offset(struct rte_bitmap *bmp, uint32_t offset, uint32_t *pos,
> uint64_t *slab).
> 
> Under the hood, the new API should call an internal function similar to yours to start the scan at a
> given offset (while aborting any scan that might be in progress). Makes sense?
> 
> BTW, do we need to declare the experimental functions defined in a header file to the library map
> file? I don't see this in the patch, but the patch seems to compile and link fine ...
> 
> Regards,
> Cristian

I like the suggested idea to add ` rte_bitmap_scan_from_offset ` API. I will implement it in the next version.

[PATCH v2] bitmap: add scan from offset function

[Volodymyr Fialko]

Currently, in the case when we search for a bit set after a particular
value, the bitmap has to be scanned from the beginning and
rte_bitmap_scan() has to be called multiple times until we hit the value.

Add a new rte_bitmap_scan_from_offset() function to initialize scan
state at the given offset and perform scan, this will allow getting
the next set bit after certain offset within one scan call.

Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
---
 app/test/test_bitmap.c       | 33 ++++++++++++++++++++-
 lib/eal/include/rte_bitmap.h | 56 ++++++++++++++++++++++++++++++++++++
 2 files changed, 88 insertions(+), 1 deletion(-)

diff --git a/app/test/test_bitmap.c b/app/test/test_bitmap.c
index e9c61590ae..9e38087408 100644
--- a/app/test/test_bitmap.c
+++ b/app/test/test_bitmap.c
@@ -18,8 +18,8 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp)
 {
 	uint64_t slab1_magic = 0xBADC0FFEEBADF00D;
 	uint64_t slab2_magic = 0xFEEDDEADDEADF00D;
+	int i, nb_clear, nb_set, next_cl;
 	uint32_t pos = 0, start_pos;
-	int i, nb_clear, nb_set;
 	uint64_t out_slab = 0;
 
 	rte_bitmap_reset(bmp);
@@ -71,6 +71,37 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp)
 		return TEST_FAILED;
 	}
 
+	/* Scan with offset check. */
+	if (!rte_bitmap_scan_from_offset(bmp, RTE_BITMAP_SLAB_BIT_SIZE, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap with scan from offset.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab2_magic != out_slab) {
+		printf("Scan from offset operation failed.\n");
+		return TEST_FAILED;
+	}
+
+	/* Scan with offset wrap around check. */
+	if (!rte_bitmap_scan_from_offset(bmp, 2 * RTE_BITMAP_SLAB_BIT_SIZE, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap with scan from offset.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab1_magic != out_slab) {
+		printf("Scan from offset with wrap around operation failed.\n");
+		return TEST_FAILED;
+	}
+
+	/* Test scan when the bit set is on a next cline */
+	rte_bitmap_reset(bmp);
+	next_cl = RTE_MIN(RTE_BITMAP_CL_BIT_SIZE, MAX_BITS);
+	rte_bitmap_set(bmp, next_cl);
+	if (!rte_bitmap_scan_from_offset(bmp, 0, &pos, &out_slab)) {
+		printf("Failed to get slab from next cache line from bitmap.\n");
+		return TEST_FAILED;
+	}
+
 	/* Test scan when a cline is half full */
 	rte_bitmap_reset(bmp);
 	for (i = 0; i < MAX_BITS; i++)
diff --git a/lib/eal/include/rte_bitmap.h b/lib/eal/include/rte_bitmap.h
index 27ee3d18a4..624365b9c5 100644
--- a/lib/eal/include/rte_bitmap.h
+++ b/lib/eal/include/rte_bitmap.h
@@ -137,6 +137,30 @@ __rte_bitmap_scan_init(struct rte_bitmap *bmp)
 	bmp->go2 = 0;
 }
 
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Bitmap initialize internal scan pointers at the given position for the scan function.
+ *
+ * @param bmp
+ *   Handle to bitmap instance
+ * @param pos
+ *   Bit position to start scan
+ */
+__rte_experimental
+static inline void
+__rte_bitmap_scan_init_at(struct rte_bitmap *bmp, uint32_t pos)
+{
+	uint64_t *slab1;
+
+	bmp->index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
+	bmp->offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
+	bmp->index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
+	slab1 = bmp->array1 + bmp->index1;
+	bmp->go2 = *slab1 & (1llu << bmp->offset1);
+}
+
 /**
  * Bitmap memory footprint calculation
  *
@@ -591,6 +615,38 @@ rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
 	return 0;
 }
 
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Bitmap scan from the given offset.
+ * Function will reset internal scan state to start scanning from the offset
+ * position.
+ * @see rte_bitmap_scan()
+ *
+ * @param bmp
+ *   Handle to bitmap instance
+ * @param offset
+ *   Bit offset to start scan
+ * @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.
+ *   When function call returns 0, slab is not modified.
+ * @return
+ *   0 if there is no bit set in the bitmap, 1 otherwise
+ */
+__rte_experimental
+static inline int
+rte_bitmap_scan_from_offset(struct rte_bitmap *bmp, uint32_t offset,
+			    uint32_t *pos, uint64_t *slab)
+{
+	__rte_bitmap_scan_init_at(bmp, offset);
+	return rte_bitmap_scan(bmp, pos, slab);
+}
+
 #ifdef __cplusplus
 }
 #endif
-- 
2.34.1

RE: [PATCH v2] bitmap: add scan from offset function

[Dumitrescu, Cristian]

> -----Original Message-----
> From: Volodymyr Fialko <vfialko@marvell.com>
> Sent: Tuesday, June 13, 2023 4:40 PM
> To: dev@dpdk.org; Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> Cc: jerinj@marvell.com; anoobj@marvell.com; thomas@monjalon.net;
> Volodymyr Fialko <vfialko@marvell.com>
> Subject: [PATCH v2] bitmap: add scan from offset function
> 
> Currently, in the case when we search for a bit set after a particular
> value, the bitmap has to be scanned from the beginning and
> rte_bitmap_scan() has to be called multiple times until we hit the value.
> 
> Add a new rte_bitmap_scan_from_offset() function to initialize scan
> state at the given offset and perform scan, this will allow getting
> the next set bit after certain offset within one scan call.
> 
> Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
> ---
>  app/test/test_bitmap.c       | 33 ++++++++++++++++++++-
>  lib/eal/include/rte_bitmap.h | 56 ++++++++++++++++++++++++++++++++++++
>  2 files changed, 88 insertions(+), 1 deletion(-)
> 
<snip>

> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change without prior notice.
> + *
> + * Bitmap initialize internal scan pointers at the given position for the scan
> function.
> + *
> + * @param bmp
> + *   Handle to bitmap instance
> + * @param pos
> + *   Bit position to start scan
> + */
> +__rte_experimental
> +static inline void
> +__rte_bitmap_scan_init_at(struct rte_bitmap *bmp, uint32_t pos)

Please add a note for this function to mark it as internal, which should be obvious from the double underscore prefix in the name, but better to write it explicitly as well.

[PATCH v3] bitmap: add scan from offset function

[Volodymyr Fialko]

Currently, in the case when we search for a bit set after a particular
value, the bitmap has to be scanned from the beginning and
rte_bitmap_scan() has to be called multiple times until we hit the value.

Add a new rte_bitmap_scan_from_offset() function to initialize scan
state at the given offset and perform scan, this will allow getting
the next set bit after certain offset within one scan call.

Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
---
v2:
 - added rte_bitmap_scan_from_offset
v3
 - added note for internal use only for init_at function

 app/test/test_bitmap.c       | 33 +++++++++++++++++++-
 lib/eal/include/rte_bitmap.h | 59 ++++++++++++++++++++++++++++++++++++
 2 files changed, 91 insertions(+), 1 deletion(-)

diff --git a/app/test/test_bitmap.c b/app/test/test_bitmap.c
index e9c61590ae..9e38087408 100644
--- a/app/test/test_bitmap.c
+++ b/app/test/test_bitmap.c
@@ -18,8 +18,8 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp)
 {
 	uint64_t slab1_magic = 0xBADC0FFEEBADF00D;
 	uint64_t slab2_magic = 0xFEEDDEADDEADF00D;
+	int i, nb_clear, nb_set, next_cl;
 	uint32_t pos = 0, start_pos;
-	int i, nb_clear, nb_set;
 	uint64_t out_slab = 0;
 
 	rte_bitmap_reset(bmp);
@@ -71,6 +71,37 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp)
 		return TEST_FAILED;
 	}
 
+	/* Scan with offset check. */
+	if (!rte_bitmap_scan_from_offset(bmp, RTE_BITMAP_SLAB_BIT_SIZE, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap with scan from offset.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab2_magic != out_slab) {
+		printf("Scan from offset operation failed.\n");
+		return TEST_FAILED;
+	}
+
+	/* Scan with offset wrap around check. */
+	if (!rte_bitmap_scan_from_offset(bmp, 2 * RTE_BITMAP_SLAB_BIT_SIZE, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap with scan from offset.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab1_magic != out_slab) {
+		printf("Scan from offset with wrap around operation failed.\n");
+		return TEST_FAILED;
+	}
+
+	/* Test scan when the bit set is on a next cline */
+	rte_bitmap_reset(bmp);
+	next_cl = RTE_MIN(RTE_BITMAP_CL_BIT_SIZE, MAX_BITS);
+	rte_bitmap_set(bmp, next_cl);
+	if (!rte_bitmap_scan_from_offset(bmp, 0, &pos, &out_slab)) {
+		printf("Failed to get slab from next cache line from bitmap.\n");
+		return TEST_FAILED;
+	}
+
 	/* Test scan when a cline is half full */
 	rte_bitmap_reset(bmp);
 	for (i = 0; i < MAX_BITS; i++)
diff --git a/lib/eal/include/rte_bitmap.h b/lib/eal/include/rte_bitmap.h
index 27ee3d18a4..b8de7c46c9 100644
--- a/lib/eal/include/rte_bitmap.h
+++ b/lib/eal/include/rte_bitmap.h
@@ -137,6 +137,33 @@ __rte_bitmap_scan_init(struct rte_bitmap *bmp)
 	bmp->go2 = 0;
 }
 
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Bitmap initialize internal scan pointers at the given position for the scan function.
+ *
+ * Note: for private/internal use, for public:
+ * @see rte_bitmap_scan_from_offset()
+ *
+ * @param bmp
+ *   Handle to bitmap instance
+ * @param pos
+ *   Bit position to start scan
+ */
+__rte_experimental
+static inline void
+__rte_bitmap_scan_init_at(struct rte_bitmap *bmp, uint32_t pos)
+{
+	uint64_t *slab1;
+
+	bmp->index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
+	bmp->offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
+	bmp->index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
+	slab1 = bmp->array1 + bmp->index1;
+	bmp->go2 = *slab1 & (1llu << bmp->offset1);
+}
+
 /**
  * Bitmap memory footprint calculation
  *
@@ -591,6 +618,38 @@ rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
 	return 0;
 }
 
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Bitmap scan from the given offset.
+ * Function will reset internal scan state to start scanning from the offset
+ * position.
+ * @see rte_bitmap_scan()
+ *
+ * @param bmp
+ *   Handle to bitmap instance
+ * @param offset
+ *   Bit offset to start scan
+ * @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.
+ *   When function call returns 0, slab is not modified.
+ * @return
+ *   0 if there is no bit set in the bitmap, 1 otherwise
+ */
+__rte_experimental
+static inline int
+rte_bitmap_scan_from_offset(struct rte_bitmap *bmp, uint32_t offset,
+			    uint32_t *pos, uint64_t *slab)
+{
+	__rte_bitmap_scan_init_at(bmp, offset);
+	return rte_bitmap_scan(bmp, pos, slab);
+}
+
 #ifdef __cplusplus
 }
 #endif
-- 
2.34.1

RE: [PATCH v3] bitmap: add scan from offset function

[Dumitrescu, Cristian]

> -----Original Message-----
> From: Volodymyr Fialko <vfialko@marvell.com>
> Sent: Wednesday, June 21, 2023 11:01 AM
> To: dev@dpdk.org; Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> Cc: jerinj@marvell.com; anoobj@marvell.com; thomas@monjalon.net;
> Volodymyr Fialko <vfialko@marvell.com>
> Subject: [PATCH v3] bitmap: add scan from offset function
> 
> Currently, in the case when we search for a bit set after a particular
> value, the bitmap has to be scanned from the beginning and
> rte_bitmap_scan() has to be called multiple times until we hit the value.
> 
> Add a new rte_bitmap_scan_from_offset() function to initialize scan
> state at the given offset and perform scan, this will allow getting
> the next set bit after certain offset within one scan call.
> 
> Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
> ---

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

Re: [PATCH v3] bitmap: add scan from offset function

[Thomas Monjalon]

21/06/2023 12:01, Volodymyr Fialko:
> Currently, in the case when we search for a bit set after a particular
> value, the bitmap has to be scanned from the beginning and
> rte_bitmap_scan() has to be called multiple times until we hit the value.
> 
> Add a new rte_bitmap_scan_from_offset() function to initialize scan
> state at the given offset and perform scan, this will allow getting
> the next set bit after certain offset within one scan call.
> 
> Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
> ---
> v2:
>  - added rte_bitmap_scan_from_offset
> v3
>  - added note for internal use only for init_at function
[...]
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change without prior notice.
> + *
> + * Bitmap initialize internal scan pointers at the given position for the scan function.
> + *
> + * Note: for private/internal use, for public:
> + * @see rte_bitmap_scan_from_offset()
> + *
> + * @param bmp
> + *   Handle to bitmap instance
> + * @param pos
> + *   Bit position to start scan
> + */
> +__rte_experimental
> +static inline void
> +__rte_bitmap_scan_init_at(struct rte_bitmap *bmp, uint32_t pos)

I think it should marked with __rte_internal instead of experimental.

RE: [PATCH v3] bitmap: add scan from offset function

[Dumitrescu, Cristian]

> -----Original Message-----
> From: Thomas Monjalon <thomas@monjalon.net>
> Sent: Thursday, June 22, 2023 6:45 PM
> To: Volodymyr Fialko <vfialko@marvell.com>
> Cc: dev@dpdk.org; Dumitrescu, Cristian <cristian.dumitrescu@intel.com>;
> jerinj@marvell.com; anoobj@marvell.com
> Subject: Re: [PATCH v3] bitmap: add scan from offset function
> 
> 21/06/2023 12:01, Volodymyr Fialko:
> > Currently, in the case when we search for a bit set after a particular
> > value, the bitmap has to be scanned from the beginning and
> > rte_bitmap_scan() has to be called multiple times until we hit the value.
> >
> > Add a new rte_bitmap_scan_from_offset() function to initialize scan
> > state at the given offset and perform scan, this will allow getting
> > the next set bit after certain offset within one scan call.
> >
> > Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
> > ---
> > v2:
> >  - added rte_bitmap_scan_from_offset
> > v3
> >  - added note for internal use only for init_at function
> [...]
> > +/**
> > + * @warning
> > + * @b EXPERIMENTAL: this API may change without prior notice.
> > + *
> > + * Bitmap initialize internal scan pointers at the given position for the scan
> function.
> > + *
> > + * Note: for private/internal use, for public:
> > + * @see rte_bitmap_scan_from_offset()
> > + *
> > + * @param bmp
> > + *   Handle to bitmap instance
> > + * @param pos
> > + *   Bit position to start scan
> > + */
> > +__rte_experimental
> > +static inline void
> > +__rte_bitmap_scan_init_at(struct rte_bitmap *bmp, uint32_t pos)
> 
> I think it should marked with __rte_internal instead of experimental.
> 
> 


+1

RE: [PATCH v3] bitmap: add scan from offset function

[Volodymyr Fialko]

Since it's header-only library, there is issue with using __rte_intenal (appeared in v4).
Even if the function itself is not used directly, it get's included to the other public files.
It explains why other functions in this library does not have the rte_internal prefix, but the double underscores.
So, should I simply remove __rte_internal from v4, or there's another approach to resolve this issue(beside creating .c file)?

/Volodymyr

> -----Original Message-----
> From: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> Sent: Friday, June 23, 2023 2:41 PM
> To: Thomas Monjalon <thomas@monjalon.net>; Volodymyr Fialko <vfialko@marvell.com>
> Cc: dev@dpdk.org; Jerin Jacob Kollanukkaran <jerinj@marvell.com>; Anoob Joseph
> <anoobj@marvell.com>
> Subject: [EXT] RE: [PATCH v3] bitmap: add scan from offset function
> 
> External Email
> 
> ----------------------------------------------------------------------
> 
> 
> > -----Original Message-----
> > From: Thomas Monjalon <thomas@monjalon.net>
> > Sent: Thursday, June 22, 2023 6:45 PM
> > To: Volodymyr Fialko <vfialko@marvell.com>
> > Cc: dev@dpdk.org; Dumitrescu, Cristian
> > <cristian.dumitrescu@intel.com>; jerinj@marvell.com;
> > anoobj@marvell.com
> > Subject: Re: [PATCH v3] bitmap: add scan from offset function
> >
> > 21/06/2023 12:01, Volodymyr Fialko:
> > > Currently, in the case when we search for a bit set after a
> > > particular value, the bitmap has to be scanned from the beginning
> > > and
> > > rte_bitmap_scan() has to be called multiple times until we hit the value.
> > >
> > > Add a new rte_bitmap_scan_from_offset() function to initialize scan
> > > state at the given offset and perform scan, this will allow getting
> > > the next set bit after certain offset within one scan call.
> > >
> > > Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
> > > ---
> > > v2:
> > >  - added rte_bitmap_scan_from_offset
> > > v3
> > >  - added note for internal use only for init_at function
> > [...]
> > > +/**
> > > + * @warning
> > > + * @b EXPERIMENTAL: this API may change without prior notice.
> > > + *
> > > + * Bitmap initialize internal scan pointers at the given position
> > > +for the scan
> > function.
> > > + *
> > > + * Note: for private/internal use, for public:
> > > + * @see rte_bitmap_scan_from_offset()
> > > + *
> > > + * @param bmp
> > > + *   Handle to bitmap instance
> > > + * @param pos
> > > + *   Bit position to start scan
> > > + */
> > > +__rte_experimental
> > > +static inline void
> > > +__rte_bitmap_scan_init_at(struct rte_bitmap *bmp, uint32_t pos)
> >
> > I think it should marked with __rte_internal instead of experimental.
> >
> >
> 
> 
> +1

Re: [PATCH v3] bitmap: add scan from offset function

[Thomas Monjalon]

03/07/2023 12:56, Volodymyr Fialko:
> Since it's header-only library, there is issue with using __rte_intenal (appeared in v4).

What is the issue?

> Even if the function itself is not used directly, it get's included to the other public files.
> It explains why other functions in this library does not have the rte_internal prefix, but the double underscores.
> So, should I simply remove __rte_internal from v4, or there's another approach to resolve this issue(beside creating .c file)?
> 
> /Volodymyr
> 
> > -----Original Message-----
> > From: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> > Sent: Friday, June 23, 2023 2:41 PM
> > To: Thomas Monjalon <thomas@monjalon.net>; Volodymyr Fialko <vfialko@marvell.com>
> > Cc: dev@dpdk.org; Jerin Jacob Kollanukkaran <jerinj@marvell.com>; Anoob Joseph
> > <anoobj@marvell.com>
> > Subject: [EXT] RE: [PATCH v3] bitmap: add scan from offset function
> > 
> > External Email
> > 
> > ----------------------------------------------------------------------
> > 
> > 
> > > -----Original Message-----
> > > From: Thomas Monjalon <thomas@monjalon.net>
> > > Sent: Thursday, June 22, 2023 6:45 PM
> > > To: Volodymyr Fialko <vfialko@marvell.com>
> > > Cc: dev@dpdk.org; Dumitrescu, Cristian
> > > <cristian.dumitrescu@intel.com>; jerinj@marvell.com;
> > > anoobj@marvell.com
> > > Subject: Re: [PATCH v3] bitmap: add scan from offset function
> > >
> > > 21/06/2023 12:01, Volodymyr Fialko:
> > > > Currently, in the case when we search for a bit set after a
> > > > particular value, the bitmap has to be scanned from the beginning
> > > > and
> > > > rte_bitmap_scan() has to be called multiple times until we hit the value.
> > > >
> > > > Add a new rte_bitmap_scan_from_offset() function to initialize scan
> > > > state at the given offset and perform scan, this will allow getting
> > > > the next set bit after certain offset within one scan call.
> > > >
> > > > Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
> > > > ---
> > > > v2:
> > > >  - added rte_bitmap_scan_from_offset
> > > > v3
> > > >  - added note for internal use only for init_at function
> > > [...]
> > > > +/**
> > > > + * @warning
> > > > + * @b EXPERIMENTAL: this API may change without prior notice.
> > > > + *
> > > > + * Bitmap initialize internal scan pointers at the given position
> > > > +for the scan
> > > function.
> > > > + *
> > > > + * Note: for private/internal use, for public:
> > > > + * @see rte_bitmap_scan_from_offset()
> > > > + *
> > > > + * @param bmp
> > > > + *   Handle to bitmap instance
> > > > + * @param pos
> > > > + *   Bit position to start scan
> > > > + */
> > > > +__rte_experimental
> > > > +static inline void
> > > > +__rte_bitmap_scan_init_at(struct rte_bitmap *bmp, uint32_t pos)
> > >
> > > I think it should marked with __rte_internal instead of experimental.
> > >
> > >
> > 
> > 
> > +1
> 

RE: [EXT] Re: [PATCH v3] bitmap: add scan from offset function

[Volodymyr Fialko]

> -----Original Message-----
> From: Thomas Monjalon <thomas@monjalon.net>
> Sent: Monday, July 3, 2023 1:51 PM
> To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>; Volodymyr Fialko <vfialko@marvell.com>
> Cc: dev@dpdk.org; Jerin Jacob Kollanukkaran <jerinj@marvell.com>; Anoob Joseph
> <anoobj@marvell.com>
> Subject: [EXT] Re: [PATCH v3] bitmap: add scan from offset function
> 
> External Email
> 
> ----------------------------------------------------------------------
> 03/07/2023 12:56, Volodymyr Fialko:
> > Since it's header-only library, there is issue with using __rte_intenal (appeared in v4).
> 
> What is the issue?

From V4 ci build failure(http://mails.dpdk.org/archives/test-report/2023-July/421235.html):
	In file included from ../examples/ipsec-secgw/event_helper.c:6:
	../lib/eal/include/rte_bitmap.h:645:2: error: Symbol is not public ABI
	        __rte_bitmap_scan_init_at(bmp, offset);
 	       ^
	../lib/eal/include/rte_bitmap.h:150:1: note: from 'diagnose_if' attribute on '__rte_bitmap_scan_init_at':
	__rte_internal
	^~~~~~~~~~~~~~
	../lib/eal/include/rte_compat.h:42:16: note: expanded from macro '__rte_internal'	
	__attribute__((diagnose_if(1, "Symbol is not public ABI", "error"), \
              		^           ~
	1 error generated.

/Volodymyr
> 
> > Even if the function itself is not used directly, it get's included to the other public files.
> > It explains why other functions in this library does not have the rte_internal prefix, but the double
> underscores.
> > So, should I simply remove __rte_internal from v4, or there's another approach to resolve this
> issue(beside creating .c file)?
> >
> > /Volodymyr
> >
> > > -----Original Message-----
> > > From: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> > > Sent: Friday, June 23, 2023 2:41 PM
> > > To: Thomas Monjalon <thomas@monjalon.net>; Volodymyr Fialko
> > > <vfialko@marvell.com>
> > > Cc: dev@dpdk.org; Jerin Jacob Kollanukkaran <jerinj@marvell.com>;
> > > Anoob Joseph <anoobj@marvell.com>
> > > Subject: [EXT] RE: [PATCH v3] bitmap: add scan from offset function
> > >
> > > External Email
> > >
> > > --------------------------------------------------------------------
> > > --
> > >
> > >
> > > > -----Original Message-----
> > > > From: Thomas Monjalon <thomas@monjalon.net>
> > > > Sent: Thursday, June 22, 2023 6:45 PM
> > > > To: Volodymyr Fialko <vfialko@marvell.com>
> > > > Cc: dev@dpdk.org; Dumitrescu, Cristian
> > > > <cristian.dumitrescu@intel.com>; jerinj@marvell.com;
> > > > anoobj@marvell.com
> > > > Subject: Re: [PATCH v3] bitmap: add scan from offset function
> > > >
> > > > 21/06/2023 12:01, Volodymyr Fialko:
> > > > > Currently, in the case when we search for a bit set after a
> > > > > particular value, the bitmap has to be scanned from the
> > > > > beginning and
> > > > > rte_bitmap_scan() has to be called multiple times until we hit the value.
> > > > >
> > > > > Add a new rte_bitmap_scan_from_offset() function to initialize
> > > > > scan state at the given offset and perform scan, this will allow
> > > > > getting the next set bit after certain offset within one scan call.
> > > > >
> > > > > Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
> > > > > ---
> > > > > v2:
> > > > >  - added rte_bitmap_scan_from_offset
> > > > > v3
> > > > >  - added note for internal use only for init_at function
> > > > [...]
> > > > > +/**
> > > > > + * @warning
> > > > > + * @b EXPERIMENTAL: this API may change without prior notice.
> > > > > + *
> > > > > + * Bitmap initialize internal scan pointers at the given
> > > > > +position for the scan
> > > > function.
> > > > > + *
> > > > > + * Note: for private/internal use, for public:
> > > > > + * @see rte_bitmap_scan_from_offset()
> > > > > + *
> > > > > + * @param bmp
> > > > > + *   Handle to bitmap instance
> > > > > + * @param pos
> > > > > + *   Bit position to start scan
> > > > > + */
> > > > > +__rte_experimental
> > > > > +static inline void
> > > > > +__rte_bitmap_scan_init_at(struct rte_bitmap *bmp, uint32_t pos)
> > > >
> > > > I think it should marked with __rte_internal instead of experimental.
> > > >
> > > >
> > >
> > >
> > > +1
> >
> 
> 
> 
> 

Re: [EXT] Re: [PATCH v3] bitmap: add scan from offset function

[Thomas Monjalon]

03/07/2023 14:02, Volodymyr Fialko:
> 
> > -----Original Message-----
> > From: Thomas Monjalon <thomas@monjalon.net>
> > Sent: Monday, July 3, 2023 1:51 PM
> > To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>; Volodymyr Fialko <vfialko@marvell.com>
> > Cc: dev@dpdk.org; Jerin Jacob Kollanukkaran <jerinj@marvell.com>; Anoob Joseph
> > <anoobj@marvell.com>
> > Subject: [EXT] Re: [PATCH v3] bitmap: add scan from offset function
> > 
> > External Email
> > 
> > ----------------------------------------------------------------------
> > 03/07/2023 12:56, Volodymyr Fialko:
> > > Since it's header-only library, there is issue with using __rte_intenal (appeared in v4).
> > 
> > What is the issue?
> 
> From V4 ci build failure(http://mails.dpdk.org/archives/test-report/2023-July/421235.html):
> 	In file included from ../examples/ipsec-secgw/event_helper.c:6:
> 	../lib/eal/include/rte_bitmap.h:645:2: error: Symbol is not public ABI
> 	        __rte_bitmap_scan_init_at(bmp, offset);
>  	       ^
> 	../lib/eal/include/rte_bitmap.h:150:1: note: from 'diagnose_if' attribute on '__rte_bitmap_scan_init_at':
> 	__rte_internal
> 	^~~~~~~~~~~~~~
> 	../lib/eal/include/rte_compat.h:42:16: note: expanded from macro '__rte_internal'	
> 	__attribute__((diagnose_if(1, "Symbol is not public ABI", "error"), \
>               		^           ~
> 	1 error generated.

OK I see.
So we should give up with __rte_internal for inline functions.
As it is not supposed to be exposed to the applications,
I think we can skip the __rte_experimental flag.

> > > Even if the function itself is not used directly, it get's included to the other public files.
> > > It explains why other functions in this library does not have the rte_internal prefix, but the double
> > underscores.
> > > So, should I simply remove __rte_internal from v4, or there's another approach to resolve this
> > issue(beside creating .c file)?
> > >
> > > /Volodymyr
> > >
> > > > -----Original Message-----
> > > > From: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> > > > Sent: Friday, June 23, 2023 2:41 PM
> > > > To: Thomas Monjalon <thomas@monjalon.net>; Volodymyr Fialko
> > > > <vfialko@marvell.com>
> > > > Cc: dev@dpdk.org; Jerin Jacob Kollanukkaran <jerinj@marvell.com>;
> > > > Anoob Joseph <anoobj@marvell.com>
> > > > Subject: [EXT] RE: [PATCH v3] bitmap: add scan from offset function
> > > >
> > > > External Email
> > > >
> > > > --------------------------------------------------------------------
> > > > --
> > > >
> > > >
> > > > > -----Original Message-----
> > > > > From: Thomas Monjalon <thomas@monjalon.net>
> > > > > Sent: Thursday, June 22, 2023 6:45 PM
> > > > > To: Volodymyr Fialko <vfialko@marvell.com>
> > > > > Cc: dev@dpdk.org; Dumitrescu, Cristian
> > > > > <cristian.dumitrescu@intel.com>; jerinj@marvell.com;
> > > > > anoobj@marvell.com
> > > > > Subject: Re: [PATCH v3] bitmap: add scan from offset function
> > > > >
> > > > > 21/06/2023 12:01, Volodymyr Fialko:
> > > > > > Currently, in the case when we search for a bit set after a
> > > > > > particular value, the bitmap has to be scanned from the
> > > > > > beginning and
> > > > > > rte_bitmap_scan() has to be called multiple times until we hit the value.
> > > > > >
> > > > > > Add a new rte_bitmap_scan_from_offset() function to initialize
> > > > > > scan state at the given offset and perform scan, this will allow
> > > > > > getting the next set bit after certain offset within one scan call.
> > > > > >
> > > > > > Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
> > > > > > ---
> > > > > > v2:
> > > > > >  - added rte_bitmap_scan_from_offset
> > > > > > v3
> > > > > >  - added note for internal use only for init_at function
> > > > > [...]
> > > > > > +/**
> > > > > > + * @warning
> > > > > > + * @b EXPERIMENTAL: this API may change without prior notice.
> > > > > > + *
> > > > > > + * Bitmap initialize internal scan pointers at the given
> > > > > > +position for the scan
> > > > > function.
> > > > > > + *
> > > > > > + * Note: for private/internal use, for public:
> > > > > > + * @see rte_bitmap_scan_from_offset()
> > > > > > + *
> > > > > > + * @param bmp
> > > > > > + *   Handle to bitmap instance
> > > > > > + * @param pos
> > > > > > + *   Bit position to start scan
> > > > > > + */
> > > > > > +__rte_experimental
> > > > > > +static inline void
> > > > > > +__rte_bitmap_scan_init_at(struct rte_bitmap *bmp, uint32_t pos)
> > > > >
> > > > > I think it should marked with __rte_internal instead of experimental.
> > > > >
> > > > >
> > > >
> > > >
> > > > +1
> > >
> > 
> > 
> > 
> > 
> 
> 

[PATCH v4] bitmap: add scan from offset function

[Volodymyr Fialko]

Currently, in the case when we search for a bit set after a particular
value, the bitmap has to be scanned from the beginning and
rte_bitmap_scan() has to be called multiple times until we hit the value.

Add a new rte_bitmap_scan_from_offset() function to initialize scan
state at the given offset and perform scan, this will allow getting
the next set bit after certain offset within one scan call.

Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
---
v2:
 - added rte_bitmap_scan_from_offset
v3:
 - added note for internal use only for init_at function
v4:
 - marked init_at function as __rte_internal

 app/test/test_bitmap.c       | 33 ++++++++++++++++++++-
 lib/eal/include/rte_bitmap.h | 56 ++++++++++++++++++++++++++++++++++++
 2 files changed, 88 insertions(+), 1 deletion(-)

diff --git a/app/test/test_bitmap.c b/app/test/test_bitmap.c
index e9c61590ae..9e38087408 100644
--- a/app/test/test_bitmap.c
+++ b/app/test/test_bitmap.c
@@ -18,8 +18,8 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp)
 {
 	uint64_t slab1_magic = 0xBADC0FFEEBADF00D;
 	uint64_t slab2_magic = 0xFEEDDEADDEADF00D;
+	int i, nb_clear, nb_set, next_cl;
 	uint32_t pos = 0, start_pos;
-	int i, nb_clear, nb_set;
 	uint64_t out_slab = 0;
 
 	rte_bitmap_reset(bmp);
@@ -71,6 +71,37 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp)
 		return TEST_FAILED;
 	}
 
+	/* Scan with offset check. */
+	if (!rte_bitmap_scan_from_offset(bmp, RTE_BITMAP_SLAB_BIT_SIZE, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap with scan from offset.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab2_magic != out_slab) {
+		printf("Scan from offset operation failed.\n");
+		return TEST_FAILED;
+	}
+
+	/* Scan with offset wrap around check. */
+	if (!rte_bitmap_scan_from_offset(bmp, 2 * RTE_BITMAP_SLAB_BIT_SIZE, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap with scan from offset.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab1_magic != out_slab) {
+		printf("Scan from offset with wrap around operation failed.\n");
+		return TEST_FAILED;
+	}
+
+	/* Test scan when the bit set is on a next cline */
+	rte_bitmap_reset(bmp);
+	next_cl = RTE_MIN(RTE_BITMAP_CL_BIT_SIZE, MAX_BITS);
+	rte_bitmap_set(bmp, next_cl);
+	if (!rte_bitmap_scan_from_offset(bmp, 0, &pos, &out_slab)) {
+		printf("Failed to get slab from next cache line from bitmap.\n");
+		return TEST_FAILED;
+	}
+
 	/* Test scan when a cline is half full */
 	rte_bitmap_reset(bmp);
 	for (i = 0; i < MAX_BITS; i++)
diff --git a/lib/eal/include/rte_bitmap.h b/lib/eal/include/rte_bitmap.h
index 27ee3d18a4..0b9ae8f135 100644
--- a/lib/eal/include/rte_bitmap.h
+++ b/lib/eal/include/rte_bitmap.h
@@ -137,6 +137,30 @@ __rte_bitmap_scan_init(struct rte_bitmap *bmp)
 	bmp->go2 = 0;
 }
 
+/**
+ * Bitmap initialize internal scan pointers at the given position for the scan function.
+ *
+ * Note: for private/internal use, for public:
+ * @see rte_bitmap_scan_from_offset()
+ *
+ * @param bmp
+ *   Handle to bitmap instance
+ * @param pos
+ *   Bit position to start scan
+ */
+__rte_internal
+static inline void
+__rte_bitmap_scan_init_at(struct rte_bitmap *bmp, uint32_t pos)
+{
+	uint64_t *slab1;
+
+	bmp->index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
+	bmp->offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
+	bmp->index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
+	slab1 = bmp->array1 + bmp->index1;
+	bmp->go2 = *slab1 & (1llu << bmp->offset1);
+}
+
 /**
  * Bitmap memory footprint calculation
  *
@@ -591,6 +615,38 @@ rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
 	return 0;
 }
 
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Bitmap scan from the given offset.
+ * Function will reset internal scan state to start scanning from the offset
+ * position.
+ * @see rte_bitmap_scan()
+ *
+ * @param bmp
+ *   Handle to bitmap instance
+ * @param offset
+ *   Bit offset to start scan
+ * @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.
+ *   When function call returns 0, slab is not modified.
+ * @return
+ *   0 if there is no bit set in the bitmap, 1 otherwise
+ */
+__rte_experimental
+static inline int
+rte_bitmap_scan_from_offset(struct rte_bitmap *bmp, uint32_t offset,
+			    uint32_t *pos, uint64_t *slab)
+{
+	__rte_bitmap_scan_init_at(bmp, offset);
+	return rte_bitmap_scan(bmp, pos, slab);
+}
+
 #ifdef __cplusplus
 }
 #endif
-- 
2.34.1

RE: [PATCH v4] bitmap: add scan from offset function

[Dumitrescu, Cristian]

> -----Original Message-----
> From: Volodymyr Fialko <vfialko@marvell.com>
> Sent: Monday, July 3, 2023 10:31 AM
> To: dev@dpdk.org; Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> Cc: jerinj@marvell.com; anoobj@marvell.com; thomas@monjalon.net;
> Volodymyr Fialko <vfialko@marvell.com>
> Subject: [PATCH v4] bitmap: add scan from offset function
> 
> Currently, in the case when we search for a bit set after a particular
> value, the bitmap has to be scanned from the beginning and
> rte_bitmap_scan() has to be called multiple times until we hit the value.
> 
> Add a new rte_bitmap_scan_from_offset() function to initialize scan
> state at the given offset and perform scan, this will allow getting
> the next set bit after certain offset within one scan call.
> 
> Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
> ---
> v2:
>  - added rte_bitmap_scan_from_offset
> v3:
>  - added note for internal use only for init_at function
> v4:
>  - marked init_at function as __rte_internal
> 
>  app/test/test_bitmap.c       | 33 ++++++++++++++++++++-
>  lib/eal/include/rte_bitmap.h | 56 

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

[PATCH v5] bitmap: add scan from offset function

[Volodymyr Fialko]

Currently, in the case when we search for a bit set after a particular
value, the bitmap has to be scanned from the beginning and
rte_bitmap_scan() has to be called multiple times until we hit the value.

Add a new rte_bitmap_scan_from_offset() function to initialize scan
state at the given offset and perform scan, this will allow getting
the next set bit after certain offset within one scan call.

Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
---
v2:
 - added rte_bitmap_scan_from_offset
v3:
 - added note for internal use only for init_at function
v4:
 - marked init_at function as __rte_internal
v5:
 - removed __rte_internal due to build errors

 app/test/test_bitmap.c       | 33 +++++++++++++++++++++-
 lib/eal/include/rte_bitmap.h | 55 ++++++++++++++++++++++++++++++++++++
 2 files changed, 87 insertions(+), 1 deletion(-)

diff --git a/app/test/test_bitmap.c b/app/test/test_bitmap.c
index e9c61590ae..9e38087408 100644
--- a/app/test/test_bitmap.c
+++ b/app/test/test_bitmap.c
@@ -18,8 +18,8 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp)
 {
 	uint64_t slab1_magic = 0xBADC0FFEEBADF00D;
 	uint64_t slab2_magic = 0xFEEDDEADDEADF00D;
+	int i, nb_clear, nb_set, next_cl;
 	uint32_t pos = 0, start_pos;
-	int i, nb_clear, nb_set;
 	uint64_t out_slab = 0;
 
 	rte_bitmap_reset(bmp);
@@ -71,6 +71,37 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp)
 		return TEST_FAILED;
 	}
 
+	/* Scan with offset check. */
+	if (!rte_bitmap_scan_from_offset(bmp, RTE_BITMAP_SLAB_BIT_SIZE, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap with scan from offset.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab2_magic != out_slab) {
+		printf("Scan from offset operation failed.\n");
+		return TEST_FAILED;
+	}
+
+	/* Scan with offset wrap around check. */
+	if (!rte_bitmap_scan_from_offset(bmp, 2 * RTE_BITMAP_SLAB_BIT_SIZE, &pos, &out_slab)) {
+		printf("Failed to get slab from bitmap with scan from offset.\n");
+		return TEST_FAILED;
+	}
+
+	if (slab1_magic != out_slab) {
+		printf("Scan from offset with wrap around operation failed.\n");
+		return TEST_FAILED;
+	}
+
+	/* Test scan when the bit set is on a next cline */
+	rte_bitmap_reset(bmp);
+	next_cl = RTE_MIN(RTE_BITMAP_CL_BIT_SIZE, MAX_BITS);
+	rte_bitmap_set(bmp, next_cl);
+	if (!rte_bitmap_scan_from_offset(bmp, 0, &pos, &out_slab)) {
+		printf("Failed to get slab from next cache line from bitmap.\n");
+		return TEST_FAILED;
+	}
+
 	/* Test scan when a cline is half full */
 	rte_bitmap_reset(bmp);
 	for (i = 0; i < MAX_BITS; i++)
diff --git a/lib/eal/include/rte_bitmap.h b/lib/eal/include/rte_bitmap.h
index 27ee3d18a4..cc14b1ed2e 100644
--- a/lib/eal/include/rte_bitmap.h
+++ b/lib/eal/include/rte_bitmap.h
@@ -137,6 +137,29 @@ __rte_bitmap_scan_init(struct rte_bitmap *bmp)
 	bmp->go2 = 0;
 }
 
+/**
+ * Bitmap initialize internal scan pointers at the given position for the scan function.
+ *
+ * Note: for private/internal use, for public:
+ * @see rte_bitmap_scan_from_offset()
+ *
+ * @param bmp
+ *   Handle to bitmap instance
+ * @param pos
+ *   Bit position to start scan
+ */
+static inline void
+__rte_bitmap_scan_init_at(struct rte_bitmap *bmp, uint32_t pos)
+{
+	uint64_t *slab1;
+
+	bmp->index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
+	bmp->offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
+	bmp->index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
+	slab1 = bmp->array1 + bmp->index1;
+	bmp->go2 = *slab1 & (1llu << bmp->offset1);
+}
+
 /**
  * Bitmap memory footprint calculation
  *
@@ -591,6 +614,38 @@ rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)
 	return 0;
 }
 
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Bitmap scan from the given offset.
+ * Function will reset internal scan state to start scanning from the offset
+ * position.
+ * @see rte_bitmap_scan()
+ *
+ * @param bmp
+ *   Handle to bitmap instance
+ * @param offset
+ *   Bit offset to start scan
+ * @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.
+ *   When function call returns 0, slab is not modified.
+ * @return
+ *   0 if there is no bit set in the bitmap, 1 otherwise
+ */
+__rte_experimental
+static inline int
+rte_bitmap_scan_from_offset(struct rte_bitmap *bmp, uint32_t offset,
+			    uint32_t *pos, uint64_t *slab)
+{
+	__rte_bitmap_scan_init_at(bmp, offset);
+	return rte_bitmap_scan(bmp, pos, slab);
+}
+
 #ifdef __cplusplus
 }
 #endif
-- 
2.34.1

RE: [PATCH v5] bitmap: add scan from offset function

[Dumitrescu, Cristian]

> -----Original Message-----
> From: Volodymyr Fialko <vfialko@marvell.com>
> Sent: Monday, July 3, 2023 1:39 PM
> To: dev@dpdk.org; Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> Cc: jerinj@marvell.com; anoobj@marvell.com; thomas@monjalon.net;
> Volodymyr Fialko <vfialko@marvell.com>
> Subject: [PATCH v5] bitmap: add scan from offset function
> 
> Currently, in the case when we search for a bit set after a particular
> value, the bitmap has to be scanned from the beginning and
> rte_bitmap_scan() has to be called multiple times until we hit the value.
> 
> Add a new rte_bitmap_scan_from_offset() function to initialize scan
> state at the given offset and perform scan, this will allow getting
> the next set bit after certain offset within one scan call.
> 
> Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
> ---

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

RE: [PATCH v5] bitmap: add scan from offset function

[Volodymyr Fialko]

Hi Thomas,

Is there any remaining work for this patch, or is it ready to be merged?

/Volodymyr

Re: [PATCH v5] bitmap: add scan from offset function

[Thomas Monjalon]

03/07/2023 14:39, Volodymyr Fialko:
> Currently, in the case when we search for a bit set after a particular
> value, the bitmap has to be scanned from the beginning and
> rte_bitmap_scan() has to be called multiple times until we hit the value.
> 
> Add a new rte_bitmap_scan_from_offset() function to initialize scan
> state at the given offset and perform scan, this will allow getting
> the next set bit after certain offset within one scan call.
> 
> Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
> ---
> v2:
>  - added rte_bitmap_scan_from_offset
> v3:
>  - added note for internal use only for init_at function
> v4:
>  - marked init_at function as __rte_internal
> v5:
>  - removed __rte_internal due to build errors

What was the build error?

You should not add an internal function in the public header file.
At least, it should be experimental.


> --- a/lib/eal/include/rte_bitmap.h
> +++ b/lib/eal/include/rte_bitmap.h
> +/**
> + * Bitmap initialize internal scan pointers at the given position for the scan function.
> + *
> + * Note: for private/internal use, for public:
> + * @see rte_bitmap_scan_from_offset()
> + *
> + * @param bmp
> + *   Handle to bitmap instance
> + * @param pos
> + *   Bit position to start scan
> + */
> +static inline void
> +__rte_bitmap_scan_init_at(struct rte_bitmap *bmp, uint32_t pos)
> +{
> +	uint64_t *slab1;
> +
> +	bmp->index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2);
> +	bmp->offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK;
> +	bmp->index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
> +	slab1 = bmp->array1 + bmp->index1;
> +	bmp->go2 = *slab1 & (1llu << bmp->offset1);
> +}

Re: [PATCH v5] bitmap: add scan from offset function

[Volodymyr Fialko]

> From: Thomas Monjalon <thomas@monjalon.net>
> Sent: Wednesday, July 3, 2024 2:50 PM
> To: Volodymyr Fialko
> Cc: dev@dpdk.org; cristian.dumitrescu@intel.com; Jerin Jacob; Anoob Joseph
> Subject: Re: [PATCH v5] bitmap: add scan from offset function
>
> 03/07/2023 14:39, Volodymyr Fialko:
> > Currently, in the case when we search for a bit set after a particular
> > value, the bitmap has to be scanned from the beginning and
> > rte_bitmap_scan() has to be called multiple times until we hit the value.
> >
> > Add a new rte_bitmap_scan_from_offset() function to initialize scan
> > state at the given offset and perform scan, this will allow getting
> > the next set bit after certain offset within one scan call.
> >
> > Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
> > ---
> > v2:
> >  - added rte_bitmap_scan_from_offset
> > v3:
> >  - added note for internal use only for init_at function
> > v4:
> >  - marked init_at function as __rte_internal
> > v5:
> >  - removed __rte_internal due to build errors
> 
> What was the build error?
> 
> You should not add an internal function in the public header file.
> At least, it should be experimental.
> 

From our discussion in previous versions(V3, V4), It looks like we agreed to
remove both markers.

> From: Thomas Monjalon <thomas@monjalon.net>
> Sent: Monday, July 3, 2023 2:17 PM
> To: Dumitrescu, Cristian; Volodymyr Fialko
> Cc: dev@dpdk.org; Jerin Jacob Kollanukkaran; Anoob Joseph
> Subject: Re: [PATCH v3] bitmap: add scan from offset function
> 
> > ----------------------------------------------------------------------
> > 03/07/2023 12:56, Volodymyr Fialko:
> > > Since it's header-only library, there is issue with using __rte_intenal (appeared in v4).
> > 
> > What is the issue?
> 
> From V4 ci build failure(http://mails.dpdk.org/archives/test-report/2023-July/421235.html):
> 	In file included from ../examples/ipsec-secgw/event_helper.c:6:
> 	../lib/eal/include/rte_bitmap.h:645:2: error: Symbol is not public ABI
> 	        __rte_bitmap_scan_init_at(bmp, offset);
>  	       ^
> 	../lib/eal/include/rte_bitmap.h:150:1: note: from 'diagnose_if' attribute on '__rte_bitmap_scan_init_at':
> 	__rte_internal
> 	^~~~~~~~~~~~~~
> 	../lib/eal/include/rte_compat.h:42:16: note: expanded from macro '__rte_internal'	
> 	__attribute__((diagnose_if(1, "Symbol is not public ABI", "error"), \
>               		^           ~
> 	1 error generated.

> OK I see.
> So we should give up with __rte_internal for inline functions.
> As it is not supposed to be exposed to the applications,
> I think we can skip the __rte_experimental flag.

/Volodymyr

Re: [PATCH v5] bitmap: add scan from offset function

[Thomas Monjalon]

03/07/2024 15:42, Volodymyr Fialko:
> > From: Thomas Monjalon <thomas@monjalon.net>
> > Sent: Wednesday, July 3, 2024 2:50 PM
> > To: Volodymyr Fialko
> > Cc: dev@dpdk.org; cristian.dumitrescu@intel.com; Jerin Jacob; Anoob Joseph
> > Subject: Re: [PATCH v5] bitmap: add scan from offset function
> >
> > 03/07/2023 14:39, Volodymyr Fialko:
> > > Currently, in the case when we search for a bit set after a particular
> > > value, the bitmap has to be scanned from the beginning and
> > > rte_bitmap_scan() has to be called multiple times until we hit the value.
> > >
> > > Add a new rte_bitmap_scan_from_offset() function to initialize scan
> > > state at the given offset and perform scan, this will allow getting
> > > the next set bit after certain offset within one scan call.
> > >
> > > Signed-off-by: Volodymyr Fialko <vfialko@marvell.com>
> > > ---
> > > v2:
> > >  - added rte_bitmap_scan_from_offset
> > > v3:
> > >  - added note for internal use only for init_at function
> > > v4:
> > >  - marked init_at function as __rte_internal
> > > v5:
> > >  - removed __rte_internal due to build errors
> > 
> > What was the build error?
> > 
> > You should not add an internal function in the public header file.
> > At least, it should be experimental.
> > 
> 
> From our discussion in previous versions(V3, V4), It looks like we agreed to
> remove both markers.

Indeed, sorry I forgot this discussion.

Re: [PATCH v5] bitmap: add scan from offset function

[Stephen Hemminger]

On Mon, 3 Jul 2023 14:39:08 +0200
Volodymyr Fialko <vfialko@marvell.com> wrote:

> +/**
> + * Bitmap initialize internal scan pointers at the given position for the scan function.
> + *
> + * Note: for private/internal use, for public:
> + * @see rte_bitmap_scan_from_offset()
> + *
> + * @param bmp
> + *   Handle to bitmap instance
> + * @param pos
> + *   Bit position to start scan
> + */
> +static inline void
> +__rte_bitmap_scan_init_at(struct rte_bitmap *bmp, uint32_t pos)
> +{
> +	uint64_t *slab1;

Since this exposed in a header file, needs to be internal or experimental.

RE: [EXTERNAL] Re: [PATCH v5] bitmap: add scan from offset function

[Volodymyr Fialko]

[-- Attachment #1: Type: text/plain, Size: 3241 bytes --]

From discussion with Thomas in previous versions of this patch, we agreed to omit both markers.

> From: Thomas Monjalon <thomas@monjalon.net<mailto:thomas@monjalon.net>>

> Sent: Monday, July 3, 2023 2:17 PM

> To: Dumitrescu, Cristian; Volodymyr Fialko

> Cc: dev@dpdk.org<mailto:dev@dpdk.org>; Jerin Jacob Kollanukkaran; Anoob Joseph

> Subject: Re: [PATCH v3] bitmap: add scan from offset function

>

> > --------------------------------------------------------------------

> > --

> > 03/07/2023 12:56, Volodymyr Fialko:

> > > Since it's header-only library, there is issue with using __rte_intenal (appeared in v4).
> > > Even if the function itself is not used directly, it get's included to the other public files.
> > > It explains why other functions in this library does not have the rte_internal prefix, but the double underscores.

> >

> > What is the issue?

>

> From V4 ci build failure(http://mails.dpdk.org/archives/test-report/2023-July/421235.html):

>             In file included from ../examples/ipsec-secgw/event_helper.c:6:

>             ../lib/eal/include/rte_bitmap.h:645:2: error: Symbol is not public ABI

>                     __rte_bitmap_scan_init_at(bmp, offset);

>                    ^

>             ../lib/eal/include/rte_bitmap.h:150:1: note: from 'diagnose_if' attribute on '__rte_bitmap_scan_init_at':

>             __rte_internal

>             ^~~~~~~~~~~~~~

>             ../lib/eal/include/rte_compat.h:42:16: note: expanded from macro '__rte_internal'

>             __attribute__((diagnose_if(1, "Symbol is not public ABI", "error"), \

>                                          ^           ~

>             1 error generated.



> OK I see.

> So we should give up with __rte_internal for inline functions.

> As it is not supposed to be exposed to the applications, I think we
> can skip the __rte_experimental flag.


/Volodymyr

From: Stephen Hemminger <stephen@networkplumber.org>
Sent: Friday, October 4, 2024 5:04 AM
To: Volodymyr Fialko <vfialko@marvell.com>
Cc: dev@dpdk.org; cristian.dumitrescu@intel.com; Jerin Jacob <jerinj@marvell.com>; Anoob Joseph <anoobj@marvell.com>; thomas@monjalon.net
Subject: [EXTERNAL] Re: [PATCH v5] bitmap: add scan from offset function
Mon, 3 Jul 2023 14: 39: 08 +0200 Volodymyr Fialko <vfialko@ marvell. com> wrote: > +/** > + * Bitmap initialize internal scan pointers at the given position for the scan function. > + * > + * Note: for private/internal use,
ZjQcmQRYFpfptBannerStart
  On Mon, 3 Jul 2023 14:39:08 +0200

Volodymyr Fialko <vfialko@marvell.com<mailto:vfialko@marvell.com>> wrote:



> +/**

> + * Bitmap initialize internal scan pointers at the given position for the scan function.

> + *

> + * Note: for private/internal use, for public:

> + * @see rte_bitmap_scan_from_offset()

> + *

> + * @param bmp

> + *   Handle to bitmap instance

> + * @param pos

> + *   Bit position to start scan

> + */

> +static inline void

> +__rte_bitmap_scan_init_at(struct rte_bitmap *bmp, uint32_t pos)

> +{

> +        uint64_t *slab1;



Since this exposed in a header file, needs to be internal or experimental.

[-- Attachment #2: Type: text/html, Size: 14628 bytes --]