[PATCH 0/9] [RFC] fair-lru eviction

[PATCH 0/9] [RFC] fair-lru eviction

[Daniel Vetter]

Hi all,

This patch series implements the fair-lru eviction Chris Wilson already
posted with a twist. It's essentially the same idea & algorithm.
Differnences versus his patch:
- Doesn't do any allocations while scanning.
- Implemented in drm_mm.c

In other words, this should also be usable by ttm. The idea is simple:
Scan through the lru, marking objects as evictable until there is a
large area of memory free/free-able. Then walk through all the scanned
objects in reverse, checking which ones fall into this hole. Finally
evicting them.

Comments, ideas highly welcome.

As per usual, I couldn't resist and had to clean up the code in drm_mm.c a
little.

Yours, Daniel

Daniel Vetter (9):
  list.h: add list_for_each_entry_safe_from_reverse
  drm: use list_for_each_entry in drm_mm.c
  drm: kill drm_mm_node->private
  drm: kill dead code in drm_mm.c
  drm: sane naming for drm_mm.c
  drm_mm: extract check_free_mm_node
  drm: implement helper functions for scanning lru list
  drm/i915: prepare for fair lru eviction
  drm/i915: implement fair lru eviction

 drivers/gpu/drm/drm_mm.c          |  359 ++++++++++++++++++++++++-------------
 drivers/gpu/drm/i915/i915_gem.c   |  122 ++++++++-----
 drivers/gpu/drm/ttm/ttm_bo.c      |    6 -
 drivers/gpu/drm/ttm/ttm_bo_util.c |    2 -
 include/drm/drm_mm.h              |   27 +++-
 include/linux/list.h              |   15 ++
 6 files changed, 347 insertions(+), 184 deletions(-)

[PATCH 1/9] list.h: add list_for_each_entry_safe_from_reverse

[Daniel Vetter]

i915 needs this.

Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
---
 include/linux/list.h |   15 +++++++++++++++
 1 files changed, 15 insertions(+), 0 deletions(-)

diff --git a/include/linux/list.h b/include/linux/list.h
index 8392884..21cdd99 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -544,6 +544,21 @@ static inline void list_splice_tail_init(struct list_head *list,
 	     &pos->member != (head); 					\
 	     pos = n, n = list_entry(n->member.prev, typeof(*n), member))
 
+/**
+ * list_for_each_entry_safe_from_reverse - iterate backwards over list from the current point safe against removal
+ * @pos:	the type * to use as a loop cursor.
+ * @n:		another type * to use as temporary storage
+ * @head:	the head for your list.
+ * @member:	the name of the list_struct within the struct.
+ *
+ * Iterate backwards over list of given type, safe against removal
+ * of list entry.
+ */
+#define list_for_each_entry_safe_from_reverse(pos, n, head, member)		\
+	for (n = list_entry(pos->member.prev, typeof(*pos), member);	\
+	     &pos->member != (head); 					\
+	     pos = n, n = list_entry(n->member.prev, typeof(*n), member))
+
 /*
  * Double linked lists with a single pointer list head.
  * Mostly useful for hash tables where the two pointer list head is
-- 
1.7.1

[PATCH 2/9] drm: use list_for_each_entry in drm_mm.c

[Daniel Vetter]

Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
---
 drivers/gpu/drm/drm_mm.c |    8 ++------
 1 files changed, 2 insertions(+), 6 deletions(-)

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c
index 2ac074c..b75eb55 100644
--- a/drivers/gpu/drm/drm_mm.c
+++ b/drivers/gpu/drm/drm_mm.c
@@ -332,7 +332,6 @@ struct drm_mm_node *drm_mm_search_free(const struct drm_mm *mm,
 				       unsigned long size,
 				       unsigned alignment, int best_match)
 {
-	struct list_head *list;
 	const struct list_head *free_stack = &mm->fl_entry;
 	struct drm_mm_node *entry;
 	struct drm_mm_node *best;
@@ -342,8 +341,7 @@ struct drm_mm_node *drm_mm_search_free(const struct drm_mm *mm,
 	best = NULL;
 	best_size = ~0UL;
 
-	list_for_each(list, free_stack) {
-		entry = list_entry(list, struct drm_mm_node, fl_entry);
+	list_for_each_entry(entry, free_stack, fl_entry) {
 		wasted = 0;
 
 		if (entry->size < size)
@@ -376,7 +374,6 @@ struct drm_mm_node *drm_mm_search_free_in_range(const struct drm_mm *mm,
 						unsigned long end,
 						int best_match)
 {
-	struct list_head *list;
 	const struct list_head *free_stack = &mm->fl_entry;
 	struct drm_mm_node *entry;
 	struct drm_mm_node *best;
@@ -386,8 +383,7 @@ struct drm_mm_node *drm_mm_search_free_in_range(const struct drm_mm *mm,
 	best = NULL;
 	best_size = ~0UL;
 
-	list_for_each(list, free_stack) {
-		entry = list_entry(list, struct drm_mm_node, fl_entry);
+	list_for_each_entry(entry, free_stack, fl_entry) {
 		wasted = 0;
 
 		if (entry->size < size)
-- 
1.7.1

[PATCH 3/9] drm: kill drm_mm_node->private

[Daniel Vetter]

Only ever assigned, never used.

Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
---
 drivers/gpu/drm/i915/i915_gem.c   |    4 +---
 drivers/gpu/drm/ttm/ttm_bo.c      |    6 ------
 drivers/gpu/drm/ttm/ttm_bo_util.c |    2 --
 include/drm/drm_mm.h              |    1 -
 4 files changed, 1 insertions(+), 12 deletions(-)

diff --git a/drivers/gpu/drm/i915/i915_gem.c b/drivers/gpu/drm/i915/i915_gem.c
index f69c1b0..952b4b3 100644
--- a/drivers/gpu/drm/i915/i915_gem.c
+++ b/drivers/gpu/drm/i915/i915_gem.c
@@ -2706,10 +2706,8 @@ i915_gem_object_bind_to_gtt(struct drm_gem_object *obj, unsigned alignment)
 	if (free_space != NULL) {
 		obj_priv->gtt_space = drm_mm_get_block(free_space, obj->size,
 						       alignment);
-		if (obj_priv->gtt_space != NULL) {
-			obj_priv->gtt_space->private = obj;
+		if (obj_priv->gtt_space != NULL)
 			obj_priv->gtt_offset = obj_priv->gtt_space->start;
-		}
 	}
 	if (obj_priv->gtt_space == NULL) {
 		/* If the gtt is empty and we're still having trouble
diff --git a/drivers/gpu/drm/ttm/ttm_bo.c b/drivers/gpu/drm/ttm/ttm_bo.c
index 3b5b094..cf8c303 100644
--- a/drivers/gpu/drm/ttm/ttm_bo.c
+++ b/drivers/gpu/drm/ttm/ttm_bo.c
@@ -476,7 +476,6 @@ static int ttm_bo_cleanup_refs(struct ttm_buffer_object *bo, bool remove_all)
 			++put_count;
 		}
 		if (bo->mem.mm_node) {
-			bo->mem.mm_node->private = NULL;
 			drm_mm_put_block(bo->mem.mm_node);
 			bo->mem.mm_node = NULL;
 		}
@@ -656,7 +655,6 @@ static int ttm_bo_evict(struct ttm_buffer_object *bo, bool interruptible,
 			printk(KERN_ERR TTM_PFX "Buffer eviction failed\n");
 		spin_lock(&glob->lru_lock);
 		if (evict_mem.mm_node) {
-			evict_mem.mm_node->private = NULL;
 			drm_mm_put_block(evict_mem.mm_node);
 			evict_mem.mm_node = NULL;
 		}
@@ -915,8 +913,6 @@ int ttm_bo_mem_space(struct ttm_buffer_object *bo,
 		mem->mm_node = node;
 		mem->mem_type = mem_type;
 		mem->placement = cur_flags;
-		if (node)
-			node->private = bo;
 		return 0;
 	}
 
@@ -959,7 +955,6 @@ int ttm_bo_mem_space(struct ttm_buffer_object *bo,
 						interruptible, no_wait_reserve, no_wait_gpu);
 		if (ret == 0 && mem->mm_node) {
 			mem->placement = cur_flags;
-			mem->mm_node->private = bo;
 			return 0;
 		}
 		if (ret == -ERESTARTSYS)
@@ -1015,7 +1010,6 @@ int ttm_bo_move_buffer(struct ttm_buffer_object *bo,
 out_unlock:
 	if (ret && mem.mm_node) {
 		spin_lock(&glob->lru_lock);
-		mem.mm_node->private = NULL;
 		drm_mm_put_block(mem.mm_node);
 		spin_unlock(&glob->lru_lock);
 	}
diff --git a/drivers/gpu/drm/ttm/ttm_bo_util.c b/drivers/gpu/drm/ttm/ttm_bo_util.c
index 13012a1..7cffb3e 100644
--- a/drivers/gpu/drm/ttm/ttm_bo_util.c
+++ b/drivers/gpu/drm/ttm/ttm_bo_util.c
@@ -353,8 +353,6 @@ static int ttm_buffer_object_transfer(struct ttm_buffer_object *bo,
 	fbo->vm_node = NULL;
 
 	fbo->sync_obj = driver->sync_obj_ref(bo->sync_obj);
-	if (fbo->mem.mm_node)
-		fbo->mem.mm_node->private = (void *)fbo;
 	kref_init(&fbo->list_kref);
 	kref_init(&fbo->kref);
 	fbo->destroy = &ttm_transfered_destroy;
diff --git a/include/drm/drm_mm.h b/include/drm/drm_mm.h
index 4c10be3..da94071 100644
--- a/include/drm/drm_mm.h
+++ b/include/drm/drm_mm.h
@@ -48,7 +48,6 @@ struct drm_mm_node {
 	unsigned long start;
 	unsigned long size;
 	struct drm_mm *mm;
-	void *private;
 };
 
 struct drm_mm {
-- 
1.7.1

Re: [PATCH 3/9] drm: kill drm_mm_node->private

[Jerome Glisse]

On Tue, May 18, 2010 at 11:11:45PM +0200, Daniel Vetter wrote:
> Only ever assigned, never used.
> 
> Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>

NAK

private was to be use when doing range restricted allocation
somehow the patch that use it was drop/forgot/lost along the
was i will try to see i have it and redo it if not.

Cheers,
Jerome

Re: [PATCH 3/9] drm: kill drm_mm_node->private

[Daniel Vetter]

On Wed, May 19, 2010 at 11:25:07AM +0200, Jerome Glisse wrote:
> On Tue, May 18, 2010 at 11:11:45PM +0200, Daniel Vetter wrote:
> > Only ever assigned, never used.
> > 
> > Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
> 
> NAK
> 
> private was to be use when doing range restricted allocation
> somehow the patch that use it was drop/forgot/lost along the
> was i will try to see i have it and redo it if not.

I don't agree for the following reasons:
1) drm_mm _does_ implement range-restricted allocations. And it does not
   use the private pointer to do so. My new scanning algorithm doesn't
   implement this (i915 doesn't use range restricted allocations), but
   it's damn trivial to add.
2) The private pointer was used as a back-pointer to the object. If
   something like this is needed, making struct drm_mm_node embedable
   looks like the right approach (perhaps with some driver-private
   bitfields to distinguish different case). I'm still in the process of
   shooting down the driver_private gem_object pointer and I don't like
   doing this right away again ...

Can you please point me to the code that needs this private pointer? Then I
can see in which way I'm wrong ... ;)

> Cheers,
> Jerome

Cheers, Daniel
-- 
Daniel Vetter
Mail: daniel@ffwll.ch
Mobile: +41 (0)79 365 57 48

Re: [PATCH 3/9] drm: kill drm_mm_node->private

[Jerome Glisse]

On Wed, May 19, 2010 at 07:03:32PM +0200, Daniel Vetter wrote:
> On Wed, May 19, 2010 at 11:25:07AM +0200, Jerome Glisse wrote:
> > On Tue, May 18, 2010 at 11:11:45PM +0200, Daniel Vetter wrote:
> > > Only ever assigned, never used.
> > > 
> > > Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
> > 
> > NAK
> > 
> > private was to be use when doing range restricted allocation
> > somehow the patch that use it was drop/forgot/lost along the
> > was i will try to see i have it and redo it if not.
> 
> I don't agree for the following reasons:
> 1) drm_mm _does_ implement range-restricted allocations. And it does not
>    use the private pointer to do so. My new scanning algorithm doesn't
>    implement this (i915 doesn't use range restricted allocations), but
>    it's damn trivial to add.
> 2) The private pointer was used as a back-pointer to the object. If
>    something like this is needed, making struct drm_mm_node embedable
>    looks like the right approach (perhaps with some driver-private
>    bitfields to distinguish different case). I'm still in the process of
>    shooting down the driver_private gem_object pointer and I don't like
>    doing this right away again ...
> 
> Can you please point me to the code that needs this private pointer? Then I
> can see in which way I'm wrong ... ;)
> 

Ok fine, nuck it, i will readd it if needed once i have time
to get back to this.

Cheers,
Jerome

[PATCH 4/9] drm: kill dead code in drm_mm.c

[Daniel Vetter]

Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
---
 drivers/gpu/drm/drm_mm.c |   45 ---------------------------------------------
 1 files changed, 0 insertions(+), 45 deletions(-)

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c
index b75eb55..a5a7a16 100644
--- a/drivers/gpu/drm/drm_mm.c
+++ b/drivers/gpu/drm/drm_mm.c
@@ -48,36 +48,6 @@
 
 #define MM_UNUSED_TARGET 4
 
-unsigned long drm_mm_tail_space(struct drm_mm *mm)
-{
-	struct list_head *tail_node;
-	struct drm_mm_node *entry;
-
-	tail_node = mm->ml_entry.prev;
-	entry = list_entry(tail_node, struct drm_mm_node, ml_entry);
-	if (!entry->free)
-		return 0;
-
-	return entry->size;
-}
-
-int drm_mm_remove_space_from_tail(struct drm_mm *mm, unsigned long size)
-{
-	struct list_head *tail_node;
-	struct drm_mm_node *entry;
-
-	tail_node = mm->ml_entry.prev;
-	entry = list_entry(tail_node, struct drm_mm_node, ml_entry);
-	if (!entry->free)
-		return -ENOMEM;
-
-	if (entry->size <= size)
-		return -ENOMEM;
-
-	entry->size -= size;
-	return 0;
-}
-
 static struct drm_mm_node *drm_mm_kmalloc(struct drm_mm *mm, int atomic)
 {
 	struct drm_mm_node *child;
@@ -152,21 +122,6 @@ static int drm_mm_create_tail_node(struct drm_mm *mm,
 	return 0;
 }
 
-int drm_mm_add_space_to_tail(struct drm_mm *mm, unsigned long size, int atomic)
-{
-	struct list_head *tail_node;
-	struct drm_mm_node *entry;
-
-	tail_node = mm->ml_entry.prev;
-	entry = list_entry(tail_node, struct drm_mm_node, ml_entry);
-	if (!entry->free) {
-		return drm_mm_create_tail_node(mm, entry->start + entry->size,
-					       size, atomic);
-	}
-	entry->size += size;
-	return 0;
-}
-
 static struct drm_mm_node *drm_mm_split_at_start(struct drm_mm_node *parent,
 						 unsigned long size,
 						 int atomic)
-- 
1.7.1

[PATCH 5/9] drm: sane naming for drm_mm.c

[Daniel Vetter]

Yeah, I've kinda noticed that fl_entry is the free stack. Still
give it (and the memory node list ml_entry) decent names.

Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
---
 drivers/gpu/drm/drm_mm.c |   72 ++++++++++++++++++++++-----------------------
 include/drm/drm_mm.h     |   11 ++++--
 2 files changed, 42 insertions(+), 41 deletions(-)

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c
index a5a7a16..d2267ff 100644
--- a/drivers/gpu/drm/drm_mm.c
+++ b/drivers/gpu/drm/drm_mm.c
@@ -64,8 +64,8 @@ static struct drm_mm_node *drm_mm_kmalloc(struct drm_mm *mm, int atomic)
 		else {
 			child =
 			    list_entry(mm->unused_nodes.next,
-				       struct drm_mm_node, fl_entry);
-			list_del(&child->fl_entry);
+				       struct drm_mm_node, free_stack);
+			list_del(&child->free_stack);
 			--mm->num_unused;
 		}
 		spin_unlock(&mm->unused_lock);
@@ -94,7 +94,7 @@ int drm_mm_pre_get(struct drm_mm *mm)
 			return ret;
 		}
 		++mm->num_unused;
-		list_add_tail(&node->fl_entry, &mm->unused_nodes);
+		list_add_tail(&node->free_stack, &mm->unused_nodes);
 	}
 	spin_unlock(&mm->unused_lock);
 	return 0;
@@ -116,8 +116,8 @@ static int drm_mm_create_tail_node(struct drm_mm *mm,
 	child->start = start;
 	child->mm = mm;
 
-	list_add_tail(&child->ml_entry, &mm->ml_entry);
-	list_add_tail(&child->fl_entry, &mm->fl_entry);
+	list_add_tail(&child->node_list, &mm->node_list);
+	list_add_tail(&child->free_stack, &mm->free_stack);
 
 	return 0;
 }
@@ -132,15 +132,15 @@ static struct drm_mm_node *drm_mm_split_at_start(struct drm_mm_node *parent,
 	if (unlikely(child == NULL))
 		return NULL;
 
-	INIT_LIST_HEAD(&child->fl_entry);
+	INIT_LIST_HEAD(&child->free_stack);
 
 	child->free = 0;
 	child->size = size;
 	child->start = parent->start;
 	child->mm = parent->mm;
 
-	list_add_tail(&child->ml_entry, &parent->ml_entry);
-	INIT_LIST_HEAD(&child->fl_entry);
+	list_add_tail(&child->node_list, &parent->node_list);
+	INIT_LIST_HEAD(&child->free_stack);
 
 	parent->size -= size;
 	parent->start += size;
@@ -168,7 +168,7 @@ struct drm_mm_node *drm_mm_get_block_generic(struct drm_mm_node *node,
 	}
 
 	if (node->size == size) {
-		list_del_init(&node->fl_entry);
+		list_del_init(&node->free_stack);
 		node->free = 0;
 	} else {
 		node = drm_mm_split_at_start(node, size, atomic);
@@ -206,7 +206,7 @@ struct drm_mm_node *drm_mm_get_block_range_generic(struct drm_mm_node *node,
 	}
 
 	if (node->size == size) {
-		list_del_init(&node->fl_entry);
+		list_del_init(&node->free_stack);
 		node->free = 0;
 	} else {
 		node = drm_mm_split_at_start(node, size, atomic);
@@ -228,8 +228,8 @@ void drm_mm_put_block(struct drm_mm_node *cur)
 {
 
 	struct drm_mm *mm = cur->mm;
-	struct list_head *cur_head = &cur->ml_entry;
-	struct list_head *root_head = &mm->ml_entry;
+	struct list_head *cur_head = &cur->node_list;
+	struct list_head *root_head = &mm->node_list;
 	struct drm_mm_node *prev_node = NULL;
 	struct drm_mm_node *next_node;
 
@@ -237,7 +237,7 @@ void drm_mm_put_block(struct drm_mm_node *cur)
 
 	if (cur_head->prev != root_head) {
 		prev_node =
-		    list_entry(cur_head->prev, struct drm_mm_node, ml_entry);
+		    list_entry(cur_head->prev, struct drm_mm_node, node_list);
 		if (prev_node->free) {
 			prev_node->size += cur->size;
 			merged = 1;
@@ -245,15 +245,15 @@ void drm_mm_put_block(struct drm_mm_node *cur)
 	}
 	if (cur_head->next != root_head) {
 		next_node =
-		    list_entry(cur_head->next, struct drm_mm_node, ml_entry);
+		    list_entry(cur_head->next, struct drm_mm_node, node_list);
 		if (next_node->free) {
 			if (merged) {
 				prev_node->size += next_node->size;
-				list_del(&next_node->ml_entry);
-				list_del(&next_node->fl_entry);
+				list_del(&next_node->node_list);
+				list_del(&next_node->free_stack);
 				spin_lock(&mm->unused_lock);
 				if (mm->num_unused < MM_UNUSED_TARGET) {
-					list_add(&next_node->fl_entry,
+					list_add(&next_node->free_stack,
 						 &mm->unused_nodes);
 					++mm->num_unused;
 				} else
@@ -268,12 +268,12 @@ void drm_mm_put_block(struct drm_mm_node *cur)
 	}
 	if (!merged) {
 		cur->free = 1;
-		list_add(&cur->fl_entry, &mm->fl_entry);
+		list_add(&cur->free_stack, &mm->free_stack);
 	} else {
-		list_del(&cur->ml_entry);
+		list_del(&cur->node_list);
 		spin_lock(&mm->unused_lock);
 		if (mm->num_unused < MM_UNUSED_TARGET) {
-			list_add(&cur->fl_entry, &mm->unused_nodes);
+			list_add(&cur->free_stack, &mm->unused_nodes);
 			++mm->num_unused;
 		} else
 			kfree(cur);
@@ -287,7 +287,6 @@ struct drm_mm_node *drm_mm_search_free(const struct drm_mm *mm,
 				       unsigned long size,
 				       unsigned alignment, int best_match)
 {
-	const struct list_head *free_stack = &mm->fl_entry;
 	struct drm_mm_node *entry;
 	struct drm_mm_node *best;
 	unsigned long best_size;
@@ -296,7 +295,7 @@ struct drm_mm_node *drm_mm_search_free(const struct drm_mm *mm,
 	best = NULL;
 	best_size = ~0UL;
 
-	list_for_each_entry(entry, free_stack, fl_entry) {
+	list_for_each_entry(entry, &mm->free_stack, free_stack) {
 		wasted = 0;
 
 		if (entry->size < size)
@@ -329,7 +328,6 @@ struct drm_mm_node *drm_mm_search_free_in_range(const struct drm_mm *mm,
 						unsigned long end,
 						int best_match)
 {
-	const struct list_head *free_stack = &mm->fl_entry;
 	struct drm_mm_node *entry;
 	struct drm_mm_node *best;
 	unsigned long best_size;
@@ -338,7 +336,7 @@ struct drm_mm_node *drm_mm_search_free_in_range(const struct drm_mm *mm,
 	best = NULL;
 	best_size = ~0UL;
 
-	list_for_each_entry(entry, free_stack, fl_entry) {
+	list_for_each_entry(entry, &mm->free_stack, free_stack) {
 		wasted = 0;
 
 		if (entry->size < size)
@@ -373,7 +371,7 @@ EXPORT_SYMBOL(drm_mm_search_free_in_range);
 
 int drm_mm_clean(struct drm_mm * mm)
 {
-	struct list_head *head = &mm->ml_entry;
+	struct list_head *head = &mm->node_list;
 
 	return (head->next->next == head);
 }
@@ -381,8 +379,8 @@ EXPORT_SYMBOL(drm_mm_clean);
 
 int drm_mm_init(struct drm_mm * mm, unsigned long start, unsigned long size)
 {
-	INIT_LIST_HEAD(&mm->ml_entry);
-	INIT_LIST_HEAD(&mm->fl_entry);
+	INIT_LIST_HEAD(&mm->node_list);
+	INIT_LIST_HEAD(&mm->free_stack);
 	INIT_LIST_HEAD(&mm->unused_nodes);
 	mm->num_unused = 0;
 	spin_lock_init(&mm->unused_lock);
@@ -393,25 +391,25 @@ EXPORT_SYMBOL(drm_mm_init);
 
 void drm_mm_takedown(struct drm_mm * mm)
 {
-	struct list_head *bnode = mm->fl_entry.next;
+	struct list_head *bnode = mm->free_stack.next;
 	struct drm_mm_node *entry;
 	struct drm_mm_node *next;
 
-	entry = list_entry(bnode, struct drm_mm_node, fl_entry);
+	entry = list_entry(bnode, struct drm_mm_node, free_stack);
 
-	if (entry->ml_entry.next != &mm->ml_entry ||
-	    entry->fl_entry.next != &mm->fl_entry) {
+	if (entry->node_list.next != &mm->node_list ||
+	    entry->free_stack.next != &mm->free_stack) {
 		DRM_ERROR("Memory manager not clean. Delaying takedown\n");
 		return;
 	}
 
-	list_del(&entry->fl_entry);
-	list_del(&entry->ml_entry);
+	list_del(&entry->free_stack);
+	list_del(&entry->node_list);
 	kfree(entry);
 
 	spin_lock(&mm->unused_lock);
-	list_for_each_entry_safe(entry, next, &mm->unused_nodes, fl_entry) {
-		list_del(&entry->fl_entry);
+	list_for_each_entry_safe(entry, next, &mm->unused_nodes, free_stack) {
+		list_del(&entry->free_stack);
 		kfree(entry);
 		--mm->num_unused;
 	}
@@ -426,7 +424,7 @@ void drm_mm_debug_table(struct drm_mm *mm, const char *prefix)
 	struct drm_mm_node *entry;
 	int total_used = 0, total_free = 0, total = 0;
 
-	list_for_each_entry(entry, &mm->ml_entry, ml_entry) {
+	list_for_each_entry(entry, &mm->node_list, node_list) {
 		printk(KERN_DEBUG "%s 0x%08lx-0x%08lx: %8ld: %s\n",
 			prefix, entry->start, entry->start + entry->size,
 			entry->size, entry->free ? "free" : "used");
@@ -447,7 +445,7 @@ int drm_mm_dump_table(struct seq_file *m, struct drm_mm *mm)
 	struct drm_mm_node *entry;
 	int total_used = 0, total_free = 0, total = 0;
 
-	list_for_each_entry(entry, &mm->ml_entry, ml_entry) {
+	list_for_each_entry(entry, &mm->node_list, node_list) {
 		seq_printf(m, "0x%08lx-0x%08lx: 0x%08lx: %s\n", entry->start, entry->start + entry->size, entry->size, entry->free ? "free" : "used");
 		total += entry->size;
 		if (entry->free)
diff --git a/include/drm/drm_mm.h b/include/drm/drm_mm.h
index da94071..e8740cc 100644
--- a/include/drm/drm_mm.h
+++ b/include/drm/drm_mm.h
@@ -42,8 +42,8 @@
 #endif
 
 struct drm_mm_node {
-	struct list_head fl_entry;
-	struct list_head ml_entry;
+	struct list_head free_stack;
+	struct list_head node_list;
 	int free;
 	unsigned long start;
 	unsigned long size;
@@ -51,8 +51,11 @@ struct drm_mm_node {
 };
 
 struct drm_mm {
-	struct list_head fl_entry;
-	struct list_head ml_entry;
+	/* List of free memory blocks, most recently freed ordered. */
+	struct list_head free_stack;
+	/* List of all memory nodes, ordered according to the (increasing) start
+	 * address of the memory node. */
+	struct list_head node_list;
 	struct list_head unused_nodes;
 	int num_unused;
 	spinlock_t unused_lock;
-- 
1.7.1

[PATCH 6/9] drm_mm: extract check_free_mm_node

[Daniel Vetter]

There are already two copies of this logic. And the new scanning
stuff will add some more. So extract it into a small helper
function.

Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
---
 drivers/gpu/drm/drm_mm.c |   71 ++++++++++++++++++++++------------------------
 1 files changed, 34 insertions(+), 37 deletions(-)

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c
index d2267ff..fd86a6c 100644
--- a/drivers/gpu/drm/drm_mm.c
+++ b/drivers/gpu/drm/drm_mm.c
@@ -283,6 +283,27 @@ void drm_mm_put_block(struct drm_mm_node *cur)
 
 EXPORT_SYMBOL(drm_mm_put_block);
 
+static int check_free_mm_node(struct drm_mm_node *entry, unsigned long size,
+			      unsigned alignment)
+{
+	unsigned wasted = 0;
+
+	if (entry->size < size)
+		return 0;
+
+	if (alignment) {
+		register unsigned tmp = entry->start % alignment;
+		if (tmp)
+			wasted = alignment - tmp;
+	}
+
+	if (entry->size >= size + wasted) {
+		return 1;
+	}
+
+	return 0;
+}
+
 struct drm_mm_node *drm_mm_search_free(const struct drm_mm *mm,
 				       unsigned long size,
 				       unsigned alignment, int best_match)
@@ -290,30 +311,20 @@ struct drm_mm_node *drm_mm_search_free(const struct drm_mm *mm,
 	struct drm_mm_node *entry;
 	struct drm_mm_node *best;
 	unsigned long best_size;
-	unsigned wasted;
 
 	best = NULL;
 	best_size = ~0UL;
 
 	list_for_each_entry(entry, &mm->free_stack, free_stack) {
-		wasted = 0;
-
-		if (entry->size < size)
+		if (!check_free_mm_node(entry, size, alignment))
 			continue;
 
-		if (alignment) {
-			register unsigned tmp = entry->start % alignment;
-			if (tmp)
-				wasted += alignment - tmp;
-		}
+		if (!best_match)
+			return entry;
 
-		if (entry->size >= size + wasted) {
-			if (!best_match)
-				return entry;
-			if (entry->size < best_size) {
-				best = entry;
-				best_size = entry->size;
-			}
+		if (entry->size < best_size) {
+			best = entry;
+			best_size = entry->size;
 		}
 	}
 
@@ -331,37 +342,23 @@ struct drm_mm_node *drm_mm_search_free_in_range(const struct drm_mm *mm,
 	struct drm_mm_node *entry;
 	struct drm_mm_node *best;
 	unsigned long best_size;
-	unsigned wasted;
 
 	best = NULL;
 	best_size = ~0UL;
 
 	list_for_each_entry(entry, &mm->free_stack, free_stack) {
-		wasted = 0;
-
-		if (entry->size < size)
+		if (entry->start > end || (entry->start+entry->size) < start)
 			continue;
 
-		if (entry->start > end || (entry->start+entry->size) < start)
+		if (!check_free_mm_node(entry, size, alignment))
 			continue;
 
-		if (entry->start < start)
-			wasted += start - entry->start;
+		if (!best_match)
+			return entry;
 
-		if (alignment) {
-			register unsigned tmp = (entry->start + wasted) % alignment;
-			if (tmp)
-				wasted += alignment - tmp;
-		}
-
-		if (entry->size >= size + wasted &&
-		    (entry->start + wasted + size) <= end) {
-			if (!best_match)
-				return entry;
-			if (entry->size < best_size) {
-				best = entry;
-				best_size = entry->size;
-			}
+		if (entry->size < best_size) {
+			best = entry;
+			best_size = entry->size;
 		}
 	}
 
-- 
1.7.1

[PATCH 7/9] drm: implement helper functions for scanning lru list

[Daniel Vetter]

These helper functions can be used to efficiently scan lru list
for eviction. Eviction becomes a three stage process:
1. Scanning through the lru list until a suitable hole has been found.
2. Scan backwards to restore drm_mm consistency and find out which
   objects fall into the hole.
3. Evict the objects that fall into the hole.

These helper functions don't allocate any memory (at the price of
not allowing any other concurrent operations). Hence this can also be
used for ttm (which does lru scanning under a spinlock).

Evicting objects in this fashion should be more fair than the current
approach by i915 (scan the lru for a object large enough to contain
the new object). It's also more efficient than the current approach used
by ttm (uncoditionally evict objects from the lru until there's enough
free space).

Signed-Off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
---
 drivers/gpu/drm/drm_mm.c |  167 ++++++++++++++++++++++++++++++++++++++++++++-
 include/drm/drm_mm.h     |   15 ++++-
 2 files changed, 177 insertions(+), 5 deletions(-)

diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c
index fd86a6c..da99edc 100644
--- a/drivers/gpu/drm/drm_mm.c
+++ b/drivers/gpu/drm/drm_mm.c
@@ -53,9 +53,9 @@ static struct drm_mm_node *drm_mm_kmalloc(struct drm_mm *mm, int atomic)
 	struct drm_mm_node *child;
 
 	if (atomic)
-		child = kmalloc(sizeof(*child), GFP_ATOMIC);
+		child = kzalloc(sizeof(*child), GFP_ATOMIC);
 	else
-		child = kmalloc(sizeof(*child), GFP_KERNEL);
+		child = kzalloc(sizeof(*child), GFP_KERNEL);
 
 	if (unlikely(child == NULL)) {
 		spin_lock(&mm->unused_lock);
@@ -85,7 +85,7 @@ int drm_mm_pre_get(struct drm_mm *mm)
 	spin_lock(&mm->unused_lock);
 	while (mm->num_unused < MM_UNUSED_TARGET) {
 		spin_unlock(&mm->unused_lock);
-		node = kmalloc(sizeof(*node), GFP_KERNEL);
+		node = kzalloc(sizeof(*node), GFP_KERNEL);
 		spin_lock(&mm->unused_lock);
 
 		if (unlikely(node == NULL)) {
@@ -134,7 +134,6 @@ static struct drm_mm_node *drm_mm_split_at_start(struct drm_mm_node *parent,
 
 	INIT_LIST_HEAD(&child->free_stack);
 
-	child->free = 0;
 	child->size = size;
 	child->start = parent->start;
 	child->mm = parent->mm;
@@ -235,6 +234,9 @@ void drm_mm_put_block(struct drm_mm_node *cur)
 
 	int merged = 0;
 
+	BUG_ON(cur->scanned_block || cur->scanned_prev_free
+				  || cur->scanned_next_free);
+
 	if (cur_head->prev != root_head) {
 		prev_node =
 		    list_entry(cur_head->prev, struct drm_mm_node, node_list);
@@ -312,6 +314,8 @@ struct drm_mm_node *drm_mm_search_free(const struct drm_mm *mm,
 	struct drm_mm_node *best;
 	unsigned long best_size;
 
+	BUG_ON(mm->scanned_blocks);
+
 	best = NULL;
 	best_size = ~0UL;
 
@@ -343,6 +347,8 @@ struct drm_mm_node *drm_mm_search_free_in_range(const struct drm_mm *mm,
 	struct drm_mm_node *best;
 	unsigned long best_size;
 
+	BUG_ON(mm->scanned_blocks);
+
 	best = NULL;
 	best_size = ~0UL;
 
@@ -366,6 +372,158 @@ struct drm_mm_node *drm_mm_search_free_in_range(const struct drm_mm *mm,
 }
 EXPORT_SYMBOL(drm_mm_search_free_in_range);
 
+/**
+ * Initializa lru scanning.
+ *
+ * This simply sets up the scanning routines with the parameters for the desired
+ * hole.
+ *
+ * Warning: As long as the scan list is non-empty, no other operations than
+ * adding/removing nodes to/from the scan list are allowed.
+ */
+void drm_mm_init_scan(struct drm_mm *mm, unsigned long size,
+		      unsigned alignment)
+{
+	mm->scan_alignment = alignment;
+	mm->scan_size = size;
+	mm->scanned_blocks = 0;
+	mm->scan_hit_start = 0;
+	mm->scan_hit_size = 0;
+}
+EXPORT_SYMBOL(drm_mm_init_scan);
+
+/**
+ * Add a node to the scan list that might be freed to make space for the desired
+ * hole.
+ *
+ * Returns non-zero, if a hole has been found, zero otherwise.
+ */
+int drm_mm_scan_add_block(struct drm_mm_node *node)
+{
+	struct drm_mm *mm = node->mm;
+	struct list_head *prev_free, *next_free;
+	struct drm_mm_node *prev_node, *next_node;
+
+	mm->scanned_blocks++;
+
+	prev_free = next_free = NULL;
+
+	BUG_ON(node->free);
+	node->scanned_block = 1;
+	node->free = 1;
+
+	if (node->node_list.prev != &mm->node_list) {
+		prev_node = list_entry(node->node_list.prev, struct drm_mm_node,
+				       node_list);
+
+		if (prev_node->free) {
+			list_del(&prev_node->node_list);
+
+			node->start = prev_node->start;
+			node->size += prev_node->size;
+
+			prev_node->scanned_prev_free = 1;
+
+			prev_free = &prev_node->free_stack;
+		}
+	}
+
+	if (node->node_list.next != &mm->node_list) {
+		next_node = list_entry(node->node_list.next, struct drm_mm_node,
+				       node_list);
+
+		if (next_node->free) {
+			list_del(&next_node->node_list);
+
+			node->size += next_node->size;
+
+			next_node->scanned_next_free = 1;
+
+			next_free = &next_node->free_stack;
+		}
+	}
+
+	/* The free_stack list is not used for allocated objects, so these two
+	 * pointers can be abused (as long as no allocations in this memory
+	 * manager happens). */
+	node->free_stack.prev = prev_free;
+	node->free_stack.next = next_free;
+
+	if (check_free_mm_node(node, mm->scan_size, mm->scan_alignment)) {
+		mm->scan_hit_start = node->start;
+		mm->scan_hit_size = node->size;
+
+		return 1;
+	}
+
+	return 0;
+}
+EXPORT_SYMBOL(drm_mm_scan_add_block);
+
+/**
+ * Remove a node from the scan list.
+ *
+ * Nodes _must_ be removed in the exact same order from the scan list as they
+ * have been added, otherwise the internal state of the memory manager will be
+ * corrupted.
+ *
+ * When the scan list is empty, the selected memory nodes can be freed. An
+ * immediatly following drm_mm_search_free with best_match = 0 will then return
+ * the just freed block (because its at the top of the free_stack list).
+ *
+ * Returns one if this block should be evicted, zero otherwise. Will always
+ * return zero when no hole has been found.
+ */
+int drm_mm_scan_remove_block(struct drm_mm_node *node)
+{
+	struct drm_mm *mm = node->mm;
+	struct drm_mm_node *prev_node, *next_node;
+
+	mm->scanned_blocks--;
+
+	BUG_ON(!node->scanned_block);
+	node->scanned_block = 0;
+	node->free = 0;
+
+	prev_node = list_entry(node->free_stack.prev, struct drm_mm_node,
+			       free_stack);
+	next_node = list_entry(node->free_stack.next, struct drm_mm_node,
+			       free_stack);
+
+	if (prev_node) {
+		BUG_ON(!prev_node->scanned_prev_free);
+		prev_node->scanned_prev_free = 0;
+
+		list_add_tail(&prev_node->node_list, &node->node_list);
+
+		node->start = prev_node->start + prev_node->size;
+		node->size -= prev_node->size;
+	}
+
+	if (next_node) {
+		BUG_ON(!next_node->scanned_next_free);
+		next_node->scanned_next_free = 0;
+
+		list_add(&next_node->node_list, &node->node_list);
+
+		node->size -= next_node->size;
+	}
+
+	INIT_LIST_HEAD(&node->free_stack);
+
+	/* Only need to check for containement because start&size for the
+	 * complete resulting free block (not just the desired part) is
+	 * stored. */
+	if (node->start >= mm->scan_hit_start &&
+	    node->start + node->size
+	    		<= mm->scan_hit_start + mm->scan_hit_size) {
+		return 1;
+	}
+
+	return 0;
+}
+EXPORT_SYMBOL(drm_mm_scan_remove_block);
+
 int drm_mm_clean(struct drm_mm * mm)
 {
 	struct list_head *head = &mm->node_list;
@@ -380,6 +538,7 @@ int drm_mm_init(struct drm_mm * mm, unsigned long start, unsigned long size)
 	INIT_LIST_HEAD(&mm->free_stack);
 	INIT_LIST_HEAD(&mm->unused_nodes);
 	mm->num_unused = 0;
+	mm->scanned_blocks = 0;
 	spin_lock_init(&mm->unused_lock);
 
 	return drm_mm_create_tail_node(mm, start, size, 0);
diff --git a/include/drm/drm_mm.h b/include/drm/drm_mm.h
index e8740cc..bf01531 100644
--- a/include/drm/drm_mm.h
+++ b/include/drm/drm_mm.h
@@ -44,7 +44,10 @@
 struct drm_mm_node {
 	struct list_head free_stack;
 	struct list_head node_list;
-	int free;
+	unsigned free : 1;
+	unsigned scanned_block : 1;
+	unsigned scanned_prev_free : 1;
+	unsigned scanned_next_free : 1;
 	unsigned long start;
 	unsigned long size;
 	struct drm_mm *mm;
@@ -59,6 +62,11 @@ struct drm_mm {
 	struct list_head unused_nodes;
 	int num_unused;
 	spinlock_t unused_lock;
+	unsigned scan_alignment;
+	unsigned long scan_size;
+	unsigned long scan_hit_start;
+	unsigned scan_hit_size;
+	unsigned scanned_blocks;
 };
 
 /*
@@ -135,6 +143,11 @@ static inline struct drm_mm *drm_get_mm(struct drm_mm_node *block)
 	return block->mm;
 }
 
+void drm_mm_init_scan(struct drm_mm *mm, unsigned long size,
+		      unsigned alignment);
+int drm_mm_scan_add_block(struct drm_mm_node *node);
+int drm_mm_scan_remove_block(struct drm_mm_node *node);
+
 extern void drm_mm_debug_table(struct drm_mm *mm, const char *prefix);
 #ifdef CONFIG_DEBUG_FS
 int drm_mm_dump_table(struct seq_file *m, struct drm_mm *mm);
-- 
1.7.1

[PATCH 8/9] drm/i915: prepare for fair lru eviction

[Daniel Vetter]

This does two little changes:

- Add an alignment parameter for evict_something. It's not really great to
  whack a carefully sized hole into the gtt with the wrong alignment.
  Especially since the fallback path is a full evict.

- With the inactive scan stuff we need to evict more that one object, so
  move the unbind call into the helper function that scans for the object
  to be evicted, too.  And adjust its name.

No functional changes in this patch, just preparation.

Signed-Off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
---
 drivers/gpu/drm/i915/i915_gem.c |   65 +++++++++++++++++++++++---------------
 1 files changed, 39 insertions(+), 26 deletions(-)

diff --git a/drivers/gpu/drm/i915/i915_gem.c b/drivers/gpu/drm/i915/i915_gem.c
index 952b4b3..d5a7db7 100644
--- a/drivers/gpu/drm/i915/i915_gem.c
+++ b/drivers/gpu/drm/i915/i915_gem.c
@@ -50,7 +50,8 @@ static int i915_gem_object_wait_rendering(struct drm_gem_object *obj);
 static int i915_gem_object_bind_to_gtt(struct drm_gem_object *obj,
 					   unsigned alignment);
 static void i915_gem_clear_fence_reg(struct drm_gem_object *obj);
-static int i915_gem_evict_something(struct drm_device *dev, int min_size);
+static int i915_gem_evict_something(struct drm_device *dev, int min_size,
+				    unsigned alignment);
 static int i915_gem_evict_from_inactive_list(struct drm_device *dev);
 static int i915_gem_phys_pwrite(struct drm_device *dev, struct drm_gem_object *obj,
 				struct drm_i915_gem_pwrite *args,
@@ -333,7 +334,7 @@ i915_gem_object_get_pages_or_evict(struct drm_gem_object *obj)
 	if (ret == -ENOMEM) {
 		struct drm_device *dev = obj->dev;
 
-		ret = i915_gem_evict_something(dev, obj->size);
+		ret = i915_gem_evict_something(dev, obj->size, 0);
 		if (ret)
 			return ret;
 
@@ -2114,10 +2115,12 @@ i915_gem_object_unbind(struct drm_gem_object *obj)
 	return 0;
 }
 
-static struct drm_gem_object *
-i915_gem_find_inactive_object(struct drm_device *dev, int min_size)
+static int
+i915_gem_scan_inactive_list_and_evict(struct drm_device *dev, int min_size,
+				      unsigned alignment, int *found)
 {
 	drm_i915_private_t *dev_priv = dev->dev_private;
+	struct drm_gem_object *obj;
 	struct drm_i915_gem_object *obj_priv;
 	struct drm_gem_object *best = NULL;
 	struct drm_gem_object *first = NULL;
@@ -2131,14 +2134,31 @@ i915_gem_find_inactive_object(struct drm_device *dev, int min_size)
 			    (!best || obj->size < best->size)) {
 				best = obj;
 				if (best->size == min_size)
-					return best;
+					break;
 			}
 			if (!first)
 			    first = obj;
 		}
 	}
 
-	return best ? best : first;
+	obj = best ? best : first;
+
+	if (!obj) {
+		*found = 0;
+		return 0;
+	}
+
+	*found = 1;
+
+#if WATCH_LRU
+	DRM_INFO("%s: evicting %p\n", __func__, obj);
+#endif
+	obj_priv = to_intel_bo(obj);
+	BUG_ON(obj_priv->pin_count != 0);
+	BUG_ON(obj_priv->active);
+
+	/* Wait on the rendering and unbind the buffer. */
+	return i915_gem_object_unbind(obj);
 }
 
 static int
@@ -2203,11 +2223,11 @@ i915_gem_evict_everything(struct drm_device *dev)
 }
 
 static int
-i915_gem_evict_something(struct drm_device *dev, int min_size)
+i915_gem_evict_something(struct drm_device *dev,
+			 int min_size, unsigned alignment)
 {
 	drm_i915_private_t *dev_priv = dev->dev_private;
-	struct drm_gem_object *obj;
-	int ret;
+	int ret, found;
 
 	for (;;) {
 		i915_gem_retire_requests(dev);
@@ -2215,20 +2235,11 @@ i915_gem_evict_something(struct drm_device *dev, int min_size)
 		/* If there's an inactive buffer available now, grab it
 		 * and be done.
 		 */
-		obj = i915_gem_find_inactive_object(dev, min_size);
-		if (obj) {
-			struct drm_i915_gem_object *obj_priv;
-
-#if WATCH_LRU
-			DRM_INFO("%s: evicting %p\n", __func__, obj);
-#endif
-			obj_priv = to_intel_bo(obj);
-			BUG_ON(obj_priv->pin_count != 0);
-			BUG_ON(obj_priv->active);
-
-			/* Wait on the rendering and unbind the buffer. */
-			return i915_gem_object_unbind(obj);
-		}
+		ret = i915_gem_scan_inactive_list_and_evict(dev, min_size,
+							    alignment,
+							    &found);
+		if (found)
+			return ret;
 
 		/* If we didn't get anything, but the ring is still processing
 		 * things, wait for the next to finish and hopefully leave us
@@ -2254,6 +2265,7 @@ i915_gem_evict_something(struct drm_device *dev, int min_size)
 		 * will get moved to inactive.
 		 */
 		if (!list_empty(&dev_priv->mm.flushing_list)) {
+			struct drm_gem_object *obj = NULL;
 			struct drm_i915_gem_object *obj_priv;
 
 			/* Find an object that we can immediately reuse */
@@ -2716,7 +2728,7 @@ i915_gem_object_bind_to_gtt(struct drm_gem_object *obj, unsigned alignment)
 #if WATCH_LRU
 		DRM_INFO("%s: GTT full, evicting something\n", __func__);
 #endif
-		ret = i915_gem_evict_something(dev, obj->size);
+		ret = i915_gem_evict_something(dev, obj->size, alignment);
 		if (ret)
 			return ret;
 
@@ -2734,7 +2746,8 @@ i915_gem_object_bind_to_gtt(struct drm_gem_object *obj, unsigned alignment)
 
 		if (ret == -ENOMEM) {
 			/* first try to clear up some space from the GTT */
-			ret = i915_gem_evict_something(dev, obj->size);
+			ret = i915_gem_evict_something(dev, obj->size,
+						       alignment);
 			if (ret) {
 				/* now try to shrink everyone else */
 				if (gfpmask) {
@@ -2764,7 +2777,7 @@ i915_gem_object_bind_to_gtt(struct drm_gem_object *obj, unsigned alignment)
 		drm_mm_put_block(obj_priv->gtt_space);
 		obj_priv->gtt_space = NULL;
 
-		ret = i915_gem_evict_something(dev, obj->size);
+		ret = i915_gem_evict_something(dev, obj->size, alignment);
 		if (ret)
 			return ret;
 
-- 
1.7.1

[PATCH 9/9] drm/i915: implement fair lru eviction

[Daniel Vetter]

Besides that this should leader to better gtt usage (by not favouring
small objects) this also fixes the eviction-ping-pong-of-doom.

Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
---
 drivers/gpu/drm/i915/i915_gem.c |   79 +++++++++++++++++++++++++-------------
 1 files changed, 52 insertions(+), 27 deletions(-)

diff --git a/drivers/gpu/drm/i915/i915_gem.c b/drivers/gpu/drm/i915/i915_gem.c
index d5a7db7..71b01b8 100644
--- a/drivers/gpu/drm/i915/i915_gem.c
+++ b/drivers/gpu/drm/i915/i915_gem.c
@@ -2120,45 +2120,70 @@ i915_gem_scan_inactive_list_and_evict(struct drm_device *dev, int min_size,
 				      unsigned alignment, int *found)
 {
 	drm_i915_private_t *dev_priv = dev->dev_private;
-	struct drm_gem_object *obj;
-	struct drm_i915_gem_object *obj_priv;
-	struct drm_gem_object *best = NULL;
-	struct drm_gem_object *first = NULL;
+	struct list_head eviction_list;
+	struct drm_i915_gem_object *obj_priv, *tmp_obj_priv;
+	int ret = 0;
+
+	INIT_LIST_HEAD(&eviction_list);
+	*found = 0;
+
+	drm_mm_init_scan(&dev_priv->mm.gtt_space, min_size, alignment);
 
-	/* Try to find the smallest clean object */
 	list_for_each_entry(obj_priv, &dev_priv->mm.inactive_list, list) {
-		struct drm_gem_object *obj = &obj_priv->base;
-		if (obj->size >= min_size) {
-			if ((!obj_priv->dirty ||
-			     i915_gem_object_is_purgeable(obj_priv)) &&
-			    (!best || obj->size < best->size)) {
-				best = obj;
-				if (best->size == min_size)
-					break;
-			}
-			if (!first)
-			    first = obj;
-		}
+		*found = drm_mm_scan_add_block(obj_priv->gtt_space);
+
+		if (*found)
+			break;
 	}
 
-	obj = best ? best : first;
+	if (!*found) {
+		/* Nothing found, clean up and bail out! */
+		list_for_each_entry_safe_reverse(obj_priv, tmp_obj_priv,
+						 &dev_priv->mm.inactive_list,
+						 list) {
+			ret = drm_mm_scan_remove_block(obj_priv->gtt_space);
+
+			BUG_ON(ret);
+		}
 
-	if (!obj) {
-		*found = 0;
 		return 0;
 	}
 
-	*found = 1;
+	list_for_each_entry_safe_from_reverse(obj_priv, tmp_obj_priv,
+					      &dev_priv->mm.inactive_list,
+					      list) {
+		if (drm_mm_scan_remove_block(obj_priv->gtt_space)) {
+			/* drm_mm doesn't allow any other other operations while
+			 * scanning, therefore store to be evicted objects on a
+			 * temporary list. */
+			list_move(&obj_priv->list, &eviction_list);
+		}
+	}
 
+	list_for_each_entry_safe(obj_priv, tmp_obj_priv,
+				 &eviction_list, list) {
 #if WATCH_LRU
-	DRM_INFO("%s: evicting %p\n", __func__, obj);
+		DRM_INFO("%s: evicting %p\n", __func__, obj);
 #endif
-	obj_priv = to_intel_bo(obj);
-	BUG_ON(obj_priv->pin_count != 0);
-	BUG_ON(obj_priv->active);
+		ret = i915_gem_object_unbind(&obj_priv->base);
+
+		if (ret != 0)
+			goto fail;
+	}
 
-	/* Wait on the rendering and unbind the buffer. */
-	return i915_gem_object_unbind(obj);
+	/* The just created free hole should be on the top of the free stack
+	 * maintained by drm_mm, so this BUG_ON actually executes in O(1).
+	 * Furthermore all accessed data has just recently been used, so it
+	 * should be really fast, too. */
+	BUG_ON(!drm_mm_search_free(&dev_priv->mm.gtt_space, min_size,
+				   alignment, 0));
+
+	return 0;
+
+fail:
+	list_splice(&eviction_list, &dev_priv->mm.inactive_list);
+
+	return ret;
 }
 
 static int
-- 
1.7.1

Re: [PATCH 0/9] [RFC] fair-lru eviction

[Eric Anholt]

[-- Attachment #1.1: Type: text/plain, Size: 850 bytes --]

On Tue, 18 May 2010 23:11:42 +0200, Daniel Vetter <daniel.vetter@ffwll.ch> wrote:
> Hi all,
> 
> This patch series implements the fair-lru eviction Chris Wilson already
> posted with a twist. It's essentially the same idea & algorithm.
> Differnences versus his patch:
> - Doesn't do any allocations while scanning.
> - Implemented in drm_mm.c
> 
> In other words, this should also be usable by ttm. The idea is simple:
> Scan through the lru, marking objects as evictable until there is a
> large area of memory free/free-able. Then walk through all the scanned
> objects in reverse, checking which ones fall into this hole. Finally
> evicting them.
> 
> Comments, ideas highly welcome.
> 
> As per usual, I couldn't resist and had to clean up the code in drm_mm.c a
> little.

Do you have performance numbers on these patches?

[-- Attachment #1.2: Type: application/pgp-signature, Size: 197 bytes --]

[-- Attachment #2: Type: text/plain, Size: 159 bytes --]

_______________________________________________
dri-devel mailing list
dri-devel@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/dri-devel

Re: [PATCH 0/9] [RFC] fair-lru eviction

[Chris Wilson]

On Tue, 18 May 2010 23:11:42 +0200, Daniel Vetter <daniel.vetter@ffwll.ch> wrote:
> Hi all,
> 
> This patch series implements the fair-lru eviction Chris Wilson already
> posted with a twist. It's essentially the same idea & algorithm.
> Differnences versus his patch:
> - Doesn't do any allocations while scanning.
> - Implemented in drm_mm.c
> 
> In other words, this should also be usable by ttm. The idea is simple:
> Scan through the lru, marking objects as evictable until there is a
> large area of memory free/free-able. Then walk through all the scanned
> objects in reverse, checking which ones fall into this hole. Finally
> evicting them.
> 
> Comments, ideas highly welcome.

The next adaptation I did was to clean up evict_something to add objects
from the inactive, active&&!pinned&&!write, flushing&&!pinned,
active&&!pinned&&write lists. This reduces the logic in evict_something to
a single scan over the available objects in LRU order.

We still need the move-to-inactive-tail upon access by the CPU, and I
think it is acceptable to maintain our preference of the GPU over the CPU.
Recovering memory from the CPU is comparatively cheap.

Comparing 'while :; do yes > /tmp/yes; done & cairo-perf-trace', there is
no significant delta between the fair LRU and current. I'll rebase my
evict_something() on top of your drm_mm, and rerun the tests.

-- 
Chris Wilson, Intel Open Source Technology Centre

Re: [PATCH 0/9] [RFC] fair-lru eviction

[Daniel Vetter]

On Wed, May 19, 2010 at 09:06:52AM +0100, Chris Wilson wrote:
> On Tue, 18 May 2010 23:11:42 +0200, Daniel Vetter <daniel.vetter@ffwll.ch> wrote:
> > Hi all,
> > 
> > This patch series implements the fair-lru eviction Chris Wilson already
> > posted with a twist. It's essentially the same idea & algorithm.
> > Differnences versus his patch:
> > - Doesn't do any allocations while scanning.
> > - Implemented in drm_mm.c
> > 
> > In other words, this should also be usable by ttm. The idea is simple:
> > Scan through the lru, marking objects as evictable until there is a
> > large area of memory free/free-able. Then walk through all the scanned
> > objects in reverse, checking which ones fall into this hole. Finally
> > evicting them.
> > 
> > Comments, ideas highly welcome.
> 
> The next adaptation I did was to clean up evict_something to add objects
> from the inactive, active&&!pinned&&!write, flushing&&!pinned,
> active&&!pinned&&write lists. This reduces the logic in evict_something to
> a single scan over the available objects in LRU order.

Is this really worth it? I've worried about the rescanning in case there's
no suitable hole in the inactive list, too. But we're doing that also in
the current code. And the new code doesn't change the algorithmic
complexity (still O(number_of_inactive_objects)) so we're not gonna hit an
ugly corner case.  Furthermore some printk instrumentation showed that for
a full cairo-perf-traces run on my i855 only three times (over the hole
run, including rescans when new stuff arrived on the inactive list) there
was no suitable hole in the inactive list. So I've stopped worrying.

> We still need the move-to-inactive-tail upon access by the CPU, and I
> think it is acceptable to maintain our preference of the GPU over the CPU.
> Recovering memory from the CPU is comparatively cheap.

Argh, I've totally forgotten to put that list_move_tail into gem_fault
(and probably gtt_(write|read)_fast, too).

> Comparing 'while :; do yes > /tmp/yes; done & cairo-perf-trace', there is
> no significant delta between the fair LRU and current. I'll rebase my
> evict_something() on top of your drm_mm, and rerun the tests.

I'm still crunching the numbers, but preliminary benchmarks on my i855
show that there are _no_ regressions in cairo-traces (poppler is the only
one to take a hit of 1% which is decently below it's noise floor of 2%;).
Speedups are comparable to what you've posted on the list for your patches

Cheers, Daniel
-- 
Daniel Vetter
Mail: daniel@ffwll.ch
Mobile: +41 (0)79 365 57 48

Re: [PATCH 0/9] [RFC] fair-lru eviction

[Chris Wilson]

On Wed, 19 May 2010 18:57:52 +0200, Daniel Vetter <daniel@ffwll.ch> wrote:
> On Wed, May 19, 2010 at 09:06:52AM +0100, Chris Wilson wrote:
> > The next adaptation I did was to clean up evict_something to add objects
> > from the inactive, active&&!pinned&&!write, flushing&&!pinned,
> > active&&!pinned&&write lists. This reduces the logic in evict_something to
> > a single scan over the available objects in LRU order.
> 
> Is this really worth it? I've worried about the rescanning in case there's
> no suitable hole in the inactive list, too. But we're doing that also in
> the current code. And the new code doesn't change the algorithmic
> complexity (still O(number_of_inactive_objects)) so we're not gonna hit an
> ugly corner case.

I actually thought it simplified the code and really clarified the rescan
logic - which is not at all obvious as it depends upon the caller as well.

>  Furthermore some printk instrumentation showed that for
> a full cairo-perf-traces run on my i855 only three times (over the hole
> run, including rescans when new stuff arrived on the inactive list) there
> was no suitable hole in the inactive list. So I've stopped worrying.

I can generate more... But yes, I don't think cairo-perf-trace is a
sufficiently aggressive test. That was why I was trying to apply artificial
memory pressure, something I am going to try and refine in future. I guess
we will have to look at the games for scenarios that thrash the aperture.

> I'm still crunching the numbers, but preliminary benchmarks on my i855
> show that there are _no_ regressions in cairo-traces (poppler is the only
> one to take a hit of 1% which is decently below it's noise floor of 2%;).
> Speedups are comparable to what you've posted on the list for your patches

Excellent!

-- 
Chris Wilson, Intel Open Source Technology Centre

Re: [PATCH 0/9] [RFC] fair-lru eviction

[Thomas Hellström]

Daniel,

Daniel Vetter wrote:
> Hi all,
>
> This patch series implements the fair-lru eviction Chris Wilson already
> posted with a twist. It's essentially the same idea & algorithm.
> Differnences versus his patch:
> - Doesn't do any allocations while scanning.
> - Implemented in drm_mm.c
>
> In other words, this should also be usable by ttm. The idea is simple:
> Scan through the lru, marking objects as evictable until there is a
> large area of memory free/free-able. Then walk through all the scanned
> objects in reverse, checking which ones fall into this hole. Finally
> evicting them.
>
> Comments, ideas highly welcome.
>
> As per usual, I couldn't resist and had to clean up the code in drm_mm.c a
> little.
>
> Yours, Daniel
>
>   

While the cleanup of drm_mm.c looks fine to me, I'm not sure the fair 
eviction is easy to implement with TTM.

TTM releases the spinlock protecting the drm_mm manager in between 
evictions to be able to wait (without holding locks) for bo idle. That 
means that the lru list may have changed between the first eviction and 
the next. In practice, drivers either don't allow simultaneous bo 
validation or should disallow it if thrashing is likely to occur, so the 
likelyhood of the lru list changing in between evictions should be small 
but it needs to be taken into account.

Nevertheless, the drm_mm.c cleanup is
Acked-by: Thomas Hellstrom <thellstrom@vmwgfx.com>

I'll leave it to the Intel guys to comment on the fair eviction stuff.

/Thomas



> Daniel Vetter (9):
>   list.h: add list_for_each_entry_safe_from_reverse
>   drm: use list_for_each_entry in drm_mm.c
>   drm: kill drm_mm_node->private
>   drm: kill dead code in drm_mm.c
>   drm: sane naming for drm_mm.c
>   drm_mm: extract check_free_mm_node
>   drm: implement helper functions for scanning lru list
>   drm/i915: prepare for fair lru eviction
>   drm/i915: implement fair lru eviction
>
>  drivers/gpu/drm/drm_mm.c          |  359 ++++++++++++++++++++++++-------------
>  drivers/gpu/drm/i915/i915_gem.c   |  122 ++++++++-----
>  drivers/gpu/drm/ttm/ttm_bo.c      |    6 -
>  drivers/gpu/drm/ttm/ttm_bo_util.c |    2 -
>  include/drm/drm_mm.h              |   27 +++-
>  include/linux/list.h              |   15 ++
>  6 files changed, 347 insertions(+), 184 deletions(-)
>
> _______________________________________________
> dri-devel mailing list
> dri-devel@lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/dri-devel
>   

Re: [PATCH 0/9] [RFC] fair-lru eviction

[Daniel Vetter]

On Wed, May 19, 2010 at 09:51:33PM +0200, Thomas Hellström wrote:
> Daniel,
> TTM releases the spinlock protecting the drm_mm manager in between
> evictions to be able to wait (without holding locks) for bo idle.
> That means that the lru list may have changed between the first
> eviction and the next. In practice, drivers either don't allow
> simultaneous bo validation or should disallow it if thrashing is
> likely to occur, so the likelyhood of the lru list changing in
> between evictions should be small but it needs to be taken into
> account.

Well, in my opinion ttm locking optimize for the wrong case: Usually there
should be a little bit of room free to fully pipeline everything. And if
it there is no room free anymore, performance is gonna dip anyway, so we
might as well block. I think the linux vm with the split between
asynchronous background writeback and synchronous writeback in case of low
amounts of free memory could be used as inspiration.

Whatever, I think ttm could use this fair eviction stuff even with the
current locking scheme: Do all the accounting under the spinlock, i.e.
- scanning the lru
- building up the eviction list
- mark the memory blocks as free (with drm_mm_put_block)
- reserve the complete free hole (needs a new function in drm_mm, but
  range-restricted allocations are not yet implemented yet, anyway) with a
  temporary object.

Then do the effective eviction outside the spinlock. iirc ttm already uses
such shadow (dunno what they're really called) objects for buffer moves.

> Nevertheless, the drm_mm.c cleanup is
> Acked-by: Thomas Hellstrom <thellstrom@vmwgfx.com>

Does that include the drm_mm_node->private pointer removal? Jerome naked
that one (but I've objected). Just to clarify.

> I'll leave it to the Intel guys to comment on the fair eviction stuff.
> 
> /Thomas

Thanks, Daniel
-- 
Daniel Vetter
Mail: daniel@ffwll.ch
Mobile: +41 (0)79 365 57 48

Re: [PATCH 0/9] [RFC] fair-lru eviction

[Thomas Hellstrom]

On 05/19/2010 10:13 PM, Daniel Vetter wrote:
> On Wed, May 19, 2010 at 09:51:33PM +0200, Thomas Hellström wrote:
>    
>> Daniel,
>> TTM releases the spinlock protecting the drm_mm manager in between
>> evictions to be able to wait (without holding locks) for bo idle.
>> That means that the lru list may have changed between the first
>> eviction and the next. In practice, drivers either don't allow
>> simultaneous bo validation or should disallow it if thrashing is
>> likely to occur, so the likelyhood of the lru list changing in
>> between evictions should be small but it needs to be taken into
>> account.
>>      
> Well, in my opinion ttm locking optimize for the wrong case: Usually there
> should be a little bit of room free to fully pipeline everything. And if
> it there is no room free anymore, performance is gonna dip anyway, so we
> might as well block.

Yes, the driver is free to block in such cases if it wants to. It's a 
matter of taking a command submission rwsem in either read- or write 
mode. However, a validation sequence of one DRI client shouldn't 
unnecessarily block other renderers whose render targets  / sources are 
already in memory, but that's only a special case. TTM tries to make 
sure and encourage driver writers make sure no CPU locks are held while 
waiting for a GPU, which may turn out to be optimizing for the wrong 
case in a single-client-single-gpu environment, but turn out to be a 
good choice in other situations.

In any case, the code must take into account that the lru may be 
modified when the spinlock is released, which I believe you have 
addressed below.

>   I think the linux vm with the split between
> asynchronous background writeback and synchronous writeback in case of low
> amounts of free memory could be used as inspiration.
>
> Whatever, I think ttm could use this fair eviction stuff even with the
> current locking scheme: Do all the accounting under the spinlock, i.e.
> - scanning the lru
> - building up the eviction list
> - mark the memory blocks as free (with drm_mm_put_block)
> - reserve the complete free hole (needs a new function in drm_mm, but
>    range-restricted allocations are not yet implemented yet, anyway) with a
>    temporary object.
>
> Then do the effective eviction outside the spinlock. iirc ttm already uses
> such shadow (dunno what they're really called) objects for buffer moves.
>
>    
>> Nevertheless, the drm_mm.c cleanup is
>> Acked-by: Thomas Hellstrom<thellstrom@vmwgfx.com>
>>      
> Does that include the drm_mm_node->private pointer removal? Jerome naked
> that one (but I've objected). Just to clarify.
>
>    

IIRC, Jerome's range validation patches was using that member at some 
stage. I think if Jerome needs the pointer it should stay.

Thanks,
Thomas


>> I'll leave it to the Intel guys to comment on the fair eviction stuff.
>>
>> /Thomas
>>      
> Thanks, Daniel
>