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

["Dumitrescu, Cristian" <cristian.dumitrescu@intel.com>]

> -----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