[PATCH 0/4] TTM unlockable restartable LRU list iteration

[PATCH 0/4] TTM unlockable restartable LRU list iteration

[Thomas Hellström]

This patch-set is a prerequisite for a standalone TTM shrinker
and for exhaustive TTM eviction using sleeping dma_resv locks,
which is the motivation it.

Currently when unlocking the TTM lru list lock, iteration needs
to be restarted from the beginning, rather from the next LRU list
node. This can potentially be a big problem, because if eviction
or shrinking fails for whatever reason after unlock, restarting
is likely to cause the same failure over and over again.

There are various schemes to be able to continue the list
iteration from where we left off. One such scheme used by the
GEM LRU list traversal is to pull items already considered off
the LRU list and reinsert them when iteration is done.
This has the drawback that concurrent list iteration doesn't see
the complete list (which is bad for exhaustive eviction) and also
doesn't lend itself well to bulk-move sublists since these will
be split in the process where items from those lists are
temporarily pulled from the list and moved to the list tail.

The approach taken here is that list iterators insert themselves
into the list next position using a special list node. Iteration
is then using that list node as starting point when restarting.
Concurrent iterators just skip over the special list nodes.

This is implemented in patch 1 and 2.

For bulk move sublist the approach is the same, but when a bulk
move sublist is moved to the tail, the iterator is also moved,
causing us to skip parts of the list. That is undesirable.
Patch 3 deals with that, and when iterator detects it is
traversing a sublist, it inserts a second restarting point just
after the sublist and if the sublist is moved to the tail,
it just uses the second restarting point instead.

This is implemented in patch 3.

The restartable property is used in patch 4 to restart swapout if
needed, but the main purpose is this paves the way for
shrinker- and exhaustive eviction.

Cc: Christian König <christian.koenig@amd.com>
Cc: <dri-devel@lists.freedesktop.org>

Thomas Hellström (4):
  drm/ttm: Allow TTM LRU list nodes of different types
  drm/ttm: Use LRU hitches
  drm/ttm: Consider hitch moves within bulk sublist moves
  drm/ttm: Allow continued swapout after -ENOSPC falure

 drivers/gpu/drm/ttm/ttm_bo.c       |   1 +
 drivers/gpu/drm/ttm/ttm_device.c   |  33 +++--
 drivers/gpu/drm/ttm/ttm_resource.c | 202 +++++++++++++++++++++++------
 include/drm/ttm/ttm_resource.h     |  91 +++++++++++--
 4 files changed, 267 insertions(+), 60 deletions(-)

-- 
2.43.0

[PATCH 1/4] drm/ttm: Allow TTM LRU list nodes of different types

[Thomas Hellström]

To be able to handle list unlocking while traversing the LRU
list, we want the iterators not only to point to the next
position of the list traversal, but to insert themselves as
list nodes at that point to work around the fact that the
next node might otherwise disappear from the list while
the iterator is pointing to it.

These list nodes need to be easily distinguishable from other
list nodes so that others traversing the list can skip
over them.

So declare a struct ttm_lru_item, with a struct list_head member
and a type enum. This will slightly increase the size of a
struct ttm_resource.

Cc: Christian König <christian.koenig@amd.com>
Cc: <dri-devel@lists.freedesktop.org>
Signed-off-by: Thomas Hellström <thomas.hellstrom@linux.intel.com>
---
 drivers/gpu/drm/ttm/ttm_device.c   | 13 ++++--
 drivers/gpu/drm/ttm/ttm_resource.c | 70 ++++++++++++++++++++++--------
 include/drm/ttm/ttm_resource.h     | 51 +++++++++++++++++++++-
 3 files changed, 110 insertions(+), 24 deletions(-)

diff --git a/drivers/gpu/drm/ttm/ttm_device.c b/drivers/gpu/drm/ttm/ttm_device.c
index 76027960054f..f27406e851e5 100644
--- a/drivers/gpu/drm/ttm/ttm_device.c
+++ b/drivers/gpu/drm/ttm/ttm_device.c
@@ -270,17 +270,22 @@ EXPORT_SYMBOL(ttm_device_fini);
 static void ttm_device_clear_lru_dma_mappings(struct ttm_device *bdev,
 					      struct list_head *list)
 {
-	struct ttm_resource *res;
+	struct ttm_lru_item *lru;
 
 	spin_lock(&bdev->lru_lock);
-	while ((res = list_first_entry_or_null(list, typeof(*res), lru))) {
-		struct ttm_buffer_object *bo = res->bo;
+	while ((lru = list_first_entry_or_null(list, typeof(*lru), link))) {
+		struct ttm_buffer_object *bo;
+
+		if (!ttm_lru_item_is_res(lru))
+			continue;
+
+		bo = ttm_lru_item_to_res(lru)->bo;
 
 		/* Take ref against racing releases once lru_lock is unlocked */
 		if (!ttm_bo_get_unless_zero(bo))
 			continue;
 
-		list_del_init(&res->lru);
+		list_del_init(&bo->resource->lru.link);
 		spin_unlock(&bdev->lru_lock);
 
 		if (bo->ttm)
diff --git a/drivers/gpu/drm/ttm/ttm_resource.c b/drivers/gpu/drm/ttm/ttm_resource.c
index fb14f7716cf8..0b8beb356b8a 100644
--- a/drivers/gpu/drm/ttm/ttm_resource.c
+++ b/drivers/gpu/drm/ttm/ttm_resource.c
@@ -69,8 +69,8 @@ void ttm_lru_bulk_move_tail(struct ttm_lru_bulk_move *bulk)
 			dma_resv_assert_held(pos->last->bo->base.resv);
 
 			man = ttm_manager_type(pos->first->bo->bdev, i);
-			list_bulk_move_tail(&man->lru[j], &pos->first->lru,
-					    &pos->last->lru);
+			list_bulk_move_tail(&man->lru[j], &pos->first->lru.link,
+					    &pos->last->lru.link);
 		}
 	}
 }
@@ -83,14 +83,38 @@ ttm_lru_bulk_move_pos(struct ttm_lru_bulk_move *bulk, struct ttm_resource *res)
 	return &bulk->pos[res->mem_type][res->bo->priority];
 }
 
+/* Return the previous resource on the list (skip over non-resource list items) */
+static struct ttm_resource *ttm_lru_prev_res(struct ttm_resource *cur)
+{
+	struct ttm_lru_item *lru = &cur->lru;
+
+	do {
+		lru = list_prev_entry(lru, link);
+	} while (!ttm_lru_item_is_res(lru));
+
+	return ttm_lru_item_to_res(lru);
+}
+
+/* Return the next resource on the list (skip over non-resource list items) */
+static struct ttm_resource *ttm_lru_next_res(struct ttm_resource *cur)
+{
+	struct ttm_lru_item *lru = &cur->lru;
+
+	do {
+		lru = list_next_entry(lru, link);
+	} while (!ttm_lru_item_is_res(lru));
+
+	return ttm_lru_item_to_res(lru);
+}
+
 /* Move the resource to the tail of the bulk move range */
 static void ttm_lru_bulk_move_pos_tail(struct ttm_lru_bulk_move_pos *pos,
 				       struct ttm_resource *res)
 {
 	if (pos->last != res) {
 		if (pos->first == res)
-			pos->first = list_next_entry(res, lru);
-		list_move(&res->lru, &pos->last->lru);
+			pos->first = ttm_lru_next_res(res);
+		list_move(&res->lru.link, &pos->last->lru.link);
 		pos->last = res;
 	}
 }
@@ -120,11 +144,11 @@ static void ttm_lru_bulk_move_del(struct ttm_lru_bulk_move *bulk,
 		pos->first = NULL;
 		pos->last = NULL;
 	} else if (pos->first == res) {
-		pos->first = list_next_entry(res, lru);
+		pos->first = ttm_lru_next_res(res);
 	} else if (pos->last == res) {
-		pos->last = list_prev_entry(res, lru);
+		pos->last = ttm_lru_prev_res(res);
 	} else {
-		list_move(&res->lru, &pos->last->lru);
+		list_move(&res->lru.link, &pos->last->lru.link);
 	}
 }
 
@@ -153,7 +177,7 @@ void ttm_resource_move_to_lru_tail(struct ttm_resource *res)
 	lockdep_assert_held(&bo->bdev->lru_lock);
 
 	if (bo->pin_count) {
-		list_move_tail(&res->lru, &bdev->pinned);
+		list_move_tail(&res->lru.link, &bdev->pinned);
 
 	} else	if (bo->bulk_move) {
 		struct ttm_lru_bulk_move_pos *pos =
@@ -164,7 +188,7 @@ void ttm_resource_move_to_lru_tail(struct ttm_resource *res)
 		struct ttm_resource_manager *man;
 
 		man = ttm_manager_type(bdev, res->mem_type);
-		list_move_tail(&res->lru, &man->lru[bo->priority]);
+		list_move_tail(&res->lru.link, &man->lru[bo->priority]);
 	}
 }
 
@@ -195,9 +219,9 @@ void ttm_resource_init(struct ttm_buffer_object *bo,
 	man = ttm_manager_type(bo->bdev, place->mem_type);
 	spin_lock(&bo->bdev->lru_lock);
 	if (bo->pin_count)
-		list_add_tail(&res->lru, &bo->bdev->pinned);
+		list_add_tail(&res->lru.link, &bo->bdev->pinned);
 	else
-		list_add_tail(&res->lru, &man->lru[bo->priority]);
+		list_add_tail(&res->lru.link, &man->lru[bo->priority]);
 	man->usage += res->size;
 	spin_unlock(&bo->bdev->lru_lock);
 }
@@ -219,7 +243,7 @@ void ttm_resource_fini(struct ttm_resource_manager *man,
 	struct ttm_device *bdev = man->bdev;
 
 	spin_lock(&bdev->lru_lock);
-	list_del_init(&res->lru);
+	list_del_init(&res->lru.link);
 	man->usage -= res->size;
 	spin_unlock(&bdev->lru_lock);
 }
@@ -462,14 +486,16 @@ struct ttm_resource *
 ttm_resource_manager_first(struct ttm_resource_manager *man,
 			   struct ttm_resource_cursor *cursor)
 {
-	struct ttm_resource *res;
+	struct ttm_lru_item *lru;
 
 	lockdep_assert_held(&man->bdev->lru_lock);
 
 	for (cursor->priority = 0; cursor->priority < TTM_MAX_BO_PRIORITY;
 	     ++cursor->priority)
-		list_for_each_entry(res, &man->lru[cursor->priority], lru)
-			return res;
+		list_for_each_entry(lru, &man->lru[cursor->priority], link) {
+			if (ttm_lru_item_is_res(lru))
+				return ttm_lru_item_to_res(lru);
+		}
 
 	return NULL;
 }
@@ -488,15 +514,21 @@ ttm_resource_manager_next(struct ttm_resource_manager *man,
 			  struct ttm_resource_cursor *cursor,
 			  struct ttm_resource *res)
 {
+	struct ttm_lru_item *lru = &res->lru;
+
 	lockdep_assert_held(&man->bdev->lru_lock);
 
-	list_for_each_entry_continue(res, &man->lru[cursor->priority], lru)
-		return res;
+	list_for_each_entry_continue(lru, &man->lru[cursor->priority], link) {
+		if (ttm_lru_item_is_res(lru))
+			return ttm_lru_item_to_res(lru);
+	}
 
 	for (++cursor->priority; cursor->priority < TTM_MAX_BO_PRIORITY;
 	     ++cursor->priority)
-		list_for_each_entry(res, &man->lru[cursor->priority], lru)
-			return res;
+		list_for_each_entry(lru, &man->lru[cursor->priority], link) {
+			if (ttm_lru_item_is_res(lru))
+				ttm_lru_item_to_res(lru);
+		}
 
 	return NULL;
 }
diff --git a/include/drm/ttm/ttm_resource.h b/include/drm/ttm/ttm_resource.h
index 1afa13f0c22b..527140579ab5 100644
--- a/include/drm/ttm/ttm_resource.h
+++ b/include/drm/ttm/ttm_resource.h
@@ -49,6 +49,43 @@ struct io_mapping;
 struct sg_table;
 struct scatterlist;
 
+/**
+ * enum ttm_lru_item_type - enumerate ttm_lru_item subclasses
+ */
+enum ttm_lru_item_type {
+	/* The resource subclass */
+	TTM_LRU_RESOURCE,
+	/* The iterator hitch subclass */
+	TTM_LRU_HITCH
+};
+
+/**
+ * struct ttm_lru_item - The TTM lru list node base class
+ * @link: The list link
+ * @type: The subclass type
+ */
+struct ttm_lru_item {
+	struct list_head link;
+	enum ttm_lru_item_type type;
+};
+
+/**
+ * ttm_lru_item_init() - initialize a struct ttm_lru_item
+ * @item: The item to initialize
+ * @type: The subclass type
+ */
+static inline void ttm_lru_item_init(struct ttm_lru_item *item,
+				     enum ttm_lru_item_type type)
+{
+	item->type = type;
+	INIT_LIST_HEAD(&item->link);
+}
+
+static inline bool ttm_lru_item_is_res(const struct ttm_lru_item *item)
+{
+	return item->type == TTM_LRU_RESOURCE;
+}
+
 struct ttm_resource_manager_func {
 	/**
 	 * struct ttm_resource_manager_func member alloc
@@ -217,9 +254,21 @@ struct ttm_resource {
 	/**
 	 * @lru: Least recently used list, see &ttm_resource_manager.lru
 	 */
-	struct list_head lru;
+	struct ttm_lru_item lru;
 };
 
+/**
+ * ttm_lru_item_to_res() - Downcast a struct ttm_lru_item to a struct ttm_resource
+ * @item: The struct ttm_lru_item to downcast
+ *
+ * Return: Pointer to the embedding struct ttm_resource
+ */
+static inline struct ttm_resource *
+ttm_lru_item_to_res(struct ttm_lru_item *item)
+{
+	return container_of(item, struct ttm_resource, lru);
+}
+
 /**
  * struct ttm_resource_cursor
  *
-- 
2.43.0

[PATCH 2/4] drm/ttm: Use LRU hitches

[Thomas Hellström]

Have iterators insert themselves into the list they are iterating
over using hitch list nodes. Since only the iterator owner
can remove these list nodes from the list, it's safe to unlock
the list and when continuing, use them as a starting point. Due to
the way LRU bumping works in TTM, newly added items will not be
missed, and bumped items will be iterated over a second time before
reaching the end of the list.

The exception is list with bulk move sublists. When bumping a
sublist, a hitch that is part of that sublist will also be moved
and we might miss items if restarting from it. This will be
addressed in a later patch.

Cc: Christian König <christian.koenig@amd.com>
Cc: <dri-devel@lists.freedesktop.org>
Signed-off-by: Thomas Hellström <thomas.hellstrom@linux.intel.com>
---
 drivers/gpu/drm/ttm/ttm_bo.c       |  1 +
 drivers/gpu/drm/ttm/ttm_device.c   |  9 ++-
 drivers/gpu/drm/ttm/ttm_resource.c | 94 ++++++++++++++++++++----------
 include/drm/ttm/ttm_resource.h     | 16 +++--
 4 files changed, 82 insertions(+), 38 deletions(-)

diff --git a/drivers/gpu/drm/ttm/ttm_bo.c b/drivers/gpu/drm/ttm/ttm_bo.c
index 96a724e8f3ff..2a048b940840 100644
--- a/drivers/gpu/drm/ttm/ttm_bo.c
+++ b/drivers/gpu/drm/ttm/ttm_bo.c
@@ -622,6 +622,7 @@ int ttm_mem_evict_first(struct ttm_device *bdev,
 		if (locked)
 			dma_resv_unlock(res->bo->base.resv);
 	}
+	ttm_resource_cursor_fini_locked(&cursor);
 
 	if (!bo) {
 		if (busy_bo && !ttm_bo_get_unless_zero(busy_bo))
diff --git a/drivers/gpu/drm/ttm/ttm_device.c b/drivers/gpu/drm/ttm/ttm_device.c
index f27406e851e5..e8a6a1dab669 100644
--- a/drivers/gpu/drm/ttm/ttm_device.c
+++ b/drivers/gpu/drm/ttm/ttm_device.c
@@ -169,12 +169,17 @@ int ttm_device_swapout(struct ttm_device *bdev, struct ttm_operation_ctx *ctx,
 			num_pages = PFN_UP(bo->base.size);
 			ret = ttm_bo_swapout(bo, ctx, gfp_flags);
 			/* ttm_bo_swapout has dropped the lru_lock */
-			if (!ret)
+			if (!ret) {
+				ttm_resource_cursor_fini(&cursor);
 				return num_pages;
-			if (ret != -EBUSY)
+			}
+			if (ret != -EBUSY) {
+				ttm_resource_cursor_fini(&cursor);
 				return ret;
+			}
 		}
 	}
+	ttm_resource_cursor_fini_locked(&cursor);
 	spin_unlock(&bdev->lru_lock);
 	return 0;
 }
diff --git a/drivers/gpu/drm/ttm/ttm_resource.c b/drivers/gpu/drm/ttm/ttm_resource.c
index 0b8beb356b8a..911364e0a5fd 100644
--- a/drivers/gpu/drm/ttm/ttm_resource.c
+++ b/drivers/gpu/drm/ttm/ttm_resource.c
@@ -32,6 +32,37 @@
 
 #include <drm/drm_util.h>
 
+/**
+ * ttm_resource_cursor_fini_locked() - Finalize the LRU list cursor usage
+ * @cursor: The struct ttm_resource_cursor to finalize.
+ *
+ * The function pulls the LRU list cursor off any lists it was previusly
+ * attached to. Needs to be called with the LRU lock held. The function
+ * can be called multiple times after eachother.
+ */
+void ttm_resource_cursor_fini_locked(struct ttm_resource_cursor *cursor)
+{
+	lockdep_assert_held(&cursor->man->bdev->lru_lock);
+	list_del_init(&cursor->hitch.link);
+}
+
+/**
+ * ttm_resource_cursor_fini_locked() - Finalize the LRU list cursor usage
+ * @cursor: The struct ttm_resource_cursor to finalize.
+ *
+ * The function pulls the LRU list cursor off any lists it was previusly
+ * attached to. Needs to be called without the LRU list lock held. The
+ * function can be called multiple times after eachother.
+ */
+void ttm_resource_cursor_fini(struct ttm_resource_cursor *cursor)
+{
+	spinlock_t *lru_lock = &cursor->man->bdev->lru_lock;
+
+	spin_lock(lru_lock);
+	ttm_resource_cursor_fini_locked(cursor);
+	spin_unlock(lru_lock);
+}
+
 /**
  * ttm_lru_bulk_move_init - initialize a bulk move structure
  * @bulk: the structure to init
@@ -475,62 +506,63 @@ void ttm_resource_manager_debug(struct ttm_resource_manager *man,
 EXPORT_SYMBOL(ttm_resource_manager_debug);
 
 /**
- * ttm_resource_manager_first
- *
- * @man: resource manager to iterate over
+ * ttm_resource_manager_next() - Continue iterating over the resource manager
+ * resources
  * @cursor: cursor to record the position
  *
- * Returns the first resource from the resource manager.
+ * Return: The next resource from the resource manager.
  */
 struct ttm_resource *
-ttm_resource_manager_first(struct ttm_resource_manager *man,
-			   struct ttm_resource_cursor *cursor)
+ttm_resource_manager_next(struct ttm_resource_cursor *cursor)
 {
+	struct ttm_resource_manager *man = cursor->man;
 	struct ttm_lru_item *lru;
 
 	lockdep_assert_held(&man->bdev->lru_lock);
 
-	for (cursor->priority = 0; cursor->priority < TTM_MAX_BO_PRIORITY;
-	     ++cursor->priority)
-		list_for_each_entry(lru, &man->lru[cursor->priority], link) {
-			if (ttm_lru_item_is_res(lru))
+	do {
+		lru = &cursor->hitch;
+		list_for_each_entry_continue(lru, &man->lru[cursor->priority], link) {
+			if (ttm_lru_item_is_res(lru)) {
+				list_move(&cursor->hitch.link, &lru->link);
 				return ttm_lru_item_to_res(lru);
+			}
 		}
 
+		if (++cursor->priority >= TTM_MAX_BO_PRIORITY)
+			break;
+
+		list_move(&cursor->hitch.link, &man->lru[cursor->priority]);
+	} while (true);
+
+	list_del_init(&cursor->hitch.link);
+
 	return NULL;
 }
 
 /**
- * ttm_resource_manager_next
- *
+ * ttm_resource_manager_first() - Start iterating over the resources
+ * of a resource manager
  * @man: resource manager to iterate over
  * @cursor: cursor to record the position
- * @res: the current resource pointer
  *
- * Returns the next resource from the resource manager.
+ * Initializes the cursor and starts iterating. When done iterating,
+ * the caller must explicitly call ttm_resource_cursor_fini().
+ *
+ * Return: The first resource from the resource manager.
  */
 struct ttm_resource *
-ttm_resource_manager_next(struct ttm_resource_manager *man,
-			  struct ttm_resource_cursor *cursor,
-			  struct ttm_resource *res)
+ttm_resource_manager_first(struct ttm_resource_manager *man,
+			   struct ttm_resource_cursor *cursor)
 {
-	struct ttm_lru_item *lru = &res->lru;
-
 	lockdep_assert_held(&man->bdev->lru_lock);
 
-	list_for_each_entry_continue(lru, &man->lru[cursor->priority], link) {
-		if (ttm_lru_item_is_res(lru))
-			return ttm_lru_item_to_res(lru);
-	}
+	cursor->priority = 0;
+	cursor->man = man;
+	ttm_lru_item_init(&cursor->hitch, TTM_LRU_HITCH);
+	list_move(&cursor->hitch.link, &man->lru[cursor->priority]);
 
-	for (++cursor->priority; cursor->priority < TTM_MAX_BO_PRIORITY;
-	     ++cursor->priority)
-		list_for_each_entry(lru, &man->lru[cursor->priority], link) {
-			if (ttm_lru_item_is_res(lru))
-				ttm_lru_item_to_res(lru);
-		}
-
-	return NULL;
+	return ttm_resource_manager_next(cursor);
 }
 
 static void ttm_kmap_iter_iomap_map_local(struct ttm_kmap_iter *iter,
diff --git a/include/drm/ttm/ttm_resource.h b/include/drm/ttm/ttm_resource.h
index 527140579ab5..7fdb9d32371b 100644
--- a/include/drm/ttm/ttm_resource.h
+++ b/include/drm/ttm/ttm_resource.h
@@ -271,15 +271,23 @@ ttm_lru_item_to_res(struct ttm_lru_item *item)
 
 /**
  * struct ttm_resource_cursor
- *
+ * @man: The resource manager currently being iterated over
+ * @hitch: A hitch list node inserted before the next resource
+ * to iterate over.
  * @priority: the current priority
  *
  * Cursor to iterate over the resources in a manager.
  */
 struct ttm_resource_cursor {
+	struct ttm_resource_manager *man;
+	struct ttm_lru_item hitch;
 	unsigned int priority;
 };
 
+void ttm_resource_cursor_fini_locked(struct ttm_resource_cursor *cursor);
+
+void ttm_resource_cursor_fini(struct ttm_resource_cursor *cursor);
+
 /**
  * struct ttm_lru_bulk_move_pos
  *
@@ -434,9 +442,7 @@ struct ttm_resource *
 ttm_resource_manager_first(struct ttm_resource_manager *man,
 			   struct ttm_resource_cursor *cursor);
 struct ttm_resource *
-ttm_resource_manager_next(struct ttm_resource_manager *man,
-			  struct ttm_resource_cursor *cursor,
-			  struct ttm_resource *res);
+ttm_resource_manager_next(struct ttm_resource_cursor *cursor);
 
 /**
  * ttm_resource_manager_for_each_res - iterate over all resources
@@ -448,7 +454,7 @@ ttm_resource_manager_next(struct ttm_resource_manager *man,
  */
 #define ttm_resource_manager_for_each_res(man, cursor, res)		\
 	for (res = ttm_resource_manager_first(man, cursor); res;	\
-	     res = ttm_resource_manager_next(man, cursor, res))
+	     res = ttm_resource_manager_next(cursor))
 
 struct ttm_kmap_iter *
 ttm_kmap_iter_iomap_init(struct ttm_kmap_iter_iomap *iter_io,
-- 
2.43.0

[PATCH 3/4] drm/ttm: Consider hitch moves within bulk sublist moves

[Thomas Hellström]

To work around the problem with hitches moving when bulk move
sublists are bumped, keep a second hitch when traversing a bulk
move sublist, which is attached to the list *after* the bulk
move sublist. If we detect a sublist bump, we use that second
hitch as the continuation point of list traversal.

Sublist bumps are detected by checking the sublist age which is
increased by 1 each time it was bumped. The age is then compared
to that of the last iteration returning an item within the sublist.

Cc: Christian König <christian.koenig@amd.com>
Cc: <dri-devel@lists.freedesktop.org>
Signed-off-by: Thomas Hellström <thomas.hellstrom@linux.intel.com>
---
 drivers/gpu/drm/ttm/ttm_resource.c | 64 +++++++++++++++++++++++++++++-
 include/drm/ttm/ttm_resource.h     | 50 +++++++++++++----------
 2 files changed, 93 insertions(+), 21 deletions(-)

diff --git a/drivers/gpu/drm/ttm/ttm_resource.c b/drivers/gpu/drm/ttm/ttm_resource.c
index 911364e0a5fd..3139c27c9262 100644
--- a/drivers/gpu/drm/ttm/ttm_resource.c
+++ b/drivers/gpu/drm/ttm/ttm_resource.c
@@ -32,6 +32,14 @@
 
 #include <drm/drm_util.h>
 
+/* Detach the cursor's bulk hitch from the LRU list */
+static void
+ttm_resource_cursor_clear_bulk(struct ttm_resource_cursor *cursor)
+{
+	cursor->bulk = NULL;
+	list_del_init(&cursor->bulk_hitch.link);
+}
+
 /**
  * ttm_resource_cursor_fini_locked() - Finalize the LRU list cursor usage
  * @cursor: The struct ttm_resource_cursor to finalize.
@@ -44,6 +52,7 @@ void ttm_resource_cursor_fini_locked(struct ttm_resource_cursor *cursor)
 {
 	lockdep_assert_held(&cursor->man->bdev->lru_lock);
 	list_del_init(&cursor->hitch.link);
+	ttm_resource_cursor_clear_bulk(cursor);
 }
 
 /**
@@ -104,6 +113,7 @@ void ttm_lru_bulk_move_tail(struct ttm_lru_bulk_move *bulk)
 					    &pos->last->lru.link);
 		}
 	}
+	bulk->age++;
 }
 EXPORT_SYMBOL(ttm_lru_bulk_move_tail);
 
@@ -505,6 +515,54 @@ void ttm_resource_manager_debug(struct ttm_resource_manager *man,
 }
 EXPORT_SYMBOL(ttm_resource_manager_debug);
 
+/* Adjust to a bulk sublist being bumped while traversing it.*/
+static bool
+ttm_resource_cursor_check_bulk(struct ttm_resource_cursor *cursor,
+			       struct ttm_lru_item *next_lru)
+{
+	struct ttm_resource *next = ttm_lru_item_to_res(next_lru);
+	struct ttm_lru_bulk_move *bulk = NULL;
+	struct ttm_buffer_object *bo = next->bo;
+
+	lockdep_assert_held(&cursor->man->bdev->lru_lock);
+	if (bo && bo->resource == next)
+		bulk = bo->bulk_move;
+
+	if (!bulk) {
+		ttm_resource_cursor_clear_bulk(cursor);
+		return false;
+	}
+
+	/*
+	 * We encountered a bulk sublist. Record its age and
+	 * set a hitch after the sublist.
+	 */
+	if (cursor->bulk != bulk) {
+		struct ttm_lru_bulk_move_pos *pos =
+			ttm_lru_bulk_move_pos(bulk, next);
+
+		cursor->bulk = bulk;
+		cursor->bulk_age = &bulk->age;
+		list_move(&cursor->bulk_hitch.link, &pos->last->lru.link);
+		return false;
+	}
+
+	/* Continue iterating down the bulk sublist */
+	if (cursor->bulk_age == &bulk->age)
+		return false;
+
+	/*
+	 * The bulk sublist in which we had a hitch has moved and the
+	 * hitch moved with it. Restart iteration from a previously
+	 * set hitch after the bulk_move, and remove that backup
+	 * hitch.
+	 */
+	list_move(&cursor->hitch.link, &cursor->bulk_hitch.link);
+	ttm_resource_cursor_clear_bulk(cursor);
+
+	return true;
+}
+
 /**
  * ttm_resource_manager_next() - Continue iterating over the resource manager
  * resources
@@ -524,6 +582,8 @@ ttm_resource_manager_next(struct ttm_resource_cursor *cursor)
 		lru = &cursor->hitch;
 		list_for_each_entry_continue(lru, &man->lru[cursor->priority], link) {
 			if (ttm_lru_item_is_res(lru)) {
+				if (ttm_resource_cursor_check_bulk(cursor, lru))
+					continue;
 				list_move(&cursor->hitch.link, &lru->link);
 				return ttm_lru_item_to_res(lru);
 			}
@@ -533,9 +593,10 @@ ttm_resource_manager_next(struct ttm_resource_cursor *cursor)
 			break;
 
 		list_move(&cursor->hitch.link, &man->lru[cursor->priority]);
+		ttm_resource_cursor_clear_bulk(cursor);
 	} while (true);
 
-	list_del_init(&cursor->hitch.link);
+	ttm_resource_cursor_fini_locked(cursor);
 
 	return NULL;
 }
@@ -560,6 +621,7 @@ ttm_resource_manager_first(struct ttm_resource_manager *man,
 	cursor->priority = 0;
 	cursor->man = man;
 	ttm_lru_item_init(&cursor->hitch, TTM_LRU_HITCH);
+	ttm_lru_item_init(&cursor->bulk_hitch, TTM_LRU_HITCH);
 	list_move(&cursor->hitch.link, &man->lru[cursor->priority]);
 
 	return ttm_resource_manager_next(cursor);
diff --git a/include/drm/ttm/ttm_resource.h b/include/drm/ttm/ttm_resource.h
index 7fdb9d32371b..432a93d0f789 100644
--- a/include/drm/ttm/ttm_resource.h
+++ b/include/drm/ttm/ttm_resource.h
@@ -269,25 +269,6 @@ ttm_lru_item_to_res(struct ttm_lru_item *item)
 	return container_of(item, struct ttm_resource, lru);
 }
 
-/**
- * struct ttm_resource_cursor
- * @man: The resource manager currently being iterated over
- * @hitch: A hitch list node inserted before the next resource
- * to iterate over.
- * @priority: the current priority
- *
- * Cursor to iterate over the resources in a manager.
- */
-struct ttm_resource_cursor {
-	struct ttm_resource_manager *man;
-	struct ttm_lru_item hitch;
-	unsigned int priority;
-};
-
-void ttm_resource_cursor_fini_locked(struct ttm_resource_cursor *cursor);
-
-void ttm_resource_cursor_fini(struct ttm_resource_cursor *cursor);
-
 /**
  * struct ttm_lru_bulk_move_pos
  *
@@ -303,16 +284,45 @@ struct ttm_lru_bulk_move_pos {
 
 /**
  * struct ttm_lru_bulk_move
- *
  * @pos: first/last lru entry for resources in the each domain/priority
+ * @age: The number of times the bulk sublists were bumped, (moved to
+ * the LRU list tail). Protected by the lru_lock.
  *
  * Container for the current bulk move state. Should be used with
  * ttm_lru_bulk_move_init() and ttm_bo_set_bulk_move().
  */
 struct ttm_lru_bulk_move {
 	struct ttm_lru_bulk_move_pos pos[TTM_NUM_MEM_TYPES][TTM_MAX_BO_PRIORITY];
+	u64 age;
 };
 
+/**
+ * struct ttm_resource_cursor
+ * @man: The resource manager currently being iterated over
+ * @hitch: A hitch list node inserted before the next resource
+ * to iterate over.
+ * @bulk_hitch: A hitch list node inserted before the next
+ * resource to iterate over if the bulk sublist @hitch was
+ * inserted in is bumped.
+ * @bulk_age: The age of @bulk when @bulk_hitch was inserted.
+ * Used to detect whether @bulk was bumped since last iteration.
+ * @priority: the current priority
+ *
+ * Cursor to iterate over the resources in a manager.
+ */
+struct ttm_resource_cursor {
+	struct ttm_resource_manager *man;
+	struct ttm_lru_item hitch;
+	struct ttm_lru_item bulk_hitch;
+	struct ttm_lru_bulk_move *bulk;
+	u64 bulk_age;
+	unsigned int priority;
+};
+
+void ttm_resource_cursor_fini_locked(struct ttm_resource_cursor *cursor);
+
+void ttm_resource_cursor_fini(struct ttm_resource_cursor *cursor);
+
 /**
  * struct ttm_kmap_iter_iomap - Specialization for a struct io_mapping +
  * struct sg_table backed struct ttm_resource.
-- 
2.43.0

[PATCH 4/4] drm/ttm: Allow continued swapout after -ENOSPC falure

[Thomas Hellström]

The -ENOSPC failure from ttm_bo_swapout() meant that the lru_lock
was dropped and simply restarting the iteration meant we'd likely
hit the same error again on the same resource. Now that we can
restart the iteration even if the lock was dropped, do that.

Cc: Christian König <christian.koenig@amd.com>
Cc: <dri-devel@lists.freedesktop.org>
Signed-off-by: Thomas Hellström <thomas.hellstrom@linux.intel.com>
---
 drivers/gpu/drm/ttm/ttm_device.c | 21 +++++++++++++--------
 1 file changed, 13 insertions(+), 8 deletions(-)

diff --git a/drivers/gpu/drm/ttm/ttm_device.c b/drivers/gpu/drm/ttm/ttm_device.c
index e8a6a1dab669..4a030b4bc848 100644
--- a/drivers/gpu/drm/ttm/ttm_device.c
+++ b/drivers/gpu/drm/ttm/ttm_device.c
@@ -168,15 +168,20 @@ int ttm_device_swapout(struct ttm_device *bdev, struct ttm_operation_ctx *ctx,
 
 			num_pages = PFN_UP(bo->base.size);
 			ret = ttm_bo_swapout(bo, ctx, gfp_flags);
-			/* ttm_bo_swapout has dropped the lru_lock */
-			if (!ret) {
-				ttm_resource_cursor_fini(&cursor);
-				return num_pages;
-			}
-			if (ret != -EBUSY) {
-				ttm_resource_cursor_fini(&cursor);
-				return ret;
+			/* Couldn't swap out, and retained the lru_lock */
+			if (ret == -EBUSY)
+				continue;
+			/* Couldn't swap out and dropped the lru_lock */
+			if (ret == -ENOSPC) {
+				spin_lock(&bdev->lru_lock);
+				continue;
 			}
+			/*
+			 * Dropped the lock and either succeeded or
+			 * hit an error that forces us to break.
+			 */
+			ttm_resource_cursor_fini(&cursor);
+			return ret ? ret : num_pages;
 		}
 	}
 	ttm_resource_cursor_fini_locked(&cursor);
-- 
2.43.0

Re: [PATCH 0/4] TTM unlockable restartable LRU list iteration

[Christian König]

Am 16.02.24 um 14:13 schrieb Thomas Hellström:
> This patch-set is a prerequisite for a standalone TTM shrinker
> and for exhaustive TTM eviction using sleeping dma_resv locks,
> which is the motivation it.
>
> Currently when unlocking the TTM lru list lock, iteration needs
> to be restarted from the beginning, rather from the next LRU list
> node. This can potentially be a big problem, because if eviction
> or shrinking fails for whatever reason after unlock, restarting
> is likely to cause the same failure over and over again.

Oh, yes please. I have been working on that problem before as well, but 
wasn't able to come up with something working.

> There are various schemes to be able to continue the list
> iteration from where we left off. One such scheme used by the
> GEM LRU list traversal is to pull items already considered off
> the LRU list and reinsert them when iteration is done.
> This has the drawback that concurrent list iteration doesn't see
> the complete list (which is bad for exhaustive eviction) and also
> doesn't lend itself well to bulk-move sublists since these will
> be split in the process where items from those lists are
> temporarily pulled from the list and moved to the list tail.

Completely agree that this is not a desirable solution.

> The approach taken here is that list iterators insert themselves
> into the list next position using a special list node. Iteration
> is then using that list node as starting point when restarting.
> Concurrent iterators just skip over the special list nodes.
>
> This is implemented in patch 1 and 2.
>
> For bulk move sublist the approach is the same, but when a bulk
> move sublist is moved to the tail, the iterator is also moved,
> causing us to skip parts of the list. That is undesirable.
> Patch 3 deals with that, and when iterator detects it is
> traversing a sublist, it inserts a second restarting point just
> after the sublist and if the sublist is moved to the tail,
> it just uses the second restarting point instead.
>
> This is implemented in patch 3.

Interesting approach, that is probably even better than what I tried.

My approach was basically to not only lock the current BO, but also the 
next one. Since only a locked BO can move on the LRU we effectively 
created an anchor.

Before I dig into the code a couple of questions:
1. How do you distinct BOs and iteration anchors on the LRU?
2. How do you detect that a bulk list moved on the LRU?
3. How do you remove the iteration anchors from the bulk list?

Regards,
Christian.

>
> The restartable property is used in patch 4 to restart swapout if
> needed, but the main purpose is this paves the way for
> shrinker- and exhaustive eviction.
>
> Cc: Christian König <christian.koenig@amd.com>
> Cc: <dri-devel@lists.freedesktop.org>
>
> Thomas Hellström (4):
>    drm/ttm: Allow TTM LRU list nodes of different types
>    drm/ttm: Use LRU hitches
>    drm/ttm: Consider hitch moves within bulk sublist moves
>    drm/ttm: Allow continued swapout after -ENOSPC falure
>
>   drivers/gpu/drm/ttm/ttm_bo.c       |   1 +
>   drivers/gpu/drm/ttm/ttm_device.c   |  33 +++--
>   drivers/gpu/drm/ttm/ttm_resource.c | 202 +++++++++++++++++++++++------
>   include/drm/ttm/ttm_resource.h     |  91 +++++++++++--
>   4 files changed, 267 insertions(+), 60 deletions(-)
>

Re: [PATCH 0/4] TTM unlockable restartable LRU list iteration

[Thomas Hellström]

On Fri, 2024-02-16 at 15:00 +0100, Christian König wrote:
> Am 16.02.24 um 14:13 schrieb Thomas Hellström:
> > This patch-set is a prerequisite for a standalone TTM shrinker
> > and for exhaustive TTM eviction using sleeping dma_resv locks,
> > which is the motivation it.
> > 
> > Currently when unlocking the TTM lru list lock, iteration needs
> > to be restarted from the beginning, rather from the next LRU list
> > node. This can potentially be a big problem, because if eviction
> > or shrinking fails for whatever reason after unlock, restarting
> > is likely to cause the same failure over and over again.
> 
> Oh, yes please. I have been working on that problem before as well,
> but 
> wasn't able to come up with something working.
> 
> > There are various schemes to be able to continue the list
> > iteration from where we left off. One such scheme used by the
> > GEM LRU list traversal is to pull items already considered off
> > the LRU list and reinsert them when iteration is done.
> > This has the drawback that concurrent list iteration doesn't see
> > the complete list (which is bad for exhaustive eviction) and also
> > doesn't lend itself well to bulk-move sublists since these will
> > be split in the process where items from those lists are
> > temporarily pulled from the list and moved to the list tail.
> 
> Completely agree that this is not a desirable solution.
> 
> > The approach taken here is that list iterators insert themselves
> > into the list next position using a special list node. Iteration
> > is then using that list node as starting point when restarting.
> > Concurrent iterators just skip over the special list nodes.
> > 
> > This is implemented in patch 1 and 2.
> > 
> > For bulk move sublist the approach is the same, but when a bulk
> > move sublist is moved to the tail, the iterator is also moved,
> > causing us to skip parts of the list. That is undesirable.
> > Patch 3 deals with that, and when iterator detects it is
> > traversing a sublist, it inserts a second restarting point just
> > after the sublist and if the sublist is moved to the tail,
> > it just uses the second restarting point instead.
> > 
> > This is implemented in patch 3.
> 
> Interesting approach, that is probably even better than what I tried.
> 
> My approach was basically to not only lock the current BO, but also
> the 
> next one. Since only a locked BO can move on the LRU we effectively 
> created an anchor.
> 
> Before I dig into the code a couple of questions:
These are described in the patches but brief comments inline.

> 1. How do you distinct BOs and iteration anchors on the LRU?
Using a struct ttm_lru_item, containing a struct list_head and the
type. List nodes embeds this instead of a struct list_head. This is
larger than the list head but makes it explicit what we're doing.
 

> 2. How do you detect that a bulk list moved on the LRU?
An age u64 counter on the bulk move that we're comparing against. It's
updated each time it moves.


> 3. How do you remove the iteration anchors from the bulk list?
A function call at the end of iteration, that the function iterating is
requried to call.


/Thomas

> 
> Regards,
> Christian.
> 
> > 
> > The restartable property is used in patch 4 to restart swapout if
> > needed, but the main purpose is this paves the way for
> > shrinker- and exhaustive eviction.
> > 
> > Cc: Christian König <christian.koenig@amd.com>
> > Cc: <dri-devel@lists.freedesktop.org>
> > 
> > Thomas Hellström (4):
> >    drm/ttm: Allow TTM LRU list nodes of different types
> >    drm/ttm: Use LRU hitches
> >    drm/ttm: Consider hitch moves within bulk sublist moves
> >    drm/ttm: Allow continued swapout after -ENOSPC falure
> > 
> >   drivers/gpu/drm/ttm/ttm_bo.c       |   1 +
> >   drivers/gpu/drm/ttm/ttm_device.c   |  33 +++--
> >   drivers/gpu/drm/ttm/ttm_resource.c | 202 +++++++++++++++++++++++-
> > -----
> >   include/drm/ttm/ttm_resource.h     |  91 +++++++++++--
> >   4 files changed, 267 insertions(+), 60 deletions(-)
> > 
> 

Re: [PATCH 0/4] TTM unlockable restartable LRU list iteration

[Christian König]

[-- Attachment #1: Type: text/plain, Size: 2431 bytes --]

Am 16.02.24 um 15:20 schrieb Thomas Hellström:
[SNIP]
>> My approach was basically to not only lock the current BO, but also
>> the
>> next one. Since only a locked BO can move on the LRU we effectively
>> created an anchor.
>>
>> Before I dig into the code a couple of questions:
> These are described in the patches but brief comments inline.
>
>> 1. How do you distinct BOs and iteration anchors on the LRU?
> Using a struct ttm_lru_item, containing a struct list_head and the
> type. List nodes embeds this instead of a struct list_head. This is
> larger than the list head but makes it explicit what we're doing.

Need to look deeper into the code of this, but it would be nice if we 
could abstract that better somehow.

>> 2. How do you detect that a bulk list moved on the LRU?
> An age u64 counter on the bulk move that we're comparing against. It's
> updated each time it moves.
>
>
>> 3. How do you remove the iteration anchors from the bulk list?
> A function call at the end of iteration, that the function iterating is
> requried to call.

Thinking quite a bit about that in the last week and I came to the 
conclusion that this might be overkill.

All BOs in a bulk share the same reservation object. So when you 
acquired one you can just keep the dma-resv locked even after evicting 
the BO.

Since moving BOs requires locking the dma-resv object the whole problem 
then just boils down to a list_for_each_element_safe().

That's probably a bit simpler than doing the add/remove dance.

Regards,
Christian.

>
>
> /Thomas
>
>> Regards,
>> Christian.
>>
>>> The restartable property is used in patch 4 to restart swapout if
>>> needed, but the main purpose is this paves the way for
>>> shrinker- and exhaustive eviction.
>>>
>>> Cc: Christian König<christian.koenig@amd.com>
>>> Cc:<dri-devel@lists.freedesktop.org>
>>>
>>> Thomas Hellström (4):
>>>     drm/ttm: Allow TTM LRU list nodes of different types
>>>     drm/ttm: Use LRU hitches
>>>     drm/ttm: Consider hitch moves within bulk sublist moves
>>>     drm/ttm: Allow continued swapout after -ENOSPC falure
>>>
>>>    drivers/gpu/drm/ttm/ttm_bo.c       |   1 +
>>>    drivers/gpu/drm/ttm/ttm_device.c   |  33 +++--
>>>    drivers/gpu/drm/ttm/ttm_resource.c | 202 +++++++++++++++++++++++-
>>> -----
>>>    include/drm/ttm/ttm_resource.h     |  91 +++++++++++--
>>>    4 files changed, 267 insertions(+), 60 deletions(-)
>>>

[-- Attachment #2: Type: text/html, Size: 4281 bytes --]

Re: [PATCH 0/4] TTM unlockable restartable LRU list iteration

[Thomas Hellström]

Hi, Christian.

Thanks for having a look.

On Thu, 2024-02-29 at 16:08 +0100, Christian König wrote:
> Am 16.02.24 um 15:20 schrieb Thomas Hellström:
> [SNIP]
> > > My approach was basically to not only lock the current BO, but
> > > also
> > > the
> > > next one. Since only a locked BO can move on the LRU we
> > > effectively
> > > created an anchor.
> > > 
> > > Before I dig into the code a couple of questions:
> > These are described in the patches but brief comments inline.
> > 
> > > 1. How do you distinct BOs and iteration anchors on the LRU?
> > Using a struct ttm_lru_item, containing a struct list_head and the
> > type. List nodes embeds this instead of a struct list_head. This is
> > larger than the list head but makes it explicit what we're doing.
> 
> Need to look deeper into the code of this, but it would be nice if we
> could abstract that better somehow.

Do you have any specific concerns or improvements in mind? I think
patch 1 and 2 are pretty straigthforward. Patch 3 is indeed a bit
hairy.

> 
> > > 2. How do you detect that a bulk list moved on the LRU?
> > An age u64 counter on the bulk move that we're comparing against.
> > It's
> > updated each time it moves.
> > 
> > 
> > > 3. How do you remove the iteration anchors from the bulk list?
> > A function call at the end of iteration, that the function
> > iterating is
> > requried to call.
> 
> Thinking quite a bit about that in the last week and I came to the 
> conclusion that this might be overkill.
> 
> All BOs in a bulk share the same reservation object. So when you 
> acquired one you can just keep the dma-resv locked even after
> evicting 
> the BO.
> 
> Since moving BOs requires locking the dma-resv object the whole
> problem 
> then just boils down to a list_for_each_element_safe().
> 
> That's probably a bit simpler than doing the add/remove dance.

I think the problem with the "lock the next object" approach is that
there are situations that it might not work. First, where not asserting
anywhere that all bulk move resource have the same lock, and after
individualization they certainly don't. (I think I had a patch
somewhere to try to enforce that, but I don't think it ever got
reviewed). I tried to sort out the locking rules at one point for
resources switching bos to ghost object but I long since forgot those.

I guess it all boils down to the list elements being resources, not
bos.

Also I'm concerned about keeping a resv held for a huge number of
evictions will block out a higher priority ticket for a substantial
amount of time.

I think while the suggested solution here might be a bit of an
overkill, it's simple enough to understand, but the locking
implications of resources switching resvs arent.

But please let me know how we should proceed here. This is a blocker
for other pending work we have.

/Thomas



> 
> Regards,
> Christian.
> 
> > 
> > 
> > /Thomas
> > 
> > > Regards,
> > > Christian.
> > > 
> > > > The restartable property is used in patch 4 to restart swapout
> > > > if
> > > > needed, but the main purpose is this paves the way for
> > > > shrinker- and exhaustive eviction.
> > > > 
> > > > Cc: Christian König<christian.koenig@amd.com>
> > > > Cc:<dri-devel@lists.freedesktop.org>
> > > > 
> > > > Thomas Hellström (4):
> > > >     drm/ttm: Allow TTM LRU list nodes of different types
> > > >     drm/ttm: Use LRU hitches
> > > >     drm/ttm: Consider hitch moves within bulk sublist moves
> > > >     drm/ttm: Allow continued swapout after -ENOSPC falure
> > > > 
> > > >    drivers/gpu/drm/ttm/ttm_bo.c       |   1 +
> > > >    drivers/gpu/drm/ttm/ttm_device.c   |  33 +++--
> > > >    drivers/gpu/drm/ttm/ttm_resource.c | 202
> > > > +++++++++++++++++++++++-
> > > > -----
> > > >    include/drm/ttm/ttm_resource.h     |  91 +++++++++++--
> > > >    4 files changed, 267 insertions(+), 60 deletions(-)
> > > > 

Re: [PATCH 0/4] TTM unlockable restartable LRU list iteration

[Thomas Hellström]

On Thu, 2024-02-29 at 18:34 +0100, Thomas Hellström wrote:
> Hi, Christian.
> 
> Thanks for having a look.
> 
> On Thu, 2024-02-29 at 16:08 +0100, Christian König wrote:
> > Am 16.02.24 um 15:20 schrieb Thomas Hellström:
> > [SNIP]
> > > > My approach was basically to not only lock the current BO, but
> > > > also
> > > > the
> > > > next one. Since only a locked BO can move on the LRU we
> > > > effectively
> > > > created an anchor.
> > > > 
> > > > Before I dig into the code a couple of questions:
> > > These are described in the patches but brief comments inline.
> > > 
> > > > 1. How do you distinct BOs and iteration anchors on the LRU?
> > > Using a struct ttm_lru_item, containing a struct list_head and
> > > the
> > > type. List nodes embeds this instead of a struct list_head. This
> > > is
> > > larger than the list head but makes it explicit what we're doing.
> > 
> > Need to look deeper into the code of this, but it would be nice if
> > we
> > could abstract that better somehow.
> 
> Do you have any specific concerns or improvements in mind? I think
> patch 1 and 2 are pretty straigthforward. Patch 3 is indeed a bit
> hairy.
> 
> > 
> > > > 2. How do you detect that a bulk list moved on the LRU?
> > > An age u64 counter on the bulk move that we're comparing against.
> > > It's
> > > updated each time it moves.
> > > 
> > > 
> > > > 3. How do you remove the iteration anchors from the bulk list?
> > > A function call at the end of iteration, that the function
> > > iterating is
> > > requried to call.
> > 
> > Thinking quite a bit about that in the last week and I came to the 
> > conclusion that this might be overkill.
> > 
> > All BOs in a bulk share the same reservation object. So when you 
> > acquired one you can just keep the dma-resv locked even after
> > evicting 
> > the BO.
> > 
> > Since moving BOs requires locking the dma-resv object the whole
> > problem 
> > then just boils down to a list_for_each_element_safe().
> > 
> > That's probably a bit simpler than doing the add/remove dance.
> 
> I think the problem with the "lock the next object" approach is that
> there are situations that it might not work. First, where not
> asserting
> anywhere that all bulk move resource have the same lock, and after
> individualization they certainly don't. (I think I had a patch
> somewhere to try to enforce that, but I don't think it ever got
> reviewed). I tried to sort out the locking rules at one point for
> resources switching bos to ghost object but I long since forgot
> those.
> 
> I guess it all boils down to the list elements being resources, not
> bos.
> 
> Also I'm concerned about keeping a resv held for a huge number of
> evictions will block out a higher priority ticket for a substantial
> amount of time.
> 
> I think while the suggested solution here might be a bit of an
> overkill, it's simple enough to understand, but the locking
> implications of resources switching resvs arent.
> 
> But please let me know how we should proceed here. This is a blocker
> for other pending work we have.

Actually some more issues with the locking approach would be with the
intended use-cases I was planning to use this for.

For example the exhaustive eviction where we regularly unlock the
lru_lock to take the bo lock. If we need to do that for the first
element of a bulk_move list, we can't have the bo lock of the next
element when we unlock the list. For part of the list that is not a
bulk sublist, this also doesn't work AFAICT.

And finally for the tt shinking that's been pending for quite some
time, the last comment that made me temporarily shelf is was that we
should expose the lru traversal to the drivers, and the drivers
implement the shrinkers with TTM helpers, rather than having TTM being
the middle layer. So I think exposing the LRU traversal to drivers will
probably end up having pretty weird semantics if it sometimes locks or
requiring locking of the next object while traversing.

But regardless of how this is solved, since I think we are agreeing
that the functionality itself is useful and needed, could we perhaps
use this implementation that is easy to verify that it works, and I
will i no way stand in the way if it turns out you come up with
something nicer. I've been thinking a bit of how to make a better
approach out of patch 3, and a possible alternative that I could
prototype would be to register list cursors that traverse a bulk
sublist with the bulk move structure using a list. At destruction of
either list cursors or bulk moves either can unregister, and on bulk
list bumping the list is traversed and the cursor is moved to the end
of the list. Probably the same amount of code but will look nicer.

/Thomas


> 
> /Thomas
> 
> 
> 
> > 
> > Regards,
> > Christian.
> > 
> > > 
> > > 
> > > /Thomas
> > > 
> > > > Regards,
> > > > Christian.
> > > > 
> > > > > The restartable property is used in patch 4 to restart
> > > > > swapout
> > > > > if
> > > > > needed, but the main purpose is this paves the way for
> > > > > shrinker- and exhaustive eviction.
> > > > > 
> > > > > Cc: Christian König<christian.koenig@amd.com>
> > > > > Cc:<dri-devel@lists.freedesktop.org>
> > > > > 
> > > > > Thomas Hellström (4):
> > > > >     drm/ttm: Allow TTM LRU list nodes of different types
> > > > >     drm/ttm: Use LRU hitches
> > > > >     drm/ttm: Consider hitch moves within bulk sublist moves
> > > > >     drm/ttm: Allow continued swapout after -ENOSPC falure
> > > > > 
> > > > >    drivers/gpu/drm/ttm/ttm_bo.c       |   1 +
> > > > >    drivers/gpu/drm/ttm/ttm_device.c   |  33 +++--
> > > > >    drivers/gpu/drm/ttm/ttm_resource.c | 202
> > > > > +++++++++++++++++++++++-
> > > > > -----
> > > > >    include/drm/ttm/ttm_resource.h     |  91 +++++++++++--
> > > > >    4 files changed, 267 insertions(+), 60 deletions(-)
> > > > > 
> 

Re: [PATCH 0/4] TTM unlockable restartable LRU list iteration

[Christian König]

Am 01.03.24 um 14:45 schrieb Thomas Hellström:
> On Thu, 2024-02-29 at 18:34 +0100, Thomas Hellström wrote:
>> Hi, Christian.
>>
>> Thanks for having a look.
>>
>> On Thu, 2024-02-29 at 16:08 +0100, Christian König wrote:
>>> Am 16.02.24 um 15:20 schrieb Thomas Hellström:
>>> [SNIP]
>>>>> My approach was basically to not only lock the current BO, but
>>>>> also
>>>>> the
>>>>> next one. Since only a locked BO can move on the LRU we
>>>>> effectively
>>>>> created an anchor.
>>>>>
>>>>> Before I dig into the code a couple of questions:
>>>> These are described in the patches but brief comments inline.
>>>>
>>>>> 1. How do you distinct BOs and iteration anchors on the LRU?
>>>> Using a struct ttm_lru_item, containing a struct list_head and
>>>> the
>>>> type. List nodes embeds this instead of a struct list_head. This
>>>> is
>>>> larger than the list head but makes it explicit what we're doing.
>>> Need to look deeper into the code of this, but it would be nice if
>>> we
>>> could abstract that better somehow.
>> Do you have any specific concerns or improvements in mind? I think
>> patch 1 and 2 are pretty straigthforward. Patch 3 is indeed a bit
>> hairy.

Yeah, seen that as well. No idea of hand how to improve.

Amar should have time to give the patches a more in deep review, maybe 
he has an idea.

>>
>>>>> 2. How do you detect that a bulk list moved on the LRU?
>>>> An age u64 counter on the bulk move that we're comparing against.
>>>> It's
>>>> updated each time it moves.
>>>>
>>>>
>>>>> 3. How do you remove the iteration anchors from the bulk list?
>>>> A function call at the end of iteration, that the function
>>>> iterating is
>>>> requried to call.
>>> Thinking quite a bit about that in the last week and I came to the
>>> conclusion that this might be overkill.
>>>
>>> All BOs in a bulk share the same reservation object. So when you
>>> acquired one you can just keep the dma-resv locked even after
>>> evicting
>>> the BO.
>>>
>>> Since moving BOs requires locking the dma-resv object the whole
>>> problem
>>> then just boils down to a list_for_each_element_safe().
>>>
>>> That's probably a bit simpler than doing the add/remove dance.
>> I think the problem with the "lock the next object" approach

Stop stop, you misunderstood me. I was not suggesting to use the lock 
the next object approach, this anchor approach here is certainly better.

I just wanted to note that we most likely don't need to insert a second 
anchor for bulk moves.

Basically my idea is that we start to use the drm_exec object to lock 
BOs and those BOs stay locked until everything is completed.

That also removes the problem that a BO might be evicted just to be 
moved back in again by a concurrent submission.

>>   is that
>> there are situations that it might not work. First, where not
>> asserting
>> anywhere that all bulk move resource have the same lock,

Daniel actually wanted that I add such an assert, I just couldn't find a 
way to easily do this back then.

But since I reworked the bulk move since then it should now be possible.

>>   and after
>> individualization they certainly don't.

Actually when they are individualized for freeing they shouldn't be part 
of any bulk any more.

>>   (I think I had a patch
>> somewhere to try to enforce that, but I don't think it ever got
>> reviewed). I tried to sort out the locking rules at one point for
>> resources switching bos to ghost object but I long since forgot
>> those.
>>
>> I guess it all boils down to the list elements being resources, not
>> bos.
>>
>> Also I'm concerned about keeping a resv held for a huge number of
>> evictions will block out a higher priority ticket for a substantial
>> amount of time.
>>
>> I think while the suggested solution here might be a bit of an
>> overkill, it's simple enough to understand, but the locking
>> implications of resources switching resvs arent.
>>
>> But please let me know how we should proceed here. This is a blocker
>> for other pending work we have.
> Actually some more issues with the locking approach would be with the
> intended use-cases I was planning to use this for.
>
> For example the exhaustive eviction where we regularly unlock the
> lru_lock to take the bo lock. If we need to do that for the first
> element of a bulk_move list, we can't have the bo lock of the next
> element when we unlock the list. For part of the list that is not a
> bulk sublist, this also doesn't work AFAICT.

Well when we drop the LRU lock we should always have the anchor on the 
LRU before the element we try to lock.

This way we actually don't have to move the anchor unless we found a BO 
which we don't want to evict.

E.g. something like

Head -> anchor -> BO1 -> BO2 -> BO3 -> BO4

And we Evict BO1, BO2 and then find that BO3 doesn't match the 
allocation pattern we need so only then is the anchor moved after BO3:

Head -> BO3 -> anchor -> BO4....

And when we moved inside a bulk with an anchor we have already locked at 
least one BO of the bulk, so locking the next one is a no-op.

> And finally for the tt shinking that's been pending for quite some
> time, the last comment that made me temporarily shelf is was that we
> should expose the lru traversal to the drivers, and the drivers
> implement the shrinkers with TTM helpers, rather than having TTM being
> the middle layer. So I think exposing the LRU traversal to drivers will
> probably end up having pretty weird semantics if it sometimes locks or
> requiring locking of the next object while traversing.

Yeah, I was just yesterday talking about that with Amar and putting him 
on the task to look into tt shrinking.

And completely agree that providing the necessary toolbox for eviction 
is a better approach than burying the eviction deep into the TTM logic.

> But regardless of how this is solved, since I think we are agreeing
> that the functionality itself is useful and needed, could we perhaps
> use this implementation that is easy to verify that it works, and I
> will i no way stand in the way if it turns out you come up with
> something nicer. I've been thinking a bit of how to make a better
> approach out of patch 3, and a possible alternative that I could
> prototype would be to register list cursors that traverse a bulk
> sublist with the bulk move structure using a list. At destruction of
> either list cursors or bulk moves either can unregister, and on bulk
> list bumping the list is traversed and the cursor is moved to the end
> of the list. Probably the same amount of code but will look nicer.

Yeah, I'm just not sure if this handling here will be so simple with 
multiple anchors. That sounds very fragile.

Regards,
Christian.

>
> /Thomas
>
>
>> /Thomas
>>
>>
>>
>>> Regards,
>>> Christian.
>>>
>>>>
>>>> /Thomas
>>>>
>>>>> Regards,
>>>>> Christian.
>>>>>
>>>>>> The restartable property is used in patch 4 to restart
>>>>>> swapout
>>>>>> if
>>>>>> needed, but the main purpose is this paves the way for
>>>>>> shrinker- and exhaustive eviction.
>>>>>>
>>>>>> Cc: Christian König<christian.koenig@amd.com>
>>>>>> Cc:<dri-devel@lists.freedesktop.org>
>>>>>>
>>>>>> Thomas Hellström (4):
>>>>>>      drm/ttm: Allow TTM LRU list nodes of different types
>>>>>>      drm/ttm: Use LRU hitches
>>>>>>      drm/ttm: Consider hitch moves within bulk sublist moves
>>>>>>      drm/ttm: Allow continued swapout after -ENOSPC falure
>>>>>>
>>>>>>     drivers/gpu/drm/ttm/ttm_bo.c       |   1 +
>>>>>>     drivers/gpu/drm/ttm/ttm_device.c   |  33 +++--
>>>>>>     drivers/gpu/drm/ttm/ttm_resource.c | 202
>>>>>> +++++++++++++++++++++++-
>>>>>> -----
>>>>>>     include/drm/ttm/ttm_resource.h     |  91 +++++++++++--
>>>>>>     4 files changed, 267 insertions(+), 60 deletions(-)
>>>>>>

Re: [PATCH 0/4] TTM unlockable restartable LRU list iteration

[Thomas Hellström]

On Fri, 2024-03-01 at 15:20 +0100, Christian König wrote:
> Am 01.03.24 um 14:45 schrieb Thomas Hellström:
> > On Thu, 2024-02-29 at 18:34 +0100, Thomas Hellström wrote:
> > > Hi, Christian.
> > > 
> > > Thanks for having a look.
> > > 
> > > On Thu, 2024-02-29 at 16:08 +0100, Christian König wrote:
> > > > Am 16.02.24 um 15:20 schrieb Thomas Hellström:
> > > > [SNIP]
> > > > > > My approach was basically to not only lock the current BO,
> > > > > > but
> > > > > > also
> > > > > > the
> > > > > > next one. Since only a locked BO can move on the LRU we
> > > > > > effectively
> > > > > > created an anchor.
> > > > > > 
> > > > > > Before I dig into the code a couple of questions:
> > > > > These are described in the patches but brief comments inline.
> > > > > 
> > > > > > 1. How do you distinct BOs and iteration anchors on the
> > > > > > LRU?
> > > > > Using a struct ttm_lru_item, containing a struct list_head
> > > > > and
> > > > > the
> > > > > type. List nodes embeds this instead of a struct list_head.
> > > > > This
> > > > > is
> > > > > larger than the list head but makes it explicit what we're
> > > > > doing.
> > > > Need to look deeper into the code of this, but it would be nice
> > > > if
> > > > we
> > > > could abstract that better somehow.
> > > Do you have any specific concerns or improvements in mind? I
> > > think
> > > patch 1 and 2 are pretty straigthforward. Patch 3 is indeed a bit
> > > hairy.
> 
> Yeah, seen that as well. No idea of hand how to improve.
> 
> Amar should have time to give the patches a more in deep review,
> maybe 
> he has an idea.
> 
> > > 
> > > > > > 2. How do you detect that a bulk list moved on the LRU?
> > > > > An age u64 counter on the bulk move that we're comparing
> > > > > against.
> > > > > It's
> > > > > updated each time it moves.
> > > > > 
> > > > > 
> > > > > > 3. How do you remove the iteration anchors from the bulk
> > > > > > list?
> > > > > A function call at the end of iteration, that the function
> > > > > iterating is
> > > > > requried to call.
> > > > Thinking quite a bit about that in the last week and I came to
> > > > the
> > > > conclusion that this might be overkill.
> > > > 
> > > > All BOs in a bulk share the same reservation object. So when
> > > > you
> > > > acquired one you can just keep the dma-resv locked even after
> > > > evicting
> > > > the BO.
> > > > 
> > > > Since moving BOs requires locking the dma-resv object the whole
> > > > problem
> > > > then just boils down to a list_for_each_element_safe().
> > > > 
> > > > That's probably a bit simpler than doing the add/remove dance.
> > > I think the problem with the "lock the next object" approach
> 
> Stop stop, you misunderstood me. I was not suggesting to use the lock
> the next object approach, this anchor approach here is certainly
> better.
> 
> I just wanted to note that we most likely don't need to insert a
> second 
> anchor for bulk moves.
> 
> Basically my idea is that we start to use the drm_exec object to lock
> BOs and those BOs stay locked until everything is completed.
> 
> That also removes the problem that a BO might be evicted just to be 
> moved back in again by a concurrent submission.

Ah, yes then we're on the same page.


> 
> > >   is that
> > > there are situations that it might not work. First, where not
> > > asserting
> > > anywhere that all bulk move resource have the same lock,
> 
> Daniel actually wanted that I add such an assert, I just couldn't
> find a 
> way to easily do this back then.
> 
> But since I reworked the bulk move since then it should now be
> possible.
> 
> > >   and after
> > > individualization they certainly don't.
> 
> Actually when they are individualized for freeing they shouldn't be
> part 
> of any bulk any more.
> 
> > >   (I think I had a patch
> > > somewhere to try to enforce that, but I don't think it ever got
> > > reviewed). I tried to sort out the locking rules at one point for
> > > resources switching bos to ghost object but I long since forgot
> > > those.
> > > 
> > > I guess it all boils down to the list elements being resources,
> > > not
> > > bos.
> > > 
> > > Also I'm concerned about keeping a resv held for a huge number of
> > > evictions will block out a higher priority ticket for a
> > > substantial
> > > amount of time.
> > > 
> > > I think while the suggested solution here might be a bit of an
> > > overkill, it's simple enough to understand, but the locking
> > > implications of resources switching resvs arent.
> > > 
> > > But please let me know how we should proceed here. This is a
> > > blocker
> > > for other pending work we have.
> > Actually some more issues with the locking approach would be with
> > the
> > intended use-cases I was planning to use this for.
> > 
> > For example the exhaustive eviction where we regularly unlock the
> > lru_lock to take the bo lock. If we need to do that for the first
> > element of a bulk_move list, we can't have the bo lock of the next
> > element when we unlock the list. For part of the list that is not a
> > bulk sublist, this also doesn't work AFAICT.
> 
> Well when we drop the LRU lock we should always have the anchor on
> the 
> LRU before the element we try to lock.
> 
> This way we actually don't have to move the anchor unless we found a
> BO 
> which we don't want to evict.
> 
> E.g. something like
> 
> Head -> anchor -> BO1 -> BO2 -> BO3 -> BO4
> 
> And we Evict BO1, BO2 and then find that BO3 doesn't match the 
> allocation pattern we need so only then is the anchor moved after
> BO3:
> 
> Head -> BO3 -> anchor -> BO4....
> 
> And when we moved inside a bulk with an anchor we have already locked
> at 
> least one BO of the bulk, so locking the next one is a no-op.
> 
> > And finally for the tt shinking that's been pending for quite some
> > time, the last comment that made me temporarily shelf is was that
> > we
> > should expose the lru traversal to the drivers, and the drivers
> > implement the shrinkers with TTM helpers, rather than having TTM
> > being
> > the middle layer. So I think exposing the LRU traversal to drivers
> > will
> > probably end up having pretty weird semantics if it sometimes locks
> > or
> > requiring locking of the next object while traversing.
> 
> Yeah, I was just yesterday talking about that with Amar and putting
> him 
> on the task to look into tt shrinking.

Oh, we should probably sync on that then so we don't create two
separate solutions. That'd be wasted work.

I think the key patch in the series I had that made things "work" was
this helper patch here:
https://patchwork.kernel.org/project/intel-gfx/patch/20230215161405.187368-15-thomas.hellstrom@linux.intel.com/

Making sure that we could shrink on a per-page basis (we either insert
the page in the swap cache or it might actually even work with copying
to shmem, since pages are immediately released one by one and not after
copying the whole tt).

Sima has little confidence that we'll find a core mm reviewer to the
patch I made to insert the pages directly into the swap cache.

https://patchwork.kernel.org/project/intel-gfx/patch/20230215161405.187368-13-thomas.hellstrom@linux.intel.com/

/Thomas