diff mbox

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

Message ID 1278003225-937-1-git-send-email-chris@chris-wilson.co.uk
State Deferred, archived
Headers show

Commit Message

Chris Wilson July 1, 2010, 4:53 p.m. UTC
None
diff mbox

Patch

diff --git a/drivers/gpu/drm/i915/Makefile b/drivers/gpu/drm/i915/Makefile
index da78f2c..384fd45 100644
--- a/drivers/gpu/drm/i915/Makefile
+++ b/drivers/gpu/drm/i915/Makefile
@@ -8,6 +8,7 @@  i915-y := i915_drv.o i915_dma.o i915_irq.o i915_mem.o \
           i915_suspend.o \
 	  i915_gem.o \
 	  i915_gem_debug.o \
+	  i915_gem_evict.o \
 	  i915_gem_tiling.o \
 	  i915_trace_points.o \
 	  intel_display.o \
diff --git a/drivers/gpu/drm/i915/i915_drv.h b/drivers/gpu/drm/i915/i915_drv.h
index 98e6980..339ce42 100644
--- a/drivers/gpu/drm/i915/i915_drv.h
+++ b/drivers/gpu/drm/i915/i915_drv.h
@@ -236,6 +236,7 @@  typedef struct drm_i915_private {
 	struct pci_dev *bridge_dev;
 	struct intel_ring_buffer render_ring;
 	struct intel_ring_buffer bsd_ring;
+	u32 next_seqno;
 
 	drm_dma_handle_t *status_page_dmah;
 	void *seqno_page;
@@ -966,6 +967,7 @@  void i915_gem_cleanup_ringbuffer(struct drm_device *dev);
 int i915_gem_do_init(struct drm_device *dev, unsigned long start,
 		     unsigned long end);
 int i915_gem_idle(struct drm_device *dev);
+int i915_gpu_idle(struct drm_device *dev);
 uint32_t i915_add_request(struct drm_device *dev,
 		struct drm_file *file_priv,
 		uint32_t flush_domains,
@@ -990,6 +992,11 @@  int i915_gem_object_flush_write_domain(struct drm_gem_object *obj);
 void i915_gem_shrinker_init(void);
 void i915_gem_shrinker_exit(void);
 
+/* i915_gem_eviction.c */
+int i915_gem_evict_from_inactive_list(struct drm_device *dev);
+int i915_gem_evict_something(struct drm_device *dev, int size, unsigned align);
+int i915_gem_evict_everything(struct drm_device *dev);
+
 /* i915_gem_tiling.c */
 void i915_gem_detect_bit_6_swizzle(struct drm_device *dev);
 void i915_gem_object_do_bit_17_swizzle(struct drm_gem_object *obj);
diff --git a/drivers/gpu/drm/i915/i915_gem.c b/drivers/gpu/drm/i915/i915_gem.c
index a6fbe3b..7d20901 100644
--- a/drivers/gpu/drm/i915/i915_gem.c
+++ b/drivers/gpu/drm/i915/i915_gem.c
@@ -48,8 +48,6 @@  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_phys_pwrite(struct drm_device *dev, struct drm_gem_object *obj,
 				struct drm_i915_gem_pwrite *args,
 				struct drm_file *file_priv);
@@ -300,6 +298,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)
 {
@@ -313,8 +347,10 @@  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);
-		if (ret)
+		ret = i915_gem_evict_something(dev,
+					       obj->size,
+					       i915_gem_get_fence_alignment(obj));
+		if (ret != -ENOSPC)
 			return ret;
 
 		ret = i915_gem_object_get_pages(obj, 0);
@@ -1308,42 +1344,6 @@  i915_gem_free_mmap_offset(struct drm_gem_object *obj)
 }
 
 /**
- * i915_gem_get_fence_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
@@ -1866,19 +1866,6 @@  i915_gem_flush(struct drm_device *dev,
 				flush_domains);
 }
 
-static void
-i915_gem_flush_ring(struct drm_device *dev,
-	       uint32_t invalidate_domains,
-	       uint32_t flush_domains,
-	       struct intel_ring_buffer *ring)
-{
-	if (flush_domains & I915_GEM_DOMAIN_CPU)
-		drm_agp_chipset_flush(dev);
-	ring->flush(dev, ring,
-			invalidate_domains,
-			flush_domains);
-}
-
 /**
  * Ensures that all rendering to the object has completed and the object is
  * safe to unbind from the GTT or access from the CPU.
@@ -1988,34 +1975,7 @@  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->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)
-					return best;
-			}
-			if (!first)
-			    first = obj;
-		}
-	}
-
-	return best ? best : first;
-}
-
-static int
+int
 i915_gpu_idle(struct drm_device *dev)
 {
 	drm_i915_private_t *dev_priv = dev->dev_private;
@@ -2056,158 +2016,6 @@  i915_gpu_idle(struct drm_device *dev)
 	return ret;
 }
 
-static int
-i915_gem_evict_everything(struct drm_device *dev)
-{
-	drm_i915_private_t *dev_priv = dev->dev_private;
-	int ret;
-	bool lists_empty;
-
-	spin_lock(&dev_priv->mm.active_list_lock);
-	lists_empty = (list_empty(&dev_priv->mm.inactive_list) &&
-		       list_empty(&dev_priv->mm.flushing_list) &&
-		       list_empty(&dev_priv->render_ring.active_list) &&
-		       (!HAS_BSD(dev)
-			|| list_empty(&dev_priv->bsd_ring.active_list)));
-	spin_unlock(&dev_priv->mm.active_list_lock);
-
-	if (lists_empty)
-		return -ENOSPC;
-
-	/* Flush everything (on to the inactive lists) and evict */
-	ret = i915_gpu_idle(dev);
-	if (ret)
-		return ret;
-
-	BUG_ON(!list_empty(&dev_priv->mm.flushing_list));
-
-	ret = i915_gem_evict_from_inactive_list(dev);
-	if (ret)
-		return ret;
-
-	spin_lock(&dev_priv->mm.active_list_lock);
-	lists_empty = (list_empty(&dev_priv->mm.inactive_list) &&
-		       list_empty(&dev_priv->mm.flushing_list) &&
-		       list_empty(&dev_priv->render_ring.active_list) &&
-		       (!HAS_BSD(dev)
-			|| list_empty(&dev_priv->bsd_ring.active_list)));
-	spin_unlock(&dev_priv->mm.active_list_lock);
-	BUG_ON(!lists_empty);
-
-	return 0;
-}
-
-static int
-i915_gem_evict_something(struct drm_device *dev, int min_size)
-{
-	drm_i915_private_t *dev_priv = dev->dev_private;
-	struct drm_gem_object *obj;
-	int ret;
-
-	struct intel_ring_buffer *render_ring = &dev_priv->render_ring;
-	struct intel_ring_buffer *bsd_ring = &dev_priv->bsd_ring;
-	for (;;) {
-		i915_gem_retire_requests(dev, render_ring);
-
-		if (HAS_BSD(dev))
-			i915_gem_retire_requests(dev, bsd_ring);
-
-		/* 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);
-		}
-
-		/* 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(&render_ring->request_list)) {
-			struct drm_i915_gem_request *request;
-
-			request = list_first_entry(&render_ring->request_list,
-						   struct drm_i915_gem_request,
-						   list);
-
-			ret = i915_wait_request(dev,
-					request->seqno, request->ring);
-			if (ret)
-				return ret;
-
-			continue;
-		}
-
-		if (HAS_BSD(dev) && !list_empty(&bsd_ring->request_list)) {
-			struct drm_i915_gem_request *request;
-
-			request = list_first_entry(&bsd_ring->request_list,
-						   struct drm_i915_gem_request,
-						   list);
-
-			ret = i915_wait_request(dev,
-					request->seqno, request->ring);
-			if (ret)
-				return ret;
-
-			continue;
-		}
-
-		/* 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;
-
-			/* Find an object that we can immediately reuse */
-			list_for_each_entry(obj_priv, &dev_priv->mm.flushing_list, list) {
-				obj = &obj_priv->base;
-				if (obj->size >= min_size)
-					break;
-
-				obj = NULL;
-			}
-
-			if (obj != NULL) {
-				uint32_t seqno;
-
-				i915_gem_flush_ring(dev,
-					       obj->write_domain,
-					       obj->write_domain,
-					       obj_priv->ring);
-				seqno = i915_add_request(dev, NULL,
-						obj->write_domain,
-						obj_priv->ring);
-				if (seqno == 0)
-					return -ENOMEM;
-				continue;
-			}
-		}
-
-		/* 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);
-	}
-}
-
 int
 i915_gem_object_get_pages(struct drm_gem_object *obj,
 			  gfp_t gfpmask)
@@ -2640,28 +2448,25 @@  i915_gem_object_bind_to_gtt(struct drm_gem_object *obj, unsigned alignment)
  search_free:
 	free_space = drm_mm_search_free(&dev_priv->mm.gtt_space,
 					obj->size, alignment, 0);
-	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;
-			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
-		 * fitting our object in, we're out of memory.
-		 */
+	if (free_space == NULL) {
 #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;
 
 		goto search_free;
 	}
 
+	obj_priv->gtt_space = drm_mm_get_block(free_space, obj->size,
+					       alignment);
+	if (obj_priv->gtt_space == NULL)
+		return -ENOMEM;
+
+	obj_priv->gtt_space->private = obj;
+	obj_priv->gtt_offset = obj_priv->gtt_space->start;
+
 #if WATCH_BUF
 	DRM_INFO("Binding object of size %zd at 0x%08x\n",
 		 obj->size, obj_priv->gtt_offset);
@@ -2673,8 +2478,11 @@  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);
-			if (ret) {
+			ret = i915_gem_evict_something(dev, obj->size, alignment);
+			if (ret == 0)
+				goto search_free;
+
+			if (ret == -ENOSPC) {
 				/* now try to shrink everyone else */
 				if (gfpmask) {
 					gfpmask = 0;
@@ -2687,7 +2495,7 @@  i915_gem_object_bind_to_gtt(struct drm_gem_object *obj, unsigned alignment)
 			goto search_free;
 		}
 
-		return ret;
+		return -ENOMEM;
 	}
 
 	/* Create an AGP memory structure pointing at our pages, and bind it
@@ -2703,11 +2511,19 @@  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);
-		if (ret)
-			return ret;
+		ret = i915_gem_evict_something(dev, obj->size, alignment);
+		if (ret == 0)
+			goto search_free;
 
-		goto search_free;
+		if (ret == -ENOSPC) {
+			/* now try to shrink everyone else */
+			if (gfpmask) {
+				gfpmask = 0;
+				goto search_free;
+			}
+		}
+
+		return -ENOMEM;
 	}
 	atomic_inc(&dev->gtt_count);
 	atomic_add(obj->size, &dev->gtt_memory);
@@ -3866,7 +3682,7 @@  i915_gem_do_execbuffer(struct drm_device *dev, void *data,
 
 		/* evict everyone we can from the aperture */
 		ret = i915_gem_evict_everything(dev);
-		if (ret && ret != -ENOSPC)
+		if (ret)
 			goto err;
 	}
 
@@ -4522,30 +4338,6 @@  void i915_gem_free_object(struct drm_gem_object *obj)
 	kfree(obj_priv);
 }
 
-/** 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)->base;
-
-		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)
 {
@@ -4686,7 +4478,11 @@  i915_gem_init_ringbuffer(struct drm_device *dev)
 		ret = intel_init_ring_buffer(dev, &dev_priv->bsd_ring);
 		if (ret)
 			goto cleanup_render_ring;
+	} else {
+		INIT_LIST_HEAD(&dev_priv->bsd_ring.active_list);
+		INIT_LIST_HEAD(&dev_priv->bsd_ring.request_list);
 	}
+	dev_priv->next_seqno = 1;
 
 	return 0;
 
diff --git a/drivers/gpu/drm/i915/i915_gem_evict.c b/drivers/gpu/drm/i915/i915_gem_evict.c
new file mode 100644
index 0000000..d2e8f04
--- /dev/null
+++ b/drivers/gpu/drm/i915/i915_gem_evict.c
@@ -0,0 +1,489 @@ 
+/*
+ * Copyright © 2008-2010 Intel Corporation
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ *
+ * Authors:
+ *    Eric Anholt <eric@anholt.net>
+ *    Chris Wilson <chris@chris-wilson.co.uk>
+ *
+ */
+
+#include "drmP.h"
+#include "drm.h"
+#include "i915_drm.h"
+#include "i915_drv.h"
+
+struct i915_gem_eviction_entry {
+	struct list_head link;
+	unsigned long start, end, size;
+	struct i915_gem_eviction_objects {
+		struct drm_i915_gem_object *obj_priv[16];
+		unsigned num_obj;
+		struct list_head link;
+	} objects;
+};
+
+struct i915_gem_eviction_roster {
+	struct list_head list;
+	struct list_head objects_free_list;
+};
+
+static void
+i915_gem_eviction_roster_entry_free(struct i915_gem_eviction_roster *roster,
+				    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_move(&objects->link, &roster->objects_free_list);
+	}
+
+	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_roster_entry_free(roster, entry);
+	}
+
+	while(!list_empty(&roster->objects_free_list)) {
+		struct i915_gem_eviction_objects *objects;
+
+		objects = list_first_entry(&roster->objects_free_list,
+					   struct i915_gem_eviction_objects,
+					   link);
+
+		list_del(&objects->link);
+		kfree(objects);
+	}
+}
+
+static int
+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_mm_node *mm;
+
+	INIT_LIST_HEAD(&roster->list);
+	INIT_LIST_HEAD(&roster->objects_free_list);
+
+	list_for_each_entry(mm, &dev_priv->mm.gtt_space.fl_entry, fl_entry) {
+		struct i915_gem_eviction_entry *entry;
+
+		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;
+}
+
+static int
+i915_gem_eviction_roster_entry_add(struct i915_gem_eviction_roster *roster,
+				   struct i915_gem_eviction_entry *entry,
+				   struct drm_i915_gem_object *obj_priv)
+{
+	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_priv)) {
+		if (list_empty (&roster->objects_free_list)) {
+			objects = kmalloc (sizeof (*objects), GFP_KERNEL);
+			if (objects == NULL)
+				return -ENOMEM;
+		} else {
+			struct i915_gem_eviction_objects *objects;
+
+			objects = list_first_entry(&roster->objects_free_list,
+						   struct i915_gem_eviction_objects,
+						   link);
+
+			list_del(&objects->link);
+		}
+
+		objects->num_obj = 0;
+		list_add(&objects->link, &entry->objects.link);
+	}
+
+	objects->obj_priv[objects->num_obj++] = obj_priv;
+	return 0;
+}
+
+static int
+i915_gem_eviction_roster_add(struct i915_gem_eviction_roster *roster,
+			     struct drm_i915_gem_object *obj_priv)
+{
+	struct i915_gem_eviction_entry *before, *after, *entry = NULL;
+	long start = obj_priv->gtt_offset;
+	long end = start + obj_priv->base.size;
+	int i, ret;
+
+	list_for_each_entry(before, &roster->list, link) {
+		if (before->end == start) {
+			i915_gem_eviction_roster_entry_add(roster, before, obj_priv);
+			entry = before;
+			entry->end = end;
+			break;
+		}
+	}
+
+	list_for_each_entry(after, &roster->list, link) {
+		if (after->start == end) {
+			if (entry) {
+				struct i915_gem_eviction_objects *objects;
+
+				entry->end = after->end;
+				for (i = 0; i < after->objects.num_obj; i++) {
+					ret = i915_gem_eviction_roster_entry_add(roster, entry, obj_priv);
+					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_roster_entry_add(roster, entry, obj_priv);
+						if (ret)
+							return ret;
+					}
+				}
+				i915_gem_eviction_roster_entry_free(roster, entry);
+			} else {
+				ret = i915_gem_eviction_roster_entry_add(roster, after, obj_priv);
+				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_priv->base.size;
+		entry->objects.num_obj = 0;
+		INIT_LIST_HEAD(&entry->objects.link);
+
+		list_add(&entry->link, &roster->list);
+
+		ret = i915_gem_eviction_roster_entry_add(roster, entry, obj_priv);
+		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 (entry->size >= size + wasted)
+			return entry;
+	}
+
+	return NULL;
+}
+
+static int
+i915_gem_eviction_entry_evict(struct i915_gem_eviction_entry *entry)
+{
+	struct i915_gem_eviction_objects *objects;
+	int i, ret;
+
+	for (i = 0; i < entry->objects.num_obj; i++) {
+		ret = i915_gem_object_unbind(&entry->objects.obj_priv[i]->base);
+		if (ret)
+			return ret;
+	}
+
+	list_for_each_entry(objects, &entry->objects.link, link) {
+		for (i = 0; i < objects->num_obj; i++) {
+			ret = i915_gem_object_unbind(&objects->obj_priv[i]->base);
+			if (ret)
+				return ret;
+		}
+	}
+
+	return 0;
+}
+
+static struct drm_i915_gem_object *
+i915_gem_next_active_object(struct drm_device *dev,
+			    struct list_head **render_iter,
+			    struct list_head **bsd_iter)
+{
+	drm_i915_private_t *dev_priv = dev->dev_private;
+	struct drm_i915_gem_object *render_obj, *bsd_obj;
+
+	if (*render_iter != &dev_priv->render_ring.active_list)
+		render_obj = list_entry(*render_iter,
+					struct drm_i915_gem_object,
+					list);
+
+	if (HAS_BSD(dev)) {
+		if (*bsd_iter != &dev_priv->bsd_ring.active_list)
+			bsd_obj = list_entry(*bsd_iter,
+					     struct drm_i915_gem_object,
+					     list);
+
+		/* XXX can we handle seqno wrapping? */
+		if (render_obj->last_rendering_seqno < bsd_obj->last_rendering_seqno) {
+			*render_iter = (*render_iter)->next;
+			return render_obj;
+		} else {
+			*bsd_iter = (*bsd_iter)->next;
+			return bsd_obj;
+		}
+	} else {
+		*render_iter = (*render_iter)->next;
+		return render_obj;
+	}
+}
+
+static int
+i915_gem_evict_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_priv;
+	struct list_head *render_iter, *bsd_iter;
+	int ret;
+
+	/* 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));
+
+	/* First search the objects that are ready to be evicted. */
+	list_for_each_entry(obj_priv, &dev_priv->mm.inactive_list, list) {
+		ret = i915_gem_eviction_roster_add(&roster, obj_priv);
+		if (ret)
+			goto err;
+
+		entry = i915_gem_eviction_roster_search(&roster, size, align);
+		if (entry)
+			goto done;
+	}
+
+	/* Now search through the soon-to-be-expired objects. */
+	render_iter = dev_priv->render_ring.active_list.next;
+	bsd_iter = dev_priv->bsd_ring.active_list.next;
+	while ((obj_priv = i915_gem_next_active_object(dev, &render_iter, &bsd_iter)) != NULL) {
+		/* Does the object require an outstanding flush? */
+		if (obj_priv->base.write_domain || obj_priv->pin_count)
+			continue;
+
+		ret = i915_gem_eviction_roster_add(&roster, obj_priv);
+		if (ret)
+			goto err;
+
+		entry = i915_gem_eviction_roster_search(&roster, size, align);
+		if (entry)
+			goto done;
+	}
+
+	/* Finally add anything with a pending flush (in order of retirement). */
+	list_for_each_entry(obj_priv, &dev_priv->mm.flushing_list, list) {
+		if (obj_priv->pin_count)
+			continue;
+
+		ret = i915_gem_eviction_roster_add(&roster, obj_priv);
+		if (ret)
+			goto err;
+
+		entry = i915_gem_eviction_roster_search(&roster, size, align);
+		if (entry)
+			goto done;
+	}
+	render_iter = dev_priv->render_ring.active_list.next;
+	bsd_iter = dev_priv->bsd_ring.active_list.next;
+	while ((obj_priv = i915_gem_next_active_object(dev, &render_iter, &bsd_iter)) != NULL) {
+		if (! obj_priv->base.write_domain || obj_priv->pin_count)
+			continue;
+
+		ret = i915_gem_eviction_roster_add(&roster, obj_priv);
+		if (ret)
+			goto err;
+
+		entry = i915_gem_eviction_roster_search(&roster, size, align);
+		if (entry)
+			goto done;
+	}
+
+	ret = -ENOSPC;
+	goto err;
+done:
+	ret = i915_gem_eviction_entry_evict(entry);
+err:
+	i915_gem_eviction_roster_fini(&roster);
+	return ret;
+}
+
+int
+i915_gem_evict_something(struct drm_device *dev, int size, unsigned align)
+{
+	drm_i915_private_t *dev_priv = dev->dev_private;
+	int ret;
+
+	spin_lock(&dev_priv->mm.active_list_lock);
+	ret = list_empty(&dev_priv->mm.inactive_list) &&
+	      list_empty(&dev_priv->mm.flushing_list) &&
+	      list_empty(&dev_priv->render_ring.active_list) &&
+	      list_empty(&dev_priv->bsd_ring.active_list);
+	spin_unlock(&dev_priv->mm.active_list_lock);
+
+	if (ret)
+		return -ENOSPC;
+
+	i915_gem_retire_requests(dev, &dev_priv->render_ring);
+	if (HAS_BSD(dev))
+		i915_gem_retire_requests(dev, &dev_priv->bsd_ring);
+
+	/* re-check for free space after retiring requests */
+	if (drm_mm_search_free(&dev_priv->mm.gtt_space,
+			       size, align, 0))
+		return 0;
+
+	ret = i915_gem_evict_space(dev, size, align);
+	if (ret != -ENOSPC)
+		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.)
+	 */
+	return i915_gem_evict_everything(dev);
+}
+
+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_i915_gem_object *obj_priv;
+		int ret;
+
+		obj_priv = list_first_entry(&dev_priv->mm.inactive_list,
+				       struct drm_i915_gem_object,
+				       list);
+
+		ret = i915_gem_object_unbind(&obj_priv->base);
+		if (ret)
+			return ret;
+	}
+
+	return 0;
+}
+
+int
+i915_gem_evict_everything(struct drm_device *dev)
+{
+	drm_i915_private_t *dev_priv = dev->dev_private;
+	int ret;
+	bool lists_empty;
+
+	spin_lock(&dev_priv->mm.active_list_lock);
+	lists_empty = (list_empty(&dev_priv->mm.inactive_list) &&
+		       list_empty(&dev_priv->mm.flushing_list) &&
+		       list_empty(&dev_priv->render_ring.active_list) &&
+		       list_empty(&dev_priv->bsd_ring.active_list));
+	spin_unlock(&dev_priv->mm.active_list_lock);
+
+	if (lists_empty)
+		return 0;
+
+	/* Flush everything (on to the inactive lists) and evict */
+	ret = i915_gpu_idle(dev);
+	if (ret)
+		return ret;
+
+	BUG_ON(!list_empty(&dev_priv->mm.flushing_list));
+
+	ret = i915_gem_evict_from_inactive_list(dev);
+	if (ret)
+		return ret;
+
+	spin_lock(&dev_priv->mm.active_list_lock);
+	lists_empty = (list_empty(&dev_priv->mm.inactive_list) &&
+		       list_empty(&dev_priv->mm.flushing_list) &&
+		       list_empty(&dev_priv->render_ring.active_list) &&
+		       list_empty(&dev_priv->bsd_ring.active_list));
+	spin_unlock(&dev_priv->mm.active_list_lock);
+	BUG_ON(!lists_empty);
+
+	return 0;
+}
diff --git a/drivers/gpu/drm/i915/intel_ringbuffer.c b/drivers/gpu/drm/i915/intel_ringbuffer.c
index 2a3d2fa..f15e174 100644
--- a/drivers/gpu/drm/i915/intel_ringbuffer.c
+++ b/drivers/gpu/drm/i915/intel_ringbuffer.c
@@ -39,12 +39,14 @@  render_ring_flush(struct drm_device *dev,
 		u32	invalidate_domains,
 		u32	flush_domains)
 {
+	drm_i915_private_t *dev_priv = dev->dev_private;
+
 #if WATCH_EXEC
 	DRM_INFO("%s: invalidate %08x flush %08x\n", __func__,
 		  invalidate_domains, flush_domains);
 #endif
 	u32 cmd;
-	trace_i915_gem_request_flush(dev, ring->next_seqno,
+	trace_i915_gem_request_flush(dev, dev_priv->next_seqno,
 				     invalidate_domains, flush_domains);
 
 	if ((invalidate_domains | flush_domains) & I915_GEM_GPU_DOMAINS) {
@@ -219,6 +221,20 @@  do {									\
 	OUT_RING(0);							\
 } while (0)
 
+static u32 i915_get_next_seqno(struct drm_device *dev)
+{
+	drm_i915_private_t *dev_priv = dev->dev_private;
+	u32 seqno;
+
+	seqno = dev_priv->next_seqno;
+
+	/* reserve 0 for non-seqno */
+	if (++dev_priv->next_seqno == 0)
+		dev_priv->next_seqno = 1;
+
+	return seqno;
+}
+
 /**
  * Creates a new sequence number, emitting a write of it to the status page
  * plus an interrupt, which will trigger i915_user_interrupt_handler.
@@ -233,9 +249,10 @@  render_ring_add_request(struct drm_device *dev,
 		struct drm_file *file_priv,
 		u32 flush_domains)
 {
-	u32 seqno;
 	drm_i915_private_t *dev_priv = dev->dev_private;
-	seqno = intel_ring_get_seqno(dev, ring);
+	u32 seqno;
+
+	seqno = i915_get_next_seqno(dev);
 
 	if (IS_GEN6(dev)) {
 		BEGIN_LP_RING(6);
@@ -405,7 +422,9 @@  bsd_ring_add_request(struct drm_device *dev,
 		u32 flush_domains)
 {
 	u32 seqno;
-	seqno = intel_ring_get_seqno(dev, ring);
+
+	seqno = i915_get_next_seqno(dev);
+
 	intel_ring_begin(dev, ring, 4);
 	intel_ring_emit(dev, ring, MI_STORE_DWORD_INDEX);
 	intel_ring_emit(dev, ring,
@@ -838,18 +857,6 @@  void intel_fill_struct(struct drm_device *dev,
 	intel_ring_advance(dev, ring);
 }
 
-u32 intel_ring_get_seqno(struct drm_device *dev,
-		struct intel_ring_buffer *ring)
-{
-	u32 seqno;
-	seqno = ring->next_seqno;
-
-	/* reserve 0 for non-seqno */
-	if (++ring->next_seqno == 0)
-		ring->next_seqno = 1;
-	return seqno;
-}
-
 struct intel_ring_buffer render_ring = {
 	.name			= "render ring",
 	.regs                   = {
@@ -867,7 +874,6 @@  struct intel_ring_buffer render_ring = {
 	.head			= 0,
 	.tail			= 0,
 	.space			= 0,
-	.next_seqno		= 1,
 	.user_irq_refcount	= 0,
 	.irq_gem_seqno		= 0,
 	.waiting_gem_seqno	= 0,
@@ -906,7 +912,6 @@  struct intel_ring_buffer bsd_ring = {
 	.head			= 0,
 	.tail			= 0,
 	.space			= 0,
-	.next_seqno		= 1,
 	.user_irq_refcount	= 0,
 	.irq_gem_seqno		= 0,
 	.waiting_gem_seqno	= 0,
diff --git a/drivers/gpu/drm/i915/intel_ringbuffer.h b/drivers/gpu/drm/i915/intel_ringbuffer.h
index ff5db57..d16ec36 100644
--- a/drivers/gpu/drm/i915/intel_ringbuffer.h
+++ b/drivers/gpu/drm/i915/intel_ringbuffer.h
@@ -128,9 +128,6 @@  void intel_fill_struct(struct drm_device *dev,
 void intel_ring_advance(struct drm_device *dev,
 		struct intel_ring_buffer *ring);
 
-u32 intel_ring_get_seqno(struct drm_device *dev,
-		struct intel_ring_buffer *ring);
-
 extern struct intel_ring_buffer render_ring;
 extern struct intel_ring_buffer bsd_ring;