From patchwork Mon Nov 26 07:44:16 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Liu, Monk" X-Patchwork-Id: 10697645 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 2D35E13AD for ; Mon, 26 Nov 2018 07:44:29 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 1257A28AAF for ; Mon, 26 Nov 2018 07:44:29 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id E1E5329072; Mon, 26 Nov 2018 07:44:28 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-5.2 required=2.0 tests=BAD_ENC_HEADER,BAYES_00, MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED autolearn=ham version=3.3.1 Received: from gabe.freedesktop.org (gabe.freedesktop.org [131.252.210.177]) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id 24FEE28AAF for ; Mon, 26 Nov 2018 07:44:28 +0000 (UTC) Received: from gabe.freedesktop.org (localhost [127.0.0.1]) by gabe.freedesktop.org (Postfix) with ESMTP id 26DAF6E2C4; Mon, 26 Nov 2018 07:44:26 +0000 (UTC) X-Original-To: dri-devel@lists.freedesktop.org Delivered-To: dri-devel@lists.freedesktop.org Received: from NAM02-BL2-obe.outbound.protection.outlook.com (mail-eopbgr750050.outbound.protection.outlook.com [40.107.75.50]) by gabe.freedesktop.org (Postfix) with ESMTPS id EC41A6E2C4 for ; Mon, 26 Nov 2018 07:44:24 +0000 (UTC) Received: from DM3PR12CA0094.namprd12.prod.outlook.com (2603:10b6:0:55::14) by CY1PR12MB0427.namprd12.prod.outlook.com (2a01:111:e400:5191::17) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1361.14; Mon, 26 Nov 2018 07:44:22 +0000 Received: from BY2NAM03FT019.eop-NAM03.prod.protection.outlook.com (2a01:111:f400:7e4a::202) by DM3PR12CA0094.outlook.office365.com (2603:10b6:0:55::14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384) id 15.20.1361.14 via Frontend Transport; Mon, 26 Nov 2018 07:44:21 +0000 Received-SPF: None (protection.outlook.com: amd.com does not designate permitted sender hosts) Received: from SATLEXCHOV02.amd.com (165.204.84.17) by BY2NAM03FT019.mail.protection.outlook.com (10.152.84.221) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384) id 15.20.1339.10 via Frontend Transport; Mon, 26 Nov 2018 07:44:21 +0000 Received: from monk-build.amd.com (10.34.1.3) by SATLEXCHOV02.amd.com (10.181.40.72) with Microsoft SMTP Server id 14.3.389.1; Mon, 26 Nov 2018 01:44:20 -0600 From: Monk Liu To: Subject: [PATCH] drm: should break if already found the best size(v2) Date: Mon, 26 Nov 2018 15:44:16 +0800 Message-ID: <1543218256-3829-1-git-send-email-Monk.Liu@amd.com> X-Mailer: git-send-email 2.7.4 MIME-Version: 1.0 X-EOPAttributedMessage: 0 X-MS-Office365-Filtering-HT: Tenant X-Forefront-Antispam-Report: CIP:165.204.84.17; IPV:NLI; CTRY:US; EFV:NLI; SFV:NSPM; SFS:(10009020)(346002)(39860400002)(376002)(136003)(396003)(2980300002)(428003)(189003)(199004)(486006)(16586007)(8936002)(8676002)(81156014)(81166006)(2906002)(426003)(126002)(2616005)(4326008)(104016004)(476003)(53936002)(26005)(68736007)(305945005)(316002)(86362001)(50226002)(6666004)(356004)(336012)(6916009)(186003)(105586002)(48376002)(5660300001)(53416004)(50466002)(106466001)(97736004)(51416003)(2351001)(7696005)(478600001)(36756003)(1857600001)(47776003)(72206003)(77096007); DIR:OUT; SFP:1101; SCL:1; SRVR:CY1PR12MB0427; H:SATLEXCHOV02.amd.com; FPR:; SPF:None; LANG:en; PTR:InfoDomainNonexistent; MX:1; A:1; X-Microsoft-Exchange-Diagnostics: 1; BY2NAM03FT019; 1:ULrfkl5zsD8pS8tDn41lsvqYBgwffkHnkWeSKSBOwvgM14YEwPNq8Z3bAWJvYAI30oWiegfKm1k1ZozoLopZtfR72XUBVikXJZMMQ+cn7xyullzUKei7H89Yf17Saqii X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: a53610b0-e9c0-40b0-9cef-08d65372faa4 X-Microsoft-Antispam: BCL:0; PCL:0; RULEID:(2390098)(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600074)(711020)(2017052603328)(7153060); SRVR:CY1PR12MB0427; X-Microsoft-Exchange-Diagnostics: 1; CY1PR12MB0427; 3:/ehyMq6Yr5b+RaEibWxBSIUQkx0ptXUzdz4lU4c7dfQBz+T/wbWy+6gwrPXoh1Sd3l3dXht1WhsD/ybxf8iQjVzcL7COZ9acv1LMNye9novUsecyaKRDXzXHtM38fHLvl5GaBAxH+cWwsXdJXDEl6BeuY1gOnEE5llvxkrauz7kKtjpj404LYE0Fiaa88CMVVpoT/x0mY2ZQIEg/JzBp+5Yyde/BKNBKYmpkW3mIu6cnAJfIutASnnrDFjfxWUXc/wd67iNWwcs0BEnB9sDrHlGXevNuAzJvDnEMaSrwXraOCG1eKtgUm8EpgbGT4bDRZf+6NiSGgfKNEQSCRCSu4ar20UweBZALWcsmrccdJ1g=; 25:Z4hAQSRwkirTnAtbt+0kuPVLp81FPVTEoiVzuusbOvM5D/c9m00bCExNUeqiAfBESH6FQixZbexZgrS4/TpAFf254ENYefMRtRTvVVUYvvoSzwZZ7h2OPL59YdHAi/jswcnuQRlSvhycWvdoQNacoud1JT5MrvgLeW6HGU+euEj0+53mCkfmVfIX953wtGXt7deMLxma+l6Tl8BVLJwNiH8dUrYU7Iuuw8LwDOr/U9XbeaX+AA1KJO3lar2nHAXLSP577pSkSh3/RXK6cIDAmdY6rrQAnXhtbWZrKj4QfKxK++wqvc3uBMlml9KAuSVh+cs2j1MNoa+PsBCl0mHpErmNTIpwsS92yRnRdWaZG3o= X-MS-TrafficTypeDiagnostic: CY1PR12MB0427: X-Microsoft-Exchange-Diagnostics: 1; CY1PR12MB0427; 31:n6iIbBFmdFZu0HhQi3GV0dqfHY7V4ldDLRTdYpPfe2Y96r1dSlnsjUC1/V//2OfKQoof8W8VzWDxPRgoiwb3K6abFwv8JLBlC753J4RWK5nEPhPgplnLH+2TzXlV7Gny3czinZcV7aFJdxTNsSs99p3LGctWQQP1kPgF6k6bH71oWeUJpu4jSNYbSPRaWlak8o2UNKR9k+fZGkwyniyAiIKCzT+jTfvZFJjPwLUBgzs=; 20:RXNuVg5fdUwyIGgxIe1XT54gvcs8gRnagvkitF/tHYkIhkqHRXLMM6ppEHh5RWxDeOfv6PPyiYgSODxkSnpTGl1+8urAdYBPlxqVZUslfKIO/mEZ6WkQudi4FZZBJ6jrJxmu5Smoys8VaascDrBJA9hnBEc3fC/aaVv2WzuZ7u8wa5r25IR7IdA9fqdzuwvbTkIsXzNJ5YPEhBr0ScSiI5PzFn5wsSCzzhM9mkY+dxbqBtc3M+1fqid3VXnyF+QyUsu4nQHV/jOWa3XHj453dErbkvrxJk3cisf2WH0tr0AXUfM+1eIAIhh2ZiKM+emvlbJxXA5wpBoCvJGN+gXfRZSv1dxYCW9QRtWQL0DQJgULTVDNHVfb94qi8oCDM8Ybytedm7J/M5lQxrmsC6QBC5uhyvS96on06M/IRuvgNNg5aIygPMQrc0z0vfUr1lrYF2MdaVjizoQ2khUowl3z6yEPD/BKeSknbITEkspaWh8e62KF5OLPGjiFbIU/ZqzU X-Microsoft-Antispam-PRVS: X-MS-Exchange-SenderADCheck: 1 X-Exchange-Antispam-Report-CFA-Test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(8121501046)(5005006)(10201501046)(93006095)(93003095)(3002001)(3231443)(944501410)(52105112)(6055026)(148016)(149066)(150057)(6041310)(20161123558120)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123560045)(20161123564045)(20161123562045)(201708071742011)(7699051)(76991095); SRVR:CY1PR12MB0427; BCL:0; PCL:0; RULEID:; SRVR:CY1PR12MB0427; X-Microsoft-Exchange-Diagnostics: 1; CY1PR12MB0427; 4:WRen7Zbbt3RehmZCcPMVjG3CZwOb03fI/Wices6Tpc2kHCQRlqCdC4bYur17FeWwjxK3HlFxRarzJNlKY2cjMARt+aEurOQ+MMoNnYqFgphcVupJMPDHxFq1w7PKtvjifj04tG0Qu7CAsmhbISfFURQ8JKAUnCyGKtqSLhUVzQ/3eh22ftgtWzz3JT/FGe+NoMb1DVPltIHG7APhMotOfcI4ocdKxyqnrJTrOIlK5MCLm1ps5A3pSJczL6eiEAWnuGepdk+FA88pUMqV/9wSMA== X-Forefront-PRVS: 086831DFB4 X-Microsoft-Exchange-Diagnostics: =?us-ascii?Q?1; CY1PR12MB0427; 23:AgmMu5jvHLINuDVgdPaZIFkI/jrWudTSju6YrHpwz?= PiauyN+0NCri/dd2UTeCDsoecxF/sUREz2SsJSdXyd6dUJTQip6JL+4M7dJfiZnG+JypGo8ka4+16gPZqwthmHeSK7TyYnQlAIPoKbd343Jn1wu6875JxexR5y3uv2pmEu6SkWTDtMvXMSPf0lafmpTn+CgHR9vRnBQFzd1fIpftZ7R6J41yKlF72epyr0UZqDyA10njVuiFohHme2RgLpXDEQz+8GqIhaP81Wigj2EjH75Kl8PwxFm42wmgaCpy6stT0WmHDhVQqVTxIqcevkCj54suyxAD2JUykJ7Rwh7J56cnM0f7yYN5QMxBTYSiJ5e9G34603HF/PJOgVR7qJJNeNgeaYTbFgS62ahZTBSQRLN4xPUN1XNB84IZOnbhWk/ud6PRadNcVIgtFSCUvNIlnBMXzfFx/2MgBQOOW0y4VJQBW6+bodxWjDupFgIs1EJOP1GAXjMQ7c1tM5LW9YUkCBAUXX+IvMv2MX/8iBPPNvBZKYQlbCpE6kSgTxiwKV2qTY/4iGKpibqTwGRtTdtsVLn3rFCZE9tlLTRAgU+Cr6i4NXzU1sleVEVvuBcky2Hl6SPeXcGG8ipp3X6SPCkyOIsxZCgcOf60VHhIfqHtN6NKAivPJkTVkHxMPpZb21QKESwZ/ZuI1QrlF6Lf/6dwc4uE23a6hzJQNOTlPLq00y9I4TGKZmpSSoREX6KdzZ/4IqJQSnl+xZut4dmJi9wIqYlELEaqKj2pCZmEpYd7L7cR8J4n21ERK2L90qahLea8+V9hSxB21WJwEqisL8blTo9H6TRhgfVeyPuZ831Ao/Jn937Kd9Voc8GkWRzhyoQ+yef5zpz0Ml8fMJUnTeUgdBHmLxlRYa1lwgakycQFRArRuzoubRp8NqLJIVSp8EkGr/2OLnWZ4N5xD8l0RFNDrtwZo6UDTfqAl7AEivvghGzawAzEQC1Gxnasp8Hv1WJiAsgN8qtCVYsJ0g1ClF6AzCuaMvGTJIT0iebDCfRmMjGdjP7qi6D1gB/cehjjYv1PTAH/9Ta6AOcjUE9bCLZY/RC6+2Gch6KoZFMhvqewGdfbSp2GxVhKG08uEULonc= X-Microsoft-Antispam-Message-Info: dd0Co1TMsj+GJLDMSEUWlrRo9CYDa3RbFk/q+ciTS6GzSwE+O1eWMgdCWWnRaBtZ5jqG4moMlcBIOEU1ep+jsVR85JcS1nbiJuFUEXMEhIqwU2Q3sc+83GrSKG5MYN/BErw863RtFonBSIWJe3Mgv3VFlQpgK45Zd6JbmqHZ/LebYE01KBs0/z4wppAp/BxYhgNsvPmqQiu6oaboU0Tk6SLhMn6bk/NcoBeaNtKixaGjsp45ZXyoWpiABd2aTPezcJG5Tyd8VprhdipsVyGlnCniPJ46usZz3M61TWWxu3Vt0AxyUaHMTPgrzjfJhiD7+ofrVFYOkGkM2BLT45xEEewrUV20yRtAXsCXigOovZE= X-Microsoft-Exchange-Diagnostics: 1; CY1PR12MB0427; 6:mH/OPb06rJYeVrFjAAUr76NnNh9g6lxxBHOnrFcSOImkMiQVipKttnaQA8UVl2fPw5c3u1k9BOjuD28TYCIPBBPSFO8jJElCeN4ajqL2bz/sSNcq6svZOdb/t24Dtrlag1MkKlNDKTwkf9U2w8xutWJi9Dkg3MniYjb2852sG+B/rJnuwZOEDcUIp/myq8UDZi9CNY8rT/j/jHp7u0Htuuh2U66YqiTH4G9MzMk3ZxRJWkjAf722vIypIImz2paxm//VtnD25t/fNvlYq8ppzcbiJG4E4d0P1mfqrxvlmasjgnswrih5s2WLAdJCnENo1+98H32DlJCfYPDy8k1CBmckDQiE9WesiYi2k3WZAQv8zI/1iCYgb586erZDq2+wRcrxl8CIrn7AnFlCF1gzrLsoVRz+VdFZNLPtOquEGJ+jUsfzNgeL+Nvfz1CWJ+zVh32dLUh+nYY4IzPiWfx2eg==; 5:kkCe/KrFGZyd7vn58VpDtLgbhdo3GGw/oi7zW8IDUAsxNRzBk6rz8woLROPHfzPMhPuFKds4suabVBkrelILxcCf8WOl8Ocy4fKfCfywcl5Hd0JJtcZ4e5tAq791U08qPVoBUxDxOZyNeLdtL8Vly4Ix/IuTZ2hBOmBzH6QzOQc=; 7:C/43c9Jxr0QU94rXC28K44gWtGdSz+pz3JnocG/arvvs+hu4pQpzQfZ7lvsk2wZbBoEGt6oWGwz/LJtQDGTaLBJ1LNawQLkAgvIApfyvQODu4ZvVdpU/hgCFx5gJ4aWEZNeqdN9sP2VEGVRvLjki4A== SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-Microsoft-Exchange-Diagnostics: 1; CY1PR12MB0427; 20:3MR8HSit2QXx65jmSwjgFdNpXyhcLcEwUQkMmZc0fsv5K195xU4Ea0WuF2f6koI7HPLBQN50vO1ViXu+hSjx7jthqNAbvrgwQo2roVDw7EJcBweteThPJ3FtJhq+zdWEoz8VpfqsDOBNPjcnR6WiCIggfkwIea9NSIANz5TUW3eBKeRlQIOja5QxyJjhFE0G9hd1+OKQAb/Kg/7AwMnjeW6bRyh6UXRKhsnbNVAjh07FvB6YNlOEj6M+KUBKxDFT X-OriginatorOrg: amd.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 26 Nov 2018 07:44:21.2848 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: a53610b0-e9c0-40b0-9cef-08d65372faa4 X-MS-Exchange-CrossTenant-Id: 3dd8961f-e488-4e60-8e11-a82d994e183d X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=3dd8961f-e488-4e60-8e11-a82d994e183d; Ip=[165.204.84.17]; Helo=[SATLEXCHOV02.amd.com] X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: CY1PR12MB0427 X-BeenThere: dri-devel@lists.freedesktop.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Direct Rendering Infrastructure - Development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Monk Liu Errors-To: dri-devel-bounces@lists.freedesktop.org Sender: "dri-devel" X-Virus-Scanned: ClamAV using ClamSMTP some description: for RB tree traveler we don't need to travel to the bottom level if already found the equal size node, thus the search performance can get improved. Tested-by: Rex Zhu Signed-off-by: Monk Liu --- 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; }