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

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

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