[v5] bitmap: add scan from offset function
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_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(-)
Comments
> -----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>
Hi Thomas,
Is there any remaining work for this patch, or is it ready to be merged?
/Volodymyr
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);
> +}
> 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
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.
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.
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.
@@ -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++)
@@ -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