[PATCH] [RFC] drm/i915: Restore LRU evict order, with a twist!

[Chris Wilson <chris@chris-wilson.co.uk>]

When we need to clear some space in the GTT in order to pin a new
buffer, scan through the inactive list amalgamating objects in LRU order
until we find a large enough contiguous space to fit the new buffer.

...
This is benchmarking much better than the current scan through for a
single buffer large enough to fit.
...

Cc: Daniel Vetter <daniel.vetter@ffwll.ch>
---
 drivers/gpu/drm/i915/i915_gem.c |  516 +++++++++++++++++++++++++++------------
 1 files changed, 360 insertions(+), 156 deletions(-)

diff --git a/drivers/gpu/drm/i915/i915_gem.c b/drivers/gpu/drm/i915/i915_gem.c
index 253ca3a..fccd595 100644
--- a/drivers/gpu/drm/i915/i915_gem.c
+++ b/drivers/gpu/drm/i915/i915_gem.c
@@ -50,8 +50,7 @@ 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_from_inactive_list(struct drm_device *dev);
+static int i915_gem_evict_something(struct drm_device *dev, int size, unsigned align);
 static int i915_gem_phys_pwrite(struct drm_device *dev, struct drm_gem_object *obj,
 				struct drm_i915_gem_pwrite *args,
 				struct drm_file *file_priv);
@@ -320,6 +319,42 @@ fail_unlock:
 	return ret;
 }
 
+/**
+ * i915_gem_get_gtt_alignment - return required GTT alignment for an object
+ * @obj: object to check
+ *
+ * Return the required GTT alignment for an object, taking into account
+ * potential fence register mapping if needed.
+ */
+static uint32_t
+i915_gem_get_fence_alignment(struct drm_gem_object *obj)
+{
+	struct drm_device *dev = obj->dev;
+	struct drm_i915_gem_object *obj_priv = to_intel_bo(obj);
+	int start, i;
+
+	/*
+	 * Minimum alignment is 4k (GTT page size), but might be greater
+	 * if a fence register is needed for the object.
+	 */
+	if (IS_I965G(dev) || obj_priv->tiling_mode == I915_TILING_NONE)
+		return 4096;
+
+	/*
+	 * Previous chips need to be aligned to the size of the smallest
+	 * fence register that can contain the object.
+	 */
+	if (IS_I9XX(dev))
+		start = 1024*1024;
+	else
+		start = 512*1024;
+
+	for (i = start; i < obj->size; i <<= 1)
+		;
+
+	return i;
+}
+
 static int
 i915_gem_object_get_pages_or_evict(struct drm_gem_object *obj)
 {
@@ -333,7 +368,9 @@ 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,
+					       i915_gem_get_fence_alignment(obj));
 		if (ret)
 			return ret;
 
@@ -1336,42 +1373,6 @@ i915_gem_free_mmap_offset(struct drm_gem_object *obj)
 }
 
 /**
- * i915_gem_get_gtt_alignment - return required GTT alignment for an object
- * @obj: object to check
- *
- * Return the required GTT alignment for an object, taking into account
- * potential fence register mapping if needed.
- */
-static uint32_t
-i915_gem_get_fence_alignment(struct drm_gem_object *obj)
-{
-	struct drm_device *dev = obj->dev;
-	struct drm_i915_gem_object *obj_priv = to_intel_bo(obj);
-	int start, i;
-
-	/*
-	 * Minimum alignment is 4k (GTT page size), but might be greater
-	 * if a fence register is needed for the object.
-	 */
-	if (IS_I965G(dev) || obj_priv->tiling_mode == I915_TILING_NONE)
-		return 4096;
-
-	/*
-	 * Previous chips need to be aligned to the size of the smallest
-	 * fence register that can contain the object.
-	 */
-	if (IS_I9XX(dev))
-		start = 1024*1024;
-	else
-		start = 512*1024;
-
-	for (i = start; i < obj->size; i <<= 1)
-		;
-
-	return i;
-}
-
-/**
  * i915_gem_mmap_gtt_ioctl - prepare an object for GTT mmap'ing
  * @dev: DRM device
  * @data: GTT mapping ioctl data
@@ -2103,33 +2104,6 @@ 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)
-{
-	drm_i915_private_t *dev_priv = dev->dev_private;
-	struct drm_i915_gem_object *obj_priv;
-	struct drm_gem_object *best = NULL;
-	struct drm_gem_object *first = NULL;
-
-	/* 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->obj;
-		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)
-					return best;
-			}
-			if (!first)
-			    first = obj;
-		}
-	}
-
-	return best ? best : first;
-}
-
 static int
 i915_gpu_idle(struct drm_device *dev)
 {
@@ -2155,6 +2129,29 @@ i915_gpu_idle(struct drm_device *dev)
 }
 
 static int
+i915_gem_evict_from_inactive_list(struct drm_device *dev)
+{
+	drm_i915_private_t *dev_priv = dev->dev_private;
+
+	while (!list_empty(&dev_priv->mm.inactive_list)) {
+		struct drm_gem_object *obj;
+		int ret;
+
+		obj = list_first_entry(&dev_priv->mm.inactive_list,
+				       struct drm_i915_gem_object,
+				       list)->obj;
+
+		ret = i915_gem_object_unbind(obj);
+		if (ret != 0) {
+			DRM_ERROR("Error unbinding object: %d\n", ret);
+			return ret;
+		}
+	}
+
+	return 0;
+}
+
+static int
 i915_gem_evict_everything(struct drm_device *dev)
 {
 	drm_i915_private_t *dev_priv = dev->dev_private;
@@ -2191,91 +2188,322 @@ i915_gem_evict_everything(struct drm_device *dev)
 	return 0;
 }
 
+struct i915_gem_eviction_entry {
+	struct list_head link;
+	unsigned long start, end, size;
+	struct i915_gem_eviction_objects {
+		struct drm_gem_object *obj[16];
+		unsigned num_obj;
+		struct list_head link;
+	} objects;
+};
+
+struct i915_gem_eviction_roster {
+	struct list_head list;
+};
+
+static void
+i915_gem_eviction_entry_free(struct i915_gem_eviction_entry *entry)
+{
+	while(!list_empty(&entry->objects.link)) {
+		struct i915_gem_eviction_objects *objects;
+
+		objects = list_first_entry(&entry->objects.link,
+					   struct i915_gem_eviction_objects,
+					   link);
+
+		list_del(&objects->link);
+		kfree(objects);
+	}
+
+	list_del(&entry->link);
+	kfree(entry);
+}
+
+static void
+i915_gem_eviction_roster_fini(struct i915_gem_eviction_roster *roster)
+{
+	while(!list_empty(&roster->list)) {
+		struct i915_gem_eviction_entry *entry;
+
+		entry = list_first_entry(&roster->list,
+					 struct i915_gem_eviction_entry,
+					 link);
+		i915_gem_eviction_entry_free(entry);
+	}
+}
+
 static int
-i915_gem_evict_something(struct drm_device *dev, int min_size)
+i915_gem_eviction_roster_init(struct drm_device *dev,
+			      struct i915_gem_eviction_roster *roster)
 {
 	drm_i915_private_t *dev_priv = dev->dev_private;
-	struct drm_gem_object *obj;
-	int ret;
+	struct drm_mm_node *mm;
 
-	for (;;) {
-		i915_gem_retire_requests(dev);
+	INIT_LIST_HEAD(&roster->list);
 
-		/* 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;
+	list_for_each_entry(mm, &dev_priv->mm.gtt_space.fl_entry, fl_entry) {
+		struct i915_gem_eviction_entry *entry;
 
-#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);
+		entry = kmalloc(sizeof (*entry), GFP_KERNEL);
+		if (entry == NULL)
+			return -ENOMEM;
+
+		entry->start = mm->start;
+		entry->end = mm->start + mm->size;
+		entry->size = mm->size;
+		entry->objects.num_obj = 0;
+		INIT_LIST_HEAD(&entry->objects.link);
+
+		list_add(&entry->link, &roster->list);
+	}
+
+	return 0;
+}
 
-			/* Wait on the rendering and unbind the buffer. */
-			return i915_gem_object_unbind(obj);
+static int
+i915_gem_eviction_entry_add(struct i915_gem_eviction_entry *entry,
+			     struct drm_gem_object *obj)
+{
+	struct i915_gem_eviction_objects *objects;
+
+	if (list_empty(&entry->objects.link)) {
+		objects = &entry->objects;
+	} else {
+		objects = list_first_entry(&entry->objects.link,
+					   struct i915_gem_eviction_objects,
+					   link);
+	}
+	if (objects->num_obj == ARRAY_SIZE(objects->obj)) {
+		objects = kmalloc (sizeof (*objects), GFP_KERNEL);
+		if (objects == NULL)
+			return -ENOMEM;
+
+		objects->num_obj = 0;
+		list_add(&objects->link, &entry->objects.link);
+	}
+
+	objects->obj[objects->num_obj++] = obj;
+	return 0;
+}
+
+static int
+i915_gem_eviction_roster_add(struct i915_gem_eviction_roster *roster,
+			     struct drm_gem_object *obj)
+{
+	struct drm_i915_gem_object *obj_priv = obj->driver_private;
+	struct i915_gem_eviction_entry *before, *after, *entry = NULL;
+	long start = obj_priv->gtt_offset;
+	long end = start + obj->size;
+	int i, ret;
+
+	list_for_each_entry(before, &roster->list, link) {
+		if (before->end == start) {
+			i915_gem_eviction_entry_add(before, obj);
+			entry = before;
+			entry->end = end;
+			break;
 		}
+	}
 
-		/* If we didn't get anything, but the ring is still processing
-		 * things, wait for the next to finish and hopefully leave us
-		 * a buffer to evict.
-		 */
-		if (!list_empty(&dev_priv->mm.request_list)) {
-			struct drm_i915_gem_request *request;
+	list_for_each_entry(after, &roster->list, link) {
+		if (after->start == end) {
+			if (entry) {
+				struct i915_gem_eviction_objects *objects;
 
-			request = list_first_entry(&dev_priv->mm.request_list,
-						   struct drm_i915_gem_request,
-						   list);
+				entry->end = after->end;
+				for (i = 0; i < after->objects.num_obj; i++) {
+					ret = i915_gem_eviction_entry_add(entry, obj);
+					if (ret)
+						return ret;
+				}
 
-			ret = i915_wait_request(dev, request->seqno);
-			if (ret)
-				return ret;
+				list_for_each_entry(objects, &after->objects.link, link) {
+					for (i = 0; i < objects->num_obj; i++) {
+						ret = i915_gem_eviction_entry_add(entry, obj);
+						if (ret)
+							return ret;
+					}
+				}
+				i915_gem_eviction_entry_free(entry);
+			} else {
+				ret = i915_gem_eviction_entry_add(after, obj);
+				if (ret)
+					return ret;
 
+				entry = after;
+				entry->start = start;
+			}
+			entry->size = entry->end - entry->start;
+			break;
+		}
+	}
+
+	if (entry == NULL) {
+		entry = kmalloc(sizeof (*entry), GFP_KERNEL);
+		if (entry == NULL)
+			return -ENOMEM;
+
+		entry->start = start;
+		entry->end = end;
+		entry->size = obj->size;
+		entry->objects.num_obj = 0;
+		INIT_LIST_HEAD(&entry->objects.link);
+
+		list_add(&entry->link, &roster->list);
+
+		ret = i915_gem_eviction_entry_add(entry, obj);
+		if (ret)
+			return ret;
+	}
+
+	return 0;
+}
+
+static struct i915_gem_eviction_entry *
+i915_gem_eviction_roster_search(struct i915_gem_eviction_roster *roster,
+				unsigned long size,
+				unsigned align)
+{
+	struct i915_gem_eviction_entry *entry;
+
+	list_for_each_entry(entry, &roster->list, link) {
+		unsigned wasted = 0;
+
+		if (entry->size < size)
 			continue;
+
+		if (align) {
+			unsigned tmp = entry->start & (align - 1);
+			if (tmp)
+				wasted += align - tmp;
 		}
 
-		/* If we didn't have anything on the request list but there
-		 * are buffers awaiting a flush, emit one and try again.
-		 * When we wait on it, those buffers waiting for that flush
-		 * will get moved to inactive.
-		 */
-		if (!list_empty(&dev_priv->mm.flushing_list)) {
-			struct drm_i915_gem_object *obj_priv;
+		if (entry->size >= size + wasted)
+			return entry;
+	}
 
-			/* Find an object that we can immediately reuse */
-			list_for_each_entry(obj_priv, &dev_priv->mm.flushing_list, list) {
-				obj = obj_priv->obj;
-				if (obj->size >= min_size)
-					break;
+	return NULL;
+}
 
-				obj = NULL;
-			}
+static int
+i915_gem_eviction_entry_evict(struct i915_gem_eviction_entry *entry)
+{
+	struct i915_gem_eviction_objects *objects;
+	int i, ret;
 
-			if (obj != NULL) {
-				uint32_t seqno;
+	for (i = 0; i < entry->objects.num_obj; i++) {
+		ret = i915_gem_object_unbind(entry->objects.obj[i]);
+		if (ret)
+			return ret;
+	}
 
-				i915_gem_flush(dev,
-					       obj->write_domain,
-					       obj->write_domain);
-				seqno = i915_add_request(dev, NULL, obj->write_domain);
-				if (seqno == 0)
-					return -ENOMEM;
-				continue;
-			}
+	list_for_each_entry(objects, &entry->objects.link, link) {
+		for (i = 0; i < objects->num_obj; i++) {
+			ret = i915_gem_object_unbind(objects->obj[i]);
+			if (ret)
+				return ret;
 		}
+	}
 
-		/* If we didn't do any of the above, there's no single buffer
-		 * large enough to swap out for the new one, so just evict
-		 * everything and start again. (This should be rare.)
-		 */
-		if (!list_empty (&dev_priv->mm.inactive_list))
-			return i915_gem_evict_from_inactive_list(dev);
-		else
-			return i915_gem_evict_everything(dev);
+	return 0;
+}
+
+static int
+i915_gem_evict_inactive_space(struct drm_device *dev, int size, unsigned align)
+{
+	drm_i915_private_t *dev_priv = dev->dev_private;
+	struct i915_gem_eviction_roster roster;
+	struct i915_gem_eviction_entry *entry;
+	struct drm_i915_gem_object *obj;
+	int ret;
+
+	/* re-check for free space after retiring requests */
+	if (drm_mm_search_free(&dev_priv->mm.gtt_space,
+			       size, align, 0))
+		return 0;
+
+	/* Build an eviction roster, and find the oldest objects that
+	 * could be evicted to free enough space for this request.
+	 */
+	ret = i915_gem_eviction_roster_init(dev, &roster);
+	if (ret)
+		goto err;
+
+	BUG_ON(i915_gem_eviction_roster_search(&roster, size, align));
+
+	list_for_each_entry(obj, &dev_priv->mm.inactive_list, list) {
+		ret = i915_gem_eviction_roster_add(&roster, obj->obj);
+		if (ret)
+			goto err;
+
+		entry = i915_gem_eviction_roster_search(&roster, size, align);
+		if (entry) {
+			ret = i915_gem_eviction_entry_evict(entry);
+			break;
+		}
 	}
+
+	ret = -ENOSPC;
+err:
+	i915_gem_eviction_roster_fini(&roster);
+	return ret;
+}
+
+static int
+i915_gem_evict_something(struct drm_device *dev, int size, unsigned align)
+{
+	drm_i915_private_t *dev_priv = dev->dev_private;
+	int ret;
+
+	i915_gem_retire_requests(dev);
+
+	/* If there's an inactive buffer available now, grab it
+	 * and be done.
+	 */
+	if (!list_empty(&dev_priv->mm.inactive_list)) {
+		ret = i915_gem_evict_inactive_space(dev, size, align);
+		if (ret != -ENOSPC)
+			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
+	 * a buffer to evict.
+	 */
+	if (!list_empty(&dev_priv->mm.request_list)) {
+		struct drm_i915_gem_request *request;
+
+		request = list_first_entry(&dev_priv->mm.request_list,
+					   struct drm_i915_gem_request,
+					   list);
+
+		return i915_wait_request(dev, request->seqno);
+	}
+
+	/* If we didn't have anything on the request list but there
+	 * are buffers awaiting a flush, emit one and try again.
+	 * When we wait on it, those buffers waiting for that flush
+	 * will get moved to inactive.
+	 */
+	if (!list_empty(&dev_priv->mm.flushing_list)) {
+		uint32_t seqno;
+
+		i915_gem_flush(dev,
+			       I915_GEM_GPU_DOMAINS,
+			       I915_GEM_GPU_DOMAINS);
+		seqno = i915_add_request(dev, NULL, I915_GEM_GPU_DOMAINS);
+		if (seqno == 0)
+			return -ENOMEM;
+
+		return i915_wait_request(dev, seqno);
+	}
+
+	/* If we didn't do any of the above, there's no single buffer
+	 * large enough to swap out for the new one, so just evict
+	 * everything and start again. (This should be rare.)
+	 */
+	return i915_gem_evict_everything(dev);
 }
 
 int
@@ -2707,7 +2935,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;
 
@@ -2725,7 +2953,7 @@ 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) {
@@ -2755,7 +2983,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;
 
@@ -4632,30 +4860,6 @@ void i915_gem_free_object(struct drm_gem_object *obj)
 	kfree(obj->driver_private);
 }
 
-/** Unbinds all inactive objects. */
-static int
-i915_gem_evict_from_inactive_list(struct drm_device *dev)
-{
-	drm_i915_private_t *dev_priv = dev->dev_private;
-
-	while (!list_empty(&dev_priv->mm.inactive_list)) {
-		struct drm_gem_object *obj;
-		int ret;
-
-		obj = list_first_entry(&dev_priv->mm.inactive_list,
-				       struct drm_i915_gem_object,
-				       list)->obj;
-
-		ret = i915_gem_object_unbind(obj);
-		if (ret != 0) {
-			DRM_ERROR("Error unbinding object: %d\n", ret);
-			return ret;
-		}
-	}
-
-	return 0;
-}
-
 int
 i915_gem_idle(struct drm_device *dev)
 {
-- 
1.7.1