From patchwork Mon Jan 11 11:01:01 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chris Wilson X-Patchwork-Id: 8002381 Return-Path: X-Original-To: patchwork-intel-gfx@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork2.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.136]) by patchwork2.web.kernel.org (Postfix) with ESMTP id 0A69BBEEE5 for ; Mon, 11 Jan 2016 11:04:06 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id D3D6A20295 for ; Mon, 11 Jan 2016 11:04:04 +0000 (UTC) Received: from gabe.freedesktop.org (gabe.freedesktop.org [131.252.210.177]) by mail.kernel.org (Postfix) with ESMTP id B94672028D for ; Mon, 11 Jan 2016 11:04:02 +0000 (UTC) Received: from gabe.freedesktop.org (localhost [127.0.0.1]) by gabe.freedesktop.org (Postfix) with ESMTP id 3E7C06E494; Mon, 11 Jan 2016 03:04:01 -0800 (PST) X-Original-To: intel-gfx@lists.freedesktop.org Delivered-To: intel-gfx@lists.freedesktop.org Received: from mail-wm0-f68.google.com (mail-wm0-f68.google.com [74.125.82.68]) by gabe.freedesktop.org (Postfix) with ESMTPS id DD2846E475; Mon, 11 Jan 2016 03:02:04 -0800 (PST) Received: by mail-wm0-f68.google.com with SMTP id u188so25684219wmu.0; Mon, 11 Jan 2016 03:02:04 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=sender:from:to:cc:subject:date:message-id:in-reply-to:references; bh=+eb5zJU/2sybaALbTbCPJNedxqP9rzYYgF7ftbRKKyY=; b=VBaOVFwleffoz4eL8mK4bxQUanuNc40umhtfdmPWTC2Ryaiba+k49iUMUz6cYniUqJ BbdFj6Um1q923Up1lLVXtN5ZFAG2re9f8H0OGmaEOVTxKafyxJXlD9cvLfB+EkWjAuGV EOu07nFAg/jaxFN88KQgRi6CNcnLaRIFTE8kaoVQ13qHLkZ1BmrI0iFVQ5bDi2tRIrM2 SIlUMis7Qa7pH8LTn+ep92YnWLj0Oe15k7Q1oFUVE4U3VGs/BQ4ICfZHI2iZHC5IvSKp l1YnMpnJDBWV14tBEism1RVAejFqEeAUO6N4dhkj1uNeo/xh4QGxFOiAxDQNyitGJVLe 8Zpw== X-Received: by 10.28.93.140 with SMTP id r134mr13522282wmb.80.1452510123694; Mon, 11 Jan 2016 03:02:03 -0800 (PST) Received: from haswell.alporthouse.com ([78.156.65.138]) by smtp.gmail.com with ESMTPSA id 73sm12311579wmm.7.2016.01.11.03.02.02 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Mon, 11 Jan 2016 03:02:02 -0800 (PST) From: Chris Wilson To: intel-gfx@lists.freedesktop.org Date: Mon, 11 Jan 2016 11:01:01 +0000 Message-Id: <1452510091-6833-19-git-send-email-chris@chris-wilson.co.uk> X-Mailer: git-send-email 2.7.0.rc3 In-Reply-To: <1452510091-6833-1-git-send-email-chris@chris-wilson.co.uk> References: <1452503961-14837-1-git-send-email-chris@chris-wilson.co.uk> <1452510091-6833-1-git-send-email-chris@chris-wilson.co.uk> Cc: dri-devel@lists.freedesktop.org Subject: [Intel-gfx] [PATCH 160/190] drm: Track drm_mm nodes with an interval tree X-BeenThere: intel-gfx@lists.freedesktop.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: Intel graphics driver community testing & development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: intel-gfx-bounces@lists.freedesktop.org Sender: "Intel-gfx" X-Spam-Status: No, score=-4.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_MED,RP_MATCHES_RCVD,T_DKIM_INVALID,UNPARSEABLE_RELAY autolearn=unavailable version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP In addition to the last-in/first-out stack for accessing drm_mm nodes, we occasionally and in the future often want to find a drm_mm_node by an address. To do so efficiently we need to track the nodes in an interval tree - lookups for a particular address will then be O(lg(N)), where N is the number of nodes in the range manager as opposed to O(N). Insertion however gains an extra O(lg(N)) step for all nodes irrespective of whether the interval tree is in use. For future i915 patches, eliminating the linear walk is a significant improvement. v2: Use generic interval-tree template for u64 and faster insertion. Signed-off-by: Chris Wilson Cc: dri-devel@lists.freedesktop.org --- drivers/gpu/drm/drm_mm.c | 124 ++++++++++++++++++++++++++++++++++++++--------- include/drm/drm_mm.h | 12 +++++ 2 files changed, 113 insertions(+), 23 deletions(-) diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index 04de6fd88f8c..fff084f266f9 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -46,6 +46,7 @@ #include #include #include +#include /** * DOC: Overview @@ -103,6 +104,63 @@ static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_ u64 end, enum drm_mm_search_flags flags); +#define START(node) ((node)->start) +#define LAST(node) ((node)->start + (node)->size - 1) + +INTERVAL_TREE_DEFINE(struct drm_mm_node, rb, + u64, __subtree_last, + START, LAST, static inline, drm_mm_interval_tree) + +struct drm_mm_node * +drm_mm_interval_first(struct drm_mm *mm, u64 start, u64 last) +{ + return drm_mm_interval_tree_iter_first(&mm->interval_tree, + start, last); +} +EXPORT_SYMBOL(drm_mm_interval_first); + +struct drm_mm_node * +drm_mm_interval_next(struct drm_mm_node *node, u64 start, u64 last) +{ + return drm_mm_interval_tree_iter_next(node, start, last); +} +EXPORT_SYMBOL(drm_mm_interval_next); + +static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node, + struct drm_mm_node *node) +{ + struct drm_mm *mm = hole_node->mm; + struct rb_node **link, *rb_parent; + struct drm_mm_node *parent; + + node->__subtree_last = LAST(node); + + if (hole_node->allocated) { + hole_node->__subtree_last = node->__subtree_last; + rb_parent = &hole_node->rb; + link = &hole_node->rb.rb_right; + } else { + rb_parent = NULL; + link = &mm->interval_tree.rb_node; + } + + while (*link) { + rb_parent = *link; + parent = rb_entry(rb_parent, struct drm_mm_node, rb); + if (parent->__subtree_last < node->__subtree_last) + parent->__subtree_last = node->__subtree_last; + if (node->start < parent->start) + link = &parent->rb.rb_left; + else + link = &parent->rb.rb_right; + } + + rb_link_node(&node->rb, rb_parent, link); + rb_insert_augmented(&node->rb, + &mm->interval_tree, + &drm_mm_interval_tree_augment); +} + static void drm_mm_insert_helper(struct drm_mm_node *hole_node, struct drm_mm_node *node, u64 size, unsigned alignment, @@ -153,6 +211,8 @@ static void drm_mm_insert_helper(struct drm_mm_node *hole_node, INIT_LIST_HEAD(&node->hole_stack); list_add(&node->node_list, &hole_node->node_list); + drm_mm_interval_tree_add_node(hole_node, node); + BUG_ON(node->start + node->size > adj_end); node->hole_follows = 0; @@ -178,39 +238,50 @@ static void drm_mm_insert_helper(struct drm_mm_node *hole_node, */ int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node) { - struct drm_mm_node *hole; u64 end = node->start + node->size; - u64 hole_start; - u64 hole_end; - - BUG_ON(node == NULL); + struct drm_mm_node *hole; + u64 hole_start, hole_end; /* Find the relevant hole to add our node to */ - drm_mm_for_each_hole(hole, mm, hole_start, hole_end) { - if (hole_start > node->start || hole_end < end) - continue; + hole = drm_mm_interval_tree_iter_first(&mm->interval_tree, + node->start, ~(u64)0); + if (hole) { + if (hole->start <= node->start) + return -ENOSPC; + } else { + hole = list_entry(&mm->head_node.node_list, + typeof(*hole), node_list); + } - node->mm = mm; - node->allocated = 1; + hole = list_last_entry(&hole->node_list, typeof(*hole), node_list); + if (!hole->hole_follows) + return -ENOSPC; - INIT_LIST_HEAD(&node->hole_stack); - list_add(&node->node_list, &hole->node_list); + hole_start = __drm_mm_hole_node_start(hole); + hole_end = __drm_mm_hole_node_end(hole); + if (hole_start > node->start || hole_end < end) + return -ENOSPC; - if (node->start == hole_start) { - hole->hole_follows = 0; - list_del_init(&hole->hole_stack); - } + node->mm = mm; + node->allocated = 1; - node->hole_follows = 0; - if (end != hole_end) { - list_add(&node->hole_stack, &mm->hole_stack); - node->hole_follows = 1; - } + INIT_LIST_HEAD(&node->hole_stack); + list_add(&node->node_list, &hole->node_list); - return 0; + drm_mm_interval_tree_add_node(hole, node); + + if (node->start == hole_start) { + hole->hole_follows = 0; + list_del_init(&hole->hole_stack); + } + + node->hole_follows = 0; + if (end != hole_end) { + list_add(&node->hole_stack, &mm->hole_stack); + node->hole_follows = 1; } - return -ENOSPC; + return 0; } EXPORT_SYMBOL(drm_mm_reserve_node); @@ -300,6 +371,8 @@ static void drm_mm_insert_helper_range(struct drm_mm_node *hole_node, INIT_LIST_HEAD(&node->hole_stack); list_add(&node->node_list, &hole_node->node_list); + drm_mm_interval_tree_add_node(hole_node, node); + BUG_ON(node->start < start); BUG_ON(node->start < adj_start); BUG_ON(node->start + node->size > adj_end); @@ -388,6 +461,7 @@ void drm_mm_remove_node(struct drm_mm_node *node) } else list_move(&prev_node->hole_stack, &mm->hole_stack); + drm_mm_interval_tree_remove(node, &mm->interval_tree); list_del(&node->node_list); node->allocated = 0; } @@ -514,11 +588,13 @@ void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new) { list_replace(&old->node_list, &new->node_list); list_replace(&old->hole_stack, &new->hole_stack); + rb_replace_node(&old->rb, &new->rb, &old->mm->interval_tree); new->hole_follows = old->hole_follows; new->mm = old->mm; new->start = old->start; new->size = old->size; new->color = old->color; + new->__subtree_last = old->__subtree_last; old->allocated = 0; new->allocated = 1; @@ -756,6 +832,8 @@ void drm_mm_init(struct drm_mm * mm, u64 start, u64 size) mm->head_node.size = start - mm->head_node.start; list_add_tail(&mm->head_node.hole_stack, &mm->hole_stack); + mm->interval_tree = RB_ROOT; + mm->color_adjust = NULL; } EXPORT_SYMBOL(drm_mm_init); diff --git a/include/drm/drm_mm.h b/include/drm/drm_mm.h index fc65118e5077..205ddcf6d55d 100644 --- a/include/drm/drm_mm.h +++ b/include/drm/drm_mm.h @@ -37,6 +37,7 @@ * Generic range manager structs */ #include +#include #include #include #include @@ -61,6 +62,7 @@ enum drm_mm_allocator_flags { struct drm_mm_node { struct list_head node_list; struct list_head hole_stack; + struct rb_node rb; unsigned hole_follows : 1; unsigned scanned_block : 1; unsigned scanned_prev_free : 1; @@ -70,6 +72,7 @@ struct drm_mm_node { unsigned long color; u64 start; u64 size; + u64 __subtree_last; struct drm_mm *mm; }; @@ -79,6 +82,9 @@ struct drm_mm { /* head_node.node_list is the list of all memory nodes, ordered * according to the (increasing) start address of the memory node. */ struct drm_mm_node head_node; + /* Keep an interval_tree for fast lookup of drm_mm_nodes by address. */ + struct rb_root interval_tree; + unsigned int scan_check_range : 1; unsigned scan_alignment; unsigned long scan_color; @@ -295,6 +301,12 @@ void drm_mm_init(struct drm_mm *mm, void drm_mm_takedown(struct drm_mm *mm); bool drm_mm_clean(struct drm_mm *mm); +struct drm_mm_node * +drm_mm_interval_first(struct drm_mm *mm, u64 start, u64 last); + +struct drm_mm_node * +drm_mm_interval_next(struct drm_mm_node *node, u64 start, u64 last); + void drm_mm_init_scan(struct drm_mm *mm, u64 size, unsigned alignment,