[POWERPC] spufs: Add tid file
[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 1 spu scheduler tick, whichever is
74  * larger), default timeslice is 100 msecs, maximum timeslice is 800 msecs.
75  */
76 #define MIN_SPU_TIMESLICE       max(5 * HZ / (1000 * SPUSCHED_TICK), 1)
77 #define DEF_SPU_TIMESLICE       (100 * HZ / (1000 * SPUSCHED_TICK))
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 /*
100  * Update scheduling information from the owning thread.
101  */
102 void __spu_update_sched_info(struct spu_context *ctx)
103 {
104         /*
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.
108          */
109         ctx->tid = current->pid;
110
111         /*
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.
116          */
117         if (rt_prio(current->prio))
118                 ctx->prio = current->prio;
119         else
120                 ctx->prio = current->static_prio;
121         ctx->policy = current->policy;
122
123         /*
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.
128          */
129         spin_lock(&spu_prio->runq_lock);
130         ctx->cpus_allowed = current->cpus_allowed;
131         spin_unlock(&spu_prio->runq_lock);
132 }
133
134 void spu_update_sched_info(struct spu_context *ctx)
135 {
136         int node = ctx->spu->node;
137
138         mutex_lock(&spu_prio->active_mutex[node]);
139         __spu_update_sched_info(ctx);
140         mutex_unlock(&spu_prio->active_mutex[node]);
141 }
142
143 static int __node_allowed(struct spu_context *ctx, int node)
144 {
145         if (nr_cpus_node(node)) {
146                 cpumask_t mask = node_to_cpumask(node);
147
148                 if (cpus_intersects(mask, ctx->cpus_allowed))
149                         return 1;
150         }
151
152         return 0;
153 }
154
155 static int node_allowed(struct spu_context *ctx, int node)
156 {
157         int rval;
158
159         spin_lock(&spu_prio->runq_lock);
160         rval = __node_allowed(ctx, node);
161         spin_unlock(&spu_prio->runq_lock);
162
163         return rval;
164 }
165
166 /**
167  * spu_add_to_active_list - add spu to active list
168  * @spu:        spu to add to the active list
169  */
170 static void spu_add_to_active_list(struct spu *spu)
171 {
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]);
175 }
176
177 static void __spu_remove_from_active_list(struct spu *spu)
178 {
179         list_del_init(&spu->list);
180 }
181
182 /**
183  * spu_remove_from_active_list - remove spu from active list
184  * @spu:       spu to remove from the active list
185  */
186 static void spu_remove_from_active_list(struct spu *spu)
187 {
188         int node = spu->node;
189
190         mutex_lock(&spu_prio->active_mutex[node]);
191         __spu_remove_from_active_list(spu);
192         mutex_unlock(&spu_prio->active_mutex[node]);
193 }
194
195 static BLOCKING_NOTIFIER_HEAD(spu_switch_notifier);
196
197 static void spu_switch_notify(struct spu *spu, struct spu_context *ctx)
198 {
199         blocking_notifier_call_chain(&spu_switch_notifier,
200                             ctx ? ctx->object_id : 0, spu);
201 }
202
203 int spu_switch_event_register(struct notifier_block * n)
204 {
205         return blocking_notifier_chain_register(&spu_switch_notifier, n);
206 }
207
208 int spu_switch_event_unregister(struct notifier_block * n)
209 {
210         return blocking_notifier_chain_unregister(&spu_switch_notifier, n);
211 }
212
213 /**
214  * spu_bind_context - bind spu context to physical spu
215  * @spu:        physical spu to bind to
216  * @ctx:        context to bind
217  */
218 static void spu_bind_context(struct spu *spu, struct spu_context *ctx)
219 {
220         pr_debug("%s: pid=%d SPU=%d NODE=%d\n", __FUNCTION__, current->pid,
221                  spu->number, spu->node);
222         spu->ctx = ctx;
223         spu->flags = 0;
224         ctx->spu = spu;
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;
233         mb();
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;
240 }
241
242 /**
243  * spu_unbind_context - unbind spu context from physical spu
244  * @spu:        physical spu to unbind from
245  * @ctx:        context to unbind
246  */
247 static void spu_unbind_context(struct spu *spu, struct spu_context *ctx)
248 {
249         pr_debug("%s: unbind pid=%d SPU=%d NODE=%d\n", __FUNCTION__,
250                  spu->pid, spu->number, spu->node);
251
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);
263         spu->pid = 0;
264         ctx->ops = &spu_backing_ops;
265         ctx->spu = NULL;
266         spu->flags = 0;
267         spu->ctx = NULL;
268 }
269
270 /**
271  * spu_add_to_rq - add a context to the runqueue
272  * @ctx:       context to add
273  */
274 static void __spu_add_to_rq(struct spu_context *ctx)
275 {
276         int prio = ctx->prio;
277
278         list_add_tail(&ctx->rq, &spu_prio->runq[prio]);
279         set_bit(prio, spu_prio->bitmap);
280 }
281
282 static void __spu_del_from_rq(struct spu_context *ctx)
283 {
284         int prio = ctx->prio;
285
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);
290 }
291
292 static void spu_prio_wait(struct spu_context *ctx)
293 {
294         DEFINE_WAIT(wait);
295
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);
302                 schedule();
303                 mutex_lock(&ctx->state_mutex);
304                 spin_lock(&spu_prio->runq_lock);
305                 __spu_del_from_rq(ctx);
306         }
307         spin_unlock(&spu_prio->runq_lock);
308         __set_current_state(TASK_RUNNING);
309         remove_wait_queue(&ctx->stop_wq, &wait);
310 }
311
312 static struct spu *spu_get_idle(struct spu_context *ctx)
313 {
314         struct spu *spu = NULL;
315         int node = cpu_to_node(raw_smp_processor_id());
316         int n;
317
318         for (n = 0; n < MAX_NUMNODES; n++, node++) {
319                 node = (node < MAX_NUMNODES) ? node : 0;
320                 if (!node_allowed(ctx, node))
321                         continue;
322                 spu = spu_alloc_node(node);
323                 if (spu)
324                         break;
325         }
326         return spu;
327 }
328
329 /**
330  * find_victim - find a lower priority context to preempt
331  * @ctx:        canidate context for running
332  *
333  * Returns the freed physical spu to run the new context on.
334  */
335 static struct spu *find_victim(struct spu_context *ctx)
336 {
337         struct spu_context *victim = NULL;
338         struct spu *spu;
339         int node, n;
340
341         /*
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
346          * the future.
347          */
348  restart:
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))
353                         continue;
354
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;
358
359                         if (tmp->prio > ctx->prio &&
360                             (!victim || tmp->prio > victim->prio))
361                                 victim = spu->ctx;
362                 }
363                 mutex_unlock(&spu_prio->active_mutex[node]);
364
365                 if (victim) {
366                         /*
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.
371                          */
372                         if (!mutex_trylock(&victim->state_mutex)) {
373                                 victim = NULL;
374                                 goto restart;
375                         }
376
377                         spu = victim->spu;
378                         if (!spu) {
379                                 /*
380                                  * This race can happen because we've dropped
381                                  * the active list mutex.  No a problem, just
382                                  * restart the search.
383                                  */
384                                 mutex_unlock(&victim->state_mutex);
385                                 victim = NULL;
386                                 goto restart;
387                         }
388                         spu_remove_from_active_list(spu);
389                         spu_unbind_context(spu, victim);
390                         mutex_unlock(&victim->state_mutex);
391                         /*
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.
395                          */
396                         wake_up(&victim->stop_wq);
397                         return spu;
398                 }
399         }
400
401         return NULL;
402 }
403
404 /**
405  * spu_activate - find a free spu for a context and execute it
406  * @ctx:        spu context to schedule
407  * @flags:      flags (currently ignored)
408  *
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
411  * is available.
412  */
413 int spu_activate(struct spu_context *ctx, unsigned long flags)
414 {
415
416         if (ctx->spu)
417                 return 0;
418
419         do {
420                 struct spu *spu;
421
422                 spu = spu_get_idle(ctx);
423                 /*
424                  * If this is a realtime thread we try to get it running by
425                  * preempting a lower priority thread.
426                  */
427                 if (!spu && rt_prio(ctx->prio))
428                         spu = find_victim(ctx);
429                 if (spu) {
430                         spu_bind_context(spu, ctx);
431                         spu_add_to_active_list(spu);
432                         return 0;
433                 }
434
435                 spu_prio_wait(ctx);
436         } while (!signal_pending(current));
437
438         return -ERESTARTSYS;
439 }
440
441 /**
442  * grab_runnable_context - try to find a runnable context
443  *
444  * Remove the highest priority context on the runqueue and return it
445  * to the caller.  Returns %NULL if no runnable context was found.
446  */
447 static struct spu_context *grab_runnable_context(int prio, int node)
448 {
449         struct spu_context *ctx;
450         int best;
451
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];
456
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);
461                                 goto found;
462                         }
463                 }
464                 best++;
465         }
466         ctx = NULL;
467  found:
468         spin_unlock(&spu_prio->runq_lock);
469         return ctx;
470 }
471
472 static int __spu_deactivate(struct spu_context *ctx, int force, int max_prio)
473 {
474         struct spu *spu = ctx->spu;
475         struct spu_context *new = NULL;
476
477         if (spu) {
478                 new = grab_runnable_context(max_prio, spu->node);
479                 if (new || force) {
480                         spu_remove_from_active_list(spu);
481                         spu_unbind_context(spu, ctx);
482                         spu_free(spu);
483                         if (new)
484                                 wake_up(&new->stop_wq);
485                 }
486
487         }
488
489         return new != NULL;
490 }
491
492 /**
493  * spu_deactivate - unbind a context from it's physical spu
494  * @ctx:        spu context to unbind
495  *
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.
498  */
499 void spu_deactivate(struct spu_context *ctx)
500 {
501         /*
502          * We must never reach this for a nosched context,
503          * but handle the case gracefull instead of panicing.
504          */
505         if (ctx->flags & SPU_CREATE_NOSCHED) {
506                 WARN_ON(1);
507                 return;
508         }
509
510         __spu_deactivate(ctx, 1, MAX_PRIO);
511 }
512
513 /**
514  * spu_yield -  yield a physical spu if others are waiting
515  * @ctx:        spu context to yield
516  *
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.
520  */
521 void spu_yield(struct spu_context *ctx)
522 {
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);
527         }
528 }
529
530 static void spusched_tick(struct spu_context *ctx)
531 {
532         if (ctx->flags & SPU_CREATE_NOSCHED)
533                 return;
534         if (ctx->policy == SCHED_FIFO)
535                 return;
536
537         if (--ctx->time_slice)
538                 return;
539
540         /*
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.
544          */
545         if (mutex_trylock(&ctx->state_mutex)) {
546                 struct spu *spu = ctx->spu;
547                 struct spu_context *new;
548
549                 new = grab_runnable_context(ctx->prio + 1, spu->node);
550                 if (new) {
551
552                         __spu_remove_from_active_list(spu);
553                         spu_unbind_context(spu, ctx);
554                         spu_free(spu);
555                         wake_up(&new->stop_wq);
556                         /*
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.
560                          */
561                         wake_up(&ctx->stop_wq);
562                 }
563                 spu_set_timeslice(ctx);
564                 mutex_unlock(&ctx->state_mutex);
565         } else {
566                 ctx->time_slice++;
567         }
568 }
569
570 static void spusched_wake(unsigned long data)
571 {
572         mod_timer(&spusched_timer, jiffies + SPUSCHED_TICK);
573         wake_up_process(spusched_task);
574 }
575
576 static int spusched_thread(void *unused)
577 {
578         struct spu *spu, *next;
579         int node;
580
581         setup_timer(&spusched_timer, spusched_wake, 0);
582         __mod_timer(&spusched_timer, jiffies + SPUSCHED_TICK);
583
584         while (!kthread_should_stop()) {
585                 set_current_state(TASK_INTERRUPTIBLE);
586                 schedule();
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],
591                                                  list)
592                                 spusched_tick(spu->ctx);
593                         mutex_unlock(&spu_prio->active_mutex[node]);
594                 }
595         }
596
597         del_timer_sync(&spusched_timer);
598         return 0;
599 }
600
601 int __init spu_sched_init(void)
602 {
603         int i;
604
605         spu_prio = kzalloc(sizeof(struct spu_prio_array), GFP_KERNEL);
606         if (!spu_prio)
607                 return -ENOMEM;
608
609         for (i = 0; i < MAX_PRIO; i++) {
610                 INIT_LIST_HEAD(&spu_prio->runq[i]);
611                 __clear_bit(i, spu_prio->bitmap);
612         }
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]);
617         }
618         spin_lock_init(&spu_prio->runq_lock);
619
620         spusched_task = kthread_run(spusched_thread, NULL, "spusched");
621         if (IS_ERR(spusched_task)) {
622                 kfree(spu_prio);
623                 return PTR_ERR(spusched_task);
624         }
625
626         pr_debug("spusched: tick: %d, min ticks: %d, default ticks: %d\n",
627                         SPUSCHED_TICK, MIN_SPU_TIMESLICE, DEF_SPU_TIMESLICE);
628         return 0;
629
630 }
631
632 void __exit spu_sched_exit(void)
633 {
634         struct spu *spu, *tmp;
635         int node;
636
637         kthread_stop(spusched_task);
638
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],
642                                          list) {
643                         list_del_init(&spu->list);
644                         spu_free(spu);
645                 }
646                 mutex_unlock(&spu_prio->active_mutex[node]);
647         }
648         kfree(spu_prio);
649 }