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

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

[Suanming Mou]

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.

For bitmap with 1000 bits, create the bitmap with all bits set costs 754
cycles, while set one by one costs 14194. CPU info as below:
Intel(R) Xeon(R) Silver 4110 CPU @ 2.10GHz

Suanming Mou (2):
  bitmap: add create bitmap with all bits set
  test/bitmap: add bitmap create with all bits set case

 app/test/test_bitmap.c                     | 57 +++++++++++++++++++++++++++++-
 lib/librte_eal/common/include/rte_bitmap.h | 32 +++++++++++++++++
 2 files changed, 88 insertions(+), 1 deletion(-)

-- 
1.8.3.1

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

[Suanming Mou]

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 | 32 ++++++++++++++++++++++++++++++
 1 file changed, 32 insertions(+)

diff --git a/lib/librte_eal/common/include/rte_bitmap.h b/lib/librte_eal/common/include/rte_bitmap.h
index 6b846f2..36b32e4 100644
--- a/lib/librte_eal/common/include/rte_bitmap.h
+++ b/lib/librte_eal/common/include/rte_bitmap.h
@@ -483,6 +483,38 @@ 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 = n_bits / RTE_BITMAP_SLAB_BIT_SIZE;
+	struct rte_bitmap *bmp = rte_bitmap_init(n_bits, mem, mem_size);
+
+	if (!bmp)
+		return NULL;
+	/* Fill the arry2 byte aligned bits. */
+	memset(bmp->array2, 0xff, slabs * sizeof(bmp->array2[0]));
+	/* Fill the arry1 bits. */
+	for (i = 0; i < n_bits; i += RTE_BITMAP_CL_BIT_SIZE)
+		rte_bitmap_set(bmp, i);
+	/* Fill the arry2 left not byte aligned bits. */
+	for (i = slabs * RTE_BITMAP_SLAB_BIT_SIZE; i < n_bits; i++)
+		rte_bitmap_set(bmp, i);
+	return bmp;
+}
+
 #ifdef __cplusplus
 }
 #endif
-- 
1.8.3.1

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

[Suanming Mou]

Add the case to verify bitmap create with all bits set works
correctly.

Signed-off-by: Suanming Mou <suanmingm@mellanox.com>
---
 app/test/test_bitmap.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 56 insertions(+), 1 deletion(-)

diff --git a/app/test/test_bitmap.c b/app/test/test_bitmap.c
index 95c5184..a8204d3 100644
--- a/app/test/test_bitmap.c
+++ b/app/test/test_bitmap.c
@@ -146,7 +146,7 @@
 }
 
 static int
-test_bitmap(void)
+test_bitmap_all_clear(void)
 {
 	void *mem;
 	uint32_t bmp_size;
@@ -182,4 +182,59 @@
 	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);
-- 
1.8.3.1

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

[Thomas Monjalon]

Call for review, please.


10/03/2020 09:21, Suanming Mou:
> 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.
> 
> For bitmap with 1000 bits, create the bitmap with all bits set costs 754
> cycles, while set one by one costs 14194. CPU info as below:
> Intel(R) Xeon(R) Silver 4110 CPU @ 2.10GHz
> 
> Suanming Mou (2):
>   bitmap: add create bitmap with all bits set
>   test/bitmap: add bitmap create with all bits set case
> 
>  app/test/test_bitmap.c                     | 57 +++++++++++++++++++++++++++++-
>  lib/librte_eal/common/include/rte_bitmap.h | 32 +++++++++++++++++
>  2 files changed, 88 insertions(+), 1 deletion(-)
> 
> 

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

[Suanming Mou]

Ping

> -----Original Message-----
> From: Thomas Monjalon <thomas@monjalon.net>
> Sent: Wednesday, March 25, 2020 9:26 PM
> To: cristian.dumitrescu@intel.com
> Cc: dev@dpdk.org; Suanming Mou <suanmingm@mellanox.com>
> Subject: Re: [dpdk-dev] [PATCH 0/2] bitmap: add create bitmap with all bits set
> 
> Call for review, please.
> 
> 
> 10/03/2020 09:21, Suanming Mou:
> > 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.
> >
> > For bitmap with 1000 bits, create the bitmap with all bits set costs
> > 754 cycles, while set one by one costs 14194. CPU info as below:
> > Intel(R) Xeon(R) Silver 4110 CPU @ 2.10GHz
> >
> > Suanming Mou (2):
> >   bitmap: add create bitmap with all bits set
> >   test/bitmap: add bitmap create with all bits set case
> >
> >  app/test/test_bitmap.c                     | 57 +++++++++++++++++++++++++++++-
> >  lib/librte_eal/common/include/rte_bitmap.h | 32 +++++++++++++++++
> >  2 files changed, 88 insertions(+), 1 deletion(-)
> >
> >
> 
> 
> 
> 

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

[Andrzej Ostruszka]

Hello Suanming

Please find my comments below.  However please note that so far I have
never used DPDK bitmaps so I might not be the best person to comment -
this patch needs some attention so I spent some time on it.

Overall I'm fine with the changes however since this is a performance
enhancement I've added some remarks/comments.

On 3/10/20 9:21 AM, Suanming Mou wrote:
> 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 | 32 ++++++++++++++++++++++++++++++
>  1 file changed, 32 insertions(+)
> 
> diff --git a/lib/librte_eal/common/include/rte_bitmap.h b/lib/librte_eal/common/include/rte_bitmap.h
> index 6b846f2..36b32e4 100644
> --- a/lib/librte_eal/common/include/rte_bitmap.h
> +++ b/lib/librte_eal/common/include/rte_bitmap.h
> @@ -483,6 +483,38 @@ 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 = n_bits / RTE_BITMAP_SLAB_BIT_SIZE;
> +	struct rte_bitmap *bmp = rte_bitmap_init(n_bits, mem, mem_size);
> +
> +	if (!bmp)
> +		return NULL;
> +	/* Fill the arry2 byte aligned bits. */
> +	memset(bmp->array2, 0xff, slabs * sizeof(bmp->array2[0]));

In rte_bitmap_init() we clear memory with 0 and now we set it with 1s.
Maybe separating the configuration from the actual initialization would
be better?  So that you call __rte_bitmap_init() and later zero in
rte_bitmap_init() and set to 1s here.

> +	/* Fill the arry1 bits. */
> +	for (i = 0; i < n_bits; i += RTE_BITMAP_CL_BIT_SIZE)
> +		rte_bitmap_set(bmp, i);

Maybe you could here also compute the number of array1 bytes that can be
set to FF and use memset() and for the remaining user rte_bitmap_set()?
Right now you are also touching array2 memory which was already set above.

> +	/* Fill the arry2 left not byte aligned bits. */
> +	for (i = slabs * RTE_BITMAP_SLAB_BIT_SIZE; i < n_bits; i++)
> +		rte_bitmap_set(bmp, i);
> +	return bmp;
> +}
> +

With regards
Andrzej Ostruszka

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

[Suanming Mou]

On 4/3/2020 10:49 PM, Andrzej Ostruszka wrote:
> Hello Suanming
>
> Please find my comments below.  However please note that so far I have
> never used DPDK bitmaps so I might not be the best person to comment -
> this patch needs some attention so I spent some time on it.
>
> Overall I'm fine with the changes however since this is a performance
> enhancement I've added some remarks/comments.
Hi Andrzej , thanks for your suggestions.
>
> On 3/10/20 9:21 AM, Suanming Mou wrote:
>> 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 | 32 ++++++++++++++++++++++++++++++
>>   1 file changed, 32 insertions(+)
>>
>> diff --git a/lib/librte_eal/common/include/rte_bitmap.h b/lib/librte_eal/common/include/rte_bitmap.h
>> index 6b846f2..36b32e4 100644
>> --- a/lib/librte_eal/common/include/rte_bitmap.h
>> +++ b/lib/librte_eal/common/include/rte_bitmap.h
>> @@ -483,6 +483,38 @@ 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 = n_bits / RTE_BITMAP_SLAB_BIT_SIZE;
>> +	struct rte_bitmap *bmp = rte_bitmap_init(n_bits, mem, mem_size);
>> +
>> +	if (!bmp)
>> +		return NULL;
>> +	/* Fill the arry2 byte aligned bits. */
>> +	memset(bmp->array2, 0xff, slabs * sizeof(bmp->array2[0]));
> In rte_bitmap_init() we clear memory with 0 and now we set it with 1s.
> Maybe separating the configuration from the actual initialization would
> be better?  So that you call __rte_bitmap_init() and later zero in
> rte_bitmap_init() and set to 1s here.

Good idea. In fact, the first proposal was to add a new function which 
can set all the n_bits.

Since currently, the bitmap struct does not contain n_bits, the 
rte_bitmap_init_with_all_set() was introduced.

>
>> +	/* Fill the arry1 bits. */
>> +	for (i = 0; i < n_bits; i += RTE_BITMAP_CL_BIT_SIZE)
>> +		rte_bitmap_set(bmp, i);
> Maybe you could here also compute the number of array1 bytes that can be
> set to FF and use memset() and for the remaining user rte_bitmap_set()?
> Right now you are also touching array2 memory which was already set above.

The RTE_BITMAP_CL_BIT_SIZE is 512 with cache_line size 64. Maybe for 
most of the cases which creates the bitmap less than 4K bits will not 
have chance with the memset.

Anyway, will add it.

>
>> +	/* Fill the arry2 left not byte aligned bits. */
>> +	for (i = slabs * RTE_BITMAP_SLAB_BIT_SIZE; i < n_bits; i++)
>> +		rte_bitmap_set(bmp, i);
>> +	return bmp;
>> +}
>> +
> With regards
> Andrzej Ostruszka
>

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

[Suanming Mou]

Hi guys,

Since we are all quite curious about which is the best implementation 
for the performance, I just did some test on my server.

There will be 3 implementations.
1. Clear all the array1 and array2 bits first, then set the bits we 
needed.(The current implementation in the patch).
2. Set all the bits in array1 and array2 first, then clear the not 
needed bits.
3. Set the needed bits in array1 and array2, and clear the left not need 
bits.
(As we are allocate more memory as the alignment, clear not needed bits 
should be done anyway.)

So it's call the 3 implementation Cs, Sc, sc:
Capital 'C' means clear all bits.
Lowercase 'c' means clear not needed bits.
Capital 'S' means set all bits.
Lowercase 's' means set needed bits.

I add some test code in the bitmap_test code, here is the cycle for 
different bits with different implementations.
RTE>>bitmap_test
Set bits:63
Cs   Sc   sc
1018 1089 1078

Set bits:126
Cs   Sc   sc
972  1082 1048

Set bits:252
Cs   Sc   sc
918  1039 1029

Set bits:504
Cs   Sc   sc
861  986  957

Set bits:1008
Cs   Sc   sc
802  882  851

Set bits:2016
Cs   Sc   sc
618  646  625

Set bits:4032
Cs   Sc   sc
272  215  209

Set bits:8064
Cs   Sc   sc
537  392  391

Set bits:16128
Cs   Sc   sc
1083 786  798

As we can see, after 4K bits, the Cs case comes disadvantage, before 4K 
bits, it works much better.
And since the cycles before 4K  bits does not show more significant 
differences, it should be OK to use the Sc or sc cases.
Maybe better to choose the sc code.

===================================
Testing code as below:
static void
test_tsc(uint32_t n_bits)
{
         void *mem;
         uint32_t i;
         uint64_t start, cost, cost2, cost3;
         uint32_t bmp_size;
         struct rte_bitmap *bmp;

         bmp_size =
                 rte_bitmap_get_memory_footprint(n_bits);

         mem = rte_zmalloc("test_bmap", bmp_size, RTE_CACHE_LINE_SIZE);
         if (mem == NULL) {
                 printf("Failed to allocate memory for bitmap\n");
                 return;
         }
         /* Make the memory hot.*/
         bmp = rte_bitmap_init_with_all_set(n_bits, mem, bmp_size);
         if (bmp == NULL) {
                 printf("Failed to init bitmap\n");
                 return;
         }
         /* Clear all bits first, set needed. */
         start = rte_rdtsc();
         for (i = 0; i < 1000; i++)
                 rte_bitmap_init_with_all_set(n_bits, mem, bmp_size);
         cost = (rte_rdtsc() - start) / 1000;
         /* Set all bits first, clear not needed. */
         start = rte_rdtsc();
         for (i = 0; i < 1000; i++)
                 rte_bitmap_init_with_all_set2(n_bits, mem, bmp_size);
         cost2 = (rte_rdtsc() - start) / 1000;
         /* Set needed bits, clear left. */
         start = rte_rdtsc();
         for (i = 0; i < 1000; i++)
                 rte_bitmap_init_with_all_set3(n_bits, mem, bmp_size);
         cost3 = (rte_rdtsc() - start) / 1000;

         printf("Set bits:%d\nCs   Sc   sc\n", n_bits);
         printf("%-4ld %-4ld %-4ld\n\n", cost, cost2, cost3);

         rte_free(mem);
}


         uint32_t i;

         for (i = 63; i < (63 << 9); i<<=1)
                 test_tsc(i);

===================================
Sc code as below:
static inline struct rte_bitmap *
rte_bitmap_init_with_all_set2(uint32_t n_bits, uint8_t *mem, uint32_t 
mem_size)
{
         uint32_t i;
         uint32_t slabs;
         struct rte_bitmap *bmp;

         bmp = __rte_bitmap_init(n_bits, mem, mem_size);
         if (!bmp)
                 return NULL;
         memset(bmp->array1, 0xff, bmp->array1_size * sizeof(uint64_t));
         memset(bmp->array2, 0xff, bmp->array2_size * sizeof(uint64_t));
         /* Fill the arry1 slab aligned bits. */
         slabs = n_bits >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 +
                            RTE_BITMAP_CL_BIT_SIZE_LOG2);
         /* 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. */
         i = slabs << (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 +
                       RTE_BITMAP_CL_BIT_SIZE_LOG2);
         for (;i < n_bits; i += RTE_BITMAP_CL_BIT_SIZE)
                 rte_bitmap_set(bmp, i);
         /* Clear the array2 left slabs. */
         slabs = n_bits >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2;
         memset(&bmp->array2[slabs], 0, (bmp->array2_size - slabs) *
                sizeof(bmp->array2[0]));
         /* Fill the array2 middle not full set slab. */
         for (i = slabs * RTE_BITMAP_SLAB_BIT_SIZE; i < n_bits; i++)
                 rte_bitmap_set(bmp, i);
         return bmp;
}

===================================
sc code as below:
static inline struct rte_bitmap *
rte_bitmap_init_with_all_set3(uint32_t n_bits, uint8_t *mem, uint32_t 
mem_size)
{
         uint32_t i;
         uint32_t slabs;
         struct rte_bitmap *bmp;

         bmp = __rte_bitmap_init(n_bits, mem, mem_size);
         if (!bmp)
                 return NULL;
         /* Fill the arry1 slab aligned bits. */
         slabs = n_bits >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 +
                            RTE_BITMAP_CL_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. */
         i = slabs << (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 +
                       RTE_BITMAP_CL_BIT_SIZE_LOG2);
         for (;i < n_bits; i += RTE_BITMAP_CL_BIT_SIZE)
                 rte_bitmap_set(bmp, 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 = slabs * RTE_BITMAP_SLAB_BIT_SIZE; i < n_bits; i++)
                 rte_bitmap_set(bmp, i);
         return bmp;
}


Any comments or suggestions?

Thanks,
SuanmingMou

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

[Dumitrescu, Cristian]

Hi Suanming,

> -----Original Message-----
> From: Suanming Mou <suanmingm@mellanox.com>
> Sent: Tuesday, March 10, 2020 8:21 AM
> To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> Cc: dev@dpdk.org
> Subject: [PATCH 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 | 32
> ++++++++++++++++++++++++++++++
>  1 file changed, 32 insertions(+)
> 
> diff --git a/lib/librte_eal/common/include/rte_bitmap.h
> b/lib/librte_eal/common/include/rte_bitmap.h
> index 6b846f2..36b32e4 100644
> --- a/lib/librte_eal/common/include/rte_bitmap.h
> +++ b/lib/librte_eal/common/include/rte_bitmap.h
> @@ -483,6 +483,38 @@ 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 = n_bits / RTE_BITMAP_SLAB_BIT_SIZE;
> +	struct rte_bitmap *bmp = rte_bitmap_init(n_bits, mem, mem_size);
> +
> +	if (!bmp)
> +		return NULL;
> +	/* Fill the arry2 byte aligned bits. */
> +	memset(bmp->array2, 0xff, slabs * sizeof(bmp->array2[0]));
> +	/* Fill the arry1 bits. */
> +	for (i = 0; i < n_bits; i += RTE_BITMAP_CL_BIT_SIZE)
> +		rte_bitmap_set(bmp, i);
> +	/* Fill the arry2 left not byte aligned bits. */
> +	for (i = slabs * RTE_BITMAP_SLAB_BIT_SIZE; i < n_bits; i++)
> +		rte_bitmap_set(bmp, i);
> +	return bmp;
> +}
> +
>  #ifdef __cplusplus
>  }
>  #endif
> --
> 1.8.3.1

I agree that starting with all bits set could be very useful for some apps.

I agree that having a customized implementation for starting with all bits set -- as opposed to simply start with all bits cleared and calling the API in a loop to set each bit -- could be useful, as it could reduce the initialization time.

What I don't understand is your implementation of it: why still calling the API to set all bits in a loop? If we are to add this, I suggest we create a fully customized implementation that sets the fields on struct rte_bitmap to the right values. Makes sense?

Thanks,
Cristian

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

[Suanming Mou]

Hi 

> -----Original Message-----
> From: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> Sent: Wednesday, April 8, 2020 1:48 AM
> To: Suanming Mou <suanmingm@mellanox.com>
> Cc: dev@dpdk.org
> Subject: RE: [PATCH 1/2] bitmap: add create bitmap with all bits set
> 
> Hi Suanming,
> 
> > -----Original Message-----
> > From: Suanming Mou <suanmingm@mellanox.com>
> > Sent: Tuesday, March 10, 2020 8:21 AM
> > To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> > Cc: dev@dpdk.org
> > Subject: [PATCH 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 | 32
> > ++++++++++++++++++++++++++++++
> >  1 file changed, 32 insertions(+)
> >
> > diff --git a/lib/librte_eal/common/include/rte_bitmap.h
> > b/lib/librte_eal/common/include/rte_bitmap.h
> > index 6b846f2..36b32e4 100644
> > --- a/lib/librte_eal/common/include/rte_bitmap.h
> > +++ b/lib/librte_eal/common/include/rte_bitmap.h
> > @@ -483,6 +483,38 @@ 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 = n_bits / RTE_BITMAP_SLAB_BIT_SIZE;
> > +	struct rte_bitmap *bmp = rte_bitmap_init(n_bits, mem, mem_size);
> > +
> > +	if (!bmp)
> > +		return NULL;
> > +	/* Fill the arry2 byte aligned bits. */
> > +	memset(bmp->array2, 0xff, slabs * sizeof(bmp->array2[0]));
> > +	/* Fill the arry1 bits. */
> > +	for (i = 0; i < n_bits; i += RTE_BITMAP_CL_BIT_SIZE)
> > +		rte_bitmap_set(bmp, i);
> > +	/* Fill the arry2 left not byte aligned bits. */
> > +	for (i = slabs * RTE_BITMAP_SLAB_BIT_SIZE; i < n_bits; i++)
> > +		rte_bitmap_set(bmp, i);
> > +	return bmp;
> > +}
> > +
> >  #ifdef __cplusplus
> >  }
> >  #endif
> > --
> > 1.8.3.1
> 
> I agree that starting with all bits set could be very useful for some apps.
> 
> I agree that having a customized implementation for starting with all bits set --
> as opposed to simply start with all bits cleared and calling the API in a loop to set
> each bit -- could be useful, as it could reduce the initialization time.
> 
> What I don't understand is your implementation of it: why still calling the API to
> set all bits in a loop? If we are to add this, I suggest we create a fully customized
> implementation that sets the fields on struct rte_bitmap to the right values.
> Makes sense?
Thanks for the suggestion. Will update.
> 
> Thanks,
> Cristian

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

[Suanming Mou]

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.

For bitmap with 1000 bits, create the bitmap with all bits set costs 754
cycles, while set one by one costs 14194. CPU info as below:
Intel(R) Xeon(R) Silver 4110 CPU @ 2.10GHz

v2 updates:
1. Split the common part to __rte_bitmap_init().
2. Set the slab bits more customized.

Suanming Mou (2):
  bitmap: add create bitmap with all bits set
  test/bitmap: add bitmap create with all bits set case

 app/test/test_bitmap.c                     |  57 ++++++++++++++-
 lib/librte_eal/common/include/rte_bitmap.h | 113 ++++++++++++++++++++++-------
 2 files changed, 141 insertions(+), 29 deletions(-)

-- 
1.8.3.1

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

[Suanming Mou]

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;
 }
 
@@ -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

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

[Suanming Mou]

Add the case to verify bitmap create with all bits set works
correctly.

Signed-off-by: Suanming Mou <suanmingm@mellanox.com>
---
 app/test/test_bitmap.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 56 insertions(+), 1 deletion(-)

diff --git a/app/test/test_bitmap.c b/app/test/test_bitmap.c
index 95c5184..a8204d3 100644
--- a/app/test/test_bitmap.c
+++ b/app/test/test_bitmap.c
@@ -146,7 +146,7 @@
 }
 
 static int
-test_bitmap(void)
+test_bitmap_all_clear(void)
 {
 	void *mem;
 	uint32_t bmp_size;
@@ -182,4 +182,59 @@
 	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);
-- 
1.8.3.1

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

[Dumitrescu, Cristian]

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

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

[Suanming Mou]

> -----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.
 * @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

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

[Dumitrescu, Cristian]

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

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

[Suanming Mou]

Hi Cristian

Thanks for the suggestion. Will update the v3 patch.

BR
SuanmingMou

> -----Original Message-----
> From: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> Sent: Friday, April 10, 2020 7:21 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
> 
> 
> 
> > -----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

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

[Suanming Mou]

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.

For bitmap with 1000 bits, create the bitmap with all bits set costs 754
cycles, while set one by one costs 14194. CPU info as below:
Intel(R) Xeon(R) Silver 4110 CPU @ 2.10GHz

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.

Suanming Mou (2):
  bitmap: add create bitmap with all bits set
  test/bitmap: add bitmap create with all bits set case

 app/test/test_bitmap.c              | 57 ++++++++++++++++++++++++++-
 lib/librte_eal/include/rte_bitmap.h | 78 +++++++++++++++++++++++++++++++++++++
 2 files changed, 134 insertions(+), 1 deletion(-)

-- 
1.8.3.1

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

[Suanming Mou]

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/include/rte_bitmap.h | 78 +++++++++++++++++++++++++++++++++++++
 1 file changed, 78 insertions(+)

diff --git a/lib/librte_eal/include/rte_bitmap.h b/lib/librte_eal/include/rte_bitmap.h
index 6b846f2..e3b806e 100644
--- a/lib/librte_eal/include/rte_bitmap.h
+++ b/lib/librte_eal/include/rte_bitmap.h
@@ -483,6 +483,84 @@ struct rte_bitmap {
 	return 0;
 }
 
+/**
+ * Bitmap clear slab overhead bits.
+ *
+ * @param slabs
+ *   Slab arrary.
+ * @param slab_size
+ *   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));
+}
+
+
+/**
+ * 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)
+{
+	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;
+}
+
 #ifdef __cplusplus
 }
 #endif
-- 
1.8.3.1

[dpdk-dev] [PATCH v3 2/2] test/bitmap: add bitmap create with all bits set case

[Suanming Mou]

Add the case to verify bitmap create with all bits set works
correctly.

Signed-off-by: Suanming Mou <suanmingm@mellanox.com>
---
 app/test/test_bitmap.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 56 insertions(+), 1 deletion(-)

diff --git a/app/test/test_bitmap.c b/app/test/test_bitmap.c
index 95c5184..a8204d3 100644
--- a/app/test/test_bitmap.c
+++ b/app/test/test_bitmap.c
@@ -146,7 +146,7 @@
 }
 
 static int
-test_bitmap(void)
+test_bitmap_all_clear(void)
 {
 	void *mem;
 	uint32_t bmp_size;
@@ -182,4 +182,59 @@
 	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);
-- 
1.8.3.1

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

[Dumitrescu, Cristian]

> -----Original Message-----
> From: Suanming Mou <suanmingm@mellanox.com>
> Sent: Friday, April 10, 2020 1:46 PM
> To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>; dev@dpdk.org
> Cc: amo@semihalf.com
> Subject: [PATCH v3 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/include/rte_bitmap.h | 78
> +++++++++++++++++++++++++++++++++++++
>  1 file changed, 78 insertions(+)
> 

Acked-by: Cristian Dumitrescu <cristian.dumitrescu@intel.com>

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

[Thomas Monjalon]

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

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

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

[Suanming Mou]

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

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

[Thomas Monjalon]

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