Branch data Line data Source code
1 : : /*
2 : : * SPDX-License-Identifier: MIT
3 : : *
4 : : * Copyright © 2018 Intel Corporation
5 : : */
6 : :
7 : : #include <linux/mutex.h>
8 : :
9 : : #include "i915_drv.h"
10 : : #include "i915_globals.h"
11 : : #include "i915_request.h"
12 : : #include "i915_scheduler.h"
13 : :
14 : : static struct i915_global_scheduler {
15 : : struct i915_global base;
16 : : struct kmem_cache *slab_dependencies;
17 : : struct kmem_cache *slab_priorities;
18 : : } global;
19 : :
20 : : static DEFINE_SPINLOCK(schedule_lock);
21 : :
22 : : static const struct i915_request *
23 : 0 : node_to_request(const struct i915_sched_node *node)
24 : : {
25 : 0 : return container_of(node, const struct i915_request, sched);
26 : : }
27 : :
28 : 0 : static inline bool node_started(const struct i915_sched_node *node)
29 : : {
30 : 0 : return i915_request_started(node_to_request(node));
31 : : }
32 : :
33 : 0 : static inline bool node_signaled(const struct i915_sched_node *node)
34 : : {
35 : 0 : return i915_request_completed(node_to_request(node));
36 : : }
37 : :
38 : 0 : static inline struct i915_priolist *to_priolist(struct rb_node *rb)
39 : : {
40 : 0 : return rb_entry(rb, struct i915_priolist, node);
41 : : }
42 : :
43 : 0 : static void assert_priolists(struct intel_engine_execlists * const execlists)
44 : : {
45 : 0 : struct rb_node *rb;
46 : 0 : long last_prio, i;
47 : :
48 : 0 : if (!IS_ENABLED(CONFIG_DRM_I915_DEBUG_GEM))
49 : 0 : return;
50 : :
51 : : GEM_BUG_ON(rb_first_cached(&execlists->queue) !=
52 : : rb_first(&execlists->queue.rb_root));
53 : :
54 : : last_prio = (INT_MAX >> I915_USER_PRIORITY_SHIFT) + 1;
55 : : for (rb = rb_first_cached(&execlists->queue); rb; rb = rb_next(rb)) {
56 : : const struct i915_priolist *p = to_priolist(rb);
57 : :
58 : : GEM_BUG_ON(p->priority >= last_prio);
59 : : last_prio = p->priority;
60 : :
61 : : GEM_BUG_ON(!p->used);
62 : : for (i = 0; i < ARRAY_SIZE(p->requests); i++) {
63 : : if (list_empty(&p->requests[i]))
64 : : continue;
65 : :
66 : : GEM_BUG_ON(!(p->used & BIT(i)));
67 : : }
68 : : }
69 : : }
70 : :
71 : : struct list_head *
72 : 0 : i915_sched_lookup_priolist(struct intel_engine_cs *engine, int prio)
73 : : {
74 : 0 : struct intel_engine_execlists * const execlists = &engine->execlists;
75 : 0 : struct i915_priolist *p;
76 : 0 : struct rb_node **parent, *rb;
77 : 0 : bool first = true;
78 : 0 : int idx, i;
79 : :
80 : 0 : lockdep_assert_held(&engine->active.lock);
81 : 0 : assert_priolists(execlists);
82 : :
83 : : /* buckets sorted from highest [in slot 0] to lowest priority */
84 : 0 : idx = I915_PRIORITY_COUNT - (prio & I915_PRIORITY_MASK) - 1;
85 : 0 : prio >>= I915_USER_PRIORITY_SHIFT;
86 [ # # ]: 0 : if (unlikely(execlists->no_priolist))
87 : 0 : prio = I915_PRIORITY_NORMAL;
88 : :
89 : 0 : find_priolist:
90 : : /* most positive priority is scheduled first, equal priorities fifo */
91 : 0 : rb = NULL;
92 : 0 : parent = &execlists->queue.rb_root.rb_node;
93 [ # # ]: 0 : while (*parent) {
94 : 0 : rb = *parent;
95 : 0 : p = to_priolist(rb);
96 [ # # ]: 0 : if (prio > p->priority) {
97 : 0 : parent = &rb->rb_left;
98 [ # # ]: 0 : } else if (prio < p->priority) {
99 : 0 : parent = &rb->rb_right;
100 : 0 : first = false;
101 : : } else {
102 : 0 : goto out;
103 : : }
104 : : }
105 : :
106 [ # # ]: 0 : if (prio == I915_PRIORITY_NORMAL) {
107 : 0 : p = &execlists->default_priolist;
108 : : } else {
109 : 0 : p = kmem_cache_alloc(global.slab_priorities, GFP_ATOMIC);
110 : : /* Convert an allocation failure to a priority bump */
111 [ # # ]: 0 : if (unlikely(!p)) {
112 : 0 : prio = I915_PRIORITY_NORMAL; /* recurses just once */
113 : :
114 : : /* To maintain ordering with all rendering, after an
115 : : * allocation failure we have to disable all scheduling.
116 : : * Requests will then be executed in fifo, and schedule
117 : : * will ensure that dependencies are emitted in fifo.
118 : : * There will be still some reordering with existing
119 : : * requests, so if userspace lied about their
120 : : * dependencies that reordering may be visible.
121 : : */
122 : 0 : execlists->no_priolist = true;
123 : 0 : goto find_priolist;
124 : : }
125 : : }
126 : :
127 : 0 : p->priority = prio;
128 [ # # ]: 0 : for (i = 0; i < ARRAY_SIZE(p->requests); i++)
129 : 0 : INIT_LIST_HEAD(&p->requests[i]);
130 [ # # ]: 0 : rb_link_node(&p->node, rb, parent);
131 [ # # ]: 0 : rb_insert_color_cached(&p->node, &execlists->queue, first);
132 : 0 : p->used = 0;
133 : :
134 : 0 : out:
135 : 0 : p->used |= BIT(idx);
136 : 0 : return &p->requests[idx];
137 : : }
138 : :
139 : 0 : void __i915_priolist_free(struct i915_priolist *p)
140 : : {
141 : 0 : kmem_cache_free(global.slab_priorities, p);
142 : 0 : }
143 : :
144 : : struct sched_cache {
145 : : struct list_head *priolist;
146 : : };
147 : :
148 : : static struct intel_engine_cs *
149 : 0 : sched_lock_engine(const struct i915_sched_node *node,
150 : : struct intel_engine_cs *locked,
151 : : struct sched_cache *cache)
152 : : {
153 : 0 : const struct i915_request *rq = node_to_request(node);
154 : 0 : struct intel_engine_cs *engine;
155 : :
156 : 0 : GEM_BUG_ON(!locked);
157 : :
158 : : /*
159 : : * Virtual engines complicate acquiring the engine timeline lock,
160 : : * as their rq->engine pointer is not stable until under that
161 : : * engine lock. The simple ploy we use is to take the lock then
162 : : * check that the rq still belongs to the newly locked engine.
163 : : */
164 [ # # ]: 0 : while (locked != (engine = READ_ONCE(rq->engine))) {
165 : 0 : spin_unlock(&locked->active.lock);
166 : 0 : memset(cache, 0, sizeof(*cache));
167 : 0 : spin_lock(&engine->active.lock);
168 : 0 : locked = engine;
169 : : }
170 : :
171 : 0 : GEM_BUG_ON(locked != engine);
172 : 0 : return locked;
173 : : }
174 : :
175 : : static inline int rq_prio(const struct i915_request *rq)
176 : : {
177 : : return rq->sched.attr.priority | __NO_PREEMPTION;
178 : : }
179 : :
180 : : static inline bool need_preempt(int prio, int active)
181 : : {
182 : : /*
183 : : * Allow preemption of low -> normal -> high, but we do
184 : : * not allow low priority tasks to preempt other low priority
185 : : * tasks under the impression that latency for low priority
186 : : * tasks does not matter (as much as background throughput),
187 : : * so kiss.
188 : : */
189 : : return prio >= max(I915_PRIORITY_NORMAL, active);
190 : : }
191 : :
192 : : static void kick_submission(struct intel_engine_cs *engine,
193 : : const struct i915_request *rq,
194 : : int prio)
195 : : {
196 : : const struct i915_request *inflight;
197 : :
198 : : /*
199 : : * We only need to kick the tasklet once for the high priority
200 : : * new context we add into the queue.
201 : : */
202 : : if (prio <= engine->execlists.queue_priority_hint)
203 : : return;
204 : :
205 : : rcu_read_lock();
206 : :
207 : : /* Nothing currently active? We're overdue for a submission! */
208 : : inflight = execlists_active(&engine->execlists);
209 : : if (!inflight)
210 : : goto unlock;
211 : :
212 : : /*
213 : : * If we are already the currently executing context, don't
214 : : * bother evaluating if we should preempt ourselves.
215 : : */
216 : : if (inflight->context == rq->context)
217 : : goto unlock;
218 : :
219 : : engine->execlists.queue_priority_hint = prio;
220 : : if (need_preempt(prio, rq_prio(inflight)))
221 : : tasklet_hi_schedule(&engine->execlists.tasklet);
222 : :
223 : : unlock:
224 : : rcu_read_unlock();
225 : : }
226 : :
227 : 0 : static void __i915_schedule(struct i915_sched_node *node,
228 : : const struct i915_sched_attr *attr)
229 : : {
230 : 0 : struct intel_engine_cs *engine;
231 : 0 : struct i915_dependency *dep, *p;
232 : 0 : struct i915_dependency stack;
233 : 0 : const int prio = attr->priority;
234 : 0 : struct sched_cache cache;
235 : 0 : LIST_HEAD(dfs);
236 : :
237 : : /* Needed in order to use the temporary link inside i915_dependency */
238 : 0 : lockdep_assert_held(&schedule_lock);
239 : 0 : GEM_BUG_ON(prio == I915_PRIORITY_INVALID);
240 : :
241 [ # # ]: 0 : if (prio <= READ_ONCE(node->attr.priority))
242 : 0 : return;
243 : :
244 [ # # ]: 0 : if (node_signaled(node))
245 : : return;
246 : :
247 : 0 : stack.signaler = node;
248 : 0 : list_add(&stack.dfs_link, &dfs);
249 : :
250 : : /*
251 : : * Recursively bump all dependent priorities to match the new request.
252 : : *
253 : : * A naive approach would be to use recursion:
254 : : * static void update_priorities(struct i915_sched_node *node, prio) {
255 : : * list_for_each_entry(dep, &node->signalers_list, signal_link)
256 : : * update_priorities(dep->signal, prio)
257 : : * queue_request(node);
258 : : * }
259 : : * but that may have unlimited recursion depth and so runs a very
260 : : * real risk of overunning the kernel stack. Instead, we build
261 : : * a flat list of all dependencies starting with the current request.
262 : : * As we walk the list of dependencies, we add all of its dependencies
263 : : * to the end of the list (this may include an already visited
264 : : * request) and continue to walk onwards onto the new dependencies. The
265 : : * end result is a topological list of requests in reverse order, the
266 : : * last element in the list is the request we must execute first.
267 : : */
268 [ # # ]: 0 : list_for_each_entry(dep, &dfs, dfs_link) {
269 : 0 : struct i915_sched_node *node = dep->signaler;
270 : :
271 : : /* If we are already flying, we know we have no signalers */
272 [ # # ]: 0 : if (node_started(node))
273 : 0 : continue;
274 : :
275 : : /*
276 : : * Within an engine, there can be no cycle, but we may
277 : : * refer to the same dependency chain multiple times
278 : : * (redundant dependencies are not eliminated) and across
279 : : * engines.
280 : : */
281 [ # # ]: 0 : list_for_each_entry(p, &node->signalers_list, signal_link) {
282 : 0 : GEM_BUG_ON(p == dep); /* no cycles! */
283 : :
284 [ # # ]: 0 : if (node_signaled(p->signaler))
285 : 0 : continue;
286 : :
287 [ # # ]: 0 : if (prio > READ_ONCE(p->signaler->attr.priority))
288 : 0 : list_move_tail(&p->dfs_link, &dfs);
289 : : }
290 : : }
291 : :
292 : : /*
293 : : * If we didn't need to bump any existing priorities, and we haven't
294 : : * yet submitted this request (i.e. there is no potential race with
295 : : * execlists_submit_request()), we can set our own priority and skip
296 : : * acquiring the engine locks.
297 : : */
298 [ # # ]: 0 : if (node->attr.priority == I915_PRIORITY_INVALID) {
299 : 0 : GEM_BUG_ON(!list_empty(&node->link));
300 : 0 : node->attr = *attr;
301 : :
302 [ # # ]: 0 : if (stack.dfs_link.next == stack.dfs_link.prev)
303 : : return;
304 : :
305 : 0 : __list_del_entry(&stack.dfs_link);
306 : : }
307 : :
308 : 0 : memset(&cache, 0, sizeof(cache));
309 : 0 : engine = node_to_request(node)->engine;
310 : 0 : spin_lock(&engine->active.lock);
311 : :
312 : : /* Fifo and depth-first replacement ensure our deps execute before us */
313 : 0 : engine = sched_lock_engine(node, engine, &cache);
314 [ # # ]: 0 : list_for_each_entry_safe_reverse(dep, p, &dfs, dfs_link) {
315 : 0 : INIT_LIST_HEAD(&dep->dfs_link);
316 : :
317 : 0 : node = dep->signaler;
318 : 0 : engine = sched_lock_engine(node, engine, &cache);
319 : 0 : lockdep_assert_held(&engine->active.lock);
320 : :
321 : : /* Recheck after acquiring the engine->timeline.lock */
322 [ # # # # ]: 0 : if (prio <= node->attr.priority || node_signaled(node))
323 : 0 : continue;
324 : :
325 : 0 : GEM_BUG_ON(node_to_request(node)->engine != engine);
326 : :
327 : 0 : node->attr.priority = prio;
328 : :
329 : : /*
330 : : * Once the request is ready, it will be placed into the
331 : : * priority lists and then onto the HW runlist. Before the
332 : : * request is ready, it does not contribute to our preemption
333 : : * decisions and we can safely ignore it, as it will, and
334 : : * any preemption required, be dealt with upon submission.
335 : : * See engine->submit_request()
336 : : */
337 [ # # ]: 0 : if (list_empty(&node->link))
338 : 0 : continue;
339 : :
340 [ # # ]: 0 : if (i915_request_in_priority_queue(node_to_request(node))) {
341 [ # # ]: 0 : if (!cache.priolist)
342 : 0 : cache.priolist =
343 : 0 : i915_sched_lookup_priolist(engine,
344 : : prio);
345 : 0 : list_move_tail(&node->link, cache.priolist);
346 : : }
347 : :
348 : : /* Defer (tasklet) submission until after all of our updates. */
349 : 0 : kick_submission(engine, node_to_request(node), prio);
350 : : }
351 : :
352 : 0 : spin_unlock(&engine->active.lock);
353 : : }
354 : :
355 : 0 : void i915_schedule(struct i915_request *rq, const struct i915_sched_attr *attr)
356 : : {
357 : 0 : spin_lock_irq(&schedule_lock);
358 : 0 : __i915_schedule(&rq->sched, attr);
359 : 0 : spin_unlock_irq(&schedule_lock);
360 : 0 : }
361 : :
362 : 0 : static void __bump_priority(struct i915_sched_node *node, unsigned int bump)
363 : : {
364 : 0 : struct i915_sched_attr attr = node->attr;
365 : :
366 : 0 : attr.priority |= bump;
367 : 0 : __i915_schedule(node, &attr);
368 : 0 : }
369 : :
370 : 0 : void i915_schedule_bump_priority(struct i915_request *rq, unsigned int bump)
371 : : {
372 : 0 : unsigned long flags;
373 : :
374 : 0 : GEM_BUG_ON(bump & ~I915_PRIORITY_MASK);
375 [ # # ]: 0 : if (READ_ONCE(rq->sched.attr.priority) & bump)
376 : : return;
377 : :
378 : 0 : spin_lock_irqsave(&schedule_lock, flags);
379 : 0 : __bump_priority(&rq->sched, bump);
380 : 0 : spin_unlock_irqrestore(&schedule_lock, flags);
381 : : }
382 : :
383 : 0 : void i915_sched_node_init(struct i915_sched_node *node)
384 : : {
385 : 0 : INIT_LIST_HEAD(&node->signalers_list);
386 : 0 : INIT_LIST_HEAD(&node->waiters_list);
387 : 0 : INIT_LIST_HEAD(&node->link);
388 : :
389 : 0 : i915_sched_node_reinit(node);
390 : 0 : }
391 : :
392 : 0 : void i915_sched_node_reinit(struct i915_sched_node *node)
393 : : {
394 : 0 : node->attr.priority = I915_PRIORITY_INVALID;
395 : 0 : node->semaphores = 0;
396 : 0 : node->flags = 0;
397 : :
398 : 0 : GEM_BUG_ON(!list_empty(&node->signalers_list));
399 : 0 : GEM_BUG_ON(!list_empty(&node->waiters_list));
400 : 0 : GEM_BUG_ON(!list_empty(&node->link));
401 : 0 : }
402 : :
403 : : static struct i915_dependency *
404 : 0 : i915_dependency_alloc(void)
405 : : {
406 : 0 : return kmem_cache_alloc(global.slab_dependencies, GFP_KERNEL);
407 : : }
408 : :
409 : : static void
410 : 0 : i915_dependency_free(struct i915_dependency *dep)
411 : : {
412 : 0 : kmem_cache_free(global.slab_dependencies, dep);
413 : 0 : }
414 : :
415 : 0 : bool __i915_sched_node_add_dependency(struct i915_sched_node *node,
416 : : struct i915_sched_node *signal,
417 : : struct i915_dependency *dep,
418 : : unsigned long flags)
419 : : {
420 : 0 : bool ret = false;
421 : :
422 : 0 : spin_lock_irq(&schedule_lock);
423 : :
424 [ # # ]: 0 : if (!node_signaled(signal)) {
425 [ # # ]: 0 : INIT_LIST_HEAD(&dep->dfs_link);
426 : 0 : dep->signaler = signal;
427 : 0 : dep->waiter = node;
428 : 0 : dep->flags = flags;
429 : :
430 : : /* Keep track of whether anyone on this chain has a semaphore */
431 [ # # # # ]: 0 : if (signal->flags & I915_SCHED_HAS_SEMAPHORE_CHAIN &&
432 : : !node_started(signal))
433 : 0 : node->flags |= I915_SCHED_HAS_SEMAPHORE_CHAIN;
434 : :
435 : : /* All set, now publish. Beware the lockless walkers. */
436 : 0 : list_add(&dep->signal_link, &node->signalers_list);
437 : 0 : list_add_rcu(&dep->wait_link, &signal->waiters_list);
438 : :
439 : : /*
440 : : * As we do not allow WAIT to preempt inflight requests,
441 : : * once we have executed a request, along with triggering
442 : : * any execution callbacks, we must preserve its ordering
443 : : * within the non-preemptible FIFO.
444 : : */
445 : 0 : BUILD_BUG_ON(__NO_PREEMPTION & ~I915_PRIORITY_MASK);
446 [ # # ]: 0 : if (flags & I915_DEPENDENCY_EXTERNAL)
447 : 0 : __bump_priority(signal, __NO_PREEMPTION);
448 : :
449 : : ret = true;
450 : : }
451 : :
452 : 0 : spin_unlock_irq(&schedule_lock);
453 : :
454 : 0 : return ret;
455 : : }
456 : :
457 : 0 : int i915_sched_node_add_dependency(struct i915_sched_node *node,
458 : : struct i915_sched_node *signal)
459 : : {
460 : 0 : struct i915_dependency *dep;
461 : :
462 : 0 : dep = i915_dependency_alloc();
463 [ # # ]: 0 : if (!dep)
464 : : return -ENOMEM;
465 : :
466 [ # # ]: 0 : if (!__i915_sched_node_add_dependency(node, signal, dep,
467 : : I915_DEPENDENCY_EXTERNAL |
468 : : I915_DEPENDENCY_ALLOC))
469 : 0 : i915_dependency_free(dep);
470 : :
471 : : return 0;
472 : : }
473 : :
474 : 0 : void i915_sched_node_fini(struct i915_sched_node *node)
475 : : {
476 : 0 : struct i915_dependency *dep, *tmp;
477 : :
478 : 0 : spin_lock_irq(&schedule_lock);
479 : :
480 : : /*
481 : : * Everyone we depended upon (the fences we wait to be signaled)
482 : : * should retire before us and remove themselves from our list.
483 : : * However, retirement is run independently on each timeline and
484 : : * so we may be called out-of-order.
485 : : */
486 [ # # ]: 0 : list_for_each_entry_safe(dep, tmp, &node->signalers_list, signal_link) {
487 : 0 : GEM_BUG_ON(!list_empty(&dep->dfs_link));
488 : :
489 [ # # ]: 0 : list_del(&dep->wait_link);
490 [ # # ]: 0 : if (dep->flags & I915_DEPENDENCY_ALLOC)
491 : 0 : i915_dependency_free(dep);
492 : : }
493 : 0 : INIT_LIST_HEAD(&node->signalers_list);
494 : :
495 : : /* Remove ourselves from everyone who depends upon us */
496 [ # # ]: 0 : list_for_each_entry_safe(dep, tmp, &node->waiters_list, wait_link) {
497 : 0 : GEM_BUG_ON(dep->signaler != node);
498 : 0 : GEM_BUG_ON(!list_empty(&dep->dfs_link));
499 : :
500 [ # # ]: 0 : list_del(&dep->signal_link);
501 [ # # ]: 0 : if (dep->flags & I915_DEPENDENCY_ALLOC)
502 : 0 : i915_dependency_free(dep);
503 : : }
504 : 0 : INIT_LIST_HEAD(&node->waiters_list);
505 : :
506 : 0 : spin_unlock_irq(&schedule_lock);
507 : 0 : }
508 : :
509 : 0 : static void i915_global_scheduler_shrink(void)
510 : : {
511 : 0 : kmem_cache_shrink(global.slab_dependencies);
512 : 0 : kmem_cache_shrink(global.slab_priorities);
513 : 0 : }
514 : :
515 : 0 : static void i915_global_scheduler_exit(void)
516 : : {
517 : 0 : kmem_cache_destroy(global.slab_dependencies);
518 : 0 : kmem_cache_destroy(global.slab_priorities);
519 : 0 : }
520 : :
521 : : static struct i915_global_scheduler global = { {
522 : : .shrink = i915_global_scheduler_shrink,
523 : : .exit = i915_global_scheduler_exit,
524 : : } };
525 : :
526 : 78 : int __init i915_global_scheduler_init(void)
527 : : {
528 : 78 : global.slab_dependencies = KMEM_CACHE(i915_dependency,
529 : : SLAB_HWCACHE_ALIGN);
530 [ + - ]: 78 : if (!global.slab_dependencies)
531 : : return -ENOMEM;
532 : :
533 : 78 : global.slab_priorities = KMEM_CACHE(i915_priolist,
534 : : SLAB_HWCACHE_ALIGN);
535 [ - + ]: 78 : if (!global.slab_priorities)
536 : 0 : goto err_priorities;
537 : :
538 : 78 : i915_global_register(&global.base);
539 : 78 : return 0;
540 : :
541 : : err_priorities:
542 : 0 : kmem_cache_destroy(global.slab_priorities);
543 : 0 : return -ENOMEM;
544 : : }
|
