Received: by 2002:a5b:505:0:0:0:0:0 with SMTP id o5csp5407919ybp; Tue, 8 Oct 2019 02:20:04 -0700 (PDT) X-Google-Smtp-Source: APXvYqw2GViS/gTKnNHoXzGy7h8FgWWmD5UMac+QXfHwt9QLTtt53E81I1LfTmRkHM9LupOHGS65 X-Received: by 2002:a17:906:fae2:: with SMTP id lu34mr27388494ejb.53.1570526404351; Tue, 08 Oct 2019 02:20:04 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1570526404; cv=none; d=google.com; s=arc-20160816; b=nJ6YV3wgVNgC14zHk0/MF6hH7zIr1Yqo2Pxr6JvqmwaFGtmjxvEBV1/f9alG0J6BCl Hej1cjkPJA0nFlbm+AyNcAeInfNA78Mq9yM+x9rYYnRXfDHwT6jwe6ikvc7KbMhaV35i ANSxumoZMCpKtSG7pEiu1lNP4OlBinv43GhdkZ7UOYOPTn11GX3azc6A/ovwgVCda/7j WKVM38paPnUx1CqO5xYIyL4G8Tr1hjqWqmjwpfFu8kJET/r1Mo374m2OLz0VHs7FLEhr ElbCd9QJt0vQuiUnVL2+cS+8KSEKQLSAsQWF5tl7neDoAY7MbmiMd6GJGKxxEkKjVuE5 u8Qw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=ndNpRSlWuLquFl6vbAkB7ndTRYhj2g7TOLU8KL+uO/4=; b=gNozZWRWBuqQRfYMd478SxjOzV3Bh02sFNc8eOG+cVOXYVz88c6aAFSnO0ZC2Zt3TF MpQrwQcj9cZD/UZ5s3uotSiVU8aKre4awbaqTtVXJ2NxLVn7aEijW8JNf8ugVI3rlWX3 4ADSPTJVJCGffnk/VSLQXrpcl4iXHheGYuX1HZlFg1m91kn6+q+s1dL1oOC4VXs2XIc6 sk4XDmP4u3Y5/SeYxI/9qP8tASkMbv3n4syEV0KEd31Itq0TchrZKRJg4tj+O6SSYhT8 X+Fyc4BOa7YK/5F7ee9v/cN0u6VFGdXzP3aChY6BCQsZEO5FOqEnyMggXsXT7ye/JQtV GyZg== ARC-Authentication-Results: i=1; mx.google.com; dkim=fail (test mode) header.i=@shipmail.org header.s=mail header.b=UGyHthrR; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id ch6si8535811ejb.275.2019.10.08.02.19.40; Tue, 08 Oct 2019 02:20:04 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; dkim=fail (test mode) header.i=@shipmail.org header.s=mail header.b=UGyHthrR; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730314AbfJHJPz (ORCPT + 99 others); Tue, 8 Oct 2019 05:15:55 -0400 Received: from ste-pvt-msa1.bahnhof.se ([213.80.101.70]:14550 "EHLO ste-pvt-msa1.bahnhof.se" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1729740AbfJHJPY (ORCPT ); Tue, 8 Oct 2019 05:15:24 -0400 Received: from localhost (localhost [127.0.0.1]) by ste-pvt-msa1.bahnhof.se (Postfix) with ESMTP id F2AF63F6B4; Tue, 8 Oct 2019 11:15:20 +0200 (CEST) Authentication-Results: ste-pvt-msa1.bahnhof.se; dkim=pass (1024-bit key; unprotected) header.d=shipmail.org header.i=@shipmail.org header.b=UGyHthrR; dkim-atps=neutral X-Virus-Scanned: Debian amavisd-new at bahnhof.se X-Spam-Flag: NO X-Spam-Score: -2.099 X-Spam-Level: X-Spam-Status: No, score=-2.099 tagged_above=-999 required=6.31 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no Received: from ste-pvt-msa1.bahnhof.se ([127.0.0.1]) by localhost (ste-pvt-msa1.bahnhof.se [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id x7Op6IdZToQ2; Tue, 8 Oct 2019 11:15:20 +0200 (CEST) Received: from mail1.shipmail.org (h-205-35.A357.priv.bahnhof.se [155.4.205.35]) (Authenticated sender: mb878879) by ste-pvt-msa1.bahnhof.se (Postfix) with ESMTPA id 3737B3F673; Tue, 8 Oct 2019 11:15:19 +0200 (CEST) Received: from localhost.localdomain.localdomain (h-205-35.A357.priv.bahnhof.se [155.4.205.35]) by mail1.shipmail.org (Postfix) with ESMTPSA id 5D9A7360FCF; Tue, 8 Oct 2019 11:15:18 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shipmail.org; s=mail; t=1570526118; bh=bx8eG09waI9JD3lCmO6ixUtN4UOAIiobzckYp+RwK+E=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=UGyHthrRM8Ty83dHf/2wxPKr3h0GCbukcY0YVrYrDQKnmQAfx/eTR6nS7nPRw+IG2 W/RedGhIGabPjcrWD5MMsk/DF68iI2/tgUUl1dF5JPQYBhO/5t5R0pyVXSXie8hTGy HG2PlvMaSgL7IZBxF3MXkfyzE/121PHNNqNzv16I= From: =?UTF-8?q?Thomas=20Hellstr=C3=B6m=20=28VMware=29?= To: linux-kernel@vger.kernel.org, linux-mm@kvack.org Cc: torvalds@linux-foundation.org, Thomas Hellstrom , Andrew Morton , Matthew Wilcox , Will Deacon , Peter Zijlstra , Rik van Riel , Minchan Kim , Michal Hocko , Huang Ying , =?UTF-8?q?J=C3=A9r=C3=B4me=20Glisse?= , "Kirill A . Shutemov" , Deepak Rawat Subject: [PATCH v4 7/9] drm/vmwgfx: Use an RBtree instead of linked list for MOB resources Date: Tue, 8 Oct 2019 11:15:06 +0200 Message-Id: <20191008091508.2682-8-thomas_os@shipmail.org> X-Mailer: git-send-email 2.20.1 In-Reply-To: <20191008091508.2682-1-thomas_os@shipmail.org> References: <20191008091508.2682-1-thomas_os@shipmail.org> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org From: Thomas Hellstrom With emulated coherent memory we need to be able to quickly look up a resource from the MOB offset. Instead of traversing a linked list with O(n) worst case, use an RBtree with O(log n) worst case complexity. Cc: Andrew Morton Cc: Matthew Wilcox Cc: Will Deacon Cc: Peter Zijlstra Cc: Rik van Riel Cc: Minchan Kim Cc: Michal Hocko Cc: Huang Ying Cc: Jérôme Glisse Cc: Kirill A. Shutemov Signed-off-by: Thomas Hellstrom Reviewed-by: Deepak Rawat --- drivers/gpu/drm/vmwgfx/vmwgfx_bo.c | 5 ++-- drivers/gpu/drm/vmwgfx/vmwgfx_drv.h | 10 +++---- drivers/gpu/drm/vmwgfx/vmwgfx_resource.c | 33 +++++++++++++++++------- 3 files changed, 32 insertions(+), 16 deletions(-) diff --git a/drivers/gpu/drm/vmwgfx/vmwgfx_bo.c b/drivers/gpu/drm/vmwgfx/vmwgfx_bo.c index 869aeaec2f86..18e4b329e563 100644 --- a/drivers/gpu/drm/vmwgfx/vmwgfx_bo.c +++ b/drivers/gpu/drm/vmwgfx/vmwgfx_bo.c @@ -463,6 +463,7 @@ void vmw_bo_bo_free(struct ttm_buffer_object *bo) struct vmw_buffer_object *vmw_bo = vmw_buffer_object(bo); WARN_ON(vmw_bo->dirty); + WARN_ON(!RB_EMPTY_ROOT(&vmw_bo->res_tree)); vmw_bo_unmap(vmw_bo); kfree(vmw_bo); } @@ -479,6 +480,7 @@ static void vmw_user_bo_destroy(struct ttm_buffer_object *bo) struct vmw_buffer_object *vbo = &vmw_user_bo->vbo; WARN_ON(vbo->dirty); + WARN_ON(!RB_EMPTY_ROOT(&vbo->res_tree)); vmw_bo_unmap(vbo); ttm_prime_object_kfree(vmw_user_bo, prime); } @@ -514,8 +516,7 @@ int vmw_bo_init(struct vmw_private *dev_priv, memset(vmw_bo, 0, sizeof(*vmw_bo)); BUILD_BUG_ON(TTM_MAX_BO_PRIORITY <= 3); vmw_bo->base.priority = 3; - - INIT_LIST_HEAD(&vmw_bo->res_list); + vmw_bo->res_tree = RB_ROOT; ret = ttm_bo_init(bdev, &vmw_bo->base, size, ttm_bo_type_device, placement, diff --git a/drivers/gpu/drm/vmwgfx/vmwgfx_drv.h b/drivers/gpu/drm/vmwgfx/vmwgfx_drv.h index 7944dbbbdd72..53f8522ae032 100644 --- a/drivers/gpu/drm/vmwgfx/vmwgfx_drv.h +++ b/drivers/gpu/drm/vmwgfx/vmwgfx_drv.h @@ -100,7 +100,7 @@ struct vmw_fpriv { /** * struct vmw_buffer_object - TTM buffer object with vmwgfx additions * @base: The TTM buffer object - * @res_list: List of resources using this buffer object as a backing MOB + * @res_tree: RB tree of resources using this buffer object as a backing MOB * @pin_count: pin depth * @dx_query_ctx: DX context if this buffer object is used as a DX query MOB * @map: Kmap object for semi-persistent mappings @@ -109,7 +109,7 @@ struct vmw_fpriv { */ struct vmw_buffer_object { struct ttm_buffer_object base; - struct list_head res_list; + struct rb_root res_tree; s32 pin_count; /* Not ref-counted. Protected by binding_mutex */ struct vmw_resource *dx_query_ctx; @@ -157,8 +157,8 @@ struct vmw_res_func; * pin-count greater than zero. It is not on the resource LRU lists and its * backup buffer is pinned. Hence it can't be evicted. * @func: Method vtable for this resource. Immutable. + * @mob_node; Node for the MOB backup rbtree. Protected by @backup reserved. * @lru_head: List head for the LRU list. Protected by @dev_priv::resource_lock. - * @mob_head: List head for the MOB backup list. Protected by @backup reserved. * @binding_head: List head for the context binding list. Protected by * the @dev_priv::binding_mutex * @res_free: The resource destructor. @@ -179,8 +179,8 @@ struct vmw_resource { unsigned long backup_offset; unsigned long pin_count; const struct vmw_res_func *func; + struct rb_node mob_node; struct list_head lru_head; - struct list_head mob_head; struct list_head binding_head; struct vmw_resource_dirty *dirty; void (*res_free) (struct vmw_resource *res); @@ -733,7 +733,7 @@ void vmw_resource_dirty_update(struct vmw_resource *res, pgoff_t start, */ static inline bool vmw_resource_mob_attached(const struct vmw_resource *res) { - return !list_empty(&res->mob_head); + return !RB_EMPTY_NODE(&res->mob_node); } /** diff --git a/drivers/gpu/drm/vmwgfx/vmwgfx_resource.c b/drivers/gpu/drm/vmwgfx/vmwgfx_resource.c index e4c97a4cf2ff..328ad46076ff 100644 --- a/drivers/gpu/drm/vmwgfx/vmwgfx_resource.c +++ b/drivers/gpu/drm/vmwgfx/vmwgfx_resource.c @@ -40,11 +40,24 @@ void vmw_resource_mob_attach(struct vmw_resource *res) { struct vmw_buffer_object *backup = res->backup; + struct rb_node **new = &backup->res_tree.rb_node, *parent = NULL; dma_resv_assert_held(res->backup->base.base.resv); res->used_prio = (res->res_dirty) ? res->func->dirty_prio : res->func->prio; - list_add_tail(&res->mob_head, &backup->res_list); + + while (*new) { + struct vmw_resource *this = + container_of(*new, struct vmw_resource, mob_node); + + parent = *new; + new = (res->backup_offset < this->backup_offset) ? + &((*new)->rb_left) : &((*new)->rb_right); + } + + rb_link_node(&res->mob_node, parent, new); + rb_insert_color(&res->mob_node, &backup->res_tree); + vmw_bo_prio_add(backup, res->used_prio); } @@ -58,7 +71,8 @@ void vmw_resource_mob_detach(struct vmw_resource *res) dma_resv_assert_held(backup->base.base.resv); if (vmw_resource_mob_attached(res)) { - list_del_init(&res->mob_head); + rb_erase(&res->mob_node, &backup->res_tree); + RB_CLEAR_NODE(&res->mob_node); vmw_bo_prio_del(backup, res->used_prio); } } @@ -204,8 +218,8 @@ int vmw_resource_init(struct vmw_private *dev_priv, struct vmw_resource *res, res->res_free = res_free; res->dev_priv = dev_priv; res->func = func; + RB_CLEAR_NODE(&res->mob_node); INIT_LIST_HEAD(&res->lru_head); - INIT_LIST_HEAD(&res->mob_head); INIT_LIST_HEAD(&res->binding_head); res->id = -1; res->backup = NULL; @@ -754,19 +768,20 @@ int vmw_resource_validate(struct vmw_resource *res, bool intr) */ void vmw_resource_unbind_list(struct vmw_buffer_object *vbo) { - - struct vmw_resource *res, *next; struct ttm_validate_buffer val_buf = { .bo = &vbo->base, .num_shared = 0 }; dma_resv_assert_held(vbo->base.base.resv); - list_for_each_entry_safe(res, next, &vbo->res_list, mob_head) { - if (!res->func->unbind) - continue; + while (!RB_EMPTY_ROOT(&vbo->res_tree)) { + struct rb_node *node = vbo->res_tree.rb_node; + struct vmw_resource *res = + container_of(node, struct vmw_resource, mob_node); + + if (!WARN_ON_ONCE(!res->func->unbind)) + (void) res->func->unbind(res, res->res_dirty, &val_buf); - (void) res->func->unbind(res, res->res_dirty, &val_buf); res->backup_dirty = true; res->res_dirty = false; vmw_resource_mob_detach(res); -- 2.21.0