From db6c2b4151f2915fe1695cdcac43b32e73d1ad32 Mon Sep 17 00:00:00 2001 From: Chris Wilson Date: Tue, 1 Nov 2016 11:54:00 +0000 Subject: [PATCH] drm/i915: Store the vma in an rbtree under the object 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. v2: Bump vma_compare() to return a long, as we return the result of comparing two pointers. References: https://bugs.freedesktop.org/show_bug.cgi?id=87726 Signed-off-by: Chris Wilson Reviewed-by: Tvrtko Ursulin Link: http://patchwork.freedesktop.org/patch/msgid/20161101115400.15647-1-chris@chris-wilson.co.uk --- drivers/gpu/drm/i915/i915_drv.h | 1 + drivers/gpu/drm/i915/i915_gem.c | 2 + drivers/gpu/drm/i915/i915_gem_gtt.c | 80 +++++++++++++++++++++++++------------ drivers/gpu/drm/i915/i915_gem_gtt.h | 1 + 4 files changed, 59 insertions(+), 25 deletions(-) diff --git a/drivers/gpu/drm/i915/i915_drv.h b/drivers/gpu/drm/i915/i915_drv.h index 539106a..9143129 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.c b/drivers/gpu/drm/i915/i915_gem.c index c9e52f7..1568f67 100644 --- a/drivers/gpu/drm/i915/i915_gem.c +++ b/drivers/gpu/drm/i915/i915_gem.c @@ -4266,6 +4266,8 @@ static void __i915_gem_free_objects(struct drm_i915_private *i915, vma->flags &= ~I915_VMA_PIN_MASK; i915_vma_close(vma); } + GEM_BUG_ON(!list_empty(&obj->vma_list)); + GEM_BUG_ON(!RB_EMPTY_ROOT(&obj->vma_tree)); list_del(&obj->global_list); } diff --git a/drivers/gpu/drm/i915/i915_gem_gtt.c b/drivers/gpu/drm/i915/i915_gem_gtt.c index e7afad5..00606a2 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 long 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,12 +3518,23 @@ 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 = rb_entry(rb, struct i915_vma, obj_node); + long cmp; - list_for_each_entry_reverse(vma, &obj->vma_list, obj_link) - if (vma_matches(vma, vm, view)) + cmp = vma_compare(vma, vm, view); + if (cmp == 0) return vma; + 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 518e75b..c23ef9d 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; -- 2.7.4