From 50f0033d1a0f3a8e9eed09ab68067fbb57b0669d Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 22 Dec 2016 08:36:09 +0000
Subject: drm: Add some kselftests for the DRM range manager (struct drm_mm)
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

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: Chris Wilson <chris@chris-wilson.co.uk>
Acked-by: Christian König <christian.koenig@amd.com>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-7-chris@chris-wilson.co.uk
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 58 +++++++++++++++++++++++++++++++++
 1 file changed, 58 insertions(+)
 create mode 100644 drivers/gpu/drm/selftests/test-drm_mm.c

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
new file mode 100644
index 000000000000..682f5f86f465
--- /dev/null
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -0,0 +1,58 @@
+/*
+ * Test cases for the drm_mm range manager
+ */
+
+#define pr_fmt(fmt) "drm_mm: " fmt
+
+#include <linux/module.h>
+#include <linux/prime_numbers.h>
+#include <linux/slab.h>
+#include <linux/random.h>
+#include <linux/vmalloc.h>
+
+#include <drm/drm_mm.h>
+
+#include "../lib/drm_random.h"
+
+#define TESTS "drm_mm_selftests.h"
+#include "drm_selftest.h"
+
+static unsigned int random_seed;
+static unsigned int max_iterations = 8192;
+static unsigned int max_prime = 128;
+
+static int igt_sanitycheck(void *ignored)
+{
+	pr_info("%s - ok!\n", __func__);
+	return 0;
+}
+
+#include "drm_selftest.c"
+
+static int __init test_drm_mm_init(void)
+{
+	int err;
+
+	while (!random_seed)
+		random_seed = get_random_int();
+
+	pr_info("Testing DRM range manger (struct drm_mm), with random_seed=0x%x max_iterations=%u max_prime=%u\n",
+		random_seed, max_iterations, max_prime);
+	err = run_selftests(selftests, ARRAY_SIZE(selftests), NULL);
+
+	return err > 0 ? 0 : err;
+}
+
+static void __exit test_drm_mm_exit(void)
+{
+}
+
+module_init(test_drm_mm_init);
+module_exit(test_drm_mm_exit);
+
+module_param(random_seed, uint, 0400);
+module_param(max_iterations, uint, 0400);
+module_param(max_prime, uint, 0400);
+
+MODULE_AUTHOR("Intel Corporation");
+MODULE_LICENSE("GPL");
-- 
cgit 


From 393b50f30566ba596bcd3e94ce6d59af4f184025 Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 22 Dec 2016 08:36:10 +0000
Subject: drm: kselftest for drm_mm_init()

Simple first test to just exercise initialisation of struct drm_mm.

Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-8-chris@chris-wilson.co.uk
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 114 ++++++++++++++++++++++++++++++++
 1 file changed, 114 insertions(+)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index 682f5f86f465..87ad147670da 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -27,6 +27,120 @@ static int igt_sanitycheck(void *ignored)
 	return 0;
 }
 
+static bool assert_no_holes(const struct drm_mm *mm)
+{
+	struct drm_mm_node *hole;
+	u64 hole_start, hole_end;
+	unsigned long count;
+
+	count = 0;
+	drm_mm_for_each_hole(hole, mm, hole_start, hole_end)
+		count++;
+	if (count) {
+		pr_err("Expected to find no holes (after reserve), found %lu instead\n", count);
+		return false;
+	}
+
+	drm_mm_for_each_node(hole, mm) {
+		if (hole->hole_follows) {
+			pr_err("Hole follows node, expected none!\n");
+			return false;
+		}
+	}
+
+	return true;
+}
+
+static bool assert_one_hole(const struct drm_mm *mm, u64 start, u64 end)
+{
+	struct drm_mm_node *hole;
+	u64 hole_start, hole_end;
+	unsigned long count;
+	bool ok = true;
+
+	if (end <= start)
+		return true;
+
+	count = 0;
+	drm_mm_for_each_hole(hole, mm, hole_start, hole_end) {
+		if (start != hole_start || end != hole_end) {
+			if (ok)
+				pr_err("empty mm has incorrect hole, found (%llx, %llx), expect (%llx, %llx)\n",
+				       hole_start, hole_end,
+				       start, end);
+			ok = false;
+		}
+		count++;
+	}
+	if (count != 1) {
+		pr_err("Expected to find one hole, found %lu instead\n", count);
+		ok = false;
+	}
+
+	return ok;
+}
+
+static int igt_init(void *ignored)
+{
+	const unsigned int size = 4096;
+	struct drm_mm mm;
+	struct drm_mm_node tmp;
+	int ret = -EINVAL;
+
+	/* Start with some simple checks on initialising the struct drm_mm */
+	memset(&mm, 0, sizeof(mm));
+	if (drm_mm_initialized(&mm)) {
+		pr_err("zeroed mm claims to be initialized\n");
+		return ret;
+	}
+
+	memset(&mm, 0xff, sizeof(mm));
+	drm_mm_init(&mm, 0, size);
+	if (!drm_mm_initialized(&mm)) {
+		pr_err("mm claims not to be initialized\n");
+		goto out;
+	}
+
+	if (!drm_mm_clean(&mm)) {
+		pr_err("mm not empty on creation\n");
+		goto out;
+	}
+
+	/* After creation, it should all be one massive hole */
+	if (!assert_one_hole(&mm, 0, size)) {
+		ret = -EINVAL;
+		goto out;
+	}
+
+	memset(&tmp, 0, sizeof(tmp));
+	tmp.start = 0;
+	tmp.size = size;
+	ret = drm_mm_reserve_node(&mm, &tmp);
+	if (ret) {
+		pr_err("failed to reserve whole drm_mm\n");
+		goto out;
+	}
+
+	/* After filling the range entirely, there should be no holes */
+	if (!assert_no_holes(&mm)) {
+		ret = -EINVAL;
+		goto out;
+	}
+
+	/* And then after emptying it again, the massive hole should be back */
+	drm_mm_remove_node(&tmp);
+	if (!assert_one_hole(&mm, 0, size)) {
+		ret = -EINVAL;
+		goto out;
+	}
+
+out:
+	if (ret)
+		drm_mm_debug_table(&mm, __func__);
+	drm_mm_takedown(&mm);
+	return ret;
+}
+
 #include "drm_selftest.c"
 
 static int __init test_drm_mm_init(void)
-- 
cgit 


From 06df8ac682e6a00e6e32d105208953ca5323cc82 Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 22 Dec 2016 08:36:11 +0000
Subject: drm: kselftest for drm_mm_debug()

Simple test to just exercise calling the debug dumper on the drm_mm.

Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-9-chris@chris-wilson.co.uk
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 35 +++++++++++++++++++++++++++++++++
 1 file changed, 35 insertions(+)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index 87ad147670da..434320061d9e 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -141,6 +141,41 @@ out:
 	return ret;
 }
 
+static int igt_debug(void *ignored)
+{
+	struct drm_mm mm;
+	struct drm_mm_node nodes[2];
+	int ret;
+
+	/* Create a small drm_mm with a couple of nodes and a few holes, and
+	 * check that the debug iterator doesn't explode over a trivial drm_mm.
+	 */
+
+	drm_mm_init(&mm, 0, 4096);
+
+	memset(nodes, 0, sizeof(nodes));
+	nodes[0].start = 512;
+	nodes[0].size = 1024;
+	ret = drm_mm_reserve_node(&mm, &nodes[0]);
+	if (ret) {
+		pr_err("failed to reserve node[0] {start=%lld, size=%lld)\n",
+		       nodes[0].start, nodes[0].size);
+		return ret;
+	}
+
+	nodes[1].size = 1024;
+	nodes[1].start = 4096 - 512 - nodes[1].size;
+	ret = drm_mm_reserve_node(&mm, &nodes[1]);
+	if (ret) {
+		pr_err("failed to reserve node[1] {start=%lld, size=%lld)\n",
+		       nodes[1].start, nodes[1].size);
+		return ret;
+	}
+
+	drm_mm_debug_table(&mm, __func__);
+	return 0;
+}
+
 #include "drm_selftest.c"
 
 static int __init test_drm_mm_init(void)
-- 
cgit 


From 900537dc388940f7f0c775e65fbf070f0d8eba9c Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 22 Dec 2016 08:36:12 +0000
Subject: drm: kselftest for drm_mm_reserve_node()

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: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-10-chris@chris-wilson.co.uk
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 275 ++++++++++++++++++++++++++++++++
 1 file changed, 275 insertions(+)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index 434320061d9e..789a810d66aa 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -80,6 +80,57 @@ static bool assert_one_hole(const struct drm_mm *mm, u64 start, u64 end)
 	return ok;
 }
 
+static bool assert_continuous(const struct drm_mm *mm, u64 size)
+{
+	struct drm_mm_node *node, *check, *found;
+	unsigned long n;
+	u64 addr;
+
+	if (!assert_no_holes(mm))
+		return false;
+
+	n = 0;
+	addr = 0;
+	drm_mm_for_each_node(node, mm) {
+		if (node->start != addr) {
+			pr_err("node[%ld] list out of order, expected %llx found %llx\n",
+			       n, addr, node->start);
+			return false;
+		}
+
+		if (node->size != size) {
+			pr_err("node[%ld].size incorrect, expected %llx, found %llx\n",
+			       n, size, node->size);
+			return false;
+		}
+
+		if (node->hole_follows) {
+			pr_err("node[%ld] is followed by a hole!\n", n);
+			return false;
+		}
+
+		found = NULL;
+		drm_mm_for_each_node_in_range(check, mm, addr, addr + size) {
+			if (node != check) {
+				pr_err("lookup return wrong node, expected start %llx, found %llx\n",
+				       node->start, check->start);
+				return false;
+			}
+			found = check;
+		}
+		if (!found) {
+			pr_err("lookup failed for node %llx + %llx\n",
+			       addr, size);
+			return false;
+		}
+
+		addr += size;
+		n++;
+	}
+
+	return true;
+}
+
 static int igt_init(void *ignored)
 {
 	const unsigned int size = 4096;
@@ -176,6 +227,230 @@ static int igt_debug(void *ignored)
 	return 0;
 }
 
+static struct drm_mm_node *set_node(struct drm_mm_node *node,
+				    u64 start, u64 size)
+{
+	node->start = start;
+	node->size = size;
+	return node;
+}
+
+static bool expect_reserve_fail(struct drm_mm *mm, struct drm_mm_node *node)
+{
+	int err;
+
+	err = drm_mm_reserve_node(mm, node);
+	if (likely(err == -ENOSPC))
+		return true;
+
+	if (!err) {
+		pr_err("impossible reserve succeeded, node %llu + %llu\n",
+		       node->start, node->size);
+		drm_mm_remove_node(node);
+	} else {
+		pr_err("impossible reserve failed with wrong error %d [expected %d], node %llu + %llu\n",
+		       err, -ENOSPC, node->start, node->size);
+	}
+	return false;
+}
+
+static bool check_reserve_boundaries(struct drm_mm *mm,
+				     unsigned int count,
+				     u64 size)
+{
+	const struct boundary {
+		u64 start, size;
+		const char *name;
+	} boundaries[] = {
+#define B(st, sz) { (st), (sz), "{ " #st ", " #sz "}" }
+		B(0, 0),
+		B(-size, 0),
+		B(size, 0),
+		B(size * count, 0),
+		B(-size, size),
+		B(-size, -size),
+		B(-size, 2*size),
+		B(0, -size),
+		B(size, -size),
+		B(count*size, size),
+		B(count*size, -size),
+		B(count*size, count*size),
+		B(count*size, -count*size),
+		B(count*size, -(count+1)*size),
+		B((count+1)*size, size),
+		B((count+1)*size, -size),
+		B((count+1)*size, -2*size),
+#undef B
+	};
+	struct drm_mm_node tmp = {};
+	int n;
+
+	for (n = 0; n < ARRAY_SIZE(boundaries); n++) {
+		if (!expect_reserve_fail(mm,
+					 set_node(&tmp,
+						  boundaries[n].start,
+						  boundaries[n].size))) {
+			pr_err("boundary[%d:%s] failed, count=%u, size=%lld\n",
+			       n, boundaries[n].name, count, size);
+			return false;
+		}
+	}
+
+	return true;
+}
+
+static int __igt_reserve(unsigned int count, u64 size)
+{
+	DRM_RND_STATE(prng, random_seed);
+	struct drm_mm mm;
+	struct drm_mm_node tmp, *nodes, *node, *next;
+	unsigned int *order, n, m, o = 0;
+	int ret, err;
+
+	/* For exercising drm_mm_reserve_node(), we want to check that
+	 * reservations outside of the drm_mm range are rejected, and to
+	 * overlapping and otherwise already occupied ranges. Afterwards,
+	 * the tree and nodes should be intact.
+	 */
+
+	DRM_MM_BUG_ON(!count);
+	DRM_MM_BUG_ON(!size);
+
+	ret = -ENOMEM;
+	order = drm_random_order(count, &prng);
+	if (!order)
+		goto err;
+
+	nodes = vzalloc(sizeof(*nodes) * count);
+	if (!nodes)
+		goto err_order;
+
+	ret = -EINVAL;
+	drm_mm_init(&mm, 0, count * size);
+
+	if (!check_reserve_boundaries(&mm, count, size))
+		goto out;
+
+	for (n = 0; n < count; n++) {
+		nodes[n].start = order[n] * size;
+		nodes[n].size = size;
+
+		err = drm_mm_reserve_node(&mm, &nodes[n]);
+		if (err) {
+			pr_err("reserve failed, step %d, start %llu\n",
+			       n, nodes[n].start);
+			ret = err;
+			goto out;
+		}
+
+		if (!drm_mm_node_allocated(&nodes[n])) {
+			pr_err("reserved node not allocated! step %d, start %llu\n",
+			       n, nodes[n].start);
+			goto out;
+		}
+
+		if (!expect_reserve_fail(&mm, &nodes[n]))
+			goto out;
+	}
+
+	/* After random insertion the nodes should be in order */
+	if (!assert_continuous(&mm, size))
+		goto out;
+
+	/* Repeated use should then fail */
+	drm_random_reorder(order, count, &prng);
+	for (n = 0; n < count; n++) {
+		if (!expect_reserve_fail(&mm,
+					 set_node(&tmp, order[n] * size, 1)))
+			goto out;
+
+		/* Remove and reinsert should work */
+		drm_mm_remove_node(&nodes[order[n]]);
+		err = drm_mm_reserve_node(&mm, &nodes[order[n]]);
+		if (err) {
+			pr_err("reserve failed, step %d, start %llu\n",
+			       n, nodes[n].start);
+			ret = err;
+			goto out;
+		}
+	}
+
+	if (!assert_continuous(&mm, size))
+		goto out;
+
+	/* Overlapping use should then fail */
+	for (n = 0; n < count; n++) {
+		if (!expect_reserve_fail(&mm, set_node(&tmp, 0, size*count)))
+			goto out;
+	}
+	for (n = 0; n < count; n++) {
+		if (!expect_reserve_fail(&mm,
+					 set_node(&tmp,
+						  size * n,
+						  size * (count - n))))
+			goto out;
+	}
+
+	/* Remove several, reinsert, check full */
+	for_each_prime_number(n, min(max_prime, count)) {
+		for (m = 0; m < n; m++) {
+			node = &nodes[order[(o + m) % count]];
+			drm_mm_remove_node(node);
+		}
+
+		for (m = 0; m < n; m++) {
+			node = &nodes[order[(o + m) % count]];
+			err = drm_mm_reserve_node(&mm, node);
+			if (err) {
+				pr_err("reserve failed, step %d/%d, start %llu\n",
+				       m, n, node->start);
+				ret = err;
+				goto out;
+			}
+		}
+
+		o += n;
+
+		if (!assert_continuous(&mm, size))
+			goto out;
+	}
+
+	ret = 0;
+out:
+	drm_mm_for_each_node_safe(node, next, &mm)
+		drm_mm_remove_node(node);
+	drm_mm_takedown(&mm);
+	vfree(nodes);
+err_order:
+	kfree(order);
+err:
+	return ret;
+}
+
+static int igt_reserve(void *ignored)
+{
+	const unsigned int count = min_t(unsigned int, BIT(10), max_iterations);
+	int n, ret;
+
+	for_each_prime_number_from(n, 1, 54) {
+		u64 size = BIT_ULL(n);
+
+		ret = __igt_reserve(count, size - 1);
+		if (ret)
+			return ret;
+
+		ret = __igt_reserve(count, size);
+		if (ret)
+			return ret;
+
+		ret = __igt_reserve(count, size + 1);
+		if (ret)
+			return ret;
+	}
+
+	return 0;
+}
+
 #include "drm_selftest.c"
 
 static int __init test_drm_mm_init(void)
-- 
cgit 


From 7886692a58045c5e6953c2efb742bb389d31484d Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 22 Dec 2016 08:36:13 +0000
Subject: drm: kselftest for drm_mm_insert_node()

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: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-11-chris@chris-wilson.co.uk
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 234 ++++++++++++++++++++++++++++++++
 1 file changed, 234 insertions(+)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index 789a810d66aa..feb5985abdc2 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -21,6 +21,23 @@ static unsigned int random_seed;
 static unsigned int max_iterations = 8192;
 static unsigned int max_prime = 128;
 
+enum {
+	DEFAULT,
+	TOPDOWN,
+	BEST,
+};
+
+static const struct insert_mode {
+	const char *name;
+	unsigned int search_flags;
+	unsigned int create_flags;
+} insert_modes[] = {
+	[DEFAULT] = { "default", DRM_MM_SEARCH_DEFAULT, DRM_MM_CREATE_DEFAULT },
+	[TOPDOWN] = { "top-down", DRM_MM_SEARCH_BELOW, DRM_MM_CREATE_TOP },
+	[BEST] = { "best", DRM_MM_SEARCH_BEST, DRM_MM_CREATE_DEFAULT },
+	{}
+};
+
 static int igt_sanitycheck(void *ignored)
 {
 	pr_info("%s - ok!\n", __func__);
@@ -131,6 +148,48 @@ static bool assert_continuous(const struct drm_mm *mm, u64 size)
 	return true;
 }
 
+static u64 misalignment(struct drm_mm_node *node, u64 alignment)
+{
+	u64 rem;
+
+	if (!alignment)
+		return 0;
+
+	div64_u64_rem(node->start, alignment, &rem);
+	return rem;
+}
+
+static bool assert_node(struct drm_mm_node *node, struct drm_mm *mm,
+			u64 size, u64 alignment, unsigned long color)
+{
+	bool ok = true;
+
+	if (!drm_mm_node_allocated(node) || node->mm != mm) {
+		pr_err("node not allocated\n");
+		ok = false;
+	}
+
+	if (node->size != size) {
+		pr_err("node has wrong size, found %llu, expected %llu\n",
+		       node->size, size);
+		ok = false;
+	}
+
+	if (misalignment(node, alignment)) {
+		pr_err("node is misalinged, start %llx rem %llu, expected alignment %llu\n",
+		       node->start, misalignment(node, alignment), alignment);
+		ok = false;
+	}
+
+	if (node->color != color) {
+		pr_err("node has wrong color, found %lu, expected %lu\n",
+		       node->color, color);
+		ok = false;
+	}
+
+	return ok;
+}
+
 static int igt_init(void *ignored)
 {
 	const unsigned int size = 4096;
@@ -451,6 +510,181 @@ static int igt_reserve(void *ignored)
 	return 0;
 }
 
+static bool expect_insert(struct drm_mm *mm, struct drm_mm_node *node,
+			  u64 size, u64 alignment, unsigned long color,
+			  const struct insert_mode *mode)
+{
+	int err;
+
+	err = drm_mm_insert_node_generic(mm, node,
+					 size, alignment, color,
+					 mode->search_flags,
+					 mode->create_flags);
+	if (err) {
+		pr_err("insert (size=%llu, alignment=%llu, color=%lu, mode=%s) failed with err=%d\n",
+		       size, alignment, color, mode->name, err);
+		return false;
+	}
+
+	if (!assert_node(node, mm, size, alignment, color)) {
+		drm_mm_remove_node(node);
+		return false;
+	}
+
+	return true;
+}
+
+static bool expect_insert_fail(struct drm_mm *mm, u64 size)
+{
+	struct drm_mm_node tmp = {};
+	int err;
+
+	err = drm_mm_insert_node(mm, &tmp, size, 0, DRM_MM_SEARCH_DEFAULT);
+	if (likely(err == -ENOSPC))
+		return true;
+
+	if (!err) {
+		pr_err("impossible insert succeeded, node %llu + %llu\n",
+		       tmp.start, tmp.size);
+		drm_mm_remove_node(&tmp);
+	} else {
+		pr_err("impossible insert failed with wrong error %d [expected %d], size %llu\n",
+		       err, -ENOSPC, size);
+	}
+	return false;
+}
+
+static int __igt_insert(unsigned int count, u64 size)
+{
+	DRM_RND_STATE(prng, random_seed);
+	const struct insert_mode *mode;
+	struct drm_mm mm;
+	struct drm_mm_node *nodes, *node, *next;
+	unsigned int *order, n, m, o = 0;
+	int ret;
+
+	/* Fill a range with lots of nodes, check it doesn't fail too early */
+
+	DRM_MM_BUG_ON(!count);
+	DRM_MM_BUG_ON(!size);
+
+	ret = -ENOMEM;
+	nodes = vzalloc(count * sizeof(*nodes));
+	if (!nodes)
+		goto err;
+
+	order = drm_random_order(count, &prng);
+	if (!order)
+		goto err_nodes;
+
+	ret = -EINVAL;
+	drm_mm_init(&mm, 0, count * size);
+
+	for (mode = insert_modes; mode->name; mode++) {
+		for (n = 0; n < count; n++) {
+			if (!expect_insert(&mm, &nodes[n], size, 0, n, mode)) {
+				pr_err("%s insert failed, size %llu step %d\n",
+				       mode->name, size, n);
+				goto out;
+			}
+		}
+
+		/* After random insertion the nodes should be in order */
+		if (!assert_continuous(&mm, size))
+			goto out;
+
+		/* Repeated use should then fail */
+		if (!expect_insert_fail(&mm, size))
+			goto out;
+
+		/* Remove one and reinsert, as the only hole it should refill itself */
+		for (n = 0; n < count; n++) {
+			u64 addr = nodes[n].start;
+
+			drm_mm_remove_node(&nodes[n]);
+			if (!expect_insert(&mm, &nodes[n], size, 0, n, mode)) {
+				pr_err("%s reinsert failed, size %llu step %d\n",
+				       mode->name, size, n);
+				goto out;
+			}
+
+			if (nodes[n].start != addr) {
+				pr_err("%s reinsert node moved, step %d, expected %llx, found %llx\n",
+				       mode->name, n, addr, nodes[n].start);
+				goto out;
+			}
+
+			if (!assert_continuous(&mm, size))
+				goto out;
+		}
+
+		/* Remove several, reinsert, check full */
+		for_each_prime_number(n, min(max_prime, count)) {
+			for (m = 0; m < n; m++) {
+				node = &nodes[order[(o + m) % count]];
+				drm_mm_remove_node(node);
+			}
+
+			for (m = 0; m < n; m++) {
+				node = &nodes[order[(o + m) % count]];
+				if (!expect_insert(&mm, node, size, 0, n, mode)) {
+					pr_err("%s multiple reinsert failed, size %llu step %d\n",
+					       mode->name, size, n);
+					goto out;
+				}
+			}
+
+			o += n;
+
+			if (!assert_continuous(&mm, size))
+				goto out;
+
+			if (!expect_insert_fail(&mm, size))
+				goto out;
+		}
+
+		drm_mm_for_each_node_safe(node, next, &mm)
+			drm_mm_remove_node(node);
+		DRM_MM_BUG_ON(!drm_mm_clean(&mm));
+	}
+
+	ret = 0;
+out:
+	drm_mm_for_each_node_safe(node, next, &mm)
+		drm_mm_remove_node(node);
+	drm_mm_takedown(&mm);
+	kfree(order);
+err_nodes:
+	vfree(nodes);
+err:
+	return ret;
+}
+
+static int igt_insert(void *ignored)
+{
+	const unsigned int count = min_t(unsigned int, BIT(10), max_iterations);
+	unsigned int n;
+	int ret;
+
+	for_each_prime_number_from(n, 1, 54) {
+		u64 size = BIT_ULL(n);
+
+		ret = __igt_insert(count, size - 1);
+		if (ret)
+			return ret;
+
+		ret = __igt_insert(count, size);
+		if (ret)
+			return ret;
+
+		ret = __igt_insert(count, size + 1);
+		if (ret)
+			return ret;
+	}
+
+	return 0;
+}
+
 #include "drm_selftest.c"
 
 static int __init test_drm_mm_init(void)
-- 
cgit 


From 2bd966d106e34e2daedad8eb109d48825ba8b655 Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 22 Dec 2016 08:36:14 +0000
Subject: drm: kselftest for drm_mm_replace_node()

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: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-12-chris@chris-wilson.co.uk
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 65 ++++++++++++++++++++++++++++++---
 1 file changed, 59 insertions(+), 6 deletions(-)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index feb5985abdc2..7914428c9862 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -554,7 +554,7 @@ static bool expect_insert_fail(struct drm_mm *mm, u64 size)
 	return false;
 }
 
-static int __igt_insert(unsigned int count, u64 size)
+static int __igt_insert(unsigned int count, u64 size, bool replace)
 {
 	DRM_RND_STATE(prng, random_seed);
 	const struct insert_mode *mode;
@@ -569,7 +569,7 @@ static int __igt_insert(unsigned int count, u64 size)
 	DRM_MM_BUG_ON(!size);
 
 	ret = -ENOMEM;
-	nodes = vzalloc(count * sizeof(*nodes));
+	nodes = vmalloc(count * sizeof(*nodes));
 	if (!nodes)
 		goto err;
 
@@ -582,11 +582,37 @@ static int __igt_insert(unsigned int count, u64 size)
 
 	for (mode = insert_modes; mode->name; mode++) {
 		for (n = 0; n < count; n++) {
-			if (!expect_insert(&mm, &nodes[n], size, 0, n, mode)) {
+			struct drm_mm_node tmp;
+
+			node = replace ? &tmp : &nodes[n];
+			memset(node, 0, sizeof(*node));
+			if (!expect_insert(&mm, node, size, 0, n, mode)) {
 				pr_err("%s insert failed, size %llu step %d\n",
 				       mode->name, size, n);
 				goto out;
 			}
+
+			if (replace) {
+				drm_mm_replace_node(&tmp, &nodes[n]);
+				if (drm_mm_node_allocated(&tmp)) {
+					pr_err("replaced old-node still allocated! step %d\n",
+					       n);
+					goto out;
+				}
+
+				if (!assert_node(&nodes[n], &mm, size, 0, n)) {
+					pr_err("replaced node did not inherit parameters, size %llu step %d\n",
+					       size, n);
+					goto out;
+				}
+
+				if (tmp.start != nodes[n].start) {
+					pr_err("replaced node mismatch location expected [%llx + %llx], found [%llx + %llx]\n",
+					       tmp.start, size,
+					       nodes[n].start, nodes[n].size);
+					goto out;
+				}
+			}
 		}
 
 		/* After random insertion the nodes should be in order */
@@ -669,17 +695,44 @@ static int igt_insert(void *ignored)
 	for_each_prime_number_from(n, 1, 54) {
 		u64 size = BIT_ULL(n);
 
-		ret = __igt_insert(count, size - 1);
+		ret = __igt_insert(count, size - 1, false);
 		if (ret)
 			return ret;
 
-		ret = __igt_insert(count, size);
+		ret = __igt_insert(count, size, false);
 		if (ret)
 			return ret;
 
-		ret = __igt_insert(count, size + 1);
+		ret = __igt_insert(count, size + 1, false);
+	}
+
+	return 0;
+}
+
+static int igt_replace(void *ignored)
+{
+	const unsigned int count = min_t(unsigned int, BIT(10), max_iterations);
+	unsigned int n;
+	int ret;
+
+	/* Reuse igt_insert to exercise replacement by inserting a dummy node,
+	 * then replacing it with the intended node. We want to check that
+	 * the tree is intact and all the information we need is carried
+	 * across to the target node.
+	 */
+
+	for_each_prime_number_from(n, 1, 54) {
+		u64 size = BIT_ULL(n);
+
+		ret = __igt_insert(count, size - 1, true);
 		if (ret)
 			return ret;
+
+		ret = __igt_insert(count, size, true);
+		if (ret)
+			return ret;
+
+		ret = __igt_insert(count, size + 1, true);
 	}
 
 	return 0;
-- 
cgit 


From 2fba0de0a9eca81edb737025fece986d4dafa94a Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 22 Dec 2016 08:36:15 +0000
Subject: drm: kselftest for drm_mm_insert_node_in_range()

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: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-13-chris@chris-wilson.co.uk
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 269 ++++++++++++++++++++++++++++++++
 1 file changed, 269 insertions(+)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index 7914428c9862..afc9274d8086 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -738,6 +738,275 @@ static int igt_replace(void *ignored)
 	return 0;
 }
 
+static bool expect_insert_in_range(struct drm_mm *mm, struct drm_mm_node *node,
+				   u64 size, u64 alignment, unsigned long color,
+				   u64 range_start, u64 range_end,
+				   const struct insert_mode *mode)
+{
+	int err;
+
+	err = drm_mm_insert_node_in_range_generic(mm, node,
+						  size, alignment, color,
+						  range_start, range_end,
+						  mode->search_flags,
+						  mode->create_flags);
+	if (err) {
+		pr_err("insert (size=%llu, alignment=%llu, color=%lu, mode=%s) nto range [%llx, %llx] failed with err=%d\n",
+		       size, alignment, color, mode->name,
+		       range_start, range_end, err);
+		return false;
+	}
+
+	if (!assert_node(node, mm, size, alignment, color)) {
+		drm_mm_remove_node(node);
+		return false;
+	}
+
+	return true;
+}
+
+static bool expect_insert_in_range_fail(struct drm_mm *mm,
+					u64 size,
+					u64 range_start,
+					u64 range_end)
+{
+	struct drm_mm_node tmp = {};
+	int err;
+
+	err = drm_mm_insert_node_in_range_generic(mm, &tmp,
+						  size, 0, 0,
+						  range_start, range_end,
+						  DRM_MM_SEARCH_DEFAULT,
+						  DRM_MM_CREATE_DEFAULT);
+	if (likely(err == -ENOSPC))
+		return true;
+
+	if (!err) {
+		pr_err("impossible insert succeeded, node %llx + %llu, range [%llx, %llx]\n",
+		       tmp.start, tmp.size, range_start, range_end);
+		drm_mm_remove_node(&tmp);
+	} else {
+		pr_err("impossible insert failed with wrong error %d [expected %d], size %llu, range [%llx, %llx]\n",
+		       err, -ENOSPC, size, range_start, range_end);
+	}
+
+	return false;
+}
+
+static bool assert_contiguous_in_range(struct drm_mm *mm,
+				       u64 size,
+				       u64 start,
+				       u64 end)
+{
+	struct drm_mm_node *node;
+	unsigned int n;
+
+	if (!expect_insert_in_range_fail(mm, size, start, end))
+		return false;
+
+	n = div64_u64(start + size - 1, size);
+	drm_mm_for_each_node(node, mm) {
+		if (node->start < start || node->start + node->size > end) {
+			pr_err("node %d out of range, address [%llx + %llu], range [%llx, %llx]\n",
+			       n, node->start, node->start + node->size, start, end);
+			return false;
+		}
+
+		if (node->start != n * size) {
+			pr_err("node %d out of order, expected start %llx, found %llx\n",
+			       n, n * size, node->start);
+			return false;
+		}
+
+		if (node->size != size) {
+			pr_err("node %d has wrong size, expected size %llx, found %llx\n",
+			       n, size, node->size);
+			return false;
+		}
+
+		if (node->hole_follows && drm_mm_hole_node_end(node) < end) {
+			pr_err("node %d is followed by a hole!\n", n);
+			return false;
+		}
+
+		n++;
+	}
+
+	drm_mm_for_each_node_in_range(node, mm, 0, start) {
+		if (node) {
+			pr_err("node before start: node=%llx+%llu, start=%llx\n",
+			       node->start, node->size, start);
+			return false;
+		}
+	}
+
+	drm_mm_for_each_node_in_range(node, mm, end, U64_MAX) {
+		if (node) {
+			pr_err("node after end: node=%llx+%llu, end=%llx\n",
+			       node->start, node->size, end);
+			return false;
+		}
+	}
+
+	return true;
+}
+
+static int __igt_insert_range(unsigned int count, u64 size, u64 start, u64 end)
+{
+	const struct insert_mode *mode;
+	struct drm_mm mm;
+	struct drm_mm_node *nodes, *node, *next;
+	unsigned int n, start_n, end_n;
+	int ret;
+
+	DRM_MM_BUG_ON(!count);
+	DRM_MM_BUG_ON(!size);
+	DRM_MM_BUG_ON(end <= start);
+
+	/* Very similar to __igt_insert(), but now instead of populating the
+	 * full range of the drm_mm, we try to fill a small portion of it.
+	 */
+
+	ret = -ENOMEM;
+	nodes = vzalloc(count * sizeof(*nodes));
+	if (!nodes)
+		goto err;
+
+	ret = -EINVAL;
+	drm_mm_init(&mm, 0, count * size);
+
+	start_n = div64_u64(start + size - 1, size);
+	end_n = div64_u64(end - size, size);
+
+	for (mode = insert_modes; mode->name; mode++) {
+		for (n = start_n; n <= end_n; n++) {
+			if (!expect_insert_in_range(&mm, &nodes[n],
+						    size, size, n,
+						    start, end, mode)) {
+				pr_err("%s insert failed, size %llu, step %d [%d, %d], range [%llx, %llx]\n",
+				       mode->name, size, n,
+				       start_n, end_n,
+				       start, end);
+				goto out;
+			}
+		}
+
+		if (!assert_contiguous_in_range(&mm, size, start, end)) {
+			pr_err("%s: range [%llx, %llx] not full after initialisation, size=%llu\n",
+			       mode->name, start, end, size);
+			goto out;
+		}
+
+		/* Remove one and reinsert, it should refill itself */
+		for (n = start_n; n <= end_n; n++) {
+			u64 addr = nodes[n].start;
+
+			drm_mm_remove_node(&nodes[n]);
+			if (!expect_insert_in_range(&mm, &nodes[n],
+						    size, size, n,
+						    start, end, mode)) {
+				pr_err("%s reinsert failed, step %d\n", mode->name, n);
+				goto out;
+			}
+
+			if (nodes[n].start != addr) {
+				pr_err("%s reinsert node moved, step %d, expected %llx, found %llx\n",
+				       mode->name, n, addr, nodes[n].start);
+				goto out;
+			}
+		}
+
+		if (!assert_contiguous_in_range(&mm, size, start, end)) {
+			pr_err("%s: range [%llx, %llx] not full after reinsertion, size=%llu\n",
+			       mode->name, start, end, size);
+			goto out;
+		}
+
+		drm_mm_for_each_node_safe(node, next, &mm)
+			drm_mm_remove_node(node);
+		DRM_MM_BUG_ON(!drm_mm_clean(&mm));
+	}
+
+	ret = 0;
+out:
+	drm_mm_for_each_node_safe(node, next, &mm)
+		drm_mm_remove_node(node);
+	drm_mm_takedown(&mm);
+	vfree(nodes);
+err:
+	return ret;
+}
+
+static int insert_outside_range(void)
+{
+	struct drm_mm mm;
+	const unsigned int start = 1024;
+	const unsigned int end = 2048;
+	const unsigned int size = end - start;
+
+	drm_mm_init(&mm, start, size);
+
+	if (!expect_insert_in_range_fail(&mm, 1, 0, start))
+		return -EINVAL;
+
+	if (!expect_insert_in_range_fail(&mm, size,
+					 start - size/2, start + (size+1)/2))
+		return -EINVAL;
+
+	if (!expect_insert_in_range_fail(&mm, size,
+					 end - (size+1)/2, end + size/2))
+		return -EINVAL;
+
+	if (!expect_insert_in_range_fail(&mm, 1, end, end + size))
+		return -EINVAL;
+
+	drm_mm_takedown(&mm);
+	return 0;
+}
+
+static int igt_insert_range(void *ignored)
+{
+	const unsigned int count = min_t(unsigned int, BIT(13), max_iterations);
+	unsigned int n;
+	int ret;
+
+	/* Check that requests outside the bounds of drm_mm are rejected. */
+	ret = insert_outside_range();
+	if (ret)
+		return ret;
+
+	for_each_prime_number_from(n, 1, 50) {
+		const u64 size = BIT_ULL(n);
+		const u64 max = count * size;
+
+		ret = __igt_insert_range(count, size, 0, max);
+		if (ret)
+			return ret;
+
+		ret = __igt_insert_range(count, size, 1, max);
+		if (ret)
+			return ret;
+
+		ret = __igt_insert_range(count, size, 0, max - 1);
+		if (ret)
+			return ret;
+
+		ret = __igt_insert_range(count, size, 0, max/2);
+		if (ret)
+			return ret;
+
+		ret = __igt_insert_range(count, size, max/2, max);
+		if (ret)
+			return ret;
+
+		ret = __igt_insert_range(count, size, max/4+1, 3*max/4-1);
+		if (ret)
+			return ret;
+	}
+
+	return 0;
+}
+
 #include "drm_selftest.c"
 
 static int __init test_drm_mm_init(void)
-- 
cgit 


From 9b26f2ed29f862f89e68acbc2e75b640b59288f1 Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 22 Dec 2016 08:36:16 +0000
Subject: drm: kselftest for drm_mm and alignment

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: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-14-chris@chris-wilson.co.uk
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 103 ++++++++++++++++++++++++++++++++
 1 file changed, 103 insertions(+)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index afc9274d8086..53ba268e07d9 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -1007,6 +1007,109 @@ static int igt_insert_range(void *ignored)
 	return 0;
 }
 
+static int igt_align(void *ignored)
+{
+	const struct insert_mode *mode;
+	const unsigned int max_count = min(8192u, max_prime);
+	struct drm_mm mm;
+	struct drm_mm_node *nodes, *node, *next;
+	unsigned int prime;
+	int ret = -EINVAL;
+
+	/* For each of the possible insertion modes, we pick a few
+	 * arbitrary alignments and check that the inserted node
+	 * meets our requirements.
+	 */
+
+	nodes = vzalloc(max_count * sizeof(*nodes));
+	if (!nodes)
+		goto err;
+
+	drm_mm_init(&mm, 1, U64_MAX - 2);
+
+	for (mode = insert_modes; mode->name; mode++) {
+		unsigned int i = 0;
+
+		for_each_prime_number_from(prime, 1, max_count) {
+			u64 size = next_prime_number(prime);
+
+			if (!expect_insert(&mm, &nodes[i],
+					   size, prime, i,
+					   mode)) {
+				pr_err("%s insert failed with alignment=%d",
+				       mode->name, prime);
+				goto out;
+			}
+
+			i++;
+		}
+
+		drm_mm_for_each_node_safe(node, next, &mm)
+			drm_mm_remove_node(node);
+		DRM_MM_BUG_ON(!drm_mm_clean(&mm));
+	}
+
+	ret = 0;
+out:
+	drm_mm_for_each_node_safe(node, next, &mm)
+		drm_mm_remove_node(node);
+	drm_mm_takedown(&mm);
+	vfree(nodes);
+err:
+	return ret;
+}
+
+static int igt_align_pot(int max)
+{
+	struct drm_mm mm;
+	struct drm_mm_node *node, *next;
+	int bit;
+	int ret = -EINVAL;
+
+	/* Check that we can align to the full u64 address space */
+
+	drm_mm_init(&mm, 1, U64_MAX - 2);
+
+	for (bit = max - 1; bit; bit--) {
+		u64 align, size;
+
+		node = kzalloc(sizeof(*node), GFP_KERNEL);
+		if (!node) {
+			ret = -ENOMEM;
+			goto out;
+		}
+
+		align = BIT_ULL(bit);
+		size = BIT_ULL(bit-1) + 1;
+		if (!expect_insert(&mm, node,
+				   size, align, bit,
+				   &insert_modes[0])) {
+			pr_err("insert failed with alignment=%llx [%d]",
+			       align, bit);
+			goto out;
+		}
+	}
+
+	ret = 0;
+out:
+	drm_mm_for_each_node_safe(node, next, &mm) {
+		drm_mm_remove_node(node);
+		kfree(node);
+	}
+	drm_mm_takedown(&mm);
+	return ret;
+}
+
+static int igt_align32(void *ignored)
+{
+	return igt_align_pot(32);
+}
+
+static int igt_align64(void *ignored)
+{
+	return igt_align_pot(64);
+}
+
 #include "drm_selftest.c"
 
 static int __init test_drm_mm_init(void)
-- 
cgit 


From 560b32842912f9271ea47879f9b374693b724721 Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 22 Dec 2016 08:36:17 +0000
Subject: drm: kselftest for drm_mm and eviction

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: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-15-chris@chris-wilson.co.uk
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 337 ++++++++++++++++++++++++++++++++
 1 file changed, 337 insertions(+)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index 53ba268e07d9..065e2c72845b 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -36,6 +36,10 @@ static const struct insert_mode {
 	[TOPDOWN] = { "top-down", DRM_MM_SEARCH_BELOW, DRM_MM_CREATE_TOP },
 	[BEST] = { "best", DRM_MM_SEARCH_BEST, DRM_MM_CREATE_DEFAULT },
 	{}
+}, evict_modes[] = {
+	{ "default", DRM_MM_SEARCH_DEFAULT, DRM_MM_CREATE_DEFAULT },
+	{ "top-down", DRM_MM_SEARCH_BELOW, DRM_MM_CREATE_TOP },
+	{}
 };
 
 static int igt_sanitycheck(void *ignored)
@@ -1110,6 +1114,339 @@ static int igt_align64(void *ignored)
 	return igt_align_pot(64);
 }
 
+static void show_scan(const struct drm_mm *scan)
+{
+	pr_info("scan: hit [%llx, %llx], size=%lld, align=%d, color=%ld\n",
+		scan->scan_hit_start, scan->scan_hit_end,
+		scan->scan_size, scan->scan_alignment, scan->scan_color);
+}
+
+static void show_holes(const struct drm_mm *mm, int count)
+{
+	u64 hole_start, hole_end;
+	struct drm_mm_node *hole;
+
+	drm_mm_for_each_hole(hole, mm, hole_start, hole_end) {
+		struct drm_mm_node *next = list_next_entry(hole, node_list);
+		const char *node1 = NULL, *node2 = NULL;
+
+		if (hole->allocated)
+			node1 = kasprintf(GFP_KERNEL,
+					  "[%llx + %lld, color=%ld], ",
+					  hole->start, hole->size, hole->color);
+
+		if (next->allocated)
+			node2 = kasprintf(GFP_KERNEL,
+					  ", [%llx + %lld, color=%ld]",
+					  next->start, next->size, next->color);
+
+		pr_info("%sHole [%llx - %llx, size %lld]%s\n",
+			node1,
+			hole_start, hole_end, hole_end - hole_start,
+			node2);
+
+		kfree(node2);
+		kfree(node1);
+
+		if (!--count)
+			break;
+	}
+}
+
+struct evict_node {
+	struct drm_mm_node node;
+	struct list_head link;
+};
+
+static bool evict_nodes(struct drm_mm *mm,
+			struct evict_node *nodes,
+			unsigned int *order,
+			unsigned int count,
+			struct list_head *evict_list)
+{
+	struct evict_node *e, *en;
+	unsigned int i;
+
+	for (i = 0; i < count; i++) {
+		e = &nodes[order ? order[i] : i];
+		list_add(&e->link, evict_list);
+		if (drm_mm_scan_add_block(&e->node))
+			break;
+	}
+	list_for_each_entry_safe(e, en, evict_list, link) {
+		if (!drm_mm_scan_remove_block(&e->node))
+			list_del(&e->link);
+	}
+	if (list_empty(evict_list)) {
+		pr_err("Failed to find eviction: size=%lld [avail=%d], align=%d (color=%lu)\n",
+		       mm->scan_size, count,
+		       mm->scan_alignment,
+		       mm->scan_color);
+		return false;
+	}
+
+	list_for_each_entry(e, evict_list, link)
+		drm_mm_remove_node(&e->node);
+
+	return true;
+}
+
+static bool evict_nothing(struct drm_mm *mm,
+			  unsigned int total_size,
+			  struct evict_node *nodes)
+{
+	LIST_HEAD(evict_list);
+	struct evict_node *e;
+	struct drm_mm_node *node;
+	unsigned int n;
+
+	drm_mm_init_scan(mm, 1, 0, 0);
+	for (n = 0; n < total_size; n++) {
+		e = &nodes[n];
+		list_add(&e->link, &evict_list);
+		drm_mm_scan_add_block(&e->node);
+	}
+	list_for_each_entry(e, &evict_list, link)
+		drm_mm_scan_remove_block(&e->node);
+
+	for (n = 0; n < total_size; n++) {
+		e = &nodes[n];
+
+		if (!drm_mm_node_allocated(&e->node)) {
+			pr_err("node[%d] no longer allocated!\n", n);
+			return false;
+		}
+
+		e->link.next = NULL;
+	}
+
+	drm_mm_for_each_node(node, mm) {
+		e = container_of(node, typeof(*e), node);
+		e->link.next = &e->link;
+	}
+
+	for (n = 0; n < total_size; n++) {
+		e = &nodes[n];
+
+		if (!e->link.next) {
+			pr_err("node[%d] no longer connected!\n", n);
+			return false;
+		}
+	}
+
+	return assert_continuous(mm, nodes[0].node.size);
+}
+
+static bool evict_everything(struct drm_mm *mm,
+			     unsigned int total_size,
+			     struct evict_node *nodes)
+{
+	LIST_HEAD(evict_list);
+	struct evict_node *e;
+	unsigned int n;
+	int err;
+
+	drm_mm_init_scan(mm, total_size, 0, 0);
+	for (n = 0; n < total_size; n++) {
+		e = &nodes[n];
+		list_add(&e->link, &evict_list);
+		drm_mm_scan_add_block(&e->node);
+	}
+	list_for_each_entry(e, &evict_list, link) {
+		if (!drm_mm_scan_remove_block(&e->node)) {
+			pr_err("Node %lld not marked for eviction!\n",
+			       e->node.start);
+			list_del(&e->link);
+		}
+	}
+
+	list_for_each_entry(e, &evict_list, link)
+		drm_mm_remove_node(&e->node);
+
+	if (!assert_one_hole(mm, 0, total_size))
+		return false;
+
+	list_for_each_entry(e, &evict_list, link) {
+		err = drm_mm_reserve_node(mm, &e->node);
+		if (err) {
+			pr_err("Failed to reinsert node after eviction: start=%llx\n",
+			       e->node.start);
+			return false;
+		}
+	}
+
+	return assert_continuous(mm, nodes[0].node.size);
+}
+
+static int evict_something(struct drm_mm *mm,
+			   struct evict_node *nodes,
+			   unsigned int *order,
+			   unsigned int count,
+			   unsigned int size,
+			   unsigned int alignment,
+			   const struct insert_mode *mode)
+{
+	LIST_HEAD(evict_list);
+	struct evict_node *e;
+	struct drm_mm_node tmp;
+	int err;
+
+	drm_mm_init_scan(mm, size, alignment, 0);
+	if (!evict_nodes(mm,
+			 nodes, order, count,
+			 &evict_list))
+		return -EINVAL;
+
+	memset(&tmp, 0, sizeof(tmp));
+	err = drm_mm_insert_node_generic(mm, &tmp, size, alignment, 0,
+					 mode->search_flags,
+					 mode->create_flags);
+	if (err) {
+		pr_err("Failed to insert into eviction hole: size=%d, align=%d\n",
+		       size, alignment);
+		show_scan(mm);
+		show_holes(mm, 3);
+		return err;
+	}
+
+	if (!assert_node(&tmp, mm, size, alignment, 0) || tmp.hole_follows) {
+		pr_err("Inserted did not fill the eviction hole: size=%lld [%d], align=%d [rem=%lld], start=%llx, hole-follows?=%d\n",
+		       tmp.size, size,
+		       alignment, misalignment(&tmp, alignment),
+		       tmp.start, tmp.hole_follows);
+		err = -EINVAL;
+	}
+
+	drm_mm_remove_node(&tmp);
+	if (err)
+		return err;
+
+	list_for_each_entry(e, &evict_list, link) {
+		err = drm_mm_reserve_node(mm, &e->node);
+		if (err) {
+			pr_err("Failed to reinsert node after eviction: start=%llx\n",
+			       e->node.start);
+			return err;
+		}
+	}
+
+	if (!assert_continuous(mm, nodes[0].node.size)) {
+		pr_err("range is no longer continuous\n");
+		return -EINVAL;
+	}
+
+	return 0;
+}
+
+static int igt_evict(void *ignored)
+{
+	DRM_RND_STATE(prng, random_seed);
+	const unsigned int size = 8192;
+	const struct insert_mode *mode;
+	struct drm_mm mm;
+	struct evict_node *nodes;
+	struct drm_mm_node *node, *next;
+	unsigned int *order, n;
+	int ret, err;
+
+	/* Here we populate a full drm_mm and then try and insert a new node
+	 * by evicting other nodes in a random order. The drm_mm_scan should
+	 * pick the first matching hole it finds from the random list. We
+	 * repeat that for different allocation strategies, alignments and
+	 * sizes to try and stress the hole finder.
+	 */
+
+	ret = -ENOMEM;
+	nodes = vzalloc(size * sizeof(*nodes));
+	if (!nodes)
+		goto err;
+
+	order = drm_random_order(size, &prng);
+	if (!order)
+		goto err_nodes;
+
+	ret = -EINVAL;
+	drm_mm_init(&mm, 0, size);
+	for (n = 0; n < size; n++) {
+		err = drm_mm_insert_node(&mm, &nodes[n].node, 1, 0,
+					 DRM_MM_SEARCH_DEFAULT);
+		if (err) {
+			pr_err("insert failed, step %d\n", n);
+			ret = err;
+			goto out;
+		}
+	}
+
+	/* First check that using the scanner doesn't break the mm */
+	if (!evict_nothing(&mm, size, nodes)) {
+		pr_err("evict_nothing() failed\n");
+		goto out;
+	}
+	if (!evict_everything(&mm, size, nodes)) {
+		pr_err("evict_everything() failed\n");
+		goto out;
+	}
+
+	for (mode = evict_modes; mode->name; mode++) {
+		for (n = 1; n <= size; n <<= 1) {
+			drm_random_reorder(order, size, &prng);
+			err = evict_something(&mm,
+					      nodes, order, size,
+					      n, 1,
+					      mode);
+			if (err) {
+				pr_err("%s evict_something(size=%u) failed\n",
+				       mode->name, n);
+				ret = err;
+				goto out;
+			}
+		}
+
+		for (n = 1; n < size; n <<= 1) {
+			drm_random_reorder(order, size, &prng);
+			err = evict_something(&mm,
+					      nodes, order, size,
+					      size/2, n,
+					      mode);
+			if (err) {
+				pr_err("%s evict_something(size=%u, alignment=%u) failed\n",
+				       mode->name, size/2, n);
+				ret = err;
+				goto out;
+			}
+		}
+
+		for_each_prime_number_from(n, 1, min(size, max_prime)) {
+			unsigned int nsize = (size - n + 1) / 2;
+
+			DRM_MM_BUG_ON(!nsize);
+
+			drm_random_reorder(order, size, &prng);
+			err = evict_something(&mm,
+					      nodes, order, size,
+					      nsize, n,
+					      mode);
+			if (err) {
+				pr_err("%s evict_something(size=%u, alignment=%u) failed\n",
+				       mode->name, nsize, n);
+				ret = err;
+				goto out;
+			}
+		}
+	}
+
+	ret = 0;
+out:
+	drm_mm_for_each_node_safe(node, next, &mm)
+		drm_mm_remove_node(node);
+	drm_mm_takedown(&mm);
+	kfree(order);
+err_nodes:
+	vfree(nodes);
+err:
+	return ret;
+}
+
 #include "drm_selftest.c"
 
 static int __init test_drm_mm_init(void)
-- 
cgit 


From 0e483254e578e106d66f4881d86e8364c8752a16 Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 22 Dec 2016 08:36:18 +0000
Subject: drm: kselftest for drm_mm and range restricted eviction

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: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-16-chris@chris-wilson.co.uk
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 113 ++++++++++++++++++++++++++++++--
 1 file changed, 109 insertions(+), 4 deletions(-)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index 065e2c72845b..d49115186967 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -1279,6 +1279,7 @@ static bool evict_everything(struct drm_mm *mm,
 }
 
 static int evict_something(struct drm_mm *mm,
+			   u64 range_start, u64 range_end,
 			   struct evict_node *nodes,
 			   unsigned int *order,
 			   unsigned int count,
@@ -1291,7 +1292,9 @@ static int evict_something(struct drm_mm *mm,
 	struct drm_mm_node tmp;
 	int err;
 
-	drm_mm_init_scan(mm, size, alignment, 0);
+	drm_mm_init_scan_with_range(mm,
+				    size, alignment, 0,
+				    range_start, range_end);
 	if (!evict_nodes(mm,
 			 nodes, order, count,
 			 &evict_list))
@@ -1309,6 +1312,12 @@ static int evict_something(struct drm_mm *mm,
 		return err;
 	}
 
+	if (tmp.start < range_start || tmp.start + tmp.size > range_end) {
+		pr_err("Inserted [address=%llu + %llu] did not fit into the request range [%llu, %llu]\n",
+		       tmp.start, tmp.size, range_start, range_end);
+		err = -EINVAL;
+	}
+
 	if (!assert_node(&tmp, mm, size, alignment, 0) || tmp.hole_follows) {
 		pr_err("Inserted did not fill the eviction hole: size=%lld [%d], align=%d [rem=%lld], start=%llx, hole-follows?=%d\n",
 		       tmp.size, size,
@@ -1390,7 +1399,7 @@ static int igt_evict(void *ignored)
 	for (mode = evict_modes; mode->name; mode++) {
 		for (n = 1; n <= size; n <<= 1) {
 			drm_random_reorder(order, size, &prng);
-			err = evict_something(&mm,
+			err = evict_something(&mm, 0, U64_MAX,
 					      nodes, order, size,
 					      n, 1,
 					      mode);
@@ -1404,7 +1413,7 @@ static int igt_evict(void *ignored)
 
 		for (n = 1; n < size; n <<= 1) {
 			drm_random_reorder(order, size, &prng);
-			err = evict_something(&mm,
+			err = evict_something(&mm, 0, U64_MAX,
 					      nodes, order, size,
 					      size/2, n,
 					      mode);
@@ -1422,7 +1431,7 @@ static int igt_evict(void *ignored)
 			DRM_MM_BUG_ON(!nsize);
 
 			drm_random_reorder(order, size, &prng);
-			err = evict_something(&mm,
+			err = evict_something(&mm, 0, U64_MAX,
 					      nodes, order, size,
 					      nsize, n,
 					      mode);
@@ -1447,6 +1456,102 @@ err:
 	return ret;
 }
 
+static int igt_evict_range(void *ignored)
+{
+	DRM_RND_STATE(prng, random_seed);
+	const unsigned int size = 8192;
+	const unsigned int range_size = size / 2;
+	const unsigned int range_start = size / 4;
+	const unsigned int range_end = range_start + range_size;
+	const struct insert_mode *mode;
+	struct drm_mm mm;
+	struct evict_node *nodes;
+	struct drm_mm_node *node, *next;
+	unsigned int *order, n;
+	int ret, err;
+
+	/* Like igt_evict() but now we are limiting the search to a
+	 * small portion of the full drm_mm.
+	 */
+
+	ret = -ENOMEM;
+	nodes = vzalloc(size * sizeof(*nodes));
+	if (!nodes)
+		goto err;
+
+	order = drm_random_order(size, &prng);
+	if (!order)
+		goto err_nodes;
+
+	ret = -EINVAL;
+	drm_mm_init(&mm, 0, size);
+	for (n = 0; n < size; n++) {
+		err = drm_mm_insert_node(&mm, &nodes[n].node, 1, 0,
+					 DRM_MM_SEARCH_DEFAULT);
+		if (err) {
+			pr_err("insert failed, step %d\n", n);
+			ret = err;
+			goto out;
+		}
+	}
+
+	for (mode = evict_modes; mode->name; mode++) {
+		for (n = 1; n <= range_size; n <<= 1) {
+			drm_random_reorder(order, size, &prng);
+			err = evict_something(&mm, range_start, range_end,
+					      nodes, order, size,
+					      n, 1,
+					      mode);
+			if (err) {
+				pr_err("%s evict_something(size=%u) failed with range [%u, %u]\n",
+				       mode->name, n, range_start, range_end);
+				goto out;
+			}
+		}
+
+		for (n = 1; n <= range_size; n <<= 1) {
+			drm_random_reorder(order, size, &prng);
+			err = evict_something(&mm, range_start, range_end,
+					      nodes, order, size,
+					      range_size/2, n,
+					      mode);
+			if (err) {
+				pr_err("%s evict_something(size=%u, alignment=%u) failed with range [%u, %u]\n",
+				       mode->name, range_size/2, n, range_start, range_end);
+				goto out;
+			}
+		}
+
+		for_each_prime_number_from(n, 1, min(range_size, max_prime)) {
+			unsigned int nsize = (range_size - n + 1) / 2;
+
+			DRM_MM_BUG_ON(!nsize);
+
+			drm_random_reorder(order, size, &prng);
+			err = evict_something(&mm, range_start, range_end,
+					      nodes, order, size,
+					      nsize, n,
+					      mode);
+			if (err) {
+				pr_err("%s evict_something(size=%u, alignment=%u) failed with range [%u, %u]\n",
+				       mode->name, nsize, n, range_start, range_end);
+				goto out;
+			}
+		}
+	}
+
+	ret = 0;
+out:
+	drm_mm_for_each_node_safe(node, next, &mm)
+		drm_mm_remove_node(node);
+	drm_mm_takedown(&mm);
+	kfree(order);
+err_nodes:
+	vfree(nodes);
+err:
+	return ret;
+}
+
 #include "drm_selftest.c"
 
 static int __init test_drm_mm_init(void)
-- 
cgit 


From 05ab3c2eec74507712cd5f2b027c7c8b9a66f190 Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 22 Dec 2016 08:36:19 +0000
Subject: drm: kselftest for drm_mm and top-down allocation

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: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-17-chris@chris-wilson.co.uk
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 119 ++++++++++++++++++++++++++++++++
 1 file changed, 119 insertions(+)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index d49115186967..d3d4e4f39042 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -1552,6 +1552,125 @@ err:
 	return ret;
 }
 
+static unsigned int node_index(const struct drm_mm_node *node)
+{
+	return div64_u64(node->start, node->size);
+}
+
+static int igt_topdown(void *ignored)
+{
+	const struct insert_mode *topdown = &insert_modes[TOPDOWN];
+	DRM_RND_STATE(prng, random_seed);
+	const unsigned int count = 8192;
+	unsigned int size;
+	unsigned long *bitmap = NULL;
+	struct drm_mm mm;
+	struct drm_mm_node *nodes, *node, *next;
+	unsigned int *order, n, m, o = 0;
+	int ret;
+
+	/* When allocating top-down, we expect to be returned a node
+	 * from a suitable hole at the top of the drm_mm. We check that
+	 * the returned node does match the highest available slot.
+	 */
+
+	ret = -ENOMEM;
+	nodes = vzalloc(count * sizeof(*nodes));
+	if (!nodes)
+		goto err;
+
+	bitmap = kzalloc(count / BITS_PER_LONG * sizeof(unsigned long),
+			 GFP_TEMPORARY);
+	if (!bitmap)
+		goto err_nodes;
+
+	order = drm_random_order(count, &prng);
+	if (!order)
+		goto err_bitmap;
+
+	ret = -EINVAL;
+	for (size = 1; size <= 64; size <<= 1) {
+		drm_mm_init(&mm, 0, size*count);
+		for (n = 0; n < count; n++) {
+			if (!expect_insert(&mm, &nodes[n],
+					   size, 0, n,
+					   topdown)) {
+				pr_err("insert failed, size %u step %d\n", size, n);
+				goto out;
+			}
+
+			if (nodes[n].hole_follows) {
+				pr_err("hole after topdown insert %d, start=%llx\n, size=%u",
+				       n, nodes[n].start, size);
+				goto out;
+			}
+
+			if (!assert_one_hole(&mm, 0, size*(count - n - 1)))
+				goto out;
+		}
+
+		if (!assert_continuous(&mm, size))
+			goto out;
+
+		drm_random_reorder(order, count, &prng);
+		for_each_prime_number_from(n, 1, min(count, max_prime)) {
+			for (m = 0; m < n; m++) {
+				node = &nodes[order[(o + m) % count]];
+				drm_mm_remove_node(node);
+				__set_bit(node_index(node), bitmap);
+			}
+
+			for (m = 0; m < n; m++) {
+				unsigned int last;
+
+				node = &nodes[order[(o + m) % count]];
+				if (!expect_insert(&mm, node,
+						   size, 0, 0,
+						   topdown)) {
+					pr_err("insert failed, step %d/%d\n", m, n);
+					goto out;
+				}
+
+				if (node->hole_follows) {
+					pr_err("hole after topdown insert %d/%d, start=%llx\n",
+					       m, n, node->start);
+					goto out;
+				}
+
+				last = find_last_bit(bitmap, count);
+				if (node_index(node) != last) {
+					pr_err("node %d/%d, size %d, not inserted into upmost hole, expected %d, found %d\n",
+					       m, n, size, last, node_index(node));
+					goto out;
+				}
+
+				__clear_bit(last, bitmap);
+			}
+
+			DRM_MM_BUG_ON(find_first_bit(bitmap, count) != count);
+
+			o += n;
+		}
+
+		drm_mm_for_each_node_safe(node, next, &mm)
+			drm_mm_remove_node(node);
+		DRM_MM_BUG_ON(!drm_mm_clean(&mm));
+	}
+
+	ret = 0;
+out:
+	drm_mm_for_each_node_safe(node, next, &mm)
+		drm_mm_remove_node(node);
+	drm_mm_takedown(&mm);
+	kfree(order);
+err_bitmap:
+	kfree(bitmap);
+err_nodes:
+	vfree(nodes);
+err:
+	return ret;
+}
+
 #include "drm_selftest.c"
 
 static int __init test_drm_mm_init(void)
-- 
cgit 


From 4c2ba55b5c76835e826564f8623c36a5bfe0d3a9 Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 22 Dec 2016 08:36:20 +0000
Subject: drm: kselftest for drm_mm and color adjustment

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: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-18-chris@chris-wilson.co.uk
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 183 ++++++++++++++++++++++++++++++++
 1 file changed, 183 insertions(+)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index d3d4e4f39042..24841d3994dc 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -1671,6 +1671,189 @@ err:
 	return ret;
 }
 
+static void separate_adjacent_colors(const struct drm_mm_node *node,
+				     unsigned long color,
+				     u64 *start,
+				     u64 *end)
+{
+	if (node->allocated && node->color != color)
+		++*start;
+
+	node = list_next_entry(node, node_list);
+	if (node->allocated && node->color != color)
+		--*end;
+}
+
+static bool colors_abutt(const struct drm_mm_node *node)
+{
+	if (!node->hole_follows &&
+	    list_next_entry(node, node_list)->allocated) {
+		pr_err("colors abutt; %ld [%llx + %llx] is next to %ld [%llx + %llx]!\n",
+		       node->color, node->start, node->size,
+		       list_next_entry(node, node_list)->color,
+		       list_next_entry(node, node_list)->start,
+		       list_next_entry(node, node_list)->size);
+		return true;
+	}
+
+	return false;
+}
+
+static int igt_color(void *ignored)
+{
+	const unsigned int count = min(4096u, max_iterations);
+	const struct insert_mode *mode;
+	struct drm_mm mm;
+	struct drm_mm_node *node, *nn;
+	unsigned int n;
+	int ret = -EINVAL, err;
+
+	/* Color adjustment complicates everything. First we just check
+	 * that when we insert a node we apply any color_adjustment callback.
+	 * The callback we use should ensure that there is a gap between
+	 * any two nodes, and so after each insertion we check that those
+	 * holes are inserted and that they are preserved.
+	 */
+
+	drm_mm_init(&mm, 0, U64_MAX);
+
+	for (n = 1; n <= count; n++) {
+		node = kzalloc(sizeof(*node), GFP_KERNEL);
+		if (!node) {
+			ret = -ENOMEM;
+			goto out;
+		}
+
+		if (!expect_insert(&mm, node,
+				   n, 0, n,
+				   &insert_modes[0])) {
+			pr_err("insert failed, step %d\n", n);
+			kfree(node);
+			goto out;
+		}
+	}
+
+	drm_mm_for_each_node_safe(node, nn, &mm) {
+		if (node->color != node->size) {
+			pr_err("invalid color stored: expected %lld, found %ld\n",
+			       node->size, node->color);
+
+			goto out;
+		}
+
+		drm_mm_remove_node(node);
+		kfree(node);
+	}
+
+	/* Now, let's start experimenting with applying a color callback */
+	mm.color_adjust = separate_adjacent_colors;
+	for (mode = insert_modes; mode->name; mode++) {
+		u64 last;
+
+		node = kzalloc(sizeof(*node), GFP_KERNEL);
+		if (!node) {
+			ret = -ENOMEM;
+			goto out;
+		}
+
+		node->size = 1 + 2*count;
+		node->color = node->size;
+
+		err = drm_mm_reserve_node(&mm, node);
+		if (err) {
+			pr_err("initial reserve failed!\n");
+			ret = err;
+			goto out;
+		}
+
+		last = node->start + node->size;
+
+		for (n = 1; n <= count; n++) {
+			int rem;
+
+			node = kzalloc(sizeof(*node), GFP_KERNEL);
+			if (!node) {
+				ret = -ENOMEM;
+				goto out;
+			}
+
+			node->start = last;
+			node->size = n + count;
+			node->color = node->size;
+
+			err = drm_mm_reserve_node(&mm, node);
+			if (err != -ENOSPC) {
+				pr_err("reserve %d did not report color overlap! err=%d\n",
+				       n, err);
+				goto out;
+			}
+
+			node->start += n + 1;
+			rem = misalignment(node, n + count);
+			node->start += n + count - rem;
+
+			err = drm_mm_reserve_node(&mm, node);
+			if (err) {
+				pr_err("reserve %d failed, err=%d\n", n, err);
+				ret = err;
+				goto out;
+			}
+
+			last = node->start + node->size;
+		}
+
+		for (n = 1; n <= count; n++) {
+			node = kzalloc(sizeof(*node), GFP_KERNEL);
+			if (!node) {
+				ret = -ENOMEM;
+				goto out;
+			}
+
+			if (!expect_insert(&mm, node,
+					   n, n, n,
+					   mode)) {
+				pr_err("%s insert failed, step %d\n",
+				       mode->name, n);
+				kfree(node);
+				goto out;
+			}
+		}
+
+		drm_mm_for_each_node_safe(node, nn, &mm) {
+			u64 rem;
+
+			if (node->color != node->size) {
+				pr_err("%s invalid color stored: expected %lld, found %ld\n",
+				       mode->name, node->size, node->color);
+
+				goto out;
+			}
+
+			if (colors_abutt(node))
+				goto out;
+
+			div64_u64_rem(node->start, node->size, &rem);
+			if (rem) {
+				pr_err("%s colored node misaligned, start=%llx expected alignment=%lld [rem=%lld]\n",
+				       mode->name, node->start, node->size, rem);
+				goto out;
+			}
+
+			drm_mm_remove_node(node);
+			kfree(node);
+		}
+	}
+
+	ret = 0;
+out:
+	drm_mm_for_each_node_safe(node, nn, &mm) {
+		drm_mm_remove_node(node);
+		kfree(node);
+	}
+	drm_mm_takedown(&mm);
+	return ret;
+}
+
 #include "drm_selftest.c"
 
 static int __init test_drm_mm_init(void)
-- 
cgit 


From c1b702c9a54316362b3c82e2fa36371ae6f4ab53 Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 22 Dec 2016 08:36:21 +0000
Subject: drm: kselftest for drm_mm and color eviction

Check that after applying the driver's color adjustment, eviction
scanning finds a suitable hole.

Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-19-chris@chris-wilson.co.uk
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 156 ++++++++++++++++++++++++++++++++
 1 file changed, 156 insertions(+)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index 24841d3994dc..6584e4ce96af 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -1854,6 +1854,162 @@ out:
 	return ret;
 }
 
+static int evict_color(struct drm_mm *mm,
+		       struct evict_node *nodes,
+		       unsigned int *order,
+		       unsigned int count,
+		       unsigned int size,
+		       unsigned int alignment,
+		       unsigned long color,
+		       const struct insert_mode *mode)
+{
+	LIST_HEAD(evict_list);
+	struct evict_node *e;
+	struct drm_mm_node tmp;
+	int err;
+
+	drm_mm_init_scan(mm, size, alignment, color);
+	if (!evict_nodes(mm,
+			 nodes, order, count,
+			 &evict_list))
+		return -EINVAL;
+
+	memset(&tmp, 0, sizeof(tmp));
+	err = drm_mm_insert_node_generic(mm, &tmp, size, alignment, color,
+					 mode->search_flags,
+					 mode->create_flags);
+	if (err) {
+		pr_err("Failed to insert into eviction hole: size=%d, align=%d, color=%lu, err=%d\n",
+		       size, alignment, color, err);
+		show_scan(mm);
+		show_holes(mm, 3);
+		return err;
+	}
+
+	if (colors_abutt(&tmp))
+		err = -EINVAL;
+
+	if (!assert_node(&tmp, mm, size, alignment, color)) {
+		pr_err("Inserted did not fit the eviction hole: size=%lld [%d], align=%d [rem=%lld], start=%llx\n",
+		       tmp.size, size,
+		       alignment, misalignment(&tmp, alignment), tmp.start);
+		err = -EINVAL;
+	}
+
+	drm_mm_remove_node(&tmp);
+	if (err)
+		return err;
+
+	list_for_each_entry(e, &evict_list, link) {
+		err = drm_mm_reserve_node(mm, &e->node);
+		if (err) {
+			pr_err("Failed to reinsert node after eviction: start=%llx\n",
+			       e->node.start);
+			return err;
+		}
+	}
+
+	return 0;
+}
+
+static int igt_color_evict(void *ignored)
+{
+	DRM_RND_STATE(prng, random_seed);
+	const unsigned int total_size = min(8192u, max_iterations);
+	const struct insert_mode *mode;
+	unsigned long color = 0;
+	struct drm_mm mm;
+	struct evict_node *nodes;
+	struct drm_mm_node *node, *next;
+	unsigned int *order, n;
+	int ret, err;
+
+	/* Check that the drm_mm_scan also honours color adjustment when
+	 * choosing its victims to create a hole. Our color_adjust does not
+	 * allow two nodes to be placed together without an intervening hole
+	 * enlarging the set of victims that must be evicted.
+	 */
+
+	ret = -ENOMEM;
+	nodes = vzalloc(total_size * sizeof(*nodes));
+	if (!nodes)
+		goto err;
+
+	order = drm_random_order(total_size, &prng);
+	if (!order)
+		goto err_nodes;
+
+	ret = -EINVAL;
+	drm_mm_init(&mm, 0, 2*total_size - 1);
+	mm.color_adjust = separate_adjacent_colors;
+	for (n = 0; n < total_size; n++) {
+		if (!expect_insert(&mm, &nodes[n].node,
+				   1, 0, color++,
+				   &insert_modes[0])) {
+			pr_err("insert failed, step %d\n", n);
+			goto out;
+		}
+	}
+
+	for (mode = evict_modes; mode->name; mode++) {
+		for (n = 1; n <= total_size; n <<= 1) {
+			drm_random_reorder(order, total_size, &prng);
+			err = evict_color(&mm,
+					  nodes, order, total_size,
+					  n, 1, color++,
+					  mode);
+			if (err) {
+				pr_err("%s evict_color(size=%u) failed\n",
+				       mode->name, n);
+				goto out;
+			}
+		}
+
+		for (n = 1; n < total_size; n <<= 1) {
+			drm_random_reorder(order, total_size, &prng);
+			err = evict_color(&mm,
+					  nodes, order, total_size,
+					  total_size/2, n, color++,
+					  mode);
+			if (err) {
+				pr_err("%s evict_color(size=%u, alignment=%u) failed\n",
+				       mode->name, total_size/2, n);
+				goto out;
+			}
+		}
+
+		for_each_prime_number_from(n, 1, min(total_size, max_prime)) {
+			unsigned int nsize = (total_size - n + 1) / 2;
+
+			DRM_MM_BUG_ON(!nsize);
+
+			drm_random_reorder(order, total_size, &prng);
+			err = evict_color(&mm,
+					  nodes, order, total_size,
+					  nsize, n, color++,
+					  mode);
+			if (err) {
+				pr_err("%s evict_color(size=%u, alignment=%u) failed\n",
+				       mode->name, nsize, n);
+				goto out;
+			}
+		}
+	}
+
+	ret = 0;
+out:
+	if (ret)
+		drm_mm_debug_table(&mm, __func__);
+	drm_mm_for_each_node_safe(node, next, &mm)
+		drm_mm_remove_node(node);
+	drm_mm_takedown(&mm);
+	kfree(order);
+err_nodes:
+	vfree(nodes);
+err:
+	return ret;
+}
+
 #include "drm_selftest.c"
 
 static int __init test_drm_mm_init(void)
-- 
cgit 


From d1bac3a78111c82befc8c8fc185b2d90a64ed4b6 Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 22 Dec 2016 08:36:22 +0000
Subject: drm: kselftest for drm_mm and restricted color eviction

Check that after applying the driver's color adjustment, restricted
eviction scanning finds a suitable hole.

Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-20-chris@chris-wilson.co.uk
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 116 ++++++++++++++++++++++++++++++--
 1 file changed, 112 insertions(+), 4 deletions(-)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index 6584e4ce96af..fb8f7056225b 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -1855,6 +1855,7 @@ out:
 }
 
 static int evict_color(struct drm_mm *mm,
+		       u64 range_start, u64 range_end,
 		       struct evict_node *nodes,
 		       unsigned int *order,
 		       unsigned int count,
@@ -1868,7 +1869,9 @@ static int evict_color(struct drm_mm *mm,
 	struct drm_mm_node tmp;
 	int err;
 
-	drm_mm_init_scan(mm, size, alignment, color);
+	drm_mm_init_scan_with_range(mm,
+				    size, alignment, color,
+				    range_start, range_end);
 	if (!evict_nodes(mm,
 			 nodes, order, count,
 			 &evict_list))
@@ -1886,6 +1889,12 @@ static int evict_color(struct drm_mm *mm,
 		return err;
 	}
 
+	if (tmp.start < range_start || tmp.start + tmp.size > range_end) {
+		pr_err("Inserted [address=%llu + %llu] did not fit into the request range [%llu, %llu]\n",
+		       tmp.start, tmp.size, range_start, range_end);
+		err = -EINVAL;
+	}
+
 	if (colors_abutt(&tmp))
 		err = -EINVAL;
 
@@ -1954,7 +1963,7 @@ static int igt_color_evict(void *ignored)
 	for (mode = evict_modes; mode->name; mode++) {
 		for (n = 1; n <= total_size; n <<= 1) {
 			drm_random_reorder(order, total_size, &prng);
-			err = evict_color(&mm,
+			err = evict_color(&mm, 0, U64_MAX,
 					  nodes, order, total_size,
 					  n, 1, color++,
 					  mode);
@@ -1967,7 +1976,7 @@ static int igt_color_evict(void *ignored)
 
 		for (n = 1; n < total_size; n <<= 1) {
 			drm_random_reorder(order, total_size, &prng);
-			err = evict_color(&mm,
+			err = evict_color(&mm, 0, U64_MAX,
 					  nodes, order, total_size,
 					  total_size/2, n, color++,
 					  mode);
@@ -1984,7 +1993,7 @@ static int igt_color_evict(void *ignored)
 			DRM_MM_BUG_ON(!nsize);
 
 			drm_random_reorder(order, total_size, &prng);
-			err = evict_color(&mm,
+			err = evict_color(&mm, 0, U64_MAX,
 					  nodes, order, total_size,
 					  nsize, n, color++,
 					  mode);
@@ -2010,6 +2019,105 @@ err:
 	return ret;
 }
 
+static int igt_color_evict_range(void *ignored)
+{
+	DRM_RND_STATE(prng, random_seed);
+	const unsigned int total_size = 8192;
+	const unsigned int range_size = total_size / 2;
+	const unsigned int range_start = total_size / 4;
+	const unsigned int range_end = range_start + range_size;
+	const struct insert_mode *mode;
+	unsigned long color = 0;
+	struct drm_mm mm;
+	struct evict_node *nodes;
+	struct drm_mm_node *node, *next;
+	unsigned int *order, n;
+	int ret, err;
+
+	/* Like igt_color_evict(), but limited to small portion of the full
+	 * drm_mm range.
+	 */
+
+	ret = -ENOMEM;
+	nodes = vzalloc(total_size * sizeof(*nodes));
+	if (!nodes)
+		goto err;
+
+	order = drm_random_order(total_size, &prng);
+	if (!order)
+		goto err_nodes;
+
+	ret = -EINVAL;
+	drm_mm_init(&mm, 0, 2*total_size - 1);
+	mm.color_adjust = separate_adjacent_colors;
+	for (n = 0; n < total_size; n++) {
+		if (!expect_insert(&mm, &nodes[n].node,
+				   1, 0, color++,
+				   &insert_modes[0])) {
+			pr_err("insert failed, step %d\n", n);
+			goto out;
+		}
+	}
+
+	for (mode = evict_modes; mode->name; mode++) {
+		for (n = 1; n <= range_size; n <<= 1) {
+			drm_random_reorder(order, range_size, &prng);
+			err = evict_color(&mm, range_start, range_end,
+					  nodes, order, total_size,
+					  n, 1, color++,
+					  mode);
+			if (err) {
+				pr_err("%s evict_color(size=%u) failed for range [%x, %x]\n",
+				       mode->name, n, range_start, range_end);
+				goto out;
+			}
+		}
+
+		for (n = 1; n < range_size; n <<= 1) {
+			drm_random_reorder(order, total_size, &prng);
+			err = evict_color(&mm, range_start, range_end,
+					  nodes, order, total_size,
+					  range_size/2, n, color++,
+					  mode);
+			if (err) {
+				pr_err("%s evict_color(size=%u, alignment=%u) failed for range [%x, %x]\n",
+				       mode->name, total_size/2, n, range_start, range_end);
+				goto out;
+			}
+		}
+
+		for_each_prime_number_from(n, 1, min(range_size, max_prime)) {
+			unsigned int nsize = (range_size - n + 1) / 2;
+
+			DRM_MM_BUG_ON(!nsize);
+
+			drm_random_reorder(order, total_size, &prng);
+			err = evict_color(&mm, range_start, range_end,
+					  nodes, order, total_size,
+					  nsize, n, color++,
+					  mode);
+			if (err) {
+				pr_err("%s evict_color(size=%u, alignment=%u) failed for range [%x, %x]\n",
+				       mode->name, nsize, n, range_start, range_end);
+				goto out;
+			}
+		}
+	}
+
+	ret = 0;
+out:
+	if (ret)
+		drm_mm_debug_table(&mm, __func__);
+	drm_mm_for_each_node_safe(node, next, &mm)
+		drm_mm_remove_node(node);
+	drm_mm_takedown(&mm);
+	kfree(order);
+err_nodes:
+	vfree(nodes);
+err:
+	return ret;
+}
+
 #include "drm_selftest.c"
 
 static int __init test_drm_mm_init(void)
-- 
cgit 


From 7173320758e5dfcd7a47a51d3fe2b21c43d9633c Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 22 Dec 2016 08:36:24 +0000
Subject: drm: Promote drm_mm alignment to u64
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

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: Chris Wilson <chris@chris-wilson.co.uk>
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Cc: Christian König <christian.koenig@amd.com>
Reviewed-by: Christian König <christian.koenig@amd.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-22-chris@chris-wilson.co.uk
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index fb8f7056225b..e2ed9efb361c 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -1116,7 +1116,7 @@ static int igt_align64(void *ignored)
 
 static void show_scan(const struct drm_mm *scan)
 {
-	pr_info("scan: hit [%llx, %llx], size=%lld, align=%d, color=%ld\n",
+	pr_info("scan: hit [%llx, %llx], size=%lld, align=%lld, color=%ld\n",
 		scan->scan_hit_start, scan->scan_hit_end,
 		scan->scan_size, scan->scan_alignment, scan->scan_color);
 }
@@ -1178,7 +1178,7 @@ static bool evict_nodes(struct drm_mm *mm,
 			list_del(&e->link);
 	}
 	if (list_empty(evict_list)) {
-		pr_err("Failed to find eviction: size=%lld [avail=%d], align=%d (color=%lu)\n",
+		pr_err("Failed to find eviction: size=%lld [avail=%d], align=%lld (color=%lu)\n",
 		       mm->scan_size, count,
 		       mm->scan_alignment,
 		       mm->scan_color);
-- 
cgit 


From 9a71e277888b39b8f0e8364813ec1ba58a5a4371 Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 22 Dec 2016 08:36:29 +0000
Subject: drm: Extract struct drm_mm_scan from struct drm_mm

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: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
[danvet: Fix up etnaviv to compile, was missing a BUG_ON.]
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 45 ++++++++++++++++++---------------
 1 file changed, 24 insertions(+), 21 deletions(-)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index e2ed9efb361c..997f2bc93b9b 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -1114,11 +1114,11 @@ static int igt_align64(void *ignored)
 	return igt_align_pot(64);
 }
 
-static void show_scan(const struct drm_mm *scan)
+static void show_scan(const struct drm_mm_scan *scan)
 {
 	pr_info("scan: hit [%llx, %llx], size=%lld, align=%lld, color=%ld\n",
-		scan->scan_hit_start, scan->scan_hit_end,
-		scan->scan_size, scan->scan_alignment, scan->scan_color);
+		scan->hit_start, scan->hit_end,
+		scan->size, scan->alignment, scan->color);
 }
 
 static void show_holes(const struct drm_mm *mm, int count)
@@ -1158,7 +1158,7 @@ struct evict_node {
 	struct list_head link;
 };
 
-static bool evict_nodes(struct drm_mm *mm,
+static bool evict_nodes(struct drm_mm_scan *scan,
 			struct evict_node *nodes,
 			unsigned int *order,
 			unsigned int count,
@@ -1170,18 +1170,16 @@ static bool evict_nodes(struct drm_mm *mm,
 	for (i = 0; i < count; i++) {
 		e = &nodes[order ? order[i] : i];
 		list_add(&e->link, evict_list);
-		if (drm_mm_scan_add_block(&e->node))
+		if (drm_mm_scan_add_block(scan, &e->node))
 			break;
 	}
 	list_for_each_entry_safe(e, en, evict_list, link) {
-		if (!drm_mm_scan_remove_block(&e->node))
+		if (!drm_mm_scan_remove_block(scan, &e->node))
 			list_del(&e->link);
 	}
 	if (list_empty(evict_list)) {
 		pr_err("Failed to find eviction: size=%lld [avail=%d], align=%lld (color=%lu)\n",
-		       mm->scan_size, count,
-		       mm->scan_alignment,
-		       mm->scan_color);
+		       scan->size, count, scan->alignment, scan->color);
 		return false;
 	}
 
@@ -1195,19 +1193,20 @@ static bool evict_nothing(struct drm_mm *mm,
 			  unsigned int total_size,
 			  struct evict_node *nodes)
 {
+	struct drm_mm_scan scan;
 	LIST_HEAD(evict_list);
 	struct evict_node *e;
 	struct drm_mm_node *node;
 	unsigned int n;
 
-	drm_mm_init_scan(mm, 1, 0, 0);
+	drm_mm_scan_init(&scan, mm, 1, 0, 0);
 	for (n = 0; n < total_size; n++) {
 		e = &nodes[n];
 		list_add(&e->link, &evict_list);
-		drm_mm_scan_add_block(&e->node);
+		drm_mm_scan_add_block(&scan, &e->node);
 	}
 	list_for_each_entry(e, &evict_list, link)
-		drm_mm_scan_remove_block(&e->node);
+		drm_mm_scan_remove_block(&scan, &e->node);
 
 	for (n = 0; n < total_size; n++) {
 		e = &nodes[n];
@@ -1241,19 +1240,21 @@ static bool evict_everything(struct drm_mm *mm,
 			     unsigned int total_size,
 			     struct evict_node *nodes)
 {
+	struct drm_mm_scan scan;
 	LIST_HEAD(evict_list);
 	struct evict_node *e;
 	unsigned int n;
 	int err;
 
-	drm_mm_init_scan(mm, total_size, 0, 0);
+	drm_mm_scan_init(&scan, mm, total_size, 0, 0);
 	for (n = 0; n < total_size; n++) {
 		e = &nodes[n];
 		list_add(&e->link, &evict_list);
-		drm_mm_scan_add_block(&e->node);
+		if (drm_mm_scan_add_block(&scan, &e->node))
+			break;
 	}
 	list_for_each_entry(e, &evict_list, link) {
-		if (!drm_mm_scan_remove_block(&e->node)) {
+		if (!drm_mm_scan_remove_block(&scan, &e->node)) {
 			pr_err("Node %lld not marked for eviction!\n",
 			       e->node.start);
 			list_del(&e->link);
@@ -1287,15 +1288,16 @@ static int evict_something(struct drm_mm *mm,
 			   unsigned int alignment,
 			   const struct insert_mode *mode)
 {
+	struct drm_mm_scan scan;
 	LIST_HEAD(evict_list);
 	struct evict_node *e;
 	struct drm_mm_node tmp;
 	int err;
 
-	drm_mm_init_scan_with_range(mm,
+	drm_mm_scan_init_with_range(&scan, mm,
 				    size, alignment, 0,
 				    range_start, range_end);
-	if (!evict_nodes(mm,
+	if (!evict_nodes(&scan,
 			 nodes, order, count,
 			 &evict_list))
 		return -EINVAL;
@@ -1307,7 +1309,7 @@ static int evict_something(struct drm_mm *mm,
 	if (err) {
 		pr_err("Failed to insert into eviction hole: size=%d, align=%d\n",
 		       size, alignment);
-		show_scan(mm);
+		show_scan(&scan);
 		show_holes(mm, 3);
 		return err;
 	}
@@ -1864,15 +1866,16 @@ static int evict_color(struct drm_mm *mm,
 		       unsigned long color,
 		       const struct insert_mode *mode)
 {
+	struct drm_mm_scan scan;
 	LIST_HEAD(evict_list);
 	struct evict_node *e;
 	struct drm_mm_node tmp;
 	int err;
 
-	drm_mm_init_scan_with_range(mm,
+	drm_mm_scan_init_with_range(&scan, mm,
 				    size, alignment, color,
 				    range_start, range_end);
-	if (!evict_nodes(mm,
+	if (!evict_nodes(&scan,
 			 nodes, order, count,
 			 &evict_list))
 		return -EINVAL;
@@ -1884,7 +1887,7 @@ static int evict_color(struct drm_mm *mm,
 	if (err) {
 		pr_err("Failed to insert into eviction hole: size=%d, align=%d, color=%lu, err=%d\n",
 		       size, alignment, color, err);
-		show_scan(mm);
+		show_scan(&scan);
 		show_holes(mm, 3);
 		return err;
 	}
-- 
cgit 


From 0b04d474a611e2831d142e246422a03a10998ae1 Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 22 Dec 2016 08:36:33 +0000
Subject: drm: Compute tight evictions for drm_mm_scan

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: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-31-chris@chris-wilson.co.uk
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index 997f2bc93b9b..1bbfc24342c5 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -1199,7 +1199,7 @@ static bool evict_nothing(struct drm_mm *mm,
 	struct drm_mm_node *node;
 	unsigned int n;
 
-	drm_mm_scan_init(&scan, mm, 1, 0, 0);
+	drm_mm_scan_init(&scan, mm, 1, 0, 0, 0);
 	for (n = 0; n < total_size; n++) {
 		e = &nodes[n];
 		list_add(&e->link, &evict_list);
@@ -1246,7 +1246,7 @@ static bool evict_everything(struct drm_mm *mm,
 	unsigned int n;
 	int err;
 
-	drm_mm_scan_init(&scan, mm, total_size, 0, 0);
+	drm_mm_scan_init(&scan, mm, total_size, 0, 0, 0);
 	for (n = 0; n < total_size; n++) {
 		e = &nodes[n];
 		list_add(&e->link, &evict_list);
@@ -1296,7 +1296,8 @@ static int evict_something(struct drm_mm *mm,
 
 	drm_mm_scan_init_with_range(&scan, mm,
 				    size, alignment, 0,
-				    range_start, range_end);
+				    range_start, range_end,
+				    mode->create_flags);
 	if (!evict_nodes(&scan,
 			 nodes, order, count,
 			 &evict_list))
@@ -1874,7 +1875,8 @@ static int evict_color(struct drm_mm *mm,
 
 	drm_mm_scan_init_with_range(&scan, mm,
 				    size, alignment, color,
-				    range_start, range_end);
+				    range_start, range_end,
+				    mode->create_flags);
 	if (!evict_nodes(&scan,
 			 nodes, order, count,
 			 &evict_list))
-- 
cgit 


From 3fa489dabea9a1cb0656e2da90354f7c4e53f890 Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 22 Dec 2016 08:36:36 +0000
Subject: drm: Apply tight eviction scanning to color_adjust

Using mm->color_adjust makes the eviction scanner much tricker since we
don't know the actual neighbours of the target hole until after it is
created (after scanning is complete). To work out whether we need to
evict the neighbours because they impact upon the hole, we have to then
check the hole afterwards - requiring an extra step in the user of the
eviction scanner when they apply color_adjust.

v2: Massage kerneldoc.

Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20161222083641.2691-34-chris@chris-wilson.co.uk
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 20 ++++++++++++++++++--
 1 file changed, 18 insertions(+), 2 deletions(-)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index 1bbfc24342c5..f609e4f1eeaf 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -1162,6 +1162,7 @@ static bool evict_nodes(struct drm_mm_scan *scan,
 			struct evict_node *nodes,
 			unsigned int *order,
 			unsigned int count,
+			bool use_color,
 			struct list_head *evict_list)
 {
 	struct evict_node *e, *en;
@@ -1186,6 +1187,21 @@ static bool evict_nodes(struct drm_mm_scan *scan,
 	list_for_each_entry(e, evict_list, link)
 		drm_mm_remove_node(&e->node);
 
+	if (use_color) {
+		struct drm_mm_node *node;
+
+		while ((node = drm_mm_scan_color_evict(scan))) {
+			e = container_of(node, typeof(*e), node);
+			drm_mm_remove_node(&e->node);
+			list_add(&e->link, evict_list);
+		}
+	} else {
+		if (drm_mm_scan_color_evict(scan)) {
+			pr_err("drm_mm_scan_color_evict unexpectedly reported overlapping nodes!\n");
+			return false;
+		}
+	}
+
 	return true;
 }
 
@@ -1299,7 +1315,7 @@ static int evict_something(struct drm_mm *mm,
 				    range_start, range_end,
 				    mode->create_flags);
 	if (!evict_nodes(&scan,
-			 nodes, order, count,
+			 nodes, order, count, false,
 			 &evict_list))
 		return -EINVAL;
 
@@ -1878,7 +1894,7 @@ static int evict_color(struct drm_mm *mm,
 				    range_start, range_end,
 				    mode->create_flags);
 	if (!evict_nodes(&scan,
-			 nodes, order, count,
+			 nodes, order, count, true,
 			 &evict_list))
 		return -EINVAL;
 
-- 
cgit 


From 3f85fb3462dc1c87a9353eb38714468d46248b2e Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 22 Dec 2016 08:36:37 +0000
Subject: drm: Wrap drm_mm_node.hole_follows

Insulate users from changes to the internal hole tracking within
struct drm_mm_node by using an accessor for hole_follows.

Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
[danvet: resolve conflicts in i915_vma.c]
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 18 ++++++++++--------
 1 file changed, 10 insertions(+), 8 deletions(-)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index f609e4f1eeaf..2ce92f4dcfc7 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -63,7 +63,7 @@ static bool assert_no_holes(const struct drm_mm *mm)
 	}
 
 	drm_mm_for_each_node(hole, mm) {
-		if (hole->hole_follows) {
+		if (drm_mm_hole_follows(hole)) {
 			pr_err("Hole follows node, expected none!\n");
 			return false;
 		}
@@ -125,7 +125,7 @@ static bool assert_continuous(const struct drm_mm *mm, u64 size)
 			return false;
 		}
 
-		if (node->hole_follows) {
+		if (drm_mm_hole_follows(node)) {
 			pr_err("node[%ld] is followed by a hole!\n", n);
 			return false;
 		}
@@ -828,7 +828,8 @@ static bool assert_contiguous_in_range(struct drm_mm *mm,
 			return false;
 		}
 
-		if (node->hole_follows && drm_mm_hole_node_end(node) < end) {
+		if (drm_mm_hole_follows(node) &&
+		    drm_mm_hole_node_end(node) < end) {
 			pr_err("node %d is followed by a hole!\n", n);
 			return false;
 		}
@@ -1337,11 +1338,12 @@ static int evict_something(struct drm_mm *mm,
 		err = -EINVAL;
 	}
 
-	if (!assert_node(&tmp, mm, size, alignment, 0) || tmp.hole_follows) {
+	if (!assert_node(&tmp, mm, size, alignment, 0) ||
+	    drm_mm_hole_follows(&tmp)) {
 		pr_err("Inserted did not fill the eviction hole: size=%lld [%d], align=%d [rem=%lld], start=%llx, hole-follows?=%d\n",
 		       tmp.size, size,
 		       alignment, misalignment(&tmp, alignment),
-		       tmp.start, tmp.hole_follows);
+		       tmp.start, drm_mm_hole_follows(&tmp));
 		err = -EINVAL;
 	}
 
@@ -1618,7 +1620,7 @@ static int igt_topdown(void *ignored)
 				goto out;
 			}
 
-			if (nodes[n].hole_follows) {
+			if (drm_mm_hole_follows(&nodes[n])) {
 				pr_err("hole after topdown insert %d, start=%llx\n, size=%u",
 				       n, nodes[n].start, size);
 				goto out;
@@ -1650,7 +1652,7 @@ static int igt_topdown(void *ignored)
 					goto out;
 				}
 
-				if (node->hole_follows) {
+				if (drm_mm_hole_follows(node)) {
 					pr_err("hole after topdown insert %d/%d, start=%llx\n",
 					       m, n, node->start);
 					goto out;
@@ -1705,7 +1707,7 @@ static void separate_adjacent_colors(const struct drm_mm_node *node,
 
 static bool colors_abutt(const struct drm_mm_node *node)
 {
-	if (!node->hole_follows &&
+	if (!drm_mm_hole_follows(node) &&
 	    list_next_entry(node, node_list)->allocated) {
 		pr_err("colors abutt; %ld [%llx + %llx] is next to %ld [%llx + %llx]!\n",
 		       node->color, node->start, node->size,
-- 
cgit 


From b5c3714fe8789745521d8351d75049b9c6a0d26b Mon Sep 17 00:00:00 2001
From: Daniel Vetter <daniel.vetter@ffwll.ch>
Date: Thu, 29 Dec 2016 12:09:24 +0100
Subject: drm/mm: Convert to drm_printer
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Including all drivers. I thought about keeping small compat functions
to avoid having to change all drivers. But I really like the
drm_printer idea, so figured spreading it more widely is a good thing.

v2: Review from Chris:
- Natural argument order and better name for drm_mm_print.
- show_mm() macro in the selftest.

Cc: Rob Clark <robdclark@gmail.com>
Cc: Russell King <rmk+kernel@armlinux.org.uk>
Cc: Alex Deucher <alexander.deucher@amd.com>
Cc: Christian König <christian.koenig@amd.com>
Cc: Lucas Stach <l.stach@pengutronix.de>
Cc: Tomi Valkeinen <tomi.valkeinen@ti.com>
Cc: Thierry Reding <thierry.reding@gmail.com>
Cc: Jyri Sarha <jsarha@ti.com>
Reviewed-by: Chris Wilson <chris@chris-wilson.co.uk>
Signed-off-by: Daniel Vetter <daniel.vetter@intel.com>
Link: http://patchwork.freedesktop.org/patch/msgid/1483009764-8281-1-git-send-email-daniel.vetter@ffwll.ch
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index 2ce92f4dcfc7..6d2a5cd211f3 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -194,6 +194,10 @@ static bool assert_node(struct drm_mm_node *node, struct drm_mm *mm,
 	return ok;
 }
 
+#define show_mm(mm) do { \
+	struct drm_printer __p = drm_debug_printer(__func__); \
+	drm_mm_print((mm), &__p); } while (0)
+
 static int igt_init(void *ignored)
 {
 	const unsigned int size = 4096;
@@ -250,7 +254,7 @@ static int igt_init(void *ignored)
 
 out:
 	if (ret)
-		drm_mm_debug_table(&mm, __func__);
+		show_mm(&mm);
 	drm_mm_takedown(&mm);
 	return ret;
 }
@@ -286,7 +290,7 @@ static int igt_debug(void *ignored)
 		return ret;
 	}
 
-	drm_mm_debug_table(&mm, __func__);
+	show_mm(&mm);
 	return 0;
 }
 
@@ -2031,7 +2035,7 @@ static int igt_color_evict(void *ignored)
 	ret = 0;
 out:
 	if (ret)
-		drm_mm_debug_table(&mm, __func__);
+		show_mm(&mm);
 	drm_mm_for_each_node_safe(node, next, &mm)
 		drm_mm_remove_node(node);
 	drm_mm_takedown(&mm);
@@ -2130,7 +2134,7 @@ static int igt_color_evict_range(void *ignored)
 	ret = 0;
 out:
 	if (ret)
-		drm_mm_debug_table(&mm, __func__);
+		show_mm(&mm);
 	drm_mm_for_each_node_safe(node, next, &mm)
 		drm_mm_remove_node(node);
 	drm_mm_takedown(&mm);
-- 
cgit 


From 95b8c64afad824014178df6b396c6ba0f4b1b80a Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Tue, 10 Jan 2017 14:40:31 +0000
Subject: drm: Fix error handling in drm_mm eviction kselftest

        drivers/gpu/drm/selftests/test-drm_mm.c:1277 evict_everything()
        warn: calling list_del() inside list_for_each

The list_del() inside the error handling in the eviction loop is
overkill. We have to undo the eviction scan to return the drm_mm back to
a recoverable state, so have to iterate over the full list, but we only
want to report the error once and once we have an error we can return
early.

Reported-by: Dan Carpenter <dan.carpenter@oracle.com>
Fixes: 560b32842912 ("drm: kselftest for drm_mm and eviction")
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Cc: Daniel Vetter <daniel.vetter@ffwll.ch>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20170110144031.7609-1-chris@chris-wilson.co.uk
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 12 +++++++++---
 1 file changed, 9 insertions(+), 3 deletions(-)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index 6d2a5cd211f3..6df53e6c1308 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -1274,13 +1274,19 @@ static bool evict_everything(struct drm_mm *mm,
 		if (drm_mm_scan_add_block(&scan, &e->node))
 			break;
 	}
+
+	err = 0;
 	list_for_each_entry(e, &evict_list, link) {
 		if (!drm_mm_scan_remove_block(&scan, &e->node)) {
-			pr_err("Node %lld not marked for eviction!\n",
-			       e->node.start);
-			list_del(&e->link);
+			if (!err) {
+				pr_err("Node %lld not marked for eviction!\n",
+				       e->node.start);
+				err = -EINVAL;
+			}
 		}
 	}
+	if (err)
+		return false;
 
 	list_for_each_entry(e, &evict_list, link)
 		drm_mm_remove_node(&e->node);
-- 
cgit 


From 4e64e5539d152e202ad6eea2b6f65f3ab58d9428 Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 2 Feb 2017 21:04:38 +0000
Subject: drm: Improve drm_mm search (and fix topdown allocation) with rbtrees
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

The drm_mm range manager claimed to support top-down insertion, but it
was neither searching for the top-most hole that could fit the
allocation request nor fitting the request to the hole correctly.

In order to search the range efficiently, we create a secondary index
for the holes using either their size or their address. This index
allows us to find the smallest hole or the hole at the bottom or top of
the range efficiently, whilst keeping the hole stack to rapidly service
evictions.

v2: Search for holes both high and low. Rename flags to mode.
v3: Discover rb_entry_safe() and use it!
v4: Kerneldoc for enum drm_mm_insert_mode.

Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Cc: Alex Deucher <alexander.deucher@amd.com>
Cc: "Christian König" <christian.koenig@amd.com>
Cc: David Airlie <airlied@linux.ie>
Cc: Russell King <rmk+kernel@armlinux.org.uk>
Cc: Daniel Vetter <daniel.vetter@intel.com>
Cc: Jani Nikula <jani.nikula@linux.intel.com>
Cc: Sean Paul <seanpaul@chromium.org>
Cc: Lucas Stach <l.stach@pengutronix.de>
Cc: Christian Gmeiner <christian.gmeiner@gmail.com>
Cc: Rob Clark <robdclark@gmail.com>
Cc: Thierry Reding <thierry.reding@gmail.com>
Cc: Stephen Warren <swarren@wwwdotorg.org>
Cc: Alexandre Courbot <gnurou@gmail.com>
Cc: Eric Anholt <eric@anholt.net>
Cc: Sinclair Yeh <syeh@vmware.com>
Cc: Thomas Hellstrom <thellstrom@vmware.com>
Reviewed-by: Alex Deucher <alexander.deucher@amd.com>
Reviewed-by: Sinclair Yeh <syeh@vmware.com> # vmwgfx
Reviewed-by: Lucas Stach <l.stach@pengutronix.de> #etnaviv
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20170202210438.28702-1-chris@chris-wilson.co.uk
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 58 +++++++++++++++------------------
 1 file changed, 26 insertions(+), 32 deletions(-)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index 6df53e6c1308..bb5b7480e0b4 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -22,23 +22,24 @@ static unsigned int max_iterations = 8192;
 static unsigned int max_prime = 128;
 
 enum {
-	DEFAULT,
-	TOPDOWN,
 	BEST,
+	BOTTOMUP,
+	TOPDOWN,
+	EVICT,
 };
 
 static const struct insert_mode {
 	const char *name;
-	unsigned int search_flags;
-	unsigned int create_flags;
+	enum drm_mm_insert_mode mode;
 } insert_modes[] = {
-	[DEFAULT] = { "default", DRM_MM_SEARCH_DEFAULT, DRM_MM_CREATE_DEFAULT },
-	[TOPDOWN] = { "top-down", DRM_MM_SEARCH_BELOW, DRM_MM_CREATE_TOP },
-	[BEST] = { "best", DRM_MM_SEARCH_BEST, DRM_MM_CREATE_DEFAULT },
+	[BEST] = { "best", DRM_MM_INSERT_BEST },
+	[BOTTOMUP] = { "bottom-up", DRM_MM_INSERT_LOW },
+	[TOPDOWN] = { "top-down", DRM_MM_INSERT_HIGH },
+	[EVICT] = { "evict", DRM_MM_INSERT_EVICT },
 	{}
 }, evict_modes[] = {
-	{ "default", DRM_MM_SEARCH_DEFAULT, DRM_MM_CREATE_DEFAULT },
-	{ "top-down", DRM_MM_SEARCH_BELOW, DRM_MM_CREATE_TOP },
+	{ "bottom-up", DRM_MM_INSERT_LOW },
+	{ "top-down", DRM_MM_INSERT_HIGH },
 	{}
 };
 
@@ -526,8 +527,7 @@ static bool expect_insert(struct drm_mm *mm, struct drm_mm_node *node,
 
 	err = drm_mm_insert_node_generic(mm, node,
 					 size, alignment, color,
-					 mode->search_flags,
-					 mode->create_flags);
+					 mode->mode);
 	if (err) {
 		pr_err("insert (size=%llu, alignment=%llu, color=%lu, mode=%s) failed with err=%d\n",
 		       size, alignment, color, mode->name, err);
@@ -547,7 +547,7 @@ static bool expect_insert_fail(struct drm_mm *mm, u64 size)
 	struct drm_mm_node tmp = {};
 	int err;
 
-	err = drm_mm_insert_node(mm, &tmp, size, 0, DRM_MM_SEARCH_DEFAULT);
+	err = drm_mm_insert_node(mm, &tmp, size);
 	if (likely(err == -ENOSPC))
 		return true;
 
@@ -753,11 +753,10 @@ static bool expect_insert_in_range(struct drm_mm *mm, struct drm_mm_node *node,
 {
 	int err;
 
-	err = drm_mm_insert_node_in_range_generic(mm, node,
-						  size, alignment, color,
-						  range_start, range_end,
-						  mode->search_flags,
-						  mode->create_flags);
+	err = drm_mm_insert_node_in_range(mm, node,
+					  size, alignment, color,
+					  range_start, range_end,
+					  mode->mode);
 	if (err) {
 		pr_err("insert (size=%llu, alignment=%llu, color=%lu, mode=%s) nto range [%llx, %llx] failed with err=%d\n",
 		       size, alignment, color, mode->name,
@@ -781,11 +780,10 @@ static bool expect_insert_in_range_fail(struct drm_mm *mm,
 	struct drm_mm_node tmp = {};
 	int err;
 
-	err = drm_mm_insert_node_in_range_generic(mm, &tmp,
-						  size, 0, 0,
-						  range_start, range_end,
-						  DRM_MM_SEARCH_DEFAULT,
-						  DRM_MM_CREATE_DEFAULT);
+	err = drm_mm_insert_node_in_range(mm, &tmp,
+					  size, 0, 0,
+					  range_start, range_end,
+					  0);
 	if (likely(err == -ENOSPC))
 		return true;
 
@@ -1324,7 +1322,7 @@ static int evict_something(struct drm_mm *mm,
 	drm_mm_scan_init_with_range(&scan, mm,
 				    size, alignment, 0,
 				    range_start, range_end,
-				    mode->create_flags);
+				    mode->mode);
 	if (!evict_nodes(&scan,
 			 nodes, order, count, false,
 			 &evict_list))
@@ -1332,8 +1330,7 @@ static int evict_something(struct drm_mm *mm,
 
 	memset(&tmp, 0, sizeof(tmp));
 	err = drm_mm_insert_node_generic(mm, &tmp, size, alignment, 0,
-					 mode->search_flags,
-					 mode->create_flags);
+					 DRM_MM_INSERT_EVICT);
 	if (err) {
 		pr_err("Failed to insert into eviction hole: size=%d, align=%d\n",
 		       size, alignment);
@@ -1408,8 +1405,7 @@ static int igt_evict(void *ignored)
 	ret = -EINVAL;
 	drm_mm_init(&mm, 0, size);
 	for (n = 0; n < size; n++) {
-		err = drm_mm_insert_node(&mm, &nodes[n].node, 1, 0,
-					 DRM_MM_SEARCH_DEFAULT);
+		err = drm_mm_insert_node(&mm, &nodes[n].node, 1);
 		if (err) {
 			pr_err("insert failed, step %d\n", n);
 			ret = err;
@@ -1517,8 +1513,7 @@ static int igt_evict_range(void *ignored)
 	ret = -EINVAL;
 	drm_mm_init(&mm, 0, size);
 	for (n = 0; n < size; n++) {
-		err = drm_mm_insert_node(&mm, &nodes[n].node, 1, 0,
-					 DRM_MM_SEARCH_DEFAULT);
+		err = drm_mm_insert_node(&mm, &nodes[n].node, 1);
 		if (err) {
 			pr_err("insert failed, step %d\n", n);
 			ret = err;
@@ -1904,7 +1899,7 @@ static int evict_color(struct drm_mm *mm,
 	drm_mm_scan_init_with_range(&scan, mm,
 				    size, alignment, color,
 				    range_start, range_end,
-				    mode->create_flags);
+				    mode->mode);
 	if (!evict_nodes(&scan,
 			 nodes, order, count, true,
 			 &evict_list))
@@ -1912,8 +1907,7 @@ static int evict_color(struct drm_mm *mm,
 
 	memset(&tmp, 0, sizeof(tmp));
 	err = drm_mm_insert_node_generic(mm, &tmp, size, alignment, color,
-					 mode->search_flags,
-					 mode->create_flags);
+					 DRM_MM_INSERT_EVICT);
 	if (err) {
 		pr_err("Failed to insert into eviction hole: size=%d, align=%d, color=%lu, err=%d\n",
 		       size, alignment, color, err);
-- 
cgit 


From bb18dfcc640d0551073e756e0af2ff60bea89e6d Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 2 Feb 2017 11:44:34 +0000
Subject: drm: kselftest for drm_mm and bottom-up allocation

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

Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20170202114434.3060-2-chris@chris-wilson.co.uk
---
 drivers/gpu/drm/selftests/test-drm_mm.c | 100 ++++++++++++++++++++++++++++++++
 1 file changed, 100 insertions(+)

(limited to 'drivers/gpu/drm/selftests/test-drm_mm.c')

diff --git a/drivers/gpu/drm/selftests/test-drm_mm.c b/drivers/gpu/drm/selftests/test-drm_mm.c
index bb5b7480e0b4..1e71bc182ca9 100644
--- a/drivers/gpu/drm/selftests/test-drm_mm.c
+++ b/drivers/gpu/drm/selftests/test-drm_mm.c
@@ -1697,6 +1697,106 @@ err:
 	return ret;
 }
 
+static int igt_bottomup(void *ignored)
+{
+	const struct insert_mode *bottomup = &insert_modes[BOTTOMUP];
+	DRM_RND_STATE(prng, random_seed);
+	const unsigned int count = 8192;
+	unsigned int size;
+	unsigned long *bitmap;
+	struct drm_mm mm;
+	struct drm_mm_node *nodes, *node, *next;
+	unsigned int *order, n, m, o = 0;
+	int ret;
+
+	/* Like igt_topdown, but instead of searching for the last hole,
+	 * we search for the first.
+	 */
+
+	ret = -ENOMEM;
+	nodes = vzalloc(count * sizeof(*nodes));
+	if (!nodes)
+		goto err;
+
+	bitmap = kzalloc(count / BITS_PER_LONG * sizeof(unsigned long),
+			 GFP_TEMPORARY);
+	if (!bitmap)
+		goto err_nodes;
+
+	order = drm_random_order(count, &prng);
+	if (!order)
+		goto err_bitmap;
+
+	ret = -EINVAL;
+	for (size = 1; size <= 64; size <<= 1) {
+		drm_mm_init(&mm, 0, size*count);
+		for (n = 0; n < count; n++) {
+			if (!expect_insert(&mm, &nodes[n],
+					   size, 0, n,
+					   bottomup)) {
+				pr_err("bottomup insert failed, size %u step %d\n", size, n);
+				goto out;
+			}
+
+			if (!assert_one_hole(&mm, size*(n + 1), size*count))
+				goto out;
+		}
+
+		if (!assert_continuous(&mm, size))
+			goto out;
+
+		drm_random_reorder(order, count, &prng);
+		for_each_prime_number_from(n, 1, min(count, max_prime)) {
+			for (m = 0; m < n; m++) {
+				node = &nodes[order[(o + m) % count]];
+				drm_mm_remove_node(node);
+				__set_bit(node_index(node), bitmap);
+			}
+
+			for (m = 0; m < n; m++) {
+				unsigned int first;
+
+				node = &nodes[order[(o + m) % count]];
+				if (!expect_insert(&mm, node,
+						   size, 0, 0,
+						   bottomup)) {
+					pr_err("insert failed, step %d/%d\n", m, n);
+					goto out;
+				}
+
+				first = find_first_bit(bitmap, count);
+				if (node_index(node) != first) {
+					pr_err("node %d/%d not inserted into bottom hole, expected %d, found %d\n",
+					       m, n, first, node_index(node));
+					goto out;
+				}
+				__clear_bit(first, bitmap);
+			}
+
+			DRM_MM_BUG_ON(find_first_bit(bitmap, count) != count);
+
+			o += n;
+		}
+
+		drm_mm_for_each_node_safe(node, next, &mm)
+			drm_mm_remove_node(node);
+		DRM_MM_BUG_ON(!drm_mm_clean(&mm));
+	}
+
+	ret = 0;
+out:
+	drm_mm_for_each_node_safe(node, next, &mm)
+		drm_mm_remove_node(node);
+	drm_mm_takedown(&mm);
+	kfree(order);
+err_bitmap:
+	kfree(bitmap);
+err_nodes:
+	vfree(nodes);
+err:
+	return ret;
+}
+
 static void separate_adjacent_colors(const struct drm_mm_node *node,
 				     unsigned long color,
 				     u64 *start,
-- 
cgit