sched: sched_rt_entity
[linux-2.6.git] / kernel / sched_rt.c
1 /*
2  * Real-Time Scheduling Class (mapped to the SCHED_FIFO and SCHED_RR
3  * policies)
4  */
5
6 #ifdef CONFIG_SMP
7
8 static inline int rt_overloaded(struct rq *rq)
9 {
10         return atomic_read(&rq->rd->rto_count);
11 }
12
13 static inline void rt_set_overload(struct rq *rq)
14 {
15         cpu_set(rq->cpu, rq->rd->rto_mask);
16         /*
17          * Make sure the mask is visible before we set
18          * the overload count. That is checked to determine
19          * if we should look at the mask. It would be a shame
20          * if we looked at the mask, but the mask was not
21          * updated yet.
22          */
23         wmb();
24         atomic_inc(&rq->rd->rto_count);
25 }
26
27 static inline void rt_clear_overload(struct rq *rq)
28 {
29         /* the order here really doesn't matter */
30         atomic_dec(&rq->rd->rto_count);
31         cpu_clear(rq->cpu, rq->rd->rto_mask);
32 }
33
34 static void update_rt_migration(struct rq *rq)
35 {
36         if (rq->rt.rt_nr_migratory && (rq->rt.rt_nr_running > 1)) {
37                 if (!rq->rt.overloaded) {
38                         rt_set_overload(rq);
39                         rq->rt.overloaded = 1;
40                 }
41         } else if (rq->rt.overloaded) {
42                 rt_clear_overload(rq);
43                 rq->rt.overloaded = 0;
44         }
45 }
46 #endif /* CONFIG_SMP */
47
48 /*
49  * Update the current task's runtime statistics. Skip current tasks that
50  * are not in our scheduling class.
51  */
52 static void update_curr_rt(struct rq *rq)
53 {
54         struct task_struct *curr = rq->curr;
55         u64 delta_exec;
56
57         if (!task_has_rt_policy(curr))
58                 return;
59
60         delta_exec = rq->clock - curr->se.exec_start;
61         if (unlikely((s64)delta_exec < 0))
62                 delta_exec = 0;
63
64         schedstat_set(curr->se.exec_max, max(curr->se.exec_max, delta_exec));
65
66         curr->se.sum_exec_runtime += delta_exec;
67         curr->se.exec_start = rq->clock;
68         cpuacct_charge(curr, delta_exec);
69 }
70
71 static inline void inc_rt_tasks(struct task_struct *p, struct rq *rq)
72 {
73         WARN_ON(!rt_task(p));
74         rq->rt.rt_nr_running++;
75 #ifdef CONFIG_SMP
76         if (p->prio < rq->rt.highest_prio)
77                 rq->rt.highest_prio = p->prio;
78         if (p->nr_cpus_allowed > 1)
79                 rq->rt.rt_nr_migratory++;
80
81         update_rt_migration(rq);
82 #endif /* CONFIG_SMP */
83 }
84
85 static inline void dec_rt_tasks(struct task_struct *p, struct rq *rq)
86 {
87         WARN_ON(!rt_task(p));
88         WARN_ON(!rq->rt.rt_nr_running);
89         rq->rt.rt_nr_running--;
90 #ifdef CONFIG_SMP
91         if (rq->rt.rt_nr_running) {
92                 struct rt_prio_array *array;
93
94                 WARN_ON(p->prio < rq->rt.highest_prio);
95                 if (p->prio == rq->rt.highest_prio) {
96                         /* recalculate */
97                         array = &rq->rt.active;
98                         rq->rt.highest_prio =
99                                 sched_find_first_bit(array->bitmap);
100                 } /* otherwise leave rq->highest prio alone */
101         } else
102                 rq->rt.highest_prio = MAX_RT_PRIO;
103         if (p->nr_cpus_allowed > 1)
104                 rq->rt.rt_nr_migratory--;
105
106         update_rt_migration(rq);
107 #endif /* CONFIG_SMP */
108 }
109
110 static void enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup)
111 {
112         struct rt_prio_array *array = &rq->rt.active;
113
114         list_add_tail(&p->rt.run_list, array->queue + p->prio);
115         __set_bit(p->prio, array->bitmap);
116         inc_cpu_load(rq, p->se.load.weight);
117
118         inc_rt_tasks(p, rq);
119 }
120
121 /*
122  * Adding/removing a task to/from a priority array:
123  */
124 static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int sleep)
125 {
126         struct rt_prio_array *array = &rq->rt.active;
127
128         update_curr_rt(rq);
129
130         list_del(&p->rt.run_list);
131         if (list_empty(array->queue + p->prio))
132                 __clear_bit(p->prio, array->bitmap);
133         dec_cpu_load(rq, p->se.load.weight);
134
135         dec_rt_tasks(p, rq);
136 }
137
138 /*
139  * Put task to the end of the run list without the overhead of dequeue
140  * followed by enqueue.
141  */
142 static void requeue_task_rt(struct rq *rq, struct task_struct *p)
143 {
144         struct rt_prio_array *array = &rq->rt.active;
145
146         list_move_tail(&p->rt.run_list, array->queue + p->prio);
147 }
148
149 static void
150 yield_task_rt(struct rq *rq)
151 {
152         requeue_task_rt(rq, rq->curr);
153 }
154
155 #ifdef CONFIG_SMP
156 static int find_lowest_rq(struct task_struct *task);
157
158 static int select_task_rq_rt(struct task_struct *p, int sync)
159 {
160         struct rq *rq = task_rq(p);
161
162         /*
163          * If the current task is an RT task, then
164          * try to see if we can wake this RT task up on another
165          * runqueue. Otherwise simply start this RT task
166          * on its current runqueue.
167          *
168          * We want to avoid overloading runqueues. Even if
169          * the RT task is of higher priority than the current RT task.
170          * RT tasks behave differently than other tasks. If
171          * one gets preempted, we try to push it off to another queue.
172          * So trying to keep a preempting RT task on the same
173          * cache hot CPU will force the running RT task to
174          * a cold CPU. So we waste all the cache for the lower
175          * RT task in hopes of saving some of a RT task
176          * that is just being woken and probably will have
177          * cold cache anyway.
178          */
179         if (unlikely(rt_task(rq->curr)) &&
180             (p->nr_cpus_allowed > 1)) {
181                 int cpu = find_lowest_rq(p);
182
183                 return (cpu == -1) ? task_cpu(p) : cpu;
184         }
185
186         /*
187          * Otherwise, just let it ride on the affined RQ and the
188          * post-schedule router will push the preempted task away
189          */
190         return task_cpu(p);
191 }
192 #endif /* CONFIG_SMP */
193
194 /*
195  * Preempt the current task with a newly woken task if needed:
196  */
197 static void check_preempt_curr_rt(struct rq *rq, struct task_struct *p)
198 {
199         if (p->prio < rq->curr->prio)
200                 resched_task(rq->curr);
201 }
202
203 static struct task_struct *pick_next_task_rt(struct rq *rq)
204 {
205         struct rt_prio_array *array = &rq->rt.active;
206         struct task_struct *next;
207         struct list_head *queue;
208         int idx;
209
210         idx = sched_find_first_bit(array->bitmap);
211         if (idx >= MAX_RT_PRIO)
212                 return NULL;
213
214         queue = array->queue + idx;
215         next = list_entry(queue->next, struct task_struct, rt.run_list);
216
217         next->se.exec_start = rq->clock;
218
219         return next;
220 }
221
222 static void put_prev_task_rt(struct rq *rq, struct task_struct *p)
223 {
224         update_curr_rt(rq);
225         p->se.exec_start = 0;
226 }
227
228 #ifdef CONFIG_SMP
229 /* Only try algorithms three times */
230 #define RT_MAX_TRIES 3
231
232 static int double_lock_balance(struct rq *this_rq, struct rq *busiest);
233 static void deactivate_task(struct rq *rq, struct task_struct *p, int sleep);
234
235 static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu)
236 {
237         if (!task_running(rq, p) &&
238             (cpu < 0 || cpu_isset(cpu, p->cpus_allowed)) &&
239             (p->nr_cpus_allowed > 1))
240                 return 1;
241         return 0;
242 }
243
244 /* Return the second highest RT task, NULL otherwise */
245 static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu)
246 {
247         struct rt_prio_array *array = &rq->rt.active;
248         struct task_struct *next;
249         struct list_head *queue;
250         int idx;
251
252         if (likely(rq->rt.rt_nr_running < 2))
253                 return NULL;
254
255         idx = sched_find_first_bit(array->bitmap);
256         if (unlikely(idx >= MAX_RT_PRIO)) {
257                 WARN_ON(1); /* rt_nr_running is bad */
258                 return NULL;
259         }
260
261         queue = array->queue + idx;
262         BUG_ON(list_empty(queue));
263
264         next = list_entry(queue->next, struct task_struct, rt.run_list);
265         if (unlikely(pick_rt_task(rq, next, cpu)))
266                 goto out;
267
268         if (queue->next->next != queue) {
269                 /* same prio task */
270                 next = list_entry(queue->next->next, struct task_struct,
271                                   rt.run_list);
272                 if (pick_rt_task(rq, next, cpu))
273                         goto out;
274         }
275
276  retry:
277         /* slower, but more flexible */
278         idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1);
279         if (unlikely(idx >= MAX_RT_PRIO))
280                 return NULL;
281
282         queue = array->queue + idx;
283         BUG_ON(list_empty(queue));
284
285         list_for_each_entry(next, queue, rt.run_list) {
286                 if (pick_rt_task(rq, next, cpu))
287                         goto out;
288         }
289
290         goto retry;
291
292  out:
293         return next;
294 }
295
296 static DEFINE_PER_CPU(cpumask_t, local_cpu_mask);
297
298 static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask)
299 {
300         int       lowest_prio = -1;
301         int       lowest_cpu  = -1;
302         int       count       = 0;
303         int       cpu;
304
305         cpus_and(*lowest_mask, task_rq(task)->rd->online, task->cpus_allowed);
306
307         /*
308          * Scan each rq for the lowest prio.
309          */
310         for_each_cpu_mask(cpu, *lowest_mask) {
311                 struct rq *rq = cpu_rq(cpu);
312
313                 /* We look for lowest RT prio or non-rt CPU */
314                 if (rq->rt.highest_prio >= MAX_RT_PRIO) {
315                         /*
316                          * if we already found a low RT queue
317                          * and now we found this non-rt queue
318                          * clear the mask and set our bit.
319                          * Otherwise just return the queue as is
320                          * and the count==1 will cause the algorithm
321                          * to use the first bit found.
322                          */
323                         if (lowest_cpu != -1) {
324                                 cpus_clear(*lowest_mask);
325                                 cpu_set(rq->cpu, *lowest_mask);
326                         }
327                         return 1;
328                 }
329
330                 /* no locking for now */
331                 if ((rq->rt.highest_prio > task->prio)
332                     && (rq->rt.highest_prio >= lowest_prio)) {
333                         if (rq->rt.highest_prio > lowest_prio) {
334                                 /* new low - clear old data */
335                                 lowest_prio = rq->rt.highest_prio;
336                                 lowest_cpu = cpu;
337                                 count = 0;
338                         }
339                         count++;
340                 } else
341                         cpu_clear(cpu, *lowest_mask);
342         }
343
344         /*
345          * Clear out all the set bits that represent
346          * runqueues that were of higher prio than
347          * the lowest_prio.
348          */
349         if (lowest_cpu > 0) {
350                 /*
351                  * Perhaps we could add another cpumask op to
352                  * zero out bits. Like cpu_zero_bits(cpumask, nrbits);
353                  * Then that could be optimized to use memset and such.
354                  */
355                 for_each_cpu_mask(cpu, *lowest_mask) {
356                         if (cpu >= lowest_cpu)
357                                 break;
358                         cpu_clear(cpu, *lowest_mask);
359                 }
360         }
361
362         return count;
363 }
364
365 static inline int pick_optimal_cpu(int this_cpu, cpumask_t *mask)
366 {
367         int first;
368
369         /* "this_cpu" is cheaper to preempt than a remote processor */
370         if ((this_cpu != -1) && cpu_isset(this_cpu, *mask))
371                 return this_cpu;
372
373         first = first_cpu(*mask);
374         if (first != NR_CPUS)
375                 return first;
376
377         return -1;
378 }
379
380 static int find_lowest_rq(struct task_struct *task)
381 {
382         struct sched_domain *sd;
383         cpumask_t *lowest_mask = &__get_cpu_var(local_cpu_mask);
384         int this_cpu = smp_processor_id();
385         int cpu      = task_cpu(task);
386         int count    = find_lowest_cpus(task, lowest_mask);
387
388         if (!count)
389                 return -1; /* No targets found */
390
391         /*
392          * There is no sense in performing an optimal search if only one
393          * target is found.
394          */
395         if (count == 1)
396                 return first_cpu(*lowest_mask);
397
398         /*
399          * At this point we have built a mask of cpus representing the
400          * lowest priority tasks in the system.  Now we want to elect
401          * the best one based on our affinity and topology.
402          *
403          * We prioritize the last cpu that the task executed on since
404          * it is most likely cache-hot in that location.
405          */
406         if (cpu_isset(cpu, *lowest_mask))
407                 return cpu;
408
409         /*
410          * Otherwise, we consult the sched_domains span maps to figure
411          * out which cpu is logically closest to our hot cache data.
412          */
413         if (this_cpu == cpu)
414                 this_cpu = -1; /* Skip this_cpu opt if the same */
415
416         for_each_domain(cpu, sd) {
417                 if (sd->flags & SD_WAKE_AFFINE) {
418                         cpumask_t domain_mask;
419                         int       best_cpu;
420
421                         cpus_and(domain_mask, sd->span, *lowest_mask);
422
423                         best_cpu = pick_optimal_cpu(this_cpu,
424                                                     &domain_mask);
425                         if (best_cpu != -1)
426                                 return best_cpu;
427                 }
428         }
429
430         /*
431          * And finally, if there were no matches within the domains
432          * just give the caller *something* to work with from the compatible
433          * locations.
434          */
435         return pick_optimal_cpu(this_cpu, lowest_mask);
436 }
437
438 /* Will lock the rq it finds */
439 static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
440 {
441         struct rq *lowest_rq = NULL;
442         int tries;
443         int cpu;
444
445         for (tries = 0; tries < RT_MAX_TRIES; tries++) {
446                 cpu = find_lowest_rq(task);
447
448                 if ((cpu == -1) || (cpu == rq->cpu))
449                         break;
450
451                 lowest_rq = cpu_rq(cpu);
452
453                 /* if the prio of this runqueue changed, try again */
454                 if (double_lock_balance(rq, lowest_rq)) {
455                         /*
456                          * We had to unlock the run queue. In
457                          * the mean time, task could have
458                          * migrated already or had its affinity changed.
459                          * Also make sure that it wasn't scheduled on its rq.
460                          */
461                         if (unlikely(task_rq(task) != rq ||
462                                      !cpu_isset(lowest_rq->cpu,
463                                                 task->cpus_allowed) ||
464                                      task_running(rq, task) ||
465                                      !task->se.on_rq)) {
466
467                                 spin_unlock(&lowest_rq->lock);
468                                 lowest_rq = NULL;
469                                 break;
470                         }
471                 }
472
473                 /* If this rq is still suitable use it. */
474                 if (lowest_rq->rt.highest_prio > task->prio)
475                         break;
476
477                 /* try again */
478                 spin_unlock(&lowest_rq->lock);
479                 lowest_rq = NULL;
480         }
481
482         return lowest_rq;
483 }
484
485 /*
486  * If the current CPU has more than one RT task, see if the non
487  * running task can migrate over to a CPU that is running a task
488  * of lesser priority.
489  */
490 static int push_rt_task(struct rq *rq)
491 {
492         struct task_struct *next_task;
493         struct rq *lowest_rq;
494         int ret = 0;
495         int paranoid = RT_MAX_TRIES;
496
497         if (!rq->rt.overloaded)
498                 return 0;
499
500         next_task = pick_next_highest_task_rt(rq, -1);
501         if (!next_task)
502                 return 0;
503
504  retry:
505         if (unlikely(next_task == rq->curr)) {
506                 WARN_ON(1);
507                 return 0;
508         }
509
510         /*
511          * It's possible that the next_task slipped in of
512          * higher priority than current. If that's the case
513          * just reschedule current.
514          */
515         if (unlikely(next_task->prio < rq->curr->prio)) {
516                 resched_task(rq->curr);
517                 return 0;
518         }
519
520         /* We might release rq lock */
521         get_task_struct(next_task);
522
523         /* find_lock_lowest_rq locks the rq if found */
524         lowest_rq = find_lock_lowest_rq(next_task, rq);
525         if (!lowest_rq) {
526                 struct task_struct *task;
527                 /*
528                  * find lock_lowest_rq releases rq->lock
529                  * so it is possible that next_task has changed.
530                  * If it has, then try again.
531                  */
532                 task = pick_next_highest_task_rt(rq, -1);
533                 if (unlikely(task != next_task) && task && paranoid--) {
534                         put_task_struct(next_task);
535                         next_task = task;
536                         goto retry;
537                 }
538                 goto out;
539         }
540
541         deactivate_task(rq, next_task, 0);
542         set_task_cpu(next_task, lowest_rq->cpu);
543         activate_task(lowest_rq, next_task, 0);
544
545         resched_task(lowest_rq->curr);
546
547         spin_unlock(&lowest_rq->lock);
548
549         ret = 1;
550 out:
551         put_task_struct(next_task);
552
553         return ret;
554 }
555
556 /*
557  * TODO: Currently we just use the second highest prio task on
558  *       the queue, and stop when it can't migrate (or there's
559  *       no more RT tasks).  There may be a case where a lower
560  *       priority RT task has a different affinity than the
561  *       higher RT task. In this case the lower RT task could
562  *       possibly be able to migrate where as the higher priority
563  *       RT task could not.  We currently ignore this issue.
564  *       Enhancements are welcome!
565  */
566 static void push_rt_tasks(struct rq *rq)
567 {
568         /* push_rt_task will return true if it moved an RT */
569         while (push_rt_task(rq))
570                 ;
571 }
572
573 static int pull_rt_task(struct rq *this_rq)
574 {
575         int this_cpu = this_rq->cpu, ret = 0, cpu;
576         struct task_struct *p, *next;
577         struct rq *src_rq;
578
579         if (likely(!rt_overloaded(this_rq)))
580                 return 0;
581
582         next = pick_next_task_rt(this_rq);
583
584         for_each_cpu_mask(cpu, this_rq->rd->rto_mask) {
585                 if (this_cpu == cpu)
586                         continue;
587
588                 src_rq = cpu_rq(cpu);
589                 /*
590                  * We can potentially drop this_rq's lock in
591                  * double_lock_balance, and another CPU could
592                  * steal our next task - hence we must cause
593                  * the caller to recalculate the next task
594                  * in that case:
595                  */
596                 if (double_lock_balance(this_rq, src_rq)) {
597                         struct task_struct *old_next = next;
598
599                         next = pick_next_task_rt(this_rq);
600                         if (next != old_next)
601                                 ret = 1;
602                 }
603
604                 /*
605                  * Are there still pullable RT tasks?
606                  */
607                 if (src_rq->rt.rt_nr_running <= 1) {
608                         spin_unlock(&src_rq->lock);
609                         continue;
610                 }
611
612                 p = pick_next_highest_task_rt(src_rq, this_cpu);
613
614                 /*
615                  * Do we have an RT task that preempts
616                  * the to-be-scheduled task?
617                  */
618                 if (p && (!next || (p->prio < next->prio))) {
619                         WARN_ON(p == src_rq->curr);
620                         WARN_ON(!p->se.on_rq);
621
622                         /*
623                          * There's a chance that p is higher in priority
624                          * than what's currently running on its cpu.
625                          * This is just that p is wakeing up and hasn't
626                          * had a chance to schedule. We only pull
627                          * p if it is lower in priority than the
628                          * current task on the run queue or
629                          * this_rq next task is lower in prio than
630                          * the current task on that rq.
631                          */
632                         if (p->prio < src_rq->curr->prio ||
633                             (next && next->prio < src_rq->curr->prio))
634                                 goto out;
635
636                         ret = 1;
637
638                         deactivate_task(src_rq, p, 0);
639                         set_task_cpu(p, this_cpu);
640                         activate_task(this_rq, p, 0);
641                         /*
642                          * We continue with the search, just in
643                          * case there's an even higher prio task
644                          * in another runqueue. (low likelyhood
645                          * but possible)
646                          *
647                          * Update next so that we won't pick a task
648                          * on another cpu with a priority lower (or equal)
649                          * than the one we just picked.
650                          */
651                         next = p;
652
653                 }
654  out:
655                 spin_unlock(&src_rq->lock);
656         }
657
658         return ret;
659 }
660
661 static void pre_schedule_rt(struct rq *rq, struct task_struct *prev)
662 {
663         /* Try to pull RT tasks here if we lower this rq's prio */
664         if (unlikely(rt_task(prev)) && rq->rt.highest_prio > prev->prio)
665                 pull_rt_task(rq);
666 }
667
668 static void post_schedule_rt(struct rq *rq)
669 {
670         /*
671          * If we have more than one rt_task queued, then
672          * see if we can push the other rt_tasks off to other CPUS.
673          * Note we may release the rq lock, and since
674          * the lock was owned by prev, we need to release it
675          * first via finish_lock_switch and then reaquire it here.
676          */
677         if (unlikely(rq->rt.overloaded)) {
678                 spin_lock_irq(&rq->lock);
679                 push_rt_tasks(rq);
680                 spin_unlock_irq(&rq->lock);
681         }
682 }
683
684
685 static void task_wake_up_rt(struct rq *rq, struct task_struct *p)
686 {
687         if (!task_running(rq, p) &&
688             (p->prio >= rq->rt.highest_prio) &&
689             rq->rt.overloaded)
690                 push_rt_tasks(rq);
691 }
692
693 static unsigned long
694 load_balance_rt(struct rq *this_rq, int this_cpu, struct rq *busiest,
695                 unsigned long max_load_move,
696                 struct sched_domain *sd, enum cpu_idle_type idle,
697                 int *all_pinned, int *this_best_prio)
698 {
699         /* don't touch RT tasks */
700         return 0;
701 }
702
703 static int
704 move_one_task_rt(struct rq *this_rq, int this_cpu, struct rq *busiest,
705                  struct sched_domain *sd, enum cpu_idle_type idle)
706 {
707         /* don't touch RT tasks */
708         return 0;
709 }
710
711 static void set_cpus_allowed_rt(struct task_struct *p, cpumask_t *new_mask)
712 {
713         int weight = cpus_weight(*new_mask);
714
715         BUG_ON(!rt_task(p));
716
717         /*
718          * Update the migration status of the RQ if we have an RT task
719          * which is running AND changing its weight value.
720          */
721         if (p->se.on_rq && (weight != p->nr_cpus_allowed)) {
722                 struct rq *rq = task_rq(p);
723
724                 if ((p->nr_cpus_allowed <= 1) && (weight > 1)) {
725                         rq->rt.rt_nr_migratory++;
726                 } else if ((p->nr_cpus_allowed > 1) && (weight <= 1)) {
727                         BUG_ON(!rq->rt.rt_nr_migratory);
728                         rq->rt.rt_nr_migratory--;
729                 }
730
731                 update_rt_migration(rq);
732         }
733
734         p->cpus_allowed    = *new_mask;
735         p->nr_cpus_allowed = weight;
736 }
737
738 /* Assumes rq->lock is held */
739 static void join_domain_rt(struct rq *rq)
740 {
741         if (rq->rt.overloaded)
742                 rt_set_overload(rq);
743 }
744
745 /* Assumes rq->lock is held */
746 static void leave_domain_rt(struct rq *rq)
747 {
748         if (rq->rt.overloaded)
749                 rt_clear_overload(rq);
750 }
751
752 /*
753  * When switch from the rt queue, we bring ourselves to a position
754  * that we might want to pull RT tasks from other runqueues.
755  */
756 static void switched_from_rt(struct rq *rq, struct task_struct *p,
757                            int running)
758 {
759         /*
760          * If there are other RT tasks then we will reschedule
761          * and the scheduling of the other RT tasks will handle
762          * the balancing. But if we are the last RT task
763          * we may need to handle the pulling of RT tasks
764          * now.
765          */
766         if (!rq->rt.rt_nr_running)
767                 pull_rt_task(rq);
768 }
769 #endif /* CONFIG_SMP */
770
771 /*
772  * When switching a task to RT, we may overload the runqueue
773  * with RT tasks. In this case we try to push them off to
774  * other runqueues.
775  */
776 static void switched_to_rt(struct rq *rq, struct task_struct *p,
777                            int running)
778 {
779         int check_resched = 1;
780
781         /*
782          * If we are already running, then there's nothing
783          * that needs to be done. But if we are not running
784          * we may need to preempt the current running task.
785          * If that current running task is also an RT task
786          * then see if we can move to another run queue.
787          */
788         if (!running) {
789 #ifdef CONFIG_SMP
790                 if (rq->rt.overloaded && push_rt_task(rq) &&
791                     /* Don't resched if we changed runqueues */
792                     rq != task_rq(p))
793                         check_resched = 0;
794 #endif /* CONFIG_SMP */
795                 if (check_resched && p->prio < rq->curr->prio)
796                         resched_task(rq->curr);
797         }
798 }
799
800 /*
801  * Priority of the task has changed. This may cause
802  * us to initiate a push or pull.
803  */
804 static void prio_changed_rt(struct rq *rq, struct task_struct *p,
805                             int oldprio, int running)
806 {
807         if (running) {
808 #ifdef CONFIG_SMP
809                 /*
810                  * If our priority decreases while running, we
811                  * may need to pull tasks to this runqueue.
812                  */
813                 if (oldprio < p->prio)
814                         pull_rt_task(rq);
815                 /*
816                  * If there's a higher priority task waiting to run
817                  * then reschedule.
818                  */
819                 if (p->prio > rq->rt.highest_prio)
820                         resched_task(p);
821 #else
822                 /* For UP simply resched on drop of prio */
823                 if (oldprio < p->prio)
824                         resched_task(p);
825 #endif /* CONFIG_SMP */
826         } else {
827                 /*
828                  * This task is not running, but if it is
829                  * greater than the current running task
830                  * then reschedule.
831                  */
832                 if (p->prio < rq->curr->prio)
833                         resched_task(rq->curr);
834         }
835 }
836
837
838 static void task_tick_rt(struct rq *rq, struct task_struct *p)
839 {
840         update_curr_rt(rq);
841
842         /*
843          * RR tasks need a special form of timeslice management.
844          * FIFO tasks have no timeslices.
845          */
846         if (p->policy != SCHED_RR)
847                 return;
848
849         if (--p->rt.time_slice)
850                 return;
851
852         p->rt.time_slice = DEF_TIMESLICE;
853
854         /*
855          * Requeue to the end of queue if we are not the only element
856          * on the queue:
857          */
858         if (p->rt.run_list.prev != p->rt.run_list.next) {
859                 requeue_task_rt(rq, p);
860                 set_tsk_need_resched(p);
861         }
862 }
863
864 static void set_curr_task_rt(struct rq *rq)
865 {
866         struct task_struct *p = rq->curr;
867
868         p->se.exec_start = rq->clock;
869 }
870
871 const struct sched_class rt_sched_class = {
872         .next                   = &fair_sched_class,
873         .enqueue_task           = enqueue_task_rt,
874         .dequeue_task           = dequeue_task_rt,
875         .yield_task             = yield_task_rt,
876 #ifdef CONFIG_SMP
877         .select_task_rq         = select_task_rq_rt,
878 #endif /* CONFIG_SMP */
879
880         .check_preempt_curr     = check_preempt_curr_rt,
881
882         .pick_next_task         = pick_next_task_rt,
883         .put_prev_task          = put_prev_task_rt,
884
885 #ifdef CONFIG_SMP
886         .load_balance           = load_balance_rt,
887         .move_one_task          = move_one_task_rt,
888         .set_cpus_allowed       = set_cpus_allowed_rt,
889         .join_domain            = join_domain_rt,
890         .leave_domain           = leave_domain_rt,
891         .pre_schedule           = pre_schedule_rt,
892         .post_schedule          = post_schedule_rt,
893         .task_wake_up           = task_wake_up_rt,
894         .switched_from          = switched_from_rt,
895 #endif
896
897         .set_curr_task          = set_curr_task_rt,
898         .task_tick              = task_tick_rt,
899
900         .prio_changed           = prio_changed_rt,
901         .switched_to            = switched_to_rt,
902 };