1 /* sched.c - SPU scheduler.
3 * Copyright (C) IBM 2005
4 * Author: Mark Nutter <mnutter@us.ibm.com>
6 * 2006-03-31 NUMA domains added.
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2, or (at your option)
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
25 #include <linux/module.h>
26 #include <linux/errno.h>
27 #include <linux/sched.h>
28 #include <linux/kernel.h>
30 #include <linux/completion.h>
31 #include <linux/vmalloc.h>
32 #include <linux/smp.h>
33 #include <linux/stddef.h>
34 #include <linux/unistd.h>
35 #include <linux/numa.h>
36 #include <linux/mutex.h>
37 #include <linux/notifier.h>
38 #include <linux/kthread.h>
41 #include <asm/mmu_context.h>
43 #include <asm/spu_csa.h>
44 #include <asm/spu_priv1.h>
47 struct spu_prio_array {
48 DECLARE_BITMAP(bitmap, MAX_PRIO);
49 struct list_head runq[MAX_PRIO];
51 struct list_head active_list[MAX_NUMNODES];
52 struct mutex active_mutex[MAX_NUMNODES];
55 static struct spu_prio_array *spu_prio;
56 static struct task_struct *spusched_task;
57 static struct timer_list spusched_timer;
60 * Priority of a normal, non-rt, non-niced'd process (aka nice level 0).
62 #define NORMAL_PRIO 120
65 * Frequency of the spu scheduler tick. By default we do one SPU scheduler
66 * tick for every 10 CPU scheduler ticks.
68 #define SPUSCHED_TICK (10)
71 * These are the 'tuning knobs' of the scheduler:
73 * Minimum timeslice is 5 msecs (or 1 spu scheduler tick, whichever is
74 * larger), default timeslice is 100 msecs, maximum timeslice is 800 msecs.
76 #define MIN_SPU_TIMESLICE max(5 * HZ / (1000 * SPUSCHED_TICK), 1)
77 #define DEF_SPU_TIMESLICE (100 * HZ / (1000 * SPUSCHED_TICK))
79 #define MAX_USER_PRIO (MAX_PRIO - MAX_RT_PRIO)
80 #define SCALE_PRIO(x, prio) \
81 max(x * (MAX_PRIO - prio) / (MAX_USER_PRIO / 2), MIN_SPU_TIMESLICE)
84 * scale user-nice values [ -20 ... 0 ... 19 ] to time slice values:
85 * [800ms ... 100ms ... 5ms]
87 * The higher a thread's priority, the bigger timeslices
88 * it gets during one round of execution. But even the lowest
89 * priority thread gets MIN_TIMESLICE worth of execution time.
91 void spu_set_timeslice(struct spu_context *ctx)
93 if (ctx->prio < NORMAL_PRIO)
94 ctx->time_slice = SCALE_PRIO(DEF_SPU_TIMESLICE * 4, ctx->prio);
96 ctx->time_slice = SCALE_PRIO(DEF_SPU_TIMESLICE, ctx->prio);
100 * Update scheduling information from the owning thread.
102 void __spu_update_sched_info(struct spu_context *ctx)
105 * 32-Bit assignment are atomic on powerpc, and we don't care about
106 * memory ordering here because retriving the controlling thread is
107 * per defintion racy.
109 ctx->tid = current->pid;
112 * We do our own priority calculations, so we normally want
113 * ->static_prio to start with. Unfortunately thies field
114 * contains junk for threads with a realtime scheduling
115 * policy so we have to look at ->prio in this case.
117 if (rt_prio(current->prio))
118 ctx->prio = current->prio;
120 ctx->prio = current->static_prio;
121 ctx->policy = current->policy;
124 * A lot of places that don't hold active_mutex poke into
125 * cpus_allowed, including grab_runnable_context which
126 * already holds the runq_lock. So abuse runq_lock
127 * to protect this field aswell.
129 spin_lock(&spu_prio->runq_lock);
130 ctx->cpus_allowed = current->cpus_allowed;
131 spin_unlock(&spu_prio->runq_lock);
134 void spu_update_sched_info(struct spu_context *ctx)
136 int node = ctx->spu->node;
138 mutex_lock(&spu_prio->active_mutex[node]);
139 __spu_update_sched_info(ctx);
140 mutex_unlock(&spu_prio->active_mutex[node]);
143 static int __node_allowed(struct spu_context *ctx, int node)
145 if (nr_cpus_node(node)) {
146 cpumask_t mask = node_to_cpumask(node);
148 if (cpus_intersects(mask, ctx->cpus_allowed))
155 static int node_allowed(struct spu_context *ctx, int node)
159 spin_lock(&spu_prio->runq_lock);
160 rval = __node_allowed(ctx, node);
161 spin_unlock(&spu_prio->runq_lock);
167 * spu_add_to_active_list - add spu to active list
168 * @spu: spu to add to the active list
170 static void spu_add_to_active_list(struct spu *spu)
172 mutex_lock(&spu_prio->active_mutex[spu->node]);
173 list_add_tail(&spu->list, &spu_prio->active_list[spu->node]);
174 mutex_unlock(&spu_prio->active_mutex[spu->node]);
177 static void __spu_remove_from_active_list(struct spu *spu)
179 list_del_init(&spu->list);
183 * spu_remove_from_active_list - remove spu from active list
184 * @spu: spu to remove from the active list
186 static void spu_remove_from_active_list(struct spu *spu)
188 int node = spu->node;
190 mutex_lock(&spu_prio->active_mutex[node]);
191 __spu_remove_from_active_list(spu);
192 mutex_unlock(&spu_prio->active_mutex[node]);
195 static BLOCKING_NOTIFIER_HEAD(spu_switch_notifier);
197 static void spu_switch_notify(struct spu *spu, struct spu_context *ctx)
199 blocking_notifier_call_chain(&spu_switch_notifier,
200 ctx ? ctx->object_id : 0, spu);
203 int spu_switch_event_register(struct notifier_block * n)
205 return blocking_notifier_chain_register(&spu_switch_notifier, n);
208 int spu_switch_event_unregister(struct notifier_block * n)
210 return blocking_notifier_chain_unregister(&spu_switch_notifier, n);
214 * spu_bind_context - bind spu context to physical spu
215 * @spu: physical spu to bind to
216 * @ctx: context to bind
218 static void spu_bind_context(struct spu *spu, struct spu_context *ctx)
220 pr_debug("%s: pid=%d SPU=%d NODE=%d\n", __FUNCTION__, current->pid,
221 spu->number, spu->node);
225 ctx->ops = &spu_hw_ops;
226 spu->pid = current->pid;
227 spu_associate_mm(spu, ctx->owner);
228 spu->ibox_callback = spufs_ibox_callback;
229 spu->wbox_callback = spufs_wbox_callback;
230 spu->stop_callback = spufs_stop_callback;
231 spu->mfc_callback = spufs_mfc_callback;
232 spu->dma_callback = spufs_dma_callback;
234 spu_unmap_mappings(ctx);
235 spu_restore(&ctx->csa, spu);
236 spu->timestamp = jiffies;
237 spu_cpu_affinity_set(spu, raw_smp_processor_id());
238 spu_switch_notify(spu, ctx);
239 ctx->state = SPU_STATE_RUNNABLE;
243 * spu_unbind_context - unbind spu context from physical spu
244 * @spu: physical spu to unbind from
245 * @ctx: context to unbind
247 static void spu_unbind_context(struct spu *spu, struct spu_context *ctx)
249 pr_debug("%s: unbind pid=%d SPU=%d NODE=%d\n", __FUNCTION__,
250 spu->pid, spu->number, spu->node);
252 spu_switch_notify(spu, NULL);
253 spu_unmap_mappings(ctx);
254 spu_save(&ctx->csa, spu);
255 spu->timestamp = jiffies;
256 ctx->state = SPU_STATE_SAVED;
257 spu->ibox_callback = NULL;
258 spu->wbox_callback = NULL;
259 spu->stop_callback = NULL;
260 spu->mfc_callback = NULL;
261 spu->dma_callback = NULL;
262 spu_associate_mm(spu, NULL);
264 ctx->ops = &spu_backing_ops;
271 * spu_add_to_rq - add a context to the runqueue
272 * @ctx: context to add
274 static void __spu_add_to_rq(struct spu_context *ctx)
276 int prio = ctx->prio;
278 list_add_tail(&ctx->rq, &spu_prio->runq[prio]);
279 set_bit(prio, spu_prio->bitmap);
282 static void __spu_del_from_rq(struct spu_context *ctx)
284 int prio = ctx->prio;
286 if (!list_empty(&ctx->rq))
287 list_del_init(&ctx->rq);
288 if (list_empty(&spu_prio->runq[prio]))
289 clear_bit(prio, spu_prio->bitmap);
292 static void spu_prio_wait(struct spu_context *ctx)
296 spin_lock(&spu_prio->runq_lock);
297 prepare_to_wait_exclusive(&ctx->stop_wq, &wait, TASK_INTERRUPTIBLE);
298 if (!signal_pending(current)) {
299 __spu_add_to_rq(ctx);
300 spin_unlock(&spu_prio->runq_lock);
301 mutex_unlock(&ctx->state_mutex);
303 mutex_lock(&ctx->state_mutex);
304 spin_lock(&spu_prio->runq_lock);
305 __spu_del_from_rq(ctx);
307 spin_unlock(&spu_prio->runq_lock);
308 __set_current_state(TASK_RUNNING);
309 remove_wait_queue(&ctx->stop_wq, &wait);
312 static struct spu *spu_get_idle(struct spu_context *ctx)
314 struct spu *spu = NULL;
315 int node = cpu_to_node(raw_smp_processor_id());
318 for (n = 0; n < MAX_NUMNODES; n++, node++) {
319 node = (node < MAX_NUMNODES) ? node : 0;
320 if (!node_allowed(ctx, node))
322 spu = spu_alloc_node(node);
330 * find_victim - find a lower priority context to preempt
331 * @ctx: canidate context for running
333 * Returns the freed physical spu to run the new context on.
335 static struct spu *find_victim(struct spu_context *ctx)
337 struct spu_context *victim = NULL;
342 * Look for a possible preemption candidate on the local node first.
343 * If there is no candidate look at the other nodes. This isn't
344 * exactly fair, but so far the whole spu schedule tries to keep
345 * a strong node affinity. We might want to fine-tune this in
349 node = cpu_to_node(raw_smp_processor_id());
350 for (n = 0; n < MAX_NUMNODES; n++, node++) {
351 node = (node < MAX_NUMNODES) ? node : 0;
352 if (!node_allowed(ctx, node))
355 mutex_lock(&spu_prio->active_mutex[node]);
356 list_for_each_entry(spu, &spu_prio->active_list[node], list) {
357 struct spu_context *tmp = spu->ctx;
359 if (tmp->prio > ctx->prio &&
360 (!victim || tmp->prio > victim->prio))
363 mutex_unlock(&spu_prio->active_mutex[node]);
367 * This nests ctx->state_mutex, but we always lock
368 * higher priority contexts before lower priority
369 * ones, so this is safe until we introduce
370 * priority inheritance schemes.
372 if (!mutex_trylock(&victim->state_mutex)) {
380 * This race can happen because we've dropped
381 * the active list mutex. No a problem, just
382 * restart the search.
384 mutex_unlock(&victim->state_mutex);
388 spu_remove_from_active_list(spu);
389 spu_unbind_context(spu, victim);
390 mutex_unlock(&victim->state_mutex);
392 * We need to break out of the wait loop in spu_run
393 * manually to ensure this context gets put on the
394 * runqueue again ASAP.
396 wake_up(&victim->stop_wq);
405 * spu_activate - find a free spu for a context and execute it
406 * @ctx: spu context to schedule
407 * @flags: flags (currently ignored)
409 * Tries to find a free spu to run @ctx. If no free spu is available
410 * add the context to the runqueue so it gets woken up once an spu
413 int spu_activate(struct spu_context *ctx, unsigned long flags)
422 spu = spu_get_idle(ctx);
424 * If this is a realtime thread we try to get it running by
425 * preempting a lower priority thread.
427 if (!spu && rt_prio(ctx->prio))
428 spu = find_victim(ctx);
430 spu_bind_context(spu, ctx);
431 spu_add_to_active_list(spu);
436 } while (!signal_pending(current));
442 * grab_runnable_context - try to find a runnable context
444 * Remove the highest priority context on the runqueue and return it
445 * to the caller. Returns %NULL if no runnable context was found.
447 static struct spu_context *grab_runnable_context(int prio, int node)
449 struct spu_context *ctx;
452 spin_lock(&spu_prio->runq_lock);
453 best = sched_find_first_bit(spu_prio->bitmap);
454 while (best < prio) {
455 struct list_head *rq = &spu_prio->runq[best];
457 list_for_each_entry(ctx, rq, rq) {
458 /* XXX(hch): check for affinity here aswell */
459 if (__node_allowed(ctx, node)) {
460 __spu_del_from_rq(ctx);
468 spin_unlock(&spu_prio->runq_lock);
472 static int __spu_deactivate(struct spu_context *ctx, int force, int max_prio)
474 struct spu *spu = ctx->spu;
475 struct spu_context *new = NULL;
478 new = grab_runnable_context(max_prio, spu->node);
480 spu_remove_from_active_list(spu);
481 spu_unbind_context(spu, ctx);
484 wake_up(&new->stop_wq);
493 * spu_deactivate - unbind a context from it's physical spu
494 * @ctx: spu context to unbind
496 * Unbind @ctx from the physical spu it is running on and schedule
497 * the highest priority context to run on the freed physical spu.
499 void spu_deactivate(struct spu_context *ctx)
502 * We must never reach this for a nosched context,
503 * but handle the case gracefull instead of panicing.
505 if (ctx->flags & SPU_CREATE_NOSCHED) {
510 __spu_deactivate(ctx, 1, MAX_PRIO);
514 * spu_yield - yield a physical spu if others are waiting
515 * @ctx: spu context to yield
517 * Check if there is a higher priority context waiting and if yes
518 * unbind @ctx from the physical spu and schedule the highest
519 * priority context to run on the freed physical spu instead.
521 void spu_yield(struct spu_context *ctx)
523 if (!(ctx->flags & SPU_CREATE_NOSCHED)) {
524 mutex_lock(&ctx->state_mutex);
525 __spu_deactivate(ctx, 0, MAX_PRIO);
526 mutex_unlock(&ctx->state_mutex);
530 static void spusched_tick(struct spu_context *ctx)
532 if (ctx->flags & SPU_CREATE_NOSCHED)
534 if (ctx->policy == SCHED_FIFO)
537 if (--ctx->time_slice)
541 * Unfortunately active_mutex ranks outside of state_mutex, so
542 * we have to trylock here. If we fail give the context another
543 * tick and try again.
545 if (mutex_trylock(&ctx->state_mutex)) {
546 struct spu *spu = ctx->spu;
547 struct spu_context *new;
549 new = grab_runnable_context(ctx->prio + 1, spu->node);
552 __spu_remove_from_active_list(spu);
553 spu_unbind_context(spu, ctx);
555 wake_up(&new->stop_wq);
557 * We need to break out of the wait loop in
558 * spu_run manually to ensure this context
559 * gets put on the runqueue again ASAP.
561 wake_up(&ctx->stop_wq);
563 spu_set_timeslice(ctx);
564 mutex_unlock(&ctx->state_mutex);
570 static void spusched_wake(unsigned long data)
572 mod_timer(&spusched_timer, jiffies + SPUSCHED_TICK);
573 wake_up_process(spusched_task);
576 static int spusched_thread(void *unused)
578 struct spu *spu, *next;
581 setup_timer(&spusched_timer, spusched_wake, 0);
582 __mod_timer(&spusched_timer, jiffies + SPUSCHED_TICK);
584 while (!kthread_should_stop()) {
585 set_current_state(TASK_INTERRUPTIBLE);
587 for (node = 0; node < MAX_NUMNODES; node++) {
588 mutex_lock(&spu_prio->active_mutex[node]);
589 list_for_each_entry_safe(spu, next,
590 &spu_prio->active_list[node],
592 spusched_tick(spu->ctx);
593 mutex_unlock(&spu_prio->active_mutex[node]);
597 del_timer_sync(&spusched_timer);
601 int __init spu_sched_init(void)
605 spu_prio = kzalloc(sizeof(struct spu_prio_array), GFP_KERNEL);
609 for (i = 0; i < MAX_PRIO; i++) {
610 INIT_LIST_HEAD(&spu_prio->runq[i]);
611 __clear_bit(i, spu_prio->bitmap);
613 __set_bit(MAX_PRIO, spu_prio->bitmap);
614 for (i = 0; i < MAX_NUMNODES; i++) {
615 mutex_init(&spu_prio->active_mutex[i]);
616 INIT_LIST_HEAD(&spu_prio->active_list[i]);
618 spin_lock_init(&spu_prio->runq_lock);
620 spusched_task = kthread_run(spusched_thread, NULL, "spusched");
621 if (IS_ERR(spusched_task)) {
623 return PTR_ERR(spusched_task);
626 pr_debug("spusched: tick: %d, min ticks: %d, default ticks: %d\n",
627 SPUSCHED_TICK, MIN_SPU_TIMESLICE, DEF_SPU_TIMESLICE);
632 void __exit spu_sched_exit(void)
634 struct spu *spu, *tmp;
637 kthread_stop(spusched_task);
639 for (node = 0; node < MAX_NUMNODES; node++) {
640 mutex_lock(&spu_prio->active_mutex[node]);
641 list_for_each_entry_safe(spu, tmp, &spu_prio->active_list[node],
643 list_del_init(&spu->list);
646 mutex_unlock(&spu_prio->active_mutex[node]);