bitmap: add scan init at given position
Checks
Commit Message
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(+)
Comments
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.
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
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
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.
@@ -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++)
@@ -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
*