Merge master.kernel.org:/pub/scm/linux/kernel/git/davem/net-2.6
[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/smp_lock.h>
34 #include <linux/stddef.h>
35 #include <linux/unistd.h>
36 #include <linux/numa.h>
37 #include <linux/mutex.h>
38 #include <linux/notifier.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 #define SPU_TIMESLICE   (HZ)
48
49 struct spu_prio_array {
50         DECLARE_BITMAP(bitmap, MAX_PRIO);
51         struct list_head runq[MAX_PRIO];
52         spinlock_t runq_lock;
53         struct list_head active_list[MAX_NUMNODES];
54         struct mutex active_mutex[MAX_NUMNODES];
55 };
56
57 static struct spu_prio_array *spu_prio;
58 static struct workqueue_struct *spu_sched_wq;
59
60 static inline int node_allowed(int node)
61 {
62         cpumask_t mask;
63
64         if (!nr_cpus_node(node))
65                 return 0;
66         mask = node_to_cpumask(node);
67         if (!cpus_intersects(mask, current->cpus_allowed))
68                 return 0;
69         return 1;
70 }
71
72 void spu_start_tick(struct spu_context *ctx)
73 {
74         if (ctx->policy == SCHED_RR)
75                 queue_delayed_work(spu_sched_wq, &ctx->sched_work, SPU_TIMESLICE);
76 }
77
78 void spu_stop_tick(struct spu_context *ctx)
79 {
80         if (ctx->policy == SCHED_RR)
81                 cancel_delayed_work(&ctx->sched_work);
82 }
83
84 void spu_sched_tick(struct work_struct *work)
85 {
86         struct spu_context *ctx =
87                 container_of(work, struct spu_context, sched_work.work);
88         struct spu *spu;
89         int rearm = 1;
90
91         mutex_lock(&ctx->state_mutex);
92         spu = ctx->spu;
93         if (spu) {
94                 int best = sched_find_first_bit(spu_prio->bitmap);
95                 if (best <= ctx->prio) {
96                         spu_deactivate(ctx);
97                         rearm = 0;
98                 }
99         }
100         mutex_unlock(&ctx->state_mutex);
101
102         if (rearm)
103                 spu_start_tick(ctx);
104 }
105
106 /**
107  * spu_add_to_active_list - add spu to active list
108  * @spu:        spu to add to the active list
109  */
110 static void spu_add_to_active_list(struct spu *spu)
111 {
112         mutex_lock(&spu_prio->active_mutex[spu->node]);
113         list_add_tail(&spu->list, &spu_prio->active_list[spu->node]);
114         mutex_unlock(&spu_prio->active_mutex[spu->node]);
115 }
116
117 /**
118  * spu_remove_from_active_list - remove spu from active list
119  * @spu:       spu to remove from the active list
120  */
121 static void spu_remove_from_active_list(struct spu *spu)
122 {
123         int node = spu->node;
124
125         mutex_lock(&spu_prio->active_mutex[node]);
126         list_del_init(&spu->list);
127         mutex_unlock(&spu_prio->active_mutex[node]);
128 }
129
130 static inline void mm_needs_global_tlbie(struct mm_struct *mm)
131 {
132         int nr = (NR_CPUS > 1) ? NR_CPUS : NR_CPUS + 1;
133
134         /* Global TLBIE broadcast required with SPEs. */
135         __cpus_setall(&mm->cpu_vm_mask, nr);
136 }
137
138 static BLOCKING_NOTIFIER_HEAD(spu_switch_notifier);
139
140 static void spu_switch_notify(struct spu *spu, struct spu_context *ctx)
141 {
142         blocking_notifier_call_chain(&spu_switch_notifier,
143                             ctx ? ctx->object_id : 0, spu);
144 }
145
146 int spu_switch_event_register(struct notifier_block * n)
147 {
148         return blocking_notifier_chain_register(&spu_switch_notifier, n);
149 }
150
151 int spu_switch_event_unregister(struct notifier_block * n)
152 {
153         return blocking_notifier_chain_unregister(&spu_switch_notifier, n);
154 }
155
156 /**
157  * spu_bind_context - bind spu context to physical spu
158  * @spu:        physical spu to bind to
159  * @ctx:        context to bind
160  */
161 static void spu_bind_context(struct spu *spu, struct spu_context *ctx)
162 {
163         pr_debug("%s: pid=%d SPU=%d NODE=%d\n", __FUNCTION__, current->pid,
164                  spu->number, spu->node);
165         spu->ctx = ctx;
166         spu->flags = 0;
167         ctx->spu = spu;
168         ctx->ops = &spu_hw_ops;
169         spu->pid = current->pid;
170         spu->mm = ctx->owner;
171         mm_needs_global_tlbie(spu->mm);
172         spu->ibox_callback = spufs_ibox_callback;
173         spu->wbox_callback = spufs_wbox_callback;
174         spu->stop_callback = spufs_stop_callback;
175         spu->mfc_callback = spufs_mfc_callback;
176         spu->dma_callback = spufs_dma_callback;
177         mb();
178         spu_unmap_mappings(ctx);
179         spu_restore(&ctx->csa, spu);
180         spu->timestamp = jiffies;
181         spu_cpu_affinity_set(spu, raw_smp_processor_id());
182         spu_switch_notify(spu, ctx);
183         spu_add_to_active_list(spu);
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_remove_from_active_list(spu);
198         spu_switch_notify(spu, NULL);
199         spu_unmap_mappings(ctx);
200         spu_save(&ctx->csa, spu);
201         spu->timestamp = jiffies;
202         ctx->state = SPU_STATE_SAVED;
203         spu->ibox_callback = NULL;
204         spu->wbox_callback = NULL;
205         spu->stop_callback = NULL;
206         spu->mfc_callback = NULL;
207         spu->dma_callback = NULL;
208         spu->mm = NULL;
209         spu->pid = 0;
210         ctx->ops = &spu_backing_ops;
211         ctx->spu = NULL;
212         spu->flags = 0;
213         spu->ctx = NULL;
214 }
215
216 /**
217  * spu_add_to_rq - add a context to the runqueue
218  * @ctx:       context to add
219  */
220 static void spu_add_to_rq(struct spu_context *ctx)
221 {
222         spin_lock(&spu_prio->runq_lock);
223         list_add_tail(&ctx->rq, &spu_prio->runq[ctx->prio]);
224         set_bit(ctx->prio, spu_prio->bitmap);
225         spin_unlock(&spu_prio->runq_lock);
226 }
227
228 /**
229  * spu_del_from_rq - remove a context from the runqueue
230  * @ctx:       context to remove
231  */
232 static void spu_del_from_rq(struct spu_context *ctx)
233 {
234         spin_lock(&spu_prio->runq_lock);
235         list_del_init(&ctx->rq);
236         if (list_empty(&spu_prio->runq[ctx->prio]))
237                 clear_bit(ctx->prio, spu_prio->bitmap);
238         spin_unlock(&spu_prio->runq_lock);
239 }
240
241 /**
242  * spu_grab_context - remove one context from the runqueue
243  * @prio:      priority of the context to be removed
244  *
245  * This function removes one context from the runqueue for priority @prio.
246  * If there is more than one context with the given priority the first
247  * task on the runqueue will be taken.
248  *
249  * Returns the spu_context it just removed.
250  *
251  * Must be called with spu_prio->runq_lock held.
252  */
253 static struct spu_context *spu_grab_context(int prio)
254 {
255         struct list_head *rq = &spu_prio->runq[prio];
256
257         if (list_empty(rq))
258                 return NULL;
259         return list_entry(rq->next, struct spu_context, rq);
260 }
261
262 static void spu_prio_wait(struct spu_context *ctx)
263 {
264         DEFINE_WAIT(wait);
265
266         set_bit(SPU_SCHED_WAKE, &ctx->sched_flags);
267         prepare_to_wait_exclusive(&ctx->stop_wq, &wait, TASK_INTERRUPTIBLE);
268         if (!signal_pending(current)) {
269                 mutex_unlock(&ctx->state_mutex);
270                 schedule();
271                 mutex_lock(&ctx->state_mutex);
272         }
273         __set_current_state(TASK_RUNNING);
274         remove_wait_queue(&ctx->stop_wq, &wait);
275         clear_bit(SPU_SCHED_WAKE, &ctx->sched_flags);
276 }
277
278 /**
279  * spu_reschedule - try to find a runnable context for a spu
280  * @spu:       spu available
281  *
282  * This function is called whenever a spu becomes idle.  It looks for the
283  * most suitable runnable spu context and schedules it for execution.
284  */
285 static void spu_reschedule(struct spu *spu)
286 {
287         int best;
288
289         spu_free(spu);
290
291         spin_lock(&spu_prio->runq_lock);
292         best = sched_find_first_bit(spu_prio->bitmap);
293         if (best < MAX_PRIO) {
294                 struct spu_context *ctx = spu_grab_context(best);
295                 if (ctx && test_bit(SPU_SCHED_WAKE, &ctx->sched_flags))
296                         wake_up(&ctx->stop_wq);
297         }
298         spin_unlock(&spu_prio->runq_lock);
299 }
300
301 static struct spu *spu_get_idle(struct spu_context *ctx)
302 {
303         struct spu *spu = NULL;
304         int node = cpu_to_node(raw_smp_processor_id());
305         int n;
306
307         for (n = 0; n < MAX_NUMNODES; n++, node++) {
308                 node = (node < MAX_NUMNODES) ? node : 0;
309                 if (!node_allowed(node))
310                         continue;
311                 spu = spu_alloc_node(node);
312                 if (spu)
313                         break;
314         }
315         return spu;
316 }
317
318 /**
319  * find_victim - find a lower priority context to preempt
320  * @ctx:        canidate context for running
321  *
322  * Returns the freed physical spu to run the new context on.
323  */
324 static struct spu *find_victim(struct spu_context *ctx)
325 {
326         struct spu_context *victim = NULL;
327         struct spu *spu;
328         int node, n;
329
330         /*
331          * Look for a possible preemption candidate on the local node first.
332          * If there is no candidate look at the other nodes.  This isn't
333          * exactly fair, but so far the whole spu schedule tries to keep
334          * a strong node affinity.  We might want to fine-tune this in
335          * the future.
336          */
337  restart:
338         node = cpu_to_node(raw_smp_processor_id());
339         for (n = 0; n < MAX_NUMNODES; n++, node++) {
340                 node = (node < MAX_NUMNODES) ? node : 0;
341                 if (!node_allowed(node))
342                         continue;
343
344                 mutex_lock(&spu_prio->active_mutex[node]);
345                 list_for_each_entry(spu, &spu_prio->active_list[node], list) {
346                         struct spu_context *tmp = spu->ctx;
347
348                         if (tmp->rt_priority < ctx->rt_priority &&
349                             (!victim || tmp->rt_priority < victim->rt_priority))
350                                 victim = spu->ctx;
351                 }
352                 mutex_unlock(&spu_prio->active_mutex[node]);
353
354                 if (victim) {
355                         /*
356                          * This nests ctx->state_mutex, but we always lock
357                          * higher priority contexts before lower priority
358                          * ones, so this is safe until we introduce
359                          * priority inheritance schemes.
360                          */
361                         if (!mutex_trylock(&victim->state_mutex)) {
362                                 victim = NULL;
363                                 goto restart;
364                         }
365
366                         spu = victim->spu;
367                         if (!spu) {
368                                 /*
369                                  * This race can happen because we've dropped
370                                  * the active list mutex.  No a problem, just
371                                  * restart the search.
372                                  */
373                                 mutex_unlock(&victim->state_mutex);
374                                 victim = NULL;
375                                 goto restart;
376                         }
377                         spu_unbind_context(spu, victim);
378                         mutex_unlock(&victim->state_mutex);
379                         return spu;
380                 }
381         }
382
383         return NULL;
384 }
385
386 /**
387  * spu_activate - find a free spu for a context and execute it
388  * @ctx:        spu context to schedule
389  * @flags:      flags (currently ignored)
390  *
391  * Tries to find a free spu to run @ctx.  If no free spu is availble
392  * add the context to the runqueue so it gets woken up once an spu
393  * is available.
394  */
395 int spu_activate(struct spu_context *ctx, unsigned long flags)
396 {
397
398         if (ctx->spu)
399                 return 0;
400
401         do {
402                 struct spu *spu;
403
404                 spu = spu_get_idle(ctx);
405                 /*
406                  * If this is a realtime thread we try to get it running by
407                  * preempting a lower priority thread.
408                  */
409                 if (!spu && ctx->rt_priority)
410                         spu = find_victim(ctx);
411                 if (spu) {
412                         spu_bind_context(spu, ctx);
413                         return 0;
414                 }
415
416                 spu_add_to_rq(ctx);
417                 if (!(flags & SPU_ACTIVATE_NOWAKE))
418                         spu_prio_wait(ctx);
419                 spu_del_from_rq(ctx);
420         } while (!signal_pending(current));
421
422         return -ERESTARTSYS;
423 }
424
425 /**
426  * spu_deactivate - unbind a context from it's physical spu
427  * @ctx:        spu context to unbind
428  *
429  * Unbind @ctx from the physical spu it is running on and schedule
430  * the highest priority context to run on the freed physical spu.
431  */
432 void spu_deactivate(struct spu_context *ctx)
433 {
434         struct spu *spu = ctx->spu;
435
436         if (spu) {
437                 spu_unbind_context(spu, ctx);
438                 spu_reschedule(spu);
439         }
440 }
441
442 /**
443  * spu_yield -  yield a physical spu if others are waiting
444  * @ctx:        spu context to yield
445  *
446  * Check if there is a higher priority context waiting and if yes
447  * unbind @ctx from the physical spu and schedule the highest
448  * priority context to run on the freed physical spu instead.
449  */
450 void spu_yield(struct spu_context *ctx)
451 {
452         struct spu *spu;
453         int need_yield = 0;
454
455         if (mutex_trylock(&ctx->state_mutex)) {
456                 if ((spu = ctx->spu) != NULL) {
457                         int best = sched_find_first_bit(spu_prio->bitmap);
458                         if (best < MAX_PRIO) {
459                                 pr_debug("%s: yielding SPU %d NODE %d\n",
460                                          __FUNCTION__, spu->number, spu->node);
461                                 spu_deactivate(ctx);
462                                 need_yield = 1;
463                         }
464                 }
465                 mutex_unlock(&ctx->state_mutex);
466         }
467         if (unlikely(need_yield))
468                 yield();
469 }
470
471 int __init spu_sched_init(void)
472 {
473         int i;
474
475         spu_sched_wq = create_singlethread_workqueue("spusched");
476         if (!spu_sched_wq)
477                 return 1;
478
479         spu_prio = kzalloc(sizeof(struct spu_prio_array), GFP_KERNEL);
480         if (!spu_prio) {
481                 printk(KERN_WARNING "%s: Unable to allocate priority queue.\n",
482                        __FUNCTION__);
483                        destroy_workqueue(spu_sched_wq);
484                 return 1;
485         }
486         for (i = 0; i < MAX_PRIO; i++) {
487                 INIT_LIST_HEAD(&spu_prio->runq[i]);
488                 __clear_bit(i, spu_prio->bitmap);
489         }
490         __set_bit(MAX_PRIO, spu_prio->bitmap);
491         for (i = 0; i < MAX_NUMNODES; i++) {
492                 mutex_init(&spu_prio->active_mutex[i]);
493                 INIT_LIST_HEAD(&spu_prio->active_list[i]);
494         }
495         spin_lock_init(&spu_prio->runq_lock);
496         return 0;
497 }
498
499 void __exit spu_sched_exit(void)
500 {
501         struct spu *spu, *tmp;
502         int node;
503
504         for (node = 0; node < MAX_NUMNODES; node++) {
505                 mutex_lock(&spu_prio->active_mutex[node]);
506                 list_for_each_entry_safe(spu, tmp, &spu_prio->active_list[node],
507                                          list) {
508                         list_del_init(&spu->list);
509                         spu_free(spu);
510                 }
511                 mutex_unlock(&spu_prio->active_mutex[node]);
512         }
513         kfree(spu_prio);
514         destroy_workqueue(spu_sched_wq);
515 }