drm/i915: Add unit tests for the breadcrumb rbtree, insert/remove
First retroactive test, make sure that the waiters are in global seqno
order after random inserts and removals.
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Tvrtko Ursulin <tvrtko.ursulin@intel.com>
Link: http://patchwork.freedesktop.org/patch/msgid/20170213171558.20942-3-chris@chris-wilson.co.uk
diff --git a/drivers/gpu/drm/i915/selftests/intel_breadcrumbs.c b/drivers/gpu/drm/i915/selftests/intel_breadcrumbs.c
new file mode 100644
index 0000000..6b5acf9
--- /dev/null
+++ b/drivers/gpu/drm/i915/selftests/intel_breadcrumbs.c
@@ -0,0 +1,172 @@
+/*
+ * Copyright © 2016 Intel Corporation
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ *
+ */
+
+#include "../i915_selftest.h"
+#include "i915_random.h"
+
+#include "mock_engine.h"
+
+static int check_rbtree(struct intel_engine_cs *engine,
+ const unsigned long *bitmap,
+ const struct intel_wait *waiters,
+ const int count)
+{
+ struct intel_breadcrumbs *b = &engine->breadcrumbs;
+ struct rb_node *rb;
+ int n;
+
+ if (&b->first_wait->node != rb_first(&b->waiters)) {
+ pr_err("First waiter does not match first element of wait-tree\n");
+ return -EINVAL;
+ }
+
+ n = 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 (n != idx) {
+ pr_err("waiter[%d, seqno=%d] does not match expected next element in tree [%d]\n",
+ idx, w->seqno, n);
+ return -EINVAL;
+ }
+
+ n = find_next_bit(bitmap, count, n + 1);
+ }
+
+ return 0;
+}
+
+static int check_rbtree_empty(struct intel_engine_cs *engine)
+{
+ struct intel_breadcrumbs *b = &engine->breadcrumbs;
+
+ if (b->first_wait) {
+ pr_err("Empty breadcrumbs still has a waiter\n");
+ return -EINVAL;
+ }
+
+ if (!RB_EMPTY_ROOT(&b->waiters)) {
+ pr_err("Empty breadcrumbs, but wait-tree not empty\n");
+ return -EINVAL;
+ }
+
+ return 0;
+}
+
+static int igt_random_insert_remove(void *arg)
+{
+ const u32 seqno_bias = 0x1000;
+ I915_RND_STATE(prng);
+ struct intel_engine_cs *engine = arg;
+ struct intel_wait *waiters;
+ const int count = 4096;
+ unsigned int *order;
+ unsigned long *bitmap;
+ int err = -ENOMEM;
+ int n;
+
+ mock_engine_reset(engine);
+
+ waiters = drm_malloc_gfp(count, sizeof(*waiters), GFP_TEMPORARY);
+ if (!waiters)
+ goto out_engines;
+
+ bitmap = kcalloc(DIV_ROUND_UP(count, BITS_PER_LONG), sizeof(*bitmap),
+ GFP_TEMPORARY);
+ if (!bitmap)
+ goto out_waiters;
+
+ order = i915_random_order(count, &prng);
+ if (!order)
+ goto out_bitmap;
+
+ for (n = 0; n < count; n++)
+ intel_wait_init(&waiters[n], seqno_bias + n);
+
+ err = check_rbtree(engine, bitmap, waiters, count);
+ if (err)
+ goto out_order;
+
+ /* Add and remove waiters into the rbtree in random order. At each
+ * step, we verify that the rbtree is correctly ordered.
+ */
+ for (n = 0; n < count; n++) {
+ int i = order[n];
+
+ intel_engine_add_wait(engine, &waiters[i]);
+ __set_bit(i, bitmap);
+
+ err = check_rbtree(engine, bitmap, waiters, count);
+ if (err)
+ goto out_order;
+ }
+
+ i915_random_reorder(order, count, &prng);
+ for (n = 0; n < count; n++) {
+ int i = order[n];
+
+ intel_engine_remove_wait(engine, &waiters[i]);
+ __clear_bit(i, bitmap);
+
+ err = check_rbtree(engine, bitmap, waiters, count);
+ if (err)
+ goto out_order;
+ }
+
+ err = check_rbtree_empty(engine);
+out_order:
+ kfree(order);
+out_bitmap:
+ kfree(bitmap);
+out_waiters:
+ drm_free_large(waiters);
+out_engines:
+ mock_engine_flush(engine);
+ return err;
+}
+
+int intel_breadcrumbs_mock_selftests(void)
+{
+ static const struct i915_subtest tests[] = {
+ SUBTEST(igt_random_insert_remove),
+ };
+ struct intel_engine_cs *engine;
+ int err;
+
+ engine = mock_engine("mock");
+ if (!engine)
+ return -ENOMEM;
+
+ err = i915_subtests(tests, engine);
+ kfree(engine);
+
+ return err;
+}