[Intel-gfx] [PATCH 6/6] drm/i915: Store the vma in an rbtree under the object

[Tvrtko Ursulin]

On 31/10/2016 10:26, Chris Wilson wrote:
> 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 <chris at chris-wilson.co.uk>

I suggest leaving this out of the mini-series which fixes the recently 
introduced bugs.

Regards,

Tvrtko


> ---
>  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;
>