From patchwork Mon Oct 31 10:26:45 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chris Wilson X-Patchwork-Id: 9405245 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 508316022E for ; Mon, 31 Oct 2016 10:27:06 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 4810529138 for ; Mon, 31 Oct 2016 10:27:06 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 3CC3529154; Mon, 31 Oct 2016 10:27:06 +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.1 required=2.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_MED,T_DKIM_INVALID 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 CA8FA29138 for ; Mon, 31 Oct 2016 10:27:05 +0000 (UTC) Received: from gabe.freedesktop.org (localhost [127.0.0.1]) by gabe.freedesktop.org (Postfix) with ESMTP id 8E9D46E23E; Mon, 31 Oct 2016 10:27:04 +0000 (UTC) X-Original-To: intel-gfx@lists.freedesktop.org Delivered-To: intel-gfx@lists.freedesktop.org Received: from mail-wm0-x243.google.com (mail-wm0-x243.google.com [IPv6:2a00:1450:400c:c09::243]) by gabe.freedesktop.org (Postfix) with ESMTPS id 166086E21B for ; Mon, 31 Oct 2016 10:27:02 +0000 (UTC) Received: by mail-wm0-x243.google.com with SMTP id p190so11500609wmp.1 for ; Mon, 31 Oct 2016 03:27:02 -0700 (PDT) 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=HilGpFo5q6dBvzOLseKkN33/h240loDWVmcQDSWkOV8=; b=W89tBXlpnTWZZrF3Yz2NTvCKrywErNVhhnuBh6KR130GRQkGsuq46KT6uOo4Os+oEQ 3RMhlOIVV1aXejSc0wpHSxOf55pZPsriBc2rVMMKHBHVJi9NPyawj1mG7f+Q6d9XUxBE 6ERM5Uwzy0/9As/u7FqkFQCWaaUtiLU0HRJoKHc2ifboMgjYXz8t3jRZ4zVmNzTPivv6 0jXRf766w+9BuQ0wW69gdUXge+5sz86bzuRxCbMat0GAQJXYCkNSx1s1l2RZjs2XiH2E FXzWGumSE1wsWPoEhFWrwvZX9q2OUbuGLoxFybU7GdEWa5Vig6p9mTaGaX0buEICc8UG PUug== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:sender:from:to:cc:subject:date:message-id :in-reply-to:references; bh=HilGpFo5q6dBvzOLseKkN33/h240loDWVmcQDSWkOV8=; b=ceLp9Lpq00ov5gy0A4jfF9VsaDzH/jgtpFHVaetiE1iR0h5/VH51vdr8/Re7reaLFb 1ffur06K1JRqeYtNgzpssVjkCHCWy2ZfL55h5HEJCBoGADBWIYHXbSYClTNR1df2nLG4 cdwAnavCwJCa2zu4XKSp9LE7lJCNHSgYK0ARei+e3lYuljBBPQ3scNZ/hpjdrxZELX+f f7xjhBqzSWIUvB09exK7LNvDbR10TLB6u9ahMyPjvJiFlvjIlPUw7jr/Vkcx++sKmbQa q37F/5w3pwE8VOAtVXCO4XJHJnthukxEXVthl5+u2xE4E6GPikJnQa9VpWK7i6aXpSLi 96wg== X-Gm-Message-State: ABUngvclzot1JggHJ/ETABt07guiYSdGuiy2VdRtMzuMn1vUWeBshB3x/ZQgZQ+7/eGbKQ== X-Received: by 10.28.210.1 with SMTP id j1mr10662960wmg.86.1477909620568; Mon, 31 Oct 2016 03:27:00 -0700 (PDT) Received: from haswell.alporthouse.com ([78.156.65.138]) by smtp.gmail.com with ESMTPSA id r4sm24063957wmb.19.2016.10.31.03.26.59 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 31 Oct 2016 03:26:59 -0700 (PDT) From: Chris Wilson To: intel-gfx@lists.freedesktop.org Date: Mon, 31 Oct 2016 10:26:45 +0000 Message-Id: <20161031102645.29495-6-chris@chris-wilson.co.uk> X-Mailer: git-send-email 2.10.2 In-Reply-To: <20161031102645.29495-1-chris@chris-wilson.co.uk> References: <20161031102645.29495-1-chris@chris-wilson.co.uk> Subject: [Intel-gfx] [PATCH 6/6] drm/i915: Store the vma in an rbtree under the object 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-Virus-Scanned: ClamAV using ClamSMTP With full-ppgtt one of the main bottlenecks is the lookup of the VMA underneath the object. For execbuf there is merit in having a very fast direct lookup of ctx:handle to the vma using a hashtree, but that still leaves a large number of other lookups. One way to speed up the lookup would be to use a rhashtable, but that requires extra allocations and may exhibit poor worse case behaviour. An alternative is to use an embedded rbtree, i.e. no extra allocations and deterministic behaviour, but at the slight cost of O(lgN) lookups (instead of O(1) for rhashtable). The major of such tree will be very shallow and so not much slower, and still scales much, much better than the current unsorted list. References: https://bugs.freedesktop.org/show_bug.cgi?id=87726 Signed-off-by: Chris Wilson Reviewed-by: Tvrtko Ursulin --- drivers/gpu/drm/i915/i915_drv.h | 1 + drivers/gpu/drm/i915/i915_gem_gtt.c | 80 +++++++++++++++++++++++++------------ drivers/gpu/drm/i915/i915_gem_gtt.h | 1 + 3 files changed, 57 insertions(+), 25 deletions(-) diff --git a/drivers/gpu/drm/i915/i915_drv.h b/drivers/gpu/drm/i915/i915_drv.h index 7a18bf66f797..e923d6596cac 100644 --- a/drivers/gpu/drm/i915/i915_drv.h +++ b/drivers/gpu/drm/i915/i915_drv.h @@ -2230,6 +2230,7 @@ struct drm_i915_gem_object { /** List of VMAs backed by this object */ struct list_head vma_list; + struct rb_root vma_tree; /** Stolen memory for this object, instead of being backed by shmem. */ struct drm_mm_node *stolen; diff --git a/drivers/gpu/drm/i915/i915_gem_gtt.c b/drivers/gpu/drm/i915/i915_gem_gtt.c index e7afad585929..aa2d21c41091 100644 --- a/drivers/gpu/drm/i915/i915_gem_gtt.c +++ b/drivers/gpu/drm/i915/i915_gem_gtt.c @@ -3399,6 +3399,7 @@ void i915_vma_destroy(struct i915_vma *vma) GEM_BUG_ON(!i915_vma_is_closed(vma)); GEM_BUG_ON(vma->fence); + rb_erase(&vma->obj_node, &vma->obj->vma_tree); list_del(&vma->vm_link); if (!i915_vma_is_ggtt(vma)) i915_ppgtt_put(i915_vm_to_ppgtt(vma->vm)); @@ -3416,12 +3417,33 @@ void i915_vma_close(struct i915_vma *vma) WARN_ON(i915_vma_unbind(vma)); } +static inline int vma_compare(struct i915_vma *vma, + struct i915_address_space *vm, + const struct i915_ggtt_view *view) +{ + GEM_BUG_ON(view && !i915_vma_is_ggtt(vma)); + + if (vma->vm != vm) + return vma->vm - vm; + + if (!view) + return vma->ggtt_view.type; + + if (vma->ggtt_view.type != view->type) + return vma->ggtt_view.type - view->type; + + return memcmp(&vma->ggtt_view.params, + &view->params, + sizeof(view->params)); +} + static struct i915_vma * __i915_vma_create(struct drm_i915_gem_object *obj, struct i915_address_space *vm, const struct i915_ggtt_view *view) { struct i915_vma *vma; + struct rb_node *rb, **p; int i; GEM_BUG_ON(vm->closed); @@ -3455,33 +3477,28 @@ __i915_vma_create(struct drm_i915_gem_object *obj, if (i915_is_ggtt(vm)) { vma->flags |= I915_VMA_GGTT; + list_add(&vma->obj_link, &obj->vma_list); } else { i915_ppgtt_get(i915_vm_to_ppgtt(vm)); + list_add_tail(&vma->obj_link, &obj->vma_list); } - list_add_tail(&vma->obj_link, &obj->vma_list); - return vma; -} + rb = NULL; + p = &obj->vma_tree.rb_node; + while (*p) { + struct i915_vma *pos; -static inline bool vma_matches(struct i915_vma *vma, - struct i915_address_space *vm, - const struct i915_ggtt_view *view) -{ - if (vma->vm != vm) - return false; - - if (!i915_vma_is_ggtt(vma)) - return true; - - if (!view) - return vma->ggtt_view.type == 0; - - if (vma->ggtt_view.type != view->type) - return false; + rb = *p; + pos = rb_entry(rb, struct i915_vma, obj_node); + if (vma_compare(pos, vm, view) < 0) + p = &rb->rb_right; + else + p = &rb->rb_left; + } + rb_link_node(&vma->obj_node, rb, p); + rb_insert_color(&vma->obj_node, &obj->vma_tree); - return memcmp(&vma->ggtt_view.params, - &view->params, - sizeof(view->params)) == 0; + return vma; } struct i915_vma * @@ -3501,11 +3518,22 @@ i915_gem_obj_to_vma(struct drm_i915_gem_object *obj, struct i915_address_space *vm, const struct i915_ggtt_view *view) { - struct i915_vma *vma; + struct rb_node *rb; + + rb = obj->vma_tree.rb_node; + while (rb) { + struct i915_vma *vma; + int cmp; - list_for_each_entry_reverse(vma, &obj->vma_list, obj_link) - if (vma_matches(vma, vm, view)) + vma = rb_entry(rb, struct i915_vma, obj_node); + cmp = vma_compare(vma, vm, view); + if (cmp == 0) return vma; + else if (cmp < 0) + rb = rb->rb_right; + else + rb = rb->rb_left; + } return NULL; } @@ -3521,8 +3549,10 @@ i915_gem_obj_lookup_or_create_vma(struct drm_i915_gem_object *obj, GEM_BUG_ON(view && !i915_is_ggtt(vm)); vma = i915_gem_obj_to_vma(obj, vm, view); - if (!vma) + if (!vma) { vma = __i915_vma_create(obj, vm, view); + GEM_BUG_ON(vma != i915_gem_obj_to_vma(obj, vm, view)); + } GEM_BUG_ON(i915_vma_is_closed(vma)); return vma; diff --git a/drivers/gpu/drm/i915/i915_gem_gtt.h b/drivers/gpu/drm/i915/i915_gem_gtt.h index 518e75b64290..c23ef9db1f53 100644 --- a/drivers/gpu/drm/i915/i915_gem_gtt.h +++ b/drivers/gpu/drm/i915/i915_gem_gtt.h @@ -227,6 +227,7 @@ struct i915_vma { struct list_head vm_link; struct list_head obj_link; /* Link in the object's VMA list */ + struct rb_node obj_node; /** This vma's place in the batchbuffer or on the eviction list */ struct list_head exec_list;