Compute the minimal required hole during scan and only evict those nodes
that overlap. This enables us to reduce the number of nodes we need to
evict to the bare minimum.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-31-chris@chris-wilson.co.uk

The scan state occupies a large proportion of the struct drm_mm and is
rarely used and only contains temporary state. That makes it suitable to
moving to its struct and onto the stack of the callers.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
[danvet: Fix up etnaviv to compile, was missing a BUG_ON.]
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>

In places (e.g. i915.ko), the alignment is exported to userspace as u64
and there now exists hardware for which we can indeed utilize a u64
alignment. As such, we need to keep 64bit integers throughout when
handling alignment.

Testcase: igt/drm_mm/align64
Testcase: igt/gem_exec_alignment
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Cc: Christian König <christian.koenig@amd.com>
Reviewed-by: NChristian König <christian.koenig@amd.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-22-chris@chris-wilson.co.uk

Check that after applying the driver's color adjustment, restricted
eviction scanning finds a suitable hole.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-20-chris@chris-wilson.co.uk

Check that after applying the driver's color adjustment, eviction
scanning finds a suitable hole.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-19-chris@chris-wilson.co.uk

Check that after applying the driver's color adjustment, fitting of the
node and its alignment are still correct.

v2: s/no_color_touching/separate_adjacent_colors/
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-18-chris@chris-wilson.co.uk

Check that if we request top-down allocation from drm_mm_insert_node()
we receive the next available hole from the top.

v2: Flip sign on conditional assert.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-17-chris@chris-wilson.co.uk

Check that we add arbitrary blocks to a restrited eviction scanner in
order to find the first minimal hole that matches our request.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-16-chris@chris-wilson.co.uk

Check that we add arbitrary blocks to the eviction scanner in order to
find the first minimal hole that matches our request.

v2: Refactor out some common eviction code for later
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-15-chris@chris-wilson.co.uk

Check that we can request alignment to any power-of-two or prime using a
plain drm_mm_node_insert(), and also handle a reasonable selection of
primes.

v2: Exercise all allocation flags
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-14-chris@chris-wilson.co.uk

Exercise drm_mm_insert_node_in_range(), check that we only allocate from
the specified range.

v2: Use all allocation flags
v3: Don't pass in invalid ranges - these will be asserted later.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-13-chris@chris-wilson.co.uk

Reuse drm_mm_insert_node() with a temporary node to exercise
drm_mm_replace_node(). We use the previous test in order to exercise the
various lists following replacement.

v2: Check that we copy across the important (user) details of the node.
The internal details (such as lists and hole tracking) we hope to detect
errors by exercise.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-12-chris@chris-wilson.co.uk

Exercise drm_mm_insert_node(), check that we can't overfill a range and
that the lists are correct after reserving/removing.

v2: Extract helpers for the repeated tests
v3: Iterate over all allocation flags
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-11-chris@chris-wilson.co.uk

Exercise drm_mm_reserve_node(), check that we can't reserve an already
occupied range and that the lists are correct after reserving/removing.

v2: Check for invalid node reservation.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-10-chris@chris-wilson.co.uk

Simple test to just exercise calling the debug dumper on the drm_mm.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-9-chris@chris-wilson.co.uk

Simple first test to just exercise initialisation of struct drm_mm.
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-8-chris@chris-wilson.co.uk

First we introduce a smattering of infrastructure for writing selftests.
The idea is that we have a test module that exercises a particular
portion of the exported API, and that module provides a set of tests
that can either be run as an ensemble via kselftest or individually via
an igt harness (in this case igt/drm_mm). To accommodate selecting
individual tests, we export a boolean parameter to control selection of
each test - that is hidden inside a bunch of reusable boilerplate macros
to keep writing the tests simple.

v2: Choose a random random_seed unless one is specified by the user.
v3: More parameters to control max_iterations and max_prime of the
tests.

Testcase: igt/drm_mm
Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
Acked-by: NChristian König <christian.koenig@amd.com>
Reviewed-by: NJoonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-7-chris@chris-wilson.co.uk