[POWERPC] spusched: Dynamic timeslicing for SCHED_OTHER
[linux-2.6] / arch / powerpc / platforms / cell / spufs / sched.c
1 /* sched.c - SPU scheduler.
2  *
3  * Copyright (C) IBM 2005
4  * Author: Mark Nutter <mnutter@us.ibm.com>
5  *
6  * 2006-03-31   NUMA domains added.
7  *
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)
11  * any later version.
12  *
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.
17  *
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.
21  */
22
23 #undef DEBUG
24
25 #include <linux/module.h>
26 #include <linux/errno.h>
27 #include <linux/sched.h>
28 #include <linux/kernel.h>
29 #include <linux/mm.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>
39
40 #include <asm/io.h>
41 #include <asm/mmu_context.h>
42 #include <asm/spu.h>
43 #include <asm/spu_csa.h>
44 #include <asm/spu_priv1.h>
45 #include "spufs.h"
46
47 struct spu_prio_array {
48         DECLARE_BITMAP(bitmap, MAX_PRIO);
49         struct list_head runq[MAX_PRIO];
50         spinlock_t runq_lock;
51         struct list_head active_list[MAX_NUMNODES];
52         struct mutex active_mutex[MAX_NUMNODES];
53 };
54
55 static struct spu_prio_array *spu_prio;
56 static struct task_struct *spusched_task;
57 static struct timer_list spusched_timer;
58
59 /*
60  * Priority of a normal, non-rt, non-niced'd process (aka nice level 0).
61  */
62 #define NORMAL_PRIO             120
63
64 /*
65  * Frequency of the spu scheduler tick.  By default we do one SPU scheduler
66  * tick for every 10 CPU scheduler ticks.
67  */
68 #define SPUSCHED_TICK           (10)
69
70 /*
71  * These are the 'tuning knobs' of the scheduler:
72  *
73  * Minimum timeslice is 5 msecs (or 10 jiffies, whichever is larger),
74  * default timeslice is 100 msecs, maximum timeslice is 800 msecs.
75  */
76 #define MIN_SPU_TIMESLICE       max(5 * HZ / 100, 10)
77 #define DEF_SPU_TIMESLICE       (100 * HZ / 100)
78
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)
82
83 /*
84  * scale user-nice values [ -20 ... 0 ... 19 ] to time slice values:
85  * [800ms ... 100ms ... 5ms]
86  *
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.
90  */
91 void spu_set_timeslice(struct spu_context *ctx)
92 {
93         if (ctx->prio < NORMAL_PRIO)
94                 ctx->time_slice = SCALE_PRIO(DEF_SPU_TIMESLICE * 4, ctx->prio);
95         else
96                 ctx->time_slice = SCALE_PRIO(DEF_SPU_TIMESLICE, ctx->prio);
97 }
98
99 static inline int node_allowed(int node)
100 {
101         cpumask_t mask;
102
103         if (!nr_cpus_node(node))
104                 return 0;
105         mask = node_to_cpumask(node);
106         if (!cpus_intersects(mask, current->cpus_allowed))
107                 return 0;
108         return 1;
109 }
110
111 /**
112  * spu_add_to_active_list - add spu to active list
113  * @spu:        spu to add to the active list
114  */
115 static void spu_add_to_active_list(struct spu *spu)
116 {
117         mutex_lock(&spu_prio->active_mutex[spu->node]);
118         list_add_tail(&spu->list, &spu_prio->active_list[spu->node]);
119         mutex_unlock(&spu_prio->active_mutex[spu->node]);
120 }
121
122 static void __spu_remove_from_active_list(struct spu *spu)
123 {
124         list_del_init(&spu->list);
125 }
126
127 /**
128  * spu_remove_from_active_list - remove spu from active list
129  * @spu:       spu to remove from the active list
130  */
131 static void spu_remove_from_active_list(struct spu *spu)
132 {
133         int node = spu->node;
134
135         mutex_lock(&spu_prio->active_mutex[node]);
136         __spu_remove_from_active_list(spu);
137         mutex_unlock(&spu_prio->active_mutex[node]);
138 }
139
140 static BLOCKING_NOTIFIER_HEAD(spu_switch_notifier);
141
142 static void spu_switch_notify(struct spu *spu, struct spu_context *ctx)
143 {
144         blocking_notifier_call_chain(&spu_switch_notifier,
145                             ctx ? ctx->object_id : 0, spu);
146 }
147
148 int spu_switch_event_register(struct notifier_block * n)
149 {
150         return blocking_notifier_chain_register(&spu_switch_notifier, n);
151 }
152
153 int spu_switch_event_unregister(struct notifier_block * n)
154 {
155         return blocking_notifier_chain_unregister(&spu_switch_notifier, n);
156 }
157
158 /**
159  * spu_bind_context - bind spu context to physical spu
160  * @spu:        physical spu to bind to
161  * @ctx:        context to bind
162  */
163 static void spu_bind_context(struct spu *spu, struct spu_context *ctx)
164 {
165         pr_debug("%s: pid=%d SPU=%d NODE=%d\n", __FUNCTION__, current->pid,
166                  spu->number, spu->node);
167         spu->ctx = ctx;
168         spu->flags = 0;
169         ctx->spu = spu;
170         ctx->ops = &spu_hw_ops;
171         spu->pid = current->pid;
172         spu_associate_mm(spu, ctx->owner);
173         spu->ibox_callback = spufs_ibox_callback;
174         spu->wbox_callback = spufs_wbox_callback;
175         spu->stop_callback = spufs_stop_callback;
176         spu->mfc_callback = spufs_mfc_callback;
177         spu->dma_callback = spufs_dma_callback;
178         mb();
179         spu_unmap_mappings(ctx);
180         spu_restore(&ctx->csa, spu);
181         spu->timestamp = jiffies;
182         spu_cpu_affinity_set(spu, raw_smp_processor_id());
183         spu_switch_notify(spu, ctx);
184         ctx->state = SPU_STATE_RUNNABLE;
185 }
186
187 /**
188  * spu_unbind_context - unbind spu context from physical spu
189  * @spu:        physical spu to unbind from
190  * @ctx:        context to unbind
191  */
192 static void spu_unbind_context(struct spu *spu, struct spu_context *ctx)
193 {
194         pr_debug("%s: unbind pid=%d SPU=%d NODE=%d\n", __FUNCTION__,
195                  spu->pid, spu->number, spu->node);
196
197         spu_switch_notify(spu, NULL);
198         spu_unmap_mappings(ctx);
199         spu_save(&ctx->csa, spu);
200         spu->timestamp = jiffies;
201         ctx->state = SPU_STATE_SAVED;
202         spu->ibox_callback = NULL;
203         spu->wbox_callback = NULL;
204         spu->stop_callback = NULL;
205         spu->mfc_callback = NULL;
206         spu->dma_callback = NULL;
207         spu_associate_mm(spu, NULL);
208         spu->pid = 0;
209         ctx->ops = &spu_backing_ops;
210         ctx->spu = NULL;
211         spu->flags = 0;
212         spu->ctx = NULL;
213 }
214
215 /**
216  * spu_add_to_rq - add a context to the runqueue
217  * @ctx:       context to add
218  */
219 static void __spu_add_to_rq(struct spu_context *ctx)
220 {
221         int prio = ctx->prio;
222
223         list_add_tail(&ctx->rq, &spu_prio->runq[prio]);
224         set_bit(prio, spu_prio->bitmap);
225 }
226
227 static void __spu_del_from_rq(struct spu_context *ctx)
228 {
229         int prio = ctx->prio;
230
231         if (!list_empty(&ctx->rq))
232                 list_del_init(&ctx->rq);
233         if (list_empty(&spu_prio->runq[prio]))
234                 clear_bit(prio, spu_prio->bitmap);
235 }
236
237 static void spu_prio_wait(struct spu_context *ctx)
238 {
239         DEFINE_WAIT(wait);
240
241         spin_lock(&spu_prio->runq_lock);
242         prepare_to_wait_exclusive(&ctx->stop_wq, &wait, TASK_INTERRUPTIBLE);
243         if (!signal_pending(current)) {
244                 __spu_add_to_rq(ctx);
245                 spin_unlock(&spu_prio->runq_lock);
246                 mutex_unlock(&ctx->state_mutex);
247                 schedule();
248                 mutex_lock(&ctx->state_mutex);
249                 spin_lock(&spu_prio->runq_lock);
250                 __spu_del_from_rq(ctx);
251         }
252         spin_unlock(&spu_prio->runq_lock);
253         __set_current_state(TASK_RUNNING);
254         remove_wait_queue(&ctx->stop_wq, &wait);
255 }
256
257 static struct spu *spu_get_idle(struct spu_context *ctx)
258 {
259         struct spu *spu = NULL;
260         int node = cpu_to_node(raw_smp_processor_id());
261         int n;
262
263         for (n = 0; n < MAX_NUMNODES; n++, node++) {
264                 node = (node < MAX_NUMNODES) ? node : 0;
265                 if (!node_allowed(node))
266                         continue;
267                 spu = spu_alloc_node(node);
268                 if (spu)
269                         break;
270         }
271         return spu;
272 }
273
274 /**
275  * find_victim - find a lower priority context to preempt
276  * @ctx:        canidate context for running
277  *
278  * Returns the freed physical spu to run the new context on.
279  */
280 static struct spu *find_victim(struct spu_context *ctx)
281 {
282         struct spu_context *victim = NULL;
283         struct spu *spu;
284         int node, n;
285
286         /*
287          * Look for a possible preemption candidate on the local node first.
288          * If there is no candidate look at the other nodes.  This isn't
289          * exactly fair, but so far the whole spu schedule tries to keep
290          * a strong node affinity.  We might want to fine-tune this in
291          * the future.
292          */
293  restart:
294         node = cpu_to_node(raw_smp_processor_id());
295         for (n = 0; n < MAX_NUMNODES; n++, node++) {
296                 node = (node < MAX_NUMNODES) ? node : 0;
297                 if (!node_allowed(node))
298                         continue;
299
300                 mutex_lock(&spu_prio->active_mutex[node]);
301                 list_for_each_entry(spu, &spu_prio->active_list[node], list) {
302                         struct spu_context *tmp = spu->ctx;
303
304                         if (tmp->prio > ctx->prio &&
305                             (!victim || tmp->prio > victim->prio))
306                                 victim = spu->ctx;
307                 }
308                 mutex_unlock(&spu_prio->active_mutex[node]);
309
310                 if (victim) {
311                         /*
312                          * This nests ctx->state_mutex, but we always lock
313                          * higher priority contexts before lower priority
314                          * ones, so this is safe until we introduce
315                          * priority inheritance schemes.
316                          */
317                         if (!mutex_trylock(&victim->state_mutex)) {
318                                 victim = NULL;
319                                 goto restart;
320                         }
321
322                         spu = victim->spu;
323                         if (!spu) {
324                                 /*
325                                  * This race can happen because we've dropped
326                                  * the active list mutex.  No a problem, just
327                                  * restart the search.
328                                  */
329                                 mutex_unlock(&victim->state_mutex);
330                                 victim = NULL;
331                                 goto restart;
332                         }
333                         spu_remove_from_active_list(spu);
334                         spu_unbind_context(spu, victim);
335                         mutex_unlock(&victim->state_mutex);
336                         /*
337                          * We need to break out of the wait loop in spu_run
338                          * manually to ensure this context gets put on the
339                          * runqueue again ASAP.
340                          */
341                         wake_up(&victim->stop_wq);
342                         return spu;
343                 }
344         }
345
346         return NULL;
347 }
348
349 /**
350  * spu_activate - find a free spu for a context and execute it
351  * @ctx:        spu context to schedule
352  * @flags:      flags (currently ignored)
353  *
354  * Tries to find a free spu to run @ctx.  If no free spu is available
355  * add the context to the runqueue so it gets woken up once an spu
356  * is available.
357  */
358 int spu_activate(struct spu_context *ctx, unsigned long flags)
359 {
360
361         if (ctx->spu)
362                 return 0;
363
364         do {
365                 struct spu *spu;
366
367                 spu = spu_get_idle(ctx);
368                 /*
369                  * If this is a realtime thread we try to get it running by
370                  * preempting a lower priority thread.
371                  */
372                 if (!spu && rt_prio(ctx->prio))
373                         spu = find_victim(ctx);
374                 if (spu) {
375                         spu_bind_context(spu, ctx);
376                         spu_add_to_active_list(spu);
377                         return 0;
378                 }
379
380                 spu_prio_wait(ctx);
381         } while (!signal_pending(current));
382
383         return -ERESTARTSYS;
384 }
385
386 /**
387  * grab_runnable_context - try to find a runnable context
388  *
389  * Remove the highest priority context on the runqueue and return it
390  * to the caller.  Returns %NULL if no runnable context was found.
391  */
392 static struct spu_context *grab_runnable_context(int prio)
393 {
394         struct spu_context *ctx = NULL;
395         int best;
396
397         spin_lock(&spu_prio->runq_lock);
398         best = sched_find_first_bit(spu_prio->bitmap);
399         if (best < prio) {
400                 struct list_head *rq = &spu_prio->runq[best];
401
402                 BUG_ON(list_empty(rq));
403
404                 ctx = list_entry(rq->next, struct spu_context, rq);
405                 __spu_del_from_rq(ctx);
406         }
407         spin_unlock(&spu_prio->runq_lock);
408
409         return ctx;
410 }
411
412 static int __spu_deactivate(struct spu_context *ctx, int force, int max_prio)
413 {
414         struct spu *spu = ctx->spu;
415         struct spu_context *new = NULL;
416
417         if (spu) {
418                 new = grab_runnable_context(max_prio);
419                 if (new || force) {
420                         spu_remove_from_active_list(spu);
421                         spu_unbind_context(spu, ctx);
422                         spu_free(spu);
423                         if (new)
424                                 wake_up(&new->stop_wq);
425                 }
426
427         }
428
429         return new != NULL;
430 }
431
432 /**
433  * spu_deactivate - unbind a context from it's physical spu
434  * @ctx:        spu context to unbind
435  *
436  * Unbind @ctx from the physical spu it is running on and schedule
437  * the highest priority context to run on the freed physical spu.
438  */
439 void spu_deactivate(struct spu_context *ctx)
440 {
441         __spu_deactivate(ctx, 1, MAX_PRIO);
442 }
443
444 /**
445  * spu_yield -  yield a physical spu if others are waiting
446  * @ctx:        spu context to yield
447  *
448  * Check if there is a higher priority context waiting and if yes
449  * unbind @ctx from the physical spu and schedule the highest
450  * priority context to run on the freed physical spu instead.
451  */
452 void spu_yield(struct spu_context *ctx)
453 {
454         if (!(ctx->flags & SPU_CREATE_NOSCHED)) {
455                 mutex_lock(&ctx->state_mutex);
456                 __spu_deactivate(ctx, 0, MAX_PRIO);
457                 mutex_unlock(&ctx->state_mutex);
458         }
459 }
460
461 static void spusched_tick(struct spu_context *ctx)
462 {
463         if (ctx->policy == SCHED_FIFO || --ctx->time_slice)
464                 return;
465
466         /*
467          * Unfortunately active_mutex ranks outside of state_mutex, so
468          * we have to trylock here.  If we fail give the context another
469          * tick and try again.
470          */
471         if (mutex_trylock(&ctx->state_mutex)) {
472                 struct spu_context *new = grab_runnable_context(ctx->prio + 1);
473                 if (new) {
474                         struct spu *spu = ctx->spu;
475
476                         __spu_remove_from_active_list(spu);
477                         spu_unbind_context(spu, ctx);
478                         spu_free(spu);
479                         wake_up(&new->stop_wq);
480                         /*
481                          * We need to break out of the wait loop in
482                          * spu_run manually to ensure this context
483                          * gets put on the runqueue again ASAP.
484                          */
485                         wake_up(&ctx->stop_wq);
486                 }
487                 spu_set_timeslice(ctx);
488                 mutex_unlock(&ctx->state_mutex);
489         } else {
490                 ctx->time_slice++;
491         }
492 }
493
494 static void spusched_wake(unsigned long data)
495 {
496         mod_timer(&spusched_timer, jiffies + SPUSCHED_TICK);
497         wake_up_process(spusched_task);
498 }
499
500 static int spusched_thread(void *unused)
501 {
502         struct spu *spu, *next;
503         int node;
504
505         setup_timer(&spusched_timer, spusched_wake, 0);
506         __mod_timer(&spusched_timer, jiffies + SPUSCHED_TICK);
507
508         while (!kthread_should_stop()) {
509                 set_current_state(TASK_INTERRUPTIBLE);
510                 schedule();
511                 for (node = 0; node < MAX_NUMNODES; node++) {
512                         mutex_lock(&spu_prio->active_mutex[node]);
513                         list_for_each_entry_safe(spu, next,
514                                                  &spu_prio->active_list[node],
515                                                  list)
516                                 spusched_tick(spu->ctx);
517                         mutex_unlock(&spu_prio->active_mutex[node]);
518                 }
519         }
520
521         del_timer_sync(&spusched_timer);
522         return 0;
523 }
524
525 int __init spu_sched_init(void)
526 {
527         int i;
528
529         spu_prio = kzalloc(sizeof(struct spu_prio_array), GFP_KERNEL);
530         if (!spu_prio)
531                 return -ENOMEM;
532
533         for (i = 0; i < MAX_PRIO; i++) {
534                 INIT_LIST_HEAD(&spu_prio->runq[i]);
535                 __clear_bit(i, spu_prio->bitmap);
536         }
537         __set_bit(MAX_PRIO, spu_prio->bitmap);
538         for (i = 0; i < MAX_NUMNODES; i++) {
539                 mutex_init(&spu_prio->active_mutex[i]);
540                 INIT_LIST_HEAD(&spu_prio->active_list[i]);
541         }
542         spin_lock_init(&spu_prio->runq_lock);
543
544         spusched_task = kthread_run(spusched_thread, NULL, "spusched");
545         if (IS_ERR(spusched_task)) {
546                 kfree(spu_prio);
547                 return PTR_ERR(spusched_task);
548         }
549         return 0;
550
551 }
552
553 void __exit spu_sched_exit(void)
554 {
555         struct spu *spu, *tmp;
556         int node;
557
558         kthread_stop(spusched_task);
559
560         for (node = 0; node < MAX_NUMNODES; node++) {
561                 mutex_lock(&spu_prio->active_mutex[node]);
562                 list_for_each_entry_safe(spu, tmp, &spu_prio->active_list[node],
563                                          list) {
564                         list_del_init(&spu->list);
565                         spu_free(spu);
566                 }
567                 mutex_unlock(&spu_prio->active_mutex[node]);
568         }
569         kfree(spu_prio);
570 }