[PATCH 62/62] drm/i915: Improve DFS for priority inheritance
Chris Wilson
chris at chris-wilson.co.uk
Sat Aug 1 14:58:51 UTC 2020
The core of the scheduling algorithm is that we compute the topological
order of the fence DAG. Knowing that we have a DAG, we should be able to
use a DFS to compute the topological sort in linear time. However,
during the conversion of the recursive algorithm into an iterative one,
the memorization of how far we had progressed down a branch was
forgotten.
Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
---
drivers/gpu/drm/i915/i915_scheduler.c | 61 ++++++++++++++++++---------
1 file changed, 41 insertions(+), 20 deletions(-)
diff --git a/drivers/gpu/drm/i915/i915_scheduler.c b/drivers/gpu/drm/i915/i915_scheduler.c
index 98816a9f147d..95adec09674a 100644
--- a/drivers/gpu/drm/i915/i915_scheduler.c
+++ b/drivers/gpu/drm/i915/i915_scheduler.c
@@ -251,15 +251,38 @@ static void ipi_priority(struct i915_dependency *p, int prio)
spin_unlock(&ipi_lock);
}
+static struct i915_request *
+stack_push(struct i915_request *rq, struct i915_request *stack)
+{
+ rq->sched.dfs.prev = &rq->sched.signalers_list;
+ rq->sched.dfs.next = (struct list_head *)stack;
+ return rq;
+}
+
+static void stack_store(struct i915_request *rq, struct i915_dependency *p)
+{
+ rq->sched.dfs.prev = &p->signal_link;
+}
+
+static struct i915_dependency *stack_load(struct i915_request *rq)
+{
+ return list_entry_rcu(rq->sched.dfs.prev->next,
+ struct i915_dependency,
+ signal_link);
+}
+
+static struct i915_request *stack_pop(struct i915_request *rq)
+{
+ return (struct i915_request *)rq->sched.dfs.next;
+}
+
static void __i915_request_set_priority(struct i915_request *rq, int prio)
{
struct intel_engine_cs *engine = rq->engine;
- struct i915_request *rn;
struct list_head *plist;
- LIST_HEAD(dfs);
lockdep_assert_held(&engine->active.lock);
- list_add(&rq->sched.dfs, &dfs);
+ plist = i915_sched_lookup_priolist(engine, prio);
/*
* Recursively bump all dependent priorities to match the new request.
@@ -279,13 +302,15 @@ static void __i915_request_set_priority(struct i915_request *rq, int prio)
* end result is a topological list of requests in reverse order, the
* last element in the list is the request we must execute first.
*/
- list_for_each_entry(rq, &dfs, sched.dfs) {
+ stack_push(rq, NULL);
+ do {
struct i915_dependency *p;
- /* Also release any children on this engine that are ready */
- GEM_BUG_ON(rq->engine != engine);
-
- for_each_signaler(p, rq) {
+descend:
+ p = stack_load(rq);
+ list_for_each_entry_from_rcu(p,
+ &rq->sched.signalers_list,
+ signal_link) {
struct i915_request *s =
container_of(p->signaler, typeof(*s), sched);
@@ -297,22 +322,18 @@ static void __i915_request_set_priority(struct i915_request *rq, int prio)
if (i915_request_completed(s))
continue;
- if (s->engine != rq->engine) {
+ if (s->engine != engine) {
ipi_priority(p, prio);
continue;
}
- list_move_tail(&s->sched.dfs, &dfs);
+ /* Remember where we our position along this branch */
+ stack_store(rq, p);
+ rq = stack_push(s, rq);
+ goto descend;
}
- }
- plist = i915_sched_lookup_priolist(engine, prio);
-
- /* Fifo and depth-first replacement ensure our deps execute first */
- list_for_each_entry_safe_reverse(rq, rn, &dfs, sched.dfs) {
- GEM_BUG_ON(rq->engine != engine);
-
- INIT_LIST_HEAD(&rq->sched.dfs);
+ RQ_TRACE(rq, "set-priority:%d\n", prio);
WRITE_ONCE(rq->sched.attr.priority, prio);
/*
@@ -326,12 +347,13 @@ static void __i915_request_set_priority(struct i915_request *rq, int prio)
if (!i915_request_is_ready(rq))
continue;
+ GEM_BUG_ON(rq->engine != engine);
if (i915_request_in_priority_queue(rq))
list_move_tail(&rq->sched.link, plist);
/* Defer (tasklet) submission until after all updates. */
kick_submission(engine, rq, prio);
- }
+ } while ((rq = stack_pop(rq)));
}
void i915_request_set_priority(struct i915_request *rq, int prio)
@@ -398,7 +420,6 @@ void i915_sched_node_init(struct i915_sched_node *node)
INIT_LIST_HEAD(&node->signalers_list);
INIT_LIST_HEAD(&node->waiters_list);
INIT_LIST_HEAD(&node->link);
- INIT_LIST_HEAD(&node->dfs);
i915_sched_node_reinit(node);
}
--
2.20.1
More information about the Intel-gfx-trybot
mailing list