drm: should break if already get the best size

Commit Message

Liu, Monk Nov. 23, 2018, 9:49 a.m. UTC

Hi Chris

Please check the sanity test of the patch from Rex

/Monk
From: Zhu, Rex
Sent: Friday, November 23, 2018 5:45 PM
To: Liu, Monk <[e-mail]>; [e-mail]
Subject: Re: [PATCH] drm: should break if already get the best size


Tested-by: Rex Zhu <[e-mail]<mailto:[e-mail]>>



Without this patch, if we search node via rb tree.



For example: we insert 9999 different node with rand size, size range in (1-9999).



the key in root node is 5587.



if we try to find the node with key equal to 5587 or 7381,


Loop:
node->key is 5587
node->key is 2273
node->key is 3706
node->key is 4892
node->key is 5296
node->key is 5461
node->key is 5519
node->key is 5549
node->key is 5570
node->key is 5581
node->key is 5584
node->key is 5585
node->key is 5586
node->key is 5586

Find the best node, key is 5587 (Loop 14 levels)

Loop:
node->key is 5587
node->key is 7381
node->key is 6474
node->key is 7034
node->key is 7228
node->key is 7314
node->key is 7339
node->key is 7349
node->key is 7372
node->key is 7377
node->key is 7378
node->key is 7379
node->key is 7379

find the best node, key is 7381. (Loop 13 levels)



With this patch:

we don't need to go down if we found the right node that size equal to we needed.



Best Regards
Rex

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