Re: [dpdk-dev] [PATCH v2 1/2] bitmap: add create bitmap with all bits set

[Suanming Mou <suanmingm@mellanox.com>]

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