<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"> <head> <meta http-equiv="Content-Type" content="text/html; charset=us-ascii"> <meta name="Generator" content="Microsoft Word 15 (filtered medium)"> <style></style> </head> <body lang="EN-US" link="blue" vlink="purple"> <div class="WordSection1"> <p class="MsoNormal">Ok, will send a v2 version with description <o:p></o:p></p> <p class="MsoNormal"><o:p> </o:p></p> <div> <div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in"> <p class="MsoNormal"><b>From:</b> Deucher, Alexander <br> <b>Sent:</b> Saturday, November 24, 2018 3:34 AM<br> <b>To:</b> Zhu, Rex <Rex.Zhu@amd.com>; Liu, Monk <Monk.Liu@amd.com>; amd-gfx@lists.freedesktop.org<br> <b>Subject:</b> Re: [PATCH] drm: should break if already get the best size<o:p></o:p></p> </div> </div> <p class="MsoNormal"><o:p> </o:p></p> <div id="divtagdefaultwrapper"> <p><span style="font-size:12.0pt;color:black">Please add a proper patch description.<o:p></o:p></span></p> <p><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p> <p><span style="font-size:12.0pt;color:black">Alex<o:p></o:p></span></p> </div> <div class="MsoNormal" align="center" style="text-align:center"> <hr size="3" width="98%" align="center"> </div> <div id="divRplyFwdMsg"> <p class="MsoNormal"><b><span style="color:black">From:</span></b><span style="color:black"> amd-gfx <<a href="mailto:amd-gfx-bounces@lists.freedesktop.org">amd-gfx-bounces@lists.freedesktop.org</a>> on behalf of Zhu, Rex <<a href="mailto:Rex.Zhu@amd.com">Rex.Zhu@amd.com</a>><br> <b>Sent:</b> Friday, November 23, 2018 4:44:31 AM<br> <b>To:</b> Liu, Monk; <a href="mailto:amd-gfx@lists.freedesktop.org">amd-gfx@lists.freedesktop.org</a><br> <b>Subject:</b> Re: [PATCH] drm: should break if already get the best size</span> <o:p></o:p></p> <div> <p class="MsoNormal"> <o:p></o:p></p> </div> </div> <div> <div id="x_divtagdefaultwrapper"> <p><span style="font-size:12.0pt;color:black">Tested-by: Rex Zhu <<a href="mailto:Rex.Zhu@amd.com">Rex.Zhu@amd.com</a>><o:p></o:p></span></p> <p><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p> <p><span style="font-size:12.0pt;color:black">Without this patch, if we search node via rb tree.<o:p></o:p></span></p> <p><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p> <p><span style="font-size:12.0pt;color:black">For example: we insert 9999 different node with rand size, size range in (1-9999).<o:p></o:p></span></p> <p><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p> <p><span style="font-size:12.0pt;color:black">the key in root node is 5587.<o:p></o:p></span></p> <p><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p> <p><span style="font-size:12.0pt;color:black">if we try to find the node with key equal to 5587 or 7381,<o:p></o:p></span></p> <p><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p> <div> <div> <p class="MsoNormal"><span style="font-size:12.0pt;color:black">Loop:<br> node->key is </span><span style="font-size:12.0pt;color:red">5587</span><span style="font-size:12.0pt;color:black"><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<o:p></o:p></span></p> </div> </div> <p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p> <div> <p class="MsoNormal"><span style="font-size:12.0pt;color:black">Find the best node, key is </span><span style="font-size:12.0pt;color:red">5587 </span><i><span style="font-size:12.0pt;color:black">(Loop 14 levels)</span></i><span style="font-size:12.0pt;color:black"><o:p></o:p></span></p> </div> <p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p> <div> <p class="MsoNormal"><span style="font-size:12.0pt;color:black">Loop:<br> node->key is 5587<br> node->key is </span><i><span style="font-size:12.0pt;color:red">7381</span></i><span style="font-size:12.0pt;color:black"><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<o:p></o:p></span></p> </div> <div> <p class="MsoNormal"><span style="font-size:12.0pt;color:black"><br> find the best node, key is </span><i><span style="font-size:12.0pt;color:red">7381. </span></i><i><span style="font-size:12.0pt;color:black">(Loop 13 levels)</span></i><span style="font-size:12.0pt;color:black"><o:p></o:p></span></p> </div> <div> <p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p> </div> <div> <p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p> </div> <p><span style="font-size:12.0pt;color:black">With this patch:<o:p></o:p></span></p> <p><span style="font-size:12.0pt;color:black">we don't need to go down if we found the right node that size equal to we needed. <o:p></o:p></span></p> <p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p> <div> <div> <p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p> </div> <p class="MsoNormal"><span style="font-size:12.0pt;color:black"><br> Best Regards<o:p></o:p></span></p> </div> <div> <p class="MsoNormal"><span style="font-size:12.0pt;color:black">Rex <o:p></o:p></span></p> </div> <p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p> <div> <div class="MsoNormal" align="center" style="text-align:center"><span style="font-size:12.0pt;color:black"> <hr size="3" width="98%" align="center"> </span></div> <div id="x_divRplyFwdMsg"> <p class="MsoNormal"><b><span style="color:black">From:</span></b><span style="color:black"> amd-gfx <<a href="mailto:amd-gfx-bounces@lists.freedesktop.org">amd-gfx-bounces@lists.freedesktop.org</a>> on behalf of Monk Liu <<a href="mailto:Monk.Liu@amd.com">Monk.Liu@amd.com</a>><br> <b>Sent:</b> Thursday, November 22, 2018 8:33 PM<br> <b>To:</b> <a href="mailto:amd-gfx@lists.freedesktop.org">amd-gfx@lists.freedesktop.org</a><br> <b>Cc:</b> Liu, Monk<br> <b>Subject:</b> [PATCH] drm: should break if already get the best size</span><span style="font-size:12.0pt;color:black"> <o:p></o:p></span></p> <div> <p class="MsoNormal"><span style="font-size:12.0pt;color:black"> <o:p></o:p></span></p> </div> </div> <div> <div> <p class="MsoNormal"><span style="color:black">Signed-off-by: Monk Liu <<a href="mailto:Monk.Liu@amd.com">Monk.Liu@amd.com</a>><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> <a href="mailto:amd-gfx@lists.freedesktop.org">amd-gfx@lists.freedesktop.org</a><br> <a href="https://lists.freedesktop.org/mailman/listinfo/amd-gfx">https://lists.freedesktop.org/mailman/listinfo/amd-gfx</a> <o:p></o:p></span></p> <div style="margin-bottom:15.0pt;overflow:auto" id="LPBorder_GT_15429546487490.27167628664524557"> <table class="MsoNormalTable" border="1" cellspacing="0" cellpadding="0" width="90%" style="width:90.0%;background:white;border-top:dotted #C8C8C8 1.0pt;border-left:none;border-bottom:dotted #C8C8C8 1.0pt;border-right:none"> <tbody> <tr> <td valign="top" style="border:none;padding:0in 0in 0in 0in"> <div id="LPTitle_15429546487480.227571535890579"> <p class="MsoNormal" style="margin-top:15.0pt;mso-line-height-alt:15.75pt"><span style="font-size:16.0pt;font-family:"Segoe UI Light",sans-serif;color:#0078D7"><a href="https://lists.freedesktop.org/mailman/listinfo/amd-gfx" target="_blank"><span style="text-decoration:none">amd-gfx Info Page - freedesktop.org</span></a><o:p></o:p></span></p> </div> <div style="margin-top:7.5pt;margin-bottom:12.0pt" id="LPMetadata_15429546487490.8445715815323509"> <p class="MsoNormal" style="margin-top:15.0pt;line-height:10.5pt"><span style="font-size:10.5pt;font-family:"Segoe UI",sans-serif;color:#666666">lists.freedesktop.org<o:p></o:p></span></p> </div> <div id="LPDescription_15429546487490.22150885879568194"> <p class="MsoNormal" style="margin-top:15.0pt;line-height:15.0pt"><span style="font-size:10.5pt;font-family:"Segoe UI",sans-serif;color:#666666">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 <a href="mailto:amd-gfx@lists.freedesktop.org"> amd-gfx@lists.freedesktop.org</a>. You can subscribe to the list, or change your existing subscription, in the sections below.<o:p></o:p></span></p> </div> </td> </tr> </tbody> </table> </div> <p class="MsoNormal"><span style="color:black"><o:p> </o:p></span></p> </div> </div> </div> </div> </div> </div> </body> </html>