Merge commit 'v2.6.26' into bkl-removal
[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 #include <linux/pid_namespace.h>
40 #include <linux/proc_fs.h>
41 #include <linux/seq_file.h>
42 #include <linux/marker.h>
43
44 #include <asm/io.h>
45 #include <asm/mmu_context.h>
46 #include <asm/spu.h>
47 #include <asm/spu_csa.h>
48 #include <asm/spu_priv1.h>
49 #include "spufs.h"
50
51 struct spu_prio_array {
52         DECLARE_BITMAP(bitmap, MAX_PRIO);
53         struct list_head runq[MAX_PRIO];
54         spinlock_t runq_lock;
55         int nr_waiting;
56 };
57
58 static unsigned long spu_avenrun[3];
59 static struct spu_prio_array *spu_prio;
60 static struct task_struct *spusched_task;
61 static struct timer_list spusched_timer;
62 static struct timer_list spuloadavg_timer;
63
64 /*
65  * Priority of a normal, non-rt, non-niced'd process (aka nice level 0).
66  */
67 #define NORMAL_PRIO             120
68
69 /*
70  * Frequency of the spu scheduler tick.  By default we do one SPU scheduler
71  * tick for every 10 CPU scheduler ticks.
72  */
73 #define SPUSCHED_TICK           (10)
74
75 /*
76  * These are the 'tuning knobs' of the scheduler:
77  *
78  * Minimum timeslice is 5 msecs (or 1 spu scheduler tick, whichever is
79  * larger), default timeslice is 100 msecs, maximum timeslice is 800 msecs.
80  */
81 #define MIN_SPU_TIMESLICE       max(5 * HZ / (1000 * SPUSCHED_TICK), 1)
82 #define DEF_SPU_TIMESLICE       (100 * HZ / (1000 * SPUSCHED_TICK))
83
84 #define MAX_USER_PRIO           (MAX_PRIO - MAX_RT_PRIO)
85 #define SCALE_PRIO(x, prio) \
86         max(x * (MAX_PRIO - prio) / (MAX_USER_PRIO / 2), MIN_SPU_TIMESLICE)
87
88 /*
89  * scale user-nice values [ -20 ... 0 ... 19 ] to time slice values:
90  * [800ms ... 100ms ... 5ms]
91  *
92  * The higher a thread's priority, the bigger timeslices
93  * it gets during one round of execution. But even the lowest
94  * priority thread gets MIN_TIMESLICE worth of execution time.
95  */
96 void spu_set_timeslice(struct spu_context *ctx)
97 {
98         if (ctx->prio < NORMAL_PRIO)
99                 ctx->time_slice = SCALE_PRIO(DEF_SPU_TIMESLICE * 4, ctx->prio);
100         else
101                 ctx->time_slice = SCALE_PRIO(DEF_SPU_TIMESLICE, ctx->prio);
102 }
103
104 /*
105  * Update scheduling information from the owning thread.
106  */
107 void __spu_update_sched_info(struct spu_context *ctx)
108 {
109         /*
110          * assert that the context is not on the runqueue, so it is safe
111          * to change its scheduling parameters.
112          */
113         BUG_ON(!list_empty(&ctx->rq));
114
115         /*
116          * 32-Bit assignments are atomic on powerpc, and we don't care about
117          * memory ordering here because retrieving the controlling thread is
118          * per definition racy.
119          */
120         ctx->tid = current->pid;
121
122         /*
123          * We do our own priority calculations, so we normally want
124          * ->static_prio to start with. Unfortunately this field
125          * contains junk for threads with a realtime scheduling
126          * policy so we have to look at ->prio in this case.
127          */
128         if (rt_prio(current->prio))
129                 ctx->prio = current->prio;
130         else
131                 ctx->prio = current->static_prio;
132         ctx->policy = current->policy;
133
134         /*
135          * TO DO: the context may be loaded, so we may need to activate
136          * it again on a different node. But it shouldn't hurt anything
137          * to update its parameters, because we know that the scheduler
138          * is not actively looking at this field, since it is not on the
139          * runqueue. The context will be rescheduled on the proper node
140          * if it is timesliced or preempted.
141          */
142         ctx->cpus_allowed = current->cpus_allowed;
143
144         /* Save the current cpu id for spu interrupt routing. */
145         ctx->last_ran = raw_smp_processor_id();
146 }
147
148 void spu_update_sched_info(struct spu_context *ctx)
149 {
150         int node;
151
152         if (ctx->state == SPU_STATE_RUNNABLE) {
153                 node = ctx->spu->node;
154
155                 /*
156                  * Take list_mutex to sync with find_victim().
157                  */
158                 mutex_lock(&cbe_spu_info[node].list_mutex);
159                 __spu_update_sched_info(ctx);
160                 mutex_unlock(&cbe_spu_info[node].list_mutex);
161         } else {
162                 __spu_update_sched_info(ctx);
163         }
164 }
165
166 static int __node_allowed(struct spu_context *ctx, int node)
167 {
168         if (nr_cpus_node(node)) {
169                 cpumask_t mask = node_to_cpumask(node);
170
171                 if (cpus_intersects(mask, ctx->cpus_allowed))
172                         return 1;
173         }
174
175         return 0;
176 }
177
178 static int node_allowed(struct spu_context *ctx, int node)
179 {
180         int rval;
181
182         spin_lock(&spu_prio->runq_lock);
183         rval = __node_allowed(ctx, node);
184         spin_unlock(&spu_prio->runq_lock);
185
186         return rval;
187 }
188
189 void do_notify_spus_active(void)
190 {
191         int node;
192
193         /*
194          * Wake up the active spu_contexts.
195          *
196          * When the awakened processes see their "notify_active" flag is set,
197          * they will call spu_switch_notify().
198          */
199         for_each_online_node(node) {
200                 struct spu *spu;
201
202                 mutex_lock(&cbe_spu_info[node].list_mutex);
203                 list_for_each_entry(spu, &cbe_spu_info[node].spus, cbe_list) {
204                         if (spu->alloc_state != SPU_FREE) {
205                                 struct spu_context *ctx = spu->ctx;
206                                 set_bit(SPU_SCHED_NOTIFY_ACTIVE,
207                                         &ctx->sched_flags);
208                                 mb();
209                                 wake_up_all(&ctx->stop_wq);
210                         }
211                 }
212                 mutex_unlock(&cbe_spu_info[node].list_mutex);
213         }
214 }
215
216 /**
217  * spu_bind_context - bind spu context to physical spu
218  * @spu:        physical spu to bind to
219  * @ctx:        context to bind
220  */
221 static void spu_bind_context(struct spu *spu, struct spu_context *ctx)
222 {
223         spu_context_trace(spu_bind_context__enter, ctx, spu);
224
225         spuctx_switch_state(ctx, SPU_UTIL_SYSTEM);
226
227         if (ctx->flags & SPU_CREATE_NOSCHED)
228                 atomic_inc(&cbe_spu_info[spu->node].reserved_spus);
229
230         ctx->stats.slb_flt_base = spu->stats.slb_flt;
231         ctx->stats.class2_intr_base = spu->stats.class2_intr;
232
233         spu_associate_mm(spu, ctx->owner);
234
235         spin_lock_irq(&spu->register_lock);
236         spu->ctx = ctx;
237         spu->flags = 0;
238         ctx->spu = spu;
239         ctx->ops = &spu_hw_ops;
240         spu->pid = current->pid;
241         spu->tgid = current->tgid;
242         spu->ibox_callback = spufs_ibox_callback;
243         spu->wbox_callback = spufs_wbox_callback;
244         spu->stop_callback = spufs_stop_callback;
245         spu->mfc_callback = spufs_mfc_callback;
246         spin_unlock_irq(&spu->register_lock);
247
248         spu_unmap_mappings(ctx);
249
250         spu_switch_log_notify(spu, ctx, SWITCH_LOG_START, 0);
251         spu_restore(&ctx->csa, spu);
252         spu->timestamp = jiffies;
253         spu_switch_notify(spu, ctx);
254         ctx->state = SPU_STATE_RUNNABLE;
255
256         spuctx_switch_state(ctx, SPU_UTIL_USER);
257 }
258
259 /*
260  * Must be used with the list_mutex held.
261  */
262 static inline int sched_spu(struct spu *spu)
263 {
264         BUG_ON(!mutex_is_locked(&cbe_spu_info[spu->node].list_mutex));
265
266         return (!spu->ctx || !(spu->ctx->flags & SPU_CREATE_NOSCHED));
267 }
268
269 static void aff_merge_remaining_ctxs(struct spu_gang *gang)
270 {
271         struct spu_context *ctx;
272
273         list_for_each_entry(ctx, &gang->aff_list_head, aff_list) {
274                 if (list_empty(&ctx->aff_list))
275                         list_add(&ctx->aff_list, &gang->aff_list_head);
276         }
277         gang->aff_flags |= AFF_MERGED;
278 }
279
280 static void aff_set_offsets(struct spu_gang *gang)
281 {
282         struct spu_context *ctx;
283         int offset;
284
285         offset = -1;
286         list_for_each_entry_reverse(ctx, &gang->aff_ref_ctx->aff_list,
287                                                                 aff_list) {
288                 if (&ctx->aff_list == &gang->aff_list_head)
289                         break;
290                 ctx->aff_offset = offset--;
291         }
292
293         offset = 0;
294         list_for_each_entry(ctx, gang->aff_ref_ctx->aff_list.prev, aff_list) {
295                 if (&ctx->aff_list == &gang->aff_list_head)
296                         break;
297                 ctx->aff_offset = offset++;
298         }
299
300         gang->aff_flags |= AFF_OFFSETS_SET;
301 }
302
303 static struct spu *aff_ref_location(struct spu_context *ctx, int mem_aff,
304                  int group_size, int lowest_offset)
305 {
306         struct spu *spu;
307         int node, n;
308
309         /*
310          * TODO: A better algorithm could be used to find a good spu to be
311          *       used as reference location for the ctxs chain.
312          */
313         node = cpu_to_node(raw_smp_processor_id());
314         for (n = 0; n < MAX_NUMNODES; n++, node++) {
315                 node = (node < MAX_NUMNODES) ? node : 0;
316                 if (!node_allowed(ctx, node))
317                         continue;
318                 mutex_lock(&cbe_spu_info[node].list_mutex);
319                 list_for_each_entry(spu, &cbe_spu_info[node].spus, cbe_list) {
320                         if ((!mem_aff || spu->has_mem_affinity) &&
321                                                         sched_spu(spu)) {
322                                 mutex_unlock(&cbe_spu_info[node].list_mutex);
323                                 return spu;
324                         }
325                 }
326                 mutex_unlock(&cbe_spu_info[node].list_mutex);
327         }
328         return NULL;
329 }
330
331 static void aff_set_ref_point_location(struct spu_gang *gang)
332 {
333         int mem_aff, gs, lowest_offset;
334         struct spu_context *ctx;
335         struct spu *tmp;
336
337         mem_aff = gang->aff_ref_ctx->flags & SPU_CREATE_AFFINITY_MEM;
338         lowest_offset = 0;
339         gs = 0;
340
341         list_for_each_entry(tmp, &gang->aff_list_head, aff_list)
342                 gs++;
343
344         list_for_each_entry_reverse(ctx, &gang->aff_ref_ctx->aff_list,
345                                                                 aff_list) {
346                 if (&ctx->aff_list == &gang->aff_list_head)
347                         break;
348                 lowest_offset = ctx->aff_offset;
349         }
350
351         gang->aff_ref_spu = aff_ref_location(gang->aff_ref_ctx, mem_aff, gs,
352                                                         lowest_offset);
353 }
354
355 static struct spu *ctx_location(struct spu *ref, int offset, int node)
356 {
357         struct spu *spu;
358
359         spu = NULL;
360         if (offset >= 0) {
361                 list_for_each_entry(spu, ref->aff_list.prev, aff_list) {
362                         BUG_ON(spu->node != node);
363                         if (offset == 0)
364                                 break;
365                         if (sched_spu(spu))
366                                 offset--;
367                 }
368         } else {
369                 list_for_each_entry_reverse(spu, ref->aff_list.next, aff_list) {
370                         BUG_ON(spu->node != node);
371                         if (offset == 0)
372                                 break;
373                         if (sched_spu(spu))
374                                 offset++;
375                 }
376         }
377
378         return spu;
379 }
380
381 /*
382  * affinity_check is called each time a context is going to be scheduled.
383  * It returns the spu ptr on which the context must run.
384  */
385 static int has_affinity(struct spu_context *ctx)
386 {
387         struct spu_gang *gang = ctx->gang;
388
389         if (list_empty(&ctx->aff_list))
390                 return 0;
391
392         if (!gang->aff_ref_spu) {
393                 if (!(gang->aff_flags & AFF_MERGED))
394                         aff_merge_remaining_ctxs(gang);
395                 if (!(gang->aff_flags & AFF_OFFSETS_SET))
396                         aff_set_offsets(gang);
397                 aff_set_ref_point_location(gang);
398         }
399
400         return gang->aff_ref_spu != NULL;
401 }
402
403 /**
404  * spu_unbind_context - unbind spu context from physical spu
405  * @spu:        physical spu to unbind from
406  * @ctx:        context to unbind
407  */
408 static void spu_unbind_context(struct spu *spu, struct spu_context *ctx)
409 {
410         u32 status;
411
412         spu_context_trace(spu_unbind_context__enter, ctx, spu);
413
414         spuctx_switch_state(ctx, SPU_UTIL_SYSTEM);
415
416         if (spu->ctx->flags & SPU_CREATE_NOSCHED)
417                 atomic_dec(&cbe_spu_info[spu->node].reserved_spus);
418
419         if (ctx->gang){
420                 mutex_lock(&ctx->gang->aff_mutex);
421                 if (has_affinity(ctx)) {
422                         if (atomic_dec_and_test(&ctx->gang->aff_sched_count))
423                                 ctx->gang->aff_ref_spu = NULL;
424                 }
425                 mutex_unlock(&ctx->gang->aff_mutex);
426         }
427
428         spu_switch_notify(spu, NULL);
429         spu_unmap_mappings(ctx);
430         spu_save(&ctx->csa, spu);
431         spu_switch_log_notify(spu, ctx, SWITCH_LOG_STOP, 0);
432
433         spin_lock_irq(&spu->register_lock);
434         spu->timestamp = jiffies;
435         ctx->state = SPU_STATE_SAVED;
436         spu->ibox_callback = NULL;
437         spu->wbox_callback = NULL;
438         spu->stop_callback = NULL;
439         spu->mfc_callback = NULL;
440         spu->pid = 0;
441         spu->tgid = 0;
442         ctx->ops = &spu_backing_ops;
443         spu->flags = 0;
444         spu->ctx = NULL;
445         spin_unlock_irq(&spu->register_lock);
446
447         spu_associate_mm(spu, NULL);
448
449         ctx->stats.slb_flt +=
450                 (spu->stats.slb_flt - ctx->stats.slb_flt_base);
451         ctx->stats.class2_intr +=
452                 (spu->stats.class2_intr - ctx->stats.class2_intr_base);
453
454         /* This maps the underlying spu state to idle */
455         spuctx_switch_state(ctx, SPU_UTIL_IDLE_LOADED);
456         ctx->spu = NULL;
457
458         if (spu_stopped(ctx, &status))
459                 wake_up_all(&ctx->stop_wq);
460 }
461
462 /**
463  * spu_add_to_rq - add a context to the runqueue
464  * @ctx:       context to add
465  */
466 static void __spu_add_to_rq(struct spu_context *ctx)
467 {
468         /*
469          * Unfortunately this code path can be called from multiple threads
470          * on behalf of a single context due to the way the problem state
471          * mmap support works.
472          *
473          * Fortunately we need to wake up all these threads at the same time
474          * and can simply skip the runqueue addition for every but the first
475          * thread getting into this codepath.
476          *
477          * It's still quite hacky, and long-term we should proxy all other
478          * threads through the owner thread so that spu_run is in control
479          * of all the scheduling activity for a given context.
480          */
481         if (list_empty(&ctx->rq)) {
482                 list_add_tail(&ctx->rq, &spu_prio->runq[ctx->prio]);
483                 set_bit(ctx->prio, spu_prio->bitmap);
484                 if (!spu_prio->nr_waiting++)
485                         __mod_timer(&spusched_timer, jiffies + SPUSCHED_TICK);
486         }
487 }
488
489 static void spu_add_to_rq(struct spu_context *ctx)
490 {
491         spin_lock(&spu_prio->runq_lock);
492         __spu_add_to_rq(ctx);
493         spin_unlock(&spu_prio->runq_lock);
494 }
495
496 static void __spu_del_from_rq(struct spu_context *ctx)
497 {
498         int prio = ctx->prio;
499
500         if (!list_empty(&ctx->rq)) {
501                 if (!--spu_prio->nr_waiting)
502                         del_timer(&spusched_timer);
503                 list_del_init(&ctx->rq);
504
505                 if (list_empty(&spu_prio->runq[prio]))
506                         clear_bit(prio, spu_prio->bitmap);
507         }
508 }
509
510 void spu_del_from_rq(struct spu_context *ctx)
511 {
512         spin_lock(&spu_prio->runq_lock);
513         __spu_del_from_rq(ctx);
514         spin_unlock(&spu_prio->runq_lock);
515 }
516
517 static void spu_prio_wait(struct spu_context *ctx)
518 {
519         DEFINE_WAIT(wait);
520
521         /*
522          * The caller must explicitly wait for a context to be loaded
523          * if the nosched flag is set.  If NOSCHED is not set, the caller
524          * queues the context and waits for an spu event or error.
525          */
526         BUG_ON(!(ctx->flags & SPU_CREATE_NOSCHED));
527
528         spin_lock(&spu_prio->runq_lock);
529         prepare_to_wait_exclusive(&ctx->stop_wq, &wait, TASK_INTERRUPTIBLE);
530         if (!signal_pending(current)) {
531                 __spu_add_to_rq(ctx);
532                 spin_unlock(&spu_prio->runq_lock);
533                 mutex_unlock(&ctx->state_mutex);
534                 schedule();
535                 mutex_lock(&ctx->state_mutex);
536                 spin_lock(&spu_prio->runq_lock);
537                 __spu_del_from_rq(ctx);
538         }
539         spin_unlock(&spu_prio->runq_lock);
540         __set_current_state(TASK_RUNNING);
541         remove_wait_queue(&ctx->stop_wq, &wait);
542 }
543
544 static struct spu *spu_get_idle(struct spu_context *ctx)
545 {
546         struct spu *spu, *aff_ref_spu;
547         int node, n;
548
549         spu_context_nospu_trace(spu_get_idle__enter, ctx);
550
551         if (ctx->gang) {
552                 mutex_lock(&ctx->gang->aff_mutex);
553                 if (has_affinity(ctx)) {
554                         aff_ref_spu = ctx->gang->aff_ref_spu;
555                         atomic_inc(&ctx->gang->aff_sched_count);
556                         mutex_unlock(&ctx->gang->aff_mutex);
557                         node = aff_ref_spu->node;
558
559                         mutex_lock(&cbe_spu_info[node].list_mutex);
560                         spu = ctx_location(aff_ref_spu, ctx->aff_offset, node);
561                         if (spu && spu->alloc_state == SPU_FREE)
562                                 goto found;
563                         mutex_unlock(&cbe_spu_info[node].list_mutex);
564
565                         mutex_lock(&ctx->gang->aff_mutex);
566                         if (atomic_dec_and_test(&ctx->gang->aff_sched_count))
567                                 ctx->gang->aff_ref_spu = NULL;
568                         mutex_unlock(&ctx->gang->aff_mutex);
569                         goto not_found;
570                 }
571                 mutex_unlock(&ctx->gang->aff_mutex);
572         }
573         node = cpu_to_node(raw_smp_processor_id());
574         for (n = 0; n < MAX_NUMNODES; n++, node++) {
575                 node = (node < MAX_NUMNODES) ? node : 0;
576                 if (!node_allowed(ctx, node))
577                         continue;
578
579                 mutex_lock(&cbe_spu_info[node].list_mutex);
580                 list_for_each_entry(spu, &cbe_spu_info[node].spus, cbe_list) {
581                         if (spu->alloc_state == SPU_FREE)
582                                 goto found;
583                 }
584                 mutex_unlock(&cbe_spu_info[node].list_mutex);
585         }
586
587  not_found:
588         spu_context_nospu_trace(spu_get_idle__not_found, ctx);
589         return NULL;
590
591  found:
592         spu->alloc_state = SPU_USED;
593         mutex_unlock(&cbe_spu_info[node].list_mutex);
594         spu_context_trace(spu_get_idle__found, ctx, spu);
595         spu_init_channels(spu);
596         return spu;
597 }
598
599 /**
600  * find_victim - find a lower priority context to preempt
601  * @ctx:        canidate context for running
602  *
603  * Returns the freed physical spu to run the new context on.
604  */
605 static struct spu *find_victim(struct spu_context *ctx)
606 {
607         struct spu_context *victim = NULL;
608         struct spu *spu;
609         int node, n;
610
611         spu_context_nospu_trace(spu_find_victim__enter, ctx);
612
613         /*
614          * Look for a possible preemption candidate on the local node first.
615          * If there is no candidate look at the other nodes.  This isn't
616          * exactly fair, but so far the whole spu scheduler tries to keep
617          * a strong node affinity.  We might want to fine-tune this in
618          * the future.
619          */
620  restart:
621         node = cpu_to_node(raw_smp_processor_id());
622         for (n = 0; n < MAX_NUMNODES; n++, node++) {
623                 node = (node < MAX_NUMNODES) ? node : 0;
624                 if (!node_allowed(ctx, node))
625                         continue;
626
627                 mutex_lock(&cbe_spu_info[node].list_mutex);
628                 list_for_each_entry(spu, &cbe_spu_info[node].spus, cbe_list) {
629                         struct spu_context *tmp = spu->ctx;
630
631                         if (tmp && tmp->prio > ctx->prio &&
632                             !(tmp->flags & SPU_CREATE_NOSCHED) &&
633                             (!victim || tmp->prio > victim->prio))
634                                 victim = spu->ctx;
635                 }
636                 mutex_unlock(&cbe_spu_info[node].list_mutex);
637
638                 if (victim) {
639                         /*
640                          * This nests ctx->state_mutex, but we always lock
641                          * higher priority contexts before lower priority
642                          * ones, so this is safe until we introduce
643                          * priority inheritance schemes.
644                          *
645                          * XXX if the highest priority context is locked,
646                          * this can loop a long time.  Might be better to
647                          * look at another context or give up after X retries.
648                          */
649                         if (!mutex_trylock(&victim->state_mutex)) {
650                                 victim = NULL;
651                                 goto restart;
652                         }
653
654                         spu = victim->spu;
655                         if (!spu || victim->prio <= ctx->prio) {
656                                 /*
657                                  * This race can happen because we've dropped
658                                  * the active list mutex.  Not a problem, just
659                                  * restart the search.
660                                  */
661                                 mutex_unlock(&victim->state_mutex);
662                                 victim = NULL;
663                                 goto restart;
664                         }
665
666                         spu_context_trace(__spu_deactivate__unload, ctx, spu);
667
668                         mutex_lock(&cbe_spu_info[node].list_mutex);
669                         cbe_spu_info[node].nr_active--;
670                         spu_unbind_context(spu, victim);
671                         mutex_unlock(&cbe_spu_info[node].list_mutex);
672
673                         victim->stats.invol_ctx_switch++;
674                         spu->stats.invol_ctx_switch++;
675                         if (test_bit(SPU_SCHED_SPU_RUN, &victim->sched_flags))
676                                 spu_add_to_rq(victim);
677
678                         mutex_unlock(&victim->state_mutex);
679
680                         return spu;
681                 }
682         }
683
684         return NULL;
685 }
686
687 static void __spu_schedule(struct spu *spu, struct spu_context *ctx)
688 {
689         int node = spu->node;
690         int success = 0;
691
692         spu_set_timeslice(ctx);
693
694         mutex_lock(&cbe_spu_info[node].list_mutex);
695         if (spu->ctx == NULL) {
696                 spu_bind_context(spu, ctx);
697                 cbe_spu_info[node].nr_active++;
698                 spu->alloc_state = SPU_USED;
699                 success = 1;
700         }
701         mutex_unlock(&cbe_spu_info[node].list_mutex);
702
703         if (success)
704                 wake_up_all(&ctx->run_wq);
705         else
706                 spu_add_to_rq(ctx);
707 }
708
709 static void spu_schedule(struct spu *spu, struct spu_context *ctx)
710 {
711         /* not a candidate for interruptible because it's called either
712            from the scheduler thread or from spu_deactivate */
713         mutex_lock(&ctx->state_mutex);
714         __spu_schedule(spu, ctx);
715         spu_release(ctx);
716 }
717
718 static void spu_unschedule(struct spu *spu, struct spu_context *ctx)
719 {
720         int node = spu->node;
721
722         mutex_lock(&cbe_spu_info[node].list_mutex);
723         cbe_spu_info[node].nr_active--;
724         spu->alloc_state = SPU_FREE;
725         spu_unbind_context(spu, ctx);
726         ctx->stats.invol_ctx_switch++;
727         spu->stats.invol_ctx_switch++;
728         mutex_unlock(&cbe_spu_info[node].list_mutex);
729 }
730
731 /**
732  * spu_activate - find a free spu for a context and execute it
733  * @ctx:        spu context to schedule
734  * @flags:      flags (currently ignored)
735  *
736  * Tries to find a free spu to run @ctx.  If no free spu is available
737  * add the context to the runqueue so it gets woken up once an spu
738  * is available.
739  */
740 int spu_activate(struct spu_context *ctx, unsigned long flags)
741 {
742         struct spu *spu;
743
744         /*
745          * If there are multiple threads waiting for a single context
746          * only one actually binds the context while the others will
747          * only be able to acquire the state_mutex once the context
748          * already is in runnable state.
749          */
750         if (ctx->spu)
751                 return 0;
752
753 spu_activate_top:
754         if (signal_pending(current))
755                 return -ERESTARTSYS;
756
757         spu = spu_get_idle(ctx);
758         /*
759          * If this is a realtime thread we try to get it running by
760          * preempting a lower priority thread.
761          */
762         if (!spu && rt_prio(ctx->prio))
763                 spu = find_victim(ctx);
764         if (spu) {
765                 unsigned long runcntl;
766
767                 runcntl = ctx->ops->runcntl_read(ctx);
768                 __spu_schedule(spu, ctx);
769                 if (runcntl & SPU_RUNCNTL_RUNNABLE)
770                         spuctx_switch_state(ctx, SPU_UTIL_USER);
771
772                 return 0;
773         }
774
775         if (ctx->flags & SPU_CREATE_NOSCHED) {
776                 spu_prio_wait(ctx);
777                 goto spu_activate_top;
778         }
779
780         spu_add_to_rq(ctx);
781
782         return 0;
783 }
784
785 /**
786  * grab_runnable_context - try to find a runnable context
787  *
788  * Remove the highest priority context on the runqueue and return it
789  * to the caller.  Returns %NULL if no runnable context was found.
790  */
791 static struct spu_context *grab_runnable_context(int prio, int node)
792 {
793         struct spu_context *ctx;
794         int best;
795
796         spin_lock(&spu_prio->runq_lock);
797         best = find_first_bit(spu_prio->bitmap, prio);
798         while (best < prio) {
799                 struct list_head *rq = &spu_prio->runq[best];
800
801                 list_for_each_entry(ctx, rq, rq) {
802                         /* XXX(hch): check for affinity here aswell */
803                         if (__node_allowed(ctx, node)) {
804                                 __spu_del_from_rq(ctx);
805                                 goto found;
806                         }
807                 }
808                 best++;
809         }
810         ctx = NULL;
811  found:
812         spin_unlock(&spu_prio->runq_lock);
813         return ctx;
814 }
815
816 static int __spu_deactivate(struct spu_context *ctx, int force, int max_prio)
817 {
818         struct spu *spu = ctx->spu;
819         struct spu_context *new = NULL;
820
821         if (spu) {
822                 new = grab_runnable_context(max_prio, spu->node);
823                 if (new || force) {
824                         spu_unschedule(spu, ctx);
825                         if (new) {
826                                 if (new->flags & SPU_CREATE_NOSCHED)
827                                         wake_up(&new->stop_wq);
828                                 else {
829                                         spu_release(ctx);
830                                         spu_schedule(spu, new);
831                                         /* this one can't easily be made
832                                            interruptible */
833                                         mutex_lock(&ctx->state_mutex);
834                                 }
835                         }
836                 }
837         }
838
839         return new != NULL;
840 }
841
842 /**
843  * spu_deactivate - unbind a context from it's physical spu
844  * @ctx:        spu context to unbind
845  *
846  * Unbind @ctx from the physical spu it is running on and schedule
847  * the highest priority context to run on the freed physical spu.
848  */
849 void spu_deactivate(struct spu_context *ctx)
850 {
851         spu_context_nospu_trace(spu_deactivate__enter, ctx);
852         __spu_deactivate(ctx, 1, MAX_PRIO);
853 }
854
855 /**
856  * spu_yield -  yield a physical spu if others are waiting
857  * @ctx:        spu context to yield
858  *
859  * Check if there is a higher priority context waiting and if yes
860  * unbind @ctx from the physical spu and schedule the highest
861  * priority context to run on the freed physical spu instead.
862  */
863 void spu_yield(struct spu_context *ctx)
864 {
865         spu_context_nospu_trace(spu_yield__enter, ctx);
866         if (!(ctx->flags & SPU_CREATE_NOSCHED)) {
867                 mutex_lock(&ctx->state_mutex);
868                 __spu_deactivate(ctx, 0, MAX_PRIO);
869                 mutex_unlock(&ctx->state_mutex);
870         }
871 }
872
873 static noinline void spusched_tick(struct spu_context *ctx)
874 {
875         struct spu_context *new = NULL;
876         struct spu *spu = NULL;
877
878         if (spu_acquire(ctx))
879                 BUG();  /* a kernel thread never has signals pending */
880
881         if (ctx->state != SPU_STATE_RUNNABLE)
882                 goto out;
883         if (ctx->flags & SPU_CREATE_NOSCHED)
884                 goto out;
885         if (ctx->policy == SCHED_FIFO)
886                 goto out;
887
888         if (--ctx->time_slice && test_bit(SPU_SCHED_SPU_RUN, &ctx->sched_flags))
889                 goto out;
890
891         spu = ctx->spu;
892
893         spu_context_trace(spusched_tick__preempt, ctx, spu);
894
895         new = grab_runnable_context(ctx->prio + 1, spu->node);
896         if (new) {
897                 spu_unschedule(spu, ctx);
898                 if (test_bit(SPU_SCHED_SPU_RUN, &ctx->sched_flags))
899                         spu_add_to_rq(ctx);
900         } else {
901                 spu_context_nospu_trace(spusched_tick__newslice, ctx);
902                 ctx->time_slice++;
903         }
904 out:
905         spu_release(ctx);
906
907         if (new)
908                 spu_schedule(spu, new);
909 }
910
911 /**
912  * count_active_contexts - count nr of active tasks
913  *
914  * Return the number of tasks currently running or waiting to run.
915  *
916  * Note that we don't take runq_lock / list_mutex here.  Reading
917  * a single 32bit value is atomic on powerpc, and we don't care
918  * about memory ordering issues here.
919  */
920 static unsigned long count_active_contexts(void)
921 {
922         int nr_active = 0, node;
923
924         for (node = 0; node < MAX_NUMNODES; node++)
925                 nr_active += cbe_spu_info[node].nr_active;
926         nr_active += spu_prio->nr_waiting;
927
928         return nr_active;
929 }
930
931 /**
932  * spu_calc_load - update the avenrun load estimates.
933  *
934  * No locking against reading these values from userspace, as for
935  * the CPU loadavg code.
936  */
937 static void spu_calc_load(void)
938 {
939         unsigned long active_tasks; /* fixed-point */
940
941         active_tasks = count_active_contexts() * FIXED_1;
942         CALC_LOAD(spu_avenrun[0], EXP_1, active_tasks);
943         CALC_LOAD(spu_avenrun[1], EXP_5, active_tasks);
944         CALC_LOAD(spu_avenrun[2], EXP_15, active_tasks);
945 }
946
947 static void spusched_wake(unsigned long data)
948 {
949         mod_timer(&spusched_timer, jiffies + SPUSCHED_TICK);
950         wake_up_process(spusched_task);
951 }
952
953 static void spuloadavg_wake(unsigned long data)
954 {
955         mod_timer(&spuloadavg_timer, jiffies + LOAD_FREQ);
956         spu_calc_load();
957 }
958
959 static int spusched_thread(void *unused)
960 {
961         struct spu *spu;
962         int node;
963
964         while (!kthread_should_stop()) {
965                 set_current_state(TASK_INTERRUPTIBLE);
966                 schedule();
967                 for (node = 0; node < MAX_NUMNODES; node++) {
968                         struct mutex *mtx = &cbe_spu_info[node].list_mutex;
969
970                         mutex_lock(mtx);
971                         list_for_each_entry(spu, &cbe_spu_info[node].spus,
972                                         cbe_list) {
973                                 struct spu_context *ctx = spu->ctx;
974
975                                 if (ctx) {
976                                         mutex_unlock(mtx);
977                                         spusched_tick(ctx);
978                                         mutex_lock(mtx);
979                                 }
980                         }
981                         mutex_unlock(mtx);
982                 }
983         }
984
985         return 0;
986 }
987
988 void spuctx_switch_state(struct spu_context *ctx,
989                 enum spu_utilization_state new_state)
990 {
991         unsigned long long curtime;
992         signed long long delta;
993         struct timespec ts;
994         struct spu *spu;
995         enum spu_utilization_state old_state;
996
997         ktime_get_ts(&ts);
998         curtime = timespec_to_ns(&ts);
999         delta = curtime - ctx->stats.tstamp;
1000
1001         WARN_ON(!mutex_is_locked(&ctx->state_mutex));
1002         WARN_ON(delta < 0);
1003
1004         spu = ctx->spu;
1005         old_state = ctx->stats.util_state;
1006         ctx->stats.util_state = new_state;
1007         ctx->stats.tstamp = curtime;
1008
1009         /*
1010          * Update the physical SPU utilization statistics.
1011          */
1012         if (spu) {
1013                 ctx->stats.times[old_state] += delta;
1014                 spu->stats.times[old_state] += delta;
1015                 spu->stats.util_state = new_state;
1016                 spu->stats.tstamp = curtime;
1017         }
1018 }
1019
1020 #define LOAD_INT(x) ((x) >> FSHIFT)
1021 #define LOAD_FRAC(x) LOAD_INT(((x) & (FIXED_1-1)) * 100)
1022
1023 static int show_spu_loadavg(struct seq_file *s, void *private)
1024 {
1025         int a, b, c;
1026
1027         a = spu_avenrun[0] + (FIXED_1/200);
1028         b = spu_avenrun[1] + (FIXED_1/200);
1029         c = spu_avenrun[2] + (FIXED_1/200);
1030
1031         /*
1032          * Note that last_pid doesn't really make much sense for the
1033          * SPU loadavg (it even seems very odd on the CPU side...),
1034          * but we include it here to have a 100% compatible interface.
1035          */
1036         seq_printf(s, "%d.%02d %d.%02d %d.%02d %ld/%d %d\n",
1037                 LOAD_INT(a), LOAD_FRAC(a),
1038                 LOAD_INT(b), LOAD_FRAC(b),
1039                 LOAD_INT(c), LOAD_FRAC(c),
1040                 count_active_contexts(),
1041                 atomic_read(&nr_spu_contexts),
1042                 current->nsproxy->pid_ns->last_pid);
1043         return 0;
1044 }
1045
1046 static int spu_loadavg_open(struct inode *inode, struct file *file)
1047 {
1048         return single_open(file, show_spu_loadavg, NULL);
1049 }
1050
1051 static const struct file_operations spu_loadavg_fops = {
1052         .open           = spu_loadavg_open,
1053         .read           = seq_read,
1054         .llseek         = seq_lseek,
1055         .release        = single_release,
1056 };
1057
1058 int __init spu_sched_init(void)
1059 {
1060         struct proc_dir_entry *entry;
1061         int err = -ENOMEM, i;
1062
1063         spu_prio = kzalloc(sizeof(struct spu_prio_array), GFP_KERNEL);
1064         if (!spu_prio)
1065                 goto out;
1066
1067         for (i = 0; i < MAX_PRIO; i++) {
1068                 INIT_LIST_HEAD(&spu_prio->runq[i]);
1069                 __clear_bit(i, spu_prio->bitmap);
1070         }
1071         spin_lock_init(&spu_prio->runq_lock);
1072
1073         setup_timer(&spusched_timer, spusched_wake, 0);
1074         setup_timer(&spuloadavg_timer, spuloadavg_wake, 0);
1075
1076         spusched_task = kthread_run(spusched_thread, NULL, "spusched");
1077         if (IS_ERR(spusched_task)) {
1078                 err = PTR_ERR(spusched_task);
1079                 goto out_free_spu_prio;
1080         }
1081
1082         mod_timer(&spuloadavg_timer, 0);
1083
1084         entry = proc_create("spu_loadavg", 0, NULL, &spu_loadavg_fops);
1085         if (!entry)
1086                 goto out_stop_kthread;
1087
1088         pr_debug("spusched: tick: %d, min ticks: %d, default ticks: %d\n",
1089                         SPUSCHED_TICK, MIN_SPU_TIMESLICE, DEF_SPU_TIMESLICE);
1090         return 0;
1091
1092  out_stop_kthread:
1093         kthread_stop(spusched_task);
1094  out_free_spu_prio:
1095         kfree(spu_prio);
1096  out:
1097         return err;
1098 }
1099
1100 void spu_sched_exit(void)
1101 {
1102         struct spu *spu;
1103         int node;
1104
1105         remove_proc_entry("spu_loadavg", NULL);
1106
1107         del_timer_sync(&spusched_timer);
1108         del_timer_sync(&spuloadavg_timer);
1109         kthread_stop(spusched_task);
1110
1111         for (node = 0; node < MAX_NUMNODES; node++) {
1112                 mutex_lock(&cbe_spu_info[node].list_mutex);
1113                 list_for_each_entry(spu, &cbe_spu_info[node].spus, cbe_list)
1114                         if (spu->alloc_state != SPU_FREE)
1115                                 spu->alloc_state = SPU_FREE;
1116                 mutex_unlock(&cbe_spu_info[node].list_mutex);
1117         }
1118         kfree(spu_prio);
1119 }