From patchwork Mon Feb 19 08:57:28 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chris Wilson X-Patchwork-Id: 10227311 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 5503F60467 for ; Mon, 19 Feb 2018 08:57:50 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 4B536282EC for ; Mon, 19 Feb 2018 08:57:50 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 3D1382818A; Mon, 19 Feb 2018 08:57:50 +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=-4.2 required=2.0 tests=BAYES_00, RCVD_IN_DNSWL_MED autolearn=unavailable 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 EA4432818A for ; Mon, 19 Feb 2018 08:57:49 +0000 (UTC) Received: from gabe.freedesktop.org (localhost [127.0.0.1]) by gabe.freedesktop.org (Postfix) with ESMTP id 8DF8689EB1; Mon, 19 Feb 2018 08:57:48 +0000 (UTC) X-Original-To: dri-devel@lists.freedesktop.org Delivered-To: dri-devel@lists.freedesktop.org Received: from fireflyinternet.com (mail.fireflyinternet.com [109.228.58.192]) by gabe.freedesktop.org (Postfix) with ESMTPS id BB79289BAF; Mon, 19 Feb 2018 08:57:46 +0000 (UTC) X-Default-Received-SPF: pass (skip=forwardok (res=PASS)) x-ip-name=78.156.65.138; Received: from haswell.alporthouse.com (unverified [78.156.65.138]) by fireflyinternet.com (Firefly Internet (M1)) with ESMTP id 10734829-1500050 for multiple; Mon, 19 Feb 2018 08:57:30 +0000 Received: by haswell.alporthouse.com (sSMTP sendmail emulation); Mon, 19 Feb 2018 08:57:31 +0000 From: Chris Wilson To: dri-devel@lists.freedesktop.org Subject: [PATCH 2/2] drm/mm: Micro-optimise updating the upper layers of the interval tree Date: Mon, 19 Feb 2018 08:57:28 +0000 Message-Id: <20180219085728.7517-2-chris@chris-wilson.co.uk> X-Mailer: git-send-email 2.16.1 In-Reply-To: <20180219085728.7517-1-chris@chris-wilson.co.uk> References: <20180219085728.7517-1-chris@chris-wilson.co.uk> X-Originating-IP: 78.156.65.138 X-Country: code=GB country="United Kingdom" ip=78.156.65.138 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: intel-gfx@lists.freedesktop.org MIME-Version: 1.0 Errors-To: dri-devel-bounces@lists.freedesktop.org Sender: "dri-devel" X-Virus-Scanned: ClamAV using ClamSMTP When we insert a node into a hole inside the interval tree, we need to climb the layers above us to update the cached interval. When doing so, we know that the initial node exists as it is our starting hole. add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-10 (-10) Function old new delta drm_mm_interval_tree_add_node 221 211 -10 Signed-off-by: Chris Wilson Reviewed-by: Joonas Lahtinen --- drivers/gpu/drm/drm_mm.c | 16 ++++++++++------ 1 file changed, 10 insertions(+), 6 deletions(-) diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index a351bd888a61..2d844c9a288f 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -179,21 +179,23 @@ static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node, { struct drm_mm *mm = hole_node->mm; struct rb_node **link, *rb; - struct drm_mm_node *parent; bool leftmost; node->__subtree_last = LAST(node); - if (hole_node->allocated) { - rb = &hole_node->rb; - while (rb) { - parent = rb_entry(rb, struct drm_mm_node, rb); + if (likely(hole_node->allocated)) { + struct drm_mm_node *parent; + + /* Update the interval range above us */ + parent = hole_node; + do { if (parent->__subtree_last >= node->__subtree_last) break; parent->__subtree_last = node->__subtree_last; rb = rb_parent(rb); - } + } while ((parent = rb_entry_safe(&parent->rb, + struct drm_mm_node, rb))); rb = &hole_node->rb; link = &hole_node->rb.rb_right; @@ -205,6 +207,8 @@ static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node, } while (*link) { + struct drm_mm_node *parent; + rb = *link; parent = rb_entry(rb, struct drm_mm_node, rb); if (parent->__subtree_last < node->__subtree_last)