[v2,1/2] bitmap: add create bitmap with all bits set
Checks
Commit Message
Currently, in the case to use bitmap as resource allocator, after
bitmap creation, all the bitmap bits should be set to indicate the
bit available. Every time when allocate one bit, search for the set
bits and clear it to make it in use.
Add a new rte_bitmap_init_with_all_set() function to have a quick
fill up the bitmap bits.
Comparing with the case create the bitmap as empty and set the bitmap
one by one, the new function costs less cycles.
Signed-off-by: Suanming Mou <suanmingm@mellanox.com>
---
lib/librte_eal/common/include/rte_bitmap.h | 113 ++++++++++++++++++++++-------
1 file changed, 85 insertions(+), 28 deletions(-)
Comments
Hi Sunaming,
> -----Original Message-----
> From: Suanming Mou <suanmingm@mellanox.com>
> Sent: Wednesday, April 8, 2020 4:06 AM
> To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> Cc: dev@dpdk.org; amo@semihalf.com
> Subject: [PATCH v2 1/2] bitmap: add create bitmap with all bits set
>
> Currently, in the case to use bitmap as resource allocator, after
> bitmap creation, all the bitmap bits should be set to indicate the
> bit available. Every time when allocate one bit, search for the set
> bits and clear it to make it in use.
>
> Add a new rte_bitmap_init_with_all_set() function to have a quick
> fill up the bitmap bits.
>
> Comparing with the case create the bitmap as empty and set the bitmap
> one by one, the new function costs less cycles.
>
> Signed-off-by: Suanming Mou <suanmingm@mellanox.com>
> ---
> lib/librte_eal/common/include/rte_bitmap.h | 113
> ++++++++++++++++++++++-------
> 1 file changed, 85 insertions(+), 28 deletions(-)
>
> diff --git a/lib/librte_eal/common/include/rte_bitmap.h
> b/lib/librte_eal/common/include/rte_bitmap.h
> index 6b846f2..740076b 100644
> --- a/lib/librte_eal/common/include/rte_bitmap.h
> +++ b/lib/librte_eal/common/include/rte_bitmap.h
> @@ -136,6 +136,40 @@ struct rte_bitmap {
> bmp->go2 = 0;
> }
>
> +static inline struct rte_bitmap *
> +__rte_bitmap_init(uint32_t n_bits, uint8_t *mem, uint32_t mem_size)
> +{
> + struct rte_bitmap *bmp;
> + uint32_t array1_byte_offset, array1_slabs;
> + uint32_t array2_byte_offset, array2_slabs;
> + uint32_t size;
> +
> + /* Check input arguments */
> + if (n_bits == 0)
> + return NULL;
> +
> + if ((mem == NULL) || (((uintptr_t) mem) &
> RTE_CACHE_LINE_MASK))
> + return NULL;
> +
> + size = __rte_bitmap_get_memory_footprint(n_bits,
> + &array1_byte_offset, &array1_slabs,
> + &array2_byte_offset, &array2_slabs);
> + if (size < mem_size)
> + return NULL;
> +
> + /* Setup bitmap */
> + bmp = (struct rte_bitmap *) mem;
> +
> + bmp->array1 = (uint64_t *) &mem[array1_byte_offset];
> + bmp->array1_size = array1_slabs;
> + bmp->array2 = (uint64_t *) &mem[array2_byte_offset];
> + bmp->array2_size = array2_slabs;
> +
> + __rte_bitmap_scan_init(bmp);
> +
> + return bmp;
> +}
> +
> /**
> * Bitmap memory footprint calculation
> *
> @@ -170,36 +204,12 @@ struct rte_bitmap {
> rte_bitmap_init(uint32_t n_bits, uint8_t *mem, uint32_t mem_size)
> {
> struct rte_bitmap *bmp;
> - uint32_t array1_byte_offset, array1_slabs, array2_byte_offset,
> array2_slabs;
> - uint32_t size;
>
> - /* Check input arguments */
> - if (n_bits == 0) {
> - return NULL;
> - }
> -
> - if ((mem == NULL) || (((uintptr_t) mem) &
> RTE_CACHE_LINE_MASK)) {
> - return NULL;
> - }
> -
> - size = __rte_bitmap_get_memory_footprint(n_bits,
> - &array1_byte_offset, &array1_slabs,
> - &array2_byte_offset, &array2_slabs);
> - if (size < mem_size) {
> + bmp = __rte_bitmap_init(n_bits, mem, mem_size);
> + if (!bmp)
> return NULL;
> - }
> -
> - /* Setup bitmap */
> - memset(mem, 0, size);
> - bmp = (struct rte_bitmap *) mem;
> -
> - bmp->array1 = (uint64_t *) &mem[array1_byte_offset];
> - bmp->array1_size = array1_slabs;
> - bmp->array2 = (uint64_t *) &mem[array2_byte_offset];
> - bmp->array2_size = array2_slabs;
> -
> - __rte_bitmap_scan_init(bmp);
> -
> + memset(bmp->array1, 0, bmp->array1_size * sizeof(uint64_t));
> + memset(bmp->array2, 0, bmp->array2_size * sizeof(uint64_t));
> return bmp;
> }
>
Can we please leave the function rte_bitmap_init() unmodified and put all changes in the new function rte_bitmap_init_with_all_set(). I realize this means duplicating a few lines of code between the two init functions, but IMO easier to maintain going forward.
> @@ -483,6 +493,53 @@ struct rte_bitmap {
> return 0;
> }
>
> +/**
> + * Bitmap initialization with all bits set
> + *
> + * @param n_bits
> + * Number of pre-allocated bits in array2.
> + * @param mem
> + * Base address of array1 and array2.
> + * @param mem_size
> + * Minimum expected size of bitmap.
> + * @return
> + * Handle to bitmap instance.
> + */
> +static inline struct rte_bitmap *
> +rte_bitmap_init_with_all_set(uint32_t n_bits, uint8_t *mem, uint32_t
> mem_size)
> +{
> + uint32_t i;
> + uint32_t slabs, array1_bits;
> + struct rte_bitmap *bmp;
> +
> + bmp = __rte_bitmap_init(n_bits, mem, mem_size);
> + if (!bmp)
> + return NULL;
> +
> + array1_bits = bmp->array2_size >>
> RTE_BITMAP_CL_SLAB_SIZE_LOG2;
> + /* Fill the arry1 slab aligned bits. */
> + slabs = array1_bits >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
> + memset(bmp->array1, 0xff, slabs * sizeof(bmp->array1[0]));
> + /* Clear the array1 left slabs. */
> + memset(&bmp->array1[slabs], 0, (bmp->array1_size - slabs) *
> + sizeof(bmp->array1[0]));
> + /* Fill the array1 middle not full set slab. */
> + for (i = 0; i < (array1_bits & RTE_BITMAP_SLAB_BIT_MASK); i++)
> + bmp->array1[slabs] |= 1llu << i;
> +
> + /* Fill the arry2 slab aligned bits. */
> + slabs = n_bits >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
> + memset(bmp->array2, 0xff, slabs * sizeof(bmp->array2[0]));
> + /* Clear the array2 left slabs. */
> + memset(&bmp->array2[slabs], 0, (bmp->array2_size - slabs) *
> + sizeof(bmp->array2[0]));
> + /* Fill the array2 middle not full set slab. */
> + for (i = 0; i < (n_bits & RTE_BITMAP_SLAB_BIT_MASK); i++)
> + bmp->array2[slabs] |= 1llu << i;
> +
> + return bmp;
> +}
> +
> #ifdef __cplusplus
> }
> #endif
> --
> 1.8.3.1
This code is not that easy to read. This function is tricky to implement, as we basically need to correct some overhead bits in array1 and array2.
What I suggest for the layout of this function:
-call essentially the same code as rte_bitmap_init(), with the change that we set ALL the bits in array1 and array2 to 1 instead of 0
-call a new helper function to correct (set to 0) all the array2 bits from position (index2, offset2) to the end
-call a new helper function to correct (set to 0) all the array1 bits from position (index1, offset1) to the end
What do you think?
Thanks,
Cristian
> -----Original Message-----
> From: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> Sent: Thursday, April 9, 2020 10:16 PM
> To: Suanming Mou <suanmingm@mellanox.com>
> Cc: dev@dpdk.org; amo@semihalf.com
> Subject: RE: [PATCH v2 1/2] bitmap: add create bitmap with all bits set
>
> Hi Sunaming,
>
> > -----Original Message-----
> > From: Suanming Mou <suanmingm@mellanox.com>
> > Sent: Wednesday, April 8, 2020 4:06 AM
> > To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> > Cc: dev@dpdk.org; amo@semihalf.com
> > Subject: [PATCH v2 1/2] bitmap: add create bitmap with all bits set
> >
> > Currently, in the case to use bitmap as resource allocator, after
> > bitmap creation, all the bitmap bits should be set to indicate the bit
> > available. Every time when allocate one bit, search for the set bits
> > and clear it to make it in use.
> >
> > Add a new rte_bitmap_init_with_all_set() function to have a quick fill
> > up the bitmap bits.
> >
> > Comparing with the case create the bitmap as empty and set the bitmap
> > one by one, the new function costs less cycles.
> >
> > Signed-off-by: Suanming Mou <suanmingm@mellanox.com>
> > ---
> > lib/librte_eal/common/include/rte_bitmap.h | 113
> > ++++++++++++++++++++++-------
> > 1 file changed, 85 insertions(+), 28 deletions(-)
> >
> > diff --git a/lib/librte_eal/common/include/rte_bitmap.h
> > b/lib/librte_eal/common/include/rte_bitmap.h
> > index 6b846f2..740076b 100644
> > --- a/lib/librte_eal/common/include/rte_bitmap.h
> > +++ b/lib/librte_eal/common/include/rte_bitmap.h
> > @@ -136,6 +136,40 @@ struct rte_bitmap {
> > bmp->go2 = 0;
> > }
> >
> > +static inline struct rte_bitmap *
> > +__rte_bitmap_init(uint32_t n_bits, uint8_t *mem, uint32_t mem_size) {
> > + struct rte_bitmap *bmp;
> > + uint32_t array1_byte_offset, array1_slabs;
> > + uint32_t array2_byte_offset, array2_slabs;
> > + uint32_t size;
> > +
> > + /* Check input arguments */
> > + if (n_bits == 0)
> > + return NULL;
> > +
> > + if ((mem == NULL) || (((uintptr_t) mem) &
> > RTE_CACHE_LINE_MASK))
> > + return NULL;
> > +
> > + size = __rte_bitmap_get_memory_footprint(n_bits,
> > + &array1_byte_offset, &array1_slabs,
> > + &array2_byte_offset, &array2_slabs);
> > + if (size < mem_size)
> > + return NULL;
> > +
> > + /* Setup bitmap */
> > + bmp = (struct rte_bitmap *) mem;
> > +
> > + bmp->array1 = (uint64_t *) &mem[array1_byte_offset];
> > + bmp->array1_size = array1_slabs;
> > + bmp->array2 = (uint64_t *) &mem[array2_byte_offset];
> > + bmp->array2_size = array2_slabs;
> > +
> > + __rte_bitmap_scan_init(bmp);
> > +
> > + return bmp;
> > +}
> > +
> > /**
> > * Bitmap memory footprint calculation
> > *
> > @@ -170,36 +204,12 @@ struct rte_bitmap { rte_bitmap_init(uint32_t
> > n_bits, uint8_t *mem, uint32_t mem_size) {
> > struct rte_bitmap *bmp;
> > - uint32_t array1_byte_offset, array1_slabs, array2_byte_offset,
> > array2_slabs;
> > - uint32_t size;
> >
> > - /* Check input arguments */
> > - if (n_bits == 0) {
> > - return NULL;
> > - }
> > -
> > - if ((mem == NULL) || (((uintptr_t) mem) &
> > RTE_CACHE_LINE_MASK)) {
> > - return NULL;
> > - }
> > -
> > - size = __rte_bitmap_get_memory_footprint(n_bits,
> > - &array1_byte_offset, &array1_slabs,
> > - &array2_byte_offset, &array2_slabs);
> > - if (size < mem_size) {
> > + bmp = __rte_bitmap_init(n_bits, mem, mem_size);
> > + if (!bmp)
> > return NULL;
> > - }
> > -
> > - /* Setup bitmap */
> > - memset(mem, 0, size);
> > - bmp = (struct rte_bitmap *) mem;
> > -
> > - bmp->array1 = (uint64_t *) &mem[array1_byte_offset];
> > - bmp->array1_size = array1_slabs;
> > - bmp->array2 = (uint64_t *) &mem[array2_byte_offset];
> > - bmp->array2_size = array2_slabs;
> > -
> > - __rte_bitmap_scan_init(bmp);
> > -
> > + memset(bmp->array1, 0, bmp->array1_size * sizeof(uint64_t));
> > + memset(bmp->array2, 0, bmp->array2_size * sizeof(uint64_t));
> > return bmp;
> > }
> >
>
> Can we please leave the function rte_bitmap_init() unmodified and put all
> changes in the new function rte_bitmap_init_with_all_set(). I realize this means
> duplicating a few lines of code between the two init functions, but IMO easier to
> maintain going forward.
Sure. Agree with that, so let's keep the rte_bitmap_init() unmodified.
>
> > @@ -483,6 +493,53 @@ struct rte_bitmap {
> > return 0;
> > }
> >
> > +/**
> > + * Bitmap initialization with all bits set
> > + *
> > + * @param n_bits
> > + * Number of pre-allocated bits in array2.
> > + * @param mem
> > + * Base address of array1 and array2.
> > + * @param mem_size
> > + * Minimum expected size of bitmap.
> > + * @return
> > + * Handle to bitmap instance.
> > + */
> > +static inline struct rte_bitmap *
> > +rte_bitmap_init_with_all_set(uint32_t n_bits, uint8_t *mem, uint32_t
> > mem_size)
> > +{
> > + uint32_t i;
> > + uint32_t slabs, array1_bits;
> > + struct rte_bitmap *bmp;
> > +
> > + bmp = __rte_bitmap_init(n_bits, mem, mem_size);
> > + if (!bmp)
> > + return NULL;
> > +
> > + array1_bits = bmp->array2_size >>
> > RTE_BITMAP_CL_SLAB_SIZE_LOG2;
> > + /* Fill the arry1 slab aligned bits. */
> > + slabs = array1_bits >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
> > + memset(bmp->array1, 0xff, slabs * sizeof(bmp->array1[0]));
> > + /* Clear the array1 left slabs. */
> > + memset(&bmp->array1[slabs], 0, (bmp->array1_size - slabs) *
> > + sizeof(bmp->array1[0]));
> > + /* Fill the array1 middle not full set slab. */
> > + for (i = 0; i < (array1_bits & RTE_BITMAP_SLAB_BIT_MASK); i++)
> > + bmp->array1[slabs] |= 1llu << i;
> > +
> > + /* Fill the arry2 slab aligned bits. */
> > + slabs = n_bits >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
> > + memset(bmp->array2, 0xff, slabs * sizeof(bmp->array2[0]));
> > + /* Clear the array2 left slabs. */
> > + memset(&bmp->array2[slabs], 0, (bmp->array2_size - slabs) *
> > + sizeof(bmp->array2[0]));
> > + /* Fill the array2 middle not full set slab. */
> > + for (i = 0; i < (n_bits & RTE_BITMAP_SLAB_BIT_MASK); i++)
> > + bmp->array2[slabs] |= 1llu << i;
> > +
> > + return bmp;
> > +}
> > +
> > #ifdef __cplusplus
> > }
> > #endif
> > --
> > 1.8.3.1
>
> This code is not that easy to read. This function is tricky to implement, as we
> basically need to correct some overhead bits in array1 and array2.
>
> What I suggest for the layout of this function:
> -call essentially the same code as rte_bitmap_init(), with the change that we set
> ALL the bits in array1 and array2 to 1 instead of 0 -call a new helper function to
> correct (set to 0) all the array2 bits from position (index2, offset2) to the end -
> call a new helper function to correct (set to 0) all the array1 bits from position
> (index1, offset1) to the end
Good suggestion.
What about the function below, it will help both arry1 and array2 clear the not needed bits:
/**
* Bitmap clear slab overhead bits.
*
* @param slab
* Slab arrary.
* @param size
* Slab array size.
* @param pos
* The start bit position in the slabs to be cleared.
*/
static inline void
__rte_bitmap_clear_slab_overhead_bits(uint64_t *slabs, uint32_t slab_size,
uint32_t pos)
{
uint32_t i;
uint32_t index = pos / RTE_BITMAP_SLAB_BIT_SIZE;
uint32_t offset = pos & RTE_BITMAP_SLAB_BIT_MASK;
if (offset) {
for (i = offset; i < RTE_BITMAP_SLAB_BIT_SIZE; i++)
slabs[index] &= ~(1llu << i);
index++;
}
if (index < slab_size)
memset(&slabs[index], 0, sizeof(slabs[0]) *
(slab_size - index));
}
It seems that is a bit difficult to find a none tricky way to clear the bits.
>
> What do you think?
>
> Thanks,
> Cristian
> -----Original Message-----
> From: Suanming Mou <suanmingm@mellanox.com>
> Sent: Friday, April 10, 2020 11:34 AM
> To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> Cc: dev@dpdk.org; amo@semihalf.com
> Subject: RE: [PATCH v2 1/2] bitmap: add create bitmap with all bits set
>
>
>
> > -----Original Message-----
> > From: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> > Sent: Thursday, April 9, 2020 10:16 PM
> > To: Suanming Mou <suanmingm@mellanox.com>
> > Cc: dev@dpdk.org; amo@semihalf.com
> > Subject: RE: [PATCH v2 1/2] bitmap: add create bitmap with all bits set
> >
> > Hi Sunaming,
> >
> > > -----Original Message-----
> > > From: Suanming Mou <suanmingm@mellanox.com>
> > > Sent: Wednesday, April 8, 2020 4:06 AM
> > > To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> > > Cc: dev@dpdk.org; amo@semihalf.com
> > > Subject: [PATCH v2 1/2] bitmap: add create bitmap with all bits set
> > >
> > > Currently, in the case to use bitmap as resource allocator, after
> > > bitmap creation, all the bitmap bits should be set to indicate the bit
> > > available. Every time when allocate one bit, search for the set bits
> > > and clear it to make it in use.
> > >
> > > Add a new rte_bitmap_init_with_all_set() function to have a quick fill
> > > up the bitmap bits.
> > >
> > > Comparing with the case create the bitmap as empty and set the bitmap
> > > one by one, the new function costs less cycles.
> > >
> > > Signed-off-by: Suanming Mou <suanmingm@mellanox.com>
> > > ---
> > > lib/librte_eal/common/include/rte_bitmap.h | 113
> > > ++++++++++++++++++++++-------
> > > 1 file changed, 85 insertions(+), 28 deletions(-)
> > >
> > > diff --git a/lib/librte_eal/common/include/rte_bitmap.h
> > > b/lib/librte_eal/common/include/rte_bitmap.h
> > > index 6b846f2..740076b 100644
> > > --- a/lib/librte_eal/common/include/rte_bitmap.h
> > > +++ b/lib/librte_eal/common/include/rte_bitmap.h
> > > @@ -136,6 +136,40 @@ struct rte_bitmap {
> > > bmp->go2 = 0;
> > > }
> > >
> > > +static inline struct rte_bitmap *
> > > +__rte_bitmap_init(uint32_t n_bits, uint8_t *mem, uint32_t mem_size) {
> > > + struct rte_bitmap *bmp;
> > > + uint32_t array1_byte_offset, array1_slabs;
> > > + uint32_t array2_byte_offset, array2_slabs;
> > > + uint32_t size;
> > > +
> > > + /* Check input arguments */
> > > + if (n_bits == 0)
> > > + return NULL;
> > > +
> > > + if ((mem == NULL) || (((uintptr_t) mem) &
> > > RTE_CACHE_LINE_MASK))
> > > + return NULL;
> > > +
> > > + size = __rte_bitmap_get_memory_footprint(n_bits,
> > > + &array1_byte_offset, &array1_slabs,
> > > + &array2_byte_offset, &array2_slabs);
> > > + if (size < mem_size)
> > > + return NULL;
> > > +
> > > + /* Setup bitmap */
> > > + bmp = (struct rte_bitmap *) mem;
> > > +
> > > + bmp->array1 = (uint64_t *) &mem[array1_byte_offset];
> > > + bmp->array1_size = array1_slabs;
> > > + bmp->array2 = (uint64_t *) &mem[array2_byte_offset];
> > > + bmp->array2_size = array2_slabs;
> > > +
> > > + __rte_bitmap_scan_init(bmp);
> > > +
> > > + return bmp;
> > > +}
> > > +
> > > /**
> > > * Bitmap memory footprint calculation
> > > *
> > > @@ -170,36 +204,12 @@ struct rte_bitmap { rte_bitmap_init(uint32_t
> > > n_bits, uint8_t *mem, uint32_t mem_size) {
> > > struct rte_bitmap *bmp;
> > > - uint32_t array1_byte_offset, array1_slabs, array2_byte_offset,
> > > array2_slabs;
> > > - uint32_t size;
> > >
> > > - /* Check input arguments */
> > > - if (n_bits == 0) {
> > > - return NULL;
> > > - }
> > > -
> > > - if ((mem == NULL) || (((uintptr_t) mem) &
> > > RTE_CACHE_LINE_MASK)) {
> > > - return NULL;
> > > - }
> > > -
> > > - size = __rte_bitmap_get_memory_footprint(n_bits,
> > > - &array1_byte_offset, &array1_slabs,
> > > - &array2_byte_offset, &array2_slabs);
> > > - if (size < mem_size) {
> > > + bmp = __rte_bitmap_init(n_bits, mem, mem_size);
> > > + if (!bmp)
> > > return NULL;
> > > - }
> > > -
> > > - /* Setup bitmap */
> > > - memset(mem, 0, size);
> > > - bmp = (struct rte_bitmap *) mem;
> > > -
> > > - bmp->array1 = (uint64_t *) &mem[array1_byte_offset];
> > > - bmp->array1_size = array1_slabs;
> > > - bmp->array2 = (uint64_t *) &mem[array2_byte_offset];
> > > - bmp->array2_size = array2_slabs;
> > > -
> > > - __rte_bitmap_scan_init(bmp);
> > > -
> > > + memset(bmp->array1, 0, bmp->array1_size * sizeof(uint64_t));
> > > + memset(bmp->array2, 0, bmp->array2_size * sizeof(uint64_t));
> > > return bmp;
> > > }
> > >
> >
> > Can we please leave the function rte_bitmap_init() unmodified and put all
> > changes in the new function rte_bitmap_init_with_all_set(). I realize this
> means
> > duplicating a few lines of code between the two init functions, but IMO
> easier to
> > maintain going forward.
>
> Sure. Agree with that, so let's keep the rte_bitmap_init() unmodified.
> >
> > > @@ -483,6 +493,53 @@ struct rte_bitmap {
> > > return 0;
> > > }
> > >
> > > +/**
> > > + * Bitmap initialization with all bits set
> > > + *
> > > + * @param n_bits
> > > + * Number of pre-allocated bits in array2.
> > > + * @param mem
> > > + * Base address of array1 and array2.
> > > + * @param mem_size
> > > + * Minimum expected size of bitmap.
> > > + * @return
> > > + * Handle to bitmap instance.
> > > + */
> > > +static inline struct rte_bitmap *
> > > +rte_bitmap_init_with_all_set(uint32_t n_bits, uint8_t *mem, uint32_t
> > > mem_size)
> > > +{
> > > + uint32_t i;
> > > + uint32_t slabs, array1_bits;
> > > + struct rte_bitmap *bmp;
> > > +
> > > + bmp = __rte_bitmap_init(n_bits, mem, mem_size);
> > > + if (!bmp)
> > > + return NULL;
> > > +
> > > + array1_bits = bmp->array2_size >>
> > > RTE_BITMAP_CL_SLAB_SIZE_LOG2;
> > > + /* Fill the arry1 slab aligned bits. */
> > > + slabs = array1_bits >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
> > > + memset(bmp->array1, 0xff, slabs * sizeof(bmp->array1[0]));
> > > + /* Clear the array1 left slabs. */
> > > + memset(&bmp->array1[slabs], 0, (bmp->array1_size - slabs) *
> > > + sizeof(bmp->array1[0]));
> > > + /* Fill the array1 middle not full set slab. */
> > > + for (i = 0; i < (array1_bits & RTE_BITMAP_SLAB_BIT_MASK); i++)
> > > + bmp->array1[slabs] |= 1llu << i;
> > > +
> > > + /* Fill the arry2 slab aligned bits. */
> > > + slabs = n_bits >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
> > > + memset(bmp->array2, 0xff, slabs * sizeof(bmp->array2[0]));
> > > + /* Clear the array2 left slabs. */
> > > + memset(&bmp->array2[slabs], 0, (bmp->array2_size - slabs) *
> > > + sizeof(bmp->array2[0]));
> > > + /* Fill the array2 middle not full set slab. */
> > > + for (i = 0; i < (n_bits & RTE_BITMAP_SLAB_BIT_MASK); i++)
> > > + bmp->array2[slabs] |= 1llu << i;
> > > +
> > > + return bmp;
> > > +}
> > > +
> > > #ifdef __cplusplus
> > > }
> > > #endif
> > > --
> > > 1.8.3.1
> >
> > This code is not that easy to read. This function is tricky to implement, as
> we
> > basically need to correct some overhead bits in array1 and array2.
> >
> > What I suggest for the layout of this function:
> > -call essentially the same code as rte_bitmap_init(), with the change that
> we set
> > ALL the bits in array1 and array2 to 1 instead of 0 -call a new helper function
> to
> > correct (set to 0) all the array2 bits from position (index2, offset2) to the
> end -
> > call a new helper function to correct (set to 0) all the array1 bits from
> position
> > (index1, offset1) to the end
>
> Good suggestion.
> What about the function below, it will help both arry1 and array2 clear the
> not needed bits:
> /**
> * Bitmap clear slab overhead bits.
> *
> * @param slab
> * Slab arrary.
> * @param size
> * Slab array size.
For more clarity, maybe document the size parameter as: number of 64-bit slabs in the slabs array.
> * @param pos
> * The start bit position in the slabs to be cleared.
> */
> static inline void
> __rte_bitmap_clear_slab_overhead_bits(uint64_t *slabs, uint32_t slab_size,
> uint32_t pos)
> {
> uint32_t i;
> uint32_t index = pos / RTE_BITMAP_SLAB_BIT_SIZE;
> uint32_t offset = pos & RTE_BITMAP_SLAB_BIT_MASK;
>
> if (offset) {
> for (i = offset; i < RTE_BITMAP_SLAB_BIT_SIZE; i++)
> slabs[index] &= ~(1llu << i);
> index++;
> }
> if (index < slab_size)
> memset(&slabs[index], 0, sizeof(slabs[0]) *
> (slab_size - index));
> }
>
Excellent, I like it, thanks Suanming!
> It seems that is a bit difficult to find a none tricky way to clear the bits.
> >
> > What do you think?
> >
> > Thanks,
> > Cristian
Hi Cristian
Thanks for the suggestion. Will update the v3 patch.
BR
SuanmingMou
> -----Original Message-----
> From: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> Sent: Friday, April 10, 2020 7:21 PM
> To: Suanming Mou <suanmingm@mellanox.com>
> Cc: dev@dpdk.org; amo@semihalf.com
> Subject: RE: [PATCH v2 1/2] bitmap: add create bitmap with all bits set
>
>
>
> > -----Original Message-----
> > From: Suanming Mou <suanmingm@mellanox.com>
> > Sent: Friday, April 10, 2020 11:34 AM
> > To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> > Cc: dev@dpdk.org; amo@semihalf.com
> > Subject: RE: [PATCH v2 1/2] bitmap: add create bitmap with all bits
> > set
> >
> >
> >
> > > -----Original Message-----
> > > From: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> > > Sent: Thursday, April 9, 2020 10:16 PM
> > > To: Suanming Mou <suanmingm@mellanox.com>
> > > Cc: dev@dpdk.org; amo@semihalf.com
> > > Subject: RE: [PATCH v2 1/2] bitmap: add create bitmap with all bits
> > > set
> > >
> > > Hi Sunaming,
> > >
> > > > -----Original Message-----
> > > > From: Suanming Mou <suanmingm@mellanox.com>
> > > > Sent: Wednesday, April 8, 2020 4:06 AM
> > > > To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> > > > Cc: dev@dpdk.org; amo@semihalf.com
> > > > Subject: [PATCH v2 1/2] bitmap: add create bitmap with all bits
> > > > set
> > > >
> > > > Currently, in the case to use bitmap as resource allocator, after
> > > > bitmap creation, all the bitmap bits should be set to indicate the
> > > > bit available. Every time when allocate one bit, search for the
> > > > set bits and clear it to make it in use.
> > > >
> > > > Add a new rte_bitmap_init_with_all_set() function to have a quick
> > > > fill up the bitmap bits.
> > > >
> > > > Comparing with the case create the bitmap as empty and set the
> > > > bitmap one by one, the new function costs less cycles.
> > > >
> > > > Signed-off-by: Suanming Mou <suanmingm@mellanox.com>
> > > > ---
> > > > lib/librte_eal/common/include/rte_bitmap.h | 113
> > > > ++++++++++++++++++++++-------
> > > > 1 file changed, 85 insertions(+), 28 deletions(-)
> > > >
> > > > diff --git a/lib/librte_eal/common/include/rte_bitmap.h
> > > > b/lib/librte_eal/common/include/rte_bitmap.h
> > > > index 6b846f2..740076b 100644
> > > > --- a/lib/librte_eal/common/include/rte_bitmap.h
> > > > +++ b/lib/librte_eal/common/include/rte_bitmap.h
> > > > @@ -136,6 +136,40 @@ struct rte_bitmap {
> > > > bmp->go2 = 0;
> > > > }
> > > >
> > > > +static inline struct rte_bitmap * __rte_bitmap_init(uint32_t
> > > > +n_bits, uint8_t *mem, uint32_t mem_size) {
> > > > + struct rte_bitmap *bmp;
> > > > + uint32_t array1_byte_offset, array1_slabs;
> > > > + uint32_t array2_byte_offset, array2_slabs;
> > > > + uint32_t size;
> > > > +
> > > > + /* Check input arguments */
> > > > + if (n_bits == 0)
> > > > + return NULL;
> > > > +
> > > > + if ((mem == NULL) || (((uintptr_t) mem) &
> > > > RTE_CACHE_LINE_MASK))
> > > > + return NULL;
> > > > +
> > > > + size = __rte_bitmap_get_memory_footprint(n_bits,
> > > > + &array1_byte_offset, &array1_slabs,
> > > > + &array2_byte_offset, &array2_slabs);
> > > > + if (size < mem_size)
> > > > + return NULL;
> > > > +
> > > > + /* Setup bitmap */
> > > > + bmp = (struct rte_bitmap *) mem;
> > > > +
> > > > + bmp->array1 = (uint64_t *) &mem[array1_byte_offset];
> > > > + bmp->array1_size = array1_slabs;
> > > > + bmp->array2 = (uint64_t *) &mem[array2_byte_offset];
> > > > + bmp->array2_size = array2_slabs;
> > > > +
> > > > + __rte_bitmap_scan_init(bmp);
> > > > +
> > > > + return bmp;
> > > > +}
> > > > +
> > > > /**
> > > > * Bitmap memory footprint calculation
> > > > *
> > > > @@ -170,36 +204,12 @@ struct rte_bitmap {
> > > > rte_bitmap_init(uint32_t n_bits, uint8_t *mem, uint32_t mem_size) {
> > > > struct rte_bitmap *bmp;
> > > > - uint32_t array1_byte_offset, array1_slabs, array2_byte_offset,
> > > > array2_slabs;
> > > > - uint32_t size;
> > > >
> > > > - /* Check input arguments */
> > > > - if (n_bits == 0) {
> > > > - return NULL;
> > > > - }
> > > > -
> > > > - if ((mem == NULL) || (((uintptr_t) mem) &
> > > > RTE_CACHE_LINE_MASK)) {
> > > > - return NULL;
> > > > - }
> > > > -
> > > > - size = __rte_bitmap_get_memory_footprint(n_bits,
> > > > - &array1_byte_offset, &array1_slabs,
> > > > - &array2_byte_offset, &array2_slabs);
> > > > - if (size < mem_size) {
> > > > + bmp = __rte_bitmap_init(n_bits, mem, mem_size);
> > > > + if (!bmp)
> > > > return NULL;
> > > > - }
> > > > -
> > > > - /* Setup bitmap */
> > > > - memset(mem, 0, size);
> > > > - bmp = (struct rte_bitmap *) mem;
> > > > -
> > > > - bmp->array1 = (uint64_t *) &mem[array1_byte_offset];
> > > > - bmp->array1_size = array1_slabs;
> > > > - bmp->array2 = (uint64_t *) &mem[array2_byte_offset];
> > > > - bmp->array2_size = array2_slabs;
> > > > -
> > > > - __rte_bitmap_scan_init(bmp);
> > > > -
> > > > + memset(bmp->array1, 0, bmp->array1_size * sizeof(uint64_t));
> > > > + memset(bmp->array2, 0, bmp->array2_size * sizeof(uint64_t));
> > > > return bmp;
> > > > }
> > > >
> > >
> > > Can we please leave the function rte_bitmap_init() unmodified and
> > > put all changes in the new function rte_bitmap_init_with_all_set().
> > > I realize this
> > means
> > > duplicating a few lines of code between the two init functions, but
> > > IMO
> > easier to
> > > maintain going forward.
> >
> > Sure. Agree with that, so let's keep the rte_bitmap_init() unmodified.
> > >
> > > > @@ -483,6 +493,53 @@ struct rte_bitmap {
> > > > return 0;
> > > > }
> > > >
> > > > +/**
> > > > + * Bitmap initialization with all bits set
> > > > + *
> > > > + * @param n_bits
> > > > + * Number of pre-allocated bits in array2.
> > > > + * @param mem
> > > > + * Base address of array1 and array2.
> > > > + * @param mem_size
> > > > + * Minimum expected size of bitmap.
> > > > + * @return
> > > > + * Handle to bitmap instance.
> > > > + */
> > > > +static inline struct rte_bitmap *
> > > > +rte_bitmap_init_with_all_set(uint32_t n_bits, uint8_t *mem,
> > > > +uint32_t
> > > > mem_size)
> > > > +{
> > > > + uint32_t i;
> > > > + uint32_t slabs, array1_bits;
> > > > + struct rte_bitmap *bmp;
> > > > +
> > > > + bmp = __rte_bitmap_init(n_bits, mem, mem_size);
> > > > + if (!bmp)
> > > > + return NULL;
> > > > +
> > > > + array1_bits = bmp->array2_size >>
> > > > RTE_BITMAP_CL_SLAB_SIZE_LOG2;
> > > > + /* Fill the arry1 slab aligned bits. */
> > > > + slabs = array1_bits >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
> > > > + memset(bmp->array1, 0xff, slabs * sizeof(bmp->array1[0]));
> > > > + /* Clear the array1 left slabs. */
> > > > + memset(&bmp->array1[slabs], 0, (bmp->array1_size - slabs) *
> > > > + sizeof(bmp->array1[0]));
> > > > + /* Fill the array1 middle not full set slab. */
> > > > + for (i = 0; i < (array1_bits & RTE_BITMAP_SLAB_BIT_MASK); i++)
> > > > + bmp->array1[slabs] |= 1llu << i;
> > > > +
> > > > + /* Fill the arry2 slab aligned bits. */
> > > > + slabs = n_bits >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
> > > > + memset(bmp->array2, 0xff, slabs * sizeof(bmp->array2[0]));
> > > > + /* Clear the array2 left slabs. */
> > > > + memset(&bmp->array2[slabs], 0, (bmp->array2_size - slabs) *
> > > > + sizeof(bmp->array2[0]));
> > > > + /* Fill the array2 middle not full set slab. */
> > > > + for (i = 0; i < (n_bits & RTE_BITMAP_SLAB_BIT_MASK); i++)
> > > > + bmp->array2[slabs] |= 1llu << i;
> > > > +
> > > > + return bmp;
> > > > +}
> > > > +
> > > > #ifdef __cplusplus
> > > > }
> > > > #endif
> > > > --
> > > > 1.8.3.1
> > >
> > > This code is not that easy to read. This function is tricky to
> > > implement, as
> > we
> > > basically need to correct some overhead bits in array1 and array2.
> > >
> > > What I suggest for the layout of this function:
> > > -call essentially the same code as rte_bitmap_init(), with the
> > > change that
> > we set
> > > ALL the bits in array1 and array2 to 1 instead of 0 -call a new
> > > helper function
> > to
> > > correct (set to 0) all the array2 bits from position (index2,
> > > offset2) to the
> > end -
> > > call a new helper function to correct (set to 0) all the array1 bits
> > > from
> > position
> > > (index1, offset1) to the end
> >
> > Good suggestion.
> > What about the function below, it will help both arry1 and array2
> > clear the not needed bits:
> > /**
> > * Bitmap clear slab overhead bits.
> > *
> > * @param slab
> > * Slab arrary.
> > * @param size
> > * Slab array size.
>
> For more clarity, maybe document the size parameter as: number of 64-bit slabs
> in the slabs array.
>
> > * @param pos
> > * The start bit position in the slabs to be cleared.
> > */
> > static inline void
> > __rte_bitmap_clear_slab_overhead_bits(uint64_t *slabs, uint32_t slab_size,
> > uint32_t pos)
> > {
> > uint32_t i;
> > uint32_t index = pos / RTE_BITMAP_SLAB_BIT_SIZE;
> > uint32_t offset = pos & RTE_BITMAP_SLAB_BIT_MASK;
> >
> > if (offset) {
> > for (i = offset; i < RTE_BITMAP_SLAB_BIT_SIZE; i++)
> > slabs[index] &= ~(1llu << i);
> > index++;
> > }
> > if (index < slab_size)
> > memset(&slabs[index], 0, sizeof(slabs[0]) *
> > (slab_size - index));
> > }
> >
>
> Excellent, I like it, thanks Suanming!
>
> > It seems that is a bit difficult to find a none tricky way to clear the bits.
> > >
> > > What do you think?
> > >
> > > Thanks,
> > > Cristian
@@ -136,6 +136,40 @@ struct rte_bitmap {
bmp->go2 = 0;
}
+static inline struct rte_bitmap *
+__rte_bitmap_init(uint32_t n_bits, uint8_t *mem, uint32_t mem_size)
+{
+ struct rte_bitmap *bmp;
+ uint32_t array1_byte_offset, array1_slabs;
+ uint32_t array2_byte_offset, array2_slabs;
+ uint32_t size;
+
+ /* Check input arguments */
+ if (n_bits == 0)
+ return NULL;
+
+ if ((mem == NULL) || (((uintptr_t) mem) & RTE_CACHE_LINE_MASK))
+ return NULL;
+
+ size = __rte_bitmap_get_memory_footprint(n_bits,
+ &array1_byte_offset, &array1_slabs,
+ &array2_byte_offset, &array2_slabs);
+ if (size < mem_size)
+ return NULL;
+
+ /* Setup bitmap */
+ bmp = (struct rte_bitmap *) mem;
+
+ bmp->array1 = (uint64_t *) &mem[array1_byte_offset];
+ bmp->array1_size = array1_slabs;
+ bmp->array2 = (uint64_t *) &mem[array2_byte_offset];
+ bmp->array2_size = array2_slabs;
+
+ __rte_bitmap_scan_init(bmp);
+
+ return bmp;
+}
+
/**
* Bitmap memory footprint calculation
*
@@ -170,36 +204,12 @@ struct rte_bitmap {
rte_bitmap_init(uint32_t n_bits, uint8_t *mem, uint32_t mem_size)
{
struct rte_bitmap *bmp;
- uint32_t array1_byte_offset, array1_slabs, array2_byte_offset, array2_slabs;
- uint32_t size;
- /* Check input arguments */
- if (n_bits == 0) {
- return NULL;
- }
-
- if ((mem == NULL) || (((uintptr_t) mem) & RTE_CACHE_LINE_MASK)) {
- return NULL;
- }
-
- size = __rte_bitmap_get_memory_footprint(n_bits,
- &array1_byte_offset, &array1_slabs,
- &array2_byte_offset, &array2_slabs);
- if (size < mem_size) {
+ bmp = __rte_bitmap_init(n_bits, mem, mem_size);
+ if (!bmp)
return NULL;
- }
-
- /* Setup bitmap */
- memset(mem, 0, size);
- bmp = (struct rte_bitmap *) mem;
-
- bmp->array1 = (uint64_t *) &mem[array1_byte_offset];
- bmp->array1_size = array1_slabs;
- bmp->array2 = (uint64_t *) &mem[array2_byte_offset];
- bmp->array2_size = array2_slabs;
-
- __rte_bitmap_scan_init(bmp);
-
+ memset(bmp->array1, 0, bmp->array1_size * sizeof(uint64_t));
+ memset(bmp->array2, 0, bmp->array2_size * sizeof(uint64_t));
return bmp;
}
@@ -483,6 +493,53 @@ struct rte_bitmap {
return 0;
}
+/**
+ * Bitmap initialization with all bits set
+ *
+ * @param n_bits
+ * Number of pre-allocated bits in array2.
+ * @param mem
+ * Base address of array1 and array2.
+ * @param mem_size
+ * Minimum expected size of bitmap.
+ * @return
+ * Handle to bitmap instance.
+ */
+static inline struct rte_bitmap *
+rte_bitmap_init_with_all_set(uint32_t n_bits, uint8_t *mem, uint32_t mem_size)
+{
+ uint32_t i;
+ uint32_t slabs, array1_bits;
+ struct rte_bitmap *bmp;
+
+ bmp = __rte_bitmap_init(n_bits, mem, mem_size);
+ if (!bmp)
+ return NULL;
+
+ array1_bits = bmp->array2_size >> RTE_BITMAP_CL_SLAB_SIZE_LOG2;
+ /* Fill the arry1 slab aligned bits. */
+ slabs = array1_bits >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
+ memset(bmp->array1, 0xff, slabs * sizeof(bmp->array1[0]));
+ /* Clear the array1 left slabs. */
+ memset(&bmp->array1[slabs], 0, (bmp->array1_size - slabs) *
+ sizeof(bmp->array1[0]));
+ /* Fill the array1 middle not full set slab. */
+ for (i = 0; i < (array1_bits & RTE_BITMAP_SLAB_BIT_MASK); i++)
+ bmp->array1[slabs] |= 1llu << i;
+
+ /* Fill the arry2 slab aligned bits. */
+ slabs = n_bits >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
+ memset(bmp->array2, 0xff, slabs * sizeof(bmp->array2[0]));
+ /* Clear the array2 left slabs. */
+ memset(&bmp->array2[slabs], 0, (bmp->array2_size - slabs) *
+ sizeof(bmp->array2[0]));
+ /* Fill the array2 middle not full set slab. */
+ for (i = 0; i < (n_bits & RTE_BITMAP_SLAB_BIT_MASK); i++)
+ bmp->array2[slabs] |= 1llu << i;
+
+ return bmp;
+}
+
#ifdef __cplusplus
}
#endif