[Intel-gfx] [PATCH] drm/i915: Add some unit tests for the breadcrumb rbtree

[Chris Wilson]

First retroactive test, make sure that the waiters are in global seqno
order after random inserts and removals.

Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
---
 drivers/gpu/drm/i915/i915_selftests.h    |   1 +
 drivers/gpu/drm/i915/intel_breadcrumbs.c | 161 +++++++++++++++++++++++++++++++
 2 files changed, 162 insertions(+)

diff --git a/drivers/gpu/drm/i915/i915_selftests.h b/drivers/gpu/drm/i915/i915_selftests.h
index 3f8015c8a520..9562ec81c781 100644
--- a/drivers/gpu/drm/i915/i915_selftests.h
+++ b/drivers/gpu/drm/i915/i915_selftests.h
@@ -8,4 +8,5 @@
  *
  * Tests are executed in reverse order by igt/drv_selftest
  */
+selftest(breadcrumbs, intel_breadcrumbs_selftest)
 selftest(sanitycheck, i915_selftest_sanitycheck) /* keep last */
diff --git a/drivers/gpu/drm/i915/intel_breadcrumbs.c b/drivers/gpu/drm/i915/intel_breadcrumbs.c
index 53ae7884babd..604ccd618ac8 100644
--- a/drivers/gpu/drm/i915/intel_breadcrumbs.c
+++ b/drivers/gpu/drm/i915/intel_breadcrumbs.c
@@ -25,6 +25,7 @@
 #include <linux/kthread.h>
 
 #include "i915_drv.h"
+#include "i915_selftest.h"
 
 static void intel_breadcrumbs_hangcheck(unsigned long data)
 {
@@ -661,3 +662,163 @@ unsigned int intel_breadcrumbs_busy(struct drm_i915_private *i915)
 
 	return mask;
 }
+
+#if IS_ENABLED(CONFIG_DRM_I915_SELFTEST)
+#include <linux/random.h>
+
+static struct intel_engine_cs *mock_engine(const char *name)
+{
+	struct intel_engine_cs *engine;
+	static int id;
+
+	engine = kzalloc(sizeof(*engine) + 4096, GFP_KERNEL);
+	if (!engine)
+		return NULL;
+
+	/* minimal engine setup for seqno */
+	engine->name = name;
+	engine->id = id++;
+	engine->status_page.page_addr = (void *)(engine + 1);
+
+	/* minimal breadcrumbs init */
+	spin_lock_init(&engine->breadcrumbs.lock);
+
+	return engine;
+}
+
+static int *get_random_order(int count)
+{
+	int *order;
+	int n, r, tmp;
+
+	order = kmalloc_array(count, sizeof(*order), GFP_TEMPORARY);
+	if (!order)
+		return order;
+
+	for (n = 0; n < count; n++)
+		order[n] = n;
+
+	for (n = count - 1; n > 1; n--) {
+		r = get_random_int() % (n + 1);
+		if (r != n) {
+			tmp = order[n];
+			order[n] = order[r];
+			order[r] = tmp;
+		}
+	}
+
+	return order;
+}
+
+static int check_rbtree(struct intel_engine_cs *engine,
+			const unsigned long *bitmap,
+			struct intel_wait *waiters,
+			const int count)
+{
+	struct intel_breadcrumbs *b = &engine->breadcrumbs;
+	struct rb_node *rb;
+	int first;
+
+	if (&b->first_wait->node != rb_first(&b->waiters)) {
+		pr_err("First waiter does not match first element of wait-tree\n");
+		return -EINVAL;
+	}
+
+	first = find_first_bit(bitmap, count);
+	for (rb = rb_first(&b->waiters); rb; rb = rb_next(rb)) {
+		struct intel_wait *w = container_of(rb, typeof(*w), node);
+		int idx = w - waiters;
+
+		if (!test_bit(idx, bitmap)) {
+			pr_err("waiter[%d, seqno=%d] removed but still in wait-tree\n",
+			       idx, w->seqno);
+			return -EINVAL;
+		}
+
+		if (first != idx) {
+			pr_err("waiter[%d, seqno=%d] does not match expected next element in tree [%d]\n",
+			       idx, w->seqno, first);
+			return -EINVAL;
+		}
+
+		first = find_next_bit(bitmap, count, first + 1);
+	}
+
+	return 0;
+}
+
+static int igt_random_insert_remove(void)
+{
+	struct intel_engine_cs *engine;
+	struct intel_wait *waiters;
+	const int count = 4096;
+	int *in_order, *out_order;
+	unsigned long *bitmap;
+	int err = -ENOMEM;
+	int n;
+
+	engine = mock_engine("mock");
+	if (!engine)
+		goto out;
+
+	waiters = kmalloc_array(count, sizeof(*waiters), GFP_KERNEL);
+	if (!waiters)
+		goto out_engines;
+
+	bitmap = kzalloc(count / BITS_PER_LONG * sizeof(*bitmap), GFP_KERNEL);
+	if (!bitmap)
+		goto out_waiters;
+
+	in_order = get_random_order(count);
+	if (!in_order)
+		goto out_bitmap;
+
+	out_order = get_random_order(count);
+	if (!out_order)
+		goto out_order;
+
+	for (n = 0; n < count; n++)
+		intel_wait_init(&waiters[n], 0x1000 + n);
+
+	err = check_rbtree(engine, bitmap, waiters, count);
+	for (n = 0; n < count; n++) {
+		int i = in_order[n];
+
+		intel_engine_add_wait(engine, &waiters[i]);
+		__set_bit(i, bitmap);
+
+		err |= check_rbtree(engine, bitmap, waiters, count);
+	}
+	for (n = 0; n < count; n++) {
+		int i = out_order[n];
+
+		intel_engine_remove_wait(engine, &waiters[i]);
+		__clear_bit(i, bitmap);
+
+		err |= check_rbtree(engine, bitmap, waiters, count);
+	}
+
+	kfree(out_order);
+out_order:
+	kfree(in_order);
+out_bitmap:
+	kfree(bitmap);
+out_waiters:
+	kfree(waiters);
+out_engines:
+	kfree(engine);
+out:
+	return err;
+}
+
+int intel_breadcrumbs_selftest(void)
+{
+	int err;
+
+	err = igt_random_insert_remove();
+	if (err)
+		return err;
+
+	return 0;
+}
+#endif
-- 
2.10.2