[PATCH v2 0/2] RDMA/cm: Optimise rbtree searching

[PATCH v2 0/2] RDMA/cm: Optimise rbtree searching

[Zhen Lei]

v1 --> v2:
1. On the advice of Jason Gunthorpe, add patch 2
Rewrite the rbtree traversing in the normal pattern:
if (a < b)
    ..
else if (a > b)
    ..
else // a == b
    ..

Zhen Lei (2):
  RDMA/cm: Delete two redundant condition branches
  RDMA/cm: Optimise rbtree searching

 drivers/infiniband/core/cm.c | 54 +++++++++++++++++-------------------
 1 file changed, 26 insertions(+), 28 deletions(-)

-- 
2.26.0.106.g9fadedd

[PATCH v2 1/2] RDMA/cm: Delete two redundant condition branches

[Zhen Lei]

The statement of the last "if (xxx)" branch is the same as the "else"
branch. Delete it to simplify code.

No functional change.

Reviewed-by: Leon Romanovsky <leonro@nvidia.com>
Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
---
 drivers/infiniband/core/cm.c | 4 ----
 1 file changed, 4 deletions(-)

diff --git a/drivers/infiniband/core/cm.c b/drivers/infiniband/core/cm.c
index 0ead0d223154011..510beb25f5b8a0b 100644
--- a/drivers/infiniband/core/cm.c
+++ b/drivers/infiniband/core/cm.c
@@ -668,8 +668,6 @@ static struct cm_id_private *cm_insert_listen(struct cm_id_private *cm_id_priv,
 			link = &(*link)->rb_right;
 		else if (be64_lt(service_id, cur_cm_id_priv->id.service_id))
 			link = &(*link)->rb_left;
-		else if (be64_gt(service_id, cur_cm_id_priv->id.service_id))
-			link = &(*link)->rb_right;
 		else
 			link = &(*link)->rb_right;
 	}
@@ -700,8 +698,6 @@ static struct cm_id_private *cm_find_listen(struct ib_device *device,
 			node = node->rb_right;
 		else if (be64_lt(service_id, cm_id_priv->id.service_id))
 			node = node->rb_left;
-		else if (be64_gt(service_id, cm_id_priv->id.service_id))
-			node = node->rb_right;
 		else
 			node = node->rb_right;
 	}
-- 
2.26.0.106.g9fadedd

[PATCH v2 2/2] RDMA/cm: Optimise rbtree searching

[Zhen Lei]

Rewrite the rbtree traversing in the normal pattern:
if (a < b)
    ..
else if (a > b)
    ..
else // a == b
    ..

This gives us some performance improvement. Because the search complexity
of the rbtree is log(N). That is, after an average of "log(N) - 1" search
failures, a success or failure is known only in the last round. That is,
the (a == b) only needs to be compared once, whereas our current writing
compares log(N) times on average.

Suggested-by: Jason Gunthorpe <jgg@nvidia.com>
Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
---
 drivers/infiniband/core/cm.c | 50 +++++++++++++++++++-----------------
 1 file changed, 26 insertions(+), 24 deletions(-)

diff --git a/drivers/infiniband/core/cm.c b/drivers/infiniband/core/cm.c
index 510beb25f5b8a0b..2198de857a06591 100644
--- a/drivers/infiniband/core/cm.c
+++ b/drivers/infiniband/core/cm.c
@@ -643,29 +643,14 @@ static struct cm_id_private *cm_insert_listen(struct cm_id_private *cm_id_priv,
 		parent = *link;
 		cur_cm_id_priv = rb_entry(parent, struct cm_id_private,
 					  service_node);
-		if ((cur_cm_id_priv->id.service_mask & service_id) ==
-		    (service_mask & cur_cm_id_priv->id.service_id) &&
-		    (cm_id_priv->id.device == cur_cm_id_priv->id.device)) {
-			/*
-			 * Sharing an ib_cm_id with different handlers is not
-			 * supported
-			 */
-			if (cur_cm_id_priv->id.cm_handler != shared_handler ||
-			    cur_cm_id_priv->id.context ||
-			    WARN_ON(!cur_cm_id_priv->id.cm_handler)) {
-				spin_unlock_irqrestore(&cm.lock, flags);
-				return NULL;
-			}
-			refcount_inc(&cur_cm_id_priv->refcount);
-			cur_cm_id_priv->listen_sharecount++;
-			spin_unlock_irqrestore(&cm.lock, flags);
-			return cur_cm_id_priv;
-		}
 
 		if (cm_id_priv->id.device < cur_cm_id_priv->id.device)
 			link = &(*link)->rb_left;
 		else if (cm_id_priv->id.device > cur_cm_id_priv->id.device)
 			link = &(*link)->rb_right;
+		else if ((cur_cm_id_priv->id.service_mask & service_id) ==
+			 (service_mask & cur_cm_id_priv->id.service_id))
+			goto found;
 		else if (be64_lt(service_id, cur_cm_id_priv->id.service_id))
 			link = &(*link)->rb_left;
 		else
@@ -676,6 +661,22 @@ static struct cm_id_private *cm_insert_listen(struct cm_id_private *cm_id_priv,
 	rb_insert_color(&cm_id_priv->service_node, &cm.listen_service_table);
 	spin_unlock_irqrestore(&cm.lock, flags);
 	return cm_id_priv;
+
+found:
+	/*
+	 * Sharing an ib_cm_id with different handlers is not
+	 * supported
+	 */
+	if (cur_cm_id_priv->id.cm_handler != shared_handler ||
+	    cur_cm_id_priv->id.context ||
+	    WARN_ON(!cur_cm_id_priv->id.cm_handler)) {
+		spin_unlock_irqrestore(&cm.lock, flags);
+		return NULL;
+	}
+	refcount_inc(&cur_cm_id_priv->refcount);
+	cur_cm_id_priv->listen_sharecount++;
+	spin_unlock_irqrestore(&cm.lock, flags);
+	return cur_cm_id_priv;
 }
 
 static struct cm_id_private *cm_find_listen(struct ib_device *device,
@@ -686,22 +687,23 @@ static struct cm_id_private *cm_find_listen(struct ib_device *device,
 
 	while (node) {
 		cm_id_priv = rb_entry(node, struct cm_id_private, service_node);
-		if ((cm_id_priv->id.service_mask & service_id) ==
-		     cm_id_priv->id.service_id &&
-		    (cm_id_priv->id.device == device)) {
-			refcount_inc(&cm_id_priv->refcount);
-			return cm_id_priv;
-		}
+
 		if (device < cm_id_priv->id.device)
 			node = node->rb_left;
 		else if (device > cm_id_priv->id.device)
 			node = node->rb_right;
+		else if ((cm_id_priv->id.service_mask & service_id) == cm_id_priv->id.service_id)
+			goto found;
 		else if (be64_lt(service_id, cm_id_priv->id.service_id))
 			node = node->rb_left;
 		else
 			node = node->rb_right;
 	}
 	return NULL;
+
+found:
+	refcount_inc(&cm_id_priv->refcount);
+	return cm_id_priv;
 }
 
 static struct cm_timewait_info *
-- 
2.26.0.106.g9fadedd

Re: [PATCH v2 2/2] RDMA/cm: Optimise rbtree searching

[Jason Gunthorpe]

On Wed, May 12, 2021 at 06:05:37PM +0800, Zhen Lei wrote:
>  static struct cm_id_private *cm_find_listen(struct ib_device *device,
> @@ -686,22 +687,23 @@ static struct cm_id_private *cm_find_listen(struct ib_device *device,
>  
>  	while (node) {
>  		cm_id_priv = rb_entry(node, struct cm_id_private, service_node);
> -		if ((cm_id_priv->id.service_mask & service_id) ==
> -		     cm_id_priv->id.service_id &&
> -		    (cm_id_priv->id.device == device)) {
> -			refcount_inc(&cm_id_priv->refcount);
> -			return cm_id_priv;
> -		}
> +
>  		if (device < cm_id_priv->id.device)
>  			node = node->rb_left;
>  		else if (device > cm_id_priv->id.device)
>  			node = node->rb_right;
> +		else if ((cm_id_priv->id.service_mask & service_id) == cm_id_priv->id.service_id)
> +			goto found;
>  		else if (be64_lt(service_id, cm_id_priv->id.service_id))
>  			node = node->rb_left;
>  		else
>  			node = node->rb_right;
>  	}

This is not the pattern I showed you. Drop the first patch and rely on
the implicit equality in the final else.

Jason

Re: [PATCH v2 2/2] RDMA/cm: Optimise rbtree searching

[Leizhen (ThunderTown)]

On 2021/5/12 20:50, Jason Gunthorpe wrote:
> On Wed, May 12, 2021 at 06:05:37PM +0800, Zhen Lei wrote:
>>  static struct cm_id_private *cm_find_listen(struct ib_device *device,
>> @@ -686,22 +687,23 @@ static struct cm_id_private *cm_find_listen(struct ib_device *device,
>>  
>>  	while (node) {
>>  		cm_id_priv = rb_entry(node, struct cm_id_private, service_node);
>> -		if ((cm_id_priv->id.service_mask & service_id) ==
>> -		     cm_id_priv->id.service_id &&
>> -		    (cm_id_priv->id.device == device)) {
>> -			refcount_inc(&cm_id_priv->refcount);
>> -			return cm_id_priv;
>> -		}
>> +
>>  		if (device < cm_id_priv->id.device)
>>  			node = node->rb_left;
>>  		else if (device > cm_id_priv->id.device)
>>  			node = node->rb_right;
>> +		else if ((cm_id_priv->id.service_mask & service_id) == cm_id_priv->id.service_id)
>> +			goto found;
>>  		else if (be64_lt(service_id, cm_id_priv->id.service_id))
>>  			node = node->rb_left;
>>  		else
>>  			node = node->rb_right;
>>  	}
> 
> This is not the pattern I showed you. Drop the first patch and rely on
> the implicit equality in the final else.

Do you mean treate the "found" process as the else branch?

But ((cm_id_priv->id.service_mask & service_id) == cm_id_priv->id.service_id) is different from
(service_id == cm_id_priv->id.service_id)，I'm just worried that it might change the original logic.

> 
> Jason
> 
> .
> 

Re: [PATCH v2 2/2] RDMA/cm: Optimise rbtree searching

[Jason Gunthorpe]

On Wed, May 12, 2021 at 09:12:08PM +0800, Leizhen (ThunderTown) wrote:
> 
> 
> On 2021/5/12 20:50, Jason Gunthorpe wrote:
> > On Wed, May 12, 2021 at 06:05:37PM +0800, Zhen Lei wrote:
> >>  static struct cm_id_private *cm_find_listen(struct ib_device *device,
> >> @@ -686,22 +687,23 @@ static struct cm_id_private *cm_find_listen(struct ib_device *device,
> >>  
> >>  	while (node) {
> >>  		cm_id_priv = rb_entry(node, struct cm_id_private, service_node);
> >> -		if ((cm_id_priv->id.service_mask & service_id) ==
> >> -		     cm_id_priv->id.service_id &&
> >> -		    (cm_id_priv->id.device == device)) {
> >> -			refcount_inc(&cm_id_priv->refcount);
> >> -			return cm_id_priv;
> >> -		}
> >> +
> >>  		if (device < cm_id_priv->id.device)
> >>  			node = node->rb_left;
> >>  		else if (device > cm_id_priv->id.device)
> >>  			node = node->rb_right;
> >> +		else if ((cm_id_priv->id.service_mask & service_id) == cm_id_priv->id.service_id)
> >> +			goto found;
> >>  		else if (be64_lt(service_id, cm_id_priv->id.service_id))
> >>  			node = node->rb_left;
> >>  		else
> >>  			node = node->rb_right;
> >>  	}
> > 
> > This is not the pattern I showed you. Drop the first patch and rely on
> > the implicit equality in the final else.
> 
> Do you mean treate the "found" process as the else branch?
> 
> But ((cm_id_priv->id.service_mask & service_id) ==
> cm_id_priv->id.service_id) is different from (service_id ==
> cm_id_priv->id.service_id),I'm just worried that it might change
> the original logic.

The service_mask is always ~cpu_to_be64(0), it is some non-working
dead code that has been left in here.

If you really want to touch this then you should have a prep patch to
remove that entire API facet, then the above will make sense.

Jason

Re: [PATCH v2 2/2] RDMA/cm: Optimise rbtree searching

[Leizhen (ThunderTown)]

On 2021/5/12 22:26, Jason Gunthorpe wrote:
> On Wed, May 12, 2021 at 09:12:08PM +0800, Leizhen (ThunderTown) wrote:
>>
>>
>> On 2021/5/12 20:50, Jason Gunthorpe wrote:
>>> On Wed, May 12, 2021 at 06:05:37PM +0800, Zhen Lei wrote:
>>>>  static struct cm_id_private *cm_find_listen(struct ib_device *device,
>>>> @@ -686,22 +687,23 @@ static struct cm_id_private *cm_find_listen(struct ib_device *device,
>>>>  
>>>>  	while (node) {
>>>>  		cm_id_priv = rb_entry(node, struct cm_id_private, service_node);
>>>> -		if ((cm_id_priv->id.service_mask & service_id) ==
>>>> -		     cm_id_priv->id.service_id &&
>>>> -		    (cm_id_priv->id.device == device)) {
>>>> -			refcount_inc(&cm_id_priv->refcount);
>>>> -			return cm_id_priv;
>>>> -		}
>>>> +
>>>>  		if (device < cm_id_priv->id.device)
>>>>  			node = node->rb_left;
>>>>  		else if (device > cm_id_priv->id.device)
>>>>  			node = node->rb_right;
>>>> +		else if ((cm_id_priv->id.service_mask & service_id) == cm_id_priv->id.service_id)
>>>> +			goto found;
>>>>  		else if (be64_lt(service_id, cm_id_priv->id.service_id))
>>>>  			node = node->rb_left;
>>>>  		else
>>>>  			node = node->rb_right;
>>>>  	}
>>>
>>> This is not the pattern I showed you. Drop the first patch and rely on
>>> the implicit equality in the final else.
>>
>> Do you mean treate the "found" process as the else branch?
>>
>> But ((cm_id_priv->id.service_mask & service_id) ==
>> cm_id_priv->id.service_id) is different from (service_id ==
>> cm_id_priv->id.service_id),I'm just worried that it might change
>> the original logic.
> 
> The service_mask is always ~cpu_to_be64(0), it is some non-working
> dead code that has been left in here.
> 
> If you really want to touch this then you should have a prep patch to
> remove that entire API facet, then the above will make sense.

Okay, I'll try.

> 
> Jason
> 
> .
>