Re: [dpdk-dev] [PATCH v4] bitmap: add init with all bits set

[Suanming Mou <suanmingm@mellanox.com>]

Hi Thomas,

Thanks for the update.

> -----Original Message-----
> From: Thomas Monjalon <thomas@monjalon.net>
> Sent: Wednesday, April 15, 2020 10:15 PM
> To: dev@dpdk.org
> Cc: amo@semihalf.com; Suanming Mou <suanmingm@mellanox.com>; Cristian
> Dumitrescu <cristian.dumitrescu@intel.com>
> Subject: [PATCH v4] bitmap: add init with all bits set
> 
> From: Suanming Mou <suanmingm@mellanox.com>
> 
> 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>
> Acked-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
Reviewed-by: Suanming Mou <suanmingm@mellanox.com>
> ---
> 
> v4:
> - add experimental tags and comments
> - move functions near original init function
> - squash test patch
> - use "init" word in title
> 
> v3 updates:
> 1. Implement individual rte_bitmap_init_with_all_set() function.
> 2. Add new function to clear the overhead bits.
> 
> v2 updates:
> 1. Split the common part to __rte_bitmap_init().
> 2. Set the slab bits more customized.
> 
> ---
>  app/test/test_bitmap.c              | 57 ++++++++++++++++++-
>  lib/librte_eal/include/rte_bitmap.h | 85 +++++++++++++++++++++++++++++
>  2 files changed, 141 insertions(+), 1 deletion(-)
> 
> diff --git a/app/test/test_bitmap.c b/app/test/test_bitmap.c index
> 95c5184882..a8204d329f 100644
> --- a/app/test/test_bitmap.c
> +++ b/app/test/test_bitmap.c
> @@ -146,7 +146,7 @@ test_bitmap_set_get_clear(struct rte_bitmap *bmp)  }
> 
>  static int
> -test_bitmap(void)
> +test_bitmap_all_clear(void)
>  {
>  	void *mem;
>  	uint32_t bmp_size;
> @@ -182,4 +182,59 @@ test_bitmap(void)
>  	return TEST_SUCCESS;
>  }
> 
> +static int
> +test_bitmap_all_set(void)
> +{
> +	void *mem;
> +	uint32_t i;
> +	uint64_t slab;
> +	uint32_t pos;
> +	uint32_t bmp_size;
> +	struct rte_bitmap *bmp;
> +
> +	bmp_size =
> +		rte_bitmap_get_memory_footprint(MAX_BITS);
> +
> +	mem = rte_zmalloc("test_bmap", bmp_size, RTE_CACHE_LINE_SIZE);
> +	if (mem == NULL) {
> +		printf("Failed to allocate memory for bitmap\n");
> +		return TEST_FAILED;
> +	}
> +
> +	bmp = rte_bitmap_init_with_all_set(MAX_BITS, mem, bmp_size);
> +	if (bmp == NULL) {
> +		printf("Failed to init bitmap\n");
> +		return TEST_FAILED;
> +	}
> +
> +	for (i = 0; i < MAX_BITS; i++) {
> +		pos = slab = 0;
> +		if (!rte_bitmap_scan(bmp, &pos, &slab)) {
> +			printf("Failed with init bitmap.\n");
> +			return TEST_FAILED;
> +		}
> +		pos += (slab ? __builtin_ctzll(slab) : 0);
> +		rte_bitmap_clear(bmp, pos);
> +	}
> +
> +	if (rte_bitmap_scan(bmp, &pos, &slab)) {
> +		printf("Too much bits set.\n");
> +		return TEST_FAILED;
> +	}
> +
> +	rte_bitmap_free(bmp);
> +	rte_free(mem);
> +
> +	return TEST_SUCCESS;
> +
> +}
> +
> +static int
> +test_bitmap(void)
> +{
> +	if (test_bitmap_all_clear() != TEST_SUCCESS)
> +		return TEST_FAILED;
> +	return test_bitmap_all_set();
> +}
> +
>  REGISTER_TEST_COMMAND(bitmap_test, test_bitmap); diff --git
> a/lib/librte_eal/include/rte_bitmap.h b/lib/librte_eal/include/rte_bitmap.h
> index 6b846f251b..7c90ef333f 100644
> --- a/lib/librte_eal/include/rte_bitmap.h
> +++ b/lib/librte_eal/include/rte_bitmap.h
> @@ -203,6 +203,91 @@ rte_bitmap_init(uint32_t n_bits, uint8_t *mem,
> uint32_t mem_size)
>  	return bmp;
>  }
> 
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change without prior notice.
> + *
> + * Bitmap clear slab overhead bits.
> + *
> + * @param slabs
> + *   Slab array.
> + * @param slab_size
> + *   Number of 64-bit slabs in the slabs array.
> + * @param pos
> + *   The start bit position in the slabs to be cleared.
> + */
> +__rte_experimental
> +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));
> +}
> +
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change without prior notice.
> + *
> + * 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.
> + */
> +__rte_experimental
> +static inline struct rte_bitmap *
> +rte_bitmap_init_with_all_set(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 || !mem || (((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);
> +
> +	memset(bmp->array1, 0xff, bmp->array1_size * sizeof(bmp->array1[0]));
> +	memset(bmp->array2, 0xff, bmp->array2_size * sizeof(bmp->array2[0]));
> +	/* Clear overhead bits. */
> +	__rte_bitmap_clear_slab_overhead_bits(bmp->array1, bmp-
> >array1_size,
> +			bmp->array2_size >>
> RTE_BITMAP_CL_SLAB_SIZE_LOG2);
> +	__rte_bitmap_clear_slab_overhead_bits(bmp->array2, bmp-
> >array2_size,
> +			n_bits);
> +	return bmp;
> +}
> +
>  /**
>   * Bitmap free
>   *
> --
> 2.26.0