drm/i915/gvt: Manage shadow pages with radix tree
authorChangbin Du <changbin.du@intel.com>
Tue, 30 Jan 2018 11:19:54 +0000 (19:19 +0800)
committerZhenyu Wang <zhenyuw@linux.intel.com>
Tue, 6 Mar 2018 05:19:21 +0000 (13:19 +0800)
commitb6c126a39345f7286bb25135efd9154419127427
treee36ba0c57197cdbf65da730c5b84e066e19b5d50
parente502a2af4c358d14ecf8fce51bf4988ebb4d10b4
drm/i915/gvt: Manage shadow pages with radix tree

We don't know how many page tables will be shadowed. It varies
considerably corresponding to guest load. Radix tree is a better
choice for us. Since Page Frame Number is used as key so most of
the bits are common.

Here is some performance data (duration in us) of looking up a
element:
Before: (aka. ppgtt_find_shadow_page)
 0.308 0.292 0.246 0.432 0.143 ... 0.311 0.225 0.382 0.199 0.325
After: (aka. intel_vgpu_find_spt_by_mfn)
 0.106 0.106 0.107 0.106 0.105 0.107 ... 0.107 0.109 0.105 0.108

This time I didn't get the early data of hash table. The data is
measured when desktop is shown.

As last change, the overall benchmark almost is not changed, but
we get better scalability.

Signed-off-by: Changbin Du <changbin.du@intel.com>
Signed-off-by: Zhenyu Wang <zhenyuw@linux.intel.com>
drivers/gpu/drm/i915/gvt/gtt.c
drivers/gpu/drm/i915/gvt/gtt.h