[PATCH 07/11] drm/ttm: use RB tree instead of link list

[Chunming Zhou]

Change-Id: I0f533c6512f3b72fcf2fbf11d738f38d9e087f26
Signed-off-by: Chunming Zhou <david1.zhou at amd.com>
---
 drivers/gpu/drm/ttm/ttm_bo.c    | 39 +++++++++++++++++++++++++++++++--------
 include/drm/ttm/ttm_bo_api.h    |  3 ++-
 include/drm/ttm/ttm_bo_driver.h |  2 +-
 3 files changed, 34 insertions(+), 10 deletions(-)

diff --git a/drivers/gpu/drm/ttm/ttm_bo.c b/drivers/gpu/drm/ttm/ttm_bo.c
index c1d0ec1238c6..73343d1108d2 100644
--- a/drivers/gpu/drm/ttm/ttm_bo.c
+++ b/drivers/gpu/drm/ttm/ttm_bo.c
@@ -157,6 +157,26 @@ static void ttm_bo_release_list(struct kref *list_kref)
 	ttm_mem_global_free(bdev->glob->mem_glob, acc_size);
 }
 
+static void ttm_bo_add_to_rb(struct ttm_buffer_object *bo,
+			     struct rb_root *root) {
+	struct rb_node **new = &(root->rb_node), *parent = NULL;
+
+        while (*new) {
+		struct ttm_buffer_object *this =
+			container_of(*new, struct ttm_buffer_object, node);
+		int result = bo->index - this->index;
+
+		parent = *new;
+		if (result < 0)
+			new = &((*new)->rb_left);
+		else if (result > 0)
+			new = &((*new)->rb_right);
+		else
+			return;
+	}
+	rb_link_node(&bo->node, parent, new);
+	rb_insert_color(&bo->node, root);
+}
 void ttm_bo_add_to_lru(struct ttm_buffer_object *bo)
 {
 	struct ttm_bo_device *bdev = bo->bdev;
@@ -170,7 +190,7 @@ void ttm_bo_add_to_lru(struct ttm_buffer_object *bo)
 
 		kref_get(&bo->list_kref);
 		if (bo->resv == ttm_process->resv)
-			list_add_tail(&bo->lru,
+			ttm_bo_add_to_rb(bo,
 				      &ttm_process->fixed_lru[bo->mem.mem_type][bo->priority]);
 		else
 			list_add_tail(&bo->lru,
@@ -200,8 +220,12 @@ void ttm_bo_del_from_lru(struct ttm_buffer_object *bo)
 	if (!list_empty(&bo->lru)) {
 		list_del_init(&bo->lru);
 		kref_put(&bo->list_kref, ttm_bo_ref_bug);
+	} else if (RB_EMPTY_NODE(&bo->node)) {
+		rb_erase(&bo->node,
+			 &bo->process->fixed_lru[bo->mem.mem_type][bo->priority]);
+		RB_CLEAR_NODE(&bo->node);
+		kref_put(&bo->list_kref, ttm_bo_ref_bug);
 	}
-
 	/*
 	 * TODO: Add a driver hook to delete from
 	 * driver-specific LRU's here.
@@ -725,6 +749,7 @@ static int ttm_mem_evict_first(struct ttm_bo_device *bdev,
 	spin_lock(&glob->lru_lock);
 	for (i = 0; i < TTM_MAX_BO_PRIORITY; ++i) {
 	list_for_each_entry(process, &bdev->process_list, process_list) {
+		struct rb_node *node;
 		list_for_each_entry(bo, &process->dynamic_lru[mem_type][i], lru) {
 			if (!ttm_bo_evict_swapout_allowable(bo, ctx, &locked))
 				continue;
@@ -741,11 +766,9 @@ static int ttm_mem_evict_first(struct ttm_bo_device *bdev,
 		if (&bo->lru != &process->dynamic_lru[mem_type][i])
 			break;
 		bo = NULL;
-		list_for_each_entry(bo, &process->fixed_lru[mem_type][i], lru) {
-			if (!bo)
-				continue;
-			if (&bo->lru == &process->fixed_lru[mem_type][i])
-				break;
+		for (node = rb_first(&process->fixed_lru[mem_type][i]); node;
+		     node = rb_next(node)) {
+			bo = rb_entry(node, struct ttm_buffer_object, node);
 			if (!ttm_bo_evict_swapout_allowable(bo, ctx, &locked))
 				continue;
 
@@ -1609,7 +1632,7 @@ int ttm_process_init(struct ttm_process *process, struct ttm_bo_device *bdev,
 	INIT_LIST_HEAD(&process->process_list);
 	for (i = 0; i < TTM_NUM_MEM_TYPES; i++) {
 		for (j = 0; j < TTM_MAX_BO_PRIORITY; j++) {
-			INIT_LIST_HEAD(&process->fixed_lru[i][j]);
+			process->fixed_lru[i][j] = RB_ROOT;
 			INIT_LIST_HEAD(&process->dynamic_lru[i][j]);
 		}
 	}
diff --git a/include/drm/ttm/ttm_bo_api.h b/include/drm/ttm/ttm_bo_api.h
index 8cb4b48f387a..9c8179bdd685 100644
--- a/include/drm/ttm/ttm_bo_api.h
+++ b/include/drm/ttm/ttm_bo_api.h
@@ -170,7 +170,7 @@ struct ttm_buffer_object {
 	/**
 	 * Members constant at init.
 	 */
-
+	struct rb_node node;
 	struct ttm_bo_device *bdev;
 	struct ttm_process *process;
 	enum ttm_bo_type type;
@@ -232,6 +232,7 @@ struct ttm_buffer_object {
 	struct reservation_object *resv;
 	struct reservation_object ttm_resv;
 	struct mutex wu_mutex;
+	u64	index;
 };
 
 /**
diff --git a/include/drm/ttm/ttm_bo_driver.h b/include/drm/ttm/ttm_bo_driver.h
index b6aa7fc5bf14..818aee15d1ec 100644
--- a/include/drm/ttm/ttm_bo_driver.h
+++ b/include/drm/ttm/ttm_bo_driver.h
@@ -440,7 +440,7 @@ struct ttm_bo_global {
 
 struct ttm_process {
 	struct list_head process_list;
-	struct list_head fixed_lru[TTM_NUM_MEM_TYPES][TTM_MAX_BO_PRIORITY];
+	struct rb_root fixed_lru[TTM_NUM_MEM_TYPES][TTM_MAX_BO_PRIORITY];
 	struct list_head dynamic_lru[TTM_NUM_MEM_TYPES][TTM_MAX_BO_PRIORITY];
 	struct reservation_object *resv;
 };
-- 
2.14.1