[PATCH v2 15/15] drm/i915/gvt: Manage shadow pages with radix tree

[changbin.du at intel.com]

From: Changbin Du <changbin.du at intel.com>

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.

Signed-off-by: Changbin Du <changbin.du at intel.com>
---
 drivers/gpu/drm/i915/gvt/gtt.c | 48 ++++++++++++++++++++++--------------------
 drivers/gpu/drm/i915/gvt/gtt.h |  4 +---
 2 files changed, 26 insertions(+), 26 deletions(-)

diff --git a/drivers/gpu/drm/i915/gvt/gtt.c b/drivers/gpu/drm/i915/gvt/gtt.c
index 2ed7dbb..c6ef2d1 100644
--- a/drivers/gpu/drm/i915/gvt/gtt.c
+++ b/drivers/gpu/drm/i915/gvt/gtt.c
@@ -640,8 +640,8 @@ static void ppgtt_free_spt(struct intel_vgpu_ppgtt_spt *spt)
 
 	dma_unmap_page(kdev, spt->shadow_page.mfn << I915_GTT_PAGE_SHIFT, 4096,
 		       PCI_DMA_BIDIRECTIONAL);
-	if (!hlist_unhashed(&spt->node))
-		hash_del(&spt->node);
+
+	radix_tree_delete(&spt->vgpu->gtt.spt_tree, spt->shadow_page.mfn);
 
 	if (spt->guest_page.oos_page)
 		detach_oos_page(spt->vgpu, spt->guest_page.oos_page);
@@ -654,12 +654,14 @@ static void ppgtt_free_spt(struct intel_vgpu_ppgtt_spt *spt)
 
 static void ppgtt_free_all_spt(struct intel_vgpu *vgpu)
 {
-	struct hlist_node *n;
 	struct intel_vgpu_ppgtt_spt *spt;
-	int i;
+	struct radix_tree_iter iter;
+	void **slot;
 
-	hash_for_each_safe(vgpu->gtt.spt_hash_table, i, n, spt, node)
+	radix_tree_for_each_slot(slot, &vgpu->gtt.spt_tree, &iter, 0) {
+		spt = radix_tree_deref_slot(slot);
 		ppgtt_free_spt(spt);
+	}
 }
 
 static int ppgtt_handle_guest_write_page_table_bytes(
@@ -697,16 +699,10 @@ static struct intel_vgpu_ppgtt_spt *intel_vgpu_find_spt_by_gfn(
 }
 
 /* Find the spt by shadow page mfn. */
-static struct intel_vgpu_ppgtt_spt *intel_vgpu_find_spt_by_mfn(
+static inline struct intel_vgpu_ppgtt_spt *intel_vgpu_find_spt_by_mfn(
 		struct intel_vgpu *vgpu, unsigned long mfn)
 {
-	struct intel_vgpu_ppgtt_spt *spt;
-
-	hash_for_each_possible(vgpu->gtt.spt_hash_table, spt, node, mfn) {
-		if (spt->shadow_page.mfn == mfn)
-			return spt;
-	}
-	return NULL;
+	return radix_tree_lookup(&vgpu->gtt.spt_tree, mfn);
 }
 
 static int reclaim_one_ppgtt_mm(struct intel_gvt *gvt);
@@ -741,8 +737,8 @@ static struct intel_vgpu_ppgtt_spt *ppgtt_alloc_spt(
 			     0, 4096, PCI_DMA_BIDIRECTIONAL);
 	if (dma_mapping_error(kdev, daddr)) {
 		gvt_vgpu_err("fail to map dma addr\n");
-		free_spt(spt);
-		return ERR_PTR(-EINVAL);
+		ret = -EINVAL;
+		goto err_free_spt;
 	}
 	spt->shadow_page.vaddr = page_address(spt->shadow_page.page);
 	spt->shadow_page.mfn = daddr >> I915_GTT_PAGE_SHIFT;
@@ -755,17 +751,23 @@ static struct intel_vgpu_ppgtt_spt *ppgtt_alloc_spt(
 
 	ret = intel_vgpu_register_page_track(vgpu, spt->guest_page.gfn,
 					ppgtt_write_protection_handler, spt);
-	if (ret) {
-		free_spt(spt);
-		dma_unmap_page(kdev, daddr, PAGE_SIZE, PCI_DMA_BIDIRECTIONAL);
-		return ERR_PTR(ret);
-	}
+	if (ret)
+		goto err_unmap_dma;
 
-	INIT_HLIST_NODE(&spt->node);
-	hash_add(vgpu->gtt.spt_hash_table, &spt->node, spt->shadow_page.mfn);
+	ret = radix_tree_insert(&vgpu->gtt.spt_tree, spt->shadow_page.mfn, spt);
+	if (ret)
+		goto err_unreg_page_track;
 
 	trace_spt_alloc(vgpu->id, spt, type, spt->shadow_page.mfn, gfn);
 	return spt;
+
+err_unreg_page_track:
+	intel_vgpu_unregister_page_track(vgpu, spt->guest_page.gfn);
+err_unmap_dma:
+	dma_unmap_page(kdev, daddr, PAGE_SIZE, PCI_DMA_BIDIRECTIONAL);
+err_free_spt:
+	free_spt(spt);
+	return ERR_PTR(ret);
 }
 
 #define pt_entry_size_shift(spt) \
@@ -1967,7 +1969,7 @@ int intel_vgpu_init_gtt(struct intel_vgpu *vgpu)
 {
 	struct intel_vgpu_gtt *gtt = &vgpu->gtt;
 
-	hash_init(gtt->spt_hash_table);
+	INIT_RADIX_TREE(&gtt->spt_tree, GFP_KERNEL);
 
 	INIT_LIST_HEAD(&gtt->ppgtt_mm_list_head);
 	INIT_LIST_HEAD(&gtt->oos_page_list_head);
diff --git a/drivers/gpu/drm/i915/gvt/gtt.h b/drivers/gpu/drm/i915/gvt/gtt.h
index a7fddab..6fcd499 100644
--- a/drivers/gpu/drm/i915/gvt/gtt.h
+++ b/drivers/gpu/drm/i915/gvt/gtt.h
@@ -39,7 +39,6 @@
 
 struct intel_vgpu_mm;
 
-#define INTEL_GVT_GTT_HASH_BITS 8
 #define INTEL_GVT_INVALID_ADDR (~0UL)
 
 struct intel_gvt_gtt_entry {
@@ -179,7 +178,7 @@ struct intel_vgpu_gtt {
 	struct intel_vgpu_mm *ggtt_mm;
 	unsigned long active_ppgtt_mm_bitmap;
 	struct list_head ppgtt_mm_list_head;
-	DECLARE_HASHTABLE(spt_hash_table, INTEL_GVT_GTT_HASH_BITS);
+	struct radix_tree_root spt_tree;
 	struct list_head oos_page_list_head;
 	struct list_head post_shadow_list_head;
 	struct intel_vgpu_scratch_pt scratch_pt[GTT_TYPE_MAX];
@@ -210,7 +209,6 @@ struct intel_vgpu_oos_page {
 struct intel_vgpu_ppgtt_spt {
 	atomic_t refcount;
 	struct intel_vgpu *vgpu;
-	struct hlist_node node;
 
 	struct {
 		intel_gvt_gtt_type_t type;
-- 
2.7.4