Re: [Intel-gfx] [CI 06/14] drm/i915/selftests: Measure set-priority duration

[Tvrtko Ursulin]

On 02/02/2021 15:14, Chris Wilson wrote:

As a topological sort, we expect it to run in linear graph time,
O(V+E). In removing the recursion, it is no longer a DFS but rather a
BFS, and performs as O(VE). Let's demonstrate how bad this is with a few
examples, and build a few test cases to verify a potential fix.

Signed-off-by: Chris Wilson 
---
  drivers/gpu/drm/i915/i915_scheduler.c |   4 +
  .../drm/i915/selftests/i915_live_selftests.h  |   1 +
  .../drm/i915/selftests/i915_perf_selftests.h  |   1 +
  .../gpu/drm/i915/selftests/i915_scheduler.c   | 672 ++
  4 files changed, 678 insertions(+)
  create mode 100644 drivers/gpu/drm/i915/selftests/i915_scheduler.c

diff --git a/drivers/gpu/drm/i915/i915_scheduler.c 
b/drivers/gpu/drm/i915/i915_scheduler.c
index 035e4be5d573..27bda7617b29 100644
--- a/drivers/gpu/drm/i915/i915_scheduler.c
+++ b/drivers/gpu/drm/i915/i915_scheduler.c
@@ -609,6 +609,10 @@ void i915_request_show_with_schedule(struct drm_printer *m,
rcu_read_unlock();
  }
  
+#if IS_ENABLED(CONFIG_DRM_I915_SELFTEST)

+#include "selftests/i915_scheduler.c"
+#endif
+
  static void i915_global_scheduler_shrink(void)
  {
kmem_cache_shrink(global.slab_dependencies);
diff --git a/drivers/gpu/drm/i915/selftests/i915_live_selftests.h 
b/drivers/gpu/drm/i915/selftests/i915_live_selftests.h
index a92c0e9b7e6b..2200a5baa68e 100644
--- a/drivers/gpu/drm/i915/selftests/i915_live_selftests.h
+++ b/drivers/gpu/drm/i915/selftests/i915_live_selftests.h
@@ -26,6 +26,7 @@ selftest(gt_mocs, intel_mocs_live_selftests)
  selftest(gt_pm, intel_gt_pm_live_selftests)
  selftest(gt_heartbeat, intel_heartbeat_live_selftests)
  selftest(requests, i915_request_live_selftests)
+selftest(scheduler, i915_scheduler_live_selftests)
  selftest(active, i915_active_live_selftests)
  selftest(objects, i915_gem_object_live_selftests)
  selftest(mman, i915_gem_mman_live_selftests)
diff --git a/drivers/gpu/drm/i915/selftests/i915_perf_selftests.h 
b/drivers/gpu/drm/i915/selftests/i915_perf_selftests.h
index c2389f8a257d..137e35283fee 100644
--- a/drivers/gpu/drm/i915/selftests/i915_perf_selftests.h
+++ b/drivers/gpu/drm/i915/selftests/i915_perf_selftests.h
@@ -17,5 +17,6 @@
   */
  selftest(engine_cs, intel_engine_cs_perf_selftests)
  selftest(request, i915_request_perf_selftests)
+selftest(scheduler, i915_scheduler_perf_selftests)
  selftest(blt, i915_gem_object_blt_perf_selftests)
  selftest(region, intel_memory_region_perf_selftests)
diff --git a/drivers/gpu/drm/i915/selftests/i915_scheduler.c 
b/drivers/gpu/drm/i915/selftests/i915_scheduler.c
new file mode 100644
index ..d095fab2ccec
--- /dev/null
+++ b/drivers/gpu/drm/i915/selftests/i915_scheduler.c
@@ -0,0 +1,672 @@
+// SPDX-License-Identifier: MIT
+/*
+ * Copyright © 2020 Intel Corporation
+ */
+
+#include "i915_selftest.h"
+
+#include "gt/intel_context.h"
+#include "gt/intel_gpu_commands.h"
+#include "gt/selftest_engine_heartbeat.h"
+#include "selftests/igt_spinner.h"
+#include "selftests/i915_random.h"
+
+static void scheduling_disable(struct intel_engine_cs *engine)
+{
+   engine->props.preempt_timeout_ms = 0;
+   engine->props.timeslice_duration_ms = 0;
+
+   st_engine_heartbeat_disable(engine);
+}
+
+static void scheduling_enable(struct intel_engine_cs *engine)
+{
+   st_engine_heartbeat_enable(engine);
+
+   engine->props.preempt_timeout_ms =
+   engine->defaults.preempt_timeout_ms;
+   engine->props.timeslice_duration_ms =
+   engine->defaults.timeslice_duration_ms;
+}
+
+static int first_engine(struct drm_i915_private *i915,
+   int (*chain)(struct intel_engine_cs *engine,
+unsigned long param,
+bool (*fn)(struct i915_request *rq,
+   unsigned long v,
+   unsigned long e)),
+   unsigned long param,
+   bool (*fn)(struct i915_request *rq,
+  unsigned long v, unsigned long e))
+{
+   struct intel_engine_cs *engine;
+
+   for_each_uabi_engine(engine, i915) {
+   if (!intel_engine_has_scheduler(engine))
+   continue;
+
+   return chain(engine, param, fn);
+   }
+
+   return 0;
+}
+
+static int all_engines(struct drm_i915_private *i915,
+  int (*chain)(struct intel_engine_cs *engine,
+   unsigned long param,
+   bool (*fn)(struct i915_request *rq,
+  unsigned long v,
+  unsigned long e)),
+  unsigned long param,
+  bool (*fn)(struct i915_request *rq,
+ unsigned long v, unsigned long e))
+{
+   struct intel_engine_cs *engine;
+  

[Intel-gfx] [CI 06/14] drm/i915/selftests: Measure set-priority duration

[Chris Wilson]

As a topological sort, we expect it to run in linear graph time,
O(V+E). In removing the recursion, it is no longer a DFS but rather a
BFS, and performs as O(VE). Let's demonstrate how bad this is with a few
examples, and build a few test cases to verify a potential fix.

Signed-off-by: Chris Wilson 
---
 drivers/gpu/drm/i915/i915_scheduler.c |   4 +
 .../drm/i915/selftests/i915_live_selftests.h  |   1 +
 .../drm/i915/selftests/i915_perf_selftests.h  |   1 +
 .../gpu/drm/i915/selftests/i915_scheduler.c   | 672 ++
 4 files changed, 678 insertions(+)
 create mode 100644 drivers/gpu/drm/i915/selftests/i915_scheduler.c

diff --git a/drivers/gpu/drm/i915/i915_scheduler.c 
b/drivers/gpu/drm/i915/i915_scheduler.c
index 035e4be5d573..27bda7617b29 100644
--- a/drivers/gpu/drm/i915/i915_scheduler.c
+++ b/drivers/gpu/drm/i915/i915_scheduler.c
@@ -609,6 +609,10 @@ void i915_request_show_with_schedule(struct drm_printer *m,
rcu_read_unlock();
 }
 
+#if IS_ENABLED(CONFIG_DRM_I915_SELFTEST)
+#include "selftests/i915_scheduler.c"
+#endif
+
 static void i915_global_scheduler_shrink(void)
 {
kmem_cache_shrink(global.slab_dependencies);
diff --git a/drivers/gpu/drm/i915/selftests/i915_live_selftests.h 
b/drivers/gpu/drm/i915/selftests/i915_live_selftests.h
index a92c0e9b7e6b..2200a5baa68e 100644
--- a/drivers/gpu/drm/i915/selftests/i915_live_selftests.h
+++ b/drivers/gpu/drm/i915/selftests/i915_live_selftests.h
@@ -26,6 +26,7 @@ selftest(gt_mocs, intel_mocs_live_selftests)
 selftest(gt_pm, intel_gt_pm_live_selftests)
 selftest(gt_heartbeat, intel_heartbeat_live_selftests)
 selftest(requests, i915_request_live_selftests)
+selftest(scheduler, i915_scheduler_live_selftests)
 selftest(active, i915_active_live_selftests)
 selftest(objects, i915_gem_object_live_selftests)
 selftest(mman, i915_gem_mman_live_selftests)
diff --git a/drivers/gpu/drm/i915/selftests/i915_perf_selftests.h 
b/drivers/gpu/drm/i915/selftests/i915_perf_selftests.h
index c2389f8a257d..137e35283fee 100644
--- a/drivers/gpu/drm/i915/selftests/i915_perf_selftests.h
+++ b/drivers/gpu/drm/i915/selftests/i915_perf_selftests.h
@@ -17,5 +17,6 @@
  */
 selftest(engine_cs, intel_engine_cs_perf_selftests)
 selftest(request, i915_request_perf_selftests)
+selftest(scheduler, i915_scheduler_perf_selftests)
 selftest(blt, i915_gem_object_blt_perf_selftests)
 selftest(region, intel_memory_region_perf_selftests)
diff --git a/drivers/gpu/drm/i915/selftests/i915_scheduler.c 
b/drivers/gpu/drm/i915/selftests/i915_scheduler.c
new file mode 100644
index ..d095fab2ccec
--- /dev/null
+++ b/drivers/gpu/drm/i915/selftests/i915_scheduler.c
@@ -0,0 +1,672 @@
+// SPDX-License-Identifier: MIT
+/*
+ * Copyright © 2020 Intel Corporation
+ */
+
+#include "i915_selftest.h"
+
+#include "gt/intel_context.h"
+#include "gt/intel_gpu_commands.h"
+#include "gt/selftest_engine_heartbeat.h"
+#include "selftests/igt_spinner.h"
+#include "selftests/i915_random.h"
+
+static void scheduling_disable(struct intel_engine_cs *engine)
+{
+   engine->props.preempt_timeout_ms = 0;
+   engine->props.timeslice_duration_ms = 0;
+
+   st_engine_heartbeat_disable(engine);
+}
+
+static void scheduling_enable(struct intel_engine_cs *engine)
+{
+   st_engine_heartbeat_enable(engine);
+
+   engine->props.preempt_timeout_ms =
+   engine->defaults.preempt_timeout_ms;
+   engine->props.timeslice_duration_ms =
+   engine->defaults.timeslice_duration_ms;
+}
+
+static int first_engine(struct drm_i915_private *i915,
+   int (*chain)(struct intel_engine_cs *engine,
+unsigned long param,
+bool (*fn)(struct i915_request *rq,
+   unsigned long v,
+   unsigned long e)),
+   unsigned long param,
+   bool (*fn)(struct i915_request *rq,
+  unsigned long v, unsigned long e))
+{
+   struct intel_engine_cs *engine;
+
+   for_each_uabi_engine(engine, i915) {
+   if (!intel_engine_has_scheduler(engine))
+   continue;
+
+   return chain(engine, param, fn);
+   }
+
+   return 0;
+}
+
+static int all_engines(struct drm_i915_private *i915,
+  int (*chain)(struct intel_engine_cs *engine,
+   unsigned long param,
+   bool (*fn)(struct i915_request *rq,
+  unsigned long v,
+  unsigned long e)),
+  unsigned long param,
+  bool (*fn)(struct i915_request *rq,
+ unsigned long v, unsigned long e))
+{
+   struct intel_engine_cs *engine;
+   int err;
+
+   for_each_uabi_engine(engine, i915) {
+