[PATCH v3] Fix one error in mthca_alloc

drivers/infiniband/hw/mthca/mthca_allocator.c: alloc->last left unchanged in mthca_alloc, which
has impact on performance of function find_next_zero_bit in mthca_alloc.

Signed-off-by: kangning <redacted>
---
 
 I squashed two commits into one in this version.
 
 drivers/infiniband/hw/mthca/mthca_allocator.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/drivers/infiniband/hw/mthca/mthca_allocator.c b/drivers/infiniband/hw/mthca/mthca_allocator.c
index aef1d274a14e..1141695093e7 100644
--- a/drivers/infiniband/hw/mthca/mthca_allocator.c
+++ b/drivers/infiniband/hw/mthca/mthca_allocator.c

@@ -51,6 +51,9 @@ u32 mthca_alloc(struct mthca_alloc *alloc)
 	}
 
 	if (obj < alloc->max) {
+		alloc->last = obj + 1;
+		if (alloc->last == alloc->max)
+			alloc->last = 0;
 		set_bit(obj, alloc->table);
 		obj |= alloc->top;
 	} else

-- 
2.17.1

On Fri, Aug 27, 2021 at 08:52:28AM +0800, kangning wrote:

drivers/infiniband/hw/mthca/mthca_allocator.c: alloc->last left unchanged in mthca_alloc, which
has impact on performance of function find_next_zero_bit in mthca_alloc.

I don't know what the sentence above means, but the change is unlikely
to be correct.

When alloc->last starts to be equal to alloc->max, the
find_next_zero_bit() will always return alloc->max. which will ensure
that the following code is executed.

   48         if (obj >= alloc->max) {
   49                 alloc->top = (alloc->top + alloc->max) & alloc->mask;
   50                 obj = find_first_zero_bit(alloc->table, alloc->max);
   51         }


However the mthca_alloc() function has other error, it returns -1 while
based on its declaration it needs to be unsigned,

Thanks

> 
> On Fri, Aug 27, 2021 at 08:52:28AM +0800, kangning wrote:
> > drivers/infiniband/hw/mthca/mthca_allocator.c: alloc->last left unchanged in mthca_alloc, which
> > has impact on performance of function find_next_zero_bit in mthca_alloc.
> 
> I don't know what the sentence above means, but the change is unlikely
> to be correct.
> 
> When alloc->last starts to be equal to alloc->max, the
> find_next_zero_bit() will always return alloc->max. which will ensure
> that the following code is executed.
> 
>    48         if (obj >= alloc->max) {
>    49                 alloc->top = (alloc->top + alloc->max) & alloc->mask;
>    50                 obj = find_first_zero_bit(alloc->table, alloc->max);
>    51         }
> 

Thanks for your review.
Yes, your analysis is right. However, this is a bitmap allocator for resource id allocation (like QP, and CQ). 
We first look at the situation where no resource id is released.
When the value of alloc->last starts to reaches alloc->max, the bitmap will 
be full. In this case, it's normal to return an invalid value.

Now, let's add resource releasing into consideration. 
The following code is part of mthca_free：

70	spin_lock_irqsave(&alloc->lock, flags);
71
72	clear_bit(obj, alloc->table);
73	alloc->last = min(alloc->last, obj);
74	alloc->top = (alloc->top + alloc->max) & alloc->mask;

mthca_free() is used to release the allocated resource id. It will update alloc->last when obj is freed. 
So, if the bitmap has space for allocation, my modification can continuously work.

> 
> However the mthca_alloc() function has other error, it returns -1 while
> based on its declaration it needs to be unsigned,

I think you are right about this. But obj is the return value of u32 type, which is the requirement of resource id 
(though it may not fully use 32 bits). I have no idea of how to fix it.

Thanks.

> 
> Thanks
> 
> > 
> > Signed-off-by: kangning [off-list ref]
> > ---
> >  
> >  I squashed two commits into one in this version.
> >  
> >  drivers/infiniband/hw/mthca/mthca_allocator.c | 3 +++
> >  1 file changed, 3 insertions(+)
> > 
> > diff --git a/drivers/infiniband/hw/mthca/mthca_allocator.c b/drivers/infiniband/hw/mthca/mthca_allocator.c
> > index aef1d274a14e..1141695093e7 100644
> > --- a/drivers/infiniband/hw/mthca/mthca_allocator.c
> > +++ b/drivers/infiniband/hw/mthca/mthca_allocator.c
> > @@ -51,6 +51,9 @@ u32 mthca_alloc(struct mthca_alloc *alloc)
> >  	}
> >  
> >  	if (obj < alloc->max) {
> > +		alloc->last = obj + 1;
> > +		if (alloc->last == alloc->max)
> > +			alloc->last = 0;
> >  		set_bit(obj, alloc->table);
> >  		obj |= alloc->top;
> >  	} else
> > -- 
> > 2.17.1
> > 
[off-list ref]

>
> On Fri, Aug 27, 2021 at 08:52:28AM +0800, kangning wrote:
> > drivers/infiniband/hw/mthca/mthca_allocator.c: alloc->last left unchanged in mthca_alloc, which
> > has impact on performance of function find_next_zero_bit in mthca_alloc.
> 
> I don't know what the sentence above means, but the change is unlikely
> to be correct.
> 
> When alloc->last starts to be equal to alloc->max, the
> find_next_zero_bit() will always return alloc->max. which will ensure
> that the following code is executed.
> 
>    48         if (obj >= alloc->max) {
>    49                 alloc->top = (alloc->top + alloc->max) & alloc->mask;
>    50                 obj = find_first_zero_bit(alloc->table, alloc->max);
>    51         }
> 

Thanks for your review.
Your analysis is right. However, this is a bitmap allocator for resource id allocation (like QP, and CQ). 
We first look at the situation where no resource id is released.
When the value of alloc->last starts to reaches alloc->max, the bitmap will 
be full. In this case, it's normal to return an invalid value.

Now, let's add resource releasing into consideration. 
The following code is part of mthca_free()：

70	spin_lock_irqsave(&alloc->lock, flags);
71
72	clear_bit(obj, alloc->table);
73	alloc->last = min(alloc->last, obj);
74	alloc->top = (alloc->top + alloc->max) & alloc->mask;

mthca_free() is used to release the allocated resource id. It will update alloc->last when obj is freed. 
So, if the bitmap has space for allocation, my modification can continuously work.

> 
> However the mthca_alloc() function has other error, it returns -1 while
> based on its declaration it needs to be unsigned,

I think you are right about this. But obj is the return value of u32 type, which is the requirement of resource id 
(though it may not fully use 32 bits). I have no idea of how to fix it.

Thanks.

> 
> Thanks
> 
> > 
> > Signed-off-by: kangning [off-list ref]
> > ---
> >  
> >  I squashed two commits into one in this version.
> >  
> >  drivers/infiniband/hw/mthca/mthca_allocator.c | 3 +++
> >  1 file changed, 3 insertions(+)
> > 
> > diff --git a/drivers/infiniband/hw/mthca/mthca_allocator.c b/drivers/infiniband/hw/mthca/mthca_allocator.c
> > index aef1d274a14e..1141695093e7 100644
> > --- a/drivers/infiniband/hw/mthca/mthca_allocator.c
> > +++ b/drivers/infiniband/hw/mthca/mthca_allocator.c
> > @@ -51,6 +51,9 @@ u32 mthca_alloc(struct mthca_alloc *alloc)
> >  	}
> >  
> >  	if (obj < alloc->max) {
> > +		alloc->last = obj + 1;
> > +		if (alloc->last == alloc->max)
> > +			alloc->last = 0;
> >  		set_bit(obj, alloc->table);
> >  		obj |= alloc->top;
> >  	} else
> > -- 
> > 2.17.1
> > 
[off-list ref]

On Tue, Aug 31, 2021 at 06:40:38PM +0800, 康宁 wrote:

> 
> On Fri, Aug 27, 2021 at 08:52:28AM +0800, kangning wrote:
> > drivers/infiniband/hw/mthca/mthca_allocator.c: alloc->last left unchanged in mthca_alloc, which
> > has impact on performance of function find_next_zero_bit in mthca_alloc.
> 
> I don't know what the sentence above means, but the change is unlikely
> to be correct.
> 
> When alloc->last starts to be equal to alloc->max, the
> find_next_zero_bit() will always return alloc->max. which will ensure
> that the following code is executed.
> 
>    48         if (obj >= alloc->max) {
>    49                 alloc->top = (alloc->top + alloc->max) & alloc->mask;
>    50                 obj = find_first_zero_bit(alloc->table, alloc->max);
>    51         }
> 

Thanks for your review.
Yes, your analysis is right. However, this is a bitmap allocator for resource id allocation (like QP, and CQ). 
We first look at the situation where no resource id is released.
When the value of alloc->last starts to reaches alloc->max, the bitmap will 
be full. In this case, it's normal to return an invalid value.

Now, let's add resource releasing into consideration. 
The following code is part of mthca_free：

70	spin_lock_irqsave(&alloc->lock, flags);
71
72	clear_bit(obj, alloc->table);
73	alloc->last = min(alloc->last, obj);
74	alloc->top = (alloc->top + alloc->max) & alloc->mask;

mthca_free() is used to release the allocated resource id. It will update alloc->last when obj is freed. 
So, if the bitmap has space for allocation, my modification can continuously work.

After alloc->last starts to be equal to alloc->max, the bitmap is
searches with find_first_zero_bit() call. That will ensure that we look
for any bit between 0 and alloc->max.

So no, your change can't be right.

Thanks

> 
> However the mthca_alloc() function has other error, it returns -1 while
> based on its declaration it needs to be unsigned,

I think you are right about this. But obj is the return value of u32 type, which is the requirement of resource id 
(though it may not fully use 32 bits). I have no idea of how to fix it.

Thanks.

> 
> Thanks
> 
> > 
> > Signed-off-by: kangning [off-list ref]
> > ---
> >  
> >  I squashed two commits into one in this version.
> >  
> >  drivers/infiniband/hw/mthca/mthca_allocator.c | 3 +++
> >  1 file changed, 3 insertions(+)
> > 
> > diff --git a/drivers/infiniband/hw/mthca/mthca_allocator.c b/drivers/infiniband/hw/mthca/mthca_allocator.c
> > index aef1d274a14e..1141695093e7 100644
> > --- a/drivers/infiniband/hw/mthca/mthca_allocator.c
> > +++ b/drivers/infiniband/hw/mthca/mthca_allocator.c
> > @@ -51,6 +51,9 @@ u32 mthca_alloc(struct mthca_alloc *alloc)
> >  	}
> >  
> >  	if (obj < alloc->max) {
> > +		alloc->last = obj + 1;
> > +		if (alloc->last == alloc->max)
> > +			alloc->last = 0;
> >  		set_bit(obj, alloc->table);
> >  		obj |= alloc->top;
> >  	} else
> > -- 
> > 2.17.1
> > 
[off-list ref]

On Tue, Aug 31, 2021 at 06:40:38PM +0800, 康宁 wrote:

quoted

>
> On Fri, Aug 27, 2021 at 08:52:28AM +0800, kangning wrote:
> > drivers/infiniband/hw/mthca/mthca_allocator.c: alloc->last left unchanged in mthca_alloc, which
> > has impact on performance of function find_next_zero_bit in mthca_alloc.
>
> I don't know what the sentence above means, but the change is unlikely
> to be correct.
>
> When alloc->last starts to be equal to alloc->max, the
> find_next_zero_bit() will always return alloc->max. which will ensure
> that the following code is executed.
>
>    48         if (obj >= alloc->max) {
>    49                 alloc->top = (alloc->top + alloc->max) & alloc->mask;
>    50                 obj = find_first_zero_bit(alloc->table, alloc->max);
>    51         }
>

Thanks for your review.
Yes, your analysis is right. However, this is a bitmap allocator for resource id allocation (like QP, and CQ).
We first look at the situation where no resource id is released.
When the value of alloc->last starts to reaches alloc->max, the bitmap will
be full. In this case, it's normal to return an invalid value.

Now, let's add resource releasing into consideration.
The following code is part of mthca_free：

70	spin_lock_irqsave(&alloc->lock, flags);
71
72	clear_bit(obj, alloc->table);
73	alloc->last = min(alloc->last, obj);
74	alloc->top = (alloc->top + alloc->max) & alloc->mask;

mthca_free() is used to release the allocated resource id. It will update alloc->last when obj is freed.
So, if the bitmap has space for allocation, my modification can continuously work.

After alloc->last starts to be equal to alloc->max, the bitmap is
searches with find_first_zero_bit() call. That will ensure that we look
for any bit between 0 and alloc->max.

So no, your change can't be right.

If you never call function mthca_free(), you will never find a valid bit  in [0, alloc->max]
with find_first_zero_bit() call. Cause every bits between 0 and alloc->max are alloacted.

But if you called mthca_free() before, the freed obj is assigned to alloc->last, and we 
still can allocate the bitmap.

My modification is correct. 

Thanks

quoted

>
> However the mthca_alloc() function has other error, it returns -1 while
> based on its declaration it needs to be unsigned,

I think you are right about this. But obj is the return value of u32 type, which is the requirement of resource id
(though it may not fully use 32 bits). I have no idea of how to fix it.

Thanks.

>
> Thanks
>
> >
> > Signed-off-by: kangning [off-list ref]
> > ---
> > 
> >  I squashed two commits into one in this version.
> > 
> >  drivers/infiniband/hw/mthca/mthca_allocator.c | 3 +++
> >  1 file changed, 3 insertions(+)
> >
> > diff --git a/drivers/infiniband/hw/mthca/mthca_allocator.c b/drivers/infiniband/hw/mthca/mthca_allocator.c
> > index aef1d274a14e..1141695093e7 100644
> > --- a/drivers/infiniband/hw/mthca/mthca_allocator.c
> > +++ b/drivers/infiniband/hw/mthca/mthca_allocator.c
> > @@ -51,6 +51,9 @@ u32 mthca_alloc(struct mthca_alloc *alloc)
> >  }
> > 
> >  if (obj < alloc->max) {
> > +	alloc->last = obj + 1;
> > +	if (alloc->last == alloc->max)
> > +	alloc->last = 0;
> >  set_bit(obj, alloc->table);
> >  obj |= alloc->top;
> >  } else
> > --
> > 2.17.1
> >
[off-list ref]