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  * SPU scheduler, based on Linux thread priority.  For now use
   7  * a simple "cooperative" yield model with no preemption.  SPU
   8  * scheduling will eventually be preemptive: When a thread with
   9  * a higher static priority gets ready to run, then an active SPU
  10  * context will be preempted and returned to the waitq.
  11  *
  12  * This program is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU General Public License as published by
  14  * the Free Software Foundation; either version 2, or (at your option)
  15  * any later version.
  16  *
  17  * This program is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  20  * GNU General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU General Public License
  23  * along with this program; if not, write to the Free Software
  24  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  25  */
  26
  27 #undef DEBUG
  28
  29 #include <linux/config.h>
  30 #include <linux/module.h>
  31 #include <linux/errno.h>
  32 #include <linux/sched.h>
  33 #include <linux/kernel.h>
  34 #include <linux/mm.h>
  35 #include <linux/completion.h>
  36 #include <linux/vmalloc.h>
  37 #include <linux/smp.h>
  38 #include <linux/smp_lock.h>
  39 #include <linux/stddef.h>
  40 #include <linux/unistd.h>
  41
  42 #include <asm/io.h>
  43 #include <asm/mmu_context.h>
  44 #include <asm/spu.h>
  45 #include <asm/spu_csa.h>
  46 #include "spufs.h"
  47
  48 #define SPU_BITMAP_SIZE (((MAX_PRIO+BITS_PER_LONG)/BITS_PER_LONG)+1)
  49 struct spu_prio_array {
  50         atomic_t nr_blocked;
  51         unsigned long bitmap[SPU_BITMAP_SIZE];
  52         wait_queue_head_t waitq[MAX_PRIO];
  53 };
  54
  55 /* spu_runqueue - This is the main runqueue data structure for SPUs. */
  56 struct spu_runqueue {
  57         struct semaphore sem;
  58         unsigned long nr_active;
  59         unsigned long nr_idle;
  60         unsigned long nr_switches;
  61         struct list_head active_list;
  62         struct list_head idle_list;
  63         struct spu_prio_array prio;
  64 };
  65
  66 static struct spu_runqueue *spu_runqueues = NULL;
  67
  68 static inline struct spu_runqueue *spu_rq(void)
  69 {
  70         /* Future: make this a per-NODE array,
  71          * and use cpu_to_node(smp_processor_id())
  72          */
  73         return spu_runqueues;
  74 }
  75
  76 static inline struct spu *del_idle(struct spu_runqueue *rq)
  77 {
  78         struct spu *spu;
  79
  80         BUG_ON(rq->nr_idle <= 0);
  81         BUG_ON(list_empty(&rq->idle_list));
  82         /* Future: Move SPU out of low-power SRI state. */
  83         spu = list_entry(rq->idle_list.next, struct spu, sched_list);
  84         list_del_init(&spu->sched_list);
  85         rq->nr_idle--;
  86         return spu;
  87 }
  88
  89 static inline void del_active(struct spu_runqueue *rq, struct spu *spu)
  90 {
  91         BUG_ON(rq->nr_active <= 0);
  92         BUG_ON(list_empty(&rq->active_list));
  93         list_del_init(&spu->sched_list);
  94         rq->nr_active--;
  95 }
  96
  97 static inline void add_idle(struct spu_runqueue *rq, struct spu *spu)
  98 {
  99         /* Future: Put SPU into low-power SRI state. */
 100         list_add_tail(&spu->sched_list, &rq->idle_list);
 101         rq->nr_idle++;
 102 }
 103
 104 static inline void add_active(struct spu_runqueue *rq, struct spu *spu)
 105 {
 106         rq->nr_active++;
 107         rq->nr_switches++;
 108         list_add_tail(&spu->sched_list, &rq->active_list);
 109 }
 110
 111 static void prio_wakeup(struct spu_runqueue *rq)
 112 {
 113         if (atomic_read(&rq->prio.nr_blocked) && rq->nr_idle) {
 114                 int best = sched_find_first_bit(rq->prio.bitmap);
 115                 if (best < MAX_PRIO) {
 116                         wait_queue_head_t *wq = &rq->prio.waitq[best];
 117                         wake_up_interruptible_nr(wq, 1);
 118                 }
 119         }
 120 }
 121
 122 static void prio_wait(struct spu_runqueue *rq, struct spu_context *ctx,
 123                       u64 flags)
 124 {
 125         int prio = current->prio;
 126         wait_queue_head_t *wq = &rq->prio.waitq[prio];
 127         DEFINE_WAIT(wait);
 128
 129         __set_bit(prio, rq->prio.bitmap);
 130         atomic_inc(&rq->prio.nr_blocked);
 131         prepare_to_wait_exclusive(wq, &wait, TASK_INTERRUPTIBLE);
 132         if (!signal_pending(current)) {
 133                 up(&rq->sem);
 134                 up_write(&ctx->state_sema);
 135                 pr_debug("%s: pid=%d prio=%d\n", __FUNCTION__,
 136                          current->pid, current->prio);
 137                 schedule();
 138                 down_write(&ctx->state_sema);
 139                 down(&rq->sem);
 140         }
 141         finish_wait(wq, &wait);
 142         atomic_dec(&rq->prio.nr_blocked);
 143         if (!waitqueue_active(wq))
 144                 __clear_bit(prio, rq->prio.bitmap);
 145 }
 146
 147 static inline int is_best_prio(struct spu_runqueue *rq)
 148 {
 149         int best_prio;
 150
 151         best_prio = sched_find_first_bit(rq->prio.bitmap);
 152         return (current->prio < best_prio) ? 1 : 0;
 153 }
 154
 155 static inline void mm_needs_global_tlbie(struct mm_struct *mm)
 156 {
 157         /* Global TLBIE broadcast required with SPEs. */
 158 #if (NR_CPUS > 1)
 159         __cpus_setall(&mm->cpu_vm_mask, NR_CPUS);
 160 #else
 161         __cpus_setall(&mm->cpu_vm_mask, NR_CPUS+1); /* is this ok? */
 162 #endif
 163 }
 164
 165 static inline void bind_context(struct spu *spu, struct spu_context *ctx)
 166 {
 167         pr_debug("%s: pid=%d SPU=%d\n", __FUNCTION__, current->pid,
 168                  spu->number);
 169         spu->ctx = ctx;
 170         spu->flags = 0;
 171         ctx->spu = spu;
 172         ctx->ops = &spu_hw_ops;
 173         spu->pid = current->pid;
 174         spu->prio = current->prio;
 175         spu->mm = ctx->owner;
 176         mm_needs_global_tlbie(spu->mm);
 177         spu->ibox_callback = spufs_ibox_callback;
 178         spu->wbox_callback = spufs_wbox_callback;
 179         spu->stop_callback = spufs_stop_callback;
 180         mb();
 181         spu_unmap_mappings(ctx);
 182         spu_restore(&ctx->csa, spu);
 183 }
 184
 185 static inline void unbind_context(struct spu *spu, struct spu_context *ctx)
 186 {
 187         pr_debug("%s: unbind pid=%d SPU=%d\n", __FUNCTION__,
 188                  spu->pid, spu->number);
 189         spu_unmap_mappings(ctx);
 190         spu_save(&ctx->csa, spu);
 191         ctx->state = SPU_STATE_SAVED;
 192         spu->ibox_callback = NULL;
 193         spu->wbox_callback = NULL;
 194         spu->stop_callback = NULL;
 195         spu->mm = NULL;
 196         spu->pid = 0;
 197         spu->prio = MAX_PRIO;
 198         ctx->ops = &spu_backing_ops;
 199         ctx->spu = NULL;
 200         spu->ctx = NULL;
 201 }
 202
 203 static struct spu *preempt_active(struct spu_runqueue *rq)
 204 {
 205         struct list_head *p;
 206         struct spu *worst, *spu;
 207
 208         worst = list_entry(rq->active_list.next, struct spu, sched_list);
 209         list_for_each(p, &rq->active_list) {
 210                 spu = list_entry(p, struct spu, sched_list);
 211                 if (spu->prio > worst->prio) {
 212                         worst = spu;
 213                 }
 214         }
 215         if (current->prio < worst->prio) {
 216                 struct spu_context *ctx = worst->ctx;
 217
 218                 spu = worst;
 219                 if (down_write_trylock(&ctx->state_sema)) {
 220                         pr_debug("%s: booting pid=%d from SPU %d\n",
 221                                  __FUNCTION__, spu->pid, spu->number);
 222                         del_active(rq, spu);
 223                         up(&rq->sem);
 224                         wake_up_all(&ctx->stop_wq);
 225                         ctx->ops->runcntl_stop(ctx);
 226                         unbind_context(spu, ctx);
 227                         up_write(&ctx->state_sema);
 228                         return spu;
 229                 }
 230         }
 231         return NULL;
 232 }
 233
 234 static struct spu *get_idle_spu(struct spu_context *ctx, u64 flags)
 235 {
 236         struct spu_runqueue *rq;
 237         struct spu *spu = NULL;
 238
 239         rq = spu_rq();
 240         down(&rq->sem);
 241         for (;;) {
 242                 if (rq->nr_idle > 0) {
 243                         if (is_best_prio(rq)) {
 244                                 /* Fall through. */
 245                                 spu = del_idle(rq);
 246                                 break;
 247                         } else {
 248                                 prio_wakeup(rq);
 249                                 up(&rq->sem);
 250                                 yield();
 251                                 if (signal_pending(current)) {
 252                                         return NULL;
 253                                 }
 254                                 rq = spu_rq();
 255                                 down(&rq->sem);
 256                                 continue;
 257                         }
 258                 } else {
 259                         if (is_best_prio(rq)) {
 260                                 if ((spu = preempt_active(rq)) != NULL)
 261                                         return spu;
 262                         }
 263                         prio_wait(rq, ctx, flags);
 264                         if (signal_pending(current)) {
 265                                 prio_wakeup(rq);
 266                                 spu = NULL;
 267                                 break;
 268                         }
 269                         continue;
 270                 }
 271         }
 272         up(&rq->sem);
 273         return spu;
 274 }
 275
 276 static void put_idle_spu(struct spu *spu)
 277 {
 278         struct spu_runqueue *rq = spu->rq;
 279
 280         down(&rq->sem);
 281         add_idle(rq, spu);
 282         prio_wakeup(rq);
 283         up(&rq->sem);
 284 }
 285
 286 static int get_active_spu(struct spu *spu)
 287 {
 288         struct spu_runqueue *rq = spu->rq;
 289         struct list_head *p;
 290         struct spu *tmp;
 291         int rc = 0;
 292
 293         down(&rq->sem);
 294         list_for_each(p, &rq->active_list) {
 295                 tmp = list_entry(p, struct spu, sched_list);
 296                 if (tmp == spu) {
 297                         del_active(rq, spu);
 298                         rc = 1;
 299                         break;
 300                 }
 301         }
 302         up(&rq->sem);
 303         return rc;
 304 }
 305
 306 static void put_active_spu(struct spu *spu)
 307 {
 308         struct spu_runqueue *rq = spu->rq;
 309
 310         down(&rq->sem);
 311         add_active(rq, spu);
 312         up(&rq->sem);
 313 }
 314
 315 /* Lock order:
 316  *      spu_activate() & spu_deactivate() require the
 317  *      caller to have down_write(&ctx->state_sema).
 318  *
 319  *      The rq->sem is breifly held (inside or outside a
 320  *      given ctx lock) for list management, but is never
 321  *      held during save/restore.
 322  */
 323
 324 int spu_activate(struct spu_context *ctx, u64 flags)
 325 {
 326         struct spu *spu;
 327
 328         if (ctx->spu)
 329                 return 0;
 330         spu = get_idle_spu(ctx, flags);
 331         if (!spu)
 332                 return (signal_pending(current)) ? -ERESTARTSYS : -EAGAIN;
 333         bind_context(spu, ctx);
 334         put_active_spu(spu);
 335         return 0;
 336 }
 337
 338 void spu_deactivate(struct spu_context *ctx)
 339 {
 340         struct spu *spu;
 341         int needs_idle;
 342
 343         spu = ctx->spu;
 344         if (!spu)
 345                 return;
 346         needs_idle = get_active_spu(spu);
 347         unbind_context(spu, ctx);
 348         if (needs_idle)
 349                 put_idle_spu(spu);
 350 }
 351
 352 void spu_yield(struct spu_context *ctx)
 353 {
 354         struct spu *spu;
 355         int need_yield = 0;
 356
 357         down_write(&ctx->state_sema);
 358         spu = ctx->spu;
 359         if (spu && (sched_find_first_bit(spu->rq->prio.bitmap) < MAX_PRIO)) {
 360                 pr_debug("%s: yielding SPU %d\n", __FUNCTION__, spu->number);
 361                 spu_deactivate(ctx);
 362                 ctx->state = SPU_STATE_SAVED;
 363                 need_yield = 1;
 364         }
 365         up_write(&ctx->state_sema);
 366         if (unlikely(need_yield))
 367                 yield();
 368 }
 369
 370 int __init spu_sched_init(void)
 371 {
 372         struct spu_runqueue *rq;
 373         struct spu *spu;
 374         int i;
 375
 376         rq = spu_runqueues = kmalloc(sizeof(struct spu_runqueue), GFP_KERNEL);
 377         if (!rq) {
 378                 printk(KERN_WARNING "%s: Unable to allocate runqueues.\n",
 379                        __FUNCTION__);
 380                 return 1;
 381         }
 382         memset(rq, 0, sizeof(struct spu_runqueue));
 383         init_MUTEX(&rq->sem);
 384         INIT_LIST_HEAD(&rq->active_list);
 385         INIT_LIST_HEAD(&rq->idle_list);
 386         rq->nr_active = 0;
 387         rq->nr_idle = 0;
 388         rq->nr_switches = 0;
 389         atomic_set(&rq->prio.nr_blocked, 0);
 390         for (i = 0; i < MAX_PRIO; i++) {
 391                 init_waitqueue_head(&rq->prio.waitq[i]);
 392                 __clear_bit(i, rq->prio.bitmap);
 393         }
 394         __set_bit(MAX_PRIO, rq->prio.bitmap);
 395         for (;;) {
 396                 spu = spu_alloc();
 397                 if (!spu)
 398                         break;
 399                 pr_debug("%s: adding SPU[%d]\n", __FUNCTION__, spu->number);
 400                 add_idle(rq, spu);
 401                 spu->rq = rq;
 402         }
 403         if (!rq->nr_idle) {
 404                 printk(KERN_WARNING "%s: No available SPUs.\n", __FUNCTION__);
 405                 kfree(rq);
 406                 return 1;
 407         }
 408         return 0;
 409 }
 410
 411 void __exit spu_sched_exit(void)
 412 {
 413         struct spu_runqueue *rq = spu_rq();
 414         struct spu *spu;
 415
 416         if (!rq) {
 417                 printk(KERN_WARNING "%s: no runqueues!\n", __FUNCTION__);
 418                 return;
 419         }
 420         while (rq->nr_idle > 0) {
 421                 spu = del_idle(rq);
 422                 if (!spu)
 423                         break;
 424                 spu_free(spu);
 425         }
 426         kfree(rq);
 427 }