drm: should break if already get the best size

Commit Message

Liu, Monk Nov. 23, 2018, 8:02 a.m. UTC

-----Original Message-----
From: amd-gfx <[e-mail]> On Behalf Of Monk Liu
Sent: Thursday, November 22, 2018 8:33 PM
To: [e-mail]
Cc: Liu, Monk <[e-mail]>
Subject: [PATCH] drm: should break if already get the best size

Signed-off-by: Monk Liu <[e-mail]>
---
 drivers/gpu/drm/drm_mm.c | 2 ++
 1 file changed, 2 insertions(+)

--
2.7.4

Comments

Chris Wilson Nov. 23, 2018, 9:03 a.m. UTC | #1

Quoting Liu, Monk (2018-11-23 08:02:11)
> 
> 
> -----Original Message-----
> From: amd-gfx <[e-mail]> On Behalf Of Monk Liu
> Sent: Thursday, November 22, 2018 8:33 PM
> To: [e-mail]
> Cc: Liu, Monk <[e-mail]>
> Subject: [PATCH] drm: should break if already get the best size
> 
> Signed-off-by: Monk Liu <[e-mail]>
> ---
>  drivers/gpu/drm/drm_mm.c | 2 ++
>  1 file changed, 2 insertions(+)
> 
> diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index 3cc5fbd..369fd9b 100644
> --- a/drivers/gpu/drm/drm_mm.c
> +++ b/drivers/gpu/drm/drm_mm.c
> @@ -318,6 +318,8 @@ static struct drm_mm_node *best_hole(struct drm_mm *mm, u64 size)
>                 if (size <= node->hole_size) {
>                         best = node;
>                         rb = rb->rb_right;
> +                       if (size == node->hole_size)
> +                               break;

No. The point is to find the first in the chain that matches because not
every node is suitable. By not checking all best_sizes you may end up
skipping the perfect match.
-Chris

Liu, Monk Nov. 23, 2018, 9:11 a.m. UTC | #2

What do you mean the first in the chain ? and also can you explain the " perfect match." ? thanks 

Assume there is couple nodes equal to the size you requested, without this patch it will traveler to the bottom level of the RB tree and gives you
the node that close to the bottom level, which takes more time compared with break on the first node, but anyway you eventually get the node with the same size 

if there is no node that equal to the size you requested, without or with my patch the logic is totally the same.

/Monk
-----Original Message-----
From: Chris Wilson <[e-mail]> 
Sent: Friday, November 23, 2018 5:03 PM
To: Liu, Monk <[e-mail]>; [e-mail]
Subject: Re: FW: [PATCH] drm: should break if already get the best size

Quoting Liu, Monk (2018-11-23 08:02:11)
> 
> 
> -----Original Message-----
> From: amd-gfx <[e-mail]> On Behalf Of 
> Monk Liu
> Sent: Thursday, November 22, 2018 8:33 PM
> To: [e-mail]
> Cc: Liu, Monk <[e-mail]>
> Subject: [PATCH] drm: should break if already get the best size
> 
> Signed-off-by: Monk Liu <[e-mail]>
> ---
>  drivers/gpu/drm/drm_mm.c | 2 ++
>  1 file changed, 2 insertions(+)
> 
> diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index 
> 3cc5fbd..369fd9b 100644
> --- a/drivers/gpu/drm/drm_mm.c
> +++ b/drivers/gpu/drm/drm_mm.c
> @@ -318,6 +318,8 @@ static struct drm_mm_node *best_hole(struct drm_mm *mm, u64 size)
>                 if (size <= node->hole_size) {
>                         best = node;
>                         rb = rb->rb_right;
> +                       if (size == node->hole_size)
> +                               break;

No. The point is to find the first in the chain that matches because not every node is suitable. By not checking all best_sizes you may end up skipping the perfect match.
-Chris

Chris Wilson Nov. 23, 2018, 9:34 a.m. UTC | #3

Quoting Liu, Monk (2018-11-23 09:11:02)
> What do you mean the first in the chain ? and also can you explain the " perfect match." ? thanks 
> 
> Assume there is couple nodes equal to the size you requested, without this patch it will traveler to the bottom level of the RB tree and gives you
> the node that close to the bottom level, which takes more time compared with break on the first node, but anyway you eventually get the node with the same size 

Size is but of one many checks the node must pass before being returned.
-Chris

Liu, Monk Nov. 23, 2018, 9:39 a.m. UTC | #4

There is no checks at all in this best_hole() ... can you review the patch again ?

/Monk
-----Original Message-----
From: Chris Wilson <[e-mail]> 
Sent: Friday, November 23, 2018 5:34 PM
To: Liu, Monk <[e-mail]>; [e-mail]
Subject: RE: FW: [PATCH] drm: should break if already get the best size

Quoting Liu, Monk (2018-11-23 09:11:02)
> What do you mean the first in the chain ? and also can you explain the 
> " perfect match." ? thanks
> 
> Assume there is couple nodes equal to the size you requested, without 
> this patch it will traveler to the bottom level of the RB tree and 
> gives you the node that close to the bottom level, which takes more 
> time compared with break on the first node, but anyway you eventually 
> get the node with the same size

Size is but of one many checks the node must pass before being returned.
-Chris

Chunming Zhou Nov. 23, 2018, 2:28 p.m. UTC | #5

Totally find to me, but can we change it a bit like:

  		if (size < node->hole_size) {
  			best = node;
  			rb = rb->rb_right;
  		} else if (size > node->hole_size){
  			rb = rb->rb_left;
  		} else {
			break;
		}


-David

在 2018/11/23 16:02, Liu, Monk 写道:
>
> -----Original Message-----
> From: amd-gfx <[e-mail]> On Behalf Of Monk Liu
> Sent: Thursday, November 22, 2018 8:33 PM
> To: [e-mail]
> Cc: Liu, Monk <[e-mail]>
> Subject: [PATCH] drm: should break if already get the best size
>
> Signed-off-by: Monk Liu <[e-mail]>
> ---
>   drivers/gpu/drm/drm_mm.c | 2 ++
>   1 file changed, 2 insertions(+)
>
> diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index 3cc5fbd..369fd9b 100644
> --- a/drivers/gpu/drm/drm_mm.c
> +++ b/drivers/gpu/drm/drm_mm.c
> @@ -318,6 +318,8 @@ static struct drm_mm_node *best_hole(struct drm_mm *mm, u64 size)
>   		if (size <= node->hole_size) {
>   			best = node;
>   			rb = rb->rb_right;
> +			if (size == node->hole_size)
> +				break;
>   		} else {
>   			rb = rb->rb_left;
>   		}
> --
> 2.7.4
>
> _______________________________________________
> amd-gfx mailing list
> [e-mail]
> https://lists.freedesktop.org/mailman/listinfo/amd-gfx
> _______________________________________________
> dri-devel mailing list
> [e-mail]
> https://lists.freedesktop.org/mailman/listinfo/dri-devel

Patch

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index 3cc5fbd..369fd9b 100644
--- a/drivers/gpu/drm/drm_mm.c
+++ b/drivers/gpu/drm/drm_mm.c
@@ -318,6 +318,8 @@  static struct drm_mm_node *best_hole(struct drm_mm *mm, u64 size)
 		if (size <= node->hole_size) {
 			best = node;
 			rb = rb->rb_right;
+			if (size == node->hole_size)
+				break;
 		} else {
 			rb = rb->rb_left;
 		}