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

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

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
  

15/04/2020 16:22, Suanming Mou:
> Hi Thomas,
> 
> Thanks for the update.
> 
> From: Thomas Monjalon <thomas@monjalon.net>
> > 
> > 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.

Applied, thanks