From patchwork Fri Apr 12 16:04:28 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Thomas Hellstrom X-Patchwork-Id: 10898665 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 49FAE1874 for ; Fri, 12 Apr 2019 16:04:37 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 2E82F28B8D for ; Fri, 12 Apr 2019 16:04:37 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 2359428EAC; Fri, 12 Apr 2019 16:04:37 +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,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 99C4A28B8D for ; Fri, 12 Apr 2019 16:04:36 +0000 (UTC) Received: from gabe.freedesktop.org (localhost [127.0.0.1]) by gabe.freedesktop.org (Postfix) with ESMTP id C1C1189A16; Fri, 12 Apr 2019 16:04:34 +0000 (UTC) X-Original-To: dri-devel@lists.freedesktop.org Delivered-To: dri-devel@lists.freedesktop.org Received: from NAM03-DM3-obe.outbound.protection.outlook.com (mail-dm3nam03on062e.outbound.protection.outlook.com [IPv6:2a01:111:f400:fe49::62e]) by gabe.freedesktop.org (Postfix) with ESMTPS id 069E389A1E for ; Fri, 12 Apr 2019 16:04:32 +0000 (UTC) Received: from MN2PR05MB6141.namprd05.prod.outlook.com (20.178.241.217) by MN2PR05MB6030.namprd05.prod.outlook.com (20.178.241.159) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1813.9; Fri, 12 Apr 2019 16:04:28 +0000 Received: from MN2PR05MB6141.namprd05.prod.outlook.com ([fe80::91e:292d:e304:78ad]) by MN2PR05MB6141.namprd05.prod.outlook.com ([fe80::91e:292d:e304:78ad%7]) with mapi id 15.20.1792.009; Fri, 12 Apr 2019 16:04:28 +0000 From: Thomas Hellstrom To: "dri-devel@lists.freedesktop.org" , Linux-graphics-maintainer , "linux-kernel@vger.kernel.org" Subject: [PATCH 7/9] drm/vmwgfx: Use an RBtree instead of linked list for MOB resources Thread-Topic: [PATCH 7/9] drm/vmwgfx: Use an RBtree instead of linked list for MOB resources Thread-Index: AQHU8UlobEdWcIwi0k+T6YSDkCCfYg== Date: Fri, 12 Apr 2019 16:04:28 +0000 Message-ID: <20190412160338.64994-8-thellstrom@vmware.com> References: <20190412160338.64994-1-thellstrom@vmware.com> In-Reply-To: <20190412160338.64994-1-thellstrom@vmware.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-clientproxiedby: VE1PR03CA0023.eurprd03.prod.outlook.com (2603:10a6:802:a0::35) To MN2PR05MB6141.namprd05.prod.outlook.com (2603:10b6:208:c7::25) x-ms-exchange-messagesentrepresentingtype: 1 x-mailer: git-send-email 2.20.1 x-originating-ip: [155.4.205.35] x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: 561d6457-3827-4c08-2d22-08d6bf608a98 x-microsoft-antispam: BCL:0; PCL:0; RULEID:(2390118)(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600139)(711020)(4605104)(2017052603328)(7193020); SRVR:MN2PR05MB6030; x-ms-traffictypediagnostic: MN2PR05MB6030: x-ld-processed: b39138ca-3cee-4b4a-a4d6-cd83d9dd62f0,ExtAddr x-microsoft-antispam-prvs: x-forefront-prvs: 0005B05917 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(136003)(366004)(346002)(376002)(39860400002)(396003)(199004)(189003)(110136005)(25786009)(476003)(2616005)(71190400001)(6512007)(2906002)(186003)(486006)(316002)(68736007)(1076003)(6486002)(6436002)(446003)(478600001)(3846002)(71200400001)(6116002)(11346002)(99286004)(256004)(14444005)(5024004)(14454004)(2501003)(8676002)(107886003)(66066001)(7736002)(4326008)(6506007)(81166006)(36756003)(81156014)(386003)(97736004)(102836004)(50226002)(106356001)(52116002)(5660300002)(53936002)(8936002)(305945005)(76176011)(26005)(86362001)(105586002); DIR:OUT; SFP:1101; SCL:1; SRVR:MN2PR05MB6030; H:MN2PR05MB6141.namprd05.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:1; MX:1; received-spf: None (protection.outlook.com: vmware.com does not designate permitted sender hosts) x-ms-exchange-senderadcheck: 1 x-microsoft-antispam-message-info: prZghs8/nRkYC2yBDJpU6rsni5svazbT5LggPxE/LoFtoi2cYrCd6VljoK+c1qaIGKzjoYVNuLDFitF6QJODGS74Mdpee+3cBjK4dEAfKTxXq13AZK6mn0Wq2b7F4ihcuxdWz6QJ1ZqopVdWTQjXkJzmxqwhcKng5eEcayY9TKfnSYnM9zCB/9K0S9Cx4BrPRZtPx0Eppdj8BArmUmViO+IJEz9jjOW8G/Mo6n+uHS4y4qmMbwJMCx8MbEKClNnV1pbVP1IKmV7Qw6p3yzyOKx3PS7p8OhhsqK4Qsx527GYgymZ0XAbSn25XVj9/jeAweeP4SBhEFBGtJ44AwjeO4s+HINJtK6Gq58qmd+xZWOf8zZo3vFTkIeF+H1Mu8yI/BgRQrl5LCJxlnaDNWUdO/hbav/+wIns4iEajTHdOZG0= MIME-Version: 1.0 X-OriginatorOrg: vmware.com X-MS-Exchange-CrossTenant-Network-Message-Id: 561d6457-3827-4c08-2d22-08d6bf608a98 X-MS-Exchange-CrossTenant-originalarrivaltime: 12 Apr 2019 16:04:28.7962 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: b39138ca-3cee-4b4a-a4d6-cd83d9dd62f0 X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-Transport-CrossTenantHeadersStamped: MN2PR05MB6030 X-Mailman-Original-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=vmware.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=EjrJEBuVV65a1qR6Ls0JKIfuFS+dXxTnVXOq5sUe7zU=; b=dQyVBINV8Fxv/q3c1iygAdWkmfCU0JY/wHvq9Much9poFAUwhIglUok5XTlwLHyYNu6VsNSnz5wkVkO5xIPEYrUVZk10uP6e8EUymEZJLGOEgMZU49Qe4uiJUupTcZ+ZZn+aIriR8sIcXP9/CCmZ+3qHTsGWUQgRKcc7zNiGSQg= X-Mailman-Original-Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=thellstrom@vmware.com; 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: Thomas Hellstrom Errors-To: dri-devel-bounces@lists.freedesktop.org Sender: "dri-devel" X-Virus-Scanned: ClamAV using ClamSMTP 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. 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 90ca866640fe..e8bc7a7ac031 100644 --- a/drivers/gpu/drm/vmwgfx/vmwgfx_bo.c +++ b/drivers/gpu/drm/vmwgfx/vmwgfx_bo.c @@ -464,6 +464,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); } @@ -480,6 +481,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); } @@ -515,8 +517,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 f05fce52fbb4..81ebcd668038 100644 --- a/drivers/gpu/drm/vmwgfx/vmwgfx_drv.h +++ b/drivers/gpu/drm/vmwgfx/vmwgfx_drv.h @@ -90,7 +90,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 @@ -99,7 +99,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; @@ -147,8 +147,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. @@ -169,8 +169,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); @@ -743,7 +743,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 d35f4bd32cd9..ff9fe5650468 100644 --- a/drivers/gpu/drm/vmwgfx/vmwgfx_resource.c +++ b/drivers/gpu/drm/vmwgfx/vmwgfx_resource.c @@ -41,11 +41,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; lockdep_assert_held(&backup->base.resv->lock.base); 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); } @@ -59,7 +72,8 @@ void vmw_resource_mob_detach(struct vmw_resource *res) lockdep_assert_held(&backup->base.resv->lock.base); 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); } } @@ -206,8 +220,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; @@ -755,19 +769,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 }; lockdep_assert_held(&vbo->base.resv->lock.base); - 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);