diff --git a/drivers/gpu/drm/i915/i915_gem_gtt.c b/drivers/gpu/drm/i915/i915_gem_gtt.c
index 3ce9f83..82b72a1 100644
--- a/drivers/gpu/drm/i915/i915_gem_gtt.c
+++ b/drivers/gpu/drm/i915/i915_gem_gtt.c
@@ -424,8 +424,12 @@ static void unmap_and_free_pd(struct i915_page_directory_entry *pd,
 			       struct drm_device *dev)
 {
 	if (pd->page) {
+		WARN(!bitmap_empty(pd->used_pdes, GEN8_PDES_PER_PAGE),
+				"Free page directory with %d used pages\n",
+				bitmap_weight(pd->used_pdes, GEN8_PDES_PER_PAGE));
 		i915_dma_unmap_single(pd, dev);
 		__free_page(pd->page);
+		kfree(pd->used_pdes);
 		kfree(pd);
 	}
 }
@@ -433,26 +437,35 @@ static void unmap_and_free_pd(struct i915_page_directory_entry *pd,
 static struct i915_page_directory_entry *alloc_pd_single(struct drm_device *dev)
 {
 	struct i915_page_directory_entry *pd;
-	int ret;
+	int ret = -ENOMEM;
 
 	pd = kzalloc(sizeof(*pd), GFP_KERNEL);
 	if (!pd)
 		return ERR_PTR(-ENOMEM);
 
+	pd->used_pdes = kcalloc(BITS_TO_LONGS(GEN8_PDES_PER_PAGE),
+				sizeof(*pd->used_pdes), GFP_KERNEL);
+	if (!pd->used_pdes)
+		goto free_pd;
+
 	pd->page = alloc_page(GFP_KERNEL | __GFP_ZERO);
-	if (!pd->page) {
-		kfree(pd);
-		return ERR_PTR(-ENOMEM);
-	}
+	if (!pd->page)
+		goto free_bitmap;
 
 	ret = i915_dma_map_px_single(pd, dev);
-	if (ret) {
-		__free_page(pd->page);
-		kfree(pd);
-		return ERR_PTR(ret);
-	}
+	if (ret)
+		goto free_page;
 
 	return pd;
+
+free_page:
+	__free_page(pd->page);
+free_bitmap:
+	kfree(pd->used_pdes);
+free_pd:
+	kfree(pd);
+
+	return ERR_PTR(ret);
 }
 
 /* Broadwell Page Directory Pointer Descriptors */
@@ -634,36 +647,47 @@ static void gen8_teardown_va_range(struct i915_address_space *vm,
 	gen8_for_each_pdpe(pd, &ppgtt->pdp, start, length, temp, pdpe) {
 		uint64_t pd_len = gen8_clamp_pd(start, length);
 		uint64_t pd_start = start;
-		gen8_for_each_pde(pt, pd, pd_start, pd_len, temp, pde) {
-			unmap_and_free_pt(pt, vm->dev);
-			pd->page_tables[pde] = NULL;
-		}
-		unmap_and_free_pd(pd, vm->dev);
-		ppgtt->pdp.page_directory[pdpe] = NULL;
-	}
-}
 
-static void gen8_ppgtt_unmap_pages(struct i915_hw_ppgtt *ppgtt)
-{
-	struct pci_dev *hwdev = ppgtt->base.dev->pdev;
-	int i, j;
-
-	for (i = 0; i < GEN8_PDES_PER_PAGE; i++) {
-		/* TODO: In the future we'll support sparse mappings, so this
-		 * will have to change. */
-		if (!ppgtt->pdp.page_directory[i]->daddr)
+		/* Page directories might not be present since the macro rounds
+		 * down, and up.
+		 */
+		if (!pd) {
+			WARN(test_bit(pdpe, ppgtt->pdp.used_pdpes),
+			     "PDPE %d is not allocated, but is reserved (%p)\n",
+			     pdpe, vm);
 			continue;
+		} else {
+			WARN(!test_bit(pdpe, ppgtt->pdp.used_pdpes),
+			     "PDPE %d not reserved, but is allocated (%p)",
+			     pdpe, vm);
+		}
 
-		pci_unmap_page(hwdev, ppgtt->pdp.page_directory[i]->daddr, PAGE_SIZE,
-				PCI_DMA_BIDIRECTIONAL);
+		gen8_for_each_pde(pt, pd, pd_start, pd_len, temp, pde) {
+			if (!pt) {
+				WARN(test_bit(pde, pd->used_pdes),
+				     "PDE %d is not allocated, but is reserved (%p)\n",
+				     pde, vm);
+				continue;
+			} else
+				WARN(!test_bit(pde, pd->used_pdes),
+				     "PDE %d not reserved, but is allocated (%p)",
+				     pde, vm);
+
+			bitmap_clear(pt->used_ptes,
+				     gen8_pte_index(pd_start),
+				     gen8_pte_count(pd_start, pd_len));
+
+			if (bitmap_empty(pt->used_ptes, GEN8_PTES_PER_PAGE)) {
+				unmap_and_free_pt(pt, vm->dev);
+				pd->page_tables[pde] = NULL;
+				WARN_ON(!test_and_clear_bit(pde, pd->used_pdes));
+			}
+		}
 
-		for (j = 0; j < GEN8_PDES_PER_PAGE; j++) {
-			struct i915_page_directory_entry *pd = ppgtt->pdp.page_directory[i];
-			struct i915_page_table_entry *pt = pd->page_tables[j];
-			dma_addr_t addr = pt->daddr;
-			if (addr)
-				pci_unmap_page(hwdev, addr, PAGE_SIZE,
-						PCI_DMA_BIDIRECTIONAL);
+		if (bitmap_empty(pd->used_pdes, GEN8_PDES_PER_PAGE)) {
+			unmap_and_free_pd(pd, vm->dev);
+			ppgtt->pdp.page_directory[pdpe] = NULL;
+			WARN_ON(!test_and_clear_bit(pdpe, ppgtt->pdp.used_pdpes));
 		}
 	}
 }
@@ -679,7 +703,6 @@ static void gen8_ppgtt_cleanup(struct i915_address_space *vm)
 	struct i915_hw_ppgtt *ppgtt =
 		container_of(vm, struct i915_hw_ppgtt, base);
 
-	gen8_ppgtt_unmap_pages(ppgtt);
 	gen8_ppgtt_free(ppgtt);
 }
 
@@ -708,6 +731,7 @@ unwind_out:
 	return -ENOMEM;
 }
 
+/* bitmap of new page_directories */
 static int gen8_ppgtt_alloc_page_directories(struct i915_page_directory_pointer_entry *pdp,
 				     uint64_t start,
 				     uint64_t length,
@@ -723,6 +747,7 @@ static int gen8_ppgtt_alloc_page_directories(struct i915_page_directory_pointer_
 	gen8_for_each_pdpe(unused, pdp, start, length, temp, pdpe) {
 		BUG_ON(unused);
 		pdp->page_directory[pdpe] = alloc_pd_single(dev);
+
 		if (IS_ERR(pdp->page_directory[pdpe]))
 			goto unwind_out;
 	}
@@ -744,10 +769,12 @@ static int gen8_alloc_va_range(struct i915_address_space *vm,
 		container_of(vm, struct i915_hw_ppgtt, base);
 	struct i915_page_directory_entry *pd;
 	const uint64_t orig_start = start;
+	const uint64_t orig_length = length;
 	uint64_t temp;
 	uint32_t pdpe;
 	int ret;
 
+	/* Do the allocations first so we can easily bail out */
 	ret = gen8_ppgtt_alloc_page_directories(&ppgtt->pdp, start, length,
 					ppgtt->base.dev);
 	if (ret)
@@ -760,6 +787,26 @@ static int gen8_alloc_va_range(struct i915_address_space *vm,
 			goto err_out;
 	}
 
+	/* Now mark everything we've touched as used. This doesn't allow for
+	 * robust error checking, but it makes the code a hell of a lot simpler.
+	 */
+	start = orig_start;
+	length = orig_length;
+
+	gen8_for_each_pdpe(pd, &ppgtt->pdp, start, length, temp, pdpe) {
+		struct i915_page_table_entry *pt;
+		uint64_t pd_len = gen8_clamp_pd(start, length);
+		uint64_t pd_start = start;
+		uint32_t pde;
+		gen8_for_each_pde(pt, &ppgtt->pd, pd_start, pd_len, temp, pde) {
+			bitmap_set(pd->page_tables[pde]->used_ptes,
+				   gen8_pte_index(start),
+				   gen8_pte_count(start, length));
+			set_bit(pde, pd->used_pdes);
+		}
+		set_bit(pdpe, ppgtt->pdp.used_pdpes);
+	}
+
 	return 0;
 
 err_out:
diff --git a/drivers/gpu/drm/i915/i915_gem_gtt.h b/drivers/gpu/drm/i915/i915_gem_gtt.h
index 4a3371a..c755617 100644
--- a/drivers/gpu/drm/i915/i915_gem_gtt.h
+++ b/drivers/gpu/drm/i915/i915_gem_gtt.h
@@ -205,11 +205,13 @@ struct i915_page_directory_entry {
 		dma_addr_t daddr;
 	};
 
+	unsigned long *used_pdes;
 	struct i915_page_table_entry *page_tables[GEN6_PPGTT_PD_ENTRIES]; /* PDEs */
 };
 
 struct i915_page_directory_pointer_entry {
 	/* struct page *page; */
+	DECLARE_BITMAP(used_pdpes, GEN8_LEGACY_PDPES);
 	struct i915_page_directory_entry *page_directory[GEN8_LEGACY_PDPES];
 };
 
@@ -447,6 +449,28 @@ static inline uint32_t gen8_pml4e_index(uint64_t address)
 	BUG(); /* For 64B */
 }
 
+static inline size_t gen8_pte_count(uint64_t addr, uint64_t length)
+{
+	return i915_pte_count(addr, length, GEN8_PDE_SHIFT);
+}
+
+static inline size_t gen8_pde_count(uint64_t addr, uint64_t length)
+{
+	const uint32_t pdp_shift = GEN8_PDE_SHIFT + 9;
+	const uint64_t mask = ~((1 << pdp_shift) - 1);
+	uint64_t end;
+
+	BUG_ON(length == 0);
+	BUG_ON(offset_in_page(addr|length));
+
+	end = addr + length;
+
+	if ((addr & mask) != (end & mask))
+		return GEN8_PDES_PER_PAGE - i915_pde_index(addr, GEN8_PDE_SHIFT);
+
+	return i915_pde_index(end, GEN8_PDE_SHIFT) - i915_pde_index(addr, GEN8_PDE_SHIFT);
+}
+
 int i915_gem_gtt_init(struct drm_device *dev);
 void i915_gem_init_global_gtt(struct drm_device *dev);
 void i915_global_gtt_cleanup(struct drm_device *dev);
