SSL i915_gem_gtt.c

/*
 * Copyright © 2016 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.
 *
 */

#include <linux/list_sort.h>
#include <linux/prime_numbers.h>

#include "gem/i915_gem_context.h"
#include "gem/i915_gem_internal.h"
#include "gem/i915_gem_lmem.h"
#include "gem/i915_gem_region.h"
#include "gem/selftests/mock_context.h"
#include "gt/intel_context.h"
#include "gt/intel_gpu_commands.h"
#include "gt/intel_gtt.h"

#include "i915_random.h"
#include "i915_selftest.h"
#include "i915_vma_resource.h"

#include "mock_drm.h"
#include "mock_gem_device.h"
#include "mock_gtt.h"
#include "igt_flush_test.h"

static void cleanup_freed_objects(struct drm_i915_private *i915)
{
 i915_gem_drain_freed_objects(i915);
}

static void fake_free_pages(struct drm_i915_gem_object *obj,
       struct sg_table *pages)
{
 sg_free_table(pages);
 kfree(pages);
}

static int fake_get_pages(struct drm_i915_gem_object *obj)
{
#define GFP (GFP_KERNEL | __GFP_NOWARN | __GFP_NORETRY)
#define PFN_BIAS 0x1000
 struct sg_table *pages;
 struct scatterlist *sg;
 typeof(obj->base.size) rem;

 pages = kmalloc(sizeof(*pages), GFP);
 if (!pages)
  return -ENOMEM;

 rem = round_up(obj->base.size, BIT(31)) >> 31;
 /* restricted by sg_alloc_table */
 if (overflows_type(rem, unsigned int)) {
  kfree(pages);
  return -E2BIG;
 }

 if (sg_alloc_table(pages, rem, GFP)) {
  kfree(pages);
  return -ENOMEM;
 }

 rem = obj->base.size;
 for (sg = pages->sgl; sg; sg = sg_next(sg)) {
  unsigned long len = min_t(typeof(rem), rem, BIT(31));

  GEM_BUG_ON(!len);
  sg_set_page(sg, pfn_to_page(PFN_BIAS), len, 0);
  sg_dma_address(sg) = page_to_phys(sg_page(sg));
  sg_dma_len(sg) = len;

  rem -= len;
 }
 GEM_BUG_ON(rem);

 __i915_gem_object_set_pages(obj, pages);

 return 0;
#undef GFP
}

static void fake_put_pages(struct drm_i915_gem_object *obj,
      struct sg_table *pages)
{
 fake_free_pages(obj, pages);
 obj->mm.dirty = false;
}

static const struct drm_i915_gem_object_ops fake_ops = {
 .name = "fake-gem",
 .flags = I915_GEM_OBJECT_IS_SHRINKABLE,
 .get_pages = fake_get_pages,
 .put_pages = fake_put_pages,
};

static struct drm_i915_gem_object *
fake_dma_object(struct drm_i915_private *i915, u64 size)
{
 static struct lock_class_key lock_class;
 struct drm_i915_gem_object *obj;

 GEM_BUG_ON(!size);
 GEM_BUG_ON(!IS_ALIGNED(size, I915_GTT_PAGE_SIZE));

 if (overflows_type(size, obj->base.size))
  return ERR_PTR(-E2BIG);

 obj = i915_gem_object_alloc();
 if (!obj)
  goto err;

 drm_gem_private_object_init(&i915->drm, &obj->base, size);
 i915_gem_object_init(obj, &fake_ops, &lock_class, 0);

 i915_gem_object_set_volatile(obj);

 obj->write_domain = I915_GEM_DOMAIN_CPU;
 obj->read_domains = I915_GEM_DOMAIN_CPU;
 obj->pat_index = i915_gem_get_pat_index(i915, I915_CACHE_NONE);

 /* Preallocate the "backing storage" */
 if (i915_gem_object_pin_pages_unlocked(obj))
  goto err_obj;

 i915_gem_object_unpin_pages(obj);
 return obj;

err_obj:
 i915_gem_object_put(obj);
err:
 return ERR_PTR(-ENOMEM);
}

static int igt_ppgtt_alloc(void *arg)
{
 struct drm_i915_private *dev_priv = arg;
 struct i915_ppgtt *ppgtt;
 struct i915_gem_ww_ctx ww;
 u64 size, last, limit;
 int err = 0;

 /* Allocate a ppggt and try to fill the entire range */

 if (!HAS_PPGTT(dev_priv))
  return 0;

 ppgtt = i915_ppgtt_create(to_gt(dev_priv), 0);
 if (IS_ERR(ppgtt))
  return PTR_ERR(ppgtt);

 if (!ppgtt->vm.allocate_va_range)
  goto ppgtt_vm_put;

 /*
 * While we only allocate the page tables here and so we could
 * address a much larger GTT than we could actually fit into
 * RAM, a practical limit is the amount of physical pages in the system.
 * This should ensure that we do not run into the oomkiller during
 * the test and take down the machine wilfully.
 */
 limit = totalram_pages() << PAGE_SHIFT;
 limit = min(ppgtt->vm.total, limit);

 i915_gem_ww_ctx_init(&ww, false);
retry:
 err = i915_vm_lock_objects(&ppgtt->vm, &ww);
 if (err)
  goto err_ppgtt_cleanup;

 /* Check we can allocate the entire range */
 for (size = 4096; size <= limit; size <<= 2) {
  struct i915_vm_pt_stash stash = {};

  err = i915_vm_alloc_pt_stash(&ppgtt->vm, &stash, size);
  if (err)
   goto err_ppgtt_cleanup;

  err = i915_vm_map_pt_stash(&ppgtt->vm, &stash);
  if (err) {
   i915_vm_free_pt_stash(&ppgtt->vm, &stash);
   goto err_ppgtt_cleanup;
  }

  ppgtt->vm.allocate_va_range(&ppgtt->vm, &stash, 0, size);
  cond_resched();

  ppgtt->vm.clear_range(&ppgtt->vm, 0, size);

  i915_vm_free_pt_stash(&ppgtt->vm, &stash);
 }

 /* Check we can incrementally allocate the entire range */
 for (last = 0, size = 4096; size <= limit; last = size, size <<= 2) {
  struct i915_vm_pt_stash stash = {};

  err = i915_vm_alloc_pt_stash(&ppgtt->vm, &stash, size - last);
  if (err)
   goto err_ppgtt_cleanup;

  err = i915_vm_map_pt_stash(&ppgtt->vm, &stash);
  if (err) {
   i915_vm_free_pt_stash(&ppgtt->vm, &stash);
   goto err_ppgtt_cleanup;
  }

  ppgtt->vm.allocate_va_range(&ppgtt->vm, &stash,
         last, size - last);
  cond_resched();

  i915_vm_free_pt_stash(&ppgtt->vm, &stash);
 }

err_ppgtt_cleanup:
 if (err == -EDEADLK) {
  err = i915_gem_ww_ctx_backoff(&ww);
  if (!err)
   goto retry;
 }
 i915_gem_ww_ctx_fini(&ww);
ppgtt_vm_put:
 i915_vm_put(&ppgtt->vm);
 return err;
}

static int lowlevel_hole(struct i915_address_space *vm,
    u64 hole_start, u64 hole_end,
    unsigned long end_time)
{
 const unsigned int min_alignment =
  i915_vm_min_alignment(vm, INTEL_MEMORY_SYSTEM);
 I915_RND_STATE(seed_prng);
 struct i915_vma_resource *mock_vma_res;
 unsigned int size;

 mock_vma_res = kzalloc(sizeof(*mock_vma_res), GFP_KERNEL);
 if (!mock_vma_res)
  return -ENOMEM;

 /* Keep creating larger objects until one cannot fit into the hole */
 for (size = 12; (hole_end - hole_start) >> size; size++) {
  I915_RND_SUBSTATE(prng, seed_prng);
  struct drm_i915_gem_object *obj;
  unsigned int *order, count, n;
  u64 hole_size, aligned_size;

  aligned_size = max_t(u32, ilog2(min_alignment), size);
  hole_size = (hole_end - hole_start) >> aligned_size;
  if (hole_size > KMALLOC_MAX_SIZE / sizeof(u32))
   hole_size = KMALLOC_MAX_SIZE / sizeof(u32);
  count = hole_size >> 1;
  if (!count) {
   pr_debug("%s: hole is too small [%llx - %llx] >> %d: %lld\n",
     __func__, hole_start, hole_end, size, hole_size);
   break;
  }

  do {
   order = i915_random_order(count, &prng);
   if (order)
    break;
  } while (count >>= 1);
  if (!count) {
   kfree(mock_vma_res);
   return -ENOMEM;
  }
  GEM_BUG_ON(!order);

  GEM_BUG_ON(count * BIT_ULL(aligned_size) > vm->total);
  GEM_BUG_ON(hole_start + count * BIT_ULL(aligned_size) > hole_end);

  /*
 * Ignore allocation failures (i.e. don't report them as
 * a test failure) as we are purposefully allocating very
 * large objects without checking that we have sufficient
 * memory. We expect to hit -ENOMEM.
 */

  obj = fake_dma_object(vm->i915, BIT_ULL(size));
  if (IS_ERR(obj)) {
   kfree(order);
   break;
  }

  GEM_BUG_ON(obj->base.size != BIT_ULL(size));

  if (i915_gem_object_pin_pages_unlocked(obj)) {
   i915_gem_object_put(obj);
   kfree(order);
   break;
  }

  for (n = 0; n < count; n++) {
   u64 addr = hole_start + order[n] * BIT_ULL(aligned_size);
   intel_wakeref_t wakeref;

   GEM_BUG_ON(addr + BIT_ULL(aligned_size) > vm->total);

   if (igt_timeout(end_time,
     "%s timed out before %d/%d\n",
     __func__, n, count)) {
    hole_end = hole_start; /* quit */
    break;
   }

   if (vm->allocate_va_range) {
    struct i915_vm_pt_stash stash = {};
    struct i915_gem_ww_ctx ww;
    int err;

    i915_gem_ww_ctx_init(&ww, false);
retry:
    err = i915_vm_lock_objects(vm, &ww);
    if (err)
     goto alloc_vm_end;

    err = -ENOMEM;
    if (i915_vm_alloc_pt_stash(vm, &stash,
          BIT_ULL(size)))
     goto alloc_vm_end;

    err = i915_vm_map_pt_stash(vm, &stash);
    if (!err)
     vm->allocate_va_range(vm, &stash,
             addr, BIT_ULL(size));
    i915_vm_free_pt_stash(vm, &stash);
alloc_vm_end:
    if (err == -EDEADLK) {
     err = i915_gem_ww_ctx_backoff(&ww);
     if (!err)
      goto retry;
    }
    i915_gem_ww_ctx_fini(&ww);

    if (err)
     break;
   }

   mock_vma_res->bi.pages = obj->mm.pages;
   mock_vma_res->node_size = BIT_ULL(aligned_size);
   mock_vma_res->start = addr;

   with_intel_runtime_pm(vm->gt->uncore->rpm, wakeref)
     vm->insert_entries(vm, mock_vma_res,
          i915_gem_get_pat_index(vm->i915,
            I915_CACHE_NONE),
          0);
  }
  count = n;

  i915_random_reorder(order, count, &prng);
  for (n = 0; n < count; n++) {
   u64 addr = hole_start + order[n] * BIT_ULL(aligned_size);
   intel_wakeref_t wakeref;

   GEM_BUG_ON(addr + BIT_ULL(size) > vm->total);
   with_intel_runtime_pm(vm->gt->uncore->rpm, wakeref)
    vm->clear_range(vm, addr, BIT_ULL(size));
  }

  i915_gem_object_unpin_pages(obj);
  i915_gem_object_put(obj);

  kfree(order);

  cleanup_freed_objects(vm->i915);
 }

 kfree(mock_vma_res);
 return 0;
}

static void close_object_list(struct list_head *objects,
         struct i915_address_space *vm)
{
 struct drm_i915_gem_object *obj, *on;
 int __maybe_unused ignored;

 list_for_each_entry_safe(obj, on, objects, st_link) {
  struct i915_vma *vma;

  vma = i915_vma_instance(obj, vm, NULL);
  if (!IS_ERR(vma))
   ignored = i915_vma_unbind_unlocked(vma);

  list_del(&obj->st_link);
  i915_gem_object_put(obj);
 }
}

static int fill_hole(struct i915_address_space *vm,
       u64 hole_start, u64 hole_end,
       unsigned long end_time)
{
 const u64 hole_size = hole_end - hole_start;
 struct drm_i915_gem_object *obj;
 const unsigned int min_alignment =
  i915_vm_min_alignment(vm, INTEL_MEMORY_SYSTEM);
 const unsigned long max_pages =
  min_t(u64, ULONG_MAX - 1, (hole_size / 2) >> ilog2(min_alignment));
 const unsigned long max_step = max(int_sqrt(max_pages), 2UL);
 unsigned long npages, prime, flags;
 struct i915_vma *vma;
 LIST_HEAD(objects);
 int err;

 /* Try binding many VMA working inwards from either edge */

 flags = PIN_OFFSET_FIXED | PIN_USER;
 if (i915_is_ggtt(vm))
  flags |= PIN_GLOBAL;

 for_each_prime_number_from(prime, 2, max_step) {
  for (npages = 1; npages <= max_pages; npages *= prime) {
   const u64 full_size = npages << PAGE_SHIFT;
   const struct {
    const char *name;
    u64 offset;
    int step;
   } phases[] = {
    { "top-down", hole_end, -1, },
    { "bottom-up", hole_start, 1, },
    { }
   }, *p;

   obj = fake_dma_object(vm->i915, full_size);
   if (IS_ERR(obj))
    break;

   list_add(&obj->st_link, &objects);

   /*
 * Align differing sized objects against the edges, and
 * check we don't walk off into the void when binding
 * them into the GTT.
 */
   for (p = phases; p->name; p++) {
    u64 offset;

    offset = p->offset;
    list_for_each_entry(obj, &objects, st_link) {
     u64 aligned_size = round_up(obj->base.size,
            min_alignment);

     vma = i915_vma_instance(obj, vm, NULL);
     if (IS_ERR(vma))
      continue;

     if (p->step < 0) {
      if (offset < hole_start + aligned_size)
       break;
      offset -= aligned_size;
     }

     err = i915_vma_pin(vma, 0, 0, offset | flags);
     if (err) {
      pr_err("%s(%s) pin (forward) failed with err=%d on size=%lu pages (prime=%lu), offset=%llx\n",
             __func__, p->name, err, npages, prime, offset);
      goto err;
     }

     if (!drm_mm_node_allocated(&vma->node) ||
         i915_vma_misplaced(vma, 0, 0, offset | flags)) {
      pr_err("%s(%s) (forward) insert failed: vma.node=%llx + %llx [allocated? %d], expected offset %llx\n",
             __func__, p->name, vma->node.start, vma->node.size, drm_mm_node_allocated(&vma->node),
             offset);
      err = -EINVAL;
      goto err;
     }

     i915_vma_unpin(vma);

     if (p->step > 0) {
      if (offset + aligned_size > hole_end)
       break;
      offset += aligned_size;
     }
    }

    offset = p->offset;
    list_for_each_entry(obj, &objects, st_link) {
     u64 aligned_size = round_up(obj->base.size,
            min_alignment);

     vma = i915_vma_instance(obj, vm, NULL);
     if (IS_ERR(vma))
      continue;

     if (p->step < 0) {
      if (offset < hole_start + aligned_size)
       break;
      offset -= aligned_size;
     }

     if (!drm_mm_node_allocated(&vma->node) ||
         i915_vma_misplaced(vma, 0, 0, offset | flags)) {
      pr_err("%s(%s) (forward) moved vma.node=%llx + %llx, expected offset %llx\n",
             __func__, p->name, vma->node.start, vma->node.size,
             offset);
      err = -EINVAL;
      goto err;
     }

     err = i915_vma_unbind_unlocked(vma);
     if (err) {
      pr_err("%s(%s) (forward) unbind of vma.node=%llx + %llx failed with err=%d\n",
             __func__, p->name, vma->node.start, vma->node.size,
             err);
      goto err;
     }

     if (p->step > 0) {
      if (offset + aligned_size > hole_end)
       break;
      offset += aligned_size;
     }
    }

    offset = p->offset;
    list_for_each_entry_reverse(obj, &objects, st_link) {
     u64 aligned_size = round_up(obj->base.size,
            min_alignment);

     vma = i915_vma_instance(obj, vm, NULL);
     if (IS_ERR(vma))
      continue;

     if (p->step < 0) {
      if (offset < hole_start + aligned_size)
       break;
      offset -= aligned_size;
     }

     err = i915_vma_pin(vma, 0, 0, offset | flags);
     if (err) {
      pr_err("%s(%s) pin (backward) failed with err=%d on size=%lu pages (prime=%lu), offset=%llx\n",
             __func__, p->name, err, npages, prime, offset);
      goto err;
     }

     if (!drm_mm_node_allocated(&vma->node) ||
         i915_vma_misplaced(vma, 0, 0, offset | flags)) {
      pr_err("%s(%s) (backward) insert failed: vma.node=%llx + %llx [allocated? %d], expected offset %llx\n",
             __func__, p->name, vma->node.start, vma->node.size, drm_mm_node_allocated(&vma->node),
             offset);
      err = -EINVAL;
      goto err;
     }

     i915_vma_unpin(vma);

     if (p->step > 0) {
      if (offset + aligned_size > hole_end)
       break;
      offset += aligned_size;
     }
    }

    offset = p->offset;
    list_for_each_entry_reverse(obj, &objects, st_link) {
     u64 aligned_size = round_up(obj->base.size,
            min_alignment);

     vma = i915_vma_instance(obj, vm, NULL);
     if (IS_ERR(vma))
      continue;

     if (p->step < 0) {
      if (offset < hole_start + aligned_size)
       break;
      offset -= aligned_size;
     }

     if (!drm_mm_node_allocated(&vma->node) ||
         i915_vma_misplaced(vma, 0, 0, offset | flags)) {
      pr_err("%s(%s) (backward) moved vma.node=%llx + %llx [allocated? %d], expected offset %llx\n",
             __func__, p->name, vma->node.start, vma->node.size, drm_mm_node_allocated(&vma->node),
             offset);
      err = -EINVAL;
      goto err;
     }

     err = i915_vma_unbind_unlocked(vma);
     if (err) {
      pr_err("%s(%s) (backward) unbind of vma.node=%llx + %llx failed with err=%d\n",
             __func__, p->name, vma->node.start, vma->node.size,
             err);
      goto err;
     }

     if (p->step > 0) {
      if (offset + aligned_size > hole_end)
       break;
      offset += aligned_size;
     }
    }
   }

   if (igt_timeout(end_time, "%s timed out (npages=%lu, prime=%lu)\n",
     __func__, npages, prime)) {
    err = -EINTR;
    goto err;
   }
  }

  close_object_list(&objects, vm);
  cleanup_freed_objects(vm->i915);
 }

 return 0;

err:
 close_object_list(&objects, vm);
 return err;
}

static int walk_hole(struct i915_address_space *vm,
       u64 hole_start, u64 hole_end,
       unsigned long end_time)
{
 const u64 hole_size = hole_end - hole_start;
 const unsigned long max_pages =
  min_t(u64, ULONG_MAX - 1, hole_size >> PAGE_SHIFT);
 unsigned long min_alignment;
 unsigned long flags;
 u64 size;

 /* Try binding a single VMA in different positions within the hole */

 flags = PIN_OFFSET_FIXED | PIN_USER;
 if (i915_is_ggtt(vm))
  flags |= PIN_GLOBAL;

 min_alignment = i915_vm_min_alignment(vm, INTEL_MEMORY_SYSTEM);

 for_each_prime_number_from(size, 1, max_pages) {
  struct drm_i915_gem_object *obj;
  struct i915_vma *vma;
  u64 addr;
  int err = 0;

  obj = fake_dma_object(vm->i915, size << PAGE_SHIFT);
  if (IS_ERR(obj))
   break;

  vma = i915_vma_instance(obj, vm, NULL);
  if (IS_ERR(vma)) {
   err = PTR_ERR(vma);
   goto err_put;
  }

  for (addr = hole_start;
       addr + obj->base.size < hole_end;
       addr += round_up(obj->base.size, min_alignment)) {
   err = i915_vma_pin(vma, 0, 0, addr | flags);
   if (err) {
    pr_err("%s bind failed at %llx + %llx [hole %llx- %llx] with err=%d\n",
           __func__, addr, vma->size,
           hole_start, hole_end, err);
    goto err_put;
   }
   i915_vma_unpin(vma);

   if (!drm_mm_node_allocated(&vma->node) ||
       i915_vma_misplaced(vma, 0, 0, addr | flags)) {
    pr_err("%s incorrect at %llx + %llx\n",
           __func__, addr, vma->size);
    err = -EINVAL;
    goto err_put;
   }

   err = i915_vma_unbind_unlocked(vma);
   if (err) {
    pr_err("%s unbind failed at %llx + %llx  with err=%d\n",
           __func__, addr, vma->size, err);
    goto err_put;
   }

   GEM_BUG_ON(drm_mm_node_allocated(&vma->node));

   if (igt_timeout(end_time,
     "%s timed out at %llx\n",
     __func__, addr)) {
    err = -EINTR;
    goto err_put;
   }
  }

err_put:
  i915_gem_object_put(obj);
  if (err)
   return err;

  cleanup_freed_objects(vm->i915);
 }

 return 0;
}

static int pot_hole(struct i915_address_space *vm,
      u64 hole_start, u64 hole_end,
      unsigned long end_time)
{
 struct drm_i915_gem_object *obj;
 struct i915_vma *vma;
 unsigned int min_alignment;
 unsigned long flags;
 unsigned int pot;
 int err = 0;

 flags = PIN_OFFSET_FIXED | PIN_USER;
 if (i915_is_ggtt(vm))
  flags |= PIN_GLOBAL;

 min_alignment = i915_vm_min_alignment(vm, INTEL_MEMORY_SYSTEM);

 obj = i915_gem_object_create_internal(vm->i915, 2 * I915_GTT_PAGE_SIZE);
 if (IS_ERR(obj))
  return PTR_ERR(obj);

 vma = i915_vma_instance(obj, vm, NULL);
 if (IS_ERR(vma)) {
  err = PTR_ERR(vma);
  goto err_obj;
 }

 /* Insert a pair of pages across every pot boundary within the hole */
 for (pot = fls64(hole_end - 1) - 1;
      pot > ilog2(2 * min_alignment);
      pot--) {
  u64 step = BIT_ULL(pot);
  u64 addr;

  for (addr = round_up(hole_start + min_alignment, step) - min_alignment;
       hole_end > addr && hole_end - addr >= 2 * min_alignment;
       addr += step) {
   err = i915_vma_pin(vma, 0, 0, addr | flags);
   if (err) {
    pr_err("%s failed to pin object at %llx in hole [%llx - %llx], with err=%d\n",
           __func__,
           addr,
           hole_start, hole_end,
           err);
    goto err_obj;
   }

   if (!drm_mm_node_allocated(&vma->node) ||
       i915_vma_misplaced(vma, 0, 0, addr | flags)) {
    pr_err("%s incorrect at %llx + %llx\n",
           __func__, addr, vma->size);
    i915_vma_unpin(vma);
    err = i915_vma_unbind_unlocked(vma);
    err = -EINVAL;
    goto err_obj;
   }

   i915_vma_unpin(vma);
   err = i915_vma_unbind_unlocked(vma);
   GEM_BUG_ON(err);
  }

  if (igt_timeout(end_time,
    "%s timed out after %d/%d\n",
    __func__, pot, fls64(hole_end - 1) - 1)) {
   err = -EINTR;
   goto err_obj;
  }
 }

err_obj:
 i915_gem_object_put(obj);
 return err;
}

static int drunk_hole(struct i915_address_space *vm,
        u64 hole_start, u64 hole_end,
        unsigned long end_time)
{
 I915_RND_STATE(prng);
 unsigned int min_alignment;
 unsigned int size;
 unsigned long flags;

 flags = PIN_OFFSET_FIXED | PIN_USER;
 if (i915_is_ggtt(vm))
  flags |= PIN_GLOBAL;

 min_alignment = i915_vm_min_alignment(vm, INTEL_MEMORY_SYSTEM);

 /* Keep creating larger objects until one cannot fit into the hole */
 for (size = 12; (hole_end - hole_start) >> size; size++) {
  struct drm_i915_gem_object *obj;
  unsigned int *order, count, n;
  struct i915_vma *vma;
  u64 hole_size, aligned_size;
  int err = -ENODEV;

  aligned_size = max_t(u32, ilog2(min_alignment), size);
  hole_size = (hole_end - hole_start) >> aligned_size;
  if (hole_size > KMALLOC_MAX_SIZE / sizeof(u32))
   hole_size = KMALLOC_MAX_SIZE / sizeof(u32);
  count = hole_size >> 1;
  if (!count) {
   pr_debug("%s: hole is too small [%llx - %llx] >> %d: %lld\n",
     __func__, hole_start, hole_end, size, hole_size);
   break;
  }

  do {
   order = i915_random_order(count, &prng);
   if (order)
    break;
  } while (count >>= 1);
  if (!count)
   return -ENOMEM;
  GEM_BUG_ON(!order);

  /*
 * Ignore allocation failures (i.e. don't report them as
 * a test failure) as we are purposefully allocating very
 * large objects without checking that we have sufficient
 * memory. We expect to hit -ENOMEM.
 */

  obj = fake_dma_object(vm->i915, BIT_ULL(size));
  if (IS_ERR(obj)) {
   kfree(order);
   break;
  }

  vma = i915_vma_instance(obj, vm, NULL);
  if (IS_ERR(vma)) {
   err = PTR_ERR(vma);
   goto err_obj;
  }

  GEM_BUG_ON(vma->size != BIT_ULL(size));

  for (n = 0; n < count; n++) {
   u64 addr = hole_start + order[n] * BIT_ULL(aligned_size);

   err = i915_vma_pin(vma, 0, 0, addr | flags);
   if (err) {
    pr_err("%s failed to pin object at %llx + %llx in hole [%llx - %llx], with err=%d\n",
           __func__,
           addr, BIT_ULL(size),
           hole_start, hole_end,
           err);
    goto err_obj;
   }

   if (!drm_mm_node_allocated(&vma->node) ||
       i915_vma_misplaced(vma, 0, 0, addr | flags)) {
    pr_err("%s incorrect at %llx + %llx\n",
           __func__, addr, BIT_ULL(size));
    i915_vma_unpin(vma);
    err = i915_vma_unbind_unlocked(vma);
    err = -EINVAL;
    goto err_obj;
   }

   i915_vma_unpin(vma);
   err = i915_vma_unbind_unlocked(vma);
   GEM_BUG_ON(err);

   if (igt_timeout(end_time,
     "%s timed out after %d/%d\n",
     __func__, n, count)) {
    err = -EINTR;
    goto err_obj;
   }
  }

err_obj:
  i915_gem_object_put(obj);
  kfree(order);
  if (err)
   return err;

  cleanup_freed_objects(vm->i915);
 }

 return 0;
}

static int __shrink_hole(struct i915_address_space *vm,
    u64 hole_start, u64 hole_end,
    unsigned long end_time)
{
 struct drm_i915_gem_object *obj;
 unsigned long flags = PIN_OFFSET_FIXED | PIN_USER;
 unsigned int min_alignment;
 unsigned int order = 12;
 LIST_HEAD(objects);
 int err = 0;
 u64 addr;

 min_alignment = i915_vm_min_alignment(vm, INTEL_MEMORY_SYSTEM);

 /* Keep creating larger objects until one cannot fit into the hole */
 for (addr = hole_start; addr < hole_end; ) {
  struct i915_vma *vma;
  u64 size = BIT_ULL(order++);

  size = min(size, hole_end - addr);
  obj = fake_dma_object(vm->i915, size);
  if (IS_ERR(obj)) {
   err = PTR_ERR(obj);
   break;
  }

  list_add(&obj->st_link, &objects);

  vma = i915_vma_instance(obj, vm, NULL);
  if (IS_ERR(vma)) {
   err = PTR_ERR(vma);
   break;
  }

  GEM_BUG_ON(vma->size != size);

  err = i915_vma_pin(vma, 0, 0, addr | flags);
  if (err) {
   pr_err("%s failed to pin object at %llx + %llx in hole [%llx - %llx], with err=%d\n",
          __func__, addr, size, hole_start, hole_end, err);
   break;
  }

  if (!drm_mm_node_allocated(&vma->node) ||
      i915_vma_misplaced(vma, 0, 0, addr | flags)) {
   pr_err("%s incorrect at %llx + %llx\n",
          __func__, addr, size);
   i915_vma_unpin(vma);
   err = i915_vma_unbind_unlocked(vma);
   err = -EINVAL;
   break;
  }

  i915_vma_unpin(vma);
  addr += round_up(size, min_alignment);

  /*
 * Since we are injecting allocation faults at random intervals,
 * wait for this allocation to complete before we change the
 * faultinjection.
 */
  err = i915_vma_sync(vma);
  if (err)
   break;

  if (igt_timeout(end_time,
    "%s timed out at offset %llx [%llx - %llx]\n",
    __func__, addr, hole_start, hole_end)) {
   err = -EINTR;
   break;
  }
 }

 close_object_list(&objects, vm);
 cleanup_freed_objects(vm->i915);
 return err;
}

static int shrink_hole(struct i915_address_space *vm,
         u64 hole_start, u64 hole_end,
         unsigned long end_time)
{
 unsigned long prime;
 int err;

 vm->fault_attr.probability = 999;
 atomic_set(&vm->fault_attr.times, -1);

 for_each_prime_number_from(prime, 0, ULONG_MAX - 1) {
  vm->fault_attr.interval = prime;
  err = __shrink_hole(vm, hole_start, hole_end, end_time);
  if (err)
   break;
 }

 memset(&vm->fault_attr, 0, sizeof(vm->fault_attr));

 return err;
}

static int shrink_boom(struct i915_address_space *vm,
         u64 hole_start, u64 hole_end,
         unsigned long end_time)
{
 unsigned int sizes[] = { SZ_2M, SZ_1G };
 struct drm_i915_gem_object *purge;
 struct drm_i915_gem_object *explode;
 int err;
 int i;

 /*
 * Catch the case which shrink_hole seems to miss. The setup here
 * requires invoking the shrinker as we do the alloc_pt/alloc_pd, while
 * ensuring that all vma associated with the respective pd/pdp are
 * unpinned at the time.
 */

 for (i = 0; i < ARRAY_SIZE(sizes); ++i) {
  unsigned int flags = PIN_USER | PIN_OFFSET_FIXED;
  unsigned int size = sizes[i];
  struct i915_vma *vma;

  purge = fake_dma_object(vm->i915, size);
  if (IS_ERR(purge))
   return PTR_ERR(purge);

  vma = i915_vma_instance(purge, vm, NULL);
  if (IS_ERR(vma)) {
   err = PTR_ERR(vma);
   goto err_purge;
  }

  err = i915_vma_pin(vma, 0, 0, flags);
  if (err)
   goto err_purge;

  /* Should now be ripe for purging */
  i915_vma_unpin(vma);

  explode = fake_dma_object(vm->i915, size);
  if (IS_ERR(explode)) {
   err = PTR_ERR(explode);
   goto err_purge;
  }

  vm->fault_attr.probability = 100;
  vm->fault_attr.interval = 1;
  atomic_set(&vm->fault_attr.times, -1);

  vma = i915_vma_instance(explode, vm, NULL);
  if (IS_ERR(vma)) {
   err = PTR_ERR(vma);
   goto err_explode;
  }

  err = i915_vma_pin(vma, 0, 0, flags | size);
  if (err)
   goto err_explode;

  i915_vma_unpin(vma);

  i915_gem_object_put(purge);
  i915_gem_object_put(explode);

  memset(&vm->fault_attr, 0, sizeof(vm->fault_attr));
  cleanup_freed_objects(vm->i915);
 }

 return 0;

err_explode:
 i915_gem_object_put(explode);
err_purge:
 i915_gem_object_put(purge);
 memset(&vm->fault_attr, 0, sizeof(vm->fault_attr));
 return err;
}

static int misaligned_case(struct i915_address_space *vm, struct intel_memory_region *mr,
      u64 addr, u64 size, unsigned long flags)
{
 struct drm_i915_gem_object *obj;
 struct i915_vma *vma;
 int err = 0;
 u64 expected_vma_size, expected_node_size;
 bool is_stolen = mr->type == INTEL_MEMORY_STOLEN_SYSTEM ||
    mr->type == INTEL_MEMORY_STOLEN_LOCAL;

 obj = i915_gem_object_create_region(mr, size, 0, I915_BO_ALLOC_GPU_ONLY);
 if (IS_ERR(obj)) {
  /* if iGVT-g or DMAR is active, stolen mem will be uninitialized */
  if (PTR_ERR(obj) == -ENODEV && is_stolen)
   return 0;
  return PTR_ERR(obj);
 }

 vma = i915_vma_instance(obj, vm, NULL);
 if (IS_ERR(vma)) {
  err = PTR_ERR(vma);
  goto err_put;
 }

 err = i915_vma_pin(vma, 0, 0, addr | flags);
 if (err)
  goto err_put;
 i915_vma_unpin(vma);

 if (!drm_mm_node_allocated(&vma->node)) {
  err = -EINVAL;
  goto err_put;
 }

 if (i915_vma_misplaced(vma, 0, 0, addr | flags)) {
  err = -EINVAL;
  goto err_put;
 }

 expected_vma_size = round_up(size, 1 << (ffs(vma->resource->page_sizes_gtt) - 1));
 expected_node_size = expected_vma_size;

 if (HAS_64K_PAGES(vm->i915) && i915_gem_object_is_lmem(obj)) {
  expected_vma_size = round_up(size, I915_GTT_PAGE_SIZE_64K);
  expected_node_size = round_up(size, I915_GTT_PAGE_SIZE_64K);
 }

 if (vma->size != expected_vma_size || vma->node.size != expected_node_size) {
  err = i915_vma_unbind_unlocked(vma);
  err = -EBADSLT;
  goto err_put;
 }

 err = i915_vma_unbind_unlocked(vma);
 if (err)
  goto err_put;

 GEM_BUG_ON(drm_mm_node_allocated(&vma->node));

err_put:
 i915_gem_object_put(obj);
 cleanup_freed_objects(vm->i915);
 return err;
}

static int misaligned_pin(struct i915_address_space *vm,
     u64 hole_start, u64 hole_end,
     unsigned long end_time)
{
 struct intel_memory_region *mr;
 enum intel_region_id id;
 unsigned long flags = PIN_OFFSET_FIXED | PIN_USER;
 int err = 0;
 u64 hole_size = hole_end - hole_start;

 if (i915_is_ggtt(vm))
  flags |= PIN_GLOBAL;

 for_each_memory_region(mr, vm->i915, id) {
  u64 min_alignment = i915_vm_min_alignment(vm, mr->type);
  u64 size = min_alignment;
  u64 addr = round_down(hole_start + (hole_size / 2), min_alignment);

  /* avoid -ENOSPC on very small hole setups */
  if (hole_size < 3 * min_alignment)
   continue;

  /* we can't test < 4k alignment due to flags being encoded in lower bits */
  if (min_alignment != I915_GTT_PAGE_SIZE_4K) {
   err = misaligned_case(vm, mr, addr + (min_alignment / 2), size, flags);
   /* misaligned should error with -EINVAL*/
   if (!err)
    err = -EBADSLT;
   if (err != -EINVAL)
    return err;
  }

  /* test for vma->size expansion to min page size */
  err = misaligned_case(vm, mr, addr, PAGE_SIZE, flags);
  if (err)
   return err;

  /* test for intermediate size not expanding vma->size for large alignments */
  err = misaligned_case(vm, mr, addr, size / 2, flags);
  if (err)
   return err;
 }

 return 0;
}

static int exercise_ppgtt(struct drm_i915_private *dev_priv,
     int (*func)(struct i915_address_space *vm,
          u64 hole_start, u64 hole_end,
          unsigned long end_time))
{
 struct i915_ppgtt *ppgtt;
 IGT_TIMEOUT(end_time);
 struct file *file;
 int err;

 if (!HAS_FULL_PPGTT(dev_priv))
  return 0;

 file = mock_file(dev_priv);
 if (IS_ERR(file))
  return PTR_ERR(file);

 ppgtt = i915_ppgtt_create(to_gt(dev_priv), 0);
 if (IS_ERR(ppgtt)) {
  err = PTR_ERR(ppgtt);
  goto out_free;
 }
 GEM_BUG_ON(offset_in_page(ppgtt->vm.total));
 assert_vm_alive(&ppgtt->vm);

 err = func(&ppgtt->vm, 0, ppgtt->vm.total, end_time);

 i915_vm_put(&ppgtt->vm);

out_free:
 fput(file);
 return err;
}

static int igt_ppgtt_fill(void *arg)
{
 return exercise_ppgtt(arg, fill_hole);
}

static int igt_ppgtt_walk(void *arg)
{
 return exercise_ppgtt(arg, walk_hole);
}

static int igt_ppgtt_pot(void *arg)
{
 return exercise_ppgtt(arg, pot_hole);
}

static int igt_ppgtt_drunk(void *arg)
{
 return exercise_ppgtt(arg, drunk_hole);
}

static int igt_ppgtt_lowlevel(void *arg)
{
 return exercise_ppgtt(arg, lowlevel_hole);
}

static int igt_ppgtt_shrink(void *arg)
{
 return exercise_ppgtt(arg, shrink_hole);
}

static int igt_ppgtt_shrink_boom(void *arg)
{
 return exercise_ppgtt(arg, shrink_boom);
}

static int igt_ppgtt_misaligned_pin(void *arg)
{
 return exercise_ppgtt(arg, misaligned_pin);
}

static int sort_holes(void *priv, const struct list_head *A,
        const struct list_head *B)
{
 struct drm_mm_node *a = list_entry(A, typeof(*a), hole_stack);
 struct drm_mm_node *b = list_entry(B, typeof(*b), hole_stack);

 if (a->start < b->start)
  return -1;
 else
  return 1;
}

static int exercise_ggtt(struct drm_i915_private *i915,
    int (*func)(struct i915_address_space *vm,
         u64 hole_start, u64 hole_end,
         unsigned long end_time))
{
 struct i915_ggtt *ggtt = to_gt(i915)->ggtt;
 u64 hole_start, hole_end, last = 0;
 struct drm_mm_node *node;
 IGT_TIMEOUT(end_time);
 int err = 0;

restart:
 list_sort(NULL, &ggtt->vm.mm.hole_stack, sort_holes);
 drm_mm_for_each_hole(node, &ggtt->vm.mm, hole_start, hole_end) {
  if (hole_start < last)
   continue;

  if (ggtt->vm.mm.color_adjust)
   ggtt->vm.mm.color_adjust(node, 0,
       &hole_start, &hole_end);
  if (hole_start >= hole_end)
   continue;

  err = func(&ggtt->vm, hole_start, hole_end, end_time);
  if (err)
   break;

  /* As we have manipulated the drm_mm, the list may be corrupt */
  last = hole_end;
  goto restart;
 }

 return err;
}

static int igt_ggtt_fill(void *arg)
{
 return exercise_ggtt(arg, fill_hole);
}

static int igt_ggtt_walk(void *arg)
{
 return exercise_ggtt(arg, walk_hole);
}

static int igt_ggtt_pot(void *arg)
{
 return exercise_ggtt(arg, pot_hole);
}

static int igt_ggtt_drunk(void *arg)
{
 return exercise_ggtt(arg, drunk_hole);
}

static int igt_ggtt_lowlevel(void *arg)
{
 return exercise_ggtt(arg, lowlevel_hole);
}

static int igt_ggtt_misaligned_pin(void *arg)
{
 return exercise_ggtt(arg, misaligned_pin);
}

static int igt_ggtt_page(void *arg)
{
 const unsigned int count = PAGE_SIZE/sizeof(u32);
 I915_RND_STATE(prng);
 struct drm_i915_private *i915 = arg;
 struct i915_ggtt *ggtt = to_gt(i915)->ggtt;
 struct drm_i915_gem_object *obj;
 intel_wakeref_t wakeref;
 struct drm_mm_node tmp;
 unsigned int *order, n;
 int err;

 if (!i915_ggtt_has_aperture(ggtt))
  return 0;

 obj = i915_gem_object_create_internal(i915, PAGE_SIZE);
 if (IS_ERR(obj))
  return PTR_ERR(obj);

 err = i915_gem_object_pin_pages_unlocked(obj);
 if (err)
  goto out_free;

 memset(&tmp, 0, sizeof(tmp));
 mutex_lock(&ggtt->vm.mutex);
 err = drm_mm_insert_node_in_range(&ggtt->vm.mm, &tmp,
       count * PAGE_SIZE, 0,
       I915_COLOR_UNEVICTABLE,
       0, ggtt->mappable_end,
       DRM_MM_INSERT_LOW);
 mutex_unlock(&ggtt->vm.mutex);
 if (err)
  goto out_unpin;

 wakeref = intel_runtime_pm_get(&i915->runtime_pm);

 for (n = 0; n < count; n++) {
  u64 offset = tmp.start + n * PAGE_SIZE;

  ggtt->vm.insert_page(&ggtt->vm,
         i915_gem_object_get_dma_address(obj, 0),
         offset,
         i915_gem_get_pat_index(i915,
           I915_CACHE_NONE),
         0);
 }

 order = i915_random_order(count, &prng);
 if (!order) {
  err = -ENOMEM;
  goto out_remove;
 }

 for (n = 0; n < count; n++) {
  u64 offset = tmp.start + order[n] * PAGE_SIZE;
  u32 __iomem *vaddr;

  vaddr = io_mapping_map_atomic_wc(&ggtt->iomap, offset);
  iowrite32(n, vaddr + n);
  io_mapping_unmap_atomic(vaddr);
 }
 intel_gt_flush_ggtt_writes(ggtt->vm.gt);

 i915_random_reorder(order, count, &prng);
 for (n = 0; n < count; n++) {
  u64 offset = tmp.start + order[n] * PAGE_SIZE;
  u32 __iomem *vaddr;
  u32 val;

  vaddr = io_mapping_map_atomic_wc(&ggtt->iomap, offset);
  val = ioread32(vaddr + n);
  io_mapping_unmap_atomic(vaddr);

  if (val != n) {
   pr_err("insert page failed: found %d, expected %d\n",
          val, n);
   err = -EINVAL;
   break;
  }
 }

 kfree(order);
out_remove:
 ggtt->vm.clear_range(&ggtt->vm, tmp.start, tmp.size);
 intel_runtime_pm_put(&i915->runtime_pm, wakeref);
 mutex_lock(&ggtt->vm.mutex);
 drm_mm_remove_node(&tmp);
 mutex_unlock(&ggtt->vm.mutex);
out_unpin:
 i915_gem_object_unpin_pages(obj);
out_free:
 i915_gem_object_put(obj);
 return err;
}

static void track_vma_bind(struct i915_vma *vma)
{
 struct drm_i915_gem_object *obj = vma->obj;

 __i915_gem_object_pin_pages(obj);

 GEM_BUG_ON(atomic_read(&vma->pages_count));
 atomic_set(&vma->pages_count, I915_VMA_PAGES_ACTIVE);
 __i915_gem_object_pin_pages(obj);
 vma->pages = obj->mm.pages;
 vma->resource->bi.pages = vma->pages;

 mutex_lock(&vma->vm->mutex);
 list_move_tail(&vma->vm_link, &vma->vm->bound_list);
 mutex_unlock(&vma->vm->mutex);
}

static int exercise_mock(struct drm_i915_private *i915,
    int (*func)(struct i915_address_space *vm,
         u64 hole_start, u64 hole_end,
         unsigned long end_time))
{
 const u64 limit = totalram_pages() << PAGE_SHIFT;
 struct i915_address_space *vm;
 struct i915_gem_context *ctx;
 IGT_TIMEOUT(end_time);
 int err;

 ctx = mock_context(i915, "mock");
 if (!ctx)
  return -ENOMEM;

 vm = i915_gem_context_get_eb_vm(ctx);
 err = func(vm, 0, min(vm->total, limit), end_time);
 i915_vm_put(vm);

 mock_context_close(ctx);
 return err;
}

static int igt_mock_fill(void *arg)
{
 struct i915_ggtt *ggtt = arg;

 return exercise_mock(ggtt->vm.i915, fill_hole);
}

static int igt_mock_walk(void *arg)
{
 struct i915_ggtt *ggtt = arg;

 return exercise_mock(ggtt->vm.i915, walk_hole);
}

static int igt_mock_pot(void *arg)
{
 struct i915_ggtt *ggtt = arg;

 return exercise_mock(ggtt->vm.i915, pot_hole);
}

static int igt_mock_drunk(void *arg)
{
 struct i915_ggtt *ggtt = arg;

 return exercise_mock(ggtt->vm.i915, drunk_hole);
}

static int reserve_gtt_with_resource(struct i915_vma *vma, u64 offset)
{
 struct i915_address_space *vm = vma->vm;
 struct i915_vma_resource *vma_res;
 struct drm_i915_gem_object *obj = vma->obj;
 int err;

 vma_res = i915_vma_resource_alloc();
 if (IS_ERR(vma_res))
  return PTR_ERR(vma_res);

 mutex_lock(&vm->mutex);
 err = i915_gem_gtt_reserve(vm, NULL, &vma->node, obj->base.size,
       offset,
       obj->pat_index,
       0);
 if (!err) {
  i915_vma_resource_init_from_vma(vma_res, vma);
  vma->resource = vma_res;
 } else {
  kfree(vma_res);
 }
 mutex_unlock(&vm->mutex);

 return err;
}

static int igt_gtt_reserve(void *arg)
{
 struct i915_ggtt *ggtt = arg;
 struct drm_i915_gem_object *obj, *on;
 I915_RND_STATE(prng);
 LIST_HEAD(objects);
 u64 total;
 int err = -ENODEV;

 /*
 * i915_gem_gtt_reserve() tries to reserve the precise range
 * for the node, and evicts if it has to. So our test checks that
 * it can give us the requested space and prevent overlaps.
 */

 /* Start by filling the GGTT */
 for (total = 0;
      total + 2 * I915_GTT_PAGE_SIZE <= ggtt->vm.total;
      total += 2 * I915_GTT_PAGE_SIZE) {
  struct i915_vma *vma;

  obj = i915_gem_object_create_internal(ggtt->vm.i915,
            2 * PAGE_SIZE);
  if (IS_ERR(obj)) {
   err = PTR_ERR(obj);
   goto out;
  }

  err = i915_gem_object_pin_pages_unlocked(obj);
  if (err) {
   i915_gem_object_put(obj);
   goto out;
  }

  list_add(&obj->st_link, &objects);
  vma = i915_vma_instance(obj, &ggtt->vm, NULL);
  if (IS_ERR(vma)) {
   err = PTR_ERR(vma);
   goto out;
  }

  err = reserve_gtt_with_resource(vma, total);
  if (err) {
   pr_err("i915_gem_gtt_reserve (pass 1) failed at %llu/%llu with err=%d\n",
          total, ggtt->vm.total, err);
   goto out;
  }
  track_vma_bind(vma);

  GEM_BUG_ON(!drm_mm_node_allocated(&vma->node));
  if (vma->node.start != total ||
      vma->node.size != 2*I915_GTT_PAGE_SIZE) {
   pr_err("i915_gem_gtt_reserve (pass 1) placement failed, found (%llx + %llx), expected (%llx + %llx)\n",
          vma->node.start, vma->node.size,
          total, 2*I915_GTT_PAGE_SIZE);
   err = -EINVAL;
   goto out;
  }
 }

 /* Now we start forcing evictions */
 for (total = I915_GTT_PAGE_SIZE;
      total + 2 * I915_GTT_PAGE_SIZE <= ggtt->vm.total;
      total += 2 * I915_GTT_PAGE_SIZE) {
  struct i915_vma *vma;

  obj = i915_gem_object_create_internal(ggtt->vm.i915,
            2 * PAGE_SIZE);
  if (IS_ERR(obj)) {
   err = PTR_ERR(obj);
   goto out;
  }

  err = i915_gem_object_pin_pages_unlocked(obj);
  if (err) {
   i915_gem_object_put(obj);
   goto out;
  }

  list_add(&obj->st_link, &objects);

  vma = i915_vma_instance(obj, &ggtt->vm, NULL);
  if (IS_ERR(vma)) {
   err = PTR_ERR(vma);
   goto out;
  }

  err = reserve_gtt_with_resource(vma, total);
  if (err) {
   pr_err("i915_gem_gtt_reserve (pass 2) failed at %llu/%llu with err=%d\n",
          total, ggtt->vm.total, err);
   goto out;
  }
  track_vma_bind(vma);

  GEM_BUG_ON(!drm_mm_node_allocated(&vma->node));
  if (vma->node.start != total ||
      vma->node.size != 2*I915_GTT_PAGE_SIZE) {
   pr_err("i915_gem_gtt_reserve (pass 2) placement failed, found (%llx + %llx), expected (%llx + %llx)\n",
          vma->node.start, vma->node.size,
          total, 2*I915_GTT_PAGE_SIZE);
   err = -EINVAL;
   goto out;
  }
 }

 /* And then try at random */
 list_for_each_entry_safe(obj, on, &objects, st_link) {
  struct i915_vma *vma;
  u64 offset;

  vma = i915_vma_instance(obj, &ggtt->vm, NULL);
  if (IS_ERR(vma)) {
   err = PTR_ERR(vma);
   goto out;
  }

  err = i915_vma_unbind_unlocked(vma);
  if (err) {
   pr_err("i915_vma_unbind failed with err=%d!\n", err);
   goto out;
  }

  offset = igt_random_offset(&prng,
        0, ggtt->vm.total,
        2 * I915_GTT_PAGE_SIZE,
        I915_GTT_MIN_ALIGNMENT);

  err = reserve_gtt_with_resource(vma, offset);
  if (err) {
   pr_err("i915_gem_gtt_reserve (pass 3) failed at %llu/%llu with err=%d\n",
          total, ggtt->vm.total, err);
   goto out;
  }
  track_vma_bind(vma);

  GEM_BUG_ON(!drm_mm_node_allocated(&vma->node));
  if (vma->node.start != offset ||
      vma->node.size != 2*I915_GTT_PAGE_SIZE) {
   pr_err("i915_gem_gtt_reserve (pass 3) placement failed, found (%llx + %llx), expected (%llx + %llx)\n",
          vma->node.start, vma->node.size,
          offset, 2*I915_GTT_PAGE_SIZE);
   err = -EINVAL;
   goto out;
  }
 }

out:
 list_for_each_entry_safe(obj, on, &objects, st_link) {
  i915_gem_object_unpin_pages(obj);
  i915_gem_object_put(obj);
 }
 return err;
}

static int insert_gtt_with_resource(struct i915_vma *vma)
{
 struct i915_address_space *vm = vma->vm;
 struct i915_vma_resource *vma_res;
 struct drm_i915_gem_object *obj = vma->obj;
 int err;

 vma_res = i915_vma_resource_alloc();
 if (IS_ERR(vma_res))
  return PTR_ERR(vma_res);

 mutex_lock(&vm->mutex);
 err = i915_gem_gtt_insert(vm, NULL, &vma->node, obj->base.size, 0,
      obj->pat_index, 0, vm->total, 0);
 if (!err) {
  i915_vma_resource_init_from_vma(vma_res, vma);
  vma->resource = vma_res;
 } else {
  kfree(vma_res);
 }
 mutex_unlock(&vm->mutex);

 return err;
}

static int igt_gtt_insert(void *arg)
{
 struct i915_ggtt *ggtt = arg;
 struct drm_i915_gem_object *obj, *on;
 struct drm_mm_node tmp = {};
 const struct invalid_insert {
  u64 size;
  u64 alignment;
  u64 start, end;
 } invalid_insert[] = {
  {
   ggtt->vm.total + I915_GTT_PAGE_SIZE, 0,
   0, ggtt->vm.total,
  },
  {
   2*I915_GTT_PAGE_SIZE, 0,
   0, I915_GTT_PAGE_SIZE,
  },
  {
   -(u64)I915_GTT_PAGE_SIZE, 0,
   0, 4*I915_GTT_PAGE_SIZE,
  },
  {
   -(u64)2*I915_GTT_PAGE_SIZE, 2*I915_GTT_PAGE_SIZE,
   0, 4*I915_GTT_PAGE_SIZE,
  },
  {
   I915_GTT_PAGE_SIZE, I915_GTT_MIN_ALIGNMENT << 1,
   I915_GTT_MIN_ALIGNMENT, I915_GTT_MIN_ALIGNMENT << 1,
  },
  {}
 }, *ii;
 LIST_HEAD(objects);
 u64 total;
 int err = -ENODEV;

 /*
 * i915_gem_gtt_insert() tries to allocate some free space in the GTT
 * to the node, evicting if required.
 */

 /* Check a couple of obviously invalid requests */
 for (ii = invalid_insert; ii->size; ii++) {
  mutex_lock(&ggtt->vm.mutex);
  err = i915_gem_gtt_insert(&ggtt->vm, NULL, &tmp,
       ii->size, ii->alignment,
       I915_COLOR_UNEVICTABLE,
       ii->start, ii->end,
       0);
  mutex_unlock(&ggtt->vm.mutex);
  if (err != -ENOSPC) {
   pr_err("Invalid i915_gem_gtt_insert(.size=%llx, .alignment=%llx, .start=%llx, .end=%llx) succeeded (err=%d)\n",
          ii->size, ii->alignment, ii->start, ii->end,
          err);
   return -EINVAL;
  }
 }

 /* Start by filling the GGTT */
 for (total = 0;
      total + I915_GTT_PAGE_SIZE <= ggtt->vm.total;
      total += I915_GTT_PAGE_SIZE) {
  struct i915_vma *vma;

  obj = i915_gem_object_create_internal(ggtt->vm.i915,
            I915_GTT_PAGE_SIZE);
  if (IS_ERR(obj)) {
   err = PTR_ERR(obj);
   goto out;
  }

  err = i915_gem_object_pin_pages_unlocked(obj);
  if (err) {
   i915_gem_object_put(obj);
   goto out;
  }

  list_add(&obj->st_link, &objects);

  vma = i915_vma_instance(obj, &ggtt->vm, NULL);
  if (IS_ERR(vma)) {
   err = PTR_ERR(vma);
   goto out;
  }

  err = insert_gtt_with_resource(vma);
  if (err == -ENOSPC) {
   /* maxed out the GGTT space */
   i915_gem_object_put(obj);
   break;
  }
  if (err) {
   pr_err("i915_gem_gtt_insert (pass 1) failed at %llu/%llu with err=%d\n",
          total, ggtt->vm.total, err);
   goto out;
  }
  track_vma_bind(vma);
  __i915_vma_pin(vma);

  GEM_BUG_ON(!drm_mm_node_allocated(&vma->node));
 }

 list_for_each_entry(obj, &objects, st_link) {
  struct i915_vma *vma;

  vma = i915_vma_instance(obj, &ggtt->vm, NULL);
  if (IS_ERR(vma)) {
   err = PTR_ERR(vma);
   goto out;
  }

  if (!drm_mm_node_allocated(&vma->node)) {
   pr_err("VMA was unexpectedly evicted!\n");
   err = -EINVAL;
   goto out;
  }

  __i915_vma_unpin(vma);
 }

 /* If we then reinsert, we should find the same hole */
 list_for_each_entry_safe(obj, on, &objects, st_link) {
  struct i915_vma *vma;
  u64 offset;

  vma = i915_vma_instance(obj, &ggtt->vm, NULL);
  if (IS_ERR(vma)) {
   err = PTR_ERR(vma);
   goto out;
  }

  GEM_BUG_ON(!drm_mm_node_allocated(&vma->node));
  offset = vma->node.start;

  err = i915_vma_unbind_unlocked(vma);
  if (err) {
   pr_err("i915_vma_unbind failed with err=%d!\n", err);
   goto out;
  }

  err = insert_gtt_with_resource(vma);
  if (err) {
   pr_err("i915_gem_gtt_insert (pass 2) failed at %llu/%llu with err=%d\n",
          total, ggtt->vm.total, err);
   goto out;
  }
  track_vma_bind(vma);

  GEM_BUG_ON(!drm_mm_node_allocated(&vma->node));
  if (vma->node.start != offset) {
   pr_err("i915_gem_gtt_insert did not return node to its previous location (the only hole), expected address %llx, found %llx\n",
          offset, vma->node.start);
   err = -EINVAL;
   goto out;
  }
 }

 /* And then force evictions */
 for (total = 0;
      total + 2 * I915_GTT_PAGE_SIZE <= ggtt->vm.total;
      total += 2 * I915_GTT_PAGE_SIZE) {
  struct i915_vma *vma;

  obj = i915_gem_object_create_internal(ggtt->vm.i915,
            2 * I915_GTT_PAGE_SIZE);
  if (IS_ERR(obj)) {
   err = PTR_ERR(obj);
   goto out;
  }

  err = i915_gem_object_pin_pages_unlocked(obj);
  if (err) {
   i915_gem_object_put(obj);
   goto out;
  }

  list_add(&obj->st_link, &objects);

  vma = i915_vma_instance(obj, &ggtt->vm, NULL);
  if (IS_ERR(vma)) {
   err = PTR_ERR(vma);
   goto out;
  }

  err = insert_gtt_with_resource(vma);
  if (err) {
   pr_err("i915_gem_gtt_insert (pass 3) failed at %llu/%llu with err=%d\n",
          total, ggtt->vm.total, err);
   goto out;
  }
  track_vma_bind(vma);

  GEM_BUG_ON(!drm_mm_node_allocated(&vma->node));
 }

out:
 list_for_each_entry_safe(obj, on, &objects, st_link) {
  i915_gem_object_unpin_pages(obj);
  i915_gem_object_put(obj);
 }
 return err;
}

int i915_gem_gtt_mock_selftests(void)
{
 static const struct i915_subtest tests[] = {
  SUBTEST(igt_mock_drunk),
  SUBTEST(igt_mock_walk),
  SUBTEST(igt_mock_pot),
  SUBTEST(igt_mock_fill),
  SUBTEST(igt_gtt_reserve),
  SUBTEST(igt_gtt_insert),
 };
 struct drm_i915_private *i915;
 struct intel_gt *gt;
 int err;

 i915 = mock_gem_device();
 if (!i915)
  return -ENOMEM;

 /* allocate the ggtt */
 err = intel_gt_assign_ggtt(to_gt(i915));
 if (err)
  goto out_put;

 gt = to_gt(i915);

 mock_init_ggtt(gt);

 err = i915_subtests(tests, gt->ggtt);

 mock_device_flush(i915);
 i915_gem_drain_freed_objects(i915);
 mock_fini_ggtt(gt->ggtt);

out_put:
 mock_destroy_device(i915);
 return err;
}

int i915_gem_gtt_live_selftests(struct drm_i915_private *i915)
{
 static const struct i915_subtest tests[] = {
  SUBTEST(igt_ppgtt_alloc),
  SUBTEST(igt_ppgtt_lowlevel),
  SUBTEST(igt_ppgtt_drunk),
  SUBTEST(igt_ppgtt_walk),
  SUBTEST(igt_ppgtt_pot),
  SUBTEST(igt_ppgtt_fill),
  SUBTEST(igt_ppgtt_shrink),
  SUBTEST(igt_ppgtt_shrink_boom),
  SUBTEST(igt_ppgtt_misaligned_pin),
  SUBTEST(igt_ggtt_lowlevel),
  SUBTEST(igt_ggtt_drunk),
  SUBTEST(igt_ggtt_walk),
  SUBTEST(igt_ggtt_pot),
  SUBTEST(igt_ggtt_fill),
  SUBTEST(igt_ggtt_page),
  SUBTEST(igt_ggtt_misaligned_pin),
 };

 GEM_BUG_ON(offset_in_page(to_gt(i915)->ggtt->vm.total));

 return i915_live_subtests(tests, i915);
}