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

[Suanming Mou]

> -----Original Message-----
> From: Dumitrescu, Cristian <cristian.dumitrescu at intel.com>
> Sent: Thursday, April 9, 2020 10:16 PM
> To: Suanming Mou <suanmingm at mellanox.com>
> Cc: dev at dpdk.org; amo at semihalf.com
> Subject: RE: [PATCH v2 1/2] bitmap: add create bitmap with all bits set
> 
> Hi Sunaming,
> 
> > -----Original Message-----
> > From: Suanming Mou <suanmingm at mellanox.com>
> > Sent: Wednesday, April 8, 2020 4:06 AM
> > To: Dumitrescu, Cristian <cristian.dumitrescu at intel.com>
> > Cc: dev at dpdk.org; amo at 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 at 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