From patchwork Fri Nov 23 09:49:31 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Liu, Monk" X-Patchwork-Id: 10695497 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 21C7B5A4 for ; Fri, 23 Nov 2018 09:49:40 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 0B4322BFB3 for ; Fri, 23 Nov 2018 09:49:40 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id F3F222BFC6; Fri, 23 Nov 2018 09:49:39 +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=BAYES_00,HTML_MESSAGE, 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 6EC372BFB3 for ; Fri, 23 Nov 2018 09:49:39 +0000 (UTC) Received: from gabe.freedesktop.org (localhost [127.0.0.1]) by gabe.freedesktop.org (Postfix) with ESMTP id 927976E611; Fri, 23 Nov 2018 09:49:38 +0000 (UTC) X-Original-To: dri-devel@lists.freedesktop.org Delivered-To: dri-devel@lists.freedesktop.org Received: from NAM01-BY2-obe.outbound.protection.outlook.com (mail-eopbgr810058.outbound.protection.outlook.com [40.107.81.58]) by gabe.freedesktop.org (Postfix) with ESMTPS id 2EC946E611 for ; Fri, 23 Nov 2018 09:49:37 +0000 (UTC) Received: from BN6PR1201MB0241.namprd12.prod.outlook.com (10.174.115.136) by BN6PR1201MB0065.namprd12.prod.outlook.com (10.174.114.15) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1361.16; Fri, 23 Nov 2018 09:49:31 +0000 Received: from BN6PR1201MB0241.namprd12.prod.outlook.com ([fe80::5892:b5e0:60ae:b647]) by BN6PR1201MB0241.namprd12.prod.outlook.com ([fe80::5892:b5e0:60ae:b647%3]) with mapi id 15.20.1339.031; Fri, 23 Nov 2018 09:49:31 +0000 From: "Liu, Monk" To: Chris Wilson , "dri-devel@lists.freedesktop.org" Subject: FW: [PATCH] drm: should break if already get the best size Thread-Topic: [PATCH] drm: should break if already get the best size Thread-Index: AQHUgl+MZnEVSWJV9UeNiwtRwErG6KVdHYWAgAABMvA= Date: Fri, 23 Nov 2018 09:49:31 +0000 Message-ID: References: <1542889986-13261-1-git-send-email-Monk.Liu@amd.com> In-Reply-To: Accept-Language: en-US, zh-CN Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [116.228.147.241] x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1; BN6PR1201MB0065; 20:jFv4TovzHX1oL3MxKz4vLDMHGkMDS7zl4faims11bYt7g5PHb+xnlzwpXqUEzA3EmgAFLlXr8NN6sREn6G1lJAgaZffQ9raMbAP3yEfVculJvrJF+jBZRqqCBZpcOnGMjdA6F2QciWIF59AyBOKL2W3B8niPMAOclzAv6xs3ippfaWECZSa+UJgpxjVskSscm08/2yhvotUdQAgs8HLPPKRSsTWU1mWM4Aifc3Zs/LZ4n9lnt36A08DgRFn78gjj x-ms-exchange-antispam-srfa-diagnostics: SOS; x-ms-office365-filtering-correlation-id: 988aab7c-7530-4bdf-1b73-08d65128f792 x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: BCL:0; PCL:0; RULEID:(2390098)(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600074)(711020)(4618075)(2017052603328)(7153060)(7193020); SRVR:BN6PR1201MB0065; x-ms-traffictypediagnostic: BN6PR1201MB0065: x-microsoft-antispam-prvs: x-ms-exchange-senderadcheck: 1 x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(5005006)(8121501046)(3231442)(944501410)(52105112)(3002001)(10201501046)(93006095)(93001095)(6055026)(148016)(149066)(150057)(6041310)(20161123558120)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123560045)(20161123564045)(20161123562045)(201708071742011)(7699051)(76991095); SRVR:BN6PR1201MB0065; BCL:0; PCL:0; RULEID:; SRVR:BN6PR1201MB0065; x-forefront-prvs: 086597191B x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(979002)(396003)(376002)(39860400002)(366004)(346002)(136003)(199004)(189003)(8936002)(71190400001)(478600001)(110136005)(105586002)(81156014)(99286004)(71200400001)(3846002)(790700001)(6116002)(72206003)(53546011)(446003)(53936002)(33656002)(5660300001)(476003)(81166006)(74316002)(2501003)(11346002)(25786009)(606006)(2900100001)(6436002)(26005)(8676002)(106356001)(316002)(236005)(7736002)(97736004)(186003)(102836004)(54896002)(256004)(68736007)(229853002)(486006)(14454004)(66066001)(6506007)(2906002)(9686003)(966005)(2473003)(7696005)(6306002)(76176011)(86362001)(55016002)(28333003)(15583001)(969003)(989001)(999001)(1009001)(1019001); DIR:OUT; SFP:1101; SCL:1; SRVR:BN6PR1201MB0065; H:BN6PR1201MB0241.namprd12.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:1; MX:1; received-spf: None (protection.outlook.com: amd.com does not designate permitted sender hosts) x-microsoft-antispam-message-info: lZmogdYNiSY/DvWves20q3h6y/NIgzRwXqutOlr+UGFeUiN7jETkzpiJlMI59Qn2gkLSnPBRSsCZJojg0ItdrviSn1Psk+hyseQij/uKpYiB+gQ3szgEFDuUVHTtJqdeqaXdB7ynHa09F/5Md+WfK+LIJpoYtNgvhDhIirIDIy7DvQzN2skFRCJLJh4iP30DB2rV+/sj5S0K8A6GmbKQvxrKep1tcnpkx4CxY7fvbOf7apiESRFW9dRJhOYCnfz/zY9vgv36Hs/iS2ybMoIm9Hxuq5C8oYCuG1fq1+PERkCVpKm/8YTMyUXnxpzGA85PBLljgXsardV4JxWGiP3nM6lrzwBdJloEAP2Mkbh27Mk= spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM MIME-Version: 1.0 X-OriginatorOrg: amd.com X-MS-Exchange-CrossTenant-Network-Message-Id: 988aab7c-7530-4bdf-1b73-08d65128f792 X-MS-Exchange-CrossTenant-originalarrivaltime: 23 Nov 2018 09:49:31.2122 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: 3dd8961f-e488-4e60-8e11-a82d994e183d X-MS-Exchange-Transport-CrossTenantHeadersStamped: BN6PR1201MB0065 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: , Errors-To: dri-devel-bounces@lists.freedesktop.org Sender: "dri-devel" X-Virus-Scanned: ClamAV using ClamSMTP 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 ; amd-gfx@lists.freedesktop.org Subject: Re: [PATCH] drm: should break if already get the best size Tested-by: Rex Zhu > 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 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; }