AMD-GFX Archive on lore.kernel.org
 help / color / mirror / Atom feed
From: Chunming Zhou <david1.zhou-5C7GfCeVMHo@public.gmane.org>
To: dri-devel-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org,
	amd-gfx-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org
Cc: Jerry.Zhang-5C7GfCeVMHo@public.gmane.org,
	ckoenig.leichtzumerken-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org,
	Kai.Guo-5C7GfCeVMHo@public.gmane.org,
	Chunming Zhou <david1.zhou-5C7GfCeVMHo@public.gmane.org>
Subject: [PATCH 08/13] drm/amdgpu: use RB tree instead of link list
Date: Wed, 9 May 2018 14:45:38 +0800	[thread overview]
Message-ID: <20180509064543.15937-9-david1.zhou@amd.com> (raw)
In-Reply-To: <20180509064543.15937-1-david1.zhou-5C7GfCeVMHo@public.gmane.org>

Change-Id: Iaca5cdaccbc5beeb7a37c0f703cdfc97df4ece4f
Signed-off-by: Chunming Zhou <david1.zhou@amd.com>
---
 drivers/gpu/drm/amd/amdgpu/amdgpu_object.h |  2 +
 drivers/gpu/drm/amd/amdgpu/amdgpu_ttm.c    |  1 +
 drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c     | 85 +++++++++++++++++++++++++++---
 drivers/gpu/drm/amd/amdgpu/amdgpu_vm.h     |  3 +-
 4 files changed, 82 insertions(+), 9 deletions(-)

diff --git a/drivers/gpu/drm/amd/amdgpu/amdgpu_object.h b/drivers/gpu/drm/amd/amdgpu/amdgpu_object.h
index f04fc401327b..b6396230d30e 100644
--- a/drivers/gpu/drm/amd/amdgpu/amdgpu_object.h
+++ b/drivers/gpu/drm/amd/amdgpu/amdgpu_object.h
@@ -82,6 +82,8 @@ struct amdgpu_bo {
 	struct ttm_placement		placement;
 	struct ttm_buffer_object	tbo;
 	struct ttm_bo_kmap_obj		kmap;
+	struct rb_node			node;
+	u64				index;
 	u64				flags;
 	unsigned			pin_count;
 	u64				tiling_flags;
diff --git a/drivers/gpu/drm/amd/amdgpu/amdgpu_ttm.c b/drivers/gpu/drm/amd/amdgpu/amdgpu_ttm.c
index 207f88f38b23..a5d8f511b011 100644
--- a/drivers/gpu/drm/amd/amdgpu/amdgpu_ttm.c
+++ b/drivers/gpu/drm/amd/amdgpu/amdgpu_ttm.c
@@ -1279,6 +1279,7 @@ static struct ttm_bo_driver amdgpu_bo_driver = {
 	.invalidate_caches = &amdgpu_invalidate_caches,
 	.init_mem_type = &amdgpu_init_mem_type,
 	.eviction_valuable = amdgpu_ttm_bo_eviction_valuable,
+	.lru_empty = &amdgpu_vm_lru_empty,
 	.get_evictable_bo = &amdgpu_vm_get_evictable_bo,
 	.add_to_lru = &amdgpu_vm_add_to_lru,
 	.del_from_lru = &amdgpu_vm_del_from_lru,
diff --git a/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c b/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c
index 27b3fdb6dd46..1a09c07bbf20 100644
--- a/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c
+++ b/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c
@@ -133,7 +133,7 @@ int amdgpu_vm_lru_init(struct amdgpu_vm_lru *vm_lru, struct amdgpu_device *adev,
 	INIT_LIST_HEAD(&vm_lru->vm_lru_list);
 	for (i = 0; i < TTM_NUM_MEM_TYPES; i++) {
 		for (j = 0; j < TTM_MAX_BO_PRIORITY; j++) {
-			INIT_LIST_HEAD(&vm_lru->fixed_lru[i][j]);
+			vm_lru->fixed_lru[i][j] = RB_ROOT;
 			INIT_LIST_HEAD(&vm_lru->dynamic_lru[i][j]);
 		}
 	}
@@ -157,6 +157,24 @@ int amdgpu_vm_lru_fini(struct amdgpu_vm_lru *vm_lru, struct amdgpu_device *adev)
 	return 0;
 }
 
+bool amdgpu_vm_lru_empty(struct ttm_bo_device *bdev, unsigned mem_type)
+{
+	struct amdgpu_device *adev = amdgpu_ttm_adev(bdev);
+	struct amdgpu_vm_lru *vm_lru;
+	int i;
+
+	for (i = 0; i < TTM_MAX_BO_PRIORITY; ++i) {
+		list_for_each_entry(vm_lru, &adev->vm_lru_list, vm_lru_list) {
+			if (!list_empty(&vm_lru->dynamic_lru[mem_type][i]))
+				return false;
+			if (!RB_EMPTY_ROOT(&vm_lru->fixed_lru[mem_type][i]))
+				return false;
+		}
+	}
+
+	return true;
+}
+
 struct ttm_buffer_object *amdgpu_vm_get_evictable_bo(struct ttm_bo_device *bdev,
 						     uint32_t mem_type,
 						     const struct ttm_place *place,
@@ -165,11 +183,13 @@ struct ttm_buffer_object *amdgpu_vm_get_evictable_bo(struct ttm_bo_device *bdev,
 {
 	struct amdgpu_device *adev = amdgpu_ttm_adev(bdev);
 	struct ttm_buffer_object *bo = NULL;
+	struct amdgpu_bo *abo = NULL;
 	struct amdgpu_vm_lru *vm_lru;
 	int i;
 
 	for (i = 0; i < TTM_MAX_BO_PRIORITY; ++i) {
 		list_for_each_entry(vm_lru, &adev->vm_lru_list, vm_lru_list) {
+			struct rb_node *node;
 			list_for_each_entry(bo, &vm_lru->dynamic_lru[mem_type][i], lru) {
 				if (!ttm_bo_evict_swapout_allowable(bo, ctx, locked))
 					continue;
@@ -184,20 +204,22 @@ struct ttm_buffer_object *amdgpu_vm_get_evictable_bo(struct ttm_bo_device *bdev,
 			if (&bo->lru != &vm_lru->dynamic_lru[mem_type][i])
 				break;
 			bo = NULL;
-			list_for_each_entry(bo, &vm_lru->fixed_lru[mem_type][i], lru) {
-				if (!ttm_bo_evict_swapout_allowable(bo, ctx, locked))
+			for (node = rb_first(&vm_lru->fixed_lru[mem_type][i]);
+			     node; node = rb_next(node)) {
+				abo = rb_entry(node, struct amdgpu_bo, node);
+				bo = &abo->tbo;
+				if (!ttm_bo_evict_swapout_allowable(bo, ctx, locked)) {
+					bo = NULL;
 					continue;
+				}
 				if (place && !bdev->driver->eviction_valuable(bo, place)) {
 					if (locked)
 						reservation_object_unlock(bo->resv);
+					bo = NULL;
 					continue;
 				}
 				break;
 			}
-			/* If the inner loop terminated early, we have our candidate */
-			if (&bo->lru != &vm_lru->fixed_lru[mem_type][i])
-				break;
-			bo = NULL;
 		}
 		if (bo)
 			break;
@@ -207,6 +229,26 @@ struct ttm_buffer_object *amdgpu_vm_get_evictable_bo(struct ttm_bo_device *bdev,
 
 }
 
+static void amdgpu_vm_bo_add_to_rb(struct amdgpu_bo *bo,
+				   struct rb_root *root)
+{
+	struct rb_node **new = &(root->rb_node), *parent = NULL;
+
+	while (*new) {
+		struct amdgpu_bo *this =
+			container_of(*new, struct amdgpu_bo, node);
+
+		parent = *new;
+		if (bo->index < this->index)
+			new = &((*new)->rb_left);
+		else
+			new = &((*new)->rb_right);
+	}
+
+	rb_link_node(&bo->node, parent, new);
+	rb_insert_color(&bo->node, root);
+}
+
 void amdgpu_vm_add_to_lru(struct ttm_buffer_object *bo)
 {
 	struct ttm_bo_device *bdev = bo->bdev;
@@ -215,7 +257,7 @@ void amdgpu_vm_add_to_lru(struct ttm_buffer_object *bo)
 
 	if (!(bo->mem.placement & TTM_PL_FLAG_NO_EVICT)) {
 		if (bo->resv == vm_lru->resv)
-			list_add_tail(&bo->lru, &vm_lru->fixed_lru[bo->mem.mem_type][bo->priority]);
+			amdgpu_vm_bo_add_to_rb(abo, &vm_lru->fixed_lru[bo->mem.mem_type][bo->priority]);
 		else
 			list_add_tail(&bo->lru, &vm_lru->dynamic_lru[bo->mem.mem_type][bo->priority]);
 		kref_get(&bo->list_kref);
@@ -230,9 +272,36 @@ void amdgpu_vm_add_to_lru(struct ttm_buffer_object *bo)
 
 }
 
+static struct amdgpu_bo *amdgpu_vm_bo_rb_find(struct rb_root *root, u64 index)
+{
+	struct rb_node *node = root->rb_node;
+
+	while (node) {
+		struct amdgpu_bo *bo =
+			container_of(node, struct amdgpu_bo, node);
+
+	if (index < bo->index)
+		node = node->rb_left;
+	else if (index > bo->index)
+		node = node->rb_right;
+	else
+		return bo;
+	}
+
+	return NULL;
+}
+
 void amdgpu_vm_del_from_lru(struct ttm_buffer_object *bo)
 {
+	struct amdgpu_bo *abo = ttm_to_amdgpu_bo(bo);
+	struct amdgpu_vm_lru *vm_lru = abo->vm_lru;
 
+	if (amdgpu_vm_bo_rb_find(&vm_lru->fixed_lru[bo->mem.mem_type][bo->priority],
+				 abo->index)) {
+		rb_erase(&abo->node,
+			 &vm_lru->fixed_lru[abo->tbo.mem.mem_type][abo->tbo.priority]);
+		kref_put(&abo->tbo.list_kref, ttm_bo_ref_bug);
+	}
 }
 
 void amdgpu_vm_move_to_lru_tail(struct ttm_buffer_object *bo)
diff --git a/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.h b/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.h
index 66ee902614a2..84400673d710 100644
--- a/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.h
+++ b/drivers/gpu/drm/amd/amdgpu/amdgpu_vm.h
@@ -138,7 +138,7 @@ enum amdgpu_vm_level {
 
 struct amdgpu_vm_lru {
 	struct list_head vm_lru_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;
 };
@@ -269,6 +269,7 @@ int amdgpu_vm_lru_init(struct amdgpu_vm_lru *vm_lru, struct amdgpu_device *adev,
 		       struct reservation_object *resv);
 int amdgpu_vm_lru_fini(struct amdgpu_vm_lru *vm_lru,
 		       struct amdgpu_device *adev);
+bool amdgpu_vm_lru_empty(struct ttm_bo_device *bdev, unsigned mem_type);
 
 struct ttm_buffer_object *amdgpu_vm_get_evictable_bo(struct ttm_bo_device *bdev,
 						     uint32_t mem_type,
-- 
2.14.1

_______________________________________________
amd-gfx mailing list
amd-gfx@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/amd-gfx

  parent reply	other threads:[~2018-05-09  6:45 UTC|newest]

Thread overview: 22+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-05-09  6:45 [PATCH 00/13] *** per vm lru *** Chunming Zhou
2018-05-09  6:45 ` [PATCH 03/13] drm/amdgpu: add lru backend for amdgpu driver Chunming Zhou
     [not found] ` <20180509064543.15937-1-david1.zhou-5C7GfCeVMHo@public.gmane.org>
2018-05-09  6:45   ` [PATCH 01/13] ttm: abstruct evictable bo Chunming Zhou
2018-05-09  8:34     ` Lucas Stach
2018-05-09  9:50       ` Daniel Vetter
2018-05-09 10:06         ` zhoucm1
2018-05-09 16:04           ` Alex Deucher
2018-05-09  6:45   ` [PATCH 02/13] ttm: allow driver has own lru policy Chunming Zhou
2018-05-09  6:45   ` [PATCH 04/13] drm/amdgpu: init/fini vm lru Chunming Zhou
2018-05-09  6:45   ` Chunming Zhou [this message]
2018-05-09  6:45   ` [PATCH 09/13] drm/amdgpu: add bo index counter Chunming Zhou
2018-05-09  6:45   ` [PATCH 10/13] drm/amdgpu: bulk move per vm bo Chunming Zhou
2018-05-09  6:45   ` [PATCH 12/13] drm/amdgpu: transferred bo doesn't use vm lru Chunming Zhou
2018-05-09  6:45   ` [PATCH 13/13] drm/amdgpu: free vm lru when vm fini Chunming Zhou
2018-05-09  6:45 ` [PATCH 05/13] drm/amdgpu: pass vm lru to buffer object Chunming Zhou
2018-05-09  6:45 ` [PATCH 06/13] drm/amdgpu: add amdgpu lru implementation Chunming Zhou
2018-05-09  6:45 ` [PATCH 07/13] drm/ttm: export ttm_bo_ref_bug Chunming Zhou
2018-05-09  6:45 ` [PATCH 11/13] ttm: export ttm_transfered_destroy Chunming Zhou
2018-05-10  5:07 ` [PATCH 00/13] *** per vm lru *** Zhang, Jerry (Junwei)
     [not found]   ` <5AF3D38F.1040704-5C7GfCeVMHo@public.gmane.org>
2018-05-10  8:45     ` zhoucm1
2018-05-14  5:44       ` Zhang, Jerry (Junwei)
     [not found]       ` <8c18f05c-54bc-47c8-8d63-8610420238cc-5C7GfCeVMHo@public.gmane.org>
2018-05-14  5:54         ` Zhang, Jerry (Junwei)

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20180509064543.15937-9-david1.zhou@amd.com \
    --to=david1.zhou-5c7gfcevmho@public.gmane.org \
    --cc=Jerry.Zhang-5C7GfCeVMHo@public.gmane.org \
    --cc=Kai.Guo-5C7GfCeVMHo@public.gmane.org \
    --cc=amd-gfx-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org \
    --cc=ckoenig.leichtzumerken-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org \
    --cc=dri-devel-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox