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