<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" style="display:none;"><!-- P {margin-top:0;margin-bottom:0;} --></style>
</head>
<body dir="ltr">
<div id="divtagdefaultwrapper" dir="ltr" style="font-size: 12pt; color: rgb(0, 0, 0); font-family: Calibri, Helvetica, sans-serif, "EmojiFont", "Apple Color Emoji", "Segoe UI Emoji", NotoColorEmoji, "Segoe UI Symbol", "Android Emoji", EmojiSymbols;">
<p style="margin-top:0; margin-bottom:0">Tested-by: <span>Rex Zhu <Rex.Zhu@amd.com></span></p>
<p style="margin-top:0; margin-bottom:0"><span><br>
</span></p>
<p style="margin-top:0; margin-bottom:0"><span>Without this patch, if we search node via rb tree.</span></p>
<p style="margin-top:0; margin-bottom:0"><span><br>
</span></p>
<p style="margin-top:0; margin-bottom:0"><span>For example: we insert 9999 different node with rand size, size range in (1-9999).</span></p>
<p style="margin-top:0; margin-bottom:0"><span><br>
</span></p>
<p style="margin-top:0; margin-bottom:0"><span><span>the key in root node is 5587</span>.</span></p>
<p style="margin-top:0; margin-bottom:0"><span><br>
</span></p>
<p style="margin-top:0; margin-bottom:0"><span>if we try to find the node with key equal to 5587 or
<span id="ms-rterangepaste-start"></span><span>7381</span><span id="ms-rterangepaste-end"></span>,</span></p>
<p style="margin-top:0; margin-bottom:0"><span><br>
</span></p>
<p style="margin-top:0; margin-bottom:0"><span></span><span></span></p>
<div>
<div>Loop:<br>
node->key is <span style="color:rgb(255,0,0)">5587</span><br>
node->key is 2273<br>
node->key is 3706<br>
node->key is 4892<br>
node->key is 5296<br>
node->key is 5461<br>
node->key is 5519<br>
node->key is 5549<br>
node->key is 5570<br>
node->key is 5581<br>
node->key is 5584<br>
node->key is 5585<br>
node->key is 5586<br>
node->key is 5586</div>
</div>
<br>
<p></p>
<p style="margin-top:0; margin-bottom:0"><span></span></p>
<div>Find the best node, key is <span style="color:rgb(255,0,0)">5587 <span style="color: rgb(255, 0, 0);">
<i><span style="color: rgb(0, 0, 0);">(Loop 14 levels)</span></i></span></span></div>
<br>
<p></p>
<div>Loop:<br>
node->key is 5587<br>
node->key is <i><span style="color: rgb(255, 0, 0);">7381</span></i><br>
node->key is 6474<br>
node->key is 7034<br>
node->key is 7228<br>
node->key is 7314<br>
node->key is 7339<br>
node->key is 7349<br>
node->key is 7372<br>
node->key is 7377<br>
node->key is 7378<br>
node->key is 7379<br>
node->key is 7379</div>
<div><br>
find the best node, key is <span style="color: rgb(255, 0, 0);"><i>7381. <span style="color: rgb(0, 0, 0);">
(Loop 13 levels)</span></i></span></div>
<div><br>
</div>
<div><br>
</div>
<div></div>
<p></p>
<p style="margin-top:0; margin-bottom:0"><span>With this patch:</span></p>
<p style="margin-top:0; margin-bottom:0"><span>we don't need to go down if we found the right node that size equal to we needed.
<br>
</span></p>
<span style="color:rgb(255,0,0)"></span><br>
<div>
<div><br>
</div>
<br>
Best Regards</div>
<div>Rex </div>
<br>
<div style="color:rgb(0,0,0)">
<hr tabindex="-1" style="display:inline-block; width:98%">
<div id="divRplyFwdMsg" dir="ltr"><font style="font-size:11pt" face="Calibri, sans-serif" color="#000000"><b>From:</b> amd-gfx <amd-gfx-bounces@lists.freedesktop.org> on behalf of Monk Liu <Monk.Liu@amd.com><br>
<b>Sent:</b> Thursday, November 22, 2018 8:33 PM<br>
<b>To:</b> amd-gfx@lists.freedesktop.org<br>
<b>Cc:</b> Liu, Monk<br>
<b>Subject:</b> [PATCH] drm: should break if already get the best size</font>
<div> </div>
</div>
<div class="BodyFragment"><font size="2"><span style="font-size:11pt">
<div class="PlainText">Signed-off-by: Monk Liu <Monk.Liu@amd.com><br>
---<br>
drivers/gpu/drm/drm_mm.c | 2 ++<br>
1 file changed, 2 insertions(+)<br>
<br>
diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c<br>
index 3cc5fbd..369fd9b 100644<br>
--- a/drivers/gpu/drm/drm_mm.c<br>
+++ b/drivers/gpu/drm/drm_mm.c<br>
@@ -318,6 +318,8 @@ static struct drm_mm_node *best_hole(struct drm_mm *mm, u64 size)<br>
if (size <= node->hole_size) {<br>
best = node;<br>
rb = rb->rb_right;<br>
+ if (size == node->hole_size)<br>
+ break;<br>
} else {<br>
rb = rb->rb_left;<br>
}<br>
-- <br>
2.7.4<br>
<br>
_______________________________________________<br>
amd-gfx mailing list<br>
amd-gfx@lists.freedesktop.org<br>
<a href="https://lists.freedesktop.org/mailman/listinfo/amd-gfx" id="LPlnk760696" class="OWAAutoLink" previewremoved="true">https://lists.freedesktop.org/mailman/listinfo/amd-gfx</a>
<div id="LPBorder_GT_15429546487490.27167628664524557" style="margin-bottom:20px; overflow:auto; width:100%; text-indent:0px">
<table id="LPContainer_15429546487480.43424038956412636" role="presentation" style="width:90%; background-color:rgb(255,255,255); overflow:auto; padding-top:20px; padding-bottom:20px; margin-top:20px; border-top:1px dotted rgb(200,200,200); border-bottom:1px dotted rgb(200,200,200)" cellspacing="0">
<tbody>
<tr style="border-spacing:0px" valign="top">
<td id="TextCell_15429546487480.3675019534019166" colspan="2" style="vertical-align: top; padding: 0px; display: table-cell; position: relative;">
<div id="LPRemovePreviewContainer_15429546487480.5161007281621218"></div>
<div id="LPTitle_15429546487480.227571535890579" style="top:0px; color:rgb(0,120,215); font-weight:400; font-size:21px; font-family:"wf_segoe-ui_light","Segoe UI Light","Segoe WP Light","Segoe UI","Segoe WP",Tahoma,Arial,sans-serif; line-height:21px">
<a id="LPUrlAnchor_15429546487490.48298712321952375" href="https://lists.freedesktop.org/mailman/listinfo/amd-gfx" target="_blank" style="text-decoration:none">amd-gfx Info Page - freedesktop.org</a></div>
<div id="LPMetadata_15429546487490.8445715815323509" style="margin:10px 0px 16px; color:rgb(102,102,102); font-weight:400; font-family:"wf_segoe-ui_normal","Segoe UI","Segoe WP",Tahoma,Arial,sans-serif; font-size:14px; line-height:14px">
lists.freedesktop.org</div>
<div id="LPDescription_15429546487490.22150885879568194" style="display:block; color:rgb(102,102,102); font-weight:400; font-family:"wf_segoe-ui_normal","Segoe UI","Segoe WP",Tahoma,Arial,sans-serif; font-size:14px; line-height:20px; max-height:100px; overflow:hidden">
To see the collection of prior postings to the list, visit the amd-gfx Archives.. Using amd-gfx: To post a message to all the list members, send email to amd-gfx@lists.freedesktop.org. You can subscribe to the list, or change your existing subscription, in
the sections below.</div>
</td>
</tr>
</tbody>
</table>
</div>
<br>
</div>
</span></font></div>
</div>
</div>
</body>
</html>