[PATCH 03/45] drm/i915: Add unit tests for the breadcrumb rbtree, insert/remove

[Tvrtko Ursulin]

On 06/12/2016 00:12, Chris Wilson wrote:
> 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 | 198 +++++++++++++++++++++++++++++++
>  drivers/gpu/drm/i915/intel_ringbuffer.h  |   1 +
>  3 files changed, 200 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..2c02939fd5b6 100644
> --- a/drivers/gpu/drm/i915/intel_breadcrumbs.c
> +++ b/drivers/gpu/drm/i915/intel_breadcrumbs.c
> @@ -109,6 +109,11 @@ static void __intel_breadcrumbs_enable_irq(struct intel_breadcrumbs *b)
>  	if (b->rpm_wakelock)
>  		return;
>
> +	if (unlikely(b->mock)) {
> +		b->rpm_wakelock = true;
> +		return;
> +	}

I think it will be very important to mark these very clearly both in 
code and declarations.

Quick idea:

struct ... {
	I915_SELFTEST_DECLARE(bool : 1, mock);
};

I915_SELFTEST() {
	if (unlikely(b->mock)) {
		b->rpm_wakelock = true;
		return;
	}
}

Extra benefit that it all gets compiled when not enabled.

> +
>  	/* Since we are waiting on a request, the GPU should be busy
>  	 * and should have its own rpm reference. For completeness,
>  	 * record an rpm reference for ourselves to cover the
> @@ -143,6 +148,11 @@ static void __intel_breadcrumbs_disable_irq(struct intel_breadcrumbs *b)
>  	if (!b->rpm_wakelock)
>  		return;
>
> +	if (unlikely(b->mock)) {
> +		b->rpm_wakelock = false;
> +		return;
> +	}
> +
>  	if (b->irq_enabled) {
>  		irq_disable(engine);
>  		b->irq_enabled = false;
> @@ -661,3 +671,191 @@ unsigned int intel_breadcrumbs_busy(struct drm_i915_private *i915)
>
>  	return mask;
>  }
> +
> +#if IS_ENABLED(CONFIG_DRM_I915_SELFTEST)
> +#include <linux/random.h>
> +
> +#include "i915_selftest.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);
> +	engine->breadcrumbs.mock = true;
> +
> +	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,
> +			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 *ignore)
> +{
> +	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);

This is quite big - around 147k if I got it right. At which point do we 
switch over to drm_malloc_ab?

> +	if (!waiters)
> +		goto out_engines;
> +
> +	bitmap = kcalloc(DIV_ROUND_UP(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);
> +	if (err)
> +		goto err;
> +
> +	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);
> +		if (err)
> +			goto err;
> +	}
> +	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);
> +		if (err)
> +			goto err;
> +	}
> +
> +	err = check_rbtree_empty(engine);
> +err:
> +	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)
> +{
> +	static const struct i915_subtest tests[] = {
> +		SUBTEST(igt_random_insert_remove),
> +	};
> +
> +	return i915_subtests(tests, NULL);
> +}
> +#endif
> diff --git a/drivers/gpu/drm/i915/intel_ringbuffer.h b/drivers/gpu/drm/i915/intel_ringbuffer.h
> index 3f43adefd1c0..308931172aa8 100644
> --- a/drivers/gpu/drm/i915/intel_ringbuffer.h
> +++ b/drivers/gpu/drm/i915/intel_ringbuffer.h
> @@ -244,6 +244,7 @@ struct intel_engine_cs {
>
>  		bool irq_enabled : 1;
>  		bool rpm_wakelock : 1;
> +		bool mock : 1;
>  	} breadcrumbs;
>
>  	/*
>

Nice test.

Regards,

Tvrtko