drm/i915: Store the vma in an rbtree under the object
authorChris Wilson <chris@chris-wilson.co.uk>
Tue, 1 Nov 2016 11:54:00 +0000 (11:54 +0000)
committerChris Wilson <chris@chris-wilson.co.uk>
Tue, 1 Nov 2016 13:00:40 +0000 (13:00 +0000)
commitdb6c2b4151f2915fe1695cdcac43b32e73d1ad32
tree1aab9afcad5d46969a5bc31cd8a8d73c87b7efad
parentbc0629a76726991f97ee88c65b87e99dd94c1dc4
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 <chris@chris-wilson.co.uk>
Reviewed-by: Tvrtko Ursulin <tvrtko.ursulin@intel.com>
Link: http://patchwork.freedesktop.org/patch/msgid/20161101115400.15647-1-chris@chris-wilson.co.uk
drivers/gpu/drm/i915/i915_drv.h
drivers/gpu/drm/i915/i915_gem.c
drivers/gpu/drm/i915/i915_gem_gtt.c
drivers/gpu/drm/i915/i915_gem_gtt.h