* [PATCH v2 0/2] RDMA/cm: Optimise rbtree searching
@ 2021-05-12 10:05 Zhen Lei
2021-05-12 10:05 ` [PATCH v2 1/2] RDMA/cm: Delete two redundant condition branches Zhen Lei
2021-05-12 10:05 ` [PATCH v2 2/2] RDMA/cm: Optimise rbtree searching Zhen Lei
0 siblings, 2 replies; 7+ messages in thread
From: Zhen Lei @ 2021-05-12 10:05 UTC (permalink / raw)
To: Doug Ledford, Jason Gunthorpe, Leon Romanovsky, linux-rdma; +Cc: 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
^ permalink raw reply [flat|nested] 7+ messages in thread
* [PATCH v2 1/2] RDMA/cm: Delete two redundant condition branches
2021-05-12 10:05 [PATCH v2 0/2] RDMA/cm: Optimise rbtree searching Zhen Lei
@ 2021-05-12 10:05 ` Zhen Lei
2021-05-12 10:05 ` [PATCH v2 2/2] RDMA/cm: Optimise rbtree searching Zhen Lei
1 sibling, 0 replies; 7+ messages in thread
From: Zhen Lei @ 2021-05-12 10:05 UTC (permalink / raw)
To: Doug Ledford, Jason Gunthorpe, Leon Romanovsky, linux-rdma; +Cc: 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
^ permalink raw reply related [flat|nested] 7+ messages in thread
* [PATCH v2 2/2] RDMA/cm: Optimise rbtree searching
2021-05-12 10:05 [PATCH v2 0/2] RDMA/cm: Optimise rbtree searching Zhen Lei
2021-05-12 10:05 ` [PATCH v2 1/2] RDMA/cm: Delete two redundant condition branches Zhen Lei
@ 2021-05-12 10:05 ` Zhen Lei
2021-05-12 12:50 ` Jason Gunthorpe
1 sibling, 1 reply; 7+ messages in thread
From: Zhen Lei @ 2021-05-12 10:05 UTC (permalink / raw)
To: Doug Ledford, Jason Gunthorpe, Leon Romanovsky, linux-rdma; +Cc: 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
^ permalink raw reply related [flat|nested] 7+ messages in thread
* Re: [PATCH v2 2/2] RDMA/cm: Optimise rbtree searching
2021-05-12 10:05 ` [PATCH v2 2/2] RDMA/cm: Optimise rbtree searching Zhen Lei
@ 2021-05-12 12:50 ` Jason Gunthorpe
2021-05-12 13:12 ` Leizhen (ThunderTown)
0 siblings, 1 reply; 7+ messages in thread
From: Jason Gunthorpe @ 2021-05-12 12:50 UTC (permalink / raw)
To: Zhen Lei; +Cc: Doug Ledford, Leon Romanovsky, linux-rdma
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
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH v2 2/2] RDMA/cm: Optimise rbtree searching
2021-05-12 12:50 ` Jason Gunthorpe
@ 2021-05-12 13:12 ` Leizhen (ThunderTown)
2021-05-12 14:26 ` Jason Gunthorpe
0 siblings, 1 reply; 7+ messages in thread
From: Leizhen (ThunderTown) @ 2021-05-12 13:12 UTC (permalink / raw)
To: Jason Gunthorpe; +Cc: Doug Ledford, Leon Romanovsky, linux-rdma
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
>
> .
>
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH v2 2/2] RDMA/cm: Optimise rbtree searching
2021-05-12 13:12 ` Leizhen (ThunderTown)
@ 2021-05-12 14:26 ` Jason Gunthorpe
2021-05-13 2:25 ` Leizhen (ThunderTown)
0 siblings, 1 reply; 7+ messages in thread
From: Jason Gunthorpe @ 2021-05-12 14:26 UTC (permalink / raw)
To: Leizhen (ThunderTown); +Cc: Doug Ledford, Leon Romanovsky, linux-rdma
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
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH v2 2/2] RDMA/cm: Optimise rbtree searching
2021-05-12 14:26 ` Jason Gunthorpe
@ 2021-05-13 2:25 ` Leizhen (ThunderTown)
0 siblings, 0 replies; 7+ messages in thread
From: Leizhen (ThunderTown) @ 2021-05-13 2:25 UTC (permalink / raw)
To: Jason Gunthorpe; +Cc: Doug Ledford, Leon Romanovsky, linux-rdma
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
>
> .
>
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2021-05-13 2:26 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-05-12 10:05 [PATCH v2 0/2] RDMA/cm: Optimise rbtree searching Zhen Lei
2021-05-12 10:05 ` [PATCH v2 1/2] RDMA/cm: Delete two redundant condition branches Zhen Lei
2021-05-12 10:05 ` [PATCH v2 2/2] RDMA/cm: Optimise rbtree searching Zhen Lei
2021-05-12 12:50 ` Jason Gunthorpe
2021-05-12 13:12 ` Leizhen (ThunderTown)
2021-05-12 14:26 ` Jason Gunthorpe
2021-05-13 2:25 ` Leizhen (ThunderTown)
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.